[apple/xnu.git] / bsd / net / classq / classq_blue.c

/*
 * Copyright (c) 2007-2012 Apple Inc. All rights reserved.
 *
 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
 *
 * This file contains Original Code and/or Modifications of Original Code
 * as defined in and that are subject to the Apple Public Source License
 * Version 2.0 (the 'License'). You may not use this file except in
 * compliance with the License. The rights granted to you under the License
 * may not be used to create, or enable the creation or redistribution of,
 * unlawful or unlicensed copies of an Apple operating system, or to
 * circumvent, violate, or enable the circumvention or violation of, any
 * terms of an Apple operating system software license agreement.
 *
 * Please obtain a copy of the License at
 * http://www.opensource.apple.com/apsl/ and read it before using this file.
 *
 * The Original Code and all software distributed under the License are
 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
 * Please see the License for the specific language governing rights and
 * limitations under the License.
 *
 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
 */

/*	$NetBSD: altq_blue.c,v 1.21 2006/11/16 01:32:37 christos Exp $	*/
/*	$KAME: altq_blue.c,v 1.15 2005/04/13 03:44:24 suz Exp $	*/

/*
 * Copyright (C) 1997-2002
 *	Sony Computer Science Laboratories Inc.  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 SONY CSL 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 SONY CSL 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.
 *
 */
/*
 * Copyright (c) 1990-1994 Regents of the University of California.
 * 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.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *	This product includes software developed by the Computer Systems
 *	Engineering Group at Lawrence Berkeley Laboratory.
 * 4. Neither the name of the University nor of the Laboratory may be used
 *    to endorse or promote products derived from this software without
 *    specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS 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 REGENTS 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.
 */

#include <sys/cdefs.h>

#if CLASSQ_BLUE

#include <sys/param.h>
#include <sys/malloc.h>
#include <sys/mbuf.h>
#include <sys/socket.h>
#include <sys/sockio.h>
#include <sys/systm.h>
#include <sys/syslog.h>
#include <sys/proc.h>
#include <sys/errno.h>
#include <sys/kernel.h>
#include <sys/kauth.h>

#include <kern/zalloc.h>

#include <net/if.h>
#include <net/if_var.h>
#include <net/if_types.h>

#include <netinet/in.h>
#include <netinet/in_systm.h>
#include <netinet/ip.h>
#if INET6
#include <netinet/ip6.h>
#endif

#include <net/classq/classq_blue.h>
#include <net/net_osdep.h>
#include <dev/random/randomdev.h>

/*
 * Blue is proposed and implemented by Wu-chang Feng <wuchang@eecs.umich.edu>.
 * more information on Blue is available from
 * http://www.eecs.umich.edu/~wuchang/blue/
 */

#define	BLUE_LIMIT	200		/* default max queue lenght */

#define	BLUE_ZONE_MAX	32		/* maximum elements in zone */
#define	BLUE_ZONE_NAME	"classq_blue"	/* zone name */

static unsigned int blue_size;		/* size of zone element */
static struct zone *blue_zone;		/* zone for blue */

/* internal function prototypes */
static struct mbuf *blue_getq_flow(struct blue *, class_queue_t *,
    u_int32_t, boolean_t);
static int blue_drop_early(struct blue *);

void
blue_init(void)
{
	_CASSERT(BLUEF_ECN4 == CLASSQF_ECN4);
	_CASSERT(BLUEF_ECN6 == CLASSQF_ECN6);

	blue_size = sizeof (struct blue);
	blue_zone = zinit(blue_size, BLUE_ZONE_MAX * blue_size,
	    0, BLUE_ZONE_NAME);
	if (blue_zone == NULL) {
		panic("%s: failed allocating %s", __func__, BLUE_ZONE_NAME);
		/* NOTREACHED */
	}
	zone_change(blue_zone, Z_EXPAND, TRUE);
	zone_change(blue_zone, Z_CALLERACCT, TRUE);
}

/*
 * blue support routines
 */
struct blue *
blue_alloc(struct ifnet *ifp, u_int32_t max_pmark, u_int32_t hold_time,
    u_int32_t flags)
{
	struct blue *bp;

	VERIFY(ifp != NULL);

	bp = zalloc(blue_zone);
	if (bp == NULL)
		return (NULL);

	bzero(bp, blue_size);
	bp->blue_idle = 1;
	bp->blue_ifp = ifp;
	bp->blue_flags = (flags & BLUEF_USERFLAGS);
#if !PF_ECN
	if (bp->blue_flags & BLUEF_ECN) {
		bp->blue_flags &= ~BLUEF_ECN;
		log(LOG_ERR, "%s: BLUE ECN not available; ignoring "
		    "BLUEF_ECN flag!\n", if_name(ifp));
	}
#endif /* !PF_ECN */


	if (max_pmark == 0)
		bp->blue_max_pmark = 1000;
	else
		bp->blue_max_pmark = max_pmark;

	if (hold_time == 0)
		bp->blue_hold_time = 50000;
	else
		bp->blue_hold_time = hold_time;

	microuptime(&bp->blue_last);

	return (bp);
}

void
blue_destroy(struct blue *bp)
{
	zfree(blue_zone, bp);
}

void
blue_getstats(struct blue *bp, struct blue_stats *sp)
{
	sp->q_pmark		= bp->blue_pmark;
	sp->drop_forced		= bp->blue_stats.drop_forced;
	sp->drop_unforced	= bp->blue_stats.drop_unforced;
	sp->marked_packets	= bp->blue_stats.marked_packets;
}

#define	DTYPE_NODROP	0	/* no drop */
#define	DTYPE_FORCED	1	/* a "forced" drop */
#define	DTYPE_EARLY	2	/* an "unforced" (early) drop */

int
blue_addq(struct blue *bp, class_queue_t *q, struct mbuf *m,
    struct pf_mtag *tag)
{
#if !PF_ECN
#pragma unused(tag)
#endif /* !PF_ECN */
	int droptype;

	/*
	 * if we were idle, this is an enqueue onto an empty queue
	 * and we should decrement marking probability
	 */
	if (bp->blue_idle) {
		struct timeval now;
		u_int32_t t;

		bp->blue_idle = 0;
		microuptime(&now);
		t = (now.tv_sec - bp->blue_last.tv_sec);
		if (t > 1) {
			bp->blue_pmark = 1;
			microuptime(&bp->blue_last);
		} else {
			t = t * 1000000 + (now.tv_usec - bp->blue_last.tv_usec);
			if (t > bp->blue_hold_time) {
				bp->blue_pmark--;
				if (bp->blue_pmark < 0)
					bp->blue_pmark = 0;
				microuptime(&bp->blue_last);
			}
		}
	}

	/* see if we drop early */
	droptype = DTYPE_NODROP;
	if (blue_drop_early(bp) && qlen(q) > 1) {
		/* mark or drop by blue */
#if PF_ECN
		if ((bp->blue_flags & BLUEF_ECN) &&
		    (tag->pftag_proto == IPPROTO_TCP) && /* only for TCP */
		    mark_ecn(m, tag, bp->blue_flags)) {
			/* successfully marked.  do not drop. */
			bp->blue_stats.marked_packets++;
		} else
#endif /* PF_ECN */
		{
			/* unforced drop by blue */
			droptype = DTYPE_EARLY;
		}
	}

	/* if the queue length hits the hard limit, it's a forced drop */
	if (droptype == DTYPE_NODROP && qlen(q) >= qlimit(q))
		droptype = DTYPE_FORCED;

	/* if successful or forced drop, enqueue this packet. */
	if (droptype != DTYPE_EARLY)
		_addq(q, m);

	if (droptype != DTYPE_NODROP) {
		if (droptype == DTYPE_EARLY) {
			/* drop the incoming packet */
			bp->blue_stats.drop_unforced++;
		} else {
			struct timeval now;
			u_int32_t t;
			/* forced drop, select a victim packet in the queue. */
			m = _getq_random(q);
			microuptime(&now);
			t = (now.tv_sec - bp->blue_last.tv_sec);
			t = t * 1000000 + (now.tv_usec - bp->blue_last.tv_usec);
			if (t > bp->blue_hold_time) {
				bp->blue_pmark += bp->blue_max_pmark >> 3;
				if (bp->blue_pmark > bp->blue_max_pmark)
					bp->blue_pmark = bp->blue_max_pmark;
				microuptime(&bp->blue_last);
			}
			bp->blue_stats.drop_forced++;
		}
		IFCQ_CONVERT_LOCK(&bp->blue_ifp->if_snd);
		m_freem(m);
		return (CLASSQEQ_DROPPED);
	}
	/* successfully queued */
	return (CLASSQEQ_SUCCESS);
}

static struct mbuf *
blue_getq_flow(struct blue *bp, class_queue_t *q, u_int32_t flow,
    boolean_t purge)
{
#pragma unused(purge)
	struct mbuf *m;

	/* flow of 0 means head of queue */
	if ((m = ((flow == 0) ? _getq(q) : _getq_flow(q, flow))) == NULL) {
		if (bp->blue_idle == 0) {
			bp->blue_idle = 1;
			microuptime(&bp->blue_last);
		}
		return (NULL);
	}

	bp->blue_idle = 0;
	return (m);
}

struct mbuf *
blue_getq(struct blue *bp, class_queue_t *q)
{
	return (blue_getq_flow(bp, q, 0, FALSE));
}

void
blue_purgeq(struct blue *bp, class_queue_t *q, u_int32_t flow,
    u_int32_t *packets, u_int32_t *bytes)
{
	u_int32_t cnt = 0, len = 0;
	struct mbuf *m;

	IFCQ_CONVERT_LOCK(&bp->blue_ifp->if_snd);

	while ((m = blue_getq_flow(bp, q, flow, TRUE)) != NULL) {
		cnt++;
		len += m_pktlen(m);
		m_freem(m);
	}

	if (packets != NULL)
		*packets = cnt;
	if (bytes != NULL)
		*bytes = len;
}

/*
 * early-drop probability is kept in blue_pmark
 */
static int
blue_drop_early(struct blue *bp)
{
	if ((RandomULong() % (unsigned)bp->blue_max_pmark) <
	    (unsigned)bp->blue_pmark) {
		/* drop or mark */
		return (1);
	}
	/* no drop/mark */
	return (0);
}

void
blue_updateq(struct blue *bp, cqev_t ev)
{
#pragma unused(bp, ev)
	/* nothing for now */
}

int
blue_suspendq(struct blue *bp, class_queue_t *q, boolean_t on)
{
#pragma unused(bp, q, on)
	return (ENOTSUP);
}
#endif /* CLASSQ_BLUE */
Commit	Line	Data
316670eb A	1	/*
	2	* Copyright (c) 2007-2012 Apple Inc. All rights reserved.
	3	*
	4	* @APPLE_OSREFERENCE_LICENSE_HEADER_START@
	5	*
	6	* This file contains Original Code and/or Modifications of Original Code
	7	* as defined in and that are subject to the Apple Public Source License
	8	* Version 2.0 (the 'License'). You may not use this file except in
	9	* compliance with the License. The rights granted to you under the License
	10	* may not be used to create, or enable the creation or redistribution of,
	11	* unlawful or unlicensed copies of an Apple operating system, or to
	12	* circumvent, violate, or enable the circumvention or violation of, any
	13	* terms of an Apple operating system software license agreement.
	14	*
	15	* Please obtain a copy of the License at
	16	* http://www.opensource.apple.com/apsl/ and read it before using this file.
	17	*
	18	* The Original Code and all software distributed under the License are
	19	* distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
	20	* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
	21	* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
	22	* FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
	23	* Please see the License for the specific language governing rights and
	24	* limitations under the License.
	25	*
	26	* @APPLE_OSREFERENCE_LICENSE_HEADER_END@
	27	*/
	28
	29	/* $NetBSD: altq_blue.c,v 1.21 2006/11/16 01:32:37 christos Exp $ */
	30	/* $KAME: altq_blue.c,v 1.15 2005/04/13 03:44:24 suz Exp $ */
	31
	32	/*
	33	* Copyright (C) 1997-2002
	34	* Sony Computer Science Laboratories Inc. All rights reserved.
	35	*
	36	* Redistribution and use in source and binary forms, with or without
	37	* modification, are permitted provided that the following conditions
	38	* are met:
	39	* 1. Redistributions of source code must retain the above copyright
	40	* notice, this list of conditions and the following disclaimer.
	41	* 2. Redistributions in binary form must reproduce the above copyright
	42	* notice, this list of conditions and the following disclaimer in the
	43	* documentation and/or other materials provided with the distribution.
	44	*
	45	* THIS SOFTWARE IS PROVIDED BY SONY CSL AND CONTRIBUTORS ``AS IS'' AND
	46	* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	47	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
	48	* ARE DISCLAIMED. IN NO EVENT SHALL SONY CSL OR CONTRIBUTORS BE LIABLE
	49	* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
	50	* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
	51	* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
	52	* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
	53	* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
	54	* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
	55	* SUCH DAMAGE.
	56	*
	57	*/
	58	/*
	59	* Copyright (c) 1990-1994 Regents of the University of California.
	60	* All rights reserved.
	61	*
	62	* Redistribution and use in source and binary forms, with or without
	63	* modification, are permitted provided that the following conditions
	64	* are met:
65	* 1. Redistributions of source code must retain the above copyright
66	* notice, this list of conditions and the following disclaimer.
67	* 2. Redistributions in binary form must reproduce the above copyright
68	* notice, this list of conditions and the following disclaimer in the
69	* documentation and/or other materials provided with the distribution.
70	* 3. All advertising materials mentioning features or use of this software
71	* must display the following acknowledgement:
72	* This product includes software developed by the Computer Systems
73	* Engineering Group at Lawrence Berkeley Laboratory.
74	* 4. Neither the name of the University nor of the Laboratory may be used
75	* to endorse or promote products derived from this software without
76	* specific prior written permission.
77	*
78	* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
79	* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
80	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
81	* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
82	* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
83	* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
84	* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
85	* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
86	* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
87	* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
88	* SUCH DAMAGE.
89	*/
90
91	#include <sys/cdefs.h>
92
93	#if CLASSQ_BLUE
94
95	#include <sys/param.h>
96	#include <sys/malloc.h>
97	#include <sys/mbuf.h>
98	#include <sys/socket.h>
99	#include <sys/sockio.h>
100	#include <sys/systm.h>
39236c6e	101	#include <sys/syslog.h>
316670eb A	102	#include <sys/proc.h>
	103	#include <sys/errno.h>
	104	#include <sys/kernel.h>
	105	#include <sys/kauth.h>
	106
	107	#include <kern/zalloc.h>
	108
	109	#include <net/if.h>
	110	#include <net/if_var.h>
	111	#include <net/if_types.h>
	112
	113	#include <netinet/in.h>
	114	#include <netinet/in_systm.h>
	115	#include <netinet/ip.h>
	116	#if INET6
	117	#include <netinet/ip6.h>
	118	#endif
	119
	120	#include <net/classq/classq_blue.h>
	121	#include <net/net_osdep.h>
39236c6e	122	#include <dev/random/randomdev.h>
316670eb A	123
	124	/*
	125	* Blue is proposed and implemented by Wu-chang Feng <wuchang@eecs.umich.edu>.
	126	* more information on Blue is available from
	127	* http://www.eecs.umich.edu/~wuchang/blue/
	128	*/
	129
	130	#define BLUE_LIMIT 200 /* default max queue lenght */
	131
	132	#define BLUE_ZONE_MAX 32 /* maximum elements in zone */
	133	#define BLUE_ZONE_NAME "classq_blue" /* zone name */
	134
	135	static unsigned int blue_size; /* size of zone element */
	136	static struct zone blue_zone; / zone for blue */
	137
	138	/* internal function prototypes */
	139	static struct mbuf blue_getq_flow(struct blue , class_queue_t *,
	140	u_int32_t, boolean_t);
	141	static int blue_drop_early(struct blue *);
	142
	143	void
	144	blue_init(void)
	145	{
	146	_CASSERT(BLUEF_ECN4 == CLASSQF_ECN4);
	147	_CASSERT(BLUEF_ECN6 == CLASSQF_ECN6);
	148
	149	blue_size = sizeof (struct blue);
	150	blue_zone = zinit(blue_size, BLUE_ZONE_MAX * blue_size,
	151	0, BLUE_ZONE_NAME);
	152	if (blue_zone == NULL) {
	153	panic("%s: failed allocating %s", __func__, BLUE_ZONE_NAME);
	154	/* NOTREACHED */
	155	}
	156	zone_change(blue_zone, Z_EXPAND, TRUE);
	157	zone_change(blue_zone, Z_CALLERACCT, TRUE);
	158	}
	159
	160	/*
	161	* blue support routines
	162	*/
	163	struct blue *
	164	blue_alloc(struct ifnet *ifp, u_int32_t max_pmark, u_int32_t hold_time,
	165	u_int32_t flags)
	166	{
	167	struct blue *bp;
	168
	169	VERIFY(ifp != NULL);
	170
	171	bp = zalloc(blue_zone);
	172	if (bp == NULL)
	173	return (NULL);
	174
	175	bzero(bp, blue_size);
	176	bp->blue_idle = 1;
316670eb	177	bp->blue_ifp = ifp;
39236c6e A	178	bp->blue_flags = (flags & BLUEF_USERFLAGS);
	179	#if !PF_ECN
	180	if (bp->blue_flags & BLUEF_ECN) {
	181	bp->blue_flags &= ~BLUEF_ECN;
	182	log(LOG_ERR, "%s: BLUE ECN not available; ignoring "
	183	"BLUEF_ECN flag!\n", if_name(ifp));
	184	}
	185	#endif /* !PF_ECN */
	186
316670eb A	187
	188	if (max_pmark == 0)
	189	bp->blue_max_pmark = 1000;
	190	else
	191	bp->blue_max_pmark = max_pmark;
	192
	193	if (hold_time == 0)
	194	bp->blue_hold_time = 50000;
	195	else
	196	bp->blue_hold_time = hold_time;
	197
	198	microuptime(&bp->blue_last);
	199
	200	return (bp);
	201	}
	202
	203	void
	204	blue_destroy(struct blue *bp)
	205	{
	206	zfree(blue_zone, bp);
	207	}
	208
	209	void
	210	blue_getstats(struct blue bp, struct blue_stats sp)
	211	{
	212	sp->q_pmark = bp->blue_pmark;
	213	sp->drop_forced = bp->blue_stats.drop_forced;
	214	sp->drop_unforced = bp->blue_stats.drop_unforced;
	215	sp->marked_packets = bp->blue_stats.marked_packets;
	216	}
	217
	218	#define DTYPE_NODROP 0 /* no drop */
	219	#define DTYPE_FORCED 1 /* a "forced" drop */
	220	#define DTYPE_EARLY 2 /* an "unforced" (early) drop */
	221
	222	int
	223	blue_addq(struct blue bp, class_queue_t q, struct mbuf *m,
	224	struct pf_mtag *tag)
	225	{
39236c6e A	226	#if !PF_ECN
	227	#pragma unused(tag)
	228	#endif /* !PF_ECN */
316670eb A	229	int droptype;
	230
	231	/*
	232	* if we were idle, this is an enqueue onto an empty queue
	233	* and we should decrement marking probability
	234	*/
	235	if (bp->blue_idle) {
	236	struct timeval now;
	237	u_int32_t t;
	238
	239	bp->blue_idle = 0;
	240	microuptime(&now);
	241	t = (now.tv_sec - bp->blue_last.tv_sec);
	242	if (t > 1) {
	243	bp->blue_pmark = 1;
	244	microuptime(&bp->blue_last);
	245	} else {
	246	t = t * 1000000 + (now.tv_usec - bp->blue_last.tv_usec);
	247	if (t > bp->blue_hold_time) {
	248	bp->blue_pmark--;
	249	if (bp->blue_pmark < 0)
	250	bp->blue_pmark = 0;
	251	microuptime(&bp->blue_last);
	252	}
	253	}
	254	}
	255
	256	/* see if we drop early */
	257	droptype = DTYPE_NODROP;
	258	if (blue_drop_early(bp) && qlen(q) > 1) {
	259	/* mark or drop by blue */
39236c6e	260	#if PF_ECN
316670eb	261	if ((bp->blue_flags & BLUEF_ECN) &&
39236c6e	262	(tag->pftag_proto == IPPROTO_TCP) && /* only for TCP */
316670eb A	263	mark_ecn(m, tag, bp->blue_flags)) {
	264	/* successfully marked. do not drop. */
	265	bp->blue_stats.marked_packets++;
39236c6e A	266	} else
	267	#endif /* PF_ECN */
	268	{
316670eb A	269	/* unforced drop by blue */
	270	droptype = DTYPE_EARLY;
	271	}
	272	}
	273
	274	/* if the queue length hits the hard limit, it's a forced drop */
	275	if (droptype == DTYPE_NODROP && qlen(q) >= qlimit(q))
	276	droptype = DTYPE_FORCED;
	277
	278	/* if successful or forced drop, enqueue this packet. */
	279	if (droptype != DTYPE_EARLY)
	280	_addq(q, m);
	281
	282	if (droptype != DTYPE_NODROP) {
	283	if (droptype == DTYPE_EARLY) {
	284	/* drop the incoming packet */
	285	bp->blue_stats.drop_unforced++;
	286	} else {
	287	struct timeval now;
	288	u_int32_t t;
	289	/* forced drop, select a victim packet in the queue. */
	290	m = _getq_random(q);
	291	microuptime(&now);
	292	t = (now.tv_sec - bp->blue_last.tv_sec);
	293	t = t * 1000000 + (now.tv_usec - bp->blue_last.tv_usec);
	294	if (t > bp->blue_hold_time) {
	295	bp->blue_pmark += bp->blue_max_pmark >> 3;
	296	if (bp->blue_pmark > bp->blue_max_pmark)
	297	bp->blue_pmark = bp->blue_max_pmark;
	298	microuptime(&bp->blue_last);
	299	}
	300	bp->blue_stats.drop_forced++;
	301	}
	302	IFCQ_CONVERT_LOCK(&bp->blue_ifp->if_snd);
	303	m_freem(m);
	304	return (CLASSQEQ_DROPPED);
	305	}
	306	/* successfully queued */
	307	return (CLASSQEQ_SUCCESS);
	308	}
	309
	310	static struct mbuf *
	311	blue_getq_flow(struct blue bp, class_queue_t q, u_int32_t flow,
	312	boolean_t purge)
	313	{
	314	#pragma unused(purge)
	315	struct mbuf *m;
	316
	317	/* flow of 0 means head of queue */
	318	if ((m = ((flow == 0) ? _getq(q) : _getq_flow(q, flow))) == NULL) {
	319	if (bp->blue_idle == 0) {
	320	bp->blue_idle = 1;
	321	microuptime(&bp->blue_last);
	322	}
	323	return (NULL);
	324	}
	325
	326	bp->blue_idle = 0;
	327	return (m);
	328	}
	329
	330	struct mbuf *
	331	blue_getq(struct blue bp, class_queue_t q)
	332	{
333	return (blue_getq_flow(bp, q, 0, FALSE));
334	}
335
336	void
337	blue_purgeq(struct blue bp, class_queue_t q, u_int32_t flow,
338	u_int32_t packets, u_int32_t bytes)
339	{
340	u_int32_t cnt = 0, len = 0;
341	struct mbuf *m;
342
343	IFCQ_CONVERT_LOCK(&bp->blue_ifp->if_snd);
344
345	while ((m = blue_getq_flow(bp, q, flow, TRUE)) != NULL) {
346	cnt++;
347	len += m_pktlen(m);
348	m_freem(m);
349	}
350
351	if (packets != NULL)
352	*packets = cnt;
353	if (bytes != NULL)
354	*bytes = len;
355	}
356
357	/*
358	* early-drop probability is kept in blue_pmark
359	*/
360	static int
361	blue_drop_early(struct blue *bp)
362	{
39236c6e	363	if ((RandomULong() % (unsigned)bp->blue_max_pmark) <
316670eb A	364	(unsigned)bp->blue_pmark) {
	365	/* drop or mark */
	366	return (1);
	367	}
	368	/* no drop/mark */
	369	return (0);
	370	}
	371
	372	void
	373	blue_updateq(struct blue *bp, cqev_t ev)
	374	{
	375	#pragma unused(bp, ev)
	376	/* nothing for now */
	377	}
	378
	379	int
	380	blue_suspendq(struct blue bp, class_queue_t q, boolean_t on)
	381	{
	382	#pragma unused(bp, q, on)
	383	return (ENOTSUP);
	384	}
	385	#endif /* CLASSQ_BLUE */