1 /* $OpenBSD: rde_spf.c,v 1.28 2020/04/05 18:19:04 denis 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 /* ARGSUSED */ 633 void 634 spf_timer(int fd, short event, void *arg) 635 { 636 struct vertex *v; 637 struct ospfd_conf *conf = arg; 638 struct area *area; 639 struct rt_node *r; 640 641 switch (conf->spf_state) { 642 case SPF_IDLE: 643 fatalx("spf_timer: invalid state IDLE"); 644 case SPF_HOLDQUEUE: 645 conf->spf_state = SPF_DELAY; 646 /* FALLTHROUGH */ 647 case SPF_DELAY: 648 LIST_FOREACH(area, &conf->area_list, entry) { 649 if (area->dirty) { 650 /* invalidate RIB entries of this area */ 651 rt_invalidate(area); 652 653 /* calculate SPF tree */ 654 spf_calc(area); 655 656 /* calculate route table */ 657 RB_FOREACH(v, lsa_tree, &area->lsa_tree) { 658 rt_calc(v, area, conf); 659 } 660 661 area->dirty = 0; 662 } 663 } 664 665 /* calculate as-external routes, first invalidate them */ 666 rt_invalidate(NULL); 667 RB_FOREACH(v, lsa_tree, &asext_tree) { 668 asext_calc(v); 669 } 670 671 RB_FOREACH(r, rt_tree, &rt) { 672 LIST_FOREACH(area, &conf->area_list, entry) 673 rde_summary_update(r, area); 674 675 if (r->d_type != DT_NET) 676 continue; 677 678 if (r->invalid) 679 rde_send_delete_kroute(r); 680 else 681 rde_send_change_kroute(r); 682 } 683 684 LIST_FOREACH(area, &conf->area_list, entry) 685 lsa_remove_invalid_sums(area); 686 687 start_spf_holdtimer(conf); 688 break; 689 case SPF_HOLD: 690 conf->spf_state = SPF_IDLE; 691 break; 692 default: 693 fatalx("spf_timer: unknown state"); 694 } 695 } 696 697 void 698 start_spf_timer(void) 699 { 700 struct timeval tv; 701 702 switch (rdeconf->spf_state) { 703 case SPF_IDLE: 704 timerclear(&tv); 705 tv.tv_sec = rdeconf->spf_delay; 706 rdeconf->spf_state = SPF_DELAY; 707 if (evtimer_add(&rdeconf->ev, &tv) == -1) 708 fatal("start_spf_timer"); 709 break; 710 case SPF_DELAY: 711 /* ignore */ 712 break; 713 case SPF_HOLD: 714 rdeconf->spf_state = SPF_HOLDQUEUE; 715 break; 716 case SPF_HOLDQUEUE: 717 /* ignore */ 718 break; 719 default: 720 fatalx("start_spf_timer: invalid spf_state"); 721 } 722 } 723 724 void 725 stop_spf_timer(struct ospfd_conf *conf) 726 { 727 if (evtimer_del(&conf->ev) == -1) 728 fatal("stop_spf_timer"); 729 } 730 731 void 732 start_spf_holdtimer(struct ospfd_conf *conf) 733 { 734 struct timeval tv; 735 736 switch (conf->spf_state) { 737 case SPF_DELAY: 738 timerclear(&tv); 739 tv.tv_sec = conf->spf_hold_time; 740 conf->spf_state = SPF_HOLD; 741 if (evtimer_add(&conf->ev, &tv) == -1) 742 fatal("start_spf_holdtimer"); 743 break; 744 case SPF_IDLE: 745 case SPF_HOLD: 746 case SPF_HOLDQUEUE: 747 fatalx("start_spf_holdtimer: invalid state"); 748 default: 749 fatalx("start_spf_holdtimer: unknown state"); 750 } 751 } 752 753 /* route table */ 754 void 755 rt_init(void) 756 { 757 RB_INIT(&rt); 758 } 759 760 int 761 rt_compare(struct rt_node *a, struct rt_node *b) 762 { 763 int i; 764 765 /* XXX maybe a & b need to be switched */ 766 i = memcmp(&a->prefix, &b->prefix, sizeof(a->prefix)); 767 if (i) 768 return (i); 769 if (a->prefixlen < b->prefixlen) 770 return (-1); 771 if (a->prefixlen > b->prefixlen) 772 return (1); 773 if (a->d_type > b->d_type) 774 return (-1); 775 if (a->d_type < b->d_type) 776 return (1); 777 return (0); 778 } 779 780 struct rt_node * 781 rt_find(struct in6_addr *prefix, u_int8_t prefixlen, enum dst_type d_type) 782 { 783 struct rt_node s; 784 785 s.prefix = *prefix; 786 s.prefixlen = prefixlen; 787 s.d_type = d_type; 788 789 return (RB_FIND(rt_tree, &rt, &s)); 790 } 791 792 int 793 rt_insert(struct rt_node *r) 794 { 795 if (RB_INSERT(rt_tree, &rt, r) != NULL) { 796 log_warnx("rt_insert failed for %s/%u", 797 log_in6addr(&r->prefix), r->prefixlen); 798 free(r); 799 return (-1); 800 } 801 802 return (0); 803 } 804 805 int 806 rt_remove(struct rt_node *r) 807 { 808 if (RB_REMOVE(rt_tree, &rt, r) == NULL) { 809 log_warnx("rt_remove failed for %s/%u", 810 log_in6addr(&r->prefix), r->prefixlen); 811 return (-1); 812 } 813 814 rt_nexthop_clear(r); 815 free(r); 816 return (0); 817 } 818 819 void 820 rt_invalidate(struct area *area) 821 { 822 struct rt_node *r, *nr; 823 struct rt_nexthop *rn, *nrn; 824 825 for (r = RB_MIN(rt_tree, &rt); r != NULL; r = nr) { 826 nr = RB_NEXT(rt_tree, &rt, r); 827 if (area == NULL) { 828 /* look only at as_ext routes */ 829 if (r->p_type != PT_TYPE1_EXT && 830 r->p_type != PT_TYPE2_EXT) 831 continue; 832 } else { 833 /* ignore all as_ext routes */ 834 if (r->p_type == PT_TYPE1_EXT || 835 r->p_type == PT_TYPE2_EXT) 836 continue; 837 838 /* look only at routes matching the area */ 839 if (r->area.s_addr != area->id.s_addr) 840 continue; 841 } 842 r->invalid = 1; 843 for (rn = TAILQ_FIRST(&r->nexthop); rn != NULL; rn = nrn) { 844 nrn = TAILQ_NEXT(rn, entry); 845 if (rn->invalid) { 846 TAILQ_REMOVE(&r->nexthop, rn, entry); 847 free(rn); 848 } else 849 rn->invalid = 1; 850 } 851 if (TAILQ_EMPTY(&r->nexthop)) 852 rt_remove(r); 853 } 854 } 855 856 void 857 rt_nexthop_clear(struct rt_node *r) 858 { 859 struct rt_nexthop *rn; 860 861 while ((rn = TAILQ_FIRST(&r->nexthop)) != NULL) { 862 TAILQ_REMOVE(&r->nexthop, rn, entry); 863 free(rn); 864 } 865 } 866 867 void 868 rt_nexthop_add(struct rt_node *r, struct v_nexthead *vnh, u_int16_t type, 869 struct in_addr adv_rtr) 870 { 871 struct v_nexthop *vn; 872 struct rt_nexthop *rn; 873 struct timespec now; 874 875 TAILQ_FOREACH(vn, vnh, entry) { 876 TAILQ_FOREACH(rn, &r->nexthop, entry) { 877 if (!IN6_ARE_ADDR_EQUAL(&rn->nexthop, &vn->nexthop)) 878 continue; 879 880 rn->adv_rtr.s_addr = adv_rtr.s_addr; 881 rn->connected = (type == LSA_TYPE_NETWORK && 882 vn->prev == spf_root) || 883 (IN6_IS_ADDR_UNSPECIFIED(&vn->nexthop)); 884 rn->invalid = 0; 885 886 r->invalid = 0; 887 break; 888 } 889 if (rn) 890 continue; 891 892 if ((rn = calloc(1, sizeof(struct rt_nexthop))) == NULL) 893 fatal("rt_nexthop_add"); 894 895 clock_gettime(CLOCK_MONOTONIC, &now); 896 rn->nexthop = vn->nexthop; 897 rn->ifindex = vn->ifindex; 898 rn->adv_rtr.s_addr = adv_rtr.s_addr; 899 rn->uptime = now.tv_sec; 900 rn->connected = (type == LSA_TYPE_NETWORK && 901 vn->prev == spf_root) || 902 (IN6_IS_ADDR_UNSPECIFIED(&vn->nexthop)); 903 rn->invalid = 0; 904 905 r->invalid = 0; 906 TAILQ_INSERT_TAIL(&r->nexthop, rn, entry); 907 } 908 } 909 910 void 911 rt_clear(void) 912 { 913 struct rt_node *r; 914 915 while ((r = RB_MIN(rt_tree, &rt)) != NULL) 916 rt_remove(r); 917 } 918 919 void 920 rt_dump(struct in_addr area, pid_t pid, u_int8_t r_type) 921 { 922 static struct ctl_rt rtctl; 923 struct timespec now; 924 struct rt_node *r; 925 struct rt_nexthop *rn; 926 927 clock_gettime(CLOCK_MONOTONIC, &now); 928 929 RB_FOREACH(r, rt_tree, &rt) { 930 if (r->invalid) 931 continue; 932 933 if (r->area.s_addr != area.s_addr) 934 continue; 935 936 switch (r_type) { 937 case RIB_RTR: 938 if (r->d_type != DT_RTR) 939 continue; 940 break; 941 case RIB_NET: 942 if (r->d_type != DT_NET) 943 continue; 944 if (r->p_type == PT_TYPE1_EXT || 945 r->p_type == PT_TYPE2_EXT) 946 continue; 947 break; 948 case RIB_EXT: 949 if (r->p_type != PT_TYPE1_EXT && 950 r->p_type != PT_TYPE2_EXT) 951 continue; 952 break; 953 default: 954 fatalx("rt_dump: invalid RIB type"); 955 } 956 957 memset(&rtctl, 0, sizeof(rtctl)); 958 rtctl.prefix = r->prefix; 959 rtctl.area.s_addr = r->area.s_addr; 960 rtctl.cost = r->cost; 961 rtctl.cost2 = r->cost2; 962 rtctl.p_type = r->p_type; 963 rtctl.d_type = r->d_type; 964 rtctl.flags = r->flags; 965 rtctl.prefixlen = r->prefixlen; 966 967 TAILQ_FOREACH(rn, &r->nexthop, entry) { 968 if (rn->invalid) 969 continue; 970 971 rtctl.connected = rn->connected; 972 rtctl.nexthop = rn->nexthop; 973 rtctl.ifindex = rn->ifindex; 974 rtctl.adv_rtr.s_addr = rn->adv_rtr.s_addr; 975 rtctl.uptime = now.tv_sec - rn->uptime; 976 977 rde_imsg_compose_ospfe(IMSG_CTL_SHOW_RIB, 0, pid, 978 &rtctl, sizeof(rtctl)); 979 } 980 } 981 } 982 983 void 984 rt_update(struct in6_addr *prefix, u_int8_t prefixlen, struct v_nexthead *vnh, 985 u_int16_t v_type, u_int32_t cost, u_int32_t cost2, struct in_addr area, 986 struct in_addr adv_rtr, enum path_type p_type, enum dst_type d_type, 987 u_int8_t flags, u_int32_t tag) 988 { 989 struct rt_node *rte; 990 struct rt_nexthop *rn; 991 int better = 0, equal = 0; 992 993 if (vnh == NULL || TAILQ_EMPTY(vnh)) /* XXX remove */ 994 fatalx("rt_update: invalid nexthop"); 995 996 if ((rte = rt_find(prefix, prefixlen, d_type)) == NULL) { 997 if ((rte = calloc(1, sizeof(struct rt_node))) == NULL) 998 fatal("rt_update"); 999 1000 TAILQ_INIT(&rte->nexthop); 1001 rte->prefix = *prefix; 1002 rte->prefixlen = prefixlen; 1003 rte->cost = cost; 1004 rte->cost2 = cost2; 1005 rte->area = area; 1006 rte->p_type = p_type; 1007 rte->d_type = d_type; 1008 rte->flags = flags; 1009 rte->ext_tag = tag; 1010 1011 rt_nexthop_add(rte, vnh, v_type, adv_rtr); 1012 1013 rt_insert(rte); 1014 } else { 1015 /* order: 1016 * 1. intra-area 1017 * 2. inter-area 1018 * 3. type 1 as ext 1019 * 4. type 2 as ext 1020 */ 1021 if (rte->invalid) /* everything is better than invalid */ 1022 better = 1; 1023 else if (p_type < rte->p_type) 1024 better = 1; 1025 else if (p_type == rte->p_type) 1026 switch (p_type) { 1027 case PT_INTRA_AREA: 1028 case PT_INTER_AREA: 1029 if (cost < rte->cost) 1030 better = 1; 1031 else if (cost == rte->cost && 1032 rte->area.s_addr == area.s_addr) 1033 equal = 1; 1034 break; 1035 case PT_TYPE1_EXT: 1036 if (cost < rte->cost) 1037 better = 1; 1038 else if (cost == rte->cost) 1039 equal = 1; 1040 break; 1041 case PT_TYPE2_EXT: 1042 if (cost2 < rte->cost2) 1043 better = 1; 1044 else if (cost2 == rte->cost2 && 1045 cost < rte->cost) 1046 better = 1; 1047 else if (cost2 == rte->cost2 && 1048 cost == rte->cost) 1049 equal = 1; 1050 break; 1051 } 1052 1053 if (better) { 1054 TAILQ_FOREACH(rn, &rte->nexthop, entry) 1055 rn->invalid = 1; 1056 1057 rte->area = area; 1058 rte->cost = cost; 1059 rte->cost2 = cost2; 1060 rte->p_type = p_type; 1061 rte->flags = flags; 1062 rte->ext_tag = tag; 1063 } 1064 1065 if (equal || better) 1066 rt_nexthop_add(rte, vnh, v_type, adv_rtr); 1067 } 1068 } 1069 1070 struct rt_node * 1071 rt_lookup(enum dst_type type, struct in6_addr *addr) 1072 { 1073 struct rt_node *rn; 1074 struct in6_addr ina; 1075 u_int8_t i = 128; 1076 1077 if (type == DT_RTR) { 1078 rn = rt_find(addr, 128, type); 1079 if (rn && rn->invalid == 0) 1080 return (rn); 1081 return (NULL); 1082 } 1083 1084 /* type == DT_NET */ 1085 do { 1086 inet6applymask(&ina, addr, i); 1087 if ((rn = rt_find(&ina, i, type)) && rn->invalid == 0) 1088 return (rn); 1089 } while (i-- != 0); 1090 1091 return (NULL); 1092 } 1093 1094 /* router LSA links */ 1095 struct lsa_rtr_link * 1096 get_rtr_link(struct vertex *v, unsigned int idx) 1097 { 1098 struct lsa_rtr_link *rtr_link = NULL; 1099 unsigned int frag = 1; 1100 unsigned int frag_nlinks; 1101 unsigned int nlinks = 0; 1102 unsigned int i; 1103 1104 if (v->type != LSA_TYPE_ROUTER) 1105 fatalx("get_rtr_link: invalid LSA type"); 1106 1107 /* Treat multiple Router-LSAs originated by the same router 1108 * as an aggregate. */ 1109 do { 1110 /* number of links validated earlier by lsa_check() */ 1111 rtr_link = (struct lsa_rtr_link *)((char *)v->lsa + 1112 sizeof(v->lsa->hdr) + sizeof(struct lsa_rtr)); 1113 frag_nlinks = ((ntohs(v->lsa->hdr.len) - 1114 sizeof(struct lsa_hdr) - sizeof(struct lsa_rtr)) / 1115 sizeof(struct lsa_rtr_link)); 1116 if (nlinks + frag_nlinks > idx) { 1117 for (i = 0; i < frag_nlinks; i++) { 1118 if (i + nlinks == idx) 1119 return (rtr_link); 1120 rtr_link++; 1121 } 1122 } 1123 nlinks += frag_nlinks; 1124 v = lsa_find_rtr_frag(v->area, htonl(v->adv_rtr), frag++); 1125 } while (v); 1126 1127 fatalx("get_rtr_link: index not found"); 1128 } 1129 1130 /* network LSA links */ 1131 struct lsa_net_link * 1132 get_net_link(struct vertex *v, unsigned int idx) 1133 { 1134 struct lsa_net_link *net_link = NULL; 1135 char *buf = (char *)v->lsa; 1136 unsigned int i, nlinks; 1137 1138 if (v->type != LSA_TYPE_NETWORK) 1139 fatalx("get_net_link: invalid LSA type"); 1140 1141 net_link = (struct lsa_net_link *)(buf + sizeof(v->lsa->hdr) + 1142 sizeof(struct lsa_net)); 1143 1144 /* number of links validated earlier by lsa_check() */ 1145 nlinks = lsa_num_links(v); 1146 for (i = 0; i < nlinks; i++) { 1147 if (i == idx) 1148 return (net_link); 1149 net_link++; 1150 } 1151 1152 fatalx("get_net_link: index not found"); 1153 } 1154 1155 /* misc */ 1156 int 1157 linked(struct vertex *w, struct vertex *v) 1158 { 1159 struct lsa_rtr_link *rtr_link = NULL; 1160 struct lsa_net_link *net_link = NULL; 1161 unsigned int i; 1162 1163 switch (w->type) { 1164 case LSA_TYPE_ROUTER: 1165 for (i = 0; i < lsa_num_links(w); i++) { 1166 rtr_link = get_rtr_link(w, i); 1167 switch (v->type) { 1168 case LSA_TYPE_ROUTER: 1169 if (rtr_link->type == LINK_TYPE_POINTTOPOINT && 1170 rtr_link->nbr_rtr_id == htonl(v->adv_rtr)) 1171 return (1); 1172 break; 1173 case LSA_TYPE_NETWORK: 1174 if (rtr_link->type == LINK_TYPE_TRANSIT_NET && 1175 rtr_link->nbr_rtr_id == htonl(v->adv_rtr) && 1176 rtr_link->nbr_iface_id == htonl(v->ls_id)) 1177 return (1); 1178 break; 1179 default: 1180 fatalx("linked: invalid type"); 1181 } 1182 } 1183 return (0); 1184 case LSA_TYPE_NETWORK: 1185 for (i = 0; i < lsa_num_links(w); i++) { 1186 net_link = get_net_link(w, i); 1187 switch (v->type) { 1188 case LSA_TYPE_ROUTER: 1189 if (net_link->att_rtr == htonl(v->adv_rtr)) 1190 return (1); 1191 break; 1192 default: 1193 fatalx("linked: invalid type"); 1194 } 1195 } 1196 return (0); 1197 default: 1198 fatalx("linked: invalid LSA type"); 1199 } 1200 1201 return (0); 1202 } 1203