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

Откуда взялась проблема

В прошлой главе (paging) мы научились бить память на страницы и держать таблицу страниц — список, который говорит: «виртуальная страница номер N живёт в физическом кадре номер M». Удобно, гибко, фрагментации почти нет. Но за эту красоту мы платим.

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

1. Сходить в память за нужной записью таблицы страниц (PTE — page table entry).
2. Достать оттуда номер кадра.
3. Только теперь сходить в память за самими данными.

Там, где раньше был один поход в память, теперь их два, а с многоуровневыми таблицами (глава компактные таблицы) и больше. Обращения к памяти — самая частая операция программы, так что наивный paging замедлил бы всё в разы.

  Наивный paging: каждое чтение данных = 2 похода в RAM
 
  CPU хочет прочитать addr
        │
        ▼
  ┌───────────────┐   поход #1 (медленно, ~100 нс)
  │ читаем PTE из  │◄──────────────── RAM
  │ таблицы в RAM  │
  └───────┬───────┘
          │ узнали номер кадра
          ▼
  ┌───────────────┐   поход #2 (медленно, ~100 нс)
  │ читаем данные  │◄──────────────── RAM
  └───────────────┘
 
  Итог: вдвое медленнее.

Нужно как-то избавиться от похода #1 в большинстве случаев. Для этого есть TLB.

Что такое TLB

TLB (Translation Lookaside Buffer, «буфер трансляции») — это маленький быстрый кэш прямо внутри MMU (того блока процессора, что занимается трансляцией адресов). В нём хранятся недавно использованные переводы «виртуальная страница → физический кадр».

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

Важно: TLB кэширует не данные, а трансляции. Одна строка TLB примерно говорит: «страница 0x5 → кадр 0x91, и вот её права доступа».

  Где живёт TLB
 
  ┌──────────────────────── CPU ────────────────────────┐
  │                                                      │
  │   ядро          ┌─────────── MMU ───────────┐       │
  │  (исполняет     │                            │       │
  │   инструкции) ─►│   ┌────────────────────┐   │       │
  │                 │   │        TLB         │   │       │
  │                 │   │  (десятки строк,   │   │       │
  │                 │   │   доступ ~1 такт)  │   │       │
  │                 │   └────────────────────┘   │       │
  │                 └────────────┬───────────────┘       │
  └──────────────────────────────┼──────────────────────┘
                                 │ только при промахе
                                 ▼
                       ┌──────────────────┐
                       │  таблица страниц │   (медленно)
                       │      в RAM       │
                       └──────────────────┘

Hit и miss: две ветви жизни

У любого кэша есть два исхода обращения: попадание (hit) — нужное нашлось, и промах (miss) — не нашлось. Разберём оба для TLB.

При обращении к памяти MMU сначала берёт номер виртуальной страницы (VPN — virtual page number) и ищет его среди строк TLB.

• TLB hit. Строка нашлась. Номер кадра берём прямо из TLB — это почти бесплатно, ни одного лишнего похода в RAM. Сразу читаем данные. Это «горячий путь», и мы хотим, чтобы он случался почти всегда.
• TLB miss. Строки нет. Придётся идти в таблицу страниц в памяти (медленный поход #1), достать PTE, записать эту трансляцию в TLB на будущее и повторить обращение — теперь уже как hit.

  Путь доступа к памяти с TLB
 
            CPU выдаёт виртуальный адрес
                       │
              извлекаем VPN (номер страницы)
                       │
                       ▼
              ┌──────────────────┐
              │ VPN есть в TLB ?  │
              └───────┬──────┬────┘
                  ДА  │      │  НЕТ
              (TLB hit)      (TLB miss)
                  │              │
                  ▼              ▼
         кадр берём из    идём в таблицу страниц
         TLB, мгновенно   в RAM (медленно),
                  │        достаём PTE,
                  │        кладём в TLB,
                  │        повторяем обращение
                  │              │
                  └──────┬───────┘
                         ▼
                 читаем данные по
                 физическому адресу

Стоимость двух исходов несравнима:

Цель — максимизировать долю попаданий (hit rate). Посчитаем, насколько она важна. Пусть обращение к RAM стоит 100 нс, поиск в TLB почти бесплатен, а промах требует прочитать PTE из RAM, то есть ещё 100 нс:

  среднее время доступа = 100 нс + (доля промахов) × 100 нс
 
  hit rate 99 %:  100 + 0,01 × 100 = 101 нс   (paging почти незаметен)
  hit rate 90 %:  100 + 0,10 × 100 = 110 нс   (на 10 % медленнее)
 
  с 4-уровневой таблицей промах = 4 чтения = 400 нс:
  hit rate 99 %:  100 + 0,01 × 400 = 104 нс
  hit rate 90 %:  100 + 0,10 × 400 = 140 нс   (на 40 % медленнее)

Числа условные: в реальном процессоре и данные, и записи таблиц часто лежат в кэшах, и походы короче. Но пропорция верная: каждый процент промахов TLB заметно бьёт по скорости, особенно при многоуровневых таблицах.

Кто обрабатывает промах

Есть два подхода.

Аппаратный (x86-64, ARM). Процессор сам знает формат таблицы страниц и сам обходит её при промахе: берёт адрес таблицы из регистра CR3, читает нужные записи, кладёт результат в TLB и повторяет инструкцию. ОС в этом не участвует, пока страница в RAM. Если же в найденной записи страница отсутствует, процессор вызывает ядро ОС (page fault, см. за пределами физической памяти).

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

Почему TLB вообще работает: локальность

Кэш крошечный (часто 64–512 строк), а виртуальное пространство огромно. Почему же hit'ов так много? Потому что программы обращаются к памяти не случайно, а с локальностью:

• Пространственная локальность. Если тронули один байт, скоро тронем соседний. Массив, поля структуры, инструкции функции лежат рядом — всё это попадает в ОДНУ страницу. Первое обращение к странице — miss, а сотни следующих по этой же странице — hit'ы.
• Временная локальность. Если страницу трогали недавно, скорее всего тронем снова (цикл крутится по тем же данным, та же функция вызывается).

  Проход по []int32 из 4096 элементов (int32 = 4 байта,
  страница 4 КБ = 1024 элемента; массив выровнен по странице)
 
  i:   0    1    2  ...  1023 1024 1025 ... 2047 ...
       │    │    │        │    │    │        │
       ▼    ▼    ▼        ▼    ▼    ▼        ▼
     [miss][hit][hit]...[hit][miss][hit]...[hit]...
       │                       │
   первый элемент            перешли на
   страницы — промах         новую страницу
 
  4096 обращений, а промахов всего 4 (по числу страниц).
  Hit rate = 4092/4096 ≈ 99,9 %.

Для []int в Go (8 байт на элемент) на страницу влезает 512 элементов, и тот же проход даст 8 промахов из 4096: всё равно 99,8 % попаданий.

Вывод для практики: код, который ходит по памяти последовательно (по порядку), дружит с TLB. Код, который прыгает случайно по огромной области (например, обход большого хеша или связного списка с разбросанными узлами), бьёт мимо TLB и тормозит, даже если данные формально в RAM.

Что лежит в одной строке TLB

Строка TLB — это не только пара «страница → кадр». Туда же копируются биты из PTE, чтобы при hit'е не лезть в таблицу вообще ни за чем.

  Одна строка (запись) TLB
 
  ┌─────────┬───────────┬──────┬─────┬───────┬──────┐
  │  VPN    │   PFN     │ valid│ prot│ dirty │ ASID │
  │ (тег:   │ (номер    │ бит  │права│  бит  │ чей  │
  │  какая  │  кадра)   │      │ R/W │ грязи │ это  │
  │ страница│           │      │ /X  │       │ proc)│
  └─────────┴───────────┴──────┴─────┴───────┴──────┘
       ▲ ищем по нему         ▲ что отдаём при hit

• VPN — тег, по нему ищем строку.
• PFN — номер физического кадра, главный результат.
• valid — действительна ли строка TLB (не путать с valid-битом в PTE!).
• prot — права: можно ли читать/писать/исполнять. Нарушил — защитная ошибка.
• dirty — менялась ли страница (нужно при вытеснении, см. swapping).
• ASID — про него ниже, метка владельца.

Цена переключения контекста: flush или ASID

А теперь самое коварное. TLB хранит трансляции текущего процесса. Но у каждого процесса своя таблица страниц: у процесса A страница 0 → кадр 10, а у процесса B та же страница 0 → кадр 88. Виртуальные адреса совпадают, физические — разные.

Что будет, если переключиться с A на B и не тронуть TLB? Процесс B обратится к своей странице 0, попадёт в строку TLB, оставшуюся от A, и прочитает чужой кадр 10. Это и утечка данных, и порча памяти: изоляция сломана.

  Опасность после context switch (если ничего не сделать)
 
  Было (выполнялся A):           TLB:  VPN0 → PFN10  (это память A!)
 
  Переключились на B...
  B читает свою страницу 0
        │
        ▼
   TLB hit → PFN10  ← ЧУЖОЙ кадр процесса A!
   B видит данные A. Изоляция сломана.

Есть два способа это починить:

1. Flush (сброс) TLB при каждом переключении. Просто помечаем все строки невалидными. Просто и безопасно. Минус: после переключения TLB пустой, и первые обращения нового процесса — сплошные промахи, пока кэш не «прогреется» заново. Это часть той самой цены переключения контекста, о которой шла речь в limited-direct-execution: переключение стоит дорого не только из-за сохранения регистров, но и из-за холодных кэшей и TLB.

  Flush: чистим всё на каждом switch
 
  switch A → B:  TLB → [пусто]
  B стартует     → промах, промах, промах... (прогрев)

2. ASID (Address Space ID) — метим строки владельцем. В каждую строку TLB кладём маленький номер адресного пространства. Процессор знает, чей сейчас ASID, и считает hit'ом только строку с совпадающим ASID. Тогда трансляции A и B мирно живут в TLB одновременно, и flush при переключении не нужен — после возврата к A его строки всё ещё там.

  ASID: строки разных процессов сосуществуют
 
  ┌──────┬──────┬───────┐
  │ ASID │ VPN  │ PFN   │
  ├──────┼──────┼───────┤
  │  A   │  0   │  10   │  ◄ при работе A — hit только тут
  │  B   │  0   │  88   │  ◄ при работе B — hit только тут
  │  A   │  1   │  23   │
  └──────┴──────┴───────┘
 
  switch A → B: ничего не чистим, просто меняем текущий ASID.

В реальности (x86 это PCID, ARM — ASID) современные процессоры используют метки, чтобы переключения были дешевле. Но ASID-ов конечное число, и при их нехватке ОС всё равно вынуждена сбрасывать TLB.

TLB reach и huge pages

TLB reach («охват TLB») — сколько памяти суммарно покрывают все строки TLB. Формула проста:

  TLB reach = (число строк TLB) × (размер страницы)
 
  Пример при странице 4 КБ и 64 строках:
     64 × 4 КБ = 256 КБ
 
  Программа активно работает с 256 КБ → почти всё в TLB → отлично.
  Программа гоняет 2 ГБ данных → 256 КБ покрытия = капля в море
     → постоянные промахи TLB, даже если данные в RAM.

Видно проблему: TLB маленький, и для «толстых» приложений (большие базы данных, in-memory кэши, аналитика на гигабайтах) охвата не хватает. Каждая новая страница — промах.

Увеличить число строк дорого (это быстрая дефицитная память в ядре CPU). Поэтому крутят второй множитель — размер страницы. Это huge pages (большие страницы): вместо 4 КБ — 2 МБ или 1 ГБ на страницу.

  Тот же 64-строчный TLB, но страницы 2 МБ:
 
     64 × 2 МБ = 128 МБ охвата   (было 256 КБ!)
 
  Рост покрытия в 512 раз теми же строками TLB.

Одна строка TLB теперь покрывает в 512 раз больше памяти, и большое приложение помещается в TLB. Бонусом таблица страниц становится мельче и многоуровневый обход короче (см. smaller-tables). Плата за huge pages — более грубая гранулярность: внутренняя фрагментация растёт (выделили 2 МБ ради маленькой структуры — почти всё впустую), а свопить такие страницы тяжелее.

Huge pages бывают двух видов. Явные (hugetlbfs): администратор заранее резервирует пул больших страниц, а приложение просит их специально. Так делают базы данных: PostgreSQL с huge_pages = on кладёт в них свой буферный пул, JVM умеет -XX:+UseLargePages. Прозрачные (transparent huge pages, THP): ядро само пытается собирать обычные страницы процесса в большие, без участия приложения.

THP — палка о двух концах. Ядро тратит время на поиск и сборку непрерывных 2 МБ физической памяти (фоновым потоком khugepaged или прямо в момент page fault), и это даёт непредсказуемые задержки. Поэтому, например, Redis прямо рекомендует отключать THP: при fork для снапшота copy-on-write копирует уже не 4 КБ, а 2 МБ на каждую изменённую страницу. Режим смотрят и меняют в /sys/kernel/mm/transparent_hugepage/enabled (always, madvise, never).

Связь с Go и продом

• Случайный доступ к большой памяти бьёт по TLB. Обход большой map, связного списка, дерева с узлами по всей куче — это промахи TLB поверх промахов кэша. Сборщик мусора Go тоже ходит по всей куче. Проверить гипотезу на Linux можно счётчиками процессора: perf stat -e dTLB-loads,dTLB-load-misses ./app.
• Go и THP. Рантайм Go на Linux работает с THP в режиме ядра по умолчанию и в разных версиях по-разному подсказывал ядру, где их использовать; эти подсказки меняли из-за роста RSS у части сервисов. Если после обновления Go или ядра у сервиса заметно изменились RSS или хвосты задержек, THP — один из подозреваемых.
• TLB shootdown. На многоядерной машине у каждого ядра CPU свой TLB. Когда процесс освобождает память (munmap, возврат памяти рантаймом через madvise) или меняет права страниц, ядро ОС обязано убрать устаревшие трансляции из TLB всех ядер, где работали потоки этого процесса. Для этого оно посылает им межпроцессорные прерывания и ждёт подтверждения. Частые munmap в многопоточном процессе — заметная цена на десятках ядер.
• Переключение контекста. Холодный TLB после переключения — часть цены переключения процессов (глава цена syscall и переключения контекста). Потоки одного процесса делят таблицу страниц, поэтому переключение между ними TLB не сбрасывает.

Частые ошибки

• Путать промах TLB с page fault. Промах TLB — трансляции нет в кэше, но страница в RAM; железо найдёт её в таблице за десятки наносекунд. Page fault — страницы нет в RAM или доступ запрещён, работает ядро ОС.
• Считать, что TLB кэширует данные. Он кэширует только трансляции; данные лежат в обычных кэшах процессора.
• Думать, что huge pages всегда ускоряют. Явные huge pages помогают большим буферам баз данных; прозрачные могут добавить задержек и памяти.

Проверьте себя

1. TLB на 1536 строк, страницы 4 КБ. Какой у него охват? А со страницами 2 МБ?
2. Обращение к RAM 100 нс, промах TLB стоит одно дополнительное обращение. Каким будет среднее время доступа при 95 % попаданий?
3. Программа проходит []int64 длиной 1 млн элементов по порядку. Сколько примерно промахов TLB при страницах 4 КБ?
4. Почему переключение между потоками одного процесса дешевле для TLB, чем между процессами?

Что спрашивают на собесе

• Зачем нужен TLB и какую проблему он решает? Ответ: paging требует лишнего похода в память за PTE на каждое обращение (2× замедление); TLB кэширует трансляции, и при hit'е лишний поход исчезает.
• Чем отличается TLB hit от miss по стоимости? Hit — кадр из TLB, ноль лишних обращений к RAM; miss — идём в таблицу страниц (одно или несколько чтений при многоуровневой таблице), заполняем TLB, повторяем.
• Почему TLB вообще даёт высокий hit rate при таком малом размере? Локальность: пространственная (соседние адреса в одной странице) и временная (повторные обращения к тем же страницам).
• Что происходит с TLB при переключении контекста и почему это часть его цены? Либо flush (затем холодный TLB и волна промахов), либо ASID/PCID (строки процессов сосуществуют, flush не нужен). Это объясняет, почему context switch дорог.
• Что такое TLB reach и как его увеличить? reach = число строк × размер страницы; увеличивают через huge pages (2 МБ/1 ГБ), что резко поднимает охват теми же строками. Минус — внутренняя фрагментация.
• Чем valid-бит в строке TLB отличается от valid в PTE? В PTE он говорит, легальна ли страница вообще (нелегальная — segfault; на x86-64 это знает ОС, а в PTE есть только present); в TLB — лишь актуальна ли строка кэша (после flush — невалидна).
• Кто обрабатывает промах TLB? На x86-64 и ARM — железо (обход таблицы); на MIPS — ОС через исключение.
• Что такое TLB shootdown и когда он случается? Сброс трансляций в TLB других ядер при munmap или смене прав; дорог на многоядерных машинах.