xref: /openbsd/usr.sbin/ospfd/lsupdate.c (revision e5dd7070) 
1 /*	$OpenBSD: lsupdate.c,v 1.48 2020/05/06 14:40:54 claudio 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 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 	size_t		ageoff;
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 	ageoff = ibuf_size(buf);
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(ibuf_seek(buf, ageoff, sizeof(age)), &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 
214 	nlsa = htonl(nlsa);
215 	memcpy(ibuf_seek(buf, sizeof(struct ospf_hdr), sizeof(nlsa)),
216 	    &nlsa, sizeof(nlsa));
217 	/* update authentication and calculate checksum */
218 	if (auth_gen(buf, iface))
219 		goto fail;
220 
221 	/* set destination */
222 	dst.sin_family = AF_INET;
223 	dst.sin_len = sizeof(struct sockaddr_in);
224 	dst.sin_addr.s_addr = addr.s_addr;
225 
226 	if (send_packet(iface, buf, &dst) == -1)
227 		goto fail;
228 
229 	ibuf_free(buf);
230 	return (0);
231 fail:
232 	log_warn("%s", __func__);
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 	/*
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 *
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
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
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
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
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 /* ARGSUSED */
433 void
434 ls_retrans_timer(int fd, short event, void *bula)
435 {
436 	struct timeval		 tv;
437 	struct timespec		 tp;
438 	struct in_addr		 addr;
439 	struct nbr		*nbr = bula;
440 	struct lsa_entry	*le;
441 	struct ibuf		*buf;
442 	time_t			 now;
443 	int			 d;
444 	u_int32_t		 nlsa = 0;
445 
446 	if ((le = TAILQ_FIRST(&nbr->ls_retrans_list)) != NULL)
447 		le->le_when = 0;	/* timer fired */
448 	else
449 		return;			/* queue empty, nothing to do */
450 
451 	clock_gettime(CLOCK_MONOTONIC, &tp);
452 	now = tp.tv_sec;
453 
454 	if (nbr->iface->self == nbr) {
455 		/*
456 		 * oneshot needs to be set for lsa queued for flooding,
457 		 * if oneshot is not set then the lsa needs to be converted
458 		 * because the router switched lately to DR or BDR
459 		 */
460 		if (le->le_oneshot && nbr->iface->state & IF_STA_DRORBDR)
461 			inet_aton(AllSPFRouters, &addr);
462 		else if (nbr->iface->state & IF_STA_DRORBDR) {
463 			/*
464 			 * old retransmission needs to be converted into
465 			 * flood by rerunning the lsa_flood.
466 			 */
467 			lsa_flood(nbr->iface, nbr, &le->le_ref->hdr,
468 			    le->le_ref->data);
469 			ls_retrans_list_free(nbr, le);
470 			/* ls_retrans_list_free retriggers the timer */
471 			return;
472 		} else if (nbr->iface->type == IF_TYPE_POINTOPOINT)
473 			memcpy(&addr, &nbr->addr, sizeof(addr));
474 		else
475 			inet_aton(AllDRouters, &addr);
476 	} else
477 		memcpy(&addr, &nbr->addr, sizeof(addr));
478 
479 	if ((buf = prepare_ls_update(nbr->iface)) == NULL) {
480 		le->le_when = 1;
481 		goto done;
482 	}
483 
484 	while ((le = TAILQ_FIRST(&nbr->ls_retrans_list)) != NULL &&
485 	    le->le_when == 0) {
486 		d = now - le->le_ref->stamp;
487 		if (d < 0)
488 			d = 0;
489 		else if (d > MAX_AGE)
490 			d = MAX_AGE;
491 
492 		if (add_ls_update(buf, nbr->iface, le->le_ref->data,
493 		    le->le_ref->len, d) == 0) {
494 			if (nlsa == 0) {
495 				/* something bad happened retry later */
496 				log_warnx("ls_retrans_timer: sending LS update "
497 				    "to neighbor ID %s failed",
498 				    inet_ntoa(nbr->id));
499 				TAILQ_REMOVE(&nbr->ls_retrans_list, le, entry);
500 				nbr->ls_ret_cnt--;
501 				le->le_when = nbr->iface->rxmt_interval;
502 				ls_retrans_list_insert(nbr, le);
503 			}
504 			break;
505 		}
506 		nlsa++;
507 		if (le->le_oneshot)
508 			ls_retrans_list_free(nbr, le);
509 		else {
510 			TAILQ_REMOVE(&nbr->ls_retrans_list, le, entry);
511 			nbr->ls_ret_cnt--;
512 			le->le_when = nbr->iface->rxmt_interval;
513 			ls_retrans_list_insert(nbr, le);
514 		}
515 	}
516 	if (nlsa)
517 		send_ls_update(buf, nbr->iface, addr, nlsa);
518 	else
519 		ibuf_free(buf);
520 
521 done:
522 	if ((le = TAILQ_FIRST(&nbr->ls_retrans_list)) != NULL) {
523 		timerclear(&tv);
524 		tv.tv_sec = le->le_when;
525 
526 		if (evtimer_add(&nbr->ls_retrans_timer, &tv) == -1)
527 			fatal("ls_retrans_timer");
528 	}
529 }
530 
531 LIST_HEAD(lsa_cache_head, lsa_ref);
532 
533 struct lsa_cache {
534 	struct lsa_cache_head	*hashtbl;
535 	u_int32_t		 hashmask;
536 } lsacache;
537 
538 SIPHASH_KEY lsacachekey;
539 
540 struct lsa_ref		*lsa_cache_look(struct lsa_hdr *);
541 
542 void
543 lsa_cache_init(u_int32_t hashsize)
544 {
545 	u_int32_t        hs, i;
546 
547 	for (hs = 1; hs < hashsize; hs <<= 1)
548 		;
549 	lsacache.hashtbl = calloc(hs, sizeof(struct lsa_cache_head));
550 	if (lsacache.hashtbl == NULL)
551 		fatal("lsa_cache_init");
552 
553 	for (i = 0; i < hs; i++)
554 		LIST_INIT(&lsacache.hashtbl[i]);
555 	arc4random_buf(&lsacachekey, sizeof(lsacachekey));
556 
557 	lsacache.hashmask = hs - 1;
558 }
559 
560 static uint32_t
561 lsa_hash_hdr(const struct lsa_hdr *hdr)
562 {
563 	return SipHash24(&lsacachekey, hdr, sizeof(*hdr));
564 }
565 
566 struct lsa_ref *
567 lsa_cache_add(void *data, u_int16_t len)
568 {
569 	struct lsa_cache_head	*head;
570 	struct lsa_ref		*ref, *old;
571 	struct timespec		 tp;
572 
573 	if ((ref = calloc(1, sizeof(*ref))) == NULL)
574 		fatal("lsa_cache_add");
575 	memcpy(&ref->hdr, data, sizeof(ref->hdr));
576 
577 	if ((old = lsa_cache_look(&ref->hdr))) {
578 		free(ref);
579 		old->refcnt++;
580 		return (old);
581 	}
582 
583 	if ((ref->data = malloc(len)) == NULL)
584 		fatal("lsa_cache_add");
585 	memcpy(ref->data, data, len);
586 
587 	clock_gettime(CLOCK_MONOTONIC, &tp);
588 	ref->stamp = tp.tv_sec;
589 	ref->len = len;
590 	ref->refcnt = 1;
591 
592 	head = &lsacache.hashtbl[lsa_hash_hdr(&ref->hdr) & lsacache.hashmask];
593 	LIST_INSERT_HEAD(head, ref, entry);
594 	return (ref);
595 }
596 
597 struct lsa_ref *
598 lsa_cache_get(struct lsa_hdr *lsa_hdr)
599 {
600 	struct lsa_ref		*ref;
601 
602 	ref = lsa_cache_look(lsa_hdr);
603 	if (ref)
604 		ref->refcnt++;
605 
606 	return (ref);
607 }
608 
609 void
610 lsa_cache_put(struct lsa_ref *ref, struct nbr *nbr)
611 {
612 	if (--ref->refcnt > 0)
613 		return;
614 
615 	if (ntohs(ref->hdr.age) >= MAX_AGE)
616 		ospfe_imsg_compose_rde(IMSG_LS_MAXAGE, nbr->peerid, 0,
617 		    ref->data, sizeof(struct lsa_hdr));
618 
619 	free(ref->data);
620 	LIST_REMOVE(ref, entry);
621 	free(ref);
622 }
623 
624 struct lsa_ref *
625 lsa_cache_look(struct lsa_hdr *lsa_hdr)
626 {
627 	struct lsa_cache_head	*head;
628 	struct lsa_ref		*ref;
629 
630 	head = &lsacache.hashtbl[lsa_hash_hdr(lsa_hdr) & lsacache.hashmask];
631 
632 	LIST_FOREACH(ref, head, entry) {
633 		if (memcmp(&ref->hdr, lsa_hdr, sizeof(*lsa_hdr)) == 0)
634 			/* found match */
635 			return (ref);
636 	}
637 
638 	return (NULL);
639 }
640