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

From: Carlo Arenas <carenas@gmail.com>
Date: Aug 9, 2021, 01:35 UTC
Message-ID: <CAPUEsphf9F1+=zOMKx3j=jH8xqDwQX99+9uHiYUpXhFE1nervg@mail.gmail.com>
In-Reply-To: <20210807224957.GA5068@dcvr>

On Sat, Aug 7, 2021 at 3:51 PM Eric Wong <e@80x24.org> wrote:

Show 46 quoted lines

>
> 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

My somewhat naive suggestion was to avoid the struct nesting by removing struct oidtree_node and using a struct cb_node directly.

Will reply with a small series of patches that fix pedantic related warnings in ew/many-alternate-optim on top of next.

Carlo