erts: Implement hashmap collision nodes

Restrict depth of hashmap tree to 8 levels.
Instead of rehashing with salt, give up and put colliding keys
in "collision nodes" at the bottom of the tree.

Collision nodes are normal tuples of arity 2 or larger.
The elements of collision nodes are key-value cons cells
like the other nodes, but they are sorted in map-key order.
We do linear search in them, but that's ok as they should
be small and rare in practice.

Why?
We had some scary encounter with forever colliding term pairs
in make_internal_hash(). Even though that has been fixed
we will sleep better at night knowing the hashmaps may
not recurse forever draining all memory of the machine.

1 files changed, 22 insertions, 8 deletions

diff --git a/erts/emulator/beam/erl_map.h b/erts/emulator/beam/erl_map.h
index b451bad7e1..9ecacb8aa0 100644
--- a/erts/emulator/beam/erl_map.h
+++ b/erts/emulator/beam/erl_map.h
@@ -56,17 +56,15 @@ typedef struct flatmap_s {
 /* the head-node is a bitmap or array with an untagged size */
 
 #define hashmap_size(x)               (((hashmap_head_t*) hashmap_val(x))->size)
-#define hashmap_make_hash(Key)        make_map_hash(Key, 0)
+#define hashmap_make_hash(Key)        make_map_hash(Key)
 
 #define hashmap_restore_hash(Lvl, Key)                                        \
-    (((Lvl) < 8) ?                                                            \
-     hashmap_make_hash(Key) >> (4*(Lvl)) :                                    \
-     make_map_hash(Key, ((Lvl) >> 3)) >> (4 * ((Lvl) & 7)))
+    (ASSERT(Lvl < 8),                                                         \
+     hashmap_make_hash(Key) >> (4*(Lvl)))
 
 #define hashmap_shift_hash(Hx, Lvl, Key)                                      \
-    (((++(Lvl)) & 7) ?                                                        \
-     (Hx) >> 4 :                                                              \
-     make_map_hash(Key, ((Lvl) >> 3)))
+    (++(Lvl), ASSERT(Lvl <= HAMT_MAX_LEVEL), /* we allow one level too much */\
+     (Hx) >> 4)
 
 /* erl_term.h stuff */
 #define flatmap_get_values(x)        (((Eterm *)(x)) + sizeof(flatmap_t)/sizeof(Eterm))
@@ -147,7 +145,8 @@ typedef struct hashmap_head_s {
 
 /* erl_map.h stuff */
 
-#define is_hashmap_header_head(x) ((MAP_HEADER_TYPE(x) & (0x2)))
+#define is_hashmap_header_head(x) (MAP_HEADER_TYPE(x) & (0x2))
+#define is_hashmap_header_node(x) (MAP_HEADER_TYPE(x) == 1)
 
 #define MAKE_MAP_HEADER(Type,Arity,Val) \
     (_make_header(((((Uint16)(Val)) << MAP_HEADER_ARITY_SZ) | (Arity)) << MAP_HEADER_TAG_SZ | (Type) , _TAG_HEADER_MAP))
@@ -164,12 +163,21 @@ typedef struct hashmap_head_s {
 #define MAP_HEADER_HAMT_NODE_BITMAP(Bmp) \
     MAKE_MAP_HEADER(MAP_HEADER_TAG_HAMT_NODE_BITMAP,0x0,Bmp)
 
+#define MAP_HEADER_HAMT_COLLISION_NODE(Arity) make_arityval(Arity)
+
 #define MAP_HEADER_FLATMAP_SZ  (sizeof(flatmap_t) / sizeof(Eterm))
 
 #define HAMT_NODE_ARRAY_SZ      (17)
 #define HAMT_HEAD_ARRAY_SZ      (18)
 #define HAMT_NODE_BITMAP_SZ(n)  (1 + n)
 #define HAMT_HEAD_BITMAP_SZ(n)  (2 + n)
+#define HAMT_COLLISION_NODE_SZ(n)     (1 + n)
+/*
+ * Collision nodes are used when all hash bits have been exhausted.
+ * They are normal tuples of arity 2 or larger. The elements of a collision
+ * node tuple contain key-value cons cells like the other nodes,
+ * but they are sorted in map-key order.
+ */
 
 /* 2 bits maps tag + 4 bits subtag + 2 ignore bits */
 #define _HEADER_MAP_SUBTAG_MASK       (0xfc)
@@ -183,11 +191,17 @@ typedef struct hashmap_head_s {
 
 #define hashmap_index(hash)      (((Uint32)hash) & 0xf)
 
+#define HAMT_MAX_LEVEL 8
+
 /* hashmap heap size:
    [one cons cell + one list term in parent node] per key
    [one header + one boxed term in parent node] per inner node
    [one header + one size word] for root node
    Observed average number of nodes per key is about 0.35.
+
+   Amendment: This size estimation does not take collision nodes into account.
+              It should be good enough though, as collision nodes are rare
+              and only make the size smaller compared to unlimited HAMT depth.
 */
 #define HASHMAP_WORDS_PER_KEY 3
 #define HASHMAP_WORDS_PER_NODE 2