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