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