15f1ab04193ad0130ca8204aadaceae083aca9881Feng Qian// Copyright (c) 2005, Google Inc. 28e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// All rights reserved. 38e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 48e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// Redistribution and use in source and binary forms, with or without 58e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// modification, are permitted provided that the following conditions are 68e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// met: 78e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 88e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// * Redistributions of source code must retain the above copyright 98e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// notice, this list of conditions and the following disclaimer. 108e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// * Redistributions in binary form must reproduce the above 118e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// copyright notice, this list of conditions and the following disclaimer 128e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// in the documentation and/or other materials provided with the 138e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// distribution. 148e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// * Neither the name of Google Inc. nor the names of its 158e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// contributors may be used to endorse or promote products derived from 168e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// this software without specific prior written permission. 178e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 188e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 198e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 208e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 218e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 228e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 238e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 248e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 258e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 268e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 278e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 288e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 298e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 308e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// --- 318e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// Author: Sanjay Ghemawat <opensource@google.com> 328e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 338e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// A data structure used by the caching malloc. It maps from page# to 348e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// a pointer that contains info about that page. We use two 358e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// representations: one for 32-bit addresses, and another for 64 bit 368e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// addresses. Both representations provide the same interface. The 378e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// first representation is implemented as a flat array, the seconds as 388e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// a three-level radix tree that strips away approximately 1/3rd of 398e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// the bits every time. 408e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// 418e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// The BITS parameter should be the number of bits required to hold 428e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// a page number. E.g., with 32 bit pointers and 4K pages (i.e., 438e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// page offset fits in lower 12 bits), BITS == 20. 448e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 458e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#ifndef TCMALLOC_PAGEMAP_H__ 468e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#define TCMALLOC_PAGEMAP_H__ 478e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 488e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#if HAVE(STDINT_H) 498e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#include <stdint.h> 508e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#elif HAVE(INTTYPES_H) 518e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#include <inttypes.h> 528e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#else 538e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#include <sys/types.h> 548e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif 558e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 568e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#include <string.h> 578e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#include "Assertions.h" 588e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 598e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// Single-level array 608e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projecttemplate <int BITS> 618e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projectclass TCMalloc_PageMap1 { 628e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project private: 638e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void** array_; 648e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 658e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project public: 668e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typedef uintptr_t Number; 678e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 688e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void init(void* (*allocator)(size_t)) { 698e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project array_ = reinterpret_cast<void**>((*allocator)(sizeof(void*) << BITS)); 708e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project memset(array_, 0, sizeof(void*) << BITS); 718e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 728e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 738e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Ensure that the map contains initialized entries "x .. x+n-1". 748e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Returns true if successful, false if we could not allocate memory. 755ddde30071f639962dd557c453f2ad01f8f0fd00Kristian Monsen bool Ensure(Number, size_t) { 768e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Nothing to do since flat array was allocate at start 778e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return true; 788e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 798e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 808e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void PreallocateMoreMemory() {} 818e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 828e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // REQUIRES "k" is in range "[0,2^BITS-1]". 838e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // REQUIRES "k" has been ensured before. 848e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // 858e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Return the current value for KEY. Returns "Value()" if not 868e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // yet set. 878e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void* get(Number k) const { 888e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return array_[k]; 898e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 908e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 918e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // REQUIRES "k" is in range "[0,2^BITS-1]". 928e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // REQUIRES "k" has been ensured before. 938e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // 948e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Sets the value for KEY. 958e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void set(Number k, void* v) { 968e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project array_[k] = v; 978e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 988e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project}; 998e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1008e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// Two-level radix tree 1018e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projecttemplate <int BITS> 1028e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projectclass TCMalloc_PageMap2 { 1038e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project private: 1048e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Put 32 entries in the root and (2^BITS)/32 entries in each leaf. 1058e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project static const int ROOT_BITS = 5; 1068e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project static const int ROOT_LENGTH = 1 << ROOT_BITS; 1078e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1088e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project static const int LEAF_BITS = BITS - ROOT_BITS; 1098e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project static const int LEAF_LENGTH = 1 << LEAF_BITS; 1108e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1118e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Leaf node 1128e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project struct Leaf { 1138e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void* values[LEAF_LENGTH]; 1148e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project }; 1158e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1168e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Leaf* root_[ROOT_LENGTH]; // Pointers to 32 child nodes 1178e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void* (*allocator_)(size_t); // Memory allocator 1188e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1198e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project public: 1208e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typedef uintptr_t Number; 1218e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1228e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void init(void* (*allocator)(size_t)) { 1238e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project allocator_ = allocator; 1248e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project memset(root_, 0, sizeof(root_)); 1258e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1268e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1278e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void* get(Number k) const { 1288e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(k >> BITS == 0); 1298e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project const Number i1 = k >> LEAF_BITS; 1308e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project const Number i2 = k & (LEAF_LENGTH-1); 1318e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return root_[i1]->values[i2]; 1328e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1338e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1348e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void set(Number k, void* v) { 1358e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(k >> BITS == 0); 1368e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project const Number i1 = k >> LEAF_BITS; 1378e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project const Number i2 = k & (LEAF_LENGTH-1); 1388e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project root_[i1]->values[i2] = v; 1398e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1408e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1418e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project bool Ensure(Number start, size_t n) { 1428e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project for (Number key = start; key <= start + n - 1; ) { 1438e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project const Number i1 = key >> LEAF_BITS; 1448e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1458e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Make 2nd level node if necessary 1468e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (root_[i1] == NULL) { 1478e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Leaf* leaf = reinterpret_cast<Leaf*>((*allocator_)(sizeof(Leaf))); 1488e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (leaf == NULL) return false; 1498e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project memset(leaf, 0, sizeof(*leaf)); 1508e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project root_[i1] = leaf; 1518e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1528e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1538e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Advance key past whatever is covered by this leaf node 1548e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project key = ((key >> LEAF_BITS) + 1) << LEAF_BITS; 1558e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1568e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return true; 1578e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1588e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1598e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void PreallocateMoreMemory() { 1608e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Allocate enough to keep track of all possible pages 1618e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Ensure(0, 1 << BITS); 1628e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1638e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1648e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#ifdef WTF_CHANGES 1658e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<class Visitor, class MemoryReader> 1668f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian void visitValues(Visitor& visitor, const MemoryReader& reader) 1678e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project { 1688e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project for (int i = 0; i < ROOT_LENGTH; i++) { 1698e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (!root_[i]) 1708e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project continue; 1718e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1728e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Leaf* l = reader(reinterpret_cast<Leaf*>(root_[i])); 1738e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project for (int j = 0; j < LEAF_LENGTH; j += visitor.visit(l->values[j])) 1748e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ; 1758e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1768e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 1778f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian 1788f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian template<class Visitor, class MemoryReader> 1798f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian void visitAllocations(Visitor& visitor, const MemoryReader&) { 1808f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian for (int i = 0; i < ROOT_LENGTH; i++) { 1818f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian if (root_[i]) 1828f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian visitor.visit(root_[i], sizeof(Leaf)); 1838f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian } 1848f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian } 1858e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif 1868e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project}; 1878e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1888e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project// Three-level radix tree 1898e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projecttemplate <int BITS> 1908e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Projectclass TCMalloc_PageMap3 { 1918e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project private: 1928e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // How many bits should we consume at each interior level 1938e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project static const int INTERIOR_BITS = (BITS + 2) / 3; // Round-up 1948e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project static const int INTERIOR_LENGTH = 1 << INTERIOR_BITS; 1958e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 1968e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // How many bits should we consume at leaf level 1978e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project static const int LEAF_BITS = BITS - 2*INTERIOR_BITS; 1988e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project static const int LEAF_LENGTH = 1 << LEAF_BITS; 1998e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2008e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Interior node 2018e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project struct Node { 2028e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Node* ptrs[INTERIOR_LENGTH]; 2038e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project }; 2048e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2058e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Leaf node 2068e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project struct Leaf { 2078e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void* values[LEAF_LENGTH]; 2088e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project }; 2098e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2108e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Node* root_; // Root of radix tree 2118e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void* (*allocator_)(size_t); // Memory allocator 2128e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2138e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Node* NewNode() { 2148e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Node* result = reinterpret_cast<Node*>((*allocator_)(sizeof(Node))); 2158e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (result != NULL) { 2168e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project memset(result, 0, sizeof(*result)); 2178e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 2188e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return result; 2198e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 2208e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2218e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project public: 2228e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project typedef uintptr_t Number; 2238e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2248e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void init(void* (*allocator)(size_t)) { 2258e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project allocator_ = allocator; 2268e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project root_ = NewNode(); 2278e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 2288e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2298e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void* get(Number k) const { 2308e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(k >> BITS == 0); 2318e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project const Number i1 = k >> (LEAF_BITS + INTERIOR_BITS); 2328e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project const Number i2 = (k >> LEAF_BITS) & (INTERIOR_LENGTH-1); 2338e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project const Number i3 = k & (LEAF_LENGTH-1); 2348e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2])->values[i3]; 2358e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 2368e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2378e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void set(Number k, void* v) { 2388e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ASSERT(k >> BITS == 0); 2398e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project const Number i1 = k >> (LEAF_BITS + INTERIOR_BITS); 2408e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project const Number i2 = (k >> LEAF_BITS) & (INTERIOR_LENGTH-1); 2418e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project const Number i3 = k & (LEAF_LENGTH-1); 2428e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2])->values[i3] = v; 2438e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 2448e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2458e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project bool Ensure(Number start, size_t n) { 2468e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project for (Number key = start; key <= start + n - 1; ) { 2478e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project const Number i1 = key >> (LEAF_BITS + INTERIOR_BITS); 2488e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project const Number i2 = (key >> LEAF_BITS) & (INTERIOR_LENGTH-1); 2498e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2508e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Make 2nd level node if necessary 2518e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (root_->ptrs[i1] == NULL) { 2528e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Node* n = NewNode(); 2538e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (n == NULL) return false; 2548e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project root_->ptrs[i1] = n; 2558e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 2568e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2578e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Make leaf node if necessary 2588e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (root_->ptrs[i1]->ptrs[i2] == NULL) { 2598e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Leaf* leaf = reinterpret_cast<Leaf*>((*allocator_)(sizeof(Leaf))); 2608e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (leaf == NULL) return false; 2618e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project memset(leaf, 0, sizeof(*leaf)); 2628e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project root_->ptrs[i1]->ptrs[i2] = reinterpret_cast<Node*>(leaf); 2638e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 2648e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2658e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project // Advance key past whatever is covered by this leaf node 2668e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project key = ((key >> LEAF_BITS) + 1) << LEAF_BITS; 2678e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 2688e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project return true; 2698e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 2708e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2718e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project void PreallocateMoreMemory() { 2728e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 2738e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2748e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#ifdef WTF_CHANGES 2758e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project template<class Visitor, class MemoryReader> 2768f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian void visitValues(Visitor& visitor, const MemoryReader& reader) { 2778e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Node* root = reader(root_); 2788e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project for (int i = 0; i < INTERIOR_LENGTH; i++) { 2798e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (!root->ptrs[i]) 2808e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project continue; 2818e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2828e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Node* n = reader(root->ptrs[i]); 2838e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project for (int j = 0; j < INTERIOR_LENGTH; j++) { 2848e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project if (!n->ptrs[j]) 2858e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project continue; 2868e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 2878e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project Leaf* l = reader(reinterpret_cast<Leaf*>(n->ptrs[j])); 2888e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project for (int k = 0; k < LEAF_LENGTH; k += visitor.visit(l->values[k])) 2898e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project ; 2908e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 2918e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 2928e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project } 2938f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian 2948f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian template<class Visitor, class MemoryReader> 2958f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian void visitAllocations(Visitor& visitor, const MemoryReader& reader) { 2968f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian visitor.visit(root_, sizeof(Node)); 2978f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian 2988f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian Node* root = reader(root_); 2998f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian for (int i = 0; i < INTERIOR_LENGTH; i++) { 3008f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian if (!root->ptrs[i]) 3018f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian continue; 3028f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian 3038f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian visitor.visit(root->ptrs[i], sizeof(Node)); 3048f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian Node* n = reader(root->ptrs[i]); 3058f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian for (int j = 0; j < INTERIOR_LENGTH; j++) { 3068f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian if (!n->ptrs[j]) 3078f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian continue; 3088f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian 3098f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian visitor.visit(n->ptrs[j], sizeof(Leaf)); 3108f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian } 3118f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian } 3128f72e70a9fd78eec56623b3a62e68f16b7b27e28Feng Qian } 3138e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif 3148e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project}; 3158e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project 3168e35f3cfc7fba1d1c829dc557ebad6409cbe16a2The Android Open Source Project#endif // TCMALLOC_PAGEMAP_H__ 317