`hashmap_new`: huge `cap` hangs forever; huge `elsize` returns a live map that crashes on the first insert

[yayong3]

Summary

hashmap_new / hashmap_new_with_allocator do not check overflow while rounding cap up to a power of two, or while computing the bucket stride from elsize. Both are public size_t arguments.

1. cap. The constructor doubles ncap until ncap >= cap. On a 64-bit size_t, the largest representable power of two is 2^63. For any cap > 2^63 (including SIZE_MAX), ncap wraps to 0 and the loop never terminates. This happens before any large allocation, so the process just hangs. A realistic mistake is passing SIZE_MAX for “as large as possible”.
2. elsize. bucketsz = sizeof(struct bucket) + elsize wraps when elsize is huge. The constructor still returns a non-NULL map with map->elsize left at the original value. The first hashmap_set then memcpys that huge length and crashes.

Normal sizes (cap = 0 → 16, elsize = sizeof(struct T)) are unaffected.

Present on 3735986 (“Add direct bucket access”).

Code

/* hashmap_new_with_allocator — hashmap.c */

size_t ncap = 16;
if (cap < ncap) {
    cap = ncap;
} else {
    while (ncap < cap) {
        ncap *= 2;          /* wraps to 0 when cap > 2^63 */
    }
    cap = ncap;
}
size_t bucketsz = sizeof(struct bucket) + elsize;  /* wraps for huge elsize */
while (bucketsz & (sizeof(uintptr_t)-1)) {
    bucketsz++;
}

hashmap_new forwards both arguments unchanged:

return hashmap_new_with_allocator(NULL, NULL, NULL, elsize, cap, ...);

The insert path then copies map->elsize bytes, not bucketsz:

/* hashmap_set_with_hash, hashmap.c:286 */
memcpy(eitem, item, map->elsize);

Reproduce

From the hashmap.c tree (hashmap.c + hashmap.h in the current directory).

1) cap = SIZE_MAX — hang

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

static uint64_t hash_int(const void *item, uint64_t seed0, uint64_t seed1)
{
    (void)seed0; (void)seed1;
    return (uint64_t)*(const int *)item;
}

static int cmp_int(const void *a, const void *b, void *udata)
{
    int da, db;
    (void)udata;
    da = *(const int *)a;
    db = *(const int *)b;
    return (da > db) - (da < db);
}

int main(void)
{
    size_t cap = (size_t)-1;
    struct hashmap *map;

    fprintf(stderr, "calling hashmap_new(elsize=%zu, cap=SIZE_MAX=%zu)\n",
            sizeof(int), cap);
    fflush(stderr);
    map = hashmap_new(sizeof(int), cap, 0, 0, hash_int, cmp_int, NULL, NULL);
    fprintf(stderr, "hashmap_new returned %p\n", (void *)map);
    return 0;
}

cc -std=c99 -O0 -g -o poc poc.c hashmap.c
timeout 2s ./poc; echo exit:$?

Observed (x86_64, GNU timeout):

calling hashmap_new(elsize=4, cap=SIZE_MAX=18446744073709551615)
exit:124

hashmap_new never returns. 124 is timeout killing a still-running process. The hang is the doubling loop, not a giant malloc.

2) elsize = SIZE_MAX — construct succeeds, first set crashes

Complete program (helpers included so the ASan frame poc.c:26 matches):

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

static uint64_t hash_int(const void *item, uint64_t seed0, uint64_t seed1)
{
    (void)seed0; (void)seed1;
    return (uint64_t)*(const int *)item;
}
static int cmp_int(const void *a, const void *b, void *udata)
{
    int da, db; (void)udata;
    da = *(const int *)a; db = *(const int *)b;
    return (da > db) - (da < db);
}
int main(void)
{
    struct hashmap *map;
    int item = 42;
    fprintf(stderr, "calling hashmap_new(elsize=SIZE_MAX, cap=16)\n");
    map = hashmap_new((size_t)-1, 16, 0, 0, hash_int, cmp_int, NULL, NULL);
    fprintf(stderr, "hashmap_new returned %p\n", (void *)map);
    if (!map) return 1;
    fprintf(stderr, "calling hashmap_set\n");
    hashmap_set(map, &item);
    fprintf(stderr, "hashmap_set returned\n");
    return 0;
}

cc -std=c99 -O0 -g -fsanitize=address -o poc poc.c hashmap.c
ASAN_OPTIONS='abort_on_error=1:halt_on_error=1' ./poc

Observed:

calling hashmap_new(elsize=SIZE_MAX, cap=16)
hashmap_new returned 0x610000000040
calling hashmap_set
ERROR: AddressSanitizer: negative-size-param: (size=-1)
    #0 __interceptor_memcpy
    #1 hashmap_set_with_hash hashmap.c:286
    #2 hashmap_set           hashmap.c:321
    #3 main                  poc.c:26

Address ... is located in stack of thread T0 at offset 32 in frame main
  This frame has 1 object(s):
    [32, 36) 'item' (line 20)
SUMMARY: AddressSanitizer: negative-size-param ... in __interceptor_memcpy

size=-1 is ASan’s rendering of memcpy(..., SIZE_MAX). The constructor returned a live pointer; it should have returned NULL.

Suggested fix

Fail the constructor instead of wrapping:

• Before ncap *= 2, if ncap > SIZE_MAX / 2, return NULL.
• Before sizeof(struct bucket) + elsize (and before the alignment bump), if the add would wrap, return NULL.
• Optionally also reject bucketsz * nbuckets wrapping when allocating the bucket array.

I would keep this as one issue: both bugs are missing overflow checks in the same function.

Environment

• tidwall/hashmap.c 3735986
• Linux x86_64, gcc 12.2.0
• Hang: timeout 2s → exit 124
• Insert crash: -fsanitize=address, ASan negative-size-param at hashmap.c:286