From dbad08513df1ea3f3de47375a50d16551df6f208 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn-Egil=20Dahlberg?= Date: Tue, 31 Mar 2015 14:49:02 +0200 Subject: erts: Fix size bug in maps:from_list/1 BIF The wrong size was imprinted on maps with deep hash key collisions. --- erts/emulator/beam/erl_map.c | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-) diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index ab40f47919..a8e8ad346b 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -89,7 +89,7 @@ static Eterm flatmap_from_validated_list(Process *p, Eterm list, Uint size); static Eterm hashmap_from_validated_list(Process *p, Eterm list, Uint size); static Eterm hashmap_from_unsorted_array(ErtsHeapFactory*, hxnode_t *hxns, Uint n, int reject_dupkeys); static Eterm hashmap_from_sorted_unique_array(ErtsHeapFactory*, hxnode_t *hxns, Uint n, int is_root); -static Eterm hashmap_from_chunked_array(ErtsHeapFactory*, hxnode_t *hxns, Uint n, int is_root); +static Eterm hashmap_from_chunked_array(ErtsHeapFactory*, hxnode_t *hxns, Uint n, Uint size, int is_root); static Eterm hashmap_info(Process *p, Eterm node); static Eterm hashmap_bld_tuple_uint(Uint **hpp, Uint *szp, Uint n, Uint nums[]); static int hxnodecmp(hxnode_t* a, hxnode_t* b); @@ -661,7 +661,7 @@ static Eterm hashmap_from_sorted_unique_array(ErtsHeapFactory* factory, ix++; } - res = hashmap_from_chunked_array(factory, hxns, elems, !lvl); + res = hashmap_from_chunked_array(factory, hxns, elems, n, !lvl); ERTS_FACTORY_HOLE_CHECK(factory); @@ -669,8 +669,8 @@ static Eterm hashmap_from_sorted_unique_array(ErtsHeapFactory* factory, } #define HALLOC_EXTRA 200 -static Eterm hashmap_from_chunked_array(ErtsHeapFactory *factory, - hxnode_t *hxns, Uint n, int is_root) { +static Eterm hashmap_from_chunked_array(ErtsHeapFactory *factory, hxnode_t *hxns, Uint n, + Uint size, int is_root) { Uint ix, d, dn, dc, slot, elems; Uint32 v, vp, vn, hdr; Uint bp, sz; @@ -840,7 +840,7 @@ static Eterm hashmap_from_chunked_array(ErtsHeapFactory *factory, if (is_root) { *hp++ = (hdr == 0xffff) ? MAP_HEADER_HAMT_HEAD_ARRAY : MAP_HEADER_HAMT_HEAD_BITMAP(hdr); - *hp++ = n; + *hp++ = size; } else { *hp++ = MAP_HEADER_HAMT_NODE_BITMAP(hdr); } -- cgit v1.2.3 From 2fc541ea6ecaf7dd8d98071ef82332fe67adfbef Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn-Egil=20Dahlberg?= Date: Tue, 31 Mar 2015 15:08:40 +0200 Subject: erts: Try to test deep Maps collision Ensure maps:size/1 is correct. --- erts/emulator/test/map_SUITE.erl | 11 +++++++++++ 1 file changed, 11 insertions(+) diff --git a/erts/emulator/test/map_SUITE.erl b/erts/emulator/test/map_SUITE.erl index a72c8dafe4..c7800a5540 100644 --- a/erts/emulator/test/map_SUITE.erl +++ b/erts/emulator/test/map_SUITE.erl @@ -644,6 +644,17 @@ t_map_size(Config) when is_list(Config) -> Ks = [build_key(fun(K) -> <<1,K:32,1>> end,I)||I<-lists:seq(1,100)], ok = build_and_check_size(Ks,0,#{}), + %% try deep collisions + %% statistically we get another subtree at 50k -> 100k elements + %% Try to be nice and don't use too much memory in the testcase, + + N = 500000, + Is = lists:seq(1,N), + N = map_size(maps:from_list([{I,I}||I<-Is])), + N = map_size(maps:from_list([{<>,I}||I<-Is])), + N = map_size(maps:from_list([{integer_to_list(I),I}||I<-Is])), + N = map_size(maps:from_list([{float(I),I}||I<-Is])), + %% Error cases. {'EXIT',{badarg,_}} = (catch map_size([])), {'EXIT',{badarg,_}} = (catch map_size(<<1,2,3>>)), -- cgit v1.2.3 From ca94abe66652fb07c435ac7f690e447d6038c474 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn-Egil=20Dahlberg?= Date: Tue, 31 Mar 2015 15:32:58 +0200 Subject: erts: Strengthen Maps merge tests --- erts/emulator/test/map_SUITE.erl | 34 ++++++++++++++++++++++++++++++++++ 1 file changed, 34 insertions(+) diff --git a/erts/emulator/test/map_SUITE.erl b/erts/emulator/test/map_SUITE.erl index c7800a5540..062d5ef7a2 100644 --- a/erts/emulator/test/map_SUITE.erl +++ b/erts/emulator/test/map_SUITE.erl @@ -1654,6 +1654,40 @@ t_bif_map_merge(Config) when is_list(Config) -> #{4 := integer, 18446744073709551629 := wat, float := 3.3, int := 3, {1,2} := "tuple", "hi" := "hello again", <<"key">> := <<"value">>} = maps:merge(M0,M1), + %% try deep collisions + N = 150000, + Is = lists:seq(1,N), + M2 = maps:from_list([{I,I}||I<-Is]), + 150000 = maps:size(M2), + M3 = maps:from_list([{<>,I}||I<-Is]), + 150000 = maps:size(M3), + M4 = maps:merge(M2,M3), + 300000 = maps:size(M4), + M5 = maps:from_list([{integer_to_list(I),I}||I<-Is]), + 150000 = maps:size(M5), + M6 = maps:merge(M4,M5), + 450000 = maps:size(M6), + M7 = maps:from_list([{float(I),I}||I<-Is]), + 150000 = maps:size(M7), + M8 = maps:merge(M7,M6), + 600000 = maps:size(M8), + + #{ 1 := 1, "1" := 1, <<1:32>> := 1 } = M8, + #{ 10 := 10, "10" := 10, <<10:32>> := 10 } = M8, + #{ 100 := 100, "100" := 100, <<100:32>> := 100 } = M8, + #{ 1000 := 1000, "1000" := 1000, <<1000:32>> := 1000 } = M8, + #{ 10000 := 10000, "10000" := 10000, <<10000:32>> := 10000 } = M8, + #{ 100000 := 100000, "100000" := 100000, <<100000:32>> := 100000 } = M8, + + %% overlapping + M8 = maps:merge(M2,M8), + M8 = maps:merge(M3,M8), + M8 = maps:merge(M4,M8), + M8 = maps:merge(M5,M8), + M8 = maps:merge(M6,M8), + M8 = maps:merge(M7,M8), + M8 = maps:merge(M8,M8), + %% error case {'EXIT',{badarg,[{maps,merge,_,_}|_]}} = (catch maps:merge((1 bsl 65 + 3), <<>>)), {'EXIT',{badarg,[{maps,merge,_,_}|_]}} = (catch maps:merge(<<>>, id(#{ a => 1}))), -- cgit v1.2.3