Doc bug, incorrect description of PDB Serialized Hash Table Format

[TimMisiak]

The documentation page for the PDB Serialized Hash Table Format (https://github.com/llvm/llvm-project/blob/main/llvm/docs/PDB/HashTable.rst) indicates that the number of key/value pairs is "capacity" but based on my reading of the microsoft-pdb repo (and looking through some PDB files modified by pdbstr.exe), it's actually "size" that determines the length. Or more accurately, in the microsoft-pdb implementation it's actually determined by the number of bits set in the "present" bit map. Which I believe should match in a well-behaved PDB.

Reference source here: https://github.com/microsoft/microsoft-pdb/blob/805655a28bd8198004be2ac27e6e0290121a5e89/PDB/include/map.h#L584

Commit in a fork showing a potential revision to the docs: TimMisiak@9bd9756

[llvmbot]

@llvm/issue-subscribers-debuginfo

Author: Tim Misiak (TimMisiak)

The documentation page for the PDB Serialized Hash Table Format (https://github.com/llvm/llvm-project/blob/main/llvm/docs/PDB/HashTable.rst) indicates that the number of key/value pairs is "capacity" but based on my reading of the microsoft-pdb repo (and looking through some PDB files modified by pdbstr.exe), it's actually "size" that determines the length. Or more accurately, in the microsoft-pdb implementation it's actually determined by the number of bits set in the "present" bit map. Which I believe should match in a well-behaved PDB.

Reference source here: https://github.com/microsoft/microsoft-pdb/blob/805655a28bd8198004be2ac27e6e0290121a5e89/PDB/include/map.h#L584

Commit in a fork showing a potential revision to the docs: TimMisiak@9bd9756

[nlguillemot]

Ran into this issue as well. Would appreciate an update to the docs.

[nlguillemot]

It seems to me that the real problem is that the documentation has swapped the meaning of size and capacity.

The LLVM docs say 1. "size", 2. "capacity". However, the reference Microsoft code uses capacity then size.

If I look at the microsoft implementation, I see this code:

// append a serialization of this map to the buffer
// format:
//  cdr
//  rgd.size()
//  isetPresent
//  isetDeleted
//  group of (D,R) pairs which were present, a total of cdr of 'em
//
template <class D, class R, class H, class C, class CS>
BOOL Map<D,R,H,C,CS>::save(Buffer* pbuf) {
    precondition(fullInvariants());
    
    MTS_PROTECT_T(CS, cs);

    unsigned size = rgd.size();
    if (!(pbuf->Append((PB)&cdr, sizeof(cdr)) &&
          pbuf->Append((PB)&size, sizeof(size)) &&
          isetPresent.save(pbuf) &&
          isetDeleted.save(pbuf)))
    {

The data being pushed to the buffer is:

1. The cdr ("count of domain-range pairs"?)
2. The size of the rgd ("range of domain"?)

as the comment says, the number of pairs is cdr.

[nlguillemot]

Hmm nah I take it back, sorry. It's size and capacity. What's happening is just that serialization only saves the keys that are actually present, not the capacity in the data structure at the time of the save.

[nlguillemot]

If the hash table's structure is really being compressed like this during serialization, then this idea in the documentation is wrong:

hash tables are serialized and embedded directly to the file, rather than requiring a consumer to read a list of values and reconstruct the hash table on the fly.

You in fact do need to read a list of values and reconstruct the hash table, don't you?