diff options
Diffstat (limited to 'sys/net/radix.c')
-rw-r--r-- | sys/net/radix.c | 239 |
1 files changed, 116 insertions, 123 deletions
diff --git a/sys/net/radix.c b/sys/net/radix.c index 6362bb7..5bf9dff 100644 --- a/sys/net/radix.c +++ b/sys/net/radix.c @@ -156,12 +156,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]) @@ -177,12 +175,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]) && @@ -191,15 +187,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; @@ -207,50 +202,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) { + 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 == 0) - return (0); + 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)); @@ -261,22 +277,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 @@ -314,7 +331,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;) @@ -335,13 +352,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; /* @@ -360,12 +377,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 @@ -387,12 +404,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; @@ -416,44 +430,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; @@ -485,20 +494,19 @@ on1: if (rn_debug) log(LOG_DEBUG, "rn_insert: Coming Out:\n"), traverse(p); #endif - } return (tt); } struct radix_node * rn_addmask_r(void *arg, struct radix_node_head *maskhead, int search, int skip) { - caddr_t netmask = (caddr_t)arg; - register struct radix_node *x; - register caddr_t cp, cplim; - register int b = 0, mlen, j; + 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; - char addmask_key[RADIX_MAX_KEY_LEN]; + unsigned char addmask_key[RADIX_MAX_KEY_LEN]; if ((mlen = LEN(netmask)) > RADIX_MAX_KEY_LEN) mlen = RADIX_MAX_KEY_LEN; @@ -540,20 +548,18 @@ rn_addmask_r(void *arg, struct radix_node_head *maskhead, int search, int 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; @@ -581,29 +587,26 @@ rn_addmask(void *n_arg, int search, int 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 (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; R_Malloc(m, struct radix_mask *, sizeof (struct radix_mask)); - if (m == 0) { + if (m == NULL) { log(LOG_ERR, "Failed to allocate route mask\n"); return (0); } @@ -616,17 +619,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; @@ -754,7 +755,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; @@ -778,29 +779,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; @@ -834,7 +833,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) { @@ -986,17 +985,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; @@ -1089,18 +1085,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 @@ -1145,8 +1138,8 @@ rn_walktree(h, f, w) 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)); |