extend with "unavailable" space

[axos88]

Hi!

I would like to have an extend method that allows to extend the heap with a space that is considered taken.
I'm working in embedded systems without MMU, so I have to work with raw memory spaces. I have three SRAM areas at 0x10000000 with the size of 16kB and at 0x20000000 with 2kB and 0x20004000 with 2kB.

Currently I can only define the global allocator to use the memory space from 0x10000000 to 0x10004000, because it's the largest continous block of memory. I would like to be able to add a "used" area at the end of size 0x2000000 - 0x10004000 = 0xFFFC000 with size of 2kB. This is invalid memory, so it should seem like already allocated space that is never read from or written to, but I should be able to add a 0x800 size free block after that. And another unavailable from 0x3800 and another free of 0x800.

If I see correctly the .extend method should be .... well extended with a parameter for wether the block should count as free space or as allocated space. It is already an unsafe function, so that's not an issue, but probably would need to add a guarantee that when defining a "used" space, that area will never be read from or written to by the allocator.

[axos88]

Unless freed of course, but that should not happen for invalid space, that's up to the application to ensure that.

[phil-opp]

The linked list allocator currently has no concept of used space. It is basically a linked list of memory chunks and every chunk in the list is considered unused.

I think a better solution to your problem would be to add an extend_with_region(start_addr: usize, size: usize) method. This would allow you to add the the additional memory areas since it doesn't require contiguous memory. One problem that this would cause is that the top method is no longer valid for a non-contiguous heap. To work around this, the Heap type could keep a non_contiguous flag and return an error from top in this case. I would be happy to merge a pull request that implements this.

If you don't care about the size and top methods, you can try that solution even without modifying this crate. Just call deallocate with the start of the region and a layout that specfies the region size. However, I wouldn't recommend this hack for anything other than experimentation.

[axos88]

Ah gotcha. I also implemented a linked list allocator a while back (during uni), but with a different memory layout, optimized for low memory overhead (only 4 bytes per used/unused block - based on your solution could be further improved to only require 4 bytes per free block), and i was expecting something similar here, but I'm starting to understand the differences between our implementations.

Where do you keep the metadata in memory? Where is the HoleList located? In my implementation it was before each block of memory, but I think you are keeping it in a separate place? How do you avoid having to preallocate space for it?

If the size and top methods are irrelevant, is there any other drawback that calling deallocate could cause? Why would you only recommend it for experimentation?

[phil-opp]

See https://os.phil-opp.com/kernel-heap/#creating-a-list-of-freed-blocks. Basically, we use the block itself as storage since we know that it is free. So the nodes of the HoleList are each stored at the beginning of the corresponding block.

If the size and top methods are irrelevant, is there any other drawback that calling deallocate could cause? Why would you only recommend it for experimentation?

The extend method is implemented like this:

https://github.com/phil-opp/linked-list-allocator/blob/620b8d121b1b3c496cd187cbc71ccd5f0763f0f9/src/lib.rs#L123-L129

If you use a custom address instead of top for the deallocate call, you can add an arbitrary region to your heap.

The reason that I recommended against it is that it violates the documented API (i.e. deallocate should be only used for freeing previously allocated blocks). While it works right now, future versions might change the implementation so that this approach no longer works. Also, if you accidentally use the top and size fields at some time in the future, you might cause errors. For example, by adding an additional memory chunk through deallocate and afterwards calling extend, the same memory chunk might be added twice to the allocator if the additional chunk is close to the top of the heap, which would cause undefined behavior.

[axos88]

Gotcha. Thanks for the answer!