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