Update docs for central page heap to reflect tree

3 files changed, 26 insertions, 17 deletions

diff --git a/docs/pageheap.dot b/docs/pageheap.dot
index 82e5fd5..ac84b90 100644
--- a/docs/pageheap.dot
+++ b/docs/pageheap.dot
@@ -3,7 +3,7 @@ rankdir=LR
 node [shape=box, width=0.3, height=0.3]
 nodesep=.05
 
-heap [shape=record, height=3, label="<f0>1 page|<f1>2 pages|<f2>3 pages|...|<f255>255 pages|<frest>rest"]
+heap [shape=record, height=3, label="<f0>1 page|<f1>2 pages|<f2>3 pages|...|<f127>127 pages"]
 O0 [shape=record, label=""]
 O1 [shape=record, label=""]
 O2 [shape=record, label="{|}"]
@@ -12,18 +12,14 @@ O4 [shape=record, label="{||}"]
 O5 [shape=record, label="{||}"]
 O6 [shape=record, label="{|...|}"]
 O7 [shape=record, label="{|...|}"]
-O8 [shape=record, label="{|.....|}"]
-O9 [shape=record, label="{|.....|}"]
 sep1 [shape=plaintext, label="..."]
 sep2 [shape=plaintext, label="..."]
 sep3 [shape=plaintext, label="..."]
 sep4 [shape=plaintext, label="..."]
-sep5 [shape=plaintext, label="..."]
 
 heap:f0 -> O0 -> O1 -> sep1
 heap:f1 -> O2 -> O3 -> sep2
 heap:f2 -> O4 -> O5 -> sep3
-heap:f255 -> O6 -> O7 -> sep4
-heap:frest -> O8 -> O9 -> sep5
+heap:f127 -> O6 -> O7 -> sep4
 
 }
diff --git a/docs/pageheap.gif b/docs/pageheap.gif
index 6632981..76b62e8 100644
--- a/docs/pageheap.gif
+++ b/docs/pageheap.gif
diff --git a/docs/tcmalloc.html b/docs/tcmalloc.html
index 117e05d..62dae72 100644
--- a/docs/tcmalloc.html
+++ b/docs/tcmalloc.html
@@ -196,22 +196,35 @@ Deallocation
 See also the section on <a href="#Garbage_Collection">Garbage Collection</a>
 to see how it affects the <code>max_length</code>.
 
-<h2><A NAME="Large_Object_Allocation">Large Object Allocation</A></h2>
+<h2><A NAME="Medium_Object_Allocation">Medium Object Allocation</A></h2>
 
-<p>A large object size (&gt; 256K) is rounded up to a page size (8K)
-and is handled by a central page heap.  The central page heap is again
-an array of free lists.  For <code>i &lt; 128</code>, the
-<code>k</code>th entry is a free list of runs that consist of
-<code>k</code> pages.  The <code>128</code>th entry is a free list of
-runs that have length <code>&gt;= 128</code> pages: </p>
+<p>A medium object size (256K &le; size &le; 1MB) is rounded up to a page
+size (8K) and is handled by a central page heap. The central page heap
+includes an array of 128 free lists.  The <code>k</code>th entry is a
+free list of runs that consist of <code>k</code> pages:</p>
 <center><img src="pageheap.gif"></center>
 
 <p>An allocation for <code>k</code> pages is satisfied by looking in
 the <code>k</code>th free list.  If that free list is empty, we look
-in the next free list, and so forth.  Eventually, we look in the last
-free list if necessary.  If that fails, we fetch memory from the
-system (using <code>sbrk</code>, <code>mmap</code>, or by mapping in
-portions of <code>/dev/mem</code>).</p>
+in the next free list, and so forth.  If no medium-object free list
+can satisfy the allocation, the allocation is treated as a large object.
+
+
+<h2><A NAME="Large_Object_Allocation">Large Object Allocation</A></h2>
+
+Allocations of 1MB or more are considered large allocations. Spans
+of free memory which can satisfy these allocations are tracked in
+a red-black tree sorted by size. Allocations follow the <em>best-fit</em>
+algorithm: the tree is searched to find the smallest span of free
+space which is larger than the requested allocation. The allocation
+is carved out of that span, and the remaining space is reinserted
+either into the large object tree or possibly into one of the smaller
+free-lists as appropriate.
+
+If no span of free memory is located that can fit the requested
+allocation, we fetch memory from the system (using <code>sbrk</code>,
+<code>mmap</code>, or by mapping in portions of
+<code>/dev/mem</code>).</p>
 
 <p>If an allocation for <code>k</code> pages is satisfied by a run
 of pages of length &gt; <code>k</code>, the remainder of the