patch, 5 partsRemove the present-despite-SKIP_WORKTREE class of bugs (for sparse-checkouts)

(Maintainer note: This series builds on (v2 of) vd/sparse-clean-etc, because it tweaks one of the testcases added there.)

(Note 2: There was a previous RFC round of this series at https://lore.kernel.org/git/20220109045732.2497526-1-newren@gmail.com/.)

Files in the present-despite-SKIP_WORKTREE state have caused no ends of discussions and bugs[1,2,3,4,5,6,...and lots of others]. Trying to address the big issue of discovering & recovering from this state has befuddled me for over a year because I was worried we'd need additional code at every skip_worktree-checking path in the code (and they are all over the place), and that we'd make the code significantly slower unless we plumbed a bunch of additional information all over the place to allow some reasonable optimizations.

This series tries to solve the problem a bit differently by automatic early discovery and recovery; as it result, it greatly simplifies the landscape, reduces our testing matrix burden, and fixes a large swath of bugs. And I figured out how to get the perf cost down to essentially negligible.

Changes since RFC version:

 * updated the commit messages as per suggestions from Victoria, including
   adding performance measurements
 * renamed the new function to use a clearer name
 * replaced the final patch with a different optimization, which is both
   simpler and performs quite a bit better (the cost for my previous patch 5
   was already decent in many cases, but had a few cases where the cost was
   significant).

Quick overview:

 * Patches 1 & 2 add a test to demonstrate accidental deletion of
   possibly-modified files, and then fix the bug.
 * Patch 3 is the crux of this series; a small amount of code with a huge
   commit message
 * Patch 4 updates the documentation
 * Patch 5 adds an optimization to reduce the performance impact of patch 3

[1] https://lore.kernel.org/git/CABPp-BFnFpzwGC11TLoLs8YK5yiisA5D5-fFjXnJsbESVDwZsA@mail.gmail.com/ [2] https://lore.kernel.org/git/CABPp-BGJ_Nvi5TmgriD9Bh6eNXE2EDq2f8e8QKXAeYG3BxZafA@mail.gmail.com/ [3] https://lore.kernel.org/git/pull.809.git.git.1592356884310.gitgitgadget@gmail.com/ [4] commit 66b209b ("merge-ort: implement CE_SKIP_WORKTREE handling with conflicted entries", 2021-03-20) [5] commit ba359fd ("stash: fix stash application in sparse-checkouts", 2020-12-01) [6] https://lore.kernel.org/git/CABPp-BH9tju7WVm=QZDOvaMDdZbpNXrVWQdN-jmfN8wC6YVhmw@mail.gmail.com/

Elijah Newren (5):
  t1011: add testcase demonstrating accidental loss of user
    modifications
  unpack-trees: fix accidental loss of user changes
  repo_read_index: clear SKIP_WORKTREE bit from files present in
    worktree
  Update documentation related to sparsity and the skip-worktree bit
  Accelerate clear_skip_worktree_from_present_files() by caching

 Documentation/git-read-tree.txt          | 12 +++-
 Documentation/git-sparse-checkout.txt    | 76 ++++++++++++++----------
 Documentation/git-update-index.txt       | 57 +++++++++++++-----
 repository.c                             |  7 +++
 sparse-index.c                           | 73 +++++++++++++++++++++++
 sparse-index.h                           |  1 +
 t/t1011-read-tree-sparse-checkout.sh     | 23 ++++++-
 t/t1092-sparse-checkout-compatibility.sh | 16 ++---
 t/t3705-add-sparse-checkout.sh           |  2 +
 t/t6428-merge-conflicts-sparse.sh        | 23 ++-----
 t/t7012-skip-worktree-writing.sh         | 44 +++-----------
 t/t7817-grep-sparse-checkout.sh          | 11 +++-
 unpack-trees.c                           |  4 +-
 13 files changed, 235 insertions(+), 114 deletions(-)

base-commit: 80697e9259e4a2c12fd0546f5f1895fb3068a66c
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1114%2Fnewren%2Ffix-present-despite-skip-worktree-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1114/newren/fix-present-despite-skip-worktree-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/1114

From: Elijah Newren <newren@gmail.com>

If a user has a file with local modifications that is not marked as SKIP_WORKTREE, but the sparsity patterns are such that it should be marked that way, and the user then invokes a command like

   * git checkout -q HEAD^

or

   * git read-tree -mu HEAD^

Then the file will be deleted along with all the users' modifications. Add a testcase demonstrating this problem.

Note: This bug only triggers if something other than 'HEAD' is given;
if the commands above had specified 'HEAD', then the users' file would
be left alone.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 t/t1011-read-tree-sparse-checkout.sh | 21 +++++++++++++++++++++
 1 file changed, 21 insertions(+)

From: Elijah Newren <newren@gmail.com>

For sparse-checkouts, we don't want unpack-trees to error out on files that are missing from the worktree, so there has traditionally been logic to make it skip the verify_uptodate() check for these. Unfortunately, it was skipping the verify_uptodate() check for files that were expected to *become* SKIP_WORKTREE. For files that were not already SKIP_WORKTREE, that can cause us to later delete the file in apply_sparse_checkout(). Only skip the check for files that were already SKIP_WORKTREE as well to avoid lightly discarding important changes users may have made to files.

Note 1: unpack-trees.c is already a bit complex, and the logic around CE_SKIP_WORKTREE and CE_NEW_SKIP_WORKTREE in that file are no exception. I also tried just replacing CE_NEW_SKIP_WORKTREE with CE_SKIP_WORKTREE in the verify_uptodate() check instead of checking for both flags, and found that it also fixed this bug and passed all the tests. I also attempted to devise a few testcases that might trip either variant of my fix and was unable to find any problems. It may be that just checking CE_SKIP_WORKTREE is a better fix, but I'm not sure. I thought it was a bit safer to strictly reduce the number of cases where we skip the up-to-date check rather than just toggling which kind of cases skip it, and thus went with the current variant of the fix.

Note 2: I also wondered if verify_absent() might have a similar bug, but despite my attempts to try to devise a testcase that would trigger such a thing, I couldn't find any problematic testcases. Thus, this patch makes no attempt to apply similar changes to verify_absent() and verify_absent_if_directory().

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 t/t1011-read-tree-sparse-checkout.sh | 2 +-
 unpack-trees.c                       | 4 +++-
 2 files changed, 4 insertions(+), 2 deletions(-)

From: Elijah Newren <newren@gmail.com>

The fix is short (~30 lines), but the description is not.  Sorry.

There is a set of problems caused by files in what I'll refer to as the "present-despite-SKIP_WORKTREE" state. This commit aims to not just fix these problems, but remove the entire class as a possibility -- for those using sparse checkouts. But first, we need to understand the problems this class presents. A quick outline:

   * Problems
     * User facing issues
     * Problem space complexity
     * Maintenance and code correctness challenges
   * SKIP_WORKTREE expectations in Git
   * Suggested solution
   * Pros/Cons of suggested solution
   * Notes on testcase modifications

=== User facing issues ===

There are various ways for users to get files to be present in the
working copy despite having the SKIP_WORKTREE bit set for that file in
the index.  This may come from:
  * various git commands not really supporting the SKIP_WORKTREE bit[1,2]
  * users grabbing files from elsewhere and writing them to the worktree
    (perhaps even cached in their editor)
  * users attempting to "abort" a sparse-checkout operation with a
    not-so-early Ctrl+C (updating $GIT_DIR/info/sparse-checkout and the
    working tree is not atomic)[3].

Once users have present-despite-SKIP_WORKTREE files, any modifications users make to these files will be ignored, possibly to users' confusion.

Further:
  * these files will degrade performance for the sparse-index case due
    to requiring the index to be expanded (see commit 55dfcf9591
    ("sparse-checkout: clear tracked sparse dirs", 2021-09-08) for why
    we try to delete entire directories outside the sparse cone).
  * these files will not be updated by by standard commands
    (switch/checkout/pull/merge/rebase will leave them alone unless
    conflicts happen -- and even then, the conflicted file may be
    written somewhere else to avoid overwriting the SKIP_WORKTREE file
    that is present and in the way)
  * there is nothing in Git that users can use to discover such
    files (status, diff, grep, etc. all ignore it)
  * there is no reasonable mechanism to "recover" from such a condition
    (neither `git sparse-checkout reapply` nor `git reset --hard` will
    correct it).

So, not only are users modifications ignored, but the files get progressively more stale over time. At some point in the future, they may change their sparseness specification or disable sparse-checkouts. At that time, all present-despite-SKIP_WORKTREE files will show up as having lots of modifications because they represent a version from a different branch or commit. These might include user-made local changes from days before, but the only way to tell is to have users look through them all closely.

If these users come to others for help, there will be no logs that explain the issue; it's just a mysterious list of changes. Users might adamantly claim (correctly, as it turns out) that they didn't modify these files, while others presume they did.

[1] https://lore.kernel.org/git/xmqqbmb1a7ga.fsf@gitster-ct.c.googlers.com/ [2] https://lore.kernel.org/git/CABPp-BH9tju7WVm=QZDOvaMDdZbpNXrVWQdN-jmfN8wC6YVhmw@mail.gmail.com/ [3] https://lore.kernel.org/git/CABPp-BFnFpzwGC11TLoLs8YK5yiisA5D5-fFjXnJsbESVDwZsA@mail.gmail.com/

=== Problem space complexity ===

SKIP_WORKTREE has been part of Git for over a decade. Duy did lots of work on it initially, and several others have since come along and put lots of work into it. Stolee spent most of 2021 on the sparse-index, with lots of bugfixes along the way including to non-sparse-index cases as we are still trying to get sparse checkouts to behave reasonably. Basically every codepath throughout the treat needs to be aware of an additional type of file: tracked-but-not-present. The extra type results in lots of extra testcases and lots of extra code everywhere.

But, the sad thing is that we actually have more than one extra type. We have tracked, tracked-but-not-present (SKIP_WORKTREE), and tracked-but-promised-to-not-be-present-but-is-present-anyway (present-despite-SKIP_WORKTREE). Two types is a monumental amount of effort to support, and adding a third feels a bit like insanity[4].

[4] Some examples of which can be seen at
    https://lore.kernel.org/git/CABPp-BGJ_Nvi5TmgriD9Bh6eNXE2EDq2f8e8QKXAeYG3BxZafA@mail.gmail.com/

=== Maintenance and code correctness challenges ===

Matheus' patches to grep stalled for nearly a year, in part because of complications of how to handle sparse-checkouts appropriately in all cases[5][6] (with trying to sanely figure out how to sanely handle present-despite-SKIP_WORKTREE files being one of the complications). His rm/add follow-ups also took months because of those kinds of issues[7]. The corner cases with things like submodules and SKIP_WORKTREE with the addition of present-despite-SKIP_WORKTREE start becoming really complex[8].

We've had to add ugly logic to merge-ort to attempt to handle present-despite-SKIP_WORKTREE files[9], and basically just been forced to give up in merge-recursive knowing full well that we'll sometimes silently discard user modifications. Despite stash essentially being a merge, it needed extra code (beyond what was in merge-ort and merge-recursive) to manually tweak SKIP_WORKTREE bits in order to avoid a few different bugs that'd result in an early abort with a partial stash application[10].

[5] See https://lore.kernel.org/git/5f3f7ac77039d41d1692ceae4b0c5df3bb45b74a.1612901326.git.matheus.bernardino@usp.br/#t
    and the dates on the thread; also Matheus and I had several
    conversations off-list trying to resolve the issues over that time
[6] ...it finally kind of got unstuck after
    https://lore.kernel.org/git/CABPp-BGJ_Nvi5TmgriD9Bh6eNXE2EDq2f8e8QKXAeYG3BxZafA@mail.gmail.com/
[7] See for example
    https://lore.kernel.org/git/CABPp-BHwNoVnooqDFPAsZxBT9aR5Dwk5D9sDRCvYSb8akxAJgA@mail.gmail.com/#t
    and quotes like "The core functionality of sparse-checkout has always
    been only partially implemented", a statement I still believe is true
    today.
[8] https://lore.kernel.org/git/pull.809.git.git.1592356884310.gitgitgadget@gmail.com/
[9] See commit 66b209b86a ("merge-ort: implement CE_SKIP_WORKTREE
    handling with conflicted entries", 2021-03-20)
[10] See commit ba359fd507 ("stash: fix stash application in
     sparse-checkouts", 2020-12-01)

=== SKIP_WORKTREE expectations in Git ===

A couple quotes:

From [11] (before the "sparse-checkout" command existed):
   If it needs too many special cases, hacks, and conditionals, then it
   is not worth the complexity---if it is easier to write a correct code
   by allowing Git to populate working tree files, it is perfectly fine
   to do so.

   In a sense, the sparse checkout "feature" itself is a hack by itself,
   and that is why I think this part should be "best effort" as well.

From the git-sparse-checkout manual (still present today):

   THIS COMMAND IS EXPERIMENTAL. ITS BEHAVIOR, AND THE BEHAVIOR OF OTHER
   COMMANDS IN THE PRESENCE OF SPARSE-CHECKOUTS, WILL LIKELY CHANGE IN
   THE FUTURE.

[11] https://lore.kernel.org/git/xmqqbmb1a7ga.fsf@gitster-ct.c.googlers.com/

=== Suggested solution ===

SKIP_WORKTREE was written to allow sparse-checkouts, in particular, as the name of the option implies, to allow the file to NOT be in the worktree but consider it to be unchanged rather than deleted.

The suggests a simple solution: present-despite-SKIP_WORKTREE files should not exist, for those using sparse-checkouts.

Enforce this at index loading time by checking if core.sparseCheckout is true; if so, check files in the index with the SKIP_WORKTREE bit set to verify that they are absent from the working tree. If they are present, unset the bit (in memory, though any commands that write to the index will record the update).

Users can, of course, can get the SKIP_WORKTREE bit back such as by running `git sparse-checkout reapply` (if they have ensured the file is unmodified and doesn't match the specified sparsity patterns).

=== Pros/Cons of suggested solution ===

Pros:

  * Solves the user visible problems reported above, which I've been
    complaining about for nearly a year but couldn't find a solution to.
  * Helps prevent slow performance degradation with a sparse-index.
  * Much easier behavior in sparse-checkouts for users to reason about
  * Very simple, ~30 lines of code.
  * Significantly simplifies some ugly testcases, and obviates the need
    to test an entire class of potential issues.
  * Reduces code complexity, reasoning, and maintenance.  Avoids
    disagreements about weird corner cases[12].
  * It has been reported that some users might be (ab)using
    SKIP_WORKTREE as a let-me-modify-but-keep-the-file-in-the-worktree
    mechanism[13, and a few other similar references].  These users know
    of multiple caveats and shortcomings in doing so; perhaps not
    surprising given the "SKIP_WORKTREE expecations" section above.
    However, these users use `git update-index --skip-worktree`, and not
    `git sparse-checkout` or core.sparseCheckout=true.  As such, these
    users would be unaffected by this change and can continue abusing
    the system as before.

[12] https://lore.kernel.org/git/CABPp-BH9tju7WVm=QZDOvaMDdZbpNXrVWQdN-jmfN8wC6YVhmw@mail.gmail.com/ [13] https://stackoverflow.com/questions/13630849/git-difference-between-assume-unchanged-and-skip-worktree

Cons:

  * When core.sparseCheckout is enabled, this adds a performance cost to
    reading the index.  I'll defer discussion of this cost to a subsequent
    patch, since I have some optimizations to add.

=== Notes on testcase modifications ===

The good:
  * t1011: Compare to two cases above it ('read-tree will not throw away
    dirty changes, non-sparse'); since the file is present, it should
    match the non-sparse case now
  * t1092: sparse-index & sparse-checkout now match full-worktree
    behavior in more cases!  Yaay for consistency!
  * t6428, t7012: look at how much simpler the tests become!  Merge and
    stash can just fail early telling the user there's a file in the
    way, instead of not noticing until it's about to write a file and
    then have to implement sudden crash avoidance.  Hurray for sanity!
  * t7817: sparse behavior better matches full tree behavior.  Hurray
    for sanity!

The confusing:
  * t3705: These changes were ONLY needed on Windows, but they don't
    hurt other platforms.  Let's discuss each individually:

    * core.sparseCheckout should be false by default.  Nothing in this
      testcase toggles that until many, many tests later.  However,
      early tests (#5 in particular) were testing `update-index
      --skip-worktree` behavior in a non-sparse-checkout, but the
      Windows tests in CI were behaving as if core.sparseCheckout=true
      had been specified somewhere.  I do not have access to a Windows
      machine.  But I just manually did what should have been a no-op
      and turned the config off.  And it fixed the test.
    * I have no idea why the leftover .gitattributes file from this
      test was causing failures for test #18 on Windows, but only with
      these changes of mine.  Test #18 was checking for empty stderr,
      and specifically wanted to know that some error completely
      unrelated to file endings did not appear.  The leftover
      .gitattributes file thus caused some spurious stderr unrelated to
      the thing being checked.  Since other tests did not intend to
      test normalization, just proactively remove the .gitattributes
      file.  I'm certain this is cleaner and better, I'm just unsure
      why/how this didn't trigger problems before.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 repository.c                             |  7 ++++
 sparse-index.c                           | 21 +++++++++++
 sparse-index.h                           |  1 +
 t/t1011-read-tree-sparse-checkout.sh     |  2 +-
 t/t1092-sparse-checkout-compatibility.sh | 16 ++++-----
 t/t3705-add-sparse-checkout.sh           |  2 ++
 t/t6428-merge-conflicts-sparse.sh        | 23 +++----------
 t/t7012-skip-worktree-writing.sh         | 44 ++++--------------------
 t/t7817-grep-sparse-checkout.sh          | 11 ++++--
 9 files changed, 61 insertions(+), 66 deletions(-)

From: Elijah Newren <newren@gmail.com>

Make several small updates, to address a few documentation issues
I spotted:
  * sparse-checkout focused on "patterns" even though the inputs (and
    outputs in the case of `list`) are directories in cone-mode
  * The description section of the sparse-checkout documentation
    was a bit sparse (no pun intended), and focused more on internal
    mechanics rather than end user usage.  This made sense in the
    early days when the command was even more experimental, but let's
    adjust a bit to try to make it more approachable to end users who
    may want to consider using it.  Keep the scary backward
    compatibility warning, though; we're still hard at work trying to
    fix up commands to behave reasonably in sparse checkouts.
  * both read-tree and update-index tried to describe how to use the
    skip-worktree bit, but both predated the sparse-checkout command.
    The sparse-checkout command is a far easier mechanism to use and
    for users trying to reduce the size of their working tree, we
    should recommend users to look at it instead.
  * The update-index documentation pointed out that assume-unchanged
    and skip-worktree sounded similar but had different purposes.
    However, it made no attempt to explain the differences, only to
    point out that they were different.  Explain the differences.
  * The update-index documentation focused much more on (internal?)
    implementation details than on end-user usage.  Try to explain
    its purpose better for users of update-index, rather than
    fellow developers trying to work with the SKIP_WORKTREE bit.
  * Clarify that when core.sparseCheckout=true, we treat a file's
    presence in the working tree as being an override to the
    SKIP_WORKTREE bit (i.e. in sparse checkouts when the file is
    present we ignore the SKIP_WORKTREE bit).

Note that this commit, like many touching documentation, is best viewed with the `--color-words` option to diff/log.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 Documentation/git-read-tree.txt       | 12 +++--
 Documentation/git-sparse-checkout.txt | 76 ++++++++++++++++-----------
 Documentation/git-update-index.txt    | 57 +++++++++++++++-----
 3 files changed, 98 insertions(+), 47 deletions(-)

From: Elijah Newren <newren@gmail.com>

Trying to clear the skip-worktree bit from files that are present does present some computational overhead, for sparse-checkouts. (We do not do the bit clearing in non-sparse-checkouts.) Optimize it as follows:

Rather than lstat()'ing every SKIP_WORKTREE path, take advantage of the fact that entire directories will often be missing, especially for cone mode and even more so ever since commit 55dfcf9591 ("sparse-checkout: clear tracked sparse dirs", 2021-09-08). If we have already determined that the parent directory of a file (or other previous ancestor) does not exist, then the file cannot exist either so we do not need to lstat() it separately.

Timings for p2000 included below, reformatted to fit in normal commit
message line lengths, which compare three things:
  * Timings before this series
  * Timings of the unoptimized version of
    clear_skip_worktree_from_present_files() from a few commits ago
  * Timings after the optimization in this commit

(NOTE: t/perf/ appears to have timing resolution only down to 0.01 s, which presents significant measurement error when timings only differ by 0.01s. I don't trust any such timings below, and yet all the optimized results differ by at most 0.01s.)

Test Before Series Unoptimized Optimized ----------------------------------------------------------------------------- *git status* full-v3 0.15(0.10+0.06) 0.32(0.16+0.17) +113.3% 0.16(0.10+0.07) +6.7% full-v4 0.15(0.11+0.05) 0.32(0.17+0.16) +113.3% 0.16(0.11+0.05) +6.7% sparse-v3 0.04(0.03+0.04) 0.04(0.02+0.05) +0.0% 0.04(0.02+0.05) +0.0% sparse-v4 0.04(0.03+0.04) 0.04(0.02+0.05) +0.0% 0.04(0.03+0.05) +0.0%

*git add -A* full-v3 0.40(0.30+0.07) 0.56(0.36+0.17) +40.0% 0.39(0.30+0.07) -2.5% full-v4 0.37(0.28+0.07) 0.54(0.37+0.16) +45.9% 0.38(0.29+0.07) +2.7% sparse-v3 0.06(0.04+0.05) 0.08(0.05+0.05) +33.3% 0.06(0.05+0.04) +0.0% sparse-v4 0.05(0.03+0.05) 0.05(0.04+0.04) +0.0% 0.06(0.04+0.05) +20.0%

*git add .* full-v3 0.40(0.31+0.07) 0.57(0.37+0.17) +42.5% 0.41(0.30+0.08) +2.5% full-v4 0.38(0.30+0.06) 0.55(0.37+0.16) +44.7% 0.38(0.30+0.06) +0.0% sparse-v3 0.06(0.04+0.05) 0.06(0.05+0.04) +0.0% 0.06(0.03+0.05) +0.0% sparse-v4 0.06(0.05+0.05) 0.06(0.04+0.05) +0.0% 0.06(0.04+0.06) +0.0%

*git commit -a -m A* full-v3 0.41(0.32+0.06) 0.58(0.39+0.17) +41.5% 0.42(0.32+0.07) +2.4% full-v4 0.39(0.30+0.07) 0.56(0.38+0.17) +43.6% 0.40(0.31+0.07) +2.6% sparse-v3 0.04(0.03+0.04) 0.04(0.03+0.04) +0.0% 0.04(0.03+0.04) +0.0% sparse-v4 0.04(0.03+0.05) 0.04(0.03+0.05) +0.0% 0.04(0.03+0.04) +0.0%

*git checkout -f -* full-v3 0.56(0.46+0.07) 0.73(0.55+0.16) +30.4% 0.57(0.47+0.08) +1.8% full-v4 0.54(0.45+0.07) 0.71(0.53+0.17) +31.5% 0.55(0.45+0.07) +1.9% sparse-v3 0.06(0.04+0.04) 0.06(0.04+0.05) +0.0% 0.06(0.04+0.05) +0.0% sparse-v4 0.05(0.05+0.04) 0.05(0.04+0.05) +0.0% 0.06(0.04+0.05) +20.0%

*git reset* full-v3 0.34(0.26+0.05) 0.51(0.34+0.15) +50.0% 0.34(0.26+0.06) +0.0% full-v4 0.32(0.24+0.06) 0.49(0.32+0.15) +53.1% 0.33(0.25+0.06) +3.1% sparse-v3 0.04(0.03+0.04) 0.04(0.03+0.04) +0.0% 0.04(0.03+0.04) +0.0% sparse-v4 0.03(0.03+0.04) 0.03(0.02+0.04) +0.0% 0.03(0.03+0.04) +0.0%

*git reset --hard* full-v3 0.57(0.46+0.07) 0.90(0.61+0.25) +57.9% 0.57(0.45+0.08) +0.0% full-v4 0.54(0.46+0.05) 0.88(0.59+0.26) +63.0% 0.55(0.45+0.07) +1.9% sparse-v3 0.07(0.03+0.03) 0.07(0.04+0.03) +0.0% 0.07(0.03+0.03) +0.0% sparse-v4 0.06(0.03+0.03) 0.06(0.04+0.02) +0.0% 0.06(0.03+0.03) +0.0%

*git reset -- does-not-exist* full-v3 0.35(0.27+0.06) 0.52(0.32+0.17) +48.6% 0.35(0.27+0.06) +0.0% full-v4 0.33(0.26+0.05) 0.50(0.33+0.15) +51.5% 0.33(0.26+0.06) +0.0% sparse-v3 0.04(0.03+0.04) 0.04(0.03+0.04) +0.0% 0.04(0.03+0.04) +0.0% sparse-v4 0.04(0.02+0.04) 0.03(0.02+0.04) -25.0% 0.03(0.02+0.04) -25.0%

*git diff* full-v3 0.07(0.04+0.04) 0.24(0.11+0.14) +242.9% 0.07(0.04+0.04) +0.0% full-v4 0.07(0.03+0.05) 0.24(0.13+0.12) +242.9% 0.08(0.04+0.05) +14.3% sparse-v3 0.02(0.01+0.04) 0.02(0.01+0.04) +0.0% 0.02(0.01+0.05) +0.0% sparse-v4 0.02(0.02+0.03) 0.02(0.01+0.04) +0.0% 0.02(0.01+0.04) +0.0%

*git diff --cached* full-v3 0.05(0.03+0.02) 0.22(0.12+0.09) +340.0% 0.05(0.03+0.01) +0.0% full-v4 0.05(0.03+0.01) 0.23(0.12+0.11) +360.0% 0.05(0.03+0.02) +0.0% sparse-v3 0.01(0.00+0.00) 0.01(0.00+0.00) +0.0% 0.01(0.00+0.00) +0.0% sparse-v4 0.01(0.00+0.00) 0.01(0.00+0.00) +0.0% 0.01(0.00+0.00) +0.0%

*git blame f2/f4/a* full-v3 0.18(0.13+0.05) 0.52(0.29+0.23) +188.9% 0.19(0.15+0.04) +5.6% full-v4 0.19(0.15+0.04) 0.52(0.28+0.23) +173.7% 0.19(0.14+0.04) +0.0% sparse-v3 0.10(0.08+0.02) 0.10(0.09+0.01) +0.0% 0.10(0.09+0.01) +0.0% sparse-v4 0.10(0.08+0.02) 0.10(0.08+0.02) +0.0% 0.10(0.08+0.02) +0.0%

*git blame f2/f4/f3/a* full-v3 0.45(0.36+0.08) 0.78(0.51+0.27) +73.3% 0.45(0.37+0.08) +0.0% full-v4 0.45(0.37+0.08) 0.78(0.51+0.26) +73.3% 0.45(0.37+0.08) +0.0% sparse-v3 0.36(0.32+0.04) 0.36(0.31+0.05) +0.0% 0.36(0.31+0.04) +0.0% sparse-v4 0.36(0.31+0.05) 0.36(0.31+0.05) +0.0% 0.36(0.31+0.04) +0.0%

*git checkout-index -f --all* full-v3 0.07(0.02+0.05) 0.24(0.12+0.12) +242.9% 0.08(0.04+0.04) +14.3% full-v4 0.07(0.03+0.04) 0.24(0.11+0.13) +242.9% 0.08(0.03+0.04) +14.3% sparse-v3 0.04(0.01+0.03) 0.04(0.00+0.03) +0.0% 0.04(0.01+0.03) +0.0% sparse-v4 0.04(0.01+0.02) 0.04(0.01+0.03) +0.0% 0.04(0.01+0.02) +0.0%

*git update-index --add --remove f2/f4/a* full-v3 0.29(0.23+0.02) 0.46(0.30+0.12) +58.6% 0.30(0.24+0.02) +3.4% full-v4 0.27(0.22+0.02) 0.45(0.29+0.12) +66.7% 0.28(0.22+0.03) +3.7% sparse-v3 0.02(0.02+0.00) 0.02(0.01+0.00) +0.0% 0.02(0.01+0.00) +0.0% sparse-v4 0.02(0.02+0.00) 0.02(0.02+0.00) +0.0% 0.02(0.02+0.00) +0.0%

So, with the optimization, the extra work appears to be essentially 0 for sparse-checkouts that are also using sparse-indexes (even before my optimization), and the extra work appears to be just marginally more than 0 for sparse-checkouts that are using full indexes.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 sparse-index.c | 56 ++++++++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 54 insertions(+), 2 deletions(-)

On Thu, Jan 13, 2022 at 8:43 AM Elijah Newren via GitGitGadget <gitgitgadget@gmail.com> wrote:

...

To follow up on this using using a tool with higher precision for a few selected cases:

...

In hyperfine, the results were:

before-series,full-v3$ hyperfine '~/floss/git/git add -A'
Benchmark #1: ~/floss/git/git add -A
  Time (mean ± σ):     129.4 ms ±   3.0 ms    [User: 84.0 ms, System: 59.9 ms]
  Range (min … max):   122.5 ms … 138.3 ms    24 runs

post-optim,full-v3$ hyperfine '~/floss/git/git add -A'
Benchmark #1: ~/floss/git/git add -A
  Time (mean ± σ):     133.4 ms ±   3.0 ms    [User: 85.6 ms, System: 61.4 ms]
  Range (min … max):   129.7 ms … 142.7 ms    22 runs

Since 133.4/129.4 ~ 1.0309, we see that we have +3.1% on the execution timing due to changes in this series. Notably, the number is actually positive as we'd expect since we are clearly doing more work, whereas the t/perf system reports -2.5% due to measurement inaccuracy.

before-series,sparse-v4$ hyperfine '~/floss/git/git add -A'
Benchmark #1: ~/floss/git/git add -A
  Time (mean ± σ):      37.0 ms ±   1.1 ms    [User: 23.1 ms, System: 47.8 ms]
  Range (min … max):    35.6 ms …  42.1 ms    72 runs

post-optim,sparse-v4$ hyperfine '~/floss/git/git add -A'
Benchmark #1: ~/floss/git/git add -A
  Time (mean ± σ):      37.3 ms ±   0.9 ms    [User: 22.8 ms, System: 48.7 ms]
  Range (min … max):    36.2 ms …  40.7 ms    72 runs

37.3/37.0 ~ 1.008, so a +0.8% on execution timing. Hard to measure, and nice that hyperfine automatically chooses to run this 72 times just to ensure the data is more reliable. (Also, the +0.8% is much more believable than the +20.0% from lack of measurement accuracy, especially combined with data below)

before-series,full-v4$ hyperfine '~/floss/git/git diff'
Benchmark #1: ~/floss/git/git diff
  Time (mean ± σ):      69.9 ms ±   1.9 ms    [User: 37.5 ms, System: 47.6 ms]
  Range (min … max):    66.5 ms …  74.0 ms    44 runs

post-optim,full-v4$ hyperfine '~/floss/git/git diff'
Benchmark #1: ~/floss/git/git diff
  Time (mean ± σ):      73.0 ms ±   1.7 ms    [User: 40.7 ms, System: 47.1 ms]
  Range (min … max):    70.3 ms …  76.2 ms    40 runs

So 73.0/69.9 ~ 1.044, so a +4.4% to the execution timing -- much less than the +14.3% reported due to lack of measurement accuracy.

(If I had used ~/floss/git/bin-wrappers/git instead of ~/floss/git/git, the timings would have been going from 72.3ms to 75.1ms, representing a +3.9% increase instead. Probably doesn't matter, but just in case folks were curious about what if I used the bin-wrappers.)

Here, the timings went from 17.5ms to 17.6ms, or +0.6%. It's really hard to measure the overhead of the changes of my patch series when sparse-index is in use, which makes sense since the extra loop only has to check the toplevel directory, not any of the entries under it. But it does show just a minor cost in runtime due to the new added check.

I think the original commit message makes it clear that with the (new) optimization, the timings are quite reasonable, but maybe this little extra flavor helps for anyone who was just looking at the percentage changes. The timings and timing differences really need to be bigger than the precision in order to trust the percentage differences, which just wasn't the case for t/perf here. But t/perf was good enough to show that the timings after my series are roughly the same as before the series (never more than 0.01s slower).

(Maintainer note: This series builds on (v2 of) vd/sparse-clean-etc, because it tweaks one of the testcases added there.)

(Note 2: There was a previous RFC round of this series at https://lore.kernel.org/git/20220109045732.2497526-1-newren@gmail.com/.)

Files in the present-despite-SKIP_WORKTREE state have caused no ends of discussions and bugs[1,2,3,4,5,6,...and lots of others]. Trying to address the big issue of discovering & recovering from this state has befuddled me for over a year because I was worried we'd need additional code at every skip_worktree-checking path in the code (and they are all over the place), and that we'd make the code significantly slower unless we plumbed a bunch of additional information all over the place to allow some reasonable optimizations.

This series tries to solve the problem a bit differently by automatic early discovery and recovery; as a result, it greatly simplifies the landscape, reduces our testing matrix burden, and fixes a large swath of bugs. And I figured out how to get the perf cost down to essentially negligible.

Changes since v1 (or v2 if you count RFC as v1):

 * now includes some fixes for testcases from
   ds/fetch-pull-with-sparse-index (which topic marked its own new tests as
   potentially suboptimal; with my series, the sparse behavior now matches
   the full tree behavior on that test. Wahoo!). Note that Junio's version
   of vd/sparse-clean-etc already includes ds/fetch-pull-with-sparse-index,
   so no need to merge in anything extra.

Changes since RFC version:

 * updated the commit messages as per suggestions from Victoria, including
   adding performance measurements
 * renamed the new function to use a clearer name
 * replaced the final patch with a different optimization, which is both
   simpler and performs quite a bit better (the cost for my previous patch 5
   was already decent in many cases, but had a few cases where the cost was
   significant).

Quick overview:

 * Patches 1 & 2 add a test to demonstrate accidental deletion of
   possibly-modified files, and then fix the bug.
 * Patch 3 is the crux of this series; a small amount of code with a huge
   commit message
 * Patch 4 updates the documentation
 * Patch 5 adds an optimization to reduce the performance impact of patch 3

[1] https://lore.kernel.org/git/CABPp-BFnFpzwGC11TLoLs8YK5yiisA5D5-fFjXnJsbESVDwZsA@mail.gmail.com/ [2] https://lore.kernel.org/git/CABPp-BGJ_Nvi5TmgriD9Bh6eNXE2EDq2f8e8QKXAeYG3BxZafA@mail.gmail.com/ [3] https://lore.kernel.org/git/pull.809.git.git.1592356884310.gitgitgadget@gmail.com/ [4] commit 66b209b ("merge-ort: implement CE_SKIP_WORKTREE handling with conflicted entries", 2021-03-20) [5] commit ba359fd ("stash: fix stash application in sparse-checkouts", 2020-12-01) [6] https://lore.kernel.org/git/CABPp-BH9tju7WVm=QZDOvaMDdZbpNXrVWQdN-jmfN8wC6YVhmw@mail.gmail.com/

Elijah Newren (5):
  t1011: add testcase demonstrating accidental loss of user
    modifications
  unpack-trees: fix accidental loss of user changes
  repo_read_index: clear SKIP_WORKTREE bit from files present in
    worktree
  Update documentation related to sparsity and the skip-worktree bit
  Accelerate clear_skip_worktree_from_present_files() by caching

 Documentation/git-read-tree.txt          | 12 +++-
 Documentation/git-sparse-checkout.txt    | 76 ++++++++++++++----------
 Documentation/git-update-index.txt       | 57 +++++++++++++-----
 repository.c                             |  7 +++
 sparse-index.c                           | 73 +++++++++++++++++++++++
 sparse-index.h                           |  1 +
 t/t1011-read-tree-sparse-checkout.sh     | 23 ++++++-
 t/t1092-sparse-checkout-compatibility.sh | 41 ++++++-------
 t/t3705-add-sparse-checkout.sh           |  2 +
 t/t6428-merge-conflicts-sparse.sh        | 23 ++-----
 t/t7012-skip-worktree-writing.sh         | 44 +++-----------
 t/t7817-grep-sparse-checkout.sh          | 11 +++-
 unpack-trees.c                           |  4 +-
 13 files changed, 246 insertions(+), 128 deletions(-)

base-commit: 48609de3bf32befb69c40c1a2595a98dac0448b4
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1114%2Fnewren%2Ffix-present-despite-skip-worktree-v2
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1114/newren/fix-present-despite-skip-worktree-v2
Pull-Request: https://github.com/gitgitgadget/git/pull/1114

Range-diff vs v1:

 1:  c553d558c2f = 1:  d50d804af4e t1011: add testcase demonstrating accidental loss of user modifications
 2:  1e3958576e2 = 2:  206c638fa90 unpack-trees: fix accidental loss of user changes
 3:  b263cc75b7d ! 3:  11d46a399d2 repo_read_index: clear SKIP_WORKTREE bit from files present in worktree
     @@ t/t1092-sparse-checkout-compatibility.sh: test_expect_success 'update-index modi
       
       	# When skip-worktree is disabled (even on files outside sparse cone), file
       	# is updated in the index
     +@@ t/t1092-sparse-checkout-compatibility.sh: test_expect_success 'ls-files' '
     + 	test_cmp dense sparse &&
     + 
     + 	# Set up a strange condition of having a file edit
     +-	# outside of the sparse-checkout cone. This is just
     +-	# to verify that sparse-checkout and sparse-index
     +-	# behave the same in this case.
     ++	# outside of the sparse-checkout cone. We want to verify
     ++	# that all modes handle this the same, and detect the
     ++	# modification.
     + 	write_script edit-content <<-\EOF &&
     +-	mkdir folder1 &&
     ++	mkdir -p folder1 &&
     + 	echo content >>folder1/a
     + 	EOF
     +-	run_on_sparse ../edit-content &&
     ++	run_on_all ../edit-content &&
     + 
     +-	# ls-files does not currently notice modified files whose
     +-	# cache entries are marked SKIP_WORKTREE. This may change
     +-	# in the future, but here we test that sparse index does
     +-	# not accidentally create a change of behavior.
     +-	test_sparse_match git ls-files --modified &&
     +-	test_must_be_empty sparse-checkout-out &&
     +-	test_must_be_empty sparse-index-out &&
     ++	test_all_match git ls-files --modified &&
     + 
     + 	git -C sparse-index ls-files --sparse --modified >sparse-index-out &&
     +-	test_must_be_empty sparse-index-out &&
     ++	cat >expect <<-\EOF &&
     ++	folder1/a
     ++	EOF
     ++	test_cmp expect sparse-index-out &&
     + 
     + 	# Add folder1 to the sparse-checkout cone and
     + 	# check that ls-files shows the expanded files.
     + 	test_sparse_match git sparse-checkout add folder1 &&
     +-	test_sparse_match git ls-files --modified &&
     ++	test_all_match git ls-files --modified &&
     + 
     + 	test_all_match git ls-files &&
     + 	git -C sparse-index ls-files --sparse >actual &&
      
       ## t/t3705-add-sparse-checkout.sh ##
      @@ t/t3705-add-sparse-checkout.sh: setup_sparse_entry () {
 4:  c74ad19616e = 4:  0af00779128 Update documentation related to sparsity and the skip-worktree bit
 5:  e68028ebe0a = 5:  05ac964e630 Accelerate clear_skip_worktree_from_present_files() by caching

From: Elijah Newren <newren@gmail.com>

If a user has a file with local modifications that is not marked as SKIP_WORKTREE, but the sparsity patterns are such that it should be marked that way, and the user then invokes a command like

   * git checkout -q HEAD^

or

   * git read-tree -mu HEAD^

Then the file will be deleted along with all the users' modifications. Add a testcase demonstrating this problem.

Note: This bug only triggers if something other than 'HEAD' is given;
if the commands above had specified 'HEAD', then the users' file would
be left alone.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 t/t1011-read-tree-sparse-checkout.sh | 21 +++++++++++++++++++++
 1 file changed, 21 insertions(+)

On Fri, Jan 14 2022, Elijah Newren via GitGitGadget wrote:

Maybe I'm missing something, but can these two just be:

    grep dirty init.t

I.e. won't grep report errors appropriately here, e.g.:
    
    $ grep foo t
    grep: t: Is a directory
    $ grep foo x
    grep: x: No such file or directory

The only prior art I could find was the same pattern in your c449947a79d (directory rename detection: files/directories in the way of some renames, 2018-04-19).

It's probably good to lose the "-q" too, unless this output is way too verbose without it. In any case the errors wouldn't be affected.

On Wed, Feb 16, 2022 at 12:53 AM Ævar Arnfjörð Bjarmason <avarab@gmail.com> wrote:

Fair point. I believe my original test during development was just test_path_is_file, then I came back later and decided I should check the contents weren't lost. A test_cmp might be a better choice to replace both of these, because we don't really want to check that it just has "dirty" somewhere in the file, but that it's been left alone and only has those contents.

From: Elijah Newren <newren@gmail.com>

For sparse-checkouts, we don't want unpack-trees to error out on files that are missing from the worktree, so there has traditionally been logic to make it skip the verify_uptodate() check for these. Unfortunately, it was skipping the verify_uptodate() check for files that were expected to *become* SKIP_WORKTREE. For files that were not already SKIP_WORKTREE, that can cause us to later delete the file in apply_sparse_checkout(). Only skip the check for files that were already SKIP_WORKTREE as well to avoid lightly discarding important changes users may have made to files.

Note 1: unpack-trees.c is already a bit complex, and the logic around CE_SKIP_WORKTREE and CE_NEW_SKIP_WORKTREE in that file are no exception. I also tried just replacing CE_NEW_SKIP_WORKTREE with CE_SKIP_WORKTREE in the verify_uptodate() check instead of checking for both flags, and found that it also fixed this bug and passed all the tests. I also attempted to devise a few testcases that might trip either variant of my fix and was unable to find any problems. It may be that just checking CE_SKIP_WORKTREE is a better fix, but I'm not sure. I thought it was a bit safer to strictly reduce the number of cases where we skip the up-to-date check rather than just toggling which kind of cases skip it, and thus went with the current variant of the fix.

Note 2: I also wondered if verify_absent() might have a similar bug, but despite my attempts to try to devise a testcase that would trigger such a thing, I couldn't find any problematic testcases. Thus, this patch makes no attempt to apply similar changes to verify_absent() and verify_absent_if_directory().

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 t/t1011-read-tree-sparse-checkout.sh | 2 +-
 unpack-trees.c                       | 4 +++-
 2 files changed, 4 insertions(+), 2 deletions(-)

From: Elijah Newren <newren@gmail.com>

The fix is short (~30 lines), but the description is not.  Sorry.

There is a set of problems caused by files in what I'll refer to as the "present-despite-SKIP_WORKTREE" state. This commit aims to not just fix these problems, but remove the entire class as a possibility -- for those using sparse checkouts. But first, we need to understand the problems this class presents. A quick outline:

   * Problems
     * User facing issues
     * Problem space complexity
     * Maintenance and code correctness challenges
   * SKIP_WORKTREE expectations in Git
   * Suggested solution
   * Pros/Cons of suggested solution
   * Notes on testcase modifications

=== User facing issues ===

There are various ways for users to get files to be present in the
working copy despite having the SKIP_WORKTREE bit set for that file in
the index.  This may come from:
  * various git commands not really supporting the SKIP_WORKTREE bit[1,2]
  * users grabbing files from elsewhere and writing them to the worktree
    (perhaps even cached in their editor)
  * users attempting to "abort" a sparse-checkout operation with a
    not-so-early Ctrl+C (updating $GIT_DIR/info/sparse-checkout and the
    working tree is not atomic)[3].

Once users have present-despite-SKIP_WORKTREE files, any modifications users make to these files will be ignored, possibly to users' confusion.

Further:
  * these files will degrade performance for the sparse-index case due
    to requiring the index to be expanded (see commit 55dfcf9591
    ("sparse-checkout: clear tracked sparse dirs", 2021-09-08) for why
    we try to delete entire directories outside the sparse cone).
  * these files will not be updated by by standard commands
    (switch/checkout/pull/merge/rebase will leave them alone unless
    conflicts happen -- and even then, the conflicted file may be
    written somewhere else to avoid overwriting the SKIP_WORKTREE file
    that is present and in the way)
  * there is nothing in Git that users can use to discover such
    files (status, diff, grep, etc. all ignore it)
  * there is no reasonable mechanism to "recover" from such a condition
    (neither `git sparse-checkout reapply` nor `git reset --hard` will
    correct it).

So, not only are users modifications ignored, but the files get progressively more stale over time. At some point in the future, they may change their sparseness specification or disable sparse-checkouts. At that time, all present-despite-SKIP_WORKTREE files will show up as having lots of modifications because they represent a version from a different branch or commit. These might include user-made local changes from days before, but the only way to tell is to have users look through them all closely.

If these users come to others for help, there will be no logs that explain the issue; it's just a mysterious list of changes. Users might adamantly claim (correctly, as it turns out) that they didn't modify these files, while others presume they did.

[1] https://lore.kernel.org/git/xmqqbmb1a7ga.fsf@gitster-ct.c.googlers.com/ [2] https://lore.kernel.org/git/CABPp-BH9tju7WVm=QZDOvaMDdZbpNXrVWQdN-jmfN8wC6YVhmw@mail.gmail.com/ [3] https://lore.kernel.org/git/CABPp-BFnFpzwGC11TLoLs8YK5yiisA5D5-fFjXnJsbESVDwZsA@mail.gmail.com/

=== Problem space complexity ===

SKIP_WORKTREE has been part of Git for over a decade. Duy did lots of work on it initially, and several others have since come along and put lots of work into it. Stolee spent most of 2021 on the sparse-index, with lots of bugfixes along the way including to non-sparse-index cases as we are still trying to get sparse checkouts to behave reasonably. Basically every codepath throughout the treat needs to be aware of an additional type of file: tracked-but-not-present. The extra type results in lots of extra testcases and lots of extra code everywhere.

But, the sad thing is that we actually have more than one extra type. We have tracked, tracked-but-not-present (SKIP_WORKTREE), and tracked-but-promised-to-not-be-present-but-is-present-anyway (present-despite-SKIP_WORKTREE). Two types is a monumental amount of effort to support, and adding a third feels a bit like insanity[4].

[4] Some examples of which can be seen at
    https://lore.kernel.org/git/CABPp-BGJ_Nvi5TmgriD9Bh6eNXE2EDq2f8e8QKXAeYG3BxZafA@mail.gmail.com/

=== Maintenance and code correctness challenges ===

Matheus' patches to grep stalled for nearly a year, in part because of complications of how to handle sparse-checkouts appropriately in all cases[5][6] (with trying to sanely figure out how to sanely handle present-despite-SKIP_WORKTREE files being one of the complications). His rm/add follow-ups also took months because of those kinds of issues[7]. The corner cases with things like submodules and SKIP_WORKTREE with the addition of present-despite-SKIP_WORKTREE start becoming really complex[8].

We've had to add ugly logic to merge-ort to attempt to handle present-despite-SKIP_WORKTREE files[9], and basically just been forced to give up in merge-recursive knowing full well that we'll sometimes silently discard user modifications. Despite stash essentially being a merge, it needed extra code (beyond what was in merge-ort and merge-recursive) to manually tweak SKIP_WORKTREE bits in order to avoid a few different bugs that'd result in an early abort with a partial stash application[10].

[5] See https://lore.kernel.org/git/5f3f7ac77039d41d1692ceae4b0c5df3bb45b74a.1612901326.git.matheus.bernardino@usp.br/#t
    and the dates on the thread; also Matheus and I had several
    conversations off-list trying to resolve the issues over that time
[6] ...it finally kind of got unstuck after
    https://lore.kernel.org/git/CABPp-BGJ_Nvi5TmgriD9Bh6eNXE2EDq2f8e8QKXAeYG3BxZafA@mail.gmail.com/
[7] See for example
    https://lore.kernel.org/git/CABPp-BHwNoVnooqDFPAsZxBT9aR5Dwk5D9sDRCvYSb8akxAJgA@mail.gmail.com/#t
    and quotes like "The core functionality of sparse-checkout has always
    been only partially implemented", a statement I still believe is true
    today.
[8] https://lore.kernel.org/git/pull.809.git.git.1592356884310.gitgitgadget@gmail.com/
[9] See commit 66b209b86a ("merge-ort: implement CE_SKIP_WORKTREE
    handling with conflicted entries", 2021-03-20)
[10] See commit ba359fd507 ("stash: fix stash application in
     sparse-checkouts", 2020-12-01)

=== SKIP_WORKTREE expectations in Git ===

A couple quotes:

From [11] (before the "sparse-checkout" command existed):
   If it needs too many special cases, hacks, and conditionals, then it
   is not worth the complexity---if it is easier to write a correct code
   by allowing Git to populate working tree files, it is perfectly fine
   to do so.

   In a sense, the sparse checkout "feature" itself is a hack by itself,
   and that is why I think this part should be "best effort" as well.

From the git-sparse-checkout manual (still present today):

   THIS COMMAND IS EXPERIMENTAL. ITS BEHAVIOR, AND THE BEHAVIOR OF OTHER
   COMMANDS IN THE PRESENCE OF SPARSE-CHECKOUTS, WILL LIKELY CHANGE IN
   THE FUTURE.

[11] https://lore.kernel.org/git/xmqqbmb1a7ga.fsf@gitster-ct.c.googlers.com/

=== Suggested solution ===

SKIP_WORKTREE was written to allow sparse-checkouts, in particular, as the name of the option implies, to allow the file to NOT be in the worktree but consider it to be unchanged rather than deleted.

The suggests a simple solution: present-despite-SKIP_WORKTREE files should not exist, for those using sparse-checkouts.

Enforce this at index loading time by checking if core.sparseCheckout is true; if so, check files in the index with the SKIP_WORKTREE bit set to verify that they are absent from the working tree. If they are present, unset the bit (in memory, though any commands that write to the index will record the update).

Users can, of course, can get the SKIP_WORKTREE bit back such as by running `git sparse-checkout reapply` (if they have ensured the file is unmodified and doesn't match the specified sparsity patterns).

=== Pros/Cons of suggested solution ===

Pros:

  * Solves the user visible problems reported above, which I've been
    complaining about for nearly a year but couldn't find a solution to.
  * Helps prevent slow performance degradation with a sparse-index.
  * Much easier behavior in sparse-checkouts for users to reason about
  * Very simple, ~30 lines of code.
  * Significantly simplifies some ugly testcases, and obviates the need
    to test an entire class of potential issues.
  * Reduces code complexity, reasoning, and maintenance.  Avoids
    disagreements about weird corner cases[12].
  * It has been reported that some users might be (ab)using
    SKIP_WORKTREE as a let-me-modify-but-keep-the-file-in-the-worktree
    mechanism[13, and a few other similar references].  These users know
    of multiple caveats and shortcomings in doing so; perhaps not
    surprising given the "SKIP_WORKTREE expecations" section above.
    However, these users use `git update-index --skip-worktree`, and not
    `git sparse-checkout` or core.sparseCheckout=true.  As such, these
    users would be unaffected by this change and can continue abusing
    the system as before.

[12] https://lore.kernel.org/git/CABPp-BH9tju7WVm=QZDOvaMDdZbpNXrVWQdN-jmfN8wC6YVhmw@mail.gmail.com/ [13] https://stackoverflow.com/questions/13630849/git-difference-between-assume-unchanged-and-skip-worktree

Cons:

  * When core.sparseCheckout is enabled, this adds a performance cost to
    reading the index.  I'll defer discussion of this cost to a subsequent
    patch, since I have some optimizations to add.

=== Notes on testcase modifications ===

The good:
  * t1011: Compare to two cases above it ('read-tree will not throw away
    dirty changes, non-sparse'); since the file is present, it should
    match the non-sparse case now
  * t1092: sparse-index & sparse-checkout now match full-worktree
    behavior in more cases!  Yaay for consistency!
  * t6428, t7012: look at how much simpler the tests become!  Merge and
    stash can just fail early telling the user there's a file in the
    way, instead of not noticing until it's about to write a file and
    then have to implement sudden crash avoidance.  Hurray for sanity!
  * t7817: sparse behavior better matches full tree behavior.  Hurray
    for sanity!

The confusing:
  * t3705: These changes were ONLY needed on Windows, but they don't
    hurt other platforms.  Let's discuss each individually:

    * core.sparseCheckout should be false by default.  Nothing in this
      testcase toggles that until many, many tests later.  However,
      early tests (#5 in particular) were testing `update-index
      --skip-worktree` behavior in a non-sparse-checkout, but the
      Windows tests in CI were behaving as if core.sparseCheckout=true
      had been specified somewhere.  I do not have access to a Windows
      machine.  But I just manually did what should have been a no-op
      and turned the config off.  And it fixed the test.
    * I have no idea why the leftover .gitattributes file from this
      test was causing failures for test #18 on Windows, but only with
      these changes of mine.  Test #18 was checking for empty stderr,
      and specifically wanted to know that some error completely
      unrelated to file endings did not appear.  The leftover
      .gitattributes file thus caused some spurious stderr unrelated to
      the thing being checked.  Since other tests did not intend to
      test normalization, just proactively remove the .gitattributes
      file.  I'm certain this is cleaner and better, I'm just unsure
      why/how this didn't trigger problems before.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 repository.c                             |  7 ++++
 sparse-index.c                           | 21 +++++++++++
 sparse-index.h                           |  1 +
 t/t1011-read-tree-sparse-checkout.sh     |  2 +-
 t/t1092-sparse-checkout-compatibility.sh | 41 ++++++++++------------
 t/t3705-add-sparse-checkout.sh           |  2 ++
 t/t6428-merge-conflicts-sparse.sh        | 23 +++----------
 t/t7012-skip-worktree-writing.sh         | 44 ++++--------------------
 t/t7817-grep-sparse-checkout.sh          | 11 ++++--
 9 files changed, 72 insertions(+), 80 deletions(-)

On Fri, Jan 14 2022, Elijah Newren via GitGitGadget wrote:

The end-state of this series will pass its tests with this on top, only the last "mkdir -p" you added for the ls-files test seems to do anything:

On Wed, Feb 16, 2022 at 1:14 AM Ævar Arnfjörð Bjarmason <avarab@gmail.com> wrote:

Maybe, but that sounds like a comment on the series from 13 months ago rather than this series. It's somewhat orthogonal to what I'm doing here... ;-)

(cc-ing Jonathan Tan, Jose Lopes, and Jeff Hostetler, vfs experts) Hi Elijah,

Elijah Newren wrote[1]:

Thanks for a clear explanation!  This is very helpful.

[...]

This patch just reached "next", so at $DAYJOB a test for our vfsd[2] noticed this change. The trick behind a Git-based virtual filesystem is typically:

- since we control the filesystem, we can pretend all files are
  already present.  On access, we obtain the file content from the git
  object store.  On write, we update the sparse-checkout pattern so
  that Git knows to start tracking the file.

- by keeping the sparse-checkout pattern narrow, we minimize the time
  commands like "git status" need to spend looking for changes in
  unmodified files.  Controlling the filesystem means we don't need to
  worry about changes to files that don't match that pattern (since
  any modification would also trigger a sparse-checkout pattern
  update).

If I understand the intent behind this change correctly, it's incompatible with that trick. How would you recommend handling that? In the not too far away future, I'd expect something like the "VFS projection hook" to handle this use case, but in the meantime, I would expect this change to break VFS for Git performance. A few options:

 a. We could guard it with a config option.  It would still be a
    regression for VFS for Git users, but they'd be able to use the
    config option to restore the expected behavior.  (Or
    alternatively, such a config option could be disabled by default,
    but I suspect that would defeat the purpose described for the
    patch.)

 b. We could distinguish between the vfsd and the "interrupted and
    forgot to update SKIP_WORKTREE bits in the index" cases somehow.
    This sounds complex.

 c. Something else?

(b) and (c) aren't sounding obviously good, so (a) seems tempting. What do you think?

Thanks, Jonathan

[1] https://lore.kernel.org/git/11d46a399d26c913787b704d2b7169cafc28d639.1642175983.git.gitgitgadget@gmail.com/ [2] see https://lore.kernel.org/git/20220207190320.2960362-1-jonathantanmy@google.com/ for what I mean by "vfsd"

On Fri, Feb 18, 2022 at 5:07 PM Jonathan Nieder <jrnieder@gmail.com> wrote:

Sorry for the headache.

Let me try to restate the problem I'm solving, then attempt to put your above situation into my own words, to verify I'm understanding...

So the primary challenge I was trying to address with this patch series, was that keeping the filesystem and the "sparsity" state in-sync was just *difficult*. Things like checkout-index or even diff+apply will write to the working tree without even thinking about updating the sparsity state in the index to match. And that's only looking at Git-related commands. People can write new copies of files manually in a myriad of ways. Detecting and handling that inconsistent state between the working tree and index wasn't as easy as it looked.

One way to solve this problem would be to have a vfs, where any time someone writes to a file, you update the index to clear the SKIP_WORKTREE bit for the written file. Sounds like you have such a thing. (...or close to it, since you'd update the sparsity patterns, and the tooling to check mismatches of sparsity patterns and the index state are good and those get updated nicely. We just struggle to have something that correctly updates between index and working tree mismatches of sparsity state). So, that basically means you wouldn't benefit from this change.

But for those of us without some kind of vfs that detects writes and auto-updates either the sparsity patterns or the SKIP_WORKTREE bit in the index, we want something that will manually check the working tree to see if files have been written and update the index accordingly.

And, of course, you're trying to do more than just detect inconsistencies -- you want the vfs to fully control the sparsity patterns and expand them based on dynamic file accesses by the user. That dynamic bit doesn't play well with the non-vfs workaround.

Does that sound right?

Side note: I thought Microsoft's vfs was first named GVFS and then based on naming collisions renamed to VFS for Git. Sounds like you have something that is probably a bit different, but which you are also calling VFS for Git? Is there some potential confusion here, or are you banking on Microsoft eventually dropping their project? Or that you'll both keep your projects internal and not share them so the naming collision doesn't matter? Just curious...

Yeah, I'm having a hard time coming up with a way that either the VFS could recognize these special Git present-despite-skip-worktree checks and treat them differently, or having Git recognize that it is running under a special VFS that likes to aggressively and automagically expand the sparsity patterns. So (a) seems tempting to me too.

Got any name suggestions? core.avoidPresentDespiteSkipWorktreeCheck (defaulting to false)? core.sparsityConsistencyCheck (defaulting to true)?

Did your team want to implement that on top of en/present-despite-skipped since you can verify if it works for you, or did you want me to take a stab at it? Should be a pretty simple change.

Hi,

Elijah Newren wrote:

You captured some of it. There's a bit more: typically when using sparse checkout the traditional way, you will not have files in your working directory that do not match the sparse checkout pattern. That way, the disk usage in the working copy is nice and small. But with a vfsd like described in [2], having other files in the working directory does not cost disk usage because the corresponding data even in compressed (git object) form does not have to be present locally until the files are accessed. So a vfsd gives an end user the illusion that all files are present, whereas git only operates on a small subset (the working set).

With this change, git would start operating on all the files.

[...]

No, sorry for the lack of clarity. When I say "VFS for Git", I genuinely mean https://vfsforgit.org/, which was authored by Microsoft and to my understanding is still used by Microsoft's Windows team and is available for anyone to use. (That page currently returns a cert error because their SSL cert expired 10 days ago. But hopefully it conveys the idea, and the content is still there if you go through the interstitial.)

I agree that it can be kind of confusing to talk about that alongside VFSes in general, but I didn't choose the name. :)

[...]

[...]

Thanks. In a way it feels like giving up (isn't it better when things automagically Just Work?), but I think it's the right thing to do.

Monday is a holiday here; it shouldn't be hard to get a patch out later this week. Happy to write one but I also won't be at all offended if someone else writes it first.

Ideally the config name should describe the intent from the user's perspective instead of the implementation. So something like "sparsecheckout.expectFilesOutsideSparsePattern".

Thanks, Jonathan

On Sat, Feb 19, 2022 at 10:14 AM Jonathan Nieder <jrnieder@gmail.com> wrote:

I took a stab at it over here: https://lore.kernel.org/git/pull.1153.git.1645333542011.gitgitgadget@gmail.com/

Let me know if that works for you.

On 2/18/2022 8:06 PM, Jonathan Nieder wrote:

Just chiming in here to say that we've dealt with these issues in microsoft/git by special-casing them behind our core_virtualfilesystem global. A recent example is the changes to 'git add' to prevent adding a file that is marked as sparse (unless --sparse is specified). We always allow this when in the virtualized scenario [1].

[1] https://github.com/microsoft/git/blob/2f6531aced2e77a6c1000a923967ae0105383930/builtin/add.c#L50-L54

This seems like something that should be on vfsd to handle, and should not prevent upstream Git from making changes that benefit its users.

Thanks, -Stolee

Hi,

Derrick Stolee wrote:

Oh! Thanks for that pointer --- it's very helpful. I hadn't realized that VFS for Git still requires a patched Git.

Separate from the "should" questions (in general I'm in favor of unpatched Git being able to serve as a solid platform for both Scalar and this kind of VFS use case), this context tells me that this is not in fact a regression for VFS for Git users, so it's much appreciated.

Thanks, Jonathan

From: Elijah Newren <newren@gmail.com>

Make several small updates, to address a few documentation issues
I spotted:
  * sparse-checkout focused on "patterns" even though the inputs (and
    outputs in the case of `list`) are directories in cone-mode
  * The description section of the sparse-checkout documentation
    was a bit sparse (no pun intended), and focused more on internal
    mechanics rather than end user usage.  This made sense in the
    early days when the command was even more experimental, but let's
    adjust a bit to try to make it more approachable to end users who
    may want to consider using it.  Keep the scary backward
    compatibility warning, though; we're still hard at work trying to
    fix up commands to behave reasonably in sparse checkouts.
  * both read-tree and update-index tried to describe how to use the
    skip-worktree bit, but both predated the sparse-checkout command.
    The sparse-checkout command is a far easier mechanism to use and
    for users trying to reduce the size of their working tree, we
    should recommend users to look at it instead.
  * The update-index documentation pointed out that assume-unchanged
    and skip-worktree sounded similar but had different purposes.
    However, it made no attempt to explain the differences, only to
    point out that they were different.  Explain the differences.
  * The update-index documentation focused much more on (internal?)
    implementation details than on end-user usage.  Try to explain
    its purpose better for users of update-index, rather than
    fellow developers trying to work with the SKIP_WORKTREE bit.
  * Clarify that when core.sparseCheckout=true, we treat a file's
    presence in the working tree as being an override to the
    SKIP_WORKTREE bit (i.e. in sparse checkouts when the file is
    present we ignore the SKIP_WORKTREE bit).

Note that this commit, like many touching documentation, is best viewed with the `--color-words` option to diff/log.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 Documentation/git-read-tree.txt       | 12 +++--
 Documentation/git-sparse-checkout.txt | 76 ++++++++++++++++-----------
 Documentation/git-update-index.txt    | 57 +++++++++++++++-----
 3 files changed, 98 insertions(+), 47 deletions(-)

On Fri, Jan 14 2022, Elijah Newren via GitGitGadget wrote:

I was honestly a bit confused about whether we were really referring to the git-update-index and git-read-tree commands here, or some sparse-checkout (re-)usage of the same as "primitives", but reading it again & the commit message we're just talking about the commands here.

So this really just wants to assure readers that they're advised to use the shiny porcelain command instead of the plumbing.

I think we should refer to these as e.g. "linkgit:git-update-index[1]" not "`update-index`" here, and call them e.g. "plumbing commands" instead of "primitives" here, which will address that (the reader wonders "what's a primitive?").

In terms of prose I think it's preferred to keep matter-of-fact "Slices and dices apples, making them easier to eat" instead of "This command slices and dices apples, which means that it's easier to eat them".

I've forgotten what the linguisting term for that is, but it's more consistent with our docs, and makes for easier reading.

As someone with light familiarity with sparse-checkout:

I'm still not sure if this is telling me that it's preferred to list directories v.s. patterns, or if it's telling me it's better to operate in "cone mode" v.s. "non-cone mode", or some combination of the two.

IOW I think peeling out that "(which is recommended)" and making it clearly refer to which (or both?) of the two we're talking about would be much better.

(I didn't read through the rest in any detail)

On Wed, Feb 16, 2022 at 1:23 AM Ævar Arnfjörð Bjarmason <avarab@gmail.com> wrote:

Neither, really.

I was trying to talk about just the small building blocks found in git-update-index and git-read-tree commands that relate to sparse checkouts (i.e. the --[no-]skip-worktree and --[no-]ignore-skip-worktree-entries options to git-update-index, and the ability to update the working tree according to $GITDIR/info/sprse-checkout buried in `git read-tree -mu HEAD`).

Perhaps:

Note: The skip-worktree capabilities in linkgit:git-update-index[1]
and `read-tree` predated the introduction of
linkgit:git-sparse-checkout[1].  Users are encouraged to use the
`sparse-checkout` command in preference to these plumbing commands for
sparse-checkout/skip-worktree related needs.

?

So, s/means that it changes/change/ ?

Much easier to fix when I resubmit the patch to change the default for sparse-checkout to cone mode (i.e. when I resubmit https://lore.kernel.org/git/e30119b96dfaf9fdb82039cab84f8b81caacc1de.1644712798.git.gitgitgadget@gmail.com/). I can include the above changes too.

From: Elijah Newren <newren@gmail.com>

Trying to clear the skip-worktree bit from files that are present does present some computational overhead, for sparse-checkouts. (We do not do the bit clearing in non-sparse-checkouts.) Optimize it as follows:

Rather than lstat()'ing every SKIP_WORKTREE path, take advantage of the fact that entire directories will often be missing, especially for cone mode and even more so ever since commit 55dfcf9591 ("sparse-checkout: clear tracked sparse dirs", 2021-09-08). If we have already determined that the parent directory of a file (or other previous ancestor) does not exist, then the file cannot exist either so we do not need to lstat() it separately.

Timings for p2000 included below, reformatted to fit in normal commit
message line lengths, which compare three things:
  * Timings before this series
  * Timings of the unoptimized version of
    clear_skip_worktree_from_present_files() from a few commits ago
  * Timings after the optimization in this commit

(NOTE: t/perf/ appears to have timing resolution only down to 0.01 s, which presents significant measurement error when timings only differ by 0.01s. I don't trust any such timings below, and yet all the optimized results differ by at most 0.01s.)

Test Before Series Unoptimized Optimized ----------------------------------------------------------------------------- *git status* full-v3 0.15(0.10+0.06) 0.32(0.16+0.17) +113.3% 0.16(0.10+0.07) +6.7% full-v4 0.15(0.11+0.05) 0.32(0.17+0.16) +113.3% 0.16(0.11+0.05) +6.7% sparse-v3 0.04(0.03+0.04) 0.04(0.02+0.05) +0.0% 0.04(0.02+0.05) +0.0% sparse-v4 0.04(0.03+0.04) 0.04(0.02+0.05) +0.0% 0.04(0.03+0.05) +0.0%

*git add -A* full-v3 0.40(0.30+0.07) 0.56(0.36+0.17) +40.0% 0.39(0.30+0.07) -2.5% full-v4 0.37(0.28+0.07) 0.54(0.37+0.16) +45.9% 0.38(0.29+0.07) +2.7% sparse-v3 0.06(0.04+0.05) 0.08(0.05+0.05) +33.3% 0.06(0.05+0.04) +0.0% sparse-v4 0.05(0.03+0.05) 0.05(0.04+0.04) +0.0% 0.06(0.04+0.05) +20.0%

*git add .* full-v3 0.40(0.31+0.07) 0.57(0.37+0.17) +42.5% 0.41(0.30+0.08) +2.5% full-v4 0.38(0.30+0.06) 0.55(0.37+0.16) +44.7% 0.38(0.30+0.06) +0.0% sparse-v3 0.06(0.04+0.05) 0.06(0.05+0.04) +0.0% 0.06(0.03+0.05) +0.0% sparse-v4 0.06(0.05+0.05) 0.06(0.04+0.05) +0.0% 0.06(0.04+0.06) +0.0%

*git commit -a -m A* full-v3 0.41(0.32+0.06) 0.58(0.39+0.17) +41.5% 0.42(0.32+0.07) +2.4% full-v4 0.39(0.30+0.07) 0.56(0.38+0.17) +43.6% 0.40(0.31+0.07) +2.6% sparse-v3 0.04(0.03+0.04) 0.04(0.03+0.04) +0.0% 0.04(0.03+0.04) +0.0% sparse-v4 0.04(0.03+0.05) 0.04(0.03+0.05) +0.0% 0.04(0.03+0.04) +0.0%

*git checkout -f -* full-v3 0.56(0.46+0.07) 0.73(0.55+0.16) +30.4% 0.57(0.47+0.08) +1.8% full-v4 0.54(0.45+0.07) 0.71(0.53+0.17) +31.5% 0.55(0.45+0.07) +1.9% sparse-v3 0.06(0.04+0.04) 0.06(0.04+0.05) +0.0% 0.06(0.04+0.05) +0.0% sparse-v4 0.05(0.05+0.04) 0.05(0.04+0.05) +0.0% 0.06(0.04+0.05) +20.0%

*git reset* full-v3 0.34(0.26+0.05) 0.51(0.34+0.15) +50.0% 0.34(0.26+0.06) +0.0% full-v4 0.32(0.24+0.06) 0.49(0.32+0.15) +53.1% 0.33(0.25+0.06) +3.1% sparse-v3 0.04(0.03+0.04) 0.04(0.03+0.04) +0.0% 0.04(0.03+0.04) +0.0% sparse-v4 0.03(0.03+0.04) 0.03(0.02+0.04) +0.0% 0.03(0.03+0.04) +0.0%

*git reset --hard* full-v3 0.57(0.46+0.07) 0.90(0.61+0.25) +57.9% 0.57(0.45+0.08) +0.0% full-v4 0.54(0.46+0.05) 0.88(0.59+0.26) +63.0% 0.55(0.45+0.07) +1.9% sparse-v3 0.07(0.03+0.03) 0.07(0.04+0.03) +0.0% 0.07(0.03+0.03) +0.0% sparse-v4 0.06(0.03+0.03) 0.06(0.04+0.02) +0.0% 0.06(0.03+0.03) +0.0%

*git reset -- does-not-exist* full-v3 0.35(0.27+0.06) 0.52(0.32+0.17) +48.6% 0.35(0.27+0.06) +0.0% full-v4 0.33(0.26+0.05) 0.50(0.33+0.15) +51.5% 0.33(0.26+0.06) +0.0% sparse-v3 0.04(0.03+0.04) 0.04(0.03+0.04) +0.0% 0.04(0.03+0.04) +0.0% sparse-v4 0.04(0.02+0.04) 0.03(0.02+0.04) -25.0% 0.03(0.02+0.04) -25.0%

*git diff* full-v3 0.07(0.04+0.04) 0.24(0.11+0.14) +242.9% 0.07(0.04+0.04) +0.0% full-v4 0.07(0.03+0.05) 0.24(0.13+0.12) +242.9% 0.08(0.04+0.05) +14.3% sparse-v3 0.02(0.01+0.04) 0.02(0.01+0.04) +0.0% 0.02(0.01+0.05) +0.0% sparse-v4 0.02(0.02+0.03) 0.02(0.01+0.04) +0.0% 0.02(0.01+0.04) +0.0%

*git diff --cached* full-v3 0.05(0.03+0.02) 0.22(0.12+0.09) +340.0% 0.05(0.03+0.01) +0.0% full-v4 0.05(0.03+0.01) 0.23(0.12+0.11) +360.0% 0.05(0.03+0.02) +0.0% sparse-v3 0.01(0.00+0.00) 0.01(0.00+0.00) +0.0% 0.01(0.00+0.00) +0.0% sparse-v4 0.01(0.00+0.00) 0.01(0.00+0.00) +0.0% 0.01(0.00+0.00) +0.0%

*git blame f2/f4/a* full-v3 0.18(0.13+0.05) 0.52(0.29+0.23) +188.9% 0.19(0.15+0.04) +5.6% full-v4 0.19(0.15+0.04) 0.52(0.28+0.23) +173.7% 0.19(0.14+0.04) +0.0% sparse-v3 0.10(0.08+0.02) 0.10(0.09+0.01) +0.0% 0.10(0.09+0.01) +0.0% sparse-v4 0.10(0.08+0.02) 0.10(0.08+0.02) +0.0% 0.10(0.08+0.02) +0.0%

*git blame f2/f4/f3/a* full-v3 0.45(0.36+0.08) 0.78(0.51+0.27) +73.3% 0.45(0.37+0.08) +0.0% full-v4 0.45(0.37+0.08) 0.78(0.51+0.26) +73.3% 0.45(0.37+0.08) +0.0% sparse-v3 0.36(0.32+0.04) 0.36(0.31+0.05) +0.0% 0.36(0.31+0.04) +0.0% sparse-v4 0.36(0.31+0.05) 0.36(0.31+0.05) +0.0% 0.36(0.31+0.04) +0.0%

*git checkout-index -f --all* full-v3 0.07(0.02+0.05) 0.24(0.12+0.12) +242.9% 0.08(0.04+0.04) +14.3% full-v4 0.07(0.03+0.04) 0.24(0.11+0.13) +242.9% 0.08(0.03+0.04) +14.3% sparse-v3 0.04(0.01+0.03) 0.04(0.00+0.03) +0.0% 0.04(0.01+0.03) +0.0% sparse-v4 0.04(0.01+0.02) 0.04(0.01+0.03) +0.0% 0.04(0.01+0.02) +0.0%

*git update-index --add --remove f2/f4/a* full-v3 0.29(0.23+0.02) 0.46(0.30+0.12) +58.6% 0.30(0.24+0.02) +3.4% full-v4 0.27(0.22+0.02) 0.45(0.29+0.12) +66.7% 0.28(0.22+0.03) +3.7% sparse-v3 0.02(0.02+0.00) 0.02(0.01+0.00) +0.0% 0.02(0.01+0.00) +0.0% sparse-v4 0.02(0.02+0.00) 0.02(0.02+0.00) +0.0% 0.02(0.02+0.00) +0.0%

So, with the optimization, the extra work appears to be essentially 0 for sparse-checkouts that are also using sparse-indexes (even before my optimization), and the extra work appears to be just marginally more than 0 for sparse-checkouts that are using full indexes.

Signed-off-by: Elijah Newren <newren@gmail.com>
---
 sparse-index.c | 56 ++++++++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 54 insertions(+), 2 deletions(-)

Elijah Newren via GitGitGadget wrote:

Thank you for including these results! In the cone-mode case, I'm happy to see that the optimization effectively brings the cost of correcting SKIP_WORKTREE down to 0. As for the unoptimized version (which, if I'm reading this correctly, still approximates some worst-case non-cone cases), I think correcting SKIP_WORKTREE is probably still worth the performance cost - in the relatively massive test repo used in p2000, it's still only ~0.2-0.3s across the board.

I really like how this version of the optimization works, and ultimately find it simpler than the hashmap approach from the RFC. Looks good!

On Fri, Jan 14 2022, Elijah Newren via GitGitGadget wrote:

I really don't care/just asking, but there was a discussion on another topic about guarding calls to the mem*() family when n=0: https://lore.kernel.org/git/xmqq1r24gsph.fsf@gitster.g/

Is this the same sort of redundancy where we could lose the "&& *dirname" part, or is it still important because a "\0" dirname would have corresponding non-0 *dir_len?

More generally ... (see below)...

In most other places we're a bit more careful about lstat() error handling, e.g.:
    
    builtin/init-db.c:              if (lstat(path->buf, &st_git)) {
    builtin/init-db.c-                      if (errno != ENOENT)
    builtin/init-db.c-                              die_errno(_("cannot stat '%s'"), path->buf);
    builtin/init-db.c-              }
    
Shouldn't we do the same here and at least error() on return values of
-1 with an accompanying errno that isn't ENOENT?

...(continued from above) is the "path is zero" part of this even
reachable? I tried with this on top and ran your tests (and the rest of
t*sparse*.sh) successfully:
	
	diff --git a/sparse-index.c b/sparse-index.c
	index eed170cd8f7..f89c944d8cd 100644
	--- a/sparse-index.c
	+++ b/sparse-index.c
	@@ -403,6 +403,7 @@ void clear_skip_worktree_from_present_files(struct index_state *istate)
	 	for (i = 0; i < istate->cache_nr; i++) {
	 		struct cache_entry *ce = istate->cache[i];
	 
	+		assert(*ce->name);
	 		if (ce_skip_worktree(ce) &&
	 		    path_found(ce->name, &last_dirname, &dir_len, &dir_found)) {
	 			if (S_ISSPARSEDIR(ce->ce_mode)) {

I.e. isn't this undue paranoia about the cache API giving us zero-length paths?

On Wed, Feb 16, 2022 at 1:37 AM Ævar Arnfjörð Bjarmason <avarab@gmail.com> wrote:

No, dirname is a char**, not a char*. I need to make sure *dirname is non-NULL before passing to memcmp or we get segfaults (and *dirname will be NULL the first time it gets to this line, so the check is critical).

If we should do that everywhere, should we have an xlstat in wrapper.[ch]?

Nope, not related at all, for two reasons: the code above was checking for NULL pointers rather than NUL characters, and the argument I was checking was last_dirname, not ce->name.

On Wed, Feb 16, 2022 at 8:30 AM Elijah Newren <newren@gmail.com> wrote:

...

Turns out we already DO have a file_exists() wrapper function, but it's found in dir.c rather than wrapper.[ch]. However, it doesn't bother to check errno either...

Elijah Newren via GitGitGadget wrote:

Betwee the RFC and this version, you've made the changes I was looking for and answered any remaining questions I had. This series (including patches 1, 2, and 4 - I didn't have anything substantial to say/ask/add to those) looks good to me.

Thank you for working on this!