Task lifetimes

When a thread exits or is killed, SlopOS frees the record the kernel kept about it exactly once, and only when nothing can use it any more: no CPU is running it, no queue holds it, and no other part of the kernel is in the middle of looking at it. That rules out a family of kernel crashes, the ones where one CPU reads a thread's record just after another CPU freed it. Both a machine proof and tests check the rules.

The record (we'll call it the task) holds the thread's registers, its kernel stack, its signals and its place in the scheduler. The technique for freeing it is not ours. Counting references and freeing at zero is how Rust's Arc works and how Linux manages its task records, and the two refinements below, a task holding a reference to itself and deferring the free when the moment is wrong, also come from Linux. SlopOS adds enforcement: the Rust types permit only the sanctioned moves, and a build check rejects code that goes around them.

Nothing here changes how you write programs, but it explains why exit and kill behave as described in Processes and signals and Scheduling and waiting. Only the last section assumes kernel experience.

Why freeing a task is hard

In an ordinary program you usually know when you are done with an object: the function that made it returns, or the list that held it is cleared. A task is harder, because many unrelated parts of the kernel point at it, on several CPUs at once, and none of them is in charge:

• the scheduler's run queue, if the task is waiting for a turn;
• a wait queue, if it is waiting for something;
• the task table, so that kill and waitpid can find it by number;
• its parent, which will ask how it ended;
• the CPU running it, which is using the task's own kernel stack.

None of those let go when the thread exits, so freeing the task at exit goes wrong in concrete ways:

• A lookup on another CPU. CPU 1 looks up pid 42 to deliver a signal and gets a pointer to its task. Meanwhile pid 42 exits on CPU 2 and its record is freed. CPU 1 now writes the signal into memory that belongs to something else.
• A late wake. A task blocked on a pipe is killed and exits. A moment later the pipe's writer wakes the pipe's wait queue, which still points at the dead task.
• Freeing the stack it runs on. A task's last act is to run the code that cleans it up. If that code frees the task's kernel stack, it frees the memory it is executing on.

All three are use-after-free bugs. They are among the worst a kernel can have because the crash doesn't happen where the mistake is: the freed memory gets reused, and the corruption surfaces somewhere unrelated, later, usually only under load.

How reference counting solves it

The fix is to free the task when nobody holds it any more, whether or not it has exited. Each task carries a count of references, one for each holder in the list above. Taking a reference adds one, giving it back subtracts one, and whoever brings the count to zero frees the task, so no holder needs to know about the others or the order in which they let go.

That fixes the first failure: CPU 1's lookup takes a reference, so the record stays put until CPU 1 is done with it, even if the thread exits in the meantime. The second is handled with a lighter kind of reference. The pipe's wait queue records only the task's number, which doesn't keep the task alive. To wake the task, the queue first asks the task table for a real reference to that number. If the task is gone the request fails and the wake does nothing; otherwise the wake holds the task safely while it works.

Two rules keep the count reliable:

• The subtraction decides who is last. It is tempting to write "if the count is 1, I'm the last holder, so free it". But two CPUs can both read 2, both subtract, and neither frees; or a new holder can appear between the read and the free. One atomic operation lowers the count and reports what it was, and exactly one holder ever sees it go from one to zero.
• Only references keep a task alive. Code that has a pointer to a task may not assume the task is alive. If it needs the task, it holds a reference.

Why each task holds a reference to itself

Some states of a living task have no natural holder. A kernel thread blocked in a wait sits in no run queue, and a new task is in the task table before it is in any queue. If nothing held a reference at those moments, the count could reach zero and the task would be freed while alive.

So every task holds one reference to itself, its existence reference, as Linux's task records do. It is handed over when the task is entered in the task table, and taken back only when the task is reaped: removed from the table after it has exited and its parent has collected its exit status (or it had no parent to collect it).

Because every live task keeps itself alive, the task table doesn't have to. It holds only weak references, which say where a task is without keeping it alive. A lookup by number turns a weak reference into a real one if the task still exists and fails cleanly if it doesn't, so a stale entry can never bring a dead task back.

Who owns the running task

The third failure, freeing the stack a task is running on, needs one more holder: the CPU itself. Each CPU keeps a reference to the task it is running in a slot of its own, so that task can't be freed. A task also can't be reaped while any CPU is running it, has it marked as its current task, or uses it as its idle task; the kernel refuses and tries again later.

Switching from task A to task B is the delicate moment, because the CPU must give up its reference to A while it is still running on A's stack. So it moves B's reference into its slot, sets A's reference aside in a second slot, switches stacks, and only once it is on B's stack gives A's reference back. Because of this a CPU can switch straight from one task to the next, without passing through its idle task in between.

When a task can't be freed immediately

Freeing a task is a lot of work. Its kernel stack and saved registers go back to the memory allocator, and the allocator may need to tell every other CPU to forget cached addresses and wait for them all to answer. The last reference is often given back somewhere that work can't be done:

• With interrupts switched off. The other CPUs answer with interrupts, so a CPU that waits for them with interrupts off waits forever.
• While holding a lock. If another CPU needs the same lock before it can answer, each waits for the other forever (a deadlock).
• On the dying task's own stack, as above.

The task table gives back lookup references while holding its lock, and the scheduler gives them back with interrupts off, so this is the common case.

So giving back a reference happens in two parts. The subtraction is always immediate. If it was the last reference and the moment is safe (interrupts on, no lock held, the task not running anywhere), the task is freed on the spot. Otherwise it goes on a list of dead tasks, which SlopOS calls the graveyard, and the CPU frees everything on that list at its next safe moment: when it releases its last lock, returns from a system call, or goes idle. Whether the moment is safe depends only on what the CPU is doing, never on the count. Linux's real-time configuration defers the last release of a task in the same way.

How Rust's ownership rules help

Most of the rules above are about ownership, which the Rust compiler can check:

• There is one way to hold a task. Outside the trusted core, code holds a task only through a handle type (TaskRef), the kernel's equivalent of an Arc<Task>. Copying a handle takes a reference, and when a handle goes out of scope Rust gives the reference back through the routine that decides whether to free now or later. Code can't forget to give one back or give one back twice, and a killed task unwinding its stack releases everything it held without special code for the kill.
• A task other CPUs can see is read-only. It is reachable only as a shared reference (&Task), and Rust forbids changing data through a shared reference unless the type allows it. So fields that change after the task is published are atomics, or live in cells that demand proof of exclusive access.
• Exclusive access has to be proved. Only the CPU running the task, or the CPU switching to or from it, may write its saved registers. The switch can't take a lock, so the writing code must instead hold a small value (a witness) that can be created only in those situations and can't be passed to another CPU.

How we know it works

The logic is proved with Verus, a tool that checks a mathematical proof against a model of the code. The proof covers seven properties, among them that a task with references is never freed, that exactly one holder sees the count reach zero, that a task is in the table exactly when it holds its existence reference, and that a task a CPU is running is never reaped. It also includes the tempting wrong version ("if the count is 1, free it") and shows that it reaches a forbidden state, so the properties aren't trivially true.

The ordering of memory operations between CPUs and the pointer handling inside the queues are outside the model. Those are checked by running the code under KernMiri, an interpreter that detects undefined behaviour, and by kernel tests. See Proofs and Miri.

For contributors

The invariants a change must keep, and why.

Only the final strong reference frees a task. Outside OSTD a task (KArc<Task>) is held only through TaskRef, and every drop goes through task_put. Raw task pointers exist only in the placement and link primitives, the per-CPU control region and the pre-heap boot stubs; scripts/check_task_ownership.sh enforces this.

Finality comes from the decrement, deferral from the context. The one-to-zero winner in task_put gets a ParkedTask token that graveyard operations take by value, so a double destroy doesn't type-check. It destroys inline only if drop_context_is_safe() and the task isn't dispatch-pinned; otherwise it pushes onto the graveyard, a lock-free stack drained at the bottom-half point. Never decide finality from a strong_count read, and never key the deferral on a count.

A task is registered if and only if it holds its existence reference. register_task claims the flag only after the reference exists, and reap_task_registration drops it only after releasing the registry lock, because that drop may be final. While the existence reference is held, no container's release can be final, which is why those releases may be a bare decrement under a lock with interrupts off.

A container owns what it links. The ready queue, the remote-wake inbox, the deferred previous-task slot and the wait maps each hold a member by an intrusive link plus one strong reference parked as a raw pointer, and the placement state machine (slopos-ostd/src/task/placement.rs) is the only way in or out:

Every retain or leak pairs with exactly one reclaim. An unmatched park leaks the task forever; a double reclaim is a use-after-free.

The reap gate must stay a disjunction. task_is_dispatch_pinned holds if the task is on a CPU, or some CPU's control region names it as current, or it is some CPU's idle task. The CurrentTask and IdleTask borrow guards (both !Send and !Sync) take no reference and rest on the second and third disjuncts. Weakening the gate breaks those guards while the Verus proof keeps verifying, because its model sees only the atomic step.

No owning reference crosses a switch in a stack frame. The incoming task's reference goes into current_task_ref and the outgoing one into the deferred previous-task slot before the register switch; the successor releases it.

Fields written after publication need a witness. The saved register context, FPU area and user-mode round-trip slots live in TaskOwnCell, and writing needs a sealed TaskExclusive witness (CurrentTask or SwitchWindow). A registered but unpublished task is not exclusive, since the registry and diagnostics can reach it; before publication, use KArc::get_mut on the sole strong reference. The accessor returns *mut T, not &mut T, because two witnesses can coexist in nested frames (an interrupt handler above a syscall on the same task) and two &mut T would be undefined behaviour. Rust-for-Linux's Opaque<T> makes the same choice.

FPU state is switched eagerly, because lazy switching leaks a stale register file across a privilege boundary (CVE-2018-3665). The CPU's owner slot is compared, never dereferenced, so a dead task's address left there is harmless.

The proof (verification/proofs/task_ownership.rs) models each operation as one atomic step, so a change to memory ordering, the intrusive links or the weak count also needs KernMiri and targeted tests.

Further reading

• Shared-State Concurrency in the Rust Book, and its chapter on Rc<T>. Start here: reference counting from first principles, and why Arc is the thread-safe kind.
• Arc, from the Rustonomicon's chapter on implementing Arc. How the counting works inside, including why the final decrement decides and which memory orderings it needs.
• Adding reference counters (krefs) to kernel objects in the Linux kernel documentation. The same idea as used throughout Linux, with the rules for taking a reference while another CPU may be dropping the last one.
• Common Concurrency Problems, chapter 32 of Operating Systems: Three Easy Pieces. The deadlock conditions behind not freeing a task while a lock is held.

In the source