Attachment #129493 for bug #173477





	RADIX_NODE_HEAD_LOCK(ipo->ipo_head);
	ipo->ipo_head->rnh_deladdr(&ipe->ipn_addr, &ipe->ipn_mask,
				   ipo->ipo_head, NULL);
	RADIX_NODE_HEAD_UNLOCK(ipo->ipo_head);

	ip_pool_node_deref(ipe);

	RADIX_NODE_HEAD_LOCK(ipo->ipo_head);
	while ((n = ipo->ipo_list) != NULL) {
		ipo->ipo_head->rnh_deladdr(&n->ipn_addr, &n->ipn_mask,
					   ipo->ipo_head, NULL);

		*n->ipn_pnext = n->ipn_next;
		if (n->ipn_next)

	struct radix_node_head *rnh = p;
	struct radix_node *d;

	d = rnh->rnh_deladdr(n->rn_key, NULL, rnh, NULL);
	if (d != NULL) {
		FreeS(d, max_keylen + 2 * sizeof (*d));
	}

Lines 228-234 Link Here

(-)/router/usr/src/sys/kern/vfs_export.c (-1 / +1 lines)
228	struct radix_node_head rnh = (struct radix_node_head ) w;	228	struct radix_node_head rnh = (struct radix_node_head ) w;
229	struct ucred *cred;	229	struct ucred *cred;
230		230
231	(*rnh->rnh_deladdr) (rn->rn_key, rn->rn_mask, rnh);	231	(*rnh->rnh_deladdr) (rn->rn_key, rn->rn_mask, rnh, NULL);
232	cred = ((struct netcred *)rn)->netc_anon;	232	cred = ((struct netcred *)rn)->netc_anon;
233	if (cred != NULL)	233	if (cred != NULL)
234	crfree(cred);	234	crfree(cred);

Lines 70-75 Link Here

(-)/router/usr/src/sys/net/if.c (-1 / +16 lines)
70	#include <net/if_types.h>	70	#include <net/if_types.h>
71	#include <net/if_var.h>	71	#include <net/if_var.h>
72	#include <net/radix.h>	72	#include <net/radix.h>
		73	#include "opt_mpath.h"
73	#include <net/route.h>	74	#include <net/route.h>
74	#include <net/vnet.h>	75	#include <net/vnet.h>
75		76
Lines 1485-1490 Link Here
1485	{	1486	{
1486	int error = 0;	1487	int error = 0;
1487	struct rt_addrinfo info;	1488	struct rt_addrinfo info;
		1489	#ifdef RADIX_MPATH
		1490	struct ifaddr *new_ifa;
		1491	#else
1488	struct sockaddr_dl null_sdl;	1492	struct sockaddr_dl null_sdl;
1489		1493
1490	bzero(&null_sdl, sizeof(null_sdl));	1494	bzero(&null_sdl, sizeof(null_sdl));
Lines 1492-1505 Link Here
1492	null_sdl.sdl_family = AF_LINK;	1496	null_sdl.sdl_family = AF_LINK;
1493	null_sdl.sdl_type = ifa->ifa_ifp->if_type;	1497	null_sdl.sdl_type = ifa->ifa_ifp->if_type;
1494	null_sdl.sdl_index = ifa->ifa_ifp->if_index;	1498	null_sdl.sdl_index = ifa->ifa_ifp->if_index;
		1499	#endif
1495	bzero(&info, sizeof(info));	1500	bzero(&info, sizeof(info));
1496	info.rti_flags = ifa->ifa_flags \| RTF_HOST \| RTF_STATIC;	1501	info.rti_flags = ifa->ifa_flags \| RTF_HOST \| RTF_STATIC;
1497	info.rti_info[RTAX_DST] = ia;	1502	info.rti_info[RTAX_DST] = ia;
		1503	#ifdef RADIX_MPATH
		1504	info.rti_ifp = V_loif;
		1505
		1506	/* link_rtrequest modifies ifa - do this also */
		1507	new_ifa = ifaof_ifpforaddr( ia, V_loif);
		1508
		1509	/* rt_mpath_matchgate matches ifa_addr and not gateway */
		1510	info.rti_info[RTAX_GATEWAY] = new_ifa->ifa_addr;
		1511	#else
1498	info.rti_info[RTAX_GATEWAY] = (struct sockaddr *)&null_sdl;	1512	info.rti_info[RTAX_GATEWAY] = (struct sockaddr *)&null_sdl;
		1513	#endif
1499	error = rtrequest1_fib(RTM_DELETE, &info, NULL, 0);	1514	error = rtrequest1_fib(RTM_DELETE, &info, NULL, 0);
1500		1515
1501	if (error != 0)	1516	if (error != 0)
1502	log(LOG_INFO, "ifa_del_loopback_route: deletion failed\n");	1517	log(LOG_INFO, "ifa_del_loopback_route: deletion failed err: %d\n", error);
1503		1518
1504	return (error);	1519	return (error);
1505	}	1520	}




	 * lot of confusion.
	 */
	if (t->rn_flags & RNF_ROOT)
	        t = t->rn_dupedkey;
	return t;
on1:
	test = (*cp ^ *cp2) & 0xff; /* find first bit that differs */

		x = t->rn_right;
	/* Promote general routes from below */
	if (x->rn_bit < 0) {
	        struct	radix_node *xx = NULL;
	        for (mp = &t->rn_mklist; x; xx = x, x = x->rn_dupedkey) {
	                if (xx && xx->rn_mklist && xx->rn_mask == x->rn_mask &&
	                    x->rn_mklist == 0) {
	                        /* multipath route, bump refcount on first mklist */
	                        x->rn_mklist = xx->rn_mklist;
	                        x->rn_mklist->rm_refs++;
                        }
                        if (x->rn_mask && (x->rn_bit >= b_leaf) && x->rn_mklist == 0) {
			        *mp = m = rn_new_radix_mask(x, 0);
			        if (m)
				        mp = &m->rm_mklist;
                        }
                }
	} else if (x->rn_mklist) {
		/*
		 * Skip over masks whose index is > that of new node

			break;
		if (m->rm_flags & RNF_NORMAL) {
			mmask = m->rm_leaf->rn_mask;
			if (keyduplicated) {
			        if (m->rm_leaf->rn_parent == tt)
			                /* new route is better */
                                        m->rm_leaf = tt;
#ifdef DIAGNOSTIC
                                else {
                                        for (t = m->rm_leaf; t;
                                            t = t->rn_dupedkey)
                                                if (t == tt)
                                                        break;
                                        if (t == NULL) {
                                                log(LOG_ERR, "Non-unique "
                                                    "normal route on dupedkey, "
                                                    "mask not entered\n");
                                                return tt;
                                        }
                                }
#endif
                                m->rm_refs++;
                                tt->rn_mklist = m;
                                return tt;
                        } else if (tt->rn_flags & RNF_NORMAL) {
			    log(LOG_ERR,
			        "Non-unique normal route, mask not entered\n");
#endif
				return tt;
			}
		} else

}

struct radix_node *
rn_delete(v_arg, netmask_arg, head, rn)
	void *v_arg, *netmask_arg;
	struct radix_node_head *head;
	struct radix_node *rn;
{
	register struct radix_node *t, *p, *x, *tt;
	struct radix_mask *m, *saved_m, **mp;

			if ((tt = tt->rn_dupedkey) == 0)
				return (0);
	}
#ifdef RADIX_MPATH
        if (rn) {
                while (tt != rn)
                        if ((tt = tt->rn_dupedkey) == 0)
                                return (0);
        }
#endif
	if (tt->rn_mask == 0 || (saved_m = m = tt->rn_mklist) == 0)
		goto on1;
	if (tt->rn_flags & RNF_NORMAL) {
		if (m->rm_leaf != tt && m->rm_refs == 0) {
		        log(LOG_ERR, "rn_delete: inconsistent normal "
		            "annotation\n");
                        return (0);
                }
                if (m->rm_leaf != tt) {
                        if (--m->rm_refs >= 0)
                                goto on1;
                }
                /* tt is currently the head of the possible multipath chain */
                if (m->rm_refs > 0) {
                        if (tt->rn_dupedkey == NULL ||
                            tt->rn_dupedkey->rn_mklist != m) {
                                log(LOG_ERR, "rn_delete: inconsistent "
                                    "dupedkey list\n");
                                return (0);
                        }
                        m->rm_leaf = tt->rn_dupedkey;
                        --m->rm_refs;
                        goto on1;
                }
		/* else tt is last and only route */
	} else {
		if (m->rm_mask != tt->rn_mask)
			log(LOG_ERR, "rn_delete: inconsistent annotation\n");
			goto on1;
		}
		if (--m->rm_refs >= 0)
			goto on1;
	}

			else
				t->rn_right = x;
		} else {
		        x = saved_tt;
		        t->rn_dupedkey = tt->rn_dupedkey;
		        if (tt->rn_dupedkey)
		                tt->rn_dupedkey->rn_parent = t;
				p->rn_dupedkey = tt->rn_dupedkey;
				if (tt->rn_dupedkey)		/* parent */
					tt->rn_dupedkey->rn_parent = p;
								/* parent */
			} else log(LOG_ERR, "rn_delete: couldn't find us\n");
		}
		t = tt + 1;
		if  (t->rn_flags & RNF_ACTIVE) {

				if (m == x->rn_mklist) {
					struct radix_mask *mm = m->rm_mklist;
					x->rn_mklist = 0;
					if (--(m->rm_refs) < 0) {
						MKFree(m);
                                        } else if (m->rm_flags & RNF_NORMAL) {
                                                /*
                                                 * don't progress because this
                                                 * a multipath route. Next
                                                 * route will use the same m.
                                                 */
                                                mm = m;
                                        }
					m = mm;
				}
			if (m)

			rn = rn->rn_left;
		next = rn;
		/* Process leaves */
		while ((rn = base) != NULL) {
			base = rn->rn_dupedkey;
			if (!(rn->rn_flags & RNF_ROOT)
			    && (error = (*f)(rn, w)))




		(void *v, void *mask,
		     struct radix_node_head *head, struct radix_node nodes[]);
	struct	radix_node *(*rnh_deladdr)	/* remove based on sockaddr */
		(void *v, void *mask, struct radix_node_head *head,
                     struct radix_node *rn);
	struct	radix_node *(*rnh_delpkt)	/* remove based on packet hdr */
		(void *v, void *mask, struct radix_node_head *head);
	struct	radix_node *(*rnh_matchaddr)	/* locate based on sockaddr */

	 *rn_addmask(void *, int, int),
	 *rn_addroute (void *, void *, struct radix_node_head *,
			struct radix_node [2]),
	 *rn_delete(void *, void *, struct radix_node_head *,
	                 struct radix_node *),
	 *rn_lookup (void *v_arg, void *m_arg,
		        struct radix_node_head *head),
	 *rn_match(void *, struct radix_node_head *);




		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_rmx.rmx_weight;
		rn = rn_mpath_next(rn);
	}
	return (i);
}

struct rtentry *
rt_mpath_matchgate(struct rtentry *rt, struct sockaddr *gate)
{

	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.
 */

}

void
rtalloc_mpath_fib(struct route *ro, uint32_t hash, u_int fibnum) {
	rtalloc_mpath_fib_flags( ro, hash, fibnum, 0);
}

/*
 * flag RTF_GATEWAY returns only interface routes,
 * only one interface-route is possible
 */ 
void
rtalloc_mpath_fib_flags(struct route *ro, uint32_t hash, u_int fibnum, int flags)
{
	struct radix_node *rn0, *rn;
	u_int32_t n = 0;
	struct rtentry *rt;
	int64_t lowest_weight;

	/*
	 * XXX we don't attempt to lookup cached route again; what should

	 */
	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) {
		if (flags & RTF_GATEWAY)
			return;
		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);

	/* find count of lowest weight route */
	for (rt = ro->ro_rt, lowest_weight = 9223372036854775807; rn != NULL;){
		if( rt->rt_flags & RTF_UP) {
			if ((flags & RTF_GATEWAY) && 
			    (!(rt->rt_flags & RTF_GATEWAY)) && 
			    (!(rt->rt_flags & RTF_HOST)) )
				goto end;   /* only 1 interface route possible! */
			if( lowest_weight > rt->rt_rmx.rmx_weight) {
				lowest_weight = rt->rt_rmx.rmx_weight;
				n = 1;
			} else if( lowest_weight == rt->rt_rmx.rmx_weight)
				n++;
		}
		if (rn->rn_dupedkey && rn->rn_mask != rn->rn_dupedkey->rn_mask)
			break;
		rn = rn->rn_dupedkey;
		rt = (struct rtentry *)rn;
	}
	/* select now one of the lowest weight routes */
	/* gw selection by Modulo-N Hash (RFC2991) */
	hash += hashjitter;
	hash %= n;
	for ( rt = ro->ro_rt, rn = rn0, n = 0; rn != NULL; ) {
		if( rt->rt_flags & RTF_UP) {
			if ( rt->rt_rmx.rmx_weight == lowest_weight) {
				if (n == hash)
					break;
				n++;
			}
		}
		if (rn->rn_dupedkey && rn->rn_mask != rn->rn_dupedkey->rn_mask)
			break;
		rn = rn->rn_dupedkey;

	/* XXX try filling rt_gwroute and avoid unreachable gw  */

	/* gw selection has failed - there must be only zero weight routes */
	if (!rn || (flags & RTF_GATEWAY)) {
		RT_UNLOCK(ro->ro_rt);
		ro->ro_rt = NULL;
		return;
	}

end:		
	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);

	}
	if (!(flags & RTF_GATEWAY))
		RT_UNLOCK(ro->ro_rt);
}

extern int	in6_inithead(void **head, int off);




struct sockaddr;
int	rn_mpath_capable(struct radix_node_head *);
struct radix_node *rn_mpath_next(struct radix_node *);
u_int32_t rn_mpath_count(struct radix_node *);
struct rtentry *rt_mpath_matchgate(struct rtentry *, struct sockaddr *);
int rt_mpath_conflict(struct radix_node_head *, struct rtentry *,
    struct sockaddr *);
void rtalloc_mpath_fib(struct route *, u_int32_t, u_int);
#define rtalloc_mpath(_route, _hash) rtalloc_mpath_fib((_route), (_hash), 0)
void rtalloc_mpath_fib_flags(struct route *, u_int32_t, u_int, int);
struct radix_node *rn_mpath_lookup(void *, void *,
    struct radix_node_head *);
int rt_mpath_deldup(struct rtentry *, struct rtentry *);




	 * Remove the item from the tree; it should be there,
	 * but when callers invoke us blindly it may not (sigh).
	 */
	rn = rnh->rnh_deladdr(rt_key(rt), rt_mask(rt), rnh, NULL);
	if (rn == NULL) {
		error = ESRCH;
		goto bad;

	return (error);
}

#ifdef RADIX_MPATH
static int
rn_mpath_update(int req, struct rt_addrinfo *info,
    struct radix_node_head *rnh, struct rtentry **ret_nrt)
{
	/*
	 * if we got multipath routes, we require users to specify
	 * a matching RTAX_GATEWAY.
	 */
	struct rtentry *rt, *rto = NULL;
	register struct radix_node *rn;
	int error = 0;

	rn = rnh->rnh_matchaddr(dst, rnh);
	if (rn == NULL)
		return (ESRCH);
	rto = rt = RNTORT(rn);
	rt = rt_mpath_matchgate(rt, gateway);
	if (rt == NULL)
		return (ESRCH);
	/*
	 * this is the first entry in the chain
	 */
	if (rto == rt) {
		rn = rn_mpath_next((struct radix_node *)rt);
		/*
		 * there is another entry, now it's active
		 */
		if (rn) {
			rto = RNTORT(rn);
			RT_LOCK(rto);
			rto->rt_flags |= RTF_UP;
			RT_UNLOCK(rto);
		} else if (rt->rt_flags & RTF_GATEWAY) {
			/*
			 * For gateway routes, we need to 
			 * make sure that we we are deleting
			 * the correct gateway. 
			 * rt_mpath_matchgate() does not 
			 * check the case when there is only
			 * one route in the chain.  
			 */
			if (gateway &&
			    (rt->rt_gateway->sa_len != gateway->sa_len ||
				memcmp(rt->rt_gateway, gateway, gateway->sa_len)))
				error = ESRCH;
			else {
				/*
				 * remove from tree before returning it
				 * to the caller
				 */
				rn = rnh->rnh_deladdr(dst, netmask, rnh);
				KASSERT(rt == RNTORT(rn), ("radix node disappeared"));
				goto gwdelete;
			}
			
		}
		/*
		 * use the normal delete code to remove
		 * the first entry
		 */
		if (req != RTM_DELETE) 
			goto nondelete;

		error = ENOENT;
		goto done;
	}
		
	/*
	 * if the entry is 2nd and on up
	 */
	if ((req == RTM_DELETE) && !rt_mpath_deldup(rto, rt))
		panic ("rtrequest1: rt_mpath_deldup");
gwdelete:
	RT_LOCK(rt);
	RT_ADDREF(rt);
	if (req == RTM_DELETE) {
		rt->rt_flags &= ~RTF_UP;
		/*
		 * One more rtentry floating around that is not
		 * linked to the routing table. rttrash will be decremented
		 * when RTFREE(rt) is eventually called.
		 */
		V_rttrash++;
	}
	
nondelete:
	if (req != RTM_DELETE)
		panic("unrecognized request %d", req);
	

	/*
	 * If the caller wants it, then it can have it,
	 * but it's up to it to free the rtentry as we won't be
	 * doing it.
	 */
	if (ret_nrt) {
		*ret_nrt = rt;
		RT_UNLOCK(rt);
	} else
		RTFREE_LOCKED(rt);
done:
	return (error);
}
#endif

int
rtrequest1_fib(int req, struct rt_addrinfo *info, struct rtentry **ret_nrt,
				u_int fibnum)

			rt_maskedcopy(dst, (struct sockaddr *)&mdst, netmask);
			dst = (struct sockaddr *)&mdst;
		}
		if ((rn = rnh->rnh_lookup(dst, netmask, rnh)) == NULL)
		        senderr(ESRCH);
                rt = RNTORT(rn);
#ifdef RADIX_MPATH
                /*
                 * if we got multipath routes, we require users to specify
                 * a matching RTAX_GATEWAY.
                 */
		if (rn_mpath_capable(rnh)) {
		        rt = rt_mpath_matchgate( rt, gateway);
		        rn = (struct radix_node *)rt;
		        if (!rt)
		                senderr(ESRCH);
			 */
			if (error != ENOENT)
				goto bad;
			error = 0;
		}
#endif
		/*
		 * Remove the item from the tree and return it.
		 * Complain if it is not there and do no more processing.
		 */
		rn = rnh->rnh_deladdr(dst, netmask, rnh, rn);
		if (rn == NULL)
			senderr(ESRCH);
		if (rn->rn_flags & (RNF_ACTIVE | RNF_ROOT))

		rt->rt_ifa = ifa;
		rt->rt_ifp = ifa->ifa_ifp;
		rt->rt_rmx.rmx_weight = 1;
		
#ifdef RADIX_MPATH
		/* do not permit exactly the same dst/mask/gw pair */
		if (rn_mpath_capable(rnh) &&

	 */
	if (rt->rt_gateway == NULL || glen > SA_SIZE(rt->rt_gateway)) {
		caddr_t new;
		
		R_Malloc(new, caddr_t, dlen + glen);
		if (new == NULL)
			return ENOBUFS;

			RADIX_NODE_HEAD_LOCK(rnh);
#ifdef RADIX_MPATH
			if (rn_mpath_capable(rnh)) {
				rn = rnh->rnh_lookup(dst, netmask, rnh);
				if (rn == NULL)
				if (rn == NULL) 
					error = ESRCH;
				else {
					rt = RNTORT(rn);

					    ifa->ifa_addr);
					if (!rt) 
						error = ESRCH;
                                        rn = (struct radix_node *)rt;
				}
			}
			else

Lines 91-100 Link Here

(-)/router/usr/src/sys/netatalk/at_rmx.c (-2 / +2 lines)
91	}	91	}
92		92
93	static struct radix_node *	93	static struct radix_node *
94	at_delroute(void v_arg, void netmask_arg, struct radix_node_head *head)	94	at_delroute(void v_arg, void netmask_arg, struct radix_node_head head, struct radix_node rn)
95	{	95	{
96		96
97	return (rn_delete(v_arg, netmask_arg, head));	97	return (rn_delete(v_arg, netmask_arg, head, rn));
98	}	98	}
99		99
100	/*	100	/*

Lines 1397-1409 Link Here

(-)/router/usr/src/sys/netinet/in.c (-1 / +11 lines)
1397	in_lltable_rtcheck(struct ifnet ifp, u_int flags, const struct sockaddr l3addr)	1397	in_lltable_rtcheck(struct ifnet ifp, u_int flags, const struct sockaddr l3addr)
1398	{	1398	{
1399	struct rtentry *rt;	1399	struct rtentry *rt;
		1400	#ifdef RADIX_MPATH
		1401	struct route ro;
		1402	#endif
1400		1403
1401	KASSERT(l3addr->sa_family == AF_INET,	1404	KASSERT(l3addr->sa_family == AF_INET,
1402	("sin_family %d", l3addr->sa_family));	1405	("sin_family %d", l3addr->sa_family));
1403		1406
		1407	#ifdef RADIX_MPATH
		1408	/* ensure to select a interface route */
		1409	bzero( &ro, sizeof(ro));
		1410	bcopy( __DECONST(struct sockaddr *, l3addr), &ro.ro_dst, sizeof(struct sockaddr));
		1411	rtalloc_mpath_fib_flags( (struct route *)&ro, 0, RT_DEFAULT_FIB, RTF_GATEWAY);
		1412	rt = ro.ro_rt;
		1413	#else
1404	/* XXX rtalloc1 should take a const param */	1414	/* XXX rtalloc1 should take a const param */
1405	rt = rtalloc1(__DECONST(struct sockaddr *, l3addr), 0, 0);	1415	rt = rtalloc1(__DECONST(struct sockaddr *, l3addr), 0, 0);
1406		1416	#endif
1407	if (rt == NULL)	1417	if (rt == NULL)
1408	return (EINVAL);	1418	return (EINVAL);
1409		1419

Lines 78-83 Link Here

(-)/router/usr/src/sys/netinet/ip_fastfwd.c (+20 lines)
78		78
79	#include "opt_ipfw.h"	79	#include "opt_ipfw.h"
80	#include "opt_ipstealth.h"	80	#include "opt_ipstealth.h"
		81	#include "opt_mpath.h"
81		82
82	#include <sys/param.h>	83	#include <sys/param.h>
83	#include <sys/systm.h>	84	#include <sys/systm.h>
Lines 113-119 Link Here
113	&VNET_NAME(ipfastforward_active), 0, "Enable fast IP forwarding");	115	&VNET_NAME(ipfastforward_active), 0, "Enable fast IP forwarding");
114		116
115	static struct sockaddr_in *	117	static struct sockaddr_in *
		118	#ifdef RADIX_MPATH
		119	ip_findroute(struct route ro, uint32_t hash, struct in_addr dest, struct mbuf m)
		120	#else
116	ip_findroute(struct route ro, struct in_addr dest, struct mbuf m)	121	ip_findroute(struct route ro, struct in_addr dest, struct mbuf m)
		122	#endif
117	{	123	{
118	struct sockaddr_in *dst;	124	struct sockaddr_in *dst;
119	struct rtentry *rt;	125	struct rtentry *rt;
Lines 126-132 Link Here
126	dst->sin_family = AF_INET;	132	dst->sin_family = AF_INET;
127	dst->sin_len = sizeof(*dst);	133	dst->sin_len = sizeof(*dst);
128	dst->sin_addr.s_addr = dest.s_addr;	134	dst->sin_addr.s_addr = dest.s_addr;
		135	#ifdef RADIX_MPATH
		136	rtalloc_mpath_fib(ro, hash, M_GETFIB(m));
		137	#else
129	in_rtalloc_ign(ro, 0, M_GETFIB(m));	138	in_rtalloc_ign(ro, 0, M_GETFIB(m));
		139	#endif
130		140
131	/*	141	/*
132	* Route there and interface still up?	142	* Route there and interface still up?
Lines 420-426 Link Here
420	/*	440	/*
421	* Find route to destination.	441	* Find route to destination.
422	*/	442	*/
		443	#ifdef RADIX_MPATH
		444	if ((dst = ip_findroute(&ro, ntohl(ip->ip_src.s_addr ^ ip->ip_dst.s_addr),
		445	dest, m)) == NULL)
		446	#else
423	if ((dst = ip_findroute(&ro, dest, m)) == NULL)	447	if ((dst = ip_findroute(&ro, dest, m)) == NULL)
		448	#endif
424	return NULL; /* icmp unreach already sent */	449	return NULL; /* icmp unreach already sent */
425	ifp = ro.ro_rt->rt_ifp;	450	ifp = ro.ro_rt->rt_ifp;
426		451
Lines 491-497 Link Here
491	}	516	}
492	#endif /* IPFIREWALL_FORWARD */	517	#endif /* IPFIREWALL_FORWARD */
493	RTFREE(ro.ro_rt);	518	RTFREE(ro.ro_rt);
		519	#ifdef RADIX_MPATH
		520	if ((dst = ip_findroute(&ro,
		521	ntohl(ip->ip_src.s_addr ^ ip->ip_dst.s_addr), dest, m))
		522	== NULL)
		523	#else
494	if ((dst = ip_findroute(&ro, dest, m)) == NULL)	524	if ((dst = ip_findroute(&ro, dest, m)) == NULL)
		525	#endif
495	return NULL; /* icmp unreach already sent */	526	return NULL; /* icmp unreach already sent */
496	ifp = ro.ro_rt->rt_ifp;	527	ifp = ro.ro_rt->rt_ifp;
497	}	528	}

Lines 379-385 Link Here

(-)/router/usr/src/sys/netinet/ipfw/ip_fw_table.c (-2 / +2 lines)
379	return (EINVAL);	379	return (EINVAL);
380	}	380	}
381		381
382	ent = (struct table_entry *)rnh->rnh_deladdr(sa_ptr, mask_ptr, rnh);	382	ent = (struct table_entry *)rnh->rnh_deladdr(sa_ptr, mask_ptr, rnh, NULL);
383	IPFW_WUNLOCK(ch);	383	IPFW_WUNLOCK(ch);
384		384
385	if (ent == NULL)	385	if (ent == NULL)
Lines 396-402 Link Here
396	struct table_entry *ent;	396	struct table_entry *ent;
397		397
398	ent = (struct table_entry *)	398	ent = (struct table_entry *)
399	rnh->rnh_deladdr(rn->rn_key, rn->rn_mask, rnh);	399	rnh->rnh_deladdr(rn->rn_key, rn->rn_mask, rnh, NULL);
400	if (ent != NULL)	400	if (ent != NULL)
401	free(ent, M_IPFW_TBL);	401	free(ent, M_IPFW_TBL);
402	return (0);	402	return (0);

Return to bug 173477

Lines 620-626 Link Here

(-)/router/usr/src/sys/contrib/ipfilter/netinet/ip_pool.c (-3 / +3 lines)
620		620
621	RADIX_NODE_HEAD_LOCK(ipo->ipo_head);	621	RADIX_NODE_HEAD_LOCK(ipo->ipo_head);
622	ipo->ipo_head->rnh_deladdr(&ipe->ipn_addr, &ipe->ipn_mask,	622	ipo->ipo_head->rnh_deladdr(&ipe->ipn_addr, &ipe->ipn_mask,
623	ipo->ipo_head);	623	ipo->ipo_head, NULL);
624	RADIX_NODE_HEAD_UNLOCK(ipo->ipo_head);	624	RADIX_NODE_HEAD_UNLOCK(ipo->ipo_head);
625		625
626	ip_pool_node_deref(ipe);	626	ip_pool_node_deref(ipe);
Lines 751-757 Link Here
751	RADIX_NODE_HEAD_LOCK(ipo->ipo_head);	751	RADIX_NODE_HEAD_LOCK(ipo->ipo_head);
752	while ((n = ipo->ipo_list) != NULL) {	752	while ((n = ipo->ipo_list) != NULL) {
753	ipo->ipo_head->rnh_deladdr(&n->ipn_addr, &n->ipn_mask,	753	ipo->ipo_head->rnh_deladdr(&n->ipn_addr, &n->ipn_mask,
754	ipo->ipo_head);	754	ipo->ipo_head, NULL);
755		755
756	*n->ipn_pnext = n->ipn_next;	756	*n->ipn_pnext = n->ipn_next;
757	if (n->ipn_next)	757	if (n->ipn_next)
Lines 963-969 Link Here
963	struct radix_node_head *rnh = p;	963	struct radix_node_head *rnh = p;
964	struct radix_node *d;	964	struct radix_node *d;
965		965
966	d = rnh->rnh_deladdr(n->rn_key, NULL, rnh);	966	d = rnh->rnh_deladdr(n->rn_key, NULL, rnh, NULL);
967	if (d != NULL) {	967	if (d != NULL) {
968	FreeS(d, max_keylen + 2 * sizeof (*d));	968	FreeS(d, max_keylen + 2 * sizeof (*d));
969	}	969	}

Lines 312-318 Link Here

(-)/router/usr/src/sys/net/radix.c (-29 / +83 lines)
312	* lot of confusion.	312	* lot of confusion.
313	*/	313	*/
314	if (t->rn_flags & RNF_ROOT)	314	if (t->rn_flags & RNF_ROOT)
315	t = t->rn_dupedkey;	315	t = t->rn_dupedkey;
316	return t;	316	return t;
317	on1:	317	on1:
318	test = (cp ^ cp2) & 0xff; /* find first bit that differs */	318	test = (cp ^ cp2) & 0xff; /* find first bit that differs */
Lines 723-734 Link Here
723	x = t->rn_right;	723	x = t->rn_right;
724	/* Promote general routes from below */	724	/* Promote general routes from below */
725	if (x->rn_bit < 0) {	725	if (x->rn_bit < 0) {
726	for (mp = &t->rn_mklist; x; x = x->rn_dupedkey)	726	struct radix_node *xx = NULL;
727	if (x->rn_mask && (x->rn_bit >= b_leaf) && x->rn_mklist == 0) {	727	for (mp = &t->rn_mklist; x; xx = x, x = x->rn_dupedkey) {
728	*mp = m = rn_new_radix_mask(x, 0);	728	if (xx && xx->rn_mklist && xx->rn_mask == x->rn_mask &&
729	if (m)	729	x->rn_mklist == 0) {
730	mp = &m->rm_mklist;	730	/* multipath route, bump refcount on first mklist */
731	}	731	x->rn_mklist = xx->rn_mklist;
		732	x->rn_mklist->rm_refs++;
		733	}
		734	if (x->rn_mask && (x->rn_bit >= b_leaf) && x->rn_mklist == 0) {
		735	*mp = m = rn_new_radix_mask(x, 0);
		736	if (m)
		737	mp = &m->rm_mklist;
		738	}
		739	}
732	} else if (x->rn_mklist) {	740	} else if (x->rn_mklist) {
733	/*	741	/*
734	* Skip over masks whose index is > that of new node	742	* Skip over masks whose index is > that of new node
Lines 760-770 Link Here
760	break;	768	break;
761	if (m->rm_flags & RNF_NORMAL) {	769	if (m->rm_flags & RNF_NORMAL) {
762	mmask = m->rm_leaf->rn_mask;	770	mmask = m->rm_leaf->rn_mask;
763	if (tt->rn_flags & RNF_NORMAL) {	771	if (keyduplicated) {
764	#if !defined(RADIX_MPATH)	772	if (m->rm_leaf->rn_parent == tt)
		773	/* new route is better */
		774	m->rm_leaf = tt;
		775	#ifdef DIAGNOSTIC
		776	else {
		777	for (t = m->rm_leaf; t;
		778	t = t->rn_dupedkey)
		779	if (t == tt)
		780	break;
		781	if (t == NULL) {
		782	log(LOG_ERR, "Non-unique "
		783	"normal route on dupedkey, "
		784	"mask not entered\n");
		785	return tt;
		786	}
		787	}
		788	#endif
		789	m->rm_refs++;
		790	tt->rn_mklist = m;
		791	return tt;
		792	} else if (tt->rn_flags & RNF_NORMAL) {
765	log(LOG_ERR,	793	log(LOG_ERR,
766	"Non-unique normal route, mask not entered\n");	794	"Non-unique normal route, mask not entered\n");
767	#endif
768	return tt;	795	return tt;
769	}	796	}
770	} else	797	} else
Lines 783-791 Link Here
783	}	810	}
784		811
785	struct radix_node *	812	struct radix_node *
786	rn_delete(v_arg, netmask_arg, head)	813	rn_delete(v_arg, netmask_arg, head, rn)
787	void v_arg, netmask_arg;	814	void v_arg, netmask_arg;
788	struct radix_node_head *head;	815	struct radix_node_head *head;
		816	struct radix_node *rn;
789	{	817	{
790	register struct radix_node t, p, x, tt;	818	register struct radix_node t, p, x, tt;
791	struct radix_mask m, saved_m, **mp;	819	struct radix_mask m, saved_m, **mp;
Lines 815-832 Link Here
815	if ((tt = tt->rn_dupedkey) == 0)	843	if ((tt = tt->rn_dupedkey) == 0)
816	return (0);	844	return (0);
817	}	845	}
		846	#ifdef RADIX_MPATH
		847	if (rn) {
		848	while (tt != rn)
		849	if ((tt = tt->rn_dupedkey) == 0)
		850	return (0);
		851	}
		852	#endif
818	if (tt->rn_mask == 0 \|\| (saved_m = m = tt->rn_mklist) == 0)	853	if (tt->rn_mask == 0 \|\| (saved_m = m = tt->rn_mklist) == 0)
819	goto on1;	854	goto on1;
820	if (tt->rn_flags & RNF_NORMAL) {	855	if (tt->rn_flags & RNF_NORMAL) {
821	if (m->rm_leaf != tt \|\| m->rm_refs > 0) {	856	if (m->rm_leaf != tt && m->rm_refs == 0) {
822	log(LOG_ERR, "rn_delete: inconsistent annotation\n");	857	log(LOG_ERR, "rn_delete: inconsistent normal "
823	return 0; /* dangling ref could cause disaster */	858	"annotation\n");
824	}	859	return (0);
		860	}
		861	if (m->rm_leaf != tt) {
		862	if (--m->rm_refs >= 0)
		863	goto on1;
		864	}
		865	/* tt is currently the head of the possible multipath chain */
		866	if (m->rm_refs > 0) {
		867	if (tt->rn_dupedkey == NULL \|\|
		868	tt->rn_dupedkey->rn_mklist != m) {
		869	log(LOG_ERR, "rn_delete: inconsistent "
		870	"dupedkey list\n");
		871	return (0);
		872	}
		873	m->rm_leaf = tt->rn_dupedkey;
		874	--m->rm_refs;
		875	goto on1;
		876	}
		877	/* else tt is last and only route */
825	} else {	878	} else {
826	if (m->rm_mask != tt->rn_mask) {	879	if (m->rm_mask != tt->rn_mask)
827	log(LOG_ERR, "rn_delete: inconsistent annotation\n");
828	goto on1;	880	goto on1;
829	}
830	if (--m->rm_refs >= 0)	881	if (--m->rm_refs >= 0)
831	goto on1;	882	goto on1;
832	}	883	}
Lines 875-889 Link Here
875	else	926	else
876	t->rn_right = x;	927	t->rn_right = x;
877	} else {	928	} else {
878	/* find node in front of tt on the chain */	929	x = saved_tt;
879	for (x = p = saved_tt; p && p->rn_dupedkey != tt;)	930	t->rn_dupedkey = tt->rn_dupedkey;
880	p = p->rn_dupedkey;	931	if (tt->rn_dupedkey)
881	if (p) {	932	tt->rn_dupedkey->rn_parent = t;
882	p->rn_dupedkey = tt->rn_dupedkey;
883	if (tt->rn_dupedkey) /* parent */
884	tt->rn_dupedkey->rn_parent = p;
885	/* parent */
886	} else log(LOG_ERR, "rn_delete: couldn't find us\n");
887	}	933	}
888	t = tt + 1;	934	t = tt + 1;
889	if (t->rn_flags & RNF_ACTIVE) {	935	if (t->rn_flags & RNF_ACTIVE) {
Lines 931-938 Link Here
931	if (m == x->rn_mklist) {	977	if (m == x->rn_mklist) {
932	struct radix_mask *mm = m->rm_mklist;	978	struct radix_mask *mm = m->rm_mklist;
933	x->rn_mklist = 0;	979	x->rn_mklist = 0;
934	if (--(m->rm_refs) < 0)	980	if (--(m->rm_refs) < 0) {
935	MKFree(m);	981	MKFree(m);
		982	} else if (m->rm_flags & RNF_NORMAL) {
		983	/*
		984	* don't progress because this
		985	* a multipath route. Next
		986	* route will use the same m.
		987	*/
		988	mm = m;
		989	}
936	m = mm;	990	m = mm;
937	}	991	}
938	if (m)	992	if (m)
Lines 1107-1113 Link Here
1107	rn = rn->rn_left;	1161	rn = rn->rn_left;
1108	next = rn;	1162	next = rn;
1109	/* Process leaves */	1163	/* Process leaves */
1110	while ((rn = base)) {	1164	while ((rn = base) != NULL) {
1111	base = rn->rn_dupedkey;	1165	base = rn->rn_dupedkey;
1112	if (!(rn->rn_flags & RNF_ROOT)	1166	if (!(rn->rn_flags & RNF_ROOT)
1113	&& (error = (*f)(rn, w)))	1167	&& (error = (*f)(rn, w)))

Lines 904-910 Link Here

(-)/router/usr/src/sys/net/route.c (-121 / +18 lines)
904	* Remove the item from the tree; it should be there,	904	* Remove the item from the tree; it should be there,
905	* but when callers invoke us blindly it may not (sigh).	905	* but when callers invoke us blindly it may not (sigh).
906	*/	906	*/
907	rn = rnh->rnh_deladdr(rt_key(rt), rt_mask(rt), rnh);	907	rn = rnh->rnh_deladdr(rt_key(rt), rt_mask(rt), rnh, NULL);
908	if (rn == NULL) {	908	if (rn == NULL) {
909	error = ESRCH;	909	error = ESRCH;
910	goto bad;	910	goto bad;
Lines 942-1053 Link Here
942	return (error);	942	return (error);
943	}	943	}
944		944
945	#ifdef RADIX_MPATH
946	static int
947	rn_mpath_update(int req, struct rt_addrinfo *info,
948	struct radix_node_head rnh, struct rtentry *ret_nrt)
949	{
950	/*
951	* if we got multipath routes, we require users to specify
952	* a matching RTAX_GATEWAY.
953	*/
954	struct rtentry rt, rto = NULL;
955	register struct radix_node *rn;
956	int error = 0;
957
958	rn = rnh->rnh_matchaddr(dst, rnh);
959	if (rn == NULL)
960	return (ESRCH);
961	rto = rt = RNTORT(rn);
962	rt = rt_mpath_matchgate(rt, gateway);
963	if (rt == NULL)
964	return (ESRCH);
965	/*
966	* this is the first entry in the chain
967	*/
968	if (rto == rt) {
969	rn = rn_mpath_next((struct radix_node *)rt);
970	/*
971	* there is another entry, now it's active
972	*/
973	if (rn) {
974	rto = RNTORT(rn);
975	RT_LOCK(rto);
976	rto->rt_flags \|= RTF_UP;
977	RT_UNLOCK(rto);
978	} else if (rt->rt_flags & RTF_GATEWAY) {
979	/*
980	* For gateway routes, we need to
981	* make sure that we we are deleting
982	* the correct gateway.
983	* rt_mpath_matchgate() does not
984	* check the case when there is only
985	* one route in the chain.
986	*/
987	if (gateway &&
988	(rt->rt_gateway->sa_len != gateway->sa_len \|\|
989	memcmp(rt->rt_gateway, gateway, gateway->sa_len)))
990	error = ESRCH;
991	else {
992	/*
993	* remove from tree before returning it
994	* to the caller
995	*/
996	rn = rnh->rnh_deladdr(dst, netmask, rnh);
997	KASSERT(rt == RNTORT(rn), ("radix node disappeared"));
998	goto gwdelete;
999	}
1000
1001	}
1002	/*
1003	* use the normal delete code to remove
1004	* the first entry
1005	*/
1006	if (req != RTM_DELETE)
1007	goto nondelete;
1008
1009	error = ENOENT;
1010	goto done;
1011	}
1012
1013	/*
1014	* if the entry is 2nd and on up
1015	*/
1016	if ((req == RTM_DELETE) && !rt_mpath_deldup(rto, rt))
1017	panic ("rtrequest1: rt_mpath_deldup");
1018	gwdelete:
1019	RT_LOCK(rt);
1020	RT_ADDREF(rt);
1021	if (req == RTM_DELETE) {
1022	rt->rt_flags &= ~RTF_UP;
1023	/*
1024	* One more rtentry floating around that is not
1025	* linked to the routing table. rttrash will be decremented
1026	* when RTFREE(rt) is eventually called.
1027	*/
1028	V_rttrash++;
1029	}
1030
1031	nondelete:
1032	if (req != RTM_DELETE)
1033	panic("unrecognized request %d", req);
1034
1035
1036	/*
1037	* If the caller wants it, then it can have it,
1038	* but it's up to it to free the rtentry as we won't be
1039	* doing it.
1040	*/
1041	if (ret_nrt) {
1042	*ret_nrt = rt;
1043	RT_UNLOCK(rt);
1044	} else
1045	RTFREE_LOCKED(rt);
1046	done:
1047	return (error);
1048	}
1049	#endif
1050
1051	int	945	int
1052	rtrequest1_fib(int req, struct rt_addrinfo info, struct rtentry *ret_nrt,	946	rtrequest1_fib(int req, struct rt_addrinfo info, struct rtentry *ret_nrt,
1053	u_int fibnum)	947	u_int fibnum)
Lines 1100-1122 Link Here
1100	rt_maskedcopy(dst, (struct sockaddr *)&mdst, netmask);	994	rt_maskedcopy(dst, (struct sockaddr *)&mdst, netmask);
1101	dst = (struct sockaddr *)&mdst;	995	dst = (struct sockaddr *)&mdst;
1102	}	996	}
		997	if ((rn = rnh->rnh_lookup(dst, netmask, rnh)) == NULL)
		998	senderr(ESRCH);
		999	rt = RNTORT(rn);
1103	#ifdef RADIX_MPATH	1000	#ifdef RADIX_MPATH
		1001	/*
		1002	* if we got multipath routes, we require users to specify
		1003	* a matching RTAX_GATEWAY.
		1004	*/
1104	if (rn_mpath_capable(rnh)) {	1005	if (rn_mpath_capable(rnh)) {
1105	error = rn_mpath_update(req, info, rnh, ret_nrt);	1006	rt = rt_mpath_matchgate( rt, gateway);
1106	/*	1007	rn = (struct radix_node *)rt;
1107	* "bad" holds true for the success case	1008	if (!rt)
1108	* as well	1009	senderr(ESRCH);
1109	*/
1110	if (error != ENOENT)
1111	goto bad;
1112	error = 0;
1113	}	1010	}
1114	#endif	1011	#endif
1115	/*	1012	/*
1116	* Remove the item from the tree and return it.	1013	* Remove the item from the tree and return it.
1117	* Complain if it is not there and do no more processing.	1014	* Complain if it is not there and do no more processing.
1118	*/	1015	*/
1119	rn = rnh->rnh_deladdr(dst, netmask, rnh);	1016	rn = rnh->rnh_deladdr(dst, netmask, rnh, rn);
1120	if (rn == NULL)	1017	if (rn == NULL)
1121	senderr(ESRCH);	1018	senderr(ESRCH);
1122	if (rn->rn_flags & (RNF_ACTIVE \| RNF_ROOT))	1019	if (rn->rn_flags & (RNF_ACTIVE \| RNF_ROOT))
Lines 1212-1218 Link Here
1212	rt->rt_ifa = ifa;	1109	rt->rt_ifa = ifa;
1213	rt->rt_ifp = ifa->ifa_ifp;	1110	rt->rt_ifp = ifa->ifa_ifp;
1214	rt->rt_rmx.rmx_weight = 1;	1111	rt->rt_rmx.rmx_weight = 1;
1215		1112
1216	#ifdef RADIX_MPATH	1113	#ifdef RADIX_MPATH
1217	/* do not permit exactly the same dst/mask/gw pair */	1114	/* do not permit exactly the same dst/mask/gw pair */
1218	if (rn_mpath_capable(rnh) &&	1115	if (rn_mpath_capable(rnh) &&
Lines 1373-1379 Link Here
1373	*/	1270	*/
1374	if (rt->rt_gateway == NULL \|\| glen > SA_SIZE(rt->rt_gateway)) {	1271	if (rt->rt_gateway == NULL \|\| glen > SA_SIZE(rt->rt_gateway)) {
1375	caddr_t new;	1272	caddr_t new;
1376		1273
1377	R_Malloc(new, caddr_t, dlen + glen);	1274	R_Malloc(new, caddr_t, dlen + glen);
1378	if (new == NULL)	1275	if (new == NULL)
1379	return ENOBUFS;	1276	return ENOBUFS;
Lines 1506-1514 Link Here
1506	RADIX_NODE_HEAD_LOCK(rnh);	1403	RADIX_NODE_HEAD_LOCK(rnh);
1507	#ifdef RADIX_MPATH	1404	#ifdef RADIX_MPATH
1508	if (rn_mpath_capable(rnh)) {	1405	if (rn_mpath_capable(rnh)) {
1509		1406	rn = rnh->rnh_lookup(dst, netmask, rnh);
1510	rn = rnh->rnh_matchaddr(dst, rnh);	1407	if (rn == NULL)
1511	if (rn == NULL)
1512	error = ESRCH;	1408	error = ESRCH;
1513	else {	1409	else {
1514	rt = RNTORT(rn);	1410	rt = RNTORT(rn);
Lines 1523-1528 Link Here
1523	ifa->ifa_addr);	1419	ifa->ifa_addr);
1524	if (!rt)	1420	if (!rt)
1525	error = ESRCH;	1421	error = ESRCH;
		1422	rn = (struct radix_node *)rt;
1526	}	1423	}
1527	}	1424	}
1528	else	1425	else

Lines 116-122 Link Here

(-)/router/usr/src/sys/net/radix.h (-2 / +4 lines)
116	(void v, void mask,	116	(void v, void mask,
117	struct radix_node_head *head, struct radix_node nodes[]);	117	struct radix_node_head *head, struct radix_node nodes[]);
118	struct radix_node (rnh_deladdr) /* remove based on sockaddr */	118	struct radix_node (rnh_deladdr) /* remove based on sockaddr */
119	(void v, void mask, struct radix_node_head *head);	119	(void v, void mask, struct radix_node_head *head,
		120	struct radix_node *rn);
120	struct radix_node (rnh_delpkt) /* remove based on packet hdr */	121	struct radix_node (rnh_delpkt) /* remove based on packet hdr */
121	(void v, void mask, struct radix_node_head *head);	122	(void v, void mask, struct radix_node_head *head);
122	struct radix_node (rnh_matchaddr) /* locate based on sockaddr */	123	struct radix_node (rnh_matchaddr) /* locate based on sockaddr */
Lines 169-175 Link Here
169	rn_addmask(void , int, int),	170	rn_addmask(void , int, int),
170	rn_addroute (void , void , struct radix_node_head ,	171	rn_addroute (void , void , struct radix_node_head ,
171	struct radix_node [2]),	172	struct radix_node [2]),
172	rn_delete(void , void , struct radix_node_head ),	173	rn_delete(void , void , struct radix_node_head ,
		174	struct radix_node *),
173	rn_lookup (void v_arg, void *m_arg,	175	rn_lookup (void v_arg, void *m_arg,
174	struct radix_node_head *head),	176	struct radix_node_head *head),
175	rn_match(void , struct radix_node_head *);	177	rn_match(void , struct radix_node_head *);

Lines 77-96 Link Here

(-)/router/usr/src/sys/net/radix_mpath.c (-55 / +49 lines)
77	return NULL;	77	return NULL;
78	}	78	}
79		79
80	uint32_t
81	rn_mpath_count(struct radix_node *rn)
82	{
83	uint32_t i = 0;
84	struct rtentry *rt;
85
86	while (rn != NULL) {
87	rt = (struct rtentry *)rn;
88	i += rt->rt_rmx.rmx_weight;
89	rn = rn_mpath_next(rn);
90	}
91	return (i);
92	}
93
94	struct rtentry *	80	struct rtentry *
95	rt_mpath_matchgate(struct rtentry rt, struct sockaddr gate)	81	rt_mpath_matchgate(struct rtentry rt, struct sockaddr gate)
96	{	82	{
Lines 122-154 Link Here
122	return (struct rtentry *)rn;	108	return (struct rtentry *)rn;
123	}	109	}
124		110
125	/*
126	* go through the chain and unlink "rt" from the list
127	* the caller will free "rt"
128	*/
129	int
130	rt_mpath_deldup(struct rtentry headrt, struct rtentry rt)
131	{
132	struct radix_node t, tt;
133
134	if (!headrt \|\| !rt)
135	return (0);
136	t = (struct radix_node *)headrt;
137	tt = rn_mpath_next(t);
138	while (tt) {
139	if (tt == (struct radix_node *)rt) {
140	t->rn_dupedkey = tt->rn_dupedkey;
141	tt->rn_dupedkey = NULL;
142	tt->rn_flags &= ~RNF_ACTIVE;
143	tt[1].rn_flags &= ~RNF_ACTIVE;
144	return (1);
145	}
146	t = tt;
147	tt = rn_mpath_next((struct radix_node *)t);
148	}
149	return (0);
150	}
151
152	/*	111	/*
153	* check if we have the same key/mask/gateway on the table already.	112	* check if we have the same key/mask/gateway on the table already.
154	*/	113	*/
Lines 256-267 Link Here
256	}	215	}
257		216
258	void	217	void
259	rtalloc_mpath_fib(struct route *ro, uint32_t hash, u_int fibnum)	218	rtalloc_mpath_fib(struct route *ro, uint32_t hash, u_int fibnum) {
		219	rtalloc_mpath_fib_flags( ro, hash, fibnum, 0);
		220	}
		221
		222	/*
		223	* flag RTF_GATEWAY returns only interface routes,
		224	* only one interface-route is possible
		225	*/
		226	void
		227	rtalloc_mpath_fib_flags(struct route *ro, uint32_t hash, u_int fibnum, int flags)
260	{	228	{
261	struct radix_node rn0, rn;	229	struct radix_node rn0, rn;
262	u_int32_t n;	230	u_int32_t n = 0;
263	struct rtentry *rt;	231	struct rtentry *rt;
264	int64_t weight;	232	int64_t lowest_weight;
265		233
266	/*	234	/*
267	* XXX we don't attempt to lookup cached route again; what should	235	* XXX we don't attempt to lookup cached route again; what should
Lines 269-297 Link Here
269	*/	237	*/
270	if (ro->ro_rt && ro->ro_rt->rt_ifp && (ro->ro_rt->rt_flags & RTF_UP)	238	if (ro->ro_rt && ro->ro_rt->rt_ifp && (ro->ro_rt->rt_flags & RTF_UP)
271	&& RT_LINK_IS_UP(ro->ro_rt->rt_ifp))	239	&& RT_LINK_IS_UP(ro->ro_rt->rt_ifp))
272	return;	240	return;
273	ro->ro_rt = rtalloc1_fib(&ro->ro_dst, 1, 0, fibnum);	241	ro->ro_rt = rtalloc1_fib(&ro->ro_dst, 1, 0, fibnum);
274		242
275	/* if the route does not exist or it is not multipath, don't care */	243	/* if the route does not exist or it is not multipath, don't care */
276	if (ro->ro_rt == NULL)	244	if (ro->ro_rt == NULL)
277	return;	245	return;
278	if (rn_mpath_next((struct radix_node *)ro->ro_rt) == NULL) {	246	if (rn_mpath_next((struct radix_node *)ro->ro_rt) == NULL) {
		247	if (flags & RTF_GATEWAY)
		248	return;
279	RT_UNLOCK(ro->ro_rt);	249	RT_UNLOCK(ro->ro_rt);
280	return;	250	return;
281	}	251	}
282		252
283	/* beyond here, we use rn as the master copy */	253	/* beyond here, we use rn as the master copy */
284	rn0 = rn = (struct radix_node *)ro->ro_rt;	254	rn0 = rn = (struct radix_node *)ro->ro_rt;
285	n = rn_mpath_count(rn0);
286		255
287	/* gw selection by Modulo-N Hash (RFC2991) XXX need improvement? */	256	/* find count of lowest weight route */
		257	for (rt = ro->ro_rt, lowest_weight = 9223372036854775807; rn != NULL;){
		258	if( rt->rt_flags & RTF_UP) {
		259	if ((flags & RTF_GATEWAY) &&
		260	(!(rt->rt_flags & RTF_GATEWAY)) &&
		261	(!(rt->rt_flags & RTF_HOST)) )
		262	goto end; /* only 1 interface route possible! */
		263	if( lowest_weight > rt->rt_rmx.rmx_weight) {
		264	lowest_weight = rt->rt_rmx.rmx_weight;
		265	n = 1;
		266	} else if( lowest_weight == rt->rt_rmx.rmx_weight)
		267	n++;
		268	}
		269	if (rn->rn_dupedkey && rn->rn_mask != rn->rn_dupedkey->rn_mask)
		270	break;
		271	rn = rn->rn_dupedkey;
		272	rt = (struct rtentry *)rn;
		273	}
		274	/* select now one of the lowest weight routes */
		275	/* gw selection by Modulo-N Hash (RFC2991) */
288	hash += hashjitter;	276	hash += hashjitter;
289	hash %= n;	277	hash %= n;
290	for (weight = abs((int32_t)hash), rt = ro->ro_rt;	278	for ( rt = ro->ro_rt, rn = rn0, n = 0; rn != NULL; ) {
291	weight >= rt->rt_rmx.rmx_weight && rn;	279	if( rt->rt_flags & RTF_UP) {
292	weight -= rt->rt_rmx.rmx_weight) {	280	if ( rt->rt_rmx.rmx_weight == lowest_weight) {
293		281	if (n == hash)
294	/* stay within the multipath routes */	282	break;
		283	n++;
		284	}
		285	}
295	if (rn->rn_dupedkey && rn->rn_mask != rn->rn_dupedkey->rn_mask)	286	if (rn->rn_dupedkey && rn->rn_mask != rn->rn_dupedkey->rn_mask)
296	break;	287	break;
297	rn = rn->rn_dupedkey;	288	rn = rn->rn_dupedkey;
Lines 300-318 Link Here
300	/* XXX try filling rt_gwroute and avoid unreachable gw */	291	/* XXX try filling rt_gwroute and avoid unreachable gw */
301		292
302	/* gw selection has failed - there must be only zero weight routes */	293	/* gw selection has failed - there must be only zero weight routes */
303	if (!rn) {	294	if (!rn \|\| (flags & RTF_GATEWAY)) {
304	RT_UNLOCK(ro->ro_rt);	295	RT_UNLOCK(ro->ro_rt);
305	ro->ro_rt = NULL;	296	ro->ro_rt = NULL;
306	return;	297	return;
307	}	298	}
		299
		300	end:
308	if (ro->ro_rt != rt) {	301	if (ro->ro_rt != rt) {
309	RTFREE_LOCKED(ro->ro_rt);	302	RTFREE_LOCKED(ro->ro_rt);
310	ro->ro_rt = (struct rtentry *)rn;	303	ro->ro_rt = (struct rtentry *)rn;
311	RT_LOCK(ro->ro_rt);	304	RT_LOCK(ro->ro_rt);
312	RT_ADDREF(ro->ro_rt);	305	RT_ADDREF(ro->ro_rt);
313		306
314	}	307	}
315	RT_UNLOCK(ro->ro_rt);	308	if (!(flags & RTF_GATEWAY))
		309	RT_UNLOCK(ro->ro_rt);
316	}	310	}
317		311
318	extern int in6_inithead(void **head, int off);	312	extern int in6_inithead(void **head, int off);

Lines 46-57 Link Here

(-)/router/usr/src/sys/net/radix_mpath.h (-1 / +1 lines)
46	struct sockaddr;	46	struct sockaddr;
47	int rn_mpath_capable(struct radix_node_head *);	47	int rn_mpath_capable(struct radix_node_head *);
48	struct radix_node rn_mpath_next(struct radix_node );	48	struct radix_node rn_mpath_next(struct radix_node );
49	u_int32_t rn_mpath_count(struct radix_node *);
50	struct rtentry rt_mpath_matchgate(struct rtentry , struct sockaddr *);	49	struct rtentry rt_mpath_matchgate(struct rtentry , struct sockaddr *);
51	int rt_mpath_conflict(struct radix_node_head , struct rtentry ,	50	int rt_mpath_conflict(struct radix_node_head , struct rtentry ,
52	struct sockaddr *);	51	struct sockaddr *);
53	void rtalloc_mpath_fib(struct route *, u_int32_t, u_int);	52	void rtalloc_mpath_fib(struct route *, u_int32_t, u_int);
54	#define rtalloc_mpath(_route, _hash) rtalloc_mpath_fib((_route), (_hash), 0)	53	#define rtalloc_mpath(_route, _hash) rtalloc_mpath_fib((_route), (_hash), 0)
		54	void rtalloc_mpath_fib_flags(struct route *, u_int32_t, u_int, int);
55	struct radix_node rn_mpath_lookup(void , void *,	55	struct radix_node rn_mpath_lookup(void , void *,
56	struct radix_node_head *);	56	struct radix_node_head *);
57	int rt_mpath_deldup(struct rtentry , struct rtentry );	57	int rt_mpath_deldup(struct rtentry , struct rtentry );