sys/netgraph/ng_car.c

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