| Message ID | pull.906.v3.git.1618261697.gitgitgadget@gmail.com (mailing list archive) |
|---|---|
| Headers | show |
| Series | Sparse Index: API protections | expand |
On Mon, Apr 12, 2021 at 2:08 PM Derrick Stolee via GitGitGadget <gitgitgadget@gmail.com> wrote: > > 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 ds/sparse-index. > > 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 v3 > ============= > > * I updated based on Elijah's feedback. > * One new patch splits out a change that Elijah (rightfully) pointed out > did not belong with the patch it was originally in. > > I gave it time to see if any other comments came in, but it looks like > review stabilized. I probably waited a bit longer than I should have. This round looks good to me. Reviewed-by: Elijah Newren <newren@gmail.com>
Elijah Newren <newren@gmail.com> writes: > This round looks good to me. > > Reviewed-by: Elijah Newren <newren@gmail.com> Thanks; this kind of change inevitably would involve semantic conflicts with topics in flight, but we've seen Derrick works well together with others in such scenarios already, so let's run with this version and see what happens. Will merge to 'next' until there are new issues found, by the end of the week at the latest. Thanks.
On 4/14/2021 4:44 PM, Junio C Hamano wrote: > Elijah Newren <newren@gmail.com> writes: > >> This round looks good to me. >> >> Reviewed-by: Elijah Newren <newren@gmail.com> > > Thanks; this kind of change inevitably would involve semantic > conflicts with topics in flight, but we've seen Derrick works well > together with others in such scenarios already, so let's run with > this version and see what happens. Thanks! Semantic conflicts like the one in mt/add-rm-sparse-checkout won't show up until I start relaxing command_requires_full_index, so I'll need to be careful at those points. But I'll keep a lookout for other issues contributors have when integrating across this change. > Will merge to 'next' until there are new issues found, by the end of > the week at the latest. That timeline works for me. -Stolee
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 ds/sparse-index. 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 v3 ============= * I updated based on Elijah's feedback. * One new patch splits out a change that Elijah (rightfully) pointed out did not belong with the patch it was originally in. I gave it time to see if any other comments came in, but it looks like review stabilized. I probably waited a bit longer than I should have. 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 (26): 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 name-hash: don't add directories to name_hash 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 | 11 +++- pathspec.c | 8 ++- pathspec.h | 6 +- read-cache.c | 35 ++++++++++-- resolve-undo.c | 4 ++ revision.c | 2 + sparse-index.c | 73 ++++++++++++++++++++++++ sparse-index.h | 14 ++++- submodule.c | 6 +- submodule.h | 6 +- 32 files changed, 273 insertions(+), 73 deletions(-) base-commit: c9e40ae8ec41c5566e5849a87c969fa81ef49fcd Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-906%2Fderrickstolee%2Fsparse-index%2Fprotections-v3 Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-906/derrickstolee/sparse-index/protections-v3 Pull-Request: https://github.com/gitgitgadget/git/pull/906 Range-diff vs v2: 1: 7484e085e342 = 1: 4731f610ba6e sparse-index: API protection strategy 2: 098b2c9ef352 = 2: d3a92538edb6 *: remove 'const' qualifier for struct index_state 3: 737d27e18d64 = 3: f4b77aa18b93 read-cache: expand on query into sparse-directory entry 4: db5c100f3e2b = 4: da17774a53c5 cache: move ensure_full_index() to cache.h 5: 4a5fc2eb5a9f = 5: b59c9f482828 add: ensure full index 6: 11c38f7277c5 = 6: 0082855b5961 checkout-index: ensure full index 7: fd04adbb3f79 = 7: e2ac527143ff checkout: ensure full index 8: 65704f39edc9 = 8: 1a3b51fd3c4b commit: ensure full index 9: 739f3fe9edf2 = 9: 8c61d40dfe01 difftool: ensure full index 10: 779a86ad1ec4 = 10: 45b603379422 fsck: ensure full index 11: 8c0d377054fa = 11: 97124e9fdc7f grep: ensure full index 12: beaa1467cabb = 12: b00e214515e8 ls-files: ensure full index 13: 73684141fcff = 13: 6497f2ce225b merge-index: ensure full index 14: 6ea81a49c6b5 = 14: 175f3bc6b336 rm: ensure full index 15: 49ca5ed05c8d = 15: daa77e84e0e2 stash: ensure full index 16: 9c4bb187c15d = 16: 8c5336964d9b update-index: ensure full index 17: fae4c078c3ef = 17: 08a62c23c8f7 dir: ensure full index 18: 2b9180ee77d3 = 18: 825ebceee508 entry: ensure full index 19: 1e3f6085a405 = 19: 3673db517235 merge-recursive: ensure full index 20: e62a597a9725 = 20: 4d3f6de29a63 pathspec: ensure full index 21: ebfffdbdd6ad = 21: bda9cab15966 read-cache: ensure full index 22: 495b07a87973 = 22: 38f295a41ec1 resolve-undo: ensure full index 23: 3144114d1a75 = 23: f928e104f0d3 revision: ensure full index -: ------------ > 24: 5fd83dcf2747 name-hash: don't add directories to name_hash 24: d52c72b4a7b9 ! 25: 335fec3676a0 sparse-index: expand_to_path() @@ sparse-index.c: void ensure_full_index(struct index_state *istate) + path_mutable.len, icase)) { + /* + * We found a parent directory in the name-hash -+ * hashtable, which means that this entry could -+ * exist within a sparse-directory entry. Expand -+ * accordingly. ++ * hashtable, because only sparse directory entries ++ * have a trailing '/' character. Since "path" wasn't ++ * in the index, perhaps it exists within this ++ * sparse-directory. Expand accordingly. + */ + ensure_full_index(istate); + break; 25: 7e2d3fae9a2a ! 26: 1f3af8a886e5 name-hash: use expand_to_path() @@ name-hash.c struct dir_entry { struct hashmap_entry ent; -@@ name-hash.c: static void hash_index_entry(struct index_state *istate, struct cache_entry *ce) - if (ce->ce_flags & CE_HASHED) - return; - ce->ce_flags |= CE_HASHED; -+ -+ if (S_ISSPARSEDIR(ce->ce_mode)) { -+ add_dir_entry(istate, ce); -+ return; -+ } -+ - hashmap_entry_init(&ce->ent, memihash(ce->name, ce_namelen(ce))); - hashmap_add(&istate->name_hash, &ce->ent); - @@ name-hash.c: int index_dir_exists(struct index_state *istate, const char *name, int namelen) struct dir_entry *dir;