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