Трансляция адреса и TLB

В уроке 53 виртуальная память была кэшем: страницы, таблица страниц, попадание и сбой. В уроке 54 она стала менеджером и охранником: у каждого процесса своё пространство, у каждой области свои права. Оба раза мы говорили “MMU переводит адрес” и шли дальше. Сегодня остановимся именно здесь. Перевод адреса происходит на каждой инструкции, иногда дважды: один раз, чтобы достать саму инструкцию, второй раз, чтобы достать её операнд. Если делать его честно, через таблицу в памяти, каждое обращение к памяти превратится в два, а на настоящей машине с четырьмя уровнями таблиц в пять. Этого не происходит, и причина называется TLB. Мы пройдём весь путь адреса до байта руками на маленькой системе, где все таблицы помещаются на экран, потом соберём тот же путь на Zig, потом перейдём к настоящему x86-64: четыре уровня таблиц, формат записи по битам, огромные страницы. И в конце измерим, сколько стоит промах TLB на живом железе, и увидим, что огромные страницы снимают эту цену почти целиком.

Цели урока

• Знать по шагам, что делает MMU при попадании страницы и что делают вместе MMU и ядро при сбое страницы, и где в этой цепочке стоит кэш процессора.
• Понимать TLB как маленький кэш записей таблицы страниц: из каких бит VPN берутся индекс набора и тег, что происходит при попадании и промахе.
• Уметь руками пройти сквозной пример: разрезать виртуальный адрес, найти строку TLB, при промахе прочитать PTE, собрать физический адрес, разрезать его для кэша и достать байт.
• Считать память под таблицы страниц: почему плоская таблица на 48 бит невозможна, сколько таблиц нужно разреженному адресному пространству и откуда берётся экономия в миллионы раз.
• Читать запись таблицы страниц x86-64 по битам (P, R/W, U/S, A, D, PS, XD), знать, что лежит в CR3, зачем нужен PCID и что меняют пять уровней.
• Понимать огромные страницы: как они укорачивают обход и расширяют охват TLB, и чем за это платят.
• Объяснять, почему кэш L1 индексируется битами смещения и как это ограничивает его размер.
• Измерять цену промахов TLB своей программой и отличать её от цены промахов кэша.

Кто переводит адрес и когда

Вспомним обозначения из урока 53. Виртуальный адрес из n бит делится на две части. Младшие p бит это VPO, смещение внутри страницы размером 2 в степени p байт. Старшие n минус p бит это VPN, номер виртуальной страницы. У физического адреса из m бит те же две части: PPO и PPN. Страницы одного размера, поэтому PPO всегда равно VPO, и вся трансляция сводится к одной замене: VPN на PPN.

Замену делает MMU. Таблицу, по которой он работает, готовит ядро, а где она лежит, говорит специальный регистр. В книге он назван PTBR, на x86-64 это CR3. Регистр хранит физический адрес, иначе чтобы найти таблицу, понадобилась бы ещё одна трансляция, и так без конца. Переключение процесса из урока про процессы и контексты с точки зрения памяти это одна запись в CR3: с этого момента все виртуальные адреса читаются по другой таблице, и процесс оказывается в своём мире.

Когда страница в памяти, всё делает железо, ядро не участвует. Шаги такие.

1. Процессор выдаёт виртуальный адрес и передаёт его MMU.
2. MMU вычисляет адрес нужной PTE: содержимое PTBR плюс VPN, умноженный на размер записи. Этот адрес физический, он уходит в кэш и основную память.
3. Память возвращает PTE.
4. MMU проверяет бит valid и права, берёт из PTE номер PPN, приписывает к нему справа VPO и получает физический адрес. Он уходит в кэш и основную память.
5. Память возвращает процессору запрошенное слово.

Посчитай обращения к памяти: их два. Одно за PTE, одно за данными. Программа просила одно.

Когда страницы в памяти нет, первые три шага те же, а дальше железо сдаётся и зовёт ядро.

4. Бит valid в PTE равен нулю. MMU возбуждает исключение, сбой страницы. Управление уходит в обработчик ядра, как в уроке про исключения: это сбой в строгом смысле классификации, инструкция не выполнена и будет перезапущена.
5. Обработчик выбирает в физической памяти страницу-жертву. Если жертву меняли (об этом скажет бит dirty в её PTE), сначала записывает её на диск.
6. Обработчик подкачивает нужную страницу на освободившееся место и исправляет PTE: valid равен единице, PPN указывает на кадр.
7. Обработчик возвращает управление на ту же инструкцию. Процессор выдаёт MMU тот же виртуальный адрес, и теперь всё идёт по короткому сценарию.

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

Где в этой схеме кэш

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

Первая: разные процессы держат разные данные по одинаковым виртуальным адресам. Если кэш индексировать виртуальным адресом, после переключения процесса он вернёт чужой байт; пришлось бы чистить кэш на каждом переключении или приписывать к тегу номер процесса. С физическим адресом проблемы нет: физический адрес байта один на всю машину. Вторая причина зеркальна: два процесса, которые делят страницу (общая библиотека из урока 54), обращаются к ней по разным виртуальным адресам, но в физически адресованном кэше попадают в одну и ту же строку и греют её друг для друга.

Следствие, о котором легко забыть: PTE это тоже данные в памяти, и MMU достаёт их через тот же кэш. Адрес PTE физический, он идёт сначала в L1, и только при промахе дальше. Так что “два обращения к памяти” на практике чаще всего означает два обращения к L1, а таблицы страниц горячего кода живут в кэше рядом с самим кодом. Это смягчает цену трансляции, но не снимает: даже попадание в L1 это три или четыре такта, и они стоят на пути каждой инструкции. Нужен кэш поближе и поуже. Он есть.

TLB: кэш для записей таблицы страниц

TLB это кэш внутри самого MMU, где каждая строка хранит ровно одну PTE. Ключом служит VPN, значением PPN вместе с битами прав. Устроен он так же, как кэш из урока 38, только режется не адрес целиком, а один VPN. Смещения в блоке нет: блок это одна запись. Если в TLB 2 в степени t наборов, то младшие t бит VPN это TLBI, индекс набора, а оставшиеся старшие биты VPN это TLBT, тег. Внутри набора все строки сравниваются с тегом одновременно, как в любом множественно-ассоциативном кэше.

Поле VA	Биты	Кому нужно
VPO	младшие p	никому при трансляции, переезжает в PA как есть
TLBI	следующие t	TLB: номер набора
TLBT	все оставшиеся старшие	TLB: тег для сравнения
VPN	TLBT и TLBI вместе	таблица страниц: индекс PTE

С TLB шаги попадания выглядят так.

1. Процессор выдаёт виртуальный адрес.
2. MMU режет VPN на TLBT и TLBI и ищет строку в TLB.
3. TLB отдаёт PTE. Всё это происходит внутри кристалла, без обращения к памяти.
4. MMU собирает физический адрес и отправляет его в кэш и память.
5. Память возвращает слово.

Обращение к памяти снова одно, как и просила программа. При промахе TLB между шагами 2 и 4 вставляется знакомый поход в память за PTE, после чего запись кладётся в TLB, при необходимости вытесняя старую. На x86-64 и ARM этот поход целиком аппаратный: в MMU есть конечный автомат, который сам идёт по таблицам, ядро о промахе TLB даже не узнаёт. Бывают архитектуры, где промах TLB это исключение и таблицу обходит код ядра (классические MIPS и SPARC), но сегодня это редкость.

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

Сквозной пример: от виртуального адреса до байта

Система учебная, из раздела 9.6.4 книги. Она нарочно крошечная: все три таблицы помещаются на страницу, а каждое число можно проверить карандашом.

• Память адресуется побайтно, обращения идут к отдельным байтам.
• Виртуальный адрес 14 бит, физический 12 бит.
• Страница 64 байта, то есть p равно 6.
• TLB на 16 строк: четыре набора по четыре строки.
• Кэш L1 прямого отображения: 16 строк, блок 4 байта. Адресуется физически.

Сначала разметим адреса. Страница 64 байта, значит VPO и PPO занимают по 6 бит. На VPN остаётся 14 минус 6, то есть 8 бит: виртуальных страниц 256. На PPN остаётся 12 минус 6, то есть 6 бит: физических страниц 64. В TLB четыре набора, значит TLBI это два младших бита VPN, а TLBT это шесть старших. У кэша 16 строк и блок из 4 байт: смещение в блоке CO это 2 бита, индекс CI это 4 бита, тег CT это оставшиеся 6 бит физического адреса.

бит VA:   13 12 11 10  9  8 | 7  6 | 5  4  3  2  1  0
          [      TLBT       ][TLBI ][      VPO        ]
          [          VPN           ]

бит PA:   11 10  9  8  7  6 | 5  4  3  2 | 1  0
          [       CT        ][    CI     ][ CO ]
          [       PPN       ][      PPO        ]

Обрати внимание на совпадение во второй схеме: граница между PPN и PPO проходит ровно там же, где граница между CT и CI плюс CO. В этой системе тег кэша побитно равен PPN, а CI и CO вместе равны PPO. Это не закон природы, а свойство именно этих параметров, но оно нам ещё пригодится, когда дойдём до настоящего L1.

Теперь содержимое. TLB, строки по наборам. Формат клетки: тег, PPN, valid. У недействительных строк PPN не определён, стоит прочерк.

Набор	Строка 0	Строка 1	Строка 2	Строка 3
0	03 · 0	09 0D 1	00 · 0	07 02 1
1	03 2D 1	02 · 0	04 · 0	0A · 0
2	02 · 0	08 · 0	06 · 0	03 · 0
3	07 · 0	03 0D 1	0A 34 1	02 · 0

Таблица страниц. Всего в ней 256 записей, нас интересуют первые 16.

VPN	PPN	valid		VPN	PPN	valid
00	28	1		08	13	1
01	·	0		09	17	1
02	33	1		0A	09	1
03	02	1		0B	·	0
04	·	0		0C	·	0
05	16	1		0D	2D	1
06	·	0		0E	11	1
07	·	0		0F	0D	1

Кэш. Индекс, тег, valid и четыре байта блока.

CI	Тег	valid	Байт 0	Байт 1	Байт 2	Байт 3
0	19	1	99	11	23	11
1	15	0	·	·	·	·
2	1B	1	00	02	04	08
3	36	0	·	·	·	·
4	32	1	43	6D	8F	09
5	0D	1	36	72	F0	1D
6	31	0	·	·	·	·
7	16	1	11	C2	DF	03
8	24	1	3A	00	51	89
9	2D	0	·	·	·	·
A	2D	1	93	15	DA	3B
B	0B	0	·	·	·	·
C	12	0	·	·	·	·
D	16	1	04	96	34	15
E	13	1	83	77	1B	D3
F	14	0	·	·	·	·

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

Адрес 0x03d4: всё попадает

Этот адрес разобран в книге, начнём с него. Пишем 14 бит и режем.

0x03d4 = 00 0011 1101 0100

VPN  = 0000 1111  = 0x0f        VPO  = 01 0100 = 0x14
TLBT = 0000 11    = 0x03        TLBI = 11      = 3

MMU идёт в набор 3 и сравнивает тег 0x03 сразу со всеми четырьмя строками. Строка 1 хранит тег 03 и действительна: попадание TLB, PPN равен 0x0d. В таблицу страниц никто не ходил. Можешь проверить, что TLB не врёт: PTE с номером 0x0f в таблице тоже хранит 0x0d.

Собираем физический адрес: PPN слева, VPO справа.

PPN = 00 1101, VPO = 01 0100  ->  PA = 0011 0101 0100 = 0x354

CT = 0011 01 = 0x0d      CI = 0101 = 5      CO = 00 = 0

Строка 5 кэша действительна, её тег 0D совпал. Попадание кэша, байт со смещением 0 равен 0x36. Итог: ни одного обращения к основной памяти. TLB внутри MMU, L1 рядом с ядром, всё решилось на кристалле.

Адрес 0x015d: промах TLB, страница в памяти

0x015d = 00 0001 0101 1101

VPN  = 0000 0101 = 0x05         VPO  = 01 1101 = 0x1d
TLBT = 0000 01   = 0x01         TLBI = 01      = 1

Набор 1, ищем тег 0x01. В наборе лежат теги 03, 02, 04 и 0A: нужного нет. Промах TLB. Теперь MMU обязан прочитать PTE из памяти: адрес записи равен PTBR плюс 5 размеров записи. PTE номер 05 действительна, PPN равен 0x16. MMU кладёт эту запись в TLB. В наборе 1 три свободные строки, занимается первая из них, строка 1: там появляется тег 01, PPN 16, valid 1.

PPN = 01 0110, VPO = 01 1101  ->  PA = 0101 1001 1101 = 0x59d

CT = 0101 10 = 0x16      CI = 0111 = 7      CO = 01 = 1

Строка 7 действительна, тег 16 совпал, байт со смещением 1 равен 0xc2. Итог: одно лишнее обращение к памяти за PTE, а данные нашлись в кэше. Если сейчас повторить этот же адрес или любой другой с той же страницы, например 0x0140, TLB уже попадёт. В виджете это видно: нажми 0x015d дважды.

Адрес 0x0900: TLB знает то, чего нет на картинке

0x0900 = 00 1001 0000 0000

VPN  = 0010 0100 = 0x24         VPO  = 00 0000 = 0x00
TLBT = 0010 01   = 0x09         TLBI = 00      = 0

VPN равен 0x24, это 36-я страница. В нашей таблице на 16 строк её нет, и на бумаге тут легко ошибиться и объявить сбой. Но MMU сначала смотрит в TLB: набор 0, тег 0x09. Строка 1 хранит тег 09 и действительна, PPN равен 0x0d. Попадание. Вот ради чего TLB существует: трансляция получена, а в таблицу страниц никто не заглядывал и не знает, что в ней написано.

PPN = 00 1101, VPO = 00 0000  ->  PA = 0011 0100 0000 = 0x340

CT = 0x0d      CI = 0      CO = 0

Строка 0 кэша действительна, но хранит тег 19, а нужен 0D. Промах кэша: блок придётся читать из основной памяти. Заодно заметь любопытное: страницы 0x0f и 0x24 отображены на одну и ту же физическую страницу 0x0d. Ничего странного, так выглядит разделяемая память внутри одного процесса, например файл, отображённый дважды.

Адрес 0x01c8: сбой страницы

0x01c8 = 00 0001 1100 1000

VPN  = 0000 0111 = 0x07         VPO  = 00 1000 = 0x08
TLBT = 0000 01   = 0x01         TLBI = 11      = 3

Набор 3, тег 0x01. В наборе теги 07, 03, 0A, 02: промах. Осторожно с ловушкой: тег 07 в строке 0 похож на наш VPN, но сравнивается тег, а не VPN, и строка к тому же недействительна. MMU читает PTE номер 07: valid равен нулю. Страницы в памяти нет. MMU возбуждает сбой страницы, физического адреса не существует, до кэша дело не доходит. Дальше работает ядро: подкачка, правка PTE, перезапуск инструкции. В TLB при этом ничего не записывается: туда попадают только действительные трансляции.

VA	VPN	TLB	PTE	PA	Кэш	Обращений к памяти
0x03d4	0x0f	попадание	не читалась	0x354	попадание, 0x36	0
0x015d	0x05	промах	действительна	0x59d	попадание, 0xc2	1 (PTE)
0x0900	0x24	попадание	не читалась	0x340	промах	1 (данные)
0x01c8	0x07	промах	недействительна	нет	не дошли	1 (PTE) и диск

Та же машина на Zig

Модель, которую можно исполнить, честнее модели на бумаге: она не позволит пропустить шаг. Напишем MMU учебной системы. Ширины полей зашьём в типы: у Zig есть целые любой разрядности, и u14 для виртуального адреса, u6 для PPN и u2 для смещения в блоке кэша работают как бесплатная проверка. Присвоить лишний бит компилятор не даст, а @truncate и @intCast явно показывают, где мы отрезаем младшие биты и где утверждаем, что старшие поместятся.

const std = @import("std");

// Учебная система: VA 14 бит, PA 12 бит, страница 64 байта,
// TLB 4 набора по 4 строки, кэш прямого отображения 16 строк по 4 байта.
const page_bits = 6;
const tlb_set_bits = 2;
const cache_set_bits = 4;
const cache_block_bits = 2;

const Va = u14;
const Pa = u12;
const Vpn = u8;
const Ppn = u6;

const TlbEntry = struct { valid: bool = false, tag: u6 = 0, ppn: Ppn = 0, last_used: u32 = 0 };
const Pte = struct { valid: bool = false, ppn: Ppn = 0 };
const CacheLine = struct { valid: bool = false, tag: u6 = 0, bytes: [4]u8 = @splat(0) };

const Outcome = union(enum) {
    ok: struct { pa: Pa, tlb_hit: bool },
    page_fault,
};

const Mmu = struct {
    tlb: [4][4]TlbEntry = @splat(@splat(.{})),
    page_table: [256]Pte = @splat(.{}),
    clock: u32 = 0,
    walks: u32 = 0,

    fn translate(self: *Mmu, va: Va) Outcome {
        self.clock += 1;
        const vpn: Vpn = @intCast(va >> page_bits);
        const vpo: u6 = @truncate(va);
        const set = &self.tlb[vpn & 0b11];
        const tag: u6 = @intCast(vpn >> tlb_set_bits);

        for (set) |*entry| {
            if (entry.valid and entry.tag == tag) {
                entry.last_used = self.clock;
                return .{ .ok = .{ .pa = join(entry.ppn, vpo), .tlb_hit = true } };
            }
        }

        // Промах TLB: идём в память за PTE.
        self.walks += 1;
        const pte = self.page_table[vpn];
        if (!pte.valid) return .page_fault;

        // Запоминаем PTE в TLB: свободная строка, иначе самая давняя.
        var victim: *TlbEntry = &set[0];
        for (set) |*entry| {
            if (!entry.valid) {
                victim = entry;
                break;
            }
            if (entry.last_used < victim.last_used) victim = entry;
        }
        victim.* = .{ .valid = true, .tag = tag, .ppn = pte.ppn, .last_used = self.clock };
        return .{ .ok = .{ .pa = join(pte.ppn, vpo), .tlb_hit = false } };
    }
};

fn join(ppn: Ppn, vpo: u6) Pa {
    return @as(Pa, ppn) << page_bits | vpo;
}

/// Кэш адресуется физически: режем уже готовый PA.
fn cacheRead(cache: *const [16]CacheLine, pa: Pa) ?u8 {
    const co: u2 = @truncate(pa);
    const ci: u4 = @truncate(pa >> cache_block_bits);
    const ct: u6 = @intCast(pa >> (cache_block_bits + cache_set_bits));
    const line = cache[ci];
    return if (line.valid and line.tag == ct) line.bytes[co] else null;
}

fn bookMmu() Mmu {
    var mmu: Mmu = .{};
    const T = struct { u2, u2, u6, Ppn }; // набор, строка, тег, PPN
    const tlb = [_]T{
        .{ 0, 1, 0x09, 0x0d }, .{ 0, 3, 0x07, 0x02 }, .{ 1, 0, 0x03, 0x2d },
        .{ 3, 1, 0x03, 0x0d }, .{ 3, 2, 0x0a, 0x34 },
    };
    for (tlb) |t| mmu.tlb[t[0]][t[1]] = .{ .valid = true, .tag = t[2], .ppn = t[3] };
    const P = struct { Vpn, Ppn };
    const ptes = [_]P{
        .{ 0x00, 0x28 }, .{ 0x02, 0x33 }, .{ 0x03, 0x02 }, .{ 0x05, 0x16 }, .{ 0x08, 0x13 },
        .{ 0x09, 0x17 }, .{ 0x0a, 0x09 }, .{ 0x0d, 0x2d }, .{ 0x0e, 0x11 }, .{ 0x0f, 0x0d },
    };
    for (ptes) |p| mmu.page_table[p[0]] = .{ .valid = true, .ppn = p[1] };
    return mmu;
}

fn bookCache() [16]CacheLine {
    var cache: [16]CacheLine = @splat(.{});
    const C = struct { u4, u6, [4]u8 }; // строка, тег, блок
    const lines = [_]C{
        .{ 0x0, 0x19, .{ 0x99, 0x11, 0x23, 0x11 } }, .{ 0x2, 0x1b, .{ 0x00, 0x02, 0x04, 0x08 } },
        .{ 0x4, 0x32, .{ 0x43, 0x6d, 0x8f, 0x09 } }, .{ 0x5, 0x0d, .{ 0x36, 0x72, 0xf0, 0x1d } },
        .{ 0x7, 0x16, .{ 0x11, 0xc2, 0xdf, 0x03 } }, .{ 0x8, 0x24, .{ 0x3a, 0x00, 0x51, 0x89 } },
        .{ 0xa, 0x2d, .{ 0x93, 0x15, 0xda, 0x3b } }, .{ 0xd, 0x16, .{ 0x04, 0x96, 0x34, 0x15 } },
        .{ 0xe, 0x13, .{ 0x83, 0x77, 0x1b, 0xd3 } },
    };
    for (lines) |l| cache[l[0]] = .{ .valid = true, .tag = l[1], .bytes = l[2] };
    return cache;
}

pub fn main(init: std.process.Init) !void {
    var buf: [4096]u8 = undefined;
    var w = std.Io.File.stdout().writer(init.io, &buf);
    const out = &w.interface;

    var mmu = bookMmu();
    const cache = bookCache();

    for ([_]Va{ 0x03d4, 0x015d, 0x015d, 0x0900, 0x01c8 }) |va| {
        try out.print("VA 0x{x:0>4}: ", .{va});
        switch (mmu.translate(va)) {
            .page_fault => try out.print("промах TLB, сбой страницы\n", .{}),
            .ok => |t| {
                const tlb = if (t.tlb_hit) "попадание TLB" else "промах TLB   ";
                try out.print("{s}, PA 0x{x:0>3}, ", .{ tlb, t.pa });
                if (cacheRead(&cache, t.pa)) |byte| {
                    try out.print("кэш отдал 0x{x:0>2}\n", .{byte});
                } else {
                    try out.print("промах кэша\n", .{});
                }
            },
        }
    }
    try out.print("обращений к таблице страниц: {d} из {d}\n", .{ mmu.walks, mmu.clock });
    try out.flush();
}

$ zig run walk.zig
VA 0x03d4: попадание TLB, PA 0x354, кэш отдал 0x36
VA 0x015d: промах TLB   , PA 0x59d, кэш отдал 0xc2
VA 0x015d: попадание TLB, PA 0x59d, кэш отдал 0xc2
VA 0x0900: попадание TLB, PA 0x340, промах кэша
VA 0x01c8: промах TLB, сбой страницы
обращений к таблице страниц: 2 из 5

Все четыре ручных разбора сошлись, а вторая строка с адресом 0x015d показывает то, чего на бумаге не видно: TLB учится. Первое обращение к странице 0x05 стоило похода в таблицу, второе уже нет.

На что посмотреть в коде.

Порядок проверок. Сначала TLB, и при попадании функция возвращается, не коснувшись page_table. Это не оптимизация модели, а смысл TLB: адрес 0x0900 переводится, хотя в нашей таблице его PTE вообще не задана.

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

Обратная задача: TLB надо уметь чистить. Раз TLB хранит копии PTE, любая правка таблицы страниц делает копию устаревшей. Ядро убрало страницу из памяти, а TLB по-прежнему отдаёт её старый PPN: процесс пишет в чужой кадр. Поэтому после правки PTE ядро обязано выбросить строку из TLB. На x86-64 для этого есть инструкция invlpg (одна страница) и перезапись CR3 (всё сразу). На многоядерной машине хуже: у каждого ядра свой TLB, и ядру ОС приходится рассылать остальным межпроцессорное прерывание с просьбой почиститься. Это называется TLB shootdown, и именно поэтому munmap и mprotect в многопоточной программе стоят заметно дороже, чем кажется по их скромным сигнатурам.

В модели этого нет, и это упрощение стоит держать в голове. В практической задаче урока ты напишешь translate сам, под тестами.

Многоуровневые таблицы: как уместить 512 ГБ в 48 КБ

До сих пор таблица страниц была одним массивом: VPN это индекс, PTE это элемент. Для учебной системы это 256 записей. Посчитаем для настоящих.

32 бита, страницы 4 КБ, PTE 4 байта. VPN занимает 20 бит, записей 2 в степени 20, таблица весит 4 МБ. На каждый процесс, всегда, даже если процесс это true, который живёт миллисекунду и трогает десяток страниц. Сто процессов это 400 МБ одних таблиц. Для машин девяностых, где памяти было 16 МБ, это приговор.

48 бит, страницы 4 КБ, PTE 8 байт. VPN занимает 36 бит. Записей 2 в степени 36, по 8 байт каждая: 2 в степени 39 байт, то есть 512 ГБ на процесс. Это уже не дорого, это невозможно.

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

Решение: дерево. Разобьём VPN на несколько кусков и будем использовать каждый кусок как индекс на своём уровне. Возьмём пример из книги: 32 бита, два уровня. Таблица первого уровня это 1024 записи, каждая отвечает за кусок адресного пространства в 4 МБ. Если в этом куске не отображена ни одна страница, запись пуста, и таблицы второго уровня для него просто не существует. Если отображена хотя бы одна, запись указывает на таблицу второго уровня: ещё 1024 записи, каждая это обычная PTE одной страницы.

Посчитаем процесс, у которого занято немного внизу (код, данные, куча в пределах 8 МБ) и немного наверху (стек в пределах 4 МБ).

Что	Сколько	Память
таблица первого уровня	1	4 КБ
таблицы второго уровня под код, данные, кучу	2	8 КБ
таблица второго уровня под стек	1	4 КБ
всего	4 таблицы	16 КБ
плоская таблица	1	4096 КБ

Экономия в 256 раз, и это для 32 бит, где пустоты сравнительно мало. У дерева есть и второе достоинство, менее заметное. В памяти обязана постоянно находиться только таблица первого уровня. Таблицы второго уровня это обычные страницы ядра, и редко используемые из них ядро в принципе может создавать по требованию и выгружать.

В общем виде: k уровней, VPN режется на k кусков, VPN 1 до VPN k. Регистр базы указывает на таблицу первого уровня. Запись уровня j указывает на начало таблицы уровня j плюс 1. Только запись последнего уровня хранит PPN страницы. Чтобы собрать физический адрес, MMU должен прочитать k записей подряд, и каждое чтение зависит от предыдущего: распараллелить нельзя.

Вот и цена. Промах TLB в двухуровневой системе это два лишних обращения к памяти, в четырёхуровневой четыре. Звучит страшно, на деле терпимо по двум причинам. Первая: TLB попадает в подавляющем большинстве случаев, а платит только промах. Вторая: таблицы верхних уровней крошечные и горячие. У процесса одна таблица первого уровня и считаные таблицы второго и третьего, обращаются к ним постоянно, и они не покидают L1. Сверх того, в современных MMU стоят специальные кэши обхода: они запоминают записи верхних уровней, и обход при промахе TLB начинается не с корня, а сразу с предпоследней таблицы. Типичный промах TLB обходится в одно, редко два обращения к памяти, а не в четыре.

Четыре уровня x86-64

Теперь настоящая машина. Книга разбирает Core i7 поколения Nehalem, и с тех пор схема страничной организации x86-64 не менялась: то, что описано ниже, верно и для процессора 2026 года. Первоисточник здесь не книга, а Intel SDM, том 3A, глава 4.

Виртуальный адрес 48 бит, физический до 52 бит. Страница 4 КБ, смещение 12 бит. Оставшиеся 36 бит VPN режутся на четыре индекса по 9 бит. Девять не случайное число: таблица из 512 записей по 8 байт занимает ровно 4096 байт, то есть каждая таблица любого уровня это ровно одна страница. Ядру не нужен отдельный аллокатор под таблицы, годится обычный аллокатор страниц.

 47      39 38      30 29      21 20      12 11          0
[  VPN 1   ][  VPN 2   ][  VPN 3   ][  VPN 4   ][    VPO     ]
   PML4        PDPT         PD          PT        смещение
  512 ГБ       1 ГБ        2 МБ        4 КБ    <- покрывает одна запись

У уровней есть имена, которые ты встретишь в исходниках ядра и в документации: PML4, PDPT, PD и PT. В ядре Linux те же уровни называются PGD, PUD, PMD и PTE. Подпись под схемой показывает, сколько адресного пространства покрывает одна запись каждого уровня: запись PT это страница 4 КБ, запись PD это 512 таких страниц, 2 МБ, запись PDPT это 1 ГБ, запись PML4 это 512 ГБ. Запомни числа 2 МБ и 1 ГБ, через раздел они вернутся как размеры огромных страниц.

Старшие 16 бит 64-битного указателя в трансляции не участвуют, но и произвольными быть не могут: они обязаны повторять бит 47. Такие адреса называют каноническими. Отсюда знакомая картина: адреса процесса начинаются с 0x0000, адреса ядра с 0xffff, а между ними дыра шириной почти во все 64 бита, куда не ведёт ни один указатель.

В виджете ниже дерево таблиц для типичного процесса. Галочки включают и выключают области. Сними все и включай по одной: следи, какие узлы появляются. Потом нажми “обойти” у любой области, чтобы увидеть путь MMU при промахе TLB.

Что стоит заметить. С четырьмя обычными областями (код с данными, куча, libc, стек) дерево это 12 таблиц: один корень, три PDPT, три PD и пять PT. 12 страниц по 4 КБ, всего 48 КБ на описание процесса, у которого отображено около 7 МБ. Плоская таблица на те же 48 бит заняла бы 512 ГБ: разница больше чем в десять миллионов раз. Код и куча лежат рядом внизу и делят и PDPT, и PD, а вот куча в 4 МБ пересекает границу двух мегабайт и потому требует двух PT. Библиотека и стек оба наверху, но под разными записями PML4, 254 и 255: между ними больше 512 ГБ, и общего у них только корень.

Минимум для процесса, у которого отображена одна-единственная страница: четыре таблицы, 16 КБ. По одной на каждом уровне.

Запись таблицы по битам

Записи всех четырёх уровней устроены почти одинаково. 64 бита, из них 40 это физический адрес следующей таблицы или страницы, остальное флаги.

Бит	Имя	Смысл
0	P	present: запись действительна. Если ноль, остальные 63 бита процессор игнорирует, и ядро вольно хранить в них что угодно, например место страницы в файле подкачки
1	R/W	ноль: только чтение, единица: чтение и запись
2	U/S	ноль: доступ только из режима ядра, единица: и из пользовательского
3, 4	PWT, PCD	политика кэширования для этой страницы; нужны для памяти устройств
5	A	accessed: MMU ставит сам при любом обращении
6	D	dirty: MMU ставит сам при записи. Имеет смысл только в записи, которая указывает на страницу
7	PS	page size: в записи PD или PDPT означает, что запись указывает не на таблицу, а сразу на огромную страницу
8	G	global: трансляцию не выбрасывать из TLB при смене CR3. Так помечают страницы ядра
9 до 11		свободны для ядра
12 до 51	адрес	40 бит физического номера страницы или следующей таблицы
52 до 62		свободны для ядра; в 59 до 62 могут жить ключи защиты памяти
63	XD	execute disable: с этой страницы нельзя исполнять код

Теперь сопоставь с уроком 54. Бит SUP из книги это U/S, бит WRITE это R/W. Отдельного бита READ у x86-64 нет: всё, что present, читать можно. А бит EXEC перевёрнут: XD запрещает исполнение, а не разрешает. Это историческое: бит добавили в 2004 году, и чтобы старые таблицы с нулём в бите 63 продолжали работать, ноль пришлось сделать разрешением. Когда ты в уроке 19 просил у mmap страницу с правом EXEC для машинного кода zl, на уровне железа ядро этот бит снимало. Правило W xor X из того же урока в этих терминах звучит так: у страницы не должны одновременно стоять R/W, равный единице, и XD, равный нулю.

Права проверяются на каждом уровне, и действует самое строгое. Если запись PML4 запрещает запись, ни одна страница под ней на запись не откроется, что бы ни стояло в PT. Ядру это удобно: одним битом в верхней таблице можно закрыть сразу 512 ГБ.

Биты A и D это мост между железом и программной политикой замещения. MMU их только ставит, ядро только читает и сбрасывает. Периодически сбрасывая A и глядя, у каких страниц он успел встать снова, ядро приблизительно узнаёт, какие страницы в ходу, и строит на этом свой вариант LRU. По биту D ядро решает, надо ли писать жертву на диск или её можно просто выбросить, как мы обсуждали в уроке 53.

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

CR3 и PCID

Корень дерева лежит в CR3: биты 12 до 51 это физический адрес PML4. Смена CR3 это смена адресного пространства, и по старому правилу она выбрасывала из TLB всё, кроме глобальных записей. Процесс после каждого переключения начинал с холодным TLB и сотнями промахов подряд.

Вспомни, почему кэш данных адресуется физически: чтобы не путать одинаковые виртуальные адреса разных процессов. TLB так не может, его ключ по определению виртуальный. Значит, остаётся второй способ: приписать к ключу имя адресного пространства. Это и есть PCID: 12 младших бит CR3, которые включаются флагом в CR4. Каждая строка TLB помечается текущим PCID и попадает, только если метка совпала. Переключился на другой процесс: его строки молчат, твои лежат и ждут. Вернулся: TLB тёплый. Идентификаторов всего 4096, процессов бывает больше, поэтому ядро раздаёт их как кэш: Linux держит по несколько штук на каждое ядро процессора и переиспользует самые давние. По-настоящему PCID пригодился в 2018 году, когда после Meltdown ядро Linux стало менять таблицы страниц на каждом системном вызове: без меток это означало бы полный сброс TLB дважды на сисколл.

Пять уровней

48 бит это 256 ТБ виртуального пространства. Для серверов с терабайтами памяти и для программ, которые любят отображать огромные файлы, потолок стал виден, и Intel добавила пятый уровень, PML5. Виртуальный адрес вырос до 57 бит (128 ПБ), физический остался до 52 бит, сверху появилась ещё одна таблица на 512 записей. Включается режим флагом LA57 в CR4; железо умеет его с серверных Ice Lake 2019 года, ядро Linux с версии 4.14. Канонический адрес в этом режиме повторяет бит 56.

Цена: пятое чтение при промахе TLB, если кэши обхода не помогли. Поэтому Linux даже на машине с LA57 по умолчанию выдаёт процессу адреса ниже 47 бит, а выше только по явной просьбе: подсказкой адреса в mmap. Заодно не ломаются программы, которые прячут служебные метки в старших битах указателей (так делают некоторые виртуальные машины и сборщики мусора): при 48 битах у них 16 свободных бит, при 57 осталось бы 7.

Охват TLB и огромные страницы

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

Процессор	L1 TLB данных	TLB второго уровня	Охват L2 при 4 КБ	Охват L2 при 2 МБ
Core i7 Nehalem, 2008 (книга)	64 строки, 4 пути	512 строк, 4 пути	2 МБ	нет, L2 только для 4 КБ
Intel Skylake, 2015	64 строки, 4 пути	1536 строк, 12 путей	6 МБ	3 ГБ
Intel Golden Cove, 2021	96 строк на чтение, 16 на запись	2048 строк	8 МБ	4 ГБ
AMD Zen 4, 2022	72 строки, полностью ассоциативный	3072 строки	12 МБ	6 ГБ

Источники: для Nehalem раздел 9.7.1 книги, для Skylake и Golden Cove таблицы микроархитектур в Intel Optimization Reference Manual, для Zen 4 руководство AMD Software Optimization Guide for Family 19h. Apple параметры TLB своих ядер не публикует.

Посмотри на третий столбец глазами программиста. За семнадцать лет память серверов выросла с гигабайт до терабайт, а охват TLB на обычных страницах с 2 МБ до 12. У Zen 4 кэш L3 на кристалле 32 МБ: кэш данных покрывает больше памяти, чем TLB. Возможна ситуация, которую в уроке 38 мы представить не могли: байт лежит в кэше, а процессор не может его взять, потому что не знает физического адреса и идёт за ним по таблицам. Программа с рабочим множеством в сотни мегабайт и случайным доступом (хеш-таблица, граф, индекс базы данных) промахивается в TLB почти на каждом обращении.

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

Страница в 2 МБ

Здесь и срабатывает бит PS. Если в записи PD он равен единице, запись указывает не на таблицу PT, а сразу на физическую страницу размером 2 МБ. Обход закончился на уровень раньше, а 9 бит, которые были индексом PT, присоединяются к смещению: VPO становится 21-битным. То же на уровень выше: PS в записи PDPT даёт страницу в 1 ГБ с 30-битным смещением. В виджете выше включи две последние области, буферы с огромными страницами, и обойди их: дерево обрывается на PD и на PDPT, чтений памяти при промахе три и два.

Выигрышей два, и второй важнее.

• Обход короче на одно или два чтения.
• Одна строка TLB теперь покрывает 2 МБ вместо 4 КБ, в 512 раз больше. Охват второго уровня из мегабайт превращается в гигабайты, последний столбец таблицы.

Побочные выигрыши: таблиц нужно меньше (на буфер в 64 МБ уходит одна PD вместо 32 PT), и сбоев страниц при первом касании в 512 раз меньше.

Теперь цена. Она вся происходит из одного факта: огромная страница это 2 МБ физически непрерывной памяти, выровненной на 2 МБ.

• Фрагментация физической памяти. На свежезагруженной машине непрерывных кусков полно. Через неделю работы свободная память нарезана вперемешку с занятой, и найти 512 соседних свободных кадров ядро может, только передвинув чужие страницы. Linux умеет это делать (уплотнение памяти), но это работа, и она иногда случается прямо в твоём сбое страницы.
• Внутренняя фрагментация. Попросил 2 МБ и 1 байт: получил 4 МБ. Тронул один байт огромной страницы: в физической памяти появились все 2 МБ, а не 4 КБ. Программа с разреженным доступом на огромных страницах может занимать в разы больше памяти. Это известная проблема Redis и некоторых баз данных, и их документация прямо советует огромные страницы отключать.
• Дорогой первый сбой. Страницу надо обнулить перед выдачей, иначе процесс увидит чужие данные. Обнулить 2 МБ это десятки микросекунд, на два порядка дольше, чем 4 КБ. В среднем на байт выходит дешевле, но программа, чувствительная к задержкам, получает редкие длинные паузы.
• Грубая гранулярность всего остального. Права, копирование при записи после fork (до него мы дойдём в следующем уроке), выгрузка на диск: всё это работает постранично. Одна запись в огромную страницу после fork копирует 2 МБ. Поэтому ядро при первой возможности раскалывает огромную страницу обратно на 512 обычных.

В Linux есть два способа получить огромные страницы. Явный, через hugetlbfs: администратор заранее резервирует пул, программа отображает файлы из особой файловой системы или зовёт mmap с флагом MAP_HUGETLB. Пул зарезервирован навсегда и другим недоступен, зато выдача гарантирована; страницы в 1 ГБ доступны только так. И прозрачный, THP: ядро само подставляет страницы по 2 МБ под обычные анонимные области. У THP три режима, текущий виден в /sys/kernel/mm/transparent_hugepage/enabled: always (везде, где получится), never и madvise (только там, где программа попросила вызовом madvise с советом MADV_HUGEPAGE). Третий режим самый честный: программа лучше ядра знает, какой из её буферов большой, плотно используемый и долгоживущий. Им мы сейчас и воспользуемся.

Почему L1 индексируется битами смещения

Осталась одна неувязка. Мы сказали, что кэш адресуется физически. Значит, сначала трансляция, потом поиск в кэше? Даже с попаданием TLB это последовательно два шага, а L1 обязан отвечать за три или четыре такта.

Фокус в том, что часть физического адреса известна до трансляции. Смещение не транслируется: младшие 12 бит физического адреса равны младшим 12 битам виртуального. Возьмём типичный L1: 32 КБ, 8 путей, линия 64 байта. Наборов 32 КБ делить на 8 и на 64, то есть 64: индекс набора это 6 бит. Смещение в линии это ещё 6 бит. Вместе 12. Ровно VPO.

Поэтому L1 работает так. Процессор выдаёт виртуальный адрес. Одновременно происходят две вещи: TLB ищет PPN по VPN, а кэш по младшим 12 битам выбирает набор и достаёт из него все восемь тегов. К моменту, когда TLB отдал PPN, теги уже лежат наготове, и остаётся сравнить: тег кэша это и есть PPN. Кэш индексируется виртуально, а тегируется физически, отсюда название VIPT. Но поскольку индекс взят целиком из смещения, результат неотличим от честного физически адресованного кэша: проблем с одинаковыми виртуальными адресами разных процессов не возникает.

Вспомни учебную систему. Там CI и CO вместе занимали 6 бит и совпадали с PPO, а CT совпадал с PPN. Авторы книги подобрали параметры так, чтобы маленькая система обладала тем же свойством, что настоящий L1.

У трюка жёсткое следствие: индекс и смещение в линии обязаны уместиться в смещение страницы. Иначе говоря, один путь L1 не может быть больше страницы. При страницах 4 КБ путь это 4 КБ, и нарастить L1 можно только ассоциативностью. Проверь по истории: 32 КБ при 8 путях держались у Intel от Nehalem до Skylake, потом стало 48 КБ, и путей стало 12. У Zen 4 те же 32 КБ и 8 путей. А у Apple M4 L1 данных 128 КБ при 8 путях: путь 16 КБ, потому что страница на Apple Silicon 16 КБ. Домашнее задание урока 38 просило проверить это правило на своей машине, теперь ты знаешь, откуда оно берётся. L2 и L3 этим не связаны: они ищут уже по готовому физическому адресу и могут быть любого размера.

Измеряем промах TLB

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

Идея эксперимента: два обхода с одинаковым числом обращений и одинаковым числом линий кэша, но разным числом страниц. Берём область в 512 МБ, в ней 131072 страницы по 4 КБ. Плотный обход читает 131072 байта с шагом 64: каждое обращение в новую линию кэша, все линии в первых 8 МБ, страниц задето 2048. Редкий обход читает 131072 байта с шагом в страницу: снова каждое обращение в новую линию, линий столько же, но страниц задето 131072. Нагрузка на кэш одинаковая, нагрузка на TLB отличается в 64 раза. Порядок в обоих случаях псевдослучайный, чтобы предвыборка не угадывала следующий адрес.

const std = @import("std");
const builtin = @import("builtin");

const region_bytes = 512 << 20;
const huge_bytes = 2 << 20;
const line_bytes = 64;
const rounds = 8;

/// Читает lines байтов с шагом stride в псевдослучайном порядке и возвращает сумму.
/// Порядок задаёт линейный конгруэнтный генератор с полным периодом: каждый
/// индекс от 0 до lines - 1 встречается ровно один раз, а предвыборка шага не угадывает.
/// При шаге больше линии кэша байт берётся не с начала куска, а со сдвигом,
/// который зависит от индекса: иначе все адреса попали бы в одни и те же наборы кэша.
fn walk(region: []const u8, lines: usize, stride: usize) u64 {
    const slots = stride / line_bytes;
    var sum: u64 = 0;
    var x: usize = 0;
    for (0..lines) |_| {
        x = (x *% 1664525 +% 1013904223) & (lines - 1);
        sum += region[x * stride + (x % slots) * line_bytes];
    }
    return sum;
}

fn medianNs(io: std.Io, region: []const u8, lines: usize, stride: usize, sink: *u64) u64 {
    var samples: [rounds]u64 = undefined;
    for (&samples) |*sample| {
        const started = std.Io.Clock.awake.now(io);
        sink.* +%= walk(region, lines, stride);
        sample.* = @intCast(started.durationTo(std.Io.Clock.awake.now(io)).nanoseconds);
    }
    std.mem.sort(u64, &samples, {}, std.sort.asc(u64));
    return samples[rounds / 2];
}

pub fn main(init: std.process.Init) !void {
    var buf: [4096]u8 = undefined;
    var w = std.Io.File.stdout().writer(init.io, &buf);
    const out = &w.interface;

    var args = init.minimal.args.iterate();
    _ = args.skip();
    const want_huge = if (args.next()) |arg| std.mem.eql(u8, arg, "huge") else false;

    // Запас в 2 МБ, чтобы начало области можно было выровнять на границу огромной страницы.
    const raw = try std.posix.mmap(
        null,
        region_bytes + huge_bytes,
        .{ .READ = true, .WRITE = true },
        .{ .TYPE = .PRIVATE, .ANONYMOUS = true },
        -1,
        0,
    );
    defer std.posix.munmap(raw);
    const skip = std.mem.alignForward(usize, @intFromPtr(raw.ptr), huge_bytes) - @intFromPtr(raw.ptr);
    const region: []align(std.heap.page_size_min) u8 = @alignCast(raw[skip..][0..region_bytes]);

    if (want_huge) {
        if (builtin.os.tag != .linux) return error.HugePagesNeedLinux;
        try std.posix.madvise(region.ptr, region.len, std.os.linux.MADV.HUGEPAGE);
    }

    // Первое касание: каждая страница приходит через сбой страницы.
    const page = std.heap.pageSize();
    const pages = region_bytes / page;
    const started = std.Io.Clock.awake.now(init.io);
    for (0..pages) |i| region[i * page] = @truncate(i);
    const touch_ns: u64 = @intCast(started.durationTo(std.Io.Clock.awake.now(init.io)).nanoseconds);

    var sink: u64 = 0;
    const dense = medianNs(init.io, region, pages, line_bytes, &sink);
    const sparse = medianNs(init.io, region, pages, page, &sink);

    const n: f64 = @floatFromInt(pages);
    try out.print("страница {d} КБ, страниц {d}, огромные страницы: {s}\n", .{ page / 1024, pages, if (want_huge) "просили" else "нет" });
    try out.print("первое касание: {d:.0} нс на страницу\n", .{@as(f64, @floatFromInt(touch_ns)) / n});
    try out.print("плотно, шаг 64 байта:   {d:.2} нс на обращение, страниц задето {d}\n", .{ @as(f64, @floatFromInt(dense)) / n, pages * line_bytes / page });
    try out.print("редко, шаг в страницу: {d:.2} нс на обращение, страниц задето {d}\n", .{ @as(f64, @floatFromInt(sparse)) / n, pages });
    try out.print("контрольная сумма {d}\n", .{sink});
    try out.flush();
}

Три места требуют пояснений.

Сдвиг внутри страницы. Первая версия этой программы читала первый байт каждой страницы, и редкий обход выходил втрое медленнее плотного даже там, где TLB был ни при чём. Причина из урока 38: адреса с шагом ровно 4096 имеют одинаковые младшие 12 бит, а именно из них L1 берёт индекс набора. Все 131072 обращения ломились в один набор из 64, и мы мерили конфликтные промахи кэша. Сдвиг (x % slots) * line_bytes раскидывает обращения по всем наборам. Мораль шире этого урока: замер, в котором не отделены друг от друга два эффекта, не измеряет ни один из них.

Выравнивание. Огромная страница обязана начинаться на границе 2 МБ, а mmap выравнивает только на 4 КБ. Просим на 2 МБ больше, чем нужно, и отступаем от начала до ближайшей границы. munmap при этом получает исходный срез raw, а не выровненный.

Первое касание. mmap памяти не выдаёт, он только заводит область, как мы видели в уроке 54. Кадры появляются в цикле первого касания, по сбою страницы на каждую. Заодно измерим и его.

Программа собрана с -O ReleaseFast. Машина: Apple M4 Max. Linux запущен на ней же в виртуальной машине (OrbStack, ядро 7.0, arm64, страница 4 КБ), THP в режиме madvise. Каждый режим запускался три раза, ниже медианный прогон. Машина в это время была занята другими задачами, так что разброс заметный: редкий обход на обычных страницах давал от 8,1 до 10,4 нс, остальные строки гуляли в пределах 5 процентов. Выводы ниже от такого разброса не зависят.

$ zig build-exe -O ReleaseFast -target aarch64-linux-musl tlbcost.zig
$ ./tlbcost                                         # Linux, обычные страницы
страница 4 КБ, страниц 131072, огромные страницы: нет
первое касание: 180 нс на страницу
плотно, шаг 64 байта:   1.51 нс на обращение, страниц задето 2048
редко, шаг в страницу: 8.27 нс на обращение, страниц задето 131072
контрольная сумма 3661824

$ ./tlbcost huge                                    # Linux, MADV_HUGEPAGE
страница 4 КБ, страниц 131072, огромные страницы: просили
первое касание: 40 нс на страницу
плотно, шаг 64 байта:   1.56 нс на обращение, страниц задето 2048
редко, шаг в страницу: 4.66 нс на обращение, страниц задето 131072
контрольная сумма 3661824

Сначала проверим, что ядро действительно дало огромные страницы: madvise это совет, а не приказ. Пока программа работает, в /proc/<pid>/smaps_rollup есть строка AnonHugePages. С аргументом huge она показывала 524288 kB, то есть все 512 МБ легли на страницы по 2 МБ; без аргумента 0 kB.

Теперь числа.

Плотный обход: 1,5 нс в обоих режимах. 2048 страниц помещаются в TLB второго уровня, трансляция бесплатна, огромным страницам нечего улучшать. Это контрольная группа: она показывает, что огромные страницы сами по себе ничего не ускоряют, они только убирают промахи TLB там, где те есть.

Редкий обход на обычных страницах: 8,3 нс, в 5,5 раза медленнее плотного. Число обращений то же, число линий кэша то же. Вся разница, почти 7 нс на обращение, это цена трансляции: 131072 страницы против охвата в несколько тысяч строк. Одних PTE здесь на мегабайт, и они сами перестают помещаться в L1.

Редкий обход на огромных страницах: 4,7 нс. Страниц стало 256, TLB хватает с запасом, и время упало почти вдвое. Но не до 1,5 нс, и это стоит честно отметить. Остаток я до конца объяснить не могу, у меня есть только правдоподобная версия. Замер шёл в виртуальной машине. Там трансляция двухступенчатая: адрес гостя переводится в “физический” адрес гостя, а тот ещё раз, уже таблицами гипервизора, в настоящий физический. В TLB лежит итог обеих ступеней, и размер такой склеенной записи равен меньшей из двух страниц. Хозяин здесь macOS со страницами 16 КБ, так что гостевая огромная страница, вероятно, дробится в TLB на куски по 16 КБ: 32768 записей вместо 256. Это лучше, чем 131072, но всё ещё больше охвата. На Linux без виртуализации на x86-64 с той же программой жди, что обе строки режима huge почти сравняются. Проверь, если есть такая машина: это второе домашнее задание.

Первое касание: 180 нс против 40 нс на каждые 4 КБ. С обычными страницами это 131072 сбоя по 180 нс. С огромными сбоев 256, и каждый стоит около 20 мкс (40 нс умножить на 512): обнулить 2 МБ дольше, чем 4 КБ, но в пересчёте на байт вчетверо дешевле, потому что вход в ядро и выход из него оплачиваются один раз на 2 МБ. Обе стороны медали в одном числе: пропускная способность выросла, а самая длинная пауза стала в сто раз длиннее.

На macOS. Программа собирается и работает напрямую, без аргумента huge: вызов madvise с MADV_HUGEPAGE существует только в Linux, и программа в этом случае завершается с ошибкой HugePagesNeedLinux. Огромных страниц для пользовательских процессов на Apple Silicon нет вообще. Зато базовая страница там 16 КБ, и это заметно. На том же M4 Max в тихий момент вывод такой: страниц 32768, первое касание 724 нс на страницу, плотно 1,50 нс, редко 1,72 нс. Редкий обход медленнее всего на 15 процентов, а не в пять раз. Страниц вчетверо меньше, все PTE занимают 256 КБ и живут в кэше, а обход таблиц у Apple, судя по результату, очень хорошо спрятан за внеочередным исполнением. Под нагрузкой от соседних процессов оба числа у меня вырастали вдвое (3,25 и 3,77 нс), но отношение оставалось тем же. Первое касание страницы в 16 КБ стоит вчетверо дороже, чем страницы в 4 КБ под Linux, то есть в пересчёте на байт столько же. Таблицы страниц на ARM64 устроены по тому же принципу, что на x86-64: дерево, четыре уровня при страницах 4 КБ (при 16 КБ индексы шире, по 11 бит), запись 8 байт с теми же по смыслу флагами, только называются они иначе, а вместо PCID метка адресного пространства зовётся ASID.

Что из этого вынести в обычную работу. Огромные страницы это инструмент для конкретного профиля: большой, долгоживущий, плотно заполненный буфер со случайным доступом. Кэш базы данных, куча виртуальной машины, большой хеш-индекс, матрицы в численных расчётах. Для всего остального обычные страницы лучше. И, как всегда в этом блоке уроков: сначала измерь. На Linux x86-64 perf stat -e dTLB-load-misses,dTLB-loads покажет долю промахов TLB в твоей программе за одну команду, и если она меньше процента, этот раздел не про тебя.

Практика

В задаче ты пишешь MMU учебной системы: один метод translate структуры Mmu. Заготовка даёт типы с зашитыми ширинами (Va это u14, Pa это u12, Ppn это u6), TLB на четыре набора по четыре строки, таблицу страниц на 256 PTE, счётчик обращений clock, счётчик походов в таблицу walks и готовую функцию join, которая собирает физический адрес. Кэша в задаче нет: работа MMU заканчивается на физическом адресе.

От модели из урока задача отличается только тем, что писать её тебе, и тем, что тесты строже глаза. Они грузят состояние TLB и таблицы страниц сквозного примера, включая мусорные теги в недействительных строках, и проверяют адреса, разобранные выше и в упражнениях ниже. Отдельно проверяется то, на чём обычно ошибаются: недействительная строка с подходящим тегом это промах; сбой страницы не меняет TLB; новая строка занимает первую свободную клетку и не трогает соседей; из полного набора уходит строка, которую дольше всех не трогали, причём попадание тоже обновляет возраст; тег это весь остаток VPN, и страницы 0x0f и 0xcf не путаются.

Упражнения

Итоги

• Трансляция адреса это замена VPN на PPN; смещение переезжает в физический адрес без изменений. Попадание страницы обслуживает только железо (MMU), сбой страницы обслуживают вместе железо и ядро: MMU возбуждает исключение, обработчик выбирает жертву, подкачивает страницу, правит PTE и перезапускает инструкцию.
• Кэш процессора адресуется физически: так его не путают одинаковые виртуальные адреса разных процессов, а разделяемые страницы греют его всем сразу. PTE тоже читаются через кэш.
• TLB это множественно-ассоциативный кэш PTE внутри MMU. Младшие t бит VPN это индекс набора TLBI, остальные это тег TLBT. Попадание TLB обходится без единого обращения к памяти. При промахе MMU сам идёт по таблицам и кладёт PTE в TLB; недействительные PTE туда не попадают.
• TLB хранит копии, поэтому после правки таблицы страниц ядро обязано выбросить устаревшую строку (invlpg, перезапись CR3), а на многоядерной машине разослать просьбу всем ядрам. Это TLB shootdown, и из-за него munmap и mprotect дороже, чем выглядят.
• Плоская таблица страниц на 48 бит занимает 512 ГБ на процесс. Дерево хранит только те таблицы, под которыми есть отображённые страницы: четыре обычные области типичного процесса это 12 таблиц и 48 КБ. Платой служит длина обхода: k уровней это k зависимых чтений при промахе TLB, которые смягчаются кэшами обхода и тем, что верхние таблицы не покидают L1.
• x86-64: 48 бит адреса, четыре индекса по 9 бит (PML4, PDPT, PD, PT) и 12 бит смещения; каждая таблица это ровно одна страница из 512 записей по 8 байт. Запись: P, R/W, U/S, A, D, PS, G, 40 бит адреса, XD. Права проверяются на каждом уровне, действует самое строгое. A и D ставит железо, читает и сбрасывает ядро. При P, равном нулю, остальные биты принадлежат ядру.
• CR3 хранит физический адрес PML4 и 12-битный PCID. Метка адресного пространства в строках TLB позволяет не сбрасывать TLB при переключении процессов. Пятый уровень (LA57) расширяет адрес до 57 бит ценой ещё одного чтения при обходе.
• Охват TLB равен числу строк на размер страницы: у процессоров начала 2020-х это 8 до 12 МБ на страницах 4 КБ, меньше кэша L3. Огромные страницы (бит PS в записи PD или PDPT, 2 МБ или 1 ГБ) укорачивают обход и расширяют охват в 512 раз. Платят за это физически непрерывной памятью, внутренней фрагментацией, долгим первым сбоем и грубой гранулярностью COW и выгрузки. В Linux их дают hugetlbfs и THP; честный режим это madvise(MADV_HUGEPAGE) на конкретный буфер.
• L1 индексируется битами смещения страницы, которые известны до трансляции, а тегом служит PPN из TLB: поиск в кэше и в TLB идут параллельно. Отсюда ограничение: один путь L1 не больше страницы, и L1 растёт только ассоциативностью (или страницей, как у Apple).
• Замер на M4 Max под Linux в виртуальной машине: 131072 обращения к 2048 страницам стоят 1,5 нс каждое, к 131072 страницам 8,3 нс при том же числе линий кэша. MADV_HUGEPAGE снижает второе число до 4,7 нс и вчетверо удешевляет первое касание. На macOS со страницами 16 КБ разница всего 15 процентов. Наивная версия того же замера мерила конфликтные промахи L1, а не TLB.

Дальше

Теперь ты знаешь, что происходит между указателем в программе и байтом в кристалле памяти, вплоть до отдельных бит в записи таблицы. В следующем уроке посмотрим, как ядро этим механизмом пользуется по-крупному. mmap привязывает область к файлу, и страницы приезжают с диска по сбою. fork копирует не память, а таблицы страниц, снимает в них бит R/W и ждёт первой записи: это копирование при записи, и бит R/W из сегодняшней таблицы окажется его главным героем. execve выбрасывает старые области и заводит новые. Там же у сегодняшней модели появится настоящее применение: процессор Y86 получит MMU с таблицей страниц и TLB, сбой страницы станет ещё одним исключением в его таблице, а у каждого процесса его маленькой системы будет своё адресное пространство. Параметры возьмём те же, что в сквозном примере, так что все сегодняшние числа ты сможешь проверить на машине, которую собрал сам.