[WebAssembly] Generalize section ordering constraints

[tlively]

Summary

Changes from using a total ordering of known sections to using a
dependency graph approach. This allows our tools to accept and process
binaries that are compliant with the spec and tool conventions that
would have been previously rejected. It also means our own tools can
do less work to enforce an artificially imposed ordering. Using a
general mechanism means fewer special cases and exceptions in the
ordering logic.

[sbc100]

When we discussed this before @binji and others argued that a total ordering made more sense.

llvm/test/MC/WebAssembly/relocs_and_producers.ll

1 ↗

(On Diff #187104)

Would it make sense to have the yaml checked in here directly and skip llc? I think you can be explicit about the ordering of the sections in the input if the test is yaml.

[tlively]

• Switch .ll test to .yaml and move to test/Object directory

[tlively]

In D58312#1400104, @sbc100 wrote:

When we discussed this before @binji and others argued that a total ordering made more sense.

What made me think this was a good idea was that I discovered that yaml2obj was not respecting the total ordering in its output by emitting relocations after the producers section. Fixing the total ordering logic to selectively ignore the producers section in some contexts seemed hacky and changing the yaml2obj logic seemed like letting section ordering complexity creep into unrelated code. That being said, I don't want to rehash old conversations pointlessly, so I'm happy to fix yaml2obj instead of making this change if that's what people want.

llvm/test/MC/WebAssembly/relocs_and_producers.ll

1 ↗

(On Diff #187104)

Yes, making the test text yaml at least reduces the number of tool invocations. The yaml does not have a separate section for the relocations, though, so I can't be explicit about the ordering.

[sbc100]

In D58312#1400234, @tlively wrote:

In D58312#1400104, @sbc100 wrote:

When we discussed this before @binji and others argued that a total ordering made more sense.

What made me think this was a good idea was that I discovered that yaml2obj was not respecting the total ordering in its output by emitting relocations after the producers section. Fixing the total ordering logic to selectively ignore the producers section in some contexts seemed hacky and changing the yaml2obj logic seemed like letting section ordering complexity creep into unrelated code. That being said, I don't want to rehash old conversations pointlessly, so I'm happy to fix yaml2obj instead of making this change if that's what people want.

I think I argued for doing it this way at the time too, I'm just making sure that we get buy in from those who argued for the total ordering before making this change.

[binji]

Yeah, I'd still prefer to have a total order if that's not too much effort. The alternative introduces a lot of potential complexity into the consumer, since we'll have a combinatorial explosion of possibilities for where these sections can be located, many of which will likely be untested.

[tlively]

In D58312#1402683, @binji wrote:

Yeah, I'd still prefer to have a total order if that's not too much effort. The alternative introduces a lot of potential complexity into the consumer, since we'll have a combinatorial explosion of possibilities for where these sections can be located, many of which will likely be untested.

I definitely want to reduce overall complexity, not increase it. My assumption is that if consumer code would be simplified by guaranteeing that section A is before section B, then the DAG ordering should be updated to make that ordering required. Sections should only be unordered with respect to each other if consumers are truly agnostic to their order.

In this case, producer code was able to be simplified by loosening the ordering constraints with no corresponding complications in consumer code that I am aware of. @binji, does this seem reasonable? Are there potential complications that I am missing?

[binji]

In D58312#1402909, @tlively wrote:

In D58312#1402683, @binji wrote:

Yeah, I'd still prefer to have a total order if that's not too much effort. The alternative introduces a lot of potential complexity into the consumer, since we'll have a combinatorial explosion of possibilities for where these sections can be located, many of which will likely be untested.

I definitely want to reduce overall complexity, not increase it. My assumption is that if consumer code would be simplified by guaranteeing that section A is before section B, then the DAG ordering should be updated to make that ordering required. Sections should only be unordered with respect to each other if consumers are truly agnostic to their order.

In this case, producer code was able to be simplified by loosening the ordering constraints with no corresponding complications in consumer code that I am aware of. @binji, does this seem reasonable? Are there potential complications that I am missing?

I'm suggesting that we provided an ordering even between sections that otherwise have no constraints, similar to the rest of the wasm format. There's no requirement that the custom sections have an ordering, but I'm worried that we'll end up with consistency issues like we did with the name section (before it was spec'd as being required after the data section).

[tlively]

In D58312#1402917, @binji wrote:

In D58312#1402909, @tlively wrote:

In D58312#1402683, @binji wrote:

Yeah, I'd still prefer to have a total order if that's not too much effort. The alternative introduces a lot of potential complexity into the consumer, since we'll have a combinatorial explosion of possibilities for where these sections can be located, many of which will likely be untested.

I definitely want to reduce overall complexity, not increase it. My assumption is that if consumer code would be simplified by guaranteeing that section A is before section B, then the DAG ordering should be updated to make that ordering required. Sections should only be unordered with respect to each other if consumers are truly agnostic to their order.

In this case, producer code was able to be simplified by loosening the ordering constraints with no corresponding complications in consumer code that I am aware of. @binji, does this seem reasonable? Are there potential complications that I am missing?

I'm suggesting that we provided an ordering even between sections that otherwise have no constraints, similar to the rest of the wasm format. There's no requirement that the custom sections have an ordering, but I'm worried that we'll end up with consistency issues like we did with the name section (before it was spec'd as being required after the data section).

I'm totally fine with specifying a mostly-linear ordering between sections, including between custom sections that are meaningful to the toolchain. But I think it also makes sense to allow for exceptions to that when it allows for simpler code, as is the case for the unspecified ordering between the producers section and relocation sections. This CL is about changing the mechanism to allow for this exception, not about changing the ordering of existing sections or changing our norm of specifying such orderings. Do you think we should disallow exceptions entirely?

[binji]

I'm totally fine with specifying a mostly-linear ordering between sections, including between custom sections that are meaningful to the toolchain. But I think it also makes sense to allow for exceptions to that when it allows for simpler code, as is the case for the unspecified ordering between the producers section and relocation sections. This CL is about changing the mechanism to allow for this exception, not about changing the ordering of existing sections or changing our norm of specifying such orderings. Do you think we should disallow exceptions entirely?

I don't want to push back too hard on this. Since we're talking about tool conventions that are currently used by tools in the LLVM repos, it's probably OK. My point is just that if we don't have a total order, then it's likely that we'll eventually see modules that support all orderings, which will make it harder to reason about. My bias is toward being over-constrained at first, then loosening those constraints, so that's why I'd like to see something more strict here. But if it's especially burdensome to do so, then I think it's fine to go with a simpler solution, as long as it's sufficiently tested.

[aheejin]

I think it'd be OK to relax these constraints, but I don't feel too strongly on either side though. Anyway LGTM to me.

llvm/lib/Object/WasmObjectFile.cpp

1555 ↗

(On Diff #187122)

I understand what this does, but maybe add an one-line comment saying this intends to express a DAG ? At first glance, someone might wonder like "Why are there only two disallowed predecessors for WASM_SEC_ORDER_TYPE"?

llvm/test/Object/wasm-relocs-and-producers.yaml

2 ↗

(On Diff #187122)

Nit: Can't we merge these into one line?
yaml2obj %s | llvm-objdump -s | FileCheck %s

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

private:
   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 {
+    // Sentinel, must be zero
+    WASM_SEC_ORDER_NONE = 0,
+
     // 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,
+    WASM_SEC_ORDER_TYPE,
+    WASM_SEC_ORDER_IMPORT,
+    WASM_SEC_ORDER_FUNCTION,
+    WASM_SEC_ORDER_TABLE,
+    WASM_SEC_ORDER_MEMORY,
+    WASM_SEC_ORDER_GLOBAL,
+    WASM_SEC_ORDER_EVENT,
+    WASM_SEC_ORDER_EXPORT,
+    WASM_SEC_ORDER_START,
+    WASM_SEC_ORDER_ELEM,
+    WASM_SEC_ORDER_DATACOUNT,
+    WASM_SEC_ORDER_CODE,
+    WASM_SEC_ORDER_DATA,
 
     // Custom sections
     // "dylink" should be the very first section in the module
-    WASM_SEC_ORDER_DYLINK = 0,
+    WASM_SEC_ORDER_DYLINK,
     // "linking" section requires DATA section in order to validate data symbols
-    WASM_SEC_ORDER_LINKING = 100,
+    WASM_SEC_ORDER_LINKING,
     // Must come after "linking" section in order to validate reloc indexes.
-    WASM_SEC_ORDER_RELOC = 101,
+    WASM_SEC_ORDER_RELOC,
     // "name" section must appear after DATA. Comes after "linking" to allow
     // symbol table to set default function name.
-    WASM_SEC_ORDER_NAME = 102,
+    WASM_SEC_ORDER_NAME,
     // "producers" section must appear after "name" section.
-    WASM_SEC_ORDER_PRODUCERS = 103
+    WASM_SEC_ORDER_PRODUCERS,
+
+    // Must be last
+    WASM_NUM_SEC_ORDERS
+
   };
 
+  // Sections that may or may not be present, but cannot be predecessors
+  static int DisallowedPredecessors[WASM_NUM_SEC_ORDERS][WASM_NUM_SEC_ORDERS];
+
   bool isValidSectionOrder(unsigned ID, StringRef CustomSectionName = "");
 
 private:
-  int LastOrder = -1; // Lastly seen known section's order
+  bool Seen[WASM_NUM_SEC_ORDERS] = {}; // Sections that have been seen already
 
   // 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

int WasmSectionOrderChecker::getSectionOrder(unsigned ID,
   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);
+        .Default(WASM_SEC_ORDER_NONE);
   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_DATACOUNT:
     return WASM_SEC_ORDER_DATACOUNT;
   case wasm::WASM_SEC_EVENT:
     return WASM_SEC_ORDER_EVENT;
   default:
     llvm_unreachable("invalid section");
   }
 }
 
+// Represents the edges in a directed graph where any node B reachable from node
+// A is not allowed to appear before A in the section ordering, but may appear
+// afterward.
+int WasmSectionOrderChecker::DisallowedPredecessors[WASM_NUM_SEC_ORDERS][WASM_NUM_SEC_ORDERS] = {
+  {}, // WASM_SEC_ORDER_NONE
+  {WASM_SEC_ORDER_TYPE, WASM_SEC_ORDER_IMPORT}, // WASM_SEC_ORDER_TYPE,
+  {WASM_SEC_ORDER_IMPORT, WASM_SEC_ORDER_FUNCTION}, // WASM_SEC_ORDER_IMPORT,
+  {WASM_SEC_ORDER_FUNCTION, WASM_SEC_ORDER_TABLE}, // WASM_SEC_ORDER_FUNCTION,
+  {WASM_SEC_ORDER_TABLE, WASM_SEC_ORDER_MEMORY}, // WASM_SEC_ORDER_TABLE,
+  {WASM_SEC_ORDER_MEMORY, WASM_SEC_ORDER_GLOBAL}, // WASM_SEC_ORDER_MEMORY,
+  {WASM_SEC_ORDER_GLOBAL, WASM_SEC_ORDER_EVENT}, // WASM_SEC_ORDER_GLOBAL,
+  {WASM_SEC_ORDER_EVENT, WASM_SEC_ORDER_EXPORT}, // WASM_SEC_ORDER_EVENT,
+  {WASM_SEC_ORDER_EXPORT, WASM_SEC_ORDER_START}, // WASM_SEC_ORDER_EXPORT,
+  {WASM_SEC_ORDER_START, WASM_SEC_ORDER_ELEM}, // WASM_SEC_ORDER_START,
+  {WASM_SEC_ORDER_ELEM, WASM_SEC_ORDER_DATACOUNT}, // WASM_SEC_ORDER_ELEM,
+  {WASM_SEC_ORDER_DATACOUNT, WASM_SEC_ORDER_CODE}, // WASM_SEC_ORDER_DATACOUNT,
+  {WASM_SEC_ORDER_CODE, WASM_SEC_ORDER_DATA}, // WASM_SEC_ORDER_CODE,
+  {WASM_SEC_ORDER_DATA, WASM_SEC_ORDER_LINKING}, // WASM_SEC_ORDER_DATA,
+
+  // Custom Sections
+  {WASM_SEC_ORDER_DYLINK, WASM_SEC_ORDER_TYPE}, // WASM_SEC_ORDER_DYLINK,
+  {WASM_SEC_ORDER_LINKING, WASM_SEC_ORDER_RELOC, WASM_SEC_ORDER_NAME}, // WASM_SEC_ORDER_LINKING,
+  {}, // WASM_SEC_ORDER_RELOC (can be repeated),
+  {WASM_SEC_ORDER_NAME, WASM_SEC_ORDER_PRODUCERS}, // WASM_SEC_ORDER_NAME,
+  {WASM_SEC_ORDER_PRODUCERS}, // WASM_SEC_ORDER_PRODUCERS,
+};
+
 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;
+  if (Order == WASM_SEC_ORDER_NONE)
+    return true;
+
+  // Disallowed predecessors we need to check for
+  SmallVector<int, WASM_NUM_SEC_ORDERS> WorkList;
+
+  // Keep track of completed checks to avoid repeating work
+  bool Checked[WASM_NUM_SEC_ORDERS] = {};
+
+  int Curr = Order;
+  while (true) {
+    // Add new disallowed predecessors to work list
+    for (size_t I = 0;; ++I) {
+      int Next = DisallowedPredecessors[Curr][I];
+      if (Next == WASM_SEC_ORDER_NONE)
+        break;
+      if (Checked[Next])
+        continue;
+      WorkList.push_back(Next);
+      Checked[Next] = true;
+    }
+
+    if (WorkList.empty())
+      break;
+
+    // Consider next disallowed predecessor
+    Curr = WorkList.pop_back_val();
+    if (Seen[Curr])
+      return false;
+  }
+
+  // Have not seen any disallowed predecessors
+  Seen[Order] = true;
 }

llvm/trunk/test/Object/wasm-relocs-and-producers.yaml

+# RUN: yaml2obj %s | llvm-objdump -s - | FileCheck %s
+
+# This is a regression test for an issue with the section order
+# checker being overly strict. yaml2obj places the relocations last,
+# but the section order checker previously checked that relocations
+# came before the producers section, which would cause this test to
+# fail.
+
+# CHECK: Contents of section producers:
+# CHECK: Contents of section reloc.CODE:
+
+--- !WASM
+FileHeader:
+  Version:         0x00000001
+Sections:
+  - Type:            TYPE
+    Signatures:
+      - Index:           0
+        ReturnType:      NORESULT
+        ParamTypes:      []
+  - Type:            IMPORT
+    Imports:
+      - Module:          env
+        Field:           __linear_memory
+        Kind:            MEMORY
+        Memory:
+          Initial:         0x00000000
+      - Module:          env
+        Field:           __indirect_function_table
+        Kind:            TABLE
+        Table:
+          ElemType:        FUNCREF
+          Limits:
+            Initial:         0x00000000
+  - Type:            FUNCTION
+    FunctionTypes:   [ 0 ]
+  - Type:            CODE
+    Relocations:
+      - Type:            R_WASM_FUNCTION_INDEX_LEB
+        Index:           0
+        Offset:          0x00000004
+    Functions:
+      - Index:           0
+        Locals:          []
+        Body:            1080808080000B
+  - Type:            CUSTOM
+    Name:            linking
+    Version:         2
+    SymbolTable:
+      - Index:           0
+        Kind:            FUNCTION
+        Name:            foo
+        Flags:           [ VISIBILITY_HIDDEN ]
+        Function:        0
+  - Type:            CUSTOM
+    Name:            producers
+    Tools:
+      - Name:            clang
+        Version:         9.0.0
+...