Per code review:\
[oota-llvm.git] / lib / Bytecode / Archive / ArchiveReader.cpp
1 //===-- ArchiveReader.cpp - Read LLVM archive files -------------*- C++ -*-===//
2 // 
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file was developed by Reid Spencer and is distributed under the 
6 // University of Illinois Open Source License. See LICENSE.TXT for details.
7 // 
8 //===----------------------------------------------------------------------===//
9 //
10 // Builds up standard unix archive files (.a) containing LLVM bytecode.
11 //
12 //===----------------------------------------------------------------------===//
13
14 #include "ArchiveInternals.h"
15 #include "llvm/Bytecode/Reader.h"
16
17 using namespace llvm;
18
19 /// Read a variable-bit-rate encoded unsigned integer
20 inline unsigned readInteger(const char*&At, const char*End) {
21   unsigned Shift = 0;
22   unsigned Result = 0;
23   
24   do {
25     if (At == End) 
26       throw std::string("Ran out of data reading vbr_uint!");
27     Result |= (unsigned)((*At++) & 0x7F) << Shift;
28     Shift += 7;
29   } while (At[-1] & 0x80);
30   return Result;
31 }
32
33 // Completely parse the Archive's symbol table and populate symTab member var.
34 void
35 Archive::parseSymbolTable(const void* data, unsigned size) {
36   const char* At = (const char*) data;
37   const char* End = At + size;
38   while (At < End) {
39     unsigned offset = readInteger(At, End);
40     unsigned length = readInteger(At, End);
41     if (At + length > End)
42       throw std::string("malformed symbol table");
43     // we don't care if it can't be inserted (duplicate entry)
44     symTab.insert(std::make_pair(std::string(At,length),offset));
45     At += length;
46   }
47   symTabSize = size;
48 }
49
50 // This member parses an ArchiveMemberHeader that is presumed to be pointed to
51 // by At. The At pointer is updated to the byte just after the header, which
52 // can be variable in size. 
53 ArchiveMember*
54 Archive::parseMemberHeader(const char*& At, const char* End) {
55   assert(At + sizeof(ArchiveMemberHeader) < End && "Not enough data");
56
57   // Cast archive member header
58   ArchiveMemberHeader* Hdr = (ArchiveMemberHeader*)At;
59   At += sizeof(ArchiveMemberHeader);
60
61   // Instantiate the ArchiveMember to be filled
62   ArchiveMember* member = new ArchiveMember(this);
63
64   // Extract the size and determine if the file is 
65   // compressed or not (negative length).
66   int flags = 0;
67   int MemberSize = atoi(Hdr->size);
68   if (MemberSize < 0) {
69     flags |= ArchiveMember::CompressedFlag;
70     MemberSize = -MemberSize;
71   }
72
73   // Check the size of the member for sanity
74   if (At + MemberSize > End)
75     throw std::string("invalid member length in archive file");
76
77   // Check the member signature
78   if (!Hdr->checkSignature())
79     throw std::string("invalid file member signature");
80
81   // Convert and check the member name
82   // The empty name ( '/' and 15 blanks) is for a foreign (non-LLVM) symbol 
83   // table. The special name "//" and 14 blanks is for a string table, used 
84   // for long file names. This library doesn't generate either of those but
85   // it will accept them. If the name starts with #1/ and the remainder is 
86   // digits, then those digits specify the length of the name that is 
87   // stored immediately following the header. The special name 
88   // __LLVM_SYM_TAB__ identifies the symbol table for LLVM bytecode. 
89   // Anything else is a regular, short filename that is terminated with 
90   // a '/' and blanks.
91
92   std::string pathname;
93   unsigned index;
94   switch (Hdr->name[0]) {
95     case '#':
96       if (Hdr->name[1] == '1' && Hdr->name[2] == '/') {
97         if (isdigit(Hdr->name[3])) {
98           unsigned len = atoi(&Hdr->name[3]);
99           pathname.assign(At,len);
100           At += len + 1; // terminated by \n
101           flags |= ArchiveMember::HasLongFilenameFlag;
102         } else
103           throw std::string("invalid long filename");
104       } else if (Hdr->name[1] == '_' && 
105                  (0==memcmp(Hdr->name,ARFILE_LLVM_SYMTAB_NAME,16))) {
106         // The member is using a long file name (>15 chars) format.
107         // This format is standard for 4.4BSD and Mac OSX operating
108         // systems. LLVM uses it similarly. In this format, the
109         // remainder of the name field (after #1/) specifies the
110         // length of the file name which occupy the first bytes of
111         // the member's data. The pathname already has the #1/ stripped.
112         pathname.assign(ARFILE_LLVM_SYMTAB_NAME);
113         flags |= ArchiveMember::LLVMSymbolTableFlag;
114       }
115       break;
116     case '/':
117       if (Hdr->name[1]== '/') {
118         if (0==memcmp(Hdr->name,ARFILE_STRTAB_NAME,16)) {
119           pathname.assign(ARFILE_STRTAB_NAME);
120           flags |= ArchiveMember::StringTableFlag;
121         } else {
122           throw std::string("invalid string table name");
123         }
124       } else if (Hdr->name[1] == ' ') {
125         if (0==memcmp(Hdr->name,ARFILE_SYMTAB_NAME,16)) {
126           pathname.assign(ARFILE_SYMTAB_NAME);
127           flags |= ArchiveMember::ForeignSymbolTableFlag;
128         } else {
129           throw std::string("invalid foreign symbol table name");
130         }
131       } else if (isdigit(Hdr->name[1])) {
132         unsigned index = atoi(&Hdr->name[1]);
133         if (index < strtab.length()) {
134           const char* namep = strtab.c_str() + index;
135           const char* endp = strtab.c_str() + strtab.length();
136           const char* p = namep;
137           const char* last_p = p;
138           while (p < endp) {
139             if (*p == '\n' && *last_p == '/') {
140               pathname.assign(namep,last_p-namep);
141               flags |= ArchiveMember::HasLongFilenameFlag;
142               break;
143             }
144             last_p = p;
145             p++;
146           }
147           if (p >= endp)
148             throw std::string("missing name termiantor in string table");
149         } else {
150           throw std::string("name index beyond string table");
151         }
152       }
153       break;
154
155     default:
156       char* slash = (char*) memchr(Hdr->name,'/',16);
157       if (slash == 0)
158         throw std::string("missing name terminator");
159       pathname.assign(Hdr->name,slash-Hdr->name);
160       break;
161   }
162
163   // Determine if this is a bytecode file
164   switch (sys::IdentifyFileType(At,4)) {
165     case sys::BytecodeFileType:
166       flags |= ArchiveMember::BytecodeFlag;
167       break;
168     case sys::CompressedBytecodeFileType:
169       flags |= ArchiveMember::CompressedBytecodeFlag;
170       flags &= ~ArchiveMember::CompressedFlag;
171       break;
172     default:
173       flags &= ~(ArchiveMember::BytecodeFlag|
174                  ArchiveMember::CompressedBytecodeFlag);
175       break;
176   }
177
178   // Fill in fields of the ArchiveMember
179   member->next = 0;
180   member->prev = 0;
181   member->parent = this;
182   member->path.setFile(pathname);
183   member->info.fileSize = MemberSize;
184   member->info.modTime.fromEpochTime(atoi(Hdr->date));
185   sscanf(Hdr->mode,"%o",&(member->info.mode));
186   member->info.user = atoi(Hdr->uid);
187   member->info.group = atoi(Hdr->gid);
188   member->flags = flags;
189   member->data = At;
190
191   return member;
192 }
193
194 void
195 Archive::checkSignature() {
196   // Check the magic string at file's header
197   if (mapfile->size() < 8 || memcmp(base, ARFILE_MAGIC,8))
198     throw std::string("invalid signature for an archive file");
199 }
200
201 // This function loads the entire archive and fully populates its ilist with 
202 // the members of the archive file. This is typically used in preparation for
203 // editing the contents of the archive.
204 void
205 Archive::loadArchive() {
206
207   // Set up parsing
208   members.clear();
209   symTab.clear();
210   const char *At = base;
211   const char *End = base + mapfile->size();
212
213   checkSignature();
214   At += 8;  // Skip the magic string.
215
216   bool seenSymbolTable = false;
217   bool foundFirstFile = false;
218   while (At < End) {
219     // parse the member header 
220     const char* Save = At;
221     ArchiveMember* mbr = parseMemberHeader(At, End);
222
223     // check if this is the foreign symbol table
224     if (mbr->isForeignSymbolTable()) {
225       // We just save this but don't do anything special
226       // with it. It doesn't count as the "first file".
227       foreignST = mbr;
228       At += mbr->getSize();
229       if ((mbr->getSize() & 1) == 1)
230         At++;
231     } else if (mbr->isStringTable()) {
232       // Simply suck the entire string table into a string
233       // variable. This will be used to get the names of the
234       // members that use the "/ddd" format for their names
235       // (SVR4 style long names).
236       strtab.assign(At,mbr->getSize());
237       At += mbr->getSize();
238       if ((mbr->getSize() & 1) == 1)
239         At++;
240       delete mbr;
241     } else if (mbr->isLLVMSymbolTable()) { 
242       // This is the LLVM symbol table for the archive. If we've seen it
243       // already, its an error. Otherwise, parse the symbol table and move on.
244       if (seenSymbolTable)
245         throw std::string("invalid archive: multiple symbol tables");
246       parseSymbolTable(mbr->getData(),mbr->getSize());
247       seenSymbolTable = true;
248       At += mbr->getSize();
249       if ((mbr->getSize() & 1) == 1)
250         At++;
251       delete mbr; // We don't need this member in the list of members.
252     } else {
253       // This is just a regular file. If its the first one, save its offset.
254       // Otherwise just push it on the list and move on to the next file.
255       if (!foundFirstFile) {
256         firstFileOffset = Save - base;
257         foundFirstFile = true;
258       }
259       members.push_back(mbr);
260       At += mbr->getSize();
261       if ((mbr->getSize() & 1) == 1)
262         At++;
263     }
264   }
265 }
266
267 // Open and completely load the archive file.
268 Archive*
269 Archive::OpenAndLoad(const sys::Path& file) {
270
271   Archive* result = new Archive(file,true);
272
273   result->loadArchive();
274   
275   return result;
276 }
277
278 // Get all the bytecode modules from the archive
279 bool
280 Archive::getAllModules(std::vector<Module*>& Modules, std::string* ErrMessage) {
281
282   for (iterator I=begin(), E=end(); I != E; ++I) {
283     if (I->isBytecode() || I->isCompressedBytecode()) {
284       Module* M = ParseBytecodeBuffer((const unsigned char*)I->getData(), 
285           I->getSize(), I->getPath().get(), ErrMessage);
286       if (!M)
287         return true;
288
289       Modules.push_back(M);
290     }
291   }
292   return false;
293 }
294
295 // Load just the symbol table from the archive file
296 void
297 Archive::loadSymbolTable() {
298
299   // Set up parsing
300   members.clear();
301   symTab.clear();
302   const char *At = base;
303   const char *End = base + mapfile->size();
304
305   // Make sure we're dealing with an archive
306   checkSignature();
307
308   At += 8; // Skip signature
309
310   // Parse the first file member header
311   const char* FirstFile = At;
312   ArchiveMember* mbr = parseMemberHeader(At, End);
313
314   if (mbr->isForeignSymbolTable()) {
315     // Skip the foreign symbol table, we don't do anything with it
316     At += mbr->getSize();
317     if ((mbr->getSize() & 1) == 1)
318       At++;
319     delete mbr;
320
321     // Read the next one
322     FirstFile = At;
323     mbr = parseMemberHeader(At,End);
324   }
325
326   if (mbr->isStringTable()) {
327     // Process the string table entry
328     strtab.assign((const char*)mbr->getData(),mbr->getSize());
329     At += mbr->getSize();
330     if ((mbr->getSize() & 1) == 1)
331       At++;
332     delete mbr;
333     // Get the next one
334     FirstFile = At;
335     mbr = parseMemberHeader(At,End);
336   }
337
338   // See if its the symbol table
339   if (mbr->isLLVMSymbolTable()) {
340     parseSymbolTable(mbr->getData(),mbr->getSize());
341     FirstFile = At + mbr->getSize();
342     if ((mbr->getSize() & 1) == 1)
343       FirstFile++;
344   } else {
345     // There's no symbol table in the file. We have to rebuild it from scratch
346     // because the intent of this method is to get the symbol table loaded so 
347     // it can be searched efficiently. 
348     // Add the member to the members list
349     members.push_back(mbr);
350   }
351
352   firstFileOffset = FirstFile - base;
353 }
354
355 // Open the archive and load just the symbol tables
356 Archive*
357 Archive::OpenAndLoadSymbols(const sys::Path& file) {
358   Archive* result = new Archive(file,true);
359
360   result->loadSymbolTable();
361
362   return result;
363 }
364
365 // Look up one symbol in the symbol table and return a ModuleProvider for the
366 // module that defines that symbol.
367 ModuleProvider* 
368 Archive::findModuleDefiningSymbol(const std::string& symbol) {
369   SymTabType::iterator SI = symTab.find(symbol);
370   if (SI == symTab.end())
371     return 0;
372
373   // The symbol table was previously constructed assuming that the members were 
374   // written without the symbol table header. Because VBR encoding is used, the
375   // values could not be adjusted to account for the offset of the symbol table
376   // because that could affect the size of the symbol table due to VBR encoding.
377   // We now have to account for this by adjusting the offset by the size of the 
378   // symbol table and its header.
379   unsigned fileOffset = 
380     SI->second +                // offset in symbol-table-less file
381     firstFileOffset;            // add offset to first "real" file in archive
382
383   // See if the module is already loaded
384   ModuleMap::iterator MI = modules.find(fileOffset);
385   if (MI != modules.end())
386     return MI->second.first;
387
388   // Module hasn't been loaded yet, we need to load it
389   const char* modptr = base + fileOffset;
390   ArchiveMember* mbr = parseMemberHeader(modptr, base + mapfile->size());
391
392   // Now, load the bytecode module to get the ModuleProvider
393   ModuleProvider* mp = getBytecodeBufferModuleProvider(
394       (const unsigned char*) mbr->getData(), mbr->getSize(), 
395       mbr->getPath().get(), 0);
396
397   modules.insert(std::make_pair(fileOffset,std::make_pair(mp,mbr)));
398
399   return mp;
400 }
401
402 // Look up multiple symbols in the symbol table and return a set of 
403 // ModuleProviders that define those symbols.
404 void
405 Archive::findModulesDefiningSymbols(const std::set<std::string>& symbols,
406                                     std::set<ModuleProvider*>& result)
407 {
408   assert(mapfile && base && "Can't findModulesDefiningSymbols on new archive");
409   if (symTab.empty()) {
410     // We don't have a symbol table, so we must build it now but lets also
411     // make sure that we populate the modules table as we do this to ensure
412     // that we don't load them twice when findModuleDefiningSymbol is called
413     // below.
414
415     // Get a pointer to the first file
416     const char* At  = ((const char*)base) + firstFileOffset;
417     const char* End = ((const char*)base) + mapfile->size();
418
419     while ( At < End) {
420       // Compute the offset to be put in the symbol table
421       unsigned offset = At - base - firstFileOffset;
422
423       // Parse the file's header
424       ArchiveMember* mbr = parseMemberHeader(At, End);
425
426       // If it contains symbols
427       if (mbr->isBytecode() || mbr->isCompressedBytecode()) {
428         // Get the symbols 
429         std::vector<std::string> symbols;
430         ModuleProvider* MP = GetBytecodeSymbols((const unsigned char*)At,
431             mbr->getSize(), mbr->getPath().get(),symbols);
432
433         if (MP) {
434           // Insert the module's symbols into the symbol table
435           for (std::vector<std::string>::iterator I = symbols.begin(), 
436                E=symbols.end(); I != E; ++I ) {
437             symTab.insert(std::make_pair(*I,offset));
438           }
439           // Insert the ModuleProvider and the ArchiveMember into the table of
440           // modules.
441           modules.insert(std::make_pair(offset,std::make_pair(MP,mbr)));
442         } else {
443           throw std::string("Can't parse bytecode member: ") +
444             mbr->getPath().get();
445         }
446       }
447
448       // Go to the next file location
449       At += mbr->getSize();
450       if ((mbr->getSize() & 1) == 1)
451         At++;
452     }
453   }
454
455   // At this point we have a valid symbol table (one way or another) so we 
456   // just use it to quickly find the symbols requested.
457
458   for (std::set<std::string>::const_iterator I=symbols.begin(), 
459        E=symbols.end(); I != E; ++I) {
460     ModuleProvider* mp = findModuleDefiningSymbol(*I);
461     if (mp) {
462       result.insert(mp);
463     }
464   }
465 }