12 ms·
Ownership is Theft: Experiences Building an Embedded OS in Rust (2015) [pdf]
- jononor 10y agoFrom the abstract: "...embedded platforms are highly event-based, and Rust’s memory safety mechanisms largely presume threads. In our experience developing an operating system for embedded systems in Rust, we have found that Rust’s ownership model prevents otherwise safe resource sharing common in the embedded domain, conflicts with the reality of hardware resources, and hinders using closures for programming asynchronously..."
- alanning 10y ago"... In addition, we draw from our experience to propose a new language extension to Rust that would enable it to provide better memory safety tools for event-driven platforms." I believe this part also warrants mention. Not only did they share their findings as experts in the field, they also did the extra work of detailing improvements. My take away is that its painful to make embedded systems in Rust now but its promising enough to make it worth the effort for the embedded community to help guide Rust's development.
- BaronSamedi 10y agoNot my field but I don't understand the rationale behind choosing Rust. Given the performance and security concerns wouldn't Ada be the natural choice here? It may not be the most fashionable language but it seems I read about security problems with embedded and IoT devices on a daily basis. Why not choose a language designed for this problem?
- vertex-four 10y agoAda isn't actually particularly safe in any reasonable sense - or rather, it provides enough escape hatches with little obvious marking that it's costly (in terms of time spent in code review) to ensure safety. Safety of existing Ada programs is primarily a result of the engineering practices that went into them, more than the language itself.
- nickpsecurity 10y agoNonsense. The designer looked at almost every spot where coding mistakes were leading to crashes or corruption. Then, made those safe-by-default wherever possible. They're described in modern form in the book below by Barnes. The effect was confirmed when defects dropped to around half what Mitre et al had been observing on C projects. There was only one case study I saw where Ada made no difference whose control group was C++. An anomaly that might have been same system reimplemented by same people, easily-correct system, or just both super-talented. So, it is a safe language with only exception being temporal safety w/out a GC. Rust delivers on that. http://www.adacore.com/uploads_gems/Ada_Safe_and_Secure_Booklet.pdf http://www.adacore.com/uploads_gems/Ada_Safe_and_Secure_Book... Also, SPARK Ada can straight-up prove common errors don't exist in that code with an automated prover. Most engineers would spend quite a bit of time doing that with pencil-and-paper examination or human-driven provers: https://en.wikipedia.org/wiki/SPARK_(programming_language) https://en.wikipedia.org/wiki/SPARK_(programming_language)
- nickpsecurity 10y agoIt would be. Especially with mature tooling available from AdaCore. Seem my reply to vertex-four for links containing proof. Here's some examples in industry & CompSci just for kicks: http://www.adacore.com/customers http://www.adacore.com/customers Note that the authors are just doing research on seeing how well Rust handles the problem domain. There's nothing wrong with them avoiding Ada to explore another tool or problem area. They should consider each carefully if they were trying to pick best tool for real work.
- naasking 10y ago> Given the performance and security concerns wouldn't Ada be the natural choice here? Ada would be a good choice, but it's way more awkward to program in. It definitely has some nice features of its own that Rust should steal asap though.
- steveklabnik 10y ago> My take away is that its painful to make embedded systems in Rust now Please note that this paper is old and some of it is due to the author's lack of experience with Rust at the time. It has gotten way way easier since then. Fun story: Niko, a Rust core team member, was keynoting the conference where this paper was presented, and ended up sitting down with the authors and working out some stuff. So their hard work was upstreamed even faster than usual! (It ended up being more of a redesign than a language extension, though.) > the embedded commmunity to help guide Rust's development. Yes please!
- alanning 10y agoWow, I totally missed that it was from 2015. Thank you for the update and for your work! I find stories like how Niko met the authors fascinating, so thank you for that as well.
- deleted 10y ago[deleted]
- steveklabnik 10y ago:D Amit, one of the authors, has left a comment on Reddit with some more context about how these problems were solved: https://www.reddit.com/r/rust/comments/655816/ownership_is_theft_experiences_building_an/dg7p2uf/ https://www.reddit.com/r/rust/comments/655816/ownership_is_t...
- ue_ 10y agoIs the title an allusion to Proudhon's succinct quote: "Property is theft!"?
- steveklabnik 10y agoI can assure you it is.
- geofft 10y agoProudhon's quote? It's everyone's quote!
- gmfawcett 10y agoWell played. :)
- shepmaster 10y agoI've been curious to see how something like tokio[1] and futures[2] would work on a microcontroller. These both seem like good fits for event-based work. [1]: https://tokio.rs/ https://tokio.rs/ [2]: https://github.com/alexcrichton/futures-rs https://github.com/alexcrichton/futures-rs
- awelkie 10y agoThere is some discussion on that here: https://github.com/rust-embedded/rfcs/issues/23 https://github.com/rust-embedded/rfcs/issues/23
- rwmj 10y ago"Garbage collection, for example, introduces nondeterministic delays. Automatic memory allocators complicate common kernel optimizations such as slab allocation" No no no. Badly designed GC, for sure. But for any modern, thought-through GC this is not true. And in any case, the Linux kernel uses ref-counting all over the place, which is the worst form of GC - slow, hard to debug, full of potential places to trip you up and cause a leak or a security bug, ...
- striking 10y agoFor reference, some previous discussion on GC here on HN: https://news.ycombinator.com/item?id=12821586 https://news.ycombinator.com/item?id=12821586
- Kenji 10y agoNo no no. Garbage collection has some mandatory overhead. Sure you can do an amortised analysis. Just like pushing into the back of a C++ vector is O(1) amortised... except that every once in a while, the entire vector has to be copied over into a larger block of memory, costing O(n) for that particular operation. You can mislead people, but you cannot trick the computer and hard realtime constraints.
- rwmj 10y agoDo you think your malloc/free (or kmalloc) implementation has no non-deterministic delays? I hate to break it to you, but malloc/free is not magical and O(1). It's complex, even reaching into the cache and operating system, and non-deterministic.
- monocasa 10y agoYep, hard real time code tends not to malloc and free for that reason. Most hard real time systems only allow dynamic memory management at system initialization, not at normal runtime.
- Kenji 10y ago>I hate to break it to you, but malloc/free is not magical and O(1). Trust me, I know more about it than I'd like to. I work on embedded software with hard realtime constraints and we had to remove all malloc/free calls from the critical paths. What I don't like is people claiming garbage collection is free. It annoys me to no end. Garbage collection comes at a clear cost and you need to make a cost/benefit analysis. For your average chat application, this is okay. For video games, it might be, but it's probably already noticeable. For anything remotely realtime, forget garbage collection.
- Manishearth 10y agoThe whole execution contexts thing is sort of based off an assumption that the unique-&mut stuff has to do with thread safety. It doesn't. In fact, it had no bearing on thread safety in Rust for the many years before scoped threads were made possible by removing the 'static bound on Send. http://manishearth.github.io/blog/2015/05/17/the-problem-with-shared-mutability/ http://manishearth.github.io/blog/2015/05/17/the-problem-wit... details why it's necessary. The article does sort of mention this (and I have talked with the authors about this before) but IMO it underrepresents the importance of it. One thing I did discuss with one of the authors at one point was swapping around the guarantees a bit -- allowing multiple &mut for cases not involving any form of runtime typing (enums and vectors are both cases of runtime typing -- in a vector the number of elements is runtime dependent). This would create a significantly different language and be incompatible with the vast majority of the ecosystem; however, it would still be safe, and has the potential to be useful. I even started hacking on a fork of the compiler that does this, but never got the chance to finish it. The idea in essence is not too hard to implement.
- mathw 10y agoI get a 404 on that link.
- deleted 10y ago[deleted]
- deleted 10y ago[deleted]
- Manishearth 10y agoTry now. Octopress does this stupid thing where it generates post URIs based on the local timezone, and I published my last post whilst in Taipei so all the URLs broke. I need to figure out how to patch the code to fix this :|
- deleted 10y ago[deleted]
- jononor 10y agoI feel that some of these issues occur due to an over-reliance on object-oriented practices, in particular 'encapsulation' of state into objects and triggering side-effects in callbacks. The usage of Rust brings painpoints to the fore, but I'll argue that the code is better done otherwise, independently of borrow checker. For instance in the 'Callback through closures' example, there is code like: setTimeout(|| { activityLed.toggle(); }, 2000); First, in an embedded system, you cannot have multiple sources of truth. So its not just because of Rust ownership reasoning that `activityLed` cannot be shared between callbacks - if multiple events is to be considered for a given output they should be syncronized explicitly. Instead I think the code should be more like the following, which models calculation of new state as a pure function. Side-effects are separated out by storing the desired effect as data, dedicated function for realizing. Time is just data, time-based logic without depending on hidden state. This increases testability significantly. And it can be fully reasoned about by Rust, no conflicts with the borrow checker. # for each tick # calculate new state if (now >= state.toggleLedTime) { state.activityLed = !state.activityLed; state.toggleLedTime = now + 2000; } # and realize it updatePin(config.ledPin, state.activityLed);
- hexmiles 10y agothe updatePin call, shouldn't be inside the if body?, or i'm missing something?
- deleted 10y ago[deleted]
- jononor 10y agoBecause it sets what is stored in `state` it does not have to be. It could be inside the if, but there two major reasons why it should not: 1) Testability. With it separated, we can write automated tests for our state calculation logic that are hardware independent, like 'normal' code. We just need to create `currentState` data, pass it into our `calculate()` function, and verify the new `state` returned. This can run both on our host-system, and on-target. We can even build simulations if we want, http://www.jonnor.com/2017/03/host-based-simulation-for-embedded-systems/ http://www.jonnor.com/2017/03/host-based-simulation-for-embe... (shameless plug). 2) Deterministic execution time. Many embedded systems have soft or hard real-time constraints, action must always be performed within X microseconds. The more branches we have the harder it is to reason about whether we can keep this guarantee. By eliminating branches we are executing our 'worst case' always, giving it much more testing.
- openasocket 10y agoThis is a really good article, and I admire the authors for the work they put in. But I can't shake the feeling that what they want to accomplish could be done with a library rather than a language extension. Can anyone explain why their issues couldn't be resolved with a particularly clever mix of traits and macros?
- steveklabnik 10y agoIt can, and it was. See my other comments in this thread.
- steveklabnik 10y agoThis paper is pretty old at this point; today the project has evolved into https://www.tockos.org/ https://www.tockos.org/ The authors have been meaning to write a follow-up paper describing how they overcame the problems here, but haven't just quite yet. That slightly different design is what became Tock.
- dom96 10y agoWas the "Execution contexts" feature outlined in the paper implemented?
- steveklabnik 10y agoThe language was not changed; there were some misunderstandings about the finer points involved here, and their design was changed instead. So overall the idea was implemented, but in already-existing Rust rather than changing the language.
- IshKebab 10y agoHmm the callback issue is exactly what I have run into while trying to wrap libsoundio. The user has to provide a read or write callback, but there's just no ergonomic way to actually do that nicely. At least I can't think of one. Maybe I just don't know the right combination of Arc, RefCell, etc.
- Dowwie 10y ago"Our proposal for execution contexts in Rust is similar but considers execution threads, instead of object graphs, as the unit of isolation. Rust’s low-level interface, safe memory management, and large community make it a particularly good fit for operating system development. If future language development can address the challenges we have demonstrated, Rust should be well positioned to support the next generation of correct embedded operating systems."
- bascule 10y agoI'm an embedded Rust developer, and was a little confused by this paper until I noticed it was written in 2015. There are now solutions to a number of the problems they pose both at the language level and the library level: Here's one in particular: In principal, this would allow us to statically allocate a buffer sized for each particular closure. Unfortunately, there is no size_of keyword in Rust, and static initialization cannot invoke functions— in this case the function size_of<T>() -> usize provided by the Rust core library. This can be solved by using the lazy_static crate: https://github.com/rust-lang-nursery/lazy-static.rs https://github.com/rust-lang-nursery/lazy-static.rs From the description in the README: Using this macro, it is possible to have statics that require code to be executed at runtime in order to be initialized. Hey look, it's exactly what they need! It's also "no_std" compatible and can work just fine in a kernel-like context. Take this paper with a grain of salt: it's a bit dated at this point, and there are solutions for a number of the problems posed.
- codys 10y agoNote that lazy-static does not "statically allocate a buffer" for all definitions of "statically allocate": lazy-static computes it's value on first use, and must use dynamic alloc space (ie: malloc/box) Also, lazy-static has been around for a long time. Releases first occurred in 2014! I'd be surprised if it had not been considered.
- bascule 10y agoWell, their original stated problem was just invoking size_of() at runtime, which lazy-static solves. That said, Rust supports custom allocators now: https://doc.rust-lang.org/book/custom-allocators.html https://doc.rust-lang.org/book/custom-allocators.html Write your own allocator and use Box.
- rkangel 10y agoI think you misunderstand what 'statically allocate' means. That means a size known at compile time, so that the space for that variable can be assigned in the memory map of the executable. Anything involving a 'custom allocator' is doing runtime memory allocation.
- bascule 10y agoI'm an embedded Rust developer, and was a little confused by this paper until I noticed it was 2015. There are now solutions to a number of the problems they pose both at the language level and the library level: Here's one in particular: In principal, this would allow us to statically allocate a buffer sized for each particular closure. Unfortunately, there is no size_of keyword in Rust, and static initialization cannot invoke functions— in this case the function size_of<T>() -> usize provided by the Rust core library. This can be solved by using the lazy_static crate: https://github.com/rust-lang-nursery/lazy-static.rs https://github.com/rust-lang-nursery/lazy-static.rs It's "no_std" compatible and can work just fine in a kernel-like context. Take this paper with a grain of salt: it's a bit dated at this point, and there are solutions for a number of the problems posed.
- kibwen 10y agoMods, can we get a [2015] in the title? Both the OS described within and Rust itself have progressed significantly since this paper's original release. :) EDIT: In particular: the people behind this recently began offering an IoT development board, "Hail", that runs Tock (the OS from the OP): https://www.tockos.org/blog/2017/introducing-hail/ https://www.tockos.org/blog/2017/introducing-hail/ (discussion on /r/rust, with authors present: https://www.reddit.com/r/rust/comments/61257c/introducing_hail_an_iot_development_board_that/ https://www.reddit.com/r/rust/comments/61257c/introducing_ha... ) EDIT 2: I see that the title has been updated, thanks. :)
- EGreg 10y agoProperty is theft!
- patrickg_zill 10y agoActually it is quite disappointing to read this paper. The problems they mention and run into, have already been examined and dealt with in embedded Schemes, such as BIT, PICBIT and PICOBIT. PICBIT http://www.iro.umontreal.ca/~feeley/papers/FeeleyDubeSW03.pdf http://www.iro.umontreal.ca/~feeley/papers/FeeleyDubeSW03.pd... (see the GC section) PICOBIT http://users.eecs.northwestern.edu/~stamourv/papers/picobit.pdf http://users.eecs.northwestern.edu/~stamourv/papers/picobit.... (not as relevant in that hard decisions/tradeoffs examined in predecessor PICBIT) BIT (1995) https://github.com/melvinzhang/bit-scheme https://github.com/melvinzhang/bit-scheme
- nickpsecurity 10y agoI'm upvoting it only because the links might interest embedded developers. You're comment might be missing the point, though, where they're leveraging Rust for it's safety that requires no GC with its CPU or memory overhead. Non-determinism, too, unless using a real-time GC.
- Animats 10y agoIt seems that, for this very tiny OS, they're trying to do real work in interrupts. Most OSs do that, including UNIX/Linux. This has the problem that you can't block the interrupt while waiting for some thread to clear a lock. QNX, though usually sends a message to a thread in a process when an interrupt comes in. The interrupt is processed slightly later. QNX has no interrupt lockouts longer than a few microseconds, because it's not doing much from interrupt code except sending messages. QNX also has a strict real-time priority system, so this doesn't hurt interrupt processing latency. So everything running in a thread uses the regular locking mechanisms, rather than depending on interrupt lockout. Something like that might be a better fit to Rust's locking model. Either that, or the language has to know about interrupts, as in Modula I.
- jacquesm 10y agoAnd that's the way to do it if you value latency rather than simply maximizing throughput. In real time situations latency is usually the more important factor. One thing about those interrupt messages ('signals') in QNX parlance, they get processed before any other messages.
- Animats 10y agoQNX has bounded latency. A standard test in the real time world is to hook a square wave generator up to an input that cause an interrupt, and run a program which gets activated by the interrupt and turns on an output. You watch the input and output signals on an oscilloscope. If there are any outliers, it's not real time. (A QNX rep once told me they'd had problems with x86 boards that did things in "system management mode", stealing CPU cycles from the real work and messing up the response time. They had a quiet blacklist of unacceptable embedded boards.) Linux has a long history of long interrupt lockouts. It's gotten better.[1] The phrase "95% real time" is used. Kernel drivers can lock out interrupts, so you have to watch for drivers that are not real-time qualified. That's the trouble with doing real work in an interrupt handler. Usually you have to activate a thread after an interrupt anyway, so there's no overall performance gain in doing work at interrupt level. [1] http://events.linuxfoundation.org/sites/events/files/slides/Real-Time-Linux-Comparison-Bridgers-ELC2015.pdf http://events.linuxfoundation.org/sites/events/files/slides/...
- belovedeagle 10y agoSorry, but you're rather sure of yourself when it's not clear whether you understand the constraints kernel writers are operating under. On many platforms simply enumerating valid RAM addresses where a heap may be constructed, let alone mapping them, is going to require considerable effort. It will inevitably be necessary to use memory somewhere off the stack to achieve that effort. Yet it will also be very difficult to write a custom allocator for that environment. One choice, for example, would be to rely on the bootloader's handling of .bss sections to allocate a temporary 'heap'. Haven't tried it, but it probably gets the job done well enough to bootstrap a real dynamic allocator. The point is, though, you can't just say "throw lazy-static and a custom allocator at the problem". Note, for example, my proposed solution requires writing the custom allocator entirely outside of Rust, since it can't access any Rust statics. It also requires two implementations of the custom allocator - one for bootstrapping, and the other after bootstrapping. These will have to be dynamically selected between at runtime since (AFAIK) Rust is hardly going to support static switching between them. Then you have to consider interoperability between them. Finally, not all kernel designs are prepared to do any kind of dynamic allocation at all: microkernels which hand all available physical memory to userspace for management there cannot dynamically allocate (except, perhaps, for O(1) of allocation in a small, static heap - but at that point, what's the point?).
- bascule 10y agoYou are making the exact same strawman argument as the post I was responding to. I gave a specific example of how lazy-static solves a specific problem mentioned in the paper, and as far as I can see nothing you have said refutes that. Clearly YMMV as to whether or not you can support a kmalloc()-style API. If you can, allocators will be great for you, and if not they are worthless. I didn't mean to imply Rust has one-size-fits-all solutions to these problems. Rust provides a lot of solutions to various problems, and it's up to you as the Rust developer to figure out which ones are applicable to your problem at hand.
- belovedeagle 10y agoSo what you're saying is, "if your use-case doesn't support kmalloc then shut up and go away, no statics for you!"? That's ridiculous, inappropriate, and generally unhelpful.
- rdtsc 10y ago> First, a linear sequence of asynchronous operations does not appear in a linear piece of code. Instead, it is spread across a series of many small functions. Largely unrelated to Rust, but I want to point out that that is a powerful insight. It took me a while to internalize that. Once you see it, you'll understand why asynchronous, callback-based programming is usually inferior to other models (green threads, channel, lightweight processes and yes, threads). There are some exceptions for course, say when callback chains are short, like a web proxy, in the an embedded world, or a short demo code someone pasted on SO. Another way to think about it is that "an sequence of callbacks forms an ad-hoc execution context, like a thread almost, except it is spread all through various functions, not very well specified, not in one single place". Now perhaps in this style you can avoid CPU locks, but if callbacks are used for concurrent IO, you are back to the the need to protect global data from concurrent modifications. For example, if a callback chain starts, say cb1, cb2, cb3 but stops at cb2 while it was modifying some global data. Then another user request (or other such event) comes and it starts running cb1, cb2, cb3. It will possibly start modifying the same global data before it was in a consistent state. Next thing you know is you need something like a lock or semaphore. And sure enough such a thing exists, here is an example in Twisted: http://twistedmatrix.com/documents/8.1.0/api/twisted.internet.defer.DeferredSemaphore.html http://twistedmatrix.com/documents/8.1.0/api/twisted.interne...