1// Copyright (c) 2005, Google Inc. 2// All rights reserved. 3// 4// Redistribution and use in source and binary forms, with or without 5// modification, are permitted provided that the following conditions are 6// met: 7// 8// * Redistributions of source code must retain the above copyright 9// notice, this list of conditions and the following disclaimer. 10// * Redistributions in binary form must reproduce the above 11// copyright notice, this list of conditions and the following disclaimer 12// in the documentation and/or other materials provided with the 13// distribution. 14// * Neither the name of Google Inc. nor the names of its 15// contributors may be used to endorse or promote products derived from 16// this software without specific prior written permission. 17// 18// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 19// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 20// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 21// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 22// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 23// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 24// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 25// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 26// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 27// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 28// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 29 30// --- 31// Author: Sanjay Ghemawat <opensource@google.com> 32// 33// A data structure used by the caching malloc. It maps from page# to 34// a pointer that contains info about that page. We use two 35// representations: one for 32-bit addresses, and another for 64 bit 36// addresses. Both representations provide the same interface. The 37// first representation is implemented as a flat array, the seconds as 38// a three-level radix tree that strips away approximately 1/3rd of 39// the bits every time. 40// 41// The BITS parameter should be the number of bits required to hold 42// a page number. E.g., with 32 bit pointers and 4K pages (i.e., 43// page offset fits in lower 12 bits), BITS == 20. 44 45#ifndef TCMALLOC_PAGEMAP_H__ 46#define TCMALLOC_PAGEMAP_H__ 47 48#include <stdint.h> 49#include <string.h> 50#include <wtf/Assertions.h> 51 52// Single-level array 53template <int BITS> 54class TCMalloc_PageMap1 { 55 private: 56 void** array_; 57 58 public: 59 typedef uintptr_t Number; 60 61 void init(void* (*allocator)(size_t)) { 62 array_ = reinterpret_cast<void**>((*allocator)(sizeof(void*) << BITS)); 63 memset(array_, 0, sizeof(void*) << BITS); 64 } 65 66 // Ensure that the map contains initialized entries "x .. x+n-1". 67 // Returns true if successful, false if we could not allocate memory. 68 bool Ensure(Number, size_t) { 69 // Nothing to do since flat array was allocate at start 70 return true; 71 } 72 73 void PreallocateMoreMemory() {} 74 75 // REQUIRES "k" is in range "[0,2^BITS-1]". 76 // REQUIRES "k" has been ensured before. 77 // 78 // Return the current value for KEY. Returns "Value()" if not 79 // yet set. 80 void* get(Number k) const { 81 return array_[k]; 82 } 83 84 // REQUIRES "k" is in range "[0,2^BITS-1]". 85 // REQUIRES "k" has been ensured before. 86 // 87 // Sets the value for KEY. 88 void set(Number k, void* v) { 89 array_[k] = v; 90 } 91}; 92 93// Two-level radix tree 94template <int BITS> 95class TCMalloc_PageMap2 { 96 private: 97 // Put 32 entries in the root and (2^BITS)/32 entries in each leaf. 98 static const int ROOT_BITS = 5; 99 static const int ROOT_LENGTH = 1 << ROOT_BITS; 100 101 static const int LEAF_BITS = BITS - ROOT_BITS; 102 static const int LEAF_LENGTH = 1 << LEAF_BITS; 103 104 // Leaf node 105 struct Leaf { 106 void* values[LEAF_LENGTH]; 107 }; 108 109 Leaf* root_[ROOT_LENGTH]; // Pointers to 32 child nodes 110 void* (*allocator_)(size_t); // Memory allocator 111 112 public: 113 typedef uintptr_t Number; 114 115 void init(void* (*allocator)(size_t)) { 116 allocator_ = allocator; 117 memset(root_, 0, sizeof(root_)); 118 } 119 120 void* get(Number k) const { 121 ASSERT(k >> BITS == 0); 122 const Number i1 = k >> LEAF_BITS; 123 const Number i2 = k & (LEAF_LENGTH-1); 124 return root_[i1]->values[i2]; 125 } 126 127 void set(Number k, void* v) { 128 ASSERT(k >> BITS == 0); 129 const Number i1 = k >> LEAF_BITS; 130 const Number i2 = k & (LEAF_LENGTH-1); 131 root_[i1]->values[i2] = v; 132 } 133 134 bool Ensure(Number start, size_t n) { 135 for (Number key = start; key <= start + n - 1; ) { 136 const Number i1 = key >> LEAF_BITS; 137 138 // Make 2nd level node if necessary 139 if (root_[i1] == NULL) { 140 Leaf* leaf = reinterpret_cast<Leaf*>((*allocator_)(sizeof(Leaf))); 141 if (leaf == NULL) return false; 142 memset(leaf, 0, sizeof(*leaf)); 143 root_[i1] = leaf; 144 } 145 146 // Advance key past whatever is covered by this leaf node 147 key = ((key >> LEAF_BITS) + 1) << LEAF_BITS; 148 } 149 return true; 150 } 151 152 void PreallocateMoreMemory() { 153 // Allocate enough to keep track of all possible pages 154 Ensure(0, 1 << BITS); 155 } 156 157#ifdef WTF_CHANGES 158 template<class Visitor, class MemoryReader> 159 void visitValues(Visitor& visitor, const MemoryReader& reader) 160 { 161 const Number leafIndexMask = LEAF_LENGTH - 1; 162 163 const Number maxKey = (1l << BITS) - 1; 164 const Number invalidIndex = maxKey; 165 Number previousRootIndex = invalidIndex; 166 167 Leaf* leaf = 0; 168 169 for (Number key = 0; key < maxKey; ) { 170 const Number rootIndex = key >> LEAF_BITS; 171 const Number leafIndex = key & leafIndexMask; 172 173 if (rootIndex != previousRootIndex) { 174 if (!root_[rootIndex]) { 175 // There's no node at this index. Move on to the next index at the root level, 176 // clearing the leaf index so that we start from the beginning of the next node. 177 key += 1 << LEAF_BITS; 178 key &= ~leafIndexMask; 179 continue; 180 } 181 182 leaf = reader(root_[rootIndex]); 183 previousRootIndex = rootIndex; 184 } 185 186 key += visitor.visit(leaf->values[leafIndex]); 187 } 188 } 189 190 template<class Visitor, class MemoryReader> 191 void visitAllocations(Visitor& visitor, const MemoryReader&) { 192 for (int i = 0; i < ROOT_LENGTH; i++) { 193 if (root_[i]) 194 visitor.visit(root_[i], sizeof(Leaf)); 195 } 196 } 197#endif 198}; 199 200// Three-level radix tree 201template <int BITS> 202class TCMalloc_PageMap3 { 203 private: 204 // How many bits should we consume at each interior level 205 static const int INTERIOR_BITS = (BITS + 2) / 3; // Round-up 206 static const int INTERIOR_LENGTH = 1 << INTERIOR_BITS; 207 208 // How many bits should we consume at leaf level 209 static const int LEAF_BITS = BITS - 2*INTERIOR_BITS; 210 static const int LEAF_LENGTH = 1 << LEAF_BITS; 211 212 // Interior node 213 struct Node { 214 Node* ptrs[INTERIOR_LENGTH]; 215 }; 216 217 // Leaf node 218 struct Leaf { 219 void* values[LEAF_LENGTH]; 220 }; 221 222 Node* root_; // Root of radix tree 223 void* (*allocator_)(size_t); // Memory allocator 224 225 Node* NewNode() { 226 Node* result = reinterpret_cast<Node*>((*allocator_)(sizeof(Node))); 227 if (result != NULL) { 228 memset(result, 0, sizeof(*result)); 229 } 230 return result; 231 } 232 233 public: 234 typedef uintptr_t Number; 235 236 void init(void* (*allocator)(size_t)) { 237 allocator_ = allocator; 238 root_ = NewNode(); 239 } 240 241 void* get(Number k) const { 242 ASSERT(k >> BITS == 0); 243 const Number i1 = k >> (LEAF_BITS + INTERIOR_BITS); 244 const Number i2 = (k >> LEAF_BITS) & (INTERIOR_LENGTH-1); 245 const Number i3 = k & (LEAF_LENGTH-1); 246 return reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2])->values[i3]; 247 } 248 249 void set(Number k, void* v) { 250 ASSERT(k >> BITS == 0); 251 const Number i1 = k >> (LEAF_BITS + INTERIOR_BITS); 252 const Number i2 = (k >> LEAF_BITS) & (INTERIOR_LENGTH-1); 253 const Number i3 = k & (LEAF_LENGTH-1); 254 reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2])->values[i3] = v; 255 } 256 257 bool Ensure(Number start, size_t n) { 258 for (Number key = start; key <= start + n - 1; ) { 259 const Number i1 = key >> (LEAF_BITS + INTERIOR_BITS); 260 const Number i2 = (key >> LEAF_BITS) & (INTERIOR_LENGTH-1); 261 262 // Make 2nd level node if necessary 263 if (root_->ptrs[i1] == NULL) { 264 Node* n = NewNode(); 265 if (n == NULL) return false; 266 root_->ptrs[i1] = n; 267 } 268 269 // Make leaf node if necessary 270 if (root_->ptrs[i1]->ptrs[i2] == NULL) { 271 Leaf* leaf = reinterpret_cast<Leaf*>((*allocator_)(sizeof(Leaf))); 272 if (leaf == NULL) return false; 273 memset(leaf, 0, sizeof(*leaf)); 274 root_->ptrs[i1]->ptrs[i2] = reinterpret_cast<Node*>(leaf); 275 } 276 277 // Advance key past whatever is covered by this leaf node 278 key = ((key >> LEAF_BITS) + 1) << LEAF_BITS; 279 } 280 return true; 281 } 282 283 void PreallocateMoreMemory() { 284 } 285 286#ifdef WTF_CHANGES 287 template<class Visitor, class MemoryReader> 288 void visitValues(Visitor& visitor, const MemoryReader& reader) { 289 const Number intermediateIndexMask = (INTERIOR_LENGTH - 1) << LEAF_BITS; 290 const Number leafIndexMask = LEAF_LENGTH - 1; 291 292 const Number maxKey = (1l << BITS) - 1; 293 const Number invalidIndex = maxKey; 294 Number previousRootIndex = invalidIndex; 295 Number previousIntermediateIndex = invalidIndex; 296 297 Node* intermediateNode = 0; 298 Leaf* leaf = 0; 299 300 Node* root = reader(root_); 301 for (Number key = 0; key < maxKey; ) { 302 const Number rootIndex = key >> (LEAF_BITS + INTERIOR_BITS); 303 const Number intermediateIndex = (key & intermediateIndexMask) >> LEAF_BITS; 304 const Number leafIndex = key & leafIndexMask; 305 306 if (rootIndex != previousRootIndex) { 307 if (!root->ptrs[rootIndex]) { 308 // There's no node at this index. Move on to the next index at the root level, clearing the 309 // intermediate and leaf indices so that we start from the beginning of that next node. 310 key += 1 << (LEAF_BITS + INTERIOR_BITS); 311 key &= ~(leafIndexMask | intermediateIndexMask); 312 continue; 313 } 314 315 intermediateNode = reader(root->ptrs[rootIndex]); 316 previousRootIndex = rootIndex; 317 318 // Invalidate the previous intermediate index since we've moved on to a different node. 319 previousIntermediateIndex = invalidIndex; 320 } 321 322 if (intermediateIndex != previousIntermediateIndex) { 323 if (!intermediateNode->ptrs[intermediateIndex]) { 324 // There's no node at this index. Move on to the next index at the intermediate level, 325 // clearing the leaf index so that we start from the beginning of the next node. 326 key += 1 << LEAF_BITS; 327 key &= ~leafIndexMask; 328 continue; 329 } 330 331 leaf = reader(reinterpret_cast<Leaf*>(intermediateNode->ptrs[intermediateIndex])); 332 previousIntermediateIndex = intermediateIndex; 333 } 334 335 key += visitor.visit(leaf->values[leafIndex]); 336 } 337 } 338 339 template<class Visitor, class MemoryReader> 340 void visitAllocations(Visitor& visitor, const MemoryReader& reader) { 341 visitor.visit(root_, sizeof(Node)); 342 343 Node* root = reader(root_); 344 for (int i = 0; i < INTERIOR_LENGTH; i++) { 345 if (!root->ptrs[i]) 346 continue; 347 348 visitor.visit(root->ptrs[i], sizeof(Node)); 349 Node* n = reader(root->ptrs[i]); 350 for (int j = 0; j < INTERIOR_LENGTH; j++) { 351 if (!n->ptrs[j]) 352 continue; 353 354 visitor.visit(n->ptrs[j], sizeof(Leaf)); 355 } 356 } 357 } 358#endif 359}; 360 361#endif // TCMALLOC_PAGEMAP_H__ 362