diff options
Diffstat (limited to 'erts/emulator/test/map_SUITE.erl')
| -rw-r--r-- | erts/emulator/test/map_SUITE.erl | 743 |
1 files changed, 535 insertions, 208 deletions
diff --git a/erts/emulator/test/map_SUITE.erl b/erts/emulator/test/map_SUITE.erl index 1a89101916..02f3c89318 100644 --- a/erts/emulator/test/map_SUITE.erl +++ b/erts/emulator/test/map_SUITE.erl @@ -17,72 +17,72 @@ %% %CopyrightEnd% %% -module(map_SUITE). --export([all/0, suite/0,groups/0,init_per_suite/1, end_per_suite/1, - init_per_group/2,end_per_group/2 - ]). - --export([ - t_build_and_match_literals/1, t_build_and_match_literals_large/1, - t_update_literals/1, t_update_literals_large/1, - t_match_and_update_literals/1, t_match_and_update_literals_large/1, - t_update_map_expressions/1, - t_update_assoc/1, t_update_assoc_large/1, - t_update_exact/1, t_update_exact_large/1, - t_guard_bifs/1, - t_guard_sequence/1, t_guard_sequence_large/1, - t_guard_update/1, t_guard_update_large/1, - t_guard_receive/1, t_guard_receive_large/1, - t_guard_fun/1, - t_update_deep/1, - t_list_comprehension/1, - t_map_sort_literals/1, - t_map_equal/1, - t_map_compare/1, - t_map_size/1, - t_is_map/1, - - %% Specific Map BIFs - t_bif_map_get/1, - t_bif_map_find/1, - t_bif_map_is_key/1, - t_bif_map_keys/1, - t_bif_map_merge/1, - t_bif_map_new/1, - t_bif_map_put/1, - t_bif_map_remove/1, - t_bif_map_update/1, - t_bif_map_values/1, - t_bif_map_to_list/1, - t_bif_map_from_list/1, - - %% erlang - t_erlang_hash/1, - t_map_encode_decode/1, - - %% non specific BIF related - t_bif_build_and_check/1, - t_bif_merge_and_check/1, - - %% maps module not bifs - t_maps_fold/1, - t_maps_map/1, - t_maps_size/1, - t_maps_without/1, - - %% misc - t_hashmap_balance/1, - t_erts_internal_order/1, - t_erts_internal_hash/1, - t_pdict/1, - t_ets/1, - t_dets/1, - t_tracing/1, - - %% instruction-level tests - t_has_map_fields/1, - y_regs/1, - badmap_17/1 - ]). +-export([all/0, suite/0]). + +-export([t_build_and_match_literals/1, t_build_and_match_literals_large/1, + t_update_literals/1, t_update_literals_large/1, + t_match_and_update_literals/1, t_match_and_update_literals_large/1, + t_update_map_expressions/1, + t_update_assoc/1, t_update_assoc_large/1, + t_update_exact/1, t_update_exact_large/1, + t_guard_bifs/1, + t_guard_sequence/1, t_guard_sequence_large/1, + t_guard_update/1, t_guard_update_large/1, + t_guard_receive/1, t_guard_receive_large/1, + t_guard_fun/1, + t_update_deep/1, + t_list_comprehension/1, + t_map_sort_literals/1, + t_map_equal/1, + t_map_compare/1, + t_map_size/1, + t_is_map/1, + + %% Specific Map BIFs + t_bif_map_get/1, + t_bif_map_find/1, + t_bif_map_is_key/1, + t_bif_map_keys/1, + t_bif_map_merge/1, + t_bif_map_new/1, + t_bif_map_put/1, + t_bif_map_remove/1, + t_bif_map_take/1, t_bif_map_take_large/1, + t_bif_map_update/1, + t_bif_map_values/1, + t_bif_map_to_list/1, + t_bif_map_from_list/1, + t_bif_erts_internal_maps_to_list/1, + + %% erlang + t_erlang_hash/1, + t_map_encode_decode/1, + t_gc_rare_map_overflow/1, + + %% non specific BIF related + t_bif_build_and_check/1, + t_bif_merge_and_check/1, + + %% maps module not bifs + t_maps_fold/1, + t_maps_map/1, + t_maps_size/1, + t_maps_without/1, + + %% misc + t_hashmap_balance/1, + t_erts_internal_order/1, + t_erts_internal_hash/1, + t_pdict/1, + t_ets/1, + t_dets/1, + t_tracing/1, + t_hash_entropy/1, + + %% instruction-level tests + t_has_map_fields/1, + y_regs/1, + badmap_17/1]). -include_lib("stdlib/include/ms_transform.hrl"). @@ -95,64 +95,59 @@ suite() -> []. -all() -> [ - t_build_and_match_literals, t_build_and_match_literals_large, - t_update_literals, t_update_literals_large, - t_match_and_update_literals, t_match_and_update_literals_large, - t_update_map_expressions, - t_update_assoc, t_update_assoc_large, - t_update_exact, t_update_exact_large, - t_guard_bifs, - t_guard_sequence, t_guard_sequence_large, - t_guard_update, t_guard_update_large, - t_guard_receive, t_guard_receive_large, - t_guard_fun, t_list_comprehension, - t_update_deep, - t_map_equal, t_map_compare, - t_map_sort_literals, - - %% Specific Map BIFs - t_bif_map_get,t_bif_map_find,t_bif_map_is_key, - t_bif_map_keys, t_bif_map_merge, t_bif_map_new, - t_bif_map_put, - t_bif_map_remove, t_bif_map_update, - t_bif_map_values, - t_bif_map_to_list, t_bif_map_from_list, - - %% erlang - t_erlang_hash, t_map_encode_decode, - t_map_size, t_is_map, - - %% non specific BIF related - t_bif_build_and_check, - t_bif_merge_and_check, - - %% maps module - t_maps_fold, t_maps_map, - t_maps_size, t_maps_without, - - - %% Other functions - t_hashmap_balance, - t_erts_internal_order, - t_erts_internal_hash, - t_pdict, - t_ets, - t_tracing, - - %% instruction-level tests - t_has_map_fields, - y_regs, - badmap_17 - ]. - -groups() -> []. - -init_per_suite(Config) -> Config. -end_per_suite(_Config) -> ok. - -init_per_group(_GroupName, Config) -> Config. -end_per_group(_GroupName, Config) -> Config. +all() -> [t_build_and_match_literals, t_build_and_match_literals_large, + t_update_literals, t_update_literals_large, + t_match_and_update_literals, t_match_and_update_literals_large, + t_update_map_expressions, + t_update_assoc, t_update_assoc_large, + t_update_exact, t_update_exact_large, + t_guard_bifs, + t_guard_sequence, t_guard_sequence_large, + t_guard_update, t_guard_update_large, + t_guard_receive, t_guard_receive_large, + t_guard_fun, t_list_comprehension, + t_update_deep, + t_map_equal, t_map_compare, + t_map_sort_literals, + + %% Specific Map BIFs + t_bif_map_get,t_bif_map_find,t_bif_map_is_key, + t_bif_map_keys, t_bif_map_merge, t_bif_map_new, + t_bif_map_put, + t_bif_map_remove, + t_bif_map_take, t_bif_map_take_large, + t_bif_map_update, + t_bif_map_values, + t_bif_map_to_list, t_bif_map_from_list, + t_bif_erts_internal_maps_to_list, + + %% erlang + t_erlang_hash, t_map_encode_decode, + t_gc_rare_map_overflow, + t_map_size, t_is_map, + + %% non specific BIF related + t_bif_build_and_check, + t_bif_merge_and_check, + + %% maps module + t_maps_fold, t_maps_map, + t_maps_size, t_maps_without, + + + %% Other functions + t_hashmap_balance, + t_erts_internal_order, + t_erts_internal_hash, + t_pdict, + t_ets, + t_tracing, + t_hash_entropy, + + %% instruction-level tests + t_has_map_fields, + y_regs, + badmap_17]. %% tests @@ -1509,11 +1504,8 @@ t_map_equal(Config) when is_list(Config) -> t_map_compare(Config) when is_list(Config) -> - Seed = {erlang:monotonic_time(), - erlang:time_offset(), - erlang:unique_integer()}, - io:format("seed = ~p\n", [Seed]), - random:seed(Seed), + rand:seed(exsplus), + io:format("seed = ~p\n", [rand:export_seed()]), repeat(100, fun(_) -> float_int_compare() end, []), repeat(100, fun(_) -> recursive_compare() end, []), ok. @@ -1531,7 +1523,7 @@ float_int_compare() -> numeric_keys(N) -> lists:foldl(fun(_,Acc) -> - Int = random:uniform(N*4) - N*2, + Int = rand:uniform(N*4) - N*2, Float = float(Int), [Int, Float, Float * 0.99, Float * 1.01 | Acc] end, @@ -1562,7 +1554,7 @@ do_compare([Gen1, Gen2]) -> %% Change one key from int to float (or vice versa) and check compare ML1 = maps:to_list(M1), - {K1,V1} = lists:nth(random:uniform(length(ML1)), ML1), + {K1,V1} = lists:nth(rand:uniform(length(ML1)), ML1), case K1 of I when is_integer(I) -> case maps:find(float(I),M1) of @@ -1653,9 +1645,9 @@ cmp_others(T1, T2, _) -> map_gen(Pairs, Size) -> {_,L} = lists:foldl(fun(_, {Keys, Acc}) -> - KI = random:uniform(size(Keys)), + KI = rand:uniform(size(Keys)), K = element(KI,Keys), - KV = element(random:uniform(size(K)), K), + KV = element(rand:uniform(size(K)), K), {erlang:delete_element(KI,Keys), [KV | Acc]} end, {Pairs, []}, @@ -1695,20 +1687,19 @@ term_gen_recursive(Leafs, Flags, Depth) -> MaxDepth = 10, Rnd = case {Flags, Depth} of {_, MaxDepth} -> % Only leafs - random:uniform(size(Leafs)) + 3; + rand:uniform(size(Leafs)) + 3; {0, 0} -> % Only containers - random:uniform(3); + rand:uniform(3); {0,_} -> % Anything - random:uniform(size(Leafs)+3) + rand:uniform(size(Leafs)+3) end, case Rnd of 1 -> % Make map - Size = random:uniform(size(Leafs)), + Size = rand:uniform(size(Leafs)), lists:foldl(fun(_, {Acc1,Acc2}) -> {K1,K2} = term_gen_recursive(Leafs, Flags, Depth+1), {V1,V2} = term_gen_recursive(Leafs, Flags, Depth+1), - %%ok = check_keys(K1,K2, 0), {maps:put(K1,V1, Acc1), maps:put(K2,V2, Acc2)} end, {maps:new(), maps:new()}, @@ -1718,7 +1709,7 @@ term_gen_recursive(Leafs, Flags, Depth) -> {Cdr1,Cdr2} = term_gen_recursive(Leafs, Flags, Depth+1), {[Car1 | Cdr1], [Car2 | Cdr2]}; 3 -> % Make tuple - Size = random:uniform(size(Leafs)), + Size = rand:uniform(size(Leafs)), L = lists:map(fun(_) -> term_gen_recursive(Leafs, Flags, Depth+1) end, lists:seq(1,Size)), {L1, L2} = lists:unzip(L), @@ -1727,7 +1718,7 @@ term_gen_recursive(Leafs, Flags, Depth) -> N -> % Make leaf case element(N-3, Leafs) of I when is_integer(I) -> - case random:uniform(4) of + case rand:uniform(4) of 1 -> {I, float(I)}; 2 -> {float(I), I}; _ -> {I,I} @@ -1736,26 +1727,6 @@ term_gen_recursive(Leafs, Flags, Depth) -> end end. -check_keys(K1, K2, _) when K1 =:= K2 -> - case erlang:phash3(K1) =:= erlang:phash3(K2) of - true -> ok; - false -> - io:format("Same keys with different hash values !!!\nK1 = ~p\nK2 = ~p\n", [K1,K2]), - error - end; -check_keys(K1, K2, 0) -> - case {erlang:phash3(K1), erlang:phash3(K2)} of - {H,H} -> check_keys(K1, K2, 1); - {_,_} -> ok - end; -check_keys(K1, K2, L) when L < 10 -> - case {erlang:phash3([L|K1]), erlang:phash3([L|K2])} of - {H,H} -> check_keys(K1, K2, L+1); - {_,_} -> ok - end; -check_keys(K1, K2, L) -> - io:format("Same hash value at level ~p !!!\nK1 = ~p\nK2 = ~p\n", [L,K1,K2]), - error. %% BIFs t_bif_map_get(Config) when is_list(Config) -> @@ -2005,7 +1976,7 @@ t_bif_map_remove(Config) when is_list(Config) -> 0 = erlang:map_size(maps:remove(some_key, #{})), M0 = #{ "hi" => "hello", int => 3, <<"key">> => <<"value">>, - 4 => number, 18446744073709551629 => wat}, + 4 => number, 18446744073709551629 => wat}, M1 = maps:remove("hi", M0), true = is_members([4,18446744073709551629,int,<<"key">>],maps:keys(M1)), @@ -2034,10 +2005,71 @@ t_bif_map_remove(Config) when is_list(Config) -> %% error case do_badmap(fun(T) -> - {'EXIT',{{badmap,T},[{maps,remove,_,_}|_]}} = - (catch maps:remove(a, T)) + {'EXIT',{{badmap,T},[{maps,remove,_,_}|_]}} = (catch maps:remove(a, T)) end), - ok. + ok. + +t_bif_map_take(Config) when is_list(Config) -> + error = maps:take(some_key, #{}), + + M0 = #{ "hi" => "hello", int => 3, <<"key">> => <<"value">>, + 4 => number, 18446744073709551629 => wat}, + + 5 = maps:size(M0), + {"hello", M1} = maps:take("hi", M0), + true = is_members([4,18446744073709551629,int,<<"key">>],maps:keys(M1)), + true = is_members([number,wat,3,<<"value">>],maps:values(M1)), + error = maps:take("hi", M1), + 4 = maps:size(M1), + + {3, M2} = maps:take(int, M1), + true = is_members([4,18446744073709551629,<<"key">>],maps:keys(M2)), + true = is_members([number,wat,<<"value">>],maps:values(M2)), + error = maps:take(int, M2), + 3 = maps:size(M2), + + {<<"value">>,M3} = maps:take(<<"key">>, M2), + true = is_members([4,18446744073709551629],maps:keys(M3)), + true = is_members([number,wat],maps:values(M3)), + error = maps:take(<<"key">>, M3), + 2 = maps:size(M3), + + {wat,M4} = maps:take(18446744073709551629, M3), + true = is_members([4],maps:keys(M4)), + true = is_members([number],maps:values(M4)), + error = maps:take(18446744073709551629, M4), + 1 = maps:size(M4), + + {number,M5} = maps:take(4, M4), + [] = maps:keys(M5), + [] = maps:values(M5), + error = maps:take(4, M5), + 0 = maps:size(M5), + + {wat,#{ "hi" := "hello", int := 3, 4 := number, <<"key">> := <<"value">>}} = maps:take(18446744073709551629,M0), + + %% error case + do_badmap(fun(T) -> + {'EXIT',{{badmap,T},[{maps,take,_,_}|_]}} = (catch maps:take(a, T)) + end), + ok. + +t_bif_map_take_large(Config) when is_list(Config) -> + KVs = [{{erlang:md5(<<I:64>>),I}, I}|| I <- lists:seq(1,500)], + M0 = maps:from_list(KVs), + ok = bif_map_take_all(KVs, M0), + ok. + +bif_map_take_all([], M0) -> + 0 = maps:size(M0), + ok; +bif_map_take_all([{K,V}|KVs],M0) -> + {ok,V} = maps:find(K,M0), + {V,M1} = maps:take(K,M0), + error = maps:find(K,M1), + error = maps:take(K,M1), + bif_map_take_all(KVs,M1). + t_bif_map_update(Config) when is_list(Config) -> M0 = #{ "hi" => "hello", int => 3, <<"key">> => <<"value">>, @@ -2099,8 +2131,6 @@ t_erlang_hash(Config) when is_list(Config) -> ok = t_bif_erlang_phash2(), ok = t_bif_erlang_phash(), - ok = t_bif_erlang_hash(), - ok. t_bif_erlang_phash2() -> @@ -2143,27 +2173,6 @@ t_bif_erlang_phash() -> 2620391445 = erlang:phash(M2,Sz), % 3590546636 ok. -t_bif_erlang_hash() -> - Sz = 1 bsl 27 - 1, - 39684169 = erlang:hash(#{},Sz), % 5158 - 33673142 = erlang:hash(#{ a => 1, "a" => 2, <<"a">> => 3, {a,b} => 4 },Sz), % 71555838 - 95337869 = erlang:hash(#{ 1 => a, 2 => "a", 3 => <<"a">>, 4 => {a,b} },Sz), % 5497225 - 108959561 = erlang:hash(#{ 1 => a },Sz), % 126071654 - 59623150 = erlang:hash(#{ a => 1 },Sz), % 126426236 - - 42775386 = erlang:hash(#{{} => <<>>},Sz), % 101655720 - 71692856 = erlang:hash(#{<<>> => {}},Sz), % 101655720 - - M0 = #{ a => 1, "key" => <<"value">> }, - M1 = maps:remove("key",M0), - M2 = M1#{ "key" => <<"value">> }, - - 70254632 = erlang:hash(M0,Sz), % 38260486 - 59623150 = erlang:hash(M1,Sz), % 126426236 - 70254632 = erlang:hash(M2,Sz), % 38260486 - ok. - - t_map_encode_decode(Config) when is_list(Config) -> <<131,116,0,0,0,0>> = erlang:term_to_binary(#{}), Pairs = [ @@ -2181,7 +2190,9 @@ t_map_encode_decode(Config) when is_list(Config) -> {<<>>, sc9}, {3.14158, sc10}, {[3.14158], sc11}, {more_atoms, sc12}, {{more_tuples}, sc13}, {self(), sc14}, - {{},{}},{[],[]} + {{},{}},{[],[]}, + {map_s, #{a=>a, 2=>b, 3=>c}}, + {map_l, maps:from_list([{I,I}||I <- lists:seq(1,74)])} ], ok = map_encode_decode_and_match(Pairs,[],#{}), @@ -2245,9 +2256,30 @@ t_map_encode_decode(Config) when is_list(Config) -> %% bad size (too small) .. should fail just truncate it .. weird. %% possibly change external format so truncated will be #{a:=1} - #{ a:=b } = - erlang:binary_to_term(<<131,116,0,0,0,1,100,0,1,97,100,0,1,98,97,1,97,1>>), - + #{ a:=b } = erlang:binary_to_term(<<131,116,0,0,0,1,100,0,1,97,100,0,1,98,97,1,97,1>>), + + %% specific fannerl (opensource app) binary_to_term error in 18.1 + + #{bias := {1,1,0}, + bit_fail := 0, + connections := #{{2,9} := _, + {8,14} := _, + {2,12} := _, + {5,7} := _, + {11,16} := _, + {11,15} := _}, + layers := {5,7,3}, + network_type := fann_nettype_layer, + num_input := 5, + num_layers := 3, + num_output := 3, + rprop_delta_max := _, + rprop_delta_min := _, + total_connections := 66, + total_neurons := 17, + train_error_function := fann_errorfunc_tanh, + train_stop_function := fann_stopfunc_mse, + training_algorithm := fann_train_rprop} = erlang:binary_to_term(fannerl()), ok. map_encode_decode_and_match([{K,V}|Pairs], EncodedPairs, M0) -> @@ -2332,23 +2364,55 @@ t_bif_map_from_list(Config) when is_list(Config) -> {'EXIT', {badarg,_}} = (catch maps:from_list(id(42))), ok. -t_bif_build_and_check(Config) when is_list(Config) -> - ok = check_build_and_remove(750,[ - fun(K) -> [K,K] end, - fun(K) -> [float(K),K] end, - fun(K) -> K end, - fun(K) -> {1,K} end, - fun(K) -> {K} end, - fun(K) -> [K|K] end, - fun(K) -> [K,1,2,3,4] end, - fun(K) -> {K,atom} end, - fun(K) -> float(K) end, - fun(K) -> integer_to_list(K) end, - fun(K) -> list_to_atom(integer_to_list(K)) end, - fun(K) -> [K,{K,[K,{K,[K]}]}] end, - fun(K) -> <<K:32>> end - ]), +t_bif_erts_internal_maps_to_list(Config) when is_list(Config) -> + %% small maps + [] = erts_internal:maps_to_list(#{},-1), + [] = erts_internal:maps_to_list(#{},-2), + [] = erts_internal:maps_to_list(#{},10), + [{a,1},{b,2}] = lists:sort(erts_internal:maps_to_list(#{a=>1,b=>2}, 2)), + [{a,1},{b,2}] = lists:sort(erts_internal:maps_to_list(#{a=>1,b=>2}, -1)), + [{_,_}] = erts_internal:maps_to_list(#{a=>1,b=>2}, 1), + [{a,1},{b,2},{c,3}] = lists:sort(erts_internal:maps_to_list(#{c=>3,a=>1,b=>2},-2)), + [{a,1},{b,2},{c,3}] = lists:sort(erts_internal:maps_to_list(#{c=>3,a=>1,b=>2},3)), + [{a,1},{b,2},{c,3}] = lists:sort(erts_internal:maps_to_list(#{c=>3,a=>1,b=>2},5)), + [{_,_},{_,_}] = erts_internal:maps_to_list(#{c=>3,a=>1,b=>2},2), + [{_,_}] = erts_internal:maps_to_list(#{c=>3,a=>1,b=>2},1), + [] = erts_internal:maps_to_list(#{c=>3,a=>1,b=>2},0), + + %% big maps + M = maps:from_list([{I,ok}||I <- lists:seq(1,500)]), + [] = erts_internal:maps_to_list(M,0), + [{_,_}] = erts_internal:maps_to_list(M,1), + [{_,_},{_,_}] = erts_internal:maps_to_list(M,2), + Ls1 = erts_internal:maps_to_list(M,10), + 10 = length(Ls1), + Ls2 = erts_internal:maps_to_list(M,20), + 20 = length(Ls2), + Ls3 = erts_internal:maps_to_list(M,120), + 120 = length(Ls3), + Ls4 = erts_internal:maps_to_list(M,-1), + 500 = length(Ls4), + %% error cases + {'EXIT', {{badmap,[{a,b},b]},_}} = (catch erts_internal:maps_to_list(id([{a,b},b]),id(1))), + {'EXIT', {badarg,_}} = (catch erts_internal:maps_to_list(id(#{}),id(a))), + {'EXIT', {badarg,_}} = (catch erts_internal:maps_to_list(id(#{1=>2}),id(<<>>))), + ok. + +t_bif_build_and_check(Config) when is_list(Config) -> + ok = check_build_and_remove(750,[fun(K) -> [K,K] end, + fun(K) -> [float(K),K] end, + fun(K) -> K end, + fun(K) -> {1,K} end, + fun(K) -> {K} end, + fun(K) -> [K|K] end, + fun(K) -> [K,1,2,3,4] end, + fun(K) -> {K,atom} end, + fun(K) -> float(K) end, + fun(K) -> integer_to_list(K) end, + fun(K) -> list_to_atom(integer_to_list(K)) end, + fun(K) -> [K,{K,[K,{K,[K]}]}] end, + fun(K) -> <<K:32>> end]), ok. check_build_and_remove(_,[]) -> ok; @@ -2391,6 +2455,9 @@ check_keys_exist([K|Ks],M) -> check_keys_exist(Ks,M). t_bif_merge_and_check(Config) when is_list(Config) -> + + io:format("rand:export_seed() -> ~p\n",[rand:export_seed()]), + %% simple disjunct ones %% make sure all keys are unique Kss = [[a,b,c,d], @@ -2438,8 +2505,49 @@ t_bif_merge_and_check(Config) when is_list(Config) -> M41 = maps:merge(M4,M1), ok = check_key_values(KVs1 ++ [{d,5}] ++ KVs, M41), + [begin Ma = random_map(SzA, a), + Mb = random_map(SzB, b), + ok = merge_maps(Ma, Mb) + end || SzA <- [3,10,20,100,200,1000], SzB <- [3,10,20,100,200,1000]], + + ok. + +% Generate random map with an average of Sz number of pairs: K -> {V,K} +random_map(Sz, V) -> + random_map_insert(#{}, 0, V, Sz*2). + +random_map_insert(M0, K0, _, Sz) when K0 > Sz -> + M0; +random_map_insert(M0, K0, V, Sz) -> + Key = K0 + rand:uniform(3), + random_map_insert(M0#{Key => {V,Key}}, Key, V, Sz). + + +merge_maps(A, B) -> + AB = maps:merge(A, B), + %%io:format("A=~p\nB=~p\n",[A,B]), + maps_foreach(fun(K,VB) -> VB = maps:get(K, AB) + end, B), + maps_foreach(fun(K,VA) -> + case {maps:get(K, AB),maps:find(K, B)} of + {VA, error} -> ok; + {VB, {ok, VB}} -> ok + end + end, A), + + maps_foreach(fun(K,V) -> + case {maps:find(K, A),maps:find(K, B)} of + {{ok, V}, error} -> ok; + {error, {ok, V}} -> ok; + {{ok,_}, {ok, V}} -> ok + end + end, AB), ok. +maps_foreach(Fun, Map) -> + maps:fold(fun(K,V,_) -> Fun(K,V) end, void, Map). + + check_key_values([],_) -> ok; check_key_values([{K,V}|KVs],M) -> V = maps:get(K,M), @@ -2529,7 +2637,7 @@ hashmap_balance(KeyFun) -> F = fun(I, {M0,Max0}) -> Key = KeyFun(I), M1 = M0#{Key => Key}, - Max1 = case erts_internal:map_type(M1) of + Max1 = case erts_internal:term_type(M1) of hashmap -> Nodes = hashmap_nodes(M1), Avg = maps:size(M1) * 0.4, @@ -2922,3 +3030,222 @@ do_badmap_17(Config) -> %% Use this function to avoid compile-time evaluation of an expression. id(I) -> I. + + +%% OTP-13763 +t_hash_entropy(Config) when is_list(Config) -> + %% entropy bug in 18.3, 19.0 + M1 = maps:from_list([{#{"id" => I}, ok}||I <- lists:seq(1,50000)]), + + #{ #{"id" => 100} := ok, + #{"id" => 200} := ok, + #{"id" => 300} := ok, + #{"id" => 400} := ok, + #{"id" => 500} := ok, + #{"id" => 600} := ok, + #{"id" => 700} := ok, + #{"id" => 800} := ok, + #{"id" => 900} := ok, + #{"id" => 25061} := ok, + #{"id" => 39766} := ok } = M1, + + M0 = maps:from_list([{I,ok}||I <- lists:seq(1,33)]), + M2 = maps:from_list([{M0#{"id" => I}, ok}||I <- lists:seq(1,50000)]), + + ok = maps:get(M0#{"id" => 100}, M2), + ok = maps:get(M0#{"id" => 200}, M2), + ok = maps:get(M0#{"id" => 300}, M2), + ok = maps:get(M0#{"id" => 400}, M2), + ok = maps:get(M0#{"id" => 500}, M2), + ok = maps:get(M0#{"id" => 600}, M2), + ok = maps:get(M0#{"id" => 700}, M2), + ok = maps:get(M0#{"id" => 800}, M2), + ok = maps:get(M0#{"id" => 900}, M2), + ok = maps:get(M0#{"id" => 25061}, M2), + ok = maps:get(M0#{"id" => 39766}, M2), + ok. + +%% OTP-13146 +%% Provoke major GC with a lot of "fat" maps on external format in msg queue +%% causing heap fragments to be allocated. +t_gc_rare_map_overflow(Config) when is_list(Config) -> + Pa = filename:dirname(code:which(?MODULE)), + {ok, Node} = test_server:start_node(gc_rare_map_overflow, slave, [{args, "-pa \""++Pa++"\""}]), + erts_debug:set_internal_state(available_internal_state, true), + try + Echo = spawn_link(Node, fun Loop() -> receive {From,Msg} -> From ! Msg + end, + Loop() + end), + FatMap = fatmap(34), + false = (flatmap =:= erts_internal:term_type(FatMap)), + + t_gc_rare_map_overflow_do(Echo, FatMap, fun() -> erlang:garbage_collect() end), + + %% Repeat test for minor gc: + t_gc_rare_map_overflow_do(Echo, FatMap, fun() -> minor_collect() end), + + unlink(Echo), + + %% Test fatmap in exit signal + Exiter = spawn_link(Node, fun Loop() -> receive {_From,Msg} -> + "not_a_map" = Msg % badmatch! + end, + Loop() + end), + process_flag(trap_exit, true), + Exiter ! {self(), FatMap}, + {'EXIT', Exiter, {{badmatch,FatMap}, _}} = receive M -> M end, + ok + + after + process_flag(trap_exit, false), + erts_debug:set_internal_state(available_internal_state, false), + test_server:stop_node(Node) + end. + +t_gc_rare_map_overflow_do(Echo, FatMap, GcFun) -> + Master = self(), + true = receive _M -> false after 0 -> true end, % assert empty msg queue + Echo ! {Master, token}, + repeat(1000, fun(_) -> Echo ! {Master, FatMap} end, void), + + timer:sleep(100), % Wait for maps to arrive in our msg queue + token = receive Tok -> Tok end, % and provoke move from outer to inner msg queue + + %% Do GC that will "overflow" and create heap frags due to all the fat maps + GcFun(), + + %% Now check that all maps in msg queueu are intact + %% Will crash emulator in OTP-18.1 + repeat(1000, fun(_) -> FatMap = receive FM -> FM end end, void), + ok. + +minor_collect() -> + Before = minor_gcs(), + erts_debug:set_internal_state(force_gc, self()), + erlang:yield(), + After = minor_gcs(), + io:format("minor_gcs: ~p -> ~p\n", [Before, After]). + +minor_gcs() -> + {garbage_collection, Info} = process_info(self(), garbage_collection), + {minor_gcs, GCS} = lists:keyfind(minor_gcs, 1, Info), + GCS. + +%% Generate a map with N (or N+1) keys that has an abnormal heap demand. +%% Done by finding keys that collide in the first 32-bit hash. +fatmap(N) -> + %%erts_debug:set_internal_state(available_internal_state, true), + Table = ets:new(void, [bag, private]), + + Seed0 = rand:seed_s(exsplus, {4711, 3141592, 2718281}), + Seed1 = fatmap_populate(Table, Seed0, (1 bsl 16)), + Keys = fatmap_generate(Table, Seed1, N, []), + ets:delete(Table), + maps:from_list([{K,K} || K <- Keys]). + +fatmap_populate(_, Seed, 0) -> Seed; +fatmap_populate(Table, Seed, N) -> + {I, NextSeed} = rand:uniform_s(1 bsl 48, Seed), + Hash = internal_hash(I), + ets:insert(Table, [{Hash, I}]), + fatmap_populate(Table, NextSeed, N-1). + + +fatmap_generate(_, _, N, Acc) when N =< 0 -> + Acc; +fatmap_generate(Table, Seed, N0, Acc0) -> + {I, NextSeed} = rand:uniform_s(1 bsl 48, Seed), + Hash = internal_hash(I), + case ets:member(Table, Hash) of + true -> + NewKeys = [I | ets:lookup_element(Table, Hash, 2)], + Acc1 = lists:usort(Acc0 ++ NewKeys), + N1 = N0 - (length(Acc1) - length(Acc0)), + fatmap_generate(Table, NextSeed, N1, Acc1); + false -> + fatmap_generate(Table, NextSeed, N0, Acc0) + end. + +internal_hash(Term) -> + erts_debug:get_internal_state({internal_hash, Term}). + + +%% map external_format (fannerl). +fannerl() -> + <<131,116,0,0,0,28,100,0,13,108,101,97,114,110,105,110,103,95,114, + 97,116,101,70,63,230,102,102,96,0,0,0,100,0,17,108,101,97,114,110,105,110, + 103,95,109,111,109,101,110,116,117,109,70,0,0,0,0,0,0,0,0,100,0, + 18,116,114,97,105,110,105,110,103,95,97,108,103,111,114,105,116,104,109,100,0, + 16,102,97,110,110,95,116,114,97,105,110,95,114,112,114,111,112, + 100,0,17,109,101,97,110,95,115,113,117,97,114,101,95,101,114,114,111,114,70, + 0,0,0,0,0,0,0,0,100,0,8,98,105,116,95,102,97,105,108,97,0,100,0,20, + 116,114,97,105,110,95,101,114,114,111,114,95,102,117,110,99,116,105,111, + 110,100,0,19,102,97,110,110,95,101,114,114,111,114,102,117,110,99, + 95,116,97,110,104,100,0,9,110,117,109,95,105,110,112,117,116,97,5,100,0,10,110, + 117,109,95,111,117,116,112,117,116,97,3,100,0,13,116,111,116,97,108, + 95,110,101,117,114,111,110,115,97,17,100,0,17,116,111,116,97,108,95,99,111,110, + 110,101,99,116,105,111,110,115,97,66,100,0,12,110,101,116,119,111,114,107, + 95,116,121,112,101,100,0,18,102,97,110,110,95,110,101,116,116,121,112,101, + 95,108,97,121,101,114,100,0,15,99,111,110,110,101,99,116,105,111,110,95, + 114,97,116,101,70,63,240,0,0,0,0,0,0,100,0,10,110,117,109,95,108,97,121,101, + 114,115,97,3,100,0,19,116,114,97,105,110,95,115,116,111,112,95,102,117,110, + 99,116,105,111,110,100,0,17,102,97,110,110,95,115,116,111,112,102,117,110, + 99,95,109,115,101,100,0,15,113,117,105,99,107,112,114,111,112,95,100,101,99, + 97,121,70,191,26,54,226,224,0,0,0,100,0,12,113,117,105,99,107,112,114, + 111,112,95,109,117,70,63,252,0,0,0,0,0,0,100,0,21,114,112,114,111,112,95,105, + 110,99,114,101,97,115,101,95,102,97,99,116,111,114,70,63,243,51,51, + 64,0,0,0,100,0,21,114,112,114,111,112,95,100,101,99,114,101,97,115,101, + 95,102,97,99,116,111,114,70,63,224,0,0,0,0,0,0,100,0,15,114,112,114,111,112, + 95,100,101,108,116,97,95,109,105,110,70,0,0,0,0,0,0,0,0,100,0,15,114,112,114, + 111,112,95,100,101,108,116,97,95,109,97,120,70,64,73,0,0,0,0,0,0,100,0, + 16,114,112,114,111,112,95,100,101,108,116,97,95,122,101,114,111,70,63,185,153, + 153,160,0,0,0,100,0,26,115,97,114,112,114,111,112,95,119,101,105,103, + 104,116,95,100,101,99,97,121,95,115,104,105,102,116,70,192,26,147,116,192,0,0,0, + 100,0,35,115,97,114,112,114,111,112,95,115,116,101,112,95,101,114, + 114,111,114,95,116,104,114,101,115,104,111,108,100,95,102,97,99,116,111,114,70, + 63,185,153,153,160,0,0,0,100,0,24,115,97,114,112,114,111,112,95,115, + 116,101,112,95,101,114,114,111,114,95,115,104,105,102,116,70,63,246,40,245, + 192,0,0,0,100,0,19,115,97,114,112,114,111,112,95,116,101,109,112,101,114, + 97,116,117,114,101,70,63,142,184,81,224,0,0,0,100,0,6,108,97,121,101,114,115, + 104,3,97,5,97,7,97,3,100,0,4,98,105,97,115,104,3,97,1,97,1,97,0,100,0,11, + 99,111,110,110,101,99,116,105,111,110,115,116,0,0,0,66,104,2,97,0,97,6,70, + 191,179,51,44,64,0,0,0,104,2,97,1,97,6,70,63,178,130,90,32,0,0,0,104,2,97,2, + 97,6,70,63,82,90,88,0,0,0,0,104,2,97,3,97,6,70,63,162,91,63,192,0,0,0,104,2, + 97,4,97,6,70,191,151,70,169,0,0,0,0,104,2,97,5,97,6,70,191,117,52,222,0,0,0, + 0,104,2,97,0,97,7,70,63,152,240,139,0,0,0,0,104,2,97,1,97,7,70,191,166,31, + 187,160,0,0,0,104,2,97,2,97,7,70,191,150,70,63,0,0,0,0,104,2,97,3,97,7,70, + 63,152,181,126,128,0,0,0,104,2,97,4,97,7,70,63,151,187,162,128,0,0,0,104,2, + 97,5,97,7,70,191,143,161,101,0,0,0,0,104,2,97,0,97,8,70,191,153,102,36,128,0, + 0,0,104,2,97,1,97,8,70,63,160,139,250,64,0,0,0,104,2,97,2,97,8,70,63,164,62, + 196,64,0,0,0,104,2,97,3,97,8,70,191,178,78,209,192,0,0,0,104,2,97,4,97,8,70, + 191,185,19,76,224,0,0,0,104,2,97,5,97,8,70,63,183,142,196,96,0,0,0,104,2,97,0, + 97,9,70,63,150,104,248,0,0,0,0,104,2,97,1,97,9,70,191,164,4,100,224,0,0,0, + 104,2,97,2,97,9,70,191,169,42,42,224,0,0,0,104,2,97,3,97,9,70,63,145,54,78,128,0, + 0,0,104,2,97,4,97,9,70,63,126,243,134,0,0,0,0,104,2,97,5,97,9,70,63,177, + 203,25,96,0,0,0,104,2,97,0,97,10,70,63,172,104,47,64,0,0,0,104,2,97,1,97,10, + 70,63,161,242,193,64,0,0,0,104,2,97,2,97,10,70,63,175,208,241,192,0,0,0,104,2, + 97,3,97,10,70,191,129,202,161,0,0,0,0,104,2,97,4,97,10,70,63,178,151,55,32,0,0,0, + 104,2,97,5,97,10,70,63,137,155,94,0,0,0,0,104,2,97,0,97,11,70,191,179, + 106,160,0,0,0,0,104,2,97,1,97,11,70,63,184,253,164,96,0,0,0,104,2,97,2,97,11, + 70,191,143,30,157,0,0,0,0,104,2,97,3,97,11,70,63,153,225,140,128,0,0,0,104, + 2,97,4,97,11,70,63,161,35,85,192,0,0,0,104,2,97,5,97,11,70,63,175,200,55,192, + 0,0,0,104,2,97,0,97,12,70,191,180,116,132,96,0,0,0,104,2,97,1,97,12,70,191, + 165,151,152,0,0,0,0,104,2,97,2,97,12,70,191,180,197,91,160,0,0,0,104,2,97,3,97,12, + 70,191,91,30,160,0,0,0,0,104,2,97,4,97,12,70,63,180,251,45,32,0,0,0, + 104,2,97,5,97,12,70,63,165,134,77,64,0,0,0,104,2,97,6,97,14,70,63,181,56,242,96, + 0,0,0,104,2,97,7,97,14,70,191,165,239,234,224,0,0,0,104,2,97,8,97,14, + 70,191,154,65,216,128,0,0,0,104,2,97,9,97,14,70,63,150,250,236,0,0,0,0,104,2,97, + 10,97,14,70,191,141,105,108,0,0,0,0,104,2,97,11,97,14,70,191,152,40, + 165,0,0,0,0,104,2,97,12,97,14,70,63,141,159,46,0,0,0,0,104,2,97,13,97,14,70, + 191,183,172,137,32,0,0,0,104,2,97,6,97,15,70,63,163,26,123,192,0,0,0,104, + 2,97,7,97,15,70,63,176,184,106,32,0,0,0,104,2,97,8,97,15,70,63,152,234,144, + 0,0,0,0,104,2,97,9,97,15,70,191,172,58,70,160,0,0,0,104,2,97,10,97,15,70, + 63,161,211,211,192,0,0,0,104,2,97,11,97,15,70,191,148,171,120,128,0,0,0,104, + 2,97,12,97,15,70,63,180,117,214,224,0,0,0,104,2,97,13,97,15,70,191,104, + 230,216,0,0,0,0,104,2,97,6,97,16,70,63,178,53,103,96,0,0,0,104,2,97,7,97,16, + 70,63,170,230,232,64,0,0,0,104,2,97,8,97,16,70,191,183,45,100,192,0,0,0, + 104,2,97,9,97,16,70,63,184,100,97,32,0,0,0,104,2,97,10,97,16,70,63,169,174, + 254,64,0,0,0,104,2,97,11,97,16,70,191,119,121,234,0,0,0,0,104,2,97,12,97, + 16,70,63,149,12,170,128,0,0,0,104,2,97,13,97,16,70,191,144,193,191,0,0,0,0>>. |