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 --- refs/iterator.c | 100 ++++++++++++++++++++------------------------------------ 1 file changed, 35 insertions(+), 65 deletions(-) (limited to 'refs/iterator.c') 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; } -- cgit v1.3 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/iterator.c') 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 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/iterator.c') 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