Re: [RFC/PATCHv2 1/6] decorate: allow storing values instead of pointers

@@ -0,0 +1,160 @@
+map API
+=======
+
+The map API is a system for efficiently mapping keys to values in memory. Items
+are stored in a hash table for fast lookup; storage efficiency is achieved
+through macro-based code generation, which lets the compiler store values
+compactly in memory.
+
+Due to the code generation, there are two different facets of this API: macros
+to build new types of mappings (i.e., generate new function and struct
+definitions), and generated functions to store and retrieve values from a
+particular mapping.
+
+
+Related APIs
+------------
+
+The hash API provides a similar key/value store. However, it does not deal with
+hash collisions itself, leaving the caller to handle bucket management (but
+this is a feature if you are interested in using the collisions as part of an
+algorithm).  Furthermore, it can store only void pointers, making storage of
+small values inefficient and cumbersome.
+
+The decorate API provides a similar interface to map, but is restricted to
+using "struct object" as the key, and a void pointer as the value.
+
+
+Defining New Map Types
+----------------------
+
+A map type is uniquely defined by the pair of its key and value types. To
+define a new type, you must use the `DECLARE_MAP` macro in `map.h`, and the
+`IMPLEMENT_MAP` macro in `map.c`. Their usage is described below:
+
+`DECLARE_MAP`::
+
+	Declare a new type of map, including the struct definition and
+	declarations of access functions. The `name` parameter should describe
+	the types (e.g., `object_uint32` to map objects to 32-bit integers).
+	The `ktype` parameter specifies the C type of the key (e.g.,
+	`struct object *`) and the `vtype` parameter specifies the C type of
+	the value (e.g., `uint32_t`).
+
+`IMPLEMENT_MAP`::
+
+	Create function definitions for a map type. The `name` parameter should
+	match one given to `DECLARE_MAP`. The `equal_fun` parameter should
+	specify a function that, when given two items of type `ktype`, will
+	return a non-zero value if they are equal.  The `hash_fun` parameter
+	should specify a function that will convert an object of type `ktype`
+	into an integer hash value.
+
+Several convenience functions are provided to fill in macro parameters:
+
+`hash_obj`::
+
+	Suitable for `hash_fun` when the key type is `struct object *`.
+
+`obj_equal`::
+
+	Suitable for `equal_fun` when the key type is `struct object *`.
+
+
+Data Structures
+---------------
+
+Each defined map type will have its own structure (e.g., `map_object_uint32`).
+
+`struct map_NAME`::
+
+	A single map object. This struct should be initialized to all-zeroes.
+	The `nr` field specifies the number of items stored in the map. The
+	`size` field specifies the number of hash buckets allocated. The `hash`
+	field stores the actual data. Callers should never need to look at
+	these fields unless they are enumerating all elements of the map (see
+	the example below).
+
+`struct map_entry_NAME`::
+
+	A single entry in the hash, which may or may not contain a value. If
+	the `used` field is false, the `key` and `value` fields should not be
+	examined at all. Otherwise, the `key` and `value` fields represent a
+	single mapped pair.  You should never need to use this type directly,
+	unless you are enumerating all elements of a map.
+
+
+Functions
+---------
+
+Each defined map type will have its own set of access function (e.g.,
+`map_get_object_uint32`).
+
+`map_get_NAME(struct map_NAME *, const ktype key, vtype *value)`::
+
+	Retrieve the value corresponding to `key`, returning it via the pointer
+	`value`. Returns 1 if an item was found, zero otherwise (in which case
+	`value` is unchanged).
+
+`map_set_NAME(struct map_NAME *, const ktype key, vtype value, vtype *old)`::
+
+	Insert a mapping from `key` to `value`. If a mapping for `key` already
+	existed, the previous value is copied into `old` (if it is non-NULL)
+	and the function returns 1. Otherwise, the function returns 0.
+
+
+Examples
+--------
+
+Create a new mapping type of objects to integers:
+
+-------------------------------------------------------------------
+/* in map.h */
+DECLARE_MAP(object_int, struct object *, int)
+
+/* in map.c */
+IMPLEMENT_MAP(object_int, struct object *, int, obj_equal, hash_obj)
+-------------------------------------------------------------------
+
+Store and retrieve integers by object key:
+
+-------------------------------------------------------------------
+static struct map_object_int foos;
+
+void store_foo(const struct commit *c, int foo)
+{
+	int old;
+	if (map_set_object_uint32(&foos, &c->object, foo, &old))
+		printf("old value was %d\n", old);
+}
+
+void print_foo(const struct commit *c)
+{
+	int v;
+
+	if (map_get_object_int(&foos, &c->object, &v))
+		printf("foo: %d\n", v);
+	else
+		printf("no such foo\n");
+}
+-------------------------------------------------------------------
+
+Iterate over all map entries:
+
+-------------------------------------------------------------------
+void dump_foos(void)
+{
+	int i;
+
+	printf("there are %u foos:\n", foos.nr);
+
+	for (i = 0; i < foos.size; i++) {
+		struct map_entry_object_int *e = foos.hash[i];
+
+		if (!e->used)
+			continue;
+
+		printf("%s -> %d\n", sha1_to_hex(e->key->sha1), e->value);
+	}
+}
+-------------------------------------------------------------------

@@ -533,6 +533,7 @@ LIB_H += list-objects.h
 LIB_H += ll-merge.h
 LIB_H += log-tree.h
 LIB_H += mailmap.h
+LIB_H += map.h
 LIB_H += merge-file.h
 LIB_H += merge-recursive.h
 LIB_H += notes.h

@@ -624,6 +625,7 @@ LIB_OBJS += ll-merge.o
 LIB_OBJS += lockfile.o
 LIB_OBJS += log-tree.o
 LIB_OBJS += mailmap.o
+LIB_OBJS += map.o
 LIB_OBJS += match-trees.o
 LIB_OBJS += merge-file.o
 LIB_OBJS += merge-recursive.o

@@ -0,0 +1,86 @@
+#include "cache.h"
+#include "map.h"
+#include "object.h"
+
+static unsigned int hash_obj(const struct object *obj, unsigned int n)
+{
+	unsigned int hash;
+
+	memcpy(&hash, obj->sha1, sizeof(unsigned int));
+	return hash % n;
+}
+
+static int obj_equal(const struct object *a, const struct object *b)
+{
+	return a == b;
+}
+
+#define IMPLEMENT_MAP(name, equal_fun, hash_fun) \
+static int map_insert_##name(struct map_##name *m, \
+			     const map_ktype_##name key, \
+			     map_vtype_##name value, \
+			     map_vtype_##name *old) \
+{ \
+	unsigned int j; \
+\
+	for (j = hash_fun(key, m->size); m->hash[j].used; j = (j+1) % m->size) { \
+		if (equal_fun(m->hash[j].key, key)) { \
+			if (old) \
+				*old = m->hash[j].value; \
+			m->hash[j].value = value; \
+			return 1; \
+		} \
+	} \
+\
+	m->hash[j].key = key; \
+	m->hash[j].value = value; \
+	m->hash[j].used = 1; \
+	m->nr++; \
+	return 0; \
+} \
+\
+static void map_grow_##name(struct map_##name *m) \
+{ \
+	struct map_entry_##name *old_hash = m->hash; \
+	unsigned int old_size = m->size; \
+	unsigned int i; \
+\
+	m->size = (old_size + 1000) * 3 / 2; \
+	m->hash = xcalloc(m->size, sizeof(*m->hash)); \
+	m->nr = 0; \
+\
+	for (i = 0; i < old_size; i++) { \
+		if (!old_hash[i].used) \
+			continue; \
+		map_insert_##name(m, old_hash[i].key, old_hash[i].value, NULL); \
+	} \
+	free(old_hash); \
+} \
+\
+int map_set_##name(struct map_##name *m, \
+		   const map_ktype_##name key, \
+		   map_vtype_##name value, \
+		   map_vtype_##name *old) \
+{ \
+	if (m->nr >= m->size * 2 / 3) \
+		map_grow_##name(m); \
+	return map_insert_##name(m, key, value, old); \
+} \
+\
+int map_get_##name(struct map_##name *m, \
+		   const map_ktype_##name key, \
+		   map_vtype_##name *value) \
+{ \
+	unsigned int j; \
+\
+	if (!m->size) \
+		return 0; \
+\
+	for (j = hash_fun(key, m->size); m->hash[j].used; j = (j+1) % m->size) { \
+		if (equal_fun(m->hash[j].key, key)) { \
+			*value = m->hash[j].value; \
+			return 1; \
+		} \
+	} \
+	return 0; \
+}

@@ -0,0 +1,26 @@
+#ifndef MAP_H
+#define MAP_H
+
+#define DECLARE_MAP(name, key_type, value_type) \
+typedef key_type map_ktype_##name; \
+typedef value_type map_vtype_##name; \
+struct map_entry_##name { \
+	map_ktype_##name key; \
+	map_vtype_##name value; \
+	unsigned used:1; \
+}; \
+\
+struct map_##name { \
+	unsigned int size, nr; \
+	struct map_entry_##name *hash; \
+}; \
+\
+extern int map_get_##name(struct map_##name *, \
+			  const map_ktype_##name key, \
+			  map_vtype_##name *value); \
+extern int map_set_##name(struct map_##name *, \
+			  const map_ktype_##name key, \
+			  map_vtype_##name value, \
+			  map_vtype_##name *old);
+
+#endif /* MAP_H */

@@ -149,7 +149,7 @@ void dump_foos(void)
 	printf("there are %u foos:\n", foos.nr);
 
 	for (i = 0; i < foos.size; i++) {
-		struct map_entry_object_int *e = foos.hash[i];
+		struct map_entry_object_int *e = foos.hash + i;
 
 		if (!e->used)
 			continue;

@@ -12,7 +12,7 @@
 #include "diffcore.h"
 #include "log-tree.h"
 #include "revision.h"
-#include "decorate.h"
+#include "map.h"
 #include "string-list.h"
 #include "utf8.h"
 #include "parse-options.h"

@@ -60,7 +60,7 @@ static int parse_opt_tag_of_filtered_mode(const struct option *opt,
 	return 0;
 }
 
-static struct decoration idnums;
+static struct map_object_uint32 idnums;
 static uint32_t last_idnum;
 
 static int has_unshown_parent(struct commit *commit)

@@ -74,20 +74,9 @@ static int has_unshown_parent(struct commit *commit)
 	return 0;
 }
 
-/* Since intptr_t is C99, we do not use it here */
-static inline uint32_t *mark_to_ptr(uint32_t mark)
-{
-	return ((uint32_t *)NULL) + mark;
-}
-
-static inline uint32_t ptr_to_mark(void * mark)
-{
-	return (uint32_t *)mark - (uint32_t *)NULL;
-}
-
 static inline void mark_object(struct object *object, uint32_t mark)
 {
-	add_decoration(&idnums, object, mark_to_ptr(mark));
+	map_set_object_uint32(&idnums, object, mark, NULL);
 }
 
 static inline void mark_next_object(struct object *object)

@@ -97,10 +86,9 @@ static inline void mark_next_object(struct object *object)
 
 static int get_object_mark(struct object *object)
 {
-	void *decoration = lookup_decoration(&idnums, object);
-	if (!decoration)
-		return 0;
-	return ptr_to_mark(decoration);
+	uint32_t ret = 0;
+	map_get_object_uint32(&idnums, object, &ret);
+	return ret;
 }
 
 static void show_progress(void)

@@ -538,8 +526,6 @@ static void handle_tags_and_duplicates(struct string_list *extra_refs)
 static void export_marks(char *file)
 {
 	unsigned int i;
-	uint32_t mark;
-	struct object_decoration *deco = idnums.hash;
 	FILE *f;
 	int e = 0;
 

@@ -548,15 +534,15 @@ static void export_marks(char *file)
 		die_errno("Unable to open marks file %s for writing.", file);
 
 	for (i = 0; i < idnums.size; i++) {
-		if (deco->base && deco->base->type == 1) {
-			mark = ptr_to_mark(deco->decoration);
-			if (fprintf(f, ":%"PRIu32" %s\n", mark,
-				sha1_to_hex(deco->base->sha1)) < 0) {
+		const struct map_entry_object_uint32 *m = idnums.hash + i;
+
+		if (m->used && m->key->type == 1) {
+			if (fprintf(f, ":%"PRIu32" %s\n", m->value,
+				sha1_to_hex(m->key->sha1)) < 0) {
 			    e = 1;
 			    break;
 			}
 		}
-		deco++;
 	}
 
 	e |= ferror(f);

@@ -84,3 +84,5 @@ int map_get_##name(struct map_##name *m, \
 	} \
 	return 0; \
 }
+
+IMPLEMENT_MAP(object_uint32, obj_equal, hash_obj)

@@ -23,4 +23,6 @@ extern int map_set_##name(struct map_##name *, \
 			  map_vtype_##name value, \
 			  map_vtype_##name *old);
 
+DECLARE_MAP(object_uint32, const struct object *, uint32_t)
+
 #endif /* MAP_H */

@@ -1,6 +1,40 @@
 decorate API
 ============
 
-Talk about <decorate.h>
+The decorate API is a system for efficiently mapping objects to values
+in memory. It is slightly slower than an actual member of an object
+struct (because it incurs a hash lookup), but it uses less memory when
+the mapping is not in use, or when the number of decorated objects is
+small compared to the total number of objects.
 
-(Linus)
+The decorate API is a special form of the `map` link:api-map.html[map
+API]. It has slightly simpler calling conventions, but only use objects
+as keys, and can only store void pointers as values.
+
+
+Data Structures
+---------------
+
+`struct decoration`::
+
+	This structure represents a single mapping of objects to values.
+	The `name` field is not used by the decorate API itself, but may
+	be used by calling code. The `map` field represents the actual
+	mapping of objects to void pointers (see the
+	link:api-map.html[map API] for details).
+
+
+Functions
+---------
+
+`add_decoration`::
+
+	Add a mapping from an object to a void pointer. If there was a
+	previous value for this object, the function returns this value;
+	otherwise, the function returns NULL.
+
+`lookup_decoration`::
+
+	Retrieve the stored value pointer for an object from the
+	mapping. The return value is the value pointer, or `NULL` if
+	there is no value for this object.

@@ -1,88 +1,17 @@
-/*
- * decorate.c - decorate a git object with some arbitrary
- * data.
- */
 #include "cache.h"
-#include "object.h"
 #include "decorate.h"
 
-static unsigned int hash_obj(const struct object *obj, unsigned int n)
-{
-	unsigned int hash;
-
-	memcpy(&hash, obj->sha1, sizeof(unsigned int));
-	return hash % n;
-}
-
-static void *insert_decoration(struct decoration *n, const struct object *base, void *decoration)
-{
-	int size = n->size;
-	struct object_decoration *hash = n->hash;
-	unsigned int j = hash_obj(base, size);
-
-	while (hash[j].base) {
-		if (hash[j].base == base) {
-			void *old = hash[j].decoration;
-			hash[j].decoration = decoration;
-			return old;
-		}
-		if (++j >= size)
-			j = 0;
-	}
-	hash[j].base = base;
-	hash[j].decoration = decoration;
-	n->nr++;
-	return NULL;
-}
-
-static void grow_decoration(struct decoration *n)
-{
-	int i;
-	int old_size = n->size;
-	struct object_decoration *old_hash = n->hash;
-
-	n->size = (old_size + 1000) * 3 / 2;
-	n->hash = xcalloc(n->size, sizeof(struct object_decoration));
-	n->nr = 0;
-
-	for (i = 0; i < old_size; i++) {
-		const struct object *base = old_hash[i].base;
-		void *decoration = old_hash[i].decoration;
-
-		if (!base)
-			continue;
-		insert_decoration(n, base, decoration);
-	}
-	free(old_hash);
-}
-
-/* Add a decoration pointer, return any old one */
 void *add_decoration(struct decoration *n, const struct object *obj,
-		void *decoration)
+		     void *decoration)
 {
-	int nr = n->nr + 1;
-
-	if (nr > n->size * 2 / 3)
-		grow_decoration(n);
-	return insert_decoration(n, obj, decoration);
+	void *ret = NULL;
+	map_set_object_void(&n->map, obj, decoration, &ret);
+	return ret;
 }
 
-/* Lookup a decoration pointer */
 void *lookup_decoration(struct decoration *n, const struct object *obj)
 {
-	unsigned int j;
-
-	/* nothing to lookup */
-	if (!n->size)
-		return NULL;
-	j = hash_obj(obj, n->size);
-	for (;;) {
-		struct object_decoration *ref = n->hash + j;
-		if (ref->base == obj)
-			return ref->decoration;
-		if (!ref->base)
-			return NULL;
-		if (++j == n->size)
-			j = 0;
-	}
+	void *ret = NULL;
+	map_get_object_void(&n->map, obj, &ret);
+	return ret;
 }

@@ -1,15 +1,11 @@
 #ifndef DECORATE_H
 #define DECORATE_H
 
-struct object_decoration {
-	const struct object *base;
-	void *decoration;
-};
+#include "map.h"
 
 struct decoration {
-	const char *name;
-	unsigned int size, nr;
-	struct object_decoration *hash;
+	char *name;
+	struct map_object_void map;
 };
 
 extern void *add_decoration(struct decoration *n, const struct object *obj, void *decoration);

@@ -86,3 +86,4 @@ int map_get_##name(struct map_##name *m, \
 }
 
 IMPLEMENT_MAP(object_uint32, obj_equal, hash_obj)
+IMPLEMENT_MAP(object_void, obj_equal, hash_obj)

@@ -24,5 +24,6 @@ extern int map_set_##name(struct map_##name *, \
 			  map_vtype_##name *old);
 
 DECLARE_MAP(object_uint32, const struct object *, uint32_t)
+DECLARE_MAP(object_void, const struct object *, void *)
 
 #endif /* MAP_H */

@@ -25,6 +25,21 @@ The decorate API provides a similar interface to map, but is restricted to
 using "struct object" as the key, and a void pointer as the value.
 
 
+Persistent Maps
+---------------
+
+Maps come in two flavors: persistent and in-core. In-core maps are
+represented by a hash table, and can contain any C type. Persistent maps
+are backed by flat storage, such as an mmap'd file, and store values
+between program runs. Key and value types must be serializable to
+fixed-width byte values.
+
+The flat storage is a sorted array of key/value pairs, with no
+delimiters between pairs or between elements of a pair.  Persistent maps
+uses an in-core map for newly-added values, and then merge the new
+values into the flat storage on request.
+
+
 Defining New Map Types
 ----------------------
 

@@ -50,6 +65,32 @@ define a new type, you must use the `DECLARE_MAP` macro in `map.h`, and the
 	should specify a function that will convert an object of type `ktype`
 	into an integer hash value.
 
+To define a persistent map, use these macros instead:
+
+`DECLARE_MAP_PERSIST`::
+
+	Declare a new persistent map. The `name` parameter must match a
+	map declared already with `DECLARE_MAP`.
+
+`IMPLEMENT_MAP_PERSIST`::
+
+	Create function definitions for a persistent map. The `name`
+	parameter must match one given to `DECLARE_MAP_PERSIST`.  The
+	`ksize` and `vsize` parameters indicate the size, in bytes, of
+	serialized keys and values.
++
+	The `k_to_disk` and `v_to_disk` parameters specify functions to
+	convert keys and values to their serialized formats; they take a
+	key (or value), and a pointer to memory of at least `ksize` (or
+	`vsize`) bytes to write into. The `disk_to_v` parameter
+	specifies a function to convert a pointer to `vsize` bytes of
+	serialized value into a `vtype`.
++
+	The `disk_lookup_fun` parameter should specify a function for
+	performing a search of the sorted flat disk array (it is given
+	the array, the number of elements, the size of the key and
+	value, and the key to lookup).
+
 Several convenience functions are provided to fill in macro parameters:
 
 `hash_obj`::

@@ -60,6 +101,26 @@ Several convenience functions are provided to fill in macro parameters:
 
 	Suitable for `equal_fun` when the key type is `struct object *`.
 
+`obj_to_disk`::
+
+	Suitable for `k_to_disk` when the key type is `struct object *`.
+
+`uint32_to_disk`::
+
+	Suitable for `k_to_disk` or `v_to_disk` when the type is
+	`uint32_t`. Integers are serialized in network byte order for
+	portability.
+
+`disk_to_uint32`::
+
+	Suitable for `disk_to_v` when the value type is `uint32_t`.
+	Integers are converted back to host byte order.
+
+`disk_lookup_sha1`::
+
+	Suitable for disk_lookup_fun when the serialized keys are sha1
+	hashes.
+
 
 Data Structures
 ---------------

@@ -83,6 +144,14 @@ Each defined map type will have its own structure (e.g., `map_object_uint32`).
 	single mapped pair.  You should never need to use this type directly,
 	unless you are enumerating all elements of a map.
 
+`struct map_persist_NAME`::
+
+	A persistent map. This struct should be initialized to
+	all-zeroes. The `map` field contains a complete in-core map. The
+	`disk_entries` and `disk_nr` fields specify the flat storage.
+	These should not be set directly, but rather through the
+	`attach` function.
+
 
 Functions
 ---------

@@ -102,6 +171,27 @@ Each defined map type will have its own set of access function (e.g.,
 	existed, the previous value is copied into `old` (if it is non-NULL)
 	and the function returns 1. Otherwise, the function returns 0.
 
+`map_persist_get_NAME(struct map_persist_NAME *, const ktype key, vtype *value)`::
+
+	Same as `map_get_NAME`, but for a persistent map.
+
+`map_persist_set_NAME(struct map_persist_NAME *, const ktype key, vtype value)`::
+
+	Same as `map_set_name`, but for a persistent map. It also does
+	not provide the "old" value for the key.
+
+`map_persist_attach_NAME`::
+
+	Attach storage from `buf` of size `len` bytes as the flat
+	backing store for the map. The map does not copy the storage;
+	the caller is responsible for making sure it stays around as
+	long as the map does.
+
+`map_persist_flush_NAME`::
+
+	Merge in-core entries with those found in the backing store, and
+	write the result to `fd`. Returns 0 for success, -1 for failure.
+
 
 Examples
 --------

@@ -158,3 +248,45 @@ void dump_foos(void)
 	}
 }
 -------------------------------------------------------------------
+
+Open and close a disk-backed persistent map of objects to 32-bit
+integers:
+
+-------------------------------------------------------------------
+static int fd;
+static const unsigned char *buf;
+static unsigned len;
+static struct map_persist_object_uint32 map;
+
+void open_map(const char *path)
+{
+	struct stat sb;
+	const unsigned char *p;
+
+	fd = open(path, O_RDONLY);
+	/* it's ok not to attach any backing store at all */
+	if (fd < 0)
+		return;
+
+	fstat(fd, &sb);
+	len = sb.st_size;
+	buf = xmmap(NULL, len, PROT_READ, MAP_PRIVATE, fd, 0);
+
+	map_persist_attach_object_uint32(&map, buf, len);
+}
+
+/* other functions call "get" and "set" */
+
+void close_map(const char *path, const char *tmp)
+{
+	int tmpfd;
+
+	tmpfd = open(tmp, O_RDONLY);
+	if (map_persist_flush_object_uint32(&map, tmpfd) < 0)
+		die_errno("unable to write new map");
+	close(tmpfd);
+	rename(tmp, path);
+
+	munmap(buf, len);
+	close(fd);
+}

@@ -1,6 +1,7 @@
 #include "cache.h"
 #include "map.h"
 #include "object.h"
+#include "sha1-lookup.h"
 
 static unsigned int hash_obj(const struct object *obj, unsigned int n)
 {

@@ -15,6 +16,74 @@ static int obj_equal(const struct object *a, const struct object *b)
 	return a == b;
 }
 
+static void obj_to_disk(const struct object *obj, unsigned char *out)
+{
+	hashcpy(out, obj->sha1);
+}
+
+static void uint32_to_disk(uint32_t v, unsigned char *out)
+{
+	v = htonl(v);
+	memcpy(out, &v, 4);
+}
+
+static void disk_to_uint32(const unsigned char *disk, uint32_t *out)
+{
+	memcpy(out, disk, 4);
+	*out = ntohl(*out);
+}
+
+static const unsigned char *disk_lookup_sha1(const unsigned char *buf,
+					     unsigned nr,
+					     unsigned ksize, unsigned vsize,
+					     const unsigned char *key)
+{
+	int pos;
+
+	pos = sha1_entry_pos(buf, ksize + vsize, 0, 0, nr, nr, key);
+	if (pos < 0)
+		return NULL;
+	return buf + (pos * (ksize + vsize)) + ksize;
+}
+
+static int merge_entries(int fd, int ksize, int vsize,
+			 const unsigned char *left, unsigned nr_left,
+			 const unsigned char *right, unsigned nr_right)
+{
+#define ADVANCE(name) \
+	do { \
+		name += ksize + vsize; \
+		nr_##name--; \
+	} while (0)
+#define WRITE_ENTRY(name) \
+	do { \
+		if (write_in_full(fd, name, ksize + vsize) < 0) \
+			return -1; \
+		ADVANCE(name); \
+	} while (0)
+
+	while (nr_left && nr_right) {
+		int cmp = memcmp(left, right, ksize);
+
+		/* skip duplicates, preferring left to right */
+		if (cmp == 0)
+			ADVANCE(right);
+		else if (cmp < 0)
+			WRITE_ENTRY(left);
+		else
+			WRITE_ENTRY(right);
+	}
+	while (nr_left)
+		WRITE_ENTRY(left);
+	while (nr_right)
+		WRITE_ENTRY(right);
+
+#undef WRITE_ENTRY
+#undef ADVANCE
+
+	return 0;
+}
+
 #define IMPLEMENT_MAP(name, equal_fun, hash_fun) \
 static int map_insert_##name(struct map_##name *m, \
 			     const map_ktype_##name key, \

@@ -85,5 +154,93 @@ int map_get_##name(struct map_##name *m, \
 	return 0; \
 }
 
+#define IMPLEMENT_MAP_PERSIST(name, \
+			      ksize, k_to_disk, \
+			      vsize, v_to_disk, disk_to_v, \
+			      disk_lookup_fun) \
+int map_persist_get_##name(struct map_persist_##name *m, \
+			   const map_ktype_##name key, \
+			   map_vtype_##name *value) \
+{ \
+	unsigned char disk_key[ksize]; \
+	const unsigned char *disk_value; \
+\
+	if (map_get_##name(&m->mem, key, value)) \
+		return 1; \
+\
+	if (!m->disk_entries) \
+		return 0; \
+\
+	k_to_disk(key, disk_key); \
+	disk_value = disk_lookup_fun(m->disk_entries, m->disk_nr, \
+				     ksize, vsize, disk_key); \
+	if (disk_value) { \
+		disk_to_v(disk_value, value); \
+		return 1; \
+	} \
+\
+	return 0; \
+} \
+\
+int map_persist_set_##name(struct map_persist_##name *m, \
+			   const map_ktype_##name key, \
+			   map_vtype_##name value) \
+{ \
+	return map_set_##name(&m->mem, key, value, NULL); \
+} \
+\
+static unsigned char *flatten_mem_entries_##name(struct map_persist_##name *m) \
+{ \
+	unsigned char *ret, *out; \
+	int i, nr; \
+\
+	out = ret = xmalloc(m->mem.nr * (ksize + vsize)); \
+	nr = 0; \
+	for (i = 0; i < m->mem.size; i++) { \
+		struct map_entry_##name *e = m->mem.hash + i; \
+\
+		if (!e->used) \
+			continue; \
+\
+		if (nr == m->mem.nr) \
+			die("BUG: map hash contained extra values"); \
+\
+		k_to_disk(e->key, out); \
+		out += ksize; \
+		v_to_disk(e->value, out); \
+		out += vsize; \
+	} \
+\
+	return ret; \
+} \
+\
+void map_persist_attach_##name(struct map_persist_##name *m, \
+			       const unsigned char *buf, \
+			       unsigned int len) \
+{ \
+	m->disk_entries = buf; \
+	m->disk_nr = len / (ksize + vsize); \
+} \
+\
+static int keycmp_##name(const void *a, const void *b) \
+{ \
+	return memcmp(a, b, ksize); \
+} \
+\
+int map_persist_flush_##name(struct map_persist_##name *m, int fd) \
+{ \
+	unsigned char *mem_entries; \
+	int r; \
+\
+	mem_entries = flatten_mem_entries_##name(m); \
+	qsort(mem_entries, m->mem.nr, ksize + vsize, keycmp_##name); \
+\
+	r = merge_entries(fd, ksize, vsize, \
+			  mem_entries, m->mem.nr, \
+			  m->disk_entries, m->disk_nr); \
+	free(mem_entries); \
+	return r; \
+}
+
 IMPLEMENT_MAP(object_uint32, obj_equal, hash_obj)
 IMPLEMENT_MAP(object_void, obj_equal, hash_obj)

@@ -23,6 +23,23 @@ extern int map_set_##name(struct map_##name *, \
 			  map_vtype_##name value, \
 			  map_vtype_##name *old);
 
+#define DECLARE_MAP_PERSIST(name) \
+struct map_persist_##name { \
+	struct map_##name mem; \
+	const unsigned char *disk_entries; \
+	unsigned int disk_nr; \
+}; \
+extern int map_persist_get_##name(struct map_persist_##name *, \
+			  const map_ktype_##name key, \
+			  map_vtype_##name *value); \
+extern int map_persist_set_##name(struct map_persist_##name *, \
+			  const map_ktype_##name key, \
+			  map_vtype_##name value); \
+extern void map_persist_attach_##name(struct map_persist_##name *, \
+				      const unsigned char *buf, \
+				      unsigned int len); \
+extern int map_persist_flush_##name(struct map_persist_##name *, int fd);
+
 DECLARE_MAP(object_uint32, const struct object *, uint32_t)
 DECLARE_MAP(object_void, const struct object *, void *)
 

@@ -0,0 +1,67 @@
+metadata cache API
+==================
+
+The metadata cache API provides simple-to-use, persistent key/value
+storage. It is built on the link:api-map.html[map API], so keys and
+values can have any serializable type.
+
+Caches are statically allocated, and no explicit initialization is
+required.  Callers can simply call the "get" and "set" functions for a
+given cache.  At program exit, any new entries in the cache are flushed
+to disk.
+
+
+Defining a New Cache
+--------------------
+
+You need to provide three pieces of information to define a new cache:
+
+name::
+	This name will be used both as part of the C identifier and as
+	part of the filename under which the cache is stored. Restrict
+	the characters used to alphanumerics and underscore.
+
+map::
+	The type of map (declared by `DECLARE_MAP`) that this cache will
+	store.
+
+validity::
+	A function that will generate a 20-byte "validity token"
+	representing the conditions under which the cache is valid.
+	For example, a cache that depended on the structure of the
+	history graph would be valid only under a given set of grafts
+	and replace refs. That set could be stirred into a sha1 and used
+	as a validity token.
+
+You must declare the cache in metadata-cache.h using
+`DECLARE_METADATA_CACHE`, and then implement it in metadata-cache.c
+using `IMPLEMENT_METADATA_CACHE`.
+
+
+Using a Cache
+-------------
+
+Interaction with a cache consists entirely of getting and setting
+values. No initialization or cleanup is required. The get and set
+functions mirror their "map" counterparts; see the
+link:api-map.html[map API] for details.
+
+
+File Format
+-----------
+
+Cache files are stored in the $GIT_DIR/cache directory. Each cache gets
+its own directory, named after the `name` parameter in the cache
+definition. Within each directory is a set of files, one cache per file,
+named after their validity tokens. Caches for multiple sets of
+conditions can simultaneously exist, and git will use whichever is
+appropriate.
+
+The files themselves consist of an 8-byte header. The first four bytes
+are the magic sequence "MTAC" (for "MeTA Cache"), followed by a 4-byte
+version number, in network byte order. This document describes version
+1.
+
+The rest of the file consists of the persistent map data. This is a
+compact, sorted list of keys and values; see the link:api-map.html[map
+API] for details.

@@ -536,6 +536,7 @@ LIB_H += mailmap.h
 LIB_H += map.h
 LIB_H += merge-file.h
 LIB_H += merge-recursive.h
+LIB_H += metadata-cache.h
 LIB_H += notes.h
 LIB_H += notes-cache.h
 LIB_H += notes-merge.h

@@ -629,6 +630,7 @@ LIB_OBJS += map.o
 LIB_OBJS += match-trees.o
 LIB_OBJS += merge-file.o
 LIB_OBJS += merge-recursive.o
+LIB_OBJS += metadata-cache.o
 LIB_OBJS += name-hash.o
 LIB_OBJS += notes.o
 LIB_OBJS += notes-cache.o

@@ -0,0 +1,126 @@
+#include "cache.h"
+#include "metadata-cache.h"
+#include "map.h"
+
+static const char *metadata_cache_path(const char *name,
+				       void (*validity)(unsigned char [20]))
+{
+	unsigned char token[20];
+
+	if (validity)
+		validity(token);
+	else
+		hashcpy(token, null_sha1);
+	return git_path("cache/%s/%s", name, sha1_to_hex(token));
+}
+
+#define IMPLEMENT_METADATA_CACHE(name, map, validity) \
+static struct map_persist_##map name##_map; \
+static int name##_fd; \
+static unsigned char *name##_buf; \
+static unsigned long name##_len; \
+\
+static void write_##name##_cache(void) \
+{ \
+	const char *path; \
+	struct strbuf tempfile = STRBUF_INIT; \
+	int fd = -1; \
+\
+	if (!name##_map.mem.nr) \
+		return; \
+\
+	path = metadata_cache_path(#name, validity); \
+	strbuf_addf(&tempfile, "%s.XXXXXX", path); \
+\
+	if (safe_create_leading_directories(tempfile.buf) < 0) \
+		goto fail; \
+	fd = git_mkstemp_mode(tempfile.buf, 0444); \
+	if (fd < 0) \
+		goto fail; \
+\
+	if (write_in_full(fd, "MTAC\x00\x00\x00\x01", 8) < 0) \
+		goto fail; \
+	if (map_persist_flush_##map(&name##_map, fd) < 0) \
+		goto fail; \
+	if (close(fd) < 0) \
+		goto fail; \
+	if (rename(tempfile.buf, path) < 0) \
+		goto fail; \
+\
+	strbuf_release(&tempfile); \
+	return; \
+\
+fail: \
+	close(fd); \
+	unlink(tempfile.buf); \
+	strbuf_release(&tempfile); \
+} \
+\
+static void init_##name##_cache(void) \
+{ \
+	static int initialized; \
+	const char *path; \
+	struct stat sb; \
+	const unsigned char *p; \
+	uint32_t version; \
+\
+	if (initialized) \
+		return; \
+\
+	atexit(write_##name##_cache); \
+	initialized = 1; \
+\
+	path = metadata_cache_path(#name, validity); \
+	name##_fd = open(path, O_RDONLY); \
+	if (name##_fd < 0) \
+		return; \
+\
+	if (fstat(name##_fd, &sb) < 0) \
+		goto fail; \
+	name##_len = sb.st_size; \
+	name##_buf = xmmap(NULL, sb.st_size, PROT_READ, MAP_PRIVATE, \
+				 name##_fd, 0); \
+\
+	if (name##_len < 8) { \
+		warning("cache '%s' is missing header", path); \
+		goto fail; \
+	} \
+	p = name##_buf; \
+	if (memcmp(p, "MTAC", 4)) { \
+		warning("cache '%s' has invalid magic: %c%c%c%c", \
+			path, p[0], p[1], p[2], p[3]); \
+		goto fail; \
+	} \
+	p += 4; \
+	memcpy(&version, p, 4); \
+	version = ntohl(version); \
+	if (version != 1) { \
+		warning("cache '%s' has unknown version: %"PRIu32, \
+			path, version); \
+		goto fail; \
+	} \
+\
+	map_persist_attach_##map(&name##_map, \
+				     name##_buf + 8, \
+				     name##_len - 8); \
+	return; \
+\
+fail: \
+	close(name##_fd); \
+	name##_fd = -1; \
+	if (name##_buf) \
+		munmap(name##_buf, name##_len); \
+	name##_buf = NULL; \
+	name##_len = 0; \
+} \
+\
+int name##_cache_get(map_ktype_##map key, map_vtype_##map *value) \
+{ \
+	init_##name##_cache(); \
+	return map_persist_get_##map(&name##_map, key, value); \
+} \
+int name##_cache_set(map_ktype_##map key, map_vtype_##map value) \
+{ \
+	init_##name##_cache(); \
+	return map_persist_set_##map(&name##_map, key, value); \
+}

@@ -0,0 +1,10 @@
+#ifndef METADATA_CACHE_H
+#define METADATA_CACHE_H
+
+#include "map.h"
+
+#define DECLARE_METADATA_CACHE(name, map) \
+extern int name##_cache_get(map_ktype_##map key, map_vtype_##map *value); \
+extern int name##_cache_set(map_ktype_##map key, map_vtype_##map value);
+
+#endif /* METADATA_CACHE_H */

@@ -1438,6 +1438,8 @@ int cmd_cherry(int argc, const char **argv, const char *prefix)
 		OPT_END()
 	};
 
+	git_config(git_default_config, NULL);
+
 	argc = parse_options(argc, argv, prefix, options, cherry_usage, 0);
 
 	switch (argc) {

@@ -596,6 +596,7 @@ extern int read_replace_refs;
 extern int fsync_object_files;
 extern int core_preload_index;
 extern int core_apply_sparse_checkout;
+extern int core_cache_patch_id;
 
 enum branch_track {
 	BRANCH_TRACK_UNSPECIFIED = -1,

@@ -659,6 +659,11 @@ static int git_default_core_config(const char *var, const char *value)
 		return 0;
 	}
 
+	if (!strcmp(var, "core.cachepatchid")) {
+		core_cache_patch_id = git_config_bool(var, value);
+		return 0;
+	}
+
 	/* Add other config variables here and to Documentation/config.txt. */
 	return 0;
 }

@@ -33,6 +33,16 @@ static void disk_to_uint32(const unsigned char *disk, uint32_t *out)
 	*out = ntohl(*out);
 }
 
+static void sha1_to_disk(struct sha1 v, unsigned char *out)
+{
+	hashcpy(out, v.v);
+}
+
+static void disk_to_sha1(const unsigned char *disk, struct sha1 *out)
+{
+	hashcpy(out->v, disk);
+}
+
 static const unsigned char *disk_lookup_sha1(const unsigned char *buf,
 					     unsigned nr,
 					     unsigned ksize, unsigned vsize,

@@ -244,3 +254,9 @@ int map_persist_flush_##name(struct map_persist_##name *m, int fd) \
 
 IMPLEMENT_MAP(object_uint32, obj_equal, hash_obj)
 IMPLEMENT_MAP(object_void, obj_equal, hash_obj)
+
+IMPLEMENT_MAP(object_sha1, obj_equal, hash_obj)
+IMPLEMENT_MAP_PERSIST(object_sha1,
+		      20, obj_to_disk,
+		      20, sha1_to_disk, disk_to_sha1,
+		      disk_lookup_sha1)

@@ -40,7 +40,13 @@ extern void map_persist_attach_##name(struct map_persist_##name *, \
 				      unsigned int len); \
 extern int map_persist_flush_##name(struct map_persist_##name *, int fd);
 
+struct sha1 {
+	unsigned char v[20];
+};
+
 DECLARE_MAP(object_uint32, const struct object *, uint32_t)
 DECLARE_MAP(object_void, const struct object *, void *)
+DECLARE_MAP(object_sha1, const struct object *, struct sha1)
+DECLARE_MAP_PERSIST(object_sha1)
 
 #endif /* MAP_H */