From 8249c046d71aa28784ec4590a985ec97862fd8a3 Mon Sep 17 00:00:00 2001 From: Donald Sharp Date: Sun, 23 Mar 2025 20:28:59 -0400 Subject: [PATCH] eigrpd: Convert the nbrs list to a typesafe hash Convert the ei->nbrs list to a typesafe hash to facilitate quick lookups. Signed-off-by: Donald Sharp --- eigrpd/eigrp_dump.c | 6 ++-- eigrpd/eigrp_hello.c | 4 +-- eigrpd/eigrp_interface.c | 13 +++----- eigrpd/eigrp_neighbor.c | 70 ++++++++++++++++++++++------------------ eigrpd/eigrp_neighbor.h | 5 +++ eigrpd/eigrp_query.c | 8 ++--- eigrpd/eigrp_structs.h | 6 +++- eigrpd/eigrp_update.c | 8 ++--- eigrpd/eigrp_vty.c | 11 +++---- eigrpd/eigrpd.c | 6 ++-- 10 files changed, 74 insertions(+), 63 deletions(-) diff --git a/eigrpd/eigrp_dump.c b/eigrpd/eigrp_dump.c index 2ebabd0efa..231554a098 100644 --- a/eigrpd/eigrp_dump.c +++ b/eigrpd/eigrp_dump.c @@ -81,11 +81,11 @@ static int config_write_debug(struct vty *vty) static int eigrp_neighbor_packet_queue_sum(struct eigrp_interface *ei) { struct eigrp_neighbor *nbr; - struct listnode *node, *nnode; int sum; + sum = 0; - for (ALL_LIST_ELEMENTS(ei->nbrs, node, nnode, nbr)) { + frr_each (eigrp_nbr_hash, &ei->nbr_hash_head, nbr) { sum += nbr->retrans_queue->count; } @@ -152,7 +152,7 @@ void show_ip_eigrp_interface_sub(struct vty *vty, struct eigrp *eigrp, vty_out(vty, "%-16s ", IF_NAME(ei)); vty_out(vty, "%-11u", ei->params.bandwidth); vty_out(vty, "%-11u", ei->params.delay); - vty_out(vty, "%-7u", ei->nbrs->count); + vty_out(vty, "%-7zu", eigrp_nbr_hash_count(&ei->nbr_hash_head)); vty_out(vty, "%u %c %-10u", 0, '/', eigrp_neighbor_packet_queue_sum(ei)); vty_out(vty, "%-7u %-14u %-12u %-8u", 0, 0, 0, 0); diff --git a/eigrpd/eigrp_hello.c b/eigrpd/eigrp_hello.c index ee0e2451a2..bd2b8ccbbd 100644 --- a/eigrpd/eigrp_hello.c +++ b/eigrpd/eigrp_hello.c @@ -496,7 +496,7 @@ static uint16_t eigrp_sequence_encode(struct eigrp *eigrp, struct stream *s) { uint16_t length = EIGRP_TLV_SEQ_BASE_LEN; struct eigrp_interface *ei; - struct listnode *node, *node2, *nnode2; + struct listnode *node; struct eigrp_neighbor *nbr; size_t backup_end, size_end; int found; @@ -510,7 +510,7 @@ static uint16_t eigrp_sequence_encode(struct eigrp *eigrp, struct stream *s) found = 0; for (ALL_LIST_ELEMENTS_RO(eigrp->eiflist, node, ei)) { - for (ALL_LIST_ELEMENTS(ei->nbrs, node2, nnode2, nbr)) { + frr_each (eigrp_nbr_hash, &ei->nbr_hash_head, nbr) { if (nbr->multicast_queue->count > 0) { length += (uint16_t)stream_put_ipv4( s, nbr->src.s_addr); diff --git a/eigrpd/eigrp_interface.c b/eigrpd/eigrp_interface.c index fb8f47e723..05012e63b2 100644 --- a/eigrpd/eigrp_interface.c +++ b/eigrpd/eigrp_interface.c @@ -66,7 +66,7 @@ struct eigrp_interface *eigrp_if_new(struct eigrp *eigrp, struct interface *ifp, ei->type = EIGRP_IFTYPE_BROADCAST; /* Initialize neighbor list. */ - ei->nbrs = list_new(); + eigrp_nbr_hash_init(&ei->nbr_hash_head); ei->crypt_seqnum = frr_sequence32_next(); @@ -102,7 +102,7 @@ int eigrp_if_delete_hook(struct interface *ifp) if (!ei) return 0; - list_delete(&ei->nbrs); + eigrp_nbr_hash_fini(&ei->nbr_hash_head); eigrp = ei->eigrp; listnode_delete(eigrp->eiflist, ei); @@ -327,9 +327,6 @@ int eigrp_if_up(struct eigrp_interface *ei) int eigrp_if_down(struct eigrp_interface *ei) { - struct listnode *node, *nnode; - struct eigrp_neighbor *nbr; - if (ei == NULL) return 0; @@ -340,9 +337,9 @@ int eigrp_if_down(struct eigrp_interface *ei) /*Set infinite metrics to routes learned by this interface and start * query process*/ - for (ALL_LIST_ELEMENTS(ei->nbrs, node, nnode, nbr)) { - eigrp_nbr_delete(nbr); - } + while (eigrp_nbr_hash_count(&ei->nbr_hash_head) > 0) + eigrp_nbr_delete(eigrp_nbr_hash_first(&ei->nbr_hash_head)); + return 1; } diff --git a/eigrpd/eigrp_neighbor.c b/eigrpd/eigrp_neighbor.c index 25209c3bb3..578d1671c8 100644 --- a/eigrpd/eigrp_neighbor.c +++ b/eigrpd/eigrp_neighbor.c @@ -41,6 +41,21 @@ DEFINE_MTYPE_STATIC(EIGRPD, EIGRP_NEIGHBOR, "EIGRP neighbor"); +int eigrp_nbr_comp(const struct eigrp_neighbor *a, const struct eigrp_neighbor *b) +{ + if (a->src.s_addr == b->src.s_addr) + return 0; + else if (a->src.s_addr < b->src.s_addr) + return -1; + + return 1; +} + +uint32_t eigrp_nbr_hash(const struct eigrp_neighbor *a) +{ + return a->src.s_addr; +} + struct eigrp_neighbor *eigrp_nbr_new(struct eigrp_interface *ei) { struct eigrp_neighbor *nbr; @@ -80,17 +95,18 @@ struct eigrp_neighbor *eigrp_nbr_get(struct eigrp_interface *ei, struct eigrp_header *eigrph, struct ip *iph) { - struct eigrp_neighbor *nbr; - struct listnode *node, *nnode; + struct eigrp_neighbor lookup, *nbr; - for (ALL_LIST_ELEMENTS(ei->nbrs, node, nnode, nbr)) { - if (iph->ip_src.s_addr == nbr->src.s_addr) { - return nbr; - } + lookup.src = iph->ip_src; + lookup.ei = ei; + + nbr = eigrp_nbr_hash_find(&ei->nbr_hash_head, &lookup); + if (nbr) { + return nbr; } nbr = eigrp_nbr_add(ei, eigrph, iph); - listnode_add(ei->nbrs, nbr); + eigrp_nbr_hash_add(&ei->nbr_hash_head, nbr); return nbr; } @@ -110,16 +126,12 @@ struct eigrp_neighbor *eigrp_nbr_get(struct eigrp_interface *ei, struct eigrp_neighbor *eigrp_nbr_lookup_by_addr(struct eigrp_interface *ei, struct in_addr *addr) { - struct eigrp_neighbor *nbr; - struct listnode *node, *nnode; + struct eigrp_neighbor lookup, *nbr; - for (ALL_LIST_ELEMENTS(ei->nbrs, node, nnode, nbr)) { - if (addr->s_addr == nbr->src.s_addr) { - return nbr; - } - } + lookup.src = *addr; + nbr = eigrp_nbr_hash_find(&ei->nbr_hash_head, &lookup); - return NULL; + return nbr; } /** @@ -138,17 +150,16 @@ struct eigrp_neighbor *eigrp_nbr_lookup_by_addr_process(struct eigrp *eigrp, struct in_addr nbr_addr) { struct eigrp_interface *ei; - struct listnode *node, *node2, *nnode2; - struct eigrp_neighbor *nbr; + struct listnode *node; + struct eigrp_neighbor lookup, *nbr; /* iterate over all eigrp interfaces */ for (ALL_LIST_ELEMENTS_RO(eigrp->eiflist, node, ei)) { /* iterate over all neighbors on eigrp interface */ - for (ALL_LIST_ELEMENTS(ei->nbrs, node2, nnode2, nbr)) { - /* compare if neighbor address is same as arg address */ - if (nbr->src.s_addr == nbr_addr.s_addr) { - return nbr; - } + lookup.src = nbr_addr; + nbr = eigrp_nbr_hash_find(&ei->nbr_hash_head, &lookup); + if (nbr) { + return nbr; } } @@ -170,7 +181,7 @@ void eigrp_nbr_delete(struct eigrp_neighbor *nbr) EVENT_OFF(nbr->t_holddown); if (nbr->ei) - listnode_delete(nbr->ei->nbrs, nbr); + eigrp_nbr_hash_del(&nbr->ei->nbr_hash_head, nbr); XFREE(MTYPE_EIGRP_NEIGHBOR, nbr); } @@ -278,18 +289,13 @@ void eigrp_nbr_state_update(struct eigrp_neighbor *nbr) int eigrp_nbr_count_get(struct eigrp *eigrp) { struct eigrp_interface *iface; - struct listnode *node, *node2, *nnode2; - struct eigrp_neighbor *nbr; + struct listnode *node; uint32_t counter; counter = 0; - for (ALL_LIST_ELEMENTS_RO(eigrp->eiflist, node, iface)) { - for (ALL_LIST_ELEMENTS(iface->nbrs, node2, nnode2, nbr)) { - if (nbr->state == EIGRP_NEIGHBOR_UP) { - counter++; - } - } - } + for (ALL_LIST_ELEMENTS_RO(eigrp->eiflist, node, iface)) + counter += eigrp_nbr_hash_count(&iface->nbr_hash_head); + return counter; } diff --git a/eigrpd/eigrp_neighbor.h b/eigrpd/eigrp_neighbor.h index 2ccc89cf3a..17e8a8edc9 100644 --- a/eigrpd/eigrp_neighbor.h +++ b/eigrpd/eigrp_neighbor.h @@ -41,4 +41,9 @@ extern void eigrp_nbr_hard_restart(struct eigrp_neighbor *nbr, struct vty *vty); extern int eigrp_nbr_split_horizon_check(struct eigrp_route_descriptor *ne, struct eigrp_interface *ei); + +extern int eigrp_nbr_comp(const struct eigrp_neighbor *a, const struct eigrp_neighbor *b); +extern uint32_t eigrp_nbr_hash(const struct eigrp_neighbor *a); + +DECLARE_HASH(eigrp_nbr_hash, struct eigrp_neighbor, nbr_hash_item, eigrp_nbr_comp, eigrp_nbr_hash); #endif /* _ZEBRA_EIGRP_NEIGHBOR_H */ diff --git a/eigrpd/eigrp_query.c b/eigrpd/eigrp_query.c index 0e206cded6..aaa8f9478c 100644 --- a/eigrpd/eigrp_query.c +++ b/eigrpd/eigrp_query.c @@ -146,7 +146,7 @@ void eigrp_send_query(struct eigrp_interface *ei) { struct eigrp_packet *ep = NULL; uint16_t length = EIGRP_HEADER_LEN; - struct listnode *node, *nnode, *node2, *nnode2; + struct listnode *node, *nnode; struct eigrp_neighbor *nbr; struct eigrp_prefix_descriptor *pe; bool has_tlv = false; @@ -177,7 +177,7 @@ void eigrp_send_query(struct eigrp_interface *ei) length += eigrp_add_internalTLV_to_stream(ep->s, pe); has_tlv = true; - for (ALL_LIST_ELEMENTS(ei->nbrs, node2, nnode2, nbr)) { + frr_each (eigrp_nbr_hash, &ei->nbr_hash_head, nbr) { if (nbr->state == EIGRP_NEIGHBOR_UP) listnode_add(pe->rij, nbr); } @@ -197,7 +197,7 @@ void eigrp_send_query(struct eigrp_interface *ei) ep->sequence_number = ei->eigrp->sequence_number; ei->eigrp->sequence_number++; - for (ALL_LIST_ELEMENTS(ei->nbrs, node2, nnode2, nbr)) { + frr_each (eigrp_nbr_hash, &ei->nbr_hash_head, nbr) { struct eigrp_packet *dup; if (nbr->state != EIGRP_NEIGHBOR_UP) @@ -237,7 +237,7 @@ void eigrp_send_query(struct eigrp_interface *ei) ep->sequence_number = ei->eigrp->sequence_number; ei->eigrp->sequence_number++; - for (ALL_LIST_ELEMENTS(ei->nbrs, node2, nnode2, nbr)) { + frr_each (eigrp_nbr_hash, &ei->nbr_hash_head, nbr) { struct eigrp_packet *dup; if (nbr->state != EIGRP_NEIGHBOR_UP) diff --git a/eigrpd/eigrp_structs.h b/eigrpd/eigrp_structs.h index 8735c48661..4acb8b10b5 100644 --- a/eigrpd/eigrp_structs.h +++ b/eigrpd/eigrp_structs.h @@ -133,6 +133,8 @@ enum { MEMBER_ALLROUTERS = 0, MEMBER_MAX, }; +PREDECL_HASH(eigrp_nbr_hash); + /*EIGRP interface structure*/ struct eigrp_interface { struct eigrp_if_params params; @@ -162,7 +164,7 @@ struct eigrp_interface { struct prefix address; /* Interface prefix */ /* Neighbor information. */ - struct list *nbrs; /* EIGRP Neighbor List */ + struct eigrp_nbr_hash_head nbr_hash_head; /* Threads. */ struct event *t_hello; /* timer */ @@ -208,6 +210,8 @@ enum Packet_part_type { /* Neighbor Data Structure */ struct eigrp_neighbor { + struct eigrp_nbr_hash_item nbr_hash_item; + /* This neighbor's parent eigrp interface. */ struct eigrp_interface *ei; diff --git a/eigrpd/eigrp_update.c b/eigrpd/eigrp_update.c index 74f573d9d8..bb61a3e6c1 100644 --- a/eigrpd/eigrp_update.c +++ b/eigrpd/eigrp_update.c @@ -482,11 +482,10 @@ static void eigrp_update_place_on_nbr_queue(struct eigrp_neighbor *nbr, static void eigrp_update_send_to_all_nbrs(struct eigrp_interface *ei, struct eigrp_packet *ep) { - struct listnode *node, *nnode; struct eigrp_neighbor *nbr; bool packet_sent = false; - for (ALL_LIST_ELEMENTS(ei->nbrs, node, nnode, nbr)) { + frr_each (eigrp_nbr_hash, &ei->nbr_hash_head, nbr) { struct eigrp_packet *ep_dup; if (nbr->state != EIGRP_NEIGHBOR_UP) @@ -595,7 +594,7 @@ void eigrp_update_send(struct eigrp_interface *ei) uint32_t seq_no = eigrp->sequence_number; uint16_t eigrp_mtu = EIGRP_PACKET_MTU(ei->ifp->mtu); - if (ei->nbrs->count == 0) + if (eigrp_nbr_hash_count(&ei->nbr_hash_head) == 0) return; uint16_t length = EIGRP_HEADER_LEN; @@ -1001,11 +1000,10 @@ void eigrp_update_send_GR(struct eigrp_neighbor *nbr, enum GR_type gr_type, void eigrp_update_send_interface_GR(struct eigrp_interface *ei, enum GR_type gr_type, struct vty *vty) { - struct listnode *node; struct eigrp_neighbor *nbr; /* iterate over all neighbors on eigrp interface */ - for (ALL_LIST_ELEMENTS_RO(ei->nbrs, node, nbr)) { + frr_each (eigrp_nbr_hash, &ei->nbr_hash_head, nbr) { /* send GR to neighbor */ eigrp_update_send_GR(nbr, gr_type, vty); } diff --git a/eigrpd/eigrp_vty.c b/eigrpd/eigrp_vty.c index 88510e75af..31782afdb9 100644 --- a/eigrpd/eigrp_vty.c +++ b/eigrpd/eigrp_vty.c @@ -252,14 +252,14 @@ static void eigrp_neighbors_helper(struct vty *vty, struct eigrp *eigrp, const char *ifname, const char *detail) { struct eigrp_interface *ei; - struct listnode *node, *node2, *nnode2; + struct listnode *node; struct eigrp_neighbor *nbr; show_ip_eigrp_neighbor_header(vty, eigrp); for (ALL_LIST_ELEMENTS_RO(eigrp->eiflist, node, ei)) { if (!ifname || strcmp(ei->ifp->name, ifname) == 0) { - for (ALL_LIST_ELEMENTS(ei->nbrs, node2, nnode2, nbr)) { + frr_each (eigrp_nbr_hash, &ei->nbr_hash_head, nbr) { if (detail || (nbr->state == EIGRP_NEIGHBOR_UP)) show_ip_eigrp_neighbor_sub(vty, nbr, !!detail); @@ -320,7 +320,7 @@ DEFPY (clear_ip_eigrp_neighbors, { struct eigrp *eigrp; struct eigrp_interface *ei; - struct listnode *node, *node2, *nnode2; + struct listnode *node; struct eigrp_neighbor *nbr; /* Check if eigrp process is enabled */ @@ -336,7 +336,7 @@ DEFPY (clear_ip_eigrp_neighbors, eigrp_hello_send(ei, EIGRP_HELLO_GRACEFUL_SHUTDOWN, NULL); /* iterate over all neighbors on eigrp interface */ - for (ALL_LIST_ELEMENTS(ei->nbrs, node2, nnode2, nbr)) { + frr_each (eigrp_nbr_hash, &ei->nbr_hash_head, nbr) { if (nbr->state != EIGRP_NEIGHBOR_DOWN) { zlog_debug( "Neighbor %pI4 (%s) is down: manually cleared", @@ -376,7 +376,6 @@ DEFPY (clear_ip_eigrp_neighbors_int, { struct eigrp *eigrp; struct eigrp_interface *ei; - struct listnode *node2, *nnode2; struct eigrp_neighbor *nbr; /* Check if eigrp process is enabled */ @@ -397,7 +396,7 @@ DEFPY (clear_ip_eigrp_neighbors_int, eigrp_hello_send(ei, EIGRP_HELLO_GRACEFUL_SHUTDOWN, NULL); /* iterate over all neighbors on eigrp interface */ - for (ALL_LIST_ELEMENTS(ei->nbrs, node2, nnode2, nbr)) { + frr_each (eigrp_nbr_hash, &ei->nbr_hash_head, nbr) { if (nbr->state != EIGRP_NEIGHBOR_DOWN) { zlog_debug( "Neighbor %pI4 (%s) is down: manually cleared", diff --git a/eigrpd/eigrpd.c b/eigrpd/eigrpd.c index c7dd96bfff..908c10ce4e 100644 --- a/eigrpd/eigrpd.c +++ b/eigrpd/eigrpd.c @@ -252,11 +252,13 @@ void eigrp_finish_final(struct eigrp *eigrp) { struct eigrp_interface *ei; struct eigrp_neighbor *nbr; - struct listnode *node, *nnode, *node2, *nnode2; + struct listnode *node, *nnode; for (ALL_LIST_ELEMENTS(eigrp->eiflist, node, nnode, ei)) { - for (ALL_LIST_ELEMENTS(ei->nbrs, node2, nnode2, nbr)) + while (eigrp_nbr_hash_count(&ei->nbr_hash_head)) { + nbr = eigrp_nbr_hash_first(&ei->nbr_hash_head); eigrp_nbr_delete(nbr); + } eigrp_if_free(ei, INTERFACE_DOWN_BY_FINAL); } -- 2.39.5