1 /* $OpenBSD: lsupdate.c,v 1.3 2008/02/11 13:48:39 norby 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/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 "ospf6.h" 30 #include "ospf6d.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 in6_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 int 200 send_ls_update(struct buf *buf, struct iface *iface, struct in6_addr addr, 201 u_int32_t nlsa) 202 { 203 int ret; 204 205 nlsa = htonl(nlsa); 206 memcpy(buf_seek(buf, sizeof(struct ospf_hdr), sizeof(nlsa)), 207 &nlsa, sizeof(nlsa)); 208 /* calculate checksum */ 209 if (upd_ospf_hdr(buf, iface)) 210 goto fail; 211 212 ret = send_packet(iface, buf->buf, buf->wpos, &addr); 213 214 buf_free(buf); 215 return (ret); 216 fail: 217 log_warn("send_ls_update"); 218 buf_free(buf); 219 return (-1); 220 } 221 222 void 223 recv_ls_update(struct nbr *nbr, char *buf, u_int16_t len) 224 { 225 struct lsa_hdr lsa; 226 u_int32_t nlsa; 227 228 if (len < sizeof(nlsa)) { 229 log_warnx("recv_ls_update: bad packet size, neighbor ID %s", 230 inet_ntoa(nbr->id)); 231 return; 232 } 233 memcpy(&nlsa, buf, sizeof(nlsa)); 234 nlsa = ntohl(nlsa); 235 buf += sizeof(nlsa); 236 len -= sizeof(nlsa); 237 238 switch (nbr->state) { 239 case NBR_STA_DOWN: 240 case NBR_STA_ATTEMPT: 241 case NBR_STA_INIT: 242 case NBR_STA_2_WAY: 243 case NBR_STA_XSTRT: 244 case NBR_STA_SNAP: 245 log_debug("recv_ls_update: packet ignored in state %s, " 246 "neighbor ID %s", nbr_state_name(nbr->state), 247 inet_ntoa(nbr->id)); 248 break; 249 case NBR_STA_XCHNG: 250 case NBR_STA_LOAD: 251 case NBR_STA_FULL: 252 for (; nlsa > 0 && len > 0; nlsa--) { 253 if (len < sizeof(lsa)) { 254 log_warnx("recv_ls_update: bad packet size, " 255 "neighbor ID %s", inet_ntoa(nbr->id)); 256 return; 257 } 258 memcpy(&lsa, buf, sizeof(lsa)); 259 if (len < ntohs(lsa.len)) { 260 log_warnx("recv_ls_update: bad packet size, " 261 "neighbor ID %s", inet_ntoa(nbr->id)); 262 return; 263 } 264 imsg_compose(ibuf_rde, IMSG_LS_UPD, nbr->peerid, 0, 265 buf, ntohs(lsa.len)); 266 buf += ntohs(lsa.len); 267 len -= ntohs(lsa.len); 268 } 269 if (nlsa > 0 || len > 0) { 270 log_warnx("recv_ls_update: bad packet size, " 271 "neighbor ID %s", inet_ntoa(nbr->id)); 272 return; 273 } 274 break; 275 default: 276 fatalx("recv_ls_update: unknown neighbor state"); 277 } 278 } 279 280 /* link state retransmit list */ 281 void 282 ls_retrans_list_add(struct nbr *nbr, struct lsa_hdr *lsa, 283 unsigned short timeout, unsigned short oneshot) 284 { 285 struct timeval tv; 286 struct lsa_entry *le; 287 struct lsa_ref *ref; 288 289 if ((ref = lsa_cache_get(lsa)) == NULL) 290 fatalx("King Bula sez: somebody forgot to lsa_cache_add"); 291 292 if ((le = calloc(1, sizeof(*le))) == NULL) 293 fatal("ls_retrans_list_add"); 294 295 le->le_ref = ref; 296 le->le_when = timeout; 297 le->le_oneshot = oneshot; 298 299 ls_retrans_list_insert(nbr, le); 300 301 if (!evtimer_pending(&nbr->ls_retrans_timer, NULL)) { 302 timerclear(&tv); 303 tv.tv_sec = TAILQ_FIRST(&nbr->ls_retrans_list)->le_when; 304 305 if (evtimer_add(&nbr->ls_retrans_timer, &tv) == -1) 306 fatal("ls_retrans_list_add"); 307 } 308 } 309 310 int 311 ls_retrans_list_del(struct nbr *nbr, struct lsa_hdr *lsa_hdr) 312 { 313 struct lsa_entry *le; 314 315 if ((le = ls_retrans_list_get(nbr, lsa_hdr)) == NULL) 316 return (-1); 317 if (lsa_hdr->seq_num == le->le_ref->hdr.seq_num && 318 lsa_hdr->ls_chksum == le->le_ref->hdr.ls_chksum) { 319 ls_retrans_list_free(nbr, le); 320 return (0); 321 } 322 323 return (-1); 324 } 325 326 struct lsa_entry * 327 ls_retrans_list_get(struct nbr *nbr, struct lsa_hdr *lsa_hdr) 328 { 329 struct lsa_entry *le; 330 331 TAILQ_FOREACH(le, &nbr->ls_retrans_list, entry) { 332 if ((lsa_hdr->type == le->le_ref->hdr.type) && 333 (lsa_hdr->ls_id == le->le_ref->hdr.ls_id) && 334 (lsa_hdr->adv_rtr == le->le_ref->hdr.adv_rtr)) 335 return (le); 336 } 337 return (NULL); 338 } 339 340 void 341 ls_retrans_list_insert(struct nbr *nbr, struct lsa_entry *new) 342 { 343 struct lsa_entry *le; 344 unsigned short when = new->le_when; 345 346 TAILQ_FOREACH(le, &nbr->ls_retrans_list, entry) { 347 if (when < le->le_when) { 348 new->le_when = when; 349 TAILQ_INSERT_BEFORE(le, new, entry); 350 nbr->ls_ret_cnt++; 351 return; 352 } 353 when -= le->le_when; 354 } 355 new->le_when = when; 356 TAILQ_INSERT_TAIL(&nbr->ls_retrans_list, new, entry); 357 nbr->ls_ret_cnt++; 358 } 359 360 void 361 ls_retrans_list_remove(struct nbr *nbr, struct lsa_entry *le) 362 { 363 struct timeval tv; 364 struct lsa_entry *next = TAILQ_NEXT(le, entry); 365 int reset = 0; 366 367 /* adjust timeout of next entry */ 368 if (next) 369 next->le_when += le->le_when; 370 371 if (TAILQ_FIRST(&nbr->ls_retrans_list) == le && 372 evtimer_pending(&nbr->ls_retrans_timer, NULL)) 373 reset = 1; 374 375 TAILQ_REMOVE(&nbr->ls_retrans_list, le, entry); 376 nbr->ls_ret_cnt--; 377 378 if (reset && TAILQ_FIRST(&nbr->ls_retrans_list)) { 379 if (evtimer_del(&nbr->ls_retrans_timer) == -1) 380 fatal("ls_retrans_list_remove"); 381 382 timerclear(&tv); 383 tv.tv_sec = TAILQ_FIRST(&nbr->ls_retrans_list)->le_when; 384 385 if (evtimer_add(&nbr->ls_retrans_timer, &tv) == -1) 386 fatal("ls_retrans_list_remove"); 387 } 388 } 389 390 void 391 ls_retrans_list_free(struct nbr *nbr, struct lsa_entry *le) 392 { 393 ls_retrans_list_remove(nbr, le); 394 395 lsa_cache_put(le->le_ref, nbr); 396 free(le); 397 } 398 399 void 400 ls_retrans_list_clr(struct nbr *nbr) 401 { 402 struct lsa_entry *le; 403 404 while ((le = TAILQ_FIRST(&nbr->ls_retrans_list)) != NULL) 405 ls_retrans_list_free(nbr, le); 406 407 nbr->ls_ret_cnt = 0; 408 } 409 410 /* ARGSUSED */ 411 void 412 ls_retrans_timer(int fd, short event, void *bula) 413 { 414 struct timeval tv; 415 struct timespec tp; 416 struct in6_addr addr; 417 struct nbr *nbr = bula; 418 struct lsa_entry *le; 419 struct buf *buf; 420 time_t now; 421 int d; 422 u_int32_t nlsa = 0; 423 424 if ((le = TAILQ_FIRST(&nbr->ls_retrans_list)) != NULL) 425 le->le_when = 0; /* timer fired */ 426 else 427 return; /* queue empty, nothing to do */ 428 429 clock_gettime(CLOCK_MONOTONIC, &tp); 430 now = tp.tv_sec; 431 432 if (nbr->iface->self == nbr) { 433 /* 434 * oneshot needs to be set for lsa queued for flooding, 435 * if oneshot is not set then the lsa needs to be converted 436 * because the router switched lately to DR or BDR 437 */ 438 if (le->le_oneshot && nbr->iface->state & IF_STA_DRORBDR) 439 inet_pton(AF_INET6, AllSPFRouters, &addr); 440 else if (nbr->iface->state & IF_STA_DRORBDR) { 441 /* 442 * old retransmission needs to be converted into 443 * flood by rerunning the lsa_flood. 444 */ 445 lsa_flood(nbr->iface, nbr, &le->le_ref->hdr, 446 le->le_ref->data); 447 ls_retrans_list_free(nbr, le); 448 /* ls_retrans_list_free retriggers the timer */ 449 return; 450 } else 451 inet_pton(AF_INET6, AllDRouters, &addr); 452 } else 453 memcpy(&addr, &nbr->addr, sizeof(addr)); 454 455 if ((buf = prepare_ls_update(nbr->iface)) == NULL) { 456 le->le_when = 1; 457 goto done; 458 } 459 460 while ((le = TAILQ_FIRST(&nbr->ls_retrans_list)) != NULL && 461 le->le_when == 0) { 462 d = now - le->le_ref->stamp; 463 if (d < 0) 464 d = 0; 465 else if (d > MAX_AGE) 466 d = MAX_AGE; 467 468 if (add_ls_update(buf, nbr->iface, le->le_ref->data, 469 le->le_ref->len, d) == 0) 470 break; 471 nlsa++; 472 if (le->le_oneshot) 473 ls_retrans_list_free(nbr, le); 474 else { 475 TAILQ_REMOVE(&nbr->ls_retrans_list, le, entry); 476 nbr->ls_ret_cnt--; 477 le->le_when = nbr->iface->rxmt_interval; 478 ls_retrans_list_insert(nbr, le); 479 } 480 } 481 send_ls_update(buf, nbr->iface, addr, nlsa); 482 483 done: 484 if ((le = TAILQ_FIRST(&nbr->ls_retrans_list)) != NULL) { 485 timerclear(&tv); 486 tv.tv_sec = le->le_when; 487 488 if (evtimer_add(&nbr->ls_retrans_timer, &tv) == -1) 489 fatal("ls_retrans_timer"); 490 } 491 } 492 493 LIST_HEAD(lsa_cache_head, lsa_ref); 494 495 struct lsa_cache { 496 struct lsa_cache_head *hashtbl; 497 u_int32_t hashmask; 498 } lsacache; 499 500 struct lsa_ref *lsa_cache_look(struct lsa_hdr *); 501 502 void 503 lsa_cache_init(u_int32_t hashsize) 504 { 505 u_int32_t hs, i; 506 507 for (hs = 1; hs < hashsize; hs <<= 1) 508 ; 509 lsacache.hashtbl = calloc(hs, sizeof(struct lsa_cache_head)); 510 if (lsacache.hashtbl == NULL) 511 fatal("lsa_cache_init"); 512 513 for (i = 0; i < hs; i++) 514 LIST_INIT(&lsacache.hashtbl[i]); 515 516 lsacache.hashmask = hs - 1; 517 } 518 519 struct lsa_ref * 520 lsa_cache_add(void *data, u_int16_t len) 521 { 522 struct lsa_cache_head *head; 523 struct lsa_ref *ref, *old; 524 struct timespec tp; 525 526 if ((ref = calloc(1, sizeof(*ref))) == NULL) 527 fatal("lsa_cache_add"); 528 memcpy(&ref->hdr, data, sizeof(ref->hdr)); 529 530 if ((old = lsa_cache_look(&ref->hdr))) { 531 free(ref); 532 old->refcnt++; 533 return (old); 534 } 535 536 if ((ref->data = malloc(len)) == NULL) 537 fatal("lsa_cache_add"); 538 memcpy(ref->data, data, len); 539 540 clock_gettime(CLOCK_MONOTONIC, &tp); 541 ref->stamp = tp.tv_sec; 542 ref->len = len; 543 ref->refcnt = 1; 544 545 head = &lsacache.hashtbl[hash32_buf(&ref->hdr, sizeof(ref->hdr), 546 HASHINIT) & lsacache.hashmask]; 547 LIST_INSERT_HEAD(head, ref, entry); 548 return (ref); 549 } 550 551 struct lsa_ref * 552 lsa_cache_get(struct lsa_hdr *lsa_hdr) 553 { 554 struct lsa_ref *ref; 555 556 ref = lsa_cache_look(lsa_hdr); 557 if (ref) 558 ref->refcnt++; 559 560 return (ref); 561 } 562 563 void 564 lsa_cache_put(struct lsa_ref *ref, struct nbr *nbr) 565 { 566 if (--ref->refcnt > 0) 567 return; 568 569 if (ntohs(ref->hdr.age) >= MAX_AGE) 570 ospfe_imsg_compose_rde(IMSG_LS_MAXAGE, nbr->peerid, 0, 571 ref->data, sizeof(struct lsa_hdr)); 572 573 free(ref->data); 574 LIST_REMOVE(ref, entry); 575 free(ref); 576 } 577 578 struct lsa_ref * 579 lsa_cache_look(struct lsa_hdr *lsa_hdr) 580 { 581 struct lsa_cache_head *head; 582 struct lsa_ref *ref; 583 584 head = &lsacache.hashtbl[hash32_buf(lsa_hdr, sizeof(*lsa_hdr), 585 HASHINIT) & lsacache.hashmask]; 586 587 LIST_FOREACH(ref, head, entry) { 588 if (memcmp(&ref->hdr, lsa_hdr, sizeof(*lsa_hdr)) == 0) 589 /* found match */ 590 return (ref); 591 } 592 593 return (NULL); 594 } 595