aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--erts/emulator/beam/erl_db_hash.c85
-rw-r--r--erts/emulator/beam/erl_db_hash.h13
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;
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-24 23:58:46 +0000