Пара моих хабровских статей [один, два] по низкоуровневому программированию для 8086 хоть и не вызвала особого ажиотажа, но опрос в конце второй части показал, что только 5% потерпевших почитавших желают отвадить автора от шевеления пальчиками по клавиатуре.

Испытывая чувство искренней признательности к оставшимся 95% читателей, автор решился родить ещё одну, совершенно оригинальную, и крайне полезную в познавательных целях "низкоуровневую" статью.

Сегодня нас ждёт мозговыносящая смесь 64/32-битного x86-ассемблера и старого-доброго C++.

Безответственность

Всё нижеизложенное - творчество автора и ничего не гарантирует. Пользуйтесь на своё усмотрение, принимая на себя риски любых возможных последствий. Цель автора - предоставить учебный пример, заготовку, или, если повезёт, суметь объяснить суть явления.

Предисловие

Предположу, что читатель знаком с понятием "нить" (thread) в контексте программного обеспечения. Вкратце, нить, если верить Вики, - это наименьшая единица, исполнение которой может быть назначено ядром. То есть, запуском, остановкой, завершением и другими состояниями нитей заведует ядро ОС. А мы, как программисты, командуем ядру, что делать с нитью. Конечно, я имею ввиду нормальную ситуацию, когда ОС вообще умеет это делать.

Так вот, волокно (fiber) - это ещё меньшая, чем нить, единица, которую ядро ОС даже не видит. Никак. Волокна - это способ реализации исполнения в кооперативном стиле. Можно представить себе волокно как нить, которая сама решает, когда отдать процессор другим волокнам, и вызывает для этого специальное API. Более того, в рамках одной нити может работать множество волокон. Не одновременно, но при должном умении программиста они будут создавать иллюзию параллельного выполнения не хуже, чем это делают несколько нитей на одном ядре процессора.

В современном C++ есть корутины. Их функционал во многом перекрывает волокна, но полноценная реализация корутин требует поддержки со стороны компилятора. Волокна же реализуются без таковой.

Win32 API предоставляет функционал для работы с волокнами, Boost::Fiber - тоже. Но, как обычно, мы идём своим путём, и делаем всё сами, чтобы:

• Понять самим и показать другим, что там "под капотом"

• Перестать бояться ассемблера и полюбить поладить с ним

• Потому что можем

Ассемблер у нас будет настолько голым, насколько это может быть: без всяких там prologue, epilogue, invoke, stackframe. Только хардкор, только mov rbp, rps и непосредственный, как я сам, call - всё как мы любим.

Пример сделан на бесплатной Microsoft Visual Studio 2022 Community, проверен и на 2019. Сам проект примера можно скачать с GitHub репозитория автора. Настроить Visual Studio для работы с Assembler+C++ проектами можно по этой рекомендации, а также есть кино на эту тему от Dr. Nina Javaher.

Как выглядит волокнистая программа на C/C++

Почти обычно она выглядит:

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;
}

Две обычные функции, циклы в них. В первой от 5 до 0 включительно, во второй от 0 до 9 включительно. Ну посмотрим...

Запускаем:

Нашёл чем удивить! Автор, ты чем там объелся?! Видно же, что сначала отрабатывает fiber1, потом fiber2. Дизлайк статье и какашка в карму!

Извини, дорогой читатель, я забыл кое-что, один маленький шаг...

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;
}

Добавил пару вызовов yield():

Присмотримся повнимательнее. Теперь вывод текста из двух функций чередуется.

-Так... это же обычные нити! Автор, всё, отписка!
-А вот и не нити. Я же не напрасно там вывожу результат вызова функции Win32 API GetCurrentThreadId(). По Thread ID текущей нити видно, что она не меняется...

Кооперация fibers

Кооперация в волокнах - это механизм добровольной передачи выполнения от одного волокна (fiber) к другому при помощи прямого или косвенного вызова специальной функции. Наша специальная функция, как вы уже заметили, называется yield(). Вся механика волокон работает в user space и, в отличие от нитей, не требует переключения каких-либо системных контекстов.

К положительным моментам fibers относится не только отсутствие переключения между user space и kernel space, но и возможность программисту самому выбирать точки "отдачи" управления. Это позволяет смягчить такую неприятность, как состояние гонки (race condition). Впрочем, достичь ситуации гонки всё равно можно, если начать изменять некий составной объект перед вызовом yield() и затем продолжить изменения после такого вызова. Внутри yield() управление будет передано другому волокну, которое увидит частично изменённый объект и сможет внести в него свои собственные изменения. Для решения этой проблемы можно приготовить аналог критической секции для кооперативного режима.

К отрицательным моментам можно отнести крайнюю нежелательность использования блокирующих вызовов. Например, обычный Win32 Sleep(milliseconds) "повесит" всю кооперацию на указанное количество миллисекунд. Поэтому все такие вещи следует заменять на неблокирующие аналоги. Например, вариант mySleep с использованием 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();
	}
}

Видим, что функция mySleep(uint32_t milliseconds) блокирует только то волокно, которое её вызвало, остальные волокна продолжат работать, т.к. "поставленное на паузу" волокно в цикле вызывает yield(), отдавая процессор своим соседям. Вот пример:

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);
	}
}

Поскольку mySleep() уже вызывает yield(), делать это дополнительно не нужно, если мы явно не хотим в каком-то месте передать управление другому волокну. Вот что получается в консоли:

+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***

Конечно, ввод данных, например, с клавиатуры, тоже можно реализовать в подходящем для использования в волокнах виде:

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;
}

Здесь _getch_nolock() и _putch nolock() - библиотечные функции, определённые в conio.h.

Саму необходимость принимать решение о том, где делать отдачу управления другим нитям тоже можно считать отрицательным моментом. Но не стоит считать его особенно серьёзным: в задачах ввода-вывода, например, в работе с сетью, вызов yield() можно полностью спрятать в обертках вокруг неблокирующих poll()/select() и далее работать из волокон с сетью через эти функции-обёртки так, как будто ввод-вывод блокируется.

У мене внутре... гм... неонка

Мы с детства любим картинки. Вот диаграмма последовательности (Рис. 3):

Читателям, знакомых с моей предыдущей публикацией, эта диаграмма очень напоминает переключатель нитей на основе прерываний таймера. Здесь основное отличие в том, что прерывания мы не используем, а вместо этого волокно вызывает yield() по своей собственной инициативе.

Вызов yield() передаёт управление в Fiber manager, который выбирает из списка зарегистрированных волокон следующее по порядку, переключает регистр-указатель стека esp/rsp на стек выбранного волокна, и делает возврат инструкцией RET в это волокно, извлекая адрес возврата из стека.

В этом другом волокне всё выглядит так, будто ранее вызванная им yield() просто разблокировалась и вернула управление. В это время первое волокно остаётся заблокированным в своём вызове yield() до тех пор, пока второе не решит снова вызвать эту функцию.

Мы обсудили состояние, когда всё уже работает. Особняком стоит ситуация входа в волокно. Для этого Fiber Manager при регистрации функции волокна создаёт ему свой отдельный стек и кладёт в этот стек, в числе прочих вещей, адрес обработчика завершения волокна onFiberFinished() и адрес входа в функцию волокна. Самый первый вызов yield() выполняется из Main code - основного кода программы. Это приводит к тому, что управление от основного кода передаётся в Fiber manager, тот выбирает из подготовленного списка волокон самое первое, записывает в esp/rsp адрес вершины стека выбранного волокна и выполняет инструкцию RET. В итоге происходит переход на код волокна - его запуск. Далее всё идёт так, как описано выше: повторный вызов yield() из функции волокна, попадание в Fiber Manager, выбор из списка следующего волокна и так далее.

Волокна на рис. 3 показаны зелёным и розовым (ладно, пусть будет розовый, а не маджента). Прерывистость фрагментов управления означает, что волокно исполняется прерывисто, в виде фрагментов на пунктирной линии жизни. Это отличается от ситуации простого вызова какой-то локальной функции и ожидания возврата из неё тем, что происходит переключение локального контекста волокна, хранящегося в его собственном стеке, и в этот момент логическая неразрывность волоконной функции временно исчезает. Fiber manager, в принципе, может не возвращать управление приостановленному волокну, продолжив при этом управление другими волокнами.

Когда волоконная функция полностью завершает свою работу через обычный сишный return, то по факту выполняется знакомая нам инструкция RET. Происходит извлечение из стека волокна адреса обработчика завершения - функции onFiberFinished() принадлежащей Fiber manager. Этот обработчик удаляет волокно из списка обслуживаемых менеджером волокон. Если список оказывается пуст, менеджер переключает регистр esp/rsp на стек основного кода (Main code на рис. 3) и, извлекая сохранённые регистры и адрес возврата, отдаёт ему управление.

Внутренности

Регистрация волокна

Весьма тривиальная штука. Функция addFiber создаёт новый дескриптор волокна FiberDescriptor на основании переданных указателя на волоконную функцию fiber и опциональный блок приватных данных data. Созданный дескриптор помещается в список волокон _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));
	}
. . . .

Дескриптор волокна

Состояние волокна сохраняется в дескрипторе волокна 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;
};

Поля данных:

• в массиве _stack живёт собственный стек волокна размером 16384 адреса, каждый адрес шириной 4 байта для 32-битного режима или 8 байт для 64-битного. Стек нужен для локальных переменных вызываемых функций, передачи параметров, хранения собственно истории вызовов (call) и обеспечения возвратов (ret) из них. Тут всё точно так же, как у нитей, тоже имеющих свой стек. Размер массива выбран опытным путём.

• в поле _stackPointer сохраняется значение регистра-указателя вершины стека esp/rsp на то время, пока управление передано в другое волокно.

Методы:

• Конструктор FiberDescriptor(void(__stdcall* fiber)(void*), void* data) получает на вход адрес волоконной функции fiber и указатель на блок данных, который может быть nullptr, если никакие стартовые данные функции не нужны.

• bool isOwnerOfStack(const MemAddr* sp) проверяет указатель на вершину стека, переданный в параметре sp, на принадлежность к стеку волокна. Метод нужен для обнаружения факта вызова yield() из Main code и сохранения указателя стека главного кода в глобальной переменной _mainSp для последующего корректного возврата из yield() обратно в главный код после завершения всех волокон.

Уделим внимание конструктору дескриптора волокна:

#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);
}

• Заполняем массив под стек заданным числовым паттерном. Это помогает понять, сколько пространства стека реально использовалось, включая вызовы системных функций Win32 API. Часть паттернов затирается вызовами и можно проанализировать, какая глубина стека нужна для работы волокна.

• функция MemAddr* lowLevelEnqueueFiber(void(__stdcall*)(void*), void*, MemAddr*) реализована на ассемблере. Она инициализирует стек нового волокна. Сейчас мы рассмотрим эту функцию подробнее.

Автор знал, что вы мечтали о современном ассемблере и брутальных, в 64 бита шириной, регистрах общего назначения. Будет и 64 бита, но начнём мы с 32 бит. Перед вами x86-32 вариант 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

Как и обещал, никаких особенных макро штучек от MASM. Тут даже инструкции enter/leave не используются для пущей наглядности примера.

push   ebp
mov    ebp, esp
sub    esp, X

mov    esp, ebp
pop    ebp

В момент вызова lowLevelEnqueueFiber, в стеке, согласно ABI для 32-битного __cdecl находятся параметры pFunc (он же fiber), pData, pStack в порядке возрастания смещения от адреса в esp. В момент входа в lowLevelEnqueueFiber регистр esp указывает на элемент стека с адресом возврата к вызывающему коду. Это мы считаем смещением 0. Со смещения 4 расположен указатель на волокно pFunc, со смещения 8 находится указатель pData, и со смещения 12dec расположен указатель pStack.

Но в коде вы видите кое-что иное: для адресации данных в стеке мы используем ebp, в который поместили копию esp, но все смещения почему-то увеличены на 4. В чём причина? Причина в том, что мы сначала затолкали в стек оригинальное значение из ebp, потом сделали mov ebp, esp и затем начали работать с параметрами. А заталкивание в стек всегда уменьшает esp на 4.

Зачем мы поместили в стек регистр ebp? Затем, чтобы у вызывающей стороны не возникло проблем с доступом к локальным переменным после возврата из lowLevelEnqueueFiber.

Пара слов о локальных переменных

Типичное место размещения локальных переменных в функции - это стек. А доступ к ним осуществляется через регистр ebp/rbp:

Больше о локальных переменных можно найти здесь.

Мы обязаны либо восстановить ebp перед выходом из нашей функции, либо вовсе не трогать его. У нас ebp используется для доступа к параметрам функции и для хранения копии регистра esp, который мы ниже по коду lowLevelEnqueueFiber меняем:

mov     esp, [ebp + 10h] ; pStack - prepare the top of stack for a new fiber

а в конце функции восстанавливаем обратно из ebp чтобы нормально вернуться в тот код, который вызвал lowLevelEnqueueFiber.

Так с какой же целью мы меняем esp? Цель наша сугубо практична и благородна! В регистр esp мы помещаем указатель на свежесозданный пустой стек волокна.

Вернёмся к тому, как выглядит вызов lowLevelEnqueueFiber из C++:

_stackPointer = lowLevelEnqueueFiber(fiber, data, &_stack[0] + nStackEntries);

Видим третий аргумент &_stack[0] + nStackEntries. Вот это и есть указатель на вершину нового стека.

В этот самый стек мы по очереди заталкиваем адрес обработчика завершения волокна onFiberFinished, адрес самой волоконной функции, переданный в виде первого аргумента при вызове lowLevelEnqueueFiber, и теперь находящийся по адресу ebp + 08h и ещё 4 нуля. Вот этот кусок:

    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

В итоге получаем подготовленный к запуску волокна стек. Скоро мы полностью раскроем смысл всех манипуляций.

А пока что на секунду вернёмся к коду lowLevelEnqueueFiber и заметим, что новое значение esp, уже после помещения в стек всех нужных адресов и нулей, копируется в eax:

mov     eax, esp    ; the result is the address of the new fiber's stack pointer in

В C/C++ соглашении cdecl функции возвращают результат через регистр eax/rax.

Итого, мы возвращаем вызывающему коду новую вершину стека волокна, не забывая перед уходом восстановить esp и вытолкнуть оригинальное значение ebp чтобы никто не обиделся ничего не упало:

    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

Уфф... Кажется, я что-то забыл... ах да, четыре нуля в стеке! Дело в том, что старт волоконной функции и её приостановки-продолжения выполняются ровно одним и тем же способом: вызовом yield(). Внутри волокна этот вызов ничем не отличается от любого другого вызова, а поэтому должен следовать некоторым ограничениям, накладываемым принятыми не нами соглашениями.

В числе них есть требование неизменности значений так называемых non-volatile регистров после возврата из функции. Другими словами, вызываемая функция должна либо сохранять и восстанавливать такие регистры, либо не использовать их. Второй вариант нам точно не подходит, ведь мы не знаем, какие регистры захочет использовать то или иное волокно, а yield() именно что передаёт управление между волокнами.

Вот список non-volatile регистров для 32-битного режима: EBX, EBP, ESP, EDI, ESI, CS, DS.

Учитывая, что программа использует стандартную для Windows (и не только) модель памяти Flat, в которой все сегменты объединены и совпадают друг с другом, мы можем полагаться на то, что CS и DS никто изменять не будет, и сами мы их не трогаем. Регистр ESP находится под нашим чутким контролем и мы строго бдим за его безопасностью, а вот EBX, ESI, EDI, EBP мы обязаны восстанавливать в их оригинальном виде на выходе из yield(). И для разных волокон это нужно делать независимо, в каждом волокне образуются собственные состояния и значения регистров. Удобнее всего сохранять регистры в стеке инструкциями PUSH, а извлекать их из стека инструкциями POP. Для того, чтобы стек волокна был правильно сформирован с учетом места для этих четырёх регистров, мы положили в него четыре нулевых значения, т.к. на старте волокна конкретные значения регистров не важны.

Старт!

Посмотрим поближе на код функции void start() в 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();
	}
}

Самая важная строчка там - вызов yield(). Этот вызов запустит механику волокон и вернёт управление в главный код только после завершения работы всех волоконных функций.

Реализация 32-битной версии yield() очень проста:

; 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

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

При вызове функция yield() сохраняет non-volatile регистры в актуальном на момент вызова стеке, затем через стек же передаёт актуальный адрес вершины в C-функцию void fiberManagerYield(MemAddr*) .

Рассмотрим, что делает fiberManagerYield:

// 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!
}

Понятно, что fiberManagerYield ничего не делает, если список волокон пуст. Проверка

if ((*_itFiber)->isOwnerOfStack(sp)) ...

нужна чтобы выяснить, была ли вызвана fiberManagerYield и, закономерно, yield(), из волокна (результат true) или из главного кода (результат false). Для этого метод

bool FiberDescriptor::isOwnerOfStack(const MemAddr* sp)

сравнивает переданный ему указатель на вершину актуального стека с диапазоном адресов, занимаемых выделенным под стек волокна массивом FiberDescriptor::_stack.

Если актуальный стек соответствует стеку текущего волокна, то выбираем для переключения (возврата управления) следующее по порядку волокно. Если актуальный стек какой-то другой, то это означает, что yield() вызвана из главного кода в ходе старта Fiber manager. В таком случае указатель на вершину актуального, а в данной ситуации главного, стека сохраняется в _mainSp для использования в корректном возврате управления в главный код при завершении всех волокон. Возврат будет произведён аккуратно туда, где была вызвана yield().

Следующий интересный момент - вызов lowLevelResume

lowLevelResume((*_itFiber)->getStackPointer());

с указателем на вершину стека выбранного волокна. Исходник 32-битной версии lowLevelResume:

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

Здесь без изысков: присваиваем регистру esp значение нового указателя, переданное через тот же стек при вызове lowLevelResume. А потом выталкиваем из нового стека non-volatile регистры и далее ret выталкивает оттуда же адрес возврата. И управление передаётся (правильнее говорить "возвращается", ведь это происходит при помощи инструкции ret) в другое волокно соответственно новому стеку.

Вы ещё помните те подозрительные

push   0
push   0
push   0
push   0

в lowLevelEnqueueFiber? Так вот, при первом запуске волокна, который также выполняется цепочкой вызовов
yield() --> fiberManagerYield() --> lowLevelResume(),
в его стеке что-то должно быть, что popall в конце lowLevelResume вытолкнет в качестве значений для четырех регистров ebp, edi, esi, ebx, а инструкция ret использует для передачи выполнения.

Вот для этого в стек изначально положили эти нули вслед за адресом начала самой волоконной функции. Тайна раскрыта!

-Автор, постой! - скажет внимательный читатель, -Ты сейчас упомянул о четырёх нулях для начальных значений non-volatile регистров, плюс ещё об одном адресе для перехода в начало функции волокна, но... твой код засовывает в стек целых шесть значений!

Когда пора остановиться

В конце предыдущей главы автор был разоблачён дотошным читателем, который запомнил кусочек кода функции lowLevelEnqueueFiber, используемой в процессе создания дескриптора нового волокна для формирования начального содержимого собственного волоконного стека:

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

Да, читатель, ты прав. Прав во всём. Пора включить воображение на полную и подумать о том, что же будет, когда функция волокна решит тихо-мирно, по-сишному, закончить свою работу через return, а то и вовсе без него, ведь возвращать void-функции нечего, кроме управления.

Компилятор C/C++ не придумал для выхода из функции ничего лучше инструкции RET. А это значит, что наш код добрался до последнего элемента собственного стека - адреса обработчика завершения волокна, с именем onFiberFinished.

Функция onFiberFinished() будет автоматически вызвана сразу после выхода из волокна, так как именно адрес onFiberFinished попадает под горячую руку той самой инструкции RET.

Посмотрим на это творение сумеречного гения поближе:

// 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);
}

Сразу убеждаемся, что вызов onFiberFinished() произошёл с использованием собственного стека волокна, последним получившего управление:

assert((*_itFiber)->isOwnerOfStack(lowLevelGetCurrentStack()));

Если алгоритм Fiber manager'а не сломан, то это обеспечивается автоматически. Далее удаляем завершившееся волокно из списка _fibers и, если список после этого опустел, выбираем для возврата управления стек главного кода:

sp = _mainSp;

В том случае, если существуют другие незавершённые волокна, то выбираем следующий по порядку дескриптор, получаем стек волокна:

sp = (*_itFiber)->getStackPointer();

И отдаём управление в код с адресом, хранящимся в выбранном стеке:

lowLevelResume(sp); // it doesn't return control!

Вот и вся реализация переключения волокон.

Загадочный мир 64-битного кода

C/C++ код для обеих платформ общий, а самая вкусняшка - ассемблер - заметно различаются. Сосредоточимся на этой разнице. Гурманы приготовили вилки, наточили ножи, подвинули поближе метатели лайков и навели их на текст автора.

64 бита - это не просто 2 по 32. Это намного хужелучше. Регистры общего назначения стали 64-битными, и, к уже привычным нам, добавились 8 новых 64-битных регистров R8-R15 ,

Отличия касаются и соглашений о вызовах функций (ABI). Все эти cdecl и stdcall превращаются в один элегантный вариант fastcall:

Первые 4 параметра, если это указатели или целые числа, передаются через регистры RCX, RDX, R8, и R9, а если у нас числа с плавающей точкой, то через регистры XMM0L, XMM1L, XMM2L, и XMM3L.

Подробности по ссылке.

Регистры, которые необходимо восстанавливать на выходе из функции (non-volatile registers):

RBX, RBP, RDI, RSI, RSP, R12, R13, R14, R15, и XMM6-XMM15

Подробности по ссылке.

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

Перед вызовом функции стек должен быть выравнен на адрес, кратный 16 байт.

Для этого автор приготовил маленькую макрокоманду 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
;----------------------------------------------------------------------------

Что ещё за SPL и зачем этот огрызок нужен?

spl - это младшая 8-битная (1 байт) часть регистра-указателя стека rsp. Дотошный читатель спросит: от чего автор не желает там использовать rsp вместо его огрызка spl? Нельзя rsp, даже если очень захочется изобразить что-то такое:

and     rsp, 0fffffffffffffff0h

ml64.exe (это macro assembler MASM) при трансляции программы напишет нам:

LowLevel_x86-64.asm(124) : error A2084:constant value too large

Это странно, но факт: Не существует инструкции AND для 64-битной константы. И не только AND этим грешит. Есть вариант для 32-битной константы* которая расширяется автоматически до 64 бит со знаком, если первый операнд 64-битный:

*) Константы на схемах инструций CPU обозначаются аббревиатурой imm от слова immediate - непосредственный, прямой.

Другая особенность - требование перед вызовом функции иметь в стеке минимум 32 байта зарезервированного места, названного Shadow space. Вызываемая функция может использовать это пространство для хранения копии переданных через регистры параметров и для реализации, например, механизма обработки переменного количества аргументов.

Подробности по ссылке.

Чтобы не писать везде, где требуется выделить место на стеке, число 32, в код добавлена константа SHADOWSIZE:

;----------------------------------------------------------------------------
; Shadow Space (see https://docs.microsoft.com/en-us/cpp/build/stack-usage?view=msvc-160 ) 
SHADOWSIZE equ 32
;----------------------------------------------------------------------------

Microsoft великодушно нарисовала стек в новом дивном мире для ситуации, когда функция A вызвала функцию B:

Перейдём к рассмотрению отличий 32- и 64-битных версий ассемблерных функций

64-битная версия 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
;----------------------------------------------------------------------------

Логика кода идентична таковому в 32-битной версии, но есть и заметные отличия:

• В собственном стеке волокна выделяется место под Shadow space.

• Этот стек выравнивается по границе 16 байт.

• Вместо push onFiberFinished используется странная комбинация инструкций

    ; onFiberFinished is handler which is called at the fiber completion stage.
    mov     r8, onFiberFinished
    push    r8

-Как будто нельзя было оставить прежний вариант... - скажет читатель. -Понятно же, что onFiberFinished - это просто адрес точки входа в одноимённую функцию!

push   80000000h

• Вместо помещения в стек адреса входа в функцию волокна, в данном случае этот параметр приходит в lowLevelEnqueueFiber через rcx, в стек уже знакомым способом попадает адрес какой-то странной функции fiberEntry. А перед ней вталкиваются регистры rdx и rcx. Отметим для себя эту особенность, а пока что смотрим дальше.

• Помните, в 32-битной версии мы клали в стек четыре 32-битных нуля как значения для четырёх non-volatile регистров на старте волокна? Всего они занимали там 16 байт. В этот раз регистров намного больше и не все они одинакового размера. Я решил просто вызвать pushall. Да, пришлось смириться с тем, что вместо нулей в стек попадёт что-то около 216 байт мусора из настоящих регистров, но он нам никак не помешает запустить нить.

• Отдельной инструкцией push 0 кладётся значение для rbp. Этот non-volatile регистр не включен в pushall/popall намеренено. Мы работаем с ним особым образом.

Вот такие отличия.

Вернёмся к упомянутой странной функции 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
;----------------------------------------------------------------------------

С учётом имеющихся знаний, никакой мистики там нет. fiberEntry переписывает параметры, переданные через стек, в нужные регистры согласно ABI и вызывает точку входа в волокно.

Реализация yield() практически повторяет таковую для 32-битного режима, а отличия связаны с требованиями по выравниванию стека:

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

В 64-битных вариантах я решил всё же использовать enter/leave для разнообразия. Ранее в этой статье описано, как они работают.

Совсем без изменений lowLevelResume, разве что входной параметр передаётся через регистр rcx вместо стека:

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

Чуть не забыл! Есть ещё одна ассемблерная функция, которую я не упомянул. Она простая и нужна для получения вершины текущего используемого стека в C-коде:

64-битная версия

;----------------------------------------------------------------------------
; Get current stack pointer to provide it to C++ code
; extern "C" MemAddr* lowLevelGetCurrentStack();
lowLevelGetCurrentStack PROC
    mov     rax, rsp
    ret
lowLevelGetCurrentStack ENDP
;----------------------------------------------------------------------------

И такая же 32-битная

;----------------------------------------------------------------------------
; Get current stack pointer to provide it in C++ code
; extern "C" MemAddr* lowLevelGetCurrentStack();
lowLevelGetCurrentStack PROC
    mov     eax, esp
    ret
lowLevelGetCurrentStack ENDP
;----------------------------------------------------------------------------

Как видите, они абсолютно идентичны и примитивны, но используются в C-коде, а, стало быть, достойны упоминания.

Заключение

Надеюсь, статья получилась умеренно скучной и хотя бы немного познавательной. На написание этого текста и примера кода потрачено много часов и мыслительных усилий. Автор будет очень благодарен за отзывы в комментариях, лайки и плюсики в карму.

Исходники на GitHub