1 /* $OpenBSD: rde_lsdb.c,v 1.43 2020/02/17 08:12:22 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 471 if (LSA_IS_SCOPE_AS(ntohs(lsa->hdr.type))) 472 tree = &asext_tree; 473 else if (LSA_IS_SCOPE_AREA(ntohs(lsa->hdr.type))) 474 tree = &nbr->area->lsa_tree; 475 else if (LSA_IS_SCOPE_LLOCAL(ntohs(lsa->hdr.type))) 476 tree = &nbr->iface->lsa_tree; 477 else 478 fatalx("%s: unknown scope type", __func__); 479 480 new = vertex_get(lsa, nbr, tree); 481 old = RB_INSERT(lsa_tree, tree, new); 482 483 if (old != NULL) { 484 if (old->deleted && evtimer_pending(&old->ev, &tv)) { 485 /* new update added before hold time expired */ 486 gettimeofday(&now, NULL); 487 timersub(&tv, &now, &res); 488 489 /* remove old LSA and insert new LSA with delay */ 490 vertex_free(old); 491 RB_INSERT(lsa_tree, tree, new); 492 new->deleted = 1; 493 494 if (evtimer_add(&new->ev, &res) != 0) 495 fatal("lsa_add"); 496 return (1); 497 } 498 if (!lsa_equal(new->lsa, old->lsa)) { 499 if (ntohs(lsa->hdr.type) == LSA_TYPE_LINK) 500 orig_intra_area_prefix_lsas(nbr->area); 501 if (ntohs(lsa->hdr.type) != LSA_TYPE_EXTERNAL) 502 nbr->area->dirty = 1; 503 start_spf_timer(); 504 } 505 vertex_free(old); 506 RB_INSERT(lsa_tree, tree, new); 507 } else { 508 if (ntohs(lsa->hdr.type) == LSA_TYPE_LINK) 509 orig_intra_area_prefix_lsas(nbr->area); 510 if (ntohs(lsa->hdr.type) != LSA_TYPE_EXTERNAL) 511 nbr->area->dirty = 1; 512 start_spf_timer(); 513 } 514 515 /* timeout handling either MAX_AGE or LS_REFRESH_TIME */ 516 timerclear(&tv); 517 518 if (nbr->self && ntohs(new->lsa->hdr.age) == DEFAULT_AGE) 519 tv.tv_sec = LS_REFRESH_TIME; 520 else 521 tv.tv_sec = MAX_AGE - ntohs(new->lsa->hdr.age); 522 523 if (evtimer_add(&new->ev, &tv) != 0) 524 fatal("lsa_add: evtimer_add()"); 525 return (0); 526 } 527 528 void 529 lsa_del(struct rde_nbr *nbr, struct lsa_hdr *lsa) 530 { 531 struct vertex *v; 532 struct timeval tv; 533 534 v = lsa_find(nbr->iface, lsa->type, lsa->ls_id, lsa->adv_rtr); 535 if (v == NULL) 536 return; 537 538 v->deleted = 1; 539 /* hold time to make sure that a new lsa is not added premature */ 540 timerclear(&tv); 541 tv.tv_sec = MIN_LS_INTERVAL; 542 if (evtimer_add(&v->ev, &tv) == -1) 543 fatal("lsa_del"); 544 } 545 546 void 547 lsa_age(struct vertex *v) 548 { 549 struct timespec tp; 550 time_t now; 551 int d; 552 u_int16_t age; 553 554 clock_gettime(CLOCK_MONOTONIC, &tp); 555 now = tp.tv_sec; 556 557 d = now - v->stamp; 558 /* set stamp so that at least new calls work */ 559 v->stamp = now; 560 561 if (d < 0) { 562 log_warnx("lsa_age: time went backwards"); 563 return; 564 } 565 566 age = ntohs(v->lsa->hdr.age); 567 if (age + d > MAX_AGE) 568 age = MAX_AGE; 569 else 570 age += d; 571 572 v->lsa->hdr.age = htons(age); 573 } 574 575 struct vertex * 576 lsa_find(struct iface *iface, u_int16_t type, u_int32_t ls_id, 577 u_int32_t adv_rtr) 578 { 579 struct lsa_tree *tree; 580 581 if (LSA_IS_SCOPE_AS(ntohs(type))) 582 tree = &asext_tree; 583 else if (LSA_IS_SCOPE_AREA(ntohs(type))) 584 tree = &iface->area->lsa_tree; 585 else if (LSA_IS_SCOPE_LLOCAL(ntohs(type))) 586 tree = &iface->lsa_tree; 587 else 588 fatalx("unknown scope type"); 589 590 return lsa_find_tree(tree, type, ls_id, adv_rtr); 591 592 } 593 594 struct vertex * 595 lsa_find_tree(struct lsa_tree *tree, u_int16_t type, u_int32_t ls_id, 596 u_int32_t adv_rtr) 597 { 598 struct vertex key; 599 struct vertex *v; 600 601 key.ls_id = ntohl(ls_id); 602 key.adv_rtr = ntohl(adv_rtr); 603 key.type = ntohs(type); 604 605 v = RB_FIND(lsa_tree, tree, &key); 606 607 /* LSA that are deleted are not findable */ 608 if (v && v->deleted) 609 return (NULL); 610 611 if (v) 612 lsa_age(v); 613 614 return (v); 615 } 616 617 struct vertex * 618 lsa_find_rtr(struct area *area, u_int32_t rtr_id) 619 { 620 return lsa_find_rtr_frag(area, rtr_id, 0); 621 } 622 623 struct vertex * 624 lsa_find_rtr_frag(struct area *area, u_int32_t rtr_id, unsigned int n) 625 { 626 struct vertex *v; 627 struct vertex key; 628 unsigned int i; 629 630 key.ls_id = 0; 631 key.adv_rtr = ntohl(rtr_id); 632 key.type = LSA_TYPE_ROUTER; 633 634 i = 0; 635 v = RB_NFIND(lsa_tree, &area->lsa_tree, &key); 636 while (v) { 637 if (v->type != LSA_TYPE_ROUTER || 638 v->adv_rtr != ntohl(rtr_id)) { 639 /* no more interesting LSAs */ 640 v = NULL; 641 break; 642 } 643 if (!v->deleted) { 644 if (i >= n) 645 break; 646 i++; 647 } 648 v = RB_NEXT(lsa_tree, &area->lsa_tree, v); 649 } 650 651 if (v) { 652 if (i == n) 653 lsa_age(v); 654 else 655 v = NULL; 656 } 657 658 return (v); 659 } 660 661 u_int32_t 662 lsa_find_lsid(struct lsa_tree *tree, int (*cmp)(struct lsa *, struct lsa *), 663 struct lsa *lsa) 664 { 665 #define MIN(x, y) ((x) < (y) ? (x) : (y)) 666 struct vertex *v; 667 struct vertex key; 668 u_int32_t min, cur; 669 670 key.ls_id = 0; 671 key.adv_rtr = ntohl(lsa->hdr.adv_rtr); 672 key.type = ntohs(lsa->hdr.type); 673 674 cur = 0; 675 min = 0xffffffffU; 676 v = RB_NFIND(lsa_tree, tree, &key); 677 while (v) { 678 if (v->type != key.type || 679 v->adv_rtr != key.adv_rtr) { 680 /* no more interesting LSAs */ 681 min = MIN(min, cur + 1); 682 return (htonl(min)); 683 } 684 if (cmp(lsa, v->lsa) == 0) { 685 /* match, return this ls_id */ 686 return (htonl(v->ls_id)); 687 } 688 if (v->ls_id > cur + 1) 689 min = cur + 1; 690 cur = v->ls_id; 691 if (cur + 1 < cur) 692 fatalx("King Bula sez: somebody got to many LSA"); 693 v = RB_NEXT(lsa_tree, tree, v); 694 } 695 min = MIN(min, cur + 1); 696 return (htonl(min)); 697 #undef MIN 698 } 699 700 u_int16_t 701 lsa_num_links(struct vertex *v) 702 { 703 unsigned int n = 1; 704 u_int16_t nlinks = 0; 705 706 switch (v->type) { 707 case LSA_TYPE_ROUTER: 708 do { 709 nlinks += ((ntohs(v->lsa->hdr.len) - 710 sizeof(struct lsa_hdr) - sizeof(struct lsa_rtr)) / 711 sizeof(struct lsa_rtr_link)); 712 v = lsa_find_rtr_frag(v->area, htonl(v->adv_rtr), n++); 713 } while (v); 714 return nlinks; 715 case LSA_TYPE_NETWORK: 716 return ((ntohs(v->lsa->hdr.len) - sizeof(struct lsa_hdr) - 717 sizeof(struct lsa_net)) / sizeof(struct lsa_net_link)); 718 default: 719 fatalx("lsa_num_links: invalid LSA type"); 720 } 721 722 return (0); 723 } 724 725 void 726 lsa_snap(struct rde_nbr *nbr) 727 { 728 struct lsa_tree *tree = &nbr->area->lsa_tree; 729 struct vertex *v; 730 731 do { 732 RB_FOREACH(v, lsa_tree, tree) { 733 if (v->deleted) 734 continue; 735 lsa_age(v); 736 if (ntohs(v->lsa->hdr.age) >= MAX_AGE) { 737 rde_imsg_compose_ospfe(IMSG_LS_SNAP, 738 nbr->peerid, 0, &v->lsa->hdr, 739 ntohs(v->lsa->hdr.len)); 740 } else { 741 rde_imsg_compose_ospfe(IMSG_DB_SNAPSHOT, 742 nbr->peerid, 0, &v->lsa->hdr, 743 sizeof(struct lsa_hdr)); 744 } 745 } 746 if (tree == &asext_tree) 747 break; 748 if (tree == &nbr->area->lsa_tree) 749 tree = &nbr->iface->lsa_tree; 750 else 751 tree = &asext_tree; 752 } while (1); 753 } 754 755 void 756 lsa_dump(struct lsa_tree *tree, int imsg_type, pid_t pid) 757 { 758 struct vertex *v; 759 760 RB_FOREACH(v, lsa_tree, tree) { 761 if (v->deleted) 762 continue; 763 lsa_age(v); 764 switch (imsg_type) { 765 case IMSG_CTL_SHOW_DATABASE: 766 rde_imsg_compose_ospfe(IMSG_CTL_SHOW_DATABASE, 0, pid, 767 &v->lsa->hdr, ntohs(v->lsa->hdr.len)); 768 continue; 769 case IMSG_CTL_SHOW_DB_SELF: 770 if (v->lsa->hdr.adv_rtr == rde_router_id()) 771 break; 772 continue; 773 case IMSG_CTL_SHOW_DB_EXT: 774 if (v->type == LSA_TYPE_EXTERNAL) 775 break; 776 continue; 777 case IMSG_CTL_SHOW_DB_LINK: 778 if (v->type == LSA_TYPE_LINK) 779 break; 780 continue; 781 case IMSG_CTL_SHOW_DB_NET: 782 if (v->type == LSA_TYPE_NETWORK) 783 break; 784 continue; 785 case IMSG_CTL_SHOW_DB_RTR: 786 if (v->type == LSA_TYPE_ROUTER) 787 break; 788 continue; 789 case IMSG_CTL_SHOW_DB_INTRA: 790 if (v->type == LSA_TYPE_INTRA_A_PREFIX) 791 break; 792 case IMSG_CTL_SHOW_DB_SUM: 793 if (v->type == LSA_TYPE_INTER_A_PREFIX) 794 break; 795 continue; 796 case IMSG_CTL_SHOW_DB_ASBR: 797 if (v->type == LSA_TYPE_INTER_A_ROUTER) 798 break; 799 continue; 800 default: 801 log_warnx("lsa_dump: unknown imsg type"); 802 return; 803 } 804 rde_imsg_compose_ospfe(imsg_type, 0, pid, &v->lsa->hdr, 805 ntohs(v->lsa->hdr.len)); 806 } 807 } 808 809 /* ARGSUSED */ 810 void 811 lsa_timeout(int fd, short event, void *bula) 812 { 813 struct vertex *v = bula; 814 struct timeval tv; 815 816 lsa_age(v); 817 818 if (v->deleted) { 819 if (ntohs(v->lsa->hdr.age) >= MAX_AGE) { 820 vertex_free(v); 821 } else { 822 v->deleted = 0; 823 824 /* schedule recalculation of the RIB */ 825 if (ntohs(v->lsa->hdr.type) == LSA_TYPE_LINK) 826 orig_intra_area_prefix_lsas(v->area); 827 if (ntohs(v->lsa->hdr.type) != LSA_TYPE_EXTERNAL) 828 v->area->dirty = 1; 829 start_spf_timer(); 830 831 rde_imsg_compose_ospfe(IMSG_LS_FLOOD, v->peerid, 0, 832 v->lsa, ntohs(v->lsa->hdr.len)); 833 834 /* timeout handling either MAX_AGE or LS_REFRESH_TIME */ 835 timerclear(&tv); 836 if (v->self) 837 tv.tv_sec = LS_REFRESH_TIME; 838 else 839 tv.tv_sec = MAX_AGE - ntohs(v->lsa->hdr.age); 840 841 if (evtimer_add(&v->ev, &tv) != 0) 842 fatal("lsa_timeout"); 843 } 844 return; 845 } 846 847 if (v->self && ntohs(v->lsa->hdr.age) < MAX_AGE) 848 lsa_refresh(v); 849 850 rde_imsg_compose_ospfe(IMSG_LS_FLOOD, v->peerid, 0, 851 v->lsa, ntohs(v->lsa->hdr.len)); 852 } 853 854 void 855 lsa_refresh(struct vertex *v) 856 { 857 struct timeval tv; 858 struct timespec tp; 859 u_int32_t seqnum; 860 u_int16_t len; 861 862 /* refresh LSA by increasing sequence number by one */ 863 if (v->self && ntohs(v->lsa->hdr.age) >= MAX_AGE) 864 /* self originated network that is currently beeing removed */ 865 v->lsa->hdr.age = htons(MAX_AGE); 866 else 867 v->lsa->hdr.age = htons(DEFAULT_AGE); 868 seqnum = ntohl(v->lsa->hdr.seq_num); 869 if (seqnum++ == MAX_SEQ_NUM) 870 /* XXX fix me */ 871 fatalx("sequence number wrapping"); 872 v->lsa->hdr.seq_num = htonl(seqnum); 873 874 /* recalculate checksum */ 875 len = ntohs(v->lsa->hdr.len); 876 v->lsa->hdr.ls_chksum = 0; 877 v->lsa->hdr.ls_chksum = htons(iso_cksum(v->lsa, len, LS_CKSUM_OFFSET)); 878 879 clock_gettime(CLOCK_MONOTONIC, &tp); 880 v->changed = v->stamp = tp.tv_sec; 881 882 timerclear(&tv); 883 tv.tv_sec = LS_REFRESH_TIME; 884 if (evtimer_add(&v->ev, &tv) == -1) 885 fatal("lsa_refresh"); 886 } 887 888 void 889 lsa_merge(struct rde_nbr *nbr, struct lsa *lsa, struct vertex *v) 890 { 891 struct timeval tv; 892 struct timespec tp; 893 time_t now; 894 u_int16_t len; 895 896 if (v == NULL) { 897 if (lsa_add(nbr, lsa)) 898 /* delayed update */ 899 return; 900 rde_imsg_compose_ospfe(IMSG_LS_FLOOD, nbr->peerid, 0, 901 lsa, ntohs(lsa->hdr.len)); 902 return; 903 } 904 905 /* set the seq_num to the current one. lsa_refresh() will do the ++ */ 906 lsa->hdr.seq_num = v->lsa->hdr.seq_num; 907 /* recalculate checksum */ 908 len = ntohs(lsa->hdr.len); 909 lsa->hdr.ls_chksum = 0; 910 lsa->hdr.ls_chksum = htons(iso_cksum(lsa, len, LS_CKSUM_OFFSET)); 911 912 /* compare LSA most header fields are equal so don't check them */ 913 if (lsa_equal(lsa, v->lsa)) { 914 free(lsa); 915 return; 916 } 917 918 /* overwrite the lsa all other fields are unaffected */ 919 free(v->lsa); 920 v->lsa = lsa; 921 if (v->type == LSA_TYPE_LINK) 922 orig_intra_area_prefix_lsas(nbr->area); 923 if (v->type != LSA_TYPE_EXTERNAL) 924 nbr->area->dirty = 1; 925 start_spf_timer(); 926 927 /* set correct timeout for reflooding the LSA */ 928 clock_gettime(CLOCK_MONOTONIC, &tp); 929 now = tp.tv_sec; 930 timerclear(&tv); 931 if (v->changed + MIN_LS_INTERVAL >= now) 932 tv.tv_sec = MIN_LS_INTERVAL; 933 if (evtimer_add(&v->ev, &tv) == -1) 934 fatal("lsa_merge"); 935 } 936 937 void 938 lsa_remove_invalid_sums(struct area *area) 939 { 940 struct lsa_tree *tree = &area->lsa_tree; 941 struct vertex *v, *nv; 942 943 /* XXX speed me up */ 944 for (v = RB_MIN(lsa_tree, tree); v != NULL; v = nv) { 945 nv = RB_NEXT(lsa_tree, tree, v); 946 if ((v->type == LSA_TYPE_INTER_A_PREFIX || 947 v->type == LSA_TYPE_INTER_A_ROUTER) && 948 v->self && v->cost == LS_INFINITY && 949 v->deleted == 0) { 950 /* 951 * age the lsa and call lsa_timeout() which will 952 * actually remove it from the database. 953 */ 954 v->lsa->hdr.age = htons(MAX_AGE); 955 lsa_timeout(0, 0, v); 956 } 957 } 958 } 959 960 int 961 lsa_equal(struct lsa *a, struct lsa *b) 962 { 963 /* 964 * compare LSA that already have same type, adv_rtr and ls_id 965 * so not all header need to be compared 966 */ 967 if (a == NULL || b == NULL) 968 return (0); 969 if (a->hdr.len != b->hdr.len) 970 return (0); 971 /* LSAs with age MAX_AGE are never equal */ 972 if (a->hdr.age == htons(MAX_AGE) || b->hdr.age == htons(MAX_AGE)) 973 return (0); 974 if (memcmp(&a->data, &b->data, ntohs(a->hdr.len) - 975 sizeof(struct lsa_hdr))) 976 return (0); 977 978 return (1); 979 } 980 981 int 982 lsa_get_prefix(void *buf, u_int16_t len, struct rt_prefix *p) 983 { 984 struct lsa_prefix *lp = buf; 985 u_int32_t *buf32, *addr = NULL; 986 u_int8_t prefixlen; 987 u_int16_t consumed; 988 989 if (len < sizeof(*lp)) 990 return (-1); 991 992 prefixlen = lp->prefixlen; 993 994 if (p) { 995 bzero(p, sizeof(*p)); 996 p->prefixlen = lp->prefixlen; 997 p->options = lp->options; 998 p->metric = ntohs(lp->metric); 999 addr = (u_int32_t *)&p->prefix; 1000 } 1001 1002 buf32 = (u_int32_t *)(lp + 1); 1003 consumed = sizeof(*lp); 1004 1005 for (prefixlen = LSA_PREFIXSIZE(prefixlen) / sizeof(u_int32_t); 1006 prefixlen > 0; prefixlen--) { 1007 if (len < consumed + sizeof(u_int32_t)) 1008 return (-1); 1009 if (addr) 1010 *addr++ = *buf32++; 1011 consumed += sizeof(u_int32_t); 1012 } 1013 1014 return (consumed); 1015 } 1016