blob: 99bdc400e7299a81edd1306e68da82769f09ab0c [file] [log] [blame]
// 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__
#if HAVE(STDINT_H)
#include <stdint.h>
#elif HAVE(INTTYPES_H)
#include <inttypes.h>
#else
#include <sys/types.h>
#endif
#include <string.h>
#include "Assertions.h"
// Single-level array
template <int BITS>
class TCMalloc_PageMap1 {
private:
void** array_;
public:
typedef uintptr_t Number;
void init(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, size_t) {
// Nothing to do since flat array was allocate at start
return true;
}
void PreallocateMoreMemory() {}
// REQUIRES "k" is in range "[0,2^BITS-1]".
// REQUIRES "k" has been ensured before.
//
// Return the current value for KEY. Returns "Value()" if not
// yet set.
void* get(Number k) const {
return array_[k];
}
// REQUIRES "k" is in range "[0,2^BITS-1]".
// REQUIRES "k" has been ensured before.
//
// Sets the value for KEY.
void set(Number k, void* v) {
array_[k] = v;
}
};
// 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;
void init(void* (*allocator)(size_t)) {
allocator_ = allocator;
memset(root_, 0, sizeof(root_));
}
void* get(Number k) const {
ASSERT(k >> BITS == 0);
const Number i1 = k >> LEAF_BITS;
const Number i2 = k & (LEAF_LENGTH-1);
return root_[i1]->values[i2];
}
void set(Number k, void* v) {
ASSERT(k >> BITS == 0);
const Number i1 = k >> LEAF_BITS;
const Number i2 = k & (LEAF_LENGTH-1);
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;
// 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);
}
#ifdef WTF_CHANGES
template<class Visitor, class MemoryReader>
void visitValues(Visitor& visitor, const MemoryReader& reader)
{
for (int i = 0; i < ROOT_LENGTH; i++) {
if (!root_[i])
continue;
Leaf* l = reader(reinterpret_cast<Leaf*>(root_[i]));
for (int j = 0; j < LEAF_LENGTH; j += visitor.visit(l->values[j]))
;
}
}
template<class Visitor, class MemoryReader>
void visitAllocations(Visitor& visitor, const MemoryReader&) {
for (int i = 0; i < ROOT_LENGTH; i++) {
if (root_[i])
visitor.visit(root_[i], sizeof(Leaf));
}
}
#endif
};
// 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;
void init(void* (*allocator)(size_t)) {
allocator_ = allocator;
root_ = NewNode();
}
void* get(Number k) const {
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);
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);
// 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() {
}
#ifdef WTF_CHANGES
template<class Visitor, class MemoryReader>
void visitValues(Visitor& visitor, const MemoryReader& reader) {
Node* root = reader(root_);
for (int i = 0; i < INTERIOR_LENGTH; i++) {
if (!root->ptrs[i])
continue;
Node* n = reader(root->ptrs[i]);
for (int j = 0; j < INTERIOR_LENGTH; j++) {
if (!n->ptrs[j])
continue;
Leaf* l = reader(reinterpret_cast<Leaf*>(n->ptrs[j]));
for (int k = 0; k < LEAF_LENGTH; k += visitor.visit(l->values[k]))
;
}
}
}
template<class Visitor, class MemoryReader>
void visitAllocations(Visitor& visitor, const MemoryReader& reader) {
visitor.visit(root_, sizeof(Node));
Node* root = reader(root_);
for (int i = 0; i < INTERIOR_LENGTH; i++) {
if (!root->ptrs[i])
continue;
visitor.visit(root->ptrs[i], sizeof(Node));
Node* n = reader(root->ptrs[i]);
for (int j = 0; j < INTERIOR_LENGTH; j++) {
if (!n->ptrs[j])
continue;
visitor.visit(n->ptrs[j], sizeof(Leaf));
}
}
}
#endif
};
#endif // TCMALLOC_PAGEMAP_H__