From: Patrick Steinhardt <ps@pks.im>
Date: Fri, 09 Jan 2026 14:19:20 GMT
Subject: Re: [PATCH v2] reftable/iter: fix UB in indexed_table_ref_iter_next
Message-ID: <aWEOaFpjj5DhFBlC@pks.im>
In-Reply-To: <f4gLTILYbAvRqE-aKM3PTyIajeuZBM2Vgo5V66Q8gI6gpI0niPpz8w_lMa29V4Rou2TJ95SKwm2B16KitVrt47KtCzY-eRBm7kemh0iw82s=@protonmail.com>

On Thu, Jan 08, 2026 at 04:52:05PM +0000, Tsahi Elkayam wrote:
> The indexed_table_ref_iter_next() function provides reverse mappings from
> object IDs to references. It currently accesses ref->value.val2 without
> checking the reference's value_type, leading to undefined behavior when
> encountering unpeeled references (REFTABLE_REF_VAL1).
> 
> While the current "obj" table implementation is suboptimal—it yields all
> reference records within a block and relies on manual filtering—this
> manual comparison is necessary to ensure the yielded record actually
> matches the target OID prefix requested by the caller.

It's correct to yield all ref records of an indexed ref block, as any of
its refs may point to the object ID. What's incorrect is that we:

  - Don't seek to the correct obj index block when creating the
    iterator. This means that we'll also seek into ref blocks that won't
    even contain any ref with the desired object ID.

  - Don't abort iterating over the obj index blocks once we see that its
    object IDs no longer match.

So this needs a bit of rephrasing. Please feel free to copy these two
bullet points as-is.

> Fix the undefined behavior by checking the value_type before performing
> the memory comparison. Additionally, replace the "/* BUG */" comment
> with a TODO explaining the current implementation's inefficiency, as
> suggested by the maintainer.

I wouldn't refer to myself as maintainer, I'm very happy to let Junio
have that role :) You can for example simply add a "Helped-by:" trailer
that refers to me.

> diff --git a/reftable/iter.c b/reftable/iter.c
> index 2ecc52b336..2eee65bb1e 100644
> --- a/reftable/iter.c
> +++ b/reftable/iter.c
> @@ -171,12 +171,19 @@ static int indexed_table_ref_iter_next(void *p, struct reftable_record rec)
>  			}
>  			continue;
>  		}
> -		/* BUG */
> -		if (!memcmp(it->oid.buf, ref->value.val2.target_value,
> -			    it->oid.len) ||
> -		    !memcmp(it->oid.buf, ref->value.val2.value, it->oid.len)) {
> +
> +		/*
> +		 * TODO: The current implementation is suboptimal as it yields
> +		 * all ref records in the block rather than filtering by the
> +		 * OID prefix. This manual comparison is still necessary.
> +		 */

And this needs a bit of rephrasing to represent the above. For example:

    /*
     * TODO: The current implementation is suboptimal as:
     *
     *  - We don't seek to the first obj record that matches our OID
     *    prefix.
     *
     *  - We don't abort iteration once the OID prefix doesn't match
     *    anymore.
     *
     * We don't have any users of this interface in-tree, but once we
     * add any we should probably try to fix this interface.
     */

Thanks!

Patrick