partition_page.h | Explore in Territory

// Copyright 2018 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef PARTITION_ALLOC_PARTITION_PAGE_H_
#define PARTITION_ALLOC_PARTITION_PAGE_H_

#include <cstdint>

#include "partition_alloc/address_pool_manager.h"
#include "partition_alloc/address_pool_manager_types.h"
#include "partition_alloc/build_config.h"
#include "partition_alloc/buildflags.h"
#include "partition_alloc/freeslot_bitmap_constants.h"
#include "partition_alloc/partition_address_space.h"
#include "partition_alloc/partition_alloc_base/bits.h"
#include "partition_alloc/partition_alloc_base/compiler_specific.h"
#include "partition_alloc/partition_alloc_base/component_export.h"
#include "partition_alloc/partition_alloc_base/thread_annotations.h"
#include "partition_alloc/partition_alloc_check.h"
#include "partition_alloc/partition_alloc_config.h"
#include "partition_alloc/partition_alloc_constants.h"
#include "partition_alloc/partition_alloc_forward.h"
#include "partition_alloc/partition_bucket.h"
#include "partition_alloc/partition_dcheck_helper.h"
#include "partition_alloc/partition_freelist_entry.h"
#include "partition_alloc/partition_page_constants.h"
#include "partition_alloc/partition_superpage_extent_entry.h"
#include "partition_alloc/reservation_offset_table.h"

#if PA_BUILDFLAG(DCHECKS_ARE_ON)
#include "partition_alloc/tagging.h"
#endif

namespace partition_alloc::internal {

// Metadata of the slot span.
//
// Some notes on slot span states. It can be in one of four major states:
// 1) Active.
// 2) Full.
// 3) Empty.
// 4) Decommitted.
// An active slot span has available free slots, as well as allocated ones.
// A full slot span has no free slots. An empty slot span has no allocated
// slots, and a decommitted slot span is an empty one that had its backing
// memory released back to the system.
//
// There are three linked lists tracking slot spans. The "active" list is an
// approximation of a list of active slot spans. It is an approximation because
// full, empty and decommitted slot spans may briefly be present in the list
// until we next do a scan over it. The "empty" list holds mostly empty slot
// spans, but may briefly hold decommitted ones too. The "decommitted" list
// holds only decommitted slot spans.
//
// The significant slot span transitions are:
// - Free() will detect when a full slot span has a slot freed and immediately
//   return the slot span to the head of the active list.
// - Free() will detect when a slot span is fully emptied. It _may_ add it to
//   the empty list or it _may_ leave it on the active list until a future
//   list scan.
// - Alloc() _may_ scan the active page list in order to fulfil the request.
//   If it does this, full, empty and decommitted slot spans encountered will be
//   booted out of the active list. If there are no suitable active slot spans
//   found, an empty or decommitted slot spans (if one exists) will be pulled
//   from the empty/decommitted list on to the active list.
#pragma pack(push, 1)
struct SlotSpanMetadata { … };
#pragma pack(pop)
static_assert …;

inline constexpr SlotSpanMetadata::SlotSpanMetadata() noexcept
    : … { … }

inline SlotSpanMetadata::SlotSpanMetadata(const SlotSpanMetadata&) = default;

// Metadata of a non-first partition page in a slot span.
template <MetadataKind kind>
struct SubsequentPageMetadata { … };

// Each partition page has metadata associated with it. The metadata of the
// first page of a slot span, describes that slot span. If a slot span spans
// more than 1 page, the page metadata may contain rudimentary additional
// information.
// "Pack" the union so that common page metadata still fits within
// kPageMetadataSize. (SlotSpanMetadata is also "packed".)
#pragma pack(push, 1)
template <MetadataKind kind>
struct PartitionPageMetadataBase { … };

template <MetadataKind kind>
struct PartitionPageMetadata;

template <>
struct PartitionPageMetadata<MetadataKind::kReadOnly>
    : public PartitionPageMetadataBase<MetadataKind::kReadOnly> { … };

template <>
struct PartitionPageMetadata<MetadataKind::kWritable>
    : public PartitionPageMetadataBase<MetadataKind::kWritable> { … };
#pragma pack(pop)

static_assert …;
static_assert …;

// Certain functions rely on PartitionPageMetadata being either SlotSpanMetadata
// or SubsequentPageMetadata, and therefore freely casting between each other.
// TODO(crbug.com/40940915) Stop ignoring the -Winvalid-offsetof warning.
#if defined(__clang__)
#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Winvalid-offsetof"
#endif
static_assert …;
static_assert …;
static_assert …;
static_assert …;
#if defined(__clang__)
#pragma clang diagnostic pop
#endif

PA_ALWAYS_INLINE PartitionPageMetadata<MetadataKind::kReadOnly>*
PartitionSuperPageToMetadataArea(uintptr_t super_page) { … }

PA_ALWAYS_INLINE const SubsequentPageMetadata<MetadataKind::kReadOnly>*
GetSubsequentPageMetadata(
    const PartitionPageMetadata<MetadataKind::kReadOnly>* page_metadata) { … }

PA_ALWAYS_INLINE SubsequentPageMetadata<MetadataKind::kWritable>*
GetSubsequentPageMetadata(
    PartitionPageMetadata<MetadataKind::kWritable>* page_metadata) { … }

PA_ALWAYS_INLINE PartitionSuperPageExtentEntry<MetadataKind::kReadOnly>*
PartitionSuperPageToExtent(uintptr_t super_page) { … }

PA_ALWAYS_INLINE PAGE_ALLOCATOR_CONSTANTS_DECLARE_CONSTEXPR size_t
ReservedStateBitmapSize() { … }

PA_ALWAYS_INLINE uintptr_t
SuperPagePayloadStartOffset(bool is_managed_by_normal_buckets) { … }

PA_ALWAYS_INLINE uintptr_t SuperPagePayloadBegin(uintptr_t super_page) { … }

PA_ALWAYS_INLINE uintptr_t SuperPagePayloadEndOffset() { … }

PA_ALWAYS_INLINE uintptr_t SuperPagePayloadEnd(uintptr_t super_page) { … }

PA_ALWAYS_INLINE size_t SuperPagePayloadSize(uintptr_t super_page) { … }

PA_ALWAYS_INLINE PartitionSuperPageExtentEntry<MetadataKind::kReadOnly>*
SlotSpanMetadata::ToSuperPageExtent() const { … }

// Returns whether the pointer lies within the super page's payload area (i.e.
// area devoted to slot spans). It doesn't check whether it's within a valid
// slot span. It merely ensures it doesn't fall in a meta-data region that would
// surely never contain user data.
PA_ALWAYS_INLINE bool IsWithinSuperPagePayload(uintptr_t address) { … }

// Converts from an address inside a super page into a pointer to the
// PartitionPageMetadata object (within super pages's metadata) that describes
// the partition page where |address| is located. |address| doesn't have to be
// located within a valid (i.e. allocated) slot span, but must be within the
// super page's payload area (i.e. area devoted to slot spans).
//
// While it is generally valid for |ptr| to be in the middle of an allocation,
// care has to be taken with direct maps that span multiple super pages. This
// function's behavior is undefined if |ptr| lies in a subsequent super page.
PA_ALWAYS_INLINE PartitionPageMetadata<MetadataKind::kReadOnly>*
PartitionPageMetadata<MetadataKind::kReadOnly>::FromAddr(uintptr_t address) { … }

// Converts from a pointer to the SlotSpanMetadata object (within a super
// pages's metadata) into a pointer to the beginning of the slot span. This
// works on direct maps too.
PA_ALWAYS_INLINE uintptr_t
SlotSpanMetadata::ToSlotSpanStart(const SlotSpanMetadata* slot_span) { … }

// Converts an address inside a slot span into a pointer to the SlotSpanMetadata
// object (within super pages's metadata) that describes the slot span
// containing that slot.
//
// CAUTION! For direct-mapped allocation, |address| has to be within the first
// partition page.
PA_ALWAYS_INLINE SlotSpanMetadata* SlotSpanMetadata::FromAddr(
    uintptr_t address) { … }

// Like |FromAddr|, but asserts that |slot_start| indeed points to the
// beginning of a slot. It doesn't check if the slot is actually allocated.
//
// This works on direct maps too.
PA_ALWAYS_INLINE SlotSpanMetadata* SlotSpanMetadata::FromSlotStart(
    uintptr_t slot_start) { … }

// Like |FromAddr|, but asserts that |object| indeed points to the beginning of
// an object. It doesn't check if the object is actually allocated.
//
// This works on direct maps too.
PA_ALWAYS_INLINE SlotSpanMetadata* SlotSpanMetadata::FromObject(void* object) { … }

// Like |FromAddr|, but asserts that |address| indeed points within an object.
// It doesn't check if the object is actually allocated.
//
// CAUTION! For direct-mapped allocation, |address| has to be within the first
// partition page.
PA_ALWAYS_INLINE SlotSpanMetadata* SlotSpanMetadata::FromObjectInnerAddr(
    uintptr_t address) { … }

PA_ALWAYS_INLINE SlotSpanMetadata* SlotSpanMetadata::FromObjectInnerPtr(
    void* ptr) { … }

// TODO(crbug.com/40238514): SlotSpanMetadata<kWritable> will implement
// SetRawSize().
PA_ALWAYS_INLINE void SlotSpanMetadata::SetRawSize(size_t raw_size) { … }

// TODO(crbug.com/40238514): SlotSpanMetadata<kReadOnly> will implement
// SetRawSize().
PA_ALWAYS_INLINE size_t SlotSpanMetadata::GetRawSize() const { … }

PA_ALWAYS_INLINE void SlotSpanMetadata::SetFreelistHead(
    PartitionFreelistEntry* new_head) { … }

PA_ALWAYS_INLINE PartitionFreelistEntry* SlotSpanMetadata::PopForAlloc(
    size_t size,
    const PartitionFreelistDispatcher* freelist_dispatcher) { … }

PA_ALWAYS_INLINE void SlotSpanMetadata::Free(
    uintptr_t slot_start,
    PartitionRoot* root,
    const PartitionFreelistDispatcher* freelist_dispatcher)
    // PartitionRootLock() is not defined inside partition_page.h, but
    // static analysis doesn't require the implementation.
    PA_EXCLUSIVE_LOCKS_REQUIRED(PartitionRootLock(root)) { … }

PA_ALWAYS_INLINE void SlotSpanMetadata::AppendFreeList(
    PartitionFreelistEntry* head,
    PartitionFreelistEntry* tail,
    size_t number_of_freed,
    PartitionRoot* root,
    const PartitionFreelistDispatcher* freelist_dispatcher)
    PA_EXCLUSIVE_LOCKS_REQUIRED(PartitionRootLock(root)) { … }

PA_ALWAYS_INLINE bool SlotSpanMetadata::is_active() const { … }

PA_ALWAYS_INLINE bool SlotSpanMetadata::is_full() const { … }

PA_ALWAYS_INLINE bool SlotSpanMetadata::is_empty() const { … }

PA_ALWAYS_INLINE bool SlotSpanMetadata::is_decommitted() const { … }

PA_ALWAYS_INLINE void SlotSpanMetadata::Reset() { … }

// Iterates over all slot spans in a super-page. |Callback| must return true if
// early return is needed.
template <typename Callback>
void IterateSlotSpans(uintptr_t super_page,
                      Callback callback) { … }

// Helper class derived from the implementation of `SlotSpanMetadata`
// that can (but does not _have_ to) enforce that it is in fact a slot
// start.
//
// Behavior is not well-defined if this class is used outside
// PartitionAlloc internals, e.g. if PA is deferring to sanitizers.
// In such cases, the return value from PA's `Alloc()` may not be
// a slot start - it might not be managed by PartitionAlloc at all.
class PA_COMPONENT_EXPORT(PARTITION_ALLOC) SlotStart { … };

}  // namespace partition_alloc::internal

#endif  // PARTITION_ALLOC_PARTITION_PAGE_H_
chromium/base/allocator/partition_allocator/src/partition_alloc/partition_page.h
