aboutsummaryrefslogtreecommitdiffstats
path: root/erts/emulator/beam
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 /erts/emulator/beam
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.
Diffstat (limited to 'erts/emulator/beam')
-rw-r--r--erts/emulator/beam/erl_bif_lists.c160
1 files changed, 103 insertions, 57 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