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