What should the memory layout look like for wasm modules?

[alexcrichton]

Currently wasm's linker, LLD, largely decides the memory layout for wasm modules and how items interact in the module's memory address space. We should either (a) decide that LLD's layout is ok or (b) figure out a different layout for ourselves and work with that!

Currently with LLD it looks like:

• Data by default starts at address 1024
• The stack starts one page (64k) above the end of data and grows down

That's quite a small stack! It looks like LLD has options to change the start of data --global-base but I don't see an option to change the stack. That probably needs to change! - turns out -z stack-size=1024

[Pauan]

Does LLD dynamically grow the stack at runtime? That might be why it's so small.

[alexcrichton]

AFAIK, no, it'll just run into global data and then underflow (causing weird corruption errors most likely!)

cc @CryZe (from our discussion today)

[CryZe]

The stack-size flag is supposedly just -z stack-size according to the source.

And no, it doesn't grow the stack from what I've seen. That wouldn't really work anyway, as even if it would somehow move the stack over, it would run into dlmalloc's memory, so that would be very bad.

So yeah on stack overflow it just corrupts all of the data sections.

[Diggsey]

Would it make more sense to put the stack at the bottom? That way if it overflows it will actually error (throw an exception in javascript's case) rather than corrupt stuff?

[CryZe]

Other things I've noticed while working on the wasm-to-rust compiler:

• All of the addresses from 0 to 1024 are completely unused, as Alex mentioned in the OP. That seems odd, as there's no protection against accesses to a null ptr (and short offsets) in the first place, so why waste 1 KiB of data.
• I wonder if we could make the stack size automatically fill up the page it is on. With the 1 KiB wasted + the 64 KiB default stack, we automatically need at least 2 WASM pages. However dlmalloc automatically assumes that it can't use any memory of the second page that the stack barely uses. Therefore the 63 KiB of the second wasm page here is entirely wasted. So I feel like the stack base should automatically round up to the end of that page possibly.

[CryZe]

@Diggsey yeah honestly that seems like a much better idea. I'm not sure how much of all of this is in our hands though.

[pepyakin]

I think, we don't have to have a 1024 bytes of memory just wasted for something. I think it has Emscripten roots.

Placing the stack at the bottom seems like a good idea. But when the last time I thought about it I realized that it would be a tradeoff.

I think the rationale of placing the data section is to make accesses to it more cheaper code-size wise, since I think the data section could have a quite a few places in which it accessed with a literal. And using numerically larger numbers make this values take more space, since literals use LEB128.

[alexcrichton]

Ah nice catch @CryZe! I updated the OP with how to configure the stack size.

cc @sunfishcode and @sbc100, y'all may be interested in this as well. The current question is whether for LLD + Rust a memory layout like this may make more sense:

0                          global-base            page boundary
|                               |                      |
|        call stack space       |	global data    |
|		  		|		       |

Or, in other words, we'd have something like:

• page boundary = align_up_to(sizeof(global data) + sizeof(call stack), page size)

And then the start of the stack would be something like:

• global-base = align_down_to(page boundary - sizeof(global_data), 16)

Do y'all have thoughts on a memory layout like that for wasm modules?

[BigBigos]

Just a (hopefully useful) note from a passing-by inexperienced Rust developer.

Isn't a null pointer already reserved for things like Option<Box> None value? Also, there exists Unique::empty() used by things like Vec or Box, which is basically a null pointer + alignof T, meaning that a non-null pointer that is small (like literal 4) might still have a special meaning.

Unless these invariants are changed, I don't think you can allow any valid pointer to go too much down the address space. If you put the stack there, you cannot really automatically detect the cases where the pointer ends up being null (or Unique::empty()), as these will happen before an underflow - each stack allocation would need to check for this explicitly.

[alexcrichton]

@BigBigos ah an excellent point! In that sense you'd expect that Some(&foo) was always Some, but if the address of foo, if on the stack, was then 0 it would cause problems (as it would print out None). While certainly quite unlikely, still plausible!

I think for other ones though with Unique::empty we'd be safe. It means that &Foo may have an address like 16, but all manufactured pointers at those locations have zero size so shouldn't be invalid (and valid pointers should otherwise continue to be valid I think?)

[BigBigos]

@alexcrichton not sure what you really mean about Unique::empty. It is defined to return a pointer that is never valid (i.e. never used by things that are dereferencable) but distinct from the null pointer.

It is implemented as null + alignof, so that this invalid pointer is at the very least aligned (not sure, but maybe it is needed for some sort of automatic pointer tagging, similar to how None automatically uses the null value). If we use i64 as an example, it has alignment of 8, so Unique<i64>::empty() returns pointer with an address of 8. It means that any valid i64 pointer that happens to have a value of 8 will be interpreted in a special way.

The users of Unique use the empty value to mark their pointers with some special semantics, e.g. Vec uses it to signify no allocation took place. In this case it should be safe, as Vec won't ever point to a stack-allocated memory, but I am not sure what the other users of Unique do with empty.

We could change the definition of empty for wasm (I assume it is possible to change its definition for a specific target) to null - alignof, i.e. to a very large number (in the case of Unique<i64> it would be 0xFFFFFFF8). I guess such pointers could still be encoded cheaply, as their signed magnitude is still small. We would then just have to make sure the page allocator never returns the highest page.

[alexcrichton]

@BigBigos hm do we actually rely on the value after Unique was constructed? I figured we'd always statically dispatch on sizeof(T) in contexts like Vec<T> rather than looking at the value of the pointer. In any case switching it all to use the high bits of the address space may also be reasonable!

[BigBigos]

@alexcrichton I think (if not - I apologize) you are confusing what empty means. I think the name is misleading - the function doesn't return an empty Unique value (whatever it would mean, as Unique is just a wrapper for a pointer) but a special value that is distinct from any other valid value and from a null value and is documented as a dangling value.

Unique<T>::empty is implemented for any T, even ones (or especially for ones) that have sizeof(T) != 0. The example before used i64 which has sizeof(i64) = 8.

Vec<T> uses Unique<T>::empty as a special marker that means no allocation took place. It is, among others, used by Vec::new() to initialize its internal Unique value. It means that if the Unique that is internal to Vec has the empty value, Vec will assume it has capacity of zero (so the pointer will never be dereferenced) and it should not be passed to the heap deallocate function.

Most such uses in other languages (like C) use a null pointer in this case (null pointer == the value is unitialized). Rust uses Option<T> for such cases which is then de-sugared into the same null pointer in case of None, but it is desirable not to use the null value so that Option<Vec<T>> can use it instead. In the end, it is just that there are 2 distinct special values - null and Unique::empty - that have a special meaning depending on context and should never represent a valid dereferencable pointer. In the case of Option<Vec<T>>, null means None, and empty means Some(Vec::new()).

As said before, it is not really a problem for Vec as the heap allocations it uses won't ever point to a stack address, i.e. the internal Unique object cannot be empty when initialized from heap allocation. But Unique definition is general enough that it could possibly be used by some other mechanism that could potentially use pointers originating from the stack (disclaimer - I don't know of any).