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.

1 files changed, 181 insertions, 58 deletions

diff --git a/doc/jemalloc.xml.in b/doc/jemalloc.xml.in
index 937879a8..7faa474d 100644
--- a/doc/jemalloc.xml.in
+++ b/doc/jemalloc.xml.in
@@ -944,24 +944,54 @@ mallctl("arena." STRINGIFY(MALLCTL_ARENAS_ALL) ".decay",
         <quote>percpu</quote>. </para></listitem>
       </varlistentry>
 
-      <varlistentry id="opt.decay_time">
+      <varlistentry id="opt.dirty_decay_time">
         <term>
-          <mallctl>opt.decay_time</mallctl>
+          <mallctl>opt.dirty_decay_time</mallctl>
           (<type>ssize_t</type>)
           <literal>r-</literal>
         </term>
         <listitem><para>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.  The pages are incrementally purged according to a
-        sigmoidal decay curve that starts and ends with zero purge rate.  A
-        decay time of 0 causes all unused dirty pages to be purged immediately
-        upon creation.  A decay time of -1 disables purging.  The default decay
-        time is 10 seconds.  See <link
-        linkend="arenas.decay_time"><mallctl>arenas.decay_time</mallctl></link>
+        purged (i.e. converted to muzzy via e.g.
+        <function>madvise(<parameter>...</parameter><parameter><constant>MADV_FREE</constant></parameter>)</function>
+        if supported by the operating system, or converted to clean otherwise)
+        and/or reused.  Dirty pages are defined as previously having been
+        potentially written to by the application, and therefore consuming
+        physical memory, yet having no current use.  The pages are incrementally
+        purged according to a sigmoidal decay curve that starts and ends with
+        zero purge rate.  A decay time of 0 causes all unused dirty pages to be
+        purged immediately upon creation.  A decay time of -1 disables purging.
+        The default decay time is 10 seconds.  See <link
+        linkend="arenas.dirty_decay_time"><mallctl>arenas.dirty_decay_time</mallctl></link>
         and <link
-        linkend="arena.i.decay_time"><mallctl>arena.&lt;i&gt;.decay_time</mallctl></link>
-        for related dynamic control options.
-        </para></listitem>
+        linkend="arena.i.muzzy_decay_time"><mallctl>arena.&lt;i&gt;.muzzy_decay_time</mallctl></link>
+        for related dynamic control options.  See <link
+        linkend="opt.muzzy_decay_time"><mallctl>opt.muzzy_decay_time</mallctl></link>
+        for a description of muzzy pages.</para></listitem>
+      </varlistentry>
+
+      <varlistentry id="opt.muzzy_decay_time">
+        <term>
+          <mallctl>opt.muzzy_decay_time</mallctl>
+          (<type>ssize_t</type>)
+          <literal>r-</literal>
+        </term>
+        <listitem><para>Approximate time in seconds from the creation of a set
+        of unused muzzy pages until an equivalent set of unused muzzy pages is
+        purged (i.e. converted to clean) and/or reused.  Muzzy pages are defined
+        as previously having been unused dirty pages that were subsequently
+        purged in a manner that left them subject to the reclamation whims of
+        the operating system (e.g.
+        <function>madvise(<parameter>...</parameter><parameter><constant>MADV_FREE</constant></parameter>)</function>),
+        and therefore in an indeterminate state.  The pages are incrementally
+        purged according to a sigmoidal decay curve that starts and ends with
+        zero purge rate.  A decay time of 0 causes all unused muzzy pages to be
+        purged immediately upon creation.  A decay time of -1 disables purging.
+        The default decay time is 10 seconds.  See <link
+        linkend="arenas.muzzy_decay_time"><mallctl>arenas.muzzy_decay_time</mallctl></link>
+        and <link
+        linkend="arena.i.muzzy_decay_time"><mallctl>arena.&lt;i&gt;.muzzy_decay_time</mallctl></link>
+        for related dynamic control options.</para></listitem>
       </varlistentry>
 
       <varlistentry id="opt.stats_print">
@@ -1460,29 +1490,31 @@ malloc_conf = "xmalloc:true";]]></programlisting>
         initialized (always true).</para></listitem>
       </varlistentry>
 
-      <varlistentry id="arena.i.purge">
+      <varlistentry id="arena.i.decay">
         <term>
-          <mallctl>arena.&lt;i&gt;.purge</mallctl>
+          <mallctl>arena.&lt;i&gt;.decay</mallctl>
           (<type>void</type>)
           <literal>--</literal>
         </term>
-        <listitem><para>Purge all unused dirty pages for arena &lt;i&gt;, or for
-        all arenas if &lt;i&gt; equals <constant>MALLCTL_ARENAS_ALL</constant>.
-        </para></listitem>
+        <listitem><para>Trigger decay-based purging of unused dirty/muzzy pages
+        for arena &lt;i&gt;, or for all arenas if &lt;i&gt; equals
+        <constant>MALLCTL_ARENAS_ALL</constant>.  The proportion of unused
+        dirty/muzzy pages to be purged depends on the current time; see <link
+        linkend="opt.dirty_decay_time"><mallctl>opt.dirty_decay_time</mallctl></link>
+        and <link
+        linkend="opt.muzzy_decay_time"><mallctl>opt.muzy_decay_time</mallctl></link>
+        for details.</para></listitem>
       </varlistentry>
 
-      <varlistentry id="arena.i.decay">
+      <varlistentry id="arena.i.purge">
         <term>
-          <mallctl>arena.&lt;i&gt;.decay</mallctl>
+          <mallctl>arena.&lt;i&gt;.purge</mallctl>
           (<type>void</type>)
           <literal>--</literal>
         </term>
-        <listitem><para>Trigger decay-based purging of unused dirty pages for
-        arena &lt;i&gt;, or for all arenas if &lt;i&gt; equals
-        <constant>MALLCTL_ARENAS_ALL</constant>.  The proportion of unused dirty
-        pages to be purged depends on the current time; see <link
-        linkend="opt.decay_time"><mallctl>opt.decay_time</mallctl></link> for
-        details.</para></listitem>
+        <listitem><para>Purge all unused dirty pages for arena &lt;i&gt;, or for
+        all arenas if &lt;i&gt; equals <constant>MALLCTL_ARENAS_ALL</constant>.
+        </para></listitem>
       </varlistentry>
 
       <varlistentry id="arena.i.reset">
@@ -1532,9 +1564,9 @@ malloc_conf = "xmalloc:true";]]></programlisting>
         settings.</para></listitem>
       </varlistentry>
 
-      <varlistentry id="arena.i.decay_time">
+      <varlistentry id="arena.i.dirty_decay_time">
         <term>
-          <mallctl>arena.&lt;i&gt;.decay_time</mallctl>
+          <mallctl>arena.&lt;i&gt;.dirty_decay_time</mallctl>
           (<type>ssize_t</type>)
           <literal>rw</literal>
         </term>
@@ -1544,8 +1576,24 @@ malloc_conf = "xmalloc:true";]]></programlisting>
         set, all currently unused dirty pages are considered to have fully
         decayed, which causes immediate purging of all unused dirty pages unless
         the decay time is set to -1 (i.e. purging disabled).  See <link
-        linkend="opt.decay_time"><mallctl>opt.decay_time</mallctl></link> for
-        additional information.</para></listitem>
+        linkend="opt.dirty_decay_time"><mallctl>opt.dirty_decay_time</mallctl></link>
+        for additional information.</para></listitem>
+      </varlistentry>
+
+      <varlistentry id="arena.i.muzzy_decay_time">
+        <term>
+          <mallctl>arena.&lt;i&gt;.muzzy_decay_time</mallctl>
+          (<type>ssize_t</type>)
+          <literal>rw</literal>
+        </term>
+        <listitem><para>Current per-arena approximate time in seconds from the
+        creation of a set of unused muzzy pages until an equivalent set of
+        unused muzzy pages is purged and/or reused.  Each time this interface is
+        set, all currently unused muzzy pages are considered to have fully
+        decayed, which causes immediate purging of all unused muzzy pages unless
+        the decay time is set to -1 (i.e. purging disabled).  See <link
+        linkend="opt.muzzy_decay_time"><mallctl>opt.muzzy_decay_time</mallctl></link>
+        for additional information.</para></listitem>
       </varlistentry>
 
       <varlistentry id="arena.i.extent_hooks">
@@ -1584,7 +1632,7 @@ struct extent_hooks_s {
         mapped committed memory, in the simplest case followed by deallocation.
         However, there are performance and platform reasons to retain extents
         for later reuse.  Cleanup attempts cascade from deallocation to decommit
-        to lazy purging to forced purging, which gives the extent management
+        to forced purging to lazy purging, which gives the extent management
         functions opportunities to reject the most permanent cleanup operations
         in favor of less permanent (and often less costly) operations.  All
         operations except allocation can be universally opted out of by setting
@@ -1707,12 +1755,14 @@ struct extent_hooks_s {
         <parameter>addr</parameter> and <parameter>size</parameter> at
         <parameter>offset</parameter> bytes, extending for
         <parameter>length</parameter> on behalf of arena
-        <parameter>arena_ind</parameter>.  A lazy extent purge function can
-        delay purging indefinitely and leave the pages within the purged virtual
-        memory range in an indeterminite state, whereas a forced extent purge
-        function immediately purges, and the pages within the virtual memory
-        range will be zero-filled the next time they are accessed.  If the
-        function returns true, this indicates failure to purge.</para>
+        <parameter>arena_ind</parameter>.  A lazy extent purge function (e.g.
+        implemented via
+        <function>madvise(<parameter>...</parameter><parameter><constant>MADV_FREE</constant></parameter>)</function>)
+        can delay purging indefinitely and leave the pages within the purged
+        virtual memory range in an indeterminite state, whereas a forced extent
+        purge function immediately purges, and the pages within the virtual
+        memory range will be zero-filled the next time they are accessed.  If
+        the function returns true, this indicates failure to purge.</para>
 
         <funcsynopsis><funcprototype>
           <funcdef>typedef bool <function>(extent_split_t)</function></funcdef>
@@ -1769,19 +1819,34 @@ struct extent_hooks_s {
         <listitem><para>Current limit on number of arenas.</para></listitem>
       </varlistentry>
 
-      <varlistentry id="arenas.decay_time">
+      <varlistentry id="arenas.dirty_decay_time">
         <term>
-          <mallctl>arenas.decay_time</mallctl>
+          <mallctl>arenas.dirty_decay_time</mallctl>
           (<type>ssize_t</type>)
           <literal>rw</literal>
         </term>
         <listitem><para>Current default per-arena 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, used to initialize <link
-        linkend="arena.i.decay_time"><mallctl>arena.&lt;i&gt;.decay_time</mallctl></link>
+        linkend="arena.i.dirty_decay_time"><mallctl>arena.&lt;i&gt;.dirty_decay_time</mallctl></link>
         during arena creation.  See <link
-        linkend="opt.decay_time"><mallctl>opt.decay_time</mallctl></link> for
-        additional information.</para></listitem>
+        linkend="opt.dirty_decay_time"><mallctl>opt.dirty_decay_time</mallctl></link>
+        for additional information.</para></listitem>
+      </varlistentry>
+
+      <varlistentry id="arenas.muzzy_decay_time">
+        <term>
+          <mallctl>arenas.muzzy_decay_time</mallctl>
+          (<type>ssize_t</type>)
+          <literal>rw</literal>
+        </term>
+        <listitem><para>Current default per-arena approximate time in seconds
+        from the creation of a set of unused muzzy pages until an equivalent set
+        of unused muzzy pages is purged and/or reused, used to initialize <link
+        linkend="arena.i.muzzy_decay_time"><mallctl>arena.&lt;i&gt;.muzzy_decay_time</mallctl></link>
+        during arena creation.  See <link
+        linkend="opt.muzzy_decay_time"><mallctl>opt.muzzy_decay_time</mallctl></link>
+        for additional information.</para></listitem>
       </varlistentry>
 
       <varlistentry id="arenas.quantum">
@@ -2014,7 +2079,9 @@ struct extent_hooks_s {
         equal to <link
         linkend="stats.allocated"><mallctl>stats.allocated</mallctl></link>.
         This does not include <link linkend="stats.arenas.i.pdirty">
-        <mallctl>stats.arenas.&lt;i&gt;.pdirty</mallctl></link>, nor pages
+        <mallctl>stats.arenas.&lt;i&gt;.pdirty</mallctl></link>,
+        <link linkend="stats.arenas.i.pmuzzy">
+        <mallctl>stats.arenas.&lt;i&gt;.pmuzzy</mallctl></link>, nor pages
         entirely devoted to allocator metadata.</para></listitem>
       </varlistentry>
 
@@ -2099,16 +2166,29 @@ struct extent_hooks_s {
         </para></listitem>
       </varlistentry>
 
-      <varlistentry id="stats.arenas.i.decay_time">
+      <varlistentry id="stats.arenas.i.dirty_decay_time">
         <term>
-          <mallctl>stats.arenas.&lt;i&gt;.decay_time</mallctl>
+          <mallctl>stats.arenas.&lt;i&gt;.dirty_decay_time</mallctl>
           (<type>ssize_t</type>)
           <literal>r-</literal>
         </term>
         <listitem><para>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.  See <link
-        linkend="opt.decay_time"><mallctl>opt.decay_time</mallctl></link>
+        linkend="opt.dirty_decay_time"><mallctl>opt.dirty_decay_time</mallctl></link>
+        for details.</para></listitem>
+      </varlistentry>
+
+      <varlistentry id="stats.arenas.i.muzzy_decay_time">
+        <term>
+          <mallctl>stats.arenas.&lt;i&gt;.muzzy_decay_time</mallctl>
+          (<type>ssize_t</type>)
+          <literal>r-</literal>
+        </term>
+        <listitem><para>Approximate time in seconds from the creation of a set
+        of unused muzzy pages until an equivalent set of unused muzzy pages is
+        purged and/or reused.  See <link
+        linkend="opt.muzzy_decay_time"><mallctl>opt.muzzy_decay_time</mallctl></link>
         for details.</para></listitem>
       </varlistentry>
 
@@ -2138,10 +2218,22 @@ struct extent_hooks_s {
           <literal>r-</literal>
         </term>
         <listitem><para>Number of pages within unused extents that are
-        potentially dirty, and for which
-        <function>madvise(<parameter>...</parameter>
-        <parameter><constant>MADV_DONTNEED</constant></parameter>)</function> or
-        similar has not been called.</para></listitem>
+        potentially dirty, and for which <function>madvise()</function> or
+        similar has not been called.  See <link
+        linkend="opt.dirty_decay_time"><mallctl>opt.dirty_decay_time</mallctl></link>
+        for a description of dirty pages.</para></listitem>
+      </varlistentry>
+
+      <varlistentry id="stats.arenas.i.pmuzzy">
+        <term>
+          <mallctl>stats.arenas.&lt;i&gt;.pmuzzy</mallctl>
+          (<type>size_t</type>)
+          <literal>r-</literal>
+        </term>
+        <listitem><para>Number of pages within unused extents that are muzzy.
+        See <link
+        linkend="opt.muzzy_decay_time"><mallctl>opt.muzzy_decay_time</mallctl></link>
+        for a description of muzzy pages.</para></listitem>
       </varlistentry>
 
       <varlistentry id="stats.arenas.i.mapped">
@@ -2207,9 +2299,9 @@ struct extent_hooks_s {
         size.</para></listitem>
       </varlistentry>
 
-      <varlistentry id="stats.arenas.i.npurge">
+      <varlistentry id="stats.arenas.i.dirty_npurge">
         <term>
-          <mallctl>stats.arenas.&lt;i&gt;.npurge</mallctl>
+          <mallctl>stats.arenas.&lt;i&gt;.dirty_npurge</mallctl>
           (<type>uint64_t</type>)
           <literal>r-</literal>
           [<option>--enable-stats</option>]
@@ -2218,26 +2310,57 @@ struct extent_hooks_s {
         </para></listitem>
       </varlistentry>
 
-      <varlistentry id="stats.arenas.i.nmadvise">
+      <varlistentry id="stats.arenas.i.dirty_nmadvise">
+        <term>
+          <mallctl>stats.arenas.&lt;i&gt;.dirty_nmadvise</mallctl>
+          (<type>uint64_t</type>)
+          <literal>r-</literal>
+          [<option>--enable-stats</option>]
+        </term>
+        <listitem><para>Number of <function>madvise()</function> or similar
+        calls made to purge dirty pages.</para></listitem>
+      </varlistentry>
+
+      <varlistentry id="stats.arenas.i.dirty_purged">
+        <term>
+          <mallctl>stats.arenas.&lt;i&gt;.dirty_purged</mallctl>
+          (<type>uint64_t</type>)
+          <literal>r-</literal>
+          [<option>--enable-stats</option>]
+        </term>
+        <listitem><para>Number of dirty pages purged.</para></listitem>
+      </varlistentry>
+
+      <varlistentry id="stats.arenas.i.muzzy_npurge">
+        <term>
+          <mallctl>stats.arenas.&lt;i&gt;.muzzy_npurge</mallctl>
+          (<type>uint64_t</type>)
+          <literal>r-</literal>
+          [<option>--enable-stats</option>]
+        </term>
+        <listitem><para>Number of muzzy page purge sweeps performed.
+        </para></listitem>
+      </varlistentry>
+
+      <varlistentry id="stats.arenas.i.muzzy_nmadvise">
         <term>
-          <mallctl>stats.arenas.&lt;i&gt;.nmadvise</mallctl>
+          <mallctl>stats.arenas.&lt;i&gt;.muzzy_nmadvise</mallctl>
           (<type>uint64_t</type>)
           <literal>r-</literal>
           [<option>--enable-stats</option>]
         </term>
-        <listitem><para>Number of <function>madvise(<parameter>...</parameter>
-        <parameter><constant>MADV_DONTNEED</constant></parameter>)</function> or
-        similar calls made to purge dirty pages.</para></listitem>
+        <listitem><para>Number of <function>madvise()</function> or similar
+        calls made to purge muzzy pages.</para></listitem>
       </varlistentry>
 
-      <varlistentry id="stats.arenas.i.purged">
+      <varlistentry id="stats.arenas.i.muzzy_purged">
         <term>
-          <mallctl>stats.arenas.&lt;i&gt;.purged</mallctl>
+          <mallctl>stats.arenas.&lt;i&gt;.muzzy_purged</mallctl>
           (<type>uint64_t</type>)
           <literal>r-</literal>
           [<option>--enable-stats</option>]
         </term>
-        <listitem><para>Number of pages purged.</para></listitem>
+        <listitem><para>Number of muzzy pages purged.</para></listitem>
       </varlistentry>
 
       <varlistentry id="stats.arenas.i.small.allocated">