[PATCH 0/5] Store submodules in a hash, not a linked list

[PATCH 0/5] Store submodules in a hash, not a linked list

[Michael Haggerty]

I have mentioned this patch series on the mailing list a couple of
time [1,2] but haven't submitted it before. I just rebased it to
current master. It is available from my Git fork [3] as branch
"submodule-hash".

The first point of this patch series is to optimize submodule
`ref_store` lookup by storing the `ref_store`s in a hashmap rather
than a linked list. But a more interesting second point is to weaken
the 1:1 relationship between submodules and `ref_stores` a little bit
more.

A `files_ref_store` would be perfectly happy to represent, say, the
references *physically* stored in a linked worktree (e.g., `HEAD`,
`refs/bisect/*`, etc) even though that is not the complete collection
of refs that are *logically* visible from that worktree (which
includes references from the main repository, too). But the old code
was confusing the two things by storing "submodule" in every
`ref_store` instance.

So push the submodule attribute down to the `files_ref_store` class
(but continue to let the `ref_store`s be looked up by submodule).

The last commit is relatively orthogonal to the others; it simplifies
read_loose_refs() by calling resolve_ref_recursively() directly using
the `ref_store` instance that it already has in hand, rather than
indirectly via the public wrappers.

Michael

[1] http://public-inbox.org/git/341999fc-4496-b974-c117-c18a2fca1358@alum.mit.edu/
[2] http://public-inbox.org/git/37fe2024-0378-a974-a28d-18a89d3e2312@alum.mit.edu/
[3] https://github.com/mhagger/git

Michael Haggerty (5):
  refs: store submodule ref stores in a hashmap
  refs: push the submodule attribute down
  register_ref_store(): new function
  files_ref_store::submodule: use NULL for the main repository
  read_loose_refs(): read refs using resolve_ref_recursively()

 refs.c               | 93 ++++++++++++++++++++++++++++++++++------------------
 refs/files-backend.c | 77 +++++++++++++++++++++++++------------------
 refs/refs-internal.h | 37 ++++++++-------------
 3 files changed, 122 insertions(+), 85 deletions(-)

-- 
2.9.3

[PATCH 1/5] refs: store submodule ref stores in a hashmap

[Michael Haggerty]

Aside from scaling better, this means that the submodule name needn't be
stored in the ref_store instance anymore (which will be changed in a
moment). This, in turn, will help loosen the strict 1:1 relationship
between ref_stores and submodules.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs.c               | 61 ++++++++++++++++++++++++++++++++++++++++------------
 refs/refs-internal.h |  6 ------
 2 files changed, 47 insertions(+), 20 deletions(-)

diff --git a/refs.c b/refs.c
index cd36b64..50d192c 100644
--- a/refs.c
+++ b/refs.c
@@ -3,6 +3,7 @@
  */
 
 #include "cache.h"
+#include "hashmap.h"
 #include "lockfile.h"
 #include "refs.h"
 #include "refs/refs-internal.h"
@@ -1357,11 +1358,42 @@ int resolve_gitlink_ref(const char *submodule, const char *refname,
 	return 0;
 }
 
+struct submodule_hash_entry
+{
+	struct hashmap_entry ent; /* must be the first member! */
+
+	struct ref_store *refs;
+
+	/* NUL-terminated name of submodule: */
+	char submodule[FLEX_ARRAY];
+};
+
+static int submodule_hash_cmp(const void *entry, const void *entry_or_key,
+			      const void *keydata)
+{
+	const struct submodule_hash_entry *e1 = entry, *e2 = entry_or_key;
+	const char *submodule = keydata;
+
+	return strcmp(e1->submodule, submodule ? submodule : e2->submodule);
+}
+
+static struct submodule_hash_entry *alloc_submodule_hash_entry(
+		const char *submodule, struct ref_store *refs)
+{
+	size_t len = strlen(submodule);
+	struct submodule_hash_entry *entry = malloc(sizeof(*entry) + len + 1);
+
+	hashmap_entry_init(entry, strhash(submodule));
+	entry->refs = refs;
+	memcpy(entry->submodule, submodule, len + 1);
+	return entry;
+}
+
 /* A pointer to the ref_store for the main repository: */
 static struct ref_store *main_ref_store;
 
-/* A linked list of ref_stores for submodules: */
-static struct ref_store *submodule_ref_stores;
+/* A hashmap of ref_stores, stored by submodule name: */
+static struct hashmap submodule_ref_stores;
 
 void base_ref_store_init(struct ref_store *refs,
 			 const struct ref_storage_be *be,
@@ -1373,16 +1405,17 @@ void base_ref_store_init(struct ref_store *refs,
 			die("BUG: main_ref_store initialized twice");
 
 		refs->submodule = "";
-		refs->next = NULL;
 		main_ref_store = refs;
 	} else {
-		if (lookup_ref_store(submodule))
+		refs->submodule = xstrdup(submodule);
+
+		if (!submodule_ref_stores.tablesize)
+			hashmap_init(&submodule_ref_stores, submodule_hash_cmp, 20);
+
+		if (hashmap_put(&submodule_ref_stores,
+				alloc_submodule_hash_entry(submodule, refs)))
 			die("BUG: ref_store for submodule '%s' initialized twice",
 			    submodule);
-
-		refs->submodule = xstrdup(submodule);
-		refs->next = submodule_ref_stores;
-		submodule_ref_stores = refs;
 	}
 }
 
@@ -1402,17 +1435,17 @@ struct ref_store *ref_store_init(const char *submodule)
 
 struct ref_store *lookup_ref_store(const char *submodule)
 {
-	struct ref_store *refs;
+	struct submodule_hash_entry *entry;
 
 	if (!submodule || !*submodule)
 		return main_ref_store;
 
-	for (refs = submodule_ref_stores; refs; refs = refs->next) {
-		if (!strcmp(submodule, refs->submodule))
-			return refs;
-	}
+	if (!submodule_ref_stores.tablesize)
+		hashmap_init(&submodule_ref_stores, submodule_hash_cmp, 20);
 
-	return NULL;
+	entry = hashmap_get_from_hash(&submodule_ref_stores,
+				      strhash(submodule), submodule);
+	return entry ? entry->refs : NULL;
 }
 
 struct ref_store *get_ref_store(const char *submodule)
diff --git a/refs/refs-internal.h b/refs/refs-internal.h
index 25444cf..4ed5f89 100644
--- a/refs/refs-internal.h
+++ b/refs/refs-internal.h
@@ -634,12 +634,6 @@ struct ref_store {
 	 * reference store:
 	 */
 	const char *submodule;
-
-	/*
-	 * Submodule reference store instances are stored in a linked
-	 * list using this pointer.
-	 */
-	struct ref_store *next;
 };
 
 /*
-- 
2.9.3

[PATCH 2/5] refs: push the submodule attribute down

[Michael Haggerty]

Push the submodule attribute down from ref_store to files_ref_store.
This is another step towards loosening the 1:1 connection between
ref_stores and submodules.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs.c               |  9 --------
 refs/files-backend.c | 61 ++++++++++++++++++++++++++++++++++++----------------
 refs/refs-internal.h | 13 -----------
 3 files changed, 43 insertions(+), 40 deletions(-)

diff --git a/refs.c b/refs.c
index 50d192c..723b4be 100644
--- a/refs.c
+++ b/refs.c
@@ -1404,11 +1404,8 @@ void base_ref_store_init(struct ref_store *refs,
 		if (main_ref_store)
 			die("BUG: main_ref_store initialized twice");
 
-		refs->submodule = "";
 		main_ref_store = refs;
 	} else {
-		refs->submodule = xstrdup(submodule);
-
 		if (!submodule_ref_stores.tablesize)
 			hashmap_init(&submodule_ref_stores, submodule_hash_cmp, 20);
 
@@ -1473,12 +1470,6 @@ struct ref_store *get_ref_store(const char *submodule)
 	return refs;
 }
 
-void assert_main_repository(struct ref_store *refs, const char *caller)
-{
-	if (*refs->submodule)
-		die("BUG: %s called for a submodule", caller);
-}
-
 /* backend functions */
 int pack_refs(unsigned int flags)
 {
diff --git a/refs/files-backend.c b/refs/files-backend.c
index c041d4b..6ed7e13 100644
--- a/refs/files-backend.c
+++ b/refs/files-backend.c
@@ -912,6 +912,14 @@ struct packed_ref_cache {
  */
 struct files_ref_store {
 	struct ref_store base;
+
+	/*
+	 * The name of the submodule represented by this object, or
+	 * the empty string if it represents the main repository's
+	 * reference store:
+	 */
+	const char *submodule;
+
 	struct ref_entry *loose;
 	struct packed_ref_cache *packed;
 };
@@ -974,10 +982,23 @@ static struct ref_store *files_ref_store_create(const char *submodule)
 
 	base_ref_store_init(ref_store, &refs_be_files, submodule);
 
+	refs->submodule = submodule ? xstrdup(submodule) : "";
+
 	return ref_store;
 }
 
 /*
+ * Die if refs is for a submodule (i.e., not for the main repository).
+ * caller is used in any necessary error messages.
+ */
+static void files_assert_main_repository(struct files_ref_store *refs,
+					 const char *caller)
+{
+	if (*refs->submodule)
+		die("BUG: %s called for a submodule", caller);
+}
+
+/*
  * Downcast ref_store to files_ref_store. Die if ref_store is not a
  * files_ref_store. If submodule_allowed is not true, then also die if
  * files_ref_store is for a submodule (i.e., not for the main
@@ -987,14 +1008,18 @@ static struct files_ref_store *files_downcast(
 		struct ref_store *ref_store, int submodule_allowed,
 		const char *caller)
 {
+	struct files_ref_store *refs;
+
 	if (ref_store->be != &refs_be_files)
 		die("BUG: ref_store is type \"%s\" not \"files\" in %s",
 		    ref_store->be->name, caller);
 
+	refs = (struct files_ref_store *)ref_store;
+
 	if (!submodule_allowed)
-		assert_main_repository(ref_store, caller);
+		files_assert_main_repository(refs, caller);
 
-	return (struct files_ref_store *)ref_store;
+	return refs;
 }
 
 /* The length of a peeled reference line in packed-refs, including EOL: */
@@ -1133,8 +1158,8 @@ static struct packed_ref_cache *get_packed_ref_cache(struct files_ref_store *ref
 {
 	char *packed_refs_file;
 
-	if (*refs->base.submodule)
-		packed_refs_file = git_pathdup_submodule(refs->base.submodule,
+	if (*refs->submodule)
+		packed_refs_file = git_pathdup_submodule(refs->submodule,
 							 "packed-refs");
 	else
 		packed_refs_file = git_pathdup("packed-refs");
@@ -1203,8 +1228,8 @@ static void read_loose_refs(const char *dirname, struct ref_dir *dir)
 	size_t path_baselen;
 	int err = 0;
 
-	if (*refs->base.submodule)
-		err = strbuf_git_path_submodule(&path, refs->base.submodule, "%s", dirname);
+	if (*refs->submodule)
+		err = strbuf_git_path_submodule(&path, refs->submodule, "%s", dirname);
 	else
 		strbuf_git_path(&path, "%s", dirname);
 	path_baselen = path.len;
@@ -1244,10 +1269,10 @@ static void read_loose_refs(const char *dirname, struct ref_dir *dir)
 		} else {
 			int read_ok;
 
-			if (*refs->base.submodule) {
+			if (*refs->submodule) {
 				hashclr(sha1);
 				flag = 0;
-				read_ok = !resolve_gitlink_ref(refs->base.submodule,
+				read_ok = !resolve_gitlink_ref(refs->submodule,
 							       refname.buf, sha1);
 			} else {
 				read_ok = !read_ref_full(refname.buf,
@@ -1358,8 +1383,8 @@ static int files_read_raw_ref(struct ref_store *ref_store,
 	*type = 0;
 	strbuf_reset(&sb_path);
 
-	if (*refs->base.submodule)
-		strbuf_git_path_submodule(&sb_path, refs->base.submodule, "%s", refname);
+	if (*refs->submodule)
+		strbuf_git_path_submodule(&sb_path, refs->submodule, "%s", refname);
 	else
 		strbuf_git_path(&sb_path, "%s", refname);
 
@@ -1540,7 +1565,7 @@ static int lock_raw_ref(struct files_ref_store *refs,
 	int ret = TRANSACTION_GENERIC_ERROR;
 
 	assert(err);
-	assert_main_repository(&refs->base, "lock_raw_ref");
+	files_assert_main_repository(refs, "lock_raw_ref");
 
 	*type = 0;
 
@@ -2006,7 +2031,7 @@ static struct ref_lock *lock_ref_sha1_basic(struct files_ref_store *refs,
 	int attempts_remaining = 3;
 	int resolved;
 
-	assert_main_repository(&refs->base, "lock_ref_sha1_basic");
+	files_assert_main_repository(refs, "lock_ref_sha1_basic");
 	assert(err);
 
 	lock = xcalloc(1, sizeof(struct ref_lock));
@@ -2152,7 +2177,7 @@ static int lock_packed_refs(struct files_ref_store *refs, int flags)
 	static int timeout_value = 1000;
 	struct packed_ref_cache *packed_ref_cache;
 
-	assert_main_repository(&refs->base, "lock_packed_refs");
+	files_assert_main_repository(refs, "lock_packed_refs");
 
 	if (!timeout_configured) {
 		git_config_get_int("core.packedrefstimeout", &timeout_value);
@@ -2190,7 +2215,7 @@ static int commit_packed_refs(struct files_ref_store *refs)
 	int save_errno = 0;
 	FILE *out;
 
-	assert_main_repository(&refs->base, "commit_packed_refs");
+	files_assert_main_repository(refs, "commit_packed_refs");
 
 	if (!packed_ref_cache->lock)
 		die("internal error: packed-refs not locked");
@@ -2223,7 +2248,7 @@ static void rollback_packed_refs(struct files_ref_store *refs)
 	struct packed_ref_cache *packed_ref_cache =
 		get_packed_ref_cache(refs);
 
-	assert_main_repository(&refs->base, "rollback_packed_refs");
+	files_assert_main_repository(refs, "rollback_packed_refs");
 
 	if (!packed_ref_cache->lock)
 		die("internal error: packed-refs not locked");
@@ -2397,7 +2422,7 @@ static int repack_without_refs(struct files_ref_store *refs,
 	struct string_list_item *refname;
 	int ret, needs_repacking = 0, removed = 0;
 
-	assert_main_repository(&refs->base, "repack_without_refs");
+	files_assert_main_repository(refs, "repack_without_refs");
 	assert(err);
 
 	/* Look for a packed ref */
@@ -2930,7 +2955,7 @@ static int commit_ref_update(struct files_ref_store *refs,
 			     const unsigned char *sha1, const char *logmsg,
 			     struct strbuf *err)
 {
-	assert_main_repository(&refs->base, "commit_ref_update");
+	files_assert_main_repository(refs, "commit_ref_update");
 
 	clear_loose_ref_cache(refs);
 	if (log_ref_write(lock->ref_name, lock->old_oid.hash, sha1, logmsg, 0, err)) {
@@ -3560,7 +3585,7 @@ static int lock_ref_for_update(struct files_ref_store *refs,
 	int ret;
 	struct ref_lock *lock;
 
-	assert_main_repository(&refs->base, "lock_ref_for_update");
+	files_assert_main_repository(refs, "lock_ref_for_update");
 
 	if ((update->flags & REF_HAVE_NEW) && is_null_sha1(update->new_sha1))
 		update->flags |= REF_DELETING;
diff --git a/refs/refs-internal.h b/refs/refs-internal.h
index 4ed5f89..97f275b 100644
--- a/refs/refs-internal.h
+++ b/refs/refs-internal.h
@@ -627,13 +627,6 @@ extern struct ref_storage_be refs_be_files;
 struct ref_store {
 	/* The backend describing this ref_store's storage scheme: */
 	const struct ref_storage_be *be;
-
-	/*
-	 * The name of the submodule represented by this object, or
-	 * the empty string if it represents the main repository's
-	 * reference store:
-	 */
-	const char *submodule;
 };
 
 /*
@@ -675,10 +668,4 @@ struct ref_store *lookup_ref_store(const char *submodule);
  */
 struct ref_store *get_ref_store(const char *submodule);
 
-/*
- * Die if refs is for a submodule (i.e., not for the main repository).
- * caller is used in any necessary error messages.
- */
-void assert_main_repository(struct ref_store *refs, const char *caller);
-
 #endif /* REFS_REFS_INTERNAL_H */
-- 
2.9.3

[PATCH 3/5] register_ref_store(): new function

[Michael Haggerty]

Move the responsibility for registering the ref_store for a submodule
from base_ref_store_init() to a new function, register_ref_store(). Call
the latter from ref_store_init().

This means that base_ref_store_init() can lose its submodule argument,
further weakening the 1:1 relationship between ref_stores and
submodules.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs.c               | 19 +++++++++++++------
 refs/files-backend.c |  2 +-
 refs/refs-internal.h | 15 ++++++++++-----
 3 files changed, 24 insertions(+), 12 deletions(-)

diff --git a/refs.c b/refs.c
index 723b4be..6012f67 100644
--- a/refs.c
+++ b/refs.c
@@ -1395,11 +1395,8 @@ static struct ref_store *main_ref_store;
 /* A hashmap of ref_stores, stored by submodule name: */
 static struct hashmap submodule_ref_stores;
 
-void base_ref_store_init(struct ref_store *refs,
-			 const struct ref_storage_be *be,
-			 const char *submodule)
+void register_ref_store(struct ref_store *refs, const char *submodule)
 {
-	refs->be = be;
 	if (!submodule) {
 		if (main_ref_store)
 			die("BUG: main_ref_store initialized twice");
@@ -1416,18 +1413,28 @@ void base_ref_store_init(struct ref_store *refs,
 	}
 }
 
+void base_ref_store_init(struct ref_store *refs,
+			 const struct ref_storage_be *be)
+{
+	refs->be = be;
+}
+
 struct ref_store *ref_store_init(const char *submodule)
 {
 	const char *be_name = "files";
 	struct ref_storage_be *be = find_ref_storage_backend(be_name);
+	struct ref_store *refs;
 
 	if (!be)
 		die("BUG: reference backend %s is unknown", be_name);
 
 	if (!submodule || !*submodule)
-		return be->init(NULL);
+		refs = be->init(NULL);
 	else
-		return be->init(submodule);
+		refs = be->init(submodule);
+
+	register_ref_store(refs, submodule);
+	return refs;
 }
 
 struct ref_store *lookup_ref_store(const char *submodule)
diff --git a/refs/files-backend.c b/refs/files-backend.c
index 6ed7e13..794b88c 100644
--- a/refs/files-backend.c
+++ b/refs/files-backend.c
@@ -980,7 +980,7 @@ static struct ref_store *files_ref_store_create(const char *submodule)
 	struct files_ref_store *refs = xcalloc(1, sizeof(*refs));
 	struct ref_store *ref_store = (struct ref_store *)refs;
 
-	base_ref_store_init(ref_store, &refs_be_files, submodule);
+	base_ref_store_init(ref_store, &refs_be_files);
 
 	refs->submodule = submodule ? xstrdup(submodule) : "";
 
diff --git a/refs/refs-internal.h b/refs/refs-internal.h
index 97f275b..73281f5 100644
--- a/refs/refs-internal.h
+++ b/refs/refs-internal.h
@@ -481,7 +481,7 @@ struct ref_store;
  * Initialize the ref_store for the specified submodule, or for the
  * main repository if submodule == NULL. These functions should call
  * base_ref_store_init() to initialize the shared part of the
- * ref_store and to record the ref_store for later lookup.
+ * ref_store.
  */
 typedef struct ref_store *ref_store_init_fn(const char *submodule);
 
@@ -630,12 +630,17 @@ struct ref_store {
 };
 
 /*
- * Fill in the generic part of refs for the specified submodule and
- * add it to our collection of reference stores.
+ * Register the specified ref_store to be the one that should be used
+ * for submodule (or the main repository if submodule is NULL). It is
+ * a fatal error to call this function twice for the same submodule.
+ */
+void register_ref_store(struct ref_store *refs, const char *submodule);
+
+/*
+ * Fill in the generic part of refs.
  */
 void base_ref_store_init(struct ref_store *refs,
-			 const struct ref_storage_be *be,
-			 const char *submodule);
+			 const struct ref_storage_be *be);
 
 /*
  * Create, record, and return a ref_store instance for the specified
-- 
2.9.3

[PATCH 4/5] files_ref_store::submodule: use NULL for the main repository

[Michael Haggerty]

The old practice of storing the empty string in this member for the main
repository was a holdover from before 00eebe3 (refs: create a base class
"ref_store" for files_ref_store, 2016-09-04), when the submodule was
stored in a flex array at the end of `struct files_ref_store`. Storing
NULL for this case is more idiomatic and a tiny bit less code.

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

diff --git a/refs/files-backend.c b/refs/files-backend.c
index 794b88c..069a8ee 100644
--- a/refs/files-backend.c
+++ b/refs/files-backend.c
@@ -915,8 +915,8 @@ struct files_ref_store {
 
 	/*
 	 * The name of the submodule represented by this object, or
-	 * the empty string if it represents the main repository's
-	 * reference store:
+	 * NULL if it represents the main repository's reference
+	 * store:
 	 */
 	const char *submodule;
 
@@ -982,7 +982,7 @@ static struct ref_store *files_ref_store_create(const char *submodule)
 
 	base_ref_store_init(ref_store, &refs_be_files);
 
-	refs->submodule = submodule ? xstrdup(submodule) : "";
+	refs->submodule = xstrdup_or_null(submodule);
 
 	return ref_store;
 }
@@ -994,7 +994,7 @@ static struct ref_store *files_ref_store_create(const char *submodule)
 static void files_assert_main_repository(struct files_ref_store *refs,
 					 const char *caller)
 {
-	if (*refs->submodule)
+	if (refs->submodule)
 		die("BUG: %s called for a submodule", caller);
 }
 
@@ -1158,7 +1158,7 @@ static struct packed_ref_cache *get_packed_ref_cache(struct files_ref_store *ref
 {
 	char *packed_refs_file;
 
-	if (*refs->submodule)
+	if (refs->submodule)
 		packed_refs_file = git_pathdup_submodule(refs->submodule,
 							 "packed-refs");
 	else
@@ -1228,7 +1228,7 @@ static void read_loose_refs(const char *dirname, struct ref_dir *dir)
 	size_t path_baselen;
 	int err = 0;
 
-	if (*refs->submodule)
+	if (refs->submodule)
 		err = strbuf_git_path_submodule(&path, refs->submodule, "%s", dirname);
 	else
 		strbuf_git_path(&path, "%s", dirname);
@@ -1269,7 +1269,7 @@ static void read_loose_refs(const char *dirname, struct ref_dir *dir)
 		} else {
 			int read_ok;
 
-			if (*refs->submodule) {
+			if (refs->submodule) {
 				hashclr(sha1);
 				flag = 0;
 				read_ok = !resolve_gitlink_ref(refs->submodule,
@@ -1383,7 +1383,7 @@ static int files_read_raw_ref(struct ref_store *ref_store,
 	*type = 0;
 	strbuf_reset(&sb_path);
 
-	if (*refs->submodule)
+	if (refs->submodule)
 		strbuf_git_path_submodule(&sb_path, refs->submodule, "%s", refname);
 	else
 		strbuf_git_path(&sb_path, "%s", refname);
-- 
2.9.3

[PATCH 5/5] read_loose_refs(): read refs using resolve_ref_recursively()

[Michael Haggerty]

There is no need to call read_ref_full() or resolve_gitlink_ref() from
read_loose_refs(), because we already have a ref_store object in hand.
So we can call resolve_ref_recursively() ourselves. Happily, this
unifies the code for the submodule vs. non-submodule cases.

This requires resolve_ref_recursively() to be exposed to the refs
subsystem, though not to non-refs code.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs.c               |  8 ++++----
 refs/files-backend.c | 18 ++++--------------
 refs/refs-internal.h |  5 +++++
 3 files changed, 13 insertions(+), 18 deletions(-)

diff --git a/refs.c b/refs.c
index 6012f67..210a453 100644
--- a/refs.c
+++ b/refs.c
@@ -1235,10 +1235,10 @@ int for_each_rawref(each_ref_fn fn, void *cb_data)
 }
 
 /* This function needs to return a meaningful errno on failure */
-static const char *resolve_ref_recursively(struct ref_store *refs,
-					   const char *refname,
-					   int resolve_flags,
-					   unsigned char *sha1, int *flags)
+const char *resolve_ref_recursively(struct ref_store *refs,
+				    const char *refname,
+				    int resolve_flags,
+				    unsigned char *sha1, int *flags)
 {
 	static struct strbuf sb_refname = STRBUF_INIT;
 	int unused_flags;
diff --git a/refs/files-backend.c b/refs/files-backend.c
index 069a8ee..f087a99 100644
--- a/refs/files-backend.c
+++ b/refs/files-backend.c
@@ -1267,20 +1267,10 @@ static void read_loose_refs(const char *dirname, struct ref_dir *dir)
 					 create_dir_entry(refs, refname.buf,
 							  refname.len, 1));
 		} else {
-			int read_ok;
-
-			if (refs->submodule) {
-				hashclr(sha1);
-				flag = 0;
-				read_ok = !resolve_gitlink_ref(refs->submodule,
-							       refname.buf, sha1);
-			} else {
-				read_ok = !read_ref_full(refname.buf,
-							 RESOLVE_REF_READING,
-							 sha1, &flag);
-			}
-
-			if (!read_ok) {
+			if (!resolve_ref_recursively(&refs->base,
+						     refname.buf,
+						     RESOLVE_REF_READING,
+						     sha1, &flag)) {
 				hashclr(sha1);
 				flag |= REF_ISBROKEN;
 			} else if (is_null_sha1(sha1)) {
diff --git a/refs/refs-internal.h b/refs/refs-internal.h
index 73281f5..af9e5fe 100644
--- a/refs/refs-internal.h
+++ b/refs/refs-internal.h
@@ -673,4 +673,9 @@ struct ref_store *lookup_ref_store(const char *submodule);
  */
 struct ref_store *get_ref_store(const char *submodule);
 
+const char *resolve_ref_recursively(struct ref_store *refs,
+				    const char *refname,
+				    int resolve_flags,
+				    unsigned char *sha1, int *flags);
+
 #endif /* REFS_REFS_INTERNAL_H */
-- 
2.9.3

Re: [PATCH 1/5] refs: store submodule ref stores in a hashmap

[Stefan Beller]

> @@ -1402,17 +1435,17 @@ struct ref_store *ref_store_init(const char *submodule)
>
>  struct ref_store *lookup_ref_store(const char *submodule)
>  {

> +       if (!submodule_ref_stores.tablesize)
> +               hashmap_init(&submodule_ref_stores, submodule_hash_cmp, 20);


So we can lookup a submodule even before we initialized the subsystem?
Does that actually happen? (It sounds like a bug to me.)

Instead of initializing, you could return NULL directly here.

Otherwise looks good.

Thanks,
Stefan

Re: [PATCH 2/5] refs: push the submodule attribute down

[Stefan Beller]

On Thu, Feb 9, 2017 at 5:26 AM, Michael Haggerty <mhagger@alum.mit.edu> wrote:
> Push the submodule attribute down from ref_store to files_ref_store.
> This is another step towards loosening the 1:1 connection between
> ref_stores and submodules.
>
> Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>

Looks good,
Stefan

Re: [PATCH 3/5] register_ref_store(): new function

[Stefan Beller]

On Thu, Feb 9, 2017 at 5:27 AM, Michael Haggerty <mhagger@alum.mit.edu> wrote:
> Move the responsibility for registering the ref_store for a submodule
> from base_ref_store_init() to a new function, register_ref_store(). Call
> the latter from ref_store_init().
>
> This means that base_ref_store_init() can lose its submodule argument,
> further weakening the 1:1 relationship between ref_stores and
> submodules.
>
> Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
> ---




> +
>  struct ref_store *ref_store_init(const char *submodule)
>  {
>         const char *be_name = "files";
>         struct ref_storage_be *be = find_ref_storage_backend(be_name);
> +       struct ref_store *refs;
>
>         if (!be)
>                 die("BUG: reference backend %s is unknown", be_name);
>
>         if (!submodule || !*submodule)
> -               return be->init(NULL);
> +               refs = be->init(NULL);
>         else
> -               return be->init(submodule);
> +               refs = be->init(submodule);
> +
> +       register_ref_store(refs, submodule);
> +       return refs;
>  }

This function is already very readable, though maybe it would be
more readable like so:

{
    const char *be_name = "files";
    struct ref_storage_be *be = find_ref_storage_backend(be_name);

    if (!be)
        die("BUG: reference backend %s is unknown", be_name);

    /* replace empty string by NULL */
    if (submodule && !*submodule)
        submodule = NULL;

    register_ref_store(be->init(submodule), submodule);
    return refs;
}

Well, I dunno; the function inside the arguments to register seems ugly, though.

Re: [PATCH 4/5] files_ref_store::submodule: use NULL for the main repository

[Stefan Beller]

On Thu, Feb 9, 2017 at 5:27 AM, Michael Haggerty <mhagger@alum.mit.edu> wrote:
> The old practice of storing the empty string in this member for the main
> repository was a holdover from before 00eebe3 (refs: create a base class
> "ref_store" for files_ref_store, 2016-09-04), when the submodule was
> stored in a flex array at the end of `struct files_ref_store`. Storing
> NULL for this case is more idiomatic and a tiny bit less code.
>
> Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
> ---

Makes sense!
Stefan

Re: [PATCH 5/5] read_loose_refs(): read refs using resolve_ref_recursively()

[Stefan Beller]

On Thu, Feb 9, 2017 at 5:27 AM, Michael Haggerty <mhagger@alum.mit.edu> wrote:
> There is no need to call read_ref_full() or resolve_gitlink_ref() from
> read_loose_refs(), because we already have a ref_store object in hand.
> So we can call resolve_ref_recursively() ourselves. Happily, this
> unifies the code for the submodule vs. non-submodule cases.
>
> This requires resolve_ref_recursively() to be exposed to the refs
> subsystem, though not to non-refs code.
>
> Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
> ---

Looks good,
Stefan

Re: [PATCH 1/5] refs: store submodule ref stores in a hashmap

[Michael Haggerty]

On 02/09/2017 05:58 PM, Stefan Beller wrote:
>> @@ -1402,17 +1435,17 @@ struct ref_store *ref_store_init(const char *submodule)
>>
>>  struct ref_store *lookup_ref_store(const char *submodule)
>>  {
> 
>> +       if (!submodule_ref_stores.tablesize)
>> +               hashmap_init(&submodule_ref_stores, submodule_hash_cmp, 20);
> 
> 
> So we can lookup a submodule even before we initialized the subsystem?
> Does that actually happen? (It sounds like a bug to me.)
>
> Instead of initializing, you could return NULL directly here.

The lines you quoted are only concerned with bringing the (empty)
hashmap into existence if it hasn't been initialized already. (There's
no HASHMAP_INIT.) I don't know what you mean by "initialize the
subsystem". The only way to bring a ref_store *object* into existence is
currently to call get_ref_store(submodule), which calls
lookup_ref_store(submodule) to see if it already exists, and if not
calls ref_store_init(submodule) to instantiate it and register it in the
hashmap. There's nothing else that has to be initialize before that
(except maybe the usual startup config reading etc.)

I suppose this code path could be changed to return NULL without
initializing the hashmap, but the hashmap will be initialized a moment
later by ref_store_init(), so I don't see much difference either way.

Thanks for your review!
Michael

Re: [PATCH 1/5] refs: store submodule ref stores in a hashmap

[Stefan Beller]

On Thu, Feb 9, 2017 at 9:40 AM, Michael Haggerty <mhagger@alum.mit.edu> wrote:
> On 02/09/2017 05:58 PM, Stefan Beller wrote:
>>> @@ -1402,17 +1435,17 @@ struct ref_store *ref_store_init(const char *submodule)
>>>
>>>  struct ref_store *lookup_ref_store(const char *submodule)
>>>  {
>>
>>> +       if (!submodule_ref_stores.tablesize)
>>> +               hashmap_init(&submodule_ref_stores, submodule_hash_cmp, 20);
>>
>>
>> So we can lookup a submodule even before we initialized the subsystem?
>> Does that actually happen? (It sounds like a bug to me.)
>>
>> Instead of initializing, you could return NULL directly here.
>
> The lines you quoted are only concerned with bringing the (empty)
> hashmap into existence if it hasn't been initialized already. (There's
> no HASHMAP_INIT.) I don't know what you mean by "initialize the
> subsystem". The only way to bring a ref_store *object* into existence is
> currently to call get_ref_store(submodule), which calls
> lookup_ref_store(submodule) to see if it already exists, and if not
> calls ref_store_init(submodule) to instantiate it and register it in the
> hashmap. There's nothing else that has to be initialize before that
> (except maybe the usual startup config reading etc.)
>
> I suppose this code path could be changed to return NULL without
> initializing the hashmap, but the hashmap will be initialized a moment
> later by ref_store_init(), so I don't see much difference either way.

Oh, I did not see that.

Thanks,
Stefan

>
> Thanks for your review!
> Michael
>

Re: [PATCH 3/5] register_ref_store(): new function

[Michael Haggerty]

On 02/09/2017 06:20 PM, Stefan Beller wrote:
> On Thu, Feb 9, 2017 at 5:27 AM, Michael Haggerty <mhagger@alum.mit.edu> wrote:
>> Move the responsibility for registering the ref_store for a submodule
>> from base_ref_store_init() to a new function, register_ref_store(). Call
>> the latter from ref_store_init().
>>
>> This means that base_ref_store_init() can lose its submodule argument,
>> further weakening the 1:1 relationship between ref_stores and
>> submodules.
>>
>> Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
>> ---
> 
> 
> 
> 
>> +
>>  struct ref_store *ref_store_init(const char *submodule)
>>  {
>>         const char *be_name = "files";
>>         struct ref_storage_be *be = find_ref_storage_backend(be_name);
>> +       struct ref_store *refs;
>>
>>         if (!be)
>>                 die("BUG: reference backend %s is unknown", be_name);
>>
>>         if (!submodule || !*submodule)
>> -               return be->init(NULL);
>> +               refs = be->init(NULL);
>>         else
>> -               return be->init(submodule);
>> +               refs = be->init(submodule);
>> +
>> +       register_ref_store(refs, submodule);
>> +       return refs;
>>  }
> 
> This function is already very readable, though maybe it would be
> more readable like so:
> 
> {
>     const char *be_name = "files";
>     struct ref_storage_be *be = find_ref_storage_backend(be_name);
> 
>     if (!be)
>         die("BUG: reference backend %s is unknown", be_name);
> 
>     /* replace empty string by NULL */
>     if (submodule && !*submodule)
>         submodule = NULL;
> 
>     register_ref_store(be->init(submodule), submodule);
>     return refs;
> }
> 
> Well, I dunno; the function inside the arguments to register seems ugly, though.

Nit: you forgot to define and initialize `refs` (for returning to the
caller).

Actually, there is an inconsistency between the docstring for this
function and its behavior. The docstring claims that it can handle
`submodule == ""`, and it tries to do so, but incorrectly. The problem
is that it passes an un-cleaned-up `submodule` to
`register_ref_store()`, which is expecting a cleaned-up one.

But this function is only called by get_ref_store(), which has already
arranged for the empty string to be passed along as NULL.

In fact, the only external entry point into these functions is
`get_ref_store()`. I think what I should do is make the other functions
private, and remove their attempts to handle `submodule == ""`. I'll fix
this up in a re-roll.

(I wonder whether anybody really passes the empty string into this
method. It never happens in the test suite. I doubt I can muster the
energy to audit all of the call paths.)

Michael

Re: [PATCH 1/5] refs: store submodule ref stores in a hashmap

[Jeff King]

On Thu, Feb 09, 2017 at 06:40:29PM +0100, Michael Haggerty wrote:

> On 02/09/2017 05:58 PM, Stefan Beller wrote:
> >> @@ -1402,17 +1435,17 @@ struct ref_store *ref_store_init(const char *submodule)
> >>
> >>  struct ref_store *lookup_ref_store(const char *submodule)
> >>  {
> > 
> >> +       if (!submodule_ref_stores.tablesize)
> >> +               hashmap_init(&submodule_ref_stores, submodule_hash_cmp, 20);
> > 
> > 
> > So we can lookup a submodule even before we initialized the subsystem?
> > Does that actually happen? (It sounds like a bug to me.)
> >
> > Instead of initializing, you could return NULL directly here.
> [...]
> I suppose this code path could be changed to return NULL without
> initializing the hashmap, but the hashmap will be initialized a moment
> later by ref_store_init(), so I don't see much difference either way.

I faced a similar issue when adding the oidset API recently: 

  http://public-inbox.org/git/20170208205307.uvgj3saf3cyrvtan@sigill.intra.peff.net/

I came to the same conclusion that it doesn't matter much in practice. A
nice thing about "return NULL" is that you do not have to duplicate the
initialization which happens on the "write" side (so if you ever changed
submodule_hash_cmp, for example, it needs changed in both places).

I also used the "cmpfn" member to check whether the table had been
initialized, which matches existing uses elsewhere. But I do notice that
the documentation explicitly says "tablesize" is good for this purpose,
so it's probably a better choice.

-Peff

Re: [PATCH 0/5] Store submodules in a hash, not a linked list

[Junio C Hamano]

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

> I have mentioned this patch series on the mailing list a couple of
> time [1,2] but haven't submitted it before. I just rebased it to
> current master. It is available from my Git fork [3] as branch
> "submodule-hash".
>
> The first point of this patch series is to optimize submodule
> `ref_store` lookup by storing the `ref_store`s in a hashmap rather
> than a linked list. But a more interesting second point is to weaken
> the 1:1 relationship between submodules and `ref_stores` a little bit
> more.
>
> A `files_ref_store` would be perfectly happy to represent, say, the
> references *physically* stored in a linked worktree (e.g., `HEAD`,
> `refs/bisect/*`, etc) even though that is not the complete collection
> of refs that are *logically* visible from that worktree (which
> includes references from the main repository, too). But the old code
> was confusing the two things by storing "submodule" in every
> `ref_store` instance.
>
> So push the submodule attribute down to the `files_ref_store` class
> (but continue to let the `ref_store`s be looked up by submodule).
>
> The last commit is relatively orthogonal to the others; it simplifies
> read_loose_refs() by calling resolve_ref_recursively() directly using
> the `ref_store` instance that it already has in hand, rather than
> indirectly via the public wrappers.
>
> Michael
>
> [1] http://public-inbox.org/git/341999fc-4496-b974-c117-c18a2fca1358@alum.mit.edu/
> [2] http://public-inbox.org/git/37fe2024-0378-a974-a28d-18a89d3e2312@alum.mit.edu/
> [3] https://github.com/mhagger/git
>
> Michael Haggerty (5):
>   refs: store submodule ref stores in a hashmap
>   refs: push the submodule attribute down
>   register_ref_store(): new function
>   files_ref_store::submodule: use NULL for the main repository
>   read_loose_refs(): read refs using resolve_ref_recursively()

Thanks.  Will queue on mh/submodule-hash forked from 'maint'.

Re: [PATCH 0/5] Store submodules in a hash, not a linked list

[Jeff King]

On Thu, Feb 09, 2017 at 02:26:57PM +0100, Michael Haggerty wrote:

> I have mentioned this patch series on the mailing list a couple of
> time [1,2] but haven't submitted it before. I just rebased it to
> current master. It is available from my Git fork [3] as branch
> "submodule-hash".
> 
> The first point of this patch series is to optimize submodule
> `ref_store` lookup by storing the `ref_store`s in a hashmap rather
> than a linked list. But a more interesting second point is to weaken
> the 1:1 relationship between submodules and `ref_stores` a little bit
> more.

Sounds good. I remember this had been discussed before due to
performance issues with resolve_gitlink_ref(), and we took a different
route (not populating non-submodule entries). I think it's nice to have
both optimizations, though, as they hit different use cases.

> A `files_ref_store` would be perfectly happy to represent, say, the
> references *physically* stored in a linked worktree (e.g., `HEAD`,
> `refs/bisect/*`, etc) even though that is not the complete collection
> of refs that are *logically* visible from that worktree (which
> includes references from the main repository, too). But the old code
> was confusing the two things by storing "submodule" in every
> `ref_store` instance.
> 
> So push the submodule attribute down to the `files_ref_store` class
> (but continue to let the `ref_store`s be looked up by submodule).

I'm not sure I understand all of the ramifications here. It _sounds_ like
pushing this down into the files-backend code would make it harder to
have mixed ref-backends for different submodules. Or is this just
pushing down an implementation detail of the files backend, and future
code is free to have as many different ref_stores as it likes?

-Peff

Re: [PATCH 1/5] refs: store submodule ref stores in a hashmap

[Junio C Hamano]

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

> Aside from scaling better, this means that the submodule name needn't be
> stored in the ref_store instance anymore (which will be changed in a
> moment).

Nice.  I like the latter reason very much (this is not a suggestion
to change the description).

> +struct submodule_hash_entry
> +{
> +	struct hashmap_entry ent; /* must be the first member! */
> +
> +	struct ref_store *refs;
> +
> +	/* NUL-terminated name of submodule: */
> +	char submodule[FLEX_ARRAY];
> +};
> +
> +static int submodule_hash_cmp(const void *entry, const void *entry_or_key,
> +			      const void *keydata)
> +{
> +	const struct submodule_hash_entry *e1 = entry, *e2 = entry_or_key;
> +	const char *submodule = keydata;
> +
> +	return strcmp(e1->submodule, submodule ? submodule : e2->submodule);

I would have found it more readable if it were like so:

	const char *submodule = keydata ? keydata : e2->submodule;

	return strcmp(e1->submodule, submodule);

but I suspect the difference is not that huge.

> +}
> +
> +static struct submodule_hash_entry *alloc_submodule_hash_entry(
> +		const char *submodule, struct ref_store *refs)
> +{
> +	size_t len = strlen(submodule);
> +	struct submodule_hash_entry *entry = malloc(sizeof(*entry) + len + 1);

I think this (and the later memcpy) is what FLEX_ALLOC_MEM() was
invented for.

> +	hashmap_entry_init(entry, strhash(submodule));
> +	entry->refs = refs;
> +	memcpy(entry->submodule, submodule, len + 1);
> +	return entry;
> +}
> ...
> @@ -1373,16 +1405,17 @@ void base_ref_store_init(struct ref_store *refs,
>  			die("BUG: main_ref_store initialized twice");
>  
>  		refs->submodule = "";
> -		refs->next = NULL;
>  		main_ref_store = refs;
>  	} else {
> -		if (lookup_ref_store(submodule))
> +		refs->submodule = xstrdup(submodule);
> +
> +		if (!submodule_ref_stores.tablesize)
> +			hashmap_init(&submodule_ref_stores, submodule_hash_cmp, 20);

Makes me wonder what "20" stands for.  Perhaps the caller should be
allowed to say "I do not quite care what initial size is" by passing
0 or some equally but more clealy meaningless value (which of course
would be outside the scope of this series).

Re: [PATCH 2/5] refs: push the submodule attribute down

[Junio C Hamano]

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

> Push the submodule attribute down from ref_store to files_ref_store.
> This is another step towards loosening the 1:1 connection between
> ref_stores and submodules.

The update seems to retain the externally visible effects, but what
does this change mean for future backend writers whose code will sit
next to files_ref_store?  They need to have "submodule" field in their
implementation of the backend and keep track of it?

Granted that the primary thing that looks at ->submodule field in
the code before this change all live in refs/files-backend.c, but I
am not sure if that is an artifact of us having only one backend at
this moment, or a sign that future backends would benefit from extra
freedom to choose how they exactly implement their submodule
support.

Re: [PATCH 3/5] register_ref_store(): new function

[Junio C Hamano]

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

> Move the responsibility for registering the ref_store for a submodule
> from base_ref_store_init() to a new function, register_ref_store(). Call
> the latter from ref_store_init().
>
> This means that base_ref_store_init() can lose its submodule argument,
> further weakening the 1:1 relationship between ref_stores and
> submodules.

OK.  I think I am starting to get it.  I've always found it
disturbing that for_each_*ref*() has a "submodule" variant.
Instead, the plan (outlined in the discussion from yesterday that
triggered your posting this series) is to give an API to request a
"ref-store", and then ask that object to iterate over refs, and
these steps get us closer to that goal, because the "to enumerate
these" won't have to know what set of refs a ref-store contains.  If
you want to iterate over refs in a submodule, you grab a ref-store
for the submodule and ask it to iterate.  Iterating over refs in
another worktree, you grab a different ref-store and ask it to
iterate using the same API.

Sounds like a good direction to go.

Re: [PATCH 4/5] files_ref_store::submodule: use NULL for the main repository

[Junio C Hamano]

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

> The old practice of storing the empty string in this member for the main
> repository was a holdover from before 00eebe3 (refs: create a base class
> "ref_store" for files_ref_store, 2016-09-04), when the submodule was
> stored in a flex array at the end of `struct files_ref_store`. Storing
> NULL for this case is more idiomatic and a tiny bit less code.

Yes.  I noticed this bit in 3/5 and wondered about it, knowing this
step comes next:

>  struct ref_store *ref_store_init(const char *submodule)
>  {
>  	const char *be_name = "files";
>  	struct ref_storage_be *be = find_ref_storage_backend(be_name);
> +	struct ref_store *refs;
>  
>  	if (!be)
>  		die("BUG: reference backend %s is unknown", be_name);
>  
>  	if (!submodule || !*submodule)
> -		return be->init(NULL);
> +		refs = be->init(NULL);
>  	else
> -		return be->init(submodule);
> +		refs = be->init(submodule);

Can't we also lose this "if !*submodule, turn it to NULL"?

> --- a/refs/files-backend.c
> +++ b/refs/files-backend.c
> @@ -980,7 +980,7 @@ static struct ref_store *files_ref_store_create(const char *submodule)
>  	struct files_ref_store *refs = xcalloc(1, sizeof(*refs));
>  	struct ref_store *ref_store = (struct ref_store *)refs;
>  
> -	base_ref_store_init(ref_store, &refs_be_files, submodule);
> +	base_ref_store_init(ref_store, &refs_be_files);
>  
>  	refs->submodule = submodule ? xstrdup(submodule) : "";

Also, can't we use xstrdup_or_null(submodule) with this step?

Re: [PATCH 0/5] Store submodules in a hash, not a linked list

[Michael Haggerty]

On 02/09/2017 08:58 PM, Jeff King wrote:
> On Thu, Feb 09, 2017 at 02:26:57PM +0100, Michael Haggerty wrote:
> [...]
>> A `files_ref_store` would be perfectly happy to represent, say, the
>> references *physically* stored in a linked worktree (e.g., `HEAD`,
>> `refs/bisect/*`, etc) even though that is not the complete collection
>> of refs that are *logically* visible from that worktree (which
>> includes references from the main repository, too). But the old code
>> was confusing the two things by storing "submodule" in every
>> `ref_store` instance.
>>
>> So push the submodule attribute down to the `files_ref_store` class
>> (but continue to let the `ref_store`s be looked up by submodule).
> 
> I'm not sure I understand all of the ramifications here. It _sounds_ like
> pushing this down into the files-backend code would make it harder to
> have mixed ref-backends for different submodules. Or is this just
> pushing down an implementation detail of the files backend, and future
> code is free to have as many different ref_stores as it likes?

I don't understand how this would make it harder, aside from the fact
that a new backend class might also need a path member and have to
maintain its own copy rather than using one that the base class provides.

I consider it an implementation detail of the files backend that it
needs to keep a permanent record of its submodule path in
files_ref_store. Some hypothetical future backend might instead need,
say, an IP number and port to connect to a MySQL server. A hypothetical
pure packed-refs backend might just store the path of the packed-refs file.

A more likely imminent change is that backends need a path, but that the
path needn't correspond to the git_dir of the repository that contains
the corresponding objects, for example in the case of a linked worktree.
You might ask for the ref_store for a worktree-submodule, and end up
getting a compound object that delegates to one ref_store pointing at
its git_dir and one at its common_dir.

Michael

Re: [PATCH 4/5] files_ref_store::submodule: use NULL for the main repository

[Stefan Beller]

On Thu, Feb 9, 2017 at 1:19 PM, Junio C Hamano <gitster@pobox.com> wrote:

>>       if (!submodule || !*submodule)
>> -             return be->init(NULL);
>> +             refs = be->init(NULL);
>>       else
>> -             return be->init(submodule);
>> +             refs = be->init(submodule);
>
> Can't we also lose this "if !*submodule, turn it to NULL"?

That was my suggestion as well, but that did not look nicer per se.
That is because at this point of the series we still handle "" just fine.

>>       refs->submodule = submodule ? xstrdup(submodule) : "";
>
> Also, can't we use xstrdup_or_null(submodule) with this step?
>

That is done in 4/5; here we must keep a "" around instead of NULL IIUC.

Re: [PATCH 0/5] Store submodules in a hash, not a linked list

[Jeff King]

On Thu, Feb 09, 2017 at 10:23:35PM +0100, Michael Haggerty wrote:

> >> So push the submodule attribute down to the `files_ref_store` class
> >> (but continue to let the `ref_store`s be looked up by submodule).
> > 
> > I'm not sure I understand all of the ramifications here. It _sounds_ like
> > pushing this down into the files-backend code would make it harder to
> > have mixed ref-backends for different submodules. Or is this just
> > pushing down an implementation detail of the files backend, and future
> > code is free to have as many different ref_stores as it likes?
> 
> I don't understand how this would make it harder, aside from the fact
> that a new backend class might also need a path member and have to
> maintain its own copy rather than using one that the base class provides.

Probably the answer is "I'm really confused".

But here's how my line of reasoning went:

  Right now we have a main ref-store that points to the submodule
  ref-stores. I don't know the current state of it, but in theory those
  could all use different backends.

  This seems like it's pushing that submodule linkage down into the
  backend.

But I think from your response that the answer is no, the thing that is
being pushed down is not the right way for the main ref store and the
submodules to be linked. In fact, there is no reason at all for the
main ref store to know or care about submodules. Anybody who wants to
know about a submodule's refs should ask the hashmap.

-Peff

Re: [PATCH 1/5] refs: store submodule ref stores in a hashmap

[Jeff King]

On Thu, Feb 09, 2017 at 12:34:04PM -0800, Junio C Hamano wrote:

> > +static struct submodule_hash_entry *alloc_submodule_hash_entry(
> > +		const char *submodule, struct ref_store *refs)
> > +{
> > +	size_t len = strlen(submodule);
> > +	struct submodule_hash_entry *entry = malloc(sizeof(*entry) + len + 1);
> 
> I think this (and the later memcpy) is what FLEX_ALLOC_MEM() was
> invented for.

Yes, it was. Though since the length comes from a strlen() call, it can
actually use the _STR variant, like:

  FLEX_ALLOC_STR(entry, submodule, submodule);

Besides being shorter, this does integer-overflow checks on the final
length.

> > @@ -1373,16 +1405,17 @@ void base_ref_store_init(struct ref_store *refs,
> >  			die("BUG: main_ref_store initialized twice");
> >  
> >  		refs->submodule = "";
> > -		refs->next = NULL;
> >  		main_ref_store = refs;
> >  	} else {
> > -		if (lookup_ref_store(submodule))
> > +		refs->submodule = xstrdup(submodule);
> > +
> > +		if (!submodule_ref_stores.tablesize)
> > +			hashmap_init(&submodule_ref_stores, submodule_hash_cmp, 20);
> 
> Makes me wonder what "20" stands for.  Perhaps the caller should be
> allowed to say "I do not quite care what initial size is" by passing
> 0 or some equally but more clealy meaningless value (which of course
> would be outside the scope of this series).

I think this is what "0" already does (grep for HASHMAP_INITIAL_SIZE).
In fact, that constant is 64. The 20 we pass in goes through some magic
load-factor computation and ends up as 25. That being smaller than the
INITIAL_SIZE constant, I believe that we end up allocating 64 entries
either way (that's just from reading the code, though; I didn't run it
to double check).

-Peff

Re: [PATCH 1/5] refs: store submodule ref stores in a hashmap

[Michael Haggerty]

On 02/09/2017 09:34 PM, Junio C Hamano wrote:
> Michael Haggerty <mhagger@alum.mit.edu> writes:
>> [...]
>> +static int submodule_hash_cmp(const void *entry, const void *entry_or_key,
>> +			      const void *keydata)
>> +{
>> +	const struct submodule_hash_entry *e1 = entry, *e2 = entry_or_key;
>> +	const char *submodule = keydata;
>> +
>> +	return strcmp(e1->submodule, submodule ? submodule : e2->submodule);
> 
> I would have found it more readable if it were like so:
> 
> 	const char *submodule = keydata ? keydata : e2->submodule;
> 
> 	return strcmp(e1->submodule, submodule);
> 
> but I suspect the difference is not that huge.

Yes, that's better. I'll change it.

On 02/10/2017 05:04 AM, Jeff King wrote:
> On Thu, Feb 09, 2017 at 12:34:04PM -0800, Junio C Hamano wrote:
>
>>> +static struct submodule_hash_entry *alloc_submodule_hash_entry(
>>> +		const char *submodule, struct ref_store *refs)
>>> +{
>>> +	size_t len = strlen(submodule);
>>> +	struct submodule_hash_entry *entry = malloc(sizeof(*entry) + len + 1);
>>
>> I think this (and the later memcpy) is what FLEX_ALLOC_MEM() was
>> invented for.
>
> Yes, it was. Though since the length comes from a strlen() call, it can
> actually use the _STR variant, like:
>
>   FLEX_ALLOC_STR(entry, submodule, submodule);
>
> Besides being shorter, this does integer-overflow checks on the final
> length.

Nice. TIL. Will fix.

>>> @@ -1373,16 +1405,17 @@ void base_ref_store_init(struct ref_store *refs,
>>>  			die("BUG: main_ref_store initialized twice");
>>>
>>>  		refs->submodule = "";
>>> -		refs->next = NULL;
>>>  		main_ref_store = refs;
>>>  	} else {
>>> -		if (lookup_ref_store(submodule))
>>> +		refs->submodule = xstrdup(submodule);
>>> +
>>> +		if (!submodule_ref_stores.tablesize)
>>> +			hashmap_init(&submodule_ref_stores, submodule_hash_cmp, 20);
>>
>> Makes me wonder what "20" stands for.  Perhaps the caller should be
>> allowed to say "I do not quite care what initial size is" by passing
>> 0 or some equally but more clealy meaningless value (which of course
>> would be outside the scope of this series).
>
> I think this is what "0" already does (grep for HASHMAP_INITIAL_SIZE).
> In fact, that constant is 64. The 20 we pass in goes through some magic
> load-factor computation and ends up as 25. That being smaller than the
> INITIAL_SIZE constant, I believe that we end up allocating 64 entries
> either way (that's just from reading the code, though; I didn't run it
> to double check).

I guess I might as well change it to zero, then.

Thanks for the feedback!

Michael

Re: [PATCH 0/5] Store submodules in a hash, not a linked list

[Michael Haggerty]

On 02/10/2017 01:40 AM, Jeff King wrote:
> On Thu, Feb 09, 2017 at 10:23:35PM +0100, Michael Haggerty wrote:
> 
>>>> So push the submodule attribute down to the `files_ref_store` class
>>>> (but continue to let the `ref_store`s be looked up by submodule).
>>>
>>> I'm not sure I understand all of the ramifications here. It _sounds_ like
>>> pushing this down into the files-backend code would make it harder to
>>> have mixed ref-backends for different submodules. Or is this just
>>> pushing down an implementation detail of the files backend, and future
>>> code is free to have as many different ref_stores as it likes?
>>
>> I don't understand how this would make it harder, aside from the fact
>> that a new backend class might also need a path member and have to
>> maintain its own copy rather than using one that the base class provides.
> 
> Probably the answer is "I'm really confused".
> 
> But here's how my line of reasoning went:
> 
>   Right now we have a main ref-store that points to the submodule
>   ref-stores. I don't know the current state of it, but in theory those
>   could all use different backends.
> 
>   This seems like it's pushing that submodule linkage down into the
>   backend.
> 
> But I think from your response that the answer is no, the thing that is
> being pushed down is not the right way for the main ref store and the
> submodules to be linked. In fact, there is no reason at all for the
> main ref store to know or care about submodules. Anybody who wants to
> know about a submodule's refs should ask the hashmap.

That's correct; the main ref store and submodule ref stores know nothing
of each other.

Michael

Re: [PATCH 0/5] Store submodules in a hash, not a linked list

[Duy Nguyen]

On Thu, Feb 09, 2017 at 07:40:33PM -0500, Jeff King wrote:
> On Thu, Feb 09, 2017 at 10:23:35PM +0100, Michael Haggerty wrote:
> 
> > >> So push the submodule attribute down to the `files_ref_store` class
> > >> (but continue to let the `ref_store`s be looked up by submodule).
> > > 
> > > I'm not sure I understand all of the ramifications here. It _sounds_ like
> > > pushing this down into the files-backend code would make it harder to
> > > have mixed ref-backends for different submodules. Or is this just
> > > pushing down an implementation detail of the files backend, and future
> > > code is free to have as many different ref_stores as it likes?
> > 
> > I don't understand how this would make it harder, aside from the fact
> > that a new backend class might also need a path member and have to
> > maintain its own copy rather than using one that the base class provides.
> 
> Probably the answer is "I'm really confused".
> 
> But here's how my line of reasoning went:
> 
>   Right now we have a main ref-store that points to the submodule
>   ref-stores. I don't know the current state of it, but in theory those
>   could all use different backends.
> 
>   This seems like it's pushing that submodule linkage down into the
>   backend.
> 
> But I think from your response that the answer is no, the thing that is
> being pushed down is not the right way for the main ref store and the
> submodules to be linked.

I think it's more about "pushing out" than "pushing down". Once files
backend takes a path to .git directory, we could have a submodule
ref_store that resolves submodule path to that .git directory,
files-backend will not need to know anything about submodules.

I imagine in future lookup_ref_store() will take a .git path instead
of a submodule path, then iterate through all backends and call the
backend-specific "probe" function to let the backend figure out if
it's the right backend and whatever parameters it needs (e.g. IP
address or path). There would be submodule_lookup_ref_store() wrapper
that converts submodule path to .git path for lookup_ref_store() to
consume.
--
Duy