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

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

Start in hashmap.c at hashmap_new_with_allocator and inspect the ncap doubling, bucket-stride calculation, allocation, and hashmap_set_with_hash path; hashmap.h shows the public constructor arguments. Reproduce both cases with the supplied timeout and AddressSanitizer commands, then verify that oversized cap or elsize inputs fail safely and normal construction and insertion still work.