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