Быстрые волокна / сопрограммы под Windows x64 - PullRequest
0 голосов
/ 19 мая 2018

Итак, у меня есть этот сопрограммный API, расширенный мной на основе кода, который я нашел здесь: https://the8bitpimp.wordpress.com/2014/10/21/coroutines-x64-and-visual-studio/

struct mcontext {
  U64 regs[8];
  U64 stack_pointer;
  U64 return_address;
  U64 coroutine_return_address;
};

struct costate {
   struct mcontext callee;
   struct mcontext caller;
   U32 state;
};

void coprepare(struct costate **token,
       void *stack, U64 stack_size, cofunc_t func); /* C code */
void coenter(struct costate *token, void *arg);     /* ASM code */
void coyield(struct costate *token);                /* ASM code */
int  coresume(struct costate *token);               /* ASM code, new */

Я застрял в реализации coyield ().coyield () может быть написан на C, но это сборка, с которой у меня проблемы.Вот что я получил до сих пор (синтаксис MASM / VC ++).

;;; function: void _yield(struct mcontext *callee, struct mcontext *caller)
;;; arg0(RCX): callee token
;;; arg2(RDX): caller token
_yield proc
    lea RBP, [RCX + 64 * 8]
    mov [RCX +  0], R15
    mov [RCX +  8], R14
    mov [RCX + 16], R13
    mov [RCX + 24], R12
    mov [RCX + 32], RSI
    mov [RCX + 40], RDI
    mov [RCX + 48], RBP
    mov [RCX + 56], RBX

    mov R11, RSP
    mov RSP, [RDX + 64]
    mov [RDX + 64], R11

    mov R15, [RDX + 0]
    mov R14, [RDX + 8]
    mov R13, [RDX + 16]
    mov R12, [RDX + 24]
    mov RSI, [RDX + 32]
    mov RDI, [RDX + 40]
    mov RBP, [RDX + 48]    
        mov RBX, [RDX + 56]

    ret
_yield endp

Это прямая адаптация кода 8bitpimp.То, что он не делает, если я правильно понимаю этот код, помещает mcontext-> return_address и mcontext-> coroutine_return_address в стек, который должен выдаваться ret.Кроме того, это быстро?IIRC, это вызывает несоответствие в предикторе ответвления, найденном в современных x64-компонентах.

1 Ответ

0 голосов
/ 23 мая 2018

В этом ответе рассматривается только часть вопроса «быстро».

Предсказание обратного адреса

Сначала краткое описание поведения типичного предиктор обратного адреса.

  • Каждый раз, когда создается call, адрес возврата, который помещается в реальный стек, также сохраняется в структуре ЦП, называемой буфером адреса возврата или чем-то в этом роде.
  • Когда выполняется ret (возврат), ЦПУ предполагает, что адресатом будет текущий адрес в верхней части буфера адреса возврата, и эта запись из буфера адреса возврата "вытолкнута".

Эффект заключается в идеальном 1 прогнозировании call / ret пар, при условии, что они встречаются в своем обычном правильно вложенном шаблоне и что ret фактически удаляет неизмененныйадрес возврата нажимается call в каждом случае.Для получения более подробной информации вы можете начать здесь .

Обычные вызовы функций в C или C ++ (или почти любом другом языке) обычно всегда следуют этому правильно вложенному шаблону 2 ,Поэтому вам не нужно делать ничего особенного, чтобы воспользоваться преимуществом предсказания возврата.

Режимы сбоя

В случаях, когда call / ret не спарены нормально,предсказания могут потерпеть неудачу (по крайней мере) несколькими различными способами:

  • Если указателем стека или возвращаемым значением в стеке манипулируют так, что ret не возвращает место, гдесоответствующее нажатие call приведет к ошибке прогнозирования цели ветвления для этого ret, но последующие обычно вложенные ret инструкции будут продолжать предсказывать правильно, пока они правильно вложены.Например, если в функции вы добавляете несколько байтов к значению [rsp], чтобы пропустить инструкцию, следующую за call в вызывающей функции, следующий ret будет неверно предсказан, а ret, который следуетвнутри вызывающей функции должно быть все в порядке.
  • С другой стороны, функции call и ret неправильно вложены, весь буфер предсказания возврата может стать не выровненным, что приведет к будущим инструкциям ret,если таковые имеются, которые используют существующие значения для неверного прогнозирования 2.5 .Например, если вы call входите в функцию, но затем используете jmp для возврата к вызывающей стороне, существует несоответствие call без ret.ret внутри вызывающего абонента будет неверно предсказываться, как и ret внутри вызывающего абонента и т. Д., Пока все не выровненные значения не будут использованы или перезаписаны 3 .Подобный случай произошел бы, если бы у вас ret не было сопоставления с соответствующим вызовом (и этот случай важен для последующего анализа).

Вместо двух приведенных выше правил вы также можете простоопределить поведение предиктора возврата, проследив код и отслеживая, как выглядит стек возврата в каждой точке.Каждый раз, когда у вас есть инструкция ret, посмотрите, вернется ли она к текущей вершине стека возврата - если нет, вы получите неверное предсказание.

Стоимость неверного предсказания

Фактическая стоимостьот неправильного прогноза зависит окружающий код.Обычно дается ~ 20 циклов, и это часто можно увидеть на практике, но фактическая стоимость может быть ниже: например, до нуля, если процессор способен разрешить ошибочное прогнозирование рано и и начать выборкупо новому пути без прерывания критического пути или выше: например, если ошибки прогнозирования ветвления требуют много времени для устранения и уменьшения эффективного параллелизма операций с большой задержкой.Независимо от того, мы можем сказать, что штраф обычно значительный , когда это происходит в операции, когда другие требуют только несколько инструкций.

Быстрые сопрограммы

Существующее поведение для Coresume и Coyield

Существующая функция _yield (переключение контекста) меняет указатель стека rsp, а затем использует ret для возврата в другое местоположение, чем то, что было фактически нажано вызывающим абонентом (в частности, оно возвращается в местоположение, которое было помещено встек caller, когда вызывающая сторона ранее вызывала yield).Как правило, это приведет к неправильному прогнозу в ret внутри _yield.

Например, рассмотрим случай, когда какая-то функция A0 делает обычный вызов функции для A1, который она вызывает coresume 4 для возобновления сопрограммы B1, которая позже вызывает coyield для возврата к A1.Внутри вызова к coresume стек возврата выглядит как A0, A1, но затем coresume меняет rsp, указывая на стек для B1, а верхнее значение этого стека - это адрес внутри B1 сразуследующий coyield в коде для B1.Следовательно, ret внутри coresume переходит к точке в B1, а не к точке в A1, как ожидает стек возвратов.Следовательно, вы получаете неправильное предсказание для этого ret, и стек возврата выглядит как A0.

Теперь рассмотрим, что происходит, когда B1 вызывает coyield, что реализуется в основном таким же образом coresume: вызов coyield толкает B1 в стек возвратов, который теперь выглядит как A0, B1, а затем меняет местами стек, указывая на A1 стек, а затем выполняет ret, который вернется к A1,Таким образом, неправильное предсказание ret произойдет таким же образом, и стек останется как A0.

Таким образом, плохая новость заключается в том, что жесткая серия вызовов coresume и coyield (как, например, типично для итератора, основанного на доходности), будет неверно предсказывать каждый раз.Хорошей новостью является то, что теперь внутри A1, по крайней мере, стек возвратов верен (не выровнен) - если A1 возвращается к своему вызывающему A0, возвращение правильно прогнозируется (и так далее, когда A0 возвращается к его абонент и т. Д.).Таким образом, вы каждый раз получаете ошибочный прогноз, но, по крайней мере, в этом сценарии вы не смещаете стек возвратов.Относительная важность этого зависит от того, как часто вы вызываете coresume / coyield по сравнению с вызывающими функциями, как правило, в приведенной ниже функции, которая вызывает coresume.

Как сделать это быстрым

Так можем ли мы исправить неверное предсказание?К сожалению, это сложно в комбинации вызовов C и внешних ASM, потому что выполнение вызова coresume или coyield подразумевает вызов, вставленный компилятором, и это трудно размотать в ассемблере.

Тем не менее, давайте попробуем.

Использовать косвенные вызовы

Один из подходов - использовать вообще ret и просто использовать косвенные переходы.

Этопросто замените ret в конце ваших вызовов coresume и coyield на:

pop r11
jmp r11

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

Если проанализировать повторную последовательность вызовов coresume и coyield, как указано выше, мы получим результат, что буфер стека возврата просто начинает расти бесконечно, как A0, A1, B1, A1, B1, ...,Это происходит потому, что на самом деле мы не используем ret вообще в этой реализации.Таким образом, мы не терпим ошибочных предсказаний возврата, потому что мы не используем ret!Вместо этого мы полагаемся на точность косвенного предиктора ветвления для прогнозирования jmp11.

Принцип работы этого предиктора зависит от того, как реализованы coresume и coyeild.Если они оба вызывают общую функцию _yield, которая не встроена, существует только одно местоположение jmp r11, и этот jmp поочередно перейдет в местоположение в A1 и B1.Большинство современных косвенных предикторов будут предсказывать этот простой повторяющийся паттерн в порядке, хотя более старые, которые отслеживали только одно местоположение, не будут.Если _yield вставлено в coresume и coyield или вы просто скопировали код в каждую функцию, есть два отдельных jmp r11 сайта вызова, каждый из которых видит только одно местоположение, и должен быть хорошопредсказывается любым процессором с косвенным предсказателем ветвления 6 .

Так что это, как правило, должно предсказывать серию жестких coyield и coresume вызовов 7 , но за счет уничтожения буфера возврата, поэтому, когда A1 решает вернуться к A0 это будет неверно предсказано, а также последующие возвраты A0 и так далее.Размер этого штрафа ограничен выше размером буфера возврата стека, поэтому, если вы делаете много жестких coresume/yield вызовов, это может быть хорошим компромиссом.

Это лучшее, что я могу придумать в рамкахограничение внешних вызовов функций, написанных на ASM, потому что у вас уже есть подразумеваемое значение call для ваших подпрограмм co, и вам нужно перейти к другой процедуре изнутри, и я не вижу, как сохранитьстеки уравновешены и возвращаются в правильное местоположение с этими ограничениями.

Встроенный код на сайте вызова

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

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

; rcx - current context
; rdc - context for coroutine we are about to resume

; save current non-volatile regs (not shown)
; load non-volatile regs for dest (not shown)
lea r11, [rsp - 8]
mov [rcx + 64], r11 ; save current stack pointer
mov r11, [rdx + 64] ; load dest stack pointer
call [r11]

Обратите внимание, что coresume на самом деле не выполняет обмен стека - он просто загружает целевой стек в r11 и затем does call против [r11], чтобы прыгнуть к сопрограмме.Это необходимо для того, чтобы call правильно выдвигал местоположение, к которому мы должны вернуться в стеке вызывающей стороны.

Тогда coyield будет выглядеть примерно так (встроено в вызывающую функцию):

; save current non-volatile regs (not shown)
; load non-volatile regs for dest (not shown)
lea r11, [after_ret]
push r11             ; save the return point on the stack
mov  rsp, [rdx + 64] ; load the destination stack
ret
after_ret:
mov rsp, r11

Когда вызов coresume переходит на сопрограмму, он заканчивается на after_ret, и перед выполнением кода пользователя инструкция mov rsp, r11 переходит в соответствующий стек для сопрограммы, которая была сохранена в r11на coresume.

Таким образом, по существу, coyield состоит из двух частей: верхняя половина выполняется перед выходом (что происходит при вызове ret) и нижняя половина, которая завершает работу, начатую coresume,Это позволяет использовать call в качестве механизма для выполнения прыжка coresume и ret для выполнения прыжка coyield.call / ret в этом случае сбалансированы.

Я замалчиваю некоторые детали этого подхода: например, поскольку не задействован вызов функции, энергонезависимые регистры, заданные ABIна самом деле не особенные: в случае встроенной сборки вам нужно будет указать компилятору, какие переменные вы закроете и сохраните остальные, но вы можете выбрать любой набор, который вам удобен.Выбор большего набора закрытых переменных делает кодовые последовательности coresume / coyield самими короче, но потенциально создает большее регистровое давление на окружающий код и может заставить компилятор пролить больше окружающего вас кода.Возможно, в идеале нужно просто объявить все засоренным, и тогда компилятор просто выдаст то, что ему нужно.


1 Конечно, на практике существуют ограничения: размер возвратаБуфер стека, вероятно, ограничен некоторым небольшим числом (например, 16 или 24), поэтому, как только глубина стека вызовов превысит это, некоторые обратные адреса будут потеряны и не будут правильно предсказаны.Кроме того, различные события, такие как переключение контекста или прерывание, могут испортить предиктор стека возврата.

2 Интересным исключением был общий шаблон для чтения текущего указателя инструкции в x86 (32-битный) код: нет инструкции, чтобы сделать это напрямую, поэтому вместо этого можно использовать последовательность call next; next: pop rax: call для следующей инструкции, которая обслуживает только push адрес в стеке, который удален.Нет соответствующего ret.Однако современные процессоры фактически распознают этот шаблон и не разбалансируют предиктор обратного адреса в этом особом случае.

2.5 Сколько неверных прогнозов это предполагает, зависит от того, как net возвращает вызывающую функцию: если она немедленно начинает вызывать еще одну глубокую цепочку вызовов, неправильно выровненные записи стека возврата могут вообще никогда не использоваться, например.

3 Или, возможно, до тех пор, пока стек обратного адреса не будет выровнен с помощью ret без соответствующего вызова, в случае "два неправильных действия делают право".

4 Вы на самом деле не показали, как coyield и coresume на самом деле вызывают _yield, поэтому в остальной части вопроса я буду предполагать, что они реализованы по существу так же, как _yield, напрямуюв пределах coyield или coresume без вызова _yield: т.е. скопируйте и вставьте код _yield в каждую функцию, возможно, с небольшими изменениями, чтобы учесть разницу.Вы также можете выполнить эту работу, позвонив по номеру _yield, но у вас будет дополнительный уровень вызовов и повторов, который усложнит анализ.

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

6 Конечно, этот анализ применим только к простому случаю, когда у вас есть одинcoresume вызов, вызываемый в сопрограмму с одним coyield вызовом.Возможны более сложные сценарии, например, несколько вызовов coyield внутри вызываемого абонента или несколько вызовов coresume внутри вызывающего абонента (возможно, для различных процедур).Однако применяется та же схема: случай с разделенными jmp r11 сайтами будет представлять собой более простую партию, чем объединенный случай (возможно, за счет увеличения ресурсов iBTB).

7 Одно исключениебудет первым или двумя вызовами: предиктору ret не требуется «разминка», но может сделать предиктор непрямой ветвления, особенно когда в промежутке вызывается другая сопрограмма.

...