Return to ip_flow.c CVS log

Up to [Apple XNU] / XNU / bsd / netinet

Annotation of XNU/bsd/netinet/ip_flow.c, revision 1.1

1.1     ! root        1: /*
        !             2:  * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
        !             3:  *
        !             4:  * @APPLE_LICENSE_HEADER_START@
        !             5:  * 
        !             6:  * The contents of this file constitute Original Code as defined in and
        !             7:  * are subject to the Apple Public Source License Version 1.1 (the
        !             8:  * "License").  You may not use this file except in compliance with the
        !             9:  * License.  Please obtain a copy of the License at
        !            10:  * http://www.apple.com/publicsource and read it before using this file.
        !            11:  * 
        !            12:  * This Original Code and all software distributed under the License are
        !            13:  * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
        !            14:  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
        !            15:  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
        !            16:  * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT.  Please see the
        !            17:  * License for the specific language governing rights and limitations
        !            18:  * under the License.
        !            19:  * 
        !            20:  * @APPLE_LICENSE_HEADER_END@
        !            21:  */
        !            22: /*-
        !            23:  * Copyright (c) 1998 The NetBSD Foundation, Inc.
        !            24:  * All rights reserved.
        !            25:  *
        !            26:  * This code is derived from software contributed to The NetBSD Foundation
        !            27:  * by the 3am Software Foundry ("3am").  It was developed by Matt Thomas.
        !            28:  *
        !            29:  * Redistribution and use in source and binary forms, with or without
        !            30:  * modification, are permitted provided that the following conditions
        !            31:  * are met:
        !            32:  * 1. Redistributions of source code must retain the above copyright
        !            33:  *    notice, this list of conditions and the following disclaimer.
        !            34:  * 2. Redistributions in binary form must reproduce the above copyright
        !            35:  *    notice, this list of conditions and the following disclaimer in the
        !            36:  *    documentation and/or other materials provided with the distribution.
        !            37:  * 3. All advertising materials mentioning features or use of this software
        !            38:  *    must display the following acknowledgement:
        !            39:  *     This product includes software developed by the NetBSD
        !            40:  *     Foundation, Inc. and its contributors.
        !            41:  * 4. Neither the name of The NetBSD Foundation nor the names of its
        !            42:  *    contributors may be used to endorse or promote products derived
        !            43:  *    from this software without specific prior written permission.
        !            44:  *
        !            45:  * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
        !            46:  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
        !            47:  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
        !            48:  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
        !            49:  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
        !            50:  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
        !            51:  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
        !            52:  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
        !            53:  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
        !            54:  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
        !            55:  * POSSIBILITY OF SUCH DAMAGE.
        !            56:  *
        !            57:  */
        !            58: 
        !            59: #include <sys/param.h>
        !            60: #include <sys/systm.h>
        !            61: #include <sys/malloc.h>
        !            62: #include <sys/mbuf.h>
        !            63: #include <sys/protosw.h>
        !            64: #include <sys/socket.h>
        !            65: #include <sys/kernel.h>
        !            66: 
        !            67: #include <sys/sysctl.h>
        !            68: 
        !            69: #include <net/if.h>
        !            70: #include <net/route.h>
        !            71: 
        !            72: #include <netinet/in.h>
        !            73: #include <netinet/in_systm.h>
        !            74: #include <netinet/ip.h>
        !            75: #include <netinet/in_var.h>
        !            76: #include <netinet/ip_var.h>
        !            77: #include <netinet/ip_flow.h>
        !            78: #include <net/dlil.h>
        !            79: 
        !            80: #define        IPFLOW_TIMER            (5 * PR_SLOWHZ)
        !            81: #define IPFLOW_HASHBITS                6       /* should not be a multiple of 8 */
        !            82: #define        IPFLOW_HASHSIZE         (1 << IPFLOW_HASHBITS)
        !            83: static LIST_HEAD(ipflowhead, ipflow) ipflows[IPFLOW_HASHSIZE];
        !            84: static int ipflow_inuse;
        !            85: #define        IPFLOW_MAX              256
        !            86: 
        !            87: #if ISFB31
        !            88: #else
        !            89: #define M_IPFLOW M_TEMP
        !            90: #endif
        !            91: 
        !            92: static int ipflow_active = 0;
        !            93: SYSCTL_INT(_net_inet_ip, IPCTL_FASTFORWARDING, fastforwarding, CTLFLAG_RW,
        !            94:           &ipflow_active, 0, "");
        !            95: 
        !            96: MALLOC_DEFINE(M_IPFLOW, "ip_flow", "IP flow");
        !            97: 
        !            98: static unsigned
        !            99: ipflow_hash(
        !           100:        struct in_addr dst,
        !           101:        struct in_addr src,
        !           102:        unsigned tos)
        !           103: {
        !           104:        unsigned hash = tos;
        !           105:        int idx;
        !           106:        for (idx = 0; idx < 32; idx += IPFLOW_HASHBITS)
        !           107:                hash += (dst.s_addr >> (32 - idx)) + (src.s_addr >> idx);
        !           108:        return hash & (IPFLOW_HASHSIZE-1);
        !           109: }
        !           110: 
        !           111: static struct ipflow *
        !           112: ipflow_lookup(
        !           113:        const struct ip *ip)
        !           114: {
        !           115:        unsigned hash;
        !           116:        struct ipflow *ipf;
        !           117: 
        !           118:        hash = ipflow_hash(ip->ip_dst, ip->ip_src, ip->ip_tos);
        !           119: 
        !           120:        ipf = LIST_FIRST(&ipflows[hash]);
        !           121:        while (ipf != NULL) {
        !           122:                if (ip->ip_dst.s_addr == ipf->ipf_dst.s_addr
        !           123:                    && ip->ip_src.s_addr == ipf->ipf_src.s_addr
        !           124:                    && ip->ip_tos == ipf->ipf_tos)
        !           125:                        break;
        !           126:                ipf = LIST_NEXT(ipf, ipf_next);
        !           127:        }
        !           128:        return ipf;
        !           129: }
        !           130: 
        !           131: int
        !           132: ipflow_fastforward(
        !           133:        struct mbuf *m)
        !           134: {
        !           135:        struct ip *ip;
        !           136:        struct ipflow *ipf;
        !           137:        struct rtentry *rt;
        !           138:        int error;
        !           139: 
        !           140:        /*
        !           141:         * Are we forwarding packets?  Big enough for an IP packet?
        !           142:         */
        !           143:        if (!ipforwarding || !ipflow_active || m->m_len < sizeof(struct ip))
        !           144:                return 0;
        !           145:        /*
        !           146:         * IP header with no option and valid version and length
        !           147:         */
        !           148:        ip = mtod(m, struct ip *);
        !           149:        if (ip->ip_v != IPVERSION || ip->ip_hl != (sizeof(struct ip) >> 2)
        !           150:            || ntohs(ip->ip_len) > m->m_pkthdr.len)
        !           151:                return 0;
        !           152:        /*
        !           153:         * Find a flow.
        !           154:         */
        !           155:        if ((ipf = ipflow_lookup(ip)) == NULL)
        !           156:                return 0;
        !           157: 
        !           158:        /*
        !           159:         * Route and interface still up?
        !           160:         */
        !           161:        rt = ipf->ipf_ro.ro_rt;
        !           162:        if ((rt->rt_flags & RTF_UP) == 0 || (rt->rt_ifp->if_flags & IFF_UP) == 0)
        !           163:                return 0;
        !           164: 
        !           165:        /*
        !           166:         * Packet size OK?  TTL?
        !           167:         */
        !           168:        if (m->m_pkthdr.len > rt->rt_ifp->if_mtu || ip->ip_ttl <= IPTTLDEC)
        !           169:                return 0;
        !           170: 
        !           171:        /*
        !           172:         * Everything checks out and so we can forward this packet.
        !           173:         * Modify the TTL and incrementally change the checksum.
        !           174:         */
        !           175:        ip->ip_ttl -= IPTTLDEC;
        !           176:        if (ip->ip_sum >= htons(0xffff - (IPTTLDEC << 8))) {
        !           177:                ip->ip_sum += htons(IPTTLDEC << 8) + 1;
        !           178:        } else {
        !           179:                ip->ip_sum += htons(IPTTLDEC << 8);
        !           180:        }
        !           181: 
        !           182:        /*
        !           183:         * Send the packet on its way.  All we can get back is ENOBUFS
        !           184:         */
        !           185:        ipf->ipf_uses++;
        !           186:        ipf->ipf_timer = IPFLOW_TIMER;
        !           187: 
        !           188:        /* Not sure the rt_dlt is valid here !! XXX */
        !           189:        if ((error = dlil_output((u_long)rt->rt_dlt, m, (caddr_t) rt, &ipf->ipf_ro.ro_dst, 0)) != 0) {
        !           190:                if (error == ENOBUFS)
        !           191:                        ipf->ipf_dropped++;
        !           192:                else
        !           193:                        ipf->ipf_errors++;
        !           194:        }
        !           195:        return 1;
        !           196: }
        !           197: 
        !           198: static void
        !           199: ipflow_addstats(
        !           200:        struct ipflow *ipf)
        !           201: {
        !           202:        ipf->ipf_ro.ro_rt->rt_use += ipf->ipf_uses;
        !           203:        ipstat.ips_cantforward += ipf->ipf_errors + ipf->ipf_dropped;
        !           204:        ipstat.ips_forward += ipf->ipf_uses;
        !           205:        ipstat.ips_fastforward += ipf->ipf_uses;
        !           206: }
        !           207: 
        !           208: static void
        !           209: ipflow_free(
        !           210:        struct ipflow *ipf)
        !           211: {
        !           212:        int s;
        !           213:        /*
        !           214:         * Remove the flow from the hash table (at elevated IPL).
        !           215:         * Once it's off the list, we can deal with it at normal
        !           216:         * network IPL.
        !           217:         */
        !           218:        s = splimp();
        !           219:        LIST_REMOVE(ipf, ipf_next);
        !           220:        splx(s);
        !           221:        ipflow_addstats(ipf);
        !           222:        RTFREE(ipf->ipf_ro.ro_rt);
        !           223:        ipflow_inuse--;
        !           224:        FREE(ipf, M_IPFLOW);
        !           225: }
        !           226: 
        !           227: static struct ipflow *
        !           228: ipflow_reap(
        !           229:        void)
        !           230: {
        !           231:        struct ipflow *ipf, *maybe_ipf = NULL;
        !           232:        int idx;
        !           233:        int s;
        !           234: 
        !           235:        for (idx = 0; idx < IPFLOW_HASHSIZE; idx++) {
        !           236:                ipf = LIST_FIRST(&ipflows[idx]);
        !           237:                while (ipf != NULL) {
        !           238:                        /*
        !           239:                         * If this no longer points to a valid route
        !           240:                         * reclaim it.
        !           241:                         */
        !           242:                        if ((ipf->ipf_ro.ro_rt->rt_flags & RTF_UP) == 0)
        !           243:                                goto done;
        !           244:                        /*
        !           245:                         * choose the one that's been least recently used
        !           246:                         * or has had the least uses in the last 1.5 
        !           247:                         * intervals.
        !           248:                         */
        !           249:                        if (maybe_ipf == NULL
        !           250:                            || ipf->ipf_timer < maybe_ipf->ipf_timer
        !           251:                            || (ipf->ipf_timer == maybe_ipf->ipf_timer
        !           252:                                && ipf->ipf_last_uses + ipf->ipf_uses <
        !           253:                                      maybe_ipf->ipf_last_uses +
        !           254:                                        maybe_ipf->ipf_uses))
        !           255:                                maybe_ipf = ipf;
        !           256:                        ipf = LIST_NEXT(ipf, ipf_next);
        !           257:                }
        !           258:        }
        !           259:        ipf = maybe_ipf;
        !           260:     done:
        !           261:        /*
        !           262:         * Remove the entry from the flow table.
        !           263:         */
        !           264:        s = splimp();
        !           265:        LIST_REMOVE(ipf, ipf_next);
        !           266:        splx(s);
        !           267:        ipflow_addstats(ipf);
        !           268:        RTFREE(ipf->ipf_ro.ro_rt);
        !           269:        return ipf;
        !           270: }
        !           271: 
        !           272: void
        !           273: ipflow_slowtimo(
        !           274:        void)
        !           275: {
        !           276:        struct ipflow *ipf;
        !           277:        int idx;
        !           278: 
        !           279:        for (idx = 0; idx < IPFLOW_HASHSIZE; idx++) {
        !           280:                ipf = LIST_FIRST(&ipflows[idx]);
        !           281:                while (ipf != NULL) {
        !           282:                        struct ipflow *next_ipf = LIST_NEXT(ipf, ipf_next);
        !           283:                        if (--ipf->ipf_timer == 0) {
        !           284:                                ipflow_free(ipf);
        !           285:                        } else {
        !           286:                                ipf->ipf_last_uses = ipf->ipf_uses;
        !           287:                                ipf->ipf_ro.ro_rt->rt_use += ipf->ipf_uses;
        !           288:                                ipstat.ips_forward += ipf->ipf_uses;
        !           289:                                ipstat.ips_fastforward += ipf->ipf_uses;
        !           290:                                ipf->ipf_uses = 0;
        !           291:                        }
        !           292:                        ipf = next_ipf;
        !           293:                }
        !           294:        }
        !           295: }
        !           296: 
        !           297: void
        !           298: ipflow_create(
        !           299:        const struct route *ro,
        !           300:        struct mbuf *m)
        !           301: {
        !           302:        const struct ip *const ip = mtod(m, struct ip *);
        !           303:        struct ipflow *ipf;
        !           304:        unsigned hash;
        !           305:        int s;
        !           306: 
        !           307:        /*
        !           308:         * Don't create cache entries for ICMP messages.
        !           309:         */
        !           310:        if (!ipflow_active || ip->ip_p == IPPROTO_ICMP)
        !           311:                return;
        !           312:        /*
        !           313:         * See if an existing flow struct exists.  If so remove it from it's
        !           314:         * list and free the old route.  If not, try to malloc a new one
        !           315:         * (if we aren't at our limit).
        !           316:         */
        !           317:        ipf = ipflow_lookup(ip);
        !           318:        if (ipf == NULL) {
        !           319:                if (ipflow_inuse == IPFLOW_MAX) {
        !           320:                        ipf = ipflow_reap();
        !           321:                } else {
        !           322:                        ipf = (struct ipflow *) _MALLOC(sizeof(*ipf), M_IPFLOW,
        !           323:                                                       M_NOWAIT);
        !           324:                        if (ipf == NULL)
        !           325:                                return;
        !           326:                        ipflow_inuse++;
        !           327:                }
        !           328:                bzero((caddr_t) ipf, sizeof(*ipf));
        !           329:        } else {
        !           330:                s = splimp();
        !           331:                LIST_REMOVE(ipf, ipf_next);
        !           332:                splx(s);
        !           333:                ipflow_addstats(ipf);
        !           334:                RTFREE(ipf->ipf_ro.ro_rt);
        !           335:                ipf->ipf_uses = ipf->ipf_last_uses = 0;
        !           336:                ipf->ipf_errors = ipf->ipf_dropped = 0;
        !           337:        }
        !           338: 
        !           339:        /*
        !           340:         * Fill in the updated information.
        !           341:         */
        !           342:        ipf->ipf_ro = *ro;
        !           343:        ro->ro_rt->rt_refcnt++;
        !           344:        ipf->ipf_dst = ip->ip_dst;
        !           345:        ipf->ipf_src = ip->ip_src;
        !           346:        ipf->ipf_tos = ip->ip_tos;
        !           347:        ipf->ipf_timer = IPFLOW_TIMER;
        !           348:        /*
        !           349:         * Insert into the approriate bucket of the flow table.
        !           350:         */
        !           351:        hash = ipflow_hash(ip->ip_dst, ip->ip_src, ip->ip_tos);
        !           352:        s = splimp();
        !           353:        LIST_INSERT_HEAD(&ipflows[hash], ipf, ipf_next);
        !           354:        splx(s);
        !           355: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.