From 351f592e1d6668f07529d30f05c04725a0a17b59 Mon Sep 17 00:00:00 2001 From: Patrick Steinhardt Date: Wed, 12 Mar 2025 16:56:11 +0100 Subject: refs/reftable: batch refname availability checks Refactor the "reftable" backend to batch the availability check for refnames. This does not yet have an effect on performance as `refs_verify_refnames_available()` effectively still performs the availability check for each refname individually. But this will be optimized in subsequent commits, where we learn to optimize some parts of the logic when checking multiple refnames for availability. Signed-off-by: Patrick Steinhardt Signed-off-by: Junio C Hamano --- refs/reftable-backend.c | 15 +++++++++------ 1 file changed, 9 insertions(+), 6 deletions(-) (limited to 'refs') diff --git a/refs/reftable-backend.c b/refs/reftable-backend.c index 7e90e13f74..546861d64c 100644 --- a/refs/reftable-backend.c +++ b/refs/reftable-backend.c @@ -1069,6 +1069,7 @@ static int reftable_be_transaction_prepare(struct ref_store *ref_store, reftable_be_downcast(ref_store, REF_STORE_WRITE|REF_STORE_MAIN, "ref_transaction_prepare"); struct strbuf referent = STRBUF_INIT, head_referent = STRBUF_INIT; struct string_list affected_refnames = STRING_LIST_INIT_NODUP; + struct string_list refnames_to_check = STRING_LIST_INIT_NODUP; struct reftable_transaction_data *tx_data = NULL; struct reftable_backend *be; struct object_id head_oid; @@ -1224,12 +1225,7 @@ static int reftable_be_transaction_prepare(struct ref_store *ref_store, * can output a proper error message instead of failing * at a later point. */ - ret = refs_verify_refname_available(ref_store, u->refname, - &affected_refnames, NULL, - transaction->flags & REF_TRANSACTION_FLAG_INITIAL, - err); - if (ret < 0) - goto done; + string_list_append(&refnames_to_check, u->refname); /* * There is no need to write the reference deletion @@ -1379,6 +1375,12 @@ static int reftable_be_transaction_prepare(struct ref_store *ref_store, } } + ret = refs_verify_refnames_available(ref_store, &refnames_to_check, &affected_refnames, NULL, + transaction->flags & REF_TRANSACTION_FLAG_INITIAL, + err); + if (ret < 0) + goto done; + transaction->backend_data = tx_data; transaction->state = REF_TRANSACTION_PREPARED; @@ -1394,6 +1396,7 @@ done: string_list_clear(&affected_refnames, 0); strbuf_release(&referent); strbuf_release(&head_referent); + string_list_clear(&refnames_to_check, 0); return ret; } -- cgit v1.3-5-g9baa From 6c90726bebfd8ec4dd429f1fad9d00112b1b6603 Mon Sep 17 00:00:00 2001 From: Patrick Steinhardt Date: Wed, 12 Mar 2025 16:56:12 +0100 Subject: refs/files: batch refname availability checks for normal transactions Same as the "reftable" backend that we have adapted in the preceding commit to use batched refname availability checks we can also do so for the "files" backend. Things are a bit more intricate here though, as we call `refs_verify_refname_available()` in a set of different contexts: 1. `lock_raw_ref()` when it hits either EEXISTS or EISDIR when creating a new reference, mostly to create a nice, user-readable error message. This is nothing we have to care about too much, as we only hit this code path at most once when we hit a conflict. 2. `lock_raw_ref()` when it _could_ create the lockfile to check whether it is conflicting with any packed refs. In the general case, this code path will be hit once for every (successful) reference update. 3. `lock_ref_oid_basic()`, but it is only executed when copying or renaming references or when expiring reflogs. It will thus not be called in contexts where we have many references queued up. 4. `refs_refname_ref_available()`, but again only when copying or renaming references. It is thus not interesting due to the same reason as the previous case. 5. `files_transaction_finish_initial()`, which is only executed when creating a new repository or migrating references. So out of these, only (2) and (5) are viable candidates to use the batched checks. Adapt `lock_raw_ref()` accordingly by queueing up reference names that need to be checked for availability and then checking them after we have processed all updates. This check is done before we (optionally) lock the `packed-refs` file, which is somewhat flawed because it means that the `packed-refs` could still change after the availability check and thus create an undetected conflict. But unconditionally locking the file would change semantics that users are likely to rely on, so we keep the current locking sequence intact, even if it's suboptmial. The refactoring of `files_transaction_finish_initial()` will be done in the next commit. Signed-off-by: Patrick Steinhardt Signed-off-by: Junio C Hamano --- refs/files-backend.c | 42 +++++++++++++++++++++++++++++++----------- 1 file changed, 31 insertions(+), 11 deletions(-) (limited to 'refs') diff --git a/refs/files-backend.c b/refs/files-backend.c index 29f08dced4..f798d8dae3 100644 --- a/refs/files-backend.c +++ b/refs/files-backend.c @@ -678,6 +678,7 @@ static void unlock_ref(struct ref_lock *lock) */ static int lock_raw_ref(struct files_ref_store *refs, const char *refname, int mustexist, + struct string_list *refnames_to_check, const struct string_list *extras, struct ref_lock **lock_p, struct strbuf *referent, @@ -855,16 +856,11 @@ retry: } /* - * If the ref did not exist and we are creating it, - * make sure there is no existing packed ref that - * conflicts with refname: + * If the ref did not exist and we are creating it, we have to + * make sure there is no existing packed ref that conflicts + * with refname. This check is deferred so that we can batch it. */ - if (refs_verify_refname_available( - refs->packed_ref_store, refname, - extras, NULL, 0, err)) { - ret = TRANSACTION_NAME_CONFLICT; - goto error_return; - } + string_list_append(refnames_to_check, refname); } ret = 0; @@ -2569,6 +2565,7 @@ static int lock_ref_for_update(struct files_ref_store *refs, struct ref_update *update, struct ref_transaction *transaction, const char *head_ref, + struct string_list *refnames_to_check, struct string_list *affected_refnames, struct strbuf *err) { @@ -2597,7 +2594,7 @@ static int lock_ref_for_update(struct files_ref_store *refs, lock->count++; } else { ret = lock_raw_ref(refs, update->refname, mustexist, - affected_refnames, + refnames_to_check, affected_refnames, &lock, &referent, &update->type, err); if (ret) { @@ -2811,6 +2808,7 @@ static int files_transaction_prepare(struct ref_store *ref_store, size_t i; int ret = 0; struct string_list affected_refnames = STRING_LIST_INIT_NODUP; + struct string_list refnames_to_check = STRING_LIST_INIT_NODUP; char *head_ref = NULL; int head_type; struct files_transaction_backend_data *backend_data; @@ -2898,7 +2896,8 @@ static int files_transaction_prepare(struct ref_store *ref_store, struct ref_update *update = transaction->updates[i]; ret = lock_ref_for_update(refs, update, transaction, - head_ref, &affected_refnames, err); + head_ref, &refnames_to_check, + &affected_refnames, err); if (ret) goto cleanup; @@ -2930,6 +2929,26 @@ static int files_transaction_prepare(struct ref_store *ref_store, } } + /* + * Verify that none of the loose reference that we're about to write + * conflict with any existing packed references. Ideally, we'd do this + * check after the packed-refs are locked so that the file cannot + * change underneath our feet. But introducing such a lock now would + * probably do more harm than good as users rely on there not being a + * global lock with the "files" backend. + * + * Another alternative would be to do the check after the (optional) + * lock, but that would extend the time we spend in the globally-locked + * state. + * + * So instead, we accept the race for now. + */ + if (refs_verify_refnames_available(refs->packed_ref_store, &refnames_to_check, + &affected_refnames, NULL, 0, err)) { + ret = TRANSACTION_NAME_CONFLICT; + goto cleanup; + } + if (packed_transaction) { if (packed_refs_lock(refs->packed_ref_store, 0, err)) { ret = TRANSACTION_GENERIC_ERROR; @@ -2972,6 +2991,7 @@ static int files_transaction_prepare(struct ref_store *ref_store, cleanup: free(head_ref); string_list_clear(&affected_refnames, 0); + string_list_clear(&refnames_to_check, 0); if (ret) files_transaction_cleanup(refs, transaction); -- cgit v1.3-5-g9baa From 268ea8515cd11bd0f3f8c4d64373121058c3fac2 Mon Sep 17 00:00:00 2001 From: Patrick Steinhardt Date: Wed, 12 Mar 2025 16:56:13 +0100 Subject: refs/files: batch refname availability checks for initial transactions The "files" backend explicitly carves out special logic for its initial transaction so that it can avoid writing out every single reference as a loose reference. While the assumption is that there shouldn't be any preexisting references, we still have to verify that none of the newly written references will conflict with any other new reference in the same transaction. Refactor the initial transaction to use batched refname availability checks. This does not yet have an effect on performance as we still call `refs_verify_refname_available()` in a loop. But this will change in subsequent commits and then impact performance when cloning a repository with many references or when migrating references to the "files" format. This will improve performance when cloning a repository with many references or when migrating references from any format to the "files" format once the availability checks have learned to optimize checks for many references in a subsequent commit. Signed-off-by: Patrick Steinhardt Signed-off-by: Junio C Hamano --- refs/files-backend.c | 23 ++++++++++++++++------- 1 file changed, 16 insertions(+), 7 deletions(-) (limited to 'refs') diff --git a/refs/files-backend.c b/refs/files-backend.c index f798d8dae3..ab6f0af550 100644 --- a/refs/files-backend.c +++ b/refs/files-backend.c @@ -3056,6 +3056,7 @@ static int files_transaction_finish_initial(struct files_ref_store *refs, size_t i; int ret = 0; struct string_list affected_refnames = STRING_LIST_INIT_NODUP; + struct string_list refnames_to_check = STRING_LIST_INIT_NODUP; struct ref_transaction *packed_transaction = NULL; struct ref_transaction *loose_transaction = NULL; @@ -3105,11 +3106,7 @@ static int files_transaction_finish_initial(struct files_ref_store *refs, !is_null_oid(&update->old_oid)) BUG("initial ref transaction with old_sha1 set"); - if (refs_verify_refname_available(&refs->base, update->refname, - &affected_refnames, NULL, 1, err)) { - ret = TRANSACTION_NAME_CONFLICT; - goto cleanup; - } + string_list_append(&refnames_to_check, update->refname); /* * packed-refs don't support symbolic refs, root refs and reflogs, @@ -3145,8 +3142,19 @@ static int files_transaction_finish_initial(struct files_ref_store *refs, } } - if (packed_refs_lock(refs->packed_ref_store, 0, err) || - ref_transaction_commit(packed_transaction, err)) { + if (packed_refs_lock(refs->packed_ref_store, 0, err)) { + ret = TRANSACTION_GENERIC_ERROR; + goto cleanup; + } + + if (refs_verify_refnames_available(&refs->base, &refnames_to_check, + &affected_refnames, NULL, 1, err)) { + packed_refs_unlock(refs->packed_ref_store); + ret = TRANSACTION_NAME_CONFLICT; + goto cleanup; + } + + if (ref_transaction_commit(packed_transaction, err)) { ret = TRANSACTION_GENERIC_ERROR; goto cleanup; } @@ -3167,6 +3175,7 @@ cleanup: ref_transaction_free(packed_transaction); transaction->state = REF_TRANSACTION_CLOSED; string_list_clear(&affected_refnames, 0); + string_list_clear(&refnames_to_check, 0); return ret; } -- cgit v1.3-5-g9baa From cec2b6f55a805c010d2acc81abf4cbc41b712130 Mon Sep 17 00:00:00 2001 From: Patrick Steinhardt Date: Wed, 12 Mar 2025 16:56:15 +0100 Subject: refs/iterator: separate lifecycle from iteration The ref and reflog iterators have their lifecycle attached to iteration: once the iterator reaches its end, it is automatically released and the caller doesn't have to care about that anymore. When the iterator should be released before it has been exhausted, callers must explicitly abort the iterator via `ref_iterator_abort()`. This lifecycle is somewhat unusual in the Git codebase and creates two problems: - Callsites need to be very careful about when exactly they call `ref_iterator_abort()`, as calling the function is only valid when the iterator itself still is. This leads to somewhat awkward calling patterns in some situations. - It is impossible to reuse iterators and re-seek them to a different prefix. This feature isn't supported by any iterator implementation except for the reftable iterators anyway, but if it was implemented it would allow us to optimize cases where we need to search for specific references repeatedly by reusing internal state. Detangle the lifecycle from iteration so that we don't deallocate the iterator anymore once it is exhausted. Instead, callers are now expected to always call a newly introduce `ref_iterator_free()` function that deallocates the iterator and its internal state. Note that the `dir_iterator` is somewhat special because it does not implement the `ref_iterator` interface, but is only used to implement other iterators. Consequently, we have to provide `dir_iterator_free()` instead of `dir_iterator_release()` as the allocated structure itself is managed by the `dir_iterator` interfaces, as well, and not freed by `ref_iterator_free()` like in all the other cases. While at it, drop the return value of `ref_iterator_abort()`, which wasn't really required by any of the iterator implementations anyway. Furthermore, stop calling `base_ref_iterator_free()` in any of the backends, but instead call it in `ref_iterator_free()`. Signed-off-by: Patrick Steinhardt Signed-off-by: Junio C Hamano --- builtin/clone.c | 2 + dir-iterator.c | 24 +++++------ dir-iterator.h | 11 ++--- iterator.h | 2 +- refs.c | 7 ++- refs/debug.c | 9 ++-- refs/files-backend.c | 36 +++++----------- refs/iterator.c | 100 +++++++++++++++---------------------------- refs/packed-backend.c | 27 ++++++------ refs/ref-cache.c | 9 ++-- refs/refs-internal.h | 29 ++++--------- refs/reftable-backend.c | 34 ++++----------- t/helper/test-dir-iterator.c | 1 + 13 files changed, 105 insertions(+), 186 deletions(-) (limited to 'refs') diff --git a/builtin/clone.c b/builtin/clone.c index f9a2ecbe9c..add9d8600c 100644 --- a/builtin/clone.c +++ b/builtin/clone.c @@ -342,6 +342,8 @@ static void copy_or_link_directory(struct strbuf *src, struct strbuf *dest, strbuf_setlen(src, src_len); die(_("failed to iterate over '%s'"), src->buf); } + + dir_iterator_free(iter); } static void clone_local(const char *src_repo, const char *dest_repo) diff --git a/dir-iterator.c b/dir-iterator.c index de619846f2..857e1d9bda 100644 --- a/dir-iterator.c +++ b/dir-iterator.c @@ -193,9 +193,9 @@ int dir_iterator_advance(struct dir_iterator *dir_iterator) if (S_ISDIR(iter->base.st.st_mode) && push_level(iter)) { if (errno != ENOENT && iter->flags & DIR_ITERATOR_PEDANTIC) - goto error_out; + return ITER_ERROR; if (iter->levels_nr == 0) - goto error_out; + return ITER_ERROR; } /* Loop until we find an entry that we can give back to the caller. */ @@ -211,11 +211,11 @@ int dir_iterator_advance(struct dir_iterator *dir_iterator) int ret = next_directory_entry(level->dir, iter->base.path.buf, &de); if (ret < 0) { if (iter->flags & DIR_ITERATOR_PEDANTIC) - goto error_out; + return ITER_ERROR; continue; } else if (ret > 0) { if (pop_level(iter) == 0) - return dir_iterator_abort(dir_iterator); + return ITER_DONE; continue; } @@ -223,7 +223,7 @@ int dir_iterator_advance(struct dir_iterator *dir_iterator) } else { if (level->entries_idx >= level->entries.nr) { if (pop_level(iter) == 0) - return dir_iterator_abort(dir_iterator); + return ITER_DONE; continue; } @@ -232,22 +232,21 @@ int dir_iterator_advance(struct dir_iterator *dir_iterator) if (prepare_next_entry_data(iter, name)) { if (errno != ENOENT && iter->flags & DIR_ITERATOR_PEDANTIC) - goto error_out; + return ITER_ERROR; continue; } return ITER_OK; } - -error_out: - dir_iterator_abort(dir_iterator); - return ITER_ERROR; } -int dir_iterator_abort(struct dir_iterator *dir_iterator) +void dir_iterator_free(struct dir_iterator *dir_iterator) { struct dir_iterator_int *iter = (struct dir_iterator_int *)dir_iterator; + if (!iter) + return; + for (; iter->levels_nr; iter->levels_nr--) { struct dir_iterator_level *level = &iter->levels[iter->levels_nr - 1]; @@ -266,7 +265,6 @@ int dir_iterator_abort(struct dir_iterator *dir_iterator) free(iter->levels); strbuf_release(&iter->base.path); free(iter); - return ITER_DONE; } struct dir_iterator *dir_iterator_begin(const char *path, unsigned int flags) @@ -301,7 +299,7 @@ struct dir_iterator *dir_iterator_begin(const char *path, unsigned int flags) return dir_iterator; error_out: - dir_iterator_abort(dir_iterator); + dir_iterator_free(dir_iterator); errno = saved_errno; return NULL; } diff --git a/dir-iterator.h b/dir-iterator.h index 6d438809b6..ccd6a19734 100644 --- a/dir-iterator.h +++ b/dir-iterator.h @@ -28,7 +28,7 @@ * * while ((ok = dir_iterator_advance(iter)) == ITER_OK) { * if (want_to_stop_iteration()) { - * ok = dir_iterator_abort(iter); + * ok = ITER_DONE; * break; * } * @@ -39,6 +39,7 @@ * * if (ok != ITER_DONE) * handle_error(); + * dir_iterator_free(iter); * * Callers are allowed to modify iter->path while they are working, * but they must restore it to its original contents before calling @@ -107,11 +108,7 @@ struct dir_iterator *dir_iterator_begin(const char *path, unsigned int flags); */ int dir_iterator_advance(struct dir_iterator *iterator); -/* - * End the iteration before it has been exhausted. Free the - * dir_iterator and any associated resources and return ITER_DONE. On - * error, free the dir_iterator and return ITER_ERROR. - */ -int dir_iterator_abort(struct dir_iterator *iterator); +/* Free the dir_iterator and any associated resources. */ +void dir_iterator_free(struct dir_iterator *iterator); #endif diff --git a/iterator.h b/iterator.h index 0f6900e43a..6b77dcc262 100644 --- a/iterator.h +++ b/iterator.h @@ -12,7 +12,7 @@ #define ITER_OK 0 /* - * The iterator is exhausted and has been freed. + * The iterator is exhausted. */ #define ITER_DONE -1 diff --git a/refs.c b/refs.c index 957446da9e..eeb8fb1021 100644 --- a/refs.c +++ b/refs.c @@ -2485,6 +2485,7 @@ int refs_verify_refnames_available(struct ref_store *refs, struct strbuf dirname = STRBUF_INIT; struct strbuf referent = STRBUF_INIT; struct string_list_item *item; + struct ref_iterator *iter = NULL; struct strset dirnames; int ret = -1; @@ -2561,7 +2562,6 @@ int refs_verify_refnames_available(struct ref_store *refs, strbuf_addch(&dirname, '/'); if (!initial_transaction) { - struct ref_iterator *iter; int ok; iter = refs_ref_iterator_begin(refs, dirname.buf, NULL, 0, @@ -2573,12 +2573,14 @@ int refs_verify_refnames_available(struct ref_store *refs, strbuf_addf(err, _("'%s' exists; cannot create '%s'"), iter->refname, refname); - ref_iterator_abort(iter); goto cleanup; } if (ok != ITER_DONE) BUG("error while iterating over references"); + + ref_iterator_free(iter); + iter = NULL; } extra_refname = find_descendant_ref(dirname.buf, extras, skip); @@ -2595,6 +2597,7 @@ cleanup: strbuf_release(&referent); strbuf_release(&dirname); strset_clear(&dirnames); + ref_iterator_free(iter); return ret; } diff --git a/refs/debug.c b/refs/debug.c index fbc4df08b4..a9786da4ba 100644 --- a/refs/debug.c +++ b/refs/debug.c @@ -179,19 +179,18 @@ static int debug_ref_iterator_peel(struct ref_iterator *ref_iterator, return res; } -static int debug_ref_iterator_abort(struct ref_iterator *ref_iterator) +static void debug_ref_iterator_release(struct ref_iterator *ref_iterator) { struct debug_ref_iterator *diter = (struct debug_ref_iterator *)ref_iterator; - int res = diter->iter->vtable->abort(diter->iter); - trace_printf_key(&trace_refs, "iterator_abort: %d\n", res); - return res; + diter->iter->vtable->release(diter->iter); + trace_printf_key(&trace_refs, "iterator_abort\n"); } static struct ref_iterator_vtable debug_ref_iterator_vtable = { .advance = debug_ref_iterator_advance, .peel = debug_ref_iterator_peel, - .abort = debug_ref_iterator_abort, + .release = debug_ref_iterator_release, }; static struct ref_iterator * diff --git a/refs/files-backend.c b/refs/files-backend.c index ab6f0af550..e97a267ad6 100644 --- a/refs/files-backend.c +++ b/refs/files-backend.c @@ -915,10 +915,6 @@ static int files_ref_iterator_advance(struct ref_iterator *ref_iterator) return ITER_OK; } - iter->iter0 = NULL; - if (ref_iterator_abort(ref_iterator) != ITER_DONE) - ok = ITER_ERROR; - return ok; } @@ -931,23 +927,17 @@ static int files_ref_iterator_peel(struct ref_iterator *ref_iterator, return ref_iterator_peel(iter->iter0, peeled); } -static int files_ref_iterator_abort(struct ref_iterator *ref_iterator) +static void files_ref_iterator_release(struct ref_iterator *ref_iterator) { struct files_ref_iterator *iter = (struct files_ref_iterator *)ref_iterator; - int ok = ITER_DONE; - - if (iter->iter0) - ok = ref_iterator_abort(iter->iter0); - - base_ref_iterator_free(ref_iterator); - return ok; + ref_iterator_free(iter->iter0); } static struct ref_iterator_vtable files_ref_iterator_vtable = { .advance = files_ref_iterator_advance, .peel = files_ref_iterator_peel, - .abort = files_ref_iterator_abort, + .release = files_ref_iterator_release, }; static struct ref_iterator *files_ref_iterator_begin( @@ -1378,7 +1368,7 @@ static int should_pack_refs(struct files_ref_store *refs, iter->flags, opts)) refcount++; if (refcount >= limit) { - ref_iterator_abort(iter); + ref_iterator_free(iter); return 1; } } @@ -1386,6 +1376,7 @@ static int should_pack_refs(struct files_ref_store *refs, if (ret != ITER_DONE) die("error while iterating over references"); + ref_iterator_free(iter); return 0; } @@ -1452,6 +1443,7 @@ static int files_pack_refs(struct ref_store *ref_store, packed_refs_unlock(refs->packed_ref_store); prune_refs(refs, &refs_to_prune); + ref_iterator_free(iter); strbuf_release(&err); return 0; } @@ -2299,9 +2291,6 @@ static int files_reflog_iterator_advance(struct ref_iterator *ref_iterator) return ITER_OK; } - iter->dir_iterator = NULL; - if (ref_iterator_abort(ref_iterator) == ITER_ERROR) - ok = ITER_ERROR; return ok; } @@ -2311,23 +2300,17 @@ static int files_reflog_iterator_peel(struct ref_iterator *ref_iterator UNUSED, BUG("ref_iterator_peel() called for reflog_iterator"); } -static int files_reflog_iterator_abort(struct ref_iterator *ref_iterator) +static void files_reflog_iterator_release(struct ref_iterator *ref_iterator) { struct files_reflog_iterator *iter = (struct files_reflog_iterator *)ref_iterator; - int ok = ITER_DONE; - - if (iter->dir_iterator) - ok = dir_iterator_abort(iter->dir_iterator); - - base_ref_iterator_free(ref_iterator); - return ok; + dir_iterator_free(iter->dir_iterator); } static struct ref_iterator_vtable files_reflog_iterator_vtable = { .advance = files_reflog_iterator_advance, .peel = files_reflog_iterator_peel, - .abort = files_reflog_iterator_abort, + .release = files_reflog_iterator_release, }; static struct ref_iterator *reflog_iterator_begin(struct ref_store *ref_store, @@ -3837,6 +3820,7 @@ static int files_fsck_refs_dir(struct ref_store *ref_store, ret = error(_("failed to iterate over '%s'"), sb.buf); out: + dir_iterator_free(iter); strbuf_release(&sb); strbuf_release(&refname); return ret; diff --git a/refs/iterator.c b/refs/iterator.c index d25e568bf0..d61474cba7 100644 --- a/refs/iterator.c +++ b/refs/iterator.c @@ -21,9 +21,14 @@ int ref_iterator_peel(struct ref_iterator *ref_iterator, return ref_iterator->vtable->peel(ref_iterator, peeled); } -int ref_iterator_abort(struct ref_iterator *ref_iterator) +void ref_iterator_free(struct ref_iterator *ref_iterator) { - return ref_iterator->vtable->abort(ref_iterator); + if (ref_iterator) { + ref_iterator->vtable->release(ref_iterator); + /* Help make use-after-free bugs fail quickly: */ + ref_iterator->vtable = NULL; + free(ref_iterator); + } } void base_ref_iterator_init(struct ref_iterator *iter, @@ -36,20 +41,13 @@ void base_ref_iterator_init(struct ref_iterator *iter, iter->flags = 0; } -void base_ref_iterator_free(struct ref_iterator *iter) -{ - /* Help make use-after-free bugs fail quickly: */ - iter->vtable = NULL; - free(iter); -} - struct empty_ref_iterator { struct ref_iterator base; }; -static int empty_ref_iterator_advance(struct ref_iterator *ref_iterator) +static int empty_ref_iterator_advance(struct ref_iterator *ref_iterator UNUSED) { - return ref_iterator_abort(ref_iterator); + return ITER_DONE; } static int empty_ref_iterator_peel(struct ref_iterator *ref_iterator UNUSED, @@ -58,16 +56,14 @@ static int empty_ref_iterator_peel(struct ref_iterator *ref_iterator UNUSED, BUG("peel called for empty iterator"); } -static int empty_ref_iterator_abort(struct ref_iterator *ref_iterator) +static void empty_ref_iterator_release(struct ref_iterator *ref_iterator UNUSED) { - base_ref_iterator_free(ref_iterator); - return ITER_DONE; } static struct ref_iterator_vtable empty_ref_iterator_vtable = { .advance = empty_ref_iterator_advance, .peel = empty_ref_iterator_peel, - .abort = empty_ref_iterator_abort, + .release = empty_ref_iterator_release, }; struct ref_iterator *empty_ref_iterator_begin(void) @@ -151,11 +147,13 @@ static int merge_ref_iterator_advance(struct ref_iterator *ref_iterator) if (!iter->current) { /* Initialize: advance both iterators to their first entries */ if ((ok = ref_iterator_advance(iter->iter0)) != ITER_OK) { + ref_iterator_free(iter->iter0); iter->iter0 = NULL; if (ok == ITER_ERROR) goto error; } if ((ok = ref_iterator_advance(iter->iter1)) != ITER_OK) { + ref_iterator_free(iter->iter1); iter->iter1 = NULL; if (ok == ITER_ERROR) goto error; @@ -166,6 +164,7 @@ static int merge_ref_iterator_advance(struct ref_iterator *ref_iterator) * entry: */ if ((ok = ref_iterator_advance(*iter->current)) != ITER_OK) { + ref_iterator_free(*iter->current); *iter->current = NULL; if (ok == ITER_ERROR) goto error; @@ -179,9 +178,8 @@ static int merge_ref_iterator_advance(struct ref_iterator *ref_iterator) iter->select(iter->iter0, iter->iter1, iter->cb_data); if (selection == ITER_SELECT_DONE) { - return ref_iterator_abort(ref_iterator); + return ITER_DONE; } else if (selection == ITER_SELECT_ERROR) { - ref_iterator_abort(ref_iterator); return ITER_ERROR; } @@ -195,6 +193,7 @@ static int merge_ref_iterator_advance(struct ref_iterator *ref_iterator) if (selection & ITER_SKIP_SECONDARY) { if ((ok = ref_iterator_advance(*secondary)) != ITER_OK) { + ref_iterator_free(*secondary); *secondary = NULL; if (ok == ITER_ERROR) goto error; @@ -211,7 +210,6 @@ static int merge_ref_iterator_advance(struct ref_iterator *ref_iterator) } error: - ref_iterator_abort(ref_iterator); return ITER_ERROR; } @@ -227,28 +225,18 @@ static int merge_ref_iterator_peel(struct ref_iterator *ref_iterator, return ref_iterator_peel(*iter->current, peeled); } -static int merge_ref_iterator_abort(struct ref_iterator *ref_iterator) +static void merge_ref_iterator_release(struct ref_iterator *ref_iterator) { struct merge_ref_iterator *iter = (struct merge_ref_iterator *)ref_iterator; - int ok = ITER_DONE; - - if (iter->iter0) { - if (ref_iterator_abort(iter->iter0) != ITER_DONE) - ok = ITER_ERROR; - } - if (iter->iter1) { - if (ref_iterator_abort(iter->iter1) != ITER_DONE) - ok = ITER_ERROR; - } - base_ref_iterator_free(ref_iterator); - return ok; + ref_iterator_free(iter->iter0); + ref_iterator_free(iter->iter1); } static struct ref_iterator_vtable merge_ref_iterator_vtable = { .advance = merge_ref_iterator_advance, .peel = merge_ref_iterator_peel, - .abort = merge_ref_iterator_abort, + .release = merge_ref_iterator_release, }; struct ref_iterator *merge_ref_iterator_begin( @@ -310,10 +298,10 @@ struct ref_iterator *overlay_ref_iterator_begin( * them. */ if (is_empty_ref_iterator(front)) { - ref_iterator_abort(front); + ref_iterator_free(front); return back; } else if (is_empty_ref_iterator(back)) { - ref_iterator_abort(back); + ref_iterator_free(back); return front; } @@ -350,19 +338,15 @@ static int prefix_ref_iterator_advance(struct ref_iterator *ref_iterator) while ((ok = ref_iterator_advance(iter->iter0)) == ITER_OK) { int cmp = compare_prefix(iter->iter0->refname, iter->prefix); - if (cmp < 0) continue; - - if (cmp > 0) { - /* - * As the source iterator is ordered, we - * can stop the iteration as soon as we see a - * refname that comes after the prefix: - */ - ok = ref_iterator_abort(iter->iter0); - break; - } + /* + * As the source iterator is ordered, we + * can stop the iteration as soon as we see a + * refname that comes after the prefix: + */ + if (cmp > 0) + return ITER_DONE; if (iter->trim) { /* @@ -386,9 +370,6 @@ static int prefix_ref_iterator_advance(struct ref_iterator *ref_iterator) return ITER_OK; } - iter->iter0 = NULL; - if (ref_iterator_abort(ref_iterator) != ITER_DONE) - return ITER_ERROR; return ok; } @@ -401,23 +382,18 @@ static int prefix_ref_iterator_peel(struct ref_iterator *ref_iterator, return ref_iterator_peel(iter->iter0, peeled); } -static int prefix_ref_iterator_abort(struct ref_iterator *ref_iterator) +static void prefix_ref_iterator_release(struct ref_iterator *ref_iterator) { struct prefix_ref_iterator *iter = (struct prefix_ref_iterator *)ref_iterator; - int ok = ITER_DONE; - - if (iter->iter0) - ok = ref_iterator_abort(iter->iter0); + ref_iterator_free(iter->iter0); free(iter->prefix); - base_ref_iterator_free(ref_iterator); - return ok; } static struct ref_iterator_vtable prefix_ref_iterator_vtable = { .advance = prefix_ref_iterator_advance, .peel = prefix_ref_iterator_peel, - .abort = prefix_ref_iterator_abort, + .release = prefix_ref_iterator_release, }; struct ref_iterator *prefix_ref_iterator_begin(struct ref_iterator *iter0, @@ -453,20 +429,14 @@ int do_for_each_ref_iterator(struct ref_iterator *iter, current_ref_iter = iter; while ((ok = ref_iterator_advance(iter)) == ITER_OK) { retval = fn(iter->refname, iter->referent, iter->oid, iter->flags, cb_data); - if (retval) { - /* - * If ref_iterator_abort() returns ITER_ERROR, - * we ignore that error in deference to the - * callback function's return value. - */ - ref_iterator_abort(iter); + if (retval) goto out; - } } out: current_ref_iter = old_ref_iter; if (ok == ITER_ERROR) - return -1; + retval = -1; + ref_iterator_free(iter); return retval; } diff --git a/refs/packed-backend.c b/refs/packed-backend.c index a7b6f74b6e..38a1956d1a 100644 --- a/refs/packed-backend.c +++ b/refs/packed-backend.c @@ -954,9 +954,6 @@ static int packed_ref_iterator_advance(struct ref_iterator *ref_iterator) return ITER_OK; } - if (ref_iterator_abort(ref_iterator) != ITER_DONE) - ok = ITER_ERROR; - return ok; } @@ -976,23 +973,19 @@ static int packed_ref_iterator_peel(struct ref_iterator *ref_iterator, } } -static int packed_ref_iterator_abort(struct ref_iterator *ref_iterator) +static void packed_ref_iterator_release(struct ref_iterator *ref_iterator) { struct packed_ref_iterator *iter = (struct packed_ref_iterator *)ref_iterator; - int ok = ITER_DONE; - strbuf_release(&iter->refname_buf); free(iter->jump); release_snapshot(iter->snapshot); - base_ref_iterator_free(ref_iterator); - return ok; } static struct ref_iterator_vtable packed_ref_iterator_vtable = { .advance = packed_ref_iterator_advance, .peel = packed_ref_iterator_peel, - .abort = packed_ref_iterator_abort + .release = packed_ref_iterator_release, }; static int jump_list_entry_cmp(const void *va, const void *vb) @@ -1362,8 +1355,10 @@ static int write_with_updates(struct packed_ref_store *refs, */ iter = packed_ref_iterator_begin(&refs->base, "", NULL, DO_FOR_EACH_INCLUDE_BROKEN); - if ((ok = ref_iterator_advance(iter)) != ITER_OK) + if ((ok = ref_iterator_advance(iter)) != ITER_OK) { + ref_iterator_free(iter); iter = NULL; + } i = 0; @@ -1411,8 +1406,10 @@ static int write_with_updates(struct packed_ref_store *refs, * the iterator over the unneeded * value. */ - if ((ok = ref_iterator_advance(iter)) != ITER_OK) + if ((ok = ref_iterator_advance(iter)) != ITER_OK) { + ref_iterator_free(iter); iter = NULL; + } cmp = +1; } else { /* @@ -1449,8 +1446,10 @@ static int write_with_updates(struct packed_ref_store *refs, peel_error ? NULL : &peeled)) goto write_error; - if ((ok = ref_iterator_advance(iter)) != ITER_OK) + if ((ok = ref_iterator_advance(iter)) != ITER_OK) { + ref_iterator_free(iter); iter = NULL; + } } else if (is_null_oid(&update->new_oid)) { /* * The update wants to delete the reference, @@ -1499,9 +1498,7 @@ write_error: get_tempfile_path(refs->tempfile), strerror(errno)); error: - if (iter) - ref_iterator_abort(iter); - + ref_iterator_free(iter); delete_tempfile(&refs->tempfile); return -1; } diff --git a/refs/ref-cache.c b/refs/ref-cache.c index 02f09e4df8..6457e02c1e 100644 --- a/refs/ref-cache.c +++ b/refs/ref-cache.c @@ -409,7 +409,7 @@ static int cache_ref_iterator_advance(struct ref_iterator *ref_iterator) if (++level->index == level->dir->nr) { /* This level is exhausted; pop up a level */ if (--iter->levels_nr == 0) - return ref_iterator_abort(ref_iterator); + return ITER_DONE; continue; } @@ -452,21 +452,18 @@ static int cache_ref_iterator_peel(struct ref_iterator *ref_iterator, return peel_object(iter->repo, ref_iterator->oid, peeled) ? -1 : 0; } -static int cache_ref_iterator_abort(struct ref_iterator *ref_iterator) +static void cache_ref_iterator_release(struct ref_iterator *ref_iterator) { struct cache_ref_iterator *iter = (struct cache_ref_iterator *)ref_iterator; - free((char *)iter->prefix); free(iter->levels); - base_ref_iterator_free(ref_iterator); - return ITER_DONE; } static struct ref_iterator_vtable cache_ref_iterator_vtable = { .advance = cache_ref_iterator_advance, .peel = cache_ref_iterator_peel, - .abort = cache_ref_iterator_abort + .release = cache_ref_iterator_release, }; struct ref_iterator *cache_ref_iterator_begin(struct ref_cache *cache, diff --git a/refs/refs-internal.h b/refs/refs-internal.h index 8894b43d1d..7d3bab654b 100644 --- a/refs/refs-internal.h +++ b/refs/refs-internal.h @@ -273,11 +273,11 @@ enum do_for_each_ref_flags { * the next reference and returns ITER_OK. The data pointed at by * refname and oid belong to the iterator; if you want to retain them * after calling ref_iterator_advance() again or calling - * ref_iterator_abort(), you must make a copy. When the iteration has + * ref_iterator_free(), you must make a copy. When the iteration has * been exhausted, ref_iterator_advance() releases any resources * associated with the iteration, frees the ref_iterator object, and * returns ITER_DONE. If you want to abort the iteration early, call - * ref_iterator_abort(), which also frees the ref_iterator object and + * ref_iterator_free(), which also frees the ref_iterator object and * any associated resources. If there was an internal error advancing * to the next entry, ref_iterator_advance() aborts the iteration, * frees the ref_iterator, and returns ITER_ERROR. @@ -293,7 +293,7 @@ enum do_for_each_ref_flags { * * while ((ok = ref_iterator_advance(iter)) == ITER_OK) { * if (want_to_stop_iteration()) { - * ok = ref_iterator_abort(iter); + * ok = ITER_DONE; * break; * } * @@ -307,6 +307,7 @@ enum do_for_each_ref_flags { * * if (ok != ITER_DONE) * handle_error(); + * ref_iterator_free(iter); */ struct ref_iterator { struct ref_iterator_vtable *vtable; @@ -333,12 +334,8 @@ int ref_iterator_advance(struct ref_iterator *ref_iterator); int ref_iterator_peel(struct ref_iterator *ref_iterator, struct object_id *peeled); -/* - * End the iteration before it has been exhausted, freeing the - * reference iterator and any associated resources and returning - * ITER_DONE. If the abort itself failed, return ITER_ERROR. - */ -int ref_iterator_abort(struct ref_iterator *ref_iterator); +/* Free the reference iterator and any associated resources. */ +void ref_iterator_free(struct ref_iterator *ref_iterator); /* * An iterator over nothing (its first ref_iterator_advance() call @@ -438,13 +435,6 @@ struct ref_iterator *prefix_ref_iterator_begin(struct ref_iterator *iter0, void base_ref_iterator_init(struct ref_iterator *iter, struct ref_iterator_vtable *vtable); -/* - * Base class destructor for ref_iterators. Destroy the ref_iterator - * part of iter and shallow-free the object. This is meant to be - * called only by the destructors of derived classes. - */ -void base_ref_iterator_free(struct ref_iterator *iter); - /* Virtual function declarations for ref_iterators: */ /* @@ -463,15 +453,14 @@ typedef int ref_iterator_peel_fn(struct ref_iterator *ref_iterator, /* * Implementations of this function should free any resources specific - * to the derived class, then call base_ref_iterator_free() to clean - * up and free the ref_iterator object. + * to the derived class. */ -typedef int ref_iterator_abort_fn(struct ref_iterator *ref_iterator); +typedef void ref_iterator_release_fn(struct ref_iterator *ref_iterator); struct ref_iterator_vtable { ref_iterator_advance_fn *advance; ref_iterator_peel_fn *peel; - ref_iterator_abort_fn *abort; + ref_iterator_release_fn *release; }; /* diff --git a/refs/reftable-backend.c b/refs/reftable-backend.c index 546861d64c..2d5f4afe6b 100644 --- a/refs/reftable-backend.c +++ b/refs/reftable-backend.c @@ -711,17 +711,10 @@ static int reftable_ref_iterator_advance(struct ref_iterator *ref_iterator) break; } - if (iter->err > 0) { - if (ref_iterator_abort(ref_iterator) != ITER_DONE) - return ITER_ERROR; + if (iter->err > 0) return ITER_DONE; - } - - if (iter->err < 0) { - ref_iterator_abort(ref_iterator); + if (iter->err < 0) return ITER_ERROR; - } - return ITER_OK; } @@ -740,7 +733,7 @@ static int reftable_ref_iterator_peel(struct ref_iterator *ref_iterator, return -1; } -static int reftable_ref_iterator_abort(struct ref_iterator *ref_iterator) +static void reftable_ref_iterator_release(struct ref_iterator *ref_iterator) { struct reftable_ref_iterator *iter = (struct reftable_ref_iterator *)ref_iterator; @@ -751,14 +744,12 @@ static int reftable_ref_iterator_abort(struct ref_iterator *ref_iterator) free(iter->exclude_patterns[i]); free(iter->exclude_patterns); } - free(iter); - return ITER_DONE; } static struct ref_iterator_vtable reftable_ref_iterator_vtable = { .advance = reftable_ref_iterator_advance, .peel = reftable_ref_iterator_peel, - .abort = reftable_ref_iterator_abort + .release = reftable_ref_iterator_release, }; static int qsort_strcmp(const void *va, const void *vb) @@ -2020,17 +2011,10 @@ static int reftable_reflog_iterator_advance(struct ref_iterator *ref_iterator) break; } - if (iter->err > 0) { - if (ref_iterator_abort(ref_iterator) != ITER_DONE) - return ITER_ERROR; + if (iter->err > 0) return ITER_DONE; - } - - if (iter->err < 0) { - ref_iterator_abort(ref_iterator); + if (iter->err < 0) return ITER_ERROR; - } - return ITER_OK; } @@ -2041,21 +2025,19 @@ static int reftable_reflog_iterator_peel(struct ref_iterator *ref_iterator UNUSE return -1; } -static int reftable_reflog_iterator_abort(struct ref_iterator *ref_iterator) +static void reftable_reflog_iterator_release(struct ref_iterator *ref_iterator) { struct reftable_reflog_iterator *iter = (struct reftable_reflog_iterator *)ref_iterator; reftable_log_record_release(&iter->log); reftable_iterator_destroy(&iter->iter); strbuf_release(&iter->last_name); - free(iter); - return ITER_DONE; } static struct ref_iterator_vtable reftable_reflog_iterator_vtable = { .advance = reftable_reflog_iterator_advance, .peel = reftable_reflog_iterator_peel, - .abort = reftable_reflog_iterator_abort + .release = reftable_reflog_iterator_release, }; static struct reftable_reflog_iterator *reflog_iterator_for_stack(struct reftable_ref_store *refs, diff --git a/t/helper/test-dir-iterator.c b/t/helper/test-dir-iterator.c index 6b297bd753..8d46e8ba40 100644 --- a/t/helper/test-dir-iterator.c +++ b/t/helper/test-dir-iterator.c @@ -53,6 +53,7 @@ int cmd__dir_iterator(int argc, const char **argv) printf("(%s) [%s] %s\n", diter->relative_path, diter->basename, diter->path.buf); } + dir_iterator_free(diter); if (iter_status != ITER_DONE) { printf("dir_iterator_advance failure\n"); -- cgit v1.3-5-g9baa From 82c39c6055b5340f0e50acbe01a97e51d3907fec Mon Sep 17 00:00:00 2001 From: Patrick Steinhardt Date: Wed, 12 Mar 2025 16:56:16 +0100 Subject: refs/iterator: provide infrastructure to re-seek iterators Reftable iterators need to be scrapped after they have either been exhausted or aren't useful to the caller anymore, and it is explicitly not possible to reuse them for iterations. But enabling for reuse of iterators may allow us to tune them by reusing internal state of an iterator. The reftable iterators for example can already be reused internally, but we're not able to expose this to any users outside of the reftable backend. Introduce a new `.seek` function in the ref iterator vtable that allows callers to seek an iterator multiple times. It is expected to be functionally the same as calling `refs_ref_iterator_begin()` with a different (or the same) prefix. Note that it is not possible to adjust parameters other than the seeked prefix for now, so exclude patterns, trimmed prefixes and flags will remain unchanged. We do not have a usecase for changing these parameters right now, but if we ever find one we can adapt accordingly. Implement the callback for trivial cases. The other iterators will be implemented in subsequent commits. Signed-off-by: Patrick Steinhardt Signed-off-by: Junio C Hamano --- refs/debug.c | 11 +++++++++++ refs/iterator.c | 24 ++++++++++++++++++++++++ refs/refs-internal.h | 24 ++++++++++++++++++++++++ 3 files changed, 59 insertions(+) (limited to 'refs') diff --git a/refs/debug.c b/refs/debug.c index a9786da4ba..5390fa9c18 100644 --- a/refs/debug.c +++ b/refs/debug.c @@ -169,6 +169,16 @@ static int debug_ref_iterator_advance(struct ref_iterator *ref_iterator) return res; } +static int debug_ref_iterator_seek(struct ref_iterator *ref_iterator, + const char *prefix) +{ + 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); + return res; +} + static int debug_ref_iterator_peel(struct ref_iterator *ref_iterator, struct object_id *peeled) { @@ -189,6 +199,7 @@ static void debug_ref_iterator_release(struct ref_iterator *ref_iterator) static struct ref_iterator_vtable debug_ref_iterator_vtable = { .advance = debug_ref_iterator_advance, + .seek = debug_ref_iterator_seek, .peel = debug_ref_iterator_peel, .release = debug_ref_iterator_release, }; diff --git a/refs/iterator.c b/refs/iterator.c index d61474cba7..ea4db59481 100644 --- a/refs/iterator.c +++ b/refs/iterator.c @@ -15,6 +15,12 @@ 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) +{ + return ref_iterator->vtable->seek(ref_iterator, prefix); +} + int ref_iterator_peel(struct ref_iterator *ref_iterator, struct object_id *peeled) { @@ -50,6 +56,12 @@ static int empty_ref_iterator_advance(struct ref_iterator *ref_iterator UNUSED) return ITER_DONE; } +static int empty_ref_iterator_seek(struct ref_iterator *ref_iterator UNUSED, + const char *prefix UNUSED) +{ + return 0; +} + static int empty_ref_iterator_peel(struct ref_iterator *ref_iterator UNUSED, struct object_id *peeled UNUSED) { @@ -62,6 +74,7 @@ static void empty_ref_iterator_release(struct ref_iterator *ref_iterator UNUSED) static struct ref_iterator_vtable empty_ref_iterator_vtable = { .advance = empty_ref_iterator_advance, + .seek = empty_ref_iterator_seek, .peel = empty_ref_iterator_peel, .release = empty_ref_iterator_release, }; @@ -373,6 +386,16 @@ static int prefix_ref_iterator_advance(struct ref_iterator *ref_iterator) return ok; } +static int prefix_ref_iterator_seek(struct ref_iterator *ref_iterator, + const char *prefix) +{ + 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); +} + static int prefix_ref_iterator_peel(struct ref_iterator *ref_iterator, struct object_id *peeled) { @@ -392,6 +415,7 @@ static void prefix_ref_iterator_release(struct ref_iterator *ref_iterator) static struct ref_iterator_vtable prefix_ref_iterator_vtable = { .advance = prefix_ref_iterator_advance, + .seek = prefix_ref_iterator_seek, .peel = prefix_ref_iterator_peel, .release = prefix_ref_iterator_release, }; diff --git a/refs/refs-internal.h b/refs/refs-internal.h index 7d3bab654b..e5862757a7 100644 --- a/refs/refs-internal.h +++ b/refs/refs-internal.h @@ -327,6 +327,22 @@ struct ref_iterator { */ int ref_iterator_advance(struct ref_iterator *ref_iterator); +/* + * 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 + * 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. + * + * Returns 0 on success, a negative error code otherwise. + */ +int ref_iterator_seek(struct ref_iterator *ref_iterator, + const char *prefix); + /* * If possible, peel the reference currently being viewed by the * iterator. Return 0 on success. @@ -445,6 +461,13 @@ 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. + */ +typedef int ref_iterator_seek_fn(struct ref_iterator *ref_iterator, + const char *prefix); + /* * Peels the current ref, returning 0 for success or -1 for failure. */ @@ -459,6 +482,7 @@ typedef void ref_iterator_release_fn(struct ref_iterator *ref_iterator); struct ref_iterator_vtable { ref_iterator_advance_fn *advance; + ref_iterator_seek_fn *seek; ref_iterator_peel_fn *peel; ref_iterator_release_fn *release; }; -- cgit v1.3-5-g9baa From 9821d90f13c6442022bbbcb2d96f1b29aad76503 Mon Sep 17 00:00:00 2001 From: Patrick Steinhardt Date: Wed, 12 Mar 2025 16:56:17 +0100 Subject: refs/iterator: implement seeking for merged iterators Implement seeking on merged iterators. The implementation is rather straight forward, with the only exception that we must not deallocate the underlying iterators once they have been exhausted. Signed-off-by: Patrick Steinhardt Signed-off-by: Junio C Hamano --- refs/iterator.c | 38 +++++++++++++++++++++++++++++--------- 1 file changed, 29 insertions(+), 9 deletions(-) (limited to 'refs') diff --git a/refs/iterator.c b/refs/iterator.c index ea4db59481..766d96e795 100644 --- a/refs/iterator.c +++ b/refs/iterator.c @@ -96,7 +96,8 @@ int is_empty_ref_iterator(struct ref_iterator *ref_iterator) struct merge_ref_iterator { struct ref_iterator base; - struct ref_iterator *iter0, *iter1; + struct ref_iterator *iter0, *iter0_owned; + struct ref_iterator *iter1, *iter1_owned; ref_iterator_select_fn *select; void *cb_data; @@ -160,13 +161,11 @@ static int merge_ref_iterator_advance(struct ref_iterator *ref_iterator) if (!iter->current) { /* Initialize: advance both iterators to their first entries */ if ((ok = ref_iterator_advance(iter->iter0)) != ITER_OK) { - ref_iterator_free(iter->iter0); iter->iter0 = NULL; if (ok == ITER_ERROR) goto error; } if ((ok = ref_iterator_advance(iter->iter1)) != ITER_OK) { - ref_iterator_free(iter->iter1); iter->iter1 = NULL; if (ok == ITER_ERROR) goto error; @@ -177,7 +176,6 @@ static int merge_ref_iterator_advance(struct ref_iterator *ref_iterator) * entry: */ if ((ok = ref_iterator_advance(*iter->current)) != ITER_OK) { - ref_iterator_free(*iter->current); *iter->current = NULL; if (ok == ITER_ERROR) goto error; @@ -206,7 +204,6 @@ static int merge_ref_iterator_advance(struct ref_iterator *ref_iterator) if (selection & ITER_SKIP_SECONDARY) { if ((ok = ref_iterator_advance(*secondary)) != ITER_OK) { - ref_iterator_free(*secondary); *secondary = NULL; if (ok == ITER_ERROR) goto error; @@ -226,6 +223,28 @@ error: return ITER_ERROR; } +static int merge_ref_iterator_seek(struct ref_iterator *ref_iterator, + const char *prefix) +{ + struct merge_ref_iterator *iter = + (struct merge_ref_iterator *)ref_iterator; + int ret; + + iter->current = NULL; + iter->iter0 = iter->iter0_owned; + iter->iter1 = iter->iter1_owned; + + ret = ref_iterator_seek(iter->iter0, prefix); + if (ret < 0) + return ret; + + ret = ref_iterator_seek(iter->iter1, prefix); + if (ret < 0) + return ret; + + return 0; +} + static int merge_ref_iterator_peel(struct ref_iterator *ref_iterator, struct object_id *peeled) { @@ -242,12 +261,13 @@ static void merge_ref_iterator_release(struct ref_iterator *ref_iterator) { struct merge_ref_iterator *iter = (struct merge_ref_iterator *)ref_iterator; - ref_iterator_free(iter->iter0); - ref_iterator_free(iter->iter1); + ref_iterator_free(iter->iter0_owned); + ref_iterator_free(iter->iter1_owned); } static struct ref_iterator_vtable merge_ref_iterator_vtable = { .advance = merge_ref_iterator_advance, + .seek = merge_ref_iterator_seek, .peel = merge_ref_iterator_peel, .release = merge_ref_iterator_release, }; @@ -268,8 +288,8 @@ struct ref_iterator *merge_ref_iterator_begin( */ base_ref_iterator_init(ref_iterator, &merge_ref_iterator_vtable); - iter->iter0 = iter0; - iter->iter1 = iter1; + iter->iter0 = iter->iter0_owned = iter0; + iter->iter1 = iter->iter1_owned = iter1; iter->select = select; iter->cb_data = cb_data; iter->current = NULL; -- cgit v1.3-5-g9baa From 53de20c931faabdb6fa9a30d949266b2a7471497 Mon Sep 17 00:00:00 2001 From: Patrick Steinhardt Date: Wed, 12 Mar 2025 16:56:18 +0100 Subject: refs/iterator: implement seeking for reftable iterators Implement seeking of reftable iterators. As the low-level reftable iterators already support seeking this change is straight-forward. Two notes though: - We do not support seeking on reflog iterators. It is unclear what seeking would even look like in this context, as you typically would want to seek to a specific entry in the reflog for a specific ref. There is currently no use case for this, but if one arises in the future, we can still implement seeking at that later point. - We start to check whether `reftable_stack_init_ref_iterator()` is successful. Signed-off-by: Patrick Steinhardt Signed-off-by: Junio C Hamano --- refs/reftable-backend.c | 35 ++++++++++++++++++++++++++++++----- 1 file changed, 30 insertions(+), 5 deletions(-) (limited to 'refs') diff --git a/refs/reftable-backend.c b/refs/reftable-backend.c index 2d5f4afe6b..c8f86da731 100644 --- a/refs/reftable-backend.c +++ b/refs/reftable-backend.c @@ -547,7 +547,7 @@ struct reftable_ref_iterator { struct reftable_ref_record ref; struct object_id oid; - const char *prefix; + char *prefix; size_t prefix_len; char **exclude_patterns; size_t exclude_patterns_index; @@ -718,6 +718,20 @@ static int reftable_ref_iterator_advance(struct ref_iterator *ref_iterator) return ITER_OK; } +static int reftable_ref_iterator_seek(struct ref_iterator *ref_iterator, + const char *prefix) +{ + 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); + + return iter->err; +} + static int reftable_ref_iterator_peel(struct ref_iterator *ref_iterator, struct object_id *peeled) { @@ -744,10 +758,12 @@ static void reftable_ref_iterator_release(struct ref_iterator *ref_iterator) free(iter->exclude_patterns[i]); free(iter->exclude_patterns); } + free(iter->prefix); } static struct ref_iterator_vtable reftable_ref_iterator_vtable = { .advance = reftable_ref_iterator_advance, + .seek = reftable_ref_iterator_seek, .peel = reftable_ref_iterator_peel, .release = reftable_ref_iterator_release, }; @@ -806,8 +822,6 @@ static struct reftable_ref_iterator *ref_iterator_for_stack(struct reftable_ref_ iter = xcalloc(1, sizeof(*iter)); base_ref_iterator_init(&iter->base, &reftable_ref_iterator_vtable); - iter->prefix = prefix; - iter->prefix_len = prefix ? strlen(prefix) : 0; iter->base.oid = &iter->oid; iter->flags = flags; iter->refs = refs; @@ -821,8 +835,11 @@ static struct reftable_ref_iterator *ref_iterator_for_stack(struct reftable_ref_ if (ret) goto done; - reftable_stack_init_ref_iterator(stack, &iter->iter); - ret = reftable_iterator_seek_ref(&iter->iter, prefix); + ret = reftable_stack_init_ref_iterator(stack, &iter->iter); + if (ret) + goto done; + + ret = reftable_ref_iterator_seek(&iter->base, prefix); if (ret) goto done; @@ -2018,6 +2035,13 @@ static int reftable_reflog_iterator_advance(struct ref_iterator *ref_iterator) return ITER_OK; } +static int reftable_reflog_iterator_seek(struct ref_iterator *ref_iterator UNUSED, + const char *prefix UNUSED) +{ + BUG("reftable reflog iterator cannot be seeked"); + return -1; +} + static int reftable_reflog_iterator_peel(struct ref_iterator *ref_iterator UNUSED, struct object_id *peeled UNUSED) { @@ -2036,6 +2060,7 @@ static void reftable_reflog_iterator_release(struct ref_iterator *ref_iterator) static struct ref_iterator_vtable reftable_reflog_iterator_vtable = { .advance = reftable_reflog_iterator_advance, + .seek = reftable_reflog_iterator_seek, .peel = reftable_reflog_iterator_peel, .release = reftable_reflog_iterator_release, }; -- cgit v1.3-5-g9baa From 84e656919cb7237f1b11a948974d0591d9d3434f Mon Sep 17 00:00:00 2001 From: Patrick Steinhardt Date: Wed, 12 Mar 2025 16:56:19 +0100 Subject: refs/iterator: implement seeking for ref-cache iterators Implement seeking of ref-cache iterators. This is done by splitting most of the logic to seek iterators out of `cache_ref_iterator_begin()` and putting it into `cache_ref_iterator_seek()` so that we can reuse the logic. Note that we cannot use the optimization anymore where we return an empty ref iterator when there aren't any references, as otherwise it wouldn't be possible to reseek the iterator to a different prefix that may exist. This shouldn't be much of a performance concern though as we now start to bail out early in case `advance()` sees that there are no more directories to be searched. Signed-off-by: Patrick Steinhardt Signed-off-by: Junio C Hamano --- refs/ref-cache.c | 79 ++++++++++++++++++++++++++++++++++++-------------------- 1 file changed, 51 insertions(+), 28 deletions(-) (limited to 'refs') diff --git a/refs/ref-cache.c b/refs/ref-cache.c index 6457e02c1e..c1f1bab1d5 100644 --- a/refs/ref-cache.c +++ b/refs/ref-cache.c @@ -362,9 +362,7 @@ struct cache_ref_iterator { struct ref_iterator base; /* - * The number of levels currently on the stack. This is always - * at least 1, because when it becomes zero the iteration is - * ended and this struct is freed. + * The number of levels currently on the stack. */ size_t levels_nr; @@ -376,7 +374,7 @@ struct cache_ref_iterator { * The prefix is matched textually, without regard for path * component boundaries. */ - const char *prefix; + char *prefix; /* * A stack of levels. levels[0] is the uppermost level that is @@ -389,6 +387,9 @@ struct cache_ref_iterator { struct cache_ref_iterator_level *levels; struct repository *repo; + struct ref_cache *cache; + + int prime_dir; }; static int cache_ref_iterator_advance(struct ref_iterator *ref_iterator) @@ -396,6 +397,9 @@ static int cache_ref_iterator_advance(struct ref_iterator *ref_iterator) struct cache_ref_iterator *iter = (struct cache_ref_iterator *)ref_iterator; + if (!iter->levels_nr) + return ITER_DONE; + while (1) { struct cache_ref_iterator_level *level = &iter->levels[iter->levels_nr - 1]; @@ -444,6 +448,41 @@ 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) +{ + struct cache_ref_iterator *iter = + (struct cache_ref_iterator *)ref_iterator; + struct cache_ref_iterator_level *level; + struct ref_dir *dir; + + dir = get_ref_dir(iter->cache->root); + if (prefix && *prefix) + dir = find_containing_dir(dir, prefix); + if (!dir) { + iter->levels_nr = 0; + return 0; + } + + if (iter->prime_dir) + prime_ref_dir(dir, prefix); + iter->levels_nr = 1; + level = &iter->levels[0]; + level->index = -1; + level->dir = dir; + + if (prefix && *prefix) { + free(iter->prefix); + iter->prefix = xstrdup(prefix); + level->prefix_state = PREFIX_WITHIN_DIR; + } else { + FREE_AND_NULL(iter->prefix); + level->prefix_state = PREFIX_CONTAINS_DIR; + } + + return 0; +} + static int cache_ref_iterator_peel(struct ref_iterator *ref_iterator, struct object_id *peeled) { @@ -456,12 +495,13 @@ static void cache_ref_iterator_release(struct ref_iterator *ref_iterator) { struct cache_ref_iterator *iter = (struct cache_ref_iterator *)ref_iterator; - free((char *)iter->prefix); + free(iter->prefix); free(iter->levels); } static struct ref_iterator_vtable cache_ref_iterator_vtable = { .advance = cache_ref_iterator_advance, + .seek = cache_ref_iterator_seek, .peel = cache_ref_iterator_peel, .release = cache_ref_iterator_release, }; @@ -471,39 +511,22 @@ struct ref_iterator *cache_ref_iterator_begin(struct ref_cache *cache, struct repository *repo, int prime_dir) { - struct ref_dir *dir; struct cache_ref_iterator *iter; struct ref_iterator *ref_iterator; - struct cache_ref_iterator_level *level; - - dir = get_ref_dir(cache->root); - if (prefix && *prefix) - dir = find_containing_dir(dir, prefix); - if (!dir) - /* There's nothing to iterate over. */ - return empty_ref_iterator_begin(); - - if (prime_dir) - prime_ref_dir(dir, prefix); CALLOC_ARRAY(iter, 1); ref_iterator = &iter->base; base_ref_iterator_init(ref_iterator, &cache_ref_iterator_vtable); ALLOC_GROW(iter->levels, 10, iter->levels_alloc); - iter->levels_nr = 1; - level = &iter->levels[0]; - level->index = -1; - level->dir = dir; + iter->repo = repo; + iter->cache = cache; + iter->prime_dir = prime_dir; - if (prefix && *prefix) { - iter->prefix = xstrdup(prefix); - level->prefix_state = PREFIX_WITHIN_DIR; - } else { - level->prefix_state = PREFIX_CONTAINS_DIR; + if (cache_ref_iterator_seek(&iter->base, prefix) < 0) { + ref_iterator_free(&iter->base); + return NULL; } - iter->repo = repo; - return ref_iterator; } -- cgit v1.3-5-g9baa From 22600c045298f4f3664f94f6cbbf337903c72e82 Mon Sep 17 00:00:00 2001 From: Patrick Steinhardt Date: Wed, 12 Mar 2025 16:56:20 +0100 Subject: refs/iterator: implement seeking for packed-ref iterators Implement seeking of `packed-ref` iterators. The implementation is again straight forward, except that we cannot continue to use the prefix iterator as we would otherwise not be able to reseek the iterator anymore in case one first asks for an empty and then for a non-empty prefix. Instead, we open-code the logic to in `advance()`. Signed-off-by: Patrick Steinhardt Signed-off-by: Junio C Hamano --- refs/packed-backend.c | 65 ++++++++++++++++++++++++++++++++++----------------- 1 file changed, 43 insertions(+), 22 deletions(-) (limited to 'refs') diff --git a/refs/packed-backend.c b/refs/packed-backend.c index 38a1956d1a..f4c82ba2c7 100644 --- a/refs/packed-backend.c +++ b/refs/packed-backend.c @@ -819,6 +819,8 @@ struct packed_ref_iterator { struct snapshot *snapshot; + char *prefix; + /* The current position in the snapshot's buffer: */ const char *pos; @@ -841,11 +843,9 @@ struct packed_ref_iterator { }; /* - * Move the iterator to the next record in the snapshot, without - * respect for whether the record is actually required by the current - * iteration. Adjust the fields in `iter` and return `ITER_OK` or - * `ITER_DONE`. This function does not free the iterator in the case - * of `ITER_DONE`. + * Move the iterator to the next record in the snapshot. Adjust the fields in + * `iter` and return `ITER_OK` or `ITER_DONE`. This function does not free the + * iterator in the case of `ITER_DONE`. */ static int next_record(struct packed_ref_iterator *iter) { @@ -942,6 +942,9 @@ static int packed_ref_iterator_advance(struct ref_iterator *ref_iterator) int ok; while ((ok = next_record(iter)) == ITER_OK) { + const char *refname = iter->base.refname; + const char *prefix = iter->prefix; + if (iter->flags & DO_FOR_EACH_PER_WORKTREE_ONLY && !is_per_worktree_ref(iter->base.refname)) continue; @@ -951,12 +954,41 @@ static int packed_ref_iterator_advance(struct ref_iterator *ref_iterator) &iter->oid, iter->flags)) continue; + while (prefix && *prefix) { + if (*refname < *prefix) + BUG("packed-refs backend yielded reference preceding its prefix"); + else if (*refname > *prefix) + return ITER_DONE; + prefix++; + refname++; + } + return ITER_OK; } return ok; } +static int packed_ref_iterator_seek(struct ref_iterator *ref_iterator, + const char *prefix) +{ + 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); + else + start = iter->snapshot->start; + + free(iter->prefix); + iter->prefix = xstrdup_or_null(prefix); + iter->pos = start; + iter->eof = iter->snapshot->eof; + + return 0; +} + static int packed_ref_iterator_peel(struct ref_iterator *ref_iterator, struct object_id *peeled) { @@ -979,11 +1011,13 @@ static void packed_ref_iterator_release(struct ref_iterator *ref_iterator) (struct packed_ref_iterator *)ref_iterator; strbuf_release(&iter->refname_buf); free(iter->jump); + free(iter->prefix); release_snapshot(iter->snapshot); } static struct ref_iterator_vtable packed_ref_iterator_vtable = { .advance = packed_ref_iterator_advance, + .seek = packed_ref_iterator_seek, .peel = packed_ref_iterator_peel, .release = packed_ref_iterator_release, }; @@ -1097,7 +1131,6 @@ static struct ref_iterator *packed_ref_iterator_begin( { struct packed_ref_store *refs; struct snapshot *snapshot; - const char *start; struct packed_ref_iterator *iter; struct ref_iterator *ref_iterator; unsigned int required_flags = REF_STORE_READ; @@ -1113,14 +1146,6 @@ static struct ref_iterator *packed_ref_iterator_begin( */ snapshot = get_snapshot(refs); - if (prefix && *prefix) - start = find_reference_location(snapshot, prefix, 0); - else - start = snapshot->start; - - if (start == snapshot->eof) - return empty_ref_iterator_begin(); - CALLOC_ARRAY(iter, 1); ref_iterator = &iter->base; base_ref_iterator_init(ref_iterator, &packed_ref_iterator_vtable); @@ -1130,19 +1155,15 @@ static struct ref_iterator *packed_ref_iterator_begin( iter->snapshot = snapshot; acquire_snapshot(snapshot); - - iter->pos = start; - iter->eof = snapshot->eof; strbuf_init(&iter->refname_buf, 0); - iter->base.oid = &iter->oid; - iter->repo = ref_store->repo; iter->flags = flags; - if (prefix && *prefix) - /* Stop iteration after we've gone *past* prefix: */ - ref_iterator = prefix_ref_iterator_begin(ref_iterator, prefix, 0); + if (packed_ref_iterator_seek(&iter->base, prefix) < 0) { + ref_iterator_free(&iter->base); + return NULL; + } return ref_iterator; } -- cgit v1.3-5-g9baa From a95da5c8aec733c5b2e051bdfaa451f11570e87a Mon Sep 17 00:00:00 2001 From: Patrick Steinhardt Date: Wed, 12 Mar 2025 16:56:21 +0100 Subject: refs/iterator: implement seeking for files iterators Implement seeking for "files" iterators. As we simply use a ref-cache iterator under the hood the implementation is straight-forward. Note that we do not implement seeking on reflog iterators, same as with the "reftable" backend. Signed-off-by: Patrick Steinhardt Signed-off-by: Junio C Hamano --- refs/files-backend.c | 16 ++++++++++++++++ 1 file changed, 16 insertions(+) (limited to 'refs') diff --git a/refs/files-backend.c b/refs/files-backend.c index e97a267ad6..5f921e85eb 100644 --- a/refs/files-backend.c +++ b/refs/files-backend.c @@ -918,6 +918,14 @@ static int files_ref_iterator_advance(struct ref_iterator *ref_iterator) return ok; } +static int files_ref_iterator_seek(struct ref_iterator *ref_iterator, + const char *prefix) +{ + struct files_ref_iterator *iter = + (struct files_ref_iterator *)ref_iterator; + return ref_iterator_seek(iter->iter0, prefix); +} + static int files_ref_iterator_peel(struct ref_iterator *ref_iterator, struct object_id *peeled) { @@ -936,6 +944,7 @@ static void files_ref_iterator_release(struct ref_iterator *ref_iterator) static struct ref_iterator_vtable files_ref_iterator_vtable = { .advance = files_ref_iterator_advance, + .seek = files_ref_iterator_seek, .peel = files_ref_iterator_peel, .release = files_ref_iterator_release, }; @@ -2294,6 +2303,12 @@ static int files_reflog_iterator_advance(struct ref_iterator *ref_iterator) return ok; } +static int files_reflog_iterator_seek(struct ref_iterator *ref_iterator UNUSED, + const char *prefix UNUSED) +{ + BUG("ref_iterator_seek() called for reflog_iterator"); +} + static int files_reflog_iterator_peel(struct ref_iterator *ref_iterator UNUSED, struct object_id *peeled UNUSED) { @@ -2309,6 +2324,7 @@ static void files_reflog_iterator_release(struct ref_iterator *ref_iterator) static struct ref_iterator_vtable files_reflog_iterator_vtable = { .advance = files_reflog_iterator_advance, + .seek = files_reflog_iterator_seek, .peel = files_reflog_iterator_peel, .release = files_reflog_iterator_release, }; -- cgit v1.3-5-g9baa