[cmaster-next] [PATCH 04/10] ldpd: use red-black trees to store 'iface' elements
Renato Westphal
renato at opensourcerouting.org
Thu Dec 15 09:55:48 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/interface.c | 37 +++++++++++++++++++++----------------
ldpd/lde.c | 4 ++--
ldpd/ldp_debug.c | 4 ++--
ldpd/ldp_vty_conf.c | 10 +++++-----
ldpd/ldpd.c | 32 ++++++++++++++++----------------
ldpd/ldpd.h | 11 +++++++----
ldpd/ldpe.c | 8 ++++----
7 files changed, 57 insertions(+), 49 deletions(-)
diff --git a/ldpd/interface.c b/ldpd/interface.c
index b6472fe..06d36fe 100644
--- a/ldpd/interface.c
+++ b/ldpd/interface.c
@@ -26,6 +26,7 @@
#include "sockopt.h"
+static __inline int iface_compare(struct iface *, struct iface *);
static struct if_addr *if_addr_new(struct kaddr *);
static struct if_addr *if_addr_lookup(struct if_addr_head *, struct kaddr *);
static int if_start(struct iface *, int);
@@ -39,6 +40,14 @@ static int if_leave_ipv4_group(struct iface *, struct in_addr *);
static int if_join_ipv6_group(struct iface *, struct in6_addr *);
static int if_leave_ipv6_group(struct iface *, struct in6_addr *);
+RB_GENERATE(iface_head, iface, entry, iface_compare)
+
+static __inline int
+iface_compare(struct iface *a, struct iface *b)
+{
+ return (strcmp(a->name, b->name));
+}
+
struct iface *
if_new(struct kif *kif)
{
@@ -69,18 +78,6 @@ if_new(struct kif *kif)
return (iface);
}
-struct iface *
-if_lookup(struct ldpd_conf *xconf, unsigned short ifindex)
-{
- struct iface *iface;
-
- LIST_FOREACH(iface, &xconf->iface_list, entry)
- if (iface->ifindex == ifindex)
- return (iface);
-
- return (NULL);
-}
-
void
if_exit(struct iface *iface)
{
@@ -100,17 +97,25 @@ if_exit(struct iface *iface)
}
struct iface *
-if_lookup_name(struct ldpd_conf *xconf, const char *ifname)
+if_lookup(struct ldpd_conf *xconf, unsigned short ifindex)
{
struct iface *iface;
- LIST_FOREACH(iface, &xconf->iface_list, entry)
- if (strcmp(iface->name, ifname) == 0)
+ RB_FOREACH(iface, iface_head, &xconf->iface_tree)
+ if (iface->ifindex == ifindex)
return (iface);
return (NULL);
}
+struct iface *
+if_lookup_name(struct ldpd_conf *xconf, const char *ifname)
+{
+ struct iface iface;
+ strlcpy(iface.name, ifname, sizeof(iface.name));
+ return (RB_FIND(iface_head, &xconf->iface_tree, &iface));
+}
+
void
if_update_info(struct iface *iface, struct kif *kif)
{
@@ -380,7 +385,7 @@ if_update_all(int af)
{
struct iface *iface;
- LIST_FOREACH(iface, &leconf->iface_list, entry)
+ RB_FOREACH(iface, iface_head, &leconf->iface_tree)
if_update(iface, af);
}
diff --git a/ldpd/lde.c b/ldpd/lde.c
index a1309c6..1e36218 100644
--- a/ldpd/lde.c
+++ b/ldpd/lde.c
@@ -473,7 +473,7 @@ lde_dispatch_parent(struct thread *thread)
fatal(NULL);
memcpy(nconf, imsg.data, sizeof(struct ldpd_conf));
- LIST_INIT(&nconf->iface_list);
+ RB_INIT(&nconf->iface_tree);
LIST_INIT(&nconf->tnbr_list);
LIST_INIT(&nconf->nbrp_list);
LIST_INIT(&nconf->l2vpn_list);
@@ -489,7 +489,7 @@ lde_dispatch_parent(struct thread *thread)
niface->ipv4.iface = niface;
niface->ipv6.iface = niface;
- LIST_INSERT_HEAD(&nconf->iface_list, niface, entry);
+ RB_INSERT(iface_head, &nconf->iface_tree, niface);
break;
case IMSG_RECONF_TNBR:
if ((ntnbr = malloc(sizeof(struct tnbr))) == NULL)
diff --git a/ldpd/ldp_debug.c b/ldpd/ldp_debug.c
index 15dd06a..86b679d 100644
--- a/ldpd/ldp_debug.c
+++ b/ldpd/ldp_debug.c
@@ -74,7 +74,7 @@ ldp_vty_debug(struct vty *vty, struct vty_arg *args[])
DEBUG_OFF(event, EVENT);
else
DEBUG_ON(event, EVENT);
- } else if (strcmp(type_str, "messages") == 0) {
+ } else if (strcmp(type_str, "messages") == 0) {
all = (vty_get_arg_value(args, "all")) ? 1 : 0;
dir_str = vty_get_arg_value(args, "dir");
if (dir_str == NULL)
@@ -99,7 +99,7 @@ ldp_vty_debug(struct vty *vty, struct vty_arg *args[])
DEBUG_ON(msg, MSG_SEND_ALL);
}
}
- } else if (strcmp(type_str, "zebra") == 0) {
+ } else if (strcmp(type_str, "zebra") == 0) {
if (disable)
DEBUG_OFF(zebra, ZEBRA);
else
diff --git a/ldpd/ldp_vty_conf.c b/ldpd/ldp_vty_conf.c
index dd70365..689554d 100644
--- a/ldpd/ldp_vty_conf.c
+++ b/ldpd/ldp_vty_conf.c
@@ -142,7 +142,7 @@ ldp_af_iface_config_write(struct vty *vty, int af)
struct iface *iface;
struct iface_af *ia;
- LIST_FOREACH(iface, &ldpd_conf->iface_list, entry) {
+ RB_FOREACH(iface, iface_head, &ldpd_conf->iface_tree) {
ia = iface_af_get(iface, af);
if (!ia->enabled)
continue;
@@ -857,7 +857,7 @@ ldp_vty_interface(struct vty *vty, struct vty_arg *args[])
ia = iface_af_get(iface, af);
ia->enabled = 1;
- LIST_INSERT_HEAD(&vty_conf->iface_list, iface, entry);
+ RB_INSERT(iface_head, &vty_conf->iface_tree, iface);
ldp_reload_ref(vty_conf, (void **)&iface);
} else {
memset(&kif, 0, sizeof(kif));
@@ -1641,14 +1641,14 @@ iface_new_api(struct ldpd_conf *conf, const char *name)
}
iface = if_new(&kif);
- LIST_INSERT_HEAD(&conf->iface_list, iface, entry);
+ RB_INSERT(iface_head, &conf->iface_tree, iface);
return (iface);
}
void
-iface_del_api(struct iface *iface)
+iface_del_api(struct ldpd_conf *conf, struct iface *iface)
{
- LIST_REMOVE(iface, entry);
+ RB_REMOVE(iface_head, &conf->iface_tree, iface);
free(iface);
}
diff --git a/ldpd/ldpd.c b/ldpd/ldpd.c
index aa1dc57..14cfaff 100644
--- a/ldpd/ldpd.c
+++ b/ldpd/ldpd.c
@@ -850,7 +850,7 @@ main_imsg_send_config(struct ldpd_conf *xconf)
sizeof(*xconf)) == -1)
return (-1);
- LIST_FOREACH(iface, &xconf->iface_list, entry) {
+ RB_FOREACH(iface, iface_head, &xconf->iface_tree) {
if (main_imsg_compose_both(IMSG_RECONF_IFACE, iface,
sizeof(*iface)) == -1)
return (-1);
@@ -954,10 +954,10 @@ ldp_config_reset_main(struct ldpd_conf *conf, void **ref)
struct iface *iface;
struct nbr_params *nbrp;
- while ((iface = LIST_FIRST(&conf->iface_list)) != NULL) {
+ while ((iface = RB_ROOT(&conf->iface_tree)) != NULL) {
if (ref && *ref == iface)
*ref = NULL;
- LIST_REMOVE(iface, entry);
+ RB_REMOVE(iface_head, &conf->iface_tree, iface);
free(iface);
}
@@ -987,7 +987,7 @@ ldp_config_reset_af(struct ldpd_conf *conf, int af, void **ref)
struct iface_af *ia;
struct tnbr *tnbr, *ttmp;
- LIST_FOREACH(iface, &conf->iface_list, entry) {
+ RB_FOREACH(iface, iface_head, &conf->iface_tree) {
ia = iface_af_get(iface, af);
ia->enabled = 0;
}
@@ -1032,16 +1032,16 @@ ldp_dup_config_ref(struct ldpd_conf *conf, void **ref)
} while (0)
COPY(xconf, conf);
- LIST_INIT(&xconf->iface_list);
+ RB_INIT(&xconf->iface_tree);
LIST_INIT(&xconf->tnbr_list);
LIST_INIT(&xconf->nbrp_list);
LIST_INIT(&xconf->l2vpn_list);
- LIST_FOREACH(iface, &conf->iface_list, entry) {
+ RB_FOREACH(iface, iface_head, &conf->iface_tree) {
COPY(xi, iface);
xi->ipv4.iface = xi;
xi->ipv6.iface = xi;
- LIST_INSERT_HEAD(&xconf->iface_list, xi, entry);
+ RB_INSERT(iface_head, &xconf->iface_tree, xi);
}
LIST_FOREACH(tnbr, &conf->tnbr_list, entry) {
COPY(xt, tnbr);
@@ -1093,8 +1093,8 @@ ldp_clear_config(struct ldpd_conf *xconf)
struct nbr_params *nbrp;
struct l2vpn *l2vpn;
- while ((iface = LIST_FIRST(&xconf->iface_list)) != NULL) {
- LIST_REMOVE(iface, entry);
+ while ((iface = RB_ROOT(&xconf->iface_tree)) != NULL) {
+ RB_REMOVE(iface_head, &xconf->iface_tree, iface);
free(iface);
}
while ((tnbr = LIST_FIRST(&xconf->tnbr_list)) != NULL) {
@@ -1236,10 +1236,10 @@ merge_ifaces(struct ldpd_conf *conf, struct ldpd_conf *xconf, void **ref)
{
struct iface *iface, *itmp, *xi;
- LIST_FOREACH_SAFE(iface, &conf->iface_list, entry, itmp) {
+ RB_FOREACH_SAFE(iface, iface_head, &conf->iface_tree, itmp) {
/* find deleted interfaces */
if ((xi = if_lookup_name(xconf, iface->name)) == NULL) {
- LIST_REMOVE(iface, entry);
+ RB_REMOVE(iface_head, &conf->iface_tree, iface);
switch (ldpd_process) {
case PROC_LDE_ENGINE:
@@ -1254,11 +1254,11 @@ merge_ifaces(struct ldpd_conf *conf, struct ldpd_conf *xconf, void **ref)
free(iface);
}
}
- LIST_FOREACH_SAFE(xi, &xconf->iface_list, entry, itmp) {
+ RB_FOREACH_SAFE(xi, iface_head, &xconf->iface_tree, itmp) {
/* find new interfaces */
if ((iface = if_lookup_name(conf, xi->name)) == NULL) {
- LIST_REMOVE(xi, entry);
- LIST_INSERT_HEAD(&conf->iface_list, xi, entry);
+ RB_REMOVE(iface_head, &xconf->iface_tree, xi);
+ RB_INSERT(iface_head, &conf->iface_tree, xi);
if (ldpd_process == PROC_MAIN) {
QOBJ_REG (xi, iface);
@@ -1271,7 +1271,7 @@ merge_ifaces(struct ldpd_conf *conf, struct ldpd_conf *xconf, void **ref)
/* update existing interfaces */
merge_iface_af(&iface->ipv4, &xi->ipv4);
merge_iface_af(&iface->ipv6, &xi->ipv6);
- LIST_REMOVE(xi, entry);
+ RB_REMOVE(iface_head, &xconf->iface_tree, xi);
if (ref && *ref == xi)
*ref = iface;
free(xi);
@@ -1770,7 +1770,7 @@ config_new_empty(void)
if (xconf == NULL)
fatal(NULL);
- LIST_INIT(&xconf->iface_list);
+ RB_INIT(&xconf->iface_tree);
LIST_INIT(&xconf->tnbr_list);
LIST_INIT(&xconf->nbrp_list);
LIST_INIT(&xconf->l2vpn_list);
diff --git a/ldpd/ldpd.h b/ldpd/ldpd.h
index 630b192..2c516c0 100644
--- a/ldpd/ldpd.h
+++ b/ldpd/ldpd.h
@@ -264,7 +264,7 @@ struct iface_af {
};
struct iface {
- LIST_ENTRY(iface) entry;
+ RB_ENTRY(iface) entry;
char name[IF_NAMESIZE];
unsigned int ifindex;
struct if_addr_head addr_list;
@@ -275,6 +275,8 @@ struct iface {
struct iface_af ipv6;
QOBJ_FIELDS
};
+RB_HEAD(iface_head, iface);
+RB_PROTOTYPE(iface_head, iface, entry, iface_compare);
DECLARE_QOBJ_TYPE(iface)
/* source of targeted hellos */
@@ -404,7 +406,7 @@ struct ldpd_conf {
struct in_addr rtr_id;
struct ldpd_af_conf ipv4;
struct ldpd_af_conf ipv6;
- LIST_HEAD(, iface) iface_list;
+ struct iface_head iface_tree;
LIST_HEAD(, tnbr) tnbr_list;
LIST_HEAD(, nbr_params) nbrp_list;
LIST_HEAD(, l2vpn) l2vpn_list;
@@ -627,9 +629,10 @@ void config_clear(struct ldpd_conf *);
/* ldp_vty_conf.c */
/* NOTE: the parameters' names should be preserved because of codegen */
-struct iface *iface_new_api(struct ldpd_conf *cfg,
+struct iface *iface_new_api(struct ldpd_conf *conf,
const char *name);
-void iface_del_api(struct iface *iface);
+void iface_del_api(struct ldpd_conf *conf,
+ struct iface *iface);
struct tnbr *tnbr_new_api(struct ldpd_conf *cfg, int af,
union ldpd_addr *addr);
void tnbr_del_api(struct tnbr *tnbr);
diff --git a/ldpd/ldpe.c b/ldpd/ldpe.c
index aef33c8..16910a3 100644
--- a/ldpd/ldpe.c
+++ b/ldpd/ldpe.c
@@ -414,7 +414,7 @@ ldpe_dispatch_main(struct thread *thread)
fatal(NULL);
memcpy(nconf, imsg.data, sizeof(struct ldpd_conf));
- LIST_INIT(&nconf->iface_list);
+ RB_INIT(&nconf->iface_tree);
LIST_INIT(&nconf->tnbr_list);
LIST_INIT(&nconf->nbrp_list);
LIST_INIT(&nconf->l2vpn_list);
@@ -430,7 +430,7 @@ ldpe_dispatch_main(struct thread *thread)
niface->ipv4.iface = niface;
niface->ipv6.iface = niface;
- LIST_INSERT_HEAD(&nconf->iface_list, niface, entry);
+ RB_INSERT(iface_head, &nconf->iface_tree, niface);
break;
case IMSG_RECONF_TNBR:
if ((ntnbr = malloc(sizeof(struct tnbr))) == NULL)
@@ -772,7 +772,7 @@ ldpe_iface_af_ctl(struct ctl_conn *c, int af, unsigned int idx)
struct iface_af *ia;
struct ctl_iface *ictl;
- LIST_FOREACH(iface, &leconf->iface_list, entry) {
+ RB_FOREACH(iface, iface_head, &leconf->iface_tree) {
if (idx == 0 || idx == iface->ifindex) {
ia = iface_af_get(iface, af);
if (!ia->enabled)
@@ -805,7 +805,7 @@ ldpe_adj_ctl(struct ctl_conn *c)
imsg_compose_event(&c->iev, IMSG_CTL_SHOW_DISCOVERY, 0, 0, -1, NULL, 0);
- LIST_FOREACH(iface, &leconf->iface_list, entry) {
+ RB_FOREACH(iface, iface_head, &leconf->iface_tree) {
memset(&ictl, 0, sizeof(ictl));
ictl.active_v4 = (iface->ipv4.state == IF_STA_ACTIVE);
ictl.active_v6 = (iface->ipv6.state == IF_STA_ACTIVE);
--
1.9.1
More information about the dev
mailing list