Home | History | Annotate | Download | only in wtf
      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 #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, size_t) {
     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__
    317