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 #include "config.h"

    49 

    50 #if HAVE(STDINT_H)

    51 #include <stdint.h>

    52 #elif HAVE(INTTYPES_H)

    53 #include <inttypes.h>

    54 #else

    55 #include <sys/types.h>

    56 #endif

    57 

    58 #include <string.h>

    59 

    60 #include "Assertions.h"

    61 

    62 // Single-level array

    63 template <int BITS>

    64 class TCMalloc_PageMap1 {

    65  private:

    66   void** array_;

    67 

    68  public:

    69   typedef uintptr_t Number;

    70 

    71   void init(void* (*allocator)(size_t)) {

    72     array_ = reinterpret_cast<void**>((*allocator)(sizeof(void*) << BITS));

    73     memset(array_, 0, sizeof(void*) << BITS);

    74   }

    75 

    76   // Ensure that the map contains initialized entries "x .. x+n-1".

    77   // Returns true if successful, false if we could not allocate memory.

    78   bool Ensure(Number x, size_t n) {

    79     // Nothing to do since flat array was allocate at start

    80     return true;

    81   }

    82 

    83   // REQUIRES "k" is in range "[0,2^BITS-1]".

    84   // REQUIRES "k" has been ensured before.

    85   //

    86   // Return the current value for KEY.  Returns "Value()" if not

    87   // yet set.

    88   void* get(Number k) const {

    89     return array_[k];

    90   }

    91 

    92   // REQUIRES "k" is in range "[0,2^BITS-1]".

    93   // REQUIRES "k" has been ensured before.

    94   //

    95   // Sets the value for KEY.

    96   void set(Number k, void* v) {

    97     array_[k] = v;

    98   }

    99 };

   100 

   101 // Two-level radix tree

   102 template <int BITS>

   103 class TCMalloc_PageMap2 {

   104  private:

   105   // Put 32 entries in the root and (2^BITS)/32 entries in each leaf.

   106   static const int ROOT_BITS = 5;

   107   static const int ROOT_LENGTH = 1 << ROOT_BITS;

   108 

   109   static const int LEAF_BITS = BITS - ROOT_BITS;

   110   static const int LEAF_LENGTH = 1 << LEAF_BITS;

   111 

   112   // Leaf node

   113   struct Leaf {

   114     void* values[LEAF_LENGTH];

   115   };

   116 

   117   Leaf* root_[ROOT_LENGTH];             // Pointers to 32 child nodes

   118   void* (*allocator_)(size_t);          // Memory allocator

   119 

   120  public:

   121   typedef uintptr_t Number;

   122 

   123   void init(void* (*allocator)(size_t)) {

   124     allocator_ = allocator;

   125     memset(root_, 0, sizeof(root_));

   126   }

   127 

   128   void* get(Number k) const {

   129     ASSERT(k >> BITS == 0);

   130     const Number i1 = k >> LEAF_BITS;

   131     const Number i2 = k & (LEAF_LENGTH-1);

   132     return root_[i1]->values[i2];

   133   }

   134 

   135   void set(Number k, void* v) {

   136     ASSERT(k >> BITS == 0);

   137     const Number i1 = k >> LEAF_BITS;

   138     const Number i2 = k & (LEAF_LENGTH-1);

   139     root_[i1]->values[i2] = v;

   140   }

   141 

   142   bool Ensure(Number start, size_t n) {

   143     for (Number key = start; key <= start + n - 1; ) {

   144       const Number i1 = key >> LEAF_BITS;

   145 

   146       // Make 2nd level node if necessary

   147       if (root_[i1] == NULL) {

   148         Leaf* leaf = reinterpret_cast<Leaf*>((*allocator_)(sizeof(Leaf)));

   149         if (leaf == NULL) return false;

   150         memset(leaf, 0, sizeof(*leaf));

   151         root_[i1] = leaf;

   152       }

   153 

   154       // Advance key past whatever is covered by this leaf node

   155       key = ((key >> LEAF_BITS) + 1) << LEAF_BITS;

   156     }

   157     return true;

   158   }

   159 

   160 #ifdef WTF_CHANGES

   161   template<class Visitor, class MemoryReader>

   162   void visit(const Visitor& visitor, const MemoryReader& reader)

   163   {

   164     for (int i = 0; i < ROOT_LENGTH; i++) {

   165       if (!root_[i])

   166         continue;

   167 

   168       Leaf* l = reader(reinterpret_cast<Leaf*>(root_[i]));

   169       for (int j = 0; j < LEAF_LENGTH; j += visitor.visit(l->values[j]))

   170         ;

   171     }

   172   }

   173 #endif

   174 };

   175 

   176 // Three-level radix tree

   177 template <int BITS>

   178 class TCMalloc_PageMap3 {

   179  private:

   180   // How many bits should we consume at each interior level

   181   static const int INTERIOR_BITS = (BITS + 2) / 3; // Round-up

   182   static const int INTERIOR_LENGTH = 1 << INTERIOR_BITS;

   183 

   184   // How many bits should we consume at leaf level

   185   static const int LEAF_BITS = BITS - 2*INTERIOR_BITS;

   186   static const int LEAF_LENGTH = 1 << LEAF_BITS;

   187 

   188   // Interior node

   189   struct Node {

   190     Node* ptrs[INTERIOR_LENGTH];

   191   };

   192 

   193   // Leaf node

   194   struct Leaf {

   195     void* values[LEAF_LENGTH];

   196   };

   197 

   198   Node* root_;                          // Root of radix tree

   199   void* (*allocator_)(size_t);          // Memory allocator

   200 

   201   Node* NewNode() {

   202     Node* result = reinterpret_cast<Node*>((*allocator_)(sizeof(Node)));

   203     if (result != NULL) {

   204       memset(result, 0, sizeof(*result));

   205     }

   206     return result;

   207   }

   208 

   209  public:

   210   typedef uintptr_t Number;

   211 

   212   void init(void* (*allocator)(size_t)) {

   213     allocator_ = allocator;

   214     root_ = NewNode();

   215   }

   216 

   217   void* get(Number k) const {

   218     ASSERT(k >> BITS == 0);

   219     const Number i1 = k >> (LEAF_BITS + INTERIOR_BITS);

   220     const Number i2 = (k >> LEAF_BITS) & (INTERIOR_LENGTH-1);

   221     const Number i3 = k & (LEAF_LENGTH-1);

   222     return reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2])->values[i3];

   223   }

   224 

   225   void set(Number k, void* v) {

   226     ASSERT(k >> BITS == 0);

   227     const Number i1 = k >> (LEAF_BITS + INTERIOR_BITS);

   228     const Number i2 = (k >> LEAF_BITS) & (INTERIOR_LENGTH-1);

   229     const Number i3 = k & (LEAF_LENGTH-1);

   230     reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2])->values[i3] = v;

   231   }

   232 

   233   bool Ensure(Number start, size_t n) {

   234     for (Number key = start; key <= start + n - 1; ) {

   235       const Number i1 = key >> (LEAF_BITS + INTERIOR_BITS);

   236       const Number i2 = (key >> LEAF_BITS) & (INTERIOR_LENGTH-1);

   237 

   238       // Make 2nd level node if necessary

   239       if (root_->ptrs[i1] == NULL) {

   240         Node* n = NewNode();

   241         if (n == NULL) return false;

   242         root_->ptrs[i1] = n;

   243       }

   244 

   245       // Make leaf node if necessary

   246       if (root_->ptrs[i1]->ptrs[i2] == NULL) {

   247         Leaf* leaf = reinterpret_cast<Leaf*>((*allocator_)(sizeof(Leaf)));

   248         if (leaf == NULL) return false;

   249         memset(leaf, 0, sizeof(*leaf));

   250         root_->ptrs[i1]->ptrs[i2] = reinterpret_cast<Node*>(leaf);

   251       }

   252 

   253       // Advance key past whatever is covered by this leaf node

   254       key = ((key >> LEAF_BITS) + 1) << LEAF_BITS;

   255     }

   256     return true;

   257   }

   258 

   259 #ifdef WTF_CHANGES

   260   template<class Visitor, class MemoryReader>

   261   void visit(const Visitor& visitor, const MemoryReader& reader) {

   262     Node* root = reader(root_);

   263     for (int i = 0; i < INTERIOR_LENGTH; i++) {

   264       if (!root->ptrs[i])

   265         continue;

   266 

   267       Node* n = reader(root->ptrs[i]);

   268       for (int j = 0; j < INTERIOR_LENGTH; j++) {

   269         if (!n->ptrs[j])

   270           continue;

   271 

   272         Leaf* l = reader(reinterpret_cast<Leaf*>(n->ptrs[j]));

   273         for (int k = 0; k < LEAF_LENGTH; k += visitor.visit(l->values[k]))

   274           ;

   275       }

   276     }

   277   }

   278 #endif

   279 };

   280 

   281 #endif  // TCMALLOC_PAGEMAP_H__