this doesn't include annotation bugfixes, but documents

work sent to mitre for a tunnel driver

SCCS-vsn: sys/net/radix.c 8.2.3.1

diff --git a/usr/src/sys/net/radix.c b/usr/src/sys/net/radix.c
index ff9e355..0eb1281 100644 (file)
--- a/usr/src/sys/net/radix.c
+++ b/usr/src/sys/net/radix.c
@@ -1,34 +1,32 @@
 /*
 /*

- * Copyright (c) 1988, 1989, 1993
+ * Copyright (c) 1988, 1991, 1993

  *     The Regents of the University of California.  All rights reserved.
  *
  * %sccs.include.redist.c%
  *
  *     The Regents of the University of California.  All rights reserved.
  *
  * %sccs.include.redist.c%
  *

- *     @(#)radix.c     8.4 (Berkeley) %G%
+ *     @(#)radix.c     8.2.3.1 (Berkeley) %G%

  */
 
 /*
  * Routines to build and maintain radix trees for routing lookups.
  */
  */
 
 /*
  * Routines to build and maintain radix trees for routing lookups.
  */

-#ifndef _RADIX_H_
+#ifndef RNF_NORMAL

 #include <sys/param.h>
 #ifdef KERNEL
 #include <sys/param.h>
 #ifdef KERNEL

-#ifdef KERNEL

 #include <sys/systm.h>
 #include <sys/malloc.h>
 #define        M_DONTWAIT M_NOWAIT
 #include <sys/systm.h>
 #include <sys/malloc.h>
 #define        M_DONTWAIT M_NOWAIT

+#ifdef KERNEL

 #include <sys/domain.h>
 #else
 #include <stdlib.h>
 #include <sys/domain.h>
 #else
 #include <stdlib.h>

-#else
-#include <stdlib.h>

 #endif
 #include <sys/syslog.h>
 #include <net/radix.h>
 #endif
 #include <sys/syslog.h>
 #include <net/radix.h>

-#include <sys/syslog.h>
-#include <net/radix.h>

 #endif
 
 #endif
 

+#include <net/radix.h>
+

 int    max_keylen;
 struct radix_node_head *mask_rnhead;
 static char *rn_zeros, *rn_ones;
 int    max_keylen;
 struct radix_node_head *mask_rnhead;
 static char *rn_zeros, *rn_ones;


@@ -125,6 +123,7 @@ rn_refines(m_arg, n_arg)
                        return 0;
                if (*n++ != *m++)
                        masks_are_equal = 0;
                        return 0;
                if (*n++ != *m++)
                        masks_are_equal = 0;

+                       

        }
        while (n < lim2)
                if (*n++)
        }
        while (n < lim2)
                if (*n++)


@@ -139,13 +138,6 @@ rn_refines(m_arg, n_arg)
 static int low_bits[] = {1, 3, 7, 15, 31, 63, 127, 255};
 static int mask_bits[] = {1, 2, 4, 8, 16, 32, 64, 128};
 
 static int low_bits[] = {1, 3, 7, 15, 31, 63, 127, 255};
 static int mask_bits[] = {1, 2, 4, 8, 16, 32, 64, 128};
 

-struct radix_node *
-rn_lookup(v_arg, m_arg, head)
-       void *v_arg, *m_arg;
-       struct radix_node_head *head;
-{
-       register struct radix_node *x;
-       caddr_t netmask = 0;

 struct radix_node *
 rn_lookup(v_arg, m_arg, head)
        void *v_arg, *m_arg;
 struct radix_node *
 rn_lookup(v_arg, m_arg, head)
        void *v_arg, *m_arg;


@@ -172,40 +164,6 @@ rn_lookup(v_arg, m_arg, head)
        return x;
 }
 
        return x;
 }
 

-static
-rn_satsifies_leaf(trial, leaf, skip)
-       char *trial;
-       register struct radix_node *leaf;
-       int skip;
-{
-       register char *cp = trial, *cp2 = leaf->rn_key, *cp3 = leaf->rn_mask;
-       char *cplim;
-       int length = min(*(u_char *)cp, *(u_char *)cp2);
-
-       if (cp3 == 0)
-               cp3 = rn_ones;
-       else
-               length = min(length, *(u_char *)cp3);
-       cplim = cp + length; cp3 += skip; cp2 += skip;
-       for (cp += skip; cp < cplim; cp++, cp2++, cp3++)
-               if ((*cp ^ *cp2) & *cp3)
-                       return 0;
-       return 1;
-}
-
-       if (m_arg) {
-               if ((x = rn_addmask(m_arg, 1, head->rnh_treetop->rn_off)) == 0)
-                       return (0);
-               netmask = x->rn_key;
-       }
-       x = rn_match(v_arg, head);
-       if (x && netmask) {
-               while (x && x->rn_mask != netmask)
-                       x = x->rn_dupedkey;
-       }
-       return x;
-}
-

 static
 rn_satsifies_leaf(trial, leaf, skip)
        char *trial;
 static
 rn_satsifies_leaf(trial, leaf, skip)
        char *trial;


@@ -385,8 +343,6 @@ rn_match(v_arg, head)
         */
        if (t->rn_mask)
                vlen = *(u_char *)t->rn_mask;
         */
        if (t->rn_mask)
                vlen = *(u_char *)t->rn_mask;

-       if (t->rn_mask)
-               vlen = *(u_char *)t->rn_mask;

        for (saved_t = t; t; t = t->rn_dupedkey)
                /* if (bits_matched >= mask_index) */
                if (rn_b <= t->rn_b) {
        for (saved_t = t; t; t = t->rn_dupedkey)
                /* if (bits_matched >= mask_index) */
                if (rn_b <= t->rn_b) {


@@ -394,6 +350,8 @@ rn_match(v_arg, head)
                         * This extra grot is in case we are explicitly asked
                         * to look up the default.  Ugh!
                         */
                         * This extra grot is in case we are explicitly asked
                         * to look up the default.  Ugh!
                         */

+                       off = min(t->rn_off, matched_off);
+                       mstart = maskedKey + off;

                        if ((t->rn_flags & RNF_ROOT) && t->rn_dupedkey)
                                t = t->rn_dupedkey;
                        return (t);
                        if ((t->rn_flags & RNF_ROOT) && t->rn_dupedkey)
                                t = t->rn_dupedkey;
                        return (t);


@@ -471,7 +429,7 @@ rn_insert(v_arg, head, dupentry, nodes)
 
 #ifdef RN_DEBUG
        if (rn_debug)
 
 #ifdef RN_DEBUG
        if (rn_debug)

-               log(LOG_DEBUG, "rn_insert: Going In:\n"), traverse(p);
+               printf("Going In:\n"), traverse(p);

 #endif
        t = rn_newpair1(v, b, nodes, head);
        /*
 #endif
        t = rn_newpair1(v, b, nodes, head);
        /*


@@ -494,7 +452,7 @@ rn_insert(v_arg, head, dupentry, nodes)
        x->rn_p = t;
 #ifdef RN_DEBUG
        if (rn_debug)
        x->rn_p = t;
 #ifdef RN_DEBUG
        if (rn_debug)

-               log(LOG_DEBUG, "rn_insert: Coming Out:\n"), traverse(p);
+               printf("Coming out:\n"), traverse(p);

 #endif
        return (nodes);
 }
 #endif
        return (nodes);
 }


@@ -512,10 +470,8 @@ rn_masksubr(n_arg, v_arg, skip, head, len_p)
        caddr_t netmask = (caddr_t)n_arg, v = v_arg;
        register struct radix_node *x = rn_masktop;
        register caddr_t cp, cplim;
        caddr_t netmask = (caddr_t)n_arg, v = v_arg;
        register struct radix_node *x = rn_masktop;
        register caddr_t cp, cplim;

-       register int b = 0, mlen, j;
-       int maskduplicated, m0, isnormal;
-       struct radix_node *saved_x;
-       static int last_zeroed = 0;
+       register int b, mlen, j;
+       int maskduplicated;

        struct radix_node *saved_x;
 
        if (head == 0)
        struct radix_node *saved_x;
 
        if (head == 0)


@@ -529,14 +485,6 @@ rn_masksubr(n_arg, v_arg, skip, head, len_p)
                Bzero(addmask_key + m0, last_zeroed - m0);
        *addmask_key = last_zeroed = mlen;
        x = rn_search(addmask_key, rn_masktop);
                Bzero(addmask_key + m0, last_zeroed - m0);
        *addmask_key = last_zeroed = mlen;
        x = rn_search(addmask_key, rn_masktop);

-       if (Bcmp(addmask_key, x->rn_key, mlen) != 0)
-               x = 0;
-       if (x || search)
-               return (x);
-       if (m0 < last_zeroed)
-               Bzero(addmask_key + m0, last_zeroed - m0);
-       *addmask_key = last_zeroed = mlen;
-       x = rn_search(addmask_key, rn_masktop);

        if (Bcmp(addmask_key, x->rn_key, mlen) != 0)
                x = 0;
        if (x || search)
        if (Bcmp(addmask_key, x->rn_key, mlen) != 0)
                x = 0;
        if (x || search)


@@ -550,7 +498,7 @@ rn_masksubr(n_arg, v_arg, skip, head, len_p)
            Bcmp(netmask + skip, x->rn_key + skip, mlen - skip) == 0)
                goto found;
        R_Malloc(x, struct radix_node *, max_keylen + 2 * sizeof (*x));
            Bcmp(netmask + skip, x->rn_key + skip, mlen - skip) == 0)
                goto found;
        R_Malloc(x, struct radix_node *, max_keylen + 2 * sizeof (*x));

-       if ((saved_x = x) == 0)
+       if (x == 0)

                return (0);
        saved_x = x;
        Bzero(x, max_keylen + 2 * sizeof (*x));
                return (0);
        saved_x = x;
        Bzero(x, max_keylen + 2 * sizeof (*x));


@@ -566,7 +514,6 @@ rn_masksubr(n_arg, v_arg, skip, head, len_p)
                x->rn_b = -1 - mlen;
        }
        b += (cp - netmask) << 3;
                x->rn_b = -1 - mlen;
        }
        b += (cp - netmask) << 3;

-       b += (cp - netmask) << 3;

 found:
        if (len_p)
                *len_p = (-1 - x->rn_b) - head->rnh_offset;
 found:
        if (len_p)
                *len_p = (-1 - x->rn_b) - head->rnh_offset;


@@ -612,45 +559,6 @@ rn_new_radix_mask(tt, next)
        return m;
 }
 
        return m;
 }
 

-static int     /* XXX: arbitrary ordering for non-contiguous masks */
-rn_lexobetter(m_arg, n_arg)
-       void *m_arg, *n_arg;
-{
-       register u_char *mp = m_arg, *np = n_arg, *lim;
-
-       if (*mp > *np)
-               return 1;  /* not really, but need to check longer one first */
-       if (*mp == *np) 
-               for (lim = mp + *mp; mp < lim;)
-                       if (*mp++ > *np++)
-                               return 1;
-       return 0;
-}
-
-static struct radix_mask *
-rn_new_radix_mask(tt, next)
-       register struct radix_node *tt;
-       register struct radix_mask *next;
-{
-       register struct radix_mask *m;
-
-       MKGet(m);
-       if (m == 0) {
-               log(LOG_ERR, "Mask for route not entered\n");
-               return (0);
-       }
-       Bzero(m, sizeof *m);
-       m->rm_b = tt->rn_b;
-       m->rm_flags = tt->rn_flags;
-       if (tt->rn_flags & RNF_NORMAL)
-               m->rm_leaf = tt;
-       else
-               m->rm_mask = tt->rn_mask;
-       m->rm_mklist = next;
-       tt->rn_mklist = m;
-       return m;
-}
-

 struct radix_node *
 rn_addroute(v_arg, n_arg, head, treenodes)
        void *v_arg, *n_arg;
 struct radix_node *
 rn_addroute(v_arg, n_arg, head, treenodes)
        void *v_arg, *n_arg;


@@ -702,6 +610,7 @@ rn_addroute(v_arg, n_arg, head, treenodes)
                t=tt+1; tt->rn_info = rn_nodenum++; t->rn_info = rn_nodenum++;
                tt->rn_twin = t; tt->rn_ybro = rn_clist; rn_clist = tt;
 #endif
                t=tt+1; tt->rn_info = rn_nodenum++; t->rn_info = rn_nodenum++;
                tt->rn_twin = t; tt->rn_ybro = rn_clist; rn_clist = tt;
 #endif

+               t = saved_tt;

                us->rn_key = (caddr_t) v;
                us->rn_flags = RNF_ACTIVE;
        }
                us->rn_key = (caddr_t) v;
                us->rn_flags = RNF_ACTIVE;
        }


@@ -710,8 +619,13 @@ rn_addroute(v_arg, n_arg, head, treenodes)
        /*
         * Annotate tree about masks.
         */
        /*
         * Annotate tree about masks.
         */

-                       if (*mp = m = rn_new_radix_mask(x, 0))
-                               mp = &m->rm_mklist;
+                       MKGet(m);
+                       if (m) {
+                               Bzero(m, sizeof *m);
+                               m->rm_b = x->rn_b;
+                               m->rm_mask = x->rn_mask;
+                               x->rn_mklist = t->rn_mklist = m;
+                       }

 
                }
            }
 
                }
            }


@@ -724,7 +638,6 @@ rn_addroute(v_arg, n_arg, head, treenodes)
                                break;
                p->rn_mklist = m; *mp = 0;
        }
                                break;
                p->rn_mklist = m; *mp = 0;
        }

-on2:

 on2:
        /* Add new route to highest possible ancestor's list */
        if ((netmask == 0) || (masklen > p->rn_b ))
 on2:
        /* Add new route to highest possible ancestor's list */
        if ((netmask == 0) || (masklen > p->rn_b ))


@@ -736,9 +649,10 @@ on2:
        /*
         * Search through routes associated with node to
         * insert new route according to index.
        /*
         * Search through routes associated with node to
         * insert new route according to index.

-        * Need same criteria as when sorting dupedkeys to avoid
-        * double loop on deletion.
+        * For nodes of equal index, place more specific
+        * masks first.

         */
         */

+       cplim = netmask + mlen;

        for (mp = &x->rn_mklist; m = *mp; mp = &m->rn_mklist) {
                if (m->rn_b > masklen_leaf)
                        continue;
        for (mp = &x->rn_mklist; m = *mp; mp = &m->rn_mklist) {
                if (m->rn_b > masklen_leaf)
                        continue;


@@ -758,6 +672,39 @@ struct radix_node *
 rn_delete(v_arg, n_arg, head)
        void *v_arg, *n_arg;
        struct radix_node_head *head;
 rn_delete(v_arg, n_arg, head)
        void *v_arg, *n_arg;
        struct radix_node_head *head;

+{
+       register struct radix_node *t, *x, *tt;
+       struct radix_node *dupedkey;
+       caddr_t v, netmask;
+       int b, head_off, vlen;
+
+       v = v_arg;
+       x = head->rnh_treetop;
+       tt = rn_search(v, x);
+       head_off = x->rn_off;
+       vlen =  *(u_char *)v;
+       if (tt == 0 ||
+           Bcmp(v + head_off, tt->rn_key + head_off, vlen - head_off))
+               return (0);
+       /*
+        * Check for possiblity of key being duped in tree.
+        */
+       if (dupedkey = tt->rn_dupedkey) {
+               if (netmask_arg) 
+                       netmask = rn_search(netmask_arg, rn_masktop)->rn_key;
+               else
+                       netmask = 0;
+               while (tt->rn_mask != netmask)
+                       if ((tt = tt->rn_dupedkey) == 0)
+                               return (0);
+       }
+       return (rn_delete1(tt, head));
+}
+
+struct radix_node *
+rn_delete1(rn, head)
+       struct radix_node *rn;
+       struct radix_node_head *head;

 {
        register struct radix_node *t, *p, *x, *tt;
        struct radix_node *m, *saved_m, **mp;
 {
        register struct radix_node *t, *p, *x, *tt;
        struct radix_node *m, *saved_m, **mp;


@@ -769,6 +716,7 @@ rn_delete(v_arg, n_arg, head)
        base = tt = rn_search_unmapped(v_arg, head);
        if (tt == 0 || Bcmp(v + head_off, tt->rn_key + head_off, vlen))
                return (0);
        base = tt = rn_search_unmapped(v_arg, head);
        if (tt == 0 || Bcmp(v + head_off, tt->rn_key + head_off, vlen))
                return (0);

+

        p = t = tt->rn_p;
        (void) rn_masksubr(v_arg, n_arg, head_off, head, &masklen);
        masklen_leaf = -1 - masklen;
        p = t = tt->rn_p;
        (void) rn_masksubr(v_arg, n_arg, head_off, head, &masklen);
        masklen_leaf = -1 - masklen;


@@ -790,11 +738,8 @@ rn_delete(v_arg, n_arg, head)
                        *mp = tt->rn_mklist;
                        break;
                }
                        *mp = tt->rn_mklist;
                        break;
                }

-       if (m == 0) {
-               log(LOG_ERR, "rn_delete: couldn't find our annotation\n");
-               if (tt->rn_flags & RNF_NORMAL)
-                       return (0); /* Dangling ref to us */
-       }
+       if (m == 0)
+               printf("rn_delete: couldn't find our annotation\n");

 on1:
        /*
         * Eliminate us from tree
 on1:
        /*
         * Eliminate us from tree


@@ -806,7 +751,7 @@ on1:
        for (t = rn_clist; t && t->rn_ybro != tt; t = t->rn_ybro) {}
        if (t) t->rn_ybro = tt->rn_ybro;
 #endif
        for (t = rn_clist; t && t->rn_ybro != tt; t = t->rn_ybro) {}
        if (t) t->rn_ybro = tt->rn_ybro;
 #endif

-       if (dupedkey = saved_tt->rn_dupedkey) {
+       if (dupedkey) {

                if (tt == base) {
                        x = dupedkey; x->rn_p = t;
                        if (t->rn_l == tt) t->rn_l = x; else t->rn_r = x;
                if (tt == base) {
                        x = dupedkey; x->rn_p = t;
                        if (t->rn_l == tt) t->rn_l = x; else t->rn_r = x;


@@ -814,7 +759,7 @@ on1:
                        for (x = base; x && x->rn_dupedkey != tt;)
                                x = x->rn_dupedkey;
                        if (x) x->rn_dupedkey = tt->rn_dupedkey;
                        for (x = base; x && x->rn_dupedkey != tt;)
                                x = x->rn_dupedkey;
                        if (x) x->rn_dupedkey = tt->rn_dupedkey;

-                       else log(LOG_ERR, "rn_delete: couldn't find us\n");
+                       else printf("rn_delete: couldn't find us\n");

                }
                x = tt + 1;
                if  (x->rn_flags & RNF_ACTIVE) {
                }
                x = tt + 1;
                if  (x->rn_flags & RNF_ACTIVE) {


@@ -934,7 +879,6 @@ rn_inithead(head, off)
        rnh->rnh_deladdr = rn_delete;
        rnh->rnh_matchaddr = rn_match;
        rnh->rnh_lookup = rn_lookup;
        rnh->rnh_deladdr = rn_delete;
        rnh->rnh_matchaddr = rn_match;
        rnh->rnh_lookup = rn_lookup;

-       rnh->rnh_lookup = rn_lookup;

        rnh->rnh_walktree = rn_walktree;
        rnh->rnh_bits_matched = rn_unmapped_bits_matched;
        rnh->rnh_set_mask = rn_unmapped_set_mask;
        rnh->rnh_walktree = rn_walktree;
        rnh->rnh_bits_matched = rn_unmapped_bits_matched;
        rnh->rnh_set_mask = rn_unmapped_set_mask;


@@ -953,8 +897,7 @@ rn_init()
                        max_keylen = dom->dom_maxrtkey;
 #endif
        if (max_keylen == 0) {
                        max_keylen = dom->dom_maxrtkey;
 #endif
        if (max_keylen == 0) {

-               log(LOG_ERR,
-                   "rn_init: radix functions require max_keylen be set\n");
+               printf("rn_init: radix functions require max_keylen be set\n");

                return;
        }
        R_Malloc(rn_zeros, char *, 3 * max_keylen);
                return;
        }
        R_Malloc(rn_zeros, char *, 3 * max_keylen);