net/sched/sch_gred.c

   1 /*
   2  * net/sched/sch_gred.c Generic Random Early Detection queue.
   3  *
   4  *
   5  *              This program is free software; you can redistribute it and/or
   6  *              modify it under the terms of the GNU General Public License
   7  *              as published by the Free Software Foundation; either version
   8  *              2 of the License, or (at your option) any later version.
   9  *
  10  * Authors:    J Hadi Salim (hadi@cyberus.ca) 1998-2002
  11  *
  12  *             991129: -  Bug fix with grio mode
  13  *                     - a better sing. AvgQ mode with Grio(WRED)
  14  *                     - A finer grained VQ dequeue based on sugestion
  15  *                       from Ren Liu
  16  *                     - More error checks
  17  *
  18  *
  19  *
  20  *  For all the glorious comments look at Alexey's sch_red.c
  21  */
  22
  23 #include <linux/config.h>
  24 #include <linux/module.h>
  25 #include <asm/uaccess.h>
  26 #include <asm/system.h>
  27 #include <linux/bitops.h>
  28 #include <linux/types.h>
  29 #include <linux/kernel.h>
  30 #include <linux/sched.h>
  31 #include <linux/string.h>
  32 #include <linux/mm.h>
  33 #include <linux/socket.h>
  34 #include <linux/sockios.h>
  35 #include <linux/in.h>
  36 #include <linux/errno.h>
  37 #include <linux/interrupt.h>
  38 #include <linux/if_ether.h>
  39 #include <linux/inet.h>
  40 #include <linux/netdevice.h>
  41 #include <linux/etherdevice.h>
  42 #include <linux/notifier.h>
  43 #include <net/ip.h>
  44 #include <net/route.h>
  45 #include <linux/skbuff.h>
  46 #include <net/sock.h>
  47 #include <net/pkt_sched.h>
  48
  49 #if 1 /* control */
  50 #define DPRINTK(format,args...) printk(KERN_DEBUG format,##args)
  51 #else
  52 #define DPRINTK(format,args...)
  53 #endif
  54
  55 #if 0 /* data */
  56 #define D2PRINTK(format,args...) printk(KERN_DEBUG format,##args)
  57 #else
  58 #define D2PRINTK(format,args...)
  59 #endif
  60
  61 struct gred_sched_data;
  62 struct gred_sched;
  63
  64 struct gred_sched_data
  65 {
  66 /* Parameters */
  67         u32             limit;          /* HARD maximal queue length    */
  68         u32             qth_min;        /* Min average length threshold: A scaled */
  69         u32             qth_max;        /* Max average length threshold: A scaled */
  70         u32             DP;             /* the drop pramaters */
  71         char            Wlog;           /* log(W)               */
  72         char            Plog;           /* random number bits   */
  73         u32             Scell_max;
  74         u32             Rmask;
  75         u32             bytesin;        /* bytes seen on virtualQ so far*/
  76         u32             packetsin;      /* packets seen on virtualQ so far*/
  77         u32             backlog;        /* bytes on the virtualQ */
  78         u32             forced; /* packets dropped for exceeding limits */
  79         u32             early;  /* packets dropped as a warning */
  80         u32             other;  /* packets dropped by invoking drop() */
  81         u32             pdrop;  /* packets dropped because we exceeded physical queue limits */
  82         char            Scell_log;
  83         u8              Stab[256];
  84         u8              prio;        /* the prio of this vq */
  85
  86 /* Variables */
  87         unsigned long   qave;           /* Average queue length: A scaled */
  88         int             qcount;         /* Packets since last random number generation */
  89         u32             qR;             /* Cached random number */
  90
  91         psched_time_t   qidlestart;     /* Start of idle period */
  92 };
  93
  94 struct gred_sched
  95 {
  96         struct gred_sched_data *tab[MAX_DPs];
  97         u32             DPs;
  98         u32             def;
  99         u8              initd;
 100         u8              grio;
 101         u8              eqp;
 102 };
 103
 104 static int
 105 gred_enqueue(struct sk_buff *skb, struct Qdisc* sch)
 106 {
 107         psched_time_t now;
 108         struct gred_sched_data *q=NULL;
 109         struct gred_sched *t= qdisc_priv(sch);
 110         unsigned long   qave=0;
 111         int i=0;
 112
 113         if (!t->initd && skb_queue_len(&sch->q) < (sch->dev->tx_queue_len ? : 1)) {
 114                 D2PRINTK("NO GRED Queues setup yet! Enqueued anyway\n");
 115                 goto do_enqueue;
 116         }
 117
 118
 119         if ( ((skb->tc_index&0xf) > (t->DPs -1)) || !(q=t->tab[skb->tc_index&0xf])) {
 120                 printk("GRED: setting to default (%d)\n ",t->def);
 121                 if (!(q=t->tab[t->def])) {
 122                         DPRINTK("GRED: setting to default FAILED! dropping!! "
 123                             "(%d)\n ", t->def);
 124                         goto drop;
 125                 }
 126                 /* fix tc_index? --could be controvesial but needed for
 127                    requeueing */
 128                 skb->tc_index=(skb->tc_index&0xfffffff0) | t->def;
 129         }
 130
 131         D2PRINTK("gred_enqueue virtualQ 0x%x classid %x backlog %d "
 132             "general backlog %d\n",skb->tc_index&0xf,sch->handle,q->backlog,
 133             sch->qstats.backlog);
 134         /* sum up all the qaves of prios <= to ours to get the new qave*/
 135         if (!t->eqp && t->grio) {
 136                 for (i=0;i<t->DPs;i++) {
 137                         if ((!t->tab[i]) || (i==q->DP))
 138                                 continue;
 139
 140                         if ((t->tab[i]->prio < q->prio) && (PSCHED_IS_PASTPERFECT(t->tab[i]->qidlestart)))
 141                                 qave +=t->tab[i]->qave;
 142                 }
 143
 144         }
 145
 146         q->packetsin++;
 147         q->bytesin+=skb->len;
 148
 149         if (t->eqp && t->grio) {
 150                 qave=0;
 151                 q->qave=t->tab[t->def]->qave;
 152                 q->qidlestart=t->tab[t->def]->qidlestart;
 153         }
 154
 155         if (!PSCHED_IS_PASTPERFECT(q->qidlestart)) {
 156                 long us_idle;
 157                 PSCHED_GET_TIME(now);
 158                 us_idle = PSCHED_TDIFF_SAFE(now, q->qidlestart, q->Scell_max);
 159                 PSCHED_SET_PASTPERFECT(q->qidlestart);
 160
 161                 q->qave >>= q->Stab[(us_idle>>q->Scell_log)&0xFF];
 162         } else {
 163                 if (t->eqp) {
 164                         q->qave += sch->qstats.backlog - (q->qave >> q->Wlog);
 165                 } else {
 166                         q->qave += q->backlog - (q->qave >> q->Wlog);
 167                 }
 168
 169         }
 170
 171
 172         if (t->eqp && t->grio)
 173                 t->tab[t->def]->qave=q->qave;
 174
 175         if ((q->qave+qave) < q->qth_min) {
 176                 q->qcount = -1;
 177 enqueue:
 178                 if (q->backlog + skb->len <= q->limit) {
 179                         q->backlog += skb->len;
 180 do_enqueue:
 181                         __skb_queue_tail(&sch->q, skb);
 182                         sch->qstats.backlog += skb->len;
 183                         sch->bstats.bytes += skb->len;
 184                         sch->bstats.packets++;
 185                         return 0;
 186                 } else {
 187                         q->pdrop++;
 188                 }
 189
 190 drop:
 191                 kfree_skb(skb);
 192                 sch->qstats.drops++;
 193                 return NET_XMIT_DROP;
 194         }
 195         if ((q->qave+qave) >= q->qth_max) {
 196                 q->qcount = -1;
 197                 sch->qstats.overlimits++;
 198                 q->forced++;
 199                 goto drop;
 200         }
 201         if (++q->qcount) {
 202                 if ((((qave+q->qave) - q->qth_min)>>q->Wlog)*q->qcount < q->qR)
 203                         goto enqueue;
 204                 q->qcount = 0;
 205                 q->qR = net_random()&q->Rmask;
 206                 sch->qstats.overlimits++;
 207                 q->early++;
 208                 goto drop;
 209         }
 210         q->qR = net_random()&q->Rmask;
 211         goto enqueue;
 212 }
 213
 214 static int
 215 gred_requeue(struct sk_buff *skb, struct Qdisc* sch)
 216 {
 217         struct gred_sched_data *q;
 218         struct gred_sched *t= qdisc_priv(sch);
 219         q= t->tab[(skb->tc_index&0xf)];
 220 /* error checking here -- probably unnecessary */
 221         PSCHED_SET_PASTPERFECT(q->qidlestart);
 222
 223         __skb_queue_head(&sch->q, skb);
 224         sch->qstats.backlog += skb->len;
 225         sch->qstats.requeues++;
 226         q->backlog += skb->len;
 227         return 0;
 228 }
 229
 230 static struct sk_buff *
 231 gred_dequeue(struct Qdisc* sch)
 232 {
 233         struct sk_buff *skb;
 234         struct gred_sched_data *q;
 235         struct gred_sched *t= qdisc_priv(sch);
 236
 237         skb = __skb_dequeue(&sch->q);
 238         if (skb) {
 239                 sch->qstats.backlog -= skb->len;
 240                 q= t->tab[(skb->tc_index&0xf)];
 241                 if (q) {
 242                         q->backlog -= skb->len;
 243                         if (!q->backlog && !t->eqp)
 244                                 PSCHED_GET_TIME(q->qidlestart);
 245                 } else {
 246                         D2PRINTK("gred_dequeue: skb has bad tcindex %x\n",skb->tc_index&0xf);
 247                 }
 248                 return skb;
 249         }
 250
 251         if (t->eqp) {
 252                         q= t->tab[t->def];
 253                         if (!q)
 254                                 D2PRINTK("no default VQ set: Results will be "
 255                                        "screwed up\n");
 256                         else
 257                                 PSCHED_GET_TIME(q->qidlestart);
 258         }
 259
 260         return NULL;
 261 }
 262
 263 static unsigned int gred_drop(struct Qdisc* sch)
 264 {
 265         struct sk_buff *skb;
 266
 267         struct gred_sched_data *q;
 268         struct gred_sched *t= qdisc_priv(sch);
 269
 270         skb = __skb_dequeue_tail(&sch->q);
 271         if (skb) {
 272                 unsigned int len = skb->len;
 273                 sch->qstats.backlog -= len;
 274                 sch->qstats.drops++;
 275                 q= t->tab[(skb->tc_index&0xf)];
 276                 if (q) {
 277                         q->backlog -= len;
 278                         q->other++;
 279                         if (!q->backlog && !t->eqp)
 280                                 PSCHED_GET_TIME(q->qidlestart);
 281                 } else {
 282                         D2PRINTK("gred_dequeue: skb has bad tcindex %x\n",skb->tc_index&0xf);
 283                 }
 284
 285                 kfree_skb(skb);
 286                 return len;
 287         }
 288
 289         q=t->tab[t->def];
 290         if (!q) {
 291                 D2PRINTK("no default VQ set: Results might be screwed up\n");
 292                 return 0;
 293         }
 294
 295         PSCHED_GET_TIME(q->qidlestart);
 296         return 0;
 297
 298 }
 299
 300 static void gred_reset(struct Qdisc* sch)
 301 {
 302         int i;
 303         struct gred_sched_data *q;
 304         struct gred_sched *t= qdisc_priv(sch);
 305
 306         __skb_queue_purge(&sch->q);
 307
 308         sch->qstats.backlog = 0;
 309
 310         for (i=0;i<t->DPs;i++) {
 311                 q= t->tab[i];
 312                 if (!q)
 313                         continue;
 314                 PSCHED_SET_PASTPERFECT(q->qidlestart);
 315                 q->qave = 0;
 316                 q->qcount = -1;
 317                 q->backlog = 0;
 318                 q->other=0;
 319                 q->forced=0;
 320                 q->pdrop=0;
 321                 q->early=0;
 322         }
 323 }
 324
 325 static int gred_change(struct Qdisc *sch, struct rtattr *opt)
 326 {
 327         struct gred_sched *table = qdisc_priv(sch);
 328         struct gred_sched_data *q;
 329         struct tc_gred_qopt *ctl;
 330         struct tc_gred_sopt *sopt;
 331         struct rtattr *tb[TCA_GRED_STAB];
 332         struct rtattr *tb2[TCA_GRED_DPS];
 333         int i;
 334
 335         if (opt == NULL ||
 336                 rtattr_parse(tb, TCA_GRED_STAB, RTA_DATA(opt), RTA_PAYLOAD(opt)) )
 337                         return -EINVAL;
 338
 339         if (tb[TCA_GRED_PARMS-1] == 0 && tb[TCA_GRED_STAB-1] == 0) {
 340                 rtattr_parse(tb2, TCA_GRED_DPS, RTA_DATA(opt),
 341                     RTA_PAYLOAD(opt));
 342
 343             if (tb2[TCA_GRED_DPS-1] == 0)
 344                         return -EINVAL;
 345
 346                 sopt = RTA_DATA(tb2[TCA_GRED_DPS-1]);
 347                 table->DPs=sopt->DPs;
 348                 table->def=sopt->def_DP;
 349                 table->grio=sopt->grio;
 350                 table->initd=0;
 351                 /* probably need to clear all the table DP entries as well */
 352                 return 0;
 353             }
 354
 355
 356         if (!table->DPs || tb[TCA_GRED_PARMS-1] == 0 || tb[TCA_GRED_STAB-1] == 0 ||
 357                 RTA_PAYLOAD(tb[TCA_GRED_PARMS-1]) < sizeof(*ctl) ||
 358                 RTA_PAYLOAD(tb[TCA_GRED_STAB-1]) < 256)
 359                         return -EINVAL;
 360
 361         ctl = RTA_DATA(tb[TCA_GRED_PARMS-1]);
 362         if (ctl->DP > MAX_DPs-1 ) {
 363                 /* misbehaving is punished! Put in the default drop probability */
 364                 DPRINTK("\nGRED: DP %u not in  the proper range fixed. New DP "
 365                         "set to default at %d\n",ctl->DP,table->def);
 366                 ctl->DP=table->def;
 367         }
 368
 369         if (table->tab[ctl->DP] == NULL) {
 370                 table->tab[ctl->DP]=kmalloc(sizeof(struct gred_sched_data),
 371                                             GFP_KERNEL);
 372                 if (NULL == table->tab[ctl->DP])
 373                         return -ENOMEM;
 374                 memset(table->tab[ctl->DP], 0, (sizeof(struct gred_sched_data)));
 375         }
 376         q= table->tab[ctl->DP];
 377
 378         if (table->grio) {
 379                 if (ctl->prio <=0) {
 380                         if (table->def && table->tab[table->def]) {
 381                                 DPRINTK("\nGRED: DP %u does not have a prio"
 382                                         "setting default to %d\n",ctl->DP,
 383                                         table->tab[table->def]->prio);
 384                                 q->prio=table->tab[table->def]->prio;
 385                         } else {
 386                                 DPRINTK("\nGRED: DP %u does not have a prio"
 387                                         " setting default to 8\n",ctl->DP);
 388                                 q->prio=8;
 389                         }
 390                 } else {
 391                         q->prio=ctl->prio;
 392                 }
 393         } else {
 394                 q->prio=8;
 395         }
 396
 397
 398         q->DP=ctl->DP;
 399         q->Wlog = ctl->Wlog;
 400         q->Plog = ctl->Plog;
 401         q->limit = ctl->limit;
 402         q->Scell_log = ctl->Scell_log;
 403         q->Rmask = ctl->Plog < 32 ? ((1<<ctl->Plog) - 1) : ~0UL;
 404         q->Scell_max = (255<<q->Scell_log);
 405         q->qth_min = ctl->qth_min<<ctl->Wlog;
 406         q->qth_max = ctl->qth_max<<ctl->Wlog;
 407         q->qave=0;
 408         q->backlog=0;
 409         q->qcount = -1;
 410         q->other=0;
 411         q->forced=0;
 412         q->pdrop=0;
 413         q->early=0;
 414
 415         PSCHED_SET_PASTPERFECT(q->qidlestart);
 416         memcpy(q->Stab, RTA_DATA(tb[TCA_GRED_STAB-1]), 256);
 417
 418         if ( table->initd && table->grio) {
 419         /* this looks ugly but it's not in the fast path */
 420                 for (i=0;i<table->DPs;i++) {
 421                         if ((!table->tab[i]) || (i==q->DP) )
 422                                 continue;
 423                         if (table->tab[i]->prio == q->prio ){
 424                                 /* WRED mode detected */
 425                                 table->eqp=1;
 426                                 break;
 427                         }
 428                 }
 429         }
 430
 431         if (!table->initd) {
 432                 table->initd=1;
 433                 /*
 434                 the first entry also goes into the default until
 435                 over-written
 436                 */
 437
 438                 if (table->tab[table->def] == NULL) {
 439                         table->tab[table->def]=
 440                                 kmalloc(sizeof(struct gred_sched_data), GFP_KERNEL);
 441                         if (NULL == table->tab[table->def])
 442                                 return -ENOMEM;
 443
 444                         memset(table->tab[table->def], 0,
 445                                (sizeof(struct gred_sched_data)));
 446                 }
 447                 q= table->tab[table->def];
 448                 q->DP=table->def;
 449                 q->Wlog = ctl->Wlog;
 450                 q->Plog = ctl->Plog;
 451                 q->limit = ctl->limit;
 452                 q->Scell_log = ctl->Scell_log;
 453                 q->Rmask = ctl->Plog < 32 ? ((1<<ctl->Plog) - 1) : ~0UL;
 454                 q->Scell_max = (255<<q->Scell_log);
 455                 q->qth_min = ctl->qth_min<<ctl->Wlog;
 456                 q->qth_max = ctl->qth_max<<ctl->Wlog;
 457
 458                 if (table->grio)
 459                         q->prio=table->tab[ctl->DP]->prio;
 460                 else
 461                         q->prio=8;
 462
 463                 q->qcount = -1;
 464                 PSCHED_SET_PASTPERFECT(q->qidlestart);
 465                 memcpy(q->Stab, RTA_DATA(tb[TCA_GRED_STAB-1]), 256);
 466         }
 467         return 0;
 468
 469 }
 470
 471 static int gred_init(struct Qdisc *sch, struct rtattr *opt)
 472 {
 473         struct gred_sched *table = qdisc_priv(sch);
 474         struct tc_gred_sopt *sopt;
 475         struct rtattr *tb[TCA_GRED_STAB];
 476         struct rtattr *tb2[TCA_GRED_DPS];
 477
 478         if (opt == NULL ||
 479                 rtattr_parse(tb, TCA_GRED_STAB, RTA_DATA(opt), RTA_PAYLOAD(opt)) )
 480                         return -EINVAL;
 481
 482         if (tb[TCA_GRED_PARMS-1] == 0 && tb[TCA_GRED_STAB-1] == 0) {
 483                 rtattr_parse(tb2, TCA_GRED_DPS, RTA_DATA(opt),RTA_PAYLOAD(opt));
 484
 485             if (tb2[TCA_GRED_DPS-1] == 0)
 486                         return -EINVAL;
 487
 488                 sopt = RTA_DATA(tb2[TCA_GRED_DPS-1]);
 489                 table->DPs=sopt->DPs;
 490                 table->def=sopt->def_DP;
 491                 table->grio=sopt->grio;
 492                 table->initd=0;
 493                 return 0;
 494         }
 495
 496         DPRINTK("\n GRED_INIT error!\n");
 497         return -EINVAL;
 498 }
 499
 500 static int gred_dump(struct Qdisc *sch, struct sk_buff *skb)
 501 {
 502         unsigned long qave;
 503         struct rtattr *rta;
 504         struct tc_gred_qopt *opt = NULL ;
 505         struct tc_gred_qopt *dst;
 506         struct gred_sched *table = qdisc_priv(sch);
 507         struct gred_sched_data *q;
 508         int i;
 509         unsigned char    *b = skb->tail;
 510
 511         rta = (struct rtattr*)b;
 512         RTA_PUT(skb, TCA_OPTIONS, 0, NULL);
 513
 514         opt=kmalloc(sizeof(struct tc_gred_qopt)*MAX_DPs, GFP_KERNEL);
 515
 516         if (opt  == NULL) {
 517                 DPRINTK("gred_dump:failed to malloc for %Zd\n",
 518                     sizeof(struct tc_gred_qopt)*MAX_DPs);
 519                 goto rtattr_failure;
 520         }
 521
 522         memset(opt, 0, (sizeof(struct tc_gred_qopt))*table->DPs);
 523
 524         if (!table->initd) {
 525                 DPRINTK("NO GRED Queues setup!\n");
 526         }
 527
 528         for (i=0;i<MAX_DPs;i++) {
 529                 dst= &opt[i];
 530                 q= table->tab[i];
 531
 532                 if (!q) {
 533                         /* hack -- fix at some point with proper message
 534                            This is how we indicate to tc that there is no VQ
 535                            at this DP */
 536
 537                         dst->DP=MAX_DPs+i;
 538                         continue;
 539                 }
 540
 541                 dst->limit=q->limit;
 542                 dst->qth_min=q->qth_min>>q->Wlog;
 543                 dst->qth_max=q->qth_max>>q->Wlog;
 544                 dst->DP=q->DP;
 545                 dst->backlog=q->backlog;
 546                 if (q->qave) {
 547                         if (table->eqp && table->grio) {
 548                                 q->qidlestart=table->tab[table->def]->qidlestart;
 549                                 q->qave=table->tab[table->def]->qave;
 550                         }
 551                         if (!PSCHED_IS_PASTPERFECT(q->qidlestart)) {
 552                                 long idle;
 553                                 psched_time_t now;
 554                                 PSCHED_GET_TIME(now);
 555                                 idle = PSCHED_TDIFF_SAFE(now, q->qidlestart, q->Scell_max);
 556                                 qave  = q->qave >> q->Stab[(idle>>q->Scell_log)&0xFF];
 557                                 dst->qave = qave >> q->Wlog;
 558
 559                         } else {
 560                                 dst->qave = q->qave >> q->Wlog;
 561                         }
 562                 } else {
 563                         dst->qave = 0;
 564                 }
 565
 566
 567                 dst->Wlog = q->Wlog;
 568                 dst->Plog = q->Plog;
 569                 dst->Scell_log = q->Scell_log;
 570                 dst->other = q->other;
 571                 dst->forced = q->forced;
 572                 dst->early = q->early;
 573                 dst->pdrop = q->pdrop;
 574                 dst->prio = q->prio;
 575                 dst->packets=q->packetsin;
 576                 dst->bytesin=q->bytesin;
 577         }
 578
 579         RTA_PUT(skb, TCA_GRED_PARMS, sizeof(struct tc_gred_qopt)*MAX_DPs, opt);
 580         rta->rta_len = skb->tail - b;
 581
 582         kfree(opt);
 583         return skb->len;
 584
 585 rtattr_failure:
 586         if (opt)
 587                 kfree(opt);
 588         DPRINTK("gred_dump: FAILURE!!!!\n");
 589
 590 /* also free the opt struct here */
 591         skb_trim(skb, b - skb->data);
 592         return -1;
 593 }
 594
 595 static void gred_destroy(struct Qdisc *sch)
 596 {
 597         struct gred_sched *table = qdisc_priv(sch);
 598         int i;
 599
 600         for (i = 0;i < table->DPs; i++) {
 601                 if (table->tab[i])
 602                         kfree(table->tab[i]);
 603         }
 604 }
 605
 606 static struct Qdisc_ops gred_qdisc_ops = {
 607         .next           =       NULL,
 608         .cl_ops         =       NULL,
 609         .id             =       "gred",
 610         .priv_size      =       sizeof(struct gred_sched),
 611         .enqueue        =       gred_enqueue,
 612         .dequeue        =       gred_dequeue,
 613         .requeue        =       gred_requeue,
 614         .drop           =       gred_drop,
 615         .init           =       gred_init,
 616         .reset          =       gred_reset,
 617         .destroy        =       gred_destroy,
 618         .change         =       gred_change,
 619         .dump           =       gred_dump,
 620         .owner          =       THIS_MODULE,
 621 };
 622
 623 static int __init gred_module_init(void)
 624 {
 625         return register_qdisc(&gred_qdisc_ops);
 626 }
 627 static void __exit gred_module_exit(void)
 628 {
 629         unregister_qdisc(&gred_qdisc_ops);
 630 }
 631 module_init(gred_module_init)
 632 module_exit(gred_module_exit)
 633 MODULE_LICENSE("GPL");