{"thread":{"id":"64718","subject":"[PATCH v2] reftable/iter: fix undefined behavior in indexed_table_ref_iter_next","startedAt":"2026-01-04T10:46:45Z","lastAt":"2026-01-09T14:19:26Z","messageCount":4,"participants":["Tsahi Elkayam","Patrick Steinhardt"],"isPatch":true,"patchVersion":2,"patchTotal":null},"messages":[{"id":"532984","messageId":"iaPdageDbUKEIQVlnOugIRhoojxnFo3j-WJFWY0eC5el1Epu3sxEnto6Lrd3bhAYL0Ry8T3czP5UPhLHX_gfWCDiCoLuMofdRkqfOSYP-Jk=@protonmail.com","threadId":"64718","inReplyTo":null,"subject":"[PATCH v2] reftable/iter: fix undefined behavior in indexed_table_ref_iter_next","fromName":"Tsahi Elkayam","fromEmail":"tsahi.elkayam@protonmail.com","sentAt":"2026-01-04T10:46:40Z","receivedAt":"2026-01-04T10:46:45Z","isPatch":true,"sender":{"key":"tsahi.elkayam@protonmail.com","avatar":null},"body":"\nThe indexed_table_ref_iter_next() function accesses ref->value.val2\nwithout first checking the ref's value_type. This is undefined behavior\nwhen the ref is not of type REFTABLE_REF_VAL2.\n\nThe correct pattern is already used in filtering_ref_iterator_next()\nwhich checks value_type before accessing the appropriate union member.\nApply the same pattern here:\n\n - Check for REFTABLE_REF_VAL2 before accessing val2 members\n - Add missing check for REFTABLE_REF_VAL1 to handle single-value refs\n\nThis was marked with a \"/* BUG */\" comment indicating the issue was\nknown but not yet fixed.\n\nSigned-off-by: Tsahi Elkayam <Tsahi.Elkayam@protonmail.com>\n---\n reftable/iter.c | 13 ++++++++-----\n 1 file changed, 8 insertions(+), 5 deletions(-)\n\ndiff --git a/reftable/iter.c b/reftable/iter.c\nindex 2ecc52b336..2eee65bb1e 100644\n--- a/reftable/iter.c\n+++ b/reftable/iter.c\n@@ -171,12 +171,15 @@ static int indexed_table_ref_iter_next(void *p, struct reftable_record *rec)\n \t\t\t}\n \t\t\tcontinue;\n \t\t}\n-\t\t/* BUG */\n-\t\tif (!memcmp(it->oid.buf, ref->value.val2.target_value,\n-\t\t\t    it->oid.len) ||\n-\t\t    !memcmp(it->oid.buf, ref->value.val2.value, it->oid.len)) {\n+\t\tif (ref->value_type == REFTABLE_REF_VAL2 &&\n+\t\t    (!memcmp(it->oid.buf, ref->value.val2.target_value,\n+\t\t\t     it->oid.len) ||\n+\t\t     !memcmp(it->oid.buf, ref->value.val2.value, it->oid.len)))\n+\t\t\treturn 0;\n+\n+\t\tif (ref->value_type == REFTABLE_REF_VAL1 &&\n+\t\t    !memcmp(it->oid.buf, ref->value.val1, it->oid.len))\n \t\t\treturn 0;\n-\t\t}\n \t}\n }\n \n-- \n2.37.1 (Apple Git-137.1)\n\n\n\n\nSent with Proton Mail secure email.\n"},{"id":"533053","messageId":"aVvR6U6EJ9wfKk8l@pks.im","threadId":"64718","inReplyTo":"iaPdageDbUKEIQVlnOugIRhoojxnFo3j-WJFWY0eC5el1Epu3sxEnto6Lrd3bhAYL0Ry8T3czP5UPhLHX_gfWCDiCoLuMofdRkqfOSYP-Jk=@protonmail.com","subject":"Re: [PATCH v2] reftable/iter: fix undefined behavior in indexed_table_ref_iter_next","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2026-01-05T14:59:53Z","receivedAt":"2026-01-05T15:00:06Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Sun, Jan 04, 2026 at 10:46:40AM +0000, Tsahi Elkayam wrote:\n> The indexed_table_ref_iter_next() function accesses ref->value.val2\n> without first checking the ref's value_type. This is undefined behavior\n> when the ref is not of type REFTABLE_REF_VAL2.\n> \n> The correct pattern is already used in filtering_ref_iterator_next()\n> which checks value_type before accessing the appropriate union member.\n> Apply the same pattern here:\n> \n>  - Check for REFTABLE_REF_VAL2 before accessing val2 members\n>  - Add missing check for REFTABLE_REF_VAL1 to handle single-value refs\n\nOne missing bit is to explain what this is actually supposed to do. That\nis, why do we even compare the data?\n\n> This was marked with a \"/* BUG */\" comment indicating the issue was\n> known but not yet fixed.\n\nThat's an indicator that something was wrong, true. But it doesn't\nreally say what the bug was. What puzzles me is that if the bug was so\neasy to fix, then why didn't the original author already do it?\nUnfortunately, blaming the line points to 46bc0e731a (reftable: read\nreftable files, 2021-10-07), and that commit doesn't really provide much\ncontext either.\n\n> diff --git a/reftable/iter.c b/reftable/iter.c\n> index 2ecc52b336..2eee65bb1e 100644\n> --- a/reftable/iter.c\n> +++ b/reftable/iter.c\n> @@ -171,12 +171,15 @@ static int indexed_table_ref_iter_next(void *p, struct reftable_record *rec)\n>  \t\t\t}\n>  \t\t\tcontinue;\n>  \t\t}\n> -\t\t/* BUG */\n> -\t\tif (!memcmp(it->oid.buf, ref->value.val2.target_value,\n> -\t\t\t    it->oid.len) ||\n> -\t\t    !memcmp(it->oid.buf, ref->value.val2.value, it->oid.len)) {\n> +\t\tif (ref->value_type == REFTABLE_REF_VAL2 &&\n> +\t\t    (!memcmp(it->oid.buf, ref->value.val2.target_value,\n> +\t\t\t     it->oid.len) ||\n> +\t\t     !memcmp(it->oid.buf, ref->value.val2.value, it->oid.len)))\n> +\t\t\treturn 0;\n> +\n> +\t\tif (ref->value_type == REFTABLE_REF_VAL1 &&\n> +\t\t    !memcmp(it->oid.buf, ref->value.val1, it->oid.len))\n>  \t\t\treturn 0;\n> -\t\t}\n>  \t}\n>  }\n\nSo let's take a step back -- what are we even trying to do here?\n\nThe indexed table is basically a table that provides reverse mappings.\nGiven an object ID, it allows us to quickly look up any reference that\npoints to this object ID. We don't make any use of that feature in Git\nright now, but historically it was designed to speed up\n\"uploadpack.allowTipSHA1InWant\". This setting is a lot less relevant\nnowadays, as most forges set \"uploadpack.allowAnySHA1InWant\" to support\npartial clones.\n\nSo this interface is somewhat confusingly named, as the term \"index\" is\noverloaded: we have the \"ref\" and \"log\" indices that enable fast lookup\nof those record types. But what this here refers to is the \"obj\" table.\nOh, well.\n\nThe iterator for those objects takes as input the object ID we're\nsearching for. Given that object ID, it is expected to yield only those\nref records that reference this object ID, either peeled or unpeeled in\ncase it is a tag.\n\nIn the `next()` function we essentially have a nested loop:\n\n  - The outer loop iterates through the \"obj\" blocks. This gives us the\n    offsets of the ref records that we need to look up and that contain.\n\n  - The inner loop iterates through the records in the \"ref\" block that\n    was referenced by the \"obj\" block.\n\nHonestly, the whole logic doesn't really make any sense though, as we\nnever filter by the caller-provided object ID at all! So we still end up\nchurning through all references, which kind of destroys the purpose of\nthis whole \"obj\" reverse index. And that's also why we have the check:\nwe verify that the object ID of the reference we have looked up matches\nthe caller's query.\n\nSo the fix you have here is correct: we may end up with a \"ref\" record\nthat is unpeeled, and in that case it's wrong to treat it as a peeled\none. And if we fix that, the result should at least be correct and void\nof any kind of undefined behaviour. But the whole infrastructure is\nstill quite broken. What we should be doing is to:\n\n  1. Seek to the obj record that has the desired object ID prefix.\n\n  2. For each obj record starting with the desired object ID prefix:\n\n    1. Look up the respective \"ref\" block indicated by the offset.\n\n    2. Iterate through all \"ref\" records and yield all those whose value\n       or peeled value match.\n\n  3. Abort once there are no more obj records matching the given prefix.\n\nAll of this is naturally outside the scope of this patch series. I'd\nargue though that we shouldn't just remove the BUG comment, but instead\nadd some TODO comment that explains why the current logic is still very\nsuboptimal.\n\nThanks!\n\nPatrick\n"},{"id":"533289","messageId":"f4gLTILYbAvRqE-aKM3PTyIajeuZBM2Vgo5V66Q8gI6gpI0niPpz8w_lMa29V4Rou2TJ95SKwm2B16KitVrt47KtCzY-eRBm7kemh0iw82s=@protonmail.com","threadId":"64718","inReplyTo":"aVvR6U6EJ9wfKk8l@pks.im","subject":"[PATCH v2] reftable/iter: fix UB in indexed_table_ref_iter_next","fromName":"Tsahi Elkayam","fromEmail":"tsahi.elkayam@protonmail.com","sentAt":"2026-01-08T16:52:05Z","receivedAt":"2026-01-08T16:52:19Z","isPatch":true,"sender":{"key":"tsahi.elkayam@protonmail.com","avatar":null},"body":"The indexed_table_ref_iter_next() function provides reverse mappings from\nobject IDs to references. It currently accesses ref->value.val2 without\nchecking the reference's value_type, leading to undefined behavior when\nencountering unpeeled references (REFTABLE_REF_VAL1).\n\nWhile the current \"obj\" table implementation is suboptimal—it yields all\nreference records within a block and relies on manual filtering—this\nmanual comparison is necessary to ensure the yielded record actually\nmatches the target OID prefix requested by the caller.\n\nFix the undefined behavior by checking the value_type before performing\nthe memory comparison. Additionally, replace the \"/* BUG */\" comment\nwith a TODO explaining the current implementation's inefficiency, as\nsuggested by the maintainer.\n\nSigned-off-by: Tsahi Elkayam <Tsahi.Elkayam@Protonmail.com>\n---\n reftable/iter.c | 13 ++++++++++---\n 1 file changed, 10 insertions(+), 3 deletions(-)\n\ndiff --git a/reftable/iter.c b/reftable/iter.c\nindex 2ecc52b336..2eee65bb1e 100644\n--- a/reftable/iter.c\n+++ b/reftable/iter.c\n@@ -171,12 +171,19 @@ static int indexed_table_ref_iter_next(void *p, struct reftable_record rec)\n \t\t\t}\n \t\t\tcontinue;\n \t\t}\n-\t\t/* BUG */\n-\t\tif (!memcmp(it->oid.buf, ref->value.val2.target_value,\n-\t\t\t    it->oid.len) ||\n-\t\t    !memcmp(it->oid.buf, ref->value.val2.value, it->oid.len)) {\n+\n+\t\t/*\n+\t\t * TODO: The current implementation is suboptimal as it yields\n+\t\t * all ref records in the block rather than filtering by the\n+\t\t * OID prefix. This manual comparison is still necessary.\n+\t\t */\n+\t\tif (ref->value_type == REFTABLE_REF_VAL2 &&\n+\t\t    (!memcmp(it->oid.buf, ref->value.val2.target_value,\n+\t\t\t     it->oid.len) ||\n+\t\t     !memcmp(it->oid.buf, ref->value.val2.value, it->oid.len)))\n+\t\t\treturn 0;\n+\n+\t\tif (ref->value_type == REFTABLE_REF_VAL1 &&\n+\t\t    !memcmp(it->oid.buf, ref->value.val1, it->oid.len))\n \t\t\treturn 0;\n-\t\t}\n \t}\n }\n--\n2.47.1\n"},{"id":"533367","messageId":"aWEOaFpjj5DhFBlC@pks.im","threadId":"64718","inReplyTo":"f4gLTILYbAvRqE-aKM3PTyIajeuZBM2Vgo5V66Q8gI6gpI0niPpz8w_lMa29V4Rou2TJ95SKwm2B16KitVrt47KtCzY-eRBm7kemh0iw82s=@protonmail.com","subject":"Re: [PATCH v2] reftable/iter: fix UB in indexed_table_ref_iter_next","fromName":"Patrick Steinhardt","fromEmail":"ps@pks.im","sentAt":"2026-01-09T14:19:20Z","receivedAt":"2026-01-09T14:19:26Z","isPatch":true,"sender":{"key":"ps@pks.im","avatar":"https://avatars.githubusercontent.com/u/4056630?v=4"},"body":"On Thu, Jan 08, 2026 at 04:52:05PM +0000, Tsahi Elkayam wrote:\n> The indexed_table_ref_iter_next() function provides reverse mappings from\n> object IDs to references. It currently accesses ref->value.val2 without\n> checking the reference's value_type, leading to undefined behavior when\n> encountering unpeeled references (REFTABLE_REF_VAL1).\n> \n> While the current \"obj\" table implementation is suboptimal—it yields all\n> reference records within a block and relies on manual filtering—this\n> manual comparison is necessary to ensure the yielded record actually\n> matches the target OID prefix requested by the caller.\n\nIt's correct to yield all ref records of an indexed ref block, as any of\nits refs may point to the object ID. What's incorrect is that we:\n\n  - Don't seek to the correct obj index block when creating the\n    iterator. This means that we'll also seek into ref blocks that won't\n    even contain any ref with the desired object ID.\n\n  - Don't abort iterating over the obj index blocks once we see that its\n    object IDs no longer match.\n\nSo this needs a bit of rephrasing. Please feel free to copy these two\nbullet points as-is.\n\n> Fix the undefined behavior by checking the value_type before performing\n> the memory comparison. Additionally, replace the \"/* BUG */\" comment\n> with a TODO explaining the current implementation's inefficiency, as\n> suggested by the maintainer.\n\nI wouldn't refer to myself as maintainer, I'm very happy to let Junio\nhave that role :) You can for example simply add a \"Helped-by:\" trailer\nthat refers to me.\n\n> diff --git a/reftable/iter.c b/reftable/iter.c\n> index 2ecc52b336..2eee65bb1e 100644\n> --- a/reftable/iter.c\n> +++ b/reftable/iter.c\n> @@ -171,12 +171,19 @@ static int indexed_table_ref_iter_next(void *p, struct reftable_record rec)\n>  \t\t\t}\n>  \t\t\tcontinue;\n>  \t\t}\n> -\t\t/* BUG */\n> -\t\tif (!memcmp(it->oid.buf, ref->value.val2.target_value,\n> -\t\t\t    it->oid.len) ||\n> -\t\t    !memcmp(it->oid.buf, ref->value.val2.value, it->oid.len)) {\n> +\n> +\t\t/*\n> +\t\t * TODO: The current implementation is suboptimal as it yields\n> +\t\t * all ref records in the block rather than filtering by the\n> +\t\t * OID prefix. This manual comparison is still necessary.\n> +\t\t */\n\nAnd this needs a bit of rephrasing to represent the above. For example:\n\n    /*\n     * TODO: The current implementation is suboptimal as:\n     *\n     *  - We don't seek to the first obj record that matches our OID\n     *    prefix.\n     *\n     *  - We don't abort iteration once the OID prefix doesn't match\n     *    anymore.\n     *\n     * We don't have any users of this interface in-tree, but once we\n     * add any we should probably try to fix this interface.\n     */\n\nThanks!\n\nPatrick\n"}]}