kern/174958: [patch] rnh_walktree_from makes unreasonable assumptions
Keith Sklower
sklower at cs.berkeley.edu
Fri Jan 4 02:00:00 UTC 2013
>Number: 174958
>Category: kern
>Synopsis: [patch] rnh_walktree_from makes unreasonable assumptions
>Confidential: no
>Severity: serious
>Priority: low
>Responsible: freebsd-bugs
>State: open
>Quarter:
>Keywords:
>Date-Required:
>Class: change-request
>Submitter-Id: current-users
>Arrival-Date: Fri Jan 04 02:00:00 UTC 2013
>Closed-Date:
>Last-Modified:
>Originator: Keith Sklower
>Release: FreeBSD 9.1-RC2 i386
>Organization:
University of California, Berkeley
>Environment:
System: FreeBSD users.isi.deterlab.net 9.1-RC2 FreeBSD 9.1-RC2 #7: Tue Oct 9 19:14:50 PDT 2012 root at users.isi.deterlab.net:/usr/obj/usr/src/sys/USERS9 i386
any machine, any version of FreeBSD after 2.3
>Description:
The radix tree method rnh_walktree_from (as implemented
by rn_walktree_from in /sys/net/radix.c) assumes that
that at least some nodes in the intended subtree are present
in the tree.
And it will always attempt to visit the entire subtree
even if you want to start in the middle.
If you ask it to walk the tree looking for a subnet which is
not present, it may invoke the supplied function on leaves
which do not meet the criteria.
If you naively supply a value of "0" for the mask (in attempt
to start from the middle) the kernel will crash.
It is low priority because nothing in the source distribution
uses this function anymore. We have a local need for it.
>How-To-Repeat:
Construct a routing tree with the following 4 routes:
128.32.8.0/24
128.32.9.0/24
128.32.8.1 (host)
128.32.8.2 (host)
invoke rn_walktree_from(tree, 128.32.25.0, 255.255.255.0, f, 0)
where f prints the IP address in each leaf visited.
It should not visit *any* nodes; it will at least erroneously visit
the node 128.32.9.0 if the simpler patch I just submitted is adopted,
[I can supply 94 line C program that demonstrates this at user level]
It should only visit 128.32.9.0/24; instead it visits the entire
tree.
>Fix:
--- radix.c 2012-11-28 10:23:37.000000000 -0800
+++ radix.c.rewrite 2013-01-03 17:21:45.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,43 @@
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 (rn->rn_flags & RNF_ROOT) {
- /* printf("root, stopping"); */
- stopping = 1;
- }
-
+ char temp[64], *cp, *cp2 = a, *cp3 = m;
+ size_t length = min(LEN(v_arg), LEN(n_arg));
+ struct subtree_info si;
+
+ if (!m)
+ return rn_waltree_with(h, a, f, w);
+ 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 +1068,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 +1087,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
>Release-Note:
>Audit-Trail:
>Unformatted:
More information about the freebsd-bugs
mailing list