wtf/TCPageMap.h

   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
  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.
  75   bool Ensure(Number x, size_t n) {
  76     // Nothing to do since flat array was allocate at start
  77     return true;
  78   }
  79
  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.
  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.
  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
 122   void init(void* (*allocator)(size_t)) {
 123     allocator_ = allocator;
 124     memset(root_, 0, sizeof(root_));
 125   }
 126
 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
 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
 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
 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>
 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>
 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
 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
 224   void init(void* (*allocator)(size_t)) {
 225     allocator_ = allocator;
 226     root_ = NewNode();
 227   }
 228
 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
 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
 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
 271   void PreallocateMoreMemory() {
 272   }
 273
 274 #ifdef WTF_CHANGES
 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++) {
 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>
 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__