diff options
Diffstat (limited to 'erts/emulator/beam/erl_ptab.c')
| -rw-r--r-- | erts/emulator/beam/erl_ptab.c | 1566 |
1 files changed, 1566 insertions, 0 deletions
diff --git a/erts/emulator/beam/erl_ptab.c b/erts/emulator/beam/erl_ptab.c new file mode 100644 index 0000000000..87beeafa1a --- /dev/null +++ b/erts/emulator/beam/erl_ptab.c @@ -0,0 +1,1566 @@ +/* + * %CopyrightBegin% + * + * Copyright Ericsson AB 2012. 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% + */ + +/* + * Description: Process/Port table implementation. + * + * Author: Rickard Green + */ + +#ifdef HAVE_CONFIG_H +# include "config.h" +#endif +#define ERTS_PTAB_WANT_BIF_IMPL__ +#define ERTS_PTAB_WANT_DEBUG_FUNCS__ +#include "erl_ptab.h" +#include "global.h" +#include "erl_binary.h" + +typedef struct ErtsPTabListBifData_ ErtsPTabListBifData; + +#define ERTS_PTAB_LIST_BIF_TAB_INSPECT_INDICES_PER_RED 25 +#define ERTS_PTAB_LIST_BIF_TAB_CHUNK_SIZE 1000 +#define ERTS_PTAB_LIST_BIF_MIN_START_REDS \ + (ERTS_PTAB_LIST_BIF_TAB_CHUNK_SIZE \ + / ERTS_PTAB_LIST_BIF_TAB_INSPECT_INDICES_PER_RED) + +#define ERTS_PTAB_LIST_BIF_TAB_FREE_DELETED_REDS 1 + +#define ERTS_PTAB_LIST_BIF_INSPECT_DELETED_PER_RED 10 + +#define ERTS_PTAB_LIST_INSPECT_DELETED_MAX_REDS \ + (ERTS_PTAB_LIST_BIF_TAB_CHUNK_SIZE \ + / ERTS_PTAB_LIST_BIF_TAB_INSPECT_INDICES_PER_RED) + + +#define ERTS_PTAB_LIST_BIF_BUILD_RESULT_CONSES_PER_RED 75 + +#define ERTS_PTAB_LIST_DBG_DO_TRACE 0 + +#ifdef DEBUG +# define ERTS_PTAB_LIST_BIF_DEBUGLEVEL 100 +#else +# define ERTS_PTAB_LIST_BIF_DEBUGLEVEL 0 +#endif + +#define ERTS_PTAB_LIST_DBGLVL_CHK_HALLOC 1 +#define ERTS_PTAB_LIST_DBGLVL_CHK_FOUND_PIDS 5 +#define ERTS_PTAB_LIST_DBGLVL_CHK_PIDS 10 +#define ERTS_PTAB_LIST_DBGLVL_CHK_DEL_LIST 20 +#define ERTS_PTAB_LIST_DBGLVL_CHK_RESLIST 20 + +#if ERTS_PTAB_LIST_BIF_DEBUGLEVEL == 0 +# define ERTS_PTAB_LIST_ASSERT(EXP) +#else +# define ERTS_PTAB_LIST_ASSERT(EXP) \ + ((void) ((EXP) \ + ? 1 \ + : (debug_ptab_list_assert_error(#EXP, \ + __FILE__, \ + __LINE__, \ + __func__), \ + 0))) +#endif + + +#if ERTS_PTAB_LIST_BIF_DEBUGLEVEL >= ERTS_PTAB_LIST_DBGLVL_CHK_HALLOC +# define ERTS_PTAB_LIST_DBG_SAVE_HEAP_ALLOC(PTLBDP, HP, SZ) \ +do { \ + ERTS_PTAB_LIST_ASSERT(!(PTLBDP)->debug.heap); \ + ERTS_PTAB_LIST_ASSERT(!(PTLBDP)->debug.heap_size); \ + (PTLBDP)->debug.heap = (HP); \ + (PTLBDP)->debug.heap_size = (SZ); \ +} while (0) +# define ERTS_PTAB_LIST_DBG_VERIFY_HEAP_ALLOC_USED(PTLBDP, HP) \ +do { \ + ERTS_PTAB_LIST_ASSERT((PTLBDP)->debug.heap); \ + ERTS_PTAB_LIST_ASSERT((PTLBDP)->debug.heap_size); \ + ERTS_PTAB_LIST_ASSERT(((PTLBDP)->debug.heap \ + + (PTLBDP)->debug.heap_size) \ + == (HP)); \ + (PTLBDP)->debug.heap = NULL; \ + (PTLBDP)->debug.heap_size = 0; \ +} while (0) +# define ERTS_PTAB_LIST_DBG_HEAP_ALLOC_INIT(PTLBDP) \ +do { \ + (PTLBDP)->debug.heap = NULL; \ + (PTLBDP)->debug.heap_size = 0; \ +} while (0) +#else +# define ERTS_PTAB_LIST_DBG_SAVE_HEAP_ALLOC(PTLBDP, HP, SZ) +# define ERTS_PTAB_LIST_DBG_VERIFY_HEAP_ALLOC_USED(PTLBDP, HP) +# define ERTS_PTAB_LIST_DBG_HEAP_ALLOC_INIT(PTLBDP) +#endif + +#if ERTS_PTAB_LIST_BIF_DEBUGLEVEL >= ERTS_PTAB_LIST_DBGLVL_CHK_RESLIST +# define ERTS_PTAB_LIST_DBG_CHK_RESLIST(R) \ + debug_ptab_list_check_res_list((R)) +#else +# define ERTS_PTAB_LIST_DBG_CHK_RESLIST(R) +#endif + +#if ERTS_PTAB_LIST_BIF_DEBUGLEVEL >= ERTS_PTAB_LIST_DBGLVL_CHK_PIDS +# define ERTS_PTAB_LIST_DBG_SAVE_PIDS(PTLBDP) \ + debug_ptab_list_save_all_pids((PTLBDP)) +# define ERTS_PTAB_LIST_DBG_VERIFY_PIDS(PTLBDP) \ +do { \ + if (!(PTLBDP)->debug.correct_pids_verified) \ + debug_ptab_list_verify_all_pids((PTLBDP)); \ +} while (0) +# define ERTS_PTAB_LIST_DBG_CLEANUP_CHK_PIDS(PTLBDP) \ +do { \ + if ((PTLBDP)->debug.correct_pids) { \ + erts_free(ERTS_ALC_T_PTAB_LIST_PIDS, \ + (PTLBDP)->debug.correct_pids); \ + (PTLBDP)->debug.correct_pids = NULL; \ + } \ +} while(0) +# define ERTS_PTAB_LIST_DBG_CHK_PIDS_INIT(PTLBDP) \ +do { \ + (PTLBDP)->debug.correct_pids_verified = 0; \ + (PTLBDP)->debug.correct_pids = NULL; \ +} while (0) +#else +# define ERTS_PTAB_LIST_DBG_SAVE_PIDS(PTLBDP) +# define ERTS_PTAB_LIST_DBG_VERIFY_PIDS(PTLBDP) +# define ERTS_PTAB_LIST_DBG_CLEANUP_CHK_PIDS(PTLBDP) +# define ERTS_PTAB_LIST_DBG_CHK_PIDS_INIT(PTLBDP) +#endif + +#if ERTS_PTAB_LIST_BIF_DEBUGLEVEL >= ERTS_PTAB_LIST_DBGLVL_CHK_FOUND_PIDS +# define ERTS_PTAB_LIST_DBG_CHK_PID_FOUND(PTLBDP, PID, IC) \ + debug_ptab_list_check_found_pid((PTLBDP), (PID), (IC), 1) +# define ERTS_PTAB_LIST_DBG_CHK_PID_NOT_FOUND(PTLBDP, PID, IC) \ + debug_ptab_list_check_found_pid((PTLBDP), (PID), (IC), 0) +#else +# define ERTS_PTAB_LIST_DBG_CHK_PID_FOUND(PTLBDP, PID, IC) +# define ERTS_PTAB_LIST_DBG_CHK_PID_NOT_FOUND(PTLBDP, PID, IC) +#endif + +#if ERTS_PTAB_LIST_BIF_DEBUGLEVEL >= ERTS_PTAB_LIST_DBGLVL_CHK_DEL_LIST +# define ERTS_PTAB_LIST_DBG_CHK_DEL_LIST(PTab) \ + debug_ptab_list_check_del_list((PTab)) +# define ERTS_PTAB_LIST_DBG_CHK_FREELIST(PTab, FL) \ + debug_ptab_list_check_del_free_list((PTab), (FL)) +#else +# define ERTS_PTAB_LIST_DBG_CHK_DEL_LIST(PTab) +# define ERTS_PTAB_LIST_DBG_CHK_FREELIST(PTab, FL) +#endif + +#if ERTS_PTAB_LIST_BIF_DEBUGLEVEL == 0 +#if ERTS_PTAB_LIST_DBG_DO_TRACE +# define ERTS_PTAB_LIST_DBG_INIT(P, PTLBDP) \ + (PTLBDP)->debug.caller = (P)->common.id +# else +# define ERTS_PTAB_LIST_DBG_INIT(P, PTLBDP) +# endif +# define ERTS_PTAB_LIST_DBG_CLEANUP(PTLBDP) +#else +# define ERTS_PTAB_LIST_DBG_INIT(P, PTLBDP) \ +do { \ + (PTLBDP)->debug.caller = (P)->common.id; \ + ERTS_PTAB_LIST_DBG_HEAP_ALLOC_INIT((PTLBDP)); \ + ERTS_PTAB_LIST_DBG_CHK_PIDS_INIT((PTLBDP)); \ +} while (0) +# define ERTS_PTAB_LIST_DBG_CLEANUP(PTLBDP) \ +do { \ + ERTS_PTAB_LIST_DBG_CLEANUP_CHK_PIDS((PTLBDP)); \ +} while (0) +#endif + +#if ERTS_PTAB_LIST_DBG_DO_TRACE +# define ERTS_PTAB_LIST_DBG_TRACE(PID, WHAT) \ + erts_fprintf(stderr, "%T %s:%d:%s(): %s\n", \ + (PID), __FILE__, __LINE__, __func__, #WHAT) +#else +# define ERTS_PTAB_LIST_DBG_TRACE(PID, WHAT) +#endif + + +#if ERTS_PTAB_LIST_BIF_DEBUGLEVEL != 0 +static void debug_ptab_list_assert_error(char* expr, + const char* file, + int line, + const char *func); +#endif +#if ERTS_PTAB_LIST_BIF_DEBUGLEVEL >= ERTS_PTAB_LIST_DBGLVL_CHK_RESLIST +static void debug_ptab_list_check_res_list(Eterm list); +#endif +#if ERTS_PTAB_LIST_BIF_DEBUGLEVEL >= ERTS_PTAB_LIST_DBGLVL_CHK_PIDS +static void debug_ptab_list_save_all_pids(ErtsPTabListBifData *ptlbdp); +static void debug_ptab_list_verify_all_pids(ErtsPTabListBifData *ptlbdp); +#endif +#if ERTS_PTAB_LIST_BIF_DEBUGLEVEL >= ERTS_PTAB_LIST_DBGLVL_CHK_FOUND_PIDS +static void debug_ptab_list_check_found_pid(ErtsPTabListBifData *ptlbdp, + Eterm pid, + Uint64 ic, + int pid_should_be_found); +#endif +#if ERTS_PTAB_LIST_BIF_DEBUGLEVEL >= ERTS_PTAB_LIST_DBGLVL_CHK_DEL_LIST +static void debug_ptab_list_check_del_list(ErtsPTab *ptab); +static void debug_ptab_list_check_del_free_list(ErtsPTab *ptab, + ErtsPTabDeletedElement *ptdep); +#endif + +struct ErtsPTabDeletedElement_ { + ErtsPTabDeletedElement *next; + ErtsPTabDeletedElement *prev; + int ix; + union { + struct { + Eterm id; + Uint64 inserted; + Uint64 deleted; + } element; + struct { + Uint64 interval; + } bif_invocation; + } u; +}; + +static Export ptab_list_continue_export; + +typedef struct { + Uint64 interval; +} ErtsPTabListBifChunkInfo; + +typedef enum { + INITIALIZING, + INSPECTING_TABLE, + INSPECTING_DELETED, + BUILDING_RESULT, + RETURN_RESULT +} ErtsPTabListBifState; + +struct ErtsPTabListBifData_ { + ErtsPTab *ptab; + ErtsPTabListBifState state; + Eterm caller; + ErtsPTabListBifChunkInfo *chunk; + int tix; + int pid_ix; + int pid_sz; + Eterm *pid; + ErtsPTabDeletedElement *bif_invocation; /* Only used when > 1 chunk */ + +#if ERTS_PTAB_LIST_BIF_DEBUGLEVEL != 0 || ERTS_PTAB_LIST_DBG_DO_TRACE + struct { + Eterm caller; +#if ERTS_PTAB_LIST_BIF_DEBUGLEVEL >= ERTS_PTAB_LIST_DBGLVL_CHK_FOUND_PIDS + Uint64 *pid_started; +#endif +#if ERTS_PTAB_LIST_BIF_DEBUGLEVEL >= ERTS_PTAB_LIST_DBGLVL_CHK_HALLOC + Eterm *heap; + Uint heap_size; +#endif +#if ERTS_PTAB_LIST_BIF_DEBUGLEVEL >= ERTS_PTAB_LIST_DBGLVL_CHK_PIDS + int correct_pids_verified; + Eterm *correct_pids; +#endif + } debug; +#endif + +}; + +#ifdef ARCH_32 + +static ERTS_INLINE Uint64 +dw_aint_to_uint64(erts_dw_aint_t *dw) +{ +#ifdef ETHR_SU_DW_NAINT_T__ + return (Uint64) dw->dw_sint; +#else + Uint64 res; + res = (Uint64) ((Uint32) dw->sint[ERTS_DW_AINT_HIGH_WORD]); + res <<= 32; + res |= (Uint64) ((Uint32) dw->sint[ERTS_DW_AINT_LOW_WORD]); + return res; +#endif +} + +static void +unint64_to_dw_aint(erts_dw_aint_t *dw, Uint64 val) +{ +#ifdef ETHR_SU_DW_NAINT_T__ + dw->dw_sint = (ETHR_SU_DW_NAINT_T__) val; +#else + dw->sint[ERTS_DW_AINT_LOW_WORD] = (erts_aint_t) (val & 0xffffffff); + dw->sint[ERTS_DW_AINT_HIGH_WORD] = (erts_aint_t) ((val >> 32) & 0xffffffff); +#endif +} + +static ERTS_INLINE void +last_data_init_nob(ErtsPTab *ptab, Uint64 val) +{ + erts_dw_aint_t dw; + unint64_to_dw_aint(&dw, val); + erts_smp_dw_atomic_init_nob(&ptab->vola.tile.last_data, &dw); +} + +static ERTS_INLINE void +last_data_set_relb(ErtsPTab *ptab, Uint64 val) +{ + erts_dw_aint_t dw; + unint64_to_dw_aint(&dw, val); + erts_smp_dw_atomic_set_relb(&ptab->vola.tile.last_data, &dw); +} + +static ERTS_INLINE Uint64 +last_data_read_nob(ErtsPTab *ptab) +{ + erts_dw_aint_t dw; + erts_smp_dw_atomic_read_nob(&ptab->vola.tile.last_data, &dw); + return dw_aint_to_uint64(&dw); +} + +static ERTS_INLINE Uint64 +last_data_read_acqb(ErtsPTab *ptab) +{ + erts_dw_aint_t dw; + erts_smp_dw_atomic_read_acqb(&ptab->vola.tile.last_data, &dw); + return dw_aint_to_uint64(&dw); +} + +static ERTS_INLINE Uint64 +last_data_cmpxchg_relb(ErtsPTab *ptab, Uint64 new, Uint64 exp) +{ + erts_dw_aint_t dw_new, dw_xchg; + + unint64_to_dw_aint(&dw_new, new); + unint64_to_dw_aint(&dw_xchg, exp); + + if (erts_smp_dw_atomic_cmpxchg_relb(&ptab->vola.tile.last_data, + &dw_new, + &dw_xchg)) + return exp; + else + return dw_aint_to_uint64(&dw_xchg); +} + +#elif defined(ARCH_64) + +union { + erts_smp_atomic_t pid_data; + char align[ERTS_CACHE_LINE_SIZE]; +} last erts_align_attribute(ERTS_CACHE_LINE_SIZE); + +static ERTS_INLINE void +last_data_init_nob(ErtsPTab *ptab, Uint64 val) +{ + erts_smp_atomic_init_nob(&ptab->vola.tile.last_data, (erts_aint_t) val); +} + +static ERTS_INLINE void +last_data_set_relb(ErtsPTab *ptab, Uint64 val) +{ + erts_smp_atomic_set_relb(&ptab->vola.tile.last_data, (erts_aint_t) val); +} + +static ERTS_INLINE Uint64 +last_data_read_nob(ErtsPTab *ptab) +{ + return (Uint64) erts_smp_atomic_read_nob(&ptab->vola.tile.last_data); +} + +static ERTS_INLINE Uint64 +last_data_read_acqb(ErtsPTab *ptab) +{ + return (Uint64) erts_smp_atomic_read_acqb(&ptab->vola.tile.last_data); +} + +static ERTS_INLINE Uint64 +last_data_cmpxchg_relb(ErtsPTab *ptab, Uint64 new, Uint64 exp) +{ + return (Uint64) erts_smp_atomic_cmpxchg_relb(&ptab->vola.tile.last_data, + (erts_aint_t) new, + (erts_aint_t) exp); +} + +#else +# error "Not 64-bit, nor 32-bit architecture..." +#endif + +static ERTS_INLINE int +last_data_cmp(Uint64 ld1, Uint64 ld2) +{ + Uint64 ld1_wrap; + + if (ld1 == ld2) + return 0; + + ld1_wrap = ld1 + (((Uint64) 1) << 63); + + if (ld1 < ld1_wrap) + return (ld1 < ld2 && ld2 < ld1_wrap) ? -1 : 1; + else + return (ld1_wrap <= ld2 && ld2 < ld1) ? 1 : -1; +} + +#define ERTS_PTAB_LastData2EtermData(LD) \ + ((Eterm) ((LD) & ~(~((Uint64) 0) << ERTS_PTAB_ID_DATA_SIZE))) + +void +erts_ptab_init_table(ErtsPTab *ptab, + ErtsAlcType_t atype, + void (*release_element)(void *), + ErtsPTabElementCommon *invalid_element, + int size, + char *name) +{ + size_t tab_sz; + int bits; + char *tab_end; + erts_smp_atomic_t *tab_entry; + erts_smp_rwmtx_opt_t rwmtx_opts = ERTS_SMP_RWMTX_OPT_DEFAULT_INITER; + rwmtx_opts.type = ERTS_SMP_RWMTX_TYPE_EXTREMELY_FREQUENT_READ; + rwmtx_opts.lived = ERTS_SMP_RWMTX_LONG_LIVED; + + erts_smp_rwmtx_init_opt(&ptab->list.data.rwmtx, &rwmtx_opts, name); + erts_smp_atomic32_init_nob(&ptab->vola.tile.count, 0); + last_data_init_nob(ptab, ~((Uint64) 0)); + + /* A size that is a power of 2 is to prefer performance wise */ + bits = erts_fit_in_bits_int32(size-1); + size = 1 << bits; + if (size > ERTS_PTAB_MAX_SIZE) { + size = ERTS_PTAB_MAX_SIZE; + bits = erts_fit_in_bits_int32((Sint32) size - 1); + } + + ptab->r.o.max = size; + + tab_sz = ERTS_ALC_CACHE_LINE_ALIGN_SIZE(size*sizeof(erts_smp_atomic_t)); + ptab->r.o.tab = erts_alloc_permanent_cache_aligned(atype, tab_sz); + tab_end = ((char *) ptab->r.o.tab) + tab_sz; + tab_entry = ptab->r.o.tab; + while (tab_end > ((char *) tab_entry)) { + erts_smp_atomic_init_nob(tab_entry, ERTS_AINT_NULL); + tab_entry++; + } + + ptab->r.o.tab_cache_lines = tab_sz/ERTS_CACHE_LINE_SIZE; + ptab->r.o.pix_per_cache_line = (ERTS_CACHE_LINE_SIZE + / sizeof(erts_smp_atomic_t)); + ASSERT((ptab->r.o.max & (ptab->r.o.max - 1)) == 0); /* power of 2 */ + ASSERT((ptab->r.o.pix_per_cache_line + & (ptab->r.o.pix_per_cache_line - 1)) == 0); /* power of 2 */ + ASSERT((ptab->r.o.tab_cache_lines + & (ptab->r.o.tab_cache_lines - 1)) == 0); /* power of 2 */ + + ptab->r.o.pix_mask + = (1 << bits) - 1; + ptab->r.o.pix_cl_mask + = ptab->r.o.tab_cache_lines-1; + ptab->r.o.pix_cl_shift + = erts_fit_in_bits_int32(ptab->r.o.pix_per_cache_line-1); + ptab->r.o.pix_cli_shift + = erts_fit_in_bits_int32(ptab->r.o.pix_cl_mask); + ptab->r.o.pix_cli_mask + = (1 << (bits - ptab->r.o.pix_cli_shift)) - 1; + + ASSERT(ptab->r.o.pix_cl_shift + ptab->r.o.pix_cli_shift == bits); + + ptab->r.o.invalid_element = invalid_element; + ptab->r.o.invalid_data = erts_ptab_id2data(ptab, invalid_element->id); + ptab->r.o.release_element = release_element; + + erts_smp_interval_init(&ptab->list.data.interval); + ptab->list.data.deleted.start = NULL; + ptab->list.data.deleted.end = NULL; + ptab->list.data.chunks = (((ptab->r.o.max - 1) + / ERTS_PTAB_LIST_BIF_TAB_CHUNK_SIZE) + + 1); + + if (size == ERTS_PTAB_MAX_SIZE) { + int pix; + /* + * We want a table size of a power of 2 which ERTS_PTAB_MAX_SIZE + * is. We only have ERTS_PTAB_MAX_SIZE-1 unique identifiers and + * we don't want to shrink the size to ERTS_PTAB_MAX_SIZE/2. + * + * In order to fix this, we insert a pointer from the table + * to the invalid_element, wich will be interpreted as a + * slot currently being modified. This way we will be able to + * have ERTS_PTAB_MAX_SIZE-1 valid elements in the table while + * still having a table size of the power of 2. + */ + erts_smp_atomic32_inc_nob(&ptab->vola.tile.count); + pix = erts_ptab_data2pix(ptab, ptab->r.o.invalid_data); + erts_smp_atomic_set_relb(&ptab->r.o.tab[pix], + (erts_aint_t) ptab->r.o.invalid_element); + } + +} + +int +erts_ptab_initialized(ErtsPTab *ptab) +{ + return ptab->r.o.tab != NULL; +} + +int +erts_ptab_new_element(ErtsPTab *ptab, + ErtsPTabElementCommon *ptab_el, + void *init_arg, + void (*init_ptab_el)(void *, Eterm)) +{ + int pix; + Uint64 ld, exp_ld; + Eterm data; + erts_aint32_t count; + erts_aint_t invalid = (erts_aint_t) ptab->r.o.invalid_element; + + erts_ptab_rlock(ptab); + + count = erts_smp_atomic32_inc_read_acqb(&ptab->vola.tile.count); + if (count > ptab->r.o.max) { + while (1) { + erts_aint32_t act_count; + + act_count = erts_smp_atomic32_cmpxchg_relb(&ptab->vola.tile.count, + count-1, + count); + if (act_count == count) { + erts_ptab_runlock(ptab); + return 0; + } + count = act_count; + if (count <= ptab->r.o.max) + break; + } + } + + ptab_el->u.alive.started_interval + = erts_smp_current_interval_nob(erts_ptab_interval(ptab)); + + ld = last_data_read_acqb(ptab); + + /* Reserve slot */ + while (1) { + ld++; + pix = erts_ptab_data2pix(ptab, ERTS_PTAB_LastData2EtermData(ld)); + if (erts_smp_atomic_read_nob(&ptab->r.o.tab[pix]) == ERTS_AINT_NULL) { + erts_aint_t val; + val = erts_smp_atomic_cmpxchg_relb(&ptab->r.o.tab[pix], + invalid, + ERTS_AINT_NULL); + + if (ERTS_AINT_NULL == val) + break; + } + } + + data = ERTS_PTAB_LastData2EtermData(ld); + + if (data == ptab->r.o.invalid_data) { + /* Do not use invalid data; fix it... */ + ld += ptab->r.o.max; + ASSERT(pix == erts_ptab_data2pix(ptab, + ERTS_PTAB_LastData2EtermData(ld))); + data = ERTS_PTAB_LastData2EtermData(ld); + ASSERT(data != ptab->r.o.invalid_data); + } + + exp_ld = last_data_read_nob(ptab); + + /* Move last data forward */ + while (1) { + Uint64 act_ld; + if (last_data_cmp(ld, exp_ld) < 0) + break; + act_ld = last_data_cmpxchg_relb(ptab, ld, exp_ld); + if (act_ld == exp_ld) + break; + exp_ld = act_ld; + } + + init_ptab_el(init_arg, data); + +#ifdef ERTS_SMP + erts_smp_atomic32_init_nob(&ptab_el->refc, 1); +#endif + + /* Move into slot reserved */ +#ifdef DEBUG + ASSERT(invalid == erts_smp_atomic_xchg_relb(&ptab->r.o.tab[pix], + (erts_aint_t) ptab_el)); +#else + erts_smp_atomic_set_relb(&ptab->r.o.tab[pix], (erts_aint_t) ptab_el); +#endif + + erts_ptab_runlock(ptab); + + return 1; +} + +static void +save_deleted_element(ErtsPTab *ptab, ErtsPTabElementCommon *ptab_el) +{ + ErtsPTabDeletedElement *ptdep = erts_alloc(ERTS_ALC_T_PTAB_LIST_DEL, + sizeof(ErtsPTabDeletedElement)); + ERTS_PTAB_LIST_ASSERT(ptab->list.data.deleted.start + && ptab->list.data.deleted.end); + ERTS_SMP_LC_ASSERT(erts_smp_lc_ptab_is_rwlocked(ptab)); + + ERTS_PTAB_LIST_DBG_CHK_DEL_LIST(ptab); + + ptdep->prev = ptab->list.data.deleted.end; + ptdep->next = NULL; + ptdep->ix = erts_ptab_id2pix(ptab, ptab_el->id); + ptdep->u.element.id = ptab_el->id; + ptdep->u.element.inserted = ptab_el->u.alive.started_interval; + ptdep->u.element.deleted = + erts_smp_current_interval_nob(erts_ptab_interval(ptab)); + + ptab->list.data.deleted.end->next = ptdep; + ptab->list.data.deleted.end = ptdep; + + ERTS_PTAB_LIST_DBG_CHK_DEL_LIST(ptab); + + ERTS_PTAB_LIST_ASSERT(ptdep->prev->ix >= 0 + ? (ptdep->u.element.deleted + >= ptdep->prev->u.element.deleted) + : (ptdep->u.element.deleted + >= ptdep->prev->u.bif_invocation.interval)); +} + +void +erts_ptab_delete_element(ErtsPTab *ptab, + ErtsPTabElementCommon *ptab_el) +{ + int maybe_save; + int pix = erts_ptab_id2pix(ptab, ptab_el->id); + + ASSERT(erts_get_scheduler_id()); /* *Need* to be a scheduler */ + + erts_ptab_rlock(ptab); + maybe_save = ptab->list.data.deleted.end != NULL; + if (maybe_save) { + erts_ptab_runlock(ptab); + erts_ptab_rwlock(ptab); + } + + erts_smp_atomic_set_relb(&ptab->r.o.tab[pix], ERTS_AINT_NULL); + + ASSERT(erts_smp_atomic32_read_nob(&ptab->vola.tile.count) > 0); + erts_smp_atomic32_dec_relb(&ptab->vola.tile.count); + + if (!maybe_save) + erts_ptab_runlock(ptab); + else { + if (ptab->list.data.deleted.end) + save_deleted_element(ptab, ptab_el); + erts_ptab_rwunlock(ptab); + } + + if (ptab->r.o.release_element) + erts_schedule_thr_prgr_later_op(ptab->r.o.release_element, + (void *) ptab_el, + &ptab_el->u.release); +} + +/* + * erts_ptab_list() implements BIFs listing the content of the table, + * e.g. erlang:processes/0. + */ +static void cleanup_ptab_list_bif_data(Binary *bp); +static int ptab_list_bif_engine(Process *c_p, Eterm *res_accp, Binary *mbp); + + +BIF_RETTYPE +erts_ptab_list(Process *c_p, ErtsPTab *ptab) +{ + /* + * A requirement: The list of identifiers returned should be a + * consistent snapshot of all elements existing + * in the table at some point in time during the + * execution of the BIF calling this function. + * Since elements might be deleted while the BIF + * is executing, we have to keep track of all + * deleted elements and add them to the result. + * We also ignore elements created after the BIF + * has begun executing. + */ + BIF_RETTYPE ret_val; + Eterm res_acc = NIL; + Binary *mbp = erts_create_magic_binary(sizeof(ErtsPTabListBifData), + cleanup_ptab_list_bif_data); + ErtsPTabListBifData *ptlbdp = ERTS_MAGIC_BIN_DATA(mbp); + + ERTS_PTAB_LIST_DBG_TRACE(c_p->common.id, call); + ptlbdp->ptab = ptab; + ptlbdp->state = INITIALIZING; + ERTS_PTAB_LIST_DBG_INIT(c_p, ptlbdp); + + if (ERTS_BIF_REDS_LEFT(c_p) >= ERTS_PTAB_LIST_BIF_MIN_START_REDS + && ptab_list_bif_engine(c_p, &res_acc, mbp)) { + erts_bin_free(mbp); + ERTS_PTAB_LIST_DBG_CHK_RESLIST(res_acc); + ERTS_PTAB_LIST_DBG_TRACE(c_p->common.id, return); + ERTS_BIF_PREP_RET(ret_val, res_acc); + } + else { + Eterm *hp; + Eterm magic_bin; + ERTS_PTAB_LIST_DBG_CHK_RESLIST(res_acc); + hp = HAlloc(c_p, PROC_BIN_SIZE); + ERTS_PTAB_LIST_DBG_SAVE_HEAP_ALLOC(ptlbdp, hp, PROC_BIN_SIZE); + magic_bin = erts_mk_magic_binary_term(&hp, &MSO(c_p), mbp); + ERTS_PTAB_LIST_DBG_VERIFY_HEAP_ALLOC_USED(ptlbdp, hp); + ERTS_PTAB_LIST_DBG_TRACE(c_p->common.id, trap); + ERTS_BIF_PREP_YIELD2(ret_val, + &ptab_list_continue_export, + c_p, + res_acc, + magic_bin); + } + return ret_val; +} + +static void +cleanup_ptab_list_bif_data(Binary *bp) +{ + ErtsPTabListBifData *ptlbdp = ERTS_MAGIC_BIN_DATA(bp); + ErtsPTab *ptab = ptlbdp->ptab; + + ERTS_PTAB_LIST_DBG_TRACE(ptlbdp->debug.caller, call); + + if (ptlbdp->state != INITIALIZING) { + + if (ptlbdp->chunk) { + erts_free(ERTS_ALC_T_PTAB_LIST_CNKI, ptlbdp->chunk); + ptlbdp->chunk = NULL; + } + if (ptlbdp->pid) { + erts_free(ERTS_ALC_T_PTAB_LIST_PIDS, ptlbdp->pid); + ptlbdp->pid = NULL; + } + +#if ERTS_PTAB_LIST_BIF_DEBUGLEVEL >= ERTS_PTAB_LIST_DBGLVL_CHK_FOUND_PIDS + if (ptlbdp->debug.pid_started) { + erts_free(ERTS_ALC_T_PTAB_LIST_PIDS, ptlbdp->debug.pid_started); + ptlbdp->debug.pid_started = NULL; + } +#endif + + if (ptlbdp->bif_invocation) { + ErtsPTabDeletedElement *ptdep; + + erts_ptab_rwlock(ptab); + + ERTS_PTAB_LIST_DBG_TRACE(ptlbdp->debug.caller, deleted_cleanup); + + ptdep = ptlbdp->bif_invocation; + ptlbdp->bif_invocation = NULL; + + ERTS_PTAB_LIST_DBG_CHK_DEL_LIST(ptab); + + if (ptdep->prev) { + /* + * Only remove this bif invokation when we + * have preceding invokations. + */ + ptdep->prev->next = ptdep->next; + if (ptdep->next) + ptdep->next->prev = ptdep->prev; + else { + /* + * At the time of writing this branch cannot be + * reached. I don't want to remove this code though + * since it may be possible to reach this line + * in the future if the cleanup order in + * erts_do_exit_process() is changed. The ASSERT(0) + * is only here to make us aware that the reorder + * has happened. /rickard + */ + ASSERT(0); + ptab->list.data.deleted.end = ptdep->prev; + } + erts_free(ERTS_ALC_T_PTAB_LIST_DEL, ptdep); + } + else { + /* + * Free all elements until next bif invokation + * is found. + */ + ERTS_PTAB_LIST_ASSERT(ptab->list.data.deleted.start == ptdep); + do { + ErtsPTabDeletedElement *fptdep = ptdep; + ptdep = ptdep->next; + erts_free(ERTS_ALC_T_PTAB_LIST_DEL, fptdep); + } while (ptdep && ptdep->ix >= 0); + ptab->list.data.deleted.start = ptdep; + if (ptdep) + ptdep->prev = NULL; + else + ptab->list.data.deleted.end = NULL; + } + + ERTS_PTAB_LIST_DBG_CHK_DEL_LIST(ptab); + + erts_ptab_rwunlock(ptab); + + } + } + + ERTS_PTAB_LIST_DBG_TRACE(ptlbdp->debug.caller, return); + ERTS_PTAB_LIST_DBG_CLEANUP(ptlbdp); +} + +static int +ptab_list_bif_engine(Process *c_p, Eterm *res_accp, Binary *mbp) +{ + ErtsPTabListBifData *ptlbdp = ERTS_MAGIC_BIN_DATA(mbp); + ErtsPTab *ptab = ptlbdp->ptab; + int have_reds; + int reds; + int locked = 0; + + do { + switch (ptlbdp->state) { + case INITIALIZING: + ptlbdp->chunk = erts_alloc(ERTS_ALC_T_PTAB_LIST_CNKI, + (sizeof(ErtsPTabListBifChunkInfo) + * ptab->list.data.chunks)); + ptlbdp->tix = 0; + ptlbdp->pid_ix = 0; + + erts_ptab_rwlock(ptab); + locked = 1; + + ERTS_PTAB_LIST_DBG_TRACE(c_p->common.id, init); + + ptlbdp->pid_sz = erts_ptab_count(ptab); + ptlbdp->pid = erts_alloc(ERTS_ALC_T_PTAB_LIST_PIDS, + sizeof(Eterm)*ptlbdp->pid_sz); + +#if ERTS_PTAB_LIST_BIF_DEBUGLEVEL >= ERTS_PTAB_LIST_DBGLVL_CHK_FOUND_PIDS + ptlbdp->debug.pid_started + = erts_alloc(ERTS_ALC_T_PTAB_LIST_PIDS, + sizeof(Uint64)*ptlbdp->pid_sz); +#endif + + ERTS_PTAB_LIST_DBG_SAVE_PIDS(ptlbdp); + + if (ptab->list.data.chunks == 1) + ptlbdp->bif_invocation = NULL; + else { + /* + * We will have to access the table multiple times + * releasing the table lock in between chunks. + */ + ptlbdp->bif_invocation + = erts_alloc(ERTS_ALC_T_PTAB_LIST_DEL, + sizeof(ErtsPTabDeletedElement)); + ptlbdp->bif_invocation->ix = -1; + ptlbdp->bif_invocation->u.bif_invocation.interval + = erts_smp_step_interval_nob(erts_ptab_interval(ptab)); + ERTS_PTAB_LIST_DBG_CHK_DEL_LIST(ptab); + + ptlbdp->bif_invocation->next = NULL; + if (ptab->list.data.deleted.end) { + ptlbdp->bif_invocation->prev = ptab->list.data.deleted.end; + ptab->list.data.deleted.end->next = ptlbdp->bif_invocation; + ERTS_PTAB_LIST_ASSERT(ptab->list.data.deleted.start); + } + else { + ptlbdp->bif_invocation->prev = NULL; + ptab->list.data.deleted.start = ptlbdp->bif_invocation; + } + ptab->list.data.deleted.end = ptlbdp->bif_invocation; + + ERTS_PTAB_LIST_DBG_CHK_DEL_LIST(ptab); + + } + + ptlbdp->state = INSPECTING_TABLE; + /* Fall through */ + + case INSPECTING_TABLE: { + int ix = ptlbdp->tix; + int indices = ERTS_PTAB_LIST_BIF_TAB_CHUNK_SIZE; + int cix = ix / ERTS_PTAB_LIST_BIF_TAB_CHUNK_SIZE; + int end_ix = ix + indices; + Uint64 *invocation_interval_p; + ErtsPTabElementCommon *invalid_element; + + invocation_interval_p + = (ptlbdp->bif_invocation + ? &ptlbdp->bif_invocation->u.bif_invocation.interval + : NULL); + + ERTS_PTAB_LIST_ASSERT(is_nil(*res_accp)); + if (!locked) { + erts_ptab_rwlock(ptab); + locked = 1; + } + + ERTS_SMP_LC_ASSERT(erts_smp_lc_ptab_is_rwlocked(ptab)); + ERTS_PTAB_LIST_DBG_TRACE(p->common.id, insp_table); + + if (cix != 0) + ptlbdp->chunk[cix].interval + = erts_smp_step_interval_nob(erts_ptab_interval(ptab)); + else if (ptlbdp->bif_invocation) + ptlbdp->chunk[0].interval = *invocation_interval_p; + /* else: interval is irrelevant */ + + if (end_ix >= ptab->r.o.max) { + ERTS_PTAB_LIST_ASSERT(cix+1 == ptab->list.data.chunks); + end_ix = ptab->r.o.max; + indices = end_ix - ix; + /* What to do when done with this chunk */ + ptlbdp->state = (ptab->list.data.chunks == 1 + ? BUILDING_RESULT + : INSPECTING_DELETED); + } + + invalid_element = ptab->r.o.invalid_element; + for (; ix < end_ix; ix++) { + ErtsPTabElementCommon *el; + el = (ErtsPTabElementCommon *) erts_ptab_pix2intptr_nob(ptab, + ix); + if (el + && el != invalid_element + && (!invocation_interval_p + || el->u.alive.started_interval < *invocation_interval_p)) { + ERTS_PTAB_LIST_ASSERT(erts_ptab_is_valid_id(el->id)); + ptlbdp->pid[ptlbdp->pid_ix] = el->id; + +#if ERTS_PTAB_LIST_BIF_DEBUGLEVEL >= ERTS_PTAB_LIST_DBGLVL_CHK_FOUND_PIDS + ptlbdp->debug.pid_started[ptlbdp->pid_ix] + = el->u.alive.started_interval; +#endif + + ptlbdp->pid_ix++; + ERTS_PTAB_LIST_ASSERT(ptlbdp->pid_ix <= ptlbdp->pid_sz); + } + } + + ptlbdp->tix = end_ix; + + erts_ptab_rwunlock(ptab); + locked = 0; + + reds = indices/ERTS_PTAB_LIST_BIF_TAB_INSPECT_INDICES_PER_RED; + BUMP_REDS(c_p, reds); + + have_reds = ERTS_BIF_REDS_LEFT(c_p); + + if (have_reds && ptlbdp->state == INSPECTING_TABLE) { + ix = ptlbdp->tix; + indices = ERTS_PTAB_LIST_BIF_TAB_CHUNK_SIZE; + end_ix = ix + indices; + if (end_ix > ptab->r.o.max) { + end_ix = ptab->r.o.max; + indices = end_ix - ix; + } + + reds = indices/ERTS_PTAB_LIST_BIF_TAB_INSPECT_INDICES_PER_RED; + + /* Pretend we have no reds left if we haven't got enough + reductions to complete next chunk */ + if (reds > have_reds) + have_reds = 0; + } + + break; + } + + case INSPECTING_DELETED: { + int i; + int max_reds; + int free_deleted = 0; + Uint64 invocation_interval; + ErtsPTabDeletedElement *ptdep; + ErtsPTabDeletedElement *free_list = NULL; + + ptdep = ptlbdp->bif_invocation; + ERTS_PTAB_LIST_ASSERT(ptdep); + invocation_interval = ptdep->u.bif_invocation.interval; + + max_reds = have_reds = ERTS_BIF_REDS_LEFT(c_p); + if (max_reds > ERTS_PTAB_LIST_INSPECT_DELETED_MAX_REDS) + max_reds = ERTS_PTAB_LIST_INSPECT_DELETED_MAX_REDS; + + reds = 0; + erts_ptab_rwlock(ptab); + ERTS_PTAB_LIST_DBG_TRACE(p->common.id, insp_term_procs); + + ERTS_PTAB_LIST_DBG_CHK_DEL_LIST(ptab); + + if (ptdep->prev) + ptdep->prev->next = ptdep->next; + else { + ERTS_PTAB_LIST_ASSERT(ptab->list.data.deleted.start == ptdep); + ptab->list.data.deleted.start = ptdep->next; + + if (ptab->list.data.deleted.start + && ptab->list.data.deleted.start->ix >= 0) { + free_list = ptab->list.data.deleted.start; + free_deleted = 1; + } + } + + if (ptdep->next) + ptdep->next->prev = ptdep->prev; + else + ptab->list.data.deleted.end = ptdep->prev; + + ptdep = ptdep->next; + + i = 0; + while (reds < max_reds && ptdep) { + if (ptdep->ix < 0) { + if (free_deleted) { + ERTS_PTAB_LIST_ASSERT(free_list); + ERTS_PTAB_LIST_ASSERT(ptdep->prev); + + ptdep->prev->next = NULL; /* end of free_list */ + ptab->list.data.deleted.start = ptdep; + ptdep->prev = NULL; + free_deleted = 0; + } + } + else { + int cix = ptdep->ix/ERTS_PTAB_LIST_BIF_TAB_CHUNK_SIZE; + Uint64 chunk_interval = ptlbdp->chunk[cix].interval; + Eterm pid = ptdep->u.element.id; + ERTS_PTAB_LIST_ASSERT(erts_ptab_is_valid_id(pid)); + + if (ptdep->u.element.inserted < invocation_interval) { + if (ptdep->u.element.deleted < chunk_interval) { + ERTS_PTAB_LIST_DBG_CHK_PID_NOT_FOUND( + ptlbdp, + pid, + ptdep->u.element.inserted); + ptlbdp->pid[ptlbdp->pid_ix] = pid; +#if ERTS_PTAB_LIST_BIF_DEBUGLEVEL >= ERTS_PTAB_LIST_DBGLVL_CHK_FOUND_PIDS + ptlbdp->debug.pid_started[ptlbdp->pid_ix] + = ptdep->u.element.inserted; +#endif + ptlbdp->pid_ix++; + ERTS_PTAB_LIST_ASSERT(ptlbdp->pid_ix + <= ptlbdp->pid_sz); + } + else { + ERTS_PTAB_LIST_DBG_CHK_PID_FOUND( + ptlbdp, + pid, + ptdep->u.element.inserted); + } + } + else { + ERTS_PTAB_LIST_DBG_CHK_PID_NOT_FOUND( + ptlbdp, + pid, + ptdep->u.element.inserted); + } + + i++; + if (i == ERTS_PTAB_LIST_BIF_INSPECT_DELETED_PER_RED) { + reds++; + i = 0; + } + if (free_deleted) + reds += ERTS_PTAB_LIST_BIF_TAB_FREE_DELETED_REDS; + } + ptdep = ptdep->next; + } + + if (free_deleted) { + ERTS_PTAB_LIST_ASSERT(free_list); + ptab->list.data.deleted.start = ptdep; + if (!ptdep) + ptab->list.data.deleted.end = NULL; + else { + ERTS_PTAB_LIST_ASSERT(ptdep->prev); + ptdep->prev->next = NULL; /* end of free_list */ + ptdep->prev = NULL; + } + } + + if (!ptdep) { + /* Done */ + ERTS_PTAB_LIST_ASSERT(ptlbdp->pid_ix == ptlbdp->pid_sz); + ptlbdp->state = BUILDING_RESULT; + ptlbdp->bif_invocation->next = free_list; + free_list = ptlbdp->bif_invocation; + ptlbdp->bif_invocation = NULL; + } + else { + /* Link in bif_invocation again where we left off */ + ptlbdp->bif_invocation->prev = ptdep->prev; + ptlbdp->bif_invocation->next = ptdep; + ptdep->prev = ptlbdp->bif_invocation; + if (ptlbdp->bif_invocation->prev) + ptlbdp->bif_invocation->prev->next = ptlbdp->bif_invocation; + else { + ERTS_PTAB_LIST_ASSERT(ptab->list.data.deleted.start + == ptdep); + ptab->list.data.deleted.start = ptlbdp->bif_invocation; + } + } + + ERTS_PTAB_LIST_DBG_CHK_DEL_LIST(ptab); + ERTS_PTAB_LIST_DBG_CHK_FREELIST(ptab, free_list); + erts_ptab_rwunlock(ptab); + + /* + * We do the actual free of deleted structures now when we + * have released the table lock instead of when we encountered + * them. This since free() isn't for free and we don't want to + * unnecessarily block other schedulers. + */ + while (free_list) { + ptdep = free_list; + free_list = ptdep->next; + erts_free(ERTS_ALC_T_PTAB_LIST_DEL, ptdep); + } + + have_reds -= reds; + if (have_reds < 0) + have_reds = 0; + BUMP_REDS(c_p, reds); + break; + } + + case BUILDING_RESULT: { + int conses, ix, min_ix; + Eterm *hp; + Eterm res = *res_accp; + + ERTS_PTAB_LIST_DBG_VERIFY_PIDS(ptlbdp); + ERTS_PTAB_LIST_DBG_CHK_RESLIST(res); + + ERTS_PTAB_LIST_DBG_TRACE(p->common.id, begin_build_res); + + have_reds = ERTS_BIF_REDS_LEFT(c_p); + conses = ERTS_PTAB_LIST_BIF_BUILD_RESULT_CONSES_PER_RED*have_reds; + min_ix = ptlbdp->pid_ix - conses; + if (min_ix < 0) { + min_ix = 0; + conses = ptlbdp->pid_ix; + } + + if (conses) { + hp = HAlloc(c_p, conses*2); + ERTS_PTAB_LIST_DBG_SAVE_HEAP_ALLOC(ptlbdp, hp, conses*2); + + for (ix = ptlbdp->pid_ix - 1; ix >= min_ix; ix--) { + ERTS_PTAB_LIST_ASSERT(erts_ptab_is_valid_id(ptlbdp->pid[ix])); + res = CONS(hp, ptlbdp->pid[ix], res); + hp += 2; + } + + ERTS_PTAB_LIST_DBG_VERIFY_HEAP_ALLOC_USED(ptlbdp, hp); + } + + ptlbdp->pid_ix = min_ix; + if (min_ix == 0) + ptlbdp->state = RETURN_RESULT; + else { + ptlbdp->pid_sz = min_ix; + ptlbdp->pid = erts_realloc(ERTS_ALC_T_PTAB_LIST_PIDS, + ptlbdp->pid, + sizeof(Eterm)*ptlbdp->pid_sz); +#if ERTS_PTAB_LIST_BIF_DEBUGLEVEL >= ERTS_PTAB_LIST_DBGLVL_CHK_FOUND_PIDS + ptlbdp->debug.pid_started + = erts_realloc(ERTS_ALC_T_PTAB_LIST_PIDS, + ptlbdp->debug.pid_started, + sizeof(Uint64) * ptlbdp->pid_sz); +#endif + } + reds = conses/ERTS_PTAB_LIST_BIF_BUILD_RESULT_CONSES_PER_RED; + BUMP_REDS(c_p, reds); + have_reds -= reds; + + ERTS_PTAB_LIST_DBG_CHK_RESLIST(res); + ERTS_PTAB_LIST_DBG_TRACE(c_p->common.id, end_build_res); + *res_accp = res; + break; + } + case RETURN_RESULT: + cleanup_ptab_list_bif_data(mbp); + return 1; + + default: + erl_exit(ERTS_ABORT_EXIT, + "%s:%d:ptab_list_bif_engine(): Invalid state: %d\n", + __FILE__, __LINE__, (int) ptlbdp->state); + } + + + } while (have_reds || ptlbdp->state == RETURN_RESULT); + + return 0; +} + +/* + * ptab_list_continue/2 is a hidden BIF that the original BIF traps to + * if there are too much work to do in one go. + */ + +static BIF_RETTYPE ptab_list_continue(BIF_ALIST_2) +{ + Eterm res_acc; + Binary *mbp; + + /* + * This bif cannot be called from erlang code. It can only be + * trapped to from other BIFs; therefore, a bad argument + * is an internal error and should never occur... + */ + + ERTS_PTAB_LIST_DBG_TRACE(BIF_P->common.id, call); + ERTS_PTAB_LIST_ASSERT(is_nil(BIF_ARG_1) || is_list(BIF_ARG_1)); + + res_acc = BIF_ARG_1; + + ERTS_PTAB_LIST_ASSERT(ERTS_TERM_IS_MAGIC_BINARY(BIF_ARG_2)); + + mbp = ((ProcBin *) binary_val(BIF_ARG_2))->val; + + ERTS_PTAB_LIST_ASSERT(ERTS_MAGIC_BIN_DESTRUCTOR(mbp) + == cleanup_ptab_list_bif_data); + ERTS_PTAB_LIST_ASSERT( + ((ErtsPTabListBifData *) ERTS_MAGIC_BIN_DATA(mbp))->debug.caller + == BIF_P->common.id); + + if (ptab_list_bif_engine(BIF_P, &res_acc, mbp)) { + ERTS_PTAB_LIST_DBG_TRACE(BIF_P->common.id, return); + BIF_RET(res_acc); + } + else { + ERTS_PTAB_LIST_DBG_TRACE(BIF_P->common.id, trap); + ERTS_BIF_YIELD2(&ptab_list_continue_export, BIF_P, res_acc, BIF_ARG_2); + } +} + +void +erts_ptab_init(void) +{ + /* ptab_list_continue/2 is a hidden BIF that the original BIF traps to. */ + erts_init_trap_export(&ptab_list_continue_export, + am_erlang, am_ptab_list_continue, 2, + &ptab_list_continue); + +} + +/* + * Debug stuff + */ + +Sint +erts_ptab_test_next_id(ErtsPTab *ptab, int set, Uint next) +{ + Uint64 ld; + Sint res; + Eterm data; + int first_pix = -1; + + erts_ptab_rwlock(ptab); + + if (!set) + ld = last_data_read_nob(ptab); + else { + + ld = (Uint64) next; + data = ERTS_PTAB_LastData2EtermData(ld); + if (ptab->r.o.invalid_data == data) { + ld += ptab->r.o.max; + ASSERT(erts_ptab_data2pix(ptab, data) + == erts_ptab_data2pix(ptab, + ERTS_PTAB_LastData2EtermData(ld))); + } + last_data_set_relb(ptab, ld); + } + + while (1) { + int pix; + ld++; + pix = (int) (ld % ptab->r.o.max); + if (first_pix < 0) + first_pix = pix; + else if (pix == first_pix) { + res = -1; + break; + } + if (ERTS_AINT_NULL == erts_ptab_pix2intptr_nob(ptab, pix)) { + data = ERTS_PTAB_LastData2EtermData(ld); + if (ptab->r.o.invalid_data == data) { + ld += ptab->r.o.max; + ASSERT(erts_ptab_data2pix(ptab, data) + == erts_ptab_data2pix(ptab, + ERTS_PTAB_LastData2EtermData(ld))); + data = ERTS_PTAB_LastData2EtermData(ld); + } + res = data; + break; + } + } + + erts_ptab_rwunlock(ptab); + + return res; +} + +static ERTS_INLINE ErtsPTabElementCommon * +ptab_pix2el(ErtsPTab *ptab, int ix) +{ + ErtsPTabElementCommon *ptab_el; + ASSERT(0 <= ix && ix < ptab->r.o.max); + ptab_el = (ErtsPTabElementCommon *) erts_ptab_pix2intptr_nob(ptab, ix); + if (ptab_el == ptab->r.o.invalid_element) + return NULL; + else + return ptab_el; +} + +Eterm +erts_debug_ptab_list(Process *c_p, ErtsPTab *ptab) +{ + int i; + Uint need; + Eterm res; + Eterm* hp; + Eterm *hp_end; + + erts_ptab_rwlock(ptab); + + res = NIL; + need = erts_ptab_count(ptab) * 2; + hp = HAlloc(c_p, need); /* we need two heap words for each id */ + hp_end = hp + need; + + /* make the list by scanning bakward */ + + + for (i = ptab->r.o.max-1; i >= 0; i--) { + ErtsPTabElementCommon *el = ptab_pix2el(ptab, i); + if (el) { + res = CONS(hp, el->id, res); + hp += 2; + } + } + + erts_ptab_rwunlock(ptab); + + HRelease(c_p, hp_end, hp); + + return res; +} + +Eterm +erts_debug_ptab_list_bif_info(Process *c_p, ErtsPTab *ptab) +{ + ERTS_DECL_AM(ptab_list_bif_info); + Eterm elements[] = { + AM_ptab_list_bif_info, + make_small((Uint) ERTS_PTAB_LIST_BIF_MIN_START_REDS), + make_small((Uint) ptab->list.data.chunks), + make_small((Uint) ERTS_PTAB_LIST_BIF_TAB_CHUNK_SIZE), + make_small((Uint) ERTS_PTAB_LIST_BIF_TAB_INSPECT_INDICES_PER_RED), + make_small((Uint) ERTS_PTAB_LIST_BIF_TAB_FREE_DELETED_REDS), + make_small((Uint) ERTS_PTAB_LIST_BIF_INSPECT_DELETED_PER_RED), + make_small((Uint) ERTS_PTAB_LIST_INSPECT_DELETED_MAX_REDS), + make_small((Uint) ERTS_PTAB_LIST_BIF_BUILD_RESULT_CONSES_PER_RED), + make_small((Uint) ERTS_PTAB_LIST_BIF_DEBUGLEVEL) + }; + Uint sz = 0; + Eterm *hp; + (void) erts_bld_tuplev(NULL, &sz, sizeof(elements)/sizeof(Eterm), elements); + hp = HAlloc(c_p, sz); + return erts_bld_tuplev(&hp, NULL, sizeof(elements)/sizeof(Eterm), elements); +} + +#if ERTS_PTAB_LIST_BIF_DEBUGLEVEL >= ERTS_PTAB_LIST_DBGLVL_CHK_FOUND_PIDS +static void +debug_ptab_list_check_found_pid(ErtsPTabListBifData *ptlbdp, + Eterm pid, + Uint64 ic, + int pid_should_be_found) +{ + int i; + for (i = 0; i < ptlbdp->pid_ix; i++) { + if (ptlbdp->pid[i] == pid && ptlbdp->debug.pid_started[i] == ic) { + ERTS_PTAB_LIST_ASSERT(pid_should_be_found); + return; + } + } + ERTS_PTAB_LIST_ASSERT(!pid_should_be_found); +} +#endif + +#if ERTS_PTAB_LIST_BIF_DEBUGLEVEL >= ERTS_PTAB_LIST_DBGLVL_CHK_RESLIST +static void +debug_ptab_list_check_res_list(Eterm list) +{ + while (is_list(list)) { + Eterm* consp = list_val(list); + Eterm hd = CAR(consp); + ERTS_PTAB_LIST_ASSERT(erts_ptab_is_valid_id(hd)); + list = CDR(consp); + } + + ERTS_PTAB_LIST_ASSERT(is_nil(list)); +} +#endif + +#if ERTS_PTAB_LIST_BIF_DEBUGLEVEL >= ERTS_PTAB_LIST_DBGLVL_CHK_PIDS + +static void +debug_ptab_list_save_all_pids(ErtsPTabListBifData *ptlbdp) +{ + int ix, tix, cpix; + ErtsPTab *ptab = ptlbdp->ptab; + ptlbdp->debug.correct_pids_verified = 0; + ptlbdp->debug.correct_pids = erts_alloc(ERTS_ALC_T_PTAB_LIST_PIDS, + sizeof(Eterm)*ptlbdp->pid_sz); + + for (tix = 0, cpix = 0; tix < ptab->r.o.max; tix++) { + ErtsPTabElementCommon *el = ptab_pix2el(ptab, tix); + if (el) { + ERTS_PTAB_LIST_ASSERT(erts_ptab_is_valid_id(el->id)); + ptlbdp->debug.correct_pids[cpix++] = el->id; + ERTS_PTAB_LIST_ASSERT(cpix <= ptlbdp->pid_sz); + } + } + ERTS_PTAB_LIST_ASSERT(cpix == ptlbdp->pid_sz); + + for (ix = 0; ix < ptlbdp->pid_sz; ix++) + ptlbdp->pid[ix] = make_small(ix); +} + +static void +debug_ptab_list_verify_all_pids(ErtsPTabListBifData *ptlbdp) +{ + int ix, cpix; + + ERTS_PTAB_LIST_ASSERT(ptlbdp->pid_ix == ptlbdp->pid_sz); + + for (ix = 0; ix < ptlbdp->pid_sz; ix++) { + int found = 0; + Eterm pid = ptlbdp->pid[ix]; + ERTS_PTAB_LIST_ASSERT(erts_ptab_is_valid_id(pid)); + for (cpix = ix; cpix < ptlbdp->pid_sz; cpix++) { + if (ptlbdp->debug.correct_pids[cpix] == pid) { + ptlbdp->debug.correct_pids[cpix] = NIL; + found = 1; + break; + } + } + if (!found) { + for (cpix = 0; cpix < ix; cpix++) { + if (ptlbdp->debug.correct_pids[cpix] == pid) { + ptlbdp->debug.correct_pids[cpix] = NIL; + found = 1; + break; + } + } + } + ERTS_PTAB_LIST_ASSERT(found); + } + ptlbdp->debug.correct_pids_verified = 1; + + erts_free(ERTS_ALC_T_PTAB_LIST_PIDS, ptlbdp->debug.correct_pids); + ptlbdp->debug.correct_pids = NULL; +} +#endif /* ERTS_PTAB_LIST_BIF_DEBUGLEVEL >= ERTS_PTAB_LIST_DBGLVL_CHK_PIDS */ + +#if ERTS_PTAB_LIST_BIF_DEBUGLEVEL >= ERTS_PTAB_LIST_DBGLVL_CHK_DEL_LIST +static void +debug_ptab_list_check_del_list(ErtsPTab *ptab) +{ + ERTS_SMP_LC_ASSERT(erts_smp_lc_ptab_is_rwlocked(ptab)); + if (!ptab->list.data.deleted.start) + ERTS_PTAB_LIST_ASSERT(!ptab->list.data.deleted.end); + else { + Uint64 curr_interval = erts_smp_current_interval_nob(erts_ptab_interval(ptab)); + Uint64 *prev_x_interval_p = NULL; + ErtsPTabDeletedElement *ptdep; + + for (ptdep = ptab->list.data.deleted.start; + ptdep; + ptdep = ptdep->next) { + if (!ptdep->prev) + ERTS_PTAB_LIST_ASSERT(ptab->list.data.deleted.start == ptdep); + else + ERTS_PTAB_LIST_ASSERT(ptdep->prev->next == ptdep); + if (!ptdep->next) + ERTS_PTAB_LIST_ASSERT(ptab->list.data.deleted.end == ptdep); + else + ERTS_PTAB_LIST_ASSERT(ptdep->next->prev == ptdep); + if (ptdep->ix < 0) { + Uint64 interval = ptdep->u.bif_invocation.interval; + ERTS_PTAB_LIST_ASSERT(interval <= curr_interval); + } + else { + Uint64 s_interval = ptdep->u.element.inserted; + Uint64 x_interval = ptdep->u.element.deleted; + + ERTS_PTAB_LIST_ASSERT(s_interval <= x_interval); + if (prev_x_interval_p) + ERTS_PTAB_LIST_ASSERT(*prev_x_interval_p <= x_interval); + prev_x_interval_p = &ptdep->u.element.deleted; + ERTS_PTAB_LIST_ASSERT( + erts_ptab_is_valid_id(ptdep->u.element.id)); + ERTS_PTAB_LIST_ASSERT(erts_ptab_id2pix(ptab, + ptdep->u.element.id) + == ptdep->ix); + + } + } + + } +} + +static void +debug_ptab_list_check_del_free_list(ErtsPTab *ptab, + ErtsPTabDeletedElement *free_list) +{ + if (ptab->list.data.deleted.start) { + ErtsPTabDeletedElement *fptdep; + ErtsPTabDeletedElement *ptdep; + + for (fptdep = free_list; fptdep; fptdep = fptdep->next) { + for (ptdep = ptab->list.data.deleted.start; + ptdep; + ptdep = ptdep->next) { + ERTS_PTAB_LIST_ASSERT(fptdep != ptdep); + } + } + } +} + +#endif + +#if ERTS_PTAB_LIST_BIF_DEBUGLEVEL != 0 + +static void +debug_ptab_list_assert_error(char* expr, const char* file, int line, const char *func) +{ + fflush(stdout); + erts_fprintf(stderr, "%s:%d:%s(): Assertion failed: %s\n", + (char *) file, line, (char *) func, expr); + fflush(stderr); + abort(); +} + +#endif |