Annotation of sys/net/radix_mpath.c, Revision 1.1
1.1 ! nbrk 1: /* $OpenBSD: radix_mpath.c,v 1.7 2006/06/18 12:03:19 pascoe Exp $ */
! 2: /* $KAME: radix_mpath.c,v 1.13 2002/10/28 21:05:59 itojun Exp $ */
! 3:
! 4: /*
! 5: * Copyright (C) 2001 WIDE Project.
! 6: * All rights reserved.
! 7: *
! 8: * Redistribution and use in source and binary forms, with or without
! 9: * modification, are permitted provided that the following conditions
! 10: * are met:
! 11: * 1. Redistributions of source code must retain the above copyright
! 12: * notice, this list of conditions and the following disclaimer.
! 13: * 2. Redistributions in binary form must reproduce the above copyright
! 14: * notice, this list of conditions and the following disclaimer in the
! 15: * documentation and/or other materials provided with the distribution.
! 16: * 3. Neither the name of the project nor the names of its contributors
! 17: * may be used to endorse or promote products derived from this software
! 18: * without specific prior written permission.
! 19: *
! 20: * THIS SOFTWARE IS PROVIDED BY THE PROJECT AND CONTRIBUTORS ``AS IS'' AND
! 21: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
! 22: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
! 23: * ARE DISCLAIMED. IN NO EVENT SHALL THE PROJECT OR CONTRIBUTORS BE LIABLE
! 24: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
! 25: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
! 26: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
! 27: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
! 28: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
! 29: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
! 30: * SUCH DAMAGE.
! 31: * THE AUTHORS DO NOT GUARANTEE THAT THIS SOFTWARE DOES NOT INFRINGE
! 32: * ANY OTHERS' INTELLECTUAL PROPERTIES. IN NO EVENT SHALL THE AUTHORS
! 33: * BE LIABLE FOR ANY INFRINGEMENT OF ANY OTHERS' INTELLECTUAL
! 34: * PROPERTIES.
! 35: */
! 36:
! 37: #include <sys/param.h>
! 38: #include <sys/systm.h>
! 39: #include <sys/malloc.h>
! 40: #include <sys/socket.h>
! 41: #define M_DONTWAIT M_NOWAIT
! 42: #include <sys/domain.h>
! 43: #include <sys/syslog.h>
! 44: #include <net/radix.h>
! 45: #include <net/radix_mpath.h>
! 46: #include <net/route.h>
! 47: #include <dev/rndvar.h>
! 48:
! 49: #include <netinet/in.h>
! 50:
! 51: extern int ipmultipath;
! 52: extern int ip6_multipath;
! 53:
! 54: u_int32_t rn_mpath_hash(struct route *, u_int32_t *);
! 55:
! 56: /*
! 57: * give some jitter to hash, to avoid synchronization between routers
! 58: */
! 59: static u_int32_t hashjitter;
! 60:
! 61: int
! 62: rn_mpath_capable(struct radix_node_head *rnh)
! 63: {
! 64: return rnh->rnh_multipath;
! 65: }
! 66:
! 67: struct radix_node *
! 68: rn_mpath_next(struct radix_node *rn)
! 69: {
! 70: struct radix_node *next;
! 71:
! 72: if (!rn->rn_dupedkey)
! 73: return NULL;
! 74: next = rn->rn_dupedkey;
! 75: if (rn->rn_mask == next->rn_mask)
! 76: return next;
! 77: else
! 78: return NULL;
! 79: }
! 80:
! 81: int
! 82: rn_mpath_count(struct radix_node *rn)
! 83: {
! 84: int i;
! 85:
! 86: i = 1;
! 87: while ((rn = rn_mpath_next(rn)) != NULL)
! 88: i++;
! 89: return i;
! 90: }
! 91:
! 92: struct rtentry *
! 93: rt_mpath_matchgate(struct rtentry *rt, struct sockaddr *gate)
! 94: {
! 95: struct radix_node *rn;
! 96:
! 97: if (!rn_mpath_next((struct radix_node *)rt))
! 98: return rt;
! 99:
! 100: if (!gate)
! 101: return NULL;
! 102: /* beyond here, we use rn as the master copy */
! 103: rn = (struct radix_node *)rt;
! 104: do {
! 105: rt = (struct rtentry *)rn;
! 106: if (rt->rt_gateway->sa_len == gate->sa_len &&
! 107: !memcmp(rt->rt_gateway, gate, gate->sa_len))
! 108: break;
! 109: } while ((rn = rn_mpath_next(rn)) != NULL);
! 110: if (!rn)
! 111: return NULL;
! 112:
! 113: return (struct rtentry *)rn;
! 114: }
! 115:
! 116: /*
! 117: * check if we have the same key/mask/gateway on the table already.
! 118: */
! 119: int
! 120: rt_mpath_conflict(struct radix_node_head *rnh, struct rtentry *rt,
! 121: struct sockaddr *netmask, int mpathok)
! 122: {
! 123: struct radix_node *rn, *rn1;
! 124: struct rtentry *rt1;
! 125: char *p, *q, *eq;
! 126: int same, l, skip;
! 127:
! 128: rn = (struct radix_node *)rt;
! 129: rn1 = rnh->rnh_lookup(rt_key(rt), netmask, rnh);
! 130: if (!rn1 || rn1->rn_flags & RNF_ROOT)
! 131: return 0;
! 132:
! 133: /*
! 134: * unlike other functions we have in this file, we have to check
! 135: * all key/mask/gateway as rnh_lookup can match less specific entry.
! 136: */
! 137: rt1 = (struct rtentry *)rn1;
! 138:
! 139: /* compare key. */
! 140: if (rt_key(rt1)->sa_len != rt_key(rt)->sa_len ||
! 141: bcmp(rt_key(rt1), rt_key(rt), rt_key(rt1)->sa_len))
! 142: goto different;
! 143:
! 144: /* key was the same. compare netmask. hairy... */
! 145: if (rt_mask(rt1) && netmask) {
! 146: skip = rnh->rnh_treetop->rn_off;
! 147: if (rt_mask(rt1)->sa_len > netmask->sa_len) {
! 148: /*
! 149: * as rt_mask(rt1) is made optimal by radix.c,
! 150: * there must be some 1-bits on rt_mask(rt1)
! 151: * after netmask->sa_len. therefore, in
! 152: * this case, the entries are different.
! 153: */
! 154: if (rt_mask(rt1)->sa_len > skip)
! 155: goto different;
! 156: else {
! 157: /* no bits to compare, i.e. same*/
! 158: goto maskmatched;
! 159: }
! 160: }
! 161:
! 162: l = rt_mask(rt1)->sa_len;
! 163: if (skip > l) {
! 164: /* no bits to compare, i.e. same */
! 165: goto maskmatched;
! 166: }
! 167: p = (char *)rt_mask(rt1);
! 168: q = (char *)netmask;
! 169: if (bcmp(p + skip, q + skip, l - skip))
! 170: goto different;
! 171: /*
! 172: * need to go through all the bit, as netmask is not
! 173: * optimal and can contain trailing 0s
! 174: */
! 175: eq = (char *)netmask + netmask->sa_len;
! 176: q += l;
! 177: same = 1;
! 178: while (eq > q)
! 179: if (*q++) {
! 180: same = 0;
! 181: break;
! 182: }
! 183: if (!same)
! 184: goto different;
! 185: } else if (!rt_mask(rt1) && !netmask)
! 186: ; /* no mask to compare, i.e. same */
! 187: else {
! 188: /* one has mask and the other does not, different */
! 189: goto different;
! 190: }
! 191:
! 192: maskmatched:
! 193: if (!mpathok)
! 194: return EEXIST;
! 195:
! 196: /* key/mask were the same. compare gateway for all multipaths */
! 197: do {
! 198: rt1 = (struct rtentry *)rn1;
! 199:
! 200: /* sanity: no use in comparing the same thing */
! 201: if (rn1 == rn)
! 202: continue;
! 203:
! 204: if (rt1->rt_gateway->sa_len != rt->rt_gateway->sa_len ||
! 205: bcmp(rt1->rt_gateway, rt->rt_gateway,
! 206: rt1->rt_gateway->sa_len))
! 207: continue;
! 208:
! 209: /* all key/mask/gateway are the same. conflicting entry. */
! 210: return EEXIST;
! 211: } while ((rn1 = rn_mpath_next(rn1)) != NULL);
! 212:
! 213: different:
! 214: return 0;
! 215: }
! 216:
! 217: /*
! 218: * allocate a route, potentially using multipath to select the peer.
! 219: */
! 220: void
! 221: rtalloc_mpath(struct route *ro, u_int32_t *srcaddrp, u_int tableid)
! 222: {
! 223: #if defined(INET) || defined(INET6)
! 224: struct radix_node *rn;
! 225: int hash, npaths, threshold;
! 226: #endif
! 227:
! 228: /*
! 229: * return a cached entry if it is still valid, otherwise we increase
! 230: * the risk of disrupting local flows.
! 231: */
! 232: if (ro->ro_rt && ro->ro_rt->rt_ifp && (ro->ro_rt->rt_flags & RTF_UP))
! 233: return;
! 234: ro->ro_rt = rtalloc1(&ro->ro_dst, 1, tableid);
! 235:
! 236: /* if the route does not exist or it is not multipath, don't care */
! 237: if (!ro->ro_rt || !(ro->ro_rt->rt_flags & RTF_MPATH))
! 238: return;
! 239:
! 240: /* check if multipath routing is enabled for the specified protocol */
! 241: if (!(0
! 242: #ifdef INET
! 243: || (ipmultipath && ro->ro_dst.sa_family == AF_INET)
! 244: #endif
! 245: #ifdef INET6
! 246: || (ip6_multipath && ro->ro_dst.sa_family == AF_INET6)
! 247: #endif
! 248: ))
! 249: return;
! 250:
! 251: #if defined(INET) || defined(INET6)
! 252: /* gw selection by Hash-Threshold (RFC 2992) */
! 253: rn = (struct radix_node *)ro->ro_rt;
! 254: npaths = rn_mpath_count(rn);
! 255: hash = rn_mpath_hash(ro, srcaddrp) & 0xffff;
! 256: threshold = 1 + (0xffff / npaths);
! 257: while (hash > threshold && rn) {
! 258: /* stay within the multipath routes */
! 259: if (rn->rn_dupedkey && rn->rn_mask != rn->rn_dupedkey->rn_mask)
! 260: break;
! 261: rn = rn->rn_dupedkey;
! 262: hash -= threshold;
! 263: }
! 264:
! 265: /* XXX try filling rt_gwroute and avoid unreachable gw */
! 266:
! 267: /* if gw selection fails, use the first match (default) */
! 268: if (!rn)
! 269: return;
! 270:
! 271: rtfree(ro->ro_rt);
! 272: ro->ro_rt = (struct rtentry *)rn;
! 273: ro->ro_rt->rt_refcnt++;
! 274: #endif
! 275: }
! 276:
! 277: int
! 278: rn_mpath_inithead(void **head, int off)
! 279: {
! 280: struct radix_node_head *rnh;
! 281:
! 282: while (hashjitter == 0)
! 283: hashjitter = arc4random();
! 284: if (rn_inithead(head, off) == 1) {
! 285: rnh = (struct radix_node_head *)*head;
! 286: rnh->rnh_multipath = 1;
! 287: return 1;
! 288: } else
! 289: return 0;
! 290: }
! 291:
! 292: /*
! 293: * hash function based on pf_hash in pf.c
! 294: */
! 295: #define mix(a,b,c) \
! 296: do { \
! 297: a -= b; a -= c; a ^= (c >> 13); \
! 298: b -= c; b -= a; b ^= (a << 8); \
! 299: c -= a; c -= b; c ^= (b >> 13); \
! 300: a -= b; a -= c; a ^= (c >> 12); \
! 301: b -= c; b -= a; b ^= (a << 16); \
! 302: c -= a; c -= b; c ^= (b >> 5); \
! 303: a -= b; a -= c; a ^= (c >> 3); \
! 304: b -= c; b -= a; b ^= (a << 10); \
! 305: c -= a; c -= b; c ^= (b >> 15); \
! 306: } while (0)
! 307:
! 308: u_int32_t
! 309: rn_mpath_hash(struct route *ro, u_int32_t *srcaddrp)
! 310: {
! 311: u_int32_t a, b, c;
! 312:
! 313: a = b = 0x9e3779b9;
! 314: c = hashjitter;
! 315:
! 316: switch (ro->ro_dst.sa_family) {
! 317: #ifdef INET
! 318: case AF_INET:
! 319: {
! 320: struct sockaddr_in *sin_dst;
! 321:
! 322: sin_dst = (struct sockaddr_in *)&ro->ro_dst;
! 323: a += sin_dst->sin_addr.s_addr;
! 324: b += srcaddrp ? srcaddrp[0] : 0;
! 325: mix(a, b, c);
! 326: break;
! 327: }
! 328: #endif /* INET */
! 329: #ifdef INET6
! 330: case AF_INET6:
! 331: {
! 332: struct sockaddr_in6 *sin6_dst;
! 333:
! 334: sin6_dst = (struct sockaddr_in6 *)&ro->ro_dst;
! 335: a += sin6_dst->sin6_addr.s6_addr32[0];
! 336: b += sin6_dst->sin6_addr.s6_addr32[2];
! 337: c += srcaddrp ? srcaddrp[0] : 0;
! 338: mix(a, b, c);
! 339: a += sin6_dst->sin6_addr.s6_addr32[1];
! 340: b += sin6_dst->sin6_addr.s6_addr32[3];
! 341: c += srcaddrp ? srcaddrp[1] : 0;
! 342: mix(a, b, c);
! 343: a += sin6_dst->sin6_addr.s6_addr32[2];
! 344: b += sin6_dst->sin6_addr.s6_addr32[1];
! 345: c += srcaddrp ? srcaddrp[2] : 0;
! 346: mix(a, b, c);
! 347: a += sin6_dst->sin6_addr.s6_addr32[3];
! 348: b += sin6_dst->sin6_addr.s6_addr32[0];
! 349: c += srcaddrp ? srcaddrp[3] : 0;
! 350: mix(a, b, c);
! 351: break;
! 352: }
! 353: #endif /* INET6 */
! 354: }
! 355:
! 356: return c;
! 357: }
CVSweb
![[BACK]](/icons/back.gif){kind=icon}
Return to radix_mpath.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / sys / net