Landing for Anton Muhin's tcmalloc patch:...

third_party/tcmalloc/page_heap.cc

 // Copyright (c) 2008, Google Inc.
 // All rights reserved.
 //
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 // notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
@@ skipping 33 matching lines @@
               "to return memory slower.  Reasonable rates are in the "
               "range [0,10]");
 
 namespace tcmalloc {
 
 PageHeap::PageHeap()
     : pagemap_(MetaDataAlloc),
       pagemap_cache_(0),
       free_pages_(0),
       system_bytes_(0),
+#if DEFER_DECOMMIT
+      free_committed_pages_(0),
+      pages_committed_since_last_scavenge_(0),
+#else
       scavenge_counter_(0),
+#endif
       // Start scavenging at kMaxPages list
       scavenge_index_(kMaxPages-1) {
   COMPILE_ASSERT(kNumClasses <= (1 << PageMapCache::kValuebits), valuebits);
   DLL_Init(&large_.normal);
   DLL_Init(&large_.returned);
   for (int i = 0; i < kMaxPages; i++) {
     DLL_Init(&free_[i].normal);
     DLL_Init(&free_[i].returned);
   }
 }
@@ skipping 78 matching lines @@
   Span* leftover = NewSpan(span->start + n, extra);
   ASSERT(leftover->location == Span::IN_USE);
   Event(leftover, 'U', extra);
   RecordSpan(leftover);
   pagemap_.set(span->start + n - 1, span); // Update map from pageid to 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)
+  );
+#if DEFER_DECOMMIT
+  pages_committed_since_last_scavenge_ += span->length;
+#endif
+}
+
 Span* PageHeap::Carve(Span* span, Length n) {
   ASSERT(n > 0);
   ASSERT(span->location != Span::IN_USE);
   const int old_location = span->location;
   DLL_Remove(span);
   span->location = Span::IN_USE;
   Event(span, 'A', n);
 
   const int extra = span->length - n;
   ASSERT(extra >= 0);
   if (extra > 0) {
     Span* leftover = NewSpan(span->start + n, extra);
     leftover->location = old_location;
     Event(leftover, 'S', extra);
     RecordSpan(leftover);
 
     // Place leftover span on appropriate free list
     SpanList* listpair = (extra < kMaxPages) ? &free_[extra] : &large_;
     Span* dst = (leftover->location == Span::ON_RETURNED_FREELIST
                  ? &listpair->returned : &listpair->normal);
     DLL_Prepend(dst, leftover);
 
     span->length = n;
     pagemap_.set(span->start + n - 1, span);
   }
+  if (old_location == Span::ON_RETURNED_FREELIST) {
+    // We need to recommit this address space.
+    CommitSpan(span);
+  } else {
+#if DEFER_DECOMMIT
+    // The newly allocated memory is from a span that's already committed.
+    // Update the free_committed_pages_ count.
+    ASSERT(free_committed_pages_ >= n);
+    free_committed_pages_ -= n;
+#endif
+  }
+  ASSERT(span->location == Span::IN_USE);
+  ASSERT(span->length == n);
   ASSERT(Check());
   free_pages_ -= n;
-  if (old_location == Span::ON_RETURNED_FREELIST) {
-    // We need to recommit this address space.
-    TCMalloc_SystemCommit(
-        reinterpret_cast<void*>(span->start << kPageShift),
-        static_cast<size_t>(span->length << kPageShift));
-  }
   return span;
 }
 
 void PageHeap::Delete(Span* span) {
   ASSERT(Check());
   ASSERT(span->location == Span::IN_USE);
   ASSERT(span->length > 0);
   ASSERT(GetDescriptor(span->start) == span);
   ASSERT(GetDescriptor(span->start + span->length - 1) == span);
   span->sizeclass = 0;
   span->sample = 0;
 
   // Coalesce -- we guarantee that "p" != 0, so no bounds checking
   // necessary.  We do not bother resetting the stale pagemap
   // entries for the pieces we are merging together because we only
   // care about the pagemap entries for the boundaries.
   //
   // Note that the spans we merge into "span" may come out of
-  // a "normal" list.  For simplicity, we move these into the
-  // "returned" list of the appropriate size class.  We do this
-  // so that we can maximize large, continuous blocks of freed
-  // space.
+  // a "returned" list.  We move those into "normal" list
+  // as for 'immediate' operations we favour committing over
+  // decommitting (decommitting is performed offline).
   const PageID p = span->start;
   const Length n = span->length;
   Span* prev = GetDescriptor(p-1);
   if (prev != NULL && prev->location != Span::IN_USE) {
     // Merge preceding span into this span
     ASSERT(prev->start + prev->length == p);
     const Length len = prev->length;
+    if (prev->location == Span::ON_RETURNED_FREELIST) {
+      CommitSpan(prev);
+#if DEFER_DECOMMIT
+      free_committed_pages_ += len;
+#endif
+    }
     DLL_Remove(prev);
     DeleteSpan(prev);
     span->start -= len;
     span->length += len;
     pagemap_.set(span->start, span);
     Event(span, 'L', len);
   }
   Span* next = GetDescriptor(p+n);
   if (next != NULL && next->location != Span::IN_USE) {
     // Merge next span into this span
     ASSERT(next->start == p+n);
     const Length len = next->length;
+    if (next->location == Span::ON_RETURNED_FREELIST) {
+      CommitSpan(next);
+#if DEFER_DECOMMIT
+      free_committed_pages_ += len;
+#endif
+    }
     DLL_Remove(next);
     DeleteSpan(next);
     span->length += len;
     pagemap_.set(span->start + span->length - 1, span);
     Event(span, 'R', len);
   }
 
   Event(span, 'D', span->length);
-  span->location = Span::ON_RETURNED_FREELIST;
-  TCMalloc_SystemRelease(reinterpret_cast<void*>(span->start << kPageShift),
-                         static_cast<size_t>(span->length << kPageShift));
+  span->location = Span::ON_NORMAL_FREELIST;
   if (span->length < kMaxPages)
-    DLL_Prepend(&free_[span->length].returned, span);
+    DLL_Prepend(&free_[span->length].normal, span);
   else
-    DLL_Prepend(&large_.returned, span);
+    DLL_Prepend(&large_.normal, span);
   free_pages_ += n;
+#if DEFER_DECOMMIT
+  free_committed_pages_ += n;
+#endif
 
+#if DEFER_DECOMMIT
+  // TODO(antonm): notify that could start scavenging
+#else
   IncrementalScavenge(n);
+#endif
   ASSERT(Check());
 }
 
+
+void PageHeap::Scavenge() {
+#if DEFER_DECOMMIT
+  // If we have to commit memory since the last scavenge, it means we don't
+  // have enough free committed pages of necessary size for the amount of
+  // allocations that we do.  So hold off on releasing memory back to the system.
+  if (pages_committed_since_last_scavenge_ > 0) {
+    pages_committed_since_last_scavenge_ = 0;
+    return;
+  }
+
+  if (free_committed_pages_ <= kMinimumFreeCommittedPageCount) {
+    return;
+  }
+
+  uint64_t to_decommit = std::min(
+      free_committed_pages_ - kMinimumFreeCommittedPageCount,
+      free_committed_pages_ / kMaxScavengeAmountFactor);
+  to_decommit = DecommitFromSpanList(&large_, to_decommit);
+  for (int i = kMaxPages - 1; i >= 0; i--) {
+    to_decommit = DecommitFromSpanList(&free_[i], to_decommit);
+  }
+
+  // Force at least one decommit from large list, otherwise big sized blocks
+  // sitting might block as from releasing smaller blocks behind.
+  if (to_decommit > 0) {
+    if (!DLL_IsEmpty(&large_.normal)) {
+      DecommitLastSpan(&large_, large_.normal.prev);
+    }
+  }
+#endif
+}
+
+#if DEFER_DECOMMIT
+Length PageHeap::DecommitLastSpan(SpanList* span_list, Span* span) {
+  ASSERT(!DLL_IsEmpty(&span_list->normal));
+  ASSERT(span_list->normal.prev == span);
+
+  Length length = span->length;
+
+  DLL_Remove(span);
+
+  TCMalloc_SystemRelease(reinterpret_cast<void*>(span->start << kPageShift), span->length << kPageShift);
+  span->location = Span::ON_RETURNED_FREELIST;
+  ASSERT(free_committed_pages_ >= length);
+  free_committed_pages_ -= length;
+
+  DLL_Prepend(&span_list->returned, span);
+
+  return length;
+}
+
+uint64_t PageHeap::DecommitFromSpanList(SpanList* span_list, uint64_t to_decommit) {
+  while (!DLL_IsEmpty(&span_list->normal)) {
+    // Release the last span on the normal portion of this list.
+    Span* span = span_list->normal.prev;
+
+    if (span->length > to_decommit) {
+      return to_decommit;
+    }
+
+    to_decommit -= DecommitLastSpan(span_list, span);
+  }
+
+  return to_decommit;
+}
+
+#else
+
 void PageHeap::IncrementalScavenge(Length n) {
   // Fast path; not yet time to release memory
   scavenge_counter_ -= n;
   if (scavenge_counter_ >= 0) return;  // Not yet time to scavenge
 
   // Never delay scavenging for more than the following number of
   // deallocated pages.  With 4K pages, this comes to 4GB of
   // deallocation.
   // Chrome:  Changed to 64MB
   static const int kMaxReleaseDelay = 1 << 14;
@@ skipping 39 matching lines @@
       scavenge_index_ = index;  // Scavenge at index+1 next time
       // Note: we stop scavenging after finding one.
       return;
     }
     index++;
   }
 
   // Nothing to scavenge, delay for a while
   scavenge_counter_ = kDefaultReleaseDelay;
 }
+#endif
 
 void PageHeap::RegisterSizeClass(Span* span, size_t sc) {
   // Associate span object with all interior pages as well
   ASSERT(span->location == Span::IN_USE);
   ASSERT(GetDescriptor(span->start) == span);
   ASSERT(GetDescriptor(span->start+span->length-1) == span);
   Event(span, 'C', sc);
   span->sizeclass = sc;
   for (Length i = 1; i < span->length-1; i++) {
     pagemap_.set(span->start+i, span);
@@ skipping 81 matching lines @@
   void* ptr = TCMalloc_SystemAlloc(ask << kPageShift, &actual_size, kPageSize);
   if (ptr == NULL) {
     if (n < ask) {
       // Try growing just "n" pages
       ask = n;
       ptr = TCMalloc_SystemAlloc(ask << kPageShift, &actual_size, kPageSize);
     }
     if (ptr == NULL) return false;
   }
   ask = actual_size >> kPageShift;
+#if DEFER_DECOMMIT
+  pages_committed_since_last_scavenge_ += ask;
+#endif
   RecordGrowth(ask << kPageShift);
 
   uint64_t old_system_bytes = system_bytes_;
   system_bytes_ += (ask << kPageShift);
   const PageID p = reinterpret_cast<uintptr_t>(ptr) >> kPageShift;
   ASSERT(p > 0);
 
   // If we have already a lot of pages allocated, just pre allocate a bunch of
   // memory for the page map. This prevents fragmentation by pagemap metadata
   // when a program keeps allocating and freeing large blocks.
@@ skipping 65 matching lines @@
                            static_cast<size_t>(s->length << kPageShift));
   }
 }
 
 void PageHeap::ReleaseFreePages() {
   for (Length s = 0; s < kMaxPages; s++) {
     ReleaseFreeList(&free_[s].normal, &free_[s].returned);
   }
   ReleaseFreeList(&large_.normal, &large_.returned);
   ASSERT(Check());
+#if DEFER_DECOMMIT
+  free_committed_pages_ = 0;
+#endif
 }
 
 }  // namespace tcmalloc