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, 29 insertions, 20 deletions

diff --git a/erts/emulator/beam/external.c b/erts/emulator/beam/external.c
index 67584e38ec..cfac7a5290 100644
--- a/erts/emulator/beam/external.c
+++ b/erts/emulator/beam/external.c
@@ -3035,7 +3035,6 @@ dec_pid(ErtsDistExternal *edep, ErtsHeapFactory* factory, const byte* ep,
 #define ENC_BIN_COPY ((Eterm) 3)
 #define ENC_MAP_PAIR ((Eterm) 4)
 #define ENC_HASHMAP_NODE ((Eterm) 5)
-#define ENC_STORE_MAP_ELEMENT ((Eterm) 6)
 #define ENC_START_SORTING_MAP ((Eterm) 7)
 #define ENC_CONTINUE_SORTING_MAP ((Eterm) 8)
 #define ENC_PUSH_SORTED_MAP ((Eterm) 9)
@@ -3193,18 +3192,32 @@ enc_term_int(TTBEncodeContext* ctx, ErtsAtomCacheMap *acmp, Eterm obj, byte* ep,
 	case ENC_HASHMAP_NODE:
 	    if (is_list(obj)) { /* leaf node [K|V] */
 		ptr = list_val(obj);
+                if (dflags & DFLAG_DETERMINISTIC) {
+                    *next_map_element++ = CAR(ptr);
+                    *next_map_element++ = CDR(ptr);
+                    goto outer_loop;
+                }
 		WSTACK_PUSH2(s, ENC_TERM, CDR(ptr));
 		obj = CAR(ptr);
 	    }
-	    break;
-	case ENC_STORE_MAP_ELEMENT:  /* option `deterministic` */
-	    if (is_list(obj)) { /* leaf node [K|V] */
-		ptr = list_val(obj);
-                *next_map_element++ = CAR(ptr);
-                *next_map_element++ = CDR(ptr);
+            else if (is_tuple(obj)) { /* collision node */
+                Uint tpl_sz;
+                ptr = tuple_val(obj);
+                tpl_sz = arityval(*ptr);
+                ASSERT(tpl_sz >= 2);
+                ptr++;
+                WSTACK_RESERVE(s, tpl_sz * 2);
+                while(tpl_sz--) {
+                    ASSERT(is_list(*ptr));
+                    WSTACK_FAST_PUSH(s, ENC_HASHMAP_NODE);
+                    WSTACK_FAST_PUSH(s, *ptr++);
+                }
                 goto outer_loop;
-	    }
-	    break;
+            }
+            else
+                ASSERT((*boxed_val(obj) & _HEADER_MAP_SUBTAG_MASK)
+                       == HAMT_SUBTAG_NODE_BITMAP);
+            break;
 	case ENC_START_SORTING_MAP: /* option `deterministic` */
             {
                 long num_reductions = r;
@@ -3489,7 +3502,6 @@ enc_term_int(TTBEncodeContext* ctx, ErtsAtomCacheMap *acmp, Eterm obj, byte* ep,
 	    } else {
 		Eterm hdr;
 		Uint node_sz;
-                Eterm node_processor;
 		ptr = boxed_val(obj);
 		hdr = *ptr;
 		ASSERT(is_header(hdr));
@@ -3530,17 +3542,14 @@ enc_term_int(TTBEncodeContext* ctx, ErtsAtomCacheMap *acmp, Eterm obj, byte* ep,
 		    node_sz = hashmap_bitcount(MAP_HEADER_VAL(hdr));
 		    ASSERT(node_sz < 17);
 		    break;
-		default:
-		    erts_exit(ERTS_ERROR_EXIT, "bad header\r\n");
-		}
-
+                default:
+                    erts_exit(ERTS_ERROR_EXIT, "bad header\r\n");
+                }
 		ptr++;
-                node_processor = (dflags & DFLAG_DETERMINISTIC) ?
-                    ENC_STORE_MAP_ELEMENT : ENC_HASHMAP_NODE;
 		WSTACK_RESERVE(s, node_sz*2);
 		while(node_sz--) {
-                    WSTACK_FAST_PUSH(s, node_processor);
-		    WSTACK_FAST_PUSH(s, *ptr++);
+                    WSTACK_FAST_PUSH(s, ENC_HASHMAP_NODE);
+                    WSTACK_FAST_PUSH(s, *ptr++);
 		}
 	    }
 	    break;
@@ -5312,8 +5321,8 @@ encode_size_struct_int(TTBSizeContext* ctx, ErtsAtomCacheMap *acmp, Eterm obj,
 		    node_sz = hashmap_bitcount(MAP_HEADER_VAL(hdr));
 		    ASSERT(node_sz < 17);
 		    break;
-		default:
-		    erts_exit(ERTS_ERROR_EXIT, "bad header\r\n");
+                default:
+                    erts_exit(ERTS_ERROR_EXIT, "bad header\r\n");
 		}
 
 		ptr++;