1 /* 2 * Copyright (c) 2003 Patrick McHardy, <kaber@trash.net> 3 * 4 * This program is free software; you can redistribute it and/or 5 * modify it under the terms of the GNU General Public License 6 * as published by the Free Software Foundation; either version 2 7 * of the License, or (at your option) any later version. 8 * 9 * 2003-10-17 - Ported from altq 10 */ 11 /* 12 * Copyright (c) 1997-1999 Carnegie Mellon University. All Rights Reserved. 13 * 14 * Permission to use, copy, modify, and distribute this software and 15 * its documentation is hereby granted (including for commercial or 16 * for-profit use), provided that both the copyright notice and this 17 * permission notice appear in all copies of the software, derivative 18 * works, or modified versions, and any portions thereof. 19 * 20 * THIS SOFTWARE IS EXPERIMENTAL AND IS KNOWN TO HAVE BUGS, SOME OF 21 * WHICH MAY HAVE SERIOUS CONSEQUENCES. CARNEGIE MELLON PROVIDES THIS 22 * SOFTWARE IN ITS ``AS IS'' CONDITION, AND ANY EXPRESS OR IMPLIED 23 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 24 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 25 * DISCLAIMED. IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY BE LIABLE 26 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 27 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT 28 * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR 29 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 30 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 31 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE 32 * USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH 33 * DAMAGE. 34 * 35 * Carnegie Mellon encourages (but does not require) users of this 36 * software to return any improvements or extensions that they make, 37 * and to grant Carnegie Mellon the rights to redistribute these 38 * changes without encumbrance. 39 */ 40 /* 41 * H-FSC is described in Proceedings of SIGCOMM'97, 42 * "A Hierarchical Fair Service Curve Algorithm for Link-Sharing, 43 * Real-Time and Priority Service" 44 * by Ion Stoica, Hui Zhang, and T. S. Eugene Ng. 45 * 46 * Oleg Cherevko <olwi@aq.ml.com.ua> added the upperlimit for link-sharing. 47 * when a class has an upperlimit, the fit-time is computed from the 48 * upperlimit service curve. the link-sharing scheduler does not schedule 49 * a class whose fit-time exceeds the current time. 50 */ 51 52 #include <linux/kernel.h> 53 #include <linux/module.h> 54 #include <linux/types.h> 55 #include <linux/errno.h> 56 #include <linux/compiler.h> 57 #include <linux/spinlock.h> 58 #include <linux/skbuff.h> 59 #include <linux/string.h> 60 #include <linux/slab.h> 61 #include <linux/list.h> 62 #include <linux/rbtree.h> 63 #include <linux/init.h> 64 #include <linux/rtnetlink.h> 65 #include <linux/pkt_sched.h> 66 #include <net/netlink.h> 67 #include <net/pkt_sched.h> 68 #include <net/pkt_cls.h> 69 #include <asm/div64.h> 70 71 /* 72 * kernel internal service curve representation: 73 * coordinates are given by 64 bit unsigned integers. 74 * x-axis: unit is clock count. 75 * y-axis: unit is byte. 76 * 77 * The service curve parameters are converted to the internal 78 * representation. The slope values are scaled to avoid overflow. 79 * the inverse slope values as well as the y-projection of the 1st 80 * segment are kept in order to to avoid 64-bit divide operations 81 * that are expensive on 32-bit architectures. 82 */ 83 84 struct internal_sc 85 { 86 u64 sm1; /* scaled slope of the 1st segment */ 87 u64 ism1; /* scaled inverse-slope of the 1st segment */ 88 u64 dx; /* the x-projection of the 1st segment */ 89 u64 dy; /* the y-projection of the 1st segment */ 90 u64 sm2; /* scaled slope of the 2nd segment */ 91 u64 ism2; /* scaled inverse-slope of the 2nd segment */ 92 }; 93 94 /* runtime service curve */ 95 struct runtime_sc 96 { 97 u64 x; /* current starting position on x-axis */ 98 u64 y; /* current starting position on y-axis */ 99 u64 sm1; /* scaled slope of the 1st segment */ 100 u64 ism1; /* scaled inverse-slope of the 1st segment */ 101 u64 dx; /* the x-projection of the 1st segment */ 102 u64 dy; /* the y-projection of the 1st segment */ 103 u64 sm2; /* scaled slope of the 2nd segment */ 104 u64 ism2; /* scaled inverse-slope of the 2nd segment */ 105 }; 106 107 enum hfsc_class_flags 108 { 109 HFSC_RSC = 0x1, 110 HFSC_FSC = 0x2, 111 HFSC_USC = 0x4 112 }; 113 114 struct hfsc_class 115 { 116 u32 classid; /* class id */ 117 unsigned int refcnt; /* usage count */ 118 119 struct gnet_stats_basic bstats; 120 struct gnet_stats_queue qstats; 121 struct gnet_stats_rate_est rate_est; 122 unsigned int level; /* class level in hierarchy */ 123 struct tcf_proto *filter_list; /* filter list */ 124 unsigned int filter_cnt; /* filter count */ 125 126 struct hfsc_sched *sched; /* scheduler data */ 127 struct hfsc_class *cl_parent; /* parent class */ 128 struct list_head siblings; /* sibling classes */ 129 struct list_head children; /* child classes */ 130 struct Qdisc *qdisc; /* leaf qdisc */ 131 132 struct rb_node el_node; /* qdisc's eligible tree member */ 133 struct rb_root vt_tree; /* active children sorted by cl_vt */ 134 struct rb_node vt_node; /* parent's vt_tree member */ 135 struct rb_root cf_tree; /* active children sorted by cl_f */ 136 struct rb_node cf_node; /* parent's cf_heap member */ 137 struct list_head hlist; /* hash list member */ 138 struct list_head dlist; /* drop list member */ 139 140 u64 cl_total; /* total work in bytes */ 141 u64 cl_cumul; /* cumulative work in bytes done by 142 real-time criteria */ 143 144 u64 cl_d; /* deadline*/ 145 u64 cl_e; /* eligible time */ 146 u64 cl_vt; /* virtual time */ 147 u64 cl_f; /* time when this class will fit for 148 link-sharing, max(myf, cfmin) */ 149 u64 cl_myf; /* my fit-time (calculated from this 150 class's own upperlimit curve) */ 151 u64 cl_myfadj; /* my fit-time adjustment (to cancel 152 history dependence) */ 153 u64 cl_cfmin; /* earliest children's fit-time (used 154 with cl_myf to obtain cl_f) */ 155 u64 cl_cvtmin; /* minimal virtual time among the 156 children fit for link-sharing 157 (monotonic within a period) */ 158 u64 cl_vtadj; /* intra-period cumulative vt 159 adjustment */ 160 u64 cl_vtoff; /* inter-period cumulative vt offset */ 161 u64 cl_cvtmax; /* max child's vt in the last period */ 162 u64 cl_cvtoff; /* cumulative cvtmax of all periods */ 163 u64 cl_pcvtoff; /* parent's cvtoff at initialization 164 time */ 165 166 struct internal_sc cl_rsc; /* internal real-time service curve */ 167 struct internal_sc cl_fsc; /* internal fair service curve */ 168 struct internal_sc cl_usc; /* internal upperlimit service curve */ 169 struct runtime_sc cl_deadline; /* deadline curve */ 170 struct runtime_sc cl_eligible; /* eligible curve */ 171 struct runtime_sc cl_virtual; /* virtual curve */ 172 struct runtime_sc cl_ulimit; /* upperlimit curve */ 173 174 unsigned long cl_flags; /* which curves are valid */ 175 unsigned long cl_vtperiod; /* vt period sequence number */ 176 unsigned long cl_parentperiod;/* parent's vt period sequence number*/ 177 unsigned long cl_nactive; /* number of active children */ 178 }; 179 180 #define HFSC_HSIZE 16 181 182 struct hfsc_sched 183 { 184 u16 defcls; /* default class id */ 185 struct hfsc_class root; /* root class */ 186 struct list_head clhash[HFSC_HSIZE]; /* class hash */ 187 struct rb_root eligible; /* eligible tree */ 188 struct list_head droplist; /* active leaf class list (for 189 dropping) */ 190 struct sk_buff_head requeue; /* requeued packet */ 191 struct qdisc_watchdog watchdog; /* watchdog timer */ 192 }; 193 194 #define HT_INFINITY 0xffffffffffffffffULL /* infinite time value */ 195 196 197 /* 198 * eligible tree holds backlogged classes being sorted by their eligible times. 199 * there is one eligible tree per hfsc instance. 200 */ 201 202 static void 203 eltree_insert(struct hfsc_class *cl) 204 { 205 struct rb_node **p = &cl->sched->eligible.rb_node; 206 struct rb_node *parent = NULL; 207 struct hfsc_class *cl1; 208 209 while (*p != NULL) { 210 parent = *p; 211 cl1 = rb_entry(parent, struct hfsc_class, el_node); 212 if (cl->cl_e >= cl1->cl_e) 213 p = &parent->rb_right; 214 else 215 p = &parent->rb_left; 216 } 217 rb_link_node(&cl->el_node, parent, p); 218 rb_insert_color(&cl->el_node, &cl->sched->eligible); 219 } 220 221 static inline void 222 eltree_remove(struct hfsc_class *cl) 223 { 224 rb_erase(&cl->el_node, &cl->sched->eligible); 225 } 226 227 static inline void 228 eltree_update(struct hfsc_class *cl) 229 { 230 eltree_remove(cl); 231 eltree_insert(cl); 232 } 233 234 /* find the class with the minimum deadline among the eligible classes */ 235 static inline struct hfsc_class * 236 eltree_get_mindl(struct hfsc_sched *q, u64 cur_time) 237 { 238 struct hfsc_class *p, *cl = NULL; 239 struct rb_node *n; 240 241 for (n = rb_first(&q->eligible); n != NULL; n = rb_next(n)) { 242 p = rb_entry(n, struct hfsc_class, el_node); 243 if (p->cl_e > cur_time) 244 break; 245 if (cl == NULL || p->cl_d < cl->cl_d) 246 cl = p; 247 } 248 return cl; 249 } 250 251 /* find the class with minimum eligible time among the eligible classes */ 252 static inline struct hfsc_class * 253 eltree_get_minel(struct hfsc_sched *q) 254 { 255 struct rb_node *n; 256 257 n = rb_first(&q->eligible); 258 if (n == NULL) 259 return NULL; 260 return rb_entry(n, struct hfsc_class, el_node); 261 } 262 263 /* 264 * vttree holds holds backlogged child classes being sorted by their virtual 265 * time. each intermediate class has one vttree. 266 */ 267 static void 268 vttree_insert(struct hfsc_class *cl) 269 { 270 struct rb_node **p = &cl->cl_parent->vt_tree.rb_node; 271 struct rb_node *parent = NULL; 272 struct hfsc_class *cl1; 273 274 while (*p != NULL) { 275 parent = *p; 276 cl1 = rb_entry(parent, struct hfsc_class, vt_node); 277 if (cl->cl_vt >= cl1->cl_vt) 278 p = &parent->rb_right; 279 else 280 p = &parent->rb_left; 281 } 282 rb_link_node(&cl->vt_node, parent, p); 283 rb_insert_color(&cl->vt_node, &cl->cl_parent->vt_tree); 284 } 285 286 static inline void 287 vttree_remove(struct hfsc_class *cl) 288 { 289 rb_erase(&cl->vt_node, &cl->cl_parent->vt_tree); 290 } 291 292 static inline void 293 vttree_update(struct hfsc_class *cl) 294 { 295 vttree_remove(cl); 296 vttree_insert(cl); 297 } 298 299 static inline struct hfsc_class * 300 vttree_firstfit(struct hfsc_class *cl, u64 cur_time) 301 { 302 struct hfsc_class *p; 303 struct rb_node *n; 304 305 for (n = rb_first(&cl->vt_tree); n != NULL; n = rb_next(n)) { 306 p = rb_entry(n, struct hfsc_class, vt_node); 307 if (p->cl_f <= cur_time) 308 return p; 309 } 310 return NULL; 311 } 312 313 /* 314 * get the leaf class with the minimum vt in the hierarchy 315 */ 316 static struct hfsc_class * 317 vttree_get_minvt(struct hfsc_class *cl, u64 cur_time) 318 { 319 /* if root-class's cfmin is bigger than cur_time nothing to do */ 320 if (cl->cl_cfmin > cur_time) 321 return NULL; 322 323 while (cl->level > 0) { 324 cl = vttree_firstfit(cl, cur_time); 325 if (cl == NULL) 326 return NULL; 327 /* 328 * update parent's cl_cvtmin. 329 */ 330 if (cl->cl_parent->cl_cvtmin < cl->cl_vt) 331 cl->cl_parent->cl_cvtmin = cl->cl_vt; 332 } 333 return cl; 334 } 335 336 static void 337 cftree_insert(struct hfsc_class *cl) 338 { 339 struct rb_node **p = &cl->cl_parent->cf_tree.rb_node; 340 struct rb_node *parent = NULL; 341 struct hfsc_class *cl1; 342 343 while (*p != NULL) { 344 parent = *p; 345 cl1 = rb_entry(parent, struct hfsc_class, cf_node); 346 if (cl->cl_f >= cl1->cl_f) 347 p = &parent->rb_right; 348 else 349 p = &parent->rb_left; 350 } 351 rb_link_node(&cl->cf_node, parent, p); 352 rb_insert_color(&cl->cf_node, &cl->cl_parent->cf_tree); 353 } 354 355 static inline void 356 cftree_remove(struct hfsc_class *cl) 357 { 358 rb_erase(&cl->cf_node, &cl->cl_parent->cf_tree); 359 } 360 361 static inline void 362 cftree_update(struct hfsc_class *cl) 363 { 364 cftree_remove(cl); 365 cftree_insert(cl); 366 } 367 368 /* 369 * service curve support functions 370 * 371 * external service curve parameters 372 * m: bps 373 * d: us 374 * internal service curve parameters 375 * sm: (bytes/psched_us) << SM_SHIFT 376 * ism: (psched_us/byte) << ISM_SHIFT 377 * dx: psched_us 378 * 379 * The clock source resolution with ktime is 1.024us. 380 * 381 * sm and ism are scaled in order to keep effective digits. 382 * SM_SHIFT and ISM_SHIFT are selected to keep at least 4 effective 383 * digits in decimal using the following table. 384 * 385 * bits/sec 100Kbps 1Mbps 10Mbps 100Mbps 1Gbps 386 * ------------+------------------------------------------------------- 387 * bytes/1.024us 12.8e-3 128e-3 1280e-3 12800e-3 128000e-3 388 * 389 * 1.024us/byte 78.125 7.8125 0.78125 0.078125 0.0078125 390 */ 391 #define SM_SHIFT 20 392 #define ISM_SHIFT 18 393 394 #define SM_MASK ((1ULL << SM_SHIFT) - 1) 395 #define ISM_MASK ((1ULL << ISM_SHIFT) - 1) 396 397 static inline u64 398 seg_x2y(u64 x, u64 sm) 399 { 400 u64 y; 401 402 /* 403 * compute 404 * y = x * sm >> SM_SHIFT 405 * but divide it for the upper and lower bits to avoid overflow 406 */ 407 y = (x >> SM_SHIFT) * sm + (((x & SM_MASK) * sm) >> SM_SHIFT); 408 return y; 409 } 410 411 static inline u64 412 seg_y2x(u64 y, u64 ism) 413 { 414 u64 x; 415 416 if (y == 0) 417 x = 0; 418 else if (ism == HT_INFINITY) 419 x = HT_INFINITY; 420 else { 421 x = (y >> ISM_SHIFT) * ism 422 + (((y & ISM_MASK) * ism) >> ISM_SHIFT); 423 } 424 return x; 425 } 426 427 /* Convert m (bps) into sm (bytes/psched us) */ 428 static u64 429 m2sm(u32 m) 430 { 431 u64 sm; 432 433 sm = ((u64)m << SM_SHIFT); 434 sm += PSCHED_TICKS_PER_SEC - 1; 435 do_div(sm, PSCHED_TICKS_PER_SEC); 436 return sm; 437 } 438 439 /* convert m (bps) into ism (psched us/byte) */ 440 static u64 441 m2ism(u32 m) 442 { 443 u64 ism; 444 445 if (m == 0) 446 ism = HT_INFINITY; 447 else { 448 ism = ((u64)PSCHED_TICKS_PER_SEC << ISM_SHIFT); 449 ism += m - 1; 450 do_div(ism, m); 451 } 452 return ism; 453 } 454 455 /* convert d (us) into dx (psched us) */ 456 static u64 457 d2dx(u32 d) 458 { 459 u64 dx; 460 461 dx = ((u64)d * PSCHED_TICKS_PER_SEC); 462 dx += USEC_PER_SEC - 1; 463 do_div(dx, USEC_PER_SEC); 464 return dx; 465 } 466 467 /* convert sm (bytes/psched us) into m (bps) */ 468 static u32 469 sm2m(u64 sm) 470 { 471 u64 m; 472 473 m = (sm * PSCHED_TICKS_PER_SEC) >> SM_SHIFT; 474 return (u32)m; 475 } 476 477 /* convert dx (psched us) into d (us) */ 478 static u32 479 dx2d(u64 dx) 480 { 481 u64 d; 482 483 d = dx * USEC_PER_SEC; 484 do_div(d, PSCHED_TICKS_PER_SEC); 485 return (u32)d; 486 } 487 488 static void 489 sc2isc(struct tc_service_curve *sc, struct internal_sc *isc) 490 { 491 isc->sm1 = m2sm(sc->m1); 492 isc->ism1 = m2ism(sc->m1); 493 isc->dx = d2dx(sc->d); 494 isc->dy = seg_x2y(isc->dx, isc->sm1); 495 isc->sm2 = m2sm(sc->m2); 496 isc->ism2 = m2ism(sc->m2); 497 } 498 499 /* 500 * initialize the runtime service curve with the given internal 501 * service curve starting at (x, y). 502 */ 503 static void 504 rtsc_init(struct runtime_sc *rtsc, struct internal_sc *isc, u64 x, u64 y) 505 { 506 rtsc->x = x; 507 rtsc->y = y; 508 rtsc->sm1 = isc->sm1; 509 rtsc->ism1 = isc->ism1; 510 rtsc->dx = isc->dx; 511 rtsc->dy = isc->dy; 512 rtsc->sm2 = isc->sm2; 513 rtsc->ism2 = isc->ism2; 514 } 515 516 /* 517 * calculate the y-projection of the runtime service curve by the 518 * given x-projection value 519 */ 520 static u64 521 rtsc_y2x(struct runtime_sc *rtsc, u64 y) 522 { 523 u64 x; 524 525 if (y < rtsc->y) 526 x = rtsc->x; 527 else if (y <= rtsc->y + rtsc->dy) { 528 /* x belongs to the 1st segment */ 529 if (rtsc->dy == 0) 530 x = rtsc->x + rtsc->dx; 531 else 532 x = rtsc->x + seg_y2x(y - rtsc->y, rtsc->ism1); 533 } else { 534 /* x belongs to the 2nd segment */ 535 x = rtsc->x + rtsc->dx 536 + seg_y2x(y - rtsc->y - rtsc->dy, rtsc->ism2); 537 } 538 return x; 539 } 540 541 static u64 542 rtsc_x2y(struct runtime_sc *rtsc, u64 x) 543 { 544 u64 y; 545 546 if (x <= rtsc->x) 547 y = rtsc->y; 548 else if (x <= rtsc->x + rtsc->dx) 549 /* y belongs to the 1st segment */ 550 y = rtsc->y + seg_x2y(x - rtsc->x, rtsc->sm1); 551 else 552 /* y belongs to the 2nd segment */ 553 y = rtsc->y + rtsc->dy 554 + seg_x2y(x - rtsc->x - rtsc->dx, rtsc->sm2); 555 return y; 556 } 557 558 /* 559 * update the runtime service curve by taking the minimum of the current 560 * runtime service curve and the service curve starting at (x, y). 561 */ 562 static void 563 rtsc_min(struct runtime_sc *rtsc, struct internal_sc *isc, u64 x, u64 y) 564 { 565 u64 y1, y2, dx, dy; 566 u32 dsm; 567 568 if (isc->sm1 <= isc->sm2) { 569 /* service curve is convex */ 570 y1 = rtsc_x2y(rtsc, x); 571 if (y1 < y) 572 /* the current rtsc is smaller */ 573 return; 574 rtsc->x = x; 575 rtsc->y = y; 576 return; 577 } 578 579 /* 580 * service curve is concave 581 * compute the two y values of the current rtsc 582 * y1: at x 583 * y2: at (x + dx) 584 */ 585 y1 = rtsc_x2y(rtsc, x); 586 if (y1 <= y) { 587 /* rtsc is below isc, no change to rtsc */ 588 return; 589 } 590 591 y2 = rtsc_x2y(rtsc, x + isc->dx); 592 if (y2 >= y + isc->dy) { 593 /* rtsc is above isc, replace rtsc by isc */ 594 rtsc->x = x; 595 rtsc->y = y; 596 rtsc->dx = isc->dx; 597 rtsc->dy = isc->dy; 598 return; 599 } 600 601 /* 602 * the two curves intersect 603 * compute the offsets (dx, dy) using the reverse 604 * function of seg_x2y() 605 * seg_x2y(dx, sm1) == seg_x2y(dx, sm2) + (y1 - y) 606 */ 607 dx = (y1 - y) << SM_SHIFT; 608 dsm = isc->sm1 - isc->sm2; 609 do_div(dx, dsm); 610 /* 611 * check if (x, y1) belongs to the 1st segment of rtsc. 612 * if so, add the offset. 613 */ 614 if (rtsc->x + rtsc->dx > x) 615 dx += rtsc->x + rtsc->dx - x; 616 dy = seg_x2y(dx, isc->sm1); 617 618 rtsc->x = x; 619 rtsc->y = y; 620 rtsc->dx = dx; 621 rtsc->dy = dy; 622 return; 623 } 624 625 static void 626 init_ed(struct hfsc_class *cl, unsigned int next_len) 627 { 628 u64 cur_time = psched_get_time(); 629 630 /* update the deadline curve */ 631 rtsc_min(&cl->cl_deadline, &cl->cl_rsc, cur_time, cl->cl_cumul); 632 633 /* 634 * update the eligible curve. 635 * for concave, it is equal to the deadline curve. 636 * for convex, it is a linear curve with slope m2. 637 */ 638 cl->cl_eligible = cl->cl_deadline; 639 if (cl->cl_rsc.sm1 <= cl->cl_rsc.sm2) { 640 cl->cl_eligible.dx = 0; 641 cl->cl_eligible.dy = 0; 642 } 643 644 /* compute e and d */ 645 cl->cl_e = rtsc_y2x(&cl->cl_eligible, cl->cl_cumul); 646 cl->cl_d = rtsc_y2x(&cl->cl_deadline, cl->cl_cumul + next_len); 647 648 eltree_insert(cl); 649 } 650 651 static void 652 update_ed(struct hfsc_class *cl, unsigned int next_len) 653 { 654 cl->cl_e = rtsc_y2x(&cl->cl_eligible, cl->cl_cumul); 655 cl->cl_d = rtsc_y2x(&cl->cl_deadline, cl->cl_cumul + next_len); 656 657 eltree_update(cl); 658 } 659 660 static inline void 661 update_d(struct hfsc_class *cl, unsigned int next_len) 662 { 663 cl->cl_d = rtsc_y2x(&cl->cl_deadline, cl->cl_cumul + next_len); 664 } 665 666 static inline void 667 update_cfmin(struct hfsc_class *cl) 668 { 669 struct rb_node *n = rb_first(&cl->cf_tree); 670 struct hfsc_class *p; 671 672 if (n == NULL) { 673 cl->cl_cfmin = 0; 674 return; 675 } 676 p = rb_entry(n, struct hfsc_class, cf_node); 677 cl->cl_cfmin = p->cl_f; 678 } 679 680 static void 681 init_vf(struct hfsc_class *cl, unsigned int len) 682 { 683 struct hfsc_class *max_cl; 684 struct rb_node *n; 685 u64 vt, f, cur_time; 686 int go_active; 687 688 cur_time = 0; 689 go_active = 1; 690 for (; cl->cl_parent != NULL; cl = cl->cl_parent) { 691 if (go_active && cl->cl_nactive++ == 0) 692 go_active = 1; 693 else 694 go_active = 0; 695 696 if (go_active) { 697 n = rb_last(&cl->cl_parent->vt_tree); 698 if (n != NULL) { 699 max_cl = rb_entry(n, struct hfsc_class,vt_node); 700 /* 701 * set vt to the average of the min and max 702 * classes. if the parent's period didn't 703 * change, don't decrease vt of the class. 704 */ 705 vt = max_cl->cl_vt; 706 if (cl->cl_parent->cl_cvtmin != 0) 707 vt = (cl->cl_parent->cl_cvtmin + vt)/2; 708 709 if (cl->cl_parent->cl_vtperiod != 710 cl->cl_parentperiod || vt > cl->cl_vt) 711 cl->cl_vt = vt; 712 } else { 713 /* 714 * first child for a new parent backlog period. 715 * add parent's cvtmax to cvtoff to make a new 716 * vt (vtoff + vt) larger than the vt in the 717 * last period for all children. 718 */ 719 vt = cl->cl_parent->cl_cvtmax; 720 cl->cl_parent->cl_cvtoff += vt; 721 cl->cl_parent->cl_cvtmax = 0; 722 cl->cl_parent->cl_cvtmin = 0; 723 cl->cl_vt = 0; 724 } 725 726 cl->cl_vtoff = cl->cl_parent->cl_cvtoff - 727 cl->cl_pcvtoff; 728 729 /* update the virtual curve */ 730 vt = cl->cl_vt + cl->cl_vtoff; 731 rtsc_min(&cl->cl_virtual, &cl->cl_fsc, vt, 732 cl->cl_total); 733 if (cl->cl_virtual.x == vt) { 734 cl->cl_virtual.x -= cl->cl_vtoff; 735 cl->cl_vtoff = 0; 736 } 737 cl->cl_vtadj = 0; 738 739 cl->cl_vtperiod++; /* increment vt period */ 740 cl->cl_parentperiod = cl->cl_parent->cl_vtperiod; 741 if (cl->cl_parent->cl_nactive == 0) 742 cl->cl_parentperiod++; 743 cl->cl_f = 0; 744 745 vttree_insert(cl); 746 cftree_insert(cl); 747 748 if (cl->cl_flags & HFSC_USC) { 749 /* class has upper limit curve */ 750 if (cur_time == 0) 751 cur_time = psched_get_time(); 752 753 /* update the ulimit curve */ 754 rtsc_min(&cl->cl_ulimit, &cl->cl_usc, cur_time, 755 cl->cl_total); 756 /* compute myf */ 757 cl->cl_myf = rtsc_y2x(&cl->cl_ulimit, 758 cl->cl_total); 759 cl->cl_myfadj = 0; 760 } 761 } 762 763 f = max(cl->cl_myf, cl->cl_cfmin); 764 if (f != cl->cl_f) { 765 cl->cl_f = f; 766 cftree_update(cl); 767 update_cfmin(cl->cl_parent); 768 } 769 } 770 } 771 772 static void 773 update_vf(struct hfsc_class *cl, unsigned int len, u64 cur_time) 774 { 775 u64 f; /* , myf_bound, delta; */ 776 int go_passive = 0; 777 778 if (cl->qdisc->q.qlen == 0 && cl->cl_flags & HFSC_FSC) 779 go_passive = 1; 780 781 for (; cl->cl_parent != NULL; cl = cl->cl_parent) { 782 cl->cl_total += len; 783 784 if (!(cl->cl_flags & HFSC_FSC) || cl->cl_nactive == 0) 785 continue; 786 787 if (go_passive && --cl->cl_nactive == 0) 788 go_passive = 1; 789 else 790 go_passive = 0; 791 792 if (go_passive) { 793 /* no more active child, going passive */ 794 795 /* update cvtmax of the parent class */ 796 if (cl->cl_vt > cl->cl_parent->cl_cvtmax) 797 cl->cl_parent->cl_cvtmax = cl->cl_vt; 798 799 /* remove this class from the vt tree */ 800 vttree_remove(cl); 801 802 cftree_remove(cl); 803 update_cfmin(cl->cl_parent); 804 805 continue; 806 } 807 808 /* 809 * update vt and f 810 */ 811 cl->cl_vt = rtsc_y2x(&cl->cl_virtual, cl->cl_total) 812 - cl->cl_vtoff + cl->cl_vtadj; 813 814 /* 815 * if vt of the class is smaller than cvtmin, 816 * the class was skipped in the past due to non-fit. 817 * if so, we need to adjust vtadj. 818 */ 819 if (cl->cl_vt < cl->cl_parent->cl_cvtmin) { 820 cl->cl_vtadj += cl->cl_parent->cl_cvtmin - cl->cl_vt; 821 cl->cl_vt = cl->cl_parent->cl_cvtmin; 822 } 823 824 /* update the vt tree */ 825 vttree_update(cl); 826 827 if (cl->cl_flags & HFSC_USC) { 828 cl->cl_myf = cl->cl_myfadj + rtsc_y2x(&cl->cl_ulimit, 829 cl->cl_total); 830 #if 0 831 /* 832 * This code causes classes to stay way under their 833 * limit when multiple classes are used at gigabit 834 * speed. needs investigation. -kaber 835 */ 836 /* 837 * if myf lags behind by more than one clock tick 838 * from the current time, adjust myfadj to prevent 839 * a rate-limited class from going greedy. 840 * in a steady state under rate-limiting, myf 841 * fluctuates within one clock tick. 842 */ 843 myf_bound = cur_time - PSCHED_JIFFIE2US(1); 844 if (cl->cl_myf < myf_bound) { 845 delta = cur_time - cl->cl_myf; 846 cl->cl_myfadj += delta; 847 cl->cl_myf += delta; 848 } 849 #endif 850 } 851 852 f = max(cl->cl_myf, cl->cl_cfmin); 853 if (f != cl->cl_f) { 854 cl->cl_f = f; 855 cftree_update(cl); 856 update_cfmin(cl->cl_parent); 857 } 858 } 859 } 860 861 static void 862 set_active(struct hfsc_class *cl, unsigned int len) 863 { 864 if (cl->cl_flags & HFSC_RSC) 865 init_ed(cl, len); 866 if (cl->cl_flags & HFSC_FSC) 867 init_vf(cl, len); 868 869 list_add_tail(&cl->dlist, &cl->sched->droplist); 870 } 871 872 static void 873 set_passive(struct hfsc_class *cl) 874 { 875 if (cl->cl_flags & HFSC_RSC) 876 eltree_remove(cl); 877 878 list_del(&cl->dlist); 879 880 /* 881 * vttree is now handled in update_vf() so that update_vf(cl, 0, 0) 882 * needs to be called explicitly to remove a class from vttree. 883 */ 884 } 885 886 /* 887 * hack to get length of first packet in queue. 888 */ 889 static unsigned int 890 qdisc_peek_len(struct Qdisc *sch) 891 { 892 struct sk_buff *skb; 893 unsigned int len; 894 895 skb = sch->dequeue(sch); 896 if (skb == NULL) { 897 if (net_ratelimit()) 898 printk("qdisc_peek_len: non work-conserving qdisc ?\n"); 899 return 0; 900 } 901 len = skb->len; 902 if (unlikely(sch->ops->requeue(skb, sch) != NET_XMIT_SUCCESS)) { 903 if (net_ratelimit()) 904 printk("qdisc_peek_len: failed to requeue\n"); 905 qdisc_tree_decrease_qlen(sch, 1); 906 return 0; 907 } 908 return len; 909 } 910 911 static void 912 hfsc_purge_queue(struct Qdisc *sch, struct hfsc_class *cl) 913 { 914 unsigned int len = cl->qdisc->q.qlen; 915 916 qdisc_reset(cl->qdisc); 917 qdisc_tree_decrease_qlen(cl->qdisc, len); 918 } 919 920 static void 921 hfsc_adjust_levels(struct hfsc_class *cl) 922 { 923 struct hfsc_class *p; 924 unsigned int level; 925 926 do { 927 level = 0; 928 list_for_each_entry(p, &cl->children, siblings) { 929 if (p->level >= level) 930 level = p->level + 1; 931 } 932 cl->level = level; 933 } while ((cl = cl->cl_parent) != NULL); 934 } 935 936 static inline unsigned int 937 hfsc_hash(u32 h) 938 { 939 h ^= h >> 8; 940 h ^= h >> 4; 941 942 return h & (HFSC_HSIZE - 1); 943 } 944 945 static inline struct hfsc_class * 946 hfsc_find_class(u32 classid, struct Qdisc *sch) 947 { 948 struct hfsc_sched *q = qdisc_priv(sch); 949 struct hfsc_class *cl; 950 951 list_for_each_entry(cl, &q->clhash[hfsc_hash(classid)], hlist) { 952 if (cl->classid == classid) 953 return cl; 954 } 955 return NULL; 956 } 957 958 static void 959 hfsc_change_rsc(struct hfsc_class *cl, struct tc_service_curve *rsc, 960 u64 cur_time) 961 { 962 sc2isc(rsc, &cl->cl_rsc); 963 rtsc_init(&cl->cl_deadline, &cl->cl_rsc, cur_time, cl->cl_cumul); 964 cl->cl_eligible = cl->cl_deadline; 965 if (cl->cl_rsc.sm1 <= cl->cl_rsc.sm2) { 966 cl->cl_eligible.dx = 0; 967 cl->cl_eligible.dy = 0; 968 } 969 cl->cl_flags |= HFSC_RSC; 970 } 971 972 static void 973 hfsc_change_fsc(struct hfsc_class *cl, struct tc_service_curve *fsc) 974 { 975 sc2isc(fsc, &cl->cl_fsc); 976 rtsc_init(&cl->cl_virtual, &cl->cl_fsc, cl->cl_vt, cl->cl_total); 977 cl->cl_flags |= HFSC_FSC; 978 } 979 980 static void 981 hfsc_change_usc(struct hfsc_class *cl, struct tc_service_curve *usc, 982 u64 cur_time) 983 { 984 sc2isc(usc, &cl->cl_usc); 985 rtsc_init(&cl->cl_ulimit, &cl->cl_usc, cur_time, cl->cl_total); 986 cl->cl_flags |= HFSC_USC; 987 } 988 989 static const struct nla_policy hfsc_policy[TCA_HFSC_MAX + 1] = { 990 [TCA_HFSC_RSC] = { .len = sizeof(struct tc_service_curve) }, 991 [TCA_HFSC_FSC] = { .len = sizeof(struct tc_service_curve) }, 992 [TCA_HFSC_USC] = { .len = sizeof(struct tc_service_curve) }, 993 }; 994 995 static int 996 hfsc_change_class(struct Qdisc *sch, u32 classid, u32 parentid, 997 struct nlattr **tca, unsigned long *arg) 998 { 999 struct hfsc_sched *q = qdisc_priv(sch); 1000 struct hfsc_class *cl = (struct hfsc_class *)*arg; 1001 struct hfsc_class *parent = NULL; 1002 struct nlattr *opt = tca[TCA_OPTIONS]; 1003 struct nlattr *tb[TCA_HFSC_MAX + 1]; 1004 struct tc_service_curve *rsc = NULL, *fsc = NULL, *usc = NULL; 1005 u64 cur_time; 1006 int err; 1007 1008 if (opt == NULL) 1009 return -EINVAL; 1010 1011 err = nla_parse_nested(tb, TCA_HFSC_MAX, opt, hfsc_policy); 1012 if (err < 0) 1013 return err; 1014 1015 if (tb[TCA_HFSC_RSC]) { 1016 rsc = nla_data(tb[TCA_HFSC_RSC]); 1017 if (rsc->m1 == 0 && rsc->m2 == 0) 1018 rsc = NULL; 1019 } 1020 1021 if (tb[TCA_HFSC_FSC]) { 1022 fsc = nla_data(tb[TCA_HFSC_FSC]); 1023 if (fsc->m1 == 0 && fsc->m2 == 0) 1024 fsc = NULL; 1025 } 1026 1027 if (tb[TCA_HFSC_USC]) { 1028 usc = nla_data(tb[TCA_HFSC_USC]); 1029 if (usc->m1 == 0 && usc->m2 == 0) 1030 usc = NULL; 1031 } 1032 1033 if (cl != NULL) { 1034 if (parentid) { 1035 if (cl->cl_parent && cl->cl_parent->classid != parentid) 1036 return -EINVAL; 1037 if (cl->cl_parent == NULL && parentid != TC_H_ROOT) 1038 return -EINVAL; 1039 } 1040 cur_time = psched_get_time(); 1041 1042 sch_tree_lock(sch); 1043 if (rsc != NULL) 1044 hfsc_change_rsc(cl, rsc, cur_time); 1045 if (fsc != NULL) 1046 hfsc_change_fsc(cl, fsc); 1047 if (usc != NULL) 1048 hfsc_change_usc(cl, usc, cur_time); 1049 1050 if (cl->qdisc->q.qlen != 0) { 1051 if (cl->cl_flags & HFSC_RSC) 1052 update_ed(cl, qdisc_peek_len(cl->qdisc)); 1053 if (cl->cl_flags & HFSC_FSC) 1054 update_vf(cl, 0, cur_time); 1055 } 1056 sch_tree_unlock(sch); 1057 1058 if (tca[TCA_RATE]) 1059 gen_replace_estimator(&cl->bstats, &cl->rate_est, 1060 &sch->dev->queue_lock, 1061 tca[TCA_RATE]); 1062 return 0; 1063 } 1064 1065 if (parentid == TC_H_ROOT) 1066 return -EEXIST; 1067 1068 parent = &q->root; 1069 if (parentid) { 1070 parent = hfsc_find_class(parentid, sch); 1071 if (parent == NULL) 1072 return -ENOENT; 1073 } 1074 1075 if (classid == 0 || TC_H_MAJ(classid ^ sch->handle) != 0) 1076 return -EINVAL; 1077 if (hfsc_find_class(classid, sch)) 1078 return -EEXIST; 1079 1080 if (rsc == NULL && fsc == NULL) 1081 return -EINVAL; 1082 1083 cl = kzalloc(sizeof(struct hfsc_class), GFP_KERNEL); 1084 if (cl == NULL) 1085 return -ENOBUFS; 1086 1087 if (rsc != NULL) 1088 hfsc_change_rsc(cl, rsc, 0); 1089 if (fsc != NULL) 1090 hfsc_change_fsc(cl, fsc); 1091 if (usc != NULL) 1092 hfsc_change_usc(cl, usc, 0); 1093 1094 cl->refcnt = 1; 1095 cl->classid = classid; 1096 cl->sched = q; 1097 cl->cl_parent = parent; 1098 cl->qdisc = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops, classid); 1099 if (cl->qdisc == NULL) 1100 cl->qdisc = &noop_qdisc; 1101 INIT_LIST_HEAD(&cl->children); 1102 cl->vt_tree = RB_ROOT; 1103 cl->cf_tree = RB_ROOT; 1104 1105 sch_tree_lock(sch); 1106 list_add_tail(&cl->hlist, &q->clhash[hfsc_hash(classid)]); 1107 list_add_tail(&cl->siblings, &parent->children); 1108 if (parent->level == 0) 1109 hfsc_purge_queue(sch, parent); 1110 hfsc_adjust_levels(parent); 1111 cl->cl_pcvtoff = parent->cl_cvtoff; 1112 sch_tree_unlock(sch); 1113 1114 if (tca[TCA_RATE]) 1115 gen_new_estimator(&cl->bstats, &cl->rate_est, 1116 &sch->dev->queue_lock, tca[TCA_RATE]); 1117 *arg = (unsigned long)cl; 1118 return 0; 1119 } 1120 1121 static void 1122 hfsc_destroy_class(struct Qdisc *sch, struct hfsc_class *cl) 1123 { 1124 struct hfsc_sched *q = qdisc_priv(sch); 1125 1126 tcf_destroy_chain(cl->filter_list); 1127 qdisc_destroy(cl->qdisc); 1128 gen_kill_estimator(&cl->bstats, &cl->rate_est); 1129 if (cl != &q->root) 1130 kfree(cl); 1131 } 1132 1133 static int 1134 hfsc_delete_class(struct Qdisc *sch, unsigned long arg) 1135 { 1136 struct hfsc_sched *q = qdisc_priv(sch); 1137 struct hfsc_class *cl = (struct hfsc_class *)arg; 1138 1139 if (cl->level > 0 || cl->filter_cnt > 0 || cl == &q->root) 1140 return -EBUSY; 1141 1142 sch_tree_lock(sch); 1143 1144 list_del(&cl->siblings); 1145 hfsc_adjust_levels(cl->cl_parent); 1146 1147 hfsc_purge_queue(sch, cl); 1148 list_del(&cl->hlist); 1149 1150 if (--cl->refcnt == 0) 1151 hfsc_destroy_class(sch, cl); 1152 1153 sch_tree_unlock(sch); 1154 return 0; 1155 } 1156 1157 static struct hfsc_class * 1158 hfsc_classify(struct sk_buff *skb, struct Qdisc *sch, int *qerr) 1159 { 1160 struct hfsc_sched *q = qdisc_priv(sch); 1161 struct hfsc_class *cl; 1162 struct tcf_result res; 1163 struct tcf_proto *tcf; 1164 int result; 1165 1166 if (TC_H_MAJ(skb->priority ^ sch->handle) == 0 && 1167 (cl = hfsc_find_class(skb->priority, sch)) != NULL) 1168 if (cl->level == 0) 1169 return cl; 1170 1171 *qerr = NET_XMIT_BYPASS; 1172 tcf = q->root.filter_list; 1173 while (tcf && (result = tc_classify(skb, tcf, &res)) >= 0) { 1174 #ifdef CONFIG_NET_CLS_ACT 1175 switch (result) { 1176 case TC_ACT_QUEUED: 1177 case TC_ACT_STOLEN: 1178 *qerr = NET_XMIT_SUCCESS; 1179 case TC_ACT_SHOT: 1180 return NULL; 1181 } 1182 #endif 1183 if ((cl = (struct hfsc_class *)res.class) == NULL) { 1184 if ((cl = hfsc_find_class(res.classid, sch)) == NULL) 1185 break; /* filter selected invalid classid */ 1186 } 1187 1188 if (cl->level == 0) 1189 return cl; /* hit leaf class */ 1190 1191 /* apply inner filter chain */ 1192 tcf = cl->filter_list; 1193 } 1194 1195 /* classification failed, try default class */ 1196 cl = hfsc_find_class(TC_H_MAKE(TC_H_MAJ(sch->handle), q->defcls), sch); 1197 if (cl == NULL || cl->level > 0) 1198 return NULL; 1199 1200 return cl; 1201 } 1202 1203 static int 1204 hfsc_graft_class(struct Qdisc *sch, unsigned long arg, struct Qdisc *new, 1205 struct Qdisc **old) 1206 { 1207 struct hfsc_class *cl = (struct hfsc_class *)arg; 1208 1209 if (cl == NULL) 1210 return -ENOENT; 1211 if (cl->level > 0) 1212 return -EINVAL; 1213 if (new == NULL) { 1214 new = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops, 1215 cl->classid); 1216 if (new == NULL) 1217 new = &noop_qdisc; 1218 } 1219 1220 sch_tree_lock(sch); 1221 hfsc_purge_queue(sch, cl); 1222 *old = xchg(&cl->qdisc, new); 1223 sch_tree_unlock(sch); 1224 return 0; 1225 } 1226 1227 static struct Qdisc * 1228 hfsc_class_leaf(struct Qdisc *sch, unsigned long arg) 1229 { 1230 struct hfsc_class *cl = (struct hfsc_class *)arg; 1231 1232 if (cl != NULL && cl->level == 0) 1233 return cl->qdisc; 1234 1235 return NULL; 1236 } 1237 1238 static void 1239 hfsc_qlen_notify(struct Qdisc *sch, unsigned long arg) 1240 { 1241 struct hfsc_class *cl = (struct hfsc_class *)arg; 1242 1243 if (cl->qdisc->q.qlen == 0) { 1244 update_vf(cl, 0, 0); 1245 set_passive(cl); 1246 } 1247 } 1248 1249 static unsigned long 1250 hfsc_get_class(struct Qdisc *sch, u32 classid) 1251 { 1252 struct hfsc_class *cl = hfsc_find_class(classid, sch); 1253 1254 if (cl != NULL) 1255 cl->refcnt++; 1256 1257 return (unsigned long)cl; 1258 } 1259 1260 static void 1261 hfsc_put_class(struct Qdisc *sch, unsigned long arg) 1262 { 1263 struct hfsc_class *cl = (struct hfsc_class *)arg; 1264 1265 if (--cl->refcnt == 0) 1266 hfsc_destroy_class(sch, cl); 1267 } 1268 1269 static unsigned long 1270 hfsc_bind_tcf(struct Qdisc *sch, unsigned long parent, u32 classid) 1271 { 1272 struct hfsc_class *p = (struct hfsc_class *)parent; 1273 struct hfsc_class *cl = hfsc_find_class(classid, sch); 1274 1275 if (cl != NULL) { 1276 if (p != NULL && p->level <= cl->level) 1277 return 0; 1278 cl->filter_cnt++; 1279 } 1280 1281 return (unsigned long)cl; 1282 } 1283 1284 static void 1285 hfsc_unbind_tcf(struct Qdisc *sch, unsigned long arg) 1286 { 1287 struct hfsc_class *cl = (struct hfsc_class *)arg; 1288 1289 cl->filter_cnt--; 1290 } 1291 1292 static struct tcf_proto ** 1293 hfsc_tcf_chain(struct Qdisc *sch, unsigned long arg) 1294 { 1295 struct hfsc_sched *q = qdisc_priv(sch); 1296 struct hfsc_class *cl = (struct hfsc_class *)arg; 1297 1298 if (cl == NULL) 1299 cl = &q->root; 1300 1301 return &cl->filter_list; 1302 } 1303 1304 static int 1305 hfsc_dump_sc(struct sk_buff *skb, int attr, struct internal_sc *sc) 1306 { 1307 struct tc_service_curve tsc; 1308 1309 tsc.m1 = sm2m(sc->sm1); 1310 tsc.d = dx2d(sc->dx); 1311 tsc.m2 = sm2m(sc->sm2); 1312 NLA_PUT(skb, attr, sizeof(tsc), &tsc); 1313 1314 return skb->len; 1315 1316 nla_put_failure: 1317 return -1; 1318 } 1319 1320 static inline int 1321 hfsc_dump_curves(struct sk_buff *skb, struct hfsc_class *cl) 1322 { 1323 if ((cl->cl_flags & HFSC_RSC) && 1324 (hfsc_dump_sc(skb, TCA_HFSC_RSC, &cl->cl_rsc) < 0)) 1325 goto nla_put_failure; 1326 1327 if ((cl->cl_flags & HFSC_FSC) && 1328 (hfsc_dump_sc(skb, TCA_HFSC_FSC, &cl->cl_fsc) < 0)) 1329 goto nla_put_failure; 1330 1331 if ((cl->cl_flags & HFSC_USC) && 1332 (hfsc_dump_sc(skb, TCA_HFSC_USC, &cl->cl_usc) < 0)) 1333 goto nla_put_failure; 1334 1335 return skb->len; 1336 1337 nla_put_failure: 1338 return -1; 1339 } 1340 1341 static int 1342 hfsc_dump_class(struct Qdisc *sch, unsigned long arg, struct sk_buff *skb, 1343 struct tcmsg *tcm) 1344 { 1345 struct hfsc_class *cl = (struct hfsc_class *)arg; 1346 struct nlattr *nest; 1347 1348 tcm->tcm_parent = cl->cl_parent ? cl->cl_parent->classid : TC_H_ROOT; 1349 tcm->tcm_handle = cl->classid; 1350 if (cl->level == 0) 1351 tcm->tcm_info = cl->qdisc->handle; 1352 1353 nest = nla_nest_start(skb, TCA_OPTIONS); 1354 if (nest == NULL) 1355 goto nla_put_failure; 1356 if (hfsc_dump_curves(skb, cl) < 0) 1357 goto nla_put_failure; 1358 nla_nest_end(skb, nest); 1359 return skb->len; 1360 1361 nla_put_failure: 1362 nla_nest_cancel(skb, nest); 1363 return -1; 1364 } 1365 1366 static int 1367 hfsc_dump_class_stats(struct Qdisc *sch, unsigned long arg, 1368 struct gnet_dump *d) 1369 { 1370 struct hfsc_class *cl = (struct hfsc_class *)arg; 1371 struct tc_hfsc_stats xstats; 1372 1373 cl->qstats.qlen = cl->qdisc->q.qlen; 1374 xstats.level = cl->level; 1375 xstats.period = cl->cl_vtperiod; 1376 xstats.work = cl->cl_total; 1377 xstats.rtwork = cl->cl_cumul; 1378 1379 if (gnet_stats_copy_basic(d, &cl->bstats) < 0 || 1380 gnet_stats_copy_rate_est(d, &cl->rate_est) < 0 || 1381 gnet_stats_copy_queue(d, &cl->qstats) < 0) 1382 return -1; 1383 1384 return gnet_stats_copy_app(d, &xstats, sizeof(xstats)); 1385 } 1386 1387 1388 1389 static void 1390 hfsc_walk(struct Qdisc *sch, struct qdisc_walker *arg) 1391 { 1392 struct hfsc_sched *q = qdisc_priv(sch); 1393 struct hfsc_class *cl; 1394 unsigned int i; 1395 1396 if (arg->stop) 1397 return; 1398 1399 for (i = 0; i < HFSC_HSIZE; i++) { 1400 list_for_each_entry(cl, &q->clhash[i], hlist) { 1401 if (arg->count < arg->skip) { 1402 arg->count++; 1403 continue; 1404 } 1405 if (arg->fn(sch, (unsigned long)cl, arg) < 0) { 1406 arg->stop = 1; 1407 return; 1408 } 1409 arg->count++; 1410 } 1411 } 1412 } 1413 1414 static void 1415 hfsc_schedule_watchdog(struct Qdisc *sch) 1416 { 1417 struct hfsc_sched *q = qdisc_priv(sch); 1418 struct hfsc_class *cl; 1419 u64 next_time = 0; 1420 1421 if ((cl = eltree_get_minel(q)) != NULL) 1422 next_time = cl->cl_e; 1423 if (q->root.cl_cfmin != 0) { 1424 if (next_time == 0 || next_time > q->root.cl_cfmin) 1425 next_time = q->root.cl_cfmin; 1426 } 1427 WARN_ON(next_time == 0); 1428 qdisc_watchdog_schedule(&q->watchdog, next_time); 1429 } 1430 1431 static int 1432 hfsc_init_qdisc(struct Qdisc *sch, struct nlattr *opt) 1433 { 1434 struct hfsc_sched *q = qdisc_priv(sch); 1435 struct tc_hfsc_qopt *qopt; 1436 unsigned int i; 1437 1438 if (opt == NULL || nla_len(opt) < sizeof(*qopt)) 1439 return -EINVAL; 1440 qopt = nla_data(opt); 1441 1442 q->defcls = qopt->defcls; 1443 for (i = 0; i < HFSC_HSIZE; i++) 1444 INIT_LIST_HEAD(&q->clhash[i]); 1445 q->eligible = RB_ROOT; 1446 INIT_LIST_HEAD(&q->droplist); 1447 skb_queue_head_init(&q->requeue); 1448 1449 q->root.refcnt = 1; 1450 q->root.classid = sch->handle; 1451 q->root.sched = q; 1452 q->root.qdisc = qdisc_create_dflt(sch->dev, &pfifo_qdisc_ops, 1453 sch->handle); 1454 if (q->root.qdisc == NULL) 1455 q->root.qdisc = &noop_qdisc; 1456 INIT_LIST_HEAD(&q->root.children); 1457 q->root.vt_tree = RB_ROOT; 1458 q->root.cf_tree = RB_ROOT; 1459 1460 list_add(&q->root.hlist, &q->clhash[hfsc_hash(q->root.classid)]); 1461 1462 qdisc_watchdog_init(&q->watchdog, sch); 1463 1464 return 0; 1465 } 1466 1467 static int 1468 hfsc_change_qdisc(struct Qdisc *sch, struct nlattr *opt) 1469 { 1470 struct hfsc_sched *q = qdisc_priv(sch); 1471 struct tc_hfsc_qopt *qopt; 1472 1473 if (opt == NULL || nla_len(opt) < sizeof(*qopt)) 1474 return -EINVAL; 1475 qopt = nla_data(opt); 1476 1477 sch_tree_lock(sch); 1478 q->defcls = qopt->defcls; 1479 sch_tree_unlock(sch); 1480 1481 return 0; 1482 } 1483 1484 static void 1485 hfsc_reset_class(struct hfsc_class *cl) 1486 { 1487 cl->cl_total = 0; 1488 cl->cl_cumul = 0; 1489 cl->cl_d = 0; 1490 cl->cl_e = 0; 1491 cl->cl_vt = 0; 1492 cl->cl_vtadj = 0; 1493 cl->cl_vtoff = 0; 1494 cl->cl_cvtmin = 0; 1495 cl->cl_cvtmax = 0; 1496 cl->cl_cvtoff = 0; 1497 cl->cl_pcvtoff = 0; 1498 cl->cl_vtperiod = 0; 1499 cl->cl_parentperiod = 0; 1500 cl->cl_f = 0; 1501 cl->cl_myf = 0; 1502 cl->cl_myfadj = 0; 1503 cl->cl_cfmin = 0; 1504 cl->cl_nactive = 0; 1505 1506 cl->vt_tree = RB_ROOT; 1507 cl->cf_tree = RB_ROOT; 1508 qdisc_reset(cl->qdisc); 1509 1510 if (cl->cl_flags & HFSC_RSC) 1511 rtsc_init(&cl->cl_deadline, &cl->cl_rsc, 0, 0); 1512 if (cl->cl_flags & HFSC_FSC) 1513 rtsc_init(&cl->cl_virtual, &cl->cl_fsc, 0, 0); 1514 if (cl->cl_flags & HFSC_USC) 1515 rtsc_init(&cl->cl_ulimit, &cl->cl_usc, 0, 0); 1516 } 1517 1518 static void 1519 hfsc_reset_qdisc(struct Qdisc *sch) 1520 { 1521 struct hfsc_sched *q = qdisc_priv(sch); 1522 struct hfsc_class *cl; 1523 unsigned int i; 1524 1525 for (i = 0; i < HFSC_HSIZE; i++) { 1526 list_for_each_entry(cl, &q->clhash[i], hlist) 1527 hfsc_reset_class(cl); 1528 } 1529 __skb_queue_purge(&q->requeue); 1530 q->eligible = RB_ROOT; 1531 INIT_LIST_HEAD(&q->droplist); 1532 qdisc_watchdog_cancel(&q->watchdog); 1533 sch->q.qlen = 0; 1534 } 1535 1536 static void 1537 hfsc_destroy_qdisc(struct Qdisc *sch) 1538 { 1539 struct hfsc_sched *q = qdisc_priv(sch); 1540 struct hfsc_class *cl, *next; 1541 unsigned int i; 1542 1543 for (i = 0; i < HFSC_HSIZE; i++) { 1544 list_for_each_entry_safe(cl, next, &q->clhash[i], hlist) 1545 hfsc_destroy_class(sch, cl); 1546 } 1547 __skb_queue_purge(&q->requeue); 1548 qdisc_watchdog_cancel(&q->watchdog); 1549 } 1550 1551 static int 1552 hfsc_dump_qdisc(struct Qdisc *sch, struct sk_buff *skb) 1553 { 1554 struct hfsc_sched *q = qdisc_priv(sch); 1555 unsigned char *b = skb_tail_pointer(skb); 1556 struct tc_hfsc_qopt qopt; 1557 1558 qopt.defcls = q->defcls; 1559 NLA_PUT(skb, TCA_OPTIONS, sizeof(qopt), &qopt); 1560 return skb->len; 1561 1562 nla_put_failure: 1563 nlmsg_trim(skb, b); 1564 return -1; 1565 } 1566 1567 static int 1568 hfsc_enqueue(struct sk_buff *skb, struct Qdisc *sch) 1569 { 1570 struct hfsc_class *cl; 1571 unsigned int len; 1572 int err; 1573 1574 cl = hfsc_classify(skb, sch, &err); 1575 if (cl == NULL) { 1576 if (err == NET_XMIT_BYPASS) 1577 sch->qstats.drops++; 1578 kfree_skb(skb); 1579 return err; 1580 } 1581 1582 len = skb->len; 1583 err = cl->qdisc->enqueue(skb, cl->qdisc); 1584 if (unlikely(err != NET_XMIT_SUCCESS)) { 1585 cl->qstats.drops++; 1586 sch->qstats.drops++; 1587 return err; 1588 } 1589 1590 if (cl->qdisc->q.qlen == 1) 1591 set_active(cl, len); 1592 1593 cl->bstats.packets++; 1594 cl->bstats.bytes += len; 1595 sch->bstats.packets++; 1596 sch->bstats.bytes += len; 1597 sch->q.qlen++; 1598 1599 return NET_XMIT_SUCCESS; 1600 } 1601 1602 static struct sk_buff * 1603 hfsc_dequeue(struct Qdisc *sch) 1604 { 1605 struct hfsc_sched *q = qdisc_priv(sch); 1606 struct hfsc_class *cl; 1607 struct sk_buff *skb; 1608 u64 cur_time; 1609 unsigned int next_len; 1610 int realtime = 0; 1611 1612 if (sch->q.qlen == 0) 1613 return NULL; 1614 if ((skb = __skb_dequeue(&q->requeue))) 1615 goto out; 1616 1617 cur_time = psched_get_time(); 1618 1619 /* 1620 * if there are eligible classes, use real-time criteria. 1621 * find the class with the minimum deadline among 1622 * the eligible classes. 1623 */ 1624 if ((cl = eltree_get_mindl(q, cur_time)) != NULL) { 1625 realtime = 1; 1626 } else { 1627 /* 1628 * use link-sharing criteria 1629 * get the class with the minimum vt in the hierarchy 1630 */ 1631 cl = vttree_get_minvt(&q->root, cur_time); 1632 if (cl == NULL) { 1633 sch->qstats.overlimits++; 1634 hfsc_schedule_watchdog(sch); 1635 return NULL; 1636 } 1637 } 1638 1639 skb = cl->qdisc->dequeue(cl->qdisc); 1640 if (skb == NULL) { 1641 if (net_ratelimit()) 1642 printk("HFSC: Non-work-conserving qdisc ?\n"); 1643 return NULL; 1644 } 1645 1646 update_vf(cl, skb->len, cur_time); 1647 if (realtime) 1648 cl->cl_cumul += skb->len; 1649 1650 if (cl->qdisc->q.qlen != 0) { 1651 if (cl->cl_flags & HFSC_RSC) { 1652 /* update ed */ 1653 next_len = qdisc_peek_len(cl->qdisc); 1654 if (realtime) 1655 update_ed(cl, next_len); 1656 else 1657 update_d(cl, next_len); 1658 } 1659 } else { 1660 /* the class becomes passive */ 1661 set_passive(cl); 1662 } 1663 1664 out: 1665 sch->flags &= ~TCQ_F_THROTTLED; 1666 sch->q.qlen--; 1667 1668 return skb; 1669 } 1670 1671 static int 1672 hfsc_requeue(struct sk_buff *skb, struct Qdisc *sch) 1673 { 1674 struct hfsc_sched *q = qdisc_priv(sch); 1675 1676 __skb_queue_head(&q->requeue, skb); 1677 sch->q.qlen++; 1678 sch->qstats.requeues++; 1679 return NET_XMIT_SUCCESS; 1680 } 1681 1682 static unsigned int 1683 hfsc_drop(struct Qdisc *sch) 1684 { 1685 struct hfsc_sched *q = qdisc_priv(sch); 1686 struct hfsc_class *cl; 1687 unsigned int len; 1688 1689 list_for_each_entry(cl, &q->droplist, dlist) { 1690 if (cl->qdisc->ops->drop != NULL && 1691 (len = cl->qdisc->ops->drop(cl->qdisc)) > 0) { 1692 if (cl->qdisc->q.qlen == 0) { 1693 update_vf(cl, 0, 0); 1694 set_passive(cl); 1695 } else { 1696 list_move_tail(&cl->dlist, &q->droplist); 1697 } 1698 cl->qstats.drops++; 1699 sch->qstats.drops++; 1700 sch->q.qlen--; 1701 return len; 1702 } 1703 } 1704 return 0; 1705 } 1706 1707 static const struct Qdisc_class_ops hfsc_class_ops = { 1708 .change = hfsc_change_class, 1709 .delete = hfsc_delete_class, 1710 .graft = hfsc_graft_class, 1711 .leaf = hfsc_class_leaf, 1712 .qlen_notify = hfsc_qlen_notify, 1713 .get = hfsc_get_class, 1714 .put = hfsc_put_class, 1715 .bind_tcf = hfsc_bind_tcf, 1716 .unbind_tcf = hfsc_unbind_tcf, 1717 .tcf_chain = hfsc_tcf_chain, 1718 .dump = hfsc_dump_class, 1719 .dump_stats = hfsc_dump_class_stats, 1720 .walk = hfsc_walk 1721 }; 1722 1723 static struct Qdisc_ops hfsc_qdisc_ops __read_mostly = { 1724 .id = "hfsc", 1725 .init = hfsc_init_qdisc, 1726 .change = hfsc_change_qdisc, 1727 .reset = hfsc_reset_qdisc, 1728 .destroy = hfsc_destroy_qdisc, 1729 .dump = hfsc_dump_qdisc, 1730 .enqueue = hfsc_enqueue, 1731 .dequeue = hfsc_dequeue, 1732 .requeue = hfsc_requeue, 1733 .drop = hfsc_drop, 1734 .cl_ops = &hfsc_class_ops, 1735 .priv_size = sizeof(struct hfsc_sched), 1736 .owner = THIS_MODULE 1737 }; 1738 1739 static int __init 1740 hfsc_init(void) 1741 { 1742 return register_qdisc(&hfsc_qdisc_ops); 1743 } 1744 1745 static void __exit 1746 hfsc_cleanup(void) 1747 { 1748 unregister_qdisc(&hfsc_qdisc_ops); 1749 } 1750 1751 MODULE_LICENSE("GPL"); 1752 module_init(hfsc_init); 1753 module_exit(hfsc_cleanup); 1754