xnu-344.49.tar.gz

[apple/xnu.git] / bsd / netat / ddp_rtmptable.c

/*
 * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
 *
 * @APPLE_LICENSE_HEADER_START@
 * 
 * Copyright (c) 1999-2003 Apple Computer, Inc.  All Rights Reserved.
 * 
 * This file contains Original Code and/or Modifications of Original Code
 * as defined in and that are subject to the Apple Public Source License
 * Version 2.0 (the 'License'). You may not use this file except in
 * compliance with the License. Please obtain a copy of the License at
 * http://www.opensource.apple.com/apsl/ and read it before using this
 * file.
 * 
 * The Original Code and all software distributed under the License are
 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
 * Please see the License for the specific language governing rights and
 * limitations under the License.
 * 
 * @APPLE_LICENSE_HEADER_END@
 */
/*----------------------------------------------------------------------------
 *
 *            RTMP & ZIP routing tables access routines
 *
 * This code implement b-tree search and manipulation of
 * of the RTMP routing table and ZIP zone table.
 *
 * The RTMP routing table is a data block divided in several routing
 * entries sorted during insertion in a b-tree form. We use a table and
 * not dynamically allocated entries because it allow us to scan the whole
 * table when RTMP packets are generated. The routing table entries are sorted
 * by there NetStop value (because non extended nets have a NetStart value of
 * zero. From any point in the tree, the left side contains Network ranges
 * smaller or equal to the current Node, and the right tree points to higher
 * values network ranges. 
 *
 *
 * 0.01 3/16/94 LD      Creation
 *    Modified for MP, 1996 by Tuyen Nguyen
 *   Modified, March 17, 1997 by Tuyen Nguyen for MacOSX.
 *
 *----------------------------------------------------------------------------
 *
 *      Copyright (c) 1994, 1996, 1997, 1998 Apple Computer, Inc.
 */

#include <sys/errno.h>
#include <sys/types.h>
#include <sys/param.h>
#include <machine/spl.h>
#include <sys/systm.h>
#include <sys/kernel.h>
#include <sys/proc.h>
#include <sys/filedesc.h>
#include <sys/fcntl.h>
#include <sys/mbuf.h>
#include <sys/ioctl.h>
#include <sys/malloc.h>
#include <sys/socket.h>
#include <sys/socketvar.h>

#include <net/if.h>
#include <net/if_types.h>

#include <netat/sysglue.h>
#include <netat/appletalk.h>
#include <netat/at_var.h>
#include <netat/ddp.h>
#include <netat/rtmp.h>
#include <netat/at_pcb.h>
#include <netat/zip.h>
#include <netat/routing_tables.h>
#include <netat/at_snmp.h>
#include <netat/debug.h>

RT_entry *RT_table_freelist;    /* start of free entry list */
RT_entry RT_table_start;        /* start of the actual entry table */
RT_entry *RT_table;             /* the routing table */
ZT_entry *ZT_table;             /* the Zone Information Protocol table */
short   RT_maxentry;            /* Number of entry in RTMP table */
short   ZT_maxentry;            /* Number of entry in ZIP table */

char errstr[512];               /* used to display meaningfull router errors*/

extern at_ifaddr_t *ifID_table[];
extern at_ifaddr_t *ifID_home;
extern snmpStats_t      snmpStats;
extern atlock_t ddpinp_lock;

short ErrorRTMPoverflow = 0;    /* flag if RTMP table is too small for this net */
short ErrorZIPoverflow  = 0;    /* flag if ZIP table is too small for this net */

        /* prototypes */
void getIfUsage( int, at_ifnames_t *);

/*
 * This a temporary function : just to display the router error 
 */

void RouterError(port, err_number)
short port, err_number;

{
        switch (err_number) {

        case ERTR_SEED_CONFLICT:
                dPrintf(D_M_RTMP, D_L_ERROR,
                         ("**** RTR Error on port# %d SEED_CONFLICT\n", port));
                break;
        
        case ERTR_CABLE_CONFLICT:
                dPrintf(D_M_RTMP, D_L_ERROR,
                        ("**** RTR Error on port# %d CABLE_CONFLICT\n", port));
                break;
        
        case ERTR_RTMP_BAD_VERSION:
                dPrintf(D_M_RTMP, D_L_ERROR,
                        ("**** RTR Error on port# %d RTMP_BAD_VERSION\n", port));
                break;

        case ERTR_CABLE_STARTUP:
                dPrintf(D_M_RTMP, D_L_ERROR,
                        ("**** RTR Error on port# %d RTMP_CABLE_STARTUP\n",
                         port));
                break;

        default:
                dPrintf(D_M_RTMP, D_L_ERROR,
                        ("**** RTR Error on port# %d WHAT IN THE WORLD IS THIS ONE? code=%d\n",
                        port, err_number));
                break;
        }
        dPrintf(D_M_RTMP, D_L_ERROR, ("Explanation: %s\n", errstr));
}
        

/*
 * this function just look for a NetNumber in the routing table,
 * no check is done for the validity of the entry
 */

RT_entry *rt_blookup (NetNumber)
at_net_al NetNumber;
{

        RT_entry *ptree = &RT_table_start;
        at_net_al LowEnd;
        register unsigned int s;
/*
        dPrintf(D_M_RTMP_LOW, D_L_ROUTING, ("%s : Lookup for Net=%d\n",
                 "rt_blookup", NetNumber));
*/      
        ATDISABLE(s, ddpinp_lock);
        while (ptree) {

                if (NetNumber > ptree->NetStop) {
/*
                        dPrintf(D_M_RTMP_LOW, D_L_ROUTING, ("%s : Go Right from  #%d\n",
                                 "rt_blookup", ptree->NextIRNet));
*/
                        ptree = ptree->right;
                        continue;
                }
                else {
                   if (ptree->NetStart) 
                        LowEnd = ptree->NetStart;
                   else
                        LowEnd = ptree->NetStop;

                   if (NetNumber < LowEnd ) {
/*
                        dPrintf(D_M_RTMP_LOW, D_L_ROUTING, ("%s : Go Left from  #%d\n",
                                 "rt_blookup", ptree->NextIRNet));
*/
                        ptree = ptree->left;
                        continue;
                   }
                   ATENABLE(s, ddpinp_lock);
                   
                   /* we're in the range (either extended or not)
                    * return the entry found.
                    */

/*                      dPrintf(D_M_RTMP_LOW, D_L_ROUTING, ("%s : found %04d-%04d Port=%d State=0x%x\n",
                                "rt_blookup", ptree->NetStart, ptree->NetStop, ptree->NetPort,
                                ptree->EntryState));
*/

                   return (ptree);
                }       
        }
        ATENABLE(s, ddpinp_lock);

        dPrintf(D_M_RTMP_LOW, D_L_ROUTING, ("%s : %04d : NOT FOUND\n",
                 "rt_blookup", NetNumber));
        return ((RT_entry *)NULL);
}


/* Routing table btree insert routine
 *  Uses a RT_entry parameter as the input, the insert is sorted in
 *  the tree on the NetStop field. Provision is made for non extented
 *  net (ie NetStart = 0).   
 *  The function returns the element where the new entry was inserted, or
 *  NULL if the insert didn't work. (In this cas there is a problem with
 *  the tree coherency...
 *  
 */


RT_entry *rt_binsert (NewEntry)
RT_entry *NewEntry;
{
        RT_entry *ptree = &RT_table_start;

        register at_net_al NetStart = NewEntry->NetStart;
        register at_net_al NetStop  = NewEntry->NetStop;

        dPrintf(D_M_RTMP_LOW, D_L_ROUTING, ("rt_binsert: for Net %d-%d state=x%x NextIR %d:%d\n",
                 NetStart, NetStop, NewEntry->EntryState,NewEntry->NextIRNet, NewEntry->NextIRNode));

        if (ptree == (RT_entry *)NULL) {
                *ptree = *NewEntry;
                at_state.flags |= AT_ST_RT_CHANGED;
                return (NewEntry);
        }
        

        while (ptree) {

                if (NetStop > ptree->NetStop) { /* walk the right sub-tree */
                        if (ptree->right)
                                ptree = ptree->right;
                        else {
                                ptree->right = NewEntry;
                                at_state.flags |= AT_ST_RT_CHANGED;
                                return (ptree);
                        }
                }
                else { /* walk the left sub-tree */
                        if (ptree->left) 
                                ptree = ptree->left;
                        else {
                                ptree->left = NewEntry;
                                at_state.flags |= AT_ST_RT_CHANGED;
                                return (ptree);
                        }
                }

        }       

        dPrintf(D_M_RTMP, D_L_WARNING, ("%s : ERROR NOT INSERTED Net %d-%d\n",
                 "rt_binsert", NetStart, NetStop));
        return ((RT_entry *)NULL);
}

RT_entry *rt_insert(NStop, NStart, NxNet, NxNode, NtDist, NtPort, EntS) 
     at_net_al NStop, NStart, NxNet;
     at_node NxNode;
     u_char NtDist, NtPort, EntS;
{
    RT_entry *New; 
    if ((New = RT_table_freelist)) {
        RT_table_freelist = RT_table_freelist->right; 
    } else 
        return ((RT_entry *)NULL);
    New->right = NULL; 
    New->NetStop = NStop; 
    New->NetStart = NStart; 
    New->NextIRNet = NxNet; 
    New->NextIRNode = NxNode; 
    New->NetDist = NtDist; 
    New->NetPort = NtPort; 
    New->EntryState = EntS; 
    bzero(New->ZoneBitMap, sizeof(New->ZoneBitMap)); 
        at_state.flags |= AT_ST_RT_CHANGED; 
        return(rt_binsert(New)); 
}

/*
        dPrintf(D_M_RTMP_LOW, D_L_ROUTING, ("%s : %04d : NOT FOUND\n",
                 "rt_blookup", NetNumber));
 * Routing table btree deletion routine
 *
 */

RT_entry *rt_bdelete (NetStop, NetStart)
     at_net_al NetStop, NetStart;
{

        RT_entry *rt_found, *pprevious, *pnext, *pnextl, *psub;
        at_net_al LowEnd;

        rt_found = &RT_table_start;

        dPrintf(D_M_RTMP_LOW, D_L_ROUTING, ("%s : Delete %d-%d\n",
                 "rt_bdelete", NetStart, NetStop));

        while (rt_found) {

                if (NetStop > rt_found->NetStop) {
                        pprevious = rt_found;
                        rt_found = rt_found->right;
                        continue;
                }
                else {
                
                   /* non extended nets cases */

                   if (rt_found->NetStart) 
                        LowEnd = rt_found->NetStart;
                   else
                        LowEnd = rt_found->NetStop;

                  if (NetStop < LowEnd) {
                        pprevious = rt_found;
                        rt_found = rt_found->left;
                        continue;
                   }
                   
                   /* we're in the range (either extended or not)
                    * return the entry found.
                    */

                   break;
                }       
        }

        dPrintf(D_M_RTMP, D_L_ROUTING, ("%s : Delete %d-%d found to delete %d-%d\n",
                 "rt_bdelete", NetStart, NetStop, rt_found->NetStart,rt_found->NetStop));

        if (rt_found) {



                   /* we found the entry, now reorg the sub-trees
                    * spanning from our node.
                    */

                    if ((pnext = rt_found->right)) {

                                /* Tree pruning: take the left branch of the current
                                 * node and place it at the lowest left branch
                                 * of the current right branch 
                                 */

                                psub = pnext;

                                /* walk the Right/Left sub tree from current node */

                                while ((pnextl = psub->left))
                                        psub = pnextl;  
                                
                                /* plug the old left tree to the new ->Right leftmost node */   
                                
                                psub->left = rt_found->left;
                                                

                    } else {     /* only left sub-tree, simple case */

                                pnext = rt_found->left;
                    }
                        
                        /* Now, plug the current node sub tree to the good pointer of 
             * our parent node.
             */


                        if (pprevious->left == rt_found)
                                pprevious->left = pnext;
                        else
                                pprevious->right = pnext;       

                        /* clean-up entry and add to the free-list */

                        at_state.flags |= AT_ST_RT_CHANGED;
                        return(rt_found);
        }

        else { /* Trying to delete something that doesn't exist? */

                dPrintf(D_M_RTMP, D_L_WARNING, ("%s : %d NOT Removed\n",
                        "rt_bdelete", NetStop));

                return ((RT_entry *)NULL);
        }

                                
}
                                        

RT_entry *rt_sortedshow(parent)
RT_entry *parent;
{
        RT_entry *me;
        
        me = parent;

        if (parent == NULL) {
                me = &RT_table_start;
                while (me) 
                        if (me->left) {
                                parent = me;
                                me = me->left;
                        }
/*              parent = parent->parent; */
        }
        return (parent);
}

/*
 * debug only: display the contents of the routing table
 */

void rt_show ()
{
        RT_entry *ptree;
        int i=0;

        ptree = &RT_table[0];

        while (ptree && i < 600 ) {
                if (ptree->NetStop) { 
                        dPrintf(D_M_RTMP_LOW, D_L_VERBOSE,
                                ("%4d-%4d IR=%d:%d Dist=%d\n",
                                ptree->NetStop, ptree->NetStart, ptree->NextIRNet,
                                ptree->NextIRNode, (short)ptree->NetDist));
                } else {
                        dPrintf(D_M_RTMP_LOW, D_L_VERBOSE,
                                ("%04d : * FREE ENTRY\n", i));
                }
                ptree++;
        i++;
        }
}

/*
 * prepare the indexing of the free entries in the RTMP table
 */

rt_table_init()
{
        short i;

        if ((RT_table = (RT_entry *)_MALLOC(sizeof(RT_entry)*RT_maxentry,
                                            M_RTABLE, M_WAITOK)) == NULL) {
                dPrintf(D_M_RTMP, D_L_WARNING, 
                        ("rtmptable: Can't allocate RT_table\n"));
                return (ENOMEM);
        }
        if ((ZT_table = (ZT_entry *)_MALLOC(sizeof(ZT_entry)*ZT_maxentry,
                                            M_RTABLE, M_WAITOK)) == NULL) {
                dPrintf(D_M_RTMP, D_L_WARNING, 
                        ("rtmptable: Can't allocate ZT_table\n"));
                return (ENOMEM);
        }
        dPrintf(D_M_RTMP, D_L_STARTUP, ("rt_table_init called\n"));
        bzero(&RT_table[0], sizeof(RT_entry)* RT_maxentry);
        for (i= 1 ; i < RT_maxentry ; i++) {
                (&RT_table[i-1])->right = &RT_table[i];
        }
        RT_table_freelist = &RT_table[0];

        at_state.flags |= AT_ST_RT_CHANGED;
        at_state.flags |= AT_ST_ZT_CHANGED;
        bzero(&RT_table_start, sizeof(RT_entry));

        /* also clean up the ZIP table */

        bzero(&ZT_table[0], sizeof(ZT_entry)* ZT_maxentry);
        ErrorRTMPoverflow = 0;
        ErrorZIPoverflow = 0;
        return(0);
}

/* 
 * zt_add_zone: add a zone name in the zone table.
 */

zt_add_zone(name, length)
char *name;
short length;
{
        at_nvestr_t zname;
        bcopy(name, &zname.str, length);
        zname.len = length;
        return (zt_add_zonename(&zname));
}

/* 
 * zt_add_zonename: add a zone name in the zone table.
 */

int zt_add_zonename(zname)
at_nvestr_t *zname;
{
        register short res,i;
        register unsigned int s;

        if (res = zt_find_zname(zname))
                return(res);

        ATDISABLE(s, ddpinp_lock);
        for (i = 0; i < ZT_maxentry ; i++) {
                if (ZT_table[i].ZoneCount == 0 && ZT_table[i].Zone.len == 0) {/* free entry */
                        ZT_table[i].Zone = *zname;
                        dPrintf(D_M_RTMP, D_L_VERBOSE, ("zt_add_zonename: zone #%d %s len=%d\n",
                                i, ZT_table[i].Zone.str, ZT_table[i].Zone.len));
                        at_state.flags |= AT_ST_ZT_CHANGED;
                        ATENABLE(s, ddpinp_lock);
                        return(i+1);
                }
        }
        ATENABLE(s, ddpinp_lock);
        /* table full... */
        return (ZT_MAXEDOUT);
}

/* Adjust zone counts for a removed network entry.
 * If the ZoneCount of a zone reaches zero, delete the zone from the zone table
 */
void zt_remove_zones(zmap)
u_char *zmap;
{

        register        u_short i,j, Index;

        for (i=0; i< ZT_BYTES ; i++) {

                if (zmap[i]) {
                        for (j=0; j < 8 ; j++)
                                if ((zmap[i] << j) & 0x80) {
                                        Index = i*8 + j;        /* get the index in ZT */
                                                /* 1-23-97 this routine caused a crash once, presumably
                                               zmap bits beyond ZT_table size got set somehow.
                           prevent that here
                                                 */
                                        if (Index >= ZT_maxentry) {
                                                dPrintf(D_M_RTMP, D_L_ERROR,
                                                        ("zt_remove_zones: index (%d) GT ZT_maxentry (%d) (zmap:%d)\n",
                                                        Index,ZT_maxentry,i));
                                                return;
                                        }
                                        dPrintf(D_M_RTMP, D_L_VERBOSE,
                                                ("zt_remove_zones: zone #%d %s was=%d\n", Index,
                                                ZT_table[Index].Zone.str, ZT_table[Index].ZoneCount));
                                        if (ZT_table[Index].ZoneCount > 0) 
                                                ZT_table[Index].ZoneCount--;
                                        if (ZT_table[Index].ZoneCount == 0)
                                                        ZT_table[Index].Zone.len = 0;
                                        at_state.flags |= AT_ST_ZT_CHANGED;
                                }
                }
        }
}



/*
 * zt_compute_hash: compute hash index from the zone name string
 */

short zt_compute_hash(zname)
at_nvestr_t *zname;
{
        register u_short checksum=0, i;
        register char c1;

        /* apply the upper name + DDP checksum algorithm */

        for (i= 0 ; i < zname->len; i++) {

                        /* upperize the character */

                        c1 = zname->str[i];
            if (c1 >= 'a' && c1 <= 'z')
                   c1 += 'A' - 'a';
            if (c1 & 0x80)
                c1 = upshift8(c1);

                        /* DDP Checksum */

                        checksum += c1;
                        checksum = ((checksum & 0x8000) ?
                                (checksum << 1 | 1) : (checksum << 1));
        }

        dPrintf(D_M_RTMP_LOW, D_L_ROUTING, ("zt_comphash: value computed for zone=%s h=%d\n",
                zname->str, checksum));

        if (checksum)
                return (checksum);
        else
                return (0xffff);

}

/* 
 * zt_upper_zname: translate the name string into uppercase
 */

void zt_upper_zname(zname)
at_nvestr_t *zname;
{
        register short i;
        register char c1;

        for (i= 0 ; i < zname->len; i++) {

                        c1 = zname->str[i];
            if (c1 >= 'a' && c1 <= 'z')
                   c1 += 'A' - 'a';
            if (c1 & 0x80)
                c1 = upshift8(c1);

                        zname->str[i] = c1;
        }
}

/*
 * zt_get_zmcast: calcularte the zone multicast address for a
 *                    given zone name. 
 *                    Returns the result in "buffer"
 */

zt_get_zmcast(ifID, zname, buffer)
     at_ifaddr_t *ifID;         /* we want to know the media type */
     at_nvestr_t *zname;        /* source name for multicast address */
     char *buffer;              /* resulting Zone Multicast address */
{
        u_short h;

        h = zt_compute_hash(zname);

/*
 * Find a nice way to decide if it is TokenRing or Ethernet for
 * the Multicast address computation....
 */

        if (ifID->aa_ifp->if_type != IFT_ISO88025) { /* token ring */

                /* Ethernet case */

                buffer[0] = 0x09;
                buffer[1] = 0x00;
                buffer[2] = 0x07;
                                /* no router, use cable multicast */
                if (MULTIHOME_MODE && ifID->ifRouterState == NO_ROUTER ) {
                        buffer[3] = buffer[4] = buffer[5] =  0xff;
                }
                else {
                        buffer[3] = 0x00;
                        buffer[4] = 0x00;
                        buffer[5] = h % 0xFD;
                }
                dPrintf(D_M_RTMP_LOW, D_L_ROUTING, ("zt_get_multi: computed for h=%d %x %x\n",
                                h, *(u_int *)&buffer[0], *(u_short *)&buffer[4]));
 
                return(6); /* returns Multicast address length */

        }
        else {
                 /* assume it is token ring: note for the magic number computation,
                  * first see Inside Mac Page 3-10, there is 20 multicast addresses
                  * for TLAP, and they are from 0xC000 0000 0008 00 to 0xC000 0200 0000 00
                  */
                buffer[0] = 0xC0;
                buffer[1] = 0x00;
                *(u_int *)&buffer[2] = 1 << ((h % 19) + 11);
                dPrintf(D_M_RTMP, D_L_WARNING,("zt_get_multi: BROAD not found forr h=%d \n",
                         h));
                return(6);
        }



}

/*
 * zt_ent_zindex: return the first zone index found in the zone map
 * return the entry number+1 in the Zone Table, or zero if not found
 */

int zt_ent_zindex(zmap)
u_char *zmap;
{
        u_short i,j;


        for (i = 0 ; i < ZT_BYTES ; i++)

                if (zmap[i]) 
                        for (j = 0 ; j < 8 ; j++)
                                if ((zmap[i] << j) & 0x80)
                                        return (8*i + j +1);

        return (0);
}
/*
 * zt_ent_zcount: count the number of actives zone for a routing entry
 */

zt_ent_zcount(ent)
RT_entry *ent;
{
        register u_char *zmap;
        register u_short i,j;
        register int       zone_count = 0 ;
        register unsigned int s;

        ATDISABLE(s, ddpinp_lock);

        if (!RT_ALL_ZONES_KNOWN(ent)) {
                        ATENABLE(s, ddpinp_lock);
                        return (0);
        }
        zmap = ent->ZoneBitMap;

        for (i = 0 ; i < ZT_BYTES ; i++) {

                if (*zmap) 

                        for (j = 0 ; j < 8 ; j++)
                                if ((*zmap << j) & 0x80)
                                        zone_count++;
                zmap++;
        }

        ATENABLE(s, ddpinp_lock);
        return (zone_count);
}

/*
 * zt_find_zname: match a zone name in the zone table and return the entry if found
 */
zt_find_zname(zname)
at_nvestr_t *zname;
{
        register short i, j, found;
        register char c1, c2;
        register unsigned int s;


        if (!zname->len)
                return(0);

        ATDISABLE(s, ddpinp_lock);
        for (i = 0 ; i < ZT_maxentry ; i++) {
                        if (!ZT_table[i].ZoneCount || zname->len != ZT_table[i].Zone.len)
                                        continue;

                        found = 1; /* did we get the right one? */

                        for (j = 0 ; j < zname->len ; j++) {
                    c1 = zname->str[j];
                c2 = ZT_table[i].Zone.str[j];
                if (c1 >= 'a' && c1 <= 'z')
                        c1 += 'A' - 'a';
                if (c2 >= 'a' && c2 <= 'z')
                        c2 += 'A' - 'a';
                if (c1 & 0x80)
                        c1 = upshift8(c1);
                if (c2 & 0x80)
                        c2 = upshift8(c2);
                if (c1 != c2) {
                        found = 0;
                                                break;
                                }
                        }

                        if (found) {
                                ATENABLE(s, ddpinp_lock);
                                return (i+1);
                        }
        }

        ATENABLE(s, ddpinp_lock);
        return(0);
}

        
/*
 * zt_set_zmap: set a bit for the corresponding zone map in an entry bitmap
 */
void zt_set_zmap(znum, zmap)
     u_short znum;
     char *zmap;
{
        register u_short num = znum -1;
        register unsigned int s;

        ATDISABLE(s, ddpinp_lock);
        if (!(zmap[num >> 3] & 0x80 >> (num % 8))) {
                zmap[num >> 3] |= 0x80 >> (num % 8);
                ZT_table[num].ZoneCount++;
        }
        ATENABLE(s, ddpinp_lock);
}


/*
 * zt_clr_zmap: clear a bit for the corresponding zone map in an entry bitmap
 */
void zt_clr_zmap(znum, zmap)
     u_short znum;
     char *zmap;
{
        register u_short num = znum -1;
        register unsigned int s;

        ATDISABLE(s, ddpinp_lock);
        if (zmap[num >> 3] & 0x80 >> (num % 8)) {
                zmap[num >> 3] ^= 0x80 >> (num % 8);
                ZT_table[num].ZoneCount--;
        }
        ATENABLE(s, ddpinp_lock);
}


/*
 * routing_needed : 
 * This function performs the actual lookup and forward of packets
 * send to the box for routing.
 *
 * The destination network is looked up in our tables, and if we
 * know the next IR to send the packet to, we forward the packet
 * on the right port.
 *
 * If the destination is unknown, we simply dump the packet.
 */

void routing_needed(mp, ifID, bypass)
     gbuf_t   *mp;
     at_ifaddr_t *ifID;
     char bypass;       /* set by special socket handlers */
{

        register at_ddp_t *ddp;
        register int       msgsize;
        register RT_entry *Entry;
        register gbuf_t *tmp_m;

        /* first check the interface is up and forwarding */

        if (!ifID) {
                dPrintf(D_M_RTMP, D_L_WARNING, 
                        ("routing_needed: non valid IFID!\n"));
                gbuf_freel(mp);         
                return;
        }
        if ((ifID->ifRoutingState < PORT_ONLINE)) {
                dPrintf(D_M_RTMP, D_L_WARNING, 
                        ("routing_needed: port %d not online yet\n",
                         ifID->ifPort));
                gbuf_freel(mp);         
                return;
        }

        ddp = (at_ddp_t *)gbuf_rptr(mp);
        msgsize = DDPLEN_VALUE(ddp);
        for (tmp_m = gbuf_next(mp); tmp_m; tmp_m = gbuf_next(tmp_m))
                msgsize += DDPLEN_VALUE(((at_ddp_t *)gbuf_rptr(tmp_m)));
        
        if (ddp->hopcount++ > 15) {
                dPrintf(D_M_RTMP, D_L_WARNING,
                        ("routing_needed: drop packet for %d:%d, hopcount too high\n",
                        NET_VALUE(ddp->dst_net), ddp->dst_node));
                gbuf_freel(mp);
                snmpStats.dd_hopCount++;
                return; /* was return(1); */
        }

        if ((Entry = rt_blookup(NET_VALUE(ddp->dst_net)))) {
        
                dPrintf(D_M_RTMP_LOW, D_L_ROUTING,
                        ("routing_needed: FOUND for %d.%d p=%d to %d.%d \n",
                        NET_VALUE(ddp->dst_net), ddp->dst_node, ifID->ifPort,
                        Entry->NextIRNet, Entry->NextIRNode));

                /* somehow, come to that point... */

                /* if multihomed - need to set source address to the interface
                 * the packet is being sent from.
                 */
                if (MULTIHOME_MODE) {
                        NET_ASSIGN(ddp->src_net, ifID_table[Entry->NetPort]->ifThisNode.s_net);
                        ddp->src_node = ifID_table[Entry->NetPort]->ifThisNode.s_node;
                }

                ifID->ifStatistics.fwdPkts++;
                ifID->ifStatistics.fwdBytes += msgsize;

                if (Entry->NetDist)  /* net not directly connected */
                        ddp_router_output(mp, ifID_table[Entry->NetPort], AT_ADDR,
                                 Entry->NextIRNet, Entry->NextIRNode, 0);
                else {/* we are directly on this net */

                        /* we want to avoid duplicating broadcast packet on the same net,
                         * but special sockets handlers are ok to do that (mainly for
                         * for loopback purpose). So, if the "bypass" flag is set, we don't
                         * check for that test... [Problem was "movietalk"].
                         */

                        if (bypass || ifID_table[Entry->NetPort] != ifID) 
                                ddp_router_output(mp, ifID_table[Entry->NetPort], AT_ADDR,
                                 NET_VALUE(ddp->dst_net), ddp->dst_node, 0);
                        else {
                                dPrintf(D_M_RTMP, D_L_ROUTING,
                                        ("routing_needed: bad loopback for add %d.%d from port %d (%d.%d)\n",
                                         NET_VALUE(ddp->dst_net), ddp->dst_node, ifID->ifPort,
                                         NET_VALUE(ddp->src_net), ddp->src_node));
                                ifID->ifStatistics.droppedPkts++;
                                ifID->ifStatistics.droppedBytes += msgsize;

                                gbuf_freel(mp);
                                return; /* was return (2); */
                        }
 

                }
        }
        else {
                dPrintf(D_M_RTMP, D_L_ROUTING,
                        ("routing_needed: NOT FOUND for add %d.%d from port %d our %d.%d\n",
                         NET_VALUE(ddp->dst_net), ddp->dst_node, ifID->ifPort,
                         ifID_home->ifThisNode.s_net,
                         ifID_home->ifThisNode.s_node));

                ifID->ifStatistics.droppedPkts++;
                ifID->ifStatistics.droppedBytes += msgsize;
                snmpStats.dd_noRoutes++;

                gbuf_freel(mp);
                return; /* was return (2); */

        }
        /*      return(0); */
} /* routing_needed */

ZT_entryno *zt_getNextZone(first)
        int     first;  
        /* a call made with first = TRUE returns the first valid entry in
           the ZT_table, if first != TRUE, then then each call returns the
           next valid entry in the table. The next call after the last
           valid entry was read returns NULL
        */
{
        int             i;
        static int      idx=0;
        static ZT_entryno       zte;
        
        if (!ZT_table)
                return NULL;

        if (first)
                idx=0;

        for (i=idx; i<ZT_maxentry; i++) {
                if (ZT_table[i].ZoneCount)
                        break;
        }
        if (i<ZT_maxentry) {
                idx = i+1;
                zte.zt = ZT_table[i];
                zte.entryno = i;
                return(&zte);
        }
        else
                return(NULL);
}

RT_entry *rt_getNextRoute(first)
        int     first;  

/* a call made with first = TRUE returns the first valid entry in
   the RT_table, if first != TRUE, then then each call returns the
   next valid entry in the table. The next call after the last
   valid entry was read returns NULL
*/

{
        int             i;
        static int      idx=0;
        
        if (!RT_table)
                return(NULL);

        if (first)
                idx=0;

        for (i=idx; i<RT_maxentry; i++) {
                if (RT_table[i].EntryState != RTE_STATE_UNUSED)
                        break;
        }
        if (i<RT_maxentry) {
                idx = i+1;
                return(&RT_table[i]);
        }
        else
                return(NULL);
}


getRtmpTableSize()
{
        register int i;
        register RT_entry *rt;
        static  int size=0;

        if(!(at_state.flags &AT_ST_RT_CHANGED))         
                return(size);

        for (i=RT_maxentry,rt = &RT_table[RT_maxentry-1]; i; i--,rt--)
                if (rt->EntryState != RTE_STATE_UNUSED) {
                        size = i;
                        return(i);
                }
        return(0);
}

getZipTableSize()
{
        register int i;
        register ZT_entry *zt;
        static  int size=0;

        if (!(at_state.flags & AT_ST_ZT_CHANGED))
                return(size);

        for (i=ZT_maxentry,zt = &ZT_table[ZT_maxentry-1]; i; i--,zt--)
                if (zt->ZoneCount) {
                        size = i;
                        return(i);
                }
        return(0);
}

getRtmpTable(d,s,c)
     RT_entry   *d;             /* destination */
     int        s;              /* starting entry */
     int        c;              /* # entries to copy */
{
        register int i,n=0;
        register RT_entry       *rt;

        for(i=s,rt=&RT_table[s]; i<RT_maxentry && n<c; rt++,i++)
                if (rt->EntryState != RTE_STATE_UNUSED) {
                        *d++ = *rt;
                        n++;
                }
}

getZipTable(d,s,c)
     ZT_entry   *d;             /* destination */
     int        s;              /* starting entry */
     int        c;              /* # entries to copy */
{

        bcopy(&ZT_table[s], d, c*sizeof(ZT_entry));
}

at_nvestr_t *getRTRLocalZone(ifz)
     zone_usage_t *ifz;
{
        char *zmap;
        RT_entry        *route;
        int i, j, index;
        int  zcnt=0;            /* zone we're pointing to in the list */
        char zonesChecked[ZT_BYTES];
        at_ifaddr_t *ifID;

        if (ifz->zone_index < 0) {
                return((at_nvestr_t*)NULL);
        }
        bzero(zonesChecked,sizeof(zonesChecked));
        TAILQ_FOREACH(ifID, &at_ifQueueHd, aa_link) {
                if (!(route = rt_blookup(ifID->ifThisNode.s_net))) {
                        return((at_nvestr_t*)NULL);
                }       
                zmap=route->ZoneBitMap;
                dPrintf(D_M_RTMP_LOW, D_L_USR1,
                        ("getRTRLocal: i/f %s, net:%d\n",ifID->ifName, 
                         ifID->ifThisNode.s_net));
                for (i = 0 ; i < ZT_BYTES; i++) {
                  if (zmap[i]) {
                    for (j = 0; j < 8 ; j++)
                      if (  (zmap[i]  & (0x80 >> j)) &&
                            !(zonesChecked[i] & (0x80 >> j)) 
                            ) {
                        zonesChecked[i] |=  (0x80 >> j);
                        if (ifz->zone_index == zcnt) {
                          index = i * 8 + j;
                          getIfUsage(index, &ifz->zone_iflist);
                          ifz->zone_name = ZT_table[index].Zone;
                          dPrintf(D_M_RTMP_LOW, D_L_USR1,
                                  ("getRTRLocal:zmap:%8x zcnt:%d\n",
                                   *(int*)zmap, zcnt));
                          ifz->zone_index = index+1;
                          return(&ZT_table[index].Zone);
                        }
                        zcnt++;
                      }
                  }
                }
        }
        dPrintf(D_M_RTMP_LOW, D_L_USR1,
                ("getRTRLocal: returning NULL last ent:%d net:%d zmap:%08x\n",
                 (ifID ? ifID->ifPort : 0),
                 (ifID ? ifID->ifThisNode.s_net : 0),*(int*)zmap));
        ifz->zone_name.len = 0;
        return((at_nvestr_t*)NULL);
} /* getRTRLocalZone */

void getIfUsage(zone, ifs_in_zone)
     int zone;
     at_ifnames_t *ifs_in_zone;

/* sets the interface name in each element of the array for each I/F in the
   requested zone. The array has a 1:1 correspondence with the
   ifID_table. Zone is assumed to be valid and local, so if we're in
   single port mode, we'll set the home port and thats it.
*/
{
        u_int   zmi;    /* zone map index for zone */
        u_char  zmb;    /* zone map bit mask for zone */
        RT_entry        *route;
        int cnt=0;
        at_ifaddr_t     *ifID;

        if (!MULTIPORT_MODE) {
                strncpy(ifs_in_zone->at_if[cnt], ifID_home->ifName, 
                        IFNAMESIZ);
                return;
        }
        bzero(ifs_in_zone, sizeof(at_ifnames_t));
        zmi = zone>>3;
        zmb = 0x80>>(zone % 8);
        dPrintf(D_M_NBP_LOW, D_L_USR3, ("get_ifs znum:%d zmi%d zmb:%x\n",
                zone, zmi, zmb));
        TAILQ_FOREACH(ifID, &at_ifQueueHd, aa_link) {
                if (!(route = rt_blookup(ifID->ifThisNode.s_net)))
                        return;
                if (route->ZoneBitMap[zmi] & zmb) {
                        dPrintf(D_M_NBP_LOW, D_L_USR3, ("zone in port %d \n",
                                route->NetPort));
                        strncpy(ifs_in_zone->at_if[cnt], 
                                ifID_table[route->NetPort]->ifName, IFNAMESIZ);
                        cnt++;
                }
        }
        return;
} /* getIfUsage */