Для начала рассмотрите картинку ниже:

Как могли увидеть в диалогах выше виртуальная память решает куча проблем: программист не должен заботиться куда выделять память, ведь как в четвёртом сообщении программист ошибся всего‑лишь на один символ и написал в конце 08, а не 80, как сказала ОС. И заметим, что ОС ничего не сделала! Не предупредила, не убила программу. Следующая проблема — памятью пользуется не только наша программа, но и другие.

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

Дисклеймер

Далее в статье все числа будут оговариваться для 64 битных процессоров. Сразу же сделаем вывод: в системе используются 64 битные указатели, также виртуальной памяти выделено байтов на одну программу.
P.s. Размер виртуальной памяти не совсем соответствует байтам, однако данный момент подробнее рассмотрим далее в статье.

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

Связь виртуальной памяти и физической

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

Теперь возникает вопрос: как связать физическую и виртуальную память между собой? Будем разбивать виртуальную и физическую память на страницы (это термин, на английском Page). Раз придумали абстракцию, то значит нужно как-то задать функцию, соглашение, как из виртуальной памяти попадать в физическую. Для этого разбиваем обе памяти на страницы. Эмпирическим путём выяснили, что удобнее всего разбивать страницы размерами по 4 килобайта (4096 байт). В первом приближении можете данную цифру запомнить.

И как сказали бы математики, в данном отображении отсутствует непрерывность, то есть подряд идущие блоки в виртуальной памяти не обязательно отображаются в такой же последовательности в физическую. 

А также, с точки зрении теории множеств отображения не является ни сюръективным, ни инъективным. Не сюръективна означает, что не каждая страница виртуальной памяти будет вообще соответствовать физической странице. А не инъективно означает, что разные куски виртуальной памяти могут указывать на одну реальную физическую, например, на библиотеку.

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

Напоминание: процессор у нас 64 битный, значит виртуальный адрес занимает 64 бита*.

* Размер виртуального адреса в 64 бита верно для архитектуры AMD64. А уже в Armv8 и RISC-V 64 размер адреса другой.

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

Анатомия виртуального адреса

Адрес же виртуальной памяти представляет собой 64 бита (справа-налево): младшие 12 бит кодируют сдвиг адреса внутри страницы; далее 4 раза по 9 бит хранят адреса страниц, оставшиеся 16 старших бит обычно не используются, и зарезервированы для дальнейшей адресации.

Теперь разберём подробнее, что кодируют биты в виртуальной ссылке. Младшие 12 бит хранят сдвиг адреса внутри страницы. Сдвиг адреса это его номер внутри странице. Возникнет вопрос, почему 12 бит? Потому что размер страницы составляет 4096 байт или байт, поэтому для того, чтобы закодировать номер адреса внутри страницы понадобится 12 бит.

Однако перед объяснением, отмечу то, что старшие 16 бит остаются зарезервированными и обычно не используются (одно из применений рассмотрим позже). 

Посередине идут 36 бит, то есть 4 раза по 9 бит, здесь уже интереснее момент. Сначала ответим на вопрос, почему 9 бит? Потому что страница весит 4096 байт, или байт, а один адрес кодируется 8 илибайт.

Теперь можем узнаем сколько вообще адресов поместится в одну страницу: адресов. Получили ответ откуда взялась цифра в 9 бит. 

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

И следующая идея, которая могла возникнуть - сделать таблицу размерами и вроде всё, у нас есть такая таблица, которая хранит отображение между виртуальной и физической памятью. Однако для хранение такой таблицы понадобится байт петабайта, а это невообразимое количество. И поэтому воспользуемся комбинаторикой, как же покрыть хотя бы адресов не используя двух петабайт памяти? Нужно воспользоваться обычным правилом перемножения, и алгоритмом BOR. 

Вспоминая BOR

Алгоритм принимает строки, последовательности и выдаёт деревья. Подадим следующие строчки: "abc", "abd", "ad". Получим дерево:

Дерево на картинке выше кодирует 3 строки. И в данном случае мощность алфавита у дерева составляет 26 символов (количество букв в английском алфавите). В нашем же случае мощность алфавита будет .

Механизм страниц

Вот, теперь у нас в инструментах есть: алгоритм BOR и комбинаторика. Вот у нас есть адреса, представим, что хотим добавить количество адресов к (выше число выводилось), для этого добавим ещё один адрес страницы, получиться уже адресов. Всё равно не хватает, и теперь давайте сделаем ещё два раза: адресов. Однако пока остановимся: обычно такого объёма хватает, и как поймём дальше, что при увеличении адресов у нас будет дольше работать. Теперь, причём тут BOR ? Притом, что из адресов по 9 бит будет строиться дерево. Но процессору также требуется знать где вершина этого BOR-а, поэтому он хранит ссылку на него в регистре CR3.

Теперь разберём какие данные хранятся в виртуальной памяти ещё:

Текст программы

Текст программы загружается в виртуальную память. И процессор для исполнения данной ему программы поддерживает регистр (RIP) "instruction pointer", который указывает на следующую исполняемую инструкцию.

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

• Использовали goto (много где по код стайлам не рекомендовано);

• Также в if else расставляются метки: если условие верно, то прыгнуть в него, если не верно, то в другое.

• Вызов функции, устроен интереснее, разберём подробно:

На месте функции компилятор напишет call <address>. Пример кода на C++ ниже:

// main.cpp
#include "foo.h"
int main() {
  Foo(); // Компилятор напишет call <address>
  return 0;
}

// foo.cpp
void Foo() {
  std::cout << "Call Foo";
}

Однако данный вызов менее очевиден, чем прыжок, потому что вызов функции и её реализация могут быть в разных .cpp файлах. И на стадии построения объектных файлов непонятно где находиться реализация. Однако на данной стадии всё не заканчивается, ведь следует этап линковки (связывания).

Вот так условно выглядит текст программы, в ней можно выделить:

Инструкция прыгнула на Foo, но непонятно куда дальше прыгать. Неясно куда возвращаться: функция вообще может быть библиотечной, поэтому статически адрес возврата не известен. И чтобы процессор мог вызывать функции и возвращаться из них нужно в run-time поддерживать ещё одну структуру: Call-Stack.

Call-Stack

Сам Call-Stack живёт также в виртуальной памяти. У процессора имеется регистр RSP, так называемый stack pointer, который указывает на вершину стека. rip - адрес возврата функции. Конечно в Call Stack-е не только rip адреса живут.

Инструкция call совершает два действия:

• Прыжок в начало функции;

• Вершину стека смещает вниз по адресам и кладёт адрес возврата.

Также нам, как разработчикам, часто требуется передавать аргументы в функции. Код ниже на C++:

void Foo() {
  Bar(1,2);
}

void Bar(int, int) {
  std::cout << "Call Bar";
}

Аргументы передаются с помощью регистров процессора, и это подводит к следующей мысли: в процессоре требуется зафиксировать общений функций друг с другом, это называется Calling conventions «соглашение о вызовах». Данное соглашение фиксирует: как передавать аргументы, фиксировать результаты, а, с другой стороны, эти соглашения делят регистры на callee-saved и caller-saved.

И продолжая пример в коде выше, функция Bar может перезаписать некоторый набор регистров, но перед возвратом в функцию Foo, Bar должна их частично восстановить, то есть часть регистров после вызова функции Bar останутся в том же виде, что и были перед вызовом Bar. И когда компилятор компилирует функцию Foo таким образом, чтобы код функции Foo не зависел от того, что будет в других регистрах, кроме callee-saved.

Регистры callee-saved у Linux для x86-64 носят названия: r12-r15

Куча (heap)

Куча (heap) является тоже страницей. И на самом деле, стек не сильно отличается от кучи, это не какая-то особенная память.

Теперь ответим на вопрос: Как аллоцировать новую страницу памяти? На языке высокого уровня, по типу, C++, программист не может напрямую попросить это сделать, однако можем сделать запрос ОС. Для этого есть вызов mmap. И давайте рассмотрим Си-шную функцию malloc, что она под капотом делает?  Аллокатор сам по себе память постоянно не аллоцирует, точнее аллоцирует её большими аренами. Современные аллокаторы обычно делят память на локации. malloc не выделяет память сразу с помощью mmap каждый раз, а запрашивает у ОС большие области, разбивает их на мелкие блоки и ведёт учёт, где что хранится.

Заключение

В нашем арсенале теперь: регистры RSP, RIP, CR3. Узнали, что такое виртуальная память, мотивация её, как работает отображение между виртуальной и физической.

Мы приблизились немного к тому, чтобы создавать свои корутины, однако в основном данная статья будет полезна студентам для сдачи ОС-ей, для общего развития, и для собеседований (да-да, на собеседовании на позицию middle C++ developer-а у меня спросили как устроено отображение из виртуальной памяти в физическую).