1 /*- 2 * Copyright (c) 2005 Nuno Antunes <nuno.antunes@gmail.com> 3 * Copyright (c) 2007 Alexander Motin <mav@freebsd.org> 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 2. Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * 15 * THIS SOFTWARE IS PROVIDED BY AUTHOR AND CONTRIBUTORS ``AS IS'' AND 16 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 18 * ARE DISCLAIMED. IN NO EVENT SHALL AUTHOR OR CONTRIBUTORS BE LIABLE 19 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 20 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 21 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 22 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 23 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 24 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 25 * SUCH DAMAGE. 26 * 27 * $FreeBSD$ 28 */ 29 30 /* 31 * ng_car - An implementation of commited access rate for netgraph 32 * 33 * TODO: 34 * - Sanitize input config values (impose some limits) 35 * - Implement internal packet painting (possibly using mbuf tags) 36 * - Implement color-aware mode 37 * - Implement DSCP marking for IPv4 38 */ 39 40 #include <sys/param.h> 41 #include <sys/errno.h> 42 #include <sys/kernel.h> 43 #include <sys/malloc.h> 44 #include <sys/mbuf.h> 45 46 #include <netgraph/ng_message.h> 47 #include <netgraph/ng_parse.h> 48 #include <netgraph/netgraph.h> 49 #include <netgraph/ng_car.h> 50 51 #define NG_CAR_QUEUE_SIZE 100 /* Maximum queue size for SHAPE mode */ 52 #define NG_CAR_QUEUE_MIN_TH 8 /* Minimum RED threshhold for SHAPE mode */ 53 54 /* Hook private info */ 55 struct hookinfo { 56 hook_p hook; /* this (source) hook */ 57 hook_p dest; /* destination hook */ 58 59 int64_t tc; /* commited token bucket counter */ 60 int64_t te; /* exceeded/peak token bucket counter */ 61 struct bintime lastRefill; /* last token refill time */ 62 63 struct ng_car_hookconf conf; /* hook configuration */ 64 struct ng_car_hookstats stats; /* hook stats */ 65 66 struct mbuf *q[NG_CAR_QUEUE_SIZE]; /* circular packet queue */ 67 int q_first; /* first queue element */ 68 int q_last; /* last queue element */ 69 struct callout q_callout; /* periodic queue processing routine */ 70 struct mtx q_mtx; /* queue mutex */ 71 }; 72 73 /* Private information for each node instance */ 74 struct privdata { 75 node_p node; /* the node itself */ 76 struct hookinfo upper; /* hook to upper layers */ 77 struct hookinfo lower; /* hook to lower layers */ 78 }; 79 typedef struct privdata *priv_p; 80 81 static ng_constructor_t ng_car_constructor; 82 static ng_rcvmsg_t ng_car_rcvmsg; 83 static ng_shutdown_t ng_car_shutdown; 84 static ng_newhook_t ng_car_newhook; 85 static ng_rcvdata_t ng_car_rcvdata; 86 static ng_disconnect_t ng_car_disconnect; 87 88 static void ng_car_refillhook(struct hookinfo *h); 89 static void ng_car_schedule(struct hookinfo *h); 90 void ng_car_q_event(node_p node, hook_p hook, void *arg, int arg2); 91 static void ng_car_enqueue(struct hookinfo *h, item_p item); 92 93 /* Parse type for struct ng_car_hookstats */ 94 static const struct ng_parse_struct_field ng_car_hookstats_type_fields[] 95 = NG_CAR_HOOKSTATS; 96 static const struct ng_parse_type ng_car_hookstats_type = { 97 &ng_parse_struct_type, 98 &ng_car_hookstats_type_fields 99 }; 100 101 /* Parse type for struct ng_car_bulkstats */ 102 static const struct ng_parse_struct_field ng_car_bulkstats_type_fields[] 103 = NG_CAR_BULKSTATS(&ng_car_hookstats_type); 104 static const struct ng_parse_type ng_car_bulkstats_type = { 105 &ng_parse_struct_type, 106 &ng_car_bulkstats_type_fields 107 }; 108 109 /* Parse type for struct ng_car_hookconf */ 110 static const struct ng_parse_struct_field ng_car_hookconf_type_fields[] 111 = NG_CAR_HOOKCONF; 112 static const struct ng_parse_type ng_car_hookconf_type = { 113 &ng_parse_struct_type, 114 &ng_car_hookconf_type_fields 115 }; 116 117 /* Parse type for struct ng_car_bulkconf */ 118 static const struct ng_parse_struct_field ng_car_bulkconf_type_fields[] 119 = NG_CAR_BULKCONF(&ng_car_hookconf_type); 120 static const struct ng_parse_type ng_car_bulkconf_type = { 121 &ng_parse_struct_type, 122 &ng_car_bulkconf_type_fields 123 }; 124 125 /* Command list */ 126 static struct ng_cmdlist ng_car_cmdlist[] = { 127 { 128 NGM_CAR_COOKIE, 129 NGM_CAR_GET_STATS, 130 "getstats", 131 NULL, 132 &ng_car_bulkstats_type, 133 }, 134 { 135 NGM_CAR_COOKIE, 136 NGM_CAR_CLR_STATS, 137 "clrstats", 138 NULL, 139 NULL, 140 }, 141 { 142 NGM_CAR_COOKIE, 143 NGM_CAR_GETCLR_STATS, 144 "getclrstats", 145 NULL, 146 &ng_car_bulkstats_type, 147 }, 148 149 { 150 NGM_CAR_COOKIE, 151 NGM_CAR_GET_CONF, 152 "getconf", 153 NULL, 154 &ng_car_bulkconf_type, 155 }, 156 { 157 NGM_CAR_COOKIE, 158 NGM_CAR_SET_CONF, 159 "setconf", 160 &ng_car_bulkconf_type, 161 NULL, 162 }, 163 { 0 } 164 }; 165 166 /* Netgraph node type descriptor */ 167 static struct ng_type ng_car_typestruct = { 168 .version = NG_ABI_VERSION, 169 .name = NG_CAR_NODE_TYPE, 170 .constructor = ng_car_constructor, 171 .rcvmsg = ng_car_rcvmsg, 172 .shutdown = ng_car_shutdown, 173 .newhook = ng_car_newhook, 174 .rcvdata = ng_car_rcvdata, 175 .disconnect = ng_car_disconnect, 176 .cmdlist = ng_car_cmdlist, 177 }; 178 NETGRAPH_INIT(car, &ng_car_typestruct); 179 180 /* 181 * Node constructor 182 */ 183 static int 184 ng_car_constructor(node_p node) 185 { 186 priv_p priv; 187 188 /* Initialize private descriptor. */ 189 priv = malloc(sizeof(*priv), M_NETGRAPH, M_NOWAIT | M_ZERO); 190 if (priv == NULL) 191 return (ENOMEM); 192 193 NG_NODE_SET_PRIVATE(node, priv); 194 priv->node = node; 195 196 /* 197 * Arbitrary default values 198 */ 199 200 priv->upper.hook = NULL; 201 priv->upper.dest = NULL; 202 priv->upper.tc = priv->upper.conf.cbs = NG_CAR_CBS_MIN; 203 priv->upper.te = priv->upper.conf.ebs = NG_CAR_EBS_MIN; 204 priv->upper.conf.cir = NG_CAR_CIR_DFLT; 205 priv->upper.conf.green_action = NG_CAR_ACTION_FORWARD; 206 priv->upper.conf.yellow_action = NG_CAR_ACTION_FORWARD; 207 priv->upper.conf.red_action = NG_CAR_ACTION_DROP; 208 priv->upper.conf.mode = 0; 209 getbinuptime(&priv->upper.lastRefill); 210 priv->upper.q_first = 0; 211 priv->upper.q_last = 0; 212 ng_callout_init(&priv->upper.q_callout); 213 mtx_init(&priv->upper.q_mtx, "ng_car_u", NULL, MTX_DEF); 214 215 priv->lower.hook = NULL; 216 priv->lower.dest = NULL; 217 priv->lower.tc = priv->lower.conf.cbs = NG_CAR_CBS_MIN; 218 priv->lower.te = priv->lower.conf.ebs = NG_CAR_EBS_MIN; 219 priv->lower.conf.cir = NG_CAR_CIR_DFLT; 220 priv->lower.conf.green_action = NG_CAR_ACTION_FORWARD; 221 priv->lower.conf.yellow_action = NG_CAR_ACTION_FORWARD; 222 priv->lower.conf.red_action = NG_CAR_ACTION_DROP; 223 priv->lower.conf.mode = 0; 224 priv->lower.lastRefill = priv->upper.lastRefill; 225 priv->lower.q_first = 0; 226 priv->lower.q_last = 0; 227 ng_callout_init(&priv->lower.q_callout); 228 mtx_init(&priv->lower.q_mtx, "ng_car_l", NULL, MTX_DEF); 229 230 return (0); 231 } 232 233 /* 234 * Add a hook. 235 */ 236 static int 237 ng_car_newhook(node_p node, hook_p hook, const char *name) 238 { 239 const priv_p priv = NG_NODE_PRIVATE(node); 240 241 if (strcmp(name, NG_CAR_HOOK_LOWER) == 0) { 242 priv->lower.hook = hook; 243 priv->upper.dest = hook; 244 bzero(&priv->lower.stats, sizeof(priv->lower.stats)); 245 NG_HOOK_SET_PRIVATE(hook, &priv->lower); 246 } else if (strcmp(name, NG_CAR_HOOK_UPPER) == 0) { 247 priv->upper.hook = hook; 248 priv->lower.dest = hook; 249 bzero(&priv->upper.stats, sizeof(priv->upper.stats)); 250 NG_HOOK_SET_PRIVATE(hook, &priv->upper); 251 } else 252 return (EINVAL); 253 return(0); 254 } 255 256 /* 257 * Data has arrived. 258 */ 259 static int 260 ng_car_rcvdata(hook_p hook, item_p item ) 261 { 262 struct hookinfo *const hinfo = NG_HOOK_PRIVATE(hook); 263 hook_p dest = hinfo->dest; 264 struct mbuf *m = NULL; 265 int error = 0; 266 int len; 267 268 /* Node is useless without destination hook. */ 269 if (dest == NULL) { 270 NG_FREE_ITEM(item); 271 ++hinfo->stats.errors; 272 return(EINVAL); 273 } 274 275 /* If queue is not empty now then enqueue packet. */ 276 if (hinfo->q_first != hinfo->q_last) { 277 ng_car_enqueue(hinfo, item); 278 return (0); 279 } 280 281 m = NGI_M(item); 282 283 #define NG_CAR_PERFORM_MATCH_ACTION(a) \ 284 do { \ 285 switch (a) { \ 286 case NG_CAR_ACTION_FORWARD: \ 287 /* Do nothing. */ \ 288 break; \ 289 case NG_CAR_ACTION_MARK: \ 290 /* XXX find a way to mark packets (mbuf tag?) */ \ 291 ++hinfo->stats.errors; \ 292 break; \ 293 case NG_CAR_ACTION_DROP: \ 294 default: \ 295 /* Drop packet and return. */ \ 296 NG_FREE_ITEM(item); \ 297 ++hinfo->stats.droped_pkts; \ 298 return (0); \ 299 } \ 300 } while (0) 301 302 /* Packet is counted as 128 tokens for better resolution */ 303 if (hinfo->conf.opt & NG_CAR_COUNT_PACKETS) { 304 len = 128; 305 } else { 306 len = m->m_pkthdr.len; 307 } 308 309 /* Check commited token bucket. */ 310 if (hinfo->tc - len >= 0) { 311 /* This packet is green. */ 312 ++hinfo->stats.green_pkts; 313 hinfo->tc -= len; 314 NG_CAR_PERFORM_MATCH_ACTION(hinfo->conf.green_action); 315 } else { 316 317 /* Refill only if not green without it. */ 318 ng_car_refillhook(hinfo); 319 320 /* Check commited token bucket again after refill. */ 321 if (hinfo->tc - len >= 0) { 322 /* This packet is green */ 323 ++hinfo->stats.green_pkts; 324 hinfo->tc -= len; 325 NG_CAR_PERFORM_MATCH_ACTION(hinfo->conf.green_action); 326 327 /* If not green and mode is SHAPE, enqueue packet. */ 328 } else if (hinfo->conf.mode == NG_CAR_SHAPE) { 329 ng_car_enqueue(hinfo, item); 330 return (0); 331 332 /* If not green and mode is RED, calculate probability. */ 333 } else if (hinfo->conf.mode == NG_CAR_RED) { 334 /* Is packet is bigger then extended burst? */ 335 if (len - (hinfo->tc - len) > hinfo->conf.ebs) { 336 /* This packet is definitely red. */ 337 ++hinfo->stats.red_pkts; 338 hinfo->te = 0; 339 NG_CAR_PERFORM_MATCH_ACTION(hinfo->conf.red_action); 340 341 /* Use token bucket to simulate RED-like drop 342 probability. */ 343 } else if (hinfo->te + (len - hinfo->tc) < 344 hinfo->conf.ebs) { 345 /* This packet is yellow */ 346 ++hinfo->stats.yellow_pkts; 347 hinfo->te += len - hinfo->tc; 348 /* Go to negative tokens. */ 349 hinfo->tc -= len; 350 NG_CAR_PERFORM_MATCH_ACTION(hinfo->conf.yellow_action); 351 } else { 352 /* This packet is probaly red. */ 353 ++hinfo->stats.red_pkts; 354 hinfo->te = 0; 355 NG_CAR_PERFORM_MATCH_ACTION(hinfo->conf.red_action); 356 } 357 /* If not green and mode is SINGLE/DOUBLE RATE. */ 358 } else { 359 /* Check extended token bucket. */ 360 if (hinfo->te - len >= 0) { 361 /* This packet is yellow */ 362 ++hinfo->stats.yellow_pkts; 363 hinfo->te -= len; 364 NG_CAR_PERFORM_MATCH_ACTION(hinfo->conf.yellow_action); 365 } else { 366 /* This packet is red */ 367 ++hinfo->stats.red_pkts; 368 NG_CAR_PERFORM_MATCH_ACTION(hinfo->conf.red_action); 369 } 370 } 371 } 372 373 #undef NG_CAR_PERFORM_MATCH_ACTION 374 375 NG_FWD_ITEM_HOOK(error, item, dest); 376 if (error != 0) 377 ++hinfo->stats.errors; 378 ++hinfo->stats.passed_pkts; 379 380 return (error); 381 } 382 383 /* 384 * Receive a control message. 385 */ 386 static int 387 ng_car_rcvmsg(node_p node, item_p item, hook_p lasthook) 388 { 389 const priv_p priv = NG_NODE_PRIVATE(node); 390 struct ng_mesg *resp = NULL; 391 int error = 0; 392 struct ng_mesg *msg; 393 394 NGI_GET_MSG(item, msg); 395 switch (msg->header.typecookie) { 396 case NGM_CAR_COOKIE: 397 switch (msg->header.cmd) { 398 case NGM_CAR_GET_STATS: 399 case NGM_CAR_GETCLR_STATS: 400 { 401 struct ng_car_bulkstats *bstats; 402 403 NG_MKRESPONSE(resp, msg, 404 sizeof(*bstats), M_NOWAIT); 405 if (resp == NULL) { 406 error = ENOMEM; 407 break; 408 } 409 bstats = (struct ng_car_bulkstats *)resp->data; 410 411 bcopy(&priv->upper.stats, &bstats->downstream, 412 sizeof(bstats->downstream)); 413 bcopy(&priv->lower.stats, &bstats->upstream, 414 sizeof(bstats->upstream)); 415 } 416 if (msg->header.cmd == NGM_CAR_GET_STATS) 417 break; 418 case NGM_CAR_CLR_STATS: 419 bzero(&priv->upper.stats, 420 sizeof(priv->upper.stats)); 421 bzero(&priv->lower.stats, 422 sizeof(priv->lower.stats)); 423 break; 424 case NGM_CAR_GET_CONF: 425 { 426 struct ng_car_bulkconf *bconf; 427 428 NG_MKRESPONSE(resp, msg, 429 sizeof(*bconf), M_NOWAIT); 430 if (resp == NULL) { 431 error = ENOMEM; 432 break; 433 } 434 bconf = (struct ng_car_bulkconf *)resp->data; 435 436 bcopy(&priv->upper.conf, &bconf->downstream, 437 sizeof(bconf->downstream)); 438 bcopy(&priv->lower.conf, &bconf->upstream, 439 sizeof(bconf->upstream)); 440 /* Convert internal 1/(8*128) of pps into pps */ 441 if (bconf->downstream.opt & NG_CAR_COUNT_PACKETS) { 442 bconf->downstream.cir /= 1024; 443 bconf->downstream.pir /= 1024; 444 bconf->downstream.cbs /= 128; 445 bconf->downstream.ebs /= 128; 446 } 447 if (bconf->upstream.opt & NG_CAR_COUNT_PACKETS) { 448 bconf->upstream.cir /= 1024; 449 bconf->upstream.pir /= 1024; 450 bconf->upstream.cbs /= 128; 451 bconf->upstream.ebs /= 128; 452 } 453 } 454 break; 455 case NGM_CAR_SET_CONF: 456 { 457 struct ng_car_bulkconf *const bconf = 458 (struct ng_car_bulkconf *)msg->data; 459 460 /* Check for invalid or illegal config. */ 461 if (msg->header.arglen != sizeof(*bconf)) { 462 error = EINVAL; 463 break; 464 } 465 /* Convert pps into internal 1/(8*128) of pps */ 466 if (bconf->downstream.opt & NG_CAR_COUNT_PACKETS) { 467 bconf->downstream.cir *= 1024; 468 bconf->downstream.pir *= 1024; 469 bconf->downstream.cbs *= 125; 470 bconf->downstream.ebs *= 125; 471 } 472 if (bconf->upstream.opt & NG_CAR_COUNT_PACKETS) { 473 bconf->upstream.cir *= 1024; 474 bconf->upstream.pir *= 1024; 475 bconf->upstream.cbs *= 125; 476 bconf->upstream.ebs *= 125; 477 } 478 if ((bconf->downstream.cir > 1000000000) || 479 (bconf->downstream.pir > 1000000000) || 480 (bconf->upstream.cir > 1000000000) || 481 (bconf->upstream.pir > 1000000000) || 482 (bconf->downstream.cbs == 0 && 483 bconf->downstream.ebs == 0) || 484 (bconf->upstream.cbs == 0 && 485 bconf->upstream.ebs == 0)) 486 { 487 error = EINVAL; 488 break; 489 } 490 if ((bconf->upstream.mode == NG_CAR_SHAPE) && 491 (bconf->upstream.cir == 0)) { 492 error = EINVAL; 493 break; 494 } 495 if ((bconf->downstream.mode == NG_CAR_SHAPE) && 496 (bconf->downstream.cir == 0)) { 497 error = EINVAL; 498 break; 499 } 500 501 /* Copy downstream config. */ 502 bcopy(&bconf->downstream, &priv->upper.conf, 503 sizeof(priv->upper.conf)); 504 priv->upper.tc = priv->upper.conf.cbs; 505 if (priv->upper.conf.mode == NG_CAR_RED || 506 priv->upper.conf.mode == NG_CAR_SHAPE) { 507 priv->upper.te = 0; 508 } else { 509 priv->upper.te = priv->upper.conf.ebs; 510 } 511 512 /* Copy upstream config. */ 513 bcopy(&bconf->upstream, &priv->lower.conf, 514 sizeof(priv->lower.conf)); 515 priv->lower.tc = priv->lower.conf.cbs; 516 if (priv->lower.conf.mode == NG_CAR_RED || 517 priv->lower.conf.mode == NG_CAR_SHAPE) { 518 priv->lower.te = 0; 519 } else { 520 priv->lower.te = priv->lower.conf.ebs; 521 } 522 } 523 break; 524 default: 525 error = EINVAL; 526 break; 527 } 528 break; 529 default: 530 error = EINVAL; 531 break; 532 } 533 NG_RESPOND_MSG(error, node, item, resp); 534 NG_FREE_MSG(msg); 535 return (error); 536 } 537 538 /* 539 * Do local shutdown processing. 540 */ 541 static int 542 ng_car_shutdown(node_p node) 543 { 544 const priv_p priv = NG_NODE_PRIVATE(node); 545 546 ng_uncallout(&priv->upper.q_callout, node); 547 ng_uncallout(&priv->lower.q_callout, node); 548 mtx_destroy(&priv->upper.q_mtx); 549 mtx_destroy(&priv->lower.q_mtx); 550 NG_NODE_UNREF(priv->node); 551 free(priv, M_NETGRAPH); 552 return (0); 553 } 554 555 /* 556 * Hook disconnection. 557 * 558 * For this type, removal of the last link destroys the node. 559 */ 560 static int 561 ng_car_disconnect(hook_p hook) 562 { 563 struct hookinfo *const hinfo = NG_HOOK_PRIVATE(hook); 564 const node_p node = NG_HOOK_NODE(hook); 565 const priv_p priv = NG_NODE_PRIVATE(node); 566 567 if (hinfo) { 568 /* Purge queue if not empty. */ 569 while (hinfo->q_first != hinfo->q_last) { 570 NG_FREE_M(hinfo->q[hinfo->q_first]); 571 hinfo->q_first++; 572 if (hinfo->q_first >= NG_CAR_QUEUE_SIZE) 573 hinfo->q_first = 0; 574 } 575 /* Remove hook refs. */ 576 if (hinfo->hook == priv->upper.hook) 577 priv->lower.dest = NULL; 578 else 579 priv->upper.dest = NULL; 580 hinfo->hook = NULL; 581 } 582 /* Already shutting down? */ 583 if ((NG_NODE_NUMHOOKS(NG_HOOK_NODE(hook)) == 0) 584 && (NG_NODE_IS_VALID(NG_HOOK_NODE(hook)))) 585 ng_rmnode_self(NG_HOOK_NODE(hook)); 586 return (0); 587 } 588 589 /* 590 * Hook's token buckets refillment. 591 */ 592 static void 593 ng_car_refillhook(struct hookinfo *h) 594 { 595 struct bintime newt, deltat; 596 unsigned int deltat_us; 597 598 /* Get current time. */ 599 getbinuptime(&newt); 600 601 /* Get time delta since last refill. */ 602 deltat = newt; 603 bintime_sub(&deltat, &h->lastRefill); 604 605 /* Time must go forward. */ 606 if (deltat.sec < 0) { 607 h->lastRefill = newt; 608 return; 609 } 610 611 /* But not too far forward. */ 612 if (deltat.sec >= 1000) { 613 deltat_us = (1000 << 20); 614 } else { 615 /* convert bintime to the 1/(2^20) of sec */ 616 deltat_us = (deltat.sec << 20) + (deltat.frac >> 44); 617 } 618 619 if (h->conf.mode == NG_CAR_SINGLE_RATE) { 620 int64_t delta; 621 /* Refill commited token bucket. */ 622 h->tc += (h->conf.cir * deltat_us) >> 23; 623 delta = h->tc - h->conf.cbs; 624 if (delta > 0) { 625 h->tc = h->conf.cbs; 626 627 /* Refill exceeded token bucket. */ 628 h->te += delta; 629 if (h->te > ((int64_t)h->conf.ebs)) 630 h->te = h->conf.ebs; 631 } 632 633 } else if (h->conf.mode == NG_CAR_DOUBLE_RATE) { 634 /* Refill commited token bucket. */ 635 h->tc += (h->conf.cir * deltat_us) >> 23; 636 if (h->tc > ((int64_t)h->conf.cbs)) 637 h->tc = h->conf.cbs; 638 639 /* Refill peak token bucket. */ 640 h->te += (h->conf.pir * deltat_us) >> 23; 641 if (h->te > ((int64_t)h->conf.ebs)) 642 h->te = h->conf.ebs; 643 644 } else { /* RED or SHAPE mode. */ 645 /* Refill commited token bucket. */ 646 h->tc += (h->conf.cir * deltat_us) >> 23; 647 if (h->tc > ((int64_t)h->conf.cbs)) 648 h->tc = h->conf.cbs; 649 } 650 651 /* Remember this moment. */ 652 h->lastRefill = newt; 653 } 654 655 /* 656 * Schedule callout when we will have required tokens. 657 */ 658 static void 659 ng_car_schedule(struct hookinfo *hinfo) 660 { 661 int delay; 662 663 delay = (-(hinfo->tc)) * hz * 8 / hinfo->conf.cir + 1; 664 665 ng_callout(&hinfo->q_callout, NG_HOOK_NODE(hinfo->hook), hinfo->hook, 666 delay, &ng_car_q_event, NULL, 0); 667 } 668 669 /* 670 * Queue processing callout handler. 671 */ 672 void 673 ng_car_q_event(node_p node, hook_p hook, void *arg, int arg2) 674 { 675 struct hookinfo *hinfo = NG_HOOK_PRIVATE(hook); 676 item_p item; 677 struct mbuf *m; 678 int error; 679 680 /* Refill tokens for time we have slept. */ 681 ng_car_refillhook(hinfo); 682 683 if (hinfo->dest != NULL) { 684 /* If we have some tokens */ 685 while (hinfo->tc >= 0) { 686 687 /* Send packet. */ 688 m = hinfo->q[hinfo->q_first]; 689 if ((item = ng_package_data(m, NG_NOFLAGS)) != NULL) 690 NG_FWD_ITEM_HOOK(error, item, hinfo->dest); 691 692 /* Get next one. */ 693 hinfo->q_first++; 694 if (hinfo->q_first >= NG_CAR_QUEUE_SIZE) 695 hinfo->q_first = 0; 696 697 /* Stop if none left. */ 698 if (hinfo->q_first == hinfo->q_last) 699 break; 700 701 /* If we have more packet, try it. */ 702 m = hinfo->q[hinfo->q_first]; 703 if (hinfo->conf.opt & NG_CAR_COUNT_PACKETS) { 704 hinfo->tc -= 128; 705 } else { 706 hinfo->tc -= m->m_pkthdr.len; 707 } 708 } 709 } 710 711 /* If something left */ 712 if (hinfo->q_first != hinfo->q_last) 713 /* Schedule queue processing. */ 714 ng_car_schedule(hinfo); 715 } 716 717 /* 718 * Enqueue packet. 719 */ 720 static void 721 ng_car_enqueue(struct hookinfo *hinfo, item_p item) 722 { 723 struct mbuf *m; 724 int len; 725 726 NGI_GET_M(item, m); 727 NG_FREE_ITEM(item); 728 729 /* Lock queue mutex. */ 730 mtx_lock(&hinfo->q_mtx); 731 732 /* Calculate used queue length. */ 733 len = hinfo->q_last - hinfo->q_first; 734 if (len < 0) 735 len += NG_CAR_QUEUE_SIZE; 736 737 /* If queue is overflowed or we have no RED tokens. */ 738 if ((len >= (NG_CAR_QUEUE_SIZE - 1)) || 739 (hinfo->te + len >= NG_CAR_QUEUE_SIZE)) { 740 /* Drop packet. */ 741 ++hinfo->stats.red_pkts; 742 NG_FREE_M(m); 743 744 hinfo->te = 0; 745 } else { 746 /* This packet is yellow. */ 747 ++hinfo->stats.yellow_pkts; 748 749 /* Enqueue packet. */ 750 hinfo->q[hinfo->q_last] = m; 751 hinfo->q_last++; 752 if (hinfo->q_last >= NG_CAR_QUEUE_SIZE) 753 hinfo->q_last = 0; 754 755 /* Use RED tokens. */ 756 if (len > NG_CAR_QUEUE_MIN_TH) 757 hinfo->te += len - NG_CAR_QUEUE_MIN_TH; 758 759 /* If this is a first packet in the queue. */ 760 if (len == 0) { 761 if (hinfo->conf.opt & NG_CAR_COUNT_PACKETS) { 762 hinfo->tc -= 128; 763 } else { 764 hinfo->tc -= m->m_pkthdr.len; 765 } 766 767 /* Schedule queue processing. */ 768 ng_car_schedule(hinfo); 769 } 770 } 771 772 /* Unlock queue mutex. */ 773 mtx_unlock(&hinfo->q_mtx); 774 } 775