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