[cmaster-next] [PATCH 00/10] Issue #12
Hi all, This patchset makes ldpd display everything in order on CLI output (interfaces, label bindings, etc). This is important to keep consistent with the other routing daemons and to make automated testing easier (CLI output should be predictable and not dependant on the order that things were created). To do this, I converted several linked lists to red-black trees, which store elements in order. I could also use ordered lists, but they have worse time-complexities than red-black trees for basically everything. Fixes issue #12 and addresses a long standing request from Martin. Renato Westphal (10): ldpd: fix segfault when configuring multiple pseudowires ldpd: allow multiple link adjacencies with unnumbered interfaces ldpd: use red-black trees to store 'lde_map' elements ldpd: use red-black trees to store 'iface' elements ldpd: use red-black trees to store 'tnbr' elements ldpd: use red-black trees to store 'nbr_params' elements ldpd: use red-black trees to store 'l2vpn' elements ldpd: use red-black trees to store 'l2vpn_if' elements ldpd: use red-black trees to store 'l2vpn_pw' elements ldpd: use red-black trees to store 'adj' elements ldpd/adjacency.c | 116 +++++++++++++++++----------- ldpd/hello.c | 6 +- ldpd/interface.c | 45 ++++++----- ldpd/l2vpn.c | 108 ++++++++++++++------------ ldpd/lde.c | 49 +++++++----- ldpd/lde.h | 9 ++- ldpd/lde_lib.c | 18 ++--- ldpd/ldp_debug.c | 4 +- ldpd/ldp_vty_conf.c | 104 +++++++++++++------------- ldpd/ldpd.c | 212 ++++++++++++++++++++++++++-------------------------- ldpd/ldpd.h | 72 +++++++++++------- ldpd/ldpe.c | 56 +++++++------- ldpd/ldpe.h | 14 ++-- ldpd/neighbor.c | 29 ++++--- 14 files changed, 468 insertions(+), 374 deletions(-) -- 1.9.1
Signed-off-by: Renato Westphal <renato@opensourcerouting.org> --- ldpd/ldp_vty_conf.c | 16 ++++++++-------- 1 file changed, 8 insertions(+), 8 deletions(-) diff --git a/ldpd/ldp_vty_conf.c b/ldpd/ldp_vty_conf.c index f2b21d8..dd70365 100644 --- a/ldpd/ldp_vty_conf.c +++ b/ldpd/ldp_vty_conf.c @@ -1250,7 +1250,7 @@ ldp_vty_l2vpn(struct vty *vty, struct vty_arg *args[]) l2vpn->type = L2VPN_TYPE_VPLS; LIST_INSERT_HEAD(&vty_conf->l2vpn_list, l2vpn, entry); - ldp_reload(vty_conf); + ldp_reload_ref(vty_conf, (void **)&l2vpn); VTY_PUSH_CONTEXT(LDP_L2VPN_NODE, l2vpn); return (CMD_SUCCESS); @@ -1432,7 +1432,7 @@ ldp_vty_l2vpn_pseudowire(struct vty *vty, struct vty_arg *args[]) } if (pw) { - VTY_PUSH_CONTEXT(LDP_PSEUDOWIRE_NODE, pw); + VTY_PUSH_CONTEXT_SUB(LDP_PSEUDOWIRE_NODE, pw); goto cancel; } @@ -1454,7 +1454,7 @@ ldp_vty_l2vpn_pseudowire(struct vty *vty, struct vty_arg *args[]) LIST_INSERT_HEAD(&l2vpn->pw_inactive_list, pw, entry); ldp_reload_ref(vty_conf, (void **)&pw); - VTY_PUSH_CONTEXT(LDP_PSEUDOWIRE_NODE, pw); + VTY_PUSH_CONTEXT_SUB(LDP_PSEUDOWIRE_NODE, pw); return (CMD_SUCCESS); @@ -1474,7 +1474,7 @@ ldp_vty_l2vpn_pw_cword(struct vty *vty, struct vty_arg *args[]) disable = (vty_get_arg_value(args, "no")) ? 1 : 0; preference_str = vty_get_arg_value(args, "preference"); - pw = VTY_GET_CONTEXT(l2vpn_pw); + pw = VTY_GET_CONTEXT_SUB(l2vpn_pw); vty_conf = ldp_dup_config_ref(ldpd_conf, (void **)&pw); if (disable) @@ -1510,7 +1510,7 @@ ldp_vty_l2vpn_pw_nbr_addr(struct vty *vty, struct vty_arg *args[]) return (CMD_WARNING); } - pw = VTY_GET_CONTEXT(l2vpn_pw); + pw = VTY_GET_CONTEXT_SUB(l2vpn_pw); vty_conf = ldp_dup_config_ref(ldpd_conf, (void **)&pw); if (disable) { @@ -1546,7 +1546,7 @@ ldp_vty_l2vpn_pw_nbr_id(struct vty *vty, struct vty_arg *args[]) return (CMD_WARNING); } - pw = VTY_GET_CONTEXT(l2vpn_pw); + pw = VTY_GET_CONTEXT_SUB(l2vpn_pw); vty_conf = ldp_dup_config_ref(ldpd_conf, (void **)&pw); if (disable) @@ -1578,7 +1578,7 @@ ldp_vty_l2vpn_pw_pwid(struct vty *vty, struct vty_arg *args[]) return (CMD_WARNING); } - pw = VTY_GET_CONTEXT(l2vpn_pw); + pw = VTY_GET_CONTEXT_SUB(l2vpn_pw); vty_conf = ldp_dup_config_ref(ldpd_conf, (void **)&pw); if (disable) @@ -1600,7 +1600,7 @@ ldp_vty_l2vpn_pw_pwstatus(struct vty *vty, struct vty_arg *args[]) disable = (vty_get_arg_value(args, "no")) ? 1 : 0; - pw = VTY_GET_CONTEXT(l2vpn_pw); + pw = VTY_GET_CONTEXT_SUB(l2vpn_pw); vty_conf = ldp_dup_config_ref(ldpd_conf, (void **)&pw); if (disable) -- 1.9.1
Now we can have two different adjacencies coming from the same source address. Check for the adjacency's interface on adj_find() to disambiguate them. Signed-off-by: Renato Westphal <renato@opensourcerouting.org> --- ldpd/adjacency.c | 4 ++++ 1 file changed, 4 insertions(+) diff --git a/ldpd/adjacency.c b/ldpd/adjacency.c index 3607ee9..d1a6fac 100644 --- a/ldpd/adjacency.c +++ b/ldpd/adjacency.c @@ -117,6 +117,10 @@ adj_find(struct hello_source *source) 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) -- 1.9.1
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@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
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@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
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@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
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@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
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@opensourcerouting.org> --- ldpd/l2vpn.c | 25 +++++++++++++++---------- ldpd/lde.c | 4 ++-- ldpd/ldp_vty_conf.c | 14 +++++++------- ldpd/ldpd.c | 28 ++++++++++++++-------------- ldpd/ldpd.h | 11 +++++++---- ldpd/ldpe.c | 4 ++-- 6 files changed, 47 insertions(+), 39 deletions(-) diff --git a/ldpd/l2vpn.c b/ldpd/l2vpn.c index dc9879e..b339c9c 100644 --- a/ldpd/l2vpn.c +++ b/ldpd/l2vpn.c @@ -26,7 +26,16 @@ #include "lde.h" #include "log.h" -static void l2vpn_pw_fec(struct l2vpn_pw *, struct fec *); +static void l2vpn_pw_fec(struct l2vpn_pw *, struct fec *); +static __inline int l2vpn_compare(struct l2vpn *, struct l2vpn *); + +RB_GENERATE(l2vpn_head, l2vpn, entry, l2vpn_compare) + +static __inline int +l2vpn_compare(struct l2vpn *a, struct l2vpn *b) +{ + return (strcmp(a->name, b->name)); +} struct l2vpn * l2vpn_new(const char *name) @@ -52,13 +61,9 @@ l2vpn_new(const char *name) struct l2vpn * l2vpn_find(struct ldpd_conf *xconf, const char *name) { - struct l2vpn *l2vpn; - - LIST_FOREACH(l2vpn, &xconf->l2vpn_list, entry) - if (strcmp(l2vpn->name, name) == 0) - return (l2vpn); - - return (NULL); + struct l2vpn l2vpn; + strlcpy(l2vpn.name, name, sizeof(l2vpn.name)); + return (RB_FIND(l2vpn_head, &xconf->l2vpn_tree, &l2vpn)); } void @@ -399,7 +404,7 @@ l2vpn_sync_pws(int af, union ldpd_addr *addr) struct fec_node *fn; struct fec_nh *fnh; - LIST_FOREACH(l2vpn, &ldeconf->l2vpn_list, entry) { + RB_FOREACH(l2vpn, l2vpn_head, &ldeconf->l2vpn_tree) { LIST_FOREACH(pw, &l2vpn->pw_list, entry) { if (af != pw->af || ldp_addrcmp(af, &pw->addr, addr)) continue; @@ -428,7 +433,7 @@ l2vpn_pw_ctl(pid_t pid) struct l2vpn_pw *pw; static struct ctl_pw pwctl; - LIST_FOREACH(l2vpn, &ldeconf->l2vpn_list, entry) + RB_FOREACH(l2vpn, l2vpn_head, &ldeconf->l2vpn_tree) LIST_FOREACH(pw, &l2vpn->pw_list, entry) { memset(&pwctl, 0, sizeof(pwctl)); strlcpy(pwctl.l2vpn_name, pw->l2vpn->name, diff --git a/ldpd/lde.c b/ldpd/lde.c index 80557ed..3feb27d 100644 --- a/ldpd/lde.c +++ b/ldpd/lde.c @@ -476,7 +476,7 @@ lde_dispatch_parent(struct thread *thread) RB_INIT(&nconf->iface_tree); RB_INIT(&nconf->tnbr_tree); RB_INIT(&nconf->nbrp_tree); - LIST_INIT(&nconf->l2vpn_list); + RB_INIT(&nconf->l2vpn_tree); break; case IMSG_RECONF_IFACE: if ((niface = malloc(sizeof(struct iface))) == NULL) @@ -514,7 +514,7 @@ lde_dispatch_parent(struct thread *thread) LIST_INIT(&nl2vpn->pw_list); LIST_INIT(&nl2vpn->pw_inactive_list); - LIST_INSERT_HEAD(&nconf->l2vpn_list, nl2vpn, entry); + RB_INSERT(l2vpn_head, &nconf->l2vpn_tree, nl2vpn); break; case IMSG_RECONF_L2VPN_IF: if ((nlif = malloc(sizeof(struct l2vpn_if))) == NULL) diff --git a/ldpd/ldp_vty_conf.c b/ldpd/ldp_vty_conf.c index 95b0971..b66d8d4 100644 --- a/ldpd/ldp_vty_conf.c +++ b/ldpd/ldp_vty_conf.c @@ -341,7 +341,7 @@ ldp_l2vpn_config_write(struct vty *vty) struct l2vpn_if *lif; struct l2vpn_pw *pw; - LIST_FOREACH(l2vpn, &ldpd_conf->l2vpn_list, entry) { + RB_FOREACH(l2vpn, l2vpn_head, &ldpd_conf->l2vpn_tree) { vty_out(vty, "l2vpn %s type vpls%s", l2vpn->name, VTY_NEWLINE); if (l2vpn->pw_type != DEFAULT_PW_TYPE) @@ -393,7 +393,7 @@ ldp_iface_is_configured(struct ldpd_conf *xconf, const char *ifname) if (if_lookup_name(xconf, ifname)) return (1); - LIST_FOREACH(l2vpn, &xconf->l2vpn_list, entry) { + RB_FOREACH(l2vpn, l2vpn_head, &xconf->l2vpn_tree) { if (l2vpn_if_find_name(l2vpn, ifname)) return (1); if (l2vpn_pw_find_name(l2vpn, ifname)) @@ -1235,7 +1235,7 @@ ldp_vty_l2vpn(struct vty *vty, struct vty_arg *args[]) if (l2vpn == NULL) goto cancel; - LIST_REMOVE(l2vpn, entry); + RB_REMOVE(l2vpn_head, &vty_conf->l2vpn_tree, l2vpn); l2vpn_del(l2vpn); ldp_reload(vty_conf); return (CMD_SUCCESS); @@ -1248,7 +1248,7 @@ ldp_vty_l2vpn(struct vty *vty, struct vty_arg *args[]) l2vpn = l2vpn_new(name_str); l2vpn->type = L2VPN_TYPE_VPLS; - LIST_INSERT_HEAD(&vty_conf->l2vpn_list, l2vpn, entry); + RB_INSERT(l2vpn_head, &vty_conf->l2vpn_tree, l2vpn); ldp_reload_ref(vty_conf, (void **)&l2vpn); VTY_PUSH_CONTEXT(LDP_L2VPN_NODE, l2vpn); @@ -1706,12 +1706,12 @@ l2vpn_new_api(struct ldpd_conf *conf, const char *name) l2vpn = l2vpn_new(name); l2vpn->type = L2VPN_TYPE_VPLS; - LIST_INSERT_HEAD(&conf->l2vpn_list, l2vpn, entry); + RB_INSERT(l2vpn_head, &conf->l2vpn_tree, l2vpn); return (l2vpn); } void -l2vpn_del_api(struct l2vpn *l2vpn) +l2vpn_del_api(struct ldpd_conf *conf, struct l2vpn *l2vpn) { struct l2vpn_if *lif; struct l2vpn_pw *pw; @@ -1728,7 +1728,7 @@ l2vpn_del_api(struct l2vpn *l2vpn) LIST_REMOVE(pw, entry); free(pw); } - LIST_REMOVE(l2vpn, entry); + RB_REMOVE(l2vpn_head, &conf->l2vpn_tree, l2vpn); free(l2vpn); } diff --git a/ldpd/ldpd.c b/ldpd/ldpd.c index 37cc0de..dab761d 100644 --- a/ldpd/ldpd.c +++ b/ldpd/ldpd.c @@ -868,7 +868,7 @@ main_imsg_send_config(struct ldpd_conf *xconf) return (-1); } - LIST_FOREACH(l2vpn, &xconf->l2vpn_list, entry) { + RB_FOREACH(l2vpn, l2vpn_head, &xconf->l2vpn_tree) { if (main_imsg_compose_both(IMSG_RECONF_L2VPN, l2vpn, sizeof(*l2vpn)) == -1) return (-1); @@ -930,7 +930,7 @@ ldp_config_normalize(struct ldpd_conf *xconf, void **ref) ldp_config_reset_af(xconf, AF_INET6, ref); } - LIST_FOREACH(l2vpn, &xconf->l2vpn_list, entry) { + RB_FOREACH(l2vpn, l2vpn_head, &xconf->l2vpn_tree) { LIST_FOREACH(pw, &l2vpn->pw_list, entry) { if (pw->flags & F_PW_STATIC_NBR_ADDR) continue; @@ -1035,7 +1035,7 @@ ldp_dup_config_ref(struct ldpd_conf *conf, void **ref) RB_INIT(&xconf->iface_tree); RB_INIT(&xconf->tnbr_tree); RB_INIT(&xconf->nbrp_tree); - LIST_INIT(&xconf->l2vpn_list); + RB_INIT(&xconf->l2vpn_tree); RB_FOREACH(iface, iface_head, &conf->iface_tree) { COPY(xi, iface); @@ -1051,12 +1051,12 @@ ldp_dup_config_ref(struct ldpd_conf *conf, void **ref) COPY(xn, nbrp); RB_INSERT(nbrp_head, &xconf->nbrp_tree, xn); } - LIST_FOREACH(l2vpn, &conf->l2vpn_list, entry) { + RB_FOREACH(l2vpn, l2vpn_head, &conf->l2vpn_tree) { COPY(xl, l2vpn); LIST_INIT(&xl->if_list); LIST_INIT(&xl->pw_list); LIST_INIT(&xl->pw_inactive_list); - LIST_INSERT_HEAD(&xconf->l2vpn_list, xl, entry); + RB_INSERT(l2vpn_head, &xconf->l2vpn_tree, xl); LIST_FOREACH(lif, &l2vpn->if_list, entry) { COPY(xf, lif); @@ -1105,8 +1105,8 @@ ldp_clear_config(struct ldpd_conf *xconf) RB_REMOVE(nbrp_head, &xconf->nbrp_tree, nbrp); free(nbrp); } - while ((l2vpn = LIST_FIRST(&xconf->l2vpn_list)) != NULL) { - LIST_REMOVE(l2vpn, entry); + while ((l2vpn = RB_ROOT(&xconf->l2vpn_tree)) != NULL) { + RB_REMOVE(l2vpn_head, &xconf->l2vpn_tree, l2vpn); l2vpn_del(l2vpn); } @@ -1469,10 +1469,10 @@ merge_l2vpns(struct ldpd_conf *conf, struct ldpd_conf *xconf, void **ref) struct l2vpn_if *lif; struct l2vpn_pw *pw; - LIST_FOREACH_SAFE(l2vpn, &conf->l2vpn_list, entry, ltmp) { + RB_FOREACH_SAFE(l2vpn, l2vpn_head, &conf->l2vpn_tree, ltmp) { /* find deleted l2vpns */ if ((xl = l2vpn_find(xconf, l2vpn->name)) == NULL) { - LIST_REMOVE(l2vpn, entry); + RB_REMOVE(l2vpn_head, &conf->l2vpn_tree, l2vpn); switch (ldpd_process) { case PROC_LDE_ENGINE: @@ -1494,11 +1494,11 @@ merge_l2vpns(struct ldpd_conf *conf, struct ldpd_conf *xconf, void **ref) l2vpn_del(l2vpn); } } - LIST_FOREACH_SAFE(xl, &xconf->l2vpn_list, entry, ltmp) { + RB_FOREACH_SAFE(xl, l2vpn_head, &xconf->l2vpn_tree, ltmp) { /* find new l2vpns */ if ((l2vpn = l2vpn_find(conf, xl->name)) == NULL) { - LIST_REMOVE(xl, entry); - LIST_INSERT_HEAD(&conf->l2vpn_list, xl, entry); + RB_REMOVE(l2vpn_head, &xconf->l2vpn_tree, xl); + RB_INSERT(l2vpn_head, &conf->l2vpn_tree, xl); switch (ldpd_process) { case PROC_LDE_ENGINE: @@ -1516,7 +1516,7 @@ merge_l2vpns(struct ldpd_conf *conf, struct ldpd_conf *xconf, void **ref) /* update existing l2vpns */ merge_l2vpn(conf, l2vpn, xl, ref); - LIST_REMOVE(xl, entry); + RB_REMOVE(l2vpn_head, &xconf->l2vpn_tree, xl); if (ref && *ref == xl) *ref = l2vpn; free(xl); @@ -1773,7 +1773,7 @@ config_new_empty(void) RB_INIT(&xconf->iface_tree); RB_INIT(&xconf->tnbr_tree); RB_INIT(&xconf->nbrp_tree); - LIST_INIT(&xconf->l2vpn_list); + RB_INIT(&xconf->l2vpn_tree); return (xconf); } diff --git a/ldpd/ldpd.h b/ldpd/ldpd.h index d8f75a0..72e5dc5 100644 --- a/ldpd/ldpd.h +++ b/ldpd/ldpd.h @@ -358,7 +358,7 @@ DECLARE_QOBJ_TYPE(l2vpn_pw) #define F_PW_STATIC_NBR_ADDR 0x20 /* static neighbor address configured */ struct l2vpn { - LIST_ENTRY(l2vpn) entry; + RB_ENTRY(l2vpn) entry; char name[L2VPN_NAME_LEN]; int type; int pw_type; @@ -370,6 +370,8 @@ struct l2vpn { LIST_HEAD(, l2vpn_pw) pw_inactive_list; QOBJ_FIELDS }; +RB_HEAD(l2vpn_head, l2vpn); +RB_PROTOTYPE(l2vpn_head, l2vpn, entry, l2vpn_compare); DECLARE_QOBJ_TYPE(l2vpn) #define L2VPN_TYPE_VPWS 1 #define L2VPN_TYPE_VPLS 2 @@ -413,7 +415,7 @@ struct ldpd_conf { struct iface_head iface_tree; struct tnbr_head tnbr_tree; struct nbrp_head nbrp_tree; - LIST_HEAD(, l2vpn) l2vpn_list; + struct l2vpn_head l2vpn_tree; uint16_t lhello_holdtime; uint16_t lhello_interval; uint16_t thello_holdtime; @@ -644,8 +646,9 @@ struct nbr_params *nbrp_new_api(struct ldpd_conf *conf, struct in_addr lsr_id); 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 *l2vpn_new_api(struct ldpd_conf *conf, const char *name); +void l2vpn_del_api(struct ldpd_conf *conf, + struct l2vpn *l2vpn); struct l2vpn_if *l2vpn_if_new_api(struct ldpd_conf *conf, struct l2vpn *l2vpn, const char *ifname); void l2vpn_if_del_api(struct l2vpn_if *lif); diff --git a/ldpd/ldpe.c b/ldpd/ldpe.c index e9e45f8..6edd180 100644 --- a/ldpd/ldpe.c +++ b/ldpd/ldpe.c @@ -417,7 +417,7 @@ ldpe_dispatch_main(struct thread *thread) RB_INIT(&nconf->iface_tree); RB_INIT(&nconf->tnbr_tree); RB_INIT(&nconf->nbrp_tree); - LIST_INIT(&nconf->l2vpn_list); + RB_INIT(&nconf->l2vpn_tree); break; case IMSG_RECONF_IFACE: if ((niface = malloc(sizeof(struct iface))) == NULL) @@ -455,7 +455,7 @@ ldpe_dispatch_main(struct thread *thread) LIST_INIT(&nl2vpn->pw_list); LIST_INIT(&nl2vpn->pw_inactive_list); - LIST_INSERT_HEAD(&nconf->l2vpn_list, nl2vpn, entry); + RB_INSERT(l2vpn_head, &nconf->l2vpn_tree, nl2vpn); break; case IMSG_RECONF_L2VPN_IF: if ((nlif = malloc(sizeof(struct l2vpn_if))) == NULL) -- 1.9.1
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@opensourcerouting.org> --- ldpd/l2vpn.c | 26 +++++++++++++++----------- ldpd/lde.c | 4 ++-- ldpd/ldp_vty_conf.c | 16 ++++++++-------- ldpd/ldpd.c | 22 +++++++++++----------- ldpd/ldpd.h | 9 ++++++--- ldpd/ldpe.c | 4 ++-- 6 files changed, 44 insertions(+), 37 deletions(-) diff --git a/ldpd/l2vpn.c b/ldpd/l2vpn.c index b339c9c..02f25e1 100644 --- a/ldpd/l2vpn.c +++ b/ldpd/l2vpn.c @@ -28,8 +28,10 @@ static void l2vpn_pw_fec(struct l2vpn_pw *, struct fec *); static __inline int l2vpn_compare(struct l2vpn *, struct l2vpn *); +static __inline int l2vpn_if_compare(struct l2vpn_if *, struct l2vpn_if *); RB_GENERATE(l2vpn_head, l2vpn, entry, l2vpn_compare) +RB_GENERATE(l2vpn_if_head, l2vpn_if, entry, l2vpn_if_compare) static __inline int l2vpn_compare(struct l2vpn *a, struct l2vpn *b) @@ -51,7 +53,7 @@ l2vpn_new(const char *name) l2vpn->mtu = DEFAULT_L2VPN_MTU; l2vpn->pw_type = DEFAULT_PW_TYPE; - LIST_INIT(&l2vpn->if_list); + RB_INIT(&l2vpn->if_tree); LIST_INIT(&l2vpn->pw_list); LIST_INIT(&l2vpn->pw_inactive_list); @@ -72,8 +74,8 @@ l2vpn_del(struct l2vpn *l2vpn) struct l2vpn_if *lif; struct l2vpn_pw *pw; - while ((lif = LIST_FIRST(&l2vpn->if_list)) != NULL) { - LIST_REMOVE(lif, entry); + while ((lif = RB_ROOT(&l2vpn->if_tree)) != NULL) { + RB_REMOVE(l2vpn_if_head, &l2vpn->if_tree, lif); free(lif); } while ((pw = LIST_FIRST(&l2vpn->pw_list)) != NULL) { @@ -106,6 +108,12 @@ l2vpn_exit(struct l2vpn *l2vpn) l2vpn_pw_exit(pw); } +static __inline int +l2vpn_if_compare(struct l2vpn_if *a, struct l2vpn_if *b) +{ + return (strcmp(a->ifname, b->ifname)); +} + struct l2vpn_if * l2vpn_if_new(struct l2vpn *l2vpn, struct kif *kif) { @@ -127,7 +135,7 @@ l2vpn_if_find(struct l2vpn *l2vpn, unsigned int ifindex) { struct l2vpn_if *lif; - LIST_FOREACH(lif, &l2vpn->if_list, entry) + RB_FOREACH(lif, l2vpn_if_head, &l2vpn->if_tree) if (lif->ifindex == ifindex) return (lif); @@ -137,13 +145,9 @@ l2vpn_if_find(struct l2vpn *l2vpn, unsigned int ifindex) struct l2vpn_if * l2vpn_if_find_name(struct l2vpn *l2vpn, const char *ifname) { - struct l2vpn_if *lif; - - LIST_FOREACH(lif, &l2vpn->if_list, entry) - if (strcmp(lif->ifname, ifname) == 0) - return (lif); - - return (NULL); + struct l2vpn_if lif; + strlcpy(lif.ifname, ifname, sizeof(lif.ifname)); + return (RB_FIND(l2vpn_if_head, &l2vpn->if_tree, &lif)); } diff --git a/ldpd/lde.c b/ldpd/lde.c index 3feb27d..522650c 100644 --- a/ldpd/lde.c +++ b/ldpd/lde.c @@ -510,7 +510,7 @@ lde_dispatch_parent(struct thread *thread) fatal(NULL); memcpy(nl2vpn, imsg.data, sizeof(struct l2vpn)); - LIST_INIT(&nl2vpn->if_list); + RB_INIT(&nl2vpn->if_tree); LIST_INIT(&nl2vpn->pw_list); LIST_INIT(&nl2vpn->pw_inactive_list); @@ -522,7 +522,7 @@ lde_dispatch_parent(struct thread *thread) memcpy(nlif, imsg.data, sizeof(struct l2vpn_if)); nlif->l2vpn = nl2vpn; - LIST_INSERT_HEAD(&nl2vpn->if_list, nlif, entry); + RB_INSERT(l2vpn_if_head, &nl2vpn->if_tree, nlif); break; case IMSG_RECONF_L2VPN_PW: if ((npw = malloc(sizeof(struct l2vpn_pw))) == NULL) diff --git a/ldpd/ldp_vty_conf.c b/ldpd/ldp_vty_conf.c index b66d8d4..b979642 100644 --- a/ldpd/ldp_vty_conf.c +++ b/ldpd/ldp_vty_conf.c @@ -354,7 +354,7 @@ ldp_l2vpn_config_write(struct vty *vty) vty_out(vty, " bridge %s%s", l2vpn->br_ifname, VTY_NEWLINE); - LIST_FOREACH(lif, &l2vpn->if_list, entry) + RB_FOREACH(lif, l2vpn_if_head, &l2vpn->if_tree) vty_out(vty, " member interface %s%s", lif->ifname, VTY_NEWLINE); @@ -1369,7 +1369,7 @@ ldp_vty_l2vpn_interface(struct vty *vty, struct vty_arg *args[]) if (lif == NULL) goto cancel; - LIST_REMOVE(lif, entry); + RB_REMOVE(l2vpn_if_head, &l2vpn->if_tree, lif); free(lif); ldp_reload(vty_conf); return (CMD_SUCCESS); @@ -1392,7 +1392,7 @@ ldp_vty_l2vpn_interface(struct vty *vty, struct vty_arg *args[]) } lif = l2vpn_if_new(l2vpn, &kif); - LIST_INSERT_HEAD(&l2vpn->if_list, lif, entry); + RB_INSERT(l2vpn_if_head, &l2vpn->if_tree, lif); ldp_reload_ref(vty_conf, (void **)&l2vpn); @@ -1716,8 +1716,8 @@ l2vpn_del_api(struct ldpd_conf *conf, struct l2vpn *l2vpn) struct l2vpn_if *lif; struct l2vpn_pw *pw; - while ((lif = LIST_FIRST(&l2vpn->if_list)) != NULL) { - LIST_REMOVE(lif, entry); + while ((lif = RB_ROOT(&l2vpn->if_tree)) != NULL) { + RB_REMOVE(l2vpn_if_head, &l2vpn->if_tree, lif); free(lif); } while ((pw = LIST_FIRST(&l2vpn->pw_list)) != NULL) { @@ -1752,14 +1752,14 @@ l2vpn_if_new_api(struct ldpd_conf *conf, struct l2vpn *l2vpn, } lif = l2vpn_if_new(l2vpn, &kif); - LIST_INSERT_HEAD(&l2vpn->if_list, lif, entry); + RB_INSERT(l2vpn_if_head, &l2vpn->if_tree, lif); return (lif); } void -l2vpn_if_del_api(struct l2vpn_if *lif) +l2vpn_if_del_api(struct l2vpn *l2vpn, struct l2vpn_if *lif) { - LIST_REMOVE(lif, entry); + RB_REMOVE(l2vpn_if_head, &l2vpn->if_tree, lif); free(lif); } diff --git a/ldpd/ldpd.c b/ldpd/ldpd.c index dab761d..0df9bbd 100644 --- a/ldpd/ldpd.c +++ b/ldpd/ldpd.c @@ -873,7 +873,7 @@ main_imsg_send_config(struct ldpd_conf *xconf) sizeof(*l2vpn)) == -1) return (-1); - LIST_FOREACH(lif, &l2vpn->if_list, entry) { + RB_FOREACH(lif, l2vpn_if_head, &l2vpn->if_tree) { if (main_imsg_compose_both(IMSG_RECONF_L2VPN_IF, lif, sizeof(*lif)) == -1) return (-1); @@ -1053,15 +1053,15 @@ ldp_dup_config_ref(struct ldpd_conf *conf, void **ref) } RB_FOREACH(l2vpn, l2vpn_head, &conf->l2vpn_tree) { COPY(xl, l2vpn); - LIST_INIT(&xl->if_list); + RB_INIT(&xl->if_tree); LIST_INIT(&xl->pw_list); LIST_INIT(&xl->pw_inactive_list); RB_INSERT(l2vpn_head, &xconf->l2vpn_tree, xl); - LIST_FOREACH(lif, &l2vpn->if_list, entry) { + RB_FOREACH(lif, l2vpn_if_head, &l2vpn->if_tree) { COPY(xf, lif); xf->l2vpn = xl; - LIST_INSERT_HEAD(&xl->if_list, xf, entry); + RB_INSERT(l2vpn_if_head, &xl->if_tree, xf); } LIST_FOREACH(pw, &l2vpn->pw_list, entry) { COPY(xp, pw); @@ -1482,7 +1482,7 @@ merge_l2vpns(struct ldpd_conf *conf, struct ldpd_conf *xconf, void **ref) ldpe_l2vpn_exit(l2vpn); break; case PROC_MAIN: - LIST_FOREACH(lif, &l2vpn->if_list, entry) + RB_FOREACH(lif, l2vpn_if_head, &l2vpn->if_tree) QOBJ_UNREG (lif); LIST_FOREACH(pw, &l2vpn->pw_list, entry) QOBJ_UNREG (pw); @@ -1537,27 +1537,27 @@ merge_l2vpn(struct ldpd_conf *xconf, struct l2vpn *l2vpn, struct l2vpn *xl, void previous_mtu = l2vpn->mtu; /* merge intefaces */ - LIST_FOREACH_SAFE(lif, &l2vpn->if_list, entry, ftmp) { + RB_FOREACH_SAFE(lif, l2vpn_if_head, &l2vpn->if_tree, ftmp) { /* find deleted interfaces */ if ((xf = l2vpn_if_find_name(xl, lif->ifname)) == NULL) { if (ldpd_process == PROC_MAIN) QOBJ_UNREG (lif); - LIST_REMOVE(lif, entry); + RB_REMOVE(l2vpn_if_head, &l2vpn->if_tree, lif); free(lif); } } - LIST_FOREACH_SAFE(xf, &xl->if_list, entry, ftmp) { + RB_FOREACH_SAFE(xf, l2vpn_if_head, &xl->if_tree, ftmp) { /* find new interfaces */ if ((lif = l2vpn_if_find_name(l2vpn, xf->ifname)) == NULL) { - LIST_REMOVE(xf, entry); - LIST_INSERT_HEAD(&l2vpn->if_list, xf, entry); + RB_REMOVE(l2vpn_if_head, &xl->if_tree, xf); + RB_INSERT(l2vpn_if_head, &l2vpn->if_tree, xf); xf->l2vpn = l2vpn; if (ldpd_process == PROC_MAIN) QOBJ_REG (xf, l2vpn_if); continue; } - LIST_REMOVE(xf, entry); + RB_REMOVE(l2vpn_if_head, &xl->if_tree, xf); if (ref && *ref == xf) *ref = lif; free(xf); diff --git a/ldpd/ldpd.h b/ldpd/ldpd.h index 72e5dc5..0a21856 100644 --- a/ldpd/ldpd.h +++ b/ldpd/ldpd.h @@ -325,13 +325,15 @@ DECLARE_QOBJ_TYPE(nbr_params) #define F_NBRP_GTSM_HOPS 0x04 struct l2vpn_if { - LIST_ENTRY(l2vpn_if) entry; + RB_ENTRY(l2vpn_if) entry; struct l2vpn *l2vpn; char ifname[IF_NAMESIZE]; unsigned int ifindex; uint16_t flags; QOBJ_FIELDS }; +RB_HEAD(l2vpn_if_head, l2vpn_if); +RB_PROTOTYPE(l2vpn_if_head, l2vpn_if, entry, l2vpn_if_compare); DECLARE_QOBJ_TYPE(l2vpn_if) struct l2vpn_pw { @@ -365,7 +367,7 @@ struct l2vpn { int mtu; char br_ifname[IF_NAMESIZE]; unsigned int br_ifindex; - LIST_HEAD(, l2vpn_if) if_list; + struct l2vpn_if_head if_tree; LIST_HEAD(, l2vpn_pw) pw_list; LIST_HEAD(, l2vpn_pw) pw_inactive_list; QOBJ_FIELDS @@ -651,7 +653,8 @@ void l2vpn_del_api(struct ldpd_conf *conf, struct l2vpn *l2vpn); struct l2vpn_if *l2vpn_if_new_api(struct ldpd_conf *conf, struct l2vpn *l2vpn, const char *ifname); -void l2vpn_if_del_api(struct l2vpn_if *lif); +void l2vpn_if_del_api(struct l2vpn *l2vpn, + struct l2vpn_if *lif); struct l2vpn_pw *l2vpn_pw_new_api(struct ldpd_conf *conf, struct l2vpn *l2vpn, const char *ifname); void l2vpn_pw_del_api(struct l2vpn_pw *pw); diff --git a/ldpd/ldpe.c b/ldpd/ldpe.c index 6edd180..2a9fb4c 100644 --- a/ldpd/ldpe.c +++ b/ldpd/ldpe.c @@ -451,7 +451,7 @@ ldpe_dispatch_main(struct thread *thread) fatal(NULL); memcpy(nl2vpn, imsg.data, sizeof(struct l2vpn)); - LIST_INIT(&nl2vpn->if_list); + RB_INIT(&nl2vpn->if_tree); LIST_INIT(&nl2vpn->pw_list); LIST_INIT(&nl2vpn->pw_inactive_list); @@ -463,7 +463,7 @@ ldpe_dispatch_main(struct thread *thread) memcpy(nlif, imsg.data, sizeof(struct l2vpn_if)); nlif->l2vpn = nl2vpn; - LIST_INSERT_HEAD(&nl2vpn->if_list, nlif, entry); + RB_INSERT(l2vpn_if_head, &nl2vpn->if_tree, nlif); break; case IMSG_RECONF_L2VPN_PW: if ((npw = malloc(sizeof(struct l2vpn_pw))) == NULL) -- 1.9.1
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@opensourcerouting.org> --- ldpd/l2vpn.c | 49 +++++++++++++++++++++------------------ ldpd/lde.c | 8 +++---- ldpd/ldp_vty_conf.c | 22 +++++++++--------- ldpd/ldpd.c | 66 ++++++++++++++++++++++++++--------------------------- ldpd/ldpd.h | 11 +++++---- ldpd/ldpe.c | 8 +++---- 6 files changed, 86 insertions(+), 78 deletions(-) diff --git a/ldpd/l2vpn.c b/ldpd/l2vpn.c index 02f25e1..c1d0437 100644 --- a/ldpd/l2vpn.c +++ b/ldpd/l2vpn.c @@ -29,9 +29,11 @@ static void l2vpn_pw_fec(struct l2vpn_pw *, struct fec *); static __inline int l2vpn_compare(struct l2vpn *, struct l2vpn *); static __inline int l2vpn_if_compare(struct l2vpn_if *, struct l2vpn_if *); +static __inline int l2vpn_pw_compare(struct l2vpn_pw *, struct l2vpn_pw *); RB_GENERATE(l2vpn_head, l2vpn, entry, l2vpn_compare) RB_GENERATE(l2vpn_if_head, l2vpn_if, entry, l2vpn_if_compare) +RB_GENERATE(l2vpn_pw_head, l2vpn_pw, entry, l2vpn_pw_compare) static __inline int l2vpn_compare(struct l2vpn *a, struct l2vpn *b) @@ -54,8 +56,8 @@ l2vpn_new(const char *name) l2vpn->pw_type = DEFAULT_PW_TYPE; RB_INIT(&l2vpn->if_tree); - LIST_INIT(&l2vpn->pw_list); - LIST_INIT(&l2vpn->pw_inactive_list); + RB_INIT(&l2vpn->pw_tree); + RB_INIT(&l2vpn->pw_inactive_tree); return (l2vpn); } @@ -78,12 +80,12 @@ l2vpn_del(struct l2vpn *l2vpn) RB_REMOVE(l2vpn_if_head, &l2vpn->if_tree, lif); free(lif); } - while ((pw = LIST_FIRST(&l2vpn->pw_list)) != NULL) { - LIST_REMOVE(pw, entry); + while ((pw = RB_ROOT(&l2vpn->pw_tree)) != NULL) { + RB_REMOVE(l2vpn_pw_head, &l2vpn->pw_tree, pw); free(pw); } - while ((pw = LIST_FIRST(&l2vpn->pw_inactive_list)) != NULL) { - LIST_REMOVE(pw, entry); + while ((pw = RB_ROOT(&l2vpn->pw_inactive_tree)) != NULL) { + RB_REMOVE(l2vpn_pw_head, &l2vpn->pw_inactive_tree, pw); free(pw); } @@ -95,7 +97,7 @@ l2vpn_init(struct l2vpn *l2vpn) { struct l2vpn_pw *pw; - LIST_FOREACH(pw, &l2vpn->pw_list, entry) + RB_FOREACH(pw, l2vpn_pw_head, &l2vpn->pw_tree) l2vpn_pw_init(pw); } @@ -104,7 +106,7 @@ l2vpn_exit(struct l2vpn *l2vpn) { struct l2vpn_pw *pw; - LIST_FOREACH(pw, &l2vpn->pw_list, entry) + RB_FOREACH(pw, l2vpn_pw_head, &l2vpn->pw_tree) l2vpn_pw_exit(pw); } @@ -150,6 +152,11 @@ l2vpn_if_find_name(struct l2vpn *l2vpn, const char *ifname) return (RB_FIND(l2vpn_if_head, &l2vpn->if_tree, &lif)); } +static __inline int +l2vpn_pw_compare(struct l2vpn_pw *a, struct l2vpn_pw *b) +{ + return (strcmp(a->ifname, b->ifname)); +} struct l2vpn_pw * l2vpn_pw_new(struct l2vpn *l2vpn, struct kif *kif) @@ -171,10 +178,10 @@ l2vpn_pw_find(struct l2vpn *l2vpn, unsigned int ifindex) { struct l2vpn_pw *pw; - LIST_FOREACH(pw, &l2vpn->pw_list, entry) + RB_FOREACH(pw, l2vpn_pw_head, &l2vpn->pw_tree) if (pw->ifindex == ifindex) return (pw); - LIST_FOREACH(pw, &l2vpn->pw_inactive_list, entry) + RB_FOREACH(pw, l2vpn_pw_head, &l2vpn->pw_inactive_tree) if (pw->ifindex == ifindex) return (pw); @@ -185,15 +192,13 @@ struct l2vpn_pw * l2vpn_pw_find_name(struct l2vpn *l2vpn, const char *ifname) { struct l2vpn_pw *pw; + struct l2vpn_pw s; - LIST_FOREACH(pw, &l2vpn->pw_list, entry) - if (strcmp(pw->ifname, ifname) == 0) - return (pw); - LIST_FOREACH(pw, &l2vpn->pw_inactive_list, entry) - if (strcmp(pw->ifname, ifname) == 0) - return (pw); - - return (NULL); + strlcpy(s.ifname, ifname, sizeof(s.ifname)); + pw = RB_FIND(l2vpn_pw_head, &l2vpn->pw_tree, &s); + if (pw) + return (pw); + return (RB_FIND(l2vpn_pw_head, &l2vpn->pw_inactive_tree, &s)); } void @@ -409,7 +414,7 @@ l2vpn_sync_pws(int af, union ldpd_addr *addr) struct fec_nh *fnh; RB_FOREACH(l2vpn, l2vpn_head, &ldeconf->l2vpn_tree) { - LIST_FOREACH(pw, &l2vpn->pw_list, entry) { + RB_FOREACH(pw, l2vpn_pw_head, &l2vpn->pw_tree) { if (af != pw->af || ldp_addrcmp(af, &pw->addr, addr)) continue; @@ -438,7 +443,7 @@ l2vpn_pw_ctl(pid_t pid) static struct ctl_pw pwctl; RB_FOREACH(l2vpn, l2vpn_head, &ldeconf->l2vpn_tree) - LIST_FOREACH(pw, &l2vpn->pw_list, entry) { + RB_FOREACH(pw, l2vpn_pw_head, &l2vpn->pw_tree) { memset(&pwctl, 0, sizeof(pwctl)); strlcpy(pwctl.l2vpn_name, pw->l2vpn->name, sizeof(pwctl.l2vpn_name)); @@ -517,7 +522,7 @@ ldpe_l2vpn_init(struct l2vpn *l2vpn) { struct l2vpn_pw *pw; - LIST_FOREACH(pw, &l2vpn->pw_list, entry) + RB_FOREACH(pw, l2vpn_pw_head, &l2vpn->pw_tree) ldpe_l2vpn_pw_init(pw); } @@ -526,7 +531,7 @@ ldpe_l2vpn_exit(struct l2vpn *l2vpn) { struct l2vpn_pw *pw; - LIST_FOREACH(pw, &l2vpn->pw_list, entry) + RB_FOREACH(pw, l2vpn_pw_head, &l2vpn->pw_tree) ldpe_l2vpn_pw_exit(pw); } diff --git a/ldpd/lde.c b/ldpd/lde.c index 522650c..aa83ef0 100644 --- a/ldpd/lde.c +++ b/ldpd/lde.c @@ -511,8 +511,8 @@ lde_dispatch_parent(struct thread *thread) memcpy(nl2vpn, imsg.data, sizeof(struct l2vpn)); RB_INIT(&nl2vpn->if_tree); - LIST_INIT(&nl2vpn->pw_list); - LIST_INIT(&nl2vpn->pw_inactive_list); + RB_INIT(&nl2vpn->pw_tree); + RB_INIT(&nl2vpn->pw_inactive_tree); RB_INSERT(l2vpn_head, &nconf->l2vpn_tree, nl2vpn); break; @@ -530,7 +530,7 @@ lde_dispatch_parent(struct thread *thread) memcpy(npw, imsg.data, sizeof(struct l2vpn_pw)); npw->l2vpn = nl2vpn; - LIST_INSERT_HEAD(&nl2vpn->pw_list, npw, entry); + RB_INSERT(l2vpn_pw_head, &nl2vpn->pw_tree, npw); break; case IMSG_RECONF_L2VPN_IPW: if ((npw = malloc(sizeof(struct l2vpn_pw))) == NULL) @@ -538,7 +538,7 @@ lde_dispatch_parent(struct thread *thread) memcpy(npw, imsg.data, sizeof(struct l2vpn_pw)); npw->l2vpn = nl2vpn; - LIST_INSERT_HEAD(&nl2vpn->pw_inactive_list, npw, entry); + RB_INSERT(l2vpn_pw_head, &nl2vpn->pw_inactive_tree, npw); break; case IMSG_RECONF_END: merge_config(ldeconf, nconf); diff --git a/ldpd/ldp_vty_conf.c b/ldpd/ldp_vty_conf.c index b979642..e408abb 100644 --- a/ldpd/ldp_vty_conf.c +++ b/ldpd/ldp_vty_conf.c @@ -358,9 +358,9 @@ ldp_l2vpn_config_write(struct vty *vty) vty_out(vty, " member interface %s%s", lif->ifname, VTY_NEWLINE); - LIST_FOREACH(pw, &l2vpn->pw_list, entry) + RB_FOREACH(pw, l2vpn_pw_head, &l2vpn->pw_tree) ldp_l2vpn_pw_config_write(vty, pw); - LIST_FOREACH(pw, &l2vpn->pw_inactive_list, entry) + RB_FOREACH(pw, l2vpn_pw_head, &l2vpn->pw_inactive_tree) ldp_l2vpn_pw_config_write(vty, pw); vty_out(vty, " !%s", VTY_NEWLINE); @@ -1425,7 +1425,7 @@ ldp_vty_l2vpn_pseudowire(struct vty *vty, struct vty_arg *args[]) if (pw == NULL) goto cancel; - LIST_REMOVE(pw, entry); + RB_REMOVE(l2vpn_pw_head, &l2vpn->pw_inactive_tree, pw); free(pw); ldp_reload(vty_conf); return (CMD_SUCCESS); @@ -1451,7 +1451,7 @@ ldp_vty_l2vpn_pseudowire(struct vty *vty, struct vty_arg *args[]) pw = l2vpn_pw_new(l2vpn, &kif); pw->flags = F_PW_STATUSTLV_CONF|F_PW_CWORD_CONF; - LIST_INSERT_HEAD(&l2vpn->pw_inactive_list, pw, entry); + RB_INSERT(l2vpn_pw_head, &l2vpn->pw_inactive_tree, pw); ldp_reload_ref(vty_conf, (void **)&pw); VTY_PUSH_CONTEXT_SUB(LDP_PSEUDOWIRE_NODE, pw); @@ -1720,12 +1720,12 @@ l2vpn_del_api(struct ldpd_conf *conf, struct l2vpn *l2vpn) RB_REMOVE(l2vpn_if_head, &l2vpn->if_tree, lif); free(lif); } - while ((pw = LIST_FIRST(&l2vpn->pw_list)) != NULL) { - LIST_REMOVE(pw, entry); + while ((pw = RB_ROOT(&l2vpn->pw_tree)) != NULL) { + RB_REMOVE(l2vpn_pw_head, &l2vpn->pw_tree, pw); free(pw); } - while ((pw = LIST_FIRST(&l2vpn->pw_inactive_list)) != NULL) { - LIST_REMOVE(pw, entry); + while ((pw = RB_ROOT(&l2vpn->pw_inactive_tree)) != NULL) { + RB_REMOVE(l2vpn_pw_head, &l2vpn->pw_inactive_tree, pw); free(pw); } RB_REMOVE(l2vpn_head, &conf->l2vpn_tree, l2vpn); @@ -1784,13 +1784,13 @@ l2vpn_pw_new_api(struct ldpd_conf *conf, struct l2vpn *l2vpn, pw = l2vpn_pw_new(l2vpn, &kif); pw->flags = F_PW_STATUSTLV_CONF|F_PW_CWORD_CONF; - LIST_INSERT_HEAD(&l2vpn->pw_inactive_list, pw, entry); + RB_INSERT(l2vpn_pw_head, &l2vpn->pw_inactive_tree, pw); return (pw); } void -l2vpn_pw_del_api(struct l2vpn_pw *pw) +l2vpn_pw_del_api(struct l2vpn *l2vpn, struct l2vpn_pw *pw) { - LIST_REMOVE(pw, entry); + RB_REMOVE(l2vpn_pw_head, &l2vpn->pw_inactive_tree, pw); free(pw); } diff --git a/ldpd/ldpd.c b/ldpd/ldpd.c index 0df9bbd..943129f 100644 --- a/ldpd/ldpd.c +++ b/ldpd/ldpd.c @@ -878,12 +878,12 @@ main_imsg_send_config(struct ldpd_conf *xconf) sizeof(*lif)) == -1) return (-1); } - LIST_FOREACH(pw, &l2vpn->pw_list, entry) { + RB_FOREACH(pw, l2vpn_pw_head, &l2vpn->pw_tree) { if (main_imsg_compose_both(IMSG_RECONF_L2VPN_PW, pw, sizeof(*pw)) == -1) return (-1); } - LIST_FOREACH(pw, &l2vpn->pw_inactive_list, entry) { + RB_FOREACH(pw, l2vpn_pw_head, &l2vpn->pw_inactive_tree) { if (main_imsg_compose_both(IMSG_RECONF_L2VPN_IPW, pw, sizeof(*pw)) == -1) return (-1); @@ -931,14 +931,14 @@ ldp_config_normalize(struct ldpd_conf *xconf, void **ref) } RB_FOREACH(l2vpn, l2vpn_head, &xconf->l2vpn_tree) { - LIST_FOREACH(pw, &l2vpn->pw_list, entry) { + RB_FOREACH(pw, l2vpn_pw_head, &l2vpn->pw_tree) { if (pw->flags & F_PW_STATIC_NBR_ADDR) continue; pw->af = AF_INET; pw->addr.v4 = pw->lsr_id; } - LIST_FOREACH(pw, &l2vpn->pw_inactive_list, entry) { + RB_FOREACH(pw, l2vpn_pw_head, &l2vpn->pw_inactive_tree) { if (pw->flags & F_PW_STATIC_NBR_ADDR) continue; @@ -1054,8 +1054,8 @@ ldp_dup_config_ref(struct ldpd_conf *conf, void **ref) RB_FOREACH(l2vpn, l2vpn_head, &conf->l2vpn_tree) { COPY(xl, l2vpn); RB_INIT(&xl->if_tree); - LIST_INIT(&xl->pw_list); - LIST_INIT(&xl->pw_inactive_list); + RB_INIT(&xl->pw_tree); + RB_INIT(&xl->pw_inactive_tree); RB_INSERT(l2vpn_head, &xconf->l2vpn_tree, xl); RB_FOREACH(lif, l2vpn_if_head, &l2vpn->if_tree) { @@ -1063,15 +1063,15 @@ ldp_dup_config_ref(struct ldpd_conf *conf, void **ref) xf->l2vpn = xl; RB_INSERT(l2vpn_if_head, &xl->if_tree, xf); } - LIST_FOREACH(pw, &l2vpn->pw_list, entry) { + RB_FOREACH(pw, l2vpn_pw_head, &l2vpn->pw_tree) { COPY(xp, pw); xp->l2vpn = xl; - LIST_INSERT_HEAD(&xl->pw_list, xp, entry); + RB_INSERT(l2vpn_pw_head, &xl->pw_tree, xp); } - LIST_FOREACH(pw, &l2vpn->pw_inactive_list, entry) { + RB_FOREACH(pw, l2vpn_pw_head, &l2vpn->pw_inactive_tree) { COPY(xp, pw); xp->l2vpn = xl; - LIST_INSERT_HEAD(&xl->pw_inactive_list, xp, entry); + RB_INSERT(l2vpn_pw_head, &xl->pw_inactive_tree, xp); } } #undef COPY @@ -1484,9 +1484,9 @@ merge_l2vpns(struct ldpd_conf *conf, struct ldpd_conf *xconf, void **ref) case PROC_MAIN: RB_FOREACH(lif, l2vpn_if_head, &l2vpn->if_tree) QOBJ_UNREG (lif); - LIST_FOREACH(pw, &l2vpn->pw_list, entry) + RB_FOREACH(pw, l2vpn_pw_head, &l2vpn->pw_tree) QOBJ_UNREG (pw); - LIST_FOREACH(pw, &l2vpn->pw_inactive_list, entry) + RB_FOREACH(pw, l2vpn_pw_head, &l2vpn->pw_inactive_tree) QOBJ_UNREG (pw); QOBJ_UNREG (l2vpn); break; @@ -1530,7 +1530,7 @@ merge_l2vpn(struct ldpd_conf *xconf, struct l2vpn *l2vpn, struct l2vpn *xl, void struct l2vpn_pw *pw, *ptmp, *xp; struct nbr *nbr; int reset_nbr, reinstall_pwfec, reinstall_tnbr; - LIST_HEAD(, l2vpn_pw) pw_aux_list; + struct l2vpn_pw_head pw_aux_list; int previous_pw_type, previous_mtu; previous_pw_type = l2vpn->pw_type; @@ -1564,8 +1564,8 @@ merge_l2vpn(struct ldpd_conf *xconf, struct l2vpn *l2vpn, struct l2vpn *xl, void } /* merge active pseudowires */ - LIST_INIT(&pw_aux_list); - LIST_FOREACH_SAFE(pw, &l2vpn->pw_list, entry, ptmp) { + RB_INIT(&pw_aux_list); + RB_FOREACH_SAFE(pw, l2vpn_pw_head, &l2vpn->pw_tree, ptmp) { /* find deleted active pseudowires */ if ((xp = l2vpn_pw_find_name(xl, pw->ifname)) == NULL) { switch (ldpd_process) { @@ -1580,15 +1580,15 @@ merge_l2vpn(struct ldpd_conf *xconf, struct l2vpn *l2vpn, struct l2vpn *xl, void break; } - LIST_REMOVE(pw, entry); + RB_REMOVE(l2vpn_pw_head, &l2vpn->pw_tree, pw); free(pw); } } - LIST_FOREACH_SAFE(xp, &xl->pw_list, entry, ptmp) { + RB_FOREACH_SAFE(xp, l2vpn_pw_head, &xl->pw_tree, ptmp) { /* find new active pseudowires */ if ((pw = l2vpn_pw_find_name(l2vpn, xp->ifname)) == NULL) { - LIST_REMOVE(xp, entry); - LIST_INSERT_HEAD(&l2vpn->pw_list, xp, entry); + RB_REMOVE(l2vpn_pw_head, &xl->pw_tree, xp); + RB_INSERT(l2vpn_pw_head, &l2vpn->pw_tree, xp); xp->l2vpn = l2vpn; switch (ldpd_process) { @@ -1644,8 +1644,8 @@ merge_l2vpn(struct ldpd_conf *xconf, struct l2vpn *l2vpn, struct l2vpn *xl, void } /* remove from active list */ - LIST_REMOVE(pw, entry); - LIST_INSERT_HEAD(&pw_aux_list, pw, entry); + RB_REMOVE(l2vpn_pw_head, &l2vpn->pw_tree, pw); + RB_INSERT(l2vpn_pw_head, &pw_aux_list, pw); } if (ldpd_process == PROC_LDP_ENGINE) { @@ -1689,27 +1689,27 @@ merge_l2vpn(struct ldpd_conf *xconf, struct l2vpn *l2vpn, struct l2vpn *xl, void l2vpn->mtu = previous_mtu; } - LIST_REMOVE(xp, entry); + RB_REMOVE(l2vpn_pw_head, &xl->pw_tree, xp); if (ref && *ref == xp) *ref = pw; free(xp); } /* merge inactive pseudowires */ - LIST_FOREACH_SAFE(pw, &l2vpn->pw_inactive_list, entry, ptmp) { + RB_FOREACH_SAFE(pw, l2vpn_pw_head, &l2vpn->pw_inactive_tree, ptmp) { /* find deleted inactive pseudowires */ if ((xp = l2vpn_pw_find_name(xl, pw->ifname)) == NULL) { - LIST_REMOVE(pw, entry); + RB_REMOVE(l2vpn_pw_head, &l2vpn->pw_inactive_tree, pw); if (ldpd_process == PROC_MAIN) QOBJ_UNREG (pw); free(pw); } } - LIST_FOREACH_SAFE(xp, &xl->pw_inactive_list, entry, ptmp) { + RB_FOREACH_SAFE(xp, l2vpn_pw_head, &xl->pw_inactive_tree, ptmp) { /* find new inactive pseudowires */ if ((pw = l2vpn_pw_find_name(l2vpn, xp->ifname)) == NULL) { - LIST_REMOVE(xp, entry); - LIST_INSERT_HEAD(&l2vpn->pw_inactive_list, xp, entry); + RB_REMOVE(l2vpn_pw_head, &xl->pw_inactive_tree, xp); + RB_INSERT(l2vpn_pw_head, &l2vpn->pw_inactive_tree, xp); xp->l2vpn = l2vpn; if (ldpd_process == PROC_MAIN) QOBJ_REG (xp, l2vpn_pw); @@ -1728,8 +1728,8 @@ merge_l2vpn(struct ldpd_conf *xconf, struct l2vpn *l2vpn, struct l2vpn *xl, void /* check if the pseudowire should be activated */ if (pw->lsr_id.s_addr != INADDR_ANY && pw->pwid != 0) { /* remove from inactive list */ - LIST_REMOVE(pw, entry); - LIST_INSERT_HEAD(&l2vpn->pw_list, pw, entry); + RB_REMOVE(l2vpn_pw_head, &l2vpn->pw_inactive_tree, pw); + RB_INSERT(l2vpn_pw_head, &l2vpn->pw_tree, pw); switch (ldpd_process) { case PROC_LDE_ENGINE: @@ -1743,16 +1743,16 @@ merge_l2vpn(struct ldpd_conf *xconf, struct l2vpn *l2vpn, struct l2vpn *xl, void } } - LIST_REMOVE(xp, entry); + RB_REMOVE(l2vpn_pw_head, &xl->pw_inactive_tree, xp); if (ref && *ref == xp) *ref = pw; free(xp); } /* insert pseudowires that were disabled in the inactive list */ - LIST_FOREACH_SAFE(pw, &pw_aux_list, entry, ptmp) { - LIST_REMOVE(pw, entry); - LIST_INSERT_HEAD(&l2vpn->pw_inactive_list, pw, entry); + RB_FOREACH_SAFE(pw, l2vpn_pw_head, &pw_aux_list, ptmp) { + RB_REMOVE(l2vpn_pw_head, &l2vpn->pw_tree, pw); + RB_INSERT(l2vpn_pw_head, &l2vpn->pw_inactive_tree, pw); } l2vpn->pw_type = xl->pw_type; diff --git a/ldpd/ldpd.h b/ldpd/ldpd.h index 0a21856..6836920 100644 --- a/ldpd/ldpd.h +++ b/ldpd/ldpd.h @@ -337,7 +337,7 @@ RB_PROTOTYPE(l2vpn_if_head, l2vpn_if, entry, l2vpn_if_compare); DECLARE_QOBJ_TYPE(l2vpn_if) struct l2vpn_pw { - LIST_ENTRY(l2vpn_pw) entry; + RB_ENTRY(l2vpn_pw) entry; struct l2vpn *l2vpn; struct in_addr lsr_id; int af; @@ -351,6 +351,8 @@ struct l2vpn_pw { uint8_t flags; QOBJ_FIELDS }; +RB_HEAD(l2vpn_pw_head, l2vpn_pw); +RB_PROTOTYPE(l2vpn_pw_head, l2vpn_pw, entry, l2vpn_pw_compare); DECLARE_QOBJ_TYPE(l2vpn_pw) #define F_PW_STATUSTLV_CONF 0x01 /* status tlv configured */ #define F_PW_STATUSTLV 0x02 /* status tlv negotiated */ @@ -368,8 +370,8 @@ struct l2vpn { char br_ifname[IF_NAMESIZE]; unsigned int br_ifindex; struct l2vpn_if_head if_tree; - LIST_HEAD(, l2vpn_pw) pw_list; - LIST_HEAD(, l2vpn_pw) pw_inactive_list; + struct l2vpn_pw_head pw_tree; + struct l2vpn_pw_head pw_inactive_tree; QOBJ_FIELDS }; RB_HEAD(l2vpn_head, l2vpn); @@ -657,7 +659,8 @@ void l2vpn_if_del_api(struct l2vpn *l2vpn, struct l2vpn_if *lif); struct l2vpn_pw *l2vpn_pw_new_api(struct ldpd_conf *conf, struct l2vpn *l2vpn, const char *ifname); -void l2vpn_pw_del_api(struct l2vpn_pw *pw); +void l2vpn_pw_del_api(struct l2vpn *l2vpn, + struct l2vpn_pw *pw); /* socket.c */ int ldp_create_socket(int, enum socket_type); diff --git a/ldpd/ldpe.c b/ldpd/ldpe.c index 2a9fb4c..c3640d4 100644 --- a/ldpd/ldpe.c +++ b/ldpd/ldpe.c @@ -452,8 +452,8 @@ ldpe_dispatch_main(struct thread *thread) memcpy(nl2vpn, imsg.data, sizeof(struct l2vpn)); RB_INIT(&nl2vpn->if_tree); - LIST_INIT(&nl2vpn->pw_list); - LIST_INIT(&nl2vpn->pw_inactive_list); + RB_INIT(&nl2vpn->pw_tree); + RB_INIT(&nl2vpn->pw_inactive_tree); RB_INSERT(l2vpn_head, &nconf->l2vpn_tree, nl2vpn); break; @@ -471,7 +471,7 @@ ldpe_dispatch_main(struct thread *thread) memcpy(npw, imsg.data, sizeof(struct l2vpn_pw)); npw->l2vpn = nl2vpn; - LIST_INSERT_HEAD(&nl2vpn->pw_list, npw, entry); + RB_INSERT(l2vpn_pw_head, &nl2vpn->pw_tree, npw); break; case IMSG_RECONF_L2VPN_IPW: if ((npw = malloc(sizeof(struct l2vpn_pw))) == NULL) @@ -479,7 +479,7 @@ ldpe_dispatch_main(struct thread *thread) memcpy(npw, imsg.data, sizeof(struct l2vpn_pw)); npw->l2vpn = nl2vpn; - LIST_INSERT_HEAD(&nl2vpn->pw_inactive_list, npw, entry); + RB_INSERT(l2vpn_pw_head, &nl2vpn->pw_inactive_tree, npw); break; case IMSG_RECONF_END: merge_config(leconf, nconf); -- 1.9.1
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@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
participants (1)
-
Renato Westphal