2 * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
4 * Copyright (c) 2005 Nuno Antunes <nuno.antunes@gmail.com>
5 * Copyright (c) 2007 Alexander Motin <mav@freebsd.org>
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
17 * THIS SOFTWARE IS PROVIDED BY AUTHOR AND CONTRIBUTORS ``AS IS'' AND
18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL AUTHOR OR CONTRIBUTORS BE LIABLE
21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
33 * ng_car - An implementation of committed access rate for netgraph
36 * - Sanitize input config values (impose some limits)
37 * - Implement internal packet painting (possibly using mbuf tags)
38 * - Implement color-aware mode
39 * - Implement DSCP marking for IPv4
42 #include <sys/param.h>
43 #include <sys/errno.h>
44 #include <sys/kernel.h>
45 #include <sys/malloc.h>
48 #include <netgraph/ng_message.h>
49 #include <netgraph/ng_parse.h>
50 #include <netgraph/netgraph.h>
51 #include <netgraph/ng_car.h>
53 #define NG_CAR_QUEUE_SIZE 100 /* Maximum queue size for SHAPE mode */
54 #define NG_CAR_QUEUE_MIN_TH 8 /* Minimum RED threshold for SHAPE mode */
56 /* Hook private info */
58 hook_p hook; /* this (source) hook */
59 hook_p dest; /* destination hook */
61 int64_t tc; /* committed token bucket counter */
62 int64_t te; /* exceeded/peak token bucket counter */
63 struct bintime lastRefill; /* last token refill time */
65 struct ng_car_hookconf conf; /* hook configuration */
66 struct ng_car_hookstats stats; /* hook stats */
68 struct mbuf *q[NG_CAR_QUEUE_SIZE]; /* circular packet queue */
69 u_int q_first; /* first queue element */
70 u_int q_last; /* last queue element */
71 struct callout q_callout; /* periodic queue processing routine */
72 struct mtx q_mtx; /* queue mutex */
75 /* Private information for each node instance */
77 node_p node; /* the node itself */
78 struct hookinfo upper; /* hook to upper layers */
79 struct hookinfo lower; /* hook to lower layers */
81 typedef struct privdata *priv_p;
83 static ng_constructor_t ng_car_constructor;
84 static ng_rcvmsg_t ng_car_rcvmsg;
85 static ng_shutdown_t ng_car_shutdown;
86 static ng_newhook_t ng_car_newhook;
87 static ng_rcvdata_t ng_car_rcvdata;
88 static ng_disconnect_t ng_car_disconnect;
90 static void ng_car_refillhook(struct hookinfo *h);
91 static void ng_car_schedule(struct hookinfo *h);
92 void ng_car_q_event(node_p node, hook_p hook, void *arg, int arg2);
93 static void ng_car_enqueue(struct hookinfo *h, item_p item);
95 /* Parse type for struct ng_car_hookstats */
96 static const struct ng_parse_struct_field ng_car_hookstats_type_fields[]
98 static const struct ng_parse_type ng_car_hookstats_type = {
99 &ng_parse_struct_type,
100 &ng_car_hookstats_type_fields
103 /* Parse type for struct ng_car_bulkstats */
104 static const struct ng_parse_struct_field ng_car_bulkstats_type_fields[]
105 = NG_CAR_BULKSTATS(&ng_car_hookstats_type);
106 static const struct ng_parse_type ng_car_bulkstats_type = {
107 &ng_parse_struct_type,
108 &ng_car_bulkstats_type_fields
111 /* Parse type for struct ng_car_hookconf */
112 static const struct ng_parse_struct_field ng_car_hookconf_type_fields[]
114 static const struct ng_parse_type ng_car_hookconf_type = {
115 &ng_parse_struct_type,
116 &ng_car_hookconf_type_fields
119 /* Parse type for struct ng_car_bulkconf */
120 static const struct ng_parse_struct_field ng_car_bulkconf_type_fields[]
121 = NG_CAR_BULKCONF(&ng_car_hookconf_type);
122 static const struct ng_parse_type ng_car_bulkconf_type = {
123 &ng_parse_struct_type,
124 &ng_car_bulkconf_type_fields
128 static struct ng_cmdlist ng_car_cmdlist[] = {
134 &ng_car_bulkstats_type,
145 NGM_CAR_GETCLR_STATS,
148 &ng_car_bulkstats_type,
156 &ng_car_bulkconf_type,
162 &ng_car_bulkconf_type,
168 /* Netgraph node type descriptor */
169 static struct ng_type ng_car_typestruct = {
170 .version = NG_ABI_VERSION,
171 .name = NG_CAR_NODE_TYPE,
172 .constructor = ng_car_constructor,
173 .rcvmsg = ng_car_rcvmsg,
174 .shutdown = ng_car_shutdown,
175 .newhook = ng_car_newhook,
176 .rcvdata = ng_car_rcvdata,
177 .disconnect = ng_car_disconnect,
178 .cmdlist = ng_car_cmdlist,
180 NETGRAPH_INIT(car, &ng_car_typestruct);
186 ng_car_constructor(node_p node)
190 /* Initialize private descriptor. */
191 priv = malloc(sizeof(*priv), M_NETGRAPH, M_WAITOK | M_ZERO);
193 NG_NODE_SET_PRIVATE(node, priv);
197 * Arbitrary default values
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);
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);
237 ng_car_newhook(node_p node, hook_p hook, const char *name)
239 const priv_p priv = NG_NODE_PRIVATE(node);
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);
260 ng_car_rcvdata(hook_p hook, item_p item )
262 struct hookinfo *const hinfo = NG_HOOK_PRIVATE(hook);
267 /* If queue is not empty now then enqueue packet. */
268 if (hinfo->q_first != hinfo->q_last) {
269 ng_car_enqueue(hinfo, item);
275 #define NG_CAR_PERFORM_MATCH_ACTION(a) \
278 case NG_CAR_ACTION_FORWARD: \
281 case NG_CAR_ACTION_MARK: \
282 /* XXX find a way to mark packets (mbuf tag?) */ \
283 ++hinfo->stats.errors; \
285 case NG_CAR_ACTION_DROP: \
287 /* Drop packet and return. */ \
288 NG_FREE_ITEM(item); \
289 ++hinfo->stats.dropped_pkts; \
294 /* Packet is counted as 128 tokens for better resolution */
295 if (hinfo->conf.opt & NG_CAR_COUNT_PACKETS) {
298 len = m->m_pkthdr.len;
301 /* Check committed token bucket. */
302 if (hinfo->tc - len >= 0) {
303 /* This packet is green. */
304 ++hinfo->stats.green_pkts;
306 NG_CAR_PERFORM_MATCH_ACTION(hinfo->conf.green_action);
308 /* Refill only if not green without it. */
309 ng_car_refillhook(hinfo);
311 /* Check committed token bucket again after refill. */
312 if (hinfo->tc - len >= 0) {
313 /* This packet is green */
314 ++hinfo->stats.green_pkts;
316 NG_CAR_PERFORM_MATCH_ACTION(hinfo->conf.green_action);
318 /* If not green and mode is SHAPE, enqueue packet. */
319 } else if (hinfo->conf.mode == NG_CAR_SHAPE) {
320 ng_car_enqueue(hinfo, item);
323 /* If not green and mode is RED, calculate probability. */
324 } else if (hinfo->conf.mode == NG_CAR_RED) {
325 /* Is packet is bigger then extended burst? */
326 if (len - (hinfo->tc - len) > hinfo->conf.ebs) {
327 /* This packet is definitely red. */
328 ++hinfo->stats.red_pkts;
330 NG_CAR_PERFORM_MATCH_ACTION(hinfo->conf.red_action);
332 /* Use token bucket to simulate RED-like drop
334 } else if (hinfo->te + (len - hinfo->tc) <
336 /* This packet is yellow */
337 ++hinfo->stats.yellow_pkts;
338 hinfo->te += len - hinfo->tc;
339 /* Go to negative tokens. */
341 NG_CAR_PERFORM_MATCH_ACTION(hinfo->conf.yellow_action);
343 /* This packet is probably red. */
344 ++hinfo->stats.red_pkts;
346 NG_CAR_PERFORM_MATCH_ACTION(hinfo->conf.red_action);
348 /* If not green and mode is SINGLE/DOUBLE RATE. */
350 /* Check extended token bucket. */
351 if (hinfo->te - len >= 0) {
352 /* This packet is yellow */
353 ++hinfo->stats.yellow_pkts;
355 NG_CAR_PERFORM_MATCH_ACTION(hinfo->conf.yellow_action);
357 /* This packet is red */
358 ++hinfo->stats.red_pkts;
359 NG_CAR_PERFORM_MATCH_ACTION(hinfo->conf.red_action);
364 #undef NG_CAR_PERFORM_MATCH_ACTION
366 NG_FWD_ITEM_HOOK(error, item, hinfo->dest);
368 ++hinfo->stats.errors;
369 ++hinfo->stats.passed_pkts;
375 * Receive a control message.
378 ng_car_rcvmsg(node_p node, item_p item, hook_p lasthook)
380 const priv_p priv = NG_NODE_PRIVATE(node);
381 struct ng_mesg *resp = NULL;
385 NGI_GET_MSG(item, msg);
386 switch (msg->header.typecookie) {
388 switch (msg->header.cmd) {
389 case NGM_CAR_GET_STATS:
390 case NGM_CAR_GETCLR_STATS:
392 struct ng_car_bulkstats *bstats;
394 NG_MKRESPONSE(resp, msg,
395 sizeof(*bstats), M_NOWAIT);
400 bstats = (struct ng_car_bulkstats *)resp->data;
402 bcopy(&priv->upper.stats, &bstats->downstream,
403 sizeof(bstats->downstream));
404 bcopy(&priv->lower.stats, &bstats->upstream,
405 sizeof(bstats->upstream));
407 if (msg->header.cmd == NGM_CAR_GET_STATS)
409 case NGM_CAR_CLR_STATS:
410 bzero(&priv->upper.stats,
411 sizeof(priv->upper.stats));
412 bzero(&priv->lower.stats,
413 sizeof(priv->lower.stats));
415 case NGM_CAR_GET_CONF:
417 struct ng_car_bulkconf *bconf;
419 NG_MKRESPONSE(resp, msg,
420 sizeof(*bconf), M_NOWAIT);
425 bconf = (struct ng_car_bulkconf *)resp->data;
427 bcopy(&priv->upper.conf, &bconf->downstream,
428 sizeof(bconf->downstream));
429 bcopy(&priv->lower.conf, &bconf->upstream,
430 sizeof(bconf->upstream));
431 /* Convert internal 1/(8*128) of pps into pps */
432 if (bconf->downstream.opt & NG_CAR_COUNT_PACKETS) {
433 bconf->downstream.cir /= 1024;
434 bconf->downstream.pir /= 1024;
435 bconf->downstream.cbs /= 128;
436 bconf->downstream.ebs /= 128;
438 if (bconf->upstream.opt & NG_CAR_COUNT_PACKETS) {
439 bconf->upstream.cir /= 1024;
440 bconf->upstream.pir /= 1024;
441 bconf->upstream.cbs /= 128;
442 bconf->upstream.ebs /= 128;
446 case NGM_CAR_SET_CONF:
448 struct ng_car_bulkconf *const bconf =
449 (struct ng_car_bulkconf *)msg->data;
451 /* Check for invalid or illegal config. */
452 if (msg->header.arglen != sizeof(*bconf)) {
456 /* Convert pps into internal 1/(8*128) of pps */
457 if (bconf->downstream.opt & NG_CAR_COUNT_PACKETS) {
458 bconf->downstream.cir *= 1024;
459 bconf->downstream.pir *= 1024;
460 bconf->downstream.cbs *= 125;
461 bconf->downstream.ebs *= 125;
463 if (bconf->upstream.opt & NG_CAR_COUNT_PACKETS) {
464 bconf->upstream.cir *= 1024;
465 bconf->upstream.pir *= 1024;
466 bconf->upstream.cbs *= 125;
467 bconf->upstream.ebs *= 125;
469 if ((bconf->downstream.cir > 1000000000) ||
470 (bconf->downstream.pir > 1000000000) ||
471 (bconf->upstream.cir > 1000000000) ||
472 (bconf->upstream.pir > 1000000000) ||
473 (bconf->downstream.cbs == 0 &&
474 bconf->downstream.ebs == 0) ||
475 (bconf->upstream.cbs == 0 &&
476 bconf->upstream.ebs == 0))
481 if ((bconf->upstream.mode == NG_CAR_SHAPE) &&
482 (bconf->upstream.cir == 0)) {
486 if ((bconf->downstream.mode == NG_CAR_SHAPE) &&
487 (bconf->downstream.cir == 0)) {
492 /* Copy downstream config. */
493 bcopy(&bconf->downstream, &priv->upper.conf,
494 sizeof(priv->upper.conf));
495 priv->upper.tc = priv->upper.conf.cbs;
496 if (priv->upper.conf.mode == NG_CAR_RED ||
497 priv->upper.conf.mode == NG_CAR_SHAPE) {
500 priv->upper.te = priv->upper.conf.ebs;
503 /* Copy upstream config. */
504 bcopy(&bconf->upstream, &priv->lower.conf,
505 sizeof(priv->lower.conf));
506 priv->lower.tc = priv->lower.conf.cbs;
507 if (priv->lower.conf.mode == NG_CAR_RED ||
508 priv->lower.conf.mode == NG_CAR_SHAPE) {
511 priv->lower.te = priv->lower.conf.ebs;
524 NG_RESPOND_MSG(error, node, item, resp);
530 * Do local shutdown processing.
533 ng_car_shutdown(node_p node)
535 const priv_p priv = NG_NODE_PRIVATE(node);
537 ng_uncallout(&priv->upper.q_callout, node);
538 ng_uncallout(&priv->lower.q_callout, node);
539 mtx_destroy(&priv->upper.q_mtx);
540 mtx_destroy(&priv->lower.q_mtx);
541 NG_NODE_UNREF(priv->node);
542 free(priv, M_NETGRAPH);
547 * Hook disconnection.
549 * For this type, removal of the last link destroys the node.
552 ng_car_disconnect(hook_p hook)
554 struct hookinfo *const hinfo = NG_HOOK_PRIVATE(hook);
555 const node_p node = NG_HOOK_NODE(hook);
556 const priv_p priv = NG_NODE_PRIVATE(node);
559 /* Purge queue if not empty. */
560 while (hinfo->q_first != hinfo->q_last) {
561 NG_FREE_M(hinfo->q[hinfo->q_first]);
563 if (hinfo->q_first >= NG_CAR_QUEUE_SIZE)
566 /* Remove hook refs. */
567 if (hinfo->hook == priv->upper.hook)
568 priv->lower.dest = NULL;
570 priv->upper.dest = NULL;
573 /* Already shutting down? */
574 if ((NG_NODE_NUMHOOKS(NG_HOOK_NODE(hook)) == 0)
575 && (NG_NODE_IS_VALID(NG_HOOK_NODE(hook))))
576 ng_rmnode_self(NG_HOOK_NODE(hook));
581 * Hook's token buckets refillment.
584 ng_car_refillhook(struct hookinfo *h)
586 struct bintime newt, deltat;
587 unsigned int deltat_us;
589 /* Get current time. */
592 /* Get time delta since last refill. */
594 bintime_sub(&deltat, &h->lastRefill);
596 /* Time must go forward. */
597 if (deltat.sec < 0) {
598 h->lastRefill = newt;
602 /* But not too far forward. */
603 if (deltat.sec >= 1000) {
604 deltat_us = (1000 << 20);
606 /* convert bintime to the 1/(2^20) of sec */
607 deltat_us = (deltat.sec << 20) + (deltat.frac >> 44);
610 if (h->conf.mode == NG_CAR_SINGLE_RATE) {
612 /* Refill committed token bucket. */
613 h->tc += (h->conf.cir * deltat_us) >> 23;
614 delta = h->tc - h->conf.cbs;
618 /* Refill exceeded token bucket. */
620 if (h->te > ((int64_t)h->conf.ebs))
624 } else if (h->conf.mode == NG_CAR_DOUBLE_RATE) {
625 /* Refill committed token bucket. */
626 h->tc += (h->conf.cir * deltat_us) >> 23;
627 if (h->tc > ((int64_t)h->conf.cbs))
630 /* Refill peak token bucket. */
631 h->te += (h->conf.pir * deltat_us) >> 23;
632 if (h->te > ((int64_t)h->conf.ebs))
635 } else { /* RED or SHAPE mode. */
636 /* Refill committed token bucket. */
637 h->tc += (h->conf.cir * deltat_us) >> 23;
638 if (h->tc > ((int64_t)h->conf.cbs))
642 /* Remember this moment. */
643 h->lastRefill = newt;
647 * Schedule callout when we will have required tokens.
650 ng_car_schedule(struct hookinfo *hinfo)
654 delay = (-(hinfo->tc)) * hz * 8 / hinfo->conf.cir + 1;
656 ng_callout(&hinfo->q_callout, NG_HOOK_NODE(hinfo->hook), hinfo->hook,
657 delay, &ng_car_q_event, NULL, 0);
661 * Queue processing callout handler.
664 ng_car_q_event(node_p node, hook_p hook, void *arg, int arg2)
666 struct hookinfo *hinfo = NG_HOOK_PRIVATE(hook);
670 /* Refill tokens for time we have slept. */
671 ng_car_refillhook(hinfo);
673 /* If we have some tokens */
674 while (hinfo->tc >= 0) {
676 m = hinfo->q[hinfo->q_first];
677 NG_SEND_DATA_ONLY(error, hinfo->dest, m);
679 ++hinfo->stats.errors;
680 ++hinfo->stats.passed_pkts;
684 if (hinfo->q_first >= NG_CAR_QUEUE_SIZE)
687 /* Stop if none left. */
688 if (hinfo->q_first == hinfo->q_last)
691 /* If we have more packet, try it. */
692 m = hinfo->q[hinfo->q_first];
693 if (hinfo->conf.opt & NG_CAR_COUNT_PACKETS) {
696 hinfo->tc -= m->m_pkthdr.len;
700 /* If something left */
701 if (hinfo->q_first != hinfo->q_last)
702 /* Schedule queue processing. */
703 ng_car_schedule(hinfo);
710 ng_car_enqueue(struct hookinfo *hinfo, item_p item)
718 /* Lock queue mutex. */
719 mtx_lock(&hinfo->q_mtx);
721 /* Calculate used queue length. */
722 len = hinfo->q_last - hinfo->q_first;
724 len += NG_CAR_QUEUE_SIZE;
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)) {
730 ++hinfo->stats.red_pkts;
731 ++hinfo->stats.dropped_pkts;
736 /* This packet is yellow. */
737 ++hinfo->stats.yellow_pkts;
739 /* Enqueue packet. */
740 hinfo->q[hinfo->q_last] = m;
742 if (hinfo->q_last >= NG_CAR_QUEUE_SIZE)
745 /* Use RED tokens. */
746 if (len > NG_CAR_QUEUE_MIN_TH)
747 hinfo->te += len - NG_CAR_QUEUE_MIN_TH;
749 /* If this is a first packet in the queue. */
751 if (hinfo->conf.opt & NG_CAR_COUNT_PACKETS) {
754 hinfo->tc -= m->m_pkthdr.len;
757 /* Schedule queue processing. */
758 ng_car_schedule(hinfo);
762 /* Unlock queue mutex. */
763 mtx_unlock(&hinfo->q_mtx);