aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorJohn Högberg <[email protected]>2018-07-19 11:41:06 +0200
committerJohn Högberg <[email protected]>2018-09-13 09:02:40 +0200
commit6f5a0d5f83668d4b53fcce9a6c927e30df169765 (patch)
treef3ce8ad3ae1382c6e7723c039bb4ec7b1a1edb82
parentffa54a25e1cc9c6d0b93dcd3a84ae9c8962ff7ec (diff)
downloadotp-6f5a0d5f83668d4b53fcce9a6c927e30df169765.tar.gz
otp-6f5a0d5f83668d4b53fcce9a6c927e30df169765.tar.bz2
otp-6f5a0d5f83668d4b53fcce9a6c927e30df169765.zip
Improve trapping in lists:reverse/2
If the process had more free space than reductions it could run a lot longer than it was supposed to. It didn't honor the number of reductions going in either, nor did it bump reductions when returning its result or erroring out. This commit also removes this function from a work function in scheduler_SUITE as it's extremely sensitive to the number of reductions spent in the test, causing equal_and_high_with_part_time_max to fail on some machines.
-rw-r--r--erts/emulator/beam/erl_bif_lists.c160
-rw-r--r--erts/emulator/test/scheduler_SUITE.erl4
2 files changed, 106 insertions, 58 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) ->