erts: Remove hashmap probabilistic heap overestimation

by adding a dynamic heap factory.

"binary_to_term" is now a hybrid solution with both
a call to decoded_size() to calculate needed heap space
AND possible dynamic allocation of more heap space
if needed for big maps.

The heap size returned from decoded_size() is guaranteed
to be sufficient for all term heap data except for hashmap
nodes. All hashmap nodes are created at the end of dec_term()
by invoking the heap factory interface that may allocate more
heap space on process heap or in fragments.

With this commit it is no longer guaranteed that a message
is confined to only one heap fragment.

1 files changed, 17 insertions, 10 deletions

diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c
index a1bd39dbc8..09fc9a2ad6 100644
--- a/erts/emulator/beam/erl_map.c
+++ b/erts/emulator/beam/erl_map.c
@@ -410,8 +410,9 @@ static Eterm hashmap_from_validated_list(Process *p, Eterm list, Uint size) {
     }
     UnUseTmpHeap(2,p);
 
-    factory.p = p;
+    erts_factory_proc_init(&factory, p);
     res = hashmap_from_unsorted_array(&factory, hxns, size, 0);
+    erts_factory_close(&factory);
 
     erts_free(ERTS_ALC_T_TMP, (void *) hxns);
     ERTS_VERIFY_UNUSED_TEMP_ALLOC(p);
@@ -515,8 +516,9 @@ Eterm erts_hashmap_from_ks_and_vs_extra(Process *p, Eterm *ks, Eterm *vs, Uint n
 	hxns[i].i    = i;
     }
 
-    factory.p = p;
+    erts_factory_proc_init(&factory, p);
     res = hashmap_from_unsorted_array(&factory, hxns, sz, 0);
+    erts_factory_close(&factory);
 
     erts_free(ERTS_ALC_T_TMP, (void *) hxns);
     ERTS_VERIFY_UNUSED_TEMP_ALLOC(p);
@@ -1063,8 +1065,9 @@ static Eterm flatmap_merge(Process *p, Eterm nodeA, Eterm nodeB) {
 	    hxns[i].i    = i;
 	}
 
-        factory.p = p;
+        erts_factory_proc_init(&factory, p);
 	res = hashmap_from_unsorted_array(&factory, hxns, n, 0);
+	erts_factory_close(&factory);
 
 	erts_free(ERTS_ALC_T_TMP, (void *) hxns);
 	ERTS_VERIFY_UNUSED_TEMP_ALLOC(p);
@@ -1107,8 +1110,9 @@ static Eterm map_merge_mixed(Process *p, Eterm flat, Eterm tree, int swap_args)
 	hxns[i].i    = i;
     }
 
-    factory.p = p;
+    erts_factory_proc_init(&factory, p);
     res = hashmap_from_unsorted_array(&factory, hxns, n, 0);
+    erts_factory_close(&factory);
 
     erts_free(ERTS_ALC_T_TMP, (void *) hxns);
     ERTS_VERIFY_UNUSED_TEMP_ALLOC(p);
@@ -2504,6 +2508,9 @@ int erts_validate_and_sort_flatmap(flatmap_t* mp)
     return 1;
 }
 
+#if 0 /* Can't get myself to remove this beautiful piece of code
+         for probabilistic overestimation of nr of nodes in a hashmap */
+
 /* Really rough estimate of sqrt(x)
  * Guaranteed not to be less than sqrt(x)
  */
@@ -2525,7 +2532,10 @@ static int int_sqrt_ceiling(Uint x)
     }
 }
 
-Uint hashmap_over_estimated_heap_size(Uint k)
+/* May not be enough if hashing is broken (not uniform)
+ * or if hell freezes over.
+ */
+Uint hashmap_overestimated_node_count(Uint k)
 {
     /* k is nr of key-value pairs.
        N(k) is expected nr of nodes in hamt.
@@ -2539,12 +2549,9 @@ Uint hashmap_over_estimated_heap_size(Uint k)
        by 15 std.devs above the average, which gives a probability for overrun
        less than 1.0e-49 (same magnitude as a git SHA1 collision).
      */
-    Uint max_nodes = 2*k/5 + (15/3)*int_sqrt_ceiling(k);
-    return (k*2 +     /* leaf cons cells */
-	    k +       /* leaf list terms */
-	    max_nodes*2); /* headers + parent boxed terms */
+    return 2*k/5 + 1 + (15/3)*int_sqrt_ceiling(k);
 }
-
+#endif
 
 BIF_RETTYPE erts_debug_map_info_1(BIF_ALIST_1) {
     if (is_hashmap(BIF_ARG_1)) {