1 /* $OpenBSD: lsupdate.c,v 1.21 2021/11/03 21:40:03 sthen Exp $ */ 2 3 /* 4 * Copyright (c) 2005 Claudio Jeker <claudio@openbsd.org> 5 * Copyright (c) 2004, 2005, 2007 Esben Norby <norby@openbsd.org> 6 * 7 * Permission to use, copy, modify, and distribute this software for any 8 * purpose with or without fee is hereby granted, provided that the above 9 * copyright notice and this permission notice appear in all copies. 10 * 11 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 12 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 13 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 14 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 15 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 16 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 17 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 18 */ 19 20 #include <sys/types.h> 21 #include <sys/socket.h> 22 #include <netinet/in.h> 23 #include <netinet/ip6.h> 24 #include <netinet/ip_ah.h> 25 #include <arpa/inet.h> 26 27 #include <stdlib.h> 28 #include <string.h> 29 #include <siphash.h> 30 31 #include "ospf6.h" 32 #include "ospf6d.h" 33 #include "log.h" 34 #include "ospfe.h" 35 #include "rde.h" 36 37 struct ibuf *prepare_ls_update(struct iface *, int); 38 int add_ls_update(struct ibuf *, struct iface *, void *, u_int16_t, 39 u_int16_t); 40 int send_ls_update(struct ibuf *, struct iface *, struct in6_addr, 41 u_int32_t); 42 43 void ls_retrans_list_insert(struct nbr *, struct lsa_entry *); 44 void ls_retrans_list_remove(struct nbr *, struct lsa_entry *); 45 46 /* link state update packet handling */ 47 int 48 lsa_flood(struct iface *iface, struct nbr *originator, struct lsa_hdr *lsa_hdr, 49 void *data) 50 { 51 struct nbr *nbr; 52 struct lsa_entry *le = NULL; 53 int queued = 0, dont_ack = 0; 54 int r; 55 56 LIST_FOREACH(nbr, &iface->nbr_list, entry) { 57 if (nbr == iface->self) 58 continue; 59 if (!(nbr->state & NBR_STA_FLOOD)) 60 continue; 61 62 if (iface->state & IF_STA_DROTHER && !queued) 63 while ((le = ls_retrans_list_get(iface->self, lsa_hdr))) 64 ls_retrans_list_free(iface->self, le); 65 66 while ((le = ls_retrans_list_get(nbr, lsa_hdr))) 67 ls_retrans_list_free(nbr, le); 68 69 if (!(nbr->state & NBR_STA_FULL) && 70 (le = ls_req_list_get(nbr, lsa_hdr)) != NULL) { 71 r = lsa_newer(lsa_hdr, le->le_lsa); 72 if (r > 0) { 73 /* to flood LSA is newer than requested */ 74 ls_req_list_free(nbr, le); 75 /* new needs to be flooded */ 76 } else if (r < 0) { 77 /* to flood LSA is older than requested */ 78 continue; 79 } else { 80 /* LSA are equal */ 81 ls_req_list_free(nbr, le); 82 continue; 83 } 84 } 85 86 if (nbr == originator) { 87 dont_ack++; 88 continue; 89 } 90 91 /* non DR or BDR router keep all lsa in one retrans list */ 92 if (iface->state & IF_STA_DROTHER) { 93 if (!queued) 94 ls_retrans_list_add(iface->self, data, 95 iface->rxmt_interval, 0); 96 queued = 1; 97 } else { 98 ls_retrans_list_add(nbr, data, iface->rxmt_interval, 0); 99 queued = 1; 100 } 101 } 102 103 if (!queued) 104 return (0); 105 106 if (iface == originator->iface && iface->self != originator) { 107 if (iface->dr == originator || iface->bdr == originator) 108 return (0); 109 if (iface->state & IF_STA_BACKUP) 110 return (0); 111 dont_ack++; 112 } 113 114 /* 115 * initial flood needs to be queued separately, timeout is zero 116 * and oneshot has to be set because the retransimssion queues 117 * are already loaded. 118 */ 119 switch (iface->type) { 120 case IF_TYPE_POINTOPOINT: 121 case IF_TYPE_BROADCAST: 122 ls_retrans_list_add(iface->self, data, 0, 1); 123 break; 124 case IF_TYPE_NBMA: 125 case IF_TYPE_POINTOMULTIPOINT: 126 case IF_TYPE_VIRTUALLINK: 127 LIST_FOREACH(nbr, &iface->nbr_list, entry) { 128 if (nbr == iface->self) 129 continue; 130 if (!(nbr->state & NBR_STA_FLOOD)) 131 continue; 132 if (!TAILQ_EMPTY(&nbr->ls_retrans_list)) { 133 le = TAILQ_LAST(&nbr->ls_retrans_list, 134 lsa_head); 135 if (lsa_hdr->type != le->le_lsa->type || 136 lsa_hdr->ls_id != le->le_lsa->ls_id || 137 lsa_hdr->adv_rtr != le->le_lsa->adv_rtr) 138 continue; 139 } 140 ls_retrans_list_add(nbr, data, 0, 1); 141 } 142 break; 143 default: 144 fatalx("lsa_flood: unknown interface type"); 145 } 146 147 return (dont_ack == 2); 148 } 149 150 struct ibuf * 151 prepare_ls_update(struct iface *iface, int bigpkt) 152 { 153 struct ibuf *buf; 154 size_t size; 155 156 size = bigpkt ? IPV6_MAXPACKET : iface->mtu; 157 if (size < IPV6_MMTU) 158 size = IPV6_MMTU; 159 size -= sizeof(struct ip6_hdr); 160 161 /* 162 * Reserve space for optional ah or esp encryption. The 163 * algorithm is taken from ah_output and esp_output, the 164 * values are the maxima of crypto/xform.c. 165 */ 166 size -= max( 167 /* base-ah-header replay authsize */ 168 AH_FLENGTH + sizeof(u_int32_t) + 32, 169 /* spi sequence ivlen blocksize pad-length next-header authsize */ 170 2 * sizeof(u_int32_t) + 16 + 16 + 2 * sizeof(u_int8_t) + 32); 171 172 if ((buf = ibuf_open(size)) == NULL) 173 fatal("prepare_ls_update"); 174 175 /* OSPF header */ 176 if (gen_ospf_hdr(buf, iface, PACKET_TYPE_LS_UPDATE)) 177 goto fail; 178 179 /* reserve space for number of lsa field */ 180 if (ibuf_reserve(buf, sizeof(u_int32_t)) == NULL) 181 goto fail; 182 183 return (buf); 184 fail: 185 log_warn("prepare_ls_update"); 186 ibuf_free(buf); 187 return (NULL); 188 } 189 190 int 191 add_ls_update(struct ibuf *buf, struct iface *iface, void *data, u_int16_t len, 192 u_int16_t older) 193 { 194 size_t ageoff; 195 u_int16_t age; 196 197 if (buf->wpos + len >= buf->max) 198 return (0); 199 200 ageoff = ibuf_size(buf); 201 if (ibuf_add(buf, data, len)) { 202 log_warn("add_ls_update"); 203 return (0); 204 } 205 206 /* age LSA before sending it out */ 207 memcpy(&age, data, sizeof(age)); 208 age = ntohs(age); 209 if ((age += older + iface->transmit_delay) >= MAX_AGE) 210 age = MAX_AGE; 211 age = htons(age); 212 memcpy(ibuf_seek(buf, ageoff, sizeof(age)), &age, sizeof(age)); 213 214 return (1); 215 } 216 217 int 218 send_ls_update(struct ibuf *buf, struct iface *iface, struct in6_addr addr, 219 u_int32_t nlsa) 220 { 221 nlsa = htonl(nlsa); 222 memcpy(ibuf_seek(buf, sizeof(struct ospf_hdr), sizeof(nlsa)), 223 &nlsa, sizeof(nlsa)); 224 /* calculate checksum */ 225 if (upd_ospf_hdr(buf, iface)) 226 goto fail; 227 228 if (send_packet(iface, buf, &addr) == -1) 229 goto fail; 230 231 ibuf_free(buf); 232 return (0); 233 fail: 234 log_warn("send_ls_update"); 235 ibuf_free(buf); 236 return (-1); 237 } 238 239 void 240 recv_ls_update(struct nbr *nbr, char *buf, u_int16_t len) 241 { 242 struct lsa_hdr lsa; 243 u_int32_t nlsa; 244 245 if (len < sizeof(nlsa)) { 246 log_warnx("recv_ls_update: bad packet size, " 247 "neighbor ID %s (%s)", inet_ntoa(nbr->id), 248 nbr->iface->name); 249 return; 250 } 251 memcpy(&nlsa, buf, sizeof(nlsa)); 252 nlsa = ntohl(nlsa); 253 buf += sizeof(nlsa); 254 len -= sizeof(nlsa); 255 256 switch (nbr->state) { 257 case NBR_STA_DOWN: 258 case NBR_STA_ATTEMPT: 259 case NBR_STA_INIT: 260 case NBR_STA_2_WAY: 261 case NBR_STA_XSTRT: 262 case NBR_STA_SNAP: 263 log_debug("recv_ls_update: packet ignored in state %s, " 264 "neighbor ID %s (%s)", nbr_state_name(nbr->state), 265 inet_ntoa(nbr->id), nbr->iface->name); 266 break; 267 case NBR_STA_XCHNG: 268 case NBR_STA_LOAD: 269 case NBR_STA_FULL: 270 for (; nlsa > 0 && len > 0; nlsa--) { 271 if (len < sizeof(lsa)) { 272 log_warnx("recv_ls_update: bad packet size, " 273 "neighbor ID %s (%s)", inet_ntoa(nbr->id), 274 nbr->iface->name); 275 return; 276 } 277 memcpy(&lsa, buf, sizeof(lsa)); 278 if (len < ntohs(lsa.len)) { 279 log_warnx("recv_ls_update: bad packet size, " 280 "neighbor ID %s (%s)", inet_ntoa(nbr->id), 281 nbr->iface->name); 282 return; 283 } 284 ospfe_imsg_compose_rde(IMSG_LS_UPD, nbr->peerid, 0, 285 buf, ntohs(lsa.len)); 286 buf += ntohs(lsa.len); 287 len -= ntohs(lsa.len); 288 } 289 if (nlsa > 0 || len > 0) { 290 log_warnx("recv_ls_update: bad packet size, " 291 "neighbor ID %s (%s)", inet_ntoa(nbr->id), 292 nbr->iface->name); 293 return; 294 } 295 break; 296 default: 297 fatalx("recv_ls_update: unknown neighbor state"); 298 } 299 } 300 301 /* link state retransmit list */ 302 void 303 ls_retrans_list_add(struct nbr *nbr, struct lsa_hdr *lsa, 304 unsigned short timeout, unsigned short oneshot) 305 { 306 struct timeval tv; 307 struct lsa_entry *le; 308 struct lsa_ref *ref; 309 310 if ((ref = lsa_cache_get(lsa)) == NULL) 311 fatalx("King Bula sez: somebody forgot to lsa_cache_add"); 312 313 if ((le = calloc(1, sizeof(*le))) == NULL) 314 fatal("ls_retrans_list_add"); 315 316 le->le_ref = ref; 317 le->le_when = timeout; 318 le->le_oneshot = oneshot; 319 320 ls_retrans_list_insert(nbr, le); 321 322 if (!evtimer_pending(&nbr->ls_retrans_timer, NULL)) { 323 timerclear(&tv); 324 tv.tv_sec = TAILQ_FIRST(&nbr->ls_retrans_list)->le_when; 325 326 if (evtimer_add(&nbr->ls_retrans_timer, &tv) == -1) 327 fatal("ls_retrans_list_add"); 328 } 329 } 330 331 int 332 ls_retrans_list_del(struct nbr *nbr, struct lsa_hdr *lsa_hdr) 333 { 334 struct lsa_entry *le; 335 336 if ((le = ls_retrans_list_get(nbr, lsa_hdr)) == NULL) 337 return (-1); 338 /* 339 * Compare LSA with the Ack by comparing not only the seq_num and 340 * checksum but also the age field. Since we only care about MAX_AGE 341 * vs. non-MAX_AGE LSA, a simple >= comparison is good enough. This 342 * ensures that a LSA withdrawal is not acked by a previous update. 343 */ 344 if (lsa_hdr->seq_num == le->le_ref->hdr.seq_num && 345 lsa_hdr->ls_chksum == le->le_ref->hdr.ls_chksum && 346 ntohs(lsa_hdr->age) >= ntohs(le->le_ref->hdr.age)) { 347 ls_retrans_list_free(nbr, le); 348 return (0); 349 } 350 351 return (-1); 352 } 353 354 struct lsa_entry * 355 ls_retrans_list_get(struct nbr *nbr, struct lsa_hdr *lsa_hdr) 356 { 357 struct lsa_entry *le; 358 359 TAILQ_FOREACH(le, &nbr->ls_retrans_list, entry) { 360 if ((lsa_hdr->type == le->le_ref->hdr.type) && 361 (lsa_hdr->ls_id == le->le_ref->hdr.ls_id) && 362 (lsa_hdr->adv_rtr == le->le_ref->hdr.adv_rtr)) 363 return (le); 364 } 365 return (NULL); 366 } 367 368 void 369 ls_retrans_list_insert(struct nbr *nbr, struct lsa_entry *new) 370 { 371 struct lsa_entry *le; 372 unsigned short when = new->le_when; 373 374 TAILQ_FOREACH(le, &nbr->ls_retrans_list, entry) { 375 if (when < le->le_when) { 376 new->le_when = when; 377 TAILQ_INSERT_BEFORE(le, new, entry); 378 nbr->ls_ret_cnt++; 379 return; 380 } 381 when -= le->le_when; 382 } 383 new->le_when = when; 384 TAILQ_INSERT_TAIL(&nbr->ls_retrans_list, new, entry); 385 nbr->ls_ret_cnt++; 386 } 387 388 void 389 ls_retrans_list_remove(struct nbr *nbr, struct lsa_entry *le) 390 { 391 struct timeval tv; 392 struct lsa_entry *next = TAILQ_NEXT(le, entry); 393 int reset = 0; 394 395 /* adjust timeout of next entry */ 396 if (next) 397 next->le_when += le->le_when; 398 399 if (TAILQ_FIRST(&nbr->ls_retrans_list) == le && 400 evtimer_pending(&nbr->ls_retrans_timer, NULL)) 401 reset = 1; 402 403 TAILQ_REMOVE(&nbr->ls_retrans_list, le, entry); 404 nbr->ls_ret_cnt--; 405 406 if (reset && TAILQ_FIRST(&nbr->ls_retrans_list)) { 407 if (evtimer_del(&nbr->ls_retrans_timer) == -1) 408 fatal("ls_retrans_list_remove"); 409 410 timerclear(&tv); 411 tv.tv_sec = TAILQ_FIRST(&nbr->ls_retrans_list)->le_when; 412 413 if (evtimer_add(&nbr->ls_retrans_timer, &tv) == -1) 414 fatal("ls_retrans_list_remove"); 415 } 416 } 417 418 void 419 ls_retrans_list_free(struct nbr *nbr, struct lsa_entry *le) 420 { 421 ls_retrans_list_remove(nbr, le); 422 423 lsa_cache_put(le->le_ref, nbr); 424 free(le); 425 } 426 427 void 428 ls_retrans_list_clr(struct nbr *nbr) 429 { 430 struct lsa_entry *le; 431 432 while ((le = TAILQ_FIRST(&nbr->ls_retrans_list)) != NULL) 433 ls_retrans_list_free(nbr, le); 434 435 nbr->ls_ret_cnt = 0; 436 } 437 438 /* ARGSUSED */ 439 void 440 ls_retrans_timer(int fd, short event, void *bula) 441 { 442 struct timeval tv; 443 struct timespec tp; 444 struct in6_addr addr; 445 struct nbr *nbr = bula; 446 struct lsa_entry *le; 447 struct ibuf *buf; 448 time_t now; 449 int d, bigpkt; 450 u_int32_t nlsa = 0; 451 452 if ((le = TAILQ_FIRST(&nbr->ls_retrans_list)) != NULL) 453 le->le_when = 0; /* timer fired */ 454 else 455 return; /* queue empty, nothing to do */ 456 457 clock_gettime(CLOCK_MONOTONIC, &tp); 458 now = tp.tv_sec; 459 460 if (nbr->iface->self == nbr) { 461 /* 462 * oneshot needs to be set for lsa queued for flooding, 463 * if oneshot is not set then the lsa needs to be converted 464 * because the router switched lately to DR or BDR 465 */ 466 if (le->le_oneshot && nbr->iface->state & IF_STA_DRORBDR) 467 inet_pton(AF_INET6, AllSPFRouters, &addr); 468 else if (nbr->iface->state & IF_STA_DRORBDR) { 469 /* 470 * old retransmission needs to be converted into 471 * flood by rerunning the lsa_flood. 472 */ 473 lsa_flood(nbr->iface, nbr, &le->le_ref->hdr, 474 le->le_ref->data); 475 ls_retrans_list_free(nbr, le); 476 /* ls_retrans_list_free retriggers the timer */ 477 return; 478 } else if (nbr->iface->type == IF_TYPE_POINTOPOINT) 479 memcpy(&addr, &nbr->addr, sizeof(addr)); 480 else 481 inet_pton(AF_INET6, AllDRouters, &addr); 482 } else 483 memcpy(&addr, &nbr->addr, sizeof(addr)); 484 485 bigpkt = le->le_ref->len > 1024; 486 if ((buf = prepare_ls_update(nbr->iface, bigpkt)) == NULL) { 487 le->le_when = 1; 488 goto done; 489 } 490 491 while ((le = TAILQ_FIRST(&nbr->ls_retrans_list)) != NULL && 492 le->le_when == 0) { 493 d = now - le->le_ref->stamp; 494 if (d < 0) 495 d = 0; 496 else if (d > MAX_AGE) 497 d = MAX_AGE; 498 499 if (add_ls_update(buf, nbr->iface, le->le_ref->data, 500 le->le_ref->len, d) == 0) { 501 if (nlsa == 0) { 502 /* something bad happened retry later */ 503 log_warnx("ls_retrans_timer: sending LS update " 504 "to neighbor ID %s (%s) failed", 505 inet_ntoa(nbr->id), nbr->iface->name); 506 log_debug("ls_retrans_timer: type: %04x len: %u", 507 ntohs(le->le_ref->hdr.type), 508 le->le_ref->len); 509 TAILQ_REMOVE(&nbr->ls_retrans_list, le, entry); 510 nbr->ls_ret_cnt--; 511 le->le_when = nbr->iface->rxmt_interval; 512 ls_retrans_list_insert(nbr, le); 513 } 514 break; 515 } 516 nlsa++; 517 if (le->le_oneshot) 518 ls_retrans_list_free(nbr, le); 519 else { 520 TAILQ_REMOVE(&nbr->ls_retrans_list, le, entry); 521 nbr->ls_ret_cnt--; 522 le->le_when = nbr->iface->rxmt_interval; 523 ls_retrans_list_insert(nbr, le); 524 } 525 } 526 if (nlsa) 527 send_ls_update(buf, nbr->iface, addr, nlsa); 528 else 529 ibuf_free(buf); 530 531 done: 532 if ((le = TAILQ_FIRST(&nbr->ls_retrans_list)) != NULL) { 533 timerclear(&tv); 534 tv.tv_sec = le->le_when; 535 536 if (evtimer_add(&nbr->ls_retrans_timer, &tv) == -1) 537 fatal("ls_retrans_timer"); 538 } 539 } 540 541 LIST_HEAD(lsa_cache_head, lsa_ref); 542 543 struct lsa_cache { 544 struct lsa_cache_head *hashtbl; 545 u_int32_t hashmask; 546 } lsacache; 547 548 SIPHASH_KEY lsacachekey; 549 550 struct lsa_ref *lsa_cache_look(struct lsa_hdr *); 551 552 void 553 lsa_cache_init(u_int32_t hashsize) 554 { 555 u_int32_t hs, i; 556 557 for (hs = 1; hs < hashsize; hs <<= 1) 558 ; 559 lsacache.hashtbl = calloc(hs, sizeof(struct lsa_cache_head)); 560 if (lsacache.hashtbl == NULL) 561 fatal("lsa_cache_init"); 562 563 for (i = 0; i < hs; i++) 564 LIST_INIT(&lsacache.hashtbl[i]); 565 arc4random_buf(&lsacachekey, sizeof(lsacachekey)); 566 567 lsacache.hashmask = hs - 1; 568 } 569 570 static uint32_t 571 lsa_hash_hdr(const struct lsa_hdr *hdr) 572 { 573 return SipHash24(&lsacachekey, hdr, sizeof(*hdr)); 574 } 575 576 struct lsa_ref * 577 lsa_cache_add(void *data, u_int16_t len) 578 { 579 struct lsa_cache_head *head; 580 struct lsa_ref *ref, *old; 581 struct timespec tp; 582 583 if ((ref = calloc(1, sizeof(*ref))) == NULL) 584 fatal("lsa_cache_add"); 585 memcpy(&ref->hdr, data, sizeof(ref->hdr)); 586 587 if ((old = lsa_cache_look(&ref->hdr))) { 588 free(ref); 589 old->refcnt++; 590 return (old); 591 } 592 593 if ((ref->data = malloc(len)) == NULL) 594 fatal("lsa_cache_add"); 595 memcpy(ref->data, data, len); 596 597 clock_gettime(CLOCK_MONOTONIC, &tp); 598 ref->stamp = tp.tv_sec; 599 ref->len = len; 600 ref->refcnt = 1; 601 602 head = &lsacache.hashtbl[lsa_hash_hdr(&ref->hdr) & lsacache.hashmask]; 603 LIST_INSERT_HEAD(head, ref, entry); 604 return (ref); 605 } 606 607 struct lsa_ref * 608 lsa_cache_get(struct lsa_hdr *lsa_hdr) 609 { 610 struct lsa_ref *ref; 611 612 ref = lsa_cache_look(lsa_hdr); 613 if (ref) 614 ref->refcnt++; 615 616 return (ref); 617 } 618 619 void 620 lsa_cache_put(struct lsa_ref *ref, struct nbr *nbr) 621 { 622 if (--ref->refcnt > 0) 623 return; 624 625 if (ntohs(ref->hdr.age) >= MAX_AGE) 626 ospfe_imsg_compose_rde(IMSG_LS_MAXAGE, nbr->peerid, 0, 627 ref->data, sizeof(struct lsa_hdr)); 628 629 free(ref->data); 630 LIST_REMOVE(ref, entry); 631 free(ref); 632 } 633 634 struct lsa_ref * 635 lsa_cache_look(struct lsa_hdr *lsa_hdr) 636 { 637 struct lsa_cache_head *head; 638 struct lsa_ref *ref; 639 640 head = &lsacache.hashtbl[lsa_hash_hdr(lsa_hdr) & lsacache.hashmask]; 641 642 LIST_FOREACH(ref, head, entry) { 643 if (memcmp(&ref->hdr, lsa_hdr, sizeof(*lsa_hdr)) == 0) 644 /* found match */ 645 return (ref); 646 } 647 648 return (NULL); 649 } 650