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 ((ip1->frag_off | ip2->frag_off) & htons(IP_MF | IP_OFFSET))
 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 (ctl->limit > CHOKE_MAX_QUEUE)
 483                 return -EINVAL;
 484
 485         mask = roundup_pow_of_two(ctl->limit + 1) - 1;
 486         if (mask != q->tab_mask) {
 487                 struct sk_buff **ntab;
 488
 489                 ntab = kcalloc(mask + 1, sizeof(struct sk_buff *), GFP_KERNEL);
 490                 if (!ntab)
 491                         ntab = vzalloc((mask + 1) * sizeof(struct sk_buff *));
 492                 if (!ntab)
 493                         return -ENOMEM;
 494
 495                 sch_tree_lock(sch);
 496                 old = q->tab;
 497                 if (old) {
 498                         unsigned int oqlen = sch->q.qlen, tail = 0;
 499
 500                         while (q->head != q->tail) {
 501                                 struct sk_buff *skb = q->tab[q->head];
 502
 503                                 q->head = (q->head + 1) & q->tab_mask;
 504                                 if (!skb)
 505                                         continue;
 506                                 if (tail < mask) {
 507                                         ntab[tail++] = skb;
 508                                         continue;
 509                                 }
 510                                 sch->qstats.backlog -= qdisc_pkt_len(skb);
 511                                 --sch->q.qlen;
 512                                 qdisc_drop(skb, sch);
 513                         }
 514                         qdisc_tree_decrease_qlen(sch, oqlen - sch->q.qlen);
 515                         q->head = 0;
 516                         q->tail = tail;
 517                 }
 518
 519                 q->tab_mask = mask;
 520                 q->tab = ntab;
 521         } else
 522                 sch_tree_lock(sch);
 523
 524         q->flags = ctl->flags;
 525         q->limit = ctl->limit;
 526
 527         red_set_parms(&q->parms, ctl->qth_min, ctl->qth_max, ctl->Wlog,
 528                       ctl->Plog, ctl->Scell_log,
 529                       nla_data(tb[TCA_CHOKE_STAB]));
 530
 531         if (q->head == q->tail)
 532                 red_end_of_idle_period(&q->parms);
 533
 534         sch_tree_unlock(sch);
 535         choke_free(old);
 536         return 0;
 537 }
 538
 539 static int choke_init(struct Qdisc *sch, struct nlattr *opt)
 540 {
 541         return choke_change(sch, opt);
 542 }
 543
 544 static int choke_dump(struct Qdisc *sch, struct sk_buff *skb)
 545 {
 546         struct choke_sched_data *q = qdisc_priv(sch);
 547         struct nlattr *opts = NULL;
 548         struct tc_red_qopt opt = {
 549                 .limit          = q->limit,
 550                 .flags          = q->flags,
 551                 .qth_min        = q->parms.qth_min >> q->parms.Wlog,
 552                 .qth_max        = q->parms.qth_max >> q->parms.Wlog,
 553                 .Wlog           = q->parms.Wlog,
 554                 .Plog           = q->parms.Plog,
 555                 .Scell_log      = q->parms.Scell_log,
 556         };
 557
 558         opts = nla_nest_start(skb, TCA_OPTIONS);
 559         if (opts == NULL)
 560                 goto nla_put_failure;
 561
 562         NLA_PUT(skb, TCA_CHOKE_PARMS, sizeof(opt), &opt);
 563         return nla_nest_end(skb, opts);
 564
 565 nla_put_failure:
 566         nla_nest_cancel(skb, opts);
 567         return -EMSGSIZE;
 568 }
 569
 570 static int choke_dump_stats(struct Qdisc *sch, struct gnet_dump *d)
 571 {
 572         struct choke_sched_data *q = qdisc_priv(sch);
 573         struct tc_choke_xstats st = {
 574                 .early  = q->stats.prob_drop + q->stats.forced_drop,
 575                 .marked = q->stats.prob_mark + q->stats.forced_mark,
 576                 .pdrop  = q->stats.pdrop,
 577                 .other  = q->stats.other,
 578                 .matched = q->stats.matched,
 579         };
 580
 581         return gnet_stats_copy_app(d, &st, sizeof(st));
 582 }
 583
 584 static void choke_destroy(struct Qdisc *sch)
 585 {
 586         struct choke_sched_data *q = qdisc_priv(sch);
 587
 588         tcf_destroy_chain(&q->filter_list);
 589         choke_free(q->tab);
 590 }
 591
 592 static struct Qdisc *choke_leaf(struct Qdisc *sch, unsigned long arg)
 593 {
 594         return NULL;
 595 }
 596
 597 static unsigned long choke_get(struct Qdisc *sch, u32 classid)
 598 {
 599         return 0;
 600 }
 601
 602 static void choke_put(struct Qdisc *q, unsigned long cl)
 603 {
 604 }
 605
 606 static unsigned long choke_bind(struct Qdisc *sch, unsigned long parent,
 607                                 u32 classid)
 608 {
 609         return 0;
 610 }
 611
 612 static struct tcf_proto **choke_find_tcf(struct Qdisc *sch, unsigned long cl)
 613 {
 614         struct choke_sched_data *q = qdisc_priv(sch);
 615
 616         if (cl)
 617                 return NULL;
 618         return &q->filter_list;
 619 }
 620
 621 static int choke_dump_class(struct Qdisc *sch, unsigned long cl,
 622                           struct sk_buff *skb, struct tcmsg *tcm)
 623 {
 624         tcm->tcm_handle |= TC_H_MIN(cl);
 625         return 0;
 626 }
 627
 628 static void choke_walk(struct Qdisc *sch, struct qdisc_walker *arg)
 629 {
 630         if (!arg->stop) {
 631                 if (arg->fn(sch, 1, arg) < 0) {
 632                         arg->stop = 1;
 633                         return;
 634                 }
 635                 arg->count++;
 636         }
 637 }
 638
 639 static const struct Qdisc_class_ops choke_class_ops = {
 640         .leaf           =       choke_leaf,
 641         .get            =       choke_get,
 642         .put            =       choke_put,
 643         .tcf_chain      =       choke_find_tcf,
 644         .bind_tcf       =       choke_bind,
 645         .unbind_tcf     =       choke_put,
 646         .dump           =       choke_dump_class,
 647         .walk           =       choke_walk,
 648 };
 649
 650 static struct sk_buff *choke_peek_head(struct Qdisc *sch)
 651 {
 652         struct choke_sched_data *q = qdisc_priv(sch);
 653
 654         return (q->head != q->tail) ? q->tab[q->head] : NULL;
 655 }
 656
 657 static struct Qdisc_ops choke_qdisc_ops __read_mostly = {
 658         .id             =       "choke",
 659         .priv_size      =       sizeof(struct choke_sched_data),
 660
 661         .enqueue        =       choke_enqueue,
 662         .dequeue        =       choke_dequeue,
 663         .peek           =       choke_peek_head,
 664         .drop           =       choke_drop,
 665         .init           =       choke_init,
 666         .destroy        =       choke_destroy,
 667         .reset          =       choke_reset,
 668         .change         =       choke_change,
 669         .dump           =       choke_dump,
 670         .dump_stats     =       choke_dump_stats,
 671         .owner          =       THIS_MODULE,
 672 };
 673
 674 static int __init choke_module_init(void)
 675 {
 676         return register_qdisc(&choke_qdisc_ops);
 677 }
 678
 679 static void __exit choke_module_exit(void)
 680 {
 681         unregister_qdisc(&choke_qdisc_ops);
 682 }
 683
 684 module_init(choke_module_init)
 685 module_exit(choke_module_exit)
 686
 687 MODULE_LICENSE("GPL");