11–20 of 30 posts
The real question is: how does this deal with freeing allocations from a thread that exited ? The implications of thread lifetime seems to be one of the biggest differences between existing allocators.
I mean, how would the thread know that the memory needs to be freed? It cannot know that the application hasn't ROT13 encoded the pointer, passed it to another thread, and that thread plans to use the memory.
The real question is: how does this deal with freeing allocations from a thread that exited ? The implications of thread lifetime seems to be one of the biggest differences between existing allocators.
Don't all thread implementations leak unfreed memory when a thread exits? I mean, how would the thread know that the memory needs to be freed? It cannot know that the application hasn't ROT13 encoded the pointer, passed it to another thread, and that thread plans to use the memory.
Are there any benchmarks?
https://github.com/microsoft/snmalloc/blob/main/docs/securit...
> Some architectures, such as CHERI (including Arm's Morello), explicitly consider pointer provenance and bounds in addition to their target addresses. Adding these considerations to the architecture enables software to constrain uses of particular pointers in ways that are not available with traditional protection mechanisms. For example, while code may have a pointer that spans its entire C stack, it may construct a pointer that authorizes access only to a particular stack allocation (e.g., a buffer) and use this latter pointer while copying data. Even if an attacker is able to control the length of the copy, the bounds imposed upon pointers involved can ensure that an overflow is impossible. (On the other hand, if the attacker can influence both the bounds and the copy length, an overflow may still be possible; in practice, however, the two concerns are often sufficiently separated.) For malloc() in particular, it is enormously beneficial to be able to impose bounds on returned pointers: it becomes impossible for allocator clients to use a pointer from malloc() to access adjacent allocations!
https://github.com/microsoft/snmalloc/blob/main/docs/StrictP...
I wonder to what extent moving bounds checks into hardware provides the potential for efficient memory safety.
According to this FAQ, snmalloc was designed for the Verona language: https://microsoft.github.io/verona/faq.html Unfortunately, I cannot find any significant code samples for Verona on the website or in the GitHub repo. There are a few types defined in a pretty low-level way: https://github.com/microsoft/verona/tree/master/std/builtin
The real question is: how does this deal with freeing allocations from a thread that exited ? The implications of thread lifetime seems to be one of the biggest differences between existing allocators.
Don't all thread implementations leak unfreed memory when a thread exits? I mean, how would the thread know that the memory needs to be freed? It cannot know that the application hasn't ROT13 encoded the pointer, passed it to another thread, and that thread plans to use the memory.
^ actually it's basically implemented. I model-checked it with TLA+ and found a bug that I haven't fixed yet. Next up I'm writing a query engine on it.
There's lots more details about the design in this PDF: https://alex.shamis.au/files/snmalloc-A-Message-Passing-Allo...
I found this design decision rather odd: Allocators may send messages to any other allocator. In a naïve implementation each allocator would keep a queue of batched messages for each other allocator. The number of queues would then either be the dynamically known number of existing threads, or the statically known maximal number of possible threads. The former would require allocation of a dynamically sized structure…
Sounds dumb but actually it's useful sometimes? I dunno, IANA networking person.
A Scheme for Fast Parallel Communication https://ldhulipala.github.io/readings/ValiantPermutationRout...
I'm messing around with implementing a parallel runtime system right now^, and I also had to implement a shared-nothing allocator. I ended up making each thread have a Chase-Lev Deque of 2MB pages. If you want to allocate a page, you do the usual pop-or-try-to-steal thing, and if that doesn't work, THEN you do the mmap to get another 2MB page. I was going to benchmark it and write a post about it, but I never got aro…
I am especially interested in how you share memory between threads in your parallel runtime - what thread safety approach do you use?
I've been thinking about static memory as permanent regions that are permanent fixtures and the program flows through them and there must be backpressure when buffers get full.
I just wrote a nonblocking multithreaded barrier with a lock free algorithm.
The real question is: how does this deal with freeing allocations from a thread that exited ? The implications of thread lifetime seems to be one of the biggest differences between existing allocators.
Don't all thread implementations leak unfreed memory when a thread exits? I mean, how would the thread know that the memory needs to be freed? It cannot know that the application hasn't ROT13 encoded the pointer, passed it to another thread, and that thread plans to use the memory.
I'm a bit slow this morning - I don't understand what this is supposed to mean.
To me, it's like saying "don't all functions leak unfreed memory when a function returns" - it's true, but so what? It's always been true.
> I mean, how would the thread know that the memory needs to be freed? It cannot know that the application hasn't ROT13 encoded the pointer, passed it to another thread, and that thread plans to use the memory.
As I understand it, they are using multiple allocators (maybe 1 allocator per thread?), and they store metadata (such as ownership information of the allocated block) during the allocation.
With 1 allocator per thread, each allocation by an allocator maps to a single thread. When a block is to be freed, the allocator for the thread checks the ownership information, and if it is not the owner of that block, sends a request to the thread that is the owner of that block.
This means that even if the thread allocated a block, and let it get used by multiple other threads, they can all call `free` on that block, and the original thread will simply get all the free requests (I assume it will ignore requests for freeing blocks that are already freed).
It all depends on extra metadata stored during allocation, that describes the ownership information of that block.
(Happy to be corrected about any/all of the above)
The real question is: how does this deal with freeing allocations from a thread that exited ? The implications of thread lifetime seems to be one of the biggest differences between existing allocators.
I assume that they don't release the allocator assigned to a thread when a thread exits, unless that allocator is holding a list of zero allocations.
That sounds like the easiest part of all of this, TBH: A single extra line of code that, after performing an actual deallocation (as opposed to sending a message to perform the deallocation), the allocator checks that it has non-zero allocations, and that the thread still exists, otherwise it deletes itself.