Трассировка стека вызовов в среде кооперативной многозадачности: стектрейсы, файберы, два ствола

Привет, Хабр! Для отладки и анализа производительности часто используется трассировка (сбор) стека вызовов aka стектрейс. И если для трассировки стека различных потоков выполнения есть системные средства, то работа с асинхронными языками и фреймворками предполагает наличие отдельного контекста выполнения и стека вызовов для каждой единицы исполнения. В этой статье мы поговорим о файберах. Они прозрачны с точки зрения операционной системы, что влечет за собой определенные сложности. Если трассировка стека вызовов активного файбера тривиальна (можно представить, что кооперативной многозадачности вообще нет), то как собирать стектрейс с неактивных файберов?

За этим вопросом кроется некоторый пласт «черной магии», и найти ответ на него не так просто: информация разбросана по разным источникам, а подходящие примеры встречаются только в определенных проектах. Меня зовут Георгий Лебедев, я работаю в команде разработки ядра Tarantool. Под катом я поделюсь опытом, который мы выработали в Tarantool, и развею ту самую «черную магию». 

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

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

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

Оптимальное использование вычислительных ресурсов в многопроцессорных системах предполагает возможность единовременного выполнения разных задач — многозадачность. Она может быть одного из двух доступных видов: 

1. Вытесняющая многозадачность — это привычные нам потоки выполнения. Вытесняющей она называется потому, что потоки имеют иллюзию (абстракцию) монопольного выполнения в процессоре, будь то настоящий процессор или виртуальная машина. Они ничего не знают о планировании выполнения и управлении потоками и не могут никак влиять на эти процессы — этим заведует операционная система (или рантайм, или виртуальная машина). ОС по своему усмотрению вытесняет из исполнения одни потоки и передает управление другим, обеспечивая прогресс в выполнении всех потоков.
2. Кооперативная многозадачность, напротив, вносит в модель выполнения (рантайм) такие понятия, как планировщик и передача управления. В рамках этой модели единицы исполнения — файберы — сами решают, когда отдать управление другим. Операционная система никак не влияет на исполнение отдельных файберов. Для обеспечения прогресса в выполнении файберы должны кооперировать друг с другом, отсюда и происходит название. Кстати, кроме файберов существуют еще корутины, но в статье мы рассматриваем именно файберы. 

Сейчас асинхронные фреймворки и языки в высоконагруженных приложениях используются повсеместно, например: folly::fibers (C++), asyncio (Python), Seastar (C++), Tokio (Rust), userver (C++), Boost.Asio (C++), boost.Fiber (C++), Erlang, Golang, Kotlin, Lua, Julia. Некоторые из них основаны на концепции кооперативной многозадачности. Не обошло это стороной и Tarantool, в основе архитектуры которого лежит кооперативная многозадачность на файберах.

Типичный файберный рантайм состоит из главного управляющего файбера, планировщика и остальных файберов, которые запускаются планировщиком. Каждый файбер имеет свой контекст выполнения. Он состоит из стека вызовов (каждый файбер имеет динамический выделяемый стек) и состояния регистров.

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

Трассировка стека вызовов

Теперь самое время напомнить, что из себя представляет трассировка стека вызовов. Стектрейсинг — это важная часть жизненного цикла разработки. Часто этот процесс используется для анализа выполнения программ, для отладки или оптимизации производительности. По сути, это отчет о действующей цепочке вызовов функций в определенный момент времени при выполнении программы.

Как на x86_64, так и на AArch64 каноническая структура фрейма стека вызовов выглядит следующим образом:

1. Адрес возврата в начало фрейма.
2. Адрес начала предыдущего фрейма.
3. Локальный контекст: аргументы функции, не поместившиеся в регистры, локальные переменные и Caller-Saved-регистры.

Трассировка стека вызовов состоит из последовательного выполнения двух шагов: 

1. Получить контекст для восстановления текущего фрейма aka Call frame information (CFI).
2. Получить контекст для трассировки стека наверх, состоящий из текущего адреса возврата и состояния стека предыдущего фрейма aka Canonical frame address (CFA).

Расхождения начинаются на шаге получения контекста: этот процесс зависит от архитектуры машины и имеющейся отладочной информации. Существуют два основных стандарта: Frame pointer based и DWARF. 

1. Во Frame pointer based используют выделенный регистр для сохранения CFA (Base pointer register aka RBP на x86_64 и Frame pointer register aka FP (x29) на AArch64) и на строго фиксированной структуре стекового фрейма, как на картинке выше. При этом регистр для сохранения CFA перестает быть регистром общего назначения, а компилятор ограничивается в оптимизации стекового фрейма. Это потенциально негативно влияет на производительность на быстром пути (Fast path), когда трассировка стека не используется.
2. DWARF основан на использовании формата отладочной информации DWARF. Машинные инструкции аннотируются специальной отладочной информацией. Она позволяет по текущему состоянию машины восстановить весь необходимый контекст. Для аннотации компилятор генерирует в ассемблере специальные CFI-директивы, которые позволяют генерировать вплоть до стековой машины для вычислений.

CFI-директивы представляют собой простые арифметические и ссылочные инструкции, позволяющие по каким-то референсным значениям текущего состояния машины (например, Stack pointer register, RSP на x86_64 или SP на AArch64) вычислить CFA или значение определенного регистра. Например, link register LR (x30) на AArch64, в котором сохраняется адрес возврата.

Рассмотрим пример:

```asm  .cfi_register x9, x8  .cfi_def_cfa x9, 128  .cfi_rel_offset x29, 64  .cfi_val_offset x30, 256  ``` 

Здесь  задается следующее состояние:

1. Значение регистра x9 сохранено в x8.
2. Значение CFA можно вычислить как значение регистра x8 плюс 128.
3. Значение регистра x29 сохранено по адресу CFA плюс 64.
4. Значение регистра x30 есть адрес CFA плюс 256.

При генерации объектного файла в специальной секции .eh_frame CFI-директивы синтезируются в CFI-records. Они состоят из Common information entry (CIE) и массива Frame description entry (FDE), ставящих в соответствие диапазону машинных инструкций набор CFI-директив. Более подробную информацию о структуре .eh_frame можно найти здесь.

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

Трассировка стека вызовов в среде кооперативной многозадачности

Выше мы уже отмечали, что в любой момент времени в рамках одного потока может исполняться строго один файбер. Для текущего, активного файбера трассировка стека вызовов тривиальна: достаточно просто вызвать библиотечную функцию, например backtrace из glibc или unw_backtrace из GNU Libunwind. К сожалению, такие библиотеки умеют собирать стек вызовов только из текущего контекста выполнения.

В асинхронных фреймворках, использующих файберы, как правило, нет встроенной поддержки трассировки стека вызовов неактивных файберов. Есть только расширения для отладчика, например у folly. Основная сложность заключается в том, что нужно искусственно восстановить контекст выполнения неактивного файбера без передачи ему управления. Для трассировки стеков вызовов всех файберов главного (транзакционного) потока в сервер приложений Tarantool встроены соответствующие функции.

Как же собрать стек вызовов неактивных файберов? Для этого в Tarantool используется следующий трюк, использующий ассемблерную вставку:

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

Такой трюк, к сожалению, несовместим с работой трассировщиков стеков, которую я описал выше. Несовместимость возникает из-за того, что во время выполнения трюка в ассемблерной вставке изменяется состояние машины — значение стекового указателя и других платформенных регистров. При этом CFI остается такой же, какой была до Inline assembly, из-за чего трассировщик стека начинает сходить с ума.

CFI-директивы спешат на помощь

К счастью, CFI-директивы можно самостоятельно вставлять в ассемблерный код, тем самым вручную размечая контекст восстановления для трассировщика стека. Примеры такого кода можно найти в реализации clone, start (glibc), во фреймворке Seastar, в языке Julia, в ART (Android Runtime) — там они используются для аннотации начала стека вызовов их кастомных единиц исполнения, будь то потоки или корутины.

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

```asm  1. Save current fiber context. */  2. pushq %rbp  3. pushq %rbx  4. pushq %r12  5. pushq %r13  6. pushq %r14  7. pushq %r15  8. /* Setup first function argument. */  9. movq %1, %rdi  10. /* Setup second function argument. */  11.movq %rsp, %rsi  12. /* Restore target fiber context. */  13. "movq (%2), %rsp  14. movq 0(%rsp), %r15  15. movq 8(%rsp), %r14  16. movq 16(%rsp), %r13  17. movq 24(%rsp), %r12  18. movq 32(%rsp), %rbx  19. movq 40(%rsp), %rbp  20. /* Setup CFI. */  21. ".cfi_remember_state  22. ".cfi_def_cfa %rsp, 8 * 7  23. leaq %P3(%rip), %rax  24. call *%rax  25. .cfi_restore_state  26. /* Restore original fiber context. */  27. mov %rax, %rsp  28. popq %r15  29. popq %r14  30. popq %r13  31. popq %r12  32. popq %rbx  33. popq %rbp  ```   ```asm  1. /* Save current fiber context. */  2. sub sp, sp, #8 * 20  3. stp x19, x20, [sp, #16 * 0]  4. stp x21, x22, [sp, #16 * 1]  5. stp x23, x24, [sp, #16 * 2]  6. stp x25, x26, [sp, #16 * 3]  7. stp x27, x28, [sp, #16 * 4]  8. stp x29, x30, [sp, #16 * 5]  9. stp d8,  d9,  [sp, #16 * 6]  10. stp d10, d11, [sp, #16 * 7]  11. stp d12, d13, [sp, #16 * 8]  12. tstp d14, d15, [sp, #16 * 9]  13. /* Setup first function argument. */  14. mov x0, %1  15. /* Setup second function argument. */  16. mov x1, sp  17. /* Restore target fiber context. */  18. ldr x2, [%2]  19. mov sp, x2  20. ldp x19, x20, [sp, #16 * 0]  21. ldp x21, x22, [sp, #16 * 1]  22. ldp x23, x24, [sp, #16 * 2]  23. ldp x25, x26, [sp, #16 * 3]  24. ldp x27, x28, [sp, #16 * 4]  25. ldp x29, x30, [sp, #16 * 5]  26. ldp d8,  d9,  [sp, #16 * 6]  27. ldp d10, d11, [sp, #16 * 7]  28. ldp d12, d13, [sp, #16 * 8]  29. ldp d14, d15, [sp, #16 * 9]  30. /* Setup CFI. */  31. .cfi_remember_state  32. .cfi_def_cfa sp, 16 * 10  33. .cfi_offset x29, -16 * 5  34. .cfi_offset x30, -16 * 5 + 8  35. bl %3  36. .cfi_restore_state\n"  37. /* Restore original fiber context. */  38. ldp x19, x20, [x0, #16 * 0]  39. ldp x21, x22, [x0, #16 * 1]  40. ldp x23, x24, [x0, #16 * 2]  41. ldp x25, x26, [x0, #16 * 3]  42. ldp x27, x28, [x0, #16 * 4]  43. ldp x29, x30, [x0, #16 * 5]  44. ldp d8,  d9,  [x0, #16 * 6]  45. ldp d10, d11, [x0, #16 * 7]  46. ldp d12, d13, [x0, #16 * 8]  47. ldp d14, d15, [x0, #16 * 9]  48. add sp, x0, #8 * 20  ``` 

Приведенные ассемблерные вставки — реализация трюка для сбора стека вызовов неактивного файбера на x86_64 и AArch64 соответственно. В них нас интересуют строки 20–25 для x86_64 и строки 30–36 для AArch6.

Как на x86_64, так и на AArch64 мы сохраняем состояние CFI до начала сбора стека вызовов и корректируем значение CFA так, чтобы началу фрейма соответствовал адрес возврата неактивного файбера. Поскольку на AArch64 для адреса возврата есть специально выделенный Link register — LR (x30), на этой платформе необходимо также явно указать, где сохранено его значение. Также для совместимости с трассировкой по Frame pointer необходимо явно указать, где сохранено значение Frame pointer — FP (x29). Затем после сбора стека вызовов на обеих платформах мы восстанавливаем состояние CFI до прежнего, то есть до начала Inline assembly.

Заключение

Вот мы и приоткрыли завесу тайны трассировки стека в среде кооперативной многозадачности. Мы рассмотрели, как устроена кооперативная многозадачность на файберах, как устроена трассировка стека вызовов и как увязать одно с другим с помощью CFI-директив. Надеюсь, что в следующий раз, когда кто-то столкнется с подобной проблемой, эта статья окажется практически полезной и сориентирует в ее решении.

Скачать Tarantool можно на официальном сайте, а получить помощь — в Telegram-чате.