From ff306f0cdaedb50de1472e7c1fb55de922a6ca60 Mon Sep 17 00:00:00 2001
From: Guus Sliepen <guus@tinc-vpn.org>
Date: Sun, 7 Oct 2012 21:59:53 +0200
Subject: [PATCH] Replace the connection_tree with a connection_list.

The tree functions were never used on the connection_tree, a list is more appropriate.
Also be more paranoid about connections disappearing while traversing the list.
---
 src/connection.c    | 29 ++++++++++++++---------------
 src/connection.h    |  4 ++--
 src/control.c       |  3 +--
 src/graph.c         | 19 +++++++------------
 src/logger.c        |  3 ++-
 src/meta.c          |  9 +++------
 src/net.c           | 40 +++++++++++++++-------------------------
 src/net_packet.c    | 14 +++++---------
 src/net_setup.c     | 15 +++++----------
 src/net_socket.c    | 15 +++++++--------
 src/protocol_auth.c |  1 -
 src/protocol_edge.c |  1 -
 src/protocol_key.c  | 11 ++++-------
 src/route.c         | 27 +++++++++++----------------
 src/sptps_test.c    |  2 +-
 15 files changed, 77 insertions(+), 116 deletions(-)

diff --git a/src/connection.c b/src/connection.c
index 7999b6fb..3591f13e 100644
--- a/src/connection.c
+++ b/src/connection.c
@@ -21,7 +21,7 @@
 
 #include "system.h"
 
-#include "splay_tree.h"
+#include "list.h"
 #include "cipher.h"
 #include "conf.h"
 #include "control_common.h"
@@ -31,22 +31,18 @@
 #include "utils.h"
 #include "xalloc.h"
 
-splay_tree_t *connection_tree;	/* Meta connections */
+list_t *connection_list;	/* Meta connections */
 connection_t *everyone;
 
-static int connection_compare(const connection_t *a, const connection_t *b) {
-	return a < b ? -1 : a == b ? 0 : 1;
-}
-
 void init_connections(void) {
-	connection_tree = splay_alloc_tree((splay_compare_t) connection_compare, (splay_action_t) free_connection);
+	connection_list = list_alloc((list_action_t) free_connection);
 	everyone = new_connection();
 	everyone->name = xstrdup("everyone");
 	everyone->hostname = xstrdup("BROADCAST");
 }
 
 void exit_connections(void) {
-	splay_delete_tree(connection_tree);
+	list_delete_list(connection_list);
 	free_connection(everyone);
 }
 
@@ -91,19 +87,22 @@ void free_connection(connection_t *c) {
 }
 
 void connection_add(connection_t *c) {
-	splay_insert(connection_tree, c);
+	list_insert_tail(connection_list, c);
 }
 
 void connection_del(connection_t *c) {
-	splay_delete(connection_tree, c);
+	for(list_node_t *node = connection_list->head; node; node = node->next) {
+		if(node->data == c) {
+			list_delete_node(connection_list, node);
+			return;
+		}
+	}
 }
 
 bool dump_connections(connection_t *cdump) {
-	splay_node_t *node;
-	connection_t *c;
-
-	for(node = connection_tree->head; node; node = node->next) {
-		c = node->data;
+	for(list_node_t *node = connection_list->head, *next; node; node = next) {
+		next = node->next;
+		connection_t *c = node->data;
 		send_request(cdump, "%d %d %s %s %x %d %x",
 				CONTROL, REQ_DUMP_CONNECTIONS,
 				c->name, c->hostname, c->options, c->socket,
diff --git a/src/connection.h b/src/connection.h
index 5730fbb8..ec342b39 100644
--- a/src/connection.h
+++ b/src/connection.h
@@ -25,7 +25,7 @@
 #include "cipher.h"
 #include "digest.h"
 #include "rsa.h"
-#include "splay_tree.h"
+#include "list.h"
 #include "sptps.h"
 
 #define OPTION_INDIRECT		0x0001
@@ -100,7 +100,7 @@ typedef struct connection_t {
 	splay_tree_t *config_tree;	/* Pointer to configuration tree belonging to him */
 } connection_t;
 
-extern splay_tree_t *connection_tree;
+extern list_t *connection_list;
 extern connection_t *everyone;
 
 extern void init_connections(void);
diff --git a/src/control.c b/src/control.c
index 956d6ee1..46300ed9 100644
--- a/src/control.c
+++ b/src/control.c
@@ -100,13 +100,12 @@ bool control_h(connection_t *c, const char *request) {
 		case REQ_DISCONNECT: {
 			char name[MAX_STRING_SIZE];
 			connection_t *other;
-			splay_node_t *node, *next;
 			bool found = false;
 
 			if(sscanf(request, "%*d %*d " MAX_STRING, name) != 1)
 				return control_return(c, REQ_DISCONNECT, -1);
 
-			for(node = connection_tree->head; node; node = next) {
+			for(list_node_t *node = connection_list->head, *next; node; node = next) {
 				next = node->next;
 				other = node->data;
 				if(strcmp(other->name, name))
diff --git a/src/graph.c b/src/graph.c
index 621dd9be..3cc99c65 100644
--- a/src/graph.c
+++ b/src/graph.c
@@ -44,12 +44,12 @@
 
 #include "system.h"
 
-#include "splay_tree.h"
 #include "config.h"
 #include "connection.h"
 #include "device.h"
 #include "edge.h"
 #include "graph.h"
+#include "list.h"
 #include "logger.h"
 #include "netutl.h"
 #include "node.h"
@@ -66,15 +66,10 @@
 */
 
 static void mst_kruskal(void) {
-	splay_node_t *node, *next;
-	edge_t *e;
-	node_t *n;
-	connection_t *c;
-
 	/* Clear MST status on connections */
 
-	for(node = connection_tree->head; node; node = node->next) {
-		c = node->data;
+	for(list_node_t *node = connection_list->head; node; node = node->next) {
+		connection_t *c = node->data;
 		c->status.mst = false;
 	}
 
@@ -82,16 +77,16 @@ static void mst_kruskal(void) {
 
 	/* Clear visited status on nodes */
 
-	for(node = node_tree->head; node; node = node->next) {
-		n = node->data;
+	for(splay_node_t *node = node_tree->head; node; node = node->next) {
+		node_t *n = node->data;
 		n->status.visited = false;
 	}
 
 	/* Add safe edges */
 
-	for(node = edge_weight_tree->head; node; node = next) {
+	for(splay_node_t *node = edge_weight_tree->head, *next; node; node = next) {
 		next = node->next;
-		e = node->data;
+		edge_t *e = node->data;
 
 		if(!e->reverse || (e->from->status.visited && e->to->status.visited))
 			continue;
diff --git a/src/logger.c b/src/logger.c
index 56bee845..5de88bde 100644
--- a/src/logger.c
+++ b/src/logger.c
@@ -140,7 +140,8 @@ void logger(int level, int priority, const char *format, ...) {
 	if(logcontrol) {
 		suppress = true;
 		logcontrol = false;
-		for(splay_node_t *node = connection_tree->head; node; node = node->next) {
+		for(list_node_t *node = connection_list->head, *next; node; node = next) {
+			next = node->next;
 			connection_t *c = node->data;
 			if(!c->status.log)
 				continue;
diff --git a/src/meta.c b/src/meta.c
index 9b2ecc26..7562792e 100644
--- a/src/meta.c
+++ b/src/meta.c
@@ -21,7 +21,6 @@
 
 #include "system.h"
 
-#include "splay_tree.h"
 #include "cipher.h"
 #include "connection.h"
 #include "logger.h"
@@ -77,11 +76,9 @@ bool send_meta(connection_t *c, const char *buffer, int length) {
 }
 
 void broadcast_meta(connection_t *from, const char *buffer, int length) {
-	splay_node_t *node;
-	connection_t *c;
-
-	for(node = connection_tree->head; node; node = node->next) {
-		c = node->data;
+	for(list_node_t *node = connection_list->head, *next; node; node = next) {
+		next = node->next;
+		connection_t *c = node->data;
 
 		if(c != from && c->status.active)
 			send_meta(c, buffer, length);
diff --git a/src/net.c b/src/net.c
index 9a32d628..ddca1c9b 100644
--- a/src/net.c
+++ b/src/net.c
@@ -23,7 +23,6 @@
 #include "system.h"
 
 #include "utils.h"
-#include "splay_tree.h"
 #include "conf.h"
 #include "connection.h"
 #include "device.h"
@@ -158,13 +157,11 @@ void terminate_connection(connection_t *c, bool report) {
   and close the connection.
 */
 static void timeout_handler(int fd, short events, void *event) {
-	splay_node_t *node, *next;
-	connection_t *c;
 	time_t now = time(NULL);
 
-	for(node = connection_tree->head; node; node = next) {
+	for(list_node_t *node = connection_list->head, *next; node; node = next) {
 		next = node->next;
-		c = node->data;
+		connection_t *c = node->data;
 
 		if(c->status.control)
 			continue;
@@ -249,10 +246,7 @@ static void sigalrm_handler(int signal, short events, void *data) {
 }
 
 int reload_configuration(void) {
-	connection_t *c;
-	splay_node_t *node, *next;
 	char *fname;
-	struct stat s;
 
 	/* Reread our own configuration file */
 
@@ -278,18 +272,16 @@ int reload_configuration(void) {
 	/* If StrictSubnet is set, expire deleted Subnets and read new ones in */
 
 	if(strictsubnets) {
-		subnet_t *subnet;
-
-		for(node = subnet_tree->head; node; node = node->next) {
-			subnet = node->data;
+		for(splay_node_t *node = subnet_tree->head; node; node = node->next) {
+			subnet_t *subnet = node->data;
 			subnet->expires = 1;
 		}
 
 		load_all_subnets();
 
-		for(node = subnet_tree->head; node; node = next) {
+		for(splay_node_t *node = subnet_tree->head, *next; node; node = next) {
 			next = node->next;
-			subnet = node->data;
+			subnet_t *subnet = node->data;
 			if(subnet->expires == 1) {
 				send_del_subnet(everyone, subnet);
 				if(subnet->owner->status.reachable)
@@ -304,9 +296,7 @@ int reload_configuration(void) {
 			}
 		}
 	} else { /* Only read our own subnets back in */
-		subnet_t *subnet, *s2;
-
-		for(node = myself->subnet_tree->head; node; node = node->next) {
+		for(splay_node_t *node = myself->subnet_tree->head; node; node = node->next) {
 			subnet_t *subnet = node->data;
 			if(!subnet->expires)
 				subnet->expires = 1;
@@ -315,6 +305,8 @@ int reload_configuration(void) {
 		config_t *cfg = lookup_config(config_tree, "Subnet");
 
 		while(cfg) {
+			subnet_t *subnet, *s2;
+
 			if(!get_config_subnet(cfg, &subnet))
 				continue;
 
@@ -332,7 +324,7 @@ int reload_configuration(void) {
 			cfg = lookup_config_next(config_tree, cfg);
 		}
 
-		for(node = myself->subnet_tree->head; node; node = next) {
+		for(splay_node_t *node = myself->subnet_tree->head, *next; node; node = next) {
 			next = node->next;
 			subnet_t *subnet = node->data;
 			if(subnet->expires == 1) {
@@ -349,14 +341,15 @@ int reload_configuration(void) {
 
 	/* Close connections to hosts that have a changed or deleted host config file */
 
-	for(node = connection_tree->head; node; node = next) {
-		c = node->data;
+	for(list_node_t *node = connection_list->head, *next; node; node = next) {
+		connection_t *c = node->data;
 		next = node->next;
 
 		if(c->status.control)
 			continue;
 
 		xasprintf(&fname, "%s" SLASH "hosts" SLASH "%s", confbase, c->name);
+		struct stat s;
 		if(stat(fname, &s) || s.st_mtime > last_config_check) {
 			logger(DEBUG_CONNECTIONS, LOG_INFO, "Host config file of %s has been changed", c->name);
 			terminate_connection(c, c->status.active);
@@ -370,12 +363,9 @@ int reload_configuration(void) {
 }
 
 void retry(void) {
-	connection_t *c;
-	splay_node_t *node, *next;
-
-	for(node = connection_tree->head; node; node = next) {
+	for(list_node_t *node = connection_list->head, *next; node; node = next) {
 		next = node->next;
-		c = node->data;
+		connection_t *c = node->data;
 		
 		if(c->outgoing && !c->node) {
 			if(timeout_initialized(&c->outgoing->ev))
diff --git a/src/net_packet.c b/src/net_packet.c
index 84392693..c9a66637 100644
--- a/src/net_packet.c
+++ b/src/net_packet.c
@@ -36,7 +36,6 @@
 #include LZO1X_H
 #endif
 
-#include "splay_tree.h"
 #include "cipher.h"
 #include "conf.h"
 #include "connection.h"
@@ -750,10 +749,6 @@ void send_packet(node_t *n, vpn_packet_t *packet) {
 /* Broadcast a packet using the minimum spanning tree */
 
 void broadcast_packet(const node_t *from, vpn_packet_t *packet) {
-	splay_node_t *node;
-	connection_t *c;
-	node_t *n;
-
 	// Always give ourself a copy of the packet.
 	if(from != myself)
 		send_packet(myself, packet);
@@ -771,8 +766,9 @@ void broadcast_packet(const node_t *from, vpn_packet_t *packet) {
 		// This guarantees all nodes receive the broadcast packet, and
 		// usually distributes the sending of broadcast packets over all nodes.
 		case BMODE_MST:
-			for(node = connection_tree->head; node; node = node->next) {
-				c = node->data;
+			for(list_node_t *node = connection_list->head, *next; node; node = next) {
+				next = node->next;
+				connection_t *c = node->data;
 
 				if(c->status.active && c->status.mst && c != from->nexthop->connection)
 					send_packet(c->node, packet);
@@ -786,8 +782,8 @@ void broadcast_packet(const node_t *from, vpn_packet_t *packet) {
 			if(from != myself)
 				break;
 
-			for(node = node_tree->head; node; node = node->next) {
-				n = node->data;
+			for(splay_node_t *node = node_tree->head; node; node = node->next) {
+				node_t *n = node->data;
 
 				if(n->status.reachable && ((n->via == myself && n->nexthop == n) || n->via == n))
 					send_packet(n, packet);
diff --git a/src/net_setup.c b/src/net_setup.c
index fd595a93..b1a8476d 100644
--- a/src/net_setup.c
+++ b/src/net_setup.c
@@ -22,7 +22,6 @@
 
 #include "system.h"
 
-#include "splay_tree.h"
 #include "cipher.h"
 #include "conf.h"
 #include "connection.h"
@@ -972,14 +971,9 @@ bool setup_network(void) {
   close all open network connections
 */
 void close_network_connections(void) {
-	splay_node_t *node, *next;
-	connection_t *c;
-	char *envp[5];
-	int i;
-
-	for(node = connection_tree->head; node; node = next) {
+	for(list_node_t *node = connection_list->head, *next; node; node = next) {
 		next = node->next;
-		c = node->data;
+		connection_t *c = node->data;
 		/* Keep control connections open until the end, so they know when we really terminated */
 		if(c->status.control)
 			c->socket = -1;
@@ -995,13 +989,14 @@ void close_network_connections(void) {
 		free_connection(myself->connection);
 	}
 
-	for(i = 0; i < listen_sockets; i++) {
+	for(int i = 0; i < listen_sockets; i++) {
 		event_del(&listen_socket[i].ev_tcp);
 		event_del(&listen_socket[i].ev_udp);
 		close(listen_socket[i].tcp);
 		close(listen_socket[i].udp);
 	}
 
+	char *envp[5];
 	xasprintf(&envp[0], "NETNAME=%s", netname ? : "");
 	xasprintf(&envp[1], "DEVICE=%s", device ? : "");
 	xasprintf(&envp[2], "INTERFACE=%s", iface ? : "");
@@ -1018,7 +1013,7 @@ void close_network_connections(void) {
 
 	if(myport) free(myport);
 
-	for(i = 0; i < 4; i++)
+	for(int i = 0; i < 4; i++)
 		free(envp[i]);
 
 	devops.close();
diff --git a/src/net_socket.c b/src/net_socket.c
index 0f0580ec..a39c2d28 100644
--- a/src/net_socket.c
+++ b/src/net_socket.c
@@ -22,7 +22,6 @@
 
 #include "system.h"
 
-#include "splay_tree.h"
 #include "conf.h"
 #include "connection.h"
 #include "logger.h"
@@ -627,9 +626,9 @@ void try_outgoing_connections(void) {
 
 	/* Terminate any connections whose outgoing_t is to be deleted. */
 
-	for(splay_node_t *n = connection_tree->head, *next; n; n = next) {
-		next = n->next;
-		connection_t *c = n->data;
+	for(list_node_t *node = connection_list->head, *next; node; node = next) {
+		next = node->next;
+		connection_t *c = node->data;
 		if(c->outgoing && c->outgoing->timeout == -1) {
 			c->outgoing = NULL;
 			logger(DEBUG_CONNECTIONS, LOG_INFO, "No more outgoing connection to %s", c->name);
@@ -639,10 +638,10 @@ void try_outgoing_connections(void) {
 
 	/* Delete outgoing_ts for which there is no ConnectTo. */
 
-	for(list_node_t *i = outgoing_list->head, *next; i; i = next) {
-		next = i->next;
-		outgoing = i->data;
+	for(list_node_t *node = outgoing_list->head, *next; node; node = next) {
+		next = node->next;
+		outgoing = node->data;
 		if(outgoing->timeout == -1)
-			list_delete_node(outgoing_list, i);
+			list_delete_node(outgoing_list, node);
 	}
 }
diff --git a/src/protocol_auth.c b/src/protocol_auth.c
index 908ab247..59917c6c 100644
--- a/src/protocol_auth.c
+++ b/src/protocol_auth.c
@@ -20,7 +20,6 @@
 
 #include "system.h"
 
-#include "splay_tree.h"
 #include "conf.h"
 #include "connection.h"
 #include "control.h"
diff --git a/src/protocol_edge.c b/src/protocol_edge.c
index e1d2051b..d1a11f41 100644
--- a/src/protocol_edge.c
+++ b/src/protocol_edge.c
@@ -21,7 +21,6 @@
 
 #include "system.h"
 
-#include "splay_tree.h"
 #include "conf.h"
 #include "connection.h"
 #include "edge.h"
diff --git a/src/protocol_key.c b/src/protocol_key.c
index f34a70da..7e122068 100644
--- a/src/protocol_key.c
+++ b/src/protocol_key.c
@@ -20,7 +20,6 @@
 
 #include "system.h"
 
-#include "splay_tree.h"
 #include "cipher.h"
 #include "connection.h"
 #include "crypto.h"
@@ -37,15 +36,13 @@
 static bool mykeyused = false;
 
 void send_key_changed(void) {
-	splay_node_t *node;
-	connection_t *c;
-
 	send_request(everyone, "%d %x %s", KEY_CHANGED, rand(), myself->name);
 
 	/* Immediately send new keys to directly connected nodes to keep UDP mappings alive */
 
-	for(node = connection_tree->head; node; node = node->next) {
-		c = node->data;
+	for(list_node_t *node = connection_list->head, *next; node; node = next) {
+		next = node->next;
+		connection_t *c = node->data;
 		if(c->status.active && c->node && c->node->status.reachable) {
 			if(!c->node->status.sptps)
 				send_ans_key(c->node);
@@ -55,7 +52,7 @@ void send_key_changed(void) {
 	/* Force key exchange for connections using SPTPS */
 
 	if(experimental) {
-		for(node = node_tree->head; node; node = node->next) {
+		for(splay_node_t *node = node_tree->head; node; node = node->next) {
 			node_t *n = node->data;
 			if(n->status.reachable && n->status.validkey && n->status.sptps)
 				sptps_force_kex(&n->sptps);
diff --git a/src/route.c b/src/route.c
index 4c4312cd..9b939580 100644
--- a/src/route.c
+++ b/src/route.c
@@ -20,7 +20,6 @@
 
 #include "system.h"
 
-#include "splay_tree.h"
 #include "connection.h"
 #include "control_common.h"
 #include "ethernet.h"
@@ -187,15 +186,12 @@ static void swap_mac_addresses(vpn_packet_t *packet) {
 }
 	
 static void age_subnets(int fd, short events, void *data) {
-	subnet_t *s;
-	connection_t *c;
-	splay_node_t *node, *next, *node2;
 	bool left = false;
 	time_t now = time(NULL);
 
-	for(node = myself->subnet_tree->head; node; node = next) {
+	for(splay_node_t *node = myself->subnet_tree->head, *next; node; node = next) {
 		next = node->next;
-		s = node->data;
+		subnet_t *s = node->data;
 		if(s->expires && s->expires < now) {
 			if(debug_level >= DEBUG_TRAFFIC) {
 				char netstr[MAXNETSTR];
@@ -203,8 +199,9 @@ static void age_subnets(int fd, short events, void *data) {
 					logger(DEBUG_TRAFFIC, LOG_INFO, "Subnet %s expired", netstr);
 			}
 
-			for(node2 = connection_tree->head; node2; node2 = node2->next) {
-				c = node2->data;
+			for(list_node_t *node = connection_list->head, *next; node; node = next) {
+				next = node->next;
+				connection_t *c = node->data;
 				if(c->status.active)
 					send_del_subnet(c, s);
 			}
@@ -221,11 +218,7 @@ static void age_subnets(int fd, short events, void *data) {
 }
 
 static void learn_mac(mac_t *address) {
-	subnet_t *subnet;
-	splay_node_t *node;
-	connection_t *c;
-
-	subnet = lookup_subnet_mac(myself, address);
+	subnet_t *subnet = lookup_subnet_mac(myself, address);
 
 	/* If we don't know this MAC address yet, store it */
 
@@ -244,8 +237,9 @@ static void learn_mac(mac_t *address) {
 
 		/* And tell all other tinc daemons it's our MAC */
 
-		for(node = connection_tree->head; node; node = node->next) {
-			c = node->data;
+		for(list_node_t *node = connection_list->head, *next; node; node = next) {
+			next = node->next;
+			connection_t *c = node->data;
 			if(c->status.active)
 				send_add_subnet(c, subnet);
 		}
@@ -878,7 +872,8 @@ static void route_mac(node_t *source, vpn_packet_t *packet) {
 
 static void send_pcap(vpn_packet_t *packet) {
 	pcap = false;
-	for(splay_node_t *node = connection_tree->head; node; node = node->next) {
+	for(list_node_t *node = connection_list->head, *next; node; node = next) {
+		next = node->next;
 		connection_t *c = node->data;
 		if(!c->status.pcap)
 			continue;
diff --git a/src/sptps_test.c b/src/sptps_test.c
index 7af8522e..d8b25d4e 100644
--- a/src/sptps_test.c
+++ b/src/sptps_test.c
@@ -26,7 +26,7 @@
 
 // Symbols necessary to link with logger.o
 bool send_request(void *c, const char *msg, ...) { return false; }
-struct splay_tree_t *connection_tree = NULL;
+struct list_t *connection_list = NULL;
 bool send_meta(void *c, const char *msg , int len) { return false; }
 char *logfilename = NULL;
 
-- 
2.20.1