Merge branch 'john/erts/improve-list-reverse-trapping/OTP-15199' into maint

* john/erts/improve-list-reverse-trapping/OTP-15199:
  Improve trapping in lists:reverse/2
  Fix unsafe use of lists:reverse/1

4 files changed, 107 insertions, 59 deletions

diff --git a/erts/emulator/beam/erl_bif_lists.c b/erts/emulator/beam/erl_bif_lists.c
index 73d327da3e..01e09da34c 100644
--- a/erts/emulator/beam/erl_bif_lists.c
+++ b/erts/emulator/beam/erl_bif_lists.c
@@ -277,75 +277,121 @@ BIF_RETTYPE lists_member_2(BIF_ALIST_2)
     BIF_RET2(am_false, CONTEXT_REDS - max_iter/10);
 }
 
-BIF_RETTYPE lists_reverse_2(BIF_ALIST_2)
+static BIF_RETTYPE lists_reverse_alloc(Process *c_p,
+                                       Eterm list_in,
+                                       Eterm tail_in)
 {
-    Eterm list;
-    Eterm tmp_list;
-    Eterm result;
-    Eterm* hp;
-    Uint n;
-    int max_iter;
-    
-    /*
-     * Handle legal and illegal non-lists quickly.
-     */
-    if (is_nil(BIF_ARG_1)) {
-	BIF_RET(BIF_ARG_2);
-    } else if (is_not_list(BIF_ARG_1)) {
-    error:
-	BIF_ERROR(BIF_P, BADARG);
+    static const Uint CELLS_PER_RED = 40;
+
+    Eterm *heap_top, *heap_end;
+    Uint cells_left, max_cells;
+    Eterm list, tail;
+    Eterm lookahead;
+
+    list = list_in;
+    tail = tail_in;
+
+    cells_left = max_cells = CELLS_PER_RED * (1 + ERTS_BIF_REDS_LEFT(c_p));
+    lookahead = list;
+
+    while (cells_left != 0 && is_list(lookahead)) {
+        lookahead = CDR(list_val(lookahead));
+        cells_left--;
     }
 
-    /*
-     * First use the rest of the remaning heap space.
-     */
-    list = BIF_ARG_1;
-    result = BIF_ARG_2;
-    hp = HEAP_TOP(BIF_P);
-    n = HeapWordsLeft(BIF_P) / 2;
-    while (n != 0 && is_list(list)) {
-	Eterm* pair = list_val(list);
-	result = CONS(hp, CAR(pair), result);
-	list = CDR(pair);
-	hp += 2;
-	n--;
+    BUMP_REDS(c_p, (max_cells - cells_left) / CELLS_PER_RED);
+
+    if (is_not_list(lookahead) && is_not_nil(lookahead)) {
+        BIF_ERROR(c_p, BADARG);
     }
-    HEAP_TOP(BIF_P) = hp;
+
+    heap_top = HAlloc(c_p, 2 * (max_cells - cells_left));
+    heap_end = heap_top + 2 * (max_cells - cells_left);
+
+    while (heap_top < heap_end) {
+        Eterm *pair = list_val(list);
+
+        tail = CONS(heap_top, CAR(pair), tail);
+        list = CDR(pair);
+
+        ASSERT(is_list(list) || is_nil(list));
+
+        heap_top += 2;
+    }
+
     if (is_nil(list)) {
-	BIF_RET(result);
+        BIF_RET(tail);
     }
 
-    /*
-     * Calculate length of remaining list (up to a suitable limit).
-     */
-    max_iter = CONTEXT_REDS * 40;
-    n = 0;
-    tmp_list = list;
-    while (max_iter-- > 0 && is_list(tmp_list)) {
-	tmp_list = CDR(list_val(tmp_list));
-	n++;
+    ASSERT(is_list(tail) && cells_left == 0);
+    BIF_TRAP2(bif_export[BIF_lists_reverse_2], c_p, list, tail);
+}
+
+static BIF_RETTYPE lists_reverse_onheap(Process *c_p,
+                                        Eterm list_in,
+                                        Eterm tail_in)
+{
+    static const Uint CELLS_PER_RED = 60;
+
+    Eterm *heap_top, *heap_end;
+    Uint cells_left, max_cells;
+    Eterm list, tail;
+
+    list = list_in;
+    tail = tail_in;
+
+    cells_left = max_cells = CELLS_PER_RED * (1 + ERTS_BIF_REDS_LEFT(c_p));
+
+    ASSERT(HEAP_LIMIT(c_p) >= HEAP_TOP(c_p) + 2);
+    heap_end = HEAP_LIMIT(c_p) - 2;
+    heap_top = HEAP_TOP(c_p);
+
+    while (heap_top < heap_end && is_list(list)) {
+        Eterm *pair = list_val(list);
+
+        tail = CONS(heap_top, CAR(pair), tail);
+        list = CDR(pair);
+
+        heap_top += 2;
     }
-    if (is_not_nil(tmp_list) && is_not_list(tmp_list)) {
-	goto error;
+
+    cells_left -= (heap_top - heap_end) / 2;
+    BUMP_REDS(c_p, (max_cells - cells_left) / CELLS_PER_RED);
+    HEAP_TOP(c_p) = heap_top;
+
+    if (is_nil(list)) {
+        BIF_RET(tail);
+    } else if (is_list(list)) {
+        ASSERT(is_list(tail));
+
+        if (cells_left > CELLS_PER_RED) {
+            return lists_reverse_alloc(c_p, list, tail);
+        }
+
+        BUMP_ALL_REDS(c_p);
+        BIF_TRAP2(bif_export[BIF_lists_reverse_2], c_p, list, tail);
     }
 
-    /*
-     * Now do one HAlloc() and continue reversing.
-     */
-    hp = HAlloc(BIF_P, 2*n);
-    while (n != 0 && is_list(list)) {
-	Eterm* pair = list_val(list);
-	result = CONS(hp, CAR(pair), result);
-	list = CDR(pair);
-	hp += 2;
-	n--;
+    BIF_ERROR(c_p, BADARG);
+}
+
+BIF_RETTYPE lists_reverse_2(BIF_ALIST_2)
+{
+    /* Handle legal and illegal non-lists quickly. */
+    if (is_nil(BIF_ARG_1)) {
+        BIF_RET(BIF_ARG_2);
+    } else if (is_not_list(BIF_ARG_1)) {
+        BIF_ERROR(BIF_P, BADARG);
     }
-    if (is_nil(list)) {
-	BIF_RET(result);
-    } else {
-	BUMP_ALL_REDS(BIF_P);
-	BIF_TRAP2(bif_export[BIF_lists_reverse_2], BIF_P, list, result);
+
+    /* We build the reversal on the unused part of the heap if possible to save
+     * us the trouble of having to figure out the list size. We fall back to
+     * lists_reverse_alloc when we run out of space. */
+    if (HeapWordsLeft(BIF_P) > 8) {
+        return lists_reverse_onheap(BIF_P, BIF_ARG_1, BIF_ARG_2);
     }
+
+    return lists_reverse_alloc(BIF_P, BIF_ARG_1, BIF_ARG_2);
 }
 
 BIF_RETTYPE
diff --git a/erts/emulator/test/scheduler_SUITE.erl b/erts/emulator/test/scheduler_SUITE.erl
index 7eebbe8b19..d98edd1ec2 100644
--- a/erts/emulator/test/scheduler_SUITE.erl
+++ b/erts/emulator/test/scheduler_SUITE.erl
@@ -2155,7 +2155,7 @@ workers_exit([Ps|Pss])  ->
     workers_exit(Pss).
 
 do_work(PartTime) ->
-    lists:reverse(lists:seq(1, 50)),
+    _ = id(lists:seq(1, 50)),
     receive stop_work -> receive after infinity -> ok end after 0 -> ok end,
     case PartTime of
 	true -> receive after 1 -> ok end;
@@ -2163,6 +2163,8 @@ do_work(PartTime) ->
     end,
     do_work(PartTime).
 
+id(I) -> I.
+
 workers(N, _Prio, _PartTime) when N =< 0 ->
     [];
 workers(N, Prio, PartTime) ->
diff --git a/erts/preloaded/ebin/prim_file.beam b/erts/preloaded/ebin/prim_file.beam
index 3316e4348c..df611f2bb0 100644
--- a/erts/preloaded/ebin/prim_file.beam
+++ b/erts/preloaded/ebin/prim_file.beam
diff --git a/erts/preloaded/src/prim_file.erl b/erts/preloaded/src/prim_file.erl
index 517ca74301..6d85868183 100644
--- a/erts/preloaded/src/prim_file.erl
+++ b/erts/preloaded/src/prim_file.erl
@@ -786,7 +786,7 @@ altname_nif(_Path) ->
 
 %% We know for certain that lists:reverse/2 is a BIF, so it's safe to use it
 %% even though this module is preloaded.
-reverse_list(List) -> lists:reverse(List).
+reverse_list(List) -> lists:reverse(List, []).
 
 proplist_get_value(_Key, [], Default) ->
     Default;