Framework for defining behavior beyond standard semantics

[penzn]

Filing to continue the discussion in the CG meeting today.

Some background, from the point of view of testing, can be found in WebAssembly/spec#1341. Other considerations would include text representation and whether or not we can make this aspect of Wasm runtimes completely separate from the spec (i.e. not requiring proposal process in order to use).

As for what was suggested in the meeting as possible solutions:

• @RossTate suggested codifying CFG modifications that such changes would entail
• @fgmccabe suggested developing a framework for meta annotations

/cc @yuri91

[yuri91]

I will try to summarize the discussion so far as I understand it, and address some of the issues:

The problem

There are a few proposals that concern the execution of a wasm module, but don't add any observable behavior:

• Branch Hinting
• Instrument and Tracing Technology
• Function hints (not currently a proposal, but experimental feature of V8)
• Constant time (actually not sure if this counts, but I would like to keep it here as a further example for now)

A basic implementation of a Wasm engine may ignore these features and still get a correct result.

The trend

Modifying the core spec and requiring all compliant implementations to handle these features is an unnecessary burden. Moreover, not all the implementations may even get anything meaningful from some of these features (e.g. an interpreter doesn't gain anything from branch hinting).

As a result, the CG is (rightfully) hesitant in handling these proposal. One "escape hatch" that can move the proposals forward is to use custom sections instead of adding new instructions.
Custom sections by definition cannot alter the semantics of the program, and can be ignored by implementations.
The Wasm spec can describe the meaning and the binary format of well-known custom sections in the Appendix, as exemplified by the name section (the only "official" custom section so far).

Custom sections are just one possible mechanism, and while the preferred way of handling this kind of proposal, it may not be always desirable (In the latest CG meeting, people seemed to agree that new instructions are probably a better way to implement Constant Time, even if the new instructions don't add observable behavior, and basic implementations will probably implement them the same way as the normal instructions).

Open questions

There are currently some open questions, both organizational and technical.

1. Are custom sections a viable mechanism to implement this kind of features?
2. Should the CG be involved in the definition of custom sections, even if these are "only" part of the appendix?

If the answer to the above questions is "yes":

3. Should we devise a guideline for figuring out if a feature should use a custom section?
4. Should we have a guideline for encoding data in the custom sections (e.g. how to represent byte offsets in the code section)?
5. Should we add a way to represent custom sections in the text format?
6. Should we add tests for the "official" custom sections? And how should we run them?

My answers

My answers to the first two questions:

1. Yes. At least for some proposals, custom sections make sense. The current spec even mentions that custom section could be used for "improving the user experience or giving compilation hints" (which is what Instrument Tracing and Branch/Function hinting respectively do).
   It does not mean that it must be the only option, and probably the decision have to be taken on a case by case basis.

2. Yes. The CG is already involved in more than just the core spec. Obvious examples are the JS and C/C++ APIs, but not the only ones.
   On practical terms, if we decide that the CG should not get involved in specifying custom section, the effect will be that more features will be presented as new instructions, just to be "official", and bloat the core spec.
   The effective implementation of these features requires coordination between application developers (the ones that ultimately use the features), tools (compilers, optimizers, debuggers, visualizers,.. that need to understand the semantics and potentially preserve it through transformations), and engines.
   I can't think of a better place to do this than the CG.

As for the remaining questions, I don't have definite answers:

3. This would be useful to avoid keep coming back on the decision to use a custom section vs new instructions over and over
4. I think we should settle on some "standard" way of encoding certain information. For example, both Branch Hinting and ITT should use the same way of encoding byte offsets. I can't find the encoding used by ITT in the proposal repo so I don't know if this is already the case)
5. This is probably useful, and some work is being done here. At the same time, I don't think this issue should block these proposals from going forward since a nice textual representation can be added as a subsequent improvement.
6. This is tricky because currently no implementation can really run custom section tests (not even for the name section!). This issue is trying to address this problem.

I am curious to see what other people think about this.

[RossTate]

To elaborate on my technical section, here's a "standard" that I think these "modifying" sections could follow.

• Have them precede any sections they modify.
• Give them "modifying" instructions like "insert this between the third and fourth instruction of the fifth function of the next section"
• Require these instructions to be listed in order

This way a tool or engine that understands a modifying section can maintain a cursor within that section, then as it parses the section being modified it can advance the cursor appropriately. If there are many such sections, it's easy to maintain many such cursors (though we'll have to come up with some disambiguation strategy if two cursors insert modifications at the same spot).

Furthermore, even if a tool doesn't understand a modifying section, it can still decorate the modified section with these black-box annotations and make an effort to preserve them through any transformations it employs. After transformation, it's still easy for the tool to generate the new modifying section with the target-locations of the modifying instructions adjusted appropriately.

[rossberg]

Another question would be where custom sections get specified. There likely is going to be a broad range of them, with widely varying relevance to the broader ecosystem. It probably doesn't make sense to put them all into the core spec, even if they get standardised. Some layering scales better, so we may want to create separate documents for distinct custom sections.

[penzn]

Sorry, the response ended up running a bit long, I am trying to break it into sections 😃 We can try to meet in some online form, this usually helps.

Spec

1. Are custom sections a viable mechanism to implement this kind of features?

In my personal view the answer is "it depends". I think we definitely need these features, however custom sections, the way they are defined now, pose some challenges. One issue is there isn't a way to meaningfully test or examine them, which can lead to divergent implementations. We can check if the section is there, but we don't have a way to test if the implementation or (more importantly) a tool does all the right things with it.

However a more serious problem is that any given tool that is not properly aware of any given custom section implementation can break it by not reflecting bytecode changes. Maintaining this type of parallel information is generally error-prone and potentially expensive. This of course is made worse by the first problem, that we can't easily test the tools 😃

I think @RossTate's proposal can help with some of these issues though.

2. Should the CG be involved in the definition of custom sections, even if these are "only" part of the appendix?

I think so, even if just to make layouts of those sections available to any implementation that wants to support them.

Better format

Furthermore, even if a tool doesn't understand a modifying section, it can still decorate the modified section with these black-box annotations and make an effort to preserve them through any transformations it employs. After transformation, it's still easy for the tool to generate the new modifying section with the target-locations of the modifying instructions adjusted appropriately.

Second that - if we can get to black-box treatment of annotations, then we can solve most of the tooling problems.

• Give them "modifying" instructions like "insert this between the third and fourth instruction of the fifth function of the next section"

I feel like we need to be able to attach tags to particular instructions (the ones they would move with), and whether they would be interpreted as "before", "after" or "at" would be up to the implementation. Also, what about situations where we want to annotate not just instructions, but ranges - for example if you are timing something you don't want start and end to be reordered, or some other sequence dropped in.

Better testing

Even if we improve the annotation format, this still would not cover the testing issue (we would just make it easier for tools to pass it through undamaged). I am not sure we have a way to fix this, as modifications encoded by custom sections would result in changes on levels below Wasm bytecode, which is beyond the spec.

[RossTate]

I feel like we need to be able to attach tags to particular instructions (the ones they would move with), and whether they would be interpreted as "before", "after" or "at" would be up to the implementation. Also, what about situations where we want to annotate not just instructions, but ranges - for example if you are timing something you don't want start and end to be reordered, or some other sequence dropped in.

Sorry, I meant the "insert" instruction to be just an example. As you mention, there are other kinds of modifying instructions we will want, and we can also add more in the future should new needs arise.

[tlively]

So it sounds like we need these components:

1. Custom section format

   A standard custom section format for associating arbitrary annotations with individual instructions in the code section. The content and interpretation of the annotations should be left to individual proposals using this framework.

   • Have them precede any sections they modify.
   • Give them "modifying" instructions like "insert this between the third and fourth instruction of the fifth function of the next section"
   • Require these instructions to be listed in order

   These rules suggested by @RossTate sound good to me, except I would suggest using byte offsets rather than instruction counts for consistency with existing code addressing mechanisms and compatibility with feature detection. Also, I don't think we need any more "instructions" besides "associate this annotation data with this code position." Proposals that need to annotate ranges, for example, can just annotate separate start and end markers to keep the framework simple.

   Concretely, here is a possible format:

   Custom section name string: "code_annotation"
   
   codeannotationsec ::= vec(codeannotation)
   
   codeannotation ::= pos: u32
                      kind: u32
                      data: vec(byte)
   

   Where pos is the byte offset into the code section and must not decrease, kind identifies what kind of annotation this is, and data is the associated annotation data, Proposals using this framework would each have their own kind values and define the interpretation of their associated data.

2. Text format

   I would want to investigate building a similar general framework for the text format on top of the annotations proposal. Having both a binary and text format will allow us to at least have tests for round-tripping annotations.

3. A test for determining when to use the framework

   Capturing our intuition that the constant time proposal should get new instructions but that the tracing and branch hinting proposals should not, I suggest this test: We should use this framework for proposals for which completely ignoring the annotations would be a "correct" implementation, where the meaning of "correct" depends on the intent of the proposal.

   So for branch hinting, compilation hinting, and tracing, it is clear that they should use the framework because ignoring the hints is an entirely acceptable behavior. For the constant-time proposal, an implementation would not be faithfully implementing the intent of the proposal if it ignored the constant-timeness of the instructions, so that proposal should use new instructions instead.

[kripken]

@RossTate

Furthermore, even if a tool doesn't understand a modifying section, it can still decorate the modified section with these black-box annotations and make an effort to preserve them through any transformations it employs. After transformation, it's still easy for the tool to generate the new modifying section with the target-locations of the modifying instructions adjusted appropriately.

I am worried about annotations that change their meaning depending on their position or other alterations. For example, a branch hint should be flipped if a tool flips the condition and the arms of an if, and an inlining hint might no longer be applicable if the toolchain inlines, etc.

At least for custom sections where the annotation is optional (like a branch hint), I would propose that

1. Each annotation type be in its own section.
2. All such sections have a standard prefix to their name (like "semantic-annotation-branch-hint", "semantic-annotation-inlining").
3. Tools that transform code would be encouraged to remove all such sections that they do not understand.

Tools could then easily remove sections with data that they cannot safely update.

[conrad-watt]

A very naive question:

Taking a hypothetical scenario where a module may have quite a few custom sections defining various bytecode offsets which would cause native codegen to be modified, would there by any startup performance concerns for streaming compilers needing to repeatedly check whether one of the relevant offsets is reached?

I guess with some careful organising of the offsets, one could make the check in the regular case no more expensive than just checking whether the "next" offset has been reached?

[yuri91]

I agree with @kripken that having tools handle sections that they don't fully understand is not feasible.

We are acting like there will be hundreds of such standardized sections, but in practice I don't expect there to be more than a dozen of them. And adding explicit support to a tool for one of them is not actually complex (not more than supporting new instructions). Especially if we stick to some guidelines on the format so that the parsing will be somewhat similar for many of these sections.
As an example, I recently made a PR to wabt to support the branchHints section (in wasm-objdump and wasm-validate for now), and it was a pretty simple process, including tests: WebAssembly/wabt#1693

Also I would like to argue about byte offsets in the code section:
We talked about it regarding branch hinting and we decided against offsets in the whole code section and in favor of a pair (function_index, offset_in_function).
This alleviates a bit the issue of the offset changing during code transformations, because only the hints in the affected function will change offset.
Also it is more handy for engines to have the hints already associated to functions.
The current spec of branch hinting does this (overview here: https://github.com/WebAssembly/branch-hinting/blob/master/proposals/branch-hinting/Overview.md , but the spec text is also updated with the formal notation)

[tlively]

The advantage to using offsets into the code section is that they are already used for relocations in the code and in DWARF, so wasm-ld already knows how to read and update them. I would prefer not to introduce a new indexing scheme on top of that.

[yuri91]

I remember that a problem with code section offsets was that there may be multiple code sec]tions in the future. How do DWARF and relocations handle that?

[penzn]

<...> adding explicit support to a tool for one of them is not actually complex (not more than supporting new instructions). Especially if we stick to some guidelines on the format so that the parsing will be somewhat similar for many of these sections.
As an example, I recently made a PR to wabt to support the branchHints section <...>

Adding something to both LLVM and Binaryen, plus ensuring that it keeps working for releases to come is much more complex effort than initial wabt support. And those are the most common tools, there are others as well. A single unsupported tool that the module passes through would be the kryptonite for the feature, no matter how good the support in other tools is. To me it feels that when adding new instructions currently there is better chance to minimize inter-dependence between unrelated features/passes.

Additionally, even if adding initial support is not really complex maintenance is still needed - if nobody is looking to keep the feature up it would eventually decay. Supporting multiple custom sections also has the potential to increase surface area of tool changes, as they can (and would) introduce new things for the tools to track, which is an incentive to turn custom section feature off for maintenance reasons. And again, lack of ways to test the semantics of custom sections does not make it easier.

I personally see two potential issues with how custom sections are defined now:

• The effort of adding and maintaining them - are they easier to add to tools than instructions?
• Greater potential for support decay in tools over time comparing to instructions

I think discarding unsupported sections is better than producing incorrect ones,, but that is still going to be a barrier for the users. I think optimally we should improve indexing, if that is possible.

[yuri91]

About the custom section vs instruction issue regarding tools:

Let's say that we add branch hinting as new instructions. These instructions are semantically a NOP, but we require nonetheless all tools and engines to support them, since they will be part of the core spec.

I want to focus on the differences in testing and tool support.

Testing

How do we add tests? since semantically these instructions are nops, we can't really test that branches are actually hinted. We can only test that the instructions are parsed correctly (and that they are self-consistent, e.g. the only valid hints are 0 and 1, no other values).

But this is no different than testing that the custom section version parses correctly and is self consistent.
Yes, we will have to add a tool in the spec repo for this, or teach the reference interpreter to read the new custom section, but it is not much different than teaching the reference interpreter about the new instructions.

The only tricky part imho is that if the custom section is indeed inconsistent or contains garbage, engines won't error out, so even the basic tests need the addition of some kind of diagnostic (probably console warnings) to be usable by engines. If we use instruction instead, any tool/engine already has a way to signal an error and abort.

So we would gain this minor convenience, at the expense of requiring all the ecosystem to "implement" these instructions, even as nops.

Tool support

Instructions are not magically safe from rotting. For example a tool that flips branches may "forget"/break branch hinting implemented with instructions as easily as with custom sections.

Here the main issue of custom sections is that a tool will need to keep track of changing offsets if it modifies the code section.
But this applies to other things too, like DWARF and relocation info, so this complexity will still be there.
If we design the format of these sections in a consistent way, it shouldn't be too hard to have some common infrastructure to handle offset relocations.

This doesn't mean that it can be done automatically for any such custom section. I still believe that a tool needs to understand the meaning of the section to be able to safely update it (same for instructions, btw), but a common format can still be useful to reduce the chance of code decay even for less used sections, and can help code reuse.

[titzer]

I generally support developing a standard way to reference instructions in code sections so that they become visible in tools, and second @tlively's point that we should use byte offsets to do so.

One thing I mentioned in the meeting as a criterion for whether something should be an out-of-band instruction modifier or a new instruction, even if semantically equivalent, was interpreters. Interpreters haven't been a big factor in our design calculus, but I think this will change (actually, in point of fact, I aim to change this :)).

[yuri91]

I am trying to summarize the discussion into a concrete plan for updating the branch hinting proposal.

I agree with the general idea of this comment , but also with @kripken that each annotation should have its own section.

The section name could be prefixed to signal that it is following this format: code_annotation.<feature_name>

So, the blueprint format of these sections could be:

Custom section name string: "code_annotation.'<feature_name>"

codeannotationsec ::= vec(codeannotation)

codeannotation ::= pos: u32
                   kind: u32
                   data: vec(byte)

in the specific case of branch hinting the new format would look like:

Custom section name string: "code_annotation.branch_hints"
branchhintsec ::= vec(branchhint)

branchhint ::= pos: u32
                   kind: 0x00 | 0x01
                   data: 0x00

(In this case the "data" vector would just be empty)

The annotations proposal seems to me like a good starting point for having a textual representation of the branch hints (and other "code annotation" proposals), but I think that it should proceed separately.

I would like to know what people thing about @rossberg 's point of potentially putting the specification of these sections in a separate document and not in the core spec.
I am not opposed to it, but if we want to go in this direction I would like some help in figuring out how to organize such a thing: a new layer of the spec needs extra documentation and organizational effort compared to just expanding the appendix of the core spec.
On the plus side this could help on the testing side, because this new spec could use a totally separate test suite than the core spec one, more suitable for the task.