123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324 |
- // -*- Mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*-
- // Copyright (c) 2005, Google Inc.
- // All rights reserved.
- //
- // Redistribution and use in source and binary forms, with or without
- // modification, are permitted provided that the following conditions are
- // met:
- //
- // * Redistributions of source code must retain the above copyright
- // notice, this list of conditions and the following disclaimer.
- // * Redistributions in binary form must reproduce the above
- // copyright notice, this list of conditions and the following disclaimer
- // in the documentation and/or other materials provided with the
- // distribution.
- // * Neither the name of Google Inc. nor the names of its
- // contributors may be used to endorse or promote products derived from
- // this software without specific prior written permission.
- //
- // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
- // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
- // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
- // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
- // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
- // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
- // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
- // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
- // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
- // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
- // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- // ---
- // Author: Sanjay Ghemawat <opensource@google.com>
- //
- // A data structure used by the caching malloc. It maps from page# to
- // a pointer that contains info about that page. We use two
- // representations: one for 32-bit addresses, and another for 64 bit
- // addresses. Both representations provide the same interface. The
- // first representation is implemented as a flat array, the seconds as
- // a three-level radix tree that strips away approximately 1/3rd of
- // the bits every time.
- //
- // The BITS parameter should be the number of bits required to hold
- // a page number. E.g., with 32 bit pointers and 4K pages (i.e.,
- // page offset fits in lower 12 bits), BITS == 20.
- #ifndef TCMALLOC_PAGEMAP_H_
- #define TCMALLOC_PAGEMAP_H_
- #include "config.h"
- #include <stddef.h> // for NULL, size_t
- #include <string.h> // for memset
- #if defined HAVE_STDINT_H
- #include <stdint.h>
- #elif defined HAVE_INTTYPES_H
- #include <inttypes.h>
- #else
- #include <sys/types.h>
- #endif
- #include "internal_logging.h" // for ASSERT
- // Single-level array
- template <int BITS>
- class TCMalloc_PageMap1 {
- private:
- static const int LENGTH = 1 << BITS;
- void** array_;
- public:
- typedef uintptr_t Number;
- explicit TCMalloc_PageMap1(void* (*allocator)(size_t)) {
- array_ = reinterpret_cast<void**>((*allocator)(sizeof(void*) << BITS));
- memset(array_, 0, sizeof(void*) << BITS);
- }
- // Ensure that the map contains initialized entries "x .. x+n-1".
- // Returns true if successful, false if we could not allocate memory.
- bool Ensure(Number x, size_t n) {
- // Nothing to do since flat array was allocated at start. All
- // that's left is to check for overflow (that is, we don't want to
- // ensure a number y where array_[y] would be an out-of-bounds
- // access).
- return n <= LENGTH - x; // an overflow-free way to do "x + n <= LENGTH"
- }
- void PreallocateMoreMemory() {}
- // Return the current value for KEY. Returns NULL if not yet set,
- // or if k is out of range.
- void* get(Number k) const {
- if ((k >> BITS) > 0) {
- return NULL;
- }
- return array_[k];
- }
- // REQUIRES "k" is in range "[0,2^BITS-1]".
- // REQUIRES "k" has been ensured before.
- //
- // Sets the value 'v' for key 'k'.
- void set(Number k, void* v) {
- array_[k] = v;
- }
- // Return the first non-NULL pointer found in this map for
- // a page number >= k. Returns NULL if no such number is found.
- void* Next(Number k) const {
- while (k < (1 << BITS)) {
- if (array_[k] != NULL) return array_[k];
- k++;
- }
- return NULL;
- }
- };
- // Two-level radix tree
- template <int BITS>
- class TCMalloc_PageMap2 {
- private:
- // Put 32 entries in the root and (2^BITS)/32 entries in each leaf.
- static const int ROOT_BITS = 5;
- static const int ROOT_LENGTH = 1 << ROOT_BITS;
- static const int LEAF_BITS = BITS - ROOT_BITS;
- static const int LEAF_LENGTH = 1 << LEAF_BITS;
- // Leaf node
- struct Leaf {
- void* values[LEAF_LENGTH];
- };
- Leaf* root_[ROOT_LENGTH]; // Pointers to 32 child nodes
- void* (*allocator_)(size_t); // Memory allocator
- public:
- typedef uintptr_t Number;
- explicit TCMalloc_PageMap2(void* (*allocator)(size_t)) {
- allocator_ = allocator;
- memset(root_, 0, sizeof(root_));
- }
- void* get(Number k) const {
- const Number i1 = k >> LEAF_BITS;
- const Number i2 = k & (LEAF_LENGTH-1);
- if ((k >> BITS) > 0 || root_[i1] == NULL) {
- return NULL;
- }
- return root_[i1]->values[i2];
- }
- void set(Number k, void* v) {
- const Number i1 = k >> LEAF_BITS;
- const Number i2 = k & (LEAF_LENGTH-1);
- ASSERT(i1 < ROOT_LENGTH);
- root_[i1]->values[i2] = v;
- }
- bool Ensure(Number start, size_t n) {
- for (Number key = start; key <= start + n - 1; ) {
- const Number i1 = key >> LEAF_BITS;
- // Check for overflow
- if (i1 >= ROOT_LENGTH)
- return false;
- // Make 2nd level node if necessary
- if (root_[i1] == NULL) {
- Leaf* leaf = reinterpret_cast<Leaf*>((*allocator_)(sizeof(Leaf)));
- if (leaf == NULL) return false;
- memset(leaf, 0, sizeof(*leaf));
- root_[i1] = leaf;
- }
- // Advance key past whatever is covered by this leaf node
- key = ((key >> LEAF_BITS) + 1) << LEAF_BITS;
- }
- return true;
- }
- void PreallocateMoreMemory() {
- // Allocate enough to keep track of all possible pages
- Ensure(0, 1 << BITS);
- }
- void* Next(Number k) const {
- while (k < (1 << BITS)) {
- const Number i1 = k >> LEAF_BITS;
- Leaf* leaf = root_[i1];
- if (leaf != NULL) {
- // Scan forward in leaf
- for (Number i2 = k & (LEAF_LENGTH - 1); i2 < LEAF_LENGTH; i2++) {
- if (leaf->values[i2] != NULL) {
- return leaf->values[i2];
- }
- }
- }
- // Skip to next top-level entry
- k = (i1 + 1) << LEAF_BITS;
- }
- return NULL;
- }
- };
- // Three-level radix tree
- template <int BITS>
- class TCMalloc_PageMap3 {
- private:
- // How many bits should we consume at each interior level
- static const int INTERIOR_BITS = (BITS + 2) / 3; // Round-up
- static const int INTERIOR_LENGTH = 1 << INTERIOR_BITS;
- // How many bits should we consume at leaf level
- static const int LEAF_BITS = BITS - 2*INTERIOR_BITS;
- static const int LEAF_LENGTH = 1 << LEAF_BITS;
- // Interior node
- struct Node {
- Node* ptrs[INTERIOR_LENGTH];
- };
- // Leaf node
- struct Leaf {
- void* values[LEAF_LENGTH];
- };
- Node* root_; // Root of radix tree
- void* (*allocator_)(size_t); // Memory allocator
- Node* NewNode() {
- Node* result = reinterpret_cast<Node*>((*allocator_)(sizeof(Node)));
- if (result != NULL) {
- memset(result, 0, sizeof(*result));
- }
- return result;
- }
- public:
- typedef uintptr_t Number;
- explicit TCMalloc_PageMap3(void* (*allocator)(size_t)) {
- allocator_ = allocator;
- root_ = NewNode();
- }
- void* get(Number k) const {
- const Number i1 = k >> (LEAF_BITS + INTERIOR_BITS);
- const Number i2 = (k >> LEAF_BITS) & (INTERIOR_LENGTH-1);
- const Number i3 = k & (LEAF_LENGTH-1);
- if ((k >> BITS) > 0 ||
- root_->ptrs[i1] == NULL || root_->ptrs[i1]->ptrs[i2] == NULL) {
- return NULL;
- }
- return reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2])->values[i3];
- }
- void set(Number k, void* v) {
- ASSERT(k >> BITS == 0);
- const Number i1 = k >> (LEAF_BITS + INTERIOR_BITS);
- const Number i2 = (k >> LEAF_BITS) & (INTERIOR_LENGTH-1);
- const Number i3 = k & (LEAF_LENGTH-1);
- reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2])->values[i3] = v;
- }
- bool Ensure(Number start, size_t n) {
- for (Number key = start; key <= start + n - 1; ) {
- const Number i1 = key >> (LEAF_BITS + INTERIOR_BITS);
- const Number i2 = (key >> LEAF_BITS) & (INTERIOR_LENGTH-1);
- // Check for overflow
- if (i1 >= INTERIOR_LENGTH || i2 >= INTERIOR_LENGTH)
- return false;
- // Make 2nd level node if necessary
- if (root_->ptrs[i1] == NULL) {
- Node* n = NewNode();
- if (n == NULL) return false;
- root_->ptrs[i1] = n;
- }
- // Make leaf node if necessary
- if (root_->ptrs[i1]->ptrs[i2] == NULL) {
- Leaf* leaf = reinterpret_cast<Leaf*>((*allocator_)(sizeof(Leaf)));
- if (leaf == NULL) return false;
- memset(leaf, 0, sizeof(*leaf));
- root_->ptrs[i1]->ptrs[i2] = reinterpret_cast<Node*>(leaf);
- }
- // Advance key past whatever is covered by this leaf node
- key = ((key >> LEAF_BITS) + 1) << LEAF_BITS;
- }
- return true;
- }
- void PreallocateMoreMemory() {
- }
- void* Next(Number k) const {
- while (k < (Number(1) << BITS)) {
- const Number i1 = k >> (LEAF_BITS + INTERIOR_BITS);
- const Number i2 = (k >> LEAF_BITS) & (INTERIOR_LENGTH-1);
- if (root_->ptrs[i1] == NULL) {
- // Advance to next top-level entry
- k = (i1 + 1) << (LEAF_BITS + INTERIOR_BITS);
- } else {
- Leaf* leaf = reinterpret_cast<Leaf*>(root_->ptrs[i1]->ptrs[i2]);
- if (leaf != NULL) {
- for (Number i3 = (k & (LEAF_LENGTH-1)); i3 < LEAF_LENGTH; i3++) {
- if (leaf->values[i3] != NULL) {
- return leaf->values[i3];
- }
- }
- }
- // Advance to next interior entry
- k = ((k >> LEAF_BITS) + 1) << LEAF_BITS;
- }
- }
- return NULL;
- }
- };
- #endif // TCMALLOC_PAGEMAP_H_
|