The following reply was made to PR kern/174958; it has been noted by GNATS.
From: Keith Sklower <[email protected]> To: [email protected], [email protected] Cc: Subject: Re: kern/174958: [patch] rnh_walktree_from makes unreasonable assumptions Date: Thu, 3 Jan 2013 18:34:24 -0800 (PST) Hi, With a fair amount of egg on my face I have to ask to resubmit the patch ... I tried tidying it up a bit to minimize diffs and forgot to recompile and test one last time here is the new patch, and I'll include my test harness after that: --- radix.c 2012-12-21 17:21:51.000000000 -0800 +++ radix.c.rewrite 2013-01-03 18:26:01.000000000 -0800 @@ -466,6 +466,10 @@ if (rn_debug) log(LOG_DEBUG, "rn_insert: Going In:\n"), traverse(p); #endif + if (nodes == 0 ) { + *dupentry = b; + return x; + } t = rn_newpair(v_arg, b, nodes); tt = t->rn_left; if ((cp[p->rn_offset] & p->rn_bmask) == 0) @@ -967,6 +971,37 @@ return (tt); } +struct subtree_info { + walktree_f_t * si_f; + void * si_w; + int si_error; + char * si_maskedkey; + char * si_netmask; + char * si_cplim; +}; + +static int +rn_walksubtree_helper(rn, w) + struct radix_node *rn; + void *w; +{ + struct subtree_info *si = w; + char *cp, *cp2 = (char *)(rn->rn_key), *cp3 = si->si_netmask; + + /* check that we are still in the subtree */ + for (cp = si->si_maskedkey; cp < si->si_cplim; cp++) { + if (*cp != (*cp2++) & (*cp3++)) + return 1; + } + if ((si->si_error = (*(si->si_f))(rn, si->si_w))) + return 2; + return 0; +} + +/* forward declaration needed below */ +static int rn_walktree_with(struct radix_node_head *h, void *a, + walktree_f_t *f, void *w); + /* * This is the same as rn_walktree() except for the parameters and the * exit. @@ -978,115 +1013,44 @@ 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; - int lastb; - - /* - * rn_search_m is sort-of-open-coded here. We cannot use the - * function because we need to keep track of the last node seen. - */ - /* 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])) { - break; - } - if (rn->rn_bmask & xa[rn->rn_offset]) { - rn = rn->rn_right; - } else { - rn = rn->rn_left; - } - } - /* printf("done searching\n"); */ - - /* - * Two cases: either we stepped off the end of our mask, - * in which case last == rn, or we reached a leaf, in which - * case we want to start from the last node we looked at. - * Either way, last is the node we want to start from. - */ - 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. - */ - 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 - && !(rn->rn_flags & RNF_ROOT)) { - rn = rn->rn_parent; - - /* if went up beyond last, stop */ - 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! - */ - } - } - - /* - * 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; - - /* Find the next *leaf* since next node might vanish, too */ - 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); - } - rn = next; + if (!m) + return rn_walktree_with(h, a, f, w); - if (rn->rn_flags & RNF_ROOT) { - /* printf("root, stopping"); */ - stopping = 1; - } + char temp[64], *cp, *cp2 = a, *cp3 = m; + size_t length = min(LEN(a), LEN(m)); + struct subtree_info si; + if (length > sizeof(temp)) { + R_Malloc(si.si_maskedkey, char *, length); + } else { + si.si_maskedkey = temp; } + si.si_f = f; + si.si_w = w; + si.si_netmask = cp3; + si.si_cplim = si.si_maskedkey + length; + + for (cp = si.si_maskedkey; cp < si.si_cplim; cp++) + { *cp = *cp2++ & *cp3++; } + + int return_code = rn_walktree_with + (h, si.si_maskedkey, rn_walksubtree_helper, &si); + if (length > sizeof(temp)) + Free(si.si_maskedkey); + if (return_code == 2) + return si.si_error; return 0; } static int -rn_walktree(h, f, w) - struct radix_node_head *h; +rn_walktree1(rn, skipfirst, f, w) + struct radix_node *rn; + int skipfirst; walktree_f_t *f; void *w; { int error; struct radix_node *base, *next; - register 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 @@ -1105,6 +1069,10 @@ /* Find the next *leaf* since next node might vanish, too */ for (rn = rn->rn_parent->rn_right; rn->rn_bit >= 0;) rn = rn->rn_left; + if (skipfirst) { + skipfirst = 0; + continue; + } next = rn; /* Process leaves */ while ((rn = base)) { @@ -1120,6 +1088,42 @@ /* NOTREACHED */ } +static int +rn_walktree(h, f, w) + struct radix_node_head *h; + walktree_f_t *f; + void *w; +{ + return rn_walktree1(h->rnh_treetop, 0, f, w); +} + +/* + * Walk the tree starting with or after v, (without masking). + */ +static int +rn_walktree_with(h, v_arg, f, w) + struct radix_node_head *h; + void *v_arg; + walktree_f_t *f; + void *w; +{ + int b, skipfirst = 0; + caddr_t v = v_arg; + struct radix_node *x = rn_insert(v_arg, h, &b, (struct radix_node *)0); + if (b != 1) { + /* our value matches every child of x up to, but !including b */ + if (v[b >> 3] & (0x80 >> ( b & 7 )) ) { + /* value will be > so start *after* rightmost child */ + skipfirst = 1; + while (x->rn_bit > 0) { x = x->rn_right; } + } else { + /* value < any child so start with leftmost child */ + while (x->rn_bit > 0) { x = x->rn_left; } + } + } /* b == 1 means exact match so we start with it */ + return rn_walktree1(x, skipfirst, f, w); +} + /* * Allocate and initialize an empty tree. This has 3 nodes, which are * part of the radix_node_head (in the order <left,root,right>) and are <end of patch> <test harness follows> #include <sys/types.h> #include <sys/socket.h> #include <netinet/in.h> #include <arpa/inet.h> #include <stdio.h> #include <strings.h> #define KASSERT(cond, list) { if (cond) printf list ; } #include "radix.c" #include <net/ethernet.h> #include <errno.h> struct radix_node_head *rnh; struct testdata { char *addr; char *mask; u_short vd_vlan; } samples[] = { { "128.32.9.0", "255.255.255.0" }, { "128.32.8.0", "255.255.255.0" }, { "128.32.8.1", 0 }, { "128.32.8.3", 0 }, { 0, 0 } }; struct treedata { struct radix_node tree_glue[2]; struct sockaddr_in tree_addr; struct sockaddr_in tree_mask; }; void debauch(char *addr, struct sockaddr_in *sin) /* lead into sin */ { /* bzero(sin, sizeof(*sin)); pedantically, already zeroed */ sin->sin_len = sizeof (*sin); sin->sin_family = AF_INET; (void) inet_aton(addr, &sin->sin_addr); } void install(struct testdata *td) { struct sockaddr_in *mask_p = 0; struct treedata *tr; R_Zalloc(tr, struct treedata *, sizeof(*tr)); debauch(td->addr, &tr->tree_addr); if (td->mask) { debauch(td->mask, &tr->tree_mask); mask_p = &tr->tree_mask; } (void) rnh->rnh_addaddr(&(tr->tree_addr), mask_p, rnh, tr->tree_glue); } int p_helper(struct radix_node *rn, void *v) { struct treedata *tr = (struct treedata *)rn; printf("addr %s\n", inet_ntoa(tr->tree_addr.sin_addr)); return (0); } struct sockaddr_in sample_mask, inthetree, notintree, middle; #ifndef offsetof #define offsetof(type, member) ((size_t)(&((type *)0)->member)) #endif main() { rn_init(sizeof sample_mask); rn_inithead((void **)&rnh, 8 * offsetof(struct sockaddr_in, sin_addr)); debauch("255.255.255.0", &sample_mask); debauch("128.32.9.0", &inthetree); debauch("128.32.25.0", ¬intree); debauch("128.32.8.2", &middle); struct testdata *td; for (td = samples; td->addr; td++) install(td); printf("inthetree case\n"); rnh->rnh_walktree_from(rnh, &inthetree, &sample_mask, p_helper, 0); printf("notintree case\n"); rnh->rnh_walktree_from(rnh, ¬intree, &sample_mask, p_helper, 0); printf("new middle case\n"); rnh->rnh_walktree_from(rnh, &middle, 0, p_helper, 0); /* printf("walksubtree does\n"); rn_walksubtree(rnh, &inthetree, &sample_mask, p_helper, 0); printf("walksubtree does\n"); rn_walksubtree(rnh, ¬intree, &sample_mask, p_helper, 0); */ exit(0); } _______________________________________________ [email protected] mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-bugs To unsubscribe, send any mail to "[email protected]"
