Assemblyscript: Implement a memory manager

[dcodeIO]

Memory management is pretty much a filler currently and consists of a large linear chunk of non-disposable memory.

Ref: std/assembly/heap.ts

API is:

• allocate_memory(size: usize): usize
  Pretty much like C's malloc.
• free_memory(ptr: usize): void
  Pretty much like C's free.

Requirements are, in this order:

• Should be correct
• Should be efficient
• Should be small

TLSF seems to be a viable candidate.

Useful resources:

• TLSF: Memory allocator real time embedded systems
• Two-Level Segregated Fit memory allocator implementation.

[dcodeIO]

See: examples/tlsf/assembly/tlsf.ts

Feel free to do excessive test-runs if you have some spare time :)

[MaxGraey]

Hi, which kind of problem with TLSF implementation now?

[dcodeIO]

Something appears to be odd about the code currently. Whenever a new block is allocated, it appears that it loses track of all the previous blocks. Or something like that, not sure, but it always grows the memory even if just two small blocks are allocated, which is an indicator for something going haywire. Another thing is that adding a memory pool adds that sentinel block, which seems to be invalid according to check, but I might be mistaken there.

My last attempt was to make an html page that visualizes all the stuff that's going on, by reimplementing check on the JS side and drawing its results, but well, I'd probably have to clone myself to be able to solve all of this alone. Hence, help appreciated :)

[MaxGraey]

Hmm, I think first of all I try to implement and visualize this by transpiling to javascript whole tlsf code for easer debugging. If all will be correct that mean problem in some part of compiler

[dcodeIO]

That's a good plan as well, yeah

[dcodeIO]

The latest commit added a re-implementation of TLSF that, according to its test, works properly. There'll most likely be additional optimization opportunities, though, and when growing memory it doesn't yet coalesce pages, but that should be trivial to add. One more thing to think about are aligned allocations, for instance when allocating memory for a class that starts with an 8-byte long field.

[MaxGraey]

Excellent job!
Definitely classes should be 8-byte aligned for efficiency. But implement this in tlsf maybe little tricky. I'm not sure this good fit for example: https://github.com/esmil/musl/blob/master/src/malloc/memalign.c#L10

[dcodeIO]

Yeah, 32-bit TLSF has the inconvenient property of having a 4-byte block header. Still thinking about more efficient solutions than splitting away MIN_SIZE-sized small blocks on alignment misses.

[MaxGraey]

What do you think, is this ready for dynamic object allocation? Except 8-byte alignment of course

[dcodeIO]

According to this test setup, yes (i.e. run npm run test:forever).

[MaxGraey]

Yes. Test was passed. Great work! So can we focused on dynamic object creation such as arrays?

[dcodeIO]

Once there is a GC implementation, yes. For testing purposes, it's also ok-ish to use the arena allocator. A specific allocator can be set by including one in the entry file, like import "allocator/arena"; or import "allocator/tlsf";.

For reference, without a GC, something like return aString + otherString would never clean up their memory.

[MaxGraey]

Ok, will try to using this approach. Actually I want just test some wasm generation with compare to rust and needs in arraylike entity.

[dcodeIO]

Ok, we have several memory allocators now: TLSF, Buddy and Arena. These all pass their tests and all align to 8 bytes, so I'm going to close this issue. Next steps: Optimize them where beneficial and figure out GC.