From d79f77985100d2f90a0021f7ebae20ec7c99e93f Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Bj=C3=B6rn-Egil=20Dahlberg?= <egil@erlang.org>
Date: Fri, 5 Jun 2015 16:00:30 +0200
Subject: erts: Fix faulty list optimization in make_internal_hash

Reported-by: Rory Byrne
---
 erts/emulator/beam/utils.c       |  8 +++--
 erts/emulator/test/map_SUITE.erl | 67 ++++++++++++++++++++++++++++++++++++++--
 2 files changed, 70 insertions(+), 5 deletions(-)

diff --git a/erts/emulator/beam/utils.c b/erts/emulator/beam/utils.c
index 965de748c9..cecd88197e 100644
--- a/erts/emulator/beam/utils.c
+++ b/erts/emulator/beam/utils.c
@@ -1140,7 +1140,7 @@ make_hash2(Eterm term)
 
     ERTS_UNDEF(hash_xor_pairs, 0);
 
-/* (HCONST * {2, ..., 16}) mod 2^32 */
+/* (HCONST * {2, ..., 22}) mod 2^32 */
 #define HCONST_2 0x3c6ef372UL
 #define HCONST_3 0xdaa66d2bUL
 #define HCONST_4 0x78dde6e4UL
@@ -1161,6 +1161,7 @@ make_hash2(Eterm term)
 #define HCONST_19 0xbe1e08bbUL
 #define HCONST_20 0x5c558274UL
 #define HCONST_21 0xfa8cfc2dUL
+#define HCONST_22 0x98c475e6UL
 
 #define HASH_MAP_TAIL (_make_header(1,_TAG_HEADER_REF))
 #define HASH_MAP_PAIR (_make_header(2,_TAG_HEADER_REF))
@@ -1645,8 +1646,9 @@ make_internal_hash(Eterm term)
 		    break;
 		ptr = list_val(term);
 	    }
-	    if (c > 0)
-		UINT32_HASH(sh, HCONST_4);
+            if (c > 0)
+                UINT32_HASH_2(sh, (Uint32)c, HCONST_22);
+
 	    if (is_list(term)) {
 		tmp = CDR(ptr);
                 CONST_HASH(HCONST_17);  /* Hash CAR in cons cell */
diff --git a/erts/emulator/test/map_SUITE.erl b/erts/emulator/test/map_SUITE.erl
index 527b6987fa..b739250aad 100644
--- a/erts/emulator/test/map_SUITE.erl
+++ b/erts/emulator/test/map_SUITE.erl
@@ -2615,13 +2615,76 @@ t_erts_internal_order(_Config) when is_list(_Config) ->
 t_erts_internal_hash(_Config) when is_list(_Config) ->
     K1 = 0.0,
     K2 = 0.0/-1,
+    M  = maps:from_list([{I,I}||I<-lists:seq(1,32)]),
 
-    M1 = (maps:from_list([{I,I}||I<-lists:seq(1,32)]))#{ K1 => a, K2 => b },
+    M1 = M#{ K1 => a, K2 => b },
     b  = maps:get(K2,M1),
 
-    M2 = (maps:from_list([{I,I}||I<-lists:seq(1,32)]))#{ K2 => a, K1 => b },
+    M2 = M#{ K2 => a, K1 => b },
     b  = maps:get(K1,M2),
 
+    %% test previously faulty hash list optimization
+
+    M3 = M#{[0] => a, [0,0] => b, [0,0,0] => c, [0,0,0,0] => d},
+    a  = maps:get([0],M3),
+    b  = maps:get([0,0],M3),
+    c  = maps:get([0,0,0],M3),
+    d  = maps:get([0,0,0,0],M3),
+
+    M4 = M#{{[0]} => a, {[0,0]} => b, {[0,0,0]} => c, {[0,0,0,0]} => d},
+    a  = maps:get({[0]},M4),
+    b  = maps:get({[0,0]},M4),
+    c  = maps:get({[0,0,0]},M4),
+    d  = maps:get({[0,0,0,0]},M4),
+
+    M5 = M3#{[0,0,0] => e, [0,0,0,0] => f, [0,0,0,0,0] => g,
+             [0,0,0,0,0,0] => h, [0,0,0,0,0,0,0] => i,
+             [0,0,0,0,0,0,0,0] => j, [0,0,0,0,0,0,0,0,0] => k},
+
+    a  = maps:get([0],M5),
+    b  = maps:get([0,0],M5),
+    e  = maps:get([0,0,0],M5),
+    f  = maps:get([0,0,0,0],M5),
+    g  = maps:get([0,0,0,0,0],M5),
+    h  = maps:get([0,0,0,0,0,0],M5),
+    i  = maps:get([0,0,0,0,0,0,0],M5),
+    j  = maps:get([0,0,0,0,0,0,0,0],M5),
+    k  = maps:get([0,0,0,0,0,0,0,0,0],M5),
+
+    M6 = M4#{{[0,0,0]} => e, {[0,0,0,0]} => f, {[0,0,0,0,0]} => g,
+             {[0,0,0,0,0,0]} => h, {[0,0,0,0,0,0,0]} => i,
+             {[0,0,0,0,0,0,0,0]} => j, {[0,0,0,0,0,0,0,0,0]} => k},
+
+    a  = maps:get({[0]},M6),
+    b  = maps:get({[0,0]},M6),
+    e  = maps:get({[0,0,0]},M6),
+    f  = maps:get({[0,0,0,0]},M6),
+    g  = maps:get({[0,0,0,0,0]},M6),
+    h  = maps:get({[0,0,0,0,0,0]},M6),
+    i  = maps:get({[0,0,0,0,0,0,0]},M6),
+    j  = maps:get({[0,0,0,0,0,0,0,0]},M6),
+    k  = maps:get({[0,0,0,0,0,0,0,0,0]},M6),
+
+    M7 = maps:merge(M5,M6),
+
+    a  = maps:get([0],M7),
+    b  = maps:get([0,0],M7),
+    e  = maps:get([0,0,0],M7),
+    f  = maps:get([0,0,0,0],M7),
+    g  = maps:get([0,0,0,0,0],M7),
+    h  = maps:get([0,0,0,0,0,0],M7),
+    i  = maps:get([0,0,0,0,0,0,0],M7),
+    j  = maps:get([0,0,0,0,0,0,0,0],M7),
+    k  = maps:get([0,0,0,0,0,0,0,0,0],M7),
+    a  = maps:get({[0]},M7),
+    b  = maps:get({[0,0]},M7),
+    e  = maps:get({[0,0,0]},M7),
+    f  = maps:get({[0,0,0,0]},M7),
+    g  = maps:get({[0,0,0,0,0]},M7),
+    h  = maps:get({[0,0,0,0,0,0]},M7),
+    i  = maps:get({[0,0,0,0,0,0,0]},M7),
+    j  = maps:get({[0,0,0,0,0,0,0,0]},M7),
+    k  = maps:get({[0,0,0,0,0,0,0,0,0]},M7),
     ok.
 
 t_pdict(_Config) ->
-- 
cgit v1.2.3