X-Git-Url: https://git.saurik.com/apple/xnu.git/blobdiff_plain/43866e378188c25dd1e2208016ab3cbeb086ae6c..39236c6e673c41db228275375ab7fdb0f837b292:/bsd/net/radix.c?ds=sidebyside diff --git a/bsd/net/radix.c b/bsd/net/radix.c index 1fb667e17..fdc7058b3 100644 --- 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 - * 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, @@ -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. - * - * @APPLE_LICENSE_HEADER_END@ + * + * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ */ /* * Copyright (c) 1988, 1989, 1993 @@ -63,27 +66,26 @@ */ #ifndef _RADIX_H_ #include -#ifdef KERNEL #include #include #define M_DONTWAIT M_NOWAIT #include -#else -#include -#endif #include #include +#include +#include +#include #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 - *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; @@ -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; + +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) \ - (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 * - 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 @@ -139,12 +147,10 @@ static int rn_satsifies_leaf __P((char *trial, struct radix_node *leaf, */ 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]) @@ -156,12 +162,10 @@ rn_search(v_arg, head) } 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]) && @@ -174,11 +178,10 @@ rn_search_m(v_arg, head, m_arg) } 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; @@ -201,20 +204,25 @@ rn_refines(m_arg, n_arg) } 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) - return (0); + return (NULL); 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; @@ -222,13 +230,18 @@ rn_lookup(v_arg, m_arg, head) 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 -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); @@ -240,21 +253,27 @@ rn_satsifies_leaf(trial, leaf, skip) 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 * -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; - 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; - register int test, b, rn_bit; + int test, b, rn_bit; /* * 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; - 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--; +keeplooking: 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; - 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) { - 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 { - register struct radix_mask *m; + struct radix_mask *m; t = t->rn_parent; m = t->rn_mklist; /* @@ -330,20 +366,21 @@ on1: */ 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; - 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); - return 0; + return (NULL); } #ifdef RN_DEBUG @@ -354,12 +391,9 @@ int rn_debug = 1; #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; @@ -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_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; @@ -379,25 +413,22 @@ rn_newpair(v, b, nodes) } 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); - 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 */ { - 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) @@ -412,7 +443,7 @@ on1: cmp_res >>= 1; } { - register struct radix_node *p, *x = top; + struct radix_node *p, *x = top; cp = v; do { p = x; @@ -449,14 +480,12 @@ on1: } 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; - 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; @@ -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) - 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) - 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"); - Free(saved_x); + R_Free(saved_x); return (x); } + mask_rnhead->rnh_cnt++; /* * 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 */ -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 */ @@ -537,16 +566,14 @@ rn_lexobetter(m_arg, n_arg) } 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"); - return (0); + return (NULL); } Bzero(m, sizeof *m); m->rm_bit = tt->rn_bit; @@ -561,13 +588,11 @@ rn_new_radix_mask(tt, next) } 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; - 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; @@ -583,7 +608,7 @@ rn_addroute(v_arg, n_arg, head, treenodes) */ 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; @@ -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) - return (0); + return (NULL); 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; } + head->rnh_cnt++; /* * 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) { - *mp = m = rn_new_radix_mask(x, 0); + *mp = m = rn_new_radix_mask(x, NULL); 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; - t->rn_mklist = m; *mp = 0; + t->rn_mklist = m; *mp = NULL; } on2: /* Add new route to highest possible ancestor's list */ @@ -716,11 +742,9 @@ on2: } 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; @@ -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)) - return (0); + return (NULL); /* * 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) - 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"); - return 0; /* dangling ref could cause disaster */ + return NULL; /* dangling ref could cause disaster */ } } 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) - return (0); /* Dangling ref to us */ + return (NULL); /* Dangling ref to us */ } 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) {} @@ -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; - x->rn_mklist = 0; + x->rn_mklist = NULL; 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 -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; - register struct radix_node *rn, *last = 0 /* shut up gcc */; - int stopping = 0; + struct radix_node *rn, *last; + int stopping; 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. */ - /* printf("about to search\n"); */ 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; - } - if (rn->rn_bmask & xa[rn->rn_offset]) { + + if (rn->rn_bmask & xa[rn->rn_offset]) rn = rn->rn_right; - } else { + else rn = rn->rn_left; - } } - /* printf("done searching\n"); */ /* * 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; - /* 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) { - /* 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 @@ -966,81 +994,114 @@ rn_walktree_from(h, a, m, f, w) rn = rn->rn_parent; /* if went up beyond last, stop */ - if (rn->rn_bit < lastb) { + if (rn->rn_bit <= lastb) { 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; - /* printf("leaf %p\n", rn); */ 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; - - if (rn->rn_flags & RNF_ROOT) { - /* printf("root, stopping"); */ + if (rn->rn_flags & RNF_ROOT) stopping = 1; - } - } 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; - 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 */ - 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 */ - 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; - /* 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; - } 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); } + /* If one or more nodes got deleted, restart from top */ + if (h->rnh_cnt < rnh_cnt) + goto restart; rn = next; - if (rn == NULL) - return (0); if (rn->rn_flags & RNF_ROOT) return (0); } @@ -1048,12 +1109,10 @@ rn_walktree(h, f, w) } 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)); @@ -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_matchaddr_args = rn_match_args; 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_cnt = 3; return (1); } void -rn_init() +rn_init(void) { char *cp, *cplim; -#ifdef KERNEL 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; -#endif + } if (max_keylen == 0) { log(LOG_ERR, "rn_init: radix functions require max_keylen be set\n");