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