Head

GCC Code Coverage Report

Directory:	./		Exec	Total	Coverage
File:	usr.sbin/ospfd/lsupdate.c	Lines:	0	274	0.0 %
Date:	2017-11-07	Branches:	0	206	0.0 %


/*	$OpenBSD: lsupdate.c,v 1.45 2016/12/26 17:38:14 jca Exp $ */

/*
 * Copyright (c) 2005 Claudio Jeker <claudio@openbsd.org>
 * Copyright (c) 2004, 2005 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 <arpa/inet.h>

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

#include "ospf.h"
#include "ospfd.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	add_ls_update(struct ibuf *, struct iface *, void *, u_int16_t,
	    u_int16_t);
int	send_ls_update(struct ibuf *, struct iface *, struct in_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)
{
	struct ibuf		*buf;

	if ((buf = ibuf_dynamic(iface->mtu - sizeof(struct ip),
	    IP_MAXPACKET - sizeof(struct ip))) == 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, u_int16_t len,
    u_int16_t older)
{
	void		*lsage;
	u_int16_t	 age;

	if ((size_t)iface->mtu < sizeof(struct ip) + sizeof(struct ospf_hdr) +
	    sizeof(u_int32_t) + ibuf_size(buf) + len + MD5_DIGEST_LENGTH) {
		/* start new packet unless this is the first LSA to pack */
		if (ibuf_size(buf) > sizeof(struct ospf_hdr) +
		    sizeof(u_int32_t))
			return (0);
	}

	lsage = ibuf_reserve(buf, 0);
	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(lsage, &age, sizeof(age));

	return (1);
}



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

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

	/* set destination */
	dst.sin_family = AF_INET;
	dst.sin_len = sizeof(struct sockaddr_in);
	dst.sin_addr.s_addr = addr.s_addr;

	ret = send_packet(iface, buf, &dst);

	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 in_addr		 addr;
	struct nbr		*nbr = bula;
	struct lsa_entry	*le;
	struct ibuf		*buf;
	time_t			 now;
	int			 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_aton(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_aton(AllDRouters, &addr);
	} else
		memcpy(&addr, &nbr->addr, sizeof(addr));

	if ((buf = prepare_ls_update(nbr->iface)) == 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 == 0) {
				/* something bad happened retry later */
				log_warnx("ls_retrans_timer: sending LS update "
				    "to neighbor ID %s failed",
				    inet_ntoa(nbr->id));
				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);
			}
			break;
		}
		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);
		}
	}
	if (nlsa)
		send_ls_update(buf, nbr->iface, addr, nlsa);
	else
		ibuf_free(buf);

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.45 2016/12/26 17:38:14 jca Exp $ */
2
3			/*
4			* Copyright (c) 2005 Claudio Jeker <claudio@openbsd.org>
5			* Copyright (c) 2004, 2005 Esben Norby <norby@openbsd.org>
6			*
7			* Permission to use, copy, modify, and distribute this software for any
8			* purpose with or without fee is hereby granted, provided that the above
9			* copyright notice and this permission notice appear in all copies.
10			*
11			* THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
12			* WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
13			* MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
14			* ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
15			* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
16			* ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
17			* OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
18			*/
19
20			#include <sys/types.h>
21			#include <sys/socket.h>
22			#include <netinet/in.h>
23			#include <arpa/inet.h>
24
25			#include <stdlib.h>
26			#include <string.h>
27			#include <siphash.h>
28
29			#include "ospf.h"
30			#include "ospfd.h"
31			#include "log.h"
32			#include "ospfe.h"
33			#include "rde.h"
34
35			extern struct ospfd_conf *oeconf;
36			extern struct imsgev *iev_rde;
37
38			struct ibuf prepare_ls_update(struct iface );
39			int add_ls_update(struct ibuf , struct iface , void *, u_int16_t,
40			u_int16_t);
41			int send_ls_update(struct ibuf , struct iface , struct in_addr, u_int32_t);
42
43			void ls_retrans_list_insert(struct nbr , struct lsa_entry );
44			void ls_retrans_list_remove(struct nbr , struct lsa_entry );
45
46			/* link state update packet handling */
47			int
48			lsa_flood(struct iface iface, struct nbr originator, struct lsa_hdr *lsa_hdr,
49			void *data)
50			{
51			struct nbr *nbr;
52			struct lsa_entry *le = NULL;
53			int queued = 0, dont_ack = 0;
54			int r;
55
56			LIST_FOREACH(nbr, &iface->nbr_list, entry) {
57			if (nbr == iface->self)
58			continue;
59			if (!(nbr->state & NBR_STA_FLOOD))
60			continue;
61
62			if (iface->state & IF_STA_DROTHER && !queued)
63			while ((le = ls_retrans_list_get(iface->self, lsa_hdr)))
64			ls_retrans_list_free(iface->self, le);
65
66			while ((le = ls_retrans_list_get(nbr, lsa_hdr)))
67			ls_retrans_list_free(nbr, le);
68
69			if (!(nbr->state & NBR_STA_FULL) &&
70			(le = ls_req_list_get(nbr, lsa_hdr)) != NULL) {
71			r = lsa_newer(lsa_hdr, le->le_lsa);
72			if (r > 0) {
73			/* to flood LSA is newer than requested */
74			ls_req_list_free(nbr, le);
75			/* new needs to be flooded */
76			} else if (r < 0) {
77			/* to flood LSA is older than requested */
78			continue;
79			} else {
80			/* LSA are equal */
81			ls_req_list_free(nbr, le);
82			continue;
83			}
84			}
85
86			if (nbr == originator) {
87			dont_ack++;
88			continue;
89			}
90
91			/* non DR or BDR router keep all lsa in one retrans list */
92			if (iface->state & IF_STA_DROTHER) {
93			if (!queued)
94			ls_retrans_list_add(iface->self, data,
95			iface->rxmt_interval, 0);
96			queued = 1;
97			} else {
98			ls_retrans_list_add(nbr, data, iface->rxmt_interval, 0);
99			queued = 1;
100			}
101			}
102
103			if (!queued)
104			return (0);
105
106			if (iface == originator->iface && iface->self != originator) {
107			if (iface->dr == originator \|\| iface->bdr == originator)
108			return (0);
109			if (iface->state & IF_STA_BACKUP)
110			return (0);
111			dont_ack++;
112			}
113
114			/*
115			* initial flood needs to be queued separately, timeout is zero
116			* and oneshot has to be set because the retransimssion queues
117			* are already loaded.
118			*/
119			switch (iface->type) {
120			case IF_TYPE_POINTOPOINT:
121			case IF_TYPE_BROADCAST:
122			ls_retrans_list_add(iface->self, data, 0, 1);
123			break;
124			case IF_TYPE_NBMA:
125			case IF_TYPE_POINTOMULTIPOINT:
126			case IF_TYPE_VIRTUALLINK:
127			LIST_FOREACH(nbr, &iface->nbr_list, entry) {
128			if (nbr == iface->self)
129			continue;
130			if (!(nbr->state & NBR_STA_FLOOD))
131			continue;
132			if (!TAILQ_EMPTY(&nbr->ls_retrans_list)) {
133			le = TAILQ_LAST(&nbr->ls_retrans_list,
134			lsa_head);
135			if (lsa_hdr->type != le->le_lsa->type \|\|
136			lsa_hdr->ls_id != le->le_lsa->ls_id \|\|
137			lsa_hdr->adv_rtr != le->le_lsa->adv_rtr)
138			continue;
139			}
140			ls_retrans_list_add(nbr, data, 0, 1);
141			}
142			break;
143			default:
144			fatalx("lsa_flood: unknown interface type");
145			}
146
147			return (dont_ack == 2);
148			}
149
150			struct ibuf *
151			prepare_ls_update(struct iface *iface)
152			{
153			struct ibuf *buf;
154
155			if ((buf = ibuf_dynamic(iface->mtu - sizeof(struct ip),
156			IP_MAXPACKET - sizeof(struct ip))) == NULL)
157			fatal("prepare_ls_update");
158
159			/* OSPF header */
160			if (gen_ospf_hdr(buf, iface, PACKET_TYPE_LS_UPDATE))
161			goto fail;
162
163			/* reserve space for number of lsa field */
164			if (ibuf_reserve(buf, sizeof(u_int32_t)) == NULL)
165			goto fail;
166
167			return (buf);
168			fail:
169			log_warn("prepare_ls_update");
170			ibuf_free(buf);
171			return (NULL);
172			}
173
174			int
175			add_ls_update(struct ibuf buf, struct iface iface, void *data, u_int16_t len,
176			u_int16_t older)
177			{
178			void *lsage;
179			u_int16_t age;
180
181			if ((size_t)iface->mtu < sizeof(struct ip) + sizeof(struct ospf_hdr) +
182			sizeof(u_int32_t) + ibuf_size(buf) + len + MD5_DIGEST_LENGTH) {
183			/* start new packet unless this is the first LSA to pack */
184			if (ibuf_size(buf) > sizeof(struct ospf_hdr) +
185			sizeof(u_int32_t))
186			return (0);
187			}
188
189			lsage = ibuf_reserve(buf, 0);
190			if (ibuf_add(buf, data, len)) {
191			log_warn("add_ls_update");
192			return (0);
193			}
194
195			/* age LSA before sending it out */
196			memcpy(&age, data, sizeof(age));
197			age = ntohs(age);
198			if ((age += older + iface->transmit_delay) >= MAX_AGE)
199			age = MAX_AGE;
200			age = htons(age);
201			memcpy(lsage, &age, sizeof(age));
202
203			return (1);
204			}
205
206
207
208			int
209			send_ls_update(struct ibuf buf, struct iface iface, struct in_addr addr,
210			u_int32_t nlsa)
211			{
212			struct sockaddr_in dst;
213			int ret;
214
215			nlsa = htonl(nlsa);
216			memcpy(ibuf_seek(buf, sizeof(struct ospf_hdr), sizeof(nlsa)),
217			&nlsa, sizeof(nlsa));
218			/* update authentication and calculate checksum */
219			if (auth_gen(buf, iface))
220			goto fail;
221
222			/* set destination */
223			dst.sin_family = AF_INET;
224			dst.sin_len = sizeof(struct sockaddr_in);
225			dst.sin_addr.s_addr = addr.s_addr;
226
227			ret = send_packet(iface, buf, &dst);
228
229			ibuf_free(buf);
230			return (ret);
231			fail:
232			log_warn("send_ls_update");
233			ibuf_free(buf);
234			return (-1);
235			}
236
237			void
238			recv_ls_update(struct nbr nbr, char buf, u_int16_t len)
239			{
240			struct lsa_hdr lsa;
241			u_int32_t nlsa;
242
243			if (len < sizeof(nlsa)) {
244			log_warnx("recv_ls_update: bad packet size, neighbor ID %s",
245			inet_ntoa(nbr->id));
246			return;
247			}
248			memcpy(&nlsa, buf, sizeof(nlsa));
249			nlsa = ntohl(nlsa);
250			buf += sizeof(nlsa);
251			len -= sizeof(nlsa);
252
253			switch (nbr->state) {
254			case NBR_STA_DOWN:
255			case NBR_STA_ATTEMPT:
256			case NBR_STA_INIT:
257			case NBR_STA_2_WAY:
258			case NBR_STA_XSTRT:
259			case NBR_STA_SNAP:
260			log_debug("recv_ls_update: packet ignored in state %s, "
261			"neighbor ID %s", nbr_state_name(nbr->state),
262			inet_ntoa(nbr->id));
263			break;
264			case NBR_STA_XCHNG:
265			case NBR_STA_LOAD:
266			case NBR_STA_FULL:
267			for (; nlsa > 0 && len > 0; nlsa--) {
268			if (len < sizeof(lsa)) {
269			log_warnx("recv_ls_update: bad packet size, "
270			"neighbor ID %s", inet_ntoa(nbr->id));
271			return;
272			}
273			memcpy(&lsa, buf, sizeof(lsa));
274			if (len < ntohs(lsa.len)) {
275			log_warnx("recv_ls_update: bad packet size, "
276			"neighbor ID %s", inet_ntoa(nbr->id));
277			return;
278			}
279			imsg_compose_event(iev_rde, IMSG_LS_UPD, nbr->peerid, 0,
280			-1, buf, ntohs(lsa.len));
281			buf += ntohs(lsa.len);
282			len -= ntohs(lsa.len);
283			}
284			if (nlsa > 0 \|\| len > 0) {
285			log_warnx("recv_ls_update: bad packet size, "
286			"neighbor ID %s", inet_ntoa(nbr->id));
287			return;
288			}
289			break;
290			default:
291			fatalx("recv_ls_update: unknown neighbor state");
292			}
293			}
294
295			/* link state retransmit list */
296			void
297			ls_retrans_list_add(struct nbr nbr, struct lsa_hdr lsa,
298			unsigned short timeout, unsigned short oneshot)
299			{
300			struct timeval tv;
301			struct lsa_entry *le;
302			struct lsa_ref *ref;
303
304			if ((ref = lsa_cache_get(lsa)) == NULL)
305			fatalx("King Bula sez: somebody forgot to lsa_cache_add");
306
307			if ((le = calloc(1, sizeof(*le))) == NULL)
308			fatal("ls_retrans_list_add");
309
310			le->le_ref = ref;
311			le->le_when = timeout;
312			le->le_oneshot = oneshot;
313
314			ls_retrans_list_insert(nbr, le);
315
316			if (!evtimer_pending(&nbr->ls_retrans_timer, NULL)) {
317			timerclear(&tv);
318			tv.tv_sec = TAILQ_FIRST(&nbr->ls_retrans_list)->le_when;
319
320			if (evtimer_add(&nbr->ls_retrans_timer, &tv) == -1)
321			fatal("ls_retrans_list_add");
322			}
323			}
324
325			int
326			ls_retrans_list_del(struct nbr nbr, struct lsa_hdr lsa_hdr)
327			{
328			struct lsa_entry *le;
329
330			if ((le = ls_retrans_list_get(nbr, lsa_hdr)) == NULL)
331			return (-1);
332			/*
333			* Compare LSA with the Ack by comparing not only the seq_num and
334			* checksum but also the age field. Since we only care about MAX_AGE
335			* vs. non-MAX_AGE LSA, a simple >= comparison is good enough. This
336			* ensures that a LSA withdrawal is not acked by a previous update.
337			*/
338			if (lsa_hdr->seq_num == le->le_ref->hdr.seq_num &&
339			lsa_hdr->ls_chksum == le->le_ref->hdr.ls_chksum &&
340			ntohs(lsa_hdr->age) >= ntohs(le->le_ref->hdr.age)) {
341			ls_retrans_list_free(nbr, le);
342			return (0);
343			}
344
345			return (-1);
346			}
347
348			struct lsa_entry *
349			ls_retrans_list_get(struct nbr nbr, struct lsa_hdr lsa_hdr)
350			{
351			struct lsa_entry *le;
352
353			TAILQ_FOREACH(le, &nbr->ls_retrans_list, entry) {
354			if ((lsa_hdr->type == le->le_ref->hdr.type) &&
355			(lsa_hdr->ls_id == le->le_ref->hdr.ls_id) &&
356			(lsa_hdr->adv_rtr == le->le_ref->hdr.adv_rtr))
357			return (le);
358			}
359			return (NULL);
360			}
361
362			void
363			ls_retrans_list_insert(struct nbr nbr, struct lsa_entry new)
364			{
365			struct lsa_entry *le;
366			unsigned short when = new->le_when;
367
368			TAILQ_FOREACH(le, &nbr->ls_retrans_list, entry) {
369			if (when < le->le_when) {
370			new->le_when = when;
371			TAILQ_INSERT_BEFORE(le, new, entry);
372			nbr->ls_ret_cnt++;
373			return;
374			}
375			when -= le->le_when;
376			}
377			new->le_when = when;
378			TAILQ_INSERT_TAIL(&nbr->ls_retrans_list, new, entry);
379			nbr->ls_ret_cnt++;
380			}
381
382			void
383			ls_retrans_list_remove(struct nbr nbr, struct lsa_entry le)
384			{
385			struct timeval tv;
386			struct lsa_entry *next = TAILQ_NEXT(le, entry);
387			int reset = 0;
388
389			/* adjust timeout of next entry */
390			if (next)
391			next->le_when += le->le_when;
392
393			if (TAILQ_FIRST(&nbr->ls_retrans_list) == le &&
394			evtimer_pending(&nbr->ls_retrans_timer, NULL))
395			reset = 1;
396
397			TAILQ_REMOVE(&nbr->ls_retrans_list, le, entry);
398			nbr->ls_ret_cnt--;
399
400			if (reset && TAILQ_FIRST(&nbr->ls_retrans_list)) {
401			if (evtimer_del(&nbr->ls_retrans_timer) == -1)
402			fatal("ls_retrans_list_remove");
403
404			timerclear(&tv);
405			tv.tv_sec = TAILQ_FIRST(&nbr->ls_retrans_list)->le_when;
406
407			if (evtimer_add(&nbr->ls_retrans_timer, &tv) == -1)
408			fatal("ls_retrans_list_remove");
409			}
410			}
411
412			void
413			ls_retrans_list_free(struct nbr nbr, struct lsa_entry le)
414			{
415			ls_retrans_list_remove(nbr, le);
416
417			lsa_cache_put(le->le_ref, nbr);
418			free(le);
419			}
420
421			void
422			ls_retrans_list_clr(struct nbr *nbr)
423			{
424			struct lsa_entry *le;
425
426			while ((le = TAILQ_FIRST(&nbr->ls_retrans_list)) != NULL)
427			ls_retrans_list_free(nbr, le);
428
429			nbr->ls_ret_cnt = 0;
430			}
431
432			/* ARGSUSED */
433			void
434			ls_retrans_timer(int fd, short event, void *bula)
435			{
436			struct timeval tv;
437			struct timespec tp;
438			struct in_addr addr;
439			struct nbr *nbr = bula;
440			struct lsa_entry *le;
441			struct ibuf *buf;
442			time_t now;
443			int d;
444			u_int32_t nlsa = 0;
445
446			if ((le = TAILQ_FIRST(&nbr->ls_retrans_list)) != NULL)
447			le->le_when = 0; /* timer fired */
448			else
449			return; /* queue empty, nothing to do */
450
451			clock_gettime(CLOCK_MONOTONIC, &tp);
452			now = tp.tv_sec;
453
454			if (nbr->iface->self == nbr) {
455			/*
456			* oneshot needs to be set for lsa queued for flooding,
457			* if oneshot is not set then the lsa needs to be converted
458			* because the router switched lately to DR or BDR
459			*/
460			if (le->le_oneshot && nbr->iface->state & IF_STA_DRORBDR)
461			inet_aton(AllSPFRouters, &addr);
462			else if (nbr->iface->state & IF_STA_DRORBDR) {
463			/*
464			* old retransmission needs to be converted into
465			* flood by rerunning the lsa_flood.
466			*/
467			lsa_flood(nbr->iface, nbr, &le->le_ref->hdr,
468			le->le_ref->data);
469			ls_retrans_list_free(nbr, le);
470			/* ls_retrans_list_free retriggers the timer */
471			return;
472			} else if (nbr->iface->type == IF_TYPE_POINTOPOINT)
473			memcpy(&addr, &nbr->iface->dst, sizeof(addr));
474			else
475			inet_aton(AllDRouters, &addr);
476			} else
477			memcpy(&addr, &nbr->addr, sizeof(addr));
478
479			if ((buf = prepare_ls_update(nbr->iface)) == NULL) {
480			le->le_when = 1;
481			goto done;
482			}
483
484			while ((le = TAILQ_FIRST(&nbr->ls_retrans_list)) != NULL &&
485			le->le_when == 0) {
486			d = now - le->le_ref->stamp;
487			if (d < 0)
488			d = 0;
489			else if (d > MAX_AGE)
490			d = MAX_AGE;
491
492			if (add_ls_update(buf, nbr->iface, le->le_ref->data,
493			le->le_ref->len, d) == 0) {
494			if (nlsa == 0) {
495			/* something bad happened retry later */
496			log_warnx("ls_retrans_timer: sending LS update "
497			"to neighbor ID %s failed",
498			inet_ntoa(nbr->id));
499			TAILQ_REMOVE(&nbr->ls_retrans_list, le, entry);
500			nbr->ls_ret_cnt--;
501			le->le_when = nbr->iface->rxmt_interval;
502			ls_retrans_list_insert(nbr, le);
503			}
504			break;
505			}
506			nlsa++;
507			if (le->le_oneshot)
508			ls_retrans_list_free(nbr, le);
509			else {
510			TAILQ_REMOVE(&nbr->ls_retrans_list, le, entry);
511			nbr->ls_ret_cnt--;
512			le->le_when = nbr->iface->rxmt_interval;
513			ls_retrans_list_insert(nbr, le);
514			}
515			}
516			if (nlsa)
517			send_ls_update(buf, nbr->iface, addr, nlsa);
518			else
519			ibuf_free(buf);
520
521			done:
522			if ((le = TAILQ_FIRST(&nbr->ls_retrans_list)) != NULL) {
523			timerclear(&tv);
524			tv.tv_sec = le->le_when;
525
526			if (evtimer_add(&nbr->ls_retrans_timer, &tv) == -1)
527			fatal("ls_retrans_timer");
528			}
529			}
530
531			LIST_HEAD(lsa_cache_head, lsa_ref);
532
533			struct lsa_cache {
534			struct lsa_cache_head *hashtbl;
535			u_int32_t hashmask;
536			} lsacache;
537
538			SIPHASH_KEY lsacachekey;
539
540			struct lsa_ref lsa_cache_look(struct lsa_hdr );
541
542			void
543			lsa_cache_init(u_int32_t hashsize)
544			{
545			u_int32_t hs, i;
546
547			for (hs = 1; hs < hashsize; hs <<= 1)
548			;
549			lsacache.hashtbl = calloc(hs, sizeof(struct lsa_cache_head));
550			if (lsacache.hashtbl == NULL)
551			fatal("lsa_cache_init");
552
553			for (i = 0; i < hs; i++)
554			LIST_INIT(&lsacache.hashtbl[i]);
555			arc4random_buf(&lsacachekey, sizeof(lsacachekey));
556
557			lsacache.hashmask = hs - 1;
558			}
559
560			static uint32_t
561			lsa_hash_hdr(const struct lsa_hdr *hdr)
562			{
563			return SipHash24(&lsacachekey, hdr, sizeof(*hdr));
564			}
565
566			struct lsa_ref *
567			lsa_cache_add(void *data, u_int16_t len)
568			{
569			struct lsa_cache_head *head;
570			struct lsa_ref ref, old;
571			struct timespec tp;
572
573			if ((ref = calloc(1, sizeof(*ref))) == NULL)
574			fatal("lsa_cache_add");
575			memcpy(&ref->hdr, data, sizeof(ref->hdr));
576
577			if ((old = lsa_cache_look(&ref->hdr))) {
578			free(ref);
579			old->refcnt++;
580			return (old);
581			}
582
583			if ((ref->data = malloc(len)) == NULL)
584			fatal("lsa_cache_add");
585			memcpy(ref->data, data, len);
586
587			clock_gettime(CLOCK_MONOTONIC, &tp);
588			ref->stamp = tp.tv_sec;
589			ref->len = len;
590			ref->refcnt = 1;
591
592			head = &lsacache.hashtbl[lsa_hash_hdr(&ref->hdr) & lsacache.hashmask];
593			LIST_INSERT_HEAD(head, ref, entry);
594			return (ref);
595			}
596
597			struct lsa_ref *
598			lsa_cache_get(struct lsa_hdr *lsa_hdr)
599			{
600			struct lsa_ref *ref;
601
602			ref = lsa_cache_look(lsa_hdr);
603			if (ref)
604			ref->refcnt++;
605
606			return (ref);
607			}
608
609			void
610			lsa_cache_put(struct lsa_ref ref, struct nbr nbr)
611			{
612			if (--ref->refcnt > 0)
613			return;
614
615			if (ntohs(ref->hdr.age) >= MAX_AGE)
616			ospfe_imsg_compose_rde(IMSG_LS_MAXAGE, nbr->peerid, 0,
617			ref->data, sizeof(struct lsa_hdr));
618
619			free(ref->data);
620			LIST_REMOVE(ref, entry);
621			free(ref);
622			}
623
624			struct lsa_ref *
625			lsa_cache_look(struct lsa_hdr *lsa_hdr)
626			{
627			struct lsa_cache_head *head;
628			struct lsa_ref *ref;
629
630			head = &lsacache.hashtbl[lsa_hash_hdr(lsa_hdr) & lsacache.hashmask];
631
632			LIST_FOREACH(ref, head, entry) {
633			if (memcmp(&ref->hdr, lsa_hdr, sizeof(*lsa_hdr)) == 0)
634			/* found match */
635			return (ref);
636			}
637
638			return (NULL);
639			}