1 /* $KAME: qop_hfsc.c,v 1.4 2000/10/18 09:15:19 kjc Exp $ */ 2 /* 3 * Copyright (C) 1999-2000 4 * Sony Computer Science Laboratories, Inc. All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 2. Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * 15 * THIS SOFTWARE IS PROVIDED BY SONY CSL AND CONTRIBUTORS ``AS IS'' AND 16 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 18 * ARE DISCLAIMED. IN NO EVENT SHALL SONY CSL OR CONTRIBUTORS BE LIABLE 19 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 20 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 21 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 22 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 23 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 24 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 25 * SUCH DAMAGE. 26 */ 27 28 #include <sys/param.h> 29 #include <sys/socket.h> 30 #include <sys/sockio.h> 31 #include <sys/ioctl.h> 32 #include <sys/fcntl.h> 33 #include <net/if.h> 34 #include <netinet/in.h> 35 #include <arpa/inet.h> 36 37 #include <stdio.h> 38 #include <stdlib.h> 39 #include <unistd.h> 40 #include <stddef.h> 41 #include <string.h> 42 #include <ctype.h> 43 #include <errno.h> 44 #include <syslog.h> 45 #include <netdb.h> 46 47 #include <altq/altq.h> 48 #include <altq/altq_hfsc.h> 49 #include "altq_qop.h" 50 #include "qop_hfsc.h" 51 52 static int read_sc(int *argcp, char ***argvp, 53 int *type, u_int *m1, u_int *d, u_int *m2); 54 static int qop_hfsc_enable_hook(struct ifinfo *ifinfo); 55 static int qop_hfsc_delete_class_hook(struct classinfo *clinfo); 56 static int validate_sc(struct service_curve *sc); 57 58 static void gsc_add_sc(struct gen_sc *gsc, struct service_curve *sc); 59 static void gsc_sub_sc(struct gen_sc *gsc, struct service_curve *sc); 60 static int is_gsc_under_sc(struct gen_sc *gsc, struct service_curve *sc); 61 static void gsc_destroy(struct gen_sc *gsc); 62 static struct segment *gsc_getentry(struct gen_sc *gsc, double x); 63 static int gsc_add_seg(struct gen_sc *gsc, 64 double x, double y, double d, double m); 65 static int gsc_sub_seg(struct gen_sc *gsc, 66 double x, double y, double d, double m); 67 static void gsc_compress(struct gen_sc *gsc); 68 static double sc_x2y(struct service_curve *sc, double x); 69 70 static int hfsc_attach(struct ifinfo *ifinfo); 71 static int hfsc_detach(struct ifinfo *ifinfo); 72 static int hfsc_clear(struct ifinfo *ifinfo); 73 static int hfsc_enable(struct ifinfo *ifinfo); 74 static int hfsc_disable(struct ifinfo *ifinfo); 75 static int hfsc_add_class(struct classinfo *clinfo); 76 static int hfsc_modify_class(struct classinfo *clinfo, void *arg); 77 static int hfsc_delete_class(struct classinfo *clinfo); 78 static int hfsc_add_filter(struct fltrinfo *fltrinfo); 79 static int hfsc_delete_filter(struct fltrinfo *fltrinfo); 80 81 #define HFSC_DEVICE "/dev/altq/hfsc" 82 83 static int hfsc_fd = -1; 84 static int hfsc_refcount = 0; 85 86 static struct qdisc_ops hfsc_qdisc = { 87 ALTQT_HFSC, 88 "hfsc", 89 hfsc_attach, 90 hfsc_detach, 91 hfsc_clear, 92 hfsc_enable, 93 hfsc_disable, 94 hfsc_add_class, 95 hfsc_modify_class, 96 hfsc_delete_class, 97 hfsc_add_filter, 98 hfsc_delete_filter, 99 }; 100 101 #define EQUAL(s1, s2) (strcmp((s1), (s2)) == 0) 102 103 /* 104 * parser interface 105 */ 106 int 107 hfsc_interface_parser(const char *ifname, int argc, char **argv) 108 { 109 u_int bandwidth = 100000000; /* 100Mbps */ 110 u_int tbrsize = 0; 111 int flags = 0; 112 113 /* 114 * process options 115 */ 116 while (argc > 0) { 117 if (EQUAL(*argv, "bandwidth")) { 118 argc--; argv++; 119 if (argc > 0) 120 bandwidth = atobps(*argv); 121 } else if (EQUAL(*argv, "tbrsize")) { 122 argc--; argv++; 123 if (argc > 0) 124 tbrsize = atobytes(*argv); 125 } else if (EQUAL(*argv, "hfsc")) { 126 /* just skip */ 127 } else { 128 LOG(LOG_ERR, 0, "Unknown keyword '%s'\n", argv); 129 return (0); 130 } 131 argc--; argv++; 132 } 133 134 if (qcmd_tbr_register(ifname, bandwidth, tbrsize) != 0) 135 return (0); 136 137 if (qcmd_hfsc_add_if(ifname, bandwidth, flags) != 0) 138 return (0); 139 return (1); 140 } 141 142 int 143 hfsc_class_parser(const char *ifname, const char *class_name, 144 const char *parent_name, int argc, char **argv) 145 { 146 u_int m1, d, m2, rm1, rd, rm2, fm1, fd, fm2; 147 int qlimit = 50; 148 int flags = 0, admission = 0; 149 int type = 0, error; 150 151 rm1 = rd = rm2 = fm1 = fd = fm2 = 0; 152 while (argc > 0) { 153 if (*argv[0] == '[') { 154 if (read_sc(&argc, &argv, &type, &m1, &d, &m2) != 0) { 155 LOG(LOG_ERR, 0, 156 "Bad service curve in %s, line %d\n", 157 altqconfigfile, line_no); 158 return (0); 159 } 160 if (type & HFSC_REALTIMESC) { 161 rm1 = m1; rd = d; rm2 = m2; 162 } 163 if (type & HFSC_LINKSHARINGSC) { 164 fm1 = m1; fd = d; fm2 = m2; 165 } 166 } else if (EQUAL(*argv, "pshare")) { 167 argc--; argv++; 168 if (argc > 0) { 169 struct ifinfo *ifinfo; 170 u_int pshare; 171 172 pshare = (u_int)strtoul(*argv, NULL, 0); 173 if ((ifinfo = ifname2ifinfo(ifname)) != NULL) { 174 fm2 = ifinfo->bandwidth / 100 * pshare; 175 type |= HFSC_LINKSHARINGSC; 176 } 177 } 178 } else if (EQUAL(*argv, "grate")) { 179 argc--; argv++; 180 if (argc > 0) { 181 rm2 = atobps(*argv); 182 type |= HFSC_REALTIMESC; 183 } 184 } else if (EQUAL(*argv, "qlimit")) { 185 argc--; argv++; 186 if (argc > 0) 187 qlimit = strtoul(*argv, NULL, 0); 188 } else if (EQUAL(*argv, "default")) { 189 flags |= HFCF_DEFAULTCLASS; 190 } else if (EQUAL(*argv, "admission")) { 191 argc--; argv++; 192 if (argc > 0) { 193 if (EQUAL(*argv, "guaranteed") 194 || EQUAL(*argv, "cntlload")) 195 admission = 1; 196 else if (EQUAL(*argv, "none")) { 197 /* nothing */ 198 } else { 199 LOG(LOG_ERR, 0, 200 "unknown admission type - %s, line %d\n", 201 *argv, line_no); 202 return (0); 203 } 204 } 205 } else if (EQUAL(*argv, "red")) { 206 flags |= HFCF_RED; 207 } else if (EQUAL(*argv, "ecn")) { 208 flags |= HFCF_ECN; 209 } else if (EQUAL(*argv, "rio")) { 210 flags |= HFCF_RIO; 211 } else if (EQUAL(*argv, "cleardscp")) { 212 flags |= HFCF_CLEARDSCP; 213 } else { 214 LOG(LOG_ERR, 0, 215 "Unknown keyword '%s' in %s, line %d\n", 216 *argv, altqconfigfile, line_no); 217 return (0); 218 } 219 220 argc--; argv++; 221 } 222 223 if (type == 0) { 224 LOG(LOG_ERR, 0, 225 "hfsc: service curve not specified in %s, line %d\n", 226 altqconfigfile, line_no); 227 return (0); 228 } 229 230 if ((flags & HFCF_ECN) && (flags & (HFCF_RED|HFCF_RIO)) == 0) 231 flags |= HFCF_RED; 232 233 /* 234 * if the link-sharing service curve is diffrent from 235 * the real-time service curve, we first create a class with the 236 * smaller service curve and then modify the other service curve. 237 */ 238 if (rm2 <= fm2) { 239 m1 = rm1; d = rd; m2 = rm2; 240 } else { 241 m1 = fm1; d = fd; m2 = fm2; 242 } 243 error = qcmd_hfsc_add_class(ifname, class_name, parent_name, 244 m1, d, m2, qlimit, flags); 245 246 if (error == 0 && (rm1 != fm1 || rd != fd || rm2 != fm2)) { 247 if (rm2 <= fm2) { 248 m1 = fm1; d = fd; m2 = fm2; type = HFSC_LINKSHARINGSC; 249 } else { 250 m1 = rm1; d = rd; m2 = rm2; type = HFSC_REALTIMESC; 251 } 252 error = qcmd_hfsc_modify_class(ifname, class_name, 253 m1, d, m2, type); 254 } 255 256 if (error == 0 && admission) { 257 /* this is a special class for rsvp */ 258 struct ifinfo *ifinfo = ifname2ifinfo(ifname); 259 struct classinfo *clinfo = clname2clinfo(ifinfo, class_name); 260 261 if (ifinfo->resv_class != NULL) { 262 LOG(LOG_ERR, 0, 263 "more than one admission class specified: %s\n", 264 class_name); 265 return (0); 266 } 267 ifinfo->resv_class = clinfo; 268 } 269 270 if (error) { 271 LOG(LOG_ERR, errno, "hfsc_class_parser: %s\n", 272 qoperror(error)); 273 return (0); 274 } 275 return (1); 276 } 277 278 /* 279 * read service curve parameters 280 * '[' <type> <m1> <d> <m2> ']' 281 * type := "sc", "rt", or "ls" 282 */ 283 static int 284 read_sc(int *argcp, char ***argvp, int *type, u_int *m1, u_int *d, u_int *m2) 285 { 286 int argc = *argcp; 287 char **argv = *argvp; 288 char *cp; 289 290 cp = *argv; 291 if (*cp++ != '[') 292 return (-1); 293 if (*cp == '\0') { 294 cp = *++argv; --argc; 295 } 296 if (*cp == 's' || *cp == 'S') 297 *type = HFSC_DEFAULTSC; 298 else if (*cp == 'r' || *cp == 'R') 299 *type = HFSC_REALTIMESC; 300 else if (*cp == 'l' || *cp == 'L') 301 *type = HFSC_LINKSHARINGSC; 302 else 303 return (-1); 304 cp = *++argv; --argc; 305 *m1 = atobps(cp); 306 cp = *++argv; --argc; 307 *d = (u_int)strtoul(cp, NULL, 0); 308 cp = *++argv; --argc; 309 *m2 = atobps(cp); 310 if (strchr(cp, ']') == NULL) { 311 cp = *++argv; --argc; 312 if (*cp != ']') 313 return (-1); 314 } 315 *argcp = argc; 316 *argvp = argv; 317 return (0); 318 } 319 320 /* 321 * qcmd api 322 */ 323 int 324 qcmd_hfsc_add_if(const char *ifname, u_int bandwidth, int flags) 325 { 326 int error; 327 328 error = qop_hfsc_add_if(NULL, ifname, bandwidth, flags); 329 if (error != 0) 330 LOG(LOG_ERR, errno, "%s: can't add hfsc on interface '%s'\n", 331 qoperror(error), ifname); 332 return (error); 333 } 334 335 int 336 qcmd_hfsc_add_class(const char *ifname, const char *class_name, 337 const char *parent_name, u_int m1, u_int d, u_int m2, 338 int qlimit, int flags) 339 { 340 struct ifinfo *ifinfo; 341 struct classinfo *parent = NULL; 342 struct service_curve sc; 343 int error = 0; 344 345 if ((ifinfo = ifname2ifinfo(ifname)) == NULL) 346 error = QOPERR_BADIF; 347 348 if (error == 0 && 349 (parent = clname2clinfo(ifinfo, parent_name)) == NULL) 350 error = QOPERR_BADCLASS; 351 352 sc.m1 = m1; 353 sc.d = d; 354 sc.m2 = m2; 355 356 if (error == 0) 357 error = qop_hfsc_add_class(NULL, class_name, ifinfo, parent, 358 &sc, qlimit, flags); 359 if (error != 0) 360 LOG(LOG_ERR, errno, 361 "hfsc: %s: can't add class '%s' on interface '%s'\n", 362 qoperror(error), class_name, ifname); 363 return (error); 364 } 365 366 int 367 qcmd_hfsc_modify_class(const char *ifname, const char *class_name, 368 u_int m1, u_int d, u_int m2, int sctype) 369 { 370 struct ifinfo *ifinfo; 371 struct classinfo *clinfo; 372 struct service_curve sc; 373 374 if ((ifinfo = ifname2ifinfo(ifname)) == NULL) 375 return (QOPERR_BADIF); 376 377 if ((clinfo = clname2clinfo(ifinfo, class_name)) == NULL) 378 return (QOPERR_BADCLASS); 379 380 sc.m1 = m1; 381 sc.d = d; 382 sc.m2 = m2; 383 384 return qop_hfsc_modify_class(clinfo, &sc, sctype); 385 } 386 387 /* 388 * qop api 389 */ 390 int 391 qop_hfsc_add_if(struct ifinfo **rp, const char *ifname, 392 u_int bandwidth, int flags) 393 { 394 struct ifinfo *ifinfo = NULL; 395 struct hfsc_ifinfo *hfsc_ifinfo = NULL; 396 struct service_curve sc; 397 int error; 398 399 if ((hfsc_ifinfo = calloc(1, sizeof(*hfsc_ifinfo))) == NULL) 400 return (QOPERR_NOMEM); 401 402 error = qop_add_if(&ifinfo, ifname, bandwidth, 403 &hfsc_qdisc, hfsc_ifinfo); 404 if (error != 0) 405 goto err_ret; 406 407 /* set enable hook */ 408 ifinfo->enable_hook = qop_hfsc_enable_hook; 409 410 /* create a dummy root class */ 411 sc.m1 = bandwidth; 412 sc.d = 0; 413 sc.m2 = bandwidth; 414 if ((error = qop_hfsc_add_class(&hfsc_ifinfo->root_class, "root", 415 ifinfo, NULL, &sc, 0, 0)) != 0) { 416 LOG(LOG_ERR, errno, 417 "hfsc: %s: can't create dummy root class on %s!\n", 418 qoperror(error), ifname); 419 (void)qop_delete_if(ifinfo); 420 return (QOPERR_CLASS); 421 } 422 423 if (rp != NULL) 424 *rp = ifinfo; 425 return (0); 426 427 err_ret: 428 if (hfsc_ifinfo != NULL) { 429 free(hfsc_ifinfo); 430 if (ifinfo != NULL) 431 ifinfo->private = NULL; 432 } 433 return (error); 434 } 435 436 #define is_sc_null(sc) (((sc) == NULL) || ((sc)->m1 == 0 && (sc)->m2 == 0)) 437 438 int 439 qop_hfsc_add_class(struct classinfo **rp, const char *class_name, 440 struct ifinfo *ifinfo, struct classinfo *parent, 441 struct service_curve *sc, int qlimit, int flags) 442 { 443 struct classinfo *clinfo; 444 struct hfsc_ifinfo *hfsc_ifinfo; 445 struct hfsc_classinfo *hfsc_clinfo = NULL, *parent_clinfo = NULL; 446 int error; 447 448 hfsc_ifinfo = ifinfo->private; 449 if ((flags & HFCF_DEFAULTCLASS) && hfsc_ifinfo->default_class != NULL) 450 return (QOPERR_CLASS_INVAL); 451 452 if (validate_sc(sc) != 0) 453 return (QOPERR_INVAL); 454 455 /* admission control */ 456 if (parent != NULL && !is_sc_null(sc)) { 457 parent_clinfo = parent->private; 458 gsc_add_sc(&parent_clinfo->gen_rsc, sc); 459 gsc_add_sc(&parent_clinfo->gen_fsc, sc); 460 if (!is_gsc_under_sc(&parent_clinfo->gen_rsc, 461 &parent_clinfo->rsc) || 462 !is_gsc_under_sc(&parent_clinfo->gen_fsc, 463 &parent_clinfo->fsc)) { 464 /* admission control failure */ 465 error = QOPERR_ADMISSION_NOBW; 466 goto err_ret; 467 } 468 } 469 470 if ((hfsc_clinfo = calloc(1, sizeof(*hfsc_clinfo))) == NULL) { 471 error = QOPERR_NOMEM; 472 goto err_ret; 473 } 474 475 hfsc_clinfo->rsc = *sc; 476 hfsc_clinfo->fsc = *sc; 477 LIST_INIT(&hfsc_clinfo->gen_rsc); 478 LIST_INIT(&hfsc_clinfo->gen_fsc); 479 hfsc_clinfo->qlimit = qlimit; 480 hfsc_clinfo->flags = flags; 481 482 if ((error = qop_add_class(&clinfo, class_name, ifinfo, parent, 483 hfsc_clinfo)) != 0) 484 goto err_ret; 485 486 /* set delete hook */ 487 clinfo->delete_hook = qop_hfsc_delete_class_hook; 488 489 if (flags & HFCF_DEFAULTCLASS) 490 hfsc_ifinfo->default_class = clinfo; 491 492 if (parent == NULL) { 493 /* 494 * if this is a root class, reserve 20% of the real-time 495 * bandwidth for safety. 496 * many network cards are not able to saturate the wire, 497 * and if we allocate real-time traffic more than the 498 * maximum sending rate of the card, hfsc is no longer 499 * able to meet the delay bound requirements. 500 */ 501 hfsc_clinfo->rsc.m1 = hfsc_clinfo->rsc.m1 / 10 * 8; 502 hfsc_clinfo->rsc.m2 = hfsc_clinfo->rsc.m2 / 10 * 8; 503 } 504 505 if (rp != NULL) 506 *rp = clinfo; 507 return (0); 508 509 err_ret: 510 /* cancel admission control */ 511 if (parent != NULL && !is_sc_null(sc)) { 512 gsc_sub_sc(&parent_clinfo->gen_rsc, sc); 513 gsc_sub_sc(&parent_clinfo->gen_fsc, sc); 514 } 515 516 if (hfsc_clinfo != NULL) { 517 free(hfsc_clinfo); 518 clinfo->private = NULL; 519 } 520 521 return (error); 522 } 523 524 /* 525 * this is called from qop_delete_class() before a class is destroyed 526 * for discipline specific cleanup. 527 */ 528 static int 529 qop_hfsc_delete_class_hook(struct classinfo *clinfo) 530 { 531 struct hfsc_classinfo *hfsc_clinfo, *parent_clinfo; 532 533 hfsc_clinfo = clinfo->private; 534 535 /* cancel admission control */ 536 if (clinfo->parent != NULL) { 537 parent_clinfo = clinfo->parent->private; 538 539 gsc_sub_sc(&parent_clinfo->gen_rsc, &hfsc_clinfo->rsc); 540 gsc_sub_sc(&parent_clinfo->gen_fsc, &hfsc_clinfo->fsc); 541 } 542 543 gsc_destroy(&hfsc_clinfo->gen_rsc); 544 gsc_destroy(&hfsc_clinfo->gen_fsc); 545 return (0); 546 } 547 548 int 549 qop_hfsc_modify_class(struct classinfo *clinfo, 550 struct service_curve *sc, int sctype) 551 { 552 struct hfsc_classinfo *hfsc_clinfo, *parent_clinfo; 553 struct service_curve rsc, fsc; 554 int error; 555 556 if (validate_sc(sc) != 0) 557 return (QOPERR_INVAL); 558 559 hfsc_clinfo = clinfo->private; 560 if (clinfo->parent == NULL) 561 return (QOPERR_CLASS_INVAL); 562 parent_clinfo = clinfo->parent->private; 563 564 /* save old service curves */ 565 rsc = hfsc_clinfo->rsc; 566 fsc = hfsc_clinfo->fsc; 567 568 /* admission control */ 569 if (sctype & HFSC_REALTIMESC) { 570 if (!is_gsc_under_sc(&hfsc_clinfo->gen_rsc, sc)) { 571 /* admission control failure */ 572 return (QOPERR_ADMISSION); 573 } 574 575 gsc_sub_sc(&parent_clinfo->gen_rsc, &hfsc_clinfo->rsc); 576 gsc_add_sc(&parent_clinfo->gen_rsc, sc); 577 if (!is_gsc_under_sc(&parent_clinfo->gen_rsc, 578 &parent_clinfo->rsc)) { 579 /* admission control failure */ 580 gsc_sub_sc(&parent_clinfo->gen_rsc, sc); 581 gsc_add_sc(&parent_clinfo->gen_rsc, &hfsc_clinfo->rsc); 582 return (QOPERR_ADMISSION_NOBW); 583 } 584 hfsc_clinfo->rsc = *sc; 585 } 586 if (sctype & HFSC_LINKSHARINGSC) { 587 if (!is_gsc_under_sc(&hfsc_clinfo->gen_fsc, sc)) { 588 /* admission control failure */ 589 return (QOPERR_ADMISSION); 590 } 591 592 gsc_sub_sc(&parent_clinfo->gen_fsc, &hfsc_clinfo->fsc); 593 gsc_add_sc(&parent_clinfo->gen_fsc, sc); 594 if (!is_gsc_under_sc(&parent_clinfo->gen_fsc, 595 &parent_clinfo->fsc)) { 596 /* admission control failure */ 597 gsc_sub_sc(&parent_clinfo->gen_fsc, sc); 598 gsc_add_sc(&parent_clinfo->gen_fsc, &hfsc_clinfo->fsc); 599 return (QOPERR_ADMISSION_NOBW); 600 } 601 hfsc_clinfo->fsc = *sc; 602 } 603 604 error = qop_modify_class(clinfo, (void *)((long)sctype)); 605 if (error == 0) 606 return (0); 607 608 /* modify failed!, restore the old service curves */ 609 if (sctype & HFSC_REALTIMESC) { 610 gsc_sub_sc(&parent_clinfo->gen_rsc, sc); 611 gsc_add_sc(&parent_clinfo->gen_rsc, &rsc); 612 hfsc_clinfo->rsc = rsc; 613 } 614 if (sctype & HFSC_LINKSHARINGSC) { 615 gsc_sub_sc(&parent_clinfo->gen_fsc, sc); 616 gsc_add_sc(&parent_clinfo->gen_fsc, &fsc); 617 hfsc_clinfo->fsc = fsc; 618 } 619 return (error); 620 } 621 622 /* 623 * sanity check at enabling hfsc: 624 * 1. there must one default class for an interface 625 * 2. the default class must be a leaf class 626 * 3. an internal class should not have filters 627 * (rule 2 and 3 are due to the fact that the hfsc link-sharing algorithm 628 * do not schedule internal classes.) 629 */ 630 static int 631 qop_hfsc_enable_hook(struct ifinfo *ifinfo) 632 { 633 struct hfsc_ifinfo *hfsc_ifinfo; 634 struct classinfo *clinfo; 635 636 hfsc_ifinfo = ifinfo->private; 637 if (hfsc_ifinfo->default_class == NULL) { 638 LOG(LOG_ERR, 0, "hfsc: no default class on interface %s!\n", 639 ifinfo->ifname); 640 return (QOPERR_CLASS); 641 } else if (hfsc_ifinfo->default_class->child != NULL) { 642 LOG(LOG_ERR, 0, "hfsc: default class on %s must be a leaf!\n", 643 ifinfo->ifname); 644 return (QOPERR_CLASS); 645 } 646 647 LIST_FOREACH(clinfo, &ifinfo->cllist, next) { 648 if (clinfo->child != NULL && !LIST_EMPTY(&clinfo->fltrlist)) { 649 LOG(LOG_ERR, 0, "hfsc: internal class \"%s\" should not have a filter!\n", 650 clinfo->clname); 651 return (QOPERR_CLASS); 652 } 653 } 654 655 return (0); 656 } 657 658 static int 659 validate_sc(struct service_curve *sc) 660 { 661 /* the 1st segment of a concave curve must be zero */ 662 if (sc->m1 < sc->m2 && sc->m1 != 0) { 663 LOG(LOG_ERR, 0, "m1 must be 0 for convex!\n"); 664 return (-1); 665 } 666 return (0); 667 } 668 669 /* 670 * admission control using generalized service curve 671 */ 672 #define INFINITY 1e500 /* IEEE: positive infinity */ 673 674 /* add a new service curve to a generilized service curve */ 675 static void 676 gsc_add_sc(struct gen_sc *gsc, struct service_curve *sc) 677 { 678 if (is_sc_null(sc)) 679 return; 680 if (sc->d != 0) 681 gsc_add_seg(gsc, 0, 0, (double)sc->d, (double)sc->m1); 682 gsc_add_seg(gsc, (double)sc->d, 0, INFINITY, (double)sc->m2); 683 } 684 685 /* subtract a service curve from a generilized service curve */ 686 static void 687 gsc_sub_sc(struct gen_sc *gsc, struct service_curve *sc) 688 { 689 if (is_sc_null(sc)) 690 return; 691 if (sc->d != 0) 692 gsc_sub_seg(gsc, 0, 0, (double)sc->d, (double)sc->m1); 693 gsc_sub_seg(gsc, (double)sc->d, 0, INFINITY, (double)sc->m2); 694 } 695 696 /* 697 * check whether all points of a generalized service curve have 698 * their y-coordinates no larger than a given two-piece linear 699 * service curve. 700 */ 701 static int 702 is_gsc_under_sc(struct gen_sc *gsc, struct service_curve *sc) 703 { 704 struct segment *s, *last, *end; 705 double y; 706 707 if (is_sc_null(sc)) { 708 if (LIST_EMPTY(gsc)) 709 return (1); 710 LIST_FOREACH(s, gsc, _next) { 711 if (s->m != 0) 712 return (0); 713 } 714 return (1); 715 } 716 /* 717 * gsc has a dummy entry at the end with x = INFINITY. 718 * loop through up to this dummy entry. 719 */ 720 end = gsc_getentry(gsc, INFINITY); 721 if (end == NULL) 722 return (1); 723 last = NULL; 724 for (s = LIST_FIRST(gsc); s != end; s = LIST_NEXT(s, _next)) { 725 if (s->y > sc_x2y(sc, s->x)) 726 return (0); 727 last = s; 728 } 729 /* last now holds the real last segment */ 730 if (last == NULL) 731 return (1); 732 if (last->m > sc->m2) 733 return (0); 734 if (last->x < sc->d && last->m > sc->m1) { 735 y = last->y + (sc->d - last->x) * last->m; 736 if (y > sc_x2y(sc, sc->d)) 737 return (0); 738 } 739 return (1); 740 } 741 742 static void 743 gsc_destroy(struct gen_sc *gsc) 744 { 745 struct segment *s; 746 747 while ((s = LIST_FIRST(gsc)) != NULL) { 748 LIST_REMOVE(s, _next); 749 free(s); 750 } 751 } 752 753 /* 754 * return a segment entry starting at x. 755 * if gsc has no entry starting at x, a new entry is created at x. 756 */ 757 static struct segment * 758 gsc_getentry(struct gen_sc *gsc, double x) 759 { 760 struct segment *new, *prev, *s; 761 762 prev = NULL; 763 LIST_FOREACH(s, gsc, _next) { 764 if (s->x == x) 765 return (s); /* matching entry found */ 766 else if (s->x < x) 767 prev = s; 768 else 769 break; 770 } 771 772 /* we have to create a new entry */ 773 if ((new = calloc(1, sizeof(struct segment))) == NULL) 774 return (NULL); 775 776 new->x = x; 777 if (x == INFINITY || s == NULL) 778 new->d = 0; 779 else if (s->x == INFINITY) 780 new->d = INFINITY; 781 else 782 new->d = s->x - x; 783 if (prev == NULL) { 784 /* insert the new entry at the head of the list */ 785 new->y = 0; 786 new->m = 0; 787 LIST_INSERT_HEAD(gsc, new, _next); 788 } else { 789 /* 790 * the start point intersects with the segment pointed by 791 * prev. divide prev into 2 segments 792 */ 793 if (x == INFINITY) { 794 prev->d = INFINITY; 795 if (prev->m == 0) 796 new->y = prev->y; 797 else 798 new->y = INFINITY; 799 } else { 800 prev->d = x - prev->x; 801 new->y = prev->d * prev->m + prev->y; 802 } 803 new->m = prev->m; 804 LIST_INSERT_AFTER(prev, new, _next); 805 } 806 return (new); 807 } 808 809 /* add a segment to a generalized service curve */ 810 static int 811 gsc_add_seg(struct gen_sc *gsc, double x, double y, double d, double m) 812 { 813 struct segment *start, *end, *s; 814 double x2; 815 816 if (d == INFINITY) 817 x2 = INFINITY; 818 else 819 x2 = x + d; 820 start = gsc_getentry(gsc, x); 821 end = gsc_getentry(gsc, x2); 822 if (start == NULL || end == NULL) 823 return (-1); 824 825 for (s = start; s != end; s = LIST_NEXT(s, _next)) { 826 s->m += m; 827 s->y += y + (s->x - x) * m; 828 } 829 830 end = gsc_getentry(gsc, INFINITY); 831 for (; s != end; s = LIST_NEXT(s, _next)) { 832 s->y += m * d; 833 } 834 835 return (0); 836 } 837 838 /* subtract a segment from a generalized service curve */ 839 static int 840 gsc_sub_seg(struct gen_sc *gsc, double x, double y, double d, double m) 841 { 842 if (gsc_add_seg(gsc, x, y, d, -m) < 0) 843 return (-1); 844 gsc_compress(gsc); 845 return (0); 846 } 847 848 /* 849 * collapse adjacent segments with the same slope 850 */ 851 static void 852 gsc_compress(struct gen_sc *gsc) 853 { 854 struct segment *s, *next; 855 856 again: 857 LIST_FOREACH(s, gsc, _next) { 858 859 if ((next = LIST_NEXT(s, _next)) == NULL) { 860 if (LIST_FIRST(gsc) == s && s->m == 0) { 861 /* 862 * if this is the only entry and its 863 * slope is 0, it's a remaining dummy 864 * entry. we can discard it. 865 */ 866 LIST_REMOVE(s, _next); 867 free(s); 868 } 869 break; 870 } 871 872 if (s->x == next->x) { 873 /* discard this entry */ 874 LIST_REMOVE(s, _next); 875 free(s); 876 goto again; 877 } else if (s->m == next->m) { 878 /* join the two entries */ 879 if (s->d != INFINITY && next->d != INFINITY) 880 s->d += next->d; 881 LIST_REMOVE(next, _next); 882 free(next); 883 goto again; 884 } 885 } 886 } 887 888 /* get y-projection of a service curve */ 889 static double 890 sc_x2y(struct service_curve *sc, double x) 891 { 892 double y; 893 894 if (x <= (double)sc->d) 895 /* y belongs to the 1st segment */ 896 y = x * (double)sc->m1; 897 else 898 /* y belongs to the 2nd segment */ 899 y = (double)sc->d * (double)sc->m1 900 + (x - (double)sc->d) * (double)sc->m2; 901 return (y); 902 } 903 904 /* 905 * system call interfaces for qdisc_ops 906 */ 907 static int 908 hfsc_attach(struct ifinfo *ifinfo) 909 { 910 struct hfsc_attach attach; 911 912 if (hfsc_fd < 0 && 913 (hfsc_fd = open(HFSC_DEVICE, O_RDWR)) < 0 && 914 (hfsc_fd = open_module(HFSC_DEVICE, O_RDWR)) < 0) { 915 LOG(LOG_ERR, errno, "HFSC open\n"); 916 return (QOPERR_SYSCALL); 917 } 918 919 hfsc_refcount++; 920 memset(&attach, 0, sizeof(attach)); 921 strncpy(attach.iface.hfsc_ifname, ifinfo->ifname, IFNAMSIZ); 922 attach.bandwidth = ifinfo->bandwidth; 923 924 if (ioctl(hfsc_fd, HFSC_IF_ATTACH, &attach) < 0) 925 return (QOPERR_SYSCALL); 926 return (0); 927 } 928 929 static int 930 hfsc_detach(struct ifinfo *ifinfo) 931 { 932 struct hfsc_interface iface; 933 934 memset(&iface, 0, sizeof(iface)); 935 strncpy(iface.hfsc_ifname, ifinfo->ifname, IFNAMSIZ); 936 937 if (ioctl(hfsc_fd, HFSC_IF_DETACH, &iface) < 0) 938 return (QOPERR_SYSCALL); 939 940 if (--hfsc_refcount == 0) { 941 close(hfsc_fd); 942 hfsc_fd = -1; 943 } 944 return (0); 945 } 946 947 static int 948 hfsc_clear(struct ifinfo *ifinfo) 949 { 950 struct hfsc_interface iface; 951 952 memset(&iface, 0, sizeof(iface)); 953 strncpy(iface.hfsc_ifname, ifinfo->ifname, IFNAMSIZ); 954 955 if (ioctl(hfsc_fd, HFSC_CLEAR_HIERARCHY, &iface) < 0) 956 return (QOPERR_SYSCALL); 957 return (0); 958 } 959 960 static int 961 hfsc_enable(struct ifinfo *ifinfo) 962 { 963 struct hfsc_interface iface; 964 965 memset(&iface, 0, sizeof(iface)); 966 strncpy(iface.hfsc_ifname, ifinfo->ifname, IFNAMSIZ); 967 968 if (ioctl(hfsc_fd, HFSC_ENABLE, &iface) < 0) 969 return (QOPERR_SYSCALL); 970 return (0); 971 } 972 973 static int 974 hfsc_disable(struct ifinfo *ifinfo) 975 { 976 struct hfsc_interface iface; 977 978 memset(&iface, 0, sizeof(iface)); 979 strncpy(iface.hfsc_ifname, ifinfo->ifname, IFNAMSIZ); 980 981 if (ioctl(hfsc_fd, HFSC_DISABLE, &iface) < 0) 982 return (QOPERR_SYSCALL); 983 return (0); 984 } 985 986 static int 987 hfsc_add_class(struct classinfo *clinfo) 988 { 989 struct hfsc_add_class class_add; 990 struct hfsc_classinfo *hfsc_clinfo; 991 struct hfsc_ifinfo *hfsc_ifinfo; 992 993 /* root class is a dummy class */ 994 if (clinfo->parent == NULL) { 995 clinfo->handle = HFSC_ROOTCLASS_HANDLE; 996 return (0); 997 } 998 999 hfsc_ifinfo = clinfo->ifinfo->private; 1000 hfsc_clinfo = clinfo->private; 1001 1002 memset(&class_add, 0, sizeof(class_add)); 1003 strncpy(class_add.iface.hfsc_ifname, clinfo->ifinfo->ifname, IFNAMSIZ); 1004 if (clinfo->parent == hfsc_ifinfo->root_class) 1005 class_add.parent_handle = HFSC_ROOTCLASS_HANDLE; 1006 else 1007 class_add.parent_handle = clinfo->parent->handle; 1008 class_add.service_curve = hfsc_clinfo->rsc; 1009 class_add.qlimit = hfsc_clinfo->qlimit; 1010 class_add.flags = hfsc_clinfo->flags; 1011 if (ioctl(hfsc_fd, HFSC_ADD_CLASS, &class_add) < 0) { 1012 clinfo->handle = HFSC_NULLCLASS_HANDLE; 1013 return (QOPERR_SYSCALL); 1014 } 1015 clinfo->handle = class_add.class_handle; 1016 return (0); 1017 } 1018 1019 static int 1020 hfsc_modify_class(struct classinfo *clinfo, void *arg) 1021 { 1022 struct hfsc_modify_class class_mod; 1023 struct hfsc_classinfo *hfsc_clinfo; 1024 long sctype; 1025 1026 sctype = (long)arg; 1027 hfsc_clinfo = clinfo->private; 1028 1029 memset(&class_mod, 0, sizeof(class_mod)); 1030 strncpy(class_mod.iface.hfsc_ifname, clinfo->ifinfo->ifname, IFNAMSIZ); 1031 class_mod.class_handle = clinfo->handle; 1032 if (sctype & HFSC_REALTIMESC) 1033 class_mod.service_curve = hfsc_clinfo->rsc; 1034 else if (sctype & HFSC_LINKSHARINGSC) 1035 class_mod.service_curve = hfsc_clinfo->fsc; 1036 else 1037 return (QOPERR_INVAL); 1038 class_mod.sctype = sctype; 1039 1040 if (ioctl(hfsc_fd, HFSC_MOD_CLASS, &class_mod) < 0) 1041 return (QOPERR_SYSCALL); 1042 return (0); 1043 } 1044 1045 static int 1046 hfsc_delete_class(struct classinfo *clinfo) 1047 { 1048 struct hfsc_delete_class class_delete; 1049 1050 if (clinfo->handle == HFSC_NULLCLASS_HANDLE || 1051 clinfo->handle == HFSC_ROOTCLASS_HANDLE) 1052 return (0); 1053 1054 memset(&class_delete, 0, sizeof(class_delete)); 1055 strncpy(class_delete.iface.hfsc_ifname, clinfo->ifinfo->ifname, 1056 IFNAMSIZ); 1057 class_delete.class_handle = clinfo->handle; 1058 1059 if (ioctl(hfsc_fd, HFSC_DEL_CLASS, &class_delete) < 0) 1060 return (QOPERR_SYSCALL); 1061 return (0); 1062 } 1063 1064 static int 1065 hfsc_add_filter(struct fltrinfo *fltrinfo) 1066 { 1067 struct hfsc_add_filter fltr_add; 1068 1069 memset(&fltr_add, 0, sizeof(fltr_add)); 1070 strncpy(fltr_add.iface.hfsc_ifname, fltrinfo->clinfo->ifinfo->ifname, 1071 IFNAMSIZ); 1072 fltr_add.class_handle = fltrinfo->clinfo->handle; 1073 fltr_add.filter = fltrinfo->fltr; 1074 1075 if (ioctl(hfsc_fd, HFSC_ADD_FILTER, &fltr_add) < 0) 1076 return (QOPERR_SYSCALL); 1077 fltrinfo->handle = fltr_add.filter_handle; 1078 return (0); 1079 } 1080 1081 static int 1082 hfsc_delete_filter(struct fltrinfo *fltrinfo) 1083 { 1084 struct hfsc_delete_filter fltr_del; 1085 1086 memset(&fltr_del, 0, sizeof(fltr_del)); 1087 strncpy(fltr_del.iface.hfsc_ifname, fltrinfo->clinfo->ifinfo->ifname, 1088 IFNAMSIZ); 1089 fltr_del.filter_handle = fltrinfo->handle; 1090 1091 if (ioctl(hfsc_fd, HFSC_DEL_FILTER, &fltr_del) < 0) 1092 return (QOPERR_SYSCALL); 1093 return (0); 1094 } 1095 1096 1097