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

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

From
Elijah Newren <newren@gmail.com>
Date
Jan 27, 2021, 03:05 UTC
Message-ID
<CABPp-BE3tLmfwyncbdTKZUgLYH_8M9zMjH=+LJG4bdGcbYDPMg@mail.gmail.com>
In-Reply-To
<ebbe8569dcc16f2ae235c4167be0e72a53982982.1611596534.git.gitgitgadget@gmail.com>

On Mon, Jan 25, 2021 at 9:42 AM Derrick Stolee via GitGitGadget <gitgitgadget@gmail.com> wrote:

Show 19 quoted lines
>
> 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

This is a weird number. What's the reason for choosing it? It looks deceptively close to 0100755, normal executable files, but has the extra 0, meaning that ce->ce_mode & S_IFMT is 0, suggesting it has no file type.

Since it's a directory, why not use S_IFDIR (040000)?

(GITLINK does use the weird 0160000 value, but it happens to be S_IFLNK | S_IFDIR == 0120000 | 040000, which conveys "it's both a directory and a symlink")

>  2. ce->flags & CE_SKIP_WORKTREE is true
Makes sense.
>  3. ce->name[ce->namelen - 1] == '/' (ends in dir separator)

Is there a particular reason for this? I'm used to seeing names without the trailing slash, both in the index and in tree objects. I don't know enough to be for or against this idea; just curious at this point.

>  4. ce->oid references a tree object.
Makes sense...but doesn't that suggest we'd want to use ce->ce_mode = 040000?

Also, as a bit of a side comment: There have been other requests in the past to support directory objects in the index. The only use I remember for them requested from others was to allow tracking empty directories. However, I've long wanted to introduce a new "blobtree" object to git, so that a user can "git add" some big binary file, but internally git splits the binary file up and stores it as multiple blobs within git plus a new "blobtree" object that references all the individual blobs with enough information about how to stitch all the blobs together to get the original file. I had a few different forms of "blobtree" things that I was interested in. I think brian once suggested some similar idea.

Show 22 quoted lines
> 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

Another magic value. Feels like the commit message should reference this one and why it was picked. Seems odd to me, and possibly problematic to re-use file permission bits that might collide with files recorded by really old versions of git. Maybe that's not a concern, though.

> +#define S_ISSPARSEDIR(m) ((m)->ce_mode == CE_MODE_SPARSE_DIRECTORY)

Should the special sauce apply to ce_flags rather than ce_mode? Thus, instead of an S_ISSPARSEDIR, perhaps have a ce_sparse_dir macro (similar to ce_skip_worktree) based on a CE_SPARSE_DIR value (similar to CE_SKIP_WORKTREE)?

Or, alternatively, do we need a single special state here? Could we check for a combination of ce_mode == 040000 && ce_skip_worktree(ce)?

Show 158 quoted lines
> +
>  /* 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;
Haven't you leaked the original istate->cache here?
Show 16 quoted lines
> +       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);

Seems logically that you'd add one, but was this meant to be included in a later patch?

Show 6 quoted lines
>
>  #endif
> \ No newline at end of file
> --
> gitgitgadget
>
Previous: Derrick Stolee via GitGitGadgetNext: Derrick Stolee
Message 3 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.