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