#structured concurrency

a rant that ended up flowing into "structured privileges"

Thinking about the execve(2) interface of UNIX, particularly with elevated privileges - especially in combination with the UNIX philosophy of little tools that do small jobs well.

This generalizes, actually - the same ideas of privilege segregation could apply within a process if languages and runtimes took advantage of modern kernels' support for it - at least in Linux, where processes and threads are basically the same kernel primitive, with just a few configuration differences.

Anyway, it bothers me that the default behavior is that if I start a root program, everything it executes is also root. In some sense, the ideal default for a program with a privileged effective UID and an unprivileged real ID is that the execve system call drops privileges - and if you want to keep privileges, that should be an explicit flag.

Even more ideally, this wouldn't be a flag that you, as the program with privileged effective UID or effective capability set or whatever, get to just set however you want - this should be some sort of object, like a file descriptor or a 128-bit random key or a pointer into read-only mapped memory, which is given to you by the caller who gave you elevated privileges. So your options are either "drop privileges" or "keep any privileges that your caller allowed you to keep" - notably absent from your options is an unconditional "keep privileges".

Of course, one problem here is that at some levels of abstraction, forking another process should be an implementation detail - when I call a program as root, I shouldn't have to know "this program wants to fork a child", let alone details like which child programs, how many, how deep the process tree goes, and so on.

So execve isn't exactly the right boundary here, at least not always. But here are a couple examples where the execve boundary is user-facing and explicit, and is the right boundary:

Suppose I want to run a privileged `find` program - because it needs to look inside directories that only root can read, and then I want to run some un-privileged command per file path - the most secure thing, especially if I don't have time to audit the command's source and build and binary for problems, is to prefix my exec arguments for find with something like sudo -iu "$USER" so that the child process of find drops privileges back down to my user before running the command.

For another example, suppose I want to run something like fzf on a list of paths, and then I want fzf to use `bat` to preview those files. bat could need read-only root privileges if some of those files are only root-readable, but there's no great way to give those privileges to just bat instead of fzf - at best, I run sudo once before running fzf, sudo caches my credentials, and then I set the preview argument of fzf to include a sudo call. But this isn't friendly to building larger programs: if the fzf call is inside some larger script, that script now has to either unconditionally include that sudo call, or include it or not based on either a flag that is passed in or if it already has special privileges.

Going back to how this generalizes, this same problem happens with libraries - instead of calling into another program, you call into some library, but either way, you probably don't have time to audit the whole thing, and it often doesn't need all the elevated privileges that you have - if I've got code to parse YAML inside my process, those instructions don't need any privileges besides access to the input bytes and enough memory to return the parsed result, and yet I have to go out of my way to isolate them and drop privileges if I want to be safe from some exploitable parser bug.

Ideally, code should have to go out of its way to explicitly take privileges that it either needs or can optionally use, as a kind of parameter. The whole system, from the ground up, would be built with APIs which have a bias towards dropping privileges and which require every privilege to be passed in from higher up in the call tree. Then the path of least resistance aligns with security: if you're writing code which doesn't need privileges, you don't go out of your way to take them from the caller - if you need privileges to do something, you have no choice but to reveal it in the API.

The only wrinkle here is that people should be able to write middleware which doesn't know or care about privileges, but is transparent to them. The simplest solution is to do what Go did with its context type - force middleware to take that parameter, and pass it through just in case the thing it calls needs it. This is... better than privilege use being invisible, but it's still pretty bad, especially when we generalize it to a granular "permissions" object, since middleware would need an arbitrarily permissive type: instead of knowing if we're calling something that requires privileges, we are back to calling something that might use any of the privileges we fed into it, and we can't know without inspecting the middleware.

In languages with templates, the permissions could be expressed as a template parameter, and then it's at least clear that the middleware takes whatever permissions its callee requires - and someone higher up in the call stack is defining the callee, so they have the responsibility and knowledge of those permissions. But this still isn't really enough, that's just a nice way to make the type system transparently propagate information about elevated privileges to the places where a developer is most served by knowing it.

But at runtime, we need a distinction between a usable privilege, and an unusable "sealed" privilege which is just being passed through code from a higher caller to a transitive callee which has what they need to unseal it.

This has been on my mind for a couple years now, at least. The overarching theme here is that ideally software has a reified representation of all interesting privileges, which ideally is both visible in the type system and actually enforced at runtime, and that code should be forced to be explicit whenever it uses or passes privileges to do anything.

Unyielding

The Function Color Myth

Some Thoughts on Asynchronous API Design in a Post Async/Await World

Structured Concurrency

on the one hand, preemptive, implicit, unpredictable multitasking is awful for reasoning about code behavior any time there can be relevant side-effects, but

on the other hand, preemptive, implicit, unpredictable multitasking is fine and a significant benefit to writing code if no side-effects that could slip in matter.

Here's where I'm at now with this:

What we really need is a system which requires cooperative multitasking unless you have written code which is "pure" code. If something in the system running your code can prove or has been told that your code need not care about side-effects, then it is fine for the system to do preemptive multitasking anywhere in your logic. But, code rootwards in the call tree from your code must be able to control if preemptive multitasking happens in your code.

Because preemptive multitasking is an optimization, the dangerous kind which is liable to change behavior or introduce bugs unless properly constrained, and like most optimizations it cannot be done without some sort of dialog between the thing implementing the optimization and the people or code which is aware of the bigger picture of the specific use-case, situation, and relevant caveats.

The simplest version of this seems trivial to do.

What's left is to figure out how to best make it granular, because stop-the-world blocking of all preemptive multitasking is rarely necessary, and would probably cause problems if code regularly relied on it to prevent race conditions.

Okay, so, here's roughly the thought process, although by now I've re-ordered and re-written several chunks of this, because the original thought process was a meandering thinking-out-loud. And this still is that, but I've tried to make it at least a little coherent.

Clearly "not safe to preempt" has to be transitive, from the caller down. Even if some pure code by itself is fit to get preempted, and even if we had a system where that code actively indicated that it is compatible with preemptive multitasking or did some sort of yield-if-needed operation, if that pure code sits in a code path which cares about any side-effects that might happen when it is preempted or something else is scheduled concurrently, then it needs to be able to call into that pure code without that code being preemptible.

Caveat: for some code, timing and latency is a relevant side-effect. This is why mainstream preemptive multitasking operating systems are so terrible for trying to build real-time computing systems - you can't guarantee any upper time bounds if any number of other things can be preemptively scheduled in between all of your operations. So whatever method we use cannot even assume that code paths of entirely pure code without side-effects in the semantics of its language is safe to preempt.

Finally, part of why "coloring" functions with an `async` keyword is good is that when `async` is transitive rootwards on the call tree, we always know when something we call is forcing concurrency problems onto us. Of course, if you can perfectly contain the concurrency within your implementation then there might be a way to split your call stack into a call tree of coroutines which are concurrent with each other but isolated from all other concurrency, wait for all those to finish or get cancelled, and that's fine to not reveal to the caller. But if your use of concurrency can breach containment in any way, you shouldn't even have the ability to express your code in a way that hides that from your caller. So that is the wisdom of function "colors".

But if we have an explicit yield-if-needed operation, should it be colored async? If you're already convinced of how great `async` color which contaminates all callers recursively is, and if you've accepted the wisdom of structured concurrency that concurrency should not be allowed to breach containment or slip in under you without you knowing about it and consenting, you might be tempted to say that the answer is obviously yes. Every instance of yield-if-needed is an opportunity for side-effects, after all.

So here's the key realization: yield-if-needed isn't saying "I use concurrency here (you are using concurrency by calling me)", it's saying "I yield to concurrency (you can use concurrency while calling me)".

So they are actually really different things, that we need to handle differently. Code which uses concurrency in a way that breaches containment is non-optionally forcing you to use concurrency, and it needs to be seen and managed as a place where something else can be scheduled underneath you. But code which merely yields to concurrency without using it is just optionally concurrent.

And so we could have a system where we can tell the scheduler "hey, I'm going to execute some optionally concurrent code now, but concurrency in this case is not safe for my logic, so don't schedule anything else in the meantime (and I accept that the only choice this might leave you with is to give me a cancellation signal or just kill me if it takes too long in total)".

Also, if yield-if-needed is an async-colored operation, then libraries doing pure logic can't just call it without tainting themselves as impure, as async-colored, and compilers or other tooling might need to do smarter and more extensive code transforms to automatically put it in for you if you don't care and just want the computer to do it for you. Because async-coloring in many languages changes the implementation of a function to return something that at a minimum holds the state which must be saved between pausing the now-interruptible function and resuming it.

So if we decide that yield-if-needed is not an async-colored operation, then

only code that introduces concurrency is async-colored, rather than any code which is not harmed by yielding to concurrency, and

yield-if-needed becomes something that actually could be slapped literally between any two operations in pure non-async code.

So finally we get to the breakthrough: we upgrade the yield-if-needed operation to yield-if-needed-and-safe.

The scheduler brings the "needed". The caller brings the "safe".

Of course, the scheduler has final say, so if you try to disallow yielding for too long you get some sort of cancellation signal, and if you don't obey your process gets killed. In fact I think there doesn't even need to be an explicit cancellation signal in the simplest version of this: when code sees that the "do I need to yield?" value is no longer zero, it could consult another "is it safe to yield?" value. If that says no, it quickly bails out and goes back to the caller with a "scheduler said to yield before I could finish" error. Or maybe there is also a good argument in some cases for the code to yield in that situation, and then only upon being resumed go back to the caller with the "scheduler said to yield before I could finish" error. Either way, getting that error from something you called functions as the cancellation signal.

I really like this. I think this elegantly solves the problem:

if you have logic which really doesn't care about being preempted, you can just write code without thinking about it, and it's trivial for your tooling or the system to automatically inject preemptive multitasking,

if you are calling into pure logic you don't need to worry about whether or not it has an yield-if-needed operations, because they're yield-if-needed-and-safe operations, and your code gets to say whether or not it is safe,

yield-if-needed-and-safe no longer needs to be async-colored, because it can only introduce concurrency which the system has proven would be irrelevant if you followed its rules, or which you have told the system is irrelevant - it can no longer force concurrency onto your caller,

we can implement this in a backwards-compatible way which allows incremental migration: add the yield-if-needed-and-safe operation, and let code opt-into this mode where it can say "don't interrupt me until I say it is okay" but it will get killed if it doesn't yield for too long,

in fact we maybe no longer need the yield-if-needed-and-safe operation, because the system can do the same check that yield-if-needed-and-safe would do, and if it knows you don't want to be preempted, it can just not schedule the next preemption until the latest possible moment,

although the yield-if-needed-and-safe might still turn out to be useful, either as an optimization, or because there is a need for it which I'm not yet seeing.

And the cool thing here is that we could generalize this! We could have systems that let you take any arbitrary sequence of operations, and the entire sequence will either succeed without interruption or race conditions, or fail somewhere along the way because there wasn't enough time in the time slot you had from the scheduler. You still have to do the hard work of figuring out how to deal with any inconsistent state from partial completions, but you no longer have to worry about all the problems that can only happen if something else gets to operate on the same state at the same time.

We could even probably figure out how to do this across processes. So even shell scripts could say "hey please don't schedule something between these commands that I'm about to run". And if the shell script or its child processes take too long, the whole process tree starting from that shell script gets whacked. And it seems like it would be fairly trivial to pass information between the operating system's scheduler and any event loop scheduler or lightweight thread scheduler in user-space, so most software developers would only need to make the request once in whatever language or framework they're using, and it could apply across all the relevant nested schedulers that are in play.

The other way this generalizes is that it would be nice and probably necessary to have the capability for branches of the call tree to isolate their concurrency from all other concurrency. To let code say "I am using concurrency as part of my implementation, and I am fine with yielding to other coroutines which I spawned as part of my logic, but I need to be safe against races with other logic".

(Incidentally, the most mature and thought-out structured concurrency implementation I know of (the Python library Trio) lets you shield a branch of the call tree from cancellation by code rootwards on the call tree. And what I'm describing here is shielding a branch of the call tree from concurrency with code which is rootwards on the call tree. I imagine Trio has cancellation shielding and not concurrency shielding because in most async code, you want other stuff scheduled while you wait on I/O, and you can get away with putting off handling cancellation until you're done with something that needs to finish to keep things consistent. Meanwhile, I'm currently more focused in robustness against race conditions and how to get the benefits of cooperative multitasking while still being robust against code which fails to yield for too long, all while making guarantees about completing within some upper bound of time - so desirability of concurrency is no longer taken for granted, and cancellation is more starkly revealed to be something that needs to be a non-optional final warning. Notably though, to the extent that cancellation shielding can be permitted, it seems a lot like a special case of concurrency shielding.)

So this is all cool, but so far this solution is fairly all-or-nothing. The simplest implementation I described is absolute - there is a "need to yield" boolean (which we might consider turning into a "yield deadline" monotonic clock value) and a "safe to yield" boolean. Of course, we can implement more granular concurrency scopes/shielding on top of that mechanism. The trouble is actually coming up with how to make it more granular than "yes I'm fine with stuff preempting me" or "no I'm not fine with stuff preempting me". What we really want is a way to specify which stuff we are fine being preempted by.

And maybe the answer is almost just locks - mutexes, or read-write locks, the usual. In a sense, locks are how you say "please do not schedule anything else which uses this specific thing at the same time". Of course this was very hard for me to see because a lot of systems do not have locks for most things or actions which you might want to avoid concurrency for, and what locks they do have are often advisory. But if

everything which touched or did a thing in a way where races might matter was required to get a lock for precisely that thing, and

all locks were automatically released if the holder did not release them on their own soon enough,

then holding locks basically functions as precise specification to the system and its scheduler of exactly what you care about not having scheduled during your code.

An almost stream-of-consciousness ramble of something I was thinking about today.

By Default, Maybe Even Mandatory

The more I think about writing correct code, the more I feel like preemptive multitasking as the norm was a mistake. That operating systems should have been written from the ground up to assume that all good and correct software yields execution back to the scheduler every once in a while. That computer science education and software development tradecraft should teach and presume that cooperative multitasking is the only multitasking available or acceptable.

Preemption for the Uncooperative

Obviously robust systems must have preemption capability, in order to avoid denial-of-service from code which never yields control. So systems would still need the foundation of preemptive multitasking, and processes which do not cooperatively multitask would need to be preempted. The temptation which many operating systems followed is to just make this the norm - anything can be preempted at any time, thus your guarantees against race conditions are weak at best and every piece of the system has to do more work just to keep things sane in the face of multitasking.

But I'm almost ready to say that programs which don't yield control for too long should probably just get killed, ignored, presumed dead or compromised, timed out, invalidated, be stripped of any resources and locks they hold, and so on. At the operating system level, at higher levels of how you design your multiprocessing and distributed systems, in your business logic, at all levels.

Given enough time, all conceivable execution delays and communication partitions which could cause things to not get back to you soon enough to not be a problem will happen. We can either

write code on systems which force us to deal with it thoroughly and from the ground up, across our entire trade and industry and culture, which is cumulatively easier to get right once everyone knows and follows the patterns, or

we can keep living in a sea of code and systems overwhelmingly saturated with an incomprehensibly inconceivably large number of concurrency and latency problems just waiting to happen.

All You Need (Probably... I Just Make Shit Up On The Internet)

Obviously almost everything is in place already, we're just not using it to build systems which are consistently honest, helpfully explicit, and manageably controlled about where concurrency can happen.

In a typical modern operating system, when you call a system call, or at least certain system calls which tend to inherently entail delays and thus are natural points for scheduling or cancellation, you are yielding execution to the kernel. Now the kernel has an opportunity to go do something else, schedule another program, deliver a signal to your program or kill your program with a signal, and so on. The kernel only preempts your process if you don't call into a system call for long enough. Otherwise you're being cooperative. And in the real world, this is how lots of programs actually play. They don't have to be written to cooperatively multitask to do it, they just have to do operations which are natural scheduling or cancellation points, which most program do often enough on their own, because most programs are interacting with the outside world, not slamming the CPU with raw self-contained computation long enough to use up their time slot.

So what about the program that do want to hog the CPU longer than their time slot?

Well, we have the ability to trivially implement a "yield control if something else is waiting" operation which would have effectively zero overhead if it's not time to yield (at most a handful of machine instructions with one branch, and if you're pipelined and branch prediction matters, that branch can be predicted as taking the "no need to yield" path for hot loops and other pure computing logic, which is the only situation where the overhead of that check and branch prediction is actually a problem).

To me that seems like the only remaining primitive the OS kernel needs to provide to user-space to make this work. And it's trivial! Let's assume we're using a memory location for generality, though this could be optimized all the way to the hardware, with a dedicated CPU flag or register and exposed in the instruction set. Anyway, in the in-memory version, the simplest form is a fixed address on systems with an MMU and virtual memory, or perhaps it is provided by the kernel to the process during initialization, to be compatible with ASLR and hardware without an MMU. When the process starts up, the kernel sets the value at that address to zero. When it's getting close to the time when the scheduler would want to preempt the process, the kernel writes one at that address.

(Internally, on modern hardware with all cores busy, flipping the value at this address from zero to one might have to be implemented as a momentary preemption of user-space by kernel-space code. So you can see where the temptation comes from! A working multitasking kernel which does not depend on cooperative multitasking must have all the building blocks necessary for preemptive multitasking, and it is so natural to just let user-space processes partake in concurrency seemingly "for free" - it took humanity half a century of experience to get to this point where we're starting to realize that this is actually detrimental on the whole.)

Now, whenever the process wants to know if it should yield, it reads the value at this address. Is it still zero? You got enough time left to do some work before checking again. Is it anything else? Time to yield - if you checked reasonably often, you've still got ample time to go directly to yielding execution to the scheduler. Did you overwrite it, or take too long to check? That sounds like a you problem, if you don't yield often enough, your process gets preempted, but then it's just killed.

Notice that you're not being asked to gracefully shut down or pause or clean up anything. This isn't some situation where you gotta scramble to flush buffers, save state to disk, commit transactions, or anything like that. You're just being told its time to yield to the scheduler, and if you obey it is exactly the same situation that in a normal preemptive multitasking system would just happen automatically, without warning, unpredictably, possibly between literally any two machine instructions. But incidentally, in a lot of situations, this would probably make it easier to set up systems where you can have enough time to do those things, and fewer possible ways for those things to be interrupted or delayed or half-finished.

So we all gain the profound benefit of being able to pick or at least see where in our code concurrency can slide in and change the state of the world out from under us or give us an out-of-band signal like a cancellation.

And the price is that those of us who write low-level code which does nothing but raw CPU operations for longer than the time slot our process gets have to add an explicit `yield_to_the_scheduler()` call - and if it really really doesn't matter, then just spam it in enough places to be safe. Which is fine because we just established that it's going to be nearly zero-overhead unless you actually have to yield to the scheduler anyway.

Notably, some operating systems already have everything in place to do this. Linux, for example, writes the current time into an address which the process can read and knows about, so the process doesn't need to pay system call context-switching overhead every time it needs the time. In fact, one possible idea to explore for improving my extremely minimal suggestion is that instead of having the memory location work as a boolean, have it contain a deadline.

Beyond that, the structured concurrency people have basically figured out the big picture of how most of this looks for most code - you have operations which are explicitly points where something else could be scheduled or you could be cancelled. For simplicity and human friendliness you probably combine those two concepts together. When we restrict ourselves to languages and primitives where each operation is either explicitly a place where multitasking can be relevant to or intrude on our logic, or a place where there are definitely no relevant concurrency concerns, we can deal with concurrency better.

Exhausting Nuance

There is only one tricky part here. The reason that preemptive multitasking is so useful is that not all concurrency is equally relevant to whatever you're doing. Most of the time, there are specific changes to the state of the world which matter to our logic, and all other changes which might happen don't matter.

Preemptive multitasking kinda takes the gamble that most systems are heavily concurrent but most parts have no reason to care about what the other parts are doing. They are not obviously harmed by the fact that anything could happen between or during any operation they do, because nothing that could happen matters, and so those programs strictly benefit from magical invasive multitasking permeating them with an infinity of possible preemptions.

For example, a typical `sed` invocation which reads from standard input and writes to standard output doesn't care about anything. In between a bunch of pure CPU operations on memory, it will read and it will write, and either those operations succeed, or one of those operations fails and it tries to call another write to standard error with an error message, and then no matter what happens, it will try to exit. Files on the system can change and it doesn't care. If the file it was reading from is truncated while `sed` was reading it, to `sed` it's no different than as if that file always ended there. It could get frozen with a SIGSTOP and eternities could pass, the file it was reading from could get overwritten, and when resumed it would just read from the offset it left off, no different than as if that file always had those contents back when `sed` started. The file it is writing to could be overwritten many times, and `sed` doesn't care - it just writes, and either it's writing in ”append" mode, or it's writing at whatever offset it is currently pointing at and maybe it wins because it's the last write or maybe it gets overwritten and it doesn't notice. `sed` could be started on Linux, have a debugger attached to it, its entire memory could be dynamically copied into another dummy process frozen with a debugger attached, possibly on another computer running a different OS with a compatibility layer for Linux, and then it can be resumed, and it doesn't care.

Notably, in some of those cases, the program which called `sed` to do a specific job probably does care a lot about some of those possibilities.

I, and to some extent structured concurrency, takes a somewhat reductionistic view that conflates all concurrency together. You do an operation and it's either asynchronous or not. You run an asynchronous operation, and anything else that's asynchronous might happen. And in structured concurrency you are never ever allowed to ignore that something is concurrent. You have no choice but to write code which is aware of all scheduling and cancellation points which it is subject to.

Maybe that's fine. Maybe...

everyone should be forced to be aware when they are doing an operation during which anything could asynchronously change,

all code which does too much should be forced to do an asynchronous yield to the scheduler every once in a while,

because these two requirements together would pressure code to cleanly split its pure logic from it impure logic, and to split its pure logic into small chunks of work which the caller can call individually.

This feels onerous to me, but I also suspect that for most problems, the best solution probably naturally meets these requirements. Possibly for all problems. At least for a sufficiently thorough definition of "best", which includes things like "made up of piece of code which are small, composable, reusable, and easy to test, easy to validate and audit, easy to understand in isolation, easy to combine, and easy to change" and "robust against all sorts of real-world problems, including edge cases".

But,

notably my definition of "best" does not include practical things like "could be created or maybe even fully appreciated or maybe even used correctly by a typical fungible software developer, or maybe even by any minds who can actually reliably get things done instead of getting stuck for entire days thinking about the design of everything", and