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