CS Notes

tlb

8 min read

TLB и стоимость трансляции

Предпосылки: трансляция и изоляция (page table, PGD/PUD/PMD/PTE, CR3, MMU), иерархия кешей (L1/L2/L3, hit/miss), когерентность кешей (MESI).

← Трансляция и изоляция | Page fault и отложенные механизмы →

Четыре чтения из RAM на каждую трансляцию, 240–400 нс на одно обращение к памяти. Казалось бы, трансляция — это одно сложение с CR3, быстро и бесплатно. На деле адрес проходит через четырёхэтажное дерево, и каждый этаж — отдельный поход в RAM. Типичная программа делает сотни миллионов обращений в секунду. 400 нс на каждое — это замедление процессора в десятки раз. Но реально работающие программы не тормозят: между процессором и page table стоит промежуточный уровень, который прячет большую часть походов.

TLB: кеш трансляций

Четыре обращения к RAM на каждую трансляцию — неприемлемо. Ответ — тот же, что для любой дорогой операции в CPU: кеш. TLB (Translation Lookaside Buffer, буфер ассоциативной трансляции) — аппаратный кеш внутри MMU, хранящий результаты недавних трансляций: пары «номер виртуальной страницы → номер физического фрейма + атрибуты».

Параллель с L3 для данных прямая:

Обращение к данным:          Трансляция адреса:
  |                             |
  v                             v
+----------+                 +----------+
| L1 data  |  1 такт         | L1 TLB   |  1 такт
+----------+                 +----------+
     | miss                       | miss
     v                            v
+----------+                 +----------+
| L2       |  ~10 тактов     | L2 TLB   |  ~8 тактов
+----------+                 +----------+
     | miss                       | miss
     v                            v
+----------+                 +----------+
| L3       |  ~40 тактов     | Page     |  4 × RAM чтения,
+----------+                 | walk     |  10-400 нс
     | miss                 +----------+
     v                            |
+----------+                      | (промежуточные PGD/PUD/PMD
|  RAM     |  ~60-100 нс          |  обычно в L1/L2 data cache)
+----------+                      v
                              физический фрейм

Две кешовые иерархии работают параллельно: одна для данных (что прочесть из RAM), другая для трансляций (по какому физическому адресу читать). Каждая инструкция load/store проходит через обе.

TLB — полностью ассоциативный кеш (fully associative). В обычных кешах (L1, L2) адрес определяет позицию в кеше — конкурируют только линии с одинаковым индексом. В TLB каждая запись может хранить любую трансляцию, и при поиске все записи сравниваются параллельно. Это возможно, потому что TLB маленький: L1 DTLB — десятки записей, L2 TLB — порядка тысячи (для сравнения: L1 кеш данных — тысячи кеш-линий). Малый размер позволяет параллельное сравнение за один такт.

Типовые параметры для процессора Intel Core (Skylake-архитектура, числа зависят от микроархитектуры и конкретной модели):

  • L1 DTLB (data TLB): 64 записи для 4 КБ страниц, 32 записи для 2 МБ huge pages
  • L2 TLB (unified): 1536 записей
  • TLB hit: ~1 такт (~0.3 нс при 3 ГГц)
  • TLB miss → page walk (полный обход 4 уровней): 10–400 нс в зависимости от того, попадут ли промежуточные таблицы в L1/L2 data cache

Hit rate TLB при типичной нагрузке — 99%+. 64 записи L1 DTLB покрывают 64 × 4 КБ = 256 КБ. С L2 TLB на 1536 записей — 6 МБ. Для программы с рабочим набором до 6 МБ практически каждое обращение попадает в TLB.

Промежуточные таблицы (PGD, PUD, PMD) — обычные страницы в RAM, и они попадают в L1/L2 кеш данных процессора. Если процесс обращается к соседним виртуальным адресам (пространственная локальность), все четыре уровня таблиц уже лежат в кеше, и page walk обходится в 10–20 нс вместо 400 нс. Именно поэтому последовательный обход массива почти не страдает от TLB-промахов: промахи есть, но page walk быстрый. Случайный доступ к памяти — другое дело: каждое обращение может затронуть другую ветвь дерева, кеш не помогает, и page walk стоит полные 100+ нс.

Когда рабочий набор вырастает — hit rate падает, и программа начинает тратить десятки наносекунд на каждый page walk. Базы данных с рабочим набором в сотни гигабайт теряют 10–20% производительности на TLB-промахах. Одна из причин использовать huge pages (2 МБ): одна запись TLB покрывает не 4 КБ, а 2 МБ — в 512 раз больше. 64 записи L1 DTLB для huge pages покрывают 64 × 2 МБ = 128 МБ вместо 256 КБ. PostgreSQL поддерживает huge pages через параметр huge_pages = on, и для shared_buffers в 8 ГБ это снижает TLB-промахи на порядок.

Переключение контекста и PCID

Запись нового значения в CR3 при переключении контекста инвалидирует TLB — все записи становятся невалидными. Это логично: трансляции старого процесса не имеют смысла для нового. Но цена высока: после переключения первые десятки обращений к памяти идут через полный page walk. На машине, переключающей контекст каждые ~4 мс (типичный квант планировщика Linux), TLB-промахи после переключения могут составлять 5–10% от всех обращений.

Процессоры смягчают это через PCID (Process Context ID) — 12-битный тег, позволяющий хранить в TLB трансляции нескольких процессов одновременно (аппаратно до 4096; Linux использует небольшой пул на каждое ядро). Каждому процессу назначается PCID из пула, и записи TLB помечаются этим тегом. С PCID переключение контекста не сбрасывает TLB целиком — при возврате к процессу его трансляции всё ещё в TLB, «холодный старт» после переключения исчезает.

Аппаратная поддержка PCID появилась ещё в Westmere (2010), но Linux долго не использовал её из-за сложности интеграции с KPTI (митигация Meltdown). Поддержку PCID в ядре включили начиная с версии 4.14 (2017). До этого каждое переключение контекста полностью сбрасывало TLB. С PCID переключение стало дешевле на 1–2% — что существенно для серверов с сотнями процессов и частыми переключениями.

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

TLB shootdown: инвалидация на других ядрах

На многоядерном CPU у каждого ядра свой TLB. Когда ядро операционной системы изменяет page table — munmap() освобождает регион, mprotect() меняет права, copy-on-write ломает разделение фрейма — TLB на других ядрах, исполняющих потоки того же процесса (несколько потоков одного процесса делят адресное пространство и могут одновременно исполняться на разных ядрах), продолжает хранить старые трансляции. Поток на ядре 3 может читать память, которую ядро 0 уже пометило как недоступную. PCID здесь не помогает: проблема не в переключении контекста, а в изменении page table текущего процесса, трансляции которого валидно лежат на нескольких ядрах одновременно.

Ядро ОС решает это через TLB shootdown: отправляет IPI (Inter-Processor Interrupt, межпроцессорное прерывание) каждому ядру, использующему это адресное пространство. Получившее IPI ядро выполняет инструкцию INVLPG (invalidate page — сбросить одну запись TLB) или полный flush, в зависимости от объёма изменений. Горячий путь в ядре Linux — функция flush_tlb_mm_range().

Логика та же, что в протоколе MESI (Modified, Exclusive, Shared, Invalid) для обычных кешей: когда одно ядро меняет разделяемые данные, остальные должны узнать об этом и пометить свои копии как невалидные. MESI инвалидирует кеш-линии при изменении данных, shootdown инвалидирует TLB-записи при изменении трансляций. Разница в реализации: MESI встроен в аппаратный протокол межъядерной коммуникации, а shootdown — программная процедура, которую инициирует ядро ОС.

Стоимость TLB shootdown — 1–10 мкс на каждое ядро-получатель: IPI пересекает interconnect, прерывает исполнение, процессор выполняет инвалидацию и возвращается к работе. На 128-ядерном сервере shootdown может затронуть десятки ядер одновременно.

Сценарий: munmap() тормозит соседние ядра

Поток-компилятор JIT (Just-In-Time, например V8 в Node.js или HotSpot JVM) на ядре 0 выделил 16 МБ через mmap(), скомпилировал туда машинный код, отработал — и вызвал munmap(), чтобы вернуть память ядру. Пока поток работал, ядро планировщика раскинуло другие потоки того же процесса по ядрам 1, 2, 3, …, 15. Каждое из этих ядер уже загрузило в свой TLB трансляции, включающие те страницы, которые munmap() сейчас удаляет из page table.

Ядро ОС выполняет шаги:

  1. Снимает VMA, покрывающий 16 МБ, из списка регионов процесса.
  2. Для каждой страницы диапазона очищает PTE в page table.
  3. Читает маску CPU, на которых исполнялись потоки этого процесса с момента последнего shootdown.
  4. Отправляет IPI всем этим ядрам. Ядра 1–15 получают прерывание, прерывают текущую работу, исполняют INVLPG для каждой страницы диапазона (или полный TLB flush, если страниц слишком много), возвращаются к работе.
  5. Ждёт, пока все ядра подтвердят выполнение.

Пока IPI не подтверждены, ядро 0 не может продолжить — оно должно гарантировать, что ни одно другое ядро не прочитает удалённый фрейм по устаревшей TLB-записи. Типовая стоимость — 5 мкс на IPI × 15 ядер = 75 мкс общего времени ответа. Для потока, который сам делает миллионы операций в секунду, это пауза в десятки микросекунд без видимой причины, с точки зрения profiler’а.

Приложения, активно работающие с mmap()/munmap() — JIT-компиляторы (V8, HotSpot JVM, LuaJIT) постоянно выделяют и освобождают регионы под скомпилированный код — получают shootdown-нагрузку пропорционально частоте ремаппинга. В Linux для частичного обхода есть MADV_FREE (ядро может оставить страницы в памяти и освободить их только под давлением) и lazy TLB modes (ядро откладывает дорогой flush/переключение TLB для ядер, реально не использующих это адресное пространство), но полностью shootdown не убирается.

Итог

TLB превращает четыре чтения из RAM на каждое обращение к памяти в один такт — и делает многоуровневую page table практичной. Но как любой кеш с когерентностью, TLB платит за это моментами инвалидации: PCID убирает цену переключения контекста, shootdown убирает цену изменения page table — и тот же shootdown становится видимой стоимостью на машинах с десятками ядер и активным ремаппингом памяти. Когда профилировщик показывает «провалы» на уровне микросекунд без вызовов в ядре, стоит посмотреть на соседние ядра: возможно, один из них делает munmap(), а ваш поток его ждёт.

Осталась третья ветка трансляции — page fault, когда MMU не может завершить трансляцию и передаёт управление ядру. Это не только обработка ошибок: на page fault построены три отложенные оптимизации, которые делают современный Linux возможным.

Sources

← Трансляция и изоляция | Page fault и отложенные механизмы →

Graph View

Backlinks