eigrpd: Convert topology list to a table

The EIGRP topology list is an extremely inefficient
way to store data about the known routes.  Convert
to using a table.

Signed-off-by: Donald Sharp <sharpd@cumulusnetorks.com>

6 files changed, 150 insertions, 119 deletions

diff --git a/eigrpd/eigrp_structs.h b/eigrpd/eigrp_structs.h
index 4441f5d004..324181c21e 100644
--- a/eigrpd/eigrp_structs.h
+++ b/eigrpd/eigrp_structs.h
@@ -100,7 +100,7 @@ struct eigrp {
 
 	struct route_table *networks; /* EIGRP config networks. */
 
-	struct list *topology_table;
+	struct route_table *topology_table;
 
 	uint64_t serno; /* Global serial number counter for topology entry
 			   changes*/
diff --git a/eigrpd/eigrp_topology.c b/eigrpd/eigrp_topology.c
index 94775622d9..7d352b8bed 100644
--- a/eigrpd/eigrp_topology.c
+++ b/eigrpd/eigrp_topology.c
@@ -51,9 +51,6 @@
 #include "eigrpd/eigrp_fsm.h"
 #include "eigrpd/eigrp_memory.h"
 
-static int eigrp_prefix_entry_cmp(struct eigrp_prefix_entry *,
-				  struct eigrp_prefix_entry *);
-static void eigrp_prefix_entry_del(struct eigrp_prefix_entry *);
 static int eigrp_nexthop_entry_cmp(struct eigrp_nexthop_entry *,
 				    struct eigrp_nexthop_entry *);
 
@@ -63,45 +60,9 @@ static int eigrp_nexthop_entry_cmp(struct eigrp_nexthop_entry *,
  * del - assigned function executed before deleting topology node by list
  * function
  */
-struct list *eigrp_topology_new()
+struct route_table *eigrp_topology_new()
 {
-	struct list *new = list_new();
-	new->cmp = (int (*)(void *, void *))eigrp_prefix_entry_cmp;
-	new->del = (void (*)(void *))eigrp_prefix_entry_del;
-
-	return new;
-}
-
-/*
- * Topology node comparison
- */
-
-static int eigrp_prefix_entry_cmp(struct eigrp_prefix_entry *node1,
-				  struct eigrp_prefix_entry *node2)
-{
-	if (node1->af == AF_INET) {
-		if (node2->af == AF_INET) {
-			if (node1->destination->u.prefix4.s_addr
-			    < node2->destination->u.prefix4.s_addr)
-				return -1;
-			if (node1->destination->u.prefix4.s_addr
-			    > node2->destination->u.prefix4.s_addr)
-				return 1;
-			else
-				return 0;
-		} else
-			return 1;
-	} else
-		return 1;
-}
-
-/*
- * Topology node delete
- */
-
-static void eigrp_prefix_entry_del(struct eigrp_prefix_entry *node)
-{
-	list_delete_and_null(&node->entries);
+	return route_table_init();
 }
 
 /*
@@ -155,30 +116,41 @@ struct eigrp_nexthop_entry *eigrp_nexthop_entry_new()
 /*
  * Freeing topology table list
  */
-void eigrp_topology_free(struct list *list)
+void eigrp_topology_free(struct route_table *table)
 {
-	list_delete_and_null(&list);
+	route_table_finish(table);
 }
 
 /*
  * Deleting all topology nodes in table
  */
-void eigrp_topology_cleanup(struct list *topology)
+void eigrp_topology_cleanup(struct route_table *table)
 {
-	assert(topology);
-
-	eigrp_topology_delete_all(topology);
+	eigrp_topology_delete_all(table);
 }
 
 /*
  * Adding topology node to topology table
  */
-void eigrp_prefix_entry_add(struct list *topology,
-			    struct eigrp_prefix_entry *node)
+void eigrp_prefix_entry_add(struct route_table *topology,
+			    struct eigrp_prefix_entry *pe)
 {
-	if (listnode_lookup(topology, node) == NULL) {
-		listnode_add_sort(topology, node);
+	struct route_node *rn;
+
+	rn = route_node_get(topology, pe->destination);
+	if (rn->info) {
+		if (IS_DEBUG_EIGRP_EVENT) {
+			char buf[PREFIX_STRLEN];
+
+			zlog_debug("%s: %s Should we have found this entry in the topo table?",
+				   __PRETTY_FUNCTION__,
+				   prefix2str(pe->destination, buf,
+					      sizeof(buf)));
+		}
 	}
+
+	rn->info = pe;
+	route_lock_node(rn);
 }
 
 /*
@@ -204,24 +176,30 @@ void eigrp_nexthop_entry_add(struct eigrp_prefix_entry *node,
 /*
  * Deleting topology node from topology table
  */
-void eigrp_prefix_entry_delete(struct list *topology,
-			       struct eigrp_prefix_entry *node)
+void eigrp_prefix_entry_delete(struct route_table *table,
+			       struct eigrp_prefix_entry *pe)
 {
 	struct eigrp *eigrp = eigrp_lookup();
+	struct route_node *rn;
+
+	rn = route_node_lookup(table, pe->destination);
+	if (!rn)
+		return;
 
 	/*
 	 * Emergency removal of the node from this list.
 	 * Whatever it is.
 	 */
-	listnode_delete(eigrp->topology_changes_internalIPV4, node);
+	listnode_delete(eigrp->topology_changes_internalIPV4, pe);
 
-	if (listnode_lookup(topology, node) != NULL) {
-		list_delete_and_null(&node->entries);
-		list_delete_and_null(&node->rij);
-		listnode_delete(topology, node);
-		eigrp_zebra_route_delete(node->destination);
-		XFREE(MTYPE_EIGRP_PREFIX_ENTRY, node);
-	}
+	list_delete_and_null(&pe->entries);
+	list_delete_and_null(&pe->rij);
+	eigrp_zebra_route_delete(pe->destination);
+
+	rn->info = NULL;
+	route_unlock_node(rn);  //Lookup above
+	route_unlock_node(rn);  //Initial creation
+	XFREE(MTYPE_EIGRP_PREFIX_ENTRY, pe);
 }
 
 /*
@@ -240,9 +218,19 @@ void eigrp_nexthop_entry_delete(struct eigrp_prefix_entry *node,
 /*
  * Deleting all nodes from topology table
  */
-void eigrp_topology_delete_all(struct list *topology)
+void eigrp_topology_delete_all(struct route_table *topology)
 {
-	list_delete_all_node(topology);
+	struct route_node *rn;
+	struct eigrp_prefix_entry *pe;
+
+	for (rn = route_top(topology); rn; rn = route_next(rn)) {
+		pe = rn->info;
+
+		if (!pe)
+			continue;
+
+		eigrp_prefix_entry_delete(topology, pe);
+	}
 }
 
 /*
@@ -258,17 +246,21 @@ unsigned int eigrp_topology_table_isempty(struct list *topology)
 }
 
 struct eigrp_prefix_entry *
-eigrp_topology_table_lookup_ipv4(struct list *topology_table,
+eigrp_topology_table_lookup_ipv4(struct route_table *table,
 				 struct prefix *address)
 {
-	struct eigrp_prefix_entry *data;
-	struct listnode *node;
-	for (ALL_LIST_ELEMENTS_RO(topology_table, node, data)) {
-		if (prefix_same(data->destination, address))
-			return data;
-	}
+	struct eigrp_prefix_entry *pe;
+	struct route_node *rn;
 
-	return NULL;
+	rn = route_node_lookup(table, address);
+	if (!rn)
+		return NULL;
+
+	pe = rn->info;
+
+	route_unlock_node(rn);
+
+	return pe;
 }
 
 /*
@@ -337,20 +329,24 @@ eigrp_prefix_entry_lookup(struct list *entries, struct eigrp_neighbor *nbr)
 struct list *eigrp_neighbor_prefixes_lookup(struct eigrp *eigrp,
 					    struct eigrp_neighbor *nbr)
 {
-	struct listnode *node1, *node11, *node2, *node22;
-	struct eigrp_prefix_entry *prefix;
+	struct listnode *node2, *node22;
 	struct eigrp_nexthop_entry *entry;
+	struct eigrp_prefix_entry *pe;
+	struct route_node *rn;
 
 	/* create new empty list for prefixes storage */
 	struct list *prefixes = list_new();
 
 	/* iterate over all prefixes in topology table */
-	for (ALL_LIST_ELEMENTS(eigrp->topology_table, node1, node11, prefix)) {
+	for (rn = route_top(eigrp->topology_table); rn; rn = route_next(rn)) {
+		if (!rn->info)
+			continue;
+		pe = rn->info;
 		/* iterate over all neighbor entry in prefix */
-		for (ALL_LIST_ELEMENTS(prefix->entries, node2, node22, entry)) {
+		for (ALL_LIST_ELEMENTS(pe->entries, node2, node22, entry)) {
 			/* if entry is from specified neighbor, add to list */
 			if (entry->adv_router == nbr) {
-				listnode_add(prefixes, prefix);
+				listnode_add(prefixes, pe);
 			}
 		}
 	}
@@ -426,11 +422,16 @@ enum metric_change eigrp_topology_update_distance(struct eigrp_fsm_action_messag
 
 void eigrp_topology_update_all_node_flags(struct eigrp *eigrp)
 {
-	struct list *table = eigrp->topology_table;
-	struct eigrp_prefix_entry *data;
-	struct listnode *node, *nnode;
-	for (ALL_LIST_ELEMENTS(table, node, nnode, data)) {
-		eigrp_topology_update_node_flags(data);
+	struct eigrp_prefix_entry *pe;
+	struct route_node *rn;
+
+	for (rn = route_top(eigrp->topology_table); rn; rn = route_next(rn)) {
+		pe = rn->info;
+
+		if (!pe)
+			continue;
+
+		eigrp_topology_update_node_flags(pe);
 	}
 }
 
@@ -484,12 +485,18 @@ void eigrp_update_routing_table(struct eigrp_prefix_entry *prefix)
 void eigrp_topology_neighbor_down(struct eigrp *eigrp,
 				  struct eigrp_neighbor *nbr)
 {
-	struct listnode *node1, *node11, *node2, *node22;
-	struct eigrp_prefix_entry *prefix;
+	struct listnode *node2, *node22;
+	struct eigrp_prefix_entry *pe;
 	struct eigrp_nexthop_entry *entry;
+	struct route_node *rn;
+
+	for (rn = route_top(eigrp->topology_table); rn; rn = route_next(rn)) {
+		pe = rn->info;
+
+		if (!pe)
+			continue;
 
-	for (ALL_LIST_ELEMENTS(eigrp->topology_table, node1, node11, prefix)) {
-		for (ALL_LIST_ELEMENTS(prefix->entries, node2, node22, entry)) {
+		for (ALL_LIST_ELEMENTS(pe->entries, node2, node22, entry)) {
 			struct eigrp_fsm_action_message msg;
 
 			if (entry->adv_router != nbr)
@@ -501,7 +508,7 @@ void eigrp_topology_neighbor_down(struct eigrp *eigrp,
 			msg.data_type = EIGRP_INT;
 			msg.adv_router = nbr;
 			msg.entry = entry;
-			msg.prefix = prefix;
+			msg.prefix = pe;
 			eigrp_fsm_event(&msg);
 		}
 	}
@@ -510,7 +517,7 @@ void eigrp_topology_neighbor_down(struct eigrp *eigrp,
 	eigrp_update_send_all(eigrp, nbr->ei);
 }
 
-void eigrp_update_topology_table_prefix(struct list *table,
+void eigrp_update_topology_table_prefix(struct route_table *table,
 					struct eigrp_prefix_entry *prefix)
 {
 	struct listnode *node1, *node2;
diff --git a/eigrpd/eigrp_topology.h b/eigrpd/eigrp_topology.h
index ef5b32d5bf..c8772c8c3a 100644
--- a/eigrpd/eigrp_topology.h
+++ b/eigrpd/eigrp_topology.h
@@ -33,23 +33,25 @@
 #define _ZEBRA_EIGRP_TOPOLOGY_H
 
 /* EIGRP Topology table related functions. */
-extern struct list *eigrp_topology_new(void);
-extern void eigrp_topology_init(struct list *);
+extern struct route_table *eigrp_topology_new(void);
+extern void eigrp_topology_init(struct route_table *table);
 extern struct eigrp_prefix_entry *eigrp_prefix_entry_new(void);
 extern struct eigrp_nexthop_entry *eigrp_nexthop_entry_new(void);
-extern void eigrp_topology_free(struct list *);
-extern void eigrp_topology_cleanup(struct list *);
-extern void eigrp_prefix_entry_add(struct list *, struct eigrp_prefix_entry *);
+extern void eigrp_topology_free(struct route_table *table);
+extern void eigrp_topology_cleanup(struct route_table *table);
+extern void eigrp_prefix_entry_add(struct route_table *table,
+				   struct eigrp_prefix_entry *pe);
 extern void eigrp_nexthop_entry_add(struct eigrp_prefix_entry *,
 				     struct eigrp_nexthop_entry *);
-extern void eigrp_prefix_entry_delete(struct list *,
-				      struct eigrp_prefix_entry *);
+extern void eigrp_prefix_entry_delete(struct route_table *table,
+				      struct eigrp_prefix_entry *pe);
 extern void eigrp_nexthop_entry_delete(struct eigrp_prefix_entry *,
 					struct eigrp_nexthop_entry *);
-extern void eigrp_topology_delete_all(struct list *);
+extern void eigrp_topology_delete_all(struct route_table *table);
 extern unsigned int eigrp_topology_table_isempty(struct list *);
 extern struct eigrp_prefix_entry *
-eigrp_topology_table_lookup_ipv4(struct list *, struct prefix *);
+eigrp_topology_table_lookup_ipv4(struct route_table *table,
+				 struct prefix *p);
 extern struct list *eigrp_topology_get_successor(struct eigrp_prefix_entry *);
 extern struct list *
 eigrp_topology_get_successor_max(struct eigrp_prefix_entry *pe,
@@ -64,7 +66,7 @@ extern enum metric_change eigrp_topology_update_distance(struct eigrp_fsm_action
 extern void eigrp_update_routing_table(struct eigrp_prefix_entry *);
 extern void eigrp_topology_neighbor_down(struct eigrp *,
 					 struct eigrp_neighbor *);
-extern void eigrp_update_topology_table_prefix(struct list *,
-					       struct eigrp_prefix_entry *);
+extern void eigrp_update_topology_table_prefix(struct route_table *table,
+					       struct eigrp_prefix_entry *pe);
 
 #endif
diff --git a/eigrpd/eigrp_update.c b/eigrpd/eigrp_update.c
index 4a86b48944..b4d1c58870 100644
--- a/eigrpd/eigrp_update.c
+++ b/eigrpd/eigrp_update.c
@@ -530,13 +530,15 @@ void eigrp_update_send_EOT(struct eigrp_neighbor *nbr)
 	u_int16_t length = EIGRP_HEADER_LEN;
 	struct eigrp_nexthop_entry *te;
 	struct eigrp_prefix_entry *pe;
-	struct listnode *node, *node2, *nnode, *nnode2;
+	struct listnode *node2, *nnode2;
 	struct eigrp_interface *ei = nbr->ei;
 	struct eigrp *eigrp = ei->eigrp;
 	struct prefix *dest_addr;
 	u_int32_t seq_no = eigrp->sequence_number;
+	u_int16_t mtu = ei->ifp->mtu;
+	struct route_node *rn;
 
-	ep = eigrp_packet_new(ei->ifp->mtu, nbr);
+	ep = eigrp_packet_new(mtu, nbr);
 
 	/* Prepare EIGRP EOT UPDATE header */
 	eigrp_packet_header_init(EIGRP_OPC_UPDATE, eigrp,
@@ -549,20 +551,26 @@ void eigrp_update_send_EOT(struct eigrp_neighbor *nbr)
 		length += eigrp_add_authTLV_MD5_to_stream(ep->s,ei);
 	}
 
-	for (ALL_LIST_ELEMENTS(eigrp->topology_table, node, nnode, pe)) {
+	for (rn = route_top(eigrp->topology_table); rn; rn = route_next(rn)) {
+		if (!rn->info)
+			continue;
+
+		pe = rn->info;
 		for (ALL_LIST_ELEMENTS(pe->entries, node2, nnode2, te)) {
 			if (eigrp_nbr_split_horizon_check(te, ei))
 				continue;
 
-			if ((length + 0x001D) > (u_int16_t)ei->ifp->mtu) {
+			if ((length + 0x001D) > mtu) {
 				eigrp_update_place_on_nbr_queue (nbr, ep, seq_no, length);
 				seq_no++;
 
 				length = EIGRP_HEADER_LEN;
-				ep = eigrp_packet_new(ei->ifp->mtu, nbr);
-				eigrp_packet_header_init(EIGRP_OPC_UPDATE, eigrp,
+				ep = eigrp_packet_new(mtu, nbr);
+				eigrp_packet_header_init(EIGRP_OPC_UPDATE,
+							 nbr->ei->eigrp,
 							 ep->s, EIGRP_EOT_FLAG,
-							 seq_no, nbr->recv_sequence_number);
+							 seq_no,
+							 nbr->recv_sequence_number);
 
 				if((ei->params.auth_type == EIGRP_AUTH_TYPE_MD5) &&
 				   (ei->params.auth_keychain != NULL))
@@ -736,7 +744,6 @@ static void eigrp_update_send_GR_part(struct eigrp_neighbor *nbr)
 {
 	struct eigrp_packet *ep;
 	u_int16_t length = EIGRP_HEADER_LEN;
-	struct listnode *node, *nnode;
 	struct eigrp_prefix_entry *pe;
 	struct prefix *dest_addr;
 	struct eigrp_interface *ei = nbr->ei;
@@ -744,6 +751,7 @@ static void eigrp_update_send_GR_part(struct eigrp_neighbor *nbr)
 	struct list *prefixes;
 	u_int32_t flags;
 	unsigned int send_prefixes;
+	struct route_node *rn;
 
 	/* get prefixes to send to neighbor */
 	prefixes = nbr->nbr_gr_prefixes_send;
@@ -795,7 +803,11 @@ static void eigrp_update_send_GR_part(struct eigrp_neighbor *nbr)
 		length += eigrp_add_authTLV_MD5_to_stream(ep->s, ei);
 	}
 
-	for (ALL_LIST_ELEMENTS(eigrp->topology_table, node, nnode, pe)) {
+	for (rn = route_top(eigrp->topology_table); rn; rn = route_next(rn)) {
+		if (!rn->info)
+			continue;
+
+		pe = rn->info;
 		/*
 		 * Filtering
 		 */
@@ -945,35 +957,40 @@ void eigrp_update_send_GR(struct eigrp_neighbor *nbr, enum GR_type gr_type,
 			  struct vty *vty)
 {
 	struct eigrp_prefix_entry *pe2;
-	struct listnode *node2, *nnode2;
 	struct list *prefixes;
+	struct route_node *rn;
+	struct eigrp_interface *ei = nbr->ei;
+	struct eigrp *eigrp = ei->eigrp;
 
 	if (gr_type == EIGRP_GR_FILTER) {
 		/* function was called after applying filtration */
 		zlog_info(
 			"Neighbor %s (%s) is resync: route configuration changed",
 			inet_ntoa(nbr->src),
-			ifindex2ifname(nbr->ei->ifp->ifindex, VRF_DEFAULT));
+			ifindex2ifname(ei->ifp->ifindex, VRF_DEFAULT));
 	} else if (gr_type == EIGRP_GR_MANUAL) {
 		/* Graceful restart was called manually */
 		zlog_info("Neighbor %s (%s) is resync: manually cleared",
 			  inet_ntoa(nbr->src),
-			  ifindex2ifname(nbr->ei->ifp->ifindex, VRF_DEFAULT));
+			  ifindex2ifname(ei->ifp->ifindex, VRF_DEFAULT));
 
 		if (vty != NULL) {
 			vty_time_print(vty, 0);
 			vty_out(vty,
 				"Neighbor %s (%s) is resync: manually cleared\n",
 				inet_ntoa(nbr->src),
-				ifindex2ifname(nbr->ei->ifp->ifindex,
+				ifindex2ifname(ei->ifp->ifindex,
 					       VRF_DEFAULT));
 		}
 	}
 
 	prefixes = list_new();
 	/* add all prefixes from topology table to list */
-	for (ALL_LIST_ELEMENTS(nbr->ei->eigrp->topology_table, node2, nnode2,
-			       pe2)) {
+	for (rn = route_top(eigrp->topology_table); rn; rn = route_next(rn)) {
+		if (!rn->info)
+			continue;
+
+		pe2 = rn->info;
 		listnode_add(prefixes, pe2);
 	}
 
diff --git a/eigrpd/eigrp_vty.c b/eigrpd/eigrp_vty.c
index d93abbb8b7..34a07f5fe3 100644
--- a/eigrpd/eigrp_vty.c
+++ b/eigrpd/eigrp_vty.c
@@ -466,9 +466,10 @@ DEFUN (show_ip_eigrp_topology,
        "Show all links in topology table\n")
 {
 	struct eigrp *eigrp;
-	struct listnode *node, *node2;
+	struct listnode *node;
 	struct eigrp_prefix_entry *tn;
 	struct eigrp_nexthop_entry *te;
+	struct route_node *rn;
 	int first;
 
 	eigrp = eigrp_lookup();
@@ -479,9 +480,13 @@ DEFUN (show_ip_eigrp_topology,
 
 	show_ip_eigrp_topology_header(vty, eigrp);
 
-	for (ALL_LIST_ELEMENTS_RO(eigrp->topology_table, node, tn)) {
+	for (rn = route_top(eigrp->topology_table); rn; rn = route_next(rn)) {
+		if (!rn->info)
+			continue;
+
+		tn = rn->info;
 		first = 1;
-		for (ALL_LIST_ELEMENTS_RO(tn->entries, node2, te)) {
+		for (ALL_LIST_ELEMENTS_RO(tn->entries, node, te)) {
 			if (argc == 5
 			    || (((te->flags
 				  & EIGRP_NEXTHOP_ENTRY_SUCCESSOR_FLAG)
diff --git a/eigrpd/eigrpd.c b/eigrpd/eigrpd.c
index a8173f4efd..42d398458e 100644
--- a/eigrpd/eigrpd.c
+++ b/eigrpd/eigrpd.c
@@ -158,7 +158,7 @@ static struct eigrp *eigrp_new(const char *AS)
 	/* init internal data structures */
 	eigrp->eiflist = list_new();
 	eigrp->passive_interface_default = EIGRP_IF_ACTIVE;
-	eigrp->networks = route_table_init();
+	eigrp->networks = eigrp_topology_new();
 
 	if ((eigrp_socket = eigrp_sock_init()) < 0) {
 		zlog_err(
@@ -181,7 +181,7 @@ static struct eigrp *eigrp_new(const char *AS)
 	thread_add_read(master, eigrp_read, eigrp, eigrp->fd, &eigrp->t_read);
 	eigrp->oi_write_q = list_new();
 
-	eigrp->topology_table = eigrp_topology_new();
+	eigrp->topology_table = route_table_init();
 
 	eigrp->neighbor_self = eigrp_nbr_new(NULL);
 	eigrp->neighbor_self->src.s_addr = INADDR_ANY;