aboutsummaryrefslogtreecommitdiffstats
path: root/erts/emulator/beam/erl_process_dict.c
diff options
context:
space:
mode:
Diffstat (limited to 'erts/emulator/beam/erl_process_dict.c')
-rw-r--r--erts/emulator/beam/erl_process_dict.c1001
1 files changed, 1001 insertions, 0 deletions
diff --git a/erts/emulator/beam/erl_process_dict.c b/erts/emulator/beam/erl_process_dict.c
new file mode 100644
index 0000000000..93466da3aa
--- /dev/null
+++ b/erts/emulator/beam/erl_process_dict.c
@@ -0,0 +1,1001 @@
+/*
+ * %CopyrightBegin%
+ *
+ * Copyright Ericsson AB 1999-2009. All Rights Reserved.
+ *
+ * The contents of this file are subject to the Erlang Public License,
+ * Version 1.1, (the "License"); you may not use this file except in
+ * compliance with the License. You should have received a copy of the
+ * Erlang Public License along with this software. If not, it can be
+ * retrieved online at http://www.erlang.org/.
+ *
+ * Software distributed under the License is distributed on an "AS IS"
+ * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See
+ * the License for the specific language governing rights and limitations
+ * under the License.
+ *
+ * %CopyrightEnd%
+ */
+
+/*
+ * Code for process dictionaries.
+ *
+ */
+#ifdef HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include "sys.h"
+#include "erl_vm.h"
+#include "global.h"
+#include "erl_process.h" /* Will include erl_process_dict.h */
+#include "error.h"
+#include "erl_driver.h"
+#include "bif.h"
+#include "big.h"
+#include "dist.h"
+#include "erl_version.h"
+
+/* #define HARDDEBUG */
+
+/*
+** Utility macros
+*/
+
+/* Flags to pd_get_hash */
+#define PD_GET_OTHER_PROCESS 1UL
+
+/* Hash constant macros */
+#define MAX_HASH 1342177280UL
+#define INITIAL_SIZE 10
+
+/* Hash utility macros */
+#define HASH_RANGE(PDict) ((PDict)->homeSize + (PDict)->splitPosition)
+
+#define MAKE_HASH(Term) \
+((is_small(Term)) ? unsigned_val(Term) : \
+ ((is_atom(Term)) ? \
+ (atom_tab(atom_val(term))->slot.bucket.hvalue) : \
+ make_hash2(Term)))
+
+#define PD_SZ2BYTES(Sz) (sizeof(ProcDict) + ((Sz) - 1)*sizeof(Eterm))
+
+/* Memory allocation macros */
+#define PD_ALLOC(Sz) \
+ erts_alloc(ERTS_ALC_T_PROC_DICT, (Sz))
+#define PD_FREE(P, Sz) \
+ erts_free(ERTS_ALC_T_PROC_DICT, (P))
+#define PD_REALLOC(P, OSz, NSz) \
+ erts_realloc(ERTS_ALC_T_PROC_DICT, (P), (NSz))
+
+
+#define TCAR(Term) CAR(list_val(Term))
+#define TCDR(Term) CDR(list_val(Term))
+
+/* Array access macro */
+#define ARRAY_GET(PDict, Index) (((PDict)->size > (Index)) ? \
+ (PDict)->data[Index] : NIL)
+
+/*
+ * Forward decalarations
+ */
+static void pd_hash_erase(Process *p, Eterm id, Eterm *ret);
+static void pd_hash_erase_all(Process *p);
+static Eterm pd_hash_get_keys(Process *p, Eterm value);
+static Eterm pd_hash_get_all(Process *p, ProcDict *pd);
+static Eterm pd_hash_put(Process *p, Eterm id, Eterm value);
+
+static void shrink(Process *p, Eterm* ret);
+static void grow(Process *p);
+
+static void array_shrink(ProcDict **ppd, unsigned int need);
+static Eterm array_put(ProcDict **ppdict, unsigned int ndx, Eterm term);
+
+static unsigned int pd_hash_value(ProcDict *pdict, Eterm term);
+static unsigned int next_array_size(unsigned int need);
+
+/*
+** Debugging prototypes and macros
+*/
+#ifdef HARDDEBUG
+
+#include <stdarg.h>
+
+static int hdebugf(char *format, ...);
+static char *hdebugf_file = "";
+static int hdebugf_line;
+#define HDEBUGF(X) ((int) hdebugf_file = __FILE__, hdebugf_line = __LINE__, \
+ hdebugf X)
+#ifndef DEBUG
+#define DEBUG 1
+#endif
+
+#else /* !HARDDEBUG */
+
+#define HDEBUGF(X) /* Nothing */
+
+#endif /* HARDDEBUG (else) */
+
+#ifdef DEBUG
+
+static void pd_check(ProcDict *pd);
+
+#define PD_CHECK(PD) pd_check(PD)
+
+#else /* !DEBUG */
+
+#define PD_CHECK(PD) /* Nothing */
+
+#endif /* DEBUG (else) */
+
+/*
+** External interface
+*/
+
+/*
+ * Called from break handler
+ */
+void
+erts_dictionary_dump(int to, void *to_arg, ProcDict *pd)
+{
+ unsigned int i;
+#ifdef DEBUG
+
+ /*PD_CHECK(pd);*/
+ if (pd == NULL)
+ return;
+ erts_print(to, to_arg, "(size = %d, used = %d, homeSize = %d, "
+ "splitPosition = %d, numElements = %d)\n",
+ pd->size, pd->used, pd->homeSize,
+ pd->splitPosition, (unsigned int) pd->numElements);
+ for (i = 0; i < HASH_RANGE(pd); ++i) {
+ erts_print(to, to_arg, "%d: %T\n", i, ARRAY_GET(pd, i));
+ }
+
+#else /* !DEBUG */
+
+ int written = 0;
+ Eterm t;
+
+ erts_print(to, to_arg, "[");
+ if (pd != NULL) {
+ for (i = 0; i < HASH_RANGE(pd); ++i) {
+ t = ARRAY_GET(pd, i);
+ if (is_list(t)) {
+ for (; t != NIL; t = TCDR(t)) {
+ erts_print(to, to_arg, written++ ? ",%T" : "%T", TCAR(t));
+ }
+ } else if (is_tuple(t)) {
+ erts_print(to, to_arg, written++ ? ",%T" : "%T", t);
+ }
+ }
+ }
+ erts_print(to, to_arg, "]");
+
+#endif /* DEBUG (else) */
+}
+
+void
+erts_deep_dictionary_dump(int to, void *to_arg,
+ ProcDict* pd, void (*cb)(int, void *, Eterm))
+{
+ unsigned int i;
+ Eterm t;
+
+ if (pd != NULL) {
+ for (i = 0; i < HASH_RANGE(pd); ++i) {
+ t = ARRAY_GET(pd, i);
+ if (is_list(t)) {
+ for (; t != NIL; t = TCDR(t)) {
+ (*cb)(to, to_arg, TCAR(t));
+ }
+ } else if (is_tuple(t)) {
+ (*cb)(to, to_arg, t);
+ }
+ }
+ }
+}
+
+Uint
+erts_dicts_mem_size(Process *p)
+{
+ Uint size = 0;
+ if (p->dictionary)
+ size += PD_SZ2BYTES(p->dictionary->size);
+ return size;
+}
+
+void
+erts_erase_dicts(Process *p)
+{
+ if (p->dictionary) {
+ pd_hash_erase_all(p);
+ p->dictionary = NULL;
+ }
+}
+
+/*
+ * Called from process_info/1,2.
+ */
+Eterm erts_dictionary_copy(Process *p, ProcDict *pd)
+{
+ Eterm* hp;
+ Eterm* heap_start;
+ Eterm res = NIL;
+ Eterm tmp, tmp2;
+ unsigned int i, num;
+
+ if (pd == NULL) {
+ return res;
+ }
+
+ PD_CHECK(pd);
+ num = HASH_RANGE(pd);
+ heap_start = hp = (Eterm *) erts_alloc(ERTS_ALC_T_TMP,
+ sizeof(Eterm) * pd->numElements * 2);
+ for (i = 0; i < num; ++i) {
+ tmp = ARRAY_GET(pd, i);
+ if (is_boxed(tmp)) {
+ ASSERT(is_tuple(tmp));
+ res = CONS(hp, tmp, res);
+ hp += 2;
+ } else if (is_list(tmp)) {
+ while (tmp != NIL) {
+ tmp2 = TCAR(tmp);
+ res = CONS(hp, tmp2, res);
+ hp += 2;
+ tmp = TCDR(tmp);
+ }
+ }
+ }
+ res = copy_object(res, p);
+ erts_free(ERTS_ALC_T_TMP, (void *) heap_start);
+ return res;
+}
+
+
+/*
+** BIF interface
+*/
+BIF_RETTYPE get_0(BIF_ALIST_0)
+{
+ Eterm ret;
+ PD_CHECK(BIF_P->dictionary);
+ ret = pd_hash_get_all(BIF_P, BIF_P->dictionary);
+ PD_CHECK(BIF_P->dictionary);
+ BIF_RET(ret);
+}
+
+BIF_RETTYPE get_1(BIF_ALIST_1)
+{
+ Eterm ret;
+ PD_CHECK(BIF_P->dictionary);
+ ret = erts_pd_hash_get(BIF_P, BIF_ARG_1);
+ PD_CHECK(BIF_P->dictionary);
+ BIF_RET(ret);
+}
+
+BIF_RETTYPE get_keys_1(BIF_ALIST_1)
+{
+ Eterm ret;
+
+ PD_CHECK(BIF_P->dictionary);
+ ret = pd_hash_get_keys(BIF_P, BIF_ARG_1);
+ PD_CHECK(BIF_P->dictionary);
+ BIF_RET(ret);
+}
+
+BIF_RETTYPE put_2(BIF_ALIST_2)
+{
+ Eterm ret;
+
+ PD_CHECK(BIF_P->dictionary);
+ ret = pd_hash_put(BIF_P, BIF_ARG_1, BIF_ARG_2);
+ PD_CHECK(BIF_P->dictionary);
+ BIF_RET(ret);
+}
+
+BIF_RETTYPE erase_0(BIF_ALIST_0)
+{
+ Eterm ret;
+ PD_CHECK(BIF_P->dictionary);
+ ret = pd_hash_get_all(BIF_P, BIF_P->dictionary);
+ pd_hash_erase_all(BIF_P);
+ PD_CHECK(BIF_P->dictionary);
+ BIF_RET(ret);
+}
+
+BIF_RETTYPE erase_1(BIF_ALIST_1)
+{
+ Eterm ret;
+ PD_CHECK(BIF_P->dictionary);
+ pd_hash_erase(BIF_P, BIF_ARG_1, &ret);
+ PD_CHECK(BIF_P->dictionary);
+ BIF_RET(ret);
+}
+
+/*
+ * BIF implementations
+ */
+static void pd_hash_erase(Process *p, Eterm id, Eterm *ret)
+{
+ unsigned int hval;
+ Eterm old;
+ Eterm tmp;
+ unsigned int range;
+
+ *ret = am_undefined;
+ if (p->dictionary == NULL) {
+ return;
+ }
+ hval = pd_hash_value(p->dictionary, id);
+ old = ARRAY_GET(p->dictionary, hval);
+ if (is_boxed(old)) { /* Tuple */
+ ASSERT(is_tuple(old));
+ if (EQ(tuple_val(old)[1], id)) {
+ array_put(&(p->dictionary), hval, NIL);
+ --(p->dictionary->numElements);
+ *ret = tuple_val(old)[2];
+ }
+ } else if (is_list(old)) {
+ /* Find cons cell for identical value */
+ Eterm* prev = &p->dictionary->data[hval];
+
+ for (tmp = *prev; tmp != NIL; prev = &TCDR(tmp), tmp = *prev) {
+ if (EQ(tuple_val(TCAR(tmp))[1], id)) {
+ *prev = TCDR(tmp);
+ *ret = tuple_val(TCAR(tmp))[2];
+ --(p->dictionary->numElements);
+ }
+ }
+
+ /* If there is only one element left in the list we must remove the list. */
+ old = ARRAY_GET(p->dictionary, hval);
+ ASSERT(is_list(old));
+ if (is_nil(TCDR(old))) {
+ array_put(&p->dictionary, hval, TCAR(old));
+ }
+ } else if (is_not_nil(old)) {
+#ifdef DEBUG
+ erts_fprintf(stderr,
+ "Process dictionary for process %T is broken, trying to "
+ "display term found in line %d:\n"
+ "%T\n", p->id, __LINE__, old);
+#endif
+ erl_exit(1, "Damaged process dictionary found during erase/1.");
+ }
+ if ((range = HASH_RANGE(p->dictionary)) > INITIAL_SIZE &&
+ range / 2 > (p->dictionary->numElements)) {
+ shrink(p, ret);
+ }
+}
+
+static void pd_hash_erase_all(Process *p)
+{
+ if (p->dictionary != NULL) {
+ PD_FREE(p->dictionary, PD_SZ2BYTES(p->dictionary->size));
+ p->dictionary = NULL;
+ }
+}
+
+Eterm erts_pd_hash_get(Process *p, Eterm id)
+{
+ unsigned int hval;
+ Eterm tmp;
+ ProcDict *pd = p->dictionary;
+
+ if (pd == NULL)
+ return am_undefined;
+ hval = pd_hash_value(pd, id);
+ tmp = ARRAY_GET(pd, hval);
+ if (is_boxed(tmp)) { /* Tuple */
+ ASSERT(is_tuple(tmp));
+ if (EQ(tuple_val(tmp)[1], id)) {
+ return tuple_val(tmp)[2];
+ }
+ } else if (is_list(tmp)) {
+ for (; tmp != NIL && !EQ(tuple_val(TCAR(tmp))[1], id); tmp = TCDR(tmp)) {
+ ;
+ }
+ if (tmp != NIL) {
+ return tuple_val(TCAR(tmp))[2];
+ }
+ } else if (is_not_nil(tmp)) {
+#ifdef DEBUG
+ erts_fprintf(stderr,
+ "Process dictionary for process %T is broken, trying to "
+ "display term found in line %d:\n"
+ "%T\n", p->id, __LINE__, tmp);
+#endif
+ erl_exit(1, "Damaged process dictionary found during get/1.");
+ }
+ return am_undefined;
+}
+
+static Eterm pd_hash_get_keys(Process *p, Eterm value)
+{
+ Eterm *hp;
+ Eterm res = NIL;
+ ProcDict *pd = p->dictionary;
+ unsigned int i, num;
+ Eterm tmp, tmp2;
+
+ if (pd == NULL) {
+ return res;
+ }
+
+ num = HASH_RANGE(pd);
+ for (i = 0; i < num; ++i) {
+ tmp = ARRAY_GET(pd, i);
+ if (is_boxed(tmp)) {
+ ASSERT(is_tuple(tmp));
+ if (EQ(tuple_val(tmp)[2], value)) {
+ hp = HAlloc(p, 2);
+ res = CONS(hp, tuple_val(tmp)[1], res);
+ }
+ } else if (is_list(tmp)) {
+ while (tmp != NIL) {
+ tmp2 = TCAR(tmp);
+ if (EQ(tuple_val(tmp2)[2], value)) {
+ hp = HAlloc(p, 2);
+ res = CONS(hp, tuple_val(tmp2)[1], res);
+ }
+ tmp = TCDR(tmp);
+ }
+ }
+ }
+ return res;
+}
+
+
+static Eterm
+pd_hash_get_all(Process *p, ProcDict *pd)
+{
+ Eterm* hp;
+ Eterm res = NIL;
+ Eterm tmp, tmp2;
+ unsigned int i;
+ unsigned int num;
+
+ if (pd == NULL) {
+ return res;
+ }
+ num = HASH_RANGE(pd);
+ hp = HAlloc(p, pd->numElements * 2);
+
+ for (i = 0; i < num; ++i) {
+ tmp = ARRAY_GET(pd, i);
+ if (is_boxed(tmp)) {
+ ASSERT(is_tuple(tmp));
+ res = CONS(hp, tmp, res);
+ hp += 2;
+ } else if (is_list(tmp)) {
+ while (tmp != NIL) {
+ tmp2 = TCAR(tmp);
+ res = CONS(hp, tmp2, res);
+ hp += 2;
+ tmp = TCDR(tmp);
+ }
+ }
+ }
+ return res;
+}
+
+static Eterm pd_hash_put(Process *p, Eterm id, Eterm value)
+{
+ unsigned int hval;
+ Eterm *hp;
+ Eterm tpl;
+ Eterm old;
+ Eterm tmp;
+ int needed;
+ int i = 0;
+#ifdef DEBUG
+ Eterm *hp_limit;
+#endif
+
+ if (p->dictionary == NULL) {
+ /* Create it */
+ array_put(&(p->dictionary), INITIAL_SIZE - 1, NIL);
+ p->dictionary->homeSize = INITIAL_SIZE;
+ }
+ hval = pd_hash_value(p->dictionary, id);
+ old = ARRAY_GET(p->dictionary, hval);
+
+ /*
+ * Calculate the number of heap words needed and garbage
+ * collect if necessary. (Might be a slight overestimation.)
+ */
+ 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;
+ } 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);
+ }
+ }
+ if (HeapWordsLeft(p) < needed) {
+ Eterm root[3];
+ root[0] = id;
+ root[1] = value;
+ root[2] = old;
+ BUMP_REDS(p, erts_garbage_collect(p, needed, root, 3));
+ id = root[0];
+ value = root[1];
+ old = root[2];
+ }
+#ifdef DEBUG
+ hp_limit = p->htop + needed;
+#endif
+
+ /*
+ * Create the {Key,Value} tuple.
+ */
+ hp = HeapOnlyAlloc(p, 3);
+ tpl = TUPLE2(hp, id, value);
+
+ /*
+ * Update the dictionary.
+ */
+ if (is_nil(old)) {
+ array_put(&(p->dictionary), hval, tpl);
+ ++(p->dictionary->numElements);
+ } 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];
+ } else {
+ hp = HeapOnlyAlloc(p, 4);
+ tmp = CONS(hp, old, NIL);
+ hp += 2;
+ ++(p->dictionary->numElements);
+ array_put(&(p->dictionary), hval, 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];
+ }
+ } else {
+#ifdef DEBUG
+ erts_fprintf(stderr,
+ "Process dictionary for process %T is broken, trying to "
+ "display term found in line %d:\n"
+ "%T\n", p->id, __LINE__, old);
+#endif
+
+ erl_exit(1, "Damaged process dictionary found during put/2.");
+ }
+ if (HASH_RANGE(p->dictionary) <= p->dictionary->numElements) {
+ grow(p);
+ }
+ return am_undefined;
+}
+
+/*
+ * Hash table utilities, rehashing
+ */
+
+static void shrink(Process *p, Eterm* ret)
+{
+ unsigned int range = HASH_RANGE(p->dictionary);
+ unsigned int steps = (range*3) / 10;
+ Eterm hi, lo, tmp;
+ unsigned int i;
+ Eterm *hp;
+#ifdef DEBUG
+ Eterm *hp_limit;
+#endif
+
+ if (range - steps < INITIAL_SIZE) {
+ steps = range - INITIAL_SIZE;
+ }
+
+ for (i = 0; i < steps; ++i) {
+ ProcDict *pd = p->dictionary;
+ if (pd->splitPosition == 0) {
+ pd->homeSize /= 2;
+ pd->splitPosition = pd->homeSize;
+ }
+ --(pd->splitPosition);
+ hi = ARRAY_GET(pd, (pd->splitPosition + pd->homeSize));
+ lo = ARRAY_GET(pd, pd->splitPosition);
+ if (hi != NIL) {
+ if (lo == NIL) {
+ array_put(&(p->dictionary), pd->splitPosition, hi);
+ } else {
+ int needed = 4;
+ if (is_list(hi) && is_list(lo)) {
+ needed = 2*list_length(hi);
+ }
+ if (HeapWordsLeft(p) < needed) {
+ BUMP_REDS(p, erts_garbage_collect(p, needed, ret, 1));
+ hi = pd->data[(pd->splitPosition + pd->homeSize)];
+ lo = pd->data[pd->splitPosition];
+ }
+#ifdef DEBUG
+ hp_limit = p->htop + needed;
+#endif
+ if (is_tuple(lo)) {
+ if (is_tuple(hi)) {
+ hp = HeapOnlyAlloc(p, 4);
+ tmp = CONS(hp, hi, NIL);
+ hp += 2;
+ array_put(&(p->dictionary), pd->splitPosition,
+ CONS(hp,lo,tmp));
+ hp += 2;
+ ASSERT(hp <= hp_limit);
+ } else { /* hi is a list */
+ hp = HeapOnlyAlloc(p, 2);
+ array_put(&(p->dictionary), pd->splitPosition,
+ CONS(hp, lo, hi));
+ hp += 2;
+ ASSERT(hp <= hp_limit);
+ }
+ } else { /* lo is a list */
+ if (is_tuple(hi)) {
+ hp = HeapOnlyAlloc(p, 2);
+ array_put(&(p->dictionary), pd->splitPosition,
+ CONS(hp, hi, lo));
+ hp += 2;
+ ASSERT(hp <= hp_limit);
+
+ } else { /* Two lists */
+ hp = HeapOnlyAlloc(p, needed);
+ for (tmp = hi; tmp != NIL; tmp = TCDR(tmp)) {
+ lo = CONS(hp, TCAR(tmp), lo);
+ hp += 2;
+ }
+ ASSERT(hp <= hp_limit);
+ array_put(&(p->dictionary), pd->splitPosition, lo);
+ }
+ }
+ }
+ }
+ array_put(&(p->dictionary), (pd->splitPosition + pd->homeSize), NIL);
+ }
+ if (HASH_RANGE(p->dictionary) <= (p->dictionary->size / 4)) {
+ array_shrink(&(p->dictionary), (HASH_RANGE(p->dictionary) * 3) / 2);
+ }
+}
+
+static void grow(Process *p)
+{
+ unsigned int i,j;
+ unsigned int steps = p->dictionary->homeSize / 5;
+ Eterm l1,l2;
+ Eterm l;
+ Eterm *hp;
+ unsigned int pos;
+ unsigned int homeSize;
+ int needed = 0;
+ ProcDict *pd;
+#ifdef DEBUG
+ Eterm *hp_limit;
+#endif
+
+ HDEBUGF(("grow: steps = %d", steps));
+ if (steps == 0)
+ steps = 1;
+ /* Dont grow over MAX_HASH */
+ if ((MAX_HASH - steps) <= HASH_RANGE(p->dictionary)) {
+ return;
+ }
+
+ /*
+ * Calculate total number of heap words needed, and garbage collect
+ * if necessary.
+ */
+
+ pd = p->dictionary;
+ pos = pd->splitPosition;
+ homeSize = pd->homeSize;
+ for (i = 0; i < steps; ++i) {
+ if (pos == homeSize) {
+ homeSize *= 2;
+ pos = 0;
+ }
+ l = ARRAY_GET(pd, pos);
+ pos++;
+ if (is_not_tuple(l)) {
+ while (l != NIL) {
+ needed += 2;
+ l = TCDR(l);
+ }
+ }
+ }
+ if (HeapWordsLeft(p) < needed) {
+ BUMP_REDS(p, erts_garbage_collect(p, needed, 0, 0));
+ }
+#ifdef DEBUG
+ hp_limit = p->htop + needed;
+#endif
+
+ /*
+ * Now grow.
+ */
+
+ for (i = 0; i < steps; ++i) {
+ ProcDict *pd = p->dictionary;
+ if (pd->splitPosition == pd->homeSize) {
+ pd->homeSize *= 2;
+ pd->splitPosition = 0;
+ }
+ pos = pd->splitPosition;
+ ++pd->splitPosition; /* For the hashes */
+ l = ARRAY_GET(pd, pos);
+ if (is_tuple(l)) {
+ if (pd_hash_value(pd, tuple_val(l)[1]) != pos) {
+ array_put(&(p->dictionary), pos +
+ p->dictionary->homeSize, l);
+ array_put(&(p->dictionary), pos, NIL);
+ }
+ } else {
+ l2 = NIL;
+ l1 = l;
+ for (j = 0; l1 != NIL; l1 = TCDR(l1))
+ j += 2;
+ hp = HeapOnlyAlloc(p, j);
+
+ while (l != NIL) {
+ if (pd_hash_value(pd, tuple_val(TCAR(l))[1]) == pos)
+ l1 = CONS(hp, TCAR(l), l1);
+ else
+ l2 = CONS(hp, TCAR(l), l2);
+ hp += 2;
+ l = TCDR(l);
+ }
+ if (l1 != NIL && TCDR(l1) == NIL)
+ l1 = TCAR(l1);
+ if (l2 != NIL && TCDR(l2) == NIL)
+ l2 = TCAR(l2);
+ ASSERT(hp <= hp_limit);
+ /* After array_put pd is no longer valid */
+ array_put(&(p->dictionary), pos, l1);
+ array_put(&(p->dictionary), pos +
+ p->dictionary->homeSize, l2);
+ }
+ }
+
+#ifdef HARDDEBUG
+ dictionary_dump(p->dictionary,CERR);
+#endif
+}
+
+/*
+** Array oriented operations
+*/
+
+static void array_shrink(ProcDict **ppd, unsigned int need)
+{
+ unsigned int siz = next_array_size(need);
+
+ HDEBUGF(("array_shrink: size = %d, used = %d, need = %d",
+ (*ppd)->size, (*ppd)->used, need));
+
+ if (siz > (*ppd)->size)
+ return; /* Only shrink */
+
+ *ppd = PD_REALLOC(((void *) *ppd),
+ PD_SZ2BYTES((*ppd)->size),
+ PD_SZ2BYTES(siz));
+
+ (*ppd)->size = siz;
+ if ((*ppd)->size < (*ppd)->used)
+ (*ppd)->used = (*ppd)->size;
+}
+
+
+static Eterm array_put(ProcDict **ppdict, unsigned int ndx, Eterm term)
+{
+ unsigned int i;
+ Eterm ret;
+ if (*ppdict == NULL) {
+ Uint siz = next_array_size(ndx+1);
+ ProcDict *p;
+
+ p = PD_ALLOC(PD_SZ2BYTES(siz));
+ for (i = 0; i < siz; ++i)
+ p->data[i] = NIL;
+ p->size = siz;
+ p->homeSize = p->splitPosition = p->numElements = p->used = 0;
+ *ppdict = p;
+ } else if (ndx >= (*ppdict)->size) {
+ Uint osize = (*ppdict)->size;
+ Uint nsize = next_array_size(ndx+1);
+ *ppdict = PD_REALLOC(((void *) *ppdict),
+ PD_SZ2BYTES(osize),
+ PD_SZ2BYTES(nsize));
+ for (i = osize; i < nsize; ++i)
+ (*ppdict)->data[i] = NIL;
+ (*ppdict)->size = nsize;
+ }
+ ret = (*ppdict)->data[ndx];
+ (*ppdict)->data[ndx] = term;
+ if ((ndx + 1) > (*ppdict)->used)
+ (*ppdict)->used = ndx + 1;
+#ifdef HARDDEBUG
+ HDEBUGF(("array_put: (*ppdict)->size = %d, (*ppdict)->used = %d, ndx = %d",
+ (*ppdict)->size, (*ppdict)->used, ndx));
+ erts_fprintf(stderr, "%T", term);
+#endif /* HARDDEBUG */
+ return ret;
+}
+
+/*
+** Basic utilities
+*/
+
+static unsigned int pd_hash_value(ProcDict *pdict, Eterm term)
+{
+ Uint hash, high;
+
+ hash = MAKE_HASH(term);
+ high = hash % (pdict->homeSize*2);
+ if (high >= HASH_RANGE(pdict))
+ return hash % pdict->homeSize;
+ return high;
+}
+
+static unsigned int next_array_size(unsigned int need)
+{
+ static unsigned int tab[] =
+ {
+ 10UL,
+ 20UL,
+ 40UL,
+ 80UL,
+ 160UL,
+ 320UL,
+ 640UL,
+ 1280UL,
+ 2560UL,
+ 5120UL,
+ 10240UL,
+ 20480UL,
+ 40960UL,
+ 81920UL,
+ 163840UL,
+ 327680UL,
+ 655360UL,
+ 1310720UL,
+ 2621440UL,
+ 5242880UL,
+ 10485760UL,
+ 20971520UL,
+ 41943040UL,
+ 83886080UL,
+ 167772160UL,
+ 335544320UL,
+ 671088640UL,
+ 1342177280UL,
+ 2684354560UL
+ };
+ int hi = sizeof(tab) / sizeof(Uint) - 1;
+ int lo = 1;
+ int cur = 4;
+
+ while (hi >= lo) {
+ if (tab[cur] >= need && tab[cur - 1] < need)
+ return tab[cur];
+ if (tab[cur] > need)
+ hi = cur - 1;
+ else
+ lo = cur + 1;
+ cur = (hi + lo) / 2;
+ }
+ return need;
+}
+
+
+/*
+** Debug functions
+*/
+#ifdef DEBUG
+
+static void pd_check(ProcDict *pd)
+{
+ unsigned int i;
+ Uint num;
+ if (pd == NULL)
+ return;
+ ASSERT(pd->size >= pd->used);
+ ASSERT(HASH_RANGE(pd) <= MAX_HASH);
+ for (i = 0, num = 0; i < pd->used; ++i) {
+ Eterm t = pd->data[i];
+ if (is_nil(t)) {
+ continue;
+ } else if (is_tuple(t)) {
+ ++num;
+ ASSERT(arityval(*tuple_val(t)) == 2);
+ continue;
+ } else if (is_list(t)) {
+ while (t != NIL) {
+ ++num;
+ ASSERT(is_tuple(TCAR(t)));
+ ASSERT(arityval(*(tuple_val(TCAR(t)))) == 2);
+ t = TCDR(t);
+ }
+ continue;
+ } else {
+ erl_exit(1,
+ "Found tag 0x%08x in process dictionary at position %d",
+ (unsigned long) t, (int) i);
+ }
+ }
+ ASSERT(num == pd->numElements);
+ ASSERT(pd->splitPosition <= pd->homeSize);
+}
+
+#endif /* DEBUG */
+
+
+#ifdef HARDDEBUG
+
+static int hdebugf(char *format, ...)
+{
+ va_list ap;
+
+ erts_fprintf(stderr, "DEBUG: %s:%d :", hdebugf_file, hdebugf_line);
+ va_start(ap, format);
+ erts_vfprintf(stderr, format, ap);
+ va_end(ap);
+ erts_fprintf(stderr, "\n");
+ return 0;
+}
+
+#endif /* HARDDEBUG */
+
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-09 17:29:19 +0000