[Docs][PDB] Update MSF File documentation

[colden]

Summary

As long as we have all this super useful knowledge, may as well share it.

[zturner]

Few minor nits, but thanks for doing this!

docs/PDB/MsfFile.rst

25

Shouldn't this be BlockSize - 3? The pattern is Block 0, Block 1, Block 2, <BlockSize - 3 more blocks>

35

Can we call it FPM instead of FBM? We use the terms Page and Block sometimes interchangeably, but we never refer to anything other than FPM in the code.

102–105

I think this sentence is a bit wrong. The first two bytes of each FPM are not necessarily 1. But the first *three bits* of each FPM are. And not necessarily each FPM either, only the active one. I would just say "There is one bit in the FPM for every block in the file, including the super block." that should be clear enough that there are no exceptions.

[colden]

docs/PDB/MsfFile.rst

25

I don't think so. I may be wrong, but here was my thinking.

If the second FPM0 is at index 4097, that means that there are 4097 blocks before it. BUT, if the interval size is 4096, that means that there's 1 extra block in the first interval, which *I think* would have to be the super block.

I can probably word this better, so I'll work on it, but I think the pattern is Super Block, followed by 1+ 4096 block-intervals repeating

35

Yeah for sure.

I'm glad you brought this up though, because the the code use is actually super confusing. Whenever we use the whole words, it's always FreeBlockMap (see SuperBlock struct), but whenever its an acronym, it's FPM. Should we just pick one and rename everything to that? I'd be happy to do that as a separate change, if we can agree on which one to go with. I personally prefer FBM, because everything else refers to them as "Blocks," not "Pages."

Maybe I'm just bitter because it took me about an hour to figure out what FPM stood for :)

102–105

So it seems like there's a couple issues here:

1. You are correct, I should have said "bits"
2. You are correct, this is only guaranteed of the active FPM.
3. 2 vs 3, This one I'm unsure about. The MS code does indeed mark the first 3 bits as "in-use,"[0] but thinking about this in conjunction with your first question, that doesn't really make sense. Because the first interval contains 4097 blocks, there *must* be one that isn't referenced by the FPM. My assumption would be it's the SuperBlock (how could it possibly be "free?").

Am I missing something obvious here? The more I think about this the more confusing it gets.

[0] The comment where you described the process of it marking 3 pages as allocated: https://reviews.llvm.org/D41734#967624

[zturner]

I think it's the block at the beginning that is throwing you off. *every* interval consists of 4096 blocks. And *every* interval looks like this:

+-------------+-------+------------------+------------------+------+------+------+
| Block Index | 0     | 1                | 2                | 3    | ...  | 4095 |
+=============+=======+==================+==================+======+======+======+
| Meaning     | Data  | Free Block Map 1 | Free Block Map 2 | Data | Data | Data |
+-------------+-------+------------------+------------------+------+------+------+

So each interval has exactly 4096 blocks. Block 0 is only special in the first interval. It's still there in every other interval, it just contains regular data.

[colden]

In D41825#970033, @zturner wrote:

So each interval has exactly 4096 blocks. Block 0 is only special in the first interval. It's still there in every other interval, it just contains regular data.

But according to the code, that can't be true. Specifically, I'm looking at llvm::msf::getFpmStreamLayout. If you look at the loop assuming that FpmBlock is 1, then it pushes index 1 as the first FPM block, adds the result of msf::getFpmIntervalLength (which always returns 4096), and pushes that. This means that the second FPM in the sequence is at index 4097, which would mean that there are 4097 blocks in front of it. Unless block at index 4096 is unused, the first interval is in fact 1 block longer.

[zturner]

In D41825#970040, @colden wrote:

In D41825#970033, @zturner wrote:

So each interval has exactly 4096 blocks. Block 0 is only special in the first interval. It's still there in every other interval, it just contains regular data.

But according to the code, that can't be true. Specifically, I'm looking at llvm::msf::getFpmStreamLayout. If you look at the loop assuming that FpmBlock is 1, then it pushes index 1 as the first FPM block, adds the result of msf::getFpmIntervalLength (which always returns 4096), and pushes that. This means that the second FPM in the sequence is at index 4097, which would mean that there are 4097 blocks in front of it. Unless block at index 4096 is unused, the first interval is in fact 1 block longer.

Doesn't all of that match up exactly with the layout I posted? Paste a copy of that layout diagram in my previous comment onto the end of itself. 4096 becomes "Data", 4097 becomes "FPM1", 4098 becomes "FPM2". "Interval" is the distance between two consecutive blocks of the same FPM. It's always 4096. So FPM1 is on blocks 1, 4096 + 1, 4096*2 + 1, 4096*3 + 1, etc. The blocks immediately before that (0, 4096, 4096*2, 4096*3, etc) are just data, with the only exception being block 0, which is the super block.

[colden]

In D41825#970042, @zturner wrote:

In D41825#970040, @colden wrote:

In D41825#970033, @zturner wrote:

So each interval has exactly 4096 blocks. Block 0 is only special in the first interval. It's still there in every other interval, it just contains regular data.

But according to the code, that can't be true. Specifically, I'm looking at llvm::msf::getFpmStreamLayout. If you look at the loop assuming that FpmBlock is 1, then it pushes index 1 as the first FPM block, adds the result of msf::getFpmIntervalLength (which always returns 4096), and pushes that. This means that the second FPM in the sequence is at index 4097, which would mean that there are 4097 blocks in front of it. Unless block at index 4096 is unused, the first interval is in fact 1 block longer.

Doesn't all of that match up exactly with the layout I posted? Paste a copy of that layout diagram in my previous comment onto the end of itself. 4096 becomes "Data", 4097 becomes "FPM1", 4098 becomes "FPM2". "Interval" is the distance between two consecutive blocks of the same FPM. It's always 4096. So FPM1 is on blocks 1, 4096 + 1, 4096*2 + 1, 4096*3 + 1, etc. The blocks immediately before that (0, 4096, 4096*2, 4096*3, etc) are just data, with the only exception being block 0, which is the super block.

OOOOOH it just clicked. I thought the FPMs were always the first blocks in the interval, but having a block of data first makes so much sense.

Sorry for being so thick, and thanks for breaking it down for me. I'll post an update here in a minute.

[colden]

Now that I actually understand how the intervals work, I reworked a lot of what I had written. I think it's much clearer now, but I'm sure there's more nits to be had :)

[colden]

Updated with my newer, better understanding of the file layout

[zturner]

llvm/docs/PDB/MsfFile.rst

97 ↗

(On Diff #128962)

This is backwards (yes it's confusing). Since it's the free block map, a value of 1 indicates that the block is free, and a value of 0 indicates that the value is not free.

107–110 ↗

(On Diff #128962)

This is also not quite true. The k'th bit in the j'th FPM block refers to the 4096*j + k'th block in the file. So, for example, consider blocks 1 and 4097. These are the first and second blocks of FPM1, respectively. To find out the allocation status of block 4097, you look at bit 1 of byte 512 (512*8 + 1 = 4097).

There's actually a comment in the MSF reference implementation that indicates this was probably a design oversight, because this results in far more FPM blocks being reserved in a file than are actually necessary (by a factor of 8). But since it's already that way and everything is relying on it, and files are out there in the wild using it, and it results in neglible file bloat, it just stays that way.

This is actually the whole point of the IncludeUnusedFpmData flag from my previous patch. If you specify true for it, it will give you a stream consisting of every block that *could* be an FPM block (i.e. the index is of the form 4096*k + 1), but if you pass false it truncates the extraneous ones at the end that would otherwise refer to blocks that are not even in the file.

[colden]

llvm/docs/PDB/MsfFile.rst

97 ↗

(On Diff #128962)

Aaah so close.

107–110 ↗

(On Diff #128962)

Oh fascinating. I was wondering about that / 8. I'll see if I can figure out a good way to phrase this.

[colden]

nth time's the charm!

[zturner]

looks good, thanks!

[colden]

Yay, thanks!

If you wouldn't mind committing this for me, I'd really appreciate it.

[colden]

Ping, could someone please submit this for me?

[colden]

Thank you Zach!

docs/PDB/MsfFile.rst

 =====================================
 The MSF File Format
 =====================================
 
 .. contents::
    :local:
 
+.. _msf_layout:
+
+File Layout
+===========
+
+The MSF file format consists of the following components:
+
+1. :ref:`msf_superblock`
+2. :ref:`msf_freeblockmap`
+3. Data
+
+Each component is stored as an indexed block, the length of which is specified
+in ``SuperBlock::BlockSize``. After index 0 (:ref:`msf_superblock`), the file
+repeats the following pattern of blocks:
+
+1. Free Block Map 1 (corresponds to ``SuperBlock::FreeBlockMapBlock`` 1)
+2. Free Block Map 2 (corresponds to ``SuperBlock::FreeBlockMapBlock`` 2)
+3. ``SuperBlock::BlockSize - 2`` blocks of data
+
+The file may end after any block, including immediately after a
+Free Block Map 1.
+
+The following diagram demonstrates the general layout of the file:
+
++-------------+-----------------------+------------------+------------------+----------+------+------+-------------+-----+
+| Block Index | 0                     | 1                | 2                | 3 - 4096 | 4097 | 4098 | 4099 - 8192 | ... |
++=============+=======================+==================+==================+==========+======+======+=============+=====+
+| Meaning     | :ref:`msf_superblock` | Free Block Map 1 | Free Block Map 2 | Data     | FBM1 | FBM2 | Data        | ... |
++-------------+-----------------------+------------------+------------------+----------+------+------+-------------+-----+
+
+Each group of FPM1, FPM2, and the following data blocks are sometimes referred
+to as an "interval."
+
+.. note::
+  LLVM only supports 4096 byte blocks (sometimes referred to as the "BigMsf"
+  variant), so the rest of this document will assume a block size of 4096.
+
 .. _msf_superblock:
 
 The Superblock
 ==============
 At file offset 0 in an MSF file is the MSF *SuperBlock*, which is laid out as
 follows:
 
 .. code-block:: c++

 - **FileMagic** - Must be equal to ``"Microsoft C / C++ MSF 7.00\\r\\n"``
   followed by the bytes ``1A 44 53 00 00 00``.
 - **BlockSize** - The block size of the internal file system.  Valid values are
   512, 1024, 2048, and 4096 bytes.  Certain aspects of the MSF file layout vary
   depending on the block sizes.  For the purposes of LLVM, we handle only block
   sizes of 4KiB, and all further discussion assumes a block size of 4KiB.
 - **FreeBlockMapBlock** - The index of a block within the file, at which begins
   a bitfield representing the set of all blocks within the file which are "free"
-  (i.e. the data within that block is not used).  This bitfield is spread across
-  the MSF file at ``BlockSize`` intervals.
+  (i.e. the data within that block is not used).  See :ref:`msf_freeblockmap` for
+  more information.
   **Important**: ``FreeBlockMapBlock`` can only be ``1`` or ``2``!  This field
   is designed to support incremental and atomic updates of the underlying MSF
   file.  While writing to an MSF file, if the value of this field is `1`, you
   can write your new modified bitfield to page 2, and vice versa.  Only when
   you commit the file to disk do you need to swap the value in the SuperBlock
   to point to the new ``FreeBlockMapBlock``.
 - **NumBlocks** - The total number of blocks in the file.  ``NumBlocks * BlockSize``
   should equal the size of the file on disk.
 - **NumDirectoryBytes** - The size of the stream directory, in bytes.  The stream
   directory contains information about each stream's size and the set of blocks
   that it occupies.  It will be described in more detail later.
 - **BlockMapAddr** - The index of a block within the MSF file.  At this block is
   an array of ``ulittle32_t``'s listing the blocks that the stream directory
   resides on.  For large MSF files, the stream directory (which describes the
   block layout of each stream) may not fit entirely on a single block.  As a
   result, this extra layer of indirection is introduced, whereby this block
   contains the list of blocks that the stream directory occupies, and the stream
   directory itself can be stitched together accordingly.  The number of
   ``ulittle32_t``'s in this array is given by ``ceil(NumDirectoryBytes / BlockSize)``.
   
+.. _msf_freeblockmap:
+
+The Free Block Map
+==================
+
+The Free Block Map (sometimes referred to as the Free Page Map, or FPM) is a
+block which contains a byte flag for every block in the interval it desribes.
+The flag will be set to 1 if the block is in use, and 0 if the block is in use.
+Because each interval includes the FPMs associated with it, the first two bytes
+of each FPM refer to FPM1 and FPM2, and are by definition 1 (the FPMs can't be
+unused). The only exception to this rule is the first interval, where byte 0
+refers to the Superblock, bype 1 refers to FPM1, byte 2 refers to FPM2, and
+byte 3 refers to the first data block.
+
 The Stream Directory
 ====================
 The Stream Directory is the root of all access to the other streams in an MSF
 file.  Beginning at byte 0 of the stream directory is the following structure:
 
 .. code-block:: c++
 
   struct StreamDirectory {