`hashmap_murmur`: unaligned `uint32_t` loads and signed `uint8_t << 24` in `MM86128`

[yayong3]

Summary

hashmap_murmur() is a documented hash helper (const void *data, no alignment requirement). It forwards to MM86128, which:

1. Reinterprets the input as const uint32_t * and loads 32-bit lanes. An unaligned pointer is undefined in C and can SIGBUS on some ARM cores. x86 usually still computes a hash.
2. In the tail, does tail[i] << 24 on a uint8_t. That byte promotes to signed int. If it is >= 128, 128 << 24 is not representable in 32-bit int (C11 6.5.7).

The same file’s xxHash path already uses memcpy (XXH_read32 / XXH_read64) for this reason. SipHash reads bytes. Only Murmur still type-puns.

Not every hash call hits this: hashmap_sip / hashmap_xxhash3 are fine. Length < 16 skips the block loads (issue 1). The << 24 tails are lengths with len % 16 ∈ {4, 8, 12}.

Present on 3735986.

Code

/* MM86128 — hashmap.c */

const uint32_t * blocks = (const uint32_t *)(data + nblocks*16);
for (int i = -nblocks; i; i++) {
    uint32_t k1 = blocks[i*4+0];   /* :596 unaligned load */
    uint32_t k2 = blocks[i*4+1];
    uint32_t k3 = blocks[i*4+2];
    uint32_t k4 = blocks[i*4+3];
    ...
}
...
switch(len & 15) {
case 12: k3 ^= tail[11] << 24;  /* :620  also case 8 (:626) and case 4 (:632) */

Public entry:

uint64_t hashmap_murmur(const void *data, size_t len, uint64_t seed0, uint64_t seed1)
{
    (void)seed1;
    return MM86128(data, len, seed0);
}

Reproduce

From the hashmap.c tree. UBSan is required to see the diagnostics on x86_64; the functions still return a hash there.

cc -std=c99 -O0 -g -fsanitize=undefined -o poc poc.c hashmap.c
UBSAN_OPTIONS='print_stacktrace=1:halt_on_error=0' ./poc

1) Unaligned 16-byte field (offset 1)

Typical use: hash a char[] member that sits after a 1-byte tag.

#include <stdio.h>
#include <stddef.h>
#include <stdint.h>
#include <string.h>
#include "hashmap.h"

struct rec {
    uint8_t kind;
    char key[16];
};

int main(void)
{
    struct rec r;
    uint64_t h;
    memset(&r, 0, sizeof r);
    r.kind = 1;
    memcpy(r.key, "0123456789abcdef", 16);
    fprintf(stderr, "offsetof(key)=%zu addr=%p\n",
            offsetof(struct rec, key), (void *)r.key);
    h = hashmap_murmur(r.key, sizeof r.key, 1, 2);
    fprintf(stderr, "hash=0x%llx\n", (unsigned long long)h);
    return 0;
}

Observed:

offsetof(key)=1 addr=0x7ffc158cc0c1
hashmap.c:596:18: runtime error: load of misaligned address 0x7ffc158cc0c1 for type 'const uint32_t', which requires 4 byte alignment
    #0 MM86128        hashmap.c:596
    #1 hashmap_murmur hashmap.c:787
    #2 main           poc.c:21
hashmap.c:597:18: runtime error: load of misaligned address ...
hashmap.c:598:18: runtime error: load of misaligned address ...
hashmap.c:599:18: runtime error: load of misaligned address ...
hash=0x18cc75b97e461b4e

(addr and the later three diagnostics vary by run; the first load is always r.key at offset 1. The hash value above is from this binary.)

2) 12-byte key, last byte 0x80 (signed << 24)

12 bytes selects case 12. A high-bit last byte is normal for binary / UTF-8 keys.

#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include "hashmap.h"

int main(void)
{
    unsigned char key[12];
    uint64_t h;
    memset(key, 0, sizeof key);
    memcpy(key, "session_id_", 11);
    key[11] = 0x80;
    fprintf(stderr, "len=12 last=0x%02x\n", key[11]);
    h = hashmap_murmur(key, sizeof key, 1, 2);
    fprintf(stderr, "hash=0x%llx\n", (unsigned long long)h);
    return 0;
}

Observed:

len=12 last=0x80
hashmap.c:620:29: runtime error: left shift of 128 by 24 places cannot be represented in type 'int'
    #0 MM86128        hashmap.c:620
    #1 hashmap_murmur hashmap.c:787
    #2 main           poc.c:14
hash=0xc71725878ca1c1e9

On this x86_64 box the call still returns a hash. The shift is still undefined; a different ISA or a later compiler may not be so kind.

Suggested fix

Match xxHash in the same file:

• Load k1..k4 with memcpy into a uint32_t (or reuse XXH_read32).
• Shift tails as unsigned, e.g. ((uint32_t)tail[11]) << 24.

Same change for case 8 / case 4 (tail[7], tail[3]).

Environment

• tidwall/hashmap.c 3735986
• Linux x86_64, gcc 12.2.0, -fsanitize=undefined
• Unaligned: UBSan at hashmap.c:596 (and 597–599)
• Shift: UBSan at hashmap.c:620