1 /* $NetBSD: ip6_flow.c,v 1.10 2007/12/11 12:30:20 lukem 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 * 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 __KERNEL_RCSID(0, "$NetBSD: ip6_flow.c,v 1.10 2007/12/11 12:30:20 lukem Exp $"); 49 50 #include <sys/param.h> 51 #include <sys/systm.h> 52 #include <sys/malloc.h> 53 #include <sys/mbuf.h> 54 #include <sys/domain.h> 55 #include <sys/protosw.h> 56 #include <sys/socket.h> 57 #include <sys/socketvar.h> 58 #include <sys/time.h> 59 #include <sys/kernel.h> 60 #include <sys/pool.h> 61 #include <sys/sysctl.h> 62 63 #include <net/if.h> 64 #include <net/if_dl.h> 65 #include <net/route.h> 66 #include <net/pfil.h> 67 68 #include <netinet/in.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_DEFAULT_HASHSIZE (1 << IP6FLOW_HASHBITS) 97 98 static struct ip6flowhead *ip6flowtable = NULL; 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 int ip6_hashsize = IP6FLOW_DEFAULT_HASHSIZE; 126 127 /* 128 * Calculate hash table position. 129 */ 130 static size_t 131 ip6flow_hash(struct ip6_hdr *ip6) 132 { 133 size_t hash; 134 uint32_t dst_sum, src_sum; 135 size_t idx; 136 137 src_sum = ip6->ip6_src.s6_addr32[0] + ip6->ip6_src.s6_addr32[1] 138 + ip6->ip6_src.s6_addr32[2] + ip6->ip6_src.s6_addr32[3]; 139 dst_sum = ip6->ip6_dst.s6_addr32[0] + ip6->ip6_dst.s6_addr32[1] 140 + ip6->ip6_dst.s6_addr32[2] + ip6->ip6_dst.s6_addr32[3]; 141 142 hash = ip6->ip6_flow; 143 144 for (idx = 0; idx < 32; idx += IP6FLOW_HASHBITS) 145 hash += (dst_sum >> (32 - idx)) + (src_sum >> idx); 146 147 return hash & (ip6_hashsize-1); 148 } 149 150 /* 151 * Check to see if a flow already exists - if so return it. 152 */ 153 static struct ip6flow * 154 ip6flow_lookup(struct ip6_hdr *ip6) 155 { 156 size_t hash; 157 struct ip6flow *ip6f; 158 159 hash = ip6flow_hash(ip6); 160 161 LIST_FOREACH(ip6f, &ip6flowtable[hash], ip6f_hash) { 162 if (IN6_ARE_ADDR_EQUAL(&ip6->ip6_dst, &ip6f->ip6f_dst) 163 && IN6_ARE_ADDR_EQUAL(&ip6->ip6_src, &ip6f->ip6f_src) 164 && ip6f->ip6f_flow == ip6->ip6_flow) { 165 /* A cached flow has been found. */ 166 return ip6f; 167 } 168 } 169 170 return NULL; 171 } 172 173 /* 174 * Allocate memory and initialise lists. This function is called 175 * from ip6_init and called there after to resize the hash table. 176 * If a newly sized table cannot be malloc'ed we just continue 177 * to use the old one. 178 */ 179 int 180 ip6flow_init(int table_size) 181 { 182 struct ip6flowhead *new_table; 183 size_t i; 184 185 new_table = (struct ip6flowhead *)malloc(sizeof(struct ip6flowhead) * 186 table_size, M_RTABLE, M_NOWAIT); 187 188 if (new_table == NULL) 189 return 1; 190 191 if (ip6flowtable != NULL) 192 free(ip6flowtable, M_RTABLE); 193 194 ip6flowtable = new_table; 195 ip6_hashsize = table_size; 196 197 LIST_INIT(&ip6flowlist); 198 for (i = 0; i < ip6_hashsize; i++) 199 LIST_INIT(&ip6flowtable[i]); 200 201 return 0; 202 } 203 204 /* 205 * IPv6 Fast Forward routine. Attempt to forward the packet - 206 * if any problems are found return to the main IPv6 input 207 * routine to deal with. 208 */ 209 int 210 ip6flow_fastforward(struct mbuf *m) 211 { 212 struct ip6flow *ip6f; 213 struct ip6_hdr *ip6; 214 struct rtentry *rt; 215 const struct sockaddr *dst; 216 int error; 217 218 /* 219 * Are we forwarding packets and have flows? 220 */ 221 if (!ip6_forwarding || ip6flow_inuse == 0) 222 return 0; 223 224 /* 225 * At least size of IPv6 Header? 226 */ 227 if (m->m_len < sizeof(struct ip6_hdr)) 228 return 0; 229 /* 230 * Was packet received as a link-level multicast or broadcast? 231 * If so, don't try to fast forward. 232 */ 233 if ((m->m_flags & (M_BCAST|M_MCAST)) != 0) 234 return 0; 235 236 if (IP6_HDR_ALIGNED_P(mtod(m, void *)) == 0) { 237 if ((m = m_copyup(m, sizeof(struct ip6_hdr), 238 (max_linkhdr + 3) & ~3)) == NULL) { 239 return 0; 240 } 241 } else if (__predict_false(m->m_len < sizeof(struct ip6_hdr))) { 242 if ((m = m_pullup(m, sizeof(struct ip6_hdr))) == NULL) { 243 return 0; 244 } 245 } 246 247 ip6 = mtod(m, struct ip6_hdr *); 248 249 if ((ip6->ip6_vfc & IPV6_VERSION_MASK) != IPV6_VERSION) { 250 /* Bad version. */ 251 return 0; 252 } 253 254 /* 255 * If we have a hop-by-hop extension we must process it. 256 * We just leave this up to ip6_input to deal with. 257 */ 258 if (ip6->ip6_nxt == IPPROTO_HOPOPTS) 259 return 0; 260 261 /* 262 * Attempt to find a flow. 263 */ 264 if ((ip6f = ip6flow_lookup(ip6)) == NULL) { 265 /* No flow found. */ 266 return 0; 267 } 268 269 /* 270 * Route and interface still up? 271 */ 272 if (rtcache_down(&ip6f->ip6f_ro) || 273 (rt = ip6f->ip6f_ro.ro_rt) == 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(struct ip6flow *ip6f) 317 { 318 if (!rtcache_down(&ip6f->ip6f_ro) && ip6f->ip6f_ro.ro_rt != NULL) 319 ip6f->ip6f_ro.ro_rt->rt_use += ip6f->ip6f_uses; 320 ip6stat.ip6s_fastforwardflows = ip6flow_inuse; 321 ip6stat.ip6s_cantforward += ip6f->ip6f_dropped; 322 ip6stat.ip6s_odropped += ip6f->ip6f_dropped; 323 ip6stat.ip6s_total += ip6f->ip6f_uses; 324 ip6stat.ip6s_forward += ip6f->ip6f_forwarded; 325 ip6stat.ip6s_fastforward += ip6f->ip6f_forwarded; 326 } 327 328 /* 329 * Add statistics and free the flow. 330 */ 331 static void 332 ip6flow_free(struct ip6flow *ip6f) 333 { 334 int s; 335 336 /* 337 * Remove the flow from the hash table (at elevated IPL). 338 * Once it's off the list, we can deal with it at normal 339 * network IPL. 340 */ 341 s = splnet(); 342 IP6FLOW_REMOVE(ip6f); 343 splx(s); 344 ip6flow_inuse--; 345 ip6flow_addstats(ip6f); 346 rtcache_free(&ip6f->ip6f_ro); 347 pool_put(&ip6flow_pool, ip6f); 348 } 349 350 /* 351 * Reap one or more flows - ip6flow_reap may remove 352 * multiple flows if net.inet6.ip6.maxflows is reduced. 353 */ 354 struct ip6flow * 355 ip6flow_reap(int just_one) 356 { 357 while (just_one || ip6flow_inuse > ip6_maxflows) { 358 struct ip6flow *ip6f, *maybe_ip6f = NULL; 359 int s; 360 361 ip6f = LIST_FIRST(&ip6flowlist); 362 while (ip6f != NULL) { 363 /* 364 * If this no longer points to a valid route - 365 * reclaim it. 366 */ 367 if (rtcache_down(&ip6f->ip6f_ro) || 368 ip6f->ip6f_ro.ro_rt == NULL) 369 goto done; 370 /* 371 * choose the one that's been least recently 372 * used or has had the least uses in the 373 * last 1.5 intervals. 374 */ 375 if (maybe_ip6f == NULL || 376 ip6f->ip6f_timer < maybe_ip6f->ip6f_timer || 377 (ip6f->ip6f_timer == maybe_ip6f->ip6f_timer && 378 ip6f->ip6f_last_uses + ip6f->ip6f_uses < 379 maybe_ip6f->ip6f_last_uses + 380 maybe_ip6f->ip6f_uses)) 381 maybe_ip6f = ip6f; 382 ip6f = LIST_NEXT(ip6f, ip6f_list); 383 } 384 ip6f = maybe_ip6f; 385 done: 386 /* 387 * Remove the entry from the flow table 388 */ 389 s = splnet(); 390 IP6FLOW_REMOVE(ip6f); 391 splx(s); 392 rtcache_free(&ip6f->ip6f_ro); 393 if (just_one) { 394 ip6flow_addstats(ip6f); 395 return ip6f; 396 } 397 ip6flow_inuse--; 398 ip6flow_addstats(ip6f); 399 pool_put(&ip6flow_pool, ip6f); 400 } 401 return NULL; 402 } 403 404 void 405 ip6flow_slowtimo(void) 406 { 407 struct ip6flow *ip6f, *next_ip6f; 408 409 for (ip6f = LIST_FIRST(&ip6flowlist); ip6f != NULL; ip6f = next_ip6f) { 410 next_ip6f = LIST_NEXT(ip6f, ip6f_list); 411 if (PRT_SLOW_ISEXPIRED(ip6f->ip6f_timer) || 412 rtcache_down(&ip6f->ip6f_ro) || 413 ip6f->ip6f_ro.ro_rt == NULL) { 414 ip6flow_free(ip6f); 415 } else { 416 ip6f->ip6f_last_uses = ip6f->ip6f_uses; 417 ip6flow_addstats(ip6f); 418 ip6f->ip6f_uses = 0; 419 ip6f->ip6f_dropped = 0; 420 ip6f->ip6f_forwarded = 0; 421 } 422 } 423 } 424 425 /* 426 * We have successfully forwarded a packet using the normal 427 * IPv6 stack. Now create/update a flow. 428 */ 429 void 430 ip6flow_create(const struct route *ro, struct mbuf *m) 431 { 432 struct ip6_hdr *ip6; 433 struct ip6flow *ip6f; 434 size_t hash; 435 int s; 436 437 ip6 = mtod(m, struct ip6_hdr *); 438 439 /* 440 * If IPv6 Fast Forward is disabled, don't create a flow. 441 * It can be disabled by setting net.inet6.ip6.maxflows to 0. 442 * 443 * Don't create a flow for ICMPv6 messages. 444 */ 445 if (ip6_maxflows == 0 || ip6->ip6_nxt == IPPROTO_IPV6_ICMP) 446 return; 447 448 /* 449 * See if an existing flow exists. If so: 450 * - Remove the flow 451 * - Add flow statistics 452 * - Free the route 453 * - Reset statistics 454 * 455 * If a flow doesn't exist allocate a new one if 456 * ip6_maxflows hasn't reached its limit. If it has 457 * been reached, reap some flows. 458 */ 459 ip6f = ip6flow_lookup(ip6); 460 if (ip6f == NULL) { 461 if (ip6flow_inuse >= ip6_maxflows) { 462 ip6f = ip6flow_reap(1); 463 } else { 464 ip6f = pool_get(&ip6flow_pool, PR_NOWAIT); 465 if (ip6f == NULL) 466 return; 467 ip6flow_inuse++; 468 } 469 memset(ip6f, 0, sizeof(*ip6f)); 470 } else { 471 s = splnet(); 472 IP6FLOW_REMOVE(ip6f); 473 splx(s); 474 ip6flow_addstats(ip6f); 475 rtcache_free(&ip6f->ip6f_ro); 476 ip6f->ip6f_uses = 0; 477 ip6f->ip6f_last_uses = 0; 478 ip6f->ip6f_dropped = 0; 479 ip6f->ip6f_forwarded = 0; 480 } 481 482 /* 483 * Fill in the updated/new details. 484 */ 485 rtcache_copy(&ip6f->ip6f_ro, ro); 486 ip6f->ip6f_dst = ip6->ip6_dst; 487 ip6f->ip6f_src = ip6->ip6_src; 488 ip6f->ip6f_flow = ip6->ip6_flow; 489 PRT_SLOW_ARM(ip6f->ip6f_timer, IP6FLOW_TIMER); 490 ip6f->ip6f_start = time_uptime; 491 492 /* 493 * Insert into the approriate bucket of the flow table. 494 */ 495 hash = ip6flow_hash(ip6); 496 s = splnet(); 497 IP6FLOW_INSERT(&ip6flowtable[hash], ip6f); 498 splx(s); 499 } 500 501 /* 502 * Invalidate/remove all flows - if new_size is positive we 503 * resize the hash table. 504 */ 505 int 506 ip6flow_invalidate_all(int new_size) 507 { 508 struct ip6flow *ip6f, *next_ip6f; 509 int s, error; 510 511 error = 0; 512 s = splnet(); 513 for (ip6f = LIST_FIRST(&ip6flowlist); ip6f != NULL; ip6f = next_ip6f) { 514 next_ip6f = LIST_NEXT(ip6f, ip6f_list); 515 ip6flow_free(ip6f); 516 } 517 518 if (new_size) 519 error = ip6flow_init(new_size); 520 splx(s); 521 522 return error; 523 } 524