]> CyberLeo.Net >> Repos - FreeBSD/FreeBSD.git/blob - lib/ReaderWriter/Native/WriterNative.cpp
Vendor import of lld trunk r233088:
[FreeBSD/FreeBSD.git] / lib / ReaderWriter / Native / WriterNative.cpp
1 //===- lib/ReaderWriter/Native/WriterNative.cpp ---------------------------===//
2 //
3 //                             The LLVM Linker
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 "NativeFileFormat.h"
11 #include "lld/Core/File.h"
12 #include "lld/Core/LinkingContext.h"
13 #include "lld/Core/Writer.h"
14 #include "llvm/ADT/ArrayRef.h"
15 #include "llvm/ADT/DenseMap.h"
16 #include "llvm/ADT/StringRef.h"
17 #include "llvm/Support/raw_ostream.h"
18 #include <cstdint>
19 #include <set>
20 #include <system_error>
21 #include <vector>
22
23 namespace lld {
24 namespace native {
25
26 ///
27 /// Class for writing native object files.
28 ///
29 class Writer : public lld::Writer {
30 public:
31   std::error_code writeFile(const lld::File &file, StringRef outPath) override {
32     // reserve first byte for unnamed atoms
33     _stringPool.push_back('\0');
34     // visit all atoms
35     for ( const DefinedAtom *defAtom : file.defined() ) {
36       this->addIVarsForDefinedAtom(*defAtom);
37       // We are trying to process all atoms, but the defined() iterator does not
38       // return group children. So, when a group parent is found, we need to
39       // handle each child atom.
40       if (defAtom->isGroupParent()) {
41         for (const Reference *r : *defAtom) {
42           if (r->kindNamespace() != lld::Reference::KindNamespace::all)
43             continue;
44           if (r->kindValue() == lld::Reference::kindGroupChild) {
45             const DefinedAtom *target = dyn_cast<DefinedAtom>(r->target());
46             assert(target && "Internal Error: kindGroupChild references need "
47                              "to be associated with Defined Atoms only");
48             this->addIVarsForDefinedAtom(*target);
49           }
50         }
51       }
52     }
53     for ( const UndefinedAtom *undefAtom : file.undefined() ) {
54       this->addIVarsForUndefinedAtom(*undefAtom);
55     }
56     for ( const SharedLibraryAtom *shlibAtom : file.sharedLibrary() ) {
57       this->addIVarsForSharedLibraryAtom(*shlibAtom);
58     }
59     for ( const AbsoluteAtom *absAtom : file.absolute() ) {
60       this->addIVarsForAbsoluteAtom(*absAtom);
61     }
62
63     maybeConvertReferencesToV1();
64
65     // construct file header based on atom information accumulated
66     this->makeHeader();
67
68     std::error_code ec;
69     llvm::raw_fd_ostream out(outPath, ec, llvm::sys::fs::F_None);
70     if (ec)
71       return ec;
72
73     this->write(out);
74
75     return std::error_code();
76   }
77
78   virtual ~Writer() {
79   }
80
81 private:
82
83   // write the lld::File in native format to the specified stream
84   void write(raw_ostream &out) {
85     assert(out.tell() == 0);
86     out.write((char*)_headerBuffer, _headerBufferSize);
87
88     writeChunk(out, _definedAtomIvars, NCS_DefinedAtomsV1);
89     writeChunk(out, _attributes, NCS_AttributesArrayV1);
90     writeChunk(out, _undefinedAtomIvars, NCS_UndefinedAtomsV1);
91     writeChunk(out, _sharedLibraryAtomIvars, NCS_SharedLibraryAtomsV1);
92     writeChunk(out, _absoluteAtomIvars, NCS_AbsoluteAtomsV1);
93     writeChunk(out, _absAttributes, NCS_AbsoluteAttributesV1);
94     writeChunk(out, _stringPool, NCS_Strings);
95     writeChunk(out, _referencesV1, NCS_ReferencesArrayV1);
96     writeChunk(out, _referencesV2, NCS_ReferencesArrayV2);
97
98     if (!_targetsTableIndex.empty()) {
99       assert(out.tell() == findChunk(NCS_TargetsTable).fileOffset);
100       writeTargetTable(out);
101     }
102
103     if (!_addendsTableIndex.empty()) {
104       assert(out.tell() == findChunk(NCS_AddendsTable).fileOffset);
105       writeAddendTable(out);
106     }
107
108     writeChunk(out, _contentPool, NCS_Content);
109   }
110
111   template<class T>
112   void writeChunk(raw_ostream &out, std::vector<T> &vector, uint32_t signature) {
113     if (vector.empty())
114       return;
115     assert(out.tell() == findChunk(signature).fileOffset);
116     out.write((char*)&vector[0], vector.size() * sizeof(T));
117   }
118
119   void addIVarsForDefinedAtom(const DefinedAtom& atom) {
120     _definedAtomIndex[&atom] = _definedAtomIvars.size();
121     NativeDefinedAtomIvarsV1 ivar;
122     unsigned refsCount;
123     ivar.nameOffset = getNameOffset(atom);
124     ivar.attributesOffset = getAttributeOffset(atom);
125     ivar.referencesStartIndex = getReferencesIndex(atom, refsCount);
126     ivar.referencesCount = refsCount;
127     ivar.contentOffset = getContentOffset(atom);
128     ivar.contentSize = atom.size();
129     ivar.sectionSize = atom.sectionSize();
130     _definedAtomIvars.push_back(ivar);
131   }
132
133   void addIVarsForUndefinedAtom(const UndefinedAtom& atom) {
134     _undefinedAtomIndex[&atom] = _undefinedAtomIvars.size();
135     NativeUndefinedAtomIvarsV1 ivar;
136     ivar.nameOffset = getNameOffset(atom);
137     ivar.flags = (atom.canBeNull() & 0x03);
138     ivar.fallbackNameOffset = 0;
139     if (atom.fallback())
140       ivar.fallbackNameOffset = getNameOffset(*atom.fallback());
141     _undefinedAtomIvars.push_back(ivar);
142   }
143
144   void addIVarsForSharedLibraryAtom(const SharedLibraryAtom& atom) {
145     _sharedLibraryAtomIndex[&atom] = _sharedLibraryAtomIvars.size();
146     NativeSharedLibraryAtomIvarsV1 ivar;
147     ivar.size = atom.size();
148     ivar.nameOffset = getNameOffset(atom);
149     ivar.loadNameOffset = getSharedLibraryNameOffset(atom.loadName());
150     ivar.type = (uint32_t)atom.type();
151     ivar.flags = atom.canBeNullAtRuntime();
152     _sharedLibraryAtomIvars.push_back(ivar);
153   }
154
155   void addIVarsForAbsoluteAtom(const AbsoluteAtom& atom) {
156     _absoluteAtomIndex[&atom] = _absoluteAtomIvars.size();
157     NativeAbsoluteAtomIvarsV1 ivar;
158     ivar.nameOffset = getNameOffset(atom);
159     ivar.attributesOffset = getAttributeOffset(atom);
160     ivar.reserved = 0;
161     ivar.value = atom.value();
162     _absoluteAtomIvars.push_back(ivar);
163   }
164
165   void convertReferencesToV1() {
166     for (const NativeReferenceIvarsV2 &v2 : _referencesV2) {
167       NativeReferenceIvarsV1 v1;
168       v1.offsetInAtom = v2.offsetInAtom;
169       v1.kindNamespace = v2.kindNamespace;
170       v1.kindArch = v2.kindArch;
171       v1.kindValue = v2.kindValue;
172       v1.targetIndex = (v2.targetIndex == NativeReferenceIvarsV2::noTarget) ?
173           (uint16_t)NativeReferenceIvarsV1::noTarget : v2.targetIndex;
174       v1.addendIndex = this->getAddendIndex(v2.addend);
175       _referencesV1.push_back(v1);
176     }
177     _referencesV2.clear();
178   }
179
180   bool canConvertReferenceToV1(const NativeReferenceIvarsV2 &ref) {
181     bool validOffset = (ref.offsetInAtom == NativeReferenceIvarsV2::noTarget) ||
182         ref.offsetInAtom < NativeReferenceIvarsV1::noTarget;
183     return validOffset && ref.targetIndex < UINT16_MAX;
184   }
185
186   // Convert vector of NativeReferenceIvarsV2 to NativeReferenceIvarsV1 if
187   // possible.
188   void maybeConvertReferencesToV1() {
189     std::set<int64_t> addends;
190     for (const NativeReferenceIvarsV2 &ref : _referencesV2) {
191       if (!canConvertReferenceToV1(ref))
192         return;
193       addends.insert(ref.addend);
194       if (addends.size() >= UINT16_MAX)
195         return;
196     }
197     convertReferencesToV1();
198   }
199
200   // fill out native file header and chunk directory
201   void makeHeader() {
202     const bool hasDefines = !_definedAtomIvars.empty();
203     const bool hasUndefines = !_undefinedAtomIvars.empty();
204     const bool hasSharedLibraries = !_sharedLibraryAtomIvars.empty();
205     const bool hasAbsolutes = !_absoluteAtomIvars.empty();
206     const bool hasReferencesV1 = !_referencesV1.empty();
207     const bool hasReferencesV2 = !_referencesV2.empty();
208     const bool hasTargetsTable = !_targetsTableIndex.empty();
209     const bool hasAddendTable = !_addendsTableIndex.empty();
210     const bool hasContent = !_contentPool.empty();
211
212     int chunkCount = 1; // always have string pool chunk
213     if ( hasDefines ) chunkCount += 2;
214     if ( hasUndefines ) ++chunkCount;
215     if ( hasSharedLibraries ) ++chunkCount;
216     if ( hasAbsolutes ) chunkCount += 2;
217     if ( hasReferencesV1 ) ++chunkCount;
218     if ( hasReferencesV2 ) ++chunkCount;
219     if ( hasTargetsTable ) ++chunkCount;
220     if ( hasAddendTable ) ++chunkCount;
221     if ( hasContent ) ++chunkCount;
222
223     _headerBufferSize = sizeof(NativeFileHeader)
224                          + chunkCount*sizeof(NativeChunk);
225     _headerBuffer = reinterpret_cast<NativeFileHeader*>
226                                (operator new(_headerBufferSize, std::nothrow));
227     NativeChunk *chunks =
228       reinterpret_cast<NativeChunk*>(reinterpret_cast<char*>(_headerBuffer)
229                                      + sizeof(NativeFileHeader));
230     memcpy(_headerBuffer->magic, NATIVE_FILE_HEADER_MAGIC,
231            sizeof(_headerBuffer->magic));
232     _headerBuffer->endian = NFH_LittleEndian;
233     _headerBuffer->architecture = 0;
234     _headerBuffer->fileSize = 0;
235     _headerBuffer->chunkCount = chunkCount;
236
237     // create chunk for defined atom ivar array
238     int nextIndex = 0;
239     uint32_t nextFileOffset = _headerBufferSize;
240     if (hasDefines) {
241       fillChunkHeader(chunks[nextIndex++], nextFileOffset, _definedAtomIvars,
242                       NCS_DefinedAtomsV1);
243
244       // create chunk for attributes
245       fillChunkHeader(chunks[nextIndex++], nextFileOffset, _attributes,
246                       NCS_AttributesArrayV1);
247     }
248
249     // create chunk for undefined atom array
250     if (hasUndefines)
251       fillChunkHeader(chunks[nextIndex++], nextFileOffset, _undefinedAtomIvars,
252                       NCS_UndefinedAtomsV1);
253
254     // create chunk for shared library atom array
255     if (hasSharedLibraries)
256       fillChunkHeader(chunks[nextIndex++], nextFileOffset,
257                       _sharedLibraryAtomIvars, NCS_SharedLibraryAtomsV1);
258
259      // create chunk for shared library atom array
260     if (hasAbsolutes) {
261       fillChunkHeader(chunks[nextIndex++], nextFileOffset, _absoluteAtomIvars,
262                       NCS_AbsoluteAtomsV1);
263
264       // create chunk for attributes
265       fillChunkHeader(chunks[nextIndex++], nextFileOffset, _absAttributes,
266                       NCS_AbsoluteAttributesV1);
267     }
268
269     // create chunk for symbol strings
270     // pad end of string pool to 4-bytes
271     while ((_stringPool.size() % 4) != 0)
272       _stringPool.push_back('\0');
273     fillChunkHeader(chunks[nextIndex++], nextFileOffset, _stringPool,
274                     NCS_Strings);
275
276     // create chunk for referencesV2
277     if (hasReferencesV1)
278       fillChunkHeader(chunks[nextIndex++], nextFileOffset, _referencesV1,
279                       NCS_ReferencesArrayV1);
280
281     // create chunk for referencesV2
282     if (hasReferencesV2)
283       fillChunkHeader(chunks[nextIndex++], nextFileOffset, _referencesV2,
284                       NCS_ReferencesArrayV2);
285
286     // create chunk for target table
287     if (hasTargetsTable) {
288       NativeChunk& cht = chunks[nextIndex++];
289       cht.signature = NCS_TargetsTable;
290       cht.fileOffset = nextFileOffset;
291       cht.fileSize = _targetsTableIndex.size() * sizeof(uint32_t);
292       cht.elementCount = _targetsTableIndex.size();
293       nextFileOffset = cht.fileOffset + cht.fileSize;
294     }
295
296     // create chunk for addend table
297     if (hasAddendTable) {
298       NativeChunk& chad = chunks[nextIndex++];
299       chad.signature = NCS_AddendsTable;
300       chad.fileOffset = nextFileOffset;
301       chad.fileSize = _addendsTableIndex.size() * sizeof(Reference::Addend);
302       chad.elementCount = _addendsTableIndex.size();
303       nextFileOffset = chad.fileOffset + chad.fileSize;
304     }
305
306     // create chunk for content
307     if (hasContent)
308       fillChunkHeader(chunks[nextIndex++], nextFileOffset, _contentPool,
309                       NCS_Content);
310
311     _headerBuffer->fileSize = nextFileOffset;
312   }
313
314   template<class T>
315   void fillChunkHeader(NativeChunk &chunk, uint32_t &nextFileOffset,
316                        const std::vector<T> &data, uint32_t signature) {
317     chunk.signature = signature;
318     chunk.fileOffset = nextFileOffset;
319     chunk.fileSize = data.size() * sizeof(T);
320     chunk.elementCount = data.size();
321     nextFileOffset = chunk.fileOffset + chunk.fileSize;
322   }
323
324   // scan header to find particular chunk
325   NativeChunk& findChunk(uint32_t signature) {
326     const uint32_t chunkCount = _headerBuffer->chunkCount;
327     NativeChunk* chunks =
328       reinterpret_cast<NativeChunk*>(reinterpret_cast<char*>(_headerBuffer)
329                                      + sizeof(NativeFileHeader));
330     for (uint32_t i=0; i < chunkCount; ++i) {
331       if ( chunks[i].signature == signature )
332         return chunks[i];
333     }
334     llvm_unreachable("findChunk() signature not found");
335   }
336
337   // append atom name to string pool and return offset
338   uint32_t getNameOffset(const Atom& atom) {
339     return this->getNameOffset(atom.name());
340   }
341
342   // check if name is already in pool or append and return offset
343   uint32_t getSharedLibraryNameOffset(StringRef name) {
344     assert(!name.empty());
345     // look to see if this library name was used by another atom
346     for (auto &it : _sharedLibraryNames)
347       if (name.equals(it.first))
348         return it.second;
349     // first use of this library name
350     uint32_t result = this->getNameOffset(name);
351     _sharedLibraryNames.push_back(std::make_pair(name, result));
352     return result;
353   }
354
355   // append atom name to string pool and return offset
356   uint32_t getNameOffset(StringRef name) {
357     if ( name.empty() )
358       return 0;
359     uint32_t result = _stringPool.size();
360     _stringPool.insert(_stringPool.end(), name.begin(), name.end());
361     _stringPool.push_back(0);
362     return result;
363   }
364
365   // append atom cotent to content pool and return offset
366   uint32_t getContentOffset(const DefinedAtom& atom) {
367     if (!atom.occupiesDiskSpace())
368       return 0;
369     uint32_t result = _contentPool.size();
370     ArrayRef<uint8_t> cont = atom.rawContent();
371     _contentPool.insert(_contentPool.end(), cont.begin(), cont.end());
372     return result;
373   }
374
375   // reuse existing attributes entry or create a new one and return offet
376   uint32_t getAttributeOffset(const DefinedAtom& atom) {
377     NativeAtomAttributesV1 attrs = computeAttributesV1(atom);
378     return getOrPushAttribute(_attributes, attrs);
379   }
380
381   uint32_t getAttributeOffset(const AbsoluteAtom& atom) {
382     NativeAtomAttributesV1 attrs = computeAbsoluteAttributes(atom);
383     return getOrPushAttribute(_absAttributes, attrs);
384   }
385
386   uint32_t getOrPushAttribute(std::vector<NativeAtomAttributesV1> &dest,
387                               const NativeAtomAttributesV1 &attrs) {
388     for (size_t i = 0, e = dest.size(); i < e; ++i) {
389       if (!memcmp(&dest[i], &attrs, sizeof(attrs))) {
390         // found that this set of attributes already used, so re-use
391         return i * sizeof(attrs);
392       }
393     }
394     // append new attribute set to end
395     uint32_t result = dest.size() * sizeof(attrs);
396     dest.push_back(attrs);
397     return result;
398   }
399
400   uint32_t sectionNameOffset(const DefinedAtom& atom) {
401     // if section based on content, then no custom section name available
402     if (atom.sectionChoice() == DefinedAtom::sectionBasedOnContent)
403       return 0;
404     StringRef name = atom.customSectionName();
405     assert(!name.empty());
406     // look to see if this section name was used by another atom
407     for (auto &it : _sectionNames)
408       if (name.equals(it.first))
409         return it.second;
410     // first use of this section name
411     uint32_t result = this->getNameOffset(name);
412     _sectionNames.push_back(std::make_pair(name, result));
413     return result;
414   }
415
416   NativeAtomAttributesV1 computeAttributesV1(const DefinedAtom& atom) {
417     NativeAtomAttributesV1 attrs;
418     attrs.sectionNameOffset = sectionNameOffset(atom);
419     attrs.align2            = atom.alignment().powerOf2;
420     attrs.alignModulus      = atom.alignment().modulus;
421     attrs.scope             = atom.scope();
422     attrs.interposable      = atom.interposable();
423     attrs.merge             = atom.merge();
424     attrs.contentType       = atom.contentType();
425     attrs.sectionChoice     = atom.sectionChoice();
426     attrs.deadStrip         = atom.deadStrip();
427     attrs.dynamicExport     = atom.dynamicExport();
428     attrs.codeModel         = atom.codeModel();
429     attrs.permissions       = atom.permissions();
430     return attrs;
431   }
432
433   NativeAtomAttributesV1 computeAbsoluteAttributes(const AbsoluteAtom& atom) {
434     NativeAtomAttributesV1 attrs;
435     attrs.scope = atom.scope();
436     return attrs;
437   }
438
439   // add references for this atom in a contiguous block in NCS_ReferencesArrayV2
440   uint32_t getReferencesIndex(const DefinedAtom& atom, unsigned& refsCount) {
441     size_t startRefSize = _referencesV2.size();
442     uint32_t result = startRefSize;
443     for (const Reference *ref : atom) {
444       NativeReferenceIvarsV2 nref;
445       nref.offsetInAtom = ref->offsetInAtom();
446       nref.kindNamespace = (uint8_t)ref->kindNamespace();
447       nref.kindArch = (uint8_t)ref->kindArch();
448       nref.kindValue = ref->kindValue();
449       nref.targetIndex = this->getTargetIndex(ref->target());
450       nref.addend = ref->addend();
451       nref.tag = ref->tag();
452       _referencesV2.push_back(nref);
453     }
454     refsCount = _referencesV2.size() - startRefSize;
455     return (refsCount == 0) ? 0 : result;
456   }
457
458   uint32_t getTargetIndex(const Atom* target) {
459     if ( target == nullptr )
460       return NativeReferenceIvarsV2::noTarget;
461     TargetToIndex::const_iterator pos = _targetsTableIndex.find(target);
462     if ( pos != _targetsTableIndex.end() ) {
463       return pos->second;
464     }
465     uint32_t result = _targetsTableIndex.size();
466     _targetsTableIndex[target] = result;
467     return result;
468   }
469
470   void writeTargetTable(raw_ostream &out) {
471     // Build table of target indexes
472     uint32_t maxTargetIndex = _targetsTableIndex.size();
473     assert(maxTargetIndex > 0);
474     std::vector<uint32_t> targetIndexes(maxTargetIndex);
475     for (auto &it : _targetsTableIndex) {
476       const Atom* atom = it.first;
477       uint32_t targetIndex = it.second;
478       assert(targetIndex < maxTargetIndex);
479
480       TargetToIndex::iterator pos = _definedAtomIndex.find(atom);
481       if (pos != _definedAtomIndex.end()) {
482         targetIndexes[targetIndex] = pos->second;
483         continue;
484       }
485       uint32_t base = _definedAtomIvars.size();
486
487       pos = _undefinedAtomIndex.find(atom);
488       if (pos != _undefinedAtomIndex.end()) {
489         targetIndexes[targetIndex] = pos->second + base;
490         continue;
491       }
492       base += _undefinedAtomIndex.size();
493
494       pos = _sharedLibraryAtomIndex.find(atom);
495       if (pos != _sharedLibraryAtomIndex.end()) {
496         targetIndexes[targetIndex] = pos->second + base;
497         continue;
498       }
499       base += _sharedLibraryAtomIndex.size();
500
501       pos = _absoluteAtomIndex.find(atom);
502       assert(pos != _absoluteAtomIndex.end());
503       targetIndexes[targetIndex] = pos->second + base;
504     }
505     // write table
506     out.write((char*)&targetIndexes[0], maxTargetIndex * sizeof(uint32_t));
507   }
508
509   uint32_t getAddendIndex(Reference::Addend addend) {
510     if ( addend == 0 )
511       return 0; // addend index zero is used to mean "no addend"
512     AddendToIndex::const_iterator pos = _addendsTableIndex.find(addend);
513     if ( pos != _addendsTableIndex.end() ) {
514       return pos->second;
515     }
516     uint32_t result = _addendsTableIndex.size() + 1; // one-based index
517     _addendsTableIndex[addend] = result;
518     return result;
519   }
520
521   void writeAddendTable(raw_ostream &out) {
522     // Build table of addends
523     uint32_t maxAddendIndex = _addendsTableIndex.size();
524     std::vector<Reference::Addend> addends(maxAddendIndex);
525     for (auto &it : _addendsTableIndex) {
526       Reference::Addend addend = it.first;
527       uint32_t index = it.second;
528       assert(index <= maxAddendIndex);
529       addends[index-1] = addend;
530     }
531     // write table
532     out.write((char*)&addends[0], maxAddendIndex*sizeof(Reference::Addend));
533   }
534
535   typedef std::vector<std::pair<StringRef, uint32_t>> NameToOffsetVector;
536
537   typedef llvm::DenseMap<const Atom*, uint32_t> TargetToIndex;
538   typedef llvm::DenseMap<Reference::Addend, uint32_t> AddendToIndex;
539
540   NativeFileHeader*                       _headerBuffer;
541   size_t                                  _headerBufferSize;
542   std::vector<char>                       _stringPool;
543   std::vector<uint8_t>                    _contentPool;
544   std::vector<NativeDefinedAtomIvarsV1>   _definedAtomIvars;
545   std::vector<NativeAtomAttributesV1>     _attributes;
546   std::vector<NativeAtomAttributesV1>     _absAttributes;
547   std::vector<NativeUndefinedAtomIvarsV1> _undefinedAtomIvars;
548   std::vector<NativeSharedLibraryAtomIvarsV1> _sharedLibraryAtomIvars;
549   std::vector<NativeAbsoluteAtomIvarsV1>  _absoluteAtomIvars;
550   std::vector<NativeReferenceIvarsV1>     _referencesV1;
551   std::vector<NativeReferenceIvarsV2>     _referencesV2;
552   TargetToIndex                           _targetsTableIndex;
553   TargetToIndex                           _definedAtomIndex;
554   TargetToIndex                           _undefinedAtomIndex;
555   TargetToIndex                           _sharedLibraryAtomIndex;
556   TargetToIndex                           _absoluteAtomIndex;
557   AddendToIndex                           _addendsTableIndex;
558   NameToOffsetVector                      _sectionNames;
559   NameToOffsetVector                      _sharedLibraryNames;
560 };
561 } // end namespace native
562
563 std::unique_ptr<Writer> createWriterNative() {
564   return std::unique_ptr<Writer>(new native::Writer());
565 }
566 } // end namespace lld