1 /* $OpenBSD: rde_lsdb.c,v 1.47 2020/10/04 07:24:46 denis Exp $ */ 2 3 /* 4 * Copyright (c) 2004, 2005 Claudio Jeker <claudio@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/tree.h> 21 #include <stdlib.h> 22 #include <string.h> 23 #include <unistd.h> 24 25 #include "ospf6.h" 26 #include "ospf6d.h" 27 #include "rde.h" 28 #include "log.h" 29 30 struct vertex *vertex_get(struct lsa *, struct rde_nbr *, struct lsa_tree *); 31 32 int lsa_link_check(struct lsa *, u_int16_t); 33 int lsa_intra_a_pref_check(struct lsa *, u_int16_t); 34 int lsa_asext_check(struct lsa *, u_int16_t); 35 void lsa_timeout(int, short, void *); 36 void lsa_refresh(struct vertex *); 37 int lsa_equal(struct lsa *, struct lsa *); 38 int lsa_get_prefix(void *, u_int16_t, struct rt_prefix *); 39 40 RB_GENERATE(lsa_tree, vertex, entry, lsa_compare) 41 42 void 43 lsa_init(struct lsa_tree *t) 44 { 45 RB_INIT(t); 46 } 47 48 int 49 lsa_compare(struct vertex *a, struct vertex *b) 50 { 51 if (a->type < b->type) 52 return (-1); 53 if (a->type > b->type) 54 return (1); 55 if (a->adv_rtr < b->adv_rtr) 56 return (-1); 57 if (a->adv_rtr > b->adv_rtr) 58 return (1); 59 if (a->ls_id < b->ls_id) 60 return (-1); 61 if (a->ls_id > b->ls_id) 62 return (1); 63 return (0); 64 } 65 66 67 struct vertex * 68 vertex_get(struct lsa *lsa, struct rde_nbr *nbr, struct lsa_tree *tree) 69 { 70 struct vertex *v; 71 struct timespec tp; 72 73 if ((v = calloc(1, sizeof(struct vertex))) == NULL) 74 fatal(NULL); 75 TAILQ_INIT(&v->nexthop); 76 v->area = nbr->area; 77 v->peerid = nbr->peerid; 78 v->lsa = lsa; 79 clock_gettime(CLOCK_MONOTONIC, &tp); 80 v->changed = v->stamp = tp.tv_sec; 81 v->cost = LS_INFINITY; 82 v->ls_id = ntohl(lsa->hdr.ls_id); 83 v->adv_rtr = ntohl(lsa->hdr.adv_rtr); 84 v->type = ntohs(lsa->hdr.type); 85 v->lsa_tree = tree; 86 87 if (!nbr->self) 88 v->flooded = 1; /* XXX fix me */ 89 v->self = nbr->self; 90 91 evtimer_set(&v->ev, lsa_timeout, v); 92 93 return (v); 94 } 95 96 void 97 vertex_free(struct vertex *v) 98 { 99 RB_REMOVE(lsa_tree, v->lsa_tree, v); 100 101 (void)evtimer_del(&v->ev); 102 vertex_nexthop_clear(v); 103 free(v->lsa); 104 free(v); 105 } 106 107 void 108 vertex_nexthop_clear(struct vertex *v) 109 { 110 struct v_nexthop *vn; 111 112 while ((vn = TAILQ_FIRST(&v->nexthop))) { 113 TAILQ_REMOVE(&v->nexthop, vn, entry); 114 free(vn); 115 } 116 } 117 118 void 119 vertex_nexthop_add(struct vertex *dst, struct vertex *parent, 120 const struct in6_addr *nexthop, u_int32_t ifindex) 121 { 122 struct v_nexthop *vn; 123 124 if ((vn = calloc(1, sizeof(*vn))) == NULL) 125 fatal("vertex_nexthop_add"); 126 127 vn->prev = parent; 128 if (nexthop) 129 vn->nexthop = *nexthop; 130 vn->ifindex = ifindex; 131 132 TAILQ_INSERT_TAIL(&dst->nexthop, vn, entry); 133 } 134 135 /* returns -1 if a is older, 1 if newer and 0 if equal to b */ 136 int 137 lsa_newer(struct lsa_hdr *a, struct lsa_hdr *b) 138 { 139 int32_t a32, b32; 140 u_int16_t a16, b16; 141 int i; 142 143 if (a == NULL) 144 return (-1); 145 if (b == NULL) 146 return (1); 147 148 /* 149 * The sequence number is defined as signed 32-bit integer, 150 * no idea how IETF came up with such a stupid idea. 151 */ 152 a32 = (int32_t)ntohl(a->seq_num); 153 b32 = (int32_t)ntohl(b->seq_num); 154 155 if (a32 > b32) 156 return (1); 157 if (a32 < b32) 158 return (-1); 159 160 a16 = ntohs(a->ls_chksum); 161 b16 = ntohs(b->ls_chksum); 162 163 if (a16 > b16) 164 return (1); 165 if (a16 < b16) 166 return (-1); 167 168 a16 = ntohs(a->age); 169 b16 = ntohs(b->age); 170 171 if (a16 >= MAX_AGE && b16 >= MAX_AGE) 172 return (0); 173 if (b16 >= MAX_AGE) 174 return (-1); 175 if (a16 >= MAX_AGE) 176 return (1); 177 178 i = b16 - a16; 179 if (abs(i) > MAX_AGE_DIFF) 180 return (i > 0 ? 1 : -1); 181 182 return (0); 183 } 184 185 int 186 lsa_check(struct rde_nbr *nbr, struct lsa *lsa, u_int16_t len) 187 { 188 u_int32_t metric; 189 190 if (len < sizeof(lsa->hdr)) { 191 log_warnx("lsa_check: bad packet size"); 192 return (0); 193 } 194 if (ntohs(lsa->hdr.len) != len) { 195 log_warnx("lsa_check: bad packet length"); 196 return (0); 197 } 198 199 if (iso_cksum(lsa, len, 0)) { 200 log_warnx("lsa_check: bad packet checksum"); 201 return (0); 202 } 203 204 /* invalid ages */ 205 if ((ntohs(lsa->hdr.age) < 1 && !nbr->self) || 206 ntohs(lsa->hdr.age) > MAX_AGE) { 207 log_warnx("lsa_check: bad age"); 208 return (0); 209 } 210 211 /* invalid sequence number */ 212 if (ntohl(lsa->hdr.seq_num) == RESV_SEQ_NUM) { 213 log_warnx("lsa_check: bad seq num"); 214 return (0); 215 } 216 217 switch (ntohs(lsa->hdr.type)) { 218 case LSA_TYPE_LINK: 219 if (!lsa_link_check(lsa, len)) 220 return (0); 221 break; 222 case LSA_TYPE_ROUTER: 223 if (len < sizeof(lsa->hdr) + sizeof(struct lsa_rtr)) { 224 log_warnx("lsa_check: bad LSA rtr packet"); 225 return (0); 226 } 227 len -= sizeof(lsa->hdr) + sizeof(struct lsa_rtr); 228 if (len % sizeof(struct lsa_rtr_link)) { 229 log_warnx("lsa_check: bad LSA rtr packet"); 230 return (0); 231 } 232 break; 233 case LSA_TYPE_NETWORK: 234 if ((len % sizeof(u_int32_t)) || 235 len < sizeof(lsa->hdr) + sizeof(u_int32_t)) { 236 log_warnx("lsa_check: bad LSA network packet"); 237 return (0); 238 } 239 break; 240 case LSA_TYPE_INTER_A_PREFIX: 241 if (len < sizeof(lsa->hdr) + sizeof(lsa->data.pref_sum)) { 242 log_warnx("lsa_check: bad LSA prefix summary packet"); 243 return (0); 244 } 245 metric = ntohl(lsa->data.pref_sum.metric); 246 if (metric & ~LSA_METRIC_MASK) { 247 log_warnx("lsa_check: bad LSA prefix summary metric"); 248 return (0); 249 } 250 if (lsa_get_prefix(((char *)lsa) + sizeof(lsa->hdr) + 251 sizeof(lsa->data.pref_sum), 252 len - sizeof(lsa->hdr) + sizeof(lsa->data.pref_sum), 253 NULL) == -1) { 254 log_warnx("lsa_check: " 255 "invalid LSA prefix summary packet"); 256 return (0); 257 } 258 break; 259 case LSA_TYPE_INTER_A_ROUTER: 260 if (len < sizeof(lsa->hdr) + sizeof(lsa->data.rtr_sum)) { 261 log_warnx("lsa_check: bad LSA router summary packet"); 262 return (0); 263 } 264 metric = ntohl(lsa->data.rtr_sum.metric); 265 if (metric & ~LSA_METRIC_MASK) { 266 log_warnx("lsa_check: bad LSA router summary metric"); 267 return (0); 268 } 269 break; 270 case LSA_TYPE_INTRA_A_PREFIX: 271 if (!lsa_intra_a_pref_check(lsa, len)) 272 return (0); 273 break; 274 case LSA_TYPE_EXTERNAL: 275 /* AS-external-LSA are silently discarded in stub areas */ 276 if (nbr->area->stub) 277 return (0); 278 if (!lsa_asext_check(lsa, len)) 279 return (0); 280 break; 281 default: 282 log_warnx("lsa_check: unknown type %x", ntohs(lsa->hdr.type)); 283 return (0); 284 } 285 286 /* MaxAge handling */ 287 if (lsa->hdr.age == htons(MAX_AGE) && !nbr->self && lsa_find(nbr->iface, 288 lsa->hdr.type, lsa->hdr.ls_id, lsa->hdr.adv_rtr) == NULL && 289 !rde_nbr_loading(nbr->area)) { 290 /* 291 * if no neighbor in state Exchange or Loading 292 * ack LSA but don't add it. Needs to be a direct ack. 293 */ 294 rde_imsg_compose_ospfe(IMSG_LS_ACK, nbr->peerid, 0, &lsa->hdr, 295 sizeof(struct lsa_hdr)); 296 return (0); 297 } 298 299 return (1); 300 } 301 302 int 303 lsa_link_check(struct lsa *lsa, u_int16_t len) 304 { 305 char *buf = (char *)lsa; 306 struct lsa_link *llink; 307 u_int32_t i, off, npref; 308 int rv; 309 310 llink = (struct lsa_link *)(buf + sizeof(lsa->hdr)); 311 off = sizeof(lsa->hdr) + sizeof(struct lsa_link); 312 if (off > len) { 313 log_warnx("lsa_link_check: invalid LSA link packet, " 314 "short header"); 315 return (0); 316 } 317 318 len -= off; 319 npref = ntohl(llink->numprefix); 320 321 for (i = 0; i < npref; i++) { 322 rv = lsa_get_prefix(buf + off, len, NULL); 323 if (rv == -1) { 324 log_warnx("lsa_link_check: invalid LSA link packet"); 325 return (0); 326 } 327 off += rv; 328 len -= rv; 329 } 330 331 return (1); 332 } 333 334 int 335 lsa_intra_a_pref_check(struct lsa *lsa, u_int16_t len) 336 { 337 char *buf = (char *)lsa; 338 struct lsa_intra_prefix *iap; 339 u_int32_t i, off, npref; 340 int rv; 341 342 iap = (struct lsa_intra_prefix *)(buf + sizeof(lsa->hdr)); 343 off = sizeof(lsa->hdr) + sizeof(struct lsa_intra_prefix); 344 if (off > len) { 345 log_warnx("lsa_intra_a_pref_check: " 346 "invalid LSA intra area prefix packet, short header"); 347 return (0); 348 } 349 350 len -= off; 351 npref = ntohs(iap->numprefix); 352 353 for (i = 0; i < npref; i++) { 354 rv = lsa_get_prefix(buf + off, len, NULL); 355 if (rv == -1) { 356 log_warnx("lsa_intra_a_pref_check: " 357 "invalid LSA intra area prefix packet"); 358 return (0); 359 } 360 off += rv; 361 len -= rv; 362 } 363 364 return (1); 365 } 366 367 int 368 lsa_asext_check(struct lsa *lsa, u_int16_t len) 369 { 370 char *buf = (char *)lsa; 371 struct lsa_asext *asext; 372 struct in6_addr fw_addr; 373 u_int32_t metric; 374 u_int16_t ref_ls_type; 375 int rv; 376 u_int16_t total_len; 377 378 asext = (struct lsa_asext *)(buf + sizeof(lsa->hdr)); 379 380 if ((len % sizeof(u_int32_t)) || 381 len < sizeof(lsa->hdr) + sizeof(*asext)) { 382 log_warnx("lsa_asext_check: bad LSA as-external packet size"); 383 return (0); 384 } 385 386 total_len = sizeof(lsa->hdr) + sizeof(*asext); 387 rv = lsa_get_prefix(&asext->prefix, len, NULL); 388 if (rv == -1) { 389 log_warnx("lsa_asext_check: bad LSA as-external packet"); 390 return (0); 391 } 392 total_len += rv - sizeof(struct lsa_prefix); 393 394 metric = ntohl(asext->metric); 395 if (metric & LSA_ASEXT_F_FLAG) { 396 if (total_len + sizeof(fw_addr) < len) { 397 bcopy(buf + total_len, &fw_addr, sizeof(fw_addr)); 398 if (IN6_IS_ADDR_UNSPECIFIED(&fw_addr) || 399 IN6_IS_ADDR_LINKLOCAL(&fw_addr)) { 400 log_warnx("lsa_asext_check: bad LSA " 401 "as-external forwarding address"); 402 return (0); 403 } 404 } 405 total_len += sizeof(fw_addr); 406 } 407 408 if (metric & LSA_ASEXT_T_FLAG) 409 total_len += sizeof(u_int32_t); 410 411 ref_ls_type = asext->prefix.metric; 412 if (ref_ls_type != 0) 413 total_len += sizeof(u_int32_t); 414 415 if (len != total_len) { 416 log_warnx("lsa_asext_check: bad LSA as-external length"); 417 return (0); 418 } 419 420 return (1); 421 } 422 423 int 424 lsa_self(struct rde_nbr *nbr, struct lsa *lsa, struct vertex *v) 425 { 426 struct lsa *dummy; 427 428 if (nbr->self) 429 return (0); 430 431 if (rde_router_id() != lsa->hdr.adv_rtr) 432 return (0); 433 434 if (v == NULL) { 435 /* LSA is no longer announced, remove by premature aging. 436 * The LSA may not be altered because the caller may still 437 * use it, so a copy needs to be added to the LSDB. 438 * The copy will be reflooded via the default timeout handler. 439 */ 440 if ((dummy = malloc(ntohs(lsa->hdr.len))) == NULL) 441 fatal("lsa_self"); 442 memcpy(dummy, lsa, ntohs(lsa->hdr.len)); 443 dummy->hdr.age = htons(MAX_AGE); 444 /* 445 * The clue is that by using the remote nbr as originator 446 * the dummy LSA will be reflooded via the default timeout 447 * handler. 448 */ 449 (void)lsa_add(rde_nbr_self(nbr->area), dummy); 450 return (1); 451 } 452 453 /* 454 * LSA is still originated, just reflood it. But we need to create 455 * a new instance by setting the LSA sequence number equal to the 456 * one of new and calling lsa_refresh(). Flooding will be done by the 457 * caller. 458 */ 459 v->lsa->hdr.seq_num = lsa->hdr.seq_num; 460 lsa_refresh(v); 461 return (1); 462 } 463 464 int 465 lsa_add(struct rde_nbr *nbr, struct lsa *lsa) 466 { 467 struct lsa_tree *tree; 468 struct vertex *new, *old; 469 struct timeval tv, now, res; 470 int update = 1; 471 472 if (LSA_IS_SCOPE_AS(ntohs(lsa->hdr.type))) 473 tree = &asext_tree; 474 else if (LSA_IS_SCOPE_AREA(ntohs(lsa->hdr.type))) 475 tree = &nbr->area->lsa_tree; 476 else if (LSA_IS_SCOPE_LLOCAL(ntohs(lsa->hdr.type))) 477 tree = &nbr->iface->lsa_tree; 478 else 479 fatalx("%s: unknown scope type", __func__); 480 481 new = vertex_get(lsa, nbr, tree); 482 old = RB_INSERT(lsa_tree, tree, new); 483 484 if (old != NULL) { 485 if (old->deleted && evtimer_pending(&old->ev, &tv)) { 486 /* new update added before hold time expired */ 487 gettimeofday(&now, NULL); 488 timersub(&tv, &now, &res); 489 490 /* remove old LSA and insert new LSA with delay */ 491 vertex_free(old); 492 RB_INSERT(lsa_tree, tree, new); 493 new->deleted = 1; 494 495 if (evtimer_add(&new->ev, &res) != 0) 496 fatal("lsa_add"); 497 return (1); 498 } 499 if (lsa_equal(new->lsa, old->lsa)) 500 update = 0; 501 vertex_free(old); 502 RB_INSERT(lsa_tree, tree, new); 503 } 504 505 if (update) { 506 if (ntohs(lsa->hdr.type) == LSA_TYPE_LINK) 507 orig_intra_area_prefix_lsas(nbr->area); 508 if (ntohs(lsa->hdr.type) != LSA_TYPE_EXTERNAL) 509 nbr->area->dirty = 1; 510 start_spf_timer(); 511 } 512 513 /* timeout handling either MAX_AGE or LS_REFRESH_TIME */ 514 timerclear(&tv); 515 516 if (nbr->self && ntohs(new->lsa->hdr.age) == DEFAULT_AGE) 517 tv.tv_sec = LS_REFRESH_TIME; 518 else 519 tv.tv_sec = MAX_AGE - ntohs(new->lsa->hdr.age); 520 521 if (evtimer_add(&new->ev, &tv) != 0) 522 fatal("lsa_add: evtimer_add()"); 523 return (0); 524 } 525 526 void 527 lsa_del(struct rde_nbr *nbr, struct lsa_hdr *lsa) 528 { 529 struct vertex *v; 530 struct timeval tv; 531 532 v = lsa_find(nbr->iface, lsa->type, lsa->ls_id, lsa->adv_rtr); 533 if (v == NULL) 534 return; 535 536 v->deleted = 1; 537 /* hold time to make sure that a new lsa is not added premature */ 538 timerclear(&tv); 539 tv.tv_sec = MIN_LS_INTERVAL; 540 if (evtimer_add(&v->ev, &tv) == -1) 541 fatal("lsa_del"); 542 } 543 544 void 545 lsa_age(struct vertex *v) 546 { 547 struct timespec tp; 548 time_t now; 549 int d; 550 u_int16_t age; 551 552 clock_gettime(CLOCK_MONOTONIC, &tp); 553 now = tp.tv_sec; 554 555 d = now - v->stamp; 556 /* set stamp so that at least new calls work */ 557 v->stamp = now; 558 559 if (d < 0) { 560 log_warnx("lsa_age: time went backwards"); 561 return; 562 } 563 564 age = ntohs(v->lsa->hdr.age); 565 if (age + d > MAX_AGE) 566 age = MAX_AGE; 567 else 568 age += d; 569 570 v->lsa->hdr.age = htons(age); 571 } 572 573 struct vertex * 574 lsa_find(struct iface *iface, u_int16_t type, u_int32_t ls_id, 575 u_int32_t adv_rtr) 576 { 577 struct lsa_tree *tree; 578 579 if (LSA_IS_SCOPE_AS(ntohs(type))) 580 tree = &asext_tree; 581 else if (LSA_IS_SCOPE_AREA(ntohs(type))) 582 tree = &iface->area->lsa_tree; 583 else if (LSA_IS_SCOPE_LLOCAL(ntohs(type))) 584 tree = &iface->lsa_tree; 585 else 586 fatalx("unknown scope type"); 587 588 return lsa_find_tree(tree, type, ls_id, adv_rtr); 589 590 } 591 592 struct vertex * 593 lsa_find_tree(struct lsa_tree *tree, u_int16_t type, u_int32_t ls_id, 594 u_int32_t adv_rtr) 595 { 596 struct vertex key; 597 struct vertex *v; 598 599 key.ls_id = ntohl(ls_id); 600 key.adv_rtr = ntohl(adv_rtr); 601 key.type = ntohs(type); 602 603 v = RB_FIND(lsa_tree, tree, &key); 604 605 /* LSA that are deleted are not findable */ 606 if (v && v->deleted) 607 return (NULL); 608 609 if (v) 610 lsa_age(v); 611 612 return (v); 613 } 614 615 struct vertex * 616 lsa_find_rtr(struct area *area, u_int32_t rtr_id) 617 { 618 return lsa_find_rtr_frag(area, rtr_id, 0); 619 } 620 621 struct vertex * 622 lsa_find_rtr_frag(struct area *area, u_int32_t rtr_id, unsigned int n) 623 { 624 struct vertex *v; 625 struct vertex key; 626 unsigned int i; 627 628 key.ls_id = 0; 629 key.adv_rtr = ntohl(rtr_id); 630 key.type = LSA_TYPE_ROUTER; 631 632 i = 0; 633 v = RB_NFIND(lsa_tree, &area->lsa_tree, &key); 634 while (v) { 635 if (v->type != LSA_TYPE_ROUTER || 636 v->adv_rtr != ntohl(rtr_id)) { 637 /* no more interesting LSAs */ 638 v = NULL; 639 break; 640 } 641 if (!v->deleted) { 642 if (i >= n) 643 break; 644 i++; 645 } 646 v = RB_NEXT(lsa_tree, &area->lsa_tree, v); 647 } 648 649 if (v) { 650 if (i == n) 651 lsa_age(v); 652 else 653 v = NULL; 654 } 655 656 return (v); 657 } 658 659 u_int32_t 660 lsa_find_lsid(struct lsa_tree *tree, int (*cmp)(struct lsa *, struct lsa *), 661 struct lsa *lsa) 662 { 663 #define MIN(x, y) ((x) < (y) ? (x) : (y)) 664 struct vertex *v; 665 struct vertex key; 666 u_int32_t min, cur; 667 668 key.ls_id = 0; 669 key.adv_rtr = ntohl(lsa->hdr.adv_rtr); 670 key.type = ntohs(lsa->hdr.type); 671 672 cur = 0; 673 min = 0xffffffffU; 674 v = RB_NFIND(lsa_tree, tree, &key); 675 while (v) { 676 if (v->type != key.type || 677 v->adv_rtr != key.adv_rtr) { 678 /* no more interesting LSAs */ 679 min = MIN(min, cur + 1); 680 return (htonl(min)); 681 } 682 if (cmp(lsa, v->lsa) == 0) { 683 /* match, return this ls_id */ 684 return (htonl(v->ls_id)); 685 } 686 if (v->ls_id > cur + 1) 687 min = cur + 1; 688 cur = v->ls_id; 689 if (cur + 1 < cur) 690 fatalx("King Bula sez: somebody got to many LSA"); 691 v = RB_NEXT(lsa_tree, tree, v); 692 } 693 min = MIN(min, cur + 1); 694 return (htonl(min)); 695 #undef MIN 696 } 697 698 u_int16_t 699 lsa_num_links(struct vertex *v) 700 { 701 unsigned int n = 1; 702 u_int16_t nlinks = 0; 703 704 switch (v->type) { 705 case LSA_TYPE_ROUTER: 706 do { 707 nlinks += ((ntohs(v->lsa->hdr.len) - 708 sizeof(struct lsa_hdr) - sizeof(struct lsa_rtr)) / 709 sizeof(struct lsa_rtr_link)); 710 v = lsa_find_rtr_frag(v->area, htonl(v->adv_rtr), n++); 711 } while (v); 712 return nlinks; 713 case LSA_TYPE_NETWORK: 714 return ((ntohs(v->lsa->hdr.len) - sizeof(struct lsa_hdr) - 715 sizeof(struct lsa_net)) / sizeof(struct lsa_net_link)); 716 default: 717 fatalx("lsa_num_links: invalid LSA type"); 718 } 719 720 return (0); 721 } 722 723 void 724 lsa_snap(struct rde_nbr *nbr) 725 { 726 struct lsa_tree *tree = &nbr->area->lsa_tree; 727 struct vertex *v; 728 729 do { 730 RB_FOREACH(v, lsa_tree, tree) { 731 if (v->deleted) 732 continue; 733 lsa_age(v); 734 if (ntohs(v->lsa->hdr.age) >= MAX_AGE) { 735 rde_imsg_compose_ospfe(IMSG_LS_SNAP, 736 nbr->peerid, 0, &v->lsa->hdr, 737 ntohs(v->lsa->hdr.len)); 738 } else { 739 rde_imsg_compose_ospfe(IMSG_DB_SNAPSHOT, 740 nbr->peerid, 0, &v->lsa->hdr, 741 sizeof(struct lsa_hdr)); 742 } 743 } 744 if (tree == &asext_tree) 745 break; 746 if (tree == &nbr->area->lsa_tree) 747 tree = &nbr->iface->lsa_tree; 748 else 749 tree = &asext_tree; 750 } while (1); 751 } 752 753 void 754 lsa_dump(struct lsa_tree *tree, int imsg_type, pid_t pid) 755 { 756 struct vertex *v; 757 758 RB_FOREACH(v, lsa_tree, tree) { 759 if (v->deleted) 760 continue; 761 lsa_age(v); 762 switch (imsg_type) { 763 case IMSG_CTL_SHOW_DATABASE: 764 break; 765 case IMSG_CTL_SHOW_DB_SELF: 766 if (v->lsa->hdr.adv_rtr == rde_router_id()) 767 break; 768 continue; 769 case IMSG_CTL_SHOW_DB_EXT: 770 if (v->type == LSA_TYPE_EXTERNAL) 771 break; 772 continue; 773 case IMSG_CTL_SHOW_DB_LINK: 774 if (v->type == LSA_TYPE_LINK) 775 break; 776 continue; 777 case IMSG_CTL_SHOW_DB_NET: 778 if (v->type == LSA_TYPE_NETWORK) 779 break; 780 continue; 781 case IMSG_CTL_SHOW_DB_RTR: 782 if (v->type == LSA_TYPE_ROUTER) 783 break; 784 continue; 785 case IMSG_CTL_SHOW_DB_INTRA: 786 if (v->type == LSA_TYPE_INTRA_A_PREFIX) 787 break; 788 continue; 789 case IMSG_CTL_SHOW_DB_SUM: 790 if (v->type == LSA_TYPE_INTER_A_PREFIX) 791 break; 792 continue; 793 case IMSG_CTL_SHOW_DB_ASBR: 794 if (v->type == LSA_TYPE_INTER_A_ROUTER) 795 break; 796 continue; 797 default: 798 log_warnx("lsa_dump: unknown imsg type"); 799 return; 800 } 801 rde_imsg_compose_ospfe(imsg_type, 0, pid, &v->lsa->hdr, 802 ntohs(v->lsa->hdr.len)); 803 } 804 } 805 806 /* ARGSUSED */ 807 void 808 lsa_timeout(int fd, short event, void *bula) 809 { 810 struct vertex *v = bula; 811 struct timeval tv; 812 813 lsa_age(v); 814 815 if (v->deleted) { 816 if (ntohs(v->lsa->hdr.age) >= MAX_AGE) { 817 vertex_free(v); 818 } else { 819 v->deleted = 0; 820 821 /* schedule recalculation of the RIB */ 822 if (ntohs(v->lsa->hdr.type) == LSA_TYPE_LINK) 823 orig_intra_area_prefix_lsas(v->area); 824 if (ntohs(v->lsa->hdr.type) != LSA_TYPE_EXTERNAL) 825 v->area->dirty = 1; 826 start_spf_timer(); 827 828 rde_imsg_compose_ospfe(IMSG_LS_FLOOD, v->peerid, 0, 829 v->lsa, ntohs(v->lsa->hdr.len)); 830 831 /* timeout handling either MAX_AGE or LS_REFRESH_TIME */ 832 timerclear(&tv); 833 if (v->self) 834 tv.tv_sec = LS_REFRESH_TIME; 835 else 836 tv.tv_sec = MAX_AGE - ntohs(v->lsa->hdr.age); 837 838 if (evtimer_add(&v->ev, &tv) != 0) 839 fatal("lsa_timeout"); 840 } 841 return; 842 } 843 844 if (v->self && ntohs(v->lsa->hdr.age) < MAX_AGE) 845 lsa_refresh(v); 846 847 rde_imsg_compose_ospfe(IMSG_LS_FLOOD, v->peerid, 0, 848 v->lsa, ntohs(v->lsa->hdr.len)); 849 } 850 851 void 852 lsa_refresh(struct vertex *v) 853 { 854 struct timeval tv; 855 struct timespec tp; 856 u_int32_t seqnum; 857 u_int16_t len; 858 859 /* refresh LSA by increasing sequence number by one */ 860 if (v->self && ntohs(v->lsa->hdr.age) >= MAX_AGE) 861 /* self originated network that is currently beeing removed */ 862 v->lsa->hdr.age = htons(MAX_AGE); 863 else 864 v->lsa->hdr.age = htons(DEFAULT_AGE); 865 seqnum = ntohl(v->lsa->hdr.seq_num); 866 if (seqnum++ == MAX_SEQ_NUM) 867 /* XXX fix me */ 868 fatalx("sequence number wrapping"); 869 v->lsa->hdr.seq_num = htonl(seqnum); 870 871 /* recalculate checksum */ 872 len = ntohs(v->lsa->hdr.len); 873 v->lsa->hdr.ls_chksum = 0; 874 v->lsa->hdr.ls_chksum = htons(iso_cksum(v->lsa, len, LS_CKSUM_OFFSET)); 875 876 clock_gettime(CLOCK_MONOTONIC, &tp); 877 v->changed = v->stamp = tp.tv_sec; 878 879 timerclear(&tv); 880 tv.tv_sec = LS_REFRESH_TIME; 881 if (evtimer_add(&v->ev, &tv) == -1) 882 fatal("lsa_refresh"); 883 } 884 885 void 886 lsa_merge(struct rde_nbr *nbr, struct lsa *lsa, struct vertex *v) 887 { 888 struct timeval tv; 889 struct timespec tp; 890 time_t now; 891 u_int16_t len; 892 893 if (v == NULL) { 894 if (lsa_add(nbr, lsa)) 895 /* delayed update */ 896 return; 897 rde_imsg_compose_ospfe(IMSG_LS_FLOOD, nbr->peerid, 0, 898 lsa, ntohs(lsa->hdr.len)); 899 return; 900 } 901 902 /* set the seq_num to the current one. lsa_refresh() will do the ++ */ 903 lsa->hdr.seq_num = v->lsa->hdr.seq_num; 904 /* recalculate checksum */ 905 len = ntohs(lsa->hdr.len); 906 lsa->hdr.ls_chksum = 0; 907 lsa->hdr.ls_chksum = htons(iso_cksum(lsa, len, LS_CKSUM_OFFSET)); 908 909 /* compare LSA most header fields are equal so don't check them */ 910 if (lsa_equal(lsa, v->lsa)) { 911 free(lsa); 912 return; 913 } 914 915 /* overwrite the lsa all other fields are unaffected */ 916 free(v->lsa); 917 v->lsa = lsa; 918 if (v->type == LSA_TYPE_LINK) 919 orig_intra_area_prefix_lsas(nbr->area); 920 if (v->type != LSA_TYPE_EXTERNAL) 921 nbr->area->dirty = 1; 922 start_spf_timer(); 923 924 /* set correct timeout for reflooding the LSA */ 925 clock_gettime(CLOCK_MONOTONIC, &tp); 926 now = tp.tv_sec; 927 timerclear(&tv); 928 if (v->changed + MIN_LS_INTERVAL >= now) 929 tv.tv_sec = MIN_LS_INTERVAL; 930 if (evtimer_add(&v->ev, &tv) == -1) 931 fatal("lsa_merge"); 932 } 933 934 void 935 lsa_remove_invalid_sums(struct area *area) 936 { 937 struct lsa_tree *tree = &area->lsa_tree; 938 struct vertex *v, *nv; 939 940 /* XXX speed me up */ 941 for (v = RB_MIN(lsa_tree, tree); v != NULL; v = nv) { 942 nv = RB_NEXT(lsa_tree, tree, v); 943 if ((v->type == LSA_TYPE_INTER_A_PREFIX || 944 v->type == LSA_TYPE_INTER_A_ROUTER) && 945 v->self && v->cost == LS_INFINITY && 946 v->deleted == 0) { 947 /* 948 * age the lsa and call lsa_timeout() which will 949 * actually remove it from the database. 950 */ 951 v->lsa->hdr.age = htons(MAX_AGE); 952 lsa_timeout(0, 0, v); 953 } 954 } 955 } 956 957 int 958 lsa_equal(struct lsa *a, struct lsa *b) 959 { 960 /* 961 * compare LSA that already have same type, adv_rtr and ls_id 962 * so not all header need to be compared 963 */ 964 if (a == NULL || b == NULL) 965 return (0); 966 if (a->hdr.len != b->hdr.len) 967 return (0); 968 /* LSAs with age MAX_AGE are never equal */ 969 if (a->hdr.age == htons(MAX_AGE) || b->hdr.age == htons(MAX_AGE)) 970 return (0); 971 if (memcmp(&a->data, &b->data, ntohs(a->hdr.len) - 972 sizeof(struct lsa_hdr))) 973 return (0); 974 975 return (1); 976 } 977 978 int 979 lsa_get_prefix(void *buf, u_int16_t len, struct rt_prefix *p) 980 { 981 struct lsa_prefix *lp = buf; 982 u_int32_t *buf32, *addr = NULL; 983 u_int8_t prefixlen; 984 u_int16_t consumed; 985 986 if (len < sizeof(*lp)) 987 return (-1); 988 989 prefixlen = lp->prefixlen; 990 991 if (p) { 992 bzero(p, sizeof(*p)); 993 p->prefixlen = lp->prefixlen; 994 p->options = lp->options; 995 p->metric = ntohs(lp->metric); 996 addr = (u_int32_t *)&p->prefix; 997 } 998 999 buf32 = (u_int32_t *)(lp + 1); 1000 consumed = sizeof(*lp); 1001 1002 for (prefixlen = LSA_PREFIXSIZE(prefixlen) / sizeof(u_int32_t); 1003 prefixlen > 0; prefixlen--) { 1004 if (len < consumed + sizeof(u_int32_t)) 1005 return (-1); 1006 if (addr) 1007 *addr++ = *buf32++; 1008 consumed += sizeof(u_int32_t); 1009 } 1010 1011 return (consumed); 1012 } 1013