xref: /freebsd-10.2-release/sys/netgraph/ng_pipe.c

/*
 * Copyright (c) 2004-2008 University of Zagreb
 * Copyright (c) 2007-2008 FreeBSD Foundation
 *
 * This software was developed by the University of Zagreb and the
 * FreeBSD Foundation under sponsorship by the Stichting NLnet and the
 * FreeBSD Foundation.
 *
 * 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 THE 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 THE 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: head/sys/netgraph/ng_pipe.c 182734 2008-09-03 18:17:45Z julian $
 */

/*
 * This node permits simple traffic shaping by emulating bandwidth
 * and delay, as well as random packet losses.
 * The node has two hooks, upper and lower. Traffic flowing from upper to
 * lower hook is referenced as downstream, and vice versa. Parameters for
 * both directions can be set separately, except for delay.
 */


#include <sys/param.h>
#include <sys/errno.h>
#include <sys/systm.h>
#include <sys/kernel.h>
#include <sys/malloc.h>
#include <sys/mbuf.h>
#include <sys/time.h>
#include <sys/vimage.h>

#include <vm/uma.h>

#include <netinet/in.h>
#include <netinet/in_systm.h>
#include <netinet/ip.h>

#include <netgraph/ng_message.h>
#include <netgraph/netgraph.h>
#include <netgraph/ng_parse.h>
#include <netgraph/ng_pipe.h>

static MALLOC_DEFINE(M_NG_PIPE, "ng_pipe", "ng_pipe");

struct mtx ng_pipe_giant;

/* Packet header struct */
struct ngp_hdr {
	TAILQ_ENTRY(ngp_hdr)	ngp_link;	/* next pkt in queue */
	struct timeval		when;		/* this packet's due time */
	struct mbuf		*m;		/* ptr to the packet data */
};
TAILQ_HEAD(p_head, ngp_hdr);

/* FIFO queue struct */
struct ngp_fifo {
	TAILQ_ENTRY(ngp_fifo)	fifo_le;	/* list of active queues only */
	struct p_head		packet_head;	/* FIFO queue head */
	u_int32_t		hash;		/* flow signature */
	struct timeval		vtime;		/* virtual time, for WFQ */
	u_int32_t		rr_deficit;	/* for DRR */
	u_int32_t		packets;	/* # of packets in this queue */
};

/* Per hook info */
struct hookinfo {
	hook_p			hook;
	int			noqueue;	/* bypass any processing */
	TAILQ_HEAD(, ngp_fifo)	fifo_head;	/* FIFO queues */
	TAILQ_HEAD(, ngp_hdr)	qout_head;	/* delay queue head */
	LIST_ENTRY(hookinfo)	active_le;	/* active hooks */
	struct timeval		qin_utime;
	struct ng_pipe_hookcfg	cfg;
	struct ng_pipe_hookrun	run;
	struct ng_pipe_hookstat	stats;
	uint64_t		*ber_p;		/* loss_p(BER,psize) map */
};

/* Per node info */
struct node_priv {
	u_int64_t		delay;
	u_int32_t		overhead;
	u_int32_t		header_offset;
	struct hookinfo		lower;
	struct hookinfo		upper;
};
typedef struct node_priv *priv_p;

/* Macro for calculating the virtual time for packet dequeueing in WFQ */
#define FIFO_VTIME_SORT(plen)						\
	if (hinfo->cfg.wfq && hinfo->cfg.bandwidth) {			\
		ngp_f->vtime.tv_usec = now->tv_usec + ((uint64_t) (plen) \
			+ priv->overhead ) * hinfo->run.fifo_queues *	\
			8000000 / hinfo->cfg.bandwidth;			\
		ngp_f->vtime.tv_sec = now->tv_sec +			\
			ngp_f->vtime.tv_usec / 1000000;			\
		ngp_f->vtime.tv_usec = ngp_f->vtime.tv_usec % 1000000;	\
		TAILQ_FOREACH(ngp_f1, &hinfo->fifo_head, fifo_le)	\
			if (ngp_f1->vtime.tv_sec > ngp_f->vtime.tv_sec || \
			    (ngp_f1->vtime.tv_sec == ngp_f->vtime.tv_sec && \
			    ngp_f1->vtime.tv_usec > ngp_f->vtime.tv_usec)) \
				break;					\
		if (ngp_f1 == NULL)					\
			TAILQ_INSERT_TAIL(&hinfo->fifo_head, ngp_f, fifo_le); \
		else							\
			TAILQ_INSERT_BEFORE(ngp_f1, ngp_f, fifo_le);	\
	} else								\
		TAILQ_INSERT_TAIL(&hinfo->fifo_head, ngp_f, fifo_le);	\


static void	parse_cfg(struct ng_pipe_hookcfg *, struct ng_pipe_hookcfg *,
			struct hookinfo *, priv_p);
static void	pipe_dequeue(struct hookinfo *, struct timeval *);
static void	pipe_scheduler(void *);
static void	pipe_poll(void);
static int	ngp_modevent(module_t, int, void *);

/* linked list of active "pipe" hooks */
static LIST_HEAD(, hookinfo) active_head;
static int active_gen_id = 0;

/* timeout handle for pipe_scheduler */
static struct callout polling_timer;

/* zone for storing ngp_hdr-s */
static uma_zone_t ngp_zone;

/* Netgraph methods */
static ng_constructor_t	ngp_constructor;
static ng_rcvmsg_t	ngp_rcvmsg;
static ng_shutdown_t	ngp_shutdown;
static ng_newhook_t	ngp_newhook;
static ng_rcvdata_t	ngp_rcvdata;
static ng_disconnect_t	ngp_disconnect;

/* Parse type for struct ng_pipe_hookstat */
static const struct ng_parse_struct_field
	ng_pipe_hookstat_type_fields[] = NG_PIPE_HOOKSTAT_INFO;
static const struct ng_parse_type ng_pipe_hookstat_type = {
	&ng_parse_struct_type,
	&ng_pipe_hookstat_type_fields
};

/* Parse type for struct ng_pipe_stats */
static const struct ng_parse_struct_field ng_pipe_stats_type_fields[] =
	NG_PIPE_STATS_INFO(&ng_pipe_hookstat_type);
static const struct ng_parse_type ng_pipe_stats_type = {
	&ng_parse_struct_type,
	&ng_pipe_stats_type_fields
};

/* Parse type for struct ng_pipe_hookrun */
static const struct ng_parse_struct_field
	ng_pipe_hookrun_type_fields[] = NG_PIPE_HOOKRUN_INFO;
static const struct ng_parse_type ng_pipe_hookrun_type = {
	&ng_parse_struct_type,
	&ng_pipe_hookrun_type_fields
};

/* Parse type for struct ng_pipe_run */
static const struct ng_parse_struct_field
	ng_pipe_run_type_fields[] = NG_PIPE_RUN_INFO(&ng_pipe_hookrun_type);
static const struct ng_parse_type ng_pipe_run_type = {
	&ng_parse_struct_type,
	&ng_pipe_run_type_fields
};

/* Parse type for struct ng_pipe_hookcfg */
static const struct ng_parse_struct_field
	ng_pipe_hookcfg_type_fields[] = NG_PIPE_HOOKCFG_INFO;
static const struct ng_parse_type ng_pipe_hookcfg_type = {
	&ng_parse_struct_type,
	&ng_pipe_hookcfg_type_fields
};

/* Parse type for struct ng_pipe_cfg */
static const struct ng_parse_struct_field
	ng_pipe_cfg_type_fields[] = NG_PIPE_CFG_INFO(&ng_pipe_hookcfg_type);
static const struct ng_parse_type ng_pipe_cfg_type = {
	&ng_parse_struct_type,
	&ng_pipe_cfg_type_fields
};

/* List of commands and how to convert arguments to/from ASCII */
static const struct ng_cmdlist ngp_cmds[] = {
	{
		.cookie =	NGM_PIPE_COOKIE,
		.cmd =		NGM_PIPE_GET_STATS,
		.name = 	"getstats",
		.respType =	 &ng_pipe_stats_type
	},
	{
		.cookie =	NGM_PIPE_COOKIE,
		.cmd =		NGM_PIPE_CLR_STATS,
		.name =		"clrstats"
	},
	{
		.cookie =	NGM_PIPE_COOKIE,
		.cmd =		NGM_PIPE_GETCLR_STATS,
		.name =		"getclrstats",
		.respType =	&ng_pipe_stats_type
	},
	{
		.cookie =	NGM_PIPE_COOKIE,
		.cmd =		NGM_PIPE_GET_RUN,
		.name =		"getrun",
		.respType =	&ng_pipe_run_type
	},
	{
		.cookie =	NGM_PIPE_COOKIE,
		.cmd =		NGM_PIPE_GET_CFG,
		.name =		"getcfg",
		.respType =	&ng_pipe_cfg_type
	},
	{
		.cookie =	NGM_PIPE_COOKIE,
		.cmd =		NGM_PIPE_SET_CFG,
		.name =		"setcfg",
		.mesgType =	&ng_pipe_cfg_type,
	},
	{ 0 }
};

/* Netgraph type descriptor */
static struct ng_type ng_pipe_typestruct = {
	.version =	NG_ABI_VERSION,
	.name =		NG_PIPE_NODE_TYPE,
	.mod_event =	ngp_modevent,
	.constructor =	ngp_constructor,
	.shutdown =	ngp_shutdown,
	.rcvmsg =	ngp_rcvmsg,
	.newhook =	ngp_newhook,
	.rcvdata =	ngp_rcvdata,
	.disconnect =	ngp_disconnect,
	.cmdlist =	ngp_cmds
};
NETGRAPH_INIT(pipe, &ng_pipe_typestruct);

/* Node constructor */
static int
ngp_constructor(node_p node)
{
	priv_p priv;

	MALLOC(priv, priv_p, sizeof(*priv), M_NG_PIPE, M_ZERO | M_NOWAIT);
	if (priv == NULL)
		return (ENOMEM);
	NG_NODE_SET_PRIVATE(node, priv);

	return (0);
}

/* Add a hook */
static int
ngp_newhook(node_p node, hook_p hook, const char *name)
{
	const priv_p priv = NG_NODE_PRIVATE(node);
	struct hookinfo *hinfo;

	if (strcmp(name, NG_PIPE_HOOK_UPPER) == 0) {
		bzero(&priv->upper, sizeof(priv->upper));
		priv->upper.hook = hook;
		NG_HOOK_SET_PRIVATE(hook, &priv->upper);
	} else if (strcmp(name, NG_PIPE_HOOK_LOWER) == 0) {
		bzero(&priv->lower, sizeof(priv->lower));
		priv->lower.hook = hook;
		NG_HOOK_SET_PRIVATE(hook, &priv->lower);
	} else
		return (EINVAL);

	/* Load non-zero initial cfg values */
	hinfo = NG_HOOK_PRIVATE(hook);
	hinfo->cfg.qin_size_limit = 50;
	hinfo->cfg.fifo = 1;
	hinfo->cfg.droptail = 1;
	TAILQ_INIT(&hinfo->fifo_head);
	TAILQ_INIT(&hinfo->qout_head);
	return (0);
}

/* Receive a control message */
static int
ngp_rcvmsg(node_p node, item_p item, hook_p lasthook)
{
	const priv_p priv = NG_NODE_PRIVATE(node);
	struct ng_mesg *resp = NULL;
	struct ng_mesg *msg;
	struct ng_pipe_stats *stats;
	struct ng_pipe_run *run;
	struct ng_pipe_cfg *cfg;
	int error = 0;

	mtx_lock(&ng_pipe_giant);

	NGI_GET_MSG(item, msg);
	switch (msg->header.typecookie) {
	case NGM_PIPE_COOKIE:
		switch (msg->header.cmd) {
		case NGM_PIPE_GET_STATS:
		case NGM_PIPE_CLR_STATS:
		case NGM_PIPE_GETCLR_STATS:
			if (msg->header.cmd != NGM_PIPE_CLR_STATS) {
				NG_MKRESPONSE(resp, msg,
				    sizeof(*stats), M_NOWAIT);
				if (resp == NULL) {
					error = ENOMEM;
					break;
				}
				stats = (struct ng_pipe_stats *)resp->data;
				bcopy(&priv->upper.stats, &stats->downstream,
				    sizeof(stats->downstream));
				bcopy(&priv->lower.stats, &stats->upstream,
				    sizeof(stats->upstream));
			}
			if (msg->header.cmd != NGM_PIPE_GET_STATS) {
				bzero(&priv->upper.stats,
				    sizeof(priv->upper.stats));
				bzero(&priv->lower.stats,
				    sizeof(priv->lower.stats));
			}
			break;
		case NGM_PIPE_GET_RUN:
			NG_MKRESPONSE(resp, msg, sizeof(*run), M_NOWAIT);
			if (resp == NULL) {
				error = ENOMEM;
				break;
			}
			run = (struct ng_pipe_run *)resp->data;
			bcopy(&priv->upper.run, &run->downstream,
				sizeof(run->downstream));
			bcopy(&priv->lower.run, &run->upstream,
				sizeof(run->upstream));
			break;
		case NGM_PIPE_GET_CFG:
			NG_MKRESPONSE(resp, msg, sizeof(*cfg), M_NOWAIT);
			if (resp == NULL) {
				error = ENOMEM;
				break;
			}
			cfg = (struct ng_pipe_cfg *)resp->data;
			bcopy(&priv->upper.cfg, &cfg->downstream,
				sizeof(cfg->downstream));
			bcopy(&priv->lower.cfg, &cfg->upstream,
				sizeof(cfg->upstream));
			cfg->delay = priv->delay;
			cfg->overhead = priv->overhead;
			cfg->header_offset = priv->header_offset;
			if (cfg->upstream.bandwidth ==
			    cfg->downstream.bandwidth) {
				cfg->bandwidth = cfg->upstream.bandwidth;
				cfg->upstream.bandwidth = 0;
				cfg->downstream.bandwidth = 0;
			} else
				cfg->bandwidth = 0;
			break;
		case NGM_PIPE_SET_CFG:
			cfg = (struct ng_pipe_cfg *)msg->data;
			if (msg->header.arglen != sizeof(*cfg)) {
				error = EINVAL;
				break;
			}

			if (cfg->delay == -1)
				priv->delay = 0;
			else if (cfg->delay > 0 && cfg->delay < 10000000)
				priv->delay = cfg->delay;

			if (cfg->bandwidth == -1) {
				priv->upper.cfg.bandwidth = 0;
				priv->lower.cfg.bandwidth = 0;
				priv->overhead = 0;
			} else if (cfg->bandwidth >= 100 &&
			    cfg->bandwidth <= 1000000000) {
				priv->upper.cfg.bandwidth = cfg->bandwidth;
				priv->lower.cfg.bandwidth = cfg->bandwidth;
				if (cfg->bandwidth >= 10000000)
					priv->overhead = 8+4+12; /* Ethernet */
				else
					priv->overhead = 10; /* HDLC */
			}

			if (cfg->overhead == -1)
				priv->overhead = 0;
			else if (cfg->overhead > 0 && cfg->overhead < 256)
				priv->overhead = cfg->overhead;

			if (cfg->header_offset == -1)
				priv->header_offset = 0;
			else if (cfg->header_offset > 0 &&
			    cfg->header_offset < 64)
				priv->header_offset = cfg->header_offset;

			parse_cfg(&priv->upper.cfg, &cfg->downstream,
				  &priv->upper, priv);
			parse_cfg(&priv->lower.cfg, &cfg->upstream,
				  &priv->lower, priv);
			break;
		default:
			error = EINVAL;
			break;
		}
		break;
	default:
		error = EINVAL;
		break;
	}
	NG_RESPOND_MSG(error, node, item, resp);
	NG_FREE_MSG(msg);

	mtx_unlock(&ng_pipe_giant);

	return (error);
}

static void
parse_cfg(struct ng_pipe_hookcfg *current, struct ng_pipe_hookcfg *new,
	struct hookinfo *hinfo, priv_p priv)
{

	if (new->ber == -1) {
		current->ber = 0;
		if (hinfo->ber_p) {
			FREE(hinfo->ber_p, M_NG_PIPE);
			hinfo->ber_p = NULL;
		}
	} else if (new->ber >= 1 && new->ber <= 1000000000000) {
		static const uint64_t one = 0x1000000000000; /* = 2^48 */
		uint64_t p0, p;
		uint32_t fsize, i;

		if (hinfo->ber_p == NULL)
			MALLOC(hinfo->ber_p, uint64_t *, \
				(MAX_FSIZE + MAX_OHSIZE)*sizeof(uint64_t), \
				M_NG_PIPE, M_NOWAIT);
		current->ber = new->ber;

		/*
		 * For given BER and each frame size N (in bytes) calculate
		 * the probability P_OK that the frame is clean:
		 *
		 * P_OK(BER,N) = (1 - 1/BER)^(N*8)
		 *
		 * We use a 64-bit fixed-point format with decimal point
		 * positioned between bits 47 and 48.
		 */
		p0 = one - one / new->ber;
		p = one;
		for (fsize = 0; fsize < MAX_FSIZE + MAX_OHSIZE; fsize++) {
			hinfo->ber_p[fsize] = p;
			for (i=0; i<8; i++)
				p = (p*(p0&0xffff)>>48) + \
				    (p*((p0>>16)&0xffff)>>32) + \
				    (p*(p0>>32)>>16);
		}
	}

	if (new->qin_size_limit == -1)
		current->qin_size_limit = 0;
	else if (new->qin_size_limit >= 5)
		current->qin_size_limit = new->qin_size_limit;

	if (new->qout_size_limit == -1)
		current->qout_size_limit = 0;
	else if (new->qout_size_limit >= 5)
		current->qout_size_limit = new->qout_size_limit;

	if (new->duplicate == -1)
		current->duplicate = 0;
	else if (new->duplicate > 0 && new->duplicate <= 50)
		current->duplicate = new->duplicate;

	if (new->fifo) {
		current->fifo = 1;
		current->wfq = 0;
		current->drr = 0;
	}

	if (new->wfq) {
		current->fifo = 0;
		current->wfq = 1;
		current->drr = 0;
	}

	if (new->drr) {
		current->fifo = 0;
		current->wfq = 0;
		/* DRR quantum */
		if (new->drr >= 32)
			current->drr = new->drr;
		else
			current->drr = 2048;		/* default quantum */
	}

	if (new->droptail) {
		current->droptail = 1;
		current->drophead = 0;
	}

	if (new->drophead) {
		current->droptail = 0;
		current->drophead = 1;
	}

	if (new->bandwidth == -1) {
		current->bandwidth = 0;
		current->fifo = 1;
		current->wfq = 0;
		current->drr = 0;
	} else if (new->bandwidth >= 100 && new->bandwidth <= 1000000000)
		current->bandwidth = new->bandwidth;

	if (current->bandwidth | priv->delay |
	    current->duplicate | current->ber)
		hinfo->noqueue = 0;
	else
		hinfo->noqueue = 1;
}

/*
 * Compute a hash signature for a packet. This function suffers from the
 * NIH sindrome, so probably it would be wise to look around what other
 * folks have found out to be a good and efficient IP hash function...
 */
static int
ip_hash(struct mbuf *m, int offset)
{
	u_int64_t i;
	struct ip *ip = (struct ip *)(mtod(m, u_char *) + offset);

	if (m->m_len < sizeof(struct ip) + offset ||
	    ip->ip_v != 4 || ip->ip_hl << 2 != sizeof(struct ip))
		return 0;

	i = ((u_int64_t) ip->ip_src.s_addr ^
	    ((u_int64_t) ip->ip_src.s_addr << 13) ^
	    ((u_int64_t) ip->ip_dst.s_addr << 7) ^
	    ((u_int64_t) ip->ip_dst.s_addr << 19));
	return (i ^ (i >> 32));
}

/*
 * Receive data on a hook - both in upstream and downstream direction.
 * We put the frame on the inbound queue, and try to initiate dequeuing
 * sequence immediately. If inbound queue is full, discard one frame
 * depending on dropping policy (from the head or from the tail of the
 * queue).
 */
static int
ngp_rcvdata(hook_p hook, item_p item)
{
	struct hookinfo *const hinfo = NG_HOOK_PRIVATE(hook);
	const priv_p priv = NG_NODE_PRIVATE(NG_HOOK_NODE(hook));
	struct timeval uuptime;
	struct timeval *now = &uuptime;
	struct ngp_fifo *ngp_f = NULL, *ngp_f1;
	struct ngp_hdr *ngp_h = NULL;
	struct mbuf *m;
	int hash;
	int error = 0;

	if (hinfo->noqueue) {
		struct hookinfo *dest;
		if (hinfo == &priv->lower)
			dest = &priv->upper;
		else
			dest = &priv->lower;
		NG_FWD_ITEM_HOOK(error, item, dest->hook);
		return error;
	}

	mtx_lock(&ng_pipe_giant);
	microuptime(now);

	/*
	 * Attach us to the list of active ng_pipes if this was an empty
	 * one before, and also update the queue service deadline time.
	 */
	if (hinfo->run.qin_frames == 0) {
		struct timeval *when = &hinfo->qin_utime;
		if (when->tv_sec < now->tv_sec || (when->tv_sec == now->tv_sec
		    && when->tv_usec < now->tv_usec)) {
			when->tv_sec = now->tv_sec;
			when->tv_usec = now->tv_usec;
		}
		if (hinfo->run.qout_frames == 0)
			LIST_INSERT_HEAD(&active_head, hinfo, active_le);
	}

	/* Populate the packet header */
	ngp_h = uma_zalloc(ngp_zone, M_NOWAIT);
	KASSERT((ngp_h != NULL), ("ngp_h zalloc failed (1)"));
	NGI_GET_M(item, m);
	KASSERT(m != NULL, ("NGI_GET_M failed"));
	ngp_h->m = m;
	NG_FREE_ITEM(item);

	if (hinfo->cfg.fifo)
		hash = 0;	/* all packets go into a single FIFO queue */
	else
		hash = ip_hash(m, priv->header_offset);

	/* Find the appropriate FIFO queue for the packet and enqueue it*/
	TAILQ_FOREACH(ngp_f, &hinfo->fifo_head, fifo_le)
		if (hash == ngp_f->hash)
			break;
	if (ngp_f == NULL) {
		ngp_f = uma_zalloc(ngp_zone, M_NOWAIT);
		KASSERT(ngp_h != NULL, ("ngp_h zalloc failed (2)"));
		TAILQ_INIT(&ngp_f->packet_head);
		ngp_f->hash = hash;
		ngp_f->packets = 1;
		ngp_f->rr_deficit = hinfo->cfg.drr;	/* DRR quantum */
		hinfo->run.fifo_queues++;
		TAILQ_INSERT_TAIL(&ngp_f->packet_head, ngp_h, ngp_link);
		FIFO_VTIME_SORT(m->m_pkthdr.len);
	} else {
		TAILQ_INSERT_TAIL(&ngp_f->packet_head, ngp_h, ngp_link);
		ngp_f->packets++;
	}
	hinfo->run.qin_frames++;
	hinfo->run.qin_octets += m->m_pkthdr.len;

	/* Discard a frame if inbound queue limit has been reached */
	if (hinfo->run.qin_frames > hinfo->cfg.qin_size_limit) {
		struct mbuf *m1;
		int longest = 0;

		/* Find the longest queue */
		TAILQ_FOREACH(ngp_f1, &hinfo->fifo_head, fifo_le)
			if (ngp_f1->packets > longest) {
				longest = ngp_f1->packets;
				ngp_f = ngp_f1;
			}

		/* Drop a frame from the queue head/tail, depending on cfg */
		if (hinfo->cfg.drophead)
			ngp_h = TAILQ_FIRST(&ngp_f->packet_head);
		else
			ngp_h = TAILQ_LAST(&ngp_f->packet_head, p_head);
		TAILQ_REMOVE(&ngp_f->packet_head, ngp_h, ngp_link);
		m1 = ngp_h->m;
		uma_zfree(ngp_zone, ngp_h);
		hinfo->run.qin_octets -= m1->m_pkthdr.len;
		hinfo->stats.in_disc_octets += m1->m_pkthdr.len;
		m_freem(m1);
		if (--(ngp_f->packets) == 0) {
			TAILQ_REMOVE(&hinfo->fifo_head, ngp_f, fifo_le);
			uma_zfree(ngp_zone, ngp_f);
			hinfo->run.fifo_queues--;
		}
		hinfo->run.qin_frames--;
		hinfo->stats.in_disc_frames++;
	} else if (hinfo->run.qin_frames > hinfo->cfg.qin_size_limit) {
		struct mbuf *m1;
		int longest = 0;

		/* Find the longest queue */
		TAILQ_FOREACH(ngp_f1, &hinfo->fifo_head, fifo_le)
			if (ngp_f1->packets > longest) {
				longest = ngp_f1->packets;
				ngp_f = ngp_f1;
			}

		/* Drop a frame from the queue head/tail, depending on cfg */
		if (hinfo->cfg.drophead)
			ngp_h = TAILQ_FIRST(&ngp_f->packet_head);
		else
			ngp_h = TAILQ_LAST(&ngp_f->packet_head, p_head);
		TAILQ_REMOVE(&ngp_f->packet_head, ngp_h, ngp_link);
		m1 = ngp_h->m;
		uma_zfree(ngp_zone, ngp_h);
		hinfo->run.qin_octets -= m1->m_pkthdr.len;
		hinfo->stats.in_disc_octets += m1->m_pkthdr.len;
		m_freem(m1);
		if (--(ngp_f->packets) == 0) {
			TAILQ_REMOVE(&hinfo->fifo_head, ngp_f, fifo_le);
			uma_zfree(ngp_zone, ngp_f);
			hinfo->run.fifo_queues--;
		}
		hinfo->run.qin_frames--;
		hinfo->stats.in_disc_frames++;
	}

	/*
	 * Try to start the dequeuing process immediately.  We must
	 * hold the ng_pipe_giant lock here and pipe_dequeue() will
	 * release it
	 */
	pipe_dequeue(hinfo, now);

	return (0);
}


/*
 * Dequeueing sequence - we basically do the following:
 *  1) Try to extract the frame from the inbound (bandwidth) queue;
 *  2) In accordance to BER specified, discard the frame randomly;
 *  3) If the frame survives BER, prepend it with delay info and move it
 *     to outbound (delay) queue;
 *  4) Loop to 2) until bandwidth quota for this timeslice is reached, or
 *     inbound queue is flushed completely;
 *  5) Extract the first frame from the outbound queue, if it's time has
 *     come.  Queue the frame for transmission on the outbound hook;
 *  6) Loop to 5) until outbound queue is flushed completely, or the next
 *     frame in the queue is not scheduled to be dequeued yet;
 *  7) Transimit all frames queued in 5)
 *
 * Note: the caller must hold the ng_pipe_giant lock; this function
 * returns with the lock released.
 */
static void
pipe_dequeue(struct hookinfo *hinfo, struct timeval *now) {
	static uint64_t rand, oldrand;
	const priv_p priv = NG_NODE_PRIVATE(NG_HOOK_NODE(hinfo->hook));
	struct hookinfo *dest;
	struct ngp_fifo *ngp_f, *ngp_f1;
	struct ngp_hdr *ngp_h;
	struct timeval *when;
	struct mbuf *q_head = NULL;
	struct mbuf *q_tail = NULL;
	struct mbuf *m;
	int error = 0;

	/* Which one is the destination hook? */
	if (hinfo == &priv->lower)
		dest = &priv->upper;
	else
		dest = &priv->lower;

	/* Bandwidth queue processing */
	while ((ngp_f = TAILQ_FIRST(&hinfo->fifo_head))) {
		when = &hinfo->qin_utime;
		if (when->tv_sec > now->tv_sec || (when->tv_sec == now->tv_sec
		    && when->tv_usec > now->tv_usec))
			break;

		ngp_h = TAILQ_FIRST(&ngp_f->packet_head);
		m = ngp_h->m;

		/* Deficit Round Robin (DRR) processing */
		if (hinfo->cfg.drr) {
			if (ngp_f->rr_deficit >= m->m_pkthdr.len) {
				ngp_f->rr_deficit -= m->m_pkthdr.len;
			} else {
				ngp_f->rr_deficit += hinfo->cfg.drr;
				TAILQ_REMOVE(&hinfo->fifo_head, ngp_f, fifo_le);
				TAILQ_INSERT_TAIL(&hinfo->fifo_head,
				    ngp_f, fifo_le);
				continue;
			}
		}

		/*
		 * Either create a duplicate and pass it on, or dequeue
		 * the original packet...
		 */
		if (hinfo->cfg.duplicate &&
		    random() % 100 <= hinfo->cfg.duplicate) {
			ngp_h = uma_zalloc(ngp_zone, M_NOWAIT);
			KASSERT(ngp_h != NULL, ("ngp_h zalloc failed (3)"));
			ngp_h->m = m_dup(m, M_NOWAIT);
			KASSERT(ngp_h->m != NULL, ("m_dup failed"));
		} else {
			TAILQ_REMOVE(&ngp_f->packet_head, ngp_h, ngp_link);
			hinfo->run.qin_frames--;
			hinfo->run.qin_octets -= m->m_pkthdr.len;
			ngp_f->packets--;
		}

		/* Calculate the serialization delay */
		if (hinfo->cfg.bandwidth) {
			hinfo->qin_utime.tv_usec += ((uint64_t) m->m_pkthdr.len
				+ priv->overhead ) *
				8000000 / hinfo->cfg.bandwidth;
			hinfo->qin_utime.tv_sec +=
				hinfo->qin_utime.tv_usec / 1000000;
			hinfo->qin_utime.tv_usec =
				hinfo->qin_utime.tv_usec % 1000000;
		}
		when = &ngp_h->when;
		when->tv_sec = hinfo->qin_utime.tv_sec;
		when->tv_usec = hinfo->qin_utime.tv_usec;

		/* Sort / rearrange inbound queues */
		if (ngp_f->packets) {
			if (hinfo->cfg.wfq) {
				TAILQ_REMOVE(&hinfo->fifo_head, ngp_f, fifo_le);
				FIFO_VTIME_SORT(TAILQ_FIRST(
				    &ngp_f->packet_head)->m->m_pkthdr.len)
			}
		} else {
			TAILQ_REMOVE(&hinfo->fifo_head, ngp_f, fifo_le);
			uma_zfree(ngp_zone, ngp_f);
			hinfo->run.fifo_queues--;
		}

		/* Randomly discard the frame, according to BER setting */
		if (hinfo->cfg.ber &&
		    ((oldrand = rand) ^ (rand = random())<<17) >=
		    hinfo->ber_p[priv->overhead + m->m_pkthdr.len] ) {
			hinfo->stats.out_disc_frames++;
			hinfo->stats.out_disc_octets += m->m_pkthdr.len;
			uma_zfree(ngp_zone, ngp_h);
			m_freem(m);
			continue;
		}

		/* Discard frame if outbound queue size limit exceeded */
		if (hinfo->cfg.qout_size_limit &&
		    hinfo->run.qout_frames>=hinfo->cfg.qout_size_limit) {
			hinfo->stats.out_disc_frames++;
			hinfo->stats.out_disc_octets += m->m_pkthdr.len;
			uma_zfree(ngp_zone, ngp_h);
			m_freem(m);
			continue;
		}

		/* Calculate the propagation delay */
		when->tv_usec += priv->delay;
		when->tv_sec += when->tv_usec / 1000000;
		when->tv_usec = when->tv_usec % 1000000;

		/* Put the frame into the delay queue */
		TAILQ_INSERT_TAIL(&hinfo->qout_head, ngp_h, ngp_link);
		hinfo->run.qout_frames++;
		hinfo->run.qout_octets += m->m_pkthdr.len;
	}

	/* Delay queue processing */
	while ((ngp_h = TAILQ_FIRST(&hinfo->qout_head))) {
		struct mbuf *m = ngp_h->m;

		when = &ngp_h->when;
		if (when->tv_sec > now->tv_sec ||
		    (when->tv_sec == now->tv_sec &&
		    when->tv_usec > now->tv_usec))
			break;

		/* Update outbound queue stats */
		hinfo->stats.fwd_frames++;
		hinfo->stats.fwd_octets += m->m_pkthdr.len;
		hinfo->run.qout_frames--;
		hinfo->run.qout_octets -= m->m_pkthdr.len;

		/* Dequeue the packet from qout */
		TAILQ_REMOVE(&hinfo->qout_head, ngp_h, ngp_link);
		uma_zfree(ngp_zone, ngp_h);

		/* Enqueue locally for sending downstream */
		if (q_head == NULL)
			q_head = m;
		if (q_tail)
			q_tail->m_nextpkt = m;
		q_tail = m;
		m->m_nextpkt = NULL;
	}

	/* If both queues are empty detach us from the list of active queues */
	if (hinfo->run.qin_frames + hinfo->run.qout_frames == 0) {
		LIST_REMOVE(hinfo, active_le);
		active_gen_id++;
	}

	mtx_unlock(&ng_pipe_giant);

	while ((m = q_head) != NULL) {
		q_head = m->m_nextpkt;
		m->m_nextpkt = NULL;
		NG_SEND_DATA(error, dest->hook, m, meta);
	}
}


/*
 * This routine is called on every clock tick. We poll all nodes/hooks
 * for queued frames by calling pipe_dequeue().
 */
static void
pipe_scheduler(void *arg)
{
	pipe_poll();

	/* Reschedule  */
	callout_reset(&polling_timer, 1, &pipe_scheduler, NULL);
}


/*
 * Traverse the list of all active hooks and attempt to dequeue
 * some packets.  Hooks with empty queues are not traversed since
 * they are not linked into this list.
 */
static void
pipe_poll(void)
{
	struct hookinfo *hinfo;
	struct timeval now;
	int old_gen_id = active_gen_id;

	mtx_lock(&ng_pipe_giant);
	microuptime(&now);
	LIST_FOREACH(hinfo, &active_head, active_le) {
		CURVNET_SET(NG_HOOK_NODE(hinfo->hook)->nd_vnet);
		pipe_dequeue(hinfo, &now);
		CURVNET_RESTORE();
		mtx_lock(&ng_pipe_giant);
		if (old_gen_id != active_gen_id) {
			/* the list was updated; restart traversing */
			hinfo = LIST_FIRST(&active_head);
			if (hinfo == NULL)
				break;
			old_gen_id = active_gen_id;
			continue;
		}
	}
	mtx_unlock(&ng_pipe_giant);
}


/*
 * Shutdown processing
 *
 * This is tricky. If we have both a lower and upper hook, then we
 * probably want to extricate ourselves and leave the two peers
 * still linked to each other. Otherwise we should just shut down as
 * a normal node would.
 */
static int
ngp_shutdown(node_p node)
{
	const priv_p priv = NG_NODE_PRIVATE(node);

	if (priv->lower.hook && priv->upper.hook)
		ng_bypass(priv->lower.hook, priv->upper.hook);
	else {
		if (priv->upper.hook != NULL)
			ng_rmhook_self(priv->upper.hook);
		if (priv->lower.hook != NULL)
			ng_rmhook_self(priv->lower.hook);
	}
	NG_NODE_UNREF(node);
	FREE(priv, M_NG_PIPE);
	return (0);
}


/*
 * Hook disconnection
 */
static int
ngp_disconnect(hook_p hook)
{
	struct hookinfo *const hinfo = NG_HOOK_PRIVATE(hook);
	struct ngp_fifo *ngp_f;
	struct ngp_hdr *ngp_h;
	int removed = 0;

	mtx_lock(&ng_pipe_giant);

	KASSERT(hinfo != NULL, ("%s: null info", __FUNCTION__));
	hinfo->hook = NULL;

	/* Flush all fifo queues associated with the hook */
	while ((ngp_f = TAILQ_FIRST(&hinfo->fifo_head))) {
		while ((ngp_h = TAILQ_FIRST(&ngp_f->packet_head))) {
			TAILQ_REMOVE(&ngp_f->packet_head, ngp_h, ngp_link);
			m_freem(ngp_h->m);
			uma_zfree(ngp_zone, ngp_h);
			removed++;
		}
		TAILQ_REMOVE(&hinfo->fifo_head, ngp_f, fifo_le);
		uma_zfree(ngp_zone, ngp_f);
	}

	/* Flush the delay queue */
	while ((ngp_h = TAILQ_FIRST(&hinfo->qout_head))) {
		TAILQ_REMOVE(&hinfo->qout_head, ngp_h, ngp_link);
		m_freem(ngp_h->m);
		uma_zfree(ngp_zone, ngp_h);
		removed++;
	}

	/*
	 * Both queues should be empty by now, so detach us from
	 * the list of active queues
	 */
	if (removed) {
		LIST_REMOVE(hinfo, active_le);
		active_gen_id++;
	}
	if (hinfo->run.qin_frames + hinfo->run.qout_frames != removed)
		printf("Mismatch: queued=%d but removed=%d !?!",
		    hinfo->run.qin_frames + hinfo->run.qout_frames, removed);

	/* Release the packet loss probability table (BER) */
	if (hinfo->ber_p)
		FREE(hinfo->ber_p, M_NG_PIPE);

	mtx_unlock(&ng_pipe_giant);

	return (0);
}

static int
ngp_modevent(module_t mod, int type, void *unused)
{
	int error = 0;

	switch (type) {
	case MOD_LOAD:
		ngp_zone = uma_zcreate("ng_pipe", max(sizeof(struct ngp_hdr),
		    sizeof (struct ngp_fifo)), NULL, NULL, NULL, NULL,
		    UMA_ALIGN_PTR, 0);
		if (ngp_zone == NULL)
			panic("ng_pipe: couldn't allocate descriptor zone");

		mtx_init(&ng_pipe_giant, "ng_pipe_giant", NULL, MTX_DEF);
		LIST_INIT(&active_head);
		callout_init(&polling_timer, CALLOUT_MPSAFE);
		callout_reset(&polling_timer, 1, &pipe_scheduler, NULL);
		break;
	case MOD_UNLOAD:
		callout_drain(&polling_timer);
		uma_zdestroy(ngp_zone);
		mtx_destroy(&ng_pipe_giant);
		break;
	default:
		error = EOPNOTSUPP;
		break;
	}

	return (error);
}