/* $OpenBSD: rde_spf.c,v 1.22 2010/03/01 08:51:40 claudio Exp $ */ /* * Copyright (c) 2005 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 "ospf6d.h" #include "ospf6.h" #include "log.h" #include "rde.h" extern struct ospfd_conf *rdeconf; TAILQ_HEAD(, vertex) cand_list; 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) struct vertex *spf_root = NULL; void calc_nexthop_clear(struct vertex *); void calc_nexthop_add(struct vertex *, struct vertex *, const struct in6_addr *, u_int32_t); struct in6_addr *calc_nexthop_lladdr(struct vertex *, struct lsa_rtr_link *, unsigned int); void calc_nexthop_transit_nbr(struct vertex *, struct vertex *, unsigned int); void calc_nexthop(struct vertex *, struct vertex *, struct area *, struct lsa_rtr_link *); void rt_nexthop_clear(struct rt_node *); void rt_nexthop_add(struct rt_node *, struct v_nexthead *, struct in_addr); void rt_update(struct in6_addr *, u_int8_t, struct v_nexthead *, u_int32_t, u_int32_t, struct in_addr, struct in_addr, enum path_type, enum dst_type, u_int8_t, u_int32_t); struct rt_node *rt_lookup(enum dst_type, struct in6_addr *); void rt_invalidate(struct area *); int linked(struct vertex *, struct vertex *); void spf_calc(struct area *area) { struct vertex *v, *w; struct lsa_rtr_link *rtr_link = NULL; struct lsa_net_link *net_link; u_int32_t d; unsigned int i; /* clear SPF tree */ spf_tree_clr(area); cand_list_clr(); /* initialize SPF tree */ if ((v = spf_root = lsa_find_rtr(area, rde_router_id())) == NULL) /* empty area because no interface is active */ return; area->transit = 0; spf_root->cost = 0; w = NULL; /* calculate SPF tree */ do { /* loop links */ for (i = 0; i < lsa_num_links(v); i++) { switch (v->type) { case LSA_TYPE_ROUTER: rtr_link = get_rtr_link(v, i); switch (rtr_link->type) { case LINK_TYPE_POINTTOPOINT: case LINK_TYPE_VIRTUAL: /* find router LSA */ w = lsa_find_rtr(area, rtr_link->nbr_rtr_id); break; case LINK_TYPE_TRANSIT_NET: /* find network LSA */ w = lsa_find_tree(&area->lsa_tree, htons(LSA_TYPE_NETWORK), rtr_link->nbr_iface_id, rtr_link->nbr_rtr_id); break; default: fatalx("spf_calc: invalid link type"); } break; case LSA_TYPE_NETWORK: net_link = get_net_link(v, i); /* find router LSA */ w = lsa_find_rtr(area, net_link->att_rtr); break; default: fatalx("spf_calc: invalid LSA type"); } if (w == NULL) continue; if (ntohs(w->lsa->hdr.age) == MAX_AGE) continue; if (lsa_num_links(w) == 0) continue; if (!linked(w, v)) { log_debug("spf_calc: w adv_rtr %s ls_id %s " "type 0x%x numlinks %hu has no link to " "v adv_rtr %s ls_id %s type 0x%x", log_rtr_id(htonl(w->adv_rtr)), log_rtr_id(htonl(w->ls_id)), w->type, lsa_num_links(w), log_rtr_id(htonl(v->adv_rtr)), log_rtr_id(htonl(v->ls_id)), v->type); continue; } if (v->type == LSA_TYPE_ROUTER) d = v->cost + ntohs(rtr_link->metric); else d = v->cost; if (cand_list_present(w)) { if (d > w->cost) continue; if (d < w->cost) { w->cost = d; calc_nexthop_clear(w); calc_nexthop(w, v, area, rtr_link); /* * need to readd to candidate list * because the list is sorted */ TAILQ_REMOVE(&cand_list, w, cand); cand_list_add(w); } else /* equal cost path */ calc_nexthop(w, v, area, rtr_link); } else if (w->cost == LS_INFINITY && d < LS_INFINITY) { w->cost = d; calc_nexthop_clear(w); calc_nexthop(w, v, area, rtr_link); cand_list_add(w); } } /* get next vertex */ v = cand_list_pop(); w = NULL; } while (v != NULL); /* spf_dump(area); */ log_debug("spf_calc: area %s calculated", inet_ntoa(area->id)); /* Dump SPF tree to log */ RB_FOREACH(v, lsa_tree, &area->lsa_tree) { struct v_nexthop *vn; char hops[4096]; struct iface *iface; bzero(hops, sizeof(hops)); if (v->type != LSA_TYPE_ROUTER && v->type != LSA_TYPE_NETWORK) continue; TAILQ_FOREACH(vn, &v->nexthop, entry) { strlcat(hops, log_in6addr(&vn->nexthop), sizeof(hops)); strlcat(hops, "%", sizeof(hops)); if ((iface = if_find(vn->ifindex)) == NULL) fatalx("spf_calc: lost iface"); strlcat(hops, iface->name, sizeof(hops)); if (vn != TAILQ_LAST(&v->nexthop, v_nexthead)) strlcat(hops, ", ", sizeof(hops)); } log_debug("%s(%s, 0x%x, %s) cost %u has nexthops [%s]", v == spf_root ? "*" : " ", log_rtr_id(htonl(v->adv_rtr)), v->type, log_rtr_id(htonl(v->ls_id)), v->cost, hops); } area->num_spf_calc++; start_spf_timer(); } void rt_calc(struct vertex *v, struct area *area, struct ospfd_conf *conf) { struct vertex *w; struct lsa_intra_prefix *iap; struct lsa_prefix *prefix; struct in_addr adv_rtr; struct in6_addr ia6; u_int16_t i, off; u_int8_t flags; lsa_age(v); if (ntohs(v->lsa->hdr.age) == MAX_AGE) return; switch (v->type) { case LSA_TYPE_ROUTER: if (v->cost >= LS_INFINITY || TAILQ_EMPTY(&v->nexthop)) return; /* router, only add border and as-external routers */ flags = LSA_24_GETHI(ntohl(v->lsa->data.rtr.opts)); if ((flags & (OSPF_RTR_B | OSPF_RTR_E)) == 0) return; bzero(&ia6, sizeof(ia6)); adv_rtr.s_addr = htonl(v->adv_rtr); bcopy(&adv_rtr, &ia6.s6_addr[12], sizeof(adv_rtr)); rt_update(&ia6, 128, &v->nexthop, v->cost, 0, area->id, adv_rtr, PT_INTER_AREA, DT_RTR, flags, 0); break; case LSA_TYPE_INTRA_A_PREFIX: /* Find referenced LSA */ iap = &v->lsa->data.pref_intra; switch (ntohs(iap->ref_type)) { case LSA_TYPE_ROUTER: w = lsa_find_rtr(area, iap->ref_adv_rtr); if (w == NULL) { warnx("rt_calc: Intra-Area-Prefix LSA (%s, %u) " "references non-existent router %s", log_rtr_id(htonl(v->adv_rtr)), v->ls_id, log_rtr_id(iap->ref_adv_rtr)); return; } flags = LSA_24_GETHI(ntohl(w->lsa->data.rtr.opts)); break; case LSA_TYPE_NETWORK: w = lsa_find_tree(&area->lsa_tree, iap->ref_type, iap->ref_ls_id, iap->ref_adv_rtr); if (w == NULL) { warnx("rt_calc: Intra-Area-Prefix LSA (%s, %u) " "references non-existent Network LSA (%s, " "%u)", log_rtr_id(htonl(v->adv_rtr)), v->ls_id, log_rtr_id(iap->ref_adv_rtr), ntohl(iap->ref_ls_id)); return; } flags = 0; break; default: warnx("rt_calc: Intra-Area-Prefix LSA (%s, %u) has " "invalid ref_type 0x%hx", log_rtr_id(v->adv_rtr), v->ls_id, ntohs(iap->ref_type)); return; } if (w->cost >= LS_INFINITY || TAILQ_EMPTY(&w->nexthop)) return; /* Add prefixes listed in Intra-Area-Prefix LSA to routing * table, using w as destination. */ off = sizeof(v->lsa->hdr) + sizeof(struct lsa_intra_prefix); for (i = 0; i < ntohs(v->lsa->data.pref_intra.numprefix); i++) { prefix = (struct lsa_prefix *)((char *)(v->lsa) + off); if (!(prefix->options & OSPF_PREFIX_NU)) { bzero(&ia6, sizeof(ia6)); bcopy(prefix + 1, &ia6, LSA_PREFIXSIZE(prefix->prefixlen)); adv_rtr.s_addr = htonl(w->adv_rtr); rt_update(&ia6, prefix->prefixlen, &w->nexthop, w->cost + ntohs(prefix->metric), 0, area->id, adv_rtr, PT_INTRA_AREA, DT_NET, flags, 0); } off += sizeof(struct lsa_prefix) + LSA_PREFIXSIZE(prefix->prefixlen); } break; case LSA_TYPE_INTER_A_PREFIX: /* XXX if ABR only look at area 0.0.0.0 LSA */ /* ignore self-originated stuff */ if (v->self) return; adv_rtr.s_addr = htonl(v->adv_rtr); w = lsa_find_rtr(area, adv_rtr.s_addr); if (w == NULL) { warnx("rt_calc: Inter-Area-Router LSA (%s, %u) " "originated from non-existent router", log_rtr_id(htonl(v->adv_rtr)), v->ls_id); return; } if (w->cost >= LS_INFINITY || TAILQ_EMPTY(&w->nexthop)) return; /* Add prefix listed in Inter-Area-Prefix LSA to routing * table, using w as destination. */ off = sizeof(v->lsa->hdr) + sizeof(struct lsa_prefix_sum); prefix = (struct lsa_prefix *)((char *)(v->lsa) + off); if (prefix->options & OSPF_PREFIX_NU) return; bzero(&ia6, sizeof(ia6)); bcopy(prefix + 1, &ia6, LSA_PREFIXSIZE(prefix->prefixlen)); rt_update(&ia6, prefix->prefixlen, &w->nexthop, w->cost + (ntohs(v->lsa->data.rtr_sum.metric) & LSA_METRIC_MASK), 0, area->id, adv_rtr, PT_INTER_AREA, DT_NET, 0, 0); break; case LSA_TYPE_INTER_A_ROUTER: /* XXX if ABR only look at area 0.0.0.0 LSA */ /* ignore self-originated stuff */ if (v->self) return; adv_rtr.s_addr = htonl(v->adv_rtr); w = lsa_find_rtr(area, adv_rtr.s_addr); if (w == NULL) { warnx("rt_calc: Inter-Area-Router LSA (%s, %u) " "originated from non-existent router", log_rtr_id(htonl(v->adv_rtr)), v->ls_id); return; } if (w->cost >= LS_INFINITY || TAILQ_EMPTY(&w->nexthop)) return; /* Add router listed in Inter-Area-Router LSA to routing * table, using w as destination. */ bzero(&ia6, sizeof(ia6)); bcopy(&v->lsa->data.rtr_sum.dest_rtr_id, &ia6.s6_addr[12], 4); rt_update(&ia6, 128, &w->nexthop, w->cost + (ntohs(v->lsa->data.rtr_sum.metric) & LSA_METRIC_MASK), 0, area->id, adv_rtr, PT_INTER_AREA, DT_RTR, 0, 0); break; default: break; } } void asext_calc(struct vertex *v) { struct in6_addr addr, fw_addr; struct rt_node *r; struct rt_nexthop *rn; struct lsa_prefix *prefix; struct in_addr adv_rtr, area; char *p; u_int32_t metric, cost2, ext_tag = 0; enum path_type type; lsa_age(v); if (ntohs(v->lsa->hdr.age) == MAX_AGE || (ntohl(v->lsa->data.asext.metric) & LSA_METRIC_MASK) >= LS_INFINITY) return; switch (v->type) { case LSA_TYPE_EXTERNAL: /* ignore self-originated stuff */ if (v->self) return; adv_rtr.s_addr = htonl(v->adv_rtr); bzero(&addr, sizeof(addr)); bcopy(&adv_rtr, &addr.s6_addr[12], sizeof(adv_rtr)); if ((r = rt_lookup(DT_RTR, &addr)) == NULL) return; prefix = &v->lsa->data.asext.prefix; if (prefix->options & OSPF_PREFIX_NU) break; bzero(&addr, sizeof(addr)); bcopy(prefix + 1, &addr, LSA_PREFIXSIZE(prefix->prefixlen)); p = (char *)(prefix + 1) + LSA_PREFIXSIZE(prefix->prefixlen); metric = ntohl(v->lsa->data.asext.metric); if (metric & LSA_ASEXT_F_FLAG) { bcopy(p, &fw_addr, sizeof(fw_addr)); p += sizeof(fw_addr); /* lookup forwarding address */ if ((r = rt_lookup(DT_NET, &fw_addr)) == NULL || (r->p_type != PT_INTRA_AREA && r->p_type != PT_INTER_AREA)) return; } if (metric & LSA_ASEXT_T_FLAG) { bcopy(p, &ext_tag, sizeof(ext_tag)); p += sizeof(ext_tag); } if (metric & LSA_ASEXT_E_FLAG) { v->cost = r->cost; cost2 = metric & LSA_METRIC_MASK; type = PT_TYPE2_EXT; } else { v->cost = r->cost + (metric & LSA_METRIC_MASK); cost2 = 0; type = PT_TYPE1_EXT; } area.s_addr = 0; calc_nexthop_clear(v); TAILQ_FOREACH(rn, &r->nexthop, entry) { if (rn->invalid) continue; if (rn->connected && r->d_type == DT_NET) { if (metric & LSA_ASEXT_F_FLAG) calc_nexthop_add(v, NULL, &fw_addr, rn->ifindex); else fatalx("asext_calc: I'm sorry Dave, " "I'm afraid I can't do that."); } else calc_nexthop_add(v, NULL, &rn->nexthop, rn->ifindex); } rt_update(&addr, prefix->prefixlen, &v->nexthop, v->cost, cost2, area, adv_rtr, type, DT_NET, 0, ext_tag); break; default: fatalx("asext_calc: invalid LSA type"); } } void spf_tree_clr(struct area *area) { struct lsa_tree *tree = &area->lsa_tree; struct vertex *v; RB_FOREACH(v, lsa_tree, tree) { v->cost = LS_INFINITY; calc_nexthop_clear(v); } } void calc_nexthop_clear(struct vertex *v) { struct v_nexthop *vn; while ((vn = TAILQ_FIRST(&v->nexthop))) { TAILQ_REMOVE(&v->nexthop, vn, entry); free(vn); } } void calc_nexthop_add(struct vertex *dst, struct vertex *parent, const struct in6_addr *nexthop, u_int32_t ifindex) { struct v_nexthop *vn; if ((vn = calloc(1, sizeof(*vn))) == NULL) fatal("calc_nexthop_add"); vn->prev = parent; if (nexthop) vn->nexthop = *nexthop; vn->ifindex = ifindex; TAILQ_INSERT_TAIL(&dst->nexthop, vn, entry); } struct in6_addr * calc_nexthop_lladdr(struct vertex *dst, struct lsa_rtr_link *rtr_link, unsigned int ifindex) { struct iface *iface; struct vertex *link; struct rde_nbr *nbr; /* Find outgoing interface, we need its LSA tree */ LIST_FOREACH(iface, &dst->area->iface_list, entry) { if (ifindex == iface->ifindex) break; } if (!iface) { log_warnx("calc_nexthop_lladdr: no interface found for " "ifindex %d", ntohl(rtr_link->iface_id)); return (NULL); } /* Determine neighbor's link-local address. * Try to get it from link LSA first. */ link = lsa_find_tree(&iface->lsa_tree, htons(LSA_TYPE_LINK), rtr_link->iface_id, htonl(dst->adv_rtr)); if (link) return &link->lsa->data.link.lladdr; /* Not found, so fall back to source address * advertised in hello packet. */ if ((nbr = rde_nbr_find(dst->peerid)) == NULL) fatalx("next hop is not a neighbor"); return &nbr->addr; } void calc_nexthop_transit_nbr(struct vertex *dst, struct vertex *parent, unsigned int ifindex) { struct lsa_rtr_link *rtr_link; unsigned int i; struct in6_addr *lladdr; if (dst->type != LSA_TYPE_ROUTER) fatalx("calc_nexthop_transit_nbr: dst is not a router"); if (parent->type != LSA_TYPE_NETWORK) fatalx("calc_nexthop_transit_nbr: parent is not a network"); /* dst is a neighbor on a directly attached transit network. * Figure out dst's link local address and add it as nexthop. */ for (i = 0; i < lsa_num_links(dst); i++) { rtr_link = get_rtr_link(dst, i); if (rtr_link->type == LINK_TYPE_TRANSIT_NET && rtr_link->nbr_rtr_id == parent->lsa->hdr.adv_rtr && rtr_link->nbr_iface_id == parent->lsa->hdr.ls_id) { lladdr = calc_nexthop_lladdr(dst, rtr_link, ifindex); calc_nexthop_add(dst, parent, lladdr, ifindex); } } } void calc_nexthop(struct vertex *dst, struct vertex *parent, struct area *area, struct lsa_rtr_link *rtr_link) { struct v_nexthop *vn; struct in6_addr *nexthop; /* case 1 */ if (parent == spf_root) { switch (dst->type) { case LSA_TYPE_ROUTER: if (rtr_link->type != LINK_TYPE_POINTTOPOINT) fatalx("inconsistent SPF tree"); nexthop = calc_nexthop_lladdr(dst, rtr_link, ntohl(rtr_link->iface_id)); break; case LSA_TYPE_NETWORK: if (rtr_link->type != LINK_TYPE_TRANSIT_NET) fatalx("inconsistent SPF tree"); /* Next hop address cannot be determined yet, * we only know the outgoing interface. */ nexthop = NULL; break; default: fatalx("calc_nexthop: invalid dst type"); } calc_nexthop_add(dst, spf_root, nexthop, ntohl(rtr_link->iface_id)); return; } /* case 2 */ if (parent->type == LSA_TYPE_NETWORK && dst->type == LSA_TYPE_ROUTER) { TAILQ_FOREACH(vn, &parent->nexthop, entry) { if (vn->prev == spf_root) calc_nexthop_transit_nbr(dst, parent, vn->ifindex); else /* dst is more than one transit net away */ calc_nexthop_add(dst, parent, &vn->nexthop, vn->ifindex); } return; } /* case 3 */ TAILQ_FOREACH(vn, &parent->nexthop, entry) calc_nexthop_add(dst, parent, &vn->nexthop, vn->ifindex); } /* candidate list */ void cand_list_init(void) { TAILQ_INIT(&cand_list); } void cand_list_add(struct vertex *v) { struct vertex *c = NULL; TAILQ_FOREACH(c, &cand_list, cand) { if (c->cost > v->cost) { TAILQ_INSERT_BEFORE(c, v, cand); return; } else if (c->cost == v->cost && c->type == LSA_TYPE_ROUTER && v->type == LSA_TYPE_NETWORK) { TAILQ_INSERT_BEFORE(c, v, cand); return; } } TAILQ_INSERT_TAIL(&cand_list, v, cand); } struct vertex * cand_list_pop(void) { struct vertex *c; if ((c = TAILQ_FIRST(&cand_list)) != NULL) { TAILQ_REMOVE(&cand_list, c, cand); } return (c); } int cand_list_present(struct vertex *v) { struct vertex *c; TAILQ_FOREACH(c, &cand_list, cand) { if (c == v) return (1); } return (0); } void cand_list_clr(void) { struct vertex *c; while ((c = TAILQ_FIRST(&cand_list)) != NULL) { TAILQ_REMOVE(&cand_list, c, cand); } } /* timers */ /* ARGSUSED */ void spf_timer(int fd, short event, void *arg) { struct vertex *v; struct ospfd_conf *conf = arg; struct area *area; struct rt_node *r; switch (conf->spf_state) { case SPF_IDLE: fatalx("spf_timer: invalid state IDLE"); case SPF_HOLDQUEUE: conf->spf_state = SPF_DELAY; /* FALLTHROUGH */ case SPF_DELAY: LIST_FOREACH(area, &conf->area_list, entry) { if (area->dirty) { /* invalidate RIB entries of this area */ rt_invalidate(area); /* calculate SPF tree */ spf_calc(area); /* calculate route table */ RB_FOREACH(v, lsa_tree, &area->lsa_tree) { rt_calc(v, area, conf); } area->dirty = 0; } } /* calculate as-external routes, first invalidate them */ rt_invalidate(NULL); RB_FOREACH(v, lsa_tree, &asext_tree) { asext_calc(v); } RB_FOREACH(r, rt_tree, &rt) { LIST_FOREACH(area, &conf->area_list, entry) rde_summary_update(r, area); if (r->d_type != DT_NET) continue; if (r->invalid) rde_send_delete_kroute(r); else rde_send_change_kroute(r); } LIST_FOREACH(area, &conf->area_list, entry) lsa_remove_invalid_sums(area); start_spf_holdtimer(conf); break; case SPF_HOLD: conf->spf_state = SPF_IDLE; break; default: fatalx("spf_timer: unknown state"); } } void start_spf_timer(void) { struct timeval tv; switch (rdeconf->spf_state) { case SPF_IDLE: timerclear(&tv); tv.tv_sec = rdeconf->spf_delay; rdeconf->spf_state = SPF_DELAY; if (evtimer_add(&rdeconf->ev, &tv) == -1) fatal("start_spf_timer"); break; case SPF_DELAY: /* ignore */ break; case SPF_HOLD: rdeconf->spf_state = SPF_HOLDQUEUE; break; case SPF_HOLDQUEUE: /* ignore */ break; default: fatalx("start_spf_timer: invalid spf_state"); } } void stop_spf_timer(struct ospfd_conf *conf) { if (evtimer_del(&conf->ev) == -1) fatal("stop_spf_timer"); } void start_spf_holdtimer(struct ospfd_conf *conf) { struct timeval tv; switch (conf->spf_state) { case SPF_DELAY: timerclear(&tv); tv.tv_sec = conf->spf_hold_time; conf->spf_state = SPF_HOLD; if (evtimer_add(&conf->ev, &tv) == -1) fatal("start_spf_holdtimer"); break; case SPF_IDLE: case SPF_HOLD: case SPF_HOLDQUEUE: fatalx("start_spf_holdtimer: invalid state"); default: fatalx("start_spf_holdtimer: unknown state"); } } /* route table */ void rt_init(void) { RB_INIT(&rt); } int rt_compare(struct rt_node *a, struct rt_node *b) { int i; /* XXX maybe a & b need to be switched */ i = memcmp(&a->prefix, &b->prefix, sizeof(a->prefix)); if (i) return (i); if (a->prefixlen < b->prefixlen) return (-1); if (a->prefixlen > b->prefixlen) return (1); if (a->d_type > b->d_type) return (-1); if (a->d_type < b->d_type) return (1); return (0); } struct rt_node * rt_find(struct in6_addr *prefix, u_int8_t prefixlen, enum dst_type d_type) { struct rt_node s; s.prefix = *prefix; s.prefixlen = prefixlen; s.d_type = d_type; return (RB_FIND(rt_tree, &rt, &s)); } int rt_insert(struct rt_node *r) { if (RB_INSERT(rt_tree, &rt, r) != NULL) { log_warnx("rt_insert failed for %s/%u", log_in6addr(&r->prefix), r->prefixlen); free(r); return (-1); } return (0); } int rt_remove(struct rt_node *r) { if (RB_REMOVE(rt_tree, &rt, r) == NULL) { log_warnx("rt_remove failed for %s/%u", log_in6addr(&r->prefix), r->prefixlen); return (-1); } rt_nexthop_clear(r); free(r); return (0); } void rt_invalidate(struct area *area) { struct rt_node *r, *nr; struct rt_nexthop *rn, *nrn; for (r = RB_MIN(rt_tree, &rt); r != NULL; r = nr) { nr = RB_NEXT(rt_tree, &rt, r); if (area == NULL) { /* look only at as_ext routes */ if (r->p_type != PT_TYPE1_EXT && r->p_type != PT_TYPE2_EXT) continue; } else { /* ignore all as_ext routes */ if (r->p_type == PT_TYPE1_EXT || r->p_type == PT_TYPE2_EXT) continue; /* look only at routes matching the area */ if (r->area.s_addr != area->id.s_addr) continue; } r->invalid = 1; for (rn = TAILQ_FIRST(&r->nexthop); rn != NULL; rn = nrn) { nrn = TAILQ_NEXT(rn, entry); if (rn->invalid) { TAILQ_REMOVE(&r->nexthop, rn, entry); free(rn); } else rn->invalid = 1; } if (TAILQ_EMPTY(&r->nexthop)) rt_remove(r); } } void rt_nexthop_clear(struct rt_node *r) { struct rt_nexthop *rn; while ((rn = TAILQ_FIRST(&r->nexthop)) != NULL) { TAILQ_REMOVE(&r->nexthop, rn, entry); free(rn); } } void rt_nexthop_add(struct rt_node *r, struct v_nexthead *vnh, struct in_addr adv_rtr) { struct v_nexthop *vn; struct rt_nexthop *rn; struct timespec now; TAILQ_FOREACH(vn, vnh, entry) { TAILQ_FOREACH(rn, &r->nexthop, entry) { if (!IN6_ARE_ADDR_EQUAL(&rn->nexthop, &vn->nexthop)) continue; rn->adv_rtr.s_addr = adv_rtr.s_addr; rn->connected = vn->prev == spf_root; rn->invalid = 0; r->invalid = 0; break; } if (rn) continue; if ((rn = calloc(1, sizeof(struct rt_nexthop))) == NULL) fatal("rt_nexthop_add"); clock_gettime(CLOCK_MONOTONIC, &now); rn->nexthop = vn->nexthop; rn->ifindex = vn->ifindex; rn->adv_rtr.s_addr = adv_rtr.s_addr; rn->uptime = now.tv_sec; rn->connected = vn->prev == spf_root; rn->invalid = 0; r->invalid = 0; TAILQ_INSERT_TAIL(&r->nexthop, rn, entry); } } void rt_clear(void) { struct rt_node *r; while ((r = RB_MIN(rt_tree, &rt)) != NULL) rt_remove(r); } void rt_dump(struct in_addr area, pid_t pid, u_int8_t r_type) { static struct ctl_rt rtctl; struct timespec now; struct rt_node *r; struct rt_nexthop *rn; clock_gettime(CLOCK_MONOTONIC, &now); RB_FOREACH(r, rt_tree, &rt) { if (r->invalid) continue; if (r->area.s_addr != area.s_addr) continue; switch (r_type) { case RIB_RTR: if (r->d_type != DT_RTR) continue; break; case RIB_NET: if (r->d_type != DT_NET) continue; if (r->p_type == PT_TYPE1_EXT || r->p_type == PT_TYPE2_EXT) continue; break; case RIB_EXT: if (r->p_type != PT_TYPE1_EXT && r->p_type != PT_TYPE2_EXT) continue; break; default: fatalx("rt_dump: invalid RIB type"); } TAILQ_FOREACH(rn, &r->nexthop, entry) { if (rn->invalid) continue; rtctl.prefix = r->prefix; rtctl.nexthop = rn->nexthop; rtctl.ifindex = rn->ifindex; rtctl.area.s_addr = r->area.s_addr; rtctl.adv_rtr.s_addr = rn->adv_rtr.s_addr; rtctl.cost = r->cost; rtctl.cost2 = r->cost2; rtctl.p_type = r->p_type; rtctl.d_type = r->d_type; rtctl.flags = r->flags; rtctl.prefixlen = r->prefixlen; rtctl.uptime = now.tv_sec - rn->uptime; rde_imsg_compose_ospfe(IMSG_CTL_SHOW_RIB, 0, pid, &rtctl, sizeof(rtctl)); } } } void rt_update(struct in6_addr *prefix, u_int8_t prefixlen, struct v_nexthead *vnh, u_int32_t cost, u_int32_t cost2, struct in_addr area, struct in_addr adv_rtr, enum path_type p_type, enum dst_type d_type, u_int8_t flags, u_int32_t tag) { struct rt_node *rte; struct rt_nexthop *rn; int better = 0, equal = 0; if (vnh == NULL || TAILQ_EMPTY(vnh)) /* XXX remove */ fatalx("rt_update: invalid nexthop"); if ((rte = rt_find(prefix, prefixlen, d_type)) == NULL) { if ((rte = calloc(1, sizeof(struct rt_node))) == NULL) fatal("rt_update"); TAILQ_INIT(&rte->nexthop); rte->prefix = *prefix; rte->prefixlen = prefixlen; rte->cost = cost; rte->cost2 = cost2; rte->area = area; rte->p_type = p_type; rte->d_type = d_type; rte->flags = flags; rte->ext_tag = tag; rt_nexthop_add(rte, vnh, adv_rtr); rt_insert(rte); } else { /* order: * 1. intra-area * 2. inter-area * 3. type 1 as ext * 4. type 2 as ext */ if (rte->invalid) /* everything is better than invalid */ better = 1; else if (p_type < rte->p_type) better = 1; else if (p_type == rte->p_type) switch (p_type) { case PT_INTRA_AREA: case PT_INTER_AREA: if (cost < rte->cost) better = 1; else if (cost == rte->cost && rte->area.s_addr == area.s_addr) equal = 1; break; case PT_TYPE1_EXT: if (cost < rte->cost) better = 1; else if (cost == rte->cost) equal = 1; break; case PT_TYPE2_EXT: if (cost2 < rte->cost2) better = 1; else if (cost2 == rte->cost2 && cost < rte->cost) better = 1; else if (cost2 == rte->cost2 && cost == rte->cost) equal = 1; break; } if (!better && !equal) return; if (better) { TAILQ_FOREACH(rn, &rte->nexthop, entry) rn->invalid = 1; rte->area = area; rte->cost = cost; rte->cost2 = cost2; rte->p_type = p_type; rte->flags = flags; rte->ext_tag = tag; } if (equal || better) rt_nexthop_add(rte, vnh, adv_rtr); } } struct rt_node * rt_lookup(enum dst_type type, struct in6_addr *addr) { struct rt_node *rn; struct in6_addr ina; u_int8_t i = 128; if (type == DT_RTR) { rn = rt_find(addr, 128, type); if (rn && rn->invalid == 0) return (rn); return (NULL); } /* type == DT_NET */ do { inet6applymask(&ina, addr, i); if ((rn = rt_find(&ina, i, type)) && rn->invalid == 0) return (rn); } while (i-- != 0); return (NULL); } /* router LSA links */ struct lsa_rtr_link * get_rtr_link(struct vertex *v, unsigned int idx) { struct lsa_rtr_link *rtr_link = NULL; unsigned int frag = 1; unsigned int frag_nlinks; unsigned int nlinks = 0; unsigned int i; if (v->type != LSA_TYPE_ROUTER) fatalx("get_rtr_link: invalid LSA type"); /* Treat multiple Router-LSAs originated by the same router * as an aggregate. */ do { /* number of links validated earlier by lsa_check() */ rtr_link = (struct lsa_rtr_link *)((char *)v->lsa + sizeof(v->lsa->hdr) + sizeof(struct lsa_rtr)); frag_nlinks = ((ntohs(v->lsa->hdr.len) - sizeof(struct lsa_hdr) - sizeof(struct lsa_rtr)) / sizeof(struct lsa_rtr_link)); if (nlinks + frag_nlinks > idx) { for (i = 0; i < frag_nlinks; i++) { if (i + nlinks == idx) return (rtr_link); rtr_link++; } } nlinks += frag_nlinks; v = lsa_find_rtr_frag(v->area, htonl(v->adv_rtr), frag++); } while (v); return (NULL); } /* network LSA links */ struct lsa_net_link * get_net_link(struct vertex *v, unsigned int idx) { struct lsa_net_link *net_link = NULL; char *buf = (char *)v->lsa; unsigned int i; if (v->type != LSA_TYPE_NETWORK) fatalx("get_net_link: invalid LSA type"); /* number of links validated earlier by lsa_check() */ net_link = (struct lsa_net_link *)(buf + sizeof(v->lsa->hdr) + sizeof(struct lsa_net)); for (i = 0; i < lsa_num_links(v); i++) { if (i == idx) return (net_link); net_link++; } return (NULL); } /* misc */ int linked(struct vertex *w, struct vertex *v) { struct lsa_rtr_link *rtr_link = NULL; struct lsa_net_link *net_link = NULL; unsigned int i; switch (w->type) { case LSA_TYPE_ROUTER: for (i = 0; i < lsa_num_links(w); i++) { rtr_link = get_rtr_link(w, i); switch (v->type) { case LSA_TYPE_ROUTER: if (rtr_link->type == LINK_TYPE_POINTTOPOINT && rtr_link->nbr_rtr_id == htonl(v->adv_rtr)) return (1); break; case LSA_TYPE_NETWORK: if (rtr_link->type == LINK_TYPE_TRANSIT_NET && rtr_link->nbr_rtr_id == htonl(v->adv_rtr) && rtr_link->nbr_iface_id == htonl(v->ls_id)) return (1); break; default: fatalx("linked: invalid type"); } } return (0); case LSA_TYPE_NETWORK: for (i = 0; i < lsa_num_links(w); i++) { net_link = get_net_link(w, i); switch (v->type) { case LSA_TYPE_ROUTER: if (net_link->att_rtr == htonl(v->adv_rtr)) return (1); break; default: fatalx("linked: invalid type"); } } return (0); default: fatalx("linked: invalid LSA type"); } return (0); }