1 //===-- MipsELFObjectWriter.cpp - Mips ELF Writer -------------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
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 "MCTargetDesc/MipsBaseInfo.h"
11 #include "MCTargetDesc/MipsFixupKinds.h"
12 #include "MCTargetDesc/MipsMCTargetDesc.h"
13 #include "llvm/ADT/STLExtras.h"
14 #include "llvm/MC/MCAssembler.h"
15 #include "llvm/MC/MCELFObjectWriter.h"
16 #include "llvm/MC/MCExpr.h"
17 #include "llvm/MC/MCSection.h"
18 #include "llvm/MC/MCSymbolELF.h"
19 #include "llvm/MC/MCValue.h"
20 #include "llvm/Support/ErrorHandling.h"
21 #include <list>
22 
23 using namespace llvm;
24 
25 namespace {
26 // A helper structure based on ELFRelocationEntry, used for sorting entries in
27 // the relocation table.
28 struct MipsRelocationEntry {
MipsRelocationEntry__anone750f2b90111::MipsRelocationEntry29   MipsRelocationEntry(const ELFRelocationEntry &R)
30       : R(R), SortOffset(R.Offset), HasMatchingHi(false) {}
31   const ELFRelocationEntry R;
32   // SortOffset equals R.Offset except for the *HI16 relocations, for which it
33   // will be set based on the R.Offset of the matching *LO16 relocation.
34   int64_t SortOffset;
35   // True when this is a *LO16 relocation chosen as a match for a *HI16
36   // relocation.
37   bool HasMatchingHi;
38 };
39 
40   class MipsELFObjectWriter : public MCELFObjectTargetWriter {
41   public:
42     MipsELFObjectWriter(bool _is64Bit, uint8_t OSABI,
43                         bool _isN64, bool IsLittleEndian);
44 
45     ~MipsELFObjectWriter() override;
46 
47     unsigned GetRelocType(const MCValue &Target, const MCFixup &Fixup,
48                           bool IsPCRel) const override;
49     bool needsRelocateWithSymbol(const MCSymbol &Sym,
50                                  unsigned Type) const override;
51     virtual void sortRelocs(const MCAssembler &Asm,
52                             std::vector<ELFRelocationEntry> &Relocs) override;
53   };
54 }
55 
MipsELFObjectWriter(bool _is64Bit,uint8_t OSABI,bool _isN64,bool IsLittleEndian)56 MipsELFObjectWriter::MipsELFObjectWriter(bool _is64Bit, uint8_t OSABI,
57                                          bool _isN64, bool IsLittleEndian)
58     : MCELFObjectTargetWriter(_is64Bit, OSABI, ELF::EM_MIPS,
59                               /*HasRelocationAddend*/ _isN64,
60                               /*IsN64*/ _isN64) {}
61 
~MipsELFObjectWriter()62 MipsELFObjectWriter::~MipsELFObjectWriter() {}
63 
GetRelocType(const MCValue & Target,const MCFixup & Fixup,bool IsPCRel) const64 unsigned MipsELFObjectWriter::GetRelocType(const MCValue &Target,
65                                            const MCFixup &Fixup,
66                                            bool IsPCRel) const {
67   // Determine the type of the relocation.
68   unsigned Kind = (unsigned)Fixup.getKind();
69 
70   switch (Kind) {
71   case Mips::fixup_Mips_NONE:
72     return ELF::R_MIPS_NONE;
73   case Mips::fixup_Mips_16:
74   case FK_Data_2:
75     return IsPCRel ? ELF::R_MIPS_PC16 : ELF::R_MIPS_16;
76   case Mips::fixup_Mips_32:
77   case FK_Data_4:
78     return IsPCRel ? ELF::R_MIPS_PC32 : ELF::R_MIPS_32;
79   }
80 
81   if (IsPCRel) {
82     switch (Kind) {
83     case Mips::fixup_Mips_Branch_PCRel:
84     case Mips::fixup_Mips_PC16:
85       return ELF::R_MIPS_PC16;
86     case Mips::fixup_MICROMIPS_PC7_S1:
87       return ELF::R_MICROMIPS_PC7_S1;
88     case Mips::fixup_MICROMIPS_PC10_S1:
89       return ELF::R_MICROMIPS_PC10_S1;
90     case Mips::fixup_MICROMIPS_PC16_S1:
91       return ELF::R_MICROMIPS_PC16_S1;
92     case Mips::fixup_MIPS_PC19_S2:
93       return ELF::R_MIPS_PC19_S2;
94     case Mips::fixup_MIPS_PC18_S3:
95       return ELF::R_MIPS_PC18_S3;
96     case Mips::fixup_MIPS_PC21_S2:
97       return ELF::R_MIPS_PC21_S2;
98     case Mips::fixup_MIPS_PC26_S2:
99       return ELF::R_MIPS_PC26_S2;
100     case Mips::fixup_MIPS_PCHI16:
101       return ELF::R_MIPS_PCHI16;
102     case Mips::fixup_MIPS_PCLO16:
103       return ELF::R_MIPS_PCLO16;
104     }
105 
106     llvm_unreachable("invalid PC-relative fixup kind!");
107   }
108 
109   switch (Kind) {
110   case Mips::fixup_Mips_64:
111   case FK_Data_8:
112     return ELF::R_MIPS_64;
113   case FK_GPRel_4:
114     if (isN64()) {
115       unsigned Type = (unsigned)ELF::R_MIPS_NONE;
116       Type = setRType((unsigned)ELF::R_MIPS_GPREL32, Type);
117       Type = setRType2((unsigned)ELF::R_MIPS_64, Type);
118       Type = setRType3((unsigned)ELF::R_MIPS_NONE, Type);
119       return Type;
120     }
121     return ELF::R_MIPS_GPREL32;
122   case Mips::fixup_Mips_GPREL16:
123     return ELF::R_MIPS_GPREL16;
124   case Mips::fixup_Mips_26:
125     return ELF::R_MIPS_26;
126   case Mips::fixup_Mips_CALL16:
127     return ELF::R_MIPS_CALL16;
128   case Mips::fixup_Mips_GOT_Global:
129   case Mips::fixup_Mips_GOT_Local:
130     return ELF::R_MIPS_GOT16;
131   case Mips::fixup_Mips_HI16:
132     return ELF::R_MIPS_HI16;
133   case Mips::fixup_Mips_LO16:
134     return ELF::R_MIPS_LO16;
135   case Mips::fixup_Mips_TLSGD:
136     return ELF::R_MIPS_TLS_GD;
137   case Mips::fixup_Mips_GOTTPREL:
138     return ELF::R_MIPS_TLS_GOTTPREL;
139   case Mips::fixup_Mips_TPREL_HI:
140     return ELF::R_MIPS_TLS_TPREL_HI16;
141   case Mips::fixup_Mips_TPREL_LO:
142     return ELF::R_MIPS_TLS_TPREL_LO16;
143   case Mips::fixup_Mips_TLSLDM:
144     return ELF::R_MIPS_TLS_LDM;
145   case Mips::fixup_Mips_DTPREL_HI:
146     return ELF::R_MIPS_TLS_DTPREL_HI16;
147   case Mips::fixup_Mips_DTPREL_LO:
148     return ELF::R_MIPS_TLS_DTPREL_LO16;
149   case Mips::fixup_Mips_GOT_PAGE:
150     return ELF::R_MIPS_GOT_PAGE;
151   case Mips::fixup_Mips_GOT_OFST:
152     return ELF::R_MIPS_GOT_OFST;
153   case Mips::fixup_Mips_GOT_DISP:
154     return ELF::R_MIPS_GOT_DISP;
155   case Mips::fixup_Mips_GPOFF_HI: {
156     unsigned Type = (unsigned)ELF::R_MIPS_NONE;
157     Type = setRType((unsigned)ELF::R_MIPS_GPREL16, Type);
158     Type = setRType2((unsigned)ELF::R_MIPS_SUB, Type);
159     Type = setRType3((unsigned)ELF::R_MIPS_HI16, Type);
160     return Type;
161   }
162   case Mips::fixup_Mips_GPOFF_LO: {
163     unsigned Type = (unsigned)ELF::R_MIPS_NONE;
164     Type = setRType((unsigned)ELF::R_MIPS_GPREL16, Type);
165     Type = setRType2((unsigned)ELF::R_MIPS_SUB, Type);
166     Type = setRType3((unsigned)ELF::R_MIPS_LO16, Type);
167     return Type;
168   }
169   case Mips::fixup_Mips_HIGHER:
170     return ELF::R_MIPS_HIGHER;
171   case Mips::fixup_Mips_HIGHEST:
172     return ELF::R_MIPS_HIGHEST;
173   case Mips::fixup_Mips_GOT_HI16:
174     return ELF::R_MIPS_GOT_HI16;
175   case Mips::fixup_Mips_GOT_LO16:
176     return ELF::R_MIPS_GOT_LO16;
177   case Mips::fixup_Mips_CALL_HI16:
178     return ELF::R_MIPS_CALL_HI16;
179   case Mips::fixup_Mips_CALL_LO16:
180     return ELF::R_MIPS_CALL_LO16;
181   case Mips::fixup_MICROMIPS_26_S1:
182     return ELF::R_MICROMIPS_26_S1;
183   case Mips::fixup_MICROMIPS_HI16:
184     return ELF::R_MICROMIPS_HI16;
185   case Mips::fixup_MICROMIPS_LO16:
186     return ELF::R_MICROMIPS_LO16;
187   case Mips::fixup_MICROMIPS_GOT16:
188     return ELF::R_MICROMIPS_GOT16;
189   case Mips::fixup_MICROMIPS_CALL16:
190     return ELF::R_MICROMIPS_CALL16;
191   case Mips::fixup_MICROMIPS_GOT_DISP:
192     return ELF::R_MICROMIPS_GOT_DISP;
193   case Mips::fixup_MICROMIPS_GOT_PAGE:
194     return ELF::R_MICROMIPS_GOT_PAGE;
195   case Mips::fixup_MICROMIPS_GOT_OFST:
196     return ELF::R_MICROMIPS_GOT_OFST;
197   case Mips::fixup_MICROMIPS_TLS_GD:
198     return ELF::R_MICROMIPS_TLS_GD;
199   case Mips::fixup_MICROMIPS_TLS_LDM:
200     return ELF::R_MICROMIPS_TLS_LDM;
201   case Mips::fixup_MICROMIPS_TLS_DTPREL_HI16:
202     return ELF::R_MICROMIPS_TLS_DTPREL_HI16;
203   case Mips::fixup_MICROMIPS_TLS_DTPREL_LO16:
204     return ELF::R_MICROMIPS_TLS_DTPREL_LO16;
205   case Mips::fixup_MICROMIPS_TLS_TPREL_HI16:
206     return ELF::R_MICROMIPS_TLS_TPREL_HI16;
207   case Mips::fixup_MICROMIPS_TLS_TPREL_LO16:
208     return ELF::R_MICROMIPS_TLS_TPREL_LO16;
209   }
210 
211   llvm_unreachable("invalid fixup kind!");
212 }
213 
214 // Sort entries by SortOffset in descending order.
215 // When there are more *HI16 relocs paired with one *LO16 reloc, the 2nd rule
216 // sorts them in ascending order of R.Offset.
cmpRelMips(const MipsRelocationEntry * AP,const MipsRelocationEntry * BP)217 static int cmpRelMips(const MipsRelocationEntry *AP,
218                       const MipsRelocationEntry *BP) {
219   const MipsRelocationEntry &A = *AP;
220   const MipsRelocationEntry &B = *BP;
221   if (A.SortOffset != B.SortOffset)
222     return B.SortOffset - A.SortOffset;
223   if (A.R.Offset != B.R.Offset)
224     return A.R.Offset - B.R.Offset;
225   if (B.R.Type != A.R.Type)
226     return B.R.Type - A.R.Type;
227   //llvm_unreachable("ELFRelocs might be unstable!");
228   return 0;
229 }
230 
231 // For the given Reloc.Type, return the matching relocation type, as in the
232 // table below.
getMatchingLoType(const MCAssembler & Asm,const ELFRelocationEntry & Reloc)233 static unsigned getMatchingLoType(const MCAssembler &Asm,
234                                   const ELFRelocationEntry &Reloc) {
235   unsigned Type = Reloc.Type;
236   if (Type == ELF::R_MIPS_HI16)
237     return ELF::R_MIPS_LO16;
238   if (Type == ELF::R_MICROMIPS_HI16)
239     return ELF::R_MICROMIPS_LO16;
240   if (Type == ELF::R_MIPS16_HI16)
241     return ELF::R_MIPS16_LO16;
242 
243   if (Reloc.Symbol->getBinding() != ELF::STB_LOCAL)
244     return ELF::R_MIPS_NONE;
245 
246   if (Type == ELF::R_MIPS_GOT16)
247     return ELF::R_MIPS_LO16;
248   if (Type == ELF::R_MICROMIPS_GOT16)
249     return ELF::R_MICROMIPS_LO16;
250   if (Type == ELF::R_MIPS16_GOT16)
251     return ELF::R_MIPS16_LO16;
252 
253   return ELF::R_MIPS_NONE;
254 }
255 
256 // Return true if First needs a matching *LO16, its matching *LO16 type equals
257 // Second's type and both relocations are against the same symbol.
areMatchingHiAndLo(const MCAssembler & Asm,const ELFRelocationEntry & First,const ELFRelocationEntry & Second)258 static bool areMatchingHiAndLo(const MCAssembler &Asm,
259                                const ELFRelocationEntry &First,
260                                const ELFRelocationEntry &Second) {
261   return getMatchingLoType(Asm, First) != ELF::R_MIPS_NONE &&
262          getMatchingLoType(Asm, First) == Second.Type &&
263          First.Symbol && First.Symbol == Second.Symbol;
264 }
265 
266 // Return true if MipsRelocs[Index] is a *LO16 preceded by a matching *HI16.
267 static bool
isPrecededByMatchingHi(const MCAssembler & Asm,uint32_t Index,std::vector<MipsRelocationEntry> & MipsRelocs)268 isPrecededByMatchingHi(const MCAssembler &Asm, uint32_t Index,
269                        std::vector<MipsRelocationEntry> &MipsRelocs) {
270   return Index < MipsRelocs.size() - 1 &&
271          areMatchingHiAndLo(Asm, MipsRelocs[Index + 1].R, MipsRelocs[Index].R);
272 }
273 
274 // Return true if MipsRelocs[Index] is a *LO16 not preceded by a matching *HI16
275 // and not chosen by a *HI16 as a match.
isFreeLo(const MCAssembler & Asm,uint32_t Index,std::vector<MipsRelocationEntry> & MipsRelocs)276 static bool isFreeLo(const MCAssembler &Asm, uint32_t Index,
277                      std::vector<MipsRelocationEntry> &MipsRelocs) {
278   return Index < MipsRelocs.size() && !MipsRelocs[Index].HasMatchingHi &&
279          !isPrecededByMatchingHi(Asm, Index, MipsRelocs);
280 }
281 
282 // Lo is chosen as a match for Hi, set their fields accordingly.
283 // Mips instructions have fixed length of at least two bytes (two for
284 // micromips/mips16, four for mips32/64), so we can set HI's SortOffset to
285 // matching LO's Offset minus one to simplify the sorting function.
setMatch(MipsRelocationEntry & Hi,MipsRelocationEntry & Lo)286 static void setMatch(MipsRelocationEntry &Hi, MipsRelocationEntry &Lo) {
287   Lo.HasMatchingHi = true;
288   Hi.SortOffset = Lo.R.Offset - 1;
289 }
290 
291 // We sort relocation table entries by offset, except for one additional rule
292 // required by MIPS ABI: every *HI16 relocation must be immediately followed by
293 // the corresponding *LO16 relocation. We also support a GNU extension that
294 // allows more *HI16s paired with one *LO16.
295 //
296 // *HI16 relocations and their matching *LO16 are:
297 //
298 // +---------------------------------------------+-------------------+
299 // |               *HI16                         |  matching *LO16   |
300 // |---------------------------------------------+-------------------|
301 // |  R_MIPS_HI16, local R_MIPS_GOT16            |    R_MIPS_LO16    |
302 // |  R_MICROMIPS_HI16, local R_MICROMIPS_GOT16  | R_MICROMIPS_LO16  |
303 // |  R_MIPS16_HI16, local R_MIPS16_GOT16        |  R_MIPS16_LO16    |
304 // +---------------------------------------------+-------------------+
305 //
306 // (local R_*_GOT16 meaning R_*_GOT16 against the local symbol.)
307 //
308 // To handle *HI16 and *LO16 relocations, the linker needs a combined addend
309 // ("AHL") calculated from both *HI16 ("AHI") and *LO16 ("ALO") relocations:
310 // AHL = (AHI << 16) + (short)ALO;
311 //
312 // We are reusing gnu as sorting algorithm so we are emitting the relocation
313 // table sorted the same way as gnu as would sort it, for easier comparison of
314 // the generated .o files.
315 //
316 // The logic is:
317 // search the table (starting from the highest offset and going back to zero)
318 // for all *HI16 relocations that don't have a matching *LO16.
319 // For every such HI, find a matching LO with highest offset that isn't already
320 // matched with another HI. If there are no free LOs, match it with the first
321 // found (starting from lowest offset).
322 // When there are more HIs matched with one LO, sort them in descending order by
323 // offset.
324 //
325 // In other words, when searching for a matching LO:
326 // - don't look for a 'better' match for the HIs that are already followed by a
327 //   matching LO;
328 // - prefer LOs without a pair;
329 // - prefer LOs with higher offset;
330 
cmpRel(const ELFRelocationEntry * AP,const ELFRelocationEntry * BP)331 static int cmpRel(const ELFRelocationEntry *AP, const ELFRelocationEntry *BP) {
332   const ELFRelocationEntry &A = *AP;
333   const ELFRelocationEntry &B = *BP;
334   if (A.Offset != B.Offset)
335     return B.Offset - A.Offset;
336   if (B.Type != A.Type)
337     return A.Type - B.Type;
338   return 0;
339 }
340 
sortRelocs(const MCAssembler & Asm,std::vector<ELFRelocationEntry> & Relocs)341 void MipsELFObjectWriter::sortRelocs(const MCAssembler &Asm,
342                                      std::vector<ELFRelocationEntry> &Relocs) {
343   if (Relocs.size() < 2)
344     return;
345 
346   // Sorts entries by Offset in descending order.
347   array_pod_sort(Relocs.begin(), Relocs.end(), cmpRel);
348 
349   // Init MipsRelocs from Relocs.
350   std::vector<MipsRelocationEntry> MipsRelocs;
351   for (unsigned I = 0, E = Relocs.size(); I != E; ++I)
352     MipsRelocs.push_back(MipsRelocationEntry(Relocs[I]));
353 
354   // Find a matching LO for all HIs that need it.
355   for (int32_t I = 0, E = MipsRelocs.size(); I != E; ++I) {
356     if (getMatchingLoType(Asm, MipsRelocs[I].R) == ELF::R_MIPS_NONE ||
357         (I > 0 && isPrecededByMatchingHi(Asm, I - 1, MipsRelocs)))
358       continue;
359 
360     int32_t MatchedLoIndex = -1;
361 
362     // Search the list in the ascending order of Offset.
363     for (int32_t J = MipsRelocs.size() - 1, N = -1; J != N; --J) {
364       // check for a match
365       if (areMatchingHiAndLo(Asm, MipsRelocs[I].R, MipsRelocs[J].R) &&
366           (MatchedLoIndex == -1 || // first match
367            // or we already have a match,
368            // but this one is with higher offset and it's free
369            (MatchedLoIndex > J && isFreeLo(Asm, J, MipsRelocs))))
370         MatchedLoIndex = J;
371     }
372 
373     if (MatchedLoIndex != -1)
374       // We have a match.
375       setMatch(MipsRelocs[I], MipsRelocs[MatchedLoIndex]);
376   }
377 
378   // SortOffsets are calculated, call the sorting function.
379   array_pod_sort(MipsRelocs.begin(), MipsRelocs.end(), cmpRelMips);
380 
381   // Copy sorted MipsRelocs back to Relocs.
382   for (unsigned I = 0, E = MipsRelocs.size(); I != E; ++I)
383     Relocs[I] = MipsRelocs[I].R;
384 }
385 
needsRelocateWithSymbol(const MCSymbol & Sym,unsigned Type) const386 bool MipsELFObjectWriter::needsRelocateWithSymbol(const MCSymbol &Sym,
387                                                   unsigned Type) const {
388   // FIXME: This is extremely conservative. This really needs to use a
389   // whitelist with a clear explanation for why each realocation needs to
390   // point to the symbol, not to the section.
391   switch (Type) {
392   default:
393     return true;
394 
395   case ELF::R_MIPS_GOT16:
396   case ELF::R_MIPS16_GOT16:
397   case ELF::R_MICROMIPS_GOT16:
398     llvm_unreachable("Should have been handled already");
399 
400   // These relocations might be paired with another relocation. The pairing is
401   // done by the static linker by matching the symbol. Since we only see one
402   // relocation at a time, we have to force them to relocate with a symbol to
403   // avoid ending up with a pair where one points to a section and another
404   // points to a symbol.
405   case ELF::R_MIPS_HI16:
406   case ELF::R_MIPS16_HI16:
407   case ELF::R_MICROMIPS_HI16:
408   case ELF::R_MIPS_LO16:
409   case ELF::R_MIPS16_LO16:
410   case ELF::R_MICROMIPS_LO16:
411     return true;
412 
413   case ELF::R_MIPS_32:
414     if (cast<MCSymbolELF>(Sym).getOther() & ELF::STO_MIPS_MICROMIPS)
415       return true;
416     // falltrough
417   case ELF::R_MIPS_26:
418   case ELF::R_MIPS_64:
419   case ELF::R_MIPS_GPREL16:
420     return false;
421   }
422 }
423 
createMipsELFObjectWriter(raw_pwrite_stream & OS,uint8_t OSABI,bool IsLittleEndian,bool Is64Bit)424 MCObjectWriter *llvm::createMipsELFObjectWriter(raw_pwrite_stream &OS,
425                                                 uint8_t OSABI,
426                                                 bool IsLittleEndian,
427                                                 bool Is64Bit) {
428   MCELFObjectTargetWriter *MOTW =
429       new MipsELFObjectWriter(Is64Bit, OSABI, Is64Bit, IsLittleEndian);
430   return createELFObjectWriter(MOTW, OS, IsLittleEndian);
431 }
432