A node that implements various traffic shaping and rate limiting algorithms.

Approved by:	glebius (mentor)

2 files changed, 867 insertions, 0 deletions

diff --git a/sys/netgraph/ng_car.c b/sys/netgraph/ng_car.c
new file mode 100644
index 0000000..820a1e3
--- /dev/null
+++ b/sys/netgraph/ng_car.c
@@ -0,0 +1,728 @@
+/*-
+ * Copyright (c) 2005 Nuno Antunes <nuno.antunes@gmail.com>
+ * Copyright (c) 2007 Alexander Motin <mav@freebsd.org>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ * $FreeBSD$
+ */
+
+/*
+ * ng_car - An implementation of commited access rate for netgraph
+ *
+ * TODO:
+ *	- Sanitize input config values (impose some limits)
+ *	- Implement internal packet painting (possibly using mbuf tags)
+ *	- Implement color-aware mode
+ *	- Implement DSCP marking for IPv4
+ */
+
+#include <sys/param.h>
+#include <sys/systm.h>
+#include <sys/kernel.h>
+#include <sys/mbuf.h>
+#include <sys/malloc.h>
+#include <sys/ctype.h>
+#include <sys/errno.h>
+#include <sys/syslog.h>
+
+#include <netgraph/ng_message.h>
+#include <netgraph/ng_parse.h>
+#include <netgraph/netgraph.h>
+#include <netgraph/ng_car.h>
+
+#define NG_CAR_QUEUE_SIZE	100	/* Maximum queue size for SHAPE mode */
+#define NG_CAR_QUEUE_MIN_TH	8	/* Minimum RED threshhold for SHAPE mode */
+
+/* Hook private info */
+struct hookinfo {
+	hook_p		hook;		/* this (source) hook */
+	hook_p		dest;		/* destination hook */
+
+	int64_t 	tc;		/* commited token bucket counter */
+	int64_t 	te;		/* exceeded / peak token bucket counter */
+	struct timeval	lastRefill;	/* last token refill time */
+
+	struct ng_car_hookconf conf;	/* hook configuration */
+	struct ng_car_hookstats stats;	/* hook stats */
+
+	struct mbuf*	q[NG_CAR_QUEUE_SIZE];	/* circular packet queue */
+	int		q_first;	/* first queue element */
+	int		q_last;		/* last queue element */
+	struct callout	q_callout;	/* periodic queue processing routine */
+	struct mtx	q_mtx;		/* queue mutex */
+};
+
+/* Private information for each node instance */
+struct privdata {
+	node_p node;				/* the node itself */
+	struct hookinfo upper;			/* hook to upper layers */
+	struct hookinfo lower;			/* hook to lower layers */
+};
+typedef struct privdata *priv_p;
+
+static ng_constructor_t	ng_car_constructor;
+static ng_rcvmsg_t	ng_car_rcvmsg;
+static ng_shutdown_t	ng_car_shutdown;
+static ng_newhook_t	ng_car_newhook;
+static ng_rcvdata_t	ng_car_rcvdata;
+static ng_disconnect_t	ng_car_disconnect;
+
+static void	ng_car_refillhook(struct hookinfo *h);
+static void	ng_car_schedule(struct hookinfo *h);
+void		ng_car_q_event(node_p node, hook_p hook, void *arg, int arg2);
+static void	ng_car_enqueue(struct hookinfo *h, item_p item);
+
+/* Parse type for struct ng_car_hookstats */
+static const struct ng_parse_struct_field ng_car_hookstats_type_fields[]
+	= NG_CAR_HOOKSTATS;
+static const struct ng_parse_type ng_car_hookstats_type = {
+	&ng_parse_struct_type,
+	&ng_car_hookstats_type_fields
+};
+
+/* Parse type for struct ng_car_bulkstats */
+static const struct ng_parse_struct_field ng_car_bulkstats_type_fields[]
+	= NG_CAR_BULKSTATS(&ng_car_hookstats_type);
+static const struct ng_parse_type ng_car_bulkstats_type = {
+	&ng_parse_struct_type,
+	&ng_car_bulkstats_type_fields
+};
+
+/* Parse type for struct ng_car_hookconf */
+static const struct ng_parse_struct_field ng_car_hookconf_type_fields[]
+	= NG_CAR_HOOKCONF;
+static const struct ng_parse_type ng_car_hookconf_type = {
+	&ng_parse_struct_type,
+	&ng_car_hookconf_type_fields
+};
+
+/* Parse type for struct ng_car_bulkconf */
+static const struct ng_parse_struct_field ng_car_bulkconf_type_fields[]
+	= NG_CAR_BULKCONF(&ng_car_hookconf_type);
+static const struct ng_parse_type ng_car_bulkconf_type = {
+	&ng_parse_struct_type,
+	&ng_car_bulkconf_type_fields
+};
+
+/* Command list */
+static struct ng_cmdlist ng_car_cmdlist[] = {
+	{
+	  NGM_CAR_COOKIE,
+	  NGM_CAR_GET_STATS,
+	  "getstats",
+	  NULL,
+	  &ng_car_bulkstats_type,
+	},
+	{
+	  NGM_CAR_COOKIE,
+	  NGM_CAR_CLR_STATS,
+	  "clrstats",
+	  NULL,
+	  NULL,
+	},
+	{
+	  NGM_CAR_COOKIE,
+	  NGM_CAR_GETCLR_STATS,
+	  "getclrstats",
+	  NULL,
+	  &ng_car_bulkstats_type,
+	},
+
+	{
+	  NGM_CAR_COOKIE,
+	  NGM_CAR_GET_CONF,
+	  "getconf",
+	  NULL,
+	  &ng_car_bulkconf_type,
+	},
+	{
+	  NGM_CAR_COOKIE,
+	  NGM_CAR_SET_CONF,
+	  "setconf",
+	  &ng_car_bulkconf_type,
+	  NULL,
+	},
+	{ 0 }
+};
+
+/* Netgraph node type descriptor */
+static struct ng_type ng_car_typestruct = {
+	.version =	NG_ABI_VERSION,
+	.name =		NG_CAR_NODE_TYPE,
+	.constructor =	ng_car_constructor,
+	.rcvmsg =	ng_car_rcvmsg,
+	.shutdown =	ng_car_shutdown,
+	.newhook =	ng_car_newhook,
+	.rcvdata =	ng_car_rcvdata,
+	.disconnect =	ng_car_disconnect,
+	.cmdlist =	ng_car_cmdlist,
+};
+NETGRAPH_INIT(car, &ng_car_typestruct);
+
+/*
+ * Node constructor
+ */
+static int
+ng_car_constructor(node_p node)
+{
+	priv_p priv;
+
+	/* Initialize private descriptor */
+	MALLOC(priv, priv_p, sizeof(*priv), M_NETGRAPH,
+		M_NOWAIT | M_ZERO);
+	if (priv == NULL)
+		return (ENOMEM);
+
+	NG_NODE_SET_PRIVATE(node, priv);
+	priv->node = node;
+
+	/*
+	 * Arbitrary default values
+	 */
+
+	priv->upper.hook = NULL;
+	priv->upper.dest = NULL;
+	priv->upper.tc = priv->upper.conf.cbs = NG_CAR_CBS_MIN;
+	priv->upper.te = priv->upper.conf.ebs = NG_CAR_EBS_MIN;
+	priv->upper.conf.cir = NG_CAR_CIR_DFLT;
+	priv->upper.conf.green_action = NG_CAR_ACTION_FORWARD;
+	priv->upper.conf.yellow_action = NG_CAR_ACTION_FORWARD;
+	priv->upper.conf.red_action = NG_CAR_ACTION_DROP;
+	priv->upper.conf.mode = 0;
+	getmicrotime(&priv->upper.lastRefill);
+	priv->upper.q_first = 0;
+	priv->upper.q_last = 0;
+	ng_callout_init(&priv->upper.q_callout);
+	mtx_init(&priv->upper.q_mtx, "ng_car_u", NULL, MTX_DEF);
+
+	priv->lower.hook = NULL;
+	priv->lower.dest = NULL;
+	priv->lower.tc = priv->lower.conf.cbs = NG_CAR_CBS_MIN;
+	priv->lower.te = priv->lower.conf.ebs = NG_CAR_EBS_MIN;
+	priv->lower.conf.cir = NG_CAR_CIR_DFLT;
+	priv->lower.conf.green_action = NG_CAR_ACTION_FORWARD;
+	priv->lower.conf.yellow_action = NG_CAR_ACTION_FORWARD;
+	priv->lower.conf.red_action = NG_CAR_ACTION_DROP;
+	priv->lower.conf.mode = 0;
+	priv->lower.lastRefill = priv->upper.lastRefill;
+	priv->lower.q_first = 0;
+	priv->lower.q_last = 0;
+	ng_callout_init(&priv->lower.q_callout);
+	mtx_init(&priv->lower.q_mtx, "ng_car_l", NULL, MTX_DEF);
+
+	return (0);
+}
+
+/*
+ * Add a hook
+ */
+static int
+ng_car_newhook(node_p node, hook_p hook, const char *name)
+{
+	const priv_p priv = NG_NODE_PRIVATE(node);
+
+	if (strcmp(name, NG_CAR_HOOK_LOWER) == 0) {
+		priv->lower.hook = hook;
+		priv->upper.dest = hook;
+		bzero(&priv->lower.stats, sizeof(priv->lower.stats));
+		NG_HOOK_SET_PRIVATE(hook, &priv->lower);
+	} else if (strcmp(name, NG_CAR_HOOK_UPPER) == 0) {
+		priv->upper.hook = hook;
+		priv->lower.dest = hook;
+		bzero(&priv->upper.stats, sizeof(priv->upper.stats));
+		NG_HOOK_SET_PRIVATE(hook, &priv->upper);
+	} else
+		return (EINVAL);
+	return(0);
+}
+
+/*
+ * Data has arrived
+ */
+static int
+ng_car_rcvdata(hook_p hook, item_p item )
+{
+	struct hookinfo *const hinfo = NG_HOOK_PRIVATE(hook);
+	hook_p dest = hinfo->dest;
+	struct mbuf *m = NULL;
+	int error = 0;
+
+	/* Node is useless without destination hook. */
+	if (dest == NULL) {
+		NG_FREE_ITEM(item);
+		++hinfo->stats.errors;
+		return(EINVAL);
+	}
+
+	/* If queue is not empty now then enqueue packet. */
+	if (hinfo->q_first != hinfo->q_last) {
+		ng_car_enqueue(hinfo, item);
+		return (0);
+	}
+
+	m = NGI_M(item);
+
+#define NG_CAR_PERFORM_MATCH_ACTION(a)			\
+	do {						\
+		switch (a) {				\
+		case NG_CAR_ACTION_FORWARD:		\
+			/* Do nothing */		\
+			break;				\
+		case NG_CAR_ACTION_MARK:		\
+			/* XXX find a way to mark packets (mbuf tag?) */ \
+			++hinfo->stats.errors;		\
+			break;				\
+		case NG_CAR_ACTION_DROP:		\
+		default:				\
+			/* Drop packet and return */	\
+			NG_FREE_ITEM(item);		\
+			++hinfo->stats.droped_pkts;	\
+			return 0;			\
+		}					\
+	}						\
+	while (0)
+
+	/* Check commited token bucket. */
+	if (hinfo->tc - m->m_pkthdr.len >= 0) {
+		/* This packet is green */
+		++hinfo->stats.green_pkts;
+		hinfo->tc -= m->m_pkthdr.len;
+		NG_CAR_PERFORM_MATCH_ACTION(hinfo->conf.green_action);
+        } else {
+
+	    /* Refill only if not green without it. */
+	    ng_car_refillhook(hinfo);
+
+	    /* Check commited token bucket again after refill. */
+	    if (hinfo->tc - m->m_pkthdr.len >= 0) {
+		/* This packet is green */
+		++hinfo->stats.green_pkts;
+		hinfo->tc -= m->m_pkthdr.len;
+		NG_CAR_PERFORM_MATCH_ACTION(hinfo->conf.green_action);
+
+	    /* If not green and mode is SHAPE, enqueue packet. */
+    	    } else if (hinfo->conf.mode == NG_CAR_SHAPE) {
+		ng_car_enqueue(hinfo, item);
+		return (0);
+
+	    /* If not green and mode is RED, calculate probability. */
+    	    } else if (hinfo->conf.mode == NG_CAR_RED) {
+		/* Is packet is bigger then extended burst? */
+		if (m->m_pkthdr.len - (hinfo->tc - m->m_pkthdr.len) 
+			> hinfo->conf.ebs) {
+		    /* This packet is definitely red */
+		    ++hinfo->stats.red_pkts;
+		    hinfo->te = 0;
+		    NG_CAR_PERFORM_MATCH_ACTION(hinfo->conf.red_action);
+
+		/* Use token bucket to simulate RED-like drop probability. */
+		} else if (hinfo->te + (m->m_pkthdr.len - hinfo->tc)
+			< hinfo->conf.ebs) {
+		    /* This packet is yellow */
+		    ++hinfo->stats.yellow_pkts;
+		    hinfo->te += m->m_pkthdr.len - hinfo->tc;
+		    hinfo->tc -= m->m_pkthdr.len; /* go to negative tokens */
+		    NG_CAR_PERFORM_MATCH_ACTION(hinfo->conf.yellow_action);
+
+		} else {
+		    /* This packet is probaly red */
+		    ++hinfo->stats.red_pkts;
+		    hinfo->te = 0;
+		    NG_CAR_PERFORM_MATCH_ACTION(hinfo->conf.red_action);
+		}
+
+	    /* If not green and mode is SINGLE/DOUBLE RATE. */
+	    } else {
+		/* Check extended token bucket. */
+		if (hinfo->te - m->m_pkthdr.len >= 0) {
+		    /* This packet is yellow */
+		    ++hinfo->stats.yellow_pkts;
+		    hinfo->te -= m->m_pkthdr.len;
+		    NG_CAR_PERFORM_MATCH_ACTION(hinfo->conf.yellow_action);
+
+		} else {
+		    /* This packet is red */
+		    ++hinfo->stats.red_pkts;
+		    NG_CAR_PERFORM_MATCH_ACTION(hinfo->conf.red_action);
+		}
+	    }
+	}
+
+#undef NG_CAR_PERFORM_MATCH_ACTION
+
+	NG_FWD_ITEM_HOOK(error, item, dest);
+	if (error != 0)
+		++hinfo->stats.errors;
+	++hinfo->stats.passed_pkts;
+
+	return error;
+}
+
+/*
+ * Receive a control message
+ */
+static int
+ng_car_rcvmsg(node_p node, item_p item, hook_p lasthook)
+{
+	const priv_p priv = NG_NODE_PRIVATE(node);
+	struct ng_mesg *resp = NULL;
+	int error = 0;
+	struct ng_mesg *msg;
+
+	NGI_GET_MSG(item, msg);
+	switch (msg->header.typecookie) {
+	case NGM_CAR_COOKIE:
+		switch (msg->header.cmd) {
+		case NGM_CAR_GET_STATS:
+		case NGM_CAR_GETCLR_STATS:
+			{
+				struct ng_car_bulkstats *bstats;
+	
+				NG_MKRESPONSE(resp, msg,
+					sizeof(*bstats), M_NOWAIT);
+				if (resp == NULL) {
+					error = ENOMEM;
+					break;
+				}
+				bstats = (struct ng_car_bulkstats *)resp->data;
+
+				bcopy(&priv->upper.stats, &bstats->downstream,
+				    sizeof(bstats->downstream));
+				bcopy(&priv->lower.stats, &bstats->upstream,
+				    sizeof(bstats->upstream));
+			}
+			if (msg->header.cmd == NGM_CAR_GET_STATS)
+				break;
+		case NGM_CAR_CLR_STATS:
+			bzero(&priv->upper.stats,
+				sizeof(priv->upper.stats));
+			bzero(&priv->lower.stats,
+				sizeof(priv->lower.stats));
+			break;
+		case NGM_CAR_GET_CONF:
+			{
+				struct ng_car_bulkconf *bconf;
+	
+				NG_MKRESPONSE(resp, msg,
+					sizeof(*bconf), M_NOWAIT);
+				if (resp == NULL) {
+					error = ENOMEM;
+					break;
+				}
+				bconf = (struct ng_car_bulkconf *)resp->data;
+
+				bcopy(&priv->upper.conf, &bconf->downstream,
+				    sizeof(bconf->downstream));
+				bcopy(&priv->lower.conf, &bconf->upstream,
+				    sizeof(bconf->upstream));
+			}
+			break;
+		case NGM_CAR_SET_CONF:
+			{
+				struct ng_car_bulkconf *const bconf =
+				(struct ng_car_bulkconf *)msg->data;
+	
+				/* Check for invalid or illegal config. */
+				if ((msg->header.arglen != sizeof(*bconf))
+				    || (bconf->downstream.cir > 1000000000)
+				    || (bconf->downstream.pir > 1000000000)
+				    || (bconf->upstream.cir > 1000000000)
+				    || (bconf->upstream.pir > 1000000000)
+				    || (bconf->downstream.cbs == 0 
+					&& bconf->downstream.ebs == 0)
+				    || (bconf->upstream.cbs == 0 
+					&& bconf->upstream.ebs == 0))
+				{
+					error = EINVAL;
+					break;
+				}
+
+				/* Copy downstream config. */
+				bcopy(&bconf->downstream, &priv->upper.conf,
+				    sizeof(priv->upper.conf));
+    				priv->upper.tc = priv->upper.conf.cbs;
+				if (priv->upper.conf.mode == NG_CAR_RED ||
+				    priv->lower.conf.mode == NG_CAR_SHAPE) {
+					priv->upper.te = 0;
+				} else {
+					priv->upper.te = priv->upper.conf.ebs;
+				}
+
+				/* Copy upstream config. */
+				bcopy(&bconf->upstream, &priv->lower.conf,
+				    sizeof(priv->lower.conf));
+    				priv->lower.tc = priv->lower.conf.cbs;
+				if (priv->lower.conf.mode == NG_CAR_RED ||
+				    priv->lower.conf.mode == NG_CAR_SHAPE) {
+					priv->lower.te = 0;
+				} else {
+					priv->lower.te = priv->lower.conf.ebs;
+				}
+			}
+			break;
+		default:
+			error = EINVAL;
+			break;
+		}
+		break;
+	default:
+		error = EINVAL;
+		break;
+	}
+	NG_RESPOND_MSG(error, node, item, resp);
+	NG_FREE_MSG(msg);
+	return (error);
+}
+
+/*
+ * Do local shutdown processing.
+ */
+static int
+ng_car_shutdown(node_p node)
+{
+	const priv_p priv = NG_NODE_PRIVATE(node);
+
+	mtx_destroy(&priv->upper.q_mtx);
+	mtx_destroy(&priv->lower.q_mtx);
+	NG_NODE_SET_PRIVATE(node, NULL);
+	NG_NODE_UNREF(priv->node);
+	FREE(priv, M_NETGRAPH);
+	return (0);
+}
+
+/*
+ * Hook disconnection.
+ *
+ * For this type, removal of the last link destroys the node.
+ */
+static int
+ng_car_disconnect(hook_p hook)
+{
+	struct hookinfo *const hinfo = NG_HOOK_PRIVATE(hook);
+	const node_p node = NG_HOOK_NODE(hook);
+	const priv_p priv = NG_NODE_PRIVATE(node);
+
+	if (hinfo) {
+		/* Purge queue if not empty. */
+		while (hinfo->q_first != hinfo->q_last) {
+			NG_FREE_M(hinfo->q[hinfo->q_first]);
+			hinfo->q_first++;
+			if (hinfo->q_first >= NG_CAR_QUEUE_SIZE)
+		    		hinfo->q_first = 0;
+		}
+		/* Remove hook refs. */
+		if (hinfo->hook == priv->upper.hook) 
+			priv->lower.dest = NULL;
+		else 
+			priv->upper.dest = NULL;
+		hinfo->hook = NULL;
+	}
+	/* Already shutting down? */
+	if ((NG_NODE_NUMHOOKS(NG_HOOK_NODE(hook)) == 0)
+	    && (NG_NODE_IS_VALID(NG_HOOK_NODE(hook))))
+		ng_rmnode_self(NG_HOOK_NODE(hook));
+	return (0);
+}
+
+/*
+ * Hook's token buckets refillment.
+ */
+static void
+ng_car_refillhook(struct hookinfo *h)
+{
+	struct timeval newt, deltat;
+	int64_t deltat_us;
+	int64_t	delta;
+
+	/* Get current time. */
+	getmicrotime(&newt);
+
+	/* Time must go forward. */
+	if (timevalcmp(&newt, &h->lastRefill, <= )) {
+	    h->lastRefill = newt;
+	    return;
+	}
+
+	/* Get time delta since last refill. */
+	deltat = newt;
+	timevalsub(&deltat, &h->lastRefill);
+
+	/* Sanity check */
+	if (deltat.tv_sec > 1000) {
+	    deltat_us = 1000000000;
+	} else {
+	    deltat_us = ((int64_t)deltat.tv_sec) * 1000000 + deltat.tv_usec;
+	}
+
+	if (h->conf.mode == NG_CAR_SINGLE_RATE) {
+		/* Refill commited token bucket. */
+		h->tc += h->conf.cir * deltat_us / 8000000;
+		delta = h->tc - h->conf.cbs;
+		if (delta > 0) {
+			h->tc = h->conf.cbs;
+
+			/* Refill exceeded token bucket. */
+			h->te += delta;
+			if (h->te > h->conf.ebs)
+				h->te = h->conf.ebs;
+		}
+
+	} else if (h->conf.mode == NG_CAR_DOUBLE_RATE) {
+		/* Refill commited token bucket. */
+		h->tc += h->conf.cir * deltat_us / 8000000;
+		if (h->tc > h->conf.cbs)
+			h->tc = h->conf.cbs;
+
+		/* Refill peak token bucket. */
+		h->te += h->conf.pir * deltat_us / 8000000;
+		if (h->te > h->conf.ebs)
+			h->te = h->conf.ebs;
+
+	} else { /* RED or SHAPE mode. */
+		/* Refill commited token bucket. */
+		h->tc += h->conf.cir * deltat_us / 8000000;
+		if (h->tc > ((int64_t)h->conf.cbs))
+			h->tc = h->conf.cbs;
+	}
+
+	/* Remember this moment. */
+	h->lastRefill = newt;
+
+	return;
+}
+
+/*
+ * Schedule callout when we will have required tokens.
+ */
+static void
+ng_car_schedule(struct hookinfo *hinfo)
+{
+	int 	delay;
+	
+	delay = (-(hinfo->tc)) * hz * 8 / hinfo->conf.cir + 1;
+
+	ng_callout(&hinfo->q_callout, NG_HOOK_NODE(hinfo->hook), hinfo->hook, 
+	    delay, &ng_car_q_event, NULL, 0);
+}
+
+/*
+ * Queue processing callout handler.
+ */
+void
+ng_car_q_event(node_p node, hook_p hook, void *arg, int arg2)
+{
+	struct hookinfo	*hinfo = NG_HOOK_PRIVATE(hook);
+	item_p 		item;
+	struct mbuf 	*m;
+	int		error;
+
+	/* Refill tokens for time we have slept. */
+	ng_car_refillhook(hinfo);
+
+	if (hinfo->dest != NULL) {
+		/* If we have some tokens */
+		while (hinfo->tc >= 0) {
+
+			/* Send packet. */
+			m = hinfo->q[hinfo->q_first];
+			if ((item = ng_package_data(m, NG_NOFLAGS)) != NULL) {
+		    		NG_FWD_ITEM_HOOK(error, item, hinfo->dest);
+			}
+
+			/* Get next one. */
+			hinfo->q_first++;
+			if (hinfo->q_first >= NG_CAR_QUEUE_SIZE)
+				hinfo->q_first = 0;
+
+			/* Stop if none left. */
+			if (hinfo->q_first == hinfo->q_last)
+				break;
+
+			/* If we have more packet, try it. */
+			m = hinfo->q[hinfo->q_first];
+			hinfo->tc -= m->m_pkthdr.len;
+		}
+	}
+
+	/* If something left */
+	if (hinfo->q_first != hinfo->q_last) {
+		/* schedule queue processing. */
+		ng_car_schedule(hinfo);
+	}
+}
+
+/*
+ * Enqueue packet.
+ */
+static void
+ng_car_enqueue(struct hookinfo *hinfo, item_p item)
+{
+	struct mbuf 	*m;
+	int		len;
+
+	NGI_GET_M(item, m);
+	NG_FREE_ITEM(item);
+
+	/* Lock queue mutex */
+	mtx_lock(&hinfo->q_mtx);
+
+	/* Calculate used queue length */
+	len = hinfo->q_last - hinfo->q_first;
+	if (len < 0)
+		len += NG_CAR_QUEUE_SIZE;
+
+	/* If queue is overflowed or we have no RED tokens */
+	if ((len >= (NG_CAR_QUEUE_SIZE - 1)) || 
+	    (hinfo->te + len >= NG_CAR_QUEUE_SIZE)) {
+		/* drop packet. */
+		++hinfo->stats.red_pkts;
+		NG_FREE_M(m);
+		
+		hinfo->te = 0;
+	} else {
+		/* This packet is yellow. */
+		++hinfo->stats.yellow_pkts;
+
+		/* Enqueue packet. */
+		hinfo->q[hinfo->q_last] = m;
+		hinfo->q_last++;
+		if (hinfo->q_last >= NG_CAR_QUEUE_SIZE)
+			hinfo->q_last = 0;
+
+		/* Use RED tokens. */
+		if (len > NG_CAR_QUEUE_MIN_TH)
+			hinfo->te += len - NG_CAR_QUEUE_MIN_TH;
+
+		/* If this is a first packet it the queue */
+		if (len == 0) {
+			hinfo->tc -= m->m_pkthdr.len;
+
+			/* schedule queue processing. */
+			ng_car_schedule(hinfo);
+		}
+	}
+
+	/* Unlock queue mutex */
+	mtx_unlock(&hinfo->q_mtx);
+}
diff --git a/sys/netgraph/ng_car.h b/sys/netgraph/ng_car.h
new file mode 100644
index 0000000..64ce52c
--- /dev/null
+++ b/sys/netgraph/ng_car.h
@@ -0,0 +1,139 @@
+/*-
+ * Copyright (c) 2005 Nuno Antunes <nuno.antunes@gmail.com>
+ * Copyright (c) 2007 Alexander Motin <mav@freebsd.org>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ * $FreeBSD$
+ */
+
+#ifndef _NETGRAPH_NG_CAR_H_
+#define _NETGRAPH_NG_CAR_H_
+
+#define NG_CAR_NODE_TYPE	"car"
+#define NGM_CAR_COOKIE		1173648034
+
+/* Hook names */
+#define NG_CAR_HOOK_UPPER	"upper"
+#define NG_CAR_HOOK_LOWER	"lower"
+
+/* Per hook statistics counters */
+struct ng_car_hookstats {
+	u_int64_t passed_pkts;	/* Counter for passed packets */
+	u_int64_t droped_pkts;	/* Counter for droped packets */
+	u_int64_t green_pkts;	/* Counter for green packets */
+	u_int64_t yellow_pkts;	/* Counter for yellow packets */
+	u_int64_t red_pkts;	/* Counter for red packets */
+	u_int64_t errors;	/* Counter for operation errors */
+};
+#define NG_CAR_HOOKSTATS	{				\
+	  { "passed",		&ng_parse_uint64_type	},	\
+	  { "droped",		&ng_parse_uint64_type	},	\
+	  { "green",		&ng_parse_uint64_type	},	\
+	  { "yellow",		&ng_parse_uint64_type	},	\
+	  { "red",		&ng_parse_uint64_type	},	\
+	  { "errors",		&ng_parse_uint64_type	},	\
+	  { NULL }						\
+}
+
+/* Bulk statistics */
+struct ng_car_bulkstats {
+	struct ng_car_hookstats upstream;
+	struct ng_car_hookstats downstream;
+};
+#define NG_CAR_BULKSTATS(hstatstype) {				\
+	  { "upstream",		(hstatstype)		},	\
+	  { "downstream",	(hstatstype)		},	\
+	  { NULL }						\
+}
+
+/* Per hook configuration */
+struct ng_car_hookconf {
+	u_int64_t cbs;		/* Commited burst size (bytes) */
+	u_int64_t ebs;		/* Exceeded/Peak burst size (bytes) */
+	u_int64_t cir;		/* Commited information rate (bits/s) */
+	u_int64_t pir;		/* Peak information rate (bits/s) */
+	u_int8_t green_action;	/* Action for green packets */
+	u_int8_t yellow_action;	/* Action for yellow packets */
+	u_int8_t red_action;	/* Action for red packets */
+	u_int8_t mode;		/* single/double rate, ... */
+	u_int8_t opt;		/* color-aware or color-blind */
+};
+/* Keep this definition in sync with the above structure */
+#define NG_CAR_HOOKCONF	{					\
+	  { "cbs",		&ng_parse_uint64_type	},	\
+	  { "ebs",		&ng_parse_uint64_type	},	\
+	  { "cir",		&ng_parse_uint64_type	},	\
+	  { "pir",		&ng_parse_uint64_type	},	\
+	  { "greenAction",	&ng_parse_uint8_type	},	\
+	  { "yellowAction",	&ng_parse_uint8_type	},	\
+	  { "redAction",	&ng_parse_uint8_type	},	\
+	  { "mode",		&ng_parse_uint8_type	},	\
+	  { "opt",		&ng_parse_uint8_type	},	\
+	  { NULL }						\
+}
+
+#define NG_CAR_CBS_MIN		8192
+#define NG_CAR_EBS_MIN		8192
+#define NG_CAR_CIR_DFLT		10240
+
+/* possible actions (...Action) */
+enum {
+    NG_CAR_ACTION_FORWARD = 1,
+    NG_CAR_ACTION_DROP,
+    NG_CAR_ACTION_MARK,
+    NG_CAR_ACTION_SET_TOS
+};
+
+/* operation modes (mode) */
+enum {
+    NG_CAR_SINGLE_RATE = 0,
+    NG_CAR_DOUBLE_RATE,
+    NG_CAR_RED,
+    NG_CAR_SHAPE
+};
+
+/* mode options (opt) */
+#define NG_CAR_COLOR_AWARE	1
+
+/* Bulk config */
+struct ng_car_bulkconf {
+	struct ng_car_hookconf upstream;
+	struct ng_car_hookconf downstream;
+};
+#define NG_CAR_BULKCONF(hconftype) {				\
+	  { "upstream",		(hconftype)		},	\
+	  { "downstream",	(hconftype)		},	\
+	  { NULL }						\
+}
+
+/* Commands */
+enum {
+	NGM_CAR_GET_STATS = 1,		/* Get statistics */
+	NGM_CAR_CLR_STATS,		/* Clear statistics */
+	NGM_CAR_GETCLR_STATS,		/* Get and clear statistics */
+	NGM_CAR_GET_CONF,		/* Get bulk configuration */
+	NGM_CAR_SET_CONF,		/* Set bulk configuration */
+};
+
+#endif /* _NETGRAPH_NG_CAR_H_ */