Re: [PATCH v2 00/25] Sparse Index: API protections

>
> Here is the second patch series submission coming out of the sparse-index
> RFC [1].
>
> [1]
> https://lore.kernel.org/git/pull.847.git.1611596533.gitgitgadget@gmail.com/
>
> This is based on v3 of the format series [2].
>
> [2]
> https://lore.kernel.org/git/pull.883.v3.git.1615912983.gitgitgadget@gmail.com/
>
> The point of this series is to insert protections for the consumers of the
> in-memory index to avoid unintended behavior change when using a sparse
> index versus a full one.
>
> We mark certain regions of code as needing a full index, so we call
> ensure_full_index() to expand a sparse index to a full one, if necessary.
> These protections are inserted file-by-file in every loop over all cache
> entries. Well, "most" loops, because some are going to be handled in the
> very next series so I leave them out.
>
> Many callers use index_name_pos() to find a path by name. In these cases, we
> can check if that position resolves to a sparse directory instance. In those
> cases, we just expand to a full index and run the search again.
>
> The last few patches deal with the name-hash hashtable for doing O(1)
> lookups.
>
> These protections don't do much right now, since the previous series created
> the_repository->settings.command_requires_full_index to guard all index
> reads and writes to ensure the in-memory copy is full for commands that have
> not been tested with the sparse index yet.
>
> However, after this series is complete, we now have a straight-forward plan
> for making commands "sparse aware" one-by-one:
>
>  1. Disable settings.command_requires_full_index to allow an in-memory
>     sparse-index.
>  2. Run versions of that command under a debugger, breaking on
>     ensure_full_index().
>  3. Examine the call stack to determine the context of that expansion, then
>     implement the proper behavior in those locations.
>  4. Add tests to ensure we are checking this logic in the presence of sparse
>     directory entries.
>
> I will admit that mostly it is the writing of the test cases that takes the
> most time in the conversions I've done so far.
>
>
> Updates in v2
> =============
>
>  * Rebased onto v5 of ds/sparse-index
>  * Updated the technical doc to describe how these protections are guards to
>    keep behavior consistent between a sparse-index and a full index. Whether
>    or not that behavior is "correct" can be interrogated later.
>  * Calls to ensure_full_index() are marked with a TODO comment saying these
>    calls should be audited later (with tests).
>  * Fixed an incorrectly squashed commit message.
>  * Dropped the diff-lib.c commit because it was erroneously included in v2.
>  * Dropped the merge-ort.c commit because of conflicts with work in flight
>    and a quick audit that it is not needed.
>  * I reviewed the merge of this topic with mt/add-rm-in-sparse-checkout and
>    found it equivalent to what I would have done.

> Thanks, -Stolee
>
> Derrick Stolee (25):
>   sparse-index: API protection strategy
>   *: remove 'const' qualifier for struct index_state
>   read-cache: expand on query into sparse-directory entry
>   cache: move ensure_full_index() to cache.h
>   add: ensure full index
>   checkout-index: ensure full index
>   checkout: ensure full index
>   commit: ensure full index
>   difftool: ensure full index
>   fsck: ensure full index
>   grep: ensure full index
>   ls-files: ensure full index
>   merge-index: ensure full index
>   rm: ensure full index
>   stash: ensure full index
>   update-index: ensure full index
>   dir: ensure full index
>   entry: ensure full index
>   merge-recursive: ensure full index
>   pathspec: ensure full index
>   read-cache: ensure full index
>   resolve-undo: ensure full index
>   revision: ensure full index
>   sparse-index: expand_to_path()
>   name-hash: use expand_to_path()
>
>  Documentation/technical/sparse-index.txt | 37 +++++++++++-
>  attr.c                                   | 14 ++---
>  attr.h                                   |  4 +-
>  builtin/add.c                            |  2 +
>  builtin/checkout-index.c                 |  2 +
>  builtin/checkout.c                       |  5 ++
>  builtin/commit.c                         |  4 ++
>  builtin/difftool.c                       |  3 +
>  builtin/fsck.c                           |  2 +
>  builtin/grep.c                           |  2 +
>  builtin/ls-files.c                       | 14 +++--
>  builtin/merge-index.c                    |  5 ++
>  builtin/rm.c                             |  2 +
>  builtin/stash.c                          |  2 +
>  builtin/update-index.c                   |  2 +
>  cache.h                                  |  7 ++-
>  convert.c                                | 26 ++++-----
>  convert.h                                | 20 +++----
>  dir.c                                    | 14 +++--
>  dir.h                                    |  8 +--
>  entry.c                                  |  2 +
>  merge-recursive.c                        |  4 +-
>  name-hash.c                              | 10 ++++
>  pathspec.c                               |  8 ++-
>  pathspec.h                               |  6 +-
>  read-cache.c                             | 35 ++++++++++--
>  resolve-undo.c                           |  4 ++
>  revision.c                               |  2 +
>  sparse-index.c                           | 72 ++++++++++++++++++++++++
>  sparse-index.h                           | 14 ++++-
>  submodule.c                              |  6 +-
>  submodule.h                              |  6 +-
>  32 files changed, 273 insertions(+), 71 deletions(-)
>
>
> base-commit: 66602733cc95d9a53594520cd8b28d3338e258ea
> Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-906%2Fderrickstolee%2Fsparse-index%2Fprotections-v2
> Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-906/derrickstolee/sparse-index/protections-v2
> Pull-Request: https://github.com/gitgitgadget/git/pull/906
>
> Range-diff vs v1:
>
>   3:  bbf19f8a2be5 !  1:  7484e085e342 sparse-index: API protection strategy
>      @@ Commit message
>           Looking for non-zero stage:
>           * builtin/add.c:chmod_pathspec()
>           * builtin/merge.c:count_unmerged_entries()
>      +    * merge-ort.c:record_conflicted_index_entries()
>           * read-cache.c:unmerged_index()
>           * rerere.c:check_one_conflict(), find_conflict(), rerere_remaining()
>           * revision.c:prepare_show_merge()
>      @@ Commit message
>           Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
>
>        ## Documentation/technical/sparse-index.txt ##
>      -@@ Documentation/technical/sparse-index.txt: also introduce other features that have been considered for improving the
>      - index, as well.
>      +@@ Documentation/technical/sparse-index.txt: index, as well.
>
>        Next, consumers of the index will be guarded against operating on a
>      --sparse-index by inserting calls to `ensure_full_index()` or
>      + sparse-index by inserting calls to `ensure_full_index()` or
>       -`expand_index_to_path()`. After these guards are in place, we can begin
>       -leaving sparse-directory entries in the in-memory index structure.
>      -+sparse-index by inserting calls to `ensure_full_index()` before iterating
>      -+over all cache entries. If a specific path is requested, then those will
>      ++`expand_index_to_path()`. If a specific path is requested, then those will
>       +be protected from within the `index_file_exists()` and `index_name_pos()`
>      -+API calls: they will call `ensure_full_index()` if necessary.
>      ++API calls: they will call `ensure_full_index()` if necessary. The
>      ++intention here is to preserve existing behavior when interacting with a
>      ++sparse-checkout. We don't want a change to happen by accident, without
>      ++tests. Many of these locations may not need any change before removing the
>      ++guards, but we should not do so without tests to ensure the expected
>      ++behavior happens.
>      ++
>      ++It may be desirable to _change_ the behavior of some commands in the
>      ++presence of a sparse index or more generally in any sparse-checkout
>      ++scenario. In such cases, these should be carefully communicated and
>      ++tested. No such behavior changes are intended during this phase.
>       +
>       +During a scan of the codebase, not every iteration of the cache entries
>       +needs an `ensure_full_index()` check. The basic reasons include:
>      @@ Documentation/technical/sparse-index.txt: also introduce other features that hav
>       +
>       +6. The sparse-index is disabled at this point when using the split-index
>       +   feature, so no effort is made to protect the split-index API.
>      -+
>      -+After these guards are in place, we can begin leaving sparse-directory
>      -+entries in the in-memory index structure.
>
>        Even after inserting these guards, we will keep expanding sparse-indexes
>        for most Git commands using the `command_requires_full_index` repository
>   1:  628e16dd3fc7 =  2:  098b2c9ef352 *: remove 'const' qualifier for struct index_state
>   2:  8e11e8917019 =  3:  737d27e18d64 read-cache: expand on query into sparse-directory entry
>   4:  7e4079c48eb2 =  4:  db5c100f3e2b cache: move ensure_full_index() to cache.h
>   5:  142df1ab8e3e !  5:  4a5fc2eb5a9f add: ensure full index
>      @@ builtin/add.c: static int renormalize_tracked_files(const struct pathspec *paths
>        {
>         int i, retval = 0;
>
>      ++ /* TODO: audit for interaction with sparse-index. */
>       + ensure_full_index(&the_index);
>         for (i = 0; i < active_nr; i++) {
>                 struct cache_entry *ce = active_cache[i];
>   6:  bfa0164cc3c1 !  6:  11c38f7277c5 checkout-index: ensure full index
>      @@ builtin/checkout-index.c: static void checkout_all(const char *prefix, int prefi
>         int i, errs = 0;
>         struct cache_entry *last_ce = NULL;
>
>      ++ /* TODO: audit for interaction with sparse-index. */
>       + ensure_full_index(&the_index);
>         for (i = 0; i < active_nr ; i++) {
>                 struct cache_entry *ce = active_cache[i];
>   7:  1bb7b6117e41 !  7:  fd04adbb3f79 checkout: ensure full index
>      @@ builtin/checkout.c: static int checkout_worktree(const struct checkout_opts *opt
>                                NULL);
>
>         enable_delayed_checkout(&state);
>      ++
>      ++ /* TODO: audit for interaction with sparse-index. */
>       + ensure_full_index(&the_index);
>         for (pos = 0; pos < active_nr; pos++) {
>                 struct cache_entry *ce = active_cache[pos];
>      @@ builtin/checkout.c: static int checkout_paths(const struct checkout_opts *opts,
>          * Make sure all pathspecs participated in locating the paths
>          * to be checked out.
>          */
>      ++ /* TODO: audit for interaction with sparse-index. */
>       + ensure_full_index(&the_index);
>         for (pos = 0; pos < active_nr; pos++)
>                 if (opts->overlay_mode)
>   8:  a59e45c4ae8f !  8:  65704f39edc9 commit: ensure full index
>      @@ builtin/commit.c: static int list_paths(struct string_list *list, const char *wi
>                 free(max_prefix);
>         }
>
>      ++ /* TODO: audit for interaction with sparse-index. */
>       + ensure_full_index(&the_index);
>         for (i = 0; i < active_nr; i++) {
>                 const struct cache_entry *ce = active_cache[i];
>      @@ builtin/commit.c: static int prepare_to_commit(const char *index_file, const cha
>                 if (get_oid(parent, &oid)) {
>                         int i, ita_nr = 0;
>
>      ++                 /* TODO: audit for interaction with sparse-index. */
>       +                 ensure_full_index(&the_index);
>                         for (i = 0; i < active_nr; i++)
>                                 if (ce_intent_to_add(active_cache[i]))
>   9:  83040e7558f3 !  9:  739f3fe9edf2 difftool: ensure full index
>      @@ builtin/difftool.c: static int run_dir_diff(const char *extcmd, int symlinks, co
>                 setenv("GIT_DIFFTOOL_DIRDIFF", "true", 1);
>         rc = run_command_v_opt(helper_argv, flags);
>
>      ++ /* TODO: audit for interaction with sparse-index. */
>       + ensure_full_index(&wtindex);
>       +
>         /*
>  10:  988f7bd2d736 ! 10:  779a86ad1ec4 fsck: ensure full index
>      @@ builtin/fsck.c: int cmd_fsck(int argc, const char **argv, const char *prefix)
>                 verify_index_checksum = 1;
>                 verify_ce_order = 1;
>                 read_cache();
>      ++         /* TODO: audit for interaction with sparse-index. */
>       +         ensure_full_index(&the_index);
>                 for (i = 0; i < active_nr; i++) {
>                         unsigned int mode;
>  11:  abe189051a0c ! 11:  8c0d377054fa grep: ensure full index
>      @@ builtin/grep.c: static int grep_cache(struct grep_opt *opt,
>         if (repo_read_index(repo) < 0)
>                 die(_("index file corrupt"));
>
>      ++ /* TODO: audit for interaction with sparse-index. */
>       + ensure_full_index(repo->index);
>         for (nr = 0; nr < repo->index->cache_nr; nr++) {
>                 const struct cache_entry *ce = repo->index->cache[nr];
>  12:  00c8a7e1d119 ! 12:  beaa1467cabb ls-files: ensure full index
>      @@ builtin/ls-files.c: static void show_files(struct repository *repo, struct dir_s
>
>         if (!(show_cached || show_stage || show_deleted || show_modified))
>                 return;
>      ++ /* TODO: audit for interaction with sparse-index. */
>       + ensure_full_index(repo->index);
>         for (i = 0; i < repo->index->cache_nr; i++) {
>                 const struct cache_entry *ce = repo->index->cache[i];
>      @@ builtin/ls-files.c: void overlay_tree_on_index(struct index_state *istate,
>                 die("bad tree-ish %s", tree_name);
>
>         /* Hoist the unmerged entries up to stage #3 to make room */
>      ++ /* TODO: audit for interaction with sparse-index. */
>       + ensure_full_index(istate);
>         for (i = 0; i < istate->cache_nr; i++) {
>                 struct cache_entry *ce = istate->cache[i];
>  13:  1288f02177d2 ! 13:  73684141fcff merge-index: ensure full index
>      @@ builtin/merge-index.c: static void merge_one_path(const char *path)
>        static void merge_all(void)
>        {
>         int i;
>      ++ /* TODO: audit for interaction with sparse-index. */
>       + ensure_full_index(&the_index);
>         for (i = 0; i < active_nr; i++) {
>                 const struct cache_entry *ce = active_cache[i];
>      @@ builtin/merge-index.c: int cmd_merge_index(int argc, const char **argv, const ch
>
>         read_cache();
>
>      ++ /* TODO: audit for interaction with sparse-index. */
>       + ensure_full_index(&the_index);
>       +
>         i = 1;
>  14:  d6816560b32f ! 14:  6ea81a49c6b5 rm: ensure full index
>      @@ builtin/rm.c: int cmd_rm(int argc, const char **argv, const char *prefix)
>
>         seen = xcalloc(pathspec.nr, 1);
>
>      ++ /* TODO: audit for interaction with sparse-index. */
>       + ensure_full_index(&the_index);
>         for (i = 0; i < active_nr; i++) {
>                 const struct cache_entry *ce = active_cache[i];
>  15:  92ccd31dd343 ! 15:  49ca5ed05c8d sparse-checkout: ensure full index
>      @@ Metadata
>       Author: Derrick Stolee <dstolee@microsoft.com>
>
>        ## Commit message ##
>      -    sparse-checkout: ensure full index
>      +    stash: ensure full index
>
>      -    When adjusting the sparse-checkout definition, ensure that a sparse
>      -    index is expanded to a full one to avoid unexpected behavior. This is a
>      -    top candidate for later integration with the sparse-index, but requires
>      -    careful testing.
>      +    Before iterating over all cache entries, ensure that a sparse index is
>      +    expanded to a full index to avoid unexpected behavior.
>
>           Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
>
>      @@ builtin/stash.c: static int do_push_stash(const struct pathspec *ps, const char
>                 int i;
>                 char *ps_matched = xcalloc(ps->nr, 1);
>
>      ++         /* TODO: audit for interaction with sparse-index. */
>       +         ensure_full_index(&the_index);
>                 for (i = 0; i < active_nr; i++)
>                         ce_path_match(&the_index, active_cache[i], ps,
>  16:  796449758a08 ! 16:  9c4bb187c15d update-index: ensure full index
>      @@ builtin/update-index.c: static int do_reupdate(int ac, const char **av,
>                  */
>                 has_head = 0;
>         redo:
>      ++ /* TODO: audit for interaction with sparse-index. */
>       + ensure_full_index(&the_index);
>         for (pos = 0; pos < active_nr; pos++) {
>                 const struct cache_entry *ce = active_cache[pos];
>  17:  45bbed6150a2 <  -:  ------------ diff-lib: ensure full index
>  18:  8ce1f80985a4 ! 17:  fae4c078c3ef dir: ensure full index
>      @@ dir.c: static void connect_wt_gitdir_in_nested(const char *sub_worktree,
>         if (repo_read_index(&subrepo) < 0)
>                 die(_("index file corrupt in repo %s"), subrepo.gitdir);
>
>      ++ /* TODO: audit for interaction with sparse-index. */
>       + ensure_full_index(subrepo.index);
>         for (i = 0; i < subrepo.index->cache_nr; i++) {
>                 const struct cache_entry *ce = subrepo.index->cache[i];
>  19:  6e0b452f44c1 ! 18:  2b9180ee77d3 entry: ensure full index
>      @@ entry.c: static void mark_colliding_entries(const struct checkout *state,
>
>         ce->ce_flags |= CE_MATCHED;
>
>      ++ /* TODO: audit for interaction with sparse-index. */
>       + ensure_full_index(state->istate);
>         for (i = 0; i < state->istate->cache_nr; i++) {
>                 struct cache_entry *dup = state->istate->cache[i];
>  20:  fb4c7038b746 <  -:  ------------ merge-ort: ensure full index
>  21:  57d59825627f ! 19:  1e3f6085a405 merge-recursive: ensure full index
>      @@ merge-recursive.c: static struct string_list *get_unmerged(struct index_state *i
>
>         unmerged->strdup_strings = 1;
>
>      ++ /* TODO: audit for interaction with sparse-index. */
>       + ensure_full_index(istate);
>         for (i = 0; i < istate->cache_nr; i++) {
>                 struct string_list_item *item;
>  22:  f4c470686b27 ! 20:  e62a597a9725 pathspec: ensure full index
>      @@ pathspec.c: void add_pathspec_matches_against_index(const struct pathspec *paths
>                         num_unmatched++;
>         if (!num_unmatched)
>                 return;
>      ++ /* TODO: audit for interaction with sparse-index. */
>       + ensure_full_index(istate);
>         for (i = 0; i < istate->cache_nr; i++) {
>                 const struct cache_entry *ce = istate->cache[i];
>  23:  81519782d4b2 ! 21:  ebfffdbdd6ad read-cache: ensure full index
>      @@ read-cache.c: int refresh_index(struct index_state *istate, unsigned int flags,
>          */
>         preload_index(istate, pathspec, 0);
>         trace2_region_enter("index", "refresh", NULL);
>      ++ /* TODO: audit for interaction with sparse-index. */
>       + ensure_full_index(istate);
>         for (i = 0; i < istate->cache_nr; i++) {
>                 struct cache_entry *ce, *new_entry;
>      @@ read-cache.c: int repo_index_has_changes(struct repository *repo,
>                 diff_flush(&opt);
>                 return opt.flags.has_changes != 0;
>         } else {
>      ++         /* TODO: audit for interaction with sparse-index. */
>       +         ensure_full_index(istate);
>                 for (i = 0; sb && i < istate->cache_nr; i++) {
>                         if (i)
>  24:  39e8bea0c1ca ! 22:  495b07a87973 resolve-undo: ensure full index
>      @@ resolve-undo.c: void unmerge_marked_index(struct index_state *istate)
>         if (!istate->resolve_undo)
>                 return;
>
>      ++ /* TODO: audit for interaction with sparse-index. */
>       + ensure_full_index(istate);
>         for (i = 0; i < istate->cache_nr; i++) {
>                 const struct cache_entry *ce = istate->cache[i];
>      @@ resolve-undo.c: void unmerge_index(struct index_state *istate, const struct path
>         if (!istate->resolve_undo)
>                 return;
>
>      ++ /* TODO: audit for interaction with sparse-index. */
>       + ensure_full_index(istate);
>         for (i = 0; i < istate->cache_nr; i++) {
>                 const struct cache_entry *ce = istate->cache[i];
>  25:  6abb1813ae10 ! 23:  3144114d1a75 revision: ensure full index
>      @@ revision.c: static void do_add_index_objects_to_pending(struct rev_info *revs,
>        {
>         int i;
>
>      ++ /* TODO: audit for interaction with sparse-index. */
>       + ensure_full_index(istate);
>         for (i = 0; i < istate->cache_nr; i++) {
>                 struct cache_entry *ce = istate->cache[i];
>  26:  1690d33c11e0 = 24:  d52c72b4a7b9 sparse-index: expand_to_path()
>  27:  40cfc59f695a = 25:  7e2d3fae9a2a name-hash: use expand_to_path()
>
> --
> gitgitgadget