ldpd: use red-black trees to store 'nbr_params' elements

Using red-black trees instead of linked lists brings the following
benefits:
1 - Elements are naturally ordered (no need to reorder anything before
    outputting data to the user);
2 - Faster lookups/deletes: O(log n) time complexity against O(n).

The insert operation with red-black trees is more expensive though,
but that's not a big issue since lookups are much more frequent.

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

6 files changed, 45 insertions, 37 deletions

diff --git a/ldpd/lde.c b/ldpd/lde.c
index 4b957c55e..80557ed4e 100644
--- a/ldpd/lde.c
+++ b/ldpd/lde.c
@@ -475,7 +475,7 @@ lde_dispatch_parent(struct thread *thread)
 
 			RB_INIT(&nconf->iface_tree);
 			RB_INIT(&nconf->tnbr_tree);
-			LIST_INIT(&nconf->nbrp_list);
+			RB_INIT(&nconf->nbrp_tree);
 			LIST_INIT(&nconf->l2vpn_list);
 			break;
 		case IMSG_RECONF_IFACE:
@@ -503,7 +503,7 @@ lde_dispatch_parent(struct thread *thread)
 				fatal(NULL);
 			memcpy(nnbrp, imsg.data, sizeof(struct nbr_params));
 
-			LIST_INSERT_HEAD(&nconf->nbrp_list, nnbrp, entry);
+			RB_INSERT(nbrp_head, &nconf->nbrp_tree, nnbrp);
 			break;
 		case IMSG_RECONF_L2VPN:
 			if ((nl2vpn = malloc(sizeof(struct l2vpn))) == NULL)
diff --git a/ldpd/ldp_vty_conf.c b/ldpd/ldp_vty_conf.c
index f5c98eb1f..95b0971e6 100644
--- a/ldpd/ldp_vty_conf.c
+++ b/ldpd/ldp_vty_conf.c
@@ -265,7 +265,7 @@ ldp_config_write(struct vty *vty)
 	if (ldpd_conf->flags & F_LDPD_DS_CISCO_INTEROP)
 		vty_out(vty, " dual-stack cisco-interop%s", VTY_NEWLINE);
 
-	LIST_FOREACH(nbrp, &ldpd_conf->nbrp_list, entry) {
+	RB_FOREACH(nbrp, nbrp_head, &ldpd_conf->nbrp_tree) {
 		if (nbrp->flags & F_NBRP_KEEPALIVE)
 			vty_out(vty, " neighbor %s session holdtime %u%s",
 			    inet_ntoa(nbrp->lsr_id), nbrp->keepalive,
@@ -740,7 +740,7 @@ ldp_vty_nbr_session_holdtime(struct vty *vty, struct vty_arg *args[])
 	} else {
 		if (nbrp == NULL) {
 			nbrp = nbr_params_new(lsr_id);
-			LIST_INSERT_HEAD(&vty_conf->nbrp_list, nbrp, entry);
+			RB_INSERT(nbrp_head, &vty_conf->nbrp_tree, nbrp);
 		} else if (nbrp->keepalive == secs)
 			goto cancel;
 
@@ -1129,7 +1129,7 @@ ldp_vty_neighbor_password(struct vty *vty, struct vty_arg *args[])
 	} else {
 		if (nbrp == NULL) {
 			nbrp = nbr_params_new(lsr_id);
-			LIST_INSERT_HEAD(&vty_conf->nbrp_list, nbrp, entry);
+			RB_INSERT(nbrp_head, &vty_conf->nbrp_tree, nbrp);
 		} else if (nbrp->auth.method == AUTH_MD5SIG &&
 		    strcmp(nbrp->auth.md5key, password_str) == 0)
 			goto cancel;
@@ -1195,7 +1195,7 @@ ldp_vty_neighbor_ttl_security(struct vty *vty, struct vty_arg *args[])
 	} else {
 		if (nbrp == NULL) {
 			nbrp = nbr_params_new(lsr_id);
-			LIST_INSERT_HEAD(&vty_conf->nbrp_list, nbrp, entry);
+			RB_INSERT(nbrp_head, &vty_conf->nbrp_tree, nbrp);
 		}
 
 		nbrp->flags |= F_NBRP_GTSM;
@@ -1685,14 +1685,14 @@ nbrp_new_api(struct ldpd_conf *conf, struct in_addr lsr_id)
 		return (NULL);
 
 	nbrp = nbr_params_new(lsr_id);
-	LIST_INSERT_HEAD(&conf->nbrp_list, nbrp, entry);
+	RB_INSERT(nbrp_head, &conf->nbrp_tree, nbrp);
 	return (nbrp);
 }
 
 void
-nbrp_del_api(struct nbr_params *nbrp)
+nbrp_del_api(struct ldpd_conf *conf, struct nbr_params *nbrp)
 {
-	LIST_REMOVE(nbrp, entry);
+	RB_REMOVE(nbrp_head, &conf->nbrp_tree, nbrp);
 	free(nbrp);
 }
 
diff --git a/ldpd/ldpd.c b/ldpd/ldpd.c
index cf793f58c..37cc0dec1 100644
--- a/ldpd/ldpd.c
+++ b/ldpd/ldpd.c
@@ -862,7 +862,7 @@ main_imsg_send_config(struct ldpd_conf *xconf)
 			return (-1);
 	}
 
-	LIST_FOREACH(nbrp, &xconf->nbrp_list, entry) {
+	RB_FOREACH(nbrp, nbrp_head, &xconf->nbrp_tree) {
 		if (main_imsg_compose_both(IMSG_RECONF_NBRP, nbrp,
 		    sizeof(*nbrp)) == -1)
 			return (-1);
@@ -961,10 +961,10 @@ ldp_config_reset_main(struct ldpd_conf *conf, void **ref)
 		free(iface);
 	}
 
-	while ((nbrp = LIST_FIRST(&conf->nbrp_list)) != NULL) {
+	while ((nbrp = RB_ROOT(&conf->nbrp_tree)) != NULL) {
 		if (ref && *ref == nbrp)
 			*ref = NULL;
-		LIST_REMOVE(nbrp, entry);
+		RB_REMOVE(nbrp_head, &conf->nbrp_tree, nbrp);
 		free(nbrp);
 	}
 
@@ -1034,7 +1034,7 @@ ldp_dup_config_ref(struct ldpd_conf *conf, void **ref)
 	COPY(xconf, conf);
 	RB_INIT(&xconf->iface_tree);
 	RB_INIT(&xconf->tnbr_tree);
-	LIST_INIT(&xconf->nbrp_list);
+	RB_INIT(&xconf->nbrp_tree);
 	LIST_INIT(&xconf->l2vpn_list);
 
 	RB_FOREACH(iface, iface_head, &conf->iface_tree) {
@@ -1047,9 +1047,9 @@ ldp_dup_config_ref(struct ldpd_conf *conf, void **ref)
 		COPY(xt, tnbr);
 		RB_INSERT(tnbr_head, &xconf->tnbr_tree, xt);
 	}
-	LIST_FOREACH(nbrp, &conf->nbrp_list, entry) {
+	RB_FOREACH(nbrp, nbrp_head, &conf->nbrp_tree) {
 		COPY(xn, nbrp);
-		LIST_INSERT_HEAD(&xconf->nbrp_list, xn, entry);
+		RB_INSERT(nbrp_head, &xconf->nbrp_tree, xn);
 	}
 	LIST_FOREACH(l2vpn, &conf->l2vpn_list, entry) {
 		COPY(xl, l2vpn);
@@ -1101,8 +1101,8 @@ ldp_clear_config(struct ldpd_conf *xconf)
 		RB_REMOVE(tnbr_head, &xconf->tnbr_tree, tnbr);
 		free(tnbr);
 	}
-	while ((nbrp = LIST_FIRST(&xconf->nbrp_list)) != NULL) {
-		LIST_REMOVE(nbrp, entry);
+	while ((nbrp = RB_ROOT(&xconf->nbrp_tree)) != NULL) {
+		RB_REMOVE(nbrp_head, &xconf->nbrp_tree, nbrp);
 		free(nbrp);
 	}
 	while ((l2vpn = LIST_FIRST(&xconf->l2vpn_list)) != NULL) {
@@ -1354,7 +1354,7 @@ merge_nbrps(struct ldpd_conf *conf, struct ldpd_conf *xconf, void **ref)
 	struct nbr		*nbr;
 	int			 nbrp_changed;
 
-	LIST_FOREACH_SAFE(nbrp, &conf->nbrp_list, entry, ntmp) {
+	RB_FOREACH_SAFE(nbrp, nbrp_head, &conf->nbrp_tree, ntmp) {
 		/* find deleted nbrps */
 		if ((xn = nbr_params_find(xconf, nbrp->lsr_id)) == NULL) {
 			switch (ldpd_process) {
@@ -1380,15 +1380,15 @@ merge_nbrps(struct ldpd_conf *conf, struct ldpd_conf *xconf, void **ref)
 				QOBJ_UNREG (nbrp);
 				break;
 			}
-			LIST_REMOVE(nbrp, entry);
+			RB_REMOVE(nbrp_head, &conf->nbrp_tree, nbrp);
 			free(nbrp);
 		}
 	}
-	LIST_FOREACH_SAFE(xn, &xconf->nbrp_list, entry, ntmp) {
+	RB_FOREACH_SAFE(xn, nbrp_head, &xconf->nbrp_tree, ntmp) {
 		/* find new nbrps */
 		if ((nbrp = nbr_params_find(conf, xn->lsr_id)) == NULL) {
-			LIST_REMOVE(xn, entry);
-			LIST_INSERT_HEAD(&conf->nbrp_list, xn, entry);
+			RB_REMOVE(nbrp_head, &xconf->nbrp_tree, xn);
+			RB_INSERT(nbrp_head, &conf->nbrp_tree, xn);
 
 			switch (ldpd_process) {
 			case PROC_LDE_ENGINE:
@@ -1455,7 +1455,7 @@ merge_nbrps(struct ldpd_conf *conf, struct ldpd_conf *xconf, void **ref)
 					nbr_establish_connection(nbr);
 			}
 		}
-		LIST_REMOVE(xn, entry);
+		RB_REMOVE(nbrp_head, &xconf->nbrp_tree, xn);
 		if (ref && *ref == xn)
 			*ref = nbrp;
 		free(xn);
@@ -1772,7 +1772,7 @@ config_new_empty(void)
 
 	RB_INIT(&xconf->iface_tree);
 	RB_INIT(&xconf->tnbr_tree);
-	LIST_INIT(&xconf->nbrp_list);
+	RB_INIT(&xconf->nbrp_tree);
 	LIST_INIT(&xconf->l2vpn_list);
 
 	return (xconf);
diff --git a/ldpd/ldpd.h b/ldpd/ldpd.h
index 7e5b4248a..d8f75a0ee 100644
--- a/ldpd/ldpd.h
+++ b/ldpd/ldpd.h
@@ -304,7 +304,7 @@ enum auth_method {
 
 /* neighbor specific parameters */
 struct nbr_params {
-	LIST_ENTRY(nbr_params)	 entry;
+	RB_ENTRY(nbr_params)	 entry;
 	struct in_addr		 lsr_id;
 	uint16_t		 keepalive;
 	int			 gtsm_enabled;
@@ -317,6 +317,8 @@ struct nbr_params {
 	uint8_t			 flags;
 	QOBJ_FIELDS
 };
+RB_HEAD(nbrp_head, nbr_params);
+RB_PROTOTYPE(nbrp_head, nbr_params, entry, nbr_params_compare);
 DECLARE_QOBJ_TYPE(nbr_params)
 #define F_NBRP_KEEPALIVE	 0x01
 #define F_NBRP_GTSM		 0x02
@@ -410,7 +412,7 @@ struct ldpd_conf {
 	struct ldpd_af_conf	 ipv6;
 	struct iface_head	 iface_tree;
 	struct tnbr_head	 tnbr_tree;
-	LIST_HEAD(, nbr_params)	 nbrp_list;
+	struct nbrp_head	 nbrp_tree;
 	LIST_HEAD(, l2vpn)	 l2vpn_list;
 	uint16_t		 lhello_holdtime;
 	uint16_t		 lhello_interval;
@@ -638,9 +640,10 @@ void			 iface_del_api(struct ldpd_conf *conf,
 struct tnbr		*tnbr_new_api(struct ldpd_conf *conf, int af,
 			    union ldpd_addr *addr);
 void			 tnbr_del_api(struct ldpd_conf *conf, struct tnbr *tnbr);
-struct nbr_params	*nbrp_new_api(struct ldpd_conf *cfg,
+struct nbr_params	*nbrp_new_api(struct ldpd_conf *conf,
 			    struct in_addr lsr_id);
-void			 nbrp_del_api(struct nbr_params *nbrp);
+void			 nbrp_del_api(struct ldpd_conf *conf,
+			    struct nbr_params *nbrp);
 struct l2vpn		*l2vpn_new_api(struct ldpd_conf *cfg, const char *name);
 void			 l2vpn_del_api(struct l2vpn *l2vpn);
 struct l2vpn_if		*l2vpn_if_new_api(struct ldpd_conf *conf,
diff --git a/ldpd/ldpe.c b/ldpd/ldpe.c
index 699ce502f..e9e45f8fe 100644
--- a/ldpd/ldpe.c
+++ b/ldpd/ldpe.c
@@ -416,7 +416,7 @@ ldpe_dispatch_main(struct thread *thread)
 
 			RB_INIT(&nconf->iface_tree);
 			RB_INIT(&nconf->tnbr_tree);
-			LIST_INIT(&nconf->nbrp_list);
+			RB_INIT(&nconf->nbrp_tree);
 			LIST_INIT(&nconf->l2vpn_list);
 			break;
 		case IMSG_RECONF_IFACE:
@@ -444,7 +444,7 @@ ldpe_dispatch_main(struct thread *thread)
 				fatal(NULL);
 			memcpy(nnbrp, imsg.data, sizeof(struct nbr_params));
 
-			LIST_INSERT_HEAD(&nconf->nbrp_list, nnbrp, entry);
+			RB_INSERT(nbrp_head, &nconf->nbrp_tree, nnbrp);
 			break;
 		case IMSG_RECONF_L2VPN:
 			if ((nl2vpn = malloc(sizeof(struct l2vpn))) == NULL)
diff --git a/ldpd/neighbor.c b/ldpd/neighbor.c
index 8376a0154..5addc4dda 100644
--- a/ldpd/neighbor.c
+++ b/ldpd/neighbor.c
@@ -39,10 +39,13 @@ static void		 nbr_start_itimeout(struct nbr *);
 static int		 nbr_idtimer(struct thread *);
 static int		 nbr_act_session_operational(struct nbr *);
 static void		 nbr_send_labelmappings(struct nbr *);
+static __inline int	 nbr_params_compare(struct nbr_params *,
+			    struct nbr_params *);
 
 RB_GENERATE(nbr_id_head, nbr, id_tree, nbr_id_compare)
 RB_GENERATE(nbr_addr_head, nbr, addr_tree, nbr_addr_compare)
 RB_GENERATE(nbr_pid_head, nbr, pid_tree, nbr_pid_compare)
+RB_GENERATE(nbrp_head, nbr_params, entry, nbr_params_compare)
 
 struct {
 	int		state;
@@ -752,6 +755,12 @@ nbr_send_labelmappings(struct nbr *nbr)
 	    NULL, 0);
 }
 
+static __inline int
+nbr_params_compare(struct nbr_params *a, struct nbr_params *b)
+{
+	return (ntohl(a->lsr_id.s_addr) - ntohl(b->lsr_id.s_addr));
+}
+
 struct nbr_params *
 nbr_params_new(struct in_addr lsr_id)
 {
@@ -769,13 +778,9 @@ nbr_params_new(struct in_addr lsr_id)
 struct nbr_params *
 nbr_params_find(struct ldpd_conf *xconf, struct in_addr lsr_id)
 {
-	struct nbr_params *nbrp;
-
-	LIST_FOREACH(nbrp, &xconf->nbrp_list, entry)
-		if (nbrp->lsr_id.s_addr == lsr_id.s_addr)
-			return (nbrp);
-
-	return (NULL);
+	struct nbr_params	 nbrp;
+	nbrp.lsr_id = lsr_id;
+	return (RB_FIND(nbrp_head, &xconf->nbrp_tree, &nbrp));
 }
 
 uint16_t