This source file includes following definitions.
- release_index_
- SearchFreeAndLargeLists
- New
- AllocLarge
- Split
- Carve
- Delete
- MergeIntoFreeList
- PrependToFreeList
- RemoveFromFreeList
- IncrementalScavenge
- ReleaseLastNormalSpan
- ReleaseAtLeastNPages
- RegisterSizeClass
- GetSmallSpanStats
- GetLargeSpanStats
- GetNextRange
- RecordGrowth
- GrowHeap
- Check
- CheckExpensive
- CheckList
#include <config.h>
#ifdef HAVE_INTTYPES_H
#include <inttypes.h>
#endif
#include <gperftools/malloc_extension.h>
#include "base/basictypes.h"
#include "base/commandlineflags.h"
#include "internal_logging.h"
#include "page_heap_allocator.h"
#include "static_vars.h"
#include "system-alloc.h"
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),
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::SearchFreeAndLargeLists(Length n) {
ASSERT(Check());
ASSERT(n > 0);
for (Length s = n; s < kMaxPages; s++) {
Span* ll = &free_[s].normal;
if (!DLL_IsEmpty(ll)) {
ASSERT(ll->next->location == Span::ON_NORMAL_FREELIST);
return Carve(ll->next, n);
}
ll = &free_[s].returned;
if (!DLL_IsEmpty(ll)) {
ASSERT(ll->next->location == Span::ON_RETURNED_FREELIST);
return Carve(ll->next, n);
}
}
return AllocLarge(n);
}
Span* PageHeap::New(Length n) {
ASSERT(Check());
ASSERT(n > 0);
Span* result = SearchFreeAndLargeLists(n);
if (result != NULL)
return result;
if (!GrowHeap(n)) {
ASSERT(Check());
return NULL;
}
return SearchFreeAndLargeLists(n);
}
Span* PageHeap::AllocLarge(Length n) {
Span *best = NULL;
for (Span* span = large_.normal.next;
span != &large_.normal;
span = span->next) {
if (span->length >= n) {
if ((best == NULL)
|| (span->length < best->length)
|| ((span->length == best->length) && (span->start < best->start))) {
best = span;
ASSERT(best->location == Span::ON_NORMAL_FREELIST);
}
}
}
for (Span* span = large_.returned.next;
span != &large_.returned;
span = span->next) {
if (span->length >= n) {
if ((best == NULL)
|| (span->length < best->length)
|| ((span->length == best->length) && (span->start < best->start))) {
best = span;
ASSERT(best->location == Span::ON_RETURNED_FREELIST);
}
}
}
return best == NULL ? NULL : Carve(best, n);
}
Span* PageHeap::Split(Span* span, Length n) {
ASSERT(0 < n);
ASSERT(n < span->length);
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);
span->length = n;
return leftover;
}
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);
PrependToFreeList(leftover);
span->length = n;
pagemap_.set(span->start + n - 1, span);
}
ASSERT(Check());
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);
IncrementalScavenge(n);
ASSERT(Check());
}
void PageHeap::MergeIntoFreeList(Span* span) {
ASSERT(span->location != Span::IN_USE);
const PageID p = span->start;
const Length n = span->length;
Span* prev = GetDescriptor(p-1);
if (prev != NULL && prev->location == span->location) {
ASSERT(prev->start + prev->length == p);
const Length len = prev->length;
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->location) {
ASSERT(next->start == p+n);
const Length len = next->length;
RemoveFromFreeList(next);
DeleteSpan(next);
span->length += len;
pagemap_.set(span->start + span->length - 1, span);
Event(span, 'R', len);
}
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 {
stats_.unmapped_bytes += (span->length << kPageShift);
DLL_Prepend(&list->returned, span);
}
}
void PageHeap::RemoveFromFreeList(Span* span) {
ASSERT(span->location != Span::IN_USE);
if (span->location == Span::ON_NORMAL_FREELIST) {
stats_.free_bytes -= (span->length << kPageShift);
} else {
stats_.unmapped_bytes -= (span->length << kPageShift);
}
DLL_Remove(span);
}
void PageHeap::IncrementalScavenge(Length n) {
scavenge_counter_ -= n;
if (scavenge_counter_ >= 0) return;
const double rate = FLAGS_tcmalloc_release_rate;
if (rate <= 1e-6) {
scavenge_counter_ = kDefaultReleaseDelay;
return;
}
Length released_pages = ReleaseAtLeastNPages(1);
if (released_pages == 0) {
scavenge_counter_ = kDefaultReleaseDelay;
} else {
const double mult = 1000.0 / rate;
double wait = mult * static_cast<double>(released_pages);
if (wait > kMaxReleaseDelay) {
wait = kMaxReleaseDelay;
}
scavenge_counter_ = static_cast<int64_t>(wait);
}
}
Length PageHeap::ReleaseLastNormalSpan(SpanList* slist) {
Span* s = slist->normal.prev;
ASSERT(s->location == Span::ON_NORMAL_FREELIST);
RemoveFromFreeList(s);
const Length n = s->length;
TCMalloc_SystemRelease(reinterpret_cast<void*>(s->start << kPageShift),
static_cast<size_t>(s->length << kPageShift));
s->location = Span::ON_RETURNED_FREELIST;
MergeIntoFreeList(s);
return n;
}
Length PageHeap::ReleaseAtLeastNPages(Length num_pages) {
Length released_pages = 0;
Length prev_released_pages = -1;
while (released_pages < num_pages) {
if (released_pages == prev_released_pages) {
break;
}
prev_released_pages = released_pages;
for (int i = 0; i < kMaxPages+1 && released_pages < num_pages;
i++, release_index_++) {
if (release_index_ > kMaxPages) release_index_ = 0;
SpanList* slist = (release_index_ == kMaxPages) ?
&large_ : &free_[release_index_];
if (!DLL_IsEmpty(&slist->normal)) {
Length released_len = ReleaseLastNormalSpan(slist);
released_pages += released_len;
}
}
}
return released_pages;
}
void PageHeap::RegisterSizeClass(Span* span, size_t sc) {
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);
}
}
void PageHeap::GetSmallSpanStats(SmallSpanStats* result) {
for (int s = 0; s < kMaxPages; s++) {
result->normal_length[s] = DLL_Length(&free_[s].normal);
result->returned_length[s] = DLL_Length(&free_[s].returned);
}
}
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++;
}
for (Span* s = large_.returned.next; s != &large_.returned; s = s->next) {
result->returned_pages += s->length;
result->spans++;
}
}
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;
switch (span->location) {
case Span::IN_USE:
r->type = base::MallocRange::INUSE;
r->fraction = 1;
if (span->sizeclass > 0) {
const size_t osize = Static::sizemap()->class_to_size(span->sizeclass);
r->fraction = (1.0 * osize * span->refcount) / r->length;
}
break;
case Span::ON_NORMAL_FREELIST:
r->type = base::MallocRange::FREE;
break;
case Span::ON_RETURNED_FREELIST:
r->type = base::MallocRange::UNMAPPED;
break;
default:
r->type = base::MallocRange::UNKNOWN;
break;
}
return true;
}
static void RecordGrowth(size_t growth) {
StackTrace* t = Static::stacktrace_allocator()->New();
t->depth = GetStackTrace(t->stack, kMaxStackDepth-1, 3);
t->size = growth;
t->stack[kMaxStackDepth-1] = reinterpret_cast<void*>(Static::growth_stacks());
Static::set_growth_stacks(t);
}
bool PageHeap::GrowHeap(Length n) {
ASSERT(kMaxPages >= kMinSystemAlloc);
if (n > kMaxValidPages) return false;
Length ask = (n>kMinSystemAlloc) ? n : static_cast<Length>(kMinSystemAlloc);
size_t actual_size;
void* ptr = TCMalloc_SystemAlloc(ask << kPageShift, &actual_size, kPageSize);
if (ptr == NULL) {
if (n < ask) {
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);
const PageID p = reinterpret_cast<uintptr_t>(ptr) >> kPageShift;
ASSERT(p > 0);
if (old_system_bytes < kPageMapBigAllocationThreshold
&& stats_.system_bytes >= kPageMapBigAllocationThreshold) {
pagemap_.PreallocateMoreMemory();
}
if (pagemap_.Ensure(p-1, ask+2)) {
Span* span = NewSpan(p, ask);
RecordSpan(span);
Delete(span);
ASSERT(Check());
return true;
} else {
return false;
}
}
bool PageHeap::Check() {
ASSERT(free_[0].normal.next == &free_[0].normal);
ASSERT(free_[0].returned.next == &free_[0].returned);
return true;
}
bool PageHeap::CheckExpensive() {
bool result = Check();
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, Span::ON_NORMAL_FREELIST);
CheckList(&free_[s].returned, s, s, Span::ON_RETURNED_FREELIST);
}
return result;
}
bool 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->location == freelist);
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;
}
}