blob: a80755c510f3120f0836303f18c07986540977cb [file] [log] [blame]
// Copyright (c) 2013 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#ifndef THIRD_PARTY_BASE_ALLOCATOR_PARTITION_ALLOCATOR_PARTITION_ALLOC_H_
#define THIRD_PARTY_BASE_ALLOCATOR_PARTITION_ALLOCATOR_PARTITION_ALLOC_H_
// DESCRIPTION
// PartitionRoot::Alloc() / PartitionRootGeneric::Alloc() and PartitionFree() /
// PartitionRootGeneric::Free() are approximately analagous to malloc() and
// free().
//
// The main difference is that a PartitionRoot / PartitionRootGeneric object
// must be supplied to these functions, representing a specific "heap partition"
// that will be used to satisfy the allocation. Different partitions are
// guaranteed to exist in separate address spaces, including being separate from
// the main system heap. If the contained objects are all freed, physical memory
// is returned to the system but the address space remains reserved.
// See PartitionAlloc.md for other security properties PartitionAlloc provides.
//
// THE ONLY LEGITIMATE WAY TO OBTAIN A PartitionRoot IS THROUGH THE
// SizeSpecificPartitionAllocator / PartitionAllocatorGeneric classes. To
// minimize the instruction count to the fullest extent possible, the
// PartitionRoot is really just a header adjacent to other data areas provided
// by the allocator class.
//
// The PartitionRoot::Alloc() variant of the API has the following caveats:
// - Allocations and frees against a single partition must be single threaded.
// - Allocations must not exceed a max size, chosen at compile-time via a
// templated parameter to PartitionAllocator.
// - Allocation sizes must be aligned to the system pointer size.
// - Allocations are bucketed exactly according to size.
//
// And for PartitionRootGeneric::Alloc():
// - Multi-threaded use against a single partition is ok; locking is handled.
// - Allocations of any arbitrary size can be handled (subject to a limit of
// INT_MAX bytes for security reasons).
// - Bucketing is by approximate size, for example an allocation of 4000 bytes
// might be placed into a 4096-byte bucket. Bucket sizes are chosen to try and
// keep worst-case waste to ~10%.
//
// The allocators are designed to be extremely fast, thanks to the following
// properties and design:
// - Just two single (reasonably predicatable) branches in the hot / fast path
// for both allocating and (significantly) freeing.
// - A minimal number of operations in the hot / fast path, with the slow paths
// in separate functions, leading to the possibility of inlining.
// - Each partition page (which is usually multiple physical pages) has a
// metadata structure which allows fast mapping of free() address to an
// underlying bucket.
// - Supports a lock-free API for fast performance in single-threaded cases.
// - The freelist for a given bucket is split across a number of partition
// pages, enabling various simple tricks to try and minimize fragmentation.
// - Fine-grained bucket sizes leading to less waste and better packing.
//
// The following security properties could be investigated in the future:
// - Per-object bucketing (instead of per-size) is mostly available at the API,
// but not used yet.
// - No randomness of freelist entries or bucket position.
// - Better checking for wild pointers in free().
// - Better freelist masking function to guarantee fault on 32-bit.
#include <limits.h>
#include <string.h>
#include "build/build_config.h"
#include "third_party/base/allocator/partition_allocator/page_allocator.h"
#include "third_party/base/allocator/partition_allocator/partition_alloc_constants.h"
#include "third_party/base/allocator/partition_allocator/partition_bucket.h"
#include "third_party/base/allocator/partition_allocator/partition_cookie.h"
#include "third_party/base/allocator/partition_allocator/partition_page.h"
#include "third_party/base/allocator/partition_allocator/partition_root_base.h"
#include "third_party/base/allocator/partition_allocator/spin_lock.h"
#include "third_party/base/base_export.h"
#include "third_party/base/bits.h"
#include "third_party/base/compiler_specific.h"
#include "third_party/base/logging.h"
#include "third_party/base/stl_util.h"
#include "third_party/base/sys_byteorder.h"
#if defined(MEMORY_TOOL_REPLACES_ALLOCATOR)
#include <stdlib.h>
#endif
namespace pdfium {
namespace base {
class PartitionStatsDumper;
enum PartitionPurgeFlags {
// Decommitting the ring list of empty pages is reasonably fast.
PartitionPurgeDecommitEmptyPages = 1 << 0,
// Discarding unused system pages is slower, because it involves walking all
// freelists in all active partition pages of all buckets >= system page
// size. It often frees a similar amount of memory to decommitting the empty
// pages, though.
PartitionPurgeDiscardUnusedSystemPages = 1 << 1,
};
// Never instantiate a PartitionRoot directly, instead use PartitionAlloc.
struct BASE_EXPORT PartitionRoot : public internal::PartitionRootBase {
PartitionRoot();
~PartitionRoot() override;
// This references the buckets OFF the edge of this struct. All uses of
// PartitionRoot must have the bucket array come right after.
//
// The PartitionAlloc templated class ensures the following is correct.
ALWAYS_INLINE internal::PartitionBucket* buckets() {
return reinterpret_cast<internal::PartitionBucket*>(this + 1);
}
ALWAYS_INLINE const internal::PartitionBucket* buckets() const {
return reinterpret_cast<const internal::PartitionBucket*>(this + 1);
}
void Init(size_t num_buckets, size_t max_allocation);
ALWAYS_INLINE void* Alloc(size_t size, const char* type_name);
ALWAYS_INLINE void* AllocFlags(int flags, size_t size, const char* type_name);
void PurgeMemory(int flags);
void DumpStats(const char* partition_name,
bool is_light_dump,
PartitionStatsDumper* dumper);
};
// Never instantiate a PartitionRootGeneric directly, instead use
// PartitionAllocatorGeneric.
struct BASE_EXPORT PartitionRootGeneric : public internal::PartitionRootBase {
PartitionRootGeneric();
~PartitionRootGeneric() override;
subtle::SpinLock lock;
// Some pre-computed constants.
size_t order_index_shifts[kBitsPerSizeT + 1] = {};
size_t order_sub_index_masks[kBitsPerSizeT + 1] = {};
// The bucket lookup table lets us map a size_t to a bucket quickly.
// The trailing +1 caters for the overflow case for very large allocation
// sizes. It is one flat array instead of a 2D array because in the 2D
// world, we'd need to index array[blah][max+1] which risks undefined
// behavior.
internal::PartitionBucket*
bucket_lookups[((kBitsPerSizeT + 1) * kGenericNumBucketsPerOrder) + 1] =
{};
internal::PartitionBucket buckets[kGenericNumBuckets] = {};
// Public API.
void Init();
ALWAYS_INLINE void* Alloc(size_t size, const char* type_name);
ALWAYS_INLINE void* AllocFlags(int flags, size_t size, const char* type_name);
ALWAYS_INLINE void Free(void* ptr);
NOINLINE void* Realloc(void* ptr, size_t new_size, const char* type_name);
// Overload that may return nullptr if reallocation isn't possible. In this
// case, |ptr| remains valid.
NOINLINE void* TryRealloc(void* ptr, size_t new_size, const char* type_name);
ALWAYS_INLINE size_t ActualSize(size_t size);
void PurgeMemory(int flags);
void DumpStats(const char* partition_name,
bool is_light_dump,
PartitionStatsDumper* partition_stats_dumper);
};
// Struct used to retrieve total memory usage of a partition. Used by
// PartitionStatsDumper implementation.
struct PartitionMemoryStats {
size_t total_mmapped_bytes; // Total bytes mmaped from the system.
size_t total_committed_bytes; // Total size of commmitted pages.
size_t total_resident_bytes; // Total bytes provisioned by the partition.
size_t total_active_bytes; // Total active bytes in the partition.
size_t total_decommittable_bytes; // Total bytes that could be decommitted.
size_t total_discardable_bytes; // Total bytes that could be discarded.
};
// Struct used to retrieve memory statistics about a partition bucket. Used by
// PartitionStatsDumper implementation.
struct PartitionBucketMemoryStats {
bool is_valid; // Used to check if the stats is valid.
bool is_direct_map; // True if this is a direct mapping; size will not be
// unique.
uint32_t bucket_slot_size; // The size of the slot in bytes.
uint32_t allocated_page_size; // Total size the partition page allocated from
// the system.
uint32_t active_bytes; // Total active bytes used in the bucket.
uint32_t resident_bytes; // Total bytes provisioned in the bucket.
uint32_t decommittable_bytes; // Total bytes that could be decommitted.
uint32_t discardable_bytes; // Total bytes that could be discarded.
uint32_t num_full_pages; // Number of pages with all slots allocated.
uint32_t num_active_pages; // Number of pages that have at least one
// provisioned slot.
uint32_t num_empty_pages; // Number of pages that are empty
// but not decommitted.
uint32_t num_decommitted_pages; // Number of pages that are empty
// and decommitted.
};
// Interface that is passed to PartitionDumpStats and
// PartitionDumpStatsGeneric for using the memory statistics.
class BASE_EXPORT PartitionStatsDumper {
public:
// Called to dump total memory used by partition, once per partition.
virtual void PartitionDumpTotals(const char* partition_name,
const PartitionMemoryStats*) = 0;
// Called to dump stats about buckets, for each bucket.
virtual void PartitionsDumpBucketStats(const char* partition_name,
const PartitionBucketMemoryStats*) = 0;
};
BASE_EXPORT void PartitionAllocGlobalInit(void (*oom_handling_function)());
class BASE_EXPORT PartitionAllocHooks {
public:
typedef void AllocationHook(void* address, size_t, const char* type_name);
typedef void FreeHook(void* address);
// To unhook, call Set*Hook with nullptr.
static void SetAllocationHook(AllocationHook* hook) {
// Chained allocation hooks are not supported. Registering a non-null
// hook when a non-null hook is already registered indicates somebody is
// trying to overwrite a hook.
CHECK(!hook || !allocation_hook_);
allocation_hook_ = hook;
}
static void SetFreeHook(FreeHook* hook) {
CHECK(!hook || !free_hook_);
free_hook_ = hook;
}
static void AllocationHookIfEnabled(void* address,
size_t size,
const char* type_name) {
AllocationHook* hook = allocation_hook_;
if (UNLIKELY(hook != nullptr))
hook(address, size, type_name);
}
static void FreeHookIfEnabled(void* address) {
FreeHook* hook = free_hook_;
if (UNLIKELY(hook != nullptr))
hook(address);
}
static void ReallocHookIfEnabled(void* old_address,
void* new_address,
size_t size,
const char* type_name) {
// Report a reallocation as a free followed by an allocation.
AllocationHook* allocation_hook = allocation_hook_;
FreeHook* free_hook = free_hook_;
if (UNLIKELY(allocation_hook && free_hook)) {
free_hook(old_address);
allocation_hook(new_address, size, type_name);
}
}
private:
// Pointers to hook functions that PartitionAlloc will call on allocation and
// free if the pointers are non-null.
static AllocationHook* allocation_hook_;
static FreeHook* free_hook_;
};
ALWAYS_INLINE void* PartitionRoot::Alloc(size_t size, const char* type_name) {
return AllocFlags(0, size, type_name);
}
ALWAYS_INLINE void* PartitionRoot::AllocFlags(int flags,
size_t size,
const char* type_name) {
#if defined(MEMORY_TOOL_REPLACES_ALLOCATOR)
void* result = malloc(size);
CHECK(result);
return result;
#else
size_t requested_size = size;
size = internal::PartitionCookieSizeAdjustAdd(size);
DCHECK(this->initialized);
size_t index = size >> kBucketShift;
DCHECK(index < this->num_buckets);
DCHECK(size == index << kBucketShift);
internal::PartitionBucket* bucket = &this->buckets()[index];
void* result = AllocFromBucket(bucket, flags, size);
PartitionAllocHooks::AllocationHookIfEnabled(result, requested_size,
type_name);
return result;
#endif // defined(MEMORY_TOOL_REPLACES_ALLOCATOR)
}
ALWAYS_INLINE bool PartitionAllocSupportsGetSize() {
#if defined(MEMORY_TOOL_REPLACES_ALLOCATOR)
return false;
#else
return true;
#endif
}
ALWAYS_INLINE size_t PartitionAllocGetSize(void* ptr) {
// No need to lock here. Only |ptr| being freed by another thread could
// cause trouble, and the caller is responsible for that not happening.
DCHECK(PartitionAllocSupportsGetSize());
ptr = internal::PartitionCookieFreePointerAdjust(ptr);
internal::PartitionPage* page = internal::PartitionPage::FromPointer(ptr);
// TODO(palmer): See if we can afford to make this a CHECK.
DCHECK(internal::PartitionRootBase::IsValidPage(page));
size_t size = page->bucket->slot_size;
return internal::PartitionCookieSizeAdjustSubtract(size);
}
ALWAYS_INLINE void PartitionFree(void* ptr) {
#if defined(MEMORY_TOOL_REPLACES_ALLOCATOR)
free(ptr);
#else
void* original_ptr = ptr;
// TODO(palmer): Check ptr alignment before continuing. Shall we do the check
// inside PartitionCookieFreePointerAdjust?
PartitionAllocHooks::FreeHookIfEnabled(original_ptr);
ptr = internal::PartitionCookieFreePointerAdjust(ptr);
internal::PartitionPage* page = internal::PartitionPage::FromPointer(ptr);
// TODO(palmer): See if we can afford to make this a CHECK.
DCHECK(internal::PartitionRootBase::IsValidPage(page));
page->Free(ptr);
#endif
}
ALWAYS_INLINE internal::PartitionBucket* PartitionGenericSizeToBucket(
PartitionRootGeneric* root,
size_t size) {
size_t order = kBitsPerSizeT - bits::CountLeadingZeroBitsSizeT(size);
// The order index is simply the next few bits after the most significant bit.
size_t order_index = (size >> root->order_index_shifts[order]) &
(kGenericNumBucketsPerOrder - 1);
// And if the remaining bits are non-zero we must bump the bucket up.
size_t sub_order_index = size & root->order_sub_index_masks[order];
internal::PartitionBucket* bucket =
root->bucket_lookups[(order << kGenericNumBucketsPerOrderBits) +
order_index + !!sub_order_index];
CHECK(bucket);
DCHECK(!bucket->slot_size || bucket->slot_size >= size);
DCHECK(!(bucket->slot_size % kGenericSmallestBucket));
return bucket;
}
ALWAYS_INLINE void* PartitionAllocGenericFlags(PartitionRootGeneric* root,
int flags,
size_t size,
const char* type_name) {
DCHECK(flags < PartitionAllocLastFlag << 1);
#if defined(MEMORY_TOOL_REPLACES_ALLOCATOR)
const bool zero_fill = flags & PartitionAllocZeroFill;
void* result = zero_fill ? calloc(1, size) : malloc(size);
CHECK(result || flags & PartitionAllocReturnNull);
return result;
#else
DCHECK(root->initialized);
size_t requested_size = size;
size = internal::PartitionCookieSizeAdjustAdd(size);
internal::PartitionBucket* bucket = PartitionGenericSizeToBucket(root, size);
void* ret = nullptr;
{
subtle::SpinLock::Guard guard(root->lock);
ret = root->AllocFromBucket(bucket, flags, size);
}
PartitionAllocHooks::AllocationHookIfEnabled(ret, requested_size, type_name);
return ret;
#endif
}
ALWAYS_INLINE void* PartitionRootGeneric::Alloc(size_t size,
const char* type_name) {
return PartitionAllocGenericFlags(this, 0, size, type_name);
}
ALWAYS_INLINE void* PartitionRootGeneric::AllocFlags(int flags,
size_t size,
const char* type_name) {
return PartitionAllocGenericFlags(this, flags, size, type_name);
}
ALWAYS_INLINE void PartitionRootGeneric::Free(void* ptr) {
#if defined(MEMORY_TOOL_REPLACES_ALLOCATOR)
free(ptr);
#else
DCHECK(this->initialized);
if (UNLIKELY(!ptr))
return;
PartitionAllocHooks::FreeHookIfEnabled(ptr);
ptr = internal::PartitionCookieFreePointerAdjust(ptr);
internal::PartitionPage* page = internal::PartitionPage::FromPointer(ptr);
// TODO(palmer): See if we can afford to make this a CHECK.
DCHECK(IsValidPage(page));
{
subtle::SpinLock::Guard guard(this->lock);
page->Free(ptr);
}
#endif
}
BASE_EXPORT void* PartitionReallocGenericFlags(PartitionRootGeneric* root,
int flags,
void* ptr,
size_t new_size,
const char* type_name);
ALWAYS_INLINE size_t PartitionRootGeneric::ActualSize(size_t size) {
#if defined(MEMORY_TOOL_REPLACES_ALLOCATOR)
return size;
#else
DCHECK(this->initialized);
size = internal::PartitionCookieSizeAdjustAdd(size);
internal::PartitionBucket* bucket = PartitionGenericSizeToBucket(this, size);
if (LIKELY(!bucket->is_direct_mapped())) {
size = bucket->slot_size;
} else if (size > kGenericMaxDirectMapped) {
// Too large to allocate => return the size unchanged.
} else {
size = internal::PartitionBucket::get_direct_map_size(size);
}
return internal::PartitionCookieSizeAdjustSubtract(size);
#endif
}
template <size_t N>
class SizeSpecificPartitionAllocator {
public:
SizeSpecificPartitionAllocator() {
memset(actual_buckets_, 0,
sizeof(internal::PartitionBucket) * pdfium::size(actual_buckets_));
}
~SizeSpecificPartitionAllocator() = default;
static const size_t kMaxAllocation = N - kAllocationGranularity;
static const size_t kNumBuckets = N / kAllocationGranularity;
void init() { partition_root_.Init(kNumBuckets, kMaxAllocation); }
ALWAYS_INLINE PartitionRoot* root() { return &partition_root_; }
private:
PartitionRoot partition_root_;
internal::PartitionBucket actual_buckets_[kNumBuckets];
};
class BASE_EXPORT PartitionAllocatorGeneric {
public:
PartitionAllocatorGeneric();
~PartitionAllocatorGeneric();
void init() { partition_root_.Init(); }
ALWAYS_INLINE PartitionRootGeneric* root() { return &partition_root_; }
private:
PartitionRootGeneric partition_root_;
};
} // namespace base
} // namespace pdfium
#endif // THIRD_PARTY_BASE_ALLOCATOR_PARTITION_ALLOCATOR_PARTITION_ALLOC_H_