From dab61239864044bd942ea7f26f13144b1c1a5098 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn-Egil=20Dahlberg?= Date: Wed, 6 Feb 2013 19:45:42 +0100 Subject: erts: Refactor mseg cache Use double ended cache queues to evict oldest cache first --- erts/emulator/sys/common/erl_mseg.c | 248 +++++++++++++++++++----------------- 1 file changed, 130 insertions(+), 118 deletions(-) diff --git a/erts/emulator/sys/common/erl_mseg.c b/erts/emulator/sys/common/erl_mseg.c index 538eea88d1..772f1df0ce 100644 --- a/erts/emulator/sys/common/erl_mseg.c +++ b/erts/emulator/sys/common/erl_mseg.c @@ -175,6 +175,7 @@ struct cache_t_ { Uint size; void *seg; cache_t *next; + cache_t *prev; }; @@ -183,9 +184,9 @@ typedef struct ErtsMsegAllctr_t_ ErtsMsegAllctr_t; struct mem_kind_t { cache_t cache[MAX_CACHE_SIZE]; - cache_t *cache_unpowered; - cache_t *cache_area[CACHE_AREAS]; - cache_t *cache_free; + cache_t cache_unpowered_node; + cache_t cache_powered_node[CACHE_AREAS]; + cache_t cache_free; Sint cache_size; Uint cache_hits; @@ -516,70 +517,102 @@ do { \ #define ERTS_DBG_MK_CHK_THR_ACCESS(MK) #endif -/* NEW CACHE interface */ +/* Cache interface */ -static ERTS_INLINE cache_t *mseg_cache_alloc_descriptor(MemKind *mk) { - cache_t *c = mk->cache_free; - ERTS_DBG_MK_CHK_THR_ACCESS(mk); - if (c) - mk->cache_free = c->next; +static ERTS_INLINE void mseg_cache_clear_node(cache_t *c) { + c->seg = NULL; + c->size = 0; + c->next = c; + c->prev = c; +} - return c; +static ERTS_INLINE void mseg_cache_unlink_node(cache_t *c) { + c->next->prev = c->prev; + c->prev->next = c->next; + + c->next = c; + c->prev = c; } -static ERTS_INLINE void mseg_cache_free_descriptor(MemKind *mk, cache_t *c) { - ERTS_DBG_MK_CHK_THR_ACCESS(mk); - ASSERT(c); +static ERTS_INLINE void mseg_cache_push_node_front(cache_t *head, cache_t *c) { + c->next = head->next; + c->prev = head; - c->seg = NULL; - c->size = 0; - c->next = mk->cache_free; - mk->cache_free = c; + head->next->prev = c; + head->next = c; + + ASSERT(c->next != c); + ASSERT(c->prev != c); +} + +/* not needed: mseg_cache_push_node_back */ + +static ERTS_INLINE cache_t *mseg_cache_pop_node_front(cache_t *head) { + cache_t *c; + + ASSERT(head->next != head && head->prev != head); + + c = head->next; + + mseg_cache_unlink_node(c); + + return c; } +static ERTS_INLINE cache_t *mseg_cache_pop_node_back(cache_t *head) { + cache_t *c; + + ASSERT(head->next != head && head->prev != head); + + c = head->prev; + + mseg_cache_unlink_node(c); + + return c; +} + +static ERTS_INLINE int mseg_cache_is_empty(cache_t *head) { + + if (head->next == head) { + ASSERT(head->prev == head); + return 1; + } + + ASSERT(head->next != head && head->prev != head); + + return 0; +} + + static ERTS_INLINE int cache_bless_segment(MemKind *mk, void *seg, Uint size) { cache_t *c; ERTS_DBG_MK_CHK_THR_ACCESS(mk); - if (mk->cache_free && MAP_IS_ALIGNED(seg)) { + if (!mseg_cache_is_empty(&(mk->cache_free)) && MAP_IS_ALIGNED(seg)) { + c = mseg_cache_pop_node_front(&(mk->cache_free)); + + c->seg = seg; + c->size = size; + if (IS_2POW(size)) { int ix = SIZE_TO_CACHE_AREA_IDX(size); ASSERT(ix < CACHE_AREAS); ASSERT((1 << (ix + MSEG_ALIGN_BITS)) == size); - /* unlink from free cache list */ - c = mseg_cache_alloc_descriptor(mk); - - /* link to cache area */ - c->seg = seg; - c->size = size; - c->next = mk->cache_area[ix]; - - mk->cache_area[ix] = c; - mk->cache_size++; - - ASSERT(mk->cache_size <= mk->ma->max_cache_size); + mseg_cache_push_node_front(&(mk->cache_powered_node[ix]), c); - return 1; } else { - /* unlink from free cache list */ - c = mseg_cache_alloc_descriptor(mk); - - /* link to cache area */ - c->seg = seg; - c->size = size; - c->next = mk->cache_unpowered; - mk->cache_unpowered = c; - mk->cache_size++; + mseg_cache_push_node_front(&(mk->cache_unpowered_node), c); + } - ASSERT(mk->cache_size <= mk->ma->max_cache_size); + mk->cache_size++; + ASSERT(mk->cache_size <= mk->ma->max_cache_size); - return 1; - } + return 1; } return 0; @@ -590,6 +623,7 @@ static ERTS_INLINE void *cache_get_segment(MemKind *mk, Uint *size_p) { Uint size = *size_p; ERTS_DBG_MK_CHK_THR_ACCESS(mk); + if (IS_2POW(size)) { int i, ix = SIZE_TO_CACHE_AREA_IDX(size); @@ -599,76 +633,63 @@ static ERTS_INLINE void *cache_get_segment(MemKind *mk, Uint *size_p) { for( i = ix; i < CACHE_AREAS; i++) { - if ((c = mk->cache_area[i]) == NULL) + if (mseg_cache_is_empty(&(mk->cache_powered_node[i]))) continue; + c = mseg_cache_pop_node_front(&(mk->cache_powered_node[i])); + ASSERT(IS_2POW(c->size)); - /* unlink from cache area */ - csize = c->size; - seg = c->seg; - mk->cache_area[i] = c->next; - c->next = NULL; + csize = c->size; + seg = c->seg; + mk->cache_size--; mk->cache_hits++; /* link to free cache list */ - mseg_cache_free_descriptor(mk, c); + mseg_cache_clear_node(c); + mseg_cache_push_node_front(&(mk->cache_free), c); ASSERT(!(mk->cache_size < 0)); - /* divvy up the cache - if needed */ - while( i > ix) { - csize = csize >> 1; - /* try to cache half of it */ - if (!cache_bless_segment(mk, (char *)seg + csize, csize)) { - /* wouldn't cache .. destroy it instead */ - mseg_destroy(mk->ma, mk, (char *)seg + csize, csize); - } - i--; + if (csize != size) { + mseg_destroy(mk->ma, mk, (char *)seg + size, csize - size); } - ASSERT(csize == size); + return seg; } } - else if (mk->cache_unpowered) { + else if (!mseg_cache_is_empty(&(mk->cache_unpowered_node))) { void *seg; - cache_t *c, *pc; + cache_t *c; Uint csize; Uint bad_max_abs = mk->ma->abs_max_cache_bad_fit; Uint bad_max_rel = mk->ma->rel_max_cache_bad_fit; - c = mk->cache_unpowered; - pc = c; + c = mk->cache_unpowered_node.next; - while (c) { + while (c != &(mk->cache_unpowered_node)) { csize = c->size; - if (csize >= size && - ((csize - size)*100 < bad_max_rel*size) && - (csize - size) < bad_max_abs ) { + if (csize >= size && + ((csize - size)*100 < bad_max_rel*size) && + (csize - size) < bad_max_abs ) { - /* unlink from cache area */ seg = c->seg; - if (pc == c) { - mk->cache_unpowered = c->next; - } else { - pc->next = c->next; - } + mseg_cache_unlink_node(c); - c->next = NULL; mk->cache_size--; mk->cache_hits++; /* link to free cache list */ - mseg_cache_free_descriptor(mk, c); + mseg_cache_clear_node(c); + mseg_cache_push_node_front(&(mk->cache_free), c); + *size_p = csize; return seg; } - - pc = c; - c = c->next; + c = c->next; } } return NULL; @@ -679,20 +700,17 @@ static ERTS_INLINE void *cache_get_segment(MemKind *mk, Uint *size_p) { * using callbacks from aux-work in the scheduler. */ -static ERTS_INLINE Uint mseg_drop_one_memkind_cache_size(MemKind *mk, cache_t **head) { +static ERTS_INLINE Uint mseg_drop_one_memkind_cache_size(MemKind *mk, cache_t *head) { cache_t *c = NULL; - c = *head; - - ASSERT( c != NULL ); - - *head = c->next; + c = mseg_cache_pop_node_back(head); if (erts_mtrace_enabled) erts_mtrace_crr_free(SEGTYPE, SEGTYPE, c->seg); mseg_destroy(mk->ma, mk, c->seg, c->size); - mseg_cache_free_descriptor(mk, c); + mseg_cache_clear_node(c); + mseg_cache_push_node_front(&(mk->cache_free), c); mk->segments.current.watermark--; mk->cache_size--; @@ -702,30 +720,26 @@ static ERTS_INLINE Uint mseg_drop_one_memkind_cache_size(MemKind *mk, cache_t ** return mk->cache_size; } -static ERTS_INLINE Uint mseg_drop_memkind_cache_size(MemKind *mk, cache_t **head) { - cache_t *c = NULL, *next = NULL; - - c = *head; - ASSERT( c != NULL ); +static ERTS_INLINE Uint mseg_drop_memkind_cache_size(MemKind *mk, cache_t *head) { + cache_t *c = NULL; - while (c) { + while (!mseg_cache_is_empty(head)) { - next = c->next; + c = mseg_cache_pop_node_back(head); if (erts_mtrace_enabled) erts_mtrace_crr_free(SEGTYPE, SEGTYPE, c->seg); mseg_destroy(mk->ma, mk, c->seg, c->size); - mseg_cache_free_descriptor(mk, c); + + mseg_cache_clear_node(c); + mseg_cache_push_node_front(&(mk->cache_free), c); mk->segments.current.watermark--; mk->cache_size--; - c = next; } - *head = NULL; - ASSERT( mk->cache_size >= 0 ); return mk->cache_size; @@ -743,12 +757,12 @@ static Uint mseg_check_memkind_cache(MemKind *mk) { ERTS_DBG_MK_CHK_THR_ACCESS(mk); for (i = 0; i < CACHE_AREAS; i++) { - if (mk->cache_area[i] != NULL) - return mseg_drop_one_memkind_cache_size(mk, &(mk->cache_area[i])); + if (!mseg_cache_is_empty(&(mk->cache_powered_node[i]))) + return mseg_drop_one_memkind_cache_size(mk, &(mk->cache_powered_node[i])); } - if (mk->cache_unpowered) - return mseg_drop_one_memkind_cache_size(mk, &(mk->cache_unpowered)); + if (!mseg_cache_is_empty(&(mk->cache_unpowered_node))) + return mseg_drop_one_memkind_cache_size(mk, &(mk->cache_unpowered_node)); return 0; } @@ -804,17 +818,17 @@ static void mseg_clear_memkind_cache(MemKind *mk) { /* drop pow2 caches */ for (i = 0; i < CACHE_AREAS; i++) { - if (mk->cache_area[i] == NULL) + if (mseg_cache_is_empty(&(mk->cache_powered_node[i]))) continue; - mseg_drop_memkind_cache_size(mk, &(mk->cache_area[i])); - ASSERT(mk->cache_area[i] == NULL); + mseg_drop_memkind_cache_size(mk, &(mk->cache_powered_node[i])); + ASSERT(mseg_cache_is_empty(&(mk->cache_powered_node[i])) == 1); } /* drop varied caches */ - if(mk->cache_unpowered) - mseg_drop_memkind_cache_size(mk, &(mk->cache_unpowered)); + if (!mseg_cache_is_empty(&(mk->cache_unpowered_node))) + mseg_drop_memkind_cache_size(mk, &(mk->cache_unpowered_node)); - ASSERT(mk->cache_unpowered == NULL); + ASSERT(mseg_cache_is_empty(&(mk->cache_unpowered_node)) == 1); ASSERT(mk->cache_size == 0); } @@ -1556,27 +1570,28 @@ erts_mseg_unit_size(void) return MSEG_ALIGNED_SIZE; } + static void mem_kind_init(ErtsMsegAllctr_t *ma, MemKind* mk, const char* name) { int i; + /* Clear all cache headers */ + mseg_cache_clear_node(&(mk->cache_free)); + mseg_cache_clear_node(&(mk->cache_unpowered_node)); + for (i = 0; i < CACHE_AREAS; i++) { - mk->cache_area[i] = NULL; + mseg_cache_clear_node(&(mk->cache_powered_node[i])); } - mk->cache_free = NULL; + /* Populate cache free list */ ASSERT(ma->max_cache_size <= MAX_CACHE_SIZE); for (i = 0; i < ma->max_cache_size; i++) { - mk->cache[i].seg = NULL; - mk->cache[i].size = 0; - mk->cache[i].next = mk->cache_free; - mk->cache_free = &(mk->cache[i]); + mseg_cache_clear_node(&(mk->cache[i])); + mseg_cache_push_node_front(&(mk->cache_free), &(mk->cache[i])); } - mk->cache_unpowered = NULL; - mk->cache_size = 0; mk->cache_hits = 0; @@ -1594,9 +1609,6 @@ static void mem_kind_init(ErtsMsegAllctr_t *ma, MemKind* mk, const char* name) ma->mk_list = mk; } - - - void erts_mseg_init(ErtsMsegInit_t *init) { -- cgit v1.2.3 From 5bce881fa8bb7c61f27697054e8e9408fa87ca2d Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn-Egil=20Dahlberg?= Date: Thu, 7 Feb 2013 18:54:00 +0100 Subject: erts: Evict old cached segments for newer ones --- erts/emulator/beam/erl_alloc_util.c | 10 ++++--- erts/emulator/sys/common/erl_mseg.c | 53 +++++++++++++++++++++++++------------ erts/emulator/sys/common/erl_mseg.h | 7 +++-- 3 files changed, 45 insertions(+), 25 deletions(-) diff --git a/erts/emulator/beam/erl_alloc_util.c b/erts/emulator/beam/erl_alloc_util.c index 187bc2b48b..ac7f420708 100644 --- a/erts/emulator/beam/erl_alloc_util.c +++ b/erts/emulator/beam/erl_alloc_util.c @@ -643,9 +643,9 @@ alcu_mseg_realloc(Allctr_t *allctr, void *seg, Uint old_size, Uint *new_size_p) } static ERTS_INLINE void -alcu_mseg_dealloc(Allctr_t *allctr, void *seg, Uint size) +alcu_mseg_dealloc(Allctr_t *allctr, void *seg, Uint size, Uint flags) { - erts_mseg_dealloc_opt(allctr->alloc_no, seg, size, &allctr->mseg_opt); + erts_mseg_dealloc_opt(allctr->alloc_no, seg, size, flags, &allctr->mseg_opt); INC_CC(allctr->calls.mseg_dealloc); } @@ -2276,7 +2276,7 @@ resize_carrier(Allctr_t *allctr, Block_t *old_blk, Uint umem_sz, UWord flags) (void *) BLK2UMEM(old_blk), MIN(new_blk_sz, old_blk_sz) - ABLK_HDR_SZ); unlink_carrier(&allctr->sbc_list, old_crr); - alcu_mseg_dealloc(allctr, old_crr, old_crr_sz); + alcu_mseg_dealloc(allctr, old_crr, old_crr_sz, ERTS_MSEG_FLG_NONE); } else { /* Old carrier unchanged; restore stat */ @@ -2352,6 +2352,7 @@ destroy_carrier(Allctr_t *allctr, Block_t *blk) Carrier_t *crr; #if HAVE_ERTS_MSEG Uint is_mseg = 0; + Uint mseg_flags = ERTS_MSEG_FLG_NONE; #endif if (IS_SBC_BLK(blk)) { @@ -2398,6 +2399,7 @@ destroy_carrier(Allctr_t *allctr, Block_t *blk) is_mseg++; ASSERT(crr_sz % MSEG_UNIT_SZ == 0); STAT_MSEG_MBC_FREE(allctr, crr_sz); + mseg_flags = ERTS_MSEG_FLG_2POW; } else #endif @@ -2411,7 +2413,7 @@ destroy_carrier(Allctr_t *allctr, Block_t *blk) #if HAVE_ERTS_MSEG if (is_mseg) { - alcu_mseg_dealloc(allctr, crr, crr_sz); + alcu_mseg_dealloc(allctr, crr, crr_sz, mseg_flags); } else #endif diff --git a/erts/emulator/sys/common/erl_mseg.c b/erts/emulator/sys/common/erl_mseg.c index 772f1df0ce..077f705122 100644 --- a/erts/emulator/sys/common/erl_mseg.c +++ b/erts/emulator/sys/common/erl_mseg.c @@ -585,18 +585,20 @@ static ERTS_INLINE int mseg_cache_is_empty(cache_t *head) { } -static ERTS_INLINE int cache_bless_segment(MemKind *mk, void *seg, Uint size) { +static ERTS_INLINE int cache_bless_segment(MemKind *mk, void *seg, Uint size, Uint flags) { cache_t *c; ERTS_DBG_MK_CHK_THR_ACCESS(mk); - if (!mseg_cache_is_empty(&(mk->cache_free)) && MAP_IS_ALIGNED(seg)) { + ASSERT(!MSEG_FLG_IS_2POW(flags) || (MSEG_FLG_IS_2POW(flags) && MAP_IS_ALIGNED(seg) && IS_2POW(size))); + + if (!mseg_cache_is_empty(&(mk->cache_free))) { c = mseg_cache_pop_node_front(&(mk->cache_free)); c->seg = seg; c->size = size; - if (IS_2POW(size)) { + if (MSEG_FLG_IS_2POW(flags)) { int ix = SIZE_TO_CACHE_AREA_IDX(size); ASSERT(ix < CACHE_AREAS); @@ -612,25 +614,42 @@ static ERTS_INLINE int cache_bless_segment(MemKind *mk, void *seg, Uint size) { mk->cache_size++; ASSERT(mk->cache_size <= mk->ma->max_cache_size); + return 1; + } else if (!MSEG_FLG_IS_2POW(flags) && !mseg_cache_is_empty(&(mk->cache_unpowered_node))) { + + /* Evict oldest slot from cache so we can store an unpowered (sbc) segment */ + + c = mseg_cache_pop_node_back(&(mk->cache_unpowered_node)); + + mseg_destroy(mk->ma, mk, c->seg, c->size); + mseg_cache_clear_node(c); + + c->seg = seg; + c->size = size; + + mseg_cache_push_node_front(&(mk->cache_unpowered_node), c); + return 1; } return 0; } -static ERTS_INLINE void *cache_get_segment(MemKind *mk, Uint *size_p) { +static ERTS_INLINE void *cache_get_segment(MemKind *mk, Uint *size_p, Uint flags) { Uint size = *size_p; ERTS_DBG_MK_CHK_THR_ACCESS(mk); - if (IS_2POW(size)) { + if (MSEG_FLG_IS_2POW(flags)) { int i, ix = SIZE_TO_CACHE_AREA_IDX(size); void *seg; cache_t *c; Uint csize; + ASSERT(IS_2POW(size)); + for( i = ix; i < CACHE_AREAS; i++) { if (mseg_cache_is_empty(&(mk->cache_powered_node[i]))) @@ -639,6 +658,7 @@ static ERTS_INLINE void *cache_get_segment(MemKind *mk, Uint *size_p) { c = mseg_cache_pop_node_front(&(mk->cache_powered_node[i])); ASSERT(IS_2POW(c->size)); + ASSERT(MAP_IS_ALIGNED(c->seg)); csize = c->size; seg = c->seg; @@ -887,7 +907,7 @@ mseg_alloc(ErtsMsegAllctr_t *ma, ErtsAlcType_t atype, Uint *size_p, ma->min_seg_size = size; #endif - if (opt->cache && mk->cache_size > 0 && (seg = cache_get_segment(mk, &size)) != NULL) + if (opt->cache && mk->cache_size > 0 && (seg = cache_get_segment(mk, &size, flags)) != NULL) goto done; if ((seg = mseg_create(ma, mk, size)) == NULL) @@ -908,14 +928,13 @@ done: static void mseg_dealloc(ErtsMsegAllctr_t *ma, ErtsAlcType_t atype, void *seg, Uint size, - const ErtsMsegOpt_t *opt) + Uint flags, const ErtsMsegOpt_t *opt) { MemKind* mk = memkind(ma, opt); - ERTS_MSEG_DEALLOC_STAT(mk,size); - if (opt->cache && cache_bless_segment(mk, seg, size)) { + if (opt->cache && cache_bless_segment(mk, seg, size, flags)) { schedule_cache_check(ma); goto done; } @@ -948,7 +967,7 @@ mseg_realloc(ErtsMsegAllctr_t *ma, ErtsAlcType_t atype, void *seg, /* Dealloc old segment if new segment is of size 0 */ if (!(*new_size_p)) { - mseg_dealloc(ma, atype, seg, old_size, opt); + mseg_dealloc(ma, atype, seg, old_size, flags, opt); DEC_CC(ma, dealloc); return NULL; } @@ -1007,7 +1026,7 @@ mseg_realloc(ErtsMsegAllctr_t *ma, ErtsAlcType_t atype, void *seg, else { if (!opt->preserv) { - mseg_dealloc(ma, atype, seg, old_size, opt); + mseg_dealloc(ma, atype, seg, old_size, flags, opt); new_seg = mseg_alloc(ma, atype, &new_size, flags, opt); ASSERT(MAP_IS_ALIGNED(new_seg) || !new_seg); } @@ -1034,7 +1053,7 @@ mseg_realloc(ErtsMsegAllctr_t *ma, ErtsAlcType_t atype, void *seg, new_size = old_size; else { sys_memcpy(((char *) new_seg), ((char *) seg), MIN(new_size, old_size)); - mseg_dealloc(ma, atype, seg, old_size, opt); + mseg_dealloc(ma, atype, seg, old_size, flags, opt); } #endif } @@ -1511,19 +1530,19 @@ erts_mseg_alloc(ErtsAlcType_t atype, Uint *size_p, Uint flags) void erts_mseg_dealloc_opt(ErtsAlcType_t atype, void *seg, - Uint size, const ErtsMsegOpt_t *opt) + Uint size, Uint flags, const ErtsMsegOpt_t *opt) { ErtsMsegAllctr_t *ma = ERTS_MSEG_ALLCTR_OPT(opt); ERTS_MSEG_LOCK(ma); ERTS_DBG_MA_CHK_THR_ACCESS(ma); - mseg_dealloc(ma, atype, seg, size, opt); + mseg_dealloc(ma, atype, seg, size, flags, opt); ERTS_MSEG_UNLOCK(ma); } void -erts_mseg_dealloc(ErtsAlcType_t atype, void *seg, Uint size) +erts_mseg_dealloc(ErtsAlcType_t atype, void *seg, Uint size, Uint flags) { - erts_mseg_dealloc_opt(atype, seg, size, &erts_mseg_default_opt); + erts_mseg_dealloc_opt(atype, seg, size, flags, &erts_mseg_default_opt); } void * @@ -1733,7 +1752,7 @@ erts_mseg_test(unsigned long op, case 0x401: return (unsigned long) erts_mseg_alloc(ERTS_ALC_A_INVALID, (Uint *) a1, (Uint) 0); case 0x402: - erts_mseg_dealloc(ERTS_ALC_A_INVALID, (void *) a1, (Uint) a2); + erts_mseg_dealloc(ERTS_ALC_A_INVALID, (void *) a1, (Uint) a2, (Uint) 0); return (unsigned long) 0; case 0x403: return (unsigned long) erts_mseg_realloc(ERTS_ALC_A_INVALID, diff --git a/erts/emulator/sys/common/erl_mseg.h b/erts/emulator/sys/common/erl_mseg.h index 3d0b0f0355..64b68fb2e6 100644 --- a/erts/emulator/sys/common/erl_mseg.h +++ b/erts/emulator/sys/common/erl_mseg.h @@ -93,11 +93,10 @@ extern const ErtsMsegOpt_t erts_mseg_default_opt; void *erts_mseg_alloc(ErtsAlcType_t, Uint *, Uint); void *erts_mseg_alloc_opt(ErtsAlcType_t, Uint *, Uint, const ErtsMsegOpt_t *); -void erts_mseg_dealloc(ErtsAlcType_t, void *, Uint); -void erts_mseg_dealloc_opt(ErtsAlcType_t, void *, Uint, const ErtsMsegOpt_t *); +void erts_mseg_dealloc(ErtsAlcType_t, void *, Uint, Uint); +void erts_mseg_dealloc_opt(ErtsAlcType_t, void *, Uint, Uint, const ErtsMsegOpt_t *); void *erts_mseg_realloc(ErtsAlcType_t, void *, Uint, Uint *, Uint); -void *erts_mseg_realloc_opt(ErtsAlcType_t, void *, Uint, Uint *, - Uint, const ErtsMsegOpt_t *); +void *erts_mseg_realloc_opt(ErtsAlcType_t, void *, Uint, Uint *, Uint, const ErtsMsegOpt_t *); void erts_mseg_clear_cache(void); void erts_mseg_cache_check(void); Uint erts_mseg_no( const ErtsMsegOpt_t *); -- cgit v1.2.3 From 468710f6de0fd48224b6e688b075c619106d1131 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn-Egil=20Dahlberg?= Date: Fri, 8 Feb 2013 15:32:56 +0100 Subject: erts: Increase default #cached segments to 10 Previous default was 5. --- erts/doc/src/erts_alloc.xml | 2 +- erts/emulator/sys/common/erl_mseg.h | 2 +- 2 files changed, 2 insertions(+), 2 deletions(-) diff --git a/erts/doc/src/erts_alloc.xml b/erts/doc/src/erts_alloc.xml index f0bde600ad..c73cdfd290 100644 --- a/erts/doc/src/erts_alloc.xml +++ b/erts/doc/src/erts_alloc.xml @@ -276,7 +276,7 @@ Max cached segments. The maximum number of memory segments stored in the memory segment cache. Valid range is - 0-30. Default value is 5. + 0-30. Default value is 10.

The following flags are available for configuration of sys_alloc:

diff --git a/erts/emulator/sys/common/erl_mseg.h b/erts/emulator/sys/common/erl_mseg.h index 64b68fb2e6..3cab9e18da 100644 --- a/erts/emulator/sys/common/erl_mseg.h +++ b/erts/emulator/sys/common/erl_mseg.h @@ -74,7 +74,7 @@ typedef struct { { \ 4*1024*1024, /* amcbf: Absolute max cache bad fit */ \ 20, /* rmcbf: Relative max cache bad fit */ \ - 5, /* mcs: Max cache size */ \ + 10, /* mcs: Max cache size */ \ 1000 /* cci: Cache check interval */ \ } -- cgit v1.2.3 From c795f9824926f38240fb3472d97e9ccf51e8dc70 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn-Egil=20Dahlberg?= Date: Mon, 11 Feb 2013 14:24:40 +0100 Subject: erts: Segment allocator CircleQ API --- erts/emulator/sys/common/erl_mseg.c | 120 ++++++++---------------------- erts/emulator/sys/common/erl_util_queue.h | 77 +++++++++++++++++++ 2 files changed, 109 insertions(+), 88 deletions(-) create mode 100644 erts/emulator/sys/common/erl_util_queue.h diff --git a/erts/emulator/sys/common/erl_mseg.c b/erts/emulator/sys/common/erl_mseg.c index 077f705122..2f237153ef 100644 --- a/erts/emulator/sys/common/erl_mseg.c +++ b/erts/emulator/sys/common/erl_mseg.c @@ -39,6 +39,7 @@ #include "erl_alloc.h" #include "big.h" #include "erl_thr_progress.h" +#include "erl_util_queue.h" #if HAVE_ERTS_MSEG @@ -527,64 +528,6 @@ static ERTS_INLINE void mseg_cache_clear_node(cache_t *c) { c->prev = c; } -static ERTS_INLINE void mseg_cache_unlink_node(cache_t *c) { - c->next->prev = c->prev; - c->prev->next = c->next; - - c->next = c; - c->prev = c; -} - -static ERTS_INLINE void mseg_cache_push_node_front(cache_t *head, cache_t *c) { - c->next = head->next; - c->prev = head; - - head->next->prev = c; - head->next = c; - - ASSERT(c->next != c); - ASSERT(c->prev != c); -} - -/* not needed: mseg_cache_push_node_back */ - -static ERTS_INLINE cache_t *mseg_cache_pop_node_front(cache_t *head) { - cache_t *c; - - ASSERT(head->next != head && head->prev != head); - - c = head->next; - - mseg_cache_unlink_node(c); - - return c; -} - -static ERTS_INLINE cache_t *mseg_cache_pop_node_back(cache_t *head) { - cache_t *c; - - ASSERT(head->next != head && head->prev != head); - - c = head->prev; - - mseg_cache_unlink_node(c); - - return c; -} - -static ERTS_INLINE int mseg_cache_is_empty(cache_t *head) { - - if (head->next == head) { - ASSERT(head->prev == head); - return 1; - } - - ASSERT(head->next != head && head->prev != head); - - return 0; -} - - static ERTS_INLINE int cache_bless_segment(MemKind *mk, void *seg, Uint size, Uint flags) { cache_t *c; @@ -592,8 +535,9 @@ static ERTS_INLINE int cache_bless_segment(MemKind *mk, void *seg, Uint size, Ui ASSERT(!MSEG_FLG_IS_2POW(flags) || (MSEG_FLG_IS_2POW(flags) && MAP_IS_ALIGNED(seg) && IS_2POW(size))); - if (!mseg_cache_is_empty(&(mk->cache_free))) { - c = mseg_cache_pop_node_front(&(mk->cache_free)); + if (!erts_circleq_is_empty(&(mk->cache_free))) { + c = erts_circleq_head(&(mk->cache_free)); + erts_circleq_remove(c); c->seg = seg; c->size = size; @@ -604,22 +548,23 @@ static ERTS_INLINE int cache_bless_segment(MemKind *mk, void *seg, Uint size, Ui ASSERT(ix < CACHE_AREAS); ASSERT((1 << (ix + MSEG_ALIGN_BITS)) == size); - mseg_cache_push_node_front(&(mk->cache_powered_node[ix]), c); + erts_circleq_push_head(&(mk->cache_powered_node[ix]), c); } else { - mseg_cache_push_node_front(&(mk->cache_unpowered_node), c); + erts_circleq_push_head(&(mk->cache_unpowered_node), c); } mk->cache_size++; ASSERT(mk->cache_size <= mk->ma->max_cache_size); return 1; - } else if (!MSEG_FLG_IS_2POW(flags) && !mseg_cache_is_empty(&(mk->cache_unpowered_node))) { + } else if (!MSEG_FLG_IS_2POW(flags) && !erts_circleq_is_empty(&(mk->cache_unpowered_node))) { /* Evict oldest slot from cache so we can store an unpowered (sbc) segment */ - c = mseg_cache_pop_node_back(&(mk->cache_unpowered_node)); + c = erts_circleq_tail(&(mk->cache_unpowered_node)); + erts_circleq_remove(c); mseg_destroy(mk->ma, mk, c->seg, c->size); mseg_cache_clear_node(c); @@ -627,7 +572,7 @@ static ERTS_INLINE int cache_bless_segment(MemKind *mk, void *seg, Uint size, Ui c->seg = seg; c->size = size; - mseg_cache_push_node_front(&(mk->cache_unpowered_node), c); + erts_circleq_push_head(&(mk->cache_unpowered_node), c); return 1; } @@ -652,10 +597,11 @@ static ERTS_INLINE void *cache_get_segment(MemKind *mk, Uint *size_p, Uint flags for( i = ix; i < CACHE_AREAS; i++) { - if (mseg_cache_is_empty(&(mk->cache_powered_node[i]))) + if (erts_circleq_is_empty(&(mk->cache_powered_node[i]))) continue; - c = mseg_cache_pop_node_front(&(mk->cache_powered_node[i])); + c = erts_circleq_head(&(mk->cache_powered_node[i])); + erts_circleq_remove(c); ASSERT(IS_2POW(c->size)); ASSERT(MAP_IS_ALIGNED(c->seg)); @@ -668,7 +614,7 @@ static ERTS_INLINE void *cache_get_segment(MemKind *mk, Uint *size_p, Uint flags /* link to free cache list */ mseg_cache_clear_node(c); - mseg_cache_push_node_front(&(mk->cache_free), c); + erts_circleq_push_head(&(mk->cache_free), c); ASSERT(!(mk->cache_size < 0)); @@ -679,16 +625,14 @@ static ERTS_INLINE void *cache_get_segment(MemKind *mk, Uint *size_p, Uint flags return seg; } } - else if (!mseg_cache_is_empty(&(mk->cache_unpowered_node))) { + else if (!erts_circleq_is_empty(&(mk->cache_unpowered_node))) { void *seg; cache_t *c; Uint csize; Uint bad_max_abs = mk->ma->abs_max_cache_bad_fit; Uint bad_max_rel = mk->ma->rel_max_cache_bad_fit; - c = mk->cache_unpowered_node.next; - - while (c != &(mk->cache_unpowered_node)) { + erts_circleq_foreach(c, &(mk->cache_unpowered_node)) { csize = c->size; if (csize >= size && ((csize - size)*100 < bad_max_rel*size) && @@ -696,20 +640,18 @@ static ERTS_INLINE void *cache_get_segment(MemKind *mk, Uint *size_p, Uint flags seg = c->seg; - mseg_cache_unlink_node(c); + erts_circleq_remove(c); mk->cache_size--; mk->cache_hits++; - /* link to free cache list */ mseg_cache_clear_node(c); - mseg_cache_push_node_front(&(mk->cache_free), c); + erts_circleq_push_head(&(mk->cache_free), c); *size_p = csize; return seg; } - c = c->next; } } return NULL; @@ -723,14 +665,15 @@ static ERTS_INLINE void *cache_get_segment(MemKind *mk, Uint *size_p, Uint flags static ERTS_INLINE Uint mseg_drop_one_memkind_cache_size(MemKind *mk, cache_t *head) { cache_t *c = NULL; - c = mseg_cache_pop_node_back(head); + c = erts_circleq_tail(head); + erts_circleq_remove(c); if (erts_mtrace_enabled) erts_mtrace_crr_free(SEGTYPE, SEGTYPE, c->seg); mseg_destroy(mk->ma, mk, c->seg, c->size); mseg_cache_clear_node(c); - mseg_cache_push_node_front(&(mk->cache_free), c); + erts_circleq_push_head(&(mk->cache_free), c); mk->segments.current.watermark--; mk->cache_size--; @@ -743,9 +686,10 @@ static ERTS_INLINE Uint mseg_drop_one_memkind_cache_size(MemKind *mk, cache_t *h static ERTS_INLINE Uint mseg_drop_memkind_cache_size(MemKind *mk, cache_t *head) { cache_t *c = NULL; - while (!mseg_cache_is_empty(head)) { + while (!erts_circleq_is_empty(head)) { - c = mseg_cache_pop_node_back(head); + c = erts_circleq_tail(head); + erts_circleq_remove(c); if (erts_mtrace_enabled) erts_mtrace_crr_free(SEGTYPE, SEGTYPE, c->seg); @@ -753,7 +697,7 @@ static ERTS_INLINE Uint mseg_drop_memkind_cache_size(MemKind *mk, cache_t *head) mseg_destroy(mk->ma, mk, c->seg, c->size); mseg_cache_clear_node(c); - mseg_cache_push_node_front(&(mk->cache_free), c); + erts_circleq_push_head(&(mk->cache_free), c); mk->segments.current.watermark--; mk->cache_size--; @@ -777,11 +721,11 @@ static Uint mseg_check_memkind_cache(MemKind *mk) { ERTS_DBG_MK_CHK_THR_ACCESS(mk); for (i = 0; i < CACHE_AREAS; i++) { - if (!mseg_cache_is_empty(&(mk->cache_powered_node[i]))) + if (!erts_circleq_is_empty(&(mk->cache_powered_node[i]))) return mseg_drop_one_memkind_cache_size(mk, &(mk->cache_powered_node[i])); } - if (!mseg_cache_is_empty(&(mk->cache_unpowered_node))) + if (!erts_circleq_is_empty(&(mk->cache_unpowered_node))) return mseg_drop_one_memkind_cache_size(mk, &(mk->cache_unpowered_node)); return 0; @@ -838,17 +782,17 @@ static void mseg_clear_memkind_cache(MemKind *mk) { /* drop pow2 caches */ for (i = 0; i < CACHE_AREAS; i++) { - if (mseg_cache_is_empty(&(mk->cache_powered_node[i]))) + if (erts_circleq_is_empty(&(mk->cache_powered_node[i]))) continue; mseg_drop_memkind_cache_size(mk, &(mk->cache_powered_node[i])); - ASSERT(mseg_cache_is_empty(&(mk->cache_powered_node[i])) == 1); + ASSERT(erts_circleq_is_empty(&(mk->cache_powered_node[i]))); } /* drop varied caches */ - if (!mseg_cache_is_empty(&(mk->cache_unpowered_node))) + if (!erts_circleq_is_empty(&(mk->cache_unpowered_node))) mseg_drop_memkind_cache_size(mk, &(mk->cache_unpowered_node)); - ASSERT(mseg_cache_is_empty(&(mk->cache_unpowered_node)) == 1); + ASSERT(erts_circleq_is_empty(&(mk->cache_unpowered_node))); ASSERT(mk->cache_size == 0); } @@ -1608,7 +1552,7 @@ static void mem_kind_init(ErtsMsegAllctr_t *ma, MemKind* mk, const char* name) for (i = 0; i < ma->max_cache_size; i++) { mseg_cache_clear_node(&(mk->cache[i])); - mseg_cache_push_node_front(&(mk->cache_free), &(mk->cache[i])); + erts_circleq_push_head(&(mk->cache_free), &(mk->cache[i])); } mk->cache_size = 0; diff --git a/erts/emulator/sys/common/erl_util_queue.h b/erts/emulator/sys/common/erl_util_queue.h new file mode 100644 index 0000000000..47925e2264 --- /dev/null +++ b/erts/emulator/sys/common/erl_util_queue.h @@ -0,0 +1,77 @@ +/* + * %CopyrightBegin% + * + * Copyright Ericsson AB 2013. 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% + */ + +#ifndef ERL_UTIL_QUEUE_H_ +#define ERL_UTIL_QUEUE_H_ + +#define erts_circleq_head(Q) ((Q)->next) +#define erts_circleq_tail(Q) ((Q)->prev) +#define erts_circleq_next(Q) ((Q)->next) +#define erts_circleq_prev(Q) ((Q)->prev) +#define erts_circleq_is_empty(Q) ((Q)->next == (void *)(Q)) + +#define erts_circleq_remove(N) \ + do { \ + (N)->next->prev = (N)->prev; \ + (N)->prev->next = (N)->next; \ + (N)->next = (N); \ + (N)->prev = (N); \ + } while(0) + +#define erts_circleq_pop_head(Q, N) \ + do { \ + (N) = (Q)->next; \ + (N)->next->prev = (N)->prev; \ + (N)->prev->next = (N)->next; \ + (N)->next = (N); \ + (N)->prev = (N); \ + } while(0) + +#define erts_circleq_pop_tail(Q, N) \ + do { \ + (N) = (Q)->prev; \ + (N)->next->prev = (N)->prev; \ + (N)->prev->next = (N)->next; \ + (N)->next = (N); \ + (N)->prev = (N); \ + } while(0) + +#define erts_circleq_push_head(Q, N) \ + do { \ + (N)->next = (Q)->next; \ + (N)->prev = (void *)(Q); \ + (Q)->next->prev = (N); \ + (Q)->next = (N); \ + } while(0) + +#define erts_circleq_push_tail(Q, N) \ + do { \ + (N)->prev = (Q)->prev; \ + (N)->next = (void *)(Q); \ + (Q)->prev->next = (N); \ + (Q)->prev = (N); \ + } while(0) + +#define erts_circleq_foreach(V, Q) \ + for ((V) = (Q)->next; (V) != (const void *)(Q); (V) = (V)->next) + +#define erts_circleq_foreach_reverse(V, Q) \ + for ((V) = (Q)->prev; (V) != (const void *)(Q); (V) = (V)->prev) + +#endif -- cgit v1.2.3 From f09d1b2895966f4262a5afdab764fe790b0f9ae1 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn-Egil=20Dahlberg?= Date: Tue, 12 Feb 2013 15:36:46 +0100 Subject: erts: Prefer sbc segment caching over mbc segments --- erts/emulator/sys/common/erl_mseg.c | 39 +++++++++++++++++++++++++++++++++---- 1 file changed, 35 insertions(+), 4 deletions(-) diff --git a/erts/emulator/sys/common/erl_mseg.c b/erts/emulator/sys/common/erl_mseg.c index 2f237153ef..32d753a67b 100644 --- a/erts/emulator/sys/common/erl_mseg.c +++ b/erts/emulator/sys/common/erl_mseg.c @@ -535,7 +535,15 @@ static ERTS_INLINE int cache_bless_segment(MemKind *mk, void *seg, Uint size, Ui ASSERT(!MSEG_FLG_IS_2POW(flags) || (MSEG_FLG_IS_2POW(flags) && MAP_IS_ALIGNED(seg) && IS_2POW(size))); + /* The idea is that sbc caching is prefered over mbc caching. + * Blocks are normally allocated in mb carriers and thus cached there. + * Large blocks has no such cache and it is up to mseg to cache them to speed things up. + */ + if (!erts_circleq_is_empty(&(mk->cache_free))) { + + /* We have free slots, use one to cache the segment */ + c = erts_circleq_head(&(mk->cache_free)); erts_circleq_remove(c); @@ -550,10 +558,8 @@ static ERTS_INLINE int cache_bless_segment(MemKind *mk, void *seg, Uint size, Ui erts_circleq_push_head(&(mk->cache_powered_node[ix]), c); - } else { - + } else erts_circleq_push_head(&(mk->cache_unpowered_node), c); - } mk->cache_size++; ASSERT(mk->cache_size <= mk->ma->max_cache_size); @@ -561,7 +567,8 @@ static ERTS_INLINE int cache_bless_segment(MemKind *mk, void *seg, Uint size, Ui return 1; } else if (!MSEG_FLG_IS_2POW(flags) && !erts_circleq_is_empty(&(mk->cache_unpowered_node))) { - /* Evict oldest slot from cache so we can store an unpowered (sbc) segment */ + /* No free slots. + * Evict oldest slot from unpowered cache so we can cache an unpowered (sbc) segment */ c = erts_circleq_tail(&(mk->cache_unpowered_node)); erts_circleq_remove(c); @@ -575,6 +582,30 @@ static ERTS_INLINE int cache_bless_segment(MemKind *mk, void *seg, Uint size, Ui erts_circleq_push_head(&(mk->cache_unpowered_node), c); return 1; + } else if (!MSEG_FLG_IS_2POW(flags)) { + + /* No free slots and no unpowered (sbc) slots. + * Evict smallest slot from powered cache so we can cache an unpowered (sbc) segment */ + + int i; + + for( i = 0; i < CACHE_AREAS; i++) { + if (erts_circleq_is_empty(&(mk->cache_powered_node[i]))) + continue; + + c = erts_circleq_tail(&(mk->cache_powered_node[i])); + erts_circleq_remove(c); + + mseg_destroy(mk->ma, mk, c->seg, c->size); + mseg_cache_clear_node(c); + + c->seg = seg; + c->size = size; + + erts_circleq_push_head(&(mk->cache_unpowered_node), c); + + return 1; + } } return 0; -- cgit v1.2.3 From def1a47fc6674fc87b74ba727054c5104694b00c Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn-Egil=20Dahlberg?= Date: Tue, 12 Feb 2013 20:02:26 +0100 Subject: erts: Utilize even more cached sbc segments --- erts/emulator/sys/common/erl_mseg.c | 59 +++++++++++++++++++++++++++++-------- 1 file changed, 47 insertions(+), 12 deletions(-) diff --git a/erts/emulator/sys/common/erl_mseg.c b/erts/emulator/sys/common/erl_mseg.c index 32d753a67b..bd8ba82a5f 100644 --- a/erts/emulator/sys/common/erl_mseg.c +++ b/erts/emulator/sys/common/erl_mseg.c @@ -585,7 +585,10 @@ static ERTS_INLINE int cache_bless_segment(MemKind *mk, void *seg, Uint size, Ui } else if (!MSEG_FLG_IS_2POW(flags)) { /* No free slots and no unpowered (sbc) slots. - * Evict smallest slot from powered cache so we can cache an unpowered (sbc) segment */ + * Evict smallest slot from powered cache so we can cache an unpowered (sbc) segment. + * Note: Though this is the wanted policy I don't think it is used significantly. + * This branch could probably be removed without serious impact. + */ int i; @@ -659,31 +662,63 @@ static ERTS_INLINE void *cache_get_segment(MemKind *mk, Uint *size_p, Uint flags else if (!erts_circleq_is_empty(&(mk->cache_unpowered_node))) { void *seg; cache_t *c; + cache_t *best = NULL; + Uint bdiff = 0; Uint csize; Uint bad_max_abs = mk->ma->abs_max_cache_bad_fit; Uint bad_max_rel = mk->ma->rel_max_cache_bad_fit; erts_circleq_foreach(c, &(mk->cache_unpowered_node)) { csize = c->size; - if (csize >= size && - ((csize - size)*100 < bad_max_rel*size) && - (csize - size) < bad_max_abs ) { + if (csize >= size) { + if (((csize - size)*100 < bad_max_rel*size) && (csize - size) < bad_max_abs ) { - seg = c->seg; + seg = c->seg; - erts_circleq_remove(c); + erts_circleq_remove(c); - mk->cache_size--; - mk->cache_hits++; + mk->cache_size--; + mk->cache_hits++; - mseg_cache_clear_node(c); - erts_circleq_push_head(&(mk->cache_free), c); + mseg_cache_clear_node(c); + erts_circleq_push_head(&(mk->cache_free), c); - *size_p = csize; + *size_p = csize; - return seg; + return seg; + + } else if (!best || (csize - size) < bdiff) { + best = c; + bdiff = csize - size; + } } } + + /* No cached segment met our criteria, use the best one found and trim it */ + + if (best) { + + seg = best->seg; + csize = best->size; + + ASSERT(best->seg); + ASSERT(best->size > 0); + + mk->cache_hits++; + + /* Use current cache placement for remaining segment space */ + + best->seg = seg + size; + best->size = csize - size; + + ASSERT((size % GET_PAGE_SIZE) == 0); + ASSERT((best->size % GET_PAGE_SIZE) == 0); + + *size_p = size; + + return seg; + + } } return NULL; } -- cgit v1.2.3