Implementing simple cooperative threads in C
brennan.io
brennan.io
Random meta note brenns10, the idiom for giving up the processor is 'yield' (rather than 'relinquish') it is common in cooperative systems.
That said, the code in Java that switched threads was called the 'trampoline' code since you bounced in, switched threads and bounced out.
And my last comment is that if you set up your scheduler in a way that it has a 'runnable' and 'sleeping' queue, you can do clever things like have a task sleep on a mutex or other conditional variable and wake up when that variable does what you're waiting for. It makes implementing network services that service multiple clients much cleaner.
I never knew Java did this. I figured most "interpreted" languages (via direct interpreters or bytecode) would be trivial to implement any kind of threads (even pre-emptive), because at any point the interpreter could decide to save the state of one language thread and switch to another, without bothering the interpreter's own stack.
> the idiom for giving up the processor is 'yield' (rather than 'relinquish') it is common in cooperative systems
Makes sense, I had been using relinquish for my other projects but I almost named it yield this time around.
> And my last comment is that if you set up your scheduler in a way that it has a 'runnable' and 'sleeping' queue, you can do clever things like have a task sleep on a mutex or other conditional variable and wake up when that variable does what you're waiting for. It makes implementing network services that service multiple clients much cleaner.
I'm really excited to tweak large parts of this, scheduler included! I'm really interested in allowing my scheduler to use `poll()` to determine readiness of blocked tasks, and yeah unblocking tasks for purposes like coroutines or mutexes or condition variables. This was the absolute minimum scheduler which would form a foundation to write baout, and I was really excited to write about the topic and share about it.
BTW mid-grey text on yellow makes your great article difficult to read. I've had to open it in eww to read it. Worth it though, thanks!
J2ME only had geen threads iirc.
Some language interpreters keep the "virtual" stack and the C stack separate like this, including current versions of Lua. As you suggest, this allows Lua to support coroutines which each have their own virtual stack.
However other interpreters, such as CPython, keep both stacks synchronized. In this case, a call in the interpreted language corresponds to a call in C - recursively back into the main interpreter loop. This is why Python's generators do not have independent stacks.
The awfully-named "Stackless Python" [0] breaks the synchronization between stacks, to allow Python to support stackful coroutines.
At least, the above was my understanding until recently. The upcoming Lua 5.4 changes to using a recursive call [1], like CPython, but still supports stackful coroutines. I don't know how this is implemented.
[0] https://github.com/stackless-dev/stackless
[1] https://github.com/lua/lua/commit/196c87c9cecfacf978f37de4ec...
[0] https://github.com/lua/lua/blob/9b7987a9d1471ba94764286b28e0...
1. As a matter of paranoia I would likely write schedule() entirely in assembly -- it's a simple function and if you write it by hand you can be certain the compiler doesn't "cleverly" optimize something that will cause pain across the context switch.
2. Your 16K stacks are allocated straight out of the heap, which means stack under or overflows are going to stomp all over adjacent allocations (possibly other stacks), and be a pain to debug. You'll likely want to look at using mmap() and friends to allocate stacks with guard pages to catch this. You can also just range-check the SP when context switching (maybe as an optional debug build thing) which may catch things before a lot of damage is done.
And in todays age of swap-less systems, you typically don't want to pollute the TLB with loads of 4k pages.
I'm more or less sure, that original Oak/Java did cooperative threads only on the VM level by simply swaping the interpreter state without any C-level context-switching. But it was still cooperative and threads had to yield or block on something. Also the scheduling was simple round-robin with different static priorities and highest priority thread will always run unless it is blocked.
On the other hand in 90's many large portable software packages had their own userspace greenthread implementations with hand-written assembler context switches because many OSes did not have threads and these that had had wildly different and incompatible implementations. This was done by both Netscape/Mozilla (eg. NPR) and AFS (where IIRC the threading implementation is somewhat deeply integrated with used RPC mechanism), I would not be surprised if one could find remnants of something similar in LibreOffice codebase.
All Java SE implementations I've ever seen use (preemptive) OS threads, so I assumed it's been this way from the beginning, and this yield() never made much sense to me.
Don't tell the Python programmers...
Back in the old 8-bit days we called it “sleep” since you were telling the scheduler if you needed to come back ASAP (i.e. sleep(0)) or N number of microseconds in the future.
https://www.chiark.greenend.org.uk/~sgtatham/coroutines.html
Submitted here: https://news.ycombinator.com/item?id=23293835
That's decades old, and actually used in PuTTY.
It's also worth noting that you don't need asm to change the stack pointer, if you don't mind being imprecise about its exact value by the size of a function invocation frame or so: you can use alloca() or variable length arrays to do arithmetic on the stack pointer! https://fanf.livejournal.com/105413.html
Then I joined a company in 96 and discovered that their software all ran on a custom in-house developed multitasking O/S (!). I immediately recognized the task switching mechanism and formally learned about coroutines.
Now here we are in 2020 and the youngins are still rediscovering the same thing.
This doesn't mean that the implementation should then be used in practice, there are likely other solutions that are better suited, more mature, etc.
1. You need to decide how much stack space to allocate to a fiber beforehand. If you go over this limit, you will segfault. 2. Thread local storage doesnt exist anymore since you're potentially swapping between different kernel threads (and different fibers are using the same thread and will share storage). 3. Certain types of locks can now fail because the lock isnt transferred to the new thread upon being woken up. Other locks run into rentrancy problems here.
Does anyone know of good solutions to these problems? Is there a library that takes all these things into account?
(1), Golang does something like this by probing on every function call and having movable stacks. Historically they used a linked list of stack pages, but gave that up in 1.4 because the performance was bad. The same does not work in C because C compilers do not expect pointers to the stack to become invalid while a stack frame is live.
A blocking call stalls the whole system. It doesn't in a non-cooperative threading environment. Various languages have "solved" this by not allowing you to use blocking calls and sometimes add syntactic sugar like async/await, but this sucks. The point of having threads is to use them like threads. At least Go gets this right.
That is the right solution. Do you seriously think in Go when you make an apparently blocking system call, an actual blocking system call is made? No, you are calling the runtime provided version that doesn't actually block. Of course in C/C++ that needs more discipline to do.
Who cares? From the perspective of the programmer, it's a blocking call.
And back to the original example, it's totally possible for a production implementation to handhold the user like this by, e.g. supplying a modified libc so that all the blocking system calls are linked against the runtime's implementation. That would basically achieve what you liked in Go.
It's inferior because you have to actually specify it whenever you make such a call, rather than having the runtime or library be smart and figure it out.
> And back to the original example, it's totally possible for a production implementation to handhold the user like this by, e.g. supplying a modified libc so that all the blocking system calls are linked against the runtime's implementation.
I know. I didn't say it was intractable. Just like problems 1-3, they all have potential solutions -- they just involve hard work.
2. You will need to reimplement thread local storage yourself. A production-quality implementation should handle this for you. Thread local storage just means having a special section of memory as a read-only template, and then duplicate them into fresh pages upon the creation of the fiber, mark them as writable, call constructors. And then remember to save the segment registers when switching. Tedious but doable.
3. You need your own locks. This is apparent even in high-level languages like Python. Notice how Python asyncio provides its own mutexes and semaphores? A production quality implementation will handle this for you, but you'll need to use them instead of the OS-provided ones.
[1] http://dunkels.com/adam/pt/ [2] https://en.wikipedia.org/wiki/Protothread
https://probablydance.com/2013/02/20/handmade-coroutines-for...
Although in this particular instance TFA also uses inline assembly to setup the stack, so it's moot.
It's much easier to deal with shared memory with cooperative threads at the expense of higher latency.
Actually implementing it was quite fun and I encourage every enterprising systems engineer to try. My implementation even supports growable stacks (up to a limit of course).
we were running on windows (3.11), macOS, and amiga (for tooling, the games didn't run on the amiga) with great success.
of course, we just used setjmp and longjmp, no assembly for portability (though there ended up being some assembly in one of the games, while macOS had good sound management, windows did not at the time and the audio mixing code ended up written in hand-rolled x86 assembly in order to perform well enough for the games to work on the hardware at the time).
So each task gets 16k of stack space, but what if it runs out of it? These are allocated from the "main" heap, so they won't exactly run into each other, but might trigger UB or crash the program. This is something that a real scheduler (like the one in the OS's kernel) would have to deal with anyway, so how does, say, Linux, solve this? Giving a lot of stack space to each running thread would lead to fragmented and underused memory, or is it not a concern at the stack spaces you'd normally deal with?
That's exactly what happens, and it's not a problem in practice -- each thread gets 8 megabytes of memory allocated. (Note, due to demand paging, physical usage grows in 4kb increments.)
The point isn't to dis this method. It's just to say it was frustrating with tiny stacks.
for g of gameobject
g.update()[1] http://libdill.org/ [2] Call to setjmp: https://github.com/sustrik/libdill/blob/de7a917bc39756f61237... [3] Call to longjmp: https://github.com/sustrik/libdill/blob/de7a917bc39756f61237...
(2007)
I would not recommend taking this approach in C.
EDIT: found a nice example of this here: https://rethinkdb.com/blog/handling-stack-overflow-on-custom...
The post is a good explanation regarding stack handling.
In any case, if I added a small JS powered button to switch into a higher contrast style, would that make the site more usable to you?
I would also like to respectfully challenge your assumption that lower contrast text is less jarring for the eyes for long reading sessions. If it were so, they'd be printing books in light gray color, wouldn't they?
Looking at the Solarized theme, my guess is it's the yellow-ish background that removes the strain on the eyes, as #fff is typically very bright. Since most people aren't focusing on the background when reading, it doesn't cause the eyes to focus more than usual. However, changing the color of the text is a different matter because that's what the eyes are focusing on, and making the text lighter causes it to be harder to read.
That's easy to verify: on the opacity scale of 0.0 to 1.0, where 1.0 is fully opaque, #000 (full black) at 0.1 opacity (almost transparent) is harder to focus on than 0.9 opacity (almost fully opaque). The only reason why some (most?) designers wouldn't be caught dead using #000 at 1.0 opacity for text, despite it being the most readable text color, is because very few things in the real world are at #000 or #fff, so the general advice is to use some shade that's close to it to make the webpage look more natural.
They're essentially trading off readability for aesthetics, and my original comment was that you traded off too much readability for aesthetics, in my opinion.
That said, if I were you, I wouldn't trust my opinion or anyone else's really. Seeing as you made it to HN, you could run an A/B test to see if serving a higher contrast page causes people to spend more time on that page on average, presumably because they're spending more time reading the content, instead of just skimming it like me. That way you'd be making informed changes based on data, not people's subjective experiences (including mine and yours).
Just for fun, I fiddled with the text color on your webpage and I'd say anything lighter than #555 for the body and #666 for the h2 seems too washed out (with the same background color).
Finally, I do want to note that the content is excellent. Happy Memorial Day!
Yes.
> Reasoning about cooperative threads in C is impossible.
Well, sorta. The problem with these approaches is mostly that C runtimes expect you to use the native operating system thread construct, not your own handrolled thing. If you were writing a libc for your own operating system you could use something vaguely like these libraries.
Another obvious problem is the lack of utilization of multiple CPU cores. And once you try and mix the two (M:N threading), the system becomes difficult to understand (and often has worse performance than just 1:1 threading).
I wouldn't say it's because reasoning about them is impossible, but that in practice, they are extremely difficult to use.
> Reasoning about async C code is impossible.
No, that part isn't true.
Ah! Blood pressure rising!
> Like with goto, the common advice is to avoid
Whew. And then goes on to make a really good case for complicated task perform with simple error handling.
It’s a good application for not exactly general use cooperative routines but a specific use case of performing multiple procedural steps.
I think there it falls short and where an RTOS/OS will be more useful is when you have to wait on one of those steps.
I think that’s the harder example with the example of an HTTP request is waiting for the response and keeping that context ready and blocking in a separate thread. That ends up being easy to read and maintainable. But I suppose there is no reason you can’t do both.
Because the pattern that emerges with setjmp/longjmp is pretty similar, and that's the most common use: to simulate what other languages offer with exceptions. The most prominent libraries I can think of that force you to do this are image related, libpng and libjpeg both use longjmp to handle errors [though IIRC it's optional in the latter].
If I’m interviewing someone for a programming job and I see goto in there C code... they better have an amazing reason or they won’t be getting the job. Harsh, but it’s reality of how few people are suited for embedded programming.
function(){
// early returns here.
// stuff
// more stuff
if(oops_err){
goto some_error;
}
// yet more stuff
// normal exit
return 0;
// bad exit
some_error:
// clean up
return oops_err;
}
https://www.kernel.org/doc/html/v4.10/process/coding-style.h...
Goto is the typical way to handle errors without creating a hell mess of "hm, gotta close this file, free that buffer, blah blah" at every step where you might want to bail early. There are a few alternatives but none of them are better than goto and a few can be said to be worse.
Denying potential job to a person on a basis of generic "goto is anathema" mantra is not a good idea until one looks at the code and understands what the "offensive" part is actually doing instead of using some code analyzer/text search blindly.