Unsoundness bug: ref.func of imported function

[tlively]

Problem

Consider this module:

(module $A
  (type $super (sub (func)))
  (type $sub (sub $super (func)))

  (import "B" "f" (func $f (type $super)))

  (global (export "f") (ref (exact $super)) (ref.func $f))
)

This module imports a function $f of type $super, then exports a reference to it with type (ref (exact $super)). According to the rules currently described in this proposal, this is fine because ref.func returns exact references. But this is unsound! The function B.f supplied at instantiation time might actually have been of type $sub. In that case it would be incorrect to type a reference to the function as (exact $super), because in fact the reference would be to a $sub.

Solution

A simple solution to this problem would be to type references to imported functions as inexact. This would be sound, but it would not be modular enough because it would create a difference in expressivity between imported and defined functions. The latter would be able to be referenced exactly and the former would not. This would inhibit e.g. module splitting where the secondary module contains a function that takes an exact reference to a function imported from the primary module. This would work before splitting the function definitions into separate modules, but not afterward.

To support this use case, we must make it possible to take exact references to imported functions. But for that to be sound, we must ensure that such imported functions have exactly the referenced type. Function imports already give a type for the imported function; we must now make it possible for that type to be exact.

There are a couple ways we could go about letting function imports be exact (e.g. allowing exactness in typeuse), but the least intrusive way is probably to make the externtype for functions be a heaptype rather than a typeuse. This is backward compatible because the binary representation of heaptype (an s33) includes all possible values of typeuse (a u32). The text format would have to be updated to allow typeuse or heaptype, though (and for best ergonomics, we would want to allow some combination of the two, so the params and results could still be given for exact imports).

The typing rule for ref.func would have to produce an exact reference for exactly imported functions and defined functions and an inexact reference for inexactly imported functions. This is probably best achieved by making funcs in the typing context be a list of possibly-exact heaptype rather than a list of deftype.

Credit

Credit for finding this bug goes to Seunghyun Lee (@0x10n) of CMU CSD / CyLab.

[rossberg]

Your solution sounds right, but I wonder if the simplest (and conservative) fix isn't to just not have ref.func return an exact type for the time being (i.e., leave exact function types uninhabited until we find out they matter). Or is there a use case for exact functions at the moment?

I agree that we should not make a distinction between imported and defined functions.

[tlively]

Yes, good point. Simply not having exact function references would also fix the problem. But exactness is useful for optimizations, so it would be a little sad to miss out on that for functions.

[rossberg]

I believe an optimiser could still safely assign the more precise typing to functions and ref.func that you suggest, and make use of that internally. Unless exact function types are either actually used by producers (which I doubt they will), or the optimiser would want to introduce them into the output code (is there such a scenario?), I don't think you'd lose any optimisation that way. Or is that thinking too simplistic?

[tlively]

The optimizer might want to introduce exact casts (e.g. by replacing a non-exact cast with an exact cast where proven to be ok) because exact casts can be executed slightly faster than inexact casts.

[tlively]

I didn't spell this out before, but I had been imagining that defined functions would always be implicitly exported as exact. This is backward-compatible because an exact export can satisfy an inexact import of the same type or any supertype. The wrinkle, however, is that it would become invalid to refine the type of an exported function to a subtype of its original type, since then it would no longer satisfy exact imports of the original type. To keep such an optimization valid, we would need a way to export a function with an inexact type. (I'm not sure how important this is, though.)

If we did the simpler thing and made ref.func return an inexact reference, then we'd be in a weird situation where you could do a cast to an exact reference right afterward and it would always succeed for defined functions (but not always for imported functions), but the cast wouldn't be able to be optimized out except by engines.

[rossberg]

The wrinkle, however, is that it would become invalid to refine the type of an exported function to a subtype of its original type, since then it would no longer satisfy exact imports of the original type. To keep such an optimization valid, we would need a way to export a function with an inexact type. (I'm not sure how important this is, though.)

Ah, good point. I think even with exact functions, we'd want to make both imports and exports inexact by default. Keeping them symmetric is more likely to avoid nasty surprises when trying to evolve a module.

If we did the simpler thing and made ref.func return an inexact reference, then we'd be in a weird situation where you could do a cast to an exact reference right afterward and it would always succeed for defined functions (but not always for imported functions), but the cast wouldn't be able to be optimized out except by engines.

True, but does it matter? Is there a use case for such casts right now?

I guess I'm still trying to understand what an optimiser could actually do with the exact type of a function ref. If there is no benefit in knowing that a function type is exact, then there is no benefit in casting to it either.

[tlively]

In principle having the most refined possible type information for function references can help do a more precise type-based call graph analysis, for example, which could lead to better devirtualization. (Again, I'm not sure how much this matters with today's optimizations, but I'm hesitant to remove a useful tool that we would otherwise be able to use in the future.)

[tlively]

@rossberg, any good ideas for the text format for exact type function imports? The binary format change is straightforward: the existing u32 encoding a typeuse simply becomes an s33 encoding a heaptype. The text format is trickier because the function type is a text typeuse that can have inline params and results.

Do we want to extend that sugar to support exact function types with inline params and results? If so, do we create a separate maybe-exact-typeuse or do we just allow the current typeuse to be exact with a side condition that it is not exact at most of its use sites?

[rossberg]

(I assume you meant exact function imports?)

If the binary encoding becomes a heaptype, then the text format should match that. To allow a non-index typeuse in a heaptype, perhaps the most natural thing to do is to introduce

heaptypeuse ::= absheaptype | exact? typeuse

[tlively]

So it would look like this?

(import "" "" (func exact (type $f)))
(import "" "" (func exact (param i32) (result i32)))
(func (import "" "") exact (type $f) (param) (result))

[rossberg]

Yes, though to be consistent with heaptype syntax elsewhere, we could require parens around (exact ...)? Maybe not, I'm undecided...

[tlively]

I think it looks better and more consistent with the parens, so that's what I've implemented in #57. I also noticed that the reference interpreter only parses a subset of the specified syntax for typeuse, but I didn't attempt to fix that at the same time.