Whenever you explicitly declare a lock ordering "B must be locked after A", it creates an (explicit) trait implementation "impl LockAfter<A> for B". It also creates a blanket (generic) trait implementation "impl LockAfter<X> for B" for any X where A implements LockAfter<X>; this basically fills in all the transitive edges of the graph.
Rust prohibits multiple implementations for the same trait and type. If there's a cycle in this graph involving A, then eventually the transitive walk will generate an "impl LockAfter<A> for A", after which it will generate a blanket "impl LockAfter<A> for B" which conflicts with the explicit impl and thus results in a compiler error.
Nice article. Any project rewritten from scratch (version 3 here) by the same experienced engineers will inevitably be better/more robust/more performant than the previous versions. During our career growth as craftsmen, we build using tools we understand, and get a certain output. As we learn more about various other tools (techniques), we have a wider understanding and will make it better again.
Having read about their journey, I can see they use 77 mutexes and a hierarchy chart for locking to prevent deadlocks. How quaint. I keep on harping about the Actor programming model to deaf ears, but I guess the apprentices need more stumbling around before achieving true enlightenment.
Version #4, perhaps?
Any guru want to share what path to take after Actors? I’m ready…
The problem with actor in rust is two fold and would prevent their use in this context I think:
- They need async. Otherwise you need to implement yielding in house, have one actor per thread, etc. OS code is usually sync / callback based.
- They need owned and usually send for all input. Since you have to send input / messages over a channel it makes it a requirement to have owned values and send if crossing thread boundaries. Very annoying requirement in rust.
Not a guru, but my take is that the actor model is one method of architecting a system to separate synchronization from other concerns. There are other ways to do that, often specific to a particular problem and with more or less separation. As always, there are many tradeoffs involved.
Effect systems are great for concurrent programming and easier to reason about than actors. They aren’t available in all programming languages however.
What is described there, seems basic encapsulation to me. We do this too in C with structure types and API around it that enforces the invariants. So C is a X-safe language too? Or what am I missing?
C is not X-safe because you can’t declare conformity in the type system.
In Rust, if I understand the article, you can create a “trait” that marks a type as conforming to an invariant, so in the article they marked thread-safe structures as Send and the thread functions as requiring types that implement Send.
Send isn’t an API to implement or type definition, it’s a sentinel saying “I declare that this type conforms to the documented expectations” even though the expectations can’t be checked by a compiler.
More generally, with C you can't restrict what can (accidentally or not) interact with the internal unsafe bits (without the cost of forcing the data to always live in the heap at least; or perhaps annoying field names that are automatically searched-for by your build system, though then you're essentially making a DSL), or even force using the "safe" parts properly (not enforced at compile-time, at least) outside of, again, a rather limited subset of cases.
As a very general example, you can repeat basically any statement in C twice and it'll still compile. If you get lucky, the compiler might tell you you've ended up with a double-free or something, but that's a very limited set of cases, and won't help if the second copy is invoked down a couple function calls.
There may be some ways to still get additional true guarantees in C, but they'll be rather more restrictive than ones you can write in Rust, and you'll likely end up with overhead, which tempts skimping out on doing things properly in the name of performance.
>it’s a sentinel saying “I declare that this type conforms to the documented expectations” even though the expectations can’t be checked by a compiler.
Interesting. So perhaps the next step is to sprinkle asserts in randomly at runtime to help with catching bugs.
Yea, it’s just encapsulation. Rust gives you some additional tools for achieving it though. Enums are very useful for this, as are the rules for handling shared and mutable references.
For some examples, imagine an HTTP server that answers requests from clients. You might imagine having a Response object that lets you set headers and the body, with a send method that sends the response back to the client that made the request. It would be an obvious sort of error to send the thing twice, so in C you would assert that send was only called once. In Rust, on the other hand, the send method can _consume_ the Response object. This takes it away from the caller, so the compiler will ensure that they can’t even write code with two calls to the send method. You can’t enforce this at compile time in C because in C all methods take a simple pointer to the object to act on.
Another invariant that you might want to enforce is that only one body gets attached to the Response, that the body is attached before the Response is sent, and that the user cannot forget to attach a body. You would start with a Response object that has methods for adding headers. It would also have a method that attaches a body. This body method would _consume_ the Response and return a ResponseWithBody object. The ResponseWithBody object doesn’t have any methods for adding headers, or for adding a body, so several of our requirements are now checked by the compiler. It does have the method for sending the response though, and the Response object does not. This satisfies the rest of the requirements. If you try to send a Response, it’ll fail to compile. If you try to add headers after the body, it’ll fail to compile. You literally just make a state machine out of types, with methods that consume one type and return another, and the compiler enforces that only valid state transitions are possible. This is usually called “typestate programming” if you want to search for more examples.
I think an object ownership system is something we should have in C. Otherwise, i am relatively unimpressed TBH. And readability of this is questionable:
I think the main thing is that it is all done in the type system at compile-time. This is the kind of thing C++ is good at but I’m not sure that C can do it with the same guarantees.
Java GC, Rust borrow checker, OCaml modules, linters, Valgrind...we more or less know the values that well-written code possesses, but we have yet to figure out how to make well-written code easy to write. Especially at the C or Rust "bare metal" level, it's not about whether a desirable programming practice is possible but whether programmers can reasonably be expected to pull it off.
Finding all possible data races in arbitrarily large and complex programs (even across 3rd party dependencies and dynamic callbacks) seems like a challenging task requiring specialized static and dynamic analyzers. But it turns out it can be reduced to automatically marking structs as safe to move to a thread, and type annotations on mutexes and thread-spawning functions.
It's an example of richer, expressive interfaces that allocate responsibility for who ensures what behavior properly for the problem. Send and Sync don't fundamentally make thread safety easier. What they do is that library authors can provide abstractions to users and each side has a clear scope of diligence. Rust's realization through Send/Sync is more complicated in practice, demonstrated by that one bug for Mutex(Guard?) in the standard library, but pulls its weight well.
You can't seriously be suggesting that Google use an extremely niche "pre-1.0" language for a production system intended to be used by hundreds of millions of people?
Readit News
Whenever you explicitly declare a lock ordering "B must be locked after A", it creates an (explicit) trait implementation "impl LockAfter<A> for B". It also creates a blanket (generic) trait implementation "impl LockAfter<X> for B" for any X where A implements LockAfter<X>; this basically fills in all the transitive edges of the graph.
Rust prohibits multiple implementations for the same trait and type. If there's a cycle in this graph involving A, then eventually the transitive walk will generate an "impl LockAfter<A> for A", after which it will generate a blanket "impl LockAfter<A> for B" which conflicts with the explicit impl and thus results in a compiler error.
Having read about their journey, I can see they use 77 mutexes and a hierarchy chart for locking to prevent deadlocks. How quaint. I keep on harping about the Actor programming model to deaf ears, but I guess the apprentices need more stumbling around before achieving true enlightenment.
Version #4, perhaps?
Any guru want to share what path to take after Actors? I’m ready…
- They need async. Otherwise you need to implement yielding in house, have one actor per thread, etc. OS code is usually sync / callback based.
- They need owned and usually send for all input. Since you have to send input / messages over a channel it makes it a requirement to have owned values and send if crossing thread boundaries. Very annoying requirement in rust.
In Rust, if I understand the article, you can create a “trait” that marks a type as conforming to an invariant, so in the article they marked thread-safe structures as Send and the thread functions as requiring types that implement Send.
Send isn’t an API to implement or type definition, it’s a sentinel saying “I declare that this type conforms to the documented expectations” even though the expectations can’t be checked by a compiler.
As a very general example, you can repeat basically any statement in C twice and it'll still compile. If you get lucky, the compiler might tell you you've ended up with a double-free or something, but that's a very limited set of cases, and won't help if the second copy is invoked down a couple function calls.
There may be some ways to still get additional true guarantees in C, but they'll be rather more restrictive than ones you can write in Rust, and you'll likely end up with overhead, which tempts skimping out on doing things properly in the name of performance.
Interesting. So perhaps the next step is to sprinkle asserts in randomly at runtime to help with catching bugs.
For some examples, imagine an HTTP server that answers requests from clients. You might imagine having a Response object that lets you set headers and the body, with a send method that sends the response back to the client that made the request. It would be an obvious sort of error to send the thing twice, so in C you would assert that send was only called once. In Rust, on the other hand, the send method can _consume_ the Response object. This takes it away from the caller, so the compiler will ensure that they can’t even write code with two calls to the send method. You can’t enforce this at compile time in C because in C all methods take a simple pointer to the object to act on.
Another invariant that you might want to enforce is that only one body gets attached to the Response, that the body is attached before the Response is sent, and that the user cannot forget to attach a body. You would start with a Response object that has methods for adding headers. It would also have a method that attaches a body. This body method would _consume_ the Response and return a ResponseWithBody object. The ResponseWithBody object doesn’t have any methods for adding headers, or for adding a body, so several of our requirements are now checked by the compiler. It does have the method for sending the response though, and the Response object does not. This satisfies the rest of the requirements. If you try to send a Response, it’ll fail to compile. If you try to add headers after the body, it’ll fail to compile. You literally just make a state machine out of types, with methods that consume one type and return another, and the compiler enforces that only valid state transitions are possible. This is usually called “typestate programming” if you want to search for more examples.
https://cs.opensource.google/fuchsia/fuchsia/+/main:src/conn...
Finding all possible data races in arbitrarily large and complex programs (even across 3rd party dependencies and dynamic callbacks) seems like a challenging task requiring specialized static and dynamic analyzers. But it turns out it can be reduced to automatically marking structs as safe to move to a thread, and type annotations on mutexes and thread-spawning functions.
Neither the language maintainers nor architects
Messages are guaranteed to be processed ordered sequentially.
https://tutorial.ponylang.io/index.html#whats-pony-anyway