dfinity
feat: Support memory freeing
@dragoljub-duric @hpeebles @dsarlis I'm not sure we'd want to merge this solution to support memory freeing.
With the expansion of stable memory, we now have another issue to solve: we have ~32k buckets, and with a default size of 8MiB per bucket, the memory manager can only manage 256GiB of memory. I bet most people don't know this, assuming that they have access to the full 400GiB (or is it 500 now?). This is a foot gun that we should resolve, and resolving this would require increasing the number of buckets.
In order to both increase the number of buckets and to support memory freeing the future, we'll have to update the memory manager in such a way that its header can span, say, two wasm pages, as opposed to one wasm page. And, if we have two wasm pages, then we won't need to represent buckets using 15 bits as we're doing in this PR, which is adding more complication than it's worth imho.
We could keep the header as a single page, store each bucket in the linked list as 3 bytes (which could support up to 16777216 buckets), and if additional buckets are needed, we use the unused space in the header to point to the page where the subsequent buckets are defined.
Then on each page of buckets is a pointer to the next page.
This way we can support far more buckets than anyone would ever need, the header remains small in most use cases, and we wouldn't need to move the existing data in the first memory page after the header.
Having thought about this a bit more I think my idea to store bucketIds as 3 bytes is wrong. If we support spreading buckets onto more pages, then storing them as 3 bytes is an unnecessary storage optimisation at the expense of code complexity. I think storing buckets as u32s is the way to go. The first page could then store something like 8192 buckets in the last 32768 bytes (using the format I introduced in this PR where the entry at each bucket's index points to the next bucket in the linked list). Follow on pages used to store buckets could then store 16384 per page. The first page then just needs to somehow store where the additional pages are. If my calculations are correct then using the format above we'd have 30178 bytes available within the first page to encode the additional bucket pages and any metadata we may need on each one.