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)#ifndef TCMALLOC_PAGE_HEAP_H_ 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define TCMALLOC_PAGE_HEAP_H_ 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <config.h> 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <stddef.h> // for size_t 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef HAVE_STDINT_H 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <stdint.h> // for uint64_t, int64_t, uint16_t 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <gperftools/malloc_extension.h> 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/basictypes.h" 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "common.h" 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "packed-cache-inl.h" 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "pagemap.h" 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "span.h" 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// We need to dllexport PageHeap just for the unittest. MSVC complains 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// that we don't dllexport the PageHeap members, but we don't need to 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// test those, so I just suppress this warning. 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef _MSC_VER 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#pragma warning(push) 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#pragma warning(disable:4251) 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This #ifdef should almost never be set. Set NO_TCMALLOC_SAMPLES if 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// you're porting to a system where you really can't get a stacktrace. 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Because we control the definition of GetStackTrace, all clients of 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// GetStackTrace should #include us rather than stacktrace.h. 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef NO_TCMALLOC_SAMPLES 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // We use #define so code compiles even if you #include stacktrace.h somehow. 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)# define GetStackTrace(stack, depth, skip) (0) 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#else 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)# include <gperftools/stacktrace.h> 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace base { 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)struct MallocRange; 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace tcmalloc { 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// ------------------------------------------------------------------------- 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Map from page-id to per-page data 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// ------------------------------------------------------------------------- 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// We use PageMap2<> for 32-bit and PageMap3<> for 64-bit machines. 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// We also use a simple one-level cache for hot PageID-to-sizeclass mappings, 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// because sometimes the sizeclass is all the information we need. 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Selector class -- general selector uses 3-level map 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <int BITS> class MapSelector { 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef TCMalloc_PageMap3<BITS-kPageShift> Type; 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef PackedCache<BITS-kPageShift, uint64_t> CacheType; 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// A two-level map for 32-bit machines 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <> class MapSelector<32> { 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef TCMalloc_PageMap2<32-kPageShift> Type; 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef PackedCache<32-kPageShift, uint16_t> CacheType; 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// ------------------------------------------------------------------------- 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Page-level allocator 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// * Eager coalescing 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Heap for page-level allocation. We allow allocating and freeing a 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// contiguous runs of pages (called a "span"). 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// ------------------------------------------------------------------------- 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class PERFTOOLS_DLL_DECL PageHeap { 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PageHeap(); 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Allocate a run of "n" pages. Returns zero if out of memory. 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Caller should not pass "n == 0" -- instead, n should have 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // been rounded up already. 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Span* New(Length n); 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Delete the span "[p, p+n-1]". 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // REQUIRES: span was returned by earlier call to New() and 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // has not yet been deleted. 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void Delete(Span* span); 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Mark an allocated span as being used for small objects of the 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // specified size-class. 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // REQUIRES: span was returned by an earlier call to New() 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // and has not yet been deleted. 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void RegisterSizeClass(Span* span, size_t sc); 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Split an allocated span into two spans: one of length "n" pages 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // followed by another span of length "span->length - n" pages. 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Modifies "*span" to point to the first span of length "n" pages. 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Returns a pointer to the second span. 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // REQUIRES: "0 < n < span->length" 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // REQUIRES: span->location == IN_USE 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // REQUIRES: span->sizeclass == 0 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Span* Split(Span* span, Length n); 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Return the descriptor for the specified page. Returns NULL if 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // this PageID was not allocated previously. 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) inline Span* GetDescriptor(PageID p) const { 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return reinterpret_cast<Span*>(pagemap_.get(p)); 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If this page heap is managing a range with starting page # >= start, 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // store info about the range in *r and return true. Else return false. 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool GetNextRange(PageID start, base::MallocRange* r); 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Page heap statistics 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct Stats { 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Stats() : system_bytes(0), free_bytes(0), unmapped_bytes(0) {} 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint64_t system_bytes; // Total bytes allocated from system 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint64_t free_bytes; // Total bytes on normal freelists 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint64_t unmapped_bytes; // Total bytes on returned freelists 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) inline Stats stats() const { return stats_; } 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct SmallSpanStats { 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // For each free list of small spans, the length (in spans) of the 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // normal and returned free lists for that size. 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int64 normal_length[kMaxPages]; 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int64 returned_length[kMaxPages]; 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void GetSmallSpanStats(SmallSpanStats* result); 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Stats for free large spans (i.e., spans with more than kMaxPages pages). 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct LargeSpanStats { 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int64 spans; // Number of such spans 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int64 normal_pages; // Combined page length of normal large spans 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int64 returned_pages; // Combined page length of unmapped spans 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void GetLargeSpanStats(LargeSpanStats* result); 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool Check(); 1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Like Check() but does some more comprehensive checking. 1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool CheckExpensive(); 1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool CheckList(Span* list, Length min_pages, Length max_pages, 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int freelist); // ON_NORMAL_FREELIST or ON_RETURNED_FREELIST 1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Try to release at least num_pages for reuse by the OS. Returns 1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // the actual number of pages released, which may be less than 1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // num_pages if there weren't enough pages to release. The result 1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // may also be larger than num_pages since page_heap might decide to 1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // release one large range instead of fragmenting it into two 1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // smaller released and unreleased ranges. 1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Length ReleaseAtLeastNPages(Length num_pages); 1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Return 0 if we have no information, or else the correct sizeclass for p. 1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Reads and writes to pagemap_cache_ do not require locking. 1845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The entries are 64 bits on 64-bit hardware and 16 bits on 1855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 32-bit hardware, and we don't mind raciness as long as each read of 1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // an entry yields a valid entry, not a partially updated entry. 1875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t GetSizeClassIfCached(PageID p) const { 1885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return pagemap_cache_.GetOrDefault(p, 0); 1895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void CacheSizeClass(PageID p, size_t cl) const { pagemap_cache_.Put(p, cl); } 1915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private: 1935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Allocates a big block of memory for the pagemap once we reach more than 1945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 128MB 1955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const size_t kPageMapBigAllocationThreshold = 128 << 20; 1965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Minimum number of pages to fetch from system at a time. Must be 1985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // significantly bigger than kBlockSize to amortize system-call 1995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // overhead, and also to reduce external fragementation. Also, we 2005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // should keep this value big because various incarnations of Linux 2015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // have small limits on the number of mmap() regions per 2025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // address-space. 2035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // REQUIRED: kMinSystemAlloc <= kMaxPages; 2045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const int kMinSystemAlloc = kMaxPages; 2055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Never delay scavenging for more than the following number of 2075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // deallocated pages. With 4K pages, this comes to 4GB of 2085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // deallocation. 2095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const int kMaxReleaseDelay = 1 << 20; 2105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If there is nothing to release, wait for so many pages before 2125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // scavenging again. With 4K pages, this comes to 1GB of memory. 2135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const int kDefaultReleaseDelay = 1 << 18; 2145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Pick the appropriate map and cache types based on pointer size 2165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef MapSelector<kAddressBits>::Type PageMap; 2175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef MapSelector<kAddressBits>::CacheType PageMapCache; 2185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) PageMap pagemap_; 2195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) mutable PageMapCache pagemap_cache_; 2205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // We segregate spans of a given size into two circular linked 2225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // lists: one for normal spans, and one for spans whose memory 2235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // has been returned to the system. 2245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct SpanList { 2255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Span normal; 2265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Span returned; 2275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 2285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // List of free spans of length >= kMaxPages 2305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SpanList large_; 2315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Array mapping from span length to a doubly linked list of free spans 2335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SpanList free_[kMaxPages]; 2345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Statistics on system, free, and unmapped bytes 2365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Stats stats_; 2375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Span* SearchFreeAndLargeLists(Length n); 2395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool GrowHeap(Length n); 2415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // REQUIRES: span->length >= n 2435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // REQUIRES: span->location != IN_USE 2445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Remove span from its free list, and move any leftover part of 2455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // span into appropriate free lists. Also update "span" to have 2465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // length exactly "n" and mark it as non-free so it can be returned 2475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // to the client. After all that, decrease free_pages_ by n and 2485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // return span. 2495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Span* Carve(Span* span, Length n); 2505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void RecordSpan(Span* span) { 2525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pagemap_.set(span->start, span); 2535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (span->length > 1) { 2545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pagemap_.set(span->start + span->length - 1, span); 2555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Allocate a large span of length == n. If successful, returns a 2595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // span of exactly the specified length. Else, returns NULL. 2605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Span* AllocLarge(Length n); 2615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Coalesce span with neighboring spans if possible, prepend to 2635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // appropriate free list, and adjust stats. 2645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void MergeIntoFreeList(Span* span); 2655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Prepends span to appropriate free list, and adjusts stats. 2675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void PrependToFreeList(Span* span); 2685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Removes span from its free list, and adjust stats. 2705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void RemoveFromFreeList(Span* span); 2715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Incrementally release some memory to the system. 2735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // IncrementalScavenge(n) is called whenever n pages are freed. 2745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void IncrementalScavenge(Length n); 2755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Release the last span on the normal portion of this list. 2775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Return the length of that span. 2785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Length ReleaseLastNormalSpan(SpanList* slist); 2795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Number of pages to deallocate before doing more scavenging 2825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int64_t scavenge_counter_; 2835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Index of last free list where we released memory to the OS. 2855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int release_index_; 2865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 2875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} // namespace tcmalloc 2895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef _MSC_VER 2915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#pragma warning(pop) 2925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 2935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif // TCMALLOC_PAGE_HEAP_H_ 295