15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright (c) 2008, Google Inc. 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// All rights reserved. 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Redistribution and use in source and binary forms, with or without 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// modification, are permitted provided that the following conditions are 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// met: 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// * Redistributions of source code must retain the above copyright 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// notice, this list of conditions and the following disclaimer. 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// * Redistributions in binary form must reproduce the above 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// copyright notice, this list of conditions and the following disclaimer 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// in the documentation and/or other materials provided with the 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// distribution. 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// * Neither the name of Google Inc. nor the names of its 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// contributors may be used to endorse or promote products derived from 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// this software without specific prior written permission. 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// --- 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Author: Sanjay Ghemawat <opensource@google.com> 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <config.h> 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef HAVE_INTTYPES_H 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <inttypes.h> // for PRIuPTR 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <gperftools/malloc_extension.h> // for MallocRange, etc 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/basictypes.h" 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/commandlineflags.h" 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "internal_logging.h" // for ASSERT, TCMalloc_Printer, etc 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "page_heap_allocator.h" // for PageHeapAllocator 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "static_vars.h" // for Static 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "system-alloc.h" // for TCMalloc_SystemAlloc, etc 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)DEFINE_double(tcmalloc_release_rate, 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EnvToDouble("TCMALLOC_RELEASE_RATE", 1.0), 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) "Rate at which we release unused memory to the system. " 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) "Zero means we never release memory back to the system. " 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) "Increase this flag to return memory faster; decrease it " 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) "to return memory slower. Reasonable rates are in the " 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) "range [0,10]"); 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace tcmalloc { 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)PageHeap::PageHeap() 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) : pagemap_(MetaDataAlloc), 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pagemap_cache_(0), 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) scavenge_counter_(0), 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Start scavenging at kMaxPages list 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) release_index_(kMaxPages) { 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) COMPILE_ASSERT(kNumClasses <= (1 << PageMapCache::kValuebits), valuebits); 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DLL_Init(&large_.normal); 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DLL_Init(&large_.returned); 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 0; i < kMaxPages; i++) { 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DLL_Init(&free_[i].normal); 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DLL_Init(&free_[i].returned); 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)Span* PageHeap::SearchFreeAndLargeLists(Length n) { 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(Check()); 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(n > 0); 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Find first size >= n that has a non-empty list 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (Length s = n; s < kMaxPages; s++) { 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Span* ll = &free_[s].normal; 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If we're lucky, ll is non-empty, meaning it has a suitable span. 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!DLL_IsEmpty(ll)) { 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(ll->next->location == Span::ON_NORMAL_FREELIST); 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return Carve(ll->next, n); 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Alternatively, maybe there's a usable returned span. 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ll = &free_[s].returned; 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!DLL_IsEmpty(ll)) { 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(ll->next->location == Span::ON_RETURNED_FREELIST); 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return Carve(ll->next, n); 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // No luck in free lists, our last chance is in a larger class. 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return AllocLarge(n); // May be NULL 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)Span* PageHeap::New(Length n) { 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(Check()); 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(n > 0); 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Span* result = SearchFreeAndLargeLists(n); 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (result != NULL) 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return result; 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Grow the heap and try again. 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!GrowHeap(n)) { 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(stats_.unmapped_bytes+ stats_.committed_bytes==stats_.system_bytes); 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(Check()); 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return NULL; 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return SearchFreeAndLargeLists(n); 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)Span* PageHeap::AllocLarge(Length n) { 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // find the best span (closest to n in size). 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The following loops implements address-ordered best-fit. 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Span *best = NULL; 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Search through normal list 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (Span* span = large_.normal.next; 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) span != &large_.normal; 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) span = span->next) { 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (span->length >= n) { 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if ((best == NULL) 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) || (span->length < best->length) 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) || ((span->length == best->length) && (span->start < best->start))) { 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) best = span; 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(best->location == Span::ON_NORMAL_FREELIST); 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Search through released list in case it has a better fit 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (Span* span = large_.returned.next; 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) span != &large_.returned; 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) span = span->next) { 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (span->length >= n) { 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if ((best == NULL) 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) || (span->length < best->length) 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) || ((span->length == best->length) && (span->start < best->start))) { 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) best = span; 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(best->location == Span::ON_RETURNED_FREELIST); 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return best == NULL ? NULL : Carve(best, n); 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)Span* PageHeap::Split(Span* span, Length n) { 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(0 < n); 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(n < span->length); 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(span->location == Span::IN_USE); 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(span->sizeclass == 0); 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Event(span, 'T', n); 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int extra = span->length - n; 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Span* leftover = NewSpan(span->start + n, extra); 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(leftover->location == Span::IN_USE); 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Event(leftover, 'U', extra); 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RecordSpan(leftover); 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pagemap_.set(span->start + n - 1, span); // Update map from pageid to span 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) span->length = n; 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return leftover; 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void PageHeap::CommitSpan(Span* span) { 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TCMalloc_SystemCommit(reinterpret_cast<void*>(span->start << kPageShift), 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static_cast<size_t>(span->length << kPageShift)); 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) stats_.committed_bytes += span->length << kPageShift; 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void PageHeap::DecommitSpan(Span* span) { 1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TCMalloc_SystemRelease(reinterpret_cast<void*>(span->start << kPageShift), 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static_cast<size_t>(span->length << kPageShift)); 1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) stats_.committed_bytes -= span->length << kPageShift; 1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)Span* PageHeap::Carve(Span* span, Length n) { 1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(n > 0); 1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(span->location != Span::IN_USE); 1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int old_location = span->location; 1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RemoveFromFreeList(span); 1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) span->location = Span::IN_USE; 1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Event(span, 'A', n); 1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int extra = span->length - n; 1855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(extra >= 0); 1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (extra > 0) { 1875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Span* leftover = NewSpan(span->start + n, extra); 1885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) leftover->location = old_location; 1895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Event(leftover, 'S', extra); 1905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RecordSpan(leftover); 1915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The previous span of |leftover| was just splitted -- no need to 1935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // coalesce them. The next span of |leftover| was not previously coalesced 1945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // with |span|, i.e. is NULL or has got location other than |old_location|. 1955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const PageID p = leftover->start; 1965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Length len = leftover->length; 1975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Span* next = GetDescriptor(p+len); 1985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT (next == NULL || 1995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) next->location == Span::IN_USE || 2005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) next->location != leftover->location); 2015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PrependToFreeList(leftover); // Skip coalescing - no candidates possible 2035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) span->length = n; 2045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pagemap_.set(span->start + n - 1, span); 2055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(Check()); 2075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (old_location == Span::ON_RETURNED_FREELIST) { 2085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // We need to recommit this address space. 2095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CommitSpan(span); 2105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(span->location == Span::IN_USE); 2125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(span->length == n); 2135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(stats_.unmapped_bytes+ stats_.committed_bytes==stats_.system_bytes); 2145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return span; 2155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void PageHeap::Delete(Span* span) { 2185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(Check()); 2195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(span->location == Span::IN_USE); 2205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(span->length > 0); 2215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(GetDescriptor(span->start) == span); 2225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(GetDescriptor(span->start + span->length - 1) == span); 2235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Length n = span->length; 2245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) span->sizeclass = 0; 2255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) span->sample = 0; 2265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) span->location = Span::ON_NORMAL_FREELIST; 2275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Event(span, 'D', span->length); 2285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MergeIntoFreeList(span); // Coalesces if possible 2295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) IncrementalScavenge(n); 2305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(stats_.unmapped_bytes+ stats_.committed_bytes==stats_.system_bytes); 2315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(Check()); 2325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void PageHeap::MergeIntoFreeList(Span* span) { 2355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(span->location != Span::IN_USE); 2365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Coalesce -- we guarantee that "p" != 0, so no bounds checking 2385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // necessary. We do not bother resetting the stale pagemap 2395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // entries for the pieces we are merging together because we only 2405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // care about the pagemap entries for the boundaries. 2415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 2425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Note that the adjacent spans we merge into "span" may come out of a 2435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // "normal" (committed) list, and cleanly merge with our IN_USE span, which 2445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // is implicitly committed. If the adjacents spans are on the "returned" 2455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // (decommitted) list, then we must get both spans into the same state before 2465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // or after we coalesce them. The current code always decomits. This is 2475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // achieved by blindly decommitting the entire coalesced region, which may 2485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // include any combination of committed and decommitted spans, at the end of 2495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // the method. 2505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // TODO(jar): "Always decommit" causes some extra calls to commit when we are 2525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // called in GrowHeap() during an allocation :-/. We need to eval the cost of 2535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // that oscillation, and possibly do something to reduce it. 2545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // TODO(jar): We need a better strategy for deciding to commit, or decommit, 2565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // based on memory usage and free heap sizes. 2575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const PageID p = span->start; 2595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Length n = span->length; 2605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Span* prev = GetDescriptor(p-1); 2615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (prev != NULL && prev->location != Span::IN_USE) { 2625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Merge preceding span into this span 2635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(prev->start + prev->length == p); 2645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Length len = prev->length; 2655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (prev->location == Span::ON_RETURNED_FREELIST) { 2665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // We're about to put the merge span into the returned freelist and call 2675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // DecommitSpan() on it, which will mark the entire span including this 2685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // one as released and decrease stats_.committed_bytes by the size of the 2695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // merged span. To make the math work out we temporarily increase the 2705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // stats_.committed_bytes amount. 2715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) stats_.committed_bytes += prev->length << kPageShift; 2725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RemoveFromFreeList(prev); 2745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DeleteSpan(prev); 2755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) span->start -= len; 2765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) span->length += len; 2775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pagemap_.set(span->start, span); 2785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Event(span, 'L', len); 2795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Span* next = GetDescriptor(p+n); 2815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (next != NULL && next->location != Span::IN_USE) { 2825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Merge next span into this span 2835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(next->start == p+n); 2845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Length len = next->length; 2855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (next->location == Span::ON_RETURNED_FREELIST) { 2865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // See the comment below 'if (prev->location ...' for explanation. 2875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) stats_.committed_bytes += next->length << kPageShift; 2885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RemoveFromFreeList(next); 2905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DeleteSpan(next); 2915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) span->length += len; 2925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pagemap_.set(span->start + span->length - 1, span); 2935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Event(span, 'R', len); 2945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Event(span, 'D', span->length); 2975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) span->location = Span::ON_RETURNED_FREELIST; 2985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DecommitSpan(span); 2995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PrependToFreeList(span); 3005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void PageHeap::PrependToFreeList(Span* span) { 3035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(span->location != Span::IN_USE); 3045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SpanList* list = (span->length < kMaxPages) ? &free_[span->length] : &large_; 3055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (span->location == Span::ON_NORMAL_FREELIST) { 3065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) stats_.free_bytes += (span->length << kPageShift); 3075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DLL_Prepend(&list->normal, span); 3085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 3095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) stats_.unmapped_bytes += (span->length << kPageShift); 3105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DLL_Prepend(&list->returned, span); 3115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void PageHeap::RemoveFromFreeList(Span* span) { 3155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(span->location != Span::IN_USE); 3165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (span->location == Span::ON_NORMAL_FREELIST) { 3175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) stats_.free_bytes -= (span->length << kPageShift); 3185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 3195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) stats_.unmapped_bytes -= (span->length << kPageShift); 3205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DLL_Remove(span); 3225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void PageHeap::IncrementalScavenge(Length n) { 3255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Fast path; not yet time to release memory 3265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) scavenge_counter_ -= n; 3275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (scavenge_counter_ >= 0) return; // Not yet time to scavenge 3285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const double rate = FLAGS_tcmalloc_release_rate; 3305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (rate <= 1e-6) { 3315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Tiny release rate means that releasing is disabled. 3325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) scavenge_counter_ = kDefaultReleaseDelay; 3335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 3345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Length released_pages = ReleaseAtLeastNPages(1); 3375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (released_pages == 0) { 3395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Nothing to scavenge, delay for a while. 3405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) scavenge_counter_ = kDefaultReleaseDelay; 3415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 3425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Compute how long to wait until we return memory. 3435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // FLAGS_tcmalloc_release_rate==1 means wait for 1000 pages 3445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // after releasing one page. 3455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const double mult = 1000.0 / rate; 3465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double wait = mult * static_cast<double>(released_pages); 3475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (wait > kMaxReleaseDelay) { 3485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Avoid overflow and bound to reasonable range. 3495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) wait = kMaxReleaseDelay; 3505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) scavenge_counter_ = static_cast<int64_t>(wait); 3525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)Length PageHeap::ReleaseLastNormalSpan(SpanList* slist) { 3565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Span* s = slist->normal.prev; 3575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(s->location == Span::ON_NORMAL_FREELIST); 3585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RemoveFromFreeList(s); 3595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Length n = s->length; 3605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TCMalloc_SystemRelease(reinterpret_cast<void*>(s->start << kPageShift), 3615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static_cast<size_t>(s->length << kPageShift)); 3625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->location = Span::ON_RETURNED_FREELIST; 3635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MergeIntoFreeList(s); // Coalesces if possible. 3645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return n; 3655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)Length PageHeap::ReleaseAtLeastNPages(Length num_pages) { 3685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Length released_pages = 0; 3695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Length prev_released_pages = -1; 3705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Round robin through the lists of free spans, releasing the last 3725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // span in each list. Stop after releasing at least num_pages. 3735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (released_pages < num_pages) { 3745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (released_pages == prev_released_pages) { 3755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Last iteration of while loop made no progress. 3765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 3775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) prev_released_pages = released_pages; 3795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 0; i < kMaxPages+1 && released_pages < num_pages; 3815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) i++, release_index_++) { 3825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (release_index_ > kMaxPages) release_index_ = 0; 3835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SpanList* slist = (release_index_ == kMaxPages) ? 3845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) &large_ : &free_[release_index_]; 3855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!DLL_IsEmpty(&slist->normal)) { 3865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Length released_len = ReleaseLastNormalSpan(slist); 3875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) released_pages += released_len; 3885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return released_pages; 3925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void PageHeap::RegisterSizeClass(Span* span, size_t sc) { 3955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Associate span object with all interior pages as well 3965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(span->location == Span::IN_USE); 3975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(GetDescriptor(span->start) == span); 3985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(GetDescriptor(span->start+span->length-1) == span); 3995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Event(span, 'C', sc); 4005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) span->sizeclass = sc; 4015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (Length i = 1; i < span->length-1; i++) { 4025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pagemap_.set(span->start+i, span); 4035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void PageHeap::GetSmallSpanStats(SmallSpanStats* result) { 4075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int s = 0; s < kMaxPages; s++) { 4085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) result->normal_length[s] = DLL_Length(&free_[s].normal); 4095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) result->returned_length[s] = DLL_Length(&free_[s].returned); 4105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void PageHeap::GetLargeSpanStats(LargeSpanStats* result) { 4145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) result->spans = 0; 4155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) result->normal_pages = 0; 4165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) result->returned_pages = 0; 4175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (Span* s = large_.normal.next; s != &large_.normal; s = s->next) { 4185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) result->normal_pages += s->length;; 4195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) result->spans++; 4205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (Span* s = large_.returned.next; s != &large_.returned; s = s->next) { 4225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) result->returned_pages += s->length; 4235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) result->spans++; 4245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool PageHeap::GetNextRange(PageID start, base::MallocRange* r) { 4285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Span* span = reinterpret_cast<Span*>(pagemap_.Next(start)); 4295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (span == NULL) { 4305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 4315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) r->address = span->start << kPageShift; 4335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) r->length = span->length << kPageShift; 4345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) r->fraction = 0; 4355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) switch (span->location) { 4365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case Span::IN_USE: 4375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) r->type = base::MallocRange::INUSE; 4385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) r->fraction = 1; 4395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (span->sizeclass > 0) { 4405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Only some of the objects in this span may be in use. 4415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const size_t osize = Static::sizemap()->class_to_size(span->sizeclass); 4425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) r->fraction = (1.0 * osize * span->refcount) / r->length; 4435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 4455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case Span::ON_NORMAL_FREELIST: 4465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) r->type = base::MallocRange::FREE; 4475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 4485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case Span::ON_RETURNED_FREELIST: 4495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) r->type = base::MallocRange::UNMAPPED; 4505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 4515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) default: 4525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) r->type = base::MallocRange::UNKNOWN; 4535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 4545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 4565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void RecordGrowth(size_t growth) { 4595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) StackTrace* t = Static::stacktrace_allocator()->New(); 4605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) t->depth = GetStackTrace(t->stack, kMaxStackDepth-1, 3); 4615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) t->size = growth; 4625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) t->stack[kMaxStackDepth-1] = reinterpret_cast<void*>(Static::growth_stacks()); 4635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Static::set_growth_stacks(t); 4645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool PageHeap::GrowHeap(Length n) { 4675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(kMaxPages >= kMinSystemAlloc); 4685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (n > kMaxValidPages) return false; 4695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Length ask = (n>kMinSystemAlloc) ? n : static_cast<Length>(kMinSystemAlloc); 4705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t actual_size; 4715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void* ptr = TCMalloc_SystemAlloc(ask << kPageShift, &actual_size, kPageSize); 4725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (ptr == NULL) { 4735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (n < ask) { 4745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Try growing just "n" pages 4755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ask = n; 4765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ptr = TCMalloc_SystemAlloc(ask << kPageShift, &actual_size, kPageSize); 4775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (ptr == NULL) return false; 4795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ask = actual_size >> kPageShift; 4815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RecordGrowth(ask << kPageShift); 4825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint64_t old_system_bytes = stats_.system_bytes; 4845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) stats_.system_bytes += (ask << kPageShift); 4855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) stats_.committed_bytes += (ask << kPageShift); 4865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const PageID p = reinterpret_cast<uintptr_t>(ptr) >> kPageShift; 4875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(p > 0); 4885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If we have already a lot of pages allocated, just pre allocate a bunch of 4905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // memory for the page map. This prevents fragmentation by pagemap metadata 4915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // when a program keeps allocating and freeing large blocks. 4925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (old_system_bytes < kPageMapBigAllocationThreshold 4945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) && stats_.system_bytes >= kPageMapBigAllocationThreshold) { 4955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pagemap_.PreallocateMoreMemory(); 4965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Make sure pagemap_ has entries for all of the new pages. 4995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Plus ensure one before and one after so coalescing code 5005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // does not need bounds-checking. 5015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (pagemap_.Ensure(p-1, ask+2)) { 5025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Pretend the new area is allocated and then Delete() it to cause 5035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // any necessary coalescing to occur. 5045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Span* span = NewSpan(p, ask); 5055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RecordSpan(span); 5065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Delete(span); 5075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(stats_.unmapped_bytes+ stats_.committed_bytes==stats_.system_bytes); 5085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(Check()); 5095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 5105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 5115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // We could not allocate memory within "pagemap_" 5125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // TODO: Once we can return memory to the system, return the new span 5135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 5145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 5165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool PageHeap::Check() { 5185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(free_[0].normal.next == &free_[0].normal); 5195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(free_[0].returned.next == &free_[0].returned); 5205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 5215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 5225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool PageHeap::CheckExpensive() { 5245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool result = Check(); 5255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CheckList(&large_.normal, kMaxPages, 1000000000, Span::ON_NORMAL_FREELIST); 5265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CheckList(&large_.returned, kMaxPages, 1000000000, Span::ON_RETURNED_FREELIST); 5275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (Length s = 1; s < kMaxPages; s++) { 5285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CheckList(&free_[s].normal, s, s, Span::ON_NORMAL_FREELIST); 5295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CheckList(&free_[s].returned, s, s, Span::ON_RETURNED_FREELIST); 5305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return result; 5325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 5335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool PageHeap::CheckList(Span* list, Length min_pages, Length max_pages, 5355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int freelist) { 5365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (Span* s = list->next; s != list; s = s->next) { 5375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK_CONDITION(s->location == freelist); // NORMAL or RETURNED 5385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK_CONDITION(s->length >= min_pages); 5395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK_CONDITION(s->length <= max_pages); 5405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK_CONDITION(GetDescriptor(s->start) == s); 5415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK_CONDITION(GetDescriptor(s->start+s->length-1) == s); 5425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 5445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 5455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} // namespace tcmalloc 547