Head

GCC Code Coverage Report

Directory:	./		Exec	Total	Coverage
File:	usr.sbin/ospf6d/lsupdate.c	Lines:	0	269	0.0 %
Date:	2017-11-13	Branches:	0	202	0.0 %


/*	$OpenBSD: lsupdate.c,v 1.13 2015/01/28 22:03:17 bluhm Exp $ */

/*
 * Copyright (c) 2005 Claudio Jeker <claudio@openbsd.org>
 * Copyright (c) 2004, 2005, 2007 Esben Norby <norby@openbsd.org>
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

#include <sys/types.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <netinet/ip6.h>
#include <netinet/ip_ah.h>
#include <arpa/inet.h>

#include <stdlib.h>
#include <string.h>
#include <siphash.h>

#include "ospf6.h"
#include "ospf6d.h"
#include "log.h"
#include "ospfe.h"
#include "rde.h"

extern struct ospfd_conf	*oeconf;
extern struct imsgev		*iev_rde;

struct ibuf *prepare_ls_update(struct iface *, int);
int	add_ls_update(struct ibuf *, struct iface *, void *, int, u_int16_t);
int	send_ls_update(struct ibuf *, struct iface *, struct in6_addr, u_int32_t);

void	ls_retrans_list_insert(struct nbr *, struct lsa_entry *);
void	ls_retrans_list_remove(struct nbr *, struct lsa_entry *);

/* link state update packet handling */
int
lsa_flood(struct iface *iface, struct nbr *originator, struct lsa_hdr *lsa_hdr,
    void *data)
{
	struct nbr		*nbr;
	struct lsa_entry	*le = NULL;
	int			 queued = 0, dont_ack = 0;
	int			 r;

	LIST_FOREACH(nbr, &iface->nbr_list, entry) {
		if (nbr == iface->self)
			continue;
		if (!(nbr->state & NBR_STA_FLOOD))
			continue;

		if (iface->state & IF_STA_DROTHER && !queued)
			while ((le = ls_retrans_list_get(iface->self, lsa_hdr)))
			    ls_retrans_list_free(iface->self, le);

		while ((le = ls_retrans_list_get(nbr, lsa_hdr)))
			ls_retrans_list_free(nbr, le);

		if (!(nbr->state & NBR_STA_FULL) &&
		    (le = ls_req_list_get(nbr, lsa_hdr)) != NULL) {
			r = lsa_newer(lsa_hdr, le->le_lsa);
			if (r > 0) {
				/* to flood LSA is newer than requested */
				ls_req_list_free(nbr, le);
				/* new needs to be flooded */
			} else if (r < 0) {
				/* to flood LSA is older than requested */
				continue;
			} else {
				/* LSA are equal */
				ls_req_list_free(nbr, le);
				continue;
			}
		}

		if (nbr == originator) {
			dont_ack++;
			continue;
		}

		/* non DR or BDR router keep all lsa in one retrans list */
		if (iface->state & IF_STA_DROTHER) {
			if (!queued)
				ls_retrans_list_add(iface->self, data,
				    iface->rxmt_interval, 0);
			queued = 1;
		} else {
			ls_retrans_list_add(nbr, data, iface->rxmt_interval, 0);
			queued = 1;
		}
	}

	if (!queued)
		return (0);

	if (iface == originator->iface && iface->self != originator) {
		if (iface->dr == originator || iface->bdr == originator)
			return (0);
		if (iface->state & IF_STA_BACKUP)
			return (0);
		dont_ack++;
	}

	/*
	 * initial flood needs to be queued separately, timeout is zero
	 * and oneshot has to be set because the retransimssion queues
	 * are already loaded.
	 */
	switch (iface->type) {
	case IF_TYPE_POINTOPOINT:
	case IF_TYPE_BROADCAST:
		ls_retrans_list_add(iface->self, data, 0, 1);
		break;
	case IF_TYPE_NBMA:
	case IF_TYPE_POINTOMULTIPOINT:
	case IF_TYPE_VIRTUALLINK:
		LIST_FOREACH(nbr, &iface->nbr_list, entry) {
			if (nbr == iface->self)
				continue;
			if (!(nbr->state & NBR_STA_FLOOD))
				continue;
			if (!TAILQ_EMPTY(&nbr->ls_retrans_list)) {
				le = TAILQ_LAST(&nbr->ls_retrans_list,
				    lsa_head);
				if (lsa_hdr->type != le->le_lsa->type ||
				    lsa_hdr->ls_id != le->le_lsa->ls_id ||
				    lsa_hdr->adv_rtr != le->le_lsa->adv_rtr)
					continue;
			}
			ls_retrans_list_add(nbr, data, 0, 1);
		}
		break;
	default:
		fatalx("lsa_flood: unknown interface type");
	}

	return (dont_ack == 2);
}

struct ibuf *
prepare_ls_update(struct iface *iface, int bigpkt)
{
	struct ibuf		*buf;
	size_t			 size;

	size = bigpkt ? IPV6_MAXPACKET : iface->mtu;
	if (size < IPV6_MMTU)
		size = IPV6_MMTU;
	size -= sizeof(struct ip6_hdr);
	/*
	 * Reserve space for optional ah or esp encryption.  The
	 * algorithm is taken from ah_output and esp_output, the
	 * values are the maxima of crypto/xform.c.
	 */
	size -= max(
	    /* base-ah-header replay authsize */
	    AH_FLENGTH + sizeof(u_int32_t) + 32,
	    /* spi sequence ivlen blocksize pad-length next-header authsize */
	    2 * sizeof(u_int32_t) + 16 + 16 + 2 * sizeof(u_int8_t) + 32);

	if ((buf = ibuf_open(size)) == NULL)
		fatal("prepare_ls_update");

	/* OSPF header */
	if (gen_ospf_hdr(buf, iface, PACKET_TYPE_LS_UPDATE))
		goto fail;

	/* reserve space for number of lsa field */
	if (ibuf_reserve(buf, sizeof(u_int32_t)) == NULL)
		goto fail;

	return (buf);
fail:
	log_warn("prepare_ls_update");
	ibuf_free(buf);
	return (NULL);
}

int
add_ls_update(struct ibuf *buf, struct iface *iface, void *data, int len,
    u_int16_t older)
{
	size_t		pos;
	u_int16_t	age;

	if (buf->wpos + len >= buf->max)
		return (0);

	pos = buf->wpos;
	if (ibuf_add(buf, data, len)) {
		log_warn("add_ls_update");
		return (0);
	}

	/* age LSA before sending it out */
	memcpy(&age, data, sizeof(age));
	age = ntohs(age);
	if ((age += older + iface->transmit_delay) >= MAX_AGE)
		age = MAX_AGE;
	age = htons(age);
	memcpy(ibuf_seek(buf, pos, sizeof(age)), &age, sizeof(age));

	return (1);
}

int
send_ls_update(struct ibuf *buf, struct iface *iface, struct in6_addr addr,
    u_int32_t nlsa)
{
	int			 ret;

	nlsa = htonl(nlsa);
	memcpy(ibuf_seek(buf, sizeof(struct ospf_hdr), sizeof(nlsa)),
	    &nlsa, sizeof(nlsa));
	/* calculate checksum */
	if (upd_ospf_hdr(buf, iface))
		goto fail;

	ret = send_packet(iface, buf->buf, buf->wpos, &addr);

	ibuf_free(buf);
	return (ret);
fail:
	log_warn("send_ls_update");
	ibuf_free(buf);
	return (-1);
}

void
recv_ls_update(struct nbr *nbr, char *buf, u_int16_t len)
{
	struct lsa_hdr		 lsa;
	u_int32_t		 nlsa;

	if (len < sizeof(nlsa)) {
		log_warnx("recv_ls_update: bad packet size, neighbor ID %s",
		    inet_ntoa(nbr->id));
		return;
	}
	memcpy(&nlsa, buf, sizeof(nlsa));
	nlsa = ntohl(nlsa);
	buf += sizeof(nlsa);
	len -= sizeof(nlsa);

	switch (nbr->state) {
	case NBR_STA_DOWN:
	case NBR_STA_ATTEMPT:
	case NBR_STA_INIT:
	case NBR_STA_2_WAY:
	case NBR_STA_XSTRT:
	case NBR_STA_SNAP:
		log_debug("recv_ls_update: packet ignored in state %s, "
		    "neighbor ID %s", nbr_state_name(nbr->state),
		    inet_ntoa(nbr->id));
		break;
	case NBR_STA_XCHNG:
	case NBR_STA_LOAD:
	case NBR_STA_FULL:
		for (; nlsa > 0 && len > 0; nlsa--) {
			if (len < sizeof(lsa)) {
				log_warnx("recv_ls_update: bad packet size, "
				    "neighbor ID %s", inet_ntoa(nbr->id));
				return;
			}
			memcpy(&lsa, buf, sizeof(lsa));
			if (len < ntohs(lsa.len)) {
				log_warnx("recv_ls_update: bad packet size, "
				    "neighbor ID %s", inet_ntoa(nbr->id));
				return;
			}
			imsg_compose_event(iev_rde, IMSG_LS_UPD, nbr->peerid, 0,
			    -1, buf, ntohs(lsa.len));
			buf += ntohs(lsa.len);
			len -= ntohs(lsa.len);
		}
		if (nlsa > 0 || len > 0) {
			log_warnx("recv_ls_update: bad packet size, "
			    "neighbor ID %s", inet_ntoa(nbr->id));
			return;
		}
		break;
	default:
		fatalx("recv_ls_update: unknown neighbor state");
	}
}

/* link state retransmit list */
void
ls_retrans_list_add(struct nbr *nbr, struct lsa_hdr *lsa,
    unsigned short timeout, unsigned short oneshot)
{
	struct timeval		 tv;
	struct lsa_entry	*le;
	struct lsa_ref		*ref;

	if ((ref = lsa_cache_get(lsa)) == NULL)
		fatalx("King Bula sez: somebody forgot to lsa_cache_add");

	if ((le = calloc(1, sizeof(*le))) == NULL)
		fatal("ls_retrans_list_add");

	le->le_ref = ref;
	le->le_when = timeout;
	le->le_oneshot = oneshot;

	ls_retrans_list_insert(nbr, le);

	if (!evtimer_pending(&nbr->ls_retrans_timer, NULL)) {
		timerclear(&tv);
		tv.tv_sec = TAILQ_FIRST(&nbr->ls_retrans_list)->le_when;

		if (evtimer_add(&nbr->ls_retrans_timer, &tv) == -1)
			fatal("ls_retrans_list_add");
	}
}

int
ls_retrans_list_del(struct nbr *nbr, struct lsa_hdr *lsa_hdr)
{
	struct lsa_entry	*le;

	if ((le = ls_retrans_list_get(nbr, lsa_hdr)) == NULL)
		return (-1);
	/*
	 * Compare LSA with the Ack by comparing not only the seq_num and
	 * checksum but also the age field.  Since we only care about MAX_AGE
	 * vs. non-MAX_AGE LSA, a simple >= comparison is good enough.  This
	 * ensures that a LSA withdrawal is not acked by a previous update.
	 */
	if (lsa_hdr->seq_num == le->le_ref->hdr.seq_num &&
	    lsa_hdr->ls_chksum == le->le_ref->hdr.ls_chksum &&
	    ntohs(lsa_hdr->age) >= ntohs(le->le_ref->hdr.age)) {
		ls_retrans_list_free(nbr, le);
		return (0);
	}

	return (-1);
}

struct lsa_entry *
ls_retrans_list_get(struct nbr *nbr, struct lsa_hdr *lsa_hdr)
{
	struct lsa_entry	*le;

	TAILQ_FOREACH(le, &nbr->ls_retrans_list, entry) {
		if ((lsa_hdr->type == le->le_ref->hdr.type) &&
		    (lsa_hdr->ls_id == le->le_ref->hdr.ls_id) &&
		    (lsa_hdr->adv_rtr == le->le_ref->hdr.adv_rtr))
			return (le);
	}
	return (NULL);
}

void
ls_retrans_list_insert(struct nbr *nbr, struct lsa_entry *new)
{
	struct lsa_entry	*le;
	unsigned short		 when = new->le_when;

	TAILQ_FOREACH(le, &nbr->ls_retrans_list, entry) {
		if (when < le->le_when) {
			new->le_when = when;
			TAILQ_INSERT_BEFORE(le, new, entry);
			nbr->ls_ret_cnt++;
			return;
		}
		when -= le->le_when;
	}
	new->le_when = when;
	TAILQ_INSERT_TAIL(&nbr->ls_retrans_list, new, entry);
	nbr->ls_ret_cnt++;
}

void
ls_retrans_list_remove(struct nbr *nbr, struct lsa_entry *le)
{
	struct timeval		 tv;
	struct lsa_entry	*next = TAILQ_NEXT(le, entry);
	int			 reset = 0;

	/* adjust timeout of next entry */
	if (next)
		next->le_when += le->le_when;

	if (TAILQ_FIRST(&nbr->ls_retrans_list) == le &&
	    evtimer_pending(&nbr->ls_retrans_timer, NULL))
		reset = 1;

	TAILQ_REMOVE(&nbr->ls_retrans_list, le, entry);
	nbr->ls_ret_cnt--;

	if (reset && TAILQ_FIRST(&nbr->ls_retrans_list)) {
		if (evtimer_del(&nbr->ls_retrans_timer) == -1)
			fatal("ls_retrans_list_remove");

		timerclear(&tv);
		tv.tv_sec = TAILQ_FIRST(&nbr->ls_retrans_list)->le_when;

		if (evtimer_add(&nbr->ls_retrans_timer, &tv) == -1)
			fatal("ls_retrans_list_remove");
	}
}

void
ls_retrans_list_free(struct nbr *nbr, struct lsa_entry *le)
{
	ls_retrans_list_remove(nbr, le);

	lsa_cache_put(le->le_ref, nbr);
	free(le);
}

void
ls_retrans_list_clr(struct nbr *nbr)
{
	struct lsa_entry	*le;

	while ((le = TAILQ_FIRST(&nbr->ls_retrans_list)) != NULL)
		ls_retrans_list_free(nbr, le);

	nbr->ls_ret_cnt = 0;
}

/* ARGSUSED */
void
ls_retrans_timer(int fd, short event, void *bula)
{
	struct timeval		 tv;
	struct timespec		 tp;
	struct in6_addr		 addr;
	struct nbr		*nbr = bula;
	struct lsa_entry	*le;
	struct ibuf		*buf;
	time_t			 now;
	int			 bigpkt, d;
	u_int32_t		 nlsa = 0;

	if ((le = TAILQ_FIRST(&nbr->ls_retrans_list)) != NULL)
		le->le_when = 0;	/* timer fired */
	else
		return;			/* queue empty, nothing to do */

	clock_gettime(CLOCK_MONOTONIC, &tp);
	now = tp.tv_sec;

	if (nbr->iface->self == nbr) {
		/*
		 * oneshot needs to be set for lsa queued for flooding,
		 * if oneshot is not set then the lsa needs to be converted
		 * because the router switched lately to DR or BDR
		 */
		if (le->le_oneshot && nbr->iface->state & IF_STA_DRORBDR)
			inet_pton(AF_INET6, AllSPFRouters, &addr);
		else if (nbr->iface->state & IF_STA_DRORBDR) {
			/*
			 * old retransmission needs to be converted into
			 * flood by rerunning the lsa_flood.
			 */
			lsa_flood(nbr->iface, nbr, &le->le_ref->hdr,
			    le->le_ref->data);
			ls_retrans_list_free(nbr, le);
			/* ls_retrans_list_free retriggers the timer */
			return;
		} else if (nbr->iface->type == IF_TYPE_POINTOPOINT)
			memcpy(&addr, &nbr->iface->dst, sizeof(addr));
		else
			inet_pton(AF_INET6, AllDRouters, &addr);
	} else
		memcpy(&addr, &nbr->addr, sizeof(addr));

	/*
	 * Allow big ipv6 packets that may get fragmented if a
	 * single lsa might be too big for an unfragmented packet.
	 * To avoid the exact algorithm duplicated here, just make
	 * a good guess.  If the first lsa is bigger than 1024
	 * bytes, reserve a separate big packet for it.  The kernel
	 * will figure out if fragmentation is necessary.  For
	 * smaller lsas, we avoid big packets and fragmentation.
	 */
	bigpkt = le->le_ref->len > 1024;
	if ((buf = prepare_ls_update(nbr->iface, bigpkt)) == NULL) {
		le->le_when = 1;
		goto done;
	}

	while ((le = TAILQ_FIRST(&nbr->ls_retrans_list)) != NULL &&
	    le->le_when == 0) {
		d = now - le->le_ref->stamp;
		if (d < 0)
			d = 0;
		else if (d > MAX_AGE)
			d = MAX_AGE;

		if (add_ls_update(buf, nbr->iface, le->le_ref->data,
		    le->le_ref->len, d) == 0) {
			if (nlsa)
				break;
			/*
			 * A single lsa is too big to fit into an update
			 * packet.  In this case drop the lsa, otherwise
			 * we send empty update packets in an endless loop.
			 */
			log_warnx("ls_retrans_timer: cannot send lsa, dropped");
			log_debug("ls_retrans_timer: type: %04x len: %u",
			    ntohs(le->le_ref->hdr.type), le->le_ref->len);
			ls_retrans_list_free(nbr, le);
			continue;
		}
		nlsa++;
		if (le->le_oneshot)
			ls_retrans_list_free(nbr, le);
		else {
			TAILQ_REMOVE(&nbr->ls_retrans_list, le, entry);
			nbr->ls_ret_cnt--;
			le->le_when = nbr->iface->rxmt_interval;
			ls_retrans_list_insert(nbr, le);
		}
		/* do not put additional lsa into fragmented big packet */
		if (bigpkt)
			break;
	}
	send_ls_update(buf, nbr->iface, addr, nlsa);

done:
	if ((le = TAILQ_FIRST(&nbr->ls_retrans_list)) != NULL) {
		timerclear(&tv);
		tv.tv_sec = le->le_when;

		if (evtimer_add(&nbr->ls_retrans_timer, &tv) == -1)
			fatal("ls_retrans_timer");
	}
}

LIST_HEAD(lsa_cache_head, lsa_ref);

struct lsa_cache {
	struct lsa_cache_head	*hashtbl;
	u_int32_t		 hashmask;
} lsacache;

SIPHASH_KEY lsacachekey;

struct lsa_ref		*lsa_cache_look(struct lsa_hdr *);

void
lsa_cache_init(u_int32_t hashsize)
{
	u_int32_t        hs, i;

	for (hs = 1; hs < hashsize; hs <<= 1)
		;
	lsacache.hashtbl = calloc(hs, sizeof(struct lsa_cache_head));
	if (lsacache.hashtbl == NULL)
		fatal("lsa_cache_init");

	for (i = 0; i < hs; i++)
		LIST_INIT(&lsacache.hashtbl[i]);
	arc4random_buf(&lsacachekey, sizeof(lsacachekey));

	lsacache.hashmask = hs - 1;
}

static uint32_t
lsa_hash_hdr(const struct lsa_hdr *hdr)
{
	return SipHash24(&lsacachekey, hdr, sizeof(*hdr));
}

struct lsa_ref *
lsa_cache_add(void *data, u_int16_t len)
{
	struct lsa_cache_head	*head;
	struct lsa_ref		*ref, *old;
	struct timespec		 tp;

	if ((ref = calloc(1, sizeof(*ref))) == NULL)
		fatal("lsa_cache_add");
	memcpy(&ref->hdr, data, sizeof(ref->hdr));

	if ((old = lsa_cache_look(&ref->hdr))) {
		free(ref);
		old->refcnt++;
		return (old);
	}

	if ((ref->data = malloc(len)) == NULL)
		fatal("lsa_cache_add");
	memcpy(ref->data, data, len);

	clock_gettime(CLOCK_MONOTONIC, &tp);
	ref->stamp = tp.tv_sec;
	ref->len = len;
	ref->refcnt = 1;

	head = &lsacache.hashtbl[lsa_hash_hdr(&ref->hdr) & lsacache.hashmask];
	LIST_INSERT_HEAD(head, ref, entry);
	return (ref);
}

struct lsa_ref *
lsa_cache_get(struct lsa_hdr *lsa_hdr)
{
	struct lsa_ref		*ref;

	ref = lsa_cache_look(lsa_hdr);
	if (ref)
		ref->refcnt++;

	return (ref);
}

void
lsa_cache_put(struct lsa_ref *ref, struct nbr *nbr)
{
	if (--ref->refcnt > 0)
		return;

	if (ntohs(ref->hdr.age) >= MAX_AGE)
		ospfe_imsg_compose_rde(IMSG_LS_MAXAGE, nbr->peerid, 0,
		    ref->data, sizeof(struct lsa_hdr));

	free(ref->data);
	LIST_REMOVE(ref, entry);
	free(ref);
}

struct lsa_ref *
lsa_cache_look(struct lsa_hdr *lsa_hdr)
{
	struct lsa_cache_head	*head;
	struct lsa_ref		*ref;

	head = &lsacache.hashtbl[lsa_hash_hdr(lsa_hdr) & lsacache.hashmask];

	LIST_FOREACH(ref, head, entry) {
		if (memcmp(&ref->hdr, lsa_hdr, sizeof(*lsa_hdr)) == 0)
			/* found match */
			return (ref);
	}

	return (NULL);
}


Generated by: GCOVR (Version 3.3)

Line	Branch	Exec	Source
1			/* $OpenBSD: lsupdate.c,v 1.13 2015/01/28 22:03:17 bluhm 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
37			extern struct ospfd_conf *oeconf;
38			extern struct imsgev *iev_rde;
39
40			struct ibuf prepare_ls_update(struct iface , int);
41			int add_ls_update(struct ibuf , struct iface , void *, int, u_int16_t);
42			int send_ls_update(struct ibuf , struct iface , struct in6_addr, u_int32_t);
43
44			void ls_retrans_list_insert(struct nbr , struct lsa_entry );
45			void ls_retrans_list_remove(struct nbr , struct lsa_entry );
46
47			/* link state update packet handling */
48			int
49			lsa_flood(struct iface iface, struct nbr originator, struct lsa_hdr *lsa_hdr,
50			void *data)
51			{
52			struct nbr *nbr;
53			struct lsa_entry *le = NULL;
54			int queued = 0, dont_ack = 0;
55			int r;
56
57			LIST_FOREACH(nbr, &iface->nbr_list, entry) {
58			if (nbr == iface->self)
59			continue;
60			if (!(nbr->state & NBR_STA_FLOOD))
61			continue;
62
63			if (iface->state & IF_STA_DROTHER && !queued)
64			while ((le = ls_retrans_list_get(iface->self, lsa_hdr)))
65			ls_retrans_list_free(iface->self, le);
66
67			while ((le = ls_retrans_list_get(nbr, lsa_hdr)))
68			ls_retrans_list_free(nbr, le);
69
70			if (!(nbr->state & NBR_STA_FULL) &&
71			(le = ls_req_list_get(nbr, lsa_hdr)) != NULL) {
72			r = lsa_newer(lsa_hdr, le->le_lsa);
73			if (r > 0) {
74			/* to flood LSA is newer than requested */
75			ls_req_list_free(nbr, le);
76			/* new needs to be flooded */
77			} else if (r < 0) {
78			/* to flood LSA is older than requested */
79			continue;
80			} else {
81			/* LSA are equal */
82			ls_req_list_free(nbr, le);
83			continue;
84			}
85			}
86
87			if (nbr == originator) {
88			dont_ack++;
89			continue;
90			}
91
92			/* non DR or BDR router keep all lsa in one retrans list */
93			if (iface->state & IF_STA_DROTHER) {
94			if (!queued)
95			ls_retrans_list_add(iface->self, data,
96			iface->rxmt_interval, 0);
97			queued = 1;
98			} else {
99			ls_retrans_list_add(nbr, data, iface->rxmt_interval, 0);
100			queued = 1;
101			}
102			}
103
104			if (!queued)
105			return (0);
106
107			if (iface == originator->iface && iface->self != originator) {
108			if (iface->dr == originator \|\| iface->bdr == originator)
109			return (0);
110			if (iface->state & IF_STA_BACKUP)
111			return (0);
112			dont_ack++;
113			}
114
115			/*
116			* initial flood needs to be queued separately, timeout is zero
117			* and oneshot has to be set because the retransimssion queues
118			* are already loaded.
119			*/
120			switch (iface->type) {
121			case IF_TYPE_POINTOPOINT:
122			case IF_TYPE_BROADCAST:
123			ls_retrans_list_add(iface->self, data, 0, 1);
124			break;
125			case IF_TYPE_NBMA:
126			case IF_TYPE_POINTOMULTIPOINT:
127			case IF_TYPE_VIRTUALLINK:
128			LIST_FOREACH(nbr, &iface->nbr_list, entry) {
129			if (nbr == iface->self)
130			continue;
131			if (!(nbr->state & NBR_STA_FLOOD))
132			continue;
133			if (!TAILQ_EMPTY(&nbr->ls_retrans_list)) {
134			le = TAILQ_LAST(&nbr->ls_retrans_list,
135			lsa_head);
136			if (lsa_hdr->type != le->le_lsa->type \|\|
137			lsa_hdr->ls_id != le->le_lsa->ls_id \|\|
138			lsa_hdr->adv_rtr != le->le_lsa->adv_rtr)
139			continue;
140			}
141			ls_retrans_list_add(nbr, data, 0, 1);
142			}
143			break;
144			default:
145			fatalx("lsa_flood: unknown interface type");
146			}
147
148			return (dont_ack == 2);
149			}
150
151			struct ibuf *
152			prepare_ls_update(struct iface *iface, int bigpkt)
153			{
154			struct ibuf *buf;
155			size_t size;
156
157			size = bigpkt ? IPV6_MAXPACKET : iface->mtu;
158			if (size < IPV6_MMTU)
159			size = IPV6_MMTU;
160			size -= sizeof(struct ip6_hdr);
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);
184			fail:
185			log_warn("prepare_ls_update");
186			ibuf_free(buf);
187			return (NULL);
188			}
189
190			int
191			add_ls_update(struct ibuf buf, struct iface iface, void *data, int len,
192			u_int16_t older)
193			{
194			size_t pos;
195			u_int16_t age;
196
197			if (buf->wpos + len >= buf->max)
198			return (0);
199
200			pos = buf->wpos;
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, pos, sizeof(age)), &age, sizeof(age));
213
214			return (1);
215			}
216
217			int
218			send_ls_update(struct ibuf buf, struct iface iface, struct in6_addr addr,
219			u_int32_t nlsa)
220			{
221			int ret;
222
223			nlsa = htonl(nlsa);
224			memcpy(ibuf_seek(buf, sizeof(struct ospf_hdr), sizeof(nlsa)),
225			&nlsa, sizeof(nlsa));
226			/* calculate checksum */
227			if (upd_ospf_hdr(buf, iface))
228			goto fail;
229
230			ret = send_packet(iface, buf->buf, buf->wpos, &addr);
231
232			ibuf_free(buf);
233			return (ret);
234			fail:
235			log_warn("send_ls_update");
236			ibuf_free(buf);
237			return (-1);
238			}
239
240			void
241			recv_ls_update(struct nbr nbr, char buf, u_int16_t len)
242			{
243			struct lsa_hdr lsa;
244			u_int32_t nlsa;
245
246			if (len < sizeof(nlsa)) {
247			log_warnx("recv_ls_update: bad packet size, neighbor ID %s",
248			inet_ntoa(nbr->id));
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", nbr_state_name(nbr->state),
265			inet_ntoa(nbr->id));
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", inet_ntoa(nbr->id));
274			return;
275			}
276			memcpy(&lsa, buf, sizeof(lsa));
277			if (len < ntohs(lsa.len)) {
278			log_warnx("recv_ls_update: bad packet size, "
279			"neighbor ID %s", inet_ntoa(nbr->id));
280			return;
281			}
282			imsg_compose_event(iev_rde, IMSG_LS_UPD, nbr->peerid, 0,
283			-1, buf, ntohs(lsa.len));
284			buf += ntohs(lsa.len);
285			len -= ntohs(lsa.len);
286			}
287			if (nlsa > 0 \|\| len > 0) {
288			log_warnx("recv_ls_update: bad packet size, "
289			"neighbor ID %s", inet_ntoa(nbr->id));
290			return;
291			}
292			break;
293			default:
294			fatalx("recv_ls_update: unknown neighbor state");
295			}
296			}
297
298			/* link state retransmit list */
299			void
300			ls_retrans_list_add(struct nbr nbr, struct lsa_hdr lsa,
301			unsigned short timeout, unsigned short oneshot)
302			{
303			struct timeval tv;
304			struct lsa_entry *le;
305			struct lsa_ref *ref;
306
307			if ((ref = lsa_cache_get(lsa)) == NULL)
308			fatalx("King Bula sez: somebody forgot to lsa_cache_add");
309
310			if ((le = calloc(1, sizeof(*le))) == NULL)
311			fatal("ls_retrans_list_add");
312
313			le->le_ref = ref;
314			le->le_when = timeout;
315			le->le_oneshot = oneshot;
316
317			ls_retrans_list_insert(nbr, le);
318
319			if (!evtimer_pending(&nbr->ls_retrans_timer, NULL)) {
320			timerclear(&tv);
321			tv.tv_sec = TAILQ_FIRST(&nbr->ls_retrans_list)->le_when;
322
323			if (evtimer_add(&nbr->ls_retrans_timer, &tv) == -1)
324			fatal("ls_retrans_list_add");
325			}
326			}
327
328			int
329			ls_retrans_list_del(struct nbr nbr, struct lsa_hdr lsa_hdr)
330			{
331			struct lsa_entry *le;
332
333			if ((le = ls_retrans_list_get(nbr, lsa_hdr)) == NULL)
334			return (-1);
335			/*
336			* Compare LSA with the Ack by comparing not only the seq_num and
337			* checksum but also the age field. Since we only care about MAX_AGE
338			* vs. non-MAX_AGE LSA, a simple >= comparison is good enough. This
339			* ensures that a LSA withdrawal is not acked by a previous update.
340			*/
341			if (lsa_hdr->seq_num == le->le_ref->hdr.seq_num &&
342			lsa_hdr->ls_chksum == le->le_ref->hdr.ls_chksum &&
343			ntohs(lsa_hdr->age) >= ntohs(le->le_ref->hdr.age)) {
344			ls_retrans_list_free(nbr, le);
345			return (0);
346			}
347
348			return (-1);
349			}
350
351			struct lsa_entry *
352			ls_retrans_list_get(struct nbr nbr, struct lsa_hdr lsa_hdr)
353			{
354			struct lsa_entry *le;
355
356			TAILQ_FOREACH(le, &nbr->ls_retrans_list, entry) {
357			if ((lsa_hdr->type == le->le_ref->hdr.type) &&
358			(lsa_hdr->ls_id == le->le_ref->hdr.ls_id) &&
359			(lsa_hdr->adv_rtr == le->le_ref->hdr.adv_rtr))
360			return (le);
361			}
362			return (NULL);
363			}
364
365			void
366			ls_retrans_list_insert(struct nbr nbr, struct lsa_entry new)
367			{
368			struct lsa_entry *le;
369			unsigned short when = new->le_when;
370
371			TAILQ_FOREACH(le, &nbr->ls_retrans_list, entry) {
372			if (when < le->le_when) {
373			new->le_when = when;
374			TAILQ_INSERT_BEFORE(le, new, entry);
375			nbr->ls_ret_cnt++;
376			return;
377			}
378			when -= le->le_when;
379			}
380			new->le_when = when;
381			TAILQ_INSERT_TAIL(&nbr->ls_retrans_list, new, entry);
382			nbr->ls_ret_cnt++;
383			}
384
385			void
386			ls_retrans_list_remove(struct nbr nbr, struct lsa_entry le)
387			{
388			struct timeval tv;
389			struct lsa_entry *next = TAILQ_NEXT(le, entry);
390			int reset = 0;
391
392			/* adjust timeout of next entry */
393			if (next)
394			next->le_when += le->le_when;
395
396			if (TAILQ_FIRST(&nbr->ls_retrans_list) == le &&
397			evtimer_pending(&nbr->ls_retrans_timer, NULL))
398			reset = 1;
399
400			TAILQ_REMOVE(&nbr->ls_retrans_list, le, entry);
401			nbr->ls_ret_cnt--;
402
403			if (reset && TAILQ_FIRST(&nbr->ls_retrans_list)) {
404			if (evtimer_del(&nbr->ls_retrans_timer) == -1)
405			fatal("ls_retrans_list_remove");
406
407			timerclear(&tv);
408			tv.tv_sec = TAILQ_FIRST(&nbr->ls_retrans_list)->le_when;
409
410			if (evtimer_add(&nbr->ls_retrans_timer, &tv) == -1)
411			fatal("ls_retrans_list_remove");
412			}
413			}
414
415			void
416			ls_retrans_list_free(struct nbr nbr, struct lsa_entry le)
417			{
418			ls_retrans_list_remove(nbr, le);
419
420			lsa_cache_put(le->le_ref, nbr);
421			free(le);
422			}
423
424			void
425			ls_retrans_list_clr(struct nbr *nbr)
426			{
427			struct lsa_entry *le;
428
429			while ((le = TAILQ_FIRST(&nbr->ls_retrans_list)) != NULL)
430			ls_retrans_list_free(nbr, le);
431
432			nbr->ls_ret_cnt = 0;
433			}
434
435			/* ARGSUSED */
436			void
437			ls_retrans_timer(int fd, short event, void *bula)
438			{
439			struct timeval tv;
440			struct timespec tp;
441			struct in6_addr addr;
442			struct nbr *nbr = bula;
443			struct lsa_entry *le;
444			struct ibuf *buf;
445			time_t now;
446			int bigpkt, d;
447			u_int32_t nlsa = 0;
448
449			if ((le = TAILQ_FIRST(&nbr->ls_retrans_list)) != NULL)
450			le->le_when = 0; /* timer fired */
451			else
452			return; /* queue empty, nothing to do */
453
454			clock_gettime(CLOCK_MONOTONIC, &tp);
455			now = tp.tv_sec;
456
457			if (nbr->iface->self == nbr) {
458			/*
459			* oneshot needs to be set for lsa queued for flooding,
460			* if oneshot is not set then the lsa needs to be converted
461			* because the router switched lately to DR or BDR
462			*/
463			if (le->le_oneshot && nbr->iface->state & IF_STA_DRORBDR)
464			inet_pton(AF_INET6, AllSPFRouters, &addr);
465			else if (nbr->iface->state & IF_STA_DRORBDR) {
466			/*
467			* old retransmission needs to be converted into
468			* flood by rerunning the lsa_flood.
469			*/
470			lsa_flood(nbr->iface, nbr, &le->le_ref->hdr,
471			le->le_ref->data);
472			ls_retrans_list_free(nbr, le);
473			/* ls_retrans_list_free retriggers the timer */
474			return;
475			} else if (nbr->iface->type == IF_TYPE_POINTOPOINT)
476			memcpy(&addr, &nbr->iface->dst, sizeof(addr));
477			else
478			inet_pton(AF_INET6, AllDRouters, &addr);
479			} else
480			memcpy(&addr, &nbr->addr, sizeof(addr));
481
482			/*
483			* Allow big ipv6 packets that may get fragmented if a
484			* single lsa might be too big for an unfragmented packet.
485			* To avoid the exact algorithm duplicated here, just make
486			* a good guess. If the first lsa is bigger than 1024
487			* bytes, reserve a separate big packet for it. The kernel
488			* will figure out if fragmentation is necessary. For
489			* smaller lsas, we avoid big packets and fragmentation.
490			*/
491			bigpkt = le->le_ref->len > 1024;
492			if ((buf = prepare_ls_update(nbr->iface, bigpkt)) == NULL) {
493			le->le_when = 1;
494			goto done;
495			}
496
497			while ((le = TAILQ_FIRST(&nbr->ls_retrans_list)) != NULL &&
498			le->le_when == 0) {
499			d = now - le->le_ref->stamp;
500			if (d < 0)
501			d = 0;
502			else if (d > MAX_AGE)
503			d = MAX_AGE;
504
505			if (add_ls_update(buf, nbr->iface, le->le_ref->data,
506			le->le_ref->len, d) == 0) {
507			if (nlsa)
508			break;
509			/*
510			* A single lsa is too big to fit into an update
511			* packet. In this case drop the lsa, otherwise
512			* we send empty update packets in an endless loop.
513			*/
514			log_warnx("ls_retrans_timer: cannot send lsa, dropped");
515			log_debug("ls_retrans_timer: type: %04x len: %u",
516			ntohs(le->le_ref->hdr.type), le->le_ref->len);
517			ls_retrans_list_free(nbr, le);
518			continue;
519			}
520			nlsa++;
521			if (le->le_oneshot)
522			ls_retrans_list_free(nbr, le);
523			else {
524			TAILQ_REMOVE(&nbr->ls_retrans_list, le, entry);
525			nbr->ls_ret_cnt--;
526			le->le_when = nbr->iface->rxmt_interval;
527			ls_retrans_list_insert(nbr, le);
528			}
529			/* do not put additional lsa into fragmented big packet */
530			if (bigpkt)
531			break;
532			}
533			send_ls_update(buf, nbr->iface, addr, nlsa);
534
535			done:
536			if ((le = TAILQ_FIRST(&nbr->ls_retrans_list)) != NULL) {
537			timerclear(&tv);
538			tv.tv_sec = le->le_when;
539
540			if (evtimer_add(&nbr->ls_retrans_timer, &tv) == -1)
541			fatal("ls_retrans_timer");
542			}
543			}
544
545			LIST_HEAD(lsa_cache_head, lsa_ref);
546
547			struct lsa_cache {
548			struct lsa_cache_head *hashtbl;
549			u_int32_t hashmask;
550			} lsacache;
551
552			SIPHASH_KEY lsacachekey;
553
554			struct lsa_ref lsa_cache_look(struct lsa_hdr );
555
556			void
557			lsa_cache_init(u_int32_t hashsize)
558			{
559			u_int32_t hs, i;
560
561			for (hs = 1; hs < hashsize; hs <<= 1)
562			;
563			lsacache.hashtbl = calloc(hs, sizeof(struct lsa_cache_head));
564			if (lsacache.hashtbl == NULL)
565			fatal("lsa_cache_init");
566
567			for (i = 0; i < hs; i++)
568			LIST_INIT(&lsacache.hashtbl[i]);
569			arc4random_buf(&lsacachekey, sizeof(lsacachekey));
570
571			lsacache.hashmask = hs - 1;
572			}
573
574			static uint32_t
575			lsa_hash_hdr(const struct lsa_hdr *hdr)
576			{
577			return SipHash24(&lsacachekey, hdr, sizeof(*hdr));
578			}
579
580			struct lsa_ref *
581			lsa_cache_add(void *data, u_int16_t len)
582			{
583			struct lsa_cache_head *head;
584			struct lsa_ref ref, old;
585			struct timespec tp;
586
587			if ((ref = calloc(1, sizeof(*ref))) == NULL)
588			fatal("lsa_cache_add");
589			memcpy(&ref->hdr, data, sizeof(ref->hdr));
590
591			if ((old = lsa_cache_look(&ref->hdr))) {
592			free(ref);
593			old->refcnt++;
594			return (old);
595			}
596
597			if ((ref->data = malloc(len)) == NULL)
598			fatal("lsa_cache_add");
599			memcpy(ref->data, data, len);
600
601			clock_gettime(CLOCK_MONOTONIC, &tp);
602			ref->stamp = tp.tv_sec;
603			ref->len = len;
604			ref->refcnt = 1;
605
606			head = &lsacache.hashtbl[lsa_hash_hdr(&ref->hdr) & lsacache.hashmask];
607			LIST_INSERT_HEAD(head, ref, entry);
608			return (ref);
609			}
610
611			struct lsa_ref *
612			lsa_cache_get(struct lsa_hdr *lsa_hdr)
613			{
614			struct lsa_ref *ref;
615
616			ref = lsa_cache_look(lsa_hdr);
617			if (ref)
618			ref->refcnt++;
619
620			return (ref);
621			}
622
623			void
624			lsa_cache_put(struct lsa_ref ref, struct nbr nbr)
625			{
626			if (--ref->refcnt > 0)
627			return;
628
629			if (ntohs(ref->hdr.age) >= MAX_AGE)
630			ospfe_imsg_compose_rde(IMSG_LS_MAXAGE, nbr->peerid, 0,
631			ref->data, sizeof(struct lsa_hdr));
632
633			free(ref->data);
634			LIST_REMOVE(ref, entry);
635			free(ref);
636			}
637
638			struct lsa_ref *
639			lsa_cache_look(struct lsa_hdr *lsa_hdr)
640			{
641			struct lsa_cache_head *head;
642			struct lsa_ref *ref;
643
644			head = &lsacache.hashtbl[lsa_hash_hdr(lsa_hdr) & lsacache.hashmask];
645
646			LIST_FOREACH(ref, head, entry) {
647			if (memcmp(&ref->hdr, lsa_hdr, sizeof(*lsa_hdr)) == 0)
648			/* found match */
649			return (ref);
650			}
651
652			return (NULL);
653			}