Wasm Support

[kateinoigakukun (Yuta Saito)]

@Joe_Groff Thank you for taking a look!

Is it possible to take the addresses of functions relative to some other per-module reference point?

In dynamic-linking context, there is a per-module base offset of function addresses within a module, named __table_base. https://github.com/webassembly/tool-conventions/blob/main/DynamicLinking.md#interface-and-usage

Using the GOT unconditionally would maintain consistency with other platforms, but is overall less efficient than using absolute addresses in the first place, so if it's possible to still get some benefit from the 32-bit direct relative representation.

Right, using 32-bit absolute addresses is a more efficient way in both performance and binary size aspects than unconditional GOT and relative address.
However, we did some quick benchmarks and found no significant regressions in either binary size or performance, and concluded that the ease of maintenance due to consistency and portability among 32 and 64 bits outweighs the disadvantages of its small regression.

If the PR will be merged to the main, it would be a big step toward official Wasm support

[Joe_Groff]

@kateinoigakukun

Right, using 32-bit absolute addresses is a more efficient way in both performance and binary size aspects than unconditional GOT and relative address.
However, we did some quick benchmarks and found no significant regressions in either binary size or performance, and concluded that the ease of maintenance due to consistency and portability among 32 and 64 bits outweighs the disadvantages of its small regression.

If the PR will be merged to the main, it would be a big step toward official Wasm support

That's good to hear. I don't mind unconditionally using the GOT for now, since that doesn't preclude adding a more direct representation in the future.

To that end: given a pointer to constant data from a module, such as a type descriptor or other Swift metadata, is there a way to recover the corresponding __table_base for the same module, so we could represent a reference to a function as either its index into the same module's table, or its relative location in the GOT?

[John_McCall]

I do have some objections to always using indirect relative references, because there are places where we currently assume we can always use a direct relative reference which would have to be changed to allow an indirect relative reference. And I think it's very common for us to do that with references to code, especially since we cannot portably distinguish direct and indirect relative references to code by using low bits because of things like e.g. the THUMB indicator bit.

The performance of reading relative references is not very important; generally, once we enter the runtime, we're already off the fast path.

It sounds like the problem here is purely around Wasm's support for PIC. There's no fundamental problem with cross-address-space relative references; the difference just needs to be as wide as the maximum of the two address spaces. Of course, you have to statically know it's a cross-AS reference in order to interpret it correctly, but that's no different from how you have to know the AS of an absolute pointer. But it sounds like Wasm does PIC by allowing text and data to slide independently (reasonable enough for a Harvard architecture), and that does break the idea of cross-address-space relative references; we need something else.

As Joe alluded to, the best approach for most of our data->text references, in terms of both compactness and avoiding load-time relocation, would be image-relative addressing. Everywhere that currently uses a cross-address-space relative reference would instead use the image-relative address of the target function (&f - __table_base). (Recall that relative references always point within an image.) So to resolve a data->text "relative reference", you would have to look up the __table_base for the image containing the reference, and then add that. That would be a relatively slow operation, but for the relative data->text references used in Swift metadata, that's probably fine.

However, not every data->text reference in Swift is on the slow path. The most important counter-example is async function pointers; we would not want those to have to do a __table_base lookup every time we made an indirect async call. But it would be relatively painless to change the ABI for just those so that they stored an absolute pointer on Wasm targets instead of a relative one.

In the short term, do we actually need to support targeting PIC Wasm? Or is the immediate problem that the object formats don't support things at all if they wouldn't work in PIC?

[kateinoigakukun (Yuta Saito)]

@Joe_Groff

given a pointer to constant data from a module, such as a type descriptor or other Swift metadata, is there a way to recover the corresponding __table_base for the same module

@John_McCall

As Joe alluded to, the best approach for most of our data->text references, in terms of both compactness and avoiding load-time relocation, would be image-relative addressing. Everywhere that currently uses a cross-address-space relative reference would instead use the image-relative address of the target function ( &f - __table_base ). (Recall that relative references always point within an image.) So to resolve a data->text "relative reference", you would have to look up the __table_base for the image containing the reference, and then add that. That would be a relatively slow operation, but for the relative data->text references used in Swift metadata, that's probably fine.

If I understand correctly, there is no way to obtain the corresponding module's __table_base from an address of a constant data in the module without extra dynamic loader support (for __table_base lookup). This is because the __table_base is intended to be used to resolve dso_local symbols in their module (at least for now).
So we need to extend the dynamic linking ABI of Wasm if we will use image relative reference. Fortunately, there is already a relocation type to calculate &f - __table_base named R_WASM_TABLE_INDEX_REL_SLEB.

@John_McCall

I do have some objections to always using indirect relative references, because there are places where we currently assume we can always use a direct relative reference which would have to be changed to allow an indirect relative reference. And I think it's very common for us to do that with references to code, especially since we cannot portably distinguish direct and indirect relative references to code by using low bits because of things like e.g. the THUMB indicator bit.

Right, data->text reference cannot be represented with RelativeIndirectablePointer portably. So we switch RelativeIndirectPointer and RelativeDirectPointer by targets in our fork.

Runtime: support indirected relative func-ptr for harvard archs

@John_McCall

However, not every data->text reference in Swift is on the slow path. The most important counter-example is async function pointers; we would not want those to have to do a __table_base lookup every time we made an indirect async call.

Ah! Certainly. I forgot that async function pointer is a pair of relative function pointer and context size.

@John_McCall

But it would be relatively painless to change the ABI for just those so that they stored an absolute pointer on Wasm targets instead of a relative one.
In the short term, do we actually need to support targeting PIC Wasm? Or is the immediate problem that the object formats don't support things at all if they wouldn't work in PIC?

Fortunately, I found that the size of function address of both wasm32 and wasm64 is 32bit (but it's under discussion), so we can store absolute function pointer instead of relative one without breaking metadata layouts.

So the options here are:

1. Absolute function pointer
   • Pros:
     • No load & fixup at pointer resolution
   • Cons:
     • Overhead of load-time relocation in PIC-mode
     • Very Wasm specific solution because no other major arch has 32bit function address in both 32- and 64-bit mode.
2. Image relative function pointer
   • Pros:
     • No load at pointer resolution
     • No load-time relocation even in PIC-mode
   • Cons:
     • Extending dynamnic-linking ABI is required
3. Unconditional indirect relative function pointer
   • Pros:
     • Portable across other Harvard architectures with independent AS
     • Load-time relocation is grouped together in GOT region in PIC-mode
   • Cons:
     • Load at function pointer resolution
     • Extra GOT space

As you said, it seems the ideal approach is the "Image relative function pointer" considering both PIC and non-PIC modes.
But for now, dynamic-linking ABI is unstable and most of the runtimes don't support it, so we can ignore PIC-related pros and cons in the short term. And if we can accept the non-portability of the function pointer size, "Absolute function pointer" seems the most simple and efficient approach.
I preferred "Unconditional indirect relative function pointer" approach for its portability, but I'm OK with both approaches now.

Which approach do you prefer as a short term approach?

[John_McCall]

@kateinoigakukun

If I understand correctly, there is no way to obtain the corresponding module's __table_base from an address of a constant data in the module without extra dynamic loader support (for __table_base lookup). This is because the __table_base is intended to be used to resolve dso_local symbols in their module (at least for now).
So we need to extend the dynamic linking ABI of Wasm if we will use image relative reference.

Yeah. The loader probably has this information lying around already, but it'd require an API to expose it.

@kateinoigakukun

Right, data->text reference cannot be represented with RelativeIndirectablePointer portably. So we switch RelativeIndirectPointer and RelativeDirectPointer by targets in our fork.

Mmm. Makes sense. Of course we can't just do that when Wasm is upstreamed — we'll have to abstract it so that different targets can use different relative-pointer ABIs.

@kateinoigakukun

Fortunately, I found that the size of function address of both wasm32 and wasm64 is 32bit (but it's under discussion), so we can store absolute function pointer instead of relative one without breaking metadata layouts.

Interesting. I hadn't actually realized there was a wasm64 effort.

I assume the natural representation of function pointers in Wasm is just an index into a table, since there's no reason to represent them as taking up a range of memory. 4 billion separate functions does seem like a reasonable cap.

Does the toolchain support doing a bit-shift on R_WASM_TABLE_INDEX_REL_SLEB, so that we can e.g. distinguish direct and indirect references, or absolute and relative references? I assume not. So we'd either need to find a way to store that bit separately (which we do for protocol references, but not for most of these places) or we'd need to do whatever we decide here unconditionally.

[kateinoigakukun (Yuta Saito)]

@John_McCall

Mmm. Makes sense. Of course we can't just do that when Wasm is upstreamed — we'll have to abstract it so that different targets can use different relative-pointer ABIs.

We are concerned about that. What kind of abstraction is acceptable?
Is it unacceptable to switch data structures between targets in the first place? Or is it OK if we can switch between them with template <Runtime> or #if SWIFT_INDIRECT_RELATIVE_FUNCTION_POINTER like SWIFT_PTRAUTH does?

@John_McCall

Does the toolchain support doing a bit-shift on R_WASM_TABLE_INDEX_REL_SLEB, so that we can e.g. distinguish direct and indirect references, or absolute and relative references? I assume not.

Do you mean we can assume the table index is less than 1 << (31-n) and use n bits for the flag?
(Sorry, I was confused. R_WASM_TABLE_INDEX_REL_SLEB is for instruction immediate encoded by LEB128, so it cannot be used in data section. )

@John_McCall

So we'd either need to find a way to store that bit separately (which we do for protocol references, but not for most of these places) or we'd need to do whatever we decide here unconditionally.

As far as I tried, most of places can determine whether a relative pointer is function pointer or data pointer at compile-time, so we can distinguish absolute/relative or indirect/direct without embedding the isIndirect or isRelative bits in pointers. (Am I missing something? Do we still need those flags for some purpose?)

The exceptions are symbolic reference, protocol witness, vtable entry (to distinguish async function pointer and normal function pointer), but they have enough information to determine their pointer type in flags beside the pointer field.

[John_McCall]

@kateinoigakukun

We are concerned about that. What kind of abstraction is acceptable?
Is it unacceptable to switch data structures between targets in the first place? Or is it OK if we can switch between them with template <Runtime> or #if SWIFT_INDIRECT_RELATIVE_FUNCTION_POINTER like SWIFT_PTRAUTH does?

template <Runtime> would be the way to do it: we’d identify runtimes that want to use alternatives to relative pointers in some way and make the runtime abstraction substitute the right information. And then InProcess would ultimately use #if, yeah.

@kateinoigakukun

Do you mean we can assume the table index is less than 1 << (31-n) and use n bits for the flag?

Well, it’s an option, if not necessarily an appealing one. Does that instruction format limit the range of the function, or does it encode a full 32 bit-immediate?

Let me step back and state where I think we are now. I always think it's valuable in this kind of project to first try to figure out the best thing we could do, so we know where want to end up. Once we've done that, then we can decide about how we want to get there.

Relative references on other targets don’t really have many significant trade-offs: they're nearly as cheap to access as absolute references, and they're substantially smaller (on 64-bit targets), and they don't have load-time or binary-size overheads. As a result, there isn’t much reason to avoid using them whenever possible in our constant metadata, especially since we expect PIC to be the common case: even executables are PIC on Darwin, and that seems to be where other OSes are headed as well, albeit somewhat slowly.

But as we’re figuring out here, the trade-offs are clearly different on Wasm, even with a perfectly cooperative toolchain: relative references from data to code aren’t possible in PIC, and the natural alternative (image-base-relative references) will require a runtime lookup that completely changes the cost profile. And I believe we also expect that the dominant code pattern on Wasm will not be PIC, and the general rule is that uncommon cases shouldn't greatly burden common cases. Therefore, we need to take the trade-offs of relative references more seriously on Wasm than we do elsewhere.

I think what that suggests is that we should be using absolute references in a lot more cases when targeting Wasm. Since data-to-data relative references are still okay, and they have size benefits on Wasm64 (and load-time/code-size benefits in PIC), we might as well continue to use those everywhere we do now. But data-to-code references should probably either be (1) unconditionally absolute or (2) somehow discriminated between absolute and either image-base-relative or indirect-relative, similarly to how we discriminate between direct and indirect relative in other places on existing targets.

Now, going unconditionally absolute for data-to-code references would have costs for PIC. The immediate question is how much this matters. If PIC on Wasm is expected to just be used for things like dynamic plugins, then this seems very low priority. But if people expect Wasm to have a robust shared library system, then we need to treat PIC as seriously as we do on other targets.

If we want to maintain the benefits of relative references in PIC while using absolute references in non-PIC, we'll need to dynamically distinguish absolute from relative references. The easiest way to do this is to use a bit in the reference, but as discussed, we may not be able to do that without constraining the range of references (unless it's already constrained by the instruction format). Otherwise, we'll have to go one-by-one through all the places that currently store data-to-code relative references and see if they have an external bit we could use to distinguish these cases. I suspect a lot of them do.

If we're going to embrace absolute data-to-code references from metadata, it also matters a lot whether Wasm64 ends up adopting 64-bit code pointers. (That really does seem extremely high given their representation, but if it's what the project decides, it's what they decide.) We might end up wanting a "code model" sort of thing where we usually emit 32-bit references but have the ABI ability to fall back on 64-bit references (with some sort of indirection) if requested. Ideally, this would be integrated with the linker such that the linker could turn an indirect reference into a direct one when the pointer value is small enough. But we're not likely to get the level of cooperation we would need to do this in the linker if the discriminator is stored separately from the reference.

[kateinoigakukun (Yuta Saito)]

Thank you for summarizing our discussion! It's far clear and reasonable from my first proposal.

@John_McCall

I think what that suggests is that we should be using absolute references in a lot more cases when targeting Wasm.

I totally agree with this direction. And it's relatively low priority to minimize costs on PIC as you said.
So we will upstream iteratively by the following steps.

1. Upstream unconditional absolute addressing
2. Evolve the toolchain for PIC support and linker for fitting 64bit address in 32bit field by the time when wasm64 and dynamic linking ABI will become stable
3. Adopt 64bit and PIC based on the evolution

(A little bit off-topic about possible compact function pointer ABI)

This is just a thought. We can think like the following layout which embeds discriminator bits, `isSmall` and `isPIC`, in a 32bit to utilize absolute pointer and relative pointer.

32        31      30                           0
 | isSmall | isPIC | value (offset or address) |

// How to resolve absolute pointer
switch (isSmall, isPIC) {
case (true, false):
    // absolute address is smaller than 30bits and non-PIC
    // -> direct pointer
    return value
case (true, true):
    // image-offset is smaller than 30bits and PIC
    // -> image-relative direct pointer
    return __table_base + value
case (false, false):
    // absolute address is large over 30bits and non-PIC
    // -> relative indirect pointer
    return *(value + (*(uint32_t *)value))
case (false, true):
    // image-offset is large over 30bits and PIC
    // -> relative indirect image-relative pointer
    return __table_base + *(value + (*(uint32_t *)value))
}

To build such layout, linker needs to relocate by falling back to indirect pointer and create indirection table entry if address of a function symbol in the image does not fit in 30 bits, as you suggested. This condition can be determined before data segment layout because linker can layout code section independently, and can know the actual address (or image-relative offset in PIC) of the function symbol. if function address depends on data segment layout, inserted indirection entries can offset function addresses, then can toggle isSmall flag. That would complicate linker's memory layout as you can imagine. So I think this design is linker friendly in our situation.

[John_McCall]

@kateinoigakukun

Upstream unconditional absolute addressing

Sounds good. Just for data-to-code references, right?

@kateinoigakukun

Evolve the toolchain for PIC support and linker for fitting 64bit address in 32bit field by the time when wasm64 and dynamic linking ABI will become stable

Please do push the dynamic-linker people to add an easy image-base lookup function.

@kateinoigakukun

Adopt 64bit and PIC based on the evolution

Sounds good.

@kateinoigakukun

We can think like the following layout which embeds discriminator bits, isSmall and isPIC, in a 32bit to utilize absolute pointer and relative pointer.

Yeah, I like this quite a bit.

[kateinoigakukun (Yuta Saito)]

@John_McCall

Sounds good. Just for data-to-code references, right?

Yeah, right

[kateinoigakukun (Yuta Saito)]

Hi there!
We are recently working on upstreaming patches and most of the essential patches around the compiler are already upstreamed now.

One of the remaining key patches is about the KeyPath accessor calling convention, which I mentioned 3 years ago Wasm Support - #21 by kateinoigakukun
Last week, I opened a PR to resolve the issue and also unlock some optimization opportunities in general. But I'm looking forward to hearing feedback from the compiler people on the design that adds SIL function conventions for each keypath accessor type before merging.

Thank you in advance

kateinoigakukun

[kerimcharfi]

Hi there,

I'm experimenting with dynamic linking by tinkering around with lld and I need your help.

My current situation:

1. I compiled a "main module" containing the runtime, disabled dead code elimination and exported all symbols.
2. Next I compiled a "side module" without the runtime by simply deleting the archive file from the toolchain and importing all undefined symbols.
3. Next I compiled another "side module"

I changed tablebase and global base so that the modules dont overwrite each other.

It actually works somehow, but I'm facing undefined behaviour when I'm defining CustomReflectable in the first side module and using it in the second side module.

When I'm compiling the first side module with the runtime and the second sidemodule without, it works.

This is the error I'm getting right now (changes depending on what the CustomMirror is)

And I have also witnessed a decrementing number at 260 offset from global base of the side module.

Both are compiled with --emit-executable because shared library is disabled. Could this have an effect?

Can somebody give a brief overview over what the linker would have to generate in the data relocation function to make this protocol conformance work (or metadata layout in general) in the current state of swiftwasm in the described scenario above?

What happens inside call $swift_addNewDSOImage ? Does this function need to be changed?

Thank you in advance

[Max_Desiatov]

Do some of your dynamically linked modules have their own linear memory declared? Could it be that one of them is holding a pointer to a linear memory it doesn't have access to and then tries to read from wrong memory instead? IIUC for dynamic linking to work with SwiftWasm you'll need to have one memory instantiated presumably by the executable module, and the rest of the modules would just import it.

Tooling conventions for Wasm dynamic linking are described in the corresponding document, is your build process following those?

[kerimcharfi]

Thank your for your response.
All modules use the same function table and the same memory.
I have looked at the convention you mentioned, but this is more of a POC and i'm not changing so much so i'm currently not following it strictly. I'm not even using PIC for now. The location of the sidemodules is predefined by setting __memory_base at compile time.
But as im reading this: does a custom __memory_base need to be somehow aligned? I was randomly using default for my main module, 15_000_000 for my first sidemodule and 30_000_000 for my second sidemodule so that they dont overwrite each other .