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