erl_process_dict.c

OTP是开放电信平台的简称

/* ``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 via the world wide web 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.
 * 
 * The Initial Developer of the Original Code is Ericsson Utvecklings AB.
 * Portions created by Ericsson are Copyright 1999, Ericsson Utvecklings
 * AB. All Rights Reserved.''
 * 
 *     $Id$
 */
/*
 * 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
*/

/* Error codes from subroutines */
#define PDICT_OK            0
#define PDICT_SYSTEM_LIMIT -1

/* 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_PROC_MORE_MEM((Sz)),			\
     erts_alloc(ERTS_ALC_T_PROC_DICT, (Sz)))
#define PD_FREE(P, Sz)				\
    (ERTS_PROC_LESS_MEM((Sz)),			\
     erts_free(ERTS_ALC_T_PROC_DICT, (P)))
#define PD_REALLOC(P, OSz, NSz) 		\
    (ERTS_PROC_LESS_MEM((OSz)),			\
     ERTS_PROC_MORE_MEM((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 int pd_hash_erase(Process *p, Eterm id, Eterm *ret);
static int pd_hash_erase_all(Process *p);
static int pd_hash_get_keys(Process *p, Eterm value, Eterm *ret) ;
static Eterm pd_hash_get_all(Process *p, ProcDict *pd);
static int pd_hash_put(Process *p, Eterm id, Eterm value, Eterm *ret);

static int shrink(Process *p); 
static int 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);
    if (p->debug_dictionary)
	size += PD_SZ2BYTES(p->debug_dictionary->size);
    return size;
}

void
erts_erase_dicts(Process *p)
{
    if (p->dictionary)
	pd_hash_erase_all(p);
    if (p->debug_dictionary) {
	p->dictionary = p->debug_dictionary;
	pd_hash_erase_all(p);
    }
    p->dictionary = NULL;
    p->debug_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);
    if (pd_hash_get_keys(BIF_P, BIF_ARG_1, &ret) != PDICT_OK) {
	PD_CHECK(BIF_P->dictionary);
	BIF_ERROR(BIF_P, BADARG);
    }
    PD_CHECK(BIF_P->dictionary);
    BIF_RET(ret);
}

BIF_RETTYPE put_2(BIF_ALIST_2)
{
    Eterm ret;
    PD_CHECK(BIF_P->dictionary);
    if (pd_hash_put(BIF_P, BIF_ARG_1, BIF_ARG_2, &ret) != PDICT_OK) {
	PD_CHECK(BIF_P->dictionary);
	BIF_ERROR(BIF_P, BADARG);
    }
    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);
    if (pd_hash_erase(BIF_P, BIF_ARG_1, &ret) != PDICT_OK) {
	PD_CHECK(BIF_P->dictionary);
	BIF_ERROR(BIF_P, BADARG);
    }
    PD_CHECK(BIF_P->dictionary);
    BIF_RET(ret);
}

/*
** Debug dictionary interfaces (i.e. $put, $get etc).
** The implementation is kind of sloppy, I switch the dictionary
** to the debug_dictionary and call the usual BIF, then switch
** back. 
*/

BIF_RETTYPE dollar_put_2(BIF_ALIST_2)
{
    BIF_RETTYPE save_ret;
    ProcDict *save_pd = BIF_P->dictionary;
    BIF_P->dictionary = BIF_P->debug_dictionary;
    save_ret = put_2(BIF_P, BIF_ARG_1, BIF_ARG_2);
    BIF_P->debug_dictionary = BIF_P->dictionary;
    BIF_P->dictionary = save_pd;
    BIF_RET(save_ret);
}

BIF_RETTYPE dollar_get_0(BIF_ALIST_0)
{
    BIF_RETTYPE save_ret;
    ProcDict *save_pd = BIF_P->dictionary;
    BIF_P->dictionary = BIF_P->debug_dictionary;
    save_ret = get_0(BIF_P);
    BIF_P->debug_dictionary = BIF_P->dictionary;
    BIF_P->dictionary = save_pd;
    BIF_RET(save_ret);
}

BIF_RETTYPE dollar_get_1(BIF_ALIST_1)
{
    BIF_RETTYPE save_ret;
    ProcDict *save_pd = BIF_P->dictionary;
    BIF_P->dictionary = BIF_P->debug_dictionary;
    save_ret = get_1(BIF_P, BIF_ARG_1);
    BIF_P->debug_dictionary = BIF_P->dictionary;
    BIF_P->dictionary = save_pd;
    BIF_RET(save_ret);
}

BIF_RETTYPE dollar_get_keys_1(BIF_ALIST_1)
{
    BIF_RETTYPE save_ret;
    ProcDict *save_pd = BIF_P->dictionary;
    BIF_P->dictionary = BIF_P->debug_dictionary;
    save_ret = get_keys_1(BIF_P, BIF_ARG_1);
    BIF_P->debug_dictionary = BIF_P->dictionary;
    BIF_P->dictionary = save_pd;
    BIF_RET(save_ret);
}

BIF_RETTYPE dollar_erase_0(BIF_ALIST_0)
{
    BIF_RETTYPE save_ret;
    ProcDict *save_pd = BIF_P->dictionary;
    BIF_P->dictionary = BIF_P->debug_dictionary;
    save_ret = erase_0(BIF_P);
    BIF_P->debug_dictionary = BIF_P->dictionary;
    BIF_P->dictionary = save_pd;
    BIF_RET(save_ret);
}

BIF_RETTYPE dollar_erase_1(BIF_ALIST_1)
{
    BIF_RETTYPE save_ret;
    ProcDict *save_pd = BIF_P->dictionary;
    BIF_P->dictionary = BIF_P->debug_dictionary;
    save_ret = erase_1(BIF_P, BIF_ARG_1);
    BIF_P->debug_dictionary = BIF_P->dictionary;
    BIF_P->dictionary = save_pd;
    BIF_RET(save_ret);
}

/*
** BIF implementations
*/
static int pd_hash_erase(Process *p, Eterm id, Eterm *ret)
{
    unsigned int hval;
    Eterm *hp;
    Eterm old;
    Eterm tmp;
    int i;
    unsigned int range;

    *ret = am_undefined;
    if (p->dictionary == NULL)
	return PDICT_OK;
    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 */
	i = 0;
	for (tmp = old; tmp != NIL && !EQ(tuple_val(TCAR(tmp))[1], id); 
	     tmp = TCDR(tmp))
	    ++i;
	if (tmp != NIL) {
	    Eterm nlist;
	    nlist = TCDR(tmp);
	    hp = HAlloc(p, i*2);
	    while (old != tmp) {
		nlist = CONS(hp, TCAR(old), nlist);
		hp += 2;
		old = TCDR(old);
	    }
	    if (TCDR(nlist) == NIL)
		nlist = TCAR(nlist);
	    array_put(&(p->dictionary), hval, nlist);
	    *ret = tuple_val(TCAR(tmp))[2];
	    --(p->dictionary->numElements);
	}
    } 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))
	return shrink(p);
    return PDICT_OK;
}

static int pd_hash_erase_all(Process *p)
{
    if (p->dictionary != NULL) {
	PD_FREE(p->dictionary, PD_SZ2BYTES(p->dictionary->size));
	p->dictionary = NULL;
    }
    return PDICT_OK;
}

Eterm erts_pd_hash_get(Process *p, Eterm id) 
{
    unsigned int hval;
    Eterm tmp;
    ProcDict *pd = p->dictionary;

    if (pd == NULL)
	return am_undefined;