Metadata layout — alignment and large pages

[fengb]

Current design is reasonably simple and compact, but we have two major issues:

1. Alignment is fixed at double-usize (8 bytes). It'd be nice if we can at least align to 16 bytes, and this might give us up to 32KB alignment for "free".
2. Payload size of 2^n - 8 is super clunky. A lot of my personal usecases require 2^n exactly, and having this limitation requires an extra half page to a page.

[fengb]

Current	Compact	Extended
Align by double word only (8B)	Align by quad-word up to half page size (32KB)	Align by quad-word up to half page size
0B wasted	0B wasted	8B wasted per page
Must be 2ⁿ - 2*word	Must be 2ⁿ - 2*word	Can be 2ⁿ once per page
Extends to large allocations	how to support large allocations?	Extends to large allocations

[fengb]

I think the tradeoffs to extended are worth it. 8B per page is pretty minor compared with much better alignment, especially when large allocations can be 2ⁿ exactly.

The biggest complexity is mixing compact and extended free nodes — e.g. 8 vs 16 or 24 vs 32. Maybe the simpler solution is only use last 8B for large allocation metadata and waste 16B per small page.

Edit: possible compromise of the simpler solution — whenever we need a "small" page, try to allocate 2 pages instead. The 2nd will be carved up as a full 64KB allocation, while the 1st will only waste 8B. Of course this wastes 64KB of memory if we can't use it...

[fengb]

I think compact small pages + extended oversized pages makes the most sense. Assuming wasm 4 byte usize and 64 KB page sizes:

Small pages:

• alignment: 2ⁿ [16 bytes, 32KB]
• payload: 2ⁿ - 8 bytes
• first 8 bytes has meta stored in last 8 bytes

Oversized pages:

• alignment: 64KB
• payload: n * 64KB
• allocated with a "small page" right before it:
  • last 8 bytes holds meta for the oversized
  • first 8 bytes wasted
• note: side effect of this is no longer supporting "free list = page size" since page size will be oversized

[Theory] hybrid pages:

• alignment: 32KB
• payload: n * 32KB
• special usage of prepended "small page":
  • last 32KB is additional data
  • then 8 bytes holds the meta
  • first 8 bytes still wasted
• wastes fewer bytes for oversized pages
• 32KB is a special case where it's considered "oversized" but doesn't require 2 pages... I think this might be acceptable

[fengb]

Rethinking: I don't think we should have "compact" mode. It saves 16 bytes per small page at the cost of forking how the metadata is found. This can be especially bad if the sibling payload looks like frame metadata and the heuristics fail.

Edit: depending on the resolution to https://github.com/fengb/zee_alloc/issues/9, compact might be back on the table. If we allow std.WasmPageAllocator to handle jumbo, we need to bifurcate anyway and compact lets us maximize usage.