[PATCH 2/5] add object-cache infrastructure

[Jeff King <peff@peff.net>]

There is sometimes a need to cache some information about an
object or set of objects persistently across git
invocations. The notes-cache interface can be used for this,
but it is very heavyweight and slow for storing small
values.

This patch introduces a new API, object-cache, which stores
a mapping of objects to values in a concise and efficient
form. See the added API documentation for details.

Signed-off-by: Jeff King <peff@peff.net>
---
As I mentioned earlier, I wanted this to be generic and size-agnostic,
because I'd also like to try caching patch-ids for git-cherry.

 Documentation/technical/api-decorate.txt     |    3 +
 Documentation/technical/api-object-cache.txt |  101 +++++++++++++
 Makefile                                     |    2 +
 object-cache.c                               |  204 ++++++++++++++++++++++++++
 object-cache.h                               |   32 ++++
 5 files changed, 342 insertions(+), 0 deletions(-)
 create mode 100644 Documentation/technical/api-object-cache.txt
 create mode 100644 object-cache.c
 create mode 100644 object-cache.h

diff --git a/Documentation/technical/api-decorate.txt b/Documentation/technical/api-decorate.txt
index 8d10b66..c851f59 100644
--- a/Documentation/technical/api-decorate.txt
+++ b/Documentation/technical/api-decorate.txt
@@ -13,6 +13,9 @@ could, for example, map objects into 32-bit integers. For ease of use,
 functions are provided for storing the values of arbitrary pointers,
 which can point to strings or structs.
 
+Note that the decorate API only stores the mapping in memory. See the
+object-cache API for persistent storage.
+
 Data Structures
 ---------------
 
diff --git a/Documentation/technical/api-object-cache.txt b/Documentation/technical/api-object-cache.txt
new file mode 100644
index 0000000..ecead4c
--- /dev/null
+++ b/Documentation/technical/api-object-cache.txt
@@ -0,0 +1,101 @@
+Object Cache API
+================
+
+The object cache API is meant to store a cache of per-object values. The
+aim is for robustness, speed, and simplicity. The stored data must be of
+a fixed size, and the only operations allowed are insertion and
+retrieval with a struct object as the key.
+
+This API is similar to the decorate API, but provides persistence of
+values across multiple invocations. It is also similar to the
+notes-cache API, but is much lighter weight and suitable for storing
+small values. If you are storing large, arbitrary data, consider using
+notes-cache.
+
+
+Storage
+-------
+
+Values are stored both on-disk and in-memory. Newly added values are
+initially stored in a hash table in memory, and written to disk only
+when `object_cache_write` is called.
+
+The disk storage consists of a single file per cache, located in the
+`$GIT_DIR/cache` directory. Each file contains a list of rows ordered by
+sha1. Each row contains a binary sha1, followed by the fixed-size data
+mapped to that sha1.
+
+When the cache is written to disk, the contents of the in-memory data
+and the disk data are merged, with in-memory values taking precedence
+over disk values. The data is written to a temporary file and atomically
+renamed into the new cache file. Thus there is no lock contention
+between competing processes on either reading or writing (though one
+process's updates may be lost).
+
+
+Speed
+-----
+
+Lookup in the cache requires `O(lg(n))` hash comparisons (via binary
+search of the disk contents, or the in-memory hash table).
+
+Insertion into the cache is amortized `O(1)` via the hash table. Writing
+the cache to disk entails `O(n*lg(n) + m)` hash comparisons, where `m`
+is the number of existing disk entries and `n` is the number of newly
+added entries.
+
+
+Data Structures
+---------------
+
+`struct object_cache`::
+
+	This structure represents a single object cache. Its contents
+	should be considered opaque by calling code.
++
+	The `fd`, `disk_entries`, `disk_nr`, and `record_size` fields
+	represent the mmap'd on-disk data. The `mem` field represents
+	the in-memory data (see the decorate API for details).
+
+
+Functions
+---------
+
+`object_cache_init`::
+
+	Initialize a new object cache; this must be called before any
+	other functions are called on the cache. The `name` parameter
+	specifies a human-readable name which will be used for storage
+	in `$GIT_DIR/cache/$name`. The `width` parameter specifies the
+	size, in units of `char`, of the data to be stored (e.g., pass
+	in `sizeof(uint32_t)` to store 32-bit integers).
+
+`object_cache_lookup`::
+
+	Retrieve a value from the object cache. A void pointer to the
+	stored value will be returned, or `NULL` if there is no value.
+
+`object_cache_add`::
+
+	Store a value in the object cache. The value pointer should
+	point to exactly `width` bytes of data.
+
+`object_cache_write`::
+
+	Merge the in-memory and existing disk entries, and write the
+	resulting cache to disk, under the name `$GIT_DIR/cache/$name`.
+	If no in-memory entries exist, the on-disk cache will be left
+	unchanged.
+
+`object_cache_lookup_uint32`::
+
+	Convenience wrapper for retrieving unsigned 32-bit integers. The
+	value will be returned via the `value` pointer. The return value
+	is `0` if a value was found, or negative otherwise (in which
+	case the contents of `value` will be unchanged).
+
+`object_cache_add_uint32`::
+
+	Convenience wrapper for storing unsigned 32-bit integers. Note
+	that integers are stored on disk in network-byte order, so it is
+	safe to access caches from any architecture.
diff --git a/Makefile b/Makefile
index f8c72e1..dd05579 100644
--- a/Makefile
+++ b/Makefile
@@ -535,6 +535,7 @@ LIB_H += merge-recursive.h
 LIB_H += notes.h
 LIB_H += notes-cache.h
 LIB_H += notes-merge.h
+LIB_H += object-cache.h
 LIB_H += object.h
 LIB_H += pack.h
 LIB_H += pack-refs.h
@@ -628,6 +629,7 @@ LIB_OBJS += name-hash.o
 LIB_OBJS += notes.o
 LIB_OBJS += notes-cache.o
 LIB_OBJS += notes-merge.o
+LIB_OBJS += object-cache.o
 LIB_OBJS += object.o
 LIB_OBJS += pack-check.o
 LIB_OBJS += pack-refs.o
diff --git a/object-cache.c b/object-cache.c
new file mode 100644
index 0000000..d019f0a
--- /dev/null
+++ b/object-cache.c
@@ -0,0 +1,204 @@
+#include "cache.h"
+#include "object-cache.h"
+#include "sha1-lookup.h"
+#include "object.h"
+
+static const char *object_cache_path(const char *name)
+{
+	return git_path("cache/%s", name);
+}
+
+static void open_disk_cache(struct object_cache *c, const char *path)
+{
+	struct stat sb;
+
+	c->fd = open(path, O_RDONLY);
+	if (c->fd < 0)
+		return;
+
+	if (fstat(c->fd, &sb) < 0) {
+		close(c->fd);
+		c->fd = -1;
+		return;
+	}
+
+	c->disk_entries = xmmap(NULL, sb.st_size, PROT_READ, MAP_PRIVATE,
+				c->fd, 0);
+	c->disk_nr = sb.st_size / c->record_size;
+}
+
+void object_cache_init(struct object_cache *c, const char *name, int width)
+{
+	memset(c, 0, sizeof(*c));
+	c->record_size = 20 + width;
+	c->mem.width = width;
+	open_disk_cache(c, object_cache_path(name));
+}
+
+static void *lookup_disk(const struct object_cache *c,
+			 const struct object *obj)
+{
+	int pos;
+
+	pos = sha1_entry_pos(c->disk_entries, c->record_size, 0,
+			     0, c->disk_nr, c->disk_nr, obj->sha1);
+	if (pos < 0)
+		return NULL;
+
+	return c->disk_entries + (pos * c->record_size) + 20;
+}
+
+const void *object_cache_lookup(const struct object_cache *c,
+					 const struct object *obj)
+{
+	void *r;
+
+	r = lookup_decoration_value(&c->mem, obj);
+	if (!r)
+		r = lookup_disk(c, obj);
+	return r;
+}
+
+void object_cache_add(struct object_cache *c, const struct object *obj,
+		      const void *value)
+{
+	add_decoration_value(&c->mem, obj, value, NULL);
+}
+
+static unsigned char *flatten_mem_entries(struct object_cache *c)
+{
+	unsigned char *p;
+	unsigned char *ret;
+	int nr;
+
+	ret = xmalloc(c->mem.nr * c->record_size);
+	nr = 0;
+	for (p = c->mem.hash; p < c->mem.end; p += c->mem.stride) {
+		struct object_decoration *e = (struct object_decoration *)p;
+		unsigned char *out;
+
+		if (!e->base)
+			continue;
+
+		if (nr == c->mem.nr)
+			die("BUG: decorate hash contained extra values");
+
+		out = ret + (nr * c->record_size);
+		hashcpy(out, e->base->sha1);
+		out += 20;
+		memcpy(out, e->decoration, c->mem.width);
+		nr++;
+	}
+
+	return ret;
+}
+
+static int void_hashcmp(const void *a, const void *b)
+{
+	return hashcmp(a, b);
+}
+
+int object_cache_write(struct object_cache *c, const char *name)
+{
+	const char *path = object_cache_path(name);
+	struct strbuf tempfile = STRBUF_INIT;
+	int fd;
+	unsigned char *mem_entries;
+	int i, j;
+	int r;
+
+	if (!c->mem.nr)
+		return 0;
+
+	strbuf_addf(&tempfile, "%s.XXXXXX", path);
+	if (safe_create_leading_directories(tempfile.buf) < 0 ||
+	    (fd = git_mkstemp_mode(tempfile.buf, 0755)) < 0) {
+		strbuf_release(&tempfile);
+		return -1;
+	}
+
+	mem_entries = flatten_mem_entries(c);
+	qsort(mem_entries, c->mem.nr, c->record_size, void_hashcmp);
+
+#define WRITE_ENTRY(e) \
+do { \
+	if (write_in_full(fd, e, c->record_size) < 0) { \
+		close(fd); \
+		unlink(tempfile.buf); \
+		strbuf_release(&tempfile); \
+		free(mem_entries); \
+		return -1; \
+	} \
+} while (0)
+
+	i = j = 0;
+	while (i < c->mem.nr && j < c->disk_nr) {
+		unsigned char *mem = mem_entries + (i * c->record_size);
+		unsigned char *disk = c->disk_entries + (j * c->record_size);
+		int cmp = hashcmp(mem, disk);
+
+		/* replace disk entries with in-memory ones */
+		if (cmp == 0)
+			j++;
+		else if (cmp < 0) {
+			WRITE_ENTRY(mem);
+			i++;
+		}
+		else {
+			WRITE_ENTRY(disk);
+			j++;
+		}
+	}
+	while (i < c->mem.nr) {
+		unsigned char *mem = mem_entries + (i * c->record_size);
+		WRITE_ENTRY(mem);
+		i++;
+	}
+	while (j < c->disk_nr) {
+		unsigned char *disk = c->disk_entries + (j * c->record_size);
+		WRITE_ENTRY(disk);
+		j++;
+	}
+#undef WRITE_ENTRY
+
+	free(mem_entries);
+
+	if (close(fd) < 0 || rename(tempfile.buf, path) < 0)
+		r = -1;
+	else
+		r = 0;
+
+	unlink(tempfile.buf);
+	strbuf_release(&tempfile);
+	return r;
+}
+
+int object_cache_lookup_uint32(const struct object_cache *c,
+			       const struct object *obj,
+			       uint32_t *value)
+{
+	const uint32_t *out;
+
+	if (c->record_size != 24)
+		die("BUG: size mismatch in object cache lookup (%d != 24)",
+		    c->record_size);
+
+	out = object_cache_lookup(c, obj);
+	if (!out)
+		return -1;
+
+	*value = ntohl(*out);
+	return 0;
+}
+
+void object_cache_add_uint32(struct object_cache *c,
+			     const struct object *obj,
+			     uint32_t value)
+{
+	if (c->record_size != 24)
+		die("BUG: size mismatch in object cache add (%d != 24)",
+		    c->record_size);
+
+	value = htonl(value);
+	object_cache_add(c, obj, &value);
+}
diff --git a/object-cache.h b/object-cache.h
new file mode 100644
index 0000000..b869f1e
--- /dev/null
+++ b/object-cache.h
@@ -0,0 +1,32 @@
+#ifndef OBJECT_CACHE_H
+#define OBJECT_CACHE_H
+
+#include "decorate.h"
+
+struct object_cache {
+	/* mmap'd disk entries */
+	int fd;
+	unsigned char *disk_entries;
+	int disk_nr;
+	int record_size;
+
+	/* in memory entries */
+	struct decoration mem;
+};
+
+void object_cache_init(struct object_cache *, const char *name, int width);
+const void *object_cache_lookup(const struct object_cache *,
+				const struct object *);
+void object_cache_add(struct object_cache *, const struct object *,
+		      const void *value);
+int object_cache_write(struct object_cache *, const char *name);
+
+/* Convenience wrappers around object_cache_{lookup,add} */
+int object_cache_lookup_uint32(const struct object_cache *,
+			       const struct object *,
+			       uint32_t *value);
+void object_cache_add_uint32(struct object_cache *,
+			     const struct object *,
+			     uint32_t value);
+
+#endif /* OBJECT_CACHE_H */
-- 
1.7.6.37.g989c6