1/*	$NetBSD: ip6_flow.c,v 1.19.2.1 2012/10/31 16:07:46 riz 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.19.2.1 2012/10/31 16:07:46 riz 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
80static struct pool ip6flow_pool;
81
82LIST_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
91static struct ip6flowhead *ip6flowtable = NULL;
92static struct ip6flowhead ip6flowlist;
93static int ip6flow_inuse;
94
95/*
96 * Insert an ip6flow into the list.
97 */
98#define	IP6FLOW_INSERT(bucket, ip6f) \
99do { \
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) \
108do { \
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
117int ip6_maxflows = IP6FLOW_DEFAULT;
118int ip6_hashsize = IP6FLOW_DEFAULT_HASHSIZE;
119
120/*
121 * Calculate hash table position.
122 */
123static size_t
124ip6flow_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 */
146static struct ip6flow *
147ip6flow_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
166void
167ip6flow_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 */
180int
181ip6flow_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 */
210int
211ip6flow_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	    	/* Route or interface is down */
280		return 0;
281	}
282
283	/*
284	 * Packet size greater than MTU?
285	 */
286	if (m->m_pkthdr.len > rt->rt_ifp->if_mtu) {
287		/* Return to main IPv6 input function. */
288		return 0;
289	}
290
291	if (ip6->ip6_hlim <= IPV6_HLIMDEC)
292		return 0;
293
294	/* Decrement hop limit (same as TTL) */
295	ip6->ip6_hlim -= IPV6_HLIMDEC;
296
297	if (rt->rt_flags & RTF_GATEWAY)
298		dst = rt->rt_gateway;
299	else
300		dst = rtcache_getdst(&ip6f->ip6f_ro);
301
302	PRT_SLOW_ARM(ip6f->ip6f_timer, IP6FLOW_TIMER);
303
304	ip6f->ip6f_uses++;
305
306	KERNEL_LOCK(1, NULL);
307	/* Send on its way - straight to the interface output routine. */
308	if ((error = (*rt->rt_ifp->if_output)(rt->rt_ifp, m, dst, rt)) != 0) {
309		ip6f->ip6f_dropped++;
310	} else {
311		ip6f->ip6f_forwarded++;
312	}
313	KERNEL_UNLOCK_ONE(NULL);
314	return 1;
315}
316
317/*
318 * Add the IPv6 flow statistics to the main IPv6 statistics.
319 */
320static void
321ip6flow_addstats(const struct ip6flow *ip6f)
322{
323	struct rtentry *rt;
324	uint64_t *ip6s;
325
326	if ((rt = rtcache_validate(&ip6f->ip6f_ro)) != NULL)
327		rt->rt_use += ip6f->ip6f_uses;
328	ip6s = IP6_STAT_GETREF();
329	ip6s[IP6_STAT_FASTFORWARDFLOWS] = ip6flow_inuse;
330	ip6s[IP6_STAT_CANTFORWARD] += ip6f->ip6f_dropped;
331	ip6s[IP6_STAT_ODROPPED] += ip6f->ip6f_dropped;
332	ip6s[IP6_STAT_TOTAL] += ip6f->ip6f_uses;
333	ip6s[IP6_STAT_FORWARD] += ip6f->ip6f_forwarded;
334	ip6s[IP6_STAT_FASTFORWARD] += ip6f->ip6f_forwarded;
335	IP6_STAT_PUTREF();
336}
337
338/*
339 * Add statistics and free the flow.
340 */
341static void
342ip6flow_free(struct ip6flow *ip6f)
343{
344	int s;
345
346	/*
347	 * Remove the flow from the hash table (at elevated IPL).
348	 * Once it's off the list, we can deal with it at normal
349	 * network IPL.
350	 */
351	s = splnet();
352	IP6FLOW_REMOVE(ip6f);
353	splx(s);
354	ip6flow_inuse--;
355	ip6flow_addstats(ip6f);
356	rtcache_free(&ip6f->ip6f_ro);
357	pool_put(&ip6flow_pool, ip6f);
358}
359
360/*
361 * Reap one or more flows - ip6flow_reap may remove
362 * multiple flows if net.inet6.ip6.maxflows is reduced.
363 */
364struct ip6flow *
365ip6flow_reap(int just_one)
366{
367	while (just_one || ip6flow_inuse > ip6_maxflows) {
368		struct ip6flow *ip6f, *maybe_ip6f = NULL;
369		int s;
370
371		ip6f = LIST_FIRST(&ip6flowlist);
372		while (ip6f != NULL) {
373			/*
374			 * If this no longer points to a valid route -
375			 * reclaim it.
376			 */
377			if (rtcache_validate(&ip6f->ip6f_ro) == NULL)
378				goto done;
379			/*
380			 * choose the one that's been least recently
381			 * used or has had the least uses in the
382			 * last 1.5 intervals.
383			 */
384			if (maybe_ip6f == NULL ||
385			    ip6f->ip6f_timer < maybe_ip6f->ip6f_timer ||
386			    (ip6f->ip6f_timer == maybe_ip6f->ip6f_timer &&
387			     ip6f->ip6f_last_uses + ip6f->ip6f_uses <
388			         maybe_ip6f->ip6f_last_uses +
389			         maybe_ip6f->ip6f_uses))
390				maybe_ip6f = ip6f;
391			ip6f = LIST_NEXT(ip6f, ip6f_list);
392		}
393		ip6f = maybe_ip6f;
394	    done:
395		/*
396		 * Remove the entry from the flow table
397		 */
398		s = splnet();
399		IP6FLOW_REMOVE(ip6f);
400		splx(s);
401		rtcache_free(&ip6f->ip6f_ro);
402		if (just_one) {
403			ip6flow_addstats(ip6f);
404			return ip6f;
405		}
406		ip6flow_inuse--;
407		ip6flow_addstats(ip6f);
408		pool_put(&ip6flow_pool, ip6f);
409	}
410	return NULL;
411}
412
413void
414ip6flow_slowtimo(void)
415{
416	struct ip6flow *ip6f, *next_ip6f;
417
418	mutex_enter(softnet_lock);
419	KERNEL_LOCK(1, NULL);
420
421	for (ip6f = LIST_FIRST(&ip6flowlist); ip6f != NULL; ip6f = next_ip6f) {
422		next_ip6f = LIST_NEXT(ip6f, ip6f_list);
423		if (PRT_SLOW_ISEXPIRED(ip6f->ip6f_timer) ||
424		    rtcache_validate(&ip6f->ip6f_ro) == NULL) {
425			ip6flow_free(ip6f);
426		} else {
427			ip6f->ip6f_last_uses = ip6f->ip6f_uses;
428			ip6flow_addstats(ip6f);
429			ip6f->ip6f_uses = 0;
430			ip6f->ip6f_dropped = 0;
431			ip6f->ip6f_forwarded = 0;
432		}
433	}
434
435	KERNEL_UNLOCK_ONE(NULL);
436	mutex_exit(softnet_lock);
437}
438
439/*
440 * We have successfully forwarded a packet using the normal
441 * IPv6 stack. Now create/update a flow.
442 */
443void
444ip6flow_create(const struct route *ro, struct mbuf *m)
445{
446	const struct ip6_hdr *ip6;
447	struct ip6flow *ip6f;
448	size_t hash;
449	int s;
450
451	ip6 = mtod(m, const struct ip6_hdr *);
452
453	/*
454	 * If IPv6 Fast Forward is disabled, don't create a flow.
455	 * It can be disabled by setting net.inet6.ip6.maxflows to 0.
456	 *
457	 * Don't create a flow for ICMPv6 messages.
458	 */
459	if (ip6_maxflows == 0 || ip6->ip6_nxt == IPPROTO_IPV6_ICMP)
460		return;
461
462	/*
463	 * See if an existing flow exists.  If so:
464	 *	- Remove the flow
465	 *	- Add flow statistics
466	 *	- Free the route
467	 *	- Reset statistics
468	 *
469	 * If a flow doesn't exist allocate a new one if
470	 * ip6_maxflows hasn't reached its limit. If it has
471	 * been reached, reap some flows.
472	 */
473	ip6f = ip6flow_lookup(ip6);
474	if (ip6f == NULL) {
475		if (ip6flow_inuse >= ip6_maxflows) {
476			ip6f = ip6flow_reap(1);
477		} else {
478			ip6f = pool_get(&ip6flow_pool, PR_NOWAIT);
479			if (ip6f == NULL)
480				return;
481			ip6flow_inuse++;
482		}
483		memset(ip6f, 0, sizeof(*ip6f));
484	} else {
485		s = splnet();
486		IP6FLOW_REMOVE(ip6f);
487		splx(s);
488		ip6flow_addstats(ip6f);
489		rtcache_free(&ip6f->ip6f_ro);
490		ip6f->ip6f_uses = 0;
491		ip6f->ip6f_last_uses = 0;
492		ip6f->ip6f_dropped = 0;
493		ip6f->ip6f_forwarded = 0;
494	}
495
496	/*
497	 * Fill in the updated/new details.
498	 */
499	rtcache_copy(&ip6f->ip6f_ro, ro);
500	ip6f->ip6f_dst = ip6->ip6_dst;
501	ip6f->ip6f_src = ip6->ip6_src;
502	ip6f->ip6f_flow = ip6->ip6_flow;
503	PRT_SLOW_ARM(ip6f->ip6f_timer, IP6FLOW_TIMER);
504
505	/*
506	 * Insert into the approriate bucket of the flow table.
507	 */
508	hash = ip6flow_hash(ip6);
509	s = splnet();
510	IP6FLOW_INSERT(&ip6flowtable[hash], ip6f);
511	splx(s);
512}
513
514/*
515 * Invalidate/remove all flows - if new_size is positive we
516 * resize the hash table.
517 */
518int
519ip6flow_invalidate_all(int new_size)
520{
521	struct ip6flow *ip6f, *next_ip6f;
522	int s, error;
523
524	error = 0;
525	s = splnet();
526	for (ip6f = LIST_FIRST(&ip6flowlist); ip6f != NULL; ip6f = next_ip6f) {
527		next_ip6f = LIST_NEXT(ip6f, ip6f_list);
528		ip6flow_free(ip6f);
529	}
530
531	if (new_size)
532		error = ip6flow_init(new_size);
533	splx(s);
534
535	return error;
536}
537