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

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