xref: /openbsd-src/usr.sbin/ospf6d/lsupdate.c (revision bf2cf3053df3551d6121df7fcab39bf211c112b2)
1*bf2cf305Sclaudio /*	$OpenBSD: lsupdate.c,v 1.24 2023/07/03 09:51:38 claudio Exp $ */
2a1a4e97bSnorby 
3a1a4e97bSnorby /*
4a1a4e97bSnorby  * Copyright (c) 2005 Claudio Jeker <claudio@openbsd.org>
5a1a4e97bSnorby  * Copyright (c) 2004, 2005, 2007 Esben Norby <norby@openbsd.org>
6a1a4e97bSnorby  *
7a1a4e97bSnorby  * Permission to use, copy, modify, and distribute this software for any
8a1a4e97bSnorby  * purpose with or without fee is hereby granted, provided that the above
9a1a4e97bSnorby  * copyright notice and this permission notice appear in all copies.
10a1a4e97bSnorby  *
11a1a4e97bSnorby  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
12a1a4e97bSnorby  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
13a1a4e97bSnorby  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
14a1a4e97bSnorby  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
15a1a4e97bSnorby  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
16a1a4e97bSnorby  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
17a1a4e97bSnorby  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
18a1a4e97bSnorby  */
19a1a4e97bSnorby 
20a1a4e97bSnorby #include <sys/types.h>
21a1a4e97bSnorby #include <sys/socket.h>
22a1a4e97bSnorby #include <netinet/in.h>
23c5a4485cSbluhm #include <netinet/ip6.h>
24c5a4485cSbluhm #include <netinet/ip_ah.h>
25a1a4e97bSnorby #include <arpa/inet.h>
26a1a4e97bSnorby 
27a1a4e97bSnorby #include <stdlib.h>
28a1a4e97bSnorby #include <string.h>
295bc82be2Stedu #include <siphash.h>
30a1a4e97bSnorby 
31a1a4e97bSnorby #include "ospf6.h"
32a1a4e97bSnorby #include "ospf6d.h"
33a1a4e97bSnorby #include "log.h"
34a1a4e97bSnorby #include "ospfe.h"
35a1a4e97bSnorby #include "rde.h"
36a1a4e97bSnorby 
370e9e9781Sdenis struct ibuf	*prepare_ls_update(struct iface *, int);
380a137951Sdenis int		 add_ls_update(struct ibuf *, struct iface *, void *, u_int16_t,
390a137951Sdenis 		    u_int16_t);
400a137951Sdenis int		 send_ls_update(struct ibuf *, struct iface *, struct in6_addr,
410a137951Sdenis 		    u_int32_t);
42a1a4e97bSnorby 
43a1a4e97bSnorby void		 ls_retrans_list_insert(struct nbr *, struct lsa_entry *);
44a1a4e97bSnorby void		 ls_retrans_list_remove(struct nbr *, struct lsa_entry *);
45a1a4e97bSnorby 
46a1a4e97bSnorby /* link state update packet handling */
47a1a4e97bSnorby int
lsa_flood(struct iface * iface,struct nbr * originator,struct lsa_hdr * lsa_hdr,void * data)48a1a4e97bSnorby lsa_flood(struct iface *iface, struct nbr *originator, struct lsa_hdr *lsa_hdr,
49a1a4e97bSnorby     void *data)
50a1a4e97bSnorby {
51a1a4e97bSnorby 	struct nbr		*nbr;
52a1a4e97bSnorby 	struct lsa_entry	*le = NULL;
53a1a4e97bSnorby 	int			 queued = 0, dont_ack = 0;
54a1a4e97bSnorby 	int			 r;
55a1a4e97bSnorby 
56a1a4e97bSnorby 	LIST_FOREACH(nbr, &iface->nbr_list, entry) {
57a1a4e97bSnorby 		if (nbr == iface->self)
58a1a4e97bSnorby 			continue;
59a1a4e97bSnorby 		if (!(nbr->state & NBR_STA_FLOOD))
60a1a4e97bSnorby 			continue;
61a1a4e97bSnorby 
62a1a4e97bSnorby 		if (iface->state & IF_STA_DROTHER && !queued)
63a1a4e97bSnorby 			while ((le = ls_retrans_list_get(iface->self, lsa_hdr)))
64a1a4e97bSnorby 			    ls_retrans_list_free(iface->self, le);
65a1a4e97bSnorby 
66a1a4e97bSnorby 		while ((le = ls_retrans_list_get(nbr, lsa_hdr)))
67a1a4e97bSnorby 			ls_retrans_list_free(nbr, le);
68a1a4e97bSnorby 
69a1a4e97bSnorby 		if (!(nbr->state & NBR_STA_FULL) &&
70a1a4e97bSnorby 		    (le = ls_req_list_get(nbr, lsa_hdr)) != NULL) {
71a1a4e97bSnorby 			r = lsa_newer(lsa_hdr, le->le_lsa);
72a1a4e97bSnorby 			if (r > 0) {
73a1a4e97bSnorby 				/* to flood LSA is newer than requested */
74a1a4e97bSnorby 				ls_req_list_free(nbr, le);
75a1a4e97bSnorby 				/* new needs to be flooded */
76a1a4e97bSnorby 			} else if (r < 0) {
77a1a4e97bSnorby 				/* to flood LSA is older than requested */
78a1a4e97bSnorby 				continue;
79a1a4e97bSnorby 			} else {
80a1a4e97bSnorby 				/* LSA are equal */
81a1a4e97bSnorby 				ls_req_list_free(nbr, le);
82a1a4e97bSnorby 				continue;
83a1a4e97bSnorby 			}
84a1a4e97bSnorby 		}
85a1a4e97bSnorby 
86a1a4e97bSnorby 		if (nbr == originator) {
87a1a4e97bSnorby 			dont_ack++;
88a1a4e97bSnorby 			continue;
89a1a4e97bSnorby 		}
90a1a4e97bSnorby 
91a1a4e97bSnorby 		/* non DR or BDR router keep all lsa in one retrans list */
92a1a4e97bSnorby 		if (iface->state & IF_STA_DROTHER) {
93a1a4e97bSnorby 			if (!queued)
94a1a4e97bSnorby 				ls_retrans_list_add(iface->self, data,
95a1a4e97bSnorby 				    iface->rxmt_interval, 0);
96a1a4e97bSnorby 			queued = 1;
97a1a4e97bSnorby 		} else {
98a1a4e97bSnorby 			ls_retrans_list_add(nbr, data, iface->rxmt_interval, 0);
99a1a4e97bSnorby 			queued = 1;
100a1a4e97bSnorby 		}
101a1a4e97bSnorby 	}
102a1a4e97bSnorby 
103a1a4e97bSnorby 	if (!queued)
104a1a4e97bSnorby 		return (0);
105a1a4e97bSnorby 
106a1a4e97bSnorby 	if (iface == originator->iface && iface->self != originator) {
107a1a4e97bSnorby 		if (iface->dr == originator || iface->bdr == originator)
108a1a4e97bSnorby 			return (0);
109a1a4e97bSnorby 		if (iface->state & IF_STA_BACKUP)
110a1a4e97bSnorby 			return (0);
111a1a4e97bSnorby 		dont_ack++;
112a1a4e97bSnorby 	}
113a1a4e97bSnorby 
114a1a4e97bSnorby 	/*
115a1a4e97bSnorby 	 * initial flood needs to be queued separately, timeout is zero
116a1a4e97bSnorby 	 * and oneshot has to be set because the retransimssion queues
117a1a4e97bSnorby 	 * are already loaded.
118a1a4e97bSnorby 	 */
119a1a4e97bSnorby 	switch (iface->type) {
120a1a4e97bSnorby 	case IF_TYPE_POINTOPOINT:
121a1a4e97bSnorby 	case IF_TYPE_BROADCAST:
122a1a4e97bSnorby 		ls_retrans_list_add(iface->self, data, 0, 1);
123a1a4e97bSnorby 		break;
124a1a4e97bSnorby 	case IF_TYPE_NBMA:
125a1a4e97bSnorby 	case IF_TYPE_POINTOMULTIPOINT:
126a1a4e97bSnorby 	case IF_TYPE_VIRTUALLINK:
127a1a4e97bSnorby 		LIST_FOREACH(nbr, &iface->nbr_list, entry) {
128a1a4e97bSnorby 			if (nbr == iface->self)
129a1a4e97bSnorby 				continue;
130a1a4e97bSnorby 			if (!(nbr->state & NBR_STA_FLOOD))
131a1a4e97bSnorby 				continue;
132a1a4e97bSnorby 			if (!TAILQ_EMPTY(&nbr->ls_retrans_list)) {
133a1a4e97bSnorby 				le = TAILQ_LAST(&nbr->ls_retrans_list,
134a1a4e97bSnorby 				    lsa_head);
135a1a4e97bSnorby 				if (lsa_hdr->type != le->le_lsa->type ||
136a1a4e97bSnorby 				    lsa_hdr->ls_id != le->le_lsa->ls_id ||
137a1a4e97bSnorby 				    lsa_hdr->adv_rtr != le->le_lsa->adv_rtr)
138a1a4e97bSnorby 					continue;
139a1a4e97bSnorby 			}
140a1a4e97bSnorby 			ls_retrans_list_add(nbr, data, 0, 1);
141a1a4e97bSnorby 		}
142a1a4e97bSnorby 		break;
143a1a4e97bSnorby 	default:
144a1a4e97bSnorby 		fatalx("lsa_flood: unknown interface type");
145a1a4e97bSnorby 	}
146a1a4e97bSnorby 
147a1a4e97bSnorby 	return (dont_ack == 2);
148a1a4e97bSnorby }
149a1a4e97bSnorby 
150e39620e5Snicm struct ibuf *
prepare_ls_update(struct iface * iface,int bigpkt)1510e9e9781Sdenis prepare_ls_update(struct iface *iface, int bigpkt)
152a1a4e97bSnorby {
153e39620e5Snicm 	struct ibuf		*buf;
1540e9e9781Sdenis 	size_t			 size;
1550e9e9781Sdenis 
1560e9e9781Sdenis 	size = bigpkt ? IPV6_MAXPACKET : iface->mtu;
1570e9e9781Sdenis 	if (size < IPV6_MMTU)
1580e9e9781Sdenis 		size = IPV6_MMTU;
1590e9e9781Sdenis 	size -= sizeof(struct ip6_hdr);
160a1a4e97bSnorby 
161c5a4485cSbluhm 	/*
162c5a4485cSbluhm 	 * Reserve space for optional ah or esp encryption.  The
163c5a4485cSbluhm 	 * algorithm is taken from ah_output and esp_output, the
164c5a4485cSbluhm 	 * values are the maxima of crypto/xform.c.
165c5a4485cSbluhm 	 */
1660e9e9781Sdenis 	size -= max(
167c5a4485cSbluhm 	    /* base-ah-header replay authsize */
168c5a4485cSbluhm 	    AH_FLENGTH + sizeof(u_int32_t) + 32,
169c5a4485cSbluhm 	    /* spi sequence ivlen blocksize pad-length next-header authsize */
170c5a4485cSbluhm 	    2 * sizeof(u_int32_t) + 16 + 16 + 2 * sizeof(u_int8_t) + 32);
171c5a4485cSbluhm 
1720e9e9781Sdenis 	if ((buf = ibuf_open(size)) == NULL)
1733af4e127Snorby 		fatal("prepare_ls_update");
174a1a4e97bSnorby 
175a1a4e97bSnorby 	/* OSPF header */
176a1a4e97bSnorby 	if (gen_ospf_hdr(buf, iface, PACKET_TYPE_LS_UPDATE))
177a1a4e97bSnorby 		goto fail;
178a1a4e97bSnorby 
179a1a4e97bSnorby 	/* reserve space for number of lsa field */
180297c3ba2Sclaudio 	if (ibuf_add_zero(buf, sizeof(u_int32_t)) == -1)
181a1a4e97bSnorby 		goto fail;
182a1a4e97bSnorby 
183a1a4e97bSnorby 	return (buf);
184a1a4e97bSnorby fail:
185a1a4e97bSnorby 	log_warn("prepare_ls_update");
186e39620e5Snicm 	ibuf_free(buf);
187a1a4e97bSnorby 	return (NULL);
188a1a4e97bSnorby }
189a1a4e97bSnorby 
190a1a4e97bSnorby int
add_ls_update(struct ibuf * buf,struct iface * iface,void * data,u_int16_t len,u_int16_t older)1910a137951Sdenis add_ls_update(struct ibuf *buf, struct iface *iface, void *data, u_int16_t len,
192a1a4e97bSnorby     u_int16_t older)
193a1a4e97bSnorby {
19420d59b60Sclaudio 	size_t		ageoff;
195a1a4e97bSnorby 	u_int16_t	age;
196a1a4e97bSnorby 
197*bf2cf305Sclaudio 	if (len >= ibuf_left(buf))
198a1a4e97bSnorby 		return (0);
199a1a4e97bSnorby 
20020d59b60Sclaudio 	ageoff = ibuf_size(buf);
201e39620e5Snicm 	if (ibuf_add(buf, data, len)) {
202a1a4e97bSnorby 		log_warn("add_ls_update");
203a1a4e97bSnorby 		return (0);
204a1a4e97bSnorby 	}
205a1a4e97bSnorby 
206a1a4e97bSnorby 	/* age LSA before sending it out */
207a1a4e97bSnorby 	memcpy(&age, data, sizeof(age));
208a1a4e97bSnorby 	age = ntohs(age);
209a1a4e97bSnorby 	if ((age += older + iface->transmit_delay) >= MAX_AGE)
210a1a4e97bSnorby 		age = MAX_AGE;
211297c3ba2Sclaudio 	if (ibuf_set_n16(buf, ageoff, age) == -1) {
212297c3ba2Sclaudio 		log_warn("add_ls_update");
213297c3ba2Sclaudio 		return (0);
214297c3ba2Sclaudio 	}
215a1a4e97bSnorby 
216a1a4e97bSnorby 	return (1);
217a1a4e97bSnorby }
218a1a4e97bSnorby 
219a1a4e97bSnorby int
send_ls_update(struct ibuf * buf,struct iface * iface,struct in6_addr addr,u_int32_t nlsa)220e39620e5Snicm send_ls_update(struct ibuf *buf, struct iface *iface, struct in6_addr addr,
221a1a4e97bSnorby     u_int32_t nlsa)
222a1a4e97bSnorby {
223297c3ba2Sclaudio 	if (ibuf_set_n32(buf, sizeof(struct ospf_hdr), nlsa) == -1)
224297c3ba2Sclaudio 		goto fail;
225a1a4e97bSnorby 	/* calculate checksum */
226a1a4e97bSnorby 	if (upd_ospf_hdr(buf, iface))
227a1a4e97bSnorby 		goto fail;
228a1a4e97bSnorby 
2290a137951Sdenis 	if (send_packet(iface, buf, &addr) == -1)
2300a137951Sdenis 		goto fail;
231a1a4e97bSnorby 
232e39620e5Snicm 	ibuf_free(buf);
2330a137951Sdenis 	return (0);
234a1a4e97bSnorby fail:
235a1a4e97bSnorby 	log_warn("send_ls_update");
236e39620e5Snicm 	ibuf_free(buf);
237a1a4e97bSnorby 	return (-1);
238a1a4e97bSnorby }
239a1a4e97bSnorby 
240a1a4e97bSnorby void
recv_ls_update(struct nbr * nbr,char * buf,u_int16_t len)241a1a4e97bSnorby recv_ls_update(struct nbr *nbr, char *buf, u_int16_t len)
242a1a4e97bSnorby {
243a1a4e97bSnorby 	struct lsa_hdr		 lsa;
244a1a4e97bSnorby 	u_int32_t		 nlsa;
245a1a4e97bSnorby 
246a1a4e97bSnorby 	if (len < sizeof(nlsa)) {
2479cc19ef1Ssthen 		log_warnx("recv_ls_update: bad packet size, "
2489cc19ef1Ssthen 		    "neighbor ID %s (%s)", inet_ntoa(nbr->id),
2499cc19ef1Ssthen 		    nbr->iface->name);
250a1a4e97bSnorby 		return;
251a1a4e97bSnorby 	}
252a1a4e97bSnorby 	memcpy(&nlsa, buf, sizeof(nlsa));
253a1a4e97bSnorby 	nlsa = ntohl(nlsa);
254a1a4e97bSnorby 	buf += sizeof(nlsa);
255a1a4e97bSnorby 	len -= sizeof(nlsa);
256a1a4e97bSnorby 
257a1a4e97bSnorby 	switch (nbr->state) {
258a1a4e97bSnorby 	case NBR_STA_DOWN:
259a1a4e97bSnorby 	case NBR_STA_ATTEMPT:
260a1a4e97bSnorby 	case NBR_STA_INIT:
261a1a4e97bSnorby 	case NBR_STA_2_WAY:
262a1a4e97bSnorby 	case NBR_STA_XSTRT:
263a1a4e97bSnorby 	case NBR_STA_SNAP:
264a1a4e97bSnorby 		log_debug("recv_ls_update: packet ignored in state %s, "
2659cc19ef1Ssthen 		    "neighbor ID %s (%s)", nbr_state_name(nbr->state),
2669cc19ef1Ssthen 		    inet_ntoa(nbr->id), nbr->iface->name);
267a1a4e97bSnorby 		break;
268a1a4e97bSnorby 	case NBR_STA_XCHNG:
269a1a4e97bSnorby 	case NBR_STA_LOAD:
270a1a4e97bSnorby 	case NBR_STA_FULL:
271a1a4e97bSnorby 		for (; nlsa > 0 && len > 0; nlsa--) {
272a1a4e97bSnorby 			if (len < sizeof(lsa)) {
273a1a4e97bSnorby 				log_warnx("recv_ls_update: bad packet size, "
2749cc19ef1Ssthen 				    "neighbor ID %s (%s)", inet_ntoa(nbr->id),
2759cc19ef1Ssthen 				    nbr->iface->name);
276a1a4e97bSnorby 				return;
277a1a4e97bSnorby 			}
278a1a4e97bSnorby 			memcpy(&lsa, buf, sizeof(lsa));
279a1a4e97bSnorby 			if (len < ntohs(lsa.len)) {
280a1a4e97bSnorby 				log_warnx("recv_ls_update: bad packet size, "
2819cc19ef1Ssthen 				    "neighbor ID %s (%s)", inet_ntoa(nbr->id),
2829cc19ef1Ssthen 				    nbr->iface->name);
283a1a4e97bSnorby 				return;
284a1a4e97bSnorby 			}
285980c654eSclaudio 			ospfe_imsg_compose_rde(IMSG_LS_UPD, nbr->peerid, 0,
286980c654eSclaudio 			    buf, ntohs(lsa.len));
287a1a4e97bSnorby 			buf += ntohs(lsa.len);
288a1a4e97bSnorby 			len -= ntohs(lsa.len);
289a1a4e97bSnorby 		}
290a1a4e97bSnorby 		if (nlsa > 0 || len > 0) {
291a1a4e97bSnorby 			log_warnx("recv_ls_update: bad packet size, "
2929cc19ef1Ssthen 			    "neighbor ID %s (%s)", inet_ntoa(nbr->id),
2939cc19ef1Ssthen 			    nbr->iface->name);
294a1a4e97bSnorby 			return;
295a1a4e97bSnorby 		}
296a1a4e97bSnorby 		break;
297a1a4e97bSnorby 	default:
298a1a4e97bSnorby 		fatalx("recv_ls_update: unknown neighbor state");
299a1a4e97bSnorby 	}
300a1a4e97bSnorby }
301a1a4e97bSnorby 
302a1a4e97bSnorby /* link state retransmit list */
303a1a4e97bSnorby void
ls_retrans_list_add(struct nbr * nbr,struct lsa_hdr * lsa,unsigned short timeout,unsigned short oneshot)304a1a4e97bSnorby ls_retrans_list_add(struct nbr *nbr, struct lsa_hdr *lsa,
305a1a4e97bSnorby     unsigned short timeout, unsigned short oneshot)
306a1a4e97bSnorby {
307a1a4e97bSnorby 	struct timeval		 tv;
308a1a4e97bSnorby 	struct lsa_entry	*le;
309a1a4e97bSnorby 	struct lsa_ref		*ref;
310a1a4e97bSnorby 
311a1a4e97bSnorby 	if ((ref = lsa_cache_get(lsa)) == NULL)
312a1a4e97bSnorby 		fatalx("King Bula sez: somebody forgot to lsa_cache_add");
313a1a4e97bSnorby 
314a1a4e97bSnorby 	if ((le = calloc(1, sizeof(*le))) == NULL)
315a1a4e97bSnorby 		fatal("ls_retrans_list_add");
316a1a4e97bSnorby 
317a1a4e97bSnorby 	le->le_ref = ref;
318a1a4e97bSnorby 	le->le_when = timeout;
319a1a4e97bSnorby 	le->le_oneshot = oneshot;
320a1a4e97bSnorby 
321a1a4e97bSnorby 	ls_retrans_list_insert(nbr, le);
322a1a4e97bSnorby 
323a1a4e97bSnorby 	if (!evtimer_pending(&nbr->ls_retrans_timer, NULL)) {
324a1a4e97bSnorby 		timerclear(&tv);
325a1a4e97bSnorby 		tv.tv_sec = TAILQ_FIRST(&nbr->ls_retrans_list)->le_when;
326a1a4e97bSnorby 
327a1a4e97bSnorby 		if (evtimer_add(&nbr->ls_retrans_timer, &tv) == -1)
328a1a4e97bSnorby 			fatal("ls_retrans_list_add");
329a1a4e97bSnorby 	}
330a1a4e97bSnorby }
331a1a4e97bSnorby 
332a1a4e97bSnorby int
ls_retrans_list_del(struct nbr * nbr,struct lsa_hdr * lsa_hdr)333a1a4e97bSnorby ls_retrans_list_del(struct nbr *nbr, struct lsa_hdr *lsa_hdr)
334a1a4e97bSnorby {
335a1a4e97bSnorby 	struct lsa_entry	*le;
336a1a4e97bSnorby 
337a1a4e97bSnorby 	if ((le = ls_retrans_list_get(nbr, lsa_hdr)) == NULL)
338a1a4e97bSnorby 		return (-1);
3398e73b4e2Sbluhm 	/*
3408e73b4e2Sbluhm 	 * Compare LSA with the Ack by comparing not only the seq_num and
3418e73b4e2Sbluhm 	 * checksum but also the age field.  Since we only care about MAX_AGE
3428e73b4e2Sbluhm 	 * vs. non-MAX_AGE LSA, a simple >= comparison is good enough.  This
3438e73b4e2Sbluhm 	 * ensures that a LSA withdrawal is not acked by a previous update.
3448e73b4e2Sbluhm 	 */
345a1a4e97bSnorby 	if (lsa_hdr->seq_num == le->le_ref->hdr.seq_num &&
3468e73b4e2Sbluhm 	    lsa_hdr->ls_chksum == le->le_ref->hdr.ls_chksum &&
3478e73b4e2Sbluhm 	    ntohs(lsa_hdr->age) >= ntohs(le->le_ref->hdr.age)) {
348a1a4e97bSnorby 		ls_retrans_list_free(nbr, le);
349a1a4e97bSnorby 		return (0);
350a1a4e97bSnorby 	}
351a1a4e97bSnorby 
352a1a4e97bSnorby 	return (-1);
353a1a4e97bSnorby }
354a1a4e97bSnorby 
355a1a4e97bSnorby struct lsa_entry *
ls_retrans_list_get(struct nbr * nbr,struct lsa_hdr * lsa_hdr)356a1a4e97bSnorby ls_retrans_list_get(struct nbr *nbr, struct lsa_hdr *lsa_hdr)
357a1a4e97bSnorby {
358a1a4e97bSnorby 	struct lsa_entry	*le;
359a1a4e97bSnorby 
360a1a4e97bSnorby 	TAILQ_FOREACH(le, &nbr->ls_retrans_list, entry) {
361a1a4e97bSnorby 		if ((lsa_hdr->type == le->le_ref->hdr.type) &&
362a1a4e97bSnorby 		    (lsa_hdr->ls_id == le->le_ref->hdr.ls_id) &&
363a1a4e97bSnorby 		    (lsa_hdr->adv_rtr == le->le_ref->hdr.adv_rtr))
364a1a4e97bSnorby 			return (le);
365a1a4e97bSnorby 	}
366a1a4e97bSnorby 	return (NULL);
367a1a4e97bSnorby }
368a1a4e97bSnorby 
369a1a4e97bSnorby void
ls_retrans_list_insert(struct nbr * nbr,struct lsa_entry * new)370a1a4e97bSnorby ls_retrans_list_insert(struct nbr *nbr, struct lsa_entry *new)
371a1a4e97bSnorby {
372a1a4e97bSnorby 	struct lsa_entry	*le;
373a1a4e97bSnorby 	unsigned short		 when = new->le_when;
374a1a4e97bSnorby 
375a1a4e97bSnorby 	TAILQ_FOREACH(le, &nbr->ls_retrans_list, entry) {
376a1a4e97bSnorby 		if (when < le->le_when) {
377a1a4e97bSnorby 			new->le_when = when;
378a1a4e97bSnorby 			TAILQ_INSERT_BEFORE(le, new, entry);
379a1a4e97bSnorby 			nbr->ls_ret_cnt++;
380a1a4e97bSnorby 			return;
381a1a4e97bSnorby 		}
382a1a4e97bSnorby 		when -= le->le_when;
383a1a4e97bSnorby 	}
384a1a4e97bSnorby 	new->le_when = when;
385a1a4e97bSnorby 	TAILQ_INSERT_TAIL(&nbr->ls_retrans_list, new, entry);
386a1a4e97bSnorby 	nbr->ls_ret_cnt++;
387a1a4e97bSnorby }
388a1a4e97bSnorby 
389a1a4e97bSnorby void
ls_retrans_list_remove(struct nbr * nbr,struct lsa_entry * le)390a1a4e97bSnorby ls_retrans_list_remove(struct nbr *nbr, struct lsa_entry *le)
391a1a4e97bSnorby {
392a1a4e97bSnorby 	struct timeval		 tv;
393a1a4e97bSnorby 	struct lsa_entry	*next = TAILQ_NEXT(le, entry);
394a1a4e97bSnorby 	int			 reset = 0;
395a1a4e97bSnorby 
396a1a4e97bSnorby 	/* adjust timeout of next entry */
397a1a4e97bSnorby 	if (next)
398a1a4e97bSnorby 		next->le_when += le->le_when;
399a1a4e97bSnorby 
400a1a4e97bSnorby 	if (TAILQ_FIRST(&nbr->ls_retrans_list) == le &&
401a1a4e97bSnorby 	    evtimer_pending(&nbr->ls_retrans_timer, NULL))
402a1a4e97bSnorby 		reset = 1;
403a1a4e97bSnorby 
404a1a4e97bSnorby 	TAILQ_REMOVE(&nbr->ls_retrans_list, le, entry);
405a1a4e97bSnorby 	nbr->ls_ret_cnt--;
406a1a4e97bSnorby 
407a1a4e97bSnorby 	if (reset && TAILQ_FIRST(&nbr->ls_retrans_list)) {
408a1a4e97bSnorby 		if (evtimer_del(&nbr->ls_retrans_timer) == -1)
409a1a4e97bSnorby 			fatal("ls_retrans_list_remove");
410a1a4e97bSnorby 
411a1a4e97bSnorby 		timerclear(&tv);
412a1a4e97bSnorby 		tv.tv_sec = TAILQ_FIRST(&nbr->ls_retrans_list)->le_when;
413a1a4e97bSnorby 
414a1a4e97bSnorby 		if (evtimer_add(&nbr->ls_retrans_timer, &tv) == -1)
415a1a4e97bSnorby 			fatal("ls_retrans_list_remove");
416a1a4e97bSnorby 	}
417a1a4e97bSnorby }
418a1a4e97bSnorby 
419a1a4e97bSnorby void
ls_retrans_list_free(struct nbr * nbr,struct lsa_entry * le)420a1a4e97bSnorby ls_retrans_list_free(struct nbr *nbr, struct lsa_entry *le)
421a1a4e97bSnorby {
422a1a4e97bSnorby 	ls_retrans_list_remove(nbr, le);
423a1a4e97bSnorby 
424a1a4e97bSnorby 	lsa_cache_put(le->le_ref, nbr);
425a1a4e97bSnorby 	free(le);
426a1a4e97bSnorby }
427a1a4e97bSnorby 
428a1a4e97bSnorby void
ls_retrans_list_clr(struct nbr * nbr)429a1a4e97bSnorby ls_retrans_list_clr(struct nbr *nbr)
430a1a4e97bSnorby {
431a1a4e97bSnorby 	struct lsa_entry	*le;
432a1a4e97bSnorby 
433a1a4e97bSnorby 	while ((le = TAILQ_FIRST(&nbr->ls_retrans_list)) != NULL)
434a1a4e97bSnorby 		ls_retrans_list_free(nbr, le);
435a1a4e97bSnorby 
436a1a4e97bSnorby 	nbr->ls_ret_cnt = 0;
437a1a4e97bSnorby }
438a1a4e97bSnorby 
439a1a4e97bSnorby void
ls_retrans_timer(int fd,short event,void * bula)440a1a4e97bSnorby ls_retrans_timer(int fd, short event, void *bula)
441a1a4e97bSnorby {
442a1a4e97bSnorby 	struct timeval		 tv;
443a1a4e97bSnorby 	struct timespec		 tp;
444a1a4e97bSnorby 	struct in6_addr		 addr;
445a1a4e97bSnorby 	struct nbr		*nbr = bula;
446a1a4e97bSnorby 	struct lsa_entry	*le;
447e39620e5Snicm 	struct ibuf		*buf;
448a1a4e97bSnorby 	time_t			 now;
4490e9e9781Sdenis 	int			 d, bigpkt;
450a1a4e97bSnorby 	u_int32_t		 nlsa = 0;
451a1a4e97bSnorby 
452a1a4e97bSnorby 	if ((le = TAILQ_FIRST(&nbr->ls_retrans_list)) != NULL)
453a1a4e97bSnorby 		le->le_when = 0;	/* timer fired */
454a1a4e97bSnorby 	else
455a1a4e97bSnorby 		return;			/* queue empty, nothing to do */
456a1a4e97bSnorby 
457a1a4e97bSnorby 	clock_gettime(CLOCK_MONOTONIC, &tp);
458a1a4e97bSnorby 	now = tp.tv_sec;
459a1a4e97bSnorby 
460a1a4e97bSnorby 	if (nbr->iface->self == nbr) {
461a1a4e97bSnorby 		/*
462a1a4e97bSnorby 		 * oneshot needs to be set for lsa queued for flooding,
463a1a4e97bSnorby 		 * if oneshot is not set then the lsa needs to be converted
464a1a4e97bSnorby 		 * because the router switched lately to DR or BDR
465a1a4e97bSnorby 		 */
466a1a4e97bSnorby 		if (le->le_oneshot && nbr->iface->state & IF_STA_DRORBDR)
467a1a4e97bSnorby 			inet_pton(AF_INET6, AllSPFRouters, &addr);
468a1a4e97bSnorby 		else if (nbr->iface->state & IF_STA_DRORBDR) {
469a1a4e97bSnorby 			/*
470a1a4e97bSnorby 			 * old retransmission needs to be converted into
471a1a4e97bSnorby 			 * flood by rerunning the lsa_flood.
472a1a4e97bSnorby 			 */
473a1a4e97bSnorby 			lsa_flood(nbr->iface, nbr, &le->le_ref->hdr,
474a1a4e97bSnorby 			    le->le_ref->data);
475a1a4e97bSnorby 			ls_retrans_list_free(nbr, le);
476a1a4e97bSnorby 			/* ls_retrans_list_free retriggers the timer */
477a1a4e97bSnorby 			return;
47879240761Smarkus 		} else if (nbr->iface->type == IF_TYPE_POINTOPOINT)
479b02e696cSclaudio 			memcpy(&addr, &nbr->addr, sizeof(addr));
48079240761Smarkus 		else
481a1a4e97bSnorby 			inet_pton(AF_INET6, AllDRouters, &addr);
482a1a4e97bSnorby 	} else
483a1a4e97bSnorby 		memcpy(&addr, &nbr->addr, sizeof(addr));
484a1a4e97bSnorby 
4850e9e9781Sdenis 	bigpkt = le->le_ref->len > 1024;
4860e9e9781Sdenis 	if ((buf = prepare_ls_update(nbr->iface, bigpkt)) == NULL) {
487a1a4e97bSnorby 		le->le_when = 1;
488a1a4e97bSnorby 		goto done;
489a1a4e97bSnorby 	}
490a1a4e97bSnorby 
491a1a4e97bSnorby 	while ((le = TAILQ_FIRST(&nbr->ls_retrans_list)) != NULL &&
492a1a4e97bSnorby 	    le->le_when == 0) {
493a1a4e97bSnorby 		d = now - le->le_ref->stamp;
494a1a4e97bSnorby 		if (d < 0)
495a1a4e97bSnorby 			d = 0;
496a1a4e97bSnorby 		else if (d > MAX_AGE)
497a1a4e97bSnorby 			d = MAX_AGE;
498a1a4e97bSnorby 
499a1a4e97bSnorby 		if (add_ls_update(buf, nbr->iface, le->le_ref->data,
50083fd6e9aSbluhm 		    le->le_ref->len, d) == 0) {
5010a137951Sdenis 			if (nlsa == 0) {
5020a137951Sdenis 				/* something bad happened retry later */
5030a137951Sdenis 				log_warnx("ls_retrans_timer: sending LS update "
5049cc19ef1Ssthen 				    "to neighbor ID %s (%s) failed",
5059cc19ef1Ssthen 				    inet_ntoa(nbr->id), nbr->iface->name);
50683fd6e9aSbluhm 				log_debug("ls_retrans_timer: type: %04x len: %u",
5070a137951Sdenis 				    ntohs(le->le_ref->hdr.type),
5080a137951Sdenis 				    le->le_ref->len);
5090a137951Sdenis 				TAILQ_REMOVE(&nbr->ls_retrans_list, le, entry);
5100a137951Sdenis 				nbr->ls_ret_cnt--;
5110a137951Sdenis 				le->le_when = nbr->iface->rxmt_interval;
5120a137951Sdenis 				ls_retrans_list_insert(nbr, le);
5130a137951Sdenis 			}
5140a137951Sdenis 			break;
51583fd6e9aSbluhm 		}
516a1a4e97bSnorby 		nlsa++;
517a1a4e97bSnorby 		if (le->le_oneshot)
518a1a4e97bSnorby 			ls_retrans_list_free(nbr, le);
519a1a4e97bSnorby 		else {
520a1a4e97bSnorby 			TAILQ_REMOVE(&nbr->ls_retrans_list, le, entry);
521a1a4e97bSnorby 			nbr->ls_ret_cnt--;
522a1a4e97bSnorby 			le->le_when = nbr->iface->rxmt_interval;
523a1a4e97bSnorby 			ls_retrans_list_insert(nbr, le);
524a1a4e97bSnorby 		}
525a1a4e97bSnorby 	}
5260a137951Sdenis 	if (nlsa)
527a1a4e97bSnorby 		send_ls_update(buf, nbr->iface, addr, nlsa);
5280a137951Sdenis 	else
5290a137951Sdenis 		ibuf_free(buf);
530a1a4e97bSnorby 
531a1a4e97bSnorby done:
532a1a4e97bSnorby 	if ((le = TAILQ_FIRST(&nbr->ls_retrans_list)) != NULL) {
533a1a4e97bSnorby 		timerclear(&tv);
534a1a4e97bSnorby 		tv.tv_sec = le->le_when;
535a1a4e97bSnorby 
536a1a4e97bSnorby 		if (evtimer_add(&nbr->ls_retrans_timer, &tv) == -1)
537a1a4e97bSnorby 			fatal("ls_retrans_timer");
538a1a4e97bSnorby 	}
539a1a4e97bSnorby }
540a1a4e97bSnorby 
541a1a4e97bSnorby LIST_HEAD(lsa_cache_head, lsa_ref);
542a1a4e97bSnorby 
543a1a4e97bSnorby struct lsa_cache {
544a1a4e97bSnorby 	struct lsa_cache_head	*hashtbl;
545a1a4e97bSnorby 	u_int32_t		 hashmask;
546a1a4e97bSnorby } lsacache;
547a1a4e97bSnorby 
5485bc82be2Stedu SIPHASH_KEY lsacachekey;
5495bc82be2Stedu 
550a1a4e97bSnorby struct lsa_ref		*lsa_cache_look(struct lsa_hdr *);
551a1a4e97bSnorby 
552a1a4e97bSnorby void
lsa_cache_init(u_int32_t hashsize)553a1a4e97bSnorby lsa_cache_init(u_int32_t hashsize)
554a1a4e97bSnorby {
555a1a4e97bSnorby 	u_int32_t        hs, i;
556a1a4e97bSnorby 
557a1a4e97bSnorby 	for (hs = 1; hs < hashsize; hs <<= 1)
558a1a4e97bSnorby 		;
559a1a4e97bSnorby 	lsacache.hashtbl = calloc(hs, sizeof(struct lsa_cache_head));
560a1a4e97bSnorby 	if (lsacache.hashtbl == NULL)
561a1a4e97bSnorby 		fatal("lsa_cache_init");
562a1a4e97bSnorby 
563a1a4e97bSnorby 	for (i = 0; i < hs; i++)
564a1a4e97bSnorby 		LIST_INIT(&lsacache.hashtbl[i]);
5655bc82be2Stedu 	arc4random_buf(&lsacachekey, sizeof(lsacachekey));
566a1a4e97bSnorby 
567a1a4e97bSnorby 	lsacache.hashmask = hs - 1;
568a1a4e97bSnorby }
569a1a4e97bSnorby 
570d4b7cca4Stedu static uint32_t
lsa_hash_hdr(const struct lsa_hdr * hdr)5715bc82be2Stedu lsa_hash_hdr(const struct lsa_hdr *hdr)
5725bc82be2Stedu {
5735bc82be2Stedu 	return SipHash24(&lsacachekey, hdr, sizeof(*hdr));
5745bc82be2Stedu }
5755bc82be2Stedu 
576a1a4e97bSnorby struct lsa_ref *
lsa_cache_add(void * data,u_int16_t len)577a1a4e97bSnorby lsa_cache_add(void *data, u_int16_t len)
578a1a4e97bSnorby {
579a1a4e97bSnorby 	struct lsa_cache_head	*head;
580a1a4e97bSnorby 	struct lsa_ref		*ref, *old;
581a1a4e97bSnorby 	struct timespec		 tp;
582a1a4e97bSnorby 
583a1a4e97bSnorby 	if ((ref = calloc(1, sizeof(*ref))) == NULL)
584a1a4e97bSnorby 		fatal("lsa_cache_add");
585a1a4e97bSnorby 	memcpy(&ref->hdr, data, sizeof(ref->hdr));
586a1a4e97bSnorby 
587a1a4e97bSnorby 	if ((old = lsa_cache_look(&ref->hdr))) {
588a1a4e97bSnorby 		free(ref);
589a1a4e97bSnorby 		old->refcnt++;
590a1a4e97bSnorby 		return (old);
591a1a4e97bSnorby 	}
592a1a4e97bSnorby 
593a1a4e97bSnorby 	if ((ref->data = malloc(len)) == NULL)
594a1a4e97bSnorby 		fatal("lsa_cache_add");
595a1a4e97bSnorby 	memcpy(ref->data, data, len);
596a1a4e97bSnorby 
597a1a4e97bSnorby 	clock_gettime(CLOCK_MONOTONIC, &tp);
598a1a4e97bSnorby 	ref->stamp = tp.tv_sec;
599a1a4e97bSnorby 	ref->len = len;
600a1a4e97bSnorby 	ref->refcnt = 1;
601a1a4e97bSnorby 
6025bc82be2Stedu 	head = &lsacache.hashtbl[lsa_hash_hdr(&ref->hdr) & lsacache.hashmask];
603a1a4e97bSnorby 	LIST_INSERT_HEAD(head, ref, entry);
604a1a4e97bSnorby 	return (ref);
605a1a4e97bSnorby }
606a1a4e97bSnorby 
607a1a4e97bSnorby struct lsa_ref *
lsa_cache_get(struct lsa_hdr * lsa_hdr)608a1a4e97bSnorby lsa_cache_get(struct lsa_hdr *lsa_hdr)
609a1a4e97bSnorby {
610a1a4e97bSnorby 	struct lsa_ref		*ref;
611a1a4e97bSnorby 
612a1a4e97bSnorby 	ref = lsa_cache_look(lsa_hdr);
613a1a4e97bSnorby 	if (ref)
614a1a4e97bSnorby 		ref->refcnt++;
615a1a4e97bSnorby 
616a1a4e97bSnorby 	return (ref);
617a1a4e97bSnorby }
618a1a4e97bSnorby 
619a1a4e97bSnorby void
lsa_cache_put(struct lsa_ref * ref,struct nbr * nbr)620a1a4e97bSnorby lsa_cache_put(struct lsa_ref *ref, struct nbr *nbr)
621a1a4e97bSnorby {
622a1a4e97bSnorby 	if (--ref->refcnt > 0)
623a1a4e97bSnorby 		return;
624a1a4e97bSnorby 
625a1a4e97bSnorby 	if (ntohs(ref->hdr.age) >= MAX_AGE)
626a1a4e97bSnorby 		ospfe_imsg_compose_rde(IMSG_LS_MAXAGE, nbr->peerid, 0,
627a1a4e97bSnorby 		    ref->data, sizeof(struct lsa_hdr));
628a1a4e97bSnorby 
629a1a4e97bSnorby 	free(ref->data);
630a1a4e97bSnorby 	LIST_REMOVE(ref, entry);
631a1a4e97bSnorby 	free(ref);
632a1a4e97bSnorby }
633a1a4e97bSnorby 
634a1a4e97bSnorby struct lsa_ref *
lsa_cache_look(struct lsa_hdr * lsa_hdr)635a1a4e97bSnorby lsa_cache_look(struct lsa_hdr *lsa_hdr)
636a1a4e97bSnorby {
637a1a4e97bSnorby 	struct lsa_cache_head	*head;
638a1a4e97bSnorby 	struct lsa_ref		*ref;
639a1a4e97bSnorby 
6405bc82be2Stedu 	head = &lsacache.hashtbl[lsa_hash_hdr(lsa_hdr) & lsacache.hashmask];
641a1a4e97bSnorby 
642a1a4e97bSnorby 	LIST_FOREACH(ref, head, entry) {
643a1a4e97bSnorby 		if (memcmp(&ref->hdr, lsa_hdr, sizeof(*lsa_hdr)) == 0)
644a1a4e97bSnorby 			/* found match */
645a1a4e97bSnorby 			return (ref);
646a1a4e97bSnorby 	}
647a1a4e97bSnorby 
648a1a4e97bSnorby 	return (NULL);
649a1a4e97bSnorby }
650