From e16f287c28ac93b54772169958c965733aa67e66 Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Thu, 25 Sep 2014 22:50:24 +0200 Subject: erts: Add pooled_list and traitor_list --- erts/emulator/beam/erl_alloc_util.c | 300 +++++++++++++++++++++++++++++++----- erts/emulator/beam/erl_alloc_util.h | 13 +- 2 files changed, 272 insertions(+), 41 deletions(-) (limited to 'erts/emulator/beam') diff --git a/erts/emulator/beam/erl_alloc_util.c b/erts/emulator/beam/erl_alloc_util.c index 55052430e1..ba16e5c3a3 100644 --- a/erts/emulator/beam/erl_alloc_util.c +++ b/erts/emulator/beam/erl_alloc_util.c @@ -205,7 +205,7 @@ MBC after deallocating first block: ASSERT(((UWord)(F) & (~FLG_MASK|THIS_FREE_BLK_HDR_FLG|PREV_FREE_BLK_HDR_FLG)) == THIS_FREE_BLK_HDR_FLG), \ (B)->bhdr = ((Sz) | (F)), \ (B)->u.carrier = (C)) - + # define IS_MBC_FIRST_ABLK(AP,B) \ ((((UWord)(B) & ~ERTS_SACRR_UNIT_MASK) == MBC_HEADER_SIZE(AP)) \ && ((B)->bhdr & MBC_ABLK_OFFSET_MASK) == 0) @@ -378,9 +378,8 @@ do { \ #ifdef ERTS_SMP #define SBC_HEADER_SIZE \ - (UNIT_CEILING(sizeof(Carrier_t) \ - - sizeof(ErtsAlcCPoolData_t) \ - + ABLK_HDR_SZ) \ + (UNIT_CEILING(offsetof(Carrier_t, cpool) \ + + ABLK_HDR_SZ) \ - ABLK_HDR_SZ) #else #define SBC_HEADER_SIZE \ @@ -929,6 +928,88 @@ unlink_carrier(CarrierList_t *cl, Carrier_t *crr) #ifdef ERTS_SMP +#ifdef DEBUG +static int is_in_list(ErtsDoubleLink_t* sentinel, ErtsDoubleLink_t* node) +{ + ErtsDoubleLink_t* p; + + ASSERT(node != sentinel); + for (p = sentinel->next; p != sentinel; p = p->next) { + if (p == node) + return 1; + } + return 0; +} +#endif /* DEBUG */ + +static ERTS_INLINE void +link_edl_after(ErtsDoubleLink_t* after_me, ErtsDoubleLink_t* node) +{ + ErtsDoubleLink_t* before_me = after_me->next; + ASSERT(node != after_me && node != before_me); + node->next = before_me; + node->prev = after_me; + before_me->prev = node; + after_me->next = node; +} + +static ERTS_INLINE void +link_edl_before(ErtsDoubleLink_t* before_me, ErtsDoubleLink_t* node) +{ + ErtsDoubleLink_t* after_me = before_me->prev; + ASSERT(node != before_me && node != after_me); + node->next = before_me; + node->prev = after_me; + before_me->prev = node; + after_me->next = node; +} + +static ERTS_INLINE void +unlink_edl(ErtsDoubleLink_t* node) +{ + node->next->prev = node->prev; + node->prev->next = node->next; +} + +static ERTS_INLINE void +relink_edl_before(ErtsDoubleLink_t* before_me, ErtsDoubleLink_t* node) +{ + if (node != before_me && node != before_me->prev) { + unlink_edl(node); + link_edl_before(before_me, node); + } +} + +static ERTS_INLINE int is_abandoned(Carrier_t *crr) +{ + return crr->cpool.abandoned.next != NULL; +} + +static ERTS_INLINE void +link_abandoned_carrier(ErtsDoubleLink_t* list, Carrier_t *crr) +{ + ASSERT(!is_abandoned(crr)); + + link_edl_after(list, &crr->cpool.abandoned); + + ASSERT(crr->cpool.abandoned.next != &crr->cpool.abandoned); + ASSERT(crr->cpool.abandoned.prev != &crr->cpool.abandoned); +} + +static ERTS_INLINE void +unlink_abandoned_carrier(Carrier_t *crr) +{ + ASSERT(is_in_list(&crr->cpool.orig_allctr->cpool.pooled_list, + &crr->cpool.abandoned) || + is_in_list(&crr->cpool.orig_allctr->cpool.traitor_list, + &crr->cpool.abandoned)); + + unlink_edl(&crr->cpool.abandoned); + + crr->cpool.abandoned.next = NULL; + crr->cpool.abandoned.prev = NULL; +} + static ERTS_INLINE void clear_busy_pool_carrier(Allctr_t *allctr, Carrier_t *crr) { @@ -955,7 +1036,7 @@ clear_busy_pool_carrier(Allctr_t *allctr, Carrier_t *crr) } } -#endif +#endif /* ERTS_SMP */ #if 0 #define ERTS_DBG_CHK_FIX_LIST(A, FIX, IX, B) \ @@ -2575,10 +2656,9 @@ mbc_realloc(Allctr_t *allctr, void *p, Uint size, Uint32 alcu_flgs, #ifdef ERTS_SMP #define ERTS_ALC_MAX_DEALLOC_CARRIER 10 -#define ERTS_ALC_CPOOL_MAX_FETCH_INSPECT 10 +#define ERTS_ALC_CPOOL_MAX_FETCH_INSPECT 20 +#define ERTS_ALC_CPOOL_MAX_TRAITOR_INSPECT 10 #define ERTS_ALC_CPOOL_CHECK_LIMIT_COUNT 100 -#define ERTS_ALC_CPOOL_MAX_NO_CARRIERS 5 -#define ERTS_ALC_CPOOL_INSERT_ALLOWED_OFFSET 100 #define ERTS_ALC_CPOOL_MAX_FAILED_STAT_READS 3 #define ERTS_ALC_CPOOL_PTR_MOD_MRK (((erts_aint_t) 1) << 0) @@ -2916,59 +2996,163 @@ cpool_delete(Allctr_t *allctr, Allctr_t *prev_allctr, Carrier_t *crr) static Carrier_t * cpool_fetch(Allctr_t *allctr, UWord size) { - int i; + int i, i_stop, has_passed_sentinel; Carrier_t *crr; ErtsAlcCPoolData_t *cpdp; - ErtsAlcCPoolData_t *sentinel = &carrier_pool[allctr->alloc_no].sentinel; + ErtsAlcCPoolData_t *cpool_entrance; + ErtsAlcCPoolData_t *sentinel; + ErtsDoubleLink_t* dl; + ErtsDoubleLink_t* first_old_traitor; ERTS_ALC_CPOOL_ASSERT(allctr->alloc_no == ERTS_ALC_A_INVALID /* testcase */ || erts_thr_progress_is_managed_thread()); - i = 0; + i = ERTS_ALC_CPOOL_MAX_FETCH_INSPECT; + first_old_traitor = allctr->cpool.traitor_list.next; + cpool_entrance = NULL; - /* First; check our own pending dealloc carrier list... */ - crr = allctr->cpool.dc_list.last; - while (crr && i < ERTS_ALC_CPOOL_MAX_FETCH_INSPECT) { - if (erts_atomic_read_nob(&crr->cpool.max_size) >= size) { - unlink_carrier(&allctr->cpool.dc_list, crr); -#ifdef ERTS_ALC_CPOOL_DEBUG - ERTS_ALC_CPOOL_ASSERT(erts_smp_atomic_xchg_nob(&crr->allctr, - ((erts_aint_t) allctr)) - == (((erts_aint_t) allctr) & ~ERTS_CRR_ALCTR_FLG_MASK)); -#else - erts_smp_atomic_set_nob(&crr->allctr, ((erts_aint_t) allctr)); -#endif - return crr; + /* + * Search my own pooled_list, + * i.e my abandoned carriers that were in the pool last time I checked. + */ + + dl = allctr->cpool.pooled_list.next; + while(dl != &allctr->cpool.pooled_list) { + erts_aint_t exp, act; + crr = (Carrier_t *) (((char *) dl) - offsetof(Carrier_t, cpool.abandoned)); + + ASSERT(!is_in_list(&allctr->cpool.traitor_list, dl)); + ASSERT(crr->cpool.orig_allctr == allctr); + dl = dl->next; + exp = erts_smp_atomic_read_rb(&crr->allctr); + if ((exp & ERTS_CRR_ALCTR_FLG_MASK) == ERTS_CRR_ALCTR_FLG_IN_POOL + && erts_atomic_read_nob(&crr->cpool.max_size) >= size) { + /* Try to fetch it... */ + act = erts_smp_atomic_cmpxchg_mb(&crr->allctr, + (erts_aint_t) allctr, + exp); + if (act == exp) { + cpool_delete(allctr, ((Allctr_t *) (act & ~ERTS_CRR_ALCTR_FLG_MASK)), crr); + unlink_abandoned_carrier(crr); + + /* Move sentinel to continue next search from here */ + relink_edl_before(dl, &allctr->cpool.pooled_list); + return crr; + } + exp = act; + } + if (exp & ERTS_CRR_ALCTR_FLG_IN_POOL) { + if (!cpool_entrance) + cpool_entrance = &crr->cpool; + } + else { /* Not in pool, move to traitor_list */ + unlink_abandoned_carrier(crr); + link_abandoned_carrier(&allctr->cpool.traitor_list, crr); + } + if (--i <= 0) { + /* Move sentinel to continue next search from here */ + relink_edl_before(dl, &allctr->cpool.pooled_list); + return NULL; } - crr = crr->prev; - i++; } - /* ... then the pool ... */ + /* Now search traitor_list. + * i.e carriers employed by other allocators last time I checked. + * They might have been abandoned since then. + */ + + i_stop = (i < ERTS_ALC_CPOOL_MAX_TRAITOR_INSPECT ? + 0 : i - ERTS_ALC_CPOOL_MAX_TRAITOR_INSPECT); + dl = first_old_traitor; + while(dl != &allctr->cpool.traitor_list) { + erts_aint_t exp, act; + crr = (Carrier_t *) (((char *) dl) - offsetof(Carrier_t, cpool.abandoned)); + ASSERT(dl != &allctr->cpool.pooled_list); + ASSERT(crr->cpool.orig_allctr == allctr); + dl = dl->next; + exp = erts_smp_atomic_read_rb(&crr->allctr); + if (exp & ERTS_CRR_ALCTR_FLG_IN_POOL) { + if (!(exp & ERTS_CRR_ALCTR_FLG_BUSY) + && erts_atomic_read_nob(&crr->cpool.max_size) >= size) { + /* Try to fetch it... */ + act = erts_smp_atomic_cmpxchg_mb(&crr->allctr, + (erts_aint_t) allctr, + exp); + if (act == exp) { + cpool_delete(allctr, ((Allctr_t *) (act & ~ERTS_CRR_ALCTR_FLG_MASK)), crr); + unlink_abandoned_carrier(crr); + + /* Move sentinel to continue next search from here */ + relink_edl_before(dl, &allctr->cpool.traitor_list); + return crr; + } + exp = act; + } + if (exp & ERTS_CRR_ALCTR_FLG_IN_POOL) { + if (!cpool_entrance) + cpool_entrance = &crr->cpool; + + /* Move to pooled_list */ + unlink_abandoned_carrier(crr); + link_abandoned_carrier(&allctr->cpool.pooled_list, crr); + } + } + if (--i <= i_stop) { + /* Move sentinel to continue next search from here */ + relink_edl_before(dl, &allctr->cpool.traitor_list); + if (i > 0) + break; + else + return NULL; + } + } /* - * We search in 'prev' direction and begin by passing - * one element before trying to fetch. This in order to - * avoid contention with threads inserting elements. + * Finally search the shared pool and try employ foreign carriers */ - cpdp = cpool_aint2cpd(cpool_read(&sentinel->prev)); - if (cpdp == sentinel) - return NULL; + sentinel = &carrier_pool[allctr->alloc_no].sentinel; + if (cpool_entrance) { + /* We saw a pooled carried above, use it as entrance into the pool + */ + cpdp = cpool_entrance; + } + else { + /* No pooled carried seen above. Start search at cpool sentinel, + * but begin by passing one element before trying to fetch. + * This in order to avoid contention with threads inserting elements. + */ + cpool_entrance = sentinel; + cpdp = cpool_aint2cpd(cpool_read(&cpool_entrance->prev)); + if (cpdp == sentinel) + return NULL; + } - while (i < ERTS_ALC_CPOOL_MAX_FETCH_INSPECT) { + has_passed_sentinel = 0; + while (1) { erts_aint_t exp; cpdp = cpool_aint2cpd(cpool_read(&cpdp->prev)); - if (cpdp == sentinel) { + if (cpdp == cpool_entrance) { + if (cpool_entrance == sentinel) { + cpdp = cpool_aint2cpd(cpool_read(&cpdp->prev)); + if (cpdp == sentinel) + return NULL; + } + i = 0; /* Last one to inspect */ + } + else if (cpdp == sentinel) { + if (has_passed_sentinel) { + /* We been here before. cpool_entrance must have been removed */ + return NULL; + } cpdp = cpool_aint2cpd(cpool_read(&cpdp->prev)); if (cpdp == sentinel) return NULL; - i = ERTS_ALC_CPOOL_MAX_FETCH_INSPECT; /* Last one to inspect */ + has_passed_sentinel = 1; } - crr = (Carrier_t *) (((char *) cpdp) - offsetof(Carrier_t, cpool)); + crr = (Carrier_t *)(((char *)cpdp) - offsetof(Carrier_t, cpool)); exp = erts_smp_atomic_read_rb(&crr->allctr); - if (((exp & (ERTS_CRR_ALCTR_FLG_IN_POOL|ERTS_CRR_ALCTR_FLG_BUSY)) - == ERTS_CRR_ALCTR_FLG_IN_POOL) + if (((exp & (ERTS_CRR_ALCTR_FLG_MASK)) == ERTS_CRR_ALCTR_FLG_IN_POOL) && (erts_atomic_read_nob(&cpdp->max_size) >= size)) { erts_aint_t act; /* Try to fetch it... */ @@ -2977,11 +3161,35 @@ cpool_fetch(Allctr_t *allctr, UWord size) exp); if (act == exp) { cpool_delete(allctr, ((Allctr_t *) (act & ~ERTS_CRR_ALCTR_FLG_MASK)), crr); + if (crr->cpool.orig_allctr == allctr) { + unlink_abandoned_carrier(crr); + } return crr; } } - i++; + if (--i <= 0) + return NULL; } + + /* Last; check our own pending dealloc carrier list... */ + crr = allctr->cpool.dc_list.last; + while (crr) { + if (erts_atomic_read_nob(&crr->cpool.max_size) >= size) { + unlink_carrier(&allctr->cpool.dc_list, crr); +#ifdef ERTS_ALC_CPOOL_DEBUG + ERTS_ALC_CPOOL_ASSERT(erts_smp_atomic_xchg_nob(&crr->allctr, + ((erts_aint_t) allctr)) + == (((erts_aint_t) allctr) & ~ERTS_CRR_ALCTR_FLG_MASK)); +#else + erts_smp_atomic_set_nob(&crr->allctr, ((erts_aint_t) allctr)); +#endif + return crr; + } + crr = crr->prev; + if (--i <= 0) + return NULL; + } + return NULL; } @@ -3078,6 +3286,9 @@ schedule_dealloc_carrier(Allctr_t *allctr, Carrier_t *crr) return; } + if (is_abandoned(crr)) + unlink_abandoned_carrier(crr); + if (crr->cpool.thr_prgr == ERTS_THR_PRGR_INVALID || erts_thr_progress_has_reached(crr->cpool.thr_prgr)) { dealloc_carrier(allctr, crr, 1); @@ -3124,6 +3335,8 @@ cpool_init_carrier_data(Allctr_t *allctr, Carrier_t *crr) limit = (csz/100)*allctr->cpool.util_limit; crr->cpool.abandon_limit = limit; } + crr->cpool.abandoned.next = NULL; + crr->cpool.abandoned.prev = NULL; } static void @@ -3154,6 +3367,9 @@ abandon_carrier(Allctr_t *allctr, Carrier_t *crr) STAT_MBC_CPOOL_INSERT(allctr, crr); unlink_carrier(&allctr->mbc_list, crr); + if (crr->cpool.orig_allctr == allctr) { + link_abandoned_carrier(&allctr->cpool.pooled_list, crr); + } allctr->remove_mbc(allctr, crr); @@ -5540,6 +5756,10 @@ erts_alcu_start(Allctr_t *allctr, AllctrInit_t *init) allctr->min_block_size = sz; } + allctr->cpool.pooled_list.next = &allctr->cpool.pooled_list; + allctr->cpool.pooled_list.prev = &allctr->cpool.pooled_list; + allctr->cpool.traitor_list.next = &allctr->cpool.traitor_list; + allctr->cpool.traitor_list.prev = &allctr->cpool.traitor_list; allctr->cpool.dc_list.first = NULL; allctr->cpool.dc_list.last = NULL; allctr->cpool.abandon_limit = 0; diff --git a/erts/emulator/beam/erl_alloc_util.h b/erts/emulator/beam/erl_alloc_util.h index 7be6b1ed9d..eee920e66c 100644 --- a/erts/emulator/beam/erl_alloc_util.h +++ b/erts/emulator/beam/erl_alloc_util.h @@ -268,6 +268,11 @@ typedef union {char c[ERTS_ALLOC_ALIGN_BYTES]; long l; double d;} Unit_t; #ifdef ERTS_SMP +typedef struct ErtsDoubleLink_t_ { + struct ErtsDoubleLink_t_ *next; + struct ErtsDoubleLink_t_ *prev; +}ErtsDoubleLink_t; + typedef struct { erts_atomic_t next; erts_atomic_t prev; @@ -277,6 +282,7 @@ typedef struct { UWord abandon_limit; UWord blocks; UWord blocks_size; + ErtsDoubleLink_t abandoned; /* node in pooled_list or traitor_list */ } ErtsAlcCPoolData_t; #endif @@ -500,7 +506,12 @@ struct Allctr_t_ { CarrierList_t sbc_list; #ifdef ERTS_SMP struct { - CarrierList_t dc_list; + /* pooled_list, traitor list and dc_list contain only + carriers _created_ by this allocator */ + ErtsDoubleLink_t pooled_list; + ErtsDoubleLink_t traitor_list; + CarrierList_t dc_list; + UWord abandon_limit; int disable_abandon; int check_limit_count; -- cgit v1.2.3 From dd853b15e9fb770a3f04fe4504fbfbb8de89e28d Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Mon, 6 Oct 2014 22:29:44 +0200 Subject: erts: Fix bug causing mbc removed from cpool to be used at pool entrance Clear both IN_POOL and BUSY flags when empty carrier is removed is removed from pool to be destroyed. Earlier it was enough to leave BUSY flag set but now with pooled_list we must clear IN_POOL to avoid using it as cpool_entrance in cpool_fetch(). --- erts/emulator/beam/erl_alloc_util.c | 5 +++++ 1 file changed, 5 insertions(+) (limited to 'erts/emulator/beam') diff --git a/erts/emulator/beam/erl_alloc_util.c b/erts/emulator/beam/erl_alloc_util.c index ba16e5c3a3..0ea9b62103 100644 --- a/erts/emulator/beam/erl_alloc_util.c +++ b/erts/emulator/beam/erl_alloc_util.c @@ -3877,6 +3877,11 @@ destroy_carrier(Allctr_t *allctr, Block_t *blk, Carrier_t **busy_pcrr_pp) if (busy_pcrr_pp && *busy_pcrr_pp) { ERTS_ALC_CPOOL_ASSERT(*busy_pcrr_pp == crr); *busy_pcrr_pp = NULL; + ERTS_ALC_CPOOL_ASSERT(erts_smp_atomic_read_nob(&crr->allctr) + == (((erts_aint_t) allctr) + | ERTS_CRR_ALCTR_FLG_IN_POOL + | ERTS_CRR_ALCTR_FLG_BUSY)); + erts_smp_atomic_set_nob(&crr->allctr, ((erts_aint_t) allctr)); cpool_delete(allctr, allctr, crr); } else -- cgit v1.2.3 From 3ca75c7e42ab2c0612ceb5e56f60e7932c40f335 Mon Sep 17 00:00:00 2001 From: Sverker Eriksson Date: Mon, 20 Oct 2014 16:04:44 +0200 Subject: erts: Fix bug causing mbc to be deleted from cpool before it was inserted Set IN_POOL flag _after_ mbc has been actually inserted. Earlier it did not matter if IN_POOL was set early as it was not possible to find a carrier before is was fully inserted. Now when searching pooled_list and traitor_list we must make sure a found carrier has been fully inserted into cpool before removing it. --- erts/emulator/beam/erl_alloc_util.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'erts/emulator/beam') diff --git a/erts/emulator/beam/erl_alloc_util.c b/erts/emulator/beam/erl_alloc_util.c index 0ea9b62103..e3172dc4fb 100644 --- a/erts/emulator/beam/erl_alloc_util.c +++ b/erts/emulator/beam/erl_alloc_util.c @@ -2835,9 +2835,6 @@ cpool_insert(Allctr_t *allctr, Carrier_t *crr) (erts_aint_t) CARRIER_SZ(crr)); erts_atomic_inc_nob(&allctr->cpool.stat.no_carriers); - erts_smp_atomic_set_nob(&crr->allctr, - ((erts_aint_t) allctr)|ERTS_CRR_ALCTR_FLG_IN_POOL); - /* * We search in 'next' direction and begin by passing * one element before trying to insert. This in order to @@ -2896,6 +2893,9 @@ cpool_insert(Allctr_t *allctr, Carrier_t *crr) cpool_set_mod_marked(&cpd2p->prev, (erts_aint_t) &crr->cpool, (erts_aint_t) cpd1p); + + erts_smp_atomic_set_wb(&crr->allctr, + ((erts_aint_t) allctr)|ERTS_CRR_ALCTR_FLG_IN_POOL); } static void -- cgit v1.2.3