1 /* $OpenBSD: rde_lsdb.c,v 1.48 2023/03/08 04:43:14 guenther 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 void 807 lsa_timeout(int fd, short event, void *bula) 808 { 809 struct vertex *v = bula; 810 struct timeval tv; 811 812 lsa_age(v); 813 814 if (v->deleted) { 815 if (ntohs(v->lsa->hdr.age) >= MAX_AGE) { 816 vertex_free(v); 817 } else { 818 v->deleted = 0; 819 820 /* schedule recalculation of the RIB */ 821 if (ntohs(v->lsa->hdr.type) == LSA_TYPE_LINK) 822 orig_intra_area_prefix_lsas(v->area); 823 if (ntohs(v->lsa->hdr.type) != LSA_TYPE_EXTERNAL) 824 v->area->dirty = 1; 825 start_spf_timer(); 826 827 rde_imsg_compose_ospfe(IMSG_LS_FLOOD, v->peerid, 0, 828 v->lsa, ntohs(v->lsa->hdr.len)); 829 830 /* timeout handling either MAX_AGE or LS_REFRESH_TIME */ 831 timerclear(&tv); 832 if (v->self) 833 tv.tv_sec = LS_REFRESH_TIME; 834 else 835 tv.tv_sec = MAX_AGE - ntohs(v->lsa->hdr.age); 836 837 if (evtimer_add(&v->ev, &tv) != 0) 838 fatal("lsa_timeout"); 839 } 840 return; 841 } 842 843 if (v->self && ntohs(v->lsa->hdr.age) < MAX_AGE) 844 lsa_refresh(v); 845 846 rde_imsg_compose_ospfe(IMSG_LS_FLOOD, v->peerid, 0, 847 v->lsa, ntohs(v->lsa->hdr.len)); 848 } 849 850 void 851 lsa_refresh(struct vertex *v) 852 { 853 struct timeval tv; 854 struct timespec tp; 855 u_int32_t seqnum; 856 u_int16_t len; 857 858 /* refresh LSA by increasing sequence number by one */ 859 if (v->self && ntohs(v->lsa->hdr.age) >= MAX_AGE) 860 /* self originated network that is currently beeing removed */ 861 v->lsa->hdr.age = htons(MAX_AGE); 862 else 863 v->lsa->hdr.age = htons(DEFAULT_AGE); 864 seqnum = ntohl(v->lsa->hdr.seq_num); 865 if (seqnum++ == MAX_SEQ_NUM) 866 /* XXX fix me */ 867 fatalx("sequence number wrapping"); 868 v->lsa->hdr.seq_num = htonl(seqnum); 869 870 /* recalculate checksum */ 871 len = ntohs(v->lsa->hdr.len); 872 v->lsa->hdr.ls_chksum = 0; 873 v->lsa->hdr.ls_chksum = htons(iso_cksum(v->lsa, len, LS_CKSUM_OFFSET)); 874 875 clock_gettime(CLOCK_MONOTONIC, &tp); 876 v->changed = v->stamp = tp.tv_sec; 877 878 timerclear(&tv); 879 tv.tv_sec = LS_REFRESH_TIME; 880 if (evtimer_add(&v->ev, &tv) == -1) 881 fatal("lsa_refresh"); 882 } 883 884 void 885 lsa_merge(struct rde_nbr *nbr, struct lsa *lsa, struct vertex *v) 886 { 887 struct timeval tv; 888 struct timespec tp; 889 time_t now; 890 u_int16_t len; 891 892 if (v == NULL) { 893 if (lsa_add(nbr, lsa)) 894 /* delayed update */ 895 return; 896 rde_imsg_compose_ospfe(IMSG_LS_FLOOD, nbr->peerid, 0, 897 lsa, ntohs(lsa->hdr.len)); 898 return; 899 } 900 901 /* set the seq_num to the current one. lsa_refresh() will do the ++ */ 902 lsa->hdr.seq_num = v->lsa->hdr.seq_num; 903 /* recalculate checksum */ 904 len = ntohs(lsa->hdr.len); 905 lsa->hdr.ls_chksum = 0; 906 lsa->hdr.ls_chksum = htons(iso_cksum(lsa, len, LS_CKSUM_OFFSET)); 907 908 /* compare LSA most header fields are equal so don't check them */ 909 if (lsa_equal(lsa, v->lsa)) { 910 free(lsa); 911 return; 912 } 913 914 /* overwrite the lsa all other fields are unaffected */ 915 free(v->lsa); 916 v->lsa = lsa; 917 if (v->type == LSA_TYPE_LINK) 918 orig_intra_area_prefix_lsas(nbr->area); 919 if (v->type != LSA_TYPE_EXTERNAL) 920 nbr->area->dirty = 1; 921 start_spf_timer(); 922 923 /* set correct timeout for reflooding the LSA */ 924 clock_gettime(CLOCK_MONOTONIC, &tp); 925 now = tp.tv_sec; 926 timerclear(&tv); 927 if (v->changed + MIN_LS_INTERVAL >= now) 928 tv.tv_sec = MIN_LS_INTERVAL; 929 if (evtimer_add(&v->ev, &tv) == -1) 930 fatal("lsa_merge"); 931 } 932 933 void 934 lsa_remove_invalid_sums(struct area *area) 935 { 936 struct lsa_tree *tree = &area->lsa_tree; 937 struct vertex *v, *nv; 938 939 /* XXX speed me up */ 940 for (v = RB_MIN(lsa_tree, tree); v != NULL; v = nv) { 941 nv = RB_NEXT(lsa_tree, tree, v); 942 if ((v->type == LSA_TYPE_INTER_A_PREFIX || 943 v->type == LSA_TYPE_INTER_A_ROUTER) && 944 v->self && v->cost == LS_INFINITY && 945 v->deleted == 0) { 946 /* 947 * age the lsa and call lsa_timeout() which will 948 * actually remove it from the database. 949 */ 950 v->lsa->hdr.age = htons(MAX_AGE); 951 lsa_timeout(0, 0, v); 952 } 953 } 954 } 955 956 int 957 lsa_equal(struct lsa *a, struct lsa *b) 958 { 959 /* 960 * compare LSA that already have same type, adv_rtr and ls_id 961 * so not all header need to be compared 962 */ 963 if (a == NULL || b == NULL) 964 return (0); 965 if (a->hdr.len != b->hdr.len) 966 return (0); 967 /* LSAs with age MAX_AGE are never equal */ 968 if (a->hdr.age == htons(MAX_AGE) || b->hdr.age == htons(MAX_AGE)) 969 return (0); 970 if (memcmp(&a->data, &b->data, ntohs(a->hdr.len) - 971 sizeof(struct lsa_hdr))) 972 return (0); 973 974 return (1); 975 } 976 977 int 978 lsa_get_prefix(void *buf, u_int16_t len, struct rt_prefix *p) 979 { 980 struct lsa_prefix *lp = buf; 981 u_int32_t *buf32, *addr = NULL; 982 u_int8_t prefixlen; 983 u_int16_t consumed; 984 985 if (len < sizeof(*lp)) 986 return (-1); 987 988 prefixlen = lp->prefixlen; 989 990 if (p) { 991 bzero(p, sizeof(*p)); 992 p->prefixlen = lp->prefixlen; 993 p->options = lp->options; 994 p->metric = ntohs(lp->metric); 995 addr = (u_int32_t *)&p->prefix; 996 } 997 998 buf32 = (u_int32_t *)(lp + 1); 999 consumed = sizeof(*lp); 1000 1001 for (prefixlen = LSA_PREFIXSIZE(prefixlen) / sizeof(u_int32_t); 1002 prefixlen > 0; prefixlen--) { 1003 if (len < consumed + sizeof(u_int32_t)) 1004 return (-1); 1005 if (addr) 1006 *addr++ = *buf32++; 1007 consumed += sizeof(u_int32_t); 1008 } 1009 1010 return (consumed); 1011 } 1012