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