[cmaster-next] [PATCH 06/10] ldpd: use red-black trees to store 'nbr_params' elements
Renato Westphal
renato at opensourcerouting.org
Thu Dec 15 09:55:50 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/lde.c | 4 ++--
ldpd/ldp_vty_conf.c | 14 +++++++-------
ldpd/ldpd.c | 30 +++++++++++++++---------------
ldpd/ldpd.h | 11 +++++++----
ldpd/ldpe.c | 4 ++--
ldpd/neighbor.c | 19 ++++++++++++-------
6 files changed, 45 insertions(+), 37 deletions(-)
diff --git a/ldpd/lde.c b/ldpd/lde.c
index 4b957c5..80557ed 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 f5c98eb..95b0971 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 cf793f5..37cc0de 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 7e5b424..d8f75a0 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 699ce50..e9e45f8 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 8376a01..5addc4d 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
--
1.9.1
More information about the dev
mailing list