xnu-2422.1.72.tar.gz

[apple/xnu.git] / bsd / net / radix.c

diff --git a/bsd/net/radix.c b/bsd/net/radix.c
index 1fb667e17e234861b5c4da5ca2c9f96a2aad0921..fdc7058b3e0006cb8c6130be8ac21e3a6218e21e 100644 (file)
--- a/bsd/net/radix.c
+++ b/bsd/net/radix.c
@@ -1,17 +1,20 @@
 /*
 /*

- * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
+ * Copyright (c) 2000-2013 Apple Inc. All rights reserved.
+ *
+ * @APPLE_OSREFERENCE_LICENSE_HEADER_START@

  *
  *

- * @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
  * 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.
- * 
+ * compliance with the License. The rights granted to you under the License
+ * may not be used to create, or enable the creation or redistribution of,
+ * unlawful or unlicensed copies of an Apple operating system, or to
+ * circumvent, violate, or enable the circumvention or violation of, any
+ * terms of an Apple operating system software license agreement.
+ *
+ * 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,
  * 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,


@@ -19,8 +22,8 @@
  * 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.
  * 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@
+ *
+ * @APPLE_OSREFERENCE_LICENSE_HEADER_END@

  */
 /*
  * Copyright (c) 1988, 1989, 1993
  */
 /*
  * Copyright (c) 1988, 1989, 1993


@@ -63,27 +66,26 @@
  */
 #ifndef _RADIX_H_
 #include <sys/param.h>
  */
 #ifndef _RADIX_H_
 #include <sys/param.h>

-#ifdef KERNEL

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

-#else
-#include <stdlib.h>
-#endif

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

+#include <sys/socket.h>
+#include <sys/socketvar.h>
+#include <kern/locks.h>

 #endif
 
 #endif
 

-static int     rn_walktree_from __P((struct radix_node_head *h, void *a,
-                                     void *m, walktree_f_t *f, void *w));
-static int rn_walktree __P((struct radix_node_head *, walktree_f_t *, void *));
+static int     rn_walktree_from(struct radix_node_head *h, void *a,
+                                     void *m, walktree_f_t *f, void *w);
+static int rn_walktree(struct radix_node_head *, walktree_f_t *, void *);

 static struct radix_node
 static struct radix_node

-        *rn_insert __P((void *, struct radix_node_head *, int *,
-                       struct radix_node [2])),
-        *rn_newpair __P((void *, int, struct radix_node[2])),
-        *rn_search __P((void *, struct radix_node *)),
-        *rn_search_m __P((void *, struct radix_node *, void *));
+        *rn_insert(void *, struct radix_node_head *, int *,
+                       struct radix_node [2]),
+        *rn_newpair(void *, int, struct radix_node[2]),
+        *rn_search(void *, struct radix_node *),
+        *rn_search_m(void *, struct radix_node *, void *);

 
 static int     max_keylen;
 static struct radix_mask *rn_mkfreelist;
 
 static int     max_keylen;
 static struct radix_mask *rn_mkfreelist;


@@ -92,17 +94,23 @@ static char *addmask_key;
 static char normal_chars[] = {0, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, -1};
 static char *rn_zeros, *rn_ones;
 
 static char normal_chars[] = {0, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, -1};
 static char *rn_zeros, *rn_ones;
 

+
+extern lck_grp_t       *domain_proto_mtx_grp;
+extern lck_attr_t      *domain_proto_mtx_attr;
+

 #define rn_masktop (mask_rnhead->rnh_treetop)
 #undef Bcmp
 #define Bcmp(a, b, l) \
 #define rn_masktop (mask_rnhead->rnh_treetop)
 #undef Bcmp
 #define Bcmp(a, b, l) \

-       (l == 0 ? 0 : bcmp((caddr_t)(a), (caddr_t)(b), (u_long)l))
+       (l == 0 ? 0 : bcmp((caddr_t)(a), (caddr_t)(b), (uint32_t)l))

 
 

-static int     rn_lexobetter __P((void *m_arg, void *n_arg));
+static int     rn_lexobetter(void *m_arg, void *n_arg);

 static struct radix_mask *
 static struct radix_mask *

-               rn_new_radix_mask __P((struct radix_node *tt,
-                                      struct radix_mask *next));
-static int     rn_satsifies_leaf __P((char *trial, struct radix_node *leaf,
-                                      int skip));
+               rn_new_radix_mask(struct radix_node *tt,
+                                      struct radix_mask *next);
+static int rn_satisfies_leaf(char *trial, struct radix_node *leaf, int skip,
+    rn_matchf_t *f, void *w);
+
+#define        RN_MATCHF(rn, f, arg)   (f == NULL || (*f)((rn), arg))

 
 /*
  * The data structure for the keys is a radix tree with one way
 
 /*
  * The data structure for the keys is a radix tree with one way


@@ -139,12 +147,10 @@ static int        rn_satsifies_leaf __P((char *trial, struct radix_node *leaf,
  */
 
 static struct radix_node *
  */
 
 static struct radix_node *

-rn_search(v_arg, head)
-       void *v_arg;
-       struct radix_node *head;
+rn_search(void *v_arg, struct radix_node *head)

 {
 {

-       register struct radix_node *x;
-       register caddr_t v;
+       struct radix_node *x;
+       caddr_t v;

 
        for (x = head, v = v_arg; x->rn_bit >= 0;) {
                if (x->rn_bmask & v[x->rn_offset])
 
        for (x = head, v = v_arg; x->rn_bit >= 0;) {
                if (x->rn_bmask & v[x->rn_offset])


@@ -156,12 +162,10 @@ rn_search(v_arg, head)
 }
 
 static struct radix_node *
 }
 
 static struct radix_node *

-rn_search_m(v_arg, head, m_arg)
-       struct radix_node *head;
-       void *v_arg, *m_arg;
+rn_search_m(void *v_arg, struct radix_node *head, void *m_arg)

 {
 {

-       register struct radix_node *x;
-       register caddr_t v = v_arg, m = m_arg;
+       struct radix_node *x;
+       caddr_t v = v_arg, m = m_arg;

 
        for (x = head; x->rn_bit >= 0;) {
                if ((x->rn_bmask & m[x->rn_offset]) &&
 
        for (x = head; x->rn_bit >= 0;) {
                if ((x->rn_bmask & m[x->rn_offset]) &&


@@ -174,11 +178,10 @@ rn_search_m(v_arg, head, m_arg)
 }
 
 int
 }
 
 int

-rn_refines(m_arg, n_arg)
-       void *m_arg, *n_arg;
+rn_refines(void *m_arg, void *n_arg)

 {
 {

-       register caddr_t m = m_arg, n = n_arg;
-       register caddr_t lim, lim2 = lim = n + *(u_char *)n;
+       caddr_t m = m_arg, n = n_arg;
+       caddr_t lim, lim2 = lim = n + *(u_char *)n;

        int longer = (*(u_char *)n++) - (int)(*(u_char *)m++);
        int masks_are_equal = 1;
 
        int longer = (*(u_char *)n++) - (int)(*(u_char *)m++);
        int masks_are_equal = 1;
 


@@ -201,20 +204,25 @@ rn_refines(m_arg, n_arg)
 }
 
 struct radix_node *
 }
 
 struct radix_node *

-rn_lookup(v_arg, m_arg, head)
-       void *v_arg, *m_arg;
-       struct radix_node_head *head;
+rn_lookup(void *v_arg, void *m_arg, struct radix_node_head *head)

 {
 {

-       register struct radix_node *x;
-       caddr_t netmask = 0;
+       return (rn_lookup_args(v_arg, m_arg, head, NULL, NULL));
+}
+
+struct radix_node *
+rn_lookup_args(void *v_arg, void *m_arg, struct radix_node_head *head,
+    rn_matchf_t *f, void *w)
+{
+       struct radix_node *x;
+       caddr_t netmask = NULL;

 
        if (m_arg) {
                x = rn_addmask(m_arg, 1, head->rnh_treetop->rn_offset);
                if (x == 0)
 
        if (m_arg) {
                x = rn_addmask(m_arg, 1, head->rnh_treetop->rn_offset);
                if (x == 0)

-                       return (0);
+                       return (NULL);

                netmask = x->rn_key;
        }
                netmask = x->rn_key;
        }

-       x = rn_match(v_arg, head);
+       x = rn_match_args(v_arg, head, f, w);

        if (x && netmask) {
                while (x && x->rn_mask != netmask)
                        x = x->rn_dupedkey;
        if (x && netmask) {
                while (x && x->rn_mask != netmask)
                        x = x->rn_dupedkey;


@@ -222,13 +230,18 @@ rn_lookup(v_arg, m_arg, head)
        return x;
 }
 
        return x;
 }
 

+/*
+ * Returns true if address 'trial' has no bits differing from the
+ * leaf's key when compared under the leaf's mask.  In other words,
+ * returns true when 'trial' matches leaf.  If a leaf-matching
+ * routine is passed in, it is also used to find a match on the
+ * conditions defined by the caller of rn_match.
+ */

 static int
 static int

-rn_satsifies_leaf(trial, leaf, skip)
-       char *trial;
-       register struct radix_node *leaf;
-       int skip;
+rn_satisfies_leaf(char *trial, struct radix_node *leaf, int skip,
+    rn_matchf_t *f, void *w)

 {
 {

-       register char *cp = trial, *cp2 = leaf->rn_key, *cp3 = leaf->rn_mask;
+       char *cp = trial, *cp2 = leaf->rn_key, *cp3 = leaf->rn_mask;

        char *cplim;
        int length = min(*(u_char *)cp, *(u_char *)cp2);
 
        char *cplim;
        int length = min(*(u_char *)cp, *(u_char *)cp2);
 


@@ -240,21 +253,27 @@ rn_satsifies_leaf(trial, leaf, skip)
        for (cp += skip; cp < cplim; cp++, cp2++, cp3++)
                if ((*cp ^ *cp2) & *cp3)
                        return 0;
        for (cp += skip; cp < cplim; cp++, cp2++, cp3++)
                if ((*cp ^ *cp2) & *cp3)
                        return 0;

-       return 1;
+
+       return (RN_MATCHF(leaf, f, w));

 }
 
 struct radix_node *
 }
 
 struct radix_node *

-rn_match(v_arg, head)
-       void *v_arg;
-       struct radix_node_head *head;
+rn_match(void *v_arg, struct radix_node_head *head)
+{
+       return (rn_match_args(v_arg, head, NULL, NULL));
+}
+
+struct radix_node *
+rn_match_args(void *v_arg, struct radix_node_head *head,
+    rn_matchf_t *f, void *w)

 {
        caddr_t v = v_arg;
 {
        caddr_t v = v_arg;

-       register struct radix_node *t = head->rnh_treetop, *x;
-       register caddr_t cp = v, cp2;
+       struct radix_node *t = head->rnh_treetop, *x;
+       caddr_t cp = v, cp2;

        caddr_t cplim;
        struct radix_node *saved_t, *top = t;
        int off = t->rn_offset, vlen = *(u_char *)cp, matched_off;
        caddr_t cplim;
        struct radix_node *saved_t, *top = t;
        int off = t->rn_offset, vlen = *(u_char *)cp, matched_off;

-       register int test, b, rn_bit;
+       int test, b, rn_bit;

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


@@ -292,11 +311,26 @@ rn_match(v_arg, head)
         */
        if (t->rn_flags & RNF_ROOT)
                t = t->rn_dupedkey;
         */
        if (t->rn_flags & RNF_ROOT)
                t = t->rn_dupedkey;

-       return t;
+       if (t == NULL || RN_MATCHF(t, f, w)) {
+               return (t);
+       } else {
+               /*
+                * Although we found an exact match on the key,
+                * f() is looking for some other criteria as well.
+                * Continue looking as if the exact match failed.
+                */
+               if (t->rn_parent->rn_flags & RNF_ROOT) {
+                       /* Hit the top; have to give up */
+                       return (NULL);
+               }
+               b = 0;
+               goto keeplooking;
+       }

 on1:
        test = (*cp ^ *cp2) & 0xff; /* find first bit that differs */
        for (b = 7; (test >>= 1) > 0;)
                b--;
 on1:
        test = (*cp ^ *cp2) & 0xff; /* find first bit that differs */
        for (b = 7; (test >>= 1) > 0;)
                b--;

+keeplooking:

        matched_off = cp - v;
        b += matched_off << 3;
        rn_bit = -1 - b;
        matched_off = cp - v;
        b += matched_off << 3;
        rn_bit = -1 - b;


@@ -305,21 +339,23 @@ on1:
         */
        if ((saved_t = t)->rn_mask == 0)
                t = t->rn_dupedkey;
         */
        if ((saved_t = t)->rn_mask == 0)
                t = t->rn_dupedkey;

-       for (; t; t = t->rn_dupedkey)
+       for (; t; t = t->rn_dupedkey) {

                /*
                 * Even if we don't match exactly as a host,
                 * we may match if the leaf we wound up at is
                 * a route to a net.
                 */
                if (t->rn_flags & RNF_NORMAL) {
                /*
                 * Even if we don't match exactly as a host,
                 * we may match if the leaf we wound up at is
                 * a route to a net.
                 */
                if (t->rn_flags & RNF_NORMAL) {

-                       if (rn_bit <= t->rn_bit)
-                               return t;
-               } else if (rn_satsifies_leaf(v, t, matched_off))
-                               return t;
+                       if ((rn_bit <= t->rn_bit) && RN_MATCHF(t, f, w))
+                               return (t);
+               } else if (rn_satisfies_leaf(v, t, matched_off, f, w)) {
+                       return (t);
+               }
+       }

        t = saved_t;
        /* start searching up the tree */
        do {
        t = saved_t;
        /* start searching up the tree */
        do {

-               register struct radix_mask *m;
+               struct radix_mask *m;

                t = t->rn_parent;
                m = t->rn_mklist;
                /*
                t = t->rn_parent;
                m = t->rn_mklist;
                /*


@@ -330,20 +366,21 @@ on1:
                 */
                while (m) {
                        if (m->rm_flags & RNF_NORMAL) {
                 */
                while (m) {
                        if (m->rm_flags & RNF_NORMAL) {

-                               if (rn_bit <= m->rm_bit)
+                               if ((rn_bit <= m->rm_bit) &&
+                                   RN_MATCHF(m->rm_leaf, f, w))

                                        return (m->rm_leaf);
                        } else {
                                off = min(t->rn_offset, matched_off);
                                x = rn_search_m(v, t, m->rm_mask);
                                while (x && x->rn_mask != m->rm_mask)
                                        x = x->rn_dupedkey;
                                        return (m->rm_leaf);
                        } else {
                                off = min(t->rn_offset, matched_off);
                                x = rn_search_m(v, t, m->rm_mask);
                                while (x && x->rn_mask != m->rm_mask)
                                        x = x->rn_dupedkey;

-                               if (x && rn_satsifies_leaf(v, x, off))
-                                       return x;
+                               if (x && rn_satisfies_leaf(v, x, off, f, w))
+                                       return (x);

                        }
                        m = m->rm_mklist;
                }
        } while (t != top);
                        }
                        m = m->rm_mklist;
                }
        } while (t != top);

-       return 0;
+       return (NULL);

 }
 
 #ifdef RN_DEBUG
 }
 
 #ifdef RN_DEBUG


@@ -354,12 +391,9 @@ int        rn_debug =  1;
 #endif
 
 static struct radix_node *
 #endif
 
 static struct radix_node *

-rn_newpair(v, b, nodes)
-       void *v;
-       int b;
-       struct radix_node nodes[2];
+rn_newpair(void *v, int b, struct radix_node nodes[2])

 {
 {

-       register struct radix_node *tt = nodes, *t = tt + 1;
+       struct radix_node *tt = nodes, *t = tt + 1;

        t->rn_bit = b;
        t->rn_bmask = 0x80 >> (b & 7);
        t->rn_left = tt;
        t->rn_bit = b;
        t->rn_bmask = 0x80 >> (b & 7);
        t->rn_left = tt;


@@ -368,7 +402,7 @@ rn_newpair(v, b, nodes)
        tt->rn_key = (caddr_t)v;
        tt->rn_parent = t;
        tt->rn_flags = t->rn_flags = RNF_ACTIVE;
        tt->rn_key = (caddr_t)v;
        tt->rn_parent = t;
        tt->rn_flags = t->rn_flags = RNF_ACTIVE;

-       tt->rn_mklist = t->rn_mklist = 0;
+       tt->rn_mklist = t->rn_mklist = NULL;

 #ifdef RN_DEBUG
        tt->rn_info = rn_nodenum++; t->rn_info = rn_nodenum++;
        tt->rn_twin = t;
 #ifdef RN_DEBUG
        tt->rn_info = rn_nodenum++; t->rn_info = rn_nodenum++;
        tt->rn_twin = t;


@@ -379,25 +413,22 @@ rn_newpair(v, b, nodes)
 }
 
 static struct radix_node *
 }
 
 static struct radix_node *

-rn_insert(v_arg, head, dupentry, nodes)
-       void *v_arg;
-       struct radix_node_head *head;
-       int *dupentry;
-       struct radix_node nodes[2];
+rn_insert(void *v_arg, struct radix_node_head *head, int *dupentry,
+         struct radix_node nodes[2])

 {
        caddr_t v = v_arg;
        struct radix_node *top = head->rnh_treetop;
        int head_off = top->rn_offset, vlen = (int)*((u_char *)v);
 {
        caddr_t v = v_arg;
        struct radix_node *top = head->rnh_treetop;
        int head_off = top->rn_offset, vlen = (int)*((u_char *)v);

-       register struct radix_node *t = rn_search(v_arg, top);
-       register caddr_t cp = v + head_off;
-       register int b;
+       struct radix_node *t = rn_search(v_arg, top);
+       caddr_t cp = v + head_off;
+       int b;

        struct radix_node *tt;
        /*
         * Find first bit at which v and t->rn_key differ
         */
     {
        struct radix_node *tt;
        /*
         * Find first bit at which v and t->rn_key differ
         */
     {

-       register caddr_t cp2 = t->rn_key + head_off;
-       register int cmp_res;
+       caddr_t cp2 = t->rn_key + head_off;
+       int cmp_res;

        caddr_t cplim = v + vlen;
 
        while (cp < cplim)
        caddr_t cplim = v + vlen;
 
        while (cp < cplim)


@@ -412,7 +443,7 @@ on1:
                cmp_res >>= 1;
     }
     {
                cmp_res >>= 1;
     }
     {

-       register struct radix_node *p, *x = top;
+       struct radix_node *p, *x = top;

        cp = v;
        do {
                p = x;
        cp = v;
        do {
                p = x;


@@ -449,14 +480,12 @@ on1:
 }
 
 struct radix_node *
 }
 
 struct radix_node *

-rn_addmask(n_arg, search, skip)
-       int search, skip;
-       void *n_arg;
+rn_addmask(void *n_arg, int search, int skip)

 {
        caddr_t netmask = (caddr_t)n_arg;
 {
        caddr_t netmask = (caddr_t)n_arg;

-       register struct radix_node *x;
-       register caddr_t cp, cplim;
-       register int b = 0, mlen, j;
+       struct radix_node *x;
+       caddr_t cp, cplim;
+       int b = 0, mlen, j;

        int maskduplicated, m0, isnormal;
        struct radix_node *saved_x;
        static int last_zeroed = 0;
        int maskduplicated, m0, isnormal;
        struct radix_node *saved_x;
        static int last_zeroed = 0;


@@ -487,21 +516,22 @@ rn_addmask(n_arg, search, skip)
        *addmask_key = last_zeroed = mlen;
        x = rn_search(addmask_key, rn_masktop);
        if (Bcmp(addmask_key, x->rn_key, mlen) != 0)
        *addmask_key = last_zeroed = mlen;
        x = rn_search(addmask_key, rn_masktop);
        if (Bcmp(addmask_key, x->rn_key, mlen) != 0)

-               x = 0;
+               x = NULL;

        if (x || search)
                return (x);
        R_Malloc(x, struct radix_node *, max_keylen + 2 * sizeof (*x));
        if ((saved_x = x) == 0)
        if (x || search)
                return (x);
        R_Malloc(x, struct radix_node *, max_keylen + 2 * sizeof (*x));
        if ((saved_x = x) == 0)

-               return (0);
+               return (NULL);

        Bzero(x, max_keylen + 2 * sizeof (*x));
        netmask = cp = (caddr_t)(x + 2);
        Bcopy(addmask_key, cp, mlen);
        x = rn_insert(cp, mask_rnhead, &maskduplicated, x);
        if (maskduplicated) {
                log(LOG_ERR, "rn_addmask: mask impossibly already in tree");
        Bzero(x, max_keylen + 2 * sizeof (*x));
        netmask = cp = (caddr_t)(x + 2);
        Bcopy(addmask_key, cp, mlen);
        x = rn_insert(cp, mask_rnhead, &maskduplicated, x);
        if (maskduplicated) {
                log(LOG_ERR, "rn_addmask: mask impossibly already in tree");

-               Free(saved_x);
+               R_Free(saved_x);

                return (x);
        }
                return (x);
        }

+       mask_rnhead->rnh_cnt++;

        /*
         * Calculate index of mask, and check for normalcy.
         */
        /*
         * Calculate index of mask, and check for normalcy.
         */


@@ -522,10 +552,9 @@ rn_addmask(n_arg, search, skip)
 }
 
 static int     /* XXX: arbitrary ordering for non-contiguous masks */
 }
 
 static int     /* XXX: arbitrary ordering for non-contiguous masks */

-rn_lexobetter(m_arg, n_arg)
-       void *m_arg, *n_arg;
+rn_lexobetter(void *m_arg, void *n_arg)

 {
 {

-       register u_char *mp = m_arg, *np = n_arg, *lim;
+       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)
                return 1;  /* not really, but need to check longer one first */


@@ -537,16 +566,14 @@ rn_lexobetter(m_arg, n_arg)
 }
 
 static struct radix_mask *
 }
 
 static struct radix_mask *

-rn_new_radix_mask(tt, next)
-       register struct radix_node *tt;
-       register struct radix_mask *next;
+rn_new_radix_mask(struct radix_node *tt, struct radix_mask *next)

 {
 {

-       register struct radix_mask *m;
+       struct radix_mask *m;

 
        MKGet(m);
        if (m == 0) {
                log(LOG_ERR, "Mask for route not entered\n");
 
        MKGet(m);
        if (m == 0) {
                log(LOG_ERR, "Mask for route not entered\n");

-               return (0);
+               return (NULL);

        }
        Bzero(m, sizeof *m);
        m->rm_bit = tt->rn_bit;
        }
        Bzero(m, sizeof *m);
        m->rm_bit = tt->rn_bit;


@@ -561,13 +588,11 @@ rn_new_radix_mask(tt, next)
 }
 
 struct radix_node *
 }
 
 struct radix_node *

-rn_addroute(v_arg, n_arg, head, treenodes)
-       void *v_arg, *n_arg;
-       struct radix_node_head *head;
-       struct radix_node treenodes[2];
+rn_addroute(void *v_arg, void *n_arg, struct radix_node_head *head,
+           struct radix_node treenodes[2])

 {
        caddr_t v = (caddr_t)v_arg, netmask = (caddr_t)n_arg;
 {
        caddr_t v = (caddr_t)v_arg, netmask = (caddr_t)n_arg;

-       register struct radix_node *t, *x = 0, *tt;
+       struct radix_node *t, *x = NULL, *tt;

        struct radix_node *saved_tt, *top = head->rnh_treetop;
        short b = 0, b_leaf = 0;
        int keyduplicated;
        struct radix_node *saved_tt, *top = head->rnh_treetop;
        short b = 0, b_leaf = 0;
        int keyduplicated;


@@ -583,7 +608,7 @@ rn_addroute(v_arg, n_arg, head, treenodes)
         */
        if (netmask)  {
                if ((x = rn_addmask(netmask, 0, top->rn_offset)) == 0)
         */
        if (netmask)  {
                if ((x = rn_addmask(netmask, 0, top->rn_offset)) == 0)

-                       return (0);
+                       return (NULL);

                b_leaf = x->rn_bit;
                b = -1 - x->rn_bit;
                netmask = x->rn_key;
                b_leaf = x->rn_bit;
                b = -1 - x->rn_bit;
                netmask = x->rn_key;


@@ -595,7 +620,7 @@ rn_addroute(v_arg, n_arg, head, treenodes)
        if (keyduplicated) {
                for (t = tt; tt; t = tt, tt = tt->rn_dupedkey) {
                        if (tt->rn_mask == netmask)
        if (keyduplicated) {
                for (t = tt; tt; t = tt, tt = tt->rn_dupedkey) {
                        if (tt->rn_mask == netmask)

-                               return (0);
+                               return (NULL);

                        if (netmask == 0 ||
                            (tt->rn_mask &&
                             ((b_leaf < tt->rn_bit) /* index(netmask) > node */
                        if (netmask == 0 ||
                            (tt->rn_mask &&
                             ((b_leaf < tt->rn_bit) /* index(netmask) > node */


@@ -640,6 +665,7 @@ rn_addroute(v_arg, n_arg, head, treenodes)
                tt->rn_bit = -1;
                tt->rn_flags = RNF_ACTIVE;
        }
                tt->rn_bit = -1;
                tt->rn_flags = RNF_ACTIVE;
        }

+       head->rnh_cnt++;

        /*
         * Put mask in tree.
         */
        /*
         * Put mask in tree.
         */


@@ -660,7 +686,7 @@ rn_addroute(v_arg, n_arg, head, treenodes)
        if (x->rn_bit < 0) {
            for (mp = &t->rn_mklist; x; x = x->rn_dupedkey)
                if (x->rn_mask && (x->rn_bit >= b_leaf) && x->rn_mklist == 0) {
        if (x->rn_bit < 0) {
            for (mp = &t->rn_mklist; x; x = x->rn_dupedkey)
                if (x->rn_mask && (x->rn_bit >= b_leaf) && x->rn_mklist == 0) {

-                       *mp = m = rn_new_radix_mask(x, 0);
+                       *mp = m = rn_new_radix_mask(x, NULL);

                        if (m)
                                mp = &m->rm_mklist;
                }
                        if (m)
                                mp = &m->rm_mklist;
                }


@@ -671,7 +697,7 @@ rn_addroute(v_arg, n_arg, head, treenodes)
                for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist)
                        if (m->rm_bit >= b_leaf)
                                break;
                for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist)
                        if (m->rm_bit >= b_leaf)
                                break;

-               t->rn_mklist = m; *mp = 0;
+               t->rn_mklist = m; *mp = NULL;

        }
 on2:
        /* Add new route to highest possible ancestor's list */
        }
 on2:
        /* Add new route to highest possible ancestor's list */


@@ -716,11 +742,9 @@ on2:
 }
 
 struct radix_node *
 }
 
 struct radix_node *

-rn_delete(v_arg, netmask_arg, head)
-       void *v_arg, *netmask_arg;
-       struct radix_node_head *head;
+rn_delete(void *v_arg, void *netmask_arg, struct radix_node_head *head)

 {
 {

-       register struct radix_node *t, *p, *x, *tt;
+       struct radix_node *t, *p, *x, *tt;

        struct radix_mask *m, *saved_m, **mp;
        struct radix_node *dupedkey, *saved_tt, *top;
        caddr_t v, netmask;
        struct radix_mask *m, *saved_m, **mp;
        struct radix_node *dupedkey, *saved_tt, *top;
        caddr_t v, netmask;


@@ -736,24 +760,24 @@ rn_delete(v_arg, netmask_arg, head)
        top = x;
        if (tt == 0 ||
            Bcmp(v + head_off, tt->rn_key + head_off, vlen - head_off))
        top = x;
        if (tt == 0 ||
            Bcmp(v + head_off, tt->rn_key + head_off, vlen - head_off))

-               return (0);
+               return (NULL);

        /*
         * Delete our route from mask lists.
         */
        if (netmask) {
                if ((x = rn_addmask(netmask, 1, head_off)) == 0)
        /*
         * Delete our route from mask lists.
         */
        if (netmask) {
                if ((x = rn_addmask(netmask, 1, head_off)) == 0)

-                       return (0);
+                       return (NULL);

                netmask = x->rn_key;
                while (tt->rn_mask != netmask)
                        if ((tt = tt->rn_dupedkey) == 0)
                netmask = x->rn_key;
                while (tt->rn_mask != netmask)
                        if ((tt = tt->rn_dupedkey) == 0)

-                               return (0);
+                               return (NULL);

        }
        if (tt->rn_mask == 0 || (saved_m = m = tt->rn_mklist) == 0)
                goto on1;
        if (tt->rn_flags & RNF_NORMAL) {
                if (m->rm_leaf != tt || m->rm_refs > 0) {
                        log(LOG_ERR, "rn_delete: inconsistent annotation\n");
        }
        if (tt->rn_mask == 0 || (saved_m = m = tt->rn_mklist) == 0)
                goto on1;
        if (tt->rn_flags & RNF_NORMAL) {
                if (m->rm_leaf != tt || m->rm_refs > 0) {
                        log(LOG_ERR, "rn_delete: inconsistent annotation\n");

-                       return 0;  /* dangling ref could cause disaster */
+                       return NULL;  /* dangling ref could cause disaster */

                }
        } else {
                if (m->rm_mask != tt->rn_mask) {
                }
        } else {
                if (m->rm_mask != tt->rn_mask) {


@@ -780,14 +804,15 @@ rn_delete(v_arg, netmask_arg, head)
        if (m == 0) {
                log(LOG_ERR, "rn_delete: couldn't find our annotation\n");
                if (tt->rn_flags & RNF_NORMAL)
        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 */
+                       return (NULL); /* Dangling ref to us */

        }
 on1:
        /*
         * Eliminate us from tree
         */
        if (tt->rn_flags & RNF_ROOT)
        }
 on1:
        /*
         * Eliminate us from tree
         */
        if (tt->rn_flags & RNF_ROOT)

-               return (0);
+               return (NULL);
+       head->rnh_cnt--;

 #ifdef RN_DEBUG
        /* Get us out of the creation list */
        for (t = rn_clist; t && t->rn_ybro != tt; t = t->rn_ybro) {}
 #ifdef RN_DEBUG
        /* Get us out of the creation list */
        for (t = rn_clist; t && t->rn_ybro != tt; t = t->rn_ybro) {}


@@ -863,15 +888,16 @@ on1:
                        for (m = t->rn_mklist; m && x; x = x->rn_dupedkey)
                                if (m == x->rn_mklist) {
                                        struct radix_mask *mm = m->rm_mklist;
                        for (m = t->rn_mklist; m && x; x = x->rn_dupedkey)
                                if (m == x->rn_mklist) {
                                        struct radix_mask *mm = m->rm_mklist;

-                                       x->rn_mklist = 0;
+                                       x->rn_mklist = NULL;

                                        if (--(m->rm_refs) < 0)
                                                MKFree(m);
                                        m = mm;
                                }
                        if (m)
                                        if (--(m->rm_refs) < 0)
                                                MKFree(m);
                                        m = mm;
                                }
                        if (m)

-                               log(LOG_ERR,
-                                   "rn_delete: Orphaned Mask %p at %p\n",
-                                   (void *)m, (void *)x);
+                               log(LOG_ERR, "rn_delete: Orphaned Mask "
+                                   "0x%llx at 0x%llx\n",
+                                   (uint64_t)VM_KERNEL_ADDRPERM(m),
+                                   (uint64_t)VM_KERNEL_ADDRPERM(x));

                }
        }
        /*
                }
        }
        /*


@@ -905,38 +931,47 @@ out:
  * exit.
  */
 static int
  * exit.
  */
 static int

-rn_walktree_from(h, a, m, f, w)
-       struct radix_node_head *h;
-       void *a, *m;
-       walktree_f_t *f;
-       void *w;
+rn_walktree_from(struct radix_node_head *h, void *a, void *m, walktree_f_t *f,
+    void *w)

 {
        int error;
        struct radix_node *base, *next;
        u_char *xa = (u_char *)a;
        u_char *xm = (u_char *)m;
 {
        int error;
        struct radix_node *base, *next;
        u_char *xa = (u_char *)a;
        u_char *xm = (u_char *)m;

-       register struct radix_node *rn, *last = 0 /* shut up gcc */;
-       int stopping = 0;
+       struct radix_node *rn, *last;
+       int stopping;

        int lastb;
        int lastb;

+       int rnh_cnt;
+
+       /*
+        * This gets complicated because we may delete the node while
+        * applying the function f to it; we cannot simply use the next
+        * leaf as the successor node in advance, because that leaf may
+        * be removed as well during deletion when it is a clone of the
+        * current node.  When that happens, we would end up referring
+        * to an already-freed radix node as the successor node.  To get
+        * around this issue, if we detect that the radix tree has changed
+        * in dimension (smaller than before), we simply restart the walk
+        * from the top of tree.
+        */
+restart:
+       last = NULL;
+       stopping = 0;
+       rnh_cnt = h->rnh_cnt;

 
        /*
         * rn_search_m is sort-of-open-coded here.
         */
 
        /*
         * rn_search_m is sort-of-open-coded here.
         */

-       /* printf("about to search\n"); */

        for (rn = h->rnh_treetop; rn->rn_bit >= 0; ) {
                last = rn;
        for (rn = h->rnh_treetop; rn->rn_bit >= 0; ) {
                last = rn;

-               /* printf("rn_bit %d, rn_bmask %x, xm[rn_offset] %x\n",
-                      rn->rn_bit, rn->rn_bmask, xm[rn->rn_offset]); */
-               if (!(rn->rn_bmask & xm[rn->rn_offset])) {
+               if (!(rn->rn_bmask & xm[rn->rn_offset]))

                        break;
                        break;

-               }
-               if (rn->rn_bmask & xa[rn->rn_offset]) {
+
+               if (rn->rn_bmask & xa[rn->rn_offset])

                        rn = rn->rn_right;
                        rn = rn->rn_right;

-               } else {
+               else

                        rn = rn->rn_left;
                        rn = rn->rn_left;

-               }

        }
        }

-       /* printf("done searching\n"); */

 
        /*
         * Two cases: either we stepped off the end of our mask,
 
        /*
         * Two cases: either we stepped off the end of our mask,


@@ -947,18 +982,11 @@ rn_walktree_from(h, a, m, f, w)
        rn = last;
        lastb = rn->rn_bit;
 
        rn = last;
        lastb = rn->rn_bit;
 

-       /* printf("rn %p, lastb %d\n", rn, lastb);*/
-
-       /*
-        * This gets complicated because we may delete the node
-        * while applying the function f to it, so we need to calculate
-        * the successor node in advance.
-        */
+       /* First time through node, go left */

        while (rn->rn_bit >= 0)
                rn = rn->rn_left;
 
        while (!stopping) {
        while (rn->rn_bit >= 0)
                rn = rn->rn_left;
 
        while (!stopping) {

-               /* printf("node %p (%d)\n", rn, rn->rn_bit); */

                base = rn;
                /* If at right child go back up, otherwise, go right */
                while (rn->rn_parent->rn_right == rn
                base = rn;
                /* If at right child go back up, otherwise, go right */
                while (rn->rn_parent->rn_right == rn


@@ -966,81 +994,114 @@ rn_walktree_from(h, a, m, f, w)
                        rn = rn->rn_parent;
 
                        /* if went up beyond last, stop */
                        rn = rn->rn_parent;
 
                        /* if went up beyond last, stop */

-                       if (rn->rn_bit < lastb) {
+                       if (rn->rn_bit <= lastb) {

                                stopping = 1;
                                stopping = 1;

-                               /* printf("up too far\n"); */
+                               /*
+                                * XXX we should jump to the 'Process leaves'
+                                * part, because the values of 'rn' and 'next'
+                                * we compute will not be used. Not a big deal
+                                * because this loop will terminate, but it is
+                                * inefficient and hard to understand!
+                                */

                        }
                }
 
                        }
                }
 

-               /* Find the next *leaf* since next node might vanish, too */
+               /*
+                * The following code (bug fix) inherited from FreeBSD is
+                * currently disabled, because our implementation uses the
+                * RTF_PRCLONING scheme that has been abandoned in current
+                * FreeBSD release.  The scheme involves setting such a flag
+                * for the default route entry, and therefore all off-link
+                * destinations would become clones of that entry.  Enabling
+                * the following code would be problematic at this point,
+                * because the removal of default route would cause only
+                * the left-half of the tree to be traversed, leaving the
+                * right-half untouched.  If there are clones of the entry
+                * that reside in that right-half, they would not be deleted
+                * and would linger around until they expire or explicitly
+                * deleted, which is a very bad thing.
+                *
+                * This code should be uncommented only after we get rid
+                * of the RTF_PRCLONING scheme.
+                */
+#if 0
+               /*
+                * At the top of the tree, no need to traverse the right
+                * half, prevent the traversal of the entire tree in the
+                * case of default route.
+                */
+               if (rn->rn_parent->rn_flags & RNF_ROOT)
+                       stopping = 1;
+#endif
+
+               /* Find the next *leaf* to start from */

                for (rn = rn->rn_parent->rn_right; rn->rn_bit >= 0;)
                        rn = rn->rn_left;
                next = rn;
                /* Process leaves */
                while ((rn = base) != 0) {
                        base = rn->rn_dupedkey;
                for (rn = rn->rn_parent->rn_right; rn->rn_bit >= 0;)
                        rn = rn->rn_left;
                next = rn;
                /* Process leaves */
                while ((rn = base) != 0) {
                        base = rn->rn_dupedkey;

-                       /* printf("leaf %p\n", rn); */

                        if (!(rn->rn_flags & RNF_ROOT)
                            && (error = (*f)(rn, w)))
                                return (error);
                }
                        if (!(rn->rn_flags & RNF_ROOT)
                            && (error = (*f)(rn, w)))
                                return (error);
                }

+               /* If one or more nodes got deleted, restart from top */
+               if (h->rnh_cnt < rnh_cnt)
+                       goto restart;

                rn = next;
                rn = next;

-
-               if (rn->rn_flags & RNF_ROOT) {
-                       /* printf("root, stopping"); */
+               if (rn->rn_flags & RNF_ROOT)

                        stopping = 1;
                        stopping = 1;

-               }
-

        }
        return 0;
 }
 
 static int
        }
        return 0;
 }
 
 static int

-rn_walktree(h, f, w)
-       struct radix_node_head *h;
-       walktree_f_t *f;
-       void *w;
+rn_walktree(struct radix_node_head *h, walktree_f_t *f, void *w)

 {
        int error;
        struct radix_node *base, *next;
 {
        int error;
        struct radix_node *base, *next;

-       register struct radix_node *rn = h->rnh_treetop;
+       struct radix_node *rn;
+       int rnh_cnt;
+

        /*
        /*

-        * This gets complicated because we may delete the node
-        * while applying the function f to it, so we need to calculate
-        * the successor node in advance.
+        * This gets complicated because we may delete the node while
+        * applying the function f to it; we cannot simply use the next
+        * leaf as the successor node in advance, because that leaf may
+        * be removed as well during deletion when it is a clone of the
+        * current node.  When that happens, we would end up referring
+        * to an already-freed radix node as the successor node.  To get
+        * around this issue, if we detect that the radix tree has changed
+        * in dimension (smaller than before), we simply restart the walk
+        * from the top of tree.

         */
         */

+restart:
+       rn = h->rnh_treetop;
+       rnh_cnt = h->rnh_cnt;
+

        /* First time through node, go left */
        /* First time through node, go left */

-       while (rn->rn_bit >= 0) 
-               if (rn)
-                       rn = rn->rn_left;
-               else return(0);
+       while (rn->rn_bit >= 0)
+               rn = rn->rn_left;

        for (;;) {
                base = rn;
                /* If at right child go back up, otherwise, go right */
        for (;;) {
                base = rn;
                /* If at right child go back up, otherwise, go right */

-               while (rn != NULL && rn->rn_parent != NULL && rn->rn_parent->rn_right == rn
-                      && (rn->rn_flags & RNF_ROOT) == 0)
+               while (rn->rn_parent->rn_right == rn &&
+                   (rn->rn_flags & RNF_ROOT) == 0)

                        rn = rn->rn_parent;
                        rn = rn->rn_parent;

-               /* Find the next *leaf* since next node might vanish, too */
-               if (rn == NULL || rn->rn_parent == NULL || rn->rn_parent->rn_right == NULL)
-                       return (0);
-               for (rn = rn->rn_parent->rn_right; rn->rn_bit >= 0;) {
-                       if (rn == NULL || rn->rn_parent == NULL || rn->rn_parent->rn_right == NULL || rn->rn_left == NULL)
-                               return(0);
+               /* Find the next *leaf* to start from */
+               for (rn = rn->rn_parent->rn_right; rn->rn_bit >= 0;)

                        rn = rn->rn_left;
                        rn = rn->rn_left;

-               }

                next = rn;
                /* Process leaves */
                next = rn;
                /* Process leaves */

-               while ((rn = base)) {
-                       if (rn == NULL)
-                               return(0);
+               while ((rn = base) != NULL) {

                        base = rn->rn_dupedkey;
                        if (!(rn->rn_flags & RNF_ROOT)
                            && (error = (*f)(rn, w)))
                                return (error);
                }
                        base = rn->rn_dupedkey;
                        if (!(rn->rn_flags & RNF_ROOT)
                            && (error = (*f)(rn, w)))
                                return (error);
                }

+               /* If one or more nodes got deleted, restart from top */
+               if (h->rnh_cnt < rnh_cnt)
+                       goto restart;

                rn = next;
                rn = next;

-               if (rn == NULL)
-                       return (0);

                if (rn->rn_flags & RNF_ROOT)
                        return (0);
        }
                if (rn->rn_flags & RNF_ROOT)
                        return (0);
        }


@@ -1048,12 +1109,10 @@ rn_walktree(h, f, w)
 }
 
 int
 }
 
 int

-rn_inithead(head, off)
-       void **head;
-       int off;
+rn_inithead(void **head, int off)

 {
 {

-       register struct radix_node_head *rnh;
-       register struct radix_node *t, *tt, *ttt;
+       struct radix_node_head *rnh;
+       struct radix_node *t, *tt, *ttt;

        if (*head)
                return (1);
        R_Malloc(rnh, struct radix_node_head *, sizeof (*rnh));
        if (*head)
                return (1);
        R_Malloc(rnh, struct radix_node_head *, sizeof (*rnh));


@@ -1073,24 +1132,27 @@ rn_inithead(head, off)
        rnh->rnh_addaddr = rn_addroute;
        rnh->rnh_deladdr = rn_delete;
        rnh->rnh_matchaddr = rn_match;
        rnh->rnh_addaddr = rn_addroute;
        rnh->rnh_deladdr = rn_delete;
        rnh->rnh_matchaddr = rn_match;

+       rnh->rnh_matchaddr_args = rn_match_args;

        rnh->rnh_lookup = rn_lookup;
        rnh->rnh_lookup = rn_lookup;

+       rnh->rnh_lookup_args = rn_lookup_args;

        rnh->rnh_walktree = rn_walktree;
        rnh->rnh_walktree_from = rn_walktree_from;
        rnh->rnh_treetop = t;
        rnh->rnh_walktree = rn_walktree;
        rnh->rnh_walktree_from = rn_walktree_from;
        rnh->rnh_treetop = t;

+       rnh->rnh_cnt = 3;

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

-rn_init()
+rn_init(void)

 {
        char *cp, *cplim;
 {
        char *cp, *cplim;

-#ifdef KERNEL

        struct domain *dom;
 
        struct domain *dom;
 

-       for (dom = domains; dom; dom = dom->dom_next)
+       /* lock already held when rn_init is called */
+       TAILQ_FOREACH(dom, &domains, dom_entry) {

                if (dom->dom_maxrtkey > max_keylen)
                        max_keylen = dom->dom_maxrtkey;
                if (dom->dom_maxrtkey > max_keylen)
                        max_keylen = dom->dom_maxrtkey;

-#endif
+       }

        if (max_keylen == 0) {
                log(LOG_ERR,
                    "rn_init: radix functions require max_keylen be set\n");
        if (max_keylen == 0) {
                log(LOG_ERR,
                    "rn_init: radix functions require max_keylen be set\n");