Bug 174958

Summary: [net] [patch] rnh_walktree_from makes unreasonable assumptions
Product: Base System Reporter: Keith Sklower <sklower>
Component: kernAssignee: freebsd-bugs (Nobody) <bugs>
Status: Open ---    
Severity: Affects Only Me CC: deter-ops
Priority: Normal Keywords: patch
Version: Unspecified   
Hardware: Any   
OS: Any   
Attachments:
Description Flags
file.diff none

Description Keith Sklower 2013-01-04 02:00:00 UTC
	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.
Comment 1 sklower 2013-01-04 02:34:24 UTC
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", &notintree);
    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, &notintree, &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, &notintree, &sample_mask, p_helper, 0);
*/
    exit(0);
}
Comment 2 Mark Linimon freebsd_committer freebsd_triage 2013-01-20 01:53:40 UTC
Responsible Changed
From-To: freebsd-bugs->freebsd-net

Over to maintainer(s).
Comment 3 Alexander V. Chernikov freebsd_committer freebsd_triage 2014-05-01 16:18:41 UTC
Hello!
Better late than never.

I'm a bit unsure how patch&test case in this PR relates to kern/174959.

Problems described here are the same as in 174959, however it looks like 
given patch
addresses some other problem. It does not touch problem function at all, 
but introduces a bunch
of new ones not used in test case.

Can you please provide some more details?
Comment 4 sklower 2014-05-10 01:38:53 UTC
Hi,

I had many, many exchanges of email with Marko Zec concerning this
issue; please keep it open.

We're both agreed there is a problem, and we came up with a patch
that he's OK with, but we didn't reach full agreement on some other
issues which have implications for locking, which have subsequently
addressed by somebody else.

I would like to come up with a patch for FreeBSD 10 and revive the
discussion, but I'm busy for the next couple of weeks.

(and also a test harness which demonstrates casses where the distributed
code fails, which can be run at user level).

Keith

> Date: Thu, 01 May 2014 19:18:41 +0400
> From: "Alexander V. Chernikov" <melifaro@FreeBSD.org>
> Subject: Re: kern/174958: [net] [patch] rnh_walktree_from makes unreasonable
>  assumptions

> Hello!
> Better late than never.

> I'm a bit unsure how patch&test case in this PR relates to kern/174959.

> Problems described here are the same as in 174959, however it looks like 
> given patch
> addresses some other problem. It does not touch problem function at all, 
> but introduces a bunch
> of new ones not used in test case.

> Can you please provide some more details?
Comment 5 Eitan Adler freebsd_committer freebsd_triage 2017-12-31 08:00:33 UTC
For bugs matching the following criteria:

Status: In Progress Changed: (is less than) 2014-06-01

Reset to default assignee and clear in-progress tags.

Mail being skipped
Comment 6 Graham Perrin freebsd_committer freebsd_triage 2022-10-17 12:34:40 UTC
Keyword: 

    patch
or  patch-ready

– in lieu of summary line prefix: 

    [patch]

* bulk change for the keyword
* summary lines may be edited manually (not in bulk). 

Keyword descriptions and search interface: 

    <https://bugs.freebsd.org/bugzilla/describekeywords.cgi>