net/sched/sch_fq.c

3  * net/sched/sch_fq.c Fair Queue Packet Scheduler (per flow pacing)
10  *  All packets belonging to a socket are considered as a 'flow'.
22  *   - lookup one RB tree (out of 1024 or more) to find the flow.
23  *     If non existent flow, create it, add it to the tree.
24  *     Add skb to the per flow list of skb (fifo).
28  *  Note : When a flow becomes empty, we do not immediately remove it from
30  *  or SLAB cache will reuse socket for another flow)
65  * Per flow structure, dynamically allocated.
72 	struct sk_buff	*head;		/* list of skbs for this flow : first skb */
75 		unsigned long  age;	/* (jiffies | 1UL) when flow was emptied, for gc */
86 	int		qlen;		/* number of packets in flow queue */
117 	u32		flow_plimit;	/* max packets per flow */
118 	unsigned long	flow_max_rate;	/* optional max rate per flow */
183 /* special value to mark a throttled flow (not on old/new list) */
196 static void fq_flow_add_tail(struct fq_sched_data *q, struct fq_flow *flow,
199 	struct fq_perband_flows *pband = &q->band_flows[flow->band];
205 		head->last->next = flow;
207 		head->first = flow;
208 	head->last = flow;
209 	flow->next = NULL;
304  *   (no flow is currently eligible for transmit,
360 	 * 2) They are not part of a 'flow' yet
369 		 * collide with a local flow (socket pointers are word aligned)
455 static struct sk_buff *fq_peek(struct fq_flow *flow)
457 	struct sk_buff *skb = skb_rb_first(&flow->t_root);
458 	struct sk_buff *head = flow->head;
471 static void fq_erase_head(struct Qdisc *sch, struct fq_flow *flow,
474 	if (skb == flow->head) {
475 		flow->head = skb->next;
477 		rb_erase(&skb->rbnode, &flow->t_root);
482 /* Remove one skb from flow queue.
485 static void fq_dequeue_skb(struct Qdisc *sch, struct fq_flow *flow,
488 	fq_erase_head(sch, flow, skb);
494 static void flow_queue_add(struct fq_flow *flow, struct sk_buff *skb)
499 	head = flow->head;
501 	    fq_skb_cb(skb)->time_to_send >= fq_skb_cb(flow->tail)->time_to_send) {
503 			flow->head = skb;
505 			flow->tail->next = skb;
506 		flow->tail = skb;
511 	p = &flow->t_root.rb_node;
523 	rb_insert_color(&skb->rbnode, &flow->t_root);
724 	 * a flow max rate.
764 static void fq_flow_purge(struct fq_flow *flow)
766 	struct rb_node *p = rb_first(&flow->t_root);
772 		rb_erase(&skb->rbnode, &flow->t_root);
775 	rtnl_kfree_skbs(flow->head, flow->tail);
776 	flow->head = NULL;
777 	flow->qlen = 0;