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 any other previous ancestor)
does not exist, then we already know the file cannot exist and do not
need to lstat() it separately.
Granted, the cost of ensure_skip_worktree_means_skip_worktree() might
be considered a bit high for non-cone mode since it might now lstat()
every SKIP_WORKTREE path when the index is loaded (an O(N) cost, with
N the number of SKIP_WORKTREE paths), but non-cone mode users already
have to deal with the O(N*M) cost (with N=the number of tracked files
and M=the number of sparsity patterns), so this should be reasonable.
Signed-off-by: Elijah Newren <newren@xxxxxxxxx>
---
sparse-index.c | 105 ++++++++++++++++++++++++++++++++++++++++++++++++-
1 file changed, 103 insertions(+), 2 deletions(-)
diff --git a/sparse-index.c b/sparse-index.c
index 79d50e444c..608782e255 100644
--- a/sparse-index.c
+++ b/sparse-index.c
@@ -341,18 +341,117 @@ void ensure_correct_sparsity(struct index_state *istate)
ensure_full_index(istate);
}
+struct path_cache_entry {
+ struct hashmap_entry ent;
+ const char *path;
+ int path_length;
+ int is_present;
+};
+
+static int path_cache_cmp(const void *unused,
+ const struct hashmap_entry *entry1,
+ const struct hashmap_entry *entry2,
+ const void *also_unused)
+{
+ const struct path_cache_entry *e1, *e2;
+
+ e1 = container_of(entry1, const struct path_cache_entry, ent);
+ e2 = container_of(entry2, const struct path_cache_entry, ent);
+ if (e1->path_length != e2->path_length)
+ return e1->path_length - e2->path_length;
+ return memcmp(e1->path, e2->path, e1->path_length);
+}
+
+static struct path_cache_entry *find_path_cache_entry(struct hashmap *map,
+ const char *str,
+ int str_length)
+{
+ struct path_cache_entry entry;
+ hashmap_entry_init(&entry.ent, memhash(str, str_length));
+ entry.path = str;
+ entry.path_length = str_length;
+ return hashmap_get_entry(map, &entry, ent, NULL);
+}
+
+static void record(struct hashmap *path_cache,
+ struct mem_pool *pool,
+ const char *path,
+ int path_length,
+ int found)
+{
+ struct path_cache_entry *entry;
+
+ entry = mem_pool_alloc(pool, sizeof(*entry));
+ hashmap_entry_init(&entry->ent, memhash(path, path_length));
+ entry->path = path;
+ entry->path_length = path_length;
+ entry->is_present = found;
+ hashmap_add(path_cache, &entry->ent);
+}
+
+static int path_found(struct hashmap *path_cache, struct mem_pool *pool,
+ const char *path, int path_length)
+{
+ struct stat st;
+ int found;
+ const char *dirsep = path + path_length - 1;
+ const char *tmp;
+
+ /* Find directory separator; memrchr is sadly glibc-specific */
+ while (dirsep > path && *dirsep != '/')
+ dirsep--;
+
+ /* If parent of path doesn't exist, no point lstat'ing path... */
+ if (dirsep > path) {
+ struct path_cache_entry *entry;
+ int new_length, parent_found;
+
+ /* First, check if path's parent's existence was cached */
+ new_length = dirsep - path;
+ entry = find_path_cache_entry(path_cache, path, new_length);
+ if (entry)
+ parent_found = entry->is_present;
+ else
+ parent_found = path_found(path_cache, pool,
+ path, new_length);
+
+ if (!parent_found) {
+ /* path can't exist if parent dir doesn't */
+ record(path_cache, pool, path, path_length, 0);
+ return 0;
+ } /* else parent was found so must check path itself too... */
+ }
+
+ /* Okay, parent dir exists, so we have to check original path */
+
+ /* Make sure we have a NUL-terminated string to pass to lstat */
+ tmp = path;
+ if (path[path_length])
+ tmp = mem_pool_strndup(pool, path, path_length);
+ /* Determine if path exists */
+ found = !lstat(tmp, &st);
+
+ record(path_cache, pool, path, path_length, found);
+ return found;
+}
+
void ensure_skip_worktree_means_skip_worktree(struct index_state *istate)
{
+ struct hashmap path_cache = HASHMAP_INIT(path_cache_cmp, NULL);
+ struct mem_pool pool;
+
int i;
+
if (!core_apply_sparse_checkout)
return;
+ mem_pool_init(&pool, 32*1024);
restart:
for (i = 0; i < istate->cache_nr; i++) {
struct cache_entry *ce = istate->cache[i];
- struct stat st;
- if (ce_skip_worktree(ce) && !lstat(ce->name, &st)) {
+ if (ce_skip_worktree(ce) &&
+ path_found(&path_cache, &pool, ce->name, strlen(ce->name))) {
if (S_ISSPARSEDIR(ce->ce_mode)) {
ensure_full_index(istate);
goto restart;
@@ -360,6 +459,8 @@ void ensure_skip_worktree_means_skip_worktree(struct index_state *istate)
ce->ce_flags &= ~CE_SKIP_WORKTREE;
}
}
+ hashmap_clear(&path_cache);
+ mem_pool_discard(&pool, 0);
}
--
2.34.1.442.ge63c19bdd2.dirty
