[MSF] Fix FPM interval calcluation

We have some code to try to determine how many pieces an MSF
Free Page Map is split into, and this code had an off by one
error which would cause the calculation to be incorrect when
there were exactly 4096*k + 1 blocks in an MSF file.

Original investigation and patch outline by Colden Cullen.

Differential Revision: https://reviews.llvm.org/D41742

llvm-svn: 321880

3 files changed, 87 insertions, 18 deletions

diff --git a/llvm/include/llvm/DebugInfo/MSF/MSFCommon.h b/llvm/include/llvm/DebugInfo/MSF/MSFCommon.h
index f28415d4e60..dd532647b71 100644
--- a/llvm/include/llvm/DebugInfo/MSF/MSFCommon.h
+++ b/llvm/include/llvm/DebugInfo/MSF/MSFCommon.h
@@ -52,6 +52,16 @@ struct SuperBlock {
 struct MSFLayout {
   MSFLayout() = default;
 
+  uint32_t mainFpmBlock() const {
+    assert(SB->FreeBlockMapBlock == 1 || SB->FreeBlockMapBlock == 2);
+    return SB->FreeBlockMapBlock;
+  }
+
+  uint32_t alternateFpmBlock() const {
+    // If mainFpmBlock is 1, this is 2.  If mainFpmBlock is 2, this is 1.
+    return 3U - mainFpmBlock();
+  }
+
   const SuperBlock *SB = nullptr;
   BitVector FreePageMap;
   ArrayRef<support::ulittle32_t> DirectoryBlocks;
@@ -108,14 +118,40 @@ inline uint32_t getFpmIntervalLength(const MSFLayout &L) {
   return L.SB->BlockSize;
 }
 
-inline uint32_t getNumFpmIntervals(const MSFLayout &L,
-                                   bool IncludeUnusedFpmData = false) {
-  if (IncludeUnusedFpmData)
-    return divideCeil(L.SB->NumBlocks, L.SB->BlockSize);
+/// Given an MSF with the specified block size and number of blocks, determine
+/// how many pieces the specified Fpm is split into.
+/// \p BlockSize - the block size of the MSF
+/// \p NumBlocks - the total number of blocks in the MSF
+/// \p IncludeUnusedFpmData - When true, this will count every block that is
+///    both in the file and matches the form of an FPM block, even if some of
+///    those FPM blocks are unused (a single FPM block can describe the
+///    allocation status of up to 32,767 blocks, although one appears only
+///    every 4,096 blocks).  So there are 8x as many blocks that match the
+///    form as there are blocks that are necessary to describe the allocation
+///    status of the file.  When this parameter is false, these extraneous
+///    trailing blocks are not counted.
+inline uint32_t getNumFpmIntervals(uint32_t BlockSize, uint32_t NumBlocks,
+                                   bool IncludeUnusedFpmData, int FpmNumber) {
+  assert(FpmNumber == 1 || FpmNumber == 2);
+  if (IncludeUnusedFpmData) {
+    // This calculation determines how many times a number of the form
+    // BlockSize * k + N appears in the range [0, NumBlocks).  We only need to
+    // do this when unused data is included, since the number of blocks dwarfs
+    // the number of fpm blocks.
+    return divideCeil(NumBlocks - FpmNumber, BlockSize);
+  }
 
   // We want the minimum number of intervals required, where each interval can
   // represent BlockSize * 8 blocks.
-  return divideCeil(L.SB->NumBlocks, 8 * L.SB->BlockSize);
+  return divideCeil(NumBlocks, 8 * BlockSize);
+}
+
+inline uint32_t getNumFpmIntervals(const MSFLayout &L,
+                                   bool IncludeUnusedFpmData = false,
+                                   bool AltFpm = false) {
+  return getNumFpmIntervals(L.SB->BlockSize, L.SB->NumBlocks,
+                            IncludeUnusedFpmData,
+                            AltFpm ? L.alternateFpmBlock() : L.mainFpmBlock());
 }
 
 Error validateSuperBlock(const SuperBlock &SB);
diff --git a/llvm/lib/DebugInfo/MSF/MSFCommon.cpp b/llvm/lib/DebugInfo/MSF/MSFCommon.cpp
index d7e1dcf31a3..d398304375a 100644
--- a/llvm/lib/DebugInfo/MSF/MSFCommon.cpp
+++ b/llvm/lib/DebugInfo/MSF/MSFCommon.cpp
@@ -64,15 +64,13 @@ MSFStreamLayout llvm::msf::getFpmStreamLayout(const MSFLayout &Msf,
                                               bool IncludeUnusedFpmData,
                                               bool AltFpm) {
   MSFStreamLayout FL;
-  uint32_t NumFpmIntervals = getNumFpmIntervals(Msf, IncludeUnusedFpmData);
-  support::ulittle32_t FpmBlock = Msf.SB->FreeBlockMapBlock;
-  assert(FpmBlock == 1 || FpmBlock == 2);
-  if (AltFpm) {
-    // If they requested the alternate FPM, then 2 becomes 1 and 1 becomes 2.
-    FpmBlock = 3U - FpmBlock;
-  }
+  uint32_t NumFpmIntervals =
+      getNumFpmIntervals(Msf, IncludeUnusedFpmData, AltFpm);
+
+  uint32_t FpmBlock = AltFpm ? Msf.alternateFpmBlock() : Msf.mainFpmBlock();
+
   for (uint32_t I = 0; I < NumFpmIntervals; ++I) {
-    FL.Blocks.push_back(FpmBlock);
+    FL.Blocks.push_back(support::ulittle32_t(FpmBlock));
     FpmBlock += msf::getFpmIntervalLength(Msf);
   }
 
diff --git a/llvm/unittests/DebugInfo/MSF/MSFCommonTest.cpp b/llvm/unittests/DebugInfo/MSF/MSFCommonTest.cpp
index 144f5b113fb..ee9ac75d15c 100644
--- a/llvm/unittests/DebugInfo/MSF/MSFCommonTest.cpp
+++ b/llvm/unittests/DebugInfo/MSF/MSFCommonTest.cpp
@@ -46,12 +46,47 @@ TEST(MSFCommonTest, FpmIntervals) {
   EXPECT_EQ(1u, getNumFpmIntervals(L, true));
   SB.NumBlocks = SB.BlockSize;
   EXPECT_EQ(1u, getNumFpmIntervals(L, true));
-  SB.NumBlocks = SB.BlockSize + 1;
-  EXPECT_EQ(2u, getNumFpmIntervals(L, true));
   SB.NumBlocks = SB.BlockSize * 8;
   EXPECT_EQ(8u, getNumFpmIntervals(L, true));
-  SB.NumBlocks = SB.BlockSize * 8 + 1;
-  EXPECT_EQ(9u, getNumFpmIntervals(L, true));
+
+  // The FPM is going to look like this:
+  // |  0  |   1   |   2   |  ...  |  4096  |  4097  |  4098  | ... |
+  // | SB  |  FPM0 | FPM1  | Data  |  Data  |  FPM0  |  FPM1  | ... |
+  //
+  // So when there are up to 4097 blocks (last index 4096), the final blocks
+  // are data blocks.  When there are 4098 blocks (last index 4097), there is
+  // one terminating FPM block, and when there are 4099 blocks, there are two
+  // terminating FPM blocks.  Make sure all these cases are handled.
+
+  // With 4096 or 4097 blocks, the last block is a data block so we only have
+  // 1 interval.
+  for (uint32_t I : {4096, 4097}) {
+    // 1 FPM0 interval
+    EXPECT_EQ(1U, getNumFpmIntervals(4096, I, true, 1));
+    EXPECT_EQ(1U, getNumFpmIntervals(4096, I, false, 1));
+
+    // 1 FPM1 interval
+    EXPECT_EQ(1U, getNumFpmIntervals(4096, I, true, 2));
+    EXPECT_EQ(1U, getNumFpmIntervals(4096, I, false, 2));
+  }
+
+  // With 4098 blocks, the last block belongs to FPM0 so we should have 2 FPM0
+  // intervals.
+  EXPECT_EQ(2U, getNumFpmIntervals(4096, 4098, true, 1));
+  EXPECT_EQ(1U, getNumFpmIntervals(4096, 4098, false, 1));
+
+  // And 1 FPM1 interval.
+  EXPECT_EQ(1U, getNumFpmIntervals(4096, 4098, true, 2));
+  EXPECT_EQ(1U, getNumFpmIntervals(4096, 4098, false, 2));
+
+  // With 4099 blocks, the last block belongs to FPM1 so we should have 2
+  // FPM0 intervals.
+  EXPECT_EQ(2U, getNumFpmIntervals(4096, 4099, true, 1));
+  EXPECT_EQ(1U, getNumFpmIntervals(4096, 4099, false, 1));
+
+  // And 2 FPM1 intervals.
+  EXPECT_EQ(2U, getNumFpmIntervals(4096, 4099, true, 2));
+  EXPECT_EQ(1U, getNumFpmIntervals(4096, 4099, false, 2));
 }
 
 TEST(MSFCommonTest, FpmStreamLayout) {
@@ -95,7 +130,7 @@ TEST(MSFCommonTest, FpmStreamLayout) {
   // 2. When we are including unused FPM data, there should be one FPM block
   //    at every BlockSize interval in the file, even if entire FPM blocks are
   //    unused.
-  SB.NumBlocks = SB.BlockSize * 8 + 1;
+  SB.NumBlocks = SB.BlockSize * 8 + 3;
   SL = getFpmStreamLayout(L, true, false);
   EXPECT_EQ(SB.BlockSize * 9, SL.Length);
   EXPECT_EQ(9u, SL.Blocks.size());