When playing with the hash table implementation in GNU make 4.1, I stumbled across the following bug: hash tables with an ht_size < 16 can get stuck in an endless loop.
The problematic code is on hash.c:55
ht->ht_capacity = ht->ht_size - (ht->ht_size / 16); /* 93.75% loading factor */
If ht->ht_size < 16, ht->ht_capacity is equal to ht->ht_size. This causes an endless loop in hash_find_slot when ht_fill == ht_capacity.
At the moment the initial sizes of all hash tables are at least 16, so the bug is not triggered in the default configuration.
You can trigger it by e.g. defining SMALL_SCOPE_VARIABLE_BUCKETS when building make:
CPPFLAGS='-DSMALL_SCOPE_VARIABLE_BUCKETS=5' make -e
A Makefile with the following contents then causes make to hang:
reverse = $(15) $(14) $(13) $(12) $(11) $(10) $(9) $(8) $(7) $(6) $(5) $(4) $(3) $(2) $(1)
bar:
echo $(call reverse,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15)
A fix would be to make sure that the initial hash table size is at least 16. In hash_init:
ht->ht_size = round_up_2 (size | 15);
As a side note, I found the comments for round_up_2 misleading at best: round_up_2(8) returns 16, not 8 like the comments would lead one to be believe.
Regards,
Peter Gijsels