4 ms·

> FWIW, the original implementation of Java (when it was known as Oak) used this trick to manage user level threading. There was also a some code to do the stac

> FWIW, the original implementation of Java (when it was known as Oak) used this trick to manage user level threading. There was also a some code to do the stack swap since you were in a virtual machine anyway, that stuff was all there to be adjusted. 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.

throwaway_pdp09 6y ago
I think he was referring to this https://en.wikipedia.org/wiki/Green_threads https://en.wikipedia.org/wiki/Green_threads 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!
- jbverschoor 6y ago
  Yep.. green threads were there, and not every platform had preemptive threading. J2ME only had geen threads iirc.
pansa2 6y ago
> I figured most "interpreted" languages would be trivial to implement any kind of threads, 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. 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 https://github.com/stackless-dev/stackless [1] https://github.com/lua/lua/commit/196c87c9cecfacf978f37de4ec69eba0a5971256 https://github.com/lua/lua/commit/196c87c9cecfacf978f37de4ec...
- anonymoushn 6y ago
  I was curious about these changes to Lua 5.4, so I had a look. When you create a Lua coroutine that allocates 200 Lua stack frames and then yields across them, the first longjmp crosses 200ish C stack frames. When you later resume, all those C stack frames are gone, but there wasn't any important state in them! Lua just calls luaV_execute in a loop[0]. (Trampolining?) So at that point, for that coroutine, the lower 200ish Lua stack frames do not have corresponding C stack frames, but any Lua subroutines you then call will have corresponding C stack frames. [0] https://github.com/lua/lua/blob/9b7987a9d1471ba94764286b28e0998f73deb46a/ldo.c#L569 https://github.com/lua/lua/blob/9b7987a9d1471ba94764286b28e0...
swetland 6y ago
Two observations about "unsafeness" of your threading system: 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.
- namibj 6y ago
  It's a bit difficult to get guard pages working together with 2MB pages, though. And in todays age of swap-less systems, you typically don't want to pollute the TLB with loads of 4k pages.
dfox 6y ago
> 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. 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.

throwaway_pdp09 6y ago

I think he was referring to this https://en.wikipedia.org/wiki/Green_threads https://en.wikipedia.org/wiki/Green_threads 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!

jbverschoor 6y ago
Yep.. green threads were there, and not every platform had preemptive threading. J2ME only had geen threads iirc.

pansa2 6y ago

> I figured most "interpreted" languages would be trivial to implement any kind of threads, 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. 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 https://github.com/stackless-dev/stackless [1] https://github.com/lua/lua/commit/196c87c9cecfacf978f37de4ec69eba0a5971256 https://github.com/lua/lua/commit/196c87c9cecfacf978f37de4ec...

anonymoushn 6y ago
I was curious about these changes to Lua 5.4, so I had a look. When you create a Lua coroutine that allocates 200 Lua stack frames and then yields across them, the first longjmp crosses 200ish C stack frames. When you later resume, all those C stack frames are gone, but there wasn't any important state in them! Lua just calls luaV_execute in a loop[0]. (Trampolining?) So at that point, for that coroutine, the lower 200ish Lua stack frames do not have corresponding C stack frames, but any Lua subroutines you then call will have corresponding C stack frames. [0] https://github.com/lua/lua/blob/9b7987a9d1471ba94764286b28e0998f73deb46a/ldo.c#L569 https://github.com/lua/lua/blob/9b7987a9d1471ba94764286b28e0...

swetland 6y ago

Two observations about "unsafeness" of your threading system: 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.

namibj 6y ago
It's a bit difficult to get guard pages working together with 2MB pages, though. And in todays age of swap-less systems, you typically don't want to pollute the TLB with loads of 4k pages.

dfox 6y ago

> 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. 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.