From 914d1be411229c28e6e8e4a0df99afa076a8b448 Mon Sep 17 00:00:00 2001 From: Kirill Isakov Date: Wed, 11 Aug 2021 20:56:21 +0600 Subject: [PATCH] Use splay trees inside node_t directly. --- src/address_cache.c | 2 +- src/autoconnect.c | 4 ++-- src/edge.c | 18 ++++++++---------- src/edge.h | 3 +-- src/graph.c | 2 +- src/net.c | 10 +++++----- src/net_packet.c | 10 +++++----- src/node.c | 18 +++++++----------- src/node.h | 4 ++-- src/protocol_auth.c | 6 +++--- src/route.c | 2 +- src/subnet.c | 21 +++++++++------------ src/subnet.h | 5 ++--- 13 files changed, 47 insertions(+), 58 deletions(-) diff --git a/src/address_cache.c b/src/address_cache.c index e17f8964..a414f46f 100644 --- a/src/address_cache.c +++ b/src/address_cache.c @@ -32,7 +32,7 @@ static struct addrinfo *get_known_addresses(node_t *n) { struct addrinfo *ai = NULL; struct addrinfo *oai = NULL; - for splay_each(edge_t, e, n->edge_tree) { + for splay_each(edge_t, e, &n->edge_tree) { if(!e->reverse) { continue; } diff --git a/src/autoconnect.c b/src/autoconnect.c index a5f433cf..4279cd37 100644 --- a/src/autoconnect.c +++ b/src/autoconnect.c @@ -114,7 +114,7 @@ static void drop_superfluous_outgoing_connection() { int count = 0; for list_each(connection_t, c, &connection_list) { - if(!c->edge || !c->outgoing || !c->node || c->node->edge_tree->count < 2) { + if(!c->edge || !c->outgoing || !c->node || c->node->edge_tree.count < 2) { continue; } @@ -128,7 +128,7 @@ static void drop_superfluous_outgoing_connection() { int r = rand() % count; for list_each(connection_t, c, &connection_list) { - if(!c->edge || !c->outgoing || !c->node || c->node->edge_tree->count < 2) { + if(!c->edge || !c->outgoing || !c->node || c->node->edge_tree.count < 2) { continue; } diff --git a/src/edge.c b/src/edge.c index 15d3150d..c521d0e1 100644 --- a/src/edge.c +++ b/src/edge.c @@ -54,12 +54,10 @@ static int edge_compare(const edge_t *a, const edge_t *b) { return strcmp(a->to->name, b->to->name); } -splay_tree_t *new_edge_tree(void) { - return splay_alloc_tree((splay_compare_t) edge_compare, (splay_action_t) free_edge); -} - -void free_edge_tree(splay_tree_t *edge_tree) { - splay_delete_tree(edge_tree); +void init_edge_tree(splay_tree_t *tree) { + memset(tree, 0, sizeof(*tree)); + tree->compare = (splay_compare_t) edge_compare; + tree->delete = (splay_action_t) free_edge; } void exit_edges(void) { @@ -80,7 +78,7 @@ void free_edge(edge_t *e) { } void edge_add(edge_t *e) { - splay_node_t *node = splay_insert(e->from->edge_tree, e); + splay_node_t *node = splay_insert(&e->from->edge_tree, e); if(!node) { logger(DEBUG_ALWAYS, LOG_ERR, "Edge from %s to %s already exists in edge_tree\n", e->from->name, e->to->name); @@ -108,7 +106,7 @@ void edge_del(edge_t *e) { } splay_delete(&edge_weight_tree, e); - splay_delete(e->from->edge_tree, e); + splay_delete(&e->from->edge_tree, e); } edge_t *lookup_edge(node_t *from, node_t *to) { @@ -117,12 +115,12 @@ edge_t *lookup_edge(node_t *from, node_t *to) { v.from = from; v.to = to; - return splay_search(from->edge_tree, &v); + return splay_search(&from->edge_tree, &v); } bool dump_edges(connection_t *c) { for splay_each(node_t, n, &node_tree) { - for splay_each(edge_t, e, n->edge_tree) { + for splay_each(edge_t, e, &n->edge_tree) { char *address = sockaddr2hostname(&e->address); char *local_address = sockaddr2hostname(&e->local_address); send_request(c, "%d %d %s %s %s %s %x %d", diff --git a/src/edge.h b/src/edge.h index 670801bb..6d588fc9 100644 --- a/src/edge.h +++ b/src/edge.h @@ -44,8 +44,7 @@ extern splay_tree_t edge_weight_tree; /* Tree with all known edges sort extern void exit_edges(void); extern edge_t *new_edge(void) __attribute__((__malloc__)); extern void free_edge(edge_t *e); -extern splay_tree_t *new_edge_tree(void) __attribute__((__malloc__)); -extern void free_edge_tree(splay_tree_t *edge_tree); +extern void init_edge_tree(splay_tree_t *tree); extern void edge_add(edge_t *e); extern void edge_del(edge_t *e); extern edge_t *lookup_edge(struct node_t *from, struct node_t *to); diff --git a/src/graph.c b/src/graph.c index bf3e75c7..3dd2ff18 100644 --- a/src/graph.c +++ b/src/graph.c @@ -149,7 +149,7 @@ static void sssp_bfs(void) { abort(); } - for splay_each(edge_t, e, n->edge_tree) { /* "e" is the edge connected to "from" */ + for splay_each(edge_t, e, &n->edge_tree) { /* "e" is the edge connected to "from" */ if(!e->reverse || e->to == myself) { continue; } diff --git a/src/net.c b/src/net.c index 78d4b76b..97ca2dba 100644 --- a/src/net.c +++ b/src/net.c @@ -54,7 +54,7 @@ void purge(void) { if(!n->status.reachable) { logger(DEBUG_SCARY_THINGS, LOG_DEBUG, "Purging node %s (%s)", n->name, n->hostname); - for splay_each(subnet_t, s, n->subnet_tree) { + for splay_each(subnet_t, s, &n->subnet_tree) { send_del_subnet(everyone, s); if(!strictsubnets) { @@ -62,7 +62,7 @@ void purge(void) { } } - for splay_each(edge_t, e, n->edge_tree) { + for splay_each(edge_t, e, &n->edge_tree) { if(!tunnelserver) { send_del_edge(everyone, e); } @@ -81,7 +81,7 @@ void purge(void) { return; } - if(!autoconnect && (!strictsubnets || !n->subnet_tree->head)) + if(!autoconnect && (!strictsubnets || !n->subnet_tree.head)) /* in strictsubnets mode do not delete nodes with subnets */ { node_del(n); @@ -391,7 +391,7 @@ int reload_configuration(void) { } } } else { /* Only read our own subnets back in */ - for splay_each(subnet_t, subnet, myself->subnet_tree) + for splay_each(subnet_t, subnet, &myself->subnet_tree) if(!subnet->expires) { subnet->expires = 1; } @@ -418,7 +418,7 @@ int reload_configuration(void) { cfg = lookup_config_next(&config_tree, cfg); } - for splay_each(subnet_t, subnet, myself->subnet_tree) { + for splay_each(subnet_t, subnet, &myself->subnet_tree) { if(subnet->expires == 1) { send_del_subnet(everyone, subnet); subnet_update(myself, subnet, false); diff --git a/src/net_packet.c b/src/net_packet.c index 290f743f..7bb182db 100644 --- a/src/net_packet.c +++ b/src/net_packet.c @@ -743,10 +743,10 @@ static void choose_udp_address(const node_t *n, const sockaddr_t **sa, size_t *s So we pick a random edge and a random socket. */ unsigned int i = 0; - unsigned int j = rand() % n->edge_tree->count; + unsigned int j = rand() % n->edge_tree.count; edge_t *candidate = NULL; - for splay_each(edge_t, e, n->edge_tree) { + for splay_each(edge_t, e, &n->edge_tree) { if(i++ == j) { candidate = e->reverse; break; @@ -767,10 +767,10 @@ static void choose_local_address(const node_t *n, const sockaddr_t **sa, size_t /* Pick one of the edges from this node at random, then use its local address. */ unsigned int i = 0; - unsigned int j = rand() % n->edge_tree->count; + unsigned int j = rand() % n->edge_tree.count; edge_t *candidate = NULL; - for splay_each(edge_t, e, n->edge_tree) { + for splay_each(edge_t, e, &n->edge_tree) { if(i++ == j) { candidate = e; break; @@ -1672,7 +1672,7 @@ static node_t *try_harder(const sockaddr_t *from, const vpn_packet_t *pkt) { bool soft = false; - for splay_each(edge_t, e, n->edge_tree) { + for splay_each(edge_t, e, &n->edge_tree) { if(!e->reverse) { continue; } diff --git a/src/node.c b/src/node.c index 850f2dae..4caf992d 100644 --- a/src/node.c +++ b/src/node.c @@ -78,8 +78,9 @@ node_t *new_node(void) { n->late = xzalloc(replaywin); } - n->subnet_tree = new_subnet_tree(); - n->edge_tree = new_edge_tree(); + init_subnet_tree(&n->subnet_tree); + init_edge_tree(&n->edge_tree); + n->mtu = MTU; n->maxmtu = MTU; n->udp_ping_rtt = -1; @@ -88,13 +89,8 @@ node_t *new_node(void) { } void free_node(node_t *n) { - if(n->subnet_tree) { - free_subnet_tree(n->subnet_tree); - } - - if(n->edge_tree) { - free_edge_tree(n->edge_tree); - } + splay_empty_tree(&n->subnet_tree); + splay_empty_tree(&n->edge_tree); sockaddrfree(&n->address); @@ -133,11 +129,11 @@ void node_add(node_t *n) { void node_del(node_t *n) { splay_delete(&node_udp_tree, n); - for splay_each(subnet_t, s, n->subnet_tree) { + for splay_each(subnet_t, s, &n->subnet_tree) { subnet_del(n, s); } - for splay_each(edge_t, e, n->edge_tree) { + for splay_each(edge_t, e, &n->edge_tree) { edge_del(e); } diff --git a/src/node.h b/src/node.h index b6039684..f312043d 100644 --- a/src/node.h +++ b/src/node.h @@ -77,9 +77,9 @@ typedef struct node_t { struct edge_t *prevedge; /* nearest node from him to us */ struct node_t *via; /* next hop for UDP packets */ - splay_tree_t *subnet_tree; /* Pointer to a tree of subnets belonging to this node */ + splay_tree_t subnet_tree; /* Pointer to a tree of subnets belonging to this node */ - splay_tree_t *edge_tree; /* Edges with this node as one of the endpoints */ + splay_tree_t edge_tree; /* Edges with this node as one of the endpoints */ struct connection_t *connection; /* Connection associated with this node (if a direct connection exists) */ diff --git a/src/protocol_auth.c b/src/protocol_auth.c index 33341296..e457b19e 100644 --- a/src/protocol_auth.c +++ b/src/protocol_auth.c @@ -886,7 +886,7 @@ static void send_everything(connection_t *c) { } if(tunnelserver) { - for splay_each(subnet_t, s, myself->subnet_tree) { + for splay_each(subnet_t, s, &myself->subnet_tree) { send_add_subnet(c, s); } @@ -894,11 +894,11 @@ static void send_everything(connection_t *c) { } for splay_each(node_t, n, &node_tree) { - for splay_each(subnet_t, s, n->subnet_tree) { + for splay_each(subnet_t, s, &n->subnet_tree) { send_add_subnet(c, s); } - for splay_each(edge_t, e, n->edge_tree) { + for splay_each(edge_t, e, &n->edge_tree) { send_add_edge(c, e); } } diff --git a/src/route.c b/src/route.c index 559cf2fc..26a8aabc 100644 --- a/src/route.c +++ b/src/route.c @@ -494,7 +494,7 @@ static void age_subnets(void *data) { (void)data; bool left = false; - for splay_each(subnet_t, s, myself->subnet_tree) { + for splay_each(subnet_t, s, &myself->subnet_tree) { if(s->expires && s->expires < now.tv_sec) { if(debug_level >= DEBUG_TRAFFIC) { char netstr[MAXNETSTR]; diff --git a/src/subnet.c b/src/subnet.c index e0d1acbc..04254957 100644 --- a/src/subnet.c +++ b/src/subnet.c @@ -66,12 +66,9 @@ void exit_subnets(void) { hash_free(mac_cache); } -splay_tree_t *new_subnet_tree(void) { - return splay_alloc_tree((splay_compare_t) subnet_compare, NULL); -} - -void free_subnet_tree(splay_tree_t *subnet_tree) { - splay_delete_tree(subnet_tree); +void init_subnet_tree(splay_tree_t *tree) { + memset(tree, 0, sizeof(*tree)); + tree->compare = (splay_compare_t) subnet_compare; } /* Allocating and freeing space for subnets */ @@ -92,7 +89,7 @@ void subnet_add(node_t *n, subnet_t *subnet) { splay_insert(&subnet_tree, subnet); if(n) { - splay_insert(n->subnet_tree, subnet); + splay_insert(&n->subnet_tree, subnet); } subnet_cache_flush(); @@ -100,7 +97,7 @@ void subnet_add(node_t *n, subnet_t *subnet) { void subnet_del(node_t *n, subnet_t *subnet) { if(n) { - splay_delete(n->subnet_tree, subnet); + splay_delete(&n->subnet_tree, subnet); } splay_delete(&subnet_tree, subnet); @@ -110,8 +107,8 @@ void subnet_del(node_t *n, subnet_t *subnet) { /* Subnet lookup routines */ -subnet_t *lookup_subnet(const node_t *owner, const subnet_t *subnet) { - return splay_search(owner->subnet_tree, subnet); +subnet_t *lookup_subnet(node_t *owner, const subnet_t *subnet) { + return splay_search(&owner->subnet_tree, subnet); } subnet_t *lookup_subnet_mac(const node_t *owner, const mac_t *address) { @@ -125,7 +122,7 @@ subnet_t *lookup_subnet_mac(const node_t *owner, const mac_t *address) { // Search all subnets for a matching one - for splay_each(subnet_t, p, owner ? owner->subnet_tree : &subnet_tree) { + for splay_each(subnet_t, p, owner ? &owner->subnet_tree : &subnet_tree) { if(!p || p->type != SUBNET_MAC) { continue; } @@ -241,7 +238,7 @@ void subnet_update(node_t *owner, subnet_t *subnet, bool up) { name = up ? "subnet-up" : "subnet-down"; if(!subnet) { - for splay_each(subnet_t, subnet, owner->subnet_tree) { + for splay_each(subnet_t, subnet, &owner->subnet_tree) { if(!net2str(netstr, sizeof(netstr), subnet)) { continue; } diff --git a/src/subnet.h b/src/subnet.h index 2e27f68f..eb558495 100644 --- a/src/subnet.h +++ b/src/subnet.h @@ -70,8 +70,7 @@ extern subnet_t *new_subnet(void) __attribute__((__malloc__)); extern void free_subnet(subnet_t *subnet); extern void init_subnets(void); extern void exit_subnets(void); -extern splay_tree_t *new_subnet_tree(void) __attribute__((__malloc__)); -extern void free_subnet_tree(splay_tree_t *); +extern void init_subnet_tree(splay_tree_t *tree); extern void subnet_add(struct node_t *owner, subnet_t *subnet); extern void subnet_del(struct node_t *owner, subnet_t *subnet); extern void subnet_update(struct node_t *owner, subnet_t *subnet, bool up); @@ -82,7 +81,7 @@ extern bool subnetcheck(const subnet_t subnet); extern bool maskcheck(const void *mask, size_t masklen, size_t len); extern bool net2str(char *netstr, size_t len, const subnet_t *subnet); extern bool str2net(subnet_t *subnet, const char *netstr); -extern subnet_t *lookup_subnet(const struct node_t *owner, const subnet_t *subnet); +extern subnet_t *lookup_subnet(struct node_t *owner, const subnet_t *subnet); extern subnet_t *lookup_subnet_mac(const struct node_t *owner, const mac_t *address); extern subnet_t *lookup_subnet_ipv4(const ipv4_t *address); extern subnet_t *lookup_subnet_ipv6(const ipv6_t *address); -- 2.20.1