1 files changed, 225 insertions, 82 deletions

diff --git a/erts/emulator/beam/erl_db_hash.c b/erts/emulator/beam/erl_db_hash.c
index b1d9eb84bc..383ee7c430 100644
--- a/erts/emulator/beam/erl_db_hash.c
+++ b/erts/emulator/beam/erl_db_hash.c
@@ -174,7 +174,7 @@ static ERTS_INLINE void 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_hash2(term)) % MAX_HASH)
+      make_internal_hash(term)) % MAX_HASH)
 
 #ifdef ERTS_SMP
 #  define DB_HASH_LOCK_MASK (DB_HASH_LOCK_CNT-1)
@@ -382,7 +382,7 @@ static HashDbTerm* search_list(DbTableHash* tb, Eterm key,
 static void shrink(DbTableHash* tb, int nactive);
 static void grow(DbTableHash* tb, int nactive);
 static Eterm build_term_list(Process* p, HashDbTerm* ptr1, HashDbTerm* ptr2,
-			   DbTableHash*);
+			   Uint sz, DbTableHash*);
 static int analyze_pattern(DbTableHash *tb, Eterm pattern, 
 			   struct mp_info *mpi);
 
@@ -426,6 +426,7 @@ static int db_select_count_continue_hash(Process *p, DbTable *tbl,
 
 static int db_select_delete_continue_hash(Process *p, DbTable *tbl,
 					  Eterm continuation, Eterm *ret);
+static int db_take_hash(Process *, DbTable *, Eterm, Eterm *);
 static void db_print_hash(int to,
 			  void *to_arg,
 			  int show,
@@ -443,8 +444,11 @@ static int db_delete_all_objects_hash(Process* p, DbTable* tbl);
 #ifdef HARDDEBUG
 static void db_check_table_hash(DbTableHash *tb);
 #endif
-static int db_lookup_dbterm_hash(DbTable *tbl, Eterm key, DbUpdateHandle* handle);
-static void db_finalize_dbterm_hash(DbUpdateHandle* handle);
+static int
+db_lookup_dbterm_hash(Process *p, DbTable *tbl, Eterm key, Eterm obj,
+                      DbUpdateHandle* handle);
+static void
+db_finalize_dbterm_hash(int cret, DbUpdateHandle* handle);
 
 static ERTS_INLINE void try_shrink(DbTableHash* tb)
 {
@@ -536,6 +540,7 @@ DbTableMethod db_hash =
     db_select_delete_continue_hash,
     db_select_count_hash,
     db_select_count_continue_hash,
+    db_take_hash,
     db_delete_all_objects_hash,
     db_free_table_hash,
     db_free_table_continue_hash,
@@ -646,25 +651,6 @@ restart:
     /* ToDo: Maybe try grow/shrink the table as well */
 }
 
-/* Only used by tests
-*/
-Uint db_kept_items_hash(DbTableHash *tb)
-{
-    Uint kept_items = 0;
-    Uint ix = 0;
-    erts_smp_rwmtx_t* lck = RLOCK_HASH(tb,ix);
-    HashDbTerm* b;
-    do {
-	for (b = BUCKET(tb, ix); b != NULL; b = b->next) {
-	    if (b->hvalue == INVALID_HASH) {
-		++kept_items;
-	    }
-	}	
-	ix = next_slot(tb, ix, &lck);
-    }while (ix);
-    return kept_items;
-}
-
 int db_create_hash(Process *p, DbTable *tbl)
 {
     DbTableHash *tb = &tbl->hash;
@@ -879,34 +865,49 @@ Ldone:
     return ret;
 }
 
+static Eterm
+get_term_list(Process *p, DbTableHash *tb, Eterm key, HashValue hval,
+              HashDbTerm *b1, HashDbTerm **bend)
+{
+    HashDbTerm* b2 = b1->next;
+    Eterm copy;
+    Uint sz = b1->dbterm.size + 2;
+
+    if (tb->common.status & (DB_BAG | DB_DUPLICATE_BAG)) {
+        while (b2 && has_key(tb, b2, key, hval)) {
+	    if (b2->hvalue != INVALID_HASH)
+		sz += b2->dbterm.size + 2;
+
+            b2 = b2->next;
+        }
+    }
+    copy = build_term_list(p, b1, b2, sz, tb);
+    CHECK_TABLES();
+    if (bend) {
+        *bend = b2;
+    }
+    return copy;
+}
+
 int db_get_hash(Process *p, DbTable *tbl, Eterm key, Eterm *ret)
 {
     DbTableHash *tb = &tbl->hash;
     HashValue hval;
     int ix;
-    HashDbTerm* b1;
+    HashDbTerm* b;
     erts_smp_rwmtx_t* lck;
 
     hval = MAKE_HASH(key);
     lck = RLOCK_HASH(tb,hval);
     ix = hash_to_ix(tb, hval);
-    b1 = BUCKET(tb, ix);
-
-    while(b1 != 0) {
-	if (has_live_key(tb,b1,key,hval)) {
-	    HashDbTerm* b2 = b1->next;
-	    Eterm copy;
+    b = BUCKET(tb, ix);
 
-	    if (tb->common.status & (DB_BAG | DB_DUPLICATE_BAG)) {
-		while(b2 != NULL && has_key(tb,b2,key,hval))
-		    b2 = b2->next;
-	    }
-	    copy = build_term_list(p, b1, b2, tb);
-	    CHECK_TABLES();
-	    *ret = copy;
+    while(b != 0) {
+        if (has_live_key(tb, b, key, hval)) {
+            *ret = get_term_list(p, tb, key, hval, b, NULL);
 	    goto done;
 	}
-	b1 = b1->next;
+        b = b->next;
     }
     *ret = NIL;
 done:
@@ -1240,7 +1241,7 @@ static int db_slot_hash(Process *p, DbTable *tbl, Eterm slot_term, Eterm *ret)
     lck = RLOCK_HASH(tb, slot);
     nactive = NACTIVE(tb);
     if (slot < nactive) {
-	*ret = build_term_list(p, BUCKET(tb, slot), 0, tb);
+	*ret = build_term_list(p, BUCKET(tb, slot), NULL, 0, tb);
 	retval = DB_ERROR_NONE;
     }
     else if (slot == nactive) {
@@ -2069,6 +2070,46 @@ trap:
 
 }
     
+static int db_take_hash(Process *p, DbTable *tbl, Eterm key, Eterm *ret)
+{
+    DbTableHash *tb = &tbl->hash;
+    HashDbTerm **bp, *b;
+    HashValue hval = MAKE_HASH(key);
+    erts_smp_rwmtx_t *lck = WLOCK_HASH(tb, hval);
+    int ix = hash_to_ix(tb, hval);
+    int nitems_diff = 0;
+
+    *ret = NIL;
+    for (bp = &BUCKET(tb, ix), b = *bp; b; bp = &b->next, b = b->next) {
+        if (has_live_key(tb, b, key, hval)) {
+            HashDbTerm *bend;
+
+            *ret = get_term_list(p, tb, key, hval, b, &bend);
+            while (b != bend) {
+                --nitems_diff;
+                if (nitems_diff == -1 && IS_FIXED(tb)) {
+                    /* Pseudo remove (no need to keep several of same key) */
+                    add_fixed_deletion(tb, ix);
+                    bp = &b->next;
+                    b->hvalue = INVALID_HASH;
+                    b = b->next;
+                } else {
+                    *bp = b->next;
+                    free_term(tb, b);
+                    b = *bp;
+                }
+            }
+            break;
+        }
+    }
+    WUNLOCK_HASH(lck);
+    if (nitems_diff) {
+        erts_smp_atomic_add_nob(&tb->common.nitems, nitems_diff);
+        try_shrink(tb);
+    }
+    return DB_ERROR_NONE;
+}
+
 /*
 ** Other interface routines (not directly coupled to one bif)
 */
@@ -2104,10 +2145,38 @@ int db_mark_all_deleted_hash(DbTable *tbl)
 static void db_print_hash(int to, void *to_arg, int show, DbTable *tbl)
 {
     DbTableHash *tb = &tbl->hash;
+    DbHashStats stats;
     int i;
 
     erts_print(to, to_arg, "Buckets: %d\n", NACTIVE(tb));
-    
+
+#ifdef ERTS_SMP
+    i = tbl->common.is_thread_safe;
+    /* If crash dumping we set table to thread safe in order to
+       avoid taking any locks */
+    if (ERTS_IS_CRASH_DUMPING)
+        tbl->common.is_thread_safe = 1;
+
+    db_calc_stats_hash(&tbl->hash, &stats);
+
+    tbl->common.is_thread_safe = i;
+#else
+    db_calc_stats_hash(&tbl->hash, &stats);
+#endif
+
+    erts_print(to, to_arg, "Chain Length Avg: %f\n", stats.avg_chain_len);
+    erts_print(to, to_arg, "Chain Length Max: %d\n", stats.max_chain_len);
+    erts_print(to, to_arg, "Chain Length Min: %d\n", stats.min_chain_len);
+    erts_print(to, to_arg, "Chain Length Std Dev: %f\n",
+               stats.std_dev_chain_len);
+    erts_print(to, to_arg, "Chain Length Expected Std Dev: %f\n",
+               stats.std_dev_expected);
+
+    if (IS_FIXED(tb))
+        erts_print(to, to_arg, "Fixed: %d\n", stats.kept_items);
+    else
+        erts_print(to, to_arg, "Fixed: false\n");
+
     if (show) {
 	for (i = 0; i < NACTIVE(tb); i++) {
 	    HashDbTerm* list = BUCKET(tb,i);
@@ -2483,23 +2552,23 @@ static int free_seg(DbTableHash *tb, int free_records)
 ** Copy terms from ptr1 until ptr2
 ** works for ptr1 == ptr2 == 0  => []
 ** or ptr2 == 0
+** sz is either precalculated heap size or 0 if not known
 */
 static Eterm build_term_list(Process* p, HashDbTerm* ptr1, HashDbTerm* ptr2,
-			   DbTableHash* tb)
+			     Uint sz, DbTableHash* tb)
 {
-    int sz = 0;
     HashDbTerm* ptr;
     Eterm list = NIL;
     Eterm copy;
     Eterm *hp, *hend;
 
-    ptr = ptr1;
-    while(ptr != ptr2) {
-
-	if (ptr->hvalue != INVALID_HASH)
-	    sz += ptr->dbterm.size + 2;
-
-	ptr = ptr->next;
+    if (!sz) {
+	ptr = ptr1;
+	while(ptr != ptr2) {
+	    if (ptr->hvalue != INVALID_HASH)
+		sz += ptr->dbterm.size + 2;
+	    ptr = ptr->next;
+	}
     }
 
     hp = HAlloc(p, sz);
@@ -2730,59 +2799,129 @@ static HashDbTerm* next(DbTableHash *tb, Uint *iptr, erts_smp_rwmtx_t** lck_ptr,
     return NULL;
 }
 
-static int db_lookup_dbterm_hash(DbTable *tbl, Eterm key, DbUpdateHandle* handle)
+static int
+db_lookup_dbterm_hash(Process *p, DbTable *tbl, Eterm key, Eterm obj,
+                      DbUpdateHandle* handle)
 {
     DbTableHash *tb = &tbl->hash;
-    HashDbTerm* b;
-    HashDbTerm** prevp;
-    int ix;
     HashValue hval;
+    HashDbTerm **bp, *b;
     erts_smp_rwmtx_t* lck;
+    int flags = 0;
+
+    ASSERT(tb->common.status & DB_SET);
 
     hval = MAKE_HASH(key);
-    lck = WLOCK_HASH(tb,hval);
-    ix = hash_to_ix(tb, hval);
-    prevp = &BUCKET(tb, ix);
-    b = *prevp;
+    lck = WLOCK_HASH(tb, hval);
+    bp = &BUCKET(tb, hash_to_ix(tb, hval));
+    b = *bp;
 
-    while (b != 0) {
-	if (has_live_key(tb,b,key,hval)) {
-	    handle->tb = tbl;
-	    handle->bp = (void**) prevp;
-	    handle->dbterm = &b->dbterm;
-	    handle->mustResize = 0;
-	    handle->new_size = b->dbterm.size;
-	#if HALFWORD_HEAP
-	    handle->abs_vec = NULL;
-	#endif
-	    handle->lck = lck;
-	    /* KEEP hval WLOCKED, db_finalize_dbterm_hash will WUNLOCK */
-	    return 1;
-	}
-	prevp = &b->next;
-	b = *prevp;
+    for (;;) {
+        if (b == NULL) {
+            break;
+        }
+        if (has_key(tb, b, key, hval)) {
+            if (b->hvalue != INVALID_HASH) {
+                goto Ldone;
+            }
+            break;
+        }
+        bp = &b->next;
+        b = *bp;
     }
-    WUNLOCK_HASH(lck);
-    return 0;
+
+    if (obj == THE_NON_VALUE) {
+        WUNLOCK_HASH(lck);
+        return 0;
+    }
+
+    {
+        Eterm *objp = tuple_val(obj);
+        int arity = arityval(*objp);
+        Eterm *htop, *hend;
+
+        ASSERT(arity >= tb->common.keypos);
+        htop = HAlloc(p, arity + 1);
+        hend = htop + arity + 1;
+        sys_memcpy(htop, objp, sizeof(Eterm) * (arity + 1));
+        htop[tb->common.keypos] = key;
+        obj = make_tuple(htop);
+
+        if (b == NULL) {
+            HashDbTerm *q = new_dbterm(tb, obj);
+
+            q->hvalue = hval;
+            q->next = NULL;
+            *bp = b = q;
+
+            {
+                int nitems = erts_smp_atomic_inc_read_nob(&tb->common.nitems);
+                int nactive = NACTIVE(tb);
+
+                if (nitems > nactive * (CHAIN_LEN + 1) && !IS_FIXED(tb)) {
+                    grow(tb, nactive);
+                }
+            }
+        } else {
+            HashDbTerm *q, *next = b->next;
+
+            ASSERT(b->hvalue == INVALID_HASH);
+            q = replace_dbterm(tb, b, obj);
+            q->next = next;
+            q->hvalue = hval;
+            *bp = b = q;
+            erts_smp_atomic_inc_nob(&tb->common.nitems);
+        }
+
+        HRelease(p, hend, htop);
+        flags |= DB_NEW_OBJECT;
+    }
+
+Ldone:
+    handle->tb = tbl;
+    handle->bp = (void **)bp;
+    handle->dbterm = &b->dbterm;
+    handle->flags = flags;
+    handle->new_size = b->dbterm.size;
+#if HALFWORD_HEAP
+    handle->abs_vec = NULL;
+#endif
+    handle->lck = lck;
+    return 1;
 }
 
 /* Must be called after call to db_lookup_dbterm
 */
-static void db_finalize_dbterm_hash(DbUpdateHandle* handle)
+static void
+db_finalize_dbterm_hash(int cret, DbUpdateHandle* handle)
 {
     DbTable* tbl = handle->tb;
-    HashDbTerm* oldp = (HashDbTerm*) *(handle->bp);
+    DbTableHash *tb = &tbl->hash;
+    HashDbTerm **bp = (HashDbTerm **) handle->bp;
+    HashDbTerm *b = *bp;
     erts_smp_rwmtx_t* lck = (erts_smp_rwmtx_t*) handle->lck;
 
-    ERTS_SMP_LC_ASSERT(IS_HASH_WLOCKED(&tbl->hash,lck));  /* locked by db_lookup_dbterm_hash */
+    ERTS_SMP_LC_ASSERT(IS_HASH_WLOCKED(tb, lck));  /* locked by db_lookup_dbterm_hash */
 
-    ASSERT((&oldp->dbterm == handle->dbterm) == !(tbl->common.compress && handle->mustResize));
+    ASSERT((&b->dbterm == handle->dbterm) == !(tb->common.compress && handle->flags & DB_MUST_RESIZE));
+
+    if (handle->flags & DB_NEW_OBJECT && cret != DB_ERROR_NONE) {
+        if (IS_FIXED(tb)) {
+            add_fixed_deletion(tb, hash_to_ix(tb, b->hvalue));
+            b->hvalue = INVALID_HASH;
+        } else {
+            *bp = b->next;
+            free_term(tb, b);
+        }
 
-    if (handle->mustResize) {
+        WUNLOCK_HASH(lck);
+        erts_smp_atomic_dec_nob(&tb->common.nitems);
+        try_shrink(tb);
+    } else if (handle->flags & DB_MUST_RESIZE) {
 	db_finalize_resize(handle, offsetof(HashDbTerm,dbterm));
 	WUNLOCK_HASH(lck);
 
-	free_term(&tbl->hash, oldp);
+	free_term(tb, b);
     }
     else {
 	WUNLOCK_HASH(lck);
@@ -2833,6 +2972,7 @@ void db_calc_stats_hash(DbTableHash* tb, DbHashStats* stats)
     erts_smp_rwmtx_t* lck;
     int sum = 0;
     int sq_sum = 0;
+    int kept_items = 0;
     int ix;
     int len;
     
@@ -2844,6 +2984,8 @@ 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)
+                ++kept_items;
 	}
 	sum += len;
 	sq_sum += len*len;
@@ -2855,7 +2997,8 @@ void db_calc_stats_hash(DbTableHash* tb, DbHashStats* stats)
     stats->std_dev_chain_len = sqrt((sq_sum - stats->avg_chain_len*sum) / NACTIVE(tb));
     /* Expected	standard deviation from a good uniform hash function, 
        ie binomial distribution (not taking the linear hashing into acount) */
-    stats->std_dev_expected = sqrt(stats->avg_chain_len * (1 - 1.0/NACTIVE(tb)));	
+    stats->std_dev_expected = sqrt(stats->avg_chain_len * (1 - 1.0/NACTIVE(tb)));
+    stats->kept_items = kept_items;
 }
 #ifdef HARDDEBUG