From 1005ffd33c7110f2097f711b6e9e07fbb9ae1d32 Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Wed, 2 May 2018 17:33:28 +0200 Subject: erts: Refactor pseudo deleted ets objects Separate pseudo-deleted-flag from the hash value. --- erts/emulator/beam/erl_db_hash.c | 85 +++++++++++++++++++++++----------------- erts/emulator/beam/erl_db_hash.h | 13 +++++- 2 files changed, 61 insertions(+), 37 deletions(-) diff --git a/erts/emulator/beam/erl_db_hash.c b/erts/emulator/beam/erl_db_hash.c index 8bbd0cd9a3..8cabf04fb1 100644 --- a/erts/emulator/beam/erl_db_hash.c +++ b/erts/emulator/beam/erl_db_hash.c @@ -21,6 +21,7 @@ /* ** Implementation of unordered ETS tables. ** The tables are implemented as linear dynamic hash tables. +** https://en.wikipedia.org/wiki/Linear_hashing */ /* SMP: @@ -148,7 +149,7 @@ static ERTS_INLINE Uint hash_to_ix(DbTableHash* tb, HashValue hval) return ix; } -/* Remember a slot containing a pseudo-deleted item (INVALID_HASH) +/* Remember a slot containing a pseudo-deleted item * Return false if we got raced by unfixing thread * and the object should be deleted for real. */ @@ -179,13 +180,17 @@ static ERTS_INLINE int add_fixed_deletion(DbTableHash* tb, int ix, } -#define MAX_HASH 0xEFFFFFFFUL -#define INVALID_HASH 0xFFFFFFFFUL + +static ERTS_INLINE int is_pseudo_deleted(HashDbTerm* p) +{ + return p->pseudo_deleted; +} + /* 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, 0)) % MAX_HASH) + make_internal_hash(term, 0)) & MAX_HASH_MASK) # define DB_HASH_LOCK_MASK (DB_HASH_LOCK_CNT-1) # define GET_LOCK(tb,hval) (&(tb)->locks->lck_vec[(hval) & DB_HASH_LOCK_MASK].lck) @@ -436,7 +441,8 @@ static ERTS_INLINE void try_shrink(DbTableHash* tb) static ERTS_INLINE int has_live_key(DbTableHash* tb, HashDbTerm* b, Eterm key, HashValue hval) { - if (b->hvalue != hval) return 0; + if (b->hvalue != hval || is_pseudo_deleted(b)) + return 0; else { Eterm itemKey = GETKEY(tb, b->dbterm.tpl); ASSERT(!is_header(itemKey)); @@ -449,7 +455,8 @@ static ERTS_INLINE int has_live_key(DbTableHash* tb, HashDbTerm* b, static ERTS_INLINE int has_key(DbTableHash* tb, HashDbTerm* b, Eterm key, HashValue hval) { - if (b->hvalue != hval && b->hvalue != INVALID_HASH) return 0; + if (b->hvalue != hval) + return 0; else { Eterm itemKey = GETKEY(tb, b->dbterm.tpl); ASSERT(!is_header(itemKey)); @@ -595,7 +602,7 @@ restart: b = *bp; while (b != NULL) { - if (b->hvalue == INVALID_HASH) { + if (is_pseudo_deleted(b)) { *bp = b->next; free_term(tb, b); work++; @@ -764,8 +771,9 @@ int db_put_hash(DbTable *tbl, Eterm obj, int key_clash_fail) */ if (tb->common.status & DB_SET) { HashDbTerm* bnext = b->next; - if (b->hvalue == INVALID_HASH) { + if (is_pseudo_deleted(b)) { erts_atomic_inc_nob(&tb->common.nitems); + b->pseudo_deleted = 0; } else if (key_clash_fail) { ret = DB_ERROR_BADKEY; @@ -773,14 +781,14 @@ int db_put_hash(DbTable *tbl, Eterm obj, int key_clash_fail) } q = replace_dbterm(tb, b, obj); q->next = bnext; - q->hvalue = hval; /* In case of INVALID_HASH */ + ASSERT(q->hvalue == hval); *bp = q; goto Ldone; } else if (key_clash_fail) { /* && (DB_BAG || DB_DUPLICATE_BAG) */ q = b; do { - if (q->hvalue != INVALID_HASH) { + if (!is_pseudo_deleted(q)) { ret = DB_ERROR_BADKEY; goto Ldone; } @@ -792,9 +800,10 @@ int db_put_hash(DbTable *tbl, Eterm obj, int key_clash_fail) q = b; do { if (db_eq(&tb->common,obj,&q->dbterm)) { - if (q->hvalue == INVALID_HASH) { + if (is_pseudo_deleted(q)) { erts_atomic_inc_nob(&tb->common.nitems); - q->hvalue = hval; + q->pseudo_deleted = 0; + ASSERT(q->hvalue == hval); if (q != b) { /* must move to preserve key insertion order */ *qp = q->next; q->next = b; @@ -812,6 +821,7 @@ int db_put_hash(DbTable *tbl, Eterm obj, int key_clash_fail) Lnew: q = new_dbterm(tb, obj); q->hvalue = hval; + q->pseudo_deleted = 0; q->next = b; *bp = q; nitems = erts_atomic_inc_read_nob(&tb->common.nitems); @@ -839,7 +849,7 @@ get_term_list(Process *p, DbTableHash *tb, Eterm key, HashValue hval, if (tb->common.status & (DB_BAG | DB_DUPLICATE_BAG)) { while (b2 && has_key(tb, b2, key, hval)) { - if (b2->hvalue != INVALID_HASH) + if (!is_pseudo_deleted(b2)) sz += b2->dbterm.size + 2; b2 = b2->next; @@ -935,7 +945,7 @@ static int db_get_element_hash(Process *p, DbTable *tbl, while(b2 != NULL && has_key(tb,b2,key,hval)) { if (ndex > arityval(b2->dbterm.tpl[0]) - && b2->hvalue != INVALID_HASH) { + && !is_pseudo_deleted(b2)) { retval = DB_ERROR_BADITEM; goto done; } @@ -943,7 +953,7 @@ static int db_get_element_hash(Process *p, DbTable *tbl, } b = b1; while(b != b2) { - if (b->hvalue != INVALID_HASH) { + if (!is_pseudo_deleted(b)) { Eterm *hp; Eterm copy = db_copy_element_from_ets(&tb->common, p, &b->dbterm, ndex, &hp, 2); @@ -993,7 +1003,7 @@ int db_erase_hash(DbTable *tbl, Eterm key, Eterm *ret) if (nitems_diff == -1 && IS_FIXED(tb) && add_fixed_deletion(tb, ix, 0)) { /* Pseudo remove (no need to keep several of same key) */ - b->hvalue = INVALID_HASH; + b->pseudo_deleted = 1; } else { *bp = b->next; free_term(tb, b); @@ -1002,7 +1012,7 @@ int db_erase_hash(DbTable *tbl, Eterm key, Eterm *ret) } } else { - if (nitems_diff && b->hvalue != INVALID_HASH) + if (nitems_diff && !is_pseudo_deleted(b)) break; } bp = &b->next; @@ -1045,7 +1055,7 @@ static int db_erase_object_hash(DbTable *tbl, Eterm object, Eterm *ret) if (db_eq(&tb->common,object, &b->dbterm)) { --nitems_diff; if (nkeys==1 && IS_FIXED(tb) && add_fixed_deletion(tb,ix,0)) { - b->hvalue = INVALID_HASH; /* Pseudo remove */ + b->pseudo_deleted = 1; bp = &b->next; b = b->next; } else { @@ -1060,7 +1070,7 @@ static int db_erase_object_hash(DbTable *tbl, Eterm object, Eterm *ret) } } } - else if (nitems_diff && b->hvalue != INVALID_HASH) { + else if (nitems_diff && !is_pseudo_deleted(b)) { break; } bp = &b->next; @@ -1253,7 +1263,7 @@ static int match_traverse(Process* p, DbTableHash* tb, */ for(;;) { if (*current_ptr != NULL) { - if ((*current_ptr)->hvalue != INVALID_HASH) { + if (!is_pseudo_deleted(*current_ptr)) { match_res = db_match_dbterm(&tb->common, p, mpi.mp, 0, &(*current_ptr)->dbterm, hpp, 2); saved_current = *current_ptr; @@ -1380,7 +1390,7 @@ static int match_traverse_continue(Process* p, DbTableHash* tb, current_ptr = &BUCKET(tb,slot_ix); for(;;) { if (*current_ptr != NULL) { - if ((*current_ptr)->hvalue != INVALID_HASH) { + if (!is_pseudo_deleted(*current_ptr)) { match_res = db_match_dbterm(&tb->common, p, *mpp, all_objects, &(*current_ptr)->dbterm, hpp, 2); saved_current = *current_ptr; @@ -1963,7 +1973,7 @@ static int mtraversal_select_delete_on_match_res(void* context_ptr, Sint slot_ix goto do_erase; sd_context_ptr->last_pseudo_delete = slot_ix; } - (*current_ptr)->hvalue = INVALID_HASH; + (*current_ptr)->pseudo_deleted = 1; } else { do_erase: @@ -2106,6 +2116,7 @@ static int mtraversal_select_replace_on_match_res(void* context_ptr, Sint slot_i new = new_dbterm(tb, match_res); new->next = next; new->hvalue = hval; + new->pseudo_deleted = 0; free_term(tb, **current_ptr_ptr); **current_ptr_ptr = new; /* replace 'next' pointer in previous object */ *current_ptr_ptr = &((**current_ptr_ptr)->next); /* advance to next object */ @@ -2226,7 +2237,7 @@ static int db_take_hash(Process *p, DbTable *tbl, Eterm key, Eterm *ret) && add_fixed_deletion(tb, ix, 0)) { /* Pseudo remove (no need to keep several of same key) */ bp = &b->next; - b->hvalue = INVALID_HASH; + b->pseudo_deleted = 1; b = b->next; } else { *bp = b->next; @@ -2267,7 +2278,7 @@ static SWord db_mark_all_deleted_hash(DbTable *tbl, SWord reds) if ((list = BUCKET(tb,i)) != NULL) { add_fixed_deletion(tb, i, 0); do { - list->hvalue = INVALID_HASH; + list->pseudo_deleted = 1; list = list->next; }while(list != NULL); reds--; @@ -2317,7 +2328,7 @@ static void db_print_hash(fmtfn_t to, void *to_arg, int show, DbTable *tbl) continue; erts_print(to, to_arg, "%d: [", i); while(list != 0) { - if (list->hvalue == INVALID_HASH) + if (is_pseudo_deleted(list)) erts_print(to, to_arg, "*"); if (tb->common.compress) { Eterm key = GETKEY(tb, list->dbterm.tpl); @@ -2683,7 +2694,7 @@ static Eterm build_term_list(Process* p, HashDbTerm* ptr1, HashDbTerm* ptr2, if (!sz) { ptr = ptr1; while(ptr != ptr2) { - if (ptr->hvalue != INVALID_HASH) + if (!is_pseudo_deleted(ptr)) sz += ptr->dbterm.size + 2; ptr = ptr->next; } @@ -2694,7 +2705,7 @@ static Eterm build_term_list(Process* p, HashDbTerm* ptr1, HashDbTerm* ptr2, ptr = ptr1; while(ptr != ptr2) { - if (ptr->hvalue != INVALID_HASH) { + if (!is_pseudo_deleted(ptr)) { copy = db_copy_object_from_ets(&tb->common, &ptr->dbterm, &hp, &MSO(p)); list = CONS(hp, copy, list); hp += 2; @@ -2787,7 +2798,7 @@ static void grow(DbTableHash* tb, int nitems) p = *pnext; to_pnext = &BUCKET(tb, to_ix); while (p != NULL) { - if (p->hvalue == INVALID_HASH) { /* rare but possible with fine locking */ + if (is_pseudo_deleted(p)) { /* rare but possible with fine locking */ *pnext = p->next; free_term(tb, p); p = *pnext; @@ -2860,7 +2871,7 @@ static void shrink(DbTableHash* tb, int nitems) * as we must step through "src" anyway to purge pseudo deleted. */ while(*bp != NULL) { - if ((*bp)->hvalue == INVALID_HASH) { + if (is_pseudo_deleted(*bp)) { HashDbTerm* deleted = *bp; *bp = deleted->next; free_term(tb, deleted); @@ -2918,7 +2929,7 @@ static HashDbTerm* next_live(DbTableHash *tb, Uint *iptr, erts_rwmtx_t** lck_ptr ERTS_LC_ASSERT(IS_HASH_RLOCKED(tb,*iptr)); for ( ; list != NULL; list = list->next) { - if (list->hvalue != INVALID_HASH) + if (!is_pseudo_deleted(list)) return list; } @@ -2927,7 +2938,7 @@ static HashDbTerm* next_live(DbTableHash *tb, Uint *iptr, erts_rwmtx_t** lck_ptr list = BUCKET(tb,i); while (list != NULL) { - if (list->hvalue != INVALID_HASH) { + if (!is_pseudo_deleted(list)) { *iptr = i; return list; } @@ -2960,7 +2971,7 @@ db_lookup_dbterm_hash(Process *p, DbTable *tbl, Eterm key, Eterm obj, break; } if (has_key(tb, b, key, hval)) { - if (b->hvalue != INVALID_HASH) { + if (!is_pseudo_deleted(b)) { goto Ldone; } break; @@ -2990,16 +3001,18 @@ db_lookup_dbterm_hash(Process *p, DbTable *tbl, Eterm key, Eterm obj, HashDbTerm *q = new_dbterm(tb, obj); q->hvalue = hval; + q->pseudo_deleted = 0; q->next = NULL; *bp = b = q; flags |= DB_INC_TRY_GROW; } else { HashDbTerm *q, *next = b->next; - ASSERT(b->hvalue == INVALID_HASH); + ASSERT(is_pseudo_deleted(b)); q = replace_dbterm(tb, b, obj); q->next = next; - q->hvalue = hval; + ASSERT(q->hvalue == hval); + q->pseudo_deleted = 0; *bp = b = q; erts_atomic_inc_nob(&tb->common.nitems); } @@ -3037,7 +3050,7 @@ db_finalize_dbterm_hash(int cret, DbUpdateHandle* handle) if (handle->flags & DB_NEW_OBJECT && cret != DB_ERROR_NONE) { if (IS_FIXED(tb) && add_fixed_deletion(tb, hash_to_ix(tb, b->hvalue), 0)) { - b->hvalue = INVALID_HASH; + b->pseudo_deleted = 1; } else { *bp = b->next; free_me = b; @@ -3130,7 +3143,7 @@ void db_calc_stats_hash(DbTableHash* tb, DbHashStats* stats) len = 0; for (b = BUCKET(tb,ix); b!=NULL; b=b->next) { len++; - if (b->hvalue == INVALID_HASH) + if (is_pseudo_deleted(b)) ++kept_items; } sum += len; diff --git a/erts/emulator/beam/erl_db_hash.h b/erts/emulator/beam/erl_db_hash.h index 5f88170ced..127512e1fe 100644 --- a/erts/emulator/beam/erl_db_hash.h +++ b/erts/emulator/beam/erl_db_hash.h @@ -28,9 +28,20 @@ typedef struct fixed_deletion { struct fixed_deletion *next; } FixedDeletion; + +typedef Uint32 HashVal; + typedef struct hash_db_term { struct hash_db_term* next; /* next bucket */ - HashValue hvalue; /* stored hash value */ +#if SIZEOF_VOID_P == 4 + Uint32 hvalue : 31; /* stored hash value */ + Uint32 pseudo_deleted : 1; +# define MAX_HASH_MASK (((Uint32)1 << 31)-1) +#elif SIZEOF_VOID_P == 8 + Uint32 hvalue; + Uint32 pseudo_deleted; +# define MAX_HASH_MASK ((Uint32)(Sint32)-1) +#endif DbTerm dbterm; /* The actual term */ } HashDbTerm; -- cgit v1.2.3