1 /* $NetBSD: qop_hfsc.c,v 1.6 2002/09/08 09:28:23 itojun Exp $ */ 2 /* $KAME: qop_hfsc.c,v 1.8 2002/09/08 09:08:13 kjc Exp $ */ 3 /* 4 * Copyright (C) 1999-2000 5 * Sony Computer Science Laboratories, Inc. All rights reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 1. Redistributions of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 16 * THIS SOFTWARE IS PROVIDED BY SONY CSL AND CONTRIBUTORS ``AS IS'' AND 17 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 19 * ARE DISCLAIMED. IN NO EVENT SHALL SONY CSL OR CONTRIBUTORS BE LIABLE 20 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 21 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 22 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 23 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 24 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 25 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 26 * SUCH DAMAGE. 27 */ 28 29 #include <sys/param.h> 30 #include <sys/socket.h> 31 #include <sys/sockio.h> 32 #include <sys/ioctl.h> 33 #include <sys/fcntl.h> 34 #include <net/if.h> 35 #include <netinet/in.h> 36 #include <arpa/inet.h> 37 38 #include <stdio.h> 39 #include <stdlib.h> 40 #include <unistd.h> 41 #include <stddef.h> 42 #include <string.h> 43 #include <ctype.h> 44 #include <errno.h> 45 #include <syslog.h> 46 #include <netdb.h> 47 #include <math.h> 48 49 #include <altq/altq.h> 50 #include <altq/altq_hfsc.h> 51 #include "altq_qop.h" 52 #include "qop_hfsc.h" 53 54 static int read_sc(int *, char ***, int *, u_int *, u_int *, u_int *); 55 static int qop_hfsc_enable_hook(struct ifinfo *); 56 static int qop_hfsc_delete_class_hook(struct classinfo *); 57 static int validate_sc(struct service_curve *); 58 59 static void gsc_add_sc(struct gen_sc *, struct service_curve *); 60 static void gsc_sub_sc(struct gen_sc *, struct service_curve *); 61 static int is_gsc_under_sc(struct gen_sc *, struct service_curve *); 62 static void gsc_destroy(struct gen_sc *); 63 static struct segment *gsc_getentry(struct gen_sc *, double); 64 static int gsc_add_seg(struct gen_sc *, double, double, double, double); 65 static int gsc_sub_seg(struct gen_sc *, double, double, double, double); 66 static void gsc_compress(struct gen_sc *); 67 static double sc_x2y(struct service_curve *, double); 68 69 static int hfsc_attach(struct ifinfo *); 70 static int hfsc_detach(struct ifinfo *); 71 static int hfsc_clear(struct ifinfo *); 72 static int hfsc_enable(struct ifinfo *); 73 static int hfsc_disable(struct ifinfo *); 74 static int hfsc_add_class(struct classinfo *); 75 static int hfsc_modify_class(struct classinfo *, void *); 76 static int hfsc_delete_class(struct classinfo *); 77 static int hfsc_add_filter(struct fltrinfo *); 78 static int hfsc_delete_filter(struct fltrinfo *); 79 80 #define HFSC_DEVICE "/dev/altq/hfsc" 81 82 static int hfsc_fd = -1; 83 static int hfsc_refcount = 0; 84 85 static struct qdisc_ops hfsc_qdisc = { 86 ALTQT_HFSC, 87 "hfsc", 88 hfsc_attach, 89 hfsc_detach, 90 hfsc_clear, 91 hfsc_enable, 92 hfsc_disable, 93 hfsc_add_class, 94 hfsc_modify_class, 95 hfsc_delete_class, 96 hfsc_add_filter, 97 hfsc_delete_filter, 98 }; 99 100 #define EQUAL(s1, s2) (strcmp((s1), (s2)) == 0) 101 102 /* 103 * parser interface 104 */ 105 int 106 hfsc_interface_parser(const char *ifname, int argc, char **argv) 107 { 108 u_int bandwidth = 100000000; /* 100Mbps */ 109 u_int tbrsize = 0; 110 int flags = 0; 111 112 /* 113 * process options 114 */ 115 while (argc > 0) { 116 if (EQUAL(*argv, "bandwidth")) { 117 argc--; argv++; 118 if (argc > 0) 119 bandwidth = atobps(*argv); 120 } else if (EQUAL(*argv, "tbrsize")) { 121 argc--; argv++; 122 if (argc > 0) 123 tbrsize = atobytes(*argv); 124 } else if (EQUAL(*argv, "hfsc")) { 125 /* just skip */ 126 } else { 127 LOG(LOG_ERR, 0, "Unknown keyword '%s'", *argv); 128 return (0); 129 } 130 argc--; argv++; 131 } 132 133 if (qcmd_tbr_register(ifname, bandwidth, tbrsize) != 0) 134 return (0); 135 136 if (qcmd_hfsc_add_if(ifname, bandwidth, flags) != 0) 137 return (0); 138 return (1); 139 } 140 141 int 142 hfsc_class_parser(const char *ifname, const char *class_name, 143 const char *parent_name, int argc, char **argv) 144 { 145 u_int m1, d, m2, rm1, rd, rm2, fm1, fd, fm2; 146 int qlimit = 50; 147 int flags = 0, admission = 0; 148 int type = 0, error; 149 150 rm1 = rd = rm2 = fm1 = fd = fm2 = 0; 151 while (argc > 0) { 152 if (*argv[0] == '[') { 153 if (read_sc(&argc, &argv, &type, &m1, &d, &m2) != 0) { 154 LOG(LOG_ERR, 0, 155 "Bad service curve in %s, line %d", 156 altqconfigfile, line_no); 157 return (0); 158 } 159 if (type & HFSC_REALTIMESC) { 160 rm1 = m1; rd = d; rm2 = m2; 161 } 162 if (type & HFSC_LINKSHARINGSC) { 163 fm1 = m1; fd = d; fm2 = m2; 164 } 165 } else if (EQUAL(*argv, "pshare")) { 166 argc--; argv++; 167 if (argc > 0) { 168 struct ifinfo *ifinfo; 169 u_int pshare; 170 171 pshare = (u_int)strtoul(*argv, NULL, 0); 172 if ((ifinfo = ifname2ifinfo(ifname)) != NULL) { 173 fm2 = ifinfo->bandwidth / 100 * pshare; 174 type |= HFSC_LINKSHARINGSC; 175 } 176 } 177 } else if (EQUAL(*argv, "grate")) { 178 argc--; argv++; 179 if (argc > 0) { 180 rm2 = atobps(*argv); 181 type |= HFSC_REALTIMESC; 182 } 183 } else if (EQUAL(*argv, "qlimit")) { 184 argc--; argv++; 185 if (argc > 0) 186 qlimit = strtoul(*argv, NULL, 0); 187 } else if (EQUAL(*argv, "default")) { 188 flags |= HFCF_DEFAULTCLASS; 189 } else if (EQUAL(*argv, "admission")) { 190 argc--; argv++; 191 if (argc > 0) { 192 if (EQUAL(*argv, "guaranteed") 193 || EQUAL(*argv, "cntlload")) 194 admission = 1; 195 else if (EQUAL(*argv, "none")) { 196 /* nothing */ 197 } else { 198 LOG(LOG_ERR, 0, 199 "unknown admission type - %s, line %d", 200 *argv, line_no); 201 return (0); 202 } 203 } 204 } else if (EQUAL(*argv, "red")) { 205 flags |= HFCF_RED; 206 } else if (EQUAL(*argv, "ecn")) { 207 flags |= HFCF_ECN; 208 } else if (EQUAL(*argv, "rio")) { 209 flags |= HFCF_RIO; 210 } else if (EQUAL(*argv, "cleardscp")) { 211 flags |= HFCF_CLEARDSCP; 212 } else { 213 LOG(LOG_ERR, 0, 214 "Unknown keyword '%s' in %s, line %d", 215 *argv, altqconfigfile, line_no); 216 return (0); 217 } 218 219 argc--; argv++; 220 } 221 222 if (type == 0) { 223 LOG(LOG_ERR, 0, 224 "hfsc: service curve not specified in %s, line %d", 225 altqconfigfile, line_no); 226 return (0); 227 } 228 229 if ((flags & HFCF_ECN) && (flags & (HFCF_RED|HFCF_RIO)) == 0) 230 flags |= HFCF_RED; 231 232 /* 233 * if the link-sharing service curve is diffrent from 234 * the real-time service curve, we first create a class with the 235 * smaller service curve and then modify the other service curve. 236 */ 237 if (rm2 <= fm2) { 238 m1 = rm1; d = rd; m2 = rm2; 239 } else { 240 m1 = fm1; d = fd; m2 = fm2; 241 } 242 error = qcmd_hfsc_add_class(ifname, class_name, parent_name, 243 m1, d, m2, qlimit, flags); 244 245 if (error == 0 && (rm1 != fm1 || rd != fd || rm2 != fm2)) { 246 if (rm2 <= fm2) { 247 m1 = fm1; d = fd; m2 = fm2; type = HFSC_LINKSHARINGSC; 248 } else { 249 m1 = rm1; d = rd; m2 = rm2; type = HFSC_REALTIMESC; 250 } 251 error = qcmd_hfsc_modify_class(ifname, class_name, 252 m1, d, m2, type); 253 } 254 255 if (error == 0 && admission) { 256 /* this is a special class for rsvp */ 257 struct ifinfo *ifinfo = ifname2ifinfo(ifname); 258 struct classinfo *clinfo = clname2clinfo(ifinfo, class_name); 259 260 if (ifinfo->resv_class != NULL) { 261 LOG(LOG_ERR, 0, 262 "more than one admission class specified: %s", 263 class_name); 264 return (0); 265 } 266 ifinfo->resv_class = clinfo; 267 } 268 269 if (error) { 270 LOG(LOG_ERR, errno, "hfsc_class_parser: %s", 271 qoperror(error)); 272 return (0); 273 } 274 return (1); 275 } 276 277 /* 278 * read service curve parameters 279 * '[' <type> <m1> <d> <m2> ']' 280 * type := "sc", "rt", or "ls" 281 */ 282 static int 283 read_sc(int *argcp, char ***argvp, int *type, u_int *m1, u_int *d, u_int *m2) 284 { 285 int argc = *argcp; 286 char **argv = *argvp; 287 char *cp; 288 289 cp = *argv; 290 if (*cp++ != '[') 291 return (-1); 292 if (*cp == '\0') { 293 cp = *++argv; --argc; 294 } 295 if (*cp == 's' || *cp == 'S') 296 *type = HFSC_DEFAULTSC; 297 else if (*cp == 'r' || *cp == 'R') 298 *type = HFSC_REALTIMESC; 299 else if (*cp == 'l' || *cp == 'L') 300 *type = HFSC_LINKSHARINGSC; 301 else 302 return (-1); 303 cp = *++argv; --argc; 304 *m1 = atobps(cp); 305 cp = *++argv; --argc; 306 *d = (u_int)strtoul(cp, NULL, 0); 307 cp = *++argv; --argc; 308 *m2 = atobps(cp); 309 if (strchr(cp, ']') == NULL) { 310 cp = *++argv; --argc; 311 if (*cp != ']') 312 return (-1); 313 } 314 *argcp = argc; 315 *argvp = argv; 316 return (0); 317 } 318 319 /* 320 * qcmd api 321 */ 322 int 323 qcmd_hfsc_add_if(const char *ifname, u_int bandwidth, int flags) 324 { 325 int error; 326 327 error = qop_hfsc_add_if(NULL, ifname, bandwidth, flags); 328 if (error != 0) 329 LOG(LOG_ERR, errno, "%s: can't add hfsc on interface '%s'", 330 qoperror(error), ifname); 331 return (error); 332 } 333 334 int 335 qcmd_hfsc_add_class(const char *ifname, const char *class_name, 336 const char *parent_name, u_int m1, u_int d, u_int m2, 337 int qlimit, int flags) 338 { 339 struct ifinfo *ifinfo; 340 struct classinfo *parent = NULL; 341 struct service_curve sc; 342 int error = 0; 343 344 if ((ifinfo = ifname2ifinfo(ifname)) == NULL) 345 error = QOPERR_BADIF; 346 347 if (error == 0 && 348 (parent = clname2clinfo(ifinfo, parent_name)) == NULL) 349 error = QOPERR_BADCLASS; 350 351 sc.m1 = m1; 352 sc.d = d; 353 sc.m2 = m2; 354 355 if (error == 0) 356 error = qop_hfsc_add_class(NULL, class_name, ifinfo, parent, 357 &sc, qlimit, flags); 358 if (error != 0) 359 LOG(LOG_ERR, errno, 360 "hfsc: %s: can't add class '%s' on interface '%s'", 361 qoperror(error), class_name, ifname); 362 return (error); 363 } 364 365 int 366 qcmd_hfsc_modify_class(const char *ifname, const char *class_name, 367 u_int m1, u_int d, u_int m2, int sctype) 368 { 369 struct ifinfo *ifinfo; 370 struct classinfo *clinfo; 371 struct service_curve sc; 372 373 if ((ifinfo = ifname2ifinfo(ifname)) == NULL) 374 return (QOPERR_BADIF); 375 376 if ((clinfo = clname2clinfo(ifinfo, class_name)) == NULL) 377 return (QOPERR_BADCLASS); 378 379 sc.m1 = m1; 380 sc.d = d; 381 sc.m2 = m2; 382 383 return qop_hfsc_modify_class(clinfo, &sc, sctype); 384 } 385 386 /* 387 * qop api 388 */ 389 int 390 qop_hfsc_add_if(struct ifinfo **rp, const char *ifname, 391 u_int bandwidth, int flags) 392 { 393 struct ifinfo *ifinfo = NULL; 394 struct hfsc_ifinfo *hfsc_ifinfo = NULL; 395 struct service_curve sc; 396 int error; 397 398 if ((hfsc_ifinfo = calloc(1, sizeof(*hfsc_ifinfo))) == NULL) 399 return (QOPERR_NOMEM); 400 401 error = qop_add_if(&ifinfo, ifname, bandwidth, 402 &hfsc_qdisc, hfsc_ifinfo); 403 if (error != 0) 404 goto err_ret; 405 406 /* set enable hook */ 407 ifinfo->enable_hook = qop_hfsc_enable_hook; 408 409 /* create a dummy root class */ 410 sc.m1 = bandwidth; 411 sc.d = 0; 412 sc.m2 = bandwidth; 413 if ((error = qop_hfsc_add_class(&hfsc_ifinfo->root_class, "root", 414 ifinfo, NULL, &sc, 0, 0)) != 0) { 415 LOG(LOG_ERR, errno, 416 "hfsc: %s: can't create dummy root class on %s!", 417 qoperror(error), ifname); 418 (void)qop_delete_if(ifinfo); 419 return (QOPERR_CLASS); 420 } 421 422 if (rp != NULL) 423 *rp = ifinfo; 424 return (0); 425 426 err_ret: 427 if (hfsc_ifinfo != NULL) { 428 free(hfsc_ifinfo); 429 if (ifinfo != NULL) 430 ifinfo->private = NULL; 431 } 432 return (error); 433 } 434 435 #define is_sc_null(sc) (((sc) == NULL) || ((sc)->m1 == 0 && (sc)->m2 == 0)) 436 437 int 438 qop_hfsc_add_class(struct classinfo **rp, const char *class_name, 439 struct ifinfo *ifinfo, struct classinfo *parent, 440 struct service_curve *sc, int qlimit, int flags) 441 { 442 struct classinfo *clinfo; 443 struct hfsc_ifinfo *hfsc_ifinfo; 444 struct hfsc_classinfo *hfsc_clinfo = NULL, *parent_clinfo = NULL; 445 int error; 446 447 hfsc_ifinfo = ifinfo->private; 448 if ((flags & HFCF_DEFAULTCLASS) && hfsc_ifinfo->default_class != NULL) 449 return (QOPERR_CLASS_INVAL); 450 451 if (validate_sc(sc) != 0) 452 return (QOPERR_INVAL); 453 454 /* admission control */ 455 if (parent != NULL && !is_sc_null(sc)) { 456 parent_clinfo = parent->private; 457 gsc_add_sc(&parent_clinfo->gen_rsc, sc); 458 gsc_add_sc(&parent_clinfo->gen_fsc, sc); 459 if (!is_gsc_under_sc(&parent_clinfo->gen_rsc, 460 &parent_clinfo->rsc) || 461 !is_gsc_under_sc(&parent_clinfo->gen_fsc, 462 &parent_clinfo->fsc)) { 463 /* admission control failure */ 464 error = QOPERR_ADMISSION_NOBW; 465 goto err_ret; 466 } 467 } 468 469 if ((hfsc_clinfo = calloc(1, sizeof(*hfsc_clinfo))) == NULL) { 470 error = QOPERR_NOMEM; 471 goto err_ret; 472 } 473 474 hfsc_clinfo->rsc = *sc; 475 hfsc_clinfo->fsc = *sc; 476 LIST_INIT(&hfsc_clinfo->gen_rsc); 477 LIST_INIT(&hfsc_clinfo->gen_fsc); 478 hfsc_clinfo->qlimit = qlimit; 479 hfsc_clinfo->flags = flags; 480 481 if ((error = qop_add_class(&clinfo, class_name, ifinfo, parent, 482 hfsc_clinfo)) != 0) 483 goto err_ret; 484 485 /* set delete hook */ 486 clinfo->delete_hook = qop_hfsc_delete_class_hook; 487 488 if (flags & HFCF_DEFAULTCLASS) 489 hfsc_ifinfo->default_class = clinfo; 490 491 if (parent == NULL) { 492 /* 493 * if this is a root class, reserve 20% of the real-time 494 * bandwidth for safety. 495 * many network cards are not able to saturate the wire, 496 * and if we allocate real-time traffic more than the 497 * maximum sending rate of the card, hfsc is no longer 498 * able to meet the delay bound requirements. 499 */ 500 hfsc_clinfo->rsc.m1 = hfsc_clinfo->rsc.m1 / 10 * 8; 501 hfsc_clinfo->rsc.m2 = hfsc_clinfo->rsc.m2 / 10 * 8; 502 } 503 504 if (rp != NULL) 505 *rp = clinfo; 506 return (0); 507 508 err_ret: 509 /* cancel admission control */ 510 if (parent != NULL && !is_sc_null(sc)) { 511 gsc_sub_sc(&parent_clinfo->gen_rsc, sc); 512 gsc_sub_sc(&parent_clinfo->gen_fsc, sc); 513 } 514 515 if (hfsc_clinfo != NULL) { 516 free(hfsc_clinfo); 517 clinfo->private = NULL; 518 } 519 520 return (error); 521 } 522 523 /* 524 * this is called from qop_delete_class() before a class is destroyed 525 * for discipline specific cleanup. 526 */ 527 static int 528 qop_hfsc_delete_class_hook(struct classinfo *clinfo) 529 { 530 struct hfsc_classinfo *hfsc_clinfo, *parent_clinfo; 531 532 hfsc_clinfo = clinfo->private; 533 534 /* cancel admission control */ 535 if (clinfo->parent != NULL) { 536 parent_clinfo = clinfo->parent->private; 537 538 gsc_sub_sc(&parent_clinfo->gen_rsc, &hfsc_clinfo->rsc); 539 gsc_sub_sc(&parent_clinfo->gen_fsc, &hfsc_clinfo->fsc); 540 } 541 542 gsc_destroy(&hfsc_clinfo->gen_rsc); 543 gsc_destroy(&hfsc_clinfo->gen_fsc); 544 return (0); 545 } 546 547 int 548 qop_hfsc_modify_class(struct classinfo *clinfo, 549 struct service_curve *sc, int sctype) 550 { 551 struct hfsc_classinfo *hfsc_clinfo, *parent_clinfo; 552 struct service_curve rsc, fsc; 553 int error; 554 555 if (validate_sc(sc) != 0) 556 return (QOPERR_INVAL); 557 558 hfsc_clinfo = clinfo->private; 559 if (clinfo->parent == NULL) 560 return (QOPERR_CLASS_INVAL); 561 parent_clinfo = clinfo->parent->private; 562 563 /* save old service curves */ 564 rsc = hfsc_clinfo->rsc; 565 fsc = hfsc_clinfo->fsc; 566 567 /* admission control */ 568 if (sctype & HFSC_REALTIMESC) { 569 if (!is_gsc_under_sc(&hfsc_clinfo->gen_rsc, sc)) { 570 /* admission control failure */ 571 return (QOPERR_ADMISSION); 572 } 573 574 gsc_sub_sc(&parent_clinfo->gen_rsc, &hfsc_clinfo->rsc); 575 gsc_add_sc(&parent_clinfo->gen_rsc, sc); 576 if (!is_gsc_under_sc(&parent_clinfo->gen_rsc, 577 &parent_clinfo->rsc)) { 578 /* admission control failure */ 579 gsc_sub_sc(&parent_clinfo->gen_rsc, sc); 580 gsc_add_sc(&parent_clinfo->gen_rsc, &hfsc_clinfo->rsc); 581 return (QOPERR_ADMISSION_NOBW); 582 } 583 hfsc_clinfo->rsc = *sc; 584 } 585 if (sctype & HFSC_LINKSHARINGSC) { 586 if (!is_gsc_under_sc(&hfsc_clinfo->gen_fsc, sc)) { 587 /* admission control failure */ 588 return (QOPERR_ADMISSION); 589 } 590 591 gsc_sub_sc(&parent_clinfo->gen_fsc, &hfsc_clinfo->fsc); 592 gsc_add_sc(&parent_clinfo->gen_fsc, sc); 593 if (!is_gsc_under_sc(&parent_clinfo->gen_fsc, 594 &parent_clinfo->fsc)) { 595 /* admission control failure */ 596 gsc_sub_sc(&parent_clinfo->gen_fsc, sc); 597 gsc_add_sc(&parent_clinfo->gen_fsc, &hfsc_clinfo->fsc); 598 return (QOPERR_ADMISSION_NOBW); 599 } 600 hfsc_clinfo->fsc = *sc; 601 } 602 603 error = qop_modify_class(clinfo, (void *)((long)sctype)); 604 if (error == 0) 605 return (0); 606 607 /* modify failed!, restore the old service curves */ 608 if (sctype & HFSC_REALTIMESC) { 609 gsc_sub_sc(&parent_clinfo->gen_rsc, sc); 610 gsc_add_sc(&parent_clinfo->gen_rsc, &rsc); 611 hfsc_clinfo->rsc = rsc; 612 } 613 if (sctype & HFSC_LINKSHARINGSC) { 614 gsc_sub_sc(&parent_clinfo->gen_fsc, sc); 615 gsc_add_sc(&parent_clinfo->gen_fsc, &fsc); 616 hfsc_clinfo->fsc = fsc; 617 } 618 return (error); 619 } 620 621 /* 622 * sanity check at enabling hfsc: 623 * 1. there must one default class for an interface 624 * 2. the default class must be a leaf class 625 * 3. an internal class should not have filters 626 * (rule 2 and 3 are due to the fact that the hfsc link-sharing algorithm 627 * do not schedule internal classes.) 628 */ 629 static int 630 qop_hfsc_enable_hook(struct ifinfo *ifinfo) 631 { 632 struct hfsc_ifinfo *hfsc_ifinfo; 633 struct classinfo *clinfo; 634 635 hfsc_ifinfo = ifinfo->private; 636 if (hfsc_ifinfo->default_class == NULL) { 637 LOG(LOG_ERR, 0, "hfsc: no default class on interface %s!", 638 ifinfo->ifname); 639 return (QOPERR_CLASS); 640 } else if (hfsc_ifinfo->default_class->child != NULL) { 641 LOG(LOG_ERR, 0, "hfsc: default class on %s must be a leaf!", 642 ifinfo->ifname); 643 return (QOPERR_CLASS); 644 } 645 646 LIST_FOREACH(clinfo, &ifinfo->cllist, next) { 647 if (clinfo->child != NULL && !LIST_EMPTY(&clinfo->fltrlist)) { 648 LOG(LOG_ERR, 0, 649 "hfsc: internal class \"%s\" should not have a filter!", 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!"); 664 return (-1); 665 } 666 return (0); 667 } 668 669 /* 670 * admission control using generalized service curve 671 */ 672 #define INFINITY HUGE_VAL /* positive infinity defined in <math.h> */ 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"); 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