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 committed 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 threshold 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; /* committed 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 u_int q_first; /* first queue element */ 68 u_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_WAITOK | M_ZERO); 190 191 NG_NODE_SET_PRIVATE(node, priv); 192 priv->node = node; 193 194 /* 195 * Arbitrary default values 196 */ 197 198 priv->upper.hook = NULL; 199 priv->upper.dest = NULL; 200 priv->upper.tc = priv->upper.conf.cbs = NG_CAR_CBS_MIN; 201 priv->upper.te = priv->upper.conf.ebs = NG_CAR_EBS_MIN; 202 priv->upper.conf.cir = NG_CAR_CIR_DFLT; 203 priv->upper.conf.green_action = NG_CAR_ACTION_FORWARD; 204 priv->upper.conf.yellow_action = NG_CAR_ACTION_FORWARD; 205 priv->upper.conf.red_action = NG_CAR_ACTION_DROP; 206 priv->upper.conf.mode = 0; 207 getbinuptime(&priv->upper.lastRefill); 208 priv->upper.q_first = 0; 209 priv->upper.q_last = 0; 210 ng_callout_init(&priv->upper.q_callout); 211 mtx_init(&priv->upper.q_mtx, "ng_car_u", NULL, MTX_DEF); 212 213 priv->lower.hook = NULL; 214 priv->lower.dest = NULL; 215 priv->lower.tc = priv->lower.conf.cbs = NG_CAR_CBS_MIN; 216 priv->lower.te = priv->lower.conf.ebs = NG_CAR_EBS_MIN; 217 priv->lower.conf.cir = NG_CAR_CIR_DFLT; 218 priv->lower.conf.green_action = NG_CAR_ACTION_FORWARD; 219 priv->lower.conf.yellow_action = NG_CAR_ACTION_FORWARD; 220 priv->lower.conf.red_action = NG_CAR_ACTION_DROP; 221 priv->lower.conf.mode = 0; 222 priv->lower.lastRefill = priv->upper.lastRefill; 223 priv->lower.q_first = 0; 224 priv->lower.q_last = 0; 225 ng_callout_init(&priv->lower.q_callout); 226 mtx_init(&priv->lower.q_mtx, "ng_car_l", NULL, MTX_DEF); 227 228 return (0); 229 } 230 231 /* 232 * Add a hook. 233 */ 234 static int 235 ng_car_newhook(node_p node, hook_p hook, const char *name) 236 { 237 const priv_p priv = NG_NODE_PRIVATE(node); 238 239 if (strcmp(name, NG_CAR_HOOK_LOWER) == 0) { 240 priv->lower.hook = hook; 241 priv->upper.dest = hook; 242 bzero(&priv->lower.stats, sizeof(priv->lower.stats)); 243 NG_HOOK_SET_PRIVATE(hook, &priv->lower); 244 } else if (strcmp(name, NG_CAR_HOOK_UPPER) == 0) { 245 priv->upper.hook = hook; 246 priv->lower.dest = hook; 247 bzero(&priv->upper.stats, sizeof(priv->upper.stats)); 248 NG_HOOK_SET_PRIVATE(hook, &priv->upper); 249 } else 250 return (EINVAL); 251 return(0); 252 } 253 254 /* 255 * Data has arrived. 256 */ 257 static int 258 ng_car_rcvdata(hook_p hook, item_p item ) 259 { 260 struct hookinfo *const hinfo = NG_HOOK_PRIVATE(hook); 261 struct mbuf *m; 262 int error = 0; 263 u_int len; 264 265 /* If queue is not empty now then enqueue packet. */ 266 if (hinfo->q_first != hinfo->q_last) { 267 ng_car_enqueue(hinfo, item); 268 return (0); 269 } 270 271 m = NGI_M(item); 272 273 #define NG_CAR_PERFORM_MATCH_ACTION(a) \ 274 do { \ 275 switch (a) { \ 276 case NG_CAR_ACTION_FORWARD: \ 277 /* Do nothing. */ \ 278 break; \ 279 case NG_CAR_ACTION_MARK: \ 280 /* XXX find a way to mark packets (mbuf tag?) */ \ 281 ++hinfo->stats.errors; \ 282 break; \ 283 case NG_CAR_ACTION_DROP: \ 284 default: \ 285 /* Drop packet and return. */ \ 286 NG_FREE_ITEM(item); \ 287 ++hinfo->stats.droped_pkts; \ 288 return (0); \ 289 } \ 290 } while (0) 291 292 /* Packet is counted as 128 tokens for better resolution */ 293 if (hinfo->conf.opt & NG_CAR_COUNT_PACKETS) { 294 len = 128; 295 } else { 296 len = m->m_pkthdr.len; 297 } 298 299 /* Check committed token bucket. */ 300 if (hinfo->tc - len >= 0) { 301 /* This packet is green. */ 302 ++hinfo->stats.green_pkts; 303 hinfo->tc -= len; 304 NG_CAR_PERFORM_MATCH_ACTION(hinfo->conf.green_action); 305 } else { 306 307 /* Refill only if not green without it. */ 308 ng_car_refillhook(hinfo); 309 310 /* Check committed token bucket again after refill. */ 311 if (hinfo->tc - len >= 0) { 312 /* This packet is green */ 313 ++hinfo->stats.green_pkts; 314 hinfo->tc -= len; 315 NG_CAR_PERFORM_MATCH_ACTION(hinfo->conf.green_action); 316 317 /* If not green and mode is SHAPE, enqueue packet. */ 318 } else if (hinfo->conf.mode == NG_CAR_SHAPE) { 319 ng_car_enqueue(hinfo, item); 320 return (0); 321 322 /* If not green and mode is RED, calculate probability. */ 323 } else if (hinfo->conf.mode == NG_CAR_RED) { 324 /* Is packet is bigger then extended burst? */ 325 if (len - (hinfo->tc - len) > hinfo->conf.ebs) { 326 /* This packet is definitely red. */ 327 ++hinfo->stats.red_pkts; 328 hinfo->te = 0; 329 NG_CAR_PERFORM_MATCH_ACTION(hinfo->conf.red_action); 330 331 /* Use token bucket to simulate RED-like drop 332 probability. */ 333 } else if (hinfo->te + (len - hinfo->tc) < 334 hinfo->conf.ebs) { 335 /* This packet is yellow */ 336 ++hinfo->stats.yellow_pkts; 337 hinfo->te += len - hinfo->tc; 338 /* Go to negative tokens. */ 339 hinfo->tc -= len; 340 NG_CAR_PERFORM_MATCH_ACTION(hinfo->conf.yellow_action); 341 } else { 342 /* This packet is probably red. */ 343 ++hinfo->stats.red_pkts; 344 hinfo->te = 0; 345 NG_CAR_PERFORM_MATCH_ACTION(hinfo->conf.red_action); 346 } 347 /* If not green and mode is SINGLE/DOUBLE RATE. */ 348 } else { 349 /* Check extended token bucket. */ 350 if (hinfo->te - len >= 0) { 351 /* This packet is yellow */ 352 ++hinfo->stats.yellow_pkts; 353 hinfo->te -= len; 354 NG_CAR_PERFORM_MATCH_ACTION(hinfo->conf.yellow_action); 355 } else { 356 /* This packet is red */ 357 ++hinfo->stats.red_pkts; 358 NG_CAR_PERFORM_MATCH_ACTION(hinfo->conf.red_action); 359 } 360 } 361 } 362 363 #undef NG_CAR_PERFORM_MATCH_ACTION 364 365 NG_FWD_ITEM_HOOK(error, item, hinfo->dest); 366 if (error != 0) 367 ++hinfo->stats.errors; 368 ++hinfo->stats.passed_pkts; 369 370 return (error); 371 } 372 373 /* 374 * Receive a control message. 375 */ 376 static int 377 ng_car_rcvmsg(node_p node, item_p item, hook_p lasthook) 378 { 379 const priv_p priv = NG_NODE_PRIVATE(node); 380 struct ng_mesg *resp = NULL; 381 int error = 0; 382 struct ng_mesg *msg; 383 384 NGI_GET_MSG(item, msg); 385 switch (msg->header.typecookie) { 386 case NGM_CAR_COOKIE: 387 switch (msg->header.cmd) { 388 case NGM_CAR_GET_STATS: 389 case NGM_CAR_GETCLR_STATS: 390 { 391 struct ng_car_bulkstats *bstats; 392 393 NG_MKRESPONSE(resp, msg, 394 sizeof(*bstats), M_NOWAIT); 395 if (resp == NULL) { 396 error = ENOMEM; 397 break; 398 } 399 bstats = (struct ng_car_bulkstats *)resp->data; 400 401 bcopy(&priv->upper.stats, &bstats->downstream, 402 sizeof(bstats->downstream)); 403 bcopy(&priv->lower.stats, &bstats->upstream, 404 sizeof(bstats->upstream)); 405 } 406 if (msg->header.cmd == NGM_CAR_GET_STATS) 407 break; 408 case NGM_CAR_CLR_STATS: 409 bzero(&priv->upper.stats, 410 sizeof(priv->upper.stats)); 411 bzero(&priv->lower.stats, 412 sizeof(priv->lower.stats)); 413 break; 414 case NGM_CAR_GET_CONF: 415 { 416 struct ng_car_bulkconf *bconf; 417 418 NG_MKRESPONSE(resp, msg, 419 sizeof(*bconf), M_NOWAIT); 420 if (resp == NULL) { 421 error = ENOMEM; 422 break; 423 } 424 bconf = (struct ng_car_bulkconf *)resp->data; 425 426 bcopy(&priv->upper.conf, &bconf->downstream, 427 sizeof(bconf->downstream)); 428 bcopy(&priv->lower.conf, &bconf->upstream, 429 sizeof(bconf->upstream)); 430 /* Convert internal 1/(8*128) of pps into pps */ 431 if (bconf->downstream.opt & NG_CAR_COUNT_PACKETS) { 432 bconf->downstream.cir /= 1024; 433 bconf->downstream.pir /= 1024; 434 bconf->downstream.cbs /= 128; 435 bconf->downstream.ebs /= 128; 436 } 437 if (bconf->upstream.opt & NG_CAR_COUNT_PACKETS) { 438 bconf->upstream.cir /= 1024; 439 bconf->upstream.pir /= 1024; 440 bconf->upstream.cbs /= 128; 441 bconf->upstream.ebs /= 128; 442 } 443 } 444 break; 445 case NGM_CAR_SET_CONF: 446 { 447 struct ng_car_bulkconf *const bconf = 448 (struct ng_car_bulkconf *)msg->data; 449 450 /* Check for invalid or illegal config. */ 451 if (msg->header.arglen != sizeof(*bconf)) { 452 error = EINVAL; 453 break; 454 } 455 /* Convert pps into internal 1/(8*128) of pps */ 456 if (bconf->downstream.opt & NG_CAR_COUNT_PACKETS) { 457 bconf->downstream.cir *= 1024; 458 bconf->downstream.pir *= 1024; 459 bconf->downstream.cbs *= 125; 460 bconf->downstream.ebs *= 125; 461 } 462 if (bconf->upstream.opt & NG_CAR_COUNT_PACKETS) { 463 bconf->upstream.cir *= 1024; 464 bconf->upstream.pir *= 1024; 465 bconf->upstream.cbs *= 125; 466 bconf->upstream.ebs *= 125; 467 } 468 if ((bconf->downstream.cir > 1000000000) || 469 (bconf->downstream.pir > 1000000000) || 470 (bconf->upstream.cir > 1000000000) || 471 (bconf->upstream.pir > 1000000000) || 472 (bconf->downstream.cbs == 0 && 473 bconf->downstream.ebs == 0) || 474 (bconf->upstream.cbs == 0 && 475 bconf->upstream.ebs == 0)) 476 { 477 error = EINVAL; 478 break; 479 } 480 if ((bconf->upstream.mode == NG_CAR_SHAPE) && 481 (bconf->upstream.cir == 0)) { 482 error = EINVAL; 483 break; 484 } 485 if ((bconf->downstream.mode == NG_CAR_SHAPE) && 486 (bconf->downstream.cir == 0)) { 487 error = EINVAL; 488 break; 489 } 490 491 /* Copy downstream config. */ 492 bcopy(&bconf->downstream, &priv->upper.conf, 493 sizeof(priv->upper.conf)); 494 priv->upper.tc = priv->upper.conf.cbs; 495 if (priv->upper.conf.mode == NG_CAR_RED || 496 priv->upper.conf.mode == NG_CAR_SHAPE) { 497 priv->upper.te = 0; 498 } else { 499 priv->upper.te = priv->upper.conf.ebs; 500 } 501 502 /* Copy upstream config. */ 503 bcopy(&bconf->upstream, &priv->lower.conf, 504 sizeof(priv->lower.conf)); 505 priv->lower.tc = priv->lower.conf.cbs; 506 if (priv->lower.conf.mode == NG_CAR_RED || 507 priv->lower.conf.mode == NG_CAR_SHAPE) { 508 priv->lower.te = 0; 509 } else { 510 priv->lower.te = priv->lower.conf.ebs; 511 } 512 } 513 break; 514 default: 515 error = EINVAL; 516 break; 517 } 518 break; 519 default: 520 error = EINVAL; 521 break; 522 } 523 NG_RESPOND_MSG(error, node, item, resp); 524 NG_FREE_MSG(msg); 525 return (error); 526 } 527 528 /* 529 * Do local shutdown processing. 530 */ 531 static int 532 ng_car_shutdown(node_p node) 533 { 534 const priv_p priv = NG_NODE_PRIVATE(node); 535 536 ng_uncallout(&priv->upper.q_callout, node); 537 ng_uncallout(&priv->lower.q_callout, node); 538 mtx_destroy(&priv->upper.q_mtx); 539 mtx_destroy(&priv->lower.q_mtx); 540 NG_NODE_UNREF(priv->node); 541 free(priv, M_NETGRAPH); 542 return (0); 543 } 544 545 /* 546 * Hook disconnection. 547 * 548 * For this type, removal of the last link destroys the node. 549 */ 550 static int 551 ng_car_disconnect(hook_p hook) 552 { 553 struct hookinfo *const hinfo = NG_HOOK_PRIVATE(hook); 554 const node_p node = NG_HOOK_NODE(hook); 555 const priv_p priv = NG_NODE_PRIVATE(node); 556 557 if (hinfo) { 558 /* Purge queue if not empty. */ 559 while (hinfo->q_first != hinfo->q_last) { 560 NG_FREE_M(hinfo->q[hinfo->q_first]); 561 hinfo->q_first++; 562 if (hinfo->q_first >= NG_CAR_QUEUE_SIZE) 563 hinfo->q_first = 0; 564 } 565 /* Remove hook refs. */ 566 if (hinfo->hook == priv->upper.hook) 567 priv->lower.dest = NULL; 568 else 569 priv->upper.dest = NULL; 570 hinfo->hook = NULL; 571 } 572 /* Already shutting down? */ 573 if ((NG_NODE_NUMHOOKS(NG_HOOK_NODE(hook)) == 0) 574 && (NG_NODE_IS_VALID(NG_HOOK_NODE(hook)))) 575 ng_rmnode_self(NG_HOOK_NODE(hook)); 576 return (0); 577 } 578 579 /* 580 * Hook's token buckets refillment. 581 */ 582 static void 583 ng_car_refillhook(struct hookinfo *h) 584 { 585 struct bintime newt, deltat; 586 unsigned int deltat_us; 587 588 /* Get current time. */ 589 getbinuptime(&newt); 590 591 /* Get time delta since last refill. */ 592 deltat = newt; 593 bintime_sub(&deltat, &h->lastRefill); 594 595 /* Time must go forward. */ 596 if (deltat.sec < 0) { 597 h->lastRefill = newt; 598 return; 599 } 600 601 /* But not too far forward. */ 602 if (deltat.sec >= 1000) { 603 deltat_us = (1000 << 20); 604 } else { 605 /* convert bintime to the 1/(2^20) of sec */ 606 deltat_us = (deltat.sec << 20) + (deltat.frac >> 44); 607 } 608 609 if (h->conf.mode == NG_CAR_SINGLE_RATE) { 610 int64_t delta; 611 /* Refill committed token bucket. */ 612 h->tc += (h->conf.cir * deltat_us) >> 23; 613 delta = h->tc - h->conf.cbs; 614 if (delta > 0) { 615 h->tc = h->conf.cbs; 616 617 /* Refill exceeded token bucket. */ 618 h->te += delta; 619 if (h->te > ((int64_t)h->conf.ebs)) 620 h->te = h->conf.ebs; 621 } 622 623 } else if (h->conf.mode == NG_CAR_DOUBLE_RATE) { 624 /* Refill committed token bucket. */ 625 h->tc += (h->conf.cir * deltat_us) >> 23; 626 if (h->tc > ((int64_t)h->conf.cbs)) 627 h->tc = h->conf.cbs; 628 629 /* Refill peak token bucket. */ 630 h->te += (h->conf.pir * deltat_us) >> 23; 631 if (h->te > ((int64_t)h->conf.ebs)) 632 h->te = h->conf.ebs; 633 634 } else { /* RED or SHAPE mode. */ 635 /* Refill committed token bucket. */ 636 h->tc += (h->conf.cir * deltat_us) >> 23; 637 if (h->tc > ((int64_t)h->conf.cbs)) 638 h->tc = h->conf.cbs; 639 } 640 641 /* Remember this moment. */ 642 h->lastRefill = newt; 643 } 644 645 /* 646 * Schedule callout when we will have required tokens. 647 */ 648 static void 649 ng_car_schedule(struct hookinfo *hinfo) 650 { 651 int delay; 652 653 delay = (-(hinfo->tc)) * hz * 8 / hinfo->conf.cir + 1; 654 655 ng_callout(&hinfo->q_callout, NG_HOOK_NODE(hinfo->hook), hinfo->hook, 656 delay, &ng_car_q_event, NULL, 0); 657 } 658 659 /* 660 * Queue processing callout handler. 661 */ 662 void 663 ng_car_q_event(node_p node, hook_p hook, void *arg, int arg2) 664 { 665 struct hookinfo *hinfo = NG_HOOK_PRIVATE(hook); 666 struct mbuf *m; 667 int error; 668 669 /* Refill tokens for time we have slept. */ 670 ng_car_refillhook(hinfo); 671 672 /* If we have some tokens */ 673 while (hinfo->tc >= 0) { 674 675 /* Send packet. */ 676 m = hinfo->q[hinfo->q_first]; 677 NG_SEND_DATA_ONLY(error, hinfo->dest, m); 678 if (error != 0) 679 ++hinfo->stats.errors; 680 ++hinfo->stats.passed_pkts; 681 682 /* Get next one. */ 683 hinfo->q_first++; 684 if (hinfo->q_first >= NG_CAR_QUEUE_SIZE) 685 hinfo->q_first = 0; 686 687 /* Stop if none left. */ 688 if (hinfo->q_first == hinfo->q_last) 689 break; 690 691 /* If we have more packet, try it. */ 692 m = hinfo->q[hinfo->q_first]; 693 if (hinfo->conf.opt & NG_CAR_COUNT_PACKETS) { 694 hinfo->tc -= 128; 695 } else { 696 hinfo->tc -= m->m_pkthdr.len; 697 } 698 } 699 700 /* If something left */ 701 if (hinfo->q_first != hinfo->q_last) 702 /* Schedule queue processing. */ 703 ng_car_schedule(hinfo); 704 } 705 706 /* 707 * Enqueue packet. 708 */ 709 static void 710 ng_car_enqueue(struct hookinfo *hinfo, item_p item) 711 { 712 struct mbuf *m; 713 int len; 714 715 NGI_GET_M(item, m); 716 NG_FREE_ITEM(item); 717 718 /* Lock queue mutex. */ 719 mtx_lock(&hinfo->q_mtx); 720 721 /* Calculate used queue length. */ 722 len = hinfo->q_last - hinfo->q_first; 723 if (len < 0) 724 len += NG_CAR_QUEUE_SIZE; 725 726 /* If queue is overflowed or we have no RED tokens. */ 727 if ((len >= (NG_CAR_QUEUE_SIZE - 1)) || 728 (hinfo->te + len >= NG_CAR_QUEUE_SIZE)) { 729 /* Drop packet. */ 730 ++hinfo->stats.red_pkts; 731 ++hinfo->stats.droped_pkts; 732 NG_FREE_M(m); 733 734 hinfo->te = 0; 735 } else { 736 /* This packet is yellow. */ 737 ++hinfo->stats.yellow_pkts; 738 739 /* Enqueue packet. */ 740 hinfo->q[hinfo->q_last] = m; 741 hinfo->q_last++; 742 if (hinfo->q_last >= NG_CAR_QUEUE_SIZE) 743 hinfo->q_last = 0; 744 745 /* Use RED tokens. */ 746 if (len > NG_CAR_QUEUE_MIN_TH) 747 hinfo->te += len - NG_CAR_QUEUE_MIN_TH; 748 749 /* If this is a first packet in the queue. */ 750 if (len == 0) { 751 if (hinfo->conf.opt & NG_CAR_COUNT_PACKETS) { 752 hinfo->tc -= 128; 753 } else { 754 hinfo->tc -= m->m_pkthdr.len; 755 } 756 757 /* Schedule queue processing. */ 758 ng_car_schedule(hinfo); 759 } 760 } 761 762 /* Unlock queue mutex. */ 763 mtx_unlock(&hinfo->q_mtx); 764 } 765