Re: [PATCH] oidtree: avoid unaligned access to crit-bit tree

[Junio C Hamano <gitster@pobox.com>]

René Scharfe <l.s.r@web.de> writes:

> The flexible array member "k" of struct cb_node is used to store the key
> of the crit-bit tree node.  It offers no alignment guarantees -- in fact
> the current struct layout puts it one byte after a 4-byte aligned
> address, i.e. guaranteed to be misaligned.
>
> oidtree uses a struct object_id as cb_node key.  Since cf0983213c (hash:
> add an algo member to struct object_id, 2021-04-26) it requires 4-byte
> alignment.  The mismatch is reported by UndefinedBehaviorSanitizer at
> runtime like this:
>
> hash.h:277:2: runtime error: member access within misaligned address 0x00015000802d for type 'struct object_id', which requires 4 byte alignment
> 0x00015000802d: note: pointer points here
>  00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  00
>              ^
> SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior hash.h:277:2 in
>
> We can fix that by:
>
> 1. eliminating the alignment requirement of struct object_id,
> 2. providing the alignment in struct cb_node, or
> 3. avoiding the issue by only using memcpy to access "k".
>
> Currently we only store one of two values in "algo" in struct object_id.
> We could use a uint8_t for that instead and widen it only once we add
> support for our twohundredth algorithm or so.  That would not only avoid
> alignment issues, but also reduce the memory requirements for each
> instance of struct object_id by ca. 9%.
>
> Supporting keys with alignment requirements might be useful to spread
> the use of crit-bit trees.  It can be achieved by using a wider type for
> "k" (e.g. uintmax_t), using different types for the members "byte" and
> "otherbits" (e.g. uint16_t or uint32_t for each), or by avoiding the use
> of flexible arrays like khash.h does.
>
> This patch implements the third option, though, because it has the least
> potential for causing side-effects and we're close to the next release.
> If one of the other options is implemented later as well to get their
> additional benefits we can get rid of the extra copies introduced here.
>
> Reported-by: Andrzej Hunt <andrzej@ahunt.org>
> Signed-off-by: René Scharfe <l.s.r@web.de>
> ---
>  cbtree.h  |  2 +-
>  hash.h    |  2 +-
>  oidtree.c | 20 +++++++++++++++-----
>  3 files changed, 17 insertions(+), 7 deletions(-)

Thanks.  Among the choices you considered (and I agree that each of
them is a solution that goes in a reasonable direction), the one
chosen here certainly is the least risky one.