lsupdate.c revision 1.22 
1/*	$OpenBSD: lsupdate.c,v 1.22 2023/03/08 04:43:14 guenther 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/socket.h>
22#include <netinet/in.h>
23#include <netinet/ip6.h>
24#include <netinet/ip_ah.h>
25#include <arpa/inet.h>
26
27#include <stdlib.h>
28#include <string.h>
29#include <siphash.h>
30
31#include "ospf6.h"
32#include "ospf6d.h"
33#include "log.h"
34#include "ospfe.h"
35#include "rde.h"
36
37struct ibuf	*prepare_ls_update(struct iface *, int);
38int		 add_ls_update(struct ibuf *, struct iface *, void *, u_int16_t,
39		    u_int16_t);
40int		 send_ls_update(struct ibuf *, struct iface *, struct in6_addr,
41		    u_int32_t);
42
43void		 ls_retrans_list_insert(struct nbr *, struct lsa_entry *);
44void		 ls_retrans_list_remove(struct nbr *, struct lsa_entry *);
45
46/* link state update packet handling */
47int
48lsa_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
150struct ibuf *
151prepare_ls_update(struct iface *iface, int bigpkt)
152{
153	struct ibuf		*buf;
154	size_t			 size;
155
156	size = bigpkt ? IPV6_MAXPACKET : iface->mtu;
157	if (size < IPV6_MMTU)
158		size = IPV6_MMTU;
159	size -= sizeof(struct ip6_hdr);
160
161	/*
162	 * Reserve space for optional ah or esp encryption.  The
163	 * algorithm is taken from ah_output and esp_output, the
164	 * values are the maxima of crypto/xform.c.
165	 */
166	size -= max(
167	    /* base-ah-header replay authsize */
168	    AH_FLENGTH + sizeof(u_int32_t) + 32,
169	    /* spi sequence ivlen blocksize pad-length next-header authsize */
170	    2 * sizeof(u_int32_t) + 16 + 16 + 2 * sizeof(u_int8_t) + 32);
171
172	if ((buf = ibuf_open(size)) == NULL)
173		fatal("prepare_ls_update");
174
175	/* OSPF header */
176	if (gen_ospf_hdr(buf, iface, PACKET_TYPE_LS_UPDATE))
177		goto fail;
178
179	/* reserve space for number of lsa field */
180	if (ibuf_reserve(buf, sizeof(u_int32_t)) == NULL)
181		goto fail;
182
183	return (buf);
184fail:
185	log_warn("prepare_ls_update");
186	ibuf_free(buf);
187	return (NULL);
188}
189
190int
191add_ls_update(struct ibuf *buf, struct iface *iface, void *data, u_int16_t len,
192    u_int16_t older)
193{
194	size_t		ageoff;
195	u_int16_t	age;
196
197	if (buf->wpos + len >= buf->max)
198		return (0);
199
200	ageoff = ibuf_size(buf);
201	if (ibuf_add(buf, data, len)) {
202		log_warn("add_ls_update");
203		return (0);
204	}
205
206	/* age LSA before sending it out */
207	memcpy(&age, data, sizeof(age));
208	age = ntohs(age);
209	if ((age += older + iface->transmit_delay) >= MAX_AGE)
210		age = MAX_AGE;
211	age = htons(age);
212	memcpy(ibuf_seek(buf, ageoff, sizeof(age)), &age, sizeof(age));
213
214	return (1);
215}
216
217int
218send_ls_update(struct ibuf *buf, struct iface *iface, struct in6_addr addr,
219    u_int32_t nlsa)
220{
221	nlsa = htonl(nlsa);
222	memcpy(ibuf_seek(buf, sizeof(struct ospf_hdr), sizeof(nlsa)),
223	    &nlsa, sizeof(nlsa));
224	/* calculate checksum */
225	if (upd_ospf_hdr(buf, iface))
226		goto fail;
227
228	if (send_packet(iface, buf, &addr) == -1)
229		goto fail;
230
231	ibuf_free(buf);
232	return (0);
233fail:
234	log_warn("send_ls_update");
235	ibuf_free(buf);
236	return (-1);
237}
238
239void
240recv_ls_update(struct nbr *nbr, char *buf, u_int16_t len)
241{
242	struct lsa_hdr		 lsa;
243	u_int32_t		 nlsa;
244
245	if (len < sizeof(nlsa)) {
246		log_warnx("recv_ls_update: bad packet size, "
247		    "neighbor ID %s (%s)", inet_ntoa(nbr->id),
248		    nbr->iface->name);
249		return;
250	}
251	memcpy(&nlsa, buf, sizeof(nlsa));
252	nlsa = ntohl(nlsa);
253	buf += sizeof(nlsa);
254	len -= sizeof(nlsa);
255
256	switch (nbr->state) {
257	case NBR_STA_DOWN:
258	case NBR_STA_ATTEMPT:
259	case NBR_STA_INIT:
260	case NBR_STA_2_WAY:
261	case NBR_STA_XSTRT:
262	case NBR_STA_SNAP:
263		log_debug("recv_ls_update: packet ignored in state %s, "
264		    "neighbor ID %s (%s)", nbr_state_name(nbr->state),
265		    inet_ntoa(nbr->id), nbr->iface->name);
266		break;
267	case NBR_STA_XCHNG:
268	case NBR_STA_LOAD:
269	case NBR_STA_FULL:
270		for (; nlsa > 0 && len > 0; nlsa--) {
271			if (len < sizeof(lsa)) {
272				log_warnx("recv_ls_update: bad packet size, "
273				    "neighbor ID %s (%s)", inet_ntoa(nbr->id),
274				    nbr->iface->name);
275				return;
276			}
277			memcpy(&lsa, buf, sizeof(lsa));
278			if (len < ntohs(lsa.len)) {
279				log_warnx("recv_ls_update: bad packet size, "
280				    "neighbor ID %s (%s)", inet_ntoa(nbr->id),
281				    nbr->iface->name);
282				return;
283			}
284			ospfe_imsg_compose_rde(IMSG_LS_UPD, nbr->peerid, 0,
285			    buf, ntohs(lsa.len));
286			buf += ntohs(lsa.len);
287			len -= ntohs(lsa.len);
288		}
289		if (nlsa > 0 || len > 0) {
290			log_warnx("recv_ls_update: bad packet size, "
291			    "neighbor ID %s (%s)", inet_ntoa(nbr->id),
292			    nbr->iface->name);
293			return;
294		}
295		break;
296	default:
297		fatalx("recv_ls_update: unknown neighbor state");
298	}
299}
300
301/* link state retransmit list */
302void
303ls_retrans_list_add(struct nbr *nbr, struct lsa_hdr *lsa,
304    unsigned short timeout, unsigned short oneshot)
305{
306	struct timeval		 tv;
307	struct lsa_entry	*le;
308	struct lsa_ref		*ref;
309
310	if ((ref = lsa_cache_get(lsa)) == NULL)
311		fatalx("King Bula sez: somebody forgot to lsa_cache_add");
312
313	if ((le = calloc(1, sizeof(*le))) == NULL)
314		fatal("ls_retrans_list_add");
315
316	le->le_ref = ref;
317	le->le_when = timeout;
318	le->le_oneshot = oneshot;
319
320	ls_retrans_list_insert(nbr, le);
321
322	if (!evtimer_pending(&nbr->ls_retrans_timer, NULL)) {
323		timerclear(&tv);
324		tv.tv_sec = TAILQ_FIRST(&nbr->ls_retrans_list)->le_when;
325
326		if (evtimer_add(&nbr->ls_retrans_timer, &tv) == -1)
327			fatal("ls_retrans_list_add");
328	}
329}
330
331int
332ls_retrans_list_del(struct nbr *nbr, struct lsa_hdr *lsa_hdr)
333{
334	struct lsa_entry	*le;
335
336	if ((le = ls_retrans_list_get(nbr, lsa_hdr)) == NULL)
337		return (-1);
338	/*
339	 * Compare LSA with the Ack by comparing not only the seq_num and
340	 * checksum but also the age field.  Since we only care about MAX_AGE
341	 * vs. non-MAX_AGE LSA, a simple >= comparison is good enough.  This
342	 * ensures that a LSA withdrawal is not acked by a previous update.
343	 */
344	if (lsa_hdr->seq_num == le->le_ref->hdr.seq_num &&
345	    lsa_hdr->ls_chksum == le->le_ref->hdr.ls_chksum &&
346	    ntohs(lsa_hdr->age) >= ntohs(le->le_ref->hdr.age)) {
347		ls_retrans_list_free(nbr, le);
348		return (0);
349	}
350
351	return (-1);
352}
353
354struct lsa_entry *
355ls_retrans_list_get(struct nbr *nbr, struct lsa_hdr *lsa_hdr)
356{
357	struct lsa_entry	*le;
358
359	TAILQ_FOREACH(le, &nbr->ls_retrans_list, entry) {
360		if ((lsa_hdr->type == le->le_ref->hdr.type) &&
361		    (lsa_hdr->ls_id == le->le_ref->hdr.ls_id) &&
362		    (lsa_hdr->adv_rtr == le->le_ref->hdr.adv_rtr))
363			return (le);
364	}
365	return (NULL);
366}
367
368void
369ls_retrans_list_insert(struct nbr *nbr, struct lsa_entry *new)
370{
371	struct lsa_entry	*le;
372	unsigned short		 when = new->le_when;
373
374	TAILQ_FOREACH(le, &nbr->ls_retrans_list, entry) {
375		if (when < le->le_when) {
376			new->le_when = when;
377			TAILQ_INSERT_BEFORE(le, new, entry);
378			nbr->ls_ret_cnt++;
379			return;
380		}
381		when -= le->le_when;
382	}
383	new->le_when = when;
384	TAILQ_INSERT_TAIL(&nbr->ls_retrans_list, new, entry);
385	nbr->ls_ret_cnt++;
386}
387
388void
389ls_retrans_list_remove(struct nbr *nbr, struct lsa_entry *le)
390{
391	struct timeval		 tv;
392	struct lsa_entry	*next = TAILQ_NEXT(le, entry);
393	int			 reset = 0;
394
395	/* adjust timeout of next entry */
396	if (next)
397		next->le_when += le->le_when;
398
399	if (TAILQ_FIRST(&nbr->ls_retrans_list) == le &&
400	    evtimer_pending(&nbr->ls_retrans_timer, NULL))
401		reset = 1;
402
403	TAILQ_REMOVE(&nbr->ls_retrans_list, le, entry);
404	nbr->ls_ret_cnt--;
405
406	if (reset && TAILQ_FIRST(&nbr->ls_retrans_list)) {
407		if (evtimer_del(&nbr->ls_retrans_timer) == -1)
408			fatal("ls_retrans_list_remove");
409
410		timerclear(&tv);
411		tv.tv_sec = TAILQ_FIRST(&nbr->ls_retrans_list)->le_when;
412
413		if (evtimer_add(&nbr->ls_retrans_timer, &tv) == -1)
414			fatal("ls_retrans_list_remove");
415	}
416}
417
418void
419ls_retrans_list_free(struct nbr *nbr, struct lsa_entry *le)
420{
421	ls_retrans_list_remove(nbr, le);
422
423	lsa_cache_put(le->le_ref, nbr);
424	free(le);
425}
426
427void
428ls_retrans_list_clr(struct nbr *nbr)
429{
430	struct lsa_entry	*le;
431
432	while ((le = TAILQ_FIRST(&nbr->ls_retrans_list)) != NULL)
433		ls_retrans_list_free(nbr, le);
434
435	nbr->ls_ret_cnt = 0;
436}
437
438void
439ls_retrans_timer(int fd, short event, void *bula)
440{
441	struct timeval		 tv;
442	struct timespec		 tp;
443	struct in6_addr		 addr;
444	struct nbr		*nbr = bula;
445	struct lsa_entry	*le;
446	struct ibuf		*buf;
447	time_t			 now;
448	int			 d, bigpkt;
449	u_int32_t		 nlsa = 0;
450
451	if ((le = TAILQ_FIRST(&nbr->ls_retrans_list)) != NULL)
452		le->le_when = 0;	/* timer fired */
453	else
454		return;			/* queue empty, nothing to do */
455
456	clock_gettime(CLOCK_MONOTONIC, &tp);
457	now = tp.tv_sec;
458
459	if (nbr->iface->self == nbr) {
460		/*
461		 * oneshot needs to be set for lsa queued for flooding,
462		 * if oneshot is not set then the lsa needs to be converted
463		 * because the router switched lately to DR or BDR
464		 */
465		if (le->le_oneshot && nbr->iface->state & IF_STA_DRORBDR)
466			inet_pton(AF_INET6, AllSPFRouters, &addr);
467		else if (nbr->iface->state & IF_STA_DRORBDR) {
468			/*
469			 * old retransmission needs to be converted into
470			 * flood by rerunning the lsa_flood.
471			 */
472			lsa_flood(nbr->iface, nbr, &le->le_ref->hdr,
473			    le->le_ref->data);
474			ls_retrans_list_free(nbr, le);
475			/* ls_retrans_list_free retriggers the timer */
476			return;
477		} else if (nbr->iface->type == IF_TYPE_POINTOPOINT)
478			memcpy(&addr, &nbr->addr, sizeof(addr));
479		else
480			inet_pton(AF_INET6, AllDRouters, &addr);
481	} else
482		memcpy(&addr, &nbr->addr, sizeof(addr));
483
484	bigpkt = le->le_ref->len > 1024;
485	if ((buf = prepare_ls_update(nbr->iface, bigpkt)) == NULL) {
486		le->le_when = 1;
487		goto done;
488	}
489
490	while ((le = TAILQ_FIRST(&nbr->ls_retrans_list)) != NULL &&
491	    le->le_when == 0) {
492		d = now - le->le_ref->stamp;
493		if (d < 0)
494			d = 0;
495		else if (d > MAX_AGE)
496			d = MAX_AGE;
497
498		if (add_ls_update(buf, nbr->iface, le->le_ref->data,
499		    le->le_ref->len, d) == 0) {
500			if (nlsa == 0) {
501				/* something bad happened retry later */
502				log_warnx("ls_retrans_timer: sending LS update "
503				    "to neighbor ID %s (%s) failed",
504				    inet_ntoa(nbr->id), nbr->iface->name);
505				log_debug("ls_retrans_timer: type: %04x len: %u",
506				    ntohs(le->le_ref->hdr.type),
507				    le->le_ref->len);
508				TAILQ_REMOVE(&nbr->ls_retrans_list, le, entry);
509				nbr->ls_ret_cnt--;
510				le->le_when = nbr->iface->rxmt_interval;
511				ls_retrans_list_insert(nbr, le);
512			}
513			break;
514		}
515		nlsa++;
516		if (le->le_oneshot)
517			ls_retrans_list_free(nbr, le);
518		else {
519			TAILQ_REMOVE(&nbr->ls_retrans_list, le, entry);
520			nbr->ls_ret_cnt--;
521			le->le_when = nbr->iface->rxmt_interval;
522			ls_retrans_list_insert(nbr, le);
523		}
524	}
525	if (nlsa)
526		send_ls_update(buf, nbr->iface, addr, nlsa);
527	else
528		ibuf_free(buf);
529
530done:
531	if ((le = TAILQ_FIRST(&nbr->ls_retrans_list)) != NULL) {
532		timerclear(&tv);
533		tv.tv_sec = le->le_when;
534
535		if (evtimer_add(&nbr->ls_retrans_timer, &tv) == -1)
536			fatal("ls_retrans_timer");
537	}
538}
539
540LIST_HEAD(lsa_cache_head, lsa_ref);
541
542struct lsa_cache {
543	struct lsa_cache_head	*hashtbl;
544	u_int32_t		 hashmask;
545} lsacache;
546
547SIPHASH_KEY lsacachekey;
548
549struct lsa_ref		*lsa_cache_look(struct lsa_hdr *);
550
551void
552lsa_cache_init(u_int32_t hashsize)
553{
554	u_int32_t        hs, i;
555
556	for (hs = 1; hs < hashsize; hs <<= 1)
557		;
558	lsacache.hashtbl = calloc(hs, sizeof(struct lsa_cache_head));
559	if (lsacache.hashtbl == NULL)
560		fatal("lsa_cache_init");
561
562	for (i = 0; i < hs; i++)
563		LIST_INIT(&lsacache.hashtbl[i]);
564	arc4random_buf(&lsacachekey, sizeof(lsacachekey));
565
566	lsacache.hashmask = hs - 1;
567}
568
569static uint32_t
570lsa_hash_hdr(const struct lsa_hdr *hdr)
571{
572	return SipHash24(&lsacachekey, hdr, sizeof(*hdr));
573}
574
575struct lsa_ref *
576lsa_cache_add(void *data, u_int16_t len)
577{
578	struct lsa_cache_head	*head;
579	struct lsa_ref		*ref, *old;
580	struct timespec		 tp;
581
582	if ((ref = calloc(1, sizeof(*ref))) == NULL)
583		fatal("lsa_cache_add");
584	memcpy(&ref->hdr, data, sizeof(ref->hdr));
585
586	if ((old = lsa_cache_look(&ref->hdr))) {
587		free(ref);
588		old->refcnt++;
589		return (old);
590	}
591
592	if ((ref->data = malloc(len)) == NULL)
593		fatal("lsa_cache_add");
594	memcpy(ref->data, data, len);
595
596	clock_gettime(CLOCK_MONOTONIC, &tp);
597	ref->stamp = tp.tv_sec;
598	ref->len = len;
599	ref->refcnt = 1;
600
601	head = &lsacache.hashtbl[lsa_hash_hdr(&ref->hdr) & lsacache.hashmask];
602	LIST_INSERT_HEAD(head, ref, entry);
603	return (ref);
604}
605
606struct lsa_ref *
607lsa_cache_get(struct lsa_hdr *lsa_hdr)
608{
609	struct lsa_ref		*ref;
610
611	ref = lsa_cache_look(lsa_hdr);
612	if (ref)
613		ref->refcnt++;
614
615	return (ref);
616}
617
618void
619lsa_cache_put(struct lsa_ref *ref, struct nbr *nbr)
620{
621	if (--ref->refcnt > 0)
622		return;
623
624	if (ntohs(ref->hdr.age) >= MAX_AGE)
625		ospfe_imsg_compose_rde(IMSG_LS_MAXAGE, nbr->peerid, 0,
626		    ref->data, sizeof(struct lsa_hdr));
627
628	free(ref->data);
629	LIST_REMOVE(ref, entry);
630	free(ref);
631}
632
633struct lsa_ref *
634lsa_cache_look(struct lsa_hdr *lsa_hdr)
635{
636	struct lsa_cache_head	*head;
637	struct lsa_ref		*ref;
638
639	head = &lsacache.hashtbl[lsa_hash_hdr(lsa_hdr) & lsacache.hashmask];
640
641	LIST_FOREACH(ref, head, entry) {
642		if (memcmp(&ref->hdr, lsa_hdr, sizeof(*lsa_hdr)) == 0)
643			/* found match */
644			return (ref);
645	}
646
647	return (NULL);
648}
649