*: use rb-trees to store interfaces instead of sorted linked-lists

This is an important optimization for users running FRR on systems with
a large number of interfaces (e.g. thousands of tunnels). Red-black
trees scale much better than sorted linked-lists and also store the
elements in an ordered way (contrary to hash tables).

This is a big patch but the interesting bits are all in lib/if.[ch].

Signed-off-by: Renato Westphal <renato@opensourcerouting.org>

1 files changed, 26 insertions, 60 deletions

diff --git a/pimd/pim_cmd.c b/pimd/pim_cmd.c
index 7ce345d8e3..cd55e0fa12 100644
--- a/pimd/pim_cmd.c
+++ b/pimd/pim_cmd.c
@@ -214,7 +214,6 @@ static void pim_show_assert(struct pim_instance *pim, struct vty *vty)
 {
 	struct pim_interface *pim_ifp;
 	struct pim_ifchannel *ch;
-	struct listnode *if_node;
 	struct interface *ifp;
 	time_t now;
 
@@ -223,7 +222,7 @@ static void pim_show_assert(struct pim_instance *pim, struct vty *vty)
 	vty_out(vty,
 		"Interface Address         Source          Group           State  Winner          Uptime   Timer\n");
 
-	for (ALL_LIST_ELEMENTS_RO(vrf_iflist(pim->vrf_id), if_node, ifp)) {
+	RB_FOREACH (ifp, if_name_head, &pim->vrf->ifaces_by_name) {
 		pim_ifp = ifp->info;
 		if (!pim_ifp)
 			continue;
@@ -263,7 +262,6 @@ static void pim_show_assert_internal_helper(struct vty *vty,
 static void pim_show_assert_internal(struct pim_instance *pim, struct vty *vty)
 {
 	struct pim_interface *pim_ifp;
-	struct listnode *if_node;
 	struct pim_ifchannel *ch;
 	struct interface *ifp;
 
@@ -275,7 +273,7 @@ static void pim_show_assert_internal(struct pim_instance *pim, struct vty *vty)
 
 	vty_out(vty,
 		"Interface Address         Source          Group           CA  eCA ATD eATD\n");
-	for (ALL_LIST_ELEMENTS_RO(vrf_iflist(pim->vrf_id), if_node, ifp)) {
+	RB_FOREACH (ifp, if_name_head, &pim->vrf->ifaces_by_name) {
 		pim_ifp = ifp->info;
 		if (!pim_ifp)
 			continue;
@@ -317,14 +315,13 @@ static void pim_show_assert_metric_helper(struct vty *vty,
 static void pim_show_assert_metric(struct pim_instance *pim, struct vty *vty)
 {
 	struct pim_interface *pim_ifp;
-	struct listnode *if_node;
 	struct pim_ifchannel *ch;
 	struct interface *ifp;
 
 	vty_out(vty,
 		"Interface Address         Source          Group           RPT Pref Metric Address        \n");
 
-	for (ALL_LIST_ELEMENTS_RO(vrf_iflist(pim->vrf_id), if_node, ifp)) {
+	RB_FOREACH (ifp, if_name_head, &pim->vrf->ifaces_by_name) {
 		pim_ifp = ifp->info;
 		if (!pim_ifp)
 			continue;
@@ -379,7 +376,6 @@ static void pim_show_assert_winner_metric_helper(struct vty *vty,
 static void pim_show_assert_winner_metric(struct pim_instance *pim,
 					  struct vty *vty)
 {
-	struct listnode *if_node;
 	struct pim_interface *pim_ifp;
 	struct pim_ifchannel *ch;
 	struct interface *ifp;
@@ -387,7 +383,7 @@ static void pim_show_assert_winner_metric(struct pim_instance *pim,
 	vty_out(vty,
 		"Interface Address         Source          Group           RPT Pref Metric Address        \n");
 
-	for (ALL_LIST_ELEMENTS_RO(vrf_iflist(pim->vrf_id), if_node, ifp)) {
+	RB_FOREACH (ifp, if_name_head, &pim->vrf->ifaces_by_name) {
 		pim_ifp = ifp->info;
 		if (!pim_ifp)
 			continue;
@@ -467,7 +463,6 @@ static void pim_show_membership_helper(struct vty *vty,
 static void pim_show_membership(struct pim_instance *pim, struct vty *vty,
 				u_char uj)
 {
-	struct listnode *if_node;
 	struct pim_interface *pim_ifp;
 	struct pim_ifchannel *ch;
 	struct interface *ifp;
@@ -477,7 +472,7 @@ static void pim_show_membership(struct pim_instance *pim, struct vty *vty,
 
 	json = json_object_new_object();
 
-	for (ALL_LIST_ELEMENTS_RO(vrf_iflist(pim->vrf_id), if_node, ifp)) {
+	RB_FOREACH (ifp, if_name_head, &pim->vrf->ifaces_by_name) {
 		pim_ifp = ifp->info;
 		if (!pim_ifp)
 			continue;
@@ -585,7 +580,6 @@ static void pim_print_ifp_flags(struct vty *vty, struct interface *ifp,
 static void igmp_show_interfaces(struct pim_instance *pim, struct vty *vty,
 				 u_char uj)
 {
-	struct listnode *node;
 	struct interface *ifp;
 	time_t now;
 	json_object *json = NULL;
@@ -599,7 +593,7 @@ static void igmp_show_interfaces(struct pim_instance *pim, struct vty *vty,
 		vty_out(vty,
 			"Interface  State          Address  V  Querier  Query Timer    Uptime\n");
 
-	for (ALL_LIST_ELEMENTS_RO(vrf_iflist(pim->vrf_id), node, ifp)) {
+	RB_FOREACH (ifp, if_name_head, &pim->vrf->ifaces_by_name) {
 		struct pim_interface *pim_ifp;
 		struct listnode *sock_node;
 		struct igmp_sock *igmp;
@@ -666,7 +660,6 @@ static void igmp_show_interfaces_single(struct pim_instance *pim,
 {
 	struct igmp_sock *igmp;
 	struct interface *ifp;
-	struct listnode *node;
 	struct listnode *sock_node;
 	struct pim_interface *pim_ifp;
 	char uptime[10];
@@ -690,7 +683,7 @@ static void igmp_show_interfaces_single(struct pim_instance *pim,
 
 	now = pim_time_monotonic_sec();
 
-	for (ALL_LIST_ELEMENTS_RO(vrf_iflist(pim->vrf_id), node, ifp)) {
+	RB_FOREACH (ifp, if_name_head, &pim->vrf->ifaces_by_name) {
 		pim_ifp = ifp->info;
 
 		if (!pim_ifp)
@@ -866,7 +859,6 @@ static void igmp_show_interfaces_single(struct pim_instance *pim,
 
 static void igmp_show_interface_join(struct pim_instance *pim, struct vty *vty)
 {
-	struct listnode *node;
 	struct interface *ifp;
 	time_t now;
 
@@ -875,7 +867,7 @@ static void igmp_show_interface_join(struct pim_instance *pim, struct vty *vty)
 	vty_out(vty,
 		"Interface Address         Source          Group           Socket Uptime  \n");
 
-	for (ALL_LIST_ELEMENTS_RO(vrf_iflist(pim->vrf_id), node, ifp)) {
+	RB_FOREACH (ifp, if_name_head, &pim->vrf->ifaces_by_name) {
 		struct pim_interface *pim_ifp;
 		struct listnode *join_node;
 		struct igmp_join *ij;
@@ -922,7 +914,6 @@ static void pim_show_interfaces_single(struct pim_instance *pim,
 	struct in_addr ifaddr;
 	struct interface *ifp;
 	struct listnode *neighnode;
-	struct listnode *node;
 	struct listnode *upnode;
 	struct pim_interface *pim_ifp;
 	struct pim_neighbor *neigh;
@@ -956,7 +947,7 @@ static void pim_show_interfaces_single(struct pim_instance *pim,
 	if (uj)
 		json = json_object_new_object();
 
-	for (ALL_LIST_ELEMENTS_RO(vrf_iflist(pim->vrf_id), node, ifp)) {
+	RB_FOREACH (ifp, if_name_head, &pim->vrf->ifaces_by_name) {
 		pim_ifp = ifp->info;
 
 		if (!pim_ifp)
@@ -1338,7 +1329,6 @@ static void pim_show_interfaces(struct pim_instance *pim, struct vty *vty,
 				u_char uj)
 {
 	struct interface *ifp;
-	struct listnode *node;
 	struct listnode *upnode;
 	struct pim_interface *pim_ifp;
 	struct pim_upstream *up;
@@ -1351,7 +1341,7 @@ static void pim_show_interfaces(struct pim_instance *pim, struct vty *vty,
 
 	json = json_object_new_object();
 
-	for (ALL_LIST_ELEMENTS_RO(vrf_iflist(pim->vrf_id), node, ifp)) {
+	RB_FOREACH (ifp, if_name_head, &pim->vrf->ifaces_by_name) {
 		pim_ifp = ifp->info;
 
 		if (!pim_ifp)
@@ -1433,7 +1423,6 @@ static void pim_show_interface_traffic(struct pim_instance *pim,
 {
 	struct interface *ifp = NULL;
 	struct pim_interface *pim_ifp = NULL;
-	struct listnode *node = NULL;
 	json_object *json = NULL;
 	json_object *json_row = NULL;
 
@@ -1451,7 +1440,7 @@ static void pim_show_interface_traffic(struct pim_instance *pim,
 			"---------------------------------------------------------------------------------------------------------------\n");
 	}
 
-	for (ALL_LIST_ELEMENTS_RO(vrf_iflist(pim->vrf_id), node, ifp)) {
+	RB_FOREACH (ifp, if_name_head, &pim->vrf->ifaces_by_name) {
 		pim_ifp = ifp->info;
 
 		if (!pim_ifp)
@@ -1514,7 +1503,6 @@ static void pim_show_interface_traffic_single(struct pim_instance *pim,
 {
 	struct interface *ifp = NULL;
 	struct pim_interface *pim_ifp = NULL;
-	struct listnode *node = NULL;
 	json_object *json = NULL;
 	json_object *json_row = NULL;
 	uint8_t found_ifname = 0;
@@ -1533,7 +1521,7 @@ static void pim_show_interface_traffic_single(struct pim_instance *pim,
 			"---------------------------------------------------------------------------------------------------------------\n");
 	}
 
-	for (ALL_LIST_ELEMENTS_RO(vrf_iflist(pim->vrf_id), node, ifp)) {
+	RB_FOREACH (ifp, if_name_head, &pim->vrf->ifaces_by_name) {
 		if (strcmp(ifname, ifp->name))
 			continue;
 
@@ -1678,7 +1666,6 @@ static void pim_show_join_helper(struct vty *vty,
 
 static void pim_show_join(struct pim_instance *pim, struct vty *vty, u_char uj)
 {
-	struct listnode *if_node;
 	struct pim_interface *pim_ifp;
 	struct pim_ifchannel *ch;
 	struct interface *ifp;
@@ -1693,7 +1680,7 @@ static void pim_show_join(struct pim_instance *pim, struct vty *vty, u_char uj)
 		vty_out(vty,
 			"Interface Address         Source          Group           State      Uptime   Expire Prune\n");
 
-	for (ALL_LIST_ELEMENTS_RO(vrf_iflist(pim->vrf_id), if_node, ifp)) {
+	RB_FOREACH (ifp, if_name_head, &pim->vrf->ifaces_by_name) {
 		pim_ifp = ifp->info;
 		if (!pim_ifp)
 			continue;
@@ -1713,7 +1700,6 @@ static void pim_show_join(struct pim_instance *pim, struct vty *vty, u_char uj)
 static void pim_show_neighbors_single(struct pim_instance *pim, struct vty *vty,
 				      const char *neighbor, u_char uj)
 {
-	struct listnode *node;
 	struct listnode *neighnode;
 	struct interface *ifp;
 	struct pim_interface *pim_ifp;
@@ -1739,7 +1725,7 @@ static void pim_show_neighbors_single(struct pim_instance *pim, struct vty *vty,
 	if (uj)
 		json = json_object_new_object();
 
-	for (ALL_LIST_ELEMENTS_RO(vrf_iflist(pim->vrf_id), node, ifp)) {
+	RB_FOREACH (ifp, if_name_head, &pim->vrf->ifaces_by_name) {
 		pim_ifp = ifp->info;
 
 		if (!pim_ifp)
@@ -2125,7 +2111,6 @@ static void pim_show_state(struct pim_instance *pim, struct vty *vty,
 static void pim_show_neighbors(struct pim_instance *pim, struct vty *vty,
 			       u_char uj)
 {
-	struct listnode *node;
 	struct listnode *neighnode;
 	struct interface *ifp;
 	struct pim_interface *pim_ifp;
@@ -2147,7 +2132,7 @@ static void pim_show_neighbors(struct pim_instance *pim, struct vty *vty,
 			"Interface         Neighbor    Uptime  Holdtime  DR Pri\n");
 	}
 
-	for (ALL_LIST_ELEMENTS_RO(vrf_iflist(pim->vrf_id), node, ifp)) {
+	RB_FOREACH (ifp, if_name_head, &pim->vrf->ifaces_by_name) {
 		pim_ifp = ifp->info;
 
 		if (!pim_ifp)
@@ -2208,13 +2193,12 @@ static void pim_show_neighbors(struct pim_instance *pim, struct vty *vty,
 static void pim_show_neighbors_secondary(struct pim_instance *pim,
 					 struct vty *vty)
 {
-	struct listnode *node;
 	struct interface *ifp;
 
 	vty_out(vty,
 		"Interface Address         Neighbor        Secondary      \n");
 
-	for (ALL_LIST_ELEMENTS_RO(vrf_iflist(pim->vrf_id), node, ifp)) {
+	RB_FOREACH (ifp, if_name_head, &pim->vrf->ifaces_by_name) {
 		struct pim_interface *pim_ifp;
 		struct in_addr ifaddr;
 		struct listnode *neighnode;
@@ -2507,7 +2491,6 @@ static void pim_show_join_desired_helper(struct pim_instance *pim,
 static void pim_show_join_desired(struct pim_instance *pim, struct vty *vty,
 				  u_char uj)
 {
-	struct listnode *if_node;
 	struct pim_interface *pim_ifp;
 	struct pim_ifchannel *ch;
 	struct interface *ifp;
@@ -2521,7 +2504,7 @@ static void pim_show_join_desired(struct pim_instance *pim, struct vty *vty,
 			"Interface Source          Group           LostAssert Joins PimInclude JoinDesired EvalJD\n");
 
 	/* scan per-interface (S,G) state */
-	for (ALL_LIST_ELEMENTS_RO(vrf_iflist(pim->vrf_id), if_node, ifp)) {
+	RB_FOREACH (ifp, if_name_head, &pim->vrf->ifaces_by_name) {
 		pim_ifp = ifp->info;
 		if (!pim_ifp)
 			continue;
@@ -2802,7 +2785,6 @@ static void pim_show_nexthop(struct pim_instance *pim, struct vty *vty)
 static void igmp_show_groups(struct pim_instance *pim, struct vty *vty,
 			     u_char uj)
 {
-	struct listnode *ifnode;
 	struct interface *ifp;
 	time_t now;
 	json_object *json = NULL;
@@ -2818,7 +2800,7 @@ static void igmp_show_groups(struct pim_instance *pim, struct vty *vty,
 			"Interface Address         Group           Mode Timer    Srcs V Uptime  \n");
 
 	/* scan interfaces */
-	for (ALL_LIST_ELEMENTS_RO(vrf_iflist(pim->vrf_id), ifnode, ifp)) {
+	RB_FOREACH (ifp, if_name_head, &pim->vrf->ifaces_by_name) {
 		struct pim_interface *pim_ifp = ifp->info;
 		struct listnode *sock_node;
 		struct igmp_sock *igmp;
@@ -2924,14 +2906,13 @@ static void igmp_show_groups(struct pim_instance *pim, struct vty *vty,
 static void igmp_show_group_retransmission(struct pim_instance *pim,
 					   struct vty *vty)
 {
-	struct listnode *ifnode;
 	struct interface *ifp;
 
 	vty_out(vty,
 		"Interface Address         Group           RetTimer Counter RetSrcs\n");
 
 	/* scan interfaces */
-	for (ALL_LIST_ELEMENTS_RO(vrf_iflist(pim->vrf_id), ifnode, ifp)) {
+	RB_FOREACH (ifp, if_name_head, &pim->vrf->ifaces_by_name) {
 		struct pim_interface *pim_ifp = ifp->info;
 		struct listnode *sock_node;
 		struct igmp_sock *igmp;
@@ -2989,7 +2970,6 @@ static void igmp_show_group_retransmission(struct pim_instance *pim,
 
 static void igmp_show_sources(struct pim_instance *pim, struct vty *vty)
 {
-	struct listnode *ifnode;
 	struct interface *ifp;
 	time_t now;
 
@@ -2999,7 +2979,7 @@ static void igmp_show_sources(struct pim_instance *pim, struct vty *vty)
 		"Interface Address         Group           Source          Timer Fwd Uptime  \n");
 
 	/* scan interfaces */
-	for (ALL_LIST_ELEMENTS_RO(vrf_iflist(pim->vrf_id), ifnode, ifp)) {
+	RB_FOREACH (ifp, if_name_head, &pim->vrf->ifaces_by_name) {
 		struct pim_interface *pim_ifp = ifp->info;
 		struct listnode *sock_node;
 		struct igmp_sock *igmp;
@@ -3066,14 +3046,13 @@ static void igmp_show_sources(struct pim_instance *pim, struct vty *vty)
 static void igmp_show_source_retransmission(struct pim_instance *pim,
 					    struct vty *vty)
 {
-	struct listnode *ifnode;
 	struct interface *ifp;
 
 	vty_out(vty,
 		"Interface Address         Group           Source          Counter\n");
 
 	/* scan interfaces */
-	for (ALL_LIST_ELEMENTS_RO(vrf_iflist(pim->vrf_id), ifnode, ifp)) {
+	RB_FOREACH (ifp, if_name_head, &pim->vrf->ifaces_by_name) {
 		struct pim_interface *pim_ifp = ifp->info;
 		struct listnode *sock_node;
 		struct igmp_sock *igmp;
@@ -3125,29 +3104,20 @@ static void igmp_show_source_retransmission(struct pim_instance *pim,
 
 static void clear_igmp_interfaces(struct pim_instance *pim)
 {
-	struct listnode *ifnode;
-	struct listnode *ifnextnode;
 	struct interface *ifp;
 
-	for (ALL_LIST_ELEMENTS(vrf_iflist(pim->vrf_id), ifnode, ifnextnode,
-			       ifp)) {
+	RB_FOREACH (ifp, if_name_head, &pim->vrf->ifaces_by_name)
 		pim_if_addr_del_all_igmp(ifp);
-	}
 
-	for (ALL_LIST_ELEMENTS(vrf_iflist(pim->vrf_id), ifnode, ifnextnode,
-			       ifp)) {
+	RB_FOREACH (ifp, if_name_head, &pim->vrf->ifaces_by_name)
 		pim_if_addr_add_all(ifp);
-	}
 }
 
 static void clear_pim_interfaces(struct pim_instance *pim)
 {
-	struct listnode *ifnode;
-	struct listnode *ifnextnode;
 	struct interface *ifp;
 
-	for (ALL_LIST_ELEMENTS(vrf_iflist(pim->vrf_id), ifnode, ifnextnode,
-			       ifp)) {
+	RB_FOREACH (ifp, if_name_head, &pim->vrf->ifaces_by_name) {
 		if (ifp->info) {
 			pim_neighbor_delete_all(ifp, "interface cleared");
 		}
@@ -3301,16 +3271,13 @@ DEFUN (clear_ip_pim_interface_traffic,
 {
 	int idx = 2;
 	struct vrf *vrf = pim_cmd_lookup_vrf(vty, argv, argc, &idx);
-	struct listnode *ifnode = NULL;
-	struct listnode *ifnextnode = NULL;
 	struct interface *ifp = NULL;
 	struct pim_interface *pim_ifp = NULL;
 
 	if (!vrf)
 		return CMD_WARNING;
 
-	for (ALL_LIST_ELEMENTS(vrf_iflist(vrf->vrf_id), ifnode, ifnextnode,
-			       ifp)) {
+	RB_FOREACH (ifp, if_name_head, &vrf->ifaces_by_name) {
 		pim_ifp = ifp->info;
 
 		if (!pim_ifp)
@@ -4320,7 +4287,6 @@ DEFUN (show_ip_pim_interface_traffic,
 
 static void show_multicast_interfaces(struct pim_instance *pim, struct vty *vty)
 {
-	struct listnode *node;
 	struct interface *ifp;
 
 	vty_out(vty, "\n");
@@ -4328,7 +4294,7 @@ static void show_multicast_interfaces(struct pim_instance *pim, struct vty *vty)
 	vty_out(vty,
 		"Interface Address            ifi Vif  PktsIn PktsOut    BytesIn   BytesOut\n");
 
-	for (ALL_LIST_ELEMENTS_RO(vrf_iflist(pim->vrf_id), node, ifp)) {
+	RB_FOREACH (ifp, if_name_head, &pim->vrf->ifaces_by_name) {
 		struct pim_interface *pim_ifp;
 		struct in_addr ifaddr;
 		struct sioc_vif_req vreq;