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