Index: projects/routing/sys/net/radix.h =================================================================== --- projects/routing/sys/net/radix.h (revision 287073) +++ projects/routing/sys/net/radix.h (revision 287074) @@ -1,190 +1,188 @@ /*- * Copyright (c) 1988, 1989, 1993 * The Regents of the University of California. All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * 4. Neither the name of the University nor the names of its contributors * may be used to endorse or promote products derived from this software * without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * * @(#)radix.h 8.2 (Berkeley) 10/31/94 * $FreeBSD$ */ #ifndef _RADIX_H_ #define _RADIX_H_ #ifdef _KERNEL #include #include #include #endif #ifdef MALLOC_DECLARE MALLOC_DECLARE(M_RTABLE); #endif /* * Radix search tree node layout. */ struct radix_node { struct radix_mask *rn_mklist; /* list of masks contained in subtree */ struct radix_node *rn_parent; /* parent */ short rn_bit; /* bit offset; -1-index(netmask) */ char rn_bmask; /* node: mask for bit test*/ u_char rn_flags; /* enumerated next */ #define RNF_NORMAL 1 /* leaf contains normal route */ #define RNF_ROOT 2 /* leaf is root leaf for tree */ #define RNF_ACTIVE 4 /* This node is alive (for rtfree) */ union { struct { /* leaf only data: */ caddr_t rn_Key; /* object of search */ caddr_t rn_Mask; /* netmask, if present */ struct radix_node *rn_Dupedkey; } rn_leaf; struct { /* node only data: */ int rn_Off; /* where to start compare */ struct radix_node *rn_L;/* progeny */ struct radix_node *rn_R;/* progeny */ } rn_node; } rn_u; #ifdef RN_DEBUG int rn_info; struct radix_node *rn_twin; struct radix_node *rn_ybro; #endif }; #define rn_dupedkey rn_u.rn_leaf.rn_Dupedkey #define rn_key rn_u.rn_leaf.rn_Key #define rn_mask rn_u.rn_leaf.rn_Mask #define rn_offset rn_u.rn_node.rn_Off #define rn_left rn_u.rn_node.rn_L #define rn_right rn_u.rn_node.rn_R /* * Annotations to tree concerning potential routes applying to subtrees. */ struct radix_mask { short rm_bit; /* bit offset; -1-index(netmask) */ char rm_unused; /* cf. rn_bmask */ u_char rm_flags; /* cf. rn_flags */ struct radix_mask *rm_mklist; /* more masks to try */ union { caddr_t rmu_mask; /* the mask */ struct radix_node *rmu_leaf; /* for normal routes */ } rm_rmu; int rm_refs; /* # of references to this struct */ }; #define rm_mask rm_rmu.rmu_mask #define rm_leaf rm_rmu.rmu_leaf /* extra field would make 32 bytes */ struct radix_head; typedef int walktree_f_t(struct radix_node *, void *); typedef struct radix_node *rn_matchaddr_f_t(void *v, struct radix_head *head); typedef struct radix_node *rn_addaddr_f_t(void *v, void *mask, struct radix_head *head, struct radix_node nodes[]); typedef struct radix_node *rn_deladdr_f_t(void *v, void *mask, struct radix_head *head); typedef struct radix_node *rn_lookup_f_t(void *v, void *mask, struct radix_head *head); typedef int rn_walktree_t(struct radix_head *head, walktree_f_t *f, void *w); typedef int rn_walktree_from_t(struct radix_head *head, void *a, void *m, walktree_f_t *f, void *w); typedef void rn_close_t(struct radix_node *rn, struct radix_head *head); struct radix_head { struct radix_node *rnh_treetop; union { struct radix_head *rnh_masks; /* Storage for our masks */ struct radix_node *mask_nodes; } s; }; struct radix_node_head { struct radix_head rh; - u_int rnh_gen; /* generation counter */ - int rnh_multipath; /* multipath capable ? */ rn_matchaddr_f_t *rnh_matchaddr; /* longest match for sockaddr */ rn_addaddr_f_t *rnh_addaddr; /* add based on sockaddr*/ rn_deladdr_f_t *rnh_deladdr; /* remove based on sockaddr */ rn_lookup_f_t *rnh_lookup; /* exact match for sockaddr */ rn_walktree_t *rnh_walktree; /* traverse tree */ rn_walktree_from_t *rnh_walktree_from; /* traverse tree below a */ rn_close_t *rnh_close; /*do something when the last ref drops*/ struct radix_node rnh_nodes[3]; /* empty tree for common case */ #ifdef _KERNEL struct rwlock rnh_lock; /* locks entire radix tree */ #endif }; /* XXX: Temporarily xported to support external radix users */ struct radix_mask_head { struct radix_head head; struct radix_node mask_nodes[3]; }; void rn_inithead_internal(struct radix_head *rh, struct radix_node *base_nodes, int off); #ifndef _KERNEL #define R_Malloc(p, t, n) (p = (t) malloc((unsigned int)(n))) #define R_Zalloc(p, t, n) (p = (t) calloc(1,(unsigned int)(n))) #define R_Free(p) free((char *)p); #else #define R_Malloc(p, t, n) (p = (t) malloc((unsigned long)(n), M_RTABLE, M_NOWAIT)) #define R_Zalloc(p, t, n) (p = (t) malloc((unsigned long)(n), M_RTABLE, M_NOWAIT | M_ZERO)) #define R_Free(p) free((caddr_t)p, M_RTABLE); #define RADIX_NODE_HEAD_LOCK_INIT(rnh) \ rw_init_flags(&(rnh)->rnh_lock, "radix node head", 0) #define RADIX_NODE_HEAD_LOCK(rnh) rw_wlock(&(rnh)->rnh_lock) #define RADIX_NODE_HEAD_UNLOCK(rnh) rw_wunlock(&(rnh)->rnh_lock) #define RADIX_NODE_HEAD_RLOCK(rnh) rw_rlock(&(rnh)->rnh_lock) #define RADIX_NODE_HEAD_RUNLOCK(rnh) rw_runlock(&(rnh)->rnh_lock) #define RADIX_NODE_HEAD_LOCK_TRY_UPGRADE(rnh) rw_try_upgrade(&(rnh)->rnh_lock) #define RADIX_NODE_HEAD_DESTROY(rnh) rw_destroy(&(rnh)->rnh_lock) #define RADIX_NODE_HEAD_LOCK_ASSERT(rnh) rw_assert(&(rnh)->rnh_lock, RA_LOCKED) #define RADIX_NODE_HEAD_WLOCK_ASSERT(rnh) rw_assert(&(rnh)->rnh_lock, RA_WLOCKED) #endif /* _KERNEL */ int rn_inithead(void **, int); int rn_detachhead(void **); int rn_refines(void *, void *); struct radix_node *rn_addroute (void *, void *, struct radix_head *, struct radix_node [2]); struct radix_node *rn_delete(void *, void *, struct radix_head *); struct radix_node *rn_lookup (void *v_arg, void *m_arg, struct radix_head *head); struct radix_node *rn_match(void *, struct radix_head *); int rn_walktree_from(struct radix_head *h, void *a, void *m, walktree_f_t *f, void *w); int rn_walktree(struct radix_head *, walktree_f_t *, void *); #endif /* _RADIX_H_ */ Index: projects/routing/sys/net/radix_mpath.c =================================================================== --- projects/routing/sys/net/radix_mpath.c (revision 287073) +++ projects/routing/sys/net/radix_mpath.c (revision 287074) @@ -1,295 +1,293 @@ /* $KAME: radix_mpath.c,v 1.17 2004/11/08 10:29:39 itojun Exp $ */ /* * Copyright (C) 2001 WIDE Project. * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * 3. Neither the name of the project nor the names of its contributors * may be used to endorse or promote products derived from this software * without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE PROJECT AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE PROJECT OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * THE AUTHORS DO NOT GUARANTEE THAT THIS SOFTWARE DOES NOT INFRINGE * ANY OTHERS' INTELLECTUAL PROPERTIES. IN NO EVENT SHALL THE AUTHORS * BE LIABLE FOR ANY INFRINGEMENT OF ANY OTHERS' INTELLECTUAL * PROPERTIES. */ #include __FBSDID("$FreeBSD$"); #include "opt_inet.h" #include "opt_inet6.h" #include #include #include #include #include #include #include #include #include #include #include #include /* * give some jitter to hash, to avoid synchronization between routers */ static uint32_t hashjitter; int rn_mpath_capable(struct radix_node_head *rnh) { - return rnh->rnh_multipath; + return 0; } struct radix_node * rn_mpath_next(struct radix_node *rn) { struct radix_node *next; if (!rn->rn_dupedkey) return NULL; next = rn->rn_dupedkey; if (rn->rn_mask == next->rn_mask) return next; else return NULL; } uint32_t rn_mpath_count(struct radix_node *rn) { uint32_t i = 0; struct rtentry *rt; while (rn != NULL) { rt = (struct rtentry *)rn; i += rt->rt_weight; rn = rn_mpath_next(rn); } return (i); } struct rtentry * rt_mpath_matchgate(struct rtentry *rt, struct sockaddr *gate) { struct radix_node *rn; if (!gate || !rt->rt_gateway) return NULL; /* beyond here, we use rn as the master copy */ rn = (struct radix_node *)rt; do { rt = (struct rtentry *)rn; /* * we are removing an address alias that has * the same prefix as another address * we need to compare the interface address because * rt_gateway is a special sockadd_dl structure */ if (rt->rt_gateway->sa_family == AF_LINK) { if (!memcmp(rt->rt_ifa->ifa_addr, gate, gate->sa_len)) break; } /* * Check for other options: * 1) Routes with 'real' IPv4/IPv6 gateway * 2) Loopback host routes (another AF_LINK/sockadd_dl check) * */ if (rt->rt_gateway->sa_len == gate->sa_len && !memcmp(rt->rt_gateway, gate, gate->sa_len)) break; } while ((rn = rn_mpath_next(rn)) != NULL); return (struct rtentry *)rn; } /* * go through the chain and unlink "rt" from the list * the caller will free "rt" */ int rt_mpath_deldup(struct rtentry *headrt, struct rtentry *rt) { struct radix_node *t, *tt; if (!headrt || !rt) return (0); t = (struct radix_node *)headrt; tt = rn_mpath_next(t); while (tt) { if (tt == (struct radix_node *)rt) { t->rn_dupedkey = tt->rn_dupedkey; tt->rn_dupedkey = NULL; tt->rn_flags &= ~RNF_ACTIVE; tt[1].rn_flags &= ~RNF_ACTIVE; return (1); } t = tt; tt = rn_mpath_next((struct radix_node *)t); } return (0); } /* * check if we have the same key/mask/gateway on the table already. * Assume @rt rt_key host bits are cleared according to @netmask */ int rt_mpath_conflict(struct radix_node_head *rnh, struct rtentry *rt, struct sockaddr *netmask) { struct radix_node *rn, *rn1; struct rtentry *rt1; rn = (struct radix_node *)rt; rn1 = rnh->rnh_lookup(rt_key(rt), netmask, &rnh->rh); if (!rn1 || rn1->rn_flags & RNF_ROOT) return (0); /* key/mask are the same. compare gateway for all multipaths */ do { rt1 = (struct rtentry *)rn1; /* sanity: no use in comparing the same thing */ if (rn1 == rn) continue; if (rt1->rt_gateway->sa_family == AF_LINK) { if (rt1->rt_ifa->ifa_addr->sa_len != rt->rt_ifa->ifa_addr->sa_len || bcmp(rt1->rt_ifa->ifa_addr, rt->rt_ifa->ifa_addr, rt1->rt_ifa->ifa_addr->sa_len)) continue; } else { if (rt1->rt_gateway->sa_len != rt->rt_gateway->sa_len || bcmp(rt1->rt_gateway, rt->rt_gateway, rt1->rt_gateway->sa_len)) continue; } /* all key/mask/gateway are the same. conflicting entry. */ return (EEXIST); } while ((rn1 = rn_mpath_next(rn1)) != NULL); return (0); } void rtalloc_mpath_fib(struct route *ro, uint32_t hash, u_int fibnum) { struct radix_node *rn0, *rn; u_int32_t n; struct rtentry *rt; int64_t weight; /* * XXX we don't attempt to lookup cached route again; what should * be done for sendto(3) case? */ if (ro->ro_rt && ro->ro_rt->rt_ifp && (ro->ro_rt->rt_flags & RTF_UP) && RT_LINK_IS_UP(ro->ro_rt->rt_ifp)) return; ro->ro_rt = rtalloc1_fib(&ro->ro_dst, 1, 0, fibnum); /* if the route does not exist or it is not multipath, don't care */ if (ro->ro_rt == NULL) return; if (rn_mpath_next((struct radix_node *)ro->ro_rt) == NULL) { RT_UNLOCK(ro->ro_rt); return; } /* beyond here, we use rn as the master copy */ rn0 = rn = (struct radix_node *)ro->ro_rt; n = rn_mpath_count(rn0); /* gw selection by Modulo-N Hash (RFC2991) XXX need improvement? */ hash += hashjitter; hash %= n; for (weight = abs((int32_t)hash), rt = ro->ro_rt; weight >= rt->rt_weight && rn; weight -= rt->rt_weight) { /* stay within the multipath routes */ if (rn->rn_dupedkey && rn->rn_mask != rn->rn_dupedkey->rn_mask) break; rn = rn->rn_dupedkey; rt = (struct rtentry *)rn; } /* XXX try filling rt_gwroute and avoid unreachable gw */ /* gw selection has failed - there must be only zero weight routes */ if (!rn) { RT_UNLOCK(ro->ro_rt); ro->ro_rt = NULL; return; } if (ro->ro_rt != rt) { RTFREE_LOCKED(ro->ro_rt); ro->ro_rt = (struct rtentry *)rn; RT_LOCK(ro->ro_rt); RT_ADDREF(ro->ro_rt); } RT_UNLOCK(ro->ro_rt); } extern int in6_inithead(void **head, int off); extern int in_inithead(void **head, int off); #ifdef INET int rn4_mpath_inithead(void **head, int off) { struct radix_node_head *rnh; hashjitter = arc4random(); if (in_inithead(head, off) == 1) { rnh = (struct radix_node_head *)*head; - rnh->rnh_multipath = 1; return 1; } else return 0; } #endif #ifdef INET6 int rn6_mpath_inithead(void **head, int off) { struct radix_node_head *rnh; hashjitter = arc4random(); if (in6_inithead(head, off) == 1) { rnh = (struct radix_node_head *)*head; - rnh->rnh_multipath = 1; return 1; } else return 0; } #endif