Синхронные и асинхронные стектрейсы: опыт использования в Facebook

Моя цель - предложение широкого ассортимента товаров и услуг на постоянно высоком качестве обслуживания по самым выгодным ценам.

Прежде чем перейти к статье, хочу вам представить, экономическую онлайн игру Brave Knights, в которой вы можете играть и зарабатывать. Регистируйтесь, играйте и зарабатывайте!

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

Обычные синхронные стектрейсы

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

struct stack_frame {
  stack_frame* nextFrame;
  void* returnAddress;
};

Обычно такая структура заполняется специализированными ассемблерными инструкциями. Например, в x86_64 вызывающая сторона выполняет инструкцию call, которая забрасывает возвращаемый адрес в стек, а затем перепрыгивает к входной точке функции. Затем первая инструкция вызываемой стороны забрасывает в стек регистр ebp (который обычно содержит указатель на актуальную структуру stack_frame), а после этого копирует регистр esp (тот, что содержит указатель на структуру stack_frame, которую мы только что заполнили) в регистр ebp.

Например:

caller:
  ...
  call callee         # Забрасывает в стек адрес следующей инструкции,
                      # заполняя член 'returnAddress' структуры 'stack_frame'.
                      # Затем перепрыгивает к адресу 'callee'. 
  mov rsp[-16], rax   # Где-нибудь сохраняем результат
  ...
 
callee:
  push rbp           # Забрасывает rbp (указатель на stack_frame) в стек (заполняет член 'nextFrame')
  mov rbp, rsp       # Обновляет rbp, чтобы он указывал на новый stack_frame
  sub rsp, 16        # Резервирует дополнительные 16 байт в пространстве стека 
  ...
  mov rax, 42        # Устанавливает возвращаемое значение в 42
  leave              # Копирует rbp -> rsp, выталкивает rbp из стека
  ret                # Выталкивает возвращаемый адрес с вершины стека и перепрыгивает к нему 

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

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

Как правило, эти кадры стека находятся в единой непрерывной области памяти, а структура данных выглядит примерно так:

Если бы мы хотели обойти асинхронный, а не нормальный стектрейс, то все равно начали бы путь с обычных кадров стека, как и в нормальном стектрейсе. Корутина может вызывать нормальные функции, и нам требуется включить кадры с этими нормальными функциями в стектрейс. Правда, как только мы дойдем до кадра, соответствующего самой верхней корутине (в данном случае coro_function_1) мы не собираемся переходить по ссылке 'nextFrame' к методу coroutine_handle::resume, как это бы произошло при обходе нормального стека. Вместо этого нам нужна ссылка на ожидающую корутину. В этот момент истории нормального и асинхронного стектрейсов расходятся. Проход по асинхронному стектрейсу требует ответить на несколько вопросов:

  • Как определить, какие из кадров стека соответствуют асинхронным кадрам?

  • Как найти адрес следующего асинхронного кадра?

  • Как и где нам выделять пространство для хранения данных, относящихся к асинхронным кадрам?

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

В чем «стеки» корутин отличаются от нормальных стеков?

Когда вы вызываете корутину на C++, программа выделяет хранилище для кадра корутины. Как правило, пространство для этой цели мы получаем из кучи, но в некоторых случаях компилятор вправе и ничего не брать из кучи, обойдясь оптимизациями – например, встраивая операцию выделения в кадр вызывающей стороны.

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

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

Тип промиса определяется в зависимости от сигнатуры функции корутины, и в большинстве случаев тип корутины зависит исключительно от ее возвращаемого типа. Благодаря этому корутины, возвращающие заданный тип (напр., folly::coro::Task<T>) могут хранить на каждый кадр корутины дополнительную информацию: для этого члены данных добавляются к типу промиса.

При clang-подобной реализации компоновка кадра корутины для заданной функции корутины выглядит примерно так:

struct __foo_frame {
  using promise_type = typename std::coroutine_traits<Ret, Arg1, Arg2>::promise_type;
  void(*resumeFn)(void*);  // coroutine_handle::resume() function-pointer
  void(*destroyFn)(void*); // coroutine_handle::destroy() function-pointer
  promise_type promise;    // объект промиса корутины
  int suspendPoint;        // отслеживает, в какой точке была приостановлена работа корутины
  char extra[458];         // дополнительное пространство для хранения локальных переменных, параметров,
                           // временных файлов, утекших регистров, т.д.
}; 

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

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

Следовательно, когда корутина активна и вызвала другую функцию, компоновка памяти будет выглядеть примерно так:

В особенности отметим, что обход асинхронной версии стека приводит к тому, что нам приходится отклониться в память кучи, последовав по framePointer в coro_function_1. В отличие от указателя на актуальный кадр стека, который, как обычно предполагается, должен храниться в регистре rbp, не предусмотрено стандартного местоположения для указателя, который направлен на кадр корутины. Это по-своему сказывается на навигации от кадра стека к данным соответствующего асинхронного кадра.

Сцепление асинхронных кадров стека

Чтобы иметь возможность составить стектрейс, который представлял бы цепочку асинхронных вызовов, а не цепочку нормальных синхронных вызовов, мы должны быть в состоянии обойти цепочку кадров корутины, записывая возвращаемый адрес/адрес продолжения каждой корутины по пути.

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

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

Технически, содержится достаточно информации в типе folly::coro::TaskPromise, относящемся к задаче folly::coro::Task, ее достаточно, чтобы перейти к следующему кадру, поскольку в этом типе уже хранится coroutine_handle для продолжения, а кадр корутины для этого продолжения уже кодирует информацию о том, какая точка приостановки работы какой корутины записаны в членах resumeFn и suspendPoint. Однако, мы сталкиваемся с определенными проблемами, если попытаемся использовать эту информацию напрямую при обходе асинхронного стектрейса.

Представление цепочки асинхронных кадров стека

Если у нас есть указатель на кадр корутины, сохраненный в coroutine_handle, то, теоретически, зная, какова компоновка объекта промиса, мы можем вычислить адрес члена 'продолжение' в составе промиса, где содержится адрес следующего кадра корутины – для этого просто прибавим постоянное значение смещения к указателю на кадр корутины.

Один из подходов, который нам может потребоваться – такой, чтобы промисы всех типов хранили coroutine_handle с продолжением в качестве первого члена данных:

template<typename T>
struct TaskPromise {
  std::coroutine_handle<void> continuation;
  Try<T> result;
  ...
};
 
struct __some_coroutine_frame {
  void(*resumeFn)(void*);
  void(*destroyFn)(void*);
  TaskPromise<int> promise;
  int suspendPoint;
};

Затем, даже если конкретный тип промиса нам не известен, мы все равно будем знать, что его первый член данных – это coroutine_handle, и что промис ставится сразу же после двух указателей функций. С точки зрения отладчика, обходящего асинхронный стектрейс, можно предположить, что кадры корутин выглядят так:

struct coroutine_frame {
  void(*resumeFn)(void*);
  void(*destroyFn)(void*);
  coroutine_frame* nextFrame;
};

К сожалению, этот подход сбоит, когда тип промиса чрезмерно выровнен (overaligned)  (то есть, его выравнивание превышает 2 указателя: 32 байт или более на 64-разрядных платформах). Такое может произойти, если тип folly::coro::Task<T> инстанцирован для чрезмерно выровненного типа, например, T, тогда матричный тип оптимизируется для использования с инструкциями SIMD.

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

Теоретически, можно было бы посмотреть значения указателей resumeFn/destroyFn, чтобы выяснить тип промиса, соответствующий телу корутины в таблице трансляции. Но это либо потребовало бы либо обращаться к отладочной информации, либо модифицировать компилятор, так, чтобы он кодировал эту информацию в составе бинарного файла. Невозможно рассчитывать, что отладочная информация всегда будет доступна, а модификация компилятора – это гораздо более крупный проект. Возможны и другие подходы, например, изменить интерфейс ABI кадров корутин, чтобы заполнение не делалось, но для этого также потребуется вносить изменения в компилятор, и получившаяся реализация будет зависеть от компилятора.

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

namespace folly {
  struct AsyncStackFrame {
    AsyncStackFrame* parentFrame;
    // другие члены...
  };
}

И этот код можно добавить в качестве члена к объектам промисов, связанным с корутинами:

namespace folly::coro {
  class TaskPromiseBase {
    ...
  private:
    std::coroutine_handle<> continuation_;
    AsyncStackFrame asyncFrame_;
    ...
  };

Всякий раз, запуская дочернюю корутину при помощи co_awaiting, мы можем перехватить AsyncStackFrame этой дочерней корутины так, чтобы член parentFrame указывал на объект AsyncStackFrame родительской корутины.

При использовании отдельной структуры данных мы приобретаем значительную гибкость в том, как нам удается представлять асинхронные стектрейсы. Такой подход изолирует структуры данных от любых зависимостей, которые могут быть связаны с внутренним устройством компилятора, а в будущем также позволяет нам многократно использовать объекты AsyncStackFrame в асинхронных операциях, не связанных с корутинами. Это обходится нам сравнительно небольшими издержками, касающимися памяти и времени выполнения, поскольку теперь нам фактически приходится хранить и поддерживать два указателя на родительскую корутину. В будущем это решение может быть пересмотрено, если нам понадобится выжать из программы дополнительную производительность – для этого нам потребуется внести в компилятор изменения, которые упоминались ранее.

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

Источник: https://habr.com/ru/company/piter/blog/649725/


Интересные статьи

Интересные статьи

 В нашем первом посте для Habr мы рассказывали про сотрудника, который в один момент радикально изменил карьеру – ушел из пилотов вертолетов в тестировщики. Отклик был очень хорошим, мы продолжил...
Цель статьи, – показать примеры управления реализацией стратегии с помощью корпоративной единой информационной площадки на доступном инструменте, - Битрикс24. В статье на простом языке обсуждаются воз...
Привет, Хабр! Меня зовут Глеб Евстропов, я работаю в Яндексе руководителем сервиса поисковых подсказок, а ещё читаю продвинутую версию курса по алгоритмам и структурам да...
Когда я десяток лет назад переехал в США для работы в Facebook, то понятия не имел, хорошим или плохим был оффер. Я даже не торговался и согласился на ту сумму, которую мне предложили. От...
Привет, Хабр! Я работаю в команде Антиспама Почты Mail.ru. В этой статье я бы хотел рассказать про наш опыт запуска сервиса с пропускной способностью около 3 миллионов запросов в минуту...