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