1 /* $NetBSD: ip6_flow.c,v 1.18 2009/03/23 18:43:20 liamjfoy 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.18 2009/03/23 18:43:20 liamjfoy 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 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 *m) 212 { 213 struct ip6flow *ip6f; 214 struct ip6_hdr *ip6; 215 struct rtentry *rt; 216 const struct sockaddr *dst; 217 int error; 218 219 /* 220 * Are we forwarding packets and have flows? 221 */ 222 if (!ip6_forwarding || ip6flow_inuse == 0) 223 return 0; 224 225 /* 226 * At least size of IPv6 Header? 227 */ 228 if (m->m_len < sizeof(struct ip6_hdr)) 229 return 0; 230 /* 231 * Was packet received as a link-level multicast or broadcast? 232 * If so, don't try to fast forward. 233 */ 234 if ((m->m_flags & (M_BCAST|M_MCAST)) != 0) 235 return 0; 236 237 if (IP6_HDR_ALIGNED_P(mtod(m, const void *)) == 0) { 238 if ((m = m_copyup(m, sizeof(struct ip6_hdr), 239 (max_linkhdr + 3) & ~3)) == NULL) { 240 return 0; 241 } 242 } else if (__predict_false(m->m_len < sizeof(struct ip6_hdr))) { 243 if ((m = m_pullup(m, sizeof(struct ip6_hdr))) == NULL) { 244 return 0; 245 } 246 } 247 248 ip6 = mtod(m, struct ip6_hdr *); 249 250 if ((ip6->ip6_vfc & IPV6_VERSION_MASK) != IPV6_VERSION) { 251 /* Bad version. */ 252 return 0; 253 } 254 255 /* 256 * If we have a hop-by-hop extension we must process it. 257 * We just leave this up to ip6_input to deal with. 258 */ 259 if (ip6->ip6_nxt == IPPROTO_HOPOPTS) 260 return 0; 261 262 /* 263 * Attempt to find a flow. 264 */ 265 if ((ip6f = ip6flow_lookup(ip6)) == NULL) { 266 /* No flow found. */ 267 return 0; 268 } 269 270 /* 271 * Route and interface still up? 272 */ 273 if ((rt = rtcache_validate(&ip6f->ip6f_ro)) == NULL || 274 (rt->rt_ifp->if_flags & IFF_UP) == 0) { 275 /* Route or interface is down */ 276 return 0; 277 } 278 279 /* 280 * Packet size greater than MTU? 281 */ 282 if (m->m_pkthdr.len > rt->rt_ifp->if_mtu) { 283 /* Return to main IPv6 input function. */ 284 return 0; 285 } 286 287 if (ip6->ip6_hlim <= IPV6_HLIMDEC) 288 return 0; 289 290 /* Decrement hop limit (same as TTL) */ 291 ip6->ip6_hlim -= IPV6_HLIMDEC; 292 293 if (rt->rt_flags & RTF_GATEWAY) 294 dst = rt->rt_gateway; 295 else 296 dst = rtcache_getdst(&ip6f->ip6f_ro); 297 298 PRT_SLOW_ARM(ip6f->ip6f_timer, IP6FLOW_TIMER); 299 300 ip6f->ip6f_uses++; 301 302 /* Send on its way - straight to the interface output routine. */ 303 if ((error = (*rt->rt_ifp->if_output)(rt->rt_ifp, m, dst, rt)) != 0) { 304 ip6f->ip6f_dropped++; 305 } else { 306 ip6f->ip6f_forwarded++; 307 } 308 309 return 1; 310 } 311 312 /* 313 * Add the IPv6 flow statistics to the main IPv6 statistics. 314 */ 315 static void 316 ip6flow_addstats(const struct ip6flow *ip6f) 317 { 318 struct rtentry *rt; 319 uint64_t *ip6s; 320 321 if ((rt = rtcache_validate(&ip6f->ip6f_ro)) != NULL) 322 rt->rt_use += ip6f->ip6f_uses; 323 ip6s = IP6_STAT_GETREF(); 324 ip6s[IP6_STAT_FASTFORWARDFLOWS] = ip6flow_inuse; 325 ip6s[IP6_STAT_CANTFORWARD] += ip6f->ip6f_dropped; 326 ip6s[IP6_STAT_ODROPPED] += ip6f->ip6f_dropped; 327 ip6s[IP6_STAT_TOTAL] += ip6f->ip6f_uses; 328 ip6s[IP6_STAT_FORWARD] += ip6f->ip6f_forwarded; 329 ip6s[IP6_STAT_FASTFORWARD] += ip6f->ip6f_forwarded; 330 IP6_STAT_PUTREF(); 331 } 332 333 /* 334 * Add statistics and free the flow. 335 */ 336 static void 337 ip6flow_free(struct ip6flow *ip6f) 338 { 339 int s; 340 341 /* 342 * Remove the flow from the hash table (at elevated IPL). 343 * Once it's off the list, we can deal with it at normal 344 * network IPL. 345 */ 346 s = splnet(); 347 IP6FLOW_REMOVE(ip6f); 348 splx(s); 349 ip6flow_inuse--; 350 ip6flow_addstats(ip6f); 351 rtcache_free(&ip6f->ip6f_ro); 352 pool_put(&ip6flow_pool, ip6f); 353 } 354 355 /* 356 * Reap one or more flows - ip6flow_reap may remove 357 * multiple flows if net.inet6.ip6.maxflows is reduced. 358 */ 359 struct ip6flow * 360 ip6flow_reap(int just_one) 361 { 362 while (just_one || ip6flow_inuse > ip6_maxflows) { 363 struct ip6flow *ip6f, *maybe_ip6f = NULL; 364 int s; 365 366 ip6f = LIST_FIRST(&ip6flowlist); 367 while (ip6f != NULL) { 368 /* 369 * If this no longer points to a valid route - 370 * reclaim it. 371 */ 372 if (rtcache_validate(&ip6f->ip6f_ro) == NULL) 373 goto done; 374 /* 375 * choose the one that's been least recently 376 * used or has had the least uses in the 377 * last 1.5 intervals. 378 */ 379 if (maybe_ip6f == NULL || 380 ip6f->ip6f_timer < maybe_ip6f->ip6f_timer || 381 (ip6f->ip6f_timer == maybe_ip6f->ip6f_timer && 382 ip6f->ip6f_last_uses + ip6f->ip6f_uses < 383 maybe_ip6f->ip6f_last_uses + 384 maybe_ip6f->ip6f_uses)) 385 maybe_ip6f = ip6f; 386 ip6f = LIST_NEXT(ip6f, ip6f_list); 387 } 388 ip6f = maybe_ip6f; 389 done: 390 /* 391 * Remove the entry from the flow table 392 */ 393 s = splnet(); 394 IP6FLOW_REMOVE(ip6f); 395 splx(s); 396 rtcache_free(&ip6f->ip6f_ro); 397 if (just_one) { 398 ip6flow_addstats(ip6f); 399 return ip6f; 400 } 401 ip6flow_inuse--; 402 ip6flow_addstats(ip6f); 403 pool_put(&ip6flow_pool, ip6f); 404 } 405 return NULL; 406 } 407 408 void 409 ip6flow_slowtimo(void) 410 { 411 struct ip6flow *ip6f, *next_ip6f; 412 413 mutex_enter(softnet_lock); 414 KERNEL_LOCK(1, NULL); 415 416 for (ip6f = LIST_FIRST(&ip6flowlist); ip6f != NULL; ip6f = next_ip6f) { 417 next_ip6f = LIST_NEXT(ip6f, ip6f_list); 418 if (PRT_SLOW_ISEXPIRED(ip6f->ip6f_timer) || 419 rtcache_validate(&ip6f->ip6f_ro) == NULL) { 420 ip6flow_free(ip6f); 421 } else { 422 ip6f->ip6f_last_uses = ip6f->ip6f_uses; 423 ip6flow_addstats(ip6f); 424 ip6f->ip6f_uses = 0; 425 ip6f->ip6f_dropped = 0; 426 ip6f->ip6f_forwarded = 0; 427 } 428 } 429 430 KERNEL_UNLOCK_ONE(NULL); 431 mutex_exit(softnet_lock); 432 } 433 434 /* 435 * We have successfully forwarded a packet using the normal 436 * IPv6 stack. Now create/update a flow. 437 */ 438 void 439 ip6flow_create(const struct route *ro, struct mbuf *m) 440 { 441 const struct ip6_hdr *ip6; 442 struct ip6flow *ip6f; 443 size_t hash; 444 int s; 445 446 ip6 = mtod(m, const struct ip6_hdr *); 447 448 /* 449 * If IPv6 Fast Forward is disabled, don't create a flow. 450 * It can be disabled by setting net.inet6.ip6.maxflows to 0. 451 * 452 * Don't create a flow for ICMPv6 messages. 453 */ 454 if (ip6_maxflows == 0 || ip6->ip6_nxt == IPPROTO_IPV6_ICMP) 455 return; 456 457 /* 458 * See if an existing flow exists. If so: 459 * - Remove the flow 460 * - Add flow statistics 461 * - Free the route 462 * - Reset statistics 463 * 464 * If a flow doesn't exist allocate a new one if 465 * ip6_maxflows hasn't reached its limit. If it has 466 * been reached, reap some flows. 467 */ 468 ip6f = ip6flow_lookup(ip6); 469 if (ip6f == NULL) { 470 if (ip6flow_inuse >= ip6_maxflows) { 471 ip6f = ip6flow_reap(1); 472 } else { 473 ip6f = pool_get(&ip6flow_pool, PR_NOWAIT); 474 if (ip6f == NULL) 475 return; 476 ip6flow_inuse++; 477 } 478 memset(ip6f, 0, sizeof(*ip6f)); 479 } else { 480 s = splnet(); 481 IP6FLOW_REMOVE(ip6f); 482 splx(s); 483 ip6flow_addstats(ip6f); 484 rtcache_free(&ip6f->ip6f_ro); 485 ip6f->ip6f_uses = 0; 486 ip6f->ip6f_last_uses = 0; 487 ip6f->ip6f_dropped = 0; 488 ip6f->ip6f_forwarded = 0; 489 } 490 491 /* 492 * Fill in the updated/new details. 493 */ 494 rtcache_copy(&ip6f->ip6f_ro, ro); 495 ip6f->ip6f_dst = ip6->ip6_dst; 496 ip6f->ip6f_src = ip6->ip6_src; 497 ip6f->ip6f_flow = ip6->ip6_flow; 498 PRT_SLOW_ARM(ip6f->ip6f_timer, IP6FLOW_TIMER); 499 ip6f->ip6f_start = time_uptime; 500 501 /* 502 * Insert into the approriate bucket of the flow table. 503 */ 504 hash = ip6flow_hash(ip6); 505 s = splnet(); 506 IP6FLOW_INSERT(&ip6flowtable[hash], ip6f); 507 splx(s); 508 } 509 510 /* 511 * Invalidate/remove all flows - if new_size is positive we 512 * resize the hash table. 513 */ 514 int 515 ip6flow_invalidate_all(int new_size) 516 { 517 struct ip6flow *ip6f, *next_ip6f; 518 int s, error; 519 520 error = 0; 521 s = splnet(); 522 for (ip6f = LIST_FIRST(&ip6flowlist); ip6f != NULL; ip6f = next_ip6f) { 523 next_ip6f = LIST_NEXT(ip6f, ip6f_list); 524 ip6flow_free(ip6f); 525 } 526 527 if (new_size) 528 error = ip6flow_init(new_size); 529 splx(s); 530 531 return error; 532 } 533