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 <asm/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= (struct gred_sched *)sch->data;
 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->stats.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, 0);
 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->stats.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->stats.backlog += skb->len;
 183                         sch->stats.bytes += skb->len;
 184                         sch->stats.packets++;
 185                         return 0;
 186                 } else {
 187                         q->pdrop++;
 188                 }
 189
 190 drop:
 191                 kfree_skb(skb);
 192                 sch->stats.drops++;
 193                 return NET_XMIT_DROP;
 194         }
 195         if ((q->qave+qave) >= q->qth_max) {
 196                 q->qcount = -1;
 197                 sch->stats.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->stats.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= (struct gred_sched *)sch->data;
 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->stats.backlog += skb->len;
 225         q->backlog += skb->len;
 226         return 0;
 227 }
 228
 229 static struct sk_buff *
 230 gred_dequeue(struct Qdisc* sch)
 231 {
 232         struct sk_buff *skb;
 233         struct gred_sched_data *q;
 234         struct gred_sched *t= (struct gred_sched *)sch->data;
 235
 236         skb = __skb_dequeue(&sch->q);
 237         if (skb) {
 238                 sch->stats.backlog -= skb->len;
 239                 q= t->tab[(skb->tc_index&0xf)];
 240                 if (q) {
 241                         q->backlog -= skb->len;
 242                         if (!q->backlog && !t->eqp)
 243                                 PSCHED_GET_TIME(q->qidlestart);
 244                 } else {
 245                         D2PRINTK("gred_dequeue: skb has bad tcindex %x\n",skb->tc_index&0xf);
 246                 }
 247                 return skb;
 248         }
 249
 250         if (t->eqp) {
 251                         q= t->tab[t->def];
 252                         if (!q)
 253                                 D2PRINTK("no default VQ set: Results will be "
 254                                        "screwed up\n");
 255                         else
 256                                 PSCHED_GET_TIME(q->qidlestart);
 257         }
 258
 259         return NULL;
 260 }
 261
 262 static unsigned int gred_drop(struct Qdisc* sch)
 263 {
 264         struct sk_buff *skb;
 265
 266         struct gred_sched_data *q;
 267         struct gred_sched *t= (struct gred_sched *)sch->data;
 268
 269         skb = __skb_dequeue_tail(&sch->q);
 270         if (skb) {
 271                 unsigned int len = skb->len;
 272                 sch->stats.backlog -= len;
 273                 sch->stats.drops++;
 274                 q= t->tab[(skb->tc_index&0xf)];
 275                 if (q) {
 276                         q->backlog -= len;
 277                         q->other++;
 278                         if (!q->backlog && !t->eqp)
 279                                 PSCHED_GET_TIME(q->qidlestart);
 280                 } else {
 281                         D2PRINTK("gred_dequeue: skb has bad tcindex %x\n",skb->tc_index&0xf);
 282                 }
 283
 284                 kfree_skb(skb);
 285                 return len;
 286         }
 287
 288         q=t->tab[t->def];
 289         if (!q) {
 290                 D2PRINTK("no default VQ set: Results might be screwed up\n");
 291                 return 0;
 292         }
 293
 294         PSCHED_GET_TIME(q->qidlestart);
 295         return 0;
 296
 297 }
 298
 299 static void gred_reset(struct Qdisc* sch)
 300 {
 301         int i;
 302         struct gred_sched_data *q;
 303         struct gred_sched *t= (struct gred_sched *)sch->data;
 304
 305         __skb_queue_purge(&sch->q);
 306
 307         sch->stats.backlog = 0;
 308
 309         for (i=0;i<t->DPs;i++) {
 310                 q= t->tab[i];
 311                 if (!q)
 312                         continue;
 313                 PSCHED_SET_PASTPERFECT(q->qidlestart);
 314                 q->qave = 0;
 315                 q->qcount = -1;
 316                 q->backlog = 0;
 317                 q->other=0;
 318                 q->forced=0;
 319                 q->pdrop=0;
 320                 q->early=0;
 321         }
 322 }
 323
 324 static int gred_change(struct Qdisc *sch, struct rtattr *opt)
 325 {
 326         struct gred_sched *table = (struct gred_sched *)sch->data;
 327         struct gred_sched_data *q;
 328         struct tc_gred_qopt *ctl;
 329         struct tc_gred_sopt *sopt;
 330         struct rtattr *tb[TCA_GRED_STAB];
 331         struct rtattr *tb2[TCA_GRED_DPS];
 332         int i;
 333
 334         if (opt == NULL ||
 335                 rtattr_parse(tb, TCA_GRED_STAB, RTA_DATA(opt), RTA_PAYLOAD(opt)) )
 336                         return -EINVAL;
 337
 338         if (tb[TCA_GRED_PARMS-1] == 0 && tb[TCA_GRED_STAB-1] == 0) {
 339                 rtattr_parse(tb2, TCA_GRED_DPS, RTA_DATA(opt),
 340                     RTA_PAYLOAD(opt));
 341
 342                 if (tb2[TCA_GRED_DPS-1] == 0)
 343                         return -EINVAL;
 344
 345                 sopt = RTA_DATA(tb2[TCA_GRED_DPS-1]);
 346                 table->DPs=sopt->DPs;
 347                 table->def=sopt->def_DP;
 348                 table->grio=sopt->grio;
 349                 table->initd=0;
 350                 /* probably need to clear all the table DP entries as well */
 351                 MOD_INC_USE_COUNT;
 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 its 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 = (struct gred_sched *)sch->data;
 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                 MOD_INC_USE_COUNT;
 494                 return 0;
 495         }
 496
 497         DPRINTK("\n GRED_INIT error!\n");
 498         return -EINVAL;
 499 }
 500
 501 static int gred_dump(struct Qdisc *sch, struct sk_buff *skb)
 502 {
 503         unsigned long qave;
 504         struct rtattr *rta;
 505         struct tc_gred_qopt *opt = NULL ;
 506         struct tc_gred_qopt *dst;
 507         struct gred_sched *table = (struct gred_sched *)sch->data;
 508         struct gred_sched_data *q;
 509         int i;
 510         unsigned char    *b = skb->tail;
 511
 512         rta = (struct rtattr*)b;
 513         RTA_PUT(skb, TCA_OPTIONS, 0, NULL);
 514
 515         opt=kmalloc(sizeof(struct tc_gred_qopt)*MAX_DPs, GFP_KERNEL);
 516
 517         if (opt  == NULL) {
 518                 DPRINTK("gred_dump:failed to malloc for %Zd\n",
 519                     sizeof(struct tc_gred_qopt)*MAX_DPs);
 520                 goto rtattr_failure;
 521         }
 522
 523         memset(opt, 0, (sizeof(struct tc_gred_qopt))*table->DPs);
 524
 525         if (!table->initd) {
 526                 DPRINTK("NO GRED Queues setup!\n");
 527         }
 528
 529         for (i=0;i<MAX_DPs;i++) {
 530                 dst= &opt[i];
 531                 q= table->tab[i];
 532
 533                 if (!q) {
 534                         /* hack -- fix at some point with proper message
 535                            This is how we indicate to tc that there is no VQ
 536                            at this DP */
 537
 538                         dst->DP=MAX_DPs+i;
 539                         continue;
 540                 }
 541
 542                 dst->limit=q->limit;
 543                 dst->qth_min=q->qth_min>>q->Wlog;
 544                 dst->qth_max=q->qth_max>>q->Wlog;
 545                 dst->DP=q->DP;
 546                 dst->backlog=q->backlog;
 547                 if (q->qave) {
 548                         if (table->eqp && table->grio) {
 549                                 q->qidlestart=table->tab[table->def]->qidlestart;
 550                                 q->qave=table->tab[table->def]->qave;
 551                         }
 552                         if (!PSCHED_IS_PASTPERFECT(q->qidlestart)) {
 553                                 long idle;
 554                                 psched_time_t now;
 555                                 PSCHED_GET_TIME(now);
 556                                 idle = PSCHED_TDIFF_SAFE(now, q->qidlestart, q->Scell_max, 0);
 557                                 qave  = q->qave >> q->Stab[(idle>>q->Scell_log)&0xFF];
 558                                 dst->qave = qave >> q->Wlog;
 559
 560                         } else {
 561                                 dst->qave = q->qave >> q->Wlog;
 562                         }
 563                 } else {
 564                         dst->qave = 0;
 565                 }
 566
 567
 568                 dst->Wlog = q->Wlog;
 569                 dst->Plog = q->Plog;
 570                 dst->Scell_log = q->Scell_log;
 571                 dst->other = q->other;
 572                 dst->forced = q->forced;
 573                 dst->early = q->early;
 574                 dst->pdrop = q->pdrop;
 575                 dst->prio = q->prio;
 576                 dst->packets=q->packetsin;
 577                 dst->bytesin=q->bytesin;
 578         }
 579
 580         RTA_PUT(skb, TCA_GRED_PARMS, sizeof(struct tc_gred_qopt)*MAX_DPs, opt);
 581         rta->rta_len = skb->tail - b;
 582
 583         kfree(opt);
 584         return skb->len;
 585
 586 rtattr_failure:
 587         if (opt)
 588                 kfree(opt);
 589         DPRINTK("gred_dump: FAILURE!!!!\n");
 590
 591 /* also free the opt struct here */
 592         skb_trim(skb, b - skb->data);
 593         return -1;
 594 }
 595
 596 static void gred_destroy(struct Qdisc *sch)
 597 {
 598         struct gred_sched *table = (struct gred_sched *)sch->data;
 599         int i;
 600
 601         for (i = 0;i < table->DPs; i++) {
 602                 if (table->tab[i])
 603                         kfree(table->tab[i]);
 604         }
 605         MOD_DEC_USE_COUNT;
 606 }
 607
 608 struct Qdisc_ops gred_qdisc_ops =
 609 {
 610         NULL,
 611         NULL,
 612         "gred",
 613         sizeof(struct gred_sched),
 614         gred_enqueue,
 615         gred_dequeue,
 616         gred_requeue,
 617         gred_drop,
 618         gred_init,
 619         gred_reset,
 620         gred_destroy,
 621         gred_change, /* change */
 622         gred_dump,
 623 };
 624
 625
 626 #ifdef MODULE
 627 int init_module(void)
 628 {
 629         return register_qdisc(&gred_qdisc_ops);
 630 }
 631
 632 void cleanup_module(void)
 633 {
 634         unregister_qdisc(&gred_qdisc_ops);
 635 }
 636 #endif
 637 MODULE_LICENSE("GPL");