1 // Copyright 2018 The Fuchsia Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include <minfs/transaction-limits.h>
6
7 namespace minfs {
8
GetBlockBitmapBlocks(const Superblock & info)9 blk_t GetBlockBitmapBlocks(const Superblock& info) {
10 ZX_DEBUG_ASSERT(info.ino_block >= info.abm_block);
11 blk_t bitmap_blocks = info.ino_block - info.abm_block;
12
13 if (info.flags & kMinfsFlagFVM) {
14 const blk_t kBlocksPerSlice = static_cast<blk_t>(info.slice_size / kMinfsBlockSize);
15 bitmap_blocks = info.abm_slices * kBlocksPerSlice;
16 }
17
18 return bitmap_blocks;
19 }
20
GetRequiredBlockCount(size_t offset,size_t length,blk_t * num_req_blocks)21 zx_status_t GetRequiredBlockCount(size_t offset, size_t length, blk_t* num_req_blocks) {
22 if (length == 0) {
23 // Return early if no data needs to be written.
24 *num_req_blocks = 0;
25 return ZX_OK;
26 }
27
28 // Determine which range of direct blocks will be accessed given offset and length,
29 // and add to total.
30 blk_t first_direct = static_cast<blk_t>(offset / kMinfsBlockSize);
31 blk_t last_direct = static_cast<blk_t>((offset + length - 1) / kMinfsBlockSize);
32 blk_t reserve_blocks = last_direct - first_direct + 1;
33
34 if (last_direct >= kMinfsDirect) {
35 // If direct blocks go into indirect range, adjust the indices accordingly.
36 first_direct = fbl::max(first_direct, kMinfsDirect) - kMinfsDirect;
37 last_direct -= kMinfsDirect;
38
39 // Calculate indirect blocks containing first and last direct blocks, and add to total.
40 blk_t first_indirect = first_direct / kMinfsDirectPerIndirect;
41 blk_t last_indirect = last_direct / kMinfsDirectPerIndirect;
42 reserve_blocks += last_indirect - first_indirect + 1;
43
44 if (last_indirect >= kMinfsIndirect) {
45 // If indirect blocks go into doubly indirect range, adjust the indices accordingly.
46 first_indirect = fbl::max(first_indirect, kMinfsIndirect) - kMinfsIndirect;
47 last_indirect -= kMinfsIndirect;
48
49 // Calculate doubly indirect blocks containing first/last indirect blocks,
50 // and add to total
51 blk_t first_dindirect = first_indirect / kMinfsDirectPerIndirect;
52 blk_t last_dindirect = last_indirect / kMinfsDirectPerIndirect;
53 reserve_blocks += last_dindirect - first_dindirect + 1;
54
55 if (last_dindirect >= kMinfsDoublyIndirect) {
56 // We cannot allocate blocks which exceed the doubly indirect range.
57 return ZX_ERR_OUT_OF_RANGE;
58 }
59 }
60 }
61
62 *num_req_blocks = reserve_blocks;
63 return ZX_OK;
64 }
65
TransactionLimits(const Superblock & info)66 TransactionLimits::TransactionLimits(const Superblock& info) {
67 CalculateDataBlocks();
68 CalculateJournalBlocks(GetBlockBitmapBlocks(info));
69 }
70
CalculateDataBlocks()71 void TransactionLimits::CalculateDataBlocks() {
72 // If we ever increase the number of doubly indirect blocks, we will need to update this offset
73 // to be 1 byte before the end of the first doubly indirect block.
74 constexpr blk_t kOffset =
75 (kMinfsDirect + (kMinfsIndirect * kMinfsDirectPerIndirect)) * kMinfsBlockSize - 1;
76
77 // This calculation ignores the fact that directory size is capped at |kMinfsMaxDirectorySize|,
78 // because following that constraint makes it a little harder to predict where the most
79 // significant cross-block write would be. This means we may overestimate the maximum number of
80 // directory blocks by some amount, but this is better than an understimate.
81 blk_t max_directory_blocks;
82 ZX_ASSERT(GetRequiredBlockCount(kOffset, kMinfsMaxDirentSize, &max_directory_blocks) == ZX_OK);
83 ZX_ASSERT(GetRequiredBlockCount(kOffset, kMaxWriteBytes, &max_data_blocks_) == ZX_OK);
84
85 blk_t direct_blocks = (fbl::round_up(kMaxWriteBytes, kMinfsBlockSize) / kMinfsBlockSize) + 1;
86 blk_t max_indirect_blocks = max_data_blocks_ - direct_blocks;
87
88 max_meta_data_blocks_ = fbl::max(max_directory_blocks, max_indirect_blocks);
89 }
90
CalculateJournalBlocks(blk_t block_bitmap_blocks)91 void TransactionLimits::CalculateJournalBlocks(blk_t block_bitmap_blocks) {
92 max_entry_data_blocks_ = kMaxSuperblockBlocks + kMaxInodeBitmapBlocks + block_bitmap_blocks
93 + kMaxInodeTableBlocks + max_meta_data_blocks_;
94
95 // Ensure we have enough space to fit all the block numbers that may be updated in one
96 // transaction. This may spill over into multiple blocks.
97 blk_t header_blocks = 1;
98 if (max_entry_data_blocks_ > kJournalEntryHeaderMaxBlocks) {
99 header_blocks += fbl::round_up((max_entry_data_blocks_ - kJournalEntryHeaderMaxBlocks),
100 kMinfsDirectPerIndirect) / kMinfsDirectPerIndirect;
101 }
102
103 // For revocation records, we need to know the maximum number of metadata blocks within the
104 // data section of Minfs that can be deleted within one operation. This is either a directory
105 // vnode's maximum possible number of data blocks + indirect blocks, or a data vnode's maximum
106 // possible number of indirect blocks.
107 blk_t maximum_directory_blocks;
108 ZX_ASSERT(GetRequiredBlockCount(0, kMinfsMaxDirectorySize, &maximum_directory_blocks) == ZX_OK);
109 blk_t maximum_indirect_blocks = kMinfsIndirect + kMinfsDoublyIndirect * kMinfsDirectPerIndirect;
110 blk_t revocation_blocks = fbl::round_up(fbl::max(maximum_directory_blocks,
111 maximum_indirect_blocks),
112 kMinfsDirectPerIndirect)
113 / kMinfsDirectPerIndirect;
114
115 blk_t commit_blocks = 1;
116
117 max_entry_blocks_ = header_blocks + revocation_blocks + max_entry_data_blocks_ + commit_blocks;
118 min_journal_blocks_ = max_entry_blocks_ + kJournalMetadataBlocks;
119 rec_journal_blocks_ = fbl::max(min_journal_blocks_, kDefaultJournalBlocks);
120 }
121
122 } // namespace minfs