Annotation of sys/altq/altq_hfsc.c, Revision 1.1
1.1 ! nbrk 1: /* $OpenBSD: altq_hfsc.c,v 1.24 2007/05/28 17:16:38 henning Exp $ */
! 2: /* $KAME: altq_hfsc.c,v 1.17 2002/11/29 07:48:33 kjc Exp $ */
! 3:
! 4: /*
! 5: * Copyright (c) 1997-1999 Carnegie Mellon University. All Rights Reserved.
! 6: *
! 7: * Permission to use, copy, modify, and distribute this software and
! 8: * its documentation is hereby granted (including for commercial or
! 9: * for-profit use), provided that both the copyright notice and this
! 10: * permission notice appear in all copies of the software, derivative
! 11: * works, or modified versions, and any portions thereof.
! 12: *
! 13: * THIS SOFTWARE IS EXPERIMENTAL AND IS KNOWN TO HAVE BUGS, SOME OF
! 14: * WHICH MAY HAVE SERIOUS CONSEQUENCES. CARNEGIE MELLON PROVIDES THIS
! 15: * SOFTWARE IN ITS ``AS IS'' CONDITION, AND ANY EXPRESS OR IMPLIED
! 16: * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
! 17: * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
! 18: * DISCLAIMED. IN NO EVENT SHALL CARNEGIE MELLON UNIVERSITY BE LIABLE
! 19: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
! 20: * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
! 21: * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
! 22: * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
! 23: * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
! 24: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
! 25: * USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
! 26: * DAMAGE.
! 27: *
! 28: * Carnegie Mellon encourages (but does not require) users of this
! 29: * software to return any improvements or extensions that they make,
! 30: * and to grant Carnegie Mellon the rights to redistribute these
! 31: * changes without encumbrance.
! 32: */
! 33: /*
! 34: * H-FSC is described in Proceedings of SIGCOMM'97,
! 35: * "A Hierarchical Fair Service Curve Algorithm for Link-Sharing,
! 36: * Real-Time and Priority Service"
! 37: * by Ion Stoica, Hui Zhang, and T. S. Eugene Ng.
! 38: *
! 39: * Oleg Cherevko <olwi@aq.ml.com.ua> added the upperlimit for link-sharing.
! 40: * when a class has an upperlimit, the fit-time is computed from the
! 41: * upperlimit service curve. the link-sharing scheduler does not schedule
! 42: * a class whose fit-time exceeds the current time.
! 43: */
! 44:
! 45: #include <sys/param.h>
! 46: #include <sys/malloc.h>
! 47: #include <sys/mbuf.h>
! 48: #include <sys/socket.h>
! 49: #include <sys/systm.h>
! 50: #include <sys/errno.h>
! 51: #include <sys/queue.h>
! 52:
! 53: #include <net/if.h>
! 54: #include <netinet/in.h>
! 55:
! 56: #include <net/pfvar.h>
! 57: #include <altq/altq.h>
! 58: #include <altq/altq_hfsc.h>
! 59:
! 60: /*
! 61: * function prototypes
! 62: */
! 63: static int hfsc_clear_interface(struct hfsc_if *);
! 64: static int hfsc_request(struct ifaltq *, int, void *);
! 65: static void hfsc_purge(struct hfsc_if *);
! 66: static struct hfsc_class *hfsc_class_create(struct hfsc_if *,
! 67: struct service_curve *, struct service_curve *, struct service_curve *,
! 68: struct hfsc_class *, int, int, int);
! 69: static int hfsc_class_destroy(struct hfsc_class *);
! 70: static struct hfsc_class *hfsc_nextclass(struct hfsc_class *);
! 71: static int hfsc_enqueue(struct ifaltq *, struct mbuf *,
! 72: struct altq_pktattr *);
! 73: static struct mbuf *hfsc_dequeue(struct ifaltq *, int);
! 74:
! 75: static int hfsc_addq(struct hfsc_class *, struct mbuf *);
! 76: static struct mbuf *hfsc_getq(struct hfsc_class *);
! 77: static struct mbuf *hfsc_pollq(struct hfsc_class *);
! 78: static void hfsc_purgeq(struct hfsc_class *);
! 79:
! 80: static void update_cfmin(struct hfsc_class *);
! 81: static void set_active(struct hfsc_class *, int);
! 82: static void set_passive(struct hfsc_class *);
! 83:
! 84: static void init_ed(struct hfsc_class *, int);
! 85: static void update_ed(struct hfsc_class *, int);
! 86: static void update_d(struct hfsc_class *, int);
! 87: static void init_vf(struct hfsc_class *, int);
! 88: static void update_vf(struct hfsc_class *, int, u_int64_t);
! 89: static ellist_t *ellist_alloc(void);
! 90: static void ellist_destroy(ellist_t *);
! 91: static void ellist_insert(struct hfsc_class *);
! 92: static void ellist_remove(struct hfsc_class *);
! 93: static void ellist_update(struct hfsc_class *);
! 94: struct hfsc_class *ellist_get_mindl(ellist_t *, u_int64_t);
! 95: static actlist_t *actlist_alloc(void);
! 96: static void actlist_destroy(actlist_t *);
! 97: static void actlist_insert(struct hfsc_class *);
! 98: static void actlist_remove(struct hfsc_class *);
! 99: static void actlist_update(struct hfsc_class *);
! 100:
! 101: static struct hfsc_class *actlist_firstfit(struct hfsc_class *,
! 102: u_int64_t);
! 103:
! 104: static __inline u_int64_t seg_x2y(u_int64_t, u_int64_t);
! 105: static __inline u_int64_t seg_y2x(u_int64_t, u_int64_t);
! 106: static __inline u_int64_t m2sm(u_int);
! 107: static __inline u_int64_t m2ism(u_int);
! 108: static __inline u_int64_t d2dx(u_int);
! 109: static u_int sm2m(u_int64_t);
! 110: static u_int dx2d(u_int64_t);
! 111:
! 112: static void sc2isc(struct service_curve *, struct internal_sc *);
! 113: static void rtsc_init(struct runtime_sc *, struct internal_sc *,
! 114: u_int64_t, u_int64_t);
! 115: static u_int64_t rtsc_y2x(struct runtime_sc *, u_int64_t);
! 116: static u_int64_t rtsc_x2y(struct runtime_sc *, u_int64_t);
! 117: static void rtsc_min(struct runtime_sc *, struct internal_sc *,
! 118: u_int64_t, u_int64_t);
! 119:
! 120: static void get_class_stats(struct hfsc_classstats *,
! 121: struct hfsc_class *);
! 122: static struct hfsc_class *clh_to_clp(struct hfsc_if *, u_int32_t);
! 123:
! 124: /*
! 125: * macros
! 126: */
! 127: #define is_a_parent_class(cl) ((cl)->cl_children != NULL)
! 128:
! 129: #define HT_INFINITY 0xffffffffffffffffLL /* infinite time value */
! 130:
! 131: int
! 132: hfsc_pfattach(struct pf_altq *a)
! 133: {
! 134: struct ifnet *ifp;
! 135: int s, error;
! 136:
! 137: if ((ifp = ifunit(a->ifname)) == NULL || a->altq_disc == NULL)
! 138: return (EINVAL);
! 139: s = splnet();
! 140: error = altq_attach(&ifp->if_snd, ALTQT_HFSC, a->altq_disc,
! 141: hfsc_enqueue, hfsc_dequeue, hfsc_request, NULL, NULL);
! 142: splx(s);
! 143: return (error);
! 144: }
! 145:
! 146: int
! 147: hfsc_add_altq(struct pf_altq *a)
! 148: {
! 149: struct hfsc_if *hif;
! 150: struct ifnet *ifp;
! 151:
! 152: if ((ifp = ifunit(a->ifname)) == NULL)
! 153: return (EINVAL);
! 154: if (!ALTQ_IS_READY(&ifp->if_snd))
! 155: return (ENODEV);
! 156:
! 157: MALLOC(hif, struct hfsc_if *, sizeof(struct hfsc_if),
! 158: M_DEVBUF, M_WAITOK);
! 159: if (hif == NULL)
! 160: return (ENOMEM);
! 161: bzero(hif, sizeof(struct hfsc_if));
! 162:
! 163: hif->hif_eligible = ellist_alloc();
! 164: if (hif->hif_eligible == NULL) {
! 165: FREE(hif, M_DEVBUF);
! 166: return (ENOMEM);
! 167: }
! 168:
! 169: hif->hif_ifq = &ifp->if_snd;
! 170:
! 171: /* keep the state in pf_altq */
! 172: a->altq_disc = hif;
! 173:
! 174: return (0);
! 175: }
! 176:
! 177: int
! 178: hfsc_remove_altq(struct pf_altq *a)
! 179: {
! 180: struct hfsc_if *hif;
! 181:
! 182: if ((hif = a->altq_disc) == NULL)
! 183: return (EINVAL);
! 184: a->altq_disc = NULL;
! 185:
! 186: (void)hfsc_clear_interface(hif);
! 187: (void)hfsc_class_destroy(hif->hif_rootclass);
! 188:
! 189: ellist_destroy(hif->hif_eligible);
! 190:
! 191: FREE(hif, M_DEVBUF);
! 192:
! 193: return (0);
! 194: }
! 195:
! 196: int
! 197: hfsc_add_queue(struct pf_altq *a)
! 198: {
! 199: struct hfsc_if *hif;
! 200: struct hfsc_class *cl, *parent;
! 201: struct hfsc_opts *opts;
! 202: struct service_curve rtsc, lssc, ulsc;
! 203:
! 204: if ((hif = a->altq_disc) == NULL)
! 205: return (EINVAL);
! 206:
! 207: opts = &a->pq_u.hfsc_opts;
! 208:
! 209: if (a->parent_qid == HFSC_NULLCLASS_HANDLE &&
! 210: hif->hif_rootclass == NULL)
! 211: parent = NULL;
! 212: else if ((parent = clh_to_clp(hif, a->parent_qid)) == NULL)
! 213: return (EINVAL);
! 214:
! 215: if (a->qid == 0)
! 216: return (EINVAL);
! 217:
! 218: if (clh_to_clp(hif, a->qid) != NULL)
! 219: return (EBUSY);
! 220:
! 221: rtsc.m1 = opts->rtsc_m1;
! 222: rtsc.d = opts->rtsc_d;
! 223: rtsc.m2 = opts->rtsc_m2;
! 224: lssc.m1 = opts->lssc_m1;
! 225: lssc.d = opts->lssc_d;
! 226: lssc.m2 = opts->lssc_m2;
! 227: ulsc.m1 = opts->ulsc_m1;
! 228: ulsc.d = opts->ulsc_d;
! 229: ulsc.m2 = opts->ulsc_m2;
! 230:
! 231: cl = hfsc_class_create(hif, &rtsc, &lssc, &ulsc,
! 232: parent, a->qlimit, opts->flags, a->qid);
! 233: if (cl == NULL)
! 234: return (ENOMEM);
! 235:
! 236: return (0);
! 237: }
! 238:
! 239: int
! 240: hfsc_remove_queue(struct pf_altq *a)
! 241: {
! 242: struct hfsc_if *hif;
! 243: struct hfsc_class *cl;
! 244:
! 245: if ((hif = a->altq_disc) == NULL)
! 246: return (EINVAL);
! 247:
! 248: if ((cl = clh_to_clp(hif, a->qid)) == NULL)
! 249: return (EINVAL);
! 250:
! 251: return (hfsc_class_destroy(cl));
! 252: }
! 253:
! 254: int
! 255: hfsc_getqstats(struct pf_altq *a, void *ubuf, int *nbytes)
! 256: {
! 257: struct hfsc_if *hif;
! 258: struct hfsc_class *cl;
! 259: struct hfsc_classstats stats;
! 260: int error = 0;
! 261:
! 262: if ((hif = altq_lookup(a->ifname, ALTQT_HFSC)) == NULL)
! 263: return (EBADF);
! 264:
! 265: if ((cl = clh_to_clp(hif, a->qid)) == NULL)
! 266: return (EINVAL);
! 267:
! 268: if (*nbytes < sizeof(stats))
! 269: return (EINVAL);
! 270:
! 271: get_class_stats(&stats, cl);
! 272:
! 273: if ((error = copyout((caddr_t)&stats, ubuf, sizeof(stats))) != 0)
! 274: return (error);
! 275: *nbytes = sizeof(stats);
! 276: return (0);
! 277: }
! 278:
! 279: /*
! 280: * bring the interface back to the initial state by discarding
! 281: * all the filters and classes except the root class.
! 282: */
! 283: static int
! 284: hfsc_clear_interface(struct hfsc_if *hif)
! 285: {
! 286: struct hfsc_class *cl;
! 287:
! 288: /* clear out the classes */
! 289: while (hif->hif_rootclass != NULL &&
! 290: (cl = hif->hif_rootclass->cl_children) != NULL) {
! 291: /*
! 292: * remove the first leaf class found in the hierarchy
! 293: * then start over
! 294: */
! 295: for (; cl != NULL; cl = hfsc_nextclass(cl)) {
! 296: if (!is_a_parent_class(cl)) {
! 297: (void)hfsc_class_destroy(cl);
! 298: break;
! 299: }
! 300: }
! 301: }
! 302:
! 303: return (0);
! 304: }
! 305:
! 306: static int
! 307: hfsc_request(struct ifaltq *ifq, int req, void *arg)
! 308: {
! 309: struct hfsc_if *hif = (struct hfsc_if *)ifq->altq_disc;
! 310:
! 311: switch (req) {
! 312: case ALTRQ_PURGE:
! 313: hfsc_purge(hif);
! 314: break;
! 315: }
! 316: return (0);
! 317: }
! 318:
! 319: /* discard all the queued packets on the interface */
! 320: static void
! 321: hfsc_purge(struct hfsc_if *hif)
! 322: {
! 323: struct hfsc_class *cl;
! 324:
! 325: for (cl = hif->hif_rootclass; cl != NULL; cl = hfsc_nextclass(cl))
! 326: if (!qempty(cl->cl_q))
! 327: hfsc_purgeq(cl);
! 328: if (ALTQ_IS_ENABLED(hif->hif_ifq))
! 329: hif->hif_ifq->ifq_len = 0;
! 330: }
! 331:
! 332: struct hfsc_class *
! 333: hfsc_class_create(struct hfsc_if *hif, struct service_curve *rsc,
! 334: struct service_curve *fsc, struct service_curve *usc,
! 335: struct hfsc_class *parent, int qlimit, int flags, int qid)
! 336: {
! 337: struct hfsc_class *cl, *p;
! 338: int i, s;
! 339:
! 340: if (hif->hif_classes >= HFSC_MAX_CLASSES)
! 341: return (NULL);
! 342:
! 343: #ifndef ALTQ_RED
! 344: if (flags & HFCF_RED) {
! 345: #ifdef ALTQ_DEBUG
! 346: printf("hfsc_class_create: RED not configured for HFSC!\n");
! 347: #endif
! 348: return (NULL);
! 349: }
! 350: #endif
! 351:
! 352: MALLOC(cl, struct hfsc_class *, sizeof(struct hfsc_class),
! 353: M_DEVBUF, M_WAITOK);
! 354: if (cl == NULL)
! 355: return (NULL);
! 356: bzero(cl, sizeof(struct hfsc_class));
! 357:
! 358: MALLOC(cl->cl_q, class_queue_t *, sizeof(class_queue_t),
! 359: M_DEVBUF, M_WAITOK);
! 360: if (cl->cl_q == NULL)
! 361: goto err_ret;
! 362: bzero(cl->cl_q, sizeof(class_queue_t));
! 363:
! 364: cl->cl_actc = actlist_alloc();
! 365: if (cl->cl_actc == NULL)
! 366: goto err_ret;
! 367:
! 368: if (qlimit == 0)
! 369: qlimit = 50; /* use default */
! 370: qlimit(cl->cl_q) = qlimit;
! 371: qtype(cl->cl_q) = Q_DROPTAIL;
! 372: qlen(cl->cl_q) = 0;
! 373: cl->cl_flags = flags;
! 374: #ifdef ALTQ_RED
! 375: if (flags & (HFCF_RED|HFCF_RIO)) {
! 376: int red_flags, red_pkttime;
! 377: u_int m2;
! 378:
! 379: m2 = 0;
! 380: if (rsc != NULL && rsc->m2 > m2)
! 381: m2 = rsc->m2;
! 382: if (fsc != NULL && fsc->m2 > m2)
! 383: m2 = fsc->m2;
! 384: if (usc != NULL && usc->m2 > m2)
! 385: m2 = usc->m2;
! 386:
! 387: red_flags = 0;
! 388: if (flags & HFCF_ECN)
! 389: red_flags |= REDF_ECN;
! 390: #ifdef ALTQ_RIO
! 391: if (flags & HFCF_CLEARDSCP)
! 392: red_flags |= RIOF_CLEARDSCP;
! 393: #endif
! 394: if (m2 < 8)
! 395: red_pkttime = 1000 * 1000 * 1000; /* 1 sec */
! 396: else
! 397: red_pkttime = (int64_t)hif->hif_ifq->altq_ifp->if_mtu
! 398: * 1000 * 1000 * 1000 / (m2 / 8);
! 399: if (flags & HFCF_RED) {
! 400: cl->cl_red = red_alloc(0, 0,
! 401: qlimit(cl->cl_q) * 10/100,
! 402: qlimit(cl->cl_q) * 30/100,
! 403: red_flags, red_pkttime);
! 404: if (cl->cl_red != NULL)
! 405: qtype(cl->cl_q) = Q_RED;
! 406: }
! 407: #ifdef ALTQ_RIO
! 408: else {
! 409: cl->cl_red = (red_t *)rio_alloc(0, NULL,
! 410: red_flags, red_pkttime);
! 411: if (cl->cl_red != NULL)
! 412: qtype(cl->cl_q) = Q_RIO;
! 413: }
! 414: #endif
! 415: }
! 416: #endif /* ALTQ_RED */
! 417:
! 418: if (rsc != NULL && (rsc->m1 != 0 || rsc->m2 != 0)) {
! 419: MALLOC(cl->cl_rsc, struct internal_sc *,
! 420: sizeof(struct internal_sc), M_DEVBUF, M_WAITOK);
! 421: if (cl->cl_rsc == NULL)
! 422: goto err_ret;
! 423: sc2isc(rsc, cl->cl_rsc);
! 424: rtsc_init(&cl->cl_deadline, cl->cl_rsc, 0, 0);
! 425: rtsc_init(&cl->cl_eligible, cl->cl_rsc, 0, 0);
! 426: }
! 427: if (fsc != NULL && (fsc->m1 != 0 || fsc->m2 != 0)) {
! 428: MALLOC(cl->cl_fsc, struct internal_sc *,
! 429: sizeof(struct internal_sc), M_DEVBUF, M_WAITOK);
! 430: if (cl->cl_fsc == NULL)
! 431: goto err_ret;
! 432: sc2isc(fsc, cl->cl_fsc);
! 433: rtsc_init(&cl->cl_virtual, cl->cl_fsc, 0, 0);
! 434: }
! 435: if (usc != NULL && (usc->m1 != 0 || usc->m2 != 0)) {
! 436: MALLOC(cl->cl_usc, struct internal_sc *,
! 437: sizeof(struct internal_sc), M_DEVBUF, M_WAITOK);
! 438: if (cl->cl_usc == NULL)
! 439: goto err_ret;
! 440: sc2isc(usc, cl->cl_usc);
! 441: rtsc_init(&cl->cl_ulimit, cl->cl_usc, 0, 0);
! 442: }
! 443:
! 444: cl->cl_id = hif->hif_classid++;
! 445: cl->cl_handle = qid;
! 446: cl->cl_hif = hif;
! 447: cl->cl_parent = parent;
! 448:
! 449: s = splnet();
! 450: hif->hif_classes++;
! 451:
! 452: /*
! 453: * find a free slot in the class table. if the slot matching
! 454: * the lower bits of qid is free, use this slot. otherwise,
! 455: * use the first free slot.
! 456: */
! 457: i = qid % HFSC_MAX_CLASSES;
! 458: if (hif->hif_class_tbl[i] == NULL)
! 459: hif->hif_class_tbl[i] = cl;
! 460: else {
! 461: for (i = 0; i < HFSC_MAX_CLASSES; i++)
! 462: if (hif->hif_class_tbl[i] == NULL) {
! 463: hif->hif_class_tbl[i] = cl;
! 464: break;
! 465: }
! 466: if (i == HFSC_MAX_CLASSES) {
! 467: splx(s);
! 468: goto err_ret;
! 469: }
! 470: }
! 471:
! 472: if (flags & HFCF_DEFAULTCLASS)
! 473: hif->hif_defaultclass = cl;
! 474:
! 475: if (parent == NULL) {
! 476: /* this is root class */
! 477: hif->hif_rootclass = cl;
! 478: } else {
! 479: /* add this class to the children list of the parent */
! 480: if ((p = parent->cl_children) == NULL)
! 481: parent->cl_children = cl;
! 482: else {
! 483: while (p->cl_siblings != NULL)
! 484: p = p->cl_siblings;
! 485: p->cl_siblings = cl;
! 486: }
! 487: }
! 488: splx(s);
! 489:
! 490: return (cl);
! 491:
! 492: err_ret:
! 493: if (cl->cl_actc != NULL)
! 494: actlist_destroy(cl->cl_actc);
! 495: if (cl->cl_red != NULL) {
! 496: #ifdef ALTQ_RIO
! 497: if (q_is_rio(cl->cl_q))
! 498: rio_destroy((rio_t *)cl->cl_red);
! 499: #endif
! 500: #ifdef ALTQ_RED
! 501: if (q_is_red(cl->cl_q))
! 502: red_destroy(cl->cl_red);
! 503: #endif
! 504: }
! 505: if (cl->cl_fsc != NULL)
! 506: FREE(cl->cl_fsc, M_DEVBUF);
! 507: if (cl->cl_rsc != NULL)
! 508: FREE(cl->cl_rsc, M_DEVBUF);
! 509: if (cl->cl_usc != NULL)
! 510: FREE(cl->cl_usc, M_DEVBUF);
! 511: if (cl->cl_q != NULL)
! 512: FREE(cl->cl_q, M_DEVBUF);
! 513: FREE(cl, M_DEVBUF);
! 514: return (NULL);
! 515: }
! 516:
! 517: static int
! 518: hfsc_class_destroy(struct hfsc_class *cl)
! 519: {
! 520: int i, s;
! 521:
! 522: if (cl == NULL)
! 523: return (0);
! 524:
! 525: if (is_a_parent_class(cl))
! 526: return (EBUSY);
! 527:
! 528: s = splnet();
! 529:
! 530: if (!qempty(cl->cl_q))
! 531: hfsc_purgeq(cl);
! 532:
! 533: if (cl->cl_parent == NULL) {
! 534: /* this is root class */
! 535: } else {
! 536: struct hfsc_class *p = cl->cl_parent->cl_children;
! 537:
! 538: if (p == cl)
! 539: cl->cl_parent->cl_children = cl->cl_siblings;
! 540: else do {
! 541: if (p->cl_siblings == cl) {
! 542: p->cl_siblings = cl->cl_siblings;
! 543: break;
! 544: }
! 545: } while ((p = p->cl_siblings) != NULL);
! 546: ASSERT(p != NULL);
! 547: }
! 548:
! 549: for (i = 0; i < HFSC_MAX_CLASSES; i++)
! 550: if (cl->cl_hif->hif_class_tbl[i] == cl) {
! 551: cl->cl_hif->hif_class_tbl[i] = NULL;
! 552: break;
! 553: }
! 554:
! 555: cl->cl_hif->hif_classes--;
! 556: splx(s);
! 557:
! 558: actlist_destroy(cl->cl_actc);
! 559:
! 560: if (cl->cl_red != NULL) {
! 561: #ifdef ALTQ_RIO
! 562: if (q_is_rio(cl->cl_q))
! 563: rio_destroy((rio_t *)cl->cl_red);
! 564: #endif
! 565: #ifdef ALTQ_RED
! 566: if (q_is_red(cl->cl_q))
! 567: red_destroy(cl->cl_red);
! 568: #endif
! 569: }
! 570:
! 571: if (cl == cl->cl_hif->hif_rootclass)
! 572: cl->cl_hif->hif_rootclass = NULL;
! 573: if (cl == cl->cl_hif->hif_defaultclass)
! 574: cl->cl_hif->hif_defaultclass = NULL;
! 575:
! 576: if (cl->cl_usc != NULL)
! 577: FREE(cl->cl_usc, M_DEVBUF);
! 578: if (cl->cl_fsc != NULL)
! 579: FREE(cl->cl_fsc, M_DEVBUF);
! 580: if (cl->cl_rsc != NULL)
! 581: FREE(cl->cl_rsc, M_DEVBUF);
! 582: FREE(cl->cl_q, M_DEVBUF);
! 583: FREE(cl, M_DEVBUF);
! 584:
! 585: return (0);
! 586: }
! 587:
! 588: /*
! 589: * hfsc_nextclass returns the next class in the tree.
! 590: * usage:
! 591: * for (cl = hif->hif_rootclass; cl != NULL; cl = hfsc_nextclass(cl))
! 592: * do_something;
! 593: */
! 594: static struct hfsc_class *
! 595: hfsc_nextclass(struct hfsc_class *cl)
! 596: {
! 597: if (cl->cl_children != NULL)
! 598: cl = cl->cl_children;
! 599: else if (cl->cl_siblings != NULL)
! 600: cl = cl->cl_siblings;
! 601: else {
! 602: while ((cl = cl->cl_parent) != NULL)
! 603: if (cl->cl_siblings) {
! 604: cl = cl->cl_siblings;
! 605: break;
! 606: }
! 607: }
! 608:
! 609: return (cl);
! 610: }
! 611:
! 612: /*
! 613: * hfsc_enqueue is an enqueue function to be registered to
! 614: * (*altq_enqueue) in struct ifaltq.
! 615: */
! 616: static int
! 617: hfsc_enqueue(struct ifaltq *ifq, struct mbuf *m, struct altq_pktattr *pktattr)
! 618: {
! 619: struct hfsc_if *hif = (struct hfsc_if *)ifq->altq_disc;
! 620: struct hfsc_class *cl;
! 621: int len;
! 622:
! 623: /* grab class set by classifier */
! 624: if ((m->m_flags & M_PKTHDR) == 0) {
! 625: /* should not happen */
! 626: printf("altq: packet for %s does not have pkthdr\n",
! 627: ifq->altq_ifp->if_xname);
! 628: m_freem(m);
! 629: return (ENOBUFS);
! 630: }
! 631: if ((cl = clh_to_clp(hif, m->m_pkthdr.pf.qid)) == NULL ||
! 632: is_a_parent_class(cl)) {
! 633: cl = hif->hif_defaultclass;
! 634: if (cl == NULL) {
! 635: m_freem(m);
! 636: return (ENOBUFS);
! 637: }
! 638: cl->cl_pktattr = NULL;
! 639: }
! 640:
! 641: len = m_pktlen(m);
! 642: if (hfsc_addq(cl, m) != 0) {
! 643: /* drop occurred. mbuf was freed in hfsc_addq. */
! 644: PKTCNTR_ADD(&cl->cl_stats.drop_cnt, len);
! 645: return (ENOBUFS);
! 646: }
! 647: IFQ_INC_LEN(ifq);
! 648: cl->cl_hif->hif_packets++;
! 649:
! 650: /* successfully queued. */
! 651: if (qlen(cl->cl_q) == 1)
! 652: set_active(cl, m_pktlen(m));
! 653:
! 654: return (0);
! 655: }
! 656:
! 657: /*
! 658: * hfsc_dequeue is a dequeue function to be registered to
! 659: * (*altq_dequeue) in struct ifaltq.
! 660: *
! 661: * note: ALTDQ_POLL returns the next packet without removing the packet
! 662: * from the queue. ALTDQ_REMOVE is a normal dequeue operation.
! 663: * ALTDQ_REMOVE must return the same packet if called immediately
! 664: * after ALTDQ_POLL.
! 665: */
! 666: static struct mbuf *
! 667: hfsc_dequeue(struct ifaltq *ifq, int op)
! 668: {
! 669: struct hfsc_if *hif = (struct hfsc_if *)ifq->altq_disc;
! 670: struct hfsc_class *cl;
! 671: struct mbuf *m;
! 672: int len, next_len;
! 673: int realtime = 0;
! 674: u_int64_t cur_time;
! 675:
! 676: if (hif->hif_packets == 0)
! 677: /* no packet in the tree */
! 678: return (NULL);
! 679:
! 680: cur_time = read_machclk();
! 681:
! 682: if (op == ALTDQ_REMOVE && hif->hif_pollcache != NULL) {
! 683:
! 684: cl = hif->hif_pollcache;
! 685: hif->hif_pollcache = NULL;
! 686: /* check if the class was scheduled by real-time criteria */
! 687: if (cl->cl_rsc != NULL)
! 688: realtime = (cl->cl_e <= cur_time);
! 689: } else {
! 690: /*
! 691: * if there are eligible classes, use real-time criteria.
! 692: * find the class with the minimum deadline among
! 693: * the eligible classes.
! 694: */
! 695: if ((cl = ellist_get_mindl(hif->hif_eligible, cur_time))
! 696: != NULL) {
! 697: realtime = 1;
! 698: } else {
! 699: #ifdef ALTQ_DEBUG
! 700: int fits = 0;
! 701: #endif
! 702: /*
! 703: * use link-sharing criteria
! 704: * get the class with the minimum vt in the hierarchy
! 705: */
! 706: cl = hif->hif_rootclass;
! 707: while (is_a_parent_class(cl)) {
! 708:
! 709: cl = actlist_firstfit(cl, cur_time);
! 710: if (cl == NULL) {
! 711: #ifdef ALTQ_DEBUG
! 712: if (fits > 0)
! 713: printf("%d fit but none found\n",fits);
! 714: #endif
! 715: return (NULL);
! 716: }
! 717: /*
! 718: * update parent's cl_cvtmin.
! 719: * don't update if the new vt is smaller.
! 720: */
! 721: if (cl->cl_parent->cl_cvtmin < cl->cl_vt)
! 722: cl->cl_parent->cl_cvtmin = cl->cl_vt;
! 723: #ifdef ALTQ_DEBUG
! 724: fits++;
! 725: #endif
! 726: }
! 727: }
! 728:
! 729: if (op == ALTDQ_POLL) {
! 730: hif->hif_pollcache = cl;
! 731: m = hfsc_pollq(cl);
! 732: return (m);
! 733: }
! 734: }
! 735:
! 736: m = hfsc_getq(cl);
! 737: if (m == NULL)
! 738: panic("hfsc_dequeue:");
! 739: len = m_pktlen(m);
! 740: cl->cl_hif->hif_packets--;
! 741: IFQ_DEC_LEN(ifq);
! 742: PKTCNTR_ADD(&cl->cl_stats.xmit_cnt, len);
! 743:
! 744: update_vf(cl, len, cur_time);
! 745: if (realtime)
! 746: cl->cl_cumul += len;
! 747:
! 748: if (!qempty(cl->cl_q)) {
! 749: if (cl->cl_rsc != NULL) {
! 750: /* update ed */
! 751: next_len = m_pktlen(qhead(cl->cl_q));
! 752:
! 753: if (realtime)
! 754: update_ed(cl, next_len);
! 755: else
! 756: update_d(cl, next_len);
! 757: }
! 758: } else {
! 759: /* the class becomes passive */
! 760: set_passive(cl);
! 761: }
! 762:
! 763: return (m);
! 764: }
! 765:
! 766: static int
! 767: hfsc_addq(struct hfsc_class *cl, struct mbuf *m)
! 768: {
! 769:
! 770: #ifdef ALTQ_RIO
! 771: if (q_is_rio(cl->cl_q))
! 772: return rio_addq((rio_t *)cl->cl_red, cl->cl_q,
! 773: m, cl->cl_pktattr);
! 774: #endif
! 775: #ifdef ALTQ_RED
! 776: if (q_is_red(cl->cl_q))
! 777: return red_addq(cl->cl_red, cl->cl_q, m, cl->cl_pktattr);
! 778: #endif
! 779: if (qlen(cl->cl_q) >= qlimit(cl->cl_q)) {
! 780: m_freem(m);
! 781: return (-1);
! 782: }
! 783:
! 784: if (cl->cl_flags & HFCF_CLEARDSCP)
! 785: write_dsfield(m, cl->cl_pktattr, 0);
! 786:
! 787: _addq(cl->cl_q, m);
! 788:
! 789: return (0);
! 790: }
! 791:
! 792: static struct mbuf *
! 793: hfsc_getq(struct hfsc_class *cl)
! 794: {
! 795: #ifdef ALTQ_RIO
! 796: if (q_is_rio(cl->cl_q))
! 797: return rio_getq((rio_t *)cl->cl_red, cl->cl_q);
! 798: #endif
! 799: #ifdef ALTQ_RED
! 800: if (q_is_red(cl->cl_q))
! 801: return red_getq(cl->cl_red, cl->cl_q);
! 802: #endif
! 803: return _getq(cl->cl_q);
! 804: }
! 805:
! 806: static struct mbuf *
! 807: hfsc_pollq(struct hfsc_class *cl)
! 808: {
! 809: return qhead(cl->cl_q);
! 810: }
! 811:
! 812: static void
! 813: hfsc_purgeq(struct hfsc_class *cl)
! 814: {
! 815: struct mbuf *m;
! 816:
! 817: if (qempty(cl->cl_q))
! 818: return;
! 819:
! 820: while ((m = _getq(cl->cl_q)) != NULL) {
! 821: PKTCNTR_ADD(&cl->cl_stats.drop_cnt, m_pktlen(m));
! 822: m_freem(m);
! 823: cl->cl_hif->hif_packets--;
! 824: IFQ_DEC_LEN(cl->cl_hif->hif_ifq);
! 825: }
! 826: ASSERT(qlen(cl->cl_q) == 0);
! 827:
! 828: update_vf(cl, 0, 0); /* remove cl from the actlist */
! 829: set_passive(cl);
! 830: }
! 831:
! 832: static void
! 833: set_active(struct hfsc_class *cl, int len)
! 834: {
! 835: if (cl->cl_rsc != NULL)
! 836: init_ed(cl, len);
! 837: if (cl->cl_fsc != NULL)
! 838: init_vf(cl, len);
! 839:
! 840: cl->cl_stats.period++;
! 841: }
! 842:
! 843: static void
! 844: set_passive(struct hfsc_class *cl)
! 845: {
! 846: if (cl->cl_rsc != NULL)
! 847: ellist_remove(cl);
! 848:
! 849: /*
! 850: * actlist is now handled in update_vf() so that update_vf(cl, 0, 0)
! 851: * needs to be called explicitly to remove a class from actlist
! 852: */
! 853: }
! 854:
! 855: static void
! 856: init_ed(struct hfsc_class *cl, int next_len)
! 857: {
! 858: u_int64_t cur_time;
! 859:
! 860: cur_time = read_machclk();
! 861:
! 862: /* update the deadline curve */
! 863: rtsc_min(&cl->cl_deadline, cl->cl_rsc, cur_time, cl->cl_cumul);
! 864:
! 865: /*
! 866: * update the eligible curve.
! 867: * for concave, it is equal to the deadline curve.
! 868: * for convex, it is a linear curve with slope m2.
! 869: */
! 870: cl->cl_eligible = cl->cl_deadline;
! 871: if (cl->cl_rsc->sm1 <= cl->cl_rsc->sm2) {
! 872: cl->cl_eligible.dx = 0;
! 873: cl->cl_eligible.dy = 0;
! 874: }
! 875:
! 876: /* compute e and d */
! 877: cl->cl_e = rtsc_y2x(&cl->cl_eligible, cl->cl_cumul);
! 878: cl->cl_d = rtsc_y2x(&cl->cl_deadline, cl->cl_cumul + next_len);
! 879:
! 880: ellist_insert(cl);
! 881: }
! 882:
! 883: static void
! 884: update_ed(struct hfsc_class *cl, int next_len)
! 885: {
! 886: cl->cl_e = rtsc_y2x(&cl->cl_eligible, cl->cl_cumul);
! 887: cl->cl_d = rtsc_y2x(&cl->cl_deadline, cl->cl_cumul + next_len);
! 888:
! 889: ellist_update(cl);
! 890: }
! 891:
! 892: static void
! 893: update_d(struct hfsc_class *cl, int next_len)
! 894: {
! 895: cl->cl_d = rtsc_y2x(&cl->cl_deadline, cl->cl_cumul + next_len);
! 896: }
! 897:
! 898: static void
! 899: init_vf(struct hfsc_class *cl, int len)
! 900: {
! 901: struct hfsc_class *max_cl, *p;
! 902: u_int64_t vt, f, cur_time;
! 903: int go_active;
! 904:
! 905: cur_time = 0;
! 906: go_active = 1;
! 907: for ( ; cl->cl_parent != NULL; cl = cl->cl_parent) {
! 908:
! 909: if (go_active && cl->cl_nactive++ == 0)
! 910: go_active = 1;
! 911: else
! 912: go_active = 0;
! 913:
! 914: if (go_active) {
! 915: max_cl = actlist_last(cl->cl_parent->cl_actc);
! 916: if (max_cl != NULL) {
! 917: /*
! 918: * set vt to the average of the min and max
! 919: * classes. if the parent's period didn't
! 920: * change, don't decrease vt of the class.
! 921: */
! 922: vt = max_cl->cl_vt;
! 923: if (cl->cl_parent->cl_cvtmin != 0)
! 924: vt = (cl->cl_parent->cl_cvtmin + vt)/2;
! 925:
! 926: if (cl->cl_parent->cl_vtperiod !=
! 927: cl->cl_parentperiod || vt > cl->cl_vt)
! 928: cl->cl_vt = vt;
! 929: } else {
! 930: /*
! 931: * first child for a new parent backlog period.
! 932: * add parent's cvtmax to vtoff of children
! 933: * to make a new vt (vtoff + vt) larger than
! 934: * the vt in the last period for all children.
! 935: */
! 936: vt = cl->cl_parent->cl_cvtmax;
! 937: for (p = cl->cl_parent->cl_children; p != NULL;
! 938: p = p->cl_siblings)
! 939: p->cl_vtoff += vt;
! 940: cl->cl_vt = 0;
! 941: cl->cl_parent->cl_cvtmax = 0;
! 942: cl->cl_parent->cl_cvtmin = 0;
! 943: }
! 944: cl->cl_initvt = cl->cl_vt;
! 945:
! 946: /* update the virtual curve */
! 947: vt = cl->cl_vt + cl->cl_vtoff;
! 948: rtsc_min(&cl->cl_virtual, cl->cl_fsc, vt, cl->cl_total);
! 949: if (cl->cl_virtual.x == vt) {
! 950: cl->cl_virtual.x -= cl->cl_vtoff;
! 951: cl->cl_vtoff = 0;
! 952: }
! 953: cl->cl_vtadj = 0;
! 954:
! 955: cl->cl_vtperiod++; /* increment vt period */
! 956: cl->cl_parentperiod = cl->cl_parent->cl_vtperiod;
! 957: if (cl->cl_parent->cl_nactive == 0)
! 958: cl->cl_parentperiod++;
! 959: cl->cl_f = 0;
! 960:
! 961: actlist_insert(cl);
! 962:
! 963: if (cl->cl_usc != NULL) {
! 964: /* class has upper limit curve */
! 965: if (cur_time == 0)
! 966: cur_time = read_machclk();
! 967:
! 968: /* update the ulimit curve */
! 969: rtsc_min(&cl->cl_ulimit, cl->cl_usc, cur_time,
! 970: cl->cl_total);
! 971: /* compute myf */
! 972: cl->cl_myf = rtsc_y2x(&cl->cl_ulimit,
! 973: cl->cl_total);
! 974: cl->cl_myfadj = 0;
! 975: }
! 976: }
! 977:
! 978: if (cl->cl_myf > cl->cl_cfmin)
! 979: f = cl->cl_myf;
! 980: else
! 981: f = cl->cl_cfmin;
! 982: if (f != cl->cl_f) {
! 983: cl->cl_f = f;
! 984: update_cfmin(cl->cl_parent);
! 985: }
! 986: }
! 987: }
! 988:
! 989: static void
! 990: update_vf(struct hfsc_class *cl, int len, u_int64_t cur_time)
! 991: {
! 992: u_int64_t f, myf_bound, delta;
! 993: int go_passive;
! 994:
! 995: go_passive = qempty(cl->cl_q);
! 996:
! 997: for (; cl->cl_parent != NULL; cl = cl->cl_parent) {
! 998:
! 999: cl->cl_total += len;
! 1000:
! 1001: if (cl->cl_fsc == NULL || cl->cl_nactive == 0)
! 1002: continue;
! 1003:
! 1004: if (go_passive && --cl->cl_nactive == 0)
! 1005: go_passive = 1;
! 1006: else
! 1007: go_passive = 0;
! 1008:
! 1009: if (go_passive) {
! 1010: /* no more active child, going passive */
! 1011:
! 1012: /* update cvtmax of the parent class */
! 1013: if (cl->cl_vt > cl->cl_parent->cl_cvtmax)
! 1014: cl->cl_parent->cl_cvtmax = cl->cl_vt;
! 1015:
! 1016: /* remove this class from the vt list */
! 1017: actlist_remove(cl);
! 1018:
! 1019: update_cfmin(cl->cl_parent);
! 1020:
! 1021: continue;
! 1022: }
! 1023:
! 1024: /*
! 1025: * update vt and f
! 1026: */
! 1027: cl->cl_vt = rtsc_y2x(&cl->cl_virtual, cl->cl_total)
! 1028: - cl->cl_vtoff + cl->cl_vtadj;
! 1029:
! 1030: /*
! 1031: * if vt of the class is smaller than cvtmin,
! 1032: * the class was skipped in the past due to non-fit.
! 1033: * if so, we need to adjust vtadj.
! 1034: */
! 1035: if (cl->cl_vt < cl->cl_parent->cl_cvtmin) {
! 1036: cl->cl_vtadj += cl->cl_parent->cl_cvtmin - cl->cl_vt;
! 1037: cl->cl_vt = cl->cl_parent->cl_cvtmin;
! 1038: }
! 1039:
! 1040: /* update the vt list */
! 1041: actlist_update(cl);
! 1042:
! 1043: if (cl->cl_usc != NULL) {
! 1044: cl->cl_myf = cl->cl_myfadj
! 1045: + rtsc_y2x(&cl->cl_ulimit, cl->cl_total);
! 1046:
! 1047: /*
! 1048: * if myf lags behind by more than one clock tick
! 1049: * from the current time, adjust myfadj to prevent
! 1050: * a rate-limited class from going greedy.
! 1051: * in a steady state under rate-limiting, myf
! 1052: * fluctuates within one clock tick.
! 1053: */
! 1054: myf_bound = cur_time - machclk_per_tick;
! 1055: if (cl->cl_myf < myf_bound) {
! 1056: delta = cur_time - cl->cl_myf;
! 1057: cl->cl_myfadj += delta;
! 1058: cl->cl_myf += delta;
! 1059: }
! 1060: }
! 1061:
! 1062: /* cl_f is max(cl_myf, cl_cfmin) */
! 1063: if (cl->cl_myf > cl->cl_cfmin)
! 1064: f = cl->cl_myf;
! 1065: else
! 1066: f = cl->cl_cfmin;
! 1067: if (f != cl->cl_f) {
! 1068: cl->cl_f = f;
! 1069: update_cfmin(cl->cl_parent);
! 1070: }
! 1071: }
! 1072: }
! 1073:
! 1074: static void
! 1075: update_cfmin(struct hfsc_class *cl)
! 1076: {
! 1077: struct hfsc_class *p;
! 1078: u_int64_t cfmin;
! 1079:
! 1080: if (TAILQ_EMPTY(cl->cl_actc)) {
! 1081: cl->cl_cfmin = 0;
! 1082: return;
! 1083: }
! 1084: cfmin = HT_INFINITY;
! 1085: TAILQ_FOREACH(p, cl->cl_actc, cl_actlist) {
! 1086: if (p->cl_f == 0) {
! 1087: cl->cl_cfmin = 0;
! 1088: return;
! 1089: }
! 1090: if (p->cl_f < cfmin)
! 1091: cfmin = p->cl_f;
! 1092: }
! 1093: cl->cl_cfmin = cfmin;
! 1094: }
! 1095:
! 1096: /*
! 1097: * TAILQ based ellist and actlist implementation
! 1098: * (ion wanted to make a calendar queue based implementation)
! 1099: */
! 1100: /*
! 1101: * eligible list holds backlogged classes being sorted by their eligible times.
! 1102: * there is one eligible list per interface.
! 1103: */
! 1104:
! 1105: static ellist_t *
! 1106: ellist_alloc(void)
! 1107: {
! 1108: ellist_t *head;
! 1109:
! 1110: MALLOC(head, ellist_t *, sizeof(ellist_t), M_DEVBUF, M_WAITOK);
! 1111: TAILQ_INIT(head);
! 1112: return (head);
! 1113: }
! 1114:
! 1115: static void
! 1116: ellist_destroy(ellist_t *head)
! 1117: {
! 1118: FREE(head, M_DEVBUF);
! 1119: }
! 1120:
! 1121: static void
! 1122: ellist_insert(struct hfsc_class *cl)
! 1123: {
! 1124: struct hfsc_if *hif = cl->cl_hif;
! 1125: struct hfsc_class *p;
! 1126:
! 1127: /* check the last entry first */
! 1128: if ((p = TAILQ_LAST(hif->hif_eligible, _eligible)) == NULL ||
! 1129: p->cl_e <= cl->cl_e) {
! 1130: TAILQ_INSERT_TAIL(hif->hif_eligible, cl, cl_ellist);
! 1131: return;
! 1132: }
! 1133:
! 1134: TAILQ_FOREACH(p, hif->hif_eligible, cl_ellist) {
! 1135: if (cl->cl_e < p->cl_e) {
! 1136: TAILQ_INSERT_BEFORE(p, cl, cl_ellist);
! 1137: return;
! 1138: }
! 1139: }
! 1140: ASSERT(0); /* should not reach here */
! 1141: }
! 1142:
! 1143: static void
! 1144: ellist_remove(struct hfsc_class *cl)
! 1145: {
! 1146: struct hfsc_if *hif = cl->cl_hif;
! 1147:
! 1148: TAILQ_REMOVE(hif->hif_eligible, cl, cl_ellist);
! 1149: }
! 1150:
! 1151: static void
! 1152: ellist_update(struct hfsc_class *cl)
! 1153: {
! 1154: struct hfsc_if *hif = cl->cl_hif;
! 1155: struct hfsc_class *p, *last;
! 1156:
! 1157: /*
! 1158: * the eligible time of a class increases monotonically.
! 1159: * if the next entry has a larger eligible time, nothing to do.
! 1160: */
! 1161: p = TAILQ_NEXT(cl, cl_ellist);
! 1162: if (p == NULL || cl->cl_e <= p->cl_e)
! 1163: return;
! 1164:
! 1165: /* check the last entry */
! 1166: last = TAILQ_LAST(hif->hif_eligible, _eligible);
! 1167: ASSERT(last != NULL);
! 1168: if (last->cl_e <= cl->cl_e) {
! 1169: TAILQ_REMOVE(hif->hif_eligible, cl, cl_ellist);
! 1170: TAILQ_INSERT_TAIL(hif->hif_eligible, cl, cl_ellist);
! 1171: return;
! 1172: }
! 1173:
! 1174: /*
! 1175: * the new position must be between the next entry
! 1176: * and the last entry
! 1177: */
! 1178: while ((p = TAILQ_NEXT(p, cl_ellist)) != NULL) {
! 1179: if (cl->cl_e < p->cl_e) {
! 1180: TAILQ_REMOVE(hif->hif_eligible, cl, cl_ellist);
! 1181: TAILQ_INSERT_BEFORE(p, cl, cl_ellist);
! 1182: return;
! 1183: }
! 1184: }
! 1185: ASSERT(0); /* should not reach here */
! 1186: }
! 1187:
! 1188: /* find the class with the minimum deadline among the eligible classes */
! 1189: struct hfsc_class *
! 1190: ellist_get_mindl(ellist_t *head, u_int64_t cur_time)
! 1191: {
! 1192: struct hfsc_class *p, *cl = NULL;
! 1193:
! 1194: TAILQ_FOREACH(p, head, cl_ellist) {
! 1195: if (p->cl_e > cur_time)
! 1196: break;
! 1197: if (cl == NULL || p->cl_d < cl->cl_d)
! 1198: cl = p;
! 1199: }
! 1200: return (cl);
! 1201: }
! 1202:
! 1203: /*
! 1204: * active children list holds backlogged child classes being sorted
! 1205: * by their virtual time.
! 1206: * each intermediate class has one active children list.
! 1207: */
! 1208: static actlist_t *
! 1209: actlist_alloc(void)
! 1210: {
! 1211: actlist_t *head;
! 1212:
! 1213: MALLOC(head, actlist_t *, sizeof(actlist_t), M_DEVBUF, M_WAITOK);
! 1214: TAILQ_INIT(head);
! 1215: return (head);
! 1216: }
! 1217:
! 1218: static void
! 1219: actlist_destroy(actlist_t *head)
! 1220: {
! 1221: FREE(head, M_DEVBUF);
! 1222: }
! 1223: static void
! 1224: actlist_insert(struct hfsc_class *cl)
! 1225: {
! 1226: struct hfsc_class *p;
! 1227:
! 1228: /* check the last entry first */
! 1229: if ((p = TAILQ_LAST(cl->cl_parent->cl_actc, _active)) == NULL
! 1230: || p->cl_vt <= cl->cl_vt) {
! 1231: TAILQ_INSERT_TAIL(cl->cl_parent->cl_actc, cl, cl_actlist);
! 1232: return;
! 1233: }
! 1234:
! 1235: TAILQ_FOREACH(p, cl->cl_parent->cl_actc, cl_actlist) {
! 1236: if (cl->cl_vt < p->cl_vt) {
! 1237: TAILQ_INSERT_BEFORE(p, cl, cl_actlist);
! 1238: return;
! 1239: }
! 1240: }
! 1241: ASSERT(0); /* should not reach here */
! 1242: }
! 1243:
! 1244: static void
! 1245: actlist_remove(struct hfsc_class *cl)
! 1246: {
! 1247: TAILQ_REMOVE(cl->cl_parent->cl_actc, cl, cl_actlist);
! 1248: }
! 1249:
! 1250: static void
! 1251: actlist_update(struct hfsc_class *cl)
! 1252: {
! 1253: struct hfsc_class *p, *last;
! 1254:
! 1255: /*
! 1256: * the virtual time of a class increases monotonically during its
! 1257: * backlogged period.
! 1258: * if the next entry has a larger virtual time, nothing to do.
! 1259: */
! 1260: p = TAILQ_NEXT(cl, cl_actlist);
! 1261: if (p == NULL || cl->cl_vt < p->cl_vt)
! 1262: return;
! 1263:
! 1264: /* check the last entry */
! 1265: last = TAILQ_LAST(cl->cl_parent->cl_actc, _active);
! 1266: ASSERT(last != NULL);
! 1267: if (last->cl_vt <= cl->cl_vt) {
! 1268: TAILQ_REMOVE(cl->cl_parent->cl_actc, cl, cl_actlist);
! 1269: TAILQ_INSERT_TAIL(cl->cl_parent->cl_actc, cl, cl_actlist);
! 1270: return;
! 1271: }
! 1272:
! 1273: /*
! 1274: * the new position must be between the next entry
! 1275: * and the last entry
! 1276: */
! 1277: while ((p = TAILQ_NEXT(p, cl_actlist)) != NULL) {
! 1278: if (cl->cl_vt < p->cl_vt) {
! 1279: TAILQ_REMOVE(cl->cl_parent->cl_actc, cl, cl_actlist);
! 1280: TAILQ_INSERT_BEFORE(p, cl, cl_actlist);
! 1281: return;
! 1282: }
! 1283: }
! 1284: ASSERT(0); /* should not reach here */
! 1285: }
! 1286:
! 1287: static struct hfsc_class *
! 1288: actlist_firstfit(struct hfsc_class *cl, u_int64_t cur_time)
! 1289: {
! 1290: struct hfsc_class *p;
! 1291:
! 1292: TAILQ_FOREACH(p, cl->cl_actc, cl_actlist) {
! 1293: if (p->cl_f <= cur_time)
! 1294: return (p);
! 1295: }
! 1296: return (NULL);
! 1297: }
! 1298:
! 1299: /*
! 1300: * service curve support functions
! 1301: *
! 1302: * external service curve parameters
! 1303: * m: bits/sec
! 1304: * d: msec
! 1305: * internal service curve parameters
! 1306: * sm: (bytes/tsc_interval) << SM_SHIFT
! 1307: * ism: (tsc_count/byte) << ISM_SHIFT
! 1308: * dx: tsc_count
! 1309: *
! 1310: * SM_SHIFT and ISM_SHIFT are scaled in order to keep effective digits.
! 1311: * we should be able to handle 100K-1Gbps linkspeed with 200Hz-1GHz CPU
! 1312: * speed. SM_SHIFT and ISM_SHIFT are selected to have at least 3 effective
! 1313: * digits in decimal using the following table.
! 1314: *
! 1315: * bits/sec 100Kbps 1Mbps 10Mbps 100Mbps 1Gbps
! 1316: * ----------+-------------------------------------------------------
! 1317: * bytes/nsec 12.5e-6 125e-6 1250e-6 12500e-6 125000e-6
! 1318: * sm(500MHz) 25.0e-6 250e-6 2500e-6 25000e-6 250000e-6
! 1319: * sm(200MHz) 62.5e-6 625e-6 6250e-6 62500e-6 625000e-6
! 1320: *
! 1321: * nsec/byte 80000 8000 800 80 8
! 1322: * ism(500MHz) 40000 4000 400 40 4
! 1323: * ism(200MHz) 16000 1600 160 16 1.6
! 1324: */
! 1325: #define SM_SHIFT 24
! 1326: #define ISM_SHIFT 10
! 1327:
! 1328: #define SM_MASK ((1LL << SM_SHIFT) - 1)
! 1329: #define ISM_MASK ((1LL << ISM_SHIFT) - 1)
! 1330:
! 1331: static __inline u_int64_t
! 1332: seg_x2y(u_int64_t x, u_int64_t sm)
! 1333: {
! 1334: u_int64_t y;
! 1335:
! 1336: /*
! 1337: * compute
! 1338: * y = x * sm >> SM_SHIFT
! 1339: * but divide it for the upper and lower bits to avoid overflow
! 1340: */
! 1341: y = (x >> SM_SHIFT) * sm + (((x & SM_MASK) * sm) >> SM_SHIFT);
! 1342: return (y);
! 1343: }
! 1344:
! 1345: static __inline u_int64_t
! 1346: seg_y2x(u_int64_t y, u_int64_t ism)
! 1347: {
! 1348: u_int64_t x;
! 1349:
! 1350: if (y == 0)
! 1351: x = 0;
! 1352: else if (ism == HT_INFINITY)
! 1353: x = HT_INFINITY;
! 1354: else {
! 1355: x = (y >> ISM_SHIFT) * ism
! 1356: + (((y & ISM_MASK) * ism) >> ISM_SHIFT);
! 1357: }
! 1358: return (x);
! 1359: }
! 1360:
! 1361: static __inline u_int64_t
! 1362: m2sm(u_int m)
! 1363: {
! 1364: u_int64_t sm;
! 1365:
! 1366: sm = ((u_int64_t)m << SM_SHIFT) / 8 / machclk_freq;
! 1367: return (sm);
! 1368: }
! 1369:
! 1370: static __inline u_int64_t
! 1371: m2ism(u_int m)
! 1372: {
! 1373: u_int64_t ism;
! 1374:
! 1375: if (m == 0)
! 1376: ism = HT_INFINITY;
! 1377: else
! 1378: ism = ((u_int64_t)machclk_freq << ISM_SHIFT) * 8 / m;
! 1379: return (ism);
! 1380: }
! 1381:
! 1382: static __inline u_int64_t
! 1383: d2dx(u_int d)
! 1384: {
! 1385: u_int64_t dx;
! 1386:
! 1387: dx = ((u_int64_t)d * machclk_freq) / 1000;
! 1388: return (dx);
! 1389: }
! 1390:
! 1391: static u_int
! 1392: sm2m(u_int64_t sm)
! 1393: {
! 1394: u_int64_t m;
! 1395:
! 1396: m = (sm * 8 * machclk_freq) >> SM_SHIFT;
! 1397: return ((u_int)m);
! 1398: }
! 1399:
! 1400: static u_int
! 1401: dx2d(u_int64_t dx)
! 1402: {
! 1403: u_int64_t d;
! 1404:
! 1405: d = dx * 1000 / machclk_freq;
! 1406: return ((u_int)d);
! 1407: }
! 1408:
! 1409: static void
! 1410: sc2isc(struct service_curve *sc, struct internal_sc *isc)
! 1411: {
! 1412: isc->sm1 = m2sm(sc->m1);
! 1413: isc->ism1 = m2ism(sc->m1);
! 1414: isc->dx = d2dx(sc->d);
! 1415: isc->dy = seg_x2y(isc->dx, isc->sm1);
! 1416: isc->sm2 = m2sm(sc->m2);
! 1417: isc->ism2 = m2ism(sc->m2);
! 1418: }
! 1419:
! 1420: /*
! 1421: * initialize the runtime service curve with the given internal
! 1422: * service curve starting at (x, y).
! 1423: */
! 1424: static void
! 1425: rtsc_init(struct runtime_sc *rtsc, struct internal_sc * isc, u_int64_t x,
! 1426: u_int64_t y)
! 1427: {
! 1428: rtsc->x = x;
! 1429: rtsc->y = y;
! 1430: rtsc->sm1 = isc->sm1;
! 1431: rtsc->ism1 = isc->ism1;
! 1432: rtsc->dx = isc->dx;
! 1433: rtsc->dy = isc->dy;
! 1434: rtsc->sm2 = isc->sm2;
! 1435: rtsc->ism2 = isc->ism2;
! 1436: }
! 1437:
! 1438: /*
! 1439: * calculate the y-projection of the runtime service curve by the
! 1440: * given x-projection value
! 1441: */
! 1442: static u_int64_t
! 1443: rtsc_y2x(struct runtime_sc *rtsc, u_int64_t y)
! 1444: {
! 1445: u_int64_t x;
! 1446:
! 1447: if (y < rtsc->y)
! 1448: x = rtsc->x;
! 1449: else if (y <= rtsc->y + rtsc->dy) {
! 1450: /* x belongs to the 1st segment */
! 1451: if (rtsc->dy == 0)
! 1452: x = rtsc->x + rtsc->dx;
! 1453: else
! 1454: x = rtsc->x + seg_y2x(y - rtsc->y, rtsc->ism1);
! 1455: } else {
! 1456: /* x belongs to the 2nd segment */
! 1457: x = rtsc->x + rtsc->dx
! 1458: + seg_y2x(y - rtsc->y - rtsc->dy, rtsc->ism2);
! 1459: }
! 1460: return (x);
! 1461: }
! 1462:
! 1463: static u_int64_t
! 1464: rtsc_x2y(struct runtime_sc *rtsc, u_int64_t x)
! 1465: {
! 1466: u_int64_t y;
! 1467:
! 1468: if (x <= rtsc->x)
! 1469: y = rtsc->y;
! 1470: else if (x <= rtsc->x + rtsc->dx)
! 1471: /* y belongs to the 1st segment */
! 1472: y = rtsc->y + seg_x2y(x - rtsc->x, rtsc->sm1);
! 1473: else
! 1474: /* y belongs to the 2nd segment */
! 1475: y = rtsc->y + rtsc->dy
! 1476: + seg_x2y(x - rtsc->x - rtsc->dx, rtsc->sm2);
! 1477: return (y);
! 1478: }
! 1479:
! 1480: /*
! 1481: * update the runtime service curve by taking the minimum of the current
! 1482: * runtime service curve and the service curve starting at (x, y).
! 1483: */
! 1484: static void
! 1485: rtsc_min(struct runtime_sc *rtsc, struct internal_sc *isc, u_int64_t x,
! 1486: u_int64_t y)
! 1487: {
! 1488: u_int64_t y1, y2, dx, dy;
! 1489:
! 1490: if (isc->sm1 <= isc->sm2) {
! 1491: /* service curve is convex */
! 1492: y1 = rtsc_x2y(rtsc, x);
! 1493: if (y1 < y)
! 1494: /* the current rtsc is smaller */
! 1495: return;
! 1496: rtsc->x = x;
! 1497: rtsc->y = y;
! 1498: return;
! 1499: }
! 1500:
! 1501: /*
! 1502: * service curve is concave
! 1503: * compute the two y values of the current rtsc
! 1504: * y1: at x
! 1505: * y2: at (x + dx)
! 1506: */
! 1507: y1 = rtsc_x2y(rtsc, x);
! 1508: if (y1 <= y) {
! 1509: /* rtsc is below isc, no change to rtsc */
! 1510: return;
! 1511: }
! 1512:
! 1513: y2 = rtsc_x2y(rtsc, x + isc->dx);
! 1514: if (y2 >= y + isc->dy) {
! 1515: /* rtsc is above isc, replace rtsc by isc */
! 1516: rtsc->x = x;
! 1517: rtsc->y = y;
! 1518: rtsc->dx = isc->dx;
! 1519: rtsc->dy = isc->dy;
! 1520: return;
! 1521: }
! 1522:
! 1523: /*
! 1524: * the two curves intersect
! 1525: * compute the offsets (dx, dy) using the reverse
! 1526: * function of seg_x2y()
! 1527: * seg_x2y(dx, sm1) == seg_x2y(dx, sm2) + (y1 - y)
! 1528: */
! 1529: dx = ((y1 - y) << SM_SHIFT) / (isc->sm1 - isc->sm2);
! 1530: /*
! 1531: * check if (x, y1) belongs to the 1st segment of rtsc.
! 1532: * if so, add the offset.
! 1533: */
! 1534: if (rtsc->x + rtsc->dx > x)
! 1535: dx += rtsc->x + rtsc->dx - x;
! 1536: dy = seg_x2y(dx, isc->sm1);
! 1537:
! 1538: rtsc->x = x;
! 1539: rtsc->y = y;
! 1540: rtsc->dx = dx;
! 1541: rtsc->dy = dy;
! 1542: return;
! 1543: }
! 1544:
! 1545: static void
! 1546: get_class_stats(struct hfsc_classstats *sp, struct hfsc_class *cl)
! 1547: {
! 1548: sp->class_id = cl->cl_id;
! 1549: sp->class_handle = cl->cl_handle;
! 1550:
! 1551: if (cl->cl_rsc != NULL) {
! 1552: sp->rsc.m1 = sm2m(cl->cl_rsc->sm1);
! 1553: sp->rsc.d = dx2d(cl->cl_rsc->dx);
! 1554: sp->rsc.m2 = sm2m(cl->cl_rsc->sm2);
! 1555: } else {
! 1556: sp->rsc.m1 = 0;
! 1557: sp->rsc.d = 0;
! 1558: sp->rsc.m2 = 0;
! 1559: }
! 1560: if (cl->cl_fsc != NULL) {
! 1561: sp->fsc.m1 = sm2m(cl->cl_fsc->sm1);
! 1562: sp->fsc.d = dx2d(cl->cl_fsc->dx);
! 1563: sp->fsc.m2 = sm2m(cl->cl_fsc->sm2);
! 1564: } else {
! 1565: sp->fsc.m1 = 0;
! 1566: sp->fsc.d = 0;
! 1567: sp->fsc.m2 = 0;
! 1568: }
! 1569: if (cl->cl_usc != NULL) {
! 1570: sp->usc.m1 = sm2m(cl->cl_usc->sm1);
! 1571: sp->usc.d = dx2d(cl->cl_usc->dx);
! 1572: sp->usc.m2 = sm2m(cl->cl_usc->sm2);
! 1573: } else {
! 1574: sp->usc.m1 = 0;
! 1575: sp->usc.d = 0;
! 1576: sp->usc.m2 = 0;
! 1577: }
! 1578:
! 1579: sp->total = cl->cl_total;
! 1580: sp->cumul = cl->cl_cumul;
! 1581:
! 1582: sp->d = cl->cl_d;
! 1583: sp->e = cl->cl_e;
! 1584: sp->vt = cl->cl_vt;
! 1585: sp->f = cl->cl_f;
! 1586:
! 1587: sp->initvt = cl->cl_initvt;
! 1588: sp->vtperiod = cl->cl_vtperiod;
! 1589: sp->parentperiod = cl->cl_parentperiod;
! 1590: sp->nactive = cl->cl_nactive;
! 1591: sp->vtoff = cl->cl_vtoff;
! 1592: sp->cvtmax = cl->cl_cvtmax;
! 1593: sp->myf = cl->cl_myf;
! 1594: sp->cfmin = cl->cl_cfmin;
! 1595: sp->cvtmin = cl->cl_cvtmin;
! 1596: sp->myfadj = cl->cl_myfadj;
! 1597: sp->vtadj = cl->cl_vtadj;
! 1598:
! 1599: sp->cur_time = read_machclk();
! 1600: sp->machclk_freq = machclk_freq;
! 1601:
! 1602: sp->qlength = qlen(cl->cl_q);
! 1603: sp->qlimit = qlimit(cl->cl_q);
! 1604: sp->xmit_cnt = cl->cl_stats.xmit_cnt;
! 1605: sp->drop_cnt = cl->cl_stats.drop_cnt;
! 1606: sp->period = cl->cl_stats.period;
! 1607:
! 1608: sp->qtype = qtype(cl->cl_q);
! 1609: #ifdef ALTQ_RED
! 1610: if (q_is_red(cl->cl_q))
! 1611: red_getstats(cl->cl_red, &sp->red[0]);
! 1612: #endif
! 1613: #ifdef ALTQ_RIO
! 1614: if (q_is_rio(cl->cl_q))
! 1615: rio_getstats((rio_t *)cl->cl_red, &sp->red[0]);
! 1616: #endif
! 1617: }
! 1618:
! 1619: /* convert a class handle to the corresponding class pointer */
! 1620: static struct hfsc_class *
! 1621: clh_to_clp(struct hfsc_if *hif, u_int32_t chandle)
! 1622: {
! 1623: int i;
! 1624: struct hfsc_class *cl;
! 1625:
! 1626: if (chandle == 0)
! 1627: return (NULL);
! 1628: /*
! 1629: * first, try the slot corresponding to the lower bits of the handle.
! 1630: * if it does not match, do the linear table search.
! 1631: */
! 1632: i = chandle % HFSC_MAX_CLASSES;
! 1633: if ((cl = hif->hif_class_tbl[i]) != NULL && cl->cl_handle == chandle)
! 1634: return (cl);
! 1635: for (i = 0; i < HFSC_MAX_CLASSES; i++)
! 1636: if ((cl = hif->hif_class_tbl[i]) != NULL &&
! 1637: cl->cl_handle == chandle)
! 1638: return (cl);
! 1639: return (NULL);
! 1640: }
CVSweb
![[BACK]](/icons/back.gif){kind=icon}
Return to altq_hfsc.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / sys / altq