src/third_party/tcmalloc/vendor/src/pagemap.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 #include "config.h"
  49
  50 #include <stddef.h>                     // for NULL, size_t
  51 #include <string.h>                     // for memset
  52 #if defined HAVE_STDINT_H
  53 #include <stdint.h>
  54 #elif defined HAVE_INTTYPES_H
  55 #include <inttypes.h>
  56 #else
  57 #include <sys/types.h>
  58 #endif
  59 #include "internal_logging.h"  // for ASSERT
  60
  61 // Single-level array
  62 template <int BITS>
  63 class TCMalloc_PageMap1 {
  64  private:
  65   static const int LENGTH = 1 << BITS;
  66
  67   void** array_;
  68
  69  public:
  70   typedef uintptr_t Number;
  71
  72   explicit TCMalloc_PageMap1(void* (*allocator)(size_t)) {
  73     array_ = reinterpret_cast<void**>((*allocator)(sizeof(void*) << BITS));
  74     memset(array_, 0, sizeof(void*) << BITS);
  75   }
  76
  77   // Ensure that the map contains initialized entries "x .. x+n-1".
  78   // Returns true if successful, false if we could not allocate memory.
  79   bool Ensure(Number x, size_t n) {
  80     // Nothing to do since flat array was allocated at start.  All
  81     // that's left is to check for overflow (that is, we don't want to
  82     // ensure a number y where array_[y] would be an out-of-bounds
  83     // access).
  84     return n <= LENGTH - x;   // an overflow-free way to do "x + n <= LENGTH"
  85   }
  86
  87   void PreallocateMoreMemory() {}
  88
  89   // Return the current value for KEY.  Returns NULL if not yet set,
  90   // or if k is out of range.
  91   void* get(Number k) const {
  92     if ((k >> BITS) > 0) {
  93       return NULL;
  94     }
  95     return array_[k];
  96   }
  97
  98   // REQUIRES "k" is in range "[0,2^BITS-1]".
  99   // REQUIRES "k" has been ensured before.
 100   //
 101   // Sets the value 'v' for key 'k'.
 102   void set(Number k, void* v) {
 103     array_[k] = v;
 104   }
 105
 106   // Return the first non-NULL pointer found in this map for
 107   // a page number >= k.  Returns NULL if no such number is found.
 108   void* Next(Number k) const {
 109     while (k < (1 << BITS)) {
 110       if (array_[k] != NULL) return array_[k];
 111       k++;
 112     }
 113     return NULL;
 114   }
 115 };
 116
 117 // Two-level radix tree
 118 template <int BITS>
 119 class TCMalloc_PageMap2 {
 120  private:
 121   // Put 32 entries in the root and (2^BITS)/32 entries in each leaf.
 122   static const int ROOT_BITS = 5;
 123   static const int ROOT_LENGTH = 1 << ROOT_BITS;
 124
 125   static const int LEAF_BITS = BITS - ROOT_BITS;
 126   static const int LEAF_LENGTH = 1 << LEAF_BITS;
 127
 128   // Leaf node
 129   struct Leaf {
 130     void* values[LEAF_LENGTH];
 131   };
 132
 133   Leaf* root_[ROOT_LENGTH];             // Pointers to 32 child nodes
 134   void* (*allocator_)(size_t);          // Memory allocator
 135
 136  public:
 137   typedef uintptr_t Number;
 138
 139   explicit TCMalloc_PageMap2(void* (*allocator)(size_t)) {
 140     allocator_ = allocator;
 141     memset(root_, 0, sizeof(root_));
 142   }
 143
 144   void* get(Number k) const {
 145     const Number i1 = k >> LEAF_BITS;
 146     const Number i2 = k & (LEAF_LENGTH-1);
 147     if ((k >> BITS) > 0 || root_[i1] == NULL) {
 148       return NULL;
 149     }
 150     return root_[i1]->values[i2];
 151   }
 152
 153   void set(Number k, void* v) {
 154     ASSERT(k >> BITS == 0);
 155     const Number i1 = k >> LEAF_BITS;
 156     const Number i2 = k & (LEAF_LENGTH-1);
 157     root_[i1]->values[i2] = v;
 158   }
 159
 160   bool Ensure(Number start, size_t n) {
 161     for (Number key = start; key <= start + n - 1; ) {
 162       const Number i1 = key >> LEAF_BITS;
 163
 164       // Check for overflow
 165       if (i1 >= ROOT_LENGTH)
 166         return false;
 167
 168       // Make 2nd level node if necessary
 169       if (root_[i1] == NULL) {
 170         Leaf* leaf = reinterpret_cast<Leaf*>((*allocator_)(sizeof(Leaf)));
 171         if (leaf == NULL) return false;
 172         memset(leaf, 0, sizeof(*leaf));
 173         root_[i1] = leaf;
 174       }
 175
 176       // Advance key past whatever is covered by this leaf node
 177       key = ((key >> LEAF_BITS) + 1) << LEAF_BITS;
 178     }
 179     return true;
 180   }
 181
 182   void PreallocateMoreMemory() {
 183     // Allocate enough to keep track of all possible pages
 184     Ensure(0, 1 << BITS);
 185   }
 186
 187   void* Next(Number k) const {
 188     while (k < (1 << BITS)) {
 189       const Number i1 = k >> LEAF_BITS;
 190       Leaf* leaf = root_[i1];
 191       if (leaf != NULL) {
 192         // Scan forward in leaf
 193         for (Number i2 = k & (LEAF_LENGTH - 1); i2 < LEAF_LENGTH; i2++) {
 194           if (leaf->values[i2] != NULL) {
 195             return leaf->values[i2];
 196           }
 197         }
 198       }
 199       // Skip to next top-level entry
 200       k = (i1 + 1) << LEAF_BITS;
 201     }
 202     return NULL;
 203   }
 204 };
 205
 206 // Three-level radix tree
 207 template <int BITS>
 208 class TCMalloc_PageMap3 {
 209  private:
 210   // How many bits should we consume at each interior level
 211   static const int INTERIOR_BITS = (BITS + 2) / 3; // Round-up
 212   static const int INTERIOR_LENGTH = 1 << INTERIOR_BITS;
 213
 214   // How many bits should we consume at leaf level
 215   static const int LEAF_BITS = BITS - 2*INTERIOR_BITS;
 216   static const int LEAF_LENGTH = 1 << LEAF_BITS;
 217
 218   // Interior node
 219   struct Node {
 220     Node* ptrs[INTERIOR_LENGTH];
 221   };
 222
 223   // Leaf node
 224   struct Leaf {
 225     void* values[LEAF_LENGTH];
 226   };
 227
 228   Node* root_;                          // Root of radix tree
 229   void* (*allocator_)(size_t);          // Memory allocator
 230
 231   Node* NewNode() {
 232     Node* result = reinterpret_cast<Node*>((*allocator_)(sizeof(Node)));
 233     if (result != NULL) {
 234       memset(result, 0, sizeof(*result));
 235     }
 236     return result;
 237   }
 238
 239  public:
 240   typedef uintptr_t Number;
 241
 242   explicit TCMalloc_PageMap3(void* (*allocator)(size_t)) {
 243     allocator_ = allocator;
 244     root_ = NewNode();
 245   }
 246
 247   void* get(Number k) const {
 248     const Number i1 = k >> (LEAF_BITS + INTERIOR_BITS);
 249     const Number i2 = (k >> LEAF_BITS) & (INTERIOR_LENGTH-1);
 250     const Number i3 = k & (LEAF_LENGTH-1);
 251     if ((k >> BITS) > 0 ||
 252         root_->ptrs[i1] == NULL || root_->ptrs[i1]->ptrs[i2] == NULL) {
 253       return NULL;
 254     }
 255     return reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2])->values[i3];
 256   }
 257
 258   void set(Number k, void* v) {
 259     ASSERT(k >> BITS == 0);
 260     const Number i1 = k >> (LEAF_BITS + INTERIOR_BITS);
 261     const Number i2 = (k >> LEAF_BITS) & (INTERIOR_LENGTH-1);
 262     const Number i3 = k & (LEAF_LENGTH-1);
 263     reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2])->values[i3] = v;
 264   }
 265
 266   bool Ensure(Number start, size_t n) {
 267     for (Number key = start; key <= start + n - 1; ) {
 268       const Number i1 = key >> (LEAF_BITS + INTERIOR_BITS);
 269       const Number i2 = (key >> LEAF_BITS) & (INTERIOR_LENGTH-1);
 270
 271       // Check for overflow
 272       if (i1 >= INTERIOR_LENGTH || i2 >= INTERIOR_LENGTH)
 273         return false;
 274
 275       // Make 2nd level node if necessary
 276       if (root_->ptrs[i1] == NULL) {
 277         Node* n = NewNode();
 278         if (n == NULL) return false;
 279         root_->ptrs[i1] = n;
 280       }
 281
 282       // Make leaf node if necessary
 283       if (root_->ptrs[i1]->ptrs[i2] == NULL) {
 284         Leaf* leaf = reinterpret_cast<Leaf*>((*allocator_)(sizeof(Leaf)));
 285         if (leaf == NULL) return false;
 286         memset(leaf, 0, sizeof(*leaf));
 287         root_->ptrs[i1]->ptrs[i2] = reinterpret_cast<Node*>(leaf);
 288       }
 289
 290       // Advance key past whatever is covered by this leaf node
 291       key = ((key >> LEAF_BITS) + 1) << LEAF_BITS;
 292     }
 293     return true;
 294   }
 295
 296   void PreallocateMoreMemory() {
 297   }
 298
 299   void* Next(Number k) const {
 300     while (k < (Number(1) << BITS)) {
 301       const Number i1 = k >> (LEAF_BITS + INTERIOR_BITS);
 302       const Number i2 = (k >> LEAF_BITS) & (INTERIOR_LENGTH-1);
 303       if (root_->ptrs[i1] == NULL) {
 304         // Advance to next top-level entry
 305         k = (i1 + 1) << (LEAF_BITS + INTERIOR_BITS);
 306       } else {
 307         Leaf* leaf = reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2]);
 308         if (leaf != NULL) {
 309           for (Number i3 = (k & (LEAF_LENGTH-1)); i3 < LEAF_LENGTH; i3++) {
 310             if (leaf->values[i3] != NULL) {
 311               return leaf->values[i3];
 312             }
 313           }
 314         }
 315         // Advance to next interior entry
 316         k = ((k >> LEAF_BITS) + 1) << LEAF_BITS;
 317       }
 318     }
 319     return NULL;
 320   }
 321 };
 322
 323 #endif  // TCMALLOC_PAGEMAP_H_