From ffa54a25e1cc9c6d0b93dcd3a84ae9c8962ff7ec Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?John=20H=C3=B6gberg?= Date: Thu, 19 Jul 2018 11:46:23 +0200 Subject: Fix unsafe use of lists:reverse/1 We said reverse/2 but used reverse/1 which is unsafe to use in preloaded modules. This didn't have any effect in practice as the affected functions weren't used before the code server was started, but it's still an error. --- erts/preloaded/ebin/prim_file.beam | Bin 27800 -> 27780 bytes erts/preloaded/src/prim_file.erl | 2 +- 2 files changed, 1 insertion(+), 1 deletion(-) diff --git a/erts/preloaded/ebin/prim_file.beam b/erts/preloaded/ebin/prim_file.beam index 3316e4348c..df611f2bb0 100644 Binary files a/erts/preloaded/ebin/prim_file.beam and b/erts/preloaded/ebin/prim_file.beam 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; -- cgit v1.2.1 From 6f5a0d5f83668d4b53fcce9a6c927e30df169765 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?John=20H=C3=B6gberg?= Date: Thu, 19 Jul 2018 11:41:06 +0200 Subject: 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. --- erts/emulator/beam/erl_bif_lists.c | 160 +++++++++++++++++++++------------ erts/emulator/test/scheduler_SUITE.erl | 4 +- 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) -> -- cgit v1.2.1