1 // SPDX-License-Identifier: GPL-2.0-only
3 * net/sched/sch_sfb.c Stochastic Fair Blue
5 * Copyright (c) 2008-2011 Juliusz Chroboczek <jch@pps.jussieu.fr>
6 * Copyright (c) 2011 Eric Dumazet <eric.dumazet@gmail.com>
8 * W. Feng, D. Kandlur, D. Saha, K. Shin. Blue:
9 * A New Class of Active Queue Management Algorithms.
10 * U. Michigan CSE-TR-387-99, April 1999.
12 * http://www.thefengs.com/wuchang/blue/CSE-TR-387-99.pdf
15 #include <linux/module.h>
16 #include <linux/types.h>
17 #include <linux/kernel.h>
18 #include <linux/errno.h>
19 #include <linux/skbuff.h>
20 #include <linux/random.h>
21 #include <linux/jhash.h>
23 #include <net/pkt_sched.h>
24 #include <net/pkt_cls.h>
25 #include <net/inet_ecn.h>
28 * SFB uses two B[l][n] : L x N arrays of bins (L levels, N bins per level)
29 * This implementation uses L = 8 and N = 16
30 * This permits us to split one 32bit hash (provided per packet by rxhash or
31 * external classifier) into 8 subhashes of 4 bits.
33 #define SFB_BUCKET_SHIFT 4
34 #define SFB_NUMBUCKETS (1 << SFB_BUCKET_SHIFT) /* N bins per Level */
35 #define SFB_BUCKET_MASK (SFB_NUMBUCKETS - 1)
36 #define SFB_LEVELS (32 / SFB_BUCKET_SHIFT) /* L */
38 /* SFB algo uses a virtual queue, named "bin" */
40 u16 qlen
; /* length of virtual queue */
41 u16 p_mark
; /* marking probability */
44 /* We use a double buffering right before hash change
45 * (Section 4.4 of SFB reference : moving hash functions)
48 u32 perturbation
; /* jhash perturbation */
49 struct sfb_bucket bins
[SFB_LEVELS
][SFB_NUMBUCKETS
];
52 struct sfb_sched_data
{
54 struct tcf_proto __rcu
*filter_list
;
55 struct tcf_block
*block
;
56 unsigned long rehash_interval
;
57 unsigned long warmup_time
; /* double buffering warmup time in jiffies */
59 u32 bin_size
; /* maximum queue length per bin */
60 u32 increment
; /* d1 */
61 u32 decrement
; /* d2 */
62 u32 limit
; /* HARD maximal queue length */
66 unsigned long rehash_time
;
67 unsigned long token_time
;
69 u8 slot
; /* current active bins (0 or 1) */
70 bool double_buffering
;
71 struct sfb_bins bins
[2];
78 u32 childdrop
; /* drops in child qdisc */
79 u32 marked
; /* ECN mark */
84 * Each queued skb might be hashed on one or two bins
85 * We store in skb_cb the two hash values.
86 * (A zero value means double buffering was not used)
92 static inline struct sfb_skb_cb
*sfb_skb_cb(const struct sk_buff
*skb
)
94 qdisc_cb_private_validate(skb
, sizeof(struct sfb_skb_cb
));
95 return (struct sfb_skb_cb
*)qdisc_skb_cb(skb
)->data
;
99 * If using 'internal' SFB flow classifier, hash comes from skb rxhash
100 * If using external classifier, hash comes from the classid.
102 static u32
sfb_hash(const struct sk_buff
*skb
, u32 slot
)
104 return sfb_skb_cb(skb
)->hashes
[slot
];
107 /* Probabilities are coded as Q0.16 fixed-point values,
108 * with 0xFFFF representing 65535/65536 (almost 1.0)
109 * Addition and subtraction are saturating in [0, 65535]
111 static u32
prob_plus(u32 p1
, u32 p2
)
115 return min_t(u32
, res
, SFB_MAX_PROB
);
118 static u32
prob_minus(u32 p1
, u32 p2
)
120 return p1
> p2
? p1
- p2
: 0;
123 static void increment_one_qlen(u32 sfbhash
, u32 slot
, struct sfb_sched_data
*q
)
126 struct sfb_bucket
*b
= &q
->bins
[slot
].bins
[0][0];
128 for (i
= 0; i
< SFB_LEVELS
; i
++) {
129 u32 hash
= sfbhash
& SFB_BUCKET_MASK
;
131 sfbhash
>>= SFB_BUCKET_SHIFT
;
132 if (b
[hash
].qlen
< 0xFFFF)
134 b
+= SFB_NUMBUCKETS
; /* next level */
138 static void increment_qlen(const struct sk_buff
*skb
, struct sfb_sched_data
*q
)
142 sfbhash
= sfb_hash(skb
, 0);
144 increment_one_qlen(sfbhash
, 0, q
);
146 sfbhash
= sfb_hash(skb
, 1);
148 increment_one_qlen(sfbhash
, 1, q
);
151 static void decrement_one_qlen(u32 sfbhash
, u32 slot
,
152 struct sfb_sched_data
*q
)
155 struct sfb_bucket
*b
= &q
->bins
[slot
].bins
[0][0];
157 for (i
= 0; i
< SFB_LEVELS
; i
++) {
158 u32 hash
= sfbhash
& SFB_BUCKET_MASK
;
160 sfbhash
>>= SFB_BUCKET_SHIFT
;
161 if (b
[hash
].qlen
> 0)
163 b
+= SFB_NUMBUCKETS
; /* next level */
167 static void decrement_qlen(const struct sk_buff
*skb
, struct sfb_sched_data
*q
)
171 sfbhash
= sfb_hash(skb
, 0);
173 decrement_one_qlen(sfbhash
, 0, q
);
175 sfbhash
= sfb_hash(skb
, 1);
177 decrement_one_qlen(sfbhash
, 1, q
);
180 static void decrement_prob(struct sfb_bucket
*b
, struct sfb_sched_data
*q
)
182 b
->p_mark
= prob_minus(b
->p_mark
, q
->decrement
);
185 static void increment_prob(struct sfb_bucket
*b
, struct sfb_sched_data
*q
)
187 b
->p_mark
= prob_plus(b
->p_mark
, q
->increment
);
190 static void sfb_zero_all_buckets(struct sfb_sched_data
*q
)
192 memset(&q
->bins
, 0, sizeof(q
->bins
));
196 * compute max qlen, max p_mark, and avg p_mark
198 static u32
sfb_compute_qlen(u32
*prob_r
, u32
*avgpm_r
, const struct sfb_sched_data
*q
)
201 u32 qlen
= 0, prob
= 0, totalpm
= 0;
202 const struct sfb_bucket
*b
= &q
->bins
[q
->slot
].bins
[0][0];
204 for (i
= 0; i
< SFB_LEVELS
* SFB_NUMBUCKETS
; i
++) {
207 totalpm
+= b
->p_mark
;
208 if (prob
< b
->p_mark
)
213 *avgpm_r
= totalpm
/ (SFB_LEVELS
* SFB_NUMBUCKETS
);
218 static void sfb_init_perturbation(u32 slot
, struct sfb_sched_data
*q
)
220 q
->bins
[slot
].perturbation
= prandom_u32();
223 static void sfb_swap_slot(struct sfb_sched_data
*q
)
225 sfb_init_perturbation(q
->slot
, q
);
227 q
->double_buffering
= false;
230 /* Non elastic flows are allowed to use part of the bandwidth, expressed
231 * in "penalty_rate" packets per second, with "penalty_burst" burst
233 static bool sfb_rate_limit(struct sk_buff
*skb
, struct sfb_sched_data
*q
)
235 if (q
->penalty_rate
== 0 || q
->penalty_burst
== 0)
238 if (q
->tokens_avail
< 1) {
239 unsigned long age
= min(10UL * HZ
, jiffies
- q
->token_time
);
241 q
->tokens_avail
= (age
* q
->penalty_rate
) / HZ
;
242 if (q
->tokens_avail
> q
->penalty_burst
)
243 q
->tokens_avail
= q
->penalty_burst
;
244 q
->token_time
= jiffies
;
245 if (q
->tokens_avail
< 1)
253 static bool sfb_classify(struct sk_buff
*skb
, struct tcf_proto
*fl
,
254 int *qerr
, u32
*salt
)
256 struct tcf_result res
;
259 result
= tcf_classify(skb
, fl
, &res
, false);
261 #ifdef CONFIG_NET_CLS_ACT
266 *qerr
= NET_XMIT_SUCCESS
| __NET_XMIT_STOLEN
;
272 *salt
= TC_H_MIN(res
.classid
);
278 static int sfb_enqueue(struct sk_buff
*skb
, struct Qdisc
*sch
,
279 struct sk_buff
**to_free
)
282 struct sfb_sched_data
*q
= qdisc_priv(sch
);
283 struct Qdisc
*child
= q
->qdisc
;
284 struct tcf_proto
*fl
;
290 int ret
= NET_XMIT_SUCCESS
| __NET_XMIT_BYPASS
;
292 if (unlikely(sch
->q
.qlen
>= q
->limit
)) {
293 qdisc_qstats_overlimit(sch
);
294 q
->stats
.queuedrop
++;
298 if (q
->rehash_interval
> 0) {
299 unsigned long limit
= q
->rehash_time
+ q
->rehash_interval
;
301 if (unlikely(time_after(jiffies
, limit
))) {
303 q
->rehash_time
= jiffies
;
304 } else if (unlikely(!q
->double_buffering
&& q
->warmup_time
> 0 &&
305 time_after(jiffies
, limit
- q
->warmup_time
))) {
306 q
->double_buffering
= true;
310 fl
= rcu_dereference_bh(q
->filter_list
);
314 /* If using external classifiers, get result and record it. */
315 if (!sfb_classify(skb
, fl
, &ret
, &salt
))
317 sfbhash
= jhash_1word(salt
, q
->bins
[slot
].perturbation
);
319 sfbhash
= skb_get_hash_perturb(skb
, q
->bins
[slot
].perturbation
);
325 sfb_skb_cb(skb
)->hashes
[slot
] = sfbhash
;
327 for (i
= 0; i
< SFB_LEVELS
; i
++) {
328 u32 hash
= sfbhash
& SFB_BUCKET_MASK
;
329 struct sfb_bucket
*b
= &q
->bins
[slot
].bins
[i
][hash
];
331 sfbhash
>>= SFB_BUCKET_SHIFT
;
333 decrement_prob(b
, q
);
334 else if (b
->qlen
>= q
->bin_size
)
335 increment_prob(b
, q
);
336 if (minqlen
> b
->qlen
)
338 if (p_min
> b
->p_mark
)
343 sfb_skb_cb(skb
)->hashes
[slot
] = 0;
345 if (unlikely(minqlen
>= q
->max
)) {
346 qdisc_qstats_overlimit(sch
);
347 q
->stats
.bucketdrop
++;
351 if (unlikely(p_min
>= SFB_MAX_PROB
)) {
353 if (q
->double_buffering
) {
354 sfbhash
= skb_get_hash_perturb(skb
,
355 q
->bins
[slot
].perturbation
);
358 sfb_skb_cb(skb
)->hashes
[slot
] = sfbhash
;
360 for (i
= 0; i
< SFB_LEVELS
; i
++) {
361 u32 hash
= sfbhash
& SFB_BUCKET_MASK
;
362 struct sfb_bucket
*b
= &q
->bins
[slot
].bins
[i
][hash
];
364 sfbhash
>>= SFB_BUCKET_SHIFT
;
366 decrement_prob(b
, q
);
367 else if (b
->qlen
>= q
->bin_size
)
368 increment_prob(b
, q
);
371 if (sfb_rate_limit(skb
, q
)) {
372 qdisc_qstats_overlimit(sch
);
373 q
->stats
.penaltydrop
++;
379 r
= prandom_u32() & SFB_MAX_PROB
;
381 if (unlikely(r
< p_min
)) {
382 if (unlikely(p_min
> SFB_MAX_PROB
/ 2)) {
383 /* If we're marking that many packets, then either
384 * this flow is unresponsive, or we're badly congested.
385 * In either case, we want to start dropping packets.
387 if (r
< (p_min
- SFB_MAX_PROB
/ 2) * 2) {
388 q
->stats
.earlydrop
++;
392 if (INET_ECN_set_ce(skb
)) {
395 q
->stats
.earlydrop
++;
401 ret
= qdisc_enqueue(skb
, child
, to_free
);
402 if (likely(ret
== NET_XMIT_SUCCESS
)) {
403 qdisc_qstats_backlog_inc(sch
, skb
);
405 increment_qlen(skb
, q
);
406 } else if (net_xmit_drop_count(ret
)) {
407 q
->stats
.childdrop
++;
408 qdisc_qstats_drop(sch
);
413 qdisc_drop(skb
, sch
, to_free
);
416 if (ret
& __NET_XMIT_BYPASS
)
417 qdisc_qstats_drop(sch
);
422 static struct sk_buff
*sfb_dequeue(struct Qdisc
*sch
)
424 struct sfb_sched_data
*q
= qdisc_priv(sch
);
425 struct Qdisc
*child
= q
->qdisc
;
428 skb
= child
->dequeue(q
->qdisc
);
431 qdisc_bstats_update(sch
, skb
);
432 qdisc_qstats_backlog_dec(sch
, skb
);
434 decrement_qlen(skb
, q
);
440 static struct sk_buff
*sfb_peek(struct Qdisc
*sch
)
442 struct sfb_sched_data
*q
= qdisc_priv(sch
);
443 struct Qdisc
*child
= q
->qdisc
;
445 return child
->ops
->peek(child
);
448 /* No sfb_drop -- impossible since the child doesn't return the dropped skb. */
450 static void sfb_reset(struct Qdisc
*sch
)
452 struct sfb_sched_data
*q
= qdisc_priv(sch
);
454 qdisc_reset(q
->qdisc
);
455 sch
->qstats
.backlog
= 0;
458 q
->double_buffering
= false;
459 sfb_zero_all_buckets(q
);
460 sfb_init_perturbation(0, q
);
463 static void sfb_destroy(struct Qdisc
*sch
)
465 struct sfb_sched_data
*q
= qdisc_priv(sch
);
467 tcf_block_put(q
->block
);
471 static const struct nla_policy sfb_policy
[TCA_SFB_MAX
+ 1] = {
472 [TCA_SFB_PARMS
] = { .len
= sizeof(struct tc_sfb_qopt
) },
475 static const struct tc_sfb_qopt sfb_default_ops
= {
476 .rehash_interval
= 600 * MSEC_PER_SEC
,
477 .warmup_time
= 60 * MSEC_PER_SEC
,
481 .increment
= (SFB_MAX_PROB
+ 500) / 1000, /* 0.1 % */
482 .decrement
= (SFB_MAX_PROB
+ 3000) / 6000,
487 static int sfb_change(struct Qdisc
*sch
, struct nlattr
*opt
,
488 struct netlink_ext_ack
*extack
)
490 struct sfb_sched_data
*q
= qdisc_priv(sch
);
492 struct nlattr
*tb
[TCA_SFB_MAX
+ 1];
493 const struct tc_sfb_qopt
*ctl
= &sfb_default_ops
;
498 err
= nla_parse_nested_deprecated(tb
, TCA_SFB_MAX
, opt
,
503 if (tb
[TCA_SFB_PARMS
] == NULL
)
506 ctl
= nla_data(tb
[TCA_SFB_PARMS
]);
511 limit
= qdisc_dev(sch
)->tx_queue_len
;
513 child
= fifo_create_dflt(sch
, &pfifo_qdisc_ops
, limit
, extack
);
515 return PTR_ERR(child
);
517 if (child
!= &noop_qdisc
)
518 qdisc_hash_add(child
, true);
521 qdisc_tree_flush_backlog(q
->qdisc
);
525 q
->rehash_interval
= msecs_to_jiffies(ctl
->rehash_interval
);
526 q
->warmup_time
= msecs_to_jiffies(ctl
->warmup_time
);
527 q
->rehash_time
= jiffies
;
529 q
->increment
= ctl
->increment
;
530 q
->decrement
= ctl
->decrement
;
532 q
->bin_size
= ctl
->bin_size
;
533 q
->penalty_rate
= ctl
->penalty_rate
;
534 q
->penalty_burst
= ctl
->penalty_burst
;
535 q
->tokens_avail
= ctl
->penalty_burst
;
536 q
->token_time
= jiffies
;
539 q
->double_buffering
= false;
540 sfb_zero_all_buckets(q
);
541 sfb_init_perturbation(0, q
);
542 sfb_init_perturbation(1, q
);
544 sch_tree_unlock(sch
);
549 static int sfb_init(struct Qdisc
*sch
, struct nlattr
*opt
,
550 struct netlink_ext_ack
*extack
)
552 struct sfb_sched_data
*q
= qdisc_priv(sch
);
555 err
= tcf_block_get(&q
->block
, &q
->filter_list
, sch
, extack
);
559 q
->qdisc
= &noop_qdisc
;
560 return sfb_change(sch
, opt
, extack
);
563 static int sfb_dump(struct Qdisc
*sch
, struct sk_buff
*skb
)
565 struct sfb_sched_data
*q
= qdisc_priv(sch
);
567 struct tc_sfb_qopt opt
= {
568 .rehash_interval
= jiffies_to_msecs(q
->rehash_interval
),
569 .warmup_time
= jiffies_to_msecs(q
->warmup_time
),
572 .bin_size
= q
->bin_size
,
573 .increment
= q
->increment
,
574 .decrement
= q
->decrement
,
575 .penalty_rate
= q
->penalty_rate
,
576 .penalty_burst
= q
->penalty_burst
,
579 sch
->qstats
.backlog
= q
->qdisc
->qstats
.backlog
;
580 opts
= nla_nest_start_noflag(skb
, TCA_OPTIONS
);
582 goto nla_put_failure
;
583 if (nla_put(skb
, TCA_SFB_PARMS
, sizeof(opt
), &opt
))
584 goto nla_put_failure
;
585 return nla_nest_end(skb
, opts
);
588 nla_nest_cancel(skb
, opts
);
592 static int sfb_dump_stats(struct Qdisc
*sch
, struct gnet_dump
*d
)
594 struct sfb_sched_data
*q
= qdisc_priv(sch
);
595 struct tc_sfb_xstats st
= {
596 .earlydrop
= q
->stats
.earlydrop
,
597 .penaltydrop
= q
->stats
.penaltydrop
,
598 .bucketdrop
= q
->stats
.bucketdrop
,
599 .queuedrop
= q
->stats
.queuedrop
,
600 .childdrop
= q
->stats
.childdrop
,
601 .marked
= q
->stats
.marked
,
604 st
.maxqlen
= sfb_compute_qlen(&st
.maxprob
, &st
.avgprob
, q
);
606 return gnet_stats_copy_app(d
, &st
, sizeof(st
));
609 static int sfb_dump_class(struct Qdisc
*sch
, unsigned long cl
,
610 struct sk_buff
*skb
, struct tcmsg
*tcm
)
615 static int sfb_graft(struct Qdisc
*sch
, unsigned long arg
, struct Qdisc
*new,
616 struct Qdisc
**old
, struct netlink_ext_ack
*extack
)
618 struct sfb_sched_data
*q
= qdisc_priv(sch
);
623 *old
= qdisc_replace(sch
, new, &q
->qdisc
);
627 static struct Qdisc
*sfb_leaf(struct Qdisc
*sch
, unsigned long arg
)
629 struct sfb_sched_data
*q
= qdisc_priv(sch
);
634 static unsigned long sfb_find(struct Qdisc
*sch
, u32 classid
)
639 static void sfb_unbind(struct Qdisc
*sch
, unsigned long arg
)
643 static int sfb_change_class(struct Qdisc
*sch
, u32 classid
, u32 parentid
,
644 struct nlattr
**tca
, unsigned long *arg
,
645 struct netlink_ext_ack
*extack
)
650 static int sfb_delete(struct Qdisc
*sch
, unsigned long cl
)
655 static void sfb_walk(struct Qdisc
*sch
, struct qdisc_walker
*walker
)
658 if (walker
->count
>= walker
->skip
)
659 if (walker
->fn(sch
, 1, walker
) < 0) {
667 static struct tcf_block
*sfb_tcf_block(struct Qdisc
*sch
, unsigned long cl
,
668 struct netlink_ext_ack
*extack
)
670 struct sfb_sched_data
*q
= qdisc_priv(sch
);
677 static unsigned long sfb_bind(struct Qdisc
*sch
, unsigned long parent
,
684 static const struct Qdisc_class_ops sfb_class_ops
= {
688 .change
= sfb_change_class
,
689 .delete = sfb_delete
,
691 .tcf_block
= sfb_tcf_block
,
692 .bind_tcf
= sfb_bind
,
693 .unbind_tcf
= sfb_unbind
,
694 .dump
= sfb_dump_class
,
697 static struct Qdisc_ops sfb_qdisc_ops __read_mostly
= {
699 .priv_size
= sizeof(struct sfb_sched_data
),
700 .cl_ops
= &sfb_class_ops
,
701 .enqueue
= sfb_enqueue
,
702 .dequeue
= sfb_dequeue
,
706 .destroy
= sfb_destroy
,
707 .change
= sfb_change
,
709 .dump_stats
= sfb_dump_stats
,
710 .owner
= THIS_MODULE
,
713 static int __init
sfb_module_init(void)
715 return register_qdisc(&sfb_qdisc_ops
);
718 static void __exit
sfb_module_exit(void)
720 unregister_qdisc(&sfb_qdisc_ops
);
723 module_init(sfb_module_init
)
724 module_exit(sfb_module_exit
)
726 MODULE_DESCRIPTION("Stochastic Fair Blue queue discipline");
727 MODULE_AUTHOR("Juliusz Chroboczek");
728 MODULE_AUTHOR("Eric Dumazet");
729 MODULE_LICENSE("GPL");