Как создать параллельный стек и запустить на нем сопрограмму?

Я решил, что должен попытаться реализовать сопрограммы (я думаю, что я должен их назвать) для удовольствия и прибыли. Я ожидаю, что придется использовать ассемблер и, возможно, некоторые C, если я хочу сделать это полезным для всего.

Имейте в виду, что это для образовательных целей. Использование уже построенной библиотеки coroutine слишком просто (и действительно не весело).

Вы, ребята, знаете setjmp и longjmp? Они позволяют вам разматывать стек до предопределенного местоположения и возобновлять выполнение оттуда. Однако он не может перемотать "позже" в стек. Вернитесь раньше.

jmpbuf_t checkpoint;
int retval = setjmp(&checkpoint); // returns 0 the first time
/* lots of stuff, lots of calls, ... We're not even in the same frame anymore! */
longjmp(checkpoint, 0xcafebabe); // execution resumes where setjmp is, and now it returns 0xcafebabe instead of 0

То, что мне нужно - это способ запускать, без потоковой передачи, две функции на разных стеках. (Очевидно, только один запускается за один раз. Нет нити, я сказал.) Эти две функции должны иметь возможность возобновить другое исполнение (и остановить их собственное). Скорее всего, если они были друг с другом. Когда он вернется к другой функции, он должен вернуться туда, где он остался (то есть во время или после вызова, который дал управление другой функции), немного похоже на то, как longjmp возвращается к setjmp.

Вот как я это думал:

Функция A создает и обнуляет параллельный стек (выделяет память и все такое).
Функция A перетаскивает все свои регистры в текущий стек.
Функция A устанавливает указатель стека и базовый указатель на это новое местоположение и вызывает таинственную структуру данных, указывающую, куда перепрыгивать назад и где указывать указатель команд назад.
Функция A обнуляет большинство своих регистров и устанавливает указатель на начало функции B.

Это для инициализации. Теперь следующая ситуация будет бесконечно замкнутой:

Функция B работает в этом стеке, выполняет любую работу, в которой она нуждается.
Функция B переходит в точку, где требуется прервать и снова дать команду A.
Функция B подталкивает все свои регистры к своему стеку, берет таинственную структуру данных A дала ее в самом начале и устанавливает указатель стека и указатель на инструкцию, где ему было указано A. В этом процессе он возвращает A новую модифицированную структуру данных, которая сообщает, где возобновить B.
Функция A просыпается, возвращая все регистры, которые она вставляет в свой стек, и работает до тех пор, пока не дойдет до точки, где ей необходимо прервать и снова дать команду B.

Все это звучит хорошо для меня. Тем не менее, есть ряд вещей, с которыми я не совсем согласен.

По-видимому, на добром ol 'x86 была эта инструкция pusha, которая отправила бы все регистры в стек. Однако архитектуры процессоров развиваются, и теперь с x86_64 у нас есть намного больше универсальных регистров и, вероятно, несколько регистров SSE. Я не мог найти никаких доказательств того, что pusha действительно их подталкивает. В mordern x86 CPU имеется около 40 публичных регистров. Должен ли я сам делать все push es? Более того, для SSE-регистров нет push (хотя он должен быть эквивалентным - я новый для всего этого "ассемблера x86" ).
Меняет указатель на инструкцию так же просто, как сказать? Могу ли я сделать, например, mov rip, rax (синтаксис Intel)? Кроме того, получение значения от него должно быть несколько особенным, поскольку оно постоянно изменяется. Если мне больше нравится mov rax, rip (синтаксис Intel снова), будет rip располагаться в команде mov, инструкции после него или где-то между? Это просто jmp foo. Пустышка.
Я несколько раз упоминал о таинственной структуре данных. До сих пор я предполагал, что он должен содержать как минимум три вещи: базовый указатель, указатель стека и указатель команд. Есть ли что-нибудь еще?
Я что-то забыл?
Пока я действительно хотел бы понять, как все работает, я уверен, что есть несколько библиотек, которые делают именно это. Вы знаете что-нибудь? Есть ли какой-либо стандартный способ для POSIX или BSD, например pthread для потоков?

Спасибо, что прочитали мой <забавный > вопрос textwall.

Ответ 1

Вы правы в том, что PUSHA не работает на x64, он вызывает исключение #UD, поскольку PUSHA только толкает 16-разрядные или 32-разрядные регистры общего назначения. См. руководства Intel для всей информации, которую вы когда-либо хотели знать.

Настройка RIP проста, jmp rax установит RIP в RAX. Чтобы получить RIP, вы можете либо получить его во время компиляции, если уже знаете все исходные данные выхода coroutine, либо можете получить его во время выполнения, после этого вызова вы можете позвонить на следующий адрес. Вот так:

a:
call b
b:
pop rax

RAX теперь будет b. Это работает, потому что CALL нажимает адрес следующей команды. Этот метод также работает и на IA32 (хотя я бы предположил, что лучше использовать его на x64, поскольку он поддерживает RIP-относительную адресацию, но я не знаю об этом). Конечно, если вы создаете функцию coroutine_yield, она может просто перехватить адрес вызывающего абонента:)

Поскольку вы не можете вытолкнуть все регистры в стек в одной команде, я бы не рекомендовал хранить состояние сопрограммы в стеке, поскольку это все равно усложняет ситуацию. Я думаю, что лучше всего было бы выделить структуру данных для каждого экземпляра coroutine.

Почему вы обнуляете вещи в функции A? Это, вероятно, не нужно.

Вот как бы я подошел ко всему, пытаясь сделать его максимально простым:

Создайте структуру coroutine_state, которая содержит следующее:

initarg
arg
registers (также содержит флаги)
caller_registers

Создайте функцию:

coroutine_state* coroutine_init(void (*coro_func)(coroutine_state*), void* initarg);

где coro_func является указателем на тело функции сопрограммы.

Эта функция выполняет следующие действия:

выделить структуру coroutine_state cs
присвойте initarg cs.initarg, это будет начальный аргумент для сопрограммы
присвойте coro_func cs.registers.rip
скопировать текущие флаги в cs.registers (не регистрировать, только флаги, так как нам нужны какие-то разумные флаги, чтобы предотвратить апокалипсис)
выделите некоторую приличную площадь для стека сопрограммы и назначьте ее cs.registers.rsp
возвращает указатель на выделенную структуру coroutine_state

Теперь у нас есть другая функция:

void* coroutine_next(coroutine_state cs, void* arg)

где cs - это структура, возвращаемая из coroutine_init, которая представляет экземпляр coroutine, а arg будет передаваться в сопрограмму coroutine по мере возобновления выполнения.

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

сохранить все текущие флаги/регистры в cs.caller_registers за исключением RSP, см. шаг 3.
сохраните arg в cs.arg
исправить указатель стека указателя (cs.caller_registers.rsp), добавив 2*sizeof(void*), исправит его, если вам повезет, вам придется посмотреть его, чтобы подтвердить его, вы, вероятно, хотите, чтобы эта функция была stdcall, поэтому никаких регистров подделаны, прежде чем называть его
mov rax, [rsp], присвойте RAX cs.caller_registers.rip; Объяснение: если ваш компилятор не находится на трещине, [RSP] будет содержать указатель инструкции к инструкции, которая следует за инструкцией вызова, которая вызвала эту функцию (то есть: адрес возврата)
загрузите флаги и регистры из cs.registers
jmp cs.registers.rip, эффективно возобновление выполнения сопрограммы

Обратите внимание, что мы никогда не возвращаемся от этой функции, сопрограммы, которые мы переходим к "возвращает" для нас (см. coroutine_yield). Также обратите внимание, что внутри этой функции вы можете столкнуться со многими сложностями, такими как пролог функций и эпилог, сгенерированный компилятором C, и, возможно, зарегистрировать аргументы, вы должны позаботиться обо всем этом. Как я уже сказал, stdcall избавит вас от многих неприятностей, я думаю, что gcc -fomit-frame_pointer удалит материал эпилога.

Последняя функция объявлена как:

void coroutine_yield(void* ret);

Эта функция вызывается внутри сопрограммы для "приостановки" выполнения сопрограммы и возврата к вызывающей стороне coroutine_next.

хранить флаги/регистры in cs.registers
исправить указатель стека coroutine (cs.registers.rsp), еще раз добавить 2*sizeof(void*) к нему, и вы хотите, чтобы эта функция также была stdcall
mov rax, arg (позволяет просто притворяться, что все функции в вашем компиляторе возвращают свои аргументы в RAX)
загрузить флаги/регистры из cs.caller_registers
jmp cs.caller_registers.rip Это по существу возвращается из вызова coroutine_next в стек стека сопроводителя сопроводителя, а так как возвращаемое значение передается в RAX, мы вернули arg. Скажем, если arg является NULL, то сопрограмма завершена, в противном случае это произвольная структура данных.

Итак, чтобы повторить, вы инициализируете сопрограмму coroutine с помощью coroutine_init, затем вы можете повторно ссылаться на экземпляр сопроводителя с помощью coroutine_next.

Сама функция сопроцессора объявлена: void my_coro(coroutine_state cs)

cs.initarg содержит аргумент начальной функции (конструктор мысли). Каждый раз, когда вызывается my_coro, cs.arg имеет другой аргумент, который был указан coroutine_next. Таким образом, сопроцессор сопрограммы связывается с сопрограммой. Наконец, каждый раз, когда coroutine хочет приостановить себя, он вызывает coroutine_yield и передает ему один аргумент, который является возвращаемым значением для сопроводителя сопрограммы.

Хорошо, теперь вы можете подумать: "Это просто!", но я оставил все сложности при загрузке регистров и флагов в правильном порядке, сохраняя при этом не поврежденный фрейм стека и каким-то образом сохраняя адрес вашей структуры данных coroutine (вы просто перезаписали все свои регистры) в потокобезопасной манере. Для этой части вам нужно будет узнать, как ваш компилятор работает внутри... удачи:)

Ответ 2

Хорошая обучающая ссылка: libcoroutine, особенно их реализация setjmp/longjmp. Я знаю, что это не забавно использовать существующую библиотеку, но вы можете хотя бы получить общее представление о том, куда идете.

Ответ 3

У Саймона Татхама есть интересная реализация сопрограмм в C, которая не требует каких-либо знаний в области архитектуры или стекирования. Это не совсем то, что вам нужно, но я подумал, что это тем не менее может иметь хотя бы академический интерес.

Ответ 4

boost.coroutine(boost.context) на boost.org делает все для вас