4 ms·

Snmalloc: A Message Passing Allocator

92 points by akyuu 3y ago

Snawoot 3y ago
Are there any benchmarks?
- akyuu 3y ago
  https://github.com/microsoft/snmalloc/blob/main/docs/security/README.md https://github.com/microsoft/snmalloc/blob/main/docs/securit...
  - jcrites 3y ago
    While reviewing that doc, I also came across this. Seems very interesting -- I did not know this was possible: > 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/StrictProvenance.md 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.
    - nwf 3y ago
      > I wonder to what extent moving bounds checks into hardware provides the potential for efficient memory safety. It's great! The CHERI team at U. Cambridge has recently released their initial performance characterization of Morello, Arm's experimental ARMv8 w/ CHERI: https://ctsrd-cheri.github.io/morello-early-performance-results/ https://ctsrd-cheri.github.io/morello-early-performance-resu... . The major take-away there is a little buried, but is: > The above 1.8% to 3.0% is our current best estimate of the geometric mean overhead that would be incurred for a future optimized design That seems to be well within people's tolerance for security features, especially as we think having CHERI would also allow us to turn off, and so stop paying for, some existing mitigations. While there's a wealth of stuff to read about CHERI (https://www.cl.cam.ac.uk/research/security/ctsrd/cheri/cheri-publications.html https://www.cl.cam.ac.uk/research/security/ctsrd/cheri/cheri...), if you're new to it and want something more presentation flavored than text, you might enjoy my talk from HOPE 2022: https://www.youtube.com/watch?v=dH7QUdXeVrI https://www.youtube.com/watch?v=dH7QUdXeVrI
alberth 3y ago
I’ve always wondered if DragonflyBSD would uniquely benefit from snmalloc, given that it’s a message-passing based kernel.
ridiculous_fish 3y ago
There's lots more details about the design in this PDF: https://alex.shamis.au/files/snmalloc-A-Message-Passing-Allocator.pdf https://alex.shamis.au/files/snmalloc-A-Message-Passing-Allo...
- Varriount 3y ago
  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 when handling remote deallocation and slow enqueueing, while the latter would lead to significant wasted space and hard-coded limits. Instead, we adapted ideas from radix trees. Allocators keep a fixed 2k size array of buckets of pending messages, where k in our implementation is 6. Batched messages are inserted into the bucket which corresponds to their destination’s address, modulo the number of buckets. Dispatch of messages takes place by sending all the messages from the same bucket to one allocator, which then responds to those messages for which it is the final destination, and forwards the rest, again according to their destination allocator address, but now shifted right by k bits. I would think that the overhead of message passing would mean that minimization of the number of messages sent. I wonder how well this technique scales.
  - jlebar 3y ago
    Reminds me of this network routing technique: Send a packet to a random node, and then have that node forward it to its final destination. Sounds dumb but actually it's useful sometimes? I dunno, IANA networking person. A Scheme for Fast Parallel Communication https://ldhulipala.github.io/readings/ValiantPermutationRouting.pdf https://ldhulipala.github.io/readings/ValiantPermutationRout...
o11c 3y ago
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.
- gavinhoward 3y ago
  I'm not a contributor to snmalloc or affiliated in any way. I'm going to reimplement snmalloc in C for my own code. I'm going to avoid that problem by using structured concurrency. Under my system, threads only get data from threads that are ancestors. (There will be a way of getting data from a non-ancestor, but it will effectively keep the allocating thread alive until the using thread is done.) The reason I'm going to use snmalloc is because of structured concurrency; it's like it was designed for structured concurrency.
  - fanf2 3y ago
    Have you considered using mimalloc? I gather it has a similar design to snmalloc, but mimalloc is written in C.
    - gavinhoward 3y ago
      I did, but I don't want to have a dependency on Microsoft code. Plus, there are some changes I will make to make my snmalloc/mimalloc clone more friendly to structured concurrency. Nothing major, stuff to mostly deal with realloc().
- netcoyote 3y ago
  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.
  - lights0123 3y ago
    The memory could be freed from another thread with a classical allocator—but this one passes it back to the allocating thread, leaving the question what happens to it?
deleted 3y ago
[deleted]
chrisaycock 3y ago
According to this FAQ, snmalloc was designed for the Verona language: https://microsoft.github.io/verona/faq.html 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 https://github.com/microsoft/verona/tree/master/std/builtin
- remram 3y ago
  Wikipedia has a code sample, no idea where it came from.
sakras 3y ago
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 around to it. Glad shared-nothing allocation seems to be a problem worth solving. ^ 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.
- samsquire 3y ago
  This is very interesting! 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.
  - sakras 3y ago
    My threads generally don’t share memory inside the runtime. The only time they touch each others’ stuff is when they perform work stealing or memory stealing, and that’s all provided by the CL-Deque
- yvdriess 3y ago
  FYI Cray developed an interesting allocator for scaling to a massive amount of threads https://dl.acm.org/doi/10.1145/1122971.1122999 https://dl.acm.org/doi/10.1145/1122971.1122999
- menaerus 3y ago
  If you're backing up your memory through pages stored in N work-stealing queues (chase-lev deque in this case), doesn't that contradict the shared-nothing architecture? When queue is empty, I understand your allocator will try to steal a page from another queue before it asks an OS for a new 2MB page - and that essentially means synchronization and thus sharing. Also, I think this approach is going to result with bad memory locality since your data will now be spread all over the place, e.g. different queues.

92 points by akyuu 3y ago

Snawoot 3y ago

Are there any benchmarks?

akyuu 3y ago
https://github.com/microsoft/snmalloc/blob/main/docs/security/README.md https://github.com/microsoft/snmalloc/blob/main/docs/securit...
- jcrites 3y ago
  While reviewing that doc, I also came across this. Seems very interesting -- I did not know this was possible: > 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/StrictProvenance.md 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.
  - nwf 3y ago
    > I wonder to what extent moving bounds checks into hardware provides the potential for efficient memory safety. It's great! The CHERI team at U. Cambridge has recently released their initial performance characterization of Morello, Arm's experimental ARMv8 w/ CHERI: https://ctsrd-cheri.github.io/morello-early-performance-results/ https://ctsrd-cheri.github.io/morello-early-performance-resu... . The major take-away there is a little buried, but is: > The above 1.8% to 3.0% is our current best estimate of the geometric mean overhead that would be incurred for a future optimized design That seems to be well within people's tolerance for security features, especially as we think having CHERI would also allow us to turn off, and so stop paying for, some existing mitigations. While there's a wealth of stuff to read about CHERI (https://www.cl.cam.ac.uk/research/security/ctsrd/cheri/cheri-publications.html https://www.cl.cam.ac.uk/research/security/ctsrd/cheri/cheri...), if you're new to it and want something more presentation flavored than text, you might enjoy my talk from HOPE 2022: https://www.youtube.com/watch?v=dH7QUdXeVrI https://www.youtube.com/watch?v=dH7QUdXeVrI

alberth 3y ago

I’ve always wondered if DragonflyBSD would uniquely benefit from snmalloc, given that it’s a message-passing based kernel.

ridiculous_fish 3y ago

There's lots more details about the design in this PDF: https://alex.shamis.au/files/snmalloc-A-Message-Passing-Allocator.pdf https://alex.shamis.au/files/snmalloc-A-Message-Passing-Allo...

Varriount 3y ago
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 when handling remote deallocation and slow enqueueing, while the latter would lead to significant wasted space and hard-coded limits. Instead, we adapted ideas from radix trees. Allocators keep a fixed 2k size array of buckets of pending messages, where k in our implementation is 6. Batched messages are inserted into the bucket which corresponds to their destination’s address, modulo the number of buckets. Dispatch of messages takes place by sending all the messages from the same bucket to one allocator, which then responds to those messages for which it is the final destination, and forwards the rest, again according to their destination allocator address, but now shifted right by k bits. I would think that the overhead of message passing would mean that minimization of the number of messages sent. I wonder how well this technique scales.
- jlebar 3y ago
  Reminds me of this network routing technique: Send a packet to a random node, and then have that node forward it to its final destination. Sounds dumb but actually it's useful sometimes? I dunno, IANA networking person. A Scheme for Fast Parallel Communication https://ldhulipala.github.io/readings/ValiantPermutationRouting.pdf https://ldhulipala.github.io/readings/ValiantPermutationRout...

o11c 3y ago

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.

gavinhoward 3y ago
I'm not a contributor to snmalloc or affiliated in any way. I'm going to reimplement snmalloc in C for my own code. I'm going to avoid that problem by using structured concurrency. Under my system, threads only get data from threads that are ancestors. (There will be a way of getting data from a non-ancestor, but it will effectively keep the allocating thread alive until the using thread is done.) The reason I'm going to use snmalloc is because of structured concurrency; it's like it was designed for structured concurrency.
- fanf2 3y ago
  Have you considered using mimalloc? I gather it has a similar design to snmalloc, but mimalloc is written in C.
  - gavinhoward 3y ago
    I did, but I don't want to have a dependency on Microsoft code. Plus, there are some changes I will make to make my snmalloc/mimalloc clone more friendly to structured concurrency. Nothing major, stuff to mostly deal with realloc().
netcoyote 3y ago
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.
- lights0123 3y ago
  The memory could be freed from another thread with a classical allocator—but this one passes it back to the allocating thread, leaving the question what happens to it?

deleted 3y ago

[deleted]

chrisaycock 3y ago

According to this FAQ, snmalloc was designed for the Verona language: https://microsoft.github.io/verona/faq.html 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 https://github.com/microsoft/verona/tree/master/std/builtin

remram 3y ago
Wikipedia has a code sample, no idea where it came from.

sakras 3y ago

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 around to it. Glad shared-nothing allocation seems to be a problem worth solving. ^ 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.

samsquire 3y ago
This is very interesting! 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.
- sakras 3y ago
  My threads generally don’t share memory inside the runtime. The only time they touch each others’ stuff is when they perform work stealing or memory stealing, and that’s all provided by the CL-Deque
yvdriess 3y ago
FYI Cray developed an interesting allocator for scaling to a massive amount of threads https://dl.acm.org/doi/10.1145/1122971.1122999 https://dl.acm.org/doi/10.1145/1122971.1122999
menaerus 3y ago
If you're backing up your memory through pages stored in N work-stealing queues (chase-lev deque in this case), doesn't that contradict the shared-nothing architecture? When queue is empty, I understand your allocator will try to steal a page from another queue before it asks an OS for a new 2MB page - and that essentially means synchronization and thus sharing. Also, I think this approach is going to result with bad memory locality since your data will now be spread all over the place, e.g. different queues.