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

[PATCH 02/27] sparse-index: implement ensure_full_index()

From
Derrick Stolee via GitGitGadget <gitgitgadget@gmail.com>
Date
Jan 25, 2021, 17:41 UTC
Message-ID
<ebbe8569dcc16f2ae235c4167be0e72a53982982.1611596534.git.gitgitgadget@gmail.com>
In-Reply-To
<pull.847.git.1611596533.gitgitgadget@gmail.com>
From: Derrick Stolee <dstolee@microsoft.com>

We will mark an in-memory index_state as having sparse directory entries with the sparse_index bit. These currently cannot exist, but we will add a mechanism for collapsing a full index to a sparse one in a later change. That will happen at write time, so we must first allow parsing the format before writing it.

Commands or methods that require a full index in order to operate can call ensure_full_index() to expand that index in-memory. This requires parsing trees using that index's repository.

Sparse directory entries have a specific 'ce_mode' value. The macro S_ISSPARSEDIR(ce) can check if a cache_entry 'ce' has this type. This ce_mode is not possible with the existing index formats, so we don't also verify all properties of a sparse-directory entry, which are:

 1. ce->ce_mode == 01000755
 2. ce->flags & CE_SKIP_WORKTREE is true
 3. ce->name[ce->namelen - 1] == '/' (ends in dir separator)
 4. ce->oid references a tree object.

These are all semi-enforced in ensure_full_index() to some extent. Any deviation will cause a warning at minimum or a failure in the worst case.

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 cache.h        | 11 +++++-
 read-cache.c   |  9 +++++
 sparse-index.c | 94 +++++++++++++++++++++++++++++++++++++++++++++++++-
 sparse-index.h |  1 +
 4 files changed, 113 insertions(+), 2 deletions(-)
diff --git a/cache.h b/cache.h
index f9c7a603841..884046ca5b8 100644
--- a/cache.h
+++ b/cache.h
@@ -204,6 +204,10 @@ struct cache_entry {
 #error "CE_EXTENDED_FLAGS out of range"
 #endif
 
+#define CE_MODE_SPARSE_DIRECTORY 01000755
+#define SPARSE_DIR_MODE 0100
+#define S_ISSPARSEDIR(m) ((m)->ce_mode == CE_MODE_SPARSE_DIRECTORY)
+
 /* Forward structure decls */
 struct pathspec;
 struct child_process;
@@ -249,6 +253,8 @@ static inline unsigned int create_ce_mode(unsigned int mode)
 {
 	if (S_ISLNK(mode))
 		return S_IFLNK;
+	if (mode == SPARSE_DIR_MODE)
+		return CE_MODE_SPARSE_DIRECTORY;
 	if (S_ISDIR(mode) || S_ISGITLINK(mode))
 		return S_IFGITLINK;
 	return S_IFREG | ce_permissions(mode);
@@ -319,7 +325,8 @@ struct index_state {
 		 drop_cache_tree : 1,
 		 updated_workdir : 1,
 		 updated_skipworktree : 1,
-		 fsmonitor_has_run_once : 1;
+		 fsmonitor_has_run_once : 1,
+		 sparse_index : 1;
 	struct hashmap name_hash;
 	struct hashmap dir_hash;
 	struct object_id oid;
@@ -721,6 +728,8 @@ int read_index_from(struct index_state *, const char *path,
 		    const char *gitdir);
 int is_index_unborn(struct index_state *);
 
+void ensure_full_index(struct index_state *istate);
+
 /* For use with `write_locked_index()`. */
 #define COMMIT_LOCK		(1 << 0)
 #define SKIP_IF_UNCHANGED	(1 << 1)
diff --git a/read-cache.c b/read-cache.c
index ecf6f689940..1097ecbf132 100644
--- a/read-cache.c
+++ b/read-cache.c
@@ -101,6 +101,9 @@ static const char *alternate_index_output;
 
 static void set_index_entry(struct index_state *istate, int nr, struct cache_entry *ce)
 {
+	if (S_ISSPARSEDIR(ce))
+		istate->sparse_index = 1;
+
 	istate->cache[nr] = ce;
 	add_name_hash(istate, ce);
 }
@@ -2255,6 +2258,12 @@ int do_read_index(struct index_state *istate, const char *path, int must_exist)
 	trace2_data_intmax("index", the_repository, "read/cache_nr",
 			   istate->cache_nr);
 
+	if (!istate->repo)
+		istate->repo = the_repository;
+	prepare_repo_settings(istate->repo);
+	if (istate->repo->settings.command_requires_full_index)
+		ensure_full_index(istate);
+
 	return istate->cache_nr;
 
 unmap:
diff --git a/sparse-index.c b/sparse-index.c
index 82183ead563..1e70244dc13 100644
--- a/sparse-index.c
+++ b/sparse-index.c
@@ -1,8 +1,100 @@
 #include "cache.h"
 #include "repository.h"
 #include "sparse-index.h"
+#include "tree.h"
+#include "pathspec.h"
+#include "trace2.h"
+
+static void set_index_entry(struct index_state *istate, int nr, struct cache_entry *ce)
+{
+	ALLOC_GROW(istate->cache, nr + 1, istate->cache_alloc);
+
+	istate->cache[nr] = ce;
+	add_name_hash(istate, ce);
+}
+
+static int add_path_to_index(const struct object_id *oid,
+				struct strbuf *base, const char *path,
+				unsigned int mode, int stage, void *context)
+{
+	struct index_state *istate = (struct index_state *)context;
+	struct cache_entry *ce;
+	size_t len = base->len;
+
+	if (S_ISDIR(mode))
+		return READ_TREE_RECURSIVE;
+
+	strbuf_addstr(base, path);
+
+	ce = make_cache_entry(istate, mode, oid, base->buf, 0, 0);
+	ce->ce_flags |= CE_SKIP_WORKTREE;
+	set_index_entry(istate, istate->cache_nr++, ce);
+
+	strbuf_setlen(base, len);
+	return 0;
+}
 
 void ensure_full_index(struct index_state *istate)
 {
-	/* intentionally left blank */
+	int i;
+	struct index_state *full;
+
+	if (!istate || !istate->sparse_index)
+		return;
+
+	if (!istate->repo)
+		istate->repo = the_repository;
+
+	trace2_region_enter("index", "ensure_full_index", istate->repo);
+
+	/* initialize basics of new index */
+	full = xcalloc(1, sizeof(struct index_state));
+	memcpy(full, istate, sizeof(struct index_state));
+
+	/* then change the necessary things */
+	full->sparse_index = 0;
+	full->cache_alloc = (3 * istate->cache_alloc) / 2;
+	full->cache_nr = 0;
+	ALLOC_ARRAY(full->cache, full->cache_alloc);
+
+	for (i = 0; i < istate->cache_nr; i++) {
+		struct cache_entry *ce = istate->cache[i];
+		struct tree *tree;
+		struct pathspec ps;
+
+		if (!S_ISSPARSEDIR(ce)) {
+			set_index_entry(full, full->cache_nr++, ce);
+			continue;
+		}
+		if (!(ce->ce_flags & CE_SKIP_WORKTREE))
+			warning(_("index entry is a directory, but not sparse (%08x)"),
+				ce->ce_flags);
+
+		/* recursively walk into cd->name */
+		tree = lookup_tree(istate->repo, &ce->oid);
+
+		memset(&ps, 0, sizeof(ps));
+		ps.recursive = 1;
+		ps.has_wildcard = 1;
+		ps.max_depth = -1;
+
+		read_tree_recursive(istate->repo, tree,
+				    ce->name, strlen(ce->name),
+				    0, &ps,
+				    add_path_to_index, full);
+
+		/* free directory entries. full entries are re-used */
+		discard_cache_entry(ce);
+	}
+
+	/* Copy back into original index. */
+	memcpy(&istate->name_hash, &full->name_hash, sizeof(full->name_hash));
+	istate->sparse_index = 0;
+	istate->cache = full->cache;
+	istate->cache_nr = full->cache_nr;
+	istate->cache_alloc = full->cache_alloc;
+
+	free(full);
+
+	trace2_region_leave("index", "ensure_full_index", istate->repo);
 }
diff --git a/sparse-index.h b/sparse-index.h
index 8dda92032e2..a2777dcac59 100644
--- a/sparse-index.h
+++ b/sparse-index.h
@@ -3,5 +3,6 @@
 
 struct index_state;
 void ensure_full_index(struct index_state *istate);
+int convert_to_sparse(struct index_state *istate);
 
 #endif
\ No newline at end of file

-- 
gitgitgadget
Previous: Derrick Stolee via GitGitGadgetNext: Elijah Newren
Message 2 of 61 in “[RFC] Sparse Index”
  1. 00/27 [RFC] Sparse IndexDerrick Stolee via GitGitGadget, Jan 25, 2021
  2. 02/27 sparse-index: implement ensure_full_index()Derrick Stolee via GitGitGadget, Jan 25, 2021
  3. Elijah NewrenJan 27, 2021
  4. Derrick StoleeJan 27, 2021
  5. Elijah NewrenJan 27, 2021
  6. Junio C HamanoJan 28, 2021
  7. 01/27 sparse-index: add guard to ensure full indexDerrick Stolee via GitGitGadget, Jan 25, 2021
  8. 09/27 sparse-index: convert from full to sparseDerrick Stolee via GitGitGadget, Jan 25, 2021
  9. Elijah NewrenJan 27, 2021
  10. 08/27 sparse-checkout: hold pattern list in indexDerrick Stolee via GitGitGadget, Jan 25, 2021
  11. Elijah NewrenJan 27, 2021
  12. Derrick StoleeJan 28, 2021
  13. 06/27 test-tool: don't force full indexDerrick Stolee via GitGitGadget, Jan 25, 2021
  14. 12/27 sparse-index: check index conversion happensDerrick Stolee via GitGitGadget, Jan 25, 2021
  15. Elijah NewrenJan 27, 2021
  16. 15/27 [RFC-VERSION] *: ensure full indexDerrick Stolee via GitGitGadget, Jan 25, 2021
  17. Elijah NewrenFeb 1, 2021
  18. Derrick StoleeFeb 1, 2021
  19. 26/27 pathspec: stop calling ensure_full_indexDerrick Stolee via GitGitGadget, Jan 25, 2021
  20. Elijah NewrenFeb 1, 2021
  21. Derrick StoleeFeb 2, 2021
  22. 14/27 sparse-checkout: toggle sparse index from builtinDerrick Stolee via GitGitGadget, Jan 25, 2021
  23. Elijah NewrenJan 27, 2021
  24. Derrick StoleeJan 28, 2021
  25. 19/27 status: skip sparse-checkout percentage with sparse-indexDerrick Stolee via GitGitGadget, Jan 25, 2021
  26. 04/27 test-read-cache: print cache entries with --tableDerrick Stolee via GitGitGadget, Jan 25, 2021
  27. Elijah NewrenJan 27, 2021
  28. 16/27 unpack-trees: make sparse awareDerrick Stolee via GitGitGadget, Jan 25, 2021
  29. Elijah NewrenFeb 1, 2021
  30. Derrick StoleeFeb 9, 2021
  31. 03/27 t1092: compare sparse-checkout to sparse-indexDerrick Stolee via GitGitGadget, Jan 25, 2021
  32. Elijah NewrenJan 27, 2021
  33. Derrick StoleeJan 27, 2021
  34. Elijah NewrenJan 27, 2021
  35. 27/27 cache-tree: integrate with sparse directory entriesDerrick Stolee via GitGitGadget, Jan 25, 2021
  36. Elijah NewrenFeb 1, 2021
  37. Derrick StoleeFeb 2, 2021
  38. Elijah NewrenFeb 2, 2021
  39. 18/27 status: use sparse-index throughoutDerrick Stolee via GitGitGadget, Jan 25, 2021
  40. 22/27 add: allow operating on a sparse-only indexDerrick Stolee via GitGitGadget, Jan 25, 2021
  41. Elijah NewrenFeb 1, 2021
  42. 20/27 sparse-index: expand_to_path() trivial implementationDerrick Stolee via GitGitGadget, Jan 25, 2021
  43. 21/27 sparse-index: expand_to_path no-op if path existsDerrick Stolee via GitGitGadget, Jan 25, 2021
  44. Elijah NewrenFeb 1, 2021
  45. 10/27 submodule: sparse-index should not collapse linksDerrick Stolee via GitGitGadget, Jan 25, 2021
  46. 17/27 dir.c: accept a directory as part of cone-mode patternsDerrick Stolee via GitGitGadget, Jan 25, 2021
  47. Elijah NewrenFeb 1, 2021
  48. 25/27 fsmonitor: disable if index is sparseDerrick Stolee via GitGitGadget, Jan 25, 2021
  49. 13/27 sparse-index: create extension for compatibilityDerrick Stolee via GitGitGadget, Jan 25, 2021
  50. Elijah NewrenJan 27, 2021
  51. 07/27 unpack-trees: ensure full indexDerrick Stolee via GitGitGadget, Jan 25, 2021
  52. Elijah NewrenJan 27, 2021
  53. 24/27 dir: use expand_to_path in add_patterns()Derrick Stolee via GitGitGadget, Jan 25, 2021
  54. Elijah NewrenFeb 1, 2021
  55. 05/27 test-tool: read-cache --table --no-statDerrick Stolee via GitGitGadget, Jan 25, 2021
  56. 11/27 unpack-trees: allow sparse directoriesDerrick Stolee via GitGitGadget, Jan 25, 2021
  57. Elijah NewrenJan 27, 2021
  58. 23/27 submodule: die_path_inside_submodule is sparse awareDerrick Stolee via GitGitGadget, Jan 25, 2021
  59. Junio C HamanoJan 25, 2021
  60. Derrick StoleeJan 25, 2021
  61. Elijah NewrenFeb 2, 2021

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.