Summary:  [net] [patch] rnh_walktree_from makes unreasonable assumptions  

Product:  Base System  Reporter:  Keith Sklower <sklower>  
Component:  kern  Assignee:  freebsdbugs (Nobody) <bugs>  
Status:  Open   
Severity:  Affects Only Me  CC:  deterops  
Priority:  Normal  
Version:  Unspecified  
Hardware:  Any  
OS:  Any  
Attachments: 

Description
Keith Sklower
20130104 02:00:00 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 20121221 17:21:51.000000000 0800 +++ radix.c.rewrite 20130103 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 sortofopencoded 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); } Responsible Changed FromTo: freebsdbugs>freebsdnet Over to maintainer(s). 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? 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? For bugs matching the following criteria: Status: In Progress Changed: (is less than) 20140601 Reset to default assignee and clear inprogress tags. Mail being skipped 