aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorJohn Högberg <[email protected]>2018-09-17 11:28:10 +0200
committerJohn Högberg <[email protected]>2018-09-17 11:28:10 +0200
commit3a33f5ffe2d130789a7ebc45df75dbb56988016e (patch)
tree29d220227d4bc989ac818fbf9a68fa351534246a
parent01cb61c5dc84bd64acfdfb69f1b072d026cfa114 (diff)
parent6f5a0d5f83668d4b53fcce9a6c927e30df169765 (diff)
downloadotp-3a33f5ffe2d130789a7ebc45df75dbb56988016e.tar.gz
otp-3a33f5ffe2d130789a7ebc45df75dbb56988016e.tar.bz2
otp-3a33f5ffe2d130789a7ebc45df75dbb56988016e.zip
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
-rw-r--r--erts/emulator/beam/erl_bif_lists.c160
-rw-r--r--erts/emulator/test/scheduler_SUITE.erl4
-rw-r--r--erts/preloaded/ebin/prim_file.beambin27800 -> 27780 bytes
-rw-r--r--erts/preloaded/src/prim_file.erl2
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
Binary files differ
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;