{"id":4958,"date":"2022-10-03T15:11:34","date_gmt":"2022-10-03T20:11:34","guid":{"rendered":"https:\/\/neosmart.net\/blog\/?p=4958"},"modified":"2022-10-08T19:59:55","modified_gmt":"2022-10-09T00:59:55","slug":"implementing-truly-safe-semaphores-in-rust","status":"publish","type":"post","link":"https:\/\/neosmart.net\/blog\/implementing-truly-safe-semaphores-in-rust\/","title":{"rendered":"Implementing truly safe semaphores in rust"},"content":{"rendered":"

Discuss this article on r\/rust<\/a> or on Hacker News<\/a>.<\/em><\/p>\n

Low-level or systems programming languages generally strive to provide libraries and interfaces that enable developers, boost productivity, enhance safety, provide resistance to misuse, and more — all while trying to reduce the runtime cost of such initiatives. Strong type systems turn runtime safety\/sanity checks into compile-time errors, optimizing compilers try to reduce an enforced sequence of api calls into a single instruction, and library developers think up of clever hacks to even completely erase any trace of an abstraction from the resulting binaries. And as anyone that’s familiar with them can tell you, the rust programming language and its developers\/community have truly embraced this ethos of zero-cost abstractions, perhaps more so than any others.<\/p>\n

I’m not going to go into detail about what the rust language and standard library do to enable zero-cost abstractions or spend a lot of time going over some of the many examples of zero-cost interfaces available to rust programmers, though I’ll just quickly mention a few of my favorites: iterators and all the methods the Iterator<\/code> trait exposes<\/a> have to be at the top of every list given the amount of black magic voodoo the compiler has to do to turn these into their loop-based equivalents, zero-sized types make developing embedded firmware in rust a dream and it’s really crazy to see how all the various peripheral abstractions<\/a> can be completely erased giving you small firmware blobs despite all the safety abstractions, and no list is complete the newest member of the team, async<\/code>\/await<\/code> and how rust manages to turn an entire web server api into a single state machine and event loop. (And to think this can be used even on embedded without a relatively heavy async framework like tokio and with even zero allocations to boot!)<\/p>\n

<\/p>\n

But the tricky thing with abstractions is that the relative<\/em> price you pay scales rather unfairly with the size of the interface you are abstracting over. While a byte here and a byte there may mean nothing when we’re talking framework-scale interfaces, when you are modeling smaller and finer-grained abstractions, every byte and every instruction begin to count.<\/p>\n

A couple of weeks ago, we released an update to rsevents<\/code><\/a>, our crate that contains a rusty cross-platform equivalent to WIN32 events for signaling between threads and writing your own synchronization primitives, and rsevents-extra<\/code><\/a> a companion crate that provides a few handy synchronization types built on top of the manual- and auto-reset events from the rsevents<\/code> crate. Aside from the usual awesome helpings of performance improvements, ergonomics enhancements, and more, this latest version of rsevents-extra<\/code> includes a Semaphore<\/code> synchronization primitive<\/a><\/strong> – something that the rust standard library surprisingly lacks… but not without good reason.<\/p>\n

What makes a semaphore a semaphore?<\/h2>\n

Semaphores are well-documented and fairly well-understood underpinnings of any concurrency library or framework and essential Computer Science knowledge. So why doesn’t the rust standard library have a semaphore type?<\/p>\n

Unlike the synchronization types that the rust standard library currently provides (such as Mutex<T><\/a><\/code> and RwLock<T><\/code><\/a>, a semaphore is somewhat harder to model as it doesn’t so much restrict concurrent access to a single object or variable so much as it does limit concurrency within a region<\/em> of code.<\/p>\n

Of course it can be argued that in traditional programming a semaphore is just a more general case of a mutex, and just like mutexes traditionally protected a region of code from concurrent access1<\/a><\/sup> but were converted into synchronization primitives owning<\/em> the data they protect and marshalling access to it, there’s no reason a rust semaphore couldn’t do the same. But therein lies the problem: a mutex and a read-write lock can both be understood in terms of readers<\/em> and\u00a0writers<\/em>,2<\/a><\/sup> a semaphore makes no such guarantees. And rust is quite fundamentally built on the concept of read ^ write: it\u00a0needs<\/em> to know if a thread\/scope is reading or writing from a variable or memory location in order to uphold its most basic memory safety guarantee: there can either be multiple “live” read-only references to an object or a single write-enabled (&mut<\/code>) reference to the same — but a semaphore doesn’t make that distinction<\/strong>!<\/p>\n

While a strictly binary semaphore (max concurrency == 1) can guarantee that there will never be multiple writers accessing a memory region, there’s not much theoretical benefit to such a binary semaphore over a mutex – in fact, they’re interchangeable. What makes a semaphore truly special is that it can be created (or even dynamically modified) with a concurrency limit n<\/em> and then uphold its core precondition, guaranteeing that at any given time there will never be more than n<\/em> threads\/stacks3<\/a><\/sup> accessing a semaphore-protected region at any given time.<\/p>\n

The problem is that with n<\/em> > 1, there’s no concept of a “privileged” owning thread and all threads that have “obtained” the semaphore do so equally. Therefore, a rust<\/em> semaphore can only ever provide read-only (&T<\/code>) access to an underlying resource, limiting the usefulness of such a semaphore almost to the point of having no utility. As such, the only safe “owning” semaphore with read-write access that can exist in the rust world would be \u00a0Semaphore<()><\/code>,4<\/a><\/sup> or one that actually owns no\u00a0<\/em>data and can only be used for its side effect of limiting concurrency while the semaphore is “owned,” so to speak.5<\/a><\/sup> (Actual mutation of accessed resources within the concurrency-limited region, if needed, would continue to be marshalled via Mutex<T><\/code> or RwLock<T><\/code> on a fine-grained level.)<\/p>\n

Ok, so this explains why the rust standard library doesn’t contain a Semaphore<T><\/code> type to mirror Mutex<T><\/code> and its friends, but then what’s so hard about shipping a non-owning std::sync::Semaphore<\/code> instead?<\/p>\n

Designing a safe Semaphore<\/code> for rust<\/h2>\n

To answer this, we need to look at what a semaphore API generally looks like in other languages. While the names and calling semantics differ, a semaphore is generally found as a type that provides the following, starting with the most fundamental to\u00a0de facto<\/em> properties:<\/p>\n