commit ab2f42e760e128287c5e880a39c591845231922b from: Stefan Sperling date: Sun Nov 10 15:51:05 2019 UTC cache delta data buffers in an LRU cache commit - 42c69117cce2e1658d5b5aabbc383ce7252cf167 commit + ab2f42e760e128287c5e880a39c591845231922b blob - 4310fc7e0269fccc28e40d464196abeb11e6d25f blob + 709948a09b358cf01d39d50454f4f9c08fad9c28 --- got/Makefile +++ got/Makefile @@ -8,7 +8,7 @@ SRCS= got.c blame.c commit_graph.c delta.c diff.c \ object_idset.c object_parse.c opentemp.c path.c pack.c \ privsep.c reference.c repository.c sha1.c worktree.c \ inflate.c buf.c rcsutil.c diff3.c lockfile.c \ - deflate.c object_create.c + deflate.c object_create.c delta_cache.c MAN = ${PROG}.1 got-worktree.5 git-repository.5 CPPFLAGS = -I${.CURDIR}/../include -I${.CURDIR}/../lib blob - /dev/null blob + b9d4f89656dd56b278729ad6c522d9c453d476da (mode 644) --- /dev/null +++ lib/delta_cache.c @@ -0,0 +1,144 @@ +/* + * Copyright (c) 2019 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_inflate.h" +#include "got_lib_object.h" +#include "got_lib_delta_cache.h" + +#ifndef nitems +#define nitems(_a) (sizeof(_a) / sizeof((_a)[0])) +#endif + +struct got_delta_cache_element { + TAILQ_ENTRY(got_delta_cache_element) entry; + off_t delta_data_offset; + uint8_t *delta_data; + size_t delta_len; +}; + +TAILQ_HEAD(got_delta_cache_head, got_delta_cache_element); + +struct got_delta_cache { + struct got_delta_cache_head entries; + int nelem; + int maxelem; + size_t maxelemsize; +}; + +struct got_delta_cache * +got_delta_cache_alloc(int maxelem, size_t maxelemsize) +{ + struct got_delta_cache *cache; + + cache = calloc(1, sizeof(*cache)); + if (cache == NULL) + return NULL; + + TAILQ_INIT(&cache->entries); + cache->maxelem = maxelem; + cache->maxelemsize = maxelemsize; + return cache; +} + +void +got_delta_cache_free(struct got_delta_cache *cache) +{ + struct got_delta_cache_element *entry; + + while (!TAILQ_EMPTY(&cache->entries)) { + entry = TAILQ_FIRST(&cache->entries); + TAILQ_REMOVE(&cache->entries, entry, entry); + free(entry->delta_data); + free(entry); + } + free(cache); +} + +static void +remove_least_used_element(struct got_delta_cache *cache) +{ + struct got_delta_cache_element *entry; + + if (cache->nelem == 0) + return; + + entry = TAILQ_LAST(&cache->entries, got_delta_cache_head); + TAILQ_REMOVE(&cache->entries, entry, entry); + free(entry->delta_data); + free(entry); + cache->nelem--; +} + + +const struct got_error * +got_delta_cache_add(struct got_delta_cache *cache, + off_t delta_data_offset, uint8_t *delta_data, size_t delta_len) +{ + struct got_delta_cache_element *entry; + + if (delta_len > cache->maxelemsize) + return got_error(GOT_ERR_NO_SPACE); + + if (cache->nelem >= cache->maxelem) + remove_least_used_element(cache); + + entry = calloc(1, sizeof(*entry)); + if (entry == NULL) + return got_error_from_errno("calloc"); + + entry->delta_data_offset = delta_data_offset; + entry->delta_data = delta_data; + entry->delta_len = delta_len; + + TAILQ_INSERT_HEAD(&cache->entries, entry, entry); + cache->nelem++; + return NULL; +} + +void +got_delta_cache_get(uint8_t **delta_data, size_t *delta_len, + struct got_delta_cache *cache, off_t delta_data_offset) +{ + struct got_delta_cache_element *entry; + + *delta_data = NULL; + *delta_len = 0; + TAILQ_FOREACH(entry, &cache->entries, entry) { + if (entry->delta_data_offset != delta_data_offset) + continue; + if (entry != TAILQ_FIRST(&cache->entries)) { + TAILQ_REMOVE(&cache->entries, entry, entry); + TAILQ_INSERT_HEAD(&cache->entries, entry, entry); + } + *delta_data = entry->delta_data; + *delta_len = entry->delta_len; + return; + } +} blob - /dev/null blob + 39cb23dc018390d1de373fde1dc990faa76c21e2 (mode 644) --- /dev/null +++ lib/got_lib_delta_cache.h @@ -0,0 +1,24 @@ +/* + * Copyright (c) 2019 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_delta_cache; + +struct got_delta_cache *got_delta_cache_alloc(int, size_t); +void got_delta_cache_free(struct got_delta_cache *); + +const struct got_error *got_delta_cache_add(struct got_delta_cache *, off_t, + uint8_t *, size_t); +void got_delta_cache_get(uint8_t **, size_t *, struct got_delta_cache *, off_t); blob - 5ccd979e0bc59829534dc075f1e50f9ef8d069d0 blob + f1f994a6a41a9c16744f389369f3692b13da72e4 --- lib/got_lib_pack.h +++ lib/got_lib_pack.h @@ -21,6 +21,7 @@ struct got_pack { uint8_t *map; size_t filesize; struct got_privsep_child *privsep_child; + struct got_delta_cache *delta_cache; }; const struct got_error *got_pack_stop_privsep_child(struct got_pack *); blob - 433976a663e5eb022cd09dd6498cb25a651150e3 blob + eef27b82b6eeb8a714c5fedd79b33b04f6e8e5f5 --- lib/pack.c +++ lib/pack.c @@ -39,6 +39,7 @@ #include "got_lib_sha1.h" #include "got_lib_delta.h" +#include "got_lib_delta_cache.h" #include "got_lib_inflate.h" #include "got_lib_object.h" #include "got_lib_object_parse.h" @@ -546,6 +547,10 @@ got_pack_close(struct got_pack *pack) free(pack->path_packfile); pack->path_packfile = NULL; pack->filesize = 0; + if (pack->delta_cache) { + got_delta_cache_free(pack->delta_cache); + pack->delta_cache = NULL; + } return err; } @@ -998,14 +1003,29 @@ get_delta_chain_max_size(uint64_t *max_size, struct go const struct got_error *err; uint8_t *delta_buf; size_t delta_len; + int cached = 1; - err = read_delta_data(&delta_buf, &delta_len, - delta->data_offset, pack); - if (err) - return err; + got_delta_cache_get(&delta_buf, &delta_len, + pack->delta_cache, delta->data_offset); + if (delta_buf == NULL) { + cached = 0; + err = read_delta_data(&delta_buf, &delta_len, + delta->data_offset, pack); + if (err) + return err; + err = got_delta_cache_add(pack->delta_cache, + delta->data_offset, delta_buf, delta_len); + if (err == NULL) + cached = 1; + else if (err->code != GOT_ERR_NO_SPACE) { + free(delta_buf); + return err; + } + } err = got_delta_get_sizes(&base_size, &result_size, delta_buf, delta_len); - free(delta_buf); + if (!cached) + free(delta_buf); if (err) return err; } else @@ -1059,6 +1079,7 @@ dump_delta_chain_to_file(size_t *result_size, struct g /* Deltas are ordered in ascending order. */ SIMPLEQ_FOREACH(delta, &deltas->entries, entry) { + int cached = 1; if (n == 0) { size_t mapoff; off_t delta_data_offset; @@ -1111,10 +1132,23 @@ dump_delta_chain_to_file(size_t *result_size, struct g continue; } - err = read_delta_data(&delta_buf, &delta_len, - delta->data_offset, pack); - if (err) - goto done; + got_delta_cache_get(&delta_buf, &delta_len, + pack->delta_cache, delta->data_offset); + if (delta_buf == NULL) { + cached = 0; + err = read_delta_data(&delta_buf, &delta_len, + delta->data_offset, pack); + if (err) + goto done; + err = got_delta_cache_add(pack->delta_cache, + delta->data_offset, delta_buf, delta_len); + if (err == NULL) + cached = 1; + else if (err->code != GOT_ERR_NO_SPACE) { + free(delta_buf); + goto done; + } + } if (base_buf) { err = got_delta_apply_in_mem(base_buf, base_bufsz, delta_buf, delta_len, accum_buf, @@ -1127,7 +1161,8 @@ dump_delta_chain_to_file(size_t *result_size, struct g ++n < deltas->nentries ? accum_file : outfile, &accum_size); } - free(delta_buf); + if (!cached) + free(delta_buf); if (err) goto done; @@ -1204,6 +1239,7 @@ dump_delta_chain_to_mem(uint8_t **outbuf, size_t *outl /* Deltas are ordered in ascending order. */ SIMPLEQ_FOREACH(delta, &deltas->entries, entry) { + int cached = 1; if (n == 0) { size_t delta_data_offset; @@ -1241,14 +1277,28 @@ dump_delta_chain_to_mem(uint8_t **outbuf, size_t *outl continue; } - err = read_delta_data(&delta_buf, &delta_len, - delta->data_offset, pack); - if (err) - goto done; + got_delta_cache_get(&delta_buf, &delta_len, + pack->delta_cache, delta->data_offset); + if (delta_buf == NULL) { + cached = 0; + err = read_delta_data(&delta_buf, &delta_len, + delta->data_offset, pack); + if (err) + goto done; + err = got_delta_cache_add(pack->delta_cache, + delta->data_offset, delta_buf, delta_len); + if (err == NULL) + cached = 1; + else if (err->code != GOT_ERR_NO_SPACE) { + free(delta_buf); + goto done; + } + } err = got_delta_apply_in_mem(base_buf, base_bufsz, delta_buf, delta_len, accum_buf, &accum_size, max_size); - free(delta_buf); + if (!cached) + free(delta_buf); n++; if (err) goto done; blob - e50b725ba52b655d85bb730cc8fae281a9751215 blob + 5fe2b7efcfad5831f504354f84e46082989a0d5f --- libexec/got-read-pack/Makefile +++ libexec/got-read-pack/Makefile @@ -5,7 +5,7 @@ PROG= got-read-pack SRCS= got-read-pack.c delta.c error.c inflate.c object_cache.c \ object_idset.c object_parse.c opentemp.c pack.c path.c \ - privsep.c sha1.c + privsep.c sha1.c delta_cache.c CPPFLAGS = -I${.CURDIR}/../../include -I${.CURDIR}/../../lib LDADD = -lutil -lz blob - cb7464ca665181ed509062b13f114a4acc24e5e1 blob + d8c2e0f8683a4492064ae0e7be3d35a1c6b485f0 --- libexec/got-read-pack/got-read-pack.c +++ libexec/got-read-pack/got-read-pack.c @@ -35,6 +35,7 @@ #include "got_object.h" #include "got_lib_delta.h" +#include "got_lib_delta_cache.h" #include "got_lib_object.h" #include "got_lib_object_cache.h" #include "got_lib_object_parse.h" @@ -491,6 +492,13 @@ receive_pack(struct got_pack **packp, struct imsgbuf * pack->path_packfile = strdup(ipack.path_packfile); if (pack->path_packfile == NULL) { err = got_error_from_errno("strdup"); + goto done; + } + + pack->delta_cache = got_delta_cache_alloc(100, + GOT_DELTA_RESULT_SIZE_CACHED_MAX); + if (pack->delta_cache == NULL) { + err = got_error_from_errno("got_delta_cache_alloc"); goto done; } blob - 531c090468f03b4cc3cec7ddbb0b6cd2c7df89a4 blob + aafde1a4c7fe645f39e2b0acb46faa64767369c7 --- tog/Makefile +++ tog/Makefile @@ -8,7 +8,7 @@ SRCS= tog.c blame.c commit_graph.c delta.c diff.c \ object_idset.c object_parse.c opentemp.c path.c pack.c \ privsep.c reference.c repository.c sha1.c worktree.c \ utf8.c inflate.c buf.c rcsutil.c diff3.c \ - lockfile.c deflate.c object_create.c + lockfile.c deflate.c object_create.c delta_cache.c MAN = ${PROG}.1 CPPFLAGS = -I${.CURDIR}/../include -I${.CURDIR}/../lib