3 ms·

I did this too! Except it was based on the original TLSF paper (on which this work is based) as I wasn't aware of that offset allocator. > I'm also curious abo

by yvt 2y ago

I did this too! Except it was based on the original TLSF paper (on which this work is based) as I wasn't aware of that offset allocator. > I'm also curious about making something like this work as a general purpose allocator (as alluded to by the README). In a general purpose allocator, you can just store allocation metadata next to a payload so the lookup from a pointer address becomes O(1). The original TLSF algorithm (as proposed by the paper) was designed this way. Months later, I also wrote a general purpose implementation of TLSF for Rust `GlobalAlloc`, which, with some rigorous optimizations, turned out to be faster and smaller than every allocator for WebAssembly and embedded environments I tested, and it's still my go-to choice. It didn't fare too bad even when compared against modern thread-caching allocators in normal use cases. Internal fragmentation is probably worse, though.

ComputerGuru 2y ago
Have you published your code to GH, by any chance?
- yvt 2y ago
  Offset allocator: https://github.com/yvt/xalloc-rs/blob/master/src/tlsf.rs https://github.com/yvt/xalloc-rs/blob/master/src/tlsf.rs Don't mind the mess, it's one of my earliest works in Rust. General-purpose allocator: https://github.com/yvt/rlsf https://github.com/yvt/rlsf
scott_s 2y ago
> In a general purpose allocator, you can just store allocation metadata next to a payload so the lookup from a pointer address becomes O(1). Yes, but the downside is that now allocator metadata pollutes the cache. It's super efficient for the allocator, but it may harm efficiency of the actual use of that memory. I believe most production allocators don't use object headers for this reason.
- Someone 2y ago
  > I believe most production allocators don't use object headers for this reason. Isn’t the original reason hardening against buffer overflows? Overwriting allocator metadata can be used to attack a system.
  - pcwalton 2y ago
    Yes. I believe that the standard workaround for this problem is to place the allocator metadata for an entire block at some fixed address boundary, so you can just mask off the bottom K bits of an address to find the allocator metadata for the block, and from there find the metadata of the allocation you're concerned with.

by yvt 2y ago

ComputerGuru 2y ago

Have you published your code to GH, by any chance?

yvt 2y ago
Offset allocator: https://github.com/yvt/xalloc-rs/blob/master/src/tlsf.rs https://github.com/yvt/xalloc-rs/blob/master/src/tlsf.rs Don't mind the mess, it's one of my earliest works in Rust. General-purpose allocator: https://github.com/yvt/rlsf https://github.com/yvt/rlsf

scott_s 2y ago

> In a general purpose allocator, you can just store allocation metadata next to a payload so the lookup from a pointer address becomes O(1). Yes, but the downside is that now allocator metadata pollutes the cache. It's super efficient for the allocator, but it may harm efficiency of the actual use of that memory. I believe most production allocators don't use object headers for this reason.

Someone 2y ago
> I believe most production allocators don't use object headers for this reason. Isn’t the original reason hardening against buffer overflows? Overwriting allocator metadata can be used to attack a system.
- pcwalton 2y ago
  Yes. I believe that the standard workaround for this problem is to place the allocator metadata for an entire block at some fixed address boundary, so you can just mask off the bottom K bits of an address to find the allocator metadata for the block, and from there find the metadata of the allocation you're concerned with.