checkpoint first working version with routing trees. (by sklower).

SCCS-vsn: sys/net/route.c 7.7

diff --git a/usr/src/sys/net/route.c b/usr/src/sys/net/route.c
index 2ebae8a..4d898a4 100644 (file)
--- a/usr/src/sys/net/route.c
+++ b/usr/src/sys/net/route.c
@@ -14,7 +14,7 @@
  * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
  * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  *
  * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
  * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  *

- *     @(#)route.c     7.6 (Berkeley) %G%
+ *     @(#)route.c     7.7 (Berkeley) %G%

  */
 
 #include "param.h"
  */
 
 #include "param.h"


@@ -30,84 +30,70 @@
 #include "if.h"
 #include "af.h"
 #include "route.h"
 #include "if.h"
 #include "af.h"
 #include "route.h"

+#include "radix.h"
+
+#include "radix.c"
+#ifdef INET
+#include "../netinet/in.h"
+#include "../netinet/in_var.h"
+#endif

 
 int    rttrash;                /* routes not in table but not freed */
 struct sockaddr wildcard;      /* zero valued cookie for wildcard searches */
 int    rthashsize = RTHASHSIZ; /* for netstat, etc. */
 
 
 int    rttrash;                /* routes not in table but not freed */
 struct sockaddr wildcard;      /* zero valued cookie for wildcard searches */
 int    rthashsize = RTHASHSIZ; /* for netstat, etc. */
 

+static int rtinits_done = 0;
+struct radix_node_head *ns_rnhead, *in_rnhead;
+rtinitheads()
+{
+       if (rtinits_done == 0 &&
+           rn_inithead(&ns_rnhead, 16, AF_NS) &&
+           rn_inithead(&in_rnhead, 32, AF_INET))
+               rtinits_done = 1;
+}
+

 /*
  * Packet routing routines.
  */
 rtalloc(ro)
        register struct route *ro;
 {
 /*
  * Packet routing routines.
  */
 rtalloc(ro)
        register struct route *ro;
 {

-       register struct rtentry *rt;
-       register struct mbuf *m;
-       register u_long hash;
-       struct sockaddr *dst = &ro->ro_dst;
-       int (*match)(), doinghost, s;
-       struct afhash h;
-       u_int af = dst->sa_family;
-       struct mbuf **table;
+       register struct radix_node_head *rnh;
+       register struct radix_node *rn;
+       register struct rtentry *rt = 0;
+       u_char af = ro->ro_dst.sa_family;
+       int  s;

 
        if (ro->ro_rt && ro->ro_rt->rt_ifp && (ro->ro_rt->rt_flags & RTF_UP))
                return;                          /* XXX */
 
        if (ro->ro_rt && ro->ro_rt->rt_ifp && (ro->ro_rt->rt_flags & RTF_UP))
                return;                          /* XXX */

-       if (af >= AF_MAX)
-               return;
-       (*afswitch[af].af_hash)(dst, &h);
-       match = afswitch[af].af_netmatch;
-       hash = h.afh_hosthash, table = rthost, doinghost = 1;

        s = splnet();
        s = splnet();

-again:
-       for (m = table[RTHASHMOD(hash)]; m; m = m->m_next) {
-               rt = mtod(m, struct rtentry *);
-               if (rt->rt_hash != hash)
-                       continue;
-               if ((rt->rt_flags & RTF_UP) == 0 ||
-                   (rt->rt_ifp->if_flags & IFF_UP) == 0)
-                       continue;
-               if (doinghost) {
-                       if (bcmp((caddr_t)&rt->rt_dst, (caddr_t)dst,
-                           sizeof (*dst)))
-                               continue;
-               } else {
-                       if (rt->rt_dst.sa_family != af ||
-                           !(*match)(&rt->rt_dst, dst))
-                               continue;
-               }
+       for (rnh = radix_node_head; rnh && (af != rnh->rnh_af); )
+               rnh = rnh->rnh_next;
+       if (rnh && rnh->rnh_treetop &&
+           (rn = rn_match((char *)&(ro->ro_dst), rnh->rnh_treetop)) &&
+           ((rn->rn_flags & RNF_ROOT) == 0)) {
+               rt = &(((struct nrtentry *)rn)->nrt_rt);

                rt->rt_refcnt++;
                rt->rt_refcnt++;

-               splx(s);
-               if (dst == &wildcard)
-                       rtstat.rts_wildcard++;
-               ro->ro_rt = rt;
-               return;
-       }
-       if (doinghost) {
-               doinghost = 0;
-               hash = h.afh_nethash, table = rtnet;
-               goto again;
-       }
-       /*
-        * Check for wildcard gateway, by convention network 0.
-        */
-       if (dst != &wildcard) {
-               dst = &wildcard, hash = 0;
-               goto again;
-       }
+       } else
+               rtstat.rts_unreach++;
+       ro->ro_rt = rt;

        splx(s);
        splx(s);

-       rtstat.rts_unreach++;

 }
 
 rtfree(rt)
        register struct rtentry *rt;
 {
 }
 
 rtfree(rt)
        register struct rtentry *rt;
 {

-
+       register struct nrtentry *nrt;
+       u_char *af;

        if (rt == 0)
                panic("rtfree");
        rt->rt_refcnt--;
        if (rt == 0)
                panic("rtfree");
        rt->rt_refcnt--;

-       if (rt->rt_refcnt == 0 && (rt->rt_flags&RTF_UP) == 0) {
+       if (rt->rt_refcnt <= 0 && (rt->rt_flags&RTF_UP) == 0) {

                rttrash--;
                rttrash--;

-               (void) m_free(dtom(rt));
+               nrt = (struct nrtentry *) (((struct radix_node *)rt) - 2);
+               if (nrt->nrt_nodes->rn_flags & (RNF_ACTIVE | RNF_ROOT))
+                       panic ("rtfree 2");
+               free((caddr_t)nrt, M_RTABLE);

        }
 }
 
        }
 }
 


@@ -117,7 +103,7 @@ rtfree(rt)
  * Normally called as a result of a routing redirect
  * message from the network layer.
  *
  * Normally called as a result of a routing redirect
  * message from the network layer.
  *

- * N.B.: must be called at splnet or higher
+ * N.B.: must be called at splnet

  *
  */
 rtredirect(dst, gateway, flags, src)
  *
  */
 rtredirect(dst, gateway, flags, src)


@@ -151,16 +137,25 @@ rtredirect(dst, gateway, flags, src)
                return;
        }
        /*
                return;
        }
        /*

+        * Old comment:

         * Create a new entry if we just got back a wildcard entry
         * or the the lookup failed.  This is necessary for hosts
         * which use routing redirects generated by smart gateways
         * to dynamically build the routing tables.
         * Create a new entry if we just got back a wildcard entry
         * or the the lookup failed.  This is necessary for hosts
         * which use routing redirects generated by smart gateways
         * to dynamically build the routing tables.

-        */
-       if (rt &&
-           (*afswitch[dst->sa_family].af_netmatch)(&wildcard, &rt->rt_dst)) {
+        *
+        * New comment:
+        * If we survived the previous tests, it doesn't matter
+        * what sort of entry we got when we looked it up;
+        * we should just go ahead and free the reference to
+        * the route we created.  rtalloc will not give a
+        * pointer to the root node.  And if we got a pointer
+        * to a default gateway, we should free the reference
+        * in any case.
+       if (rt) {

                rtfree(rt);
                rt = 0;
        }
                rtfree(rt);
                rt = 0;
        }

+        */

        if (rt == 0) {
                rtinit(dst, gateway, (int)SIOCADDRT,
                    (flags & RTF_HOST) | RTF_GATEWAY | RTF_DYNAMIC);
        if (rt == 0) {
                rtinit(dst, gateway, (int)SIOCADDRT,
                    (flags & RTF_HOST) | RTF_GATEWAY | RTF_DYNAMIC);


@@ -185,7 +180,7 @@ rtredirect(dst, gateway, flags, src)
                         * Smash the current notion of the gateway to
                         * this destination.
                         */
                         * Smash the current notion of the gateway to
                         * this destination.
                         */

-                       rt->rt_gateway = *gateway;
+                       rt->rt_gateway = *gateway; /*XXX -- size? */

                        rt->rt_flags |= RTF_MODIFIED;
                        rtstat.rts_newgateway++;
                }
                        rt->rt_flags |= RTF_MODIFIED;
                        rtstat.rts_newgateway++;
                }


@@ -208,6 +203,60 @@ rtioctl(cmd, data)
                return (u.u_error);
        return (rtrequest(cmd, (struct rtentry *)data));
 }
                return (u.u_error);
        return (rtrequest(cmd, (struct rtentry *)data));
 }

+/*
+ * This routine will go away soon.
+ * Tries to guess which netmask is appropriate for a given net.
+ */
+static struct sockaddr_in rtgmask = { 8, 0 };
+
+char *
+rtgetmask(sa, ifa)
+register struct sockaddr *sa;
+register struct ifaddr *ifa;
+{
+       u_long i, net, mask, subnet;
+
+       switch (sa->sa_family) {
+#ifdef INET
+       register struct in_ifaddr *ia;
+
+       case AF_INET:
+
+               i = ntohl(((struct sockaddr_in *)sa)->sin_addr.s_addr);
+               if (i == 0) {
+                       rtgmask.sin_addr.s_addr = 0;
+                       return ((char *)&rtgmask);
+               } else if (IN_CLASSA(i)) {
+                       net = i & IN_CLASSA_NET;
+                       mask = IN_CLASSA_NET;
+               } else if (IN_CLASSB(i)) {
+                       net = i & IN_CLASSB_NET;
+                       mask = IN_CLASSB_NET;
+               } else if (IN_CLASSC(i)) {
+                       net = i & IN_CLASSC_NET;
+                       mask = IN_CLASSC_NET;
+               } else {
+                       net = i;
+                       mask = 0xffffffff;
+               }
+
+               /*
+                * Check whether network is a subnet;
+                * if so, return subnet number.
+                */
+               for (ia = in_ifaddr; ia; ia = ia->ia_next)
+                       if (net == ia->ia_net) {
+                               ifa = &ia->ia_ifa;
+                               break;
+                       }
+               if (ia == 0) {
+                       rtgmask.sin_addr.s_addr = ntohl(mask);
+                       return ((char *)&rtgmask);
+               }
+#endif
+       }
+       return ((char *)ifa->ifa_netmask);
+}

 
 /*
  * Carry out a request to change the routing table.  Called by
 
 /*
  * Carry out a request to change the routing table.  Called by


@@ -218,18 +267,20 @@ rtrequest(req, entry)
        int req;
        register struct rtentry *entry;
 {
        int req;
        register struct rtentry *entry;
 {

-       register struct mbuf *m, **mprev;
-       struct mbuf **mfirst;

        register struct rtentry *rt;
        register struct rtentry *rt;

-       struct afhash h;
-       int s, error = 0, (*match)();
-       u_int af;
-       u_long hash;
+       int s, error = 0, found;
+       u_char af;

        struct ifaddr *ifa;
        struct ifaddr *ifa_ifwithdstaddr();
        struct ifaddr *ifa;
        struct ifaddr *ifa_ifwithdstaddr();

+       register struct nrtentry *nrt;
+       register struct radix_node *rn;
+       register struct radix_node_head *rnh;
+       struct radix_node *head;
+       char *netmask;

 
 #ifdef COMPAT_43
 #if BYTE_ORDER != BIG_ENDIAN
 
 #ifdef COMPAT_43
 #if BYTE_ORDER != BIG_ENDIAN

+       s = splnet();

        if (entry->rt_dst.sa_family == 0 && entry->rt_dst.sa_len < 16) {
                entry->rt_dst.sa_family = entry->rt_dst.sa_len;
                entry->rt_dst.sa_len = 16;
        if (entry->rt_dst.sa_family == 0 && entry->rt_dst.sa_len < 16) {
                entry->rt_dst.sa_family = entry->rt_dst.sa_len;
                entry->rt_dst.sa_len = 16;


@@ -245,99 +296,88 @@ rtrequest(req, entry)
                entry->rt_gateway.sa_len = 16;
 #endif
 #endif
                entry->rt_gateway.sa_len = 16;
 #endif
 #endif

+       if (rtinits_done == 0)
+               rtinitheads();

        af = entry->rt_dst.sa_family;
        af = entry->rt_dst.sa_family;

-       if (af >= AF_MAX)
-               return (EAFNOSUPPORT);
-       (*afswitch[af].af_hash)(&entry->rt_dst, &h);
-       if (entry->rt_flags & RTF_HOST) {
-               hash = h.afh_hosthash;
-               mprev = &rthost[RTHASHMOD(hash)];
+       for (rnh = radix_node_head; rnh && (af != rnh->rnh_af); )
+               rnh = rnh->rnh_next;
+       if (rnh == 0) {
+               error = ESRCH;
+               goto bad;
+       }
+       head = rnh->rnh_treetop;
+       if ((entry->rt_flags & RTF_GATEWAY) == 0) {
+               /*
+                * If we are adding a route to an interface,
+                * and the interface is a pt to pt link
+                * we should search for the destination
+                * as our clue to the interface.  Otherwise
+                * we can use the local address.
+                */
+               ifa = 0;
+               if (entry->rt_flags & RTF_HOST) 
+                       ifa = ifa_ifwithdstaddr(&entry->rt_dst);
+               if (ifa == 0)
+                       ifa = ifa_ifwithaddr(&entry->rt_gateway);

        } else {
        } else {

-               hash = h.afh_nethash;
-               mprev = &rtnet[RTHASHMOD(hash)];
+               /*
+                * If we are adding a route to a remote net
+                * or host, the gateway may still be on the
+                * other end of a pt to pt link.
+                */
+               ifa = ifa_ifwithdstaddr(&entry->rt_gateway);

        }
        }

-       match = afswitch[af].af_netmatch;
-       s = splimp();
-       for (mfirst = mprev; m = *mprev; mprev = &m->m_next) {
-               rt = mtod(m, struct rtentry *);
-               if (rt->rt_hash != hash)
-                       continue;
-               if (entry->rt_flags & RTF_HOST) {
-                       if (!equal(&rt->rt_dst, &entry->rt_dst))
-                               continue;
-               } else {
-                       if (rt->rt_dst.sa_family != entry->rt_dst.sa_family ||
-                           (*match)(&rt->rt_dst, &entry->rt_dst) == 0)
-                               continue;
+       if (ifa == 0) {
+               ifa = ifa_ifwithnet(&entry->rt_gateway);
+               if (ifa == 0 && req == SIOCADDRT) {
+                       error = ENETUNREACH;
+                       goto bad;

                }
                }

-               if (equal(&rt->rt_gateway, &entry->rt_gateway))
-                       break;

        }
        }

+       if (entry->rt_flags & RTF_HOST)
+               netmask = 0;
+       else
+               netmask = rtgetmask(&entry->rt_dst, ifa);

        switch (req) {
 
        case SIOCDELRT:
        switch (req) {
 
        case SIOCDELRT:

-               if (m == 0) {
+               if ((rn = rn_delete((char *)&entry->rt_dst,
+                                       netmask, head)) == 0) {

                        error = ESRCH;
                        goto bad;
                }
                        error = ESRCH;
                        goto bad;
                }

-               *mprev = m->m_next;
-               if (rt->rt_refcnt > 0) {
-                       rt->rt_flags &= ~RTF_UP;
+               if (rn->rn_flags & (RNF_ACTIVE | RNF_ROOT))
+                       panic ("rtrequest delete");
+               nrt = (struct nrtentry *)rn;
+               nrt->nrt_rt.rt_flags &= ~RTF_UP;
+               if (nrt->nrt_rt.rt_refcnt > 0)

                        rttrash++;
                        rttrash++;

-                       m->m_next = 0;
-               } else
-                       (void) m_free(m);
+               else 
+                       free((caddr_t)nrt, M_RTABLE);

                break;
 
        case SIOCADDRT:
                break;
 
        case SIOCADDRT:

-               if (m) {
-                       error = EEXIST;
+               Malloc(nrt, struct nrtentry *, sizeof *nrt);
+               if (nrt == 0) {
+                       error = ENOBUFS;

                        goto bad;
                }
                        goto bad;
                }

-               if ((entry->rt_flags & RTF_GATEWAY) == 0) {
-                       /*
-                        * If we are adding a route to an interface,
-                        * and the interface is a pt to pt link
-                        * we should search for the destination
-                        * as our clue to the interface.  Otherwise
-                        * we can use the local address.
-                        */
-                       ifa = 0;
-                       if (entry->rt_flags & RTF_HOST) 
-                               ifa = ifa_ifwithdstaddr(&entry->rt_dst);
-                       if (ifa == 0)
-                               ifa = ifa_ifwithaddr(&entry->rt_gateway);
-               } else {
-                       /*
-                        * If we are adding a route to a remote net
-                        * or host, the gateway may still be on the
-                        * other end of a pt to pt link.
-                        */
-                       ifa = ifa_ifwithdstaddr(&entry->rt_gateway);
-               }
-               if (ifa == 0) {
-                       ifa = ifa_ifwithnet(&entry->rt_gateway);
-                       if (ifa == 0) {
-                               error = ENETUNREACH;
-                               goto bad;
-                       }
-               }
-               m = m_get(M_DONTWAIT, MT_RTABLE);
-               if (m == 0) {
-                       error = ENOBUFS;
+               Bzero(nrt, sizeof *nrt);
+               rn = rn_addroute((char *)&entry->rt_dst, netmask,
+                                                   head, nrt->nrt_nodes);
+               if (rn == 0) {
+                       free((caddr_t)nrt, M_RTABLE);
+                       error = EEXIST;

                        goto bad;
                }
                        goto bad;
                }

-               m->m_next = *mfirst;
-               *mfirst = m;
-               m->m_len = sizeof (struct rtentry);
-               rt = mtod(m, struct rtentry *);
-               rt->rt_hash = hash;
+               rt = &nrt->nrt_rt;
+               rn->rn_key = (char *)&(nrt->nrt_rt.rt_dst);

                rt->rt_dst = entry->rt_dst;
                rt->rt_gateway = entry->rt_gateway;
                rt->rt_flags = RTF_UP |
                    (entry->rt_flags & (RTF_HOST|RTF_GATEWAY|RTF_DYNAMIC));
                rt->rt_dst = entry->rt_dst;
                rt->rt_gateway = entry->rt_gateway;
                rt->rt_flags = RTF_UP |
                    (entry->rt_flags & (RTF_HOST|RTF_GATEWAY|RTF_DYNAMIC));

-               rt->rt_refcnt = 0;

                rt->rt_use = 0;
                rt->rt_use = 0;

+               rt->rt_refcnt = 0;

                rt->rt_ifp = ifa->ifa_ifp;
                break;
        }
                rt->rt_ifp = ifa->ifa_ifp;
                break;
        }