Store clients inside a splay tree

From day one we've been using a static array of client struct to hold
the clients data.  This has variuos drawbacks, among which:

 * reuse of the storage  ("shades of heartbleed")
 * maximum fixed amount of clients connected at the same time
 * bugs are harder to debug

The last point in particular is important because if we mess the client
ids, or try to execute some functions (e.g. the various fcgi_*) after a
client has been disconnected, it's harder to "see" this "use after
free"-tier kind of bug.

Now I'm using a splay tree to hold the data about the live connections.
Each client' data is managed by malloc.  If we try to access a client
data after the disconnection we'll probably crash with a SIGSEGV and
find the bug is more easy.  

Performance-wise the connection phase should be faster since we don't
have to loop anymore to find an empty spot in the clients array, but
some operations could be slightly slower (compare the O(1) access in an
array with a SPLAY_FIND operation -- still be faster than O(n) thought.)

1 files changed, 43 insertions, 33 deletions

diff --git a/server.c b/server.c
index 66202c4..4f5e4f2 100644
--- a/server.c
+++ b/server.c
@@ -31,8 +31,6 @@
 
 int shutting_down;
 
-struct client	 clients[MAX_USERS];
-
 static struct tls	*ctx;
 
 static struct event e4, e6, imsgev, siginfo, sigusr2;
@@ -84,6 +82,10 @@ static imsg_handlerfn *handlers[] = {
 	[IMSG_FCGI_FD] = handle_imsg_fcgi_fd,
 };
 
+static uint32_t server_client_id;
+
+struct client_tree_id clients;
+
 static inline int
 matches(const char *pattern, const char *path)
 {
@@ -1165,6 +1167,8 @@ client_close(struct client *c)
 	 * this point.
 	 */
 
+	SPLAY_REMOVE(client_tree_id, &clients, c);
+
 	if (c->cgibev != NULL) {
 		bufferevent_disable(c->cgibev, EVBUFFER_READ|EVBUFFER_WRITE);
 		bufferevent_free(c->cgibev);
@@ -1275,7 +1279,7 @@ do_accept(int sock, short et, void *d)
 	struct sockaddr_storage addr;
 	struct sockaddr *saddr;
 	socklen_t len;
-	int i, fd;
+	int fd;
 
 	(void)et;
 
@@ -1289,44 +1293,41 @@ do_accept(int sock, short et, void *d)
 
 	mark_nonblock(fd);
 
-	for (i = 0; i < MAX_USERS; ++i) {
-		c = &clients[i];
-		if (c->fd == -1) {
-			memset(c, 0, sizeof(*c));
-			c->id = i;
-			if (tls_accept_socket(ctx, &c->ctx, fd) == -1)
-				break; /* goodbye fd! */
-
-			c->fd = fd;
-			c->pfd = -1;
-			c->dir = NULL;
-			c->addr = addr;
-
-			event_once(c->fd, EV_READ|EV_WRITE, handle_handshake,
-			    c, NULL);
+	c = xcalloc(1, sizeof(*c));
+	c->id = ++server_client_id;
+	c->fd = fd;
+	c->pfd = -1;
+	c->addr = addr;
 
-			connected_clients++;
-			return;
-		}
+	if (tls_accept_socket(ctx, &c->ctx, fd) == -1) {
+		log_warn(c, "failed to accept socket: %s", tls_error(c->ctx));
+		close(c->fd);
+		free(c);
+		return;
 	}
 
-	close(fd);
+	SPLAY_INSERT(client_tree_id, &clients, c);
+	event_once(c->fd, EV_READ|EV_WRITE, handle_handshake, c, NULL);
+	connected_clients++;
 }
 
 static struct client *
 client_by_id(int id)
 {
-	if ((size_t)id > sizeof(clients)/sizeof(clients[0]))
+	struct client *c;
+
+	if ((c = try_client_by_id(id)) == NULL)
 		fatal("in client_by_id: invalid id %d", id);
-	return &clients[id];
+	return c;
 }
 
 struct client *
 try_client_by_id(int id)
 {
-	if ((size_t)id > sizeof(clients)/sizeof(clients[0]))
-                return NULL;
-	return &clients[id];
+	struct client find;
+
+	find.id = id;
+	return SPLAY_FIND(client_tree_id, &clients, &find);
 }
 
 static void
@@ -1423,15 +1424,11 @@ handle_siginfo(int fd, short ev, void *d)
 void
 loop(struct tls *ctx_, int sock4, int sock6, struct imsgbuf *ibuf)
 {
-	size_t i;
-
 	ctx = ctx_;
 
-	event_init();
+	SPLAY_INIT(&clients);
 
-	memset(&clients, 0, sizeof(clients));
-	for (i = 0; i < MAX_USERS; ++i)
-		clients[i].fd = -1;
+	event_init();
 
 	event_set(&e4, sock4, EV_READ | EV_PERSIST, &do_accept, NULL);
 	event_add(&e4, NULL);
@@ -1457,3 +1454,16 @@ loop(struct tls *ctx_, int sock4, int sock6, struct imsgbuf *ibuf)
 	event_dispatch();
 	_exit(0);
 }
+
+int
+client_tree_cmp(struct client *a, struct client *b)
+{
+	if (a->id == b->id)
+		return 0;
+	else if (a->id < b->id)
+		return -1;
+	else
+		return +1;
+}
+
+SPLAY_GENERATE(client_tree_id, client, entry, client_tree_cmp)