1// Copyright (c) 2008, Google Inc. 2// All rights reserved. 3// 4// Redistribution and use in source and binary forms, with or without 5// modification, are permitted provided that the following conditions are 6// met: 7// 8// * Redistributions of source code must retain the above copyright 9// notice, this list of conditions and the following disclaimer. 10// * Redistributions in binary form must reproduce the above 11// copyright notice, this list of conditions and the following disclaimer 12// in the documentation and/or other materials provided with the 13// distribution. 14// * Neither the name of Google Inc. nor the names of its 15// contributors may be used to endorse or promote products derived from 16// this software without specific prior written permission. 17// 18// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 19// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 20// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 21// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 22// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 23// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 24// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 25// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 26// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 27// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 28// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 29 30// --- 31// Author: Sanjay Ghemawat <opensource@google.com> 32 33#include <config.h> 34#ifdef HAVE_INTTYPES_H 35#include <inttypes.h> // for PRIuPTR 36#endif 37#include <gperftools/malloc_extension.h> // for MallocRange, etc 38#include "base/basictypes.h" 39#include "base/commandlineflags.h" 40#include "internal_logging.h" // for ASSERT, TCMalloc_Printer, etc 41#include "page_heap_allocator.h" // for PageHeapAllocator 42#include "static_vars.h" // for Static 43#include "system-alloc.h" // for TCMalloc_SystemAlloc, etc 44 45DEFINE_double(tcmalloc_release_rate, 46 EnvToDouble("TCMALLOC_RELEASE_RATE", 1.0), 47 "Rate at which we release unused memory to the system. " 48 "Zero means we never release memory back to the system. " 49 "Increase this flag to return memory faster; decrease it " 50 "to return memory slower. Reasonable rates are in the " 51 "range [0,10]"); 52 53namespace tcmalloc { 54 55PageHeap::PageHeap() 56 : pagemap_(MetaDataAlloc), 57 pagemap_cache_(0), 58 scavenge_counter_(0), 59 // Start scavenging at kMaxPages list 60 release_index_(kMaxPages) { 61 COMPILE_ASSERT(kNumClasses <= (1 << PageMapCache::kValuebits), valuebits); 62 DLL_Init(&large_.normal); 63 DLL_Init(&large_.returned); 64 for (int i = 0; i < kMaxPages; i++) { 65 DLL_Init(&free_[i].normal); 66 DLL_Init(&free_[i].returned); 67 } 68} 69 70Span* PageHeap::SearchFreeAndLargeLists(Length n) { 71 ASSERT(Check()); 72 ASSERT(n > 0); 73 74 // Find first size >= n that has a non-empty list 75 for (Length s = n; s < kMaxPages; s++) { 76 Span* ll = &free_[s].normal; 77 // If we're lucky, ll is non-empty, meaning it has a suitable span. 78 if (!DLL_IsEmpty(ll)) { 79 ASSERT(ll->next->location == Span::ON_NORMAL_FREELIST); 80 return Carve(ll->next, n); 81 } 82 // Alternatively, maybe there's a usable returned span. 83 ll = &free_[s].returned; 84 if (!DLL_IsEmpty(ll)) { 85 ASSERT(ll->next->location == Span::ON_RETURNED_FREELIST); 86 return Carve(ll->next, n); 87 } 88 } 89 // No luck in free lists, our last chance is in a larger class. 90 return AllocLarge(n); // May be NULL 91} 92 93Span* PageHeap::New(Length n) { 94 ASSERT(Check()); 95 ASSERT(n > 0); 96 97 Span* result = SearchFreeAndLargeLists(n); 98 if (result != NULL) 99 return result; 100 101 // Grow the heap and try again. 102 if (!GrowHeap(n)) { 103 ASSERT(Check()); 104 return NULL; 105 } 106 return SearchFreeAndLargeLists(n); 107} 108 109Span* PageHeap::AllocLarge(Length n) { 110 // find the best span (closest to n in size). 111 // The following loops implements address-ordered best-fit. 112 Span *best = NULL; 113 114 // Search through normal list 115 for (Span* span = large_.normal.next; 116 span != &large_.normal; 117 span = span->next) { 118 if (span->length >= n) { 119 if ((best == NULL) 120 || (span->length < best->length) 121 || ((span->length == best->length) && (span->start < best->start))) { 122 best = span; 123 ASSERT(best->location == Span::ON_NORMAL_FREELIST); 124 } 125 } 126 } 127 128 // Search through released list in case it has a better fit 129 for (Span* span = large_.returned.next; 130 span != &large_.returned; 131 span = span->next) { 132 if (span->length >= n) { 133 if ((best == NULL) 134 || (span->length < best->length) 135 || ((span->length == best->length) && (span->start < best->start))) { 136 best = span; 137 ASSERT(best->location == Span::ON_RETURNED_FREELIST); 138 } 139 } 140 } 141 142 return best == NULL ? NULL : Carve(best, n); 143} 144 145Span* PageHeap::Split(Span* span, Length n) { 146 ASSERT(0 < n); 147 ASSERT(n < span->length); 148 ASSERT(span->location == Span::IN_USE); 149 ASSERT(span->sizeclass == 0); 150 Event(span, 'T', n); 151 152 const int extra = span->length - n; 153 Span* leftover = NewSpan(span->start + n, extra); 154 ASSERT(leftover->location == Span::IN_USE); 155 Event(leftover, 'U', extra); 156 RecordSpan(leftover); 157 pagemap_.set(span->start + n - 1, span); // Update map from pageid to span 158 span->length = n; 159 160 return leftover; 161} 162 163Span* PageHeap::Carve(Span* span, Length n) { 164 ASSERT(n > 0); 165 ASSERT(span->location != Span::IN_USE); 166 const int old_location = span->location; 167 RemoveFromFreeList(span); 168 span->location = Span::IN_USE; 169 Event(span, 'A', n); 170 171 const int extra = span->length - n; 172 ASSERT(extra >= 0); 173 if (extra > 0) { 174 Span* leftover = NewSpan(span->start + n, extra); 175 leftover->location = old_location; 176 Event(leftover, 'S', extra); 177 RecordSpan(leftover); 178 PrependToFreeList(leftover); // Skip coalescing - no candidates possible 179 span->length = n; 180 pagemap_.set(span->start + n - 1, span); 181 } 182 ASSERT(Check()); 183 return span; 184} 185 186void PageHeap::Delete(Span* span) { 187 ASSERT(Check()); 188 ASSERT(span->location == Span::IN_USE); 189 ASSERT(span->length > 0); 190 ASSERT(GetDescriptor(span->start) == span); 191 ASSERT(GetDescriptor(span->start + span->length - 1) == span); 192 const Length n = span->length; 193 span->sizeclass = 0; 194 span->sample = 0; 195 span->location = Span::ON_NORMAL_FREELIST; 196 Event(span, 'D', span->length); 197 MergeIntoFreeList(span); // Coalesces if possible 198 IncrementalScavenge(n); 199 ASSERT(Check()); 200} 201 202void PageHeap::MergeIntoFreeList(Span* span) { 203 ASSERT(span->location != Span::IN_USE); 204 205 // Coalesce -- we guarantee that "p" != 0, so no bounds checking 206 // necessary. We do not bother resetting the stale pagemap 207 // entries for the pieces we are merging together because we only 208 // care about the pagemap entries for the boundaries. 209 // 210 // Note that only similar spans are merged together. For example, 211 // we do not coalesce "returned" spans with "normal" spans. 212 const PageID p = span->start; 213 const Length n = span->length; 214 Span* prev = GetDescriptor(p-1); 215 if (prev != NULL && prev->location == span->location) { 216 // Merge preceding span into this span 217 ASSERT(prev->start + prev->length == p); 218 const Length len = prev->length; 219 RemoveFromFreeList(prev); 220 DeleteSpan(prev); 221 span->start -= len; 222 span->length += len; 223 pagemap_.set(span->start, span); 224 Event(span, 'L', len); 225 } 226 Span* next = GetDescriptor(p+n); 227 if (next != NULL && next->location == span->location) { 228 // Merge next span into this span 229 ASSERT(next->start == p+n); 230 const Length len = next->length; 231 RemoveFromFreeList(next); 232 DeleteSpan(next); 233 span->length += len; 234 pagemap_.set(span->start + span->length - 1, span); 235 Event(span, 'R', len); 236 } 237 238 PrependToFreeList(span); 239} 240 241void PageHeap::PrependToFreeList(Span* span) { 242 ASSERT(span->location != Span::IN_USE); 243 SpanList* list = (span->length < kMaxPages) ? &free_[span->length] : &large_; 244 if (span->location == Span::ON_NORMAL_FREELIST) { 245 stats_.free_bytes += (span->length << kPageShift); 246 DLL_Prepend(&list->normal, span); 247 } else { 248 stats_.unmapped_bytes += (span->length << kPageShift); 249 DLL_Prepend(&list->returned, span); 250 } 251} 252 253void PageHeap::RemoveFromFreeList(Span* span) { 254 ASSERT(span->location != Span::IN_USE); 255 if (span->location == Span::ON_NORMAL_FREELIST) { 256 stats_.free_bytes -= (span->length << kPageShift); 257 } else { 258 stats_.unmapped_bytes -= (span->length << kPageShift); 259 } 260 DLL_Remove(span); 261} 262 263void PageHeap::IncrementalScavenge(Length n) { 264 // Fast path; not yet time to release memory 265 scavenge_counter_ -= n; 266 if (scavenge_counter_ >= 0) return; // Not yet time to scavenge 267 268 const double rate = FLAGS_tcmalloc_release_rate; 269 if (rate <= 1e-6) { 270 // Tiny release rate means that releasing is disabled. 271 scavenge_counter_ = kDefaultReleaseDelay; 272 return; 273 } 274 275 Length released_pages = ReleaseAtLeastNPages(1); 276 277 if (released_pages == 0) { 278 // Nothing to scavenge, delay for a while. 279 scavenge_counter_ = kDefaultReleaseDelay; 280 } else { 281 // Compute how long to wait until we return memory. 282 // FLAGS_tcmalloc_release_rate==1 means wait for 1000 pages 283 // after releasing one page. 284 const double mult = 1000.0 / rate; 285 double wait = mult * static_cast<double>(released_pages); 286 if (wait > kMaxReleaseDelay) { 287 // Avoid overflow and bound to reasonable range. 288 wait = kMaxReleaseDelay; 289 } 290 scavenge_counter_ = static_cast<int64_t>(wait); 291 } 292} 293 294Length PageHeap::ReleaseLastNormalSpan(SpanList* slist) { 295 Span* s = slist->normal.prev; 296 ASSERT(s->location == Span::ON_NORMAL_FREELIST); 297 RemoveFromFreeList(s); 298 const Length n = s->length; 299 TCMalloc_SystemRelease(reinterpret_cast<void*>(s->start << kPageShift), 300 static_cast<size_t>(s->length << kPageShift)); 301 s->location = Span::ON_RETURNED_FREELIST; 302 MergeIntoFreeList(s); // Coalesces if possible. 303 return n; 304} 305 306Length PageHeap::ReleaseAtLeastNPages(Length num_pages) { 307 Length released_pages = 0; 308 Length prev_released_pages = -1; 309 310 // Round robin through the lists of free spans, releasing the last 311 // span in each list. Stop after releasing at least num_pages. 312 while (released_pages < num_pages) { 313 if (released_pages == prev_released_pages) { 314 // Last iteration of while loop made no progress. 315 break; 316 } 317 prev_released_pages = released_pages; 318 319 for (int i = 0; i < kMaxPages+1 && released_pages < num_pages; 320 i++, release_index_++) { 321 if (release_index_ > kMaxPages) release_index_ = 0; 322 SpanList* slist = (release_index_ == kMaxPages) ? 323 &large_ : &free_[release_index_]; 324 if (!DLL_IsEmpty(&slist->normal)) { 325 Length released_len = ReleaseLastNormalSpan(slist); 326 released_pages += released_len; 327 } 328 } 329 } 330 return released_pages; 331} 332 333void PageHeap::RegisterSizeClass(Span* span, size_t sc) { 334 // Associate span object with all interior pages as well 335 ASSERT(span->location == Span::IN_USE); 336 ASSERT(GetDescriptor(span->start) == span); 337 ASSERT(GetDescriptor(span->start+span->length-1) == span); 338 Event(span, 'C', sc); 339 span->sizeclass = sc; 340 for (Length i = 1; i < span->length-1; i++) { 341 pagemap_.set(span->start+i, span); 342 } 343} 344 345void PageHeap::GetSmallSpanStats(SmallSpanStats* result) { 346 for (int s = 0; s < kMaxPages; s++) { 347 result->normal_length[s] = DLL_Length(&free_[s].normal); 348 result->returned_length[s] = DLL_Length(&free_[s].returned); 349 } 350} 351 352void PageHeap::GetLargeSpanStats(LargeSpanStats* result) { 353 result->spans = 0; 354 result->normal_pages = 0; 355 result->returned_pages = 0; 356 for (Span* s = large_.normal.next; s != &large_.normal; s = s->next) { 357 result->normal_pages += s->length;; 358 result->spans++; 359 } 360 for (Span* s = large_.returned.next; s != &large_.returned; s = s->next) { 361 result->returned_pages += s->length; 362 result->spans++; 363 } 364} 365 366bool PageHeap::GetNextRange(PageID start, base::MallocRange* r) { 367 Span* span = reinterpret_cast<Span*>(pagemap_.Next(start)); 368 if (span == NULL) { 369 return false; 370 } 371 r->address = span->start << kPageShift; 372 r->length = span->length << kPageShift; 373 r->fraction = 0; 374 switch (span->location) { 375 case Span::IN_USE: 376 r->type = base::MallocRange::INUSE; 377 r->fraction = 1; 378 if (span->sizeclass > 0) { 379 // Only some of the objects in this span may be in use. 380 const size_t osize = Static::sizemap()->class_to_size(span->sizeclass); 381 r->fraction = (1.0 * osize * span->refcount) / r->length; 382 } 383 break; 384 case Span::ON_NORMAL_FREELIST: 385 r->type = base::MallocRange::FREE; 386 break; 387 case Span::ON_RETURNED_FREELIST: 388 r->type = base::MallocRange::UNMAPPED; 389 break; 390 default: 391 r->type = base::MallocRange::UNKNOWN; 392 break; 393 } 394 return true; 395} 396 397static void RecordGrowth(size_t growth) { 398 StackTrace* t = Static::stacktrace_allocator()->New(); 399 t->depth = GetStackTrace(t->stack, kMaxStackDepth-1, 3); 400 t->size = growth; 401 t->stack[kMaxStackDepth-1] = reinterpret_cast<void*>(Static::growth_stacks()); 402 Static::set_growth_stacks(t); 403} 404 405bool PageHeap::GrowHeap(Length n) { 406 ASSERT(kMaxPages >= kMinSystemAlloc); 407 if (n > kMaxValidPages) return false; 408 Length ask = (n>kMinSystemAlloc) ? n : static_cast<Length>(kMinSystemAlloc); 409 size_t actual_size; 410 void* ptr = TCMalloc_SystemAlloc(ask << kPageShift, &actual_size, kPageSize); 411 if (ptr == NULL) { 412 if (n < ask) { 413 // Try growing just "n" pages 414 ask = n; 415 ptr = TCMalloc_SystemAlloc(ask << kPageShift, &actual_size, kPageSize); 416 } 417 if (ptr == NULL) return false; 418 } 419 ask = actual_size >> kPageShift; 420 RecordGrowth(ask << kPageShift); 421 422 uint64_t old_system_bytes = stats_.system_bytes; 423 stats_.system_bytes += (ask << kPageShift); 424 const PageID p = reinterpret_cast<uintptr_t>(ptr) >> kPageShift; 425 ASSERT(p > 0); 426 427 // If we have already a lot of pages allocated, just pre allocate a bunch of 428 // memory for the page map. This prevents fragmentation by pagemap metadata 429 // when a program keeps allocating and freeing large blocks. 430 431 if (old_system_bytes < kPageMapBigAllocationThreshold 432 && stats_.system_bytes >= kPageMapBigAllocationThreshold) { 433 pagemap_.PreallocateMoreMemory(); 434 } 435 436 // Make sure pagemap_ has entries for all of the new pages. 437 // Plus ensure one before and one after so coalescing code 438 // does not need bounds-checking. 439 if (pagemap_.Ensure(p-1, ask+2)) { 440 // Pretend the new area is allocated and then Delete() it to cause 441 // any necessary coalescing to occur. 442 Span* span = NewSpan(p, ask); 443 RecordSpan(span); 444 Delete(span); 445 ASSERT(Check()); 446 return true; 447 } else { 448 // We could not allocate memory within "pagemap_" 449 // TODO: Once we can return memory to the system, return the new span 450 return false; 451 } 452} 453 454bool PageHeap::Check() { 455 ASSERT(free_[0].normal.next == &free_[0].normal); 456 ASSERT(free_[0].returned.next == &free_[0].returned); 457 return true; 458} 459 460bool PageHeap::CheckExpensive() { 461 bool result = Check(); 462 CheckList(&large_.normal, kMaxPages, 1000000000, Span::ON_NORMAL_FREELIST); 463 CheckList(&large_.returned, kMaxPages, 1000000000, Span::ON_RETURNED_FREELIST); 464 for (Length s = 1; s < kMaxPages; s++) { 465 CheckList(&free_[s].normal, s, s, Span::ON_NORMAL_FREELIST); 466 CheckList(&free_[s].returned, s, s, Span::ON_RETURNED_FREELIST); 467 } 468 return result; 469} 470 471bool PageHeap::CheckList(Span* list, Length min_pages, Length max_pages, 472 int freelist) { 473 for (Span* s = list->next; s != list; s = s->next) { 474 CHECK_CONDITION(s->location == freelist); // NORMAL or RETURNED 475 CHECK_CONDITION(s->length >= min_pages); 476 CHECK_CONDITION(s->length <= max_pages); 477 CHECK_CONDITION(GetDescriptor(s->start) == s); 478 CHECK_CONDITION(GetDescriptor(s->start+s->length-1) == s); 479 } 480 return true; 481} 482 483} // namespace tcmalloc 484