A couple of my Habr articles [one, two] on low-level programming for 8086 didn't cause much of a stir, but a poll at the end of the second part showed that only 5% of the victims readers wanted to discourage the author from tapping their fingers on the keyboard.
Feeling a sense of sincere gratitude to the remaining 95% of readers, the author decided to produce another, completely original, and extremely useful for educational purposes "low-level" article.
Today, we're in for a mind-blowing mix of 64/32-bit x86 assembly and good old C++.
Disclaimer
Everything below is the author's creation and comes with no guarantees. Use it at your own discretion, accepting the risks of any possible consequences. The author's goal is to provide an educational example, a template, or, if lucky, to explain the essence of the phenomenon.
Preface
I'll assume the reader is familiar with the concept of a "thread" (thread) in the context of software. In short, a thread, according to Wikipedia, is the smallest unit of execution that can be scheduled by the kernel. That is, the OS kernel manages the starting, stopping, termination, and other states of threads. And we, as programmers, command the kernel what to do with the thread. Of course, I mean a normal situation where the OS can do this at all.
So, a fiber (fiber) is an even smaller unit than a thread, one that the OS kernel doesn't even see. At all. Fibers are a way to implement cooperative execution. You can think of a fiber as a thread that decides for itself when to yield the processor to other fibers and calls a special API for this purpose. Moreover, many fibers can run within a single thread. Not simultaneously, but with the right programming skills, they can create the illusion of parallel execution just as well as multiple threads on a single processor core.
Modern C++ has coroutines. Their functionality largely overlaps with fibers, but a full-fledged implementation of coroutines requires compiler support. Fibers, on the other hand, are implemented without it.
The Win32 API provides functionality for working with fibers, and Boost::Fiber does too. But, as usual, we're going our own way and doing everything ourselves in order to:
Understand for ourselves and show others what's "under the hood"
Stop being afraid of assembly and
loveget along with itBecause we can
Our assembly will be as bare-bones as it gets: without any of that prologue, epilogue, invoke, stackframe. Only hardcore, only mov rbp, rsp and as direct as I am, call - just the way we like it.
The example was made with the free Microsoft Visual Studio 2022 Community, and tested on 2019. The example project itself can be downloaded from the author's GitHub repository. You can configure Visual Studio for Assembler+C++ projects using this recommendation, and there's also a video on this topic from Dr. Nina Javaher.
What a fiber-based program in C/C++ looks like
Almost normal:
void __stdcall fiber1(void* data) { for (auto i = 5; i >= 0; --i) { std::cout << "+Fiber1:" << ::GetCurrentThreadId() << " " << i << std::endl; } } void __stdcall fiber2(void* data) { for (auto i = 0; i < 10; i++) { std::cout << "-Fiber2:" << ::GetCurrentThreadId() << " " << i << std::endl; } } int main() { // register our fibers FiberManager::addFiber(fiber1, nullptr); FiberManager::addFiber(fiber2, nullptr); // run FiberManager::start(); // done std::cout << "***Exit***" << std::endl; return 0; }
Two ordinary functions with loops in them. The first one goes from 5 down to 0 inclusive, the second from 0 up to 9 inclusive. Well, let's see...
Let's run it:
Found something to surprise us with! Author, what have you been eating?! It's obvious that first fiber1 runs, then fiber2. Dislike the article and a poop emoji to your karma!
Sorry, dear reader, I forgot something, one small step...
void __stdcall fiber1(void* data) { for (auto i = 5; i >= 0; --i) { std::cout << "+Fiber1:" << ::GetCurrentThreadId() << " " << i << std::endl; yield(); // one small step for man... } } void __stdcall fiber2(void* data) { for (auto i = 0; i < 10; i++) { std::cout << "-Fiber2:" << ::GetCurrentThreadId() << " " << i << std::endl; yield(); // ...one giant leap for mankind } } int main() { // register our fibers FiberManager::addFiber(fiber1, nullptr); FiberManager::addFiber(fiber2, nullptr); // run FiberManager::start(); // done std::cout << "***Exit***" << std::endl; return 0; }
I added a couple of calls to yield():
Let's take a closer look. Now the text output from the two functions is interleaved.
-Wait... these are just regular threads! Author, that's it, I'm unsubscribing!
-But they're not threads. It's not for nothing that I'm printing the result of the Win32 API function call GetCurrentThreadId(). The Thread ID of the current thread shows that it doesn't change...
Fiber cooperation
Cooperation in fibers is a mechanism for voluntarily transferring execution from one fiber to another by directly or indirectly calling a special function. Our special function, as you've already noticed, is called yield(). The entire fiber mechanism operates in user space and, unlike threads, does not require switching any system contexts.
The positive aspects of fibers include not only the absence of switching between user space and kernel space, but also the ability for the programmer to choose the points at which to "yield" control. This helps mitigate such an unpleasant issue as a race condition. However, a race condition can still be achieved if you start modifying a composite object before calling yield() and then continue the modifications after such a call. Inside yield(), control will be passed to another fiber, which will see the partially modified object and can make its own changes to it. To solve this problem, you can prepare an analog of a critical section for cooperative mode.
The negative aspects include the extreme undesirability of using blocking calls. For example, the standard Win32 Sleep(milliseconds) will "hang" the entire cooperative system for the specified number of milliseconds. Therefore, all such things should be replaced with non-blocking analogs. For example, a version mySleep using the Win32 GetTickCount64():
void mySleep(uint32_t milliseconds) { // Retrieve the number of milliseconds that have elapsed since the system was started. // See https://learn.microsoft.com/en-us/windows/win32/api/sysinfoapi/nf-sysinfoapi-gettickcount64 ULONGLONG t = GetTickCount64(); while (GetTickCount64() < t + milliseconds) { yield(); } }
We see that the function mySleep(uint32_t milliseconds) blocks only the fiber that called it; the other fibers will continue to run, because the "paused" fiber calls yield() in a loop, yielding the processor to its neighbors. Here's an example:
void __stdcall fiber1(void* data) { for (auto i = 5; i >= 0; --i) { std::cout << "+Fiber1:" << ::GetCurrentThreadId() << " " << i << std::endl; mySleep(300); } } void __stdcall fiber2(void* data) { for (auto i = 0; i < 10; i++) { std::cout << "-Fiber2:" << ::GetCurrentThreadId() << " " << i << std::endl; mySleep(100); } }
Since mySleep() already calls yield(), there's no need to do it again, unless we explicitly want to yield control to another fiber at some point. Here's what we get in the console:
+Fiber1:10140 5 -Fiber2:10140 0 -Fiber2:10140 1 -Fiber2:10140 2 +Fiber1:10140 4 -Fiber2:10140 3 -Fiber2:10140 4 -Fiber2:10140 5 +Fiber1:10140 3 -Fiber2:10140 6 +Fiber1:10140 2 -Fiber2:10140 7 -Fiber2:10140 8 -Fiber2:10140 9 +Fiber1:10140 1 +Fiber1:10140 0 ***Exit***
Of course, data input, for example, from the keyboard, can also be implemented in a way suitable for use in fibers:
std::string myReadString() { std::string result; for (;;) { if (_kbhit()) { char c = static_cast<char>(_getch_nolock()); if (c == '\r') { break; } _putch_nolock(c); result += c; } yield(); } return result; }
Here, _getch_nolock() and _putch nolock() are library functions defined in conio.h.
The very need to decide where to yield control to other threads can also be considered a negative point. But it shouldn't be considered particularly serious: in I/O tasks, for example, when working with a network, the call to yield() can be completely hidden in wrappers around non-blocking poll()/select() and then work with the network from fibers through these wrapper functions as if the I/O were blocking.
Inside me... ahem... a neon light
Long story short...
- Long story short, this printing contraption, unfortunately, contains nothing new. It only contains very old things...
- Inside! - the old man rustled. - Look inside, where its analyzer and thinker are...
- Analyzer... - I said. - There's no analyzer here. A standard rectifier - yes, also an old one. An ordinary neon bulb. A toggle switch. A good toggle switch, new. Riiight... There's also a cord. A very good cord, brand new... Well, I guess that's all.
-- Arkady Strugatsky, Boris Strugatsky.
"Tale of the Troika"
We've loved pictures since childhood. Here is a sequence diagram (Fig. 3):
For readers familiar with my previous publication, this diagram is very reminiscent of a thread switcher based on timer interrupts. The main difference here is that we don't use interrupts; instead, the fiber calls yield() on its own initiative.
A call to yield() transfers control to the Fiber manager, which selects the next fiber in order from the list of registered fibers, switches the stack pointer register esp/rsp to the selected fiber's stack, and returns with the RET instruction to that fiber, popping the return address from the stack.
In this other fiber, it looks as if the yield() it previously called has just unblocked and returned control. Meanwhile, the first fiber remains blocked in its call to yield() until the second one decides to call this function again.
We've discussed the state when everything is already running. The situation of entering a fiber is a special case. For this, when registering a fiber function, the Fiber Manager creates a separate stack for it and places, among other things, the address of the fiber termination handler
onFiberFinished()and the entry address of the fiber function onto this stack. The very first call toyield()is made from the Main code - the main program code. This causes control to be transferred from the main code to the Fiber manager, which selects the very first fiber from the prepared list, writes the address of the selected fiber's stack top toesp/rspand executes theRETinstruction. As a result, a jump to the fiber's code occurs - it starts. From then on, everything proceeds as described above: a subsequent call toyield()from the fiber function, entering the Fiber Manager, selecting the next fiber from the list, and so on.
The fibers in Fig. 3 are shown in green and pink (okay, let's say pink, not magenta). The discontinuity of the control fragments means that the fiber executes intermittently, in fragments on a dotted lifeline. This differs from the situation of a simple call to some local function and waiting for its return, because there is a switch of the fiber's local context, which is stored on its own stack. At this moment, the logical continuity of the fiber function temporarily disappears. The Fiber manager, in principle, can choose not to return control to a suspended fiber, while continuing to manage other fibers.
When a fiber function completes its work through a standard C-style
return, it actually executes the familiarRETinstruction. This pops the address of the termination handler - the functiononFiberFinished()belonging to the Fiber manager - from the fiber's stack. This handler removes the fiber from the list of fibers managed by the manager. If the list becomes empty, the manager switches theesp/rspregister to the main code's stack (Main code in Fig. 3) and, by popping the saved registers and return address, returns control to it.
The Guts
Fiber Registration
A rather trivial thing. The function addFiber creates a new fiber descriptor FiberDescriptor based on the passed pointer to the fiber function fiber and an optional block of private data data. The created descriptor is placed in the list of fibers _fibers:
namespace FiberManager { typedef std::unique_ptr<FiberDescriptor> FiberDescritporPtr; typedef std::list<FiberDescritporPtr> Descriptors; Descriptors _fibers; FiberDescritporPtr _finishedFiber; Descriptors::iterator _itFiber; // points to a current fiber void addFiber(void(__stdcall* fiber)(void*), void* data) { _fibers.emplace_back(std::make_unique<FiberDescriptor>(fiber, data)); } . . . .
Fiber Descriptor
The state of a fiber is saved in the fiber descriptor FiberDescriptor:
#ifdef _M_X64 typedef uint64_t MemAddr; #else typedef uint32_t MemAddr; #endif class FiberDescriptor { public: static constexpr size_t nStackEntries = 16384; FiberDescriptor(const FiberDescriptor&) = delete; FiberDescriptor& operator=(const FiberDescriptor&) = delete; FiberDescriptor(void(__stdcall* fiber)(void*), void* data); bool isOwnerOfStack(const MemAddr* sp) { return (sp >= &_stack[0]) && (sp < &_stack[0] + nStackEntries); } void saveStackPointer(MemAddr* sp) { _stackPointer = sp; } MemAddr* getStackPointer() const { return _stackPointer; } private: MemAddr _stack[nStackEntries]; MemAddr* _stackPointer; };
Data fields:
in the array
_stacklives the fiber's own stack with a size of 16384 addresses, each address being 4 bytes wide for 32-bit mode or 8 bytes for 64-bit mode. The stack is needed for local variables of called functions, passing parameters, storing the call history itself (call) and ensuring returns (ret) from them. Everything here is exactly the same as with threads, which also have their own stack. The array size was chosen empirically.in the field
_stackPointerthe value of the stack top pointer registeresp/rspis saved for the time while control is transferred to another fiber.
Methods:
The constructor
FiberDescriptor(void(__stdcall* fiber)(void*), void* data)receives the address of the fiber functionfiberand a pointer to a data block, which can benullptr, if no starting data is needed for the function.bool isOwnerOfStack(const MemAddr* sp)checks the stack top pointer, passed in the parametersp, for belonging to the fiber's stack. The method is needed to detect whetheryield()was called from the Main code and to save the main code's stack pointer in the global variable_mainSpfor a subsequent correct return fromyield()back to the main code after all fibers have completed.
Let's pay attention to the fiber descriptor's constructor:
#include "FiberDescriptor.h" extern "C" MemAddr* lowLevelEnqueueFiber(void(__stdcall*)(void*), void*, MemAddr*); // defined in .asm FiberDescriptor::FiberDescriptor(void(__stdcall* fiber)(void*), void* data) { // fill the stack with pre-defined pattern for (auto& elem : _stack) { #ifdef _M_X64 elem = 0xdeadbeeff00da011ULL; // DeadBeefFoodA0ll for debug #else elem = 0xdeadbeefU; // DeadBeef for debug #endif } _stackPointer = lowLevelEnqueueFiber(fiber, data, &_stack[0] + nStackEntries); }
We fill the stack array with a specified numerical pattern. This helps to understand how much stack space was actually used, including calls to Win32 API system functions. Part of the pattern is overwritten by calls, and one can analyze what stack depth is needed for the fiber to work.
the function
MemAddr* lowLevelEnqueueFiber(void(__stdcall*)(void*), void*, MemAddr*)is implemented in assembly. It initializes the new fiber's stack. We will now look at this function in more detail.
The author knew you were dreaming of modern assembly and brutal, 64-bit wide, general-purpose registers. There will be 64-bit, but we'll start with 32-bit. Here is the x86-32 version of lowLevelEnqueueFiber:
;---------------------------------------------------------------------------- ; Should be used from MAIN context to add a new fiber to fiber dispatcher. ; returns new stack pointer in eax ; extern "C" MemAddr* lowLevelEnqueueFiber(void(__stdcall*)(void*), void*, MemAddr*); lowLevelEnqueueFiber PROC ;pFunc:PTR, pData:PTR, pStack:PTR push ebp mov ebp, esp mov esp, [ebp + 10h] ; pStack - prepare the top of stack for a new fiber push [ebp + 0Ch] ; pData - points to void* parameter will passed to the fiber via stack push onFiberFinished ; the handler which is called at the fiber completion stage push [ebp + 08h] ; pFunc = pointer to a fiber function ; allocate stack space to popping edi, esi, ebx, ebp in lowLevelResume() push 0 push 0 push 0 push 0 mov eax, esp ; the result is the address of the new fiber's stack pointer in eax. mov esp, ebp ; restore esp pop ebp ; restore ebp ret lowLevelEnqueueFiber ENDP
As promised, no special macro tricks from MASM. Here, even the enter/leave instructions are not used for the sake of a clearer example.
Briefly about enter/leave
ENTER op1,op2
The ENTER instruction creates a stack frame required by most high-level languages. The first operand specifies the number of bytes of memory to be allocated on the stack upon entering the procedure. The second operand specifies the nesting level of the procedure in the high-level language source code. It determines the number of stack frame pointers to be copied into the new stack frame from the previous one. If the current bitness is 16 bits, the processor uses the BP register as the frame pointer and the SP register as the stack pointer. If the bitness is 32 bits, the processor uses the EBP and ESP registers, respectively, and in the 64-bit case, RBP and RSP. Source: https://sysprog.ru/post/komandy-enter-leave
In plain language, ENTER X, 0 can be written like this:
push ebp mov ebp, esp sub esp, X
For the particularly curious, here they explain the second parameter of ENTER.
LEAVE
The LEAVE instruction has the opposite effect of the ENTER instruction. In fact, the LEAVE instruction only copies the contents of EBP to ESP, thereby discarding the entire stack frame created by the ENTER instruction, and reads the value of the EBP register for the previous procedure. Source: https://sysprog.ru/post/komandy-enter-leave
In a language we're used to, LEAVE can be implemented like this:
mov esp, ebp pop ebp
At the moment of calling lowLevelEnqueueFiber, on the stack, according to the ABI for 32-bit __cdecl, are the parameters pFunc (aka fiber), pData, pStack in increasing order of offset from the address in esp. At the moment of entry into lowLevelEnqueueFiber, the esp register points to the stack element with the return address to the calling code. We consider this to be offset 0. At offset 4 is the pointer to the fiber pFunc, at offset 8 is the pData pointer, and at offset 12dec is the pointer pStack.
But in the code, you see something different: to address data on the stack, we use ebp, into which we placed a copy of esp, but for some reason, all offsets are increased by 4. What's the reason? The reason is that we first pushed the original value from ebp onto the stack, then did mov ebp, esp and then started working with the parameters. And pushing onto the stack always decrements esp by 4.
Why did we put the ebp register on the stack? So that the calling side wouldn't have problems accessing local variables after returning from lowLevelEnqueueFiber.
A few words about local variables
The typical place for local variables in a function is the stack. And they are accessed via the ebp/rbp:
You can find more about local variables here.
We must either restore ebp before exiting our function, or not touch it at all. In our case, ebp is used to access the function's parameters and to store a copy of the esp register, which we lowLevelEnqueueFiber change later in the code:
mov esp, [ebp + 10h] ; pStack - prepare the top of stack for a new fiber
and at the end of the function, we restore it back from ebp to return normally to the code that called lowLevelEnqueueFiber.
So, for what purpose do we change esp? Our goal is purely practical and noble! We put a pointer to the newly created empty fiber stack into the esp register.
Let's go back to what the call to lowLevelEnqueueFiber from C++ looks like:
_stackPointer = lowLevelEnqueueFiber(fiber, data, &_stack[0] + nStackEntries);
We see the third argument &_stack[0] + nStackEntries. This is the pointer to the top of the new stack.
The stack grows downwards...
...from larger addresses to smaller ones. When a value is placed on the stack, first a decrement of esp by 4 (in the 64-bit case, rsp is decremented by 8) occurs, and then the value to be saved is written to the resulting address. So, everything is correct here.*
*) It's more correct to say not "by 4" or "by 8", but "by the size of the object being placed on the stack". However, most often, general-purpose registers are placed there, and their size is exactly 4 and 8 bytes for 32- and 64-bit modes, respectively.
Onto this very stack, we sequentially push the address of the fiber termination handler onFiberFinished, the address of the fiber function itself, passed as the first argument when calling lowLevelEnqueueFiber, and now located at the address ebp + 08h, and another 4 zeros. Here's that piece:
push onFiberFinished ; the handler which is called at the fiber completion stage push [ebp + 08h] ; pFunc = pointer to a fiber function ; allocate stack space to popping edi, esi, ebx, ebp in lowLevelResume() push 0 push 0 push 0 push 0
As a result, we get a stack prepared for launching the fiber. We will soon fully reveal the meaning of all these manipulations.
For now, let's return for a second to the code of lowLevelEnqueueFiber and notice that the new value of esp, after all the necessary addresses and zeros have been placed on the stack, is copied to eax:
mov eax, esp ; the result is the address of the new fiber's stack pointer in
In the C/C++ cdecl convention, functions return their result through the
eax/raxregister.
So, we return the new top of the fiber's stack to the calling code, not forgetting to restore esp and pop the original value of ebp before leaving, so that no one gets offended nothing crashes:
mov eax, esp ; the result is the address of the new fiber's stack pointer in eax. mov esp, ebp ; restore esp pop ebp ; restore ebp ret
Phew... I think I forgot something... oh yes, the four zeros on the stack! The thing is, starting a fiber function and its suspend-resume operations are performed in exactly the same way: by calling yield(). Inside a fiber, this call is no different from any other call, and therefore must follow certain restrictions imposed by conventions we didn't create.
Among them is the requirement that the values of so-called non-volatile registers remain unchanged after returning from a function. In other words, the called function must either save and restore such registers, or not use them. The second option is definitely not suitable for us, because we don't know which registers a particular fiber will want to use, and yield() is precisely what transfers control between fibers.
Here is a list of non-volatile registers for 32-bit mode:
EBX,EBP,ESP,EDI,ESI,CS,DS.
Given that the program uses the standard Flat memory model for Windows (and not only), in which all segments are combined and coincide with each other, we can rely on the fact that CS and DS will not be changed by anyone, and we don't touch them ourselves. The ESP register is under our close control and we strictly watch over its safety, but EBX, ESI, EDI, EBP we are obliged to restore to their original state upon exiting yield(). And this must be done independently for different fibers; each fiber forms its own states and register values. It's most convenient to save registers on the stack with PUSH instructions, and retrieve them from the stack with POP instructions. In order for the fiber's stack to be correctly formed with space for these four registers, we placed four zero values in it, since the specific register values are not important at the start of the fiber.
Start!
Let's take a closer look at the code of the void start() function in the Fiber manager:
// Pointer to MAIN stack static MemAddr* _mainSp; namespace FiberManager { typedef std::unique_ptr<FiberDescriptor> FiberDescritporPtr; typedef std::list<FiberDescritporPtr> Descriptors; Descriptors _fibers; FiberDescritporPtr _finishedFiber; Descriptors::iterator _itFiber; // points to a current fiber void addFiber(void(__stdcall* fiber)(void*), void* data) { _fibers.emplace_back(std::make_unique<FiberDescriptor>(fiber, data)); } void start() { _mainSp = nullptr; _itFiber = _fibers.begin(); // Select the first fiber // Run the first fiber from MAIN stack context. // The stack will be switched to a local fiber-related stack. yield(); // it returns back to start() when all the fibers will finish. _finishedFiber.reset(); } }
The most important line there is the call to yield(). This call will start the fiber mechanics and will only return control to the main code after all fiber functions have completed their work.
The implementation of the 32-bit version of yield() is very simple:
; void yield() is used to switch the fiber. Should be called from running fiber. ; It is also used to run the initial fiber from main context yield PROC pushall ; save non-volatile registers push esp ; pass a stack pointer to fiberManagerYield as argument ; fiberManagerYield(sp) switches the execution to another fiber call fiberManagerYield add esp, 4 ; release one stacked parameter passed to fiberManagerYield popall ; restore non-volatile registers ret yield ENDP
The pushall and popall macro-instructions save/retrieve non-volatile registers to/from the stack
32-bit version:
;---------------------------------------------------------------------------- ; See https://www.agner.org/optimize/calling_conventions.pdf and ; https://learn.microsoft.com/en-us/cpp/cpp/cdecl?view=msvc-160 ; Non-vloatile registers are EBX, EBP, ESP, EDI, ESI, CS and DS pushall macro push ebx push esi push edi push ebp endm ;---------------------------------------------------------------------------- ; See https://www.agner.org/optimize/calling_conventions.pdf and ; https://learn.microsoft.com/en-us/cpp/cpp/cdecl?view=msvc-160 ; Non-vloatile registers are EBX, EBP, ESP, EDI, ESI, CS and DS popall macro pop ebp pop edi pop esi pop ebx endm ;----------------------------------------------------------------------------
When called, the yield() function saves the non-volatile registers on the current stack at the time of the call, then passes the current top address via the same stack to the C function void fiberManagerYield(MemAddr*) .
Let's look at what fiberManagerYield does:
// This function is called from ASM code yield(). // @param sp - current stack pointer after all the required CPU // registers have been pushed to stack. void fiberManagerYield(MemAddr* sp) { using namespace FiberManager; if (_fibers.empty()) // No fibers in the list? { // No fibers to switch to, just return back to yield(). return; } // Does the current fiber own the stack pointed by sp? if ((*_itFiber)->isOwnerOfStack(sp)) { // Save current stack pointer to the fiber descriptor (*_itFiber)->saveStackPointer(sp); if (_fibers.size() > 1) { // Select the next fiber. if (++_itFiber == _fibers.end()) // Is the last fiber? { // Go to first. _itFiber = _fibers.begin(); } } } else { // Execution goes here ONCE, when yield() is first called from the // MAIN stack context. We have only one such place in the start() function. assert(_mainSp == nullptr); // Save MAIN stack pointer to use it in the final completion. _mainSp = sp; } // Switch to the selected fiber using its own stack. lowLevelResume((*_itFiber)->getStackPointer()); assert(false); // The execution must never go here! }
It's clear that fiberManagerYield does nothing if the fiber list is empty. The check
if ((*_itFiber)->isOwnerOfStack(sp)) ...
is needed to find out if fiberManagerYield and, consequently, yield(), was called from a fiber (result true) or from the main code (result false). For this, the method
bool FiberDescriptor::isOwnerOfStack(const MemAddr* sp)
compares the pointer to the top of the current stack passed to it with the range of addresses occupied by the array FiberDescriptor::_stack allocated for the fiber's stack.
If the current stack corresponds to the current fiber's stack, we select the next fiber in order for switching (returning control). If the current stack is different, it means that yield() was called from the main code during the start of the Fiber manager. In this case, the pointer to the top of the current, and in this situation, the main, stack is saved in _mainSp to be used for a correct return of control to the main code upon completion of all fibers. The return will be made precisely to where yield() was called.
The next interesting point is the call to lowLevelResume
lowLevelResume((*_itFiber)->getStackPointer());
with a pointer to the top of the selected fiber's stack. The source for the 32-bit version of lowLevelResume is:
;---------------------------------------------------------------------------- ; Get a new stack pointer from passed argument and switch the stack ; to return into a different fiber ; extern "C" void lowLevelResume(MemAddr*); lowLevelResume PROC ; pSP:PTR ; update esp with a new address taken from pSP parameter passed via stack mov esp, [esp + 4] ; pSP ; extract previously saved non-volatile registers using the passed stack pointer popall ret lowLevelResume ENDP
No frills here: we assign the new pointer value, passed via the same stack when calling esp, to the lowLevelResume register. Then we pop the non-volatile registers from the new stack, and then ret pops the return address from there as well. And control is transferred (it's more correct to say "returned", since this happens with the ret instruction) to another fiber according to the new stack.
Do you still remember those suspicious
push 0 push 0 push 0 push 0
in lowLevelEnqueueFiber? Well, during the first launch of a fiber, which is also executed by the chain of callsyield() --> fiberManagerYield() --> lowLevelResume(),
, there must be something on its stack that popall at the end of lowLevelResume will pop as values for the four registers ebp, edi, esi, ebx, and that the ret instruction will use to transfer execution.
This is why those zeros were initially placed on the stack after the starting address of the fiber function itself. The mystery is solved!
-Author, wait! - an attentive reader will say, -You just mentioned four zeros for the initial values of non-volatile registers, plus one more address for the jump to the beginning of the fiber function, but... your code pushes a whole six values onto the stack!
When it's time to stop
At the end of the previous chapter, the author was exposed by a meticulous reader who remembered a piece of code from the lowLevelEnqueueFiber function, used in the process of creating a new fiber descriptor to form the initial content of its own fiber stack:
. . . . . push onFiberFinished ; the handler which is called at the fiber completion stage push [ebp + 08h] ; pFunc = pointer to a fiber function ; allocate stack space to popping edi, esi, ebx, ebp in lowLevelResume() push 0 push 0 push 0 push 0 . . . . .
Yes, reader, you are right. Right about everything. It's time to turn on our imagination to the fullest and think about what will happen when a fiber function decides to quietly, in a C-like manner, finish its work via return, or even without it, since a void function has nothing to return but control.
The C/C++ compiler didn't come up with anything better for exiting a function than the RET instruction. And this means that our code has reached the last element of its own stack - the address of the fiber termination handler, named onFiberFinished.
I'm sure you know, but still...
...a C/C++ function name is translated by the compiler into its address. For this reason, we can use a function name as an entry point or as an argument where a function pointer is expected. This rule also works for assembly.
The function onFiberFinished() will be automatically called immediately after exiting the fiber, as it is the address of onFiberFinished that falls into the hands of that very RET instruction.
Let's take a closer look at this creation of a twilight genius:
// This function is called from ASM code as a fiber completion. // It should ALWAYS call lowLevelResume() void onFiberFinished() { using namespace FiberManager; // Currently, completing fiber is ALWAYS the owner of the current stack. But we mus assert((*_itFiber)->isOwnerOfStack(lowLevelGetCurrentStack())); // Avoid of auto-destruction the FiberDescriptor by saving it to // finishedTask shared pointer. We need this stack to be allocated // because it is current stack we are working with right now. _finishedFiber.reset(_itFiber->release()); // Remove completed fiber from the list. _itFiber = _fibers.erase(_itFiber); MemAddr* sp; if (_fibers.empty()) { // Prepare the final completion, we will return the control // from yield() to start() function. See yield() call in start(). sp = _mainSp; } else { // Switch to the next fiber. if (_itFiber == _fibers.end()) { _itFiber = _fibers.begin(); } sp = (*_itFiber)->getStackPointer(); } lowLevelResume(sp); // it doesn't return control! assert(false); }
We immediately verify that the call to onFiberFinished() occurred using the stack of the fiber that last received control:
assert((*_itFiber)->isOwnerOfStack(lowLevelGetCurrentStack()));
If the Fiber manager's algorithm is not broken, this is ensured automatically. Next, we remove the completed fiber from the list _fibers and, if the list becomes empty after this, we select the main code's stack to return control to:
sp = _mainSp;
If other incomplete fibers exist, we select the next descriptor in order and get the fiber's stack:
sp = (*_itFiber)->getStackPointer();
And we yield control to the code at the address stored on the selected stack:
lowLevelResume(sp); // it doesn't return control!
And that's the entire implementation of fiber switching.
The Mysterious World of 64-bit Code
The C/C++ code is common for both platforms, but the tastiest part - the assembly - differs significantly. Let's focus on this difference. Gourmets have prepared their forks, sharpened their knives, moved their like-throwers closer, and aimed them at the author's text.
64 bits is not just 2 times 32. It's much worsebetter. The general-purpose registers became 64-bit, and, in addition to the ones we're used to, 8 new 64-bit registers were added: R8-R15 ,
The differences also concern function calling conventions (ABI). All those cdecl and stdcall turn into one elegant fastcall variant:
The first 4 parameters, if they are pointers or integers, are passed through the registers
RCX,RDX,R8, andR9, and if we have floating-point numbers, then through the registersXMM0L,XMM1L,XMM2L, andXMM3L.Details at this link.
Registers that must be restored upon exiting a function (non-volatile registers):
RBX,RBP,RDI,RSI,RSP,R12,R13,R14,R15, andXMM6-XMM15Details at this link.
In this regard, the code for the pushall/popall macro-instructions has undergone significant changes
The 64-bit version does not include the rbp register; we work with it in a special way in the 64-bit version of the code:
;---------------------------------------------------------------------------- pushmmx macro mmxreg sub rsp, 16 movdqu [rsp], mmxreg endm ;---------------------------------------------------------------------------- popmmx macro mmxreg movdqu mmxreg, [rsp] add rsp, 16 endm ;---------------------------------------------------------------------------- ; See https://learn.microsoft.com/en-us/cpp/build/x64-calling-convention?view=msvc-170#callercallee-saved-registers pushall macro push rbx push rsi push rdi push r12 push r13 push r14 push r15 pushmmx xmm6 pushmmx xmm7 pushmmx xmm8 pushmmx xmm9 pushmmx xmm10 pushmmx xmm11 pushmmx xmm12 pushmmx xmm13 pushmmx xmm14 pushmmx xmm15 endm ;---------------------------------------------------------------------------- ; See https://learn.microsoft.com/en-us/cpp/build/x64-calling-convention?view=msvc-170#callercallee-saved-registers popall macro popmmx xmm15 popmmx xmm14 popmmx xmm13 popmmx xmm12 popmmx xmm11 popmmx xmm10 popmmx xmm9 popmmx xmm8 popmmx xmm7 popmmx xmm6 pop r15 pop r14 pop r13 pop r12 pop rdi pop rsi pop rbx endm ;----------------------------------------------------------------------------
Before calling a function, the stack must be aligned to an address that is a multiple of 16 bytes.
For this, the author has prepared a small macro-instruction alignstack:
;---------------------------------------------------------------------------- ; Align stack at 16 (see https://docs.microsoft.com/en-us/cpp/build/stack-usage?view=msvc-160 ) alignstack macro and spl, 0f0h endm ;----------------------------------------------------------------------------
What is this SPL and why is this stub needed?
spl is the lower 8-bit (1 byte) part of the stack pointer register rsp. A meticulous reader will ask: why doesn't the author want to use rsp there instead of its stub spl? You can't use rsp, even if you really want to depict something like this:
and rsp, 0fffffffffffffff0h
ml64.exe (this is the MASM macro assembler) will write to us during program translation:
LowLevel_x86-64.asm(124) : error A2084:constant value too large
It's strange, but true: There is no AND instruction for a 64-bit constant. And it's not just AND that has this issue. There is an option for a 32-bit constant* which is automatically sign-extended to 64 bits if the first operand is 64-bit:
*) Constants in CPU instruction diagrams are denoted by the abbreviation imm from the word immediate - direct.
Another feature is the requirement to have at least 32 bytes of reserved space on the stack before a function call, called the Shadow space. The called function can use this space to store a copy of the parameters passed through registers and to implement, for example, a mechanism for handling a variable number of arguments.
Details at this link.
To avoid writing the number 32 everywhere space needs to be allocated on the stack, the constant SHADOWSIZE has been added to the code:
;---------------------------------------------------------------------------- ; Shadow Space (see https://docs.microsoft.com/en-us/cpp/build/stack-usage?view=msvc-160 ) SHADOWSIZE equ 32 ;----------------------------------------------------------------------------
Microsoft has graciously drawn the stack in the brave new world for the situation where function A has called function B:
Let's move on to considering the differences between the 32- and 64-bit versions of the assembly functions
The 64-bit version of lowLevelEnqueueFiber:
;---------------------------------------------------------------------------- ; Should be used from MAIN context to add a new fiber to fiber dispatcher ; rcx - pointer to a fiber function ; rdx - void* data ; r8 - pointer to a function stack ; returns rax - address of a new host's stack pointer ; extern "C" MemAddr* lowLevelEnqueueFiber(void(__stdcall*)(void*), void*, MemAddr*); lowLevelEnqueueFiber PROC push rbp mov rbp, rsp mov rsp, r8 ; prepare the top of stack for a new fiber sub rsp, SHADOWSIZE ; THIS SPACE IN TASK STACK IS REQUIRED BY ABI! alignstack ; onFiberFinished is handler which is called at the fiber completion stage. mov r8, onFiberFinished push r8 push rdx push rcx ; prepare fiber entry proxy function mov r8, fiberEntry push r8 pushall ; allocate stack space to popping non-volatile registers in lowLevelResume() push 0 ; 0 is a value for RBP when it will be popped in lowLevelResume(). mov rax, rsp mov rsp, rbp pop rbp ret lowLevelEnqueueFiber ENDP ;----------------------------------------------------------------------------
The code logic is identical to that in the 32-bit version, but there are also noticeable differences:
Space for the Shadow space is allocated on the fiber's own stack.
This stack is aligned to a 16-byte boundary.
Instead of
push onFiberFinished, a strange combination of instructions is used
; onFiberFinished is handler which is called at the fiber completion stage. mov r8, onFiberFinished push r8
-As if they couldn't have left the old version... - the reader will say. -It's obvious that onFiberFinished is just the address of the entry point to the function of the same name!
Unfortunately, push does not work with 64-bit constants...
...maximum 32 bits, which are sign-extended to 64 bits when written to the stack. For example, the instruction push with the 32-bit operand 80000000hex
push 80000000h
will ultimately place the following bytes into the stack memory (shown from least significant to most significant):
00 00 00 80 ff ff ff ff
This happens because the most significant bit in the 32-bit 80000000hex is 1, which means this number is negative and equal to -2 147 483 648dec. So it gets extended to the exact same negative value with the full power of 64 bits!
Now live with that :-D
Instead of pushing the fiber function's entry address onto the stack, in this case, this parameter comes into
lowLevelEnqueueFiberviarcx, and the address of some strange functionfiberEntryis pushed onto the stack in the familiar way. And before it, therdxandrcxregisters are pushed. Let's note this feature for ourselves and move on for now.Remember, in the 32-bit version, we put four 32-bit zeros on the stack as values for the four non-volatile registers at the start of the fiber? They took up a total of 16 bytes. This time, there are many more registers, and not all of them are the same size. I decided to just call
pushall. Yes, I had to accept that instead of zeros, about 216 bytes of garbage from the actual registers would end up on the stack, but it won't prevent us from starting the thread in any way.A separate instruction
push 0places the value forrbp. This non-volatile register is not included inpushall/popallintentionally. We work with it in a special way.
These are the differences.
Let's return to the strange function mentioned earlier, fiberEntry:
;---------------------------------------------------------------------------- ; Fiber entry code is used to prepare an input parameter in RCX fiberEntry PROC pop rdx ; Target fiber function address pop rcx ; Fiber argument pointer enter SHADOWSIZE, 0 ; it pushes RBP to current stack and sets RBP=RSP and then RSP -= SHADOWSIZE alignstack call rdx ; call fiber entry point leave ; Restore stack (rsp) & frame pointer (rbp) ret fiberEntry ENDP ;----------------------------------------------------------------------------
With our current knowledge, there's no mystery there. fiberEntry rewrites the parameters passed via the stack into the necessary registers according to the ABI and calls the fiber's entry point.
The implementation of yield() practically repeats that for the 32-bit mode, with the differences related to stack alignment requirements:
;---------------------------------------------------------------------------- ; void yield() is used to switch fiber. Should be called from running fiber. ; It is also used to run the initial fiber from main context yield PROC pushall enter 0, 0 ; it pushes RBP to current stack and sets RBP=RSP mov rcx, rsp ; rcx is passed as parameter to fiberManagerYield sub rsp, SHADOWSIZE alignstack ; fiberManagerYield(sp) switches the execution to another fiber call fiberManagerYield leave ; Restore stack (rsp) & frame pointer (rbp) popall ret yield ENDP ;----------------------------------------------------------------------------
In the 64-bit versions, I decided to use enter/leave for variety. How they work was described earlier in this article.
Completely unchanged is lowLevelResume, except that the input parameter is passed via the rcx register instead of the stack:
;---------------------------------------------------------------------------- ; Get a new stack pointer from passed argument (rcx) and switch the stack ; to return into a different fiber ; rcx - target stack pointer ; extern "C" void lowLevelResume(MemAddr*); lowLevelResume PROC mov rsp, rcx ; extract previously saved non-volatile registers pop rbp popall ret lowLevelResume ENDP ;----------------------------------------------------------------------------
I almost forgot! There's one more assembly function I haven't mentioned. It's simple and is needed to get the top of the currently used stack in C code:
64-bit version
;---------------------------------------------------------------------------- ; Get current stack pointer to provide it to C++ code ; extern "C" MemAddr* lowLevelGetCurrentStack(); lowLevelGetCurrentStack PROC mov rax, rsp ret lowLevelGetCurrentStack ENDP ;----------------------------------------------------------------------------
And the same for 32-bit
;---------------------------------------------------------------------------- ; Get current stack pointer to provide it in C++ code ; extern "C" MemAddr* lowLevelGetCurrentStack(); lowLevelGetCurrentStack PROC mov eax, esp ret lowLevelGetCurrentStack ENDP ;----------------------------------------------------------------------------
As you can see, they are absolutely identical and primitive, but they are used in C code and, therefore, are worthy of mention.
Conclusion
I hope the article turned out to be moderately boring and at least a little informative. Many hours and mental effort were spent writing this text and the code example. The author would be very grateful for feedback in the comments, likes, and karma boosts.