Version:  2.0.40 2.2.26 2.4.37 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10 3.11 3.12 3.13 3.14 3.15 3.16 3.17 3.18

Linux/net/sched/sch_choke.c

  1 /*
  2  * net/sched/sch_choke.c        CHOKE scheduler
  3  *
  4  * Copyright (c) 2011 Stephen Hemminger <shemminger@vyatta.com>
  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  */
 12 
 13 #include <linux/module.h>
 14 #include <linux/types.h>
 15 #include <linux/kernel.h>
 16 #include <linux/skbuff.h>
 17 #include <linux/vmalloc.h>
 18 #include <net/pkt_sched.h>
 19 #include <net/inet_ecn.h>
 20 #include <net/red.h>
 21 #include <net/flow_keys.h>
 22 
 23 /*
 24    CHOKe stateless AQM for fair bandwidth allocation
 25    =================================================
 26 
 27    CHOKe (CHOose and Keep for responsive flows, CHOose and Kill for
 28    unresponsive flows) is a variant of RED that penalizes misbehaving flows but
 29    maintains no flow state. The difference from RED is an additional step
 30    during the enqueuing process. If average queue size is over the
 31    low threshold (qmin), a packet is chosen at random from the queue.
 32    If both the new and chosen packet are from the same flow, both
 33    are dropped. Unlike RED, CHOKe is not really a "classful" qdisc because it
 34    needs to access packets in queue randomly. It has a minimal class
 35    interface to allow overriding the builtin flow classifier with
 36    filters.
 37 
 38    Source:
 39    R. Pan, B. Prabhakar, and K. Psounis, "CHOKe, A Stateless
 40    Active Queue Management Scheme for Approximating Fair Bandwidth Allocation",
 41    IEEE INFOCOM, 2000.
 42 
 43    A. Tang, J. Wang, S. Low, "Understanding CHOKe: Throughput and Spatial
 44    Characteristics", IEEE/ACM Transactions on Networking, 2004
 45 
 46  */
 47 
 48 /* Upper bound on size of sk_buff table (packets) */
 49 #define CHOKE_MAX_QUEUE (128*1024 - 1)
 50 
 51 struct choke_sched_data {
 52 /* Parameters */
 53         u32              limit;
 54         unsigned char    flags;
 55 
 56         struct red_parms parms;
 57 
 58 /* Variables */
 59         struct red_vars  vars;
 60         struct tcf_proto __rcu *filter_list;
 61         struct {
 62                 u32     prob_drop;      /* Early probability drops */
 63                 u32     prob_mark;      /* Early probability marks */
 64                 u32     forced_drop;    /* Forced drops, qavg > max_thresh */
 65                 u32     forced_mark;    /* Forced marks, qavg > max_thresh */
 66                 u32     pdrop;          /* Drops due to queue limits */
 67                 u32     other;          /* Drops due to drop() calls */
 68                 u32     matched;        /* Drops to flow match */
 69         } stats;
 70 
 71         unsigned int     head;
 72         unsigned int     tail;
 73 
 74         unsigned int     tab_mask; /* size - 1 */
 75 
 76         struct sk_buff **tab;
 77 };
 78 
 79 /* number of elements in queue including holes */
 80 static unsigned int choke_len(const struct choke_sched_data *q)
 81 {
 82         return (q->tail - q->head) & q->tab_mask;
 83 }
 84 
 85 /* Is ECN parameter configured */
 86 static int use_ecn(const struct choke_sched_data *q)
 87 {
 88         return q->flags & TC_RED_ECN;
 89 }
 90 
 91 /* Should packets over max just be dropped (versus marked) */
 92 static int use_harddrop(const struct choke_sched_data *q)
 93 {
 94         return q->flags & TC_RED_HARDDROP;
 95 }
 96 
 97 /* Move head pointer forward to skip over holes */
 98 static void choke_zap_head_holes(struct choke_sched_data *q)
 99 {
100         do {
101                 q->head = (q->head + 1) & q->tab_mask;
102                 if (q->head == q->tail)
103                         break;
104         } while (q->tab[q->head] == NULL);
105 }
106 
107 /* Move tail pointer backwards to reuse holes */
108 static void choke_zap_tail_holes(struct choke_sched_data *q)
109 {
110         do {
111                 q->tail = (q->tail - 1) & q->tab_mask;
112                 if (q->head == q->tail)
113                         break;
114         } while (q->tab[q->tail] == NULL);
115 }
116 
117 /* Drop packet from queue array by creating a "hole" */
118 static void choke_drop_by_idx(struct Qdisc *sch, unsigned int idx)
119 {
120         struct choke_sched_data *q = qdisc_priv(sch);
121         struct sk_buff *skb = q->tab[idx];
122 
123         q->tab[idx] = NULL;
124 
125         if (idx == q->head)
126                 choke_zap_head_holes(q);
127         if (idx == q->tail)
128                 choke_zap_tail_holes(q);
129 
130         qdisc_qstats_backlog_dec(sch, skb);
131         qdisc_drop(skb, sch);
132         qdisc_tree_decrease_qlen(sch, 1);
133         --sch->q.qlen;
134 }
135 
136 /* private part of skb->cb[] that a qdisc is allowed to use
137  * is limited to QDISC_CB_PRIV_LEN bytes.
138  * As a flow key might be too large, we store a part of it only.
139  */
140 #define CHOKE_K_LEN min_t(u32, sizeof(struct flow_keys), QDISC_CB_PRIV_LEN - 3)
141 
142 struct choke_skb_cb {
143         u16                     classid;
144         u8                      keys_valid;
145         u8                      keys[QDISC_CB_PRIV_LEN - 3];
146 };
147 
148 static inline struct choke_skb_cb *choke_skb_cb(const struct sk_buff *skb)
149 {
150         qdisc_cb_private_validate(skb, sizeof(struct choke_skb_cb));
151         return (struct choke_skb_cb *)qdisc_skb_cb(skb)->data;
152 }
153 
154 static inline void choke_set_classid(struct sk_buff *skb, u16 classid)
155 {
156         choke_skb_cb(skb)->classid = classid;
157 }
158 
159 static u16 choke_get_classid(const struct sk_buff *skb)
160 {
161         return choke_skb_cb(skb)->classid;
162 }
163 
164 /*
165  * Compare flow of two packets
166  *  Returns true only if source and destination address and port match.
167  *          false for special cases
168  */
169 static bool choke_match_flow(struct sk_buff *skb1,
170                              struct sk_buff *skb2)
171 {
172         struct flow_keys temp;
173 
174         if (skb1->protocol != skb2->protocol)
175                 return false;
176 
177         if (!choke_skb_cb(skb1)->keys_valid) {
178                 choke_skb_cb(skb1)->keys_valid = 1;
179                 skb_flow_dissect(skb1, &temp);
180                 memcpy(&choke_skb_cb(skb1)->keys, &temp, CHOKE_K_LEN);
181         }
182 
183         if (!choke_skb_cb(skb2)->keys_valid) {
184                 choke_skb_cb(skb2)->keys_valid = 1;
185                 skb_flow_dissect(skb2, &temp);
186                 memcpy(&choke_skb_cb(skb2)->keys, &temp, CHOKE_K_LEN);
187         }
188 
189         return !memcmp(&choke_skb_cb(skb1)->keys,
190                        &choke_skb_cb(skb2)->keys,
191                        CHOKE_K_LEN);
192 }
193 
194 /*
195  * Classify flow using either:
196  *  1. pre-existing classification result in skb
197  *  2. fast internal classification
198  *  3. use TC filter based classification
199  */
200 static bool choke_classify(struct sk_buff *skb,
201                            struct Qdisc *sch, int *qerr)
202 
203 {
204         struct choke_sched_data *q = qdisc_priv(sch);
205         struct tcf_result res;
206         struct tcf_proto *fl;
207         int result;
208 
209         fl = rcu_dereference_bh(q->filter_list);
210         result = tc_classify(skb, fl, &res);
211         if (result >= 0) {
212 #ifdef CONFIG_NET_CLS_ACT
213                 switch (result) {
214                 case TC_ACT_STOLEN:
215                 case TC_ACT_QUEUED:
216                         *qerr = NET_XMIT_SUCCESS | __NET_XMIT_STOLEN;
217                 case TC_ACT_SHOT:
218                         return false;
219                 }
220 #endif
221                 choke_set_classid(skb, TC_H_MIN(res.classid));
222                 return true;
223         }
224 
225         return false;
226 }
227 
228 /*
229  * Select a packet at random from queue
230  * HACK: since queue can have holes from previous deletion; retry several
231  *   times to find a random skb but then just give up and return the head
232  * Will return NULL if queue is empty (q->head == q->tail)
233  */
234 static struct sk_buff *choke_peek_random(const struct choke_sched_data *q,
235                                          unsigned int *pidx)
236 {
237         struct sk_buff *skb;
238         int retrys = 3;
239 
240         do {
241                 *pidx = (q->head + prandom_u32_max(choke_len(q))) & q->tab_mask;
242                 skb = q->tab[*pidx];
243                 if (skb)
244                         return skb;
245         } while (--retrys > 0);
246 
247         return q->tab[*pidx = q->head];
248 }
249 
250 /*
251  * Compare new packet with random packet in queue
252  * returns true if matched and sets *pidx
253  */
254 static bool choke_match_random(const struct choke_sched_data *q,
255                                struct sk_buff *nskb,
256                                unsigned int *pidx)
257 {
258         struct sk_buff *oskb;
259 
260         if (q->head == q->tail)
261                 return false;
262 
263         oskb = choke_peek_random(q, pidx);
264         if (rcu_access_pointer(q->filter_list))
265                 return choke_get_classid(nskb) == choke_get_classid(oskb);
266 
267         return choke_match_flow(oskb, nskb);
268 }
269 
270 static int choke_enqueue(struct sk_buff *skb, struct Qdisc *sch)
271 {
272         int ret = NET_XMIT_SUCCESS | __NET_XMIT_BYPASS;
273         struct choke_sched_data *q = qdisc_priv(sch);
274         const struct red_parms *p = &q->parms;
275 
276         if (rcu_access_pointer(q->filter_list)) {
277                 /* If using external classifiers, get result and record it. */
278                 if (!choke_classify(skb, sch, &ret))
279                         goto other_drop;        /* Packet was eaten by filter */
280         }
281 
282         choke_skb_cb(skb)->keys_valid = 0;
283         /* Compute average queue usage (see RED) */
284         q->vars.qavg = red_calc_qavg(p, &q->vars, sch->q.qlen);
285         if (red_is_idling(&q->vars))
286                 red_end_of_idle_period(&q->vars);
287 
288         /* Is queue small? */
289         if (q->vars.qavg <= p->qth_min)
290                 q->vars.qcount = -1;
291         else {
292                 unsigned int idx;
293 
294                 /* Draw a packet at random from queue and compare flow */
295                 if (choke_match_random(q, skb, &idx)) {
296                         q->stats.matched++;
297                         choke_drop_by_idx(sch, idx);
298                         goto congestion_drop;
299                 }
300 
301                 /* Queue is large, always mark/drop */
302                 if (q->vars.qavg > p->qth_max) {
303                         q->vars.qcount = -1;
304 
305                         qdisc_qstats_overlimit(sch);
306                         if (use_harddrop(q) || !use_ecn(q) ||
307                             !INET_ECN_set_ce(skb)) {
308                                 q->stats.forced_drop++;
309                                 goto congestion_drop;
310                         }
311 
312                         q->stats.forced_mark++;
313                 } else if (++q->vars.qcount) {
314                         if (red_mark_probability(p, &q->vars, q->vars.qavg)) {
315                                 q->vars.qcount = 0;
316                                 q->vars.qR = red_random(p);
317 
318                                 qdisc_qstats_overlimit(sch);
319                                 if (!use_ecn(q) || !INET_ECN_set_ce(skb)) {
320                                         q->stats.prob_drop++;
321                                         goto congestion_drop;
322                                 }
323 
324                                 q->stats.prob_mark++;
325                         }
326                 } else
327                         q->vars.qR = red_random(p);
328         }
329 
330         /* Admit new packet */
331         if (sch->q.qlen < q->limit) {
332                 q->tab[q->tail] = skb;
333                 q->tail = (q->tail + 1) & q->tab_mask;
334                 ++sch->q.qlen;
335                 qdisc_qstats_backlog_inc(sch, skb);
336                 return NET_XMIT_SUCCESS;
337         }
338 
339         q->stats.pdrop++;
340         return qdisc_drop(skb, sch);
341 
342 congestion_drop:
343         qdisc_drop(skb, sch);
344         return NET_XMIT_CN;
345 
346 other_drop:
347         if (ret & __NET_XMIT_BYPASS)
348                 qdisc_qstats_drop(sch);
349         kfree_skb(skb);
350         return ret;
351 }
352 
353 static struct sk_buff *choke_dequeue(struct Qdisc *sch)
354 {
355         struct choke_sched_data *q = qdisc_priv(sch);
356         struct sk_buff *skb;
357 
358         if (q->head == q->tail) {
359                 if (!red_is_idling(&q->vars))
360                         red_start_of_idle_period(&q->vars);
361                 return NULL;
362         }
363 
364         skb = q->tab[q->head];
365         q->tab[q->head] = NULL;
366         choke_zap_head_holes(q);
367         --sch->q.qlen;
368         qdisc_qstats_backlog_dec(sch, skb);
369         qdisc_bstats_update(sch, skb);
370 
371         return skb;
372 }
373 
374 static unsigned int choke_drop(struct Qdisc *sch)
375 {
376         struct choke_sched_data *q = qdisc_priv(sch);
377         unsigned int len;
378 
379         len = qdisc_queue_drop(sch);
380         if (len > 0)
381                 q->stats.other++;
382         else {
383                 if (!red_is_idling(&q->vars))
384                         red_start_of_idle_period(&q->vars);
385         }
386 
387         return len;
388 }
389 
390 static void choke_reset(struct Qdisc *sch)
391 {
392         struct choke_sched_data *q = qdisc_priv(sch);
393 
394         red_restart(&q->vars);
395 }
396 
397 static const struct nla_policy choke_policy[TCA_CHOKE_MAX + 1] = {
398         [TCA_CHOKE_PARMS]       = { .len = sizeof(struct tc_red_qopt) },
399         [TCA_CHOKE_STAB]        = { .len = RED_STAB_SIZE },
400         [TCA_CHOKE_MAX_P]       = { .type = NLA_U32 },
401 };
402 
403 
404 static void choke_free(void *addr)
405 {
406         kvfree(addr);
407 }
408 
409 static int choke_change(struct Qdisc *sch, struct nlattr *opt)
410 {
411         struct choke_sched_data *q = qdisc_priv(sch);
412         struct nlattr *tb[TCA_CHOKE_MAX + 1];
413         const struct tc_red_qopt *ctl;
414         int err;
415         struct sk_buff **old = NULL;
416         unsigned int mask;
417         u32 max_P;
418 
419         if (opt == NULL)
420                 return -EINVAL;
421 
422         err = nla_parse_nested(tb, TCA_CHOKE_MAX, opt, choke_policy);
423         if (err < 0)
424                 return err;
425 
426         if (tb[TCA_CHOKE_PARMS] == NULL ||
427             tb[TCA_CHOKE_STAB] == NULL)
428                 return -EINVAL;
429 
430         max_P = tb[TCA_CHOKE_MAX_P] ? nla_get_u32(tb[TCA_CHOKE_MAX_P]) : 0;
431 
432         ctl = nla_data(tb[TCA_CHOKE_PARMS]);
433 
434         if (ctl->limit > CHOKE_MAX_QUEUE)
435                 return -EINVAL;
436 
437         mask = roundup_pow_of_two(ctl->limit + 1) - 1;
438         if (mask != q->tab_mask) {
439                 struct sk_buff **ntab;
440 
441                 ntab = kcalloc(mask + 1, sizeof(struct sk_buff *),
442                                GFP_KERNEL | __GFP_NOWARN);
443                 if (!ntab)
444                         ntab = vzalloc((mask + 1) * sizeof(struct sk_buff *));
445                 if (!ntab)
446                         return -ENOMEM;
447 
448                 sch_tree_lock(sch);
449                 old = q->tab;
450                 if (old) {
451                         unsigned int oqlen = sch->q.qlen, tail = 0;
452 
453                         while (q->head != q->tail) {
454                                 struct sk_buff *skb = q->tab[q->head];
455 
456                                 q->head = (q->head + 1) & q->tab_mask;
457                                 if (!skb)
458                                         continue;
459                                 if (tail < mask) {
460                                         ntab[tail++] = skb;
461                                         continue;
462                                 }
463                                 qdisc_qstats_backlog_dec(sch, skb);
464                                 --sch->q.qlen;
465                                 qdisc_drop(skb, sch);
466                         }
467                         qdisc_tree_decrease_qlen(sch, oqlen - sch->q.qlen);
468                         q->head = 0;
469                         q->tail = tail;
470                 }
471 
472                 q->tab_mask = mask;
473                 q->tab = ntab;
474         } else
475                 sch_tree_lock(sch);
476 
477         q->flags = ctl->flags;
478         q->limit = ctl->limit;
479 
480         red_set_parms(&q->parms, ctl->qth_min, ctl->qth_max, ctl->Wlog,
481                       ctl->Plog, ctl->Scell_log,
482                       nla_data(tb[TCA_CHOKE_STAB]),
483                       max_P);
484         red_set_vars(&q->vars);
485 
486         if (q->head == q->tail)
487                 red_end_of_idle_period(&q->vars);
488 
489         sch_tree_unlock(sch);
490         choke_free(old);
491         return 0;
492 }
493 
494 static int choke_init(struct Qdisc *sch, struct nlattr *opt)
495 {
496         return choke_change(sch, opt);
497 }
498 
499 static int choke_dump(struct Qdisc *sch, struct sk_buff *skb)
500 {
501         struct choke_sched_data *q = qdisc_priv(sch);
502         struct nlattr *opts = NULL;
503         struct tc_red_qopt opt = {
504                 .limit          = q->limit,
505                 .flags          = q->flags,
506                 .qth_min        = q->parms.qth_min >> q->parms.Wlog,
507                 .qth_max        = q->parms.qth_max >> q->parms.Wlog,
508                 .Wlog           = q->parms.Wlog,
509                 .Plog           = q->parms.Plog,
510                 .Scell_log      = q->parms.Scell_log,
511         };
512 
513         opts = nla_nest_start(skb, TCA_OPTIONS);
514         if (opts == NULL)
515                 goto nla_put_failure;
516 
517         if (nla_put(skb, TCA_CHOKE_PARMS, sizeof(opt), &opt) ||
518             nla_put_u32(skb, TCA_CHOKE_MAX_P, q->parms.max_P))
519                 goto nla_put_failure;
520         return nla_nest_end(skb, opts);
521 
522 nla_put_failure:
523         nla_nest_cancel(skb, opts);
524         return -EMSGSIZE;
525 }
526 
527 static int choke_dump_stats(struct Qdisc *sch, struct gnet_dump *d)
528 {
529         struct choke_sched_data *q = qdisc_priv(sch);
530         struct tc_choke_xstats st = {
531                 .early  = q->stats.prob_drop + q->stats.forced_drop,
532                 .marked = q->stats.prob_mark + q->stats.forced_mark,
533                 .pdrop  = q->stats.pdrop,
534                 .other  = q->stats.other,
535                 .matched = q->stats.matched,
536         };
537 
538         return gnet_stats_copy_app(d, &st, sizeof(st));
539 }
540 
541 static void choke_destroy(struct Qdisc *sch)
542 {
543         struct choke_sched_data *q = qdisc_priv(sch);
544 
545         tcf_destroy_chain(&q->filter_list);
546         choke_free(q->tab);
547 }
548 
549 static struct Qdisc *choke_leaf(struct Qdisc *sch, unsigned long arg)
550 {
551         return NULL;
552 }
553 
554 static unsigned long choke_get(struct Qdisc *sch, u32 classid)
555 {
556         return 0;
557 }
558 
559 static void choke_put(struct Qdisc *q, unsigned long cl)
560 {
561 }
562 
563 static unsigned long choke_bind(struct Qdisc *sch, unsigned long parent,
564                                 u32 classid)
565 {
566         return 0;
567 }
568 
569 static struct tcf_proto __rcu **choke_find_tcf(struct Qdisc *sch,
570                                                unsigned long cl)
571 {
572         struct choke_sched_data *q = qdisc_priv(sch);
573 
574         if (cl)
575                 return NULL;
576         return &q->filter_list;
577 }
578 
579 static int choke_dump_class(struct Qdisc *sch, unsigned long cl,
580                           struct sk_buff *skb, struct tcmsg *tcm)
581 {
582         tcm->tcm_handle |= TC_H_MIN(cl);
583         return 0;
584 }
585 
586 static void choke_walk(struct Qdisc *sch, struct qdisc_walker *arg)
587 {
588         if (!arg->stop) {
589                 if (arg->fn(sch, 1, arg) < 0) {
590                         arg->stop = 1;
591                         return;
592                 }
593                 arg->count++;
594         }
595 }
596 
597 static const struct Qdisc_class_ops choke_class_ops = {
598         .leaf           =       choke_leaf,
599         .get            =       choke_get,
600         .put            =       choke_put,
601         .tcf_chain      =       choke_find_tcf,
602         .bind_tcf       =       choke_bind,
603         .unbind_tcf     =       choke_put,
604         .dump           =       choke_dump_class,
605         .walk           =       choke_walk,
606 };
607 
608 static struct sk_buff *choke_peek_head(struct Qdisc *sch)
609 {
610         struct choke_sched_data *q = qdisc_priv(sch);
611 
612         return (q->head != q->tail) ? q->tab[q->head] : NULL;
613 }
614 
615 static struct Qdisc_ops choke_qdisc_ops __read_mostly = {
616         .id             =       "choke",
617         .priv_size      =       sizeof(struct choke_sched_data),
618 
619         .enqueue        =       choke_enqueue,
620         .dequeue        =       choke_dequeue,
621         .peek           =       choke_peek_head,
622         .drop           =       choke_drop,
623         .init           =       choke_init,
624         .destroy        =       choke_destroy,
625         .reset          =       choke_reset,
626         .change         =       choke_change,
627         .dump           =       choke_dump,
628         .dump_stats     =       choke_dump_stats,
629         .owner          =       THIS_MODULE,
630 };
631 
632 static int __init choke_module_init(void)
633 {
634         return register_qdisc(&choke_qdisc_ops);
635 }
636 
637 static void __exit choke_module_exit(void)
638 {
639         unregister_qdisc(&choke_qdisc_ops);
640 }
641 
642 module_init(choke_module_init)
643 module_exit(choke_module_exit)
644 
645 MODULE_LICENSE("GPL");
646 

This page was automatically generated by LXR 0.3.1 (source).  •  Linux is a registered trademark of Linus Torvalds  •  Contact us