1 /*- 2 * Copyright (c) 1998 The NetBSD Foundation, Inc. 3 * All rights reserved. 4 * 5 * This code is derived from software contributed to The NetBSD Foundation 6 * by the 3am Software Foundry ("3am"). It was developed by Matt Thomas. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 1. Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * 2. Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in the 15 * documentation and/or other materials provided with the distribution. 16 * 3. All advertising materials mentioning features or use of this software 17 * must display the following acknowledgement: 18 * This product includes software developed by the NetBSD 19 * Foundation, Inc. and its contributors. 20 * 4. Neither the name of The NetBSD Foundation nor the names of its 21 * contributors may be used to endorse or promote products derived 22 * from this software without specific prior written permission. 23 * 24 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 25 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 26 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 27 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 28 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 29 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 30 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 31 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 32 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 33 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 34 * POSSIBILITY OF SUCH DAMAGE. 35 * 36 * $FreeBSD: src/sys/netinet/ip_flow.c,v 1.9.2.2 2001/11/04 17:35:31 luigi Exp $ 37 */ 38 39 #include <sys/param.h> 40 #include <sys/kernel.h> 41 #include <sys/malloc.h> 42 #include <sys/mbuf.h> 43 #include <sys/protosw.h> 44 #include <sys/socket.h> 45 #include <sys/sysctl.h> 46 #include <sys/thread2.h> 47 #include <sys/in_cksum.h> 48 49 #include <machine/smp.h> 50 51 #include <net/if.h> 52 #include <net/if_var.h> 53 #include <net/route.h> 54 #include <net/netisr2.h> 55 #include <net/netmsg2.h> 56 57 #include <netinet/in.h> 58 #include <netinet/ip.h> 59 #include <netinet/in_var.h> 60 #include <netinet/ip_var.h> 61 #include <netinet/ip_flow.h> 62 63 #define IPFLOW_TIMER (5 * PR_SLOWHZ) 64 #define IPFLOW_HASHBITS 6 /* should not be a multiple of 8 */ 65 #define IPFLOW_HASHSIZE (1 << IPFLOW_HASHBITS) 66 #define IPFLOW_MAX 256 67 68 #define IPFLOW_RTENTRY_ISDOWN(rt) \ 69 (((rt)->rt_flags & RTF_UP) == 0 || \ 70 ((rt)->rt_ifp->if_flags & IFF_UP) == 0) 71 72 struct netmsg_ipfaddr { 73 struct netmsg_base base; 74 struct in_addr ipf_addr; 75 }; 76 77 struct ipflow { 78 LIST_ENTRY(ipflow) ipf_hash; /* next ipflow in hash bucket */ 79 LIST_ENTRY(ipflow) ipf_list; /* next ipflow in list */ 80 81 struct in_addr ipf_dst; /* destination address */ 82 struct in_addr ipf_src; /* source address */ 83 uint8_t ipf_tos; /* type-of-service */ 84 85 uint8_t ipf_flags; /* see IPFLOW_FLAG_ */ 86 uint8_t ipf_pad[2]; /* explicit pad */ 87 int ipf_refcnt; /* reference count */ 88 89 struct route ipf_ro; /* associated route entry */ 90 u_long ipf_uses; /* number of uses in this period */ 91 92 int ipf_timer; /* remaining lifetime of this entry */ 93 u_long ipf_dropped; /* ENOBUFS returned by if_output */ 94 u_long ipf_errors; /* other errors returned by if_output */ 95 u_long ipf_last_uses; /* number of uses in last period */ 96 }; 97 LIST_HEAD(ipflowhead, ipflow); 98 99 #define IPFLOW_FLAG_ONLIST 0x1 100 101 #define ipflow_inuse ipflow_inuse_pcpu[mycpuid] 102 #define ipflowtable ipflowtable_pcpu[mycpuid] 103 #define ipflowlist ipflowlist_pcpu[mycpuid] 104 105 static struct ipflowhead ipflowtable_pcpu[MAXCPU][IPFLOW_HASHSIZE]; 106 static struct ipflowhead ipflowlist_pcpu[MAXCPU]; 107 static int ipflow_inuse_pcpu[MAXCPU]; 108 static struct netmsg_base ipflow_timo_netmsgs[MAXCPU]; 109 static int ipflow_active = 0; 110 111 #define IPFLOW_REFCNT_INIT 1 112 113 /* ipflow is alive and active */ 114 #define IPFLOW_IS_ACTIVE(ipf) ((ipf)->ipf_refcnt > IPFLOW_REFCNT_INIT) 115 /* ipflow is alive but not active */ 116 #define IPFLOW_NOT_ACTIVE(ipf) ((ipf)->ipf_refcnt == IPFLOW_REFCNT_INIT) 117 118 #define IPFLOW_REF(ipf) \ 119 do { \ 120 KKASSERT((ipf)->ipf_refcnt > 0); \ 121 (ipf)->ipf_refcnt++; \ 122 } while (0) 123 124 #define IPFLOW_FREE(ipf) \ 125 do { \ 126 KKASSERT((ipf)->ipf_refcnt > 0); \ 127 (ipf)->ipf_refcnt--; \ 128 if ((ipf)->ipf_refcnt == 0) \ 129 ipflow_free((ipf)); \ 130 } while (0) 131 132 #define IPFLOW_INSERT(bucket, ipf) \ 133 do { \ 134 KKASSERT(((ipf)->ipf_flags & IPFLOW_FLAG_ONLIST) == 0); \ 135 (ipf)->ipf_flags |= IPFLOW_FLAG_ONLIST; \ 136 LIST_INSERT_HEAD((bucket), (ipf), ipf_hash); \ 137 LIST_INSERT_HEAD(&ipflowlist, (ipf), ipf_list); \ 138 } while (0) 139 140 #define IPFLOW_REMOVE(ipf) \ 141 do { \ 142 KKASSERT((ipf)->ipf_flags & IPFLOW_FLAG_ONLIST); \ 143 (ipf)->ipf_flags &= ~IPFLOW_FLAG_ONLIST; \ 144 LIST_REMOVE((ipf), ipf_hash); \ 145 LIST_REMOVE((ipf), ipf_list); \ 146 } while (0) 147 148 SYSCTL_NODE(_net_inet_ip, OID_AUTO, ipflow, CTLFLAG_RW, 0, "ip flow"); 149 SYSCTL_INT(_net_inet_ip, IPCTL_FASTFORWARDING, fastforwarding, CTLFLAG_RW, 150 &ipflow_active, 0, "Enable flow-based IP forwarding"); 151 152 static MALLOC_DEFINE(M_IPFLOW, "ip_flow", "IP flow"); 153 154 static void ipflow_free(struct ipflow *); 155 156 static unsigned 157 ipflow_hash(struct in_addr dst, struct in_addr src, unsigned tos) 158 { 159 unsigned hash = tos; 160 int idx; 161 162 for (idx = 0; idx < 32; idx += IPFLOW_HASHBITS) 163 hash += (dst.s_addr >> (32 - idx)) + (src.s_addr >> idx); 164 return hash & (IPFLOW_HASHSIZE-1); 165 } 166 167 static struct ipflow * 168 ipflow_lookup(const struct ip *ip) 169 { 170 unsigned hash; 171 struct ipflow *ipf; 172 173 hash = ipflow_hash(ip->ip_dst, ip->ip_src, ip->ip_tos); 174 LIST_FOREACH(ipf, &ipflowtable[hash], ipf_hash) { 175 if (ip->ip_dst.s_addr == ipf->ipf_dst.s_addr && 176 ip->ip_src.s_addr == ipf->ipf_src.s_addr && 177 ip->ip_tos == ipf->ipf_tos) 178 break; 179 } 180 return ipf; 181 } 182 183 int 184 ipflow_fastforward(struct mbuf *m) 185 { 186 struct ip *ip; 187 struct ipflow *ipf; 188 struct rtentry *rt; 189 struct sockaddr *dst; 190 struct ifnet *ifp; 191 int error, iplen; 192 193 /* 194 * Are we forwarding packets? 195 */ 196 if (!ipforwarding || !ipflow_active) 197 return 0; 198 199 /* 200 * Was packet received as a link-level multicast or broadcast? 201 * If so, don't try to fast forward.. 202 */ 203 if (m->m_flags & (M_BCAST | M_MCAST)) 204 return 0; 205 206 /* length checks already done in ip_hashfn() */ 207 KASSERT(m->m_len >= sizeof(struct ip), ("IP header not in one mbuf")); 208 ip = mtod(m, struct ip *); 209 210 /* 211 * IP header with no option and valid version 212 */ 213 if (ip->ip_v != IPVERSION || ip->ip_hl != (sizeof(struct ip) >> 2)) 214 return 0; 215 216 iplen = ntohs(ip->ip_len); 217 /* length checks already done in ip_hashfn() */ 218 KASSERT(iplen >= sizeof(struct ip), 219 ("total length less then header length")); 220 KASSERT(m->m_pkthdr.len >= iplen, ("mbuf too short")); 221 222 /* 223 * Find a flow. 224 */ 225 ipf = ipflow_lookup(ip); 226 if (ipf == NULL) 227 return 0; 228 229 /* 230 * Verify the IP header checksum. 231 */ 232 if (m->m_pkthdr.csum_flags & CSUM_IP_CHECKED) { 233 if (!(m->m_pkthdr.csum_flags & CSUM_IP_VALID)) 234 return 0; 235 } else { 236 /* Must compute it ourselves. */ 237 if (in_cksum_hdr(ip) != 0) 238 return 0; 239 } 240 241 /* 242 * Route and interface still up? 243 */ 244 rt = ipf->ipf_ro.ro_rt; 245 if (IPFLOW_RTENTRY_ISDOWN(rt)) 246 return 0; 247 ifp = rt->rt_ifp; 248 249 /* 250 * Packet size OK? TTL? 251 */ 252 if (m->m_pkthdr.len > ifp->if_mtu || ip->ip_ttl <= IPTTLDEC) 253 return 0; 254 255 /* 256 * Clear any in-bound checksum flags for this packet. 257 */ 258 m->m_pkthdr.csum_flags = 0; 259 260 /* 261 * Everything checks out and so we can forward this packet. 262 * Modify the TTL and incrementally change the checksum. 263 * 264 * This method of adding the checksum works on either endian CPU. 265 * If htons() is inlined, all the arithmetic is folded; otherwise 266 * the htons()s are combined by CSE due to the __const__ attribute. 267 * 268 * Don't bother using HW checksumming here -- the incremental 269 * update is pretty fast. 270 */ 271 ip->ip_ttl -= IPTTLDEC; 272 if (ip->ip_sum >= (uint16_t)~htons(IPTTLDEC << 8)) 273 ip->ip_sum -= ~htons(IPTTLDEC << 8); 274 else 275 ip->ip_sum += htons(IPTTLDEC << 8); 276 277 /* 278 * Trim the packet in case it's too long.. 279 */ 280 if (m->m_pkthdr.len > iplen) { 281 if (m->m_len == m->m_pkthdr.len) { 282 m->m_len = iplen; 283 m->m_pkthdr.len = iplen; 284 } else { 285 m_adj(m, iplen - m->m_pkthdr.len); 286 } 287 } 288 289 /* 290 * Send the packet on its way. All we can get back is ENOBUFS 291 */ 292 ipf->ipf_uses++; 293 ipf->ipf_timer = IPFLOW_TIMER; 294 295 if (rt->rt_flags & RTF_GATEWAY) 296 dst = rt->rt_gateway; 297 else 298 dst = &ipf->ipf_ro.ro_dst; 299 300 /* 301 * Reference count this ipflow, before the possible blocking 302 * ifnet.if_output(), so this ipflow will not be changed or 303 * reaped behind our back. 304 */ 305 IPFLOW_REF(ipf); 306 307 error = ifp->if_output(ifp, m, dst, rt); 308 if (error) { 309 if (error == ENOBUFS) 310 ipf->ipf_dropped++; 311 else 312 ipf->ipf_errors++; 313 } 314 315 IPFLOW_FREE(ipf); 316 return 1; 317 } 318 319 static void 320 ipflow_addstats(struct ipflow *ipf) 321 { 322 ipf->ipf_ro.ro_rt->rt_use += ipf->ipf_uses; 323 ipstat.ips_cantforward += ipf->ipf_errors + ipf->ipf_dropped; 324 ipstat.ips_total += ipf->ipf_uses; 325 ipstat.ips_forward += ipf->ipf_uses; 326 ipstat.ips_fastforward += ipf->ipf_uses; 327 } 328 329 static void 330 ipflow_free(struct ipflow *ipf) 331 { 332 KKASSERT(ipf->ipf_refcnt == 0); 333 KKASSERT((ipf->ipf_flags & IPFLOW_FLAG_ONLIST) == 0); 334 335 KKASSERT(ipflow_inuse > 0); 336 ipflow_inuse--; 337 338 ipflow_addstats(ipf); 339 RTFREE(ipf->ipf_ro.ro_rt); 340 kfree(ipf, M_IPFLOW); 341 } 342 343 static void 344 ipflow_reset(struct ipflow *ipf) 345 { 346 ipflow_addstats(ipf); 347 RTFREE(ipf->ipf_ro.ro_rt); 348 ipf->ipf_uses = ipf->ipf_last_uses = 0; 349 ipf->ipf_errors = ipf->ipf_dropped = 0; 350 } 351 352 static struct ipflow * 353 ipflow_reap(void) 354 { 355 struct ipflow *ipf, *maybe_ipf = NULL; 356 357 LIST_FOREACH(ipf, &ipflowlist, ipf_list) { 358 /* 359 * Skip actively used ipflow 360 */ 361 if (IPFLOW_IS_ACTIVE(ipf)) 362 continue; 363 364 /* 365 * If this no longer points to a valid route 366 * reclaim it. 367 */ 368 if ((ipf->ipf_ro.ro_rt->rt_flags & RTF_UP) == 0) 369 goto done; 370 371 /* 372 * choose the one that's been least recently used 373 * or has had the least uses in the last 1.5 374 * intervals. 375 */ 376 if (maybe_ipf == NULL || 377 ipf->ipf_timer < maybe_ipf->ipf_timer || 378 (ipf->ipf_timer == maybe_ipf->ipf_timer && 379 ipf->ipf_last_uses + ipf->ipf_uses < 380 maybe_ipf->ipf_last_uses + maybe_ipf->ipf_uses)) 381 maybe_ipf = ipf; 382 } 383 if (maybe_ipf == NULL) 384 return NULL; 385 386 ipf = maybe_ipf; 387 done: 388 /* 389 * Remove the entry from the flow table and reset its states 390 */ 391 IPFLOW_REMOVE(ipf); 392 ipflow_reset(ipf); 393 return ipf; 394 } 395 396 static void 397 ipflow_timo_dispatch(netmsg_t nmsg) 398 { 399 struct ipflow *ipf, *next_ipf; 400 401 crit_enter(); 402 lwkt_replymsg(&nmsg->lmsg, 0); /* reply ASAP */ 403 crit_exit(); 404 405 LIST_FOREACH_MUTABLE(ipf, &ipflowlist, ipf_list, next_ipf) { 406 if (--ipf->ipf_timer == 0) { 407 IPFLOW_REMOVE(ipf); 408 IPFLOW_FREE(ipf); 409 } else { 410 ipf->ipf_last_uses = ipf->ipf_uses; 411 ipf->ipf_ro.ro_rt->rt_use += ipf->ipf_uses; 412 ipstat.ips_total += ipf->ipf_uses; 413 ipstat.ips_forward += ipf->ipf_uses; 414 ipstat.ips_fastforward += ipf->ipf_uses; 415 ipf->ipf_uses = 0; 416 } 417 } 418 } 419 420 static void 421 ipflow_timo_ipi(void *arg __unused) 422 { 423 struct lwkt_msg *msg = &ipflow_timo_netmsgs[mycpuid].lmsg; 424 425 crit_enter(); 426 if (msg->ms_flags & MSGF_DONE) 427 lwkt_sendmsg_oncpu(netisr_cpuport(mycpuid), msg); 428 crit_exit(); 429 } 430 431 void 432 ipflow_slowtimo(void) 433 { 434 cpumask_t mask; 435 int i; 436 437 CPUMASK_ASSZERO(mask); 438 for (i = 0; i < ncpus; ++i) { 439 if (ipflow_inuse_pcpu[i]) 440 CPUMASK_ORBIT(mask, i); 441 } 442 CPUMASK_ANDMASK(mask, smp_active_mask); 443 if (CPUMASK_TESTNZERO(mask)) 444 lwkt_send_ipiq_mask(mask, ipflow_timo_ipi, NULL); 445 } 446 447 void 448 ipflow_create(const struct route *ro, struct mbuf *m) 449 { 450 const struct ip *const ip = mtod(m, struct ip *); 451 struct ipflow *ipf; 452 unsigned hash; 453 454 /* 455 * Don't create cache entries for ICMP messages. 456 */ 457 if (!ipflow_active || ip->ip_p == IPPROTO_ICMP) 458 return; 459 460 /* 461 * See if an existing flow struct exists. If so remove it from it's 462 * list and free the old route. If not, try to malloc a new one 463 * (if we aren't at our limit). 464 */ 465 ipf = ipflow_lookup(ip); 466 if (ipf == NULL) { 467 if (ipflow_inuse == IPFLOW_MAX) { 468 ipf = ipflow_reap(); 469 if (ipf == NULL) 470 return; 471 } else { 472 ipf = kmalloc(sizeof(*ipf), M_IPFLOW, 473 M_NOWAIT | M_ZERO); 474 if (ipf == NULL) 475 return; 476 ipf->ipf_refcnt = IPFLOW_REFCNT_INIT; 477 478 ipflow_inuse++; 479 } 480 } else { 481 if (IPFLOW_NOT_ACTIVE(ipf)) { 482 IPFLOW_REMOVE(ipf); 483 ipflow_reset(ipf); 484 } else { 485 /* This ipflow is being used; don't change it */ 486 KKASSERT(IPFLOW_IS_ACTIVE(ipf)); 487 return; 488 } 489 } 490 /* This ipflow should not be actively used */ 491 KKASSERT(IPFLOW_NOT_ACTIVE(ipf)); 492 493 /* 494 * Fill in the updated information. 495 */ 496 ipf->ipf_ro = *ro; 497 ro->ro_rt->rt_refcnt++; 498 ipf->ipf_dst = ip->ip_dst; 499 ipf->ipf_src = ip->ip_src; 500 ipf->ipf_tos = ip->ip_tos; 501 ipf->ipf_timer = IPFLOW_TIMER; 502 503 /* 504 * Insert into the approriate bucket of the flow table. 505 */ 506 hash = ipflow_hash(ip->ip_dst, ip->ip_src, ip->ip_tos); 507 IPFLOW_INSERT(&ipflowtable[hash], ipf); 508 } 509 510 void 511 ipflow_flush_oncpu(void) 512 { 513 struct ipflow *ipf; 514 515 while ((ipf = LIST_FIRST(&ipflowlist)) != NULL) { 516 IPFLOW_REMOVE(ipf); 517 IPFLOW_FREE(ipf); 518 } 519 } 520 521 static void 522 ipflow_ifaddr_handler(netmsg_t nmsg) 523 { 524 struct netmsg_ipfaddr *amsg = (struct netmsg_ipfaddr *)nmsg; 525 struct ipflow *ipf, *next_ipf; 526 527 LIST_FOREACH_MUTABLE(ipf, &ipflowlist, ipf_list, next_ipf) { 528 if (ipf->ipf_dst.s_addr == amsg->ipf_addr.s_addr || 529 ipf->ipf_src.s_addr == amsg->ipf_addr.s_addr) { 530 IPFLOW_REMOVE(ipf); 531 IPFLOW_FREE(ipf); 532 } 533 } 534 netisr_forwardmsg(&nmsg->base, mycpuid + 1); 535 } 536 537 static void 538 ipflow_ifaddr(void *arg __unused, struct ifnet *ifp __unused, 539 enum ifaddr_event event, struct ifaddr *ifa) 540 { 541 struct netmsg_ipfaddr amsg; 542 543 if (ifa->ifa_addr->sa_family != AF_INET) 544 return; 545 546 /* Only add/change events need to be handled */ 547 switch (event) { 548 case IFADDR_EVENT_ADD: 549 case IFADDR_EVENT_CHANGE: 550 break; 551 552 case IFADDR_EVENT_DELETE: 553 return; 554 } 555 556 netmsg_init(&amsg.base, NULL, &curthread->td_msgport, 557 MSGF_PRIORITY, ipflow_ifaddr_handler); 558 amsg.ipf_addr = ifatoia(ifa)->ia_addr.sin_addr; 559 560 netisr_domsg(&amsg.base, 0); 561 } 562 563 static void 564 ipflow_init(void) 565 { 566 char oid_name[32]; 567 int i; 568 569 for (i = 0; i < ncpus; ++i) { 570 netmsg_init(&ipflow_timo_netmsgs[i], NULL, &netisr_adone_rport, 571 MSGF_PRIORITY, ipflow_timo_dispatch); 572 573 ksnprintf(oid_name, sizeof(oid_name), "inuse%d", i); 574 575 SYSCTL_ADD_INT(NULL, 576 SYSCTL_STATIC_CHILDREN(_net_inet_ip_ipflow), 577 OID_AUTO, oid_name, CTLFLAG_RD, &ipflow_inuse_pcpu[i], 0, 578 "# of ip flow being used"); 579 } 580 EVENTHANDLER_REGISTER(ifaddr_event, ipflow_ifaddr, NULL, 581 EVENTHANDLER_PRI_ANY); 582 } 583 SYSINIT(arp, SI_SUB_PROTO_DOMAIN, SI_ORDER_ANY, ipflow_init, 0); 584