DRC collector: use a better free list

[fitzgen]

We use a very simple, first-fit free list for allocation in the DRC collector right now:

wasmtime/crates/wasmtime/src/runtime/vm/gc/enabled/free_list.rs

Line 5 in 57ba95e

/// A very simple first-fit free list for use by our garbage collectors.

We should use something better, that has size classes and good hueristics and all that.

But also, we would ideally not write and maintain what is essentially our own malloc implementation ourselves, since getting all the details right and tuning them correctly for a variety of workloads is a lot of effort. The problem is that our malloc is outside the memory space that it is divvying up and parceling out: it is not inside the GC heap using and returning pointers within the GC heap, it is in the VM on the outside and is returning indices into the sandboxed region that makes up the GC heap, rather than pointers.

But... why not just compile dlmalloc (or something) to Wasm, have dlmalloc use the GC heap as its linear memory, and make GC allocations call dlmalloc's allocation and deallocation routines? That would give us a battle-hardened allocator that is most certainly faster than our free list pretty much For Free and with trivial long-term maintenance burden. Compiling dlmalloc to Wasm, with the right flags and exported symbols, results in a ~5-6 KiB binary that doesn't use any Wasm globals or funcref tables and uses only ~500 bytes of static data. It seems very doable.

This will rely on a lot of the same kind of infrastructure we want to have for compile-time builtins.

Random kinks to work out:

• Do we compile dlmalloc into every GC-type-using module, similar to trampolines? (Including modules that just use externref and not full Wasm GC.)
  • This means there would be some duplicate copies of the code when you load multiple GC-type-using modules in the system, which is fine from a correctness POV, but is undesirable from a disk space usage POV, and a memory usage POV if you're on a system without virtual memory.
• Or do we try and have only a single copy of dlmalloc in a system that is running multiple modules?
  • We could compile dlmalloc-gc-heap.wasm on demand the first time a gc-type-using module is compiled, but that requires that wasmtime was built with a compiler itself.
  • We could compile dlmalloc-gc-heap.wasm at Wasmtime build time and include_bytes!(...) it into the Wasmtime binary, but that means additional, bootstrap-y, cyclic dependencies where you need a wasmtime to build wasmtime.
  • We could require that configuring Wasmtime to use the DRC collector means you have to give a wasmtime::Drc object to the wasmtime::Config::collector method, and you can either wasmtime::Drc::new() when wasmtime is built with a compiler or wasmtime::Drc::from_serialized(...) otherwise. However, this raises questions about impl Default for Config since Config contains the configured collector, which by default is the DRC collector. Does it no longer impl Default when there is no compiler? Do we change the default collector when there is no compiler? Do we just remove that Default impl?

[alexcrichton]

This will rely on a lot of the same kind of infrastructure we want to have for bytecodealliance/rfcs#43.

I was thinking about this issue over the weekend I'm actually no longer certain that this is true. I believe that this can be implemented entirely independently of host builtins via a scheme such as:

• Add a new API requirement for Wasmtime that there's something along the lines of Engine::prepare_gc_implementation which compiles dlmalloc.wasm or deserializes it or similar. Basically an intentional step executed once at startup, after you have an Engine, which enables use of the GC. Trying to do anything GC-related before this is called just fails at runtime saying "go call that method"
• The GcRuntime implementations would have a Module which corresponds to dlmalloc.wasm. The new_gc_heap method would take a &mut StoreOpaque which could be used to instantiate the Module into the store, allocating the GC heap and such.
• The GcHeap trait would either stay as-is or optionally change to returning TypedFunc<..., ...> for various accessors (e.g. alloc would return a TypedFunc, maybe gc-ing as well?
• The GcHeap would store various VM* data structures in its "gc-specific data area" which is accessible from wasm, and the GcCompiler would use all of these.

Basically I don't think that any new trampolines are necessary, nor editing the compilation of any module. I think we could get away with this entirely with a Module stored in each GC implementation. Over time I think implementations like the current gc-or-maybe-grow logic would go entirely in GcHeap implementations to allow customizing that per-GC as necessary.