Memory usage optimization

[axos88]

Based on the discussion in #16:

I think the pointer in the Hole structure can be removed and calculated on the fly from (&this as usize) + this.size.

Any reason we are not doing that?

[phil-opp]

I don't think this will work. Consider https://os.phil-opp.com/kernel-heap/overview.svg: The size of the unused memory block is completely independent from the size of the used memory block afterwards.

Basically, the size field stores the size of the unused block, and the pointer implicitly stores the size of the unusable memory block that follows.

[axos88]

This is only in case there is padding due to alignment requirements isn't it? I'll have to look it up how I solved this issue.

[phil-opp]

If you keep track of both used and unused chunks, you can use this approach. However, if you only keep track of unused chunks, there is no way to know where the next unused block begins without storing a pointer.

[axos88]

Well you don't really care about used chunks, since they're not available. And whenever somebody claims to try to free up a chunk, the allocator gets both the address, and the layout of said chunk, and blindly obliges, creating a new chunk (or extends a previous or next one, if the freed up memory are neighbours another free chunk). This would mean that an incorrect call (freeing up nonclaimed space, or double frees) would create corrupt the heap and cause chaos, but that's already the case, isn't it?

[phil-opp]

This would mean that an incorrect call (freeing up nonclaimed space, or double frees) would create corrupt the heap and cause chaos, but that's already the case, isn't it?

Yes, it is. Even a deallocate call with a valid address can cause undefined behavior due to use-after-free.

Well you don't really care about used chunks, since they're not available.

Yes, that's why this crate only keeps unused blocks in the list. I just don't understand how we can remove the pointer in the list nodes.