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__