sys/netinet6/ip6_flow.c

   1 /*      $NetBSD: ip6_flow.c,v 1.17 2008/04/28 20:24:10 martin 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.17 2008/04/28 20:24:10 martin 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 }