chromium/base/allocator/partition_allocator/src/partition_alloc/reservation_offset_table.h

// Copyright 2021 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_RESERVATION_OFFSET_TABLE_H_
#define PARTITION_ALLOC_RESERVATION_OFFSET_TABLE_H_

#include <cstddef>
#include <cstdint>
#include <limits>
#include <tuple>

#include "partition_alloc/address_pool_manager.h"
#include "partition_alloc/build_config.h"
#include "partition_alloc/buildflags.h"
#include "partition_alloc/partition_address_space.h"
#include "partition_alloc/partition_alloc_base/compiler_specific.h"
#include "partition_alloc/partition_alloc_base/component_export.h"
#include "partition_alloc/partition_alloc_check.h"
#include "partition_alloc/partition_alloc_constants.h"
#include "partition_alloc/tagging.h"
#include "partition_alloc/thread_isolation/alignment.h"

namespace partition_alloc::internal {

static constexpr uint16_t kOffsetTagNotAllocated = …;
static constexpr uint16_t kOffsetTagNormalBuckets = …;

// The main purpose of the reservation offset table is to easily locate the
// direct map reservation start address for any given address. There is one
// entry in the table for each super page.
//
// When PartitionAlloc reserves an address region it is always aligned to
// super page boundary. However, in 32-bit mode, the size may not be aligned
// super-page-aligned, so it may look like this:
//   |<--------- actual reservation size --------->|
//   +----------+----------+-----+-----------+-----+ - - - +
//   |SuperPage0|SuperPage1| ... |SuperPage K|SuperPage K+1|
//   +----------+----------+-----+-----------+-----+ - - -.+
//                                           |<-X->|<-Y*)->|
//
// The table entries for reserved super pages say how many pages away from the
// reservation the super page is:
//   +----------+----------+-----+-----------+-------------+
//   |Entry for |Entry for | ... |Entry for  |Entry for    |
//   |SuperPage0|SuperPage1|     |SuperPage K|SuperPage K+1|
//   +----------+----------+-----+-----------+-------------+
//   |     0    |    1     | ... |     K     |   K + 1     |
//   +----------+----------+-----+-----------+-------------+
//
// For an address Z, the reservation start can be found using this formula:
//   ((Z >> kSuperPageShift) - (the entry for Z)) << kSuperPageShift
//
// kOffsetTagNotAllocated is a special tag denoting that the super page isn't
// allocated by PartitionAlloc and kOffsetTagNormalBuckets denotes that it is
// used for a normal-bucket allocation, not for a direct-map allocation.
//
// *) In 32-bit mode, Y is not used by PartitionAlloc, and cannot be used
//    until X is unreserved, because PartitionAlloc always uses kSuperPageSize
//    alignment when reserving address spaces. One can use check "is in pool?"
//    to further determine which part of the super page is used by
//    PartitionAlloc. This isn't a problem in 64-bit mode, where allocation
//    granularity is kSuperPageSize.
class PA_COMPONENT_EXPORT(PARTITION_ALLOC)
    PA_THREAD_ISOLATED_ALIGN ReservationOffsetTable { … };

#if PA_BUILDFLAG(HAS_64_BIT_POINTERS)
PA_ALWAYS_INLINE uint16_t* GetReservationOffsetTable(pool_handle handle) { … }

PA_ALWAYS_INLINE const uint16_t* GetReservationOffsetTableEnd(
    pool_handle handle) { … }

PA_ALWAYS_INLINE uint16_t* GetReservationOffsetTable(uintptr_t address) { … }

PA_ALWAYS_INLINE const uint16_t* GetReservationOffsetTableEnd(
    uintptr_t address) { … }

PA_ALWAYS_INLINE uint16_t* ReservationOffsetPointer(pool_handle pool,
                                                    uintptr_t offset_in_pool) { … }
#else   // PA_BUILDFLAG(HAS_64_BIT_POINTERS)
PA_ALWAYS_INLINE uint16_t* GetReservationOffsetTable(uintptr_t address) {
  return ReservationOffsetTable::reservation_offset_table_.offsets;
}

PA_ALWAYS_INLINE const uint16_t* GetReservationOffsetTableEnd(
    uintptr_t address) {
  return ReservationOffsetTable::reservation_offset_table_.offsets +
         ReservationOffsetTable::kReservationOffsetTableLength;
}
#endif  // PA_BUILDFLAG(HAS_64_BIT_POINTERS)

PA_ALWAYS_INLINE uint16_t* ReservationOffsetPointer(uintptr_t address) { … }

PA_ALWAYS_INLINE uintptr_t ComputeReservationStart(uintptr_t address,
                                                   uint16_t* offset_ptr) { … }

// If the given address doesn't point to direct-map allocated memory,
// returns 0.
PA_ALWAYS_INLINE uintptr_t GetDirectMapReservationStart(uintptr_t address) { … }

#if PA_BUILDFLAG(HAS_64_BIT_POINTERS)
// If the given address doesn't point to direct-map allocated memory,
// returns 0.
// This variant has better performance than the regular one on 64-bit builds if
// the Pool that an allocation belongs to is known.
PA_ALWAYS_INLINE uintptr_t
GetDirectMapReservationStart(uintptr_t address,
                             pool_handle pool,
                             uintptr_t offset_in_pool) { … }
#endif  // PA_BUILDFLAG(HAS_64_BIT_POINTERS)

// Returns true if |address| is the beginning of the first super page of a
// reservation, i.e. either a normal bucket super page, or the first super page
// of direct map.
// |address| must belong to an allocated super page.
PA_ALWAYS_INLINE bool IsReservationStart(uintptr_t address) { … }

// Returns true if |address| belongs to a normal bucket super page.
PA_ALWAYS_INLINE bool IsManagedByNormalBuckets(uintptr_t address) { … }

// Returns true if |address| belongs to a direct map region.
PA_ALWAYS_INLINE bool IsManagedByDirectMap(uintptr_t address) { … }

// Returns true if |address| belongs to a normal bucket super page or a direct
// map region, i.e. belongs to an allocated super page.
PA_ALWAYS_INLINE bool IsManagedByNormalBucketsOrDirectMap(uintptr_t address) { … }

}  // namespace partition_alloc::internal

#endif  // PARTITION_ALLOC_RESERVATION_OFFSET_TABLE_H_