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 * For all the glorious comments look at include/net/red.h 19 */ 20 21 #include <linux/slab.h> 22 #include <linux/module.h> 23 #include <linux/types.h> 24 #include <linux/kernel.h> 25 #include <linux/skbuff.h> 26 #include <net/pkt_sched.h> 27 #include <net/red.h> 28 29 #define GRED_DEF_PRIO (MAX_DPs / 2) 30 #define GRED_VQ_MASK (MAX_DPs - 1) 31 32 struct gred_sched_data; 33 struct gred_sched; 34 35 struct gred_sched_data { 36 u32 limit; /* HARD maximal queue length */ 37 u32 DP; /* the drop parameters */ 38 u32 bytesin; /* bytes seen on virtualQ so far*/ 39 u32 packetsin; /* packets seen on virtualQ so far*/ 40 u32 backlog; /* bytes on the virtualQ */ 41 u8 prio; /* the prio of this vq */ 42 43 struct red_parms parms; 44 struct red_vars vars; 45 struct red_stats stats; 46 }; 47 48 enum { 49 GRED_WRED_MODE = 1, 50 GRED_RIO_MODE, 51 }; 52 53 struct gred_sched { 54 struct gred_sched_data *tab[MAX_DPs]; 55 unsigned long flags; 56 u32 red_flags; 57 u32 DPs; 58 u32 def; 59 struct red_vars wred_set; 60 }; 61 62 static inline int gred_wred_mode(struct gred_sched *table) 63 { 64 return test_bit(GRED_WRED_MODE, &table->flags); 65 } 66 67 static inline void gred_enable_wred_mode(struct gred_sched *table) 68 { 69 __set_bit(GRED_WRED_MODE, &table->flags); 70 } 71 72 static inline void gred_disable_wred_mode(struct gred_sched *table) 73 { 74 __clear_bit(GRED_WRED_MODE, &table->flags); 75 } 76 77 static inline int gred_rio_mode(struct gred_sched *table) 78 { 79 return test_bit(GRED_RIO_MODE, &table->flags); 80 } 81 82 static inline void gred_enable_rio_mode(struct gred_sched *table) 83 { 84 __set_bit(GRED_RIO_MODE, &table->flags); 85 } 86 87 static inline void gred_disable_rio_mode(struct gred_sched *table) 88 { 89 __clear_bit(GRED_RIO_MODE, &table->flags); 90 } 91 92 static inline int gred_wred_mode_check(struct Qdisc *sch) 93 { 94 struct gred_sched *table = qdisc_priv(sch); 95 int i; 96 97 /* Really ugly O(n^2) but shouldn't be necessary too frequent. */ 98 for (i = 0; i < table->DPs; i++) { 99 struct gred_sched_data *q = table->tab[i]; 100 int n; 101 102 if (q == NULL) 103 continue; 104 105 for (n = 0; n < table->DPs; n++) 106 if (table->tab[n] && table->tab[n] != q && 107 table->tab[n]->prio == q->prio) 108 return 1; 109 } 110 111 return 0; 112 } 113 114 static inline unsigned int gred_backlog(struct gred_sched *table, 115 struct gred_sched_data *q, 116 struct Qdisc *sch) 117 { 118 if (gred_wred_mode(table)) 119 return sch->qstats.backlog; 120 else 121 return q->backlog; 122 } 123 124 static inline u16 tc_index_to_dp(struct sk_buff *skb) 125 { 126 return skb->tc_index & GRED_VQ_MASK; 127 } 128 129 static inline void gred_load_wred_set(const struct gred_sched *table, 130 struct gred_sched_data *q) 131 { 132 q->vars.qavg = table->wred_set.qavg; 133 q->vars.qidlestart = table->wred_set.qidlestart; 134 } 135 136 static inline void gred_store_wred_set(struct gred_sched *table, 137 struct gred_sched_data *q) 138 { 139 table->wred_set.qavg = q->vars.qavg; 140 } 141 142 static inline int gred_use_ecn(struct gred_sched *t) 143 { 144 return t->red_flags & TC_RED_ECN; 145 } 146 147 static inline int gred_use_harddrop(struct gred_sched *t) 148 { 149 return t->red_flags & TC_RED_HARDDROP; 150 } 151 152 static int gred_enqueue(struct sk_buff *skb, struct Qdisc *sch) 153 { 154 struct gred_sched_data *q = NULL; 155 struct gred_sched *t = qdisc_priv(sch); 156 unsigned long qavg = 0; 157 u16 dp = tc_index_to_dp(skb); 158 159 if (dp >= t->DPs || (q = t->tab[dp]) == NULL) { 160 dp = t->def; 161 162 q = t->tab[dp]; 163 if (!q) { 164 /* Pass through packets not assigned to a DP 165 * if no default DP has been configured. This 166 * allows for DP flows to be left untouched. 167 */ 168 if (skb_queue_len(&sch->q) < qdisc_dev(sch)->tx_queue_len) 169 return qdisc_enqueue_tail(skb, sch); 170 else 171 goto drop; 172 } 173 174 /* fix tc_index? --could be controversial but needed for 175 requeueing */ 176 skb->tc_index = (skb->tc_index & ~GRED_VQ_MASK) | dp; 177 } 178 179 /* sum up all the qaves of prios <= to ours to get the new qave */ 180 if (!gred_wred_mode(t) && gred_rio_mode(t)) { 181 int i; 182 183 for (i = 0; i < t->DPs; i++) { 184 if (t->tab[i] && t->tab[i]->prio < q->prio && 185 !red_is_idling(&t->tab[i]->vars)) 186 qavg += t->tab[i]->vars.qavg; 187 } 188 189 } 190 191 q->packetsin++; 192 q->bytesin += qdisc_pkt_len(skb); 193 194 if (gred_wred_mode(t)) 195 gred_load_wred_set(t, q); 196 197 q->vars.qavg = red_calc_qavg(&q->parms, 198 &q->vars, 199 gred_backlog(t, q, sch)); 200 201 if (red_is_idling(&q->vars)) 202 red_end_of_idle_period(&q->vars); 203 204 if (gred_wred_mode(t)) 205 gred_store_wred_set(t, q); 206 207 switch (red_action(&q->parms, &q->vars, q->vars.qavg + qavg)) { 208 case RED_DONT_MARK: 209 break; 210 211 case RED_PROB_MARK: 212 sch->qstats.overlimits++; 213 if (!gred_use_ecn(t) || !INET_ECN_set_ce(skb)) { 214 q->stats.prob_drop++; 215 goto congestion_drop; 216 } 217 218 q->stats.prob_mark++; 219 break; 220 221 case RED_HARD_MARK: 222 sch->qstats.overlimits++; 223 if (gred_use_harddrop(t) || !gred_use_ecn(t) || 224 !INET_ECN_set_ce(skb)) { 225 q->stats.forced_drop++; 226 goto congestion_drop; 227 } 228 q->stats.forced_mark++; 229 break; 230 } 231 232 if (q->backlog + qdisc_pkt_len(skb) <= q->limit) { 233 q->backlog += qdisc_pkt_len(skb); 234 return qdisc_enqueue_tail(skb, sch); 235 } 236 237 q->stats.pdrop++; 238 drop: 239 return qdisc_drop(skb, sch); 240 241 congestion_drop: 242 qdisc_drop(skb, sch); 243 return NET_XMIT_CN; 244 } 245 246 static struct sk_buff *gred_dequeue(struct Qdisc *sch) 247 { 248 struct sk_buff *skb; 249 struct gred_sched *t = qdisc_priv(sch); 250 251 skb = qdisc_dequeue_head(sch); 252 253 if (skb) { 254 struct gred_sched_data *q; 255 u16 dp = tc_index_to_dp(skb); 256 257 if (dp >= t->DPs || (q = t->tab[dp]) == NULL) { 258 if (net_ratelimit()) 259 pr_warning("GRED: Unable to relocate VQ 0x%x " 260 "after dequeue, screwing up " 261 "backlog.\n", tc_index_to_dp(skb)); 262 } else { 263 q->backlog -= qdisc_pkt_len(skb); 264 265 if (!q->backlog && !gred_wred_mode(t)) 266 red_start_of_idle_period(&q->vars); 267 } 268 269 return skb; 270 } 271 272 if (gred_wred_mode(t) && !red_is_idling(&t->wred_set)) 273 red_start_of_idle_period(&t->wred_set); 274 275 return NULL; 276 } 277 278 static unsigned int gred_drop(struct Qdisc *sch) 279 { 280 struct sk_buff *skb; 281 struct gred_sched *t = qdisc_priv(sch); 282 283 skb = qdisc_dequeue_tail(sch); 284 if (skb) { 285 unsigned int len = qdisc_pkt_len(skb); 286 struct gred_sched_data *q; 287 u16 dp = tc_index_to_dp(skb); 288 289 if (dp >= t->DPs || (q = t->tab[dp]) == NULL) { 290 if (net_ratelimit()) 291 pr_warning("GRED: Unable to relocate VQ 0x%x " 292 "while dropping, screwing up " 293 "backlog.\n", tc_index_to_dp(skb)); 294 } else { 295 q->backlog -= len; 296 q->stats.other++; 297 298 if (!q->backlog && !gred_wred_mode(t)) 299 red_start_of_idle_period(&q->vars); 300 } 301 302 qdisc_drop(skb, sch); 303 return len; 304 } 305 306 if (gred_wred_mode(t) && !red_is_idling(&t->wred_set)) 307 red_start_of_idle_period(&t->wred_set); 308 309 return 0; 310 311 } 312 313 static void gred_reset(struct Qdisc *sch) 314 { 315 int i; 316 struct gred_sched *t = qdisc_priv(sch); 317 318 qdisc_reset_queue(sch); 319 320 for (i = 0; i < t->DPs; i++) { 321 struct gred_sched_data *q = t->tab[i]; 322 323 if (!q) 324 continue; 325 326 red_restart(&q->vars); 327 q->backlog = 0; 328 } 329 } 330 331 static inline void gred_destroy_vq(struct gred_sched_data *q) 332 { 333 kfree(q); 334 } 335 336 static inline int gred_change_table_def(struct Qdisc *sch, struct nlattr *dps) 337 { 338 struct gred_sched *table = qdisc_priv(sch); 339 struct tc_gred_sopt *sopt; 340 int i; 341 342 if (dps == NULL) 343 return -EINVAL; 344 345 sopt = nla_data(dps); 346 347 if (sopt->DPs > MAX_DPs || sopt->DPs == 0 || sopt->def_DP >= sopt->DPs) 348 return -EINVAL; 349 350 sch_tree_lock(sch); 351 table->DPs = sopt->DPs; 352 table->def = sopt->def_DP; 353 table->red_flags = sopt->flags; 354 355 /* 356 * Every entry point to GRED is synchronized with the above code 357 * and the DP is checked against DPs, i.e. shadowed VQs can no 358 * longer be found so we can unlock right here. 359 */ 360 sch_tree_unlock(sch); 361 362 if (sopt->grio) { 363 gred_enable_rio_mode(table); 364 gred_disable_wred_mode(table); 365 if (gred_wred_mode_check(sch)) 366 gred_enable_wred_mode(table); 367 } else { 368 gred_disable_rio_mode(table); 369 gred_disable_wred_mode(table); 370 } 371 372 for (i = table->DPs; i < MAX_DPs; i++) { 373 if (table->tab[i]) { 374 pr_warning("GRED: Warning: Destroying " 375 "shadowed VQ 0x%x\n", i); 376 gred_destroy_vq(table->tab[i]); 377 table->tab[i] = NULL; 378 } 379 } 380 381 return 0; 382 } 383 384 static inline int gred_change_vq(struct Qdisc *sch, int dp, 385 struct tc_gred_qopt *ctl, int prio, 386 u8 *stab, u32 max_P, 387 struct gred_sched_data **prealloc) 388 { 389 struct gred_sched *table = qdisc_priv(sch); 390 struct gred_sched_data *q = table->tab[dp]; 391 392 if (!q) { 393 table->tab[dp] = q = *prealloc; 394 *prealloc = NULL; 395 if (!q) 396 return -ENOMEM; 397 } 398 399 q->DP = dp; 400 q->prio = prio; 401 q->limit = ctl->limit; 402 403 if (q->backlog == 0) 404 red_end_of_idle_period(&q->vars); 405 406 red_set_parms(&q->parms, 407 ctl->qth_min, ctl->qth_max, ctl->Wlog, ctl->Plog, 408 ctl->Scell_log, stab, max_P); 409 red_set_vars(&q->vars); 410 return 0; 411 } 412 413 static const struct nla_policy gred_policy[TCA_GRED_MAX + 1] = { 414 [TCA_GRED_PARMS] = { .len = sizeof(struct tc_gred_qopt) }, 415 [TCA_GRED_STAB] = { .len = 256 }, 416 [TCA_GRED_DPS] = { .len = sizeof(struct tc_gred_sopt) }, 417 [TCA_GRED_MAX_P] = { .type = NLA_U32 }, 418 }; 419 420 static int gred_change(struct Qdisc *sch, struct nlattr *opt) 421 { 422 struct gred_sched *table = qdisc_priv(sch); 423 struct tc_gred_qopt *ctl; 424 struct nlattr *tb[TCA_GRED_MAX + 1]; 425 int err, prio = GRED_DEF_PRIO; 426 u8 *stab; 427 u32 max_P; 428 struct gred_sched_data *prealloc; 429 430 if (opt == NULL) 431 return -EINVAL; 432 433 err = nla_parse_nested(tb, TCA_GRED_MAX, opt, gred_policy); 434 if (err < 0) 435 return err; 436 437 if (tb[TCA_GRED_PARMS] == NULL && tb[TCA_GRED_STAB] == NULL) 438 return gred_change_table_def(sch, opt); 439 440 if (tb[TCA_GRED_PARMS] == NULL || 441 tb[TCA_GRED_STAB] == NULL) 442 return -EINVAL; 443 444 max_P = tb[TCA_GRED_MAX_P] ? nla_get_u32(tb[TCA_GRED_MAX_P]) : 0; 445 446 err = -EINVAL; 447 ctl = nla_data(tb[TCA_GRED_PARMS]); 448 stab = nla_data(tb[TCA_GRED_STAB]); 449 450 if (ctl->DP >= table->DPs) 451 goto errout; 452 453 if (gred_rio_mode(table)) { 454 if (ctl->prio == 0) { 455 int def_prio = GRED_DEF_PRIO; 456 457 if (table->tab[table->def]) 458 def_prio = table->tab[table->def]->prio; 459 460 printk(KERN_DEBUG "GRED: DP %u does not have a prio " 461 "setting default to %d\n", ctl->DP, def_prio); 462 463 prio = def_prio; 464 } else 465 prio = ctl->prio; 466 } 467 468 prealloc = kzalloc(sizeof(*prealloc), GFP_KERNEL); 469 sch_tree_lock(sch); 470 471 err = gred_change_vq(sch, ctl->DP, ctl, prio, stab, max_P, &prealloc); 472 if (err < 0) 473 goto errout_locked; 474 475 if (gred_rio_mode(table)) { 476 gred_disable_wred_mode(table); 477 if (gred_wred_mode_check(sch)) 478 gred_enable_wred_mode(table); 479 } 480 481 err = 0; 482 483 errout_locked: 484 sch_tree_unlock(sch); 485 kfree(prealloc); 486 errout: 487 return err; 488 } 489 490 static int gred_init(struct Qdisc *sch, struct nlattr *opt) 491 { 492 struct nlattr *tb[TCA_GRED_MAX + 1]; 493 int err; 494 495 if (opt == NULL) 496 return -EINVAL; 497 498 err = nla_parse_nested(tb, TCA_GRED_MAX, opt, gred_policy); 499 if (err < 0) 500 return err; 501 502 if (tb[TCA_GRED_PARMS] || tb[TCA_GRED_STAB]) 503 return -EINVAL; 504 505 return gred_change_table_def(sch, tb[TCA_GRED_DPS]); 506 } 507 508 static int gred_dump(struct Qdisc *sch, struct sk_buff *skb) 509 { 510 struct gred_sched *table = qdisc_priv(sch); 511 struct nlattr *parms, *opts = NULL; 512 int i; 513 u32 max_p[MAX_DPs]; 514 struct tc_gred_sopt sopt = { 515 .DPs = table->DPs, 516 .def_DP = table->def, 517 .grio = gred_rio_mode(table), 518 .flags = table->red_flags, 519 }; 520 521 opts = nla_nest_start(skb, TCA_OPTIONS); 522 if (opts == NULL) 523 goto nla_put_failure; 524 NLA_PUT(skb, TCA_GRED_DPS, sizeof(sopt), &sopt); 525 526 for (i = 0; i < MAX_DPs; i++) { 527 struct gred_sched_data *q = table->tab[i]; 528 529 max_p[i] = q ? q->parms.max_P : 0; 530 } 531 NLA_PUT(skb, TCA_GRED_MAX_P, sizeof(max_p), max_p); 532 533 parms = nla_nest_start(skb, TCA_GRED_PARMS); 534 if (parms == NULL) 535 goto nla_put_failure; 536 537 for (i = 0; i < MAX_DPs; i++) { 538 struct gred_sched_data *q = table->tab[i]; 539 struct tc_gred_qopt opt; 540 541 memset(&opt, 0, sizeof(opt)); 542 543 if (!q) { 544 /* hack -- fix at some point with proper message 545 This is how we indicate to tc that there is no VQ 546 at this DP */ 547 548 opt.DP = MAX_DPs + i; 549 goto append_opt; 550 } 551 552 opt.limit = q->limit; 553 opt.DP = q->DP; 554 opt.backlog = q->backlog; 555 opt.prio = q->prio; 556 opt.qth_min = q->parms.qth_min >> q->parms.Wlog; 557 opt.qth_max = q->parms.qth_max >> q->parms.Wlog; 558 opt.Wlog = q->parms.Wlog; 559 opt.Plog = q->parms.Plog; 560 opt.Scell_log = q->parms.Scell_log; 561 opt.other = q->stats.other; 562 opt.early = q->stats.prob_drop; 563 opt.forced = q->stats.forced_drop; 564 opt.pdrop = q->stats.pdrop; 565 opt.packets = q->packetsin; 566 opt.bytesin = q->bytesin; 567 568 if (gred_wred_mode(table)) { 569 q->vars.qidlestart = 570 table->tab[table->def]->vars.qidlestart; 571 q->vars.qavg = table->tab[table->def]->vars.qavg; 572 } 573 574 opt.qave = red_calc_qavg(&q->parms, &q->vars, q->vars.qavg); 575 576 append_opt: 577 if (nla_append(skb, sizeof(opt), &opt) < 0) 578 goto nla_put_failure; 579 } 580 581 nla_nest_end(skb, parms); 582 583 return nla_nest_end(skb, opts); 584 585 nla_put_failure: 586 nla_nest_cancel(skb, opts); 587 return -EMSGSIZE; 588 } 589 590 static void gred_destroy(struct Qdisc *sch) 591 { 592 struct gred_sched *table = qdisc_priv(sch); 593 int i; 594 595 for (i = 0; i < table->DPs; i++) { 596 if (table->tab[i]) 597 gred_destroy_vq(table->tab[i]); 598 } 599 } 600 601 static struct Qdisc_ops gred_qdisc_ops __read_mostly = { 602 .id = "gred", 603 .priv_size = sizeof(struct gred_sched), 604 .enqueue = gred_enqueue, 605 .dequeue = gred_dequeue, 606 .peek = qdisc_peek_head, 607 .drop = gred_drop, 608 .init = gred_init, 609 .reset = gred_reset, 610 .destroy = gred_destroy, 611 .change = gred_change, 612 .dump = gred_dump, 613 .owner = THIS_MODULE, 614 }; 615 616 static int __init gred_module_init(void) 617 { 618 return register_qdisc(&gred_qdisc_ops); 619 } 620 621 static void __exit gred_module_exit(void) 622 { 623 unregister_qdisc(&gred_qdisc_ops); 624 } 625 626 module_init(gred_module_init) 627 module_exit(gred_module_exit) 628 629 MODULE_LICENSE("GPL"); 630