From 0835f40ae25f97360dc393928796387d3cd6b16e Mon Sep 17 00:00:00 2001 From: Guilherme Andrade Date: Wed, 19 Apr 2017 00:43:37 +0100 Subject: erts: Add enif_phash2 and enif_phash2_ranged These allow one to hash VM terms from NIF code. --- erts/doc/src/erl_nif.xml | 30 ++++++++++ erts/emulator/beam/bif.c | 17 ++---- erts/emulator/beam/erl_nif.c | 20 +++++++ erts/emulator/beam/erl_nif_api_funcs.h | 4 ++ erts/emulator/beam/erl_utils.h | 1 + erts/emulator/beam/utils.c | 10 ++++ erts/emulator/test/nif_SUITE.erl | 85 ++++++++++++++++++++++++++- erts/emulator/test/nif_SUITE_data/nif_SUITE.c | 19 ++++++ 8 files changed, 173 insertions(+), 13 deletions(-) diff --git a/erts/doc/src/erl_nif.xml b/erts/doc/src/erl_nif.xml index 6bb1109415..34dae418ef 100644 --- a/erts/doc/src/erl_nif.xml +++ b/erts/doc/src/erl_nif.xml @@ -2369,6 +2369,36 @@ enif_map_iterator_destroy(env, &iter); + + + unsigned long + enif_phash2(ERL_NIF_TERM term) + + Portable hash function. + +

Portable hash function that gives the same hash for the same Erlang term + regardless of machine architecture and ERTS version. Corresponds to + erlang:phash2/1.

+

Returns an unsigned integer within 0..2^27-1.

+ + + + + + unsigned long + enif_phash2_ranged(ERL_NIF_TERM term, unsigned long range) + + Portable hash function. + +

Similar to enif_phash2 + but hash range can be specified. Corresponds to + erlang:phash2/2.

+

Returns an unsigned integer within 0..range-1 + if 0 < range < 2^32, and within 0..2^32-1 otherwise. +

+ + + intenif_port_command(ErlNifEnv* env, const ErlNifPort* to_port, ErlNifEnv *msg_env, ERL_NIF_TERM msg) diff --git a/erts/emulator/beam/bif.c b/erts/emulator/beam/bif.c index 214de3652f..d59adc18d6 100644 --- a/erts/emulator/beam/bif.c +++ b/erts/emulator/beam/bif.c @@ -4888,7 +4888,6 @@ BIF_RETTYPE phash2_1(BIF_ALIST_1) BIF_RETTYPE phash2_2(BIF_ALIST_2) { Uint32 hash; - Uint32 final_hash; Uint32 range; /* Check for special case 2^32 */ @@ -4901,23 +4900,19 @@ BIF_RETTYPE phash2_2(BIF_ALIST_2) } range = (Uint32) u; } - hash = make_hash2(BIF_ARG_1); - if (range) { - final_hash = hash % range; /* [0..range-1] */ - } else { - final_hash = hash; - } + hash = make_hash2_within_range(BIF_ARG_1, range); + /* * Return either a small or a big. Use the heap for bigs if there is room. */ #if defined(ARCH_64) - BIF_RET(make_small(final_hash)); + BIF_RET(make_small(hash)); #else - if (IS_USMALL(0, final_hash)) { - BIF_RET(make_small(final_hash)); + if (IS_USMALL(0, hash)) { + BIF_RET(make_small(hash)); } else { Eterm* hp = HAlloc(BIF_P, BIG_UINT_HEAP_SIZE); - BIF_RET(uint_to_big(final_hash, hp)); + BIF_RET(uint_to_big(hash, hp)); } #endif } diff --git a/erts/emulator/beam/erl_nif.c b/erts/emulator/beam/erl_nif.c index f86b9739fa..14abf461a3 100644 --- a/erts/emulator/beam/erl_nif.c +++ b/erts/emulator/beam/erl_nif.c @@ -55,6 +55,7 @@ #include "dtrace-wrapper.h" #include "erl_process.h" #include "erl_bif_unique.h" +#include "erl_utils.h" #undef ERTS_WANT_NFUNC_SCHED_INTERNALS__ #define ERTS_WANT_NFUNC_SCHED_INTERNALS__ #include "erl_nfunc_sched.h" @@ -1213,6 +1214,25 @@ int enif_compare(Eterm lhs, Eterm rhs) return result; } +#if SIZEOF_LONG < 4 +/* This *really* shouldn't happen */ +# error Incompatible long word size +#endif + +unsigned long enif_phash2(Eterm term) +{ + return make_hash2(term) & ((1 << 27) - 1); +} + +unsigned long enif_phash2_ranged(Eterm term, unsigned long range) +{ +#if SIZEOF_LONG > 4 + if (range > (unsigned long) UINT32_MAX) + range = 0; +#endif + return make_hash2_within_range(term, range); +} + int enif_get_tuple(ErlNifEnv* env, Eterm tpl, int* arity, const Eterm** array) { Eterm* ptr; diff --git a/erts/emulator/beam/erl_nif_api_funcs.h b/erts/emulator/beam/erl_nif_api_funcs.h index 01d9e386ed..8a3f9165d9 100644 --- a/erts/emulator/beam/erl_nif_api_funcs.h +++ b/erts/emulator/beam/erl_nif_api_funcs.h @@ -47,6 +47,8 @@ ERL_NIF_API_FUNC_DECL(int,enif_get_list_cell,(ErlNifEnv* env, ERL_NIF_TERM term, ERL_NIF_API_FUNC_DECL(int,enif_get_tuple,(ErlNifEnv* env, ERL_NIF_TERM tpl, int* arity, const ERL_NIF_TERM** array)); ERL_NIF_API_FUNC_DECL(int,enif_is_identical,(ERL_NIF_TERM lhs, ERL_NIF_TERM rhs)); ERL_NIF_API_FUNC_DECL(int,enif_compare,(ERL_NIF_TERM lhs, ERL_NIF_TERM rhs)); +ERL_NIF_API_FUNC_DECL(unsigned long,enif_phash2,(ERL_NIF_TERM term)); +ERL_NIF_API_FUNC_DECL(unsigned long,enif_phash2_ranged,(ERL_NIF_TERM term, unsigned long)); ERL_NIF_API_FUNC_DECL(ERL_NIF_TERM,enif_make_binary,(ErlNifEnv* env, ErlNifBinary* bin)); ERL_NIF_API_FUNC_DECL(ERL_NIF_TERM,enif_make_badarg,(ErlNifEnv* env)); ERL_NIF_API_FUNC_DECL(ERL_NIF_TERM,enif_make_int,(ErlNifEnv* env, int i)); @@ -208,6 +210,8 @@ ERL_NIF_API_FUNC_DECL(int, enif_compare_monitors,(const ErlNifMonitor*,const Erl # define enif_get_list_cell ERL_NIF_API_FUNC_MACRO(enif_get_list_cell) # define enif_is_identical ERL_NIF_API_FUNC_MACRO(enif_is_identical) # define enif_compare ERL_NIF_API_FUNC_MACRO(enif_compare) +# define enif_phash2 ERL_NIF_API_FUNC_MACRO(enif_phash2) +# define enif_phash2_ranged ERL_NIF_API_FUNC_MACRO(enif_phash2_ranged) # define enif_make_binary ERL_NIF_API_FUNC_MACRO(enif_make_binary) # define enif_make_badarg ERL_NIF_API_FUNC_MACRO(enif_make_badarg) diff --git a/erts/emulator/beam/erl_utils.h b/erts/emulator/beam/erl_utils.h index 47289a0af1..75578c26d6 100644 --- a/erts/emulator/beam/erl_utils.h +++ b/erts/emulator/beam/erl_utils.h @@ -119,6 +119,7 @@ Sint erts_list_length(Eterm); int erts_is_builtin(Eterm, Eterm, int); Uint32 block_hash(byte *, unsigned, Uint32); Uint32 make_hash2(Eterm); +Uint32 make_hash2_within_range(Eterm, Uint32); Uint32 make_hash(Eterm); Uint32 make_internal_hash(Eterm); diff --git a/erts/emulator/beam/utils.c b/erts/emulator/beam/utils.c index 8f3f48f38f..72c59b33c6 100644 --- a/erts/emulator/beam/utils.c +++ b/erts/emulator/beam/utils.c @@ -1552,6 +1552,16 @@ make_hash2(Eterm term) } } +Uint32 +make_hash2_within_range(Eterm term, Uint32 range) +{ + Uint32 hash = make_hash2(term); + if (range) + return hash % range; /* [0..range-1] */ + else + return hash; /* Special case: 2**32 */ +} + /* Term hash function for internal use. * * Limitation #1: Is not "portable" in any way between different VM instances. diff --git a/erts/emulator/test/nif_SUITE.erl b/erts/emulator/test/nif_SUITE.erl index 693db42e58..780fe0a5ee 100644 --- a/erts/emulator/test/nif_SUITE.erl +++ b/erts/emulator/test/nif_SUITE.erl @@ -56,7 +56,9 @@ nif_is_process_alive/1, nif_is_port_alive/1, nif_term_to_binary/1, nif_binary_to_term/1, nif_port_command/1, - nif_snprintf/1 + nif_snprintf/1, + nif_phash2/1, + nif_phash2_ranged/1 ]). -export([many_args_100/100]). @@ -90,7 +92,9 @@ all() -> nif_is_process_alive, nif_is_port_alive, nif_term_to_binary, nif_binary_to_term, nif_port_command, - nif_snprintf]. + nif_snprintf, + nif_phash2, + nif_phash2_ranged]. groups() -> [{G, [], api_repeaters()} || G <- api_groups()] @@ -2610,6 +2614,81 @@ nif_snprintf(Config) -> <<"{{hello,world,-33},",0>> = format_term_nif(20,{{hello,world, -33}, 3.14, self()}), ok. +nif_phash2(Config) -> + ensure_lib_loaded(Config), + Terms = + [random_term() || _ <- lists:seq(1, 1000)], + + lists:foreach( + fun (Term) -> + HashValue = erlang:phash2(Term), + NifHashValue = phash2_nif(Term), + (HashValue =:= NifHashValue + orelse ct:fail("Expected: ~p\nActual: ~p", + [HashValue, NifHashValue])) + end, + Terms). + +nif_phash2_ranged(Config) -> + ensure_lib_loaded(Config), + RandomRangedTerms = + [{random_term(), rand:uniform((1 bsl 32) - 1)} + || _ <- lists:seq(1, 1000)], + + lists:foreach( + fun ({Term, Range}) -> + HashValue = erlang:phash2(Term, Range), + NifHashValue = phash2_ranged_nif(Term, Range), + (HashValue =:= NifHashValue + orelse ct:fail("Expected: ~p\nActual: ~p", + [HashValue, NifHashValue])) + end, + RandomRangedTerms), + + EdgeCaseTerm = random_term(), + EdgeCaseHashValue = erlang:phash2(EdgeCaseTerm, 1 bsl 32), + EdgeCaseNifHashValue = phash2_ranged_nif(EdgeCaseTerm, 0), + (EdgeCaseHashValue =:= EdgeCaseNifHashValue + orelse ct:fail("Expected: ~p\nActual: ~p", + [EdgeCaseHashValue, EdgeCaseNifHashValue])). + +-define(HALF_DBL_EPSILON, 1.1102230246251565e-16). % math:pow(2, -53) + +random_term() -> + case rand:uniform(6) of + 1 -> rand:uniform(1 bsl 27) - 1; % small + 2 -> (1 bsl 27) + rand:uniform(1 bsl 128); % big + 3 -> random_sign() * (rand:uniform() * ?HALF_DBL_EPSILON); % float + 4 -> random_binary(); + 5 -> random_pid(); + 6 -> + Length = rand:uniform(10), + List = [random_term() || _ <- lists:seq(1, Length)], + case rand:uniform(2) of + 1 -> + List; + 2 -> + list_to_tuple(List) + end + end. + +random_sign() -> + case rand:uniform(2) of + 1 -> -1.0; + 2 -> 1.0 + end. + +random_binary() -> + list_to_binary(random_bytes(rand:uniform(32) - 1)). + +random_bytes(0) -> + []; +random_bytes(N) when N > 0 -> + [rand:uniform(256) - 1 | random_bytes(N - 1)]. + +random_pid() -> + Processes = erlang:processes(), + lists:nth(rand:uniform(length(Processes)), Processes). %% The NIFs: lib_version() -> undefined. @@ -2621,6 +2700,8 @@ type_test() -> ?nif_stub. tuple_2_list(_) -> ?nif_stub. is_identical(_,_) -> ?nif_stub. compare(_,_) -> ?nif_stub. +phash2_nif(_) -> ?nif_stub. +phash2_ranged_nif(_, _) -> ?nif_stub. many_args_100(_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_) -> ?nif_stub. clone_bin(_) -> ?nif_stub. make_sub_bin(_,_,_) -> ?nif_stub. diff --git a/erts/emulator/test/nif_SUITE_data/nif_SUITE.c b/erts/emulator/test/nif_SUITE_data/nif_SUITE.c index 8fe5ee809a..3bdd4d93c7 100644 --- a/erts/emulator/test/nif_SUITE_data/nif_SUITE.c +++ b/erts/emulator/test/nif_SUITE_data/nif_SUITE.c @@ -687,6 +687,23 @@ static ERL_NIF_TERM compare(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[]) return enif_make_int(env, enif_compare(argv[0],argv[1])); } +static ERL_NIF_TERM phash2_nif(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[]) +{ + if (argc != 1) { + return enif_make_badarg(env); + } + return enif_make_ulong(env, enif_phash2(argv[0])); +} + +static ERL_NIF_TERM phash2_ranged_nif(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[]) +{ + unsigned long range; + if (argc != 2 || !enif_get_ulong(env, argv[1], &range)) { + return enif_make_badarg(env); + } + return enif_make_ulong(env, enif_phash2_ranged(argv[0], range)); +} + static ERL_NIF_TERM many_args_100(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[]) { int i, k; @@ -2864,6 +2881,8 @@ static ErlNifFunc nif_funcs[] = {"tuple_2_list", 1, tuple_2_list}, {"is_identical",2,is_identical}, {"compare",2,compare}, + {"phash2_nif",1,phash2_nif}, + {"phash2_ranged_nif",2,phash2_ranged_nif}, {"many_args_100", 100, many_args_100}, {"clone_bin", 1, clone_bin}, {"make_sub_bin", 3, make_sub_bin}, -- cgit v1.2.3 From 1b37d0b010ea31b04b9d0a15d0bec9c75a013dc9 Mon Sep 17 00:00:00 2001 From: Guilherme Andrade Date: Thu, 20 Apr 2017 21:35:54 +0100 Subject: erts: Remove enif_phash2_ranged --- erts/doc/src/erl_nif.xml | 16 -------------- erts/emulator/beam/bif.c | 17 +++++++++------ erts/emulator/beam/erl_nif.c | 14 ++----------- erts/emulator/beam/erl_nif_api_funcs.h | 2 -- erts/emulator/beam/erl_utils.h | 1 - erts/emulator/beam/utils.c | 10 --------- erts/emulator/test/nif_SUITE.erl | 30 ++------------------------- erts/emulator/test/nif_SUITE_data/nif_SUITE.c | 10 --------- 8 files changed, 15 insertions(+), 85 deletions(-) diff --git a/erts/doc/src/erl_nif.xml b/erts/doc/src/erl_nif.xml index 34dae418ef..35c42ac517 100644 --- a/erts/doc/src/erl_nif.xml +++ b/erts/doc/src/erl_nif.xml @@ -2383,22 +2383,6 @@ enif_map_iterator_destroy(env, &iter); - - - unsigned long - enif_phash2_ranged(ERL_NIF_TERM term, unsigned long range) - - Portable hash function. - -

Similar to enif_phash2 - but hash range can be specified. Corresponds to - erlang:phash2/2.

-

Returns an unsigned integer within 0..range-1 - if 0 < range < 2^32, and within 0..2^32-1 otherwise. -

- - - intenif_port_command(ErlNifEnv* env, const ErlNifPort* to_port, ErlNifEnv *msg_env, ERL_NIF_TERM msg) diff --git a/erts/emulator/beam/bif.c b/erts/emulator/beam/bif.c index d59adc18d6..214de3652f 100644 --- a/erts/emulator/beam/bif.c +++ b/erts/emulator/beam/bif.c @@ -4888,6 +4888,7 @@ BIF_RETTYPE phash2_1(BIF_ALIST_1) BIF_RETTYPE phash2_2(BIF_ALIST_2) { Uint32 hash; + Uint32 final_hash; Uint32 range; /* Check for special case 2^32 */ @@ -4900,19 +4901,23 @@ BIF_RETTYPE phash2_2(BIF_ALIST_2) } range = (Uint32) u; } - hash = make_hash2_within_range(BIF_ARG_1, range); - + hash = make_hash2(BIF_ARG_1); + if (range) { + final_hash = hash % range; /* [0..range-1] */ + } else { + final_hash = hash; + } /* * Return either a small or a big. Use the heap for bigs if there is room. */ #if defined(ARCH_64) - BIF_RET(make_small(hash)); + BIF_RET(make_small(final_hash)); #else - if (IS_USMALL(0, hash)) { - BIF_RET(make_small(hash)); + if (IS_USMALL(0, final_hash)) { + BIF_RET(make_small(final_hash)); } else { Eterm* hp = HAlloc(BIF_P, BIG_UINT_HEAP_SIZE); - BIF_RET(uint_to_big(hash, hp)); + BIF_RET(uint_to_big(final_hash, hp)); } #endif } diff --git a/erts/emulator/beam/erl_nif.c b/erts/emulator/beam/erl_nif.c index 14abf461a3..f7777c8b92 100644 --- a/erts/emulator/beam/erl_nif.c +++ b/erts/emulator/beam/erl_nif.c @@ -1214,25 +1214,15 @@ int enif_compare(Eterm lhs, Eterm rhs) return result; } +unsigned long enif_phash2(Eterm term) +{ #if SIZEOF_LONG < 4 /* This *really* shouldn't happen */ # error Incompatible long word size #endif - -unsigned long enif_phash2(Eterm term) -{ return make_hash2(term) & ((1 << 27) - 1); } -unsigned long enif_phash2_ranged(Eterm term, unsigned long range) -{ -#if SIZEOF_LONG > 4 - if (range > (unsigned long) UINT32_MAX) - range = 0; -#endif - return make_hash2_within_range(term, range); -} - int enif_get_tuple(ErlNifEnv* env, Eterm tpl, int* arity, const Eterm** array) { Eterm* ptr; diff --git a/erts/emulator/beam/erl_nif_api_funcs.h b/erts/emulator/beam/erl_nif_api_funcs.h index 8a3f9165d9..c096b18f91 100644 --- a/erts/emulator/beam/erl_nif_api_funcs.h +++ b/erts/emulator/beam/erl_nif_api_funcs.h @@ -48,7 +48,6 @@ ERL_NIF_API_FUNC_DECL(int,enif_get_tuple,(ErlNifEnv* env, ERL_NIF_TERM tpl, int* ERL_NIF_API_FUNC_DECL(int,enif_is_identical,(ERL_NIF_TERM lhs, ERL_NIF_TERM rhs)); ERL_NIF_API_FUNC_DECL(int,enif_compare,(ERL_NIF_TERM lhs, ERL_NIF_TERM rhs)); ERL_NIF_API_FUNC_DECL(unsigned long,enif_phash2,(ERL_NIF_TERM term)); -ERL_NIF_API_FUNC_DECL(unsigned long,enif_phash2_ranged,(ERL_NIF_TERM term, unsigned long)); ERL_NIF_API_FUNC_DECL(ERL_NIF_TERM,enif_make_binary,(ErlNifEnv* env, ErlNifBinary* bin)); ERL_NIF_API_FUNC_DECL(ERL_NIF_TERM,enif_make_badarg,(ErlNifEnv* env)); ERL_NIF_API_FUNC_DECL(ERL_NIF_TERM,enif_make_int,(ErlNifEnv* env, int i)); @@ -211,7 +210,6 @@ ERL_NIF_API_FUNC_DECL(int, enif_compare_monitors,(const ErlNifMonitor*,const Erl # define enif_is_identical ERL_NIF_API_FUNC_MACRO(enif_is_identical) # define enif_compare ERL_NIF_API_FUNC_MACRO(enif_compare) # define enif_phash2 ERL_NIF_API_FUNC_MACRO(enif_phash2) -# define enif_phash2_ranged ERL_NIF_API_FUNC_MACRO(enif_phash2_ranged) # define enif_make_binary ERL_NIF_API_FUNC_MACRO(enif_make_binary) # define enif_make_badarg ERL_NIF_API_FUNC_MACRO(enif_make_badarg) diff --git a/erts/emulator/beam/erl_utils.h b/erts/emulator/beam/erl_utils.h index 75578c26d6..47289a0af1 100644 --- a/erts/emulator/beam/erl_utils.h +++ b/erts/emulator/beam/erl_utils.h @@ -119,7 +119,6 @@ Sint erts_list_length(Eterm); int erts_is_builtin(Eterm, Eterm, int); Uint32 block_hash(byte *, unsigned, Uint32); Uint32 make_hash2(Eterm); -Uint32 make_hash2_within_range(Eterm, Uint32); Uint32 make_hash(Eterm); Uint32 make_internal_hash(Eterm); diff --git a/erts/emulator/beam/utils.c b/erts/emulator/beam/utils.c index 72c59b33c6..8f3f48f38f 100644 --- a/erts/emulator/beam/utils.c +++ b/erts/emulator/beam/utils.c @@ -1552,16 +1552,6 @@ make_hash2(Eterm term) } } -Uint32 -make_hash2_within_range(Eterm term, Uint32 range) -{ - Uint32 hash = make_hash2(term); - if (range) - return hash % range; /* [0..range-1] */ - else - return hash; /* Special case: 2**32 */ -} - /* Term hash function for internal use. * * Limitation #1: Is not "portable" in any way between different VM instances. diff --git a/erts/emulator/test/nif_SUITE.erl b/erts/emulator/test/nif_SUITE.erl index 780fe0a5ee..f868b018c9 100644 --- a/erts/emulator/test/nif_SUITE.erl +++ b/erts/emulator/test/nif_SUITE.erl @@ -57,8 +57,7 @@ nif_term_to_binary/1, nif_binary_to_term/1, nif_port_command/1, nif_snprintf/1, - nif_phash2/1, - nif_phash2_ranged/1 + nif_phash2/1 ]). -export([many_args_100/100]). @@ -93,8 +92,7 @@ all() -> nif_term_to_binary, nif_binary_to_term, nif_port_command, nif_snprintf, - nif_phash2, - nif_phash2_ranged]. + nif_phash2]. groups() -> [{G, [], api_repeaters()} || G <- api_groups()] @@ -2629,29 +2627,6 @@ nif_phash2(Config) -> end, Terms). -nif_phash2_ranged(Config) -> - ensure_lib_loaded(Config), - RandomRangedTerms = - [{random_term(), rand:uniform((1 bsl 32) - 1)} - || _ <- lists:seq(1, 1000)], - - lists:foreach( - fun ({Term, Range}) -> - HashValue = erlang:phash2(Term, Range), - NifHashValue = phash2_ranged_nif(Term, Range), - (HashValue =:= NifHashValue - orelse ct:fail("Expected: ~p\nActual: ~p", - [HashValue, NifHashValue])) - end, - RandomRangedTerms), - - EdgeCaseTerm = random_term(), - EdgeCaseHashValue = erlang:phash2(EdgeCaseTerm, 1 bsl 32), - EdgeCaseNifHashValue = phash2_ranged_nif(EdgeCaseTerm, 0), - (EdgeCaseHashValue =:= EdgeCaseNifHashValue - orelse ct:fail("Expected: ~p\nActual: ~p", - [EdgeCaseHashValue, EdgeCaseNifHashValue])). - -define(HALF_DBL_EPSILON, 1.1102230246251565e-16). % math:pow(2, -53) random_term() -> @@ -2701,7 +2676,6 @@ tuple_2_list(_) -> ?nif_stub. is_identical(_,_) -> ?nif_stub. compare(_,_) -> ?nif_stub. phash2_nif(_) -> ?nif_stub. -phash2_ranged_nif(_, _) -> ?nif_stub. many_args_100(_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_) -> ?nif_stub. clone_bin(_) -> ?nif_stub. make_sub_bin(_,_,_) -> ?nif_stub. diff --git a/erts/emulator/test/nif_SUITE_data/nif_SUITE.c b/erts/emulator/test/nif_SUITE_data/nif_SUITE.c index 3bdd4d93c7..dac6d02e9d 100644 --- a/erts/emulator/test/nif_SUITE_data/nif_SUITE.c +++ b/erts/emulator/test/nif_SUITE_data/nif_SUITE.c @@ -695,15 +695,6 @@ static ERL_NIF_TERM phash2_nif(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv return enif_make_ulong(env, enif_phash2(argv[0])); } -static ERL_NIF_TERM phash2_ranged_nif(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[]) -{ - unsigned long range; - if (argc != 2 || !enif_get_ulong(env, argv[1], &range)) { - return enif_make_badarg(env); - } - return enif_make_ulong(env, enif_phash2_ranged(argv[0], range)); -} - static ERL_NIF_TERM many_args_100(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[]) { int i, k; @@ -2882,7 +2873,6 @@ static ErlNifFunc nif_funcs[] = {"is_identical",2,is_identical}, {"compare",2,compare}, {"phash2_nif",1,phash2_nif}, - {"phash2_ranged_nif",2,phash2_ranged_nif}, {"many_args_100", 100, many_args_100}, {"clone_bin", 1, clone_bin}, {"make_sub_bin", 3, make_sub_bin}, -- cgit v1.2.3 From 5ad95cca3f3c6802cd71fdd35dd397c3a37dc239 Mon Sep 17 00:00:00 2001 From: Guilherme Andrade Date: Thu, 20 Apr 2017 21:53:54 +0100 Subject: erts: Fix random floats in enif_phash2 tests --- erts/emulator/test/nif_SUITE.erl | 4 +--- 1 file changed, 1 insertion(+), 3 deletions(-) diff --git a/erts/emulator/test/nif_SUITE.erl b/erts/emulator/test/nif_SUITE.erl index f868b018c9..9127a5eae9 100644 --- a/erts/emulator/test/nif_SUITE.erl +++ b/erts/emulator/test/nif_SUITE.erl @@ -2627,13 +2627,11 @@ nif_phash2(Config) -> end, Terms). --define(HALF_DBL_EPSILON, 1.1102230246251565e-16). % math:pow(2, -53) - random_term() -> case rand:uniform(6) of 1 -> rand:uniform(1 bsl 27) - 1; % small 2 -> (1 bsl 27) + rand:uniform(1 bsl 128); % big - 3 -> random_sign() * (rand:uniform() * ?HALF_DBL_EPSILON); % float + 3 -> random_sign() * (rand:uniform() * (1 bsl 53)); % float 4 -> random_binary(); 5 -> random_pid(); 6 -> -- cgit v1.2.3 From d8756f8665a42effa2f3515369058cff4441abeb Mon Sep 17 00:00:00 2001 From: Guilherme Andrade Date: Thu, 20 Apr 2017 22:44:04 +0100 Subject: erts: Refactor enif_phash2 into enif_hash A more generic hashing function which can also hash terms based on `make_internal_hash'. --- erts/doc/src/erl_nif.xml | 49 +++++++++++++++++++-------- erts/emulator/beam/erl_nif.c | 11 ++++-- erts/emulator/beam/erl_nif.h | 5 +++ erts/emulator/beam/erl_nif_api_funcs.h | 4 +-- erts/emulator/test/nif_SUITE.erl | 47 +++++++++++++++++++++++-- erts/emulator/test/nif_SUITE_data/nif_SUITE.c | 20 ++++++++--- 6 files changed, 111 insertions(+), 25 deletions(-) diff --git a/erts/doc/src/erl_nif.xml b/erts/doc/src/erl_nif.xml index 35c42ac517..53b6fdeaa1 100644 --- a/erts/doc/src/erl_nif.xml +++ b/erts/doc/src/erl_nif.xml @@ -813,6 +813,28 @@ typedef enum { + ErlNifHash + +

An enumeration of the supported hash types that can be generated + using enif_hash. +

+ + ERL_NIF_INTERNAL_HASH + +

Non-portable hash function that gives different hashes for the same Erlang + term depending on machine architecture and ERTS version.

+

Generated hash values within 0..2^32-1.

+ + ERL_NIF_PHASH2 + +

Portable hash function that gives the same hash for the same Erlang term + regardless of machine architecture and ERTS version. Corresponds to + erlang:phash2/1.

+

Slower than ERL_NIF_INTERNAL_HASH.

+

Generated hash values within 0..2^27-1.

+ + + @@ -1386,6 +1408,19 @@ typedef enum { + + + unsigned long + enif_hash(ErlNifHash type, ERL_NIF_TERM term) + + Hash terms. + +

Hash terms according to the specified + ErlNifHash type.

+

Range of returned value depends on the hash type.

+ + + intenif_inspect_binary(ErlNifEnv* env, ERL_NIF_TERM bin_term, ErlNifBinary* bin) @@ -2369,20 +2404,6 @@ enif_map_iterator_destroy(env, &iter); - - - unsigned long - enif_phash2(ERL_NIF_TERM term) - - Portable hash function. - -

Portable hash function that gives the same hash for the same Erlang term - regardless of machine architecture and ERTS version. Corresponds to - erlang:phash2/1.

-

Returns an unsigned integer within 0..2^27-1.

- - - intenif_port_command(ErlNifEnv* env, const ErlNifPort* to_port, ErlNifEnv *msg_env, ERL_NIF_TERM msg) diff --git a/erts/emulator/beam/erl_nif.c b/erts/emulator/beam/erl_nif.c index f7777c8b92..3470cf3fd5 100644 --- a/erts/emulator/beam/erl_nif.c +++ b/erts/emulator/beam/erl_nif.c @@ -1214,13 +1214,20 @@ int enif_compare(Eterm lhs, Eterm rhs) return result; } -unsigned long enif_phash2(Eterm term) +unsigned long enif_hash(ErlNifHash type, Eterm term) { #if SIZEOF_LONG < 4 /* This *really* shouldn't happen */ # error Incompatible long word size #endif - return make_hash2(term) & ((1 << 27) - 1); + switch (type) { + case ERL_NIF_INTERNAL_HASH: + return make_internal_hash(term); + case ERL_NIF_PHASH2: + return make_hash2(term) & ((1 << 27) - 1); + default: + return 0; + } } int enif_get_tuple(ErlNifEnv* env, Eterm tpl, int* arity, const Eterm** array) diff --git a/erts/emulator/beam/erl_nif.h b/erts/emulator/beam/erl_nif.h index ac45f3ac81..5a81f5fbbb 100644 --- a/erts/emulator/beam/erl_nif.h +++ b/erts/emulator/beam/erl_nif.h @@ -236,6 +236,11 @@ typedef enum { ERL_NIF_BIN2TERM_SAFE = 0x20000000 } ErlNifBinaryToTerm; +typedef enum { + ERL_NIF_INTERNAL_HASH = 1, + ERL_NIF_PHASH2 = 2 +} ErlNifHash; + /* * Return values from enif_thread_type(). Negative values * reserved for specific types of non-scheduler threads. diff --git a/erts/emulator/beam/erl_nif_api_funcs.h b/erts/emulator/beam/erl_nif_api_funcs.h index c096b18f91..f52c841ed7 100644 --- a/erts/emulator/beam/erl_nif_api_funcs.h +++ b/erts/emulator/beam/erl_nif_api_funcs.h @@ -47,7 +47,7 @@ ERL_NIF_API_FUNC_DECL(int,enif_get_list_cell,(ErlNifEnv* env, ERL_NIF_TERM term, ERL_NIF_API_FUNC_DECL(int,enif_get_tuple,(ErlNifEnv* env, ERL_NIF_TERM tpl, int* arity, const ERL_NIF_TERM** array)); ERL_NIF_API_FUNC_DECL(int,enif_is_identical,(ERL_NIF_TERM lhs, ERL_NIF_TERM rhs)); ERL_NIF_API_FUNC_DECL(int,enif_compare,(ERL_NIF_TERM lhs, ERL_NIF_TERM rhs)); -ERL_NIF_API_FUNC_DECL(unsigned long,enif_phash2,(ERL_NIF_TERM term)); +ERL_NIF_API_FUNC_DECL(unsigned long,enif_hash,(ErlNifHash type, ERL_NIF_TERM term)); ERL_NIF_API_FUNC_DECL(ERL_NIF_TERM,enif_make_binary,(ErlNifEnv* env, ErlNifBinary* bin)); ERL_NIF_API_FUNC_DECL(ERL_NIF_TERM,enif_make_badarg,(ErlNifEnv* env)); ERL_NIF_API_FUNC_DECL(ERL_NIF_TERM,enif_make_int,(ErlNifEnv* env, int i)); @@ -209,7 +209,7 @@ ERL_NIF_API_FUNC_DECL(int, enif_compare_monitors,(const ErlNifMonitor*,const Erl # define enif_get_list_cell ERL_NIF_API_FUNC_MACRO(enif_get_list_cell) # define enif_is_identical ERL_NIF_API_FUNC_MACRO(enif_is_identical) # define enif_compare ERL_NIF_API_FUNC_MACRO(enif_compare) -# define enif_phash2 ERL_NIF_API_FUNC_MACRO(enif_phash2) +# define enif_hash ERL_NIF_API_FUNC_MACRO(enif_hash) # define enif_make_binary ERL_NIF_API_FUNC_MACRO(enif_make_binary) # define enif_make_badarg ERL_NIF_API_FUNC_MACRO(enif_make_badarg) diff --git a/erts/emulator/test/nif_SUITE.erl b/erts/emulator/test/nif_SUITE.erl index 9127a5eae9..e177fa4963 100644 --- a/erts/emulator/test/nif_SUITE.erl +++ b/erts/emulator/test/nif_SUITE.erl @@ -57,6 +57,7 @@ nif_term_to_binary/1, nif_binary_to_term/1, nif_port_command/1, nif_snprintf/1, + nif_internal_hash/1, nif_phash2/1 ]). @@ -92,6 +93,7 @@ all() -> nif_term_to_binary, nif_binary_to_term, nif_port_command, nif_snprintf, + nif_internal_hash, nif_phash2]. groups() -> @@ -2612,15 +2614,54 @@ nif_snprintf(Config) -> <<"{{hello,world,-33},",0>> = format_term_nif(20,{{hello,world, -33}, 3.14, self()}), ok. +nif_internal_hash(Config) -> + ensure_lib_loaded(Config), + Terms = + [random_term() || _ <- lists:seq(1, 5000)], + + % Unlike the phash2 hash, in this case we + % have nothing to compare to, so let's try + % and at least make sure the distribution + % isn't outright wrong, statistical nuances + % aside. + + OnesPerBit = + lists:foldl( + fun (Term, Acc) -> + NifHashValue = hash_nif(internal, Term), + lists:foldl( + fun (BitIndex, AccB) -> + BitValue = (NifHashValue band (1 bsl BitIndex)) bsr BitIndex, + dict:update_counter(BitIndex, BitValue, AccB) + end, + Acc, + lists:seq(0, 31)) + end, + dict:new(), + Terms), + + ExpectedNrOfOnes = length(Terms) div 2, + dict:fold( + fun (BitIndex, NrOfOnes, Acc) -> + RelativeDeviation = abs(NrOfOnes - ExpectedNrOfOnes) / ExpectedNrOfOnes, + (RelativeDeviation < 0.10 + orelse ct:fail("Unreasonable deviation on number of set bits (i=~p): " + "expected ~p, got ~p (relative dev. ~.3f)", + [BitIndex, ExpectedNrOfOnes, NrOfOnes, RelativeDeviation])), + Acc + end, + ok, + OnesPerBit). + nif_phash2(Config) -> ensure_lib_loaded(Config), Terms = - [random_term() || _ <- lists:seq(1, 1000)], + [random_term() || _ <- lists:seq(1, 5000)], lists:foreach( fun (Term) -> HashValue = erlang:phash2(Term), - NifHashValue = phash2_nif(Term), + NifHashValue = hash_nif(phash2, Term), (HashValue =:= NifHashValue orelse ct:fail("Expected: ~p\nActual: ~p", [HashValue, NifHashValue])) @@ -2673,7 +2714,7 @@ type_test() -> ?nif_stub. tuple_2_list(_) -> ?nif_stub. is_identical(_,_) -> ?nif_stub. compare(_,_) -> ?nif_stub. -phash2_nif(_) -> ?nif_stub. +hash_nif(_, _) -> ?nif_stub. many_args_100(_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_) -> ?nif_stub. clone_bin(_) -> ?nif_stub. make_sub_bin(_,_,_) -> ?nif_stub. diff --git a/erts/emulator/test/nif_SUITE_data/nif_SUITE.c b/erts/emulator/test/nif_SUITE_data/nif_SUITE.c index dac6d02e9d..9d65b9c09b 100644 --- a/erts/emulator/test/nif_SUITE_data/nif_SUITE.c +++ b/erts/emulator/test/nif_SUITE_data/nif_SUITE.c @@ -687,12 +687,24 @@ static ERL_NIF_TERM compare(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[]) return enif_make_int(env, enif_compare(argv[0],argv[1])); } -static ERL_NIF_TERM phash2_nif(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[]) +static ERL_NIF_TERM hash_nif(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[]) { - if (argc != 1) { + if (argc != 2) { + return enif_make_badarg(env); + } + + ErlNifHash type; + if (enif_is_identical(argv[0], enif_make_atom(env, "internal"))) { + type = ERL_NIF_INTERNAL_HASH; + } + else if (enif_is_identical(argv[0], enif_make_atom(env, "phash2"))) { + type = ERL_NIF_PHASH2; + } + else { return enif_make_badarg(env); } - return enif_make_ulong(env, enif_phash2(argv[0])); + + return enif_make_ulong(env, enif_hash(type, argv[1])); } static ERL_NIF_TERM many_args_100(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[]) @@ -2872,7 +2884,7 @@ static ErlNifFunc nif_funcs[] = {"tuple_2_list", 1, tuple_2_list}, {"is_identical",2,is_identical}, {"compare",2,compare}, - {"phash2_nif",1,phash2_nif}, + {"hash_nif",2,hash_nif}, {"many_args_100", 100, many_args_100}, {"clone_bin", 1, clone_bin}, {"make_sub_bin", 3, make_sub_bin}, -- cgit v1.2.3 From 21e1d879faaae2278a68200fe1085d7e73791fa0 Mon Sep 17 00:00:00 2001 From: Guilherme Andrade Date: Sat, 22 Apr 2017 17:22:32 +0100 Subject: erts: Support custom salt in enif_hash --- erts/doc/src/erl_nif.xml | 19 ++++++++----- erts/emulator/beam/bif.c | 4 +-- erts/emulator/beam/erl_bif_info.c | 2 +- erts/emulator/beam/erl_db_hash.c | 2 +- erts/emulator/beam/erl_map.h | 2 +- erts/emulator/beam/erl_nif.c | 6 ++-- erts/emulator/beam/erl_nif_api_funcs.h | 2 +- erts/emulator/beam/erl_process_dict.c | 2 +- erts/emulator/beam/erl_trace.c | 2 +- erts/emulator/beam/erl_utils.h | 4 +-- erts/emulator/beam/utils.c | 40 +++++++++++++-------------- erts/emulator/hipe/hipe_bif0.c | 2 +- erts/emulator/test/nif_SUITE.erl | 6 ++-- erts/emulator/test/nif_SUITE_data/nif_SUITE.c | 11 ++++++-- 14 files changed, 57 insertions(+), 47 deletions(-) diff --git a/erts/doc/src/erl_nif.xml b/erts/doc/src/erl_nif.xml index 53b6fdeaa1..03c96dd3ca 100644 --- a/erts/doc/src/erl_nif.xml +++ b/erts/doc/src/erl_nif.xml @@ -827,11 +827,13 @@ typedef enum { ERL_NIF_PHASH2 -

Portable hash function that gives the same hash for the same Erlang term - regardless of machine architecture and ERTS version. Corresponds to - erlang:phash2/1.

-

Slower than ERL_NIF_INTERNAL_HASH.

+

Portable hash function that gives the same hash for the + same Erlang term regardless of machine architecture and ERTS version.

Generated hash values within 0..2^27-1.

+

Slower than ERL_NIF_INTERNAL_HASH. + When used with salt=0, + it corresponds to + erlang:phash2/1.

 @@ -1411,12 +1413,15 @@ typedef enum { unsigned long - enif_hash(ErlNifHash type, ERL_NIF_TERM term) + + enif_hash(ErlNifHash type, ERL_NIF_TERM term, unsigned long salt) + Hash terms. -

Hash terms according to the specified - ErlNifHash type.

+

Hash term according to the specified + ErlNifHash type + and using the least significant 32 bits of salt.

Range of returned value depends on the hash type.

 diff --git a/erts/emulator/beam/bif.c b/erts/emulator/beam/bif.c index 214de3652f..7473a8e43f 100644 --- a/erts/emulator/beam/bif.c +++ b/erts/emulator/beam/bif.c @@ -4881,7 +4881,7 @@ BIF_RETTYPE phash2_1(BIF_ALIST_1) { Uint32 hash; - hash = make_hash2(BIF_ARG_1); + hash = make_hash2(BIF_ARG_1, 0); BIF_RET(make_small(hash & ((1L << 27) - 1))); } @@ -4901,7 +4901,7 @@ BIF_RETTYPE phash2_2(BIF_ALIST_2) } range = (Uint32) u; } - hash = make_hash2(BIF_ARG_1); + hash = make_hash2(BIF_ARG_1, 0); if (range) { final_hash = hash % range; /* [0..range-1] */ } else { diff --git a/erts/emulator/beam/erl_bif_info.c b/erts/emulator/beam/erl_bif_info.c index 3a8687dc59..f2863f5d5b 100644 --- a/erts/emulator/beam/erl_bif_info.c +++ b/erts/emulator/beam/erl_bif_info.c @@ -3950,7 +3950,7 @@ BIF_RETTYPE erts_debug_get_internal_state_1(BIF_ALIST_1) BIF_RET(erts_debug_reader_groups_map(BIF_P, (int) groups)); } else if (ERTS_IS_ATOM_STR("internal_hash", tp[1])) { - Uint hash = (Uint) make_internal_hash(tp[2]); + Uint hash = (Uint) make_internal_hash(tp[2], 0); Uint hsz = 0; Eterm* hp; erts_bld_uint(NULL, &hsz, hash); diff --git a/erts/emulator/beam/erl_db_hash.c b/erts/emulator/beam/erl_db_hash.c index 7ab27df00c..07f6da7b6d 100644 --- a/erts/emulator/beam/erl_db_hash.c +++ b/erts/emulator/beam/erl_db_hash.c @@ -189,7 +189,7 @@ static ERTS_INLINE int add_fixed_deletion(DbTableHash* tb, int ix, /* optimised version of make_hash (normal case? atomic key) */ #define MAKE_HASH(term) \ ((is_atom(term) ? (atom_tab(atom_val(term))->slot.bucket.hvalue) : \ - make_internal_hash(term)) % MAX_HASH) + make_internal_hash(term, 0)) % MAX_HASH) #ifdef ERTS_SMP # define DB_HASH_LOCK_MASK (DB_HASH_LOCK_CNT-1) diff --git a/erts/emulator/beam/erl_map.h b/erts/emulator/beam/erl_map.h index 61a841f7f0..f7d0413685 100644 --- a/erts/emulator/beam/erl_map.h +++ b/erts/emulator/beam/erl_map.h @@ -57,7 +57,7 @@ typedef struct flatmap_s { #define hashmap_size(x) (((hashmap_head_t*) hashmap_val(x))->size) -#define hashmap_make_hash(Key) make_internal_hash(Key) +#define hashmap_make_hash(Key) make_internal_hash(Key, 0) #define hashmap_restore_hash(Heap,Lvl,Key) \ (((Lvl) < 8) ? hashmap_make_hash(Key) >> (4*(Lvl)) : hashmap_make_hash(CONS(Heap, make_small((Lvl)>>3), (Key))) >> (4*((Lvl) & 7))) diff --git a/erts/emulator/beam/erl_nif.c b/erts/emulator/beam/erl_nif.c index 3470cf3fd5..bdfb7f3b8e 100644 --- a/erts/emulator/beam/erl_nif.c +++ b/erts/emulator/beam/erl_nif.c @@ -1214,7 +1214,7 @@ int enif_compare(Eterm lhs, Eterm rhs) return result; } -unsigned long enif_hash(ErlNifHash type, Eterm term) +unsigned long enif_hash(ErlNifHash type, Eterm term, unsigned long salt) { #if SIZEOF_LONG < 4 /* This *really* shouldn't happen */ @@ -1222,9 +1222,9 @@ unsigned long enif_hash(ErlNifHash type, Eterm term) #endif switch (type) { case ERL_NIF_INTERNAL_HASH: - return make_internal_hash(term); + return make_internal_hash(term, salt); case ERL_NIF_PHASH2: - return make_hash2(term) & ((1 << 27) - 1); + return make_hash2(term, salt) & ((1 << 27) - 1); default: return 0; } diff --git a/erts/emulator/beam/erl_nif_api_funcs.h b/erts/emulator/beam/erl_nif_api_funcs.h index f52c841ed7..6b9f78d46b 100644 --- a/erts/emulator/beam/erl_nif_api_funcs.h +++ b/erts/emulator/beam/erl_nif_api_funcs.h @@ -47,7 +47,7 @@ ERL_NIF_API_FUNC_DECL(int,enif_get_list_cell,(ErlNifEnv* env, ERL_NIF_TERM term, ERL_NIF_API_FUNC_DECL(int,enif_get_tuple,(ErlNifEnv* env, ERL_NIF_TERM tpl, int* arity, const ERL_NIF_TERM** array)); ERL_NIF_API_FUNC_DECL(int,enif_is_identical,(ERL_NIF_TERM lhs, ERL_NIF_TERM rhs)); ERL_NIF_API_FUNC_DECL(int,enif_compare,(ERL_NIF_TERM lhs, ERL_NIF_TERM rhs)); -ERL_NIF_API_FUNC_DECL(unsigned long,enif_hash,(ErlNifHash type, ERL_NIF_TERM term)); +ERL_NIF_API_FUNC_DECL(unsigned long,enif_hash,(ErlNifHash type, ERL_NIF_TERM term, unsigned long salt)); ERL_NIF_API_FUNC_DECL(ERL_NIF_TERM,enif_make_binary,(ErlNifEnv* env, ErlNifBinary* bin)); ERL_NIF_API_FUNC_DECL(ERL_NIF_TERM,enif_make_badarg,(ErlNifEnv* env)); ERL_NIF_API_FUNC_DECL(ERL_NIF_TERM,enif_make_int,(ErlNifEnv* env, int i)); diff --git a/erts/emulator/beam/erl_process_dict.c b/erts/emulator/beam/erl_process_dict.c index 7cfdf20341..01e240c65d 100644 --- a/erts/emulator/beam/erl_process_dict.c +++ b/erts/emulator/beam/erl_process_dict.c @@ -57,7 +57,7 @@ ((is_small(Term)) ? (Uint32) unsigned_val(Term) : \ ((is_atom(Term)) ? \ (Uint32) atom_val(Term) : \ - make_internal_hash(Term))) + make_internal_hash(Term, 0))) #define PD_SZ2BYTES(Sz) (sizeof(ProcDict) + ((Sz) - 1)*sizeof(Eterm)) diff --git a/erts/emulator/beam/erl_trace.c b/erts/emulator/beam/erl_trace.c index 04f3160d42..8855449ca1 100644 --- a/erts/emulator/beam/erl_trace.c +++ b/erts/emulator/beam/erl_trace.c @@ -3230,7 +3230,7 @@ static int tracer_cmp_fun(void* a, void* b) static HashValue tracer_hash_fun(void* obj) { - return make_internal_hash(((ErtsTracerNif*)obj)->module); + return make_internal_hash(((ErtsTracerNif*)obj)->module, 0); } static void *tracer_alloc_fun(void* tmpl) diff --git a/erts/emulator/beam/erl_utils.h b/erts/emulator/beam/erl_utils.h index 47289a0af1..b38beaf93d 100644 --- a/erts/emulator/beam/erl_utils.h +++ b/erts/emulator/beam/erl_utils.h @@ -118,9 +118,9 @@ int erts_fit_in_bits_uint(Uint); Sint erts_list_length(Eterm); int erts_is_builtin(Eterm, Eterm, int); Uint32 block_hash(byte *, unsigned, Uint32); -Uint32 make_hash2(Eterm); +Uint32 make_hash2(Eterm, Uint32 salt); Uint32 make_hash(Eterm); -Uint32 make_internal_hash(Eterm); +Uint32 make_internal_hash(Eterm, Uint32 salt); void erts_save_emu_args(int argc, char **argv); Eterm erts_get_emu_args(struct process *c_p); diff --git a/erts/emulator/beam/utils.c b/erts/emulator/beam/utils.c index 8f3f48f38f..2378c057dd 100644 --- a/erts/emulator/beam/utils.c +++ b/erts/emulator/beam/utils.c @@ -1003,7 +1003,7 @@ tail_recur: break; } case MAP_DEF: - hash = hash*FUNNY_NUMBER13 + FUNNY_NUMBER14 + make_hash2(term); + hash = hash*FUNNY_NUMBER13 + FUNNY_NUMBER14 + make_hash2(term, 0); break; case TUPLE_DEF: { @@ -1109,7 +1109,7 @@ block_hash(byte *k, unsigned length, Uint32 initval) } Uint32 -make_hash2(Eterm term) +make_hash2(Eterm term, Uint32 salt) { Uint32 hash; Uint32 hash_xor_pairs; @@ -1179,7 +1179,7 @@ make_hash2(Eterm term) switch (term & _TAG_IMMED2_MASK) { case _TAG_IMMED2_ATOM: /* Fast, but the poor hash value should be mixed. */ - return atom_tab(atom_val(term))->slot.bucket.hvalue; + return atom_tab(atom_val(term))->slot.bucket.hvalue ^ salt; } break; case _TAG_IMMED1_SMALL: @@ -1190,7 +1190,7 @@ make_hash2(Eterm term) term = small_to_big(x, tmp_big); break; } - hash = 0; + hash = salt; SINT32_HASH(x, HCONST); return hash; } @@ -1201,7 +1201,7 @@ make_hash2(Eterm term) DECLARE_ESTACK(s); UseTmpHeapNoproc(2); - hash = 0; + hash = salt; for (;;) { switch (primary_tag(term)) { case TAG_PRIMARY_LIST: @@ -1277,7 +1277,7 @@ make_hash2(Eterm term) ESTACK_PUSH(s, hash_xor_pairs); ESTACK_PUSH(s, hash); ESTACK_PUSH(s, HASH_MAP_TAIL); - hash = 0; + hash = salt; hash_xor_pairs = 0; for (i = size - 1; i >= 0; i--) { ESTACK_PUSH(s, HASH_MAP_PAIR); @@ -1296,7 +1296,7 @@ make_hash2(Eterm term) ESTACK_PUSH(s, hash_xor_pairs); ESTACK_PUSH(s, hash); ESTACK_PUSH(s, HASH_MAP_TAIL); - hash = 0; + hash = salt; hash_xor_pairs = 0; } switch (hdr & _HEADER_MAP_SUBTAG_MASK) { @@ -1471,7 +1471,7 @@ make_hash2(Eterm term) break; default: - erts_exit(ERTS_ERROR_EXIT, "Invalid tag in make_hash2(0x%X)\n", term); + erts_exit(ERTS_ERROR_EXIT, "Invalid tag in make_hash2(0x%X, %lu)\n", term, salt); } } break; @@ -1488,21 +1488,21 @@ make_hash2(Eterm term) case _TAG_IMMED1_IMMED2: switch (term & _TAG_IMMED2_MASK) { case _TAG_IMMED2_ATOM: - if (hash == 0) + if (hash == salt) /* Fast, but the poor hash value should be mixed. */ - hash = atom_tab(atom_val(term))->slot.bucket.hvalue; + hash = atom_tab(atom_val(term))->slot.bucket.hvalue ^ salt; else UINT32_HASH(atom_tab(atom_val(term))->slot.bucket.hvalue, HCONST_3); goto hash2_common; case _TAG_IMMED2_NIL: - if (hash == 0) - hash = 3468870702UL; + if (hash == salt) + hash = 3468870702UL ^ salt; else UINT32_HASH(NIL_DEF, HCONST_2); goto hash2_common; default: - erts_exit(ERTS_ERROR_EXIT, "Invalid tag in make_hash2(0x%X)\n", term); + erts_exit(ERTS_ERROR_EXIT, "Invalid tag in make_hash2(0x%X, %lu)\n", term, salt); } case _TAG_IMMED1_SMALL: { @@ -1518,7 +1518,7 @@ make_hash2(Eterm term) } break; default: - erts_exit(ERTS_ERROR_EXIT, "Invalid tag in make_hash2(0x%X)\n", term); + erts_exit(ERTS_ERROR_EXIT, "Invalid tag in make_hash2(0x%X, %lu)\n", term, salt); hash2_common: /* Uint32 hash always has the hash value of the previous term, @@ -1542,7 +1542,7 @@ make_hash2(Eterm term) } case HASH_MAP_PAIR: hash_xor_pairs ^= hash; - hash = 0; + hash = salt; goto hash2_common; default: break; @@ -1578,7 +1578,7 @@ do { /* Lightweight mixing of constant (type info) */ \ } while (0) Uint32 -make_internal_hash(Eterm term) +make_internal_hash(Eterm term, Uint32 salt) { Uint32 hash; Uint32 hash_xor_pairs; @@ -1587,7 +1587,7 @@ make_internal_hash(Eterm term) /* Optimization. Simple cases before declaration of estack. */ if (primary_tag(term) == TAG_PRIMARY_IMMED1) { - hash = 0; + hash = salt; #if ERTS_SIZEOF_ETERM == 8 UINT32_HASH_2((Uint32)term, (Uint32)(term >> 32), HCONST); #elif ERTS_SIZEOF_ETERM == 4 @@ -1601,7 +1601,7 @@ make_internal_hash(Eterm term) Eterm tmp; DECLARE_ESTACK(s); - hash = 0; + hash = salt; for (;;) { switch (primary_tag(term)) { case TAG_PRIMARY_LIST: @@ -1894,7 +1894,7 @@ make_internal_hash(Eterm term) goto pop_next; } default: - erts_exit(ERTS_ERROR_EXIT, "Invalid tag in make_hash2(0x%X)\n", term); + erts_exit(ERTS_ERROR_EXIT, "Invalid tag in make_internal_hash(0x%X, %lu)\n", term, salt); } } break; @@ -1907,7 +1907,7 @@ make_internal_hash(Eterm term) goto pop_next; default: - erts_exit(ERTS_ERROR_EXIT, "Invalid tag in make_hash2(0x%X)\n", term); + erts_exit(ERTS_ERROR_EXIT, "Invalid tag in make_internal_hash(0x%X, %lu)\n", term, salt); pop_next: if (ESTACK_ISEMPTY(s)) { diff --git a/erts/emulator/hipe/hipe_bif0.c b/erts/emulator/hipe/hipe_bif0.c index 8b420b9e9b..b7297043e5 100644 --- a/erts/emulator/hipe/hipe_bif0.c +++ b/erts/emulator/hipe/hipe_bif0.c @@ -496,7 +496,7 @@ static ErlOffHeap const_term_table_off_heap; static HashValue const_term_hash(void *tmpl) { - return make_hash2((Eterm)tmpl); + return make_hash2((Eterm)tmpl, 0); } static int const_term_cmp(void *tmpl, void *bucket) diff --git a/erts/emulator/test/nif_SUITE.erl b/erts/emulator/test/nif_SUITE.erl index e177fa4963..36af68be60 100644 --- a/erts/emulator/test/nif_SUITE.erl +++ b/erts/emulator/test/nif_SUITE.erl @@ -2628,7 +2628,7 @@ nif_internal_hash(Config) -> OnesPerBit = lists:foldl( fun (Term, Acc) -> - NifHashValue = hash_nif(internal, Term), + NifHashValue = hash_nif(internal, Term, 0), lists:foldl( fun (BitIndex, AccB) -> BitValue = (NifHashValue band (1 bsl BitIndex)) bsr BitIndex, @@ -2661,7 +2661,7 @@ nif_phash2(Config) -> lists:foreach( fun (Term) -> HashValue = erlang:phash2(Term), - NifHashValue = hash_nif(phash2, Term), + NifHashValue = hash_nif(phash2, Term, 0), (HashValue =:= NifHashValue orelse ct:fail("Expected: ~p\nActual: ~p", [HashValue, NifHashValue])) @@ -2714,7 +2714,7 @@ type_test() -> ?nif_stub. tuple_2_list(_) -> ?nif_stub. is_identical(_,_) -> ?nif_stub. compare(_,_) -> ?nif_stub. -hash_nif(_, _) -> ?nif_stub. +hash_nif(_Type, _Term, _Salt) -> ?nif_stub. many_args_100(_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_) -> ?nif_stub. clone_bin(_) -> ?nif_stub. make_sub_bin(_,_,_) -> ?nif_stub. diff --git a/erts/emulator/test/nif_SUITE_data/nif_SUITE.c b/erts/emulator/test/nif_SUITE_data/nif_SUITE.c index 9d65b9c09b..2a80d48b62 100644 --- a/erts/emulator/test/nif_SUITE_data/nif_SUITE.c +++ b/erts/emulator/test/nif_SUITE_data/nif_SUITE.c @@ -689,7 +689,7 @@ static ERL_NIF_TERM compare(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[]) static ERL_NIF_TERM hash_nif(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[]) { - if (argc != 2) { + if (argc != 3) { return enif_make_badarg(env); } @@ -704,7 +704,12 @@ static ERL_NIF_TERM hash_nif(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[] return enif_make_badarg(env); } - return enif_make_ulong(env, enif_hash(type, argv[1])); + unsigned long salt; + if (! enif_get_ulong(env, argv[2], &salt)) { + return enif_make_badarg(env); + } + + return enif_make_ulong(env, enif_hash(type, argv[1], salt)); } static ERL_NIF_TERM many_args_100(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[]) @@ -2884,7 +2889,7 @@ static ErlNifFunc nif_funcs[] = {"tuple_2_list", 1, tuple_2_list}, {"is_identical",2,is_identical}, {"compare",2,compare}, - {"hash_nif",2,hash_nif}, + {"hash_nif",3,hash_nif}, {"many_args_100", 100, many_args_100}, {"clone_bin", 1, clone_bin}, {"make_sub_bin", 3, make_sub_bin}, -- cgit v1.2.3 From c94506ccc003016db49fa2dbe5741196e071d45a Mon Sep 17 00:00:00 2001 From: Guilherme Andrade Date: Sat, 22 Apr 2017 18:40:26 +0100 Subject: erts: Add test cases for salted enif_hash calls --- erts/emulator/test/nif_SUITE.erl | 148 ++++++++++++++++++++++++++++----------- 1 file changed, 107 insertions(+), 41 deletions(-) diff --git a/erts/emulator/test/nif_SUITE.erl b/erts/emulator/test/nif_SUITE.erl index 36af68be60..6e4866bfd8 100644 --- a/erts/emulator/test/nif_SUITE.erl +++ b/erts/emulator/test/nif_SUITE.erl @@ -58,7 +58,9 @@ nif_port_command/1, nif_snprintf/1, nif_internal_hash/1, - nif_phash2/1 + nif_internal_hash_salted/1, + nif_phash2/1, + nif_phash2_salted/1 ]). -export([many_args_100/100]). @@ -94,7 +96,9 @@ all() -> nif_port_command, nif_snprintf, nif_internal_hash, - nif_phash2]. + nif_internal_hash_salted, + nif_phash2, + nif_phash2_salted]. groups() -> [{G, [], api_repeaters()} || G <- api_groups()] @@ -2616,57 +2620,119 @@ nif_snprintf(Config) -> nif_internal_hash(Config) -> ensure_lib_loaded(Config), - Terms = - [random_term() || _ <- lists:seq(1, 5000)], + HashValueBitSize = nif_hash_result_bitsize(internal), + Terms = unique([random_term() || _ <- lists:seq(1, 5000)]), + HashValues = [hash_nif(internal, Term, 0) || Term <- Terms], + test_bit_distribution_fitness(HashValues, HashValueBitSize, 0.05). - % Unlike the phash2 hash, in this case we - % have nothing to compare to, so let's try - % and at least make sure the distribution - % isn't outright wrong, statistical nuances - % aside. +nif_internal_hash_salted(Config) -> + ensure_lib_loaded(Config), + test_salted_nif_hash(internal). + +nif_phash2(Config) -> + ensure_lib_loaded(Config), + HashValueBitSize = nif_hash_result_bitsize(phash2), + Terms = unique([random_term() || _ <- lists:seq(1, 5000)]), + HashValues = + lists:map( + fun (Term) -> + HashValue = erlang:phash2(Term), + NifHashValue = hash_nif(phash2, Term, 0), + (HashValue =:= NifHashValue + orelse ct:fail("Expected: ~p\nActual: ~p", + [HashValue, NifHashValue])), + HashValue + end, + Terms), + test_bit_distribution_fitness(HashValues, HashValueBitSize, 0.05). + +nif_phash2_salted(Config) -> + ensure_lib_loaded(Config), + test_salted_nif_hash(phash2). + +test_salted_nif_hash(HashType) -> + HashValueBitSize = nif_hash_result_bitsize(HashType), + Terms = unique([random_term() || _ <- lists:seq(1, 5000)]), + Salts = unique([random_uint32() || _ <- lists:seq(1, 100)]), + {HashValuesPerSalt, HashValuesPerTerm} = + lists:mapfoldl( + fun (Salt, Acc) -> + {HashValues, NewAcc} = + lists:mapfoldl( + fun (Term, AccB) -> + HashValue = hash_nif(HashType, Term, Salt), + NewAccB = dict:append(Term, HashValue, AccB), + {HashValue, NewAccB} + end, + Acc, + Terms), + {{Salt, HashValues}, NewAcc} + end, + dict:new(), + Salts), + + % Test per-salt hash distribution of different terms + lists:foreach( + fun ({_Salt, HashValues}) -> + test_bit_distribution_fitness(HashValues, HashValueBitSize, 0.05) + end, + HashValuesPerSalt), + % Test per-term hash distribution of different salts + dict:fold( + fun (_Term, HashValues, Acc) -> + % Be more tolerant of relative deviation, + % as there's fewer hash values here. + test_bit_distribution_fitness(HashValues, HashValueBitSize, 0.30), + Acc + end, + ok, + HashValuesPerTerm). + +test_bit_distribution_fitness(Integers, BitSize, MaxRelativeDeviation) -> + MaxInteger = (1 bsl BitSize) - 1, OnesPerBit = lists:foldl( - fun (Term, Acc) -> - NifHashValue = hash_nif(internal, Term, 0), + fun (Integer, Acc) when Integer >= 0, Integer =< MaxInteger -> lists:foldl( fun (BitIndex, AccB) -> - BitValue = (NifHashValue band (1 bsl BitIndex)) bsr BitIndex, - dict:update_counter(BitIndex, BitValue, AccB) + BitValue = (Integer band (1 bsl BitIndex)) bsr BitIndex, + orddict:update_counter(BitIndex, BitValue, AccB) end, Acc, - lists:seq(0, 31)) + lists:seq(0, BitSize - 1)) end, - dict:new(), - Terms), + orddict:new(), + Integers), + + ExpectedNrOfOnes = length(Integers) div 2, + FailureText = + orddict:fold( + fun (BitIndex, NrOfOnes, Acc) -> + RelativeDeviation = abs(NrOfOnes - ExpectedNrOfOnes) / length(Integers), + case RelativeDeviation >= MaxRelativeDeviation of + false -> Acc; + true -> + [Acc, + io_lib:format( + "Unreasonable deviation on number of set bits (i=~p): " + "expected ~p, got ~p (relative dev. ~.3f)~n", + [BitIndex, ExpectedNrOfOnes, NrOfOnes, RelativeDeviation])] + end + end, + [], + OnesPerBit), - ExpectedNrOfOnes = length(Terms) div 2, - dict:fold( - fun (BitIndex, NrOfOnes, Acc) -> - RelativeDeviation = abs(NrOfOnes - ExpectedNrOfOnes) / ExpectedNrOfOnes, - (RelativeDeviation < 0.10 - orelse ct:fail("Unreasonable deviation on number of set bits (i=~p): " - "expected ~p, got ~p (relative dev. ~.3f)", - [BitIndex, ExpectedNrOfOnes, NrOfOnes, RelativeDeviation])), - Acc - end, - ok, - OnesPerBit). + (FailureText =:= [] orelse ct:fail(FailureText)). -nif_phash2(Config) -> - ensure_lib_loaded(Config), - Terms = - [random_term() || _ <- lists:seq(1, 5000)], +nif_hash_result_bitsize(internal) -> 32; +nif_hash_result_bitsize(phash2) -> 27. - lists:foreach( - fun (Term) -> - HashValue = erlang:phash2(Term), - NifHashValue = hash_nif(phash2, Term, 0), - (HashValue =:= NifHashValue - orelse ct:fail("Expected: ~p\nActual: ~p", - [HashValue, NifHashValue])) - end, - Terms). +unique(List) -> + lists:usort(List). + +random_uint32() -> + rand:uniform(1 bsl 32) - 1. random_term() -> case rand:uniform(6) of -- cgit v1.2.3 From d810cd2b1ce642703d4986ba26ba50fd7949fcab Mon Sep 17 00:00:00 2001 From: Guilherme Andrade Date: Sat, 22 Apr 2017 18:46:16 +0100 Subject: erts: Improve enif_hash documentation --- erts/doc/src/erl_nif.xml | 7 +++---- 1 file changed, 3 insertions(+), 4 deletions(-) diff --git a/erts/doc/src/erl_nif.xml b/erts/doc/src/erl_nif.xml index 03c96dd3ca..5faf1a05fc 100644 --- a/erts/doc/src/erl_nif.xml +++ b/erts/doc/src/erl_nif.xml @@ -821,8 +821,8 @@ typedef enum { ERL_NIF_INTERNAL_HASH -

Non-portable hash function that gives different hashes for the same Erlang - term depending on machine architecture and ERTS version.

+

Non-portable hash function that only guarantees the same hash + for the same term within one Erlang VM instance.

Generated hash values within 0..2^32-1.

 ERL_NIF_PHASH2 @@ -831,8 +831,7 @@ typedef enum { same Erlang term regardless of machine architecture and ERTS version.

Generated hash values within 0..2^27-1.

Slower than ERL_NIF_INTERNAL_HASH. - When used with salt=0, - it corresponds to + When used with salt=0, it corresponds to erlang:phash2/1.

 -- cgit v1.2.3 From da9abd24a93ae8fe174cdd38fc9699bbc45fdf56 Mon Sep 17 00:00:00 2001 From: Guilherme Andrade Date: Sat, 22 Apr 2017 20:00:28 +0100 Subject: erts: Allow for easier future enif_hash expansion Allow for expanding support to 64-bit hashes without breaking the interface. --- erts/doc/src/erl_nif.xml | 17 +++++++---------- erts/emulator/beam/erl_nif.c | 10 +++------- erts/emulator/beam/erl_nif_api_funcs.h | 2 +- erts/emulator/test/nif_SUITE_data/nif_SUITE.c | 6 +++--- 4 files changed, 14 insertions(+), 21 deletions(-) diff --git a/erts/doc/src/erl_nif.xml b/erts/doc/src/erl_nif.xml index 5faf1a05fc..534c90cbdc 100644 --- a/erts/doc/src/erl_nif.xml +++ b/erts/doc/src/erl_nif.xml @@ -823,13 +823,13 @@ typedef enum {

Non-portable hash function that only guarantees the same hash for the same term within one Erlang VM instance.

-

Generated hash values within 0..2^32-1.

+

It takes 32-bit salt values and generates hashes within 0..2^32-1.

 ERL_NIF_PHASH2

Portable hash function that gives the same hash for the same Erlang term regardless of machine architecture and ERTS version.

-

Generated hash values within 0..2^27-1.

+

It takes 32-bit salt values and generates hashes within 0..2^27-1.

Slower than ERL_NIF_INTERNAL_HASH. When used with salt=0, it corresponds to erlang:phash2/1.

@@ -1411,17 +1411,14 @@ typedef enum { - unsigned long - - enif_hash(ErlNifHash type, ERL_NIF_TERM term, unsigned long salt) - + ErlNifUInt64 + enif_hash(ErlNifHash type, ERL_NIF_TERM term, ErlNifUInt64 salt) Hash terms. -

Hash term according to the specified - ErlNifHash type - and using the least significant 32 bits of salt.

-

Range of returned value depends on the hash type.

+

Hashes term according to the specified + ErlNifHash type.

+

Ranges of taken salt and returned value depend on the hash type.

 diff --git a/erts/emulator/beam/erl_nif.c b/erts/emulator/beam/erl_nif.c index bdfb7f3b8e..3ff6c8d3ed 100644 --- a/erts/emulator/beam/erl_nif.c +++ b/erts/emulator/beam/erl_nif.c @@ -1214,17 +1214,13 @@ int enif_compare(Eterm lhs, Eterm rhs) return result; } -unsigned long enif_hash(ErlNifHash type, Eterm term, unsigned long salt) +ErlNifUInt64 enif_hash(ErlNifHash type, Eterm term, ErlNifUInt64 salt) { -#if SIZEOF_LONG < 4 -/* This *really* shouldn't happen */ -# error Incompatible long word size -#endif switch (type) { case ERL_NIF_INTERNAL_HASH: - return make_internal_hash(term, salt); + return make_internal_hash(term, (Uint32) salt); case ERL_NIF_PHASH2: - return make_hash2(term, salt) & ((1 << 27) - 1); + return make_hash2(term, (Uint32) salt) & ((1 << 27) - 1); default: return 0; } diff --git a/erts/emulator/beam/erl_nif_api_funcs.h b/erts/emulator/beam/erl_nif_api_funcs.h index 6b9f78d46b..1a91a04f32 100644 --- a/erts/emulator/beam/erl_nif_api_funcs.h +++ b/erts/emulator/beam/erl_nif_api_funcs.h @@ -47,7 +47,7 @@ ERL_NIF_API_FUNC_DECL(int,enif_get_list_cell,(ErlNifEnv* env, ERL_NIF_TERM term, ERL_NIF_API_FUNC_DECL(int,enif_get_tuple,(ErlNifEnv* env, ERL_NIF_TERM tpl, int* arity, const ERL_NIF_TERM** array)); ERL_NIF_API_FUNC_DECL(int,enif_is_identical,(ERL_NIF_TERM lhs, ERL_NIF_TERM rhs)); ERL_NIF_API_FUNC_DECL(int,enif_compare,(ERL_NIF_TERM lhs, ERL_NIF_TERM rhs)); -ERL_NIF_API_FUNC_DECL(unsigned long,enif_hash,(ErlNifHash type, ERL_NIF_TERM term, unsigned long salt)); +ERL_NIF_API_FUNC_DECL(ErlNifUInt64,enif_hash,(ErlNifHash type, ERL_NIF_TERM term, ErlNifUInt64 salt)); ERL_NIF_API_FUNC_DECL(ERL_NIF_TERM,enif_make_binary,(ErlNifEnv* env, ErlNifBinary* bin)); ERL_NIF_API_FUNC_DECL(ERL_NIF_TERM,enif_make_badarg,(ErlNifEnv* env)); ERL_NIF_API_FUNC_DECL(ERL_NIF_TERM,enif_make_int,(ErlNifEnv* env, int i)); diff --git a/erts/emulator/test/nif_SUITE_data/nif_SUITE.c b/erts/emulator/test/nif_SUITE_data/nif_SUITE.c index 2a80d48b62..a255c9f096 100644 --- a/erts/emulator/test/nif_SUITE_data/nif_SUITE.c +++ b/erts/emulator/test/nif_SUITE_data/nif_SUITE.c @@ -704,12 +704,12 @@ static ERL_NIF_TERM hash_nif(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[] return enif_make_badarg(env); } - unsigned long salt; - if (! enif_get_ulong(env, argv[2], &salt)) { + ErlNifUInt64 salt; + if (! enif_get_uint64(env, argv[2], &salt)) { return enif_make_badarg(env); } - return enif_make_ulong(env, enif_hash(type, argv[1], salt)); + return enif_make_uint64(env, enif_hash(type, argv[1], salt)); } static ERL_NIF_TERM many_args_100(ErlNifEnv* env, int argc, const ERL_NIF_TERM argv[]) -- cgit v1.2.3 From 3d6b8e7fb68543713f1620a45b8a590ef4ed88a5 Mon Sep 17 00:00:00 2001 From: Guilherme Andrade Date: Mon, 24 Apr 2017 22:51:49 +0100 Subject: erts: Discontinue salted use of enif_hash/phash2 --- erts/doc/src/erl_nif.xml | 8 ++++---- erts/emulator/beam/bif.c | 4 ++-- erts/emulator/beam/erl_nif.c | 6 +++++- erts/emulator/beam/erl_utils.h | 2 +- erts/emulator/beam/utils.c | 30 +++++++++++++++--------------- erts/emulator/hipe/hipe_bif0.c | 2 +- erts/emulator/test/nif_SUITE.erl | 13 ++++--------- 7 files changed, 32 insertions(+), 33 deletions(-) diff --git a/erts/doc/src/erl_nif.xml b/erts/doc/src/erl_nif.xml index 534c90cbdc..05b519fe7d 100644 --- a/erts/doc/src/erl_nif.xml +++ b/erts/doc/src/erl_nif.xml @@ -829,10 +829,10 @@ typedef enum {

Portable hash function that gives the same hash for the same Erlang term regardless of machine architecture and ERTS version.

-

It takes 32-bit salt values and generates hashes within 0..2^27-1.

+

It ignores salt values and generates hashes within 0..2^27-1.

Slower than ERL_NIF_INTERNAL_HASH. - When used with salt=0, it corresponds to - erlang:phash2/1.

+ It corresponds to erlang:phash2/1. +

@@ -1418,7 +1418,7 @@ typedef enum {

Hashes term according to the specified ErlNifHash type.

-

Ranges of taken salt and returned value depend on the hash type.

+

Ranges of taken salt (if any) and returned value depend on the hash type.

 diff --git a/erts/emulator/beam/bif.c b/erts/emulator/beam/bif.c index 7473a8e43f..214de3652f 100644 --- a/erts/emulator/beam/bif.c +++ b/erts/emulator/beam/bif.c @@ -4881,7 +4881,7 @@ BIF_RETTYPE phash2_1(BIF_ALIST_1) { Uint32 hash; - hash = make_hash2(BIF_ARG_1, 0); + hash = make_hash2(BIF_ARG_1); BIF_RET(make_small(hash & ((1L << 27) - 1))); } @@ -4901,7 +4901,7 @@ BIF_RETTYPE phash2_2(BIF_ALIST_2) } range = (Uint32) u; } - hash = make_hash2(BIF_ARG_1, 0); + hash = make_hash2(BIF_ARG_1); if (range) { final_hash = hash % range; /* [0..range-1] */ } else { diff --git a/erts/emulator/beam/erl_nif.c b/erts/emulator/beam/erl_nif.c index 3ff6c8d3ed..e101747011 100644 --- a/erts/emulator/beam/erl_nif.c +++ b/erts/emulator/beam/erl_nif.c @@ -1220,7 +1220,11 @@ ErlNifUInt64 enif_hash(ErlNifHash type, Eterm term, ErlNifUInt64 salt) case ERL_NIF_INTERNAL_HASH: return make_internal_hash(term, (Uint32) salt); case ERL_NIF_PHASH2: - return make_hash2(term, (Uint32) salt) & ((1 << 27) - 1); + /* It appears that make_hash2 doesn't always react to seasoning + * as well as it should. Therefore, let's make it ignore the salt + * value and declare salted uses of phash2 as unsupported. + */ + return make_hash2(term) & ((1 << 27) - 1); default: return 0; } diff --git a/erts/emulator/beam/erl_utils.h b/erts/emulator/beam/erl_utils.h index b38beaf93d..75d7e47239 100644 --- a/erts/emulator/beam/erl_utils.h +++ b/erts/emulator/beam/erl_utils.h @@ -118,7 +118,7 @@ int erts_fit_in_bits_uint(Uint); Sint erts_list_length(Eterm); int erts_is_builtin(Eterm, Eterm, int); Uint32 block_hash(byte *, unsigned, Uint32); -Uint32 make_hash2(Eterm, Uint32 salt); +Uint32 make_hash2(Eterm); Uint32 make_hash(Eterm); Uint32 make_internal_hash(Eterm, Uint32 salt); diff --git a/erts/emulator/beam/utils.c b/erts/emulator/beam/utils.c index 2378c057dd..9d140470ac 100644 --- a/erts/emulator/beam/utils.c +++ b/erts/emulator/beam/utils.c @@ -1003,7 +1003,7 @@ tail_recur: break; } case MAP_DEF: - hash = hash*FUNNY_NUMBER13 + FUNNY_NUMBER14 + make_hash2(term, 0); + hash = hash*FUNNY_NUMBER13 + FUNNY_NUMBER14 + make_hash2(term); break; case TUPLE_DEF: { @@ -1109,7 +1109,7 @@ block_hash(byte *k, unsigned length, Uint32 initval) } Uint32 -make_hash2(Eterm term, Uint32 salt) +make_hash2(Eterm term) { Uint32 hash; Uint32 hash_xor_pairs; @@ -1179,7 +1179,7 @@ make_hash2(Eterm term, Uint32 salt) switch (term & _TAG_IMMED2_MASK) { case _TAG_IMMED2_ATOM: /* Fast, but the poor hash value should be mixed. */ - return atom_tab(atom_val(term))->slot.bucket.hvalue ^ salt; + return atom_tab(atom_val(term))->slot.bucket.hvalue; } break; case _TAG_IMMED1_SMALL: @@ -1190,7 +1190,7 @@ make_hash2(Eterm term, Uint32 salt) term = small_to_big(x, tmp_big); break; } - hash = salt; + hash = 0; SINT32_HASH(x, HCONST); return hash; } @@ -1201,7 +1201,7 @@ make_hash2(Eterm term, Uint32 salt) DECLARE_ESTACK(s); UseTmpHeapNoproc(2); - hash = salt; + hash = 0; for (;;) { switch (primary_tag(term)) { case TAG_PRIMARY_LIST: @@ -1277,7 +1277,7 @@ make_hash2(Eterm term, Uint32 salt) ESTACK_PUSH(s, hash_xor_pairs); ESTACK_PUSH(s, hash); ESTACK_PUSH(s, HASH_MAP_TAIL); - hash = salt; + hash = 0; hash_xor_pairs = 0; for (i = size - 1; i >= 0; i--) { ESTACK_PUSH(s, HASH_MAP_PAIR); @@ -1296,7 +1296,7 @@ make_hash2(Eterm term, Uint32 salt) ESTACK_PUSH(s, hash_xor_pairs); ESTACK_PUSH(s, hash); ESTACK_PUSH(s, HASH_MAP_TAIL); - hash = salt; + hash = 0; hash_xor_pairs = 0; } switch (hdr & _HEADER_MAP_SUBTAG_MASK) { @@ -1471,7 +1471,7 @@ make_hash2(Eterm term, Uint32 salt) break; default: - erts_exit(ERTS_ERROR_EXIT, "Invalid tag in make_hash2(0x%X, %lu)\n", term, salt); + erts_exit(ERTS_ERROR_EXIT, "Invalid tag in make_hash2(0x%X)\n", term); } } break; @@ -1488,21 +1488,21 @@ make_hash2(Eterm term, Uint32 salt) case _TAG_IMMED1_IMMED2: switch (term & _TAG_IMMED2_MASK) { case _TAG_IMMED2_ATOM: - if (hash == salt) + if (hash == 0) /* Fast, but the poor hash value should be mixed. */ - hash = atom_tab(atom_val(term))->slot.bucket.hvalue ^ salt; + hash = atom_tab(atom_val(term))->slot.bucket.hvalue; else UINT32_HASH(atom_tab(atom_val(term))->slot.bucket.hvalue, HCONST_3); goto hash2_common; case _TAG_IMMED2_NIL: - if (hash == salt) - hash = 3468870702UL ^ salt; + if (hash == 0) + hash = 3468870702UL; else UINT32_HASH(NIL_DEF, HCONST_2); goto hash2_common; default: - erts_exit(ERTS_ERROR_EXIT, "Invalid tag in make_hash2(0x%X, %lu)\n", term, salt); + erts_exit(ERTS_ERROR_EXIT, "Invalid tag in make_hash2(0x%X)\n", term); } case _TAG_IMMED1_SMALL: { @@ -1518,7 +1518,7 @@ make_hash2(Eterm term, Uint32 salt) } break; default: - erts_exit(ERTS_ERROR_EXIT, "Invalid tag in make_hash2(0x%X, %lu)\n", term, salt); + erts_exit(ERTS_ERROR_EXIT, "Invalid tag in make_hash2(0x%X)\n", term); hash2_common: /* Uint32 hash always has the hash value of the previous term, @@ -1542,7 +1542,7 @@ make_hash2(Eterm term, Uint32 salt) } case HASH_MAP_PAIR: hash_xor_pairs ^= hash; - hash = salt; + hash = 0; goto hash2_common; default: break; diff --git a/erts/emulator/hipe/hipe_bif0.c b/erts/emulator/hipe/hipe_bif0.c index b7297043e5..8b420b9e9b 100644 --- a/erts/emulator/hipe/hipe_bif0.c +++ b/erts/emulator/hipe/hipe_bif0.c @@ -496,7 +496,7 @@ static ErlOffHeap const_term_table_off_heap; static HashValue const_term_hash(void *tmpl) { - return make_hash2((Eterm)tmpl, 0); + return make_hash2((Eterm)tmpl); } static int const_term_cmp(void *tmpl, void *bucket) diff --git a/erts/emulator/test/nif_SUITE.erl b/erts/emulator/test/nif_SUITE.erl index 6e4866bfd8..8ad11d3bf3 100644 --- a/erts/emulator/test/nif_SUITE.erl +++ b/erts/emulator/test/nif_SUITE.erl @@ -59,8 +59,7 @@ nif_snprintf/1, nif_internal_hash/1, nif_internal_hash_salted/1, - nif_phash2/1, - nif_phash2_salted/1 + nif_phash2/1 ]). -export([many_args_100/100]). @@ -97,8 +96,7 @@ all() -> nif_snprintf, nif_internal_hash, nif_internal_hash_salted, - nif_phash2, - nif_phash2_salted]. + nif_phash2]. groups() -> [{G, [], api_repeaters()} || G <- api_groups()] @@ -2637,7 +2635,8 @@ nif_phash2(Config) -> lists:map( fun (Term) -> HashValue = erlang:phash2(Term), - NifHashValue = hash_nif(phash2, Term, 0), + Salt = random_uint32(), % phash2 should ignore salt + NifHashValue = hash_nif(phash2, Term, Salt), (HashValue =:= NifHashValue orelse ct:fail("Expected: ~p\nActual: ~p", [HashValue, NifHashValue])), @@ -2646,10 +2645,6 @@ nif_phash2(Config) -> Terms), test_bit_distribution_fitness(HashValues, HashValueBitSize, 0.05). -nif_phash2_salted(Config) -> - ensure_lib_loaded(Config), - test_salted_nif_hash(phash2). - test_salted_nif_hash(HashType) -> HashValueBitSize = nif_hash_result_bitsize(HashType), Terms = unique([random_term() || _ <- lists:seq(1, 5000)]), -- cgit v1.2.3 From e40ec046a2a1037b2f87b657503c5f21c5de4e2a Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Thu, 27 Apr 2017 12:18:57 +0200 Subject: Move enif_hash last to not break Windows --- erts/emulator/beam/erl_nif_api_funcs.h | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/erts/emulator/beam/erl_nif_api_funcs.h b/erts/emulator/beam/erl_nif_api_funcs.h index 1a91a04f32..b34058f303 100644 --- a/erts/emulator/beam/erl_nif_api_funcs.h +++ b/erts/emulator/beam/erl_nif_api_funcs.h @@ -47,7 +47,6 @@ ERL_NIF_API_FUNC_DECL(int,enif_get_list_cell,(ErlNifEnv* env, ERL_NIF_TERM term, ERL_NIF_API_FUNC_DECL(int,enif_get_tuple,(ErlNifEnv* env, ERL_NIF_TERM tpl, int* arity, const ERL_NIF_TERM** array)); ERL_NIF_API_FUNC_DECL(int,enif_is_identical,(ERL_NIF_TERM lhs, ERL_NIF_TERM rhs)); ERL_NIF_API_FUNC_DECL(int,enif_compare,(ERL_NIF_TERM lhs, ERL_NIF_TERM rhs)); -ERL_NIF_API_FUNC_DECL(ErlNifUInt64,enif_hash,(ErlNifHash type, ERL_NIF_TERM term, ErlNifUInt64 salt)); ERL_NIF_API_FUNC_DECL(ERL_NIF_TERM,enif_make_binary,(ErlNifEnv* env, ErlNifBinary* bin)); ERL_NIF_API_FUNC_DECL(ERL_NIF_TERM,enif_make_badarg,(ErlNifEnv* env)); ERL_NIF_API_FUNC_DECL(ERL_NIF_TERM,enif_make_int,(ErlNifEnv* env, int i)); @@ -181,6 +180,7 @@ ERL_NIF_API_FUNC_DECL(ErlNifResourceType*,enif_open_resource_type_x,(ErlNifEnv*, ERL_NIF_API_FUNC_DECL(int, enif_monitor_process,(ErlNifEnv*,void* obj,const ErlNifPid*,ErlDrvMonitor *monitor)); ERL_NIF_API_FUNC_DECL(int, enif_demonitor_process,(ErlNifEnv*,void* obj,const ErlDrvMonitor *monitor)); ERL_NIF_API_FUNC_DECL(int, enif_compare_monitors,(const ErlNifMonitor*,const ErlNifMonitor*)); +ERL_NIF_API_FUNC_DECL(ErlNifUInt64,enif_hash,(ErlNifHash type, ERL_NIF_TERM term, ErlNifUInt64 salt)); /* ** ADD NEW ENTRIES HERE (before this comment) !!! @@ -209,7 +209,6 @@ ERL_NIF_API_FUNC_DECL(int, enif_compare_monitors,(const ErlNifMonitor*,const Erl # define enif_get_list_cell ERL_NIF_API_FUNC_MACRO(enif_get_list_cell) # define enif_is_identical ERL_NIF_API_FUNC_MACRO(enif_is_identical) # define enif_compare ERL_NIF_API_FUNC_MACRO(enif_compare) -# define enif_hash ERL_NIF_API_FUNC_MACRO(enif_hash) # define enif_make_binary ERL_NIF_API_FUNC_MACRO(enif_make_binary) # define enif_make_badarg ERL_NIF_API_FUNC_MACRO(enif_make_badarg) @@ -344,6 +343,7 @@ ERL_NIF_API_FUNC_DECL(int, enif_compare_monitors,(const ErlNifMonitor*,const Erl # define enif_monitor_process ERL_NIF_API_FUNC_MACRO(enif_monitor_process) # define enif_demonitor_process ERL_NIF_API_FUNC_MACRO(enif_demonitor_process) # define enif_compare_monitors ERL_NIF_API_FUNC_MACRO(enif_compare_monitors) +# define enif_hash ERL_NIF_API_FUNC_MACRO(enif_hash) /* ** ADD NEW ENTRIES HERE (before this comment) -- cgit v1.2.3