[PATCH 00/28] Store references hierarchically in cache

[PATCH 00/28] Store references hierarchically in cache

[mhagger]

From: Michael Haggerty <mhagger@alum.mit.edu>

This patch series applies on top of v3 of "Use refs API more
consistently", which ultimately branches from gitster/master.

This patch series changes how references are stored in the reference
cache data structures (entirely internal to refs.c).  Previously, the
packed refs were stored in one big array of pointers-to-struct, and
the loose refs were stored in another.  This had a few problems:

* Whenever any loose refs were needed, the whole refs tree had to be
  read from disk into memory.  This can be quite expensive when there
  are a lot of loose references.  And it is often overkill, as
  frequently only a small part of the refs tree is needed.  For
  example:

  * refs/replace is almost *always* needed even though it often
    doesn't even exist.  Thus the presence of many loose references
    slows down *many* git commands for no reason whatsoever.

  * When a new reference is created, is_refname_available() is called
    to see whether there is another another reference whose name
    conflicts with the new one.  Currently this loads and iterates
    through *all* references.  But there are only a few refnames that
    can possibly conflict; for example, given the refname
    "refs/heads/foo/bar", the only possible conflicts are with
    "refs/heads/foo" and "refs/heads/foo/bar/*".  Therefore it is
    silly to load and iterate through the whole refname hierarchy.

  * "git for-each-ref" is capable of searching a subtree of the
    references.  But currently this causes all references to be
    loaded.

Therefore, this patch series changes the data structure used to store
the reference cache from a single array of pointers-to-struct into a
tree-like structure in which each subdirectory of the reference
namespace is stored as an array of pointers-to-entry and entries can
be either references or subdirectories containing more references.
Moreover, each subdirectory of loose references is only read from disk
when a reference from that subdirectory (or one of its descendants) is
needed.  This slightly slows down commands that need to iterate
through all references (simply because the new data structures are
more complicated), but it *dramatically* decreases the time needed for
some common operations.  For example, in a test repository with 20000
revisions and 10000 loose tags:

* the time to create a new branch goes from 180 ms to less than 10 ms
  (my test resolution only includes two decimal places) and the time
  to checkout a new branch does the same.

* the time for a "git filter-branch" of all commits (which used to
  scale like N^2) goes from 4 hours to 13 minutes.  (Since
  filter-branch necessarily *creates* lots of loose references, the
  savings are also there if the references are originally packed.)

The efficiency gains are such that some operations are now faster with
loose references than with packed references; however, some operations
with packed references slow down a bit.

These changes do not increase the amount of space per reference needed
for the reference cache, but they do add one similarly-sized entry for
each subdirectory (for each of loose and packed).  I don't think that
the space increase should be significant in any reasonable situation.

After these changes, there is a benefit to sharding the reference
namespace, especially for loose references.


The patches:

The first few patches are just preparation.

Patch 6 "refs: store references hierarchically" introduces the big
data structure change.  It causes much extra sorting to be done and
therefore slows down performance significantly, but the following two
commits restore performance to approximately the old level.

Patches 11-24 change most of the internal functions to work with
"struct ref_entry *" (namely the kind of ref_entry that holds a
directory of references) instead of "struct ref_dir *".  The reason
for this change it to allow these functions access to the "flag" and
"name" fields that are stored in ref_entry and thereby avoid having to
store redundant information in "struct ref_dir" (which would increase
the size of *every* ref_entry because of its presence in the union).

The other patches (9-10 and 25-28) reap the benefits of the new data
structure:

* do_for_each_ref() can iterate only over the desired subtree instead
  of iterating over all references and filtering out the unwanted ones

* loose references can be read on demand, one directory at a time

* is_refname_available() can query only the possibly-conflicting parts
  of the reference namespace

Michael Haggerty (28):
  refs.c: reorder definitions more logically
  free_ref_entry(): new function
  check_refname_component(): return 0 for zero-length components
  struct ref_entry: nest the value part in a union
  refs.c: rename ref_array -> ref_dir
  refs: store references hierarchically
  sort_ref_dir(): do not sort if already sorted
  refs: sort ref_dirs lazily
  do_for_each_ref(): only iterate over the subtree that was requested
  get_ref_dir(): keep track of the current ref_dir
  refs: wrap top-level ref_dirs in ref_entries
  get_packed_refs(): return (ref_entry *) instead of (ref_dir *)
  get_loose_refs(): return (ref_entry *) instead of (ref_dir *)
  is_refname_available(): take (ref_entry *) instead of (ref_dir *)
  find_ref(): take (ref_entry *) instead of (ref_dir *)
  read_packed_refs(): take (ref_entry *) instead of (ref_dir *)
  add_ref(): take (ref_entry *) instead of (ref_dir *)
  find_containing_direntry(): use (ref_entry *) instead of (ref_dir *)
  search_ref_dir(): take (ref_entry *) instead of (ref_dir *)
  add_entry(): take (ref_entry *) instead of (ref_dir *)
  do_for_each_ref_in_dir*(): take (ref_entry *) instead of (ref_dir *)
  sort_ref_dir(): take (ref_entry *) instead of (ref_dir *)
  struct ref_dir: store a reference to the enclosing ref_cache
  read_loose_refs(): take a (ref_entry *) as argument
  refs: read loose references lazily
  is_refname_available(): query only possibly-conflicting references
  read_packed_refs(): keep track of the directory being worked in
  repack_without_ref(): call clear_packed_ref_cache()

 refs.c | 1268 ++++++++++++++++++++++++++++++++++++++++++---------------------
 refs.h |    7 +-
 2 files changed, 850 insertions(+), 425 deletions(-)

-- 
1.7.7

[PATCH 01/28] refs.c: reorder definitions more logically

[mhagger]

From: Michael Haggerty <mhagger@alum.mit.edu>

Reorder definitions in file: first check_refname_format() and helper
functions, then the functions for managing the ref_entry and ref_array
data structures, then ref_cache, then the more "business-logicky"
stuff.  No code is changed.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs.c |  669 ++++++++++++++++++++++++++++++++--------------------------------
 1 files changed, 336 insertions(+), 333 deletions(-)

diff --git a/refs.c b/refs.c
index 96466f3..56868a5 100644
--- a/refs.c
+++ b/refs.c
@@ -4,6 +4,108 @@
 #include "tag.h"
 #include "dir.h"
 
+/*
+ * Make sure "ref" is something reasonable to have under ".git/refs/";
+ * We do not like it if:
+ *
+ * - any path component of it begins with ".", or
+ * - it has double dots "..", or
+ * - it has ASCII control character, "~", "^", ":" or SP, anywhere, or
+ * - it ends with a "/".
+ * - it ends with ".lock"
+ * - it contains a "\" (backslash)
+ */
+
+/* Return true iff ch is not allowed in reference names. */
+static inline int bad_ref_char(int ch)
+{
+	if (((unsigned) ch) <= ' ' || ch == 0x7f ||
+	    ch == '~' || ch == '^' || ch == ':' || ch == '\\')
+		return 1;
+	/* 2.13 Pattern Matching Notation */
+	if (ch == '*' || ch == '?' || ch == '[') /* Unsupported */
+		return 1;
+	return 0;
+}
+
+/*
+ * Try to read one refname component from the front of refname.  Return
+ * the length of the component found, or -1 if the component is not
+ * legal.
+ */
+static int check_refname_component(const char *refname, int flags)
+{
+	const char *cp;
+	char last = '\0';
+
+	for (cp = refname; ; cp++) {
+		char ch = *cp;
+		if (ch == '\0' || ch == '/')
+			break;
+		if (bad_ref_char(ch))
+			return -1; /* Illegal character in refname. */
+		if (last == '.' && ch == '.')
+			return -1; /* Refname contains "..". */
+		if (last == '@' && ch == '{')
+			return -1; /* Refname contains "@{". */
+		last = ch;
+	}
+	if (cp == refname)
+		return -1; /* Component has zero length. */
+	if (refname[0] == '.') {
+		if (!(flags & REFNAME_DOT_COMPONENT))
+			return -1; /* Component starts with '.'. */
+		/*
+		 * Even if leading dots are allowed, don't allow "."
+		 * as a component (".." is prevented by a rule above).
+		 */
+		if (refname[1] == '\0')
+			return -1; /* Component equals ".". */
+	}
+	if (cp - refname >= 5 && !memcmp(cp - 5, ".lock", 5))
+		return -1; /* Refname ends with ".lock". */
+	return cp - refname;
+}
+
+int check_refname_format(const char *refname, int flags)
+{
+	int component_len, component_count = 0;
+
+	while (1) {
+		/* We are at the start of a path component. */
+		component_len = check_refname_component(refname, flags);
+		if (component_len < 0) {
+			if ((flags & REFNAME_REFSPEC_PATTERN) &&
+					refname[0] == '*' &&
+					(refname[1] == '\0' || refname[1] == '/')) {
+				/* Accept one wildcard as a full refname component. */
+				flags &= ~REFNAME_REFSPEC_PATTERN;
+				component_len = 1;
+			} else {
+				return -1;
+			}
+		}
+		component_count++;
+		if (refname[component_len] == '\0')
+			break;
+		/* Skip to next component. */
+		refname += component_len + 1;
+	}
+
+	if (refname[component_len - 1] == '.')
+		return -1; /* Refname ends with '.'. */
+	if (!(flags & REFNAME_ALLOW_ONELEVEL) && component_count < 2)
+		return -1; /* Refname has only one component. */
+	return 0;
+}
+
+struct ref_entry;
+
+struct ref_array {
+	int nr, alloc;
+	struct ref_entry **refs;
+};
+
 /* ISSYMREF=0x01, ISPACKED=0x02 and ISBROKEN=0x04 are public interfaces */
 #define REF_KNOWS_PEELED 0x10
 
@@ -15,47 +117,6 @@ struct ref_entry {
 	char name[FLEX_ARRAY];
 };
 
-struct ref_array {
-	int nr, alloc;
-	struct ref_entry **refs;
-};
-
-/*
- * Parse one line from a packed-refs file.  Write the SHA1 to sha1.
- * Return a pointer to the refname within the line (null-terminated),
- * or NULL if there was a problem.
- */
-static const char *parse_ref_line(char *line, unsigned char *sha1)
-{
-	/*
-	 * 42: the answer to everything.
-	 *
-	 * In this case, it happens to be the answer to
-	 *  40 (length of sha1 hex representation)
-	 *  +1 (space in between hex and name)
-	 *  +1 (newline at the end of the line)
-	 */
-	int len = strlen(line) - 42;
-
-	if (len <= 0)
-		return NULL;
-	if (get_sha1_hex(line, sha1) < 0)
-		return NULL;
-	if (!isspace(line[40]))
-		return NULL;
-	line += 41;
-	if (isspace(*line))
-		return NULL;
-	if (line[len] != '\n')
-		return NULL;
-	line[len] = 0;
-
-	if (check_refname_format(line, REFNAME_ALLOW_ONELEVEL))
-		return NULL;
-
-	return line;
-}
-
 static struct ref_entry *create_ref_entry(const char *refname,
 					  const unsigned char *sha1, int flag)
 {
@@ -80,6 +141,16 @@ static void add_ref(struct ref_array *refs, struct ref_entry *ref)
 	refs->refs[refs->nr++] = ref;
 }
 
+static void clear_ref_array(struct ref_array *array)
+{
+	int i;
+	for (i = 0; i < array->nr; i++)
+		free(array->refs[i]);
+	free(array->refs);
+	array->nr = array->alloc = 0;
+	array->refs = NULL;
+}
+
 static int ref_entry_cmp(const void *a, const void *b)
 {
 	struct ref_entry *one = *(struct ref_entry **)a;
@@ -87,6 +158,31 @@ static int ref_entry_cmp(const void *a, const void *b)
 	return strcmp(one->name, two->name);
 }
 
+static struct ref_entry *search_ref_array(struct ref_array *array, const char *refname)
+{
+	struct ref_entry *e, **r;
+	int len;
+
+	if (refname == NULL)
+		return NULL;
+
+	if (!array->nr)
+		return NULL;
+
+	len = strlen(refname) + 1;
+	e = xmalloc(sizeof(struct ref_entry) + len);
+	memcpy(e->name, refname, len);
+
+	r = bsearch(&e, array->refs, array->nr, sizeof(*array->refs), ref_entry_cmp);
+
+	free(e);
+
+	if (r == NULL)
+		return NULL;
+
+	return *r;
+}
+
 /*
  * Emit a warning and return true iff ref1 and ref2 have the same name
  * and the same sha1.  Die if they have the same name but different
@@ -130,29 +226,137 @@ static void sort_ref_array(struct ref_array *array)
 	array->nr = i + 1;
 }
 
-static struct ref_entry *search_ref_array(struct ref_array *array, const char *refname)
+#define DO_FOR_EACH_INCLUDE_BROKEN 01
+
+static struct ref_entry *current_ref;
+
+static int do_one_ref(const char *base, each_ref_fn fn, int trim,
+		      int flags, void *cb_data, struct ref_entry *entry)
 {
-	struct ref_entry *e, **r;
-	int len;
+	if (prefixcmp(entry->name, base))
+		return 0;
 
-	if (refname == NULL)
-		return NULL;
+	if (!(flags & DO_FOR_EACH_INCLUDE_BROKEN)) {
+		if (entry->flag & REF_ISBROKEN)
+			return 0; /* ignore broken refs e.g. dangling symref */
+		if (!has_sha1_file(entry->sha1)) {
+			error("%s does not point to a valid object!", entry->name);
+			return 0;
+		}
+	}
+	current_ref = entry;
+	return fn(entry->name + trim, entry->sha1, entry->flag, cb_data);
+}
 
-	if (!array->nr)
-		return NULL;
+static int do_for_each_ref_in_array(struct ref_array *array, int offset,
+				    const char *base,
+				    each_ref_fn fn, int trim, int flags, void *cb_data)
+{
+	int i;
+	for (i = offset; i < array->nr; i++) {
+		int retval = do_one_ref(base, fn, trim, flags, cb_data, array->refs[i]);
+		if (retval)
+			return retval;
+	}
+	return 0;
+}
 
-	len = strlen(refname) + 1;
-	e = xmalloc(sizeof(struct ref_entry) + len);
-	memcpy(e->name, refname, len);
+static int do_for_each_ref_in_arrays(struct ref_array *array1,
+				     struct ref_array *array2,
+				     const char *base, each_ref_fn fn, int trim,
+				     int flags, void *cb_data)
+{
+	int retval;
+	int i1 = 0, i2 = 0;
 
-	r = bsearch(&e, array->refs, array->nr, sizeof(*array->refs), ref_entry_cmp);
+	while (1) {
+		struct ref_entry *e1, *e2;
+		int cmp;
+		if (i1 == array1->nr) {
+			return do_for_each_ref_in_array(array2, i2,
+							base, fn, trim, flags, cb_data);
+		}
+		if (i2 == array2->nr) {
+			return do_for_each_ref_in_array(array1, i1,
+							base, fn, trim, flags, cb_data);
+		}
+		e1 = array1->refs[i1];
+		e2 = array2->refs[i2];
+		cmp = strcmp(e1->name, e2->name);
+		if (cmp == 0) {
+			/* Two refs with the same name; ignore the one from array1. */
+			i1++;
+			continue;
+		}
+		if (cmp < 0) {
+			retval = do_one_ref(base, fn, trim, flags, cb_data, e1);
+			i1++;
+		} else {
+			retval = do_one_ref(base, fn, trim, flags, cb_data, e2);
+			i2++;
+		}
+		if (retval)
+			return retval;
+	}
+}
 
-	free(e);
+/*
+ * Return true iff refname1 and refname2 conflict with each other.
+ * Two reference names conflict if one of them exactly matches the
+ * leading components of the other; e.g., "foo/bar" conflicts with
+ * both "foo" and with "foo/bar/baz" but not with "foo/bar" or
+ * "foo/barbados".
+ */
+static int names_conflict(const char *refname1, const char *refname2)
+{
+	for (; *refname1 && *refname1 == *refname2; refname1++, refname2++)
+		;
+	return (*refname1 == '\0' && *refname2 == '/')
+		|| (*refname1 == '/' && *refname2 == '\0');
+}
 
-	if (r == NULL)
-		return NULL;
+struct name_conflict_cb {
+	const char *refname;
+	const char *oldrefname;
+	const char *conflicting_refname;
+};
 
-	return *r;
+static int name_conflict_fn(const char *existingrefname, const unsigned char *sha1,
+			    int flags, void *cb_data)
+{
+	struct name_conflict_cb *data = (struct name_conflict_cb *)cb_data;
+	if (data->oldrefname && !strcmp(data->oldrefname, existingrefname))
+		return 0;
+	if (names_conflict(data->refname, existingrefname)) {
+		data->conflicting_refname = existingrefname;
+		return 1;
+	}
+	return 0;
+}
+
+/*
+ * Return true iff a reference named refname could be created without
+ * conflicting with the name of an existing reference.  If oldrefname
+ * is non-NULL, ignore potential conflicts with oldrefname (e.g.,
+ * because oldrefname is scheduled for deletion in the same
+ * operation).
+ */
+static int is_refname_available(const char *refname, const char *oldrefname,
+				struct ref_array *array)
+{
+	struct name_conflict_cb data;
+	data.refname = refname;
+	data.oldrefname = oldrefname;
+	data.conflicting_refname = NULL;
+
+	if (do_for_each_ref_in_array(array, 0, "", name_conflict_fn,
+				     0, DO_FOR_EACH_INCLUDE_BROKEN,
+				     &data)) {
+		error("'%s' exists; cannot create '%s'",
+		      data.conflicting_refname, refname);
+		return 0;
+	}
+	return 1;
 }
 
 /*
@@ -169,20 +373,8 @@ static struct ref_cache {
 	char name[FLEX_ARRAY];
 } *ref_cache;
 
-static struct ref_entry *current_ref;
-
 static struct ref_array extra_refs;
 
-static void clear_ref_array(struct ref_array *array)
-{
-	int i;
-	for (i = 0; i < array->nr; i++)
-		free(array->refs[i]);
-	free(array->refs);
-	array->nr = array->alloc = 0;
-	array->refs = NULL;
-}
-
 static void clear_packed_ref_cache(struct ref_cache *refs)
 {
 	if (refs->did_packed)
@@ -239,6 +431,42 @@ void invalidate_ref_cache(const char *submodule)
 	clear_loose_ref_cache(refs);
 }
 
+/*
+ * Parse one line from a packed-refs file.  Write the SHA1 to sha1.
+ * Return a pointer to the refname within the line (null-terminated),
+ * or NULL if there was a problem.
+ */
+static const char *parse_ref_line(char *line, unsigned char *sha1)
+{
+	/*
+	 * 42: the answer to everything.
+	 *
+	 * In this case, it happens to be the answer to
+	 *  40 (length of sha1 hex representation)
+	 *  +1 (space in between hex and name)
+	 *  +1 (newline at the end of the line)
+	 */
+	int len = strlen(line) - 42;
+
+	if (len <= 0)
+		return NULL;
+	if (get_sha1_hex(line, sha1) < 0)
+		return NULL;
+	if (!isspace(line[40]))
+		return NULL;
+	line += 41;
+	if (isspace(*line))
+		return NULL;
+	if (line[len] != '\n')
+		return NULL;
+	line[len] = 0;
+
+	if (check_refname_format(line, REFNAME_ALLOW_ONELEVEL))
+		return NULL;
+
+	return line;
+}
+
 static void read_packed_refs(FILE *f, struct ref_array *array)
 {
 	struct ref_entry *last = NULL;
@@ -355,53 +583,19 @@ static void get_ref_dir(struct ref_cache *refs, const char *base,
 				hashclr(sha1);
 				flag = 0;
 				if (resolve_gitlink_ref(refs->name, refname, sha1) < 0) {
-					hashclr(sha1);
-					flag |= REF_ISBROKEN;
-				}
-			} else
-				if (!resolve_ref(refname, sha1, 1, &flag)) {
-					hashclr(sha1);
-					flag |= REF_ISBROKEN;
-				}
-			add_ref(array, create_ref_entry(refname, sha1, flag));
-		}
-		free(refname);
-		closedir(dir);
-	}
-}
-
-struct warn_if_dangling_data {
-	FILE *fp;
-	const char *refname;
-	const char *msg_fmt;
-};
-
-static int warn_if_dangling_symref(const char *refname, const unsigned char *sha1,
-				   int flags, void *cb_data)
-{
-	struct warn_if_dangling_data *d = cb_data;
-	const char *resolves_to;
-	unsigned char junk[20];
-
-	if (!(flags & REF_ISSYMREF))
-		return 0;
-
-	resolves_to = resolve_ref(refname, junk, 0, NULL);
-	if (!resolves_to || strcmp(resolves_to, d->refname))
-		return 0;
-
-	fprintf(d->fp, d->msg_fmt, refname);
-	return 0;
-}
-
-void warn_dangling_symref(FILE *fp, const char *msg_fmt, const char *refname)
-{
-	struct warn_if_dangling_data data;
-
-	data.fp = fp;
-	data.refname = refname;
-	data.msg_fmt = msg_fmt;
-	for_each_rawref(warn_if_dangling_symref, &data);
+					hashclr(sha1);
+					flag |= REF_ISBROKEN;
+				}
+			} else
+				if (!resolve_ref(refname, sha1, 1, &flag)) {
+					hashclr(sha1);
+					flag |= REF_ISBROKEN;
+				}
+			add_ref(array, create_ref_entry(refname, sha1, flag));
+		}
+		free(refname);
+		closedir(dir);
+	}
 }
 
 static struct ref_array *get_loose_refs(struct ref_cache *refs)
@@ -631,27 +825,8 @@ int read_ref(const char *refname, unsigned char *sha1)
 	return -1;
 }
 
-#define DO_FOR_EACH_INCLUDE_BROKEN 01
-static int do_one_ref(const char *base, each_ref_fn fn, int trim,
-		      int flags, void *cb_data, struct ref_entry *entry)
-{
-	if (prefixcmp(entry->name, base))
-		return 0;
-
-	if (!(flags & DO_FOR_EACH_INCLUDE_BROKEN)) {
-		if (entry->flag & REF_ISBROKEN)
-			return 0; /* ignore broken refs e.g. dangling symref */
-		if (!has_sha1_file(entry->sha1)) {
-			error("%s does not point to a valid object!", entry->name);
-			return 0;
-		}
-	}
-	current_ref = entry;
-	return fn(entry->name + trim, entry->sha1, entry->flag, cb_data);
-}
-
 static int filter_refs(const char *refname, const unsigned char *sha, int flags,
-	void *data)
+		       void *data)
 {
 	struct ref_filter *filter = (struct ref_filter *)data;
 	if (fnmatch(filter->pattern, refname, 0))
@@ -700,56 +875,38 @@ fallback:
 	return -1;
 }
 
-static int do_for_each_ref_in_array(struct ref_array *array, int offset,
-				    const char *base,
-				    each_ref_fn fn, int trim, int flags, void *cb_data)
+struct warn_if_dangling_data {
+	FILE *fp;
+	const char *refname;
+	const char *msg_fmt;
+};
+
+static int warn_if_dangling_symref(const char *refname, const unsigned char *sha1,
+				   int flags, void *cb_data)
 {
-	int i;
-	for (i = offset; i < array->nr; i++) {
-		int retval = do_one_ref(base, fn, trim, flags, cb_data, array->refs[i]);
-		if (retval)
-			return retval;
-	}
+	struct warn_if_dangling_data *d = cb_data;
+	const char *resolves_to;
+	unsigned char junk[20];
+
+	if (!(flags & REF_ISSYMREF))
+		return 0;
+
+	resolves_to = resolve_ref(refname, junk, 0, NULL);
+	if (!resolves_to || strcmp(resolves_to, d->refname))
+		return 0;
+
+	fprintf(d->fp, d->msg_fmt, refname);
 	return 0;
 }
 
-static int do_for_each_ref_in_arrays(struct ref_array *array1,
-				     struct ref_array *array2,
-				     const char *base, each_ref_fn fn, int trim,
-				     int flags, void *cb_data)
+void warn_dangling_symref(FILE *fp, const char *msg_fmt, const char *refname)
 {
-	int retval;
-	int i1 = 0, i2 = 0;
+	struct warn_if_dangling_data data;
 
-	while (1) {
-		struct ref_entry *e1, *e2;
-		int cmp;
-		if (i1 == array1->nr) {
-			return do_for_each_ref_in_array(array2, i2,
-							base, fn, trim, flags, cb_data);
-		}
-		if (i2 == array2->nr) {
-			return do_for_each_ref_in_array(array1, i1,
-							base, fn, trim, flags, cb_data);
-		}
-		e1 = array1->refs[i1];
-		e2 = array2->refs[i2];
-		cmp = strcmp(e1->name, e2->name);
-		if (cmp == 0) {
-			/* Two refs with the same name; ignore the one from array1. */
-			i1++;
-			continue;
-		}
-		if (cmp < 0) {
-			retval = do_one_ref(base, fn, trim, flags, cb_data, e1);
-			i1++;
-		} else {
-			retval = do_one_ref(base, fn, trim, flags, cb_data, e2);
-			i2++;
-		}
-		if (retval)
-			return retval;
-	}
+	data.fp = fp;
+	data.refname = refname;
+	data.msg_fmt = msg_fmt;
+	for_each_rawref(warn_if_dangling_symref, &data);
 }
 
 static int do_for_each_ref(const char *submodule, const char *base, each_ref_fn fn,
@@ -920,101 +1077,6 @@ int for_each_rawref(each_ref_fn fn, void *cb_data)
 			       DO_FOR_EACH_INCLUDE_BROKEN, cb_data);
 }
 
-/*
- * Make sure "ref" is something reasonable to have under ".git/refs/";
- * We do not like it if:
- *
- * - any path component of it begins with ".", or
- * - it has double dots "..", or
- * - it has ASCII control character, "~", "^", ":" or SP, anywhere, or
- * - it ends with a "/".
- * - it ends with ".lock"
- * - it contains a "\" (backslash)
- */
-
-/* Return true iff ch is not allowed in reference names. */
-static inline int bad_ref_char(int ch)
-{
-	if (((unsigned) ch) <= ' ' || ch == 0x7f ||
-	    ch == '~' || ch == '^' || ch == ':' || ch == '\\')
-		return 1;
-	/* 2.13 Pattern Matching Notation */
-	if (ch == '*' || ch == '?' || ch == '[') /* Unsupported */
-		return 1;
-	return 0;
-}
-
-/*
- * Try to read one refname component from the front of refname.  Return
- * the length of the component found, or -1 if the component is not
- * legal.
- */
-static int check_refname_component(const char *refname, int flags)
-{
-	const char *cp;
-	char last = '\0';
-
-	for (cp = refname; ; cp++) {
-		char ch = *cp;
-		if (ch == '\0' || ch == '/')
-			break;
-		if (bad_ref_char(ch))
-			return -1; /* Illegal character in refname. */
-		if (last == '.' && ch == '.')
-			return -1; /* Refname contains "..". */
-		if (last == '@' && ch == '{')
-			return -1; /* Refname contains "@{". */
-		last = ch;
-	}
-	if (cp == refname)
-		return -1; /* Component has zero length. */
-	if (refname[0] == '.') {
-		if (!(flags & REFNAME_DOT_COMPONENT))
-			return -1; /* Component starts with '.'. */
-		/*
-		 * Even if leading dots are allowed, don't allow "."
-		 * as a component (".." is prevented by a rule above).
-		 */
-		if (refname[1] == '\0')
-			return -1; /* Component equals ".". */
-	}
-	if (cp - refname >= 5 && !memcmp(cp - 5, ".lock", 5))
-		return -1; /* Refname ends with ".lock". */
-	return cp - refname;
-}
-
-int check_refname_format(const char *refname, int flags)
-{
-	int component_len, component_count = 0;
-
-	while (1) {
-		/* We are at the start of a path component. */
-		component_len = check_refname_component(refname, flags);
-		if (component_len < 0) {
-			if ((flags & REFNAME_REFSPEC_PATTERN) &&
-					refname[0] == '*' &&
-					(refname[1] == '\0' || refname[1] == '/')) {
-				/* Accept one wildcard as a full refname component. */
-				flags &= ~REFNAME_REFSPEC_PATTERN;
-				component_len = 1;
-			} else {
-				return -1;
-			}
-		}
-		component_count++;
-		if (refname[component_len] == '\0')
-			break;
-		/* Skip to next component. */
-		refname += component_len + 1;
-	}
-
-	if (refname[component_len - 1] == '.')
-		return -1; /* Refname ends with '.'. */
-	if (!(flags & REFNAME_ALLOW_ONELEVEL) && component_count < 2)
-		return -1; /* Refname has only one component. */
-	return 0;
-}
-
 const char *prettify_refname(const char *name)
 {
 	return name + (
@@ -1092,65 +1154,6 @@ static int remove_empty_directories(const char *file)
 }
 
 /*
- * Return true iff refname1 and refname2 conflict with each other.
- * Two reference names conflict if one of them exactly matches the
- * leading components of the other; e.g., "foo/bar" conflicts with
- * both "foo" and with "foo/bar/baz" but not with "foo/bar" or
- * "foo/barbados".
- */
-static int names_conflict(const char *refname1, const char *refname2)
-{
-	for (; *refname1 && *refname1 == *refname2; refname1++, refname2++)
-		;
-	return (*refname1 == '\0' && *refname2 == '/')
-		|| (*refname1 == '/' && *refname2 == '\0');
-}
-
-struct name_conflict_cb {
-	const char *refname;
-	const char *oldrefname;
-	const char *conflicting_refname;
-};
-
-static int name_conflict_fn(const char *existingrefname, const unsigned char *sha1,
-			    int flags, void *cb_data)
-{
-	struct name_conflict_cb *data = (struct name_conflict_cb *)cb_data;
-	if (data->oldrefname && !strcmp(data->oldrefname, existingrefname))
-		return 0;
-	if (names_conflict(data->refname, existingrefname)) {
-		data->conflicting_refname = existingrefname;
-		return 1;
-	}
-	return 0;
-}
-
-/*
- * Return true iff a reference named refname could be created without
- * conflicting with the name of an existing reference.  If oldrefname
- * is non-NULL, ignore potential conflicts with oldrefname (e.g.,
- * because oldrefname is scheduled for deletion in the same
- * operation).
- */
-static int is_refname_available(const char *refname, const char *oldrefname,
-				struct ref_array *array)
-{
-	struct name_conflict_cb data;
-	data.refname = refname;
-	data.oldrefname = oldrefname;
-	data.conflicting_refname = NULL;
-
-	if (do_for_each_ref_in_array(array, 0, "", name_conflict_fn,
-				     0, DO_FOR_EACH_INCLUDE_BROKEN,
-				     &data)) {
-		error("'%s' exists; cannot create '%s'",
-		      data.conflicting_refname, refname);
-		return 0;
-	}
-	return 1;
-}
-
-/*
  * *string and *len will only be substituted, and *string returned (for
  * later free()ing) if the string passed in is a magic short-hand form
  * to name a branch.
-- 
1.7.7

[PATCH 02/28] free_ref_entry(): new function

[mhagger]

From: Michael Haggerty <mhagger@alum.mit.edu>

Add a function free_ref_entry().  This function will become nontrivial
when ref_entry (soon) becomes polymorphic.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs.c |    9 +++++++--
 1 files changed, 7 insertions(+), 2 deletions(-)

diff --git a/refs.c b/refs.c
index 56868a5..eff1abe 100644
--- a/refs.c
+++ b/refs.c
@@ -134,6 +134,11 @@ static struct ref_entry *create_ref_entry(const char *refname,
 	return ref;
 }
 
+static void free_ref_entry(struct ref_entry *entry)
+{
+	free(entry);
+}
+
 /* Add a ref_entry to the end of the ref_array (unsorted). */
 static void add_ref(struct ref_array *refs, struct ref_entry *ref)
 {
@@ -145,7 +150,7 @@ static void clear_ref_array(struct ref_array *array)
 {
 	int i;
 	for (i = 0; i < array->nr; i++)
-		free(array->refs[i]);
+		free_ref_entry(array->refs[i]);
 	free(array->refs);
 	array->nr = array->alloc = 0;
 	array->refs = NULL;
@@ -217,7 +222,7 @@ static void sort_ref_array(struct ref_array *array)
 		struct ref_entry *a = array->refs[i];
 		struct ref_entry *b = array->refs[j];
 		if (is_dup_ref(a, b)) {
-			free(b);
+			free_ref_entry(b);
 			continue;
 		}
 		i++;
-- 
1.7.7

[PATCH 03/28] check_refname_component(): return 0 for zero-length components

[mhagger]

From: Michael Haggerty <mhagger@alum.mit.edu>

Return 0 (instead of -1) for zero-length components.  Move the
interpretation of zero-length components as illegal to
check_refname_format().

This will make it easier to extend check_refname_format() to also
check whether directory names are valid.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs.c |    4 ++--
 1 files changed, 2 insertions(+), 2 deletions(-)

diff --git a/refs.c b/refs.c
index eff1abe..61dfb32 100644
--- a/refs.c
+++ b/refs.c
@@ -51,7 +51,7 @@ static int check_refname_component(const char *refname, int flags)
 		last = ch;
 	}
 	if (cp == refname)
-		return -1; /* Component has zero length. */
+		return 0; /* Component has zero length. */
 	if (refname[0] == '.') {
 		if (!(flags & REFNAME_DOT_COMPONENT))
 			return -1; /* Component starts with '.'. */
@@ -74,7 +74,7 @@ int check_refname_format(const char *refname, int flags)
 	while (1) {
 		/* We are at the start of a path component. */
 		component_len = check_refname_component(refname, flags);
-		if (component_len < 0) {
+		if (component_len <= 0) {
 			if ((flags & REFNAME_REFSPEC_PATTERN) &&
 					refname[0] == '*' &&
 					(refname[1] == '\0' || refname[1] == '/')) {
-- 
1.7.7

[PATCH 04/28] struct ref_entry: nest the value part in a union

[mhagger]

From: Michael Haggerty <mhagger@alum.mit.edu>

This change is obviously silly by itself, but it is a step towards
adding a second member to the union.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs.c |   32 +++++++++++++++++++-------------
 1 files changed, 19 insertions(+), 13 deletions(-)

diff --git a/refs.c b/refs.c
index 61dfb32..dafb585 100644
--- a/refs.c
+++ b/refs.c
@@ -101,6 +101,11 @@ int check_refname_format(const char *refname, int flags)
 
 struct ref_entry;
 
+struct ref_value {
+	unsigned char sha1[20];
+	unsigned char peeled[20];
+};
+
 struct ref_array {
 	int nr, alloc;
 	struct ref_entry **refs;
@@ -111,8 +116,9 @@ struct ref_array {
 
 struct ref_entry {
 	unsigned char flag; /* ISSYMREF? ISPACKED? */
-	unsigned char sha1[20];
-	unsigned char peeled[20];
+	union {
+		struct ref_value value;
+	} u;
 	/* The full name of the reference (e.g., "refs/heads/master"): */
 	char name[FLEX_ARRAY];
 };
@@ -127,8 +133,8 @@ static struct ref_entry *create_ref_entry(const char *refname,
 		die("Reference has invalid format: '%s'", refname);
 	len = strlen(refname) + 1;
 	ref = xmalloc(sizeof(struct ref_entry) + len);
-	hashcpy(ref->sha1, sha1);
-	hashclr(ref->peeled);
+	hashcpy(ref->u.value.sha1, sha1);
+	hashclr(ref->u.value.peeled);
 	memcpy(ref->name, refname, len);
 	ref->flag = flag;
 	return ref;
@@ -197,7 +203,7 @@ static int is_dup_ref(const struct ref_entry *ref1, const struct ref_entry *ref2
 {
 	if (!strcmp(ref1->name, ref2->name)) {
 		/* Duplicate name; make sure that the SHA1s match: */
-		if (hashcmp(ref1->sha1, ref2->sha1))
+		if (hashcmp(ref1->u.value.sha1, ref2->u.value.sha1))
 			die("Duplicated ref, and SHA1s don't match: %s",
 			    ref1->name);
 		warning("Duplicated ref: %s", ref1->name);
@@ -244,13 +250,13 @@ static int do_one_ref(const char *base, each_ref_fn fn, int trim,
 	if (!(flags & DO_FOR_EACH_INCLUDE_BROKEN)) {
 		if (entry->flag & REF_ISBROKEN)
 			return 0; /* ignore broken refs e.g. dangling symref */
-		if (!has_sha1_file(entry->sha1)) {
+		if (!has_sha1_file(entry->u.value.sha1)) {
 			error("%s does not point to a valid object!", entry->name);
 			return 0;
 		}
 	}
 	current_ref = entry;
-	return fn(entry->name + trim, entry->sha1, entry->flag, cb_data);
+	return fn(entry->name + trim, entry->u.value.sha1, entry->flag, cb_data);
 }
 
 static int do_for_each_ref_in_array(struct ref_array *array, int offset,
@@ -502,7 +508,7 @@ static void read_packed_refs(FILE *f, struct ref_array *array)
 		    strlen(refline) == 42 &&
 		    refline[41] == '\n' &&
 		    !get_sha1_hex(refline + 1, sha1))
-			hashcpy(last->peeled, sha1);
+			hashcpy(last->u.value.peeled, sha1);
 	}
 	sort_ref_array(array);
 }
@@ -632,7 +638,7 @@ static int resolve_gitlink_packed_ref(struct ref_cache *refs,
 	if (ref == NULL)
 		return -1;
 
-	memcpy(sha1, ref->sha1, 20);
+	memcpy(sha1, ref->u.value.sha1, 20);
 	return 0;
 }
 
@@ -702,7 +708,7 @@ static int get_packed_ref(const char *refname, unsigned char *sha1)
 	struct ref_array *packed = get_packed_refs(get_ref_cache(NULL));
 	struct ref_entry *entry = search_ref_array(packed, refname);
 	if (entry) {
-		hashcpy(sha1, entry->sha1);
+		hashcpy(sha1, entry->u.value.sha1);
 		return 0;
 	}
 	return -1;
@@ -848,10 +854,10 @@ int peel_ref(const char *refname, unsigned char *sha1)
 	if (current_ref && (current_ref->name == refname
 		|| !strcmp(current_ref->name, refname))) {
 		if (current_ref->flag & REF_KNOWS_PEELED) {
-			hashcpy(sha1, current_ref->peeled);
+			hashcpy(sha1, current_ref->u.value.peeled);
 			return 0;
 		}
-		hashcpy(base, current_ref->sha1);
+		hashcpy(base, current_ref->u.value.sha1);
 		goto fallback;
 	}
 
@@ -863,7 +869,7 @@ int peel_ref(const char *refname, unsigned char *sha1)
 		struct ref_entry *r = search_ref_array(array, refname);
 
 		if (r != NULL && r->flag & REF_KNOWS_PEELED) {
-			hashcpy(sha1, r->peeled);
+			hashcpy(sha1, r->u.value.peeled);
 			return 0;
 		}
 	}
-- 
1.7.7

[PATCH 05/28] refs.c: rename ref_array -> ref_dir

[mhagger]

From: Michael Haggerty <mhagger@alum.mit.edu>

This purely textual change is in preparation for storing references
hierarchically, when the old ref_array structure will represent one
"directory" of references.  Rename functions that deal with this
structure analogously, and also rename the structure's "refs" member
to "entries".

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs.c |  168 ++++++++++++++++++++++++++++++++--------------------------------
 1 files changed, 84 insertions(+), 84 deletions(-)

diff --git a/refs.c b/refs.c
index dafb585..708eebf 100644
--- a/refs.c
+++ b/refs.c
@@ -106,9 +106,9 @@ struct ref_value {
 	unsigned char peeled[20];
 };
 
-struct ref_array {
+struct ref_dir {
 	int nr, alloc;
-	struct ref_entry **refs;
+	struct ref_entry **entries;
 };
 
 /* ISSYMREF=0x01, ISPACKED=0x02 and ISBROKEN=0x04 are public interfaces */
@@ -145,21 +145,21 @@ static void free_ref_entry(struct ref_entry *entry)
 	free(entry);
 }
 
-/* Add a ref_entry to the end of the ref_array (unsorted). */
-static void add_ref(struct ref_array *refs, struct ref_entry *ref)
+/* Add a ref_entry to the end of the ref_dir (unsorted). */
+static void add_ref(struct ref_dir *refs, struct ref_entry *ref)
 {
-	ALLOC_GROW(refs->refs, refs->nr + 1, refs->alloc);
-	refs->refs[refs->nr++] = ref;
+	ALLOC_GROW(refs->entries, refs->nr + 1, refs->alloc);
+	refs->entries[refs->nr++] = ref;
 }
 
-static void clear_ref_array(struct ref_array *array)
+static void clear_ref_dir(struct ref_dir *dir)
 {
 	int i;
-	for (i = 0; i < array->nr; i++)
-		free_ref_entry(array->refs[i]);
-	free(array->refs);
-	array->nr = array->alloc = 0;
-	array->refs = NULL;
+	for (i = 0; i < dir->nr; i++)
+		free_ref_entry(dir->entries[i]);
+	free(dir->entries);
+	dir->nr = dir->alloc = 0;
+	dir->entries = NULL;
 }
 
 static int ref_entry_cmp(const void *a, const void *b)
@@ -169,7 +169,7 @@ static int ref_entry_cmp(const void *a, const void *b)
 	return strcmp(one->name, two->name);
 }
 
-static struct ref_entry *search_ref_array(struct ref_array *array, const char *refname)
+static struct ref_entry *search_ref_dir(struct ref_dir *dir, const char *refname)
 {
 	struct ref_entry *e, **r;
 	int len;
@@ -177,14 +177,14 @@ static struct ref_entry *search_ref_array(struct ref_array *array, const char *r
 	if (refname == NULL)
 		return NULL;
 
-	if (!array->nr)
+	if (!dir->nr)
 		return NULL;
 
 	len = strlen(refname) + 1;
 	e = xmalloc(sizeof(struct ref_entry) + len);
 	memcpy(e->name, refname, len);
 
-	r = bsearch(&e, array->refs, array->nr, sizeof(*array->refs), ref_entry_cmp);
+	r = bsearch(&e, dir->entries, dir->nr, sizeof(*dir->entries), ref_entry_cmp);
 
 	free(e);
 
@@ -213,28 +213,28 @@ static int is_dup_ref(const struct ref_entry *ref1, const struct ref_entry *ref2
 	}
 }
 
-static void sort_ref_array(struct ref_array *array)
+static void sort_ref_dir(struct ref_dir *dir)
 {
 	int i = 0, j = 1;
 
 	/* Nothing to sort unless there are at least two entries */
-	if (array->nr < 2)
+	if (dir->nr < 2)
 		return;
 
-	qsort(array->refs, array->nr, sizeof(*array->refs), ref_entry_cmp);
+	qsort(dir->entries, dir->nr, sizeof(*dir->entries), ref_entry_cmp);
 
-	/* Remove any duplicates from the ref_array */
-	for (; j < array->nr; j++) {
-		struct ref_entry *a = array->refs[i];
-		struct ref_entry *b = array->refs[j];
+	/* Remove any duplicates from the ref_dir */
+	for (; j < dir->nr; j++) {
+		struct ref_entry *a = dir->entries[i];
+		struct ref_entry *b = dir->entries[j];
 		if (is_dup_ref(a, b)) {
 			free_ref_entry(b);
 			continue;
 		}
 		i++;
-		array->refs[i] = array->refs[j];
+		dir->entries[i] = dir->entries[j];
 	}
-	array->nr = i + 1;
+	dir->nr = i + 1;
 }
 
 #define DO_FOR_EACH_INCLUDE_BROKEN 01
@@ -259,23 +259,23 @@ static int do_one_ref(const char *base, each_ref_fn fn, int trim,
 	return fn(entry->name + trim, entry->u.value.sha1, entry->flag, cb_data);
 }
 
-static int do_for_each_ref_in_array(struct ref_array *array, int offset,
-				    const char *base,
-				    each_ref_fn fn, int trim, int flags, void *cb_data)
+static int do_for_each_ref_in_dir(struct ref_dir *dir, int offset,
+				  const char *base,
+				  each_ref_fn fn, int trim, int flags, void *cb_data)
 {
 	int i;
-	for (i = offset; i < array->nr; i++) {
-		int retval = do_one_ref(base, fn, trim, flags, cb_data, array->refs[i]);
+	for (i = offset; i < dir->nr; i++) {
+		int retval = do_one_ref(base, fn, trim, flags, cb_data, dir->entries[i]);
 		if (retval)
 			return retval;
 	}
 	return 0;
 }
 
-static int do_for_each_ref_in_arrays(struct ref_array *array1,
-				     struct ref_array *array2,
-				     const char *base, each_ref_fn fn, int trim,
-				     int flags, void *cb_data)
+static int do_for_each_ref_in_dirs(struct ref_dir *dir1,
+				   struct ref_dir *dir2,
+				   const char *base, each_ref_fn fn, int trim,
+				   int flags, void *cb_data)
 {
 	int retval;
 	int i1 = 0, i2 = 0;
@@ -283,19 +283,19 @@ static int do_for_each_ref_in_arrays(struct ref_array *array1,
 	while (1) {
 		struct ref_entry *e1, *e2;
 		int cmp;
-		if (i1 == array1->nr) {
-			return do_for_each_ref_in_array(array2, i2,
-							base, fn, trim, flags, cb_data);
+		if (i1 == dir1->nr) {
+			return do_for_each_ref_in_dir(dir2, i2,
+						      base, fn, trim, flags, cb_data);
 		}
-		if (i2 == array2->nr) {
-			return do_for_each_ref_in_array(array1, i1,
-							base, fn, trim, flags, cb_data);
+		if (i2 == dir2->nr) {
+			return do_for_each_ref_in_dir(dir1, i1,
+						      base, fn, trim, flags, cb_data);
 		}
-		e1 = array1->refs[i1];
-		e2 = array2->refs[i2];
+		e1 = dir1->entries[i1];
+		e2 = dir2->entries[i2];
 		cmp = strcmp(e1->name, e2->name);
 		if (cmp == 0) {
-			/* Two refs with the same name; ignore the one from array1. */
+			/* Two refs with the same name; ignore the one from dir1. */
 			i1++;
 			continue;
 		}
@@ -353,16 +353,16 @@ static int name_conflict_fn(const char *existingrefname, const unsigned char *sh
  * operation).
  */
 static int is_refname_available(const char *refname, const char *oldrefname,
-				struct ref_array *array)
+				struct ref_dir *dir)
 {
 	struct name_conflict_cb data;
 	data.refname = refname;
 	data.oldrefname = oldrefname;
 	data.conflicting_refname = NULL;
 
-	if (do_for_each_ref_in_array(array, 0, "", name_conflict_fn,
-				     0, DO_FOR_EACH_INCLUDE_BROKEN,
-				     &data)) {
+	if (do_for_each_ref_in_dir(dir, 0, "", name_conflict_fn,
+				   0, DO_FOR_EACH_INCLUDE_BROKEN,
+				   &data)) {
 		error("'%s' exists; cannot create '%s'",
 		      data.conflicting_refname, refname);
 		return 0;
@@ -378,25 +378,25 @@ static struct ref_cache {
 	struct ref_cache *next;
 	char did_loose;
 	char did_packed;
-	struct ref_array loose;
-	struct ref_array packed;
+	struct ref_dir loose;
+	struct ref_dir packed;
 	/* The submodule name, or "" for the main repo. */
 	char name[FLEX_ARRAY];
 } *ref_cache;
 
-static struct ref_array extra_refs;
+static struct ref_dir extra_refs;
 
 static void clear_packed_ref_cache(struct ref_cache *refs)
 {
 	if (refs->did_packed)
-		clear_ref_array(&refs->packed);
+		clear_ref_dir(&refs->packed);
 	refs->did_packed = 0;
 }
 
 static void clear_loose_ref_cache(struct ref_cache *refs)
 {
 	if (refs->did_loose)
-		clear_ref_array(&refs->loose);
+		clear_ref_dir(&refs->loose);
 	refs->did_loose = 0;
 }
 
@@ -478,7 +478,7 @@ static const char *parse_ref_line(char *line, unsigned char *sha1)
 	return line;
 }
 
-static void read_packed_refs(FILE *f, struct ref_array *array)
+static void read_packed_refs(FILE *f, struct ref_dir *dir)
 {
 	struct ref_entry *last = NULL;
 	char refline[PATH_MAX];
@@ -500,7 +500,7 @@ static void read_packed_refs(FILE *f, struct ref_array *array)
 		refname = parse_ref_line(refline, sha1);
 		if (refname) {
 			last = create_ref_entry(refname, sha1, flag);
-			add_ref(array, last);
+			add_ref(dir, last);
 			continue;
 		}
 		if (last &&
@@ -510,7 +510,7 @@ static void read_packed_refs(FILE *f, struct ref_array *array)
 		    !get_sha1_hex(refline + 1, sha1))
 			hashcpy(last->u.value.peeled, sha1);
 	}
-	sort_ref_array(array);
+	sort_ref_dir(dir);
 }
 
 void add_extra_ref(const char *refname, const unsigned char *sha1, int flag)
@@ -520,10 +520,10 @@ void add_extra_ref(const char *refname, const unsigned char *sha1, int flag)
 
 void clear_extra_refs(void)
 {
-	clear_ref_array(&extra_refs);
+	clear_ref_dir(&extra_refs);
 }
 
-static struct ref_array *get_packed_refs(struct ref_cache *refs)
+static struct ref_dir *get_packed_refs(struct ref_cache *refs)
 {
 	if (!refs->did_packed) {
 		const char *packed_refs_file;
@@ -544,9 +544,9 @@ static struct ref_array *get_packed_refs(struct ref_cache *refs)
 }
 
 static void get_ref_dir(struct ref_cache *refs, const char *base,
-			struct ref_array *array)
+			struct ref_dir *dir)
 {
-	DIR *dir;
+	DIR *d;
 	const char *path;
 
 	if (*refs->name)
@@ -555,9 +555,9 @@ static void get_ref_dir(struct ref_cache *refs, const char *base,
 		path = git_path("%s", base);
 
 
-	dir = opendir(path);
+	d = opendir(path);
 
-	if (dir) {
+	if (d) {
 		struct dirent *de;
 		int baselen = strlen(base);
 		char *refname = xmalloc(baselen + 257);
@@ -566,7 +566,7 @@ static void get_ref_dir(struct ref_cache *refs, const char *base,
 		if (baselen && base[baselen-1] != '/')
 			refname[baselen++] = '/';
 
-		while ((de = readdir(dir)) != NULL) {
+		while ((de = readdir(d)) != NULL) {
 			unsigned char sha1[20];
 			struct stat st;
 			int flag;
@@ -587,7 +587,7 @@ static void get_ref_dir(struct ref_cache *refs, const char *base,
 			if (stat(refdir, &st) < 0)
 				continue;
 			if (S_ISDIR(st.st_mode)) {
-				get_ref_dir(refs, refname, array);
+				get_ref_dir(refs, refname, dir);
 				continue;
 			}
 			if (*refs->name) {
@@ -602,18 +602,18 @@ static void get_ref_dir(struct ref_cache *refs, const char *base,
 					hashclr(sha1);
 					flag |= REF_ISBROKEN;
 				}
-			add_ref(array, create_ref_entry(refname, sha1, flag));
+			add_ref(dir, create_ref_entry(refname, sha1, flag));
 		}
 		free(refname);
-		closedir(dir);
+		closedir(d);
 	}
 }
 
-static struct ref_array *get_loose_refs(struct ref_cache *refs)
+static struct ref_dir *get_loose_refs(struct ref_cache *refs)
 {
 	if (!refs->did_loose) {
 		get_ref_dir(refs, "refs", &refs->loose);
-		sort_ref_array(&refs->loose);
+		sort_ref_dir(&refs->loose);
 		refs->did_loose = 1;
 	}
 	return &refs->loose;
@@ -632,9 +632,9 @@ static int resolve_gitlink_packed_ref(struct ref_cache *refs,
 				      const char *refname, unsigned char *sha1)
 {
 	struct ref_entry *ref;
-	struct ref_array *array = get_packed_refs(refs);
+	struct ref_dir *dir = get_packed_refs(refs);
 
-	ref = search_ref_array(array, refname);
+	ref = search_ref_dir(dir, refname);
 	if (ref == NULL)
 		return -1;
 
@@ -705,8 +705,8 @@ int resolve_gitlink_ref(const char *path, const char *refname, unsigned char *sh
  */
 static int get_packed_ref(const char *refname, unsigned char *sha1)
 {
-	struct ref_array *packed = get_packed_refs(get_ref_cache(NULL));
-	struct ref_entry *entry = search_ref_array(packed, refname);
+	struct ref_dir *packed = get_packed_refs(get_ref_cache(NULL));
+	struct ref_entry *entry = search_ref_dir(packed, refname);
 	if (entry) {
 		hashcpy(sha1, entry->u.value.sha1);
 		return 0;
@@ -865,8 +865,8 @@ int peel_ref(const char *refname, unsigned char *sha1)
 		return -1;
 
 	if ((flag & REF_ISPACKED)) {
-		struct ref_array *array = get_packed_refs(get_ref_cache(NULL));
-		struct ref_entry *r = search_ref_array(array, refname);
+		struct ref_dir *dir = get_packed_refs(get_ref_cache(NULL));
+		struct ref_entry *r = search_ref_dir(dir, refname);
 
 		if (r != NULL && r->flag & REF_KNOWS_PEELED) {
 			hashcpy(sha1, r->u.value.peeled);
@@ -926,12 +926,12 @@ static int do_for_each_ref(const char *submodule, const char *base, each_ref_fn
 	int retval = 0;
 	struct ref_cache *refs = get_ref_cache(submodule);
 
-	retval = do_for_each_ref_in_array(&extra_refs, 0,
-					  base, fn, trim, flags, cb_data);
+	retval = do_for_each_ref_in_dir(&extra_refs, 0,
+					base, fn, trim, flags, cb_data);
 	if (!retval)
-		retval = do_for_each_ref_in_arrays(get_packed_refs(refs),
-						   get_loose_refs(refs),
-						   base, fn, trim, flags, cb_data);
+		retval = do_for_each_ref_in_dirs(get_packed_refs(refs),
+						 get_loose_refs(refs),
+						 base, fn, trim, flags, cb_data);
 
 	current_ref = NULL;
 	return retval;
@@ -1377,10 +1377,10 @@ static struct lock_file packlock;
 static int repack_without_ref(const char *refname)
 {
 	struct repack_without_ref_sb data;
-	struct ref_array *packed;
+	struct ref_dir *packed;
 
 	packed = get_packed_refs(get_ref_cache(NULL));
-	if (search_ref_array(packed, refname) == NULL)
+	if (search_ref_dir(packed, refname) == NULL)
 		return 0;
 	data.refname = refname;
 	data.fd = hold_lock_file_for_update(&packlock, git_path("packed-refs"), 0);
@@ -1388,7 +1388,7 @@ static int repack_without_ref(const char *refname)
 		unable_to_lock_error(git_path("packed-refs"), errno);
 		return error("cannot delete '%s' from packed refs", refname);
 	}
-	do_for_each_ref_in_array(packed, 0, "", repack_without_ref_fn, 0, 0, &data);
+	do_for_each_ref_in_dir(packed, 0, "", repack_without_ref_fn, 0, 0, &data);
 	return commit_lock_file(&packlock);
 }
 
@@ -1998,10 +1998,10 @@ int for_each_reflog_ent(const char *refname, each_reflog_ent_fn fn, void *cb_dat
 
 static int do_for_each_reflog(const char *base, each_ref_fn fn, void *cb_data)
 {
-	DIR *dir = opendir(git_path("logs/%s", base));
+	DIR *d = opendir(git_path("logs/%s", base));
 	int retval = 0;
 
-	if (dir) {
+	if (d) {
 		struct dirent *de;
 		int baselen = strlen(base);
 		char *log = xmalloc(baselen + 257);
@@ -2010,7 +2010,7 @@ static int do_for_each_reflog(const char *base, each_ref_fn fn, void *cb_data)
 		if (baselen && base[baselen-1] != '/')
 			log[baselen++] = '/';
 
-		while ((de = readdir(dir)) != NULL) {
+		while ((de = readdir(d)) != NULL) {
 			struct stat st;
 			int namelen;
 
@@ -2037,7 +2037,7 @@ static int do_for_each_reflog(const char *base, each_ref_fn fn, void *cb_data)
 				break;
 		}
 		free(log);
-		closedir(dir);
+		closedir(d);
 	}
 	else if (*base)
 		return errno;
-- 
1.7.7

[PATCH 06/28] refs: store references hierarchically

[mhagger]

From: Michael Haggerty <mhagger@alum.mit.edu>

Store references hierarchically in a tree that matches the
pseudo-directory structure of the reference names.  Add a new kind of
ref_entry (with flag REF_DIR) to represent a whole subdirectory of
references.  Teach check_refname_format() to decide whether a
reference directory name is valid.

Please note that this change causes some extra sorting to be required,
and therefore a performance regression.  The old performance will be
regained in the next couple of commits by (1) keeping track of when a
directory is already sorted and not re-sorting it; (2) only sorting a
directory when the correct order needed; and (3) not sorting
directories recursively.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs.c |  325 +++++++++++++++++++++++++++++++++++++++++++++++++++++-----------
 1 files changed, 271 insertions(+), 54 deletions(-)

diff --git a/refs.c b/refs.c
index 708eebf..6b4d5d5 100644
--- a/refs.c
+++ b/refs.c
@@ -67,6 +67,23 @@ static int check_refname_component(const char *refname, int flags)
 	return cp - refname;
 }
 
+/*
+ * Non-public option to check_refname_format(), for asking it to check
+ * that refname is a valid reference "directory" name.
+ */
+#define REFNAME_DIR 0x08
+
+/*
+ * See refs.h for a description of the public interface of this
+ * function.  In addition, there is a private interface that can be
+ * accessed by setting the REFNAME_DIR bit.  If REFNAME_DIR is set,
+ * then refname must be a valid reference "directory" name.  This
+ * means that it must include at least one valid component (which *is*
+ * allowed to end with '.') followed by a trailing '/'.  If
+ * REFNAME_DIR and REFNAME_ALLOW_ONELEVEL are both passed, then
+ * additionally the empty string (no trailing slash allowed) is
+ * allowed.
+ */
 int check_refname_format(const char *refname, int flags)
 {
 	int component_len, component_count = 0;
@@ -74,7 +91,7 @@ int check_refname_format(const char *refname, int flags)
 	while (1) {
 		/* We are at the start of a path component. */
 		component_len = check_refname_component(refname, flags);
-		if (component_len <= 0) {
+		if (component_len < 0) {
 			if ((flags & REFNAME_REFSPEC_PATTERN) &&
 					refname[0] == '*' &&
 					(refname[1] == '\0' || refname[1] == '/')) {
@@ -86,16 +103,36 @@ int check_refname_format(const char *refname, int flags)
 			}
 		}
 		component_count++;
-		if (refname[component_len] == '\0')
+		if (refname[component_len] == '\0') {
+			if (flags & REFNAME_DIR) {
+				/*
+				 * The last component of a REFNAME_DIR
+				 * *must* be the empty string.
+				 */
+				if (component_len != 0)
+					return -1;
+			} else {
+				/*
+				 * The last component of a
+				 * non-REFNAME_DIR *must not* be the
+				 * empty string.
+				 */
+				if (component_len == 0)
+					return -1;
+				if (refname[component_len - 1] == '.')
+					return -1; /* Refname ends with '.'. */
+			}
+			if (!(flags & REFNAME_ALLOW_ONELEVEL) && component_count < 2)
+				return -1; /* Refname has only one component. */
+
 			break;
+		}
+		if (component_len == 0)
+			return -1; /* Double '/' */
 		/* Skip to next component. */
 		refname += component_len + 1;
 	}
 
-	if (refname[component_len - 1] == '.')
-		return -1; /* Refname ends with '.'. */
-	if (!(flags & REFNAME_ALLOW_ONELEVEL) && component_count < 2)
-		return -1; /* Refname has only one component. */
 	return 0;
 }
 
@@ -111,15 +148,54 @@ struct ref_dir {
 	struct ref_entry **entries;
 };
 
-/* ISSYMREF=0x01, ISPACKED=0x02 and ISBROKEN=0x04 are public interfaces */
-#define REF_KNOWS_PEELED 0x10
+/* ISSYMREF=0x01, ISPACKED=0x02, and ISBROKEN=0x04 are public interfaces */
+#define REF_KNOWS_PEELED 0x08
+#define REF_DIR 0x10
 
+/*
+ * A ref_entry represents either a reference or a "subdirectory" of
+ * references.  Each directory in the reference namespace is
+ * represented by a ref_entry with (flags & REF_DIR) set and
+ * containing a subdir member that holds the entries in that
+ * directory.  References are represented by a ref_entry with (flags &
+ * REF_DIR) unset and a value member that describes the reference's
+ * value.  The flag member is at the ref_entry level, but it is also
+ * needed to interpret the contents of the value field (in other
+ * words, a ref_value object is not very much use without the
+ * enclosing ref_entry).
+ *
+ * Reference names cannot end with slash and directories' names are
+ * always stored with a trailing slash (except for the top-level
+ * directory, which is always denoted by "").  This has two nice
+ * consequences: (1) when the entries in each subdir are sorted
+ * lexicographically by name (as they usually are), the references in
+ * a whole tree can be generated in lexicographic order by traversing
+ * the tree in left-to-right, depth-first order; (2) the names of
+ * references and subdirectories cannot conflict, and therefore the
+ * presence of an empty subdirectory does not block the creation of a
+ * similarly-named reference.  (The fact that reference names with the
+ * same leading components can conflict *with each other* is a
+ * separate issue that is regulated by is_refname_available().)
+ *
+ * Please note that the name field contains the fully-qualified
+ * reference (or subdirectory) name.  Space could be saved by only
+ * storing the relative names.  But that would require the full names
+ * to be generated on the fly when iterating in do_for_each_ref(), and
+ * would break callback functions, who have always been able to assume
+ * that the name strings that they are passed will not be freed during
+ * the iteration.
+ */
 struct ref_entry {
 	unsigned char flag; /* ISSYMREF? ISPACKED? */
 	union {
-		struct ref_value value;
+		struct ref_value value; /* if not (flags&REF_DIR) */
+		struct ref_dir subdir; /* if (flags&REF_DIR) */
 	} u;
-	/* The full name of the reference (e.g., "refs/heads/master"): */
+	/*
+	 * The full name of the reference (e.g., "refs/heads/master")
+	 * or the full name of the directory with a trailing slash
+	 * (e.g., "refs/heads/"):
+	 */
 	char name[FLEX_ARRAY];
 };
 
@@ -140,18 +216,29 @@ static struct ref_entry *create_ref_entry(const char *refname,
 	return ref;
 }
 
+static void clear_ref_dir(struct ref_dir *dir);
+
 static void free_ref_entry(struct ref_entry *entry)
 {
+	if (entry->flag & REF_DIR)
+		clear_ref_dir(&entry->u.subdir);
 	free(entry);
 }
 
-/* Add a ref_entry to the end of the ref_dir (unsorted). */
-static void add_ref(struct ref_dir *refs, struct ref_entry *ref)
+/*
+ * Add a ref_entry to the end of dir (unsorted).  Entry is always
+ * stored directly in dir; no recursion into subdirectories is
+ * done.
+ */
+static void add_entry_to_dir(struct ref_dir *dir, struct ref_entry *entry)
 {
-	ALLOC_GROW(refs->entries, refs->nr + 1, refs->alloc);
-	refs->entries[refs->nr++] = ref;
+	ALLOC_GROW(dir->entries, dir->nr + 1, dir->alloc);
+	dir->entries[dir->nr++] = entry;
 }
 
+/*
+ * Clear and free all entries in dir, recursively.
+ */
 static void clear_ref_dir(struct ref_dir *dir)
 {
 	int i;
@@ -162,6 +249,28 @@ static void clear_ref_dir(struct ref_dir *dir)
 	dir->entries = NULL;
 }
 
+/*
+ * Create a struct ref_entry object for the specified dirname.
+ * dirname is the name of the directory with a trailing slash (e.g.,
+ * "refs/heads/").
+ */
+static struct ref_entry *create_dir_entry(const char *dirname)
+{
+	struct ref_entry *direntry;
+	if (*dirname) {
+		int len = strlen(dirname);
+		direntry = xcalloc(1, sizeof(struct ref_entry) + len + 1);
+		memcpy(direntry->name, dirname, len + 1);
+		if (check_refname_format(direntry->name, REFNAME_DIR|REFNAME_ALLOW_ONELEVEL))
+			die("reference directory has invalid format: '%s'", direntry->name);
+	} else {
+		direntry = xcalloc(1, sizeof(struct ref_entry) + 1);
+		direntry->name[0] = '\0';
+	}
+	direntry->flag = REF_DIR;
+	return direntry;
+}
+
 static int ref_entry_cmp(const void *a, const void *b)
 {
 	struct ref_entry *one = *(struct ref_entry **)a;
@@ -169,16 +278,26 @@ static int ref_entry_cmp(const void *a, const void *b)
 	return strcmp(one->name, two->name);
 }
 
+static void sort_ref_dir(struct ref_dir *dir);
+
+/*
+ * Return the entry with the given refname from the ref_dir
+ * (non-recursively).  Return NULL if no such entry is found.
+ */
 static struct ref_entry *search_ref_dir(struct ref_dir *dir, const char *refname)
 {
 	struct ref_entry *e, **r;
 	int len;
 
-	if (refname == NULL)
+	if (refname == NULL || !dir->nr)
 		return NULL;
 
-	if (!dir->nr)
-		return NULL;
+	/*
+	 * We need dir to be sorted so that binary search works.
+	 * FIXME: Sorting the array each time is terribly inefficient,
+	 * and has to be changed.
+	 */
+	sort_ref_dir(dir);
 
 	len = strlen(refname) + 1;
 	e = xmalloc(sizeof(struct ref_entry) + len);
@@ -195,46 +314,116 @@ static struct ref_entry *search_ref_dir(struct ref_dir *dir, const char *refname
 }
 
 /*
+ * If refname is a reference name, find the ref_dir within the dir
+ * tree that should hold refname.  If refname is a directory name
+ * (i.e., ends in '/'), then return that ref_dir itself.  dir must
+ * represent the top-level directory.  Recurse into subdirectories as
+ * necessary.  If mkdir is set, then create any missing directories;
+ * otherwise, return NULL if the desired directory cannot be found.
+ */
+static struct ref_dir *find_containing_dir(struct ref_dir *dir,
+					   const char *refname, int mkdir)
+{
+	char *refname_copy = xstrdup(refname);
+	char *slash;
+	struct ref_entry *entry;
+	for (slash = strchr(refname_copy, '/'); slash; slash = strchr(slash + 1, '/')) {
+		char tmp = slash[1];
+		slash[1] = '\0';
+		entry = search_ref_dir(dir, refname_copy);
+		if (!entry) {
+			if (!mkdir) {
+				dir = NULL;
+				break;
+			}
+			entry = create_dir_entry(refname_copy);
+			add_entry_to_dir(dir, entry);
+		}
+		slash[1] = tmp;
+		assert(entry->flag & REF_DIR);
+		dir = &entry->u.subdir;
+	}
+
+	free(refname_copy);
+	return dir;
+}
+
+/*
+ * Find the value entry with the given name in dir, recursing into
+ * subdirectories as necessary.  If the name is not found or it
+ * corresponds to a directory entry, return NULL.
+ */
+static struct ref_entry *find_ref(struct ref_dir *dir, const char *refname)
+{
+	struct ref_entry *entry;
+	dir = find_containing_dir(dir, refname, 0);
+	if (!dir)
+		return NULL;
+	entry = search_ref_dir(dir, refname);
+	return (entry && !(entry->flag & REF_DIR)) ? entry : NULL;
+}
+
+/*
+ * Add a ref_entry to the ref_dir (unsorted), recursing into
+ * subdirectories as necessary.  dir must represent the top-level
+ * directory.  Return 0 on success.
+ */
+static int add_ref(struct ref_dir *dir, struct ref_entry *ref)
+{
+	dir = find_containing_dir(dir, ref->name, 1);
+	if (!dir)
+		return -1;
+	add_entry_to_dir(dir, ref);
+	return 0;
+}
+
+/*
  * Emit a warning and return true iff ref1 and ref2 have the same name
  * and the same sha1.  Die if they have the same name but different
  * sha1s.
  */
 static int is_dup_ref(const struct ref_entry *ref1, const struct ref_entry *ref2)
 {
-	if (!strcmp(ref1->name, ref2->name)) {
-		/* Duplicate name; make sure that the SHA1s match: */
-		if (hashcmp(ref1->u.value.sha1, ref2->u.value.sha1))
-			die("Duplicated ref, and SHA1s don't match: %s",
-			    ref1->name);
-		warning("Duplicated ref: %s", ref1->name);
-		return 1;
-	} else {
+	if (strcmp(ref1->name, ref2->name))
 		return 0;
-	}
+
+	/* Duplicate name; make sure that they don't conflict: */
+
+	if ((ref1->flag & REF_DIR) || (ref2->flag & REF_DIR))
+		/* This is impossible by construction */
+		die("Reference directory conflict: %s", ref1->name);
+
+	if (hashcmp(ref1->u.value.sha1, ref2->u.value.sha1))
+		die("Duplicated ref, and SHA1s don't match: %s", ref1->name);
+
+	warning("Duplicated ref: %s", ref1->name);
+	return 1;
 }
 
 static void sort_ref_dir(struct ref_dir *dir)
 {
-	int i = 0, j = 1;
+	int i, j;
+	struct ref_entry *last = NULL;
 
-	/* Nothing to sort unless there are at least two entries */
-	if (dir->nr < 2)
+	if (!dir->nr)
 		return;
 
 	qsort(dir->entries, dir->nr, sizeof(*dir->entries), ref_entry_cmp);
 
-	/* Remove any duplicates from the ref_dir */
-	for (; j < dir->nr; j++) {
-		struct ref_entry *a = dir->entries[i];
-		struct ref_entry *b = dir->entries[j];
-		if (is_dup_ref(a, b)) {
-			free_ref_entry(b);
-			continue;
+	/* Remove any duplicates and sort subdirectories: */
+	for (i = 0, j = 0; j < dir->nr; j++) {
+		struct ref_entry *entry = dir->entries[j];
+		if (last && is_dup_ref(last, entry)) {
+			free_ref_entry(entry);
+		} else if (entry->flag & REF_DIR) {
+			sort_ref_dir(&entry->u.subdir);
+			dir->entries[i++] = entry;
+			last = NULL;
+		} else {
+			last = dir->entries[i++] = entry;
 		}
-		i++;
-		dir->entries[i] = dir->entries[j];
 	}
-	dir->nr = i + 1;
+	dir->nr = i;
 }
 
 #define DO_FOR_EACH_INCLUDE_BROKEN 01
@@ -265,7 +454,14 @@ static int do_for_each_ref_in_dir(struct ref_dir *dir, int offset,
 {
 	int i;
 	for (i = offset; i < dir->nr; i++) {
-		int retval = do_one_ref(base, fn, trim, flags, cb_data, dir->entries[i]);
+		struct ref_entry *entry = dir->entries[i];
+		int retval;
+		if (entry->flag & REF_DIR) {
+			retval = do_for_each_ref_in_dir(&entry->u.subdir, 0,
+							base, fn, trim, flags, cb_data);
+		} else {
+			retval = do_one_ref(base, fn, trim, flags, cb_data, entry);
+		}
 		if (retval)
 			return retval;
 	}
@@ -281,7 +477,7 @@ static int do_for_each_ref_in_dirs(struct ref_dir *dir1,
 	int i1 = 0, i2 = 0;
 
 	while (1) {
-		struct ref_entry *e1, *e2;
+		struct ref_entry *e1, *e2, *entry;
 		int cmp;
 		if (i1 == dir1->nr) {
 			return do_for_each_ref_in_dir(dir2, i2,
@@ -295,16 +491,37 @@ static int do_for_each_ref_in_dirs(struct ref_dir *dir1,
 		e2 = dir2->entries[i2];
 		cmp = strcmp(e1->name, e2->name);
 		if (cmp == 0) {
-			/* Two refs with the same name; ignore the one from dir1. */
-			i1++;
-			continue;
-		}
-		if (cmp < 0) {
-			retval = do_one_ref(base, fn, trim, flags, cb_data, e1);
-			i1++;
+			if ((e1->flag & REF_DIR) && (e2->flag & REF_DIR)) {
+				/* Both are directories; descend them in parallel. */
+				retval = do_for_each_ref_in_dirs(
+						&e1->u.subdir, &e2->u.subdir,
+						base, fn, trim, flags, cb_data);
+				i1++;
+				i2++;
+			} else if (!(e1->flag & REF_DIR) && !(e2->flag & REF_DIR)) {
+				/* Both are references; ignore the one from dir1. */
+				retval = do_one_ref(base, fn, trim, flags, cb_data, e2);
+				i1++;
+				i2++;
+			} else {
+				die("conflict between reference and directory: %s",
+				    e1->name);
+			}
 		} else {
-			retval = do_one_ref(base, fn, trim, flags, cb_data, e2);
-			i2++;
+			if (cmp < 0) {
+				entry = e1;
+				i1++;
+			} else {
+				entry = e2;
+				i2++;
+			}
+			if (entry->flag & REF_DIR) {
+				retval = do_for_each_ref_in_dir(
+						&entry->u.subdir, 0,
+						base, fn, trim, flags, cb_data);
+			} else {
+				retval = do_one_ref(base, fn, trim, flags, cb_data, entry);
+			}
 		}
 		if (retval)
 			return retval;
@@ -634,7 +851,7 @@ static int resolve_gitlink_packed_ref(struct ref_cache *refs,
 	struct ref_entry *ref;
 	struct ref_dir *dir = get_packed_refs(refs);
 
-	ref = search_ref_dir(dir, refname);
+	ref = find_ref(dir, refname);
 	if (ref == NULL)
 		return -1;
 
@@ -706,7 +923,7 @@ int resolve_gitlink_ref(const char *path, const char *refname, unsigned char *sh
 static int get_packed_ref(const char *refname, unsigned char *sha1)
 {
 	struct ref_dir *packed = get_packed_refs(get_ref_cache(NULL));
-	struct ref_entry *entry = search_ref_dir(packed, refname);
+	struct ref_entry *entry = find_ref(packed, refname);
 	if (entry) {
 		hashcpy(sha1, entry->u.value.sha1);
 		return 0;
@@ -866,7 +1083,7 @@ int peel_ref(const char *refname, unsigned char *sha1)
 
 	if ((flag & REF_ISPACKED)) {
 		struct ref_dir *dir = get_packed_refs(get_ref_cache(NULL));
-		struct ref_entry *r = search_ref_dir(dir, refname);
+		struct ref_entry *r = find_ref(dir, refname);
 
 		if (r != NULL && r->flag & REF_KNOWS_PEELED) {
 			hashcpy(sha1, r->u.value.peeled);
@@ -1380,7 +1597,7 @@ static int repack_without_ref(const char *refname)
 	struct ref_dir *packed;
 
 	packed = get_packed_refs(get_ref_cache(NULL));
-	if (search_ref_dir(packed, refname) == NULL)
+	if (find_ref(packed, refname) == NULL)
 		return 0;
 	data.refname = refname;
 	data.fd = hold_lock_file_for_update(&packlock, git_path("packed-refs"), 0);
-- 
1.7.7

[PATCH 07/28] sort_ref_dir(): do not sort if already sorted

[mhagger]

From: Michael Haggerty <mhagger@alum.mit.edu>

Keep track of how many entries in a ref_dir are already sorted.  In
sort_ref_dir(), only call qsort() if the dir contains unsorted
entries.

We could store a binary "sorted" value instead of an integer, but
storing the number of sorted entries leaves the way open for a couple
of possible future optimizations:

* In sort_ref_dir(), sort *only* the unsorted entries, then merge them
  with the sorted entries.  This should be faster if most of the
  entries are already sorted.

* Teach search_ref_dir() to do a binary search of any sorted entries,
  and if unsuccessful do a linear search of any unsorted entries.
  This would avoid the need to sort the list every time that
  search_ref_dir() is called, and (given some intelligence about how
  often to sort) could significantly improve the speed in certain
  hypothetical usage patterns.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs.c |   29 ++++++++++++++++++++++++-----
 1 files changed, 24 insertions(+), 5 deletions(-)

diff --git a/refs.c b/refs.c
index 6b4d5d5..8733a08 100644
--- a/refs.c
+++ b/refs.c
@@ -145,6 +145,10 @@ struct ref_value {
 
 struct ref_dir {
 	int nr, alloc;
+
+	/* How many of the entries in this directory are sorted? */
+	int sorted;
+
 	struct ref_entry **entries;
 };
 
@@ -245,7 +249,7 @@ static void clear_ref_dir(struct ref_dir *dir)
 	for (i = 0; i < dir->nr; i++)
 		free_ref_entry(dir->entries[i]);
 	free(dir->entries);
-	dir->nr = dir->alloc = 0;
+	dir->sorted = dir->nr = dir->alloc = 0;
 	dir->entries = NULL;
 }
 
@@ -294,8 +298,9 @@ static struct ref_entry *search_ref_dir(struct ref_dir *dir, const char *refname
 
 	/*
 	 * We need dir to be sorted so that binary search works.
-	 * FIXME: Sorting the array each time is terribly inefficient,
-	 * and has to be changed.
+	 * Calling sort_ref_dir() here is not quite as terribly
+	 * inefficient as it looks, because directories that are
+	 * already sorted are not re-sorted.
 	 */
 	sort_ref_dir(dir);
 
@@ -400,13 +405,27 @@ static int is_dup_ref(const struct ref_entry *ref1, const struct ref_entry *ref2
 	return 1;
 }
 
+/*
+ * Sort the entries in dir and its subdirectories (if they are not
+ * already sorted).
+ */
 static void sort_ref_dir(struct ref_dir *dir)
 {
 	int i, j;
 	struct ref_entry *last = NULL;
 
-	if (!dir->nr)
+	if (dir->sorted == dir->nr) {
+		/*
+		 * This directory is already sorted and de-duped, but
+		 * we still have to sort subdirectories.
+		 */
+		for (i = 0; i < dir->nr; i++) {
+			struct ref_entry *entry = dir->entries[i];
+			if (entry->flag & REF_DIR)
+				sort_ref_dir(&entry->u.subdir);
+		}
 		return;
+	}
 
 	qsort(dir->entries, dir->nr, sizeof(*dir->entries), ref_entry_cmp);
 
@@ -423,7 +442,7 @@ static void sort_ref_dir(struct ref_dir *dir)
 			last = dir->entries[i++] = entry;
 		}
 	}
-	dir->nr = i;
+	dir->sorted = dir->nr = i;
 }
 
 #define DO_FOR_EACH_INCLUDE_BROKEN 01
-- 
1.7.7

[PATCH 08/28] refs: sort ref_dirs lazily

[mhagger]

From: Michael Haggerty <mhagger@alum.mit.edu>

Sort ref_dirs lazily, when the ordering is needed: for searching via
search_ref_dir(), and when iterating over them via
do_for_each_ref_in_dir() and do_for_each_ref_in_dirs().

This change means that we never have to sort directories recursively,
so change sort_ref_dirs() to not recurse.

NOTE: the dirs can now be sorted as a side-effect of other function
calls.  Therefore, it would be problematic to do something from a
each_ref_fn callback that could provoke the sorting of the directory
that is currently being iterated over.  This is not so likely, because
a directory is always sorted just before being iterated over and thus
can be searched through during the iteration without causing a
re-sort.  But if a callback function would add a reference to a parent
directory of the reference in the iteration, then try to resolve a
reference under that directory, inconsistency could result.

Add a comment in refs.h warning against modifications during
iteration.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs.c |   35 +++++++++++++++--------------------
 refs.h |    7 +++++--
 2 files changed, 20 insertions(+), 22 deletions(-)

diff --git a/refs.c b/refs.c
index 8733a08..733d7a8 100644
--- a/refs.c
+++ b/refs.c
@@ -298,9 +298,14 @@ static struct ref_entry *search_ref_dir(struct ref_dir *dir, const char *refname
 
 	/*
 	 * We need dir to be sorted so that binary search works.
-	 * Calling sort_ref_dir() here is not quite as terribly
-	 * inefficient as it looks, because directories that are
-	 * already sorted are not re-sorted.
+	 * Calling sort_ref_dir() here is not as terribly inefficient
+	 * as it looks.  (1) If the directory is already sorted, it is
+	 * not re-sorted. (2) When adding a reference,
+	 * search_ref_dir() is only called to find the containing
+	 * subdirectories; there is no search of the directory to
+	 * which the reference will be stored.  Thus adding a bunch of
+	 * references one after the other to a single subdirectory
+	 * doesn't require *any* intermediate sorting.
 	 */
 	sort_ref_dir(dir);
 
@@ -406,26 +411,16 @@ static int is_dup_ref(const struct ref_entry *ref1, const struct ref_entry *ref2
 }
 
 /*
- * Sort the entries in dir and its subdirectories (if they are not
- * already sorted).
+ * Sort the entries in dir (if they are not already sorted).  Sort
+ * only dir itself, not its subdirectories.
  */
 static void sort_ref_dir(struct ref_dir *dir)
 {
 	int i, j;
 	struct ref_entry *last = NULL;
 
-	if (dir->sorted == dir->nr) {
-		/*
-		 * This directory is already sorted and de-duped, but
-		 * we still have to sort subdirectories.
-		 */
-		for (i = 0; i < dir->nr; i++) {
-			struct ref_entry *entry = dir->entries[i];
-			if (entry->flag & REF_DIR)
-				sort_ref_dir(&entry->u.subdir);
-		}
-		return;
-	}
+	if (dir->sorted == dir->nr)
+		return; /* This directory is already sorted and de-duped */
 
 	qsort(dir->entries, dir->nr, sizeof(*dir->entries), ref_entry_cmp);
 
@@ -435,7 +430,6 @@ static void sort_ref_dir(struct ref_dir *dir)
 		if (last && is_dup_ref(last, entry)) {
 			free_ref_entry(entry);
 		} else if (entry->flag & REF_DIR) {
-			sort_ref_dir(&entry->u.subdir);
 			dir->entries[i++] = entry;
 			last = NULL;
 		} else {
@@ -472,6 +466,7 @@ static int do_for_each_ref_in_dir(struct ref_dir *dir, int offset,
 				  each_ref_fn fn, int trim, int flags, void *cb_data)
 {
 	int i;
+	sort_ref_dir(dir);
 	for (i = offset; i < dir->nr; i++) {
 		struct ref_entry *entry = dir->entries[i];
 		int retval;
@@ -495,6 +490,8 @@ static int do_for_each_ref_in_dirs(struct ref_dir *dir1,
 	int retval;
 	int i1 = 0, i2 = 0;
 
+	sort_ref_dir(dir1);
+	sort_ref_dir(dir2);
 	while (1) {
 		struct ref_entry *e1, *e2, *entry;
 		int cmp;
@@ -746,7 +743,6 @@ static void read_packed_refs(FILE *f, struct ref_dir *dir)
 		    !get_sha1_hex(refline + 1, sha1))
 			hashcpy(last->u.value.peeled, sha1);
 	}
-	sort_ref_dir(dir);
 }
 
 void add_extra_ref(const char *refname, const unsigned char *sha1, int flag)
@@ -849,7 +845,6 @@ static struct ref_dir *get_loose_refs(struct ref_cache *refs)
 {
 	if (!refs->did_loose) {
 		get_ref_dir(refs, "refs", &refs->loose);
-		sort_ref_dir(&refs->loose);
 		refs->did_loose = 1;
 	}
 	return &refs->loose;
diff --git a/refs.h b/refs.h
index d498291..5bb4678 100644
--- a/refs.h
+++ b/refs.h
@@ -15,8 +15,11 @@ struct ref_lock {
 #define REF_ISBROKEN 0x04
 
 /*
- * Calls the specified function for each ref file until it returns nonzero,
- * and returns the value
+ * Calls the specified function for each ref file until it returns
+ * nonzero, and returns the value.  Please note that it is not safe to
+ * modify references while an iteration is in progress, unless the
+ * same callback function invocation that modifies the reference also
+ * returns a nonzero value to immediately stop the iteration.
  */
 typedef int each_ref_fn(const char *refname, const unsigned char *sha1, int flags, void *cb_data);
 extern int head_ref(each_ref_fn, void *);
-- 
1.7.7

[PATCH 09/28] do_for_each_ref(): only iterate over the subtree that was requested

[mhagger]

From: Michael Haggerty <mhagger@alum.mit.edu>

If the base argument has a "/" chararacter, then only iterate over the
reference subdir whose name is the part up to the last "/".

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs.c |   31 ++++++++++++++++++++++++++-----
 1 files changed, 26 insertions(+), 5 deletions(-)

diff --git a/refs.c b/refs.c
index 733d7a8..515b44c 100644
--- a/refs.c
+++ b/refs.c
@@ -1156,13 +1156,34 @@ static int do_for_each_ref(const char *submodule, const char *base, each_ref_fn
 {
 	int retval = 0;
 	struct ref_cache *refs = get_ref_cache(submodule);
+	struct ref_dir *extra_dir = &extra_refs;
+	struct ref_dir *packed_dir = get_packed_refs(refs);
+	struct ref_dir *loose_dir = get_loose_refs(refs);
 
-	retval = do_for_each_ref_in_dir(&extra_refs, 0,
+	if (base && *base) {
+		extra_dir = find_containing_dir(extra_dir, base, 0);
+		packed_dir = find_containing_dir(packed_dir, base, 0);
+		loose_dir = find_containing_dir(loose_dir, base, 0);
+	}
+
+	if (extra_dir)
+		retval = do_for_each_ref_in_dir(
+				extra_dir, 0,
+				base, fn, trim, flags, cb_data);
+	if (!retval) {
+		if (packed_dir && loose_dir)
+			retval = do_for_each_ref_in_dirs(
+					packed_dir, loose_dir,
+					base, fn, trim, flags, cb_data);
+		else if (packed_dir)
+			retval = do_for_each_ref_in_dir(
+					packed_dir, 0,
 					base, fn, trim, flags, cb_data);
-	if (!retval)
-		retval = do_for_each_ref_in_dirs(get_packed_refs(refs),
-						 get_loose_refs(refs),
-						 base, fn, trim, flags, cb_data);
+		else if (loose_dir)
+			retval = do_for_each_ref_in_dir(
+					loose_dir, 0,
+					base, fn, trim, flags, cb_data);
+	}
 
 	current_ref = NULL;
 	return retval;
-- 
1.7.7

[PATCH 10/28] get_ref_dir(): keep track of the current ref_dir

[mhagger]

From: Michael Haggerty <mhagger@alum.mit.edu>

Look up the ref_dir that will hold the new entries once at the start
of processing of a directory.  This eliminates the need to search down
the reference tree to find the place to put each new reference.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs.c |   43 ++++++++++++++++++++++++++-----------------
 1 files changed, 26 insertions(+), 17 deletions(-)

diff --git a/refs.c b/refs.c
index 515b44c..bdd90c5 100644
--- a/refs.c
+++ b/refs.c
@@ -775,29 +775,36 @@ static struct ref_dir *get_packed_refs(struct ref_cache *refs)
 	return &refs->packed;
 }
 
-static void get_ref_dir(struct ref_cache *refs, const char *base,
-			struct ref_dir *dir)
+/*
+ * dirname must match the name associated with dir; in particular, it
+ * must end with '/'.
+ */
+static void get_ref_dir(struct ref_cache *refs, const char *dirname)
 {
 	DIR *d;
-	const char *path;
+	char *path;
+	int dirnamelen = strlen(dirname);
+	int pathlen;
+	struct ref_dir *dir;
+
+	assert(dirnamelen && dirname[dirnamelen - 1] == '/');
+
+	dir = find_containing_dir(&refs->loose, dirname, 1);
 
 	if (*refs->name)
-		path = git_path_submodule(refs->name, "%s", base);
+		path = git_path_submodule(refs->name, "%s", dirname);
 	else
-		path = git_path("%s", base);
-
+		path = git_path("%s", dirname);
+	pathlen = strlen(path);
+	assert(pathlen && path[pathlen - 1] == '/');
+	path[pathlen - 1] = '\0';
 
 	d = opendir(path);
 
 	if (d) {
 		struct dirent *de;
-		int baselen = strlen(base);
-		char *refname = xmalloc(baselen + 257);
-
-		memcpy(refname, base, baselen);
-		if (baselen && base[baselen-1] != '/')
-			refname[baselen++] = '/';
-
+		char *refname = xmalloc(dirnamelen + 257);
+		memcpy(refname, dirname, dirnamelen);
 		while ((de = readdir(d)) != NULL) {
 			unsigned char sha1[20];
 			struct stat st;
@@ -812,14 +819,16 @@ static void get_ref_dir(struct ref_cache *refs, const char *base,
 				continue;
 			if (has_extension(de->d_name, ".lock"))
 				continue;
-			memcpy(refname + baselen, de->d_name, namelen+1);
+			memcpy(refname + dirnamelen, de->d_name, namelen+1);
 			refdir = *refs->name
 				? git_path_submodule(refs->name, "%s", refname)
 				: git_path("%s", refname);
 			if (stat(refdir, &st) < 0)
 				continue;
 			if (S_ISDIR(st.st_mode)) {
-				get_ref_dir(refs, refname, dir);
+				refname[dirnamelen + namelen] = '/';
+				refname[dirnamelen + namelen + 1] = '\0';
+				get_ref_dir(refs, refname);
 				continue;
 			}
 			if (*refs->name) {
@@ -834,7 +843,7 @@ static void get_ref_dir(struct ref_cache *refs, const char *base,
 					hashclr(sha1);
 					flag |= REF_ISBROKEN;
 				}
-			add_ref(dir, create_ref_entry(refname, sha1, flag));
+			add_entry_to_dir(dir, create_ref_entry(refname, sha1, flag));
 		}
 		free(refname);
 		closedir(d);
@@ -844,7 +853,7 @@ static void get_ref_dir(struct ref_cache *refs, const char *base,
 static struct ref_dir *get_loose_refs(struct ref_cache *refs)
 {
 	if (!refs->did_loose) {
-		get_ref_dir(refs, "refs", &refs->loose);
+		get_ref_dir(refs, "refs/");
 		refs->did_loose = 1;
 	}
 	return &refs->loose;
-- 
1.7.7

[PATCH 11/28] refs: wrap top-level ref_dirs in ref_entries

[mhagger]

From: Michael Haggerty <mhagger@alum.mit.edu>

Wrap the top-level ref_dirs in REF_DIR style ref_entries so that we
have the flag and name available when dealing with them.  This
affects:

* cache_ref::loose
* cache_ref::packed
* extra_refs

The next several commits will expand the use of ref_entry as opposed
to ref_dir, culminating in the ability of a ref_entry representing a
directory of loose references to load itself only when used.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs.c |   54 ++++++++++++++++++++++++++++++------------------------
 1 files changed, 30 insertions(+), 24 deletions(-)

diff --git a/refs.c b/refs.c
index bdd90c5..673fa04 100644
--- a/refs.c
+++ b/refs.c
@@ -256,7 +256,7 @@ static void clear_ref_dir(struct ref_dir *dir)
 /*
  * Create a struct ref_entry object for the specified dirname.
  * dirname is the name of the directory with a trailing slash (e.g.,
- * "refs/heads/").
+ * "refs/heads/") or "" for the top-level directory.
  */
 static struct ref_entry *create_dir_entry(const char *dirname)
 {
@@ -609,28 +609,28 @@ static int is_refname_available(const char *refname, const char *oldrefname,
  */
 static struct ref_cache {
 	struct ref_cache *next;
-	char did_loose;
-	char did_packed;
-	struct ref_dir loose;
-	struct ref_dir packed;
+	struct ref_entry *loose;
+	struct ref_entry *packed;
 	/* The submodule name, or "" for the main repo. */
 	char name[FLEX_ARRAY];
 } *ref_cache;
 
-static struct ref_dir extra_refs;
+static struct ref_entry *extra_refs;
 
 static void clear_packed_ref_cache(struct ref_cache *refs)
 {
-	if (refs->did_packed)
-		clear_ref_dir(&refs->packed);
-	refs->did_packed = 0;
+	if (refs->packed) {
+		free_ref_entry(refs->packed);
+		refs->packed = NULL;
+	}
 }
 
 static void clear_loose_ref_cache(struct ref_cache *refs)
 {
-	if (refs->did_loose)
-		clear_ref_dir(&refs->loose);
-	refs->did_loose = 0;
+	if (refs->loose) {
+		free_ref_entry(refs->loose);
+		refs->loose = NULL;
+	}
 }
 
 static struct ref_cache *create_ref_cache(const char *submodule)
@@ -747,32 +747,37 @@ static void read_packed_refs(FILE *f, struct ref_dir *dir)
 
 void add_extra_ref(const char *refname, const unsigned char *sha1, int flag)
 {
-	add_ref(&extra_refs, create_ref_entry(refname, sha1, flag));
+	if (!extra_refs)
+		extra_refs = create_dir_entry("");
+	add_ref(&extra_refs->u.subdir, create_ref_entry(refname, sha1, flag));
 }
 
 void clear_extra_refs(void)
 {
-	clear_ref_dir(&extra_refs);
+	if (extra_refs) {
+		free_ref_entry(extra_refs);
+		extra_refs = NULL;
+	}
 }
 
 static struct ref_dir *get_packed_refs(struct ref_cache *refs)
 {
-	if (!refs->did_packed) {
+	if (!refs->packed) {
 		const char *packed_refs_file;
 		FILE *f;
 
+		refs->packed = create_dir_entry("");
 		if (*refs->name)
 			packed_refs_file = git_path_submodule(refs->name, "packed-refs");
 		else
 			packed_refs_file = git_path("packed-refs");
 		f = fopen(packed_refs_file, "r");
 		if (f) {
-			read_packed_refs(f, &refs->packed);
+			read_packed_refs(f, &refs->packed->u.subdir);
 			fclose(f);
 		}
-		refs->did_packed = 1;
 	}
-	return &refs->packed;
+	return &refs->packed->u.subdir;
 }
 
 /*
@@ -789,7 +794,7 @@ static void get_ref_dir(struct ref_cache *refs, const char *dirname)
 
 	assert(dirnamelen && dirname[dirnamelen - 1] == '/');
 
-	dir = find_containing_dir(&refs->loose, dirname, 1);
+	dir = find_containing_dir(&refs->loose->u.subdir, dirname, 1);
 
 	if (*refs->name)
 		path = git_path_submodule(refs->name, "%s", dirname);
@@ -852,11 +857,11 @@ static void get_ref_dir(struct ref_cache *refs, const char *dirname)
 
 static struct ref_dir *get_loose_refs(struct ref_cache *refs)
 {
-	if (!refs->did_loose) {
+	if (!refs->loose) {
+		refs->loose = create_dir_entry("");
 		get_ref_dir(refs, "refs/");
-		refs->did_loose = 1;
 	}
-	return &refs->loose;
+	return &refs->loose->u.subdir;
 }
 
 /* We allow "recursive" symbolic refs. Only within reason, though */
@@ -1165,12 +1170,13 @@ static int do_for_each_ref(const char *submodule, const char *base, each_ref_fn
 {
 	int retval = 0;
 	struct ref_cache *refs = get_ref_cache(submodule);
-	struct ref_dir *extra_dir = &extra_refs;
+	struct ref_dir *extra_dir = extra_refs ? &extra_refs->u.subdir : NULL;
 	struct ref_dir *packed_dir = get_packed_refs(refs);
 	struct ref_dir *loose_dir = get_loose_refs(refs);
 
 	if (base && *base) {
-		extra_dir = find_containing_dir(extra_dir, base, 0);
+		if (extra_dir)
+			extra_dir = find_containing_dir(extra_dir, base, 0);
 		packed_dir = find_containing_dir(packed_dir, base, 0);
 		loose_dir = find_containing_dir(loose_dir, base, 0);
 	}
-- 
1.7.7

[PATCH 12/28] get_packed_refs(): return (ref_entry *) instead of (ref_dir *)

[mhagger]

From: Michael Haggerty <mhagger@alum.mit.edu>


Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs.c |   33 +++++++++++++++++----------------
 1 files changed, 17 insertions(+), 16 deletions(-)

diff --git a/refs.c b/refs.c
index 673fa04..425fdaa 100644
--- a/refs.c
+++ b/refs.c
@@ -760,7 +760,7 @@ void clear_extra_refs(void)
 	}
 }
 
-static struct ref_dir *get_packed_refs(struct ref_cache *refs)
+static struct ref_entry *get_packed_refs(struct ref_cache *refs)
 {
 	if (!refs->packed) {
 		const char *packed_refs_file;
@@ -777,7 +777,7 @@ static struct ref_dir *get_packed_refs(struct ref_cache *refs)
 			fclose(f);
 		}
 	}
-	return &refs->packed->u.subdir;
+	return refs->packed;
 }
 
 /*
@@ -877,9 +877,9 @@ static int resolve_gitlink_packed_ref(struct ref_cache *refs,
 				      const char *refname, unsigned char *sha1)
 {
 	struct ref_entry *ref;
-	struct ref_dir *dir = get_packed_refs(refs);
+	struct ref_entry *direntry = get_packed_refs(refs);
 
-	ref = find_ref(dir, refname);
+	ref = find_ref(&direntry->u.subdir, refname);
 	if (ref == NULL)
 		return -1;
 
@@ -950,8 +950,8 @@ int resolve_gitlink_ref(const char *path, const char *refname, unsigned char *sh
  */
 static int get_packed_ref(const char *refname, unsigned char *sha1)
 {
-	struct ref_dir *packed = get_packed_refs(get_ref_cache(NULL));
-	struct ref_entry *entry = find_ref(packed, refname);
+	struct ref_entry *packed = get_packed_refs(get_ref_cache(NULL));
+	struct ref_entry *entry = find_ref(&packed->u.subdir, refname);
 	if (entry) {
 		hashcpy(sha1, entry->u.value.sha1);
 		return 0;
@@ -1110,8 +1110,8 @@ int peel_ref(const char *refname, unsigned char *sha1)
 		return -1;
 
 	if ((flag & REF_ISPACKED)) {
-		struct ref_dir *dir = get_packed_refs(get_ref_cache(NULL));
-		struct ref_entry *r = find_ref(dir, refname);
+		struct ref_entry *direntry = get_packed_refs(get_ref_cache(NULL));
+		struct ref_entry *r = find_ref(&direntry->u.subdir, refname);
 
 		if (r != NULL && r->flag & REF_KNOWS_PEELED) {
 			hashcpy(sha1, r->u.value.peeled);
@@ -1171,7 +1171,8 @@ static int do_for_each_ref(const char *submodule, const char *base, each_ref_fn
 	int retval = 0;
 	struct ref_cache *refs = get_ref_cache(submodule);
 	struct ref_dir *extra_dir = extra_refs ? &extra_refs->u.subdir : NULL;
-	struct ref_dir *packed_dir = get_packed_refs(refs);
+	struct ref_entry *packed_direntry = get_packed_refs(refs);
+	struct ref_dir *packed_dir = &packed_direntry->u.subdir;
 	struct ref_dir *loose_dir = get_loose_refs(refs);
 
 	if (base && *base) {
@@ -1564,7 +1565,8 @@ static struct ref_lock *lock_ref_sha1_basic(const char *refname,
 	 * name is a proper prefix of our refname.
 	 */
 	if (missing &&
-	     !is_refname_available(refname, NULL, get_packed_refs(get_ref_cache(NULL)))) {
+	     !is_refname_available(refname, NULL,
+				   &get_packed_refs(get_ref_cache(NULL))->u.subdir)) {
 		last_errno = ENOTDIR;
 		goto error_return;
 	}
@@ -1644,10 +1646,8 @@ static struct lock_file packlock;
 static int repack_without_ref(const char *refname)
 {
 	struct repack_without_ref_sb data;
-	struct ref_dir *packed;
-
-	packed = get_packed_refs(get_ref_cache(NULL));
-	if (find_ref(packed, refname) == NULL)
+	struct ref_entry *packed = get_packed_refs(get_ref_cache(NULL));
+	if (find_ref(&packed->u.subdir, refname) == NULL)
 		return 0;
 	data.refname = refname;
 	data.fd = hold_lock_file_for_update(&packlock, git_path("packed-refs"), 0);
@@ -1655,7 +1655,8 @@ static int repack_without_ref(const char *refname)
 		unable_to_lock_error(git_path("packed-refs"), errno);
 		return error("cannot delete '%s' from packed refs", refname);
 	}
-	do_for_each_ref_in_dir(packed, 0, "", repack_without_ref_fn, 0, 0, &data);
+	do_for_each_ref_in_dir(&packed->u.subdir, 0,
+			       "", repack_without_ref_fn, 0, 0, &data);
 	return commit_lock_file(&packlock);
 }
 
@@ -1726,7 +1727,7 @@ int rename_ref(const char *oldrefname, const char *newrefname, const char *logms
 	if (!symref)
 		return error("refname %s not found", oldrefname);
 
-	if (!is_refname_available(newrefname, oldrefname, get_packed_refs(refs)))
+	if (!is_refname_available(newrefname, oldrefname, &get_packed_refs(refs)->u.subdir))
 		return 1;
 
 	if (!is_refname_available(newrefname, oldrefname, get_loose_refs(refs)))
-- 
1.7.7

[PATCH 13/28] get_loose_refs(): return (ref_entry *) instead of (ref_dir *)

[mhagger]

From: Michael Haggerty <mhagger@alum.mit.edu>


Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs.c |    9 +++++----
 1 files changed, 5 insertions(+), 4 deletions(-)

diff --git a/refs.c b/refs.c
index 425fdaa..d6d5d0e 100644
--- a/refs.c
+++ b/refs.c
@@ -855,13 +855,13 @@ static void get_ref_dir(struct ref_cache *refs, const char *dirname)
 	}
 }
 
-static struct ref_dir *get_loose_refs(struct ref_cache *refs)
+static struct ref_entry *get_loose_refs(struct ref_cache *refs)
 {
 	if (!refs->loose) {
 		refs->loose = create_dir_entry("");
 		get_ref_dir(refs, "refs/");
 	}
-	return &refs->loose->u.subdir;
+	return refs->loose;
 }
 
 /* We allow "recursive" symbolic refs. Only within reason, though */
@@ -1173,7 +1173,8 @@ static int do_for_each_ref(const char *submodule, const char *base, each_ref_fn
 	struct ref_dir *extra_dir = extra_refs ? &extra_refs->u.subdir : NULL;
 	struct ref_entry *packed_direntry = get_packed_refs(refs);
 	struct ref_dir *packed_dir = &packed_direntry->u.subdir;
-	struct ref_dir *loose_dir = get_loose_refs(refs);
+	struct ref_entry *loose_direntry = get_loose_refs(refs);
+	struct ref_dir *loose_dir = &loose_direntry->u.subdir;
 
 	if (base && *base) {
 		if (extra_dir)
@@ -1730,7 +1731,7 @@ int rename_ref(const char *oldrefname, const char *newrefname, const char *logms
 	if (!is_refname_available(newrefname, oldrefname, &get_packed_refs(refs)->u.subdir))
 		return 1;
 
-	if (!is_refname_available(newrefname, oldrefname, get_loose_refs(refs)))
+	if (!is_refname_available(newrefname, oldrefname, &get_loose_refs(refs)->u.subdir))
 		return 1;
 
 	if (log && rename(git_path("logs/%s", oldrefname), git_path(TMP_RENAMED_LOG)))
-- 
1.7.7

[PATCH 14/28] is_refname_available(): take (ref_entry *) instead of (ref_dir *)

[mhagger]

From: Michael Haggerty <mhagger@alum.mit.edu>


Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs.c |   12 +++++++-----
 1 files changed, 7 insertions(+), 5 deletions(-)

diff --git a/refs.c b/refs.c
index d6d5d0e..6bda033 100644
--- a/refs.c
+++ b/refs.c
@@ -586,14 +586,16 @@ static int name_conflict_fn(const char *existingrefname, const unsigned char *sh
  * operation).
  */
 static int is_refname_available(const char *refname, const char *oldrefname,
-				struct ref_dir *dir)
+				struct ref_entry *direntry)
 {
 	struct name_conflict_cb data;
 	data.refname = refname;
 	data.oldrefname = oldrefname;
 	data.conflicting_refname = NULL;
 
-	if (do_for_each_ref_in_dir(dir, 0, "", name_conflict_fn,
+	assert(direntry->flag & REF_DIR);
+
+	if (do_for_each_ref_in_dir(&direntry->u.subdir, 0, "", name_conflict_fn,
 				   0, DO_FOR_EACH_INCLUDE_BROKEN,
 				   &data)) {
 		error("'%s' exists; cannot create '%s'",
@@ -1567,7 +1569,7 @@ static struct ref_lock *lock_ref_sha1_basic(const char *refname,
 	 */
 	if (missing &&
 	     !is_refname_available(refname, NULL,
-				   &get_packed_refs(get_ref_cache(NULL))->u.subdir)) {
+				   get_packed_refs(get_ref_cache(NULL)))) {
 		last_errno = ENOTDIR;
 		goto error_return;
 	}
@@ -1728,10 +1730,10 @@ int rename_ref(const char *oldrefname, const char *newrefname, const char *logms
 	if (!symref)
 		return error("refname %s not found", oldrefname);
 
-	if (!is_refname_available(newrefname, oldrefname, &get_packed_refs(refs)->u.subdir))
+	if (!is_refname_available(newrefname, oldrefname, get_packed_refs(refs)))
 		return 1;
 
-	if (!is_refname_available(newrefname, oldrefname, &get_loose_refs(refs)->u.subdir))
+	if (!is_refname_available(newrefname, oldrefname, get_loose_refs(refs)))
 		return 1;
 
 	if (log && rename(git_path("logs/%s", oldrefname), git_path(TMP_RENAMED_LOG)))
-- 
1.7.7

[PATCH 15/28] find_ref(): take (ref_entry *) instead of (ref_dir *)

[mhagger]

From: Michael Haggerty <mhagger@alum.mit.edu>


Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs.c |   14 ++++++++------
 1 files changed, 8 insertions(+), 6 deletions(-)

diff --git a/refs.c b/refs.c
index 6bda033..e7d4482 100644
--- a/refs.c
+++ b/refs.c
@@ -363,10 +363,12 @@ static struct ref_dir *find_containing_dir(struct ref_dir *dir,
  * subdirectories as necessary.  If the name is not found or it
  * corresponds to a directory entry, return NULL.
  */
-static struct ref_entry *find_ref(struct ref_dir *dir, const char *refname)
+static struct ref_entry *find_ref(struct ref_entry *direntry, const char *refname)
 {
 	struct ref_entry *entry;
-	dir = find_containing_dir(dir, refname, 0);
+	struct ref_dir *dir;
+	assert(direntry->flag & REF_DIR);
+	dir = find_containing_dir(&direntry->u.subdir, refname, 0);
 	if (!dir)
 		return NULL;
 	entry = search_ref_dir(dir, refname);
@@ -881,7 +883,7 @@ static int resolve_gitlink_packed_ref(struct ref_cache *refs,
 	struct ref_entry *ref;
 	struct ref_entry *direntry = get_packed_refs(refs);
 
-	ref = find_ref(&direntry->u.subdir, refname);
+	ref = find_ref(direntry, refname);
 	if (ref == NULL)
 		return -1;
 
@@ -953,7 +955,7 @@ int resolve_gitlink_ref(const char *path, const char *refname, unsigned char *sh
 static int get_packed_ref(const char *refname, unsigned char *sha1)
 {
 	struct ref_entry *packed = get_packed_refs(get_ref_cache(NULL));
-	struct ref_entry *entry = find_ref(&packed->u.subdir, refname);
+	struct ref_entry *entry = find_ref(packed, refname);
 	if (entry) {
 		hashcpy(sha1, entry->u.value.sha1);
 		return 0;
@@ -1113,7 +1115,7 @@ int peel_ref(const char *refname, unsigned char *sha1)
 
 	if ((flag & REF_ISPACKED)) {
 		struct ref_entry *direntry = get_packed_refs(get_ref_cache(NULL));
-		struct ref_entry *r = find_ref(&direntry->u.subdir, refname);
+		struct ref_entry *r = find_ref(direntry, refname);
 
 		if (r != NULL && r->flag & REF_KNOWS_PEELED) {
 			hashcpy(sha1, r->u.value.peeled);
@@ -1650,7 +1652,7 @@ static int repack_without_ref(const char *refname)
 {
 	struct repack_without_ref_sb data;
 	struct ref_entry *packed = get_packed_refs(get_ref_cache(NULL));
-	if (find_ref(&packed->u.subdir, refname) == NULL)
+	if (find_ref(packed, refname) == NULL)
 		return 0;
 	data.refname = refname;
 	data.fd = hold_lock_file_for_update(&packlock, git_path("packed-refs"), 0);
-- 
1.7.7

[PATCH 16/28] read_packed_refs(): take (ref_entry *) instead of (ref_dir *)

[mhagger]

From: Michael Haggerty <mhagger@alum.mit.edu>


Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs.c |    7 ++++---
 1 files changed, 4 insertions(+), 3 deletions(-)

diff --git a/refs.c b/refs.c
index e7d4482..f402d39 100644
--- a/refs.c
+++ b/refs.c
@@ -715,12 +715,13 @@ static const char *parse_ref_line(char *line, unsigned char *sha1)
 	return line;
 }
 
-static void read_packed_refs(FILE *f, struct ref_dir *dir)
+static void read_packed_refs(FILE *f, struct ref_entry *direntry)
 {
 	struct ref_entry *last = NULL;
 	char refline[PATH_MAX];
 	int flag = REF_ISPACKED;
 
+	assert(direntry->flag & REF_DIR);
 	while (fgets(refline, sizeof(refline), f)) {
 		unsigned char sha1[20];
 		const char *refname;
@@ -737,7 +738,7 @@ static void read_packed_refs(FILE *f, struct ref_dir *dir)
 		refname = parse_ref_line(refline, sha1);
 		if (refname) {
 			last = create_ref_entry(refname, sha1, flag);
-			add_ref(dir, last);
+			add_ref(&direntry->u.subdir, last);
 			continue;
 		}
 		if (last &&
@@ -777,7 +778,7 @@ static struct ref_entry *get_packed_refs(struct ref_cache *refs)
 			packed_refs_file = git_path("packed-refs");
 		f = fopen(packed_refs_file, "r");
 		if (f) {
-			read_packed_refs(f, &refs->packed->u.subdir);
+			read_packed_refs(f, refs->packed);
 			fclose(f);
 		}
 	}
-- 
1.7.7

[PATCH 17/28] add_ref(): take (ref_entry *) instead of (ref_dir *)

[mhagger]

From: Michael Haggerty <mhagger@alum.mit.edu>


Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs.c |   10 ++++++----
 1 files changed, 6 insertions(+), 4 deletions(-)

diff --git a/refs.c b/refs.c
index f402d39..f5aaafe 100644
--- a/refs.c
+++ b/refs.c
@@ -380,9 +380,11 @@ static struct ref_entry *find_ref(struct ref_entry *direntry, const char *refnam
  * subdirectories as necessary.  dir must represent the top-level
  * directory.  Return 0 on success.
  */
-static int add_ref(struct ref_dir *dir, struct ref_entry *ref)
+static int add_ref(struct ref_entry *direntry, struct ref_entry *ref)
 {
-	dir = find_containing_dir(dir, ref->name, 1);
+	struct ref_dir *dir;
+	assert(direntry->flag & REF_DIR);
+	dir = find_containing_dir(&direntry->u.subdir, ref->name, 1);
 	if (!dir)
 		return -1;
 	add_entry_to_dir(dir, ref);
@@ -738,7 +740,7 @@ static void read_packed_refs(FILE *f, struct ref_entry *direntry)
 		refname = parse_ref_line(refline, sha1);
 		if (refname) {
 			last = create_ref_entry(refname, sha1, flag);
-			add_ref(&direntry->u.subdir, last);
+			add_ref(direntry, last);
 			continue;
 		}
 		if (last &&
@@ -754,7 +756,7 @@ void add_extra_ref(const char *refname, const unsigned char *sha1, int flag)
 {
 	if (!extra_refs)
 		extra_refs = create_dir_entry("");
-	add_ref(&extra_refs->u.subdir, create_ref_entry(refname, sha1, flag));
+	add_ref(extra_refs, create_ref_entry(refname, sha1, flag));
 }
 
 void clear_extra_refs(void)
-- 
1.7.7

[PATCH 18/28] find_containing_direntry(): use (ref_entry *) instead of (ref_dir *)

[mhagger]

From: Michael Haggerty <mhagger@alum.mit.edu>

Change type of both argument and return value.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs.c |   78 ++++++++++++++++++++++++++++++++--------------------------------
 1 files changed, 39 insertions(+), 39 deletions(-)

diff --git a/refs.c b/refs.c
index f5aaafe..35b3ff2 100644
--- a/refs.c
+++ b/refs.c
@@ -324,38 +324,40 @@ static struct ref_entry *search_ref_dir(struct ref_dir *dir, const char *refname
 }
 
 /*
- * If refname is a reference name, find the ref_dir within the dir
+ * If refname is a reference name, find the ref_entry within the dir
  * tree that should hold refname.  If refname is a directory name
- * (i.e., ends in '/'), then return that ref_dir itself.  dir must
- * represent the top-level directory.  Recurse into subdirectories as
- * necessary.  If mkdir is set, then create any missing directories;
- * otherwise, return NULL if the desired directory cannot be found.
+ * (i.e., "" or ends in '/'), then return that ref_entry itself.  dir
+ * must represent the top-level directory.  Recurse into
+ * subdirectories as necessary.  If mkdir is set, then create any
+ * missing directories; otherwise, return NULL if the desired
+ * directory cannot be found.
  */
-static struct ref_dir *find_containing_dir(struct ref_dir *dir,
-					   const char *refname, int mkdir)
+static struct ref_entry *find_containing_direntry(struct ref_entry *direntry,
+						  const char *refname, int mkdir)
 {
 	char *refname_copy = xstrdup(refname);
 	char *slash;
-	struct ref_entry *entry;
+	assert(direntry->flag & REF_DIR);
 	for (slash = strchr(refname_copy, '/'); slash; slash = strchr(slash + 1, '/')) {
 		char tmp = slash[1];
+		struct ref_entry *entry;
 		slash[1] = '\0';
-		entry = search_ref_dir(dir, refname_copy);
+		entry = search_ref_dir(&direntry->u.subdir, refname_copy);
 		if (!entry) {
 			if (!mkdir) {
-				dir = NULL;
+				direntry = NULL;
 				break;
 			}
 			entry = create_dir_entry(refname_copy);
-			add_entry_to_dir(dir, entry);
+			add_entry_to_dir(&direntry->u.subdir, entry);
 		}
 		slash[1] = tmp;
 		assert(entry->flag & REF_DIR);
-		dir = &entry->u.subdir;
+		direntry = entry;
 	}
 
 	free(refname_copy);
-	return dir;
+	return direntry;
 }
 
 /*
@@ -366,12 +368,11 @@ static struct ref_dir *find_containing_dir(struct ref_dir *dir,
 static struct ref_entry *find_ref(struct ref_entry *direntry, const char *refname)
 {
 	struct ref_entry *entry;
-	struct ref_dir *dir;
 	assert(direntry->flag & REF_DIR);
-	dir = find_containing_dir(&direntry->u.subdir, refname, 0);
-	if (!dir)
+	direntry = find_containing_direntry(direntry, refname, 0);
+	if (!direntry)
 		return NULL;
-	entry = search_ref_dir(dir, refname);
+	entry = search_ref_dir(&direntry->u.subdir, refname);
 	return (entry && !(entry->flag & REF_DIR)) ? entry : NULL;
 }
 
@@ -382,12 +383,11 @@ static struct ref_entry *find_ref(struct ref_entry *direntry, const char *refnam
  */
 static int add_ref(struct ref_entry *direntry, struct ref_entry *ref)
 {
-	struct ref_dir *dir;
 	assert(direntry->flag & REF_DIR);
-	dir = find_containing_dir(&direntry->u.subdir, ref->name, 1);
-	if (!dir)
+	direntry = find_containing_direntry(direntry, ref->name, 1);
+	if (!direntry)
 		return -1;
-	add_entry_to_dir(dir, ref);
+	add_entry_to_dir(&direntry->u.subdir, ref);
 	return 0;
 }
 
@@ -797,11 +797,11 @@ static void get_ref_dir(struct ref_cache *refs, const char *dirname)
 	char *path;
 	int dirnamelen = strlen(dirname);
 	int pathlen;
-	struct ref_dir *dir;
+	struct ref_entry *direntry;
 
 	assert(dirnamelen && dirname[dirnamelen - 1] == '/');
 
-	dir = find_containing_dir(&refs->loose->u.subdir, dirname, 1);
+	direntry = find_containing_direntry(refs->loose, dirname, 1);
 
 	if (*refs->name)
 		path = git_path_submodule(refs->name, "%s", dirname);
@@ -855,7 +855,8 @@ static void get_ref_dir(struct ref_cache *refs, const char *dirname)
 					hashclr(sha1);
 					flag |= REF_ISBROKEN;
 				}
-			add_entry_to_dir(dir, create_ref_entry(refname, sha1, flag));
+			add_entry_to_dir(&direntry->u.subdir,
+					 create_ref_entry(refname, sha1, flag));
 		}
 		free(refname);
 		closedir(d);
@@ -1177,35 +1178,34 @@ static int do_for_each_ref(const char *submodule, const char *base, each_ref_fn
 {
 	int retval = 0;
 	struct ref_cache *refs = get_ref_cache(submodule);
-	struct ref_dir *extra_dir = extra_refs ? &extra_refs->u.subdir : NULL;
+	struct ref_entry *extra_direntry = extra_refs;
 	struct ref_entry *packed_direntry = get_packed_refs(refs);
-	struct ref_dir *packed_dir = &packed_direntry->u.subdir;
 	struct ref_entry *loose_direntry = get_loose_refs(refs);
-	struct ref_dir *loose_dir = &loose_direntry->u.subdir;
 
 	if (base && *base) {
-		if (extra_dir)
-			extra_dir = find_containing_dir(extra_dir, base, 0);
-		packed_dir = find_containing_dir(packed_dir, base, 0);
-		loose_dir = find_containing_dir(loose_dir, base, 0);
+		if (extra_direntry)
+			extra_direntry = find_containing_direntry(extra_direntry, base, 0);
+		packed_direntry = find_containing_direntry(packed_direntry, base, 0);
+		loose_direntry = find_containing_direntry(loose_direntry, base, 0);
 	}
 
-	if (extra_dir)
+	if (extra_direntry)
 		retval = do_for_each_ref_in_dir(
-				extra_dir, 0,
+				&extra_direntry->u.subdir, 0,
 				base, fn, trim, flags, cb_data);
 	if (!retval) {
-		if (packed_dir && loose_dir)
+		if (packed_direntry && loose_direntry)
 			retval = do_for_each_ref_in_dirs(
-					packed_dir, loose_dir,
+					&packed_direntry->u.subdir,
+					&loose_direntry->u.subdir,
 					base, fn, trim, flags, cb_data);
-		else if (packed_dir)
+		else if (packed_direntry)
 			retval = do_for_each_ref_in_dir(
-					packed_dir, 0,
+					&packed_direntry->u.subdir, 0,
 					base, fn, trim, flags, cb_data);
-		else if (loose_dir)
+		else if (loose_direntry)
 			retval = do_for_each_ref_in_dir(
-					loose_dir, 0,
+					&loose_direntry->u.subdir, 0,
 					base, fn, trim, flags, cb_data);
 	}
 
-- 
1.7.7

[PATCH 19/28] search_ref_dir(): take (ref_entry *) instead of (ref_dir *)

[mhagger]

From: Michael Haggerty <mhagger@alum.mit.edu>


Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs.c |    9 ++++++---
 1 files changed, 6 insertions(+), 3 deletions(-)

diff --git a/refs.c b/refs.c
index 35b3ff2..e91cc15 100644
--- a/refs.c
+++ b/refs.c
@@ -288,11 +288,14 @@ static void sort_ref_dir(struct ref_dir *dir);
  * Return the entry with the given refname from the ref_dir
  * (non-recursively).  Return NULL if no such entry is found.
  */
-static struct ref_entry *search_ref_dir(struct ref_dir *dir, const char *refname)
+static struct ref_entry *search_ref_dir(struct ref_entry *direntry, const char *refname)
 {
 	struct ref_entry *e, **r;
 	int len;
+	struct ref_dir *dir;
 
+	assert(direntry->flag & REF_DIR);
+	dir = &direntry->u.subdir;
 	if (refname == NULL || !dir->nr)
 		return NULL;
 
@@ -342,7 +345,7 @@ static struct ref_entry *find_containing_direntry(struct ref_entry *direntry,
 		char tmp = slash[1];
 		struct ref_entry *entry;
 		slash[1] = '\0';
-		entry = search_ref_dir(&direntry->u.subdir, refname_copy);
+		entry = search_ref_dir(direntry, refname_copy);
 		if (!entry) {
 			if (!mkdir) {
 				direntry = NULL;
@@ -372,7 +375,7 @@ static struct ref_entry *find_ref(struct ref_entry *direntry, const char *refnam
 	direntry = find_containing_direntry(direntry, refname, 0);
 	if (!direntry)
 		return NULL;
-	entry = search_ref_dir(&direntry->u.subdir, refname);
+	entry = search_ref_dir(direntry, refname);
 	return (entry && !(entry->flag & REF_DIR)) ? entry : NULL;
 }
 
-- 
1.7.7

[PATCH 20/28] add_entry(): take (ref_entry *) instead of (ref_dir *)

[mhagger]

From: Michael Haggerty <mhagger@alum.mit.edu>


Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs.c |   12 +++++++-----
 1 files changed, 7 insertions(+), 5 deletions(-)

diff --git a/refs.c b/refs.c
index e91cc15..3567d56 100644
--- a/refs.c
+++ b/refs.c
@@ -234,8 +234,11 @@ static void free_ref_entry(struct ref_entry *entry)
  * stored directly in dir; no recursion into subdirectories is
  * done.
  */
-static void add_entry_to_dir(struct ref_dir *dir, struct ref_entry *entry)
+static void add_entry(struct ref_entry *direntry, struct ref_entry *entry)
 {
+	struct ref_dir *dir;
+	assert(direntry->flag & REF_DIR);
+	dir = &direntry->u.subdir;
 	ALLOC_GROW(dir->entries, dir->nr + 1, dir->alloc);
 	dir->entries[dir->nr++] = entry;
 }
@@ -352,7 +355,7 @@ static struct ref_entry *find_containing_direntry(struct ref_entry *direntry,
 				break;
 			}
 			entry = create_dir_entry(refname_copy);
-			add_entry_to_dir(&direntry->u.subdir, entry);
+			add_entry(direntry, entry);
 		}
 		slash[1] = tmp;
 		assert(entry->flag & REF_DIR);
@@ -390,7 +393,7 @@ static int add_ref(struct ref_entry *direntry, struct ref_entry *ref)
 	direntry = find_containing_direntry(direntry, ref->name, 1);
 	if (!direntry)
 		return -1;
-	add_entry_to_dir(&direntry->u.subdir, ref);
+	add_entry(direntry, ref);
 	return 0;
 }
 
@@ -858,8 +861,7 @@ static void get_ref_dir(struct ref_cache *refs, const char *dirname)
 					hashclr(sha1);
 					flag |= REF_ISBROKEN;
 				}
-			add_entry_to_dir(&direntry->u.subdir,
-					 create_ref_entry(refname, sha1, flag));
+			add_entry(direntry, create_ref_entry(refname, sha1, flag));
 		}
 		free(refname);
 		closedir(d);
-- 
1.7.7

[PATCH 21/28] do_for_each_ref_in_dir*(): take (ref_entry *) instead of (ref_dir *)

[mhagger]

From: Michael Haggerty <mhagger@alum.mit.edu>


Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs.c |   38 ++++++++++++++++++++++----------------
 1 files changed, 22 insertions(+), 16 deletions(-)

diff --git a/refs.c b/refs.c
index 3567d56..c3ee93d 100644
--- a/refs.c
+++ b/refs.c
@@ -471,17 +471,20 @@ static int do_one_ref(const char *base, each_ref_fn fn, int trim,
 	return fn(entry->name + trim, entry->u.value.sha1, entry->flag, cb_data);
 }
 
-static int do_for_each_ref_in_dir(struct ref_dir *dir, int offset,
+static int do_for_each_ref_in_dir(struct ref_entry *direntry, int offset,
 				  const char *base,
 				  each_ref_fn fn, int trim, int flags, void *cb_data)
 {
 	int i;
+	struct ref_dir *dir;
+	assert(direntry->flag & REF_DIR);
+	dir = &direntry->u.subdir;
 	sort_ref_dir(dir);
 	for (i = offset; i < dir->nr; i++) {
 		struct ref_entry *entry = dir->entries[i];
 		int retval;
 		if (entry->flag & REF_DIR) {
-			retval = do_for_each_ref_in_dir(&entry->u.subdir, 0,
+			retval = do_for_each_ref_in_dir(entry, 0,
 							base, fn, trim, flags, cb_data);
 		} else {
 			retval = do_one_ref(base, fn, trim, flags, cb_data, entry);
@@ -492,25 +495,30 @@ static int do_for_each_ref_in_dir(struct ref_dir *dir, int offset,
 	return 0;
 }
 
-static int do_for_each_ref_in_dirs(struct ref_dir *dir1,
-				   struct ref_dir *dir2,
+static int do_for_each_ref_in_dirs(struct ref_entry *direntry1,
+				   struct ref_entry *direntry2,
 				   const char *base, each_ref_fn fn, int trim,
 				   int flags, void *cb_data)
 {
 	int retval;
 	int i1 = 0, i2 = 0;
+	struct ref_dir *dir1, *dir2;
 
+	assert(direntry1->flag & REF_DIR);
+	assert(direntry2->flag & REF_DIR);
+	dir1 = &direntry1->u.subdir;
+	dir2 = &direntry2->u.subdir;
 	sort_ref_dir(dir1);
 	sort_ref_dir(dir2);
 	while (1) {
 		struct ref_entry *e1, *e2, *entry;
 		int cmp;
 		if (i1 == dir1->nr) {
-			return do_for_each_ref_in_dir(dir2, i2,
+			return do_for_each_ref_in_dir(direntry2, i2,
 						      base, fn, trim, flags, cb_data);
 		}
 		if (i2 == dir2->nr) {
-			return do_for_each_ref_in_dir(dir1, i1,
+			return do_for_each_ref_in_dir(direntry1, i1,
 						      base, fn, trim, flags, cb_data);
 		}
 		e1 = dir1->entries[i1];
@@ -520,7 +528,7 @@ static int do_for_each_ref_in_dirs(struct ref_dir *dir1,
 			if ((e1->flag & REF_DIR) && (e2->flag & REF_DIR)) {
 				/* Both are directories; descend them in parallel. */
 				retval = do_for_each_ref_in_dirs(
-						&e1->u.subdir, &e2->u.subdir,
+						e1, e2,
 						base, fn, trim, flags, cb_data);
 				i1++;
 				i2++;
@@ -543,7 +551,7 @@ static int do_for_each_ref_in_dirs(struct ref_dir *dir1,
 			}
 			if (entry->flag & REF_DIR) {
 				retval = do_for_each_ref_in_dir(
-						&entry->u.subdir, 0,
+						entry, 0,
 						base, fn, trim, flags, cb_data);
 			} else {
 				retval = do_one_ref(base, fn, trim, flags, cb_data, entry);
@@ -605,7 +613,7 @@ static int is_refname_available(const char *refname, const char *oldrefname,
 
 	assert(direntry->flag & REF_DIR);
 
-	if (do_for_each_ref_in_dir(&direntry->u.subdir, 0, "", name_conflict_fn,
+	if (do_for_each_ref_in_dir(direntry, 0, "", name_conflict_fn,
 				   0, DO_FOR_EACH_INCLUDE_BROKEN,
 				   &data)) {
 		error("'%s' exists; cannot create '%s'",
@@ -1196,21 +1204,20 @@ static int do_for_each_ref(const char *submodule, const char *base, each_ref_fn
 
 	if (extra_direntry)
 		retval = do_for_each_ref_in_dir(
-				&extra_direntry->u.subdir, 0,
+				extra_direntry, 0,
 				base, fn, trim, flags, cb_data);
 	if (!retval) {
 		if (packed_direntry && loose_direntry)
 			retval = do_for_each_ref_in_dirs(
-					&packed_direntry->u.subdir,
-					&loose_direntry->u.subdir,
+					packed_direntry, loose_direntry,
 					base, fn, trim, flags, cb_data);
 		else if (packed_direntry)
 			retval = do_for_each_ref_in_dir(
-					&packed_direntry->u.subdir, 0,
+					packed_direntry, 0,
 					base, fn, trim, flags, cb_data);
 		else if (loose_direntry)
 			retval = do_for_each_ref_in_dir(
-					&loose_direntry->u.subdir, 0,
+					loose_direntry, 0,
 					base, fn, trim, flags, cb_data);
 	}
 
@@ -1668,8 +1675,7 @@ static int repack_without_ref(const char *refname)
 		unable_to_lock_error(git_path("packed-refs"), errno);
 		return error("cannot delete '%s' from packed refs", refname);
 	}
-	do_for_each_ref_in_dir(&packed->u.subdir, 0,
-			       "", repack_without_ref_fn, 0, 0, &data);
+	do_for_each_ref_in_dir(packed, 0, "", repack_without_ref_fn, 0, 0, &data);
 	return commit_lock_file(&packlock);
 }
 
-- 
1.7.7

[PATCH 22/28] sort_ref_dir(): take (ref_entry *) instead of (ref_dir *)

[mhagger]

From: Michael Haggerty <mhagger@alum.mit.edu>


Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs.c |   16 +++++++++-------
 1 files changed, 9 insertions(+), 7 deletions(-)

diff --git a/refs.c b/refs.c
index c3ee93d..98c8569 100644
--- a/refs.c
+++ b/refs.c
@@ -285,7 +285,7 @@ static int ref_entry_cmp(const void *a, const void *b)
 	return strcmp(one->name, two->name);
 }
 
-static void sort_ref_dir(struct ref_dir *dir);
+static void sort_ref_dir(struct ref_entry *direntry);
 
 /*
  * Return the entry with the given refname from the ref_dir
@@ -313,7 +313,7 @@ static struct ref_entry *search_ref_dir(struct ref_entry *direntry, const char *
 	 * references one after the other to a single subdirectory
 	 * doesn't require *any* intermediate sorting.
 	 */
-	sort_ref_dir(dir);
+	sort_ref_dir(direntry);
 
 	len = strlen(refname) + 1;
 	e = xmalloc(sizeof(struct ref_entry) + len);
@@ -424,11 +424,13 @@ static int is_dup_ref(const struct ref_entry *ref1, const struct ref_entry *ref2
  * Sort the entries in dir (if they are not already sorted).  Sort
  * only dir itself, not its subdirectories.
  */
-static void sort_ref_dir(struct ref_dir *dir)
+static void sort_ref_dir(struct ref_entry *direntry)
 {
 	int i, j;
 	struct ref_entry *last = NULL;
-
+	struct ref_dir *dir;
+	assert(direntry->flag & REF_DIR);
+	dir = &direntry->u.subdir;
 	if (dir->sorted == dir->nr)
 		return; /* This directory is already sorted and de-duped */
 
@@ -479,7 +481,7 @@ static int do_for_each_ref_in_dir(struct ref_entry *direntry, int offset,
 	struct ref_dir *dir;
 	assert(direntry->flag & REF_DIR);
 	dir = &direntry->u.subdir;
-	sort_ref_dir(dir);
+	sort_ref_dir(direntry);
 	for (i = offset; i < dir->nr; i++) {
 		struct ref_entry *entry = dir->entries[i];
 		int retval;
@@ -508,8 +510,8 @@ static int do_for_each_ref_in_dirs(struct ref_entry *direntry1,
 	assert(direntry2->flag & REF_DIR);
 	dir1 = &direntry1->u.subdir;
 	dir2 = &direntry2->u.subdir;
-	sort_ref_dir(dir1);
-	sort_ref_dir(dir2);
+	sort_ref_dir(direntry1);
+	sort_ref_dir(direntry2);
 	while (1) {
 		struct ref_entry *e1, *e2, *entry;
 		int cmp;
-- 
1.7.7

[PATCH 23/28] struct ref_dir: store a reference to the enclosing ref_cache

[mhagger]

From: Michael Haggerty <mhagger@alum.mit.edu>

This means that it contains enough information to serve as the sole
argument to get_ref_dir(), which will be changed in the next commit.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs.c |   21 ++++++++++++++++-----
 1 files changed, 16 insertions(+), 5 deletions(-)

diff --git a/refs.c b/refs.c
index 98c8569..6b2b2f6 100644
--- a/refs.c
+++ b/refs.c
@@ -143,6 +143,8 @@ struct ref_value {
 	unsigned char peeled[20];
 };
 
+struct ref_cache;
+
 struct ref_dir {
 	int nr, alloc;
 
@@ -150,6 +152,12 @@ struct ref_dir {
 	int sorted;
 
 	struct ref_entry **entries;
+
+	/*
+	 * A pointer to the ref_cache that contains this ref_dir, or
+	 * NULL if this ref_dir is used for extra_refs.
+	 */
+	struct ref_cache *ref_cache;
 };
 
 /* ISSYMREF=0x01, ISPACKED=0x02, and ISBROKEN=0x04 are public interfaces */
@@ -261,7 +269,8 @@ static void clear_ref_dir(struct ref_dir *dir)
  * dirname is the name of the directory with a trailing slash (e.g.,
  * "refs/heads/") or "" for the top-level directory.
  */
-static struct ref_entry *create_dir_entry(const char *dirname)
+static struct ref_entry *create_dir_entry(struct ref_cache *ref_cache,
+					  const char *dirname)
 {
 	struct ref_entry *direntry;
 	if (*dirname) {
@@ -275,6 +284,7 @@ static struct ref_entry *create_dir_entry(const char *dirname)
 		direntry->name[0] = '\0';
 	}
 	direntry->flag = REF_DIR;
+	direntry->u.subdir.ref_cache = ref_cache;
 	return direntry;
 }
 
@@ -354,7 +364,8 @@ static struct ref_entry *find_containing_direntry(struct ref_entry *direntry,
 				direntry = NULL;
 				break;
 			}
-			entry = create_dir_entry(refname_copy);
+			entry = create_dir_entry(direntry->u.subdir.ref_cache,
+						 refname_copy);
 			add_entry(direntry, entry);
 		}
 		slash[1] = tmp;
@@ -771,7 +782,7 @@ static void read_packed_refs(FILE *f, struct ref_entry *direntry)
 void add_extra_ref(const char *refname, const unsigned char *sha1, int flag)
 {
 	if (!extra_refs)
-		extra_refs = create_dir_entry("");
+		extra_refs = create_dir_entry(NULL, "");
 	add_ref(extra_refs, create_ref_entry(refname, sha1, flag));
 }
 
@@ -789,7 +800,7 @@ static struct ref_entry *get_packed_refs(struct ref_cache *refs)
 		const char *packed_refs_file;
 		FILE *f;
 
-		refs->packed = create_dir_entry("");
+		refs->packed = create_dir_entry(refs, "");
 		if (*refs->name)
 			packed_refs_file = git_path_submodule(refs->name, "packed-refs");
 		else
@@ -881,7 +892,7 @@ static void get_ref_dir(struct ref_cache *refs, const char *dirname)
 static struct ref_entry *get_loose_refs(struct ref_cache *refs)
 {
 	if (!refs->loose) {
-		refs->loose = create_dir_entry("");
+		refs->loose = create_dir_entry(refs, "");
 		get_ref_dir(refs, "refs/");
 	}
 	return refs->loose;
-- 
1.7.7

[PATCH 24/28] read_loose_refs(): take a (ref_entry *) as argument

[mhagger]

From: Michael Haggerty <mhagger@alum.mit.edu>

Rename get_ref_dir() to read_loose_refs(), and change its signature.
This is another step towards reading loose references one directory
at a time.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs.c |   21 +++++++++++----------
 1 files changed, 11 insertions(+), 10 deletions(-)

diff --git a/refs.c b/refs.c
index 6b2b2f6..f3910de 100644
--- a/refs.c
+++ b/refs.c
@@ -815,21 +815,20 @@ static struct ref_entry *get_packed_refs(struct ref_cache *refs)
 }
 
 /*
- * dirname must match the name associated with dir; in particular, it
- * must end with '/'.
+ * Fill direntry with loose references read from the filesystem.
  */
-static void get_ref_dir(struct ref_cache *refs, const char *dirname)
+static void read_loose_refs(struct ref_entry *direntry)
 {
 	DIR *d;
 	char *path;
+	char *dirname = direntry->name;
 	int dirnamelen = strlen(dirname);
 	int pathlen;
-	struct ref_entry *direntry;
-
-	assert(dirnamelen && dirname[dirnamelen - 1] == '/');
-
-	direntry = find_containing_direntry(refs->loose, dirname, 1);
+	struct ref_cache *refs;
 
+	assert(direntry->flag & REF_DIR);
+	assert(dirnamelen && direntry->name[dirnamelen - 1] == '/');
+	refs = direntry->u.subdir.ref_cache;
 	if (*refs->name)
 		path = git_path_submodule(refs->name, "%s", dirname);
 	else
@@ -867,7 +866,9 @@ static void get_ref_dir(struct ref_cache *refs, const char *dirname)
 			if (S_ISDIR(st.st_mode)) {
 				refname[dirnamelen + namelen] = '/';
 				refname[dirnamelen + namelen + 1] = '\0';
-				get_ref_dir(refs, refname);
+				read_loose_refs(find_containing_direntry(
+								refs->loose,
+								refname, 1));
 				continue;
 			}
 			if (*refs->name) {
@@ -893,7 +894,7 @@ static struct ref_entry *get_loose_refs(struct ref_cache *refs)
 {
 	if (!refs->loose) {
 		refs->loose = create_dir_entry(refs, "");
-		get_ref_dir(refs, "refs/");
+		read_loose_refs(find_containing_direntry(refs->loose, "refs/", 1));
 	}
 	return refs->loose;
 }
-- 
1.7.7

[PATCH 25/28] refs: read loose references lazily

[mhagger]

From: Michael Haggerty <mhagger@alum.mit.edu>

Instead of reading the whole directory of loose references the first
time any are needed, only read them on demand, one directory at a
time.

Use a new ref_entry flag value REF_DIR_INCOMPLETE to indicate that the
entry represents a REF_DIR that hasn't been read yet.  Whenever any
entries from such a directory are needed, read all of the loose
references from that directory.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs.c |  112 ++++++++++++++++++++++++++++++++++++++++++++++++++--------------
 1 files changed, 88 insertions(+), 24 deletions(-)

diff --git a/refs.c b/refs.c
index f3910de..88ef9dd 100644
--- a/refs.c
+++ b/refs.c
@@ -138,6 +138,12 @@ int check_refname_format(const char *refname, int flags)
 
 struct ref_entry;
 
+/*
+ * Information used (along with the information in ref_entry) to
+ * describe a single cached reference.  This data structure only
+ * occurs embedded in a union in struct ref_entry, and only when
+ * (ref_entry->flag & REF_DIR) is zero.
+ */
 struct ref_value {
 	unsigned char sha1[20];
 	unsigned char peeled[20];
@@ -145,6 +151,34 @@ struct ref_value {
 
 struct ref_cache;
 
+/*
+ * Information used (along with the information in ref_entry) to
+ * describe a level in the hierarchy of references.  This data
+ * structure only occurs embedded in a union in struct ref_entry, and
+ * only when (ref_entry.flag & REF_DIR) is nonzero.  In that case,
+ * (ref_entry.flag & REF_DIR) can take the following values:
+ *
+ *     REF_DIR_COMPLETE -- a directory of loose or packed references,
+ *         already read.
+ *
+ *     REF_DIR_INCOMPLETE -- a directory of loose references that
+ *         hasn't been read yet (nor has any of its subdirectories).
+ *
+ * Entries within a directory are stored within a growable array of
+ * pointers to ref_entries (entries, nr, alloc).  Entries 0 <= i <
+ * sorted are sorted by their component name in strcmp() order and the
+ * remaining entries are unsorted.
+ *
+ * Loose references are read lazily, one directory at a time.  When a
+ * directory of loose references is read, then all of the references
+ * in that directory are stored, and REF_DIR_INCOMPLETE stubs are
+ * created for any subdirectories, but the subdirectories themselves
+ * are not read.  The reading is triggered either by search_ref_dir()
+ * (called when single references are added or interrogated), by
+ * sort_ref_dir(), or by iteration over a subdirectory of references
+ * using one of the for_each_ref*() functions (which calls
+ * sort_ref_dir() for each subdirectory).
+ */
 struct ref_dir {
 	int nr, alloc;
 
@@ -162,19 +196,33 @@ struct ref_dir {
 
 /* ISSYMREF=0x01, ISPACKED=0x02, and ISBROKEN=0x04 are public interfaces */
 #define REF_KNOWS_PEELED 0x08
-#define REF_DIR 0x10
+
+/* If any of these bits are set, the entry represents a directory: */
+#define REF_DIR 0x30
+
+/* A directory that has already been fully read. */
+#define REF_DIR_COMPLETE 0x10
+
+/* A directory of loose references that has not yet been fully read. */
+#define REF_DIR_INCOMPLETE 0x20
 
 /*
  * A ref_entry represents either a reference or a "subdirectory" of
- * references.  Each directory in the reference namespace is
- * represented by a ref_entry with (flags & REF_DIR) set and
- * containing a subdir member that holds the entries in that
- * directory.  References are represented by a ref_entry with (flags &
- * REF_DIR) unset and a value member that describes the reference's
- * value.  The flag member is at the ref_entry level, but it is also
- * needed to interpret the contents of the value field (in other
- * words, a ref_value object is not very much use without the
- * enclosing ref_entry).
+ * references.
+ *
+ * Each directory in the reference namespace is represented by a
+ * ref_entry with (flags & REF_DIR) set and containing a subdir member
+ * that holds the entries in that directory that have been read so
+ * far.  If (flags & REF_DIR) == REF_DIR_INCOMPLETE, then the
+ * directory and its subdirectories haven't been read yet.
+ * REF_DIR_INCOMPLETE is only used for loose references.
+ *
+ * References are represented by a ref_entry with (flags & REF_DIR) ==
+ * 0 and a value member that describes the reference's value.  The
+ * flag member is at the ref_entry level, but it is also needed to
+ * interpret the contents of the value field (in other words, a
+ * ref_value object is not very much use without the enclosing
+ * ref_entry).
  *
  * Reference names cannot end with slash and directories' names are
  * always stored with a trailing slash (except for the top-level
@@ -264,13 +312,15 @@ static void clear_ref_dir(struct ref_dir *dir)
 	dir->entries = NULL;
 }
 
+static void read_loose_refs(struct ref_entry *direntry);
+
 /*
  * Create a struct ref_entry object for the specified dirname.
  * dirname is the name of the directory with a trailing slash (e.g.,
  * "refs/heads/") or "" for the top-level directory.
  */
 static struct ref_entry *create_dir_entry(struct ref_cache *ref_cache,
-					  const char *dirname)
+					  const char *dirname, int flag)
 {
 	struct ref_entry *direntry;
 	if (*dirname) {
@@ -283,7 +333,7 @@ static struct ref_entry *create_dir_entry(struct ref_cache *ref_cache,
 		direntry = xcalloc(1, sizeof(struct ref_entry) + 1);
 		direntry->name[0] = '\0';
 	}
-	direntry->flag = REF_DIR;
+	direntry->flag = flag;
 	direntry->u.subdir.ref_cache = ref_cache;
 	return direntry;
 }
@@ -308,6 +358,7 @@ static struct ref_entry *search_ref_dir(struct ref_entry *direntry, const char *
 	struct ref_dir *dir;
 
 	assert(direntry->flag & REF_DIR);
+	read_loose_refs(direntry);
 	dir = &direntry->u.subdir;
 	if (refname == NULL || !dir->nr)
 		return NULL;
@@ -364,8 +415,14 @@ static struct ref_entry *find_containing_direntry(struct ref_entry *direntry,
 				direntry = NULL;
 				break;
 			}
+			/*
+			 * If search_ref_dir() above didn't make the
+			 * entry spring into existence, then this must
+			 * not be an unread loose reference tree, so
+			 * the correct flag is REF_DIR_COMPLETE.
+			 */
 			entry = create_dir_entry(direntry->u.subdir.ref_cache,
-						 refname_copy);
+						 refname_copy, REF_DIR_COMPLETE);
 			add_entry(direntry, entry);
 		}
 		slash[1] = tmp;
@@ -441,6 +498,7 @@ static void sort_ref_dir(struct ref_entry *direntry)
 	struct ref_entry *last = NULL;
 	struct ref_dir *dir;
 	assert(direntry->flag & REF_DIR);
+	read_loose_refs(direntry);
 	dir = &direntry->u.subdir;
 	if (dir->sorted == dir->nr)
 		return; /* This directory is already sorted and de-duped */
@@ -491,8 +549,8 @@ static int do_for_each_ref_in_dir(struct ref_entry *direntry, int offset,
 	int i;
 	struct ref_dir *dir;
 	assert(direntry->flag & REF_DIR);
-	dir = &direntry->u.subdir;
 	sort_ref_dir(direntry);
+	dir = &direntry->u.subdir;
 	for (i = offset; i < dir->nr; i++) {
 		struct ref_entry *entry = dir->entries[i];
 		int retval;
@@ -519,10 +577,10 @@ static int do_for_each_ref_in_dirs(struct ref_entry *direntry1,
 
 	assert(direntry1->flag & REF_DIR);
 	assert(direntry2->flag & REF_DIR);
-	dir1 = &direntry1->u.subdir;
-	dir2 = &direntry2->u.subdir;
 	sort_ref_dir(direntry1);
 	sort_ref_dir(direntry2);
+	dir1 = &direntry1->u.subdir;
+	dir2 = &direntry2->u.subdir;
 	while (1) {
 		struct ref_entry *e1, *e2, *entry;
 		int cmp;
@@ -782,7 +840,7 @@ static void read_packed_refs(FILE *f, struct ref_entry *direntry)
 void add_extra_ref(const char *refname, const unsigned char *sha1, int flag)
 {
 	if (!extra_refs)
-		extra_refs = create_dir_entry(NULL, "");
+		extra_refs = create_dir_entry(NULL, "", REF_DIR_COMPLETE);
 	add_ref(extra_refs, create_ref_entry(refname, sha1, flag));
 }
 
@@ -800,7 +858,7 @@ static struct ref_entry *get_packed_refs(struct ref_cache *refs)
 		const char *packed_refs_file;
 		FILE *f;
 
-		refs->packed = create_dir_entry(refs, "");
+		refs->packed = create_dir_entry(refs, "", REF_DIR_COMPLETE);
 		if (*refs->name)
 			packed_refs_file = git_path_submodule(refs->name, "packed-refs");
 		else
@@ -822,11 +880,14 @@ static void read_loose_refs(struct ref_entry *direntry)
 	DIR *d;
 	char *path;
 	char *dirname = direntry->name;
-	int dirnamelen = strlen(dirname);
+	int dirnamelen;
 	int pathlen;
 	struct ref_cache *refs;
 
 	assert(direntry->flag & REF_DIR);
+	if ((direntry->flag & REF_DIR) != REF_DIR_INCOMPLETE)
+		return;
+	dirnamelen = strlen(dirname);
 	assert(dirnamelen && direntry->name[dirnamelen - 1] == '/');
 	refs = direntry->u.subdir.ref_cache;
 	if (*refs->name)
@@ -864,11 +925,12 @@ static void read_loose_refs(struct ref_entry *direntry)
 			if (stat(refdir, &st) < 0)
 				continue;
 			if (S_ISDIR(st.st_mode)) {
+				struct ref_entry *subdirentry;
 				refname[dirnamelen + namelen] = '/';
 				refname[dirnamelen + namelen + 1] = '\0';
-				read_loose_refs(find_containing_direntry(
-								refs->loose,
-								refname, 1));
+				subdirentry = create_dir_entry(direntry->u.subdir.ref_cache,
+							       refname, REF_DIR_INCOMPLETE);
+				add_entry(direntry, subdirentry);
 				continue;
 			}
 			if (*refs->name) {
@@ -888,13 +950,15 @@ static void read_loose_refs(struct ref_entry *direntry)
 		free(refname);
 		closedir(d);
 	}
+	direntry->flag = REF_DIR_COMPLETE;
 }
 
 static struct ref_entry *get_loose_refs(struct ref_cache *refs)
 {
 	if (!refs->loose) {
-		refs->loose = create_dir_entry(refs, "");
-		read_loose_refs(find_containing_direntry(refs->loose, "refs/", 1));
+		refs->loose = create_dir_entry(refs, "", REF_DIR_COMPLETE);
+		add_entry(refs->loose,
+			  create_dir_entry(refs, "refs/", REF_DIR_INCOMPLETE));
 	}
 	return refs->loose;
 }
-- 
1.7.7

[PATCH 26/28] is_refname_available(): query only possibly-conflicting references

[mhagger]

From: Michael Haggerty <mhagger@alum.mit.edu>

Instead of iterating through all of the references, inquire more
pointedly about the references that could conflict with the new name.
This requires checking for a few individual references, plus iterating
through a small subtree of the rest of the references (and usually the
subtree iteration ends without having to recurse).  A big benefit is
that populating the whole loose reference cache (which can be very
expensive) can usually be avoided.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs.c |   40 +++++++++++++++++++++++++++++++++-------
 1 files changed, 33 insertions(+), 7 deletions(-)

diff --git a/refs.c b/refs.c
index 88ef9dd..6a7f9c3 100644
--- a/refs.c
+++ b/refs.c
@@ -658,7 +658,7 @@ static int name_conflict_fn(const char *existingrefname, const unsigned char *sh
 			    int flags, void *cb_data)
 {
 	struct name_conflict_cb *data = (struct name_conflict_cb *)cb_data;
-	if (data->oldrefname && !strcmp(data->oldrefname, existingrefname))
+	if (!strcmp(data->oldrefname, existingrefname))
 		return 0;
 	if (names_conflict(data->refname, existingrefname)) {
 		data->conflicting_refname = existingrefname;
@@ -669,22 +669,48 @@ static int name_conflict_fn(const char *existingrefname, const unsigned char *sh
 
 /*
  * Return true iff a reference named refname could be created without
- * conflicting with the name of an existing reference.  If oldrefname
- * is non-NULL, ignore potential conflicts with oldrefname (e.g.,
- * because oldrefname is scheduled for deletion in the same
+ * conflicting with the name of an existing reference in direntry.  If
+ * oldrefname is non-NULL, ignore potential conflicts with oldrefname
+ * (e.g., because oldrefname is scheduled for deletion in the same
  * operation).
  */
 static int is_refname_available(const char *refname, const char *oldrefname,
 				struct ref_entry *direntry)
 {
+	int prefixlen = strlen(refname);
+	char *prefix;
+	char *slash;
 	struct name_conflict_cb data;
+
+	assert(direntry->flag & REF_DIR);
+
+	if (!oldrefname)
+		oldrefname = ""; /* invalid; cannot match any existing refname */
+
+	/* Check whether a prefix of refname is an existing reference: */
+	prefix = xmalloc(prefixlen + 2);
+	memcpy(prefix, refname, prefixlen + 1);
+	for (slash = strchr(prefix, '/'); slash; slash = strchr(slash + 1, '/')) {
+		*slash = '\0';
+		if (strcmp(oldrefname, prefix)) {
+			struct ref_entry *entry = find_ref(direntry, prefix);
+			if (entry) {
+				error("'%s' exists; cannot create '%s'", prefix, refname);
+				free(prefix);
+				return 0;
+			}
+		}
+		*slash = '/';
+	}
+
+	/* Check whether refname is a proper prefix of an existing reference: */
+	prefix[prefixlen++] = '/';
+	prefix[prefixlen] = '\0';
 	data.refname = refname;
 	data.oldrefname = oldrefname;
 	data.conflicting_refname = NULL;
 
-	assert(direntry->flag & REF_DIR);
-
-	if (do_for_each_ref_in_dir(direntry, 0, "", name_conflict_fn,
+	if (do_for_each_ref_in_dir(direntry, 0, prefix, name_conflict_fn,
 				   0, DO_FOR_EACH_INCLUDE_BROKEN,
 				   &data)) {
 		error("'%s' exists; cannot create '%s'",
-- 
1.7.7

[PATCH 27/28] read_packed_refs(): keep track of the directory being worked in

[mhagger]

From: Michael Haggerty <mhagger@alum.mit.edu>

Packed references are stored in $GIT_DIR/packed-refs sorted, so
adjacent ones are pretty likely to be in the same directory.  So while
reading them, keep track of the last directory used, and reuse it if
possible to avoid searching the reference namespace from the root each
time.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs.c |   16 +++++++++++++++-
 1 files changed, 15 insertions(+), 1 deletions(-)

diff --git a/refs.c b/refs.c
index 6a7f9c3..6a19d19 100644
--- a/refs.c
+++ b/refs.c
@@ -831,6 +831,7 @@ static const char *parse_ref_line(char *line, unsigned char *sha1)
 static void read_packed_refs(FILE *f, struct ref_entry *direntry)
 {
 	struct ref_entry *last = NULL;
+	struct ref_entry *current_direntry = NULL;
 	char refline[PATH_MAX];
 	int flag = REF_ISPACKED;
 
@@ -850,8 +851,21 @@ static void read_packed_refs(FILE *f, struct ref_entry *direntry)
 
 		refname = parse_ref_line(refline, sha1);
 		if (refname) {
+			if (current_direntry) {
+				char *slash = strrchr(refname, '/');
+				if (!slash
+				    || strncmp(current_direntry->name, refname,
+					       slash - refname + 1)
+				    || current_direntry->name[slash - refname + 1] != '\0')
+					/* The new refname does not go in current_direntry */
+					current_direntry = NULL;
+			}
+			if (!current_direntry)
+				current_direntry = find_containing_direntry(
+						direntry, refname, 1);
+
 			last = create_ref_entry(refname, sha1, flag);
-			add_ref(direntry, last);
+			add_entry(current_direntry, last);
 			continue;
 		}
 		if (last &&
-- 
1.7.7

[PATCH 28/28] repack_without_ref(): call clear_packed_ref_cache()

[mhagger]

From: Michael Haggerty <mhagger@alum.mit.edu>

Call clear_packed_ref_cache() from repack_without_ref().  This is a
more logical place to call it than from delete_ref().  Also,
repack_without_ref() is smart enough to know that it doesn't have to
invalidate the cache if the reference was not found among the packed
refs.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs.c |    7 +++++--
 1 files changed, 5 insertions(+), 2 deletions(-)

diff --git a/refs.c b/refs.c
index 6a19d19..bbf9e3e 100644
--- a/refs.c
+++ b/refs.c
@@ -1784,7 +1784,9 @@ static struct lock_file packlock;
 static int repack_without_ref(const char *refname)
 {
 	struct repack_without_ref_sb data;
-	struct ref_entry *packed = get_packed_refs(get_ref_cache(NULL));
+	struct ref_cache *refs = get_ref_cache(NULL);
+	struct ref_entry *packed = get_packed_refs(refs);
+
 	if (find_ref(packed, refname) == NULL)
 		return 0;
 	data.refname = refname;
@@ -1794,6 +1796,7 @@ static int repack_without_ref(const char *refname)
 		return error("cannot delete '%s' from packed refs", refname);
 	}
 	do_for_each_ref_in_dir(packed, 0, "", repack_without_ref_fn, 0, 0, &data);
+	clear_packed_ref_cache(refs);
 	return commit_lock_file(&packlock);
 }
 
@@ -1822,6 +1825,7 @@ int delete_ref(const char *refname, const unsigned char *sha1, int delopt)
 
 		if (!(delopt & REF_NODEREF))
 			lock->lk->filename[i] = '.';
+		clear_loose_ref_cache(get_ref_cache(NULL));
 	}
 	/* removing the loose one could have resurrected an earlier
 	 * packed one.  Also, if it was not loose we need to repack
@@ -1830,7 +1834,6 @@ int delete_ref(const char *refname, const unsigned char *sha1, int delopt)
 	ret |= repack_without_ref(refname);
 
 	unlink_or_warn(git_path("logs/%s", lock->ref_name));
-	invalidate_ref_cache(NULL);
 	unlock_ref(lock);
 	return ret;
 }
-- 
1.7.7

Re: [PATCH 00/28] Store references hierarchically in cache

[Ramkumar Ramachandra]

Hi Michael,

Michael Haggerty writes:
> Therefore, this patch series changes the data structure used to store
> the reference cache from a single array of pointers-to-struct into a
> tree-like structure in which each subdirectory of the reference
> namespace is stored as an array of pointers-to-entry and entries can
> be either references or subdirectories containing more references.

Very nice! I like the idea. Can't wait to start reading the series.

>  * refs/replace is almost *always* needed even though it often
>    doesn't even exist.  Thus the presence of many loose references
>    slows down *many* git commands for no reason whatsoever.

Was this one of your primary inspirations for writing this series?

>  * When a new reference is created, is_refname_available() is called
>    to see whether there is another another reference whose name
>    conflicts with the new one.  Currently this loads and iterates
>    through *all* references.  But there are only a few refnames that
>    can possibly conflict; for example, given the refname
>    "refs/heads/foo/bar", the only possible conflicts are with
>    "refs/heads/foo" and "refs/heads/foo/bar/*".  Therefore it is
>    silly to load and iterate through the whole refname hierarchy.

Hm, the original design does sound quite sub-optimal.  I suppose it
was written when Git didn't have so many refs in so many
subdirectories.

>  * "git for-each-ref" is capable of searching a subtree of the
>    references.  But currently this causes all references to be
>    loaded.

Ah.  I was using git for-each-ref to write a filter-branch like thing
earlier, and I was wondering why it was so slow.

> * the time to create a new branch goes from 180 ms to less than 10 ms
>  (my test resolution only includes two decimal places) and the time
>  to checkout a new branch does the same.

I'm interested in seeing how the callgraph changed.  Assuming you used
Valgrind to profile it, could you publish the outputs?

> * the time for a "git filter-branch" of all commits (which used to
>  scale like N^2) goes from 4 hours to 13 minutes.  (Since
>  filter-branch necessarily *creates* lots of loose references, the
>  savings are also there if the references are originally packed.)

This is seriously awesome.

> The efficiency gains are such that some operations are now faster with
> loose references than with packed references; however, some operations
> with packed references slow down a bit.

Curiously, why do operations with packed references slow down?  (I'll
probably find out in a few minutes after reading the series, but I'm
asking anyway because it it's very non-obvious to me now)

> These changes do not increase the amount of space per reference needed
> for the reference cache, but they do add one similarly-sized entry for
> each subdirectory (for each of loose and packed).  I don't think that
> the space increase should be significant in any reasonable situation.
>
> After these changes, there is a benefit to sharding the reference
> namespace, especially for loose references.

Hm, I wonder what this means for Git hosting services.

> Patches 11-24 change most of the internal functions to work with
> "struct ref_entry *" (namely the kind of ref_entry that holds a
> directory of references) instead of "struct ref_dir *".  The reason
> for this change it to allow these functions access to the "flag" and
> "name" fields that are stored in ref_entry and thereby avoid having to
> store redundant information in "struct ref_dir" (which would increase
> the size of *every* ref_entry because of its presence in the union).

Hm, I was wondering why the series was looking so intimidating.  Is it
not possible to squash all (or atleast some) of these together?

> From: Michael Haggerty <mhagger@alum.mit.edu>

Nit: Can't you configure your email client to put this in the "From: "
header of your emails?

Thanks for the interesting read.

-- Ram

Re: [PATCH 00/28] Store references hierarchically in cache

[Michael Haggerty]

On 10/28/2011 03:07 PM, Ramkumar Ramachandra wrote:
> Michael Haggerty writes:
>> Therefore, this patch series changes the data structure used to store
>> the reference cache from a single array of pointers-to-struct into a
>> tree-like structure in which each subdirectory of the reference
>> namespace is stored as an array of pointers-to-entry and entries can
>> be either references or subdirectories containing more references.
> 
> Very nice! I like the idea. Can't wait to start reading the series.
> 
>>  * refs/replace is almost *always* needed even though it often
>>    doesn't even exist.  Thus the presence of many loose references
>>    slows down *many* git commands for no reason whatsoever.
> 
> Was this one of your primary inspirations for writing this series?

My primary inspiration was that "git filter-branch" was so slow, which
is partly because of the refs/replace thing and partly just the built-in
inefficiency of the old reference cache.

>> * the time to create a new branch goes from 180 ms to less than 10 ms
>>  (my test resolution only includes two decimal places) and the time
>>  to checkout a new branch does the same.
> 
> I'm interested in seeing how the callgraph changed.  Assuming you used
> Valgrind to profile it, could you publish the outputs?

I didn't use valgrind; I just timed commands using time(1).

>> The efficiency gains are such that some operations are now faster with
>> loose references than with packed references; however, some operations
>> with packed references slow down a bit.
> 
> Curiously, why do operations with packed references slow down?  (I'll
> probably find out in a few minutes after reading the series, but I'm
> asking anyway because it it's very non-obvious to me now)

I think it's just because the new data structure is slightly slower than
the old one for the task of appending thousands of refs without doing
any searching or sorting.  Since packed refs are read all-or-nothing
(even after my changes), there is no way to read the packed refs only
for the directory that you are interested in.

>> Patches 11-24 change most of the internal functions to work with
>> "struct ref_entry *" (namely the kind of ref_entry that holds a
>> directory of references) instead of "struct ref_dir *".  The reason
>> for this change it to allow these functions access to the "flag" and
>> "name" fields that are stored in ref_entry and thereby avoid having to
>> store redundant information in "struct ref_dir" (which would increase
>> the size of *every* ref_entry because of its presence in the union).
> 
> Hm, I was wondering why the series was looking so intimidating.  Is it
> not possible to squash all (or atleast some) of these together?

Why would I possibly want to squash them together?  Each one is
self-contained and logically separate from the rest.  After each commit
the code compiles and works.  Squashing them together wouldn't increase
the cognitive burden of reading them; on the contrary, it would make it
harder to read them because several logically-separate changes would be
confounded into a single patch.  Most of these patches have only a few
nontrivial lines which you can read at a glance.  And if the series ever
has to be bisected, the error can be narrowed down to a very small diff.

>> From: Michael Haggerty <mhagger@alum.mit.edu>
> 
> Nit: Can't you configure your email client to put this in the "From: "
> header of your emails?

I'm not sure where those extra lines come from.  My email client is
git-send-email.  I just checked, and they have appeared in patch series
sent through two completely different SMTP servers, so it seems unlikely
that the SMTP server is guilty.  I'll see if I can figure it out.

> Thanks for the interesting read.

Thanks for reading :-)

Michael

-- 
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/

[PATCH] Fix "is_refname_available(): query only possibly-conflicting references"

[mhagger]

From: Michael Haggerty <mhagger@alum.mit.edu>

The above-named commit didn't do all that its commit message claimed.
The problem is that do_for_each_ref_in_dir() doesn't avoid iterating
through reference subtrees outside of "prefix"; it only skips passing
those references to the callback function.  So the function
unnecessarily caused all loose references to be loaded rather than
just those in the required subtree.

So instead, explicitly select the possibly-conflicting subtree and
pass it to do_for_each_ref_in_dir().

Also, simplify name_conflict_fn().  Since it will only be called for
possibly-conflicting references, there is necessarily a conflict if it
is called for *any* reference besides "oldrefname".

Remove function names_conflict(), which is now unused.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---

This patch can be squashed on top of "is_refname_available(): query
only possibly-conflicting references", or applied at the end of
mh/ref-api-take-2; it does not conflict with the two commits later in
the series.

 refs.c |   40 +++++++++++++++++-----------------------
 1 files changed, 17 insertions(+), 23 deletions(-)

diff --git a/refs.c b/refs.c
index 6a7f9c3..b185c32 100644
--- a/refs.c
+++ b/refs.c
@@ -633,23 +633,7 @@ static int do_for_each_ref_in_dirs(struct ref_entry *direntry1,
 	}
 }
 
-/*
- * Return true iff refname1 and refname2 conflict with each other.
- * Two reference names conflict if one of them exactly matches the
- * leading components of the other; e.g., "foo/bar" conflicts with
- * both "foo" and with "foo/bar/baz" but not with "foo/bar" or
- * "foo/barbados".
- */
-static int names_conflict(const char *refname1, const char *refname2)
-{
-	for (; *refname1 && *refname1 == *refname2; refname1++, refname2++)
-		;
-	return (*refname1 == '\0' && *refname2 == '/')
-		|| (*refname1 == '/' && *refname2 == '\0');
-}
-
 struct name_conflict_cb {
-	const char *refname;
 	const char *oldrefname;
 	const char *conflicting_refname;
 };
@@ -660,11 +644,13 @@ static int name_conflict_fn(const char *existingrefname, const unsigned char *sh
 	struct name_conflict_cb *data = (struct name_conflict_cb *)cb_data;
 	if (!strcmp(data->oldrefname, existingrefname))
 		return 0;
-	if (names_conflict(data->refname, existingrefname)) {
-		data->conflicting_refname = existingrefname;
-		return 1;
-	}
-	return 0;
+
+	/*
+	 * Since we are only iterating over the subtree that has the
+	 * new refname as prefix, *any* reference found is a conflict.
+	 */
+	data->conflicting_refname = existingrefname;
+	return 1;
 }
 
 /*
@@ -673,6 +659,11 @@ static int name_conflict_fn(const char *existingrefname, const unsigned char *sh
  * oldrefname is non-NULL, ignore potential conflicts with oldrefname
  * (e.g., because oldrefname is scheduled for deletion in the same
  * operation).
+ *
+ * Two reference names conflict if one of them exactly matches the
+ * leading components of the other; e.g., "foo/bar" conflicts with
+ * both "foo" and with "foo/bar/baz" but not with "foo/bar" or
+ * "foo/barbados".
  */
 static int is_refname_available(const char *refname, const char *oldrefname,
 				struct ref_entry *direntry)
@@ -706,11 +697,14 @@ static int is_refname_available(const char *refname, const char *oldrefname,
 	/* Check whether refname is a proper prefix of an existing reference: */
 	prefix[prefixlen++] = '/';
 	prefix[prefixlen] = '\0';
-	data.refname = refname;
 	data.oldrefname = oldrefname;
 	data.conflicting_refname = NULL;
 
-	if (do_for_each_ref_in_dir(direntry, 0, prefix, name_conflict_fn,
+	direntry = find_containing_direntry(direntry, prefix, 0);
+	if (!direntry)
+		return 1;
+
+	if (do_for_each_ref_in_dir(direntry, 0, "", name_conflict_fn,
 				   0, DO_FOR_EACH_INCLUDE_BROKEN,
 				   &data)) {
 		error("'%s' exists; cannot create '%s'",
-- 
1.7.7.2

Re: [PATCH] Fix "is_refname_available(): query only possibly-conflicting references"

[Junio C Hamano]

mhagger@alum.mit.edu writes:

> This patch can be squashed on top of "is_refname_available(): query
> only possibly-conflicting references", or applied at the end of
> mh/ref-api-take-2; it does not conflict with the two commits later in
> the series.

Thanks. At the microscopic level (i.e. in the context of the said series),
the patch makes sense to me.

However, I'd rather see us spend effort to make absolutely sure that other
topics already in next that touch the related codepaths (I think you have
two such series yourself and I suspect there are other minor fixes that
may textually conflict) are in good shape and have them graduate early
after 1.7.8 ships, before queuing a re-roll of the ref-api series, which
is rather extensive.

Re: [PATCH] Fix "is_refname_available(): query only possibly-conflicting references"

[Michael Haggerty]

On 11/15/2011 08:24 AM, Junio C Hamano wrote:
> However, I'd rather see us spend effort to make absolutely sure that other
> topics already in next that touch the related codepaths (I think you have
> two such series yourself and I suspect there are other minor fixes that
> may textually conflict) are in good shape and have them graduate early
> after 1.7.8 ships, before queuing a re-roll of the ref-api series, which
> is rather extensive.

If you have a preference for which patch series you would like to
integrate in which order (and especially if you think that there are
gaps that need to be filled), please let me know.  It would be a lot
less work to put them in the right order from the start rather than
trying to keep them all synchronized with master and continually reroll
them based on what you have merged so far.

Also, I am working under the assumption that the patch series that are
already in "next" should be left alone; if you have doubts about any of
those patch series (i.e., are thinking of ejecting them from next during
the post-release chaos), please let me know what needs changing.

I'm still getting the hang of this workflow, so suggestions are welcome.

Michael

-- 
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/

Re: [PATCH] Fix "is_refname_available(): query only possibly-conflicting references"

[Junio C Hamano]

Michael Haggerty <mhagger@alum.mit.edu> writes:

> If you have a preference for which patch series you would like to
> integrate in which order (and especially if you think that there are
> gaps that need to be filled), please let me know.  It would be a lot
> less work to put them in the right order from the start rather than
> trying to keep them all synchronized with master and continually reroll
> them based on what you have merged so far.

I've re-read mh/ref-api-[23] a few times myself during this feature-freeze
period and found that the checks they enforce seemed to be sensible for
newly created refs. But I do not know if there are widespread mispractices
of using "wrong" refnames, created by either older versions of Git and
common third-party ones, that may make existing repository unusable
without first correcting them, and more importantly, I do not know if the
updated code is lenient enough to give users necessary escape hatches to
correct the existing problems. As we recently found out on the 'master'
front for your earlier topic, an updated check that is more strict and
saner than the older one is not necessarily an improvement, if it causes
pain to existing users to adjust to the new world order.

The output frm "git log --oneline --first-parent master..pu" should give
rough idea of what I have in mind. Obvious and nonintrusive clean-ups come
early, then features that are shown to be needed in the field and are with
user-facing design that are perfected come next to give them longer time
to fix potential issues in implemementation, followed by all the rest.

Re: [PATCH 00/28] Store references hierarchically in cache -- benchmark results

[Michael Haggerty]

On 10/28/2011 02:28 PM, mhagger@alum.mit.edu wrote:
> [...]
> This patch series changes how references are stored in the reference
> cache data structures (entirely internal to refs.c).  Previously, the
> packed refs were stored in one big array of pointers-to-struct, and
> the loose refs were stored in another.  [...]
> 
> Therefore, this patch series changes the data structure used to store
> the reference cache from a single array of pointers-to-struct into a
> tree-like structure in which each subdirectory of the reference
> namespace is stored as an array of pointers-to-entry and entries can
> be either references or subdirectories containing more references.
> Moreover, each subdirectory of loose references is only read from disk
> when a reference from that subdirectory (or one of its descendants) is
> needed.  This slightly slows down commands that need to iterate
> through all references (simply because the new data structures are
> more complicated), but it *dramatically* decreases the time needed for
> some common operations.  For example, in a test repository with 20000
> revisions and 10000 loose tags:

Due to the death of my old computer, I got distracted and never
published the benchmark results that I cited above.  (The numbers here
are different than the originals because they are done on a different
computer.)  The benchmarks are done using code from [1]; the test
repository consists of a linear series of 20000 commits (with very
little content) and 10000 tags (on every second commit); the tags are
unsharded.  The numbers are times in seconds; "cold" means that the disk
cache was flushed immediately before the test; "warm" usually means that
the same operation was done a second time.

Column #0 is Git 1.7.7.2; column #1 is Git 1.7.8-rc2; column #2 is a
recent git master plus my ref-related patch series (what Junio calls
mh/ref-api-take-2 plus the fix that I posted yesterday).

The main change between 1.7.7.2 and 1.7.8 is that the latter stores the
reference cache in a sorted array rather than a linked list, meaning
that it is possible to use bisection to locate a reference quickly by
name rather than having to search linearly through a linked list.  This
greatly helps some operations when most references are packed and can be
read from disk quickly.  It doesn't make much difference when most
references are loose, because the time required to read the loose
references from disk overwhelms the time for iterating through the array
in memory.

The main improvements between 1.7.8 and the new version are when the old
code would have read all of the loose references but the new code only
needs to read a couple of directories of them.  Given that almost all of
the references in the test repository are tags, they often don't need to
be read at all when branches are being manipulated.  By contrast, many
old code paths force *all* of the references to be read, for example
when they check for replacements in refs/replace/.

I've done other benchmarks with varying numbers of references.  The
results suggest that many operations go from O(N) in the number of loose
references to O(1) (e.g., if all they do is check refs/replace/) or some
other slow scaling that depends on how the reference namespace is organized.

Anything involving packed references necessarily scales at least like
O(N) because packed references are all read at once.  OTOH reading
packed refs is so much faster than reading loose references that with
10000 references, packing is still advantageous.  (For some number of
references, of course, the curves must cross and loose references will
be more efficient than packed references for some operations.)

The case of git-filter-branch is particularly dramatic; the old code
scales like O(N^2) whereas the new code scales like O(N) as expected.
Moreover, git-filter-branch creates lots of loose references while it
works, so it is not possible to evade the problem by packing the
references before invoking git-filter-branch.  I believe that
git-filter-branch is mostly slowed down be each subcommand's check for
replacements in refs/replace (even though there are none in my test
repository) because in the old code this check forces *all* loose
references to be read.  Versions 1.7.7 and 1.7.8 of git-filter-branch
runs much faster if the --no-replace-objects option is used.

With these changes, it becomes thinkable to work with repositories with
very large numbers of references (especially if the reference namespace
is sharded appropriately), whereas in 1.7.7 some operations were
annoyingly slow.

Michael

[1] branch "refperf" at git://github.com/mhagger/git.git

> ===================================  ========  ========  ========
> Test name                                 [0]       [1]       [2]
> ===================================  ========  ========  ========
> branch-loose-cold                        1.59      1.68      0.29
> branch-loose-warm                        0.04      0.04      0.00
> for-each-ref-loose-cold                  1.86      1.96      1.88
> for-each-ref-loose-warm                  0.10      0.10      0.11
> checkout-loose-cold                      1.66      1.86      0.39
> checkout-loose-warm                      0.04      0.05      0.01
> checkout-orphan-loose                    0.04      0.04      0.00
> checkout-from-detached-loose-cold        2.04      2.11      1.81
> checkout-from-detached-loose-warm        0.24      0.15      0.16
> branch-contains-loose-cold               1.79      1.86      1.87
> branch-contains-loose-warm               0.14      0.14      0.14
> pack-refs-loose                          0.49      0.53      0.53
> branch-packed-cold                       0.28      0.25      0.25
> branch-packed-warm                       0.02      0.00      0.00
> for-each-ref-packed-cold                 0.34      0.39      0.40
> for-each-ref-packed-warm                 0.07      0.07      0.07
> checkout-packed-cold                     2.81      0.50      0.55
> checkout-packed-warm                     0.01      0.00      0.01
> checkout-orphan-packed                   0.00      0.00      0.00
> checkout-from-detached-packed-cold       2.83      0.55      0.46
> checkout-from-detached-packed-warm       2.45      0.12      0.13
> branch-contains-packed-cold              0.38      0.32      0.43
> branch-contains-packed-warm              0.11      0.11      0.11
> clone-loose-cold                        30.16     30.31     30.51
> clone-loose-warm                         1.28      1.30      1.33
> fetch-nothing-loose                      0.21      0.39      0.38
> pack-refs                                0.14      0.12      0.14
> fetch-nothing-packed                     0.21      0.40      0.39
> clone-packed-cold                        1.07      1.24      1.18
> clone-packed-warm                        0.23      0.23      0.22
> fetch-everything-cold                   30.49     30.89     31.09
> fetch-everything-warm                    1.78      2.01      2.06
> filter-branch-warm                    2949.81   2891.51    440.60
> ===================================  ========  ========  ========
> 
> 
> [0] 8d19b44 (tag: v1.7.7.2) Git 1.7.7.2
>     Test repository created using: t/make-refperf-repo --commits 20000 --refs 10000
> [1] bc1bbe0 (tag: v1.7.8-rc2) Git 1.7.8-rc2
>     Test repository created using: t/make-refperf-repo --commits 20000 --refs 10000
> [2] 01494b4 (github/ref-api-D) repack_without_ref(): call clear_packed_ref_cache()
>     Test repository created using: t/make-refperf-repo --commits 20000 --refs 10000



-- 
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/