René Scharfe <l.s.r@xxxxxx> 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@xxxxxxxxx> > Signed-off-by: René Scharfe <l.s.r@xxxxxx> > --- > 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.
