aboutsummaryrefslogtreecommitdiffstats
path: root/erts/emulator
diff options
context:
space:
mode:
authorBjörn-Egil Dahlberg <[email protected]>2015-04-10 15:52:11 +0200
committerBjörn-Egil Dahlberg <[email protected]>2015-04-10 15:52:11 +0200
commitc3b50fc66fced021b0886163b9c7aeb7ce5f20c0 (patch)
tree3385486a3762d6f45af3ccfc87b5da069a14f834 /erts/emulator
parent42b1ee09491706cd255f8c146e07c1cb2cd939cc (diff)
parent30ed5b1cc6aa0efe6ac099b66d33d46c7c0c6b47 (diff)
downloadotp-c3b50fc66fced021b0886163b9c7aeb7ce5f20c0.tar.gz
otp-c3b50fc66fced021b0886163b9c7aeb7ce5f20c0.tar.bz2
otp-c3b50fc66fced021b0886163b9c7aeb7ce5f20c0.zip
Merge branch 'egil/fix-maps-deep-colliding-merge'
* egil/fix-maps-deep-colliding-merge: erts: Fix deep colliding hash values in maps:from_list/1
Diffstat (limited to 'erts/emulator')
-rw-r--r--erts/emulator/beam/erl_map.c30
-rw-r--r--erts/emulator/test/map_SUITE.erl10
2 files changed, 38 insertions, 2 deletions
diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c
index d1df737723..98023bbb47 100644
--- a/erts/emulator/beam/erl_map.c
+++ b/erts/emulator/beam/erl_map.c
@@ -679,7 +679,35 @@ static Eterm hashmap_from_chunked_array(ErtsHeapFactory *factory, hxnode_t *hxns
DECLARE_ESTACK(stack);
Eterm res = NIL, *hp = NULL, *nhp;
- ASSERT(n > 1);
+
+ /* if we get here with only one element then
+ * we have eight levels of collisions
+ */
+
+ if (n == 1) {
+ res = hxns[0].val;
+ v = hxns[0].hx;
+ for (d = 7; d > 0; d--) {
+ slot = maskval(v,d);
+ hp = erts_produce_heap(factory, HAMT_NODE_BITMAP_SZ(1), HALLOC_EXTRA);
+ hp[0] = MAP_HEADER_HAMT_NODE_BITMAP(1 << slot);
+ hp[1] = res;
+ res = make_hashmap(hp);
+ }
+
+ slot = maskval(v,0);
+ hp = erts_produce_heap(factory, (is_root ? 3 : 2), 0);
+
+ if (is_root) {
+ hp[0] = MAP_HEADER_HAMT_HEAD_BITMAP(1 << slot);
+ hp[1] = size;
+ hp[2] = res;
+ } else {
+ hp[0] = MAP_HEADER_HAMT_NODE_BITMAP(1 << slot);
+ hp[1] = res;
+ }
+ return make_hashmap(hp);
+ }
/* push initial nodes on the stack,
* this is the starting depth */
diff --git a/erts/emulator/test/map_SUITE.erl b/erts/emulator/test/map_SUITE.erl
index dc6286fdb6..f061b177c5 100644
--- a/erts/emulator/test/map_SUITE.erl
+++ b/erts/emulator/test/map_SUITE.erl
@@ -1888,11 +1888,19 @@ t_bif_map_merge(Config) when is_list(Config) ->
M8 = maps:merge(M7,M8),
M8 = maps:merge(M8,M8),
+ %% maps:merge/2 and mixed
+
+ Ks1 = [764492191,2361333849], %% deep collision
+ Ks2 = lists:seq(1,33),
+ M9 = maps:from_list([{K,K}||K <- Ks1]),
+ M10 = maps:from_list([{K,K}||K <- Ks2]),
+ M11 = maps:merge(M9,M10),
+ ok = check_keys_exist(Ks1 ++ Ks2, M11),
+
%% error case
{'EXIT',{badarg,[{maps,merge,_,_}|_]}} = (catch maps:merge((1 bsl 65 + 3), <<>>)),
{'EXIT',{badarg,[{maps,merge,_,_}|_]}} = (catch maps:merge(<<>>, id(#{ a => 1}))),
{'EXIT',{badarg,[{maps,merge,_,_}|_]}} = (catch maps:merge(id(#{ a => 2}), <<>> )),
-
ok.