diff options
| author | Björn-Egil Dahlberg <[email protected]> | 2015-04-10 15:52:11 +0200 |
|---|---|---|
| committer | Björn-Egil Dahlberg <[email protected]> | 2015-04-10 15:52:11 +0200 |
| commit | c3b50fc66fced021b0886163b9c7aeb7ce5f20c0 (patch) | |
| tree | 3385486a3762d6f45af3ccfc87b5da069a14f834 | |
| parent | 42b1ee09491706cd255f8c146e07c1cb2cd939cc (diff) | |
| parent | 30ed5b1cc6aa0efe6ac099b66d33d46c7c0c6b47 (diff) | |
| download | otp-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
| -rw-r--r-- | erts/emulator/beam/erl_map.c | 30 | ||||
| -rw-r--r-- | erts/emulator/test/map_SUITE.erl | 10 |
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. |