Instead of a simple timer per neighbor for the LS retransmition list use

a timewheel. All LSA updates are now first added to the queue and sent out
later. This makes it possible to cluster multiple LSA updates into on OSPF
packet. This gives a massive speedup when large databases need to be synced.
Tested and OK norby@

3 files changed, 174 insertions, 65 deletions

diff --git a/usr.sbin/ospfd/lsupdate.c b/usr.sbin/ospfd/lsupdate.c
index 9dbeacd3848..763a527f158 100644
--- a/usr.sbin/ospfd/lsupdate.c
+++ b/usr.sbin/ospfd/lsupdate.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: lsupdate.c,v 1.21 2005/11/12 18:18:24 deraadt Exp $ */
+/*	$OpenBSD: lsupdate.c,v 1.22 2005/12/29 13:53:36 claudio Exp $ */
 
 /*
  * Copyright (c) 2005 Claudio Jeker <claudio@openbsd.org>
@@ -34,12 +34,18 @@
 extern struct ospfd_conf	*oeconf;
 extern struct imsgbuf		*ibuf_rde;
 
+struct buf *prepare_ls_update(struct iface *);
+int	add_ls_update(struct buf *, struct iface *, void *, int);
+int	send_ls_update(struct buf *, 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, u_int16_t len)
 {
-	struct in_addr		 addr;
 	struct nbr		*nbr;
 	struct lsa_entry	*le = NULL;
 	int			 queued = 0, dont_ack = 0;
@@ -83,10 +89,11 @@ lsa_flood(struct iface *iface, struct nbr *originator, struct lsa_hdr *lsa_hdr,
 		/* 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);
+				ls_retrans_list_add(iface->self, data,
+				    iface->rxmt_interval, 0);
 			queued = 1;
 		} else {
-			ls_retrans_list_add(nbr, data);
+			ls_retrans_list_add(nbr, data, iface->rxmt_interval, 0);
 			queued = 1;
 		}
 	}
@@ -102,18 +109,15 @@ lsa_flood(struct iface *iface, struct nbr *originator, struct lsa_hdr *lsa_hdr,
 		dont_ack++;
 	}
 
-	/* flood LSA but first set correct destination */
+	/*
+	 * 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:
-		inet_aton(AllSPFRouters, &addr);
-		send_ls_update(iface, addr, data, len);
-		break;
 	case IF_TYPE_BROADCAST:
-		if (iface->state & IF_STA_DRORBDR)
-			inet_aton(AllSPFRouters, &addr);
-		else
-			inet_aton(AllDRouters, &addr);
-		send_ls_update(iface, addr, data, len);
+		ls_retrans_list_add(iface->self, data, 0, 1);
 		break;
 	case IF_TYPE_NBMA:
 	case IF_TYPE_POINTOMULTIPOINT:
@@ -131,7 +135,7 @@ lsa_flood(struct iface *iface, struct nbr *originator, struct lsa_hdr *lsa_hdr,
 				    lsa_hdr->adv_rtr != le->le_lsa->adv_rtr)
 					continue;
 			}
-			send_ls_update(iface, nbr->addr, data, len);
+			ls_retrans_list_add(nbr, data, 0, 1);
 		}
 		break;
 	default:
@@ -141,36 +145,43 @@ lsa_flood(struct iface *iface, struct nbr *originator, struct lsa_hdr *lsa_hdr,
 	return (dont_ack == 2);
 }
 
-int
-send_ls_update(struct iface *iface, struct in_addr addr, void *data, int len)
+struct buf *
+prepare_ls_update(struct iface *iface)
 {
-	struct sockaddr_in	 dst;
 	struct buf		*buf;
-	size_t			 pos;
-	u_int32_t		 nlsa;
-	u_int16_t		 age;
-	int			 ret;
 
-	/* XXX READ_BUF_SIZE */
-	if ((buf = buf_dynamic(PKG_DEF_SIZE, READ_BUF_SIZE)) == NULL)
+	if ((buf = buf_open(iface->mtu - sizeof(struct ip))) == NULL)
 		fatal("send_ls_update");
 
-	/* set destination */
-	dst.sin_family = AF_INET;
-	dst.sin_len = sizeof(struct sockaddr_in);
-	dst.sin_addr.s_addr = addr.s_addr;
-
 	/* OSPF header */
 	if (gen_ospf_hdr(buf, iface, PACKET_TYPE_LS_UPDATE))
 		goto fail;
 
-	nlsa = htonl(1);
-	if (buf_add(buf, &nlsa, sizeof(nlsa)))
+	/* reserve space for number of lsa field */
+	if (buf_reserve(buf, sizeof(u_int32_t)) == NULL)
 		goto fail;
 
+	return (buf);
+fail:
+	log_warn("prepare_ls_update");
+	buf_free(buf);
+	return (NULL);
+}
+
+int
+add_ls_update(struct buf *buf, struct iface *iface, void *data, int len)
+{
+	size_t			 pos;
+	u_int16_t		 age;
+
+	if (buf->wpos + len >= buf->max - MD5_DIGEST_LENGTH)
+		return (0);
+
 	pos = buf->wpos;
-	if (buf_add(buf, data, len))
-		goto fail;
+	if (buf_add(buf, data, len)) {
+		log_warn("add_ls_update");
+		return (0);
+	}
 
 	/* age LSA before sending it out */
 	memcpy(&age, data, sizeof(age));
@@ -180,10 +191,30 @@ send_ls_update(struct iface *iface, struct in_addr addr, void *data, int len)
 	age = htons(age);
 	memcpy(buf_seek(buf, pos, sizeof(age)), &age, sizeof(age));
 
+	return (1);
+}
+
+
+	
+int
+send_ls_update(struct buf *buf, struct iface *iface, struct in_addr addr,
+    u_int32_t nlsa)
+{
+	struct sockaddr_in	 dst;
+	int			 ret;
+
+	nlsa = htonl(nlsa);
+	memcpy(buf_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->buf, buf->wpos, &dst);
 
 	buf_free(buf);
@@ -254,7 +285,8 @@ recv_ls_update(struct nbr *nbr, char *buf, u_int16_t len)
 
 /* link state retransmit list */
 void
-ls_retrans_list_add(struct nbr *nbr, struct lsa_hdr *lsa)
+ls_retrans_list_add(struct nbr *nbr, struct lsa_hdr *lsa,
+    unsigned short timeout, unsigned short oneshot)
 {
 	struct timeval		 tv;
 	struct lsa_entry	*le;
@@ -267,11 +299,14 @@ ls_retrans_list_add(struct nbr *nbr, struct lsa_hdr *lsa)
 		fatal("ls_retrans_list_add");
 
 	le->le_ref = ref;
-	TAILQ_INSERT_TAIL(&nbr->ls_retrans_list, le, entry);
+	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 = nbr->iface->rxmt_interval;
+		tv.tv_sec = TAILQ_FIRST(&nbr->ls_retrans_list)->le_when;
 
 		if (evtimer_add(&nbr->ls_retrans_timer, &tv) == -1)
 			log_warn("ls_retrans_list_add: evtimer_add failed");
@@ -313,10 +348,56 @@ ls_retrans_list_get(struct nbr *nbr, struct lsa_hdr *lsa_hdr)
 }
 
 void
-ls_retrans_list_free(struct nbr *nbr, struct lsa_entry *le)
+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);
+			return;
+		}
+		when -= le->le_when;
+	}
+	new->le_when = when;
+	TAILQ_INSERT_TAIL(&nbr->ls_retrans_list, new, entry);
+}
+
+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);
 
+	if (reset && TAILQ_FIRST(&nbr->ls_retrans_list)) {
+		evtimer_del(&nbr->ls_retrans_timer);
+
+		timerclear(&tv);
+		tv.tv_sec = TAILQ_FIRST(&nbr->ls_retrans_list)->le_when;
+
+		if (evtimer_add(&nbr->ls_retrans_timer, &tv) == -1)
+			log_warn("ls_retrans_timer: evtimer_add failed");
+	}
+}
+
+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);
 }
@@ -343,35 +424,62 @@ ls_retrans_timer(int fd, short event, void *bula)
 	struct in_addr		 addr;
 	struct nbr		*nbr = bula;
 	struct lsa_entry	*le;
+	struct buf		*buf;
+	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 */
+	
 	if (nbr->iface->self == nbr) {
-		if (!(nbr->iface->state & IF_STA_DROTHER)) {
+		/*
+		 * 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) {
 			/*
-			 * Iick, we are suddenly DR or BDDR so convert this
-			 * retrans list into a real flood. I'm not 100% sure if
-			 * using iface->self as originator is correct but we
-			 * will flood the whole net with this and that's the
-			 * idea.
+			 * old retransmission needs to be converted into
+			 * flood by rerunning the lsa_flood.
 			 */
-			while ((le = TAILQ_FIRST(&nbr->ls_retrans_list)) !=
-			    NULL) {
-				lsa_flood(nbr->iface, nbr, &le->le_ref->hdr,
-				    le->le_ref->data, le->le_ref->len);
-				ls_retrans_list_free(nbr, le);
-			}
+			lsa_flood(nbr->iface, nbr, &le->le_ref->hdr,
+			    le->le_ref->data, le->le_ref->len);
+			ls_retrans_list_free(nbr, le);
+			/* ls_retrans_list_free retriggers the timer */
 			return;
-		}
-		inet_aton(AllDRouters, &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;
+	}
 
-	if ((le = TAILQ_FIRST(&nbr->ls_retrans_list)) != NULL) {
-		send_ls_update(nbr->iface, addr, le->le_ref->data,
-		    le->le_ref->len);
+	while ((le = TAILQ_FIRST(&nbr->ls_retrans_list)) != NULL &&
+	    le->le_when == 0) {
+		if (add_ls_update(buf, nbr->iface, le->le_ref->data,
+		    le->le_ref->len) == 0)
+			break;
+		nlsa++;
+		if (le->le_oneshot)
+			ls_retrans_list_free(nbr, le);
+		else {
+			TAILQ_REMOVE(&nbr->ls_retrans_list, le, entry);
+			le->le_when = nbr->iface->rxmt_interval;
+			ls_retrans_list_insert(nbr, le);
+		}		
+	}
+	send_ls_update(buf, nbr->iface, addr, nlsa);
 
+done:
+	if ((le = TAILQ_FIRST(&nbr->ls_retrans_list)) != NULL) {
 		timerclear(&tv);
-		tv.tv_sec = nbr->iface->rxmt_interval;
+		tv.tv_sec = le->le_when;
 
 		if (evtimer_add(&nbr->ls_retrans_timer, &tv) == -1)
 			log_warn("ls_retrans_timer: evtimer_add failed");
diff --git a/usr.sbin/ospfd/ospfe.c b/usr.sbin/ospfd/ospfe.c
index 40c2db820b9..f8ea9d59df2 100644
--- a/usr.sbin/ospfd/ospfe.c
+++ b/usr.sbin/ospfd/ospfe.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: ospfe.c,v 1.35 2005/12/15 20:30:44 claudio Exp $ */
+/*	$OpenBSD: ospfe.c,v 1.36 2005/12/29 13:53:36 claudio Exp $ */
 
 /*
  * Copyright (c) 2005 Claudio Jeker <claudio@openbsd.org>
@@ -485,15 +485,14 @@ ospfe_dispatch_rde(int fd, short event, void *bula)
 				break;
 
 			memcpy(&age, imsg.data, sizeof(age));
-			if (ntohs(age) >= MAX_AGE) {
+			ref = lsa_cache_add(imsg.data, l);
+			if (ntohs(age) >= MAX_AGE)
 				/* add to retransmit list */
-				ref = lsa_cache_add(imsg.data, l);
-				ls_retrans_list_add(nbr, imsg.data);
-				lsa_cache_put(ref, nbr);
-			}
+				ls_retrans_list_add(nbr, imsg.data, 0, 0);
+			else
+				ls_retrans_list_add(nbr, imsg.data, 0, 1);
 
-			/* send direct don't add to retransmit list */
-			send_ls_update(nbr->iface, nbr->addr, imsg.data, l);
+			lsa_cache_put(ref, nbr);
 			break;
 		case IMSG_LS_ACK:
 			/*
diff --git a/usr.sbin/ospfd/ospfe.h b/usr.sbin/ospfd/ospfe.h
index 436cab69fbd..d7f34dc5e53 100644
--- a/usr.sbin/ospfd/ospfe.h
+++ b/usr.sbin/ospfd/ospfe.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: ospfe.h,v 1.19 2005/12/15 20:29:06 claudio Exp $ */
+/*	$OpenBSD: ospfe.h,v 1.20 2005/12/29 13:53:36 claudio Exp $ */
 
 /*
  * Copyright (c) 2004, 2005 Esben Norby <norby@openbsd.org>
@@ -87,6 +87,8 @@ struct lsa_entry {
 		struct lsa_hdr	*lu_lsa;
 		struct lsa_ref	*lu_ref;
 	}			 le_data;
+	unsigned short		 le_when;
+	unsigned short		 le_oneshot;
 };
 #define	le_lsa	le_data.lu_lsa
 #define	le_ref	le_data.lu_ref
@@ -235,10 +237,10 @@ int	 stop_ls_req_tx_timer(struct nbr *);
 /* lsupdate.c */
 int		 lsa_flood(struct iface *, struct nbr *, struct lsa_hdr *,
 		     void *, u_int16_t);
-int		 send_ls_update(struct iface *, struct in_addr, void *, int);
 void		 recv_ls_update(struct nbr *, char *, u_int16_t);
 
-void		 ls_retrans_list_add(struct nbr *, struct lsa_hdr *);
+void		 ls_retrans_list_add(struct nbr *, struct lsa_hdr *,
+		     unsigned short, unsigned short);
 int		 ls_retrans_list_del(struct nbr *, struct lsa_hdr *);
 struct lsa_entry	*ls_retrans_list_get(struct nbr *, struct lsa_hdr *);
 void		 ls_retrans_list_free(struct nbr *, struct lsa_entry *);