diff options
author | csilvers <csilvers@6b5cf1ce-ec42-a296-1ba9-69fdba395a50> | 2008-06-14 02:30:53 +0000 |
---|---|---|
committer | csilvers <csilvers@6b5cf1ce-ec42-a296-1ba9-69fdba395a50> | 2008-06-14 02:30:53 +0000 |
commit | 100e657c5092bc274424286a728db5116a4bbc54 (patch) | |
tree | 3a688677e9366e218b25651d0a75567e8ecacf4f /src/tcmalloc.cc | |
parent | 7ec719093b1c9fda979ba0d07eed288e2a7c3c9b (diff) | |
download | gperftools-100e657c5092bc274424286a728db5116a4bbc54.tar.gz |
Mon Jun 9 16:47:03 2008 Google Inc. <opensource@google.com>
* google-perftools: version 0.98 release
* Add ProfilerStartWithOptions() (cgd)
* Change tcmalloc_minimal to not do any stack-tracing at all (csilvers)
* Prefer mmap to sbrk for 64-buit debug mode (sanjay)
* Fix accounting for some tcmalloc stats (sanjay)
* Use setrlimit() to keep unittests from killing the machine (odo)
* Fix a bug when sbrk-ing near address 4G (csilvers)
* Make MallocHook thread-safe (jyasskin)
* Fix windows build for MemoryBarrier (jyasskin)
* Fix CPU-profiler docs to mention correct libs (csilvers)
* Fix for GetHeapProfile() when heap-profiling is off (maxim)
* Avoid realloc resizing ping-pongs using hysteresis (csilvers)
* Add --callgrind output support to pprof (klimek)
* Fix profiler.h and heap-profiler.h to be C-compatible (csilvers)
* Break malloc_hook.h into two parts to reduce dependencies (csilvers)
* Better handle systems that don't implement mmap (csilvers)
* PORTING: disable system_alloc_unittest for msvc (csilvers)
* PORTING: Makefile tweaks to build better on cygwin (csilvers)
git-svn-id: http://gperftools.googlecode.com/svn/trunk@52 6b5cf1ce-ec42-a296-1ba9-69fdba395a50
Diffstat (limited to 'src/tcmalloc.cc')
-rw-r--r-- | src/tcmalloc.cc | 135 |
1 files changed, 81 insertions, 54 deletions
diff --git a/src/tcmalloc.cc b/src/tcmalloc.cc index 0b4e715..94287ba 100644 --- a/src/tcmalloc.cc +++ b/src/tcmalloc.cc @@ -64,6 +64,19 @@ // in Populate() for pages with sizeclass > 0 objects, and in do_malloc() and // do_memalign() for all other relevant pages. // +// PAGEMAP +// ------- +// Page map contains a mapping from page id to Span. +// +// If Span s occupies pages [p..q], +// pagemap[p] == s +// pagemap[q] == s +// pagemap[p+1..q-1] are undefined +// pagemap[p-1] and pagemap[q+1] are defined: +// NULL if the corresponding page is not yet in the address space. +// Otherwise it points to a Span. This span may be free +// or allocated. If free, it is in one of pageheap's freelist. +// // TODO: Bias reclamation to larger addresses // TODO: implement mallinfo/mallopt // TODO: Better testing @@ -101,6 +114,7 @@ #include "base/basictypes.h" // gets us PRIu64 #include "base/sysinfo.h" #include "base/spinlock.h" +#include "malloc_hook-inl.h" #include <google/malloc_hook.h> #include <google/malloc_extension.h> #include "internal_logging.h" @@ -216,7 +230,7 @@ static const size_t kMaxPages = kMinSystemAlloc; static unsigned int primes_list[] = { // Small values might cause high rates of sampling // and hence commented out. - // 2, 5, 11, 17, 37, 67, 131, 257, + // 2, 5, 11, 17, 37, 67, 131, 257, // 521, 1031, 2053, 4099, 8209, 16411, 32771, 65537, 131101, 262147, 524309, 1048583, 2097169, 4194319, 8388617, 16777259, 33554467 }; @@ -627,19 +641,6 @@ static inline Length pages(size_t bytes) { ((bytes & (kPageSize - 1)) > 0 ? 1 : 0); } -// Convert a user size into the number of bytes that will actually be -// allocated -static size_t AllocationSize(size_t bytes) { - if (bytes > kMaxSize) { - // Large object: we allocate an integral number of pages - ASSERT(bytes <= (kMaxValidPages << kPageShift)); - return pages(bytes) << kPageShift; - } else { - // Small object: find the size class to which it belongs - return ByteSizeForClass(SizeClass(bytes)); - } -} - // Information kept for a span (a contiguous run of pages). struct Span { PageID start; // Starting page number @@ -649,7 +650,7 @@ struct Span { void* objects; // Linked list of free objects unsigned int refcount : 16; // Number of non-free objects unsigned int sizeclass : 8; // Size-class for small objects (or 0) - unsigned int free : 1; // Is the span free + unsigned int location : 2; // Is the span on a freelist, and if so, which? unsigned int sample : 1; // Sampled object? #undef SPAN_HISTORY @@ -659,6 +660,9 @@ struct Span { char history[64]; int value[64]; #endif + + // What freelist the span is on: IN_USE if on none, or normal or returned + enum { IN_USE, ON_NORMAL_FREELIST, ON_RETURNED_FREELIST }; }; #ifdef SPAN_HISTORY @@ -818,7 +822,7 @@ class TCMalloc_PageHeap { // Returns a pointer to the second span. // // REQUIRES: "0 < n < span->length" - // REQUIRES: !span->free + // REQUIRES: span->location == IN_USE // REQUIRES: span->sizeclass == 0 Span* Split(Span* span, Length n); @@ -839,7 +843,8 @@ class TCMalloc_PageHeap { } bool Check(); - bool CheckList(Span* list, Length min_pages, Length max_pages); + bool CheckList(Span* list, Length min_pages, Length max_pages, + int freelist); // ON_NORMAL_FREELIST or ON_RETURNED_FREELIST // Release all pages on the free list for reuse by the OS: void ReleaseFreePages(); @@ -883,15 +888,14 @@ class TCMalloc_PageHeap { bool GrowHeap(Length n); - // REQUIRES span->length >= n + // REQUIRES: span->length >= n + // REQUIRES: span->location != IN_USE // Remove span from its free list, and move any leftover part of // span into appropriate free lists. Also update "span" to have // length exactly "n" and mark it as non-free so it can be returned // to the client. After all that, decrease free_pages_ by n and // return span. - // - // "released" is true iff "span" was found on a "returned" list. - Span* Carve(Span* span, Length n, bool released); + Span* Carve(Span* span, Length n); void RecordSpan(Span* span) { pagemap_.set(span->start, span); @@ -939,18 +943,18 @@ Span* TCMalloc_PageHeap::New(Length n) { // Find first size >= n that has a non-empty list for (Length s = n; s < kMaxPages; s++) { Span* ll = &free_[s].normal; - bool released = false; // If we're lucky, ll is non-empty, meaning it has a suitable span. - if (DLL_IsEmpty(ll)) { - // Alternatively, maybe there's a usable returned span. - ll = &free_[s].returned; - released = true; - if (DLL_IsEmpty(ll)) { - // Still no luck, so keep looking in larger classes. - continue; - } + 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); } - return Carve(ll->next, n, released); + // Still no luck, so keep looking in larger classes. } Span* result = AllocLarge(n); @@ -968,7 +972,6 @@ Span* TCMalloc_PageHeap::New(Length n) { Span* TCMalloc_PageHeap::AllocLarge(Length n) { // find the best span (closest to n in size). // The following loops implements address-ordered best-fit. - bool from_released = false; Span *best = NULL; // Search through normal list @@ -980,7 +983,7 @@ Span* TCMalloc_PageHeap::AllocLarge(Length n) { || (span->length < best->length) || ((span->length == best->length) && (span->start < best->start))) { best = span; - from_released = false; + ASSERT(best->location == Span::ON_NORMAL_FREELIST); } } } @@ -994,23 +997,24 @@ Span* TCMalloc_PageHeap::AllocLarge(Length n) { || (span->length < best->length) || ((span->length == best->length) && (span->start < best->start))) { best = span; - from_released = true; + ASSERT(best->location == Span::ON_RETURNED_FREELIST); } } } - return best == NULL ? NULL : Carve(best, n, from_released); + return best == NULL ? NULL : Carve(best, n); } Span* TCMalloc_PageHeap::Split(Span* span, Length n) { ASSERT(0 < n); ASSERT(n < span->length); - ASSERT(!span->free); + ASSERT(span->location == Span::IN_USE); ASSERT(span->sizeclass == 0); Event(span, 'T', n); const int extra = span->length - n; 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 @@ -1019,23 +1023,26 @@ Span* TCMalloc_PageHeap::Split(Span* span, Length n) { return leftover; } -Span* TCMalloc_PageHeap::Carve(Span* span, Length n, bool released) { +Span* TCMalloc_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->free = 0; + 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->free = 1; + 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 = released ? &listpair->returned : &listpair->normal; + Span* dst = (leftover->location == Span::ON_RETURNED_FREELIST + ? &listpair->returned : &listpair->normal); DLL_Prepend(dst, leftover); span->length = n; @@ -1048,7 +1055,7 @@ Span* TCMalloc_PageHeap::Carve(Span* span, Length n, bool released) { void TCMalloc_PageHeap::Delete(Span* span) { ASSERT(Check()); - ASSERT(!span->free); + ASSERT(span->location == Span::IN_USE); ASSERT(span->length > 0); ASSERT(GetDescriptor(span->start) == span); ASSERT(GetDescriptor(span->start + span->length - 1) == span); @@ -1066,7 +1073,7 @@ void TCMalloc_PageHeap::Delete(Span* span) { const PageID p = span->start; const Length n = span->length; Span* prev = GetDescriptor(p-1); - if (prev != NULL && prev->free) { + 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; @@ -1078,7 +1085,7 @@ void TCMalloc_PageHeap::Delete(Span* span) { Event(span, 'L', len); } Span* next = GetDescriptor(p+n); - if (next != NULL && next->free) { + if (next != NULL && next->location != Span::IN_USE) { // Merge next span into this span ASSERT(next->start == p+n); const Length len = next->length; @@ -1090,7 +1097,7 @@ void TCMalloc_PageHeap::Delete(Span* span) { } Event(span, 'D', span->length); - span->free = 1; + span->location = Span::ON_NORMAL_FREELIST; if (span->length < kMaxPages) { DLL_Prepend(&free_[span->length].normal, span); } else { @@ -1131,9 +1138,11 @@ void TCMalloc_PageHeap::IncrementalScavenge(Length n) { if (!DLL_IsEmpty(&slist->normal)) { // Release the last span on the normal portion of this list Span* s = slist->normal.prev; + ASSERT(s->location == Span::ON_NORMAL_FREELIST); DLL_Remove(s); TCMalloc_SystemRelease(reinterpret_cast<void*>(s->start << kPageShift), static_cast<size_t>(s->length << kPageShift)); + s->location = Span::ON_RETURNED_FREELIST; DLL_Prepend(&slist->returned, s); // Compute how long to wait until we return memory. @@ -1159,7 +1168,7 @@ void TCMalloc_PageHeap::IncrementalScavenge(Length n) { void TCMalloc_PageHeap::RegisterSizeClass(Span* span, size_t sc) { // Associate span object with all interior pages as well - ASSERT(!span->free); + ASSERT(span->location == Span::IN_USE); ASSERT(GetDescriptor(span->start) == span); ASSERT(GetDescriptor(span->start+span->length-1) == span); Event(span, 'C', sc); @@ -1296,18 +1305,19 @@ bool TCMalloc_PageHeap::GrowHeap(Length n) { bool TCMalloc_PageHeap::Check() { ASSERT(free_[0].normal.next == &free_[0].normal); ASSERT(free_[0].returned.next == &free_[0].returned); - CheckList(&large_.normal, kMaxPages, 1000000000); - CheckList(&large_.returned, kMaxPages, 1000000000); + CheckList(&large_.normal, kMaxPages, 1000000000, Span::ON_NORMAL_FREELIST); + CheckList(&large_.returned, kMaxPages, 1000000000, Span::ON_RETURNED_FREELIST); for (Length s = 1; s < kMaxPages; s++) { - CheckList(&free_[s].normal, s, s); - CheckList(&free_[s].returned, s, s); + CheckList(&free_[s].normal, s, s, Span::ON_NORMAL_FREELIST); + CheckList(&free_[s].returned, s, s, Span::ON_RETURNED_FREELIST); } return true; } -bool TCMalloc_PageHeap::CheckList(Span* list, Length min_pages, Length max_pages) { +bool TCMalloc_PageHeap::CheckList(Span* list, Length min_pages, Length max_pages, + int freelist) { for (Span* s = list->next; s != list; s = s->next) { - CHECK_CONDITION(s->free); + 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); @@ -1323,6 +1333,8 @@ static void ReleaseFreeList(Span* list, Span* returned) { Span* s = list->prev; DLL_Remove(s); DLL_Prepend(returned, s); + ASSERT(s->location == Span::ON_NORMAL_FREELIST); + s->location = Span::ON_RETURNED_FREELIST; TCMalloc_SystemRelease(reinterpret_cast<void*>(s->start << kPageShift), static_cast<size_t>(s->length << kPageShift)); } @@ -2503,6 +2515,7 @@ class TCMallocImplementation : public MallocExtension { *value = stats.system_bytes - stats.thread_bytes - stats.central_bytes + - stats.transfer_bytes - stats.pageheap_bytes; return true; } @@ -2963,9 +2976,23 @@ extern "C" void* realloc(void* old_ptr, size_t new_size) __THROW { // Reallocate if the new size is larger than the old size, // or if the new size is significantly smaller than the old size. - if ((new_size > old_size) || (AllocationSize(new_size) < old_size)) { - // Need to reallocate - void* new_ptr = do_malloc(new_size); + // We do hysteresis to avoid resizing ping-pongs: + // . If we need to grow, grow to max(new_size, old_size * 1.X) + // . Don't shrink unless new_size < old_size * 0.Y + // X and Y trade-off time for wasted space. For now we do 1.25 and 0.5. + const int lower_bound_to_grow = old_size + old_size / 4; + const int upper_bound_to_shrink = old_size / 2; + if ((new_size > old_size) || (new_size < upper_bound_to_shrink)) { + // Need to reallocate. + void* new_ptr = NULL; + + if (new_size > old_size && new_size < lower_bound_to_grow) { + new_ptr = do_malloc(lower_bound_to_grow); + } + if (new_ptr == NULL) { + // Either new_size is not a tiny increment, or last do_malloc failed. + new_ptr = do_malloc(new_size); + } if (new_ptr == NULL) { return NULL; } |