blob: b02f9152794a9e8c43c8a49b2154ff68ce8a2b18 [file] [log] [blame]
// 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 "node-populator.h"
#include <stdint.h>
#include <zircon/types.h>
#include <blobfs/format.h>
#include <fbl/vector.h>
#include "allocator/allocator.h"
#include "extent-iterator.h"
namespace blobfs {
NodePopulator::NodePopulator(Allocator* allocator, fbl::Vector<ReservedExtent> extents,
fbl::Vector<ReservedNode> nodes)
: allocator_(allocator), extents_(std::move(extents)), nodes_(std::move(nodes)) {
ZX_DEBUG_ASSERT(extents_.size() <= kMaxBlobExtents);
ZX_DEBUG_ASSERT(nodes_.size() >=
NodeCountForExtents(static_cast<ExtentCountType>(extents_.size())));
}
uint32_t NodePopulator::NodeCountForExtents(ExtentCountType extent_count) {
bool out_of_line_extents = extent_count > kInlineMaxExtents;
uint32_t remaining_extents = out_of_line_extents ? extent_count - kInlineMaxExtents : 0;
return 1 + ((remaining_extents + kContainerMaxExtents - 1) / kContainerMaxExtents);
}
zx_status_t NodePopulator::Walk(OnNodeCallback on_node, OnExtentCallback on_extent) {
// The first node is not an extent container, and must be treated differently.
size_t node_count = 0;
uint32_t node_index = nodes_[node_count].index();
Inode* inode = allocator_->GetNode(node_index);
allocator_->MarkInodeAllocated(nodes_[node_count]);
ExtentContainer* container = nullptr;
uint32_t local_index = 0;
ExtentCountType extent_index = 0;
for (; extent_index < extents_.size(); extent_index++) {
bool next_container = false;
if (extent_index == kInlineMaxExtents) {
// At capacity for the extents inside the inode; moving to a container.
ZX_DEBUG_ASSERT_MSG(nodes_.size() > node_count, "Not enough nodes to hold extents");
inode->header.next_node = nodes_[node_count + 1].index();
next_container = true;
} else if (local_index == kContainerMaxExtents) {
// At capacity for the extents within a container; moving to another container.
ZX_DEBUG_ASSERT_MSG(nodes_.size() > node_count, "Not enough nodes to hold extents");
next_container = true;
}
if (next_container) {
// Acquire the next container node, and connect it to the
// previous node.
const ReservedNode& node = nodes_[node_count + 1];
uint32_t next = node.index();
uint32_t previous = nodes_[node_count].index();
allocator_->MarkContainerNodeAllocated(node, previous);
container = allocator_->GetNode(next)->AsExtentContainer();
node_count++;
local_index = 0;
}
// Copy the extent into the chosen container.
IterationCommand command = on_extent(extents_[extent_index]);
if (extent_index < kInlineMaxExtents) {
inode->extents[local_index] = extents_[extent_index].extent();
} else {
container->extents[local_index] = extents_[extent_index].extent();
container->extent_count++;
}
inode->extent_count++;
if (command == IterationCommand::Stop) {
break;
}
local_index++;
}
// Walk over all nodes in order *after* visiting all extents, now that
// we know how many of them are used.
for (size_t i = 0; i < node_count + 1; i++) {
on_node(nodes_[i]);
}
return ZX_OK;
}
} // namespace blobfs