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 <stdint.h>
6
7 #include <blobfs/allocator.h>
8 #include <blobfs/format.h>
9 #include <blobfs/iterator/extent-iterator.h>
10 #include <blobfs/iterator/node-populator.h>
11 #include <fbl/vector.h>
12 #include <zircon/types.h>
13
14 namespace blobfs {
15
NodePopulator(Allocator * allocator,fbl::Vector<ReservedExtent> extents,fbl::Vector<ReservedNode> nodes)16 NodePopulator::NodePopulator(Allocator* allocator, fbl::Vector<ReservedExtent> extents,
17 fbl::Vector<ReservedNode> nodes)
18 : allocator_(allocator), extents_(std::move(extents)), nodes_(std::move(nodes)) {
19 ZX_DEBUG_ASSERT(extents_.size() <= kMaxBlobExtents);
20 ZX_DEBUG_ASSERT(nodes_.size() >=
21 NodeCountForExtents(static_cast<ExtentCountType>(extents_.size())));
22 }
23
NodeCountForExtents(ExtentCountType extent_count)24 uint32_t NodePopulator::NodeCountForExtents(ExtentCountType extent_count) {
25 bool out_of_line_extents = extent_count > kInlineMaxExtents;
26 uint32_t remaining_extents = out_of_line_extents ? extent_count - kInlineMaxExtents : 0;
27 return 1 + ((remaining_extents + kContainerMaxExtents - 1) / kContainerMaxExtents);
28 }
29
Walk(OnNodeCallback on_node,OnExtentCallback on_extent)30 zx_status_t NodePopulator::Walk(OnNodeCallback on_node, OnExtentCallback on_extent) {
31 // The first node is not an extent container, and must be treated differently.
32 size_t node_count = 0;
33 uint32_t node_index = nodes_[node_count].index();
34
35 Inode* inode = allocator_->GetNode(node_index);
36 allocator_->MarkInodeAllocated(nodes_[node_count]);
37
38 ExtentContainer* container = nullptr;
39 uint32_t local_index = 0;
40 ExtentCountType extent_index = 0;
41 for (; extent_index < extents_.size(); extent_index++) {
42 bool next_container = false;
43 if (extent_index == kInlineMaxExtents) {
44 // At capacity for the extents inside the inode; moving to a container.
45 ZX_DEBUG_ASSERT_MSG(nodes_.size() > node_count, "Not enough nodes to hold extents");
46 inode->header.next_node = nodes_[node_count + 1].index();
47 next_container = true;
48 } else if (local_index == kContainerMaxExtents) {
49 // At capacity for the extents within a container; moving to another container.
50 ZX_DEBUG_ASSERT_MSG(nodes_.size() > node_count, "Not enough nodes to hold extents");
51 next_container = true;
52 }
53
54 if (next_container) {
55 // Acquire the next container node, and connect it to the
56 // previous node.
57 const ReservedNode& node = nodes_[node_count + 1];
58 uint32_t next = node.index();
59 uint32_t previous = nodes_[node_count].index();
60 allocator_->MarkContainerNodeAllocated(node, previous);
61 container = allocator_->GetNode(next)->AsExtentContainer();
62
63 node_count++;
64 local_index = 0;
65 }
66
67 // Copy the extent into the chosen container.
68 IterationCommand command = on_extent(extents_[extent_index]);
69 if (extent_index < kInlineMaxExtents) {
70 inode->extents[local_index] = extents_[extent_index].extent();
71 } else {
72 container->extents[local_index] = extents_[extent_index].extent();
73 container->extent_count++;
74 }
75
76 inode->extent_count++;
77
78 if (command == IterationCommand::Stop) {
79 break;
80 }
81
82 local_index++;
83 }
84
85 // Walk over all nodes in order *after* visiting all extents, now that
86 // we know how many of them are used.
87 for (size_t i = 0; i < node_count + 1; i++) {
88 on_node(nodes_[i]);
89 }
90
91 return ZX_OK;
92 }
93
94 } // namespace blobfs
95