From 9ca66cc76d19e641780cbc64cc5ee6008ae8648b Mon Sep 17 00:00:00 2001 From: Donald Sharp Date: Fri, 6 Oct 2017 09:19:45 -0400 Subject: [PATCH] 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 --- eigrpd/eigrp_structs.h | 2 +- eigrpd/eigrp_topology.c | 181 +++++++++++++++++++++------------------- eigrpd/eigrp_topology.h | 24 +++--- eigrpd/eigrp_update.c | 47 +++++++---- eigrpd/eigrp_vty.c | 11 ++- eigrpd/eigrpd.c | 4 +- 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; -- 2.39.5