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(Check()); 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return NULL; 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return SearchFreeAndLargeLists(n); 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)Span* PageHeap::AllocLarge(Length n) { 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // find the best span (closest to n in size). 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The following loops implements address-ordered best-fit. 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Span *best = NULL; 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Search through normal list 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (Span* span = large_.normal.next; 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) span != &large_.normal; 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) span = span->next) { 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (span->length >= n) { 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if ((best == NULL) 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) || (span->length < best->length) 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) || ((span->length == best->length) && (span->start < best->start))) { 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) best = span; 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(best->location == Span::ON_NORMAL_FREELIST); 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Search through released list in case it has a better fit 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (Span* span = large_.returned.next; 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) span != &large_.returned; 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) span = span->next) { 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (span->length >= n) { 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if ((best == NULL) 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) || (span->length < best->length) 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) || ((span->length == best->length) && (span->start < best->start))) { 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) best = span; 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(best->location == Span::ON_RETURNED_FREELIST); 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return best == NULL ? NULL : Carve(best, n); 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)Span* PageHeap::Split(Span* span, Length n) { 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(0 < n); 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(n < span->length); 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(span->location == Span::IN_USE); 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(span->sizeclass == 0); 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Event(span, 'T', n); 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int extra = span->length - n; 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Span* leftover = NewSpan(span->start + n, extra); 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(leftover->location == Span::IN_USE); 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Event(leftover, 'U', extra); 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RecordSpan(leftover); 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pagemap_.set(span->start + n - 1, span); // Update map from pageid to span 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) span->length = n; 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return leftover; 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)Span* PageHeap::Carve(Span* span, Length n) { 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(n > 0); 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(span->location != Span::IN_USE); 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int old_location = span->location; 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RemoveFromFreeList(span); 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) span->location = Span::IN_USE; 1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Event(span, 'A', n); 1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int extra = span->length - n; 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(extra >= 0); 1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (extra > 0) { 1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Span* leftover = NewSpan(span->start + n, extra); 1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) leftover->location = old_location; 1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Event(leftover, 'S', extra); 1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RecordSpan(leftover); 1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PrependToFreeList(leftover); // Skip coalescing - no candidates possible 1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) span->length = n; 1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pagemap_.set(span->start + n - 1, span); 1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(Check()); 1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return span; 1845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void PageHeap::Delete(Span* span) { 1875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(Check()); 1885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(span->location == Span::IN_USE); 1895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(span->length > 0); 1905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(GetDescriptor(span->start) == span); 1915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(GetDescriptor(span->start + span->length - 1) == span); 1925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Length n = span->length; 1935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) span->sizeclass = 0; 1945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) span->sample = 0; 1955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) span->location = Span::ON_NORMAL_FREELIST; 1965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Event(span, 'D', span->length); 1975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MergeIntoFreeList(span); // Coalesces if possible 1985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) IncrementalScavenge(n); 1995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(Check()); 2005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void PageHeap::MergeIntoFreeList(Span* span) { 2035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(span->location != Span::IN_USE); 2045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Coalesce -- we guarantee that "p" != 0, so no bounds checking 2065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // necessary. We do not bother resetting the stale pagemap 2075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // entries for the pieces we are merging together because we only 2085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // care about the pagemap entries for the boundaries. 2095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 2105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Note that only similar spans are merged together. For example, 2115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // we do not coalesce "returned" spans with "normal" spans. 2125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const PageID p = span->start; 2135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Length n = span->length; 2145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Span* prev = GetDescriptor(p-1); 2155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (prev != NULL && prev->location == span->location) { 2165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Merge preceding span into this span 2175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(prev->start + prev->length == p); 2185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Length len = prev->length; 2195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RemoveFromFreeList(prev); 2205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DeleteSpan(prev); 2215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) span->start -= len; 2225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) span->length += len; 2235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pagemap_.set(span->start, span); 2245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Event(span, 'L', len); 2255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Span* next = GetDescriptor(p+n); 2275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (next != NULL && next->location == span->location) { 2285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Merge next span into this span 2295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(next->start == p+n); 2305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Length len = next->length; 2315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RemoveFromFreeList(next); 2325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DeleteSpan(next); 2335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) span->length += len; 2345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pagemap_.set(span->start + span->length - 1, span); 2355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Event(span, 'R', len); 2365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PrependToFreeList(span); 2395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void PageHeap::PrependToFreeList(Span* span) { 2425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(span->location != Span::IN_USE); 2435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SpanList* list = (span->length < kMaxPages) ? &free_[span->length] : &large_; 2445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (span->location == Span::ON_NORMAL_FREELIST) { 2455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) stats_.free_bytes += (span->length << kPageShift); 2465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DLL_Prepend(&list->normal, span); 2475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 2485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) stats_.unmapped_bytes += (span->length << kPageShift); 2495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DLL_Prepend(&list->returned, span); 2505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void PageHeap::RemoveFromFreeList(Span* span) { 2545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(span->location != Span::IN_USE); 2555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (span->location == Span::ON_NORMAL_FREELIST) { 2565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) stats_.free_bytes -= (span->length << kPageShift); 2575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 2585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) stats_.unmapped_bytes -= (span->length << kPageShift); 2595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DLL_Remove(span); 2615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void PageHeap::IncrementalScavenge(Length n) { 2645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Fast path; not yet time to release memory 2655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) scavenge_counter_ -= n; 2665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (scavenge_counter_ >= 0) return; // Not yet time to scavenge 2675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const double rate = FLAGS_tcmalloc_release_rate; 2695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (rate <= 1e-6) { 2705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Tiny release rate means that releasing is disabled. 2715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) scavenge_counter_ = kDefaultReleaseDelay; 2725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 2735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Length released_pages = ReleaseAtLeastNPages(1); 2765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (released_pages == 0) { 2785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Nothing to scavenge, delay for a while. 2795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) scavenge_counter_ = kDefaultReleaseDelay; 2805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 2815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Compute how long to wait until we return memory. 2825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // FLAGS_tcmalloc_release_rate==1 means wait for 1000 pages 2835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // after releasing one page. 2845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const double mult = 1000.0 / rate; 2855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) double wait = mult * static_cast<double>(released_pages); 2865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (wait > kMaxReleaseDelay) { 2875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Avoid overflow and bound to reasonable range. 2885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) wait = kMaxReleaseDelay; 2895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) scavenge_counter_ = static_cast<int64_t>(wait); 2915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)Length PageHeap::ReleaseLastNormalSpan(SpanList* slist) { 2955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Span* s = slist->normal.prev; 2965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(s->location == Span::ON_NORMAL_FREELIST); 2975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RemoveFromFreeList(s); 2985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Length n = s->length; 2995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TCMalloc_SystemRelease(reinterpret_cast<void*>(s->start << kPageShift), 3005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static_cast<size_t>(s->length << kPageShift)); 3015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) s->location = Span::ON_RETURNED_FREELIST; 3025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MergeIntoFreeList(s); // Coalesces if possible. 3035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return n; 3045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)Length PageHeap::ReleaseAtLeastNPages(Length num_pages) { 3075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Length released_pages = 0; 3085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Length prev_released_pages = -1; 3095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Round robin through the lists of free spans, releasing the last 3115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // span in each list. Stop after releasing at least num_pages. 3125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (released_pages < num_pages) { 3135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (released_pages == prev_released_pages) { 3145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Last iteration of while loop made no progress. 3155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 3165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) prev_released_pages = released_pages; 3185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 0; i < kMaxPages+1 && released_pages < num_pages; 3205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) i++, release_index_++) { 3215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (release_index_ > kMaxPages) release_index_ = 0; 3225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SpanList* slist = (release_index_ == kMaxPages) ? 3235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) &large_ : &free_[release_index_]; 3245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (!DLL_IsEmpty(&slist->normal)) { 3255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Length released_len = ReleaseLastNormalSpan(slist); 3265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) released_pages += released_len; 3275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return released_pages; 3315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void PageHeap::RegisterSizeClass(Span* span, size_t sc) { 3345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Associate span object with all interior pages as well 3355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(span->location == Span::IN_USE); 3365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(GetDescriptor(span->start) == span); 3375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(GetDescriptor(span->start+span->length-1) == span); 3385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Event(span, 'C', sc); 3395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) span->sizeclass = sc; 3405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (Length i = 1; i < span->length-1; i++) { 3415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pagemap_.set(span->start+i, span); 3425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void PageHeap::GetSmallSpanStats(SmallSpanStats* result) { 3465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int s = 0; s < kMaxPages; s++) { 3475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) result->normal_length[s] = DLL_Length(&free_[s].normal); 3485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) result->returned_length[s] = DLL_Length(&free_[s].returned); 3495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void PageHeap::GetLargeSpanStats(LargeSpanStats* result) { 3535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) result->spans = 0; 3545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) result->normal_pages = 0; 3555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) result->returned_pages = 0; 3565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (Span* s = large_.normal.next; s != &large_.normal; s = s->next) { 3575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) result->normal_pages += s->length;; 3585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) result->spans++; 3595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (Span* s = large_.returned.next; s != &large_.returned; s = s->next) { 3615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) result->returned_pages += s->length; 3625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) result->spans++; 3635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool PageHeap::GetNextRange(PageID start, base::MallocRange* r) { 3675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Span* span = reinterpret_cast<Span*>(pagemap_.Next(start)); 3685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (span == NULL) { 3695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 3705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) r->address = span->start << kPageShift; 3725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) r->length = span->length << kPageShift; 3735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) r->fraction = 0; 3745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) switch (span->location) { 3755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case Span::IN_USE: 3765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) r->type = base::MallocRange::INUSE; 3775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) r->fraction = 1; 3785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (span->sizeclass > 0) { 3795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Only some of the objects in this span may be in use. 3805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const size_t osize = Static::sizemap()->class_to_size(span->sizeclass); 3815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) r->fraction = (1.0 * osize * span->refcount) / r->length; 3825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 3845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case Span::ON_NORMAL_FREELIST: 3855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) r->type = base::MallocRange::FREE; 3865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 3875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) case Span::ON_RETURNED_FREELIST: 3885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) r->type = base::MallocRange::UNMAPPED; 3895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 3905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) default: 3915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) r->type = base::MallocRange::UNKNOWN; 3925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) break; 3935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 3955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void RecordGrowth(size_t growth) { 3985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) StackTrace* t = Static::stacktrace_allocator()->New(); 3995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) t->depth = GetStackTrace(t->stack, kMaxStackDepth-1, 3); 4005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) t->size = growth; 4015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) t->stack[kMaxStackDepth-1] = reinterpret_cast<void*>(Static::growth_stacks()); 4025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Static::set_growth_stacks(t); 4035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool PageHeap::GrowHeap(Length n) { 4065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(kMaxPages >= kMinSystemAlloc); 4075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (n > kMaxValidPages) return false; 4085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Length ask = (n>kMinSystemAlloc) ? n : static_cast<Length>(kMinSystemAlloc); 4095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t actual_size; 4105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void* ptr = TCMalloc_SystemAlloc(ask << kPageShift, &actual_size, kPageSize); 4115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (ptr == NULL) { 4125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (n < ask) { 4135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Try growing just "n" pages 4145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ask = n; 4155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ptr = TCMalloc_SystemAlloc(ask << kPageShift, &actual_size, kPageSize); 4165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (ptr == NULL) return false; 4185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ask = actual_size >> kPageShift; 4205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RecordGrowth(ask << kPageShift); 4215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint64_t old_system_bytes = stats_.system_bytes; 4235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) stats_.system_bytes += (ask << kPageShift); 4245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const PageID p = reinterpret_cast<uintptr_t>(ptr) >> kPageShift; 4255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(p > 0); 4265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If we have already a lot of pages allocated, just pre allocate a bunch of 4285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // memory for the page map. This prevents fragmentation by pagemap metadata 4295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // when a program keeps allocating and freeing large blocks. 4305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (old_system_bytes < kPageMapBigAllocationThreshold 4325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) && stats_.system_bytes >= kPageMapBigAllocationThreshold) { 4335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pagemap_.PreallocateMoreMemory(); 4345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Make sure pagemap_ has entries for all of the new pages. 4375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Plus ensure one before and one after so coalescing code 4385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // does not need bounds-checking. 4395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (pagemap_.Ensure(p-1, ask+2)) { 4405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Pretend the new area is allocated and then Delete() it to cause 4415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // any necessary coalescing to occur. 4425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Span* span = NewSpan(p, ask); 4435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RecordSpan(span); 4445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Delete(span); 4455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(Check()); 4465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 4475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 4485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // We could not allocate memory within "pagemap_" 4495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // TODO: Once we can return memory to the system, return the new span 4505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 4515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool PageHeap::Check() { 4555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(free_[0].normal.next == &free_[0].normal); 4565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(free_[0].returned.next == &free_[0].returned); 4575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 4585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool PageHeap::CheckExpensive() { 4615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool result = Check(); 4625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CheckList(&large_.normal, kMaxPages, 1000000000, Span::ON_NORMAL_FREELIST); 4635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CheckList(&large_.returned, kMaxPages, 1000000000, Span::ON_RETURNED_FREELIST); 4645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (Length s = 1; s < kMaxPages; s++) { 4655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CheckList(&free_[s].normal, s, s, Span::ON_NORMAL_FREELIST); 4665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CheckList(&free_[s].returned, s, s, Span::ON_RETURNED_FREELIST); 4675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return result; 4695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)bool PageHeap::CheckList(Span* list, Length min_pages, Length max_pages, 4725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int freelist) { 4735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (Span* s = list->next; s != list; s = s->next) { 4745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK_CONDITION(s->location == freelist); // NORMAL or RETURNED 4755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK_CONDITION(s->length >= min_pages); 4765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK_CONDITION(s->length <= max_pages); 4775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK_CONDITION(GetDescriptor(s->start) == s); 4785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK_CONDITION(GetDescriptor(s->start+s->length-1) == s); 4795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 4815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} // namespace tcmalloc 484