I remember feeling “unsatisfied” when this article first came out: first two examples are rather textbookish (I guess Send doesn’t impress anymore which is a good thing), and the last one beyond impressingly complicated (73 mutexes?) seems to be very niche and already well covered by existing tooling (clang annotations?) and passing lock references as evidence is a common practice.
Does anyone know any examples of what the article talks about where Rust typesystem especially shines?
“Incorrect code shouldn’t compile” is my favorite principle (along with believe that type systems is one of the greatest inventions ever).
Not Rust (though the same techniques would directly map to Rust), but in snmalloc we use C++ types to encode the lifecycle of allocations, with a three-dimensional state space. The wrapper encodes the valid transitions and means that we aren’t just passing void* all over the place.
A memory allocator is a good example of this because it’s doing intrinsically unsafe things. It is providing the abstraction of heap objects that the rest of the system relies on. When a pointer is passed to free, we ingest it as a ‘wild’ pointer: i.e. one that came from outside and may be untrusted. It must then be converted to a tame pointer by calling the platform’s domestication function, which does arbitrary amounts of checking (in addition to checking that its address is the start of an allocation). This set of type transitions also provides hooks in the right places for things like applying CHERI bounds or setting MTE colours.
This is really cool: pointers need to be safer. I wonder: since you have 3 dims don’t you have too many variants? Is it all auto everywhere and dozen of versions of each function or are there only a few combinations used?
snmalloc looks interesting . What’s up with so many allocators coming out of MSFT? Some kind of culture thing? :)
I wonder: since you have 3 dims don’t you have too many variants? Is it all auto everywhere and dozen of versions of each function or are there only a few combinations used?
Most of the dimensions are only 2-3 elements deep, so the total size of the matrix is fairly small and not all variants are used. And most of the transitions are shifting a single dimension, so there’s a simple call to do the right check for shifting in that dimension and return the result.
snmalloc looks interesting . What’s up with so many allocators coming out of MSFT? Some kind of culture thing? :)
We created snmalloc at about the same time as mimalloc, and neither project knew about the other until we had finished. Mimalloc was created because Z3 and Lean did a lot of small allocations and was often bottlenecked on malloc performance. They wanted something that scaled well for lots of small allocations. Snmalloc started as a bet between Matt and Sylvan that you could improve the performance of Pony if you added a lower-level message passing protocol so that memory allocations were returned to the thread that allocated them.
The data structure design for the two ended up looking quite similar (and we each stole good ideas from the other). The main difference is that mimalloc aims to be a good malloc implementation, whereas snmalloc aims to be a set of building blocks for creating different memory allocators. Most of the features of snmalloc are templated and can be pulled in or replaced with alternate implementations easily.
I remember feeling “unsatisfied” when this article first came out: first two examples are rather textbookish (I guess Send doesn’t impress anymore which is a good thing), and the last one beyond impressingly complicated (73 mutexes?) seems to be very niche and already well covered by existing tooling (clang annotations?) and passing lock references as evidence is a common practice.
Does anyone know any examples of what the article talks about where Rust typesystem especially shines?
“Incorrect code shouldn’t compile” is my favorite principle (along with believe that type systems is one of the greatest inventions ever).
Not Rust (though the same techniques would directly map to Rust), but in snmalloc we use C++ types to encode the lifecycle of allocations, with a three-dimensional state space. The wrapper encodes the valid transitions and means that we aren’t just passing
void*all over the place.A memory allocator is a good example of this because it’s doing intrinsically unsafe things. It is providing the abstraction of heap objects that the rest of the system relies on. When a pointer is passed to free, we ingest it as a ‘wild’ pointer: i.e. one that came from outside and may be untrusted. It must then be converted to a tame pointer by calling the platform’s domestication function, which does arbitrary amounts of checking (in addition to checking that its address is the start of an allocation). This set of type transitions also provides hooks in the right places for things like applying CHERI bounds or setting MTE colours.
This is really cool: pointers need to be safer. I wonder: since you have 3 dims don’t you have too many variants? Is it all
autoeverywhere and dozen of versions of each function or are there only a few combinations used?snmalloc looks interesting . What’s up with so many allocators coming out of MSFT? Some kind of culture thing? :)
Most of the dimensions are only 2-3 elements deep, so the total size of the matrix is fairly small and not all variants are used. And most of the transitions are shifting a single dimension, so there’s a simple call to do the right check for shifting in that dimension and return the result.
We created snmalloc at about the same time as mimalloc, and neither project knew about the other until we had finished. Mimalloc was created because Z3 and Lean did a lot of small allocations and was often bottlenecked on malloc performance. They wanted something that scaled well for lots of small allocations. Snmalloc started as a bet between Matt and Sylvan that you could improve the performance of Pony if you added a lower-level message passing protocol so that memory allocations were returned to the thread that allocated them.
The data structure design for the two ended up looking quite similar (and we each stole good ideas from the other). The main difference is that mimalloc aims to be a good malloc implementation, whereas snmalloc aims to be a set of building blocks for creating different memory allocators. Most of the features of snmalloc are templated and can be pulled in or replaced with alternate implementations easily.