Index: llvm/trunk/include/llvm/DebugInfo/PDB/Raw/MsfBuilder.h =================================================================== --- llvm/trunk/include/llvm/DebugInfo/PDB/Raw/MsfBuilder.h +++ llvm/trunk/include/llvm/DebugInfo/PDB/Raw/MsfBuilder.h @@ -0,0 +1,136 @@ +//===- 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: + /// \brief Create a new `MsfBuilder`. + /// + /// \param BlockSize The internal block size used by the PDB file. See + /// isValidBlockSize() for a list of valid block sizes. + /// + /// \param MinBlockCount Causes the builder to reserve up front space for + /// at least `MinBlockCount` blocks. This is useful when using `MsfBuilder` + /// to read an existing PDB that you want to write back out later. The + /// original PDB file's SuperBlock contains the exact number of blocks used + /// by the file, so is a good hint as to how many blocks the new PDB file + /// will contain. Furthermore, it is actually necessary in this case. To + /// preserve stability of the file's layout, it is helpful to try to keep + /// all streams mapped to their original block numbers. To ensure that this + /// is possible, space for all blocks must be allocated beforehand so that + /// streams can be assigned to them. + /// + /// \param CanGrow If true, any operation which results in an attempt to + /// locate a free block when all available blocks have been exhausted will + /// allocate a new block, thereby growing the size of the final PDB file. + /// When false, any such attempt will result in an error. This is especially + /// useful in testing scenarios when you know your test isn't going to do + /// anything to increase the size of the file, so having an Error returned if + /// it were to happen would catch a programming error + /// + /// \returns an llvm::Error representing whether the operation succeeded or + /// failed. Currently the only way this can fail is if an invalid block size + /// is specified, or `MinBlockCount` does not leave enough room for the + /// mandatory reserved blocks required by an MSF file. + static Expected create(BumpPtrAllocator &Allocator, + uint32_t BlockSize, + uint32_t MinBlockCount = 0, + bool CanGrow = true); + + /// Request the block map to be at a specific block address. This is useful + /// when editing a PDB and you want the layout to be as stable as possible. + Error setBlockMapAddr(uint32_t Addr); + + /// Add a stream to the MSF file with the given size, occupying the given + /// list of blocks. This is useful when reading a PDB file and you want a + /// particular stream to occupy the original set of blocks. If the given + /// blocks are already allocated, or if the number of blocks specified is + /// incorrect for the given stream size, this function will return an Error. + Error addStream(uint32_t Size, ArrayRef Blocks); + + /// Add a stream to the MSF file with the given size, occupying any available + /// blocks that the builder decides to use. This is useful when building a + /// new PDB file from scratch and you don't care what blocks a stream occupies + /// but you just want it to work. + Error addStream(uint32_t Size); + + /// Update the size of an existing stream. This will allocate or deallocate + /// blocks as needed to match the requested size. This can fail if `CanGrow` + /// was set to false when initializing the `MsfBuilder`. + Error setStreamSize(uint32_t Idx, uint32_t Size); + + /// Get the total number of streams in the MSF layout. This should return 1 + /// for every call to `addStream`. + uint32_t getNumStreams() const; + + /// Get the size of a stream by index. + uint32_t getStreamSize(uint32_t StreamIdx) const; + + /// Get the list of blocks allocated to a particular stream. + ArrayRef getStreamBlocks(uint32_t StreamIdx) const; + + /// Get the total number of blocks that will be allocated to actual data in + /// this MSF file. + uint32_t getNumUsedBlocks() const; + + /// Get the total number of blocks that exist in the MSF file but are not + /// allocated to any valid data. + uint32_t getNumFreeBlocks() const; + + /// Get the total number of blocks in the MSF file. In practice this is equal + /// to `getNumUsedBlocks() + getNumFreeBlocks()`. + uint32_t getTotalBlockCount() const; + + /// Check whether a particular block is allocated or free. + bool isBlockFree(uint32_t Idx) const; + + /// Finalize the layout and build the headers and structures that describe the + /// MSF layout and can be written directly to the MSF file. + Expected build(); + +private: + MsfBuilder(uint32_t BlockSize, uint32_t MinBlockCount, bool CanGrow, + BumpPtrAllocator &Allocator); + + Error allocateBlocks(uint32_t NumBlocks, MutableArrayRef Blocks); + uint32_t computeDirectoryByteSize() const; + + typedef std::vector BlockList; + + BumpPtrAllocator &Allocator; + + bool IsGrowable; + uint32_t BlockSize; + uint32_t MininumBlocks; + uint32_t BlockMapAddr; + BitVector FreeBlocks; + std::vector DirectoryBlocks; + std::vector> StreamData; +}; +} +} + +#endif Index: llvm/trunk/include/llvm/DebugInfo/PDB/Raw/MsfCommon.h =================================================================== --- llvm/trunk/include/llvm/DebugInfo/PDB/Raw/MsfCommon.h +++ llvm/trunk/include/llvm/DebugInfo/PDB/Raw/MsfCommon.h @@ -0,0 +1,83 @@ +//===- 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 bool isValidBlockSize(uint32_t Size) { + switch (Size) { + case 512: + case 1024: + case 2048: + case 4096: + return true; + } + return false; +} + +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: llvm/trunk/lib/DebugInfo/PDB/CMakeLists.txt =================================================================== --- llvm/trunk/lib/DebugInfo/PDB/CMakeLists.txt +++ llvm/trunk/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: llvm/trunk/lib/DebugInfo/PDB/Raw/MsfBuilder.cpp =================================================================== --- llvm/trunk/lib/DebugInfo/PDB/Raw/MsfBuilder.cpp +++ llvm/trunk/lib/DebugInfo/PDB/Raw/MsfBuilder.cpp @@ -0,0 +1,240 @@ +//===- 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 kSuperBlockBlock = 0; +const uint32_t kDefaultBlockMapAddr = 1; +} + +MsfBuilder::MsfBuilder(uint32_t BlockSize, uint32_t MinBlockCount, bool CanGrow, + BumpPtrAllocator &Allocator) + : Allocator(Allocator), BlockSize(BlockSize), MininumBlocks(MinBlockCount), + IsGrowable(CanGrow), BlockMapAddr(kDefaultBlockMapAddr), + FreeBlocks(MinBlockCount + 2U, true) { + FreeBlocks[kSuperBlockBlock] = false; + FreeBlocks[BlockMapAddr] = false; +} + +Expected MsfBuilder::create(BumpPtrAllocator &Allocator, + uint32_t BlockSize, + uint32_t MinBlockCount, bool CanGrow) { + if (!msf::isValidBlockSize(BlockSize)) + return make_error(raw_error_code::unspecified, + "The requested block size is unsupported"); + + return MsfBuilder(BlockSize, MinBlockCount, CanGrow, Allocator); +} + +Error MsfBuilder::setBlockMapAddr(uint32_t Addr) { + if (Addr == BlockMapAddr) + return Error::success(); + + if (Addr >= FreeBlocks.size()) { + if (!IsGrowable) + return make_error(raw_error_code::unspecified, + "Cannot grow the number of blocks"); + FreeBlocks.resize(Addr + 1); + } + + if (!isBlockFree(Addr)) + return make_error(raw_error_code::unspecified, + "Attempt to reuse an allocated block"); + FreeBlocks[BlockMapAddr] = true; + FreeBlocks[Addr] = false; + BlockMapAddr = Addr; + return Error::success(); +} + +Error MsfBuilder::allocateBlocks(uint32_t NumBlocks, + MutableArrayRef Blocks) { + if (NumBlocks == 0) + return Error::success(); + + uint32_t NumFreeBlocks = FreeBlocks.count(); + if (NumFreeBlocks < NumBlocks) { + if (!IsGrowable) + return make_error(raw_error_code::unspecified, + "There are no free Blocks in the file"); + uint32_t AllocBlocks = NumBlocks - NumFreeBlocks; + FreeBlocks.resize(AllocBlocks + FreeBlocks.size(), true); + } + + int I = 0; + int Block = FreeBlocks.find_first(); + do { + assert(Block != -1 && "We ran out of Blocks!"); + + uint32_t NextBlock = static_cast(Block); + Blocks[I++] = NextBlock; + FreeBlocks.reset(NextBlock); + Block = FreeBlocks.find_next(Block); + } while (--NumBlocks > 0); + return Error::success(); +} + +uint32_t MsfBuilder::getNumUsedBlocks() const { + return getTotalBlockCount() - getNumFreeBlocks(); +} + +uint32_t MsfBuilder::getNumFreeBlocks() const { return FreeBlocks.count(); } + +uint32_t MsfBuilder::getTotalBlockCount() const { return FreeBlocks.size(); } + +bool MsfBuilder::isBlockFree(uint32_t Idx) const { return FreeBlocks[Idx]; } + +Error MsfBuilder::addStream(uint32_t Size, ArrayRef Blocks) { + // 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 >= FreeBlocks.size()) + FreeBlocks.resize(Block + 1, true); + + if (!FreeBlocks.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) { + FreeBlocks.reset(Block); + } + StreamData.push_back(std::make_pair(Size, Blocks)); + return Error::success(); +} + +Error MsfBuilder::addStream(uint32_t Size) { + uint32_t ReqBlocks = bytesToBlocks(Size, BlockSize); + std::vector NewBlocks; + NewBlocks.resize(ReqBlocks); + if (auto EC = allocateBlocks(ReqBlocks, NewBlocks)) + return EC; + StreamData.push_back(std::make_pair(Size, NewBlocks)); + return Error::success(); +} + +Error MsfBuilder::setStreamSize(uint32_t Idx, uint32_t Size) { + uint32_t OldSize = getStreamSize(Idx); + if (OldSize == Size) + return Error::success(); + + uint32_t NewBlocks = bytesToBlocks(Size, BlockSize); + uint32_t OldBlocks = bytesToBlocks(OldSize, BlockSize); + + if (NewBlocks > OldBlocks) { + uint32_t AddedBlocks = NewBlocks - OldBlocks; + // If we're growing, we have to allocate new Blocks. + std::vector AddedBlockList; + AddedBlockList.resize(AddedBlocks); + if (auto EC = allocateBlocks(AddedBlocks, AddedBlockList)) + return EC; + auto &CurrentBlocks = StreamData[Idx].second; + CurrentBlocks.insert(CurrentBlocks.end(), AddedBlockList.begin(), + AddedBlockList.end()); + } else if (OldBlocks > NewBlocks) { + // For shrinking, free all the Blocks in the Block map, update the stream + // data, then shrink the directory. + uint32_t RemovedBlocks = OldBlocks - NewBlocks; + auto CurrentBlocks = ArrayRef(StreamData[Idx].second); + auto RemovedBlockList = CurrentBlocks.drop_front(NewBlocks); + for (auto P : RemovedBlockList) + FreeBlocks[P] = true; + StreamData[Idx].second = CurrentBlocks.drop_back(RemovedBlocks); + } + + 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() { + Layout L; + L.SB = Allocator.Allocate(); + std::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 = allocateBlocks(NumDirectoryBlocks, DirectoryBlocks)) + return std::move(EC); + + // Don't set the number of blocks in the file until after allocating Blocks + // for + // the directory, since the allocation might cause the file to need to grow. + L.SB->NumBlocks = FreeBlocks.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()); + } + } + + return L; +} Index: llvm/trunk/lib/DebugInfo/PDB/Raw/MsfCommon.cpp =================================================================== --- llvm/trunk/lib/DebugInfo/PDB/Raw/MsfCommon.cpp +++ llvm/trunk/lib/DebugInfo/PDB/Raw/MsfCommon.cpp @@ -0,0 +1,48 @@ +//===- 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 (std::memcmp(SB.MagicBytes, Magic, sizeof(Magic)) != 0) + return make_error(raw_error_code::corrupt_file, + "MSF magic header doesn't match"); + + if (!isValidBlockSize(SB.BlockSize)) + 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: llvm/trunk/unittests/DebugInfo/PDB/CMakeLists.txt =================================================================== --- llvm/trunk/unittests/DebugInfo/PDB/CMakeLists.txt +++ llvm/trunk/unittests/DebugInfo/PDB/CMakeLists.txt @@ -5,6 +5,7 @@ set(DebugInfoPDBSources MappedBlockStreamTest.cpp + MsfBuilderTest.cpp PDBApiTest.cpp ) Index: llvm/trunk/unittests/DebugInfo/PDB/ErrorChecking.h =================================================================== --- llvm/trunk/unittests/DebugInfo/PDB/ErrorChecking.h +++ llvm/trunk/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: llvm/trunk/unittests/DebugInfo/PDB/MappedBlockStreamTest.cpp =================================================================== --- llvm/trunk/unittests/DebugInfo/PDB/MappedBlockStreamTest.cpp +++ llvm/trunk/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: llvm/trunk/unittests/DebugInfo/PDB/MsfBuilderTest.cpp =================================================================== --- llvm/trunk/unittests/DebugInfo/PDB/MsfBuilderTest.cpp +++ llvm/trunk/unittests/DebugInfo/PDB/MsfBuilderTest.cpp @@ -0,0 +1,300 @@ +//===- 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 powers of 2. + 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 assigning a stream to a known list of blocks, the blocks + // are correctly marked as used after adding, but no other incorrect blocks + // are accidentally marked as used. + + // Allocate some extra blocks at the end so we can verify that they're free + // after the initialization. + std::vector Blocks = {2, 3, 4, 5, 6, 7, 8, 9, 10}; + auto ExpectedMsf = MsfBuilder::create(Allocator, 4096, Blocks.size() + 10); + EXPECT_EXPECTED(ExpectedMsf); + auto &Msf = *ExpectedMsf; + + EXPECT_NO_ERROR(Msf.addStream(Blocks.size() * 4096, Blocks)); + + for (auto B : Blocks) { + EXPECT_FALSE(Msf.isBlockFree(B)); + } + for (int I = 11; I < 21; ++I) { + EXPECT_TRUE(Msf.isBlockFree(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 Block boundary. + auto ExpectedMsf = MsfBuilder::create(Allocator, 4096); + EXPECT_EXPECTED(ExpectedMsf); + auto &Msf = *ExpectedMsf; + + auto ExpectedL1 = Msf.build(); + EXPECT_EXPECTED(ExpectedL1); + Layout &L1 = *ExpectedL1; + + auto OldDirBlocks = L1.DirectoryBlocks; + EXPECT_EQ(1U, OldDirBlocks.size()); + + auto ExpectedMsf2 = MsfBuilder::create(Allocator, 4096); + EXPECT_EXPECTED(ExpectedMsf2); + auto &Msf2 = *ExpectedMsf2; + + EXPECT_NO_ERROR(Msf2.addStream(4000)); + EXPECT_EQ(1U, Msf2.getNumStreams()); + EXPECT_EQ(4000U, Msf2.getStreamSize(0)); + auto Blocks = Msf2.getStreamBlocks(0); + EXPECT_EQ(1U, Blocks.size()); + + auto ExpectedL2 = Msf2.build(); + EXPECT_EXPECTED(ExpectedL2); + Layout &L2 = *ExpectedL2; + auto NewDirBlocks = L2.DirectoryBlocks; + EXPECT_EQ(1U, 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 Block boundary. This is because the newly added stream occupies + // so many Blocks that need to be indexed in the directory that the directory + // crosses a Block boundary. + auto ExpectedMsf = MsfBuilder::create(Allocator, 4096); + EXPECT_EXPECTED(ExpectedMsf); + auto &Msf = *ExpectedMsf; + + 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(2U, DirBlocks.size()); +} + +TEST_F(MsfBuilderTest, TestGrowStreamNoBlockIncrease) { + // Test growing an existing stream by a value that does not affect the number + // of blocks it occupies. + auto ExpectedMsf = MsfBuilder::create(Allocator, 4096); + EXPECT_EXPECTED(ExpectedMsf); + auto &Msf = *ExpectedMsf; + + EXPECT_NO_ERROR(Msf.addStream(1024)); + EXPECT_EQ(1024U, Msf.getStreamSize(0)); + auto OldStreamBlocks = Msf.getStreamBlocks(0); + EXPECT_EQ(1U, OldStreamBlocks.size()); + + EXPECT_NO_ERROR(Msf.setStreamSize(0, 2048)); + EXPECT_EQ(2048U, Msf.getStreamSize(0)); + auto NewStreamBlocks = Msf.getStreamBlocks(0); + EXPECT_EQ(1U, NewStreamBlocks.size()); + + EXPECT_EQ(OldStreamBlocks, NewStreamBlocks); +} + +TEST_F(MsfBuilderTest, TestGrowStreamWithBlockIncrease) { + // Test that growing an existing stream to a value large enough that it causes + // the need to allocate new Blocks to the stream correctly updates the + // stream's + // block list. + auto ExpectedMsf = MsfBuilder::create(Allocator, 4096); + EXPECT_EXPECTED(ExpectedMsf); + auto &Msf = *ExpectedMsf; + + EXPECT_NO_ERROR(Msf.addStream(2048)); + EXPECT_EQ(2048U, Msf.getStreamSize(0)); + std::vector OldStreamBlocks = Msf.getStreamBlocks(0); + EXPECT_EQ(1U, OldStreamBlocks.size()); + + EXPECT_NO_ERROR(Msf.setStreamSize(0, 6144)); + EXPECT_EQ(6144U, Msf.getStreamSize(0)); + std::vector NewStreamBlocks = Msf.getStreamBlocks(0); + EXPECT_EQ(2U, 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 Blocks it occupies makes no changes to stream's block list. + auto ExpectedMsf = MsfBuilder::create(Allocator, 4096); + EXPECT_EXPECTED(ExpectedMsf); + auto &Msf = *ExpectedMsf; + + EXPECT_NO_ERROR(Msf.addStream(2048)); + EXPECT_EQ(2048U, Msf.getStreamSize(0)); + std::vector OldStreamBlocks = Msf.getStreamBlocks(0); + EXPECT_EQ(1U, OldStreamBlocks.size()); + + EXPECT_NO_ERROR(Msf.setStreamSize(0, 1024)); + EXPECT_EQ(1024U, Msf.getStreamSize(0)); + std::vector NewStreamBlocks = Msf.getStreamBlocks(0); + EXPECT_EQ(1U, NewStreamBlocks.size()); + + EXPECT_EQ(OldStreamBlocks, NewStreamBlocks); +} + +TEST_F(MsfBuilderTest, TestShrinkStreamWithBlockDecrease) { + // Test that shrinking an existing stream to a value large enough that it + // causes the need to deallocate new Blocks to the stream correctly updates + // the stream's block list. + auto ExpectedMsf = MsfBuilder::create(Allocator, 4096); + EXPECT_EXPECTED(ExpectedMsf); + auto &Msf = *ExpectedMsf; + + EXPECT_NO_ERROR(Msf.addStream(6144)); + EXPECT_EQ(6144U, Msf.getStreamSize(0)); + std::vector OldStreamBlocks = Msf.getStreamBlocks(0); + EXPECT_EQ(2U, OldStreamBlocks.size()); + + EXPECT_NO_ERROR(Msf.setStreamSize(0, 2048)); + EXPECT_EQ(2048U, Msf.getStreamSize(0)); + std::vector NewStreamBlocks = Msf.getStreamBlocks(0); + EXPECT_EQ(1U, 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. + auto ExpectedMsf = MsfBuilder::create(Allocator, 4096); + EXPECT_EXPECTED(ExpectedMsf); + auto &Msf = *ExpectedMsf; + + EXPECT_NO_ERROR(Msf.addStream(6144)); + + std::vector Blocks = {2, 3}; + EXPECT_ERROR(Msf.addStream(6144, Blocks)); +} + +TEST_F(MsfBuilderTest, TestBlockCountsWhenAddingStreams) { + // Test that when adding multiple streams, the number of used and free Blocks + // allocated to the MSF file are as expected. + auto ExpectedMsf = MsfBuilder::create(Allocator, 4096); + EXPECT_EXPECTED(ExpectedMsf); + auto &Msf = *ExpectedMsf; + + // one for the super block, one for the directory block map + uint32_t NumUsedBlocks = Msf.getNumUsedBlocks(); + EXPECT_EQ(2U, NumUsedBlocks); + EXPECT_EQ(0U, Msf.getNumFreeBlocks()); + + const uint32_t StreamSizes[] = {4000, 6193, 189723}; + for (int I = 0; I < 3; ++I) { + EXPECT_NO_ERROR(Msf.addStream(StreamSizes[I])); + NumUsedBlocks += bytesToBlocks(StreamSizes[I], 4096); + EXPECT_EQ(NumUsedBlocks, Msf.getNumUsedBlocks()); + EXPECT_EQ(0U, Msf.getNumFreeBlocks()); + } +} + +TEST_F(MsfBuilderTest, TestBuildMsfLayout) { + // Test that we can generate an Msf Layout structure from a valid layout + // specification. + auto ExpectedMsf = MsfBuilder::create(Allocator, 4096); + EXPECT_EXPECTED(ExpectedMsf); + auto &Msf = *ExpectedMsf; + + 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(4096U, L.SB->BlockSize); + EXPECT_EQ(ExpectedNumBlocks, L.SB->NumBlocks); + + EXPECT_EQ(1U, L.DirectoryBlocks.size()); + + EXPECT_EQ(3U, L.StreamMap.size()); + EXPECT_EQ(3U, L.StreamSizes.size()); + for (int I = 0; I < 3; ++I) { + EXPECT_EQ(StreamSizes[I], L.StreamSizes[I]); + uint32_t ExpectedNumBlocks = bytesToBlocks(StreamSizes[I], 4096); + EXPECT_EQ(ExpectedNumBlocks, L.StreamMap[I].size()); + } +}