[NOT TO COMMIT!] Replace third_party/tcmalloc/chromium with tcmalloc r136 (the latest).

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 82 matching lines @@
 Span* PageHeap::New(Length n) {
   ASSERT(Check());
   ASSERT(n > 0);
 
   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 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;
@@ skipping 40 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));
-  stats_.committed_bytes += span->length << kPageShift;
-}
-
-void PageHeap::DecommitSpan(Span* span) {
-  TCMalloc_SystemRelease(reinterpret_cast<void*>(span->start << kPageShift),
-                         static_cast<size_t>(span->length << kPageShift));
-  stats_.committed_bytes -= span->length << kPageShift;
-}
-
 Span* PageHeap::Carve(Span* span, Length n) {
   ASSERT(n > 0);
   ASSERT(span->location != Span::IN_USE);
   const int old_location = span->location;
   RemoveFromFreeList(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);
-
-    // 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;
 }
 
 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);
   const Length n = span->length;
   span->sizeclass = 0;
   span->sample = 0;
   span->location = Span::ON_NORMAL_FREELIST;
   Event(span, 'D', span->length);
   MergeIntoFreeList(span);  // Coalesces if possible
   IncrementalScavenge(n);
-  ASSERT(stats_.unmapped_bytes+ stats_.committed_bytes==stats_.system_bytes);
   ASSERT(Check());
 }
 
 void PageHeap::MergeIntoFreeList(Span* span) {
   ASSERT(span->location != Span::IN_USE);
 
   // 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 adjacent spans we merge into "span" may come out of a
-  // "normal" (committed) list, and cleanly merge with our IN_USE span, which
-  // is implicitly committed.  If the adjacents spans are on the "returned"
-  // (decommitted) list, then we must get both spans into the same state before
-  // or after we coalesce them.  The current code always decomits. This is
-  // achieved by blindly decommitting the entire coalesced region, which  may
-  // include any combination of committed and decommitted spans, at the end of
-  // the method.
-
-  // TODO(jar): "Always decommit" causes some extra calls to commit when we are
-  // called in GrowHeap() during an allocation :-/.  We need to eval the cost of
-  // that oscillation, and possibly do something to reduce it.
-
-  // TODO(jar): We need a better strategy for deciding to commit, or decommit,
-  // based on memory usage and free heap sizes.
-
+  // 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);
-  if (prev != NULL && prev->location != Span::IN_USE) {
+  if (prev != NULL && prev->location == span->location) {
     // Merge preceding span into this span
     ASSERT(prev->start + prev->length == p);
     const Length len = prev->length;
-    if (prev->location == Span::ON_RETURNED_FREELIST) {
-      // We're about to put the merge span into the returned freelist and call
-      // DecommitSpan() on it, which will mark the entire span including this
-      // one as released and decrease stats_.committed_bytes by the size of the
-      // merged span.  To make the math work out we temporarily increase the
-      // stats_.committed_bytes amount.
-      stats_.committed_bytes += prev->length << kPageShift;
-    }
     RemoveFromFreeList(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) {
+  if (next != NULL && next->location == span->location) {
     // Merge next span into this span
     ASSERT(next->start == p+n);
     const Length len = next->length;
-    if (next->location == Span::ON_RETURNED_FREELIST) {
-      // See the comment below 'if (prev->location ...' for explanation.
-      stats_.committed_bytes += next->length << kPageShift;
-    }
     RemoveFromFreeList(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;
-  DecommitSpan(span);
   PrependToFreeList(span);
 }
 
 void PageHeap::PrependToFreeList(Span* span) {
   ASSERT(span->location != Span::IN_USE);
   SpanList* list = (span->length < kMaxPages) ? &free_[span->length] : &large_;
   if (span->location == Span::ON_NORMAL_FREELIST) {
     stats_.free_bytes += (span->length << kPageShift);
     DLL_Prepend(&list->normal, span);
   } else {
@@ skipping 87 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 MiB(uint64_t bytes) {
-  return bytes / 1048576.0;
-}
-
-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) {
-
+void PageHeap::GetSmallSpanStats(SmallSpanStats* result) {
   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;
-    }
+    result->normal_length[s] = DLL_Length(&free_[s].normal);
+    result->returned_length[s] = DLL_Length(&free_[s].returned);
   }
 }
 
-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++;
-    }
+void PageHeap::GetLargeSpanStats(LargeSpanStats* result) {
+  result->spans = 0;
+  result->normal_pages = 0;
+  result->returned_pages = 0;
+  for (Span* s = large_.normal.next; s != &large_.normal; s = s->next) {
+    result->normal_pages += s->length;;
+    result->spans++;
   }
-  out->printf("------------------------------------------------\n");
-  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 MiB; %6.1f MiB cum"
-                  "; unmapped: %6.1f MiB; %6.1f MiB cum\n",
-                  s,
-                  (n_length + r_length),
-                  PagesToMiB(n_pages + r_pages),
-                  PagesToMiB(total_normal + total_returned),
-                  PagesToMiB(r_pages),
-                  PagesToMiB(total_returned));
-    }
+  for (Span* s = large_.returned.next; s != &large_.returned; s = s->next) {
+    result->returned_pages += s->length;
+    result->spans++;
   }
-
-  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 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 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 MiB; %6.1f MiB cum"
-              "; unmapped: %6.1f MiB; %6.1f MiB cum\n",
-              (n_spans + r_spans),
-              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 40 matching lines @@
       ask = n;
       ptr = TCMalloc_SystemAlloc(ask << kPageShift, &actual_size, kPageSize);
     }
     if (ptr == NULL) return false;
   }
   ask = actual_size >> kPageShift;
   RecordGrowth(ask << kPageShift);
 
   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);
 
   // 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.
 
   if (old_system_bytes < kPageMapBigAllocationThreshold
       && stats_.system_bytes >= kPageMapBigAllocationThreshold) {
     pagemap_.PreallocateMoreMemory();
   }
 
   // Make sure pagemap_ has entries for all of the new pages.
   // Plus ensure one before and one after so coalescing code
   // does not need bounds-checking.
   if (pagemap_.Ensure(p-1, ask+2)) {
     // Pretend the new area is allocated and then Delete() it to cause
     // any necessary coalescing to occur.
     Span* span = NewSpan(p, ask);
     RecordSpan(span);
     Delete(span);
-    ASSERT(stats_.unmapped_bytes+ stats_.committed_bytes==stats_.system_bytes);
     ASSERT(Check());
     return true;
   } else {
     // We could not allocate memory within "pagemap_"
     // TODO: Once we can return memory to the system, return the new span
     return false;
   }
 }
 
 bool PageHeap::Check() {
@@ skipping 19 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