1 /* $NetBSD: pfctl_altq.c,v 1.5 2005/07/01 12:43:50 peter Exp $ */ 2 /* $OpenBSD: pfctl_altq.c,v 1.86 2005/02/28 14:04:51 henning Exp $ */ 3 4 /* 5 * Copyright (c) 2002 6 * Sony Computer Science Laboratories Inc. 7 * Copyright (c) 2002, 2003 Henning Brauer <henning@openbsd.org> 8 * 9 * Permission to use, copy, modify, and distribute this software for any 10 * purpose with or without fee is hereby granted, provided that the above 11 * copyright notice and this permission notice appear in all copies. 12 * 13 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 14 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 15 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 16 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 17 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 18 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 19 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 20 */ 21 22 #include <sys/types.h> 23 #include <sys/ioctl.h> 24 #include <sys/socket.h> 25 #ifdef __NetBSD__ 26 #include <sys/param.h> 27 #include <sys/mbuf.h> 28 #endif 29 30 #include <net/if.h> 31 #include <netinet/in.h> 32 #include <net/pfvar.h> 33 34 #include <err.h> 35 #include <errno.h> 36 #include <limits.h> 37 #include <math.h> 38 #include <stdio.h> 39 #include <stdlib.h> 40 #include <string.h> 41 #include <unistd.h> 42 43 #include <altq/altq.h> 44 #include <altq/altq_cbq.h> 45 #include <altq/altq_priq.h> 46 #include <altq/altq_hfsc.h> 47 48 #include "pfctl_parser.h" 49 #include "pfctl.h" 50 51 #define is_sc_null(sc) (((sc) == NULL) || ((sc)->m1 == 0 && (sc)->m2 == 0)) 52 53 TAILQ_HEAD(altqs, pf_altq) altqs = TAILQ_HEAD_INITIALIZER(altqs); 54 LIST_HEAD(gen_sc, segment) rtsc, lssc; 55 56 struct pf_altq *qname_to_pfaltq(const char *, const char *); 57 u_int32_t qname_to_qid(const char *); 58 59 static int eval_pfqueue_cbq(struct pfctl *, struct pf_altq *); 60 static int cbq_compute_idletime(struct pfctl *, struct pf_altq *); 61 static int check_commit_cbq(int, int, struct pf_altq *); 62 static int print_cbq_opts(const struct pf_altq *); 63 64 static int eval_pfqueue_priq(struct pfctl *, struct pf_altq *); 65 static int check_commit_priq(int, int, struct pf_altq *); 66 static int print_priq_opts(const struct pf_altq *); 67 68 static int eval_pfqueue_hfsc(struct pfctl *, struct pf_altq *); 69 static int check_commit_hfsc(int, int, struct pf_altq *); 70 static int print_hfsc_opts(const struct pf_altq *, 71 const struct node_queue_opt *); 72 73 static void gsc_add_sc(struct gen_sc *, struct service_curve *); 74 static int is_gsc_under_sc(struct gen_sc *, 75 struct service_curve *); 76 static void gsc_destroy(struct gen_sc *); 77 static struct segment *gsc_getentry(struct gen_sc *, double); 78 static int gsc_add_seg(struct gen_sc *, double, double, double, 79 double); 80 static double sc_x2y(struct service_curve *, double); 81 82 u_int32_t getifspeed(char *); 83 u_long getifmtu(char *); 84 int eval_queue_opts(struct pf_altq *, struct node_queue_opt *, 85 u_int32_t); 86 u_int32_t eval_bwspec(struct node_queue_bw *, u_int32_t); 87 void print_hfsc_sc(const char *, u_int, u_int, u_int, 88 const struct node_hfsc_sc *); 89 90 void 91 pfaltq_store(struct pf_altq *a) 92 { 93 struct pf_altq *altq; 94 95 if ((altq = malloc(sizeof(*altq))) == NULL) 96 err(1, "malloc"); 97 memcpy(altq, a, sizeof(struct pf_altq)); 98 TAILQ_INSERT_TAIL(&altqs, altq, entries); 99 } 100 101 void 102 pfaltq_free(struct pf_altq *a) 103 { 104 struct pf_altq *altq; 105 106 TAILQ_FOREACH(altq, &altqs, entries) { 107 if (strncmp(a->ifname, altq->ifname, IFNAMSIZ) == 0 && 108 strncmp(a->qname, altq->qname, PF_QNAME_SIZE) == 0) { 109 TAILQ_REMOVE(&altqs, altq, entries); 110 free(altq); 111 return; 112 } 113 } 114 } 115 116 struct pf_altq * 117 pfaltq_lookup(const char *ifname) 118 { 119 struct pf_altq *altq; 120 121 TAILQ_FOREACH(altq, &altqs, entries) { 122 if (strncmp(ifname, altq->ifname, IFNAMSIZ) == 0 && 123 altq->qname[0] == 0) 124 return (altq); 125 } 126 return (NULL); 127 } 128 129 struct pf_altq * 130 qname_to_pfaltq(const char *qname, const char *ifname) 131 { 132 struct pf_altq *altq; 133 134 TAILQ_FOREACH(altq, &altqs, entries) { 135 if (strncmp(ifname, altq->ifname, IFNAMSIZ) == 0 && 136 strncmp(qname, altq->qname, PF_QNAME_SIZE) == 0) 137 return (altq); 138 } 139 return (NULL); 140 } 141 142 u_int32_t 143 qname_to_qid(const char *qname) 144 { 145 struct pf_altq *altq; 146 147 /* 148 * We guarantee that same named queues on different interfaces 149 * have the same qid, so we do NOT need to limit matching on 150 * one interface! 151 */ 152 153 TAILQ_FOREACH(altq, &altqs, entries) { 154 if (strncmp(qname, altq->qname, PF_QNAME_SIZE) == 0) 155 return (altq->qid); 156 } 157 return (0); 158 } 159 160 void 161 print_altq(const struct pf_altq *a, unsigned level, struct node_queue_bw *bw, 162 struct node_queue_opt *qopts) 163 { 164 if (a->qname[0] != 0) { 165 print_queue(a, level, bw, 0, qopts); 166 return; 167 } 168 169 printf("altq on %s ", a->ifname); 170 171 switch (a->scheduler) { 172 case ALTQT_CBQ: 173 if (!print_cbq_opts(a)) 174 printf("cbq "); 175 break; 176 case ALTQT_PRIQ: 177 if (!print_priq_opts(a)) 178 printf("priq "); 179 break; 180 case ALTQT_HFSC: 181 if (!print_hfsc_opts(a, qopts)) 182 printf("hfsc "); 183 break; 184 } 185 186 if (bw != NULL && bw->bw_percent > 0) { 187 if (bw->bw_percent < 100) 188 printf("bandwidth %u%% ", bw->bw_percent); 189 } else 190 printf("bandwidth %s ", rate2str((double)a->ifbandwidth)); 191 192 if (a->qlimit != DEFAULT_QLIMIT) 193 printf("qlimit %u ", a->qlimit); 194 printf("tbrsize %u ", a->tbrsize); 195 } 196 197 void 198 print_queue(const struct pf_altq *a, unsigned level, struct node_queue_bw *bw, 199 int print_interface, struct node_queue_opt *qopts) 200 { 201 unsigned i; 202 203 printf("queue "); 204 for (i = 0; i < level; ++i) 205 printf(" "); 206 printf("%s ", a->qname); 207 if (print_interface) 208 printf("on %s ", a->ifname); 209 if (a->scheduler == ALTQT_CBQ || a->scheduler == ALTQT_HFSC) { 210 if (bw != NULL && bw->bw_percent > 0) { 211 if (bw->bw_percent < 100) 212 printf("bandwidth %u%% ", bw->bw_percent); 213 } else 214 printf("bandwidth %s ", rate2str((double)a->bandwidth)); 215 } 216 if (a->priority != DEFAULT_PRIORITY) 217 printf("priority %u ", a->priority); 218 if (a->qlimit != DEFAULT_QLIMIT) 219 printf("qlimit %u ", a->qlimit); 220 switch (a->scheduler) { 221 case ALTQT_CBQ: 222 print_cbq_opts(a); 223 break; 224 case ALTQT_PRIQ: 225 print_priq_opts(a); 226 break; 227 case ALTQT_HFSC: 228 print_hfsc_opts(a, qopts); 229 break; 230 } 231 } 232 233 /* 234 * eval_pfaltq computes the discipline parameters. 235 */ 236 int 237 eval_pfaltq(struct pfctl *pf, struct pf_altq *pa, struct node_queue_bw *bw, 238 struct node_queue_opt *opts) 239 { 240 u_int rate, size, errors = 0; 241 242 if (bw->bw_absolute > 0) 243 pa->ifbandwidth = bw->bw_absolute; 244 else 245 if ((rate = getifspeed(pa->ifname)) == 0) { 246 fprintf(stderr, "cannot determine interface bandwidth " 247 "for %s, specify an absolute bandwidth\n", 248 pa->ifname); 249 errors++; 250 } else if ((pa->ifbandwidth = eval_bwspec(bw, rate)) == 0) 251 pa->ifbandwidth = rate; 252 253 errors += eval_queue_opts(pa, opts, pa->ifbandwidth); 254 255 /* if tbrsize is not specified, use heuristics */ 256 if (pa->tbrsize == 0) { 257 rate = pa->ifbandwidth; 258 if (rate <= 1 * 1000 * 1000) 259 size = 1; 260 else if (rate <= 10 * 1000 * 1000) 261 size = 4; 262 else if (rate <= 200 * 1000 * 1000) 263 size = 8; 264 else 265 size = 24; 266 size = size * getifmtu(pa->ifname); 267 if (size > 0xffff) 268 size = 0xffff; 269 pa->tbrsize = size; 270 } 271 return (errors); 272 } 273 274 /* 275 * check_commit_altq does consistency check for each interface 276 */ 277 int 278 check_commit_altq(int dev, int opts) 279 { 280 struct pf_altq *altq; 281 int error = 0; 282 283 /* call the discipline check for each interface. */ 284 TAILQ_FOREACH(altq, &altqs, entries) { 285 if (altq->qname[0] == 0) { 286 switch (altq->scheduler) { 287 case ALTQT_CBQ: 288 error = check_commit_cbq(dev, opts, altq); 289 break; 290 case ALTQT_PRIQ: 291 error = check_commit_priq(dev, opts, altq); 292 break; 293 case ALTQT_HFSC: 294 error = check_commit_hfsc(dev, opts, altq); 295 break; 296 default: 297 break; 298 } 299 } 300 } 301 return (error); 302 } 303 304 /* 305 * eval_pfqueue computes the queue parameters. 306 */ 307 int 308 eval_pfqueue(struct pfctl *pf, struct pf_altq *pa, struct node_queue_bw *bw, 309 struct node_queue_opt *opts) 310 { 311 /* should be merged with expand_queue */ 312 struct pf_altq *if_pa, *parent, *altq; 313 u_int32_t bwsum; 314 int error = 0; 315 316 /* find the corresponding interface and copy fields used by queues */ 317 if ((if_pa = pfaltq_lookup(pa->ifname)) == NULL) { 318 fprintf(stderr, "altq not defined on %s\n", pa->ifname); 319 return (1); 320 } 321 pa->scheduler = if_pa->scheduler; 322 pa->ifbandwidth = if_pa->ifbandwidth; 323 324 if (qname_to_pfaltq(pa->qname, pa->ifname) != NULL) { 325 fprintf(stderr, "queue %s already exists on interface %s\n", 326 pa->qname, pa->ifname); 327 return (1); 328 } 329 pa->qid = qname_to_qid(pa->qname); 330 331 parent = NULL; 332 if (pa->parent[0] != 0) { 333 parent = qname_to_pfaltq(pa->parent, pa->ifname); 334 if (parent == NULL) { 335 fprintf(stderr, "parent %s not found for %s\n", 336 pa->parent, pa->qname); 337 return (1); 338 } 339 pa->parent_qid = parent->qid; 340 } 341 if (pa->qlimit == 0) 342 pa->qlimit = DEFAULT_QLIMIT; 343 344 if (pa->scheduler == ALTQT_CBQ || pa->scheduler == ALTQT_HFSC) { 345 pa->bandwidth = eval_bwspec(bw, 346 parent == NULL ? 0 : parent->bandwidth); 347 348 if (pa->bandwidth > pa->ifbandwidth) { 349 fprintf(stderr, "bandwidth for %s higher than " 350 "interface\n", pa->qname); 351 return (1); 352 } 353 /* check the sum of the child bandwidth is under parent's */ 354 if (parent != NULL) { 355 if (pa->bandwidth > parent->bandwidth) { 356 warnx("bandwidth for %s higher than parent", 357 pa->qname); 358 return (1); 359 } 360 bwsum = 0; 361 TAILQ_FOREACH(altq, &altqs, entries) { 362 if (strncmp(altq->ifname, pa->ifname, 363 IFNAMSIZ) == 0 && 364 altq->qname[0] != 0 && 365 strncmp(altq->parent, pa->parent, 366 PF_QNAME_SIZE) == 0) 367 bwsum += altq->bandwidth; 368 } 369 bwsum += pa->bandwidth; 370 if (bwsum > parent->bandwidth) { 371 warnx("the sum of the child bandwidth higher" 372 " than parent \"%s\"", parent->qname); 373 } 374 } 375 } 376 377 if (eval_queue_opts(pa, opts, parent == NULL? 0 : parent->bandwidth)) 378 return (1); 379 380 switch (pa->scheduler) { 381 case ALTQT_CBQ: 382 error = eval_pfqueue_cbq(pf, pa); 383 break; 384 case ALTQT_PRIQ: 385 error = eval_pfqueue_priq(pf, pa); 386 break; 387 case ALTQT_HFSC: 388 error = eval_pfqueue_hfsc(pf, pa); 389 break; 390 default: 391 break; 392 } 393 return (error); 394 } 395 396 /* 397 * CBQ support functions 398 */ 399 #define RM_FILTER_GAIN 5 /* log2 of gain, e.g., 5 => 31/32 */ 400 #define RM_NS_PER_SEC (1000000000) 401 402 static int 403 eval_pfqueue_cbq(struct pfctl *pf, struct pf_altq *pa) 404 { 405 struct cbq_opts *opts; 406 u_int ifmtu; 407 408 if (pa->priority >= CBQ_MAXPRI) { 409 warnx("priority out of range: max %d", CBQ_MAXPRI - 1); 410 return (-1); 411 } 412 413 ifmtu = getifmtu(pa->ifname); 414 opts = &pa->pq_u.cbq_opts; 415 416 if (opts->pktsize == 0) { /* use default */ 417 opts->pktsize = ifmtu; 418 if (opts->pktsize > MCLBYTES) /* do what TCP does */ 419 opts->pktsize &= ~MCLBYTES; 420 } else if (opts->pktsize > ifmtu) 421 opts->pktsize = ifmtu; 422 if (opts->maxpktsize == 0) /* use default */ 423 opts->maxpktsize = ifmtu; 424 else if (opts->maxpktsize > ifmtu) 425 opts->pktsize = ifmtu; 426 427 if (opts->pktsize > opts->maxpktsize) 428 opts->pktsize = opts->maxpktsize; 429 430 if (pa->parent[0] == 0) 431 opts->flags |= (CBQCLF_ROOTCLASS | CBQCLF_WRR); 432 433 cbq_compute_idletime(pf, pa); 434 return (0); 435 } 436 437 /* 438 * compute ns_per_byte, maxidle, minidle, and offtime 439 */ 440 static int 441 cbq_compute_idletime(struct pfctl *pf, struct pf_altq *pa) 442 { 443 struct cbq_opts *opts; 444 double maxidle_s, maxidle, minidle; 445 double offtime, nsPerByte, ifnsPerByte, ptime, cptime; 446 double z, g, f, gton, gtom; 447 u_int minburst, maxburst; 448 449 opts = &pa->pq_u.cbq_opts; 450 ifnsPerByte = (1.0 / (double)pa->ifbandwidth) * RM_NS_PER_SEC * 8; 451 minburst = opts->minburst; 452 maxburst = opts->maxburst; 453 454 if (pa->bandwidth == 0) 455 f = 0.0001; /* small enough? */ 456 else 457 f = ((double) pa->bandwidth / (double) pa->ifbandwidth); 458 459 nsPerByte = ifnsPerByte / f; 460 ptime = (double)opts->pktsize * ifnsPerByte; 461 cptime = ptime * (1.0 - f) / f; 462 463 if (nsPerByte * (double)opts->maxpktsize > (double)INT_MAX) { 464 /* 465 * this causes integer overflow in kernel! 466 * (bandwidth < 6Kbps when max_pkt_size=1500) 467 */ 468 if (pa->bandwidth != 0 && (pf->opts & PF_OPT_QUIET) == 0) 469 warnx("queue bandwidth must be larger than %s", 470 rate2str(ifnsPerByte * (double)opts->maxpktsize / 471 (double)INT_MAX * (double)pa->ifbandwidth)); 472 fprintf(stderr, "cbq: queue %s is too slow!\n", 473 pa->qname); 474 nsPerByte = (double)(INT_MAX / opts->maxpktsize); 475 } 476 477 if (maxburst == 0) { /* use default */ 478 if (cptime > 10.0 * 1000000) 479 maxburst = 4; 480 else 481 maxburst = 16; 482 } 483 if (minburst == 0) /* use default */ 484 minburst = 2; 485 if (minburst > maxburst) 486 minburst = maxburst; 487 488 z = (double)(1 << RM_FILTER_GAIN); 489 g = (1.0 - 1.0 / z); 490 gton = pow(g, (double)maxburst); 491 gtom = pow(g, (double)(minburst-1)); 492 maxidle = ((1.0 / f - 1.0) * ((1.0 - gton) / gton)); 493 maxidle_s = (1.0 - g); 494 if (maxidle > maxidle_s) 495 maxidle = ptime * maxidle; 496 else 497 maxidle = ptime * maxidle_s; 498 if (minburst) 499 offtime = cptime * (1.0 + 1.0/(1.0 - g) * (1.0 - gtom) / gtom); 500 else 501 offtime = cptime; 502 minidle = -((double)opts->maxpktsize * (double)nsPerByte); 503 504 /* scale parameters */ 505 maxidle = ((maxidle * 8.0) / nsPerByte) * 506 pow(2.0, (double)RM_FILTER_GAIN); 507 offtime = (offtime * 8.0) / nsPerByte * 508 pow(2.0, (double)RM_FILTER_GAIN); 509 minidle = ((minidle * 8.0) / nsPerByte) * 510 pow(2.0, (double)RM_FILTER_GAIN); 511 512 maxidle = maxidle / 1000.0; 513 offtime = offtime / 1000.0; 514 minidle = minidle / 1000.0; 515 516 opts->minburst = minburst; 517 opts->maxburst = maxburst; 518 opts->ns_per_byte = (u_int)nsPerByte; 519 opts->maxidle = (u_int)fabs(maxidle); 520 opts->minidle = (int)minidle; 521 opts->offtime = (u_int)fabs(offtime); 522 523 return (0); 524 } 525 526 static int 527 check_commit_cbq(int dev, int opts, struct pf_altq *pa) 528 { 529 struct pf_altq *altq; 530 int root_class, default_class; 531 int error = 0; 532 533 /* 534 * check if cbq has one root queue and one default queue 535 * for this interface 536 */ 537 root_class = default_class = 0; 538 TAILQ_FOREACH(altq, &altqs, entries) { 539 if (strncmp(altq->ifname, pa->ifname, IFNAMSIZ) != 0) 540 continue; 541 if (altq->qname[0] == 0) /* this is for interface */ 542 continue; 543 if (altq->pq_u.cbq_opts.flags & CBQCLF_ROOTCLASS) 544 root_class++; 545 if (altq->pq_u.cbq_opts.flags & CBQCLF_DEFCLASS) 546 default_class++; 547 } 548 if (root_class != 1) { 549 warnx("should have one root queue on %s", pa->ifname); 550 error++; 551 } 552 if (default_class != 1) { 553 warnx("should have one default queue on %s", pa->ifname); 554 error++; 555 } 556 return (error); 557 } 558 559 static int 560 print_cbq_opts(const struct pf_altq *a) 561 { 562 const struct cbq_opts *opts; 563 564 opts = &a->pq_u.cbq_opts; 565 if (opts->flags) { 566 printf("cbq("); 567 if (opts->flags & CBQCLF_RED) 568 printf(" red"); 569 if (opts->flags & CBQCLF_ECN) 570 printf(" ecn"); 571 if (opts->flags & CBQCLF_RIO) 572 printf(" rio"); 573 if (opts->flags & CBQCLF_CLEARDSCP) 574 printf(" cleardscp"); 575 if (opts->flags & CBQCLF_FLOWVALVE) 576 printf(" flowvalve"); 577 #ifdef CBQCLF_BORROW 578 if (opts->flags & CBQCLF_BORROW) 579 printf(" borrow"); 580 #endif 581 if (opts->flags & CBQCLF_WRR) 582 printf(" wrr"); 583 if (opts->flags & CBQCLF_EFFICIENT) 584 printf(" efficient"); 585 if (opts->flags & CBQCLF_ROOTCLASS) 586 printf(" root"); 587 if (opts->flags & CBQCLF_DEFCLASS) 588 printf(" default"); 589 printf(" ) "); 590 591 return (1); 592 } else 593 return (0); 594 } 595 596 /* 597 * PRIQ support functions 598 */ 599 static int 600 eval_pfqueue_priq(struct pfctl *pf, struct pf_altq *pa) 601 { 602 struct pf_altq *altq; 603 604 if (pa->priority >= PRIQ_MAXPRI) { 605 warnx("priority out of range: max %d", PRIQ_MAXPRI - 1); 606 return (-1); 607 } 608 /* the priority should be unique for the interface */ 609 TAILQ_FOREACH(altq, &altqs, entries) { 610 if (strncmp(altq->ifname, pa->ifname, IFNAMSIZ) == 0 && 611 altq->qname[0] != 0 && altq->priority == pa->priority) { 612 warnx("%s and %s have the same priority", 613 altq->qname, pa->qname); 614 return (-1); 615 } 616 } 617 618 return (0); 619 } 620 621 static int 622 check_commit_priq(int dev, int opts, struct pf_altq *pa) 623 { 624 struct pf_altq *altq; 625 int default_class; 626 int error = 0; 627 628 /* 629 * check if priq has one default class for this interface 630 */ 631 default_class = 0; 632 TAILQ_FOREACH(altq, &altqs, entries) { 633 if (strncmp(altq->ifname, pa->ifname, IFNAMSIZ) != 0) 634 continue; 635 if (altq->qname[0] == 0) /* this is for interface */ 636 continue; 637 if (altq->pq_u.priq_opts.flags & PRCF_DEFAULTCLASS) 638 default_class++; 639 } 640 if (default_class != 1) { 641 warnx("should have one default queue on %s", pa->ifname); 642 error++; 643 } 644 return (error); 645 } 646 647 static int 648 print_priq_opts(const struct pf_altq *a) 649 { 650 const struct priq_opts *opts; 651 652 opts = &a->pq_u.priq_opts; 653 654 if (opts->flags) { 655 printf("priq("); 656 if (opts->flags & PRCF_RED) 657 printf(" red"); 658 if (opts->flags & PRCF_ECN) 659 printf(" ecn"); 660 if (opts->flags & PRCF_RIO) 661 printf(" rio"); 662 if (opts->flags & PRCF_CLEARDSCP) 663 printf(" cleardscp"); 664 if (opts->flags & PRCF_DEFAULTCLASS) 665 printf(" default"); 666 printf(" ) "); 667 668 return (1); 669 } else 670 return (0); 671 } 672 673 /* 674 * HFSC support functions 675 */ 676 static int 677 eval_pfqueue_hfsc(struct pfctl *pf, struct pf_altq *pa) 678 { 679 struct pf_altq *altq, *parent; 680 struct hfsc_opts *opts; 681 struct service_curve sc; 682 683 opts = &pa->pq_u.hfsc_opts; 684 685 if (pa->parent[0] == 0) { 686 /* root queue */ 687 opts->lssc_m1 = pa->ifbandwidth; 688 opts->lssc_m2 = pa->ifbandwidth; 689 opts->lssc_d = 0; 690 return (0); 691 } 692 693 LIST_INIT(&rtsc); 694 LIST_INIT(&lssc); 695 696 /* if link_share is not specified, use bandwidth */ 697 if (opts->lssc_m2 == 0) 698 opts->lssc_m2 = pa->bandwidth; 699 700 if ((opts->rtsc_m1 > 0 && opts->rtsc_m2 == 0) || 701 (opts->lssc_m1 > 0 && opts->lssc_m2 == 0) || 702 (opts->ulsc_m1 > 0 && opts->ulsc_m2 == 0)) { 703 warnx("m2 is zero for %s", pa->qname); 704 return (-1); 705 } 706 707 if ((opts->rtsc_m1 < opts->rtsc_m2 && opts->rtsc_m1 != 0) || 708 (opts->rtsc_m1 < opts->rtsc_m2 && opts->rtsc_m1 != 0) || 709 (opts->rtsc_m1 < opts->rtsc_m2 && opts->rtsc_m1 != 0)) { 710 warnx("m1 must be zero for convex curve: %s", pa->qname); 711 return (-1); 712 } 713 714 /* 715 * admission control: 716 * for the real-time service curve, the sum of the service curves 717 * should not exceed 80% of the interface bandwidth. 20% is reserved 718 * not to over-commit the actual interface bandwidth. 719 * for the linkshare service curve, the sum of the child service 720 * curve should not exceed the parent service curve. 721 * for the upper-limit service curve, the assigned bandwidth should 722 * be smaller than the interface bandwidth, and the upper-limit should 723 * be larger than the real-time service curve when both are defined. 724 */ 725 parent = qname_to_pfaltq(pa->parent, pa->ifname); 726 if (parent == NULL) 727 errx(1, "parent %s not found for %s", pa->parent, pa->qname); 728 729 TAILQ_FOREACH(altq, &altqs, entries) { 730 if (strncmp(altq->ifname, pa->ifname, IFNAMSIZ) != 0) 731 continue; 732 if (altq->qname[0] == 0) /* this is for interface */ 733 continue; 734 735 /* if the class has a real-time service curve, add it. */ 736 if (opts->rtsc_m2 != 0 && altq->pq_u.hfsc_opts.rtsc_m2 != 0) { 737 sc.m1 = altq->pq_u.hfsc_opts.rtsc_m1; 738 sc.d = altq->pq_u.hfsc_opts.rtsc_d; 739 sc.m2 = altq->pq_u.hfsc_opts.rtsc_m2; 740 gsc_add_sc(&rtsc, &sc); 741 } 742 743 if (strncmp(altq->parent, pa->parent, PF_QNAME_SIZE) != 0) 744 continue; 745 746 /* if the class has a linkshare service curve, add it. */ 747 if (opts->lssc_m2 != 0 && altq->pq_u.hfsc_opts.lssc_m2 != 0) { 748 sc.m1 = altq->pq_u.hfsc_opts.lssc_m1; 749 sc.d = altq->pq_u.hfsc_opts.lssc_d; 750 sc.m2 = altq->pq_u.hfsc_opts.lssc_m2; 751 gsc_add_sc(&lssc, &sc); 752 } 753 } 754 755 /* check the real-time service curve. reserve 20% of interface bw */ 756 if (opts->rtsc_m2 != 0) { 757 /* add this queue to the sum */ 758 sc.m1 = opts->rtsc_m1; 759 sc.d = opts->rtsc_d; 760 sc.m2 = opts->rtsc_m2; 761 gsc_add_sc(&rtsc, &sc); 762 /* compare the sum with 80% of the interface */ 763 sc.m1 = 0; 764 sc.d = 0; 765 sc.m2 = pa->ifbandwidth / 100 * 80; 766 if (!is_gsc_under_sc(&rtsc, &sc)) { 767 warnx("real-time sc exceeds 80%% of the interface " 768 "bandwidth (%s)", rate2str((double)sc.m2)); 769 goto err_ret; 770 } 771 } 772 773 /* check the linkshare service curve. */ 774 if (opts->lssc_m2 != 0) { 775 /* add this queue to the child sum */ 776 sc.m1 = opts->lssc_m1; 777 sc.d = opts->lssc_d; 778 sc.m2 = opts->lssc_m2; 779 gsc_add_sc(&lssc, &sc); 780 /* compare the sum of the children with parent's sc */ 781 sc.m1 = parent->pq_u.hfsc_opts.lssc_m1; 782 sc.d = parent->pq_u.hfsc_opts.lssc_d; 783 sc.m2 = parent->pq_u.hfsc_opts.lssc_m2; 784 if (!is_gsc_under_sc(&lssc, &sc)) { 785 warnx("linkshare sc exceeds parent's sc"); 786 goto err_ret; 787 } 788 } 789 790 /* check the upper-limit service curve. */ 791 if (opts->ulsc_m2 != 0) { 792 if (opts->ulsc_m1 > pa->ifbandwidth || 793 opts->ulsc_m2 > pa->ifbandwidth) { 794 warnx("upper-limit larger than interface bandwidth"); 795 goto err_ret; 796 } 797 if (opts->rtsc_m2 != 0 && opts->rtsc_m2 > opts->ulsc_m2) { 798 warnx("upper-limit sc smaller than real-time sc"); 799 goto err_ret; 800 } 801 } 802 803 gsc_destroy(&rtsc); 804 gsc_destroy(&lssc); 805 806 return (0); 807 808 err_ret: 809 gsc_destroy(&rtsc); 810 gsc_destroy(&lssc); 811 return (-1); 812 } 813 814 static int 815 check_commit_hfsc(int dev, int opts, struct pf_altq *pa) 816 { 817 struct pf_altq *altq, *def = NULL; 818 int default_class; 819 int error = 0; 820 821 /* check if hfsc has one default queue for this interface */ 822 default_class = 0; 823 TAILQ_FOREACH(altq, &altqs, entries) { 824 if (strncmp(altq->ifname, pa->ifname, IFNAMSIZ) != 0) 825 continue; 826 if (altq->qname[0] == 0) /* this is for interface */ 827 continue; 828 if (altq->parent[0] == 0) /* dummy root */ 829 continue; 830 if (altq->pq_u.hfsc_opts.flags & HFCF_DEFAULTCLASS) { 831 default_class++; 832 def = altq; 833 } 834 } 835 if (default_class != 1) { 836 warnx("should have one default queue on %s", pa->ifname); 837 return (1); 838 } 839 /* make sure the default queue is a leaf */ 840 TAILQ_FOREACH(altq, &altqs, entries) { 841 if (strncmp(altq->ifname, pa->ifname, IFNAMSIZ) != 0) 842 continue; 843 if (altq->qname[0] == 0) /* this is for interface */ 844 continue; 845 if (strncmp(altq->parent, def->qname, PF_QNAME_SIZE) == 0) { 846 warnx("default queue is not a leaf"); 847 error++; 848 } 849 } 850 return (error); 851 } 852 853 static int 854 print_hfsc_opts(const struct pf_altq *a, const struct node_queue_opt *qopts) 855 { 856 const struct hfsc_opts *opts; 857 const struct node_hfsc_sc *rtsc, *lssc, *ulsc; 858 859 opts = &a->pq_u.hfsc_opts; 860 if (qopts == NULL) 861 rtsc = lssc = ulsc = NULL; 862 else { 863 rtsc = &qopts->data.hfsc_opts.realtime; 864 lssc = &qopts->data.hfsc_opts.linkshare; 865 ulsc = &qopts->data.hfsc_opts.upperlimit; 866 } 867 868 if (opts->flags || opts->rtsc_m2 != 0 || opts->ulsc_m2 != 0 || 869 (opts->lssc_m2 != 0 && (opts->lssc_m2 != a->bandwidth || 870 opts->lssc_d != 0))) { 871 printf("hfsc("); 872 if (opts->flags & HFCF_RED) 873 printf(" red"); 874 if (opts->flags & HFCF_ECN) 875 printf(" ecn"); 876 if (opts->flags & HFCF_RIO) 877 printf(" rio"); 878 if (opts->flags & HFCF_CLEARDSCP) 879 printf(" cleardscp"); 880 if (opts->flags & HFCF_DEFAULTCLASS) 881 printf(" default"); 882 if (opts->rtsc_m2 != 0) 883 print_hfsc_sc("realtime", opts->rtsc_m1, opts->rtsc_d, 884 opts->rtsc_m2, rtsc); 885 if (opts->lssc_m2 != 0 && (opts->lssc_m2 != a->bandwidth || 886 opts->lssc_d != 0)) 887 print_hfsc_sc("linkshare", opts->lssc_m1, opts->lssc_d, 888 opts->lssc_m2, lssc); 889 if (opts->ulsc_m2 != 0) 890 print_hfsc_sc("upperlimit", opts->ulsc_m1, opts->ulsc_d, 891 opts->ulsc_m2, ulsc); 892 printf(" ) "); 893 894 return (1); 895 } else 896 return (0); 897 } 898 899 /* 900 * admission control using generalized service curve 901 */ 902 #ifdef __OpenBSD__ 903 #define INFINITY HUGE_VAL /* positive infinity defined in <math.h> */ 904 #endif 905 906 /* add a new service curve to a generalized service curve */ 907 static void 908 gsc_add_sc(struct gen_sc *gsc, struct service_curve *sc) 909 { 910 if (is_sc_null(sc)) 911 return; 912 if (sc->d != 0) 913 gsc_add_seg(gsc, 0.0, 0.0, (double)sc->d, (double)sc->m1); 914 gsc_add_seg(gsc, (double)sc->d, 0.0, INFINITY, (double)sc->m2); 915 } 916 917 /* 918 * check whether all points of a generalized service curve have 919 * their y-coordinates no larger than a given two-piece linear 920 * service curve. 921 */ 922 static int 923 is_gsc_under_sc(struct gen_sc *gsc, struct service_curve *sc) 924 { 925 struct segment *s, *last, *end; 926 double y; 927 928 if (is_sc_null(sc)) { 929 if (LIST_EMPTY(gsc)) 930 return (1); 931 LIST_FOREACH(s, gsc, _next) { 932 if (s->m != 0) 933 return (0); 934 } 935 return (1); 936 } 937 /* 938 * gsc has a dummy entry at the end with x = INFINITY. 939 * loop through up to this dummy entry. 940 */ 941 end = gsc_getentry(gsc, INFINITY); 942 if (end == NULL) 943 return (1); 944 last = NULL; 945 for (s = LIST_FIRST(gsc); s != end; s = LIST_NEXT(s, _next)) { 946 if (s->y > sc_x2y(sc, s->x)) 947 return (0); 948 last = s; 949 } 950 /* last now holds the real last segment */ 951 if (last == NULL) 952 return (1); 953 if (last->m > sc->m2) 954 return (0); 955 if (last->x < sc->d && last->m > sc->m1) { 956 y = last->y + (sc->d - last->x) * last->m; 957 if (y > sc_x2y(sc, sc->d)) 958 return (0); 959 } 960 return (1); 961 } 962 963 static void 964 gsc_destroy(struct gen_sc *gsc) 965 { 966 struct segment *s; 967 968 while ((s = LIST_FIRST(gsc)) != NULL) { 969 LIST_REMOVE(s, _next); 970 free(s); 971 } 972 } 973 974 /* 975 * return a segment entry starting at x. 976 * if gsc has no entry starting at x, a new entry is created at x. 977 */ 978 static struct segment * 979 gsc_getentry(struct gen_sc *gsc, double x) 980 { 981 struct segment *new, *prev, *s; 982 983 prev = NULL; 984 LIST_FOREACH(s, gsc, _next) { 985 if (s->x == x) 986 return (s); /* matching entry found */ 987 else if (s->x < x) 988 prev = s; 989 else 990 break; 991 } 992 993 /* we have to create a new entry */ 994 if ((new = calloc(1, sizeof(struct segment))) == NULL) 995 return (NULL); 996 997 new->x = x; 998 if (x == INFINITY || s == NULL) 999 new->d = 0; 1000 else if (s->x == INFINITY) 1001 new->d = INFINITY; 1002 else 1003 new->d = s->x - x; 1004 if (prev == NULL) { 1005 /* insert the new entry at the head of the list */ 1006 new->y = 0; 1007 new->m = 0; 1008 LIST_INSERT_HEAD(gsc, new, _next); 1009 } else { 1010 /* 1011 * the start point intersects with the segment pointed by 1012 * prev. divide prev into 2 segments 1013 */ 1014 if (x == INFINITY) { 1015 prev->d = INFINITY; 1016 if (prev->m == 0) 1017 new->y = prev->y; 1018 else 1019 new->y = INFINITY; 1020 } else { 1021 prev->d = x - prev->x; 1022 new->y = prev->d * prev->m + prev->y; 1023 } 1024 new->m = prev->m; 1025 LIST_INSERT_AFTER(prev, new, _next); 1026 } 1027 return (new); 1028 } 1029 1030 /* add a segment to a generalized service curve */ 1031 static int 1032 gsc_add_seg(struct gen_sc *gsc, double x, double y, double d, double m) 1033 { 1034 struct segment *start, *end, *s; 1035 double x2; 1036 1037 if (d == INFINITY) 1038 x2 = INFINITY; 1039 else 1040 x2 = x + d; 1041 start = gsc_getentry(gsc, x); 1042 end = gsc_getentry(gsc, x2); 1043 if (start == NULL || end == NULL) 1044 return (-1); 1045 1046 for (s = start; s != end; s = LIST_NEXT(s, _next)) { 1047 s->m += m; 1048 s->y += y + (s->x - x) * m; 1049 } 1050 1051 end = gsc_getentry(gsc, INFINITY); 1052 for (; s != end; s = LIST_NEXT(s, _next)) { 1053 s->y += m * d; 1054 } 1055 1056 return (0); 1057 } 1058 1059 /* get y-projection of a service curve */ 1060 static double 1061 sc_x2y(struct service_curve *sc, double x) 1062 { 1063 double y; 1064 1065 if (x <= (double)sc->d) 1066 /* y belongs to the 1st segment */ 1067 y = x * (double)sc->m1; 1068 else 1069 /* y belongs to the 2nd segment */ 1070 y = (double)sc->d * (double)sc->m1 1071 + (x - (double)sc->d) * (double)sc->m2; 1072 return (y); 1073 } 1074 1075 /* 1076 * misc utilities 1077 */ 1078 #define R2S_BUFS 8 1079 #define RATESTR_MAX 16 1080 1081 char * 1082 rate2str(double rate) 1083 { 1084 char *buf; 1085 static char r2sbuf[R2S_BUFS][RATESTR_MAX]; /* ring bufer */ 1086 static int idx = 0; 1087 int i; 1088 static const char unit[] = " KMG"; 1089 1090 buf = r2sbuf[idx++]; 1091 if (idx == R2S_BUFS) 1092 idx = 0; 1093 1094 for (i = 0; rate >= 1000 && i <= 3; i++) 1095 rate /= 1000; 1096 1097 if ((int)(rate * 100) % 100) 1098 snprintf(buf, RATESTR_MAX, "%.2f%cb", rate, unit[i]); 1099 else 1100 snprintf(buf, RATESTR_MAX, "%d%cb", (int)rate, unit[i]); 1101 1102 return (buf); 1103 } 1104 1105 u_int32_t 1106 getifspeed(char *ifname) 1107 { 1108 int s; 1109 struct ifreq ifr; 1110 struct if_data ifrdat; 1111 1112 if ((s = socket(AF_INET, SOCK_DGRAM, 0)) < 0) 1113 err(1, "socket"); 1114 bzero(&ifr, sizeof(ifr)); 1115 if (strlcpy(ifr.ifr_name, ifname, sizeof(ifr.ifr_name)) >= 1116 sizeof(ifr.ifr_name)) 1117 errx(1, "getifspeed: strlcpy"); 1118 ifr.ifr_data = (caddr_t)&ifrdat; 1119 if (ioctl(s, SIOCGIFDATA, (caddr_t)&ifr) == -1) 1120 err(1, "SIOCGIFDATA"); 1121 if (shutdown(s, SHUT_RDWR) == -1) 1122 err(1, "shutdown"); 1123 if (close(s)) 1124 err(1, "close"); 1125 return ((u_int32_t)ifrdat.ifi_baudrate); 1126 } 1127 1128 u_long 1129 getifmtu(char *ifname) 1130 { 1131 int s; 1132 struct ifreq ifr; 1133 1134 if ((s = socket(AF_INET, SOCK_DGRAM, 0)) < 0) 1135 err(1, "socket"); 1136 bzero(&ifr, sizeof(ifr)); 1137 if (strlcpy(ifr.ifr_name, ifname, sizeof(ifr.ifr_name)) >= 1138 sizeof(ifr.ifr_name)) 1139 errx(1, "getifmtu: strlcpy"); 1140 if (ioctl(s, SIOCGIFMTU, (caddr_t)&ifr) == -1) 1141 err(1, "SIOCGIFMTU"); 1142 if (shutdown(s, SHUT_RDWR) == -1) 1143 err(1, "shutdown"); 1144 if (close(s)) 1145 err(1, "close"); 1146 if (ifr.ifr_mtu > 0) 1147 return (ifr.ifr_mtu); 1148 else { 1149 warnx("could not get mtu for %s, assuming 1500", ifname); 1150 return (1500); 1151 } 1152 } 1153 1154 int 1155 eval_queue_opts(struct pf_altq *pa, struct node_queue_opt *opts, 1156 u_int32_t ref_bw) 1157 { 1158 int errors = 0; 1159 1160 switch (pa->scheduler) { 1161 case ALTQT_CBQ: 1162 pa->pq_u.cbq_opts = opts->data.cbq_opts; 1163 break; 1164 case ALTQT_PRIQ: 1165 pa->pq_u.priq_opts = opts->data.priq_opts; 1166 break; 1167 case ALTQT_HFSC: 1168 pa->pq_u.hfsc_opts.flags = opts->data.hfsc_opts.flags; 1169 if (opts->data.hfsc_opts.linkshare.used) { 1170 pa->pq_u.hfsc_opts.lssc_m1 = 1171 eval_bwspec(&opts->data.hfsc_opts.linkshare.m1, 1172 ref_bw); 1173 pa->pq_u.hfsc_opts.lssc_m2 = 1174 eval_bwspec(&opts->data.hfsc_opts.linkshare.m2, 1175 ref_bw); 1176 pa->pq_u.hfsc_opts.lssc_d = 1177 opts->data.hfsc_opts.linkshare.d; 1178 } 1179 if (opts->data.hfsc_opts.realtime.used) { 1180 pa->pq_u.hfsc_opts.rtsc_m1 = 1181 eval_bwspec(&opts->data.hfsc_opts.realtime.m1, 1182 ref_bw); 1183 pa->pq_u.hfsc_opts.rtsc_m2 = 1184 eval_bwspec(&opts->data.hfsc_opts.realtime.m2, 1185 ref_bw); 1186 pa->pq_u.hfsc_opts.rtsc_d = 1187 opts->data.hfsc_opts.realtime.d; 1188 } 1189 if (opts->data.hfsc_opts.upperlimit.used) { 1190 pa->pq_u.hfsc_opts.ulsc_m1 = 1191 eval_bwspec(&opts->data.hfsc_opts.upperlimit.m1, 1192 ref_bw); 1193 pa->pq_u.hfsc_opts.ulsc_m2 = 1194 eval_bwspec(&opts->data.hfsc_opts.upperlimit.m2, 1195 ref_bw); 1196 pa->pq_u.hfsc_opts.ulsc_d = 1197 opts->data.hfsc_opts.upperlimit.d; 1198 } 1199 break; 1200 default: 1201 warnx("eval_queue_opts: unknown scheduler type %u", 1202 opts->qtype); 1203 errors++; 1204 break; 1205 } 1206 1207 return (errors); 1208 } 1209 1210 u_int32_t 1211 eval_bwspec(struct node_queue_bw *bw, u_int32_t ref_bw) 1212 { 1213 if (bw->bw_absolute > 0) 1214 return (bw->bw_absolute); 1215 1216 if (bw->bw_percent > 0) 1217 return (ref_bw / 100 * bw->bw_percent); 1218 1219 return (0); 1220 } 1221 1222 void 1223 print_hfsc_sc(const char *scname, u_int m1, u_int d, u_int m2, 1224 const struct node_hfsc_sc *sc) 1225 { 1226 printf(" %s", scname); 1227 1228 if (d != 0) { 1229 printf("("); 1230 if (sc != NULL && sc->m1.bw_percent > 0) 1231 printf("%u%%", sc->m1.bw_percent); 1232 else 1233 printf("%s", rate2str((double)m1)); 1234 printf(" %u", d); 1235 } 1236 1237 if (sc != NULL && sc->m2.bw_percent > 0) 1238 printf(" %u%%", sc->m2.bw_percent); 1239 else 1240 printf(" %s", rate2str((double)m2)); 1241 1242 if (d != 0) 1243 printf(")"); 1244 } 1245