[cmaster-next] [PATCH 10/10] ldpd: use red-black trees to store 'adj' elements
Renato Westphal
renato at opensourcerouting.org
Thu Dec 15 09:55:54 EST 2016
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 at opensourcerouting.org>
---
ldpd/adjacency.c | 80 ++++++++++++++++++++++++++++++++++----------------------
ldpd/hello.c | 2 +-
ldpd/interface.c | 8 +++---
ldpd/lde.c | 4 +--
ldpd/ldpd.h | 9 ++++---
ldpd/ldpe.c | 18 ++++++-------
ldpd/ldpe.h | 12 ++++++---
ldpd/neighbor.c | 10 +++----
8 files changed, 84 insertions(+), 59 deletions(-)
diff --git a/ldpd/adjacency.c b/ldpd/adjacency.c
index 3f478df..2e7b432 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 0833ebb..95be1d5 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 06d36fe..8fea91b 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 aa83ef0..5b2ae00 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 6836920..4d57559 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 c3640d4..c960acf 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 52899fd..81add63 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 5addc4d..d24ceb1 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);
--
1.9.1
More information about the dev
mailing list