blob: dad49c4465d70498c6bdf7b4393829aa01db9bc7 [file] [log] [blame]
// Copyright 2016 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.
// This file describes the on-disk format of MinFS
#include <limits.h>
#include <stdbool.h>
#include <stdint.h>
#include <zircon/assert.h>
#include <zircon/types.h>
#include <limits>
#include <fbl/algorithm.h>
namespace minfs {
// Type of a reference to block number, either absolute (able to index into disk directly) or
// relative to some entity (such as a file).
using blk_t = uint32_t;
// The type of an inode number, which may be used as an index into the inode table.
using ino_t = uint32_t;
// clang-format off
constexpr uint64_t kMinfsMagic0 = (0x002153466e694d21ULL);
constexpr uint64_t kMinfsMagic1 = (0x385000d3d3d3d304ULL);
// Current version of the format. The major version determines backwards-compatibility. The minor
// version can be freely incremented at any time and does not impact backwards-compatibility; the
// more often it is updated, the more granularly we can find out what the oldest driver that has
// touched a filesystem instance.
// Minimally, the minor version should be incremented whenever a (backwards-compatible) format
// change is made, but it can also be incremented when major logic changes are made in case there is
// chance of bugs being introduced and we would like to be able to detect if the filesystem has been
// touched by a potentially buggy driver. The kBlobfsCurrentMinorVersion is used to updated the
// oldest_minor_version field in the header when it is opened.
// See //src/storage/docs/ for more.
constexpr uint32_t kMinfsCurrentMajorVersion = 9u;
constexpr uint32_t kMinfsCurrentMinorVersion = 2u;
constexpr ino_t kMinfsRootIno = 1;
constexpr uint32_t kMinfsFlagClean = 0x00000001; // Currently unused,
constexpr uint32_t kMinfsFlagFVM = 0x00000002; // Mounted on FVM.
constexpr uint32_t kMinfsBlockSize = 8192;
constexpr uint32_t kMinfsBlockBits = (kMinfsBlockSize * 8);
constexpr uint32_t kMinfsInodeSize = 256;
constexpr uint32_t kMinfsInodesPerBlock = (kMinfsBlockSize / kMinfsInodeSize);
constexpr uint32_t kMinfsDirect = 16;
constexpr uint32_t kMinfsIndirect = 31;
constexpr uint32_t kMinfsDoublyIndirect = 1;
constexpr uint32_t kMinfsDirectPerIndirect = (kMinfsBlockSize / sizeof(blk_t));
constexpr uint32_t kMinfsDirectPerDindirect = kMinfsDirectPerIndirect * kMinfsDirectPerIndirect;
// It is not possible to have a block at or past this one due to the limitations of the inode and
// indirect blocks.
// TODO( Remove this artificial cap when MinFS can safely deal with files larger than 4GB.
constexpr uint64_t kMinfsMaxFileBlock =
(std::numeric_limits<uint32_t>::max() / kMinfsBlockSize) - 1;
constexpr uint64_t kMinfsMaxFileSize = kMinfsMaxFileBlock * kMinfsBlockSize;
constexpr uint32_t kMinfsTypeFile = 8;
constexpr uint32_t kMinfsTypeDir = 4;
// Number of blocks allocated to the superblock.
constexpr blk_t kSuperblockBlocks = 1;
// Number of blocks allocated to the backup superblock.
constexpr blk_t kBackupSuperblockBlocks = 1;
// Superblock location.
constexpr size_t kSuperblockStart = 0;
// NonFVM and FVM backup superblock locations.
constexpr size_t kNonFvmSuperblockBackup = 7;
constexpr size_t kFvmSuperblockBackup = 0x40000;
constexpr size_t kFVMBlockInodeBmStart = 0x10000;
constexpr size_t kFVMBlockDataBmStart = 0x20000;
constexpr size_t kFVMBlockInodeStart = 0x30000;
constexpr size_t kFVMBlockJournalStart = kFvmSuperblockBackup + kBackupSuperblockBlocks;
constexpr size_t kFVMBlockDataStart = 0x50000;
constexpr blk_t kJournalEntryHeaderMaxBlocks = 2040;
// clang-format on
constexpr uint32_t MinfsMagic(uint32_t T) { return 0xAA6f6e00 | T; }
constexpr uint32_t kMinfsMagicDir = MinfsMagic(kMinfsTypeDir);
constexpr uint32_t kMinfsMagicFile = MinfsMagic(kMinfsTypeFile);
constexpr uint32_t MinfsMagicType(uint32_t n) { return n & 0xFF; }
constexpr uint32_t kMinfsMagicPurged = 0xdeaddead;
struct Superblock {
uint64_t magic0;
uint64_t magic1;
// The format version is the version of the overall format. If this is larger than
// kCurrentMinfsMajorVersion the driver must not access the data.
// See also "oldest_minor_version" below and //src/storage/docs/
// The deprecated2 field used to store a minor version which was never used and should always
// be zero. Old versions of the MinFS driver will fail to mount if this field is nonzero when
// otherwise they may have been able to mount a filesystem of version 9.
uint32_t major_version;
uint32_t deprecated2;
uint32_t checksum; // Crc32 checksum of the contents of the info block.
uint32_t generation_count; // Generation count of backup superblock for debugging purpose.
uint32_t flags;
uint32_t block_size; // 8K typical.
uint32_t inode_size; // 256.
uint32_t block_count; // total number of data blocks.
uint32_t inode_count; // total number of inodes.
uint32_t alloc_block_count; // total number of allocated data blocks.
uint32_t alloc_inode_count; // total number of allocated inodes.
uint32_t ibm_block; // first blockno of inode allocation bitmap.
uint32_t abm_block; // first blockno of block allocation bitmap.
uint32_t ino_block; // first blockno of inode table.
uint32_t integrity_start_block; // first blockno available for journal + backup superblock.
uint32_t dat_block; // first blockno available for file data.
// The following fields are only valid with (flags & kMinfsFlagFVM):
uint32_t slice_size; // Underlying slice size.
uint32_t deprecated1; // Unused but not necessarily 0 (saved total vslices in old vers.).
uint32_t ibm_slices; // Slices allocated to inode bitmap.
uint32_t abm_slices; // Slices allocated to block bitmap.
uint32_t ino_slices; // Slices allocated to inode table.
uint32_t integrity_slices; // Slices allocated to integrity section (journal + backup
// superblock).
uint32_t dat_slices; // Slices allocated to file data section.
uint32_t unlinked_head; // Index to the first unlinked (but open) inode.
uint32_t unlinked_tail; // Index to the last unlinked (but open) inode.
// Records the oldest revision of Minfs code that has touched this volume. It can be used for
// example by fsck to determine what checks should be strict and what should be warnings. This
// should be incremented any time there's any change in how data is written to the device, even
// if it's backwards compatible. Compatibility is determined by major_version above.
// See //src/storage/docs/
uint32_t oldest_minor_version;
uint32_t reserved[2018];
uint32_t BlockSize() const {
// Either intentionally or unintenttionally, we do not want to change block
// size to anything other than kMinfsBlockSize yet. This is because changing
// block size might lead to format change and also because anything other
// than 8k is not well tested. So assert when we find block size other
// than 8k.
ZX_ASSERT(block_size == kMinfsBlockSize);
return block_size;
// Returns true if kMinfsFlagFVM is set for superblock.
bool GetFlagFvm() const { return (flags & kMinfsFlagFVM) == kMinfsFlagFVM; }
// Returns first block number from where inode bitmap starts.
uint64_t InodeBitmapStartBlock() const {
if (!GetFlagFvm()) {
return ibm_block;
return kFVMBlockInodeBmStart;
// Returns first block number from where data bitmap starts.
uint64_t DataBitmapStartBlock() const {
if (!GetFlagFvm()) {
return abm_block;
return kFVMBlockDataBmStart;
// Returns first block number from where inode table starts.
uint64_t InodeTableStartBlock() const {
if (!GetFlagFvm()) {
return ino_block;
return kFVMBlockInodeStart;
// Returns first block number from where data blocks starts.
uint64_t DataStartBlock() const {
if (!GetFlagFvm()) {
return dat_block;
return kFVMBlockDataStart;
// Returns first block number from where backup superblock starts.
uint64_t BackupSuperblockStart() const {
if (!GetFlagFvm()) {
return kNonFvmSuperblockBackup;
return kFvmSuperblockBackup;
static_assert(sizeof(Superblock) == kMinfsBlockSize, "minfs info size is wrong");
// Notes:
// - The inode bitmap, block bitmap, inode table, journal, and data
// regions must be in that order and may not overlap.
// - The abm has an entry for every block on the volume, including
// the info block (0), the bitmaps, etc.
// - Data blocks referenced from direct and indirect block tables
// in inodes are also relative to (0), but it is not legal for
// a block number of less than dat_block (start of data blocks)
// to be used.
// - Inode numbers refer to the inode in block:
// ino_block + ino / kMinfsInodesPerBlock
// at offset: ino % kMinfsInodesPerBlock.
// - Inode 0 is never used, should be marked allocated but ignored.
// The minimal number of slices to allocate a MinFS partition:
// Superblock, Inode bitmap, Data bitmap, Inode Table, Journal (2), and actual data.
constexpr size_t kMinfsMinimumSlices = 7;
constexpr uint64_t kMinfsDefaultInodeCount = 4096;
struct Inode {
uint32_t magic;
uint32_t size;
uint32_t block_count;
uint32_t link_count;
uint64_t create_time;
uint64_t modify_time;
uint32_t seq_num; // bumped when modified
uint32_t gen_num; // bumped when deleted
uint32_t dirent_count; // for directories
ino_t last_inode; // index to the previous unlinked inode
ino_t next_inode; // index to the next unlinked inode
uint32_t rsvd[3];
blk_t dnum[kMinfsDirect]; // direct blocks
blk_t inum[kMinfsIndirect]; // indirect blocks
blk_t dinum[kMinfsDoublyIndirect]; // doubly indirect blocks
static_assert(sizeof(Inode) == kMinfsInodeSize, "minfs inode size is wrong");
struct Dirent {
ino_t ino; // Inode number.
uint32_t reclen; // Low 28 bits: Length of record. High 4 bits: Flags
uint8_t namelen; // Length of the filename.
uint8_t type; // One of kMinfsType*.
char name[]; // The name bytes follow immediately. There is no trailing null.
constexpr uint8_t kMinfsDirentAlignment = 4;
constexpr uint8_t kMinfsDirentAlignmentMask = kMinfsDirentAlignment - 1;
static_assert(kMinfsDirentAlignment == alignof(Dirent), "Dirent alignment changed");
constexpr uint32_t kMinfsDirentSize = sizeof(Dirent);
// Returns the length of the Dirent structure required to hold a name of the given length. See
// also DirentReservedSize().
constexpr uint32_t DirentSize(uint8_t namelen) {
return kMinfsDirentSize + fbl::round_up<uint32_t>(namelen, kMinfsDirentAlignment);
constexpr uint8_t kMinfsMaxNameSize = 255;
// The largest acceptable value of DirentSize(dirent->namelen). The 'dirent->reclen' field may be
// larger after coalescing entries.
constexpr uint32_t kMinfsMaxDirentSize = DirentSize(kMinfsMaxNameSize);
constexpr uint32_t kMinfsMaxDirectorySize = fbl::round_down((1u << 20) - 1, kMinfsDirentAlignment);
static_assert(kMinfsMaxDirectorySize % kMinfsDirentAlignment == 0, "Invalid max directory size");
static_assert(kMinfsMaxDirectorySize < (1u << 20), "Max directory size too large");
// Storage for a Dirent padded out to the size for the maximum length. This is used as a buffer to
// read into with the correct alignment.
template <size_t max_size = kMinfsMaxDirentSize>
union DirentBuffer {
uint8_t raw[max_size];
Dirent dirent;
static_assert(kMinfsMaxNameSize >= NAME_MAX,
"MinFS names must be large enough to hold NAME_MAX characters");
constexpr uint32_t kMinfsReclenMask = 0x0FFFFFFF;
constexpr uint32_t kMinfsReclenLast = 0x80000000;
// Returns the data size reserved to this Dirent. For the last one, this will be the size from the
// beginning of it to the max space available for all records in a directory. For others, only
// part of this data may be used, see DirentSize().
constexpr uint32_t DirentReservedSize(Dirent* de, size_t off) {
return (de->reclen & kMinfsReclenLast) ? kMinfsMaxDirectorySize - static_cast<uint32_t>(off)
: de->reclen & kMinfsReclenMask;
static_assert(kMinfsMaxDirectorySize <= kMinfsReclenMask,
"MinFS directory size must be smaller than reclen mask");
// Notes:
// - dirents with ino of 0 are free, and skipped over on lookup.
// - reclen must be a multiple of 4.
// - The last record in a directory has the "kMinfsReclenLast" flag set. The actual size of this
// record can be computed from the offset at which this record starts. If the MAX_DIR_SIZE is
// increased, this 'last' record will also increase in size.
// blocksize 8K 16K 32K
// 16 dir = 128K 256K 512K
// 32 ind = 512M 1024M 2048M
// 1GB -> 128K blocks -> 16K bitmap (2K qword)
// 4GB -> 512K blocks -> 64K bitmap (8K qword)
// 32GB -> 4096K blocks -> 512K bitmap (64K qwords)
// Block Cache (bcache.c).
constexpr uint32_t kMinfsHashBits = (8);
// Sets kMinfsFlagFVM for given superblock.
constexpr void SetMinfsFlagFvm(Superblock& info) { info.flags |= kMinfsFlagFVM; }
constexpr uint64_t InodeBitmapBlocks(const Superblock& info) {
if ((info.flags & kMinfsFlagFVM) == kMinfsFlagFVM) {
auto blocks_per_slice = static_cast<blk_t>(info.slice_size / kMinfsBlockSize);
return info.ibm_slices * blocks_per_slice;
return info.abm_block - info.ibm_block;
constexpr uint64_t BlockBitmapBlocks(const Superblock& info) {
if ((info.flags & kMinfsFlagFVM) == kMinfsFlagFVM) {
auto blocks_per_slice = static_cast<blk_t>(info.slice_size / kMinfsBlockSize);
return info.abm_slices * blocks_per_slice;
return info.ino_block - info.abm_block;
constexpr uint64_t InodeBlocks(const Superblock& info) {
if ((info.flags & kMinfsFlagFVM) == kMinfsFlagFVM) {
auto blocks_per_slice = static_cast<blk_t>(info.slice_size / kMinfsBlockSize);
return info.ino_slices * blocks_per_slice;
return info.integrity_start_block - info.ino_block;
constexpr uint64_t JournalStartBlock(const Superblock& info) {
if ((info.flags & kMinfsFlagFVM) == kMinfsFlagFVM) {
return kFVMBlockJournalStart;
return info.integrity_start_block + kBackupSuperblockBlocks;
constexpr uint64_t JournalBlocks(const Superblock& info) {
if ((info.flags & kMinfsFlagFVM) == kMinfsFlagFVM) {
auto blocks_per_slice = static_cast<blk_t>(info.slice_size / kMinfsBlockSize);
return info.integrity_slices * blocks_per_slice - kBackupSuperblockBlocks;
return info.dat_block - info.integrity_start_block - kBackupSuperblockBlocks;
constexpr uint64_t DataBlocks(const Superblock& info) {
if ((info.flags & kMinfsFlagFVM) == kMinfsFlagFVM) {
auto blocks_per_slice = static_cast<blk_t>(info.slice_size / kMinfsBlockSize);
return info.dat_slices * blocks_per_slice;
return info.block_count;
constexpr uint64_t NonDataBlocks(const Superblock& info) {
return InodeBitmapBlocks(info) + BlockBitmapBlocks(info) + InodeBlocks(info) +
} // namespace minfs