[apple/xnu.git] / bsd / netinet / ip_flow.c

/*
 * Copyright (c) 2000-2008 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@
 */
/*-
 * Copyright (c) 1998 The NetBSD Foundation, Inc.
 * All rights reserved.
 *
 * This code is derived from software contributed to The NetBSD Foundation
 * by the 3am Software Foundry ("3am").  It was developed by Matt Thomas.
 *
 * 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 NetBSD
 *	Foundation, Inc. and its contributors.
 * 4. Neither the name of The NetBSD Foundation nor the names of its
 *    contributors may be used to endorse or promote products derived
 *    from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. 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 FOUNDATION 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: src/sys/netinet/ip_flow.c,v 1.9.2.1 2001/08/08 08:20:35 ru Exp $
 */

#include <sys/param.h>
#include <sys/systm.h>
#include <sys/malloc.h>
#include <sys/mbuf.h>
#include <sys/protosw.h>
#include <sys/socket.h>
#include <sys/kernel.h>

#include <sys/sysctl.h>
#include <libkern/OSAtomic.h>

#include <net/if.h>
#include <net/route.h>

#include <netinet/in.h>
#include <netinet/in_systm.h>
#include <netinet/ip.h>
#include <netinet/in_var.h>
#include <netinet/ip_var.h>
#include <netinet/ip_flow.h>
#include <net/dlil.h>

#if IPFLOW

#define	IPFLOW_TIMER		(5 * PR_SLOWHZ)
#define IPFLOW_HASHBITS		6	/* should not be a multiple of 8 */
#define	IPFLOW_HASHSIZE		(1 << IPFLOW_HASHBITS)
static LIST_HEAD(ipflowhead, ipflow) ipflows[IPFLOW_HASHSIZE];
static int ipflow_inuse;
#define	IPFLOW_MAX		256

#ifdef __APPLE__
#define M_IPFLOW M_TEMP
#endif

static int ipflow_active = 0;
SYSCTL_INT(_net_inet_ip, IPCTL_FASTFORWARDING, fastforwarding, CTLFLAG_RW,
    &ipflow_active, 0, "Enable flow-based IP forwarding");

#ifndef __APPLE__
static MALLOC_DEFINE(M_IPFLOW, "ip_flow", "IP flow");
#endif

static unsigned
ipflow_hash(
	struct in_addr dst,
	struct in_addr src,
	unsigned tos)
{
	unsigned hash = tos;
	int idx;
	for (idx = 0; idx < 32; idx += IPFLOW_HASHBITS)
		hash += (dst.s_addr >> (32 - idx)) + (src.s_addr >> idx);
	return hash & (IPFLOW_HASHSIZE-1);
}

static struct ipflow *
ipflow_lookup(
	const struct ip *ip)
{
	unsigned hash;
	struct ipflow *ipf;

	hash = ipflow_hash(ip->ip_dst, ip->ip_src, ip->ip_tos);

	ipf = LIST_FIRST(&ipflows[hash]);
	while (ipf != NULL) {
		if (ip->ip_dst.s_addr == ipf->ipf_dst.s_addr
		    && ip->ip_src.s_addr == ipf->ipf_src.s_addr
		    && ip->ip_tos == ipf->ipf_tos)
			break;
		ipf = LIST_NEXT(ipf, ipf_next);
	}
	return ipf;
}

int
ipflow_fastforward(
	struct mbuf *m)
{
	struct ip *ip;
	struct ipflow *ipf;
	struct rtentry *rt;
	struct sockaddr *dst;
	int error;

	/*
	 * Are we forwarding packets?  Big enough for an IP packet?
	 */
	if (!ipforwarding || !ipflow_active || m->m_len < sizeof(struct ip))
		return 0;
	/*
	 * IP header with no option and valid version and length
	 */
	ip = mtod(m, struct ip *);
	if (ip->ip_v != IPVERSION || ip->ip_hl != (sizeof(struct ip) >> 2)
	    || ntohs(ip->ip_len) > m->m_pkthdr.len)
		return 0;
	/*
	 * Find a flow.
	 */
	if ((ipf = ipflow_lookup(ip)) == NULL)
		return 0;

	/*
	 * Route and interface still up?
	 */
	rt = ipf->ipf_ro.ro_rt;
	if ((rt->rt_flags & RTF_UP) == 0 || (rt->rt_ifp->if_flags & IFF_UP) == 0)
		return 0;

	/*
	 * Packet size OK?  TTL?
	 */
	if (m->m_pkthdr.len > rt->rt_ifp->if_mtu || ip->ip_ttl <= IPTTLDEC)
		return 0;

	/*
	 * Everything checks out and so we can forward this packet.
	 * Modify the TTL and incrementally change the checksum.
	 */
	ip->ip_ttl -= IPTTLDEC;
	if (ip->ip_sum >= htons(0xffff - (IPTTLDEC << 8))) {
		ip->ip_sum += htons(IPTTLDEC << 8) + 1;
	} else {
		ip->ip_sum += htons(IPTTLDEC << 8);
	}

	/*
	 * Send the packet on its way.  All we can get back is ENOBUFS
	 */
	ipf->ipf_uses++;
	ipf->ipf_timer = IPFLOW_TIMER;

	if (rt->rt_flags & RTF_GATEWAY)
		dst = rt->rt_gateway;
	else
		dst = &ipf->ipf_ro.ro_dst;
#ifdef __APPLE__
	/* Not sure the rt_dlt is valid here !! XXX */
	if ((error = dlil_output(rt->rt_ifp, PF_INET, m, (caddr_t) rt, dst, 0)) != 0) {

#else
	if ((error = (*rt->rt_ifp->if_output)(rt->rt_ifp, m, dst, rt)) != 0) {
#endif
		if (error == ENOBUFS)
			ipf->ipf_dropped++;
		else
			ipf->ipf_errors++;
	}
	return 1;
}
\f
static void
ipflow_addstats(
	struct ipflow *ipf)
{
	ipf->ipf_ro.ro_rt->rt_use += ipf->ipf_uses;
	OSAddAtomic(ipf->ipf_errors + ipf->ipf_dropped, &ipstat.ips_cantforward);
	OSAddAtomic(ipf->ipf_uses, &ipstat.ips_forward);
	OSAddAtomic(ipf->ipf_uses, &ipstat.ips_fastforward);
}

static void
ipflow_free(
	struct ipflow *ipf)
{
	/*
	 * Remove the flow from the hash table (at elevated IPL).
	 * Once it's off the list, we can deal with it at normal
	 * network IPL.
	 */
	LIST_REMOVE(ipf, ipf_next);
	ipflow_addstats(ipf);
	rtfree(ipf->ipf_ro.ro_rt);
	ipflow_inuse--;
	FREE(ipf, M_IPFLOW);
}

static struct ipflow *
ipflow_reap(
	void)
{
	struct ipflow *ipf, *maybe_ipf = NULL;
	int idx;

	for (idx = 0; idx < IPFLOW_HASHSIZE; idx++) {
		ipf = LIST_FIRST(&ipflows[idx]);
		while (ipf != NULL) {
			/*
			 * If this no longer points to a valid route
			 * reclaim it.
			 */
			if ((ipf->ipf_ro.ro_rt->rt_flags & RTF_UP) == 0)
				goto done;
			/*
			 * choose the one that's been least recently used
			 * or has had the least uses in the last 1.5 
			 * intervals.
			 */
			if (maybe_ipf == NULL
			    || ipf->ipf_timer < maybe_ipf->ipf_timer
			    || (ipf->ipf_timer == maybe_ipf->ipf_timer
				&& ipf->ipf_last_uses + ipf->ipf_uses <
				      maybe_ipf->ipf_last_uses +
					maybe_ipf->ipf_uses))
				maybe_ipf = ipf;
			ipf = LIST_NEXT(ipf, ipf_next);
		}
	}
	ipf = maybe_ipf;
    done:
	/*
	 * Remove the entry from the flow table.
	 */
	LIST_REMOVE(ipf, ipf_next);
	ipflow_addstats(ipf);
	rtfree(ipf->ipf_ro.ro_rt);
	return ipf;
}
/* note: called under the ip_mutex lock */
void
ipflow_slowtimo(
	void)
{
	struct ipflow *ipf;
	int idx;

	for (idx = 0; idx < IPFLOW_HASHSIZE; idx++) {
		ipf = LIST_FIRST(&ipflows[idx]);
		while (ipf != NULL) {
			struct ipflow *next_ipf = LIST_NEXT(ipf, ipf_next);
			if (--ipf->ipf_timer == 0) {
				ipflow_free(ipf);
			} else {
				ipf->ipf_last_uses = ipf->ipf_uses;
				ipf->ipf_ro.ro_rt->rt_use += ipf->ipf_uses;
				OSAddAtomic(ipf->ipf_uses, &ipstat.ips_forward);
				OSAddAtomic(ipf->ipf_uses, &ipstat.ips_fastforward);
				ipstat.ips_forward += ipf->ipf_uses;
				ipstat.ips_fastforward += ipf->ipf_uses;
				ipf->ipf_uses = 0;
			}
			ipf = next_ipf;
		}
	}
}

void
ipflow_create(
	const struct route *ro,
	struct mbuf *m)
{
	const struct ip *const ip = mtod(m, struct ip *);
	struct ipflow *ipf;
	unsigned hash;

	/*
	 * Don't create cache entries for ICMP messages.
	 */
	if (!ipflow_active || ip->ip_p == IPPROTO_ICMP)
		return;
	/*
	 * See if an existing flow struct exists.  If so remove it from it's
	 * list and free the old route.  If not, try to malloc a new one
	 * (if we aren't at our limit).
	 */
	ipf = ipflow_lookup(ip);
	if (ipf == NULL) {
		if (ipflow_inuse == IPFLOW_MAX) {
			ipf = ipflow_reap();
		} else {
			ipf = (struct ipflow *) _MALLOC(sizeof(*ipf), M_IPFLOW,
						       M_NOWAIT);
			if (ipf == NULL)
				return;
			ipflow_inuse++;
		}
		bzero((caddr_t) ipf, sizeof(*ipf));
	} else {
		LIST_REMOVE(ipf, ipf_next);
		ipflow_addstats(ipf);
		rtfree(ipf->ipf_ro.ro_rt);
		ipf->ipf_uses = ipf->ipf_last_uses = 0;
		ipf->ipf_errors = ipf->ipf_dropped = 0;
	}

	/*
	 * Fill in the updated information.
	 */
	ipf->ipf_ro = *ro;
	RT_ADDREF(ro->ro_rt);
	ipf->ipf_dst = ip->ip_dst;
	ipf->ipf_src = ip->ip_src;
	ipf->ipf_tos = ip->ip_tos;
	ipf->ipf_timer = IPFLOW_TIMER;
	/*
	 * Insert into the approriate bucket of the flow table.
	 */
	hash = ipflow_hash(ip->ip_dst, ip->ip_src, ip->ip_tos);
	LIST_INSERT_HEAD(&ipflows[hash], ipf, ipf_next);
}
#else /* !IPFLOW */
int
ipflow_fastforward(struct mbuf *m)
{
#pragma unused(m)
	/*
	 * Since this symbol is exported (albeit unsupported), just return
	 * false to keep things (e.g. PPP) happy, in case ipflow is not
	 * compiled in.
	 */
	return (0);
}
#endif /* !IPFLOW */
Commit	Line	Data
1c79356b	1	/*
b0d623f7	2	* Copyright (c) 2000-2008 Apple Inc. All rights reserved.
5d5c5d0d	3	*
2d21ac55	4	* @APPLE_OSREFERENCE_LICENSE_HEADER_START@
1c79356b	5	*
2d21ac55 A	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.
8f6c56a5	14	*
2d21ac55 A	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
8f6c56a5 A	20	* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
8f6c56a5 A	21	* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
2d21ac55 A	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.
8f6c56a5	25	*
2d21ac55	26	* @APPLE_OSREFERENCE_LICENSE_HEADER_END@
1c79356b A	27	*/
	28	/*-
	29	* Copyright (c) 1998 The NetBSD Foundation, Inc.
	30	* All rights reserved.
	31	*
	32	* This code is derived from software contributed to The NetBSD Foundation
	33	* by the 3am Software Foundry ("3am"). It was developed by Matt Thomas.
	34	*
	35	* Redistribution and use in source and binary forms, with or without
	36	* modification, are permitted provided that the following conditions
	37	* are met:
	38	* 1. Redistributions of source code must retain the above copyright
	39	* notice, this list of conditions and the following disclaimer.
	40	* 2. Redistributions in binary form must reproduce the above copyright
	41	* notice, this list of conditions and the following disclaimer in the
	42	* documentation and/or other materials provided with the distribution.
	43	* 3. All advertising materials mentioning features or use of this software
	44	* must display the following acknowledgement:
	45	* This product includes software developed by the NetBSD
	46	* Foundation, Inc. and its contributors.
	47	* 4. Neither the name of The NetBSD Foundation nor the names of its
	48	* contributors may be used to endorse or promote products derived
	49	* from this software without specific prior written permission.
	50	*
	51	* THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
	52	* ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
	53	* TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
	54	* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
	55	* BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
	56	* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
	57	* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
	58	* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
	59	* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
	60	* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
	61	* POSSIBILITY OF SUCH DAMAGE.
	62	*
9bccf70c	63	* $FreeBSD: src/sys/netinet/ip_flow.c,v 1.9.2.1 2001/08/08 08:20:35 ru Exp $
1c79356b A	64	*/
	65
	66	#include <sys/param.h>
	67	#include <sys/systm.h>
	68	#include <sys/malloc.h>
	69	#include <sys/mbuf.h>
	70	#include <sys/protosw.h>
	71	#include <sys/socket.h>
	72	#include <sys/kernel.h>
	73
	74	#include <sys/sysctl.h>
2d21ac55	75	#include <libkern/OSAtomic.h>
1c79356b A	76
	77	#include <net/if.h>
	78	#include <net/route.h>
	79
	80	#include <netinet/in.h>
	81	#include <netinet/in_systm.h>
	82	#include <netinet/ip.h>
	83	#include <netinet/in_var.h>
	84	#include <netinet/ip_var.h>
	85	#include <netinet/ip_flow.h>
	86	#include <net/dlil.h>
	87
b0d623f7 A	88	#if IPFLOW
b0d623f7 A	89
1c79356b A	90	#define IPFLOW_TIMER (5 * PR_SLOWHZ)
	91	#define IPFLOW_HASHBITS 6 /* should not be a multiple of 8 */
	92	#define IPFLOW_HASHSIZE (1 << IPFLOW_HASHBITS)
	93	static LIST_HEAD(ipflowhead, ipflow) ipflows[IPFLOW_HASHSIZE];
	94	static int ipflow_inuse;
	95	#define IPFLOW_MAX 256
	96
9bccf70c	97	#ifdef __APPLE__
1c79356b A	98	#define M_IPFLOW M_TEMP
	99	#endif
	100
	101	static int ipflow_active = 0;
	102	SYSCTL_INT(_net_inet_ip, IPCTL_FASTFORWARDING, fastforwarding, CTLFLAG_RW,
9bccf70c	103	&ipflow_active, 0, "Enable flow-based IP forwarding");
1c79356b	104
9bccf70c A	105	#ifndef __APPLE__
	106	static MALLOC_DEFINE(M_IPFLOW, "ip_flow", "IP flow");
	107	#endif
1c79356b A	108
	109	static unsigned
	110	ipflow_hash(
	111	struct in_addr dst,
	112	struct in_addr src,
	113	unsigned tos)
	114	{
	115	unsigned hash = tos;
	116	int idx;
	117	for (idx = 0; idx < 32; idx += IPFLOW_HASHBITS)
	118	hash += (dst.s_addr >> (32 - idx)) + (src.s_addr >> idx);
	119	return hash & (IPFLOW_HASHSIZE-1);
	120	}
	121
	122	static struct ipflow *
	123	ipflow_lookup(
	124	const struct ip *ip)
	125	{
	126	unsigned hash;
	127	struct ipflow *ipf;
	128
	129	hash = ipflow_hash(ip->ip_dst, ip->ip_src, ip->ip_tos);
	130
	131	ipf = LIST_FIRST(&ipflows[hash]);
	132	while (ipf != NULL) {
	133	if (ip->ip_dst.s_addr == ipf->ipf_dst.s_addr
	134	&& ip->ip_src.s_addr == ipf->ipf_src.s_addr
	135	&& ip->ip_tos == ipf->ipf_tos)
	136	break;
	137	ipf = LIST_NEXT(ipf, ipf_next);
	138	}
	139	return ipf;
	140	}
	141
	142	int
	143	ipflow_fastforward(
	144	struct mbuf *m)
	145	{
	146	struct ip *ip;
	147	struct ipflow *ipf;
	148	struct rtentry *rt;
9bccf70c	149	struct sockaddr *dst;
1c79356b A	150	int error;
	151
	152	/*
	153	* Are we forwarding packets? Big enough for an IP packet?
	154	*/
	155	if (!ipforwarding \|\| !ipflow_active \|\| m->m_len < sizeof(struct ip))
	156	return 0;
	157	/*
	158	* IP header with no option and valid version and length
	159	*/
	160	ip = mtod(m, struct ip *);
	161	if (ip->ip_v != IPVERSION \|\| ip->ip_hl != (sizeof(struct ip) >> 2)
	162	\|\| ntohs(ip->ip_len) > m->m_pkthdr.len)
	163	return 0;
	164	/*
	165	* Find a flow.
	166	*/
	167	if ((ipf = ipflow_lookup(ip)) == NULL)
	168	return 0;
	169
	170	/*
	171	* Route and interface still up?
	172	*/
	173	rt = ipf->ipf_ro.ro_rt;
	174	if ((rt->rt_flags & RTF_UP) == 0 \|\| (rt->rt_ifp->if_flags & IFF_UP) == 0)
	175	return 0;
	176
	177	/*
	178	* Packet size OK? TTL?
	179	*/
	180	if (m->m_pkthdr.len > rt->rt_ifp->if_mtu \|\| ip->ip_ttl <= IPTTLDEC)
	181	return 0;
	182
	183	/*
	184	* Everything checks out and so we can forward this packet.
	185	* Modify the TTL and incrementally change the checksum.
	186	*/
	187	ip->ip_ttl -= IPTTLDEC;
	188	if (ip->ip_sum >= htons(0xffff - (IPTTLDEC << 8))) {
	189	ip->ip_sum += htons(IPTTLDEC << 8) + 1;
	190	} else {
	191	ip->ip_sum += htons(IPTTLDEC << 8);
	192	}
	193
	194	/*
	195	* Send the packet on its way. All we can get back is ENOBUFS
	196	*/
	197	ipf->ipf_uses++;
	198	ipf->ipf_timer = IPFLOW_TIMER;
	199
9bccf70c A	200	if (rt->rt_flags & RTF_GATEWAY)
	201	dst = rt->rt_gateway;
	202	else
	203	dst = &ipf->ipf_ro.ro_dst;
	204	#ifdef __APPLE__
1c79356b	205	/* Not sure the rt_dlt is valid here !! XXX */
91447636	206	if ((error = dlil_output(rt->rt_ifp, PF_INET, m, (caddr_t) rt, dst, 0)) != 0) {
9bccf70c A	207
	208	#else
	209	if ((error = (*rt->rt_ifp->if_output)(rt->rt_ifp, m, dst, rt)) != 0) {
	210	#endif
1c79356b A	211	if (error == ENOBUFS)
	212	ipf->ipf_dropped++;
	213	else
	214	ipf->ipf_errors++;
	215	}
	216	return 1;
	217	}
	218	\f
	219	static void
	220	ipflow_addstats(
	221	struct ipflow *ipf)
	222	{
	223	ipf->ipf_ro.ro_rt->rt_use += ipf->ipf_uses;
b0d623f7 A	224	OSAddAtomic(ipf->ipf_errors + ipf->ipf_dropped, &ipstat.ips_cantforward);
	225	OSAddAtomic(ipf->ipf_uses, &ipstat.ips_forward);
	226	OSAddAtomic(ipf->ipf_uses, &ipstat.ips_fastforward);
1c79356b A	227	}
	228
	229	static void
	230	ipflow_free(
	231	struct ipflow *ipf)
	232	{
1c79356b A	233	/*
	234	* Remove the flow from the hash table (at elevated IPL).
	235	* Once it's off the list, we can deal with it at normal
	236	* network IPL.
	237	*/
1c79356b	238	LIST_REMOVE(ipf, ipf_next);
1c79356b	239	ipflow_addstats(ipf);
9bccf70c	240	rtfree(ipf->ipf_ro.ro_rt);
1c79356b A	241	ipflow_inuse--;
	242	FREE(ipf, M_IPFLOW);
	243	}
	244
	245	static struct ipflow *
	246	ipflow_reap(
	247	void)
	248	{
	249	struct ipflow ipf, maybe_ipf = NULL;
	250	int idx;
1c79356b A	251
	252	for (idx = 0; idx < IPFLOW_HASHSIZE; idx++) {
	253	ipf = LIST_FIRST(&ipflows[idx]);
	254	while (ipf != NULL) {
	255	/*
	256	* If this no longer points to a valid route
	257	* reclaim it.
	258	*/
	259	if ((ipf->ipf_ro.ro_rt->rt_flags & RTF_UP) == 0)
	260	goto done;
	261	/*
	262	* choose the one that's been least recently used
	263	* or has had the least uses in the last 1.5
	264	* intervals.
	265	*/
	266	if (maybe_ipf == NULL
	267	\|\| ipf->ipf_timer < maybe_ipf->ipf_timer
	268	\|\| (ipf->ipf_timer == maybe_ipf->ipf_timer
	269	&& ipf->ipf_last_uses + ipf->ipf_uses <
	270	maybe_ipf->ipf_last_uses +
	271	maybe_ipf->ipf_uses))
	272	maybe_ipf = ipf;
	273	ipf = LIST_NEXT(ipf, ipf_next);
	274	}
	275	}
	276	ipf = maybe_ipf;
	277	done:
	278	/*
	279	* Remove the entry from the flow table.
	280	*/
1c79356b	281	LIST_REMOVE(ipf, ipf_next);
1c79356b	282	ipflow_addstats(ipf);
9bccf70c	283	rtfree(ipf->ipf_ro.ro_rt);
1c79356b A	284	return ipf;
1c79356b A	285	}
2d21ac55	286	/* note: called under the ip_mutex lock */
1c79356b A	287	void
	288	ipflow_slowtimo(
	289	void)
	290	{
	291	struct ipflow *ipf;
	292	int idx;
	293
	294	for (idx = 0; idx < IPFLOW_HASHSIZE; idx++) {
	295	ipf = LIST_FIRST(&ipflows[idx]);
	296	while (ipf != NULL) {
	297	struct ipflow *next_ipf = LIST_NEXT(ipf, ipf_next);
	298	if (--ipf->ipf_timer == 0) {
	299	ipflow_free(ipf);
	300	} else {
	301	ipf->ipf_last_uses = ipf->ipf_uses;
	302	ipf->ipf_ro.ro_rt->rt_use += ipf->ipf_uses;
b0d623f7 A	303	OSAddAtomic(ipf->ipf_uses, &ipstat.ips_forward);
b0d623f7 A	304	OSAddAtomic(ipf->ipf_uses, &ipstat.ips_fastforward);
1c79356b A	305	ipstat.ips_forward += ipf->ipf_uses;
	306	ipstat.ips_fastforward += ipf->ipf_uses;
	307	ipf->ipf_uses = 0;
	308	}
	309	ipf = next_ipf;
	310	}
	311	}
	312	}
	313
	314	void
	315	ipflow_create(
	316	const struct route *ro,
	317	struct mbuf *m)
	318	{
	319	const struct ip const ip = mtod(m, struct ip );
	320	struct ipflow *ipf;
	321	unsigned hash;
1c79356b A	322
	323	/*
	324	* Don't create cache entries for ICMP messages.
	325	*/
	326	if (!ipflow_active \|\| ip->ip_p == IPPROTO_ICMP)
	327	return;
	328	/*
	329	* See if an existing flow struct exists. If so remove it from it's
	330	* list and free the old route. If not, try to malloc a new one
	331	* (if we aren't at our limit).
	332	*/
	333	ipf = ipflow_lookup(ip);
	334	if (ipf == NULL) {
	335	if (ipflow_inuse == IPFLOW_MAX) {
	336	ipf = ipflow_reap();
	337	} else {
	338	ipf = (struct ipflow ) _MALLOC(sizeof(ipf), M_IPFLOW,
	339	M_NOWAIT);
	340	if (ipf == NULL)
	341	return;
	342	ipflow_inuse++;
	343	}
	344	bzero((caddr_t) ipf, sizeof(*ipf));
	345	} else {
1c79356b	346	LIST_REMOVE(ipf, ipf_next);
1c79356b	347	ipflow_addstats(ipf);
9bccf70c	348	rtfree(ipf->ipf_ro.ro_rt);
1c79356b A	349	ipf->ipf_uses = ipf->ipf_last_uses = 0;
	350	ipf->ipf_errors = ipf->ipf_dropped = 0;
	351	}
	352
	353	/*
	354	* Fill in the updated information.
	355	*/
	356	ipf->ipf_ro = *ro;
b0d623f7	357	RT_ADDREF(ro->ro_rt);
1c79356b A	358	ipf->ipf_dst = ip->ip_dst;
	359	ipf->ipf_src = ip->ip_src;
	360	ipf->ipf_tos = ip->ip_tos;
	361	ipf->ipf_timer = IPFLOW_TIMER;
	362	/*
	363	* Insert into the approriate bucket of the flow table.
	364	*/
	365	hash = ipflow_hash(ip->ip_dst, ip->ip_src, ip->ip_tos);
1c79356b	366	LIST_INSERT_HEAD(&ipflows[hash], ipf, ipf_next);
1c79356b	367	}
b0d623f7 A	368	#else /* !IPFLOW */
	369	int
	370	ipflow_fastforward(struct mbuf *m)
	371	{
	372	#pragma unused(m)
	373	/*
	374	* Since this symbol is exported (albeit unsupported), just return
	375	* false to keep things (e.g. PPP) happy, in case ipflow is not
	376	* compiled in.
	377	*/
	378	return (0);
	379	}
	380	#endif /* !IPFLOW */