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