qop_hfsc.c revision 1.7
1 /* $NetBSD: qop_hfsc.c,v 1.7 2003/10/26 08:08:06 lukem 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 673 /* add a new service curve to a generilized service curve */ 674 static void 675 gsc_add_sc(struct gen_sc *gsc, struct service_curve *sc) 676 { 677 if (is_sc_null(sc)) 678 return; 679 if (sc->d != 0) 680 gsc_add_seg(gsc, 0, 0, (double)sc->d, (double)sc->m1); 681 gsc_add_seg(gsc, (double)sc->d, 0, HUGE_VAL, (double)sc->m2); 682 } 683 684 /* subtract a service curve from a generilized service curve */ 685 static void 686 gsc_sub_sc(struct gen_sc *gsc, struct service_curve *sc) 687 { 688 if (is_sc_null(sc)) 689 return; 690 if (sc->d != 0) 691 gsc_sub_seg(gsc, 0, 0, (double)sc->d, (double)sc->m1); 692 gsc_sub_seg(gsc, (double)sc->d, 0, HUGE_VAL, (double)sc->m2); 693 } 694 695 /* 696 * check whether all points of a generalized service curve have 697 * their y-coordinates no larger than a given two-piece linear 698 * service curve. 699 */ 700 static int 701 is_gsc_under_sc(struct gen_sc *gsc, struct service_curve *sc) 702 { 703 struct segment *s, *last, *end; 704 double y; 705 706 if (is_sc_null(sc)) { 707 if (LIST_EMPTY(gsc)) 708 return (1); 709 LIST_FOREACH(s, gsc, _next) { 710 if (s->m != 0) 711 return (0); 712 } 713 return (1); 714 } 715 /* 716 * gsc has a dummy entry at the end with x = HUGE_VAL. 717 * loop through up to this dummy entry. 718 */ 719 end = gsc_getentry(gsc, HUGE_VAL); 720 if (end == NULL) 721 return (1); 722 last = NULL; 723 for (s = LIST_FIRST(gsc); s != end; s = LIST_NEXT(s, _next)) { 724 if (s->y > sc_x2y(sc, s->x)) 725 return (0); 726 last = s; 727 } 728 /* last now holds the real last segment */ 729 if (last == NULL) 730 return (1); 731 if (last->m > sc->m2) 732 return (0); 733 if (last->x < sc->d && last->m > sc->m1) { 734 y = last->y + (sc->d - last->x) * last->m; 735 if (y > sc_x2y(sc, sc->d)) 736 return (0); 737 } 738 return (1); 739 } 740 741 static void 742 gsc_destroy(struct gen_sc *gsc) 743 { 744 struct segment *s; 745 746 while ((s = LIST_FIRST(gsc)) != NULL) { 747 LIST_REMOVE(s, _next); 748 free(s); 749 } 750 } 751 752 /* 753 * return a segment entry starting at x. 754 * if gsc has no entry starting at x, a new entry is created at x. 755 */ 756 static struct segment * 757 gsc_getentry(struct gen_sc *gsc, double x) 758 { 759 struct segment *new, *prev, *s; 760 761 prev = NULL; 762 LIST_FOREACH(s, gsc, _next) { 763 if (s->x == x) 764 return (s); /* matching entry found */ 765 else if (s->x < x) 766 prev = s; 767 else 768 break; 769 } 770 771 /* we have to create a new entry */ 772 if ((new = calloc(1, sizeof(struct segment))) == NULL) 773 return (NULL); 774 775 new->x = x; 776 if (x == HUGE_VAL || s == NULL) 777 new->d = 0; 778 else if (s->x == HUGE_VAL) 779 new->d = HUGE_VAL; 780 else 781 new->d = s->x - x; 782 if (prev == NULL) { 783 /* insert the new entry at the head of the list */ 784 new->y = 0; 785 new->m = 0; 786 LIST_INSERT_HEAD(gsc, new, _next); 787 } else { 788 /* 789 * the start point intersects with the segment pointed by 790 * prev. divide prev into 2 segments 791 */ 792 if (x == HUGE_VAL) { 793 prev->d = HUGE_VAL; 794 if (prev->m == 0) 795 new->y = prev->y; 796 else 797 new->y = HUGE_VAL; 798 } else { 799 prev->d = x - prev->x; 800 new->y = prev->d * prev->m + prev->y; 801 } 802 new->m = prev->m; 803 LIST_INSERT_AFTER(prev, new, _next); 804 } 805 return (new); 806 } 807 808 /* add a segment to a generalized service curve */ 809 static int 810 gsc_add_seg(struct gen_sc *gsc, double x, double y, double d, double m) 811 { 812 struct segment *start, *end, *s; 813 double x2; 814 815 if (d == HUGE_VAL) 816 x2 = HUGE_VAL; 817 else 818 x2 = x + d; 819 start = gsc_getentry(gsc, x); 820 end = gsc_getentry(gsc, x2); 821 if (start == NULL || end == NULL) 822 return (-1); 823 824 for (s = start; s != end; s = LIST_NEXT(s, _next)) { 825 s->m += m; 826 s->y += y + (s->x - x) * m; 827 } 828 829 end = gsc_getentry(gsc, HUGE_VAL); 830 for (; s != end; s = LIST_NEXT(s, _next)) { 831 s->y += m * d; 832 } 833 834 return (0); 835 } 836 837 /* subtract a segment from a generalized service curve */ 838 static int 839 gsc_sub_seg(struct gen_sc *gsc, double x, double y, double d, double m) 840 { 841 if (gsc_add_seg(gsc, x, y, d, -m) < 0) 842 return (-1); 843 gsc_compress(gsc); 844 return (0); 845 } 846 847 /* 848 * collapse adjacent segments with the same slope 849 */ 850 static void 851 gsc_compress(struct gen_sc *gsc) 852 { 853 struct segment *s, *next; 854 855 again: 856 LIST_FOREACH(s, gsc, _next) { 857 858 if ((next = LIST_NEXT(s, _next)) == NULL) { 859 if (LIST_FIRST(gsc) == s && s->m == 0) { 860 /* 861 * if this is the only entry and its 862 * slope is 0, it's a remaining dummy 863 * entry. we can discard it. 864 */ 865 LIST_REMOVE(s, _next); 866 free(s); 867 } 868 break; 869 } 870 871 if (s->x == next->x) { 872 /* discard this entry */ 873 LIST_REMOVE(s, _next); 874 free(s); 875 goto again; 876 } else if (s->m == next->m) { 877 /* join the two entries */ 878 if (s->d != HUGE_VAL && next->d != HUGE_VAL) 879 s->d += next->d; 880 LIST_REMOVE(next, _next); 881 free(next); 882 goto again; 883 } 884 } 885 } 886 887 /* get y-projection of a service curve */ 888 static double 889 sc_x2y(struct service_curve *sc, double x) 890 { 891 double y; 892 893 if (x <= (double)sc->d) 894 /* y belongs to the 1st segment */ 895 y = x * (double)sc->m1; 896 else 897 /* y belongs to the 2nd segment */ 898 y = (double)sc->d * (double)sc->m1 899 + (x - (double)sc->d) * (double)sc->m2; 900 return (y); 901 } 902 903 /* 904 * system call interfaces for qdisc_ops 905 */ 906 static int 907 hfsc_attach(struct ifinfo *ifinfo) 908 { 909 struct hfsc_attach attach; 910 911 if (hfsc_fd < 0 && 912 (hfsc_fd = open(HFSC_DEVICE, O_RDWR)) < 0 && 913 (hfsc_fd = open_module(HFSC_DEVICE, O_RDWR)) < 0) { 914 LOG(LOG_ERR, errno, "HFSC open"); 915 return (QOPERR_SYSCALL); 916 } 917 918 hfsc_refcount++; 919 memset(&attach, 0, sizeof(attach)); 920 strncpy(attach.iface.hfsc_ifname, ifinfo->ifname, IFNAMSIZ); 921 attach.bandwidth = ifinfo->bandwidth; 922 923 if (ioctl(hfsc_fd, HFSC_IF_ATTACH, &attach) < 0) 924 return (QOPERR_SYSCALL); 925 return (0); 926 } 927 928 static int 929 hfsc_detach(struct ifinfo *ifinfo) 930 { 931 struct hfsc_interface iface; 932 933 memset(&iface, 0, sizeof(iface)); 934 strncpy(iface.hfsc_ifname, ifinfo->ifname, IFNAMSIZ); 935 936 if (ioctl(hfsc_fd, HFSC_IF_DETACH, &iface) < 0) 937 return (QOPERR_SYSCALL); 938 939 if (--hfsc_refcount == 0) { 940 close(hfsc_fd); 941 hfsc_fd = -1; 942 } 943 return (0); 944 } 945 946 static int 947 hfsc_clear(struct ifinfo *ifinfo) 948 { 949 struct hfsc_interface iface; 950 951 memset(&iface, 0, sizeof(iface)); 952 strncpy(iface.hfsc_ifname, ifinfo->ifname, IFNAMSIZ); 953 954 if (ioctl(hfsc_fd, HFSC_CLEAR_HIERARCHY, &iface) < 0) 955 return (QOPERR_SYSCALL); 956 return (0); 957 } 958 959 static int 960 hfsc_enable(struct ifinfo *ifinfo) 961 { 962 struct hfsc_interface iface; 963 964 memset(&iface, 0, sizeof(iface)); 965 strncpy(iface.hfsc_ifname, ifinfo->ifname, IFNAMSIZ); 966 967 if (ioctl(hfsc_fd, HFSC_ENABLE, &iface) < 0) 968 return (QOPERR_SYSCALL); 969 return (0); 970 } 971 972 static int 973 hfsc_disable(struct ifinfo *ifinfo) 974 { 975 struct hfsc_interface iface; 976 977 memset(&iface, 0, sizeof(iface)); 978 strncpy(iface.hfsc_ifname, ifinfo->ifname, IFNAMSIZ); 979 980 if (ioctl(hfsc_fd, HFSC_DISABLE, &iface) < 0) 981 return (QOPERR_SYSCALL); 982 return (0); 983 } 984 985 static int 986 hfsc_add_class(struct classinfo *clinfo) 987 { 988 struct hfsc_add_class class_add; 989 struct hfsc_classinfo *hfsc_clinfo; 990 struct hfsc_ifinfo *hfsc_ifinfo; 991 992 /* root class is a dummy class */ 993 if (clinfo->parent == NULL) { 994 clinfo->handle = HFSC_ROOTCLASS_HANDLE; 995 return (0); 996 } 997 998 hfsc_ifinfo = clinfo->ifinfo->private; 999 hfsc_clinfo = clinfo->private; 1000 1001 memset(&class_add, 0, sizeof(class_add)); 1002 strncpy(class_add.iface.hfsc_ifname, clinfo->ifinfo->ifname, IFNAMSIZ); 1003 if (clinfo->parent == hfsc_ifinfo->root_class) 1004 class_add.parent_handle = HFSC_ROOTCLASS_HANDLE; 1005 else 1006 class_add.parent_handle = clinfo->parent->handle; 1007 class_add.service_curve = hfsc_clinfo->rsc; 1008 class_add.qlimit = hfsc_clinfo->qlimit; 1009 class_add.flags = hfsc_clinfo->flags; 1010 if (ioctl(hfsc_fd, HFSC_ADD_CLASS, &class_add) < 0) { 1011 clinfo->handle = HFSC_NULLCLASS_HANDLE; 1012 return (QOPERR_SYSCALL); 1013 } 1014 clinfo->handle = class_add.class_handle; 1015 return (0); 1016 } 1017 1018 static int 1019 hfsc_modify_class(struct classinfo *clinfo, void *arg) 1020 { 1021 struct hfsc_modify_class class_mod; 1022 struct hfsc_classinfo *hfsc_clinfo; 1023 long sctype; 1024 1025 sctype = (long)arg; 1026 hfsc_clinfo = clinfo->private; 1027 1028 memset(&class_mod, 0, sizeof(class_mod)); 1029 strncpy(class_mod.iface.hfsc_ifname, clinfo->ifinfo->ifname, IFNAMSIZ); 1030 class_mod.class_handle = clinfo->handle; 1031 if (sctype & HFSC_REALTIMESC) 1032 class_mod.service_curve = hfsc_clinfo->rsc; 1033 else if (sctype & HFSC_LINKSHARINGSC) 1034 class_mod.service_curve = hfsc_clinfo->fsc; 1035 else 1036 return (QOPERR_INVAL); 1037 class_mod.sctype = sctype; 1038 1039 if (ioctl(hfsc_fd, HFSC_MOD_CLASS, &class_mod) < 0) 1040 return (QOPERR_SYSCALL); 1041 return (0); 1042 } 1043 1044 static int 1045 hfsc_delete_class(struct classinfo *clinfo) 1046 { 1047 struct hfsc_delete_class class_delete; 1048 1049 if (clinfo->handle == HFSC_NULLCLASS_HANDLE || 1050 clinfo->handle == HFSC_ROOTCLASS_HANDLE) 1051 return (0); 1052 1053 memset(&class_delete, 0, sizeof(class_delete)); 1054 strncpy(class_delete.iface.hfsc_ifname, clinfo->ifinfo->ifname, 1055 IFNAMSIZ); 1056 class_delete.class_handle = clinfo->handle; 1057 1058 if (ioctl(hfsc_fd, HFSC_DEL_CLASS, &class_delete) < 0) 1059 return (QOPERR_SYSCALL); 1060 return (0); 1061 } 1062 1063 static int 1064 hfsc_add_filter(struct fltrinfo *fltrinfo) 1065 { 1066 struct hfsc_add_filter fltr_add; 1067 1068 memset(&fltr_add, 0, sizeof(fltr_add)); 1069 strncpy(fltr_add.iface.hfsc_ifname, fltrinfo->clinfo->ifinfo->ifname, 1070 IFNAMSIZ); 1071 fltr_add.class_handle = fltrinfo->clinfo->handle; 1072 fltr_add.filter = fltrinfo->fltr; 1073 1074 if (ioctl(hfsc_fd, HFSC_ADD_FILTER, &fltr_add) < 0) 1075 return (QOPERR_SYSCALL); 1076 fltrinfo->handle = fltr_add.filter_handle; 1077 return (0); 1078 } 1079 1080 static int 1081 hfsc_delete_filter(struct fltrinfo *fltrinfo) 1082 { 1083 struct hfsc_delete_filter fltr_del; 1084 1085 memset(&fltr_del, 0, sizeof(fltr_del)); 1086 strncpy(fltr_del.iface.hfsc_ifname, fltrinfo->clinfo->ifinfo->ifname, 1087 IFNAMSIZ); 1088 fltr_del.filter_handle = fltrinfo->handle; 1089 1090 if (ioctl(hfsc_fd, HFSC_DEL_FILTER, &fltr_del) < 0) 1091 return (QOPERR_SYSCALL); 1092 return (0); 1093 } 1094 1095 1096
Indexes created Sun Oct 19 18:09:56 GMT 2025