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 #include <stdint.h> 49 #include <string.h> 50 #include "wtf/Assertions.h" 51 52 // Single-level array 53 template <int BITS> 54 class 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 94 template <int BITS> 95 class 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 template<class Visitor, class MemoryReader> 158 void visitValues(Visitor& visitor, const MemoryReader& reader) 159 { 160 for (int i = 0; i < ROOT_LENGTH; i++) { 161 if (!root_[i]) 162 continue; 163 164 Leaf* l = reader(reinterpret_cast<Leaf*>(root_[i])); 165 for (int j = 0; j < LEAF_LENGTH; j += visitor.visit(l->values[j])) 166 ; 167 } 168 } 169 170 template<class Visitor, class MemoryReader> 171 void visitAllocations(Visitor& visitor, const MemoryReader&) { 172 for (int i = 0; i < ROOT_LENGTH; i++) { 173 if (root_[i]) 174 visitor.visit(root_[i], sizeof(Leaf)); 175 } 176 } 177 }; 178 179 // Three-level radix tree 180 template <int BITS> 181 class TCMalloc_PageMap3 { 182 private: 183 // How many bits should we consume at each interior level 184 static const int INTERIOR_BITS = (BITS + 2) / 3; // Round-up 185 static const int INTERIOR_LENGTH = 1 << INTERIOR_BITS; 186 187 // How many bits should we consume at leaf level 188 static const int LEAF_BITS = BITS - 2*INTERIOR_BITS; 189 static const int LEAF_LENGTH = 1 << LEAF_BITS; 190 191 // Interior node 192 struct Node { 193 Node* ptrs[INTERIOR_LENGTH]; 194 }; 195 196 // Leaf node 197 struct Leaf { 198 void* values[LEAF_LENGTH]; 199 }; 200 201 Node* root_; // Root of radix tree 202 void* (*allocator_)(size_t); // Memory allocator 203 204 Node* NewNode() { 205 Node* result = reinterpret_cast<Node*>((*allocator_)(sizeof(Node))); 206 if (result != NULL) { 207 memset(result, 0, sizeof(*result)); 208 } 209 return result; 210 } 211 212 public: 213 typedef uintptr_t Number; 214 215 void init(void* (*allocator)(size_t)) { 216 allocator_ = allocator; 217 root_ = NewNode(); 218 } 219 220 void* get(Number k) const { 221 ASSERT(k >> BITS == 0); 222 const Number i1 = k >> (LEAF_BITS + INTERIOR_BITS); 223 const Number i2 = (k >> LEAF_BITS) & (INTERIOR_LENGTH-1); 224 const Number i3 = k & (LEAF_LENGTH-1); 225 return reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2])->values[i3]; 226 } 227 228 void set(Number k, void* v) { 229 ASSERT(k >> BITS == 0); 230 const Number i1 = k >> (LEAF_BITS + INTERIOR_BITS); 231 const Number i2 = (k >> LEAF_BITS) & (INTERIOR_LENGTH-1); 232 const Number i3 = k & (LEAF_LENGTH-1); 233 reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2])->values[i3] = v; 234 } 235 236 bool Ensure(Number start, size_t n) { 237 for (Number key = start; key <= start + n - 1; ) { 238 const Number i1 = key >> (LEAF_BITS + INTERIOR_BITS); 239 const Number i2 = (key >> LEAF_BITS) & (INTERIOR_LENGTH-1); 240 241 // Make 2nd level node if necessary 242 if (root_->ptrs[i1] == NULL) { 243 Node* n = NewNode(); 244 if (n == NULL) return false; 245 root_->ptrs[i1] = n; 246 } 247 248 // Make leaf node if necessary 249 if (root_->ptrs[i1]->ptrs[i2] == NULL) { 250 Leaf* leaf = reinterpret_cast<Leaf*>((*allocator_)(sizeof(Leaf))); 251 if (leaf == NULL) return false; 252 memset(leaf, 0, sizeof(*leaf)); 253 root_->ptrs[i1]->ptrs[i2] = reinterpret_cast<Node*>(leaf); 254 } 255 256 // Advance key past whatever is covered by this leaf node 257 key = ((key >> LEAF_BITS) + 1) << LEAF_BITS; 258 } 259 return true; 260 } 261 262 void PreallocateMoreMemory() { 263 } 264 265 template<class Visitor, class MemoryReader> 266 void visitValues(Visitor& visitor, const MemoryReader& reader) { 267 Node* root = reader(root_); 268 for (int i = 0; i < INTERIOR_LENGTH; i++) { 269 if (!root->ptrs[i]) 270 continue; 271 272 Node* n = reader(root->ptrs[i]); 273 for (int j = 0; j < INTERIOR_LENGTH; j++) { 274 if (!n->ptrs[j]) 275 continue; 276 277 Leaf* l = reader(reinterpret_cast<Leaf*>(n->ptrs[j])); 278 for (int k = 0; k < LEAF_LENGTH; k += visitor.visit(l->values[k])) 279 ; 280 } 281 } 282 } 283 284 template<class Visitor, class MemoryReader> 285 void visitAllocations(Visitor& visitor, const MemoryReader& reader) { 286 visitor.visit(root_, sizeof(Node)); 287 288 Node* root = reader(root_); 289 for (int i = 0; i < INTERIOR_LENGTH; i++) { 290 if (!root->ptrs[i]) 291 continue; 292 293 visitor.visit(root->ptrs[i], sizeof(Node)); 294 Node* n = reader(root->ptrs[i]); 295 for (int j = 0; j < INTERIOR_LENGTH; j++) { 296 if (!n->ptrs[j]) 297 continue; 298 299 visitor.visit(n->ptrs[j], sizeof(Leaf)); 300 } 301 } 302 } 303 }; 304 305 #endif // TCMALLOC_PAGEMAP_H__ 306
