kern/174959: [patch] rnh_walktree_from visits spurious nodes

[Keith Sklower]

>Number:         174959
>Category:       kern
>Synopsis:       [patch] rnh_walktree_from visits spurious nodes
>Confidential:   no
>Severity:       serious
>Priority:       low
>Responsible:    freebsd-bugs
>State:          open
>Quarter:        
>Keywords:       
>Date-Required:
>Class:          sw-bug
>Submitter-Id:   current-users
>Arrival-Date:   Fri Jan 04 02:10: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) invokes the helper
	function f on nodes that it should not, even when supplied with
	inputs adhering to its unreasonably strict assumptions.

	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.9.0, 255.255.255.0, f, 0)
	where f prints the IP address in each leaf visited.

	[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.pfix	2013-01-03 16:12:33.000000000 -0800
@@ -1009,11 +1009,11 @@
 	/*
 	 * 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.
+	 * case we want to start from the leaf.
 	 */
-	rn = last;
-	lastb = rn->rn_bit;
+	 if (rn-> rn_bit >= 0)
+	    rn = last;
+	lastb = last->rn_bit;
 
 	/* printf("rn %p, lastb %d\n", rn, lastb);*/
 
>Release-Note:
>Audit-Trail:
>Unformatted: