[cmaster-next] [PATCH 03/10] ldpd: use red-black trees to store 'lde_map' elements
Renato Westphal
renato at opensourcerouting.org
Thu Dec 15 09:55:47 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/l2vpn.c | 4 ++--
ldpd/lde.c | 17 ++++++++++++++---
ldpd/lde.h | 9 ++++++---
ldpd/lde_lib.c | 18 +++++++++---------
4 files changed, 31 insertions(+), 17 deletions(-)
diff --git a/ldpd/l2vpn.c b/ldpd/l2vpn.c
index 851ff77..c0f6586 100644
--- a/ldpd/l2vpn.c
+++ b/ldpd/l2vpn.c
@@ -459,7 +459,7 @@ l2vpn_binding_ctl(pid_t pid)
fn = (struct fec_node *)f;
if (fn->local_label == NO_LABEL &&
- LIST_EMPTY(&fn->downstream))
+ RB_EMPTY(&fn->downstream))
continue;
memset(&pwctl, 0, sizeof(pwctl));
@@ -477,7 +477,7 @@ l2vpn_binding_ctl(pid_t pid)
} else
pwctl.local_label = NO_LABEL;
- LIST_FOREACH(me, &fn->downstream, entry)
+ RB_FOREACH(me, lde_map_head, &fn->downstream)
if (f->u.pwid.lsr_id.s_addr == me->nexthop->id.s_addr)
break;
diff --git a/ldpd/lde.c b/ldpd/lde.c
index 67ed982..a1309c6 100644
--- a/ldpd/lde.c
+++ b/ldpd/lde.c
@@ -45,12 +45,14 @@ static struct lde_nbr *lde_nbr_find(uint32_t);
static void lde_nbr_clear(void);
static void lde_nbr_addr_update(struct lde_nbr *,
struct lde_addr *, int);
+static __inline int lde_map_compare(struct lde_map *, struct lde_map *);
static void lde_map_free(void *);
static int lde_address_add(struct lde_nbr *, struct lde_addr *);
static int lde_address_del(struct lde_nbr *, struct lde_addr *);
static void lde_address_list_free(struct lde_nbr *);
RB_GENERATE(nbr_tree, lde_nbr, entry, lde_nbr_compare)
+RB_GENERATE(lde_map_head, lde_map, entry, lde_map_compare)
struct ldpd_conf *ldeconf;
struct nbr_tree lde_nbrs = RB_INITIALIZER(&lde_nbrs);
@@ -1141,6 +1143,13 @@ lde_nbr_addr_update(struct lde_nbr *ln, struct lde_addr *lde_addr, int removed)
}
}
+static __inline int
+lde_map_compare(struct lde_map *a, struct lde_map *b)
+{
+ return (ldp_addrcmp(AF_INET, (union ldpd_addr *)&a->nexthop->id,
+ (union ldpd_addr *)&b->nexthop->id));
+}
+
struct lde_map *
lde_map_add(struct lde_nbr *ln, struct fec_node *fn, int sent)
{
@@ -1154,13 +1163,15 @@ lde_map_add(struct lde_nbr *ln, struct fec_node *fn, int sent)
me->nexthop = ln;
if (sent) {
- LIST_INSERT_HEAD(&fn->upstream, me, entry);
+ RB_INSERT(lde_map_head, &fn->upstream, me);
+ me->head = &fn->upstream;
if (fec_insert(&ln->sent_map, &me->fec))
log_warnx("failed to add %s to sent map",
log_fec(&me->fec));
/* XXX on failure more cleanup is needed */
} else {
- LIST_INSERT_HEAD(&fn->downstream, me, entry);
+ RB_INSERT(lde_map_head, &fn->downstream, me);
+ me->head = &fn->downstream;
if (fec_insert(&ln->recv_map, &me->fec))
log_warnx("failed to add %s to recv map",
log_fec(&me->fec));
@@ -1185,7 +1196,7 @@ lde_map_free(void *ptr)
{
struct lde_map *map = ptr;
- LIST_REMOVE(map, entry);
+ RB_REMOVE(lde_map_head, map->head, map);
free(map);
}
diff --git a/ldpd/lde.h b/ldpd/lde.h
index 5f5d37d..fe90b2c 100644
--- a/ldpd/lde.h
+++ b/ldpd/lde.h
@@ -62,10 +62,13 @@ struct lde_req {
/* mapping entries */
struct lde_map {
struct fec fec;
- LIST_ENTRY(lde_map) entry;
+ struct lde_map_head *head; /* fec_node's upstream/downstream */
+ RB_ENTRY(lde_map) entry;
struct lde_nbr *nexthop;
struct map map;
};
+RB_HEAD(lde_map_head, lde_map);
+RB_PROTOTYPE(lde_map_head, lde_map, entry, lde_map_cmp);
/* withdraw entries */
struct lde_wdraw {
@@ -112,8 +115,8 @@ struct fec_node {
struct fec fec;
LIST_HEAD(, fec_nh) nexthops; /* fib nexthops */
- LIST_HEAD(, lde_map) downstream; /* recv mappings */
- LIST_HEAD(, lde_map) upstream; /* sent mappings */
+ struct lde_map_head downstream; /* recv mappings */
+ struct lde_map_head upstream; /* sent mappings */
uint32_t local_label;
void *data; /* fec specific data */
diff --git a/ldpd/lde_lib.c b/ldpd/lde_lib.c
index 14ac592..df65eda 100644
--- a/ldpd/lde_lib.c
+++ b/ldpd/lde_lib.c
@@ -159,7 +159,7 @@ rt_dump(pid_t pid)
RB_FOREACH(f, fec_tree, &ft) {
fn = (struct fec_node *)f;
if (fn->local_label == NO_LABEL &&
- LIST_EMPTY(&fn->downstream))
+ RB_EMPTY(&fn->downstream))
continue;
rtctl.first = 1;
@@ -179,7 +179,7 @@ rt_dump(pid_t pid)
}
rtctl.local_label = fn->local_label;
- LIST_FOREACH(me, &fn->downstream, entry) {
+ RB_FOREACH(me, lde_map_head, &fn->downstream) {
rtctl.in_use = lde_nbr_is_nexthop(fn, me->nexthop);
rtctl.nexthop = me->nexthop->id;
rtctl.remote_label = me->map.label;
@@ -188,7 +188,7 @@ rt_dump(pid_t pid)
&rtctl, sizeof(rtctl));
rtctl.first = 0;
}
- if (LIST_EMPTY(&fn->downstream)) {
+ if (RB_EMPTY(&fn->downstream)) {
rtctl.in_use = 0;
rtctl.nexthop.s_addr = INADDR_ANY;
rtctl.remote_label = NO_LABEL;
@@ -224,10 +224,10 @@ fec_free(void *arg)
while ((fnh = LIST_FIRST(&fn->nexthops)))
fec_nh_del(fnh);
- if (!LIST_EMPTY(&fn->downstream))
+ if (!RB_EMPTY(&fn->downstream))
log_warnx("%s: fec %s downstream list not empty", __func__,
log_fec(&fn->fec));
- if (!LIST_EMPTY(&fn->upstream))
+ if (!RB_EMPTY(&fn->upstream))
log_warnx("%s: fec %s upstream list not empty", __func__,
log_fec(&fn->fec));
@@ -251,8 +251,8 @@ fec_add(struct fec *fec)
fn->fec = *fec;
fn->local_label = NO_LABEL;
- LIST_INIT(&fn->upstream);
- LIST_INIT(&fn->downstream);
+ RB_INIT(&fn->upstream);
+ RB_INIT(&fn->downstream);
LIST_INIT(&fn->nexthops);
if (fec_insert(&ft, &fn->fec))
@@ -774,8 +774,8 @@ lde_gc_timer(struct thread *thread)
fn = (struct fec_node *) fec;
if (!LIST_EMPTY(&fn->nexthops) ||
- !LIST_EMPTY(&fn->downstream) ||
- !LIST_EMPTY(&fn->upstream))
+ !RB_EMPTY(&fn->downstream) ||
+ !RB_EMPTY(&fn->upstream))
continue;
fec_remove(&ft, &fn->fec);
--
1.9.1
More information about the dev
mailing list