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 (at) 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 #if HAVE(STDINT_H) 49 #include <stdint.h> 50 #elif HAVE(INTTYPES_H) 51 #include <inttypes.h> 52 #else 53 #include <sys/types.h> 54 #endif 55 56 #include <string.h> 57 #include "Assertions.h" 58 59 // Single-level array 60 template <int BITS> 61 class TCMalloc_PageMap1 { 62 private: 63 void** array_; 64 65 public: 66 typedef uintptr_t Number; 67 68 void init(void* (*allocator)(size_t)) { 69 array_ = reinterpret_cast<void**>((*allocator)(sizeof(void*) << BITS)); 70 memset(array_, 0, sizeof(void*) << BITS); 71 } 72 73 // Ensure that the map contains initialized entries "x .. x+n-1". 74 // Returns true if successful, false if we could not allocate memory. 75 bool Ensure(Number, size_t) { 76 // Nothing to do since flat array was allocate at start 77 return true; 78 } 79 80 void PreallocateMoreMemory() {} 81 82 // REQUIRES "k" is in range "[0,2^BITS-1]". 83 // REQUIRES "k" has been ensured before. 84 // 85 // Return the current value for KEY. Returns "Value()" if not 86 // yet set. 87 void* get(Number k) const { 88 return array_[k]; 89 } 90 91 // REQUIRES "k" is in range "[0,2^BITS-1]". 92 // REQUIRES "k" has been ensured before. 93 // 94 // Sets the value for KEY. 95 void set(Number k, void* v) { 96 array_[k] = v; 97 } 98 }; 99 100 // Two-level radix tree 101 template <int BITS> 102 class TCMalloc_PageMap2 { 103 private: 104 // Put 32 entries in the root and (2^BITS)/32 entries in each leaf. 105 static const int ROOT_BITS = 5; 106 static const int ROOT_LENGTH = 1 << ROOT_BITS; 107 108 static const int LEAF_BITS = BITS - ROOT_BITS; 109 static const int LEAF_LENGTH = 1 << LEAF_BITS; 110 111 // Leaf node 112 struct Leaf { 113 void* values[LEAF_LENGTH]; 114 }; 115 116 Leaf* root_[ROOT_LENGTH]; // Pointers to 32 child nodes 117 void* (*allocator_)(size_t); // Memory allocator 118 119 public: 120 typedef uintptr_t Number; 121 122 void init(void* (*allocator)(size_t)) { 123 allocator_ = allocator; 124 memset(root_, 0, sizeof(root_)); 125 } 126 127 void* get(Number k) const { 128 ASSERT(k >> BITS == 0); 129 const Number i1 = k >> LEAF_BITS; 130 const Number i2 = k & (LEAF_LENGTH-1); 131 return root_[i1]->values[i2]; 132 } 133 134 void set(Number k, void* v) { 135 ASSERT(k >> BITS == 0); 136 const Number i1 = k >> LEAF_BITS; 137 const Number i2 = k & (LEAF_LENGTH-1); 138 root_[i1]->values[i2] = v; 139 } 140 141 bool Ensure(Number start, size_t n) { 142 for (Number key = start; key <= start + n - 1; ) { 143 const Number i1 = key >> LEAF_BITS; 144 145 // Make 2nd level node if necessary 146 if (root_[i1] == NULL) { 147 Leaf* leaf = reinterpret_cast<Leaf*>((*allocator_)(sizeof(Leaf))); 148 if (leaf == NULL) return false; 149 memset(leaf, 0, sizeof(*leaf)); 150 root_[i1] = leaf; 151 } 152 153 // Advance key past whatever is covered by this leaf node 154 key = ((key >> LEAF_BITS) + 1) << LEAF_BITS; 155 } 156 return true; 157 } 158 159 void PreallocateMoreMemory() { 160 // Allocate enough to keep track of all possible pages 161 Ensure(0, 1 << BITS); 162 } 163 164 #ifdef WTF_CHANGES 165 template<class Visitor, class MemoryReader> 166 void visitValues(Visitor& visitor, const MemoryReader& reader) 167 { 168 for (int i = 0; i < ROOT_LENGTH; i++) { 169 if (!root_[i]) 170 continue; 171 172 Leaf* l = reader(reinterpret_cast<Leaf*>(root_[i])); 173 for (int j = 0; j < LEAF_LENGTH; j += visitor.visit(l->values[j])) 174 ; 175 } 176 } 177 178 template<class Visitor, class MemoryReader> 179 void visitAllocations(Visitor& visitor, const MemoryReader&) { 180 for (int i = 0; i < ROOT_LENGTH; i++) { 181 if (root_[i]) 182 visitor.visit(root_[i], sizeof(Leaf)); 183 } 184 } 185 #endif 186 }; 187 188 // Three-level radix tree 189 template <int BITS> 190 class TCMalloc_PageMap3 { 191 private: 192 // How many bits should we consume at each interior level 193 static const int INTERIOR_BITS = (BITS + 2) / 3; // Round-up 194 static const int INTERIOR_LENGTH = 1 << INTERIOR_BITS; 195 196 // How many bits should we consume at leaf level 197 static const int LEAF_BITS = BITS - 2*INTERIOR_BITS; 198 static const int LEAF_LENGTH = 1 << LEAF_BITS; 199 200 // Interior node 201 struct Node { 202 Node* ptrs[INTERIOR_LENGTH]; 203 }; 204 205 // Leaf node 206 struct Leaf { 207 void* values[LEAF_LENGTH]; 208 }; 209 210 Node* root_; // Root of radix tree 211 void* (*allocator_)(size_t); // Memory allocator 212 213 Node* NewNode() { 214 Node* result = reinterpret_cast<Node*>((*allocator_)(sizeof(Node))); 215 if (result != NULL) { 216 memset(result, 0, sizeof(*result)); 217 } 218 return result; 219 } 220 221 public: 222 typedef uintptr_t Number; 223 224 void init(void* (*allocator)(size_t)) { 225 allocator_ = allocator; 226 root_ = NewNode(); 227 } 228 229 void* get(Number k) const { 230 ASSERT(k >> BITS == 0); 231 const Number i1 = k >> (LEAF_BITS + INTERIOR_BITS); 232 const Number i2 = (k >> LEAF_BITS) & (INTERIOR_LENGTH-1); 233 const Number i3 = k & (LEAF_LENGTH-1); 234 return reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2])->values[i3]; 235 } 236 237 void set(Number k, void* v) { 238 ASSERT(k >> BITS == 0); 239 const Number i1 = k >> (LEAF_BITS + INTERIOR_BITS); 240 const Number i2 = (k >> LEAF_BITS) & (INTERIOR_LENGTH-1); 241 const Number i3 = k & (LEAF_LENGTH-1); 242 reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2])->values[i3] = v; 243 } 244 245 bool Ensure(Number start, size_t n) { 246 for (Number key = start; key <= start + n - 1; ) { 247 const Number i1 = key >> (LEAF_BITS + INTERIOR_BITS); 248 const Number i2 = (key >> LEAF_BITS) & (INTERIOR_LENGTH-1); 249 250 // Make 2nd level node if necessary 251 if (root_->ptrs[i1] == NULL) { 252 Node* n = NewNode(); 253 if (n == NULL) return false; 254 root_->ptrs[i1] = n; 255 } 256 257 // Make leaf node if necessary 258 if (root_->ptrs[i1]->ptrs[i2] == NULL) { 259 Leaf* leaf = reinterpret_cast<Leaf*>((*allocator_)(sizeof(Leaf))); 260 if (leaf == NULL) return false; 261 memset(leaf, 0, sizeof(*leaf)); 262 root_->ptrs[i1]->ptrs[i2] = reinterpret_cast<Node*>(leaf); 263 } 264 265 // Advance key past whatever is covered by this leaf node 266 key = ((key >> LEAF_BITS) + 1) << LEAF_BITS; 267 } 268 return true; 269 } 270 271 void PreallocateMoreMemory() { 272 } 273 274 #ifdef WTF_CHANGES 275 template<class Visitor, class MemoryReader> 276 void visitValues(Visitor& visitor, const MemoryReader& reader) { 277 Node* root = reader(root_); 278 for (int i = 0; i < INTERIOR_LENGTH; i++) { 279 if (!root->ptrs[i]) 280 continue; 281 282 Node* n = reader(root->ptrs[i]); 283 for (int j = 0; j < INTERIOR_LENGTH; j++) { 284 if (!n->ptrs[j]) 285 continue; 286 287 Leaf* l = reader(reinterpret_cast<Leaf*>(n->ptrs[j])); 288 for (int k = 0; k < LEAF_LENGTH; k += visitor.visit(l->values[k])) 289 ; 290 } 291 } 292 } 293 294 template<class Visitor, class MemoryReader> 295 void visitAllocations(Visitor& visitor, const MemoryReader& reader) { 296 visitor.visit(root_, sizeof(Node)); 297 298 Node* root = reader(root_); 299 for (int i = 0; i < INTERIOR_LENGTH; i++) { 300 if (!root->ptrs[i]) 301 continue; 302 303 visitor.visit(root->ptrs[i], sizeof(Node)); 304 Node* n = reader(root->ptrs[i]); 305 for (int j = 0; j < INTERIOR_LENGTH; j++) { 306 if (!n->ptrs[j]) 307 continue; 308 309 visitor.visit(n->ptrs[j], sizeof(Leaf)); 310 } 311 } 312 } 313 #endif 314 }; 315 316 #endif // TCMALLOC_PAGEMAP_H__ 317
