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

Am 09.08.21 um 03:35 schrieb Carlo Arenas:

On Sat, Aug 7, 2021 at 3:51 PM Eric Wong [off-list ref] wrote:

quoted

René Scharfe [off-list ref] wrote:

quoted

Am 06.08.21 um 17:31 schrieb Andrzej Hunt:

quoted

On 29/06/2021 22:53, Eric Wong wrote:

quoted

[...snip...]

diff --git a/oidtree.c b/oidtree.c
new file mode 100644
index 0000000000..c1188d8f48
--- /dev/null
+++ b/oidtree.c

quoted

quoted

quoted

+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

That's an additional problem.  UBSan still reports the alignment error
with your patches.

René