commit eb77ee116adf68529f88c2ab3de1ce2aaf0c1b52 from: Stefan Sperling date: Sun Jul 08 16:06:36 2018 UTC add an object id cache which backs the object cache commit - 60f2eee18fcaff9bd6983122f15e71afa79ab46e commit + eb77ee116adf68529f88c2ab3de1ce2aaf0c1b52 blob - 4ca05ec8487753b03115ac175e8878dac1c78bcb blob + 8c76a73674eff72a0574331795351df57050510c --- got/Makefile +++ got/Makefile @@ -2,8 +2,8 @@ PROG= got SRCS= got.c blame.c commit_graph.c delta.c diff.c diffreg.c error.c \ - fileindex.c object.c object_idset.c opentemp.c path.c \ - pack.c privsep.c reference.c repository.c sha1.c \ + fileindex.c object.c object_idcache.c object_idset.c opentemp.c \ + path.c pack.c privsep.c reference.c repository.c sha1.c \ worktree.c zbuf.c CPPFLAGS = -I${.CURDIR}/../include -I${.CURDIR}/../lib blob - /dev/null blob + 79206665203625b474ebdbb75bc88916a1593301 (mode 644) --- /dev/null +++ lib/got_lib_object_idcache.h @@ -0,0 +1,31 @@ +/* + * Copyright (c) 2018 Stefan Sperling + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +struct got_object_idcache; + +struct got_object_idcache *got_object_idcache_alloc(int); +void got_object_idcache_free(struct got_object_idcache *); + +const struct got_error *got_object_idcache_add(struct got_object_idcache *, + struct got_object_id *, void *); +void *got_object_idcache_get(struct got_object_idcache *, struct got_object_id *); +const struct got_error *got_object_idcache_remove_least_used(void **, + struct got_object_idcache *); +int got_object_idcache_contains(struct got_object_idcache *, + struct got_object_id *); +void got_object_idcache_for_each(struct got_object_idcache *, + void (*cb)(struct got_object_id *, void *, void *), void *); +int got_object_idcache_num_elements(struct got_object_idcache *); blob - 203dd23f75b193d6dc458dc139f85bca240aa676 blob + 24122e83d302d604ba05b7698aaad60bc5ea8e16 --- lib/got_lib_repository.h +++ lib/got_lib_repository.h @@ -38,7 +38,7 @@ struct got_object_cache_entry { struct got_object_cache { enum got_object_chache_type type; - struct got_object_idset *set; + struct got_object_idcache *idcache; size_t size; int cache_hit; int cache_miss; blob - /dev/null blob + 2c206beb86a5cae32d59676d22db74b24023fb64 (mode 644) --- /dev/null +++ lib/object_idcache.c @@ -0,0 +1,170 @@ +/* + * Copyright (c) 2018 Stefan Sperling + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include + +#include +#include +#include +#include +#include +#include +#include + +#include "got_object.h" +#include "got_error.h" + +#include "got_lib_delta.h" +#include "got_lib_zbuf.h" +#include "got_lib_object.h" +#include "got_lib_object_idcache.h" + +#ifndef nitems +#define nitems(_a) (sizeof(_a) / sizeof((_a)[0])) +#endif + +struct got_object_idcache_element { + TAILQ_ENTRY(got_object_idcache_element) entry; + struct got_object_id id; + void *data; /* API user data */ +}; + +TAILQ_HEAD(got_object_idcache_head, got_object_idcache_element); + +struct got_object_idcache { + struct got_object_idcache_head entries; + int nelem; + int maxelem; +}; + +struct got_object_idcache * +got_object_idcache_alloc(int maxelem) +{ + struct got_object_idcache *cache; + + cache = calloc(1, sizeof(*cache)); + if (cache == NULL) + return NULL; + + TAILQ_INIT(&cache->entries); + cache->maxelem = maxelem; + return cache; +} + +void +got_object_idcache_free(struct got_object_idcache *cache) +{ + struct got_object_idcache_element *entry; + + while (!TAILQ_EMPTY(&cache->entries)) { + entry = TAILQ_FIRST(&cache->entries); + TAILQ_REMOVE(&cache->entries, entry, entry); + /* User data should be freed by caller. */ + free(entry); + } + free(cache); +} + +const struct got_error * +got_object_idcache_add(struct got_object_idcache *cache, + struct got_object_id *id, void *data) +{ + struct got_object_idcache_element *entry; + + if (cache->nelem >= cache->maxelem) { + entry = TAILQ_LAST(&cache->entries, got_object_idcache_head); + TAILQ_REMOVE(&cache->entries, entry, entry); + cache->nelem--; + } + + entry = calloc(1, sizeof(*entry)); + if (entry == NULL) + return got_error_from_errno(); + + memcpy(&entry->id, id, sizeof(entry->id)); + entry->data = data; + + TAILQ_INSERT_HEAD(&cache->entries, entry, entry); + cache->nelem++; + return NULL; +} + +void * +got_object_idcache_get(struct got_object_idcache *cache, struct got_object_id *id) +{ + struct got_object_idcache_element *entry; + + TAILQ_FOREACH(entry, &cache->entries, entry) { + if (got_object_id_cmp(&entry->id, id) != 0) + continue; + if (entry != TAILQ_FIRST(&cache->entries)) { + TAILQ_REMOVE(&cache->entries, entry, entry); + TAILQ_INSERT_HEAD(&cache->entries, entry, entry); + } + return entry->data; + } + + return NULL; +} + +const struct got_error * +got_object_idcache_remove_least_used(void **data, struct got_object_idcache *cache) +{ + struct got_object_idcache_element *entry; + + if (data) + *data = NULL; + + if (cache->nelem == 0) + return got_error(GOT_ERR_NO_OBJ); + + entry = TAILQ_LAST(&cache->entries, got_object_idcache_head); + TAILQ_REMOVE(&cache->entries, entry, entry); + if (data) + *data = entry->data; + free(entry); + cache->nelem--; + return NULL; +} + +int +got_object_idcache_contains(struct got_object_idcache *cache, + struct got_object_id *id) +{ + struct got_object_idcache_element *entry; + + TAILQ_FOREACH(entry, &cache->entries, entry) { + if (got_object_id_cmp(&entry->id, id) == 0) + return 1; + } + + return 0; +} + +void got_object_idcache_for_each(struct got_object_idcache *cache, + void (*cb)(struct got_object_id *, void *, void *), void *arg) +{ + struct got_object_idcache_element *entry; + + TAILQ_FOREACH(entry, &cache->entries, entry) + cb(&entry->id, entry->data, arg); +} + +int +got_object_idcache_num_elements(struct got_object_idcache *set) +{ + return set->nelem; +} blob - 9f2643e160d80e60579fdc434640f570194ec4ca blob + 02939023000c3b4ff481dcc502717377033f97e7 --- lib/repository.c +++ lib/repository.c @@ -37,7 +37,7 @@ #include "got_lib_pack.h" #include "got_lib_repository.h" #include "got_lib_worktree.h" -#include "got_lib_object_idset.h" +#include "got_lib_object_idcache.h" #ifndef nitems #define nitems(_a) (sizeof(_a) / sizeof((_a)[0])) @@ -156,10 +156,10 @@ cache_add(struct got_object_cache *cache, struct got_o struct got_object_cache_entry *ce; int nelem; - nelem = got_object_idset_num_elements(cache->set); + nelem = got_object_idcache_num_elements(cache->idcache); if (nelem >= cache->size) { - err = got_object_idset_remove_random((void **)&ce, - cache->set); + err = got_object_idcache_remove_least_used((void **)&ce, + cache->idcache); if (err) return err; switch (cache->type) { @@ -191,7 +191,7 @@ cache_add(struct got_object_cache *cache, struct got_o ce->data.commit = (struct got_commit_object *)item; break; } - err = got_object_idset_add(NULL, cache->set, id, ce); + err = got_object_idcache_add(cache->idcache, id, ce); if (err) { if (err->code == GOT_ERR_OBJ_EXISTS) { free(ce); @@ -222,7 +222,7 @@ got_repo_get_cached_object(struct got_repository *repo { struct got_object_cache_entry *ce; - ce = got_object_idset_get(repo->objcache.set, id); + ce = got_object_idcache_get(repo->objcache.idcache, id); if (ce) { repo->objcache.cache_hit++; return ce->data.obj; @@ -252,7 +252,7 @@ got_repo_get_cached_tree(struct got_repository *repo, { struct got_object_cache_entry *ce; - ce = got_object_idset_get(repo->treecache.set, id); + ce = got_object_idcache_get(repo->treecache.idcache, id); if (ce) { repo->treecache.cache_hit++; return ce->data.tree; @@ -282,7 +282,7 @@ got_repo_get_cached_commit(struct got_repository *repo { struct got_object_cache_entry *ce; - ce = got_object_idset_get(repo->commitcache.set, id); + ce = got_object_idcache_get(repo->commitcache.idcache, id); if (ce) { repo->commitcache.cache_hit++; return ce->data.commit; @@ -312,29 +312,31 @@ got_repo_open(struct got_repository **ret, const char goto done; } - repo->objcache.set = got_object_idset_alloc(); - if (repo->objcache.set == NULL) { - err = got_error_from_errno(); - goto done; - } repo->objcache.type = GOT_OBJECT_CACHE_TYPE_OBJ; repo->objcache.size = GOT_OBJECT_CACHE_SIZE_OBJ; - - repo->treecache.set = got_object_idset_alloc(); - if (repo->treecache.set == NULL) { + repo->objcache.idcache = got_object_idcache_alloc(repo->objcache.size); + if (repo->objcache.idcache == NULL) { err = got_error_from_errno(); goto done; } + repo->treecache.type = GOT_OBJECT_CACHE_TYPE_TREE; repo->treecache.size = GOT_OBJECT_CACHE_SIZE_TREE; - - repo->commitcache.set = got_object_idset_alloc(); - if (repo->commitcache.set == NULL) { + repo->treecache.idcache = + got_object_idcache_alloc(repo->treecache.size); + if (repo->treecache.idcache == NULL) { err = got_error_from_errno(); goto done; } + repo->commitcache.type = GOT_OBJECT_CACHE_TYPE_COMMIT; repo->commitcache.size = GOT_OBJECT_CACHE_SIZE_COMMIT; + repo->commitcache.idcache = + got_object_idcache_alloc(repo->commitcache.size); + if (repo->commitcache.idcache == NULL) { + err = got_error_from_errno(); + goto done; + } repo->path = got_path_normalize(abspath); if (repo->path == NULL) { @@ -395,8 +397,8 @@ static void print_cache_stats(struct got_object_cache *cache, const char *name) { fprintf(stderr, "%s cache: %d elements, %d hits, %d missed\n", - name, got_object_idset_num_elements(cache->set), cache->cache_hit, - cache->cache_miss); + name, got_object_idcache_num_elements(cache->idcache), + cache->cache_hit, cache->cache_miss); } void check_refcount(struct got_object_id *id, void *data, void *arg) @@ -462,19 +464,19 @@ got_repo_close(struct got_repository *repo) print_cache_stats(&repo->objcache, "object"); print_cache_stats(&repo->treecache, "tree"); print_cache_stats(&repo->commitcache, "commit"); - got_object_idset_for_each(repo->objcache.set, check_refcount, + got_object_idcache_for_each(repo->objcache.idcache, check_refcount, &repo->objcache); - got_object_idset_for_each(repo->treecache.set, check_refcount, + got_object_idcache_for_each(repo->treecache.idcache, check_refcount, &repo->treecache); - got_object_idset_for_each(repo->commitcache.set, check_refcount, + got_object_idcache_for_each(repo->commitcache.idcache, check_refcount, &repo->commitcache); #endif - if (repo->objcache.set) - got_object_idset_free(repo->objcache.set); - if (repo->treecache.set) - got_object_idset_free(repo->treecache.set); - if (repo->commitcache.set) - got_object_idset_free(repo->commitcache.set); + if (repo->objcache.idcache) + got_object_idcache_free(repo->objcache.idcache); + if (repo->treecache.idcache) + got_object_idcache_free(repo->treecache.idcache); + if (repo->commitcache.idcache) + got_object_idcache_free(repo->commitcache.idcache); free(repo); } blob - 957eacee13af6f70b82176c5e8ef18cfd848f6f1 blob + 7b2e4c1cc0f0fdf61d47bafcc829ab5a949db6df --- regress/idset/Makefile +++ regress/idset/Makefile @@ -3,7 +3,7 @@ PROG = idset_test SRCS = error.c object.c privsep.c sha1.c pack.c zbuf.c path.c opentemp.c \ delta.c repository.c reference.c worktree.c fileindex.c \ - object_idset.c idset_test.c + object_idcache.c object_idset.c idset_test.c CPPFLAGS = -I${.CURDIR}/../../include -I${.CURDIR}/../../lib LDADD = -lutil -lz blob - f8b2b59598ba8b5bcd3cd5ba387f87af186e03d2 blob + c8f2d7e9d3b04208321ffaa6a29020d7b147e132 --- regress/repository/Makefile +++ regress/repository/Makefile @@ -1,9 +1,9 @@ .PATH:${.CURDIR}/../../lib PROG = repository_test -SRCS = path.c repository.c error.c reference.c object.c object_idset.c \ - opentemp.c sha1.c diff.c diffreg.c pack.c privsep.c delta.c \ - fileindex.c worktree.c zbuf.c repository_test.c +SRCS = path.c repository.c error.c reference.c object.c object_idcache.c \ + object_idset.c opentemp.c sha1.c diff.c diffreg.c pack.c privsep.c \ + delta.c fileindex.c worktree.c zbuf.c repository_test.c CPPFLAGS = -I${.CURDIR}/../../include -I${.CURDIR}/../../lib LDADD = -lutil -lz blob - 90487491477b18e37724fd9a9abd505fb267ecf5 blob + 4c90c64fc7ae7d0c6e12a7cfcd6aae6e59a22245 --- regress/worktree/Makefile +++ regress/worktree/Makefile @@ -1,9 +1,9 @@ .PATH:${.CURDIR}/../../lib PROG = worktree_test -SRCS = worktree.c repository.c object.c object_idset.c opentemp.c path.c \ - error.c reference.c sha1.c pack.c privsep.c delta.c zbuf.c \ - fileindex.c worktree_test.c +SRCS = worktree.c repository.c object.c object_idcache.c object_idset.c \ + opentemp.c path.c error.c reference.c sha1.c pack.c privsep.c delta.c \ + zbuf.c fileindex.c worktree_test.c CPPFLAGS = -I${.CURDIR}/../../include -I${.CURDIR}/../../lib LDADD = -lutil -lz blob - 4ffef6ba32276ff6be6a63c52ea4754c6de7124f blob + f3f595818068357c40dd403d4732cde1697a36dc --- tog/Makefile +++ tog/Makefile @@ -2,9 +2,9 @@ PROG= tog SRCS= tog.c blame.c commit_graph.c delta.c diff.c diffreg.c error.c \ - fileindex.c object.c object_idset.c opentemp.c path.c \ - pack.c privsep.c reference.c repository.c sha1.c worktree.c \ - utf8.c zbuf.c + fileindex.c object.c object_idcache.c object_idset.c \ + opentemp.c path.c pack.c privsep.c reference.c repository.c \ + sha1.c worktree.c utf8.c zbuf.c CPPFLAGS = -I${.CURDIR}/../include -I${.CURDIR}/../lib LDADD = -lpanel -lncursesw -lutil -lz