/* route.c - packet routing routines *//* Copyright 1984 - 2002 Wind River Systems, Inc. */#include "copyright_wrs.h"/* * Copyright (c) 1980, 1986, 1991, 1993 *	The Regents of the University of California.  All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright *    notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright *    notice, this list of conditions and the following disclaimer in the *    documentation and/or other materials provided with the distribution. * 3. All advertising materials mentioning features or use of this software *    must display the following acknowledgement: *	This product includes software developed by the University of *	California, Berkeley and its contributors. * 4. Neither the name of the University nor the names of its contributors *    may be used to endorse or promote products derived from this software *    without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * *	@(#)route.c	8.3 (Berkeley) 1/9/95 *//*modification history--------------------01s,14mar02,vvv  fixed route addition check for dest=gateway in rt_setgate		 (SPR #74244)01r,24jan02,niq  fixed call to new address message hook (SPR #71670)01q,03jan02,vvv  added check for rt_setgate return value in rtredirect 		 (SPR #71518)01p,05dec01,vvv  fixed NT simulator exception (SPR #71659)01o,12oct01,rae  merge from truestack ver 02e, base 01l (SPR #69683 etc.)01n,20feb01,ijm  corrected additional bug in rtalloc1.  Precedence bits		 must be cleared before searching the table.01m,02nov00,ijm  fixed rtalloc1 TOS bug, SPR# 3019501l,04mar99,spm  fixed errors in SPR #23301 fix causing build failures01k,02mar99,spm  eliminated EEXIST error caused by ARP entries (SPR #23301)01j,26aug98,n_s  added return val check for mBufClGet in rtinit. spr #22238.01i,07jul97,rjc  newer version of rtentry incorporated.01h,01jul97,vin  added route socket message hooks for scalability, fixed		 warnings.01g,30jun97,rjc  restored old rtentry size.01f,03jun97,rjc  netmask with RTF_HOST set to 0.01e,13feb97,rjc  more changes for tos routing,01e,05feb97,rjc  changes for tos routing,01d,05dec96,vin  moved ifafree() to if.c01c,22nov96,vin  added cluster support replaced m_get(..) with mBufClGet(..).01b,24sep96,vin  rtioctl() fixed for multicast addresses.01a,03mar96,vin  created from BSD4.4 stuff. added rtioctl for backward		 compatibility. moved ifa_ifwithroute() to if.c.*/#include "vxWorks.h"#include "logLib.h"#include "sysLib.h"#include "wdLib.h"#include "net/mbuf.h"#include "net/domain.h"#include "net/protosw.h"#include "sys/socket.h"#include "sys/ioctl.h"#include "net/socketvar.h"#include "errno.h"#include "net/if.h"#include "net/if_types.h"#include "net/route.h"#include "net/systm.h"#include "net/raw_cb.h"#include "routeEnhLib.h"#include "netinet/in.h"#include "netinet/in_var.h"#ifdef VIRTUAL_STACK#include "netinet/vsLib.h"#endif#ifdef NS#include <netns/ns.h>#endif#ifdef WV_INSTRUMENTATION#ifdef INCLUDE_WVNET#include "wvNetLib.h"#endif#endif#ifdef RTALLOC_DEBUG#include "stdio.h"#include "net/if_dl.h"#include "inetLib.h"LOCAL int routeEntryDebugShow (struct radix_node * newrt);#endif /* RTALLOC_DEBUG *//* externs */int	tickGet();#define	SA(p) ((struct sockaddr *)(p))#define SOCKADDR_IN(s) (((struct sockaddr_in*)(s))->sin_addr.s_addr)#define ROUTE_KILL_FREQUENCY 600    /* Check for old routes every 10 minutes */#define ROUTE_PEND_MAXIMUM  3600    /* Remove old routes after 1 hour (max). */#define ROUTE_PEND_MINIMUM  10      /* 10 second minimum for old routes. */#ifndef VIRTUAL_STACKstruct	rtstat	rtstat;struct	radix_node_head *rt_tables[AF_MAX+1];#endifstruct rtqk_arg    {    struct radix_node_head *rnh;    int draining;    int killed;    int found;    int updating;    ULONG nextstop;    };#ifndef VIRTUAL_STACKint	rttrash;		/* routes not in table but not freed */int     rtmodified = 0; 	/* route table modified */struct	sockaddr wildcard; 	/* zero valued cookie for wildcard searches */LOCAL WDOG_ID routeKillTimer; 	/* Schedules removal of expired routes. */LOCAL ULONG routeKillInterval; 	/* Removal frequency, in ticks. */LOCAL int routePendInterval; 	/* Time to keep unused routes, in ticks. */LOCAL int routePendMinimum; 	/* Minimum preservation time. */LOCAL int routePendLimit = 128;    /*                                    * Number of unused routes before                                    * reduced removal time.                                    */LOCAL int routeExpireChange = 0;                                   /* Most recent removal time adjustment. */#endifstruct radix_node * routeSwap (struct radix_node_head *, struct rtentry *,                               struct sockaddr *, struct sockaddr *);#ifdef WV_INSTRUMENTATION#ifdef INCLUDE_WVNET    /* Set common fields of event identifiers for this module. */LOCAL UCHAR wvNetModuleId = WV_NET_ROUTE_MODULE;   /* Value for route.c */LOCAL UCHAR wvNetLocalFilter = WV_NET_NONE;     /* Available event filter */LOCAL ULONG wvNetEventId;       /* Event identifier: see wvNetLib.h */#endif    /* INCLUDE_WVNET */#endifLOCAL void routeKillCheck (void);LOCAL int routeUpdate (struct radix_node *, void *);IMPORT STATUS   netJobAdd (FUNCPTR routine, int param1, int param2, int param3,                           int param4, int param5);#ifndef VIRTUAL_STACK/* * The routeStorageCreate routine replaces this version with an implementation * to initialize radix trees for a virtual stack. */voidrtable_init(table)	void **table;{	struct domain *dom;	for (dom = domains; dom; dom = dom->dom_next)		if (dom->dom_rtattach)			dom->dom_rtattach(&table[dom->dom_family],			    dom->dom_rtoffset);}#endif#ifdef VIRTUAL_STACK/********************************************************************************* routeStorageCreate - initialize the routing database** This routine sets up the radix tree and initializes the routing storage* for addresses in the AF_INET family. It mimics the more generic route_init* routine which uses the domains list to create storage for any address* type. That original routine can be compiled and used if support for* other domains is needed.** INTERNAL* Currently, this routine assumes that the caller has assigned the* correct virtual stack number allowing creation of isolated routing storage.* That process could occur internally (with the stack number as an argument)* if that approach is more convenient.** RETURNS: OK, or ERROR if initialization failed.*/STATUS routeStorageCreate (void)    {    VS_RADIX * pGlobals;    STATUS result;    pGlobals = malloc (sizeof (VS_RADIX));    if (pGlobals == NULL)        return (ERROR);    bzero ( (char *)pGlobals, sizeof (VS_RADIX));    vsTbl [myStackNum]->pRadixGlobals = pGlobals;    /*     * The radixInit() routine replaces the rn_init() routine to avoid access     * to the (currently non-virtualized) "domains" global.     */    result = radixInit (); /* initialize all zeroes, all ones, mask table */    if (result == ERROR)        {        free (pGlobals);        return (ERROR);        }   /*    * Setup any routing tables required for the available domains.     * Originally, this initialization routine executed indirectly    * through the rtable_init() routine which searched the domains    * list. This process skips that search since the only applicable    * entry involves AF_INET addresses with an offset of 27 bits    * (originally 32). The original offset skips the length, family,    * and port fields in a sockaddr_in structure. The adjusted offset    * examines five additional bits to incorporate TOS values into    * routing lookups.    *    * NOTE: The original route_init() routine (if compiled and used)    * will use the rtable_init() routine to complete the routing    * storage setup for other domains, if that capability is necessary.    */    result = rn_inithead (&rt_tables[AF_INET], 27);    if (result == 0)        {        /* Tree creation failed: release allocated memory and return. */        Free (rn_zeros);        Free (mask_rnhead);        free (pGlobals);        return (ERROR);        }    routeKillTimer = wdCreate ();    if (routeKillTimer == NULL)        {        Free (rn_zeros);        Free (mask_rnhead);        Free (rt_tables[AF_INET]);        free (pGlobals);        return (ERROR);        }    routeKillInterval = sysClkRateGet() * ROUTE_KILL_FREQUENCY;    routePendInterval = sysClkRateGet() * ROUTE_PEND_MAXIMUM;    routePendMinimum = sysClkRateGet() * ROUTE_PEND_MINIMUM;    wdStart (routeKillTimer, routeKillInterval, netJobAdd,             (int)routeKillCheck);    return (OK);    }#else/* * The routeStorageCreate routine replaces this version with an implementation * which creates an isolated set of (previously global) variables for a single * virtual stack. */introute_init(){#ifdef WV_INSTRUMENTATION#ifdef INCLUDE_WVNET    /* WV_NET_VERBOSE event */    WV_NET_MARKER_0 (NET_AUX_EVENT, WV_NET_VERBOSE, 33, 13,                     WV_NETEVENT_ROUTEINIT_START)#endif  /* INCLUDE_WVNET */#endif	rn_init();	/* initialize all zeroes, all ones, mask table */	rtable_init((void **)rt_tables);        routeKillTimer = wdCreate ();        if (routeKillTimer == NULL)            return (ERROR);        routeKillInterval = sysClkRateGet() * ROUTE_KILL_FREQUENCY;        routePendInterval = sysClkRateGet() * ROUTE_PEND_MAXIMUM;        routePendMinimum = sysClkRateGet() * ROUTE_PEND_MINIMUM;        wdStart (routeKillTimer, routeKillInterval, netJobAdd, (int) routeKillCheck);	return (OK);}#endif/* * Look for cloned routes to remote destinations which are no longer in * use. Remove any expired route entries. */void routeKillCheck (void)    {    struct radix_node_head *pHead;    struct rtqk_arg   count;    int s;    ULONG now;    pHead = rt_tables [AF_INET];    if (pHead == NULL)    /* Missing routing table. */        return;    count.found = count.killed = 0;    count.rnh = pHead;    count.nextstop = tickGet() + routeKillInterval;    count.draining = count.updating = 0;    /* Remove any old (currently unused) routes which expired. */    s = splnet ();    rn_walktree (pHead, routeUpdate, &count);    splx (s);    if (count.found - count.killed > routePendLimit)        {        /*         * The routing table still contains excessive unused routes.         * Reduce the expiration time and try to remove more entries.         */        now = tickGet ();        if ( (now - routeExpireChange >= routeKillInterval) &&            routePendInterval > routePendMinimum)            {            routePendInterval = 2 * routePendInterval / 3;            if (routePendInterval < routePendMinimum)                routePendInterval = routePendMinimum;            routeExpireChange = now;            /*             * Reset the expiration time for old (currently unused) routes             * to the new (smaller) value. Also update the "nextstop" field             * to the nearest (new) expiration time.             */            count.found = count.killed = 0;            count.updating = 1;            s = splnet ();            rn_walktree (pHead, routeUpdate, &count);            splx (s);            }        }    /*     * The routeUpdate() routine may reduce the "nextstop" value to the     * nearest expiration time of a pending route. Set the timer to      * restart at that point, or after the default interval if no old routes     * are found.     */    now = count.nextstop - tickGet ();    wdStart (routeKillTimer, now, netJobAdd, (int)routeKillCheck);     return;    }/* * This routine performs garbage collection on unused route entries. * The system clones those routes (from entries to remote destinations) * to store the path MTU results.  * * The <pArg> argument selects the operation to perform. Normally, both * the "draining" and "updating" fields are 0. In that case, this routine * completes the deletion of (unused) cloned entries triggered when rtfree() * set the RTF_DELETE flag. Since the RTF_DELETE flag and RTF_ANNOUNCE flags * have the same value, this routine also tests the RTF_STATIC flag to prevent * the removal of manually added proxy ARP entries. * * If too many routes exist, the "updating" flag reduces the lifetime of * appropriate entries. The "draining" flag removes all entries immediately * due to severe memory limitations. *  * As a side effect, this routine resets the "nextstop" field to the  * nearest expiration time of a route entry waiting for deletion, if any. */      LOCAL int routeUpdate    (    struct radix_node * pNode,    void * pArg    )    {    struct rtqk_arg * pCount = pArg;    struct rtentry * pRoute = (struct rtentry *)pNode;    int error;    ULONG now;    now = tickGet();    if ( (pRoute->rt_flags & RTF_DELETE) && !(pRoute->rt_flags & RTF_STATIC))        {        pCount->found++;        if (pCount->draining || pRoute->rt_rmx.rmx_expire <= now)            {            if (pRoute->rt_refcnt > 0)                panic ("routeKill removing route in use?");            error = rtrequest (RTM_DELETE, (struct sockaddr *)rt_key (pRoute),                               pRoute->rt_gateway, rt_mask (pRoute),                               pRoute->rt_flags, 0);            if (!error)                pCount->killed++;            }        else            {            if (pCount->updating &&                (pRoute->rt_rmx.rmx_expire - now > routePendInterval))                pRoute->rt_rmx.rmx_expire = now + routePendInterval;            if (pRoute->rt_rmx.rmx_expire < pCount->nextstop)                pCount->nextstop = pRoute->rt_rmx.rmx_expire;            }        }    return (0);    }    /*     * Remove all unused routes cloned from entries to remote destinations,     * regardless of expiration time.     */void routeDrain (void)    {    struct radix_node_head *pHead;    struct rtqk_arg   count;    int s;    pHead = rt_tables [AF_INET];    if (pHead == NULL)    /* Missing routing table. */        return;    count.found = count.killed = 0;    count.rnh = pHead;    count.nextstop = 0;    count.draining = 1;    count.updating = 0;    s = splnet ();    rn_walktree (pHead, routeUpdate, &count);    splx (s);    }/* * Packet routing routines.