[MSF] Fix FPM interval calculation

[zturner]

Summary

The FPM (free page map) in an MSF file is an odd structure. It is a series of blocks that are spread throughout the file at periodic intervals. And there are actually two separate FPMs organized in the file this way.

The first one, FPM0, begins at block 1 and a new piece occurs every BlockSize blocks.
The second one, FPM1, begins at block 2 and a new piece also occurs every BlockSize blocks.

Graphically, this can be represented like this:

Block Index |  0  |   1   |   2   |  ...  ┊  4096  |  4097  |  4098  | ... | 
    Meaning | SB  |  FPM0 | FPM1  | Data  ┊  Data  |  FPM0  |  FPM1  | ... |

where ┊ indicates a a period-boundary.

We had an off by 1 error where if there were exactly 4097 blocks (or, for that matter, 4096 * n + 1 blocks for any n), one piece of code would decide "oh that ends before FPM0 from this period, so we don't have an FPM0 to worry about" whereas another piece of code would say "there are two FPM intervals here" and then when iterating over those 2 intervals, would access uninitialized memory since the other piece of code only returned data from 1.

The fix here is to properly handle these edge cases. If block count is of the form 4096 * n + 1, we properly return n fpm intervals instead of n+1.

There's another odd edge case that wasn't being triggered, but was found by inspection when looking into this issue. We shouldn't ever create a PDB file with 4098 blocks, because that would look like this:

Block Index |  0  |   1   |   2   |  ...  ┊  4096  |  4097  |
    Meaning | SB  |  FPM0 | FPM1  | Data  ┊  Data  |  FPM0  |

and here we've got a continuation of FPM0 but not of FPM1. Although we can promise never to generate one of these, we probably should have the code handle it gracefully anyway and not crash (since we can't control what we see).

Initial investigative work and patch was done by Colden Cullen in D41734 (there's also some interesting discussion over there if anyone wants to follow)

[colden]

Makes sense! Thanks for adding a test btw.

I tested this with my use-case, and it does indeed fix the problem.

llvm/include/llvm/DebugInfo/MSF/MSFCommon.h

118

Naming nitpick: In other contexts, AltFpm implies the opposite of Msf.SB->FreeBlockMapBlock (i.e. 3 - FpmBlock). How about instead of taking that param here, you take an int for FpmIndex (or something), require it be 1 or 2, and then in the MSFLayout overload you can do the AltFpm transformation?

119

Ah, so I was almost right! Just didn't need the +1 on BlockSize.

[colden]

llvm/include/llvm/DebugInfo/MSF/MSFCommon.h

118

Follow up question: shouldn't it not matter which FPM you're using?

[zturner]

llvm/include/llvm/DebugInfo/MSF/MSFCommon.h

118

It only matters insofar as we want to handle that last edge case mentioned in the description of the diff. It won't matter for your case, but if somehow there were a PDB with *exactly* 4098 blocks (which again, LLD would never generate), then there would be 2 FPM0 intervals and 1 FPM1 interval.

[colden]

llvm/include/llvm/DebugInfo/MSF/MSFCommon.h

118

Oh I see what you mean. It's too bad we can't trim those on load, but maybe that's another patch for another day :)

[zturner]

Meh, I'm getting a crash when I run the full test suite with this patch. Will have to investigate.

[zturner]

False alarm, no crash. This update makes the suggested naming change, and also adds a detailed comment to the getNumFpmIntervals function.

[colden]

llvm/include/llvm/DebugInfo/MSF/MSFCommon.h

143

Sorry maybe I wasn't super clear before, but if you look at MSFCommon.cpp, getFpmStreamLayout, the AltFpm parameter there doesn't actually specify which Fpm block to use, but whether or not to use the Fpm block NOT referenced by the layout. To match that functionality, this should look more like:

int Fpm = L.SB->FreeBlockMapBlock;
return getNumFpmIntervals(L.SB->BlockSize, L.SB->NumBlocks,
                            IncludeUnusedFpmData, AltFpm ? 3U - Fpm  : Fpm);

Otherwise you could end up in situations where your active FPM is 2, but you want to initialize 1, so you pass true for AltFpm. That just gets you 2 anyway. This is how it's used in PDBFileBuilder::commitFpm, when it initializes the second Fpm but never uses it.

[zturner]

llvm/include/llvm/DebugInfo/MSF/MSFCommon.h

143

Ahh yea, I see your point.

[zturner]

Updated with suggestions

[colden]

I'm assuming you'll want approval from someone else too, but this looks good to me, and is proven to fix my bug.

llvm/include/llvm/DebugInfo/MSF/MSFCommon.h

144

Oh that's even cleaner.

[colden]

Oh hey also, should this go in 6.0?

llvm/include/llvm/DebugInfo/MSF/MSFCommon.h

 inline uint64_t blockToOffset(uint64_t BlockNumber, uint64_t BlockSize) {
   return BlockNumber * BlockSize;
 }
 
 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 ? 2 : 1);
 }
 
 Error validateSuperBlock(const SuperBlock &SB);
 
 } // end namespace msf
 } // end namespace llvm
 
 #endif // LLVM_DEBUGINFO_MSF_MSFCOMMON_H

llvm/lib/DebugInfo/MSF/MSFCommon.cpp

Error llvm::msf::validateSuperBlock(const SuperBlock &SB) {
 
   return Error::success();
 }
 
 MSFStreamLayout llvm::msf::getFpmStreamLayout(const MSFLayout &Msf,
                                               bool IncludeUnusedFpmData,
                                               bool AltFpm) {
   MSFStreamLayout FL;
-  uint32_t NumFpmIntervals = getNumFpmIntervals(Msf, IncludeUnusedFpmData);
+  uint32_t NumFpmIntervals =
+      getNumFpmIntervals(Msf, IncludeUnusedFpmData, AltFpm);
   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;
   }
   for (uint32_t I = 0; I < NumFpmIntervals; ++I) {
     FL.Blocks.push_back(FpmBlock);

llvm/unittests/DebugInfo/MSF/MSFCommonTest.cpp

TEST(MSFCommonTest, FpmIntervals) {
   EXPECT_EQ(1u, getNumFpmIntervals(L, false));
   SB.NumBlocks = SB.BlockSize * 8 + 1;
   EXPECT_EQ(2u, getNumFpmIntervals(L, false));
 
   SB.NumBlocks = 12;
   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, false));
+    EXPECT_EQ(1U, getNumFpmIntervals(4096, I, false, false));
+
+    // 1 FPM1 interval
+    EXPECT_EQ(1U, getNumFpmIntervals(4096, I, true, true));
+    EXPECT_EQ(1U, getNumFpmIntervals(4096, I, false, true));
+  }
+
+  // With 4098 blocks, the last block belongs to FPM0 so we should have 2 FPM0
+  // intervals.
+  EXPECT_EQ(2U, getNumFpmIntervals(4096, 4098, true, false));
+  EXPECT_EQ(1U, getNumFpmIntervals(4096, 4098, false, false));
+
+  // And 1 FPM1 interval.
+  EXPECT_EQ(1U, getNumFpmIntervals(4096, 4098, true, true));
+  EXPECT_EQ(1U, getNumFpmIntervals(4096, 4098, false, true));
+
+  // With 4099 blocks, the last block belongs to FPM1 so we should have 2
+  // FPM0 intervals.
+  EXPECT_EQ(2U, getNumFpmIntervals(4096, 4099, true, false));
+  EXPECT_EQ(1U, getNumFpmIntervals(4096, 4099, false, false));
+
+  // And 2 FPM1 intervals.
+  EXPECT_EQ(2U, getNumFpmIntervals(4096, 4099, true, true));
+  EXPECT_EQ(1U, getNumFpmIntervals(4096, 4099, false, true));
 }
 
 TEST(MSFCommonTest, FpmStreamLayout) {
   SuperBlock SB;
   MSFLayout L;
   L.SB = &SB;
   SB.FreeBlockMapBlock = 1;
 
TEST(MSFCommonTest, FpmStreamLayout) {
   EXPECT_EQ(SB.BlockSize + 1, SL.Length);
   EXPECT_EQ(2u, SL.Blocks.size());
   EXPECT_EQ(3u - SB.FreeBlockMapBlock, SL.Blocks[0]);
   EXPECT_EQ(3u - SB.FreeBlockMapBlock + SB.BlockSize, SL.Blocks[1]);
 
   // 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());
   for (int I = 0; I < 9; ++I)
     EXPECT_EQ(I * SB.BlockSize + SB.FreeBlockMapBlock, SL.Blocks[I]);
 }