Home | History | Annotate | Line # | Download | only in netinet6
ip6_flow.c revision 1.17 
      1 /*	$NetBSD: ip6_flow.c,v 1.17 2008/04/28 20:24:10 martin Exp $	*/
      2 
      3 /*-
      4  * Copyright (c) 2007 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 Liam J. Foy
      9  * <liamjfoy (at) netbsd.org> and Matt Thomas <matt (at) netbsd.org>.
     10  *
     11  * Redistribution and use in source and binary forms, with or without
     12  * modification, are permitted provided that the following conditions
     13  * are met:
     14  * 1. Redistributions of source code must retain the above copyright
     15  *    notice, this list of conditions and the following disclaimer.
     16  * 2. Redistributions in binary form must reproduce the above copyright
     17  *    notice, this list of conditions and the following disclaimer in the
     18  *    documentation and/or other materials provided with the distribution.
     19  *
     20  * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
     21  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
     22  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
     23  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
     24  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
     25  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
     26  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
     27  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
     28  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
     29  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
     30  * POSSIBILITY OF SUCH DAMAGE.
     31  *
     32  * IPv6 version was developed by Liam J. Foy. Original source existed in IPv4
     33  * format developed by Matt Thomas. Thanks to Joerg Sonnenberger, Matt
     34  * Thomas and Christos Zoulas.
     35  *
     36  * Thanks to Liverpool John Moores University, especially Dr. David Llewellyn-Jones
     37  * for providing resources (to test) and Professor Madjid Merabti.
     38  */
     39 
     40 #include <sys/cdefs.h>
     41 __KERNEL_RCSID(0, "$NetBSD: ip6_flow.c,v 1.17 2008/04/28 20:24:10 martin Exp $");
     42 
     43 #include <sys/param.h>
     44 #include <sys/systm.h>
     45 #include <sys/malloc.h>
     46 #include <sys/mbuf.h>
     47 #include <sys/domain.h>
     48 #include <sys/protosw.h>
     49 #include <sys/socket.h>
     50 #include <sys/socketvar.h>
     51 #include <sys/time.h>
     52 #include <sys/kernel.h>
     53 #include <sys/pool.h>
     54 #include <sys/sysctl.h>
     55 
     56 #include <net/if.h>
     57 #include <net/if_dl.h>
     58 #include <net/route.h>
     59 #include <net/pfil.h>
     60 
     61 #include <netinet/in.h>
     62 #include <netinet6/in6_var.h>
     63 #include <netinet/in_systm.h>
     64 #include <netinet/ip6.h>
     65 #include <netinet6/ip6_var.h>
     66 #include <netinet6/ip6_private.h>
     67 
     68 /*
     69  * IPv6 Fast Forward caches/hashes flows from one source to destination.
     70  *
     71  * Upon a successful forward IPv6FF caches and hashes details such as the
     72  * route, source and destination. Once another packet is received matching
     73  * the source and destination the packet is forwarded straight onto if_output
     74  * using the cached details.
     75  *
     76  * Example:
     77  * ether/fddi_input -> ip6flow_fastfoward -> if_output
     78  */
     79 
     80 POOL_INIT(ip6flow_pool, sizeof(struct ip6flow), 0, 0, 0, "ip6flowpl", NULL,
     81     IPL_NET);
     82 
     83 LIST_HEAD(ip6flowhead, ip6flow);
     84 
     85 /*
     86  * We could use IPv4 defines (IPFLOW_HASHBITS) but we'll
     87  * use our own (possibly for future expansion).
     88  */
     89 #define	IP6FLOW_TIMER		(5 * PR_SLOWHZ)
     90 #define	IP6FLOW_DEFAULT_HASHSIZE	(1 << IP6FLOW_HASHBITS)
     91 
     92 static struct ip6flowhead *ip6flowtable = NULL;
     93 static struct ip6flowhead ip6flowlist;
     94 static int ip6flow_inuse;
     95 
     96 /*
     97  * Insert an ip6flow into the list.
     98  */
     99 #define	IP6FLOW_INSERT(bucket, ip6f) \
    100 do { \
    101 	LIST_INSERT_HEAD((bucket), (ip6f), ip6f_hash); \
    102 	LIST_INSERT_HEAD(&ip6flowlist, (ip6f), ip6f_list); \
    103 } while (/*CONSTCOND*/ 0)
    104 
    105 /*
    106  * Remove an ip6flow from the list.
    107  */
    108 #define	IP6FLOW_REMOVE(ip6f) \
    109 do { \
    110 	LIST_REMOVE((ip6f), ip6f_hash); \
    111 	LIST_REMOVE((ip6f), ip6f_list); \
    112 } while (/*CONSTCOND*/ 0)
    113 
    114 #ifndef IP6FLOW_DEFAULT
    115 #define	IP6FLOW_DEFAULT		256
    116 #endif
    117 
    118 int ip6_maxflows = IP6FLOW_DEFAULT;
    119 int ip6_hashsize = IP6FLOW_DEFAULT_HASHSIZE;
    120 
    121 /*
    122  * Calculate hash table position.
    123  */
    124 static size_t
    125 ip6flow_hash(const struct ip6_hdr *ip6)
    126 {
    127 	size_t hash;
    128 	uint32_t dst_sum, src_sum;
    129 	size_t idx;
    130 
    131 	src_sum = ip6->ip6_src.s6_addr32[0] + ip6->ip6_src.s6_addr32[1]
    132 	    + ip6->ip6_src.s6_addr32[2] + ip6->ip6_src.s6_addr32[3];
    133 	dst_sum = ip6->ip6_dst.s6_addr32[0] + ip6->ip6_dst.s6_addr32[1]
    134 	    + ip6->ip6_dst.s6_addr32[2] + ip6->ip6_dst.s6_addr32[3];
    135 
    136 	hash = ip6->ip6_flow;
    137 
    138 	for (idx = 0; idx < 32; idx += IP6FLOW_HASHBITS)
    139 		hash += (dst_sum >> (32 - idx)) + (src_sum >> idx);
    140 
    141 	return hash & (ip6_hashsize-1);
    142 }
    143 
    144 /*
    145  * Check to see if a flow already exists - if so return it.
    146  */
    147 static struct ip6flow *
    148 ip6flow_lookup(const struct ip6_hdr *ip6)
    149 {
    150 	size_t hash;
    151 	struct ip6flow *ip6f;
    152 
    153 	hash = ip6flow_hash(ip6);
    154 
    155 	LIST_FOREACH(ip6f, &ip6flowtable[hash], ip6f_hash) {
    156 		if (IN6_ARE_ADDR_EQUAL(&ip6->ip6_dst, &ip6f->ip6f_dst)
    157 		    && IN6_ARE_ADDR_EQUAL(&ip6->ip6_src, &ip6f->ip6f_src)
    158 		    && ip6f->ip6f_flow == ip6->ip6_flow) {
    159 		    	/* A cached flow has been found. */
    160 			return ip6f;
    161 		}
    162 	}
    163 
    164 	return NULL;
    165 }
    166 
    167 /*
    168  * Allocate memory and initialise lists. This function is called
    169  * from ip6_init and called there after to resize the hash table.
    170  * If a newly sized table cannot be malloc'ed we just continue
    171  * to use the old one.
    172  */
    173 int
    174 ip6flow_init(int table_size)
    175 {
    176 	struct ip6flowhead *new_table;
    177 	size_t i;
    178 
    179 	new_table = (struct ip6flowhead *)malloc(sizeof(struct ip6flowhead) *
    180 	    table_size, M_RTABLE, M_NOWAIT);
    181 
    182 	if (new_table == NULL)
    183 		return 1;
    184 
    185 	if (ip6flowtable != NULL)
    186 		free(ip6flowtable, M_RTABLE);
    187 
    188 	ip6flowtable = new_table;
    189 	ip6_hashsize = table_size;
    190 
    191 	LIST_INIT(&ip6flowlist);
    192 	for (i = 0; i < ip6_hashsize; i++)
    193 		LIST_INIT(&ip6flowtable[i]);
    194 
    195 	return 0;
    196 }
    197 
    198 /*
    199  * IPv6 Fast Forward routine. Attempt to forward the packet -
    200  * if any problems are found return to the main IPv6 input
    201  * routine to deal with.
    202  */
    203 int
    204 ip6flow_fastforward(struct mbuf *m)
    205 {
    206 	struct ip6flow *ip6f;
    207 	struct ip6_hdr *ip6;
    208 	struct rtentry *rt;
    209 	const struct sockaddr *dst;
    210 	int error;
    211 
    212 	/*
    213 	 * Are we forwarding packets and have flows?
    214 	 */
    215 	if (!ip6_forwarding || ip6flow_inuse == 0)
    216 		return 0;
    217 
    218 	/*
    219 	 * At least size of IPv6 Header?
    220 	 */
    221 	if (m->m_len < sizeof(struct ip6_hdr))
    222 		return 0;
    223 	/*
    224 	 * Was packet received as a link-level multicast or broadcast?
    225 	 * If so, don't try to fast forward.
    226 	 */
    227 	if ((m->m_flags & (M_BCAST|M_MCAST)) != 0)
    228 		return 0;
    229 
    230 	if (IP6_HDR_ALIGNED_P(mtod(m, const void *)) == 0) {
    231 		if ((m = m_copyup(m, sizeof(struct ip6_hdr),
    232 				(max_linkhdr + 3) & ~3)) == NULL) {
    233 			return 0;
    234 		}
    235 	} else if (__predict_false(m->m_len < sizeof(struct ip6_hdr))) {
    236 		if ((m = m_pullup(m, sizeof(struct ip6_hdr))) == NULL) {
    237 			return 0;
    238 		}
    239 	}
    240 
    241 	ip6 = mtod(m, struct ip6_hdr *);
    242 
    243 	if ((ip6->ip6_vfc & IPV6_VERSION_MASK) != IPV6_VERSION) {
    244 		/* Bad version. */
    245 		return 0;
    246 	}
    247 
    248 	/*
    249 	 * If we have a hop-by-hop extension we must process it.
    250 	 * We just leave this up to ip6_input to deal with.
    251 	 */
    252 	if (ip6->ip6_nxt == IPPROTO_HOPOPTS)
    253 		return 0;
    254 
    255 	/*
    256 	 * Attempt to find a flow.
    257 	 */
    258 	if ((ip6f = ip6flow_lookup(ip6)) == NULL) {
    259 		/* No flow found. */
    260 		return 0;
    261 	}
    262 
    263 	/*
    264 	 * Route and interface still up?
    265 	 */
    266 	if ((rt = rtcache_validate(&ip6f->ip6f_ro)) == NULL ||
    267 	    (rt->rt_ifp->if_flags & IFF_UP) == 0) {
    268 	    	/* Route or interface is down */
    269 		return 0;
    270 	}
    271 
    272 	/*
    273 	 * Packet size greater than MTU?
    274 	 */
    275 	if (m->m_pkthdr.len > rt->rt_ifp->if_mtu) {
    276 		/* Return to main IPv6 input function. */
    277 		return 0;
    278 	}
    279 
    280 	if (ip6->ip6_hlim <= IPV6_HLIMDEC)
    281 		return 0;
    282 
    283 	/* Decrement hop limit (same as TTL) */
    284 	ip6->ip6_hlim -= IPV6_HLIMDEC;
    285 
    286 	if (rt->rt_flags & RTF_GATEWAY)
    287 		dst = rt->rt_gateway;
    288 	else
    289 		dst = rtcache_getdst(&ip6f->ip6f_ro);
    290 
    291 	PRT_SLOW_ARM(ip6f->ip6f_timer, IP6FLOW_TIMER);
    292 
    293 	ip6f->ip6f_uses++;
    294 
    295 	/* Send on its way - straight to the interface output routine. */
    296 	if ((error = (*rt->rt_ifp->if_output)(rt->rt_ifp, m, dst, rt)) != 0) {
    297 		ip6f->ip6f_dropped++;
    298 	} else {
    299 		ip6f->ip6f_forwarded++;
    300 	}
    301 
    302 	return 1;
    303 }
    304 
    305 /*
    306  * Add the IPv6 flow statistics to the main IPv6 statistics.
    307  */
    308 static void
    309 ip6flow_addstats(const struct ip6flow *ip6f)
    310 {
    311 	struct rtentry *rt;
    312 	uint64_t *ip6s;
    313 
    314 	if ((rt = rtcache_validate(&ip6f->ip6f_ro)) != NULL)
    315 		rt->rt_use += ip6f->ip6f_uses;
    316 	ip6s = IP6_STAT_GETREF();
    317 	ip6s[IP6_STAT_FASTFORWARDFLOWS] = ip6flow_inuse;
    318 	ip6s[IP6_STAT_CANTFORWARD] += ip6f->ip6f_dropped;
    319 	ip6s[IP6_STAT_ODROPPED] += ip6f->ip6f_dropped;
    320 	ip6s[IP6_STAT_TOTAL] += ip6f->ip6f_uses;
    321 	ip6s[IP6_STAT_FORWARD] += ip6f->ip6f_forwarded;
    322 	ip6s[IP6_STAT_FASTFORWARD] += ip6f->ip6f_forwarded;
    323 	IP6_STAT_PUTREF();
    324 }
    325 
    326 /*
    327  * Add statistics and free the flow.
    328  */
    329 static void
    330 ip6flow_free(struct ip6flow *ip6f)
    331 {
    332 	int s;
    333 
    334 	/*
    335 	 * Remove the flow from the hash table (at elevated IPL).
    336 	 * Once it's off the list, we can deal with it at normal
    337 	 * network IPL.
    338 	 */
    339 	s = splnet();
    340 	IP6FLOW_REMOVE(ip6f);
    341 	splx(s);
    342 	ip6flow_inuse--;
    343 	ip6flow_addstats(ip6f);
    344 	rtcache_free(&ip6f->ip6f_ro);
    345 	pool_put(&ip6flow_pool, ip6f);
    346 }
    347 
    348 /*
    349  * Reap one or more flows - ip6flow_reap may remove
    350  * multiple flows if net.inet6.ip6.maxflows is reduced.
    351  */
    352 struct ip6flow *
    353 ip6flow_reap(int just_one)
    354 {
    355 	while (just_one || ip6flow_inuse > ip6_maxflows) {
    356 		struct ip6flow *ip6f, *maybe_ip6f = NULL;
    357 		int s;
    358 
    359 		ip6f = LIST_FIRST(&ip6flowlist);
    360 		while (ip6f != NULL) {
    361 			/*
    362 			 * If this no longer points to a valid route -
    363 			 * reclaim it.
    364 			 */
    365 			if (rtcache_validate(&ip6f->ip6f_ro) == NULL)
    366 				goto done;
    367 			/*
    368 			 * choose the one that's been least recently
    369 			 * used or has had the least uses in the
    370 			 * last 1.5 intervals.
    371 			 */
    372 			if (maybe_ip6f == NULL ||
    373 			    ip6f->ip6f_timer < maybe_ip6f->ip6f_timer ||
    374 			    (ip6f->ip6f_timer == maybe_ip6f->ip6f_timer &&
    375 			     ip6f->ip6f_last_uses + ip6f->ip6f_uses <
    376 			         maybe_ip6f->ip6f_last_uses +
    377 			         maybe_ip6f->ip6f_uses))
    378 				maybe_ip6f = ip6f;
    379 			ip6f = LIST_NEXT(ip6f, ip6f_list);
    380 		}
    381 		ip6f = maybe_ip6f;
    382 	    done:
    383 		/*
    384 		 * Remove the entry from the flow table
    385 		 */
    386 		s = splnet();
    387 		IP6FLOW_REMOVE(ip6f);
    388 		splx(s);
    389 		rtcache_free(&ip6f->ip6f_ro);
    390 		if (just_one) {
    391 			ip6flow_addstats(ip6f);
    392 			return ip6f;
    393 		}
    394 		ip6flow_inuse--;
    395 		ip6flow_addstats(ip6f);
    396 		pool_put(&ip6flow_pool, ip6f);
    397 	}
    398 	return NULL;
    399 }
    400 
    401 void
    402 ip6flow_slowtimo(void)
    403 {
    404 	struct ip6flow *ip6f, *next_ip6f;
    405 
    406 	mutex_enter(softnet_lock);
    407 	KERNEL_LOCK(1, NULL);
    408 
    409 	for (ip6f = LIST_FIRST(&ip6flowlist); ip6f != NULL; ip6f = next_ip6f) {
    410 		next_ip6f = LIST_NEXT(ip6f, ip6f_list);
    411 		if (PRT_SLOW_ISEXPIRED(ip6f->ip6f_timer) ||
    412 		    rtcache_validate(&ip6f->ip6f_ro) == NULL) {
    413 			ip6flow_free(ip6f);
    414 		} else {
    415 			ip6f->ip6f_last_uses = ip6f->ip6f_uses;
    416 			ip6flow_addstats(ip6f);
    417 			ip6f->ip6f_uses = 0;
    418 			ip6f->ip6f_dropped = 0;
    419 			ip6f->ip6f_forwarded = 0;
    420 		}
    421 	}
    422 
    423 	KERNEL_UNLOCK_ONE(NULL);
    424 	mutex_exit(softnet_lock);
    425 }
    426 
    427 /*
    428  * We have successfully forwarded a packet using the normal
    429  * IPv6 stack. Now create/update a flow.
    430  */
    431 void
    432 ip6flow_create(const struct route *ro, struct mbuf *m)
    433 {
    434 	const struct ip6_hdr *ip6;
    435 	struct ip6flow *ip6f;
    436 	size_t hash;
    437 	int s;
    438 
    439 	ip6 = mtod(m, const struct ip6_hdr *);
    440 
    441 	/*
    442 	 * If IPv6 Fast Forward is disabled, don't create a flow.
    443 	 * It can be disabled by setting net.inet6.ip6.maxflows to 0.
    444 	 *
    445 	 * Don't create a flow for ICMPv6 messages.
    446 	 */
    447 	if (ip6_maxflows == 0 || ip6->ip6_nxt == IPPROTO_IPV6_ICMP)
    448 		return;
    449 
    450 	/*
    451 	 * See if an existing flow exists.  If so:
    452 	 *	- Remove the flow
    453 	 *	- Add flow statistics
    454 	 *	- Free the route
    455 	 *	- Reset statistics
    456 	 *
    457 	 * If a flow doesn't exist allocate a new one if
    458 	 * ip6_maxflows hasn't reached its limit. If it has
    459 	 * been reached, reap some flows.
    460 	 */
    461 	ip6f = ip6flow_lookup(ip6);
    462 	if (ip6f == NULL) {
    463 		if (ip6flow_inuse >= ip6_maxflows) {
    464 			ip6f = ip6flow_reap(1);
    465 		} else {
    466 			ip6f = pool_get(&ip6flow_pool, PR_NOWAIT);
    467 			if (ip6f == NULL)
    468 				return;
    469 			ip6flow_inuse++;
    470 		}
    471 		memset(ip6f, 0, sizeof(*ip6f));
    472 	} else {
    473 		s = splnet();
    474 		IP6FLOW_REMOVE(ip6f);
    475 		splx(s);
    476 		ip6flow_addstats(ip6f);
    477 		rtcache_free(&ip6f->ip6f_ro);
    478 		ip6f->ip6f_uses = 0;
    479 		ip6f->ip6f_last_uses = 0;
    480 		ip6f->ip6f_dropped = 0;
    481 		ip6f->ip6f_forwarded = 0;
    482 	}
    483 
    484 	/*
    485 	 * Fill in the updated/new details.
    486 	 */
    487 	rtcache_copy(&ip6f->ip6f_ro, ro);
    488 	ip6f->ip6f_dst = ip6->ip6_dst;
    489 	ip6f->ip6f_src = ip6->ip6_src;
    490 	ip6f->ip6f_flow = ip6->ip6_flow;
    491 	PRT_SLOW_ARM(ip6f->ip6f_timer, IP6FLOW_TIMER);
    492 	ip6f->ip6f_start = time_uptime;
    493 
    494 	/*
    495 	 * Insert into the approriate bucket of the flow table.
    496 	 */
    497 	hash = ip6flow_hash(ip6);
    498 	s = splnet();
    499 	IP6FLOW_INSERT(&ip6flowtable[hash], ip6f);
    500 	splx(s);
    501 }
    502 
    503 /*
    504  * Invalidate/remove all flows - if new_size is positive we
    505  * resize the hash table.
    506  */
    507 int
    508 ip6flow_invalidate_all(int new_size)
    509 {
    510 	struct ip6flow *ip6f, *next_ip6f;
    511 	int s, error;
    512 
    513 	error = 0;
    514 	s = splnet();
    515 	for (ip6f = LIST_FIRST(&ip6flowlist); ip6f != NULL; ip6f = next_ip6f) {
    516 		next_ip6f = LIST_NEXT(ip6f, ip6f_list);
    517 		ip6flow_free(ip6f);
    518 	}
    519 
    520 	if (new_size)
    521 		error = ip6flow_init(new_size);
    522 	splx(s);
    523 
    524 	return error;
    525 }
    526