1 //===- lib/ReaderWriter/MachO/GOTPass.cpp -----------------------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 ///
9 /// \file
10 /// This linker pass transforms all GOT kind references to real references.
11 /// That is, in assembly you can write something like:
12 ///     movq foo@GOTPCREL(%rip), %rax
13 /// which means you want to load a pointer to "foo" out of the GOT (global
14 /// Offsets Table). In the object file, the Atom containing this instruction
15 /// has a Reference whose target is an Atom named "foo" and the Reference
16 /// kind is a GOT load.  The linker needs to instantiate a pointer sized
17 /// GOT entry.  This is done be creating a GOT Atom to represent that pointer
18 /// sized data in this pass, and altering the Atom graph so the Reference now
19 /// points to the GOT Atom entry (corresponding to "foo") and changing the
20 /// Reference Kind to reflect it is now pointing to a GOT entry (rather
21 /// then needing a GOT entry).
22 ///
23 /// There is one optimization the linker can do here.  If the target of the GOT
24 /// is in the same linkage unit and does not need to be interposable, and
25 /// the GOT use is just a load (not some other operation), this pass can
26 /// transform that load into an LEA (add).  This optimizes away one memory load
27 /// which at runtime that could stall the pipeline.  This optimization only
28 /// works for architectures in which a (GOT) load instruction can be change to
29 /// an LEA instruction that is the same size.  The method isGOTAccess() should
30 /// only return true for "canBypassGOT" if this optimization is supported.
31 ///
32 //===----------------------------------------------------------------------===//
33 
34 #include "ArchHandler.h"
35 #include "File.h"
36 #include "MachOPasses.h"
37 #include "lld/Common/LLVM.h"
38 #include "lld/Core/DefinedAtom.h"
39 #include "lld/Core/File.h"
40 #include "lld/Core/Reference.h"
41 #include "lld/Core/Simple.h"
42 #include "llvm/ADT/DenseMap.h"
43 #include "llvm/ADT/STLExtras.h"
44 
45 namespace lld {
46 namespace mach_o {
47 
48 //
49 //  GOT Entry Atom created by the GOT pass.
50 //
51 class GOTEntryAtom : public SimpleDefinedAtom {
52 public:
53   GOTEntryAtom(const File &file, bool is64, StringRef name)
54     : SimpleDefinedAtom(file), _is64(is64), _name(name) { }
55 
56   ~GOTEntryAtom() override = default;
57 
58   ContentType contentType() const override {
59     return DefinedAtom::typeGOT;
60   }
61 
62   Alignment alignment() const override {
63     return _is64 ? 8 : 4;
64   }
65 
66   uint64_t size() const override {
67     return _is64 ? 8 : 4;
68   }
69 
70   ContentPermissions permissions() const override {
71     return DefinedAtom::permRW_;
72   }
73 
74   ArrayRef<uint8_t> rawContent() const override {
75     static const uint8_t zeros[] =
76         { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 };
77     return llvm::makeArrayRef(zeros, size());
78   }
79 
80   StringRef slotName() const {
81     return _name;
82   }
83 
84 private:
85   const bool _is64;
86   StringRef _name;
87 };
88 
89 /// Pass for instantiating and optimizing GOT slots.
90 ///
91 class GOTPass : public Pass {
92 public:
93   GOTPass(const MachOLinkingContext &context)
94       : _ctx(context), _archHandler(_ctx.archHandler()),
95         _file(*_ctx.make_file<MachOFile>("<mach-o GOT Pass>")) {
96     _file.setOrdinal(_ctx.getNextOrdinalAndIncrement());
97   }
98 
99 private:
100   llvm::Error perform(SimpleFile &mergedFile) override {
101     // Scan all references in all atoms.
102     for (const DefinedAtom *atom : mergedFile.defined()) {
103       for (const Reference *ref : *atom) {
104         // Look at instructions accessing the GOT.
105         bool canBypassGOT;
106         if (!_archHandler.isGOTAccess(*ref, canBypassGOT))
107           continue;
108         const Atom *target = ref->target();
109         assert(target != nullptr);
110 
111         if (!shouldReplaceTargetWithGOTAtom(target, canBypassGOT)) {
112           // Update reference kind to reflect that target is a direct accesss.
113           _archHandler.updateReferenceToGOT(ref, false);
114         } else {
115           // Replace the target with a reference to a GOT entry.
116           const DefinedAtom *gotEntry = makeGOTEntry(target);
117           const_cast<Reference *>(ref)->setTarget(gotEntry);
118           // Update reference kind to reflect that target is now a GOT entry.
119           _archHandler.updateReferenceToGOT(ref, true);
120         }
121       }
122     }
123 
124     // Sort and add all created GOT Atoms to master file
125     std::vector<const GOTEntryAtom *> entries;
126     entries.reserve(_targetToGOT.size());
127     for (auto &it : _targetToGOT)
128       entries.push_back(it.second);
129     std::sort(entries.begin(), entries.end(),
130               [](const GOTEntryAtom *left, const GOTEntryAtom *right) {
131       return (left->slotName().compare(right->slotName()) < 0);
132     });
133     for (const GOTEntryAtom *slot : entries)
134       mergedFile.addAtom(*slot);
135 
136     return llvm::Error::success();
137   }
138 
139   bool shouldReplaceTargetWithGOTAtom(const Atom *target, bool canBypassGOT) {
140     // Accesses to shared library symbols must go through GOT.
141     if (isa<SharedLibraryAtom>(target))
142       return true;
143     // Accesses to interposable symbols in same linkage unit must also go
144     // through GOT.
145     const DefinedAtom *defTarget = dyn_cast<DefinedAtom>(target);
146     if (defTarget != nullptr &&
147         defTarget->interposable() != DefinedAtom::interposeNo) {
148       assert(defTarget->scope() != DefinedAtom::scopeTranslationUnit);
149       return true;
150     }
151     // Target does not require indirection.  So, if instruction allows GOT to be
152     // by-passed, do that optimization and don't create GOT entry.
153     return !canBypassGOT;
154   }
155 
156   const DefinedAtom *makeGOTEntry(const Atom *target) {
157     auto pos = _targetToGOT.find(target);
158     if (pos == _targetToGOT.end()) {
159       auto *gotEntry = new (_file.allocator())
160           GOTEntryAtom(_file, _ctx.is64Bit(), target->name());
161       _targetToGOT[target] = gotEntry;
162       const ArchHandler::ReferenceInfo &nlInfo = _archHandler.stubInfo().
163                                                 nonLazyPointerReferenceToBinder;
164       gotEntry->addReference(Reference::KindNamespace::mach_o, nlInfo.arch,
165                              nlInfo.kind, 0, target, 0);
166       return gotEntry;
167     }
168     return pos->second;
169   }
170 
171   const MachOLinkingContext &_ctx;
172   mach_o::ArchHandler                             &_archHandler;
173   MachOFile                                       &_file;
174   llvm::DenseMap<const Atom*, const GOTEntryAtom*> _targetToGOT;
175 };
176 
177 void addGOTPass(PassManager &pm, const MachOLinkingContext &ctx) {
178   assert(ctx.needsGOTPass());
179   pm.add(llvm::make_unique<GOTPass>(ctx));
180 }
181 
182 } // end namesapce mach_o
183 } // end namesapce lld
184