From e201e24904d53897409b1dda451d40c5d2e0dc29 Mon Sep 17 00:00:00 2001
From: Jason Evans <jasone@canonware.com>
Date: Thu, 2 Mar 2017 18:04:35 -0800
Subject: Perform delayed coalescing prior to purging.
Rather than purging uncoalesced extents, perform just enough incremental
coalescing to purge only fully coalesced extents. In the absence of
cached extent reuse, the immediate versus delayed incremental purging
algorithms result in the same purge order.
This resolves #655.
---
include/jemalloc/internal/extent_externs.h | 5 +-
include/jemalloc/internal/extent_inlines.h | 9 ++
include/jemalloc/internal/extent_structs.h | 7 +-
include/jemalloc/internal/private_symbols.txt | 2 +
src/arena.c | 28 +++--
src/extent.c | 151 +++++++++++++++++++-------
6 files changed, 152 insertions(+), 50 deletions(-)
diff --git a/include/jemalloc/internal/extent_externs.h b/include/jemalloc/internal/extent_externs.h
index f5efed0..ef2467e 100644
--- a/include/jemalloc/internal/extent_externs.h
+++ b/include/jemalloc/internal/extent_externs.h
@@ -18,10 +18,11 @@ size_t extent_size_quantize_ceil(size_t size);
ph_proto(, extent_heap_, extent_heap_t, extent_t)
bool extents_init(tsdn_t *tsdn, extents_t *extents, extent_state_t state,
- bool try_coalesce);
+ bool delay_coalesce);
extent_state_t extents_state_get(const extents_t *extents);
size_t extents_npages_get(extents_t *extents);
-extent_t *extents_evict(tsdn_t *tsdn, extents_t *extents, size_t npages_min);
+extent_t *extents_evict(tsdn_t *tsdn, arena_t *arena,
+ extent_hooks_t **r_extent_hooks, extents_t *extents, size_t npages_min);
void extents_prefork(tsdn_t *tsdn, extents_t *extents);
void extents_postfork_parent(tsdn_t *tsdn, extents_t *extents);
void extents_postfork_child(tsdn_t *tsdn, extents_t *extents);
diff --git a/include/jemalloc/internal/extent_inlines.h b/include/jemalloc/internal/extent_inlines.h
index 473aad7..989c0d1 100644
--- a/include/jemalloc/internal/extent_inlines.h
+++ b/include/jemalloc/internal/extent_inlines.h
@@ -37,6 +37,8 @@ void extent_list_init(extent_list_t *list);
extent_t *extent_list_first(const extent_list_t *list);
extent_t *extent_list_last(const extent_list_t *list);
void extent_list_append(extent_list_t *list, extent_t *extent);
+void extent_list_replace(extent_list_t *list, extent_t *to_remove,
+ extent_t *to_insert);
void extent_list_remove(extent_list_t *list, extent_t *extent);
int extent_sn_comp(const extent_t *a, const extent_t *b);
int extent_ad_comp(const extent_t *a, const extent_t *b);
@@ -254,6 +256,13 @@ extent_list_append(extent_list_t *list, extent_t *extent) {
}
JEMALLOC_INLINE void
+extent_list_replace(extent_list_t *list, extent_t *to_remove,
+ extent_t *to_insert) {
+ ql_after_insert(to_remove, to_insert, ql_link);
+ ql_remove(list, to_remove, ql_link);
+}
+
+JEMALLOC_INLINE void
extent_list_remove(extent_list_t *list, extent_t *extent) {
ql_remove(list, extent, ql_link);
}
diff --git a/include/jemalloc/internal/extent_structs.h b/include/jemalloc/internal/extent_structs.h
index 008b635..9ea6972 100644
--- a/include/jemalloc/internal/extent_structs.h
+++ b/include/jemalloc/internal/extent_structs.h
@@ -116,8 +116,11 @@ struct extents_s {
/* All stored extents must be in the same state. */
extent_state_t state;
- /* If true, try to coalesce during extent deallocation. */
- bool try_coalesce;
+ /*
+ * If true, delay coalescing until eviction; otherwise coalesce during
+ * deallocation.
+ */
+ bool delay_coalesce;
};
#endif /* JEMALLOC_INTERNAL_EXTENT_STRUCTS_H */
diff --git a/include/jemalloc/internal/private_symbols.txt b/include/jemalloc/internal/private_symbols.txt
index b122dae..30cd395 100644
--- a/include/jemalloc/internal/private_symbols.txt
+++ b/include/jemalloc/internal/private_symbols.txt
@@ -159,8 +159,10 @@ extent_init
extent_last_get
extent_list_append
extent_list_first
+extent_list_init
extent_list_last
extent_list_remove
+extent_list_replace
extent_lookup
extent_merge_wrapper
extent_past_get
diff --git a/src/arena.c b/src/arena.c
index 56ab362..cef61cc 100644
--- a/src/arena.c
+++ b/src/arena.c
@@ -715,9 +715,9 @@ arena_stash_dirty(tsdn_t *tsdn, arena_t *arena, extent_hooks_t **r_extent_hooks,
/* Stash extents according to ndirty_limit. */
size_t nstashed = 0;
- for (extent_t *extent = extents_evict(tsdn, &arena->extents_cached,
- ndirty_limit); extent != NULL; extent = extents_evict(tsdn,
- &arena->extents_cached, ndirty_limit)) {
+ extent_t *extent;
+ while ((extent = extents_evict(tsdn, arena, r_extent_hooks,
+ &arena->extents_cached, ndirty_limit)) != NULL) {
extent_list_append(purge_extents, extent);
nstashed += extent_size_get(extent) >> LG_PAGE;
}
@@ -943,9 +943,9 @@ arena_destroy_retained(tsdn_t *tsdn, arena_t *arena) {
* either unmap retained extents or track them for later use.
*/
extent_hooks_t *extent_hooks = extent_hooks_get(arena);
- for (extent_t *extent = extents_evict(tsdn, &arena->extents_retained,
- 0); extent != NULL; extent = extents_evict(tsdn,
- &arena->extents_retained, 0)) {
+ extent_t *extent;
+ while ((extent = extents_evict(tsdn, arena, &extent_hooks,
+ &arena->extents_retained, 0)) != NULL) {
extent_dalloc_wrapper_try(tsdn, arena, &extent_hooks, extent);
}
}
@@ -1679,12 +1679,24 @@ arena_new(tsdn_t *tsdn, unsigned ind, extent_hooks_t *extent_hooks) {
goto label_error;
}
+ /*
+ * Delay coalescing for cached extents despite the disruptive effect on
+ * memory layout for best-fit extent allocation, since cached extents
+ * are likely to be reused soon after deallocation, and the cost of
+ * merging/splitting extents is non-trivial.
+ */
if (extents_init(tsdn, &arena->extents_cached, extent_state_dirty,
- false)) {
+ true)) {
goto label_error;
}
+ /*
+ * Coalesce retained extents immediately, in part because they will
+ * never be evicted (and therefore there's no opportunity for delayed
+ * coalescing), but also because operations on retained extents are not
+ * in the critical path.
+ */
if (extents_init(tsdn, &arena->extents_retained,
- extent_state_retained, true)) {
+ extent_state_retained, false)) {
goto label_error;
}
diff --git a/src/extent.c b/src/extent.c
index 09990aa..368c974 100644
--- a/src/extent.c
+++ b/src/extent.c
@@ -69,6 +69,9 @@ static size_t highpages;
*/
static void extent_deregister(tsdn_t *tsdn, extent_t *extent);
+static extent_t *extent_try_coalesce(tsdn_t *tsdn, arena_t *arena,
+ extent_hooks_t **r_extent_hooks, rtree_ctx_t *rtree_ctx, extents_t *extents,
+ extent_t *extent, bool *coalesced);
static void extent_record(tsdn_t *tsdn, arena_t *arena,
extent_hooks_t **r_extent_hooks, extents_t *extents, extent_t *extent);
@@ -175,7 +178,7 @@ ph_gen(, extent_heap_, extent_heap_t, extent_t, ph_link, extent_snad_comp)
bool
extents_init(tsdn_t *tsdn, extents_t *extents, extent_state_t state,
- bool try_coalesce) {
+ bool delay_coalesce) {
if (malloc_mutex_init(&extents->mtx, "extents", WITNESS_RANK_EXTENTS)) {
return true;
}
@@ -185,7 +188,7 @@ extents_init(tsdn_t *tsdn, extents_t *extents, extent_state_t state,
extent_list_init(&extents->lru);
extents->npages = 0;
extents->state = state;
- extents->try_coalesce = try_coalesce;
+ extents->delay_coalesce = delay_coalesce;
return false;
}
@@ -200,7 +203,8 @@ extents_npages_get(extents_t *extents) {
}
static void
-extents_insert_locked(tsdn_t *tsdn, extents_t *extents, extent_t *extent) {
+extents_insert_locked(tsdn_t *tsdn, extents_t *extents, extent_t *extent,
+ bool preserve_lru) {
malloc_mutex_assert_owner(tsdn, &extents->mtx);
assert(extent_state_get(extent) == extents->state);
@@ -208,13 +212,16 @@ extents_insert_locked(tsdn_t *tsdn, extents_t *extents, extent_t *extent) {
size_t psz = extent_size_quantize_floor(size);
pszind_t pind = psz2ind(psz);
extent_heap_insert(&extents->heaps[pind], extent);
- extent_list_append(&extents->lru, extent);
+ if (!preserve_lru) {
+ extent_list_append(&extents->lru, extent);
+ }
size_t npages = size >> LG_PAGE;
atomic_add_zu(&extents->npages, npages);
}
static void
-extents_remove_locked(tsdn_t *tsdn, extents_t *extents, extent_t *extent) {
+extents_remove_locked(tsdn_t *tsdn, extents_t *extents, extent_t *extent,
+ bool preserve_lru) {
malloc_mutex_assert_owner(tsdn, &extents->mtx);
assert(extent_state_get(extent) == extents->state);
@@ -222,7 +229,9 @@ extents_remove_locked(tsdn_t *tsdn, extents_t *extents, extent_t *extent) {
size_t psz = extent_size_quantize_floor(size);
pszind_t pind = psz2ind(psz);
extent_heap_remove(&extents->heaps[pind], extent);
- extent_list_remove(&extents->lru, extent);
+ if (!preserve_lru) {
+ extent_list_remove(&extents->lru, extent);
+ }
size_t npages = size >> LG_PAGE;
assert(atomic_read_zu(&extents->npages) >= npages);
atomic_sub_zu(&extents->npages, size >> LG_PAGE);
@@ -249,22 +258,62 @@ extents_first_best_fit_locked(tsdn_t *tsdn, arena_t *arena, extents_t *extents,
return NULL;
}
+static bool
+extent_try_delayed_coalesce(tsdn_t *tsdn, arena_t *arena,
+ extent_hooks_t **r_extent_hooks, rtree_ctx_t *rtree_ctx, extents_t *extents,
+ extent_t *extent) {
+ extent_state_set(extent, extent_state_active);
+ bool coalesced;
+ extent = extent_try_coalesce(tsdn, arena, r_extent_hooks, rtree_ctx,
+ extents, extent, &coalesced);
+ extent_state_set(extent, extents_state_get(extents));
+
+ if (!coalesced) {
+ return true;
+ }
+ extents_insert_locked(tsdn, extents, extent, true);
+ return false;
+}
+
extent_t *
-extents_evict(tsdn_t *tsdn, extents_t *extents, size_t npages_min) {
+extents_evict(tsdn_t *tsdn, arena_t *arena, extent_hooks_t **r_extent_hooks,
+ extents_t *extents, size_t npages_min) {
+ rtree_ctx_t rtree_ctx_fallback;
+ rtree_ctx_t *rtree_ctx = tsdn_rtree_ctx(tsdn, &rtree_ctx_fallback);
+
malloc_mutex_lock(tsdn, &extents->mtx);
- /* Get the LRU extent, if any. */
- extent_t *extent = extent_list_first(&extents->lru);
- if (extent == NULL) {
- goto label_return;
- }
- /* Check the eviction limit. */
- size_t npages = extent_size_get(extent) >> LG_PAGE;
- if (atomic_read_zu(&extents->npages) - npages < npages_min) {
- extent = NULL;
- goto label_return;
+ /*
+ * Get the LRU coalesced extent, if any. If coalescing was delayed,
+ * the loop will iterate until the LRU extent is fully coalesced.
+ */
+ extent_t *extent;
+ while (true) {
+ /* Get the LRU extent, if any. */
+ extent = extent_list_first(&extents->lru);
+ if (extent == NULL) {
+ goto label_return;
+ }
+ /* Check the eviction limit. */
+ size_t npages = extent_size_get(extent) >> LG_PAGE;
+ if (atomic_read_zu(&extents->npages) - npages < npages_min) {
+ extent = NULL;
+ goto label_return;
+ }
+ extents_remove_locked(tsdn, extents, extent, false);
+ if (!extents->delay_coalesce) {
+ break;
+ }
+ /* Try to coalesce. */
+ if (extent_try_delayed_coalesce(tsdn, arena, r_extent_hooks,
+ rtree_ctx, extents, extent)) {
+ break;
+ }
+ /*
+ * The LRU extent was just coalesced and the result placed in
+ * the LRU at its neighbor's position. Start over.
+ */
}
- extents_remove_locked(tsdn, extents, extent);
/*
* Either mark the extent active or deregister it to protect against
@@ -320,29 +369,29 @@ extents_postfork_child(tsdn_t *tsdn, extents_t *extents) {
static void
extent_deactivate_locked(tsdn_t *tsdn, arena_t *arena, extents_t *extents,
- extent_t *extent) {
+ extent_t *extent, bool preserve_lru) {
assert(extent_arena_get(extent) == arena);
assert(extent_state_get(extent) == extent_state_active);
extent_state_set(extent, extents_state_get(extents));
- extents_insert_locked(tsdn, extents, extent);
+ extents_insert_locked(tsdn, extents, extent, preserve_lru);
}
static void
extent_deactivate(tsdn_t *tsdn, arena_t *arena, extents_t *extents,
- extent_t *extent) {
+ extent_t *extent, bool preserve_lru) {
malloc_mutex_lock(tsdn, &extents->mtx);
- extent_deactivate_locked(tsdn, arena, extents, extent);
+ extent_deactivate_locked(tsdn, arena, extents, extent, preserve_lru);
malloc_mutex_unlock(tsdn, &extents->mtx);
}
static void
extent_activate_locked(tsdn_t *tsdn, arena_t *arena, extents_t *extents,
- extent_t *extent) {
+ extent_t *extent, bool preserve_lru) {
assert(extent_arena_get(extent) == arena);
assert(extent_state_get(extent) == extents_state_get(extents));
- extents_remove_locked(tsdn, extents, extent);
+ extents_remove_locked(tsdn, extents, extent, preserve_lru);
extent_state_set(extent, extent_state_active);
}
@@ -581,7 +630,7 @@ extent_recycle_extract(tsdn_t *tsdn, arena_t *arena,
return NULL;
}
- extent_activate_locked(tsdn, arena, extents, extent);
+ extent_activate_locked(tsdn, arena, extents, extent, false);
if (!locked) {
malloc_mutex_unlock(tsdn, &extents->mtx);
}
@@ -620,7 +669,7 @@ extent_recycle_split(tsdn_t *tsdn, arena_t *arena,
lead);
return NULL;
}
- extent_deactivate(tsdn, arena, extents, lead);
+ extent_deactivate(tsdn, arena, extents, lead, false);
}
/* Split the trail. */
@@ -633,7 +682,7 @@ extent_recycle_split(tsdn_t *tsdn, arena_t *arena,
extent);
return NULL;
}
- extent_deactivate(tsdn, arena, extents, trail);
+ extent_deactivate(tsdn, arena, extents, trail, false);
} else if (leadsize == 0) {
/*
* Splitting causes usize to be set as a side effect, but no
@@ -1030,7 +1079,16 @@ extent_coalesce(tsdn_t *tsdn, arena_t *arena, extent_hooks_t **r_extent_hooks,
extents_t *extents, extent_t *inner, extent_t *outer, bool forward) {
assert(extent_can_coalesce(arena, extents, inner, outer));
- extent_activate_locked(tsdn, arena, extents, outer);
+ if (forward && extents->delay_coalesce) {
+ /*
+ * The extent that remains after coalescing must occupy the
+ * outer extent's position in the LRU. For forward coalescing,
+ * swap the inner extent into the LRU.
+ */
+ extent_list_replace(&extents->lru, outer, inner);
+ }
+ extent_activate_locked(tsdn, arena, extents, outer,
+ extents->delay_coalesce);
malloc_mutex_unlock(tsdn, &extents->mtx);
bool err = extent_merge_wrapper(tsdn, arena, r_extent_hooks,
@@ -1038,7 +1096,11 @@ extent_coalesce(tsdn_t *tsdn, arena_t *arena, extent_hooks_t **r_extent_hooks,
malloc_mutex_lock(tsdn, &extents->mtx);
if (err) {
- extent_deactivate_locked(tsdn, arena, extents, outer);
+ if (forward && extents->delay_coalesce) {
+ extent_list_replace(&extents->lru, inner, outer);
+ }
+ extent_deactivate_locked(tsdn, arena, extents, outer,
+ extents->delay_coalesce);
}
return err;
@@ -1047,14 +1109,14 @@ extent_coalesce(tsdn_t *tsdn, arena_t *arena, extent_hooks_t **r_extent_hooks,
static extent_t *
extent_try_coalesce(tsdn_t *tsdn, arena_t *arena,
extent_hooks_t **r_extent_hooks, rtree_ctx_t *rtree_ctx, extents_t *extents,
- extent_t *extent) {
+ extent_t *extent, bool *coalesced) {
/*
* Continue attempting to coalesce until failure, to protect against
* races with other threads that are thwarted by this one.
*/
- bool coalesced;
+ bool again;
do {
- coalesced = false;
+ again = false;
/* Try to coalesce forward. */
rtree_elm_t *next_elm = rtree_elm_acquire(tsdn, &extents_rtree,
@@ -1073,7 +1135,12 @@ extent_try_coalesce(tsdn_t *tsdn, arena_t *arena,
rtree_elm_release(tsdn, &extents_rtree, next_elm);
if (can_coalesce && !extent_coalesce(tsdn, arena,
r_extent_hooks, extents, extent, next, true)) {
- coalesced = true;
+ if (extents->delay_coalesce) {
+ /* Do minimal coalescing. */
+ *coalesced = true;
+ return extent;
+ }
+ again = true;
}
}
@@ -1090,11 +1157,19 @@ extent_try_coalesce(tsdn_t *tsdn, arena_t *arena,
if (can_coalesce && !extent_coalesce(tsdn, arena,
r_extent_hooks, extents, extent, prev, false)) {
extent = prev;
- coalesced = true;
+ if (extents->delay_coalesce) {
+ /* Do minimal coalescing. */
+ *coalesced = true;
+ return extent;
+ }
+ again = true;
}
}
- } while (coalesced);
+ } while (again);
+ if (extents->delay_coalesce) {
+ *coalesced = false;
+ }
return extent;
}
@@ -1118,12 +1193,12 @@ extent_record(tsdn_t *tsdn, arena_t *arena, extent_hooks_t **r_extent_hooks,
assert(extent_lookup(tsdn, extent_base_get(extent), true) == extent);
- if (extents->try_coalesce) {
+ if (!extents->delay_coalesce) {
extent = extent_try_coalesce(tsdn, arena, r_extent_hooks,
- rtree_ctx, extents, extent);
+ rtree_ctx, extents, extent, NULL);
}
- extent_deactivate_locked(tsdn, arena, extents, extent);
+ extent_deactivate_locked(tsdn, arena, extents, extent, false);
malloc_mutex_unlock(tsdn, &extents->mtx);
}
--
cgit v0.12