issue-489: ported chromium windows decommitting code

I tried to do it cleanly with merges but chromium code has so many
relevant commits (with frequent reverts) that makes it near
impossible.

Simpler 2-way emerge-files worked in the end. I've removed chromium's
aggressive 'always decommit' behavior which I want to make optional
later.

Majority of this work is the following commits (but there are more,
particularly against port.cc):

commit 9c92338c5f8770c440799d24387c3733fd6d826b
Author: jamesr@chromium.org <jamesr@chromium.org@0039d316-1c4b-4281-b951-d872f2087c98>
Date:   Tue Oct 6 18:33:31 2009 +0000

    Tracks the amount of committed vs uncommitted memory in tcmalloc's page heap's freelists

    Keeps track of the number of reserved but not committed pages in the freelist and uses that to calculate a waste metric, which is the ratio of committed pages vs pages used by the application.  This is exposed in the GetStats() call (which is used for about:tcmalloc) and through GetNumericalProperty() in Malloc

    BUG=none
    TEST=open about:tcmalloc and monitor 'WASTE' columns while using the browser

    Review URL: http://codereview.chromium.org/251065

    git-svn-id: svn://svn.chromium.org/chrome/trunk/src@28133 0039d316-1c4b-4281-b951-d872f2087c98

commit aef4f1be3eec2059a7c6e2c106050a5f3d6ccf12
Author: jar@chromium.org <jar@chromium.org@0039d316-1c4b-4281-b951-d872f2087c98>
Date:   Mon Oct 5 17:58:51 2009 +0000

    Revert further back to MBelshe's baseline forking TCMalloc

    This changes to decommitting in all paths through the
    page_heap delete method (which adds spans to the free lists).

    r=mbelshe,jamesr
    Review URL: http://codereview.chromium.org/255067

    git-svn-id: svn://svn.chromium.org/chrome/trunk/src@28006 0039d316-1c4b-4281-b951-d872f2087c98

commit e94afbb913b95f512cb8745a2729c73f82b15ae7
Author: jar@chromium.org <jar@chromium.org@0039d316-1c4b-4281-b951-d872f2087c98>
Date:   Thu Oct 1 00:25:41 2009 +0000

    Rollback Scavenge implemetation and rely on existing functionality to free

    This is a landing of a patch provided by antonm.  See:
    http://codereview.chromium.org/235022

    Also included change to browser_about_handler.cc to fix build, and I set
    TCMALLOC_RELEASE_RATE to 1.0 on line 40 of page_heap.cc (I think this
    was an inadvertent rollback element).

    r=antonm
    Review URL: http://codereview.chromium.org/257009

    git-svn-id: svn://svn.chromium.org/chrome/trunk/src@27692 0039d316-1c4b-4281-b951-d872f2087c98

commit c585892d2c42a47c95d06a684a6685156c545403
Author: mbelshe@google.com <mbelshe@google.com@0039d316-1c4b-4281-b951-d872f2087c98>
Date:   Wed Sep 2 17:33:23 2009 +0000

    Landing for Anton Muhin's tcmalloc patch:
    http://codereview.chromium.org/180021/show

    Restore decommitting in IncrementalScavenge and draft Scavenge method to
    be invoked periodically
    to reduce amount of committed pages.

    BUG=none
    TEST=none

    Review URL: http://codereview.chromium.org/187008

    git-svn-id: svn://svn.chromium.org/chrome/trunk/src@25188 0039d316-1c4b-4281-b951-d872f2087c98

commit 14239acc00731e94736ac62e80fc6b17c31ea131
Author: mbelshe@google.com <mbelshe@google.com@0039d316-1c4b-4281-b951-d872f2087c98>
Date:   Wed Aug 12 02:17:14 2009 +0000

    Major changes to the Chrome allocator.

    Changes include:
    * Fix tcmalloc to release memory.  Implements the TCMalloc_SystemCommit()
      mechanism so that tcmalloc can implement SystemRelease() and later
      reuse that memory.
    * Enable dynamic switching of allocators based on an environment variable.
      Users can now switch between tcmalloc, jemalloc, the default windows
      heap, and the windows low-fragmentation heap.
    * Implements set_new_mode() across all allocators so that we can be sure
      that out-of-memory conditions are handled safely.

    BUG=18345
    TEST=none; plan to get all unit tests running through these allocators.

    Review URL: http://codereview.chromium.org/165275

    git-svn-id: svn://svn.chromium.org/chrome/trunk/src@23140 0039d316-1c4b-4281-b951-d872f2087c98

5 files changed, 123 insertions, 20 deletions

diff --git a/src/page_heap.cc b/src/page_heap.cc
index 6b92321..651a93a 100644
--- a/src/page_heap.cc
+++ b/src/page_heap.cc
@@ -153,6 +153,7 @@ Span* PageHeap::New(Length n) {
 
   // Grow the heap and try again.
   if (!GrowHeap(n)) {
+    ASSERT(stats_.unmapped_bytes+ stats_.committed_bytes==stats_.system_bytes);
     ASSERT(Check());
     return NULL;
   }
@@ -235,6 +236,22 @@ Span* PageHeap::Split(Span* span, Length n) {
   return leftover;
 }
 
+void PageHeap::CommitSpan(Span* span) {
+  TCMalloc_SystemCommit(reinterpret_cast<void*>(span->start << kPageShift),
+                        static_cast<size_t>(span->length << kPageShift));
+  stats_.committed_bytes += span->length << kPageShift;
+}
+
+bool PageHeap::DecommitSpan(Span* span) {
+  bool rv = TCMalloc_SystemRelease(reinterpret_cast<void*>(span->start << kPageShift),
+                                   static_cast<size_t>(span->length << kPageShift));
+  if (rv) {
+    stats_.committed_bytes -= span->length << kPageShift;
+  }
+
+  return rv;
+}
+
 Span* PageHeap::Carve(Span* span, Length n) {
   ASSERT(n > 0);
   ASSERT(span->location != Span::IN_USE);
@@ -250,11 +267,29 @@ Span* PageHeap::Carve(Span* span, Length n) {
     leftover->location = old_location;
     Event(leftover, 'S', extra);
     RecordSpan(leftover);
+
+    // The previous span of |leftover| was just splitted -- no need to
+    // coalesce them. The next span of |leftover| was not previously coalesced
+    // with |span|, i.e. is NULL or has got location other than |old_location|.
+    const PageID p = leftover->start;
+    const Length len = leftover->length;
+    Span* next = GetDescriptor(p+len);
+    ASSERT (next == NULL ||
+            next->location == Span::IN_USE ||
+            next->location != leftover->location);
+
     PrependToFreeList(leftover);  // Skip coalescing - no candidates possible
     span->length = n;
     pagemap_.set(span->start + n - 1, span);
   }
   ASSERT(Check());
+  if (old_location == Span::ON_RETURNED_FREELIST) {
+    // We need to recommit this address space.
+    CommitSpan(span);
+  }
+  ASSERT(span->location == Span::IN_USE);
+  ASSERT(span->length == n);
+  ASSERT(stats_.unmapped_bytes+ stats_.committed_bytes==stats_.system_bytes);
   return span;
 }
 
@@ -271,6 +306,7 @@ void PageHeap::Delete(Span* span) {
   Event(span, 'D', span->length);
   MergeIntoFreeList(span);  // Coalesces if possible
   IncrementalScavenge(n);
+  ASSERT(stats_.unmapped_bytes+ stats_.committed_bytes==stats_.system_bytes);
   ASSERT(Check());
 }
 
@@ -284,6 +320,7 @@ void PageHeap::MergeIntoFreeList(Span* span) {
   //
   // Note that only similar spans are merged together.  For example,
   // we do not coalesce "returned" spans with "normal" spans.
+
   const PageID p = span->start;
   const Length n = span->length;
   Span* prev = GetDescriptor(p-1);
@@ -370,8 +407,7 @@ Length PageHeap::ReleaseLastNormalSpan(SpanList* slist) {
   Span* s = slist->normal.prev;
   ASSERT(s->location == Span::ON_NORMAL_FREELIST);
 
-  if (TCMalloc_SystemRelease(reinterpret_cast<void*>(s->start << kPageShift),
-                         static_cast<size_t>(s->length << kPageShift))) {
+  if (DecommitSpan(s)) {
     RemoveFromFreeList(s);
     const Length n = s->length;
     s->location = Span::ON_RETURNED_FREELIST;
@@ -525,6 +561,7 @@ bool PageHeap::GrowHeap(Length n) {
 
   uint64_t old_system_bytes = stats_.system_bytes;
   stats_.system_bytes += (ask << kPageShift);
+  stats_.committed_bytes += (ask << kPageShift);
   const PageID p = reinterpret_cast<uintptr_t>(ptr) >> kPageShift;
   ASSERT(p > 0);
 
@@ -546,6 +583,7 @@ bool PageHeap::GrowHeap(Length n) {
     Span* span = NewSpan(p, ask);
     RecordSpan(span);
     Delete(span);
+    ASSERT(stats_.unmapped_bytes+ stats_.committed_bytes==stats_.system_bytes);
     ASSERT(Check());
     return true;
   } else {
diff --git a/src/page_heap.h b/src/page_heap.h
index 1fde70c..a4f3d66 100644
--- a/src/page_heap.h
+++ b/src/page_heap.h
@@ -143,10 +143,12 @@ class PERFTOOLS_DLL_DECL PageHeap {
 
   // Page heap statistics
   struct Stats {
-    Stats() : system_bytes(0), free_bytes(0), unmapped_bytes(0) {}
+    Stats() : system_bytes(0), free_bytes(0), unmapped_bytes(0), committed_bytes(0) {}
     uint64_t system_bytes;    // Total bytes allocated from system
     uint64_t free_bytes;      // Total bytes on normal freelists
     uint64_t unmapped_bytes;  // Total bytes on returned freelists
+    uint64_t committed_bytes;  // Bytes committed, always <= system_bytes_.
+
   };
   inline Stats stats() const { return stats_; }
 
@@ -264,6 +266,12 @@ class PERFTOOLS_DLL_DECL PageHeap {
   // appropriate free list, and adjust stats.
   void MergeIntoFreeList(Span* span);
 
+  // Commit the span.
+  void CommitSpan(Span* span);
+
+  // Decommit the span.
+  bool DecommitSpan(Span* span);
+
   // Prepends span to appropriate free list, and adjusts stats.
   void PrependToFreeList(Span* span);
 
diff --git a/src/system-alloc.cc b/src/system-alloc.cc
index 0cbed80..e61c087 100755
--- a/src/system-alloc.cc
+++ b/src/system-alloc.cc
@@ -544,3 +544,9 @@ bool TCMalloc_SystemRelease(void* start, size_t length) {
 #endif
   return false;
 }
+
+void TCMalloc_SystemCommit(void* start, size_t length) {
+  // Nothing to do here.  TCMalloc_SystemRelease does not alter pages
+  // such that they need to be re-committed before they can be used by the
+  // application.
+}
diff --git a/src/system-alloc.h b/src/system-alloc.h
index 9783e4f..8233f96 100644
--- a/src/system-alloc.h
+++ b/src/system-alloc.h
@@ -76,6 +76,13 @@ void* TCMalloc_SystemAlloc(size_t bytes, size_t *actual_bytes,
 extern PERFTOOLS_DLL_DECL
 bool TCMalloc_SystemRelease(void* start, size_t length);
 
+// Called to ressurect memory which has been previously released
+// to the system via TCMalloc_SystemRelease.  An attempt to
+// commit a page that is already committed does not cause this
+// function to fail.
+extern PERFTOOLS_DLL_DECL
+void TCMalloc_SystemCommit(void* start, size_t length);
+
 // The current system allocator.
 extern PERFTOOLS_DLL_DECL SysAllocator* sys_alloc;
 
diff --git a/src/windows/system-alloc.cc b/src/windows/system-alloc.cc
index 91bc3e8..4682489 100644
--- a/src/windows/system-alloc.cc
+++ b/src/windows/system-alloc.cc
@@ -66,31 +66,31 @@ void* VirtualSysAllocator::Alloc(size_t size, size_t *actual_size,
   if (alignment < pagesize) alignment = pagesize;
   size = ((size + alignment - 1) / alignment) * alignment;
 
-  // Safest is to make actual_size same as input-size.
+  // Report the total number of bytes the OS actually delivered.  This might be
+  // greater than |size| because of alignment concerns.  The full size is
+  // necessary so that adjacent spans can be coalesced.
+  // TODO(antonm): proper processing of alignments
+  // in actual_size and decommitting.
   if (actual_size) {
     *actual_size = size;
   }
 
-  // Ask for extra memory if alignment > pagesize
-  size_t extra = 0;
-  if (alignment > pagesize) {
-    extra = alignment - pagesize;
-  }
+  // We currently do not support alignments larger than the pagesize or
+  // alignments that are not multiples of the pagesize after being floored.
+  // If this ability is needed it can be done by the caller (assuming it knows
+  // the page size).
+  assert(alignment <= pagesize);
 
-  void* result = VirtualAlloc(0, size + extra,
+  void* result = VirtualAlloc(0, size,
                               MEM_COMMIT|MEM_RESERVE, PAGE_READWRITE);
   if (result == NULL)
     return NULL;
 
-  // Adjust the return memory so it is aligned
-  uintptr_t ptr = reinterpret_cast<uintptr_t>(result);
-  size_t adjust = 0;
-  if ((ptr & (alignment - 1)) != 0) {
-    adjust = alignment - (ptr & (alignment - 1));
-  }
+  // If the result is not aligned memory fragmentation will result which can
+  // lead to pathological memory use.
+  assert((reinterpret_cast<uintptr_t>(result) & (alignment - 1)) == 0);
 
-  ptr += adjust;
-  return reinterpret_cast<void*>(ptr);
+  return result;
 }
 
 #ifdef _MSC_VER
@@ -146,8 +146,52 @@ void* TCMalloc_SystemAlloc(size_t size, size_t *actual_size,
 
 extern PERFTOOLS_DLL_DECL
 bool TCMalloc_SystemRelease(void* start, size_t length) {
-  // TODO(csilvers): should I be calling VirtualFree here?
-  return false;
+  if (VirtualFree(start, length, MEM_DECOMMIT))
+    return true;
+
+  // The decommit may fail if the memory region consists of allocations
+  // from more than one call to VirtualAlloc.  In this case, fall back to
+  // using VirtualQuery to retrieve the allocation boundaries and decommit
+  // them each individually.
+
+  char* ptr = static_cast<char*>(start);
+  char* end = ptr + length;
+  MEMORY_BASIC_INFORMATION info;
+  while (ptr < end) {
+    size_t resultSize = VirtualQuery(ptr, &info, sizeof(info));
+    assert(resultSize == sizeof(info));
+    size_t decommitSize = std::min<size_t>(info.RegionSize, end - ptr);
+    BOOL success = VirtualFree(ptr, decommitSize, MEM_DECOMMIT);
+    assert(success == TRUE);
+    ptr += decommitSize;
+  }
+
+  return true;
+}
+
+extern PERFTOOLS_DLL_DECL
+void TCMalloc_SystemCommit(void* start, size_t length) {
+  if (VirtualAlloc(start, length, MEM_COMMIT, PAGE_READWRITE) == start)
+    return;
+
+  // The commit may fail if the memory region consists of allocations
+  // from more than one call to VirtualAlloc.  In this case, fall back to
+  // using VirtualQuery to retrieve the allocation boundaries and commit them
+  // each individually.
+
+  char* ptr = static_cast<char*>(start);
+  char* end = ptr + length;
+  MEMORY_BASIC_INFORMATION info;
+  while (ptr < end) {
+    size_t resultSize = VirtualQuery(ptr, &info, sizeof(info));
+    assert(resultSize == sizeof(info));
+
+    size_t commitSize = std::min<size_t>(info.RegionSize, end - ptr);
+    void* newAddress = VirtualAlloc(ptr, commitSize, MEM_COMMIT,
+                                    PAGE_READWRITE);
+    assert(newAddress == ptr);
+    ptr += commitSize;
+  }
 }
 
 bool RegisterSystemAllocator(SysAllocator *allocator, int priority) {