net/sched/sch_choke.c

   1 // SPDX-License-Identifier: GPL-2.0-only
   2 /*
   3  * net/sched/sch_choke.c        CHOKE scheduler
   4  *
   5  * Copyright (c) 2011 Stephen Hemminger <[email protected]>
   6  * Copyright (c) 2011 Eric Dumazet <[email protected]>
   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         u8                      keys_valid;
 135         struct                  flow_keys_digest keys;
 136 };
 137
 138 static inline struct choke_skb_cb *choke_skb_cb(const struct sk_buff *skb)
 139 {
 140         qdisc_cb_private_validate(skb, sizeof(struct choke_skb_cb));
 141         return (struct choke_skb_cb *)qdisc_skb_cb(skb)->data;
 142 }
 143
 144 /*
 145  * Compare flow of two packets
 146  *  Returns true only if source and destination address and port match.
 147  *          false for special cases
 148  */
 149 static bool choke_match_flow(struct sk_buff *skb1,
 150                              struct sk_buff *skb2)
 151 {
 152         struct flow_keys temp;
 153
 154         if (skb1->protocol != skb2->protocol)
 155                 return false;
 156
 157         if (!choke_skb_cb(skb1)->keys_valid) {
 158                 choke_skb_cb(skb1)->keys_valid = 1;
 159                 skb_flow_dissect_flow_keys(skb1, &temp, 0);
 160                 make_flow_keys_digest(&choke_skb_cb(skb1)->keys, &temp);
 161         }
 162
 163         if (!choke_skb_cb(skb2)->keys_valid) {
 164                 choke_skb_cb(skb2)->keys_valid = 1;
 165                 skb_flow_dissect_flow_keys(skb2, &temp, 0);
 166                 make_flow_keys_digest(&choke_skb_cb(skb2)->keys, &temp);
 167         }
 168
 169         return !memcmp(&choke_skb_cb(skb1)->keys,
 170                        &choke_skb_cb(skb2)->keys,
 171                        sizeof(choke_skb_cb(skb1)->keys));
 172 }
 173
 174 /*
 175  * Select a packet at random from queue
 176  * HACK: since queue can have holes from previous deletion; retry several
 177  *   times to find a random skb but then just give up and return the head
 178  * Will return NULL if queue is empty (q->head == q->tail)
 179  */
 180 static struct sk_buff *choke_peek_random(const struct choke_sched_data *q,
 181                                          unsigned int *pidx)
 182 {
 183         struct sk_buff *skb;
 184         int retrys = 3;
 185
 186         do {
 187                 *pidx = (q->head + prandom_u32_max(choke_len(q))) & q->tab_mask;
 188                 skb = q->tab[*pidx];
 189                 if (skb)
 190                         return skb;
 191         } while (--retrys > 0);
 192
 193         return q->tab[*pidx = q->head];
 194 }
 195
 196 /*
 197  * Compare new packet with random packet in queue
 198  * returns true if matched and sets *pidx
 199  */
 200 static bool choke_match_random(const struct choke_sched_data *q,
 201                                struct sk_buff *nskb,
 202                                unsigned int *pidx)
 203 {
 204         struct sk_buff *oskb;
 205
 206         if (q->head == q->tail)
 207                 return false;
 208
 209         oskb = choke_peek_random(q, pidx);
 210         return choke_match_flow(oskb, nskb);
 211 }
 212
 213 static int choke_enqueue(struct sk_buff *skb, struct Qdisc *sch,
 214                          struct sk_buff **to_free)
 215 {
 216         struct choke_sched_data *q = qdisc_priv(sch);
 217         const struct red_parms *p = &q->parms;
 218
 219         choke_skb_cb(skb)->keys_valid = 0;
 220         /* Compute average queue usage (see RED) */
 221         q->vars.qavg = red_calc_qavg(p, &q->vars, sch->q.qlen);
 222         if (red_is_idling(&q->vars))
 223                 red_end_of_idle_period(&q->vars);
 224
 225         /* Is queue small? */
 226         if (q->vars.qavg <= p->qth_min)
 227                 q->vars.qcount = -1;
 228         else {
 229                 unsigned int idx;
 230
 231                 /* Draw a packet at random from queue and compare flow */
 232                 if (choke_match_random(q, skb, &idx)) {
 233                         q->stats.matched++;
 234                         choke_drop_by_idx(sch, idx, to_free);
 235                         goto congestion_drop;
 236                 }
 237
 238                 /* Queue is large, always mark/drop */
 239                 if (q->vars.qavg > p->qth_max) {
 240                         q->vars.qcount = -1;
 241
 242                         qdisc_qstats_overlimit(sch);
 243                         if (use_harddrop(q) || !use_ecn(q) ||
 244                             !INET_ECN_set_ce(skb)) {
 245                                 q->stats.forced_drop++;
 246                                 goto congestion_drop;
 247                         }
 248
 249                         q->stats.forced_mark++;
 250                 } else if (++q->vars.qcount) {
 251                         if (red_mark_probability(p, &q->vars, q->vars.qavg)) {
 252                                 q->vars.qcount = 0;
 253                                 q->vars.qR = red_random(p);
 254
 255                                 qdisc_qstats_overlimit(sch);
 256                                 if (!use_ecn(q) || !INET_ECN_set_ce(skb)) {
 257                                         q->stats.prob_drop++;
 258                                         goto congestion_drop;
 259                                 }
 260
 261                                 q->stats.prob_mark++;
 262                         }
 263                 } else
 264                         q->vars.qR = red_random(p);
 265         }
 266
 267         /* Admit new packet */
 268         if (sch->q.qlen < q->limit) {
 269                 q->tab[q->tail] = skb;
 270                 q->tail = (q->tail + 1) & q->tab_mask;
 271                 ++sch->q.qlen;
 272                 qdisc_qstats_backlog_inc(sch, skb);
 273                 return NET_XMIT_SUCCESS;
 274         }
 275
 276         q->stats.pdrop++;
 277         return qdisc_drop(skb, sch, to_free);
 278
 279 congestion_drop:
 280         qdisc_drop(skb, sch, to_free);
 281         return NET_XMIT_CN;
 282 }
 283
 284 static struct sk_buff *choke_dequeue(struct Qdisc *sch)
 285 {
 286         struct choke_sched_data *q = qdisc_priv(sch);
 287         struct sk_buff *skb;
 288
 289         if (q->head == q->tail) {
 290                 if (!red_is_idling(&q->vars))
 291                         red_start_of_idle_period(&q->vars);
 292                 return NULL;
 293         }
 294
 295         skb = q->tab[q->head];
 296         q->tab[q->head] = NULL;
 297         choke_zap_head_holes(q);
 298         --sch->q.qlen;
 299         qdisc_qstats_backlog_dec(sch, skb);
 300         qdisc_bstats_update(sch, skb);
 301
 302         return skb;
 303 }
 304
 305 static void choke_reset(struct Qdisc *sch)
 306 {
 307         struct choke_sched_data *q = qdisc_priv(sch);
 308
 309         while (q->head != q->tail) {
 310                 struct sk_buff *skb = q->tab[q->head];
 311
 312                 q->head = (q->head + 1) & q->tab_mask;
 313                 if (!skb)
 314                         continue;
 315                 rtnl_qdisc_drop(skb, sch);
 316         }
 317
 318         sch->q.qlen = 0;
 319         sch->qstats.backlog = 0;
 320         if (q->tab)
 321                 memset(q->tab, 0, (q->tab_mask + 1) * sizeof(struct sk_buff *));
 322         q->head = q->tail = 0;
 323         red_restart(&q->vars);
 324 }
 325
 326 static const struct nla_policy choke_policy[TCA_CHOKE_MAX + 1] = {
 327         [TCA_CHOKE_PARMS]       = { .len = sizeof(struct tc_red_qopt) },
 328         [TCA_CHOKE_STAB]        = { .len = RED_STAB_SIZE },
 329         [TCA_CHOKE_MAX_P]       = { .type = NLA_U32 },
 330 };
 331
 332
 333 static void choke_free(void *addr)
 334 {
 335         kvfree(addr);
 336 }
 337
 338 static int choke_change(struct Qdisc *sch, struct nlattr *opt,
 339                         struct netlink_ext_ack *extack)
 340 {
 341         struct choke_sched_data *q = qdisc_priv(sch);
 342         struct nlattr *tb[TCA_CHOKE_MAX + 1];
 343         const struct tc_red_qopt *ctl;
 344         int err;
 345         struct sk_buff **old = NULL;
 346         unsigned int mask;
 347         u32 max_P;
 348
 349         if (opt == NULL)
 350                 return -EINVAL;
 351
 352         err = nla_parse_nested_deprecated(tb, TCA_CHOKE_MAX, opt,
 353                                           choke_policy, NULL);
 354         if (err < 0)
 355                 return err;
 356
 357         if (tb[TCA_CHOKE_PARMS] == NULL ||
 358             tb[TCA_CHOKE_STAB] == NULL)
 359                 return -EINVAL;
 360
 361         max_P = tb[TCA_CHOKE_MAX_P] ? nla_get_u32(tb[TCA_CHOKE_MAX_P]) : 0;
 362
 363         ctl = nla_data(tb[TCA_CHOKE_PARMS]);
 364
 365         if (!red_check_params(ctl->qth_min, ctl->qth_max, ctl->Wlog, ctl->Scell_log))
 366                 return -EINVAL;
 367
 368         if (ctl->limit > CHOKE_MAX_QUEUE)
 369                 return -EINVAL;
 370
 371         mask = roundup_pow_of_two(ctl->limit + 1) - 1;
 372         if (mask != q->tab_mask) {
 373                 struct sk_buff **ntab;
 374
 375                 ntab = kvcalloc(mask + 1, sizeof(struct sk_buff *), GFP_KERNEL);
 376                 if (!ntab)
 377                         return -ENOMEM;
 378
 379                 sch_tree_lock(sch);
 380                 old = q->tab;
 381                 if (old) {
 382                         unsigned int oqlen = sch->q.qlen, tail = 0;
 383                         unsigned dropped = 0;
 384
 385                         while (q->head != q->tail) {
 386                                 struct sk_buff *skb = q->tab[q->head];
 387
 388                                 q->head = (q->head + 1) & q->tab_mask;
 389                                 if (!skb)
 390                                         continue;
 391                                 if (tail < mask) {
 392                                         ntab[tail++] = skb;
 393                                         continue;
 394                                 }
 395                                 dropped += qdisc_pkt_len(skb);
 396                                 qdisc_qstats_backlog_dec(sch, skb);
 397                                 --sch->q.qlen;
 398                                 rtnl_qdisc_drop(skb, sch);
 399                         }
 400                         qdisc_tree_reduce_backlog(sch, oqlen - sch->q.qlen, dropped);
 401                         q->head = 0;
 402                         q->tail = tail;
 403                 }
 404
 405                 q->tab_mask = mask;
 406                 q->tab = ntab;
 407         } else
 408                 sch_tree_lock(sch);
 409
 410         q->flags = ctl->flags;
 411         q->limit = ctl->limit;
 412
 413         red_set_parms(&q->parms, ctl->qth_min, ctl->qth_max, ctl->Wlog,
 414                       ctl->Plog, ctl->Scell_log,
 415                       nla_data(tb[TCA_CHOKE_STAB]),
 416                       max_P);
 417         red_set_vars(&q->vars);
 418
 419         if (q->head == q->tail)
 420                 red_end_of_idle_period(&q->vars);
 421
 422         sch_tree_unlock(sch);
 423         choke_free(old);
 424         return 0;
 425 }
 426
 427 static int choke_init(struct Qdisc *sch, struct nlattr *opt,
 428                       struct netlink_ext_ack *extack)
 429 {
 430         return choke_change(sch, opt, extack);
 431 }
 432
 433 static int choke_dump(struct Qdisc *sch, struct sk_buff *skb)
 434 {
 435         struct choke_sched_data *q = qdisc_priv(sch);
 436         struct nlattr *opts = NULL;
 437         struct tc_red_qopt opt = {
 438                 .limit          = q->limit,
 439                 .flags          = q->flags,
 440                 .qth_min        = q->parms.qth_min >> q->parms.Wlog,
 441                 .qth_max        = q->parms.qth_max >> q->parms.Wlog,
 442                 .Wlog           = q->parms.Wlog,
 443                 .Plog           = q->parms.Plog,
 444                 .Scell_log      = q->parms.Scell_log,
 445         };
 446
 447         opts = nla_nest_start_noflag(skb, TCA_OPTIONS);
 448         if (opts == NULL)
 449                 goto nla_put_failure;
 450
 451         if (nla_put(skb, TCA_CHOKE_PARMS, sizeof(opt), &opt) ||
 452             nla_put_u32(skb, TCA_CHOKE_MAX_P, q->parms.max_P))
 453                 goto nla_put_failure;
 454         return nla_nest_end(skb, opts);
 455
 456 nla_put_failure:
 457         nla_nest_cancel(skb, opts);
 458         return -EMSGSIZE;
 459 }
 460
 461 static int choke_dump_stats(struct Qdisc *sch, struct gnet_dump *d)
 462 {
 463         struct choke_sched_data *q = qdisc_priv(sch);
 464         struct tc_choke_xstats st = {
 465                 .early  = q->stats.prob_drop + q->stats.forced_drop,
 466                 .marked = q->stats.prob_mark + q->stats.forced_mark,
 467                 .pdrop  = q->stats.pdrop,
 468                 .other  = q->stats.other,
 469                 .matched = q->stats.matched,
 470         };
 471
 472         return gnet_stats_copy_app(d, &st, sizeof(st));
 473 }
 474
 475 static void choke_destroy(struct Qdisc *sch)
 476 {
 477         struct choke_sched_data *q = qdisc_priv(sch);
 478
 479         choke_free(q->tab);
 480 }
 481
 482 static struct sk_buff *choke_peek_head(struct Qdisc *sch)
 483 {
 484         struct choke_sched_data *q = qdisc_priv(sch);
 485
 486         return (q->head != q->tail) ? q->tab[q->head] : NULL;
 487 }
 488
 489 static struct Qdisc_ops choke_qdisc_ops __read_mostly = {
 490         .id             =       "choke",
 491         .priv_size      =       sizeof(struct choke_sched_data),
 492
 493         .enqueue        =       choke_enqueue,
 494         .dequeue        =       choke_dequeue,
 495         .peek           =       choke_peek_head,
 496         .init           =       choke_init,
 497         .destroy        =       choke_destroy,
 498         .reset          =       choke_reset,
 499         .change         =       choke_change,
 500         .dump           =       choke_dump,
 501         .dump_stats     =       choke_dump_stats,
 502         .owner          =       THIS_MODULE,
 503 };
 504
 505 static int __init choke_module_init(void)
 506 {
 507         return register_qdisc(&choke_qdisc_ops);
 508 }
 509
 510 static void __exit choke_module_exit(void)
 511 {
 512         unregister_qdisc(&choke_qdisc_ops);
 513 }
 514
 515 module_init(choke_module_init)
 516 module_exit(choke_module_exit)
 517
 518 MODULE_LICENSE("GPL");