Re: [PATCH v2 5/5] oidtree: a crit-bit tree for odb_loose_cache

> On Sat, Aug 7, 2021 at 3:51 PM Eric Wong <e@80x24.org> wrote:
>>
>> René Scharfe <l.s.r@web.de> wrote:
>>> Am 06.08.21 um 17:31 schrieb Andrzej Hunt:
>>>> On 29/06/2021 22:53, Eric Wong wrote:
>>>>> [...snip...]
>>>>> diff --git a/oidtree.c b/oidtree.c
>>>>> new file mode 100644
>>>>> index 0000000000..c1188d8f48
>>>>> --- /dev/null
>>>>> +++ b/oidtree.c
>>
>>>>> +struct oidtree_node {
>>>>> +    /* n.k[] is used to store "struct object_id" */
>>>>> +    struct cb_node n;
>>>>> +};
>>>>> +
>>>>> [... snip ...]
>>>>> +
>>>>> +void oidtree_insert(struct oidtree *ot, const struct object_id *oid)
>>>>> +{
>>>>> +    struct oidtree_node *on;
>>>>> +
>>>>> +    if (!ot->mempool)
>>>>> +        ot->mempool = allocate_alloc_state();
>>>>> +    if (!oid->algo)
>>>>> +        BUG("oidtree_insert requires oid->algo");
>>>>> +
>>>>> +    on = alloc_from_state(ot->mempool, sizeof(*on) + sizeof(*oid));
>>>>> +    oidcpy_with_padding((struct object_id *)on->n.k, oid);
>>>>
>>>> I think this object_id cast introduced undefined behaviour - here's
>>>> my layperson's interepretation of what's going on (full UBSAN output
>>>> is pasted below):
>>>>
>>>> cb_node.k is a uint8_t[], and hence can be 1-byte aligned (on my
>>>> machine: offsetof(struct cb_node, k) == 21). We're casting its
>>>> pointer to "struct object_id *", and later try to access
>>>> object_id.hash within oidcpy_with_padding. My compiler assumes that
>>>> an object_id pointer needs to be 4-byte aligned, and reading from a
>>>> misaligned pointer means we hit undefined behaviour. (I think the
>>>> 4-byte alignment requirement comes from the fact that object_id's
>>>> largest member is an int?)
>>
>> I seem to recall struct alignment requirements being
>> architecture-dependent; and x86/x86-64 are the most liberal
>> w.r.t alignment requirements.
>
> I think the problem here is not the alignment though, but the fact that
> the nesting of structs with flexible arrays is forbidden by ISO/IEC
> 9899:2011 6.7.2.1¶3 that reads :
>
> 6.7.2.1 Structure and union specifiers
>
> ¶3 A structure or union shall not contain a member with incomplete or
> function type (hence, a structure shall not contain an instance of
> itself, but may contain a pointer to an instance of itself), except
> that the last member of a structure with more than one named member
> may have incomplete array type; such a structure (and any union
> containing, possibly recursively, a member that is such a structure)
> shall not be a member of a structure or an element of an array.
>
> and it will throw a warning with clang 12
> (-Wflexible-array-extensions) or gcc 11 (-Werror=pedantic) when using
> DEVOPTS=pedantic