Устройство виртуальной памяти процесса

Без понимания принципов устройства виртуальной памяти процесса вполне можно разрабатывать прикладное ПО. Однако, понимание этих принципов будет полезно любому software инженеру. А в случаях низкоуровневой работы с памятью такие знания становятся необходимостью. В данном посте я поверхностно раскрою данную тему, а в последующих сделаю углубление в отдельные темы о том, как работает память внутри программного обеспечения.

Для начала давайте разберемся, что такое виртуальная память, зачем она нужна и почему мы не можем обращаться к реальной памяти напрямую.
На заре развития компьютеры исполняли лишь одну программу за раз. И даже первые операционные системы были однозадачными. Запущенная программа спокойно могла распоряжаться всеми доступными ресурсами, в том числе и оперативной памятью.
Предоставить такой программе доступ к реальной памяти не вызывало особых проблем.
Сегодня же подобными привилегиями могут похвастаться лишь программы исполняемые на голом железе, такие как ядра операционных систем и прошивки микроконтроллеров.

Если же мы имеем дело с программой исполняющейся под одной из современных операционных систем, таких как Linux, Windows, MacOS, FreeBSD и некоторых других, то мы оказываемся в многозадачной среде, в которой исполняются несколько программ параллельно.
В таких условиях при использовании реальной памяти появляется ряд проблем. Одна из них - это эффективное ограничение доступа к областям памяти принадлежащих другим процессам. Менее очевидная для разработчиков работавших только с высокоуровневыми языками проблема - мы не можем гарантировать, что исполняемый код нашей программы будет всегда загружен в оперативную память по одним и тем же адресам, что сильно затрудняет вызовы функций/методов нашей программы.
Наличие же виртуальной памяти, помимо решения вышеуказанных проблем позволяет делать еще несколько полезных трюков, вроде сброса неиспользуемой в данный момент памяти в файл/раздел подкачки или архивирование ее в ZRAM, а так же отображение виртуальной памяти в устройства отличные от оперативный памяти.

Как же это работает?
Каждому процессу в системе предоставляется виртуальное адресное пространство, как будто он обладает максимально возможной памятью для данной аппаратной архитектуры. О том, какие максимумы для памяти доступны на различных архитектурах я расскажу в одном из следующих постов. А вот с виртуальными адресами разберемся прямо сейчас.
Когда процесс обращается к памяти по своему виртуальному адресу, контроллер памяти сопоставляет ему реальный адрес по специальным таблицам, составленным операционной системой.
Если такое сопоставление успешно, то программа получает в свое распоряжение конкретный блок реальной памяти.
Если же виртуальный адрес не сопоставлен реальному, то программа падает с segmentation fault.
Еще один возможный сценарий, когда виртуальный адрес сопоставлен с чем либо за пределами оперативной памяти, например с файлом подкачки, в этом случае управление передается операционной системе, которая загружает нужные данные в оперативную память и обновляет таблицу виртуальных адресов, после чего операция повторяется и программа получает доступ к требуемой памяти.

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

Страничная организация памяти

В предыдущем посте мы рассмотрели что такое виртуальная память, а так же узнали о том, что процессы оперируют виртуальными адресами, которые преобразуются в реальные адреса по специальным таблицам.
Нетрудно догадаться, что для хранения таких таблиц так же требуется оперативная память, а отображение каждого виртуального адреса в реальный является неэффективным.
Кроме того, если учесть возможность арифметики указателей (которая встречается гораздо чаще, чем вы думаете), то такое отображение и вовсе перестанет работать.
Самым эффективным способом организации памяти на сегодня является представление памяти в виде страниц фиксированного размера.

Для начала посмотрим, как это работает.
Для каждого процесса ОС заводит несколько таблиц для хранения информации о страницах памяти. В одной таблице могут хранится только таблицы одинакового размера, а количество записей ограничено. Помимо реального адреса начала страницы, в каждой записи таблицы хранятся права доступа к данной странице, похожие на права файлов в unix - чтение, запись, выполнение, с той разницей, что ограничение на чтение обычно не имеет смысла и вместо него используется ограничение на доступ только из ядра ОС.
Несколько таблиц объединяются в каталоги, а каталоги могут объединяться в каталоги более высокого уровня. В современных 64-битных архитектурах может использоваться до 4 уровней вложенности.
Виртуальный адрес в такой модели состоит из двух частей: старшие биты указывают на индекс каталога/таблицы, а младшие - смещение в странице.

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

Области виртуальной памяти

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

Что это за области?
Я предполагаю, что большинство моих читателей хотя бы что-то слышали о таких понятиях как стек и куча. Это как раз 2 примера таких областей, однако ими дело не ограничивается.
Прежде чем мы разберемся, какие области бывают и для чего они предназначены, стоит прояснить несколько важных моментов:
Во-первых, все эти области являются всего лишь абстракциями. Это значит, что большинство из этих областей по сути не являются обязательными, но ими оперируют большинство языков программирования на уровне компиляторов и стандартных библиотек. Однако никто не мешает нам на самом низком уровне распоряжаться памятью так, как мы сочтем нужным. Хотя и здесь есть нюансы, например ОС может навязывать нам свои правила.
Во-вторых, не лишним будет знать, что виртуальная память обычно разделена на 2 пространства - пользовательское и пространство ядра. Пространство ядра как правило располагается в верхней половине адресов и недоступно из режима пользователя, в котором выполняются наши программы. Такое разделение очень важно для выполнения системных вызовов, о которых мы поговорим в будущих постах.
В третьих, некоторые области могут быть на деле разбросаны по адресному пространству, а так же присутствовать в нескольких экземплярах. То, что стек обычно рисуют сверху - не более чем грубое упрощение, таким упрощениям я посвящу следующий пост.

Перечислим часто встречающиеся области с описанием для чего они нужны:

stack - используется для локальных переменных функций, а так же для мета информации о вызовах, такой как адрес возврата. Каждый поток имеет свой собственный стек. Размер стека не изменяется в процессе выполнения и определяется ОС для главного потока и разработчиком для дочерних. Получил свое название в честь одноименной структуры данных, так как по сути представлен стеком кадров (stack frames), каждый из которых содержит информацию запущенной в текущей момент функции.

heap (куча) - используется для динамической памяти, которая выделяется и освобождается в runtime по мере надобности. Опять же, куча названа так по имени структуры данных, которая использовалась в первых аллокаторах (алгоритмах выделяющих и освобождающих память, а так же нарезающих страницы на куски).

text - здесь расположен машинный код программы. Указатели на функции ведут в эту область памяти. Сюда запрещена запись, но разрешено выполнение.

data - область для static и глобальных переменных инициализированных на старте программы. Начальное состояние загружается из файла с программой (elf/exe/mach o).

rodata - область для констант, похожа на предыдущую с той разницей, что сюда запрещена запись.

bss - область для неинициализированных static и глобальных переменных. От data отличается тем, что в файле с программой описывается лишь размер данных. В зависимости от ОС на старте программы может быть заполнена нулями или мусором.

env - область в которую ОС записывает переменные окружения и аргументы командной строки.

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

Вот несколько таких нюансов:
- В Windows область text расположена по более старшим адресам, чем stack.
- Stack не растет вниз, размер стека не меняется.
- В программе может быть больше одного стека.
- Heap (куча) не растет вверх.
- В таких языках как JavaScript или Python разработчику доступна только куча.
- Есть языки с JIT компиляцией, у которых под капотом используются области с одновременно разрешенными записью и исполнением.

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

Как работает stack?

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

В основе работы стека лежит регистр специального назначения называемый stack pointer (sp), который хранит в себе адрес указывающий на вершину стека. Так же в большинстве ассемблеров можно встретить такие операции как push и pop. Если упрощать, то можно сказать, что push кладет свой аргумент на вершину стека, а pop извлекает вершину стека в свой аргумент.

Но что эти операции делают на самом деле?
Операция push на самом деле выполняет 2 действия. Сначала она уменьшает значение в регистре sp на размер машинного слова (8 байт на 64 битных архитектурах). Затем она перемещает данные из регистра указанного в ее аргументе по адресу полученному в результате предыдущей операции.
Операция pop делает все наоборот. Помещает данные из памяти по адресу хранящемуся в sp в регистр указанный в ее аргументе, а затем увеличивает значение sp на размер машинного слова.

Из-за того, что адрес в sp уменьшается при push и увеличивается при pop, создается впечатление, что стек растет вниз. На самом деле стек никуда не растет, выделенная под него память имеет фиксированный размер, меняется лишь адрес в sp, который указывает на память внутри данной области. Именно это делает стек таким быстрым, операции со стеком сводятся к сложению/вычитанию адресов, а данные на стеке расположены близко друг к другу, что благоприятно для процессорного кэша.

На самом деле никто не запрещает нам записать в sp любой адрес. И это даже будет работать при условии, что данный виртуальный адрес можно отобразить в реальный через таблицы страниц и нам разрешена запись в данную память. Этим активно пользуются некоторые языки и фреймворки, а так же сама ОС для организации кооперативной многозадачности.

Ну и раз уж заговорили о многозадачности. Операции со стеком не задумывались для работы в многопоточной среде, поэтому для каждого потока в программе создается свой собственный стек. Память под стек выделяется в момент создания потока, а освобождается когда поток завершает свою работу.
Сколько выделить памяти решает тот, кто запускает поток, для главного потока - ОС, для дочерних - программа. Единственное ограничение тут - стек должен занимать целое число страниц.
Ниже этой памяти ОС размечает 1 дополнительную страницу, которая не отображается на реальную память, а служит защитником стека (stack guard), при попытке записи в данную страницу вместо ошибки segmentation fault происходит более понятная ошибка stack overflow.

Немного холиварной лирики в ленту касательно языков.

Я вижу как много указали Java в комментах под опросом выше. Упоминали и другие языки, но именно Java оказалось очень много, что не мудрено. Если думать с позиции заколачивания кэша, то Python, JavaScript (или скорее TypeScript) и Java - беспроигрышный выбор, с которым всегда найдешь работу.

Почему основной список языков в опросе именно такой? Это те языки, которыми я владею уверенно, как минимум на достаточном уровне чтоб написать на них что-то осмысленное.

Конечно у каждого наверняка есть свой язык любимчик. Для меня Rust - one love 🫀+🧠. Но я хочу взглянуть на языки немного с другой стороны. С позиции парадокса Блаба. Исходя из того, как они развивают программистский кругозор и прокачивают мозг.
С одной стороны можно просто изучить как можно больше языков, но без использования знания выветриваются. Я уже не думаю на php или Go, хотя когда-то зарабатывал на них деньги. Я вообще не помню QBasic и Pascal, хотя начинал с них. Я по фану въехал в Brainfuck, но дальше фана он не применим. Мне интересны семейства Prolog и APL, вот только кому они нужны на практике.
И если вы спросите меня про 3 языка, которые проапгрейдили мое мышление, то я отвечу - C, Haskell, Rust.

C - до предела простой. В нем минимум абстракций, нужна абстракция - напиши ее сам. Он заставляет думать о том, как все работает под капотом, не погружаясь при этом в дебри ассемблера.

Haskell - заставляет мыслить совершенно по другому. Мыслить в категории потока данных проходящих через последовательность вычислений (что по сути и делает любая программа). Он взрывает мозг, когда ты втыкаешь отладку через unsafePerformIO $ print и получаешь не то что ожидал. Но потом ты в это въезжаешь и ты уже никогда не будешь мыслить как прежде. Правда мне теперь всегда не хватает HKT в других языках, каждый раз, как я ухожу в метапрограммирование на типах.

Rust - еще один переворот сознания. Хоть и многословное, но красивое сочетание zero-cost абстракций из мира плюсов с изяществом ML языков. Первый месяц ты борешься с компилятором с мыслями "какого черта оно не компилируется?" А потом приходит понимание, которое навсегда меняет твой подход к написанию кода на любом языке. Да и читаешь ты код уже по другому. Начинаешь видеть проблемы там где они есть, но раньше ты их не видел. И сетуешь, почему нельзя было кинуть хотя бы warning на ту дичь, что написал коллега джун.
Плюсовики, вы видите тут UB?
void foo(const int &x, int &y) {
bar(x, ++y);
}
А так: foo(a, a)? А Rust не даст такое скомпилировать, в этом и прелесть.

Stack Frames или сказ о вызовах функций используя стек

Есть много способов, как организовать вызовы функций, да так, чтоб мы могли передавать в функцию аргументы, изолировать в ней локальные переменные, а так же уметь возвращаться назад, желательно с результатом.
Некоторые динамические языки, вроде JavaScript, php или Python, могут даже позволить себе роскошь хранить локальные переменные на куче (в случае исполнения интерпретатором такая роскошь вынужденная).
Но чаще всего компиляторы организуют вызовы и хранение локальных переменных используя кадры стека (stack frames).

Stack frame - это такая абстракция компилятора, которая позволяет разделить части стека принадлежащие разным функциям.
В ее основе лежит еще один регистр специального назначения называемый base pointer (bp). У него 2 назначения: во-первых быть базовым адресом, относительно которого можно обращаться к локальным переменным, во-вторых хранить в себе состояние stack pointer (sp), которое было до вызова и восстанавливать его при возврате из функции.

Есть и операции в ассемблере для манипуляции с кадрами стека - call и ret.
Операция call сохраняет свой адрес инструкции на стеке и делает переход по адресу из своего аргумента. То есть ее можно заменить на последовательность push %ip и jmp arg, где arg - аргумент call, а ip - еще один регистр специального назначения instruction pointer, указывающий на адрес текущей операции.
Операция ret делает все наоборот, переходит по адресу на стеке и восстанавливает регистр ip. То есть ее можно развернуть в последовательность jmp %sp и pop %ip.

Давайте посмотрим на примере такой функции:

int func(int a, int b) {
    int c = a + b;
    return c;
}

Она может быть скомпилирована в следующий ассемблер:
func:
; сохраняем bp на стек
pushq %rbp
; обновляем bp значением sp
movq %rsp, %rbp
; сохраняем аргументы на стек
movl %edi, -4(%rbp)
movl %esi, -8(%rbp)
; складываем
movl -4(%rbp), %eax
addl -8(%rbp), %eax
movl %eax, -12(%rbp)
; возвращаем результат
movl -12(%rbp), %eax
; восстанавливаем bp
popq %rbp
; возвращаемся в место вызова
retq

Теперь ее можно будет вызвать с аргументами 1 и 2 вот так:
movl $1, %edi
movl $2, %esi
callq func

Суффикс l у операции и префикс e у регистра в x86 говорит об операции со значением размером 32 бита, суффикс q и префикс r - 64 бита, а без суффикса и префикса - 16 бит.
Метка func будет заменена на адрес следующей за ней инструкции при линковке.

Использование кадров стека позволяет производить вложенные вызовы, глубина которых ограничена только размером стека. Так же, благодаря кадрам стека мы можем произвольно обращаться к локальным переменным не ограничиваясь лишь тем, что лежит на вершине стека.

Но есть в такой модели и ограничение - компилятор должен знать размер stack frame для каждой функции, а значит размер всех ее локальных переменных, включая аргументы.

Встречаются и расширения данной модели, позволяющие обойти это ограничение, но они не так эффективны.