The paper titled “Multiprogramming a 64 kB Computer Safely and Efficiently” is an interesting work that brings multiprogramming feature support to microcontroller level.

Problem

Microcontrollers have limited resources in terms of power budget, memory capacity and hardware protection mechanism. In these systems, applications and the OS share the same address space. With emerging class of embedded platforms running multiple applications rather than a single application, there is a need to support multiprogramming features such as fault isolation, dynamic memory allocation and flexible concurrency. For instance, a USB authentication device runs multiple independent but related applications on a single embedded device.

Issues with Previous Approaches

• Traditionally, isolation was not an important aspect in microcontrollers. Instead the focus was on writing completely bug-free code. As a result, there was no isolation between components.
• Updates were system wide, i.e, replacing individual components without restarting the whole system was not possible
• Static memory allocation was used to ensure long-running and fault-free operation and prevent unpredictable memory exhaustion due to dynamic application behavior. However, this approach has the drawback of fixed concurrency at compile-time.

Tock Overview

To overcome these limitations, the paper proposes Tock - new operating system for low-power platforms that takes advantage of protection mechanisms provided by Memory Protection Unit and type-safety features of Rust programming language to provide a multiprogramming environment. As a result, Tock supports:

• Isolation of software components.
• Updation/restart/removal of individual (user-space) components independently.
• A combination of static and dynamic memory allocation techniques to balance safety and reliability of static allocation with flexibility of dynamic allocation.

Capsules

Tock kernel is built out of components called capsules. These are instances of Rust structs with fields, associated methods, and accessible static variables. Capsules are invoked in response to hardware events and system calls from processes. Capsules have a shared stack and no heap. They communicate through references and method calls, thereby incurring low overhead. Device drivers, timers etc are implemented as capsules. These are the trusted system components. To ensure isolation, capsule fields such memory pointers are not exposed directly to clients. They are exposed as Rust slices - clients cannot access memory directly through pointers, instead they must create a slice of memory to access it. This prevents clients from corrupting memory that they do not have access to.

Processes

Untrusted third party user applications are implemeted as processes. These are scheduled preemptively. They communicate via system calls & IPC. A context switch takes approximately 340 cycles and therefore processes incur a higher overhead as compared to capsules. MPU provides memory isolation between applications as well as between applications and the kernel.

Grants

Static memory allocation must trade off memory efficiency and maximum concurrency. Allocating more memory than required wastes the limited resource while allocating less memory than required can cause unexpected application failures. On the other hand, dynamic memory allocation could lead to unfair share of memory among processes, causing unpredictable shortages with one process’s demands impacting capabilities of others. To resolve these issues, the paper proposes Grants - fixed size per process kernel heaps. Allocations for one process no longer affect others. System proceeds even if one grant section is exhausted. All process resources are freed immediately upon process termination. Even if there are any dangling pointers left, they can’t be used - Grants ensure that references are only accessible when the process is alive.

Comments

• Hardware parallelism ?
• Need to port applications
• Attack/Threat model ? Applications developed by 3rd parties are modelled as malicious
• Dependency on Rust programming language - support ?

Access presentation here.

Reference

Amit Levy et al, “Multiprogramming a 64 kB Computer Safely and Efficiently”, Proceedings of the 26th Symposium on Operating Systems Principles. ACM, 2017