thodg/got

diff --git a/got/Makefile b/got/Makefile
index 4310fc7..709948a 100644
--- a/got/Makefile
+++ b/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
diff --git a/lib/delta_cache.c b/lib/delta_cache.c
new file mode 100644
index 0000000..b9d4f89
--- /dev/null
+++ b/lib/delta_cache.c
@@ -0,0 +1,144 @@
+/*
+ * Copyright (c) 2019 Stefan Sperling <stsp@openbsd.org>
+ *
+ * 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 <sys/queue.h>
+
+#include <stdlib.h>
+#include <string.h>
+#include <sha1.h>
+#include <stdio.h>
+#include <zlib.h>
+#include <limits.h>
+#include <time.h>
+
+#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;
+	}
+}
diff --git a/lib/got_lib_delta_cache.h b/lib/got_lib_delta_cache.h
new file mode 100644
index 0000000..39cb23d
--- /dev/null
+++ b/lib/got_lib_delta_cache.h
@@ -0,0 +1,24 @@
+/*
+ * Copyright (c) 2019 Stefan Sperling <stsp@openbsd.org>
+ *
+ * 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);
diff --git a/lib/got_lib_pack.h b/lib/got_lib_pack.h
index 5ccd979..f1f994a 100644
--- a/lib/got_lib_pack.h
+++ b/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 *);
diff --git a/lib/pack.c b/lib/pack.c
index 433976a..eef27b8 100644
--- a/lib/pack.c
+++ b/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 got_delta_chain *deltas,
 			const struct got_error *err;
 			uint8_t *delta_buf;
 			size_t delta_len;
-
-			err = read_delta_data(&delta_buf, &delta_len,
-			    delta->data_offset, pack);
-			if (err)
-				return err;
+			int cached = 1;
+
+			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 got_delta_chain *deltas,
 
 	/* 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 got_delta_chain *deltas,
 			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 got_delta_chain *deltas,
 			    ++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 *outlen,
 
 	/* 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 *outlen,
 			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;
diff --git a/libexec/got-read-pack/Makefile b/libexec/got-read-pack/Makefile
index e50b725..5fe2b7e 100644
--- a/libexec/got-read-pack/Makefile
+++ b/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
diff --git a/libexec/got-read-pack/got-read-pack.c b/libexec/got-read-pack/got-read-pack.c
index cb7464c..d8c2e0f 100644
--- a/libexec/got-read-pack/got-read-pack.c
+++ b/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"
@@ -494,6 +495,13 @@ receive_pack(struct got_pack **packp, struct imsgbuf *ibuf)
 		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;
+	}
+
 #ifndef GOT_PACK_NO_MMAP
 	pack->map = mmap(NULL, pack->filesize, PROT_READ, MAP_PRIVATE,
 	    pack->fd, 0);
diff --git a/tog/Makefile b/tog/Makefile
index 531c090..aafde1a 100644
--- a/tog/Makefile
+++ b/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