Разработка ядра Linux

Глава 14 Адресное пространство процесса

В главе 11, "Управление памятью", было рассказано о том, как ядро управляет физической памятью. В дополнение к тому, что ядро должно управлять своей памятью, оно также должно, управлять и адресным пространством процессов — тем, как память видится для каждого процесса в системе. Операционная система Linux — это операционная система с виртуальной памятью (virtual memory operating system), т.е. для всех процессов выполняется виртуализация ресурсов памяти. Для каждого процесса создается иллюзия того, что он один использует всю физическую память в системе. Еще более важно, что адресное пространство процессов может быть даже значительно больше объема физической памяти. В этой главе рассказывается о том, как ядро управляет адресным пространством процесса.

Адресное пространство процесса состоит из диапазона адресов, которые выделены процессу, и, что более важно, в этом диапазоне выделяются адреса, которые процесс может так или иначе использовать. Каждому процессу выделяется "плоское" 32- или 64-битовое адресное пространство. Термин "плоское" обозначает, что адресное пространство состоит из одного диапазона адресов (например, 32-разрядное адресное пространство занимает диапазон адресов от 0 до 429496729). Некоторые операционные системы предоставляют сегментированное адресное пространство — адресное пространство состоит больше чем из одного диапазона адресов, т.е. состоит из сегментов. Современные операционные системы обычно предоставляют плоское адресное пространство. Размер адресного пространства зависит от аппаратной платформы. Обычно для каждого процесса существует свое адресное пространство. Адрес памяти в адресном пространстве одного процесса не имеет никакого отношения к такому же адресу памяти в адресном пространстве другого процесса. Тем не менее несколько процессов могут совместно использовать одно общее адресное пространство. Такие процессы называются потоками.

Значение адреса памяти — это заданное значение из диапазона адресов адресного пространства, как, например, 41021f000. Это значение идентифицирует определенный байт в 32-битовом адресном пространстве. Важной частью адресного пространства являются интервалы адресов памяти, к которым процесс имеет право доступа, как, например, 08048000–0804c000. Такие интервалы разрешенных адресов называются областями памяти (memory area). С помощью ядра процесс может динамически добавлять и удалять области памяти своего адресного пространства.

Процесс имеет право доступа только к действительным областям памяти. Более того, на область памяти могут быть установлены права только для чтения или запрет на выполнение. Если процесс обращается к адресу памяти, который не находится в действительной области памяти, или доступ к действительной области выполняется запрещенным образом, то ядро уничтожает процесс с ужасным сообщением "Segmentation Fault" (ошибка сегментации).

Области памяти могут содержать следующую нужную информацию.

• Отображение выполняемого кода из выполняемого файла в область памяти процесса, которая называется сегментом кода (text section).

• Отображение инициализированных переменных из выполняемого файла в область памяти процесса, которая называется сегментом данных (data section).

• Отображение страницы памяти, заполненной нулями, в область памяти процесса, которая содержит неинициализированные глобальные переменные и называется сегментом bss[79] (bss section). Нулевая страница памяти (zero page, страница памяти, заполненная нулями) — это страница памяти, которая полностью заполнена нулевыми значениями и используется, например, для указанной выше цели.

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

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

• Все файлы, содержимое которых отображено в память.

• Все области совместно используемой памяти.

• Все анонимные отображения в память, как, например, связанные с функцией

malloc()

[80].

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

Дескриптор памяти

Ядро представляет адресное пространство процесса в виде структуры данных, которая называется дескриптором памяти. Эта структура содержит всю информацию, которая относится к адресному пространству процесса. Дескриптор памяти представляется с помощью структуры

struct mm_struct

, которая определена в файле

[81].

Рассмотрим эту структуру с комментариями, поясняющими назначение каждого поля.

struct mm_struct {

 struct vm_area_struct *mmap;    /* список областей памяти */

 struct rb_root     mm_rb;    /* красно-черное дерево

                     областей памяти */

 struct vm_area_struct *mmap_cache; /* последняя использованная

                    область памяти */

 unsigned long     free_area_cache; /* первый незанятый участок

                       адресного пространства */

 pgd_t         *pgd;     /* глобальный каталог страниц */

 atomic_t       mm_users;   /* счетчик пользователей адресного

                    пространства */

 atomic_t        mm_count;   /* основной счетчик использования */

 int          map_count;  /* количество областей памяти */

 struct rw_semaphore  mmap_sem;   /* семафор для областей памяти */

 spinlock_t       page_table_lock; /* спин-блокировка

                      таблиц страниц */

 struct list_head    mmlist;    /* список всех структур mm_struct */

 unsigned long     start_code;  /* начальный адрес сегмента кода */

 unsigned long     end code;   /* конечный адрес сегмента кода */

 unsigned long     start_data;  /* начальный адрес сегмента данных */

 unsigned long     end_data;   /* конечный адрес сегмента данных */

 unsigned long     start_brk;  /* начальный адрес сегмента "кучи" */

 unsigned long     brk;     /* конечный адрес сегмента "кучи" */

 unsigned long     start_stack; /* начало стека процесса */

 unsigned long     arg_start;  /* начальный адрес

                     области аргументов */

 unsigned long     arg_end;   /* конечный адрес

                     области аргументов */

 unsigned long     env_start;  /* начальный адрес

                     области переменных среды */

 unsigned long     env_end;   /* конечный адрес

                     области переменных среды */

 unsigned long     rss;     /* количество физических страниц памяти */

 unsigned long     total_vm;   /* общее количество страниц памяти */

 unsigned long     locked_vm;  /* количество заблокированных страниц

                     памяти */

 unsigned long     def_flags;  /* флаги доступа, используемые

                     по умолчанию */

 unsigned long     cpu_vm_mask; /* маска отложенного переключения

                     буфера TLB */

 unsigned long     swap_address; /* последний сканированный адрес */

 unsigned        dumpable:1;  /* можно ли создавать файл core? */

 int          used_hugetlb; /* используются ли гигантские

                    страницы памяти (hugetlb)? */

 mm_context_t      context;   /* данные, специфичные для аппаратной

                    платформы */

 int          core_waiters; /* количество потоков, ожидающих на

                     создание файла core */

 struct completion   *core_startup_done; /* условная переменная начала

                         создания файла core */

 struct completion   core_done;  /* условная переменная завершения

                    создания файла core */

 rwlock_t        ioctx_list_lock; /* блокировка списка асинхронного

                      ввода-вывода (AIO) */

 struct kioctx     *ioctx_list; /* список асинхронного ввода-вывода (AIO) */

 struct kioctx     default_kioctx; /* контекст асинхронного ввода-

            вывода, используемый по умолчанию */

};

Поле

mm_users

— это количество процессов, которые используют данное адресное пространство. Например, если одно и то же адресное пространство совместно используется двумя потоками, то значение поля

mm_users

равно двум. Поле

mm_count

— это основной счетчик использования структуры

mm_struct

. Наличие пользователей структуры, которым соответствует поле

mm_users

, приводит к увеличению счетчика

mm_count

на единицу. В предыдущем примере значение поля

mm_count

равно единице. Когда значение поля

mm_users

становится равным нулю (т.е. когда два потока завершатся), только тогда значение поля

mm_count

уменьшается на единицу. Когда значение поля mm_count становится равным нулю, то на соответствующую структуру

mm_struct

больше нет ссылок, и она освобождается, Поддержка двух счетчиков позволяет ядру отличать главный счетчик использования (

mm_count

) от количества процессов, которые используют данную структуру (

mm_users

Поля

mmap

mm_rb

— это два различных контейнера данных, которые содержат одну и ту же информацию: информацию обо всех областях памяти в соответствующем адресном пространстве. В первом контейнере эта информация хранится в виде связанного списка, а во втором — в виде красно-черного бинарного дерева. Поскольку красно-черное дерево — это разновидность бинарного дерева, то, как и для всех типов бинарного дерева, количество операций поиска заданного элемента в нем равно О(log(n)). Более детальное рассмотрение красно-черных деревьев найдете в разделе "Списки и деревья областей памяти".

Хотя обычно в ядре избегают избыточности, связанной с введением нескольких структур для хранения одних и тех же данных, тем не менее в данном случае эта избыточность очень кстати. Контейнер

mmap

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

mm_rb

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

Все структуры

mm_struct

объединены в двухсвязный список с помощью нолей

mmlist

. Первым элементом этого списка является дескриптор памяти

init_mm

, который является дескриптором памяти процесса init. Этот список защищен от конкурентного доступа с помощью блокировки

mmlist_lock

, которая определена в файле

kernel/fork.с

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

mmlist_nr

, которая определена в том же файле.

Выделение дескриптора памяти

Указатель на дескриптор памяти, выделенный для какой-либо задачи, хранится в поле

mm

дескриптора процесса этой задачи. Следовательно, выражение

current->mm

позволяет получить дескриптор памяти текущего процесса. Функция

copy_mm()

используется для копирования дескриптора родительского процесса в дескриптор порожденного процесса во время выполнения вызова

fork()

. Структура

mm_struct

выделяется из слябового кэша

mm_cachep

с помощью макроса

allocate_mm()

. Это реализовано в файле

kernel/fork.c

. Обычно каждый процесс получает уникальный экземпляр структуры

mm_struct

и соответственно уникальное адресное пространство.

Процесс может использовать одно и то же адресное пространство совместно со своими порожденными процессами, путем указания флага

CLONE_VM

при выполнении вызова

clone()

. Такие процессы называются потоками. Вспомните из материала главы 3, "Управление процессами", что в операционной системе Linux в этом и состоит единственное существенное отличие между обычными процессами и потоками. Ядро Linux больше никаким другим образом их не различает. Потоки с точки зрения ядра — это обычные процессы, которые просто совместно используют некоторые общие ресурсы.

В случае, когда указан флаг

CLONE_VM

, макрос

allocate_mm()

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

сору_mm()

if (clone_flags & CLONE_VM) {

/*

 * current — это родительский процесс

 * tsk — это процесс, порожденный в вызове fork()

*/

 atomic_inc(¤t->mm->mm_users);

 tsk->mm = current->mm;

Удаление дескриптора памяти

Когда процесс, связанный с определенным адресным пространством, завершается, то вызывается функция

exit_mm()

. Эта функция выполняет некоторые служебные действия и обновляет некоторую статистическую информацию. Далее вызывается функция

mput()

, которая уменьшает на единицу значение счетчика количества пользователей

mm_users

для дескриптора памяти. Когда значение счетчика количества пользователей становится равным нулю, то вызывается функция

mmdrop()

, которая уменьшает значение основного счетчика использования

mm_count

. Когда и этот счетчик использования наконец достигает нулевого значения, то вызывается функция

free_mm()

, которая возвращает экземпляр структуры

mm_struct

в слябовый кэш

mm_cachep

с помощью вызова функции

kmem_cache_free()

, поскольку дескриптор памяти больше не используется.

Структура

mm_struct

и потоки пространства ядра

Потоки пространства ядра не имеют своего адресного пространства процесса и, следовательно, связанного с ним дескриптора памяти. Значение поля

mm

для потока пространства ядра равно

NULL

. Еще одно определение потока ядра — это процесс, который не имеет пользовательского контекста.

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

Когда процесс запланирован на выполнение, то загружается адресное пространство, на которое указывает поле

mm

этого процесса. Поле

active

_mm дескриптора процесса обновляется таким образом, чтобы указывать на новое адресное пространство. Потоки ядра не имеют своего адресного пространства, поэтому значение поля mm для них равно

NULL

. Поэтому, когда поток ядра планируется на выполнение, ядро определяет, что значение ноля

mm

равно

NULL

, и оставляет загруженным предыдущее адресное пространство. После этого ядро обновляет поле

active_mm

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

Области памяти

Области памяти (memory areas) представляются с помощью объектов областей памяти, которые хранятся в структурах типа

vm_area_struct

. Эта структура определена в файле

. Области памяти часто называются областями виртуальной памяти (virtual memory area, или VMA).

Структура

vm_area_struct

описывает одну непрерывную область памяти в данном адресном пространстве. Ядро рассматривает каждую область памяти, как уникальный объект. Для каждой области памяти определены некоторые общие свойства, такие как права доступа и набор соответствующих операций. Таким образом, одна структура VMA может представлять различные типы областей памяти, например файлы, отображаемые в память, или стек пространства пользователя. Это аналогично объектно-ориентированному подходу, который используется в подсистеме VFS (см. главу 12, "Виртуальная файловая система").

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

struct vm_area_struct {

 struct mm_struct    *vm_mm;    /* соответствующая структура mm_struct */

 unsigned long     vm_start;   /* начало диапазона адресов */

 unsigned long     vm_end;    /* конец диапазона адресов */

 struct vm_area_struct *vm_next;   /* список областей VMA */

 pgprot_t        vm_page_prot; /* права доступа */

 unsigned long     vm_flags;   /* флаги */

 struct rb_node     vm_rb;    /* узел текущей области VMA */

 union { /* связь с address_space->i_mmap, или i_mmap_nonlinear */

  struct {

  struct list_head    list;

  void          *parent;

  struct vm_area_struct *head;

  } vm_set;

  struct prio_tree_node prio_tree_node;

 } shared;

 struct list_head       anon_vma_node;   /* анонимные области */

 struct anon_vma       *anon_vma;     /* объект анонимной VMA */

 struct vm_operations_struct *vm_ops;      /* операции */

 unsigned long        vm_pgoff;     /* смещение в файле */

 struct file         *vm_file;     /* отображенный файл (если есть) */

 void            *vm_private_data; /* приватные данные */

};

Как уже было рассказано, каждый дескриптор памяти связан с уникальным диапазоном (интервалом) адресов в адресном пространстве процесса. Поле vm_

start

— это начальный (минимальный) адрес, а поле

vm_end

— конечный (максимальный) адрес данного интервала. Следовательно, значение (

vm_end - vm_start

) — это размер (длина) интервала адресов в байтах. Интервалы адресов разных областей памяти одного адресного пространства не могут перекрываться.

Поле

vm_mm

указывает на структуру

mm_struct

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

mm_struct

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

vm_area_struct

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

vm_area_struct

в этом адресном пространстве.

Флаги областей VMA

Поле флагов

vm_flags

содержит битовые флаги, которые определены в файле

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

vm_flags

содержит информацию, которая относится к каждой странице в области памяти или, что то же самое, ко всей области памяти в целом. В табл. 14.1 приведен список возможных значений флагов

vm_flags

Таблица 14.1. Флаги областей VMA

Флаг	Влияние на область VMA и на ее страницы памяти
`VM_READ`	Из страниц памяти можно считывать информацию
`VM_WRITE`	В страницы памяти можно записывать информацию
`VM_EXEC`	Можно выполнять код, хранящийся в страницах памяти
`VM_SHARED`	Страницы памяти являются совместно используемыми
`VM_MAYREAD`	Можно устанавливать флаг `VM_READ`
`VM_MAYWRITE`	Можно устанавливать флаг `VM_WRITE`
`VM_MAYEXEC`	Можно устанавливать флаг `VM_EXEC`
`VM_MAYSHARE`	Можно устанавливать флаг `VM_SHARED`
`VM_GROWSDOWN`	Область памяти может расширяться "вниз"
`VM_GROWSUP`	Область памяти может расширяться "вверх"
`VM_SHM`	Область используется для разделяемой (совместно используемой) памяти
`VM_DENYWRITE`	В область отображается файл, в который нельзя выполнять запись
`VM_EXECUTABLE`	В область отображается выполняемый файл
`VM_LOCKED`	Страницы памяти в области являются заблокированными
`VM_IQ`	В область памяти отображается пространство ввода-вывода аппаратного устройства
`VM_SEQ_READ`	К страницам памяти, вероятнее всего, осуществляется последовательный доступ
`VM_RAND_READ`	К страницам памяти, вероятнее всего, осуществляется случайный доступ
`VM_DONTCOPY`	Область памяти не должна копироваться при вызове `fork()`
`VM_DONTEXPAND`	Область памяти не может быть увеличена с помощью вызова `remap()`
`VM_RESERVED`	Область памяти не должна откачиваться на диск
`VM_ACCOUNT`	Область памяти является объектом, по которому выполняется учет ресурсов
`VM_HUGETLB`	В области памяти используются гигантские ( `hugetlb` ) страницы памяти
`VM_NONLINEAR`	Область памяти содержит нелинейное отображение

Рассмотрим подробнее назначение наиболее интересных и важных флагов. Флаги

VM_READ

VM_WRITE

VM_EXEC

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

VM_READ

VM_EXEC

, но никак не с указанием флага

VM_WRITE

. С другой стороны, сегмент данных из выполняемого файла может отображаться с указанием флагов

VM_READ

VM_WRITE

, указывать при этом флаг

VM_EXEC

не имеет смысла. Файл данных, который отображается только для чтения, должен отображаться с указанием только флага

VM_READ

Флаг

VM_SHARED

указывает на то, что область памяти содержит отображение, которое может совместно использоваться несколькими процессами. Если этот флаг установлен, то такое отображение называют совместно используемым (shared mapping), что интуитивно понятно. Если этот флаг не установлен, то такое отображение доступно только одному процессу и оно называется частным отображением, (private mapping).

Флаг

VM_IO

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

mmap()

для отображения в память области ввода-вывода аппаратного устройства. Кроме всего прочего, этот флаг указывает, что область памяти не должна включаться в файл core процесса. Флаг

VM_RESERVED

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

Флаг

VM_SBQ_READ

является подсказкой ядру, что приложение выполняет последовательное (т.е. линейное и непрерывное) чтение из соответствующего отображения. При этом ядро может повысить производительность чтения за счет выполнения упреждающего чтения (read-ahead) из отображаемого файла. Флаг

VM_RAND_READ

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

madvice()

путем указания соответственно флагов

MADV_SEQUENTIAL

MADV_RANDOM

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

Операции с областями VMA

Поле

vm_ops

структуры

vm_area_struct

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

vm_area_struct

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

Таблица операций представлена с помощью структуры

vm_operations_struct

, которая определена в файле

следующим образом.

struct vm_operations_struct {

 void (*open)(struct vm_area_struct*);

 void (*close)(struct vm_area_struct*);

 struct page* (*nopage)(struct vm_area_struct*, unsigned long, int);

 int (*populate)(struct vm_area struct*, unsigned long,

  unsigned long, pgprot_t, unsigned long, int);

};

Рассмотрим каждый метод в отдельности.

•

void open(struct vm_area_struct *area);

Эта функция вызывается, когда соответствующая область памяти добавляется в адресное пространство.

•

void close(struct vm_area_struct *area);

Эта функция вызывается, когда соответствующая область памяти удаляется из адресного пространства.

•

struct page* nopage(struct vm_area_struct *area,

  unsigned long address, int unused);

Эта функция вызывается обработчиком прерывания из-за отсутствия страницы (page fault), когда производится доступ к странице, которая отсутствует в физической памяти.

•

int populate(struct vm_area_struct *area,

  unsigned long address, unsigned long len, pgprot_t prot,

  unsigned long pgoff, int nonblock);

Эта функция вызывается из системного вызова

remap_pages()

для предварительного заполнения таблиц страниц области памяти (prefault) при создании нового отображения.

Списки и деревья областей памяти

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

mmap

mm_rb

. Эти две структуры данных независимо друг от друга указывают на все области памяти, связанные с данным дескриптором памяти. Они содержат указатели на одни и те же структуры

vm_area_struct

, просто эти указатели связаны друг с другом по-разному.

Первый контейнер, поле

mmap

, объединяет все объекты областей памяти в односвязный список. Структуры

vm_area_struct

объединяются в список с помощью своих полей

vm_next

. Области памяти отсортированы в порядке увеличения адресов (от наименьшего и до наибольшего). Первой области памяти соответствует структура

vm_area_struct

, на которую указывает само поле

mmap

. Указатель на самую последнюю структуру равен значению

NULL

Второе поле,

mm_rb

, объединяет все объекты областей памяти в красно-черное (red-black) дерево. На корень дерева указывает поле

mm_rb

, а каждая структура

vm_area_struct

присоединяется к дереву с помощью поля

vm_rb

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

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

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

Рассмотрим пример адресного пространства процесса и области памяти в этом адресном пространстве. Для этой цели можно воспользоваться полезной файловой системой

/proc

и утилитой

pmар(1)

. В качестве примера рассмотрим следующую простую прикладную программу, которая работает в пространстве пользователя. Эта программа не делает абсолютно ничего, кроме того, что служит примером.

int main(int argc, char *argv[]) {

 return 0;

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

libc.so

и для модуля

ld.so

. И наконец, среди областей памяти также есть стек процесса.

Результат вывода списка областей адресного пространства этого процесса из файла

/proc//maps

имеет следующий вид.

rml@phantasy:~$ cat /proc/1426/maps

00e80000-00faf000 r-xp 00000000 03:01 208530 /lib/tls/libc-2.3.2.so

00faf000-00fb2000 rw-p 0012f000 03:01 208530 /lib/tls/libc-2.3.2.so

00fb2000-00fb4000 rw-p 00000000 00:00 0

08048000-08049000 r-xp 00000000 03:03 439029 /home/rml/src/example

08049000-0804a000 rw-p 00000000 03:03 439029 /home/rml/src/example

40000000-40015000 r-xp 00000000 03:01 80276  /lib/ld-2.3.2.so

40015000-40016000 rw-p 00015000 03:01 80276  /lib/ld-2.3.2.so

4001e000-4001f000 rw-p 00000000 00:00 0

bfffe000-c0000000 rwxp fffff000 00:00 0

Информация об областях памяти выдается в следующем формате.

начало-конец права доступа смещение старший:младший номера устройства файловый индекс файл

Утилита

pmap(1)

[82] форматирует эту информацию в следующем, более удобочитаемом виде.

rml@phantasy:~$ pmap 142 6 example[142 6]

00e80000 (1212 KB) r-xp (03:01 208530) /lib/tls/libc-2.3.2.so

00faf000 (12 KB)  rw-p (03:01 208530) /lib/tls/libc-2.3.2.so 00fb2000 (8 KB) rw-p (00:00 0)

08048000 (4 KB)   r-xp (03:03 439029) /home/rml/src/example

08049000 (4 KB)   rw-p (03:03 439029) /home/rml/src/example

40000000 (84 KB)  r-xp (03:01 80276)  /lib/ld-2.3.2.so

40015000 (4 KB)  rw-p (03:01 80276)  /lib/ld-2.3.2.so

4001e000 (4 KB)   rw-p (00:00 0)

bfffe000 (8 KB)   rwxp (00:00 0)

mapped: 1340 KB writable/private: 40 KB shared: 0 KB

Первые три строчки соответствуют сегменту кода, сегменту данных и сегменту bss модуля

libc.so

(библиотека функций языка С). Следующие две строчки описывают соответственно сегмент кода и сегмент данных выполняемого образа. Далее три строчки — описание сегментов кода, данных и bss модуля

ld.so

(динамический компоновщик). Последняя строчка описывает стек процесса.

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

Все адресное пространство составляет порядка 1340 Кбайт, но только 40 Кбайт из них имеют право на запись и соответствуют частному отображению. Если область памяти является совместно используемой и не имеет прав на запись, то ядро хранит в памяти всего одну копию отображаемого файла. Это может показаться обычным для совместно используемых отображений; однако, случай, когда при этом еще и отсутствуют права на запись, проявляется несколько неожиданно. Если учесть факт, что когда на отображение нет прав записи, то соответствующая информация никогда не может быть изменена (из отображения возможно только чтение), становится ясно, что можно совершенно безопасно загрузить выполняемый образ в память всего один раз. Поэтому динамически загружаемая библиотека функций языка С и занимает в памяти всего 1212 Кбайт, а не 1212 Кбайт, умноженное на количество процессов, которые эту библиотеку используют. В связи с этим, процесс, код и данные которого имеют объем порядка 1340 Кбайт, на самом деле занимает всего 40 Кбайт физической памяти. Экономия памяти из-за такого совместного использования получается существенной.

Обратите внимание на области памяти, которые не имеют отображаемого файла, находятся на устройстве с номерами

00:00

и номер файлового индекса для которых равен нулю. Это отображение страницы, заполненной нулями (zero page, пулевая страница). Если отобразить страницу, заполненную нулями, на область памяти, которая имеет права на запись, то побочным эффектом является инициализация всех переменных в нулевые значения. Это важно, поскольку в таком случае получается область памяти, заполненная нулями, которая нужна для сегмента bss.

Каждой области памяти, связанной с процессом, соответствует структура

vm_area_struct

. Так как процесс не является потоком (thread), то для него существует отдельная структура

min_struct

, на которую есть ссылка из структуры

task_struct

Работа с областями памяти

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

mmap()

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

Функция

find_vma()

Функция

find_vma()

определена в файле

mm/mmap.c

Эта функция позволяет найти в заданном адресном пространстве ту первую область памяти, для которой значение поля

vm_end

больше заданного адреса

addr

. Другими словами, эта функция позволяет найти первую область памяти, которая содержит адрес

addr

или начинается с адреса, большего адреса

addr

. Если такой области памяти не существует, то функция возвращает значение

NULL

В противном случае возвращается указатель на соответствующую структуру

vm_area_struct

. Обратите внимание, что найденная область VMA может начинаться с адреса, большего адреса

addr

, и этот адрес не обязательно принадлежит найденной области памяти. Результат выполнения функции

find_vma()

кэшируется в поле

map_cache

дескриптора памяти. Поскольку очень велика вероятность того, что после одной операции с областью памяти последуют еще операции с ней же, то процент попаданий в кэш получается достаточно большим (на практике получаются значения порядка 30-40%). Проверка кэшированных результатов выполняется очень быстро. Если нужный адрес в кэше не найден, то выполняется поиск по всем областям памяти, связанным с заданным дескриптором. Этот поиск выполняется с помощью красно-черного дерева следующим образом.

struct vm_area_struct* find_vma(struct mm_struct *mm,

 unsigned long addr) {

 struct vm_area_struct *vma = NULL;

 if (mm) {

  vma = mm->mmap_cache;

  if (!(vma && vma->vm_end > addr && vma->vm_start <= addr)) {

  struct rb_node* rb_node;

  rb_node = mm->mm_rb.rb_node;

  vma = NULL;

  while (rb_node) {

   struct vm_area_struct* vma_tmp;

   vma_tmp =

   rb_entry(rb_node, struct vm_area_struct, vm_rb);

   if (vma_tmp->vm_end > addr) {

   vma = vma_tmp;

   if (vma_tmp->vm_start <= addr)

    break;

   rb_node = rb_node->rb_left;

   } else

   rb_node = rb_node->rb_right;

  if (vma)

   mm->mmap_cache = vma;

 return vma;

Вначале выполняется проверка поля

vma_cache

на предмет того, содержит ли кэшированная область VMA необходимый адрес. Обратите внимание, что простая проверка того, является ли значение поля

vm_end

большим

addr

, не гарантирует что проверяемая область памяти является первой, в которой есть адреса, большие

addr

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

Если кэш не содержит нужную область VMA, то функция должна выполнять поиск по красно-черному дереву. Это выполняется путем проверки узлов дерева. Если значение поля

vma_end

для области памяти текущего узла больше

addr

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

addr

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

addr

. Если вообще не найдена ни одна область памяти, то возвращается значение

NULL

Функция

find_vma_prev()

Функция

find_vma_prev()

работает аналогично функции

find_vma()

, но дополнительно она еще возвращает последнюю область VMA, которая заканчивается перед адресом

addr

. Эта функция также определена в файле

mma/mmap.c

и объявлена в файле

следующим образом.

struct vm_area_struct* find vma_prev(struct mm_struct *mm,

 unsigned long addr, struct vm_area_struct **pprev);

Параметр

pprev

после возвращения из функции содержит указатель на предыдущую область VMA.

Функция

find_vma_intersection()

Функция

find_vma_intersection()

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

следующим образом. Это функция с подстановкой тела.

static inline struct vm_area_struct* find_vma_intersection(

 struct mm_struct *mm, unsigned long start_addr,

 unsigned long end_addr) {

 struct vm_area_struct *vma;

 vma = find_vma(mm, start_addr);

 if (vma && end_addr <= vma->vm_start)

  vma = NULL;

 return vma;

Первый параметр — адресное пространство, в котором выполняется поиск, параметр

start_addr

— это первый адрес интервала адресов, а параметр

end_addr

— последний адрес интервала.

Очевидно, что если функция

find_vma()

возвращает значение

NULL

, то это же значение будет возвращать и функция

find_vma_intersection()

. Если функция

find_vma()

возвращает существующую область VMA, то функция

find_vma_intersection()

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

find_vma()

, начинается после последнего адреса из указанного диапазона, то функция

find_vma_intersection()

возвращает значение

NULL

Функции

mmap()

do_mmap()

: создание интервала адресов

Функция

do_mmap()

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

do_mmap()

— это функция, которая добавляет интервал адресов к адресному пространству процесса, независимо от того, создается ли при этом новая область VMA или расширяется существующая.

Функция

do_mmap()

объявлена в файле

следующим образом.

unsigned long do_mmap(struct file *file,

 unsigned long addr, unsigned long len,

 unsigned long prot,

unsigned long flag,

 unsigned long offset);

Эта функция выполняет отображение на память содержимого файла

file

начиная с позиции в файле

offset

; размер отображаемого участка равен

len

байт. Значения параметров

file

offset

могут быть нулевыми, в этом случае отображение не будет резервироваться (сохраняться) в файле. Такое отображение называется анонимным (anonymous mapping). Если указан файл и смещение, то отображение называется отображением файла в память (file-backed mapping).

Параметр

addr

указывает (точнее, всего лишь подсказывает), откуда начинать поиск свободного интервала адресов.

Параметр

prot

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

. Хотя на практике для всех аппаратных платформ определены флаги, приведенные в табл. 14.2.

Таблица 14.2. Флаги защиты страниц памяти

Флаг	Влияние на страницы памяти в созданном интервале адресов
`PROT_READ`	Соответствует флагу `VM_READ`
`PROT_WRITE`	Соответствует флагу `VM_WRITE`
`PROT_EXEC`	Соответствует флагу `VM_EXEC`
`PROT_NONE`	К страницам памяти нет доступа

Параметр

flags

позволяет указать все остальные флаги области VMA Эти флаги также определены в

и приведены в табл. 14.3.

Таблица 14.3. Флаги защиты страниц памяти

Флаг	Влияние на созданный интервал адресов
`MAP_SHARED`	Отображение может быть совместно используемым
`MAP_PRIVATE`	Отображение не может быть совместно используемым
`MAP_FIXED`	Создаваемый интервал адресов должен начинаться с указанного адреса `addr`
`MAP_ANONYMOUS`	Отображение является анонимным, а не отображением файла
`MAP_GROWSDOWN`	Соответствует флагу `VM_GROWSDOWN`
`MAP_DENYWRITE`	Соответствует флагу `VM_DENYWRITE`
`MAP_EXECUTABLE`	Соответствует флагу `VM_EXECUTABLE`
`MAP_LOCKED`	Соответствует флагу `VM_LOCKED`
`MAP_NORESERVE`	Нет необходимости резервировать память для отображения
`MAP_POPULATE`	Предварительно заполнить (prefault) таблицы страниц
`MAP_NONBLOCK`	Не блокировать при операциях ввода-вывода

Если какой-либо из параметров имеет недопустимое значение, то функция

do_mmap()

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

vm_area_struct

, которая выделяется в слябовом кэше

vm_area_cachep

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

vma_link()

. Затем обновляется значение поля

total_vm

в дескрипторе памяти. В конце концов, функция возвращает начальный адрес вновь созданного интервала адресов.

Системный вызов

mmap()

Возможности функции

do_mmap()

экспортируются в пространство пользователя с помощью системного вызова

mmap()

, который определен следующим образом.

void *mmap2(void *start,

 size_t length, int prot, int flags, int fd, off_t pgoff);

Этот системный вызов имеет имя

mmap2()

, т.е. второй вариант функции

mmap()

. Первоначальный вариант

mmap()

требовал в качестве последнего параметра смещение в байтах, а текущий вариант,

mmap2()

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

mmap()

, который соответствует стандарту POSIX, доступен через библиотеку функций языка С, как функция

mmap()

, но в ядре уже не реализован. Новый вариант библиотечной функции называется

mmap2()

. Обе эти библиотечные функции используют системный вызов

mmap2()

. При этом библиотечная функция

mmap()

переводит значение смещения из байтов в количество страниц памяти.

Функции

munmap()

do_munmap()

: удаление интервала адресов

Функция

do_munmap()

удаляет интервал адресов из указанного адресного пространства процесса. Эта функция объявлена в файле

следующим образом.

int do_munmap(struct mm_struct *mm,

 unsigned long start, size_t len);

Первый параметр указывает адресное пространство, из которого удаляется интервал адресов, начинающийся с адреса

start

и имеющий длину

len

байт. В случае успеха возвращается нуль, а в случае ошибки — отрицательное значение.

Системный вызов

munmap()

Системный вызов

munmap()

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

mmap()

и имеет следующий прототип.

int munmap(void*start, size_t length);

Данный системный вызов реализован в виде очень простой интерфейсной оболочки (wrapper) функции

do_munmap()

asmlinkage long sys_munmap(unsigned long addr, size_t len) {

 int ret;

 struct mm_struct *mm; mm = current->mm;

 down_write(&mm->mmap_sem);

 ret = do_munmap(mm, addr, len);

 p_write(&mm->mmap_sem);

 return ret;

Таблицы страниц

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

В операционной системе Linux таблицы страниц состоят из трех уровней[83]. Несколько уровней позволяют эффективно поддерживать неравномерно заполненные адресные пространства даже для 64-разрядных машин. Если бы таблицы страниц были выполнены в виде одного статического массива, то их размер, даже для 32-разрядных аппаратных платформ, был бы чрезвычайно большим. В операционной системе Linux трехуровневые таблицы страниц используются даже для тех аппаратных платформ, которые аппаратно не поддерживают трехуровневых таблиц (например, для некоторых аппаратных платформ поддерживается только два уровня или аппаратно реализовано хеширование). Три уровня соответствуют своего рода "наибольшему общему знаменателю". Для аппаратных платформ с менее сложной реализацией работа с таблицами страниц в ядре при необходимости может быть упрощена с помощью оптимизаций компилятора.

Таблица страниц самого верхнего уровня называется глобальным каталогом страниц (page global directory, PGD). Таблица PGD представляет собой массив элементов типа

pgd_t

. Для большинства аппаратных платформ тип

pgd_t

соответствует типу

unsigned long

. Записи в таблице PGD содержат указатели на каталоги страниц более низкого уровня, PMD.

Каталоги страниц второго уровня еще называются каталогами страниц; среднего уровня (page middle directory, PMD). Каждый каталог PMD — это массив элементов типа

pmd_t

. Записи таблиц PMD укалывают на таблицы РТЕ (page table entry, запись таблицы страниц).

Таблицы страниц последнего уровня называются просто таблицами страниц и содержат элементы типа

pte_t

. Записи таблиц страниц указывают на страницы памяти.

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

Рис. 14.1. Таблицы страниц

Каждый процесс имеет свои таблицы страниц (разумеется, потоки эти таблицы используют совместно). Поле

pgd

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

page_table_lock

, которая также находится в соответствующем дескрипторе памяти.

Структуры данных, связанные с таблицами страниц, сильно зависят от аппаратной платформы и определены в файле

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

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

fork()

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

fork()

Заключение

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

struct mm_struct

) и каким образом ядро представляет области памяти внутри этого адресного пространства (

struct vm_area_struct

). Также рассказывалось о том, как ядро создает (с помощью функции

mmap()

) и удаляет (с помощью функции

munmap()

) области памяти. Б конце были рассмотрены таблицы страниц. Так как операционная система Linux — это система с виртуальной памятью, то все эти понятия очень важны для понимания работы системы и используемой модели процессов.

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