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

diff --git a/usr/src/sys/net/radix.c b/usr/src/sys/net/radix.c
index fb0d340..f1f52db 100644 (file)
--- a/usr/src/sys/net/radix.c
+++ b/usr/src/sys/net/radix.c
@@ -4,7 +4,7 @@
  *
  * %sccs.include.redist.c%
  *
  *
  * %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 <sys/param.h>
 #ifdef KERNEL
 #ifndef _RADIX_H_
 #include <sys/param.h>
 #ifdef KERNEL

+#ifdef KERNEL

 #include <sys/systm.h>
 #include <sys/malloc.h>
 #define        M_DONTWAIT M_NOWAIT
 #include <sys/domain.h>
 #else
 #include <stdlib.h>
 #include <sys/systm.h>
 #include <sys/malloc.h>
 #define        M_DONTWAIT M_NOWAIT
 #include <sys/domain.h>
 #else
 #include <stdlib.h>

+#else
+#include <stdlib.h>

 #endif
 #include <sys/syslog.h>
 #include <net/radix.h>
 #endif
 #include <sys/syslog.h>
 #include <net/radix.h>

+#include <sys/syslog.h>
+#include <net/radix.h>

 #endif
 
 int    max_keylen;
 #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};
 
 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;
 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;
 }
 
        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;
 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;

+       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) {
        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);
                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)
        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;
                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;
 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;
 }
 
        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;
 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;
        }
                                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 ))
 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_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;
        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 728e00d..013397a 100644 (file)
--- a/usr/src/sys/net/radix.h
+++ b/usr/src/sys/net/radix.h
@@ -4,7 +4,7 @@
  *
  * %sccs.include.redist.c%
  *
  *
  * %sccs.include.redist.c%
  *

- *     @(#)radix.h     8.1.2.1 (Berkeley) %G%
+ *     @(#)radix.h     8.2 (Berkeley) %G%

  */
 
 #ifndef _RADIX_H_
  */
 
 #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));
                __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 */
        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))
 #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);
 #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*/
 #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));
 
 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 b2100ac..60edf79 100644 (file)
--- a/usr/src/sys/net/rtsock.c
+++ b/usr/src/sys/net/rtsock.c
@@ -4,7 +4,7 @@
  *
  * %sccs.include.redist.c%
  *
  *
  * %sccs.include.redist.c%
  *

- *     @(#)rtsock.c    8.3.1.1 (Berkeley) %G%
+ *     @(#)rtsock.c    8.4 (Berkeley) %G%

  */
 
 #include <sys/param.h>
  */
 
 #include <sys/param.h>


@@ -106,6 +106,7 @@ route_output(m, so)
        register struct rtentry *rt = 0;
        struct rtentry *saved_nrt = 0;
        struct radix_node_head *rnh;
        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;
        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,
 
        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:
                break;
 
        case RTM_GET:


@@ -179,6 +185,7 @@ route_output(m, so)
                switch(rtm->rtm_type) {
 
                case RTM_GET:
                switch(rtm->rtm_type) {
 
                case RTM_GET:

+               report:

                        dst = rt_key(rt);
                        gate = rt->rt_gateway;
                        netmask = rt_mask(rt);
                        dst = rt_key(rt);
                        gate = rt->rt_gateway;
                        netmask = rt_mask(rt);


@@ -193,7 +200,7 @@ route_output(m, so)
                                        ifaaddr = 0;
                            }
                        }
                                        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;
                                (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;
                        }
                                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;
                                (struct walkarg *)0);
                        rtm->rtm_flags = rt->rt_flags;
                        rtm->rtm_rmx = rt->rt_rmx;