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
lsa_flood(struct iface * iface,struct nbr * originator,struct lsa_hdr * lsa_hdr,void * data)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 *
prepare_ls_update(struct iface * iface)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
add_ls_update(struct ibuf * buf,struct iface * iface,void * data,u_int16_t len,u_int16_t older)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
send_ls_update(struct ibuf * buf,struct iface * iface,struct in_addr addr,u_int32_t nlsa)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
recv_ls_update(struct nbr * nbr,char * buf,u_int16_t len)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
ls_retrans_list_add(struct nbr * nbr,struct lsa_hdr * lsa,unsigned short timeout,unsigned short oneshot)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
ls_retrans_list_del(struct nbr * nbr,struct lsa_hdr * lsa_hdr)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 *
ls_retrans_list_get(struct nbr * nbr,struct lsa_hdr * lsa_hdr)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
ls_retrans_list_insert(struct nbr * nbr,struct lsa_entry * new)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
ls_retrans_list_remove(struct nbr * nbr,struct lsa_entry * le)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
ls_retrans_list_free(struct nbr * nbr,struct lsa_entry * le)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
ls_retrans_list_clr(struct nbr * nbr)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
ls_retrans_timer(int fd,short event,void * bula)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
lsa_cache_init(u_int32_t hashsize)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
lsa_hash_hdr(const struct lsa_hdr * hdr)560 lsa_hash_hdr(const struct lsa_hdr *hdr)
561 {
562 return SipHash24(&lsacachekey, hdr, sizeof(*hdr));
563 }
564
565 struct lsa_ref *
lsa_cache_add(void * data,u_int16_t len)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 *
lsa_cache_get(struct lsa_hdr * lsa_hdr)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
lsa_cache_put(struct lsa_ref * ref,struct nbr * nbr)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 *
lsa_cache_look(struct lsa_hdr * lsa_hdr)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