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 (limited to 'erts/emulator/sys/common') 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