From 4ba36fcc23223922534fcda01635350cb70d1880 Mon Sep 17 00:00:00 2001 From: Keith Sklower Date: Mon, 31 Oct 1994 21:42:56 -0800 Subject: [PATCH] compromise fixes for duped keys SCCS-vsn: sys/net/radix.c 8.3 SCCS-vsn: sys/net/radix.h 8.2 SCCS-vsn: sys/net/rtsock.c 8.4 --- usr/src/sys/net/radix.c | 100 ++++++++++++++++++++++++++++++++++++++- usr/src/sys/net/radix.h | 6 ++- usr/src/sys/net/rtsock.c | 15 ++++-- 3 files changed, 115 insertions(+), 6 deletions(-) diff --git a/usr/src/sys/net/radix.c b/usr/src/sys/net/radix.c index fb0d340e25..f1f52db589 100644 --- a/usr/src/sys/net/radix.c +++ b/usr/src/sys/net/radix.c @@ -4,7 +4,7 @@ * * %sccs.include.redist.c% * - * @(#)radix.c 8.2.2.1 (Berkeley) %G% + * @(#)radix.c 8.3 (Berkeley) %G% */ /* @@ -13,15 +13,20 @@ #ifndef _RADIX_H_ #include #ifdef KERNEL +#ifdef KERNEL #include #include #define M_DONTWAIT M_NOWAIT #include #else #include +#else +#include #endif #include #include +#include +#include #endif int max_keylen; @@ -134,6 +139,13 @@ rn_refines(m_arg, n_arg) static int low_bits[] = {1, 3, 7, 15, 31, 63, 127, 255}; static int mask_bits[] = {1, 2, 4, 8, 16, 32, 64, 128}; +struct radix_node * +rn_lookup(v_arg, m_arg, head) + void *v_arg, *m_arg; + struct radix_node_head *head; +{ + register struct radix_node *x; + caddr_t netmask = 0; struct radix_node * rn_lookup(v_arg, m_arg, head) void *v_arg, *m_arg; @@ -160,6 +172,40 @@ rn_lookup(v_arg, m_arg, head) return x; } +static +rn_satsifies_leaf(trial, leaf, skip) + char *trial; + register struct radix_node *leaf; + int skip; +{ + register char *cp = trial, *cp2 = leaf->rn_key, *cp3 = leaf->rn_mask; + char *cplim; + int length = min(*(u_char *)cp, *(u_char *)cp2); + + if (cp3 == 0) + cp3 = rn_ones; + else + length = min(length, *(u_char *)cp3); + cplim = cp + length; cp3 += skip; cp2 += skip; + for (cp += skip; cp < cplim; cp++, cp2++, cp3++) + if ((*cp ^ *cp2) & *cp3) + return 0; + return 1; +} + + if (m_arg) { + if ((x = rn_addmask(m_arg, 1, head->rnh_treetop->rn_off)) == 0) + return (0); + netmask = x->rn_key; + } + x = rn_match(v_arg, head); + if (x && netmask) { + while (x && x->rn_mask != netmask) + x = x->rn_dupedkey; + } + return x; +} + static rn_satsifies_leaf(trial, leaf, skip) char *trial; @@ -339,6 +385,8 @@ rn_match(v_arg, head) */ if (t->rn_mask) vlen = *(u_char *)t->rn_mask; + if (t->rn_mask) + vlen = *(u_char *)t->rn_mask; for (saved_t = t; t; t = t->rn_dupedkey) /* if (bits_matched >= mask_index) */ if (rn_b <= t->rn_b) { @@ -481,6 +529,14 @@ rn_masksubr(n_arg, v_arg, skip, head, len_p) Bzero(addmask_key + m0, last_zeroed - m0); *addmask_key = last_zeroed = mlen; x = rn_search(addmask_key, rn_masktop); + if (Bcmp(addmask_key, x->rn_key, mlen) != 0) + x = 0; + if (x || search) + return (x); + if (m0 < last_zeroed) + Bzero(addmask_key + m0, last_zeroed - m0); + *addmask_key = last_zeroed = mlen; + x = rn_search(addmask_key, rn_masktop); if (Bcmp(addmask_key, x->rn_key, mlen) != 0) x = 0; if (x || search) @@ -510,6 +566,7 @@ rn_masksubr(n_arg, v_arg, skip, head, len_p) x->rn_b = -1 - mlen; } b += (cp - netmask) << 3; + b += (cp - netmask) << 3; found: if (len_p) *len_p = (-1 - x->rn_b) - head->rnh_offset; @@ -555,6 +612,45 @@ rn_new_radix_mask(tt, next) return m; } +static int /* XXX: arbitrary ordering for non-contiguous masks */ +rn_lexobetter(m_arg, n_arg) + void *m_arg, *n_arg; +{ + register u_char *mp = m_arg, *np = n_arg, *lim; + + if (*mp > *np) + return 1; /* not really, but need to check longer one first */ + if (*mp == *np) + for (lim = mp + *mp; mp < lim;) + if (*mp++ > *np++) + return 1; + return 0; +} + +static struct radix_mask * +rn_new_radix_mask(tt, next) + register struct radix_node *tt; + register struct radix_mask *next; +{ + register struct radix_mask *m; + + MKGet(m); + if (m == 0) { + log(LOG_ERR, "Mask for route not entered\n"); + return (0); + } + Bzero(m, sizeof *m); + m->rm_b = tt->rn_b; + m->rm_flags = tt->rn_flags; + if (tt->rn_flags & RNF_NORMAL) + m->rm_leaf = tt; + else + m->rm_mask = tt->rn_mask; + m->rm_mklist = next; + tt->rn_mklist = m; + return m; +} + struct radix_node * rn_addroute(v_arg, n_arg, head, treenodes) void *v_arg, *n_arg; @@ -628,6 +724,7 @@ rn_addroute(v_arg, n_arg, head, treenodes) break; p->rn_mklist = m; *mp = 0; } +on2: on2: /* Add new route to highest possible ancestor's list */ if ((netmask == 0) || (masklen > p->rn_b )) @@ -837,6 +934,7 @@ rn_inithead(head, off) rnh->rnh_deladdr = rn_delete; rnh->rnh_matchaddr = rn_match; rnh->rnh_lookup = rn_lookup; + rnh->rnh_lookup = rn_lookup; rnh->rnh_walktree = rn_walktree; rnh->rnh_bits_matched = rn_unmapped_bits_matched; rnh->rnh_set_mask = rn_unmapped_set_mask; diff --git a/usr/src/sys/net/radix.h b/usr/src/sys/net/radix.h index 728e00d3d4..013397a967 100644 --- a/usr/src/sys/net/radix.h +++ b/usr/src/sys/net/radix.h @@ -4,7 +4,7 @@ * * %sccs.include.redist.c% * - * @(#)radix.h 8.1.2.1 (Berkeley) %G% + * @(#)radix.h 8.2 (Berkeley) %G% */ #ifndef _RADIX_H_ @@ -67,6 +67,8 @@ struct radix_node_head { __P((void *v, struct radix_node_head *head)); struct radix_node *(*rnh_lookup) /* locate based on sockaddr */ __P((void *v, void *mask, struct radix_node_head *head)); + struct radix_node *(*rnh_lookup) /* locate based on sockaddr */ + __P((void *v, void *mask, struct radix_node_head *head)); struct radix_node *(*rnh_matchpkt) /* locate based on packet hdr */ __P((void *v, struct radix_node_head *head)); int (*rnh_walktree) /* traverse tree */ @@ -91,6 +93,7 @@ struct radix_node_head { #ifndef KERNEL #define Bcmp(a, b, n) bcmp(((char *)(a)), ((char *)(b)), (n)) #define Bcopy(a, b, n) bcopy(((char *)(a)), ((char *)(b)), (unsigned)(n)) +#define Bcopy(a, b, n) bcopy(((char *)(a)), ((char *)(b)), (unsigned)(n)) #define Bzero(p, n) bzero((char *)(p), (int)(n)); #define R_Malloc(p, t, n) (p = (t) malloc((unsigned int)(n))) #define Free(p) free((char *)p); @@ -102,6 +105,7 @@ struct radix_node_head { #define Free(p) free((caddr_t)p, M_RTABLE); #endif /*KERNEL*/ #endif /*KERNEL*/ +#endif /*KERNEL*/ void rn_init __P((void)); int rn_inithead __P((void **, int)); diff --git a/usr/src/sys/net/rtsock.c b/usr/src/sys/net/rtsock.c index b2100ac79f..60edf79537 100644 --- a/usr/src/sys/net/rtsock.c +++ b/usr/src/sys/net/rtsock.c @@ -4,7 +4,7 @@ * * %sccs.include.redist.c% * - * @(#)rtsock.c 8.3.1.1 (Berkeley) %G% + * @(#)rtsock.c 8.4 (Berkeley) %G% */ #include @@ -106,6 +106,7 @@ route_output(m, so) register struct rtentry *rt = 0; struct rtentry *saved_nrt = 0; struct radix_node_head *rnh; + struct radix_node_head *rnh; struct rt_addrinfo info; int len, error = 0; struct ifnet *ifp = 0; @@ -163,7 +164,12 @@ route_output(m, so) case RTM_DELETE: error = rtrequest(RTM_DELETE, dst, gate, netmask, - rtm->rtm_flags, (struct rtentry **)0); + rtm->rtm_flags, &saved_nrt); + if (error == 0) { + if ((rt = saved_nrt)->rt_refcnt <= 0) + rt->rt_refcnt++; + goto report; + } break; case RTM_GET: @@ -179,6 +185,7 @@ route_output(m, so) switch(rtm->rtm_type) { case RTM_GET: + report: dst = rt_key(rt); gate = rt->rt_gateway; netmask = rt_mask(rt); @@ -193,7 +200,7 @@ route_output(m, so) ifaaddr = 0; } } - len = rt_msg2(RTM_GET, &info, (caddr_t)0, + len = rt_msg2(rtm->rtm_type, &info, (caddr_t)0, (struct walkarg *)0); if (len > rtm->rtm_msglen) { struct rt_msghdr *new_rtm; @@ -203,7 +210,7 @@ route_output(m, so) Bcopy(rtm, new_rtm, rtm->rtm_msglen); Free(rtm); rtm = new_rtm; } - (void)rt_msg2(RTM_GET, &info, (caddr_t)rtm, + (void)rt_msg2(rtm->rtm_type, &info, (caddr_t)rtm, (struct walkarg *)0); rtm->rtm_flags = rt->rt_flags; rtm->rtm_rmx = rt->rt_rmx; -- 2.20.1