1 files changed, 242 insertions, 104 deletions

diff --git a/ospfd/ospf_packet.c b/ospfd/ospf_packet.c
index 87aaccad..d35f0a13 100644
--- a/ospfd/ospf_packet.c
+++ b/ospfd/ospf_packet.c
@@ -292,54 +292,66 @@ void ospf_ls_req_event(struct ospf_neighbor *nbr)
 	event_add_event(master, ospf_ls_req_timer, nbr, 0, &nbr->t_ls_req);
 }
 
-/* Cyclic timer function.  Fist registered in ospf_nbr_new () in
-   ospf_neighbor.c  */
-void ospf_ls_upd_timer(struct event *thread)
+/*
+ * OSPF neighbor link state retransmission timer handler. Unicast
+ * unacknowledged LSAs to the neigbhors.
+ */
+void ospf_ls_rxmt_timer(struct event *thread)
 {
 	struct ospf_neighbor *nbr;
+	int retransmit_interval, retransmit_window, rxmt_lsa_count = 0;
 
 	nbr = EVENT_ARG(thread);
-	nbr->t_ls_upd = NULL;
+	nbr->t_ls_rxmt = NULL;
+	retransmit_interval = nbr->v_ls_rxmt;
+	retransmit_window = OSPF_IF_PARAM(nbr->oi, retransmit_window);
 
 	/* Send Link State Update. */
 	if (ospf_ls_retransmit_count(nbr) > 0) {
+		struct ospf_lsa_list_entry *ls_rxmt_list_entry;
+		struct timeval current_time, latest_rxmt_time, next_rxmt_time;
+		struct timeval rxmt_interval = { retransmit_interval, 0 };
+		struct timeval rxmt_window;
 		struct list *update;
-		struct ospf_lsdb *lsdb;
-		int i;
-		int retransmit_interval;
 
-		retransmit_interval =
-			OSPF_IF_PARAM(nbr->oi, retransmit_interval);
+		/*
+		 * Set the retransmission window based on the configured value
+		 * in milliseconds.
+		 */
+		rxmt_window.tv_sec = retransmit_window / 1000;
+		rxmt_window.tv_usec = (retransmit_window % 1000) * 1000;
+
+		/*
+		 * Calculate the latest retransmit time for LSAs transmited in
+		 * this timer pass by adding the retransmission window to the
+		 * current time. Calculate the next retransmission time by adding
+		 * the retransmit interval to the current time.
+		 */
+		monotime(&current_time);
+		timeradd(&current_time, &rxmt_window, &latest_rxmt_time);
+		timeradd(&current_time, &rxmt_interval, &next_rxmt_time);
 
-		lsdb = &nbr->ls_rxmt;
 		update = list_new();
+		while ((ls_rxmt_list_entry =
+				ospf_lsa_list_first(&nbr->ls_rxmt_list))) {
+			if (timercmp(&ls_rxmt_list_entry->list_entry_time,
+				     &latest_rxmt_time, >))
+				break;
 
-		for (i = OSPF_MIN_LSA; i < OSPF_MAX_LSA; i++) {
-			struct route_table *table = lsdb->type[i].db;
-			struct route_node *rn;
-
-			for (rn = route_top(table); rn; rn = route_next(rn)) {
-				struct ospf_lsa *lsa;
-
-				if ((lsa = rn->info) != NULL) {
-					/* Don't retransmit an LSA if we
-					  received it within
-					  the last RxmtInterval seconds - this
-					  is to allow the
-					  neighbour a chance to acknowledge the
-					  LSA as it may
-					  have ben just received before the
-					  retransmit timer
-					  fired.  This is a small tweak to what
-					  is in the RFC,
-					  but it will cut out out a lot of
-					  retransmit traffic
-					  - MAG */
-					if (monotime_since(&lsa->tv_recv, NULL)
-					    >= retransmit_interval * 1000000LL)
-						listnode_add(update, rn->info);
-				}
-			}
+			listnode_add(update, ls_rxmt_list_entry->lsa);
+			rxmt_lsa_count++;
+
+			/*
+			 * Set the next retransmit time for the LSA and move it
+			 * to the end of the neighbor's retransmission list.
+			 */
+			ls_rxmt_list_entry->list_entry_time = next_rxmt_time;
+			ospf_lsa_list_del(&nbr->ls_rxmt_list,
+					  ls_rxmt_list_entry);
+			ospf_lsa_list_add_tail(&nbr->ls_rxmt_list,
+					       ls_rxmt_list_entry);
+			nbr->ls_rxmt_lsa++;
+			nbr->oi->ls_rxmt_lsa++;
 		}
 
 		if (listcount(update) > 0)
@@ -348,23 +360,25 @@ void ospf_ls_upd_timer(struct event *thread)
 		list_delete(&update);
 	}
 
+	if (IS_DEBUG_OSPF_EVENT)
+		zlog_debug("RXmtL(%lu) NBR(%pI4(%s)) timer event - sent %u LSAs",
+			   ospf_ls_retransmit_count(nbr), &nbr->router_id,
+			   ospf_get_name(nbr->oi->ospf), rxmt_lsa_count);
+
 	/* Set LS Update retransmission timer. */
-	OSPF_NSM_TIMER_ON(nbr->t_ls_upd, ospf_ls_upd_timer, nbr->v_ls_upd);
+	ospf_ls_retransmit_set_timer(nbr);
 }
 
-void ospf_ls_ack_timer(struct event *thread)
+void ospf_ls_ack_delayed_timer(struct event *thread)
 {
 	struct ospf_interface *oi;
 
 	oi = EVENT_ARG(thread);
-	oi->t_ls_ack = NULL;
+	oi->t_ls_ack_delayed = NULL;
 
 	/* Send Link State Acknowledgment. */
-	if (listcount(oi->ls_ack) > 0)
+	if (ospf_lsa_list_count(&oi->ls_ack_delayed))
 		ospf_ls_ack_send_delayed(oi);
-
-	/* Set LS Ack timer. */
-	OSPF_ISM_TIMER_ON(oi->t_ls_ack, ospf_ls_ack_timer, oi->v_ls_ack);
 }
 
 #ifdef WANT_OSPF_WRITE_FRAGMENT
@@ -1803,7 +1817,7 @@ static void ospf_ls_upd(struct ospf *ospf, struct ip *iph,
 		if (IS_LSA_MAXAGE(lsa) && !current
 		    && ospf_check_nbr_status(oi->ospf)) {
 			/* (4a) Response Link State Acknowledgment. */
-			ospf_ls_ack_send(nbr, lsa);
+			ospf_ls_ack_send_direct(nbr, lsa);
 
 			/* (4b) Discard LSA. */
 			if (IS_DEBUG_OSPF(lsa, LSA)) {
@@ -1828,7 +1842,7 @@ static void ospf_ls_upd(struct ospf *ospf, struct ip *iph,
 			if (IS_LSA_MAXAGE(lsa)) {
 				zlog_info("LSA[%s]: Boomerang effect?",
 					  dump_lsa_key(lsa));
-				ospf_ls_ack_send(nbr, lsa);
+				ospf_ls_ack_send_direct(nbr, lsa);
 				ospf_lsa_discard(lsa);
 
 				if (current != NULL && !IS_LSA_MAXAGE(current))
@@ -1862,7 +1876,7 @@ static void ospf_ls_upd(struct ospf *ospf, struct ip *iph,
 
 				SET_FLAG(lsa->flags, OSPF_LSA_SELF);
 
-				ospf_ls_ack_send(nbr, lsa);
+				ospf_ls_ack_send_direct(nbr, lsa);
 
 				if (!ospf->gr_info.restart_in_progress) {
 					ospf_opaque_self_originated_lsa_received(
@@ -2001,9 +2015,8 @@ static void ospf_ls_upd(struct ospf *ospf, struct ip *iph,
 				   */
 				if (oi->state == ISM_Backup)
 					if (NBR_IS_DR(nbr))
-						listnode_add(
-							oi->ls_ack,
-							ospf_lsa_lock(lsa));
+						ospf_ls_ack_send_direct(nbr,
+									lsa);
 
 				DISCARD_LSA(lsa, 6);
 			} else
@@ -2012,7 +2025,7 @@ static void ospf_ls_upd(struct ospf *ospf, struct ip *iph,
 			   receiving
 			   interface. */
 			{
-				ospf_ls_ack_send(nbr, lsa);
+				ospf_ls_ack_send_direct(nbr, lsa);
 				DISCARD_LSA(lsa, 7);
 			}
 		}
@@ -2793,9 +2806,7 @@ static enum ospf_read_return_enum ospf_read_helper(struct ospf *ospf)
 	 * or header area is backbone but ospf_interface is not
 	 * check for VLINK interface
 	 */
-	if ((oi == NULL)
-	    || (OSPF_IS_AREA_ID_BACKBONE(ospfh->area_id)
-		&& !OSPF_IS_AREA_ID_BACKBONE(oi->area->area_id))) {
+	if (oi == NULL) {
 		if ((oi = ospf_associate_packet_vl(ospf, ifp, iph, ospfh))
 		    == NULL) {
 			if (!ospf->instance && IS_DEBUG_OSPF_EVENT)
@@ -2804,6 +2815,15 @@ static enum ospf_read_return_enum ospf_read_helper(struct ospf *ospf)
 					&iph->ip_src, ifp->name);
 			return OSPF_READ_CONTINUE;
 		}
+	} else if (OSPF_IS_AREA_ID_BACKBONE(ospfh->area_id) &&
+		   !OSPF_IS_AREA_ID_BACKBONE(oi->area->area_id)) {
+		oi = ospf_associate_packet_vl(ospf, ifp, iph, ospfh);
+		if (oi == NULL) {
+			flog_warn(EC_OSPF_PACKET,
+				  "interface %s: ospf_read invalid Area ID %pI4",
+				  ifp->name, &ospfh->area_id);
+			return OSPF_READ_CONTINUE;
+		}
 	}
 
 	/*
@@ -3314,17 +3334,35 @@ static int ospf_make_ls_upd(struct ospf_interface *oi, struct list *update,
 	return length;
 }
 
-static int ospf_make_ls_ack(struct ospf_interface *oi, struct list *ack,
-			    struct stream *s)
+static int ospf_make_ls_ack(struct ospf_interface *oi,
+			    struct ospf_lsa_list_head *ls_ack_list,
+			    bool direct_ack, bool delete_ack, struct stream *s)
 {
-	struct listnode *node, *nnode;
+	struct ospf_lsa_list_entry *ls_ack_list_first;
+	struct ospf_lsa_list_entry *ls_ack_list_entry;
 	uint16_t length = OSPF_LS_ACK_MIN_SIZE;
-	unsigned long delta = OSPF_LSA_HEADER_SIZE;
 	struct ospf_lsa *lsa;
+	struct in_addr first_dst_addr = { INADDR_ANY };
 
-	for (ALL_LIST_ELEMENTS(ack, node, nnode, lsa)) {
+	/*
+	 * For direct LS Acks, assure the destination address doesn't
+	 * change between queued acknowledgments.
+	 */
+	if (direct_ack) {
+		ls_ack_list_first = ospf_lsa_list_first(ls_ack_list);
+		if (ls_ack_list_first)
+			first_dst_addr.s_addr =
+				ls_ack_list_first->list_entry_dst.s_addr;
+	}
+
+	frr_each_safe (ospf_lsa_list, ls_ack_list, ls_ack_list_entry) {
+		lsa = ls_ack_list_entry->lsa;
 		assert(lsa);
 
+		if (direct_ack && (ls_ack_list_entry->list_entry_dst.s_addr !=
+				   first_dst_addr.s_addr))
+			break;
+
 		/* LS Ack packet overflows interface MTU
 		 * delta is just number of bytes required for
 		 * 1 LS Ack(1 LS Hdr) ospf_packet_max will return
@@ -3333,19 +3371,46 @@ static int ospf_make_ls_ack(struct ospf_interface *oi, struct list *ack,
 		 * against ospf_packet_max to check if it can fit
 		 * another ls header in the same packet.
 		 */
-		if ((length + delta) > ospf_packet_max(oi))
+		if ((length + OSPF_LSA_HEADER_SIZE) > ospf_packet_max(oi))
 			break;
 
 		stream_put(s, lsa->data, OSPF_LSA_HEADER_SIZE);
 		length += OSPF_LSA_HEADER_SIZE;
 
-		listnode_delete(ack, lsa);
-		ospf_lsa_unlock(&lsa); /* oi->ls_ack_direct.ls_ack */
+		if (delete_ack) {
+			ospf_lsa_list_del(ls_ack_list, ls_ack_list_entry);
+			XFREE(MTYPE_OSPF_LSA_LIST, ls_ack_list_entry);
+			ospf_lsa_unlock(&lsa);
+		}
 	}
 
 	return length;
 }
 
+/*
+ * On non-braodcast networks, the same LS acks must be sent to multiple
+ * neighbors and deletion must be deferred until after the LS Ack packet
+ * is sent to all neighbors.
+ */
+static void ospf_delete_ls_ack_delayed(struct ospf_interface *oi)
+{
+	struct ospf_lsa_list_entry *ls_ack_list_entry;
+	struct ospf_lsa *lsa;
+	uint16_t length = OSPF_LS_ACK_MIN_SIZE;
+
+	frr_each_safe (ospf_lsa_list, &oi->ls_ack_delayed, ls_ack_list_entry) {
+		lsa = ls_ack_list_entry->lsa;
+		assert(lsa);
+		if ((length + OSPF_LSA_HEADER_SIZE) > ospf_packet_max(oi))
+			break;
+
+		length += OSPF_LSA_HEADER_SIZE;
+		ospf_lsa_list_del(&oi->ls_ack_delayed, ls_ack_list_entry);
+		XFREE(MTYPE_OSPF_LSA_LIST, ls_ack_list_entry);
+		ospf_lsa_unlock(&lsa);
+	}
+}
+
 static void ospf_hello_send_sub(struct ospf_interface *oi, in_addr_t addr)
 {
 	struct ospf_packet *op;
@@ -3917,10 +3982,13 @@ void ospf_ls_upd_send(struct ospf_neighbor *nbr, struct list *update, int flag,
 				&oi->t_ls_upd_event);
 }
 
-static void ospf_ls_ack_send_list(struct ospf_interface *oi, struct list *ack,
+static void ospf_ls_ack_send_list(struct ospf_interface *oi,
+				  struct ospf_lsa_list_head *ls_ack_list,
+				  bool direct_ack, bool delete_ack,
 				  struct in_addr dst)
 {
 	struct ospf_packet *op;
+	struct ospf_lsa_list_entry *ls_ack_list_first;
 	uint16_t length = OSPF_HEADER_SIZE;
 
 	op = ospf_packet_new(oi->ifp->mtu);
@@ -3928,8 +3996,18 @@ static void ospf_ls_ack_send_list(struct ospf_interface *oi, struct list *ack,
 	/* Prepare OSPF common header. */
 	ospf_make_header(OSPF_MSG_LS_ACK, oi, op->s);
 
+	/* Determine the destination address - for direct acks,
+	 * the list entries always include the distination address.
+	 */
+	if (direct_ack) {
+		ls_ack_list_first = ospf_lsa_list_first(ls_ack_list);
+		op->dst.s_addr = ls_ack_list_first->list_entry_dst.s_addr;
+	} else
+		op->dst.s_addr = dst.s_addr;
+
 	/* Prepare OSPF Link State Acknowledgment body. */
-	length += ospf_make_ls_ack(oi, ack, op->s);
+	length += ospf_make_ls_ack(oi, ls_ack_list, direct_ack, delete_ack,
+				   op->s);
 
 	/* Fill OSPF header. */
 	ospf_fill_header(oi, op->s, length);
@@ -3937,14 +4015,6 @@ static void ospf_ls_ack_send_list(struct ospf_interface *oi, struct list *ack,
 	/* Set packet length. */
 	op->length = length;
 
-	/* Decide destination address. */
-	if (oi->type == OSPF_IFTYPE_POINTOPOINT ||
-	    (oi->type == OSPF_IFTYPE_POINTOMULTIPOINT &&
-	     !oi->p2mp_non_broadcast))
-		op->dst.s_addr = htonl(OSPF_ALLSPFROUTERS);
-	else
-		op->dst.s_addr = dst.s_addr;
-
 	/* Add packet to the interface output queue. */
 	ospf_packet_add(oi, op);
 
@@ -3952,34 +4022,96 @@ static void ospf_ls_ack_send_list(struct ospf_interface *oi, struct list *ack,
 	OSPF_ISM_WRITE_ON(oi->ospf);
 }
 
-static void ospf_ls_ack_send_event(struct event *thread)
+static void ospf_ls_ack_send_direct_event(struct event *thread)
 {
 	struct ospf_interface *oi = EVENT_ARG(thread);
+	struct in_addr dst = { INADDR_ANY };
 
 	oi->t_ls_ack_direct = NULL;
 
-	while (listcount(oi->ls_ack_direct.ls_ack))
-		ospf_ls_ack_send_list(oi, oi->ls_ack_direct.ls_ack,
-				      oi->ls_ack_direct.dst);
+	while (ospf_lsa_list_count(&oi->ls_ack_direct))
+		ospf_ls_ack_send_list(oi, &(oi->ls_ack_direct), true, true, dst);
 }
 
-void ospf_ls_ack_send(struct ospf_neighbor *nbr, struct ospf_lsa *lsa)
+void ospf_ls_ack_send_direct(struct ospf_neighbor *nbr, struct ospf_lsa *lsa)
 {
+	struct ospf_lsa_list_entry *ls_ack_list_entry;
 	struct ospf_interface *oi = nbr->oi;
 
+	if (IS_DEBUG_OSPF(lsa, LSA_FLOODING))
+		zlog_debug("%s:Add LSA[Type%d:%pI4:%pI4]: seq 0x%x age %u NBR %pI4 (%s) ack queue",
+			   __func__, lsa->data->type, &lsa->data->id,
+			   &lsa->data->adv_router, ntohl(lsa->data->ls_seqnum),
+			   ntohs(lsa->data->ls_age), &nbr->router_id,
+			   IF_NAME(nbr->oi));
+
+	/*
+	 * On Point-to-Multipoint broadcast-capabile interfaces,
+	 * where direct acks from are sent to the ALLSPFRouters
+	 * address and one direct ack send event, may include LSAs
+	 * from multiple neighbors, there is a possibility of the same
+	 * LSA being processed more than once in the same send event.
+	 * In this case, the instances subsequent to the first can be
+	 * ignored.
+	 */
+	if (oi->type == OSPF_IFTYPE_POINTOMULTIPOINT && !oi->p2mp_non_broadcast) {
+		struct ospf_lsa_list_entry *ls_ack_list_entry;
+		struct ospf_lsa *ack_queue_lsa;
+
+		frr_each (ospf_lsa_list, &oi->ls_ack_direct, ls_ack_list_entry) {
+			ack_queue_lsa = ls_ack_list_entry->lsa;
+			if ((lsa == ack_queue_lsa) ||
+			    ((lsa->data->type == ack_queue_lsa->data->type) &&
+			     (lsa->data->id.s_addr ==
+			      ack_queue_lsa->data->id.s_addr) &&
+			     (lsa->data->adv_router.s_addr ==
+			      ack_queue_lsa->data->adv_router.s_addr) &&
+			     (lsa->data->ls_seqnum ==
+			      ack_queue_lsa->data->ls_seqnum))) {
+				if (IS_DEBUG_OSPF(lsa, LSA_FLOODING))
+					zlog_debug("%s:LSA[Type%d:%pI4:%pI4]: seq 0x%x age %u NBR %pI4 (%s) ack queue duplicate",
+						   __func__, lsa->data->type,
+						   &lsa->data->id,
+						   &lsa->data->adv_router,
+						   ntohl(lsa->data->ls_seqnum),
+						   ntohs(lsa->data->ls_age),
+						   &nbr->router_id,
+						   IF_NAME(nbr->oi));
+				return;
+			}
+		}
+	}
+
 	if (IS_GRACE_LSA(lsa)) {
 		if (IS_DEBUG_OSPF_GR)
 			zlog_debug("%s, Sending GRACE ACK to Restarter.",
 				   __func__);
 	}
 
-	if (listcount(oi->ls_ack_direct.ls_ack) == 0)
-		oi->ls_ack_direct.dst = nbr->address.u.prefix4;
+	ls_ack_list_entry = XCALLOC(MTYPE_OSPF_LSA_LIST,
+				    sizeof(struct ospf_lsa_list_entry));
+
+	/*
+	 * Determine the destination address - Direct LS acknowledgments
+	 * are sent the AllSPFRouters multicast address on Point-to-Point
+	 * and Point-to-Multipoint broadcast-capable interfaces. For all other
+	 * interface types, they are unicast directly to the neighbor.
+	 */
+	if (oi->type == OSPF_IFTYPE_POINTOPOINT ||
+	    (oi->type == OSPF_IFTYPE_POINTOMULTIPOINT &&
+	     !oi->p2mp_non_broadcast))
+		ls_ack_list_entry->list_entry_dst.s_addr =
+			htonl(OSPF_ALLSPFROUTERS);
+	else
+		ls_ack_list_entry->list_entry_dst.s_addr =
+			nbr->address.u.prefix4.s_addr;
 
-	listnode_add(oi->ls_ack_direct.ls_ack, ospf_lsa_lock(lsa));
+	ls_ack_list_entry->lsa = ospf_lsa_lock(lsa);
+	ospf_lsa_list_add_tail(&nbr->oi->ls_ack_direct, ls_ack_list_entry);
 
-	event_add_event(master, ospf_ls_ack_send_event, oi, 0,
-			&oi->t_ls_ack_direct);
+	if (oi->t_ls_ack_direct == NULL)
+		event_add_event(master, ospf_ls_ack_send_direct_event, oi, 0,
+				&oi->t_ls_ack_direct);
 }
 
 /* Send Link State Acknowledgment delayed. */
@@ -3996,33 +4128,39 @@ void ospf_ls_ack_send_delayed(struct ospf_interface *oi)
 		struct ospf_neighbor *nbr;
 		struct route_node *rn;
 
-		for (rn = route_top(oi->nbrs); rn; rn = route_next(rn)) {
-			nbr = rn->info;
+		while (ospf_lsa_list_count(&oi->ls_ack_delayed)) {
+			for (rn = route_top(oi->nbrs); rn; rn = route_next(rn)) {
+				nbr = rn->info;
 
-			if (!nbr)
-				continue;
+				if (!nbr)
+					continue;
 
-			if (nbr != oi->nbr_self && nbr->state >= NSM_Exchange)
-				while (listcount(oi->ls_ack))
-					ospf_ls_ack_send_list(
-						oi, oi->ls_ack,
-						nbr->address.u.prefix4);
+				if (nbr != oi->nbr_self &&
+				    nbr->state >= NSM_Exchange)
+					ospf_ls_ack_send_list(oi,
+							      &oi->ls_ack_delayed,
+							      false, false,
+							      nbr->address.u
+								      .prefix4);
+			}
+			ospf_delete_ls_ack_delayed(oi);
 		}
-		return;
-	}
-	if (oi->type == OSPF_IFTYPE_VIRTUALLINK)
-		dst.s_addr = oi->vl_data->peer_addr.s_addr;
-	else if (oi->state == ISM_DR || oi->state == ISM_Backup)
-		dst.s_addr = htonl(OSPF_ALLSPFROUTERS);
-	else if (oi->type == OSPF_IFTYPE_POINTOPOINT)
-		dst.s_addr = htonl(OSPF_ALLSPFROUTERS);
-	else if (oi->type == OSPF_IFTYPE_POINTOMULTIPOINT)
-		dst.s_addr = htonl(OSPF_ALLSPFROUTERS);
-	else
-		dst.s_addr = htonl(OSPF_ALLDROUTERS);
+	} else {
+		if (oi->type == OSPF_IFTYPE_VIRTUALLINK)
+			dst.s_addr = oi->vl_data->peer_addr.s_addr;
+		else if (oi->state == ISM_DR || oi->state == ISM_Backup)
+			dst.s_addr = htonl(OSPF_ALLSPFROUTERS);
+		else if (oi->type == OSPF_IFTYPE_POINTOPOINT)
+			dst.s_addr = htonl(OSPF_ALLSPFROUTERS);
+		else if (oi->type == OSPF_IFTYPE_POINTOMULTIPOINT)
+			dst.s_addr = htonl(OSPF_ALLSPFROUTERS);
+		else
+			dst.s_addr = htonl(OSPF_ALLDROUTERS);
 
-	while (listcount(oi->ls_ack))
-		ospf_ls_ack_send_list(oi, oi->ls_ack, dst);
+		while (ospf_lsa_list_count(&oi->ls_ack_delayed))
+			ospf_ls_ack_send_list(oi, &oi->ls_ack_delayed, false,
+					      true, dst);
+	}
 }
 
 /*