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 <net/netlink.h>
51 #include <net/pkt_sched.h>
53 #include <net/tcp_states.h>
56 * Per flow structure, dynamically allocated
59 struct sk_buff
*head
; /* list of skbs for this flow : first skb */
61 struct sk_buff
*tail
; /* last skb in the list */
62 unsigned long age
; /* jiffies when flow was emptied, for gc */
64 struct rb_node fq_node
; /* anchor in fq_root[] trees */
66 int qlen
; /* number of packets in flow queue */
68 u32 socket_hash
; /* sk_hash */
69 struct fq_flow
*next
; /* next pointer in RR lists, or &detached */
71 struct rb_node rate_node
; /* anchor in q->delayed tree */
76 struct fq_flow
*first
;
80 struct fq_sched_data
{
81 struct fq_flow_head new_flows
;
83 struct fq_flow_head old_flows
;
85 struct rb_root delayed
; /* for rate limited flows */
86 u64 time_next_delayed_flow
;
88 struct fq_flow internal
; /* for non classified or high prio packets */
91 u32 flow_max_rate
; /* optional max rate per flow */
92 u32 flow_plimit
; /* max packets per flow */
93 struct rb_root
*fq_root
;
102 u64 stat_internal_packets
;
103 u64 stat_tcp_retrans
;
105 u64 stat_flows_plimit
;
106 u64 stat_pkts_too_long
;
107 u64 stat_allocation_errors
;
108 struct qdisc_watchdog watchdog
;
111 /* special value to mark a detached flow (not on old/new list) */
112 static struct fq_flow detached
, throttled
;
114 static void fq_flow_set_detached(struct fq_flow
*f
)
119 static bool fq_flow_is_detached(const struct fq_flow
*f
)
121 return f
->next
== &detached
;
124 static void fq_flow_set_throttled(struct fq_sched_data
*q
, struct fq_flow
*f
)
126 struct rb_node
**p
= &q
->delayed
.rb_node
, *parent
= NULL
;
132 aux
= container_of(parent
, struct fq_flow
, rate_node
);
133 if (f
->time_next_packet
>= aux
->time_next_packet
)
134 p
= &parent
->rb_right
;
136 p
= &parent
->rb_left
;
138 rb_link_node(&f
->rate_node
, parent
, p
);
139 rb_insert_color(&f
->rate_node
, &q
->delayed
);
140 q
->throttled_flows
++;
143 f
->next
= &throttled
;
144 if (q
->time_next_delayed_flow
> f
->time_next_packet
)
145 q
->time_next_delayed_flow
= f
->time_next_packet
;
149 static struct kmem_cache
*fq_flow_cachep __read_mostly
;
151 static void fq_flow_add_tail(struct fq_flow_head
*head
, struct fq_flow
*flow
)
154 head
->last
->next
= flow
;
161 /* limit number of collected flows per round */
163 #define FQ_GC_AGE (3*HZ)
165 static bool fq_gc_candidate(const struct fq_flow
*f
)
167 return fq_flow_is_detached(f
) &&
168 time_after(jiffies
, f
->age
+ FQ_GC_AGE
);
171 static void fq_gc(struct fq_sched_data
*q
,
172 struct rb_root
*root
,
175 struct fq_flow
*f
, *tofree
[FQ_GC_MAX
];
176 struct rb_node
**p
, *parent
;
184 f
= container_of(parent
, struct fq_flow
, fq_node
);
188 if (fq_gc_candidate(f
)) {
190 if (fcnt
== FQ_GC_MAX
)
195 p
= &parent
->rb_right
;
197 p
= &parent
->rb_left
;
201 q
->inactive_flows
-= fcnt
;
202 q
->stat_gc_flows
+= fcnt
;
204 struct fq_flow
*f
= tofree
[--fcnt
];
206 rb_erase(&f
->fq_node
, root
);
207 kmem_cache_free(fq_flow_cachep
, f
);
211 static struct fq_flow
*fq_classify(struct sk_buff
*skb
, struct fq_sched_data
*q
)
213 struct rb_node
**p
, *parent
;
214 struct sock
*sk
= skb
->sk
;
215 struct rb_root
*root
;
218 /* warning: no starvation prevention... */
219 if (unlikely((skb
->priority
& TC_PRIO_MAX
) == TC_PRIO_CONTROL
))
223 /* By forcing low order bit to 1, we make sure to not
224 * collide with a local flow (socket pointers are word aligned)
226 sk
= (struct sock
*)(skb_get_rxhash(skb
) | 1L);
229 root
= &q
->fq_root
[hash_32((u32
)(long)sk
, q
->fq_trees_log
)];
231 if (q
->flows
>= (2U << q
->fq_trees_log
) &&
232 q
->inactive_flows
> q
->flows
/2)
240 f
= container_of(parent
, struct fq_flow
, fq_node
);
242 /* socket might have been reallocated, so check
243 * if its sk_hash is the same.
244 * It not, we need to refill credit with
247 if (unlikely(skb
->sk
&&
248 f
->socket_hash
!= sk
->sk_hash
)) {
249 f
->credit
= q
->initial_quantum
;
250 f
->socket_hash
= sk
->sk_hash
;
251 f
->time_next_packet
= 0ULL;
256 p
= &parent
->rb_right
;
258 p
= &parent
->rb_left
;
261 f
= kmem_cache_zalloc(fq_flow_cachep
, GFP_ATOMIC
| __GFP_NOWARN
);
263 q
->stat_allocation_errors
++;
266 fq_flow_set_detached(f
);
269 f
->socket_hash
= sk
->sk_hash
;
270 f
->credit
= q
->initial_quantum
;
272 rb_link_node(&f
->fq_node
, parent
, p
);
273 rb_insert_color(&f
->fq_node
, root
);
281 /* remove one skb from head of flow queue */
282 static struct sk_buff
*fq_dequeue_head(struct Qdisc
*sch
, struct fq_flow
*flow
)
284 struct sk_buff
*skb
= flow
->head
;
287 flow
->head
= skb
->next
;
290 sch
->qstats
.backlog
-= qdisc_pkt_len(skb
);
296 /* We might add in the future detection of retransmits
297 * For the time being, just return false
299 static bool skb_is_retransmit(struct sk_buff
*skb
)
304 /* add skb to flow queue
305 * flow queue is a linked list, kind of FIFO, except for TCP retransmits
306 * We special case tcp retransmits to be transmitted before other packets.
307 * We rely on fact that TCP retransmits are unlikely, so we do not waste
308 * a separate queue or a pointer.
309 * head-> [retrans pkt 1]
314 * tail-> [ normal pkt 4]
316 static void flow_queue_add(struct fq_flow
*flow
, struct sk_buff
*skb
)
318 struct sk_buff
*prev
, *head
= flow
->head
;
326 if (likely(!skb_is_retransmit(skb
))) {
327 flow
->tail
->next
= skb
;
332 /* This skb is a tcp retransmit,
333 * find the last retrans packet in the queue
336 while (skb_is_retransmit(head
)) {
342 if (!prev
) { /* no rtx packet in queue, become the new head */
343 skb
->next
= flow
->head
;
346 if (prev
== flow
->tail
)
349 skb
->next
= prev
->next
;
354 static int fq_enqueue(struct sk_buff
*skb
, struct Qdisc
*sch
)
356 struct fq_sched_data
*q
= qdisc_priv(sch
);
359 if (unlikely(sch
->q
.qlen
>= sch
->limit
))
360 return qdisc_drop(skb
, sch
);
362 f
= fq_classify(skb
, q
);
363 if (unlikely(f
->qlen
>= q
->flow_plimit
&& f
!= &q
->internal
)) {
364 q
->stat_flows_plimit
++;
365 return qdisc_drop(skb
, sch
);
369 flow_queue_add(f
, skb
);
370 if (skb_is_retransmit(skb
))
371 q
->stat_tcp_retrans
++;
372 sch
->qstats
.backlog
+= qdisc_pkt_len(skb
);
373 if (fq_flow_is_detached(f
)) {
374 fq_flow_add_tail(&q
->new_flows
, f
);
375 if (q
->quantum
> f
->credit
)
376 f
->credit
= q
->quantum
;
378 qdisc_unthrottled(sch
);
380 if (unlikely(f
== &q
->internal
)) {
381 q
->stat_internal_packets
++;
382 qdisc_unthrottled(sch
);
386 return NET_XMIT_SUCCESS
;
389 static void fq_check_throttled(struct fq_sched_data
*q
, u64 now
)
393 if (q
->time_next_delayed_flow
> now
)
396 q
->time_next_delayed_flow
= ~0ULL;
397 while ((p
= rb_first(&q
->delayed
)) != NULL
) {
398 struct fq_flow
*f
= container_of(p
, struct fq_flow
, rate_node
);
400 if (f
->time_next_packet
> now
) {
401 q
->time_next_delayed_flow
= f
->time_next_packet
;
404 rb_erase(p
, &q
->delayed
);
405 q
->throttled_flows
--;
406 fq_flow_add_tail(&q
->old_flows
, f
);
410 static struct sk_buff
*fq_dequeue(struct Qdisc
*sch
)
412 struct fq_sched_data
*q
= qdisc_priv(sch
);
413 u64 now
= ktime_to_ns(ktime_get());
414 struct fq_flow_head
*head
;
419 skb
= fq_dequeue_head(sch
, &q
->internal
);
422 fq_check_throttled(q
, now
);
424 head
= &q
->new_flows
;
426 head
= &q
->old_flows
;
428 if (q
->time_next_delayed_flow
!= ~0ULL)
429 qdisc_watchdog_schedule_ns(&q
->watchdog
,
430 q
->time_next_delayed_flow
);
436 if (f
->credit
<= 0) {
437 f
->credit
+= q
->quantum
;
438 head
->first
= f
->next
;
439 fq_flow_add_tail(&q
->old_flows
, f
);
443 if (unlikely(f
->head
&& now
< f
->time_next_packet
)) {
444 head
->first
= f
->next
;
445 fq_flow_set_throttled(q
, f
);
449 skb
= fq_dequeue_head(sch
, f
);
451 head
->first
= f
->next
;
452 /* force a pass through old_flows to prevent starvation */
453 if ((head
== &q
->new_flows
) && q
->old_flows
.first
) {
454 fq_flow_add_tail(&q
->old_flows
, f
);
456 fq_flow_set_detached(f
);
463 f
->time_next_packet
= now
;
464 f
->credit
-= qdisc_pkt_len(skb
);
466 if (f
->credit
> 0 || !q
->rate_enable
)
469 rate
= q
->flow_max_rate
;
470 if (skb
->sk
&& skb
->sk
->sk_state
!= TCP_TIME_WAIT
)
471 rate
= min(skb
->sk
->sk_pacing_rate
, rate
);
474 u32 plen
= max(qdisc_pkt_len(skb
), q
->quantum
);
475 u64 len
= (u64
)plen
* NSEC_PER_SEC
;
479 /* Since socket rate can change later,
480 * clamp the delay to 125 ms.
481 * TODO: maybe segment the too big skb, as in commit
482 * e43ac79a4bc ("sch_tbf: segment too big GSO packets")
484 if (unlikely(len
> 125 * NSEC_PER_MSEC
)) {
485 len
= 125 * NSEC_PER_MSEC
;
486 q
->stat_pkts_too_long
++;
489 f
->time_next_packet
= now
+ len
;
492 qdisc_bstats_update(sch
, skb
);
493 qdisc_unthrottled(sch
);
497 static void fq_reset(struct Qdisc
*sch
)
499 struct fq_sched_data
*q
= qdisc_priv(sch
);
500 struct rb_root
*root
;
506 while ((skb
= fq_dequeue_head(sch
, &q
->internal
)) != NULL
)
512 for (idx
= 0; idx
< (1U << q
->fq_trees_log
); idx
++) {
513 root
= &q
->fq_root
[idx
];
514 while ((p
= rb_first(root
)) != NULL
) {
515 f
= container_of(p
, struct fq_flow
, fq_node
);
518 while ((skb
= fq_dequeue_head(sch
, f
)) != NULL
)
521 kmem_cache_free(fq_flow_cachep
, f
);
524 q
->new_flows
.first
= NULL
;
525 q
->old_flows
.first
= NULL
;
526 q
->delayed
= RB_ROOT
;
528 q
->inactive_flows
= 0;
529 q
->throttled_flows
= 0;
532 static void fq_rehash(struct fq_sched_data
*q
,
533 struct rb_root
*old_array
, u32 old_log
,
534 struct rb_root
*new_array
, u32 new_log
)
536 struct rb_node
*op
, **np
, *parent
;
537 struct rb_root
*oroot
, *nroot
;
538 struct fq_flow
*of
, *nf
;
542 for (idx
= 0; idx
< (1U << old_log
); idx
++) {
543 oroot
= &old_array
[idx
];
544 while ((op
= rb_first(oroot
)) != NULL
) {
546 of
= container_of(op
, struct fq_flow
, fq_node
);
547 if (fq_gc_candidate(of
)) {
549 kmem_cache_free(fq_flow_cachep
, of
);
552 nroot
= &new_array
[hash_32((u32
)(long)of
->sk
, new_log
)];
554 np
= &nroot
->rb_node
;
559 nf
= container_of(parent
, struct fq_flow
, fq_node
);
560 BUG_ON(nf
->sk
== of
->sk
);
563 np
= &parent
->rb_right
;
565 np
= &parent
->rb_left
;
568 rb_link_node(&of
->fq_node
, parent
, np
);
569 rb_insert_color(&of
->fq_node
, nroot
);
573 q
->inactive_flows
-= fcnt
;
574 q
->stat_gc_flows
+= fcnt
;
577 static int fq_resize(struct fq_sched_data
*q
, u32 log
)
579 struct rb_root
*array
;
582 if (q
->fq_root
&& log
== q
->fq_trees_log
)
585 array
= kmalloc(sizeof(struct rb_root
) << log
, GFP_KERNEL
);
589 for (idx
= 0; idx
< (1U << log
); idx
++)
590 array
[idx
] = RB_ROOT
;
593 fq_rehash(q
, q
->fq_root
, q
->fq_trees_log
, array
, log
);
597 q
->fq_trees_log
= log
;
602 static const struct nla_policy fq_policy
[TCA_FQ_MAX
+ 1] = {
603 [TCA_FQ_PLIMIT
] = { .type
= NLA_U32
},
604 [TCA_FQ_FLOW_PLIMIT
] = { .type
= NLA_U32
},
605 [TCA_FQ_QUANTUM
] = { .type
= NLA_U32
},
606 [TCA_FQ_INITIAL_QUANTUM
] = { .type
= NLA_U32
},
607 [TCA_FQ_RATE_ENABLE
] = { .type
= NLA_U32
},
608 [TCA_FQ_FLOW_DEFAULT_RATE
] = { .type
= NLA_U32
},
609 [TCA_FQ_FLOW_MAX_RATE
] = { .type
= NLA_U32
},
610 [TCA_FQ_BUCKETS_LOG
] = { .type
= NLA_U32
},
613 static int fq_change(struct Qdisc
*sch
, struct nlattr
*opt
)
615 struct fq_sched_data
*q
= qdisc_priv(sch
);
616 struct nlattr
*tb
[TCA_FQ_MAX
+ 1];
617 int err
, drop_count
= 0;
623 err
= nla_parse_nested(tb
, TCA_FQ_MAX
, opt
, fq_policy
);
629 fq_log
= q
->fq_trees_log
;
631 if (tb
[TCA_FQ_BUCKETS_LOG
]) {
632 u32 nval
= nla_get_u32(tb
[TCA_FQ_BUCKETS_LOG
]);
634 if (nval
>= 1 && nval
<= ilog2(256*1024))
639 if (tb
[TCA_FQ_PLIMIT
])
640 sch
->limit
= nla_get_u32(tb
[TCA_FQ_PLIMIT
]);
642 if (tb
[TCA_FQ_FLOW_PLIMIT
])
643 q
->flow_plimit
= nla_get_u32(tb
[TCA_FQ_FLOW_PLIMIT
]);
645 if (tb
[TCA_FQ_QUANTUM
])
646 q
->quantum
= nla_get_u32(tb
[TCA_FQ_QUANTUM
]);
648 if (tb
[TCA_FQ_INITIAL_QUANTUM
])
649 q
->initial_quantum
= nla_get_u32(tb
[TCA_FQ_INITIAL_QUANTUM
]);
651 if (tb
[TCA_FQ_FLOW_DEFAULT_RATE
])
652 pr_warn_ratelimited("sch_fq: defrate %u ignored.\n",
653 nla_get_u32(tb
[TCA_FQ_FLOW_DEFAULT_RATE
]));
655 if (tb
[TCA_FQ_FLOW_MAX_RATE
])
656 q
->flow_max_rate
= nla_get_u32(tb
[TCA_FQ_FLOW_MAX_RATE
]);
658 if (tb
[TCA_FQ_RATE_ENABLE
]) {
659 u32 enable
= nla_get_u32(tb
[TCA_FQ_RATE_ENABLE
]);
662 q
->rate_enable
= enable
;
668 err
= fq_resize(q
, fq_log
);
670 while (sch
->q
.qlen
> sch
->limit
) {
671 struct sk_buff
*skb
= fq_dequeue(sch
);
678 qdisc_tree_decrease_qlen(sch
, drop_count
);
680 sch_tree_unlock(sch
);
684 static void fq_destroy(struct Qdisc
*sch
)
686 struct fq_sched_data
*q
= qdisc_priv(sch
);
690 qdisc_watchdog_cancel(&q
->watchdog
);
693 static int fq_init(struct Qdisc
*sch
, struct nlattr
*opt
)
695 struct fq_sched_data
*q
= qdisc_priv(sch
);
699 q
->flow_plimit
= 100;
700 q
->quantum
= 2 * psched_mtu(qdisc_dev(sch
));
701 q
->initial_quantum
= 10 * psched_mtu(qdisc_dev(sch
));
702 q
->flow_max_rate
= ~0U;
704 q
->new_flows
.first
= NULL
;
705 q
->old_flows
.first
= NULL
;
706 q
->delayed
= RB_ROOT
;
708 q
->fq_trees_log
= ilog2(1024);
709 qdisc_watchdog_init(&q
->watchdog
, sch
);
712 err
= fq_change(sch
, opt
);
714 err
= fq_resize(q
, q
->fq_trees_log
);
719 static int fq_dump(struct Qdisc
*sch
, struct sk_buff
*skb
)
721 struct fq_sched_data
*q
= qdisc_priv(sch
);
724 opts
= nla_nest_start(skb
, TCA_OPTIONS
);
726 goto nla_put_failure
;
728 /* TCA_FQ_FLOW_DEFAULT_RATE is not used anymore */
730 if (nla_put_u32(skb
, TCA_FQ_PLIMIT
, sch
->limit
) ||
731 nla_put_u32(skb
, TCA_FQ_FLOW_PLIMIT
, q
->flow_plimit
) ||
732 nla_put_u32(skb
, TCA_FQ_QUANTUM
, q
->quantum
) ||
733 nla_put_u32(skb
, TCA_FQ_INITIAL_QUANTUM
, q
->initial_quantum
) ||
734 nla_put_u32(skb
, TCA_FQ_RATE_ENABLE
, q
->rate_enable
) ||
735 nla_put_u32(skb
, TCA_FQ_FLOW_MAX_RATE
, q
->flow_max_rate
) ||
736 nla_put_u32(skb
, TCA_FQ_BUCKETS_LOG
, q
->fq_trees_log
))
737 goto nla_put_failure
;
739 nla_nest_end(skb
, opts
);
746 static int fq_dump_stats(struct Qdisc
*sch
, struct gnet_dump
*d
)
748 struct fq_sched_data
*q
= qdisc_priv(sch
);
749 u64 now
= ktime_to_ns(ktime_get());
750 struct tc_fq_qd_stats st
= {
751 .gc_flows
= q
->stat_gc_flows
,
752 .highprio_packets
= q
->stat_internal_packets
,
753 .tcp_retrans
= q
->stat_tcp_retrans
,
754 .throttled
= q
->stat_throttled
,
755 .flows_plimit
= q
->stat_flows_plimit
,
756 .pkts_too_long
= q
->stat_pkts_too_long
,
757 .allocation_errors
= q
->stat_allocation_errors
,
759 .inactive_flows
= q
->inactive_flows
,
760 .throttled_flows
= q
->throttled_flows
,
761 .time_next_delayed_flow
= q
->time_next_delayed_flow
- now
,
764 return gnet_stats_copy_app(d
, &st
, sizeof(st
));
767 static struct Qdisc_ops fq_qdisc_ops __read_mostly
= {
769 .priv_size
= sizeof(struct fq_sched_data
),
771 .enqueue
= fq_enqueue
,
772 .dequeue
= fq_dequeue
,
773 .peek
= qdisc_peek_dequeued
,
776 .destroy
= fq_destroy
,
779 .dump_stats
= fq_dump_stats
,
780 .owner
= THIS_MODULE
,
783 static int __init
fq_module_init(void)
787 fq_flow_cachep
= kmem_cache_create("fq_flow_cache",
788 sizeof(struct fq_flow
),
793 ret
= register_qdisc(&fq_qdisc_ops
);
795 kmem_cache_destroy(fq_flow_cachep
);
799 static void __exit
fq_module_exit(void)
801 unregister_qdisc(&fq_qdisc_ops
);
802 kmem_cache_destroy(fq_flow_cachep
);
805 module_init(fq_module_init
)
806 module_exit(fq_module_exit
)
807 MODULE_AUTHOR("Eric Dumazet");
808 MODULE_LICENSE("GPL");