From eedfe1a5e3a85ff5ec7ab49d491250f3b501f3ba Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Tue, 8 May 2018 17:20:07 +0200 Subject: erts: Try fix contant maps:next order Symptom: maps:iterator+next returns different orders for the exact same map. Problem: Number of cached key-values within iterator term depends on number of input reductions to erts_internal_map_next_3. Solution: Build cached key-values in destructive non-reverse order to not affect iteration order. --- erts/emulator/beam/erl_map.c | 32 +++++++++++++++++++++----------- 1 file changed, 21 insertions(+), 11 deletions(-) (limited to 'erts/emulator/beam/erl_map.c') diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index 3d565b1bb8..05e8fc11a2 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -3058,7 +3058,7 @@ BIF_RETTYPE erts_internal_map_next_3(BIF_ALIST_3) { Uint path_length = 0; Uint *path_rest = NULL; int i, elems, orig_elems; - Eterm node = map, res, *path_ptr = NULL, *hp; + Eterm node = map, res, *patch_ptr = NULL, *hp; /* A stack WSTACK is used when traversing the hashmap. * It contains: node, idx, sz, ptr @@ -3117,13 +3117,21 @@ BIF_RETTYPE erts_internal_map_next_3(BIF_ALIST_3) { } if (type == iterator) { - /* iterator uses the format {K, V, {K, V, {K, V, [Path | Map]}}}, - * so each element is 4 words large */ + /* + * Iterator uses the format {K1, V1, {K2, V2, {K3, V3, [Path | Map]}}}, + * so each element is 4 words large. + * To make iteration order independent of input reductions + * the KV-pairs are here built in DESTRUCTIVE non-reverse order. + */ hp = HAlloc(BIF_P, 4 * elems); - res = am_none; } else { - /* list used the format [Path, Map, {K,V}, {K,V} | BIF_ARG_3], - * so each element is 2+3 words large */ + /* + * List used the format [Path, Map, {K3,V3}, {K2,V2}, {K1,V1} | BIF_ARG_3], + * so each element is 2+3 words large. + * To make list order independent of input reductions + * the KV-pairs are here built in FUNCTIONAL reverse order + * as this is how the list as a whole is constructed. + */ hp = HAlloc(BIF_P, (2 + 3) * elems); res = BIF_ARG_3; } @@ -3149,9 +3157,9 @@ BIF_RETTYPE erts_internal_map_next_3(BIF_ALIST_3) { if (is_list(ptr[PATH_ELEM(curr_path)])) { Eterm *lst = list_val(ptr[PATH_ELEM(curr_path)]); if (type == iterator) { - res = TUPLE3(hp, CAR(lst), CDR(lst), res); hp += 4; - /* Note where we should patch the Iterator is needed */ - path_ptr = hp-1; + res = TUPLE3(hp, CAR(lst), CDR(lst), make_tuple(hp+4)); + hp += 4; + patch_ptr = hp-1; } else { Eterm tup = TUPLE2(hp, CAR(lst), CDR(lst)); hp += 3; res = CONS(hp, tup, res); hp += 2; @@ -3188,7 +3196,8 @@ BIF_RETTYPE erts_internal_map_next_3(BIF_ALIST_3) { while (idx < sz && elems != 0 && is_list(ptr[idx])) { Eterm *lst = list_val(ptr[idx]); if (type == iterator) { - res = TUPLE3(hp, CAR(lst), CDR(lst), res); hp += 4; + (void) TUPLE3(hp, CAR(lst), CDR(lst), make_tuple(hp+4)); hp += 4; + patch_ptr = hp-1; } else { Eterm tup = TUPLE2(hp, CAR(lst), CDR(lst)); hp += 3; res = CONS(hp, tup, res); hp += 2; @@ -3286,7 +3295,7 @@ BIF_RETTYPE erts_internal_map_next_3(BIF_ALIST_3) { if (type == iterator) { hp = HAlloc(BIF_P, 2); - *path_ptr = CONS(hp, path, map); hp += 2; + *patch_ptr = CONS(hp, path, map); hp += 2; } else { hp = HAlloc(BIF_P, 4); res = CONS(hp, map, res); hp += 2; @@ -3294,6 +3303,7 @@ BIF_RETTYPE erts_internal_map_next_3(BIF_ALIST_3) { } } else { if (type == iterator) { + *patch_ptr = am_none; HRelease(BIF_P, hp + 4 * elems, hp); } else { HRelease(BIF_P, hp + (2+3) * elems, hp); -- cgit v1.2.3