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