From 04bf7a9a3bf7814e3218b6dbccc00aefb4b0d4ae Mon Sep 17 00:00:00 2001
From: Egor <egor@patchysicp.xyz>
Date: Sun, 22 Oct 2023 18:46:21 +0300
Subject: [PATCH] add alternative map impl, fix some memory leaks

---
 Makefile            |  35 ++++++------
 libtls.suppressions |   8 +++
 src/common.h        |  34 +++++++-----
 src/irc.c           |  67 ++++++++++++-----------
 src/irc.h           |   1 +
 src/main.c          |  13 +++++
 src/map_dynarr.c    | 130 ++++++++++++++++++++++++++++++++++++++++++++
 src/map_dynarr.h    |  24 ++++++++
 src/net.c           |  14 +++--
 src/trie.c          |   8 +--
 src/trie.h          |   9 +--
 vg                  |   2 +
 12 files changed, 267 insertions(+), 78 deletions(-)
 create mode 100644 libtls.suppressions
 create mode 100644 src/map_dynarr.c
 create mode 100644 src/map_dynarr.h
 create mode 100755 vg

diff --git a/Makefile b/Makefile
index fe50f38..a964cf9 100644
--- a/Makefile
+++ b/Makefile
@@ -1,24 +1,25 @@
 TARGET := ircd
 SOURCES := \
-	src/main.c    \
-	src/irc.c     \
-	src/ircfmt.c  \
-	src/net.c     \
-	src/netpoll.c \
-	src/netsock.c \
-	src/passwd.c  \
-	src/trie.c    \
+	src/main.c       \
+	src/irc.c        \
+	src/ircfmt.c     \
+	src/net.c        \
+	src/netpoll.c    \
+	src/netsock.c    \
+	src/passwd.c     \
 	src/util.c
+SOURCES += src/trie.c
 HEADERS := \
-	src/common.h  \
-	src/config.h  \
-	src/irc.h     \
-	src/ircfmt.h  \
-	src/net.h     \
-	src/netpoll.h \
-	src/netsock.h \
-	src/passwd.h  \
-	src/trie.h    \
+	src/common.h     \
+	src/config.h     \
+	src/irc.h        \
+	src/ircfmt.h     \
+	src/net.h        \
+	src/netpoll.h    \
+	src/netsock.h    \
+	src/passwd.h     \
+	src/trie.h       \
+	src/map_dynarr.h \
 	src/util.h
 
 -include config.mk
diff --git a/libtls.suppressions b/libtls.suppressions
new file mode 100644
index 0000000..21be759
--- /dev/null
+++ b/libtls.suppressions
@@ -0,0 +1,8 @@
+{
+   <tls_init>
+   Memcheck:Leak
+   match-leak-kinds: reachable
+   ...
+   fun:tls_init
+   fun:main
+}
diff --git a/src/common.h b/src/common.h
index b7209c6..12da8c8 100644
--- a/src/common.h
+++ b/src/common.h
@@ -3,7 +3,11 @@
 #include "netsock.h"
 #include "netpoll.h"
 #include "config.h"
+#ifdef USE_MAP_DYNARR
+#include "map_dynarr.h"
+#else
 #include "trie.h"
+#endif
 #include <time.h>
 #ifdef HAS_TLS
 #include <tls.h>
@@ -48,8 +52,8 @@ struct client_data {
 	size_t wbufLen;
 	char   umode;
 	char   regstate;
-	struct trie_node *channels;
-	struct trie_node *invites;
+	map_t  channels;
+	map_t  invites;
 	int    cookie;
 	time_t signon;
 	time_t lastactivity;
@@ -70,18 +74,18 @@ struct channel {
 	char *topic_who;
 	time_t topic_when;
 	time_t creation;
-	struct trie_node *members;
-	struct trie_node *o;
-	struct trie_node *v;
+	map_t members;
+	map_t o;
+	map_t v;
 	int member_count;
 	char dmode;
-	struct trie_node *listb;
-	struct trie_node *liste;
-	struct trie_node *listI;
-	struct trie_node *listq;
-	struct trie_node *listwo;
-	struct trie_node *listwv;
-	struct trie_node *invitees;
+	map_t listb;
+	map_t liste;
+	map_t listI;
+	map_t listq;
+	map_t listwo;
+	map_t listwv;
+	map_t invitees;
 	char *chankey;
 	int member_limit;
 };
@@ -93,9 +97,9 @@ struct channel {
 #define DMODE_TOPICPROT 32
 #define is_chanop(chan, client) (!!trie_get(&(chan)->o, (client)->key))
 #define is_chanvoice(chan, client) (!!trie_get(&(chan)->v, (client)->key))
-extern struct trie_node *client_map;
-extern struct trie_node *channel_map;
-extern struct trie_node *autojoin;
+extern map_t client_map;
+extern map_t channel_map;
+extern map_t autojoin;
 extern struct client_data  *clients;
 extern struct client_data  *dyingclients;
 
diff --git a/src/irc.c b/src/irc.c
index dc03c14..dd4f3c7 100644
--- a/src/irc.c
+++ b/src/irc.c
@@ -4,9 +4,9 @@
 
 struct dynarr databuf;
 
-struct trie_node *client_map = NULL;
-struct trie_node *channel_map = NULL;
-struct trie_node *autojoin = NULL;
+map_t client_map = {0};
+map_t channel_map = {0};
+map_t autojoin = {0};
 
 const char *hostname = IRCDHOSTNAME;
 #define is_registered(cl) ((cl)->regstate == REG_REGISTERED)
@@ -39,7 +39,7 @@ void sendbuf_chan_caps(struct channel *chan, unsigned positive, unsigned negativ
 void sendbuf_chan(struct channel *chan) {
 	sendbuf_chan_caps(chan, 0, 0);
 }
-void sendbuf_list_sans_self_caps(struct client_data *client, struct trie_node **ls, int cookie, int positive, int negative) {
+void sendbuf_list_sans_self_caps(struct client_data *client, map_t *ls, int cookie, int positive, int negative) {
 	struct trie_find *f = NULL;
 	if (trie_findfirst(&f, ls) == 1)
 		do {
@@ -56,7 +56,7 @@ void sendbuf_list_sans_self_caps(struct client_data *client, struct trie_node **
 			}
 		} while (trie_findnext(&f) == 1);
 }
-void sendbuf_list_sans_self(struct client_data *client, struct trie_node **ls, int cookie) {
+void sendbuf_list_sans_self(struct client_data *client, map_t *ls, int cookie) {
 	sendbuf_list_sans_self_caps(client, ls, cookie, 0, 0);
 }
 int get_cookie() {
@@ -98,7 +98,7 @@ const char *format_umodes(struct client_data *cl) {
 	*p++ = '\0';
 	return umodes;
 }
-int match_list(struct client_data *cl, struct trie_node **list)
+int match_list(struct client_data *cl, map_t *list)
 {
 	struct trie_find *f = NULL;
 	if (trie_findfirst(&f, list) == 1)
@@ -796,7 +796,7 @@ int processPacket(struct client_data *client, char *source, char *command, int a
 					case '-': is_plus = 0; break;
 					default: goto unknown;
 				}
-				struct trie_node **list;
+				map_t *list;
 				char **argp = &args[2];
 				while (*p) {
 					switch (*p) {
@@ -1370,31 +1370,34 @@ void channel_part(struct client_data *client, struct channel *chan, const char *
 	trie_set(&chan->o, client->key, NULL, NULL);
 	trie_set(&chan->v, client->key, NULL, NULL);
 	chan->member_count--;
-	if (!chan->member_count && !(chan->dmode & DMODE_PERSIST)) {
-		trie_set(&channel_map, chan->key, NULL, NULL);
-		struct trie_find *f = NULL;
-		if (trie_findfirst(&f, &chan->invitees) == 1)
-			do {
-				struct client_data *cl = f->n->value;
-				trie_set(&cl->invites, chan->key, NULL, NULL);
-			} while(trie_findnext(&f) == 1);
-		free(chan->key);
-		free(chan->name);
-		free(chan->topic);
-		free(chan->topic_who);
-		trie_free(&chan->members);
-		trie_free(&chan->o);
-		trie_free(&chan->v);
-		trie_free(&chan->listb);
-		trie_free(&chan->liste);
-		trie_free(&chan->listI);
-		trie_free(&chan->listq);
-		trie_free(&chan->listwo);
-		trie_free(&chan->listwv);
-		trie_free(&chan->invitees);
-		free(chan->chankey);
-		free(chan);
-	}
+	if (!chan->member_count && !(chan->dmode & DMODE_PERSIST))
+		channel_kill(chan);
+}
+void channel_kill(struct channel *chan)
+{
+	trie_set(&channel_map, chan->key, NULL, NULL);
+	struct trie_find *f = NULL;
+	if (trie_findfirst(&f, &chan->invitees) == 1)
+		do {
+			struct client_data *cl = f->n->value;
+			trie_set(&cl->invites, chan->key, NULL, NULL);
+		} while(trie_findnext(&f) == 1);
+	free(chan->key);
+	free(chan->name);
+	free(chan->topic);
+	free(chan->topic_who);
+	trie_free(&chan->members);
+	trie_free(&chan->o);
+	trie_free(&chan->v);
+	trie_free(&chan->listb);
+	trie_free(&chan->liste);
+	trie_free(&chan->listI);
+	trie_free(&chan->listq);
+	trie_free(&chan->listwo);
+	trie_free(&chan->listwv);
+	trie_free(&chan->invitees);
+	free(chan->chankey);
+	free(chan);
 }
 struct client_data *findClient(const char *nickname)
 {
diff --git a/src/irc.h b/src/irc.h
index 0a3ada2..9272c82 100644
--- a/src/irc.h
+++ b/src/irc.h
@@ -17,5 +17,6 @@ void channel_sendtopic(struct client_data *client, struct channel *chan, int joi
 void channel_sendnames(struct client_data *client, struct channel *chan);
 void channel_join(struct client_data *client, const char *channel, const char *chankey);
 void channel_part(struct client_data *client, struct channel *chan, const char *reason, struct client_data *kicker);
+void channel_kill(struct channel *chan);
 extern struct dynarr databuf;
 #endif
diff --git a/src/main.c b/src/main.c
index 3a36e1f..60c0a10 100644
--- a/src/main.c
+++ b/src/main.c
@@ -417,6 +417,19 @@ int main(int argc, char *argv[])
 	tls_free(tls_ctx);
 #endif
 	free(databuf.buf);
+	/* free any persisten channels */
+	{
+		struct trie_find *f = NULL;
+		while (trie_findfirst(&f, &channel_map) == 1) {
+			struct channel *chan = f->n->value;
+			channel_kill(chan);
+		}
+		free(f);
+	}
+	trie_free(&client_map);
+	trie_free(&channel_map);
 	trie_free(&autojoin);
+	if (fchanlog)
+		fclose(fchanlog);
 	return 0;
 }
diff --git a/src/map_dynarr.c b/src/map_dynarr.c
new file mode 100644
index 0000000..06fa881
--- /dev/null
+++ b/src/map_dynarr.c
@@ -0,0 +1,130 @@
+#include "map_dynarr.h"
+#include <stdlib.h>
+#include <string.h>
+static int ent_find(map_t *root, const char *key, int *found)
+{
+	int lo = 0;
+	int hi = root->len;
+	while (lo != hi) {
+		int mid = (lo+hi)/2;
+		int cmp = strcmp(root->ptr[mid].key, key);
+		if (cmp == 0) {
+			*found = 1;
+			return mid;
+		} if (cmp > 0) {
+			hi = mid;
+		} else {
+			lo = mid+1;
+		}
+	}
+	*found = 0;
+	return lo;
+}
+void *trie_get(map_t *root, const char *key)
+{
+	int found;
+	int i = ent_find(root, key, &found);
+	return found ? root->ptr[i].value : 0;
+}
+int trie_set(map_t *root, const char *key, const void *value, void **oldvalue)
+{
+	int found;
+	int i = ent_find(root, key, &found);
+	if (found) {
+		if (oldvalue)
+			*oldvalue = root->ptr[i].value;
+		if (!value) {
+			free(root->ptr[i].key);
+			memmove(root->ptr+i, root->ptr+i+1, sizeof(struct map_dynarr_value)*(root->len-(i+1)));
+			root->len--;
+		} else {
+			root->ptr[i].value = (void *)value;
+		}
+	} else {
+		if (oldvalue)
+			*oldvalue = 0;
+		if (value) {
+			if (root->len == root->cap) {
+				int ncap = root->cap ? root->cap*2 : 2;
+				struct map_dynarr_value *nptr = realloc(root->ptr, sizeof(struct map_dynarr_value)*ncap);
+				if (!nptr)
+					return -1;
+				root->ptr = nptr;
+				root->cap = ncap;
+			}
+			int slen = strlen(key)+1;
+			char *nkey = malloc(slen);
+			if (!nkey)
+				return -1;
+			memcpy(nkey, key, slen);
+			memmove(root->ptr+i+1, root->ptr+i, sizeof(struct map_dynarr_value)*(root->len-i));
+			root->len++;
+			root->ptr[i].key = nkey;
+			root->ptr[i].value = (void *)value;
+		}
+	}
+	return 0;
+}
+void trie_free(map_t *root)
+{
+	while (root->len) {
+		free(root->ptr[--root->len].key);
+	}
+	free(root->ptr);
+	root->ptr = 0;
+	root->len = root->cap = 0;
+}
+static int fill(struct trie_find **pf, int index)
+{
+	struct trie_find *f = *pf;
+	int keylen = strlen(f->_root->ptr[index].key)+1;
+	if (keylen > f->_cap) {
+		while (keylen > f->_cap)
+			f->_cap *= 2;
+		struct trie_find *nf = realloc(f, sizeof(struct trie_find)+f->_cap);
+		if (!nf) {
+			*pf = 0;
+			free(f);
+			return -1;
+		}
+		*pf = f = nf;
+		f->key = (char*)&f[1];
+		f->n = &f->_n;
+	}
+	memcpy(f->key, f->_root->ptr[index].key, keylen);
+	f->n->value = f->_root->ptr[index].value;
+	return 1;
+}
+int trie_findfirst(struct trie_find **pf, map_t *root)
+{
+	if (!root->len)
+		return 0;
+	struct trie_find *f;
+	if (!*pf) {
+		f = malloc(sizeof(struct trie_find)+32);
+		if (!f)
+			return -1;
+		f->key = (char*)&f[1];
+		f->key[0] = 0;
+		f->n = &f->_n;
+		f->_cap = 32;
+		*pf = f;
+	} else {
+		f = *pf;
+	}
+	f->_root = root;
+	return fill(pf, 0);
+}
+int trie_findnext(struct trie_find **pf)
+{
+	struct trie_find *f = *pf;
+	int found;
+	int i = ent_find(f->_root, f->key, &found);
+	i += found;
+	if (f->_root->len == (size_t)i) {
+		*pf = 0;
+		free(f);
+		return 0;
+	}
+	return fill(pf, i);
+}
diff --git a/src/map_dynarr.h b/src/map_dynarr.h
new file mode 100644
index 0000000..eba2332
--- /dev/null
+++ b/src/map_dynarr.h
@@ -0,0 +1,24 @@
+#ifndef MAP_DYNARR_H_
+#define MAP_DYNARR_H_
+#include <stddef.h>
+struct map_dynarr_value {
+	char *key;
+	void *value;
+};
+struct map_dynarr {
+	struct map_dynarr_value *ptr;
+	size_t len, cap;
+};
+typedef struct map_dynarr map_t;
+void *trie_get(map_t *root, const char *key);
+int trie_set(map_t *root, const char *key, const void *value, void **oldvalue);
+void trie_free(map_t *root);
+struct trie_find {
+	char *key;
+	struct { void *value; } *n, _n;
+	map_t *_root;
+	int _cap;
+};
+int trie_findfirst(struct trie_find **pf, map_t *root);
+int trie_findnext(struct trie_find **pf);
+#endif
diff --git a/src/net.c b/src/net.c
index 347dfe6..83d90db 100644
--- a/src/net.c
+++ b/src/net.c
@@ -65,12 +65,12 @@ void killConnection(struct client_data *cl, int byChoice)
 	update_poll_reg(cl);
 	/* Part all channels */
 	struct trie_find *f = NULL;
-	if (trie_findfirst(&f, &cl->channels) == 1)
-		do {
-			struct channel *chan = f->n->value;
-			channel_part(cl, chan, NULL, NULL);
-		} while(trie_findfirst(&f, &cl->channels) == 1);
-	/* Get rid of the pending invites */
+	while (trie_findfirst(&f, &cl->channels) == 1) {
+		struct channel *chan = f->n->value;
+		channel_part(cl, chan, NULL, NULL);
+	}
+	free(f);
+	/* Remove from client_map and get rid of the pending invites */
 	if (cl->key) {
 		trie_set(&client_map, cl->key, NULL, NULL);
 		struct trie_find *f = NULL;
@@ -80,6 +80,8 @@ void killConnection(struct client_data *cl, int byChoice)
 				trie_set(&chan->invitees, cl->key, NULL, NULL);
 			} while(trie_findnext(&f) == 1);
 	}
+	trie_free(&cl->channels);
+	trie_free(&cl->invites);
 	killConnectionPart2(cl);
 }
 void killConnectionPart2(struct client_data *cl)
diff --git a/src/trie.c b/src/trie.c
index efb7fa9..630a172 100644
--- a/src/trie.c
+++ b/src/trie.c
@@ -26,7 +26,7 @@ static int ent_find(struct trie_node *n, int key)
 	return lo;
 }
 // get value from trie O(n log s)
-void *trie_get(struct trie_node **root, const char *key)
+void *trie_get(map_t *root, const char *key)
 {
 	struct trie_node *n = *root;
 	if (!n)
@@ -41,7 +41,7 @@ void *trie_get(struct trie_node **root, const char *key)
 	return n->value;
 }
 // set value in trie O(ns)
-int trie_set(struct trie_node **root, const char *key, const void *value, void **oldvalue)
+int trie_set(map_t *root, const char *key, const void *value, void **oldvalue)
 {
 	int rv = 0;
 	if (oldvalue)
@@ -119,7 +119,7 @@ cleanup:
 	return rv;
 }
 // free a trie
-void trie_free(struct trie_node **root) {
+void trie_free(map_t *root) {
 	struct trie_node *n = *root;
 	while (n) {
 		if (n->len) {
@@ -165,7 +165,7 @@ int trie_findnext(struct trie_find **pf) {
 		}
 	}
 }
-int trie_findfirst(struct trie_find **pf, struct trie_node **root) {
+int trie_findfirst(struct trie_find **pf, map_t *root) {
 	if (!*root)
 		return 0;
 	struct trie_find *f;
diff --git a/src/trie.h b/src/trie.h
index 513f496..ef21dbd 100644
--- a/src/trie.h
+++ b/src/trie.h
@@ -13,19 +13,20 @@ struct trie_node {
 	struct trie_node *parent;
 	struct trie_node *data[1];
 };
+typedef struct trie_node *map_t;
 // get value from trie O(n log s)
-void *trie_get(struct trie_node **root, const char *key);
+void *trie_get(map_t *root, const char *key);
 // set value in trie O(ns)
-int trie_set(struct trie_node **root, const char *key, const void *value, void **oldvalue);
+int trie_set(map_t *root, const char *key, const void *value, void **oldvalue);
 // free a trie
-void trie_free(struct trie_node **root);
+void trie_free(map_t *root);
 struct trie_find {
 	struct trie_node *n;
 	size_t len;
 	size_t cap;
 	char key[1];
 };
-int trie_findfirst(struct trie_find **pf, struct trie_node **root);
+int trie_findfirst(struct trie_find **pf, map_t *root);
 int trie_findnext(struct trie_find **pf);
 #ifdef __cplusplus
 }
diff --git a/vg b/vg
new file mode 100755
index 0000000..8136e72
--- /dev/null
+++ b/vg
@@ -0,0 +1,2 @@
+#!/bin/sh
+exec valgrind --leak-check=full --show-leak-kinds=all -s --suppressions=libtls.suppressions ./ircd
-- 
2.56.0