diff options
Diffstat (limited to 'sys/net')
-rw-r--r-- | sys/net/radix.c | 239 | ||||
-rw-r--r-- | sys/net/radix.h | 4 | ||||
-rw-r--r-- | sys/net/radix_mpath.c | 73 | ||||
-rw-r--r-- | sys/net/route.c | 57 | ||||
-rw-r--r-- | sys/net/rtsock.c | 39 |
5 files changed, 194 insertions, 218 deletions
diff --git a/sys/net/radix.c b/sys/net/radix.c index 6362bb7..5bf9dff 100644 --- a/sys/net/radix.c +++ b/sys/net/radix.c @@ -156,12 +156,10 @@ static int rn_satisfies_leaf(char *trial, struct radix_node *leaf, * Search a node in the tree matching the key. */ static struct radix_node * -rn_search(v_arg, head) - void *v_arg; - struct radix_node *head; +rn_search(void *v_arg, struct radix_node *head) { - register struct radix_node *x; - register caddr_t v; + struct radix_node *x; + caddr_t v; for (x = head, v = v_arg; x->rn_bit >= 0;) { if (x->rn_bmask & v[x->rn_offset]) @@ -177,12 +175,10 @@ rn_search(v_arg, head) * XXX note this function is used only once. */ static struct radix_node * -rn_search_m(v_arg, head, m_arg) - struct radix_node *head; - void *v_arg, *m_arg; +rn_search_m(void *v_arg, struct radix_node *head, void *m_arg) { - register struct radix_node *x; - register caddr_t v = v_arg, m = m_arg; + struct radix_node *x; + caddr_t v = v_arg, m = m_arg; for (x = head; x->rn_bit >= 0;) { if ((x->rn_bmask & m[x->rn_offset]) && @@ -191,15 +187,14 @@ rn_search_m(v_arg, head, m_arg) else x = x->rn_left; } - return x; + return (x); } int -rn_refines(m_arg, n_arg) - void *m_arg, *n_arg; +rn_refines(void *m_arg, void *n_arg) { - register caddr_t m = m_arg, n = n_arg; - register caddr_t lim, lim2 = lim = n + LEN(n); + caddr_t m = m_arg, n = n_arg; + caddr_t lim, lim2 = lim = n + LEN(n); int longer = LEN(n++) - LEN(m++); int masks_are_equal = 1; @@ -207,50 +202,71 @@ rn_refines(m_arg, n_arg) lim -= longer; while (n < lim) { if (*n & ~(*m)) - return 0; + return (0); if (*n++ != *m++) masks_are_equal = 0; } while (n < lim2) if (*n++) - return 0; + return (0); if (masks_are_equal && (longer < 0)) for (lim2 = m - longer; m < lim2; ) if (*m++) - return 1; + return (1); return (!masks_are_equal); } +/* + * Search for exact match in given @head. + * Assume host bits are cleared in @v_arg if @m_arg is not NULL + * Note that prefixes with /32 or /128 masks are treated differently + * from host routes. + */ struct radix_node * -rn_lookup(v_arg, m_arg, head) - void *v_arg, *m_arg; - struct radix_node_head *head; +rn_lookup(void *v_arg, void *m_arg, struct radix_node_head *head) { - register struct radix_node *x; - caddr_t netmask = 0; + struct radix_node *x; + caddr_t netmask; - if (m_arg) { + if (m_arg != NULL) { + /* + * Most common case: search exact prefix/mask + */ x = rn_addmask_r(m_arg, head->rnh_masks, 1, head->rnh_treetop->rn_offset); - if (x == 0) - return (0); + if (x == NULL) + return (NULL); netmask = x->rn_key; - } - x = rn_match(v_arg, head); - if (x && netmask) { - while (x && x->rn_mask != netmask) + + x = rn_match(v_arg, head); + + while (x != NULL && x->rn_mask != netmask) x = x->rn_dupedkey; + + return (x); } - return x; + + /* + * Search for host address. + */ + if ((x = rn_match(v_arg, head)) == NULL) + return (NULL); + + /* Check if found key is the same */ + if (LEN(x->rn_key) != LEN(v_arg) || bcmp(x->rn_key, v_arg, LEN(v_arg))) + return (NULL); + + /* Check if this is not host route */ + if (x->rn_mask != NULL) + return (NULL); + + return (x); } static int -rn_satisfies_leaf(trial, leaf, skip) - char *trial; - register struct radix_node *leaf; - int skip; +rn_satisfies_leaf(char *trial, struct radix_node *leaf, int skip) { - register char *cp = trial, *cp2 = leaf->rn_key, *cp3 = leaf->rn_mask; + char *cp = trial, *cp2 = leaf->rn_key, *cp3 = leaf->rn_mask; char *cplim; int length = min(LEN(cp), LEN(cp2)); @@ -261,22 +277,23 @@ rn_satisfies_leaf(trial, leaf, skip) cplim = cp + length; cp3 += skip; cp2 += skip; for (cp += skip; cp < cplim; cp++, cp2++, cp3++) if ((*cp ^ *cp2) & *cp3) - return 0; - return 1; + return (0); + return (1); } +/* + * Search for longest-prefix match in given @head + */ struct radix_node * -rn_match(v_arg, head) - void *v_arg; - struct radix_node_head *head; +rn_match(void *v_arg, struct radix_node_head *head) { caddr_t v = v_arg; - register struct radix_node *t = head->rnh_treetop, *x; - register caddr_t cp = v, cp2; + struct radix_node *t = head->rnh_treetop, *x; + caddr_t cp = v, cp2; caddr_t cplim; struct radix_node *saved_t, *top = t; int off = t->rn_offset, vlen = LEN(cp), matched_off; - register int test, b, rn_bit; + int test, b, rn_bit; /* * Open code rn_search(v, top) to avoid overhead of extra @@ -314,7 +331,7 @@ rn_match(v_arg, head) */ if (t->rn_flags & RNF_ROOT) t = t->rn_dupedkey; - return t; + return (t); on1: test = (*cp ^ *cp2) & 0xff; /* find first bit that differs */ for (b = 7; (test >>= 1) > 0;) @@ -335,13 +352,13 @@ on1: */ if (t->rn_flags & RNF_NORMAL) { if (rn_bit <= t->rn_bit) - return t; + return (t); } else if (rn_satisfies_leaf(v, t, matched_off)) - return t; + return (t); t = saved_t; /* start searching up the tree */ do { - register struct radix_mask *m; + struct radix_mask *m; t = t->rn_parent; m = t->rn_mklist; /* @@ -360,12 +377,12 @@ on1: while (x && x->rn_mask != m->rm_mask) x = x->rn_dupedkey; if (x && rn_satisfies_leaf(v, x, off)) - return x; + return (x); } m = m->rm_mklist; } } while (t != top); - return 0; + return (0); } #ifdef RN_DEBUG @@ -387,12 +404,9 @@ int rn_debug = 1; */ static struct radix_node * -rn_newpair(v, b, nodes) - void *v; - int b; - struct radix_node nodes[2]; +rn_newpair(void *v, int b, struct radix_node nodes[2]) { - register struct radix_node *tt = nodes, *t = tt + 1; + struct radix_node *tt = nodes, *t = tt + 1; t->rn_bit = b; t->rn_bmask = 0x80 >> (b & 7); t->rn_left = tt; @@ -416,44 +430,39 @@ rn_newpair(v, b, nodes) tt->rn_ybro = rn_clist; rn_clist = tt; #endif - return t; + return (t); } static struct radix_node * -rn_insert(v_arg, head, dupentry, nodes) - void *v_arg; - struct radix_node_head *head; - int *dupentry; - struct radix_node nodes[2]; +rn_insert(void *v_arg, struct radix_node_head *head, int *dupentry, + struct radix_node nodes[2]) { caddr_t v = v_arg; struct radix_node *top = head->rnh_treetop; int head_off = top->rn_offset, vlen = LEN(v); - register struct radix_node *t = rn_search(v_arg, top); - register caddr_t cp = v + head_off; - register int b; - struct radix_node *tt; + struct radix_node *t = rn_search(v_arg, top); + caddr_t cp = v + head_off; + int b; + struct radix_node *p, *tt, *x; /* * Find first bit at which v and t->rn_key differ */ - { - register caddr_t cp2 = t->rn_key + head_off; - register int cmp_res; + caddr_t cp2 = t->rn_key + head_off; + int cmp_res; caddr_t cplim = v + vlen; while (cp < cplim) if (*cp2++ != *cp++) goto on1; *dupentry = 1; - return t; + return (t); on1: *dupentry = 0; cmp_res = (cp[-1] ^ cp2[-1]) & 0xff; for (b = (cp - v) << 3; cmp_res; b--) cmp_res >>= 1; - } - { - register struct radix_node *p, *x = top; + + x = top; cp = v; do { p = x; @@ -485,20 +494,19 @@ on1: if (rn_debug) log(LOG_DEBUG, "rn_insert: Coming Out:\n"), traverse(p); #endif - } return (tt); } struct radix_node * rn_addmask_r(void *arg, struct radix_node_head *maskhead, int search, int skip) { - caddr_t netmask = (caddr_t)arg; - register struct radix_node *x; - register caddr_t cp, cplim; - register int b = 0, mlen, j; + unsigned char *netmask = arg; + unsigned char *cp, *cplim; + struct radix_node *x; + int b = 0, mlen, j; int maskduplicated, isnormal; struct radix_node *saved_x; - char addmask_key[RADIX_MAX_KEY_LEN]; + unsigned char addmask_key[RADIX_MAX_KEY_LEN]; if ((mlen = LEN(netmask)) > RADIX_MAX_KEY_LEN) mlen = RADIX_MAX_KEY_LEN; @@ -540,20 +548,18 @@ rn_addmask_r(void *arg, struct radix_node_head *maskhead, int search, int skip) * Calculate index of mask, and check for normalcy. * First find the first byte with a 0 bit, then if there are * more bits left (remember we already trimmed the trailing 0's), - * the pattern must be one of those in normal_chars[], or we have + * the bits should be contiguous, otherwise we have got * a non-contiguous mask. */ +#define CONTIG(_c) (((~(_c) + 1) & (_c)) == (unsigned char)(~(_c) + 1)) cplim = netmask + mlen; isnormal = 1; for (cp = netmask + skip; (cp < cplim) && *(u_char *)cp == 0xff;) cp++; if (cp != cplim) { - static char normal_chars[] = { - 0, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, 0xff}; - for (j = 0x80; (j & *cp) != 0; j >>= 1) b++; - if (*cp != normal_chars[b] || cp != (cplim - 1)) + if (!CONTIG(*cp) || cp != (cplim - 1)) isnormal = 0; } b += (cp - netmask) << 3; @@ -581,29 +587,26 @@ rn_addmask(void *n_arg, int search, int skip) } static int /* XXX: arbitrary ordering for non-contiguous masks */ -rn_lexobetter(m_arg, n_arg) - void *m_arg, *n_arg; +rn_lexobetter(void *m_arg, void *n_arg) { - register u_char *mp = m_arg, *np = n_arg, *lim; + u_char *mp = m_arg, *np = n_arg, *lim; if (LEN(mp) > LEN(np)) - return 1; /* not really, but need to check longer one first */ + return (1); /* not really, but need to check longer one first */ if (LEN(mp) == LEN(np)) for (lim = mp + LEN(mp); mp < lim;) if (*mp++ > *np++) - return 1; - return 0; + return (1); + return (0); } static struct radix_mask * -rn_new_radix_mask(tt, next) - register struct radix_node *tt; - register struct radix_mask *next; +rn_new_radix_mask(struct radix_node *tt, struct radix_mask *next) { - register struct radix_mask *m; + struct radix_mask *m; R_Malloc(m, struct radix_mask *, sizeof (struct radix_mask)); - if (m == 0) { + if (m == NULL) { log(LOG_ERR, "Failed to allocate route mask\n"); return (0); } @@ -616,17 +619,15 @@ rn_new_radix_mask(tt, next) m->rm_mask = tt->rn_mask; m->rm_mklist = next; tt->rn_mklist = m; - return m; + return (m); } struct radix_node * -rn_addroute(v_arg, n_arg, head, treenodes) - void *v_arg, *n_arg; - struct radix_node_head *head; - struct radix_node treenodes[2]; +rn_addroute(void *v_arg, void *n_arg, struct radix_node_head *head, + struct radix_node treenodes[2]) { caddr_t v = (caddr_t)v_arg, netmask = (caddr_t)n_arg; - register struct radix_node *t, *x = 0, *tt; + struct radix_node *t, *x = 0, *tt; struct radix_node *saved_tt, *top = head->rnh_treetop; short b = 0, b_leaf = 0; int keyduplicated; @@ -754,7 +755,7 @@ rn_addroute(v_arg, n_arg, head, treenodes) on2: /* Add new route to highest possible ancestor's list */ if ((netmask == 0) || (b > t->rn_bit )) - return tt; /* can't lift at all */ + return (tt); /* can't lift at all */ b_leaf = tt->rn_bit; do { x = t; @@ -778,29 +779,27 @@ on2: log(LOG_ERR, "Non-unique normal route, mask not entered\n"); #endif - return tt; + return (tt); } } else mmask = m->rm_mask; if (mmask == netmask) { m->rm_refs++; tt->rn_mklist = m; - return tt; + return (tt); } if (rn_refines(netmask, mmask) || rn_lexobetter(netmask, mmask)) break; } *mp = rn_new_radix_mask(tt, *mp); - return tt; + return (tt); } struct radix_node * -rn_delete(v_arg, netmask_arg, head) - void *v_arg, *netmask_arg; - struct radix_node_head *head; +rn_delete(void *v_arg, void *netmask_arg, struct radix_node_head *head) { - register struct radix_node *t, *p, *x, *tt; + struct radix_node *t, *p, *x, *tt; struct radix_mask *m, *saved_m, **mp; struct radix_node *dupedkey, *saved_tt, *top; caddr_t v, netmask; @@ -834,7 +833,7 @@ rn_delete(v_arg, netmask_arg, head) if (tt->rn_flags & RNF_NORMAL) { if (m->rm_leaf != tt || m->rm_refs > 0) { log(LOG_ERR, "rn_delete: inconsistent annotation\n"); - return 0; /* dangling ref could cause disaster */ + return (0); /* dangling ref could cause disaster */ } } else { if (m->rm_mask != tt->rn_mask) { @@ -986,17 +985,14 @@ out: * exit. */ static int -rn_walktree_from(h, a, m, f, w) - struct radix_node_head *h; - void *a, *m; - walktree_f_t *f; - void *w; +rn_walktree_from(struct radix_node_head *h, void *a, void *m, + walktree_f_t *f, void *w) { int error; struct radix_node *base, *next; u_char *xa = (u_char *)a; u_char *xm = (u_char *)m; - register struct radix_node *rn, *last = 0 /* shut up gcc */; + struct radix_node *rn, *last = NULL; /* shut up gcc */ int stopping = 0; int lastb; @@ -1089,18 +1085,15 @@ rn_walktree_from(h, a, m, f, w) } } - return 0; + return (0); } static int -rn_walktree(h, f, w) - struct radix_node_head *h; - walktree_f_t *f; - void *w; +rn_walktree(struct radix_node_head *h, walktree_f_t *f, void *w) { int error; struct radix_node *base, *next; - register struct radix_node *rn = h->rnh_treetop; + struct radix_node *rn = h->rnh_treetop; /* * This gets complicated because we may delete the node * while applying the function f to it, so we need to calculate @@ -1145,8 +1138,8 @@ rn_walktree(h, f, w) static int rn_inithead_internal(void **head, int off) { - register struct radix_node_head *rnh; - register struct radix_node *t, *tt, *ttt; + struct radix_node_head *rnh; + struct radix_node *t, *tt, *ttt; if (*head) return (1); R_Zalloc(rnh, struct radix_node_head *, sizeof (*rnh)); diff --git a/sys/net/radix.h b/sys/net/radix.h index 5423b2c..3554c77 100644 --- a/sys/net/radix.h +++ b/sys/net/radix.h @@ -119,9 +119,9 @@ struct radix_node_head { (void *v, void *mask, struct radix_node_head *head); 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 */ + struct radix_node *(*rnh_matchaddr) /* longest match for sockaddr */ (void *v, struct radix_node_head *head); - struct radix_node *(*rnh_lookup) /* locate based on sockaddr */ + struct radix_node *(*rnh_lookup) /*exact match for sockaddr*/ (void *v, void *mask, struct radix_node_head *head); struct radix_node *(*rnh_matchpkt) /* locate based on packet hdr */ (void *v, struct radix_node_head *head); diff --git a/sys/net/radix_mpath.c b/sys/net/radix_mpath.c index c87f13c..7a29069 100644 --- a/sys/net/radix_mpath.c +++ b/sys/net/radix_mpath.c @@ -151,6 +151,7 @@ rt_mpath_deldup(struct rtentry *headrt, struct rtentry *rt) /* * 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, @@ -158,76 +159,13 @@ rt_mpath_conflict(struct radix_node_head *rnh, struct rtentry *rt, { struct radix_node *rn, *rn1; struct rtentry *rt1; - char *p, *q, *eq; - int same, l, skip; rn = (struct radix_node *)rt; rn1 = rnh->rnh_lookup(rt_key(rt), netmask, rnh); if (!rn1 || rn1->rn_flags & RNF_ROOT) - return 0; - - /* - * unlike other functions we have in this file, we have to check - * all key/mask/gateway as rnh_lookup can match less specific entry. - */ - rt1 = (struct rtentry *)rn1; - - /* compare key. */ - if (rt_key(rt1)->sa_len != rt_key(rt)->sa_len || - bcmp(rt_key(rt1), rt_key(rt), rt_key(rt1)->sa_len)) - goto different; - - /* key was the same. compare netmask. hairy... */ - if (rt_mask(rt1) && netmask) { - skip = rnh->rnh_treetop->rn_offset; - if (rt_mask(rt1)->sa_len > netmask->sa_len) { - /* - * as rt_mask(rt1) is made optimal by radix.c, - * there must be some 1-bits on rt_mask(rt1) - * after netmask->sa_len. therefore, in - * this case, the entries are different. - */ - if (rt_mask(rt1)->sa_len > skip) - goto different; - else { - /* no bits to compare, i.e. same*/ - goto maskmatched; - } - } - - l = rt_mask(rt1)->sa_len; - if (skip > l) { - /* no bits to compare, i.e. same */ - goto maskmatched; - } - p = (char *)rt_mask(rt1); - q = (char *)netmask; - if (bcmp(p + skip, q + skip, l - skip)) - goto different; - /* - * need to go through all the bit, as netmask is not - * optimal and can contain trailing 0s - */ - eq = (char *)netmask + netmask->sa_len; - q += l; - same = 1; - while (eq > q) - if (*q++) { - same = 0; - break; - } - if (!same) - goto different; - } else if (!rt_mask(rt1) && !netmask) - ; /* no mask to compare, i.e. same */ - else { - /* one has mask and the other does not, different */ - goto different; - } - -maskmatched: + return (0); - /* key/mask were the same. compare gateway for all multipaths */ + /* key/mask are the same. compare gateway for all multipaths */ do { rt1 = (struct rtentry *)rn1; @@ -248,11 +186,10 @@ maskmatched: } /* all key/mask/gateway are the same. conflicting entry. */ - return EEXIST; + return (EEXIST); } while ((rn1 = rn_mpath_next(rn1)) != NULL); -different: - return 0; + return (0); } void diff --git a/sys/net/route.c b/sys/net/route.c index d99b0ab..015eccb 100644 --- a/sys/net/route.c +++ b/sys/net/route.c @@ -979,6 +979,57 @@ bad: return (error); } +#if 0 +int p_sockaddr(char *buf, int buflen, struct sockaddr *s); +int rt_print(char *buf, int buflen, struct rtentry *rt); + +int +p_sockaddr(char *buf, int buflen, struct sockaddr *s) +{ + void *paddr = NULL; + + switch (s->sa_family) { + case AF_INET: + paddr = &((struct sockaddr_in *)s)->sin_addr; + break; + case AF_INET6: + paddr = &((struct sockaddr_in6 *)s)->sin6_addr; + break; + } + + if (paddr == NULL) + return (0); + + if (inet_ntop(s->sa_family, paddr, buf, buflen) == NULL) + return (0); + + return (strlen(buf)); +} + +int +rt_print(char *buf, int buflen, struct rtentry *rt) +{ + struct sockaddr *addr, *mask; + int i = 0; + + addr = rt_key(rt); + mask = rt_mask(rt); + + i = p_sockaddr(buf, buflen, addr); + if (!(rt->rt_flags & RTF_HOST)) { + buf[i++] = '/'; + i += p_sockaddr(buf + i, buflen - i, mask); + } + + if (rt->rt_flags & RTF_GATEWAY) { + buf[i++] = '>'; + i += p_sockaddr(buf + i, buflen - i, rt->rt_gateway); + } + + return (i); +} +#endif + #ifdef RADIX_MPATH static int rn_mpath_update(int req, struct rt_addrinfo *info, @@ -992,10 +1043,11 @@ rn_mpath_update(int req, struct rt_addrinfo *info, register struct radix_node *rn; int error = 0; - rn = rnh->rnh_matchaddr(dst, rnh); + rn = rnh->rnh_lookup(dst, netmask, rnh); if (rn == NULL) return (ESRCH); rto = rt = RNTORT(rn); + rt = rt_mpath_matchgate(rt, gateway); if (rt == NULL) return (ESRCH); @@ -1555,8 +1607,7 @@ rtinit1(struct ifaddr *ifa, int cmd, int flags, int fibnum) rn = rnh->rnh_lookup(dst, netmask, rnh); error = (rn == NULL || (rn->rn_flags & RNF_ROOT) || - RNTORT(rn)->rt_ifa != ifa || - !sa_equal((struct sockaddr *)rn->rn_key, dst)); + RNTORT(rn)->rt_ifa != ifa); RADIX_NODE_HEAD_RUNLOCK(rnh); if (error) { /* this is only an error if bad on ALL tables */ diff --git a/sys/net/rtsock.c b/sys/net/rtsock.c index bacd393..af51ac6 100644 --- a/sys/net/rtsock.c +++ b/sys/net/rtsock.c @@ -725,10 +725,24 @@ route_output(struct mbuf *m, struct socket *so) info.rti_info[RTAX_DST]->sa_family); if (rnh == NULL) senderr(EAFNOSUPPORT); + RADIX_NODE_HEAD_RLOCK(rnh); - rt = (struct rtentry *) rnh->rnh_lookup(info.rti_info[RTAX_DST], - info.rti_info[RTAX_NETMASK], rnh); - if (rt == NULL) { /* XXX looks bogus */ + + if (info.rti_info[RTAX_NETMASK] == NULL && + rtm->rtm_type == RTM_GET) { + /* + * Provide logest prefix match for + * address lookup (no mask). + * 'route -n get addr' + */ + rt = (struct rtentry *) rnh->rnh_matchaddr( + info.rti_info[RTAX_DST], rnh); + } else + rt = (struct rtentry *) rnh->rnh_lookup( + info.rti_info[RTAX_DST], + info.rti_info[RTAX_NETMASK], rnh); + + if (rt == NULL) { RADIX_NODE_HEAD_RUNLOCK(rnh); senderr(ESRCH); } @@ -785,25 +799,6 @@ route_output(struct mbuf *m, struct socket *so) RT_ADDREF(rt); RADIX_NODE_HEAD_RUNLOCK(rnh); - /* - * Fix for PR: 82974 - * - * RTM_CHANGE/LOCK need a perfect match, rn_lookup() - * returns a perfect match in case a netmask is - * specified. For host routes only a longest prefix - * match is returned so it is necessary to compare the - * existence of the netmask. If both have a netmask - * rnh_lookup() did a perfect match and if none of them - * have a netmask both are host routes which is also a - * perfect match. - */ - - if (rtm->rtm_type != RTM_GET && - (!rt_mask(rt) != !info.rti_info[RTAX_NETMASK])) { - RT_UNLOCK(rt); - senderr(ESRCH); - } - switch(rtm->rtm_type) { case RTM_GET: |