[cmaster-next] [PATCH 05/10] ldpd: use red-black trees to store 'tnbr' elements
Renato Westphal
renato at opensourcerouting.org
Thu Dec 15 09:55:49 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 | 40 +++++++++++++++++++++++++---------------
ldpd/hello.c | 4 ++--
ldpd/l2vpn.c | 4 ++--
ldpd/lde.c | 4 ++--
ldpd/ldp_vty_conf.c | 12 ++++++------
ldpd/ldpd.c | 34 +++++++++++++++++-----------------
ldpd/ldpd.h | 10 ++++++----
ldpd/ldpe.c | 10 +++++-----
ldpd/ldpe.h | 2 +-
9 files changed, 66 insertions(+), 54 deletions(-)
diff --git a/ldpd/adjacency.c b/ldpd/adjacency.c
index d1a6fac..3f478df 100644
--- a/ldpd/adjacency.c
+++ b/ldpd/adjacency.c
@@ -26,11 +26,14 @@
#include "log.h"
static int adj_itimer(struct thread *);
-static void tnbr_del(struct tnbr *);
+static __inline int tnbr_compare(struct tnbr *, struct tnbr *);
+static void tnbr_del(struct ldpd_conf *, struct tnbr *);
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(tnbr_head, tnbr, entry, tnbr_compare)
+
struct adj *
adj_new(struct in_addr lsr_id, struct hello_source *source,
union ldpd_addr *addr)
@@ -165,7 +168,7 @@ adj_itimer(struct thread *thread)
if (!(adj->source.target->flags & F_TNBR_CONFIGURED) &&
adj->source.target->pw_count == 0) {
/* remove dynamic targeted neighbor */
- tnbr_del(adj->source.target);
+ tnbr_del(leconf, adj->source.target);
return (0);
}
adj->source.target->adj = NULL;
@@ -192,6 +195,17 @@ adj_stop_itimer(struct adj *adj)
/* targeted neighbors */
+static __inline int
+tnbr_compare(struct tnbr *a, struct tnbr *b)
+{
+ if (a->af < b->af)
+ return (-1);
+ if (a->af > b->af)
+ return (1);
+
+ return (ldp_addrcmp(a->af, &a->addr, &b->addr));
+}
+
struct tnbr *
tnbr_new(int af, union ldpd_addr *addr)
{
@@ -208,34 +222,30 @@ tnbr_new(int af, union ldpd_addr *addr)
}
static void
-tnbr_del(struct tnbr *tnbr)
+tnbr_del(struct ldpd_conf *xconf, struct tnbr *tnbr)
{
tnbr_stop_hello_timer(tnbr);
if (tnbr->adj)
adj_del(tnbr->adj, S_SHUTDOWN);
- LIST_REMOVE(tnbr, entry);
+ RB_REMOVE(tnbr_head, &xconf->tnbr_tree, tnbr);
free(tnbr);
}
struct tnbr *
tnbr_find(struct ldpd_conf *xconf, int af, union ldpd_addr *addr)
{
- struct tnbr *tnbr;
-
- LIST_FOREACH(tnbr, &xconf->tnbr_list, entry)
- if (af == tnbr->af &&
- ldp_addrcmp(af, addr, &tnbr->addr) == 0)
- return (tnbr);
-
- return (NULL);
+ struct tnbr tnbr;
+ tnbr.af = af;
+ tnbr.addr = *addr;
+ return (RB_FIND(tnbr_head, &xconf->tnbr_tree, &tnbr));
}
struct tnbr *
-tnbr_check(struct tnbr *tnbr)
+tnbr_check(struct ldpd_conf *xconf, struct tnbr *tnbr)
{
if (!(tnbr->flags & (F_TNBR_CONFIGURED|F_TNBR_DYNAMIC)) &&
tnbr->pw_count == 0) {
- tnbr_del(tnbr);
+ tnbr_del(xconf, tnbr);
return (NULL);
}
@@ -280,7 +290,7 @@ tnbr_update_all(int af)
struct tnbr *tnbr;
/* update targeted neighbors */
- LIST_FOREACH(tnbr, &leconf->tnbr_list, entry)
+ RB_FOREACH(tnbr, tnbr_head, &leconf->tnbr_tree)
if (tnbr->af == af || af == AF_UNSPEC)
tnbr_update(tnbr);
}
diff --git a/ldpd/hello.c b/ldpd/hello.c
index 755b25a..0833ebb 100644
--- a/ldpd/hello.c
+++ b/ldpd/hello.c
@@ -261,7 +261,7 @@ recv_hello(struct in_addr lsr_id, struct ldp_msg *msg, int af,
if (tnbr && (tnbr->flags & F_TNBR_DYNAMIC) &&
!((flags & F_HELLO_REQ_TARG))) {
tnbr->flags &= ~F_TNBR_DYNAMIC;
- tnbr = tnbr_check(tnbr);
+ tnbr = tnbr_check(leconf, tnbr);
}
if (!tnbr) {
@@ -273,7 +273,7 @@ recv_hello(struct in_addr lsr_id, struct ldp_msg *msg, int af,
tnbr = tnbr_new(af, src);
tnbr->flags |= F_TNBR_DYNAMIC;
tnbr_update(tnbr);
- LIST_INSERT_HEAD(&leconf->tnbr_list, tnbr, entry);
+ RB_INSERT(tnbr_head, &leconf->tnbr_tree, tnbr);
}
source.type = HELLO_TARGETED;
diff --git a/ldpd/l2vpn.c b/ldpd/l2vpn.c
index c0f6586..dc9879e 100644
--- a/ldpd/l2vpn.c
+++ b/ldpd/l2vpn.c
@@ -530,7 +530,7 @@ ldpe_l2vpn_pw_init(struct l2vpn_pw *pw)
if (tnbr == NULL) {
tnbr = tnbr_new(pw->af, &pw->addr);
tnbr_update(tnbr);
- LIST_INSERT_HEAD(&leconf->tnbr_list, tnbr, entry);
+ RB_INSERT(tnbr_head, &leconf->tnbr_tree, tnbr);
}
tnbr->pw_count++;
@@ -544,6 +544,6 @@ ldpe_l2vpn_pw_exit(struct l2vpn_pw *pw)
tnbr = tnbr_find(leconf, pw->af, &pw->addr);
if (tnbr) {
tnbr->pw_count--;
- tnbr_check(tnbr);
+ tnbr_check(leconf, tnbr);
}
}
diff --git a/ldpd/lde.c b/ldpd/lde.c
index 1e36218..4b957c5 100644
--- a/ldpd/lde.c
+++ b/ldpd/lde.c
@@ -474,7 +474,7 @@ lde_dispatch_parent(struct thread *thread)
memcpy(nconf, imsg.data, sizeof(struct ldpd_conf));
RB_INIT(&nconf->iface_tree);
- LIST_INIT(&nconf->tnbr_list);
+ RB_INIT(&nconf->tnbr_tree);
LIST_INIT(&nconf->nbrp_list);
LIST_INIT(&nconf->l2vpn_list);
break;
@@ -496,7 +496,7 @@ lde_dispatch_parent(struct thread *thread)
fatal(NULL);
memcpy(ntnbr, imsg.data, sizeof(struct tnbr));
- LIST_INSERT_HEAD(&nconf->tnbr_list, ntnbr, entry);
+ RB_INSERT(tnbr_head, &nconf->tnbr_tree, ntnbr);
break;
case IMSG_RECONF_NBRP:
if ((nnbrp = malloc(sizeof(struct nbr_params))) == NULL)
diff --git a/ldpd/ldp_vty_conf.c b/ldpd/ldp_vty_conf.c
index 689554d..f5c98eb 100644
--- a/ldpd/ldp_vty_conf.c
+++ b/ldpd/ldp_vty_conf.c
@@ -213,7 +213,7 @@ ldp_af_config_write(struct vty *vty, int af, struct ldpd_conf *conf,
vty_out(vty, " session holdtime %u%s", af_conf->keepalive,
VTY_NEWLINE);
- LIST_FOREACH(tnbr, &ldpd_conf->tnbr_list, entry) {
+ RB_FOREACH(tnbr, tnbr_head, &ldpd_conf->tnbr_tree) {
if (tnbr->af == af) {
vty_out(vty, " !%s", VTY_NEWLINE);
vty_out(vty, " neighbor %s targeted%s",
@@ -955,7 +955,7 @@ ldp_vty_neighbor_targeted(struct vty *vty, struct vty_arg *args[])
if (tnbr == NULL)
goto cancel;
- LIST_REMOVE(tnbr, entry);
+ RB_REMOVE(tnbr_head, &vty_conf->tnbr_tree, tnbr);
free(tnbr);
ldp_reload(vty_conf);
return (CMD_SUCCESS);
@@ -966,7 +966,7 @@ ldp_vty_neighbor_targeted(struct vty *vty, struct vty_arg *args[])
tnbr = tnbr_new(af, &addr);
tnbr->flags |= F_TNBR_CONFIGURED;
- LIST_INSERT_HEAD(&vty_conf->tnbr_list, tnbr, entry);
+ RB_INSERT(tnbr_head, &vty_conf->tnbr_tree, tnbr);
ldp_reload(vty_conf);
@@ -1665,14 +1665,14 @@ tnbr_new_api(struct ldpd_conf *conf, int af, union ldpd_addr *addr)
tnbr = tnbr_new(af, addr);
tnbr->flags |= F_TNBR_CONFIGURED;
- LIST_INSERT_HEAD(&conf->tnbr_list, tnbr, entry);
+ RB_INSERT(tnbr_head, &conf->tnbr_tree, tnbr);
return (tnbr);
}
void
-tnbr_del_api(struct tnbr *tnbr)
+tnbr_del_api(struct ldpd_conf *conf, struct tnbr *tnbr)
{
- LIST_REMOVE(tnbr, entry);
+ RB_REMOVE(tnbr_head, &conf->tnbr_tree, tnbr);
free(tnbr);
}
diff --git a/ldpd/ldpd.c b/ldpd/ldpd.c
index 14cfaff..cf793f5 100644
--- a/ldpd/ldpd.c
+++ b/ldpd/ldpd.c
@@ -856,7 +856,7 @@ main_imsg_send_config(struct ldpd_conf *xconf)
return (-1);
}
- LIST_FOREACH(tnbr, &xconf->tnbr_list, entry) {
+ RB_FOREACH(tnbr, tnbr_head, &xconf->tnbr_tree) {
if (main_imsg_compose_both(IMSG_RECONF_TNBR, tnbr,
sizeof(*tnbr)) == -1)
return (-1);
@@ -992,13 +992,13 @@ ldp_config_reset_af(struct ldpd_conf *conf, int af, void **ref)
ia->enabled = 0;
}
- LIST_FOREACH_SAFE(tnbr, &conf->tnbr_list, entry, ttmp) {
+ RB_FOREACH_SAFE(tnbr, tnbr_head, &conf->tnbr_tree, ttmp) {
if (tnbr->af != af)
continue;
if (ref && *ref == tnbr)
*ref = NULL;
- LIST_REMOVE(tnbr, entry);
+ RB_REMOVE(tnbr_head, &conf->tnbr_tree, tnbr);
free(tnbr);
}
@@ -1033,7 +1033,7 @@ ldp_dup_config_ref(struct ldpd_conf *conf, void **ref)
COPY(xconf, conf);
RB_INIT(&xconf->iface_tree);
- LIST_INIT(&xconf->tnbr_list);
+ RB_INIT(&xconf->tnbr_tree);
LIST_INIT(&xconf->nbrp_list);
LIST_INIT(&xconf->l2vpn_list);
@@ -1043,9 +1043,9 @@ ldp_dup_config_ref(struct ldpd_conf *conf, void **ref)
xi->ipv6.iface = xi;
RB_INSERT(iface_head, &xconf->iface_tree, xi);
}
- LIST_FOREACH(tnbr, &conf->tnbr_list, entry) {
+ RB_FOREACH(tnbr, tnbr_head, &conf->tnbr_tree) {
COPY(xt, tnbr);
- LIST_INSERT_HEAD(&xconf->tnbr_list, xt, entry);
+ RB_INSERT(tnbr_head, &xconf->tnbr_tree, xt);
}
LIST_FOREACH(nbrp, &conf->nbrp_list, entry) {
COPY(xn, nbrp);
@@ -1097,8 +1097,8 @@ ldp_clear_config(struct ldpd_conf *xconf)
RB_REMOVE(iface_head, &xconf->iface_tree, iface);
free(iface);
}
- while ((tnbr = LIST_FIRST(&xconf->tnbr_list)) != NULL) {
- LIST_REMOVE(tnbr, entry);
+ while ((tnbr = RB_ROOT(&xconf->tnbr_tree)) != NULL) {
+ RB_REMOVE(tnbr_head, &xconf->tnbr_tree, tnbr);
free(tnbr);
}
while ((nbrp = LIST_FIRST(&xconf->nbrp_list)) != NULL) {
@@ -1295,7 +1295,7 @@ merge_tnbrs(struct ldpd_conf *conf, struct ldpd_conf *xconf, void **ref)
{
struct tnbr *tnbr, *ttmp, *xt;
- LIST_FOREACH_SAFE(tnbr, &conf->tnbr_list, entry, ttmp) {
+ RB_FOREACH_SAFE(tnbr, tnbr_head, &conf->tnbr_tree, ttmp) {
if (!(tnbr->flags & F_TNBR_CONFIGURED))
continue;
@@ -1303,26 +1303,26 @@ merge_tnbrs(struct ldpd_conf *conf, struct ldpd_conf *xconf, void **ref)
if ((xt = tnbr_find(xconf, tnbr->af, &tnbr->addr)) == NULL) {
switch (ldpd_process) {
case PROC_LDE_ENGINE:
- LIST_REMOVE(tnbr, entry);
+ RB_REMOVE(tnbr_head, &conf->tnbr_tree, tnbr);
free(tnbr);
break;
case PROC_LDP_ENGINE:
tnbr->flags &= ~F_TNBR_CONFIGURED;
- tnbr_check(tnbr);
+ tnbr_check(conf, tnbr);
break;
case PROC_MAIN:
- LIST_REMOVE(tnbr, entry);
+ RB_REMOVE(tnbr_head, &conf->tnbr_tree, tnbr);
QOBJ_UNREG (tnbr);
free(tnbr);
break;
}
}
}
- LIST_FOREACH_SAFE(xt, &xconf->tnbr_list, entry, ttmp) {
+ RB_FOREACH_SAFE(xt, tnbr_head, &xconf->tnbr_tree, ttmp) {
/* find new tnbrs */
if ((tnbr = tnbr_find(conf, xt->af, &xt->addr)) == NULL) {
- LIST_REMOVE(xt, entry);
- LIST_INSERT_HEAD(&conf->tnbr_list, xt, entry);
+ RB_REMOVE(tnbr_head, &xconf->tnbr_tree, xt);
+ RB_INSERT(tnbr_head, &conf->tnbr_tree, xt);
switch (ldpd_process) {
case PROC_LDE_ENGINE:
@@ -1340,7 +1340,7 @@ merge_tnbrs(struct ldpd_conf *conf, struct ldpd_conf *xconf, void **ref)
/* update existing tnbrs */
if (!(tnbr->flags & F_TNBR_CONFIGURED))
tnbr->flags |= F_TNBR_CONFIGURED;
- LIST_REMOVE(xt, entry);
+ RB_REMOVE(tnbr_head, &xconf->tnbr_tree, xt);
if (ref && *ref == xt)
*ref = tnbr;
free(xt);
@@ -1771,7 +1771,7 @@ config_new_empty(void)
fatal(NULL);
RB_INIT(&xconf->iface_tree);
- LIST_INIT(&xconf->tnbr_list);
+ RB_INIT(&xconf->tnbr_tree);
LIST_INIT(&xconf->nbrp_list);
LIST_INIT(&xconf->l2vpn_list);
diff --git a/ldpd/ldpd.h b/ldpd/ldpd.h
index 2c516c0..7e5b424 100644
--- a/ldpd/ldpd.h
+++ b/ldpd/ldpd.h
@@ -281,7 +281,7 @@ DECLARE_QOBJ_TYPE(iface)
/* source of targeted hellos */
struct tnbr {
- LIST_ENTRY(tnbr) entry;
+ RB_ENTRY(tnbr) entry;
struct thread *hello_timer;
struct adj *adj;
int af;
@@ -291,6 +291,8 @@ struct tnbr {
uint8_t flags;
QOBJ_FIELDS
};
+RB_HEAD(tnbr_head, tnbr);
+RB_PROTOTYPE(tnbr_head, tnbr, entry, tnbr_compare);
DECLARE_QOBJ_TYPE(tnbr)
#define F_TNBR_CONFIGURED 0x01
#define F_TNBR_DYNAMIC 0x02
@@ -407,7 +409,7 @@ struct ldpd_conf {
struct ldpd_af_conf ipv4;
struct ldpd_af_conf ipv6;
struct iface_head iface_tree;
- LIST_HEAD(, tnbr) tnbr_list;
+ struct tnbr_head tnbr_tree;
LIST_HEAD(, nbr_params) nbrp_list;
LIST_HEAD(, l2vpn) l2vpn_list;
uint16_t lhello_holdtime;
@@ -633,9 +635,9 @@ struct iface *iface_new_api(struct ldpd_conf *conf,
const char *name);
void iface_del_api(struct ldpd_conf *conf,
struct iface *iface);
-struct tnbr *tnbr_new_api(struct ldpd_conf *cfg, int af,
+struct tnbr *tnbr_new_api(struct ldpd_conf *conf, int af,
union ldpd_addr *addr);
-void tnbr_del_api(struct tnbr *tnbr);
+void tnbr_del_api(struct ldpd_conf *conf, struct tnbr *tnbr);
struct nbr_params *nbrp_new_api(struct ldpd_conf *cfg,
struct in_addr lsr_id);
void nbrp_del_api(struct nbr_params *nbrp);
diff --git a/ldpd/ldpe.c b/ldpd/ldpe.c
index 16910a3..699ce50 100644
--- a/ldpd/ldpe.c
+++ b/ldpd/ldpe.c
@@ -415,7 +415,7 @@ ldpe_dispatch_main(struct thread *thread)
memcpy(nconf, imsg.data, sizeof(struct ldpd_conf));
RB_INIT(&nconf->iface_tree);
- LIST_INIT(&nconf->tnbr_list);
+ RB_INIT(&nconf->tnbr_tree);
LIST_INIT(&nconf->nbrp_list);
LIST_INIT(&nconf->l2vpn_list);
break;
@@ -437,7 +437,7 @@ ldpe_dispatch_main(struct thread *thread)
fatal(NULL);
memcpy(ntnbr, imsg.data, sizeof(struct tnbr));
- LIST_INSERT_HEAD(&nconf->tnbr_list, ntnbr, entry);
+ RB_INSERT(tnbr_head, &nconf->tnbr_tree, ntnbr);
break;
case IMSG_RECONF_NBRP:
if ((nnbrp = malloc(sizeof(struct nbr_params))) == NULL)
@@ -743,12 +743,12 @@ ldpe_remove_dynamic_tnbrs(int af)
{
struct tnbr *tnbr, *safe;
- LIST_FOREACH_SAFE(tnbr, &leconf->tnbr_list, entry, safe) {
+ RB_FOREACH_SAFE(tnbr, tnbr_head, &leconf->tnbr_tree, safe) {
if (tnbr->af != af)
continue;
tnbr->flags &= ~F_TNBR_DYNAMIC;
- tnbr_check(tnbr);
+ tnbr_check(leconf, tnbr);
}
}
@@ -832,7 +832,7 @@ ldpe_adj_ctl(struct ctl_conn *c)
}
}
- LIST_FOREACH(tnbr, &leconf->tnbr_list, entry) {
+ RB_FOREACH(tnbr, tnbr_head, &leconf->tnbr_tree) {
memset(&tctl, 0, sizeof(tctl));
tctl.af = tnbr->af;
tctl.addr = tnbr->addr;
diff --git a/ldpd/ldpe.h b/ldpd/ldpe.h
index aab1a7f..52899fd 100644
--- a/ldpd/ldpe.h
+++ b/ldpd/ldpe.h
@@ -225,7 +225,7 @@ void adj_start_itimer(struct adj *);
void adj_stop_itimer(struct adj *);
struct tnbr *tnbr_new(int, union ldpd_addr *);
struct tnbr *tnbr_find(struct ldpd_conf *, int, union ldpd_addr *);
-struct tnbr *tnbr_check(struct tnbr *);
+struct tnbr *tnbr_check(struct ldpd_conf *, struct tnbr *);
void tnbr_update(struct tnbr *);
void tnbr_update_all(int);
uint16_t tnbr_get_hello_holdtime(struct tnbr *);
--
1.9.1
More information about the dev
mailing list