LCOV - code coverage report
Current view: top level - lib/DebugInfo/PDB/Native - PDBStringTableBuilder.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 47 57 82.5 %
Date: 2018-07-13 00:08:38 Functions: 12 17 70.6 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- PDBStringTableBuilder.cpp - PDB String Table -------------*- C++ -*-===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : 
      10             : #include "llvm/DebugInfo/PDB/Native/PDBStringTableBuilder.h"
      11             : 
      12             : #include "llvm/ADT/ArrayRef.h"
      13             : #include "llvm/DebugInfo/PDB/Native/Hash.h"
      14             : #include "llvm/DebugInfo/PDB/Native/RawTypes.h"
      15             : #include "llvm/Support/BinaryStreamWriter.h"
      16             : #include "llvm/Support/Endian.h"
      17             : 
      18             : #include <map>
      19             : 
      20             : using namespace llvm;
      21             : using namespace llvm::msf;
      22             : using namespace llvm::support;
      23             : using namespace llvm::support::endian;
      24             : using namespace llvm::pdb;
      25             : 
      26          90 : StringTableHashTraits::StringTableHashTraits(PDBStringTableBuilder &Table)
      27          90 :     : Table(&Table) {}
      28             : 
      29           0 : uint32_t StringTableHashTraits::hashLookupKey(StringRef S) const {
      30           0 :   return Table->getIdForString(S);
      31             : }
      32             : 
      33           0 : StringRef StringTableHashTraits::storageKeyToLookupKey(uint32_t Offset) const {
      34           0 :   return Table->getStringForId(Offset);
      35             : }
      36             : 
      37           0 : uint32_t StringTableHashTraits::lookupKeyToStorageKey(StringRef S) {
      38           0 :   return Table->insert(S);
      39             : }
      40             : 
      41          81 : uint32_t PDBStringTableBuilder::insert(StringRef S) {
      42          81 :   return Strings.insert(S);
      43             : }
      44             : 
      45           0 : uint32_t PDBStringTableBuilder::getIdForString(StringRef S) const {
      46           0 :   return Strings.getIdForString(S);
      47             : }
      48             : 
      49           0 : StringRef PDBStringTableBuilder::getStringForId(uint32_t Id) const {
      50           0 :   return Strings.getStringForId(Id);
      51             : }
      52             : 
      53             : // This is a precomputed list of Buckets given the specified number of
      54             : // strings.  Matching the reference algorithm exactly is not strictly
      55             : // necessary for correctness, but it helps when comparing LLD's PDBs with
      56             : // Microsoft's PDBs so as to eliminate superfluous differences.
      57       99743 : static std::map<uint32_t, uint32_t> StringsToBuckets = {
      58             :     {1, 2},
      59             :     {2, 4},
      60             :     {4, 7},
      61             :     {6, 11},
      62             :     {9, 17},
      63             :     {13, 26},
      64             :     {20, 40},
      65             :     {31, 61},
      66             :     {46, 92},
      67             :     {70, 139},
      68             :     {105, 209},
      69             :     {157, 314},
      70             :     {236, 472},
      71             :     {355, 709},
      72             :     {532, 1064},
      73             :     {799, 1597},
      74             :     {1198, 2396},
      75             :     {1798, 3595},
      76             :     {2697, 5393},
      77             :     {4045, 8090},
      78             :     {6068, 12136},
      79             :     {9103, 18205},
      80             :     {13654, 27308},
      81             :     {20482, 40963},
      82             :     {30723, 61445},
      83             :     {46084, 92168},
      84             :     {69127, 138253},
      85             :     {103690, 207380},
      86             :     {155536, 311071},
      87             :     {233304, 466607},
      88             :     {349956, 699911},
      89             :     {524934, 1049867},
      90             :     {787401, 1574801},
      91             :     {1181101, 2362202},
      92             :     {1771652, 3543304},
      93             :     {2657479, 5314957},
      94             :     {3986218, 7972436},
      95             :     {5979328, 11958655},
      96             :     {8968992, 17937983},
      97             :     {13453488, 26906975},
      98             :     {20180232, 40360463},
      99             :     {30270348, 60540695},
     100             :     {45405522, 90811043},
     101             :     {68108283, 136216565},
     102             :     {102162424, 204324848},
     103             :     {153243637, 306487273},
     104             :     {229865455, 459730910},
     105             :     {344798183, 689596366},
     106             :     {517197275, 1034394550},
     107             :     {775795913, 1551591826}};
     108             : 
     109             : static uint32_t computeBucketCount(uint32_t NumStrings) {
     110             :   auto Entry = StringsToBuckets.lower_bound(NumStrings);
     111             :   assert(Entry != StringsToBuckets.end());
     112         621 :   return Entry->second;
     113             : }
     114             : 
     115         443 : uint32_t PDBStringTableBuilder::calculateHashTableSize() const {
     116             :   uint32_t Size = sizeof(uint32_t); // Hash table begins with 4-byte size field.
     117         886 :   Size += sizeof(uint32_t) * computeBucketCount(Strings.size());
     118             : 
     119         443 :   return Size;
     120             : }
     121             : 
     122         265 : uint32_t PDBStringTableBuilder::calculateSerializedSize() const {
     123             :   uint32_t Size = 0;
     124             :   Size += sizeof(PDBStringTableHeader);
     125         265 :   Size += Strings.calculateSerializedSize();
     126         265 :   Size += calculateHashTableSize();
     127         265 :   Size += sizeof(uint32_t); // The /names stream ends with the string count.
     128         265 :   return Size;
     129             : }
     130             : 
     131          87 : void PDBStringTableBuilder::setStrings(
     132             :     const codeview::DebugStringTableSubsection &Strings) {
     133          87 :   this->Strings = Strings;
     134          87 : }
     135             : 
     136         178 : Error PDBStringTableBuilder::writeHeader(BinaryStreamWriter &Writer) const {
     137             :   // Write a header
     138             :   PDBStringTableHeader H;
     139             :   H.Signature = PDBStringTableSignature;
     140             :   H.HashVersion = 1;
     141         178 :   H.ByteSize = Strings.calculateSerializedSize();
     142         178 :   if (auto EC = Writer.writeObject(H))
     143             :     return EC;
     144             :   assert(Writer.bytesRemaining() == 0);
     145             :   return Error::success();
     146             : }
     147             : 
     148         178 : Error PDBStringTableBuilder::writeStrings(BinaryStreamWriter &Writer) const {
     149         356 :   if (auto EC = Strings.commit(Writer))
     150             :     return EC;
     151             : 
     152             :   assert(Writer.bytesRemaining() == 0);
     153             :   return Error::success();
     154             : }
     155             : 
     156         178 : Error PDBStringTableBuilder::writeHashTable(BinaryStreamWriter &Writer) const {
     157             :   // Write a hash table.
     158         178 :   uint32_t BucketCount = computeBucketCount(Strings.size());
     159         356 :   if (auto EC = Writer.writeInteger(BucketCount))
     160             :     return EC;
     161         178 :   std::vector<ulittle32_t> Buckets(BucketCount);
     162             : 
     163         381 :   for (auto &Pair : Strings) {
     164         203 :     StringRef S = Pair.getKey();
     165         203 :     uint32_t Offset = Pair.getValue();
     166         203 :     uint32_t Hash = hashStringV1(S);
     167             : 
     168         237 :     for (uint32_t I = 0; I != BucketCount; ++I) {
     169         220 :       uint32_t Slot = (Hash + I) % BucketCount;
     170         440 :       if (Buckets[Slot] != 0)
     171             :         continue;
     172             :       Buckets[Slot] = Offset;
     173             :       break;
     174             :     }
     175             :   }
     176             : 
     177         356 :   if (auto EC = Writer.writeArray(ArrayRef<ulittle32_t>(Buckets)))
     178             :     return EC;
     179             : 
     180             :   assert(Writer.bytesRemaining() == 0);
     181             :   return Error::success();
     182             : }
     183             : 
     184         178 : Error PDBStringTableBuilder::writeEpilogue(BinaryStreamWriter &Writer) const {
     185         356 :   if (auto EC = Writer.writeInteger<uint32_t>(Strings.size()))
     186             :     return EC;
     187             :   assert(Writer.bytesRemaining() == 0);
     188             :   return Error::success();
     189             : }
     190             : 
     191         178 : Error PDBStringTableBuilder::commit(BinaryStreamWriter &Writer) const {
     192             :   BinaryStreamWriter SectionWriter;
     193             : 
     194         356 :   std::tie(SectionWriter, Writer) = Writer.split(sizeof(PDBStringTableHeader));
     195         356 :   if (auto EC = writeHeader(SectionWriter))
     196             :     return EC;
     197             : 
     198         178 :   std::tie(SectionWriter, Writer) =
     199         356 :       Writer.split(Strings.calculateSerializedSize());
     200         356 :   if (auto EC = writeStrings(SectionWriter))
     201             :     return EC;
     202             : 
     203         356 :   std::tie(SectionWriter, Writer) = Writer.split(calculateHashTableSize());
     204         356 :   if (auto EC = writeHashTable(SectionWriter))
     205             :     return EC;
     206             : 
     207         356 :   std::tie(SectionWriter, Writer) = Writer.split(sizeof(uint32_t));
     208         356 :   if (auto EC = writeEpilogue(SectionWriter))
     209             :     return EC;
     210             : 
     211             :   return Error::success();
     212      299229 : }

Generated by: LCOV version 1.13