Роберт Лав - Разработка ядра Linux

Второе поле, 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] Утилита pmap(1) печатает форматированный список областей памяти процесса. Результат ее вывода несколько более удобочитаем, чем информация, получаемая из файловой системы /proc , но это одна и та же информация. Данная утилита включена в новые версии пакета procps . форматирует эту информацию в следующем, более удобочитаемом виде.

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, которые содержат глобальные переменные, помечаются как имеющие права на запись и чтение, а не на выполнение.