• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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@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 
init(void * (* allocator)(size_t))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.
Ensure(Number x,size_t n)75   bool Ensure(Number x, size_t n) {
76     // Nothing to do since flat array was allocate at start
77     return true;
78   }
79 
PreallocateMoreMemory()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.
get(Number k)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.
set(Number k,void * v)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 
init(void * (* allocator)(size_t))122   void init(void* (*allocator)(size_t)) {
123     allocator_ = allocator;
124     memset(root_, 0, sizeof(root_));
125   }
126 
get(Number k)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 
set(Number k,void * v)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 
Ensure(Number start,size_t n)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 
PreallocateMoreMemory()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>
visitValues(Visitor & visitor,const MemoryReader & reader)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>
visitAllocations(Visitor & visitor,const 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 
NewNode()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 
init(void * (* allocator)(size_t))224   void init(void* (*allocator)(size_t)) {
225     allocator_ = allocator;
226     root_ = NewNode();
227   }
228 
get(Number k)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 
set(Number k,void * v)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 
Ensure(Number start,size_t n)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 
PreallocateMoreMemory()271   void PreallocateMoreMemory() {
272   }
273 
274 #ifdef WTF_CHANGES
275   template<class Visitor, class MemoryReader>
visitValues(Visitor & visitor,const MemoryReader & reader)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>
visitAllocations(Visitor & visitor,const MemoryReader & reader)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