(also as an issue at https://github.com/tock/tock/issues/4370)
Grants and allowed buffers provide a mechanism for capsules and other
kernel components to use and/or access memory bound to the lifetime of
("owned" by) a process. Commonly allowed buffers are used to
send/receive data on behalf of a process using lower-level drivers,
sometimes using DMA or other asynchronous hardware, and grants are used
to store metadata related to a process.
Grants were originally design with three important goals in mind:
1. No dangling pointers: it is not possible for a capsule to access
grant memory after the process has been reaped or an allowed buffer
after it has been unallowed.
2. No zombies: It should be possible to deallocate process memory
without waiting for outstanding hardware operations. I.e. the kernel
should be able to reap a process's grants and allowed buffers as soon as
it terminates the process.
3. Infallible deallocation: unallowing a buffer should always succeed.
4. Availability: the kernel should be always be able to access grant
memory at least once per call-stack.
Accomplishing all four simultaneously is challenging, and has lead to a
design that either precludes or makes cumbersome and inefficient
zero-copy operations on granted memory.
This proposal outlines a design for two new grant access mechanisms. One
that achieves all four goals while enables a limited form of zero-copy
functionality. A second that enabled general-purpose zero-copy
functionality (including through asynchronous DMA), but sacrifices
infallible deallocation, availablity and the no-zombie guaratees and, in
exchange, requires users to have elevated trust (via a capability).
## The case for zero-copying granted memory
The current grant (including allow-ed memory) access mechanism only
allows references with lifetimes bounded by the scope of a function. A
consequence of this is many capsules adopt the following patterm:
1. Allocate a static buffer
2. Copy (some) grant data into the static buffer
3. Pass ownership of this buffer to a driver
4. Pass ownership back. Go to step 2.
The downsides to this pattern are
- Extra copying
- Extra allocation
- Extra logic
Logic is both implementation and maintenance complexity, but also
generated code size.
There is no good solution to sizing allocations. Too small and the
control logic will ruin performance. Too large consumes what is
typically a precious resource. No size is large enough to accept
arbitrary sized allow-ed buffers.
Copies are a performance concern in some applications.
Zero-copy could address these downsides.
## Different use-cases, different trade-offs
The two main use cases for zero-copy we consider are those that do not
require asynchronous hardware access to memory (e.g. DMA), and those
that do.
We can satisfy all four original requirements while allowing the former
use case.
However, concurrent and zero-copy DMA is fundementally incompatible with
the last three of the original requirements. If a DMA is ongoing to user
memory we cannot reap that proccesses memory, we cannot respect a user's
wish to deallocate, and the kernel itself may not be able to
concurrently access that memory while DMA is writing to it.
#### Memory-Mapped FIFO UART
This is a typical non-DMA capable UART (such as the ns16550). The CPU
can read/write to the UART's FIFO by reading/writing to a memory-mapped
register. The process provided buffer for sending/receiving data is an
arbitrary length, and almost certainly bigger than the UART FIFO
(typically just a few bytes), so a single send/recieve operation will
need to be done in steps. The UART is slow compared to the CPU, and we
do not want to wait for the FIFO to clear synchronously, instead relying
on interrupts to resume transmission/reception asynchronously.
As a result, it's also possible for a process to unallow or replace the
allowed buffer while the UART is waiting for the FIFO to clear. The UART
should discover this and react appropriately (e.g. short cut the
operation), but it need not necessarily be able to complete the
operation.
We want to pass the allowed memory from, e.g., a console system call
driver to the UART driver, and let the UART driver handle the logic
necessary to track how much as been sent/received so far, and where to
continue from, without having to allocate additional memory and without
having to continually call back to the console driver.
#### DMA Ethernet
This is an Ethernet device that has one or more DMA channels for
receiving. The CPU writes a base pointer and length to each
memory-mapped registers for each channel's and the hardware
asynchronously populates that memory with received MTU-sized frames. The
process provides a large, variably sized buffer for receiving data
potentially larger than the MTU size. Because receiving one or more
frames may take an abitrary amount of time, the CPU should do other
things while it's waiting rather than block. As a result, to effectively
use the device, the driver should chop up the process buffer into
MTU-sized slices and receive on as many slices as there are channels,
then rely on interrupts to signal completion of DMA operations.
We want to pass the allowed memory from, e.g., a UDP system call driver
to the ethernet driver, and allow the ethernet driver to reference this
memory directly in the DMA, rather than copying it to a potentially
large buffer. We _must_ retain goal one---a dangling pointer that's
reused for something else might result, for example, in leaking some
secret unintentionally over the network---but the ethernet driver is
trusted enough (by the board) to release memory for reclamation to relax
goals 2-4.
## Two New Grant Mechanisms
Here are described two new mechanisms that intend to solve the two
different zero-copy patterns.
### `ARef` (Allow-Lifetime Reference) & `PRef` (Process-Lifetime
Reference)
`ARef` & `PRef` are similar types that differ only in that the first is
bounded by the lifetime of an allow, and the second by the lifetime of a
process. They are both a sort of reference (generic in what they point
to), and they have `'static` lifetime.
Neither are directly dereferenceable. Instead, capsules and drivers must
first convert them to a live version (`LiveARef<'a>` and
`LivePRef<'a>`). The difference between the live and non-live versions
is that the live versions _can_ be dereferenced (they are smart
pointers), and have a corresponding lifetime that ensures they do not
outlive a scope narrower than any process could be de-allocated, or
buffer unallowed.
The conversion to live is cheap (a load / compare), and fallible (it
returns an `Option`). Live references have the same caveat as legacy
entry in that they only work within a given function. However, a live
reference can be frozen again (which is zero-cost and cannot fail), and
so stored globally. Notably, while live, these reference can be modified
and, e.g., broken apart into packets or the portions of a slice that
still needs to be transmitted.
ARef/PRef work by storing with each process / allow a generation
counter. ARef / PRef themselves have both the counter of when they were
created, and a reference to the counter to compare to. All ARef/PRef can
be immediatly invalidated by incrementing the counter. This is done in a
scope where no LiveARef/LivePRef are allowed to exist.
These types are applicable in the non-DMA case. For instance, we can
pass a LiveARef to a uart driver. It can write as many bytes as it
likes, then freeze the remainging sub-slice and store it. Later, on an
interrupt path, it can try covert to live and continue. If the
conversion fails, the buffer must have been un-allowed and it can report
this outcome. ARef/PRef also support an iterator pattern for use cases
like this.
ARef/PRef do not suffer from availability problems as they are shared
references. They can be requested as many times as required on a call
stack. They can also all be immediately revoked, causing any future
attempts to convert to live reference to fail. They cannot dangle as the
live versions have lifetimes that bound them sufficiently.
ARef/PRef are not appropriate for DMA wherein the system is doing other
things while DMA takes place. Hardware will not perform the checks that
the live conversions do, and also will outlive the lifetimes that guard
the live references.
### `Ref` / `RefMut`
For DMA, we need to ensure that memory does not have its lifetime end
while DMA is ungoing. DMA is unbounded. For this reason, we suggest
reference counting by the kernel, which can also block de-allocaiton and
fail subsequent allows if it finds non-zero reference counts.
`RefCell`, and its referrence types`Ref` and `RefMut` are the types from
the core library which implement reference counting. (Note the lifetime
we provide for these references is `'static`). These provide a
sufficient implementation of reference counting for our purposes. We
allow both `Ref` and `RefMut` to the grant data, and `Ref` to allow-ed
data.
Misbehaving capsules and drivers cannot break safety, but if they leak
the `Ref` or `RefMut` will create zombie processes. Nothing short of a
system reset is likely to save a suffciently broken driver.
Because accesssing these types breaks three of our original design
goals, they are both locked off behind a capability, and can be turned
off entirely at a configuration level. The intent is that these be used
solely when other mechanisms do not work.
### Legacy mechanism
`ARef` / `PRef` are proposed as general replacement for the legacy
mechanism. `Ref` / `RefMut` are not as they have drawbacks.
However, to to support the existing codebase the legacy mechanism is
still supported in parralel on a case-by-case basis. There are
conditions on using them in a mix-and-match way.
For any given grant:
Using `ARef`/`PRef` at all, or having an active `Ref`/`RefMut`, blocks
use of the legacy mechanism. Being inside a grant via the legacy
mechanism blocks both of the two new mechanisms. ARef/PRef cannot be
used in conjunction with `RefMut` (they can be used with `Ref`)
## Initial results / takeaways
### Code size savings
A simple "hello world" board was created with a console, uart mux, and
uart. It was compiled with two versions of the console/uart: the
existing version and a new zero-copy version.
The new version saved 1K of text.
### Impementation simplicity
Insert image of side by side code here
## Nice externalities
Other things that this design solved at the same time (but are somewhat
orthogonal):
- Reentrancy
Previously, if a grant was entered it could not be entered again on the
same call stack. ARef/PRef/Ref are all inherently shared references and
solve this problem by just allowing accessing grants multiple times.
- Variable number of allows
Scatter/gather lists with arbitrary number of ranges now works with a
fixed (only 1!) allow number.
Because changing the generation counter is somewhat orthogonal to
changing the pointer, we can allow a new system call to change the
pointer but not the counter.
- Drivers/Drivers can notice buffers being ripped out underneath them
User no longer has the ability to change a slice address / length
underneath a capsule. Only disallow entirely.
