commit 0be8fa4c11ab3b1e2c7f93a8d8649c885cd72d28 from: Stefan Sperling via: Thomas Adam date: Fri Oct 15 19:22:03 2021 UTC use RB_TREE instead of STAILQ to manage packindex bloom filters; much faster commit - 40d16f06b477a3e4552e99de8ec91bce62125c6b commit + 0be8fa4c11ab3b1e2c7f93a8d8649c885cd72d28 blob - 14f895c1ec910a384eec39f6e8d68c60ffa65538 blob + 2b173017176381035ce051fd5a542a032ce7ece7 --- lib/fetch.c +++ lib/fetch.c @@ -16,6 +16,8 @@ #include #include +#include +#include #include #include #include blob - d12c1d0d2ac9ef2b17d24062220b1f89c1f7ae78 blob + b99fe9fe68c49923f58a4b5c45969f4bbcded942 --- 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 - f9d1969b15f4cb43862b7013f35e7485fea9e8b5 blob + a2a77eec3583a812ce8b2b1da88c1970e30fb163 --- lib/object.c +++ lib/object.c @@ -16,6 +16,8 @@ #include #include +#include +#include #include #include #include blob - 1dc86652038f22a8bbfaad63930eb197d314c21b blob + cb9e1e66b8b4e4c2db906ac6472f37b6af5c7487 --- lib/object_parse.c +++ lib/object_parse.c @@ -16,6 +16,8 @@ #include #include +#include +#include #include #include #include blob - c0d6e28feff22e3c6f2c9901d5faf98218b9eab2 blob + 55f61382d4f074d706dc6d052fd5df1313c5b78d --- lib/pack_create.c +++ lib/pack_create.c @@ -16,6 +16,8 @@ */ #include +#include +#include #include #include @@ -29,6 +31,7 @@ #include "got_error.h" #include "got_cancel.h" #include "got_object.h" +#include "got_path.h" #include "got_reference.h" #include "got_repository_admin.h" blob - 38d61ae41b5d5e94177f872aefb961dbaaf3a579 blob + ece760d04d7554cbe9da184cb110afd48bddff28 --- lib/repository.c +++ lib/repository.c @@ -15,6 +15,8 @@ */ #include +#include +#include #include #include #include @@ -61,6 +63,9 @@ #ifndef nitems #define nitems(_a) (sizeof(_a) / sizeof((_a)[0])) #endif + +RB_PROTOTYPE(got_packidx_bloom_filter_tree, got_packidx_bloom_filter, entry, + got_packidx_bloom_filter_cmp); const char * got_repo_get_path(struct got_repository *repo) @@ -633,7 +638,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, @@ -723,6 +728,7 @@ const struct got_error * got_repo_close(struct got_repository *repo) { const struct got_error *err = NULL, *child_err; + struct got_packidx_bloom_filter *bf; size_t i; for (i = 0; i < repo->pack_cache_size; i++) { @@ -731,10 +737,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); } @@ -963,19 +969,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; @@ -1001,11 +1017,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) @@ -1016,14 +1030,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); @@ -1033,7 +1046,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; } @@ -2125,3 +2139,6 @@ done: } return err; } + +RB_GENERATE(got_packidx_bloom_filter_tree, got_packidx_bloom_filter, entry, + got_packidx_bloom_filter_cmp); blob - f73c38388a2637a76122e000a939cc43c4314c89 blob + 12174bd21c15a9ea4fa8bd42b3382c936afccd77 --- lib/repository_admin.c +++ lib/repository_admin.c @@ -15,6 +15,8 @@ */ #include +#include +#include #include #include #include blob - 9082a982b2d18cfec0e4a2b47e43d39474a99fa2 blob + d983e298afbf41bdaf8560eb6a46db4c9148df0c --- lib/send.c +++ lib/send.c @@ -17,6 +17,8 @@ #include #include +#include +#include #include #include #include