*: 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>

2 files changed, 20 insertions, 20 deletions

diff --git a/ripngd/ripng_interface.c b/ripngd/ripng_interface.c
index 5c65f522e..aab2b2324 100644
--- a/ripngd/ripng_interface.c
+++ b/ripngd/ripng_interface.c
@@ -306,11 +306,11 @@ int ripng_interface_delete(int command, struct zclient *zclient,
 
 void ripng_interface_clean(void)
 {
-	struct listnode *node, *nnode;
+	struct vrf *vrf = vrf_lookup_by_id(VRF_DEFAULT);
 	struct interface *ifp;
 	struct ripng_interface *ri;
 
-	for (ALL_LIST_ELEMENTS(vrf_iflist(VRF_DEFAULT), node, nnode, ifp)) {
+	RB_FOREACH (ifp, if_name_head, &vrf->ifaces_by_name) {
 		ri = ifp->info;
 
 		ri->enable_network = 0;
@@ -326,11 +326,11 @@ void ripng_interface_clean(void)
 
 void ripng_interface_reset(void)
 {
-	struct listnode *node;
+	struct vrf *vrf = vrf_lookup_by_id(VRF_DEFAULT);
 	struct interface *ifp;
 	struct ripng_interface *ri;
 
-	for (ALL_LIST_ELEMENTS_RO(vrf_iflist(VRF_DEFAULT), node, ifp)) {
+	RB_FOREACH (ifp, if_name_head, &vrf->ifaces_by_name) {
 		ri = ifp->info;
 
 		ri->enable_network = 0;
@@ -760,10 +760,10 @@ void ripng_enable_apply(struct interface *ifp)
 /* Set distribute list to all interfaces. */
 static void ripng_enable_apply_all(void)
 {
+	struct vrf *vrf = vrf_lookup_by_id(VRF_DEFAULT);
 	struct interface *ifp;
-	struct listnode *node;
 
-	for (ALL_LIST_ELEMENTS_RO(vrf_iflist(VRF_DEFAULT), node, ifp))
+	RB_FOREACH (ifp, if_name_head, &vrf->ifaces_by_name)
 		ripng_enable_apply(ifp);
 }
 
@@ -821,10 +821,10 @@ void ripng_passive_interface_apply(struct interface *ifp)
 
 static void ripng_passive_interface_apply_all(void)
 {
+	struct vrf *vrf = vrf_lookup_by_id(VRF_DEFAULT);
 	struct interface *ifp;
-	struct listnode *node;
 
-	for (ALL_LIST_ELEMENTS_RO(vrf_iflist(VRF_DEFAULT), node, ifp))
+	RB_FOREACH (ifp, if_name_head, &vrf->ifaces_by_name)
 		ripng_passive_interface_apply(ifp);
 }
 
@@ -1069,12 +1069,12 @@ static int ripng_if_delete_hook(struct interface *ifp)
 /* Configuration write function for ripngd. */
 static int interface_config_write(struct vty *vty)
 {
-	struct listnode *node;
+	struct vrf *vrf = vrf_lookup_by_id(VRF_DEFAULT);
 	struct interface *ifp;
 	struct ripng_interface *ri;
 	int write = 0;
 
-	for (ALL_LIST_ELEMENTS_RO(vrf_iflist(VRF_DEFAULT), node, ifp)) {
+	RB_FOREACH (ifp, if_name_head, &vrf->ifaces_by_name) {
 		ri = ifp->info;
 
 		/* Do not display the interface if there is no
diff --git a/ripngd/ripngd.c b/ripngd/ripngd.c
index 4df1aafe5..902b5d986 100644
--- a/ripngd/ripngd.c
+++ b/ripngd/ripngd.c
@@ -1377,7 +1377,7 @@ static void ripng_clear_changed_flag(void)
    enabled interface. */
 static int ripng_update(struct thread *t)
 {
-	struct listnode *node;
+	struct vrf *vrf = vrf_lookup_by_id(VRF_DEFAULT);
 	struct interface *ifp;
 	struct ripng_interface *ri;
 
@@ -1389,7 +1389,7 @@ static int ripng_update(struct thread *t)
 		zlog_debug("RIPng update timer expired!");
 
 	/* Supply routes to each interface. */
-	for (ALL_LIST_ELEMENTS_RO(vrf_iflist(VRF_DEFAULT), node, ifp)) {
+	RB_FOREACH (ifp, if_name_head, &vrf->ifaces_by_name) {
 		ri = ifp->info;
 
 		if (if_is_loopback(ifp) || !if_is_up(ifp))
@@ -1445,7 +1445,7 @@ static int ripng_triggered_interval(struct thread *t)
 /* Execute triggered update. */
 int ripng_triggered_update(struct thread *t)
 {
-	struct listnode *node;
+	struct vrf *vrf = vrf_lookup_by_id(VRF_DEFAULT);
 	struct interface *ifp;
 	struct ripng_interface *ri;
 	int interval;
@@ -1465,7 +1465,7 @@ int ripng_triggered_update(struct thread *t)
 
 	/* Split Horizon processing is done when generating triggered
 	   updates as well as normal updates (see section 2.6). */
-	for (ALL_LIST_ELEMENTS_RO(vrf_iflist(VRF_DEFAULT), node, ifp)) {
+	RB_FOREACH (ifp, if_name_head, &vrf->ifaces_by_name) {
 		ri = ifp->info;
 
 		if (if_is_loopback(ifp) || !if_is_up(ifp))
@@ -2058,7 +2058,7 @@ DEFUN (show_ipv6_ripng_status,
        "Show RIPng routes\n"
        "IPv6 routing protocol process parameters and statistics\n")
 {
-	struct listnode *node;
+	struct vrf *vrf = vrf_lookup_by_id(VRF_DEFAULT);
 	struct interface *ifp;
 
 	if (!ripng)
@@ -2091,7 +2091,7 @@ DEFUN (show_ipv6_ripng_status,
 
 	vty_out(vty, "    Interface        Send  Recv\n");
 
-	for (ALL_LIST_ELEMENTS_RO(vrf_iflist(VRF_DEFAULT), node, ifp)) {
+	RB_FOREACH (ifp, if_name_head, &vrf->ifaces_by_name) {
 		struct ripng_interface *ri;
 
 		ri = ifp->info;
@@ -2791,10 +2791,10 @@ void ripng_distribute_update_interface(struct interface *ifp)
 /* Update all interface's distribute list. */
 static void ripng_distribute_update_all(struct prefix_list *notused)
 {
+	struct vrf *vrf = vrf_lookup_by_id(VRF_DEFAULT);
 	struct interface *ifp;
-	struct listnode *node;
 
-	for (ALL_LIST_ELEMENTS_RO(vrf_iflist(VRF_DEFAULT), node, ifp))
+	RB_FOREACH (ifp, if_name_head, &vrf->ifaces_by_name)
 		ripng_distribute_update_interface(ifp);
 }
 
@@ -2968,10 +2968,10 @@ static void ripng_routemap_update_redistribute(void)
 
 static void ripng_routemap_update(const char *unused)
 {
+	struct vrf *vrf = vrf_lookup_by_id(VRF_DEFAULT);
 	struct interface *ifp;
-	struct listnode *node;
 
-	for (ALL_LIST_ELEMENTS_RO(vrf_iflist(VRF_DEFAULT), node, ifp))
+	RB_FOREACH (ifp, if_name_head, &vrf->ifaces_by_name)
 		ripng_if_rmap_update_interface(ifp);
 
 	ripng_routemap_update_redistribute();