Index: include/llvm/DebugInfo/PDB/Raw/MsfBuilder.h =================================================================== --- /dev/null +++ include/llvm/DebugInfo/PDB/Raw/MsfBuilder.h @@ -0,0 +1,72 @@ +//===- MSFBuilder.h - MSF Directory & Metadata Builder ----------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_DEBUGINFO_PDB_RAW_MSFBUILDER_H +#define LLVM_DEBUGINFO_PDB_RAW_MSFBUILDER_H + +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/BitVector.h" + +#include "llvm/DebugInfo/PDB/Raw/MsfCommon.h" +#include "llvm/DebugInfo/PDB/Raw/PDBFile.h" + +#include "llvm/Support/Allocator.h" +#include "llvm/Support/Endian.h" +#include "llvm/Support/Error.h" + +#include +#include + +namespace llvm { +namespace pdb { +class MsfBuilder { +public: + explicit MsfBuilder(BumpPtrAllocator &Allocator); + void initialize(uint32_t PageSize, uint32_t MinPageCount = 0, + bool CanGrow = true); + void reset(); + + Error setBlockMapAddr(uint32_t Addr); + + Error addStream(uint32_t Size, ArrayRef Blocks); + Error addStream(uint32_t Size); + Error setStreamSize(uint32_t Idx, uint32_t Size); + + uint32_t getNumStreams() const; + uint32_t getStreamSize(uint32_t StreamIdx) const; + ArrayRef getStreamBlocks(uint32_t StreamIdx) const; + + uint32_t getNumUsedPages() const; + uint32_t getNumFreePages() const; + uint32_t getTotalPageCount() const; + bool isPageFree(uint32_t Idx) const; + + Expected build(); + +private: + Error allocatePages(uint32_t NumPages, MutableArrayRef Pages); + uint32_t computeDirectoryByteSize() const; + + typedef std::vector BlockList; + + BumpPtrAllocator &Allocator; + + bool IsInitialized = false; + bool IsGrowable = false; + uint32_t BlockSize = 0; + uint32_t MininumBlocks = 0; + uint32_t BlockMapAddr; + std::vector DirectoryBlocks; + BitVector FreePages; + std::vector> StreamData; +}; +} +} + +#endif Index: include/llvm/DebugInfo/PDB/Raw/MsfCommon.h =================================================================== --- /dev/null +++ include/llvm/DebugInfo/PDB/Raw/MsfCommon.h @@ -0,0 +1,72 @@ +//===- MsfCommon.h - Common types and functions for MSF files ---*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_DEBUGINFO_PDB_RAW_MSFCOMMON_H +#define LLVM_DEBUGINFO_PDB_RAW_MSFCOMMON_H + +#include "llvm/ADT/ArrayRef.h" + +#include "llvm/Support/Endian.h" +#include "llvm/Support/Error.h" +#include "llvm/Support/MathExtras.h" + +#include + +namespace llvm { +namespace pdb { +namespace msf { +static const char Magic[] = {'M', 'i', 'c', 'r', 'o', 's', 'o', 'f', + 't', ' ', 'C', '/', 'C', '+', '+', ' ', + 'M', 'S', 'F', ' ', '7', '.', '0', '0', + '\r', '\n', '\x1a', 'D', 'S', '\0', '\0', '\0'}; + +// The superblock is overlaid at the beginning of the file (offset 0). +// It starts with a magic header and is followed by information which +// describes the layout of the file system. +struct SuperBlock { + char MagicBytes[sizeof(Magic)]; + // The file system is split into a variable number of fixed size elements. + // These elements are referred to as blocks. The size of a block may vary + // from system to system. + support::ulittle32_t BlockSize; + // This field's purpose is not yet known. + support::ulittle32_t Unknown0; + // This contains the number of blocks resident in the file system. In + // practice, NumBlocks * BlockSize is equivalent to the size of the PDB + // file. + support::ulittle32_t NumBlocks; + // This contains the number of bytes which make up the directory. + support::ulittle32_t NumDirectoryBytes; + // This field's purpose is not yet known. + support::ulittle32_t Unknown1; + // This contains the block # of the block map. + support::ulittle32_t BlockMapAddr; +}; + +struct Layout { + SuperBlock *SB; + ArrayRef DirectoryBlocks; + ArrayRef StreamSizes; + std::vector> StreamMap; +}; + +inline uint64_t bytesToBlocks(uint64_t NumBytes, uint64_t BlockSize) { + return alignTo(NumBytes, BlockSize) / BlockSize; +} + +inline uint64_t blockToOffset(uint64_t BlockNumber, uint64_t BlockSize) { + return BlockNumber * BlockSize; +} + +Error validateSuperBlock(const SuperBlock &SB); +} +} +} + +#endif Index: lib/DebugInfo/PDB/CMakeLists.txt =================================================================== --- lib/DebugInfo/PDB/CMakeLists.txt +++ lib/DebugInfo/PDB/CMakeLists.txt @@ -38,6 +38,8 @@ Raw/MappedBlockStream.cpp Raw/ModInfo.cpp Raw/ModStream.cpp + Raw/MsfBuilder.cpp + Raw/MsfCommon.cpp Raw/NameHashTable.cpp Raw/NameMap.cpp Raw/PDBFile.cpp Index: lib/DebugInfo/PDB/Raw/MsfBuilder.cpp =================================================================== --- /dev/null +++ lib/DebugInfo/PDB/Raw/MsfBuilder.cpp @@ -0,0 +1,266 @@ +//===- MSFBuilder.cpp - MSF Directory & Metadata Builder --------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "llvm/DebugInfo/PDB/Raw/MsfBuilder.h" +#include "llvm/DebugInfo/PDB/Raw/RawError.h" + +using namespace llvm; +using namespace llvm::pdb; +using namespace llvm::pdb::msf; +using namespace llvm::support; + +namespace { +const uint32_t kSuperBlockPage = 0; +const uint32_t kDefaultBlockMapAddr = 1; +} + +MsfBuilder::MsfBuilder(BumpPtrAllocator &Allocator) + : Allocator(Allocator), BlockMapAddr(kDefaultBlockMapAddr) {} + +void MsfBuilder::initialize(uint32_t PageSize, uint32_t MinPageCount, + bool CanGrow) { + assert(!IsInitialized && "MsfBuilder is already initialized!"); + + // The super block and block map address are not counted + BlockSize = PageSize; + IsInitialized = true; + IsGrowable = CanGrow; + MininumBlocks = MinPageCount + 2U; + + FreePages = BitVector(MininumBlocks, true); + FreePages[kSuperBlockPage] = false; + FreePages[BlockMapAddr] = false; +} + +Error MsfBuilder::setBlockMapAddr(uint32_t Addr) { + if (Addr == BlockMapAddr) + return Error::success(); + + if (Addr >= FreePages.size()) { + if (!IsGrowable) + return make_error(raw_error_code::unspecified, + "Cannot grow the number of blocks"); + FreePages.resize(Addr + 1); + } + + if (!isPageFree(Addr)) + return make_error(raw_error_code::unspecified, + "Attempt to reuse an allocated block"); + FreePages[BlockMapAddr] = true; + FreePages[Addr] = false; + BlockMapAddr = Addr; + return Error::success(); +} + +void MsfBuilder::reset() { + FreePages = BitVector(); + BlockSize = 0; + MininumBlocks = 0; + IsGrowable = false; + IsInitialized = false; + BlockMapAddr = kDefaultBlockMapAddr; + StreamData.clear(); +} + +Error MsfBuilder::allocatePages(uint32_t NumPages, + MutableArrayRef Pages) { + assert(IsInitialized && "Must call MsfBuilder::initialize!"); + + if (NumPages == 0) + return Error::success(); + + uint32_t NumFreePages = FreePages.count(); + if (NumFreePages < NumPages) { + if (!IsGrowable) + return make_error(raw_error_code::unspecified, + "There are no free pages in the file"); + uint32_t AllocPages = NumPages - NumFreePages; + FreePages.resize(AllocPages + FreePages.size(), true); + } + + int I = 0; + int Page = FreePages.find_first(); + do { + assert(Page != -1 && "We ran out of pages!"); + + uint32_t NextPage = static_cast(Page); + Pages[I++] = NextPage; + FreePages.reset(NextPage); + Page = FreePages.find_next(Page); + } while (--NumPages > 0); + return Error::success(); +} + +uint32_t MsfBuilder::getNumUsedPages() const { + return getTotalPageCount() - getNumFreePages(); +} + +uint32_t MsfBuilder::getNumFreePages() const { return FreePages.count(); } + +uint32_t MsfBuilder::getTotalPageCount() const { return FreePages.size(); } + +bool MsfBuilder::isPageFree(uint32_t Idx) const { return FreePages[Idx]; } + +Error MsfBuilder::addStream(uint32_t Size, ArrayRef Blocks) { + assert(IsInitialized && "Must call MsfBuilder::initialize!"); + + // Add a new stream mapped to the specified blocks. Verify that the specified + // blocks are both necessary and sufficient for holding the requested number + // of bytes, and verify that all requested blocks are free. + uint32_t ReqBlocks = bytesToBlocks(Size, BlockSize); + if (ReqBlocks != Blocks.size()) + return make_error( + raw_error_code::unspecified, + "Incorrect number of blocks for requested stream size"); + for (auto Block : Blocks) { + if (Block >= FreePages.size()) + FreePages.resize(Block + 1, true); + + if (!FreePages.test(Block)) + return make_error( + raw_error_code::unspecified, + "Attempt to re-use an already allocated block"); + } + // Mark all the blocks occupied by the new stream as not free. + for (auto Block : Blocks) { + FreePages.reset(Block); + } + StreamData.push_back(std::make_pair(Size, Blocks)); + return Error::success(); +} + +Error MsfBuilder::addStream(uint32_t Size) { + assert(IsInitialized && "Must call MsfBuilder::initialize!"); + + // Add a new stream of the specified size, but determine the blocks to map the + // stream to + // automatically. + uint32_t ReqBlocks = bytesToBlocks(Size, BlockSize); + std::vector NewPages; + NewPages.resize(ReqBlocks); + if (auto EC = allocatePages(ReqBlocks, NewPages)) + return EC; + StreamData.push_back(std::make_pair(Size, NewPages)); + return Error::success(); +} + +Error MsfBuilder::setStreamSize(uint32_t Idx, uint32_t Size) { + assert(IsInitialized && "Must call MsfBuilder::initialize!"); + + // If the size is the same, just return. Otherwise we may need to shrink or + // grow the stream + // which could necessitate shrinking or growing the directory as well. + uint32_t OldSize = getStreamSize(Idx); + if (OldSize == Size) + return Error::success(); + + uint32_t NewPages = bytesToBlocks(Size, BlockSize); + uint32_t OldPages = bytesToBlocks(OldSize, BlockSize); + + if (NewPages > OldPages) { + uint32_t AddedPages = NewPages - OldPages; + // If we're growing, we have to allocate new pages. + std::vector AddedPageList; + AddedPageList.resize(AddedPages); + if (auto EC = allocatePages(AddedPages, AddedPageList)) + return EC; + auto &CurrentPages = StreamData[Idx].second; + CurrentPages.insert(CurrentPages.end(), AddedPageList.begin(), + AddedPageList.end()); + } else if (OldPages > NewPages) { + // For shrinking, free all the pages in the page map, update the stream + // data, then shrink the directory. + uint32_t RemovedPages = OldPages - NewPages; + auto CurrentPages = ArrayRef(StreamData[Idx].second); + auto RemovedPageList = CurrentPages.drop_front(NewPages); + for (auto P : RemovedPageList) + FreePages[P] = true; + StreamData[Idx].second = CurrentPages.drop_back(RemovedPages); + } + + StreamData[Idx].first = Size; + return Error::success(); +} + +uint32_t MsfBuilder::getNumStreams() const { return StreamData.size(); } + +uint32_t MsfBuilder::getStreamSize(uint32_t StreamIdx) const { + return StreamData[StreamIdx].first; +} + +ArrayRef MsfBuilder::getStreamBlocks(uint32_t StreamIdx) const { + return StreamData[StreamIdx].second; +} + +uint32_t MsfBuilder::computeDirectoryByteSize() const { + // The directory has the following layout, where each item is a ulittle32_t. + // NumStreams + // StreamSizes[NumStreams] + // StreamBlocks[NumStreams][] + uint32_t Size = sizeof(ulittle32_t); // NumStreams + Size += StreamData.size() * sizeof(ulittle32_t); // StreamSizes + for (const auto &D : StreamData) { + uint32_t ExpectedNumBlocks = bytesToBlocks(D.first, BlockSize); + assert(ExpectedNumBlocks == D.second.size() && + "Unexpected number of blocks"); + Size += ExpectedNumBlocks * sizeof(ulittle32_t); + } + return Size; +} + +Expected MsfBuilder::build() { + assert(IsInitialized && "Must call MsfBuilder::initialize!"); + + Layout L; + // The super block should was already allocated, just set it. + L.SB = Allocator.Allocate(); + ::memcpy(L.SB->MagicBytes, Magic, sizeof(Magic)); + L.SB->BlockMapAddr = BlockMapAddr; + L.SB->BlockSize = BlockSize; + L.SB->NumDirectoryBytes = computeDirectoryByteSize(); + L.SB->Unknown0 = 0; + L.SB->Unknown1 = 0; + + uint32_t NumDirectoryBlocks = + bytesToBlocks(L.SB->NumDirectoryBytes, BlockSize); + // The directory blocks should be re-allocated as a stable pointer. + std::vector DirectoryBlocks; + DirectoryBlocks.resize(NumDirectoryBlocks); + if (auto EC = allocatePages(NumDirectoryBlocks, DirectoryBlocks)) + return std::move(EC); + + // Don't set the number of blocks in the file until after allocating pages for + // the directory, since the allocation might cause the file to need to grow. + L.SB->NumBlocks = FreePages.size(); + + ulittle32_t *DirBlocks = Allocator.Allocate(NumDirectoryBlocks); + std::uninitialized_copy_n(DirectoryBlocks.begin(), NumDirectoryBlocks, + DirBlocks); + L.DirectoryBlocks = ArrayRef(DirBlocks, NumDirectoryBlocks); + + // The stream sizes should be re-allocated as a stable pointer and the stream + // map should have each of its entries allocated as a separate stable pointer. + if (StreamData.size() > 0) { + ulittle32_t *Sizes = Allocator.Allocate(StreamData.size()); + L.StreamSizes = ArrayRef(Sizes, StreamData.size()); + L.StreamMap.resize(StreamData.size()); + for (uint32_t I = 0; I < StreamData.size(); ++I) { + Sizes[I] = StreamData[I].first; + ulittle32_t *BlockList = + Allocator.Allocate(StreamData[I].second.size()); + std::uninitialized_copy_n(StreamData[I].second.begin(), + StreamData[I].second.size(), BlockList); + L.StreamMap[I] = + ArrayRef(BlockList, StreamData[I].second.size()); + } + } + + reset(); + return L; +} Index: lib/DebugInfo/PDB/Raw/MsfCommon.cpp =================================================================== --- /dev/null +++ lib/DebugInfo/PDB/Raw/MsfCommon.cpp @@ -0,0 +1,61 @@ +//===- MsfCommon.cpp - Common types and functions for MSF files -*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "llvm/DebugInfo/PDB/Raw/MsfCommon.h" +#include "llvm/DebugInfo/PDB/Raw/RawError.h" + +using namespace llvm; +using namespace llvm::pdb::msf; + +Error llvm::pdb::msf::validateSuperBlock(const SuperBlock &SB) { + // Check the magic bytes. + if (memcmp(SB.MagicBytes, Magic, sizeof(Magic)) != 0) + return make_error(raw_error_code::corrupt_file, + "MSF magic header doesn't match"); + + // We don't support blocksizes which aren't a multiple of four bytes. + if (SB.BlockSize % sizeof(support::ulittle32_t) != 0) + return make_error(raw_error_code::corrupt_file, + "Block size is not multiple of 4."); + + switch (SB.BlockSize) { + case 512: + case 1024: + case 2048: + case 4096: + break; + default: + // An invalid block size suggests a corrupt PDB file. + return make_error(raw_error_code::corrupt_file, + "Unsupported block size."); + } + + // We don't support directories whose sizes aren't a multiple of four bytes. + if (SB.NumDirectoryBytes % sizeof(support::ulittle32_t) != 0) + return make_error(raw_error_code::corrupt_file, + "Directory size is not multiple of 4."); + + // The number of blocks which comprise the directory is a simple function of + // the number of bytes it contains. + uint64_t NumDirectoryBlocks = + bytesToBlocks(SB.NumDirectoryBytes, SB.BlockSize); + + // The directory, as we understand it, is a block which consists of a list of + // block numbers. It is unclear what would happen if the number of blocks + // couldn't fit on a single block. + if (NumDirectoryBlocks > SB.BlockSize / sizeof(support::ulittle32_t)) + return make_error(raw_error_code::corrupt_file, + "Too many directory blocks."); + + if (SB.BlockMapAddr == 0) + return make_error(raw_error_code::corrupt_file, + "Block 0 is reserved"); + + return Error::success(); +} Index: unittests/DebugInfo/PDB/CMakeLists.txt =================================================================== --- unittests/DebugInfo/PDB/CMakeLists.txt +++ unittests/DebugInfo/PDB/CMakeLists.txt @@ -5,6 +5,7 @@ set(DebugInfoPDBSources MappedBlockStreamTest.cpp + MsfBuilderTest.cpp PDBApiTest.cpp ) Index: unittests/DebugInfo/PDB/ErrorChecking.h =================================================================== --- /dev/null +++ unittests/DebugInfo/PDB/ErrorChecking.h @@ -0,0 +1,41 @@ +//===- ErrorChecking.h - Helpers for verifying llvm::Errors -----*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_UNITTESTS_DEBUGINFO_PDB_ERRORCHECKING_H +#define LLVM_UNITTESTS_DEBUGINFO_PDB_ERRORCHECKING_H + +#define EXPECT_NO_ERROR(Err) \ + { \ + auto E = Err; \ + EXPECT_FALSE(static_cast(E)); \ + if (E) \ + consumeError(std::move(E)); \ + } + +#define EXPECT_ERROR(Err) \ + { \ + auto E = Err; \ + EXPECT_TRUE(static_cast(E)); \ + if (E) \ + consumeError(std::move(E)); \ + } + +#define EXPECT_EXPECTED(Exp) \ + { \ + auto E = Exp.takeError(); \ + EXPECT_FALSE(static_cast(E)); \ + if (E) { \ + consumeError(std::move(E)); \ + return; \ + } \ + } + +#define EXPECT_UNEXPECTED(Exp) EXPECT_ERROR(Err) + +#endif Index: unittests/DebugInfo/PDB/MappedBlockStreamTest.cpp =================================================================== --- unittests/DebugInfo/PDB/MappedBlockStreamTest.cpp +++ unittests/DebugInfo/PDB/MappedBlockStreamTest.cpp @@ -7,7 +7,7 @@ // //===----------------------------------------------------------------------===// -#include +#include "ErrorChecking.h" #include "llvm/DebugInfo/CodeView/ByteStream.h" #include "llvm/DebugInfo/CodeView/StreamReader.h" @@ -19,28 +19,14 @@ #include "llvm/DebugInfo/PDB/Raw/MappedBlockStream.h" #include "gtest/gtest.h" +#include + using namespace llvm; using namespace llvm::codeview; using namespace llvm::pdb; namespace { -#define EXPECT_NO_ERROR(Err) \ - { \ - auto E = Err; \ - EXPECT_FALSE(static_cast(E)); \ - if (E) \ - consumeError(std::move(E)); \ - } - -#define EXPECT_ERROR(Err) \ - { \ - auto E = Err; \ - EXPECT_TRUE(static_cast(E)); \ - if (E) \ - consumeError(std::move(E)); \ - } - static const uint32_t BlocksAry[] = {0, 1, 2, 5, 4, 3, 6, 7, 8, 9}; static uint8_t DataAry[] = {'A', 'B', 'C', 'F', 'E', 'D', 'G', 'H', 'I', 'J'}; Index: unittests/DebugInfo/PDB/MsfBuilderTest.cpp =================================================================== --- /dev/null +++ unittests/DebugInfo/PDB/MsfBuilderTest.cpp @@ -0,0 +1,288 @@ +//===- MsfBuilderTest.cpp Tests manipulation of MSF stream metadata ------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "ErrorChecking.h" + +#include "llvm/DebugInfo/PDB/Raw/MsfBuilder.h" +#include "llvm/DebugInfo/PDB/Raw/MsfCommon.h" + +#include "gtest/gtest.h" + +using namespace llvm; +using namespace llvm::pdb; +using namespace llvm::pdb::msf; + +namespace { +class MsfBuilderTest : public testing::Test { +protected: + void initializeSimpleSuperBlock(msf::SuperBlock &SB) { + initializeSuperBlock(SB); + SB.NumBlocks = 1000; + SB.NumDirectoryBytes = 8192; + } + + void initializeSuperBlock(msf::SuperBlock &SB) { + ::memset(&SB, 0, sizeof(SB)); + + ::memcpy(SB.MagicBytes, msf::Magic, sizeof(msf::Magic)); + SB.BlockMapAddr = 1; + SB.BlockSize = 4096; + SB.NumDirectoryBytes = 0; + SB.NumBlocks = 2; // one for the Super Block, one for the directory + } + + BumpPtrAllocator Allocator; +}; +} + +TEST_F(MsfBuilderTest, ValidateSuperBlockAccept) { + // Test that a known good super block passes validation. + SuperBlock SB; + initializeSuperBlock(SB); + + EXPECT_NO_ERROR(msf::validateSuperBlock(SB)); +} + +TEST_F(MsfBuilderTest, ValidateSuperBlockReject) { + // Test that various known problems cause a super block to be rejected. + SuperBlock SB; + initializeSimpleSuperBlock(SB); + + // Mismatched magic + SB.MagicBytes[0] = 8; + EXPECT_ERROR(msf::validateSuperBlock(SB)); + initializeSimpleSuperBlock(SB); + + // Block 0 is reserved for super block, can't be occupied by the block map + SB.BlockMapAddr = 0; + EXPECT_ERROR(msf::validateSuperBlock(SB)); + initializeSimpleSuperBlock(SB); + + // Block sizes have to be a multiple of 4. + SB.BlockSize = 3120; + EXPECT_ERROR(msf::validateSuperBlock(SB)); + initializeSimpleSuperBlock(SB); + + // The directory itself has a maximum size. + SB.NumDirectoryBytes = SB.BlockSize * SB.BlockSize / 4; + EXPECT_NO_ERROR(msf::validateSuperBlock(SB)); + SB.NumDirectoryBytes = SB.NumDirectoryBytes + 4; + EXPECT_ERROR(msf::validateSuperBlock(SB)); +} + +TEST_F(MsfBuilderTest, TestUsedBlocksMarkedAsUsed) { + // Test that when initializing an MsfBuilder with a list of directory blocks + // that the directory blocks are marked as used, but the other blocks are + // still marked as free. + MsfBuilder Msf(Allocator); + + std::vector Blocks = {2, 3, 4, 5, 6, 7, 8, 9, 10}; + // Allocate some extra blocks at the end so we can verify that they're free + // after the initialization. + Msf.initialize(4096, Blocks.size() + 10); + + EXPECT_NO_ERROR(Msf.addStream(Blocks.size() * 4096, Blocks)); + + for (auto B : Blocks) { + EXPECT_FALSE(Msf.isPageFree(B)); + } + for (int I = 11; I < 21; ++I) { + EXPECT_TRUE(Msf.isPageFree(I)); + } +} + +TEST_F(MsfBuilderTest, TestAddStreamNoDirectoryBlockIncrease) { + // Test that adding a new stream correctly updates the directory. This only + // tests the case where the directory *DOES NOT* grow large enough that it + // crosses a page boundary. + MsfBuilder Msf(Allocator); + + Msf.initialize(4096); + auto ExpectedL1 = Msf.build(); + EXPECT_EXPECTED(ExpectedL1); + Layout &L1 = *ExpectedL1; + + auto OldDirBlocks = L1.DirectoryBlocks; + EXPECT_EQ(1, OldDirBlocks.size()); + + MsfBuilder Msf2(Allocator); + Msf2.initialize(4096); + EXPECT_NO_ERROR(Msf2.addStream(4000)); + EXPECT_EQ(1, Msf2.getNumStreams()); + EXPECT_EQ(4000, Msf2.getStreamSize(0)); + auto Blocks = Msf2.getStreamBlocks(0); + EXPECT_EQ(1, Blocks.size()); + + auto ExpectedL2 = Msf2.build(); + EXPECT_EXPECTED(ExpectedL2); + Layout &L2 = *ExpectedL2; + auto NewDirBlocks = L2.DirectoryBlocks; + EXPECT_EQ(1, NewDirBlocks.size()); +} + +TEST_F(MsfBuilderTest, TestAddStreamWithDirectoryBlockIncrease) { + // Test that adding a new stream correctly updates the directory. This only + // tests the case where the directory *DOES* grow large enough that it + // crosses a page boundary. This is because the newly added stream occupies + // so many pages that need to be indexed in the directory. + // crosses a page boundary. + MsfBuilder Msf(Allocator); + + Msf.initialize(4096); + EXPECT_NO_ERROR(Msf.addStream(4096 * 4096 / sizeof(uint32_t))); + + auto ExpectedL1 = Msf.build(); + EXPECT_EXPECTED(ExpectedL1); + Layout &L1 = *ExpectedL1; + auto DirBlocks = L1.DirectoryBlocks; + EXPECT_EQ(2, DirBlocks.size()); +} + +TEST_F(MsfBuilderTest, TestGrowStreamNoBlockIncrease) { + // Test growing an existing stream by a value that does not affect the number + // of + // of pages it occupies. + MsfBuilder Msf(Allocator); + + Msf.initialize(4096); + EXPECT_NO_ERROR(Msf.addStream(1024)); + EXPECT_EQ(Msf.getStreamSize(0), 1024); + auto OldStreamBlocks = Msf.getStreamBlocks(0); + EXPECT_EQ(1, OldStreamBlocks.size()); + + EXPECT_NO_ERROR(Msf.setStreamSize(0, 2048)); + EXPECT_EQ(Msf.getStreamSize(0), 2048); + auto NewStreamBlocks = Msf.getStreamBlocks(0); + EXPECT_EQ(1, NewStreamBlocks.size()); + + EXPECT_EQ(OldStreamBlocks, NewStreamBlocks); +} + +TEST_F(MsfBuilderTest, TestGrowStreamWithDirectoryBlockIncrease) { + // Test that growing an existing stream to a value large enough that it causes + // the + // need to allocate new pages to the stream correctly updates the directory. + MsfBuilder Msf(Allocator); + + Msf.initialize(4096); + EXPECT_NO_ERROR(Msf.addStream(2048)); + EXPECT_EQ(Msf.getStreamSize(0), 2048); + std::vector OldStreamBlocks = Msf.getStreamBlocks(0); + EXPECT_EQ(1, OldStreamBlocks.size()); + + EXPECT_NO_ERROR(Msf.setStreamSize(0, 6144)); + EXPECT_EQ(Msf.getStreamSize(0), 6144); + std::vector NewStreamBlocks = Msf.getStreamBlocks(0); + EXPECT_EQ(2, NewStreamBlocks.size()); + + EXPECT_EQ(OldStreamBlocks[0], NewStreamBlocks[0]); + EXPECT_NE(NewStreamBlocks[0], NewStreamBlocks[1]); +} + +TEST_F(MsfBuilderTest, TestShrinkStreamNoBlockDecrease) { + // Test that shrinking an existing stream by a value that does not affect the + // number + // of pages it occupies makes no changes to the directory or super block. + MsfBuilder Msf(Allocator); + + Msf.initialize(4096); + EXPECT_NO_ERROR(Msf.addStream(2048)); + EXPECT_EQ(Msf.getStreamSize(0), 2048); + std::vector OldStreamBlocks = Msf.getStreamBlocks(0); + EXPECT_EQ(1, OldStreamBlocks.size()); + + EXPECT_NO_ERROR(Msf.setStreamSize(0, 1024)); + EXPECT_EQ(Msf.getStreamSize(0), 1024); + std::vector NewStreamBlocks = Msf.getStreamBlocks(0); + EXPECT_EQ(1, NewStreamBlocks.size()); + + EXPECT_EQ(OldStreamBlocks, NewStreamBlocks); +} + +TEST_F(MsfBuilderTest, TestShrinkStreamWithDirectoryBlockDecrease) { + // Test that shrinking an existing stream to a value large enough that it + // causes the + // need to deallocate new pages to the stream correctly updates the directory. + MsfBuilder Msf(Allocator); + + Msf.initialize(4096); + + EXPECT_NO_ERROR(Msf.addStream(6144)); + EXPECT_EQ(Msf.getStreamSize(0), 6144); + std::vector OldStreamBlocks = Msf.getStreamBlocks(0); + EXPECT_EQ(2, OldStreamBlocks.size()); + + EXPECT_NO_ERROR(Msf.setStreamSize(0, 2048)); + EXPECT_EQ(Msf.getStreamSize(0), 2048); + std::vector NewStreamBlocks = Msf.getStreamBlocks(0); + EXPECT_EQ(1, NewStreamBlocks.size()); + + EXPECT_EQ(OldStreamBlocks[0], NewStreamBlocks[0]); +} + +TEST_F(MsfBuilderTest, TestRejectReusedStreamBlock) { + // Test that attempting to add a stream and assigning a block that is already + // in use + // by another stream fails. + MsfBuilder Msf(Allocator); + + Msf.initialize(4096); + EXPECT_NO_ERROR(Msf.addStream(6144)); + + std::vector Blocks = {2, 3}; + EXPECT_ERROR(Msf.addStream(6144, Blocks)); +} + +TEST_F(MsfBuilderTest, TestPageCountsWhenAddingStreams) { + MsfBuilder Msf(Allocator); + Msf.initialize(4096); + + // one for the super block, one for the directory block map + uint32_t NumUsedPages = Msf.getNumUsedPages(); + EXPECT_EQ(2, NumUsedPages); + EXPECT_EQ(0, Msf.getNumFreePages()); + + const uint32_t StreamSizes[] = {4000, 6193, 189723}; + for (int I = 0; I < 3; ++I) { + EXPECT_NO_ERROR(Msf.addStream(StreamSizes[I])); + NumUsedPages += bytesToBlocks(StreamSizes[I], 4096); + EXPECT_EQ(NumUsedPages, Msf.getNumUsedPages()); + EXPECT_EQ(0, Msf.getNumFreePages()); + } +} + +TEST_F(MsfBuilderTest, TestBuildMsfLayout) { + // Test that we can generate an Msf Layout structure from a valid layout + // specification. + MsfBuilder Msf(Allocator); + Msf.initialize(4096); + const uint32_t StreamSizes[] = {4000, 6193, 189723}; + uint32_t ExpectedNumBlocks = 2; + for (int I = 0; I < 3; ++I) { + EXPECT_NO_ERROR(Msf.addStream(StreamSizes[I])); + ExpectedNumBlocks += bytesToBlocks(StreamSizes[I], 4096); + } + ++ExpectedNumBlocks; // The directory itself should use 1 block + + auto ExpectedLayout = Msf.build(); + EXPECT_EXPECTED(ExpectedLayout); + Layout &L = *ExpectedLayout; + EXPECT_EQ(4096, L.SB->BlockSize); + EXPECT_EQ(ExpectedNumBlocks, L.SB->NumBlocks); + + EXPECT_EQ(1, L.DirectoryBlocks.size()); + + EXPECT_EQ(3, L.StreamMap.size()); + EXPECT_EQ(3, L.StreamSizes.size()); + for (int I = 0; I < 3; ++I) { + EXPECT_EQ(StreamSizes[I], L.StreamSizes[I]); + uint32_t ExpectedNumPages = bytesToBlocks(StreamSizes[I], 4096); + EXPECT_EQ(ExpectedNumPages, L.StreamMap[I].size()); + } +}