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