Testing of annotations and custom sections

[yuri91]

I have been thinking a lot on how to add testing to the Branch Hinting proposal,
and in general to annotations and custom section based proposals (like the Annotations proposal
and the Instrument and Tracing Technology proposal), and to a feature present in
the MVP itself but not currently tested: the name section.

The main issue with testing these features is that an implementation is allowed to
ignore annotations and custom sections, even if malformed, and they cannot affect the
semantics of the module.

By discussing about it in various CG meetings and in private, I believe that we need
to achieve the following:

• The reference interpreter should have a special mode that enables the parsing
  and validation of known annotations and custom sections, and should be able to round trip
  them between text and binary format.

• a separate set of tests is run in this special mode, allowing the testing of these features

• We don't expect engines, or even most implementations to add such special mode,
  so passing these tests is optional. The test cases themseslves can still be useful to
  understand what is allowed and what not, and to be integrated in the engine/tool test
  suite in a manual way.

• Given the above, the test runner should have itself a command line option to
  enable/disable these tests (not sure what the default should be, but the CI should
  run them)

I have a proof of concept that satisfies the above requirements and adds support
in the interpreter and tests for the @custom annotation specified in the Annotations proposal.

If the CG likes the approach I can similarly implement branch hinting (I started with
@custom because validation is simpler).

The proof of concept is in this branch of the branch hinting repo, but I will rebase it
on top of the annotations repo and make a PR there if people like this approach.

I am very interested in feedback about this, and eager to adapt the PoC to additional
requirements.

I also welcome feedback on the OCaml code. This is the first time I use it and
the code is probably not idiomatic.

Features added to the interpreter:

• new command line switch -c that enables annotations and custom sections handling
• text parsing and text output of @custom annotations
• binary encoding and decoding of custom sections
• proper roundtrip of custom sections when converting to text and back, via custom annotations
• same but starting from custom annotations in text

Features added to tests/core/run.py:

• new command line switch --custom that adds tests in the custom directory
  to the list of tests to run
• logic to pass the -c flag to the interpreter for tests inside the custom directory

Related past issues: WebAssembly/annotations#15 , WebAssembly/branch-hinting#13 , #1424 , WebAssembly/spec#1341

[rossberg]

Thanks for looking into this, this looks like a good direction. A few comments:

• A monolithic custom flag probably isn't enough. Different implementations or tools may choose to recognise different custom sections. In particular, if they do not implement certain custom sections, they may want to be able to compare against the reference interpreter ignoring the same sections. So instead of an all-or-nothing flag, I think we'd want a way of selecting the set of custom sections somebody cares about.

• I don't think it will work to parse structured annotations directly in the parser as you currently do with @custom. If somebody turns off recognising custom sections, then the interpreter will have to accept (syntactically) any annotation, whether syntactically well-formed or not. So you'll have to parse annotations generically in the main parser and then post-process them if the respective flag is on, possibly with a secondary parser.

• Since annotations are not part of Wasm syntax proper, their AST should probably be defined separately from the main AST.

• For some custom sections (like @name), there will also be corresponding custom annotation syntax. We probably want the interpreter to be able to parse those as well.

• What is the plan for "validating" custom sections/annotations?

• There probably should also be a flag to make unrecognised custom sections/annotations an error, in order to avoid false positives.

• In general, various unrelated custom sections might accumulate, so it would be great to handle them in a modular fashion. For example, there could be an internal registry for modules, each of which provides functionality for decoding/parsing/validating/encoding/printing a section of a given name. Based on the flags passed to the interpreter, this registry is populated, and other custom sections/annotations are ignored.

The last point touches on one meta concern I have, which is about correspondence to the spec. The reference interpreter is supposed to reflect what's in the core spec, nothing else. And I expect that most custom sections will be defined elsewhere, e.g., closer to tool conventions or something similar. For those, neither implementation nor tests would belong into the main spec repo. I'm not sure how to handle this, since the current approach seems to require extending the interpreter itself.

With modularisation into a registry, custom modules would be kept almost entirely decoupled from the rest of the interpreter, so that they can be plugged into the build with only a single hook, which can reasonably be done in a downstream fork. That might be sufficient for our needs.

Does that make sense?

[yuri91]

Thanks for the feedback!

• A monolithic custom flag probably isn't enough. [...]

True.

Though for the python test runner we probably want an all-or-nothing that enables all of the options for stuff in the special directory?

Otherwise we need to attach the required flags to the tests, either with a map in the code or in the file themselves as comments at the beginning (this seems to be a common solution to this sort of issue). It seems to me as an unnecessary complication, at least for now.

• I don't think it will work to parse structured annotations directly in the parser as you currently do with @Custom. If somebody turns off recognising custom sections, then the interpreter will have to accept (syntactically) any annotation, whether syntactically well-formed or not. So you'll have to parse annotations generically in the main parser and then post-process them if the respective flag is on, possibly with a secondary parser.

Actually if the flag is off the annotations are eaten by the lexer and no token is produced, like in the original in the annotations proposal. And the same happens for any non-recognized annotation name even with the flag on. I think it is easier than parsing a completely generic annotation to just discard all the tokens.

• Since annotations are not part of Wasm syntax proper, their AST should probably be defined separately from the main AST.

This makes sense, but for @custom in particular, since it is the text representation of custom sections, and those are in the syntax proper, I think that the lines blur a bit.

• For some custom sections (like @name), there will also be corresponding custom annotation syntax. We probably want the interpreter to be able to parse those as well.

Yes, I started with @custom because there is not really any validation logic for it, just simple parsing, but @name should also be added

• What is the plan for "validating" custom sections/annotations?

For now I haven't touched the validation part of the interpreter, as it is not needed if we are just accepting @custom.
But once we add more complex ones (like @name), we need to validate them. And in particular we should probably validate them even if they are contained in a @custom and not using the specialized annotation syntax.
I was planning of plugging this validation into the same logic that validates the other sections.

• There probably should also be a flag to make unrecognised custom sections/annotations an error, in order to avoid false positives.

Makes sense.

About the registry concept, could you elaborate a bit on how "dynamic" it should be in your mind?

Because trying to put all the parsing/validation/decoding/encoding of a custom section in its own module makes sense (though I am not sure how easy it is to combine parsers, or if the lexer should be common or not...), but I am not convinced about the ability to "plug" features that are outside of the spec.

In my opinion the reference interpreter should only deal with sections/annotations present in the appendix of the core spec. For other non-standard secttions/annotations that may become relevant, other tools can be used (like Wabt). This should greatly reduce the number of features that will need to be added.

[rossberg]

Thanks for the feedback!

• A monolithic custom flag probably isn't enough. [...]

Though for the python test runner we probably want an all-or-nothing that enables all of the options for stuff in the special directory?

Yes, we probably want both, individual flags and shortcuts for all or none, e.g., for CI.

Otherwise we need to attach the required flags to the tests, either with a map in the code or in the file themselves as comments at the beginning (this seems to be a common solution to this sort of issue). It seems to me as an unnecessary complication, at least for now.

Well, the choice has to be up to the person running the test suite, because they decide which custom sections they implement. So the configuration can't be inside the test suite alone.

My rough idea for a test suite infrastructure would be that we have a subdirectory test/custom (parallel to test/core), and below that further subdirectories, one for each custom section. When invoking the runner, you can somehow select which subdirs to include in the run. That also allows, e.g., merging multiple downstream forks with non-standard custom sections into a single local repo and using them together without conflict.

• I don't think it will work to parse structured annotations directly in the parser as you currently do with @Custom. If somebody turns off recognising custom sections, then the interpreter will have to accept (syntactically) any annotation, whether syntactically well-formed or not. So you'll have to parse annotations generically in the main parser and then post-process them if the respective flag is on, possibly with a secondary parser.

Actually if the flag is off the annotations are eaten by the lexer and no token is produced, like in the original in the annotations proposal. And the same happens for any non-recognized annotation name even with the flag on. I think it is easier than parsing a completely generic annotation to just discard all the tokens.

Ah, I see. Yeah, but that still is rather unmodular. For example, it isn't clear how this approach would handle custom annotations that need their own special token interpretation. I'm afraid separating parsers is the only solution to make that possible.

FWIW, in the early days of the annotations proposal I did an implementation for this somewhere, which I have to dig up. IIRC, the Decode module changed to

val decode : string -> string -> Ast.module_ * Custom.custom list

and similarly, Parse to

val parse : string -> Lexing.lexbuf -> 'a start -> 'a * Annot.annot list

where

(* module Custom *)
type custom = custom' Source.phrase
and custom' = {name : Ast.name; content : string}
(* ... *)

and

(* module Annot *)
type annot = annot' Source.phrase
and annot' = {name : Ast.name; items : item list}
and item = item' Source.phrase
and item' =
  | Atom of string
  | Var of string
  | String of string
  | Nat of string
  | Int of string
  | Float of string
  | Parens of item list
  | Annot of annot
(* ... *)

The motivation was that I also needed my own custom section and annotation for another project, and it was implemented on top of the above with a simple recursive descent parser over item lists as tokens.

About the registry concept, could you elaborate a bit on how "dynamic" it should be in your mind?

For now, I have in mind something similar to how host modules are hooked in via Import.register (see the configure function on top of main.ml). Except that for custom sections/annotations, we need a bit more than a single function, so the respective registry would contain first-class modules, e.g., each with a signature like

module type CUSTOM_IMPL =
sig
  type t
  exception Invalid of Source.region * string
  val name : Ast.name
  val decode : Ast.module_ -> Custom.custom -> t
  val encode : t -> Custom.custom
  val parse : Ast.module_ -> Annot.annot list -> t
  val arrange : t -> Sexpr.sexpr
  val check : Ast.module_ -> t -> unit (* raises Invalid *)
end

Here, decode, parse, and check are given the AST of the module itself as well, in case they need to relate to it somehow.

In Ocaml, you can use any module as a first-class value. To add a custom section, you'd simply implement a regular module matching the above signature and then hook it up in the configure function in main.ml. I guess there would be some function in module Custom like

register : (module CUSTOM_IMPL) -> unit
lookup : Ast.name -> (module CUSTOM_IMPL) option

Somewhere in run.ml we'd run over the custom sections / annotations and lookup the respective module if present to handle them, otherwise ignore (or error, depending on flags, I guess).

In my opinion the reference interpreter should only deal with sections/annotations present in the appendix of the core spec. For other non-standard secttions/annotations that may become relevant, other tools can be used (like Wabt). This should greatly reduce the number of features that will need to be added.

Fair enough, but it's still useful to keep this modular and separated from the core Wasm code.

How about I'll dig up my old code and see how easy it would be to upgrade to the current interpreter and implement the above infrastructure. If that works, you could take it from there. WDYT?

[yuri91]

Thanks for the clarifications. I was just about to try something similar to what you are proposing!

How about I'll dig up my old code and see how easy it would be to upgrade to the current interpreter and implement the above infrastructure. If that works, you could take it from there. WDYT?

That would be great!

[yuri91]

@rossberg I was thinking about how to fit branch hinting annotations with this design, and I think I am missing something:

For branch hinting, but probably most other annotations as well, it is important to record where in the code the annotation appears.

The CUSTOM_IMPL interface that you propose has the following function signature for parse:

  val parse : Ast.module_ -> Annot.annot list -> t

And you added:

Here, decode, parse, and check are given the AST of the module itself as well, in case they need to relate to it somehow.

But how can parse trace back each annotation to its original position in the code? Are annot nodes also present in the module's AST?

[rossberg]

@yuri91, I've been working on this over the past weeks. See this branch for my current attempt (diff to annotations main).

Was a bit more tricky than I thought, and still requires a bunch of clean-up and code deduplication, but:

• The interpreter has a hook for "custom handlers", see interpreter/custom directory. They can be activated individually with the new -c <name> flag.
• @Custom annotations are working and do roundtrip, respecting their position and relative order (this is slightly tricky, because the explicit placement information is lost when converting to binary).
• "name" sections work as well, but @name annotations currently only work for module names.
• There's a new test dir test/custom which has corresponding tests (not many yet), and new test targets in the interpreter's Makefile.

To answer your question, the parse function would traverse the AST and look at the position infos to narrow down and find the associated syntax node – sort of analogous to how the binary format uses byte offsets to find the opcode. See the locate_* functions in handler_name.ml for the general idea.

I believe this would work fine for instruction annotations. But admittedly, I'm having difficulties making @name annotations work this way, since some of the relevant source syntax (especially function parameters) is sugar that is not actually present in the AST. Currently, I have no good idea how to solve this.

[yuri91]

To answer your question, the parse function would traverse the AST and look at the position infos to narrow down and find the associated syntax node – sort of analogous to how the binary format uses byte offsets to find the opcode. See the locate_* functions in handler_name.ml for the general idea.

I see. It makes sense.

I believe this would work fine for instruction annotations.

I will try to implement branch hinting with this system, see if there is any hidden issue, and share my findings here.

But admittedly, I'm having difficulties making @name annotations work this way, since some of the relevant source syntax (especially function parameters) is sugar that is not actually present in the AST. Currently, I have no good idea how to solve this.

I will try to think about this. Maybe we could keep some extra metadata with the required positions infos in the AST?

[yuri91]

I tried to implement branch hinting. You can see my attempt here: https://github.com/WebAssembly/branch-hinting/tree/annot_bh

Decoding, parsing and checking are fine, but arranging and decoding aren't possible with the current custom handler design.

Arranging

Currently it is only possible to output a @custom annotation that contains the binary. This is fine for name annotations, but it does not work for any code metadata annotation: the binary form needs the byte offsets of the instructions with the attached metadata, but they are not only not available, they are meaningless: There are multiple valid binary translations of a wat file, if only for the fact that ulebs have multiple representations. So there is no guarantee that the offsets contained in the section will match to the intended instruction offsets once the file is converted to binary.
The only solution here is to have a way to output annotations anywhere, or at least next to instructions.

Encoding

Here there is a similar problem as above: in order to encode a code metadata section, we need the byte offsets of the annotated instructions. The current handler interface though has no way of obtaining them. On top of that, the metadata section should appear before the code section, so we either produce it later and then we compose the final file with the right order, or we leave holes to fix up later once the instructions have been written. Either way, the handler needs to know the instruction offsets somehow.

Solution

I am not sure of the best way to fix these issues, but both could be fixed by allowing the handler to register a "callback" that is invoked during arranging/encoding, that lets it interact with the process to some degree. I don't know how much "invasive" such a system would be to the codebase, especially if fully general (allowing to be called back when processing any ast node), but maybe if we limit it to code metadata annotations (so only for annotations next to instructions) it could be doable.

[rossberg]

Mmh, yes, I see the problem. And it's indeed not clear how to fix that nicely. In general, a custom encoder would need to be able to inquire the byte offset of every AST node, as you point out (and offset relative to what? that might already be specific to the custom format). Simpler than a callback mechanism would be a side table or annotating the offset in the AST for later consumption, but that's also rather invasive.

I have one question, though: if the hint section has to go before the code section, isn't that going to be problem for any producer? It seems to inherently require two passes for encoding. So isn't the need to patch up holes a problem a problem that every producer will face?

[yuri91]

The reason for putting the hint section before the code section is for making it easier for the consumer rather than the producer. I think that this is a common theme in wasm in general. For example anything that requires its size beforehand has to either leave 5 bytes and write the size there later, or use multiple buffers and copy them.

Two phases can be avoided by actually producing the hint section after the code section, and then rearrange them appropriately in the final buffer. This is how Cheerp and Wabt solve it.

About the starting point for relative offsets: if enough nodes of the AST can record their absolute offset, this is not an issue since a relative offset to anything can be easily derived. For example for branch hinting we just need absolute offsets of functions and instructions, and the relative offset of an instruction to the function can be easily computed.

[rossberg]

Depends on what you mean by "absolute" offset. ;) I would interpret that as offset in the whole binary, but that would not work if you want to be able to rearrange the final buffer in the end, like you describe.

[yuri91]

That's true, I hadn't considered that rearranging the sections prevents using real absolute offsets (at least without a second phase, but that would defeat the purpose of rearranging).

At the same time, I can't envision such offsets to be useful to any feature. Byte offsets in general are probably only useful to point to code, since most other entities are already identified by indexes. DWARF has "absolute offsets" that start from the beginning of the code section for example.

[yuri91]

I am trying to overcome the encoding and arranging issues for code metadata sections.

For now I have a decent solution for the arranging issue (being able to emit annotations in the code section, not only in a separate custom annotation) here: WebAssembly/branch-hinting@38631f2

There is a balancing act to be had between being completely general (enabling custom handlers to emit annotations anywhere) and not polluting the main code too much.
The compromise that I chose is to just allow annotations in the code section for now. This covers any code metadata section needs. Sections that want to emit annotations in other places (e.g. name) should be ok with emitting a @custom annotation, unless they need to both emit in the code section and elsewhere. I am not aware of any feature that needs that.

Anyway the design allows for more cases to be covered should they arise (arrange now returns a type annot_kind with two variants).

I am trying a similar strategy for the encoding issue (having information about instruction byte offsets when emitting custom sections in binary format), but it is a bit more tricky here.