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