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