Гостиница с номерами

Прошлая глава закончилась опытом, который не укладывается в голове. Программа на C раздваивается вызовом fork, ребёнок меняет переменную, и оба процесса печатают её адрес. Адрес один и тот же, а значения разные: у ребёнка 99, у родителя 10. Если адрес — номер ячейки памяти, как мы считали с главы 14, в одной ячейке не могут одновременно лежать два числа. Значит, адрес, который видит программа, — не номер ячейки. Каждой программе кажется, что вся память принадлежит ей одной. Чтобы понять, как держится эта иллюзия, во что обходится и где ломается, придётся поработать портье.

Номер на ключе и номер комнаты

Представьте гостиницу со странными правилами. Каждый гость получает ключи с номерами от первого до миллионного — как будто весь отель его. Комнат в здании всего несколько сотен, и номер на ключе с номером комнаты не совпадает. Когда гость идёт к «своему» номеру 4012, портье открывает книгу этого гостя, находит строку «4012» и отводит его в комнату 37. У соседа тоже есть ключ 4012, но в его книге напротив этого номера записана комната 108. Гости друг друга не встречают и не могут встретить: в чужую комнату их никто не поведёт.

Так устроена память всякого современного компьютера. Числа, которыми программа называет ячейки, — виртуальные адреса, номера на ключах. Номера ячеек в самих микросхемах — физические адреса, комнаты. Набор всех виртуальных адресов, которыми может пользоваться процесс, — его адресное пространство: у каждого процесса оно своё, поэтому одно и то же число в двух процессах ведёт в разные ячейки. Всю эту систему перевода называют виртуальной памятью. Портье — это блок внутри процессора, MMU (memory management unit), и он переводит каждый адрес при каждом обращении к памяти — миллиарды раз в секунду.

Своё адресное пространство можно увидеть. Ядро Linux держит его карту в файле /proc/self/maps — по строке на каждую область: где начинается, где кончается, что с ней можно делать и откуда она взялась. Найдём на карте, где живут список, большой буфер, машинный код самого Python и стек.

Микроскоп ctypes из главы 14 нашёл три адреса: самого списка, данных буфера и одной функции внутри интерпретатора, написанной на C. Список живёт в большой безымянной области, где Python раскладывает свои мелкие объекты. Десяти мегабайтам буфера досталась отдельная область по их размеру. Машинный код лежит в области, отображённой из файла библиотеки libpython. Второй столбец — права: r — читать, w — писать, x — исполнять как команды, p — область частная, своя у процесса. У данных права rw-p, у кода r-xp: код можно выполнять, но нельзя переписывать. Областей около сотни, и между ними — огромные пустоты, адреса, которых процессу никто не выдавал. А переменная x из прошлой главы была выдана обоим процессам — только в двух книгах против одного номера стоят разные комнаты.

Манчестер, 1962. Память в один уровень

В 1960-х виртуальная память появилась в машинах Burroughs и IBM, в 1970-х стала обычной на больших машинах, а в персональные компьютеры пришла с процессорами Intel: у 80286 (1982) — сегментами, у 80386 (1985) — страницами, как в этой главе. Сегодня без неё не работает ни один телефон. Посмотрим, как портье управляется с книгой, если комнат миллионы, а гостей сотни.

Страницы и комнаты

Первая трудность видна сразу: книга, где записан каждый адрес, была бы больше самой памяти. Поэтому, как в Atlas, перевод делают кусками. Адресное пространство режут на страницы — обычно по 4096 байт, — а физическую память на кадры того же размера. Страница, как гость, может жить в любом кадре, и внутри страницы ничего не переставляется: байт номер 100 страницы окажется байтом номер 100 кадра. Поэтому адрес делится на две части. $4096 = 2^{12}$, так что младшие 12 бит — смещение внутри страницы, а всё, что старше, — номер страницы. Это сдвиг и маска из главы 28: номер страницы — address >> 12, смещение — address & 0xFFF.

Книга портье — таблица страниц. Для каждой страницы процесса в ней записано, в каком кадре она лежит, и несколько флагов: есть ли страница в памяти вообще, можно ли в неё писать, можно ли исполнять её как код, доступна ли она обычной программе или только ядру. Ещё два флага ставит сам процессор: «к странице обращались» и «в страницу писали». Перевод адреса — одна строка: найти в таблице кадр страницы и приставить к нему то же смещение. Встаньте за стойку портье сами.

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

Книга в четыре тома

Вторая трудность — размер самой книги. У процессора x86-64 виртуальный адрес занимает 48 бит. Страниц в таком пространстве $2^{48} / 2^{12} = 2^{36}$, около 69 миллиардов, и если на каждую завести строку в 8 байт, таблица одного процесса заняла бы 512 ГиБ. Но процесс пользуется крошечной долей своего пространства — мы видели на карте около сотни областей среди пустоты. Поэтому книгу делают деревом. Номер страницы режут ещё на четыре куска по 9 бит. Первый кусок выбирает строку в оглавлении, оглавление указывает на том, второй кусок выбирает строку в томе — и так четыре раза, пока последняя строка не назовёт кадр. В каждой таблице $2^9 = 512$ строк по 8 байт — ровно одна страница. А тома без единой выданной страницы не заводят вовсе. Это тот же бор из главы 27, только буквы в нём — куски адреса по 9 бит.

Четыре числа от 0 до 511 — путь портье по четырём томам к кадру, где лежит список. Числа у вас будут другими: система раскладывает области по адресному пространству случайно, чтобы взломщику было труднее угадать, где что лежит. Новым процессорам и 48 бит мало, и у них есть пятый том — 57-битные адреса.

Записная книжка портье

Четыре тома — это четыре лишних чтения памяти на каждое обращение программы, а обращений миллиарды. Если бы MMU листал книгу при каждом обращении, память стала бы впятеро медленнее. Спасает то же, что спасало в главе 34, — локальность. Программа обращается к одним и тем же страницам снова и снова: подряд по массиву, в одну и ту же функцию, на вершину стека. Поэтому у портье есть записная книжка на несколько последних переводов — TLB (translation lookaside buffer), кэш переводов внутри процессора. В нём от нескольких десятков до пары тысяч строк «страница — кадр», и обычно больше 99 % обращений находят перевод там, не открывая книгу.

У книжки есть одна неприятность, и мы её уже встречали. Перевод зависит от процесса: страница 0x1 гостя A и страница 0x1 гостя B — разные комнаты. Поэтому при переключении контекста из прошлой главы записи старого процесса в TLB становятся бесполезны: либо книжку стирают, и новый процесс начинает с промахов, либо каждую запись помечают номером процесса. Это ещё одна скрытая цена переключения. А программы, которым нужны гигабайты, — базы данных, обучение нейросетей — просят у системы огромные страницы по 2 МиБ или даже 1 ГиБ: одна строка книжки покрывает тогда в 512 или в 262 144 раза больше памяти.

Ночной звонок: страничное прерывание

Бывает, что в книге против номера стоит «комнаты нет». Тогда портье будит хозяина гостиницы. Процессор, не найдя страницу в памяти, поднимает страничное прерывание (page fault). Это такое же прерывание, как в прошлой главе, только поднимает его не таймер, а сама команда программы. Ядро операционной системы смотрит, что это за страница. Если её вообще не выдавали — это ошибка программы, о ней ниже. Если выдавали, ядро находит свободный кадр, кладёт туда нужное, записывает кадр в таблицу и выполняет команду заново. Программа ничего не замечает, кроме задержки.

На страничных прерываниях держится ленивость виртуальной памяти. Когда программа просит память, система ничего не кладёт в кадры: она только записывает в книгу, что такие номера выданы. Кадр появится при первой записи. Песочнице курса дают 256 МБ физической памяти. Попросим 600.

Модуль mmap просит у ядра кусок адресного пространства напрямую — так же Python и сам берёт память под большие объекты. Ядро согласилось выдать 600 МБ адресов — больше, чем есть в песочнице, — и в микросхемах не прибавилось ни килобайта. Тронули 100 МБ — и занято стало ровно на 100 МБ больше. Первая запись в каждую страницу стоит заметно дороже второй: в её цену входят страничное прерывание, вход в ядро, поиск и обнуление свободного кадра. Вторая запись — только запись. На сервере курса разница ещё больше: там прерывание обрабатывает дополнительная защитная прослойка. Попросите вместо 600 целых 1200 МБ, и mmap откажет: на адреса у песочницы стоит отдельный предел в гигабайт.

Поэтому в любом диспетчере задач у программы две цифры памяти. Одна — сколько адресов она себе взяла, другая — сколько кадров действительно занимает; в Linux их называют VSZ и RSS. Первая бывает огромной и почти ничего не значит. Если программа «весит» десять гигабайт виртуальной памяти, а резидентной — двести мегабайт, у соседей она отняла только эти двести.

Пристройка: подкачка

Благодаря ленивости адресов можно раздать больше, чем есть памяти. Но гости могут и правда въехать все разом. Тогда хозяин гостиницы переселяет кого-нибудь в пристройку. Ядро выбирает кадр, записывает его содержимое на диск в специальный файл или раздел — область подкачки (swap), — отмечает в таблице страниц бывшего жильца «в пристройке» и отдаёт освободившийся кадр новому. Когда выселенная страница понадобится, случится страничное прерывание, и ядро принесёт её с диска обратно, выселив кого-то ещё. Если страницу с момента заселения не меняли — например, это код программы, — писать её на диск не нужно: копия и так лежит в файле программы. Для этого процессор и отмечает в таблице, писали ли в страницу.

Иллюзия бесконечной памяти держится, пока в пристройку переселяют тех, кто долго не понадобится. Но диск страшно медленнее памяти: обращение к памяти — около десятой доли микросекунды, к быстрому SSD — около сотни микросекунд, к старому жёсткому диску — миллисекунды. Каждый промах обходится в тысячу, а то и в сто тысяч обращений к памяти. Пусть программа ходит по кругу по пятидесяти страницам, а комнат ей досталось то больше, то меньше. Выселяем, как в главе 34, того, кто дольше всех не нужен (LRU).

Пока комнат не меньше пятидесяти, промахи случаются только на первом круге, когда страницы заселяются впервые. Стоит отнять одну комнату — и промахом становится каждое обращение, а средняя цена подскакивает почти в сорок раз, сразу, без всякого постепенного замедления. LRU на круге чуть больше памяти ошибается всегда (мы видели это в главе 34), но и другие правила здесь мало помогут: страниц, которые нужны прямо сейчас, больше, чем комнат. Набор страниц, которыми программа пользуется в ближайшее время, Питер Деннинг в 1968 году назвал рабочим набором. Если рабочие наборы всех процессов не помещаются в память, система почти всё время возит страницы туда и обратно, а полезная работа стоит. Это пробуксовка (thrashing). Её симптомы знакомы каждому: компьютер перестаёт откликаться, диск работает без остановки, а процессор при этом почти свободен — все ждут диска. Лекарство одно: закрыть часть программ, чтобы рабочие наборы оставшихся поместились.

Кого переселить

Правила выбора вы знаете по главе 34: по приходу (FIFO), того, кто дольше всех не нужен (LRU), случайного — и недостижимый идеал Белади: выселять того, кто понадобится позже всех. У страниц тут своя трудность. Кэш процессора следит за каждым обращением сам, в железе. А вести точный LRU для страниц ядро не может: пришлось бы передвигать страницу в списке при каждом обращении к памяти, миллиарды раз в секунду. Зато у ядра есть флаг «к странице обращались», который процессор ставит сам.

На этом флаге построено правило часов, или «второго шанса». Кадры стоят по кругу, как цифры на циферблате, и по ним ходит стрелка. Нужно освободить кадр — стрелка смотрит на флаг очередного. Флаг поднят — к странице недавно обращались: стрелка опускает флаг, оставляет страницу и идёт дальше. Флаг опущен — с прошлого оборота стрелки страницей никто не пользовался, её и переселяют. Один бит на страницу вместо списка — и выбор почти такой же разумный, как у LRU. В современных системах работают усложнённые потомки этих часов.

Больше комнат — больше переселений

Пример из той статьи умещается в двенадцать обращений. Гости стучатся в страницы 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5. Проживём их с тремя комнатами и с четырьмя, выселяя того, кто въехал раньше всех.

С тремя комнатами — девять промахов, с четырьмя — десять. Где всё ломается, видно в седьмой строке, когда приходит пятёрка. В трёх комнатах к этому моменту живут 4, 1, 2: единица и двойка только что въехали заново, они молодые, и выселяют четвёрку. В четырёх комнатах промахов не было, единица живёт с самого начала — она самая старая, и выселяют её. А следом приходят как раз 1 и 2. Правило по приходу смотрит, когда страница въехала, а не когда она нужна, и лишняя комната меняет порядок заселения так, что выселяется не тот.

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

Кривые LRU и OPT не поднимаются никогда, сколько ни ищи, и это можно доказать.

Правила с таким свойством — содержимое меньшей памяти всегда входит в содержимое большей — позже назвали стековыми; к ним относятся LRU и OPT. FIFO это свойство нарушает, и седьмая строка ячейки показывает как: в трёх комнатах живут 1, 2, 5, в четырёх — 2, 3, 4, 5, и единицы там нет. Часы тоже не стековые и тоже бывают аномальны. Насколько аномалия редка, проверим на двадцати тысячах случайных строк.

Несколько десятков строк из двадцати тысяч — у FIFO, ни одной — у LRU, как и обещает теорема. Редкость, но не диковина. Белади с соавторами строили строки, где FIFO с лишней памятью промахивался почти вдвое чаще, и предполагали, что больше чем вдвое не бывает. А в 2010 году Форнаи и Иваньи показали, что у FIFO отношение промахов «больше памяти» к «меньше памяти» может быть сколь угодно большим.

Замки на дверях

Книга портье ещё и охраняет гостей. У каждой страницы в таблице есть права: можно ли из неё читать, писать в неё, исполнять её как код, пускать ли туда обычную программу или только ядро. MMU проверяет их при каждом обращении — заодно с переводом, бесплатно. Нарушение тоже вызывает страничное прерывание, только на этот раз ядро видит, что страница на месте, но запрещена, или что такого адреса процессу вообще не выдавали. Чинить тут нечего, и ядро посылает программе сигнал SIGSEGV, номер 11. Если программа его не перехватила, она умирает с сообщением, которое знает каждый, кто писал на C: segmentation fault. Слово segment осталось от более старой схемы защиты, в которой память делили на сегменты.

Самый частый случай — нулевой указатель. Страницу с адресом 0 система нарочно не выдаёт никому, поэтому обращение по NULL ловится всегда и не портит тихо чужие данные. Второй случай — запись туда, куда нельзя. Вызов mprotect меняет права страницы прямо на ходу: повесим на комнату замок «только чтение» и попробуем в неё написать.

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

Становится понятной и смерть рекурсии без базового случая из главы 33: под стеком система оставляет невыданные страницы, и, когда кадры дорастают до них, MMU поднимает тревогу. Python до такого не доводит: он сам проверяет и глубину рекурсии, и границы списков и бросает исключение с трейсбеком. Но в Python тоже бывает segfault — в расширениях на C или через ctypes. Тогда процесс умирает молча. Помогает модуль faulthandler: при аварии он успевает напечатать, в какой строке Python это случилось.

Код завершения −11 значит «убит сигналом 11». Без faulthandler — ни слова, с ним — строка, на которой всё случилось. Запомните ключ -X faulthandler (или переменную окружения PYTHONFAULTHANDLER=1): если программа на Python с библиотеками на C иногда исчезает без трейсбека, это первый шаг.

Те же замки охраняют ядро. Память ядра отображена в адресное пространство каждого процесса, но её страницы помечены «только для ядра», и обычная программа получает SIGSEGV при первой же попытке туда заглянуть. Именно эту стену пробила атака Meltdown из главы 35: процессор проверял права слишком поздно и успевал начерно прочитать запретное. Заплатка 2018 года убрала ядро из таблиц страниц обычных процессов почти целиком — остался лишь крошечный кусок, через который в ядро входят и выходят, — и каждый системный вызов стал чуть дороже: теперь при входе в ядро и выходе из него меняется сама книга портье.

Одна комната на двоих

Вернёмся к загадке прошлой главы. fork делает копию процесса со всей его памятью. Если процесс занимает гигабайт, копировать гигабайт при каждом таком вызове было бы разорительно, тем более что оболочка запускает каждую команду через fork и сразу exec и скопированное тут же выбрасывает. Поэтому ядро копирует только книгу. Обе книги указывают на те же комнаты, а все страницы, куда можно писать, ядро помечает в обеих книгах «только чтение». Пока родитель и ребёнок читают, они живут в одних и тех же кадрах. Первая же запись — нарушение защиты, страничное прерывание. Ядро видит, что страница общая и замок на ней временный, копирует её в новый кадр для того, кто пишет, и снимает замок. Это копирование при записи (copy-on-write). Ребёнок из прошлой главы записал 99 в свою x — и в этот момент получил собственную страницу с тем же номером на ключе.

Проверим на пределе песочницы. Программа занимает 150 МБ и рожает троих детей. Если бы fork копировал память, понадобилось бы 600 МБ, а у песочницы всего 256, и программу убили бы.

Три копии процесса в 150 МБ появились за миллисекунду-другую и все дожили до конца: каждый ребёнок прочитал все 38 400 страниц, а скопированы были только те десять, в которые он писал. То же можно увидеть в комнатах виджета «Портье»: нажмите fork и запишите что-нибудь в стек от имени C. Копирование при записи живёт не только в fork. На нём построены снимки файловых систем и некоторых баз данных: снимок ничего не копирует, пока данные не начнут меняться.

У этого приёма в Python есть враг — счётчик ссылок, о котором следующий раздел. Даже чтение объекта меняет его счётчик, то есть пишет в страницу, где объект лежит. Поэтому дети серверного процесса на Python, созданные через fork, понемногу копируют себе почти всю общую память. Для таких серверов в Python 3.7 появилась функция gc.freeze(): её зовут перед fork, чтобы сборщик мусора хотя бы сам не трогал старые объекты.

Уборка в номерах: память Python

Ядро выдаёт процессу страницы, а внутри них Python раскладывает объекты сам — и сам решает, когда объект пора выселять. Картинку вы знаете с главы 2: имя — ярлык на верёвочке, привязанный к объекту; ярлыков у объекта может быть много; объект, на котором не осталось ни одного, недостижим, и Python освобождает его память. А в главе 14 микроскоп нашёл в заголовке объекта само число ярлыков. Это счётчик ссылок. Каждая новая ссылка — имя, элемент списка, атрибут другого объекта — прибавляет к нему единицу, каждая исчезнувшая отнимает, и объект со счётчиком ноль освобождается сразу, без задержки. Подсмотреть счётчик можно функцией sys.getrefcount.

Двойка вместо ожидаемой единицы — не ошибка: пока работает getrefcount, на список смотрит и её собственный аргумент. Второе имя прибавило единицу, del её отнял: он снимает ярлык, а не уничтожает объект. А у None и у числа 7 счётчик — 4 294 967 295 (так в Python 3.13 песочницы; в других версиях число бывает другим, но тоже огромным), и он не меняется. С Python 3.12 такие вездесущие объекты бессмертны: их счётчик нарочно не трогают, чтобы тысячи ссылок на None не писали лишний раз в его страницу — вспомните копирование при записи.

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

Для петель в CPython есть второй механизм — сборщик мусора, модуль gc; он появился в Python 2.0 в 2000 году. Сборщик смотрит только на контейнеры — списки, словари, объекты классов, — ведь петлю могут образовать лишь объекты, которые на что-то ссылаются. Для каждого он вычитает из счётчика ссылки, идущие от других контейнеров. Кто после этого остался с положительным числом, того держит кто-то снаружи: имя, стек, модуль. От этих объектов сборщик идёт по ссылкам и помечает всё достижимое живым. Остальное — мусор. Проверим в ячейке, выключив на время автоматическую сборку.

Номер A без петли выселен в ту же секунду, как исчезло его имя. Номера X и Y пережили свои имена и ждали, пока gc.collect() их не нашёл. Обычно сборку зовут не руками: Python запускает её сам, когда созданных и ещё живых контейнеров стало на 2000 больше, чем при прошлой сборке, — это первое число порогов. Объекты при этом делятся на поколения: молодые проверяют часто, переживших несколько сборок — реже, потому что большинство объектов умирает молодыми, а старожилы, скорее всего, проживут и дальше.

Утечки

Python убирает за программой сам, и всё же память в нём течёт, только обычно не так, как в C. В C утечка — это забытый вызов free. В языке со сборкой мусора утечка — забытая ссылка: объект больше не нужен, но до него ещё можно дотянуться, и сборщик с полным правом считает его живым. Список, куда «на всякий случай» складывают все запросы; кэш без предела, как @cache из главы 34 на долгоживущем сервере; обработчик, которого подписали на событие и забыли отписать. Найти такую ссылку помогает модуль tracemalloc: он записывает, какая строка программы сколько памяти выделила, и умеет сравнивать два снимка.

Сравнение снимков сразу показывает виновника: строка 7, двадцать тысяч объектов, двадцать с лишним мебибайт. На сервере делают так же: снимок сейчас, снимок через час, разница — список подозреваемых строк. Если память растёт, а tracemalloc молчит, течёт, скорее всего, не Python, а библиотека на C, и тогда смотрят на RSS процесса из раздела о ленивости.

Задачи

Три задачи за стойкой портье: посчитать переселения, построить аномалию Белади для любого числа комнат и перевести адрес по книге в два тома, как это делал процессор Intel 80386.

Куда дальше

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

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

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