Game of Trees Repos

Commit Diff

Commit:: cfe4112187cdecbd49844c80bb337c1671a2d7ab
From:: Stefan Sperling <stsp@stsp.name>
Via:: Thomas Adam <thomas@xteddy.org>
Date:: Sat Oct 16 11:09:49 2021 UTC
Message:: use RB_TREE instead of STAILQ to manage packindex bloom filters; much faster
Actions:: Patch | Tree
commit - 4eaf43871217ec0d5ddda0840af42350cd4048fd
commit + cfe4112187cdecbd49844c80bb337c1671a2d7ab
blob - 14f895c1ec910a384eec39f6e8d68c60ffa65538
blob + 2b173017176381035ce051fd5a542a032ce7ece7
--- lib/fetch.c
+++ lib/fetch.c
@@ -16,6 +16,8 @@
 
 #include <sys/types.h>
 #include <sys/stat.h>
+#include <sys/queue.h>
+#include <sys/tree.h>
 #include <sys/uio.h>
 #include <sys/socket.h>
 #include <sys/wait.h>
blob - 7005ceff4f2d553de11c1201ae67f4e97388b4be
blob + 831cb967da0e76447d97b70ff058416fbf492de4
--- lib/got_lib_repository.h
+++ lib/got_lib_repository.h
@@ -31,14 +31,21 @@
 #define GOT_PACK_CACHE_SIZE	64
 
 struct got_packidx_bloom_filter {
-	char path_packidx[PATH_MAX]; /* on-disk path */
-	size_t path_packidx_len;
+	RB_ENTRY(got_packidx_bloom_filter) entry;
+	char path[PATH_MAX]; /* on-disk path */
+	size_t path_len;
 	struct bloom *bloom;
-	STAILQ_ENTRY(got_packidx_bloom_filter) entry;
 };
 
-STAILQ_HEAD(got_packidx_bloom_filter_head, got_packidx_bloom_filter);
+RB_HEAD(got_packidx_bloom_filter_tree, got_packidx_bloom_filter);
 
+static inline int
+got_packidx_bloom_filter_cmp(const struct got_packidx_bloom_filter *f1,
+    const struct got_packidx_bloom_filter *f2)
+{
+	return got_path_cmp(f1->path, f2->path, f1->path_len, f2->path_len);
+}
+
 struct got_repository {
 	char *path;
 	char *path_git_dir;
@@ -52,7 +59,7 @@ struct got_repository {
 	 * Used to avoid opening a pack index in search of an
 	 * object ID which is not contained in this pack index.
 	 */
-	struct got_packidx_bloom_filter_head packidx_bloom_filters;
+	struct got_packidx_bloom_filter_tree packidx_bloom_filters;
 
 	/* Open file handles for pack files. */
 	struct got_pack packs[GOT_PACK_CACHE_SIZE];
blob - f997c6e8b0b6ca0e1730e6d4660cfef42b2e8ea9
blob + 29ea30e10bd9622eac9d105e0f8999912a726c9d
--- lib/object.c
+++ lib/object.c
@@ -16,6 +16,8 @@
 
 #include <sys/types.h>
 #include <sys/stat.h>
+#include <sys/queue.h>
+#include <sys/tree.h>
 #include <sys/uio.h>
 #include <sys/socket.h>
 #include <sys/wait.h>
blob - 7c6038283aab7c45804ce6b4b6da1f9794b3ec2a
blob + b78b7ba3c8fbd3036ee95c115be0ea37323e9496
--- lib/object_parse.c
+++ lib/object_parse.c
@@ -16,6 +16,8 @@
 
 #include <sys/types.h>
 #include <sys/stat.h>
+#include <sys/queue.h>
+#include <sys/tree.h>
 #include <sys/uio.h>
 #include <sys/socket.h>
 #include <sys/wait.h>
blob - b181dec766f418a030c0b719f55ab0b3e491b0e0
blob + 6ad71896f6f904435d6699beaa3bc9dbcf7d2147
--- lib/pack_create.c
+++ lib/pack_create.c
@@ -16,6 +16,8 @@
  */
 
 #include <sys/types.h>
+#include <sys/queue.h>
+#include <sys/tree.h>
 #include <sys/uio.h>
 #include <sys/stat.h>
 
blob - c6f5465ad763c15f1e6aad591500253352468c39
blob + 39a26086156c2074eb1982a44d103fcf5424f1e1
--- lib/repository.c
+++ lib/repository.c
@@ -15,6 +15,8 @@
  */
 
 #include <sys/types.h>
+#include <sys/queue.h>
+#include <sys/tree.h>
 #include <sys/uio.h>
 #include <sys/socket.h>
 #include <sys/stat.h>
@@ -663,7 +665,7 @@ got_repo_open(struct got_repository **repop, const cha
 		goto done;
 	}
 
-	STAILQ_INIT(&repo->packidx_bloom_filters);
+	RB_INIT(&repo->packidx_bloom_filters);
 
 	for (i = 0; i < nitems(repo->privsep_children); i++) {
 		memset(&repo->privsep_children[i], 0,
@@ -766,10 +768,10 @@ got_repo_close(struct got_repository *repo)
 		got_packidx_close(repo->packidx_cache[i]);
 	}
 
-	while (!STAILQ_EMPTY(&repo->packidx_bloom_filters)) {
-		struct got_packidx_bloom_filter *bf;
-		bf = STAILQ_FIRST(&repo->packidx_bloom_filters);
-		STAILQ_REMOVE_HEAD(&repo->packidx_bloom_filters, entry);
+	while ((bf = RB_MIN(got_packidx_bloom_filter_tree,
+	    &repo->packidx_bloom_filters))) {
+		RB_REMOVE(got_packidx_bloom_filter_tree,
+		    &repo->packidx_bloom_filters, bf);
 		free(bf->bloom);
 		free(bf);
 	}
@@ -999,19 +1001,29 @@ got_repo_is_packidx_filename(const char *name, size_t 
 	return 1;
 }
 
+static struct got_packidx_bloom_filter *
+get_packidx_bloom_filter(struct got_repository *repo,
+    const char *path, size_t path_len)
+{
+	struct got_packidx_bloom_filter key;
+
+	if (strlcpy(key.path, path, sizeof(key.path)) >= sizeof(key.path))
+		return NULL; /* XXX */
+	key.path_len = path_len;
+
+	return RB_FIND(got_packidx_bloom_filter_tree,
+	    &repo->packidx_bloom_filters, &key);
+}
+
 static int
 check_packidx_bloom_filter(struct got_repository *repo,
     const char *path_packidx, struct got_object_id *id)
 {
 	struct got_packidx_bloom_filter *bf;
 
-	STAILQ_FOREACH(bf, &repo->packidx_bloom_filters, entry) {
-		if (got_path_cmp(bf->path_packidx, path_packidx,
-		    bf->path_packidx_len, strlen(path_packidx)) == 0) {
-			return bloom_check(bf->bloom, id->sha1,
-			    sizeof(id->sha1));
-		}
-	}
+	bf = get_packidx_bloom_filter(repo, path_packidx, strlen(path_packidx));
+	if (bf)
+		return bloom_check(bf->bloom, id->sha1, sizeof(id->sha1));
 
 	/* No bloom filter means this pack index must be searched. */
 	return 1;
@@ -1037,11 +1049,9 @@ add_packidx_bloom_filter(struct got_repository *repo,
 		return NULL;
 
 	/* Do we already have a filter for this pack index? */
-	STAILQ_FOREACH(bf, &repo->packidx_bloom_filters, entry) {
-		if (got_path_cmp(bf->path_packidx, path_packidx,
-		    bf->path_packidx_len, strlen(path_packidx)) == 0)
-			return NULL;
-	}
+	if (get_packidx_bloom_filter(repo, path_packidx,
+	    strlen(path_packidx)) != NULL)
+		return NULL;
 
 	bf = calloc(1, sizeof(*bf));
 	if (bf == NULL)
@@ -1052,14 +1062,13 @@ add_packidx_bloom_filter(struct got_repository *repo,
 		return got_error_from_errno("calloc");
 	}
 	
-	
-	len = strlcpy(bf->path_packidx, path_packidx, sizeof(bf->path_packidx));
-	if (len >= sizeof(bf->path_packidx)) {
+	len = strlcpy(bf->path, path_packidx, sizeof(bf->path));
+	if (len >= sizeof(bf->path)) {
 		free(bf->bloom);
 		free(bf);
 		return got_error(GOT_ERR_NO_SPACE);
 	}
-	bf->path_packidx_len = len;
+	bf->path_len = len;
 
 	/* Minimum size supported by our bloom filter is 1000 entries. */
 	bloom_init(bf->bloom, nobjects < 1000 ? 1000 : nobjects, 0.1);
@@ -1069,7 +1078,8 @@ add_packidx_bloom_filter(struct got_repository *repo,
 		bloom_add(bf->bloom, id->sha1, sizeof(id->sha1));
 	}
 
-	STAILQ_INSERT_TAIL(&repo->packidx_bloom_filters, bf, entry);
+	RB_INSERT(got_packidx_bloom_filter_tree,
+	    &repo->packidx_bloom_filters, bf);
 	return NULL;
 }
 
blob - f73c38388a2637a76122e000a939cc43c4314c89
blob + 12174bd21c15a9ea4fa8bd42b3382c936afccd77
--- lib/repository_admin.c
+++ lib/repository_admin.c
@@ -15,6 +15,8 @@
  */
 
 #include <sys/types.h>
+#include <sys/queue.h>
+#include <sys/tree.h>
 #include <sys/uio.h>
 #include <sys/stat.h>
 #include <sys/socket.h>
blob - 9082a982b2d18cfec0e4a2b47e43d39474a99fa2
blob + d983e298afbf41bdaf8560eb6a46db4c9148df0c
--- lib/send.c
+++ lib/send.c
@@ -17,6 +17,8 @@
 
 #include <sys/types.h>
 #include <sys/stat.h>
+#include <sys/queue.h>
+#include <sys/tree.h>
 #include <sys/uio.h>
 #include <sys/socket.h>
 #include <sys/wait.h>