zircon/system/ulib/minfs/transaction_limits.cc

// Copyright 2018 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.

#include <zircon/assert.h>

#include <fbl/algorithm.h>
#include <fs/journal/format.h>
#include <minfs/transaction_limits.h>

namespace minfs {

blk_t GetBlockBitmapBlocks(const Superblock& info) {
  ZX_DEBUG_ASSERT(info.ino_block >= info.abm_block);
  blk_t bitmap_blocks = info.ino_block - info.abm_block;

  if (info.flags & kMinfsFlagFVM) {
    const blk_t kBlocksPerSlice = static_cast<blk_t>(info.slice_size / kMinfsBlockSize);
    bitmap_blocks = info.abm_slices * kBlocksPerSlice;
  }

  return bitmap_blocks;
}

zx_status_t GetRequiredBlockCount(size_t offset, size_t length, blk_t* num_req_blocks) {
  if (length == 0) {
    // Return early if no data needs to be written.
    *num_req_blocks = 0;
    return ZX_OK;
  }

  // Determine which range of direct blocks will be accessed given offset and length,
  // and add to total.
  blk_t first_direct = static_cast<blk_t>(offset / kMinfsBlockSize);
  blk_t last_direct = static_cast<blk_t>((offset + length - 1) / kMinfsBlockSize);
  blk_t reserve_blocks = last_direct - first_direct + 1;

  if (last_direct >= kMinfsDirect) {
    // If direct blocks go into indirect range, adjust the indices accordingly.
    first_direct = fbl::max(first_direct, kMinfsDirect) - kMinfsDirect;
    last_direct -= kMinfsDirect;

    // Calculate indirect blocks containing first and last direct blocks, and add to total.
    blk_t first_indirect = first_direct / kMinfsDirectPerIndirect;
    blk_t last_indirect = last_direct / kMinfsDirectPerIndirect;
    reserve_blocks += last_indirect - first_indirect + 1;

    if (last_indirect >= kMinfsIndirect) {
      // If indirect blocks go into doubly indirect range, adjust the indices accordingly.
      first_indirect = fbl::max(first_indirect, kMinfsIndirect) - kMinfsIndirect;
      last_indirect -= kMinfsIndirect;

      // Calculate doubly indirect blocks containing first/last indirect blocks,
      // and add to total
      blk_t first_dindirect = first_indirect / kMinfsDirectPerIndirect;
      blk_t last_dindirect = last_indirect / kMinfsDirectPerIndirect;
      reserve_blocks += last_dindirect - first_dindirect + 1;

      if (last_dindirect >= kMinfsDoublyIndirect) {
        // We cannot allocate blocks which exceed the doubly indirect range.
        return ZX_ERR_OUT_OF_RANGE;
      }
    }
  }

  *num_req_blocks = reserve_blocks;
  return ZX_OK;
}

TransactionLimits::TransactionLimits(const Superblock& info) {
  CalculateDataBlocks();
  CalculateIntegrityBlocks(GetBlockBitmapBlocks(info));
}

void TransactionLimits::CalculateDataBlocks() {
  // If we ever increase the number of doubly indirect blocks, we will need to update this offset
  // to be 1 byte before the end of the first doubly indirect block.
  constexpr blk_t kOffset =
      (kMinfsDirect + (kMinfsIndirect * kMinfsDirectPerIndirect)) * kMinfsBlockSize - 1;

  // This calculation ignores the fact that directory size is capped at |kMinfsMaxDirectorySize|,
  // because following that constraint makes it a little harder to predict where the most
  // significant cross-block write would be. This means we may overestimate the maximum number of
  // directory blocks by some amount, but this is better than an understimate.
  blk_t max_directory_blocks;
  ZX_ASSERT(GetRequiredBlockCount(kOffset, kMinfsMaxDirentSize, &max_directory_blocks) == ZX_OK);
  ZX_ASSERT(GetRequiredBlockCount(kOffset, kMaxWriteBytes, &max_data_blocks_) == ZX_OK);

  blk_t direct_blocks = (fbl::round_up(kMaxWriteBytes, kMinfsBlockSize) / kMinfsBlockSize) + 1;
  blk_t max_indirect_blocks = max_data_blocks_ - direct_blocks;

  max_meta_data_blocks_ = fbl::max(max_directory_blocks, max_indirect_blocks);
}

void TransactionLimits::CalculateIntegrityBlocks(blk_t block_bitmap_blocks) {
  max_entry_data_blocks_ = kMaxSuperblockBlocks + kMaxInodeBitmapBlocks + block_bitmap_blocks +
                           kMaxInodeTableBlocks + max_meta_data_blocks_;

  // Ensure we have enough space to fit all the block numbers that may be updated in one
  // transaction. This may spill over into multiple blocks.
  blk_t header_blocks = 1;
  if (max_entry_data_blocks_ > fs::kMaxBlockDescriptors) {
    header_blocks += fbl::round_up((max_entry_data_blocks_ - fs::kMaxBlockDescriptors),
                                   kMinfsDirectPerIndirect) /
                     kMinfsDirectPerIndirect;
  }

  // For revocation records, we need to know the maximum number of metadata blocks within the
  // data section of Minfs that can be deleted within one operation. This is either a directory
  // vnode's maximum possible number of data blocks + indirect blocks, or a data vnode's maximum
  // possible number of indirect blocks.
  blk_t maximum_directory_blocks;
  ZX_ASSERT(GetRequiredBlockCount(0, kMinfsMaxDirectorySize, &maximum_directory_blocks) == ZX_OK);
  blk_t maximum_indirect_blocks = kMinfsIndirect + kMinfsDoublyIndirect * kMinfsDirectPerIndirect;
  blk_t revocation_blocks =
      fbl::round_up(fbl::max(maximum_directory_blocks, maximum_indirect_blocks),
                    kMinfsDirectPerIndirect) /
      kMinfsDirectPerIndirect;

  blk_t commit_blocks = 1;

  max_entry_blocks_ = header_blocks + revocation_blocks + max_entry_data_blocks_ + commit_blocks;
  min_integrity_blocks_ = max_entry_blocks_ + kJournalMetadataBlocks + kBackupSuperblockBlocks;
  rec_integrity_blocks_ = fbl::max(min_integrity_blocks_, kDefaultJournalBlocks);
}

}  // namespace minfs