zircon/kernel/lib/arch/include/lib/arch/paging.h

// Copyright 2023 The Fuchsia Authors
// Use of this source code is governed by a MIT-style
// license that can be found in the LICENSE file or at
// https://opensource.org/licenses/MIT

#ifndef ZIRCON_KERNEL_LIB_ARCH_INCLUDE_LIB_ARCH_PAGING_H_
#define ZIRCON_KERNEL_LIB_ARCH_INCLUDE_LIB_ARCH_PAGING_H_

#include <inttypes.h>
#include <lib/fit/result.h>
#include <lib/stdcompat/algorithm.h>
#include <zircon/assert.h>

#include <array>
#include <cstddef>
#include <cstdint>
#include <iterator>
#include <limits>
#include <optional>
#include <type_traits>
#include <utility>

#include <fbl/bits.h>
#include <hwreg/bitfields.h>

namespace arch {

/// Settings relating to the access permissions of a page or pages that map
/// through an entry.
struct AccessPermissions {
  bool readable = false;
  bool writable = false;
  bool executable = false;
  bool user_accessible = false;
};

namespace internal {

template <typename T, typename = std::enable_if_t<std::is_default_constructible_v<T>>>
inline constexpr T kDefaultConstructedValue = {};

// See ExamplePagingTraits::PagingSettings below.
template <typename MemoryType, auto& DefaultMemoryValue = kDefaultConstructedValue<MemoryType>>
struct PagingSettings {
  static constexpr MemoryType kDefaultMemory = DefaultMemoryValue;

  uint64_t address = 0u;
  bool present = false;
  bool terminal = false;
  AccessPermissions access;
  MemoryType memory = DefaultMemoryValue;
  bool global = false;
};

// See Paging<PagingTraits>::MemoryType below.
template <typename MemoryType, auto& DefaultMemoryValue = kDefaultConstructedValue<MemoryType>>
struct MapSettings {
  AccessPermissions access;
  MemoryType memory = DefaultMemoryValue;
  bool global = false;
};

}  // namespace internal

/// Parameterizes the unaddressable bits of a virtual address.
enum class VirtualAddressExtension {
  /// Sign-extended (commonly referred to as "canonical"): each unaddressable
  /// bit must match the highest addressable bit.
  ///
  /// Conventionally used in paging schemes that configure the upper and lower
  /// spaces together: the subspace that is sign-extended as 0 represents the
  /// lower, while the subspace that is sign-extended as 1 represents the upper.
  kCanonical,

  /// All unaddressable bits are 0.
  ///
  /// Conventionally used for describing the lower address space in paging
  /// schemes that configure the upper and lower spaces separately.
  k0,

  /// All unaddressable bits are 1.
  ///
  /// Conventionally used for describing the upper address space in paging
  /// schemes that configure the upper and lower spaces separately.
  k1,
};

/// ExamplePagingTraits defines the "PagingTraits" API, being a coded examplar
/// intended for documentation purposes only. Parameterizing the creation of
/// virtual memory spaces, the traits are used to abstract away finicky paging
/// business logic across that differs across CPU architectures (or IOMMU
/// translation schemes). The resulting uniform API can than be used for a
/// generic approach to address translation and page mapping.
struct ExamplePagingTraits {
  /// An enum or integral type describing the levels of paging. Rather than
  /// mandate that this be an integral type, we leave room for the enum to
  /// support the use of context-specific names for each level. This is done
  /// for two reasons:
  ///
  ///   * Some architectures do not label their paging levels with numbers
  ///     (e.g., x86's "page directory pointer table"), so allowing for the use
  ///     of more recognizable names aids in readability (especially when it
  ///     comes to cross-referencing with the manual);
  ///
  ///   * Architectures that do label levels with numbers have inconsistent
  ///     conventions: for example, ARM paging levels range from -1 up to 3,
  ///     while RISC-V's range from 4 down to 0.
  ///
  enum class LevelType { kExampleLevel };

  /// A type describing 'memory' configuration (both RAM and MMIO). This might
  /// encode cache coherence policy or similar architecture-specific details.
  struct MemoryType {};

  /// Captures runtime system information that feeds into translation or
  /// mapping considerations. The construction of this information is
  /// context-dependent and so is left to the user of the API.
  ///
  /// SystemState is expected to be default-constructible.
  struct SystemState {};

  /// PagingSettings should be a class with the following public fields,
  /// corresponding to TableEntry's accessors below:
  /// *  bool present;
  /// *  bool terminal;
  /// *  uint64_t address;
  /// *  AccessPermissions access;
  /// *  MemoryType memory;
  ///
  /// Further, PagingSettings should define a default memory type value in the
  /// form of
  /// *  static constexpr MemoryType kDefaultMemory;
  ///
  /// This abstraction allows traits to define their own default settings.
  ///
  /// PagingSettings must be default-constructible.
  ///
  /// internal::PagingSettings may be instantiated to satisfy these
  /// requirements.
  using PagingSettings = internal::PagingSettings<MemoryType>;

  /// The register type representing a page table entry at a given level. It
  /// must meet the defined API below.
  template <LevelType Level>
  struct TableEntry : public hwreg::RegisterBase<TableEntry<Level>, uint64_t> {
    /// Whether the entry is present to the hardware.
    ///
    /// The reading of an entry's settings while in the 'not present' state is
    /// permitted, 'presence (to the hardware)' being regarding as orthogonal
    /// in this case. It is assumed that `ValueType{0}` is in the 'not present'
    /// state.
    constexpr bool present() const { return false; }

    /// Whether the entry is terminal and points to the ultimate, physical page
    /// (or block).
    constexpr bool terminal() const { return false; }

    /// Gives the physical address of the table at the next level or that of
    /// the ultimate, physical page (or block) if the entry is terminal.
    ///
    /// TODO(https://fxbug.dev/42079764): document required alignment.
    constexpr uint64_t address() const { return 0; }

    /// If the entry is terminal, these accessors give the access permissions
    /// of the associated page (or block); if non-terminal, a false permission
    /// flag here means that the flag is ignored in the entries at later
    /// levels. In particular, that means that if the entry is non-terminal and
    /// `!Traits::kNonTerminalAccessPermissions` then these accessors are
    /// expected return identically true.
    ///
    /// In the case of readability, writability, and executability, these
    /// permissions constrain how the *supervisor* may access associated pages.
    /// These permissions do not a priori indicate how usermode may access them
    /// when `user_accessible()` is true; rather, the latter only indicates
    /// usermode may access them in some fashion.
    constexpr bool readable() const { return false; }
    constexpr bool writable() const { return false; }
    constexpr bool executable() const { return false; }
    constexpr bool user_accessible() const { return false; }

    /// If terminal, whether the associated page was read from, written to, or
    /// executed. If non-terminal, this *may* for certain implementations
    /// indicate whether a page that maps through this entry was similarly
    /// accessed; otherwise, this is expected to return false.
    ///
    /// Hardware may often be configured so as to manage this bit
    /// automatically - but otherwise software must do so and contend with
    /// access faults when unset.
    constexpr bool accessed() const { return false; }

    /// If terminal, whether the associated page is 'global'. A page being
    /// designated as such prevents its TLB entries from being affected by
    /// normal TLB invalidations. This is useful in the case of mappings that
    /// are expected to exist within different page table trees being switched
    /// between. If non-terminal, this is expected to return false.
    constexpr bool global() const { return false; }

    /// Returns the memory type of the associated page, which may require
    /// access to system state to decode.
    ///
    /// This method may only be called on a terminal entry.
    constexpr MemoryType Memory(const SystemState& state) const {
      assert(terminal());
      return PagingSettings::kDefaultMemory;
    }

    /// (Re)populates an entry as new. This is done in one go as there can be
    /// interdependicies among the different aspects of entry state: these
    /// could not otherwise be captured by individual setters with an
    /// unconstrained relative call order. (For example, the setting of address
    /// could be sensitive to whether the entry is terminal.)
    ///
    /// If `settings.present` is false, all other settings should be ignored.
    ///
    /// Once a setting is applied, the corresponding getter should return
    /// reflect that identically.
    ///
    /// If `settings.terminal` is true, then it is the responsibility of the
    /// user to check that the provided access permissions are valid (e.g.,
    /// in consultation with Traits::kExecuteOnlyAllowed) before making this
    /// call; otherwise if `!Traits::kNonTerminalAccessPermissions` then the
    /// provided access permissions are expected to be maximally permissive.
    ///
    /// Where the qualifiers make sense (which is implementation-specific), a
    /// call to Set() will result in a present entry being updated as accessed.
    /// There is no case in which we would want to create a new
    /// entry but not mark it as such. If hardware is managing these bits, then
    /// there is no penalty to doing so; if software-managed, then we avoid an
    /// unnecessary trap that we would only handle later on to set these bits.
    /// Similarly, if an entry is Set() as writable, then it should reflect as
    /// 'dirty' when that makes sense.
    constexpr TableEntry& Set(const SystemState& state, const PagingSettings& settings) {
      return *this;
    }
  };

  /// The maximum number of addressable physical address bits permitted by the
  /// hardware.
  static constexpr unsigned int kMaxPhysicalAddressSize = 64;

  /// The ordered, sequence of paging levels. This is expected to be a
  /// indexable, constexpr container of LevelType; in practice this is a
  /// std::array, or a std::span over one.
  static constexpr std::array kLevels = {LevelType::kExampleLevel};

  /// The required log2 alignment of each page table's physical address.
  static constexpr unsigned int kTableAlignmentLog2 = 0;

  /// The log2 number of page table entries for a given level.
  template <LevelType Level>
  static constexpr unsigned int kNumTableEntriesLog2 = 1;

  /// Whether the hardware permits execute-only mappings.
  static constexpr bool kExecuteOnlyAllowed = false;

  /// Whether access permissions may be set on non-terminal entries so as to
  /// narrow access for later levels. If false, then access permissions are
  /// only applicable to terminal entries - and those provided to
  /// `TableEntry<Level>::Set()` for non-terminal entries must be maximally
  /// permissive.
  static constexpr bool kNonTerminalAccessPermissions = false;

  /// An optional override for the number of addressable bits of a virtual
  /// address. The values of `kNumTableEntriesLog2<Level>` collectively and
  /// indirectly prescribe a maximum width, as this determines the maximum bit
  /// that figures into the first level of paging. There are cases in which an
  /// address space may be configured to be strictly smaller, which can be
  /// specified by this value (which must be smaller than the default max);
  /// otherwise, a value of std::nullopt specifies the size as the default max.
  static constexpr std::optional<unsigned int> kVirtualAddressSizeOverride = std::nullopt;

  /// Parameterizes the unaddressable virtual address space bits.
  static constexpr auto kVirtualAddressExtension = VirtualAddressExtension::kCanonical;

  /// Whether the given level can generally feature terminal entries.
  template <LevelType Level>
  static bool LevelCanBeTerminal(const SystemState& state) {
    return false;
  }
};

/// A range of (zero-indexed) bits within a virtual address.
struct VirtualAddressBitRange {
  unsigned int high, low;
};

/// The page information associated with a given virtual address, returned by
/// Paging's Query API below.
struct PagingQueryResult {
  struct Page {
    uint64_t paddr = 0;
    uint64_t size = 0;
  };

  /// The physical address to which the associated virtual address is mapped.
  uint64_t paddr = 0;

  /// The page in which the associated virtual address is mapped.
  Page page;

  /// The access permissions of the associated page.
  AccessPermissions access;
};

/// A mapping error, returned by the mapping utilities below.
struct MapError {
  enum class Type {
    /// An unknown error, given to a default-constructed error.
    kUnknown,

    /// The allocation of a page table was unsuccessful.
    kAllocationFailure,

    /// An attempt was made to map a previously-mapped virtual address.
    kAlreadyMapped,
  };

  /// The physical address of at which the error occurred.
  uint64_t paddr = 0;

  /// The virtual address for the map attempt.
  uint64_t vaddr = 0;

  Type type = Type::kUnknown;
};

/// Paging provides paging-related operations for a given a set of paging
/// traits.
template <class PagingTraits>
class Paging : public PagingTraits {
 public:
  using typename PagingTraits::LevelType;
  static_assert(std::is_enum_v<LevelType> || std::is_integral_v<LevelType>);

  template <LevelType Level>
  using TableEntry = typename PagingTraits::template TableEntry<Level>;

  using typename PagingTraits::MemoryType;

  using typename PagingTraits::PagingSettings;
  static_assert(std::is_default_constructible_v<PagingSettings>);

  using typename PagingTraits::SystemState;
  static_assert(std::is_default_constructible_v<SystemState>);

  /// The settings to apply to each page mapped in the context of the mapping
  /// utilities below.
  using MapSettings = internal::MapSettings<MemoryType, PagingSettings::kDefaultMemory>;

  using PagingTraits::kLevels;
  static_assert(kLevels.size() > 0);

  using PagingTraits::kMaxPhysicalAddressSize;
  static_assert(kMaxPhysicalAddressSize > 0);
  static_assert(kMaxPhysicalAddressSize <= 64);

  /// The maximum supported physical address.
  static constexpr uint64_t kMaxPhysicalAddress = []() {
    if constexpr (kMaxPhysicalAddressSize == 64) {
      return std::numeric_limits<uint64_t>::max();
    } else {
      return (uint64_t{1u} << kMaxPhysicalAddressSize) - 1;
    }
  }();

  using PagingTraits::kTableAlignmentLog2;
  static_assert(kTableAlignmentLog2 < 64);

  template <LevelType Level>
  static constexpr unsigned int kNumTableEntriesLog2 =
      PagingTraits::template kNumTableEntriesLog2<Level>;

  using PagingTraits::kVirtualAddressExtension;
  using PagingTraits::kVirtualAddressSizeOverride;

  static constexpr LevelType kFirstLevel = kLevels.front();

  /// A table's physical alignment at any level.
  static constexpr uint64_t kTableAlignment = uint64_t{1u} << kTableAlignmentLog2;

  /// The number of table entries at a given level.
  template <LevelType Level>
  static constexpr uint64_t kNumTableEntries = uint64_t{1u} << kNumTableEntriesLog2<Level>;

  /// The size in bytes of an entry at a given level.
  template <LevelType Level>
  static constexpr uint64_t kEntrySize = sizeof(typename TableEntry<Level>::ValueType);

  /// The size in bytes of a table at a given level.
  template <LevelType Level>
  static constexpr uint64_t kTableSize = kEntrySize<Level> * kNumTableEntries<Level>;

  /// The level after `Level`. Must be used in a constexpr context in
  /// which `Level` is not the last.
  template <LevelType Level>
  static constexpr LevelType kNextLevel = []() {
    static_assert(Level != kLevels.back());
    constexpr auto it = cpp20::find(kLevels.begin(), kLevels.end(), Level);
    static_assert(it != kLevels.end());
    return *std::next(it);
  }();

  /// The virtual address bit range at a given level that serves as the index
  /// into a page table at that level.
  template <LevelType Level>
  static constexpr VirtualAddressBitRange kVirtualAddressBitRange =
      []() { return Paging::template GetVirtualAddressBitRange<Level>(); }();

  /// The size of a would-be page if mapped from a given level.
  template <LevelType Level>
  static constexpr uint64_t kPageSize = uint64_t{1u} << kVirtualAddressBitRange<Level>.low;

  /// The number of addressable bits in a virtual address (i.e., its "size").
  static constexpr unsigned int kVirtualAddressSize = []() {
    constexpr unsigned int kMaxSize = kVirtualAddressBitRange<kLevels[0]>.high + 1;
    if constexpr (kVirtualAddressSizeOverride) {
      static_assert(*kVirtualAddressSizeOverride <= kMaxSize);
      return *kVirtualAddressSizeOverride;
    }
    return kMaxSize;
  }();

  /// The virtual address marking the (exclusive) end of the lower range, if
  /// parameterized by PagingTraits.
  static constexpr std::optional<uint64_t> kLowerVirtualAddressRangeEnd = []() {
    if constexpr (kVirtualAddressExtension == VirtualAddressExtension::k1) {
      return std::nullopt;
    } else if (kVirtualAddressSize < 64) {
      return uint64_t{1u} << kVirtualAddressSize;
    } else {
      return std::numeric_limits<uint64_t>::max();
    }
  }();

  /// The virtual address marking the beginning of the upper range, if
  /// parameterized by PagingTraits.
  static constexpr std::optional<uint64_t> kUpperVirtualAddressRangeStart = []() {
    if constexpr (kVirtualAddressExtension == VirtualAddressExtension::k0) {
      return std::nullopt;
    } else {
      return ~((uint64_t{1u} << kVirtualAddressSize) - 1);
    }
  }();

  ///
  /// Main paging trait methods.
  ///
  /// I/O is abstracted via a `PaddrToTableIo` callable that maps the physical
  /// address (of a page table) to an I/O provider intended for reading from
  /// and writing to entries in that table, where offset represents the index.
  ///

  /// A diagnostic utility that returns the page information associated with a
  /// mapped virtual address `vaddr`. `fit::failed` is returned if a
  /// non-present table entry was encountered.
  template <typename PaddrToTableIo>
  static fit::result<fit::failed, PagingQueryResult> Query(uint64_t root_paddr,
                                                           PaddrToTableIo&& paddr_to_io,
                                                           uint64_t vaddr) {
    ReadonlyTerminalVisitor visitor([vaddr](const auto& terminal) {
      return PagingQueryResult{
          .paddr = TerminalAddress(terminal, vaddr),
          .page = PageInfo(terminal),
          .access =
              AccessPermissions{
                  .readable = terminal.readable(),
                  .writable = terminal.writable(),
                  .executable = terminal.executable(),
                  .user_accessible = terminal.user_accessible(),
              },
      };
    });
    return VisitPageTables(root_paddr, std::forward<PaddrToTableIo>(paddr_to_io), visitor, vaddr);
  }

  /// Attempts to map `[input_vaddr, input_vaddr + size)` to
  /// `[output_paddr, output_paddr + size)` with the provided settings.
  /// `input_vaddr` and `output_vaddr` must both be aligned to the smallest
  /// possible page size, and `size` must be a multiple of it. The mapping
  /// must be a fresh one; this operation will return an error of type
  /// `kAlreadyAllocated` if it encounters an existing mapping. The mapping
  /// will proceed incrementally, mapping the largest possible page for each
  /// increasing subrange.
  ///
  /// Page table allocation is abstracted by an `PageTableAllocator` callable
  /// with a signature of
  /// ```
  /// std::optional<uint64_t>(uint64_t size, uint64_t alignment)
  /// ```
  /// std::nullopt being returned in the event of an allocation failure.
  ///
  /// `settings` represents the set of page-related settings to apply to a
  /// new, zero-filled, terminal entry.
  template <typename PaddrToIoProvider, typename PageTableAllocator>
  static fit::result<MapError> Map(uint64_t root_paddr,              //
                                   PaddrToIoProvider&& paddr_to_io,  //
                                   PageTableAllocator allocator,     //
                                   const SystemState& state,         //
                                   uint64_t input_vaddr,             //
                                   uint64_t size,                    //
                                   uint64_t output_paddr,            //
                                   const MapSettings& settings) {    //
    static_assert(
        std::is_invocable_r_v<std::optional<uint64_t>, PageTableAllocator, uint64_t, uint64_t>);

    constexpr uint64_t kMinPageSize = kTableAlignment;
    ZX_ASSERT_MSG((input_vaddr % kMinPageSize) == 0,
                  "virtual address %#" PRIx64 " must be %#" PRIx64 "-aligned", input_vaddr,
                  kMinPageSize);
    ZX_ASSERT_MSG((output_paddr % kMinPageSize) == 0,
                  "physical address %#" PRIx64 " must be %#" PRIx64 "-aligned", output_paddr,
                  kMinPageSize);
    ZX_ASSERT_MSG(size % kMinPageSize == 0, "size %#" PRIx64 " must be a multiple of %#" PRIx64,
                  size, kMinPageSize);

    // MappingVisitor tracks the range to be mapped, mapping and updating
    // the current mappable window on successive calls.
    //
    // TODO(joshuaseaton): Repeated calls to VisitPageTables() does redundant
    // walking. The current walk is also not conducive to marking adjacent
    // entries as being part of the same contiguous mapping, when appropriate,
    // in order to optimize the TLB use.
    MappingVisitor mapper(std::move(allocator), state, input_vaddr, size, output_paddr, settings);
    while (mapper.unmapped_size() > 0) {
      auto result = VisitPageTables(root_paddr, paddr_to_io, mapper, mapper.next_vaddr());
      if (result.is_error()) {
        return result.take_error();
      }
    }
    return fit::ok();
  }

  ///
  /// Additional primitives.
  ///
  /// The following types and methods define more abstracted paging primitives.
  /// Central to these is the notion of a "(page table) visitor". A visitor
  /// abstracts the visitation logic of page table entries encountered during
  /// a page table walk. It is represented by a type with the overloaded call
  /// signatures
  /// ```
  /// std::optional<Value>(TableIo& io,
  ///                      TableEntry<Level>& entry,
  ///                      uint64_t table_paddr);
  /// ```
  /// for some I/O provider `TableIo` and some value type `Value`, for every
  /// `Level` in `kLevels`. The I/O provider is passed to permit the visitor to
  /// make modifications when desired. When a visitor returns `std::nullopt`
  /// that is a directive to continue translation to the next entry; otherwise,
  /// the returned value signifies that the visitor is done visiting, that the
  /// walk should terminate, and that this value should be plumbed back up to
  /// whatever is orchestrating the walk. We refer to `Value` as the "value type"
  /// of a visitor.
  ///
  /// A visitor must return a non-null value before the walk terminates;
  /// otherwise, the walk panics.
  ///

  /// This type is a helper for validating that `Visitor` does indeed meet the
  /// API expectations of a page table visitor (at least when specialized with
  /// `TableIo`).
  template <typename Visitor, class TableIo>
  class VisitResult {
   private:
    template <LevelType Level>
    struct ResultAt {
      static_assert(std::is_invocable_v<Visitor, TableIo&, TableEntry<Level>&, uint64_t>);
      using type = std::invoke_result_t<Visitor, TableIo&, TableEntry<Level>&, uint64_t>;

      using value_type = typename type::value_type;
      static_assert(std::is_same_v<type, std::optional<value_type>>);
    };

   public:
    using value_type = typename ResultAt<kFirstLevel>::value_type;
    using type = std::optional<value_type>;

   private:
    template <size_t... LevelIndex>
    static constexpr bool ValueTypesCoincide(std::index_sequence<LevelIndex...>) {
      return (std::is_same_v<value_type, typename ResultAt<kLevels[LevelIndex]>::value_type> &&
              ...);
    }
    static_assert(ValueTypesCoincide(std::make_index_sequence<kLevels.size()>{}));
  };

  /// The value type of a visitor.
  template <class TableIo, typename Visitor>
  using VisitValue = typename VisitResult<TableIo, Visitor>::value_type;

  /// The type of I/O provider associated with a `PaddrToTableIo`.
  template <typename PaddrToTableIo>
  using TableIo = std::invoke_result_t<PaddrToTableIo, uint64_t>;

  /// Walk the page tables rooted at `table_paddr` for a given virtual address
  /// and visitor.
  template <typename PaddrToTableIo, typename Visitor>
  static VisitValue<Visitor, TableIo<PaddrToTableIo>> VisitPageTables(
      uint64_t table_paddr,          //
      PaddrToTableIo&& paddr_to_io,  //
      Visitor&& visitor,             //
      uint64_t vaddr) {              //
    AssertValidVirtualAddress(vaddr);
    return VisitPageTablesFrom<kFirstLevel>(table_paddr, std::forward<PaddrToTableIo>(paddr_to_io),
                                            std::forward<Visitor>(visitor), vaddr);
  }

  /// A simple read-only visitor that returns information based on the terminal
  /// entry encountered. The logic at the terminal level and visitor's return
  /// value are parameterized by `OnTerminalEntry`: called only on terminal
  /// entries this type is callable on `const TableEntry<Level>&` for each
  /// level in `kLevels` with a uniform return type. Representing its return
  /// type as `TerminalResult`, the value type of the visitor is then
  /// `fit::result<fit::failed, TerminalResult>`, where `fit::failed` is
  /// returned in the event of encountering an unexpected, non-present entry.
  template <typename OnTerminalEntry>
  class ReadonlyTerminalVisitor {
   private:
    template <LevelType Level>
    struct TerminalResultAt {
      static_assert(std::is_invocable_v<OnTerminalEntry, const TableEntry<Level>&>);
      using type = std::invoke_result_t<OnTerminalEntry, const TableEntry<Level>&>;
    };

   public:
    using TerminalResult = typename TerminalResultAt<kFirstLevel>::type;

    /// The value type of the visitor.
    using value_type = fit::result<fit::failed, TerminalResult>;

    explicit ReadonlyTerminalVisitor(OnTerminalEntry on_terminal)
        : on_terminal_(std::move(on_terminal)) {}

    template <class TableIo, LevelType Level>
    std::optional<value_type> operator()(TableIo& io, TableEntry<Level>& entry, uint64_t vaddr) {
      if (!entry.present()) {
        return fit::failed();
      }
      if (entry.terminal()) {
        return fit::ok(on_terminal_(entry));
      }
      return {};
    }

   private:
    template <size_t LevelIndex>
    static constexpr void TerminalResultsCoincide() {
      static_assert(
          std::is_same_v<TerminalResult, typename TerminalResultAt<kLevels[LevelIndex]>::type>);
    }
    template <size_t... LevelIndex>
    static constexpr bool TerminalResultsCoincide(std::index_sequence<LevelIndex...>) {
      (TerminalResultsCoincide<LevelIndex>(), ...);
      return true;
    }
    static_assert(TerminalResultsCoincide(std::make_index_sequence<kLevels.size()>{}));

    OnTerminalEntry on_terminal_;
  };

  template <typename OnTerminalEntry>
  ReadonlyTerminalVisitor(OnTerminalEntry&&)
      -> ReadonlyTerminalVisitor<std::decay_t<OnTerminalEntry>>;

 private:
  // TODO(https://fxbug.dev/42081428): Once hwreg is constexpr-friendly, we can add a static
  // assert that zeroed entries at any level report as non-present.

  /// A visitor tailor-made to help perform a mapping of
  /// `[input_vaddr, input_vaddr + size)` to
  /// `[output_paddr, output_paddr + size)` in the context of `Map()`. Calling
  /// `VisitPageTables()` with this visitor will attempt to map the largest
  /// possible page contained within the given virtual range, updating the
  /// values describing the virtual and physical ranges provided on
  /// construction. Repeated calls to `VisitPageTables()` can then be made to
  /// fully map the region.
  template <typename PageTableAllocator>
  class MappingVisitor {
   public:
    using value_type = fit::result<MapError>;

    MappingVisitor(PageTableAllocator page_table_allocator,  //
                   const SystemState& state,                 //
                   uint64_t input_vaddr,                     //
                   uint64_t size,                            //
                   uint64_t output_paddr,                    //
                   const MapSettings& settings)              //
        : allocator_(std::move(page_table_allocator)),
          state_(state),
          input_vaddr_(input_vaddr),
          size_(size),
          output_paddr_(output_paddr),
          settings_(settings) {}

    /// The size of the range yet to be mapped.
    uint64_t unmapped_size() const { return size_; }

    /// The next virtual address to be mapped.
    uint64_t next_vaddr() const { return input_vaddr_; }

    template <typename TableIo, LevelType Level>
    std::optional<fit::result<MapError>> operator()(TableIo&& io, TableEntry<Level>& entry,
                                                    uint64_t table_paddr) {
      auto to_error = [entry_paddr = table_paddr + kEntrySize<Level> * entry.reg_addr(),
                       vaddr = input_vaddr_](MapError::Type type) -> MapError {
        return {.paddr = entry_paddr, .vaddr = vaddr, .type = type};
      };

      // If we reach a non-terminal entry, carry on with the translation.
      // Otherwise, the desired mapping cannot be a fresh one.
      if (entry.present()) {
        if (entry.terminal()) {
          return fit::error(to_error(MapError::Type::kAlreadyMapped));
        }
        return {};
      }

      constexpr uint64_t kMapSize = kPageSize<Level>;
      bool terminal = PagingTraits::template LevelCanBeTerminal<Level>(state_) &&  //
                      kMapSize <= size_ &&                                         //
                      input_vaddr_ % kMapSize == 0;                                //

      // We do not constrain the access permissions of intermediate entries,
      // leaving that instead to terminal ones.
      constexpr AccessPermissions kMaxIntermediateAccess = AccessPermissions{
          .readable = true,
          .writable = true,
          .executable = true,
          .user_accessible = true,
      };

      // At this point, the entry is not present. Unless we intend to terminate
      // at this level, we will need to allocate the next level table.
      PagingSettings settings{
          .present = true,
          .terminal = terminal,
      };
      if (terminal) {
        settings.address = output_paddr_;
        settings.access = settings_.access;
        settings.memory = settings_.memory;
        settings.global = settings_.global;
      } else {
        std::optional<uint64_t> new_table_paddr = allocator_(kTableSize<Level>, kTableAlignment);
        if (!new_table_paddr) {
          return fit::error(to_error(MapError::Type::kAllocationFailure));
        }
        settings.address = *new_table_paddr;
        settings.access = kMaxIntermediateAccess;
      }
      entry.Set(state_, settings);
      entry.WriteTo(&io);

      if (terminal) {
        input_vaddr_ += kMapSize;
        output_paddr_ += kMapSize;
        size_ -= kMapSize;
        return fit::ok();
      }
      return {};
    }

   private:
    PageTableAllocator allocator_;
    const SystemState state_;
    uint64_t input_vaddr_;
    uint64_t size_;
    uint64_t output_paddr_;
    const MapSettings settings_;
  };

  template <typename PageTableAllocator>
  MappingVisitor(PageTableAllocator, ...) -> MappingVisitor<PageTableAllocator>;

  // A private helper for defining kVirtualAddressBitRange.
  template <LevelType Level>
  static constexpr VirtualAddressBitRange GetVirtualAddressBitRange() {
    constexpr auto kRange = []() -> VirtualAddressBitRange {
      constexpr unsigned int kWidth = kNumTableEntriesLog2<Level>;
      if constexpr (Level == kLevels.back()) {
        return {
            .high = kTableAlignmentLog2 + kWidth - 1,
            .low = kTableAlignmentLog2,
        };
      } else {
        constexpr auto kNextRange = GetVirtualAddressBitRange<kNextLevel<Level>>();
        return {
            .high = kNextRange.high + 1 + kWidth - 1,
            .low = kNextRange.high + 1,
        };
      }
    }();
    static_assert(64 > kRange.high);
    static_assert(kRange.high >= kRange.low);
    static_assert(kRange.low >= kTableAlignmentLog2);
    return kRange;
  }

  static void AssertValidVirtualAddress(uint64_t vaddr) {
    if constexpr (kVirtualAddressExtension == VirtualAddressExtension::kCanonical) {
      ZX_DEBUG_ASSERT(kLowerVirtualAddressRangeEnd);
      ZX_DEBUG_ASSERT(kUpperVirtualAddressRangeStart);
      ZX_DEBUG_ASSERT_MSG(
          vaddr < *kLowerVirtualAddressRangeEnd || vaddr >= *kUpperVirtualAddressRangeStart,
          "virtual address %#" PRIx64 " must be within [0, %#" PRIx64 ") or [%#" PRIx64
          ", 0xffff'ffff'ffff'ffff]",
          vaddr, *kLowerVirtualAddressRangeEnd, *kUpperVirtualAddressRangeStart);
    } else if constexpr (kVirtualAddressExtension == VirtualAddressExtension::k0) {
      ZX_DEBUG_ASSERT(kLowerVirtualAddressRangeEnd);
      ZX_DEBUG_ASSERT_MSG(vaddr < *kLowerVirtualAddressRangeEnd,
                          "virtual address %#" PRIx64 " must be within [0, %#" PRIx64 ")", vaddr,
                          *kLowerVirtualAddressRangeEnd);
    } else if constexpr (kVirtualAddressExtension == VirtualAddressExtension::k1) {
      ZX_DEBUG_ASSERT(kUpperVirtualAddressRangeStart);
      ZX_DEBUG_ASSERT_MSG(vaddr >= *kUpperVirtualAddressRangeStart,
                          "virtual address %#" PRIx64 " must be within [%#" PRIx64
                          ", 0xffff'ffff'ffff'ffff]",
                          vaddr, *kUpperVirtualAddressRangeStart);
    }
  }

  /// A helper routine for `VisitPageTables()` starting a given level, allowing
  /// for a straightforward recursive(ish) definition.
  template <LevelType Level, typename PaddrToTableIo, typename Visitor>
  static VisitValue<Visitor, TableIo<PaddrToTableIo>> VisitPageTablesFrom(
      uint64_t table_paddr,          //
      PaddrToTableIo&& paddr_to_io,  //
      Visitor&& visitor,             //
      uint64_t vaddr) {              //
    static_assert(cpp20::find(kLevels.begin(), kLevels.end(), Level) != kLevels.end());

    ZX_DEBUG_ASSERT(table_paddr <= kMaxPhysicalAddress);
    auto io = paddr_to_io(table_paddr);

    constexpr VirtualAddressBitRange kBitRange = kVirtualAddressBitRange<Level>;
    uint32_t entry_index = fbl::ExtractBits<kBitRange.high, kBitRange.low, uint32_t>(vaddr);

    TableEntry<Level> entry = hwreg::RegisterAddr<TableEntry<Level>>(entry_index).ReadFrom(&io);
    if (auto result = visitor(io, entry, vaddr)) {
      return *result;
    }
    if constexpr (Level == kLevels.back()) {
      ZX_PANIC("Page table visitor did not terminate the walk; there are no more levels to visit");
    } else {
      return VisitPageTablesFrom<kNextLevel<Level>>(entry.address(),
                                                    std::forward<PaddrToTableIo>(paddr_to_io),
                                                    std::forward<Visitor>(visitor), vaddr);
    }
  }

  template <LevelType Level>
  static constexpr uint64_t TerminalAddress(const TableEntry<Level>& terminal, uint64_t vaddr) {
    ZX_DEBUG_ASSERT(terminal.terminal());
    constexpr uint64_t kAlignmentLog2 = kVirtualAddressBitRange<Level>.low;
    return terminal.address() | fbl::ExtractBits<kAlignmentLog2 - 1, 0, uint64_t>(vaddr);
  }

  template <LevelType Level>
  static constexpr PagingQueryResult::Page PageInfo(const TableEntry<Level>& terminal) {
    ZX_DEBUG_ASSERT(terminal.terminal());
    return {
        .paddr = terminal.address(),
        .size = kPageSize<Level>,
    };
  }
};

}  // namespace arch

#endif  // ZIRCON_KERNEL_LIB_ARCH_INCLUDE_LIB_ARCH_PAGING_H_