From 09bae951cdb7fe1a16e3051107f37b8355e8869f Mon Sep 17 00:00:00 2001 From: wollman Date: Mon, 20 Mar 1995 21:30:21 +0000 Subject: Better fix for the deletion of parents of cloned routes problem, superseding the `nextchild' hack. This also provides a way forward to fix RTM_CHANGE and RTM_ADD as well. --- sys/net/radix.c | 81 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++- sys/net/radix.h | 5 +++- sys/net/route.c | 76 +++++++++++++++++++---------------------------------- sys/net/route.h | 9 +++---- 4 files changed, 115 insertions(+), 56 deletions(-) (limited to 'sys/net') diff --git a/sys/net/radix.c b/sys/net/radix.c index d8da6e2..17773d3 100644 --- a/sys/net/radix.c +++ b/sys/net/radix.c @@ -31,7 +31,7 @@ * SUCH DAMAGE. * * @(#)radix.c 8.2 (Berkeley) 1/4/94 - * $Id: radix.c,v 1.4 1994/10/08 22:38:23 phk Exp $ + * $Id: radix.c,v 1.5 1994/10/15 21:33:17 phk Exp $ */ /* @@ -662,6 +662,84 @@ out: return (tt); } +/* + * This is the same as rn_walktree() except for the parameters and the + * exit. + */ +int +rn_walktree_from(h, a, m, f, w) + struct radix_node_head *h; + void *a, *m; + register int (*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. + */ + for (rn = h->rnh_treetop; rn->rn_b >= 0; ) { + last = rn; + if (!(rn->rn_bmask & xm[rn->rn_off])) + break; + if (rn->rn_bmask & xa[rn->rn_off]) { + rn = rn->rn_r; + } else { + rn = rn->rn_l; + } + } + + /* + * 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_b; + + /* + * 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_b >= 0) + rn = rn->rn_l; + + while (!stopping) { + base = rn; + /* If at right child go back up, otherwise, go right */ + while (rn->rn_p->rn_r == rn && !(rn->rn_flags & RNF_ROOT)) { + rn = rn->rn_p; + + /* if went up beyond last, stop */ + if (rn->rn_b < lastb) { + stopping = 1; + } + } + + /* Find the next *leaf* since next node might vanish, too */ + for (rn = rn->rn_p->rn_r; rn->rn_b >= 0;) + rn = rn->rn_l; + next = rn; + /* Process leaves */ + while ((rn = base) != 0) { + base = rn->rn_dupedkey; + if (!(rn->rn_flags & RNF_ROOT) + && (error = (*f)(rn, w))) + return (error); + } + rn = next; + } + return 0; +} + int rn_walktree(h, f, w) struct radix_node_head *h; @@ -728,6 +806,7 @@ rn_inithead(head, off) rnh->rnh_deladdr = rn_delete; rnh->rnh_matchaddr = rn_match; rnh->rnh_walktree = rn_walktree; + rnh->rnh_walktree_from = rn_walktree_from; rnh->rnh_treetop = t; return (1); } diff --git a/sys/net/radix.h b/sys/net/radix.h index 9d44941..89df2ac 100644 --- a/sys/net/radix.h +++ b/sys/net/radix.h @@ -31,7 +31,7 @@ * SUCH DAMAGE. * * @(#)radix.h 8.1 (Berkeley) 6/10/93 - * $Id: radix.h,v 1.5 1994/11/14 14:06:06 bde Exp $ + * $Id: radix.h,v 1.6 1995/03/16 18:14:29 bde Exp $ */ #ifndef _NET_RADIX_H_ @@ -120,6 +120,9 @@ struct radix_node_head { __P((void *v, struct radix_node_head *head)); int (*rnh_walktree) /* traverse tree */ __P((struct radix_node_head *head, walktree_f_t *f, void *w)); + int (*rnh_walktree_from) /* traverse tree below a */ + __P((struct radix_node_head *head, void *a, void *m, + walktree_f_t *f, void *w)); void (*rnh_close) /* do something when the last ref drops */ __P((struct radix_node *rn, struct radix_node_head *head)); struct radix_node rnh_nodes[3]; /* empty tree for common case */ diff --git a/sys/net/route.c b/sys/net/route.c index 510a085..b17b2c1 100644 --- a/sys/net/route.c +++ b/sys/net/route.c @@ -31,7 +31,7 @@ * SUCH DAMAGE. * * @(#)route.c 8.2 (Berkeley) 11/15/93 - * $Id: route.c,v 1.15 1995/01/23 17:53:21 davidg Exp $ + * $Id: route.c,v 1.16 1995/03/16 18:14:30 bde Exp $ */ #include @@ -53,10 +53,6 @@ #include #include -#ifdef NS -#include -#endif - #define SA(p) ((struct sockaddr *)(p)) int rttrash; /* routes not in table but not freed */ @@ -350,7 +346,7 @@ ifa_ifwithroute(flags, dst, gateway) #define ROUNDUP(a) (a>0 ? (1 + (((a) - 1) | (sizeof(long) - 1))) : sizeof(long)) -static void rt_fixfamily(struct rtentry *rt); +static int rt_fixdelete(struct radix_node *, void *); int rtrequest(req, dst, gateway, netmask, flags, ret_nrt) @@ -379,7 +375,15 @@ rtrequest(req, dst, gateway, netmask, flags, ret_nrt) panic ("rtrequest delete"); rt = (struct rtentry *)rn; rt->rt_flags &= ~RTF_UP; - rt_fixfamily(rt); + + /* + * Now search what's left of the subtree for any cloned + * routes which might have been formed from this node. + */ + if (rt->rt_flags & RTF_PRCLONING) { + rnh->rnh_walktree_from(rnh, dst, netmask, + rt_fixdelete, rt); + } if (rt->rt_gwroute) { rt = rt->rt_gwroute; RTFREE(rt); (rt = (struct rtentry *)rn)->rt_gwroute = 0; @@ -444,13 +448,10 @@ rtrequest(req, dst, gateway, netmask, flags, ret_nrt) ifa->ifa_refcnt++; rt->rt_ifa = ifa; rt->rt_ifp = ifa->ifa_ifp; - if (req == RTM_RESOLVE) + if (req == RTM_RESOLVE) { rt->rt_rmx = (*ret_nrt)->rt_rmx; /* copy metrics */ - if ((req == RTM_RESOLVE) - && ((*ret_nrt)->rt_flags & RTF_PRCLONING)) { - rt->rt_parent = (*ret_nrt); - rt->rt_nextchild = (*ret_nrt)->rt_nextchild; - (*ret_nrt)->rt_nextchild = rt; + if ((*ret_nrt)->rt_flags & RTF_PRCLONING) + rt->rt_parent = (*ret_nrt); } if (ifa->ifa_rtrequest) ifa->ifa_rtrequest(req, rt, SA(ret_nrt ? *ret_nrt : 0)); @@ -468,45 +469,22 @@ bad: /* * Called from rtrequest(RTM_DELETE, ...) to fix up the route's ``family'' * (i.e., the routes related to it by the operation of cloning). This - * involves deleting the entire chain of descendants (in the case of a parent - * route being deleted), or removing this route from the chain (in the case - * of a child route being deleted). + * routine is iterated over all potential former-child-routes by way of + * rnh->rnh_walktree_from() above, and those that actually are children of + * the late parent (passed in as VP here) are themselves deleted. */ -static void -rt_fixfamily(struct rtentry *rt0) +static int +rt_fixdelete(struct radix_node *rn, void *vp) { - struct rtentry *rt, *lrt, *nrt; - - if(rt = rt0->rt_parent) { - if(rt->rt_flags & RTF_CHAINDELETE) - return; /* relax, it will all be done for us */ - - /* So what if it takes linear time? */ - do { - lrt = rt; - rt = rt->rt_nextchild; - } while(rt && rt != rt0); - lrt->rt_nextchild = rt0->rt_nextchild; - } else if((rt = rt0)->rt_nextchild) { - lrt = rt; - rt->rt_flags |= RTF_CHAINDELETE; - - rt = rt->rt_nextchild; - - while(rt) { - nrt = rt->rt_nextchild; - /* - * There might be some value to open-coding this - * rtrequest call, but I am not yet convinced of - * the value of this. - */ - rtrequest(RTM_DELETE, rt_key(rt), - (struct sockaddr *)0, rt_mask(rt), - rt->rt_flags, (struct rtentry **)0); - rt = nrt; - } - lrt->rt_flags &= ~RTF_CHAINDELETE; + struct rtentry *rt = (struct rtentry *)rn; + struct rtentry *rt0 = vp; + + if (rt->rt_parent == rt0) { + return rtrequest(RTM_DELETE, rt_key(rt), + (struct sockaddr *)0, rt_mask(rt), + rt->rt_flags, (struct rtentry **)0); } + return 0; } int diff --git a/sys/net/route.h b/sys/net/route.h index 76b07d2..58178ab 100644 --- a/sys/net/route.h +++ b/sys/net/route.h @@ -31,7 +31,7 @@ * SUCH DAMAGE. * * @(#)route.h 8.3 (Berkeley) 4/19/94 - * $Id: route.h,v 1.11 1995/02/07 19:05:12 wollman Exp $ + * $Id: route.h,v 1.12 1995/02/08 20:01:13 wollman Exp $ */ #ifndef _NET_ROUTE_H_ @@ -101,10 +101,9 @@ struct rtentry { #define rt_key(r) ((struct sockaddr *)((r)->rt_nodes->rn_key)) #define rt_mask(r) ((struct sockaddr *)((r)->rt_nodes->rn_mask)) struct sockaddr *rt_gateway; /* value */ - /* XXX - rt_flags should be unified with rt_prflags */ - short rt_filler; /* up/down?, host/net */ + short rt_filler; /* was short flags field */ short rt_refcnt; /* # held references */ - u_long rt_flags; /* protocol-specific flags */ + u_long rt_flags; /* up/down?, host/net */ struct ifnet *rt_ifp; /* the answer: interface to use */ struct ifaddr *rt_ifa; /* the answer: interface to use */ struct sockaddr *rt_genmask; /* for generation of cloned routes */ @@ -115,7 +114,7 @@ struct rtentry { struct sockaddr *, int)); /* output routine for this (rt,if) */ struct rtentry *rt_parent; /* cloning parent of this route */ - struct rtentry *rt_nextchild; /* next cloned child of this route */ + void *rt_filler2; /* more filler */ }; /* -- cgit v1.1