pfctl_altq.c revision 177700 
1/*	$OpenBSD: pfctl_altq.c,v 1.91 2006/11/28 00:08:50 henning Exp $	*/
2
3/*
4 * Copyright (c) 2002
5 *	Sony Computer Science Laboratories Inc.
6 * Copyright (c) 2002, 2003 Henning Brauer <henning@openbsd.org>
7 *
8 * Permission to use, copy, modify, and distribute this software for any
9 * purpose with or without fee is hereby granted, provided that the above
10 * copyright notice and this permission notice appear in all copies.
11 *
12 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
13 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
14 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
15 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
16 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
17 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
18 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
19 */
20
21#include <sys/cdefs.h>
22__FBSDID("$FreeBSD: head/contrib/pf/pfctl/pfctl_altq.c 177700 2008-03-29 00:24:36Z mlaier $");
23
24#include <sys/param.h>
25#include <sys/ioctl.h>
26#include <sys/socket.h>
27
28#include <net/if.h>
29#include <netinet/in.h>
30#include <net/pfvar.h>
31
32#include <err.h>
33#include <errno.h>
34#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