From 883a7ea0543426d0ecb172c72c8f706348961605 Mon Sep 17 00:00:00 2001 From: Karthik Nayak Date: Tue, 15 Jul 2025 13:28:27 +0200 Subject: ref-cache: remove unused function 'find_ref_entry()' The 'find_ref_entry' function is no longer used, so remove it. Signed-off-by: Karthik Nayak Signed-off-by: Junio C Hamano --- refs/ref-cache.c | 14 -------------- 1 file changed, 14 deletions(-) (limited to 'refs/ref-cache.c') diff --git a/refs/ref-cache.c b/refs/ref-cache.c index c1f1bab1d5..8aaffa8c6b 100644 --- a/refs/ref-cache.c +++ b/refs/ref-cache.c @@ -194,20 +194,6 @@ static struct ref_dir *find_containing_dir(struct ref_dir *dir, return dir; } -struct ref_entry *find_ref_entry(struct ref_dir *dir, const char *refname) -{ - int entry_index; - struct ref_entry *entry; - dir = find_containing_dir(dir, refname); - if (!dir) - return NULL; - entry_index = search_ref_dir(dir, refname, strlen(refname)); - if (entry_index == -1) - return NULL; - entry = dir->entries[entry_index]; - return (entry->flag & REF_DIR) ? NULL : entry; -} - /* * Emit a warning and return true iff ref1 and ref2 have the same name * and the same oid. Die if they have the same name but different -- cgit v1.3 From 2b4648b9190b552e942d93363482bd617a510fc1 Mon Sep 17 00:00:00 2001 From: Karthik Nayak Date: Tue, 15 Jul 2025 13:28:28 +0200 Subject: refs: selectively set prefix in the seek functions The ref iterator exposes a `ref_iterator_seek()` function. The name suggests that this would seek the iterator to a specific reference in some ways similar to how `fseek()` works for the filesystem. However, the function actually sets the prefix for refs iteration. So further iteration would only yield references which match the particular prefix. This is a bit confusing. Let's add a 'flags' field to the function, which when set with the 'REF_ITERATOR_SEEK_SET_PREFIX' flag, will set the prefix for the iteration in-line with the existing behavior. Otherwise, the reference backends will simply seek to the specified reference and clears any previously set prefix. This allows users to start iteration from a specific reference. In the packed and reftable backend, since references are available in a sorted list, the changes are simply setting the prefix if needed. The changes on the files-backend are a little more involved, since the files backend uses the 'ref-cache' mechanism. We move out the existing logic within `cache_ref_iterator_seek()` to `cache_ref_iterator_set_prefix()` which is called when the 'REF_ITERATOR_SEEK_SET_PREFIX' flag is set. We then parse the provided seek string and set the required levels and their indexes to ensure that seeking is possible. Helped-by: Patrick Steinhardt Signed-off-by: Karthik Nayak Signed-off-by: Junio C Hamano --- refs.c | 6 ++-- refs.h | 26 +++++++++------ refs/debug.c | 7 ++-- refs/files-backend.c | 7 ++-- refs/iterator.c | 26 ++++++++------- refs/packed-backend.c | 17 ++++++---- refs/ref-cache.c | 85 ++++++++++++++++++++++++++++++++++++++++++++++--- refs/refs-internal.h | 7 ++-- refs/reftable-backend.c | 21 ++++++++---- 9 files changed, 152 insertions(+), 50 deletions(-) (limited to 'refs/ref-cache.c') diff --git a/refs.c b/refs.c index dce5c49ca2..243e6898b8 100644 --- a/refs.c +++ b/refs.c @@ -2666,12 +2666,12 @@ enum ref_transaction_error refs_verify_refnames_available(struct ref_store *refs if (!initial_transaction) { int ok; - if (!iter) { + if (!iter) iter = refs_ref_iterator_begin(refs, dirname.buf, NULL, 0, DO_FOR_EACH_INCLUDE_BROKEN); - } else if (ref_iterator_seek(iter, dirname.buf) < 0) { + else if (ref_iterator_seek(iter, dirname.buf, + REF_ITERATOR_SEEK_SET_PREFIX) < 0) goto cleanup; - } while ((ok = ref_iterator_advance(iter)) == ITER_OK) { if (skip && diff --git a/refs.h b/refs.h index 7c21aaef3d..e6780a8848 100644 --- a/refs.h +++ b/refs.h @@ -1299,21 +1299,29 @@ struct ref_iterator *refs_ref_iterator_begin( */ int ref_iterator_advance(struct ref_iterator *ref_iterator); +enum ref_iterator_seek_flag { + /* + * When the REF_ITERATOR_SEEK_SET_PREFIX flag is set, the iterator's prefix is + * updated to match the provided string, affecting all subsequent iterations. If + * not, the iterator seeks to the specified reference and clears any previously + * set prefix. + */ + REF_ITERATOR_SEEK_SET_PREFIX = (1 << 0), +}; + /* - * Seek the iterator to the first reference with the given prefix. - * The prefix is matched as a literal string, without regard for path - * separators. If prefix is NULL or the empty string, seek the iterator to the + * Seek the iterator to the first reference matching the given seek string. + * The seek string is matched as a literal string, without regard for path + * separators. If seek is NULL or the empty string, seek the iterator to the * first reference again. * - * This function is expected to behave as if a new ref iterator with the same - * prefix had been created, but allows reuse of iterators and thus may allow - * the backend to optimize. Parameters other than the prefix that have been - * passed when creating the iterator will remain unchanged. + * This function is expected to behave as if a new ref iterator has been + * created, but allows reuse of existing iterators for optimization. * * Returns 0 on success, a negative error code otherwise. */ -int ref_iterator_seek(struct ref_iterator *ref_iterator, - const char *prefix); +int ref_iterator_seek(struct ref_iterator *ref_iterator, const char *refname, + unsigned int flags); /* * If possible, peel the reference currently being viewed by the diff --git a/refs/debug.c b/refs/debug.c index 485e3079d7..da300efaf3 100644 --- a/refs/debug.c +++ b/refs/debug.c @@ -170,12 +170,13 @@ static int debug_ref_iterator_advance(struct ref_iterator *ref_iterator) } static int debug_ref_iterator_seek(struct ref_iterator *ref_iterator, - const char *prefix) + const char *refname, unsigned int flags) { struct debug_ref_iterator *diter = (struct debug_ref_iterator *)ref_iterator; - int res = diter->iter->vtable->seek(diter->iter, prefix); - trace_printf_key(&trace_refs, "iterator_seek: %s: %d\n", prefix ? prefix : "", res); + int res = diter->iter->vtable->seek(diter->iter, refname, flags); + trace_printf_key(&trace_refs, "iterator_seek: %s flags: %d: %d\n", + refname ? refname : "", flags, res); return res; } diff --git a/refs/files-backend.c b/refs/files-backend.c index bf6f89b1d1..8b282f2a60 100644 --- a/refs/files-backend.c +++ b/refs/files-backend.c @@ -929,11 +929,11 @@ static int files_ref_iterator_advance(struct ref_iterator *ref_iterator) } static int files_ref_iterator_seek(struct ref_iterator *ref_iterator, - const char *prefix) + const char *refname, unsigned int flags) { struct files_ref_iterator *iter = (struct files_ref_iterator *)ref_iterator; - return ref_iterator_seek(iter->iter0, prefix); + return ref_iterator_seek(iter->iter0, refname, flags); } static int files_ref_iterator_peel(struct ref_iterator *ref_iterator, @@ -2316,7 +2316,8 @@ static int files_reflog_iterator_advance(struct ref_iterator *ref_iterator) } static int files_reflog_iterator_seek(struct ref_iterator *ref_iterator UNUSED, - const char *prefix UNUSED) + const char *refname UNUSED, + unsigned int flags UNUSED) { BUG("ref_iterator_seek() called for reflog_iterator"); } diff --git a/refs/iterator.c b/refs/iterator.c index 766d96e795..17ef841d8a 100644 --- a/refs/iterator.c +++ b/refs/iterator.c @@ -15,10 +15,10 @@ int ref_iterator_advance(struct ref_iterator *ref_iterator) return ref_iterator->vtable->advance(ref_iterator); } -int ref_iterator_seek(struct ref_iterator *ref_iterator, - const char *prefix) +int ref_iterator_seek(struct ref_iterator *ref_iterator, const char *refname, + unsigned int flags) { - return ref_iterator->vtable->seek(ref_iterator, prefix); + return ref_iterator->vtable->seek(ref_iterator, refname, flags); } int ref_iterator_peel(struct ref_iterator *ref_iterator, @@ -57,7 +57,8 @@ static int empty_ref_iterator_advance(struct ref_iterator *ref_iterator UNUSED) } static int empty_ref_iterator_seek(struct ref_iterator *ref_iterator UNUSED, - const char *prefix UNUSED) + const char *refname UNUSED, + unsigned int flags UNUSED) { return 0; } @@ -224,7 +225,7 @@ error: } static int merge_ref_iterator_seek(struct ref_iterator *ref_iterator, - const char *prefix) + const char *refname, unsigned int flags) { struct merge_ref_iterator *iter = (struct merge_ref_iterator *)ref_iterator; @@ -234,11 +235,11 @@ static int merge_ref_iterator_seek(struct ref_iterator *ref_iterator, iter->iter0 = iter->iter0_owned; iter->iter1 = iter->iter1_owned; - ret = ref_iterator_seek(iter->iter0, prefix); + ret = ref_iterator_seek(iter->iter0, refname, flags); if (ret < 0) return ret; - ret = ref_iterator_seek(iter->iter1, prefix); + ret = ref_iterator_seek(iter->iter1, refname, flags); if (ret < 0) return ret; @@ -407,13 +408,16 @@ static int prefix_ref_iterator_advance(struct ref_iterator *ref_iterator) } static int prefix_ref_iterator_seek(struct ref_iterator *ref_iterator, - const char *prefix) + const char *refname, unsigned int flags) { struct prefix_ref_iterator *iter = (struct prefix_ref_iterator *)ref_iterator; - free(iter->prefix); - iter->prefix = xstrdup_or_null(prefix); - return ref_iterator_seek(iter->iter0, prefix); + + if (flags & REF_ITERATOR_SEEK_SET_PREFIX) { + free(iter->prefix); + iter->prefix = xstrdup_or_null(refname); + } + return ref_iterator_seek(iter->iter0, refname, flags); } static int prefix_ref_iterator_peel(struct ref_iterator *ref_iterator, diff --git a/refs/packed-backend.c b/refs/packed-backend.c index 7fd73a0e6d..5fa4ae6655 100644 --- a/refs/packed-backend.c +++ b/refs/packed-backend.c @@ -1004,19 +1004,23 @@ static int packed_ref_iterator_advance(struct ref_iterator *ref_iterator) } static int packed_ref_iterator_seek(struct ref_iterator *ref_iterator, - const char *prefix) + const char *refname, unsigned int flags) { struct packed_ref_iterator *iter = (struct packed_ref_iterator *)ref_iterator; const char *start; - if (prefix && *prefix) - start = find_reference_location(iter->snapshot, prefix, 0); + if (refname && *refname) + start = find_reference_location(iter->snapshot, refname, 0); else start = iter->snapshot->start; - free(iter->prefix); - iter->prefix = xstrdup_or_null(prefix); + /* Unset any previously set prefix */ + FREE_AND_NULL(iter->prefix); + + if (flags & REF_ITERATOR_SEEK_SET_PREFIX) + iter->prefix = xstrdup_or_null(refname); + iter->pos = start; iter->eof = iter->snapshot->eof; @@ -1194,7 +1198,8 @@ static struct ref_iterator *packed_ref_iterator_begin( iter->repo = ref_store->repo; iter->flags = flags; - if (packed_ref_iterator_seek(&iter->base, prefix) < 0) { + if (packed_ref_iterator_seek(&iter->base, prefix, + REF_ITERATOR_SEEK_SET_PREFIX) < 0) { ref_iterator_free(&iter->base); return NULL; } diff --git a/refs/ref-cache.c b/refs/ref-cache.c index 8aaffa8c6b..1d95b56d40 100644 --- a/refs/ref-cache.c +++ b/refs/ref-cache.c @@ -434,11 +434,9 @@ static int cache_ref_iterator_advance(struct ref_iterator *ref_iterator) } } -static int cache_ref_iterator_seek(struct ref_iterator *ref_iterator, - const char *prefix) +static int cache_ref_iterator_set_prefix(struct cache_ref_iterator *iter, + const char *prefix) { - struct cache_ref_iterator *iter = - (struct cache_ref_iterator *)ref_iterator; struct cache_ref_iterator_level *level; struct ref_dir *dir; @@ -469,6 +467,82 @@ static int cache_ref_iterator_seek(struct ref_iterator *ref_iterator, return 0; } +static int cache_ref_iterator_seek(struct ref_iterator *ref_iterator, + const char *refname, unsigned int flags) +{ + struct cache_ref_iterator *iter = + (struct cache_ref_iterator *)ref_iterator; + + if (flags & REF_ITERATOR_SEEK_SET_PREFIX) { + return cache_ref_iterator_set_prefix(iter, refname); + } else if (refname && *refname) { + struct cache_ref_iterator_level *level; + const char *slash = refname; + struct ref_dir *dir; + + dir = get_ref_dir(iter->cache->root); + + if (iter->prime_dir) + prime_ref_dir(dir, refname); + + iter->levels_nr = 1; + level = &iter->levels[0]; + level->index = -1; + level->dir = dir; + + /* Unset any previously set prefix */ + FREE_AND_NULL(iter->prefix); + + /* + * Breakdown the provided seek path and assign the correct + * indexing to each level as needed. + */ + do { + int len, idx; + int cmp = 0; + + sort_ref_dir(dir); + + slash = strchr(slash, '/'); + len = slash ? slash - refname : (int)strlen(refname); + + for (idx = 0; idx < dir->nr; idx++) { + cmp = strncmp(refname, dir->entries[idx]->name, len); + if (cmp <= 0) + break; + } + /* don't overflow the index */ + idx = idx >= dir->nr ? dir->nr - 1 : idx; + + if (slash) + slash = slash + 1; + + level->index = idx; + if (dir->entries[idx]->flag & REF_DIR) { + /* push down a level */ + dir = get_ref_dir(dir->entries[idx]); + + ALLOC_GROW(iter->levels, iter->levels_nr + 1, + iter->levels_alloc); + level = &iter->levels[iter->levels_nr++]; + level->dir = dir; + level->index = -1; + } else { + /* reduce the index so the leaf node is iterated over */ + if (cmp <= 0 && !slash) + level->index = idx - 1; + /* + * while the seek path may not be exhausted, our + * match is exhausted at a leaf node. + */ + break; + } + } while (slash); + } + + return 0; +} + static int cache_ref_iterator_peel(struct ref_iterator *ref_iterator, struct object_id *peeled) { @@ -509,7 +583,8 @@ struct ref_iterator *cache_ref_iterator_begin(struct ref_cache *cache, iter->cache = cache; iter->prime_dir = prime_dir; - if (cache_ref_iterator_seek(&iter->base, prefix) < 0) { + if (cache_ref_iterator_seek(&iter->base, prefix, + REF_ITERATOR_SEEK_SET_PREFIX) < 0) { ref_iterator_free(&iter->base); return NULL; } diff --git a/refs/refs-internal.h b/refs/refs-internal.h index 03f5df04d5..40c1c0f93d 100644 --- a/refs/refs-internal.h +++ b/refs/refs-internal.h @@ -353,11 +353,12 @@ void base_ref_iterator_init(struct ref_iterator *iter, typedef int ref_iterator_advance_fn(struct ref_iterator *ref_iterator); /* - * Seek the iterator to the first reference matching the given prefix. Should - * behave the same as if a new iterator was created with the same prefix. + * Seek the iterator to the first matching reference. If the + * REF_ITERATOR_SEEK_SET_PREFIX flag is set, it would behave the same as if a + * new iterator was created with the provided refname as prefix. */ typedef int ref_iterator_seek_fn(struct ref_iterator *ref_iterator, - const char *prefix); + const char *refname, unsigned int flags); /* * Peels the current ref, returning 0 for success or -1 for failure. diff --git a/refs/reftable-backend.c b/refs/reftable-backend.c index 4c3817f4ec..c3d48cc412 100644 --- a/refs/reftable-backend.c +++ b/refs/reftable-backend.c @@ -719,15 +719,20 @@ static int reftable_ref_iterator_advance(struct ref_iterator *ref_iterator) } static int reftable_ref_iterator_seek(struct ref_iterator *ref_iterator, - const char *prefix) + const char *refname, unsigned int flags) { struct reftable_ref_iterator *iter = (struct reftable_ref_iterator *)ref_iterator; - free(iter->prefix); - iter->prefix = xstrdup_or_null(prefix); - iter->prefix_len = prefix ? strlen(prefix) : 0; - iter->err = reftable_iterator_seek_ref(&iter->iter, prefix); + /* Unset any previously set prefix */ + FREE_AND_NULL(iter->prefix); + iter->prefix_len = 0; + + if (flags & REF_ITERATOR_SEEK_SET_PREFIX) { + iter->prefix = xstrdup_or_null(refname); + iter->prefix_len = refname ? strlen(refname) : 0; + } + iter->err = reftable_iterator_seek_ref(&iter->iter, refname); return iter->err; } @@ -839,7 +844,8 @@ static struct reftable_ref_iterator *ref_iterator_for_stack(struct reftable_ref_ if (ret) goto done; - ret = reftable_ref_iterator_seek(&iter->base, prefix); + ret = reftable_ref_iterator_seek(&iter->base, prefix, + REF_ITERATOR_SEEK_SET_PREFIX); if (ret) goto done; @@ -2042,7 +2048,8 @@ static int reftable_reflog_iterator_advance(struct ref_iterator *ref_iterator) } static int reftable_reflog_iterator_seek(struct ref_iterator *ref_iterator UNUSED, - const char *prefix UNUSED) + const char *refname UNUSED, + unsigned int flags UNUSED) { BUG("reftable reflog iterator cannot be seeked"); return -1; -- cgit v1.3 From 9201261a70b5d325b344036de15901a4064d66c0 Mon Sep 17 00:00:00 2001 From: Karthik Nayak Date: Fri, 25 Jul 2025 00:11:36 +0200 Subject: ref-cache: set prefix_state when seeking In 090eb5336c (refs: selectively set prefix in the seek functions, 2025-07-15) we separated the seeking functionality of reference iterators from the functionality to set prefix to an iterator. This allows users of ref iterators to seek to a particular reference to provide pagination support. The files-backend, uses the ref-cache iterator to iterate over loose refs. The iterator tracks directories and entries already processed via a stack of levels. Each level corresponds to a directory under the files backend. New levels are added to the stack, and when all entries from a level is yielded, the corresponding level is popped from the stack. To accommodate seeking, we need to populate and traverse the levels to stop the requested seek marker at the appropriate level and its entry index. Each level also contains a 'prefix_state' which is used for prefix matching, this allows the iterator to skip levels/entries which don't match a prefix. The default value of 'prefix_state' is PREFIX_CONTAINS_DIR, which yields all entries within a level. When purely seeking without prefix matching, we want to yield all entries. The commit however, skips setting the value explicitly. This causes the MemorySanitizer to issue a 'use-of-uninitialized-value' error when running 't/t6302-for-each-ref-filter'. Set the value explicitly to avoid to fix the issue. Reported-by: Kyle Lippincott Helped-by: Kyle Lippincott Helped-by: Jeff King Signed-off-by: Karthik Nayak Signed-off-by: Junio C Hamano --- refs/ref-cache.c | 1 + 1 file changed, 1 insertion(+) (limited to 'refs/ref-cache.c') diff --git a/refs/ref-cache.c b/refs/ref-cache.c index 1d95b56d40..ceef3a2008 100644 --- a/refs/ref-cache.c +++ b/refs/ref-cache.c @@ -527,6 +527,7 @@ static int cache_ref_iterator_seek(struct ref_iterator *ref_iterator, level = &iter->levels[iter->levels_nr++]; level->dir = dir; level->index = -1; + level->prefix_state = PREFIX_CONTAINS_DIR; } else { /* reduce the index so the leaf node is iterated over */ if (cmp <= 0 && !slash) -- cgit v1.3