kern/174958: [patch] rnh_walktree_from makes unreasonable assumptions
Keith Sklower
sklower at vangogh.CS.Berkeley.EDU
Fri Jan 4 02:50:01 UTC 2013
The following reply was made to PR kern/174958; it has been noted by GNATS.
From: Keith Sklower <sklower at vangogh.CS.Berkeley.EDU>
To: freebsd-bugs at FreeBSD.org, FreeBSD-gnats-submit at FreeBSD.org
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);
}
More information about the freebsd-bugs
mailing list