1//===- NaClBitstreamReader.cpp --------------------------------------------===//
2//     NaClBitstreamReader implementation
3//
4//                     The LLVM Compiler Infrastructure
5//
6// This file is distributed under the University of Illinois Open Source
7// License. See LICENSE.TXT for details.
8//
9//===----------------------------------------------------------------------===//
10
11#include "llvm/ADT/STLExtras.h"
12#include "llvm/Bitcode/NaCl/NaClBitstreamReader.h"
13#include "llvm/Support/Format.h"
14#include "llvm/Support/raw_ostream.h"
15
16using namespace llvm;
17
18namespace {
19
20static const char *ErrorLevelName[] = {
21  "Warning",
22  "Error",
23  "Fatal"
24};
25
26} // End of anonymous namespace.
27
28std::string llvm::naclbitc::getBitAddress(uint64_t Bit) {
29  std::string Buffer;
30  raw_string_ostream Stream(Buffer);
31  Stream << (Bit / 8) << ":" << (Bit % 8);
32  return Stream.str();
33}
34
35raw_ostream &llvm::naclbitc::ErrorAt(
36    raw_ostream &Out, ErrorLevel Level, uint64_t BitPosition) {
37  assert(Level < array_lengthof(::ErrorLevelName));
38  return Out << ErrorLevelName[Level] << "("
39             << naclbitc::getBitAddress(BitPosition) << "): ";
40}
41
42//===----------------------------------------------------------------------===//
43//  NaClBitstreamCursor implementation
44//===----------------------------------------------------------------------===//
45
46void NaClBitstreamCursor::ErrorHandler::
47Fatal(const std::string &ErrorMessage) const {
48  // Default implementation is simply print message, and the bit where
49  // the error occurred.
50  std::string Buffer;
51  raw_string_ostream StrBuf(Buffer);
52  naclbitc::ErrorAt(StrBuf, naclbitc::Fatal,
53                    Cursor.getErrorBitNo(getCurrentBitNo())) << ErrorMessage;
54  report_fatal_error(StrBuf.str());
55}
56
57void NaClBitstreamCursor::reportInvalidAbbrevNumber(unsigned AbbrevNo) const {
58  std::string Buffer;
59  raw_string_ostream StrBuf(Buffer);
60  StrBuf << "Invalid abbreviation # " << AbbrevNo << " defined for record";
61  ErrHandler->Fatal(StrBuf.str());
62}
63
64void NaClBitstreamCursor::reportInvalidJumpToBit(uint64_t BitNo) const {
65  std::string Buffer;
66  raw_string_ostream StrBuf(Buffer);
67  StrBuf << "Invalid jump to bit " << BitNo;
68  ErrHandler->Fatal(StrBuf.str());
69}
70
71/// EnterSubBlock - Having read the ENTER_SUBBLOCK abbrevid, enter
72/// the block, and return true if the block has an error.
73bool NaClBitstreamCursor::EnterSubBlock(unsigned BlockID, unsigned *NumWordsP) {
74  const bool IsFixed = true;
75  NaClBitcodeSelectorAbbrev
76      CodeAbbrev(IsFixed, ReadVBR(naclbitc::CodeLenWidth));
77  BlockScope.push_back(Block(BitStream->getBlockInfo(BlockID), CodeAbbrev));
78  SkipToFourByteBoundary();
79  unsigned NumWords = Read(naclbitc::BlockSizeWidth);
80  if (NumWordsP) *NumWordsP = NumWords;
81
82  // Validate that this block is sane.
83  if (BlockScope.back().getCodeAbbrev().NumBits == 0 || AtEndOfStream())
84    return true;
85
86  return false;
87}
88
89void NaClBitstreamCursor::skipAbbreviatedField(const NaClBitCodeAbbrevOp &Op) {
90  // Decode the value as we are commanded.
91  switch (Op.getEncoding()) {
92  case NaClBitCodeAbbrevOp::Literal:
93    // No read necessary for literal.
94    break;
95  case NaClBitCodeAbbrevOp::Fixed:
96    (void)Read((unsigned)Op.getValue());
97    break;
98  case NaClBitCodeAbbrevOp::VBR:
99    (void)ReadVBR64((unsigned)Op.getValue());
100    break;
101  case NaClBitCodeAbbrevOp::Array:
102    // This can't happen because the abbreviation must be valid.
103    llvm_unreachable("Bad array abbreviation encoding!");
104    break;
105  case NaClBitCodeAbbrevOp::Char6:
106    (void)Read(6);
107    break;
108  }
109}
110
111/// skipRecord - Read the current record and discard it.
112void NaClBitstreamCursor::skipRecord(unsigned AbbrevID) {
113  // Skip unabbreviated records by reading past their entries.
114  if (AbbrevID == naclbitc::UNABBREV_RECORD) {
115    unsigned Code = ReadVBR(6);
116    (void)Code;
117    unsigned NumElts = ReadVBR(6);
118    for (unsigned i = 0; i != NumElts; ++i)
119      (void)ReadVBR64(6);
120    SkipToByteBoundaryIfAligned();
121    return;
122  }
123
124  const NaClBitCodeAbbrev *Abbv = getAbbrev(AbbrevID);
125
126  for (unsigned i = 0, e = Abbv->getNumOperandInfos(); i != e; ++i) {
127    const NaClBitCodeAbbrevOp &Op = Abbv->getOperandInfo(i);
128    switch (Op.getEncoding()) {
129    default:
130      skipAbbreviatedField(Op);
131      break;
132    case NaClBitCodeAbbrevOp::Literal:
133      break;
134    case NaClBitCodeAbbrevOp::Array: {
135      // Array case.  Read the number of elements as a vbr6.
136      unsigned NumElts = ReadVBR(6);
137
138      // Get the element encoding.
139      const NaClBitCodeAbbrevOp &EltEnc = Abbv->getOperandInfo(++i);
140
141      // Read all the elements.
142      for (; NumElts; --NumElts)
143        skipAbbreviatedField(EltEnc);
144      break;
145    }
146    }
147  }
148  SkipToByteBoundaryIfAligned();
149}
150
151bool NaClBitstreamCursor::readRecordAbbrevField(
152    const NaClBitCodeAbbrevOp &Op, uint64_t &Value) {
153  switch (Op.getEncoding()) {
154  case NaClBitCodeAbbrevOp::Literal:
155    Value = Op.getValue();
156    break;
157  case NaClBitCodeAbbrevOp::Array:
158    // Returns number of elements in the array.
159    Value = ReadVBR(6);
160    return true;
161  case NaClBitCodeAbbrevOp::Fixed:
162    Value = Read((unsigned)Op.getValue());
163    break;
164  case NaClBitCodeAbbrevOp::VBR:
165    Value = ReadVBR64((unsigned)Op.getValue());
166    break;
167  case NaClBitCodeAbbrevOp::Char6:
168    Value = NaClBitCodeAbbrevOp::DecodeChar6(Read(6));
169    break;
170  }
171  return false;
172}
173
174uint64_t NaClBitstreamCursor::readArrayAbbreviatedField(
175    const NaClBitCodeAbbrevOp &Op) {
176  // Decode the value as we are commanded.
177  switch (Op.getEncoding()) {
178  case NaClBitCodeAbbrevOp::Literal:
179    return Op.getValue();
180  case NaClBitCodeAbbrevOp::Fixed:
181    return Read((unsigned)Op.getValue());
182  case NaClBitCodeAbbrevOp::VBR:
183    return ReadVBR64((unsigned)Op.getValue());
184  case NaClBitCodeAbbrevOp::Array:
185    // This can't happen because the abbreviation must be valid.
186    llvm_unreachable("Bad array abbreviation encoding!");
187    break;
188  case NaClBitCodeAbbrevOp::Char6:
189    return NaClBitCodeAbbrevOp::DecodeChar6(Read(6));
190  }
191  llvm_unreachable("Illegal abbreviation encoding for field!");
192}
193
194void NaClBitstreamCursor::readArrayAbbrev(
195    const NaClBitCodeAbbrevOp &Op, unsigned NumArrayElements,
196    SmallVectorImpl<uint64_t> &Vals) {
197  for (; NumArrayElements; --NumArrayElements) {
198    Vals.push_back(readArrayAbbreviatedField(Op));
199  }
200}
201
202unsigned NaClBitstreamCursor::readRecord(unsigned AbbrevID,
203                                         SmallVectorImpl<uint64_t> &Vals) {
204  if (AbbrevID == naclbitc::UNABBREV_RECORD) {
205    unsigned Code = ReadVBR(6);
206    unsigned NumElts = ReadVBR(6);
207    for (unsigned i = 0; i != NumElts; ++i)
208      Vals.push_back(ReadVBR64(6));
209    SkipToByteBoundaryIfAligned();
210    return Code;
211  }
212
213  // Read code.
214  const NaClBitCodeAbbrev *Abbv = getAbbrev(AbbrevID);
215  uint64_t Value;
216  unsigned Code;
217  if (readRecordAbbrevField(Abbv->getOperandInfo(0), Value)) {
218    // Array found, use to read all elements.
219    if (Value == 0)
220      ErrHandler->Fatal("No code found for record!");
221    const NaClBitCodeAbbrevOp &Op = Abbv->getOperandInfo(1);
222    Code = readArrayAbbreviatedField(Op);
223    readArrayAbbrev(Op, Value - 1, Vals);
224    SkipToByteBoundaryIfAligned();
225    return Code;
226  }
227  Code = Value;
228
229  // Read arguments.
230  unsigned NumOperands = Abbv->getNumOperandInfos();
231  for (unsigned i = 1; i != NumOperands; ++i) {
232    if (readRecordAbbrevField(Abbv->getOperandInfo(i), Value)) {
233      ++i;
234      readArrayAbbrev(Abbv->getOperandInfo(i), Value, Vals);
235      SkipToByteBoundaryIfAligned();
236      return Code;
237    }
238    Vals.push_back(Value);
239  }
240  SkipToByteBoundaryIfAligned();
241  return Code;
242}
243
244
245NaClBitCodeAbbrevOp::Encoding NaClBitstreamCursor::
246getEncoding(uint64_t Value) {
247  if (!NaClBitCodeAbbrevOp::isValidEncoding(Value)) {
248    std::string Buffer;
249    raw_string_ostream StrBuf(Buffer);
250    StrBuf << "Invalid abbreviation encoding specified in bitcode file: "
251           << Value;
252    ErrHandler->Fatal(StrBuf.str());
253  }
254  return NaClBitCodeAbbrevOp::Encoding(Value);
255}
256
257void NaClBitstreamCursor::ReadAbbrevRecord(bool IsLocal,
258                                           NaClAbbrevListener *Listener) {
259  NaClBitCodeAbbrev *Abbv = BlockScope.back().appendLocalCreate();
260  unsigned NumOpInfo = ReadVBR(5);
261  if (Listener) Listener->Values.push_back(NumOpInfo);
262  for (unsigned i = 0; i != NumOpInfo; ++i) {
263    bool IsLiteral = Read(1) ? true : false;
264    if (Listener) Listener->Values.push_back(IsLiteral);
265    if (IsLiteral) {
266      uint64_t Value = ReadVBR64(8);
267      if (Listener) Listener->Values.push_back(Value);
268      Abbv->Add(NaClBitCodeAbbrevOp(Value));
269      continue;
270    }
271    NaClBitCodeAbbrevOp::Encoding E = getEncoding(Read(3));
272    if (Listener) Listener->Values.push_back(E);
273    if (NaClBitCodeAbbrevOp::hasValue(E)) {
274      unsigned Data = ReadVBR64(5);
275      if (Listener) Listener->Values.push_back(Data);
276
277      // As a special case, handle fixed(0) (i.e., a fixed field with zero bits)
278      // and vbr(0) as a literal zero.  This is decoded the same way, and avoids
279      // a slow path in Read() to have to handle reading zero bits.
280      if ((E == NaClBitCodeAbbrevOp::Fixed || E == NaClBitCodeAbbrevOp::VBR) &&
281          Data == 0) {
282        if (Listener) Listener->Values.push_back(0);
283        Abbv->Add(NaClBitCodeAbbrevOp(0));
284        continue;
285      }
286      if (!NaClBitCodeAbbrevOp::isValid(E, Data)) {
287        std::string Buffer;
288        raw_string_ostream StrBuf(Buffer);
289        StrBuf << "Invalid abbreviation encoding ("
290               << NaClBitCodeAbbrevOp::getEncodingName(E)
291               << ", " << Data << ")";
292        ErrHandler->Fatal(StrBuf.str());
293      }
294      Abbv->Add(NaClBitCodeAbbrevOp(E, Data));
295    } else {
296      if (!NaClBitCodeAbbrevOp::isValid(E)) {
297        std::string Buffer;
298        raw_string_ostream StrBuf(Buffer);
299        StrBuf << "Invalid abbreviation encoding ("
300               << NaClBitCodeAbbrevOp::getEncodingName(E) << ")";
301        ErrHandler->Fatal(StrBuf.str());
302      }
303      Abbv->Add(NaClBitCodeAbbrevOp(E));
304    }
305  }
306  SkipToByteBoundaryIfAligned();
307  if (!Abbv->isValid())
308    ErrHandler->Fatal("Invalid abbreviation specified in bitcode file");
309  if (Listener) {
310    Listener->ProcessAbbreviation(Abbv, IsLocal);
311    // Reset record information of the listener.
312    Listener->Values.clear();
313    Listener->StartBit = GetCurrentBitNo();
314  }
315}
316
317void NaClBitstreamCursor::SkipAbbrevRecord() {
318  unsigned NumOpInfo = ReadVBR(5);
319  for (unsigned i = 0; i != NumOpInfo; ++i) {
320    bool IsLiteral = Read(1) ? true : false;
321    if (IsLiteral) {
322      ReadVBR64(8);
323      continue;
324    }
325    NaClBitCodeAbbrevOp::Encoding E = getEncoding(Read(3));
326    if (NaClBitCodeAbbrevOp::hasValue(E)) {
327      ReadVBR64(5);
328    }
329  }
330  SkipToByteBoundaryIfAligned();
331}
332
333namespace {
334
335unsigned ValidBlockIDs[] = {
336  naclbitc::BLOCKINFO_BLOCK_ID,
337  naclbitc::CONSTANTS_BLOCK_ID,
338  naclbitc::FUNCTION_BLOCK_ID,
339  naclbitc::GLOBALVAR_BLOCK_ID,
340  naclbitc::MODULE_BLOCK_ID,
341  naclbitc::TOP_LEVEL_BLOCKID,
342  naclbitc::TYPE_BLOCK_ID_NEW,
343  naclbitc::VALUE_SYMTAB_BLOCK_ID
344};
345
346} // end of anonymous namespace
347
348NaClBitstreamReader::BlockInfoRecordsMap::
349BlockInfoRecordsMap() : IsFrozen(false) {
350  for (size_t BlockID : ValidBlockIDs) {
351    std::unique_ptr<BlockInfo> Info(new BlockInfo(BlockID));
352    KnownInfos.emplace(BlockID, std::move(Info));
353  }
354}
355
356NaClBitstreamReader::BlockInfo * NaClBitstreamReader::BlockInfoRecordsMap::
357getOrCreateUnknownBlockInfo(unsigned BlockID) {
358  std::unique_lock<std::mutex> Lock(UnknownBlockInfoLock);
359  while (true) {
360    auto Pos = UnknownInfos.find(BlockID);
361    if (Pos != UnknownInfos.end())
362      return Pos->second.get();
363    // Install, then let next iteration find.
364    std::unique_ptr<BlockInfo> Info(new BlockInfo(BlockID));
365    UnknownInfos.emplace(BlockID, std::move(Info));
366  }
367}
368
369NaClBitstreamReader::BlockInfoRecordsMap::UpdateLock::
370UpdateLock(BlockInfoRecordsMap &BlockInfoRecords)
371    : BlockInfoRecords(BlockInfoRecords),
372      Lock(BlockInfoRecords.UpdateRecordsLock) {}
373
374NaClBitstreamReader::BlockInfoRecordsMap::UpdateLock::
375~UpdateLock() {
376  if (BlockInfoRecords.freeze())
377    report_fatal_error("Global abbreviations block frozen while building.");
378}
379
380bool NaClBitstreamCursor::ReadBlockInfoBlock(NaClAbbrevListener *Listener) {
381  // If this is the second read of the block info block, skip it.
382  if (BitStream->BlockInfoRecords->isFrozen())
383    return SkipBlock();
384
385  NaClBitstreamReader::BlockInfoRecordsMap::UpdateLock
386      Lock(*BitStream->BlockInfoRecords);
387  unsigned NumWords;
388  if (EnterSubBlock(naclbitc::BLOCKINFO_BLOCK_ID, &NumWords)) return true;
389
390  if (Listener) Listener->BeginBlockInfoBlock(NumWords);
391
392  NaClBitcodeRecordVector Record;
393  Block &CurBlock = BlockScope.back();
394  NaClBitstreamReader::AbbrevList *UpdateAbbrevs =
395      &CurBlock.GlobalAbbrevs->getAbbrevs();
396  bool FoundSetBID = false;
397
398  // Read records of the BlockInfo block.
399  while (1) {
400    if (Listener) Listener->StartBit = GetCurrentBitNo();
401    NaClBitstreamEntry Entry = advance(AF_DontAutoprocessAbbrevs, Listener);
402
403    switch (Entry.Kind) {
404    case llvm::NaClBitstreamEntry::SubBlock:  // PNaCl doesn't allow!
405    case llvm::NaClBitstreamEntry::Error:
406      return true;
407    case llvm::NaClBitstreamEntry::EndBlock:
408      if (Listener) Listener->EndBlockInfoBlock();
409      return false;
410    case llvm::NaClBitstreamEntry::Record:
411      // The interesting case.
412      break;
413    }
414
415    // Read abbrev records, associate them with CurBID.
416    if (Entry.ID == naclbitc::DEFINE_ABBREV) {
417      ReadAbbrevRecord(false, Listener);
418
419      // ReadAbbrevRecord installs a local abbreviation.  Move it to the
420      // appropriate BlockInfo if the corresponding SetBID record has been
421      // found.
422      if (FoundSetBID)
423        CurBlock.moveLocalAbbrevToAbbrevList(UpdateAbbrevs);
424      continue;
425    }
426
427    // Read a record.
428    Record.clear();
429    switch (readRecord(Entry.ID, Record)) {
430      default:
431        // No other records should be found!
432        return true;
433      case naclbitc::BLOCKINFO_CODE_SETBID:
434        if (Record.size() < 1) return true;
435        FoundSetBID = true;
436        UpdateAbbrevs =
437            &BitStream->getBlockInfo((unsigned)Record[0])->getAbbrevs();
438        if (Listener) {
439          Listener->Values = Record;
440          Listener->SetBID();
441        }
442        break;
443    }
444  }
445}
446