aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--erts/emulator/beam/erl_process_dict.c158
-rw-r--r--lib/kernel/test/pdict_SUITE.erl32
2 files changed, 114 insertions, 76 deletions
diff --git a/erts/emulator/beam/erl_process_dict.c b/erts/emulator/beam/erl_process_dict.c
index 3c80f0e0f6..aee88841ae 100644
--- a/erts/emulator/beam/erl_process_dict.c
+++ b/erts/emulator/beam/erl_process_dict.c
@@ -79,6 +79,8 @@
/* Array access macro */
#define ARRAY_GET(PDict, Index) (ASSERT((Index) < (PDict)->arraySize), \
(PDict)->data[Index])
+#define ARRAY_GET_PTR(PDict, Index) (ASSERT((Index) < (PDict)->arraySize), \
+ &(PDict)->data[Index])
#define ARRAY_PUT(PDict, Index, Val) (ASSERT((Index) < (PDict)->arraySize), \
(PDict)->data[Index] = (Val))
@@ -92,7 +94,7 @@ static void pd_hash_erase_all(Process *p);
static Eterm pd_hash_get_with_hval(Process *p, Eterm bucket, Eterm id);
static Eterm pd_hash_get_keys(Process *p, Eterm value);
static Eterm pd_hash_get_all_keys(Process *p, ProcDict *pd);
-static Eterm pd_hash_get_all(Process *p, ProcDict *pd);
+static Eterm pd_hash_get_all(Process *p, ProcDict *pd, int keep_dict);
static Eterm pd_hash_put(Process *p, Eterm id, Eterm value);
static void shrink(Process *p, Eterm* ret);
@@ -281,7 +283,7 @@ BIF_RETTYPE get_0(BIF_ALIST_0)
{
Eterm ret;
PD_CHECK(BIF_P->dictionary);
- ret = pd_hash_get_all(BIF_P, BIF_P->dictionary);
+ ret = pd_hash_get_all(BIF_P, BIF_P->dictionary, 1);
PD_CHECK(BIF_P->dictionary);
BIF_RET(ret);
}
@@ -329,7 +331,7 @@ BIF_RETTYPE erase_0(BIF_ALIST_0)
{
Eterm ret;
PD_CHECK(BIF_P->dictionary);
- ret = pd_hash_get_all(BIF_P, BIF_P->dictionary);
+ ret = pd_hash_get_all(BIF_P, BIF_P->dictionary, 0);
pd_hash_erase_all(BIF_P);
PD_CHECK(BIF_P->dictionary);
BIF_RET(ret);
@@ -541,29 +543,46 @@ static Eterm pd_hash_get_keys(Process *p, Eterm value)
static Eterm
-pd_hash_get_all(Process *p, ProcDict *pd)
+pd_hash_get_all(Process *p, ProcDict *pd, int keep_dict)
{
Eterm* hp;
+ Eterm* tp;
Eterm res = NIL;
Eterm tmp, tmp2;
unsigned int i;
unsigned int num;
+ Uint need;
if (pd == NULL) {
return res;
}
num = HASH_RANGE(pd);
- hp = HAlloc(p, pd->numElements * 2);
-
+
+ /*
+ * If this is not erase/0, then must copy all key-value tuples
+ * as they may be mutated by put/2.
+ */
+ need = pd->numElements * (keep_dict ? 2+3 : 2);
+ hp = HAlloc(p, need);
+
for (i = 0; i < num; ++i) {
tmp = ARRAY_GET(pd, i);
if (is_boxed(tmp)) {
- ASSERT(is_tuple(tmp));
+ if (keep_dict) {
+ tp = tuple_val(tmp);
+ tmp = TUPLE2(hp, tp[1], tp[2]);
+ hp += 3;
+ }
res = CONS(hp, tmp, res);
hp += 2;
} else if (is_list(tmp)) {
while (tmp != NIL) {
tmp2 = TCAR(tmp);
+ if (keep_dict) {
+ tp = tuple_val(tmp2);
+ tmp2 = TUPLE2(hp, tp[1], tp[2]);
+ hp += 3;
+ }
res = CONS(hp, tmp2, res);
hp += 2;
tmp = TCDR(tmp);
@@ -577,11 +596,14 @@ static Eterm pd_hash_put(Process *p, Eterm id, Eterm value)
{
unsigned int hval;
Eterm *hp;
+ Eterm *tp;
+ Eterm *bucket;
Eterm tpl;
Eterm old;
+ Eterm old_val = am_undefined;
Eterm tmp;
int needed;
- int i = 0;
+ int new_key = 1;
#ifdef DEBUG
Eterm *hp_limit;
#endif
@@ -595,7 +617,8 @@ static Eterm pd_hash_put(Process *p, Eterm id, Eterm value)
p->dictionary->numElements = 0;
}
hval = pd_hash_value(p->dictionary, id);
- old = ARRAY_GET(p->dictionary, hval);
+ bucket = ARRAY_GET_PTR(p->dictionary, hval);
+ old = *bucket;
/*
* Calculate the number of heap words needed and garbage
@@ -603,32 +626,49 @@ static Eterm pd_hash_put(Process *p, Eterm id, Eterm value)
*/
needed = 3; /* {Key,Value} tuple */
if (is_boxed(old)) {
- /*
- * We don't want to compare keys twice, so we'll always
- * reserve the space for two CONS cells.
- */
- needed += 2+2;
+ ASSERT(is_tuple(old));
+ tp = tuple_val(old);
+ if (EQ(tp[1], id)) {
+ old_val = tp[2];
+ if (is_immed(value)) {
+ tp[2] = value; /* DESTRUCTIVE HEAP ASSIGNMENT */
+ return old_val;
+ }
+ new_key = 0;
+ }
+ else {
+ needed += 2+2;
+ }
} else if (is_list(old)) {
- i = 0;
- for (tmp = old; tmp != NIL && !EQ(tuple_val(TCAR(tmp))[1], id); tmp = TCDR(tmp)) {
- ++i;
- }
- if (is_nil(tmp)) {
- i = -1;
- needed += 2;
- } else {
- needed += 2*(i+1);
+ Eterm* prev_cdr = bucket;
+
+ needed += 2;
+ for (tmp = old; tmp != NIL; prev_cdr = &TCDR(tmp), tmp = *prev_cdr) {
+ tp = tuple_val(TCAR(tmp));
+ if (EQ(tp[1], id)) {
+ old_val = tp[2];
+ if (is_immed(value)) {
+ tp[2] = value; /* DESTRUCTIVE HEAP ASSIGNMENT */
+ return old_val;
+ }
+ new_key = 0;
+ /* Unlink old {Key,Value} from list */
+ *prev_cdr = TCDR(tmp); /* maybe DESTRUCTIVE HEAP ASSIGNMENT */
+ break;
+ }
}
}
if (HeapWordsLeft(p) < needed) {
Eterm root[3];
root[0] = id;
root[1] = value;
- root[2] = old;
+ root[2] = old_val;
erts_garbage_collect(p, needed, root, 3);
id = root[0];
value = root[1];
- old = root[2];
+ old_val = root[2];
+ ASSERT(bucket == ARRAY_GET_PTR(p->dictionary, hval));
+ old = *bucket;
}
#ifdef DEBUG
hp_limit = p->htop + needed;
@@ -644,66 +684,29 @@ static Eterm pd_hash_put(Process *p, Eterm id, Eterm value)
* Update the dictionary.
*/
if (is_nil(old)) {
- ARRAY_PUT(p->dictionary, hval, tpl);
- ++(p->dictionary->numElements);
+ *bucket = tpl;
} else if (is_boxed(old)) {
ASSERT(is_tuple(old));
- if (EQ(tuple_val(old)[1],id)) {
- ARRAY_PUT(p->dictionary, hval, tpl);
- return tuple_val(old)[2];
+ if (!new_key) {
+ ASSERT(EQ(tuple_val(old)[1],id));
+ *bucket = tpl;
+ return old_val;
} else {
hp = HeapOnlyAlloc(p, 4);
tmp = CONS(hp, old, NIL);
hp += 2;
- ++(p->dictionary->numElements);
- ARRAY_PUT(p->dictionary, hval, CONS(hp, tpl, tmp));
+ *bucket = CONS(hp, tpl, tmp);
hp += 2;
ASSERT(hp <= hp_limit);
}
} else if (is_list(old)) {
- if (i == -1) {
- /*
- * New key. Simply prepend the tuple to the beginning of the list.
- */
- hp = HeapOnlyAlloc(p, 2);
- ARRAY_PUT(p->dictionary, hval, CONS(hp, tpl, old));
- hp += 2;
- ASSERT(hp <= hp_limit);
- ++(p->dictionary->numElements);
- } else {
- /*
- * i = Number of CDRs to skip to reach the changed element in the list.
- *
- * Replace old value in list. To avoid pointers from the old generation
- * to the new, we must rebuild the list from the beginning up to and
- * including the changed element.
- */
- Eterm nlist;
- int j;
-
- hp = HeapOnlyAlloc(p, (i+1)*2);
-
- /* Find the list element to change. */
- for (j = 0, nlist = old; j < i; j++, nlist = TCDR(nlist)) {
- ;
- }
- ASSERT(EQ(tuple_val(TCAR(nlist))[1], id));
- nlist = TCDR(nlist); /* Unchanged part of list. */
-
- /* Rebuild list before the updated element. */
- for (tmp = old; i-- > 0; tmp = TCDR(tmp)) {
- nlist = CONS(hp, TCAR(tmp), nlist);
- hp += 2;
- }
- ASSERT(EQ(tuple_val(TCAR(tmp))[1], id));
-
- /* Put the updated element first in the new list. */
- nlist = CONS(hp, tpl, nlist);
- hp += 2;
- ASSERT(hp <= hp_limit);
- ARRAY_PUT(p->dictionary, hval, nlist);
- return tuple_val(TCAR(tmp))[2];
- }
+ /*
+ * Simply prepend the tuple to the beginning of the list.
+ */
+ hp = HeapOnlyAlloc(p, 2);
+ *bucket = CONS(hp, tpl, *bucket);
+ hp += 2;
+ ASSERT(hp <= hp_limit);
} else {
#ifdef DEBUG
erts_fprintf(stderr,
@@ -714,10 +717,13 @@ static Eterm pd_hash_put(Process *p, Eterm id, Eterm value)
erts_exit(ERTS_ERROR_EXIT, "Damaged process dictionary found during put/2.");
}
+
+ p->dictionary->numElements += new_key;
+
if (HASH_RANGE(p->dictionary) <= p->dictionary->numElements) {
grow(p);
}
- return am_undefined;
+ return old_val;
}
/*
diff --git a/lib/kernel/test/pdict_SUITE.erl b/lib/kernel/test/pdict_SUITE.erl
index d105952df9..a891451c82 100644
--- a/lib/kernel/test/pdict_SUITE.erl
+++ b/lib/kernel/test/pdict_SUITE.erl
@@ -33,6 +33,7 @@
init_per_group/2,end_per_group/2,
mixed/1,
literals/1,
+ destructive/1,
simple/1, complicated/1, heavy/1, simple_all_keys/1, info/1]).
-export([init_per_testcase/2, end_per_testcase/2]).
-export([other_process/2]).
@@ -52,6 +53,7 @@ suite() ->
all() ->
[simple, complicated, heavy, simple_all_keys, info,
literals,
+ destructive,
mixed].
groups() ->
@@ -367,6 +369,36 @@ match_keys(All) ->
ok.
+%% Test destructive put optimization of immed values
+%% does not affect get/0 or process_info.
+destructive(_Config) ->
+ Keys = lists:seq(1,100),
+ [put(Key, 17) || Key <- Keys],
+ Get1 = get(),
+ {dictionary,PI1} = process_info(self(), dictionary),
+
+ [begin
+ {Key, 17} = lists:keyfind(Key, 1, Get1),
+ {Key, 17} = lists:keyfind(Key, 1, PI1)
+ end
+ || Key <- Keys],
+
+ [17 = put(Key, 42) || Key <- Keys], % Mutate
+
+ Get2 = get(),
+ {dictionary,PI2} = process_info(self(), dictionary),
+
+ [begin
+ {Key, 17} = lists:keyfind(Key, 1, Get1),
+ {Key, 17} = lists:keyfind(Key, 1, PI1),
+ {Key, 42} = lists:keyfind(Key, 1, Get2),
+ {Key, 42} = lists:keyfind(Key, 1, PI2)
+
+ end
+ || Key <- Keys],
+
+ ok.
+
%% Do random mixed put/erase to test grow/shrink
%% Written for a temporary bug in gc during shrink
mixed(_Config) ->
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-16 21:22:55 +0000