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 */
55struct 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 */
74struct 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};
79typedef struct privdata *priv_p;
80
81static ng_constructor_t	ng_car_constructor;
82static ng_rcvmsg_t	ng_car_rcvmsg;
83static ng_shutdown_t	ng_car_shutdown;
84static ng_newhook_t	ng_car_newhook;
85static ng_rcvdata_t	ng_car_rcvdata;
86static ng_disconnect_t	ng_car_disconnect;
87
88static void	ng_car_refillhook(struct hookinfo *h);
89static void	ng_car_schedule(struct hookinfo *h);
90void		ng_car_q_event(node_p node, hook_p hook, void *arg, int arg2);
91static void	ng_car_enqueue(struct hookinfo *h, item_p item);
92
93/* Parse type for struct ng_car_hookstats */
94static const struct ng_parse_struct_field ng_car_hookstats_type_fields[]
95	= NG_CAR_HOOKSTATS;
96static 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 */
102static const struct ng_parse_struct_field ng_car_bulkstats_type_fields[]
103	= NG_CAR_BULKSTATS(&ng_car_hookstats_type);
104static 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 */
110static const struct ng_parse_struct_field ng_car_hookconf_type_fields[]
111	= NG_CAR_HOOKCONF;
112static 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 */
118static const struct ng_parse_struct_field ng_car_bulkconf_type_fields[]
119	= NG_CAR_BULKCONF(&ng_car_hookconf_type);
120static 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 */
126static 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 */
167static 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};
178NETGRAPH_INIT(car, &ng_car_typestruct);
179
180/*
181 * Node constructor
182 */
183static int
184ng_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 */
234static int
235ng_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 */
257static int
258ng_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 commited 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 commited 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 probaly 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 */
376static int
377ng_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 */
531static int
532ng_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 */
550static int
551ng_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 */
582static void
583ng_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 commited 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 commited 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 commited 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 */
648static void
649ng_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 */
662void
663ng_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 */
709static void
710ng_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