ipid: Call ip_randomid() on all CPUs.
[dragonfly.git] / sys / netinet / ip_flow.c
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_TIMEOUT_FREQ     2       /* 2/second */
64 #define IPFLOW_TIMEOUT          (hz / IPFLOW_TIMEOUT_FREQ)
65
66 #define IPFLOW_TIMER            (5 * IPFLOW_TIMEOUT_FREQ)
67 #define IPFLOW_HASHBITS         6       /* should not be a multiple of 8 */
68 #define IPFLOW_HASHSIZE         (1 << IPFLOW_HASHBITS)
69 #define IPFLOW_MAX              256
70
71 #define IPFLOW_RTENTRY_ISDOWN(rt) \
72         (((rt)->rt_flags & RTF_UP) == 0 || \
73          ((rt)->rt_ifp->if_flags & IFF_UP) == 0)
74
75 struct netmsg_ipfaddr {
76         struct netmsg_base base;
77         struct in_addr  ipf_addr;
78 };
79
80 struct ipflow {
81         LIST_ENTRY(ipflow) ipf_hash;    /* next ipflow in hash bucket */
82         LIST_ENTRY(ipflow) ipf_list;    /* next ipflow in list */
83
84         struct in_addr ipf_dst;         /* destination address */
85         struct in_addr ipf_src;         /* source address */
86         uint8_t ipf_tos;                /* type-of-service */
87
88         uint8_t ipf_flags;              /* see IPFLOW_FLAG_ */
89         uint8_t ipf_pad[2];             /* explicit pad */
90         int ipf_refcnt;                 /* reference count */
91
92         struct route ipf_ro;            /* associated route entry */
93         u_long ipf_uses;                /* number of uses in this period */
94
95         int ipf_timer;                  /* remaining lifetime of this entry */
96         u_long ipf_dropped;             /* ENOBUFS returned by if_output */
97         u_long ipf_errors;              /* other errors returned by if_output */
98         u_long ipf_last_uses;           /* number of uses in last period */
99 } __cachealign;
100 LIST_HEAD(ipflowhead, ipflow);
101
102 #define IPFLOW_FLAG_ONLIST      0x1
103
104 struct ipflow_pcpu {
105         struct ipflowhead       ipf_table[IPFLOW_HASHSIZE];
106         struct ipflowhead       ipf_list;
107         int                     ipf_inuse;
108         struct callout          ipf_timeo;
109         struct netmsg_base      ipf_timeo_netmsg;
110 } __cachealign;
111
112 static struct ipflow_pcpu       *ipflow_pcpu_data;
113
114 #define ipflow_inuse            ipflow_pcpu_data[mycpuid].ipf_inuse
115 #define ipflowtable             ipflow_pcpu_data[mycpuid].ipf_table
116 #define ipflowlist              ipflow_pcpu_data[mycpuid].ipf_list
117
118 static int                      ipflow_active = 0;
119
120 #define IPFLOW_REFCNT_INIT      1
121
122 /* ipflow is alive and active */
123 #define IPFLOW_IS_ACTIVE(ipf)   ((ipf)->ipf_refcnt > IPFLOW_REFCNT_INIT)
124 /* ipflow is alive but not active */
125 #define IPFLOW_NOT_ACTIVE(ipf)  ((ipf)->ipf_refcnt == IPFLOW_REFCNT_INIT)
126
127 #define IPFLOW_REF(ipf) \
128 do { \
129         KKASSERT((ipf)->ipf_refcnt > 0); \
130         (ipf)->ipf_refcnt++; \
131 } while (0)
132
133 #define IPFLOW_FREE(ipf) \
134 do { \
135         KKASSERT((ipf)->ipf_refcnt > 0); \
136         (ipf)->ipf_refcnt--; \
137         if ((ipf)->ipf_refcnt == 0) \
138                 ipflow_free((ipf)); \
139 } while (0)
140
141 #define IPFLOW_INSERT(bucket, ipf) \
142 do { \
143         KKASSERT(((ipf)->ipf_flags & IPFLOW_FLAG_ONLIST) == 0); \
144         (ipf)->ipf_flags |= IPFLOW_FLAG_ONLIST; \
145         LIST_INSERT_HEAD((bucket), (ipf), ipf_hash); \
146         LIST_INSERT_HEAD(&ipflowlist, (ipf), ipf_list); \
147 } while (0)
148
149 #define IPFLOW_REMOVE(ipf) \
150 do { \
151         KKASSERT((ipf)->ipf_flags & IPFLOW_FLAG_ONLIST); \
152         (ipf)->ipf_flags &= ~IPFLOW_FLAG_ONLIST; \
153         LIST_REMOVE((ipf), ipf_hash); \
154         LIST_REMOVE((ipf), ipf_list); \
155 } while (0)
156
157 SYSCTL_NODE(_net_inet_ip, OID_AUTO, ipflow, CTLFLAG_RW, 0, "ip flow");
158 SYSCTL_INT(_net_inet_ip, IPCTL_FASTFORWARDING, fastforwarding, CTLFLAG_RW,
159            &ipflow_active, 0, "Enable flow-based IP forwarding");
160
161 static MALLOC_DEFINE(M_IPFLOW, "ip_flow", "IP flow");
162
163 static void     ipflow_free(struct ipflow *);
164 static void     ipflow_timeo(void *);
165
166 static unsigned
167 ipflow_hash(struct in_addr dst, struct in_addr src, unsigned tos)
168 {
169         unsigned hash = tos + src.s_addr;
170         int idx;
171
172         for (idx = IPFLOW_HASHBITS; idx < 32; idx += IPFLOW_HASHBITS)
173                 hash += (dst.s_addr >> (32 - idx)) + (src.s_addr >> idx);
174         return hash & (IPFLOW_HASHSIZE-1);
175 }
176
177 static struct ipflow *
178 ipflow_lookup(const struct ip *ip)
179 {
180         unsigned hash;
181         struct ipflow *ipf;
182
183         hash = ipflow_hash(ip->ip_dst, ip->ip_src, ip->ip_tos);
184         LIST_FOREACH(ipf, &ipflowtable[hash], ipf_hash) {
185                 if (ip->ip_dst.s_addr == ipf->ipf_dst.s_addr &&
186                     ip->ip_src.s_addr == ipf->ipf_src.s_addr &&
187                     ip->ip_tos == ipf->ipf_tos)
188                         break;
189         }
190         return ipf;
191 }
192
193 int
194 ipflow_fastforward(struct mbuf *m)
195 {
196         struct ip *ip;
197         struct ipflow *ipf;
198         struct rtentry *rt;
199         struct sockaddr *dst;
200         struct ifnet *ifp;
201         int error, iplen;
202
203         ASSERT_NETISR_NCPUS(curthread, mycpuid);
204
205         /*
206          * Are we forwarding packets?
207          */
208         if (!ipforwarding || !ipflow_active)
209                 return 0;
210
211         /*
212          * Was packet received as a link-level multicast or broadcast?
213          * If so, don't try to fast forward..
214          */
215         if (m->m_flags & (M_BCAST | M_MCAST))
216                 return 0;
217
218         /* length checks already done in ip_hashfn() */
219         KASSERT(m->m_len >= sizeof(struct ip), ("IP header not in one mbuf"));
220         ip = mtod(m, struct ip *);
221
222         /*
223          * IP header with no option and valid version
224          */
225         if (ip->ip_v != IPVERSION || ip->ip_hl != (sizeof(struct ip) >> 2))
226                 return 0;
227
228         iplen = ntohs(ip->ip_len);
229         /* length checks already done in ip_hashfn() */
230         KASSERT(iplen >= sizeof(struct ip),
231                 ("total length less then header length"));
232         KASSERT(m->m_pkthdr.len >= iplen, ("mbuf too short"));
233
234         /*
235          * Find a flow.
236          */
237         ipf = ipflow_lookup(ip);
238         if (ipf == NULL)
239                 return 0;
240
241         /*
242          * Verify the IP header checksum.
243          */
244         if (m->m_pkthdr.csum_flags & CSUM_IP_CHECKED) {
245                 if (!(m->m_pkthdr.csum_flags & CSUM_IP_VALID))
246                         return 0;
247         } else {
248                 /* Must compute it ourselves. */
249                 if (in_cksum_hdr(ip) != 0)
250                         return 0;
251         }
252
253         /*
254          * Route and interface still up?
255          */
256         rt = ipf->ipf_ro.ro_rt;
257         if (IPFLOW_RTENTRY_ISDOWN(rt))
258                 return 0;
259         ifp = rt->rt_ifp;
260
261         /*
262          * Packet size OK?  TTL?
263          */
264         if (m->m_pkthdr.len > ifp->if_mtu || ip->ip_ttl <= IPTTLDEC)
265                 return 0;
266
267         /*
268          * Clear any in-bound checksum flags for this packet.
269          */
270         m->m_pkthdr.csum_flags = 0;
271
272         /*
273          * Everything checks out and so we can forward this packet.
274          * Modify the TTL and incrementally change the checksum.
275          * 
276          * This method of adding the checksum works on either endian CPU.
277          * If htons() is inlined, all the arithmetic is folded; otherwise
278          * the htons()s are combined by CSE due to the __const__ attribute.
279          *
280          * Don't bother using HW checksumming here -- the incremental
281          * update is pretty fast.
282          */
283         ip->ip_ttl -= IPTTLDEC;
284         if (ip->ip_sum >= (uint16_t)~htons(IPTTLDEC << 8))
285                 ip->ip_sum -= ~htons(IPTTLDEC << 8);
286         else
287                 ip->ip_sum += htons(IPTTLDEC << 8);
288
289         /*
290          * Trim the packet in case it's too long.. 
291          */
292         if (m->m_pkthdr.len > iplen) {
293                 if (m->m_len == m->m_pkthdr.len) {
294                         m->m_len = iplen;
295                         m->m_pkthdr.len = iplen;
296                 } else {
297                         m_adj(m, iplen - m->m_pkthdr.len);
298                 }
299         }
300
301         /*
302          * Send the packet on its way.  All we can get back is ENOBUFS
303          */
304         ipf->ipf_uses++;
305         ipf->ipf_timer = IPFLOW_TIMER;
306
307         if (rt->rt_flags & RTF_GATEWAY)
308                 dst = rt->rt_gateway;
309         else
310                 dst = &ipf->ipf_ro.ro_dst;
311
312         /*
313          * Reference count this ipflow, before the possible blocking
314          * ifnet.if_output(), so this ipflow will not be changed or
315          * reaped behind our back.
316          */
317         IPFLOW_REF(ipf);
318
319         error = ifp->if_output(ifp, m, dst, rt);
320         if (error) {
321                 if (error == ENOBUFS)
322                         ipf->ipf_dropped++;
323                 else
324                         ipf->ipf_errors++;
325         }
326
327         IPFLOW_FREE(ipf);
328         return 1;
329 }
330
331 static void
332 ipflow_addstats(struct ipflow *ipf)
333 {
334         ipf->ipf_ro.ro_rt->rt_use += ipf->ipf_uses;
335         ipstat.ips_cantforward += ipf->ipf_errors + ipf->ipf_dropped;
336         ipstat.ips_total += ipf->ipf_uses;
337         ipstat.ips_forward += ipf->ipf_uses;
338         ipstat.ips_fastforward += ipf->ipf_uses;
339 }
340
341 static void
342 ipflow_free(struct ipflow *ipf)
343 {
344         KKASSERT(ipf->ipf_refcnt == 0);
345         KKASSERT((ipf->ipf_flags & IPFLOW_FLAG_ONLIST) == 0);
346
347         KKASSERT(ipflow_inuse > 0);
348         ipflow_inuse--;
349
350         ipflow_addstats(ipf);
351         RTFREE(ipf->ipf_ro.ro_rt);
352         kfree(ipf, M_IPFLOW);
353 }
354
355 static void
356 ipflow_reset(struct ipflow *ipf)
357 {
358         ipflow_addstats(ipf);
359         RTFREE(ipf->ipf_ro.ro_rt);
360         ipf->ipf_uses = ipf->ipf_last_uses = 0;
361         ipf->ipf_errors = ipf->ipf_dropped = 0;
362 }
363
364 static struct ipflow *
365 ipflow_reap(void)
366 {
367         struct ipflow *ipf, *maybe_ipf = NULL;
368
369         LIST_FOREACH(ipf, &ipflowlist, ipf_list) {
370                 /*
371                  * Skip actively used ipflow
372                  */
373                 if (IPFLOW_IS_ACTIVE(ipf))
374                         continue;
375
376                 /*
377                  * If this no longer points to a valid route
378                  * reclaim it.
379                  */
380                 if ((ipf->ipf_ro.ro_rt->rt_flags & RTF_UP) == 0)
381                         goto done;
382
383                 /*
384                  * choose the one that's been least recently used
385                  * or has had the least uses in the last 1.5
386                  * intervals.
387                  */
388                 if (maybe_ipf == NULL ||
389                     ipf->ipf_timer < maybe_ipf->ipf_timer ||
390                     (ipf->ipf_timer == maybe_ipf->ipf_timer &&
391                      ipf->ipf_last_uses + ipf->ipf_uses <
392                      maybe_ipf->ipf_last_uses + maybe_ipf->ipf_uses))
393                         maybe_ipf = ipf;
394         }
395         if (maybe_ipf == NULL)
396                 return NULL;
397
398         ipf = maybe_ipf;
399 done:
400         /*
401          * Remove the entry from the flow table and reset its states
402          */
403         IPFLOW_REMOVE(ipf);
404         ipflow_reset(ipf);
405         return ipf;
406 }
407
408 static void
409 ipflow_timeo_dispatch(netmsg_t nmsg)
410 {
411         struct ipflow *ipf, *next_ipf;
412         struct ipflow_pcpu *pcpu;
413         int cpuid = mycpuid;
414
415         ASSERT_NETISR_NCPUS(curthread, cpuid);
416
417         crit_enter();
418         lwkt_replymsg(&nmsg->lmsg, 0);  /* reply ASAP */
419         crit_exit();
420
421         LIST_FOREACH_MUTABLE(ipf, &ipflowlist, ipf_list, next_ipf) {
422                 if (--ipf->ipf_timer == 0) {
423                         IPFLOW_REMOVE(ipf);
424                         IPFLOW_FREE(ipf);
425                 } else {
426                         ipf->ipf_last_uses = ipf->ipf_uses;
427                         ipf->ipf_ro.ro_rt->rt_use += ipf->ipf_uses;
428                         ipstat.ips_total += ipf->ipf_uses;
429                         ipstat.ips_forward += ipf->ipf_uses;
430                         ipstat.ips_fastforward += ipf->ipf_uses;
431                         ipf->ipf_uses = 0;
432                 }
433         }
434
435         pcpu = &ipflow_pcpu_data[cpuid];
436         callout_reset(&pcpu->ipf_timeo, IPFLOW_TIMEOUT, ipflow_timeo, pcpu);
437 }
438
439 static void
440 ipflow_timeo(void *xpcpu)
441 {
442         struct ipflow_pcpu *pcpu = xpcpu;
443         struct lwkt_msg *msg = &pcpu->ipf_timeo_netmsg.lmsg;
444
445         crit_enter();
446         if (msg->ms_flags & MSGF_DONE)
447                 lwkt_sendmsg_oncpu(netisr_cpuport(mycpuid), msg);
448         crit_exit();
449 }
450
451 void
452 ipflow_create(const struct route *ro, struct mbuf *m)
453 {
454         const struct ip *const ip = mtod(m, struct ip *);
455         struct ipflow *ipf;
456         unsigned hash;
457
458         ASSERT_NETISR_NCPUS(curthread, mycpuid);
459
460         /*
461          * Don't create cache entries for ICMP messages.
462          */
463         if (!ipflow_active || ip->ip_p == IPPROTO_ICMP)
464                 return;
465
466         /*
467          * See if an existing flow struct exists.  If so remove it from it's
468          * list and free the old route.  If not, try to malloc a new one
469          * (if we aren't at our limit).
470          */
471         ipf = ipflow_lookup(ip);
472         if (ipf == NULL) {
473                 if (ipflow_inuse == IPFLOW_MAX) {
474                         ipf = ipflow_reap();
475                         if (ipf == NULL)
476                                 return;
477                 } else {
478                         ipf = kmalloc(sizeof(*ipf), M_IPFLOW,
479                                       M_NOWAIT | M_ZERO);
480                         if (ipf == NULL)
481                                 return;
482                         ipf->ipf_refcnt = IPFLOW_REFCNT_INIT;
483
484                         ipflow_inuse++;
485                 }
486         } else {
487                 if (IPFLOW_NOT_ACTIVE(ipf)) {
488                         IPFLOW_REMOVE(ipf);
489                         ipflow_reset(ipf);
490                 } else {
491                         /* This ipflow is being used; don't change it */
492                         KKASSERT(IPFLOW_IS_ACTIVE(ipf));
493                         return;
494                 }
495         }
496         /* This ipflow should not be actively used */
497         KKASSERT(IPFLOW_NOT_ACTIVE(ipf));
498
499         /*
500          * Fill in the updated information.
501          */
502         ipf->ipf_ro = *ro;
503         ro->ro_rt->rt_refcnt++;
504         ipf->ipf_dst = ip->ip_dst;
505         ipf->ipf_src = ip->ip_src;
506         ipf->ipf_tos = ip->ip_tos;
507         ipf->ipf_timer = IPFLOW_TIMER;
508
509         /*
510          * Insert into the approriate bucket of the flow table.
511          */
512         hash = ipflow_hash(ip->ip_dst, ip->ip_src, ip->ip_tos);
513         IPFLOW_INSERT(&ipflowtable[hash], ipf);
514 }
515
516 void
517 ipflow_flush_oncpu(void)
518 {
519         struct ipflow *ipf;
520
521         /*
522          * FIXME: netisr_ncpus
523          * Change this into assert, after routes are duplicated
524          * to only netisr_ncpus.
525          */
526         if (mycpuid >= netisr_ncpus)
527                 return;
528
529         while ((ipf = LIST_FIRST(&ipflowlist)) != NULL) {
530                 IPFLOW_REMOVE(ipf);
531                 IPFLOW_FREE(ipf);
532         }
533 }
534
535 static void
536 ipflow_ifaddr_handler(netmsg_t nmsg)
537 {
538         struct netmsg_ipfaddr *amsg = (struct netmsg_ipfaddr *)nmsg;
539         struct ipflow *ipf, *next_ipf;
540
541         LIST_FOREACH_MUTABLE(ipf, &ipflowlist, ipf_list, next_ipf) {
542                 if (ipf->ipf_dst.s_addr == amsg->ipf_addr.s_addr ||
543                     ipf->ipf_src.s_addr == amsg->ipf_addr.s_addr) {
544                         IPFLOW_REMOVE(ipf);
545                         IPFLOW_FREE(ipf);
546                 }
547         }
548         netisr_forwardmsg(&nmsg->base, mycpuid + 1);
549 }
550
551 static void
552 ipflow_ifaddr(void *arg __unused, struct ifnet *ifp __unused,
553               enum ifaddr_event event, struct ifaddr *ifa)
554 {
555         struct netmsg_ipfaddr amsg;
556
557         if (ifa->ifa_addr->sa_family != AF_INET)
558                 return;
559
560         /* Only add/change events need to be handled */
561         switch (event) {
562         case IFADDR_EVENT_ADD:
563         case IFADDR_EVENT_CHANGE:
564                 break;
565
566         case IFADDR_EVENT_DELETE:
567                 return;
568         }
569
570         netmsg_init(&amsg.base, NULL, &curthread->td_msgport,
571                     MSGF_PRIORITY, ipflow_ifaddr_handler);
572         amsg.ipf_addr = ifatoia(ifa)->ia_addr.sin_addr;
573
574         netisr_domsg(&amsg.base, 0);
575 }
576
577 static void
578 ipflow_init(void)
579 {
580         char oid_name[32];
581         int i;
582
583         ipflow_pcpu_data = kmalloc(sizeof(struct ipflow_pcpu) * netisr_ncpus,
584             M_IPFLOW, M_WAITOK | M_ZERO);
585
586         for (i = 0; i < netisr_ncpus; ++i) {
587                 struct ipflow_pcpu *pcpu = &ipflow_pcpu_data[i];
588
589                 netmsg_init(&pcpu->ipf_timeo_netmsg, NULL, &netisr_adone_rport,
590                     MSGF_PRIORITY, ipflow_timeo_dispatch);
591                 callout_init_mp(&pcpu->ipf_timeo);
592
593                 ksnprintf(oid_name, sizeof(oid_name), "inuse%d", i);
594
595                 SYSCTL_ADD_INT(NULL,
596                     SYSCTL_STATIC_CHILDREN(_net_inet_ip_ipflow), OID_AUTO,
597                     oid_name, CTLFLAG_RD, &pcpu->ipf_inuse, 0,
598                     "# of ip flow being used");
599
600                 callout_reset_bycpu(&pcpu->ipf_timeo, IPFLOW_TIMEOUT,
601                     ipflow_timeo, pcpu, i);
602         }
603         EVENTHANDLER_REGISTER(ifaddr_event, ipflow_ifaddr, NULL,
604                               EVENTHANDLER_PRI_ANY);
605 }
606 SYSINIT(arp, SI_SUB_PROTO_DOMAIN, SI_ORDER_ANY, ipflow_init, 0);