[WebAssembly] Ensure relocation entries are ordered by offset

[ncw]

Looks good to me. I think something similar to this was included in one of my previous patches, and just got lost somewhere.

I'm busy on other things at work, so I've had to put Wasm to the side for the last few months, but I'm hoping to get back to polishing and submitting some more stuff - when I'm able!

lib/MC/WasmObjectWriter.cpp

918–922

Should this be stable_sort? (I think LLVM is trying to remove uses of the unstable/non-deterministic version.)

Alternatively could assert that it's sorted, since it seems in practice that it is (and the assert would make sure that stays the case).

[sbc100]

• fixup
• stable_sort

lib/MC/WasmObjectWriter.cpp

918–922

I tracked down some cases where its not ordered.

The issue is that we order the function according to the order of the Asm.symbols() list, an not the order of the sections in Asm. If we followed the sections order (I wrote a patch for this to confirm) we would most likely be ordered in most cases today, but I'm not sure that is guaranteed anywhere in LLVM. So I think certainly now we need to sort. Other plaforms do this reloc sorting too. See MCELFObjectTargetWriter::sortRelocs

lib/MC/WasmObjectWriter.cpp

private:
   void writeFunctionSection(ArrayRef<WasmFunction> Functions);
   void writeGlobalSection();
   void writeExportSection(ArrayRef<wasm::WasmExport> Exports);
   void writeElemSection(ArrayRef<uint32_t> TableElems);
   void writeCodeSection(const MCAssembler &Asm, const MCAsmLayout &Layout,
                         ArrayRef<WasmFunction> Functions);
   void writeDataSection();
   void writeRelocSection(uint32_t SectionIndex, StringRef Name,
-                         ArrayRef<WasmRelocationEntry> Relocations);
+                         std::vector<WasmRelocationEntry>& Relocations);
   void writeLinkingMetaDataSection(
       ArrayRef<wasm::WasmSymbolInfo> SymbolInfos,
       ArrayRef<std::pair<uint16_t, uint32_t>> InitFuncs,
       const std::map<StringRef, std::vector<WasmComdatEntry>> &Comdats);
   void writeCustomSections(const MCAssembler &Asm, const MCAsmLayout &Layout);
   void writeCustomRelocSections();
   void
   updateCustomSectionRelocations(const SmallVector<WasmFunction, 4> &Functions,
void WasmObjectWriter::writeDataSection() {
   // Apply fixups.
   applyRelocations(DataRelocations, Section.ContentsOffset);
 
   endSection(Section);
 }
 
 void WasmObjectWriter::writeRelocSection(
     uint32_t SectionIndex, StringRef Name,
-    ArrayRef<WasmRelocationEntry> Relocations) {
+    std::vector<WasmRelocationEntry>& Relocs) {
   // See: https://github.com/WebAssembly/tool-conventions/blob/master/Linking.md
   // for descriptions of the reloc sections.
 
-  if (Relocations.empty())
+  if (Relocs.empty())
     return;
 
+  // First, ensure the relocations are sorted in offset order.  In general they
+  // should already be sorted since `recordRelocation` is called in offset
+  // order, but for the code section we combine many MC sections into single
+  // wasm section, and this order is determined by the order of Asm.Symbols()
+  // not the sections order.
+  std::stable_sort(
+      Relocs.begin(), Relocs.end(),
+      [](const WasmRelocationEntry &A, const WasmRelocationEntry &B) {
+        return (A.Offset + A.FixupSection->getSectionOffset()) <
+               (B.Offset + B.FixupSection->getSectionOffset());
+      });
+
   SectionBookkeeping Section;
   startCustomSection(Section, std::string("reloc.") + Name.str());
 
   encodeULEB128(SectionIndex, W.OS);
-  encodeULEB128(Relocations.size(), W.OS);
-  for (const WasmRelocationEntry& RelEntry : Relocations) {
+  encodeULEB128(Relocs.size(), W.OS);
+  for (const WasmRelocationEntry& RelEntry : Relocs) {
     uint64_t Offset = RelEntry.Offset +
                       RelEntry.FixupSection->getSectionOffset();
     uint32_t Index = getRelocationIndexValue(RelEntry);
 
     W.OS << char(RelEntry.Type);
     encodeULEB128(Offset, W.OS);
     encodeULEB128(Index, W.OS);
     if (RelEntry.hasAddend())
       encodeSLEB128(RelEntry.Addend, W.OS);
   }
 

lib/Object/WasmObjectFile.cpp

 Error WasmObjectFile::parseRelocSection(StringRef Name, ReadContext &Ctx) {
   uint32_t SectionIndex = readVaruint32(Ctx);
   if (SectionIndex >= Sections.size())
     return make_error<GenericBinaryError>("Invalid section index",
                                           object_error::parse_failed);
   WasmSection& Section = Sections[SectionIndex];
   uint32_t RelocCount = readVaruint32(Ctx);
   uint32_t EndOffset = Section.Content.size();
+  uint32_t PreviousOffset = 0;
   while (RelocCount--) {
     wasm::WasmRelocation Reloc = {};
     Reloc.Type = readVaruint32(Ctx);
     Reloc.Offset = readVaruint32(Ctx);
+    if (Reloc.Offset < PreviousOffset)
+      return make_error<GenericBinaryError>("Relocations not in offset order",
+                                            object_error::parse_failed);
+    PreviousOffset = Reloc.Offset;
     Reloc.Index = readVaruint32(Ctx);
     switch (Reloc.Type) {
     case wasm::R_WEBASSEMBLY_FUNCTION_INDEX_LEB:
     case wasm::R_WEBASSEMBLY_TABLE_INDEX_SLEB:
     case wasm::R_WEBASSEMBLY_TABLE_INDEX_I32:
       if (!isValidFunctionSymbol(Reloc.Index))
         return make_error<GenericBinaryError>("Bad relocation function index",
                                               object_error::parse_failed);