xref: /netbsd-src/sys/netinet6/ip6_flow.c (revision 946379e7b37692fc43f68eb0d1c10daa0a7f3b6c) 
1 /*	$NetBSD: ip6_flow.c,v 1.24 2015/03/23 18:33:17 roy 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@netbsd.org> and Matt Thomas <matt@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.24 2015/03/23 18:33:17 roy 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_fastforward -> if_output
78  */
79 
80 static struct pool ip6flow_pool;
81 
82 LIST_HEAD(ip6flowhead, ip6flow);
83 
84 /*
85  * We could use IPv4 defines (IPFLOW_HASHBITS) but we'll
86  * use our own (possibly for future expansion).
87  */
88 #define	IP6FLOW_TIMER		(5 * PR_SLOWHZ)
89 #define	IP6FLOW_DEFAULT_HASHSIZE	(1 << IP6FLOW_HASHBITS)
90 
91 static struct ip6flowhead *ip6flowtable = NULL;
92 static struct ip6flowhead ip6flowlist;
93 static int ip6flow_inuse;
94 
95 /*
96  * Insert an ip6flow into the list.
97  */
98 #define	IP6FLOW_INSERT(bucket, ip6f) \
99 do { \
100 	LIST_INSERT_HEAD((bucket), (ip6f), ip6f_hash); \
101 	LIST_INSERT_HEAD(&ip6flowlist, (ip6f), ip6f_list); \
102 } while (/*CONSTCOND*/ 0)
103 
104 /*
105  * Remove an ip6flow from the list.
106  */
107 #define	IP6FLOW_REMOVE(ip6f) \
108 do { \
109 	LIST_REMOVE((ip6f), ip6f_hash); \
110 	LIST_REMOVE((ip6f), ip6f_list); \
111 } while (/*CONSTCOND*/ 0)
112 
113 #ifndef IP6FLOW_DEFAULT
114 #define	IP6FLOW_DEFAULT		256
115 #endif
116 
117 int ip6_maxflows = IP6FLOW_DEFAULT;
118 int ip6_hashsize = IP6FLOW_DEFAULT_HASHSIZE;
119 
120 /*
121  * Calculate hash table position.
122  */
123 static size_t
124 ip6flow_hash(const struct ip6_hdr *ip6)
125 {
126 	size_t hash;
127 	uint32_t dst_sum, src_sum;
128 	size_t idx;
129 
130 	src_sum = ip6->ip6_src.s6_addr32[0] + ip6->ip6_src.s6_addr32[1]
131 	    + ip6->ip6_src.s6_addr32[2] + ip6->ip6_src.s6_addr32[3];
132 	dst_sum = ip6->ip6_dst.s6_addr32[0] + ip6->ip6_dst.s6_addr32[1]
133 	    + ip6->ip6_dst.s6_addr32[2] + ip6->ip6_dst.s6_addr32[3];
134 
135 	hash = ip6->ip6_flow;
136 
137 	for (idx = 0; idx < 32; idx += IP6FLOW_HASHBITS)
138 		hash += (dst_sum >> (32 - idx)) + (src_sum >> idx);
139 
140 	return hash & (ip6_hashsize-1);
141 }
142 
143 /*
144  * Check to see if a flow already exists - if so return it.
145  */
146 static struct ip6flow *
147 ip6flow_lookup(const struct ip6_hdr *ip6)
148 {
149 	size_t hash;
150 	struct ip6flow *ip6f;
151 
152 	hash = ip6flow_hash(ip6);
153 
154 	LIST_FOREACH(ip6f, &ip6flowtable[hash], ip6f_hash) {
155 		if (IN6_ARE_ADDR_EQUAL(&ip6->ip6_dst, &ip6f->ip6f_dst)
156 		    && IN6_ARE_ADDR_EQUAL(&ip6->ip6_src, &ip6f->ip6f_src)
157 		    && ip6f->ip6f_flow == ip6->ip6_flow) {
158 		    	/* A cached flow has been found. */
159 			return ip6f;
160 		}
161 	}
162 
163 	return NULL;
164 }
165 
166 void
167 ip6flow_poolinit(void)
168 {
169 
170 	pool_init(&ip6flow_pool, sizeof(struct ip6flow), 0, 0, 0, "ip6flowpl",
171 			NULL, IPL_NET);
172 }
173 
174 /*
175  * Allocate memory and initialise lists. This function is called
176  * from ip6_init and called there after to resize the hash table.
177  * If a newly sized table cannot be malloc'ed we just continue
178  * to use the old one.
179  */
180 int
181 ip6flow_init(int table_size)
182 {
183 	struct ip6flowhead *new_table;
184 	size_t i;
185 
186 	new_table = (struct ip6flowhead *)malloc(sizeof(struct ip6flowhead) *
187 	    table_size, M_RTABLE, M_NOWAIT);
188 
189 	if (new_table == NULL)
190 		return 1;
191 
192 	if (ip6flowtable != NULL)
193 		free(ip6flowtable, M_RTABLE);
194 
195 	ip6flowtable = new_table;
196 	ip6_hashsize = table_size;
197 
198 	LIST_INIT(&ip6flowlist);
199 	for (i = 0; i < ip6_hashsize; i++)
200 		LIST_INIT(&ip6flowtable[i]);
201 
202 	return 0;
203 }
204 
205 /*
206  * IPv6 Fast Forward routine. Attempt to forward the packet -
207  * if any problems are found return to the main IPv6 input
208  * routine to deal with.
209  */
210 int
211 ip6flow_fastforward(struct mbuf **mp)
212 {
213 	struct ip6flow *ip6f;
214 	struct ip6_hdr *ip6;
215 	struct rtentry *rt;
216 	struct mbuf *m;
217 	const struct sockaddr *dst;
218 	int error;
219 
220 	/*
221 	 * Are we forwarding packets and have flows?
222 	 */
223 	if (!ip6_forwarding || ip6flow_inuse == 0)
224 		return 0;
225 
226 	m = *mp;
227 	/*
228 	 * At least size of IPv6 Header?
229 	 */
230 	if (m->m_len < sizeof(struct ip6_hdr))
231 		return 0;
232 	/*
233 	 * Was packet received as a link-level multicast or broadcast?
234 	 * If so, don't try to fast forward.
235 	 */
236 	if ((m->m_flags & (M_BCAST|M_MCAST)) != 0)
237 		return 0;
238 
239 	if (IP6_HDR_ALIGNED_P(mtod(m, const void *)) == 0) {
240 		if ((m = m_copyup(m, sizeof(struct ip6_hdr),
241 				(max_linkhdr + 3) & ~3)) == NULL) {
242 			return 0;
243 		}
244 		*mp = m;
245 	} else if (__predict_false(m->m_len < sizeof(struct ip6_hdr))) {
246 		if ((m = m_pullup(m, sizeof(struct ip6_hdr))) == NULL) {
247 			return 0;
248 		}
249 		*mp = m;
250 	}
251 
252 	ip6 = mtod(m, struct ip6_hdr *);
253 
254 	if ((ip6->ip6_vfc & IPV6_VERSION_MASK) != IPV6_VERSION) {
255 		/* Bad version. */
256 		return 0;
257 	}
258 
259 	/*
260 	 * If we have a hop-by-hop extension we must process it.
261 	 * We just leave this up to ip6_input to deal with.
262 	 */
263 	if (ip6->ip6_nxt == IPPROTO_HOPOPTS)
264 		return 0;
265 
266 	/*
267 	 * Attempt to find a flow.
268 	 */
269 	if ((ip6f = ip6flow_lookup(ip6)) == NULL) {
270 		/* No flow found. */
271 		return 0;
272 	}
273 
274 	/*
275 	 * Route and interface still up?
276 	 */
277 	if ((rt = rtcache_validate(&ip6f->ip6f_ro)) == NULL ||
278 	    (rt->rt_ifp->if_flags & IFF_UP) == 0 ||
279 	    (rt->rt_flags & RTF_BLACKHOLE) != 0)
280 		return 0;
281 
282 	/*
283 	 * Packet size greater than MTU?
284 	 */
285 	if (m->m_pkthdr.len > rt->rt_ifp->if_mtu) {
286 		/* Return to main IPv6 input function. */
287 		return 0;
288 	}
289 
290 	/*
291 	 * Clear any in-bound checksum flags for this packet.
292 	 */
293 	m->m_pkthdr.csum_flags = 0;
294 
295 	if (ip6->ip6_hlim <= IPV6_HLIMDEC)
296 		return 0;
297 
298 	/* Decrement hop limit (same as TTL) */
299 	ip6->ip6_hlim -= IPV6_HLIMDEC;
300 
301 	if (rt->rt_flags & RTF_GATEWAY)
302 		dst = rt->rt_gateway;
303 	else
304 		dst = rtcache_getdst(&ip6f->ip6f_ro);
305 
306 	PRT_SLOW_ARM(ip6f->ip6f_timer, IP6FLOW_TIMER);
307 
308 	ip6f->ip6f_uses++;
309 
310 	KERNEL_LOCK(1, NULL);
311 	/* Send on its way - straight to the interface output routine. */
312 	if ((error = (*rt->rt_ifp->if_output)(rt->rt_ifp, m, dst, rt)) != 0) {
313 		ip6f->ip6f_dropped++;
314 	} else {
315 		ip6f->ip6f_forwarded++;
316 	}
317 	KERNEL_UNLOCK_ONE(NULL);
318 	return 1;
319 }
320 
321 /*
322  * Add the IPv6 flow statistics to the main IPv6 statistics.
323  */
324 static void
325 ip6flow_addstats(const struct ip6flow *ip6f)
326 {
327 	struct rtentry *rt;
328 	uint64_t *ip6s;
329 
330 	if ((rt = rtcache_validate(&ip6f->ip6f_ro)) != NULL)
331 		rt->rt_use += ip6f->ip6f_uses;
332 	ip6s = IP6_STAT_GETREF();
333 	ip6s[IP6_STAT_FASTFORWARDFLOWS] = ip6flow_inuse;
334 	ip6s[IP6_STAT_CANTFORWARD] += ip6f->ip6f_dropped;
335 	ip6s[IP6_STAT_ODROPPED] += ip6f->ip6f_dropped;
336 	ip6s[IP6_STAT_TOTAL] += ip6f->ip6f_uses;
337 	ip6s[IP6_STAT_FORWARD] += ip6f->ip6f_forwarded;
338 	ip6s[IP6_STAT_FASTFORWARD] += ip6f->ip6f_forwarded;
339 	IP6_STAT_PUTREF();
340 }
341 
342 /*
343  * Add statistics and free the flow.
344  */
345 static void
346 ip6flow_free(struct ip6flow *ip6f)
347 {
348 	int s;
349 
350 	/*
351 	 * Remove the flow from the hash table (at elevated IPL).
352 	 * Once it's off the list, we can deal with it at normal
353 	 * network IPL.
354 	 */
355 	s = splnet();
356 	IP6FLOW_REMOVE(ip6f);
357 	splx(s);
358 	ip6flow_inuse--;
359 	ip6flow_addstats(ip6f);
360 	rtcache_free(&ip6f->ip6f_ro);
361 	pool_put(&ip6flow_pool, ip6f);
362 }
363 
364 /*
365  * Reap one or more flows - ip6flow_reap may remove
366  * multiple flows if net.inet6.ip6.maxflows is reduced.
367  */
368 struct ip6flow *
369 ip6flow_reap(int just_one)
370 {
371 	while (just_one || ip6flow_inuse > ip6_maxflows) {
372 		struct ip6flow *ip6f, *maybe_ip6f = NULL;
373 		int s;
374 
375 		ip6f = LIST_FIRST(&ip6flowlist);
376 		while (ip6f != NULL) {
377 			/*
378 			 * If this no longer points to a valid route -
379 			 * reclaim it.
380 			 */
381 			if (rtcache_validate(&ip6f->ip6f_ro) == NULL)
382 				goto done;
383 			/*
384 			 * choose the one that's been least recently
385 			 * used or has had the least uses in the
386 			 * last 1.5 intervals.
387 			 */
388 			if (maybe_ip6f == NULL ||
389 			    ip6f->ip6f_timer < maybe_ip6f->ip6f_timer ||
390 			    (ip6f->ip6f_timer == maybe_ip6f->ip6f_timer &&
391 			     ip6f->ip6f_last_uses + ip6f->ip6f_uses <
392 			         maybe_ip6f->ip6f_last_uses +
393 			         maybe_ip6f->ip6f_uses))
394 				maybe_ip6f = ip6f;
395 			ip6f = LIST_NEXT(ip6f, ip6f_list);
396 		}
397 		ip6f = maybe_ip6f;
398 	    done:
399 		/*
400 		 * Remove the entry from the flow table
401 		 */
402 		s = splnet();
403 		IP6FLOW_REMOVE(ip6f);
404 		splx(s);
405 		rtcache_free(&ip6f->ip6f_ro);
406 		if (just_one) {
407 			ip6flow_addstats(ip6f);
408 			return ip6f;
409 		}
410 		ip6flow_inuse--;
411 		ip6flow_addstats(ip6f);
412 		pool_put(&ip6flow_pool, ip6f);
413 	}
414 	return NULL;
415 }
416 
417 void
418 ip6flow_slowtimo(void)
419 {
420 	struct ip6flow *ip6f, *next_ip6f;
421 
422 	mutex_enter(softnet_lock);
423 	KERNEL_LOCK(1, NULL);
424 
425 	for (ip6f = LIST_FIRST(&ip6flowlist); ip6f != NULL; ip6f = next_ip6f) {
426 		next_ip6f = LIST_NEXT(ip6f, ip6f_list);
427 		if (PRT_SLOW_ISEXPIRED(ip6f->ip6f_timer) ||
428 		    rtcache_validate(&ip6f->ip6f_ro) == NULL) {
429 			ip6flow_free(ip6f);
430 		} else {
431 			ip6f->ip6f_last_uses = ip6f->ip6f_uses;
432 			ip6flow_addstats(ip6f);
433 			ip6f->ip6f_uses = 0;
434 			ip6f->ip6f_dropped = 0;
435 			ip6f->ip6f_forwarded = 0;
436 		}
437 	}
438 
439 	KERNEL_UNLOCK_ONE(NULL);
440 	mutex_exit(softnet_lock);
441 }
442 
443 /*
444  * We have successfully forwarded a packet using the normal
445  * IPv6 stack. Now create/update a flow.
446  */
447 void
448 ip6flow_create(const struct route *ro, struct mbuf *m)
449 {
450 	const struct ip6_hdr *ip6;
451 	struct ip6flow *ip6f;
452 	size_t hash;
453 	int s;
454 
455 	ip6 = mtod(m, const struct ip6_hdr *);
456 
457 	/*
458 	 * If IPv6 Fast Forward is disabled, don't create a flow.
459 	 * It can be disabled by setting net.inet6.ip6.maxflows to 0.
460 	 *
461 	 * Don't create a flow for ICMPv6 messages.
462 	 */
463 	if (ip6_maxflows == 0 || ip6->ip6_nxt == IPPROTO_IPV6_ICMP)
464 		return;
465 
466 	KERNEL_LOCK(1, NULL);
467 
468 	/*
469 	 * See if an existing flow exists.  If so:
470 	 *	- Remove the flow
471 	 *	- Add flow statistics
472 	 *	- Free the route
473 	 *	- Reset statistics
474 	 *
475 	 * If a flow doesn't exist allocate a new one if
476 	 * ip6_maxflows hasn't reached its limit. If it has
477 	 * been reached, reap some flows.
478 	 */
479 	ip6f = ip6flow_lookup(ip6);
480 	if (ip6f == NULL) {
481 		if (ip6flow_inuse >= ip6_maxflows) {
482 			ip6f = ip6flow_reap(1);
483 		} else {
484 			ip6f = pool_get(&ip6flow_pool, PR_NOWAIT);
485 			if (ip6f == NULL)
486 				goto out;
487 			ip6flow_inuse++;
488 		}
489 		memset(ip6f, 0, sizeof(*ip6f));
490 	} else {
491 		s = splnet();
492 		IP6FLOW_REMOVE(ip6f);
493 		splx(s);
494 		ip6flow_addstats(ip6f);
495 		rtcache_free(&ip6f->ip6f_ro);
496 		ip6f->ip6f_uses = 0;
497 		ip6f->ip6f_last_uses = 0;
498 		ip6f->ip6f_dropped = 0;
499 		ip6f->ip6f_forwarded = 0;
500 	}
501 
502 	/*
503 	 * Fill in the updated/new details.
504 	 */
505 	rtcache_copy(&ip6f->ip6f_ro, ro);
506 	ip6f->ip6f_dst = ip6->ip6_dst;
507 	ip6f->ip6f_src = ip6->ip6_src;
508 	ip6f->ip6f_flow = ip6->ip6_flow;
509 	PRT_SLOW_ARM(ip6f->ip6f_timer, IP6FLOW_TIMER);
510 
511 	/*
512 	 * Insert into the approriate bucket of the flow table.
513 	 */
514 	hash = ip6flow_hash(ip6);
515 	s = splnet();
516 	IP6FLOW_INSERT(&ip6flowtable[hash], ip6f);
517 	splx(s);
518 
519  out:
520 	KERNEL_UNLOCK_ONE(NULL);
521 }
522 
523 /*
524  * Invalidate/remove all flows - if new_size is positive we
525  * resize the hash table.
526  */
527 int
528 ip6flow_invalidate_all(int new_size)
529 {
530 	struct ip6flow *ip6f, *next_ip6f;
531 	int s, error;
532 
533 	error = 0;
534 	s = splnet();
535 	for (ip6f = LIST_FIRST(&ip6flowlist); ip6f != NULL; ip6f = next_ip6f) {
536 		next_ip6f = LIST_NEXT(ip6f, ip6f_list);
537 		ip6flow_free(ip6f);
538 	}
539 
540 	if (new_size)
541 		error = ip6flow_init(new_size);
542 	splx(s);
543 
544 	return error;
545 }
546