From 5c039a1fb4979314912dc3af6626d8d7a1c73993 Mon Sep 17 00:00:00 2001 From: Rickard Green Date: Sun, 5 May 2013 19:47:05 +0200 Subject: Introduce a better id allocation algorithm for PTabs --- erts/doc/src/erl.xml | 24 ++- erts/emulator/beam/erl_alloc.c | 18 +- erts/emulator/beam/erl_init.c | 59 ++++-- erts/emulator/beam/erl_process.c | 5 +- erts/emulator/beam/erl_process.h | 2 +- erts/emulator/beam/erl_ptab.c | 342 ++++++++++++++++++++++++++--------- erts/emulator/beam/erl_ptab.h | 13 +- erts/emulator/beam/global.h | 2 +- erts/emulator/beam/io.c | 6 +- erts/emulator/test/process_SUITE.erl | 12 +- 10 files changed, 352 insertions(+), 131 deletions(-) (limited to 'erts') diff --git a/erts/doc/src/erl.xml b/erts/doc/src/erl.xml index 9f5de8a9ae..a7b05899fd 100644 --- a/erts/doc/src/erl.xml +++ b/erts/doc/src/erl.xml @@ -637,10 +637,11 @@

Se also io:printable_range/0.

- +

Sets the maximum number of simultaneously existing processes for this - system. Valid range for Number is [1024-134217727]

+ system if a Number is passed as value. Valid range for + Number is [1024-134217727]

NOTE: The actual maximum chosen may be much larger than the Number passed. Currently the runtime system often, but not always, chooses a value that is a power of 2. This might, @@ -648,11 +649,19 @@ checked by calling erlang:system_info(process_limit).

The default value is 262144

+

If legacy is passed as value, the legacy algorithm for + allocation of process identifiers will be used. Using the legacy + algorithm, identifiers will be allocated in a strictly increasing + fashion until largest possible identifier has been reached. Note that + this algorithm suffers from performance issues and can under certain + circumstances be extremely expensive. The legacy algoritm is deprecated, + and the legacy option is scheduled for removal in OTP-R18.

 - +

Sets the maximum number of simultaneously existing ports for this - system. Valid range for Number is [1024-134217727]

+ system if a Number is passed as value. Valid range for Number + is [1024-134217727]

NOTE: The actual maximum chosen may be much larger than the actual Number passed. Currently the runtime system often, but not always, chooses a value that is a power of 2. This might, @@ -671,6 +680,13 @@ for setting the maximum number of simultaneously existing ports. This environment variable is deprecated, and scheduled for removal in OTP-R17, but can still be used.

+

If legacy is passed as value, the legacy algorithm for + allocation of port identifiers will be used. Using the legacy + algorithm, identifiers will be allocated in a strictly increasing + fashion until largest possible identifier has been reached. Note that + this algorithm suffers from performance issues and can under certain + circumstances be extremely expensive. The legacy algoritm is deprecated, + and the legacy option is scheduled for removal in OTP-R18.

 diff --git a/erts/emulator/beam/erl_alloc.c b/erts/emulator/beam/erl_alloc.c index d748f86d75..700ca127e6 100644 --- a/erts/emulator/beam/erl_alloc.c +++ b/erts/emulator/beam/erl_alloc.c @@ -2142,7 +2142,6 @@ erts_memory(int *print_to_p, void *print_to_arg, void *proc, Eterm earg) if (want_tot_or_sys || want.processes || want.processes_used) { - int max_processes = erts_ptab_max(&erts_proc); UWord tmp; if (ERTS_MEM_NEED_ALL_ALCU) @@ -2152,7 +2151,7 @@ erts_memory(int *print_to_p, void *print_to_arg, void *proc, Eterm earg) fi, ERTS_ALC_NO_FIXED_SIZES); tmp = alcu_size(ERTS_ALC_A_EHEAP, NULL, 0); } - tmp += max_processes*sizeof(erts_smp_atomic_t); + tmp += erts_ptab_mem_size(&erts_proc); tmp += erts_bif_timer_memory_size(); tmp += erts_tot_link_lh_size(); @@ -2278,13 +2277,11 @@ struct aa_values { Eterm erts_allocated_areas(int *print_to_p, void *print_to_arg, void *proc) { -#define MAX_AA_VALUES (23) +#define MAX_AA_VALUES (24) struct aa_values values[MAX_AA_VALUES]; Eterm res = THE_NON_VALUE; int i, length; Uint reserved_atom_space, atom_space; - int max_processes = erts_ptab_max(&erts_proc); - int max_ports = erts_ptab_max(&erts_port); if (proc) { ERTS_SMP_LC_ASSERT(ERTS_PROC_LOCK_MAIN @@ -2315,8 +2312,8 @@ erts_allocated_areas(int *print_to_p, void *print_to_arg, void *proc) values[i].arity = 2; values[i].name = "static"; - values[i].ui[0] = - max_ports*sizeof(erts_smp_atomic_t) /* Port table */ + values[i].ui[0] = + sizeof(ErtsPTab)*2 /* proc & port tables */ + erts_timer_wheel_memory_size(); /* Timer wheel */ i++; @@ -2395,7 +2392,12 @@ erts_allocated_areas(int *print_to_p, void *print_to_arg, void *proc) values[i].arity = 2; values[i].name = "process_table"; - values[i].ui[0] = max_processes*sizeof(Process*); + values[i].ui[0] = erts_ptab_mem_size(&erts_proc); + i++; + + values[i].arity = 2; + values[i].name = "port_table"; + values[i].ui[0] = erts_ptab_mem_size(&erts_port); i++; values[i].arity = 2; diff --git a/erts/emulator/beam/erl_init.c b/erts/emulator/beam/erl_init.c index e6a96d427f..b5bac2151d 100644 --- a/erts/emulator/beam/erl_init.c +++ b/erts/emulator/beam/erl_init.c @@ -131,8 +131,10 @@ extern void ConWaitForExit(void); static void erl_init(int ncpu, int proc_tab_sz, + int legacy_proc_tab, int port_tab_sz, - int port_tab_sz_ignore_files); + int port_tab_sz_ignore_files, + int legacy_port_tab); static erts_atomic_t exiting; @@ -280,7 +282,9 @@ erts_short_init(void) int ncpu = early_init(NULL, NULL); erl_init(ncpu, ERTS_DEFAULT_MAX_PROCESSES, + 0, ERTS_DEFAULT_MAX_PORTS, + 0, 0); erts_initialized = 1; } @@ -288,8 +292,10 @@ erts_short_init(void) static void erl_init(int ncpu, int proc_tab_sz, + int legacy_proc_tab, int port_tab_sz, - int port_tab_sz_ignore_files) + int port_tab_sz_ignore_files, + int legacy_port_tab) { init_benchmarking(); @@ -297,7 +303,7 @@ erl_init(int ncpu, erts_init_gc(); erts_init_time(); erts_init_sys_common_misc(); - erts_init_process(ncpu, proc_tab_sz); + erts_init_process(ncpu, proc_tab_sz, legacy_proc_tab); erts_init_scheduling(no_schedulers, no_schedulers_online); erts_init_cpu_topology(); /* Must be after init_scheduling */ @@ -327,7 +333,7 @@ erl_init(int ncpu, init_dist(); erl_drv_thr_init(); erts_init_async(); - erts_init_io(port_tab_sz, port_tab_sz_ignore_files); + erts_init_io(port_tab_sz, port_tab_sz_ignore_files, legacy_port_tab); init_load(); erts_init_bif(); erts_init_bif_chksum(); @@ -923,6 +929,9 @@ erl_start(int argc, char **argv) int proc_tab_sz = ERTS_DEFAULT_MAX_PROCESSES; int port_tab_sz = ERTS_DEFAULT_MAX_PORTS; int port_tab_sz_ignore_files = 0; + int legacy_proc_tab = 0; + int legacy_port_tab = 0; + envbufsz = sizeof(envbuf); if (erts_sys_getenv_raw(ERL_MAX_ETS_TABLES_ENV, envbuf, &envbufsz) == 0) @@ -1268,27 +1277,35 @@ erl_start(int argc, char **argv) case 'P': /* set maximum number of processes */ arg = get_arg(argv[i]+2, argv[i+1], &i); - errno = 0; - proc_tab_sz = strtol(arg, NULL, 10); - if (errno != 0 - || proc_tab_sz < ERTS_MIN_PROCESSES - || ERTS_MAX_PROCESSES < proc_tab_sz) { - erts_fprintf(stderr, "bad number of processes %s\n", arg); - erts_usage(); + if (strcmp(arg, "legacy") == 0) + legacy_proc_tab = 1; + else { + errno = 0; + proc_tab_sz = strtol(arg, NULL, 10); + if (errno != 0 + || proc_tab_sz < ERTS_MIN_PROCESSES + || ERTS_MAX_PROCESSES < proc_tab_sz) { + erts_fprintf(stderr, "bad number of processes %s\n", arg); + erts_usage(); + } } break; case 'Q': /* set maximum number of ports */ arg = get_arg(argv[i]+2, argv[i+1], &i); - errno = 0; - port_tab_sz = strtol(arg, NULL, 10); - if (errno != 0 - || port_tab_sz < ERTS_MIN_PROCESSES - || ERTS_MAX_PROCESSES < port_tab_sz) { - erts_fprintf(stderr, "bad number of ports %s\n", arg); - erts_usage(); + if (strcmp(arg, "legacy") == 0) + legacy_port_tab = 1; + else { + errno = 0; + port_tab_sz = strtol(arg, NULL, 10); + if (errno != 0 + || port_tab_sz < ERTS_MIN_PROCESSES + || ERTS_MAX_PROCESSES < port_tab_sz) { + erts_fprintf(stderr, "bad number of ports %s\n", arg); + erts_usage(); + } + port_tab_sz_ignore_files = 1; } - port_tab_sz_ignore_files = 1; break; case 'S' : /* Was handled in early_init() just read past it */ @@ -1642,8 +1659,10 @@ erl_start(int argc, char **argv) erl_init(ncpu, proc_tab_sz, + legacy_proc_tab, port_tab_sz, - port_tab_sz_ignore_files); + port_tab_sz_ignore_files, + legacy_port_tab); load_preloaded(); erts_end_staging_code_ix(); diff --git a/erts/emulator/beam/erl_process.c b/erts/emulator/beam/erl_process.c index f9ef4eac65..5cf18735fd 100644 --- a/erts/emulator/beam/erl_process.c +++ b/erts/emulator/beam/erl_process.c @@ -485,7 +485,7 @@ release_process(void *vproc) /* initialize the scheduler */ void -erts_init_process(int ncpu, int proc_tab_size) +erts_init_process(int ncpu, int proc_tab_size, int legacy_proc_tab) { #ifdef ERTS_SMP @@ -505,7 +505,8 @@ erts_init_process(int ncpu, int proc_tab_size) (ErtsPTabElementCommon *) &erts_invalid_process.common, proc_tab_size, sizeof(Process), - "process_table"); + "process_table", + legacy_proc_tab); last_reductions = 0; last_exact_reductions = 0; diff --git a/erts/emulator/beam/erl_process.h b/erts/emulator/beam/erl_process.h index 3d3579fa7e..9bf3bf097d 100644 --- a/erts/emulator/beam/erl_process.h +++ b/erts/emulator/beam/erl_process.h @@ -1351,7 +1351,7 @@ void erts_schedule_multi_misc_aux_work(int ignore_self, erts_aint32_t erts_set_aux_work_timeout(int, erts_aint32_t, int); void erts_sched_notify_check_cpu_bind(void); Uint erts_active_schedulers(void); -void erts_init_process(int, int); +void erts_init_process(int, int, int); Eterm erts_process_status(Process *, ErtsProcLocks, Process *, Eterm); Uint erts_run_queues_len(Uint *); void erts_add_to_runq(Process *); diff --git a/erts/emulator/beam/erl_ptab.c b/erts/emulator/beam/erl_ptab.c index 5bbc71c659..8da135b2c8 100644 --- a/erts/emulator/beam/erl_ptab.c +++ b/erts/emulator/beam/erl_ptab.c @@ -34,6 +34,8 @@ typedef struct ErtsPTabListBifData_ ErtsPTabListBifData; +#define ERTS_PTAB_NEW_MAX_RESERVE_FAIL 1000 + #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 \ @@ -415,6 +417,27 @@ last_data_cmp(Uint64 ld1, Uint64 ld2) #define ERTS_PTAB_LastData2EtermData(LD) \ ((Eterm) ((LD) & ~(~((Uint64) 0) << ERTS_PTAB_ID_DATA_SIZE))) +static ERTS_INLINE Uint32 +ix_to_free_id_data_ix(ErtsPTab *ptab, Uint32 ix) +{ + Uint32 dix; + + dix = ((ix & ptab->r.o.dix_cl_mask) << ptab->r.o.dix_cl_shift); + dix += ((ix >> ptab->r.o.dix_cli_shift) & ptab->r.o.dix_cli_mask); + ASSERT(0 <= dix && dix < ptab->r.o.max); + return dix; +} + +UWord +erts_ptab_mem_size(ErtsPTab *ptab) +{ + UWord size = ptab->r.o.max*sizeof(erts_smp_atomic_t); + if (ptab->r.o.free_id_data) + size += ptab->r.o.max*sizeof(Uint32); + return size; +} + + void erts_ptab_init_table(ErtsPTab *ptab, ErtsAlcType_t atype, @@ -422,10 +445,11 @@ erts_ptab_init_table(ErtsPTab *ptab, ErtsPTabElementCommon *invalid_element, int size, UWord element_size, - char *name) + char *name, + int legacy) { - size_t tab_sz; - int bits; + size_t tab_sz, alloc_sz; + Uint32 bits, cl, cli, ix, ix_per_cache_line, tab_cache_lines; char *tab_end; erts_smp_atomic_t *tab_entry; erts_smp_rwmtx_opt_t rwmtx_opts = ERTS_SMP_RWMTX_OPT_DEFAULT_INITER; @@ -448,7 +472,10 @@ erts_ptab_init_table(ErtsPTab *ptab, 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); + alloc_sz = tab_sz; + if (!legacy) + alloc_sz += ERTS_ALC_CACHE_LINE_ALIGN_SIZE(size*sizeof(Uint32)); + ptab->r.o.tab = erts_alloc_permanent_cache_aligned(atype, alloc_sz); tab_end = ((char *) ptab->r.o.tab) + tab_sz; tab_entry = ptab->r.o.tab; while (tab_end > ((char *) tab_entry)) { @@ -456,28 +483,57 @@ erts_ptab_init_table(ErtsPTab *ptab, 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)); + tab_cache_lines = tab_sz/ERTS_CACHE_LINE_SIZE; + ix_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((ix_per_cache_line & (ix_per_cache_line - 1)) == 0); /* power of 2 */ + ASSERT((tab_cache_lines & (tab_cache_lines - 1)) == 0); /* power of 2 */ + + ptab->r.o.pix_mask = (1 << bits) - 1; + ptab->r.o.pix_cl_mask = tab_cache_lines-1; + ptab->r.o.pix_cl_shift = erts_fit_in_bits_int32(ix_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); + if (legacy) { + ptab->r.o.free_id_data = NULL; + ptab->r.o.dix_cl_mask = 0; + ptab->r.o.dix_cl_shift = 0; + ptab->r.o.dix_cli_shift = 0; + ptab->r.o.dix_cli_mask = 0; + } + else { + + tab_sz = ERTS_ALC_CACHE_LINE_ALIGN_SIZE(size*sizeof(Uint32)); + ptab->r.o.free_id_data = (Uint32 *) tab_end; + + tab_cache_lines = tab_sz/ERTS_CACHE_LINE_SIZE; + ix_per_cache_line = (ERTS_CACHE_LINE_SIZE/sizeof(Uint32)); + + ptab->r.o.dix_cl_mask = tab_cache_lines-1; + ptab->r.o.dix_cl_shift = erts_fit_in_bits_int32(ix_per_cache_line-1); + ptab->r.o.dix_cli_shift = erts_fit_in_bits_int32(ptab->r.o.dix_cl_mask); + ptab->r.o.dix_cli_mask = (1 << (bits - ptab->r.o.dix_cli_shift)) - 1; + + ASSERT((ix_per_cache_line & (ix_per_cache_line - 1)) == 0); /* power of 2 */ + ASSERT((tab_cache_lines & (tab_cache_lines - 1)) == 0); /* power of 2 */ + + ASSERT(ptab->r.o.dix_cl_shift + ptab->r.o.dix_cli_shift == bits); + + ix = 0; + for (cl = 0; cl < tab_cache_lines; cl++) { + for (cli = 0; cli < ix_per_cache_line; cli++) { + ptab->r.o.free_id_data[ix] = cli*tab_cache_lines+cl; + ix++; + } + } + + erts_smp_atomic32_init_nob(&ptab->vola.tile.aid_ix, -1); + erts_smp_atomic32_init_nob(&ptab->vola.tile.fid_ix, -1); + + } 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; @@ -522,9 +578,7 @@ erts_ptab_new_element(ErtsPTab *ptab, void *init_arg, void (*init_ptab_el)(void *, Eterm)) { - int pix; - Uint64 ld, exp_ld; - Eterm data; + Uint32 pix, ix, data; erts_aint32_t count; erts_aint_t invalid = (erts_aint_t) ptab->r.o.invalid_element; @@ -551,62 +605,108 @@ erts_ptab_new_element(ErtsPTab *ptab, ptab_el->u.alive.started_interval = erts_smp_current_interval_nob(erts_ptab_interval(ptab)); - ld = last_data_read_acqb(ptab); + if (ptab->r.o.free_id_data) { - /* 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); + ix = (Uint32) erts_smp_atomic32_inc_read_acqb(&ptab->vola.tile.aid_ix); + ix = ix_to_free_id_data_ix(ptab, ix); + + data = ptab->r.o.free_id_data[ix]; + + init_ptab_el(init_arg, (Eterm) data); + +#ifdef ERTS_SMP + erts_smp_atomic32_init_nob(&ptab_el->refc, 1); +#endif + + pix = erts_ptab_data2pix(ptab, (Eterm) data); + +#ifdef DEBUG + ASSERT(ERTS_AINT_NULL == 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); - if (ERTS_AINT_NULL == val) - break; - } } + else { + int rlocked = ERTS_PTAB_NEW_MAX_RESERVE_FAIL; + Uint64 ld, exp_ld; + /* Deprecated legacy algorithm... */ + + restart: + + ptab_el->u.alive.started_interval + = erts_smp_current_interval_nob(erts_ptab_interval(ptab)); - data = ERTS_PTAB_LastData2EtermData(ld); + 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; + } + if (rlocked && --rlocked == 0) { + erts_ptab_runlock(ptab); + erts_ptab_rwlock(ptab); + goto restart; + } + } - 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); + 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); + } - /* 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; - } + 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); + init_ptab_el(init_arg, data); #ifdef ERTS_SMP - erts_smp_atomic32_init_nob(&ptab_el->refc, 1); + erts_smp_atomic32_init_nob(&ptab_el->refc, 1); #endif - /* Move into slot reserved */ + /* Move into slot reserved */ #ifdef DEBUG - ASSERT(invalid == erts_smp_atomic_xchg_relb(&ptab->r.o.tab[pix], + 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); + erts_smp_atomic_set_relb(&ptab->r.o.tab[pix], (erts_aint_t) ptab_el); #endif - erts_ptab_runlock(ptab); + if (rlocked) + erts_ptab_runlock(ptab); + else + erts_ptab_rwunlock(ptab); + + } return 1; } @@ -647,7 +747,9 @@ erts_ptab_delete_element(ErtsPTab *ptab, ErtsPTabElementCommon *ptab_el) { int maybe_save; - int pix = erts_ptab_id2pix(ptab, ptab_el->id); + Uint32 pix, ix, data; + + pix = erts_ptab_id2pix(ptab, ptab_el->id); ASSERT(erts_get_scheduler_id()); /* *Need* to be a scheduler */ @@ -660,6 +762,26 @@ erts_ptab_delete_element(ErtsPTab *ptab, erts_smp_atomic_set_relb(&ptab->r.o.tab[pix], ERTS_AINT_NULL); + if (ptab->r.o.free_id_data) { + + /* Next data for this slot... */ + data = (Uint32) erts_ptab_id2data(ptab, ptab_el->id); + data += ptab->r.o.max; + data &= ~(~((Uint32) 0) << ERTS_PTAB_ID_DATA_SIZE); + if (data == ptab->r.o.invalid_data) { /* make sure not invalid */ + data += ptab->r.o.max; + data &= ~(~((Uint32) 0) << ERTS_PTAB_ID_DATA_SIZE); + } + + ASSERT(data != ptab->r.o.invalid_data); + ASSERT(pix == erts_ptab_data2pix(ptab, data)); + + ix = (Uint32) erts_smp_atomic32_inc_read_relb(&ptab->vola.tile.fid_ix); + ix = ix_to_free_id_data_ix(ptab, ix); + + ptab->r.o.free_id_data[ix] = data; + } + ASSERT(erts_smp_atomic32_read_nob(&ptab->vola.tile.count) > 0); erts_smp_atomic32_dec_relb(&ptab->vola.tile.count); @@ -1280,42 +1402,86 @@ erts_ptab_test_next_id(ErtsPTab *ptab, int set, Uint next) erts_ptab_rwlock(ptab); - if (!set) - ld = last_data_read_nob(ptab); - else { + if (ptab->r.o.free_id_data) { + Uint32 aid_ix, dix; - 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))); + if (set) { + Uint32 max_ix, ser, num, start; + max_ix = ptab->r.o.max - 1; + ser = next & ~max_ix; + start = num = next & max_ix; + + aid_ix = (Uint32) erts_smp_atomic32_read_nob(&ptab->vola.tile.aid_ix) + 1; + + do { + Uint32 pix = erts_ptab_data2pix(ptab, num); + if (ERTS_AINT_NULL == erts_ptab_pix2intptr_nob(ptab, pix)) { + dix = ix_to_free_id_data_ix(ptab, aid_ix); + ptab->r.o.free_id_data[dix] = ser + num; + ASSERT(pix == erts_ptab_data2pix(ptab, ser+num)); + if (aid_ix == max_ix) + aid_ix = 0; + else + aid_ix++; + } + if (num == max_ix) + num = 0; + else + num++; + } while (num != start); + +#ifdef DEBUG + if (aid_ix == 0) + aid_ix = max_ix; + else + aid_ix--; + ASSERT((aid_ix & max_ix) == (((Uint32) erts_atomic32_read_nob(&ptab->vola.tile.fid_ix)) & max_ix)); +#endif } - last_data_set_relb(ptab, ld); + + aid_ix = (Uint32) erts_smp_atomic32_read_nob(&ptab->vola.tile.aid_ix) + 1; + dix = ix_to_free_id_data_ix(ptab, aid_ix); + res = (Sint) ptab->r.o.free_id_data[dix]; } + else { + /* Deprecated legacy algorithm... */ + if (!set) + ld = last_data_read_nob(ptab); + else { - 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)) { + 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; } - res = data; - break; } } diff --git a/erts/emulator/beam/erl_ptab.h b/erts/emulator/beam/erl_ptab.h index 7fa1251900..84ff7d0de4 100644 --- a/erts/emulator/beam/erl_ptab.h +++ b/erts/emulator/beam/erl_ptab.h @@ -94,18 +94,23 @@ typedef struct { erts_smp_atomic_t last_data; #endif erts_smp_atomic32_t count; + erts_smp_atomic32_t aid_ix; + erts_smp_atomic32_t fid_ix; } ErtsPTabVolatileData; typedef struct { erts_smp_atomic_t *tab; + Uint32 *free_id_data; Uint32 max; - Uint32 tab_cache_lines; - Uint32 pix_per_cache_line; Uint32 pix_mask; Uint32 pix_cl_mask; Uint32 pix_cl_shift; Uint32 pix_cli_mask; Uint32 pix_cli_shift; + Uint32 dix_cl_mask; + Uint32 dix_cl_shift; + Uint32 dix_cli_mask; + Uint32 dix_cli_shift; ErtsPTabElementCommon *invalid_element; Eterm invalid_data; void (*release_element)(void *); @@ -179,7 +184,8 @@ void erts_ptab_init_table(ErtsPTab *ptab, ErtsPTabElementCommon *invalid_element, int size, UWord element_size, - char *name); + char *name, + int legacy); int erts_ptab_new_element(ErtsPTab *ptab, ErtsPTabElementCommon *ptab_el, void *init_arg, @@ -187,6 +193,7 @@ int erts_ptab_new_element(ErtsPTab *ptab, void erts_ptab_delete_element(ErtsPTab *ptab, ErtsPTabElementCommon *ptab_el); int erts_ptab_initialized(ErtsPTab *ptab); +UWord erts_ptab_mem_size(ErtsPTab *ptab); ERTS_GLB_INLINE erts_interval_t *erts_ptab_interval(ErtsPTab *ptab); ERTS_GLB_INLINE int erts_ptab_max(ErtsPTab *ptab); diff --git a/erts/emulator/beam/global.h b/erts/emulator/beam/global.h index 012c1c7e6a..c900cdca39 100755 --- a/erts/emulator/beam/global.h +++ b/erts/emulator/beam/global.h @@ -724,7 +724,7 @@ int erts_add_driver_entry(ErlDrvEntry *drv, DE_Handle *handle, int driver_list_l void erts_destroy_driver(erts_driver_t *drv); int erts_save_suspend_process_on_port(Port*, Process*); Port *erts_open_driver(erts_driver_t*, Eterm, char*, SysDriverOpts*, int *, int *); -void erts_init_io(int, int); +void erts_init_io(int, int, int); void erts_raw_port_command(Port*, byte*, Uint); void driver_report_exit(ErlDrvPort, int); LineBuf* allocate_linebuf(int); diff --git a/erts/emulator/beam/io.c b/erts/emulator/beam/io.c index 43918a7141..e89dd89f6a 100644 --- a/erts/emulator/beam/io.c +++ b/erts/emulator/beam/io.c @@ -2648,7 +2648,8 @@ erts_port_link(Process *c_p, Port *prt, Eterm to, Eterm *refp) } void erts_init_io(int port_tab_size, - int port_tab_size_ignore_files) + int port_tab_size_ignore_files, + int legacy_port_tab) { ErlDrvEntry** dp; UWord common_element_size; @@ -2691,7 +2692,8 @@ void erts_init_io(int port_tab_size, (ErtsPTabElementCommon *) &erts_invalid_port.common, port_tab_size, common_element_size, /* Doesn't need to be excact */ - "port_table"); + "port_table", + legacy_port_tab); erts_smp_atomic_init_nob(&erts_bytes_out, 0); erts_smp_atomic_init_nob(&erts_bytes_in, 0); diff --git a/erts/emulator/test/process_SUITE.erl b/erts/emulator/test/process_SUITE.erl index 863cd2d654..72f3e8fe85 100644 --- a/erts/emulator/test/process_SUITE.erl +++ b/erts/emulator/test/process_SUITE.erl @@ -1494,6 +1494,7 @@ processes_bif_cleaner() -> spawn_initial_hangarounds(Cleaner) -> TabSz = erlang:system_info(process_limit), + erts_debug:set_internal_state(next_pid,TabSz), spawn_initial_hangarounds(Cleaner, TabSz, TabSz*2, @@ -1538,14 +1539,21 @@ hangaround(Cleaner, Type) -> spawn_initial_hangarounds(_Cleaner, NP, Max, Len, HAs) when NP > Max -> {Len, HAs}; spawn_initial_hangarounds(Cleaner, NP, Max, Len, HAs) -> - erts_debug:set_internal_state(next_pid,NP), + Skip = 30, HA1 = spawn_opt(?MODULE, hangaround, [Cleaner, initial_hangaround], [{priority, low}]), HA2 = spawn_opt(?MODULE, hangaround, [Cleaner, initial_hangaround], [{priority, normal}]), HA3 = spawn_opt(?MODULE, hangaround, [Cleaner, initial_hangaround], [{priority, high}]), - spawn_initial_hangarounds(Cleaner, NP+30, Max, Len+3, [HA1,HA2,HA3|HAs]). + spawn_drop(Skip), + spawn_initial_hangarounds(Cleaner, NP+Skip, Max, Len+3, [HA1,HA2,HA3|HAs]). + +spawn_drop(N) when N =< 0 -> + ok; +spawn_drop(N) -> + spawn(fun () -> ok end), + spawn_drop(N-1). do_processes(WantReds) -> erts_debug:set_internal_state(reds_left, WantReds), -- cgit v1.2.3