/* $OpenBSD: rde_srt.c,v 1.25 2010/09/02 14:03:21 sobrado Exp $ */ /* * Copyright (c) 2009 Michele Marchetto * Copyright (c) 2005, 2006 Esben Norby * * Permission to use, copy, modify, and distribute this software for any * purpose with or without fee is hereby granted, provided that the above * copyright notice and this permission notice appear in all copies. * * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */ #include #include #include #include #include #include #include #include #include "igmp.h" #include "dvmrp.h" #include "dvmrpd.h" #include "log.h" #include "dvmrpe.h" #include "rde.h" /* source route tree */ void rt_invalidate(void); void rt_expire_timer(int, short, void *); int rt_start_expire_timer(struct rt_node *); void rt_holddown_timer(int, short, void *); void rt_start_holddown_timer(struct rt_node *); void srt_set_upstream(struct rt_node *, u_int32_t); /* Designated forwarder */ void srt_set_forwarder_self(struct rt_node *, struct iface *); void srt_update_ds_forwarders(struct rt_node *, struct iface *, u_int32_t); void srt_current_forwarder(struct rt_node *, struct iface *, u_int32_t, u_int32_t); /* Downstream neighbors */ void srt_add_ds(struct rt_node *, u_int32_t, u_int32_t); void srt_delete_ds(struct rt_node *, struct ds_nbr *, struct iface *); /* Flash updates */ void flash_update(struct rt_node *); void flash_update_ds(struct rt_node *); RB_HEAD(rt_tree, rt_node) rt; RB_PROTOTYPE(rt_tree, rt_node, entry, rt_compare) RB_GENERATE(rt_tree, rt_node, entry, rt_compare) extern struct dvmrpd_conf *rdeconf; /* timers */ void rt_expire_timer(int fd, short event, void *arg) { struct rt_node *rn = arg; struct timeval tv; log_debug("rt_expire_timer: route %s/%d", inet_ntoa(rn->prefix), rn->prefixlen); timerclear(&tv); rn->old_cost = rn->cost; rn->cost = INFINITY_METRIC; tv.tv_sec = ROUTE_HOLD_DOWN; if (evtimer_add(&rn->holddown_timer, &tv) == -1) fatal("rt_expire_timer"); } int rt_start_expire_timer(struct rt_node *rn) { struct timeval tv; rn->old_cost = 0; if (evtimer_pending(&rn->holddown_timer, NULL)) if (evtimer_del(&rn->holddown_timer) == -1) fatal("rt_start_expire_timer"); timerclear(&tv); tv.tv_sec = ROUTE_EXPIRATION_TIME; return (evtimer_add(&rn->expiration_timer, &tv)); } void rt_holddown_timer(int fd, short event, void *arg) { struct rt_node *rn = arg; log_debug("rt_holddown_timer: route %s/%d", inet_ntoa(rn->prefix), rn->prefixlen); rt_remove(rn); } void rt_start_holddown_timer(struct rt_node *rn) { struct timeval tv; timerclear(&tv); tv.tv_sec = ROUTE_HOLD_DOWN; if (evtimer_pending(&rn->expiration_timer, NULL)) { if (evtimer_del(&rn->expiration_timer) == -1) fatal("rt_start_holddown_timer"); evtimer_add(&rn->holddown_timer, &tv); } } /* route table */ void rt_init(void) { RB_INIT(&rt); } int rt_compare(struct rt_node *a, struct rt_node *b) { /* * sort route entries based on prefixlen since generating route * reports rely on that. */ if (a->prefixlen < b->prefixlen) return (-1); if (a->prefixlen > b->prefixlen) return (1); if (ntohl(a->prefix.s_addr) < ntohl(b->prefix.s_addr)) return (-1); if (ntohl(a->prefix.s_addr) > ntohl(b->prefix.s_addr)) return (1); return (0); } struct rt_node * rt_find(in_addr_t prefix, u_int8_t prefixlen) { struct rt_node s; s.prefix.s_addr = prefix; s.prefixlen = prefixlen; return (RB_FIND(rt_tree, &rt, &s)); } struct rt_node * rr_new_rt(struct route_report *rr, u_int32_t adj_metric, int connected) { struct timespec now; struct rt_node *rn; int i; clock_gettime(CLOCK_MONOTONIC, &now); if ((rn = calloc(1, sizeof(*rn))) == NULL) fatal("rr_new_rt"); rn->prefix.s_addr = rr->net.s_addr; rn->prefixlen = mask2prefixlen(rr->mask.s_addr); rn->nexthop.s_addr = rr->nexthop.s_addr; rn->cost = adj_metric; rn->ifindex = rr->ifindex; for (i = 0; i < MAXVIFS; i++) { rn->ttls[i] = 0; rn->ds_cnt[i] = 0; rn->adv_rtr[i].addr.s_addr = 0; rn->adv_rtr[i].metric = 0; } LIST_INIT(&rn->ds_list); rn->flags = F_DVMRPD_INSERTED; rn->connected = connected; rn->uptime = now.tv_sec; evtimer_set(&rn->expiration_timer, rt_expire_timer, rn); evtimer_set(&rn->holddown_timer, rt_holddown_timer, rn); return (rn); } int rt_insert(struct rt_node *r) { log_debug("rt_insert: inserting route %s/%d", inet_ntoa(r->prefix), r->prefixlen); if (RB_INSERT(rt_tree, &rt, r) != NULL) { log_warnx("rt_insert failed for %s/%u", inet_ntoa(r->prefix), r->prefixlen); free(r); return (-1); } return (0); } int rt_remove(struct rt_node *r) { struct ds_nbr *ds_nbr; if (RB_REMOVE(rt_tree, &rt, r) == NULL) { log_warnx("rt_remove failed for %s/%u", inet_ntoa(r->prefix), r->prefixlen); return (-1); } LIST_FOREACH(ds_nbr, &r->ds_list, entry) { LIST_REMOVE(ds_nbr, entry); free(ds_nbr); } free(r); return (0); } void rt_invalidate(void) { struct rt_node *r, *nr; for (r = RB_MIN(rt_tree, &rt); r != NULL; r = nr) { nr = RB_NEXT(rt_tree, &rt, r); if (r->invalid) rt_remove(r); else r->invalid = 1; } } void rt_clear(void) { struct rt_node *r; while ((r = RB_MIN(rt_tree, &rt)) != NULL) rt_remove(r); } void rt_snap(u_int32_t peerid) { struct rt_node *r; struct route_report rr; RB_FOREACH(r, rt_tree, &rt) { if (r->invalid) continue; rr.net = r->prefix; rr.mask.s_addr = ntohl(prefixlen2mask(r->prefixlen)); rr.metric = r->cost; rr.ifindex = r->ifindex; rde_imsg_compose_dvmrpe(IMSG_FULL_ROUTE_REPORT, peerid, 0, &rr, sizeof(rr)); } } void rt_dump(pid_t pid) { static struct ctl_rt rtctl; struct timespec now; struct timeval tv, now2, res; struct rt_node *r; clock_gettime(CLOCK_MONOTONIC, &now); RB_FOREACH(r, rt_tree, &rt) { if (r->invalid) continue; rtctl.prefix.s_addr = r->prefix.s_addr; rtctl.nexthop.s_addr = r->nexthop.s_addr; rtctl.cost = r->cost; rtctl.flags = r->flags; rtctl.prefixlen = r->prefixlen; rtctl.uptime = now.tv_sec - r->uptime; gettimeofday(&now2, NULL); if (evtimer_pending(&r->expiration_timer, &tv)) { timersub(&tv, &now2, &res); rtctl.expire = res.tv_sec; } else rtctl.expire = -1; rde_imsg_compose_dvmrpe(IMSG_CTL_SHOW_RIB, 0, pid, &rtctl, sizeof(rtctl)); } } void rt_update(struct rt_node *rn) { if (!rn->connected) rt_start_expire_timer(rn); } struct rt_node * rt_match_origin(in_addr_t src) { struct rt_node *r; RB_FOREACH(r, rt_tree, &rt) { if (r->prefix.s_addr == (src & htonl(prefixlen2mask(r->prefixlen)))) return (r); } return (NULL); } int srt_check_route(struct route_report *rr, int connected) { struct rt_node *rn; struct iface *iface; struct ds_nbr *ds_nbr; u_int32_t adj_metric; u_int32_t nbr_ip, nbr_report, ifindex; if ((iface = if_find_index(rr->ifindex)) == NULL) return (-1); ifindex = iface->ifindex; /* Interpret special case 0.0.0.0/8 as 0.0.0.0/0 */ if (rr->net.s_addr == 0) rr->mask.s_addr = 0; if (connected) adj_metric = rr->metric; else adj_metric = rr->metric + iface->metric; if (adj_metric > INFINITY_METRIC) adj_metric = INFINITY_METRIC; /* If the route is new and the Adjusted Metric is less than infinity, the route should be added. */ rn = rt_find(rr->net.s_addr, mask2prefixlen(rr->mask.s_addr)); if (rn == NULL) { if (adj_metric < INFINITY_METRIC) { rn = rr_new_rt(rr, adj_metric, connected); rt_insert(rn); } return (0); } /* If the route is connected accept only downstream neighbors reports */ if (rn->connected && rr->metric <= INFINITY_METRIC) return (0); nbr_ip = rn->nexthop.s_addr; nbr_report = rr->nexthop.s_addr; if (rr->metric < INFINITY_METRIC) { /* If it is our current nexthop it cannot be a * downstream router */ if (nbr_ip != nbr_report) if ((ds_nbr = srt_find_ds(rn, nbr_report))) srt_delete_ds(rn, ds_nbr, iface); if (adj_metric > rn->cost) { if (nbr_ip == nbr_report) { rn->cost = adj_metric; flash_update_ds(rn); } } else if (adj_metric < rn->cost) { rn->cost = adj_metric; if (nbr_ip != nbr_report) { rn->nexthop.s_addr = nbr_report; srt_set_upstream(rn, ifindex); flash_update(rn); } /* We have a new best route to source, update the * designated forwarders on downstream interfaces to * reflect the new metric */ srt_update_ds_forwarders(rn, iface, nbr_report); } else { if (nbr_report < nbr_ip) { rn->nexthop.s_addr = nbr_report; srt_set_upstream(rn, ifindex); flash_update(rn); } else if (nbr_report == nbr_ip && adj_metric == rn->old_cost) rt_update(rn); flash_update_ds(rn); } /* Update forwarder of current interface if necessary and * refresh the route */ srt_current_forwarder(rn, iface, rr->metric, nbr_report); rt_update(rn); } else if (rr->metric == INFINITY_METRIC) { if (nbr_report == rn->adv_rtr[ifindex].addr.s_addr) srt_set_forwarder_self(rn, iface); infinity: if (nbr_ip == nbr_report) { if (rn->cost < INFINITY_METRIC) rt_start_holddown_timer(rn); } else if ((ds_nbr = srt_find_ds(rn, nbr_report))) srt_delete_ds(rn, ds_nbr, iface); } else if (INFINITY_METRIC < rr->metric && rr->metric < 2 * INFINITY_METRIC) { /* Neighbor is reporting his dependency for this source */ if (nbr_report == rn->adv_rtr[ifindex].addr.s_addr) srt_set_forwarder_self(rn, iface); if (rn->ifindex == ifindex) goto infinity; else if (srt_find_ds(rn, nbr_report) == NULL) srt_add_ds(rn, nbr_report, ifindex); } return (0); } void srt_current_forwarder(struct rt_node *rn, struct iface *iface, u_int32_t metric, u_int32_t nbr_report) { struct adv_rtr *adv = &rn->adv_rtr[iface->ifindex]; if (nbr_report == adv->addr.s_addr) { if (metric > rn->cost || (metric == rn->cost && iface->addr.s_addr < nbr_report)) srt_set_forwarder_self(rn, iface); } else { if (metric < adv->metric || (metric == adv->metric && nbr_report < adv->addr.s_addr)) if (adv->addr.s_addr == iface->addr.s_addr) rn->ttls[iface->ifindex] = 0; adv->addr.s_addr = nbr_report; adv->metric = metric; mfc_update_source(rn); } } void srt_update_ds_forwarders(struct rt_node *rn, struct iface *iface, u_int32_t nbr_report) { struct iface *ifa; int i; for (i = 0; i < MAXVIFS; i++) { if (rn->adv_rtr[i].addr.s_addr && (rn->cost < rn->adv_rtr[i].metric || (rn->cost == rn->adv_rtr[i].metric && iface->addr.s_addr < nbr_report))) { ifa = if_find_index(i); srt_set_forwarder_self(rn, ifa); } } } void srt_set_forwarder_self(struct rt_node *rn, struct iface *iface) { rn->adv_rtr[iface->ifindex].addr.s_addr = iface->addr.s_addr; rn->adv_rtr[iface->ifindex].metric = rn->cost; rn->ttls[iface->ifindex] = 1; mfc_update_source(rn); } void srt_set_upstream(struct rt_node *rn, u_int32_t ifindex) { if (rn->ifindex != ifindex) { rn->ttls[rn->ifindex] = 1; rn->ifindex = ifindex; } mfc_update_source(rn); } void srt_add_ds(struct rt_node *rn, u_int32_t nbr_report, u_int32_t ifindex) { struct ds_nbr *ds_nbr; log_debug("srt_add_ds: adding downstream router for source %s/%d", inet_ntoa(rn->prefix), rn->prefixlen); if ((ds_nbr = malloc(sizeof(struct ds_nbr))) == NULL) fatal("srt_add_ds"); ds_nbr->addr.s_addr = nbr_report; LIST_INSERT_HEAD(&rn->ds_list, ds_nbr, entry); rn->ds_cnt[ifindex]++; rn->ttls[ifindex] = 1; mfc_update_source(rn); } struct ds_nbr * srt_find_ds(struct rt_node *rn, u_int32_t nbr_report) { struct ds_nbr *ds_nbr; LIST_FOREACH(ds_nbr, &rn->ds_list, entry) if (ds_nbr->addr.s_addr == nbr_report) return (ds_nbr); return (NULL); } void srt_delete_ds(struct rt_node *rn, struct ds_nbr *ds_nbr, struct iface *iface) { log_debug("srt_delete_ds: deleting downstream router for source %s/%d", inet_ntoa(rn->prefix), rn->prefixlen); LIST_REMOVE(ds_nbr, entry); free(ds_nbr); rn->ds_cnt[iface->ifindex]--; srt_check_downstream_ifaces(rn, iface); } void srt_check_downstream_ifaces(struct rt_node *rn, struct iface *iface) { /* We are not the designated forwarder for this source on this interface. Keep things as they currently are */ if (rn->adv_rtr[iface->ifindex].addr.s_addr != iface->addr.s_addr) return; /* There are still downstream dependent router for this source Keep things as they currently are */ if (rn->ds_cnt[iface->ifindex]) return; /* There are still group members for this source on this iface Keep things as they currently are */ if (mfc_check_members(rn, iface)) return; /* Remove interface from the downstream list */ rn->ttls[iface->ifindex] = 0; mfc_update_source(rn); } void srt_expire_nbr(struct in_addr addr, unsigned int ifindex) { struct ds_nbr *ds; struct rt_node *rn; struct iface *iface; iface = if_find_index(ifindex); if (iface == NULL) fatal("srt_expire_nbr: interface not found"); RB_FOREACH(rn, rt_tree, &rt) { if (rn->adv_rtr[ifindex].addr.s_addr == addr.s_addr) { rn->adv_rtr[ifindex].addr.s_addr = iface->addr.s_addr; rn->adv_rtr[ifindex].metric = rn->cost; /* XXX: delete all routes learned from this nbr */ } else if (rn->adv_rtr[ifindex].addr.s_addr == iface->addr.s_addr) { ds = srt_find_ds(rn, addr.s_addr); if (ds) { srt_delete_ds(rn, ds, iface); srt_check_downstream_ifaces(rn, iface); } } } } void flash_update(struct rt_node *rn) { struct route_report rr; rr.net = rn->prefix; rr.mask.s_addr = ntohl(prefixlen2mask(rn->prefixlen)); rr.metric = rn->cost; rr.ifindex = rn->ifindex; rde_imsg_compose_dvmrpe(IMSG_FLASH_UPDATE, 0, 0, &rr, sizeof(rr)); } void flash_update_ds(struct rt_node *rn) { struct route_report rr; rr.net = rn->prefix; rr.mask.s_addr = ntohl(prefixlen2mask(rn->prefixlen)); rr.metric = rn->cost; rr.ifindex = rn->ifindex; rde_imsg_compose_dvmrpe(IMSG_FLASH_UPDATE_DS, 0, 0, &rr, sizeof(rr)); }