Как я могу создать параллельный стек и запустить сопрограмму на нем? - PullRequest
11 голосов
/ 22 июня 2010

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

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

Вы, ребята, знаете 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 по отношению к другому. Как только он возвращается к другой функции, он должен возобновить с того места, где он оставил (то есть во время или после вызова, который передал управление другой функции), подобно тому, как longjmp возвращается к setjmp.

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

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

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

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

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

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

Спасибо за чтение моего вопроса textwall.

Ответы [ 4 ]

9 голосов

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

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

a:
call b
b:
pop rax

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

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

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

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

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

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

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

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

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

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

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

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

void* coroutine_next(coroutine_state cs, void* arg)

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

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

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

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

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

void coroutine_yield(void* ret);

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

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

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

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

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

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

1 голос
/ 22 июня 2010

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

1 голос
/ 22 июня 2010

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

0 голосов
/ 11 марта 2013

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

...