zircon/system/ulib/inspect/include/lib/inspect/cpp/vmo/block.h

// Copyright 2019 The Fuchsia 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 LIB_INSPECT_CPP_VMO_BLOCK_H_
#define LIB_INSPECT_CPP_VMO_BLOCK_H_

#include <lib/inspect/cpp/vmo/limits.h>
#include <lib/stdcompat/optional.h>
#include <zircon/types.h>

#include <algorithm>
#include <cstdint>
#include <type_traits>

namespace inspect {
namespace internal {

enum class BlockType : uint8_t {
  kFree = 0,
  kReserved = 1,
  kHeader = 2,
  kNodeValue = 3,
  kIntValue = 4,
  kUintValue = 5,
  kDoubleValue = 6,
  kBufferValue = 7,
  kExtent = 8,
  kName = 9,
  kTombstone = 10,
  kArrayValue = 11,
  kLinkValue = 12,
  kBoolValue = 13,
  kStringReference = 14,
};

enum class PropertyBlockFormat : uint8_t {
  // The property is a UTF-8 string.
  kUtf8 = 0,

  // The property is a binary string of uint8_t.
  kBinary = 1
};

enum class ArrayBlockFormat : uint8_t {
  // The array stores N raw values in N slots.
  kDefault = 0,

  // The array is a linear histogram with N buckets and N+4 slots, which are:
  // - param_floor_value
  // - param_step_size
  // - underflow_bucket
  // - ...N buckets...
  // - overflow_bucket
  kLinearHistogram = 1,

  // The array is an exponential histogram with N buckets and N+5 slots, which are:
  // - param_floor_value
  // - param_initial_step
  // - param_step_multiplier
  // - underflow_bucket
  // - ...N buckets...
  // - overflow_bucket
  kExponentialHistogram = 2
};

enum class LinkBlockDisposition : uint8_t {
  // The linked sub-hierarchy root is a child of the LINK_VALUE's parent.
  kChild = 0,

  // The linked sub-hierarchy root's properties and children belong to the LINK_VALUE's parent.
  kInline = 1,
};

using BlockOrder = uint32_t;
using BlockIndex = uint64_t;

// Returns the smallest order such that (kMinOrderSize << order) >= size.
// Size must be non-zero.
constexpr BlockOrder FitOrder(size_t size) {
  auto ret = static_cast<size_t>(64 - __builtin_clzl(size - 1)) - kMinOrderShift;
  return static_cast<BlockOrder>(ret);
}

// Structure of the block header and payload.
struct Block final {
  union {
    uint64_t header;
    char header_data[8];
  };
  union {
    int64_t i64;
    uint64_t u64;
    double f64;
    char data[8];
  } payload;

  // Get the payload as a const char*.
  const char* payload_ptr() const { return static_cast<const char*>(payload.data); }

  // Get the payload as a char*.
  char* payload_ptr() { return static_cast<char*>(payload.data); }
};

static_assert(sizeof(Block) == 16, "Block header must be 16 bytes");
static_assert(sizeof(Block) == kMinOrderSize,
              "Minimum allocation size must exactly hold a block header");

// Describes the layout of a bit-field packed into a 64-bit word.
template <size_t begin, size_t end>
struct Field final {
  static_assert(begin < sizeof(uint64_t) * 8, "begin is out of bounds");
  static_assert(end < sizeof(uint64_t) * 8, "end is out of bounds");
  static_assert(begin <= end, "begin must not be larger than end");
  static_assert(end - begin + 1 < 64, "must be a part of a word, not a whole word");

  static constexpr uint64_t kMask = (uint64_t(1) << (end - begin + 1)) - 1;

  template <typename T>
  static constexpr uint64_t Make(T value) {
    return static_cast<uint64_t>(value) << begin;
  }

  template <typename U>
  static constexpr U Get(uint64_t word) {
    static_assert(sizeof(U) >= SizeInBytes(), "attempt to narrow value lossily");
    return static_cast<U>((word >> (begin % 64)) & kMask);
  }

  static constexpr void Set(uint64_t* word, uint64_t value) {
    *word = (*word & ~(kMask << begin)) | (value << begin);
  }

  // The size of a field in bytes. This will truncate the size of values which
  // are not byte aligned.
  static constexpr size_t SizeInBytes() { return ((end + 1) - begin) / 8; }
};

// Describes the base fields present for all blocks.
struct BlockFields {
  using Order = Field<0, 3>;
  using Type = Field<8, 15>;
};

struct HeaderBlockFields final : public BlockFields {
  using Version = Field<16, 31>;
  using MagicNumber = Field<32, 63>;
};

struct FreeBlockFields final : public BlockFields {
  using NextFreeBlock = Field<16, 39>;
};

// Describes the fields common to all value blocks.
struct ValueBlockFields final : public BlockFields {
  using ParentIndex = Field<16, 39>;
  using NameIndex = Field<40, 63>;
};

struct StringReferenceBlockFields final : public BlockFields {
  using NextExtentIndex = Field<16, 39>;
  using ReferenceCount = Field<40, 63>;
};

struct StringReferenceBlockPayload final {
  using TotalLength = Field<0, 31>;
};

struct PropertyBlockPayload final {
  using TotalLength = Field<0, 31>;
  using ExtentIndex = Field<32, 59>;
  using Flags = Field<60, 63>;
};

// Describes the fields for ARRAY_VALUE payloads.
struct ArrayBlockPayload final {
  using EntryType = Field<0, 3>;
  using Flags = Field<4, 7>;
  using Count = Field<8, 15>;
};

struct ExtentBlockFields final : public BlockFields {
  using NextExtentIndex = Field<16, 39>;
};

struct NameBlockFields final : public BlockFields {
  using Length = Field<16, 27>;
};

struct LinkBlockPayload final {
  using ContentIndex = Field<0, 19>;
  using Flags = Field<60, 63>;
};

constexpr BlockOrder GetOrder(const Block* block) {
  return BlockFields::Order::Get<BlockOrder>(block->header);
}

constexpr BlockType GetType(const Block* block) {
  return BlockFields::Type::Get<BlockType>(block->header);
}

constexpr size_t PayloadCapacity(BlockOrder order) {
  return OrderToSize(order) - sizeof(Block::header);
}

constexpr cpp17::optional<size_t> SizeForArrayPayload(const BlockType payload_type) {
  switch (payload_type) {
    case BlockType::kIntValue:
    case BlockType::kUintValue:
    case BlockType::kDoubleValue:
      return {sizeof(uint64_t)};
    case BlockType::kStringReference:
      return {sizeof(uint32_t)};

    default:
      return {};
  }
}

constexpr cpp17::optional<size_t> ArrayCapacity(BlockOrder order, BlockType type) {
  const auto size = SizeForArrayPayload(type);
  if (size.has_value()) {
    return (OrderToSize(order) - sizeof(Block::header) - sizeof(Block::payload)) / size.value();
  }

  return {};
}

constexpr size_t BlockSizeForPayload(size_t payload_size) {
  return std::max(payload_size + sizeof(Block::header), kMinOrderSize);
}

// For array types, get a pointer to a specific slot in the array.
// Because the return type is a pointer to a value inside the input block,
// the output type needs to be const if the input block is const.
// If the index is out of bounds, return nullptr.
// If the input block is not an array type, return nullptr.
template <typename T, typename B,
          // check that B is a Block* of some kind
          typename = std::enable_if_t<std::is_same<typename std::decay_t<B>, Block>::value>,
          // check that the return pointer is at least as const as the input block
          typename = std::enable_if_t<std::is_const<B>::value ? std::is_const<T>::value : true>>
constexpr T* GetArraySlot(B* block, size_t index) {
  if (GetType(block) != BlockType::kArrayValue) {
    return nullptr;
  }

  const auto capacity = ArrayCapacity(
      GetOrder(block), ArrayBlockPayload::EntryType::Get<BlockType>(block->payload.u64));
  if (!capacity.has_value()) {
    return nullptr;
  }

  if (index > capacity.value()) {
    return nullptr;
  }

  T* arr = reinterpret_cast<T*>(&block->payload);
  return arr + index + (sizeof(uint64_t) / sizeof(T)) /* skip inline payload */;
}

// Get a BlockIndex pointing to a string reference from a string array `Block`.
//
// This can't return a pointer because the VMO representation of block indexes is smaller
// than the C++ one, so a string reference's BlockIndex written directly to the array
// through the pointer would overwrite other data.
inline cpp17::optional<BlockIndex> GetArraySlotForString(const Block* block, size_t index) {
  const auto* tmp = GetArraySlot<const uint32_t>(block, index);
  if (tmp == nullptr) {
    return {};
  }

  return static_cast<const BlockIndex>(*tmp);
}

// Set the value of a string array at `index_into_array` with a `BlockIndex`, `value`,
// pointing to a string reference.
//
// Necessary to have a helper function instead of returning a mutable pointer into the array
// for the reasons noted on `GetArraySlotForString`.
inline void SetArraySlotForString(Block* block, size_t index_into_array, BlockIndex value) {
  auto* slot = GetArraySlot<uint32_t>(block, index_into_array);
  if (slot == nullptr) {
    return;
  }

  auto value_as_u32 = static_cast<uint32_t>(value);
  *slot = value_as_u32;
}

constexpr size_t kMaxPayloadSize = kMaxOrderSize - sizeof(Block::header);

inline void SetHeaderVmoSize(Block* block, size_t headerVmoSize) {
  if (GetType(block) != BlockType::kHeader || GetOrder(block) != kVmoHeaderOrder) {
    return;
  }
  // The size field is located at the start of the first block after header and payload.
  memcpy(block->payload_ptr() + sizeof(block->payload), &headerVmoSize, sizeof(size_t));
}

inline cpp17::optional<size_t> GetHeaderVmoSize(const Block* block) {
  if (GetType(block) != BlockType::kHeader || GetOrder(block) != kVmoHeaderOrder) {
    return {};
  }
  size_t size = 0;
  // The size field is located at the start of the first block after header and payload.
  memcpy(&size, block->payload_ptr() + sizeof(block->payload), sizeof(size_t));
  return {size};
}

}  // namespace internal
}  // namespace inspect

#endif  // LIB_INSPECT_CPP_VMO_BLOCK_H_