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

/*
 * Copyright (c) 2000 Apple Computer, 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 <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>

#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;
	ipstat.ips_cantforward += ipf->ipf_errors + ipf->ipf_dropped;
	ipstat.ips_forward += ipf->ipf_uses;
	ipstat.ips_fastforward += ipf->ipf_uses;
}

static void
ipflow_free(
	struct ipflow *ipf)
{
	int s;
	/*
	 * 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.
	 */
	s = splimp();
	LIST_REMOVE(ipf, ipf_next);
	splx(s);
	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;
	int s;

	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.
	 */
	s = splimp();
	LIST_REMOVE(ipf, ipf_next);
	splx(s);
	ipflow_addstats(ipf);
	rtfree(ipf->ipf_ro.ro_rt);
	return ipf;
}

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;
				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;
	int s;

	/*
	 * 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 {
		s = splimp();
		LIST_REMOVE(ipf, ipf_next);
		splx(s);
		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;
	rtref(ro->ro_rt);		//### LD 5/25/04 needs rt_mtx lock
	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);
	s = splimp();
	LIST_INSERT_HEAD(&ipflows[hash], ipf, ipf_next);
	splx(s);
}
Commit	Line	Data
1c79356b	1	/*
5d5c5d0d A	2	* Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
5d5c5d0d A	3	*
8f6c56a5	4	* @APPLE_OSREFERENCE_LICENSE_HEADER_START@
1c79356b	5	*
8f6c56a5 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.
	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
8ad349bb	24	* limitations under the License.
8f6c56a5 A	25	*
8f6c56a5 A	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>
	75
	76	#include <net/if.h>
	77	#include <net/route.h>
	78
	79	#include <netinet/in.h>
	80	#include <netinet/in_systm.h>
	81	#include <netinet/ip.h>
	82	#include <netinet/in_var.h>
	83	#include <netinet/ip_var.h>
	84	#include <netinet/ip_flow.h>
	85	#include <net/dlil.h>
	86
	87	#define IPFLOW_TIMER (5 * PR_SLOWHZ)
	88	#define IPFLOW_HASHBITS 6 /* should not be a multiple of 8 */
	89	#define IPFLOW_HASHSIZE (1 << IPFLOW_HASHBITS)
	90	static LIST_HEAD(ipflowhead, ipflow) ipflows[IPFLOW_HASHSIZE];
	91	static int ipflow_inuse;
	92	#define IPFLOW_MAX 256
	93
9bccf70c	94	#ifdef __APPLE__
1c79356b A	95	#define M_IPFLOW M_TEMP
	96	#endif
	97
	98	static int ipflow_active = 0;
	99	SYSCTL_INT(_net_inet_ip, IPCTL_FASTFORWARDING, fastforwarding, CTLFLAG_RW,
9bccf70c	100	&ipflow_active, 0, "Enable flow-based IP forwarding");
1c79356b	101
9bccf70c A	102	#ifndef __APPLE__
	103	static MALLOC_DEFINE(M_IPFLOW, "ip_flow", "IP flow");
	104	#endif
1c79356b A	105
	106	static unsigned
	107	ipflow_hash(
	108	struct in_addr dst,
	109	struct in_addr src,
	110	unsigned tos)
	111	{
	112	unsigned hash = tos;
	113	int idx;
	114	for (idx = 0; idx < 32; idx += IPFLOW_HASHBITS)
	115	hash += (dst.s_addr >> (32 - idx)) + (src.s_addr >> idx);
	116	return hash & (IPFLOW_HASHSIZE-1);
	117	}
	118
	119	static struct ipflow *
	120	ipflow_lookup(
	121	const struct ip *ip)
	122	{
	123	unsigned hash;
	124	struct ipflow *ipf;
	125
	126	hash = ipflow_hash(ip->ip_dst, ip->ip_src, ip->ip_tos);
	127
	128	ipf = LIST_FIRST(&ipflows[hash]);
	129	while (ipf != NULL) {
	130	if (ip->ip_dst.s_addr == ipf->ipf_dst.s_addr
	131	&& ip->ip_src.s_addr == ipf->ipf_src.s_addr
	132	&& ip->ip_tos == ipf->ipf_tos)
	133	break;
	134	ipf = LIST_NEXT(ipf, ipf_next);
	135	}
	136	return ipf;
	137	}
	138
	139	int
	140	ipflow_fastforward(
	141	struct mbuf *m)
	142	{
	143	struct ip *ip;
	144	struct ipflow *ipf;
	145	struct rtentry *rt;
9bccf70c	146	struct sockaddr *dst;
1c79356b A	147	int error;
	148
	149	/*
	150	* Are we forwarding packets? Big enough for an IP packet?
	151	*/
	152	if (!ipforwarding \|\| !ipflow_active \|\| m->m_len < sizeof(struct ip))
	153	return 0;
	154	/*
	155	* IP header with no option and valid version and length
	156	*/
	157	ip = mtod(m, struct ip *);
	158	if (ip->ip_v != IPVERSION \|\| ip->ip_hl != (sizeof(struct ip) >> 2)
	159	\|\| ntohs(ip->ip_len) > m->m_pkthdr.len)
	160	return 0;
	161	/*
	162	* Find a flow.
	163	*/
	164	if ((ipf = ipflow_lookup(ip)) == NULL)
	165	return 0;
	166
	167	/*
	168	* Route and interface still up?
	169	*/
	170	rt = ipf->ipf_ro.ro_rt;
	171	if ((rt->rt_flags & RTF_UP) == 0 \|\| (rt->rt_ifp->if_flags & IFF_UP) == 0)
	172	return 0;
	173
	174	/*
	175	* Packet size OK? TTL?
	176	*/
	177	if (m->m_pkthdr.len > rt->rt_ifp->if_mtu \|\| ip->ip_ttl <= IPTTLDEC)
	178	return 0;
	179
	180	/*
	181	* Everything checks out and so we can forward this packet.
	182	* Modify the TTL and incrementally change the checksum.
	183	*/
	184	ip->ip_ttl -= IPTTLDEC;
	185	if (ip->ip_sum >= htons(0xffff - (IPTTLDEC << 8))) {
	186	ip->ip_sum += htons(IPTTLDEC << 8) + 1;
	187	} else {
	188	ip->ip_sum += htons(IPTTLDEC << 8);
	189	}
	190
	191	/*
	192	* Send the packet on its way. All we can get back is ENOBUFS
	193	*/
	194	ipf->ipf_uses++;
	195	ipf->ipf_timer = IPFLOW_TIMER;
	196
9bccf70c A	197	if (rt->rt_flags & RTF_GATEWAY)
	198	dst = rt->rt_gateway;
	199	else
	200	dst = &ipf->ipf_ro.ro_dst;
	201	#ifdef __APPLE__
1c79356b	202	/* Not sure the rt_dlt is valid here !! XXX */
91447636	203	if ((error = dlil_output(rt->rt_ifp, PF_INET, m, (caddr_t) rt, dst, 0)) != 0) {
9bccf70c A	204
	205	#else
	206	if ((error = (*rt->rt_ifp->if_output)(rt->rt_ifp, m, dst, rt)) != 0) {
	207	#endif
1c79356b A	208	if (error == ENOBUFS)
	209	ipf->ipf_dropped++;
	210	else
	211	ipf->ipf_errors++;
	212	}
	213	return 1;
	214	}
	215	\f
	216	static void
	217	ipflow_addstats(
	218	struct ipflow *ipf)
	219	{
	220	ipf->ipf_ro.ro_rt->rt_use += ipf->ipf_uses;
	221	ipstat.ips_cantforward += ipf->ipf_errors + ipf->ipf_dropped;
	222	ipstat.ips_forward += ipf->ipf_uses;
	223	ipstat.ips_fastforward += ipf->ipf_uses;
	224	}
	225
	226	static void
	227	ipflow_free(
	228	struct ipflow *ipf)
	229	{
	230	int s;
	231	/*
	232	* Remove the flow from the hash table (at elevated IPL).
	233	* Once it's off the list, we can deal with it at normal
	234	* network IPL.
	235	*/
	236	s = splimp();
	237	LIST_REMOVE(ipf, ipf_next);
	238	splx(s);
	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;
	251	int s;
	252
	253	for (idx = 0; idx < IPFLOW_HASHSIZE; idx++) {
	254	ipf = LIST_FIRST(&ipflows[idx]);
	255	while (ipf != NULL) {
	256	/*
	257	* If this no longer points to a valid route
	258	* reclaim it.
	259	*/
	260	if ((ipf->ipf_ro.ro_rt->rt_flags & RTF_UP) == 0)
	261	goto done;
	262	/*
	263	* choose the one that's been least recently used
	264	* or has had the least uses in the last 1.5
	265	* intervals.
	266	*/
	267	if (maybe_ipf == NULL
	268	\|\| ipf->ipf_timer < maybe_ipf->ipf_timer
	269	\|\| (ipf->ipf_timer == maybe_ipf->ipf_timer
	270	&& ipf->ipf_last_uses + ipf->ipf_uses <
	271	maybe_ipf->ipf_last_uses +
	272	maybe_ipf->ipf_uses))
	273	maybe_ipf = ipf;
	274	ipf = LIST_NEXT(ipf, ipf_next);
	275	}
	276	}
	277	ipf = maybe_ipf;
	278	done:
	279	/*
	280	* Remove the entry from the flow table.
	281	*/
	282	s = splimp();
	283	LIST_REMOVE(ipf, ipf_next);
	284	splx(s);
	285	ipflow_addstats(ipf);
9bccf70c	286	rtfree(ipf->ipf_ro.ro_rt);
1c79356b A	287	return ipf;
	288	}
	289
	290	void
	291	ipflow_slowtimo(
	292	void)
	293	{
	294	struct ipflow *ipf;
	295	int idx;
	296
	297	for (idx = 0; idx < IPFLOW_HASHSIZE; idx++) {
	298	ipf = LIST_FIRST(&ipflows[idx]);
	299	while (ipf != NULL) {
	300	struct ipflow *next_ipf = LIST_NEXT(ipf, ipf_next);
	301	if (--ipf->ipf_timer == 0) {
	302	ipflow_free(ipf);
	303	} else {
	304	ipf->ipf_last_uses = ipf->ipf_uses;
	305	ipf->ipf_ro.ro_rt->rt_use += ipf->ipf_uses;
	306	ipstat.ips_forward += ipf->ipf_uses;
	307	ipstat.ips_fastforward += ipf->ipf_uses;
	308	ipf->ipf_uses = 0;
	309	}
	310	ipf = next_ipf;
	311	}
	312	}
	313	}
	314
	315	void
	316	ipflow_create(
	317	const struct route *ro,
	318	struct mbuf *m)
	319	{
	320	const struct ip const ip = mtod(m, struct ip );
	321	struct ipflow *ipf;
	322	unsigned hash;
	323	int s;
	324
	325	/*
	326	* Don't create cache entries for ICMP messages.
	327	*/
	328	if (!ipflow_active \|\| ip->ip_p == IPPROTO_ICMP)
	329	return;
	330	/*
	331	* See if an existing flow struct exists. If so remove it from it's
	332	* list and free the old route. If not, try to malloc a new one
	333	* (if we aren't at our limit).
	334	*/
	335	ipf = ipflow_lookup(ip);
	336	if (ipf == NULL) {
	337	if (ipflow_inuse == IPFLOW_MAX) {
	338	ipf = ipflow_reap();
	339	} else {
	340	ipf = (struct ipflow ) _MALLOC(sizeof(ipf), M_IPFLOW,
	341	M_NOWAIT);
	342	if (ipf == NULL)
	343	return;
	344	ipflow_inuse++;
	345	}
	346	bzero((caddr_t) ipf, sizeof(*ipf));
	347	} else {
	348	s = splimp();
	349	LIST_REMOVE(ipf, ipf_next);
	350	splx(s);
351	ipflow_addstats(ipf);
9bccf70c	352	rtfree(ipf->ipf_ro.ro_rt);
1c79356b A	353	ipf->ipf_uses = ipf->ipf_last_uses = 0;
	354	ipf->ipf_errors = ipf->ipf_dropped = 0;
	355	}
	356
	357	/*
	358	* Fill in the updated information.
	359	*/
	360	ipf->ipf_ro = *ro;
91447636	361	rtref(ro->ro_rt); //### LD 5/25/04 needs rt_mtx lock
1c79356b A	362	ipf->ipf_dst = ip->ip_dst;
	363	ipf->ipf_src = ip->ip_src;
	364	ipf->ipf_tos = ip->ip_tos;
	365	ipf->ipf_timer = IPFLOW_TIMER;
	366	/*
	367	* Insert into the approriate bucket of the flow table.
	368	*/
	369	hash = ipflow_hash(ip->ip_dst, ip->ip_src, ip->ip_tos);
	370	s = splimp();
	371	LIST_INSERT_HEAD(&ipflows[hash], ipf, ipf_next);
	372	splx(s);
	373	}