1 // Copyright (c) 2005, Google Inc.
2 // All rights reserved.
4 // Redistribution and use in source and binary forms, with or without
5 // modification, are permitted provided that the following conditions are
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
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.
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.
31 // Author: Sanjay Ghemawat <opensource@google.com>
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.
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.
45 #ifndef TCMALLOC_PAGEMAP_H__
46 #define TCMALLOC_PAGEMAP_H__
50 #elif HAVE(INTTYPES_H)
53 #include <sys/types.h>
57 #include "Assertions.h"
61 class TCMalloc_PageMap1 {
66 typedef uintptr_t Number;
68 void init(void* (*allocator)(size_t)) {
69 array_ = reinterpret_cast<void**>((*allocator)(sizeof(void*) << BITS));
70 memset(array_, 0, sizeof(void*) << BITS);
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
80 void PreallocateMoreMemory() {}
82 // REQUIRES "k" is in range "[0,2^BITS-1]".
83 // REQUIRES "k" has been ensured before.
85 // Return the current value for KEY. Returns "Value()" if not
87 void* get(Number k) const {
91 // REQUIRES "k" is in range "[0,2^BITS-1]".
92 // REQUIRES "k" has been ensured before.
94 // Sets the value for KEY.
95 void set(Number k, void* v) {
100 // Two-level radix tree
102 class TCMalloc_PageMap2 {
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;
108 static const int LEAF_BITS = BITS - ROOT_BITS;
109 static const int LEAF_LENGTH = 1 << LEAF_BITS;
113 void* values[LEAF_LENGTH];
116 Leaf* root_[ROOT_LENGTH]; // Pointers to 32 child nodes
117 void* (*allocator_)(size_t); // Memory allocator
120 typedef uintptr_t Number;
122 void init(void* (*allocator)(size_t)) {
123 allocator_ = allocator;
124 memset(root_, 0, sizeof(root_));
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];
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;
141 bool Ensure(Number start, size_t n) {
142 for (Number key = start; key <= start + n - 1; ) {
143 const Number i1 = key >> LEAF_BITS;
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));
153 // Advance key past whatever is covered by this leaf node
154 key = ((key >> LEAF_BITS) + 1) << LEAF_BITS;
159 void PreallocateMoreMemory() {
160 // Allocate enough to keep track of all possible pages
161 Ensure(0, 1 << BITS);
165 template<class Visitor, class MemoryReader>
166 void visitValues(Visitor& visitor, const MemoryReader& reader)
168 for (int i = 0; i < ROOT_LENGTH; i++) {
172 Leaf* l = reader(reinterpret_cast<Leaf*>(root_[i]));
173 for (int j = 0; j < LEAF_LENGTH; j += visitor.visit(l->values[j]))
178 template<class Visitor, class MemoryReader>
179 void visitAllocations(Visitor& visitor, const MemoryReader&) {
180 for (int i = 0; i < ROOT_LENGTH; i++) {
182 visitor.visit(root_[i], sizeof(Leaf));
188 // Three-level radix tree
190 class TCMalloc_PageMap3 {
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;
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;
202 Node* ptrs[INTERIOR_LENGTH];
207 void* values[LEAF_LENGTH];
210 Node* root_; // Root of radix tree
211 void* (*allocator_)(size_t); // Memory allocator
214 Node* result = reinterpret_cast<Node*>((*allocator_)(sizeof(Node)));
215 if (result != NULL) {
216 memset(result, 0, sizeof(*result));
222 typedef uintptr_t Number;
224 void init(void* (*allocator)(size_t)) {
225 allocator_ = allocator;
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];
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;
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);
250 // Make 2nd level node if necessary
251 if (root_->ptrs[i1] == NULL) {
253 if (n == NULL) return false;
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);
265 // Advance key past whatever is covered by this leaf node
266 key = ((key >> LEAF_BITS) + 1) << LEAF_BITS;
271 void PreallocateMoreMemory() {
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++) {
282 Node* n = reader(root->ptrs[i]);
283 for (int j = 0; j < INTERIOR_LENGTH; j++) {
287 Leaf* l = reader(reinterpret_cast<Leaf*>(n->ptrs[j]));
288 for (int k = 0; k < LEAF_LENGTH; k += visitor.visit(l->values[k]))
294 template<class Visitor, class MemoryReader>
295 void visitAllocations(Visitor& visitor, const MemoryReader& reader) {
296 visitor.visit(root_, sizeof(Node));
298 Node* root = reader(root_);
299 for (int i = 0; i < INTERIOR_LENGTH; i++) {
303 visitor.visit(root->ptrs[i], sizeof(Node));
304 Node* n = reader(root->ptrs[i]);
305 for (int j = 0; j < INTERIOR_LENGTH; j++) {
309 visitor.visit(n->ptrs[j], sizeof(Leaf));
316 #endif // TCMALLOC_PAGEMAP_H__