xref: /netbsd-src/sys/netinet6/ip6_flow.c (revision fdd524d4ccd2bb0c6f67401e938dabf773eb0372) 
1 /*	$NetBSD: ip6_flow.c,v 1.28 2016/07/11 07:37:00 ozaki-r 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.28 2016/07/11 07:37:00 ozaki-r 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 #include <sys/workqueue.h>
56 
57 #include <net/if.h>
58 #include <net/if_dl.h>
59 #include <net/route.h>
60 #include <net/pfil.h>
61 
62 #include <netinet/in.h>
63 #include <netinet6/in6_var.h>
64 #include <netinet/in_systm.h>
65 #include <netinet/ip6.h>
66 #include <netinet6/ip6_var.h>
67 #include <netinet6/ip6_private.h>
68 
69 /*
70  * IPv6 Fast Forward caches/hashes flows from one source to destination.
71  *
72  * Upon a successful forward IPv6FF caches and hashes details such as the
73  * route, source and destination. Once another packet is received matching
74  * the source and destination the packet is forwarded straight onto if_output
75  * using the cached details.
76  *
77  * Example:
78  * ether/fddi_input -> ip6flow_fastforward -> if_output
79  */
80 
81 static struct pool ip6flow_pool;
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 /*
93  * ip6_flow.c internal lock.
94  * If we use softnet_lock, it would cause recursive lock.
95  *
96  * This is a tentative workaround.
97  * We should make it scalable somehow in the future.
98  */
99 static kmutex_t ip6flow_lock;
100 static struct ip6flowhead *ip6flowtable = NULL;
101 static struct ip6flowhead ip6flowlist;
102 static int ip6flow_inuse;
103 
104 static void ip6flow_slowtimo_work(struct work *, void *);
105 static struct workqueue	*ip6flow_slowtimo_wq;
106 static struct work	ip6flow_slowtimo_wk;
107 
108 /*
109  * Insert an ip6flow into the list.
110  */
111 #define	IP6FLOW_INSERT(bucket, ip6f) \
112 do { \
113 	LIST_INSERT_HEAD((bucket), (ip6f), ip6f_hash); \
114 	LIST_INSERT_HEAD(&ip6flowlist, (ip6f), ip6f_list); \
115 } while (/*CONSTCOND*/ 0)
116 
117 /*
118  * Remove an ip6flow from the list.
119  */
120 #define	IP6FLOW_REMOVE(ip6f) \
121 do { \
122 	LIST_REMOVE((ip6f), ip6f_hash); \
123 	LIST_REMOVE((ip6f), ip6f_list); \
124 } while (/*CONSTCOND*/ 0)
125 
126 #ifndef IP6FLOW_DEFAULT
127 #define	IP6FLOW_DEFAULT		256
128 #endif
129 
130 int ip6_maxflows = IP6FLOW_DEFAULT;
131 int ip6_hashsize = IP6FLOW_DEFAULT_HASHSIZE;
132 
133 /*
134  * Calculate hash table position.
135  */
136 static size_t
137 ip6flow_hash(const struct ip6_hdr *ip6)
138 {
139 	size_t hash;
140 	uint32_t dst_sum, src_sum;
141 	size_t idx;
142 
143 	src_sum = ip6->ip6_src.s6_addr32[0] + ip6->ip6_src.s6_addr32[1]
144 	    + ip6->ip6_src.s6_addr32[2] + ip6->ip6_src.s6_addr32[3];
145 	dst_sum = ip6->ip6_dst.s6_addr32[0] + ip6->ip6_dst.s6_addr32[1]
146 	    + ip6->ip6_dst.s6_addr32[2] + ip6->ip6_dst.s6_addr32[3];
147 
148 	hash = ip6->ip6_flow;
149 
150 	for (idx = 0; idx < 32; idx += IP6FLOW_HASHBITS)
151 		hash += (dst_sum >> (32 - idx)) + (src_sum >> idx);
152 
153 	return hash & (ip6_hashsize-1);
154 }
155 
156 /*
157  * Check to see if a flow already exists - if so return it.
158  */
159 static struct ip6flow *
160 ip6flow_lookup(const struct ip6_hdr *ip6)
161 {
162 	size_t hash;
163 	struct ip6flow *ip6f;
164 
165 	KASSERT(mutex_owned(&ip6flow_lock));
166 
167 	hash = ip6flow_hash(ip6);
168 
169 	LIST_FOREACH(ip6f, &ip6flowtable[hash], ip6f_hash) {
170 		if (IN6_ARE_ADDR_EQUAL(&ip6->ip6_dst, &ip6f->ip6f_dst)
171 		    && IN6_ARE_ADDR_EQUAL(&ip6->ip6_src, &ip6f->ip6f_src)
172 		    && ip6f->ip6f_flow == ip6->ip6_flow) {
173 		    	/* A cached flow has been found. */
174 			return ip6f;
175 		}
176 	}
177 
178 	return NULL;
179 }
180 
181 void
182 ip6flow_poolinit(void)
183 {
184 
185 	pool_init(&ip6flow_pool, sizeof(struct ip6flow), 0, 0, 0, "ip6flowpl",
186 			NULL, IPL_NET);
187 }
188 
189 /*
190  * Allocate memory and initialise lists. This function is called
191  * from ip6_init and called there after to resize the hash table.
192  * If a newly sized table cannot be malloc'ed we just continue
193  * to use the old one.
194  */
195 static int
196 ip6flow_init_locked(int table_size)
197 {
198 	struct ip6flowhead *new_table;
199 	size_t i;
200 
201 	KASSERT(mutex_owned(&ip6flow_lock));
202 
203 	new_table = (struct ip6flowhead *)malloc(sizeof(struct ip6flowhead) *
204 	    table_size, M_RTABLE, M_NOWAIT);
205 
206 	if (new_table == NULL)
207 		return 1;
208 
209 	if (ip6flowtable != NULL)
210 		free(ip6flowtable, M_RTABLE);
211 
212 	ip6flowtable = new_table;
213 	ip6_hashsize = table_size;
214 
215 	LIST_INIT(&ip6flowlist);
216 	for (i = 0; i < ip6_hashsize; i++)
217 		LIST_INIT(&ip6flowtable[i]);
218 
219 	return 0;
220 }
221 
222 int
223 ip6flow_init(int table_size)
224 {
225 	int ret, error;
226 
227 	error = workqueue_create(&ip6flow_slowtimo_wq, "ip6flow_slowtimo",
228 	    ip6flow_slowtimo_work, NULL, PRI_SOFTNET, IPL_SOFTNET, WQ_MPSAFE);
229 	if (error != 0)
230 		panic("%s: workqueue_create failed (%d)\n", __func__, error);
231 
232 	mutex_init(&ip6flow_lock, MUTEX_DEFAULT, IPL_NONE);
233 
234 	mutex_enter(&ip6flow_lock);
235 	ret = ip6flow_init_locked(table_size);
236 	mutex_exit(&ip6flow_lock);
237 
238 	return ret;
239 }
240 
241 /*
242  * IPv6 Fast Forward routine. Attempt to forward the packet -
243  * if any problems are found return to the main IPv6 input
244  * routine to deal with.
245  */
246 int
247 ip6flow_fastforward(struct mbuf **mp)
248 {
249 	struct ip6flow *ip6f;
250 	struct ip6_hdr *ip6;
251 	struct rtentry *rt;
252 	struct mbuf *m;
253 	const struct sockaddr *dst;
254 	int error;
255 	int ret = 0;
256 
257 	mutex_enter(&ip6flow_lock);
258 
259 	/*
260 	 * Are we forwarding packets and have flows?
261 	 */
262 	if (!ip6_forwarding || ip6flow_inuse == 0)
263 		goto out;
264 
265 	m = *mp;
266 	/*
267 	 * At least size of IPv6 Header?
268 	 */
269 	if (m->m_len < sizeof(struct ip6_hdr))
270 		goto out;
271 	/*
272 	 * Was packet received as a link-level multicast or broadcast?
273 	 * If so, don't try to fast forward.
274 	 */
275 	if ((m->m_flags & (M_BCAST|M_MCAST)) != 0)
276 		goto out;
277 
278 	if (IP6_HDR_ALIGNED_P(mtod(m, const void *)) == 0) {
279 		if ((m = m_copyup(m, sizeof(struct ip6_hdr),
280 				(max_linkhdr + 3) & ~3)) == NULL) {
281 			goto out;
282 		}
283 		*mp = m;
284 	} else if (__predict_false(m->m_len < sizeof(struct ip6_hdr))) {
285 		if ((m = m_pullup(m, sizeof(struct ip6_hdr))) == NULL) {
286 			goto out;
287 		}
288 		*mp = m;
289 	}
290 
291 	ip6 = mtod(m, struct ip6_hdr *);
292 
293 	if ((ip6->ip6_vfc & IPV6_VERSION_MASK) != IPV6_VERSION) {
294 		/* Bad version. */
295 		goto out;
296 	}
297 
298 	/*
299 	 * If we have a hop-by-hop extension we must process it.
300 	 * We just leave this up to ip6_input to deal with.
301 	 */
302 	if (ip6->ip6_nxt == IPPROTO_HOPOPTS)
303 		goto out;
304 
305 	/*
306 	 * Attempt to find a flow.
307 	 */
308 	if ((ip6f = ip6flow_lookup(ip6)) == NULL) {
309 		/* No flow found. */
310 		goto out;
311 	}
312 
313 	/*
314 	 * Route and interface still up?
315 	 */
316 	if ((rt = rtcache_validate(&ip6f->ip6f_ro)) == NULL ||
317 	    (rt->rt_ifp->if_flags & IFF_UP) == 0 ||
318 	    (rt->rt_flags & RTF_BLACKHOLE) != 0)
319 		goto out;
320 
321 	/*
322 	 * Packet size greater than MTU?
323 	 */
324 	if (m->m_pkthdr.len > rt->rt_ifp->if_mtu) {
325 		/* Return to main IPv6 input function. */
326 		goto out;
327 	}
328 
329 	/*
330 	 * Clear any in-bound checksum flags for this packet.
331 	 */
332 	m->m_pkthdr.csum_flags = 0;
333 
334 	if (ip6->ip6_hlim <= IPV6_HLIMDEC)
335 		goto out;
336 
337 	/* Decrement hop limit (same as TTL) */
338 	ip6->ip6_hlim -= IPV6_HLIMDEC;
339 
340 	if (rt->rt_flags & RTF_GATEWAY)
341 		dst = rt->rt_gateway;
342 	else
343 		dst = rtcache_getdst(&ip6f->ip6f_ro);
344 
345 	PRT_SLOW_ARM(ip6f->ip6f_timer, IP6FLOW_TIMER);
346 
347 	ip6f->ip6f_uses++;
348 
349 	/* Send on its way - straight to the interface output routine. */
350 	if ((error = if_output_lock(rt->rt_ifp, rt->rt_ifp, m, dst, rt)) != 0) {
351 		ip6f->ip6f_dropped++;
352 	} else {
353 		ip6f->ip6f_forwarded++;
354 	}
355 	ret = 1;
356  out:
357 	mutex_exit(&ip6flow_lock);
358 	return ret;
359 }
360 
361 /*
362  * Add the IPv6 flow statistics to the main IPv6 statistics.
363  */
364 static void
365 ip6flow_addstats(const struct ip6flow *ip6f)
366 {
367 	struct rtentry *rt;
368 	uint64_t *ip6s;
369 
370 	if ((rt = rtcache_validate(&ip6f->ip6f_ro)) != NULL)
371 		rt->rt_use += ip6f->ip6f_uses;
372 	ip6s = IP6_STAT_GETREF();
373 	ip6s[IP6_STAT_FASTFORWARDFLOWS] = ip6flow_inuse;
374 	ip6s[IP6_STAT_CANTFORWARD] += ip6f->ip6f_dropped;
375 	ip6s[IP6_STAT_ODROPPED] += ip6f->ip6f_dropped;
376 	ip6s[IP6_STAT_TOTAL] += ip6f->ip6f_uses;
377 	ip6s[IP6_STAT_FORWARD] += ip6f->ip6f_forwarded;
378 	ip6s[IP6_STAT_FASTFORWARD] += ip6f->ip6f_forwarded;
379 	IP6_STAT_PUTREF();
380 }
381 
382 /*
383  * Add statistics and free the flow.
384  */
385 static void
386 ip6flow_free(struct ip6flow *ip6f)
387 {
388 
389 	KASSERT(mutex_owned(&ip6flow_lock));
390 
391 	/*
392 	 * Remove the flow from the hash table (at elevated IPL).
393 	 * Once it's off the list, we can deal with it at normal
394 	 * network IPL.
395 	 */
396 	IP6FLOW_REMOVE(ip6f);
397 
398 	ip6flow_inuse--;
399 	ip6flow_addstats(ip6f);
400 	rtcache_free(&ip6f->ip6f_ro);
401 	pool_put(&ip6flow_pool, ip6f);
402 }
403 
404 static struct ip6flow *
405 ip6flow_reap_locked(int just_one)
406 {
407 
408 	KASSERT(mutex_owned(&ip6flow_lock));
409 
410 	while (just_one || ip6flow_inuse > ip6_maxflows) {
411 		struct ip6flow *ip6f, *maybe_ip6f = NULL;
412 
413 		ip6f = LIST_FIRST(&ip6flowlist);
414 		while (ip6f != NULL) {
415 			/*
416 			 * If this no longer points to a valid route -
417 			 * reclaim it.
418 			 */
419 			if (rtcache_validate(&ip6f->ip6f_ro) == NULL)
420 				goto done;
421 			/*
422 			 * choose the one that's been least recently
423 			 * used or has had the least uses in the
424 			 * last 1.5 intervals.
425 			 */
426 			if (maybe_ip6f == NULL ||
427 			    ip6f->ip6f_timer < maybe_ip6f->ip6f_timer ||
428 			    (ip6f->ip6f_timer == maybe_ip6f->ip6f_timer &&
429 			     ip6f->ip6f_last_uses + ip6f->ip6f_uses <
430 			         maybe_ip6f->ip6f_last_uses +
431 			         maybe_ip6f->ip6f_uses))
432 				maybe_ip6f = ip6f;
433 			ip6f = LIST_NEXT(ip6f, ip6f_list);
434 		}
435 		ip6f = maybe_ip6f;
436 	    done:
437 		/*
438 		 * Remove the entry from the flow table
439 		 */
440 		IP6FLOW_REMOVE(ip6f);
441 
442 		rtcache_free(&ip6f->ip6f_ro);
443 		if (just_one) {
444 			ip6flow_addstats(ip6f);
445 			return ip6f;
446 		}
447 		ip6flow_inuse--;
448 		ip6flow_addstats(ip6f);
449 		pool_put(&ip6flow_pool, ip6f);
450 	}
451 	return NULL;
452 }
453 
454 /*
455  * Reap one or more flows - ip6flow_reap may remove
456  * multiple flows if net.inet6.ip6.maxflows is reduced.
457  */
458 struct ip6flow *
459 ip6flow_reap(int just_one)
460 {
461 	struct ip6flow *ip6f;
462 
463 	mutex_enter(&ip6flow_lock);
464 	ip6f = ip6flow_reap_locked(just_one);
465 	mutex_exit(&ip6flow_lock);
466 	return ip6f;
467 }
468 
469 static bool ip6flow_work_enqueued = false;
470 
471 void
472 ip6flow_slowtimo_work(struct work *wk, void *arg)
473 {
474 	struct ip6flow *ip6f, *next_ip6f;
475 
476 	mutex_enter(softnet_lock);
477 	mutex_enter(&ip6flow_lock);
478 	KERNEL_LOCK(1, NULL);
479 
480 	for (ip6f = LIST_FIRST(&ip6flowlist); ip6f != NULL; ip6f = next_ip6f) {
481 		next_ip6f = LIST_NEXT(ip6f, ip6f_list);
482 		if (PRT_SLOW_ISEXPIRED(ip6f->ip6f_timer) ||
483 		    rtcache_validate(&ip6f->ip6f_ro) == NULL) {
484 			ip6flow_free(ip6f);
485 		} else {
486 			ip6f->ip6f_last_uses = ip6f->ip6f_uses;
487 			ip6flow_addstats(ip6f);
488 			ip6f->ip6f_uses = 0;
489 			ip6f->ip6f_dropped = 0;
490 			ip6f->ip6f_forwarded = 0;
491 		}
492 	}
493 	ip6flow_work_enqueued = false;
494 
495 	KERNEL_UNLOCK_ONE(NULL);
496 	mutex_exit(&ip6flow_lock);
497 	mutex_exit(softnet_lock);
498 }
499 
500 void
501 ip6flow_slowtimo(void)
502 {
503 
504 	/* Avoid enqueuing another work when one is already enqueued */
505 	mutex_enter(&ip6flow_lock);
506 	if (ip6flow_work_enqueued) {
507 		mutex_exit(&ip6flow_lock);
508 		return;
509 	}
510 	ip6flow_work_enqueued = true;
511 	mutex_exit(&ip6flow_lock);
512 
513 	workqueue_enqueue(ip6flow_slowtimo_wq, &ip6flow_slowtimo_wk, NULL);
514 }
515 
516 /*
517  * We have successfully forwarded a packet using the normal
518  * IPv6 stack. Now create/update a flow.
519  */
520 void
521 ip6flow_create(const struct route *ro, struct mbuf *m)
522 {
523 	const struct ip6_hdr *ip6;
524 	struct ip6flow *ip6f;
525 	size_t hash;
526 
527 	mutex_enter(&ip6flow_lock);
528 
529 	ip6 = mtod(m, const struct ip6_hdr *);
530 
531 	/*
532 	 * If IPv6 Fast Forward is disabled, don't create a flow.
533 	 * It can be disabled by setting net.inet6.ip6.maxflows to 0.
534 	 *
535 	 * Don't create a flow for ICMPv6 messages.
536 	 */
537 	if (ip6_maxflows == 0 || ip6->ip6_nxt == IPPROTO_IPV6_ICMP) {
538 		mutex_exit(&ip6flow_lock);
539 		return;
540 	}
541 
542 	KERNEL_LOCK(1, NULL);
543 
544 	/*
545 	 * See if an existing flow exists.  If so:
546 	 *	- Remove the flow
547 	 *	- Add flow statistics
548 	 *	- Free the route
549 	 *	- Reset statistics
550 	 *
551 	 * If a flow doesn't exist allocate a new one if
552 	 * ip6_maxflows hasn't reached its limit. If it has
553 	 * been reached, reap some flows.
554 	 */
555 	ip6f = ip6flow_lookup(ip6);
556 	if (ip6f == NULL) {
557 		if (ip6flow_inuse >= ip6_maxflows) {
558 			ip6f = ip6flow_reap_locked(1);
559 		} else {
560 			ip6f = pool_get(&ip6flow_pool, PR_NOWAIT);
561 			if (ip6f == NULL)
562 				goto out;
563 			ip6flow_inuse++;
564 		}
565 		memset(ip6f, 0, sizeof(*ip6f));
566 	} else {
567 		IP6FLOW_REMOVE(ip6f);
568 
569 		ip6flow_addstats(ip6f);
570 		rtcache_free(&ip6f->ip6f_ro);
571 		ip6f->ip6f_uses = 0;
572 		ip6f->ip6f_last_uses = 0;
573 		ip6f->ip6f_dropped = 0;
574 		ip6f->ip6f_forwarded = 0;
575 	}
576 
577 	/*
578 	 * Fill in the updated/new details.
579 	 */
580 	rtcache_copy(&ip6f->ip6f_ro, ro);
581 	ip6f->ip6f_dst = ip6->ip6_dst;
582 	ip6f->ip6f_src = ip6->ip6_src;
583 	ip6f->ip6f_flow = ip6->ip6_flow;
584 	PRT_SLOW_ARM(ip6f->ip6f_timer, IP6FLOW_TIMER);
585 
586 	/*
587 	 * Insert into the approriate bucket of the flow table.
588 	 */
589 	hash = ip6flow_hash(ip6);
590 	IP6FLOW_INSERT(&ip6flowtable[hash], ip6f);
591 
592  out:
593 	KERNEL_UNLOCK_ONE(NULL);
594 	mutex_exit(&ip6flow_lock);
595 }
596 
597 /*
598  * Invalidate/remove all flows - if new_size is positive we
599  * resize the hash table.
600  */
601 int
602 ip6flow_invalidate_all(int new_size)
603 {
604 	struct ip6flow *ip6f, *next_ip6f;
605 	int error;
606 
607 	error = 0;
608 
609 	mutex_enter(&ip6flow_lock);
610 
611 	for (ip6f = LIST_FIRST(&ip6flowlist); ip6f != NULL; ip6f = next_ip6f) {
612 		next_ip6f = LIST_NEXT(ip6f, ip6f_list);
613 		ip6flow_free(ip6f);
614 	}
615 
616 	if (new_size)
617 		error = ip6flow_init_locked(new_size);
618 
619 	mutex_exit(&ip6flow_lock);
620 
621 	return error;
622 }
623