/* * Gated Release 4.x, 5.x, 6.x, 7.x * * Copyright (c) 1996,1997,1998 The Regents of the University of Michigan. * All Rights Reserved. * * License to use, copy, modify, and distribute this software and its * documentation can be obtained from Merit at the University of Michigan. * * Merit GateDaemon Project * 4251 Plymouth Road, Suite C * Ann Arbor, MI 48105 * * THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER * EXPRESS OR IMPLIED, INCLUDING WITHOUT LIMITATION WARRANTIES OF * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE REGENTS OF THE * UNIVERSITY OF MICHIGAN AND MERIT DO NOT WARRANT THAT THE FUNCTIONS * CONTAINED IN THE SOFTWARE WILL MEET LICENSEE'S REQUIREMENTS OR THAT * OPERATION WILL BE UNINTERRUPTED OR ERROR FREE. The Regents of the * University of Michigan and Merit shall not be liable for any special, * indirect, incidental or consequential damages with respect to any claim * by Licensee or any third party arising from use of the software. * GateDaemon was originated and developed through release 3.0 by Cornell * University and its collaborators. * * Please forward bug fixes, enhancements and questions to the * gated mailing list: gated-people@gated.merit.edu. * * This copyright has ben automatically added by util/addcopyright.pl. * __END_OF_COPYRIGHT__ */ /* * Copyright (c) 1997 by the University of Southern California. * All rights reserved. * * Permission to use, copy, modify, and distribute this software and * its documentation in source and binary forms for lawful * non-commercial purposes and without fee is hereby granted, provided * that the above copyright notice appear in all copies and that both * the copyright notice and this permission notice appear in supporting * documentation, and that any documentation, advertising materials, * and other materials related to such distribution and use acknowledge * that the software was developed by the University of Southern * California and/or Information Sciences Institute. * The name of the University of Southern California may not * be used to endorse or promote products derived from this software * without specific prior written permission. * * THE UNIVERSITY OF SOUTHERN CALIFORNIA DOES NOT MAKE ANY REPRESENTATIONS * ABOUT THE SUITABILITY OF THIS SOFTWARE FOR ANY PURPOSE. THIS SOFTWARE IS * PROVIDED "AS IS" AND WITHOUT ANY EXPRESS OR IMPLIED WARRANTIES, * INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, TITLE, AND * NON-INFRINGEMENT. * * IN NO EVENT SHALL USC, OR ANY OTHER CONTRIBUTOR BE LIABLE FOR ANY * SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES, WHETHER IN CONTRACT, * TORT, OR OTHER FORM OF ACTION, ARISING OUT OF OR IN CONNECTION WITH, * THE USE OR PERFORMANCE OF THIS SOFTWARE. * * Questions concerning this software should be directed to * eddy@isi.edu. * * $Id: mrt.c,v 1.29 1998/11/21 03:47:52 eddy Exp $ */ /* * The merit copyright covers the basic algorithms derived from * rt_radix.c, the USC copyright applys the multicast route table * adaptation of the radix trie algorithms. */ /* * the routing table is such that a single trie * will contain all groups, with a default for (*, *, RP) * Each radix_node has a pointer to a group struct, that contains * all the vitals for that group including a pointer to a secondary * radix trie for all sources to that group, with (*, G) as a default * of the secondary radix trie. * * the radix_node and radix_tree structures will be used for both * the group and source. this is done by providing a shared struct * for external nodes. external contains the addr/mask for the node, * and a pointer to the group or source specific info, for it's given * key. */ #define INCLUDE_MROUTE #define INCLUDE_ROUTE #define INCLUDE_IOCTL #define INCLUDE_IF #define INCLUDE_SOCKIO #define INCLUDE_MROUTE_KERNEL #include "include.h" #ifdef IP_MULTICAST_ROUTING #ifdef PROTO_INET #include "inet.h" #endif /* PROTO_INET */ #ifdef PROTO_ISO #include "iso.h" #endif /* PROTO_ISO */ #include "mrt.h" #include "mbr.h" #include "igmp.h" extern task *krt_task; static block_t mrt_node_block_index; static block_t mrt_src_block_index; static block_t mrt_grp_block_index; static block_t mrt_addr_block_index; static block_t mrt_table_block_index; static block_t mrt_downstream_block_index; static block_t mrt_upstream_block_index; static block_t mrt_char_block_index; static block_t mrt_src_list_block_index; static block_t mrt_grp_list_block_index; block_t addr_list_block_index; sockaddr_un *mrt_wildcard; /* 224.0.0.0 */ sockaddr_un *mrt_wildcard_mask; /* /4 */ int mrt_wildcard_masklen; /********************************************************************* downstream: XXX: most of these should be MACROS(). ********************************************************************/ mrt_addr_t * mrt_addr_alloc () { return (mrt_addr_t *) task_block_alloc (mrt_addr_block_index); } void mrt_addr_free(node) mrt_addr_t *node; { task_block_free(mrt_addr_block_index, node); } downstream_t * mrt_downstream_alloc() { downstream_t *ds; ds = (downstream_t *) task_block_alloc (mrt_downstream_block_index); bzero ((char *) ds, sizeof (downstream_t)); ds->ds_ctime = ds->ds_rtime; ds->ds_count++; return ds; } downstream_t * mrt_downstream_create () { downstream_t *ds = mrt_downstream_alloc(); ds->forw = ds->back = ds; ds->ds_ctime = ds->ds_rtime = time_sec; return ds; } void mrt_downstream_free(ds) downstream_t *ds; { IFA_FREE(ds->ds_ifap); task_block_free(mrt_downstream_block_index, ds); } void mrt_downstream_delete_list (list) downstream_t *list; { downstream_t *gonner; for (gonner = list->forw; gonner != list; gonner = list->forw) { DOWNSTREAM_DEQ (gonner); mrt_downstream_free(gonner); } } downstream_t * mrt_downstream_dup (downstream_t *ds) { downstream_t *dp; dp = mrt_downstream_create(); IFA_ALLOC (dp->ds_ifap = ds->ds_ifap); dp->ds_protos = ds->ds_protos; return dp; } /* * XXX: what should we do if to is !NULL? we'll just * append from to to. * * ifap is an interface to exclude from the dup list, typically * the iif of the newly created entry. return the size * of the dup'd list. */ int mrt_downstream_copy (top, from, ifap) downstream_t **top; /* in/out: to pointer, list to be copied to */ downstream_t *from; /* in: the list to be copied from */ if_addr *ifap; /* in: ifap to be excluded from the dup */ { downstream_t *nds, *ds, *to; int count = 0; if (!*top) to = mrt_downstream_create(); else to = *top; /* empty the old list */ if (to != to->forw) mrt_downstream_delete_list (to); DOWNSTREAM_LIST(ds, from) { if (ifap && ds->ds_ifap == ifap) continue; nds = mrt_downstream_create(); IFA_ALLOC(nds->ds_ifap = ds->ds_ifap); nds->ds_protos = ds->ds_protos; nds->ds_data = ds->ds_data; DOWNSTREAM_ENQ (nds, to->back); count++; } DOWNSTREAM_LIST_END(ds, from); *top = to; return count; } /* * return the number of new items added. we traverse both to and * from until we hit the end. XXX: warning ds_data does not get * copied!!! */ int mrt_downstream_merge (top, from, ifap) downstream_t **top; downstream_t *from; if_addr *ifap; { downstream_t *to, *src, *dst, *new; int count = 0; to = *top; if (!to) { /* just dup and return */ return mrt_downstream_copy(top, from, ifap); } /* * walk the source list adding if necessary each element. * the lists are sorted according to ascending ip address. */ for (src = from->forw, dst = to->forw; src != from; src = src->forw) { int cmp = (dst == to) ? 1 : sockaddrcmp2 (IFA_UNIQUE_ADDR(src->ds_ifap), IFA_UNIQUE_ADDR(dst->ds_ifap)); if (cmp == 1) { /* src is smaller or to is at the end, we can dup src and add it to to */ new = mrt_downstream_create(); IFA_ALLOC(new->ds_ifap = src->ds_ifap); new->ds_protos = src->ds_protos; new->ds_holdtime = src->ds_holdtime; new->ds_timeout = src->ds_timeout; count++; DOWNSTREAM_ENQ(new, dst->back); } } return count; } int mrt_downstream_cmp (s, d) downstream_t *s; downstream_t *d; { downstream_t *ds, *nds = d->forw; DOWNSTREAM_LIST (ds, s) { if (ds->ds_ifap != nds->ds_ifap) break; nds = nds->forw; } DOWNSTREAM_LIST_END (ds, s); if (!ds && nds->ds_ifap == NULL) return TRUE; return FALSE; } downstream_t * /* OUT: downstream entry for iface, or NULL if not found */ find_downstream_ifap(src, ifap) source_t *src; /* IN: source entry */ if_addr *ifap; /* IN: interface to find */ { register downstream_t *dp; DOWNSTREAM_LIST (dp, src->src_downstream) { if (dp->ds_ifap == ifap) return dp; } DOWNSTREAM_LIST_END (dp, src->src_downstream); return NULL; } addr_list * mrt_addr_list_alloc() { addr_list *dl = (addr_list *) task_block_alloc (addr_list_block_index); dl->forw = (addr_list *) 0; dl->addr = (sockaddr_un *) 0; dl->mask = (sockaddr_un *) 0; return dl; } void mrt_addr_list_delete(addr_list *alist) { addr_list *a = alist; while (a = alist) { alist = alist->forw; if (a->addr) sockfree (a->addr); task_block_free(addr_list_block_index, a); } } mrt_src_list_t * mrt_src_list_alloc() { mrt_src_list_t *s = (mrt_src_list_t *) task_block_alloc (mrt_src_list_block_index); s->forw = s->back = s; s->src = (source_t *) 0; return s; } void mrt_src_list_free (item) mrt_src_list_t *item; { task_block_free(mrt_src_list_block_index, item); } mrt_grp_list_t * mrt_grp_list_alloc() { mrt_grp_list_t *s = (mrt_grp_list_t *) task_block_alloc (mrt_grp_list_block_index); s->forw = s->back = s; s->grp = (group_t *) 0; return s; } void mrt_grp_list_free (item) mrt_grp_list_t *item; { task_block_free(mrt_grp_list_block_index, item); } mrt_src_list_t * mrt_src_find (source_t *src, mrt_src_list_t *slist) { mrt_src_list_t *s; MRT_SRC_LIST(s, slist) { if (s->src == src) break; } MRT_SRC_LIST_END(s, slist); return s; } /********************************************************************* Node source and group. these can be macroized. ********************************************************************/ static mrt_node_t * mrt_node_alloc () { return (mrt_node_t *) task_block_alloc (mrt_node_block_index); } static void mrt_node_free (node) mrt_node_t *node; { task_block_free(mrt_node_block_index, node); } static source_t * mrt_src_alloc() { source_t *src; src = (source_t *) task_block_alloc (mrt_src_block_index); return src; } char * psrc (source_t *src) { static buf[80]; sprintf ((char *) &buf, "(%A/%d, %A/%d)\0", src->addr, inet_prefix_mask (src->mask), src->src_gaddr, inet_prefix_mask(src->src_gmask)); return (char *) &buf; } static void mrt_src_free(src) source_t *src; { task_block_free(mrt_src_block_index, src); } void mrt_source_delete(src) source_t *src; { downstream_t *ds; int i; trace_tp (krt_task, TR_ROUTE, 0, ("MRT src delete: (%A, %A)", src->addr, src->src_gaddr)); mrt_downstream_delete_list (src->src_downstream); for (i = 0; i < MAXVIFS; i++) { ds = src->src_dstable[i]; if (ds) { IFA_FREE(ds->ds_ifap); assert (!ds->ds_data); /* proto must remove this */ } } mrt_table_remove (src->src_group->grp_srcs, (mrt_addr_t *) src); sockfree(src->addr); if (src->src_upstream) mrt_upstream_delete(src->src_upstream); mrt_src_free(src); } static group_t * mrt_group_alloc() { return (group_t *) task_block_alloc (mrt_grp_block_index); } static void mrt_group_free(grp) group_t *grp; { task_block_free(mrt_grp_block_index, (void_t) grp); } void mrt_group_delete(grp) group_t *grp; { source_t *src; MRT_WALK(grp->grp_srcs, src) { mrt_source_delete (src); } MRT_WALK_END(grp->grp_srcs, src); mrt_table_remove (grp->grp_table, (mrt_addr_t *) grp); sockfree(grp->addr); mrt_group_free(grp); } upstream_t * mrt_upstream_alloc() { return (upstream_t *) task_block_alloc (mrt_upstream_block_index); } void mrt_upstream_delete(up) upstream_t *up; { if (!up) return; if (up->ifap) IFA_FREE(up->ifap); if (up->nbr) sockfree(up->nbr); task_block_free(mrt_upstream_block_index, up); } upstream_t * mrt_upstream_dup(up) upstream_t *up; { upstream_t *new; if (!up || !up->ifap) { return (upstream_t *) 0; } new = mrt_upstream_alloc(); memcpy (new, up, sizeof (upstream_t)); if (up->nbr) new->nbr = sockdup(up->nbr); if (up->ifap) IFA_ALLOC(up->ifap); return new; } /* * This program not only allocs the mrt_table struct, it also * adds it to the linked list of all mrt tables (XXX nolonger used) */ mrt_table_t * mrt_table_create(tp, af, name) task *tp; int af; const char *name; { mrt_table_t *mrt, *t; mrt = (mrt_table_t *) task_block_alloc (mrt_table_block_index); mrt->mrt_head = (mrt_node_t *) 0; mrt->mrt_inodes = 0; mrt->mrt_routes = 0; mrt->mrt_sinfo = &(sock_info[af]); /* sock info */ mrt->mrt_name = (char *) task_block_alloc (mrt_char_block_index); mrt->mrt_task = tp; strcpy (mrt->mrt_name, name); return mrt; } void mrt_table_delete(mrt) mrt_table_t *mrt; { group_t *grp; source_t *src; mrt_src_list_t *deathlist, *gonner; mrt_grp_list_t *glist, *g; mrt_node_t *gnode, *snode; /* * we'll walk the table gathering all sources and groups * into respective gonner lists and kill them off afterwords. */ deathlist = mrt_src_list_alloc(); glist = mrt_grp_list_alloc(); gnode = mrt->mrt_head; MRT_GRP_WALK(gnode, grp) { snode = grp->grp_srcs->mrt_head; MRT_SRC_WALK (snode, (void_t) src) { MRT_SRC_LIST_ADD(src, deathlist); } MRT_SRC_WALK_END (snode, src); MRT_GRP_LIST_ADD(grp, glist); } MRT_GRP_WALK_END(gnode, grp); for (gonner = (mrt_src_list_t *) deathlist->forw; deathlist != deathlist->forw; gonner = deathlist->forw) { mrt_source_delete (gonner->src); MRT_SRC_LIST_DELETE(gonner); } /* we should not have any nodes remaining on the source trie */ for (g = (mrt_grp_list_t *) glist->forw; glist != glist->forw; g = glist->forw) { assert(g->grp->grp_srcs->mrt_inodes == 0); mrt_group_delete (g->grp); MRT_GRP_LIST_DELETE(g); } assert (mrt->mrt_inodes == 0); task_block_free (mrt_table_block_index, (void_t) mrt); } void mrt_init() { mrt_node_block_index = task_block_init (sizeof (mrt_node_t), "mrt_node"); mrt_src_block_index = task_block_init (sizeof (source_t), "mrt_src"); mrt_grp_block_index = task_block_init (sizeof (group_t), "mrt_grp"); mrt_addr_block_index = task_block_init (sizeof (mrt_addr_t), "mrt_addr"); mrt_table_block_index= task_block_init (sizeof (mrt_table_t), "mrt_table"); mrt_downstream_block_index = task_block_init (sizeof (downstream_t), "mrt_downstream"); mrt_upstream_block_index = task_block_init (sizeof (upstream_t), "mrt_upstream"); mrt_char_block_index = task_block_init (sizeof (char) * 80, "char"); mrt_src_list_block_index = task_block_init (sizeof (mrt_src_list_t), "src_list"); mrt_grp_list_block_index = task_block_init (sizeof (mrt_grp_list_t), "grp_list"); addr_list_block_index = task_block_init (sizeof (addr_list), "src_list"); mrt_wildcard = sockdup(sockbuild_in(0, htonl(MRT_WILDCARD))); mrt_wildcard_mask = inet_masks[mrt_wildcard_masklen]; } void mrt_terminate() { } /* * return the radix node for the best match. returning the radix node * allows the caller to traverse back up to the root of the tree, * providing all possible matches beggining with the most specific */ mrt_node_t * /* out: radix node, NULL if none */ mrt_match_node(mrt,dst) mrt_table_t *mrt; /* in: radix table */ sockaddr_un *dst; /* in: destination to be best matched */ { register mrt_node_t *rn, **sp; register byte *ap, *ap2; register u_short bitlen, dbit; mrt_node_t *stack[MAXDEPTH]; struct sock_info *si; if (!(rn = mrt->mrt_head)) { return (mrt_node_t *) NULL; } si = mrt->mrt_sinfo; ap = RN_ADDR(dst, si->si_offset); /* * search the tree recording all the nodes we cross on the * way down. */ sp = stack; while (rn) { if (rn->rn_ext) { *sp++ = rn; } if (rn->rn_tbit == 0) { break; } if (ap[rn->rn_tbyte] & rn->rn_tbit) { rn = rn->rn_right; } else { rn = rn->rn_left; } } /* * Take the last guy on the stack (there is guaranteed to * be at least one) and compute the first bit different. We * won't match a node with a bit number larger than this. */ rn = *(--sp); bitlen = rn->rn_bit; ap2 = RN_ADDR(((mrt_addr_t *) rn->rn_ext)->addr, si->si_offset); for (dbit = 0; dbit < bitlen; dbit += RNBBY) { if (*ap != *ap2) { dbit += first_bit_set[*ap ^ *ap2]; break; } ap++; ap2++; } /* * Throw anyone off the stack with a bit number larger than this. */ for (; rn->rn_bit > dbit; rn = *(--sp)) { if (sp == stack) { return (mrt_node_t *) 0; } } return rn; } /* * return the radix node for the best match with mask >= mask. returning the * radix node allows the caller to traverse back up to the root of the tree, * providing all possible matches beggining with the most specific. Note mask * must come from the inet_masks */ mrt_node_t * /* out: radix node, NULL if none */ mrt_match_node_mask(mrt, addr, mask) mrt_table_t *mrt; /* in: radix table */ sockaddr_un *addr; /* in: destination to be best matched */ sockaddr_un *mask; { register mrt_node_t *rn, **sp; register byte *ap, *ap2; register u_short bitlen, dbit; mrt_node_t *stack[MAXDEPTH]; struct sock_info *si; if (!(rn = mrt->mrt_head)) { return (mrt_node_t *) NULL; } /* ensure mask is a pointer from inet_masks */ assert (inet_mask_default <= mask || mask <= inet_mask_host); si = mrt->mrt_sinfo; ap = RN_ADDR(addr, si->si_offset); /* * search the tree recording all the nodes we cross on the * way down, begining when the mask <= the mask of the node * on the tree. */ sp = stack; while (rn) { if (rn->rn_ext) { *sp++ = rn; } if (rn->rn_tbit == 0) { break; } if (ap[rn->rn_tbyte] & rn->rn_tbit) { rn = rn->rn_right; } else { rn = rn->rn_left; } } /* * Take the last guy on the stack (there is guaranteed to * be at least one) and compute the first bit different. We * won't match a node with a bit number larger than this. */ rn = *(--sp); bitlen = rn->rn_bit; ap2 = RN_ADDR(((mrt_addr_t *) rn->rn_ext)->addr, si->si_offset); for (dbit = 0; dbit < bitlen; dbit += RNBBY) { if (*ap != *ap2) { dbit += first_bit_set[*ap ^ *ap2]; break; } ap++; ap2++; } /* * Throw anyone off the stack with a bit number larger than this. */ for (; rn->rn_bit > dbit; rn = *(--sp)) { if (sp == stack) { return (mrt_node_t *) 0; } } return rn; } /* This does a longest match on the group and source */ source_t * /* out: matched source node, NULL if none */ mrt_longest_match_source(mrt, gaddr, saddr) mrt_table_t *mrt; /* in: mrt table */ sockaddr_un *gaddr; /* in: group addr to be best matched */ sockaddr_un *saddr; /* in: source addr to be best matched */ { mrt_node_t *rn; source_t *src = (source_t *) 0; /* * lookup the node coresponding to the group */ rn = mrt_match_node (mrt, gaddr); if (!rn) { return (source_t *) NULL; } /* * look for a node with an external pointer */ while (rn && !rn->rn_ext) { rn = rn->rn_parent; } if (rn && rn->rn_ext) { group_t *grp = (group_t *) rn->rn_ext; if (grp->grp_srcs) { mrt_node_t *nn; nn = mrt_match_node(grp->grp_srcs, saddr); while (nn && !nn->rn_ext) { nn = nn->rn_parent; } if (nn && nn->rn_ext) { src = nn->rn_ext; } } } return src; } /* * exact match extern (can be source_t, group_t, addr_t) * return the external node NULL if */ void * mrt_locate_mask(mrt, dst, mask) mrt_table_t *mrt; /* in: table */ sockaddr_un *dst; /* in: dest */ sockaddr_un *mask; /* in: mask */ { register mrt_node_t *rn; register byte *ap, *ap2; register u_short bitlen; register struct sock_info *si; void *ext; if (!mrt || !(rn = mrt->mrt_head)) { trace_tp (krt_task, TR_ROUTE, 0, ("mrt_locate_mask: mrt %s empty", mrt->mrt_name)); return (void *) NULL; } /* * Compute the bit length of the mask. */ si = mrt->mrt_sinfo; bitlen = mask_to_prefix_si(si, mask); assert(bitlen != (u_short) -1); /* * Search down the tree until we find a node which * has a bit number the same as ours. */ ap = RN_ADDR(dst, si->si_offset); while (rn->rn_bit < bitlen) { if (rn->rn_tbit & ap[rn->rn_tbyte]) { rn = rn->rn_right; } else { rn = rn->rn_left; } if (!rn) { break; } } /* * If we didn't find an exact bit length match, we're gone. * If there is no ext on this node, we're gone too. */ if (!rn || rn->rn_bit != bitlen || !(ext = rn->rn_ext)) { return (void *) 0; } /* * So far so good. Fetch the address and see if we have an * exact match. */ ap2 = RN_ADDR((((mrt_addr_t *) ext)->addr), si->si_offset); bitlen = RN_BYTELEN(bitlen); while (bitlen--) { if (*ap++ != *ap2++) { return (void *) 0; } } return ext; } void * mrt_locate(mrt, dst) mrt_table_t *mrt; sockaddr_un *dst; { sockaddr_un *mask; mask = (sockaddrcmp(dst, inet_addr_default)) ? inet_mask_default : inet_mask_host; return (mrt_locate_mask(mrt, dst, mask)); } /* * This routine will find the group, then the source for the * includes. */ source_t * mrt_locate_source_mask(mrt, gaddr, gmask, saddr, smask) mrt_table_t *mrt; sockaddr_un *gaddr; sockaddr_un *gmask; sockaddr_un *saddr; sockaddr_un *smask; { source_t *src = (source_t *) 0; group_t *grp; grp = mrt_locate_group_mask (mrt, gaddr, gmask); if (!grp) { return src; } src = (source_t *) mrt_locate_mask (grp->grp_srcs, saddr, smask); return src; } /* This does an exact match on the group and source */ source_t * mrt_locate_source(mrt, gaddr, saddr) mrt_table_t *mrt; sockaddr_un *gaddr; sockaddr_un *saddr; { group_t *grp; grp = mrt_locate_group(mrt, gaddr); if (!grp) { return (source_t *) 0; } return (source_t *) mrt_locate (grp->grp_srcs, saddr); } /* * Locate the parent rt_head for the given rt_head */ void * mrt_locate_parent (ext) void *ext; { mrt_node_t *up = ((mrt_addr_t *) ext)->node->rn_parent; while (up && !up->rn_ext) up = up->rn_parent; return up ? up->rn_ext : (void *) 0; } /* remove an ext from the tree */ void mrt_table_remove (mrt, ext) mrt_table_t *mrt; mrt_addr_t *ext; { mrt_node_t *rn, *rn_next, *rn_prev; mrt->mrt_routes--; rn = ext->node; ext->node = (mrt_node_t *) 0; #ifdef MRT_WALK_STRUCTS /* * find all the rtwalk_t structures pointing at this node, and update * their pointer. */ rt_walk_delfix(rth); #endif MRT_WALK_STRUCTS /* * Catch the easy case. If this guy has nodes on both his left * and right, he stays in the tree. */ if (rn->rn_left && rn->rn_right) { rn->rn_ext = (mrt_node_t *) 0; return; } /* * If this guy has no successor he's a goner. The guy above * him will be too, unless he's got external stuff attached to * him. */ if (!(rn->rn_left) && !(rn->rn_right)) { rn_prev = rn->rn_parent; mrt_node_free (rn); mrt->mrt_inodes--; if (!rn_prev) { /* Last guy in the tree, remove the root node pointer */ mrt->mrt_head = (mrt_node_t *) 0; return; } if (rn_prev->rn_left == rn) { rn_prev->rn_left = (mrt_node_t *) 0; } else { assert (rn_prev->rn_right == rn); rn_prev->rn_right = (mrt_node_t *) 0; } if (rn_prev->rn_ext) { return; } rn = rn_prev; } /* * Here we have a one-way brancher with no external stuff attached * (either we just removed the external stuff or one of his child * nodes). Remove him, promoting his one remaining child. */ rn_prev = rn->rn_parent; if (rn->rn_left) { rn_next = rn->rn_left; } else { rn_next = rn->rn_right; } rn_next->rn_parent = rn_prev; if (!rn_prev) { /* new root node put it in. */ mrt->mrt_head = rn_next; } else { /* * Find the pointer to our guy in the parent and replace * it with the pointer to our former child. */ if (rn_prev->rn_left == rn) { rn_prev->rn_left = rn_next; } else { assert(rn_prev->rn_right == rn); rn_prev->rn_right = rn_next; } } mrt_node_free (rn); mrt->mrt_inodes--; } /* * Insert this ext into the tree */ void mrt_table_add (mrt, ext) mrt_table_t *mrt; mrt_addr_t *ext; { register mrt_node_t *rn, *rn_prev, *rn_add, *rn_new; register u_short bitlen, bits2chk, dbit; register byte *addr, *his_addr; register u_int i; struct sock_info *si; assert(mrt); trace_tp (krt_task, TR_ROUTE, 0, ("mrt_table_add (%s): adding %A/%d", mrt->mrt_name, ext->addr, inet_prefix_mask(ext->mask))); /* Compute the bit length of the mask. */ si = mrt->mrt_sinfo; bitlen = mask_to_prefix_si(si, ext->mask); assert(bitlen != (u_short) -1); rn_prev = mrt->mrt_head; mrt->mrt_routes++; /* * If there is no existing root node, this is it. Catch this * case now. */ if (!rn_prev) { rn = (mrt_node_t *) mrt_node_alloc(); mrt->mrt_head = ((mrt_addr_t *) ext)->node = rn; RN_SETBIT(rn, bitlen, ((mrt_addr_t *) ext)->mask == si->si_mask_max); rn->rn_ext = ext; mrt->mrt_inodes++; return; } /* * Search down the tree as far as we can, stopping at a node * with a bit number >= ours which has an ext attached. It * is possible we won't get down the tree this far, however, * so deal with that as well. */ addr = RN_ADDR(((mrt_addr_t *)ext)->addr, si->si_offset); rn = rn_prev; while (rn->rn_bit < bitlen || !(rn->rn_ext)) { if (BIT_TEST(addr[rn->rn_tbyte], rn->rn_tbit)) { if (!(rn->rn_right)) { break; } rn = rn->rn_right; } else { if (!(rn->rn_left)) { break; } rn = rn->rn_left; } } /* * Now we need to find the number of the first bit in our address * which differs from his address. */ bits2chk = MIN(rn->rn_bit, bitlen); his_addr = RN_ADDR(((mrt_addr_t *)rn->rn_ext)->addr, si->si_offset); for (dbit = 0; dbit < bits2chk; dbit += RNBBY) { i = dbit >> RNSHIFT; if (addr[i] != his_addr[i]) { dbit += first_bit_set[addr[i] ^ his_addr[i]]; break; } } /* * If the different bit is less than bits2chk we will need to * insert a split above him. Otherwise we will either be in * the tree above him, or attached below him. */ if (dbit > bits2chk) { dbit = bits2chk; } rn_prev = rn->rn_parent; while (rn_prev && rn_prev->rn_bit >= dbit) { rn = rn_prev; rn_prev = rn->rn_parent; } /* * Okay. If the node rn points at is equal to our bit number, we * may just be able to attach the ext to him. Check this since it * is easy. */ if (dbit == bitlen && rn->rn_bit == bitlen) { assert(!(rn->rn_ext)); rn->rn_ext = ext; ((mrt_addr_t *) ext)->node = rn; return; } /* * Allocate us a new node, we are sure to need it now. */ rn_add = mrt_node_alloc(); mrt->mrt_inodes++; RN_SETBIT(rn_add, bitlen, (((mrt_addr_t *) ext)->addr == si->si_mask_max)); rn_add->rn_ext = ext; ext->node = rn_add; /* * There are a couple of possibilities. The first is that we * attach directly to the thing pointed to by rn. This will be * the case if his bit is equal to dbit. */ if (rn->rn_bit == dbit) { assert(dbit < bitlen); rn_add->rn_parent = rn; if (BIT_TEST(addr[rn->rn_tbyte], rn->rn_tbit)) { assert(!(rn->rn_right)); rn->rn_right = rn_add; } else { assert(!(rn->rn_left)); rn->rn_left = rn_add; } return; } /* * The other case where we don't need to add a split is where * we were on the same branch as the guy we found. In this case * we insert rn_add into the tree between rn_prev and rn. Otherwise * we add a split between rn_prev and rn and append the node we're * adding to one side of it. */ if (dbit == bitlen) { if (BIT_TEST(his_addr[rn_add->rn_tbyte], rn_add->rn_tbit)) { rn_add->rn_right = rn; } else { rn_add->rn_left = rn; } rn_new = rn_add; } else { rn_new = (mrt_node_t *) task_block_alloc(mrt_node_block_index); mrt->mrt_inodes++; RN_SETBIT(rn_new, dbit, FALSE); rn_add->rn_parent = rn_new; if (BIT_TEST(addr[rn_new->rn_tbyte], rn_new->rn_tbit)) { rn_new->rn_right = rn_add; rn_new->rn_left = rn; } else { rn_new->rn_left = rn_add; rn_new->rn_right = rn; } } rn->rn_parent = rn_new; rn_new->rn_parent = rn_prev; /* * If rn_prev is NULL this is a new root node, otherwise it * is attached to the guy above in the place where rn was. */ if (!rn_prev) { mrt->mrt_head = rn_new; } else if (rn_prev->rn_right == rn) { rn_prev->rn_right = rn_new; } else { assert(rn_prev->rn_left == rn); rn_prev->rn_left = rn_new; } } /* * this function will look for the requested group and return * the corresponding group_t, an entry will be created if not * found */ group_t * mrt_create_group_mask(mrt, gaddr, gmask) mrt_table_t *mrt; sockaddr_un *gaddr; sockaddr_un *gmask; { group_t *grp; char str[80]; /* * need to do some sanity checks. Is this a mcast addr? */ grp = mrt_locate_mask (mrt, gaddr, gmask); if (!grp) { grp = mrt_group_alloc(); grp->addr = sockdup (gaddr); grp->mask = gmask; grp->node = (mrt_node_t *) 0; mrt_table_add(mrt, (mrt_addr_t *) grp); sprintf ((char *) str, "Sources for Group: %A\0", gaddr); grp->grp_srcs = mrt_table_create (mrt->mrt_task, socktype(inet_mask_host), str); grp->grp_table = mrt; } return (grp); } group_t * mrt_create_group(mrt, gaddr) mrt_table_t *mrt; sockaddr_un *gaddr; { return mrt_create_group_mask(mrt, gaddr, inet_mask_host); } source_t * mrt_create_source_mask(grp, saddr, mask) group_t *grp; sockaddr_un *saddr; sockaddr_un *mask; { mrt_table_t *mrt = grp->grp_srcs; source_t *src; if (!mrt) { char str[256]; sprintf ((char *) str, "Source for Group: %A\n", grp->addr); mrt = mrt_table_create (mrt->mrt_task, socktype(inet_addr_default), (char *) str); } src = mrt_locate_mask (mrt, saddr, mask); if (!src) { upstream_t *up; src = mrt_src_alloc(); src->addr = sockdup (saddr); src->mask = mask; src->src_group = grp; src->src_downstream = mrt_downstream_create (); /* * XXX: This is protocol specific and really should not * be done here, but in the protocol itself. we can: * leave it alone since most protocols will do it anyway, * and let those that must change it deal with it, or * remove it and verify nothing breaks... */ if (!sockaddrcmp_in (inet_addr_default, saddr)) { src->src_upstream = mrt_upstream_dup (mbr_locate_upstream(saddr)); } mrt_table_add (mrt, (mrt_addr_t *) src); } assert (src->src_group); return src; } source_t * mrt_create_source(grp,saddr) group_t *grp; sockaddr_un *saddr; { return mrt_create_source_mask (grp, saddr, inet_mask_host); } source_t * mrt_create_entry_mask(mrt,gaddr,gmask,saddr,smask) mrt_table_t *mrt; sockaddr_un *gaddr; sockaddr_un *gmask; sockaddr_un *saddr; sockaddr_un *smask; { source_t *src = (source_t *) 0; group_t *grp = mrt_create_group_mask (mrt, gaddr, gmask); if (grp) { src = mrt_create_source_mask (grp, saddr, smask); } return src; } source_t * mrt_create_entry(mrt,gaddr,saddr) mrt_table_t *mrt; sockaddr_un *gaddr; sockaddr_un *saddr; { source_t *src = (source_t *) 0; group_t *grp = mrt_create_group (mrt, gaddr); if (grp) { src = mrt_create_source (grp, saddr); } return src; } /* * Display information about the radix tree, including a visual * representation of the tree itself */ void mrt_dump __PF2(tp, task *, fp, FILE *) { fprintf (fp, "TBD: mrt dump\n"); } void mrt_dump_table (mrt, fp) mrt_table_t *mrt; /* IN: the table to be output */ FILE *fp; /* IN: output file */ { struct { mrt_node_t *rn; int state; char right; } stack[MAXDEPTH], *sp; char prefix[MAXDEPTH]; int i = MAXDEPTH; char number[4]; while (i--) { prefix[i] = ' '; } sp = stack; (void) fprintf(fp, "\n\tMRT: %s, inodes %u routes %u:", mrt->mrt_name, mrt->mrt_sinfo->si_family, mrt->mrt_inodes, mrt->mrt_routes); if (mrt->mrt_inodes > 200) { (void) fprintf(fp, " (too large to print)\n\n"); } else if (!(sp->rn = mrt->mrt_head)) { (void) fprintf(fp, " (empty)\n\n"); } else { /* If the tree is small enough, format it */ (void) fprintf(fp, "\n\n"); sp->right = TRUE; sp->state = 0; do { mrt_node_t *rn = sp->rn; int ii = (sp - stack) * 3; switch (sp->state) { case 0: sp->state++; if (rn->rn_right) { sp++; sp->rn = rn->rn_right; sp->right = TRUE; sp->state = 0; continue; } /* Fall through */ case 1: sp->state++; (void) sprintf(number, "%3d", rn->rn_bit); for (i = 0; i < 3 && number[i] == ' '; i++) { number[i] = '-'; } (void) fprintf(fp, "\t\t%.*s+-%s%u+", ii, prefix, (rn->rn_bit > 9) ? "" : "-", rn->rn_bit); if (rn->rn_ext) { (void) fprintf(fp, "--{%A\n", ((mrt_addr_t *) rn->rn_ext)->addr); } else { (void) fprintf(fp, "\n"); } switch (sp->right) { case TRUE: prefix[ii] = '|'; break; case FALSE: prefix[ii] = ' '; break; } if (rn->rn_left) { sp++; sp->rn = rn->rn_left; sp->right = FALSE; sp->state = 0; continue; } case 2: /* Pop the stack */ sp--; } } while (sp >= stack); } (void) fprintf (fp, "\n\n"); } /* * print out an mrt in a more readable form, don't worry about radix trie */ void mrt_print (mrt_table_t *mrt, FILE *fp) { (void) fprintf(fp, "\n\tMRT: %s, inodes %u routes %u:", mrt->mrt_name, mrt->mrt_sinfo->si_family, mrt->mrt_inodes, mrt->mrt_routes); } void downstream(ds) downstream_t *ds; { downstream_t *dsp; fprintf (stdout, "Downstream:\n\t"); DOWNSTREAM_LIST (dsp, ds) { fprintf (stdout, "%A(%s), protos %#x, holdtime %d, deldelay: %d, ctime: %T: rtime: %T, exp: %T, now %T\n", IFA_UNIQUE_ADDR(dsp->ds_ifap), dsp->ds_ifap->ifa_link->ifl_name, dsp->ds_protos, dsp->ds_timeout, (time_t) dsp->ds_data, dsp->ds_ctime, dsp->ds_rtime, dsp->ds_rtime + dsp->ds_timeout, time_sec); } DOWNSTREAM_LIST_END (dsp, ds); fprintf (stdout, "\n"); } void mrt_print_src (fp, src) FILE *fp; source_t *src; { downstream_t *dsp; fprintf (fp, "src: (%A/%A, %A/%A), flags: 0x%x ", src->addr, src->mask, src->src_gaddr, src->src_gmask, src->src_flags); fprintf (fp, "\n"); fprintf (fp, "\tDownstream List: \n\t\t"); downstream (src->src_downstream); fprintf (fp, "\n\n"); } void mrt_print_grp (fp, grp) FILE *fp; group_t *grp; { fprintf (fp, "Group: %A/%A\n", grp->addr, grp->mask); } void mrt_print_table (fp, mrt) FILE *fp; mrt_table_t *mrt; { mrt_node_t *snode; source_t *src; group_t *grp; (void) fprintf(fp, "\nMRT: %s, inodes %u routes %u:\n", mrt->mrt_name, mrt->mrt_sinfo->si_family, mrt->mrt_inodes, mrt->mrt_routes); MRT_GRP_WALK(mrt->mrt_head, grp) { fprintf (fp, "\n\tGroup %A\n", grp->addr); snode = mrt_match_node_mask (grp->grp_srcs, inet_addr_any, inet_mask_default); MRT_SRC_WALK(snode, src) { fprintf (fp, "\t"); mrt_print_src (fp, src); } MRT_SRC_WALK_END(snode, src); } MRT_GRP_WALK_END(mrt->mrt_head, grp); } void mrt_print_subtree (mrt, gaddr, gmask, saddr, smask) mrt_table_t *mrt; sockaddr_un *gaddr, *gmask; sockaddr_un *saddr, *smask; { mrt_node_t *gnode, *snode; group_t *grp; source_t *src; gnode = mrt_match_node_mask (mrt, gaddr, gmask); MRT_GRP_WALK(gnode, grp) { snode = mrt_match_node_mask(grp->grp_srcs, saddr, smask); mrt_print_grp (stdout, grp); MRT_SRC_WALK(snode, src) { mrt_print_src (stdout, src); } MRT_SRC_WALK_END(snode, src); } MRT_GRP_WALK_END(gnode, grp); } int mrt_match (addr, mask, dst) sockaddr_un *addr, *mask, *dst; { return((dst->in.gin_addr.s_addr & mask->in.gin_addr.s_addr) == (addr->in.gin_addr.s_addr & mask->in.gin_addr.s_addr)); } /* Find the 'closest' route matching a given route. Mode is * RTW_UP for a less specific route, RTW_DOWN for a more specific route. * Kind of the same as rt_table_locate() but more tolerent! */ mrt_node_t * mrt_walk_start (mrt, addr, mask, dir) mrt_table_t *mrt; sockaddr_un *addr, *mask; int dir; /* Direction up or down */ { register mrt_node_t *rn, *last, *n; register mrt_addr_t *maddr; register byte *ap; register u_short bitlen; register struct sock_info *si; /* * If there is no table, or nothing to do, assume nothing found. */ if (!(rn = mrt->mrt_head)) return (mrt_node_t *) NULL; /* * Compute the bit length of the mask. */ si = mrt->mrt_sinfo; bitlen = mask_to_prefix_si(si, mask); assert(bitlen != (u_short) -1); /* * Search down the tree until we find a node which * has a bit number the same as ours. */ ap = RN_ADDR(addr, si->si_offset); last = rn->rn_ext ? rn : NULL; while (rn->rn_bit < bitlen) { if (rn->rn_tbit & ap[rn->rn_tbyte]) { rn = rn->rn_right; } else { rn = rn->rn_left; } if (!rn) break; last = rn->rn_ext ? rn: NULL; } /* * If the mask is shorter, check out the RTW_UP dir. Also if * the len are the same but no rn_ext. */ if (!rn) { if (dir != RTW_UP) return (mrt_node_t *) NULL; if (!last) return (mrt_node_t *) NULL; assert(last->rn_bit < bitlen); /* Do we have a match? */ maddr = (mrt_addr_t *) (rn->rn_ext); if (!mrt_match(maddr->addr, maddr->mask, addr)) return (mrt_node_t *) NULL; return last; } /* If the mask is the same, we should have an exact match */ if (bitlen == rn->rn_bit && rn->rn_ext) { maddr = (mrt_addr_t *) (rn->rn_ext); if (!mrt_match(maddr->addr, maddr->mask, addr)) return (mrt_node_t *) NULL; return rn; } /* If the mask is shorter, check the RTW_DOWN dir */ assert(bitlen <= rn->rn_bit); if (dir != RTW_DOWN) return (mrt_node_t *) NULL; /* Get the next node with a rn_rth. There must be one. */ while(!rn->rn_ext) if (rn->rn_left) rn = rn->rn_left; else rn = rn->rn_right; maddr = (mrt_addr_t *) (rn->rn_ext); if (!mrt_match(addr, mask, maddr->addr)) return (mrt_node_t *) NULL; return rn; } static block_t mrt_test_block = 0; mrt_test_t * mrt_test_alloc() { mrt_test_t *fk; if (!mrt_test_block) mrt_test_block = task_block_init (sizeof (mrt_test_t), "mrt_test"); fk = (mrt_test_t *) task_block_alloc (mrt_test_block); fk->forw = (mrt_test_t *) 0; return fk; } void mrt_test (mrt, fakes) mrt_table_t *mrt; mrt_test_t *fakes; { mrt_test_t *fk; for (fk = fakes; fk->forw; fk = fk->forw) { sockaddr_un *gaddr, *gmask, *saddr, *smask, *addr, *mask; u_long ginaddr, sinaddr; mrt_node_t *gnode, *snode; source_t *src = 0; group_t *grp = 0; if (fk->mt_cmd != MRTA_DUMP) { gmask = inet_mask_prefix (fk->mt_glen); ginaddr = htonl(fk->mt_gaddr); ginaddr &= gmask->in.gin_addr.s_addr; gaddr = sockbuild_in (0, ginaddr); smask = inet_mask_prefix (fk->mt_slen); sinaddr = htonl(fk->mt_saddr); sinaddr &= smask->in.gin_addr.s_addr; saddr = sockbuild_in (0, sinaddr); fprintf (stdout, "Fake (%A/%d, %A/%d) ", gaddr, fk->mt_glen, saddr, fk->mt_slen); } switch (fk->mt_cmd) { case MRTA_NONE: case MRTA_ADD: src = mrt_create_entry_mask (mrt, gaddr, gmask, saddr, smask); fprintf (stdout, " Add %s\n", (src) ? "succeded" : "failed"); break; case MRTA_DEL: src = mrt_locate_source_mask (mrt, gaddr, gmask, saddr, smask); if (src) { mrt_source_delete (src); fprintf (stdout, " deleted\n"); } else { fprintf (stdout, " does not exist\n"); } break; case MRTA_EXACT: src = mrt_locate_source_mask (mrt, gaddr, gmask, saddr, smask); fprintf (stdout, "exact match %s\n", src ? "found" : "not found"); break; case MRTA_BEST: gnode = mrt_match_node_mask (mrt, gaddr, gmask); if (gnode) { grp = (group_t *) gnode->rn_ext; snode = mrt_match_node_mask (grp->grp_srcs, saddr, smask); if (snode) src = (source_t *) snode->rn_ext; } fprintf (stdout, "best match "); if (src) fprintf (stdout, "(%A/%d, %A/%d)\n", src->addr, inet_prefix_mask(src->mask), src->src_gaddr, inet_prefix_mask(src->src_gmask)); else fprintf (stdout, "not found\n"); break; case MRTA_DUMP: printf (" Table dump\n"); gnode = mrt_match_node_mask (mrt, gaddr, gmask); if (gnode) grp = (group_t *) gnode->rn_ext; if (!grp) break; else mrt_dump_table (grp->grp_srcs, stdout); break; case MRTA_WALKDOWN: fprintf (stdout, "Walkdown\n"); gnode = mrt_match_node_mask (mrt, gaddr, gmask); if (!gnode) break; MRT_GRP_WALK (gnode, grp) { snode = mrt_match_node_mask (grp->grp_srcs, saddr, smask); if (!snode) break; MRT_SRC_WALK (snode, src) { fprintf (stdout, "\tsrc %A/%d\n", src->addr, inet_prefix_mask(src->mask)); } MRT_SRC_WALK_END(snode, src); } MRT_GRP_WALK_END(gnode, grp); break; case MRTA_WALKUP: fprintf (stdout, " Walkup not supported\n"); break; case MRTA_DELTABLE: mrt_table_delete (mrt); break; default: fprintf (stdout, " unknown command %d", fk->mt_cmd); break; } } } #endif /* IP_MULTICAST_ROUTING */