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