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