2 * net/sched/sch_choke.c CHOKE scheduler
4 * Copyright (c) 2011 Stephen Hemminger <shemminger@vyatta.com>
5 * Copyright (c) 2011 Eric Dumazet <eric.dumazet@gmail.com>
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.
13 #include <linux/module.h>
14 #include <linux/types.h>
15 #include <linux/kernel.h>
16 #include <linux/skbuff.h>
17 #include <linux/reciprocal_div.h>
18 #include <linux/vmalloc.h>
19 #include <net/pkt_sched.h>
20 #include <net/inet_ecn.h>
22 #include <net/flow_keys.h>
25 CHOKe stateless AQM for fair bandwidth allocation
26 =================================================
28 CHOKe (CHOose and Keep for responsive flows, CHOose and Kill for
29 unresponsive flows) is a variant of RED that penalizes misbehaving flows but
30 maintains no flow state. The difference from RED is an additional step
31 during the enqueuing process. If average queue size is over the
32 low threshold (qmin), a packet is chosen at random from the queue.
33 If both the new and chosen packet are from the same flow, both
34 are dropped. Unlike RED, CHOKe is not really a "classful" qdisc because it
35 needs to access packets in queue randomly. It has a minimal class
36 interface to allow overriding the builtin flow classifier with
40 R. Pan, B. Prabhakar, and K. Psounis, "CHOKe, A Stateless
41 Active Queue Management Scheme for Approximating Fair Bandwidth Allocation",
44 A. Tang, J. Wang, S. Low, "Understanding CHOKe: Throughput and Spatial
45 Characteristics", IEEE/ACM Transactions on Networking, 2004
49 /* Upper bound on size of sk_buff table (packets) */
50 #define CHOKE_MAX_QUEUE (128*1024 - 1)
52 struct choke_sched_data {
57 struct red_parms parms;
60 struct tcf_proto *filter_list;
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 */
74 unsigned int tab_mask; /* size - 1 */
79 /* deliver a random number between 0 and N - 1 */
80 static u32 random_N(unsigned int N)
82 return reciprocal_divide(random32(), N);
85 /* number of elements in queue including holes */
86 static unsigned int choke_len(const struct choke_sched_data *q)
88 return (q->tail - q->head) & q->tab_mask;
91 /* Is ECN parameter configured */
92 static int use_ecn(const struct choke_sched_data *q)
94 return q->flags & TC_RED_ECN;
97 /* Should packets over max just be dropped (versus marked) */
98 static int use_harddrop(const struct choke_sched_data *q)
100 return q->flags & TC_RED_HARDDROP;
103 /* Move head pointer forward to skip over holes */
104 static void choke_zap_head_holes(struct choke_sched_data *q)
107 q->head = (q->head + 1) & q->tab_mask;
108 if (q->head == q->tail)
110 } while (q->tab[q->head] == NULL);
113 /* Move tail pointer backwards to reuse holes */
114 static void choke_zap_tail_holes(struct choke_sched_data *q)
117 q->tail = (q->tail - 1) & q->tab_mask;
118 if (q->head == q->tail)
120 } while (q->tab[q->tail] == NULL);
123 /* Drop packet from queue array by creating a "hole" */
124 static void choke_drop_by_idx(struct Qdisc *sch, unsigned int idx)
126 struct choke_sched_data *q = qdisc_priv(sch);
127 struct sk_buff *skb = q->tab[idx];
132 choke_zap_head_holes(q);
134 choke_zap_tail_holes(q);
136 sch->qstats.backlog -= qdisc_pkt_len(skb);
137 qdisc_drop(skb, sch);
138 qdisc_tree_decrease_qlen(sch, 1);
142 struct choke_skb_cb {
145 struct flow_keys keys;
148 static inline struct choke_skb_cb *choke_skb_cb(const struct sk_buff *skb)
150 BUILD_BUG_ON(sizeof(skb->cb) <
151 sizeof(struct qdisc_skb_cb) + sizeof(struct choke_skb_cb));
152 return (struct choke_skb_cb *)qdisc_skb_cb(skb)->data;
155 static inline void choke_set_classid(struct sk_buff *skb, u16 classid)
157 choke_skb_cb(skb)->classid = classid;
160 static u16 choke_get_classid(const struct sk_buff *skb)
162 return choke_skb_cb(skb)->classid;
166 * Compare flow of two packets
167 * Returns true only if source and destination address and port match.
168 * false for special cases
170 static bool choke_match_flow(struct sk_buff *skb1,
171 struct sk_buff *skb2)
173 if (skb1->protocol != skb2->protocol)
176 if (!choke_skb_cb(skb1)->keys_valid) {
177 choke_skb_cb(skb1)->keys_valid = 1;
178 skb_flow_dissect(skb1, &choke_skb_cb(skb1)->keys);
181 if (!choke_skb_cb(skb2)->keys_valid) {
182 choke_skb_cb(skb2)->keys_valid = 1;
183 skb_flow_dissect(skb2, &choke_skb_cb(skb2)->keys);
186 return !memcmp(&choke_skb_cb(skb1)->keys,
187 &choke_skb_cb(skb2)->keys,
188 sizeof(struct flow_keys));
192 * Classify flow using either:
193 * 1. pre-existing classification result in skb
194 * 2. fast internal classification
195 * 3. use TC filter based classification
197 static bool choke_classify(struct sk_buff *skb,
198 struct Qdisc *sch, int *qerr)
201 struct choke_sched_data *q = qdisc_priv(sch);
202 struct tcf_result res;
205 result = tc_classify(skb, q->filter_list, &res);
207 #ifdef CONFIG_NET_CLS_ACT
211 *qerr = NET_XMIT_SUCCESS | __NET_XMIT_STOLEN;
216 choke_set_classid(skb, TC_H_MIN(res.classid));
224 * Select a packet at random from queue
225 * HACK: since queue can have holes from previous deletion; retry several
226 * times to find a random skb but then just give up and return the head
227 * Will return NULL if queue is empty (q->head == q->tail)
229 static struct sk_buff *choke_peek_random(const struct choke_sched_data *q,
236 *pidx = (q->head + random_N(choke_len(q))) & q->tab_mask;
240 } while (--retrys > 0);
242 return q->tab[*pidx = q->head];
246 * Compare new packet with random packet in queue
247 * returns true if matched and sets *pidx
249 static bool choke_match_random(const struct choke_sched_data *q,
250 struct sk_buff *nskb,
253 struct sk_buff *oskb;
255 if (q->head == q->tail)
258 oskb = choke_peek_random(q, pidx);
260 return choke_get_classid(nskb) == choke_get_classid(oskb);
262 return choke_match_flow(oskb, nskb);
265 static int choke_enqueue(struct sk_buff *skb, struct Qdisc *sch)
267 struct choke_sched_data *q = qdisc_priv(sch);
268 struct red_parms *p = &q->parms;
269 int ret = NET_XMIT_SUCCESS | __NET_XMIT_BYPASS;
271 if (q->filter_list) {
272 /* If using external classifiers, get result and record it. */
273 if (!choke_classify(skb, sch, &ret))
274 goto other_drop; /* Packet was eaten by filter */
277 choke_skb_cb(skb)->keys_valid = 0;
278 /* Compute average queue usage (see RED) */
279 p->qavg = red_calc_qavg(p, sch->q.qlen);
280 if (red_is_idling(p))
281 red_end_of_idle_period(p);
283 /* Is queue small? */
284 if (p->qavg <= p->qth_min)
289 /* Draw a packet at random from queue and compare flow */
290 if (choke_match_random(q, skb, &idx)) {
292 choke_drop_by_idx(sch, idx);
293 goto congestion_drop;
296 /* Queue is large, always mark/drop */
297 if (p->qavg > p->qth_max) {
300 sch->qstats.overlimits++;
301 if (use_harddrop(q) || !use_ecn(q) ||
302 !INET_ECN_set_ce(skb)) {
303 q->stats.forced_drop++;
304 goto congestion_drop;
307 q->stats.forced_mark++;
308 } else if (++p->qcount) {
309 if (red_mark_probability(p, p->qavg)) {
311 p->qR = red_random(p);
313 sch->qstats.overlimits++;
314 if (!use_ecn(q) || !INET_ECN_set_ce(skb)) {
315 q->stats.prob_drop++;
316 goto congestion_drop;
319 q->stats.prob_mark++;
322 p->qR = red_random(p);
325 /* Admit new packet */
326 if (sch->q.qlen < q->limit) {
327 q->tab[q->tail] = skb;
328 q->tail = (q->tail + 1) & q->tab_mask;
330 sch->qstats.backlog += qdisc_pkt_len(skb);
331 return NET_XMIT_SUCCESS;
337 return NET_XMIT_DROP;
340 qdisc_drop(skb, sch);
344 if (ret & __NET_XMIT_BYPASS)
350 static struct sk_buff *choke_dequeue(struct Qdisc *sch)
352 struct choke_sched_data *q = qdisc_priv(sch);
355 if (q->head == q->tail) {
356 if (!red_is_idling(&q->parms))
357 red_start_of_idle_period(&q->parms);
361 skb = q->tab[q->head];
362 q->tab[q->head] = NULL;
363 choke_zap_head_holes(q);
365 sch->qstats.backlog -= qdisc_pkt_len(skb);
366 qdisc_bstats_update(sch, skb);
371 static unsigned int choke_drop(struct Qdisc *sch)
373 struct choke_sched_data *q = qdisc_priv(sch);
376 len = qdisc_queue_drop(sch);
380 if (!red_is_idling(&q->parms))
381 red_start_of_idle_period(&q->parms);
387 static void choke_reset(struct Qdisc *sch)
389 struct choke_sched_data *q = qdisc_priv(sch);
391 red_restart(&q->parms);
394 static const struct nla_policy choke_policy[TCA_CHOKE_MAX + 1] = {
395 [TCA_CHOKE_PARMS] = { .len = sizeof(struct tc_red_qopt) },
396 [TCA_CHOKE_STAB] = { .len = RED_STAB_SIZE },
400 static void choke_free(void *addr)
403 if (is_vmalloc_addr(addr))
410 static int choke_change(struct Qdisc *sch, struct nlattr *opt)
412 struct choke_sched_data *q = qdisc_priv(sch);
413 struct nlattr *tb[TCA_CHOKE_MAX + 1];
414 const struct tc_red_qopt *ctl;
416 struct sk_buff **old = NULL;
422 err = nla_parse_nested(tb, TCA_CHOKE_MAX, opt, choke_policy);
426 if (tb[TCA_CHOKE_PARMS] == NULL ||
427 tb[TCA_CHOKE_STAB] == NULL)
430 ctl = nla_data(tb[TCA_CHOKE_PARMS]);
432 if (ctl->limit > CHOKE_MAX_QUEUE)
435 mask = roundup_pow_of_two(ctl->limit + 1) - 1;
436 if (mask != q->tab_mask) {
437 struct sk_buff **ntab;
439 ntab = kcalloc(mask + 1, sizeof(struct sk_buff *), GFP_KERNEL);
441 ntab = vzalloc((mask + 1) * sizeof(struct sk_buff *));
448 unsigned int oqlen = sch->q.qlen, tail = 0;
450 while (q->head != q->tail) {
451 struct sk_buff *skb = q->tab[q->head];
453 q->head = (q->head + 1) & q->tab_mask;
460 sch->qstats.backlog -= qdisc_pkt_len(skb);
462 qdisc_drop(skb, sch);
464 qdisc_tree_decrease_qlen(sch, oqlen - sch->q.qlen);
474 q->flags = ctl->flags;
475 q->limit = ctl->limit;
477 red_set_parms(&q->parms, ctl->qth_min, ctl->qth_max, ctl->Wlog,
478 ctl->Plog, ctl->Scell_log,
479 nla_data(tb[TCA_CHOKE_STAB]));
481 if (q->head == q->tail)
482 red_end_of_idle_period(&q->parms);
484 sch_tree_unlock(sch);
489 static int choke_init(struct Qdisc *sch, struct nlattr *opt)
491 return choke_change(sch, opt);
494 static int choke_dump(struct Qdisc *sch, struct sk_buff *skb)
496 struct choke_sched_data *q = qdisc_priv(sch);
497 struct nlattr *opts = NULL;
498 struct tc_red_qopt opt = {
501 .qth_min = q->parms.qth_min >> q->parms.Wlog,
502 .qth_max = q->parms.qth_max >> q->parms.Wlog,
503 .Wlog = q->parms.Wlog,
504 .Plog = q->parms.Plog,
505 .Scell_log = q->parms.Scell_log,
508 opts = nla_nest_start(skb, TCA_OPTIONS);
510 goto nla_put_failure;
512 NLA_PUT(skb, TCA_CHOKE_PARMS, sizeof(opt), &opt);
513 return nla_nest_end(skb, opts);
516 nla_nest_cancel(skb, opts);
520 static int choke_dump_stats(struct Qdisc *sch, struct gnet_dump *d)
522 struct choke_sched_data *q = qdisc_priv(sch);
523 struct tc_choke_xstats st = {
524 .early = q->stats.prob_drop + q->stats.forced_drop,
525 .marked = q->stats.prob_mark + q->stats.forced_mark,
526 .pdrop = q->stats.pdrop,
527 .other = q->stats.other,
528 .matched = q->stats.matched,
531 return gnet_stats_copy_app(d, &st, sizeof(st));
534 static void choke_destroy(struct Qdisc *sch)
536 struct choke_sched_data *q = qdisc_priv(sch);
538 tcf_destroy_chain(&q->filter_list);
542 static struct Qdisc *choke_leaf(struct Qdisc *sch, unsigned long arg)
547 static unsigned long choke_get(struct Qdisc *sch, u32 classid)
552 static void choke_put(struct Qdisc *q, unsigned long cl)
556 static unsigned long choke_bind(struct Qdisc *sch, unsigned long parent,
562 static struct tcf_proto **choke_find_tcf(struct Qdisc *sch, unsigned long cl)
564 struct choke_sched_data *q = qdisc_priv(sch);
568 return &q->filter_list;
571 static int choke_dump_class(struct Qdisc *sch, unsigned long cl,
572 struct sk_buff *skb, struct tcmsg *tcm)
574 tcm->tcm_handle |= TC_H_MIN(cl);
578 static void choke_walk(struct Qdisc *sch, struct qdisc_walker *arg)
581 if (arg->fn(sch, 1, arg) < 0) {
589 static const struct Qdisc_class_ops choke_class_ops = {
593 .tcf_chain = choke_find_tcf,
594 .bind_tcf = choke_bind,
595 .unbind_tcf = choke_put,
596 .dump = choke_dump_class,
600 static struct sk_buff *choke_peek_head(struct Qdisc *sch)
602 struct choke_sched_data *q = qdisc_priv(sch);
604 return (q->head != q->tail) ? q->tab[q->head] : NULL;
607 static struct Qdisc_ops choke_qdisc_ops __read_mostly = {
609 .priv_size = sizeof(struct choke_sched_data),
611 .enqueue = choke_enqueue,
612 .dequeue = choke_dequeue,
613 .peek = choke_peek_head,
616 .destroy = choke_destroy,
617 .reset = choke_reset,
618 .change = choke_change,
620 .dump_stats = choke_dump_stats,
621 .owner = THIS_MODULE,
624 static int __init choke_module_init(void)
626 return register_qdisc(&choke_qdisc_ops);
629 static void __exit choke_module_exit(void)
631 unregister_qdisc(&choke_qdisc_ops);
634 module_init(choke_module_init)
635 module_exit(choke_module_exit)
637 MODULE_LICENSE("GPL");