1 /* $OpenBSD: lsupdate.c,v 1.41 2013/01/17 09:06:35 markus 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/hash.h> 22 #include <sys/socket.h> 23 #include <netinet/in.h> 24 #include <arpa/inet.h> 25 26 #include <stdlib.h> 27 #include <string.h> 28 29 #include "ospf.h" 30 #include "ospfd.h" 31 #include "log.h" 32 #include "ospfe.h" 33 #include "rde.h" 34 35 extern struct ospfd_conf *oeconf; 36 extern struct imsgev *iev_rde; 37 38 struct ibuf *prepare_ls_update(struct iface *); 39 int add_ls_update(struct ibuf *, struct iface *, void *, u_int16_t, 40 u_int16_t); 41 int send_ls_update(struct ibuf *, struct iface *, struct in_addr, 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) 152 { 153 struct ibuf *buf; 154 155 if ((buf = ibuf_dynamic(iface->mtu - sizeof(struct ip), 156 IP_MAXPACKET - sizeof(struct ip))) == NULL) 157 fatal("prepare_ls_update"); 158 159 /* OSPF header */ 160 if (gen_ospf_hdr(buf, iface, PACKET_TYPE_LS_UPDATE)) 161 goto fail; 162 163 /* reserve space for number of lsa field */ 164 if (ibuf_reserve(buf, sizeof(u_int32_t)) == NULL) 165 goto fail; 166 167 return (buf); 168 fail: 169 log_warn("prepare_ls_update"); 170 ibuf_free(buf); 171 return (NULL); 172 } 173 174 int 175 add_ls_update(struct ibuf *buf, struct iface *iface, void *data, u_int16_t len, 176 u_int16_t older) 177 { 178 void *lsage; 179 u_int16_t age; 180 181 if ((size_t)iface->mtu < sizeof(struct ip) + sizeof(struct ospf_hdr) + 182 sizeof(u_int32_t) + ibuf_size(buf) + len + MD5_DIGEST_LENGTH) { 183 /* start new packet unless this is the first LSA to pack */ 184 if (ibuf_size(buf) > sizeof(struct ospf_hdr) + 185 sizeof(u_int32_t)) 186 return (0); 187 } 188 189 lsage = ibuf_reserve(buf, 0); 190 if (ibuf_add(buf, data, len)) { 191 log_warn("add_ls_update"); 192 return (0); 193 } 194 195 /* age LSA before sending it out */ 196 memcpy(&age, data, sizeof(age)); 197 age = ntohs(age); 198 if ((age += older + iface->transmit_delay) >= MAX_AGE) 199 age = MAX_AGE; 200 age = htons(age); 201 memcpy(lsage, &age, sizeof(age)); 202 203 return (1); 204 } 205 206 207 208 int 209 send_ls_update(struct ibuf *buf, struct iface *iface, struct in_addr addr, 210 u_int32_t nlsa) 211 { 212 struct sockaddr_in dst; 213 int ret; 214 215 nlsa = htonl(nlsa); 216 memcpy(ibuf_seek(buf, sizeof(struct ospf_hdr), sizeof(nlsa)), 217 &nlsa, sizeof(nlsa)); 218 /* update authentication and calculate checksum */ 219 if (auth_gen(buf, iface)) 220 goto fail; 221 222 /* set destination */ 223 dst.sin_family = AF_INET; 224 dst.sin_len = sizeof(struct sockaddr_in); 225 dst.sin_addr.s_addr = addr.s_addr; 226 227 ret = send_packet(iface, buf, &dst); 228 229 ibuf_free(buf); 230 return (ret); 231 fail: 232 log_warn("send_ls_update"); 233 ibuf_free(buf); 234 return (-1); 235 } 236 237 void 238 recv_ls_update(struct nbr *nbr, char *buf, u_int16_t len) 239 { 240 struct lsa_hdr lsa; 241 u_int32_t nlsa; 242 243 if (len < sizeof(nlsa)) { 244 log_warnx("recv_ls_update: bad packet size, neighbor ID %s", 245 inet_ntoa(nbr->id)); 246 return; 247 } 248 memcpy(&nlsa, buf, sizeof(nlsa)); 249 nlsa = ntohl(nlsa); 250 buf += sizeof(nlsa); 251 len -= sizeof(nlsa); 252 253 switch (nbr->state) { 254 case NBR_STA_DOWN: 255 case NBR_STA_ATTEMPT: 256 case NBR_STA_INIT: 257 case NBR_STA_2_WAY: 258 case NBR_STA_XSTRT: 259 case NBR_STA_SNAP: 260 log_debug("recv_ls_update: packet ignored in state %s, " 261 "neighbor ID %s", nbr_state_name(nbr->state), 262 inet_ntoa(nbr->id)); 263 break; 264 case NBR_STA_XCHNG: 265 case NBR_STA_LOAD: 266 case NBR_STA_FULL: 267 for (; nlsa > 0 && len > 0; nlsa--) { 268 if (len < sizeof(lsa)) { 269 log_warnx("recv_ls_update: bad packet size, " 270 "neighbor ID %s", inet_ntoa(nbr->id)); 271 return; 272 } 273 memcpy(&lsa, buf, sizeof(lsa)); 274 if (len < ntohs(lsa.len)) { 275 log_warnx("recv_ls_update: bad packet size, " 276 "neighbor ID %s", inet_ntoa(nbr->id)); 277 return; 278 } 279 imsg_compose_event(iev_rde, IMSG_LS_UPD, nbr->peerid, 0, 280 -1, buf, ntohs(lsa.len)); 281 buf += ntohs(lsa.len); 282 len -= ntohs(lsa.len); 283 } 284 if (nlsa > 0 || len > 0) { 285 log_warnx("recv_ls_update: bad packet size, " 286 "neighbor ID %s", inet_ntoa(nbr->id)); 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 if (lsa_hdr->seq_num == le->le_ref->hdr.seq_num && 333 lsa_hdr->ls_chksum == le->le_ref->hdr.ls_chksum) { 334 ls_retrans_list_free(nbr, le); 335 return (0); 336 } 337 338 return (-1); 339 } 340 341 struct lsa_entry * 342 ls_retrans_list_get(struct nbr *nbr, struct lsa_hdr *lsa_hdr) 343 { 344 struct lsa_entry *le; 345 346 TAILQ_FOREACH(le, &nbr->ls_retrans_list, entry) { 347 if ((lsa_hdr->type == le->le_ref->hdr.type) && 348 (lsa_hdr->ls_id == le->le_ref->hdr.ls_id) && 349 (lsa_hdr->adv_rtr == le->le_ref->hdr.adv_rtr)) 350 return (le); 351 } 352 return (NULL); 353 } 354 355 void 356 ls_retrans_list_insert(struct nbr *nbr, struct lsa_entry *new) 357 { 358 struct lsa_entry *le; 359 unsigned short when = new->le_when; 360 361 TAILQ_FOREACH(le, &nbr->ls_retrans_list, entry) { 362 if (when < le->le_when) { 363 new->le_when = when; 364 TAILQ_INSERT_BEFORE(le, new, entry); 365 nbr->ls_ret_cnt++; 366 return; 367 } 368 when -= le->le_when; 369 } 370 new->le_when = when; 371 TAILQ_INSERT_TAIL(&nbr->ls_retrans_list, new, entry); 372 nbr->ls_ret_cnt++; 373 } 374 375 void 376 ls_retrans_list_remove(struct nbr *nbr, struct lsa_entry *le) 377 { 378 struct timeval tv; 379 struct lsa_entry *next = TAILQ_NEXT(le, entry); 380 int reset = 0; 381 382 /* adjust timeout of next entry */ 383 if (next) 384 next->le_when += le->le_when; 385 386 if (TAILQ_FIRST(&nbr->ls_retrans_list) == le && 387 evtimer_pending(&nbr->ls_retrans_timer, NULL)) 388 reset = 1; 389 390 TAILQ_REMOVE(&nbr->ls_retrans_list, le, entry); 391 nbr->ls_ret_cnt--; 392 393 if (reset && TAILQ_FIRST(&nbr->ls_retrans_list)) { 394 if (evtimer_del(&nbr->ls_retrans_timer) == -1) 395 fatal("ls_retrans_list_remove"); 396 397 timerclear(&tv); 398 tv.tv_sec = TAILQ_FIRST(&nbr->ls_retrans_list)->le_when; 399 400 if (evtimer_add(&nbr->ls_retrans_timer, &tv) == -1) 401 fatal("ls_retrans_list_remove"); 402 } 403 } 404 405 void 406 ls_retrans_list_free(struct nbr *nbr, struct lsa_entry *le) 407 { 408 ls_retrans_list_remove(nbr, le); 409 410 lsa_cache_put(le->le_ref, nbr); 411 free(le); 412 } 413 414 void 415 ls_retrans_list_clr(struct nbr *nbr) 416 { 417 struct lsa_entry *le; 418 419 while ((le = TAILQ_FIRST(&nbr->ls_retrans_list)) != NULL) 420 ls_retrans_list_free(nbr, le); 421 422 nbr->ls_ret_cnt = 0; 423 } 424 425 /* ARGSUSED */ 426 void 427 ls_retrans_timer(int fd, short event, void *bula) 428 { 429 struct timeval tv; 430 struct timespec tp; 431 struct in_addr addr; 432 struct nbr *nbr = bula; 433 struct lsa_entry *le; 434 struct ibuf *buf; 435 time_t now; 436 int d; 437 u_int32_t nlsa = 0; 438 439 if ((le = TAILQ_FIRST(&nbr->ls_retrans_list)) != NULL) 440 le->le_when = 0; /* timer fired */ 441 else 442 return; /* queue empty, nothing to do */ 443 444 clock_gettime(CLOCK_MONOTONIC, &tp); 445 now = tp.tv_sec; 446 447 if (nbr->iface->self == nbr) { 448 /* 449 * oneshot needs to be set for lsa queued for flooding, 450 * if oneshot is not set then the lsa needs to be converted 451 * because the router switched lately to DR or BDR 452 */ 453 if (le->le_oneshot && nbr->iface->state & IF_STA_DRORBDR) 454 inet_aton(AllSPFRouters, &addr); 455 else if (nbr->iface->state & IF_STA_DRORBDR) { 456 /* 457 * old retransmission needs to be converted into 458 * flood by rerunning the lsa_flood. 459 */ 460 lsa_flood(nbr->iface, nbr, &le->le_ref->hdr, 461 le->le_ref->data); 462 ls_retrans_list_free(nbr, le); 463 /* ls_retrans_list_free retriggers the timer */ 464 return; 465 } else if (nbr->iface->type == IF_TYPE_POINTOPOINT) 466 memcpy(&addr, &nbr->iface->dst, sizeof(addr)); 467 else 468 inet_aton(AllDRouters, &addr); 469 } else 470 memcpy(&addr, &nbr->addr, sizeof(addr)); 471 472 if ((buf = prepare_ls_update(nbr->iface)) == NULL) { 473 le->le_when = 1; 474 goto done; 475 } 476 477 while ((le = TAILQ_FIRST(&nbr->ls_retrans_list)) != NULL && 478 le->le_when == 0) { 479 d = now - le->le_ref->stamp; 480 if (d < 0) 481 d = 0; 482 else if (d > MAX_AGE) 483 d = MAX_AGE; 484 485 if (add_ls_update(buf, nbr->iface, le->le_ref->data, 486 le->le_ref->len, d) == 0) { 487 if (nlsa == 0) { 488 /* something bad happend retry later */ 489 log_warnx("ls_retrans_timer: sending LS update " 490 "to neighbor ID %s failed", 491 inet_ntoa(nbr->id)); 492 TAILQ_REMOVE(&nbr->ls_retrans_list, le, entry); 493 nbr->ls_ret_cnt--; 494 le->le_when = nbr->iface->rxmt_interval; 495 ls_retrans_list_insert(nbr, le); 496 } 497 break; 498 } 499 nlsa++; 500 if (le->le_oneshot) 501 ls_retrans_list_free(nbr, le); 502 else { 503 TAILQ_REMOVE(&nbr->ls_retrans_list, le, entry); 504 nbr->ls_ret_cnt--; 505 le->le_when = nbr->iface->rxmt_interval; 506 ls_retrans_list_insert(nbr, le); 507 } 508 } 509 if (nlsa) 510 send_ls_update(buf, nbr->iface, addr, nlsa); 511 else 512 ibuf_free(buf); 513 514 done: 515 if ((le = TAILQ_FIRST(&nbr->ls_retrans_list)) != NULL) { 516 timerclear(&tv); 517 tv.tv_sec = le->le_when; 518 519 if (evtimer_add(&nbr->ls_retrans_timer, &tv) == -1) 520 fatal("ls_retrans_timer"); 521 } 522 } 523 524 LIST_HEAD(lsa_cache_head, lsa_ref); 525 526 struct lsa_cache { 527 struct lsa_cache_head *hashtbl; 528 u_int32_t hashmask; 529 } lsacache; 530 531 struct lsa_ref *lsa_cache_look(struct lsa_hdr *); 532 533 void 534 lsa_cache_init(u_int32_t hashsize) 535 { 536 u_int32_t hs, i; 537 538 for (hs = 1; hs < hashsize; hs <<= 1) 539 ; 540 lsacache.hashtbl = calloc(hs, sizeof(struct lsa_cache_head)); 541 if (lsacache.hashtbl == NULL) 542 fatal("lsa_cache_init"); 543 544 for (i = 0; i < hs; i++) 545 LIST_INIT(&lsacache.hashtbl[i]); 546 547 lsacache.hashmask = hs - 1; 548 } 549 550 struct lsa_ref * 551 lsa_cache_add(void *data, u_int16_t len) 552 { 553 struct lsa_cache_head *head; 554 struct lsa_ref *ref, *old; 555 struct timespec tp; 556 557 if ((ref = calloc(1, sizeof(*ref))) == NULL) 558 fatal("lsa_cache_add"); 559 memcpy(&ref->hdr, data, sizeof(ref->hdr)); 560 561 if ((old = lsa_cache_look(&ref->hdr))) { 562 free(ref); 563 old->refcnt++; 564 return (old); 565 } 566 567 if ((ref->data = malloc(len)) == NULL) 568 fatal("lsa_cache_add"); 569 memcpy(ref->data, data, len); 570 571 clock_gettime(CLOCK_MONOTONIC, &tp); 572 ref->stamp = tp.tv_sec; 573 ref->len = len; 574 ref->refcnt = 1; 575 576 head = &lsacache.hashtbl[hash32_buf(&ref->hdr, sizeof(ref->hdr), 577 HASHINIT) & lsacache.hashmask]; 578 LIST_INSERT_HEAD(head, ref, entry); 579 return (ref); 580 } 581 582 struct lsa_ref * 583 lsa_cache_get(struct lsa_hdr *lsa_hdr) 584 { 585 struct lsa_ref *ref; 586 587 ref = lsa_cache_look(lsa_hdr); 588 if (ref) 589 ref->refcnt++; 590 591 return (ref); 592 } 593 594 void 595 lsa_cache_put(struct lsa_ref *ref, struct nbr *nbr) 596 { 597 if (--ref->refcnt > 0) 598 return; 599 600 if (ntohs(ref->hdr.age) >= MAX_AGE) 601 ospfe_imsg_compose_rde(IMSG_LS_MAXAGE, nbr->peerid, 0, 602 ref->data, sizeof(struct lsa_hdr)); 603 604 free(ref->data); 605 LIST_REMOVE(ref, entry); 606 free(ref); 607 } 608 609 struct lsa_ref * 610 lsa_cache_look(struct lsa_hdr *lsa_hdr) 611 { 612 struct lsa_cache_head *head; 613 struct lsa_ref *ref; 614 615 head = &lsacache.hashtbl[hash32_buf(lsa_hdr, sizeof(*lsa_hdr), 616 HASHINIT) & lsacache.hashmask]; 617 618 LIST_FOREACH(ref, head, entry) { 619 if (memcmp(&ref->hdr, lsa_hdr, sizeof(*lsa_hdr)) == 0) 620 /* found match */ 621 return (ref); 622 } 623 624 return (NULL); 625 } 626