[WebAssembly] Check if the section order is correct

[aheejin]

Summary

This patch checks if the section order is correct when reading a wasm
object file in WasmObjectFile and converting YAML to wasm object in
yaml2wasm. (It is not possible to check when reading YAML because it is
handled exclusively by the YAML reader.)

This checks the ordering of all known sections (core sections + known
custom sections). This also adds section ID DataCount section that will
be scheduled to be added in near future.

[aheejin]

• Change function name + add comments

[aheejin]

• Comment fix

[sbc100]

For reference there was a previous CL that tries to do something similar: https://reviews.llvm.org/D44024.

[aheejin]

I see.. so why wasn't it landed? It says it was stalled because we couldn't decide whether or how to check custom section orderings and orderings between custom section vs. normal sections. Do we now have consensus on that? If so landing that CL makes more sense. If not, do you think now is a good time to re-discuss it? Or would landing this CL first and decide what to do with custom sections later makes sense?

The main motivation for this CL was, I had to delete code that was previously checking relative section orders in yaml2wasm because the previous code only checked if the section codes were monotonically increasing and the new event section had code 12, and you suggested we should reinstate it in a separate CL.

[sbc100]

In D54924#1310734, @aheejin wrote:

I see.. so why wasn't it landed? It says it was stalled because we couldn't decide whether or how to check custom section orderings and orderings between custom section vs. normal sections. Do we now have consensus on that? If so landing that CL makes more sense. If not, do you think now is a good time to re-discuss it? Or would landing this CL first and decide what to do with custom sections later makes sense?

The main motivation for this CL was, I had to delete code that was previously checking relative section orders in yaml2wasm because the previous code only checked if the section codes were monotonically increasing and the new event section had code 12, and you suggested we should reinstate it in a separate CL.

I don't feel super strongly about it, but for completeness we do need to include custom sections in the ordering I think.

IIRC, I think i was hoping there would be a simpler way to do that the method proposed in D44024 but maybe t here isn't.

BTW, Is there any reason you decided to do this in libBinaryFormat over libObject?

[aheejin]

D44024 is not simpler; actually it is more complicated because it checks more things than this, such as custom sections and whether the function section matches with the code section. If you think we should also include custom section checking in this CL, why don't we just land D44024?

The reason I added that in BinaryFormat is it uses wasm namespace while Object uses object namespace. I wanted put isValidSectionOrder function within wasm namespace.

[sbc100]

In D54924#1310780, @aheejin wrote:

D44024 is not simpler; actually it is more complicated because it checks more things than this, such as custom sections and whether the function section matches with the code section. If you think we should also include custom section checking in this CL, why don't we just land D44024?

Sure I'd be happy to see D44024 resurrected. I'll ping ncw@ and see if he has cycles to do that.

The reason I added that in BinaryFormat is it uses wasm namespace while Object uses object namespace. I wanted put isValidSectionOrder function within wasm namespace.

Right, but there is plenty of wasm-speciifc code in the object namespace. The code for wasm object file parsing, etc all lives in the object::WasmObjectFile() class. Its not clear to me in this case what the best home for such a function is.

[aheejin]

• Add custom section checking

[aheejin]

Also moved the checker to lib/Object.

include/llvm/Object/Wasm.h

311 ↗

(On Diff #177817)

I copied this comments on orders (linking section should be after data section and reloc sections should be after linking section) from D44024. Are these still valid? If so, do you think we should specify them in Linking spec?

[aheejin]

• Remove unused code

[aheejin]

include/llvm/Object/Wasm.h

311 ↗

(On Diff #177817)

Oh after deleting some code the comment location got weird. What I meant was the comments about relationship of data - "reloc" and "reloc" - "linking".

[aheejin]

Ping

[sbc100]

lib/Object/WasmObjectFile.cpp

278 ↗

(On Diff #177821)

If this is only passing the section type, not the section name, I can't see how it can check the ordering for custom sections?

Should we move this change down in "parseSection" so it can access the name and ID of custom sections?

1454 ↗

(On Diff #177821)

We also have "dylink" section which must come first before any other section.

tools/yaml2obj/CMakeLists.txt

2 ↗

(On Diff #177821)

Is this change still needed?

[aheejin]

include/llvm/Object/Wasm.h

311 ↗

(On Diff #177817)

Are these explanations about data - "reloc" and "reloc" - "linking" ordering still correct?

lib/Object/WasmObjectFile.cpp

278 ↗

(On Diff #177821)

Oh right, I forgot that... Moved the checking code into readSection. And also fixed it in yaml2wasm side too, in which case I didn't need to move the checking code into a function though.

tools/yaml2obj/CMakeLists.txt

2 ↗

(On Diff #177821)

Nope. Deleted it, thanks.

[aheejin]

• Address comments

[aheejin]

• Delete unused peakUint8

[sbc100]

include/llvm/Object/Wasm.h

311 ↗

(On Diff #177817)

Yup. They seem correct to me.

llvm/trunk/include/llvm/BinaryFormat/Wasm.h

 struct WasmLinkingData {
   uint32_t Version;
   std::vector<WasmInitFunc> InitFunctions;
   std::vector<StringRef> Comdats;
   std::vector<WasmSymbolInfo> SymbolTable;
 };
 
 enum : unsigned {
-  WASM_SEC_CUSTOM = 0,   // Custom / User-defined section
-  WASM_SEC_TYPE = 1,     // Function signature declarations
-  WASM_SEC_IMPORT = 2,   // Import declarations
-  WASM_SEC_FUNCTION = 3, // Function declarations
-  WASM_SEC_TABLE = 4,    // Indirect function table and other tables
-  WASM_SEC_MEMORY = 5,   // Memory attributes
-  WASM_SEC_GLOBAL = 6,   // Global declarations
-  WASM_SEC_EXPORT = 7,   // Exports
-  WASM_SEC_START = 8,    // Start function declaration
-  WASM_SEC_ELEM = 9,     // Elements section
-  WASM_SEC_CODE = 10,    // Function bodies (code)
-  WASM_SEC_DATA = 11,    // Data segments
-  WASM_SEC_EVENT = 13    // Event declarations
+  WASM_SEC_CUSTOM = 0,     // Custom / User-defined section
+  WASM_SEC_TYPE = 1,       // Function signature declarations
+  WASM_SEC_IMPORT = 2,     // Import declarations
+  WASM_SEC_FUNCTION = 3,   // Function declarations
+  WASM_SEC_TABLE = 4,      // Indirect function table and other tables
+  WASM_SEC_MEMORY = 5,     // Memory attributes
+  WASM_SEC_GLOBAL = 6,     // Global declarations
+  WASM_SEC_EXPORT = 7,     // Exports
+  WASM_SEC_START = 8,      // Start function declaration
+  WASM_SEC_ELEM = 9,       // Elements section
+  WASM_SEC_CODE = 10,      // Function bodies (code)
+  WASM_SEC_DATA = 11,      // Data segments
+  WASM_SEC_DATACOUNT = 12, // Data segment count
+  WASM_SEC_EVENT = 13      // Event declarations
 };
 
 // Type immediate encodings used in various contexts.
 enum : unsigned {
   WASM_TYPE_I32 = 0x7F,
   WASM_TYPE_I64 = 0x7E,
   WASM_TYPE_F32 = 0x7D,
   WASM_TYPE_F64 = 0x7C,

llvm/trunk/include/llvm/Object/Wasm.h

private:
   uint32_t NumImportedFunctions = 0;
   uint32_t NumImportedEvents = 0;
   uint32_t CodeSection = 0;
   uint32_t DataSection = 0;
   uint32_t GlobalSection = 0;
   uint32_t EventSection = 0;
 };
 
+class WasmSectionOrderChecker {
+public:
+  // We define orders for all core wasm sections and known custom sections.
+  enum : int {
+    // Core sections
+    // The order of standard sections is precisely given by the spec.
+    WASM_SEC_ORDER_TYPE = 1,
+    WASM_SEC_ORDER_IMPORT = 2,
+    WASM_SEC_ORDER_FUNCTION = 3,
+    WASM_SEC_ORDER_TABLE = 4,
+    WASM_SEC_ORDER_MEMORY = 5,
+    WASM_SEC_ORDER_GLOBAL = 6,
+    WASM_SEC_ORDER_EVENT = 7,
+    WASM_SEC_ORDER_EXPORT = 8,
+    WASM_SEC_ORDER_START = 9,
+    WASM_SEC_ORDER_ELEM = 10,
+    WASM_SEC_ORDER_DATACOUNT = 11,
+    WASM_SEC_ORDER_CODE = 12,
+    WASM_SEC_ORDER_DATA = 13,
+
+    // Custom sections
+    // "dylink" should be the very first section in the module
+    WASM_SEC_ORDER_DYLINK = 0,
+    // "linking" section requires DATA section in order to validate data symbols
+    WASM_SEC_ORDER_LINKING = 100,
+    // Must come after "linking" section in order to validate reloc indexes.
+    WASM_SEC_ORDER_RELOC = 101,
+    // "name" section must appear after DATA. Comes after "linking" to allow
+    // symbol table to set default function name.
+    WASM_SEC_ORDER_NAME = 102,
+    // "producers" section must appear after "name" section.
+    WASM_SEC_ORDER_PRODUCERS = 103
+  };
+
+  bool isValidSectionOrder(unsigned ID, StringRef CustomSectionName = "");
+
+private:
+  int LastOrder = -1; // Lastly seen known section's order
+
+  // Returns -1 for unknown sections.
+  int getSectionOrder(unsigned ID, StringRef CustomSectionName = "");
+};
+
 } // end namespace object
 
 inline raw_ostream &operator<<(raw_ostream &OS, const object::WasmSymbol &Sym) {
   Sym.print(OS);
   return OS;
 }
 
 } // end namespace llvm
 
 #endif // LLVM_OBJECT_WASM_H

llvm/trunk/lib/Object/WasmObjectFile.cpp

 #include "llvm/Object/Error.h"
 #include "llvm/Object/ObjectFile.h"
 #include "llvm/Object/SymbolicFile.h"
 #include "llvm/Object/Wasm.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/LEB128.h"
+#include "llvm/Support/ScopedPrinter.h"
 #include <algorithm>
 #include <cassert>
 #include <cstdint>
 #include <cstring>
 #include <system_error>
 
 #define DEBUG_TYPE "wasm-object"
 

 
 static wasm::WasmTable readTable(WasmObjectFile::ReadContext &Ctx) {
   wasm::WasmTable Table;
   Table.ElemType = readUint8(Ctx);
   Table.Limits = readLimits(Ctx);
   return Table;
 }
 
-static Error readSection(WasmSection &Section,
-                         WasmObjectFile::ReadContext &Ctx) {
+static Error readSection(WasmSection &Section, WasmObjectFile::ReadContext &Ctx,
+                         WasmSectionOrderChecker &Checker) {
   Section.Offset = Ctx.Ptr - Ctx.Start;
   Section.Type = readUint8(Ctx);
   LLVM_DEBUG(dbgs() << "readSection type=" << Section.Type << "\n");
   uint32_t Size = readVaruint32(Ctx);
   if (Size == 0)
     return make_error<StringError>("Zero length section",
                                    object_error::parse_failed);
   if (Ctx.Ptr + Size > Ctx.End)
     return make_error<StringError>("Section too large",
                                    object_error::parse_failed);
   if (Section.Type == wasm::WASM_SEC_CUSTOM) {
     WasmObjectFile::ReadContext SectionCtx;
     SectionCtx.Start = Ctx.Ptr;
     SectionCtx.Ptr = Ctx.Ptr;
     SectionCtx.End = Ctx.Ptr + Size;
 
     Section.Name = readString(SectionCtx);
 
     uint32_t SectionNameSize = SectionCtx.Ptr - SectionCtx.Start;
     Ctx.Ptr += SectionNameSize;
     Size -= SectionNameSize;
   }
+
+  if (!Checker.isValidSectionOrder(Section.Type, Section.Name)) {
+    return make_error<StringError>("Out of order section type: " +
+                                       llvm::to_string(Section.Type),
+                                   object_error::parse_failed);
+  }
+
   Section.Content = ArrayRef<uint8_t>(Ctx.Ptr, Size);
   Ctx.Ptr += Size;
   return Error::success();
 }
 
 WasmObjectFile::WasmObjectFile(MemoryBufferRef Buffer, Error &Err)
     : ObjectFile(Binary::ID_Wasm, Buffer) {
   ErrorAsOutParameter ErrAsOutParam(&Err);
WasmObjectFile::WasmObjectFile(MemoryBufferRef Buffer, Error &Err)
   Header.Version = readUint32(Ctx);
   if (Header.Version != wasm::WasmVersion) {
     Err = make_error<StringError>("Bad version number",
                                   object_error::parse_failed);
     return;
   }
 
   WasmSection Sec;
+  WasmSectionOrderChecker Checker;
   while (Ctx.Ptr < Ctx.End) {
-    if ((Err = readSection(Sec, Ctx)))
+    if ((Err = readSection(Sec, Ctx, Checker)))
       return;
     if ((Err = parseSection(Sec)))
       return;
 
     Sections.push_back(Sec);
   }
 }
 

 
 const wasm::WasmRelocation &
 WasmObjectFile::getWasmRelocation(DataRefImpl Ref) const {
   assert(Ref.d.a < Sections.size());
   const WasmSection &Sec = Sections[Ref.d.a];
   assert(Ref.d.b < Sec.Relocations.size());
   return Sec.Relocations[Ref.d.b];
 }
+
+int WasmSectionOrderChecker::getSectionOrder(unsigned ID,
+                                             StringRef CustomSectionName) {
+  switch (ID) {
+  case wasm::WASM_SEC_CUSTOM:
+    return StringSwitch<unsigned>(CustomSectionName)
+        .Case("dylink", WASM_SEC_ORDER_DYLINK)
+        .Case("linking", WASM_SEC_ORDER_LINKING)
+        .StartsWith("reloc.", WASM_SEC_ORDER_RELOC)
+        .Case("name", WASM_SEC_ORDER_NAME)
+        .Case("producers", WASM_SEC_ORDER_PRODUCERS)
+        .Default(-1);
+  case wasm::WASM_SEC_TYPE:
+    return WASM_SEC_ORDER_TYPE;
+  case wasm::WASM_SEC_IMPORT:
+    return WASM_SEC_ORDER_IMPORT;
+  case wasm::WASM_SEC_FUNCTION:
+    return WASM_SEC_ORDER_FUNCTION;
+  case wasm::WASM_SEC_TABLE:
+    return WASM_SEC_ORDER_TABLE;
+  case wasm::WASM_SEC_MEMORY:
+    return WASM_SEC_ORDER_MEMORY;
+  case wasm::WASM_SEC_GLOBAL:
+    return WASM_SEC_ORDER_GLOBAL;
+  case wasm::WASM_SEC_EXPORT:
+    return WASM_SEC_ORDER_EXPORT;
+  case wasm::WASM_SEC_START:
+    return WASM_SEC_ORDER_START;
+  case wasm::WASM_SEC_ELEM:
+    return WASM_SEC_ORDER_ELEM;
+  case wasm::WASM_SEC_CODE:
+    return WASM_SEC_ORDER_CODE;
+  case wasm::WASM_SEC_DATA:
+    return WASM_SEC_ORDER_DATA;
+  case wasm::WASM_SEC_DATACOUNT:
+    return WASM_SEC_ORDER_DATACOUNT;
+  case wasm::WASM_SEC_EVENT:
+    return WASM_SEC_ORDER_EVENT;
+  default:
+    llvm_unreachable("invalid section");
+  }
+}
+
+bool WasmSectionOrderChecker::isValidSectionOrder(unsigned ID,
+                                                  StringRef CustomSectionName) {
+  int Order = getSectionOrder(ID, CustomSectionName);
+  if (Order == -1) // Skip unknown sections
+    return true;
+  // There can be multiple "reloc." sections. Otherwise there shouldn't be any
+  // duplicate section orders.
+  bool IsValid = (LastOrder == Order && Order == WASM_SEC_ORDER_RELOC) ||
+                 LastOrder < Order;
+  LastOrder = Order;
+  return IsValid;
+}

llvm/trunk/test/Object/wasm-invalid-section-order.test

+# RUN: not obj2yaml %p/Inputs/WASM/invalid-section-order.wasm 2>&1 | FileCheck %s
+# CHECK: {{.*}}: Out of order section type: 10
+
+# Inputs/WASM/invalid-section-order.wasm is generated from this ll file, by
+# modifying WasmObjectWriter to incorrectly write the data section before the
+# code section.
+#
+# target datalayout = "e-m:e-p:32:32-i64:64-n32:64-S128"
+# target triple = "wasm32-unknown-unknown"
+#
+# @data = global i32 0, align 4
+#
+# define void @foo() {
+# entry:
+#   ret void
+# }

llvm/trunk/test/ObjectYAML/wasm/invalid_section_order.yaml

+# RUN: not yaml2obj %s -o /dev/null 2>&1 | FileCheck %s
+
+--- !WASM
+FileHeader:
+  Version:         0x00000001
+Sections:
+  - Type:            TYPE
+    Signatures:
+      - Index:           0
+        ReturnType:      NORESULT
+        ParamTypes:      []
+  - Type:            CODE
+    Functions:
+      - Index:           0
+        Locals:          []
+        Body:            0B
+  # CHECK: Out of order section type: 3
+  - Type:            FUNCTION
+    FunctionTypes:   [ 0 ]
+...

llvm/trunk/tools/yaml2obj/yaml2wasm.cpp

 //===- yaml2wasm - Convert YAML to a Wasm object file --------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
 /// The Wasm component of yaml2obj.
 ///
 //===----------------------------------------------------------------------===//
 //
 
+#include "llvm/Object/Wasm.h"
 #include "llvm/ObjectYAML/ObjectYAML.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/LEB128.h"
 
 using namespace llvm;
 
 /// This parses a yaml stream that represents a Wasm object file.
 /// See docs/yaml2obj for the yaml scheema.

 }
 
 int WasmWriter::writeWasm(raw_ostream &OS) {
   // Write headers
   OS.write(wasm::WasmMagic, sizeof(wasm::WasmMagic));
   writeUint32(OS, Obj.Header.Version);
 
   // Write each section
+  llvm::object::WasmSectionOrderChecker Checker;
   for (const std::unique_ptr<WasmYAML::Section> &Sec : Obj.Sections) {
+    StringRef SecName = "";
+    if (auto S = dyn_cast<WasmYAML::CustomSection>(Sec.get()))
+      SecName = S->Name;
+    if (!Checker.isValidSectionOrder(Sec->Type, SecName)) {
+      errs() << "Out of order section type: " << Sec->Type << "\n";
+      return 1;
+    }
     encodeULEB128(Sec->Type, OS);
     std::string OutString;
     raw_string_ostream StringStream(OutString);
     if (auto S = dyn_cast<WasmYAML::CustomSection>(Sec.get())) {
       if (auto Err = writeSectionContent(StringStream, *S))
         return Err;
     } else if (auto S = dyn_cast<WasmYAML::TypeSection>(Sec.get())) {
       if (auto Err = writeSectionContent(StringStream, *S))