git/sparse-index.c, branch v2.33.6

sparse-index: copy dir_hash in ensure_full_index()

2021-08-30T16:24:12Z

Copy the 'index_state->dir_hash' back to the real istate after expanding a sparse index. A crash was observed in 'git status' during some hashmap lookups with corrupted hashmap entries. During an index expansion, new cache-entries are added to the 'index_state->name_hash' and the 'dir_hash' in a temporary 'index_state' variable 'full'. However, only the 'name_hash' hashmap from this temp variable was copied back into the real 'istate' variable. The original copy of the 'dir_hash' was incorrectly preserved. If the table in the 'full->dir_hash' hashmap were realloced, the stale version (in 'istate') would be corrupted. The test suite does not operate on index sizes sufficiently large to trigger this reallocation, so they do not cover this behavior. Increasing the test suite to cover such scale is fragile and likely wasteful. Signed-off-by: Jeff Hostetler Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano

sparse-index: recompute cache-tree

2021-07-14T22:05:53Z

When some commands run with command_requires_full_index=1, then the index can get in a state where the in-memory cache tree is actually equal to the sparse index's cache tree instead of the full one. This results in incorrect entry_count values. By clearing the cache tree before converting to sparse, we avoid this issue. Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano

fsmonitor: integrate with sparse index

2021-07-14T20:42:49Z

If we need to expand a sparse-index into a full one, then the FS Monitor bitmap is going to be incorrect. Ensure that we start fresh at such an event. While this is currently a performance drawback, the eventual hope of the sparse-index feature is that these expansions will be rare and hence we will be able to keep the FS Monitor data accurate across multiple Git commands. These tests are added to demonstrate that the behavior is the same across a full index and a sparse index, but also that file modifications to a tracked directory outside of the sparse cone will trigger ensure_full_index(). Reviewed-by: Elijah Newren Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano

sparse-index: include EXTENDED flag when expanding

2021-07-14T20:42:21Z

When creating a full index from a sparse one, we create cache entries for every blob within a given sparse directory entry. These are correctly marked with the CE_SKIP_WORKTREE flag, but the CE_EXTENDED flag is not included. The CE_EXTENDED flag would exist if we loaded a full index from disk with these entries marked with CE_SKIP_WORKTREE, so we can add the flag here to be consistent. This allows us to directly compare the flags present in cache entries when testing the sparse-index feature, but has no significance to its correctness in the user-facing functionality. Reviewed-by: Elijah Newren Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano

sparse-index: skip indexes with unmerged entries

2021-07-14T20:42:21Z

The sparse-index format is designed to be compatible with merge conflicts, even those outside the sparse-checkout definition. The reason is that when converting a full index to a sparse one, a cache entry with nonzero stage will not be collapsed into a sparse directory entry. However, this behavior was not tested, and a different behavior within convert_to_sparse() fails in this scenario. Specifically, cache_tree_update() will fail when unmerged entries exist. convert_to_sparse_rec() uses the cache-tree data to recursively walk the tree structure, but also to compute the OIDs used in the sparse-directory entries. Add an index scan to convert_to_sparse() that will detect if these merge conflict entries exist and skip the conversion before trying to update the cache-tree. This is marked as NEEDSWORK because this can be removed with a suitable update to cache_tree_update() or a similar method that can construct a cache-tree with invalid nodes, but still allow creating the nodes necessary for creating sparse directory entries. It is possible that in the future we will not need to make such an update, since if we do not expand a sparse-index into a full one, this conversion does not need to happen. Thus, this can be deferred until the merge machinery is made to integrate with the sparse-index. Reviewed-by: Elijah Newren Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano

Merge branch 'ds/sparse-index-protections'

2021-05-20T20:50:38Z

Fix access to uninitialized piece of memory, introduced during this cycle. * ds/sparse-index-protections: sparse-index: fix uninitialized jump

sparse-index: fix uninitialized jump

2021-05-17T21:29:17Z

While testing the sparse-index, I verified a test with --valgrind and it complained about an uninitialized value being used in a jump in the path_matches_pattern_list() method. The line was this one: if (*dtype == DT_UNKNOWN) In the call stack, the culprit was the initialization of the dtype variable in convert_to_sparse_rec(). Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano

sparse-index.c: remove set_index_sparse_config()

2021-05-06T03:53:46Z

Remove the set_index_sparse_config() function by folding it into set_sparse_index_config(), which was its only user. Since 122ba1f7b52 (sparse-checkout: toggle sparse index from builtin, 2021-03-30) the flow of this code hasn't made much sense, we'd get "enabled" in set_sparse_index_config(), proceed to call set_index_sparse_config() with it. There we'd call prepare_repo_settings() and set "repo->settings.sparse_index = 1", only to needlessly call prepare_repo_settings() again in set_sparse_index_config() (where it would early abort), and finally setting "repo->settings.sparse_index = enabled". Instead we can just call prepare_repo_settings() once, and set the variable to "enabled" in the first place. Signed-off-by: Ævar Arnfjörð Bjarmason Signed-off-by: Junio C Hamano

sparse-index: expand_to_path()

2021-04-14T20:47:54Z

Some users of the index API have a specific path they are looking for, but choose to use index_file_exists() to rely on the name-hash hashtable instead of doing binary search with index_name_pos(). These users only need to know a yes/no answer, not a position within the cache array. When the index is sparse, the name-hash hash table does not contain the full list of paths within sparse directories. It _does_ contain the directory names for the sparse-directory entries. Create a helper function, expand_to_path(), for intended use with the name-hash hashtable functions. The integration with name-hash.c will follow in a later change. The solution here is to use ensure_full_index() when we determine that the requested path is within a sparse directory entry. This will populate the name-hash hashtable as the index is recomputed from scratch. There may be cases where the caller is trying to find an untracked path that is not in the index but also is not within a sparse directory entry. We want to minimize the overhead for these requests. If we used index_name_pos() to find the insertion order of the path, then we could determine from that position if a sparse-directory exists. (In fact, just calling index_name_pos() in that case would lead to expanding the index to a full index.) However, this takes O(log N) time where N is the number of cache entries. To keep the performance of this call based mostly on the input string, use index_file_exists() to look for the ancestors of the path. Using the heuristic that a sparse directory is likely to have a small number of parent directories, we start from the bottom and build up. Use a string buffer to allow mutating the path name to terminate after each slash for each hashset test. Signed-off-by: Derrick Stolee Reviewed-by: Elijah Newren Signed-off-by: Junio C Hamano

cache-tree: integrate with sparse directory entries

2021-03-30T19:57:48Z

The cache-tree extension was previously disabled with sparse indexes. However, the cache-tree is an important performance feature for commands like 'git status' and 'git add'. Integrate it with sparse directory entries. When writing a sparse index, completely clear and recalculate the cache tree. By starting from scratch, the only integration necessary is to check if we hit a sparse directory entry and create a leaf of the cache-tree that has an entry_count of one and no subtrees. Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano