text: // Copyright 2021 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_PHYS_LIB_MEMALLOC_INCLUDE_LIB_MEMALLOC_RANGE_H_
  #define ZIRCON_KERNEL_PHYS_LIB_MEMALLOC_INCLUDE_LIB_MEMALLOC_RANGE_H_
  
  #include <lib/fit/function.h>
  #include <lib/stdcompat/span.h>
  #include <zircon/boot/image.h>
  
  #include <algorithm>
  #include <array>
  #include <string_view>
  
  namespace memalloc {
  
  constexpr uint64_t kMinExtendedTypeValue =
      static_cast<uint64_t>(std::numeric_limits<uint32_t>::max()) + 1;
  
  // The type of a physical memory range. Represented by 64 bits, the lower 2^32
  // values in the space are reserved for memory range types defined in the ZBI
  // spec, the "base types"; the types in the upper half are referred to as
  // "extended types", and increment from kMinExtendedTypeValue in value.
  //
  // As is detailed in the ZBI spec regarding overlaps, among the base types,
  // kReserved and kPeripheral ranges have the highest precedence, in that order.
  // Further, by definition here, an extended type is only permitted to overlap
  // with kFreeRam or the same type.
  enum class Type : uint64_t {
    //
    // ZBI memory range types:
    //
  
    kFreeRam = ZBI_MEM_RANGE_RAM,
    kPeripheral = ZBI_MEM_RANGE_PERIPHERAL,
    kReserved = ZBI_MEM_RANGE_RESERVED,
  
    //
    // Extended types:
    //
  
    // Reserved for internal bookkeeping.
    kPoolBookkeeping = kMinExtendedTypeValue,
  
    // The beginning region of memory, discarded so that accidental, relative
    // access off of a null pointer is unlikely to touch any memory that might
    // be allocated.
    kNullPointerRegion,
  
    // The phys kernel memory image.
    kPhysKernel,
  
    // The kernel memory image.
    kKernel,
  
    // The kernel memory image at a fixed address of 1MiB.
    kFixedAddressKernel,
  
    // A (decompressed) STORAGE_KERNEL ZBI payload.
    kKernelStorage,
  
    // The data ZBI, as placed by the bootloader.
    kDataZbi,
  
    // Data structures related to legacy boot protocols.
    kLegacyBootData,
  
    // Identity-mapping page tables.
    kIdentityPageTables,
  
    // General scratch space used by the phys kernel, but that which is free for
    // the next kernel as of hand-off.
    kPhysScratch,
  
    // A generic allocated type for Pool tests.
    kPoolTestPayload,
  
    // A generic allocated type for ZBI tests.
    kZbiTestPayload,
  
    // Memory carved out for the kernel.test.ram.reserve boot option.
    kTestRamReserve,
  
    // Memory carved out for the ZBI_TYPE_NVRAM region.
    kNvram,
  
    // A placeholder value signifying the last extended type. It must not be used
    // as an actual type value.
    kMaxExtended,
  };
  
  static_assert(static_cast<uint64_t>(Type::kFreeRam) < kMinExtendedTypeValue);
  static_assert(static_cast<uint64_t>(Type::kPeripheral) < kMinExtendedTypeValue);
  static_assert(static_cast<uint64_t>(Type::kReserved) < kMinExtendedTypeValue);
  
  constexpr uint64_t kMaxExtendedTypeValue = static_cast<uint64_t>(Type::kMaxExtended);
  constexpr size_t kNumExtendedTypes = kMaxExtendedTypeValue - kMinExtendedTypeValue;
  constexpr size_t kNumBaseTypes = 3;
  
  std::string_view ToString(Type type);
  
  constexpr bool IsExtendedType(Type type) {
    return static_cast<uint64_t>(type) >= kMinExtendedTypeValue;
  }
  
  // A memory range type that is layout-compatible to zbi_mem_range_t, but with
  // the benefit of being able to use extended types.
  struct Range {
    uint64_t addr;
    uint64_t size;
    Type type;
  
    // The end of the memory range. This method may only be called if addr + size
    // has been normalized to not overflow.
    constexpr uint64_t end() const { return addr + size; }
  
    constexpr bool operator==(const Range& other) const {
      return addr == other.addr && size == other.size && type == other.type;
    }
    constexpr bool operator!=(const Range& other) const { return !(*this == other); }
  
    // Gives a lexicographic order on Range.
    constexpr bool operator<(const Range& other) const {
      return addr < other.addr || (addr == other.addr && size < other.size);
    }
  };
  
  // We have constrained Type so that the ZBI memory type's value space
  // identically embeds into the lower 2^32 values of Type; the upper 2^32 values
  // is reserved for Type's extensions. Accordingly, in order to coherently
  // recast a zbi_mem_range_t as a Range, the former's `reserved` field -
  // which, layout-wise, corresponds to the upper half of Type - must be zeroed
  // out.
  cpp20::span<Range> AsRanges(cpp20::span<zbi_mem_range_t> ranges);
  
  namespace internal {
  
  // Effectively just a span and an iterator. This is used internally to iterate
  // over a variable number of range arrays.
  struct RangeIterationContext {
    RangeIterationContext() = default;
  
    // Lexicographically sorts the ranges on construction.
    explicit RangeIterationContext(cpp20::span<Range> ranges) : ranges_(ranges), it_(ranges.begin()) {
      std::sort(ranges_.begin(), ranges_.end());
    }
  
    cpp20::span<Range> ranges_;
    typename cpp20::span<Range>::iterator it_;
  };
  
  }  // namespace internal
  
  }  // namespace memalloc
  
  #endif  // ZIRCON_KERNEL_PHYS_LIB_MEMALLOC_INCLUDE_LIB_MEMALLOC_RANGE_H_
  