blob: d5c5ec3e044cda2a43fbbab0583ca7e056c99e4b [file] [log] [blame]
// Copyright 2017 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_FVM_FORMAT_H__
#define __LIB_FVM_FORMAT_H__
#include <digest/digest.h>
#include <stdlib.h>
#include <string.h>
#ifdef __cplusplus
#include <limits>
#include <type_traits>
#include <fbl/algorithm.h>
#include <gpt/gpt.h>
namespace fvm {
// Unique identifier mapped to a GPT partition that contains a FVM.
static constexpr uint64_t kMagic = 0x54524150204d5646;
// Current version of the FVM format being handled by this library.
static constexpr uint64_t kVersion = 0x00000001;
// Defines the block size of that the FVM driver exposes.
static constexpr uint64_t kBlockSize = 8192;
// Maximum number of virtual partitions that can be created.
static constexpr uint64_t kMaxVPartitions = 1024;
// Maximum size for a partition GUID.
static constexpr uint64_t kGuidSize = GPT_GUID_LEN;
// Maximum string length for virtual partition GUID.
static constexpr uint64_t kGuidStrLen = GPT_GUID_STRLEN;
// Maximum length allowed for a virtual partition name.
static constexpr uint16_t kMaxVPartitionNameLength = 24;
// Number of bits required for the VSlice address space.
static constexpr uint64_t kSliceEntryVSliceBits = 32;
// Number of bits required for the VPartition address space.
static constexpr uint64_t kSliceEntryVPartitionBits = 16;
// Maximum number of VSlices that can be addressed.
static constexpr uint64_t kMaxVSlices = 1ull << (kSliceEntryVSliceBits - 1);
namespace internal {
// Minimal safety checks for persisted data structures. Currently they are required to be trivial
// and standard layout.
template <typename T>
struct is_persistable {
static constexpr bool value = std::is_standard_layout<T>::value && std::is_trivial<T>::value;
// FVM block alignment properties for a given type.
template <typename T>
struct block_alignment {
static constexpr bool may_cross_boundary = (kBlockSize % sizeof(T)) != 0;
static constexpr bool ends_at_boundary = (sizeof(T) % kBlockSize);
} // namespace internal
// FVM header which describes the contents and layout of the volume manager.
struct Header {
// Unique identifier for this format type.
uint64_t magic;
// Version of the format.
uint64_t version;
// Number of slices which can be addressed and allocated by the virtual parititons.
uint64_t pslice_count;
// Size of the each slice in size.
uint64_t slice_size;
// Size of the volume the fvm described by this header is expecting to interact with.
uint64_t fvm_partition_size;
// Size of the partition table of the superblock the header describes, which contains
// partition metadata.
uint64_t vpartition_table_size;
// Size of the allocation table allocated size. This includes extra space allowing the
// fvm to grow as the underlying volume grows. The actual allocation table size, which defines
// the number of slices that can be addressed, is determined by |fvm_partition_size|.
uint64_t allocation_table_size;
// Use to determine over two copies(primary, secondary) of superblock, which one is the latest
// one.
uint64_t generation;
// Integrity check.
uint8_t hash[SHA256_DIGEST_LENGTH];
// Fill remainder of the block.
uint8_t reserved[0];
// TODO(gevalentino): Remove once all callsites have been updated.
using fvm_t = Header;
static_assert(internal::is_persistable<Header>::value && sizeof(Header) <= kBlockSize,
"fvm::Header must fit within one block, be trivial and match standard layout.");
// Represent an entry in the FVM Partition table, which is fixed size contiguous flat buffer.
struct VPartitionEntry {
// Returns a new blank entry.
static VPartitionEntry Create() {
VPartitionEntry entry;
return entry;
// Returns a new entry with a the respective |type|, |guid|, |name|, |slices| and |flags|.
// Note: This is subject to NRVO.
static VPartitionEntry Create(const uint8_t* type, const uint8_t* guid, uint32_t slices,
const char* name, uint32_t flags);
// Returns the allowed set of flags in |raw_flags|.
static uint32_t ParseFlags(uint32_t raw_flags);
// Returns true if the entry is allocated.
bool IsAllocated() const;
// Returns true if the entry is free.
bool IsFree() const;
// Releases the partition, marking it as free.
void Release();
// Returns true if the partition is should be treated as active..
bool IsActive() const;
// Returns true if the partition is flagged as inactive.
bool IsInactive() const;
// Marks this entry active status as |is_active|.
void SetActive(bool is_active);
// Mirrors GPT value.
uint8_t type[kGuidSize];
// Mirrors GPT value.
uint8_t guid[kGuidSize];
// Number of allocated slices.
uint32_t slices;
uint32_t flags;
// Partition name.
uint8_t name[fvm::kMaxVPartitionNameLength];
// TODO(gevalentino): remove after updating callsites.
using vpart_entry_t = VPartitionEntry;
static_assert(sizeof(VPartitionEntry) == 64, "Unchecked VPartitionEntry size change.");
"VPartitionEntry must be standard layout compilant and trivial.");
"VPartitionEntry must not cross block boundary.");
"VPartitionEntry table max size must end at block boundary.");
// A Slice Entry represents the allocation of a slice.
// Slice Entries are laid out in an array on disk. The index into this array
// determines the "physical slice" being accessed, where physical slices consist
// of all disk space immediately following the FVM metadata on an FVM partition.
struct SliceEntry {
// Returns a new blank entry.
static SliceEntry Create() {
SliceEntry entry;
return entry;
// Returns a slice entry with vpartition and vslice set.
static SliceEntry Create(uint64_t vpartition, uint64_t vslice);
// Returns true if this slice is assigned to a partition.
bool IsAllocated() const;
// Returns true if this slice is unassigned.
bool IsFree() const;
// Resets the slice entry, marking it as Free.
void Release();
// Returns the |vpartition| that owns this slice.
uint64_t VPartition() const;
// Returns the |vslice| of this slice. This represents the relative order of the slices
// assigned to |vpartition|. This is, the block device exposed to |partition| sees an array of
// all slices assigned to it, sorted by |vslice|.
uint64_t VSlice() const;
// Sets the contents of the slice entry to |partition| and |slice|.
void Set(uint64_t vpartition, uint64_t vslice);
// Packed entry, the format must remain obscure to the user.
uint64_t data;
using slice_entry_t = SliceEntry;
static_assert(sizeof(SliceEntry) == 8, "Unchecked SliceEntry size change.");
"VSliceEntry must meet persistable constraints.");
"VSliceEntry must not cross block boundary.");
// Partition Table.
// TODO(gevalentino): Upgrade this into a class that provides a view into a an unowned buffer, so
// the logic for calculating offsets and accessing respective entries is hidden.
struct PartitionTable {
// The Partition table starts at the next block after the respective header.
static constexpr uint64_t kOffset = kBlockSize;
// The Partition table size will finish at a block boundary, which is determined by the maximum
// allowed number of partitions.
static constexpr uint64_t kLength = sizeof(VPartitionEntry) * kMaxVPartitions;
// Allocation Table.
// TODO(gevalentino): Upgrade this into a class that provides a view into a an unowned buffer, so
// the logic for calculating offsets and accessing respective entries is hidden.
struct AllocationTable {
// The allocation table offset with respect to the start of the header.
static constexpr uint64_t kOffset = PartitionTable::kOffset + PartitionTable::kLength;
// Returns an over estimation of size required to allocate all slices in a fvm_volume of
// |fvm_disk_size| with a given |slice_size|. The returned value is always rounded to the next
// block boundary.
constexpr uint64_t Length(size_t fvm_disk_size, size_t slice_size) {
return fbl::round_up(sizeof(SliceEntry) * (fvm_disk_size / slice_size), kBlockSize);
// Remove this.
constexpr size_t kVPartTableOffset = PartitionTable::kOffset;
constexpr size_t kVPartTableLength = PartitionTable::kLength;
constexpr size_t kAllocTableOffset = AllocationTable::kOffset;
constexpr size_t AllocTableLength(size_t total_size, size_t slice_size) {
return fbl::round_up(sizeof(slice_entry_t) * (total_size / slice_size), fvm::kBlockSize);
constexpr size_t MetadataSize(size_t total_size, size_t slice_size) {
return kAllocTableOffset + AllocTableLength(total_size, slice_size);
constexpr size_t BackupStart(size_t total_size, size_t slice_size) {
return MetadataSize(total_size, slice_size);
constexpr size_t SlicesStart(size_t total_size, size_t slice_size) {
return 2 * MetadataSize(total_size, slice_size);
constexpr size_t UsableSlicesCount(size_t total_size, size_t slice_size) {
return (total_size - SlicesStart(total_size, slice_size)) / slice_size;
constexpr size_t BlocksToSlices(size_t slice_size, size_t block_size, size_t block_count) {
if (slice_size == 0 || slice_size < block_size) {
return 0;
const size_t kBlocksPerSlice = slice_size / block_size;
return (block_count + kBlocksPerSlice - 1) / kBlocksPerSlice;
constexpr size_t SlicesToBlocks(size_t slice_size, size_t block_size, size_t slice_count) {
return slice_count * slice_size / block_size;
// Defines the type of superblocks of an FVM. The key difference is how the offset from the
// beginning is calculated. They both share the same format.
enum class SuperblockType {
// Helper class for obtaining information about the format of a FVM, such as superblock offsets,
// metadata size, allocated sizes, etc.
// This class is copyable and moveable.
class FormatInfo {
// Returns a FormatInfo from a Fvm header and a disk size.
static FormatInfo FromSuperBlock(const fvm_t& superblock);
// Assumes a superblock created from the given disk for the given disk size,
// with slice size. (No Preallocated metadata headers for future growth).
static FormatInfo FromDiskSize(size_t disk_size, size_t slice_size);
// Without instantiating a SuperBlock, assumes that an fvm will be formatted initially with
// |initial_size| and eventually will grow up to |max_size| with |slice_size|.
static FormatInfo FromPreallocatedSize(size_t initial_size, size_t max_size, size_t slice_size);
FormatInfo() = default;
FormatInfo(const FormatInfo&) = default;
FormatInfo(FormatInfo&&) = default;
FormatInfo& operator=(const FormatInfo&) = default;
FormatInfo& operator=(FormatInfo&&) = default;
~FormatInfo() = default;
// Returns the size of the addressable metadata in a FVM header.
size_t metadata_size() const { return metadata_size_; }
// Returns the size of the allocated metadata SuperBlock. This may be bigger than
// |metadata_size_| if there was extra space pre allocated for allowing fvm growing.
size_t metadata_allocated_size() const { return metadata_allocated_size_; }
// Returns the number of addressable slices for the superblock, this is the number
// of physical slices.
size_t slice_count() const { return slice_count_; }
// Returns the size of each slice in the described block.
size_t slice_size() const { return slice_size_; }
// Returns the offset of the given superblock. The first superblock is considered primary,
// in terms of position.
size_t GetSuperblockOffset(SuperblockType type) const {
return (type == SuperblockType::kPrimary) ? 0 : metadata_allocated_size();
// Returns the offset from the start of the disk to beginning of |pslice| physical slice.
// Note: pslice is 1-indexed.
size_t GetSliceStart(size_t pslice) const {
return 2 * metadata_allocated_size_ + (pslice - 1) * slice_size_;
// Returns the maximum number of slices that can be addressed from the maximum possible size
// of the metatadata.
size_t GetMaxAllocatableSlices() const {
return (metadata_allocated_size() - kAllocTableOffset) / sizeof(SliceEntry);
// Returns the maximum number of slices that the allocated metadata can address for a given
// |disk_size|.
size_t GetMaxAddressableSlices(uint64_t disk_size) const {
size_t slice_count =
std::min(GetMaxAllocatableSlices(), UsableSlicesCount(disk_size, slice_size_));
// Because the allocation thable is 1-indexed and pslices are 0 indexed on disk,
// if the number of slices fit perfectly in the metadata, the allocated buffer won't be big
// enough to address them all. This only happens when the rounded up block value happens to
// match the disk size.
// TODO(gevalentino): Fix underlying cause and remove workaround.
if ((GetSliceStart(1) + slice_count * slice_size()) == metadata_allocated_size()) {
return slice_count;
// Returns the maximum partition size the current metadata can grow to.
size_t GetMaxPartitionSize() const {
return GetSliceStart(1) + GetMaxAllocatableSlices() * slice_size_;
// Size in bytes of addressable metadata.
size_t metadata_size_ = 0;
// Size in bytes of the allocated size of metadata.
size_t metadata_allocated_size_ = 0;
// Number of addressable slices.
size_t slice_count_ = 0;
// Size of the slices.
size_t slice_size_ = 0;
} // namespace fvm
#endif // __cplusplus
// Update's the metadata's hash field to accurately reflect
// the contents of metadata.
void fvm_update_hash(void* metadata, size_t metadata_size);
// Validate the FVM header information, and identify which
// copy of metadata (primary or backup) should be used for
// initial reading, if either.
// "out" is an optional output parameter which is equal to a
// valid copy of either metadata or backup on success.
zx_status_t fvm_validate_header(const void* metadata, const void* backup, size_t metadata_size,
const void** out);
#endif // __LIB_FVM_FORMAT_H__