[Wasm][Clang] Support for `__externref_t*`?

[hoodmane]

A year ago I opened a draft pull request adding __externref_t* support:
#163610
The idea would be that llvm gains a blessed __externref_table of externrefs, the analogue of __indirect_function_table. Dereferencing an externref pointer would turn into a table_get operation on that table. The table could have a stack region and a heap region. If a pointer to an externref is taken inside of a function, the externref could spill to the stack, so we would bump the stack pointer down 1, use a table_set to assign the externref into the table, and then the address of the externref would be the table index. In the epilogue, we'd use a 𝗍𝖺𝖻𝗅𝖾.𝖿𝗂𝗅l instruction to null out the stack references and then restore the stack pointer. For heap references, we could have __externref_t* table_alloc(void) and void table_free(__externref_t*).

This would allow graceful handling of:

• externref in a struct
• externref arrays
• externref in a varargs
• functions with multiple externref return values
  with the same ergonomics as normal pointers. Currently all of this stuff works, but the ergonomics are poor and each library has its own ad-hoc handling of these problems so there is no globally agreed-upon notion of an externref pointer.

The biggest problem is that currently static __externref_t blah[]; declares a table, and a table is represented in the clang IR as an array type. Because arrays freely decay to pointers, this means that clang currently interprets __externref_t* as coming from a decayed table and representing also a table. We will need some way to migrate the current behavior to the new behavior. I think tables ideally should be declared with an attribute e.g., __attribute__((wasmtable)) __externref_t table[]; so that pointers can be reserved for things that admit arithmetic, dereferencing, etc.

[dschuff]

Before discussing your proposal specifically, let me state up front where I'd like to end up. As you noted the current situation is basically a language extension but it's incomplete and there are several basic C language features or behaviors that don't interact well with it, which makes it difficult to use and reason about. At least partly because of that, there aren't too many users. Because of that I don't think it will necessarily be a problem to make breaking changes to the current support if we can give users something that is much better and can support current use cases. (Part of the problem in doing that though, is that we don't necessarily know who those users are, I don't recall any specific use cases that were tested when the support was implemented in the first place).
So I'd like to see a solution that can support using externrefs more cleanly with regular C code, but of course this is hard because externrefs can never be written to linear memory, but C expects that everything is in memory. So I worry for example that you can quickly run into a case where, say, your externref function argument works in optimized mode, but not in debug mode (where all the function arguments are copied into allocas in the prolog). Or various other cases where users or transformations assume they can do things that break in surprising ways.
I suspect that given all of the limitations, there will be some behaviors that C users expect that won't work, so I would want us to be able to clearly specify those cases in a way users (and not just language lawyers) can understand. And of course given that sharing this with Rust is also a goal (I haven't seen it mentioned actually, but I think that's the case?), we should also be able to clearly specify the conditions and limitations at the LLVM IR layer.
All of these issues are pre-existing of course, but I am hoping to avoid the common failure mode where we fix things just enough for the one use case in front of us but don't at least have a plan for the rest. In other words I'm hoping we can make the current situation as good as it can be rather than just, say, 50% better if we can.

[dschuff]

So, having said all that.
My recollection (correct me if I'm wrong) is that currently __externref_t is effectively a pointer type, i.e. a ptr addrspace(10). It can never be dereferenced (i.e. no LLVM load or store instructions with that ptr type) because that would materialize an opaque value that can't then be written into C memory. In principle you should be able to do addrspacecast, inttoptr and ptrtoint because they are just integers in the end, although I'm not sure that works now.

if I'm understanding what you're proposing at a high level, it's basically turning externref_t into more of a value type, and one that can live in a table rather than a linear memory. So for things like address-taken variables, you are proposing to mirror exactly what we do with the linear memory, i.e. have a shadow stack, and an allocator. So that handles pointer-to-externref.

I'm still a little unclear about how this allows externref in a struct though, or more generally an externref value.
If you have

struct s {
  int a;
  externref_t b;
};
struct s *p;
struct s a = {};
memcpy(s, &a);

What does the initializer look like? What does the memcpy look like?

[hoodmane]

At least partly because of that, there aren't too many users.

Well I use it quite heavily. But I mostly only target one compiler version at a time so I can update my code when I update the compiler. So I'm not too concerned for myself.

there will be some behaviors that C users expect that won't work, so I would want us to be able to clearly specify those cases in a way users (and not just language lawyers) can understand

My hope is that it will be as simple as "If it goes in linear memory (structs, unions, varargs), then you must use __externref_t*. __externref_t can only be used as function arguments and return values and simple variables."

I worry for example that you can quickly run into a case where, say, your externref function argument works in optimized mode, but not in debug mode (where all the function arguments are copied into allocas in the prolog). Or various other cases where users or transformations emscripten-core/emscripten#20021 they can do things that break in surprising ways.

Of course "works in both optimized mode and debug mode" is a simple enough test case. The Emscripten issue seems to be a case of "you can't use __externref_t here but you can use __externref_t*" which will happen in many places.

sharing this with Rust is also a goal ... (?)

Yes, sharing this with Rust is a goal.

My recollection (correct me if I'm wrong) is that currently __externref_t is effectively a pointer type, i.e. a ptr addrspace(10).

That is correct.

It can never be dereferenced (i.e. no LLVM load or store instructions with that ptr type) because that would materialize an opaque value that can't then be written into C memory. In principle you should be able to do addrspacecast, inttoptr and ptrtoint because they are just integers in the end, although I'm not sure that works now.

Yes. What happens is that clang says no to all of these things in SemaChecking. If they are expressed anyways in llvm IR then there is a assertion failure in the target emitter.

I'm still a little unclear about how this allows externref in a struct

The plan is that SemaChecking still fails with field has sizeless type '__externref_t' if you say

struct s {
  int a;
  externref_t b;
};

but the following works fine:

struct s {
  int a;
  externref_t* b;
};

The actual value written is a table index. The initializer would fill in the NULL pointer and memcpy just copies the bytes.

[hoodmane]

One concern is that making a global __externref_t currently turns into a mutable WebAssembly.Global, which we cannot take the address of (if we copied it into the table, people could mutate the Global separately from the table entry). I think we'll have to change this so that a global __externref_t becomes a static externref table index and we export the table index.

[hoodmane]

Oh it turns out that it is possible to make a global __externref_t but only if you never use it -- reading or writing it leads to a cannot select externref,ch = load<...> or cannot select store

[hoodmane]

I have a branch here with a llm-assisted rough draft of the design I'm after:
main...hoodmane:llvm-project:wasm-table-type

This emscripten branch updates the dynamic loader to work with dynamic libraries
that define externref (or externref array) globals:
emscripten-core/emscripten@main...hoodmane:dylink-externref-globals

clang

Internal changes

Table types are now represented by WebAssemblyTableType. Array or pointer to externref now mean actual arrays and pointers to externref.

User-facing changes

Table declarations

Tables are now declared via
__externref_t my_table[] __attribute__((wasmtable)).

Declarations like __externref_t my_table[3]; declare an array.

Sema check

externref and arrays of externref (including n-d arrays) are now allowed as:

• globals
• locals
• function arguments
• pointer targets (pointer to externref and pointer to array of externref)

It is also allowed to apply the address-of operator to an externref or array of externrefs

externref and arrays of externref not allowed as:

• varargs
• struct fields
• union fields
  For these things use pointer to externref or pointer to externref array.

I didn't make any changes to funcrefs, arrays and pointers to funcref are still not supported.

Binary format

• Added two new relocations R_WASM_EXTERNREF_TABLE_INDEX_LEB and
  R_WASM_EXTERNREF_TABLE_INDEX_REL_LEB for externref/externref array globals.
• Added a new WASM_DYLINK_MEM_INFO_EXTERNREFS dylink subsection that includes
  how many externref table slots the dynamic library needs.
• Added a WASM_SYMBOL_EXTERNREF flag to symbols which tells the dynamic loader
  to relocate by adding externref_table_base instead of memory_base.

wasm-ld

Table layout

If any table types are used, it will synthesize an __externref_table. The table
gets laid out with the following globals:

• __externref_data_end: represents the end of the bss.
• __externref_stack_low, __externref_stack_high, __externref_stack_pointer
• __externref_heap_base

I put the bss first and then the stack. I'm not sure whether we need
__externref_data_end or whether we should also have an __externref_data_start
symbol in case we ever want the stack first.

Also, I made __externref_heap_base immutable but perhaps preloading dynamic
libraries will want to move the externref heap base like they do for the memory
heap base.

There are new --export-externref-table and --import-externref-table flags
similar to --export-table and --import-table. They force a table to be
synthesized if passed. There is also a -z externref-stack-size option which
controls the stack size, it defaults to 1024 if used.

There is still a bug if the externref stack is used in a dynamic library but not
in the main executable since the externref stack won't get created at all.

Slot allocation

ExternrefElemSection resolves the new R_WASM_EXTERNREF_TABLE_INDEX_LEB and
R_WASM_EXTERNREF_TABLE_INDEX_REL_LEB globals. Each scalar global gets a single
slot, an array gets one slot per entry.

PIC/dynamic libraries

• externref globals get imported from a GOT.externref module
• dynamic libraries import a global constant __externref_table_base to use to
  relocate externref globals
• the linker populates the new WASM_DYLINK_MEM_INFO_EXTERNREFS dylink.0
  subsection with the number of table slots if there are any exported externref globals
• If a PIC object file is linked into a binary with no dynamic loading, we
  resolve the relocation against externref_table_base at link time.

LLVM CodeGen

• Reading/setting a global externref is a table.get/table.set.
  • In nopic we generate an EXTERNREF_TABLE_INDEX relocation for the table index
  • in pic dso local we generate an EXTERNREF_TABLE_INDEX_REL against the
    table base
  • in pic nonlocal we generate a GOT lookup
• Address of a global externref uses the same process but no table.get/table.set
• If the address of a local externref spills, we allocate a spot on the stack
  region of the __externref_table.
  • in the epilogue of the function, we use a table.fill to null out stack slots
    so we don't accidentally hold externref values alive
  • if the address doesn't spill, we still generate a wasm local
• codegen also supports global and local arrays

[hoodmane]

Also, as a side note the arrays support is sort of blocked on a fix for #69894 since in practice most uses of arrays will hit that bug.

[hoodmane]

I opened #203165 with a fix for #69894.

[llvmorg-github-actions]

@llvm/issue-subscribers-backend-webassembly

Author: Hood Chatham (hoodmane)

Details

A year ago I opened a draft pull request adding `__externref_t*` support: https://github.com//pull/163610 The idea would be that llvm gains a blessed `__externref_table` of externrefs, the analogue of `__indirect_function_table`. Dereferencing an externref pointer would turn into a `table_get` operation on that table. The table could have a stack region and a heap region. If a pointer to an externref is taken inside of a function, the externref could spill to the stack, so we would bump the stack pointer down 1, use a `table_set` to assign the externref into the table, and then the address of the externref would be the table index. In the epilogue, we'd use a `𝗍𝖺𝖻𝗅𝖾.𝖿𝗂𝗅l` instruction to null out the stack references and then restore the stack pointer. For heap references, we could have `__externref_t* table_alloc(void)` and `void table_free(__externref_t*)`.

This would allow graceful handling of:

• externref in a struct
• externref arrays
• externref in a varargs
• functions with multiple externref return values
  with the same ergonomics as normal pointers. Currently all of this stuff works, but the ergonomics are poor and each library has its own ad-hoc handling of these problems so there is no globally agreed-upon notion of an externref pointer.

The biggest problem is that currently static __externref_t blah[]; declares a table, and a table is represented in the clang IR as an array type. Because arrays freely decay to pointers, this means that clang currently interprets __externref_t* as coming from a decayed table and representing also a table. We will need some way to migrate the current behavior to the new behavior. I think tables ideally should be declared with an attribute e.g., __attribute__((wasmtable)) __externref_t table[]; so that pointers can be reserved for things that admit arithmetic, dereferencing, etc.

[QuantumSegfault]

On a side note, could we get [Wasm] and if it's not already there, [WASM] added to the automatic labeller?

I didn't see this one sooner (get notified about it) cause it didn't get labelled backend:WebAssembly and ping @llvm/issue-subscribers-backend-webassembly.

[dschuff]

@tlively here's the issue I mentioned today.

[antocuni]

Hello! Sorry for jumping in, but FWIW I'd also like to see this issue moving forward.
Context: I'm writing SPy which is a static-python-to-C compiler and supports many targets, including WASM (both WASI and emscripten).
I have an experimental jsffi module to interact with the JS world and I have essentially the same problems as pyodide, "how to represent JS objects on the C side"?
I can use externref_t but as soon as they need to spill I have to manually manage a table, which is essentially doing manually what I think/hope clang could to automatically.

As for compatibility, my compiler is extremely alpha state and AFAIK I don't have any users apart writing demos, so there are no compatibility concerns on my side.