Implement two-phase decay-based purging.

Split decay-based purging into two phases, the first of which uses lazy
purging to convert dirty pages to "muzzy", and the second of which uses
forced purging, decommit, or unmapping to convert pages to clean or
destroy them altogether.  Not all operating systems support lazy
purging, yet the application may provide extent hooks that implement
lazy purging, so care must be taken to dynamically omit the first phase
when necessary.

The mallctl interfaces change as follows:
- opt.decay_time --> opt.{dirty,muzzy}_decay_time
- arena.<i>.decay_time --> arena.<i>.{dirty,muzzy}_decay_time
- arenas.decay_time --> arenas.{dirty,muzzy}_decay_time
- stats.arenas.<i>.pdirty --> stats.arenas.<i>.p{dirty,muzzy}
- stats.arenas.<i>.{npurge,nmadvise,purged} -->
  stats.arenas.<i>.{dirty,muzzy}_{npurge,nmadvise,purged}

This resolves #521.

10 files changed, 82 insertions, 50 deletions

diff --git a/include/jemalloc/internal/arena_externs.h b/include/jemalloc/internal/arena_externs.h
index 349bae9..9603d74 100644
--- a/include/jemalloc/internal/arena_externs.h
+++ b/include/jemalloc/internal/arena_externs.h
@@ -9,7 +9,8 @@ static const size_t	large_pad =
 #endif
     ;
 
-extern ssize_t		opt_decay_time;
+extern ssize_t		opt_dirty_decay_time;
+extern ssize_t		opt_muzzy_decay_time;
 
 extern const arena_bin_info_t	arena_bin_info[NBINS];
 
@@ -22,13 +23,13 @@ void arena_stats_large_nrequests_add(tsdn_t *tsdn, arena_stats_t *arena_stats,
 void arena_stats_mapped_add(tsdn_t *tsdn, arena_stats_t *arena_stats,
     size_t size);
 void	arena_basic_stats_merge(tsdn_t *tsdn, arena_t *arena,
-    unsigned *nthreads, const char **dss, ssize_t *decay_time, size_t *nactive,
-    size_t *ndirty);
+    unsigned *nthreads, const char **dss, ssize_t *dirty_decay_time,
+    ssize_t *muzzy_decay_time, size_t *nactive, size_t *ndirty, size_t *nmuzzy);
 void arena_stats_merge(tsdn_t *tsdn, arena_t *arena, unsigned *nthreads,
-    const char **dss, ssize_t *decay_time, size_t *nactive, size_t *ndirty,
-    arena_stats_t *astats, malloc_bin_stats_t *bstats,
-    malloc_large_stats_t *lstats);
-void	arena_extent_cache_dalloc(tsdn_t *tsdn, arena_t *arena,
+    const char **dss, ssize_t *dirty_decay_time, ssize_t *muzzy_decay_time,
+    size_t *nactive, size_t *ndirty, size_t *nmuzzy, arena_stats_t *astats,
+    malloc_bin_stats_t *bstats, malloc_large_stats_t *lstats);
+void	arena_extents_dirty_dalloc(tsdn_t *tsdn, arena_t *arena,
     extent_hooks_t **r_extent_hooks, extent_t *extent);
 #ifdef JEMALLOC_JET
 size_t	arena_slab_regind(extent_t *slab, szind_t binind, const void *ptr);
@@ -41,9 +42,13 @@ void	arena_extent_ralloc_large_shrink(tsdn_t *tsdn, arena_t *arena,
     extent_t *extent, size_t oldsize);
 void	arena_extent_ralloc_large_expand(tsdn_t *tsdn, arena_t *arena,
     extent_t *extent, size_t oldsize);
-ssize_t	arena_decay_time_get(arena_t *arena);
-bool	arena_decay_time_set(tsdn_t *tsdn, arena_t *arena, ssize_t decay_time);
-void	arena_purge(tsdn_t *tsdn, arena_t *arena, bool all);
+ssize_t arena_dirty_decay_time_get(arena_t *arena);
+bool arena_dirty_decay_time_set(tsdn_t *tsdn, arena_t *arena,
+    ssize_t decay_time);
+ssize_t arena_muzzy_decay_time_get(arena_t *arena);
+bool arena_muzzy_decay_time_set(tsdn_t *tsdn, arena_t *arena,
+    ssize_t decay_time);
+void arena_decay(tsdn_t *tsdn, arena_t *arena, bool all);
 void	arena_reset(tsd_t *tsd, arena_t *arena);
 void	arena_destroy(tsd_t *tsd, arena_t *arena);
 void	arena_tcache_fill_small(tsdn_t *tsdn, arena_t *arena,
@@ -74,8 +79,10 @@ void	*arena_ralloc(tsdn_t *tsdn, arena_t *arena, extent_t *extent, void *ptr,
     size_t oldsize, size_t size, size_t alignment, bool zero, tcache_t *tcache);
 dss_prec_t	arena_dss_prec_get(arena_t *arena);
 bool	arena_dss_prec_set(arena_t *arena, dss_prec_t dss_prec);
-ssize_t	arena_decay_time_default_get(void);
-bool	arena_decay_time_default_set(ssize_t decay_time);
+ssize_t arena_dirty_decay_time_default_get(void);
+bool arena_dirty_decay_time_default_set(ssize_t decay_time);
+ssize_t arena_muzzy_decay_time_default_get(void);
+bool arena_muzzy_decay_time_default_set(ssize_t decay_time);
 unsigned	arena_nthreads_get(arena_t *arena, bool internal);
 void	arena_nthreads_inc(arena_t *arena, bool internal);
 void	arena_nthreads_dec(arena_t *arena, bool internal);
diff --git a/include/jemalloc/internal/arena_inlines_b.h b/include/jemalloc/internal/arena_inlines_b.h
index 275866a..b718451 100644
--- a/include/jemalloc/internal/arena_inlines_b.h
+++ b/include/jemalloc/internal/arena_inlines_b.h
@@ -75,13 +75,14 @@ arena_decay_ticks(tsdn_t *tsdn, arena_t *arena, unsigned nticks) {
 		return;
 	}
 	if (unlikely(ticker_ticks(decay_ticker, nticks))) {
-		arena_purge(tsdn, arena, false);
+		arena_decay(tsdn, arena, false);
 	}
 }
 
 JEMALLOC_ALWAYS_INLINE void
 arena_decay_tick(tsdn_t *tsdn, arena_t *arena) {
-	malloc_mutex_assert_not_owner(tsdn, &arena->decay.mtx);
+	malloc_mutex_assert_not_owner(tsdn, &arena->decay_dirty.mtx);
+	malloc_mutex_assert_not_owner(tsdn, &arena->decay_muzzy.mtx);
 
 	arena_decay_ticks(tsdn, arena, 1);
 }
diff --git a/include/jemalloc/internal/arena_structs_b.h b/include/jemalloc/internal/arena_structs_b.h
index 612b4e7..a5191d1 100644
--- a/include/jemalloc/internal/arena_structs_b.h
+++ b/include/jemalloc/internal/arena_structs_b.h
@@ -48,10 +48,8 @@ struct arena_decay_s {
 	 * Approximate time in seconds from the creation of a set of unused
 	 * dirty pages until an equivalent set of unused dirty pages is purged
 	 * and/or reused.
-	 *
-	 * Synchronization: atomic.
 	 */
-	ssize_t			time;
+	atomic_zd_t		time;
 	/* time / SMOOTHSTEP_NSTEPS. */
 	nstime_t		interval;
 	/*
@@ -73,10 +71,10 @@ struct arena_decay_s {
 	 */
 	nstime_t		deadline;
 	/*
-	 * Number of dirty pages at beginning of current epoch.  During epoch
-	 * advancement we use the delta between arena->decay.ndirty and
-	 * extents_npages_get(&arena->extents_cached) to determine how many
-	 * dirty pages, if any, were generated.
+	 * Number of unpurged pages at beginning of current epoch.  During epoch
+	 * advancement we use the delta between arena->decay_*.nunpurged and
+	 * extents_npages_get(&arena->extents_*) to determine how many dirty
+	 * pages, if any, were generated.
 	 */
 	size_t			nunpurged;
 	/*
@@ -86,6 +84,14 @@ struct arena_decay_s {
 	 * relative to epoch.
 	 */
 	size_t			backlog[SMOOTHSTEP_NSTEPS];
+
+	/*
+	 * Pointer to associated stats.  These stats are embedded directly in
+	 * the arena's stats due to how stats structures are shared between the
+	 * arena and ctl code.
+	 *
+	 * Synchronization: Same as associated arena's stats field. */
+	decay_stats_t		*stats;
 };
 
 struct arena_bin_s {
@@ -194,15 +200,18 @@ struct arena_s {
 	 *
 	 * Synchronization: internal.
 	 */
-	extents_t		extents_cached;
+	extents_t		extents_dirty;
+	extents_t		extents_muzzy;
 	extents_t		extents_retained;
 
 	/*
-	 * Decay-based purging state.
+	 * Decay-based purging state, responsible for scheduling extent state
+	 * transitions.
 	 *
 	 * Synchronization: internal.
 	 */
-	arena_decay_t		decay;
+	arena_decay_t		decay_dirty; /* dirty --> muzzy */
+	arena_decay_t		decay_muzzy; /* muzzy --> retained */
 
 	/*
 	 * Next extent size class in a growing series to use when satisfying a
diff --git a/include/jemalloc/internal/arena_types.h b/include/jemalloc/internal/arena_types.h
index 067c9ee..ba53c40 100644
--- a/include/jemalloc/internal/arena_types.h
+++ b/include/jemalloc/internal/arena_types.h
@@ -7,8 +7,9 @@
 #define LG_SLAB_MAXREGS		(LG_PAGE - LG_TINY_MIN)
 #define SLAB_MAXREGS		(1U << LG_SLAB_MAXREGS)
 
-/* Default decay time in seconds. */
-#define DECAY_TIME_DEFAULT	10
+/* Default decay times in seconds. */
+#define DIRTY_DECAY_TIME_DEFAULT	10
+#define MUZZY_DECAY_TIME_DEFAULT	10
 /* Number of event ticks between time checks. */
 #define DECAY_NTICKS_PER_UPDATE	1000
 
diff --git a/include/jemalloc/internal/ctl_structs.h b/include/jemalloc/internal/ctl_structs.h
index 18806a5..4df43d9 100644
--- a/include/jemalloc/internal/ctl_structs.h
+++ b/include/jemalloc/internal/ctl_structs.h
@@ -51,9 +51,11 @@ struct ctl_arena_s {
 	/* Basic stats, supported even if !config_stats. */
 	unsigned		nthreads;
 	const char		*dss;
-	ssize_t			decay_time;
+	ssize_t			dirty_decay_time;
+	ssize_t			muzzy_decay_time;
 	size_t			pactive;
 	size_t			pdirty;
+	size_t			pmuzzy;
 
 	/* NULL if !config_stats. */
 	ctl_arena_stats_t	*astats;
diff --git a/include/jemalloc/internal/extent_externs.h b/include/jemalloc/internal/extent_externs.h
index ef2467e..e8f632f 100644
--- a/include/jemalloc/internal/extent_externs.h
+++ b/include/jemalloc/internal/extent_externs.h
@@ -21,20 +21,21 @@ bool extents_init(tsdn_t *tsdn, extents_t *extents, extent_state_t state,
     bool delay_coalesce);
 extent_state_t extents_state_get(const extents_t *extents);
 size_t extents_npages_get(extents_t *extents);
+extent_t *extents_alloc(tsdn_t *tsdn, arena_t *arena,
+    extent_hooks_t **r_extent_hooks, extents_t *extents, void *new_addr,
+    size_t usize, size_t pad, size_t alignment, bool *zero, bool *commit,
+    bool slab);
+void extents_dalloc(tsdn_t *tsdn, arena_t *arena,
+    extent_hooks_t **r_extent_hooks, extents_t *extents, extent_t *extent);
 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);
-extent_t	*extent_alloc_cache(tsdn_t *tsdn, arena_t *arena,
-    extent_hooks_t **r_extent_hooks, void *new_addr, size_t usize, size_t pad,
-    size_t alignment, bool *zero, bool *commit, bool slab);
 extent_t	*extent_alloc_wrapper(tsdn_t *tsdn, arena_t *arena,
     extent_hooks_t **r_extent_hooks, void *new_addr, size_t usize, size_t pad,
     size_t alignment, bool *zero, bool *commit, bool slab);
 void	extent_dalloc_gap(tsdn_t *tsdn, arena_t *arena, extent_t *extent);
-void	extent_dalloc_cache(tsdn_t *tsdn, arena_t *arena,
-    extent_hooks_t **r_extent_hooks, extent_t *extent);
 bool	extent_dalloc_wrapper_try(tsdn_t *tsdn, arena_t *arena,
     extent_hooks_t **r_extent_hooks, extent_t *extent);
 void	extent_dalloc_wrapper(tsdn_t *tsdn, arena_t *arena,
diff --git a/include/jemalloc/internal/extent_structs.h b/include/jemalloc/internal/extent_structs.h
index c14aef8..001b7c1 100644
--- a/include/jemalloc/internal/extent_structs.h
+++ b/include/jemalloc/internal/extent_structs.h
@@ -4,7 +4,8 @@
 typedef enum {
 	extent_state_active   = 0,
 	extent_state_dirty    = 1,
-	extent_state_retained = 2
+	extent_state_muzzy    = 2,
+	extent_state_retained = 3
 } extent_state_t;
 
 /* Extent (span of pages).  Use accessor functions for e_* fields. */
diff --git a/include/jemalloc/internal/private_symbols.txt b/include/jemalloc/internal/private_symbols.txt
index c0211e5..5ca7281 100644
--- a/include/jemalloc/internal/private_symbols.txt
+++ b/include/jemalloc/internal/private_symbols.txt
@@ -15,21 +15,26 @@ arena_dalloc_bin_junked_locked
 arena_dalloc_junk_small
 arena_dalloc_promoted
 arena_dalloc_small
+arena_decay
 arena_decay_tick
 arena_decay_ticks
-arena_decay_time_default_get
-arena_decay_time_default_set
-arena_decay_time_get
-arena_decay_time_set
+arena_dirty_decay_time_default_get
+arena_dirty_decay_time_default_set
+arena_dirty_decay_time_get
+arena_dirty_decay_time_set
+arena_muzzy_decay_time_default_get
+arena_muzzy_decay_time_default_set
+arena_muzzy_decay_time_get
+arena_muzzy_decay_time_set
 arena_destroy
 arena_dss_prec_get
 arena_dss_prec_set
 arena_extent_alloc_large
-arena_extent_cache_dalloc
 arena_extent_dalloc_large_prep
 arena_extent_ralloc_large_expand
 arena_extent_ralloc_large_shrink
 arena_extent_sn_next
+arena_extents_dirty_dalloc
 arena_get
 arena_ichoose
 arena_ind_get
@@ -59,7 +64,6 @@ arena_prof_promote
 arena_prof_tctx_get
 arena_prof_tctx_reset
 arena_prof_tctx_set
-arena_purge
 arena_ralloc
 arena_ralloc_no_move
 arena_reset
@@ -138,7 +142,6 @@ extent_commit_wrapper
 extent_committed_get
 extent_committed_set
 extent_dalloc
-extent_dalloc_cache
 extent_dalloc_gap
 extent_dalloc_mmap
 extent_dalloc_wrapper
@@ -192,6 +195,8 @@ extent_usize_get
 extent_usize_set
 extent_zeroed_get
 extent_zeroed_set
+extents_alloc
+extents_dalloc
 extents_evict
 extents_init
 extents_npages_get
@@ -299,7 +304,8 @@ nstime_sec
 nstime_subtract
 nstime_update
 opt_abort
-opt_decay_time
+opt_dirty_decay_time
+opt_muzzy_decay_time
 opt_dss
 opt_junk
 opt_junk_alloc
diff --git a/include/jemalloc/internal/stats_structs.h b/include/jemalloc/internal/stats_structs.h
index 4e9c898..ffcb3c1 100644
--- a/include/jemalloc/internal/stats_structs.h
+++ b/include/jemalloc/internal/stats_structs.h
@@ -77,6 +77,15 @@ struct malloc_large_stats_s {
 	size_t		curlextents; /* Derived. */
 };
 
+struct decay_stats_s {
+	/* Total number of purge sweeps. */
+	arena_stats_u64_t	npurge;
+	/* Total number of madvise calls made. */
+	arena_stats_u64_t	nmadvise;
+	/* Total number of pages purged. */
+	arena_stats_u64_t	purged;
+};
+
 /*
  * Arena stats.  Note that fields marked "derived" are not directly maintained
  * within the arena code; rather their values are derived during stats merge
@@ -84,7 +93,7 @@ struct malloc_large_stats_s {
  */
 struct arena_stats_s {
 #ifndef JEMALLOC_ATOMIC_U64
-	malloc_mutex_t	mtx;
+	malloc_mutex_t		mtx;
 #endif
 
 	/* Number of bytes currently mapped, excluding retained memory. */
@@ -98,14 +107,8 @@ struct arena_stats_s {
 	 */
 	atomic_zu_t		retained; /* Derived. */
 
-	/*
-	 * Total number of purge sweeps, total number of madvise calls made,
-	 * and total pages purged in order to keep dirty unused memory under
-	 * control.
-	 */
-	arena_stats_u64_t	npurge;
-	arena_stats_u64_t	nmadvise;
-	arena_stats_u64_t	purged;
+	decay_stats_t		decay_dirty;
+	decay_stats_t		decay_muzzy;
 
 	atomic_zu_t		base; /* Derived. */
 	atomic_zu_t		internal;
diff --git a/include/jemalloc/internal/stats_types.h b/include/jemalloc/internal/stats_types.h
index f202b23..4848338 100644
--- a/include/jemalloc/internal/stats_types.h
+++ b/include/jemalloc/internal/stats_types.h
@@ -4,6 +4,7 @@
 typedef struct tcache_bin_stats_s tcache_bin_stats_t;
 typedef struct malloc_bin_stats_s malloc_bin_stats_t;
 typedef struct malloc_large_stats_s malloc_large_stats_t;
+typedef struct decay_stats_s decay_stats_t;
 typedef struct arena_stats_s arena_stats_t;
 
 #endif /* JEMALLOC_INTERNAL_STATS_TYPES_H */