1/*	$OpenBSD: lsupdate.c,v 1.53 2023/06/21 07:44:08 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
35struct ibuf *prepare_ls_update(struct iface *);
36int	add_ls_update(struct ibuf *, struct iface *, void *, u_int16_t,
37	    u_int16_t);
38int	send_ls_update(struct ibuf *, struct iface *, struct in_addr, u_int32_t);
39
40void	ls_retrans_list_insert(struct nbr *, struct lsa_entry *);
41void	ls_retrans_list_remove(struct nbr *, struct lsa_entry *);
42
43/* link state update packet handling */
44int
45lsa_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
147struct ibuf *
148prepare_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);
165fail:
166	log_warn("prepare_ls_update");
167	ibuf_free(buf);
168	return (NULL);
169}
170
171int
172add_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
205int
206send_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);
227fail:
228	log_warn("%s", __func__);
229	ibuf_free(buf);
230	return (-1);
231}
232
233void
234recv_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 */
296void
297ls_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
325int
326ls_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
348struct lsa_entry *
349ls_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
362void
363ls_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
382void
383ls_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
412void
413ls_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
421void
422ls_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
432void
433ls_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_aton(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_aton(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
520done:
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
530LIST_HEAD(lsa_cache_head, lsa_ref);
531
532struct lsa_cache {
533	struct lsa_cache_head	*hashtbl;
534	u_int32_t		 hashmask;
535} lsacache;
536
537SIPHASH_KEY lsacachekey;
538
539struct lsa_ref		*lsa_cache_look(struct lsa_hdr *);
540
541void
542lsa_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
559static uint32_t
560lsa_hash_hdr(const struct lsa_hdr *hdr)
561{
562	return SipHash24(&lsacachekey, hdr, sizeof(*hdr));
563}
564
565struct lsa_ref *
566lsa_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
596struct lsa_ref *
597lsa_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
608void
609lsa_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
623struct lsa_ref *
624lsa_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