15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright (c) 2005, 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)// A data structure used by the caching malloc. It maps from page# to 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// a pointer that contains info about that page. We use two 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// representations: one for 32-bit addresses, and another for 64 bit 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// addresses. Both representations provide the same interface. The 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// first representation is implemented as a flat array, the seconds as 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// a three-level radix tree that strips away approximately 1/3rd of 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// the bits every time. 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The BITS parameter should be the number of bits required to hold 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// a page number. E.g., with 32 bit pointers and 4K pages (i.e., 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// page offset fits in lower 12 bits), BITS == 20. 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifndef TCMALLOC_PAGEMAP_H_ 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define TCMALLOC_PAGEMAP_H_ 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "config.h" 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <stddef.h> // for NULL, size_t 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <string.h> // for memset 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#if defined HAVE_STDINT_H 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <stdint.h> 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#elif defined HAVE_INTTYPES_H 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <inttypes.h> 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#else 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <sys/types.h> 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef WIN32 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// TODO(jar): This is not needed when TCMalloc_PageMap1_LazyCommit has an API 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// supporting commit and reservation of memory. 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "common.h" 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "internal_logging.h" // for ASSERT 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Single-level array 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <int BITS> 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class TCMalloc_PageMap1 { 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private: 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const int LENGTH = 1 << BITS; 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void** array_; 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef uintptr_t Number; 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) explicit TCMalloc_PageMap1(void* (*allocator)(size_t)) { 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) array_ = reinterpret_cast<void**>((*allocator)(sizeof(void*) << BITS)); 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memset(array_, 0, sizeof(void*) << BITS); 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Ensure that the map contains initialized entries "x .. x+n-1". 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Returns true if successful, false if we could not allocate memory. 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool Ensure(Number x, size_t n) { 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Nothing to do since flat array was allocated at start. All 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // that's left is to check for overflow (that is, we don't want to 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // ensure a number y where array_[y] would be an out-of-bounds 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // access). 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return n <= LENGTH - x; // an overflow-free way to do "x + n <= LENGTH" 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void PreallocateMoreMemory() {} 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Return the current value for KEY. Returns NULL if not yet set, 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // or if k is out of range. 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void* get(Number k) const { 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if ((k >> BITS) > 0) { 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return NULL; 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return array_[k]; 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // REQUIRES "k" is in range "[0,2^BITS-1]". 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // REQUIRES "k" has been ensured before. 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Sets the value 'v' for key 'k'. 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void set(Number k, void* v) { 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) array_[k] = v; 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Return the first non-NULL pointer found in this map for 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // a page number >= k. Returns NULL if no such number is found. 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void* Next(Number k) const { 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (k < (1 << BITS)) { 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (array_[k] != NULL) return array_[k]; 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) k++; 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return NULL; 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef WIN32 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Lazy commit, single-level array. 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Very similar to PageMap1, except the page map is only committed as needed. 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Since we don't return memory to the OS, the committed portion of the map will 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// only grow, and we'll only be called to Ensure when we really grow the heap. 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// We maintain a bit map to help us deduce if we've already committed a range 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// in our map. 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <int BITS> 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class TCMalloc_PageMap1_LazyCommit { 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private: 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Dimension of our page map array_. 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const int LENGTH = 1 << BITS; 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The page map array that sits in reserved virtual space. Pages of this 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // array are committed as they are needed. For each page of virtual memory, 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // we potentially have a pointer to a span instance. 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void** array_; 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // A bit vector that allows us to deduce what pages in array_ are committed. 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Note that 2^3 = 8 bits per char, and hence the use of the magical "3" in 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // the array range gives us the effective "divide by 8". 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) char committed_[sizeof(void*) << (BITS - kPageShift - 3)]; 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Given an |index| into |array_|, find the page number in |array_| that holds 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // that element. 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t ContainingPage(size_t index) const { 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return (index * sizeof(*array_)) >> kPageShift; 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Find out if the given page_num index in array_ is in committed memory. 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool IsCommitted(size_t page_num) const { 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return committed_[page_num >> 3] & (1 << (page_num & 0x7)); 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Remember that the given page_num index in array_ is in committed memory. 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void SetCommitted(size_t page_num) { 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) committed_[page_num >> 3] |= (1 << (page_num & 0x7)); 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef uintptr_t Number; 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) explicit TCMalloc_PageMap1_LazyCommit(void* (*allocator)(size_t)) { 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // TODO(jar): We need a reservation function, but current API to this class 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // only provides an allocator. 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Get decommitted memory. We will commit as necessary. 1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t size = sizeof(*array_) << BITS; 1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) array_ = reinterpret_cast<void**>(VirtualAlloc( 1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) NULL, size, MEM_RESERVE, PAGE_READWRITE)); 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) tcmalloc::update_metadata_system_bytes(size); 1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) tcmalloc::update_metadata_unmapped_bytes(size); 1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Make sure we divided LENGTH evenly. 1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(sizeof(committed_) * 8 == (LENGTH * sizeof(*array_)) >> kPageShift); 1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Indicate that none of the pages of array_ have been committed yet. 1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memset(committed_, 0, sizeof(committed_)); 1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Ensure that the map contains initialized and committed entries in array_ to 1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // describe pages "x .. x+n-1". 1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Returns true if successful, false if we could not ensure this. 1845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If we have to commit more memory in array_ (which also clears said memory), 1855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // then we'll set some of the bits in committed_ to remember this fact. 1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Only the bits of committed_ near end-points for calls to Ensure() are ever 1875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // set, as the calls to Ensure() will never have overlapping ranges other than 1885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // at their end-points. 1895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 1905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Example: Suppose the OS allocates memory in pages including 40...50, and 1915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // later the OS allocates memory in pages 51...83. When the first allocation 1925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // of 40...50 is observed, then Ensure of (39,51) will be called. The range 1935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // shown in the arguments is extended so that tcmalloc can look to see if 1945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // adjacent pages are part of a span that can be coaleced. Later, when pages 1955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 51...83 are allocated, Ensure() will be called with arguments (50,84), 1965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // broadened again for the same reason. 1975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 1985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // After the above, we would NEVER get a call such as Ensure(45,60), as that 1995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // overlaps with the interior of prior ensured regions. We ONLY get an Ensure 2005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // call when the OS has allocated memory, and since we NEVER give memory back 2015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // to the OS, the OS can't possible allocate the same region to us twice, and 2025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // can't induce an Ensure() on an interior of previous Ensure call. 2035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 2045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Also note that OS allocations are NOT guaranteed to be consecutive (there 2055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // may be "holes" where code etc. uses the virtual addresses), or to appear in 2065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // any order, such as lowest to highest, or vice versa (as other independent 2075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // allocation systems in the process may be performing VirtualAllocations and 2085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // VirtualFrees asynchronously.) 2095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool Ensure(Number x, size_t n) { 2105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (n > LENGTH - x) 2115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; // We won't Ensure mapping for last pages in memory. 2125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(n > 0); 2135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // For a given page number in memory, calculate what page in array_ needs to 2155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // be memory resident. Note that we really only need a few bytes in array_ 2165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // for each page of virtual space we have to map, but we can only commit 2175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // whole pages of array_. For instance, a 4K page of array_ has about 1k 2185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // entries, and hence can map about 1K pages, or a total of about 4MB 2195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // typically. As a result, it is possible that the first entry in array_, 2205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // and the n'th entry in array_, will sit in the same page of array_. 2215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t first_page = ContainingPage(x); 2225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t last_page = ContainingPage(x + n - 1); 2235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Check at each boundary, to see if we need to commit at that end. Some 2255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // other neighbor may have already forced us to commit at either or both 2265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // boundaries. 2275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (IsCommitted(first_page)) { 2285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (first_page == last_page) return true; 2295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++first_page; 2305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (IsCommitted(first_page)) { 2315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (first_page == last_page) return true; 2325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++first_page; 2335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (IsCommitted(last_page)) { 2375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (first_page == last_page) return true; 2385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) --last_page; 2395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (IsCommitted(last_page)) { 2405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (first_page == last_page) return true; 2415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) --last_page; 2425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(!IsCommitted(last_page)); 2465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(!IsCommitted(first_page)); 2475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void* start = reinterpret_cast<char*>(array_) + (first_page << kPageShift); 2495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t length = (last_page - first_page + 1) << kPageShift; 2505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifndef NDEBUG 2525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Validate we are committing new sections, and hence we're not clearing any 2535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // existing data. 2545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MEMORY_BASIC_INFORMATION info = {0}; 2555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size_t result = VirtualQuery(start, &info, sizeof(info)); 2565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(result); 2575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(0 == (info.State & MEM_COMMIT)); // It starts with uncommitted. 2585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(info.RegionSize >= length); // Entire length is uncommitted. 2595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 2605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) TCMalloc_SystemCommit(start, length); 2625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) tcmalloc::update_metadata_unmapped_bytes(-length); 2635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifndef NDEBUG 2655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) result = VirtualQuery(start, &info, sizeof(info)); 2665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(result); 2675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(0 != (info.State & MEM_COMMIT)); // Now it is committed. 2685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(info.RegionSize >= length); // Entire length is committed. 2695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 2705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // As noted in the large comment/example describing this method, we will 2725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // never be called with a range of pages very much inside this |first_page| 2735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // to |last_page| range. 2745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // As a result, we only need to set bits for each end of that range, and one 2755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // page inside each end. 2765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SetCommitted(first_page); 2775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (first_page < last_page) { 2785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SetCommitted(last_page); 2795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SetCommitted(first_page + 1); // These may be duplicates now. 2805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SetCommitted(last_page - 1); 2815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 2845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // This is a premature call to get all the meta-memory allocated, so as to 2875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // avoid virtual space fragmentation. Since we pre-reserved all memory, we 2885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // don't need to do anything here (we won't fragment virtual space). 2895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void PreallocateMoreMemory() {} 2905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Return the current value for KEY. Returns NULL if not yet set, 2925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // or if k is out of range. 2935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void* get(Number k) const { 2945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if ((k >> BITS) > 0) { 2955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return NULL; 2965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return array_[k]; 2985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // REQUIRES "k" is in range "[0,2^BITS-1]". 3015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // REQUIRES "k" has been ensured before. 3025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 3035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Sets the value for KEY. 3045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void set(Number k, void* v) { 3055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) array_[k] = v; 3065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Return the first non-NULL pointer found in this map for 3085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // a page number >= k. Returns NULL if no such number is found. 3095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void* Next(Number k) const { 3105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (k < (1 << BITS)) { 3115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (array_[k] != NULL) return array_[k]; 3125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) k++; 3135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return NULL; 3155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 3175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif // WIN32 3185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Two-level radix tree 3215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <int BITS> 3225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class TCMalloc_PageMap2 { 3235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private: 3245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Put 32 entries in the root and (2^BITS)/32 entries in each leaf. 3255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const int ROOT_BITS = 5; 3265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const int ROOT_LENGTH = 1 << ROOT_BITS; 3275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const int LEAF_BITS = BITS - ROOT_BITS; 3295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const int LEAF_LENGTH = 1 << LEAF_BITS; 3305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Leaf node 3325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct Leaf { 3335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void* values[LEAF_LENGTH]; 3345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 3355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Leaf* root_[ROOT_LENGTH]; // Pointers to 32 child nodes 3375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void* (*allocator_)(size_t); // Memory allocator 3385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 3405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef uintptr_t Number; 3415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) explicit TCMalloc_PageMap2(void* (*allocator)(size_t)) { 3435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) allocator_ = allocator; 3445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memset(root_, 0, sizeof(root_)); 3455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void* get(Number k) const { 3485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Number i1 = k >> LEAF_BITS; 3495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Number i2 = k & (LEAF_LENGTH-1); 3505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if ((k >> BITS) > 0 || root_[i1] == NULL) { 3515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return NULL; 3525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return root_[i1]->values[i2]; 3545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void set(Number k, void* v) { 3575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(k >> BITS == 0); 3585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Number i1 = k >> LEAF_BITS; 3595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Number i2 = k & (LEAF_LENGTH-1); 3605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) root_[i1]->values[i2] = v; 3615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool Ensure(Number start, size_t n) { 3645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (Number key = start; key <= start + n - 1; ) { 3655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Number i1 = key >> LEAF_BITS; 3665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Check for overflow 3685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (i1 >= ROOT_LENGTH) 3695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 3705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Make 2nd level node if necessary 3725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (root_[i1] == NULL) { 3735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Leaf* leaf = reinterpret_cast<Leaf*>((*allocator_)(sizeof(Leaf))); 3745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (leaf == NULL) return false; 3755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memset(leaf, 0, sizeof(*leaf)); 3765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) root_[i1] = leaf; 3775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Advance key past whatever is covered by this leaf node 3805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) key = ((key >> LEAF_BITS) + 1) << LEAF_BITS; 3815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 3835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void PreallocateMoreMemory() { 3865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Allocate enough to keep track of all possible pages 3875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Ensure(0, 1 << BITS); 3885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void* Next(Number k) const { 3915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (k < (1 << BITS)) { 3925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Number i1 = k >> LEAF_BITS; 3935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Leaf* leaf = root_[i1]; 3945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (leaf != NULL) { 3955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Scan forward in leaf 3965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (Number i2 = k & (LEAF_LENGTH - 1); i2 < LEAF_LENGTH; i2++) { 3975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (leaf->values[i2] != NULL) { 3985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return leaf->values[i2]; 3995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Skip to next top-level entry 4035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) k = (i1 + 1) << LEAF_BITS; 4045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return NULL; 4065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 4085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Three-level radix tree 4105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)template <int BITS> 4115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class TCMalloc_PageMap3 { 4125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private: 4135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // How many bits should we consume at each interior level 4145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const int INTERIOR_BITS = (BITS + 2) / 3; // Round-up 4155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const int INTERIOR_LENGTH = 1 << INTERIOR_BITS; 4165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // How many bits should we consume at leaf level 4185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const int LEAF_BITS = BITS - 2*INTERIOR_BITS; 4195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const int LEAF_LENGTH = 1 << LEAF_BITS; 4205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Interior node 4225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct Node { 4235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Node* ptrs[INTERIOR_LENGTH]; 4245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 4255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Leaf node 4275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct Leaf { 4285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void* values[LEAF_LENGTH]; 4295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 4305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Node* root_; // Root of radix tree 4325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void* (*allocator_)(size_t); // Memory allocator 4335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Node* NewNode() { 4355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Node* result = reinterpret_cast<Node*>((*allocator_)(sizeof(Node))); 4365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (result != NULL) { 4375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memset(result, 0, sizeof(*result)); 4385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return result; 4405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 4435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) typedef uintptr_t Number; 4445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) explicit TCMalloc_PageMap3(void* (*allocator)(size_t)) { 4465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) allocator_ = allocator; 4475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) root_ = NewNode(); 4485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void* get(Number k) const { 4515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Number i1 = k >> (LEAF_BITS + INTERIOR_BITS); 4525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Number i2 = (k >> LEAF_BITS) & (INTERIOR_LENGTH-1); 4535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Number i3 = k & (LEAF_LENGTH-1); 4545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if ((k >> BITS) > 0 || 4555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) root_->ptrs[i1] == NULL || root_->ptrs[i1]->ptrs[i2] == NULL) { 4565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return NULL; 4575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2])->values[i3]; 4595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void set(Number k, void* v) { 4625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT(k >> BITS == 0); 4635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Number i1 = k >> (LEAF_BITS + INTERIOR_BITS); 4645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Number i2 = (k >> LEAF_BITS) & (INTERIOR_LENGTH-1); 4655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Number i3 = k & (LEAF_LENGTH-1); 4665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2])->values[i3] = v; 4675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool Ensure(Number start, size_t n) { 4705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (Number key = start; key <= start + n - 1; ) { 4715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Number i1 = key >> (LEAF_BITS + INTERIOR_BITS); 4725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Number i2 = (key >> LEAF_BITS) & (INTERIOR_LENGTH-1); 4735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Check for overflow 4755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (i1 >= INTERIOR_LENGTH || i2 >= INTERIOR_LENGTH) 4765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return false; 4775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Make 2nd level node if necessary 4795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (root_->ptrs[i1] == NULL) { 4805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Node* n = NewNode(); 4815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (n == NULL) return false; 4825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) root_->ptrs[i1] = n; 4835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Make leaf node if necessary 4865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (root_->ptrs[i1]->ptrs[i2] == NULL) { 4875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Leaf* leaf = reinterpret_cast<Leaf*>((*allocator_)(sizeof(Leaf))); 4885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (leaf == NULL) return false; 4895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memset(leaf, 0, sizeof(*leaf)); 4905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) root_->ptrs[i1]->ptrs[i2] = reinterpret_cast<Node*>(leaf); 4915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Advance key past whatever is covered by this leaf node 4945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) key = ((key >> LEAF_BITS) + 1) << LEAF_BITS; 4955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return true; 4975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void PreallocateMoreMemory() { 5005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void* Next(Number k) const { 5035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (k < (Number(1) << BITS)) { 5045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Number i1 = k >> (LEAF_BITS + INTERIOR_BITS); 5055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Number i2 = (k >> LEAF_BITS) & (INTERIOR_LENGTH-1); 5065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (root_->ptrs[i1] == NULL) { 5075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Advance to next top-level entry 5085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) k = (i1 + 1) << (LEAF_BITS + INTERIOR_BITS); 5095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 5105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Leaf* leaf = reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2]); 5115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (leaf != NULL) { 5125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (Number i3 = (k & (LEAF_LENGTH-1)); i3 < LEAF_LENGTH; i3++) { 5135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (leaf->values[i3] != NULL) { 5145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return leaf->values[i3]; 5155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Advance to next interior entry 5195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) k = ((k >> LEAF_BITS) + 1) << LEAF_BITS; 5205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return NULL; 5235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 5255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif // TCMALLOC_PAGEMAP_H_ 527