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