2 * net/sched/sch_fq.c Fair Queue Packet Scheduler (per flow pacing)
4 * Copyright (C) 2013 Eric Dumazet <edumazet@google.com>
6 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU General Public License
8 * as published by the Free Software Foundation; either version
9 * 2 of the License, or (at your option) any later version.
11 * Meant to be mostly used for localy generated traffic :
12 * Fast classification depends on skb->sk being set before reaching us.
13 * If not, (router workload), we use rxhash as fallback, with 32 bits wide hash.
14 * All packets belonging to a socket are considered as a 'flow'.
16 * Flows are dynamically allocated and stored in a hash table of RB trees
17 * They are also part of one Round Robin 'queues' (new or old flows)
19 * Burst avoidance (aka pacing) capability :
21 * Transport (eg TCP) can set in sk->sk_pacing_rate a rate, enqueue a
22 * bunch of packets, and this packet scheduler adds delay between
23 * packets to respect rate limitation.
26 * - lookup one RB tree (out of 1024 or more) to find the flow.
27 * If non existent flow, create it, add it to the tree.
28 * Add skb to the per flow list of skb (fifo).
29 * - Use a special fifo for high prio packets
31 * dequeue() : serves flows in Round Robin
32 * Note : When a flow becomes empty, we do not immediately remove it from
33 * rb trees, for performance reasons (its expected to send additional packets,
34 * or SLAB cache will reuse socket for another flow)
37 #include <linux/module.h>
38 #include <linux/types.h>
39 #include <linux/kernel.h>
40 #include <linux/jiffies.h>
41 #include <linux/string.h>
43 #include <linux/errno.h>
44 #include <linux/init.h>
45 #include <linux/skbuff.h>
46 #include <linux/slab.h>
47 #include <linux/rbtree.h>
48 #include <linux/hash.h>
49 #include <linux/prefetch.h>
50 #include <linux/vmalloc.h>
51 #include <net/netlink.h>
52 #include <net/pkt_sched.h>
54 #include <net/tcp_states.h>
57 * Per flow structure, dynamically allocated
60 struct sk_buff
*head
; /* list of skbs for this flow : first skb */
62 struct sk_buff
*tail
; /* last skb in the list */
63 unsigned long age
; /* jiffies when flow was emptied, for gc */
65 struct rb_node fq_node
; /* anchor in fq_root[] trees */
67 int qlen
; /* number of packets in flow queue */
69 u32 socket_hash
; /* sk_hash */
70 struct fq_flow
*next
; /* next pointer in RR lists, or &detached */
72 struct rb_node rate_node
; /* anchor in q->delayed tree */
77 struct fq_flow
*first
;
81 struct fq_sched_data
{
82 struct fq_flow_head new_flows
;
84 struct fq_flow_head old_flows
;
86 struct rb_root delayed
; /* for rate limited flows */
87 u64 time_next_delayed_flow
;
89 struct fq_flow internal
; /* for non classified or high prio packets */
92 u32 flow_refill_delay
;
93 u32 flow_max_rate
; /* optional max rate per flow */
94 u32 flow_plimit
; /* max packets per flow */
95 struct rb_root
*fq_root
;
104 u64 stat_internal_packets
;
105 u64 stat_tcp_retrans
;
107 u64 stat_flows_plimit
;
108 u64 stat_pkts_too_long
;
109 u64 stat_allocation_errors
;
110 struct qdisc_watchdog watchdog
;
113 /* special value to mark a detached flow (not on old/new list) */
114 static struct fq_flow detached
, throttled
;
116 static void fq_flow_set_detached(struct fq_flow
*f
)
122 static bool fq_flow_is_detached(const struct fq_flow
*f
)
124 return f
->next
== &detached
;
127 static void fq_flow_set_throttled(struct fq_sched_data
*q
, struct fq_flow
*f
)
129 struct rb_node
**p
= &q
->delayed
.rb_node
, *parent
= NULL
;
135 aux
= container_of(parent
, struct fq_flow
, rate_node
);
136 if (f
->time_next_packet
>= aux
->time_next_packet
)
137 p
= &parent
->rb_right
;
139 p
= &parent
->rb_left
;
141 rb_link_node(&f
->rate_node
, parent
, p
);
142 rb_insert_color(&f
->rate_node
, &q
->delayed
);
143 q
->throttled_flows
++;
146 f
->next
= &throttled
;
147 if (q
->time_next_delayed_flow
> f
->time_next_packet
)
148 q
->time_next_delayed_flow
= f
->time_next_packet
;
152 static struct kmem_cache
*fq_flow_cachep __read_mostly
;
154 static void fq_flow_add_tail(struct fq_flow_head
*head
, struct fq_flow
*flow
)
157 head
->last
->next
= flow
;
164 /* limit number of collected flows per round */
166 #define FQ_GC_AGE (3*HZ)
168 static bool fq_gc_candidate(const struct fq_flow
*f
)
170 return fq_flow_is_detached(f
) &&
171 time_after(jiffies
, f
->age
+ FQ_GC_AGE
);
174 static void fq_gc(struct fq_sched_data
*q
,
175 struct rb_root
*root
,
178 struct fq_flow
*f
, *tofree
[FQ_GC_MAX
];
179 struct rb_node
**p
, *parent
;
187 f
= container_of(parent
, struct fq_flow
, fq_node
);
191 if (fq_gc_candidate(f
)) {
193 if (fcnt
== FQ_GC_MAX
)
198 p
= &parent
->rb_right
;
200 p
= &parent
->rb_left
;
204 q
->inactive_flows
-= fcnt
;
205 q
->stat_gc_flows
+= fcnt
;
207 struct fq_flow
*f
= tofree
[--fcnt
];
209 rb_erase(&f
->fq_node
, root
);
210 kmem_cache_free(fq_flow_cachep
, f
);
214 static struct fq_flow
*fq_classify(struct sk_buff
*skb
, struct fq_sched_data
*q
)
216 struct rb_node
**p
, *parent
;
217 struct sock
*sk
= skb
->sk
;
218 struct rb_root
*root
;
221 /* warning: no starvation prevention... */
222 if (unlikely((skb
->priority
& TC_PRIO_MAX
) == TC_PRIO_CONTROL
))
226 /* By forcing low order bit to 1, we make sure to not
227 * collide with a local flow (socket pointers are word aligned)
229 sk
= (struct sock
*)(skb_get_hash(skb
) | 1L);
232 root
= &q
->fq_root
[hash_32((u32
)(long)sk
, q
->fq_trees_log
)];
234 if (q
->flows
>= (2U << q
->fq_trees_log
) &&
235 q
->inactive_flows
> q
->flows
/2)
243 f
= container_of(parent
, struct fq_flow
, fq_node
);
245 /* socket might have been reallocated, so check
246 * if its sk_hash is the same.
247 * It not, we need to refill credit with
250 if (unlikely(skb
->sk
&&
251 f
->socket_hash
!= sk
->sk_hash
)) {
252 f
->credit
= q
->initial_quantum
;
253 f
->socket_hash
= sk
->sk_hash
;
254 f
->time_next_packet
= 0ULL;
259 p
= &parent
->rb_right
;
261 p
= &parent
->rb_left
;
264 f
= kmem_cache_zalloc(fq_flow_cachep
, GFP_ATOMIC
| __GFP_NOWARN
);
266 q
->stat_allocation_errors
++;
269 fq_flow_set_detached(f
);
272 f
->socket_hash
= sk
->sk_hash
;
273 f
->credit
= q
->initial_quantum
;
275 rb_link_node(&f
->fq_node
, parent
, p
);
276 rb_insert_color(&f
->fq_node
, root
);
284 /* remove one skb from head of flow queue */
285 static struct sk_buff
*fq_dequeue_head(struct Qdisc
*sch
, struct fq_flow
*flow
)
287 struct sk_buff
*skb
= flow
->head
;
290 flow
->head
= skb
->next
;
293 qdisc_qstats_backlog_dec(sch
, skb
);
299 /* We might add in the future detection of retransmits
300 * For the time being, just return false
302 static bool skb_is_retransmit(struct sk_buff
*skb
)
307 /* add skb to flow queue
308 * flow queue is a linked list, kind of FIFO, except for TCP retransmits
309 * We special case tcp retransmits to be transmitted before other packets.
310 * We rely on fact that TCP retransmits are unlikely, so we do not waste
311 * a separate queue or a pointer.
312 * head-> [retrans pkt 1]
317 * tail-> [ normal pkt 4]
319 static void flow_queue_add(struct fq_flow
*flow
, struct sk_buff
*skb
)
321 struct sk_buff
*prev
, *head
= flow
->head
;
329 if (likely(!skb_is_retransmit(skb
))) {
330 flow
->tail
->next
= skb
;
335 /* This skb is a tcp retransmit,
336 * find the last retrans packet in the queue
339 while (skb_is_retransmit(head
)) {
345 if (!prev
) { /* no rtx packet in queue, become the new head */
346 skb
->next
= flow
->head
;
349 if (prev
== flow
->tail
)
352 skb
->next
= prev
->next
;
357 static int fq_enqueue(struct sk_buff
*skb
, struct Qdisc
*sch
)
359 struct fq_sched_data
*q
= qdisc_priv(sch
);
362 if (unlikely(sch
->q
.qlen
>= sch
->limit
))
363 return qdisc_drop(skb
, sch
);
365 f
= fq_classify(skb
, q
);
366 if (unlikely(f
->qlen
>= q
->flow_plimit
&& f
!= &q
->internal
)) {
367 q
->stat_flows_plimit
++;
368 return qdisc_drop(skb
, sch
);
372 if (skb_is_retransmit(skb
))
373 q
->stat_tcp_retrans
++;
374 qdisc_qstats_backlog_inc(sch
, skb
);
375 if (fq_flow_is_detached(f
)) {
376 fq_flow_add_tail(&q
->new_flows
, f
);
377 if (time_after(jiffies
, f
->age
+ q
->flow_refill_delay
))
378 f
->credit
= max_t(u32
, f
->credit
, q
->quantum
);
382 /* Note: this overwrites f->age */
383 flow_queue_add(f
, skb
);
385 if (unlikely(f
== &q
->internal
)) {
386 q
->stat_internal_packets
++;
390 return NET_XMIT_SUCCESS
;
393 static void fq_check_throttled(struct fq_sched_data
*q
, u64 now
)
397 if (q
->time_next_delayed_flow
> now
)
400 q
->time_next_delayed_flow
= ~0ULL;
401 while ((p
= rb_first(&q
->delayed
)) != NULL
) {
402 struct fq_flow
*f
= container_of(p
, struct fq_flow
, rate_node
);
404 if (f
->time_next_packet
> now
) {
405 q
->time_next_delayed_flow
= f
->time_next_packet
;
408 rb_erase(p
, &q
->delayed
);
409 q
->throttled_flows
--;
410 fq_flow_add_tail(&q
->old_flows
, f
);
414 static struct sk_buff
*fq_dequeue(struct Qdisc
*sch
)
416 struct fq_sched_data
*q
= qdisc_priv(sch
);
417 u64 now
= ktime_get_ns();
418 struct fq_flow_head
*head
;
423 skb
= fq_dequeue_head(sch
, &q
->internal
);
426 fq_check_throttled(q
, now
);
428 head
= &q
->new_flows
;
430 head
= &q
->old_flows
;
432 if (q
->time_next_delayed_flow
!= ~0ULL)
433 qdisc_watchdog_schedule_ns(&q
->watchdog
,
434 q
->time_next_delayed_flow
,
441 if (f
->credit
<= 0) {
442 f
->credit
+= q
->quantum
;
443 head
->first
= f
->next
;
444 fq_flow_add_tail(&q
->old_flows
, f
);
448 if (unlikely(f
->head
&& now
< f
->time_next_packet
)) {
449 head
->first
= f
->next
;
450 fq_flow_set_throttled(q
, f
);
454 skb
= fq_dequeue_head(sch
, f
);
456 head
->first
= f
->next
;
457 /* force a pass through old_flows to prevent starvation */
458 if ((head
== &q
->new_flows
) && q
->old_flows
.first
) {
459 fq_flow_add_tail(&q
->old_flows
, f
);
461 fq_flow_set_detached(f
);
467 f
->time_next_packet
= now
;
468 f
->credit
-= qdisc_pkt_len(skb
);
470 if (f
->credit
> 0 || !q
->rate_enable
)
473 rate
= q
->flow_max_rate
;
474 if (skb
->sk
&& skb
->sk
->sk_state
!= TCP_TIME_WAIT
)
475 rate
= min(skb
->sk
->sk_pacing_rate
, rate
);
478 u32 plen
= max(qdisc_pkt_len(skb
), q
->quantum
);
479 u64 len
= (u64
)plen
* NSEC_PER_SEC
;
483 /* Since socket rate can change later,
484 * clamp the delay to 1 second.
485 * Really, providers of too big packets should be fixed !
487 if (unlikely(len
> NSEC_PER_SEC
)) {
489 q
->stat_pkts_too_long
++;
492 f
->time_next_packet
= now
+ len
;
495 qdisc_bstats_update(sch
, skb
);
499 static void fq_reset(struct Qdisc
*sch
)
501 struct fq_sched_data
*q
= qdisc_priv(sch
);
502 struct rb_root
*root
;
508 while ((skb
= fq_dequeue_head(sch
, &q
->internal
)) != NULL
)
514 for (idx
= 0; idx
< (1U << q
->fq_trees_log
); idx
++) {
515 root
= &q
->fq_root
[idx
];
516 while ((p
= rb_first(root
)) != NULL
) {
517 f
= container_of(p
, struct fq_flow
, fq_node
);
520 while ((skb
= fq_dequeue_head(sch
, f
)) != NULL
)
523 kmem_cache_free(fq_flow_cachep
, f
);
526 q
->new_flows
.first
= NULL
;
527 q
->old_flows
.first
= NULL
;
528 q
->delayed
= RB_ROOT
;
530 q
->inactive_flows
= 0;
531 q
->throttled_flows
= 0;
534 static void fq_rehash(struct fq_sched_data
*q
,
535 struct rb_root
*old_array
, u32 old_log
,
536 struct rb_root
*new_array
, u32 new_log
)
538 struct rb_node
*op
, **np
, *parent
;
539 struct rb_root
*oroot
, *nroot
;
540 struct fq_flow
*of
, *nf
;
544 for (idx
= 0; idx
< (1U << old_log
); idx
++) {
545 oroot
= &old_array
[idx
];
546 while ((op
= rb_first(oroot
)) != NULL
) {
548 of
= container_of(op
, struct fq_flow
, fq_node
);
549 if (fq_gc_candidate(of
)) {
551 kmem_cache_free(fq_flow_cachep
, of
);
554 nroot
= &new_array
[hash_32((u32
)(long)of
->sk
, new_log
)];
556 np
= &nroot
->rb_node
;
561 nf
= container_of(parent
, struct fq_flow
, fq_node
);
562 BUG_ON(nf
->sk
== of
->sk
);
565 np
= &parent
->rb_right
;
567 np
= &parent
->rb_left
;
570 rb_link_node(&of
->fq_node
, parent
, np
);
571 rb_insert_color(&of
->fq_node
, nroot
);
575 q
->inactive_flows
-= fcnt
;
576 q
->stat_gc_flows
+= fcnt
;
579 static void *fq_alloc_node(size_t sz
, int node
)
583 ptr
= kmalloc_node(sz
, GFP_KERNEL
| __GFP_REPEAT
| __GFP_NOWARN
, node
);
585 ptr
= vmalloc_node(sz
, node
);
589 static void fq_free(void *addr
)
594 static int fq_resize(struct Qdisc
*sch
, u32 log
)
596 struct fq_sched_data
*q
= qdisc_priv(sch
);
597 struct rb_root
*array
;
601 if (q
->fq_root
&& log
== q
->fq_trees_log
)
604 /* If XPS was setup, we can allocate memory on right NUMA node */
605 array
= fq_alloc_node(sizeof(struct rb_root
) << log
,
606 netdev_queue_numa_node_read(sch
->dev_queue
));
610 for (idx
= 0; idx
< (1U << log
); idx
++)
611 array
[idx
] = RB_ROOT
;
615 old_fq_root
= q
->fq_root
;
617 fq_rehash(q
, old_fq_root
, q
->fq_trees_log
, array
, log
);
620 q
->fq_trees_log
= log
;
622 sch_tree_unlock(sch
);
624 fq_free(old_fq_root
);
629 static const struct nla_policy fq_policy
[TCA_FQ_MAX
+ 1] = {
630 [TCA_FQ_PLIMIT
] = { .type
= NLA_U32
},
631 [TCA_FQ_FLOW_PLIMIT
] = { .type
= NLA_U32
},
632 [TCA_FQ_QUANTUM
] = { .type
= NLA_U32
},
633 [TCA_FQ_INITIAL_QUANTUM
] = { .type
= NLA_U32
},
634 [TCA_FQ_RATE_ENABLE
] = { .type
= NLA_U32
},
635 [TCA_FQ_FLOW_DEFAULT_RATE
] = { .type
= NLA_U32
},
636 [TCA_FQ_FLOW_MAX_RATE
] = { .type
= NLA_U32
},
637 [TCA_FQ_BUCKETS_LOG
] = { .type
= NLA_U32
},
638 [TCA_FQ_FLOW_REFILL_DELAY
] = { .type
= NLA_U32
},
641 static int fq_change(struct Qdisc
*sch
, struct nlattr
*opt
)
643 struct fq_sched_data
*q
= qdisc_priv(sch
);
644 struct nlattr
*tb
[TCA_FQ_MAX
+ 1];
645 int err
, drop_count
= 0;
651 err
= nla_parse_nested(tb
, TCA_FQ_MAX
, opt
, fq_policy
);
657 fq_log
= q
->fq_trees_log
;
659 if (tb
[TCA_FQ_BUCKETS_LOG
]) {
660 u32 nval
= nla_get_u32(tb
[TCA_FQ_BUCKETS_LOG
]);
662 if (nval
>= 1 && nval
<= ilog2(256*1024))
667 if (tb
[TCA_FQ_PLIMIT
])
668 sch
->limit
= nla_get_u32(tb
[TCA_FQ_PLIMIT
]);
670 if (tb
[TCA_FQ_FLOW_PLIMIT
])
671 q
->flow_plimit
= nla_get_u32(tb
[TCA_FQ_FLOW_PLIMIT
]);
673 if (tb
[TCA_FQ_QUANTUM
])
674 q
->quantum
= nla_get_u32(tb
[TCA_FQ_QUANTUM
]);
676 if (tb
[TCA_FQ_INITIAL_QUANTUM
])
677 q
->initial_quantum
= nla_get_u32(tb
[TCA_FQ_INITIAL_QUANTUM
]);
679 if (tb
[TCA_FQ_FLOW_DEFAULT_RATE
])
680 pr_warn_ratelimited("sch_fq: defrate %u ignored.\n",
681 nla_get_u32(tb
[TCA_FQ_FLOW_DEFAULT_RATE
]));
683 if (tb
[TCA_FQ_FLOW_MAX_RATE
])
684 q
->flow_max_rate
= nla_get_u32(tb
[TCA_FQ_FLOW_MAX_RATE
]);
686 if (tb
[TCA_FQ_RATE_ENABLE
]) {
687 u32 enable
= nla_get_u32(tb
[TCA_FQ_RATE_ENABLE
]);
690 q
->rate_enable
= enable
;
695 if (tb
[TCA_FQ_FLOW_REFILL_DELAY
]) {
696 u32 usecs_delay
= nla_get_u32(tb
[TCA_FQ_FLOW_REFILL_DELAY
]) ;
698 q
->flow_refill_delay
= usecs_to_jiffies(usecs_delay
);
702 sch_tree_unlock(sch
);
703 err
= fq_resize(sch
, fq_log
);
706 while (sch
->q
.qlen
> sch
->limit
) {
707 struct sk_buff
*skb
= fq_dequeue(sch
);
714 qdisc_tree_decrease_qlen(sch
, drop_count
);
716 sch_tree_unlock(sch
);
720 static void fq_destroy(struct Qdisc
*sch
)
722 struct fq_sched_data
*q
= qdisc_priv(sch
);
726 qdisc_watchdog_cancel(&q
->watchdog
);
729 static int fq_init(struct Qdisc
*sch
, struct nlattr
*opt
)
731 struct fq_sched_data
*q
= qdisc_priv(sch
);
735 q
->flow_plimit
= 100;
736 q
->quantum
= 2 * psched_mtu(qdisc_dev(sch
));
737 q
->initial_quantum
= 10 * psched_mtu(qdisc_dev(sch
));
738 q
->flow_refill_delay
= msecs_to_jiffies(40);
739 q
->flow_max_rate
= ~0U;
741 q
->new_flows
.first
= NULL
;
742 q
->old_flows
.first
= NULL
;
743 q
->delayed
= RB_ROOT
;
745 q
->fq_trees_log
= ilog2(1024);
746 qdisc_watchdog_init(&q
->watchdog
, sch
);
749 err
= fq_change(sch
, opt
);
751 err
= fq_resize(sch
, q
->fq_trees_log
);
756 static int fq_dump(struct Qdisc
*sch
, struct sk_buff
*skb
)
758 struct fq_sched_data
*q
= qdisc_priv(sch
);
761 opts
= nla_nest_start(skb
, TCA_OPTIONS
);
763 goto nla_put_failure
;
765 /* TCA_FQ_FLOW_DEFAULT_RATE is not used anymore */
767 if (nla_put_u32(skb
, TCA_FQ_PLIMIT
, sch
->limit
) ||
768 nla_put_u32(skb
, TCA_FQ_FLOW_PLIMIT
, q
->flow_plimit
) ||
769 nla_put_u32(skb
, TCA_FQ_QUANTUM
, q
->quantum
) ||
770 nla_put_u32(skb
, TCA_FQ_INITIAL_QUANTUM
, q
->initial_quantum
) ||
771 nla_put_u32(skb
, TCA_FQ_RATE_ENABLE
, q
->rate_enable
) ||
772 nla_put_u32(skb
, TCA_FQ_FLOW_MAX_RATE
, q
->flow_max_rate
) ||
773 nla_put_u32(skb
, TCA_FQ_FLOW_REFILL_DELAY
,
774 jiffies_to_usecs(q
->flow_refill_delay
)) ||
775 nla_put_u32(skb
, TCA_FQ_BUCKETS_LOG
, q
->fq_trees_log
))
776 goto nla_put_failure
;
778 return nla_nest_end(skb
, opts
);
784 static int fq_dump_stats(struct Qdisc
*sch
, struct gnet_dump
*d
)
786 struct fq_sched_data
*q
= qdisc_priv(sch
);
787 u64 now
= ktime_get_ns();
788 struct tc_fq_qd_stats st
= {
789 .gc_flows
= q
->stat_gc_flows
,
790 .highprio_packets
= q
->stat_internal_packets
,
791 .tcp_retrans
= q
->stat_tcp_retrans
,
792 .throttled
= q
->stat_throttled
,
793 .flows_plimit
= q
->stat_flows_plimit
,
794 .pkts_too_long
= q
->stat_pkts_too_long
,
795 .allocation_errors
= q
->stat_allocation_errors
,
797 .inactive_flows
= q
->inactive_flows
,
798 .throttled_flows
= q
->throttled_flows
,
799 .time_next_delayed_flow
= q
->time_next_delayed_flow
- now
,
802 return gnet_stats_copy_app(d
, &st
, sizeof(st
));
805 static struct Qdisc_ops fq_qdisc_ops __read_mostly
= {
807 .priv_size
= sizeof(struct fq_sched_data
),
809 .enqueue
= fq_enqueue
,
810 .dequeue
= fq_dequeue
,
811 .peek
= qdisc_peek_dequeued
,
814 .destroy
= fq_destroy
,
817 .dump_stats
= fq_dump_stats
,
818 .owner
= THIS_MODULE
,
821 static int __init
fq_module_init(void)
825 fq_flow_cachep
= kmem_cache_create("fq_flow_cache",
826 sizeof(struct fq_flow
),
831 ret
= register_qdisc(&fq_qdisc_ops
);
833 kmem_cache_destroy(fq_flow_cachep
);
837 static void __exit
fq_module_exit(void)
839 unregister_qdisc(&fq_qdisc_ops
);
840 kmem_cache_destroy(fq_flow_cachep
);
843 module_init(fq_module_init
)
844 module_exit(fq_module_exit
)
845 MODULE_AUTHOR("Eric Dumazet");
846 MODULE_LICENSE("GPL");