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 #include <wtf/Assertions.h>
54 class TCMalloc_PageMap1 {
59 typedef uintptr_t Number;
61 void init(void* (*allocator)(size_t)) {
62 array_ = reinterpret_cast<void**>((*allocator)(sizeof(void*) << BITS));
63 memset(array_, 0, sizeof(void*) << BITS);
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
73 void PreallocateMoreMemory() {}
75 // REQUIRES "k" is in range "[0,2^BITS-1]".
76 // REQUIRES "k" has been ensured before.
78 // Return the current value for KEY. Returns "Value()" if not
80 void* get(Number k) const {
84 // REQUIRES "k" is in range "[0,2^BITS-1]".
85 // REQUIRES "k" has been ensured before.
87 // Sets the value for KEY.
88 void set(Number k, void* v) {
93 // Two-level radix tree
95 class TCMalloc_PageMap2 {
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;
101 static const int LEAF_BITS = BITS - ROOT_BITS;
102 static const int LEAF_LENGTH = 1 << LEAF_BITS;
106 void* values[LEAF_LENGTH];
109 Leaf* root_[ROOT_LENGTH]; // Pointers to 32 child nodes
110 void* (*allocator_)(size_t); // Memory allocator
113 typedef uintptr_t Number;
115 void init(void* (*allocator)(size_t)) {
116 allocator_ = allocator;
117 memset(root_, 0, sizeof(root_));
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];
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;
134 bool Ensure(Number start, size_t n) {
135 for (Number key = start; key <= start + n - 1; ) {
136 const Number i1 = key >> LEAF_BITS;
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));
146 // Advance key past whatever is covered by this leaf node
147 key = ((key >> LEAF_BITS) + 1) << LEAF_BITS;
152 void PreallocateMoreMemory() {
153 // Allocate enough to keep track of all possible pages
154 Ensure(0, 1 << BITS);
158 template<class Visitor, class MemoryReader>
159 void visitValues(Visitor& visitor, const MemoryReader& reader)
161 for (int i = 0; i < ROOT_LENGTH; i++) {
165 Leaf* l = reader(reinterpret_cast<Leaf*>(root_[i]));
166 for (int j = 0; j < LEAF_LENGTH; j += visitor.visit(l->values[j]))
171 template<class Visitor, class MemoryReader>
172 void visitAllocations(Visitor& visitor, const MemoryReader&) {
173 for (int i = 0; i < ROOT_LENGTH; i++) {
175 visitor.visit(root_[i], sizeof(Leaf));
181 // Three-level radix tree
183 class TCMalloc_PageMap3 {
185 // How many bits should we consume at each interior level
186 static const int INTERIOR_BITS = (BITS + 2) / 3; // Round-up
187 static const int INTERIOR_LENGTH = 1 << INTERIOR_BITS;
189 // How many bits should we consume at leaf level
190 static const int LEAF_BITS = BITS - 2*INTERIOR_BITS;
191 static const int LEAF_LENGTH = 1 << LEAF_BITS;
195 Node* ptrs[INTERIOR_LENGTH];
200 void* values[LEAF_LENGTH];
203 Node* root_; // Root of radix tree
204 void* (*allocator_)(size_t); // Memory allocator
207 Node* result = reinterpret_cast<Node*>((*allocator_)(sizeof(Node)));
208 if (result != NULL) {
209 memset(result, 0, sizeof(*result));
215 typedef uintptr_t Number;
217 void init(void* (*allocator)(size_t)) {
218 allocator_ = allocator;
222 void* get(Number k) const {
223 ASSERT(k >> BITS == 0);
224 const Number i1 = k >> (LEAF_BITS + INTERIOR_BITS);
225 const Number i2 = (k >> LEAF_BITS) & (INTERIOR_LENGTH-1);
226 const Number i3 = k & (LEAF_LENGTH-1);
227 return reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2])->values[i3];
230 void set(Number k, void* v) {
231 ASSERT(k >> BITS == 0);
232 const Number i1 = k >> (LEAF_BITS + INTERIOR_BITS);
233 const Number i2 = (k >> LEAF_BITS) & (INTERIOR_LENGTH-1);
234 const Number i3 = k & (LEAF_LENGTH-1);
235 reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2])->values[i3] = v;
238 bool Ensure(Number start, size_t n) {
239 for (Number key = start; key <= start + n - 1; ) {
240 const Number i1 = key >> (LEAF_BITS + INTERIOR_BITS);
241 const Number i2 = (key >> LEAF_BITS) & (INTERIOR_LENGTH-1);
243 // Make 2nd level node if necessary
244 if (root_->ptrs[i1] == NULL) {
246 if (n == NULL) return false;
250 // Make leaf node if necessary
251 if (root_->ptrs[i1]->ptrs[i2] == NULL) {
252 Leaf* leaf = reinterpret_cast<Leaf*>((*allocator_)(sizeof(Leaf)));
253 if (leaf == NULL) return false;
254 memset(leaf, 0, sizeof(*leaf));
255 root_->ptrs[i1]->ptrs[i2] = reinterpret_cast<Node*>(leaf);
258 // Advance key past whatever is covered by this leaf node
259 key = ((key >> LEAF_BITS) + 1) << LEAF_BITS;
264 void PreallocateMoreMemory() {
268 template<class Visitor, class MemoryReader>
269 void visitValues(Visitor& visitor, const MemoryReader& reader) {
270 Node* root = reader(root_);
271 for (int i = 0; i < INTERIOR_LENGTH; i++) {
275 Node* n = reader(root->ptrs[i]);
276 for (int j = 0; j < INTERIOR_LENGTH; j++) {
280 Leaf* l = reader(reinterpret_cast<Leaf*>(n->ptrs[j]));
281 for (int k = 0; k < LEAF_LENGTH; k += visitor.visit(l->values[k]))
287 template<class Visitor, class MemoryReader>
288 void visitAllocations(Visitor& visitor, const MemoryReader& reader) {
289 visitor.visit(root_, sizeof(Node));
291 Node* root = reader(root_);
292 for (int i = 0; i < INTERIOR_LENGTH; i++) {
296 visitor.visit(root->ptrs[i], sizeof(Node));
297 Node* n = reader(root->ptrs[i]);
298 for (int j = 0; j < INTERIOR_LENGTH; j++) {
302 visitor.visit(n->ptrs[j], sizeof(Leaf));
309 #endif // TCMALLOC_PAGEMAP_H__