Support the `custom-page-size` proposal in `Talckwasm`

[anlavandier]

Support the custom-page-size proposal in Talckwasm

The WebAssembly custom-page-sizes proposal allows Wasm modules to have page sizes of either 65536 or 1.

It is in implementation phase and supported by the runtimes wasmi and wasmtime.
It has also recently been added to the LLVM linker wasm-ld so it's now possible (albeit annoying) to compile Rust Code to WebAssembly while using this proposal.

I am using this proposal for my wasm files because I'm working on running wasm on architectures where 64KiB of RAM is hard to come by and 128KiB is not happening. I'm also using talc because afaik it is the only maintained allocator that advertises WebAssembly apps as a usage scenario.
Currently, I am using a static arena but I'm thinking that using a grow-able heap would allow me to use less RAM in most contexts.

I am willing to work on this (It should only be a matter of a few lines of code anyway) but I would like your opinion on this before I do anything.

[SFBdragon]

Talc is finally in a state to be accepting contributions normally again. Would be great to do so in the near future between 5.0.0-beta.2 (currently released) and 5.0.0 when we've got an opportunity for breaking changes.

I'm not too familiar with what support for custom page sizes in Talc looks like in terms of changes yet though.

For example, currently PAGE_SIZE is hardcoded as 64KiB I believe. That needs to change depending on the custom page size, but I'm not sure where to "get" that value for the current compilation target or runtime or however it works.

[max-dau]

I am also interested in using talc for allocation in WebAssembly programs with the custom-page-sizes proposal as @anlavandier explained (I suspect this is for the same project @anlavandier had in mind when opening this issue). I have been looking into the talc source code a bit and have adjusted it to work with dynamic allocation in WebAssembly programs using 1 byte pages in my testing.

Here is what I needed to do to make it work:

As @SFBdragon wrote, this required setting PAGE_SIZE to 1 and additionally required ensuring that allocations aren't too small. This previously happened implicitly because at least one 64 KiB page was allocated every time, where one 1-byte-page does not seem to be enough space anymore. On commit a7a0516ca2bd0aa535c1ec6e7e996a98366b90a8 (around version 4.4.3), there was a comment stating that "delta_pages is always greater than zero, thus one page is enough space for metadata, therefore we can unwrap the result". This comment is not present on the current version anymore, but the logic is the same. Issues arising from this can be mitigated by e.g. ensuring that some lower bound of space is allocated (it works with 1 KiB in my testing, but I haven't looked into what would be a more sensible value/what the minimum is, so far I only have this quite hacky version).

@SFBdragon If you're still interested in having this feature added, I would be happy to put some more thought into how to integrate the proposal in a non-hacky way and fitting nicely into the current version of talc (especially without requiring a major version increase) and look into this more precisely. I'm open to any ideas and would like to hear any more thoughts you may have.

[SFBdragon]

Hi @max-dau - thanks for letting me know there's still interest in this.

Currently, Talc should be fully capable of supporting this with a custom Source (previously, OomHandler) implementation.

The current WASM-specific Sources (e.g. WasmGrowAndExtend) assume a 64KiB page size, but there's nothing specific to 64KiB baked into Talc.

That said, I'm keen on Talc providing useful Source implementations that aren't too niche, and supporting custom-page-sizes out of the box sounds like a good feature to have.

---

On telling Talc the page size.

The implementation changes are easy. The only problem is that I don't know which interface alteration is right. This hinges on two questions.

1. Will Talc foreseeably need to concern itself with handling WASM page sizes other than 1 and 64KiB?
2. When and how is the page size determined. i.e. at dev time by the programmer (one application always targets one page size), at compile time by the compilation target (builds are specific to a page size), the WASM runtime (executions are specific to a page size), or during execution (the page size can change during execution? probably not).
   • The corollary of this being "in what ways can this be specified to Talc" - a cfg arg? a const generic parameter? a normal parameter? etc.

Unfortunately I don't have the time to research this myself right now. I'm hoping devs who've spent more time in this area will have more insight here.

---

Aside: On configuring Talc for such a constrained system

Just for reference, the default binning strategy on WASM...

talc/talc/src/wasm.rs

Lines 7 to 35 in b55d533

	/// A binning configuration optimized for WebAssembly.
	///
	/// Why does WebAssembly get its own bin config?
	/// - `wasm32` has instructions for 64-bit numbers, which requires
	/// less instructions than using two `usize`s for the availability bitfield.
	pub struct WasmBinning;
	impl Binning for WasmBinning {
	#[cfg(not(target_arch = "wasm64"))]
	type AvailabilityBitField = u64;
	#[cfg(target_arch = "wasm64")]
	type AvailabilityBitField = [usize; 2];
	fn size_to_bin(size: usize) -> u32 {
	#[cfg(not(target_arch = "wasm64"))]
	{
	crate::base::binning::linear_extent_then_linearly_divided_exponential_binning::<2, 8>(
	size,
	)
	}
	#[cfg(target_arch = "wasm64")]
	{
	crate::base::binning::linear_extent_then_linearly_divided_exponential_binning::<4, 8>(
	size,
	)
	}
	}
	}

...doesn't really suit your needs very well. The metadata for this takes.. 64 buckets * 1ptr/bucket * 4 bytes/ptr = 256 bytes, the range is high, and bucket density is quite low.

This'll work better.

/// Optimized for 128KiB of available memory.
/// Uses 32*4=128bytes for metadata.
/// This is much more dense than the default, which should result in less memory fragmentation.
/// The sacrifice is that this isn't suitable for arenas of ~512KiB+ of memory.
/// Use https://github.com/SFBdragon/talc/blob/b55d533df498d9e5c29ffecc71c0580d390c6fdd/talc/examples/bucket_ranges.rs
/// to try different bucketing strategies if you like. Compile for i686 for correct word size, or divide all the sizes by two on a 64 bit machine.
/// The goal is to cover up to perhaps 10-25% of your arena size as densely with buckets as possible.  
pub struct SmallWasmBinning;
impl Binning for SmallWasmBinning {
    type AvailabilityBitField = u32;
    fn size_to_bin(size: usize) -> u32 {
        /// <2, 8> is less dense but has a higher range if the available memory might be 256KiB-1MiB. 
        /// <4, 1> is better for allocations in the 0.5-8KiB range
        crate::base::binning::linear_extent_then_linearly_divided_exponential_binning::<4, 1>(size)
    }
}

I'm not really sure what your ideal speed vs size tradeoff looks like.

[max-dau]

Thanks @SFBdragon, that's very interesting. I have some quick thoughts on telling Talc the page size:

About point 1/possible future Wasm page sizes: The proposal @anlavandier linked above quite explicitly states that it is written in a way to enable any power of two to be chosen as the page size in a possible future version: "The encoding and spec are factored such that we can relax this to allow any power of two between 1 and 65536 (inclusive) in the future, should we choose to do so."

About point 2, I can only talk about my own usage with the TreVM project. There, using 1-byte-pages is an argument passed when building the .wasm file. With this in mind, I'm not sure how the page size would best be passed to Talc without adding unnecessary complexity.
The Wasm runtime (at least for Wasmtime) also needs to have this proposal enabled when executing the program, which is a configuration option of the per-engine configuration Config, but I do not believe this matters for Talc.