git/list[1] front-page[2] threads[3] people[4] search[5] about
 

[PATCH v2 48/51] refs: read loose references lazily

From
mhagger@alum.mit.edu <mhagger@alum.mit.edu>
Date
Dec 12, 2011, 05:38 UTC
Message-ID
<1323668338-1764-49-git-send-email-mhagger@alum.mit.edu>
In-Reply-To
<1323668338-1764-1-git-send-email-mhagger@alum.mit.edu>
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 a85a8a5..3cd8e04 100644
--- a/refs.c
+++ b/refs.c
@@ -101,6 +101,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];
@@ -108,6 +114,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;
 
@@ -125,19 +159,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
@@ -229,19 +277,21 @@ 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;
 	int len = strlen(dirname);
 	direntry = xcalloc(1, sizeof(struct ref_entry) + len + 1);
 	memcpy(direntry->name, dirname, len + 1);
-	direntry->flag = REF_DIR;
+	direntry->flag = flag;
 	direntry->u.subdir.ref_cache = ref_cache;
 	return direntry;
 }
@@ -266,6 +316,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;
@@ -322,8 +373,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;
@@ -399,6 +456,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 */
@@ -449,8 +507,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;
@@ -477,10 +535,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;
@@ -737,7 +795,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, 0));
 }
 
@@ -755,7 +813,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
@@ -777,11 +835,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)
@@ -819,11 +880,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) {
@@ -842,13 +904,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.8
Previous: mhagger@alum.mit.eduNext: mhagger@alum.mit.edu
Message 75 of 79 in “ref-api-C and ref-api-D re-roll”
  1. 00/51 ref-api-C and ref-api-D re-rollmhagger@alum.mit.edu, Dec 12, 2011
  2. 01/51 struct ref_entry: document name membermhagger@alum.mit.edu, Dec 12, 2011
  3. 02/51 refs: rename "refname" variablesmhagger@alum.mit.edu, Dec 12, 2011
  4. Junio C HamanoDec 13, 2011
  5. 03/51 refs: rename parameters result -> sha1mhagger@alum.mit.edu, Dec 12, 2011
  6. 04/51 clear_ref_array(): rename from free_ref_array()mhagger@alum.mit.edu, Dec 12, 2011
  7. 05/51 is_refname_available(): remove the "quiet" argumentmhagger@alum.mit.edu, Dec 12, 2011
  8. 06/51 parse_ref_line(): add docstringmhagger@alum.mit.edu, Dec 12, 2011
  9. 07/51 add_ref(): add docstringmhagger@alum.mit.edu, Dec 12, 2011
  10. 08/51 is_dup_ref(): extract function from sort_ref_array()mhagger@alum.mit.edu, Dec 12, 2011
  11. Jeff KingDec 12, 2011
  12. Michael HaggertyDec 12, 2011
  13. Junio C HamanoDec 12, 2011
  14. Junio C HamanoDec 12, 2011
  15. Michael HaggertyDec 13, 2011
  16. Michael HaggertyDec 13, 2011
  17. 09/51 refs: change signatures of get_packed_refs() and get_loose_refs()mhagger@alum.mit.edu, Dec 12, 2011
  18. 10/51 get_ref_dir(): change signaturemhagger@alum.mit.edu, Dec 12, 2011
  19. 11/51 resolve_gitlink_ref(): improve docstringmhagger@alum.mit.edu, Dec 12, 2011
  20. 12/51 Pass a (ref_cache *) to the resolve_gitlink_*() helper functionsmhagger@alum.mit.edu, Dec 12, 2011
  21. 13/51 resolve_gitlink_ref_recursive(): change to work with struct ref_cachemhagger@alum.mit.edu, Dec 12, 2011
  22. 14/51 repack_without_ref(): remove temporarymhagger@alum.mit.edu, Dec 12, 2011
  23. 15/51 create_ref_entry(): extract function from add_ref()mhagger@alum.mit.edu, Dec 12, 2011
  24. 16/51 add_ref(): take a (struct ref_entry *) parametermhagger@alum.mit.edu, Dec 12, 2011
  25. 17/51 do_for_each_ref(): correctly terminate while processesing extra_refsmhagger@alum.mit.edu, Dec 12, 2011
  26. Junio C HamanoDec 12, 2011
  27. 18/51 do_for_each_ref_in_array(): new functionmhagger@alum.mit.edu, Dec 12, 2011
  28. 19/51 do_for_each_ref_in_arrays(): new functionmhagger@alum.mit.edu, Dec 12, 2011
  29. 20/51 repack_without_ref(): reimplement using do_for_each_ref_in_array()mhagger@alum.mit.edu, Dec 12, 2011
  30. Junio C HamanoDec 12, 2011
  31. 21/51 names_conflict(): new function, extracted from is_refname_available()mhagger@alum.mit.edu, Dec 12, 2011
  32. 22/51 names_conflict(): simplify implementationmhagger@alum.mit.edu, Dec 12, 2011
  33. 23/51 is_refname_available(): reimplement using do_for_each_ref_in_array()mhagger@alum.mit.edu, Dec 12, 2011
  34. 24/51 refs.c: reorder definitions more logicallymhagger@alum.mit.edu, Dec 12, 2011
  35. 25/51 free_ref_entry(): new functionmhagger@alum.mit.edu, Dec 12, 2011
  36. 26/51 check_refname_component(): return 0 for zero-length componentsmhagger@alum.mit.edu, Dec 12, 2011
  37. 27/51 struct ref_entry: nest the value part in a unionmhagger@alum.mit.edu, Dec 12, 2011
  38. 28/51 refs.c: rename ref_array -> ref_dirmhagger@alum.mit.edu, Dec 12, 2011
  39. Junio C HamanoDec 13, 2011
  40. Michael HaggertyDec 13, 2011
  41. Junio C HamanoDec 13, 2011
  42. Michael HaggertyDec 13, 2011
  43. Junio C HamanoDec 13, 2011
  44. Michael HaggertyDec 13, 2011
  45. Junio C HamanoDec 13, 2011
  46. Junio C HamanoDec 14, 2011
  47. Jeff KingDec 14, 2011
  48. Michael HaggertyDec 15, 2011
  49. Jeff KingDec 15, 2011
  50. Michael HaggertyJan 17, 2012
  51. Michael HaggertyFeb 10, 2012
  52. Jeff KingFeb 10, 2012
  53. Junio C HamanoFeb 10, 2012
  54. Michael HaggertyFeb 11, 2012
  55. 29/51 refs: store references hierarchicallymhagger@alum.mit.edu, Dec 12, 2011
  56. 30/51 sort_ref_dir(): do not sort if already sortedmhagger@alum.mit.edu, Dec 12, 2011
  57. Junio C HamanoDec 12, 2011
  58. 31/51 refs: sort ref_dirs lazilymhagger@alum.mit.edu, Dec 12, 2011
  59. 32/51 do_for_each_ref(): only iterate over the subtree that was requestedmhagger@alum.mit.edu, Dec 12, 2011
  60. 33/51 get_ref_dir(): keep track of the current ref_dirmhagger@alum.mit.edu, Dec 12, 2011
  61. 34/51 refs: wrap top-level ref_dirs in ref_entriesmhagger@alum.mit.edu, Dec 12, 2011
  62. 35/51 get_packed_refs(): return (ref_entry *) instead of (ref_dir *)mhagger@alum.mit.edu, Dec 12, 2011
  63. 36/51 get_loose_refs(): return (ref_entry *) instead of (ref_dir *)mhagger@alum.mit.edu, Dec 12, 2011
  64. 37/51 is_refname_available(): take (ref_entry *) instead of (ref_dir *)mhagger@alum.mit.edu, Dec 12, 2011
  65. 38/51 find_ref(): take (ref_entry *) instead of (ref_dir *)mhagger@alum.mit.edu, Dec 12, 2011
  66. 39/51 read_packed_refs(): take (ref_entry *) instead of (ref_dir *)mhagger@alum.mit.edu, Dec 12, 2011
  67. 40/51 add_ref(): take (ref_entry *) instead of (ref_dir *)mhagger@alum.mit.edu, Dec 12, 2011
  68. 41/51 find_containing_direntry(): use (ref_entry *) instead of (ref_dir *)mhagger@alum.mit.edu, Dec 12, 2011
  69. 42/51 search_ref_dir(): take (ref_entry *) instead of (ref_dir *)mhagger@alum.mit.edu, Dec 12, 2011
  70. 43/51 add_entry(): take (ref_entry *) instead of (ref_dir *)mhagger@alum.mit.edu, Dec 12, 2011
  71. 44/51 do_for_each_ref_in_dir*(): take (ref_entry *) instead of (ref_dir *)mhagger@alum.mit.edu, Dec 12, 2011
  72. 45/51 sort_ref_dir(): take (ref_entry *) instead of (ref_dir *)mhagger@alum.mit.edu, Dec 12, 2011
  73. 46/51 struct ref_dir: store a reference to the enclosing ref_cachemhagger@alum.mit.edu, Dec 12, 2011
  74. 47/51 read_loose_refs(): take a (ref_entry *) as argumentmhagger@alum.mit.edu, Dec 12, 2011
  75. 48/51 refs: read loose references lazilymhagger@alum.mit.edu, Dec 12, 2011
  76. 49/51 is_refname_available(): query only possibly-conflicting referencesmhagger@alum.mit.edu, Dec 12, 2011
  77. 50/51 read_packed_refs(): keep track of the directory being worked inmhagger@alum.mit.edu, Dec 12, 2011
  78. 51/51 repack_without_ref(): call clear_packed_ref_cache()mhagger@alum.mit.edu, Dec 12, 2011
  79. Junio C HamanoDec 12, 2011

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.