memory.tex

\documentclass[main]{subfiles}

\begin{document}
\chapter{Виртуальная память}
\begin{itemize}
\item Необходимость одновременной работы нескольких программ, а потому --- их
защита друг от друга
\item Не вся память программы нужна программе во все моменты времени --- например,
может быть редко используемая большая функция, и её можно просто не загружать в память
\item Защита от ошибок в самой программе --- например, если копируется испорченная
строка без нуль-терминатора, она может перезаписать критичные данные
\end{itemize}

Что в ней есть? Основными являются три механизма:
\section{Механизм защиты (кольца защиты)}
множество инструкций,
которые может изменять процессор, и в нём выделяются некоторые подмножества (0, 1, 2, 3 уровни),
где 0-й уровень позволяет всё, а 3-й уровень сильно ограничен (именно в 3-ем уровне
обычно работает ПО)
Вот что обычно защищают:
\begin{itemize}
\item Обращение к служебным регистрам (ss, ds, es, idtr, \dots)
\item Выходить за границы сегментов и обращаться к несуществующим сегментам
\item Изменять readonly память
\item Работа с внешними устройствами
\end{itemize}

Уровень 3 --- user mode, в котором выполняется прикладное ПО. 0 --- system mode,
в котором работает ядро ОС. Одно из основных применений других колец (кроме "на
всякий случай") --- виртуализация. На нулевом кольце может быть запущен гипервизор,
который будет делить между запущенными ОС на первом уровне имеющиеся ресурсы
(диапазоны памяти, процессоры). Стоит заметить, что такая виртуализация поддерживается
не везде.

Кроме того, существует паравиртуализация, при которой тоже существует некоторый
гипервизор (уже гораздо более "толстый"), а ядро ОС модифицировано так, чтобы
некоторые операции проходили через обращение к гипервизору (например, выделение
памяти, обращение к шине). Примеры --- xen, vmware, jail.

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

Как же всё это обеспечивается?
Во-первых --- сегменты. Их достаточно много, есть понятие как тип сегмента.
Тип сегмента накладывает ограничение на множество команд, которые можно
с ним исполнять. Бывают сегменты инструкций, данных, системный сегмент
(информация о подключённых устройствах, обыкновенно не меняется, таблица
отображений), стек (вроде бы, часть данных, но стоит выделить).
Также выделяют права: можно ли писать в сегмент, или он доступен только
для чтения. Также, с сегментом связан уровень привилегий (ограничение доступа).
У сегмента также есть база --- тот адрес в \emph{виртуальной} памяти, с
которого начинается сегмент, множитель длины и размер, и бит
присутствия --- используется ли сегмент (и ещё некоторые данные, зависящие от
архитектуры). Все эти данные хранятся в таблице сегмента.
Есть LDT --- сегменты, которые программа может создавать для своих целей
и GDT --- системные.

Для чего нужны сегменты? Для управления доступом к памяти, очевидно же.

\section{Страницы}
Вся память поделена на сегменты, которые могут быть отображены
на реальные адреса (возможно, совпадающие). Тут есть небольшая неприятность:
какой размер страницы нужно выбрать? С одной стороны, меньший размер страницы
даёт больший контроль, с другой стороны --- это даёт дополнительные расходы
(кэш, больше расходы на хранение информации). Распространённые размеры ---
2 МиБ, 10 КиБ.

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

В таблице страниц хранятся следующие данные:
\begin{enumerate}
\item Бит присутствия --- используется ли страница (по нему ведётся поиск,
обращение к неиспользуемому вызывает прерывание page fault)
\item Права доступа (r, r/w)
\item Бит грязности --- по этому виртуальному адресу изменяли память
(используется для свопа, сбрасывается после сохранения)
\item Бит доступа --- к этой странице обращались (на запись / чтение)
(сбрасывается через некоторое время)
\item Бит сбрасываемости --- можно ли сбрасывать страницы в своп
\item Физический адрес
\end{enumerate}

Разграничение программ достигается именно механизмом страниц.

Размер виртуальной памяти определяется размером сегментов, которые в ней есть.
Сегменты могут накладываться друг на друга (часто встречается в ОС). Сегмент
данных занимает всю память, сегмент кода ОС начинается позже, ещё дальше ---
пользовательский сегмент, в котором находятся программы.
Вначале обычно идёт код, далее данные, потом --- куча и стек (стек
растёт в сторону младших адресов). Куча --- это та память, которая выделяется
с помощью malloc'а.

\section{Работа с виртуальной памятью}
Кроме стандартной таблицы страниц, есть также некая таблица страниц, которая
исходит из адресов физической памяти. В ней хранится информация о том,
что это такое, кому оно нужно, некоторые дополнительные данные.
В ОС (по крайней мере, в Linux) выделяется три множества страниц:
\begin{enumerate}
\item Совсем активные страницы --- к ним происходят постоянные обращения
и они должны храниться в TLB-кэше. Их сбрасывание замедлит ОС в сотни раз, и
их очень мало.
\item Невыгружаемые страницы --- страницы, которые всегда должны быть в памяти,
там содержатся важные данные ядра, но они используются не так часто.
\item Все прочие страницы
\end{enumerate}
Различные части ОС могут запросить себе страницу, в зависимости от требуемого
типа, используются различные механизмы и алгоритмы их выделения. В ядре
Linux есть вызов kmalloc, который позволяет запросить невыгружаемые страницы
(используется, например, если вы пишете свой драйвер).

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

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

\section{Переполнение буфера}
Одна из распространённых уязвимостей --- переполнение буфера.
Если происходит считывание пользовательских данных в буфер без проверки
длины, злоумышленник может перезаписать адрес возврата на стеке и
выполнить свой код.

Что может сделать линковщик, чтобы препятствовать этому?

\begin{itemize}
\item "<Канарейка"> --- перед адресом возврата выделяется участок памяти
с некоторым значением, которое будет проверено на корректность перед
возвратом из функции. Если адрес возврата будет перезаписан, то
изменится и это значение, что позволит определить факт вмешательства.
Название методу "<дали"> шахтёры, которые брали канареек в шахты;
если начинал выделяться газ, канарейки умирали, и прекращение их
пения было сигналом опасности (у лектора --- вставка
неиспользуемого пространства случайного размера).

\item Рандомизация размещения функций и переменных --- опять же затрудняет
поиск адреса (защита от вызова функций ПО и кода злоумышленника).
\end{itemize}

\section{Позиционно-зависимый и независимый код}
Позиционно-зависимый код: код, которому известно, по каким адресам
находятся объекты, с которыми он работает (переменные, функции).
Когда нужен позиционно-независимый код? Например, если мы хотим
подключать библиотеки во время исполнения, например --- подключение плагинов.
Кроме того, это позволит уменьшить размер исполняемого кода:
если программа невелика (мало кода, данных), то мы можем использовать
адресацию меньшего размера.

Позиционно-зависимый же код, нужен, во-первых, в операционной системе для
обращения к различным аппаратно-зависимым таблицам, например, к таблице
обработчиков прерываний; для загрузчиков ОС.

Для компиляции позиционно-независимого кода (.so, .dll) используется ключ
-fPIC. Потенциально, позиционно-независимый код может быть более "<дорогим">.

\section{TLB-кэш}
Существует TLB --- некоторый кэш процессора, который ставит в соответствие
виртуальным адресам физические адреса (и индекс старения).
Эта таблица позволяет избежать
обращений к таблице страниц (которая находится в оперативной памяти), тем
самым сэкономив значительное время, ведь работа с RAM гораздо дольше.
Для страниц можно запретить сбрасывать TLB-кэш, тогда мы будем работать с
адресами в этих страницах быстрее.

Стоит заметить, что из-за этого стоит избегать случайного доступа к разным
страницам памяти, т. к. это будет лишать программу преимуществ TLB-кэша.
Существует транзакционная память, которая позволяет записать шаблоны обращений
и сохранить их в TLB-кэше, что позволит избежать проблемы случайного доступа.
\end{document}