[Перевод] Механизм перезапускаемых последовательностей (Rseq) при работе с TCMalloc28.01.2024 11:15

❯ Кэши для отдельных ядер процессора

В TCMalloc кэши для отдельных ядер процессора реализуются при помощи перезапускаемых последовательностей (man rseq(2)) под Linux. Эту возможность ядра разработали Пол Тёрнер и Эндрю Хантер из Google, а также Мэтью Дезнойерс из EfficiOS. При помощи перезапускаемых последовательностей можно вплоть до завершения выполнять область памяти (атомарно, относительно других потоков, выполняющихся на том же ядре процессора), либо выходить из этого процесса, если ядро прервёт этот процесс, например, вытеснив его или прервавшись на обработку сигнала.

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

В таком случае приходится решить несколько проблем, возникающих при реализации:

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

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

❯ Как устроен TcmallocSlab

Работая с областями, закреплёнными за процессором, мы выделяем массив N TcmallocSlab::Slabs. Для всех операций мы индексируем этот массив идентификаторами логических ядер процессора.

У каждого slab-блока есть заголовочная область, в которой содержатся управляющие данные (один 8-байтовый заголовок на класс размеров). Этими данными индексируется оставшаяся часть slab-блока, где содержатся указатели на свободные перечисленные объекты.

Вот как эту логику можно представить в коде C++:

struct Slabs {
  std::atomic header[NumClasses];
  void* mem[((1ul << Shift) - sizeof(header)) / sizeof(void*)];
};

// Заголовок Slab-блока (упакован, атомарно обновляется, 64-разрядный).
// Все значения {begin, current, end} – это смещения указателей от того места, где начинается область, 
// закреплённая за процессором. Массив ячеек содержится в [begin, end), а занятые ячейки находятся в
// [begin, current).
struct Header {
  // Конец смещения той области, ячейки которой в настоящий момент заняты.
  uint16_t current;
  // Копирование окончания. Обновляется через Shrink/Grow, но не затирается через Drain.
  uint16_t end_copy;
  // Обновление блокировок начинается и заканчивается 32-разрядной записью.

  // Начальное смещение массива ячеек для данного класса размеров.
  uint16_t begin;
  // Конечное смещение массива ячеек для данного класса размеров.
  uint16_t end;

  // Drain при помощи блокировки останавливает конкурентные мутации в заголовке.
  // При блокировке устанавливаем начало в 0xffff и конец в 0, из-за этого операции Push и Pop не проходят,
  // независимо от текущего значения.
  bool IsLocked() const;
  void Lock();
};

Атомарный заголовок header позволяет считывать состояние ядра (в частности, для целей телеметрии), не вызывая при этом неопределённого поведения.

Поля в Header индексируются с шагом sizeof(void*) внутрь slab-блока. При значении Shift=18, действующем по умолчанию, это позволяет нам кэшировать почти по 32K объектов на ядро ЦП. Сейчас ведётся работа, чтобы закодировать Slabs* и Shift в рамках одного указателя — в таком случае их можно будет динамически обновлять во время выполнения.

Мы выделили мощности для объектов end-begin под класс заданного размера. begin выбран путём статического сегментирования во время инициализации. end выбирается динамически на более высоком уровне (в tcmalloc::CPUCache), вот так:

• Избегаем попадания в область begin классов следующего размера;
• Балансируем мощность кэшированных объектов между классами разных размеров, в соответствии с заданным байтовым пределом.

❯ Операция: выделение

В качестве первой операции рассмотрим выделение памяти (аллокацию). При этой операции необходимо прочитать указатель, расположенный по индексу current-1, возвратить этот объект и уменьшить current на единицу. Уменьшение current на единицу — это операция фиксации (commit).

In pseudo-C++, this looks like:
void* TcmallocSlab_Pop(
    void *slabs,
    size_t size_class,
    UnderflowHandler underflow_handler) {
  // Расширенный макрос START_RSEQ...
restart:
  __rseq_abi.rseq_cs = &__rseq_cs_TcmallocSlab_Pop;
start:
  // Конкретная последовательность
  uint64_t cpu_id = __rseq_abi.cpu_id;
  Header* hdr = &slabs[cpu_id].header[size_class];
  uint64_t current = hdr->current;
  uint64_t begin = hdr->begin;
  if (ABSL_PREDICT_FALSE(current <= begin)) {
    goto underflow;
  }

  void* next = *(&slabs[cpu_id] + current * sizeof(void*) - 2 * sizeof(void*))
  prefetcht0(next);

  void* ret = *(&slabs[cpu_id] + current * sizeof(void*) - sizeof(void*));
  --current;
  hdr->current = current;
commit:
  return ret;
underflow:
  return underflow_handler(cpu_id, size_class);
}

// Реализовано на ассемблере, но только в демонстрационных целях.
ABSL_CONST_INIT kernel_rseq_cs __rseq_cs_TcmallocSlab_Pop = {
  .version = 0,
  .flags = 0,
  .start_ip = &&start,
  .post_commit_offset = &&commit - &&start,
  .abort_ip = &&abort,
};

__rseq_cs_TcmallocSlab_Pop — это структура данных, предназначенная только для чтения. В ней содержатся метаданные о данной конкретной перезапускаемой последовательности. Когда ядро вытесняет поток, выполняемый в настоящий момент, оно проверяет эту структуру данных. Если актуальный указатель на инструкцию находится между [start, commit), то ядро возвращает управление в указанный заголовок перезапуска, соответствующий конкретной последовательности, это происходит при abort.

Поскольку следующий объект часто выделяется вскоре после актуального объекта, на пути выделения памяти предварительно выбирается тот объект, на который направлен указатель. Чтобы избежать такой предвыборки по случайному адресу, мы заполняем slabs[cpu][begin] для каждого ядра ЦП/размера классов указателем на самого себя.

Эта последовательность завершается одиночной операцией сохранения в hdr->current. Если произошла миграция или прерывание по какой-то другой причине, то перезапускаются подготовительные шаги, поскольку значения cpu_id,  current,  begin могли успеть измениться.

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

❯ Обработка перезапуска

Метка abort отличается от restart. API rseq предоставляется ядром (см. ниже) требует «сигнатуру» (как правило, это заведомо недействительный код операции) в 4 байт до того, как начнёт выполняться обработчик перезапуска. Так мы делаем небольшой трамплин — правильно оформленный — при помощи которого можем вернуться обратно к restart.

На ассемблере для архитектуры x86 код выглядит так:

  // Кодируем nop с сигнатурой RSEQ_SIGNATURE в соответствующем отступе.
  .byte 0x0f, 0x1f, 0x05
  .long RSEQ_SIGNATURE
  .local TcmallocSlab_Push_trampoline
  .type TcmallocSlab_Push_trampoline,@function
  TcmallocSlab_Push_trampoline:
abort:
  jmp restart

Так гарантируется, что 4 байта, предшествующие abort, совпадают с сигнатурой, которая была сконфигурирована для работы с системным вызовом up rseq.

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

❯ Операция деаллокации

При деаллокации (операция, обратная выделению памяти) используется два акта сохранения — при первом мы сохраняем «развыделенный» объект, а при втором обновляем current. Такая практика, тем не менее, совместима с описанной техникой применения перезапускаемых последовательностей, поскольку у нас всё равно остаётся единственный шаг фиксации, которого нам достаточно для обновления current. Любые вытесняемые последовательности будут затирать развыделенный объект до тех пор, пока не найдётся успешная последовательность, которая зафиксирует этот объект, обновив current.

int TcmallocSlab_Push(
    void *slab,
    size_t size_class,
    void* item,
    OverflowHandler overflow_handler) {
  // Расширенный макрос START_RSEQ...
restart:
  __rseq_abi.rseq_cs = &__rseq_cs_TcmallocSlab_Push;
start:
  // Актуальная последовательность
  uint64_t cpu_id = __rseq_abi.cpu_id;
  Header* hdr = &slabs[cpu_id].header[size_class];
  uint64_t current = hdr->current;
  uint64_t end = hdr->end;
  if (ABSL_PREDICT_FALSE(current >= end)) {
    goto overflow;
  }

  *(&slabs[cpu_id] + current * sizeof(void*) - sizeof(void*)) = item;
  current++;
  hdr->current = current;
commit:
  return;
overflow:
  return overflow_handler(cpu_id, size_class, item);
}

❯ Инициализация Slab-блока

Чтобы обойтись меньшим количеством метаданных, мы лениво инициализируем slab-блоки. При этом мы рассчитываем, что ядро предоставит нам заполненные нулями страницы, поступающие от вызова mmap, и так мы получим память, в которой станут храниться метаданные slab-блока.

В таком случае заголовок Header каждого такого блока будет инициализирован в current = begin = end = 0. Исходная операция push или pop спровоцирует развитие ситуации по пути переполнения или недозаполнения (соответственно), и так мы сможем заполнить эти значения.

❯ Более сложные операции: работа с пакетами

При недозаполнении или переполнении кэша мы заполняем или удаляем целый пакет объектов, полученных их внутренних кэшей. Так можно самортизировать часть логики, требуемой на приобретение блокировок или анна обслуживание этих кэшей. Используя примерно такой же подход, как и показанный выше в случае с push и pop, мы читаем/записываем пакет из N элементов и обновляем current, чтобы зафиксировать эту операцию.

❯ API ядра и его реализация

В этом разделе кратко рассказано об API rseq, предоставляемом ядром (этот API не слишком хорошо документирован), а также показано в коде, как именно он реализован.

Системный вызов rseq реализован при помощи sys_rseq. Он начинается с обработки того случая, в котором поток пытается разрегистрироваться. Это реализуется так: очищаем информацию о rseq из структуры task_struct для потока, действующего на актуальном ядре ЦП. Затем программа переходит к возврату ошибки, если поток уже зарегистрирован для работы с rseq. Затем мы валидируем и сохраняем ввод, полученный от пользователя. Далее для потока устанавливается флаг TIF_NOTIFY_RESUME.

❯ Операции перезапуска

Среди прочего, пользовательский ввод, подаваемый системному вызову rseq, используется rseq_ip_fixup, чтобы определить, находимся ли мы в критической секции и, если так — перезапуститься в abort-точке. Эту функцию вызывает __rseq_handle_notify_resume, в документации по которому сказано, что его необходимо вытеснять после вытеснения или после прихода сигнала, но до возврата пользователю. Эта функция, в свою очередь, вызывается rseq_handle_notify_resume –это простая обёртка, к которой мы прибегаем, если в данном потоке не активирована возможность работы с rseq.

Вот один из путей, приводящий нас к данной ситуации, если мы работаем с архитектурой x86:

Итак, узким местом является код возврата в пользовательское пространство. Вот несколько заметок о том, как может варьироваться логика перезапуска в зависимости от конкретного пользовательского ввода:

• rseq_ip_fixup всякий раз вызывает rseq_get_rseq_cs. Таким образом, он читает указатель на struct rseq_cs, а затем окольно выходит через него, освободившись от всей пользовательской памяти. При этом данный код проверяет наличие недоспустимых случаев (и такой случай вызывает ошибку сегментирования пользовательского процесса), после чего производится валидация IP-сигнатуры аварийного завершения функции, о чём мы поговорим ниже.
• Проверка сигнатуры: из кода, ссылка на который дана выше, вытекает следующее требование: перед обработчиком аварийного завершения, указанным в rseq_cs::abort_ip, должно идти 32-разрядное волшебное число,  сопоставляемое с исходно предоставленным числом. Далее оно сохраняется при помощи системного вызова rseq.
  Это делается для того, чтобы превратить случаи переполнения буфера в выполнение произвольного кода. Если злоумышленник может записывать информацию в памяти, то он сможет контролировать rseq_cs::abort_ip. Ситуация напоминает следующую: представьте, что мы записываем в память инструкцию перехода, которая, принципе, нарушает механизмы защиты W^X. Вместо этого ядро заставляет вызывающую сторону предварительно зарегистрировать волшебное значение из выполняемой памяти, которое предполагается запустить. При этом мы исходим из того, что злоумышленник вряд ли сможет отыскать в исполняемой памяти другие подходящие для этой цели «рычаги», которым предшествует это значение.

Кроме того, стоит отметить, что поступление сигналов и вытеснение всегда приводит к стиранию rseq::rseq_cs::ptr64 из пользовательского пространства на этапе выполнения кода выхода, за исключением случаев, когда из-за какого-то сбоя происходит ошибка сегментирования.

❯ Идентификаторы ядер ЦП

Кроме того,  rseq.c отвечает за запись ID ядер ЦП в память пользовательского пространства.
В пользовательском пространстве есть два поля, в которые заносится эта информация: rseq: cpu_id_start и rseq: cpu_id. Разница между ними заключается в том, что cpu_id_start всегда находится в диапазоне, тогда как cpu_id может содержать значения ошибок. Оба этих поля ядро предоставляет, чтобы поддержать вычисление значений, выводимых из ID ядра ЦП. Эта задача выполняется до входа в критическую секцию. Это можно было бы сделать при помощи всего одного ID ядра ЦП, но в таком случае потребовалось бы запрограммировать ещё одну ветку кода, которая позволяла бы отличать состояние «не инициализировано» от «ID ЦП изменился после того, как был выбран». С другой стороны, если (как и при работе с tcmalloc) ID ядра ЦП выбирается только в критической секции, то вам понадобится всего одно поле, так как и ветка в коде одна: «прошла ли инициализация». Не существует такого явления как несовпадение ядер ЦП, так как при изменении ID ядра ЦП вы просто перезапускаетесь.

Два поля для ID ядер ЦП поддерживаются таким образом:

• В каждое из полей rseq_update_cpu_id записывается ID ядра ЦП. Для этого выполняется вызов __rseq_handle_notify_resume, о чём шла речь выше.
• rseq_reset_rseq_cpu_id устанавливает поле cpu_id_start в ноль, а поле cpu_id в to RSEQ_CPU_ID_UNINITIALIZED (это значение, находящееся за пределами диапазона). Вызов производится на пути разрегистрации, о чём также шла речь выше.

❯ Операции между ядрами ЦП

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

Операции на нескольких ядрах ЦП выполняются при содействии операционной системы (обёртываются в tcmalloc::tcmalloc_internal::subtle::percpu::FenceCpu) для прерывания любых действующих перезапускаемых последовательностей на удалённом ядре. Когда управление возвращается потоку, работающему на данном ядре, есть гарантия, что либо завершилась та перезапускаемая последовательность, что выполнялась на этом ядре, либо что перезапускаемая последовательность была вытеснена.

Вытеснение и «блокировки» (TcmallocSlab::Header::Lock) используются для того, чтобы, в пределах конкретного периода все попытки пойти по быстрому пути не удавались. В такой ситуации кэш одновременно «полон» и «пуст», поэтому все операции вставки и удаления идут по медленному пути. В отличие от случая, когда sched_setaffinity обеспечивает работу на удалённом ядре, вышеописанный подход позволяет выполнять более длительные операции: например, извлечение элементов из кэша и вставка их в TransferCache в рамках Drain, при этом всё равно поддерживая корректность.

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

Например, в конце Drain, мы:

• Сохраняем hdr.current. hdr.begin = 0xFFFF и hdr.end = 0x0, гарантируя таким образом, что операции вставки и удаления и далее будут заканчиваться неудачно.
• FenceCpu
• Сохраняем в hdr.begin и hdr.end подходящие для них значения.

Tакая последовательность гарантирует, что поток, выполняемый на удалённом ядре, увидит только:

• hdr.current = X; hdr.begin = 0xFFFF; hdr.end = 0x0
• hdr.current = Y; hdr.begin = 0xFFFF; hdr.end = 0x0
• hdr.current = Y; hdr.begin = Y; hdr.end = Y

FenceCpu гарантирует, что после завершения этой операции ни один поток больше не сможет видеть current=X.

Если мы выполнили всего одну операцию сохранения или пропускали вставную операцию установки барьера, то поток на удалённом ядре потенциально может увидеть hdr.begin = Y < hdr.current = X и попытаться удалить элемент из кэша. Такая неисправность может приводить к повреждению данных, поскольку элемент уже был «развыделен» в TransferCache. В результате происходит ошибка двойного высвобождения.

Возможно, захочется почитать и это:

© Habrahabr.ru