This problem was originally reported by Brent E Stephens <bestephe.com> in a private email, I'm opening the bugzilla on behalf of Brent.

Brent observed if he called hash_create() with an initial table size of 65536 it would corrupt memory. Under the default parameters the corruption can occur if the initial table size > 1024.

This occurs because at line 568 of dhash.c is this loop:

for (i = 0; i < count; i++) {
    table->directory[i] = (segment_t *)halloc(table, table->segment_size * sizeof(segment_t));

The directory array is allocated above and the count variable is not bounded by the size of the directory array.

Briefly the count variable is meant to be the next power of two less then two to the number of bits allocated to a segment (sorry, that's obscure).

The number of buckets in the hash table is 2**directory_bits + 2**segment_bits. By default both directory_bits and segment_bits is 5, therefore in a default case the directory size is 32 and the segment size is 32 yielding 1024 buckets.

The value of count above will exceed 32 (the default length of the directory) when the initial count > 1024.

There are two problems with the directory initialization loop:

1) It was not bounded by the directory size.

2) It was a dubious optimization.  The idea was to pre-populate every conceivable bucket based on the initial size. But the whole point of a dynamic hash table is to allow it's internal data structure to grow or contract based on the current number of items in the table to strike a balance between memory usage and performance. But if one pre-allocates based on an initial size you lose the memory advantage. The disadvantage is further compounded by the fact after the first item is entered into the table the table will examine it's memory usage based on having just one item and may elect to contract the table to conserve memory. The table should be initialized to it's minimum size and allow to grow naturally.

The correct optimization based on the suggested table size is to adjust the number of directory_bits and segment_bits to accommodate the suggested table size. The directory_bits and segment_bits are fixed at table creation time and previously assumed default values of 5 unless overridden via parameters in create_table_ex(). It's the directory_bits and segment_bits which potentially have more impact on the table performance thus they should have been influenced by the suggested table size (because those values influence the length of the bucket chain which must be traversed on a hash collision). The bottom line is that optimal performance is a function of the number of hash collisions vs. memory utilization which is an extremely hard thing to predict a priori. But adjusting the memory utilization via the size of the directory_bits and segment_bits based on the anticipated table size is probably as close as we can get. The ideal is to have the number of buckets equal the table size and for every item in the table to hash to a unique bucket. We want to avoid buckets with long chains or buckets with no chains. Since we can't predict the hash collision a priori our next best solution is to allow the table to grow to where the number of buckets matches the number of entries. This can be done by choosing directory_bits and segment_bits based on the table size. The number of collisions will determine how many of the buckets have more than one entry and how many buckets are unpopulated. If the number of buckets >= table size and there are no collisions we've reached optimal performance in terms of the number of processor cycles used to locate the item in the table (of course that has to be balanced against processor cache misses and virtual memory paging if we use too much memory).

Sorry for the long rant, but to fix the bug I had to take a long hard look at how memory was utilized and to refer back to the ACM paper the original implementation was based on. Also, the original implementation did not have the ability to contract the table to conserve memory, thus there was an advantage to pre-allocating based on suggested table size. That pre-allocation survived the later addition of the contraction logic. As far as I can tell the original implementation always contained the bug which did not bound to the pre-allocation loop to the directory size.