| // Copyright 2017 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. | |
| // Tests Minfs Allocator and AllocatorReservation behavior. | |
| #include "src/storage/minfs/allocator/allocator.h" | |
| #include <lib/zx/result.h> | |
| #include <lib/zx/vmo.h> | |
| #include <zircon/assert.h> | |
| #include <zircon/errors.h> | |
| #include <algorithm> | |
| #include <cstddef> | |
| #include <cstdint> | |
| #include <cstring> | |
| #include <memory> | |
| #include <utility> | |
| #include <fbl/array.h> | |
| #include <gtest/gtest.h> | |
| #include "src/storage/lib/buffer/block_buffer.h" | |
| #include "src/storage/lib/buffer/owned_vmoid.h" | |
| #include "src/storage/lib/operation/operation.h" | |
| #include "src/storage/lib/operation/unbuffered_operation.h" | |
| #include "src/storage/lib/operation/unbuffered_operations_builder.h" | |
| #include "src/storage/lib/vfs/cpp/transaction/buffered_operations_builder.h" | |
| #include "src/storage/minfs/allocator/allocator_reservation.h" | |
| #include "src/storage/minfs/allocator/metadata.h" | |
| #include "src/storage/minfs/allocator/storage.h" | |
| #include "src/storage/minfs/format.h" | |
| #include "src/storage/minfs/pending_work.h" | |
| namespace minfs { | |
| namespace { | |
| constexpr uint32_t kTotalElements = 64; | |
| class FakeStorage : public AllocatorStorage { | |
| public: | |
| FakeStorage() = delete; | |
| FakeStorage(const FakeStorage&) = delete; | |
| FakeStorage& operator=(const FakeStorage&) = delete; | |
| explicit FakeStorage(uint32_t units) : pool_used_(0), pool_total_(units) {} | |
| ~FakeStorage() {} | |
| #ifdef __Fuchsia__ | |
| zx::result<> AttachVmo(const zx::vmo& vmo, storage::OwnedVmoid* vmoid) final { return zx::ok(); } | |
| #endif | |
| void Load(fs::BufferedOperationsBuilder* builder, storage::BlockBuffer* data) final {} | |
| zx::result<> Extend(PendingWork* transaction, WriteData data, GrowMapCallback grow_map) final { | |
| return zx::error(ZX_ERR_NO_SPACE); | |
| } | |
| uint32_t PoolAvailable() const final { return pool_total_ - pool_used_; } | |
| uint32_t PoolTotal() const final { return pool_total_; } | |
| // Write back the allocation of the following items to disk. | |
| void PersistRange(PendingWork* transaction, WriteData data, size_t index, size_t count) final {} | |
| void PersistAllocate(PendingWork* transaction, size_t count) final { | |
| ZX_DEBUG_ASSERT(pool_used_ + count <= pool_total_); | |
| pool_used_ += static_cast<uint32_t>(count); | |
| } | |
| void PersistRelease(PendingWork* transaction, size_t count) final { | |
| ZX_DEBUG_ASSERT(pool_used_ >= count); | |
| pool_used_ -= static_cast<uint32_t>(count); | |
| } | |
| private: | |
| uint32_t pool_used_; | |
| uint32_t pool_total_; | |
| }; | |
| class FakeTransaction : public PendingWork { | |
| public: | |
| void EnqueueMetadata(storage::Operation operation, storage::BlockBuffer* buffer) final { | |
| storage::UnbufferedOperation unbuffered_operation = { | |
| .vmo = zx::unowned_vmo(buffer->Vmo()), | |
| .op = operation, | |
| }; | |
| metadata_operations_.Add(unbuffered_operation); | |
| } | |
| void EnqueueData(storage::Operation operation, storage::BlockBuffer* buffer) final {} | |
| size_t AllocateBlock() final { return 0; } | |
| void DeallocateBlock(size_t) final {} | |
| size_t BlockCount() { return metadata_operations_.BlockCount(); } | |
| private: | |
| storage::UnbufferedOperationsBuilder metadata_operations_; | |
| }; | |
| // Creates an allocator with |kTotalElements| elements. | |
| void CreateAllocator(std::unique_ptr<Allocator>* out) { | |
| // Create an Allocator with FakeStorage. | |
| // Give it 1 more than total_elements since element 0 will be unavailable. | |
| std::unique_ptr<FakeStorage> storage(new FakeStorage(kTotalElements + 1)); | |
| fs::BufferedOperationsBuilder builder; | |
| auto allocator_or = Allocator::Create(&builder, std::move(storage)); | |
| ASSERT_TRUE(allocator_or.is_ok()); | |
| // Allocate the '0' index (the Allocator assumes that this is reserved). | |
| AllocatorReservation zero_reservation(allocator_or.value().get()); | |
| ASSERT_TRUE(zero_reservation.Reserve(nullptr, 1).is_ok()); | |
| size_t index = zero_reservation.Allocate(); | |
| ZX_DEBUG_ASSERT(index == 0); | |
| ASSERT_EQ(allocator_or->GetAvailable(), kTotalElements); | |
| FakeTransaction transaction; | |
| zero_reservation.Commit(&transaction); | |
| *out = std::move(allocator_or.value()); | |
| } | |
| // Initializes the |reservation| with |reserved_count| elements from |allocator|. | |
| // Should only be called if initialization is expected to succeed. | |
| void InitializeReservation(size_t reserved_count, AllocatorReservation* reservation) { | |
| ASSERT_TRUE(reservation->Reserve(nullptr, reserved_count).is_ok()); | |
| ASSERT_EQ(reservation->GetReserved(), reserved_count); | |
| } | |
| TEST(AllocatorTest, ReserveEmpty) { | |
| std::unique_ptr<Allocator> allocator; | |
| ASSERT_NO_FATAL_FAILURE(CreateAllocator(&allocator)); | |
| // Initialize an empty AllocatorReservation (with no reserved units); | |
| ASSERT_EQ(allocator->GetAvailable(), kTotalElements); | |
| AllocatorReservation reservation(allocator.get()); | |
| ASSERT_NO_FATAL_FAILURE(InitializeReservation(0, &reservation)); | |
| ASSERT_EQ(allocator->GetAvailable(), kTotalElements); | |
| } | |
| TEST(AllocatorTest, OverReserve) { | |
| std::unique_ptr<Allocator> allocator; | |
| ASSERT_NO_FATAL_FAILURE(CreateAllocator(&allocator)); | |
| // Attempt to reserve more elements than the allocator has. | |
| AllocatorReservation reservation(allocator.get()); | |
| ASSERT_TRUE(reservation.Reserve(nullptr, kTotalElements + 1).is_error()); | |
| } | |
| TEST(AllocatorTest, ReserveTwiceFails) { | |
| std::unique_ptr<Allocator> allocator; | |
| ASSERT_NO_FATAL_FAILURE(CreateAllocator(&allocator)); | |
| AllocatorReservation reservation(allocator.get()); | |
| ASSERT_NO_FATAL_FAILURE(InitializeReservation(1, &reservation)); | |
| ASSERT_EQ(allocator->GetAvailable(), kTotalElements - 1); | |
| // Attempting to initialize a previously initialized AllocatorReservation should fail. | |
| ASSERT_TRUE(reservation.Reserve(nullptr, 1).is_error()); | |
| reservation.Cancel(); | |
| ASSERT_EQ(allocator->GetAvailable(), kTotalElements); | |
| } | |
| TEST(AllocatorTest, ExtendReservationByZeroDoesNotFail) { | |
| std::unique_ptr<Allocator> allocator; | |
| ASSERT_NO_FATAL_FAILURE(CreateAllocator(&allocator)); | |
| // Initialize an empty AllocatorReservation (with no reserved units); | |
| ASSERT_EQ(allocator->GetAvailable(), kTotalElements); | |
| AllocatorReservation reservation(allocator.get()); | |
| ASSERT_TRUE(reservation.Reserve(nullptr, 1).is_ok()); | |
| ASSERT_TRUE(reservation.ExtendReservation(nullptr, 0).is_ok()); | |
| ASSERT_EQ(allocator->GetAvailable(), kTotalElements - 1); | |
| } | |
| TEST(AllocatorTest, ExtendReservationByFewBlocks) { | |
| std::unique_ptr<Allocator> allocator; | |
| ASSERT_NO_FATAL_FAILURE(CreateAllocator(&allocator)); | |
| constexpr size_t kInitialReservation = 3; | |
| constexpr size_t kExtendedReservation = 8; | |
| // Initialize an empty AllocatorReservation (with no reserved units); | |
| ASSERT_EQ(allocator->GetAvailable(), kTotalElements); | |
| AllocatorReservation reservation(allocator.get()); | |
| ASSERT_TRUE(reservation.Reserve(nullptr, kInitialReservation).is_ok()); | |
| ASSERT_TRUE(reservation.ExtendReservation(nullptr, kExtendedReservation).is_ok()); | |
| ASSERT_EQ(allocator->GetAvailable(), | |
| kTotalElements - (kInitialReservation + kExtendedReservation)); | |
| } | |
| TEST(AllocatorTest, OverExtendFails) { | |
| std::unique_ptr<Allocator> allocator; | |
| ASSERT_NO_FATAL_FAILURE(CreateAllocator(&allocator)); | |
| constexpr size_t kInitialReservation = 3; | |
| constexpr size_t kExtendedReservation = kTotalElements + 1 - kInitialReservation; | |
| AllocatorReservation reservation(allocator.get()); | |
| ASSERT_TRUE(reservation.Reserve(nullptr, kInitialReservation).is_ok()); | |
| // Attempt to extend reservation more elements than the allocator has. | |
| ASSERT_TRUE(reservation.ExtendReservation(nullptr, kExtendedReservation).is_error()); | |
| ASSERT_EQ(allocator->GetAvailable(), kTotalElements - kInitialReservation); | |
| } | |
| TEST(AllocatorTest, GetReserved) { | |
| std::unique_ptr<Allocator> allocator; | |
| ASSERT_NO_FATAL_FAILURE(CreateAllocator(&allocator)); | |
| constexpr size_t kInitialReservation = 3; | |
| constexpr size_t kExtendedReservation = 2; | |
| constexpr size_t kExtendedReservationFail = | |
| kTotalElements + 1 - (kInitialReservation + kExtendedReservation); | |
| AllocatorReservation reservation(allocator.get()); | |
| // Nothing should be reserved. | |
| ASSERT_EQ(reservation.GetReserved(), 0ul); | |
| // kInitialReservation elements should be reserved. | |
| ASSERT_TRUE(reservation.Reserve(nullptr, kInitialReservation).is_ok()); | |
| ASSERT_EQ(reservation.GetReserved(), kInitialReservation); | |
| // kInitialReservation + kExtendedReservation elements should be reserved. | |
| ASSERT_TRUE(reservation.ExtendReservation(nullptr, kExtendedReservation).is_ok()); | |
| ASSERT_EQ(reservation.GetReserved(), kInitialReservation + kExtendedReservation); | |
| // Attempt to extend reservation more elements than the allocator has. The reserved elements | |
| // should be unchanged. | |
| ASSERT_TRUE(reservation.ExtendReservation(nullptr, kExtendedReservationFail).is_error()); | |
| ASSERT_EQ(reservation.GetReserved(), kInitialReservation + kExtendedReservation); | |
| // On cancelling reservation, number of reserved elements should be 0. | |
| reservation.Cancel(); | |
| ASSERT_EQ(reservation.GetReserved(), 0ul); | |
| } | |
| fbl::Array<size_t> CreateArray(size_t size) { | |
| fbl::Array<size_t> array(new size_t[size], size); | |
| memset(array.data(), 0, sizeof(size_t) * size); | |
| return array; | |
| } | |
| // Helper which allocates |allocate_count| units through |reservation|. | |
| // Allocated indices are returned in |out|. | |
| void PerformAllocate(size_t allocate_count, AllocatorReservation* reservation, | |
| fbl::Array<size_t>* out) { | |
| ASSERT_NE(nullptr, reservation); | |
| ASSERT_NE(nullptr, out); | |
| ASSERT_LE(allocate_count, reservation->GetReserved()); | |
| size_t remaining_count = reservation->GetReserved() - allocate_count; | |
| fbl::Array<size_t> indices = CreateArray(allocate_count); | |
| for (size_t i = 0; i < allocate_count; i++) { | |
| indices[i] = reservation->Allocate(); | |
| } | |
| ASSERT_EQ(reservation->GetReserved(), remaining_count); | |
| *out = std::move(indices); | |
| } | |
| // Helper which swaps |swap_count| units through |reservation|. |indices| must contain the units to | |
| // be swapped out (can be 0). These values will be replaced with the newly swapp indices. | |
| void PerformSwap(size_t swap_count, AllocatorReservation* reservation, | |
| fbl::Array<size_t>* indices) { | |
| ASSERT_NE(nullptr, reservation); | |
| ASSERT_NE(nullptr, indices); | |
| ASSERT_GE(indices->size(), swap_count); | |
| ASSERT_GE(reservation->GetReserved(), swap_count); | |
| size_t remaining_count = reservation->GetReserved() - swap_count; | |
| for (size_t i = 0; i < swap_count; i++) { | |
| size_t old_index = (*indices)[i]; | |
| (*indices)[i] = reservation->Swap(old_index); | |
| } | |
| ASSERT_EQ(reservation->GetReserved(), remaining_count); | |
| } | |
| // Frees all units in |indices| from |allocator|. | |
| void PerformFree(Allocator* allocator, const fbl::Array<size_t>& indices) { | |
| size_t free_count = allocator->GetAvailable(); | |
| { | |
| AllocatorReservation reservation(allocator); | |
| for (size_t index : indices) { | |
| allocator->Free(&reservation, index); | |
| } | |
| FakeTransaction transaction; | |
| reservation.Commit(&transaction); | |
| } | |
| ASSERT_EQ(allocator->GetAvailable(), indices.size() + free_count); | |
| } | |
| void ReserveAndExtend(AllocatorReservation& reservation, size_t elements) { | |
| size_t extend_by = elements / 2; | |
| size_t reserve = elements - extend_by; | |
| ASSERT_TRUE(reservation.Reserve(nullptr, reserve).is_ok()); | |
| ASSERT_TRUE(reservation.ExtendReservation(nullptr, extend_by).is_ok()); | |
| ASSERT_EQ(reservation.GetReserved(), elements); | |
| } | |
| TEST(AllocatorTest, Allocate) { | |
| std::unique_ptr<Allocator> allocator; | |
| ASSERT_NO_FATAL_FAILURE(CreateAllocator(&allocator)); | |
| fbl::Array<size_t> indices; | |
| { | |
| // Reserve all of the elements. | |
| AllocatorReservation reservation(allocator.get()); | |
| ReserveAndExtend(reservation, kTotalElements); | |
| // Allocate half of the reservation's reserved elements. | |
| ASSERT_NO_FATAL_FAILURE(PerformAllocate(kTotalElements / 2, &reservation, &indices)); | |
| // Cancel the remaining reservation. | |
| size_t reserved_count = reservation.GetReserved(); | |
| reservation.Cancel(); | |
| ASSERT_EQ(allocator->GetAvailable(), reserved_count); | |
| FakeTransaction transaction; | |
| reservation.Commit(&transaction); | |
| } | |
| // Free the allocated elements. | |
| ASSERT_NO_FATAL_FAILURE(PerformFree(allocator.get(), indices)); | |
| } | |
| TEST(AllocatorTest, Swap) { | |
| std::unique_ptr<Allocator> allocator; | |
| ASSERT_NO_FATAL_FAILURE(CreateAllocator(&allocator)); | |
| size_t swap_count = kTotalElements / 2; | |
| fbl::Array<size_t> indices = CreateArray(swap_count); | |
| { | |
| // Reserve all of the elements. | |
| AllocatorReservation reservation(allocator.get()); | |
| ASSERT_TRUE(reservation.Reserve(nullptr, kTotalElements).is_ok()); | |
| // Swap half of the reservation's reserved elements. | |
| ASSERT_GT(swap_count, 0u); | |
| ASSERT_NO_FATAL_FAILURE(PerformSwap(swap_count, &reservation, &indices)); | |
| ASSERT_EQ(allocator->GetAvailable(), 0ul); | |
| // Cancel the remaining reservation. | |
| size_t reserved_count = reservation.GetReserved(); | |
| reservation.Cancel(); | |
| ASSERT_EQ(allocator->GetAvailable(), reserved_count); | |
| FakeTransaction transaction; | |
| reservation.Commit(&transaction); | |
| } | |
| // Free the allocated elements. | |
| ASSERT_NO_FATAL_FAILURE(PerformFree(allocator.get(), indices)); | |
| } | |
| TEST(AllocatorTest, AllocateSwap) { | |
| std::unique_ptr<Allocator> allocator; | |
| ASSERT_NO_FATAL_FAILURE(CreateAllocator(&allocator)); | |
| fbl::Array<size_t> indices; | |
| { | |
| // Reserve all of the elements. | |
| AllocatorReservation reservation(allocator.get()); | |
| ASSERT_TRUE(reservation.Reserve(nullptr, kTotalElements).is_ok()); | |
| // Allocate half of the reservation's reserved elements. | |
| size_t allocate_count = kTotalElements / 2; | |
| ASSERT_GT(allocate_count, 0ul); | |
| ASSERT_NO_FATAL_FAILURE(PerformAllocate(allocate_count, &reservation, &indices)); | |
| // Swap as many of the allocated elements as possible. | |
| size_t swap_count = std::min(reservation.GetReserved(), allocate_count); | |
| ASSERT_GT(swap_count, 0ul); | |
| ASSERT_NO_FATAL_FAILURE(PerformSwap(swap_count, &reservation, &indices)); | |
| // Cancel the remaining reservation. | |
| size_t reserved_count = reservation.GetReserved(); | |
| reservation.Cancel(); | |
| ASSERT_EQ(allocator->GetAvailable(), swap_count + reserved_count); | |
| FakeTransaction transaction; | |
| reservation.Commit(&transaction); | |
| } | |
| // Free the allocated elements. | |
| ASSERT_NO_FATAL_FAILURE(PerformFree(allocator.get(), indices)); | |
| } | |
| TEST(AllocatorTest, PersistRange) { | |
| // Create PersistentStorage with bogus attributes - valid storage is unnecessary for this test. | |
| AllocatorFvmMetadata fvm_metadata; | |
| AllocatorMetadata metadata(0, 0, false, std::move(fvm_metadata), nullptr, {}); | |
| PersistentStorage storage(nullptr, nullptr, kMinfsBlockSize, nullptr, std::move(metadata), | |
| kMinfsBlockSize); | |
| FakeTransaction transaction; | |
| ASSERT_EQ(transaction.BlockCount(), 0ul); | |
| // Add a transaction which crosses the boundary between two blocks within the storage bitmap. | |
| storage.PersistRange(&transaction, 1, kMinfsBlockBits - 1, 2); | |
| // Check that two distinct blocks have been added to the txn. | |
| ASSERT_EQ(transaction.BlockCount(), 2ul); | |
| } | |
| TEST(AllocatorTest, PendingAllocationIsReserved) { | |
| std::unique_ptr<Allocator> allocator; | |
| ASSERT_NO_FATAL_FAILURE(CreateAllocator(&allocator)); | |
| AllocatorReservation reservation1(allocator.get()); | |
| FakeTransaction transaction; | |
| ASSERT_TRUE(reservation1.Reserve(&transaction, 1).is_ok()); | |
| size_t item = reservation1.Allocate(); | |
| AllocatorReservation reservation2(allocator.get()); | |
| ASSERT_TRUE(reservation2.Reserve(&transaction, 1).is_ok()); | |
| size_t item2 = reservation2.Allocate(); | |
| EXPECT_NE(item, item2); | |
| AllocatorReservation reservation3(allocator.get()); | |
| ASSERT_TRUE(reservation3.Reserve(&transaction, 1).is_ok()); | |
| size_t item3 = reservation3.Allocate(); | |
| EXPECT_NE(item, item3); | |
| EXPECT_NE(item2, item3); | |
| } | |
| TEST(AllocatorTest, PendingDeallocationIsReserved) { | |
| std::unique_ptr<Allocator> allocator; | |
| ASSERT_NO_FATAL_FAILURE(CreateAllocator(&allocator)); | |
| size_t item; | |
| { | |
| AllocatorReservation reservation(allocator.get()); | |
| FakeTransaction transaction; | |
| ASSERT_TRUE(reservation.Reserve(&transaction, 1).is_ok()); | |
| item = reservation.Allocate(); | |
| reservation.Commit(&transaction); | |
| } | |
| { | |
| // Free that item. | |
| AllocatorReservation reservation(allocator.get()); | |
| allocator->Free(&reservation, item); | |
| FakeTransaction transaction; | |
| reservation.Commit(&transaction); | |
| // Even though we have freed the item, we won't reuse it until reservation goes out of scope. | |
| AllocatorReservation reservation2(allocator.get()); | |
| EXPECT_TRUE(reservation2.Reserve(&transaction, 1).is_ok()); | |
| EXPECT_NE(item, reservation2.Allocate()); | |
| } | |
| // Now we should be able to allocate that item. | |
| AllocatorReservation reservation(allocator.get()); | |
| FakeTransaction transaction; | |
| EXPECT_TRUE(reservation.Reserve(&transaction, 1).is_ok()); | |
| EXPECT_EQ(item, reservation.Allocate()); | |
| } | |
| } // namespace | |
| } // namespace minfs |