?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Linux 5.7.7
[linux/fpc-iii.git] / net / sched / sch_choke.c
blob1bcf8fbfd40e4c56baddd8b8f0fe1bb804cc5b4e
1 // SPDX-License-Identifier: GPL-2.0-only
2 /*
3 * net/sched/sch_choke.c CHOKE scheduler
4 *
5 * Copyright (c) 2011 Stephen Hemminger <shemminger@vyatta.com>
6 * Copyright (c) 2011 Eric Dumazet <eric.dumazet@gmail.com>
7 */
8
9 #include <linux/module.h>
10 #include <linux/types.h>
11 #include <linux/kernel.h>
12 #include <linux/skbuff.h>
13 #include <linux/vmalloc.h>
14 #include <net/pkt_sched.h>
15 #include <net/pkt_cls.h>
16 #include <net/inet_ecn.h>
17 #include <net/red.h>
18 #include <net/flow_dissector.h>
19
20 /*
21 CHOKe stateless AQM for fair bandwidth allocation
22 =================================================
23
24 CHOKe (CHOose and Keep for responsive flows, CHOose and Kill for
25 unresponsive flows) is a variant of RED that penalizes misbehaving flows but
26 maintains no flow state. The difference from RED is an additional step
27 during the enqueuing process. If average queue size is over the
28 low threshold (qmin), a packet is chosen at random from the queue.
29 If both the new and chosen packet are from the same flow, both
30 are dropped. Unlike RED, CHOKe is not really a "classful" qdisc because it
31 needs to access packets in queue randomly. It has a minimal class
32 interface to allow overriding the builtin flow classifier with
33 filters.
34
35 Source:
36 R. Pan, B. Prabhakar, and K. Psounis, "CHOKe, A Stateless
37 Active Queue Management Scheme for Approximating Fair Bandwidth Allocation",
38 IEEE INFOCOM, 2000.
39
40 A. Tang, J. Wang, S. Low, "Understanding CHOKe: Throughput and Spatial
41 Characteristics", IEEE/ACM Transactions on Networking, 2004
42
43 */
44
45 /* Upper bound on size of sk_buff table (packets) */
46 #define CHOKE_MAX_QUEUE (128*1024 - 1)
47
48 struct choke_sched_data {
49 /* Parameters */
50 u32 limit;
51 unsigned char flags;
52
53 struct red_parms parms;
54
55 /* Variables */
56 struct red_vars vars;
57 struct {
58 u32 prob_drop; /* Early probability drops */
59 u32 prob_mark; /* Early probability marks */
60 u32 forced_drop; /* Forced drops, qavg > max_thresh */
61 u32 forced_mark; /* Forced marks, qavg > max_thresh */
62 u32 pdrop; /* Drops due to queue limits */
63 u32 other; /* Drops due to drop() calls */
64 u32 matched; /* Drops to flow match */
65 } stats;
66
67 unsigned int head;
68 unsigned int tail;
69
70 unsigned int tab_mask; /* size - 1 */
71
72 struct sk_buff **tab;
73 };
74
75 /* number of elements in queue including holes */
76 static unsigned int choke_len(const struct choke_sched_data *q)
77 {
78 return (q->tail - q->head) & q->tab_mask;
79 }
80
81 /* Is ECN parameter configured */
82 static int use_ecn(const struct choke_sched_data *q)
83 {
84 return q->flags & TC_RED_ECN;
85 }
86
87 /* Should packets over max just be dropped (versus marked) */
88 static int use_harddrop(const struct choke_sched_data *q)
89 {
90 return q->flags & TC_RED_HARDDROP;
91 }
92
93 /* Move head pointer forward to skip over holes */
94 static void choke_zap_head_holes(struct choke_sched_data *q)
95 {
96 do {
97 q->head = (q->head + 1) & q->tab_mask;
98 if (q->head == q->tail)
99 break;
100 } while (q->tab[q->head] == NULL);
101 }
102
103 /* Move tail pointer backwards to reuse holes */
104 static void choke_zap_tail_holes(struct choke_sched_data *q)
105 {
106 do {
107 q->tail = (q->tail - 1) & q->tab_mask;
108 if (q->head == q->tail)
109 break;
110 } while (q->tab[q->tail] == NULL);
111 }
112
113 /* Drop packet from queue array by creating a "hole" */
114 static void choke_drop_by_idx(struct Qdisc *sch, unsigned int idx,
115 struct sk_buff **to_free)
116 {
117 struct choke_sched_data *q = qdisc_priv(sch);
118 struct sk_buff *skb = q->tab[idx];
119
120 q->tab[idx] = NULL;
121
122 if (idx == q->head)
123 choke_zap_head_holes(q);
124 if (idx == q->tail)
125 choke_zap_tail_holes(q);
126
127 qdisc_qstats_backlog_dec(sch, skb);
128 qdisc_tree_reduce_backlog(sch, 1, qdisc_pkt_len(skb));
129 qdisc_drop(skb, sch, to_free);
130 --sch->q.qlen;
131 }
132
133 struct choke_skb_cb {
134 u16 classid;
135 u8 keys_valid;
136 struct flow_keys_digest keys;
137 };
138
139 static inline struct choke_skb_cb *choke_skb_cb(const struct sk_buff *skb)
140 {
141 qdisc_cb_private_validate(skb, sizeof(struct choke_skb_cb));
142 return (struct choke_skb_cb *)qdisc_skb_cb(skb)->data;
143 }
144
145 static inline void choke_set_classid(struct sk_buff *skb, u16 classid)
146 {
147 choke_skb_cb(skb)->classid = classid;
148 }
149
150 /*
151 * Compare flow of two packets
152 * Returns true only if source and destination address and port match.
153 * false for special cases
154 */
155 static bool choke_match_flow(struct sk_buff *skb1,
156 struct sk_buff *skb2)
157 {
158 struct flow_keys temp;
159
160 if (skb1->protocol != skb2->protocol)
161 return false;
162
163 if (!choke_skb_cb(skb1)->keys_valid) {
164 choke_skb_cb(skb1)->keys_valid = 1;
165 skb_flow_dissect_flow_keys(skb1, &temp, 0);
166 make_flow_keys_digest(&choke_skb_cb(skb1)->keys, &temp);
167 }
168
169 if (!choke_skb_cb(skb2)->keys_valid) {
170 choke_skb_cb(skb2)->keys_valid = 1;
171 skb_flow_dissect_flow_keys(skb2, &temp, 0);
172 make_flow_keys_digest(&choke_skb_cb(skb2)->keys, &temp);
173 }
174
175 return !memcmp(&choke_skb_cb(skb1)->keys,
176 &choke_skb_cb(skb2)->keys,
177 sizeof(choke_skb_cb(skb1)->keys));
178 }
179
180 /*
181 * Select a packet at random from queue
182 * HACK: since queue can have holes from previous deletion; retry several
183 * times to find a random skb but then just give up and return the head
184 * Will return NULL if queue is empty (q->head == q->tail)
185 */
186 static struct sk_buff *choke_peek_random(const struct choke_sched_data *q,
187 unsigned int *pidx)
188 {
189 struct sk_buff *skb;
190 int retrys = 3;
191
192 do {
193 *pidx = (q->head + prandom_u32_max(choke_len(q))) & q->tab_mask;
194 skb = q->tab[*pidx];
195 if (skb)
196 return skb;
197 } while (--retrys > 0);
198
199 return q->tab[*pidx = q->head];
200 }
201
202 /*
203 * Compare new packet with random packet in queue
204 * returns true if matched and sets *pidx
205 */
206 static bool choke_match_random(const struct choke_sched_data *q,
207 struct sk_buff *nskb,
208 unsigned int *pidx)
209 {
210 struct sk_buff *oskb;
211
212 if (q->head == q->tail)
213 return false;
214
215 oskb = choke_peek_random(q, pidx);
216 return choke_match_flow(oskb, nskb);
217 }
218
219 static int choke_enqueue(struct sk_buff *skb, struct Qdisc *sch,
220 struct sk_buff **to_free)
221 {
222 struct choke_sched_data *q = qdisc_priv(sch);
223 const struct red_parms *p = &q->parms;
224
225 choke_skb_cb(skb)->keys_valid = 0;
226 /* Compute average queue usage (see RED) */
227 q->vars.qavg = red_calc_qavg(p, &q->vars, sch->q.qlen);
228 if (red_is_idling(&q->vars))
229 red_end_of_idle_period(&q->vars);
230
231 /* Is queue small? */
232 if (q->vars.qavg <= p->qth_min)
233 q->vars.qcount = -1;
234 else {
235 unsigned int idx;
236
237 /* Draw a packet at random from queue and compare flow */
238 if (choke_match_random(q, skb, &idx)) {
239 q->stats.matched++;
240 choke_drop_by_idx(sch, idx, to_free);
241 goto congestion_drop;
242 }
243
244 /* Queue is large, always mark/drop */
245 if (q->vars.qavg > p->qth_max) {
246 q->vars.qcount = -1;
247
248 qdisc_qstats_overlimit(sch);
249 if (use_harddrop(q) || !use_ecn(q) ||
250 !INET_ECN_set_ce(skb)) {
251 q->stats.forced_drop++;
252 goto congestion_drop;
253 }
254
255 q->stats.forced_mark++;
256 } else if (++q->vars.qcount) {
257 if (red_mark_probability(p, &q->vars, q->vars.qavg)) {
258 q->vars.qcount = 0;
259 q->vars.qR = red_random(p);
260
261 qdisc_qstats_overlimit(sch);
262 if (!use_ecn(q) || !INET_ECN_set_ce(skb)) {
263 q->stats.prob_drop++;
264 goto congestion_drop;
265 }
266
267 q->stats.prob_mark++;
268 }
269 } else
270 q->vars.qR = red_random(p);
271 }
272
273 /* Admit new packet */
274 if (sch->q.qlen < q->limit) {
275 q->tab[q->tail] = skb;
276 q->tail = (q->tail + 1) & q->tab_mask;
277 ++sch->q.qlen;
278 qdisc_qstats_backlog_inc(sch, skb);
279 return NET_XMIT_SUCCESS;
280 }
281
282 q->stats.pdrop++;
283 return qdisc_drop(skb, sch, to_free);
284
285 congestion_drop:
286 qdisc_drop(skb, sch, to_free);
287 return NET_XMIT_CN;
288 }
289
290 static struct sk_buff *choke_dequeue(struct Qdisc *sch)
291 {
292 struct choke_sched_data *q = qdisc_priv(sch);
293 struct sk_buff *skb;
294
295 if (q->head == q->tail) {
296 if (!red_is_idling(&q->vars))
297 red_start_of_idle_period(&q->vars);
298 return NULL;
299 }
300
301 skb = q->tab[q->head];
302 q->tab[q->head] = NULL;
303 choke_zap_head_holes(q);
304 --sch->q.qlen;
305 qdisc_qstats_backlog_dec(sch, skb);
306 qdisc_bstats_update(sch, skb);
307
308 return skb;
309 }
310
311 static void choke_reset(struct Qdisc *sch)
312 {
313 struct choke_sched_data *q = qdisc_priv(sch);
314
315 while (q->head != q->tail) {
316 struct sk_buff *skb = q->tab[q->head];
317
318 q->head = (q->head + 1) & q->tab_mask;
319 if (!skb)
320 continue;
321 rtnl_qdisc_drop(skb, sch);
322 }
323
324 sch->q.qlen = 0;
325 sch->qstats.backlog = 0;
326 if (q->tab)
327 memset(q->tab, 0, (q->tab_mask + 1) * sizeof(struct sk_buff *));
328 q->head = q->tail = 0;
329 red_restart(&q->vars);
330 }
331
332 static const struct nla_policy choke_policy[TCA_CHOKE_MAX + 1] = {
333 [TCA_CHOKE_PARMS] = { .len = sizeof(struct tc_red_qopt) },
334 [TCA_CHOKE_STAB] = { .len = RED_STAB_SIZE },
335 [TCA_CHOKE_MAX_P] = { .type = NLA_U32 },
336 };
337
338
339 static void choke_free(void *addr)
340 {
341 kvfree(addr);
342 }
343
344 static int choke_change(struct Qdisc *sch, struct nlattr *opt,
345 struct netlink_ext_ack *extack)
346 {
347 struct choke_sched_data *q = qdisc_priv(sch);
348 struct nlattr *tb[TCA_CHOKE_MAX + 1];
349 const struct tc_red_qopt *ctl;
350 int err;
351 struct sk_buff **old = NULL;
352 unsigned int mask;
353 u32 max_P;
354
355 if (opt == NULL)
356 return -EINVAL;
357
358 err = nla_parse_nested_deprecated(tb, TCA_CHOKE_MAX, opt,
359 choke_policy, NULL);
360 if (err < 0)
361 return err;
362
363 if (tb[TCA_CHOKE_PARMS] == NULL ||
364 tb[TCA_CHOKE_STAB] == NULL)
365 return -EINVAL;
366
367 max_P = tb[TCA_CHOKE_MAX_P] ? nla_get_u32(tb[TCA_CHOKE_MAX_P]) : 0;
368
369 ctl = nla_data(tb[TCA_CHOKE_PARMS]);
370
371 if (!red_check_params(ctl->qth_min, ctl->qth_max, ctl->Wlog))
372 return -EINVAL;
373
374 if (ctl->limit > CHOKE_MAX_QUEUE)
375 return -EINVAL;
376
377 mask = roundup_pow_of_two(ctl->limit + 1) - 1;
378 if (mask != q->tab_mask) {
379 struct sk_buff **ntab;
380
381 ntab = kvcalloc(mask + 1, sizeof(struct sk_buff *), GFP_KERNEL);
382 if (!ntab)
383 return -ENOMEM;
384
385 sch_tree_lock(sch);
386 old = q->tab;
387 if (old) {
388 unsigned int oqlen = sch->q.qlen, tail = 0;
389 unsigned dropped = 0;
390
391 while (q->head != q->tail) {
392 struct sk_buff *skb = q->tab[q->head];
393
394 q->head = (q->head + 1) & q->tab_mask;
395 if (!skb)
396 continue;
397 if (tail < mask) {
398 ntab[tail++] = skb;
399 continue;
400 }
401 dropped += qdisc_pkt_len(skb);
402 qdisc_qstats_backlog_dec(sch, skb);
403 --sch->q.qlen;
404 rtnl_qdisc_drop(skb, sch);
405 }
406 qdisc_tree_reduce_backlog(sch, oqlen - sch->q.qlen, dropped);
407 q->head = 0;
408 q->tail = tail;
409 }
410
411 q->tab_mask = mask;
412 q->tab = ntab;
413 } else
414 sch_tree_lock(sch);
415
416 q->flags = ctl->flags;
417 q->limit = ctl->limit;
418
419 red_set_parms(&q->parms, ctl->qth_min, ctl->qth_max, ctl->Wlog,
420 ctl->Plog, ctl->Scell_log,
421 nla_data(tb[TCA_CHOKE_STAB]),
422 max_P);
423 red_set_vars(&q->vars);
424
425 if (q->head == q->tail)
426 red_end_of_idle_period(&q->vars);
427
428 sch_tree_unlock(sch);
429 choke_free(old);
430 return 0;
431 }
432
433 static int choke_init(struct Qdisc *sch, struct nlattr *opt,
434 struct netlink_ext_ack *extack)
435 {
436 return choke_change(sch, opt, extack);
437 }
438
439 static int choke_dump(struct Qdisc *sch, struct sk_buff *skb)
440 {
441 struct choke_sched_data *q = qdisc_priv(sch);
442 struct nlattr *opts = NULL;
443 struct tc_red_qopt opt = {
444 .limit = q->limit,
445 .flags = q->flags,
446 .qth_min = q->parms.qth_min >> q->parms.Wlog,
447 .qth_max = q->parms.qth_max >> q->parms.Wlog,
448 .Wlog = q->parms.Wlog,
449 .Plog = q->parms.Plog,
450 .Scell_log = q->parms.Scell_log,
451 };
452
453 opts = nla_nest_start_noflag(skb, TCA_OPTIONS);
454 if (opts == NULL)
455 goto nla_put_failure;
456
457 if (nla_put(skb, TCA_CHOKE_PARMS, sizeof(opt), &opt) ||
458 nla_put_u32(skb, TCA_CHOKE_MAX_P, q->parms.max_P))
459 goto nla_put_failure;
460 return nla_nest_end(skb, opts);
461
462 nla_put_failure:
463 nla_nest_cancel(skb, opts);
464 return -EMSGSIZE;
465 }
466
467 static int choke_dump_stats(struct Qdisc *sch, struct gnet_dump *d)
468 {
469 struct choke_sched_data *q = qdisc_priv(sch);
470 struct tc_choke_xstats st = {
471 .early = q->stats.prob_drop + q->stats.forced_drop,
472 .marked = q->stats.prob_mark + q->stats.forced_mark,
473 .pdrop = q->stats.pdrop,
474 .other = q->stats.other,
475 .matched = q->stats.matched,
476 };
477
478 return gnet_stats_copy_app(d, &st, sizeof(st));
479 }
480
481 static void choke_destroy(struct Qdisc *sch)
482 {
483 struct choke_sched_data *q = qdisc_priv(sch);
484
485 choke_free(q->tab);
486 }
487
488 static struct sk_buff *choke_peek_head(struct Qdisc *sch)
489 {
490 struct choke_sched_data *q = qdisc_priv(sch);
491
492 return (q->head != q->tail) ? q->tab[q->head] : NULL;
493 }
494
495 static struct Qdisc_ops choke_qdisc_ops __read_mostly = {
496 .id = "choke",
497 .priv_size = sizeof(struct choke_sched_data),
498
499 .enqueue = choke_enqueue,
500 .dequeue = choke_dequeue,
501 .peek = choke_peek_head,
502 .init = choke_init,
503 .destroy = choke_destroy,
504 .reset = choke_reset,
505 .change = choke_change,
506 .dump = choke_dump,
507 .dump_stats = choke_dump_stats,
508 .owner = THIS_MODULE,
509 };
510
511 static int __init choke_module_init(void)
512 {
513 return register_qdisc(&choke_qdisc_ops);
514 }
515
516 static void __exit choke_module_exit(void)
517 {
518 unregister_qdisc(&choke_qdisc_ops);
519 }
520
521 module_init(choke_module_init)
522 module_exit(choke_module_exit)
523
524 MODULE_LICENSE("GPL");
Linux with added FPC-III support