fix bug in routing socket, add sanity check . . .

[unix-history] / usr / src / sys / net / radix.c

diff --git a/usr/src/sys/net/radix.c b/usr/src/sys/net/radix.c
index 12ea6bb..b4b5d9e 100644 (file)
--- a/usr/src/sys/net/radix.c
+++ b/usr/src/sys/net/radix.c
@@ -1,32 +1,27 @@
 /*
 /*

- * Copyright (c) 1982, 1988 Regents of the University of California.
+ * Copyright (c) 1988, 1989  Regents of the University of California.

  * All rights reserved.
  *
  * All rights reserved.
  *

- * Redistribution and use in source and binary forms are permitted
- * provided that the above copyright notice and this paragraph are
- * duplicated in all such forms and that any documentation,
- * advertising materials, and other materials related to such
- * distribution and use acknowledge that the software was developed
- * by the University of California, Berkeley.  The name of the
- * University may not be used to endorse or promote products derived
- * from this software without specific prior written permission.
- * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
- * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
- * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
+ * %sccs.include.redist.c%

  *
  *

- *     @(#)radix.c     7.1 (Berkeley) %G%
+ *     @(#)radix.c     7.7 (Berkeley) %G%

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

-typedef unsigned char u_char;
+#include "param.h"

 #include "radix.h"
 #include "radix.h"

+#include "malloc.h"
+#define        M_DONTWAIT M_NOWAIT

 #endif
 #endif

-struct radix_node_head *radix_node_head;
+struct radix_node_head *mask_rnhead;
+#define rn_maskhead mask_rnhead->rnh_treetop

 struct radix_mask *rn_mkfreelist;
 struct radix_mask *rn_mkfreelist;

-#define rn_maskhead radix_node_head->rnh_treetop
+struct radix_node_head *radix_node_head;
+#undef Bcmp
+#define Bcmp(a, b, l) (l == 0 ? 0 : bcmp((caddr_t)(a), (caddr_t)(b), (u_long)l))

 /*
  * The data structure for the keys is a radix tree with one way
  * branching removed.  The index rn_b at an internal node n represents a bit
 /*
  * The data structure for the keys is a radix tree with one way
  * branching removed.  The index rn_b at an internal node n represents a bit


@@ -60,7 +55,7 @@ struct radix_mask *rn_mkfreelist;
 struct radix_node *
 rn_search(v, head)
        struct radix_node *head;
 struct radix_node *
 rn_search(v, head)
        struct radix_node *head;

-       register char *v;
+       register caddr_t v;

 {
        register struct radix_node *x;
 
 {
        register struct radix_node *x;
 


@@ -73,6 +68,23 @@ rn_search(v, head)
        return x;
 };
 
        return x;
 };
 

+struct radix_node *
+rn_search_m(v, head, m)
+       struct radix_node *head;
+       register caddr_t v, m;
+{
+       register struct radix_node *x;
+
+       for (x = head; x->rn_b >= 0;) {
+               if ((x->rn_bmask & m[x->rn_off]) &&
+                   (x->rn_bmask & v[x->rn_off]))
+                       x = x->rn_r;
+               else
+                       x = x->rn_l;
+       }
+       return x;
+};
+

 
 static int gotOddMasks;
 static char maskedKey[MAXKEYLEN];
 
 static int gotOddMasks;
 static char maskedKey[MAXKEYLEN];


@@ -80,13 +92,13 @@ static char maskedKey[MAXKEYLEN];
 struct radix_node *
 rn_match(v, head)
        struct radix_node *head;
 struct radix_node *
 rn_match(v, head)
        struct radix_node *head;

-       char *v;
+       caddr_t v;

 {
        register struct radix_node *t = head, *x;
 {
        register struct radix_node *t = head, *x;

-       register char *cp = v, *cp2, *cp3;
-       char *cplim, *mstart;
+       register caddr_t cp = v, cp2, cp3;
+       caddr_t cplim, mstart;

        struct radix_node *saved_t;
        struct radix_node *saved_t;

-       int off = t->rn_off, vlen = *(u_char *)cp, head_off, matched_off;
+       int off = t->rn_off, vlen = *(u_char *)cp, matched_off;

 
        /*
         * Open code rn_search(v, head) to avoid overhead of extra
 
        /*
         * Open code rn_search(v, head) to avoid overhead of extra


@@ -105,6 +117,12 @@ rn_match(v, head)
        for (; cp < cplim; cp++, cp2++)
                if (*cp != *cp2)
                        goto on1;
        for (; cp < cplim; cp++, cp2++)
                if (*cp != *cp2)
                        goto on1;

+       /*
+        * This extra grot is in case we are explicitly asked
+        * to look up the default.  Ugh!
+        */
+       if ((t->rn_flags & RNF_ROOT) && t->rn_dupedkey)
+               t = t->rn_dupedkey;

        return t;
 on1:
        matched_off = cp - v;
        return t;
 on1:
        matched_off = cp - v;


@@ -117,11 +135,13 @@ on1:
                 * a route to a net.
                 */
                cp3 = matched_off + t->rn_mask;
                 * a route to a net.
                 */
                cp3 = matched_off + t->rn_mask;

+               cp2 = matched_off + t->rn_key;

                for (; cp < cplim; cp++)
                        if ((*cp2++ ^ *cp) & *cp3++)
                                break;
                if (cp == cplim)
                        return t;
                for (; cp < cplim; cp++)
                        if ((*cp2++ ^ *cp) & *cp3++)
                                break;
                if (cp == cplim)
                        return t;

+               cp = matched_off + v;

            }
        } while (t = t->rn_dupedkey);
        t = saved_t;
            }
        } while (t = t->rn_dupedkey);
        t = saved_t;


@@ -130,6 +150,12 @@ on1:
                register struct radix_mask *m;
                t = t->rn_p;
                if (m = t->rn_mklist) {
                register struct radix_mask *m;
                t = t->rn_p;
                if (m = t->rn_mklist) {

+                       /*
+                        * After doing measurements here, it may
+                        * turn out to be faster to open code
+                        * rn_search_m here instead of always
+                        * copying and masking.
+                        */

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


@@ -158,7 +184,7 @@ int rn_saveinfo;
 
 struct radix_node *
 rn_newpair(v, b, nodes)
 
 struct radix_node *
 rn_newpair(v, b, nodes)

-       char *v;
+       caddr_t v;

        struct radix_node nodes[2];
 {
        register struct radix_node *tt = nodes, *t = tt + 1;
        struct radix_node nodes[2];
 {
        register struct radix_node *tt = nodes, *t = tt + 1;


@@ -176,23 +202,23 @@ rn_newpair(v, b, nodes)
 int rn_debug =  1;
 struct radix_node *
 rn_insert(v, head, dupentry, nodes)
 int rn_debug =  1;
 struct radix_node *
 rn_insert(v, head, dupentry, nodes)

-       char *v;
+       caddr_t v;

        struct radix_node *head;
        int *dupentry;
        struct radix_node nodes[2];
 {
        int head_off = head->rn_off, vlen = (int)*((u_char *)v);
        register struct radix_node *t = rn_search(v, head);
        struct radix_node *head;
        int *dupentry;
        struct radix_node nodes[2];
 {
        int head_off = head->rn_off, vlen = (int)*((u_char *)v);
        register struct radix_node *t = rn_search(v, head);

-       register char *cp = v + head_off;
+       register caddr_t cp = v + head_off;

        register int b;
        struct radix_node *tt;
        /*
         *find first bit at which v and t->rn_key differ
         */
     {
        register int b;
        struct radix_node *tt;
        /*
         *find first bit at which v and t->rn_key differ
         */
     {

-       register char *cp2 = t->rn_key + head_off;
+       register caddr_t cp2 = t->rn_key + head_off;

        register int cmp_res;
        register int cmp_res;

-       char *cplim = v + vlen;
+       caddr_t cplim = v + vlen;

 
        while (cp < cplim)
                if (*cp2++ != *cp++)
 
        while (cp < cplim)
                if (*cp2++ != *cp++)


@@ -237,18 +263,62 @@ on1:
        return (tt);
 }
 
        return (tt);
 }
 

+struct radix_node *
+rn_addmask(netmask, search, skip)
+caddr_t netmask;
+{
+       register struct radix_node *x;
+       register caddr_t cp, cplim;
+       register int b, mlen, j;
+       int maskduplicated;
+
+       mlen = *(u_char *)netmask;
+       if (search) {
+               x = rn_search(netmask, rn_maskhead);
+               mlen = *(u_char *)netmask;
+               if (Bcmp(netmask, x->rn_key, mlen) == 0)
+                       return (x);
+       }
+       R_Malloc(x, struct radix_node *, MAXKEYLEN + 2 * sizeof (*x));
+       if (x == 0)
+               return (0);
+       Bzero(x, MAXKEYLEN + 2 * sizeof (*x));
+       cp = (caddr_t)(x + 2);
+       Bcopy(netmask, cp, mlen);
+       netmask = cp;
+       x = rn_insert(netmask, rn_maskhead, &maskduplicated, x);
+       /*
+        * Calculate index of mask.
+        */
+       cplim = netmask + mlen;
+       for (cp = netmask + skip; cp < cplim; cp++)
+               if (*(u_char *)cp != 0xff)
+                       break;
+       b = (cp - netmask) << 3;
+       if (cp != cplim) {
+               if (*cp != 0) {
+                       gotOddMasks = 1;
+                       for (j = 0x80; j; b++, j >>= 1)  
+                               if ((j & *cp) == 0)
+                                       break;
+               }
+       }
+       x->rn_b = -1 - b;
+       return (x);
+}
+

 struct radix_node *
 rn_addroute(v, netmask, head, treenodes)
 struct radix_node *
 rn_addroute(v, netmask, head, treenodes)

-       struct radix_node *head;
-       char *netmask, *v;
+struct radix_node *head;
+       caddr_t netmask, v;

        struct radix_node treenodes[2];
 {
        register int j;
        struct radix_node treenodes[2];
 {
        register int j;

-       register char *cp;
+       register caddr_t cp;

        register struct radix_node *t, *x, *tt;
        short b = 0, b_leaf;
        register struct radix_node *t, *x, *tt;
        short b = 0, b_leaf;

-       int vlen = *(u_char *)v, maskduplicated = 0, mlen, keyduplicated;
-       char *cplim; unsigned char *maskp;
+       int vlen = *(u_char *)v, mlen, keyduplicated;
+       caddr_t cplim; unsigned char *maskp;

        struct radix_mask *m, **mp;
        struct radix_node *saved_tt;
 
        struct radix_mask *m, **mp;
        struct radix_node *saved_tt;
 


@@ -262,22 +332,24 @@ rn_addroute(v, netmask, head, treenodes)
        if (netmask)  {
                x = rn_search(netmask, rn_maskhead);
                mlen = *(u_char *)netmask;
        if (netmask)  {
                x = rn_search(netmask, rn_maskhead);
                mlen = *(u_char *)netmask;

-               if (Bcmp(netmask, x->rn_key, mlen) == 0) {
-                       maskduplicated = 1;
-                       netmask = x->rn_key;
-                       b = -1 - x->rn_b;
+               if (Bcmp(netmask, x->rn_key, mlen) != 0) {
+                       x = rn_addmask(netmask, 0, head->rn_off);
+                       if (x == 0)
+                               return (0);

                }
                }

+               netmask = x->rn_key;
+               b = -1 - x->rn_b;

        }
        /*
         * Deal with duplicated keys: attach node to previous instance
         */
        saved_tt = tt = rn_insert(v, head, &keyduplicated, treenodes);
        if (keyduplicated) {
        }
        /*
         * Deal with duplicated keys: attach node to previous instance
         */
        saved_tt = tt = rn_insert(v, head, &keyduplicated, treenodes);
        if (keyduplicated) {

-               if (tt->rn_mask == netmask)
-                       return (0);
-               for (; tt->rn_dupedkey; tt = tt->rn_dupedkey)
+               do {

                        if (tt->rn_mask == netmask)
                                return (0);
                        if (tt->rn_mask == netmask)
                                return (0);

+                       t = tt;
+               } while (tt = tt->rn_dupedkey);

                /*
                 * If the mask is not duplicated, we wouldn't
                 * find it among possible duplicate key entries
                /*
                 * If the mask is not duplicated, we wouldn't
                 * find it among possible duplicate key entries


@@ -288,55 +360,23 @@ rn_addroute(v, netmask, head, treenodes)
                 * It is an unfortunate pain having to relocate
                 * the head of the list.
                 */
                 * It is an unfortunate pain having to relocate
                 * the head of the list.
                 */

-               tt->rn_dupedkey = treenodes;
-               tt = treenodes;
+               t->rn_dupedkey = tt = treenodes;

 #ifdef RN_DEBUG
                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;
 #ifdef RN_DEBUG
                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;

-               tt->rn_key = t->rn_key;
-               tt->rn_b = t->rn_b;
+               tt->rn_key = (caddr_t) v;
+               tt->rn_b = -1;

                tt->rn_flags = t->rn_flags & ~RNF_ROOT;
        }
        /*
         * Put mask in tree.
         */
                tt->rn_flags = t->rn_flags & ~RNF_ROOT;
        }
        /*
         * Put mask in tree.
         */

-       if (netmask == 0)
-               goto on1;
-       if (maskduplicated == 0) {
-               Malloc(x, struct radix_node *, MAXKEYLEN + 2 * sizeof (*x));
-               if (x == 0)
-                       return (0);
-               Bzero(x, MAXKEYLEN + 2 * sizeof (*x));
-               cp = (char *)(x + 2);
-               bcopy(netmask, cp, mlen);
-               netmask = cp;
-               x = rn_insert(netmask, rn_maskhead, &maskduplicated, x);
-               /*
-                * Calculate index of mask.
-                */
-               cplim = netmask + vlen;
-               for (cp = netmask + head->rn_off; cp < cplim; cp++)
-                       if (*(u_char *)cp != 0xff)
-                               break;
-               b = (cp - netmask) << 3;
-               if (cp != cplim) {
-                       if (*cp != 0) {
-                               gotOddMasks = 1;
-                               for (j = 0x80; j; b++, j >>= 1)  
-                                       if ((j & *cp) == 0)
-                                               break;
-                       }
-               }
-               x->rn_b = -1 - b;
+       if (netmask) {
+               tt->rn_mask = netmask;
+               tt->rn_b = x->rn_b;

        }
        }

-       /*
-        * Set up usual parameters
-        */
-       tt->rn_mask = netmask;
-       tt->rn_b = x->rn_b;
-on1:

        t = saved_tt->rn_p;
        b_leaf = -1 - t->rn_b;
        if (t->rn_r == saved_tt) x = t->rn_l; else x = t->rn_r;
        t = saved_tt->rn_p;
        b_leaf = -1 - t->rn_b;
        if (t->rn_r == saved_tt) x = t->rn_l; else x = t->rn_r;


@@ -348,7 +388,7 @@ on1:
                                Bzero(m, sizeof *m);
                                m->rm_b = x->rn_b;
                                m->rm_mask = x->rn_mask;
                                Bzero(m, sizeof *m);
                                m->rm_b = x->rn_b;
                                m->rm_mask = x->rn_mask;

-                               t->rn_mklist = m;
+                               x->rn_mklist = t->rn_mklist = m;

                        }
                }
        } else if (x->rn_mklist) {
                        }
                }
        } else if (x->rn_mklist) {


@@ -407,13 +447,13 @@ on2:
 
 struct radix_node *
 rn_delete(v, netmask, head)
 
 struct radix_node *
 rn_delete(v, netmask, head)

-       char *v, *netmask;
+       caddr_t v, netmask;

        struct radix_node *head;
 {
        register struct radix_node *t, *p, *x = head;
        register struct radix_node *tt = rn_search(v, x);
        int b, head_off = x->rn_off, vlen =  * (u_char *) v;
        struct radix_node *head;
 {
        register struct radix_node *t, *p, *x = head;
        register struct radix_node *tt = rn_search(v, x);
        int b, head_off = x->rn_off, vlen =  * (u_char *) v;

-       struct radix_mask *m, **mp;
+       struct radix_mask *m, *saved_m, **mp;

        struct radix_node *dupedkey, *saved_tt = tt;
 
        if (tt == 0 ||
        struct radix_node *dupedkey, *saved_tt = tt;
 
        if (tt == 0 ||


@@ -429,9 +469,13 @@ rn_delete(v, netmask, head)
                        if (tt == 0)
                                return (0);
        }
                        if (tt == 0)
                                return (0);
        }

-       if (tt->rn_mask == 0)
+       if (tt->rn_mask == 0 || (saved_m = m = tt->rn_mklist) == 0)
+               goto on1;
+       if (m->rm_mask != tt->rn_mask) {
+               printf("rn_delete: inconsistent annotation\n");

                goto on1;
                goto on1;

-       if ((m = tt->rn_mklist) && --m->rm_refs >= 0)
+       }
+       if (--m->rm_refs >= 0)

                goto on1;
        b = -1 - tt->rn_b;
        t = saved_tt->rn_p;
                goto on1;
        b = -1 - tt->rn_b;
        t = saved_tt->rn_p;


@@ -442,15 +486,13 @@ rn_delete(v, netmask, head)
                t = t->rn_p;
        } while (b <= t->rn_b && x != head);
        for (mp = &x->rn_mklist; m = *mp; mp = &m->rm_mklist)
                t = t->rn_p;
        } while (b <= t->rn_b && x != head);
        for (mp = &x->rn_mklist; m = *mp; mp = &m->rm_mklist)

-               if (m->rm_mask == tt->rn_mask)
-                       break;
-       if (m) {
-               if (m->rm_refs < 0) {
+               if (m == saved_m) {

                        *mp = m->rm_mklist;
                        MKFree(m);
                        *mp = m->rm_mklist;
                        MKFree(m);

+                       break;

                }
                }

-       } else
-               printf("rn_delete: couldn't find our mask\n");
+       if (m == 0)
+               printf("rn_delete: couldn't find our annotation\n");

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


@@ -501,7 +543,11 @@ on1:
                } else {
                        for (m = t->rn_mklist; m;) {
                                struct radix_mask *mm = m->rm_mklist;
                } else {
                        for (m = t->rn_mklist; m;) {
                                struct radix_mask *mm = m->rm_mklist;

-                               MKFree(m);
+                               if (m == x->rn_mklist && (--(m->rm_refs) < 0)) {
+                                       x->rn_mklist = 0;
+                                       MKFree(m);
+                               } else
+                                       printf("rn_delete: Orphaned mask\n");

                                m = mm;
                        }
                }
                                m = mm;
                        }
                }


@@ -531,17 +577,17 @@ rn_inithead(head, off, af)
 struct radix_node_head **head;
 int off;
 {
 struct radix_node_head **head;
 int off;
 {

-       register struct radix_node_head *hp;
+       register struct radix_node_head *rnh;

        register struct radix_node *t, *tt, *ttt;
        if (*head)
                return (1);
        register struct radix_node *t, *tt, *ttt;
        if (*head)
                return (1);

-       Malloc(hp, struct radix_node_head *, sizeof (*hp));
-       if (hp == 0)
+       R_Malloc(rnh, struct radix_node_head *, sizeof (*rnh));
+       if (rnh == 0)

                return (0);
                return (0);

-       Bzero(hp, sizeof (*hp));
-       *head = hp;
-       t = rn_newpair(rn_zeros, off, hp->rnh_nrt.nrt_nodes);
-       ttt = &(hp->rnh_upper);
+       Bzero(rnh, sizeof (*rnh));
+       *head = rnh;
+       t = rn_newpair(rn_zeros, off, rnh->rnh_nodes);
+       ttt = rnh->rnh_nodes + 2;

        t->rn_r = ttt;
        t->rn_p = t;
        tt = t->rn_l;
        t->rn_r = ttt;
        t->rn_p = t;
        tt = t->rn_l;


@@ -549,20 +595,21 @@ int off;
        tt->rn_b = -1 - off;
        *ttt = *tt;
        ttt->rn_key = rn_ones;
        tt->rn_b = -1 - off;
        *ttt = *tt;
        ttt->rn_key = rn_ones;

-       hp->rnh_af = af;
-       hp->rnh_treetop = t;
+       rnh->rnh_af = af;
+       rnh->rnh_treetop = t;

        if (radix_node_head == 0) {
        if (radix_node_head == 0) {

-               char *cp = rn_ones, *cplim = rn_ones + MAXKEYLEN;
+               caddr_t cp = rn_ones, cplim = rn_ones + MAXKEYLEN;

                while (cp < cplim)
                        *cp++ = -1;
                if (rn_inithead(&radix_node_head, 0, 0) == 0) {
                while (cp < cplim)
                        *cp++ = -1;
                if (rn_inithead(&radix_node_head, 0, 0) == 0) {

-                       Free(hp);
+                       Free(rnh);

                        *head = 0;
                        return (0);
                }
                        *head = 0;
                        return (0);
                }

+               mask_rnhead = radix_node_head;

        }
        }

-       hp->rnh_next = radix_node_head->rnh_next;
-       if (radix_node_head != hp)
-               radix_node_head->rnh_next = hp;
+       rnh->rnh_next = radix_node_head->rnh_next;
+       if (radix_node_head != rnh)
+               radix_node_head->rnh_next = rnh;

        return (1);
 }
        return (1);
 }