Быстрые волокна / сопрограммы под Windows x64

Так что у меня есть этот сопрограммный 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 ответ

Решение

Этот ответ касается только "это быстро" часть вопроса.

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

Во-первых, краткое описание поведения типичного предиктора адреса возврата.

  • Каждый раз 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который он в свою очередь называет coresume4 возобновить сопрограмму 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 подпрограммы, и вы должны сделать прыжок к другой процедуре изнутри там, и я не могу понять, как сохранить равновесие стеков и вернуться в правильное место с этими ограничениями.

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

Если вы можете встроить код в call-сайт ваших методов поведения (например, с поддержкой компилятора или встроенного 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 а затем делает 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 Предиктор не нуждается в "разогреве", но косвенный предсказатель ветвления может это сделать, особенно когда в промежутке вызывается другая сопрограмма.

Источник
Другие вопросы по тегам