rde_spf.c revision 1.14
1/* $OpenBSD: rde_spf.c,v 1.14 2009/04/09 19:06:52 stsp Exp $ */ 2 3/* 4 * Copyright (c) 2005 Esben Norby <norby@openbsd.org> 5 * 6 * Permission to use, copy, modify, and distribute this software for any 7 * purpose with or without fee is hereby granted, provided that the above 8 * copyright notice and this permission notice appear in all copies. 9 * 10 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 11 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 12 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 13 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 14 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 15 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 16 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 17 */ 18 19#include <sys/types.h> 20#include <sys/socket.h> 21#include <netinet/in.h> 22#include <arpa/inet.h> 23#include <err.h> 24#include <stdlib.h> 25#include <strings.h> 26 27#include "ospf6d.h" 28#include "ospf6.h" 29#include "log.h" 30#include "rde.h" 31 32extern struct ospfd_conf *rdeconf; 33TAILQ_HEAD(, vertex) cand_list; 34RB_HEAD(rt_tree, rt_node) rt; 35RB_PROTOTYPE(rt_tree, rt_node, entry, rt_compare) 36RB_GENERATE(rt_tree, rt_node, entry, rt_compare) 37struct vertex *spf_root = NULL; 38 39void calc_nexthop_clear(struct vertex *); 40void calc_nexthop_add(struct vertex *, struct vertex *, 41 const struct in6_addr *, u_int32_t); 42struct in6_addr *calc_nexthop_lladdr(struct vertex *, struct lsa_rtr_link *); 43void calc_nexthop_transit_nbr(struct vertex *, struct vertex *, 44 u_int32_t ifindex); 45void calc_nexthop(struct vertex *, struct vertex *, 46 struct area *, struct lsa_rtr_link *); 47void rt_nexthop_clear(struct rt_node *); 48void rt_nexthop_add(struct rt_node *, struct v_nexthead *, 49 struct in_addr); 50void rt_update(struct in6_addr *, u_int8_t, struct v_nexthead *, 51 u_int32_t, u_int32_t, struct in_addr, struct in_addr, 52 enum path_type, enum dst_type, u_int8_t, u_int32_t); 53struct rt_node *rt_lookup(enum dst_type, struct in6_addr *); 54void rt_invalidate(struct area *); 55int linked(struct vertex *, struct vertex *); 56 57void 58spf_calc(struct area *area) 59{ 60 struct vertex *v, *w; 61 struct lsa_rtr_link *rtr_link = NULL; 62 struct lsa_net_link *net_link; 63 u_int32_t d; 64 unsigned int i; 65 66 /* clear SPF tree */ 67 spf_tree_clr(area); 68 cand_list_clr(); 69 70 /* initialize SPF tree */ 71 if ((v = spf_root = lsa_find_rtr(area, rde_router_id())) == NULL) 72 /* empty area because no interface is active */ 73 return; 74 75 area->transit = 0; 76 spf_root->cost = 0; 77 w = NULL; 78 79 /* calculate SPF tree */ 80 do { 81 /* TODO: Treat multiple router LSAs originated by a single 82 * router as one aggregate. We don't do this [yet], 83 * but RFC5340 says we MUST do it. */ 84 85 /* loop links */ 86 for (i = 0; i < lsa_num_links(v); i++) { 87 switch (v->type) { 88 case LSA_TYPE_ROUTER: 89 rtr_link = get_rtr_link(v, i); 90 switch (rtr_link->type) { 91 case LINK_TYPE_POINTTOPOINT: 92 case LINK_TYPE_VIRTUAL: 93 /* find router LSA */ 94 w = lsa_find_rtr(area, 95 rtr_link->nbr_rtr_id); 96 break; 97 case LINK_TYPE_TRANSIT_NET: 98 /* find network LSA */ 99 w = lsa_find_tree(&area->lsa_tree, 100 htons(LSA_TYPE_NETWORK), 101 rtr_link->nbr_iface_id, 102 rtr_link->nbr_rtr_id); 103 break; 104 default: 105 fatalx("spf_calc: invalid link type"); 106 } 107 break; 108 case LSA_TYPE_NETWORK: 109 net_link = get_net_link(v, i); 110 /* find router LSA */ 111 w = lsa_find_rtr(area, net_link->att_rtr); 112 break; 113 default: 114 fatalx("spf_calc: invalid LSA type"); 115 } 116 117 if (w == NULL) 118 continue; 119 120 if (ntohs(w->lsa->hdr.age) == MAX_AGE) 121 continue; 122 123 if (lsa_num_links(w) == 0) 124 continue; 125 126 if (!linked(w, v)) { 127 log_debug("spf_calc: w adv_rtr %s ls_id %s " 128 "type 0x%x numlinks %hu has no link to " 129 "v adv_rtr %s ls_id %s type 0x%x", 130 log_rtr_id(htonl(w->adv_rtr)), 131 log_rtr_id(htonl(w->ls_id)), w->type, 132 lsa_num_links(w), 133 log_rtr_id(htonl(v->adv_rtr)), 134 log_rtr_id(htonl(v->ls_id)), v->type); 135 continue; 136 } 137 138 if (v->type == LSA_TYPE_ROUTER) 139 d = v->cost + ntohs(rtr_link->metric); 140 else 141 d = v->cost; 142 143 if (cand_list_present(w)) { 144 if (d > w->cost) 145 continue; 146 if (d < w->cost) { 147 w->cost = d; 148 calc_nexthop_clear(w); 149 calc_nexthop(w, v, area, rtr_link); 150 /* 151 * need to readd to candidate list 152 * because the list is sorted 153 */ 154 TAILQ_REMOVE(&cand_list, w, cand); 155 cand_list_add(w); 156 } else 157 /* equal cost path */ 158 calc_nexthop(w, v, area, rtr_link); 159 } else if (w->cost == LS_INFINITY && d < LS_INFINITY) { 160 w->cost = d; 161 162 calc_nexthop_clear(w); 163 calc_nexthop(w, v, area, rtr_link); 164 cand_list_add(w); 165 } 166 } 167 168 /* get next vertex */ 169 v = cand_list_pop(); 170 w = NULL; 171 } while (v != NULL); 172 173 /* spf_dump(area); */ 174 log_debug("spf_calc: area %s calculated", inet_ntoa(area->id)); 175 176 /* Dump SPF tree to log */ 177 RB_FOREACH(v, lsa_tree, &area->lsa_tree) { 178 struct v_nexthop *vn; 179 char hops[4096]; 180 struct iface *iface; 181 182 bzero(hops, sizeof(hops)); 183 184 if (v->type != LSA_TYPE_ROUTER && v->type != LSA_TYPE_NETWORK) 185 continue; 186 187 TAILQ_FOREACH(vn, &v->nexthop, entry) { 188 strlcat(hops, log_in6addr(&vn->nexthop), sizeof(hops)); 189 strlcat(hops, "%", sizeof(hops)); 190 if ((iface = if_find(vn->ifindex)) == NULL) 191 fatalx("spf_calc: lost iface"); 192 strlcat(hops, iface->name, sizeof(hops)); 193 if (vn != TAILQ_LAST(&v->nexthop, v_nexthead)) 194 strlcat(hops, ", ", sizeof(hops)); 195 } 196 log_debug("%s(%s, 0x%x, %s) cost %u has nexthops [%s]", 197 v == spf_root ? "*" : " ", log_rtr_id(htonl(v->adv_rtr)), 198 v->type, log_rtr_id(htonl(v->ls_id)), v->cost, hops); 199 } 200 201 area->num_spf_calc++; 202 start_spf_timer(); 203} 204 205void 206rt_calc(struct vertex *v, struct area *area, struct ospfd_conf *conf) 207{ 208 struct vertex *w; 209 struct lsa_intra_prefix *iap; 210 struct lsa_prefix *prefix; 211 struct in_addr adv_rtr; 212 struct in6_addr ia6; 213 u_int16_t i, off; 214 u_int8_t flags; 215 216 lsa_age(v); 217 if (ntohs(v->lsa->hdr.age) == MAX_AGE) 218 return; 219 220 switch (v->type) { 221 case LSA_TYPE_INTRA_A_PREFIX: 222 /* Find referenced LSA */ 223 iap = &v->lsa->data.pref_intra; 224 switch (ntohs(iap->ref_type)) { 225 case LSA_TYPE_ROUTER: 226 w = lsa_find_rtr(area, iap->ref_adv_rtr); 227 if (w == NULL) { 228 warnx("rt_calc: Intra-Area-Prefix LSA (%s, %u) " 229 "references non-existent router %s", 230 log_rtr_id(htonl(v->adv_rtr)), 231 v->ls_id, log_rtr_id(iap->ref_adv_rtr)); 232 return; 233 } 234 flags = LSA_24_GETHI(w->lsa->data.rtr.opts); 235 break; 236 case LSA_TYPE_NETWORK: 237 w = lsa_find_tree(&area->lsa_tree, iap->ref_type, 238 iap->ref_ls_id, iap->ref_adv_rtr); 239 if (w == NULL) { 240 warnx("rt_calc: Intra-Area-Prefix LSA (%s, %u) " 241 "references non-existent Network LSA (%s, " 242 "%u)", log_rtr_id(htonl(v->adv_rtr)), 243 v->ls_id, log_rtr_id(iap->ref_adv_rtr), 244 ntohl(iap->ref_ls_id)); 245 return; 246 } 247 flags = 0; 248 break; 249 default: 250 warnx("rt_calc: Intra-Area-Prefix LSA (%s, %u) has " 251 "invalid ref_type 0x%hx", log_rtr_id(v->adv_rtr), 252 v->ls_id, ntohs(iap->ref_type)); 253 return; 254 } 255 256 if (w->cost >= LS_INFINITY || TAILQ_EMPTY(&w->nexthop)) 257 return; 258 259 /* Add prefixes listed in Intra-Area-Prefix LSA to routing 260 * table, using w as destination. */ 261 off = sizeof(v->lsa->hdr) + sizeof(struct lsa_intra_prefix); 262 for (i = 0; i < ntohs(v->lsa->data.pref_intra.numprefix); i++) { 263 prefix = (struct lsa_prefix *)((char *)(v->lsa) + off); 264 if (!(prefix->options & OSPF_PREFIX_NU)) { 265 bzero(&ia6, sizeof(ia6)); 266 bcopy(prefix + 1, &ia6, 267 LSA_PREFIXSIZE(prefix->prefixlen)); 268 269 adv_rtr.s_addr = htonl(w->adv_rtr); 270 271 rt_update(&ia6, prefix->prefixlen, &w->nexthop, 272 w->cost + ntohs(prefix->metric), 0, 273 area->id, adv_rtr, PT_INTRA_AREA, DT_NET, 274 flags, 0); 275 } 276 off += sizeof(struct lsa_prefix) 277 + LSA_PREFIXSIZE(prefix->prefixlen); 278 } 279 /* TODO: inter-area routes, as-external routes */ 280 default: 281 break; 282 } 283} 284 285void 286asext_calc(struct vertex *v) 287{ 288#if 0 289 struct rt_node *r; 290 struct rt_nexthop *rn; 291 u_int32_t cost2; 292 struct in_addr addr, adv_rtr, a; 293 enum path_type type; 294#endif 295 296 lsa_age(v); 297 if (ntohs(v->lsa->hdr.age) == MAX_AGE || 298 (ntohl(v->lsa->data.asext.metric) & LSA_METRIC_MASK) >= 299 LS_INFINITY) 300 return; 301 302 switch (v->type) { 303 case LSA_TYPE_EXTERNAL: 304 /* ignore self-originated stuff */ 305 if (v->self) 306 return; 307 308#if 0 /* XXX this will be different for sure */ 309 if ((r = rt_lookup(DT_RTR, htonl(v->adv_rtr))) == NULL) 310 return; 311 312 /* XXX RFC1583Compatibility */ 313 if (v->lsa->data.asext.fw_addr != 0 && 314 (r = rt_lookup(DT_NET, v->lsa->data.asext.fw_addr)) == NULL) 315 return; 316 317 if (v->lsa->data.asext.fw_addr != 0 && 318 r->p_type != PT_INTRA_AREA && 319 r->p_type != PT_INTER_AREA) 320 return; 321 322 if (ntohl(v->lsa->data.asext.metric) & LSA_ASEXT_E_FLAG) { 323 v->cost = r->cost; 324 cost2 = ntohl(v->lsa->data.asext.metric) & 325 LSA_METRIC_MASK; 326 type = PT_TYPE2_EXT; 327 } else { 328 v->cost = r->cost + (ntohl(v->lsa->data.asext.metric) & 329 LSA_METRIC_MASK); 330 cost2 = 0; 331 type = PT_TYPE1_EXT; 332 } 333 334 a.s_addr = 0; 335 adv_rtr.s_addr = htonl(v->adv_rtr); 336 addr.s_addr = htonl(v->ls_id) & v->lsa->data.asext.mask; 337 338 calc_nexthop_clear(v); 339 TAILQ_FOREACH(rn, &r->nexthop, entry) { 340 if (rn->invalid) 341 continue; 342 343 if (rn->connected && r->d_type == DT_NET) { 344 if (v->lsa->data.asext.fw_addr != 0) 345 calc_nexthop_add(v, NULL, 346 v->lsa->data.asext.fw_addr); 347 else 348 calc_nexthop_add(v, NULL, 349 htonl(v->adv_rtr)); 350 } else 351 calc_nexthop_add(v, NULL, 0 352 /* XXX rn->nexthop.s_addri */); 353 } 354 355 rt_update(addr, mask2prefixlen(v->lsa->data.asext.mask), 356 &v->nexthop, v->cost, cost2, a, adv_rtr, type, 357 DT_NET, 0, ntohl(v->lsa->data.asext.ext_tag)); 358#endif 359 break; 360 default: 361 fatalx("asext_calc: invalid LSA type"); 362 } 363} 364 365void 366spf_tree_clr(struct area *area) 367{ 368 struct lsa_tree *tree = &area->lsa_tree; 369 struct vertex *v; 370 371 RB_FOREACH(v, lsa_tree, tree) { 372 v->cost = LS_INFINITY; 373 calc_nexthop_clear(v); 374 } 375} 376 377void 378calc_nexthop_clear(struct vertex *v) 379{ 380 struct v_nexthop *vn; 381 382 while ((vn = TAILQ_FIRST(&v->nexthop))) { 383 TAILQ_REMOVE(&v->nexthop, vn, entry); 384 free(vn); 385 } 386} 387 388void 389calc_nexthop_add(struct vertex *dst, struct vertex *parent, 390 const struct in6_addr *nexthop, u_int32_t ifindex) 391{ 392 struct v_nexthop *vn; 393 394 if ((vn = calloc(1, sizeof(*vn))) == NULL) 395 fatal("calc_nexthop_add"); 396 397 vn->prev = parent; 398 if (nexthop) 399 vn->nexthop = *nexthop; 400 vn->ifindex = ifindex; 401 402 TAILQ_INSERT_TAIL(&dst->nexthop, vn, entry); 403} 404 405struct in6_addr * 406calc_nexthop_lladdr(struct vertex *dst, struct lsa_rtr_link *rtr_link) 407{ 408 struct iface *iface; 409 struct vertex *link; 410 struct rde_nbr *nbr; 411 412 /* Find outgoing interface, we need its LSA tree */ 413 LIST_FOREACH(iface, &dst->area->iface_list, entry) { 414 if (ntohl(rtr_link->iface_id) == iface->ifindex) 415 break; 416 } 417 if (!iface) { 418 warnx("calc_nexthop_lladdr: no interface found for ifindex"); 419 return (NULL); 420 } 421 422 /* Determine neighbor's link-local address. 423 * Try to get it from link LSA first. */ 424 link = lsa_find_tree(&iface->lsa_tree, 425 htons(LSA_TYPE_LINK), rtr_link->nbr_iface_id, 426 htonl(dst->adv_rtr)); 427 if (link) 428 return &link->lsa->data.link.lladdr; 429 430 /* Not found, so fall back to source address 431 * advertised in hello packet. */ 432 if ((nbr = rde_nbr_find(dst->peerid)) == NULL) 433 fatalx("next hop is not a neighbor"); 434 return &nbr->addr; 435} 436 437void 438calc_nexthop_transit_nbr(struct vertex *dst, struct vertex *parent, 439 u_int32_t ifindex) 440{ 441 struct lsa_rtr_link *rtr_link; 442 unsigned int i; 443 struct in6_addr *lladdr; 444 445 if (dst->type != LSA_TYPE_ROUTER) 446 fatalx("calc_nexthop_transit_nbr: dst is not a router"); 447 if (parent->type != LSA_TYPE_NETWORK) 448 fatalx("calc_nexthop_transit_nbr: parent is not a network"); 449 450 /* dst is a neighbor on a directly attached transit network. 451 * Figure out dst's link local address and add it as nexthop. */ 452 for (i = 0; i < lsa_num_links(dst); i++) { 453 rtr_link = get_rtr_link(dst, i); 454 if (rtr_link->type == LINK_TYPE_TRANSIT_NET && 455 rtr_link->nbr_rtr_id == parent->lsa->hdr.adv_rtr && 456 rtr_link->nbr_iface_id == parent->lsa->hdr.ls_id) { 457 lladdr = calc_nexthop_lladdr(dst, rtr_link); 458 calc_nexthop_add(dst, parent, lladdr, ifindex); 459 } 460 } 461} 462 463void 464calc_nexthop(struct vertex *dst, struct vertex *parent, 465 struct area *area, struct lsa_rtr_link *rtr_link) 466{ 467 struct v_nexthop *vn; 468 struct in6_addr *nexthop; 469 470 /* case 1 */ 471 if (parent == spf_root) { 472 switch (dst->type) { 473 case LSA_TYPE_ROUTER: 474 if (rtr_link->type != LINK_TYPE_POINTTOPOINT) 475 fatalx("inconsistent SPF tree"); 476 nexthop = calc_nexthop_lladdr(dst, rtr_link); 477 break; 478 case LSA_TYPE_NETWORK: 479 if (rtr_link->type != LINK_TYPE_TRANSIT_NET) 480 fatalx("inconsistent SPF tree"); 481 482 /* Next hop address cannot be determined yet, 483 * we only know the outgoing interface. */ 484 nexthop = NULL; 485 break; 486 default: 487 fatalx("calc_nexthop: invalid dst type"); 488 } 489 490 calc_nexthop_add(dst, spf_root, nexthop, 491 ntohl(rtr_link->iface_id)); 492 return; 493 } 494 495 /* case 2 */ 496 if (parent->type == LSA_TYPE_NETWORK && dst->type == LSA_TYPE_ROUTER) { 497 TAILQ_FOREACH(vn, &parent->nexthop, entry) { 498 if (vn->prev == spf_root) 499 calc_nexthop_transit_nbr(dst, parent, 500 vn->ifindex); 501 else 502 /* dst is more than one transit net away */ 503 calc_nexthop_add(dst, parent, &vn->nexthop, 504 vn->ifindex); 505 } 506 return; 507 } 508 509 /* case 3 */ 510 TAILQ_FOREACH(vn, &parent->nexthop, entry) 511 calc_nexthop_add(dst, parent, &vn->nexthop, vn->ifindex); 512} 513 514/* candidate list */ 515void 516cand_list_init(void) 517{ 518 TAILQ_INIT(&cand_list); 519} 520 521void 522cand_list_add(struct vertex *v) 523{ 524 struct vertex *c = NULL; 525 526 TAILQ_FOREACH(c, &cand_list, cand) { 527 if (c->cost > v->cost) { 528 TAILQ_INSERT_BEFORE(c, v, cand); 529 return; 530 } else if (c->cost == v->cost && c->type == LSA_TYPE_ROUTER && 531 v->type == LSA_TYPE_NETWORK) { 532 TAILQ_INSERT_BEFORE(c, v, cand); 533 return; 534 } 535 } 536 TAILQ_INSERT_TAIL(&cand_list, v, cand); 537} 538 539struct vertex * 540cand_list_pop(void) 541{ 542 struct vertex *c; 543 544 if ((c = TAILQ_FIRST(&cand_list)) != NULL) { 545 TAILQ_REMOVE(&cand_list, c, cand); 546 } 547 548 return (c); 549} 550 551int 552cand_list_present(struct vertex *v) 553{ 554 struct vertex *c; 555 556 TAILQ_FOREACH(c, &cand_list, cand) { 557 if (c == v) 558 return (1); 559 } 560 561 return (0); 562} 563 564void 565cand_list_clr(void) 566{ 567 struct vertex *c; 568 569 while ((c = TAILQ_FIRST(&cand_list)) != NULL) { 570 TAILQ_REMOVE(&cand_list, c, cand); 571 } 572} 573 574/* timers */ 575/* ARGSUSED */ 576void 577spf_timer(int fd, short event, void *arg) 578{ 579 struct vertex *v; 580 struct ospfd_conf *conf = arg; 581 struct area *area; 582 struct rt_node *r; 583 584 switch (conf->spf_state) { 585 case SPF_IDLE: 586 fatalx("spf_timer: invalid state IDLE"); 587 case SPF_HOLDQUEUE: 588 conf->spf_state = SPF_DELAY; 589 /* FALLTHROUGH */ 590 case SPF_DELAY: 591 LIST_FOREACH(area, &conf->area_list, entry) { 592 if (area->dirty) { 593 /* invalidate RIB entries of this area */ 594 rt_invalidate(area); 595 596 /* calculate SPF tree */ 597 spf_calc(area); 598 599 /* calculate route table */ 600 RB_FOREACH(v, lsa_tree, &area->lsa_tree) { 601 rt_calc(v, area, conf); 602 } 603 604 area->dirty = 0; 605 } 606 } 607 608 /* calculate as-external routes, first invalidate them */ 609 rt_invalidate(NULL); 610 RB_FOREACH(v, lsa_tree, &asext_tree) { 611 asext_calc(v); 612 } 613 614 RB_FOREACH(r, rt_tree, &rt) { 615 LIST_FOREACH(area, &conf->area_list, entry) 616 rde_summary_update(r, area); 617 618 if (r->d_type != DT_NET) 619 continue; 620 621 if (r->invalid) 622 rde_send_delete_kroute(r); 623 else 624 rde_send_change_kroute(r); 625 } 626 627 LIST_FOREACH(area, &conf->area_list, entry) 628 lsa_remove_invalid_sums(area); 629 630 start_spf_holdtimer(conf); 631 break; 632 case SPF_HOLD: 633 conf->spf_state = SPF_IDLE; 634 break; 635 default: 636 fatalx("spf_timer: unknown state"); 637 } 638} 639 640void 641start_spf_timer(void) 642{ 643 struct timeval tv; 644 645 switch (rdeconf->spf_state) { 646 case SPF_IDLE: 647 timerclear(&tv); 648 tv.tv_sec = rdeconf->spf_delay; 649 rdeconf->spf_state = SPF_DELAY; 650 if (evtimer_add(&rdeconf->ev, &tv) == -1) 651 fatal("start_spf_timer"); 652 break; 653 case SPF_DELAY: 654 /* ignore */ 655 break; 656 case SPF_HOLD: 657 rdeconf->spf_state = SPF_HOLDQUEUE; 658 break; 659 case SPF_HOLDQUEUE: 660 /* ignore */ 661 break; 662 default: 663 fatalx("start_spf_timer: invalid spf_state"); 664 } 665} 666 667void 668stop_spf_timer(struct ospfd_conf *conf) 669{ 670 if (evtimer_del(&conf->ev) == -1) 671 fatal("stop_spf_timer"); 672} 673 674void 675start_spf_holdtimer(struct ospfd_conf *conf) 676{ 677 struct timeval tv; 678 679 switch (conf->spf_state) { 680 case SPF_DELAY: 681 timerclear(&tv); 682 tv.tv_sec = conf->spf_hold_time; 683 conf->spf_state = SPF_HOLD; 684 if (evtimer_add(&conf->ev, &tv) == -1) 685 fatal("start_spf_holdtimer"); 686 break; 687 case SPF_IDLE: 688 case SPF_HOLD: 689 case SPF_HOLDQUEUE: 690 fatalx("start_spf_holdtimer: invalid state"); 691 default: 692 fatalx("start_spf_holdtimer: unknown state"); 693 } 694} 695 696/* route table */ 697void 698rt_init(void) 699{ 700 RB_INIT(&rt); 701} 702 703int 704rt_compare(struct rt_node *a, struct rt_node *b) 705{ 706 int i; 707 708 /* XXX maybe a & b need to be switched */ 709 i = memcmp(&a->prefix, &b->prefix, sizeof(a->prefix)); 710 if (i) 711 return (i); 712 if (a->prefixlen < b->prefixlen) 713 return (-1); 714 if (a->prefixlen > b->prefixlen) 715 return (1); 716 if (a->d_type > b->d_type) 717 return (-1); 718 if (a->d_type < b->d_type) 719 return (1); 720 return (0); 721} 722 723struct rt_node * 724rt_find(struct in6_addr *prefix, u_int8_t prefixlen, enum dst_type d_type) 725{ 726 struct rt_node s; 727 728 s.prefix = *prefix; 729 s.prefixlen = prefixlen; 730 s.d_type = d_type; 731 732 return (RB_FIND(rt_tree, &rt, &s)); 733} 734 735int 736rt_insert(struct rt_node *r) 737{ 738 if (RB_INSERT(rt_tree, &rt, r) != NULL) { 739 log_warnx("rt_insert failed for %s/%u", 740 log_in6addr(&r->prefix), r->prefixlen); 741 free(r); 742 return (-1); 743 } 744 745 return (0); 746} 747 748int 749rt_remove(struct rt_node *r) 750{ 751 if (RB_REMOVE(rt_tree, &rt, r) == NULL) { 752 log_warnx("rt_remove failed for %s/%u", 753 log_in6addr(&r->prefix), r->prefixlen); 754 return (-1); 755 } 756 757 rt_nexthop_clear(r); 758 free(r); 759 return (0); 760} 761 762void 763rt_invalidate(struct area *area) 764{ 765 struct rt_node *r, *nr; 766 struct rt_nexthop *rn, *nrn; 767 768 for (r = RB_MIN(rt_tree, &rt); r != NULL; r = nr) { 769 nr = RB_NEXT(rt_tree, &rt, r); 770 if (area == NULL) { 771 /* look only at as_ext routes */ 772 if (r->p_type != PT_TYPE1_EXT && 773 r->p_type != PT_TYPE2_EXT) 774 continue; 775 } else { 776 /* ignore all as_ext routes */ 777 if (r->p_type == PT_TYPE1_EXT || 778 r->p_type == PT_TYPE2_EXT) 779 continue; 780 781 /* look only at routes matching the area */ 782 if (r->area.s_addr != area->id.s_addr) 783 continue; 784 } 785 r->invalid = 1; 786 for (rn = TAILQ_FIRST(&r->nexthop); rn != NULL; rn = nrn) { 787 nrn = TAILQ_NEXT(rn, entry); 788 if (rn->invalid) { 789 TAILQ_REMOVE(&r->nexthop, rn, entry); 790 free(rn); 791 } else 792 rn->invalid = 1; 793 } 794 if (TAILQ_EMPTY(&r->nexthop)) 795 rt_remove(r); 796 } 797} 798 799void 800rt_nexthop_clear(struct rt_node *r) 801{ 802 struct rt_nexthop *rn; 803 804 while ((rn = TAILQ_FIRST(&r->nexthop)) != NULL) { 805 TAILQ_REMOVE(&r->nexthop, rn, entry); 806 free(rn); 807 } 808} 809 810void 811rt_nexthop_add(struct rt_node *r, struct v_nexthead *vnh, 812 struct in_addr adv_rtr) 813{ 814 struct v_nexthop *vn; 815 struct rt_nexthop *rn; 816 struct timespec now; 817 818 TAILQ_FOREACH(vn, vnh, entry) { 819 TAILQ_FOREACH(rn, &r->nexthop, entry) { 820 if (!IN6_ARE_ADDR_EQUAL(&rn->nexthop, &vn->nexthop)) 821 continue; 822 823 rn->adv_rtr.s_addr = adv_rtr.s_addr; 824 rn->connected = vn->prev == spf_root; 825 rn->invalid = 0; 826 827 r->invalid = 0; 828 break; 829 } 830 if (rn) 831 continue; 832 833 if ((rn = calloc(1, sizeof(struct rt_nexthop))) == NULL) 834 fatal("rt_nexthop_add"); 835 836 clock_gettime(CLOCK_MONOTONIC, &now); 837 rn->nexthop = vn->nexthop; 838 rn->adv_rtr.s_addr = adv_rtr.s_addr; 839 rn->uptime = now.tv_sec; 840 rn->connected = vn->prev == spf_root; 841 rn->invalid = 0; 842 843 r->invalid = 0; 844 TAILQ_INSERT_TAIL(&r->nexthop, rn, entry); 845 } 846} 847 848void 849rt_clear(void) 850{ 851 struct rt_node *r; 852 853 while ((r = RB_MIN(rt_tree, &rt)) != NULL) 854 rt_remove(r); 855} 856 857void 858rt_dump(struct in_addr area, pid_t pid, u_int8_t r_type) 859{ 860 static struct ctl_rt rtctl; 861 struct timespec now; 862 struct rt_node *r; 863 struct rt_nexthop *rn; 864 865 clock_gettime(CLOCK_MONOTONIC, &now); 866 867 RB_FOREACH(r, rt_tree, &rt) { 868 if (r->invalid) 869 continue; 870 871 if (r->area.s_addr != area.s_addr) 872 continue; 873 874 switch (r_type) { 875 case RIB_RTR: 876 if (r->d_type != DT_RTR) 877 continue; 878 break; 879 case RIB_NET: 880 if (r->d_type != DT_NET) 881 continue; 882 if (r->p_type == PT_TYPE1_EXT || 883 r->p_type == PT_TYPE2_EXT) 884 continue; 885 break; 886 case RIB_EXT: 887 if (r->p_type != PT_TYPE1_EXT && 888 r->p_type != PT_TYPE2_EXT) 889 continue; 890 break; 891 default: 892 fatalx("rt_dump: invalid RIB type"); 893 } 894 895 TAILQ_FOREACH(rn, &r->nexthop, entry) { 896 if (rn->invalid) 897 continue; 898 899 rtctl.prefix = r->prefix; 900 rtctl.nexthop = rn->nexthop; 901 rtctl.area.s_addr = r->area.s_addr; 902 rtctl.adv_rtr.s_addr = rn->adv_rtr.s_addr; 903 rtctl.cost = r->cost; 904 rtctl.cost2 = r->cost2; 905 rtctl.p_type = r->p_type; 906 rtctl.d_type = r->d_type; 907 rtctl.flags = r->flags; 908 rtctl.prefixlen = r->prefixlen; 909 rtctl.uptime = now.tv_sec - rn->uptime; 910 911 rde_imsg_compose_ospfe(IMSG_CTL_SHOW_RIB, 0, pid, 912 &rtctl, sizeof(rtctl)); 913 } 914 } 915} 916 917void 918rt_update(struct in6_addr *prefix, u_int8_t prefixlen, struct v_nexthead *vnh, 919 u_int32_t cost, u_int32_t cost2, struct in_addr area, 920 struct in_addr adv_rtr, enum path_type p_type, enum dst_type d_type, 921 u_int8_t flags, u_int32_t tag) 922{ 923 struct rt_node *rte; 924 struct rt_nexthop *rn; 925 int better = 0, equal = 0; 926 927 if (vnh == NULL || TAILQ_EMPTY(vnh)) /* XXX remove */ 928 fatalx("rt_update: invalid nexthop"); 929 930 if ((rte = rt_find(prefix, prefixlen, d_type)) == NULL) { 931 if ((rte = calloc(1, sizeof(struct rt_node))) == NULL) 932 fatal("rt_update"); 933 934 TAILQ_INIT(&rte->nexthop); 935 rte->prefix = *prefix; 936 rte->prefixlen = prefixlen; 937 rte->cost = cost; 938 rte->cost2 = cost2; 939 rte->area = area; 940 rte->p_type = p_type; 941 rte->d_type = d_type; 942 rte->flags = flags; 943 rte->ext_tag = tag; 944 945 rt_nexthop_add(rte, vnh, adv_rtr); 946 947 rt_insert(rte); 948 } else { 949 /* order: 950 * 1. intra-area 951 * 2. inter-area 952 * 3. type 1 as ext 953 * 4. type 2 as ext 954 */ 955 if (rte->invalid) /* everything is better than invalid */ 956 better = 1; 957 else if (p_type < rte->p_type) 958 better = 1; 959 else if (p_type == rte->p_type) 960 switch (p_type) { 961 case PT_INTRA_AREA: 962 case PT_INTER_AREA: 963 if (cost < rte->cost) 964 better = 1; 965 else if (cost == rte->cost && 966 rte->area.s_addr == area.s_addr) 967 equal = 1; 968 break; 969 case PT_TYPE1_EXT: 970 if (cost < rte->cost) 971 better = 1; 972 else if (cost == rte->cost) 973 equal = 1; 974 break; 975 case PT_TYPE2_EXT: 976 if (cost2 < rte->cost2) 977 better = 1; 978 else if (cost2 == rte->cost2 && 979 cost < rte->cost) 980 better = 1; 981 else if (cost2 == rte->cost2 && 982 cost == rte->cost) 983 equal = 1; 984 break; 985 } 986 987 if (!better && !equal) 988 return; 989 990 if (better) { 991 TAILQ_FOREACH(rn, &rte->nexthop, entry) 992 rn->invalid = 1; 993 994 rte->area = area; 995 rte->cost = cost; 996 rte->cost2 = cost2; 997 rte->p_type = p_type; 998 rte->flags = flags; 999 rte->ext_tag = tag; 1000 } 1001 1002 if (equal || better) 1003 rt_nexthop_add(rte, vnh, adv_rtr); 1004 } 1005} 1006 1007struct rt_node * 1008rt_lookup(enum dst_type type, struct in6_addr *addr) 1009{ 1010 struct rt_node *rn; 1011 struct in6_addr ina; 1012 u_int8_t i = 128; 1013 1014 if (type == DT_RTR) { 1015 rn = rt_find(addr, 32, type); 1016 if (rn && rn->invalid == 0) 1017 return (rn); 1018 return (NULL); 1019 } 1020 1021 /* type == DT_NET */ 1022 do { 1023 inet6applymask(&ina, addr, i); 1024 if ((rn = rt_find(&ina, i, type)) && rn->invalid == 0) 1025 return (rn); 1026 } while (i-- != 0); 1027 1028 return (NULL); 1029} 1030 1031/* router LSA links */ 1032struct lsa_rtr_link * 1033get_rtr_link(struct vertex *v, unsigned int idx) 1034{ 1035 struct lsa_rtr_link *rtr_link = NULL; 1036 char *buf = (char *)v->lsa; 1037 unsigned int i; 1038 1039 if (v->type != LSA_TYPE_ROUTER) 1040 fatalx("get_rtr_link: invalid LSA type"); 1041 1042 /* number of links validated earlier by lsa_check() */ 1043 rtr_link = (struct lsa_rtr_link *)(buf + sizeof(v->lsa->hdr) + 1044 sizeof(struct lsa_rtr)); 1045 for (i = 0; i < lsa_num_links(v); i++) { 1046 if (i == idx) 1047 return (rtr_link); 1048 rtr_link++; 1049 } 1050 1051 return (NULL); 1052} 1053 1054/* network LSA links */ 1055struct lsa_net_link * 1056get_net_link(struct vertex *v, unsigned int idx) 1057{ 1058 struct lsa_net_link *net_link = NULL; 1059 char *buf = (char *)v->lsa; 1060 unsigned int i; 1061 1062 if (v->type != LSA_TYPE_NETWORK) 1063 fatalx("get_net_link: invalid LSA type"); 1064 1065 /* number of links validated earlier by lsa_check() */ 1066 net_link = (struct lsa_net_link *)(buf + sizeof(v->lsa->hdr) + 1067 sizeof(struct lsa_net)); 1068 for (i = 0; i < lsa_num_links(v); i++) { 1069 if (i == idx) 1070 return (net_link); 1071 net_link++; 1072 } 1073 1074 return (NULL); 1075} 1076 1077/* misc */ 1078int 1079linked(struct vertex *w, struct vertex *v) 1080{ 1081 struct lsa_rtr_link *rtr_link = NULL; 1082 struct lsa_net_link *net_link = NULL; 1083 unsigned int i; 1084 1085 switch (w->type) { 1086 case LSA_TYPE_ROUTER: 1087 for (i = 0; i < lsa_num_links(w); i++) { 1088 rtr_link = get_rtr_link(w, i); 1089 switch (v->type) { 1090 case LSA_TYPE_ROUTER: 1091 if (rtr_link->type == LINK_TYPE_POINTTOPOINT && 1092 rtr_link->nbr_rtr_id == htonl(v->adv_rtr)) 1093 return (1); 1094 break; 1095 case LSA_TYPE_NETWORK: 1096 if (rtr_link->type == LINK_TYPE_TRANSIT_NET && 1097 rtr_link->nbr_rtr_id == htonl(v->adv_rtr) && 1098 rtr_link->nbr_iface_id == htonl(v->ls_id)) 1099 return (1); 1100 break; 1101 default: 1102 fatalx("linked: invalid type"); 1103 } 1104 } 1105 return (0); 1106 case LSA_TYPE_NETWORK: 1107 for (i = 0; i < lsa_num_links(w); i++) { 1108 net_link = get_net_link(w, i); 1109 switch (v->type) { 1110 case LSA_TYPE_ROUTER: 1111 if (net_link->att_rtr == htonl(v->adv_rtr)) 1112 return (1); 1113 break; 1114 default: 1115 fatalx("linked: invalid type"); 1116 } 1117 } 1118 return (0); 1119 default: 1120 fatalx("linked: invalid LSA type"); 1121 } 1122 1123 return (0); 1124} 1125