OpenBSD-4.6/usr.sbin/ospf6d/rde_spf.c
/* $OpenBSD: rde_spf.c,v 1.14 2009/04/09 19:06:52 stsp Exp $ */
/*
* Copyright (c) 2005 Esben Norby <norby@openbsd.org>
*
* 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 <sys/types.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <arpa/inet.h>
#include <err.h>
#include <stdlib.h>
#include <strings.h>
#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 *);
void calc_nexthop_transit_nbr(struct vertex *, struct vertex *,
u_int32_t ifindex);
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 {
/* TODO: Treat multiple router LSAs originated by a single
* router as one aggregate. We don't do this [yet],
* but RFC5340 says we MUST do it. */
/* 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_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(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);
}
/* TODO: inter-area routes, as-external routes */
default:
break;
}
}
void
asext_calc(struct vertex *v)
{
#if 0
struct rt_node *r;
struct rt_nexthop *rn;
u_int32_t cost2;
struct in_addr addr, adv_rtr, a;
enum path_type type;
#endif
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;
#if 0 /* XXX this will be different for sure */
if ((r = rt_lookup(DT_RTR, htonl(v->adv_rtr))) == NULL)
return;
/* XXX RFC1583Compatibility */
if (v->lsa->data.asext.fw_addr != 0 &&
(r = rt_lookup(DT_NET, v->lsa->data.asext.fw_addr)) == NULL)
return;
if (v->lsa->data.asext.fw_addr != 0 &&
r->p_type != PT_INTRA_AREA &&
r->p_type != PT_INTER_AREA)
return;
if (ntohl(v->lsa->data.asext.metric) & LSA_ASEXT_E_FLAG) {
v->cost = r->cost;
cost2 = ntohl(v->lsa->data.asext.metric) &
LSA_METRIC_MASK;
type = PT_TYPE2_EXT;
} else {
v->cost = r->cost + (ntohl(v->lsa->data.asext.metric) &
LSA_METRIC_MASK);
cost2 = 0;
type = PT_TYPE1_EXT;
}
a.s_addr = 0;
adv_rtr.s_addr = htonl(v->adv_rtr);
addr.s_addr = htonl(v->ls_id) & v->lsa->data.asext.mask;
calc_nexthop_clear(v);
TAILQ_FOREACH(rn, &r->nexthop, entry) {
if (rn->invalid)
continue;
if (rn->connected && r->d_type == DT_NET) {
if (v->lsa->data.asext.fw_addr != 0)
calc_nexthop_add(v, NULL,
v->lsa->data.asext.fw_addr);
else
calc_nexthop_add(v, NULL,
htonl(v->adv_rtr));
} else
calc_nexthop_add(v, NULL, 0
/* XXX rn->nexthop.s_addri */);
}
rt_update(addr, mask2prefixlen(v->lsa->data.asext.mask),
&v->nexthop, v->cost, cost2, a, adv_rtr, type,
DT_NET, 0, ntohl(v->lsa->data.asext.ext_tag));
#endif
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)
{
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 (ntohl(rtr_link->iface_id) == iface->ifindex)
break;
}
if (!iface) {
warnx("calc_nexthop_lladdr: no interface found for ifindex");
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->nbr_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,
u_int32_t 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);
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);
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->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.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, 32, 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;
char *buf = (char *)v->lsa;
unsigned int i;
if (v->type != LSA_TYPE_ROUTER)
fatalx("get_rtr_link: invalid LSA type");
/* number of links validated earlier by lsa_check() */
rtr_link = (struct lsa_rtr_link *)(buf + sizeof(v->lsa->hdr) +
sizeof(struct lsa_rtr));
for (i = 0; i < lsa_num_links(v); i++) {
if (i == idx)
return (rtr_link);
rtr_link++;
}
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);
}