diff options
Diffstat (limited to 'freebsd/sys/net/radix.c')
-rw-r--r-- | freebsd/sys/net/radix.c | 415 |
1 files changed, 226 insertions, 189 deletions
diff --git a/freebsd/sys/net/radix.c b/freebsd/sys/net/radix.c index 875a482c..ba15eb51 100644 --- a/freebsd/sys/net/radix.c +++ b/freebsd/sys/net/radix.c @@ -68,27 +68,27 @@ static struct radix_node *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 struct radix_node_head *mask_rnhead; +static void rn_detachhead_internal(void **head); +static int rn_inithead_internal(void **head, int off); + +#define RADIX_MAX_KEY_LEN 32 + +static char rn_zeros[RADIX_MAX_KEY_LEN]; +static char rn_ones[RADIX_MAX_KEY_LEN] = { + -1, -1, -1, -1, -1, -1, -1, -1, + -1, -1, -1, -1, -1, -1, -1, -1, + -1, -1, -1, -1, -1, -1, -1, -1, + -1, -1, -1, -1, -1, -1, -1, -1, +}; + /* - * Work area -- the following point to 3 buffers of size max_keylen, - * allocated in this order in a block of memory malloc'ed by rn_init. - * rn_zeros, rn_ones are set in rn_init and used in readonly afterwards. - * addmask_key is used in rn_addmask in rw mode and not thread-safe. + * XXX: Compat stuff for old rn_addmask() users */ -static char *rn_zeros, *rn_ones, *addmask_key; - -#define MKGet(m) { \ - if (rn_mkfreelist) { \ - m = rn_mkfreelist; \ - rn_mkfreelist = (m)->rm_mklist; \ - } else \ - R_Malloc(m, struct radix_mask *, sizeof (struct radix_mask)); } - -#define MKFree(m) { (m)->rm_mklist = rn_mkfreelist; rn_mkfreelist = (m);} +static struct radix_node_head *mask_rnhead_compat; +#ifdef _KERNEL +static struct mtx mask_mtx; +#endif -#define rn_masktop (mask_rnhead->rnh_treetop) static int rn_lexobetter(void *m_arg, void *n_arg); static struct radix_mask * @@ -158,12 +158,10 @@ static int rn_satisfies_leaf(char *trial, struct radix_node *leaf, * Search a node in the tree matching the key. */ 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]) @@ -179,12 +177,10 @@ rn_search(v_arg, head) * XXX note this function is used only once. */ 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]) && @@ -193,15 +189,14 @@ rn_search_m(v_arg, head, m_arg) else x = x->rn_left; } - return x; + return (x); } 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 + LEN(n); + caddr_t m = m_arg, n = n_arg; + caddr_t lim, lim2 = lim = n + LEN(n); int longer = LEN(n++) - LEN(m++); int masks_are_equal = 1; @@ -209,49 +204,71 @@ rn_refines(m_arg, n_arg) lim -= longer; while (n < lim) { if (*n & ~(*m)) - return 0; + return (0); if (*n++ != *m++) masks_are_equal = 0; } while (n < lim2) if (*n++) - return 0; + return (0); if (masks_are_equal && (longer < 0)) for (lim2 = m - longer; m < lim2; ) if (*m++) - return 1; + return (1); return (!masks_are_equal); } +/* + * Search for exact match in given @head. + * Assume host bits are cleared in @v_arg if @m_arg is not NULL + * Note that prefixes with /32 or /128 masks are treated differently + * from host routes. + */ 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; + struct radix_node *x; + caddr_t netmask; - if (m_arg) { - x = rn_addmask(m_arg, 1, head->rnh_treetop->rn_offset); - if (x == 0) - return (0); + if (m_arg != NULL) { + /* + * Most common case: search exact prefix/mask + */ + x = rn_addmask_r(m_arg, head->rnh_masks, 1, + head->rnh_treetop->rn_offset); + if (x == NULL) + return (NULL); netmask = x->rn_key; - } - x = rn_match(v_arg, head); - if (x && netmask) { - while (x && x->rn_mask != netmask) + + x = rn_match(v_arg, head); + + while (x != NULL && x->rn_mask != netmask) x = x->rn_dupedkey; + + return (x); } - return x; + + /* + * Search for host address. + */ + if ((x = rn_match(v_arg, head)) == NULL) + return (NULL); + + /* Check if found key is the same */ + if (LEN(x->rn_key) != LEN(v_arg) || bcmp(x->rn_key, v_arg, LEN(v_arg))) + return (NULL); + + /* Check if this is not host route */ + if (x->rn_mask != NULL) + return (NULL); + + return (x); } static int -rn_satisfies_leaf(trial, leaf, skip) - char *trial; - register struct radix_node *leaf; - int skip; +rn_satisfies_leaf(char *trial, struct radix_node *leaf, int skip) { - 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(LEN(cp), LEN(cp2)); @@ -262,22 +279,23 @@ rn_satisfies_leaf(trial, leaf, skip) cplim = cp + length; cp3 += skip; cp2 += skip; for (cp += skip; cp < cplim; cp++, cp2++, cp3++) if ((*cp ^ *cp2) & *cp3) - return 0; - return 1; + return (0); + return (1); } +/* + * Search for longest-prefix match in given @head + */ 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) { 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 = LEN(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 @@ -315,7 +333,7 @@ rn_match(v_arg, head) */ if (t->rn_flags & RNF_ROOT) t = t->rn_dupedkey; - return t; + return (t); on1: test = (*cp ^ *cp2) & 0xff; /* find first bit that differs */ for (b = 7; (test >>= 1) > 0;) @@ -336,13 +354,13 @@ on1: */ if (t->rn_flags & RNF_NORMAL) { if (rn_bit <= t->rn_bit) - return t; + return (t); } else if (rn_satisfies_leaf(v, t, matched_off)) - return t; + 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; /* @@ -361,12 +379,12 @@ on1: while (x && x->rn_mask != m->rm_mask) x = x->rn_dupedkey; if (x && rn_satisfies_leaf(v, x, off)) - return x; + return (x); } m = m->rm_mklist; } } while (t != top); - return 0; + return (0); } #ifdef RN_DEBUG @@ -388,12 +406,9 @@ int rn_debug = 1; */ 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; @@ -417,44 +432,39 @@ rn_newpair(v, b, nodes) tt->rn_ybro = rn_clist; rn_clist = tt; #endif - return t; + return (t); } 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 = LEN(v); - register struct radix_node *t = rn_search(v_arg, top); - register caddr_t cp = v + head_off; - register int b; - struct radix_node *tt; + struct radix_node *t = rn_search(v_arg, top); + caddr_t cp = v + head_off; + int b; + struct radix_node *p, *tt, *x; /* * 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) if (*cp2++ != *cp++) goto on1; *dupentry = 1; - return t; + return (t); on1: *dupentry = 0; cmp_res = (cp[-1] ^ cp2[-1]) & 0xff; for (b = (cp - v) << 3; cmp_res; b--) cmp_res >>= 1; - } - { - register struct radix_node *p, *x = top; + + x = top; cp = v; do { p = x; @@ -486,58 +496,51 @@ on1: if (rn_debug) log(LOG_DEBUG, "rn_insert: Coming Out:\n"), traverse(p); #endif - } return (tt); } struct radix_node * -rn_addmask(n_arg, search, skip) - int search, skip; - void *n_arg; +rn_addmask_r(void *arg, struct radix_node_head *maskhead, 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; - int maskduplicated, m0, isnormal; + unsigned char *netmask = arg; + unsigned char *cp, *cplim; + struct radix_node *x; + int b = 0, mlen, j; + int maskduplicated, isnormal; struct radix_node *saved_x; - static int last_zeroed = 0; + unsigned char addmask_key[RADIX_MAX_KEY_LEN]; - if ((mlen = LEN(netmask)) > max_keylen) - mlen = max_keylen; + if ((mlen = LEN(netmask)) > RADIX_MAX_KEY_LEN) + mlen = RADIX_MAX_KEY_LEN; if (skip == 0) skip = 1; if (mlen <= skip) - return (mask_rnhead->rnh_nodes); + return (maskhead->rnh_nodes); + + bzero(addmask_key, RADIX_MAX_KEY_LEN); if (skip > 1) bcopy(rn_ones + 1, addmask_key + 1, skip - 1); - if ((m0 = mlen) > skip) - bcopy(netmask + skip, addmask_key + skip, mlen - skip); + bcopy(netmask + skip, addmask_key + skip, mlen - skip); /* * Trim trailing zeroes. */ for (cp = addmask_key + mlen; (cp > addmask_key) && cp[-1] == 0;) cp--; mlen = cp - addmask_key; - if (mlen <= skip) { - if (m0 >= last_zeroed) - last_zeroed = mlen; - return (mask_rnhead->rnh_nodes); - } - if (m0 < last_zeroed) - bzero(addmask_key + m0, last_zeroed - m0); - *addmask_key = last_zeroed = mlen; - x = rn_search(addmask_key, rn_masktop); + if (mlen <= skip) + return (maskhead->rnh_nodes); + *addmask_key = mlen; + x = rn_search(addmask_key, maskhead->rnh_treetop); if (bcmp(addmask_key, x->rn_key, mlen) != 0) x = 0; if (x || search) return (x); - R_Zalloc(x, struct radix_node *, max_keylen + 2 * sizeof (*x)); + R_Zalloc(x, struct radix_node *, RADIX_MAX_KEY_LEN + 2 * sizeof (*x)); if ((saved_x = x) == 0) return (0); netmask = cp = (caddr_t)(x + 2); bcopy(addmask_key, cp, mlen); - x = rn_insert(cp, mask_rnhead, &maskduplicated, x); + x = rn_insert(cp, maskhead, &maskduplicated, x); if (maskduplicated) { log(LOG_ERR, "rn_addmask: mask impossibly already in tree"); Free(saved_x); @@ -547,20 +550,18 @@ rn_addmask(n_arg, search, skip) * Calculate index of mask, and check for normalcy. * First find the first byte with a 0 bit, then if there are * more bits left (remember we already trimmed the trailing 0's), - * the pattern must be one of those in normal_chars[], or we have + * the bits should be contiguous, otherwise we have got * a non-contiguous mask. */ +#define CONTIG(_c) (((~(_c) + 1) & (_c)) == (unsigned char)(~(_c) + 1)) cplim = netmask + mlen; isnormal = 1; for (cp = netmask + skip; (cp < cplim) && *(u_char *)cp == 0xff;) cp++; if (cp != cplim) { - static char normal_chars[] = { - 0, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, 0xff}; - for (j = 0x80; (j & *cp) != 0; j >>= 1) b++; - if (*cp != normal_chars[b] || cp != (cplim - 1)) + if (!CONTIG(*cp) || cp != (cplim - 1)) isnormal = 0; } b += (cp - netmask) << 3; @@ -570,34 +571,48 @@ rn_addmask(n_arg, search, skip) return (x); } +struct radix_node * +rn_addmask(void *n_arg, int search, int skip) +{ + struct radix_node *tt; + +#ifdef _KERNEL + mtx_lock(&mask_mtx); +#endif + tt = rn_addmask_r(&mask_rnhead_compat, n_arg, search, skip); + +#ifdef _KERNEL + mtx_unlock(&mask_mtx); +#endif + + return (tt); +} + 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 (LEN(mp) > LEN(np)) - return 1; /* not really, but need to check longer one first */ + return (1); /* not really, but need to check longer one first */ if (LEN(mp) == LEN(np)) for (lim = mp + LEN(mp); mp < lim;) if (*mp++ > *np++) - return 1; - return 0; + return (1); + return (0); } 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"); + R_Malloc(m, struct radix_mask *, sizeof (struct radix_mask)); + if (m == NULL) { + log(LOG_ERR, "Failed to allocate route mask\n"); return (0); } - bzero(m, sizeof *m); + bzero(m, sizeof(*m)); m->rm_bit = tt->rn_bit; m->rm_flags = tt->rn_flags; if (tt->rn_flags & RNF_NORMAL) @@ -606,17 +621,15 @@ rn_new_radix_mask(tt, next) m->rm_mask = tt->rn_mask; m->rm_mklist = next; tt->rn_mklist = m; - return m; + return (m); } 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 = 0, *tt; struct radix_node *saved_tt, *top = head->rnh_treetop; short b = 0, b_leaf = 0; int keyduplicated; @@ -631,7 +644,8 @@ rn_addroute(v_arg, n_arg, head, treenodes) * nodes and possibly save time in calculating indices. */ if (netmask) { - if ((x = rn_addmask(netmask, 0, top->rn_offset)) == 0) + x = rn_addmask_r(netmask, head->rnh_masks, 0, top->rn_offset); + if (x == NULL) return (0); b_leaf = x->rn_bit; b = -1 - x->rn_bit; @@ -743,7 +757,7 @@ rn_addroute(v_arg, n_arg, head, treenodes) on2: /* Add new route to highest possible ancestor's list */ if ((netmask == 0) || (b > t->rn_bit )) - return tt; /* can't lift at all */ + return (tt); /* can't lift at all */ b_leaf = tt->rn_bit; do { x = t; @@ -767,29 +781,27 @@ on2: log(LOG_ERR, "Non-unique normal route, mask not entered\n"); #endif - return tt; + return (tt); } } else mmask = m->rm_mask; if (mmask == netmask) { m->rm_refs++; tt->rn_mklist = m; - return tt; + return (tt); } if (rn_refines(netmask, mmask) || rn_lexobetter(netmask, mmask)) break; } *mp = rn_new_radix_mask(tt, *mp); - return tt; + return (tt); } 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; @@ -810,7 +822,8 @@ rn_delete(v_arg, netmask_arg, head) * Delete our route from mask lists. */ if (netmask) { - if ((x = rn_addmask(netmask, 1, head_off)) == 0) + x = rn_addmask_r(netmask, head->rnh_masks, 1, head_off); + if (x == NULL) return (0); netmask = x->rn_key; while (tt->rn_mask != netmask) @@ -822,7 +835,7 @@ rn_delete(v_arg, netmask_arg, head) 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 (0); /* dangling ref could cause disaster */ } } else { if (m->rm_mask != tt->rn_mask) { @@ -843,7 +856,7 @@ rn_delete(v_arg, netmask_arg, head) for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist) if (m == saved_m) { *mp = m->rm_mklist; - MKFree(m); + Free(m); break; } if (m == 0) { @@ -934,7 +947,7 @@ on1: struct radix_mask *mm = m->rm_mklist; x->rn_mklist = 0; if (--(m->rm_refs) < 0) - MKFree(m); + Free(m); m = mm; } if (m) @@ -974,17 +987,14 @@ 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 */; + struct radix_node *rn, *last = NULL; /* shut up gcc */ int stopping = 0; int lastb; @@ -1077,18 +1087,15 @@ rn_walktree_from(h, a, m, f, w) } } - return 0; + 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 = h->rnh_treetop; /* * This gets complicated because we may delete the node * while applying the function f to it, so we need to calculate @@ -1130,13 +1137,11 @@ rn_walktree(h, f, w) * bits starting at 'off'. * Return 1 on success, 0 on error. */ -int -rn_inithead(head, off) - void **head; - int off; +static int +rn_inithead_internal(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_Zalloc(rnh, struct radix_node_head *, sizeof (*rnh)); @@ -1165,8 +1170,8 @@ rn_inithead(head, off) return (1); } -int -rn_detachhead(void **head) +static void +rn_detachhead_internal(void **head) { struct radix_node_head *rnh; @@ -1178,28 +1183,60 @@ rn_detachhead(void **head) Free(rnh); *head = NULL; +} + +int +rn_inithead(void **head, int off) +{ + struct radix_node_head *rnh; + + if (*head != NULL) + return (1); + + if (rn_inithead_internal(head, off) == 0) + return (0); + + rnh = (struct radix_node_head *)(*head); + + if (rn_inithead_internal((void **)&rnh->rnh_masks, 0) == 0) { + rn_detachhead_internal(head); + return (0); + } + + return (1); +} + +int +rn_detachhead(void **head) +{ + struct radix_node_head *rnh; + + KASSERT((head != NULL && *head != NULL), + ("%s: head already freed", __func__)); + + rnh = *head; + + rn_detachhead_internal((void **)&rnh->rnh_masks); + rn_detachhead_internal(head); return (1); } void rn_init(int maxk) { - char *cp, *cplim; - - max_keylen = maxk; - if (max_keylen == 0) { + if ((maxk <= 0) || (maxk > RADIX_MAX_KEY_LEN)) { log(LOG_ERR, - "rn_init: radix functions require max_keylen be set\n"); + "rn_init: max_keylen must be within 1..%d\n", + RADIX_MAX_KEY_LEN); return; } - R_Malloc(rn_zeros, char *, 3 * max_keylen); - if (rn_zeros == NULL) - panic("rn_init"); - bzero(rn_zeros, 3 * max_keylen); - rn_ones = cp = rn_zeros + max_keylen; - addmask_key = cplim = rn_ones + max_keylen; - while (cp < cplim) - *cp++ = -1; - if (rn_inithead((void **)(void *)&mask_rnhead, 0) == 0) + + /* + * XXX: Compat for old rn_addmask() users + */ + if (rn_inithead((void **)(void *)&mask_rnhead_compat, 0) == 0) panic("rn_init 2"); +#ifdef _KERNEL + mtx_init(&mask_mtx, "radix_mask", NULL, MTX_DEF); +#endif } |