From owner-freebsd-bugs@FreeBSD.ORG Fri Jan 4 02:00:00 2013 Return-Path: Delivered-To: freebsd-bugs@smarthost.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.FreeBSD.org [8.8.178.115]) by hub.freebsd.org (Postfix) with ESMTP id E053DE19 for ; Fri, 4 Jan 2013 02:00:00 +0000 (UTC) (envelope-from gnats@FreeBSD.org) Received: from freefall.freebsd.org (freefall.freebsd.org [IPv6:2001:1900:2254:206c::16:87]) by mx1.freebsd.org (Postfix) with ESMTP id C55AA2B3 for ; Fri, 4 Jan 2013 02:00:00 +0000 (UTC) Received: from freefall.freebsd.org (localhost [127.0.0.1]) by freefall.freebsd.org (8.14.5/8.14.5) with ESMTP id r04200R2091086 for ; Fri, 4 Jan 2013 02:00:00 GMT (envelope-from gnats@freefall.freebsd.org) Received: (from gnats@localhost) by freefall.freebsd.org (8.14.5/8.14.5/Submit) id r04200H7091085; Fri, 4 Jan 2013 02:00:00 GMT (envelope-from gnats) Resent-Date: Fri, 4 Jan 2013 02:00:00 GMT Resent-Message-Id: <201301040200.r04200H7091085@freefall.freebsd.org> Resent-From: FreeBSD-gnats-submit@FreeBSD.org (GNATS Filer) Resent-To: freebsd-bugs@FreeBSD.org Resent-Reply-To: FreeBSD-gnats-submit@FreeBSD.org, Keith Sklower Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) by hub.freebsd.org (Postfix) with ESMTP id 57F0FE09 for ; Fri, 4 Jan 2013 01:58:31 +0000 (UTC) (envelope-from sklower@isi.deterlab.net) Received: from users.isi.deterlab.net (users.isi.deterlab.net [206.117.25.49]) by mx1.freebsd.org (Postfix) with ESMTP id 2AF7A2AA for ; Fri, 4 Jan 2013 01:58:30 +0000 (UTC) Received: from users.isi.deterlab.net (localhost.isi.deterlab.net [127.0.0.1]) by users.isi.deterlab.net (8.14.5/8.14.4) with ESMTP id r041wUn3005680; Thu, 3 Jan 2013 17:58:30 -0800 (PST) (envelope-from sklower@users.isi.deterlab.net) Received: (from sklower@localhost) by users.isi.deterlab.net (8.14.5/8.13.8/Submit) id r041wUYX005679; Thu, 3 Jan 2013 17:58:30 -0800 (PST) (envelope-from sklower) Message-Id: <201301040158.r041wUYX005679@users.isi.deterlab.net> Date: Thu, 3 Jan 2013 17:58:30 -0800 (PST) From: Keith Sklower To: FreeBSD-gnats-submit@FreeBSD.org X-Send-Pr-Version: 3.113 Subject: kern/174958: [patch] rnh_walktree_from makes unreasonable assumptions Cc: deter-ops@isi.edu X-BeenThere: freebsd-bugs@freebsd.org X-Mailman-Version: 2.1.14 Precedence: list Reply-To: Keith Sklower List-Id: Bug reports List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 04 Jan 2013 02:00:00 -0000 >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@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 ) and are >Release-Note: >Audit-Trail: >Unformatted: