ldpd: use red-black trees to store 'adj' 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>

8 files changed, 84 insertions, 59 deletions

diff --git a/ldpd/adjacency.c b/ldpd/adjacency.c
index 3f478df38a..2e7b43296a 100644
--- a/ldpd/adjacency.c
+++ b/ldpd/adjacency.c
@@ -25,6 +25,7 @@
 #include "ldpe.h"
 #include "log.h"
 
+static __inline int adj_compare(struct adj *, struct adj *);
 static int	 adj_itimer(struct thread *);
 static __inline int tnbr_compare(struct tnbr *, struct tnbr *);
 static void	 tnbr_del(struct ldpd_conf *, struct tnbr *);
@@ -32,8 +33,47 @@ static int	 tnbr_hello_timer(struct thread *);
 static void	 tnbr_start_hello_timer(struct tnbr *);
 static void	 tnbr_stop_hello_timer(struct tnbr *);
 
+RB_GENERATE(global_adj_head, adj, global_entry, adj_compare)
+RB_GENERATE(nbr_adj_head, adj, nbr_entry, adj_compare)
+RB_GENERATE(ia_adj_head, adj, ia_entry, adj_compare)
 RB_GENERATE(tnbr_head, tnbr, entry, tnbr_compare)
 
+static __inline int
+adj_compare(struct adj *a, struct adj *b)
+{
+	if (a->source.type < b->source.type)
+		return (-1);
+	if (a->source.type > b->source.type)
+		return (1);
+
+	switch (a->source.type) {
+	case HELLO_LINK:
+		if (strcmp(a->source.link.ia->iface->name,
+		    b->source.link.ia->iface->name) < 0)
+			return (-1);
+		if (strcmp(a->source.link.ia->iface->name,
+		    b->source.link.ia->iface->name) > 0)
+			return (1);
+		if (a->source.link.ia->af < b->source.link.ia->af)
+			return (-1);
+		if (a->source.link.ia->af > b->source.link.ia->af)
+			return (1);
+		return (ldp_addrcmp(a->source.link.ia->af,
+		    &a->source.link.src_addr, &b->source.link.src_addr));
+	case HELLO_TARGETED:
+		if (a->source.target->af < b->source.target->af)
+			return (-1);
+		if (a->source.target->af > b->source.target->af)
+			return (1);
+		return (ldp_addrcmp(a->source.target->af,
+		    &a->source.target->addr, &b->source.target->addr));
+	default:
+		fatalx("adj_get_af: unknown hello type");
+	}
+
+	return (0);
+}
+
 struct adj *
 adj_new(struct in_addr lsr_id, struct hello_source *source,
     union ldpd_addr *addr)
@@ -51,11 +91,11 @@ adj_new(struct in_addr lsr_id, struct hello_source *source,
 	adj->source = *source;
 	adj->trans_addr = *addr;
 
-	LIST_INSERT_HEAD(&global.adj_list, adj, global_entry);
+	RB_INSERT(global_adj_head, &global.adj_tree, adj);
 
 	switch (source->type) {
 	case HELLO_LINK:
-		LIST_INSERT_HEAD(&source->link.ia->adj_list, adj, ia_entry);
+		RB_INSERT(ia_adj_head, &source->link.ia->adj_tree, adj);
 		break;
 	case HELLO_TARGETED:
 		source->target->adj = adj;
@@ -73,12 +113,12 @@ adj_del_single(struct adj *adj)
 
 	adj_stop_itimer(adj);
 
-	LIST_REMOVE(adj, global_entry);
+	RB_REMOVE(global_adj_head, &global.adj_tree, adj);
 	if (adj->nbr)
-		LIST_REMOVE(adj, nbr_entry);
+		RB_REMOVE(nbr_adj_head, &adj->nbr->adj_tree, adj);
 	switch (adj->source.type) {
 	case HELLO_LINK:
-		LIST_REMOVE(adj, ia_entry);
+		RB_REMOVE(ia_adj_head, &adj->source.link.ia->adj_tree, adj);
 		break;
 	case HELLO_TARGETED:
 		adj->source.target->adj = NULL;
@@ -102,7 +142,7 @@ adj_del(struct adj *adj, uint32_t notif_status)
 	 * then delete it.
 	 */
 	if (nbr && nbr_adj_count(nbr, nbr->af) == 0) {
-		LIST_FOREACH_SAFE(adj, &nbr->adj_list, nbr_entry, atmp)
+		RB_FOREACH_SAFE(adj, nbr_adj_head, &nbr->adj_tree, atmp)
 			adj_del_single(adj);
 		session_shutdown(nbr, notif_status, 0, 0);
 		nbr_del(nbr);
@@ -112,31 +152,9 @@ adj_del(struct adj *adj, uint32_t notif_status)
 struct adj *
 adj_find(struct hello_source *source)
 {
-	struct adj *adj;
-
-	LIST_FOREACH(adj, &global.adj_list, global_entry) {
-		if (adj->source.type != source->type)
-			continue;
-
-		switch (source->type) {
-		case HELLO_LINK:
-			if (strcmp(source->link.ia->iface->name,
-			    adj->source.link.ia->iface->name))
-				continue;
-
-			if (ldp_addrcmp(source->link.ia->af,
-			    &adj->source.link.src_addr,
-			    &source->link.src_addr) == 0)
-				return (adj);
-			break;
-		case HELLO_TARGETED:
-			if (adj->source.target == source->target)
-				return (adj);
-			break;
-		}
-	}
-
-	return (NULL);
+	struct adj	 adj;
+	adj.source = *source;
+	return (RB_FIND(global_adj_head, &global.adj_tree, &adj));
 }
 
 int
diff --git a/ldpd/hello.c b/ldpd/hello.c
index 0833ebbafb..95be1d5111 100644
--- a/ldpd/hello.c
+++ b/ldpd/hello.c
@@ -364,7 +364,7 @@ recv_hello(struct in_addr lsr_id, struct ldp_msg *msg, int af,
 		adj = adj_new(lsr_id, &source, &trans_addr);
 		if (nbr) {
 			adj->nbr = nbr;
-			LIST_INSERT_HEAD(&nbr->adj_list, adj, nbr_entry);
+			RB_INSERT(nbr_adj_head, &nbr->adj_tree, adj);
 		}
 	}
 
diff --git a/ldpd/interface.c b/ldpd/interface.c
index 06d36fef72..8fea91b878 100644
--- a/ldpd/interface.c
+++ b/ldpd/interface.c
@@ -66,14 +66,14 @@ if_new(struct kif *kif)
 	iface->ipv4.iface = iface;
 	iface->ipv4.enabled = 0;
 	iface->ipv4.state = IF_STA_DOWN;
-	LIST_INIT(&iface->ipv4.adj_list);
+	RB_INIT(&iface->ipv4.adj_tree);
 
 	/* ipv6 */
 	iface->ipv6.af = AF_INET6;
 	iface->ipv6.iface = iface;
 	iface->ipv6.enabled = 0;
 	iface->ipv6.state = IF_STA_DOWN;
-	LIST_INIT(&iface->ipv6.adj_list);
+	RB_INIT(&iface->ipv6.adj_tree);
 
 	return (iface);
 }
@@ -293,7 +293,7 @@ if_reset(struct iface *iface, int af)
 	ia = iface_af_get(iface, af);
 	if_stop_hello_timer(ia);
 
-	while ((adj = LIST_FIRST(&ia->adj_list)) != NULL)
+	while ((adj = RB_ROOT(&ia->adj_tree)) != NULL)
 		adj_del(adj, S_SHUTDOWN);
 
 	/* try to cleanup */
@@ -465,7 +465,7 @@ if_to_ctl(struct iface_af *ia)
 		ictl.uptime = 0;
 
 	ictl.adj_cnt = 0;
-	LIST_FOREACH(adj, &ia->adj_list, ia_entry)
+	RB_FOREACH(adj, ia_adj_head, &ia->adj_tree)
 		ictl.adj_cnt++;
 
 	return (&ictl);
diff --git a/ldpd/lde.c b/ldpd/lde.c
index aa83ef0aba..5b2ae00fe6 100644
--- a/ldpd/lde.c
+++ b/ldpd/lde.c
@@ -484,8 +484,8 @@ lde_dispatch_parent(struct thread *thread)
 			memcpy(niface, imsg.data, sizeof(struct iface));
 
 			LIST_INIT(&niface->addr_list);
-			LIST_INIT(&niface->ipv4.adj_list);
-			LIST_INIT(&niface->ipv6.adj_list);
+			RB_INIT(&niface->ipv4.adj_tree);
+			RB_INIT(&niface->ipv6.adj_tree);
 			niface->ipv4.iface = niface;
 			niface->ipv6.iface = niface;
 
diff --git a/ldpd/ldpd.h b/ldpd/ldpd.h
index 6836920bc9..4d575597ae 100644
--- a/ldpd/ldpd.h
+++ b/ldpd/ldpd.h
@@ -196,7 +196,10 @@ enum nbr_action {
 	NBR_ACT_CLOSE_SESSION
 };
 
-TAILQ_HEAD(mapping_head, mapping_entry);
+/* forward declarations */
+RB_HEAD(global_adj_head, adj);
+RB_HEAD(nbr_adj_head, adj);
+RB_HEAD(ia_adj_head, adj);
 
 struct map {
 	uint8_t		type;
@@ -256,7 +259,7 @@ struct iface_af {
 	int			 af;
 	int			 enabled;
 	int			 state;
-	LIST_HEAD(, adj)	 adj_list;
+	struct ia_adj_head	 adj_tree;
 	time_t			 uptime;
 	struct thread		*hello_timer;
 	uint16_t		 hello_holdtime;
@@ -450,7 +453,7 @@ struct ldpd_global {
 	uint32_t		 conf_seqnum;
 	int			 pfkeysock;
 	struct if_addr_head	 addr_list;
-	LIST_HEAD(, adj)	 adj_list;
+	struct global_adj_head	 adj_tree;
 	struct in_addr		 mcast_addr_v4;
 	struct in6_addr		 mcast_addr_v6;
 	TAILQ_HEAD(, pending_conn) pending_conns;
diff --git a/ldpd/ldpe.c b/ldpd/ldpe.c
index c3640d4131..c960acf3b1 100644
--- a/ldpd/ldpe.c
+++ b/ldpd/ldpe.c
@@ -111,7 +111,7 @@ ldpe(const char *user, const char *group)
 	ldpd_process = PROC_LDP_ENGINE;
 
 	LIST_INIT(&global.addr_list);
-	LIST_INIT(&global.adj_list);
+	RB_INIT(&global.adj_tree);
 	TAILQ_INIT(&global.pending_conns);
 	if (inet_pton(AF_INET, AllRouters_v4, &global.mcast_addr_v4) != 1)
 		fatal("inet_pton");
@@ -209,7 +209,7 @@ ldpe_shutdown(void)
 		LIST_REMOVE(if_addr, entry);
 		free(if_addr);
 	}
-	while ((adj = LIST_FIRST(&global.adj_list)) != NULL)
+	while ((adj = RB_ROOT(&global.adj_tree)) != NULL)
 		adj_del(adj, S_SHUTDOWN);
 
 	/* clean up */
@@ -425,8 +425,8 @@ ldpe_dispatch_main(struct thread *thread)
 			memcpy(niface, imsg.data, sizeof(struct iface));
 
 			LIST_INIT(&niface->addr_list);
-			LIST_INIT(&niface->ipv4.adj_list);
-			LIST_INIT(&niface->ipv6.adj_list);
+			RB_INIT(&niface->ipv4.adj_tree);
+			RB_INIT(&niface->ipv6.adj_tree);
 			niface->ipv4.iface = niface;
 			niface->ipv6.iface = niface;
 
@@ -814,18 +814,18 @@ ldpe_adj_ctl(struct ctl_conn *c)
 			continue;
 
 		strlcpy(ictl.name, iface->name, sizeof(ictl.name));
-		if (LIST_EMPTY(&iface->ipv4.adj_list) &&
-		    LIST_EMPTY(&iface->ipv6.adj_list))
+		if (RB_EMPTY(&iface->ipv4.adj_tree) &&
+		    RB_EMPTY(&iface->ipv6.adj_tree))
 			ictl.no_adj = 1;
 		imsg_compose_event(&c->iev, IMSG_CTL_SHOW_DISC_IFACE, 0, 0,
 		    -1, &ictl, sizeof(ictl));
 
-		LIST_FOREACH(adj, &iface->ipv4.adj_list, ia_entry) {
+		RB_FOREACH(adj, ia_adj_head, &iface->ipv4.adj_tree) {
 			actl = adj_to_ctl(adj);
 			imsg_compose_event(&c->iev, IMSG_CTL_SHOW_DISC_ADJ,
 			    0, 0, -1, actl, sizeof(struct ctl_adj));
 		}
-		LIST_FOREACH(adj, &iface->ipv6.adj_list, ia_entry) {
+		RB_FOREACH(adj, ia_adj_head, &iface->ipv6.adj_tree) {
 			actl = adj_to_ctl(adj);
 			imsg_compose_event(&c->iev, IMSG_CTL_SHOW_DISC_ADJ,
 			    0, 0, -1, actl, sizeof(struct ctl_adj));
@@ -869,7 +869,7 @@ ldpe_nbr_ctl(struct ctl_conn *c)
 		imsg_compose_event(&c->iev, IMSG_CTL_SHOW_NBR, 0, 0, -1, nctl,
 		    sizeof(struct ctl_nbr));
 
-		LIST_FOREACH(adj, &nbr->adj_list, nbr_entry) {
+		RB_FOREACH(adj, nbr_adj_head, &nbr->adj_tree) {
 			actl = adj_to_ctl(adj);
 			imsg_compose_event(&c->iev, IMSG_CTL_SHOW_NBR_DISC,
 			    0, 0, -1, actl, sizeof(struct ctl_adj));
diff --git a/ldpd/ldpe.h b/ldpd/ldpe.h
index 52899fd85c..81add63836 100644
--- a/ldpd/ldpe.h
+++ b/ldpd/ldpe.h
@@ -32,6 +32,9 @@
 #define min(x,y) ((x) <= (y) ? (x) : (y))
 #define max(x,y) ((x) > (y) ? (x) : (y))
 
+/* forward declarations */
+TAILQ_HEAD(mapping_head, mapping_entry);
+
 struct hello_source {
 	enum hello_type		 type;
 	struct {
@@ -42,9 +45,7 @@ struct hello_source {
 };
 
 struct adj {
-	LIST_ENTRY(adj)		 global_entry;
-	LIST_ENTRY(adj)		 nbr_entry;
-	LIST_ENTRY(adj)		 ia_entry;
+	RB_ENTRY(adj)		 global_entry, nbr_entry, ia_entry;
 	struct in_addr		 lsr_id;
 	struct nbr		*nbr;
 	int			 ds_tlv;
@@ -53,6 +54,9 @@ struct adj {
 	uint16_t		 holdtime;
 	union ldpd_addr		 trans_addr;
 };
+RB_PROTOTYPE(global_adj_head, adj, global_entry, adj_compare)
+RB_PROTOTYPE(nbr_adj_head, adj, nbr_entry, adj_compare)
+RB_PROTOTYPE(ia_adj_head, adj, ia_entry, adj_compare)
 
 struct tcp_conn {
 	struct nbr		*nbr;
@@ -67,7 +71,7 @@ struct tcp_conn {
 struct nbr {
 	RB_ENTRY(nbr)		 id_tree, addr_tree, pid_tree;
 	struct tcp_conn		*tcp;
-	LIST_HEAD(, adj)	 adj_list;	/* adjacencies */
+	struct nbr_adj_head	 adj_tree;	/* adjacencies */
 	struct thread		*ev_connect;
 	struct thread		*keepalive_timer;
 	struct thread		*keepalive_timeout;
diff --git a/ldpd/neighbor.c b/ldpd/neighbor.c
index 5addc4dda2..d24ceb1229 100644
--- a/ldpd/neighbor.c
+++ b/ldpd/neighbor.c
@@ -229,7 +229,7 @@ nbr_new(struct in_addr id, int af, int ds_tlv, union ldpd_addr *addr,
 	if ((nbr = calloc(1, sizeof(*nbr))) == NULL)
 		fatal(__func__);
 
-	LIST_INIT(&nbr->adj_list);
+	RB_INIT(&nbr->adj_tree);
 	nbr->state = NBR_STA_PRESENT;
 	nbr->peerid = 0;
 	nbr->af = af;
@@ -244,10 +244,10 @@ nbr_new(struct in_addr id, int af, int ds_tlv, union ldpd_addr *addr,
 	nbr->raddr_scope = scope_id;
 	nbr->conf_seqnum = 0;
 
-	LIST_FOREACH(adj, &global.adj_list, global_entry) {
+	RB_FOREACH(adj, global_adj_head, &global.adj_tree) {
 		if (adj->lsr_id.s_addr == nbr->id.s_addr) {
 			adj->nbr = nbr;
-			LIST_INSERT_HEAD(&nbr->adj_list, adj, nbr_entry);
+			RB_INSERT(nbr_adj_head, &nbr->adj_tree, adj);
 		}
 	}
 
@@ -366,7 +366,7 @@ nbr_adj_count(struct nbr *nbr, int af)
 	struct adj	*adj;
 	int		 total = 0;
 
-	LIST_FOREACH(adj, &nbr->adj_list, nbr_entry)
+	RB_FOREACH(adj, nbr_adj_head, &nbr->adj_tree)
 		if (adj_get_af(adj) == af)
 			total++;
 
@@ -624,7 +624,7 @@ nbr_establish_connection(struct nbr *nbr)
 	 * Send an extra hello to guarantee that the remote peer has formed
 	 * an adjacency as well.
 	 */
-	LIST_FOREACH(adj, &nbr->adj_list, nbr_entry)
+	RB_FOREACH(adj, nbr_adj_head, &nbr->adj_tree)
 		send_hello(adj->source.type, adj->source.link.ia,
 		    adj->source.target);