Merge google-perftools r109 (the current contents of third_party/tcmalloc/vendor)

third_party/tcmalloc/chromium/src/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 13 matching lines @@
 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 
 // ---
 // Author: Sanjay Ghemawat <opensource@google.com>
 
 #include <config.h>
-#include "page_heap.h"
-
-#include "static_vars.h"
-#include "system-alloc.h"
+#ifdef HAVE_INTTYPES_H
+#include <inttypes.h>                   // for PRIuPTR
+#endif
+#include <google/malloc_extension.h>      // for MallocRange, etc
+#include "base/basictypes.h"
+#include "base/commandlineflags.h"
+#include "internal_logging.h"  // for ASSERT, TCMalloc_Printer, etc
+#include "page_heap_allocator.h"  // for PageHeapAllocator
+#include "static_vars.h"       // for Static
+#include "system-alloc.h"      // for TCMalloc_SystemAlloc, etc
 
 DEFINE_double(tcmalloc_release_rate,
               EnvToDouble("TCMALLOC_RELEASE_RATE", 1.0),
               "Rate at which we release unused memory to the system.  "
               "Zero means we never release memory back to the system.  "
               "Increase this flag to return memory faster; decrease it "
               "to return memory slower.  Reasonable rates are in the "
               "range [0,10]");
 
 namespace tcmalloc {
 
 PageHeap::PageHeap()
     : pagemap_(MetaDataAlloc),
       pagemap_cache_(0),
       scavenge_counter_(0),
       // Start scavenging at kMaxPages list
       release_index_(kMaxPages) {
   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);
   }
 }
 
-Span* PageHeap::New(Length n) {
+Span* PageHeap::SearchFreeAndLargeLists(Length n) {
   ASSERT(Check());
   ASSERT(n > 0);
 
   // Find first size >= n that has a non-empty list
   for (Length s = n; s < kMaxPages; s++) {
     Span* ll = &free_[s].normal;
     // If we're lucky, ll is non-empty, meaning it has a suitable span.
     if (!DLL_IsEmpty(ll)) {
       ASSERT(ll->next->location == Span::ON_NORMAL_FREELIST);
       return Carve(ll->next, n);
     }
     // Alternatively, maybe there's a usable returned span.
     ll = &free_[s].returned;
     if (!DLL_IsEmpty(ll)) {
       ASSERT(ll->next->location == Span::ON_RETURNED_FREELIST);
       return Carve(ll->next, n);
     }
-    // Still no luck, so keep looking in larger classes.
   }
+  // No luck in free lists, our last chance is in a larger class.
+  return AllocLarge(n);  // May be NULL
+}
 
-  Span* result = AllocLarge(n);
-  if (result != NULL) return result;
+Span* PageHeap::New(Length n) {
+  ASSERT(Check());
+  ASSERT(n > 0);
 
-  // Grow the heap and try again
+  Span* result = SearchFreeAndLargeLists(n);
+  if (result != NULL)
+    return result;
+
+  // Grow the heap and try again.
   if (!GrowHeap(n)) {
     ASSERT(stats_.unmapped_bytes+ stats_.committed_bytes==stats_.system_bytes);
     ASSERT(Check());
     return NULL;
   }
-
-  return AllocLarge(n);
+  return SearchFreeAndLargeLists(n);
 }
 
 Span* PageHeap::AllocLarge(Length n) {
   // find the best span (closest to n in size).
   // The following loops implements address-ordered best-fit.
   Span *best = NULL;
 
   // Search through normal list
   for (Span* span = large_.normal.next;
        span != &large_.normal;
@@ skipping 278 matching lines @@
   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);
   }
 }
 
-static double MB(uint64_t bytes) {
+static double MiB(uint64_t bytes) {
   return bytes / 1048576.0;
 }
 
-static double PagesToMB(uint64_t pages) {
+static double PagesToMiB(uint64_t pages) {
   return (pages << kPageShift) / 1048576.0;
 }
 
+void PageHeap::GetClassSizes(int64 class_sizes_normal[kMaxPages],
+                             int64 class_sizes_returned[kMaxPages],
+                             int64* normal_pages_in_spans,
+                             int64* returned_pages_in_spans) {
+
+  for (int s = 0; s < kMaxPages; s++) {
+    if (class_sizes_normal != NULL) {
+      class_sizes_normal[s] = DLL_Length(&free_[s].normal);
+    }
+    if (class_sizes_returned != NULL) {
+      class_sizes_returned[s] = DLL_Length(&free_[s].returned);
+    }
+  }
+
+  if (normal_pages_in_spans != NULL) {
+    *normal_pages_in_spans = 0;
+    for (Span* s = large_.normal.next; s != &large_.normal; s = s->next) {
+      *normal_pages_in_spans += s->length;;
+    }
+  }
+
+  if (returned_pages_in_spans != NULL) {
+    *returned_pages_in_spans = 0;
+    for (Span* s = large_.returned.next; s != &large_.returned; s = s->next) {
+      *returned_pages_in_spans += s->length;
+    }
+  }
+}
+
 void PageHeap::Dump(TCMalloc_Printer* out) {
   int nonempty_sizes = 0;
   for (int s = 0; s < kMaxPages; s++) {
     if (!DLL_IsEmpty(&free_[s].normal) || !DLL_IsEmpty(&free_[s].returned)) {
       nonempty_sizes++;
     }
   }
   out->printf("------------------------------------------------\n");
-  out->printf("PageHeap: %d sizes; %6.1f MB free; %6.1f MB unmapped\n",
-              nonempty_sizes, MB(stats_.free_bytes), MB(stats_.unmapped_bytes));
+  out->printf("PageHeap: %d sizes; %6.1f MiB free; %6.1f MiB unmapped\n",
+              nonempty_sizes, MiB(stats_.free_bytes),
+              MiB(stats_.unmapped_bytes));
   out->printf("------------------------------------------------\n");
   uint64_t total_normal = 0;
   uint64_t total_returned = 0;
   for (int s = 0; s < kMaxPages; s++) {
     const int n_length = DLL_Length(&free_[s].normal);
     const int r_length = DLL_Length(&free_[s].returned);
     if (n_length + r_length > 0) {
       uint64_t n_pages = s * n_length;
       uint64_t r_pages = s * r_length;
       total_normal += n_pages;
       total_returned += r_pages;
-      out->printf("%6u pages * %6u spans ~ %6.1f MB; %6.1f MB cum"
-                  "; unmapped: %6.1f MB; %6.1f MB cum\n",
+      out->printf("%6u pages * %6u spans ~ %6.1f MiB; %6.1f MiB cum"
+                  "; unmapped: %6.1f MiB; %6.1f MiB cum\n",
                   s,
                   (n_length + r_length),
-                  PagesToMB(n_pages + r_pages),
-                  PagesToMB(total_normal + total_returned),
-                  PagesToMB(r_pages),
-                  PagesToMB(total_returned));
+                  PagesToMiB(n_pages + r_pages),
+                  PagesToMiB(total_normal + total_returned),
+                  PagesToMiB(r_pages),
+                  PagesToMiB(total_returned));
     }
   }
 
   uint64_t n_pages = 0;
   uint64_t r_pages = 0;
   int n_spans = 0;
   int r_spans = 0;
   out->printf("Normal large spans:\n");
   for (Span* s = large_.normal.next; s != &large_.normal; s = s->next) {
-    out->printf("   [ %6" PRIuPTR " pages ] %6.1f MB\n",
-                s->length, PagesToMB(s->length));
+    out->printf("   [ %6" PRIuPTR " pages ] %6.1f MiB\n",
+                s->length, PagesToMiB(s->length));
     n_pages += s->length;
     n_spans++;
   }
   out->printf("Unmapped large spans:\n");
   for (Span* s = large_.returned.next; s != &large_.returned; s = s->next) {
-    out->printf("   [ %6" PRIuPTR " pages ] %6.1f MB\n",
-                s->length, PagesToMB(s->length));
+    out->printf("   [ %6" PRIuPTR " pages ] %6.1f MiB\n",
+                s->length, PagesToMiB(s->length));
     r_pages += s->length;
     r_spans++;
   }
   total_normal += n_pages;
   total_returned += r_pages;
-  out->printf(">255   large * %6u spans ~ %6.1f MB; %6.1f MB cum"
-              "; unmapped: %6.1f MB; %6.1f MB cum\n",
+  out->printf(">255   large * %6u spans ~ %6.1f MiB; %6.1f MiB cum"
+              "; unmapped: %6.1f MiB; %6.1f MiB cum\n",
               (n_spans + r_spans),
-              PagesToMB(n_pages + r_pages),
-              PagesToMB(total_normal + total_returned),
-              PagesToMB(r_pages),
-              PagesToMB(total_returned));
+              PagesToMiB(n_pages + r_pages),
+              PagesToMiB(total_normal + total_returned),
+              PagesToMiB(r_pages),
+              PagesToMiB(total_returned));
 }
 
 bool PageHeap::GetNextRange(PageID start, base::MallocRange* r) {
   Span* span = reinterpret_cast<Span*>(pagemap_.Next(start));
   if (span == NULL) {
     return false;
   }
   r->address = span->start << kPageShift;
   r->length = span->length << kPageShift;
   r->fraction = 0;
@@ skipping 102 matching lines @@
     CHECK_CONDITION(s->location == freelist);  // NORMAL or RETURNED
     CHECK_CONDITION(s->length >= min_pages);
     CHECK_CONDITION(s->length <= max_pages);
     CHECK_CONDITION(GetDescriptor(s->start) == s);
     CHECK_CONDITION(GetDescriptor(s->start+s->length-1) == s);
   }
   return true;
 }
 
 }  // namespace tcmalloc