Commit | Line | Data |
---|---|---|
d2912cb1 | 1 | // SPDX-License-Identifier: GPL-2.0-only |
e13e02a3 ED |
2 | /* |
3 | * net/sched/sch_sfb.c Stochastic Fair Blue | |
4 | * | |
5 | * Copyright (c) 2008-2011 Juliusz Chroboczek <jch@pps.jussieu.fr> | |
6 | * Copyright (c) 2011 Eric Dumazet <eric.dumazet@gmail.com> | |
7 | * | |
e13e02a3 ED |
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. | |
11 | * | |
12 | * http://www.thefengs.com/wuchang/blue/CSE-TR-387-99.pdf | |
e13e02a3 ED |
13 | */ |
14 | ||
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> | |
55667441 | 21 | #include <linux/siphash.h> |
e13e02a3 ED |
22 | #include <net/ip.h> |
23 | #include <net/pkt_sched.h> | |
cf1facda | 24 | #include <net/pkt_cls.h> |
e13e02a3 ED |
25 | #include <net/inet_ecn.h> |
26 | ||
27 | /* | |
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. | |
32 | */ | |
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 */ | |
37 | ||
38 | /* SFB algo uses a virtual queue, named "bin" */ | |
39 | struct sfb_bucket { | |
40 | u16 qlen; /* length of virtual queue */ | |
41 | u16 p_mark; /* marking probability */ | |
42 | }; | |
43 | ||
44 | /* We use a double buffering right before hash change | |
45 | * (Section 4.4 of SFB reference : moving hash functions) | |
46 | */ | |
47 | struct sfb_bins { | |
55667441 | 48 | siphash_key_t perturbation; /* siphash key */ |
e13e02a3 ED |
49 | struct sfb_bucket bins[SFB_LEVELS][SFB_NUMBUCKETS]; |
50 | }; | |
51 | ||
52 | struct sfb_sched_data { | |
53 | struct Qdisc *qdisc; | |
25d8c0d5 | 54 | struct tcf_proto __rcu *filter_list; |
6529eaba | 55 | struct tcf_block *block; |
e13e02a3 ED |
56 | unsigned long rehash_interval; |
57 | unsigned long warmup_time; /* double buffering warmup time in jiffies */ | |
58 | u32 max; | |
59 | u32 bin_size; /* maximum queue length per bin */ | |
60 | u32 increment; /* d1 */ | |
61 | u32 decrement; /* d2 */ | |
62 | u32 limit; /* HARD maximal queue length */ | |
63 | u32 penalty_rate; | |
64 | u32 penalty_burst; | |
65 | u32 tokens_avail; | |
66 | unsigned long rehash_time; | |
67 | unsigned long token_time; | |
68 | ||
69 | u8 slot; /* current active bins (0 or 1) */ | |
70 | bool double_buffering; | |
71 | struct sfb_bins bins[2]; | |
72 | ||
73 | struct { | |
74 | u32 earlydrop; | |
75 | u32 penaltydrop; | |
76 | u32 bucketdrop; | |
77 | u32 queuedrop; | |
78 | u32 childdrop; /* drops in child qdisc */ | |
79 | u32 marked; /* ECN mark */ | |
80 | } stats; | |
81 | }; | |
82 | ||
83 | /* | |
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) | |
87 | */ | |
88 | struct sfb_skb_cb { | |
89 | u32 hashes[2]; | |
90 | }; | |
91 | ||
92 | static inline struct sfb_skb_cb *sfb_skb_cb(const struct sk_buff *skb) | |
93 | { | |
16bda13d | 94 | qdisc_cb_private_validate(skb, sizeof(struct sfb_skb_cb)); |
e13e02a3 ED |
95 | return (struct sfb_skb_cb *)qdisc_skb_cb(skb)->data; |
96 | } | |
97 | ||
98 | /* | |
99 | * If using 'internal' SFB flow classifier, hash comes from skb rxhash | |
100 | * If using external classifier, hash comes from the classid. | |
101 | */ | |
102 | static u32 sfb_hash(const struct sk_buff *skb, u32 slot) | |
103 | { | |
104 | return sfb_skb_cb(skb)->hashes[slot]; | |
105 | } | |
106 | ||
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] | |
110 | */ | |
111 | static u32 prob_plus(u32 p1, u32 p2) | |
112 | { | |
113 | u32 res = p1 + p2; | |
114 | ||
115 | return min_t(u32, res, SFB_MAX_PROB); | |
116 | } | |
117 | ||
118 | static u32 prob_minus(u32 p1, u32 p2) | |
119 | { | |
120 | return p1 > p2 ? p1 - p2 : 0; | |
121 | } | |
122 | ||
123 | static void increment_one_qlen(u32 sfbhash, u32 slot, struct sfb_sched_data *q) | |
124 | { | |
125 | int i; | |
126 | struct sfb_bucket *b = &q->bins[slot].bins[0][0]; | |
127 | ||
128 | for (i = 0; i < SFB_LEVELS; i++) { | |
129 | u32 hash = sfbhash & SFB_BUCKET_MASK; | |
130 | ||
131 | sfbhash >>= SFB_BUCKET_SHIFT; | |
132 | if (b[hash].qlen < 0xFFFF) | |
133 | b[hash].qlen++; | |
134 | b += SFB_NUMBUCKETS; /* next level */ | |
135 | } | |
136 | } | |
137 | ||
9efd2329 | 138 | static void increment_qlen(const struct sfb_skb_cb *cb, struct sfb_sched_data *q) |
e13e02a3 ED |
139 | { |
140 | u32 sfbhash; | |
141 | ||
9efd2329 | 142 | sfbhash = cb->hashes[0]; |
e13e02a3 ED |
143 | if (sfbhash) |
144 | increment_one_qlen(sfbhash, 0, q); | |
145 | ||
9efd2329 | 146 | sfbhash = cb->hashes[1]; |
e13e02a3 ED |
147 | if (sfbhash) |
148 | increment_one_qlen(sfbhash, 1, q); | |
149 | } | |
150 | ||
151 | static void decrement_one_qlen(u32 sfbhash, u32 slot, | |
152 | struct sfb_sched_data *q) | |
153 | { | |
154 | int i; | |
155 | struct sfb_bucket *b = &q->bins[slot].bins[0][0]; | |
156 | ||
157 | for (i = 0; i < SFB_LEVELS; i++) { | |
158 | u32 hash = sfbhash & SFB_BUCKET_MASK; | |
159 | ||
160 | sfbhash >>= SFB_BUCKET_SHIFT; | |
161 | if (b[hash].qlen > 0) | |
162 | b[hash].qlen--; | |
163 | b += SFB_NUMBUCKETS; /* next level */ | |
164 | } | |
165 | } | |
166 | ||
167 | static void decrement_qlen(const struct sk_buff *skb, struct sfb_sched_data *q) | |
168 | { | |
169 | u32 sfbhash; | |
170 | ||
171 | sfbhash = sfb_hash(skb, 0); | |
172 | if (sfbhash) | |
173 | decrement_one_qlen(sfbhash, 0, q); | |
174 | ||
175 | sfbhash = sfb_hash(skb, 1); | |
176 | if (sfbhash) | |
177 | decrement_one_qlen(sfbhash, 1, q); | |
178 | } | |
179 | ||
180 | static void decrement_prob(struct sfb_bucket *b, struct sfb_sched_data *q) | |
181 | { | |
182 | b->p_mark = prob_minus(b->p_mark, q->decrement); | |
183 | } | |
184 | ||
185 | static void increment_prob(struct sfb_bucket *b, struct sfb_sched_data *q) | |
186 | { | |
187 | b->p_mark = prob_plus(b->p_mark, q->increment); | |
188 | } | |
189 | ||
190 | static void sfb_zero_all_buckets(struct sfb_sched_data *q) | |
191 | { | |
192 | memset(&q->bins, 0, sizeof(q->bins)); | |
193 | } | |
194 | ||
195 | /* | |
196 | * compute max qlen, max p_mark, and avg p_mark | |
197 | */ | |
198 | static u32 sfb_compute_qlen(u32 *prob_r, u32 *avgpm_r, const struct sfb_sched_data *q) | |
199 | { | |
200 | int i; | |
201 | u32 qlen = 0, prob = 0, totalpm = 0; | |
202 | const struct sfb_bucket *b = &q->bins[q->slot].bins[0][0]; | |
203 | ||
204 | for (i = 0; i < SFB_LEVELS * SFB_NUMBUCKETS; i++) { | |
205 | if (qlen < b->qlen) | |
206 | qlen = b->qlen; | |
207 | totalpm += b->p_mark; | |
208 | if (prob < b->p_mark) | |
209 | prob = b->p_mark; | |
210 | b++; | |
211 | } | |
212 | *prob_r = prob; | |
213 | *avgpm_r = totalpm / (SFB_LEVELS * SFB_NUMBUCKETS); | |
214 | return qlen; | |
215 | } | |
216 | ||
217 | ||
218 | static void sfb_init_perturbation(u32 slot, struct sfb_sched_data *q) | |
219 | { | |
55667441 ED |
220 | get_random_bytes(&q->bins[slot].perturbation, |
221 | sizeof(q->bins[slot].perturbation)); | |
e13e02a3 ED |
222 | } |
223 | ||
224 | static void sfb_swap_slot(struct sfb_sched_data *q) | |
225 | { | |
226 | sfb_init_perturbation(q->slot, q); | |
227 | q->slot ^= 1; | |
228 | q->double_buffering = false; | |
229 | } | |
230 | ||
231 | /* Non elastic flows are allowed to use part of the bandwidth, expressed | |
232 | * in "penalty_rate" packets per second, with "penalty_burst" burst | |
233 | */ | |
234 | static bool sfb_rate_limit(struct sk_buff *skb, struct sfb_sched_data *q) | |
235 | { | |
236 | if (q->penalty_rate == 0 || q->penalty_burst == 0) | |
237 | return true; | |
238 | ||
239 | if (q->tokens_avail < 1) { | |
240 | unsigned long age = min(10UL * HZ, jiffies - q->token_time); | |
241 | ||
242 | q->tokens_avail = (age * q->penalty_rate) / HZ; | |
243 | if (q->tokens_avail > q->penalty_burst) | |
244 | q->tokens_avail = q->penalty_burst; | |
245 | q->token_time = jiffies; | |
246 | if (q->tokens_avail < 1) | |
247 | return true; | |
248 | } | |
249 | ||
250 | q->tokens_avail--; | |
251 | return false; | |
252 | } | |
253 | ||
25d8c0d5 | 254 | static bool sfb_classify(struct sk_buff *skb, struct tcf_proto *fl, |
e13e02a3 ED |
255 | int *qerr, u32 *salt) |
256 | { | |
257 | struct tcf_result res; | |
258 | int result; | |
259 | ||
3aa26055 | 260 | result = tcf_classify(skb, NULL, fl, &res, false); |
e13e02a3 ED |
261 | if (result >= 0) { |
262 | #ifdef CONFIG_NET_CLS_ACT | |
263 | switch (result) { | |
264 | case TC_ACT_STOLEN: | |
265 | case TC_ACT_QUEUED: | |
e25ea21f | 266 | case TC_ACT_TRAP: |
e13e02a3 | 267 | *qerr = NET_XMIT_SUCCESS | __NET_XMIT_STOLEN; |
964201de | 268 | fallthrough; |
e13e02a3 ED |
269 | case TC_ACT_SHOT: |
270 | return false; | |
271 | } | |
272 | #endif | |
273 | *salt = TC_H_MIN(res.classid); | |
274 | return true; | |
275 | } | |
276 | return false; | |
277 | } | |
278 | ||
ac5c66f2 | 279 | static int sfb_enqueue(struct sk_buff *skb, struct Qdisc *sch, |
520ac30f | 280 | struct sk_buff **to_free) |
e13e02a3 ED |
281 | { |
282 | ||
283 | struct sfb_sched_data *q = qdisc_priv(sch); | |
2f09707d | 284 | unsigned int len = qdisc_pkt_len(skb); |
e13e02a3 | 285 | struct Qdisc *child = q->qdisc; |
25d8c0d5 | 286 | struct tcf_proto *fl; |
9efd2329 | 287 | struct sfb_skb_cb cb; |
e13e02a3 ED |
288 | int i; |
289 | u32 p_min = ~0; | |
290 | u32 minqlen = ~0; | |
63c0ad4d TH |
291 | u32 r, sfbhash; |
292 | u32 slot = q->slot; | |
e13e02a3 ED |
293 | int ret = NET_XMIT_SUCCESS | __NET_XMIT_BYPASS; |
294 | ||
363437f4 | 295 | if (unlikely(sch->q.qlen >= q->limit)) { |
25331d6c | 296 | qdisc_qstats_overlimit(sch); |
363437f4 ED |
297 | q->stats.queuedrop++; |
298 | goto drop; | |
299 | } | |
300 | ||
e13e02a3 ED |
301 | if (q->rehash_interval > 0) { |
302 | unsigned long limit = q->rehash_time + q->rehash_interval; | |
303 | ||
304 | if (unlikely(time_after(jiffies, limit))) { | |
305 | sfb_swap_slot(q); | |
306 | q->rehash_time = jiffies; | |
307 | } else if (unlikely(!q->double_buffering && q->warmup_time > 0 && | |
308 | time_after(jiffies, limit - q->warmup_time))) { | |
309 | q->double_buffering = true; | |
310 | } | |
311 | } | |
312 | ||
25d8c0d5 JF |
313 | fl = rcu_dereference_bh(q->filter_list); |
314 | if (fl) { | |
63c0ad4d TH |
315 | u32 salt; |
316 | ||
e13e02a3 | 317 | /* If using external classifiers, get result and record it. */ |
25d8c0d5 | 318 | if (!sfb_classify(skb, fl, &ret, &salt)) |
e13e02a3 | 319 | goto other_drop; |
55667441 | 320 | sfbhash = siphash_1u32(salt, &q->bins[slot].perturbation); |
e13e02a3 | 321 | } else { |
55667441 | 322 | sfbhash = skb_get_hash_perturb(skb, &q->bins[slot].perturbation); |
e13e02a3 ED |
323 | } |
324 | ||
e13e02a3 | 325 | |
e13e02a3 ED |
326 | if (!sfbhash) |
327 | sfbhash = 1; | |
328 | sfb_skb_cb(skb)->hashes[slot] = sfbhash; | |
329 | ||
330 | for (i = 0; i < SFB_LEVELS; i++) { | |
331 | u32 hash = sfbhash & SFB_BUCKET_MASK; | |
332 | struct sfb_bucket *b = &q->bins[slot].bins[i][hash]; | |
333 | ||
334 | sfbhash >>= SFB_BUCKET_SHIFT; | |
335 | if (b->qlen == 0) | |
336 | decrement_prob(b, q); | |
337 | else if (b->qlen >= q->bin_size) | |
338 | increment_prob(b, q); | |
339 | if (minqlen > b->qlen) | |
340 | minqlen = b->qlen; | |
341 | if (p_min > b->p_mark) | |
342 | p_min = b->p_mark; | |
343 | } | |
344 | ||
345 | slot ^= 1; | |
346 | sfb_skb_cb(skb)->hashes[slot] = 0; | |
347 | ||
363437f4 | 348 | if (unlikely(minqlen >= q->max)) { |
25331d6c | 349 | qdisc_qstats_overlimit(sch); |
363437f4 | 350 | q->stats.bucketdrop++; |
e13e02a3 ED |
351 | goto drop; |
352 | } | |
353 | ||
354 | if (unlikely(p_min >= SFB_MAX_PROB)) { | |
355 | /* Inelastic flow */ | |
356 | if (q->double_buffering) { | |
63c0ad4d | 357 | sfbhash = skb_get_hash_perturb(skb, |
55667441 | 358 | &q->bins[slot].perturbation); |
e13e02a3 ED |
359 | if (!sfbhash) |
360 | sfbhash = 1; | |
361 | sfb_skb_cb(skb)->hashes[slot] = sfbhash; | |
362 | ||
363 | for (i = 0; i < SFB_LEVELS; i++) { | |
364 | u32 hash = sfbhash & SFB_BUCKET_MASK; | |
365 | struct sfb_bucket *b = &q->bins[slot].bins[i][hash]; | |
366 | ||
367 | sfbhash >>= SFB_BUCKET_SHIFT; | |
368 | if (b->qlen == 0) | |
369 | decrement_prob(b, q); | |
370 | else if (b->qlen >= q->bin_size) | |
371 | increment_prob(b, q); | |
372 | } | |
373 | } | |
374 | if (sfb_rate_limit(skb, q)) { | |
25331d6c | 375 | qdisc_qstats_overlimit(sch); |
e13e02a3 ED |
376 | q->stats.penaltydrop++; |
377 | goto drop; | |
378 | } | |
379 | goto enqueue; | |
380 | } | |
381 | ||
f743f16c | 382 | r = get_random_u16() & SFB_MAX_PROB; |
e13e02a3 ED |
383 | |
384 | if (unlikely(r < p_min)) { | |
385 | if (unlikely(p_min > SFB_MAX_PROB / 2)) { | |
386 | /* If we're marking that many packets, then either | |
387 | * this flow is unresponsive, or we're badly congested. | |
388 | * In either case, we want to start dropping packets. | |
389 | */ | |
390 | if (r < (p_min - SFB_MAX_PROB / 2) * 2) { | |
391 | q->stats.earlydrop++; | |
392 | goto drop; | |
393 | } | |
394 | } | |
395 | if (INET_ECN_set_ce(skb)) { | |
396 | q->stats.marked++; | |
397 | } else { | |
398 | q->stats.earlydrop++; | |
399 | goto drop; | |
400 | } | |
401 | } | |
402 | ||
403 | enqueue: | |
9efd2329 | 404 | memcpy(&cb, sfb_skb_cb(skb), sizeof(cb)); |
ac5c66f2 | 405 | ret = qdisc_enqueue(skb, child, to_free); |
e13e02a3 | 406 | if (likely(ret == NET_XMIT_SUCCESS)) { |
2f09707d | 407 | sch->qstats.backlog += len; |
e13e02a3 | 408 | sch->q.qlen++; |
9efd2329 | 409 | increment_qlen(&cb, q); |
e13e02a3 ED |
410 | } else if (net_xmit_drop_count(ret)) { |
411 | q->stats.childdrop++; | |
25331d6c | 412 | qdisc_qstats_drop(sch); |
e13e02a3 ED |
413 | } |
414 | return ret; | |
415 | ||
416 | drop: | |
520ac30f | 417 | qdisc_drop(skb, sch, to_free); |
e13e02a3 ED |
418 | return NET_XMIT_CN; |
419 | other_drop: | |
420 | if (ret & __NET_XMIT_BYPASS) | |
25331d6c | 421 | qdisc_qstats_drop(sch); |
e13e02a3 ED |
422 | kfree_skb(skb); |
423 | return ret; | |
424 | } | |
425 | ||
426 | static struct sk_buff *sfb_dequeue(struct Qdisc *sch) | |
427 | { | |
428 | struct sfb_sched_data *q = qdisc_priv(sch); | |
429 | struct Qdisc *child = q->qdisc; | |
430 | struct sk_buff *skb; | |
431 | ||
432 | skb = child->dequeue(q->qdisc); | |
433 | ||
434 | if (skb) { | |
435 | qdisc_bstats_update(sch, skb); | |
3d4357fb | 436 | qdisc_qstats_backlog_dec(sch, skb); |
e13e02a3 ED |
437 | sch->q.qlen--; |
438 | decrement_qlen(skb, q); | |
439 | } | |
440 | ||
441 | return skb; | |
442 | } | |
443 | ||
444 | static struct sk_buff *sfb_peek(struct Qdisc *sch) | |
445 | { | |
446 | struct sfb_sched_data *q = qdisc_priv(sch); | |
447 | struct Qdisc *child = q->qdisc; | |
448 | ||
449 | return child->ops->peek(child); | |
450 | } | |
451 | ||
452 | /* No sfb_drop -- impossible since the child doesn't return the dropped skb. */ | |
453 | ||
454 | static void sfb_reset(struct Qdisc *sch) | |
455 | { | |
456 | struct sfb_sched_data *q = qdisc_priv(sch); | |
457 | ||
2a3fc782 ZS |
458 | if (likely(q->qdisc)) |
459 | qdisc_reset(q->qdisc); | |
e13e02a3 ED |
460 | q->slot = 0; |
461 | q->double_buffering = false; | |
462 | sfb_zero_all_buckets(q); | |
463 | sfb_init_perturbation(0, q); | |
464 | } | |
465 | ||
466 | static void sfb_destroy(struct Qdisc *sch) | |
467 | { | |
468 | struct sfb_sched_data *q = qdisc_priv(sch); | |
469 | ||
6529eaba | 470 | tcf_block_put(q->block); |
86bd446b | 471 | qdisc_put(q->qdisc); |
e13e02a3 ED |
472 | } |
473 | ||
474 | static const struct nla_policy sfb_policy[TCA_SFB_MAX + 1] = { | |
475 | [TCA_SFB_PARMS] = { .len = sizeof(struct tc_sfb_qopt) }, | |
476 | }; | |
477 | ||
478 | static const struct tc_sfb_qopt sfb_default_ops = { | |
479 | .rehash_interval = 600 * MSEC_PER_SEC, | |
480 | .warmup_time = 60 * MSEC_PER_SEC, | |
481 | .limit = 0, | |
482 | .max = 25, | |
483 | .bin_size = 20, | |
484 | .increment = (SFB_MAX_PROB + 500) / 1000, /* 0.1 % */ | |
485 | .decrement = (SFB_MAX_PROB + 3000) / 6000, | |
486 | .penalty_rate = 10, | |
487 | .penalty_burst = 20, | |
488 | }; | |
489 | ||
2030721c AA |
490 | static int sfb_change(struct Qdisc *sch, struct nlattr *opt, |
491 | struct netlink_ext_ack *extack) | |
e13e02a3 ED |
492 | { |
493 | struct sfb_sched_data *q = qdisc_priv(sch); | |
e3ae1f96 | 494 | struct Qdisc *child, *old; |
e13e02a3 ED |
495 | struct nlattr *tb[TCA_SFB_MAX + 1]; |
496 | const struct tc_sfb_qopt *ctl = &sfb_default_ops; | |
497 | u32 limit; | |
498 | int err; | |
499 | ||
500 | if (opt) { | |
8cb08174 JB |
501 | err = nla_parse_nested_deprecated(tb, TCA_SFB_MAX, opt, |
502 | sfb_policy, NULL); | |
e13e02a3 ED |
503 | if (err < 0) |
504 | return -EINVAL; | |
505 | ||
506 | if (tb[TCA_SFB_PARMS] == NULL) | |
507 | return -EINVAL; | |
508 | ||
509 | ctl = nla_data(tb[TCA_SFB_PARMS]); | |
510 | } | |
511 | ||
512 | limit = ctl->limit; | |
513 | if (limit == 0) | |
348e3435 | 514 | limit = qdisc_dev(sch)->tx_queue_len; |
e13e02a3 | 515 | |
a38a9882 | 516 | child = fifo_create_dflt(sch, &pfifo_qdisc_ops, limit, extack); |
e13e02a3 ED |
517 | if (IS_ERR(child)) |
518 | return PTR_ERR(child); | |
519 | ||
49b49971 JK |
520 | if (child != &noop_qdisc) |
521 | qdisc_hash_add(child, true); | |
e13e02a3 ED |
522 | sch_tree_lock(sch); |
523 | ||
e3ae1f96 VB |
524 | qdisc_purge_queue(q->qdisc); |
525 | old = q->qdisc; | |
e13e02a3 ED |
526 | q->qdisc = child; |
527 | ||
528 | q->rehash_interval = msecs_to_jiffies(ctl->rehash_interval); | |
529 | q->warmup_time = msecs_to_jiffies(ctl->warmup_time); | |
530 | q->rehash_time = jiffies; | |
531 | q->limit = limit; | |
532 | q->increment = ctl->increment; | |
533 | q->decrement = ctl->decrement; | |
534 | q->max = ctl->max; | |
535 | q->bin_size = ctl->bin_size; | |
536 | q->penalty_rate = ctl->penalty_rate; | |
537 | q->penalty_burst = ctl->penalty_burst; | |
538 | q->tokens_avail = ctl->penalty_burst; | |
539 | q->token_time = jiffies; | |
540 | ||
541 | q->slot = 0; | |
542 | q->double_buffering = false; | |
543 | sfb_zero_all_buckets(q); | |
544 | sfb_init_perturbation(0, q); | |
545 | sfb_init_perturbation(1, q); | |
546 | ||
547 | sch_tree_unlock(sch); | |
e3ae1f96 | 548 | qdisc_put(old); |
e13e02a3 ED |
549 | |
550 | return 0; | |
551 | } | |
552 | ||
e63d7dfd AA |
553 | static int sfb_init(struct Qdisc *sch, struct nlattr *opt, |
554 | struct netlink_ext_ack *extack) | |
e13e02a3 ED |
555 | { |
556 | struct sfb_sched_data *q = qdisc_priv(sch); | |
6529eaba JP |
557 | int err; |
558 | ||
8d1a77f9 | 559 | err = tcf_block_get(&q->block, &q->filter_list, sch, extack); |
6529eaba JP |
560 | if (err) |
561 | return err; | |
e13e02a3 ED |
562 | |
563 | q->qdisc = &noop_qdisc; | |
2030721c | 564 | return sfb_change(sch, opt, extack); |
e13e02a3 ED |
565 | } |
566 | ||
567 | static int sfb_dump(struct Qdisc *sch, struct sk_buff *skb) | |
568 | { | |
569 | struct sfb_sched_data *q = qdisc_priv(sch); | |
570 | struct nlattr *opts; | |
571 | struct tc_sfb_qopt opt = { | |
572 | .rehash_interval = jiffies_to_msecs(q->rehash_interval), | |
573 | .warmup_time = jiffies_to_msecs(q->warmup_time), | |
574 | .limit = q->limit, | |
575 | .max = q->max, | |
576 | .bin_size = q->bin_size, | |
577 | .increment = q->increment, | |
578 | .decrement = q->decrement, | |
579 | .penalty_rate = q->penalty_rate, | |
580 | .penalty_burst = q->penalty_burst, | |
581 | }; | |
582 | ||
583 | sch->qstats.backlog = q->qdisc->qstats.backlog; | |
ae0be8de | 584 | opts = nla_nest_start_noflag(skb, TCA_OPTIONS); |
7ac2908e AC |
585 | if (opts == NULL) |
586 | goto nla_put_failure; | |
1b34ec43 DM |
587 | if (nla_put(skb, TCA_SFB_PARMS, sizeof(opt), &opt)) |
588 | goto nla_put_failure; | |
e13e02a3 ED |
589 | return nla_nest_end(skb, opts); |
590 | ||
591 | nla_put_failure: | |
592 | nla_nest_cancel(skb, opts); | |
593 | return -EMSGSIZE; | |
594 | } | |
595 | ||
596 | static int sfb_dump_stats(struct Qdisc *sch, struct gnet_dump *d) | |
597 | { | |
598 | struct sfb_sched_data *q = qdisc_priv(sch); | |
599 | struct tc_sfb_xstats st = { | |
600 | .earlydrop = q->stats.earlydrop, | |
601 | .penaltydrop = q->stats.penaltydrop, | |
602 | .bucketdrop = q->stats.bucketdrop, | |
603 | .queuedrop = q->stats.queuedrop, | |
604 | .childdrop = q->stats.childdrop, | |
605 | .marked = q->stats.marked, | |
606 | }; | |
607 | ||
608 | st.maxqlen = sfb_compute_qlen(&st.maxprob, &st.avgprob, q); | |
609 | ||
610 | return gnet_stats_copy_app(d, &st, sizeof(st)); | |
611 | } | |
612 | ||
613 | static int sfb_dump_class(struct Qdisc *sch, unsigned long cl, | |
614 | struct sk_buff *skb, struct tcmsg *tcm) | |
615 | { | |
616 | return -ENOSYS; | |
617 | } | |
618 | ||
619 | static int sfb_graft(struct Qdisc *sch, unsigned long arg, struct Qdisc *new, | |
653d6fd6 | 620 | struct Qdisc **old, struct netlink_ext_ack *extack) |
e13e02a3 ED |
621 | { |
622 | struct sfb_sched_data *q = qdisc_priv(sch); | |
623 | ||
624 | if (new == NULL) | |
625 | new = &noop_qdisc; | |
626 | ||
86a7996c | 627 | *old = qdisc_replace(sch, new, &q->qdisc); |
e13e02a3 ED |
628 | return 0; |
629 | } | |
630 | ||
631 | static struct Qdisc *sfb_leaf(struct Qdisc *sch, unsigned long arg) | |
632 | { | |
633 | struct sfb_sched_data *q = qdisc_priv(sch); | |
634 | ||
635 | return q->qdisc; | |
636 | } | |
637 | ||
143976ce | 638 | static unsigned long sfb_find(struct Qdisc *sch, u32 classid) |
e13e02a3 ED |
639 | { |
640 | return 1; | |
641 | } | |
642 | ||
143976ce | 643 | static void sfb_unbind(struct Qdisc *sch, unsigned long arg) |
e13e02a3 ED |
644 | { |
645 | } | |
646 | ||
647 | static int sfb_change_class(struct Qdisc *sch, u32 classid, u32 parentid, | |
793d81d6 AA |
648 | struct nlattr **tca, unsigned long *arg, |
649 | struct netlink_ext_ack *extack) | |
e13e02a3 ED |
650 | { |
651 | return -ENOSYS; | |
652 | } | |
653 | ||
4dd78a73 MM |
654 | static int sfb_delete(struct Qdisc *sch, unsigned long cl, |
655 | struct netlink_ext_ack *extack) | |
e13e02a3 ED |
656 | { |
657 | return -ENOSYS; | |
658 | } | |
659 | ||
660 | static void sfb_walk(struct Qdisc *sch, struct qdisc_walker *walker) | |
661 | { | |
662 | if (!walker->stop) { | |
e046fa89 | 663 | tc_qdisc_stats_dump(sch, 1, walker); |
e13e02a3 ED |
664 | } |
665 | } | |
666 | ||
cbaacc4e AA |
667 | static struct tcf_block *sfb_tcf_block(struct Qdisc *sch, unsigned long cl, |
668 | struct netlink_ext_ack *extack) | |
e13e02a3 ED |
669 | { |
670 | struct sfb_sched_data *q = qdisc_priv(sch); | |
671 | ||
672 | if (cl) | |
673 | return NULL; | |
6529eaba | 674 | return q->block; |
e13e02a3 ED |
675 | } |
676 | ||
677 | static unsigned long sfb_bind(struct Qdisc *sch, unsigned long parent, | |
678 | u32 classid) | |
679 | { | |
680 | return 0; | |
681 | } | |
682 | ||
683 | ||
684 | static const struct Qdisc_class_ops sfb_class_ops = { | |
685 | .graft = sfb_graft, | |
686 | .leaf = sfb_leaf, | |
143976ce | 687 | .find = sfb_find, |
e13e02a3 ED |
688 | .change = sfb_change_class, |
689 | .delete = sfb_delete, | |
690 | .walk = sfb_walk, | |
6529eaba | 691 | .tcf_block = sfb_tcf_block, |
e13e02a3 | 692 | .bind_tcf = sfb_bind, |
143976ce | 693 | .unbind_tcf = sfb_unbind, |
e13e02a3 ED |
694 | .dump = sfb_dump_class, |
695 | }; | |
696 | ||
697 | static struct Qdisc_ops sfb_qdisc_ops __read_mostly = { | |
698 | .id = "sfb", | |
699 | .priv_size = sizeof(struct sfb_sched_data), | |
700 | .cl_ops = &sfb_class_ops, | |
701 | .enqueue = sfb_enqueue, | |
702 | .dequeue = sfb_dequeue, | |
703 | .peek = sfb_peek, | |
704 | .init = sfb_init, | |
705 | .reset = sfb_reset, | |
706 | .destroy = sfb_destroy, | |
707 | .change = sfb_change, | |
708 | .dump = sfb_dump, | |
709 | .dump_stats = sfb_dump_stats, | |
710 | .owner = THIS_MODULE, | |
711 | }; | |
712 | ||
713 | static int __init sfb_module_init(void) | |
714 | { | |
715 | return register_qdisc(&sfb_qdisc_ops); | |
716 | } | |
717 | ||
718 | static void __exit sfb_module_exit(void) | |
719 | { | |
720 | unregister_qdisc(&sfb_qdisc_ops); | |
721 | } | |
722 | ||
723 | module_init(sfb_module_init) | |
724 | module_exit(sfb_module_exit) | |
725 | ||
726 | MODULE_DESCRIPTION("Stochastic Fair Blue queue discipline"); | |
727 | MODULE_AUTHOR("Juliusz Chroboczek"); | |
728 | MODULE_AUTHOR("Eric Dumazet"); | |
729 | MODULE_LICENSE("GPL"); |