Linux Kernel (Ядро линукса) (часть 2)

Базисное дерево

В Linux файлы могут быть очень большими, до нескольких терабайт. При работе с большим файлом кэш страниц может оказаться заполненным таким большим количеством страниц файлов, что последовательное их сканирование может потребовать слишком много времени. Для повышения эффективности просмотра кэша страниц в Linux 2.6 используется большой набор деревьев поиска, по одному на каждый объект address space.

Поле page tree объекта address space является корнем базисного дерева, содержащего указатели на дескрипторы страниц владельца. При заданном индексе страницы, обозначающем ее позицию в образе диска ее владельца, ядро может выполнить довольно быстрый просмотр и определить, находится ли в кэше требуемая страница. При поиске страницы ядро интерпретирует индекс как путь по базисному дереву и быстро доходит до места, где хранится (или должен храниться) дескриптор страницы. Найдя дескриптор, ядро может прочитать его, а также быстро определить, является ли страница "грязной” (нужно ли ее принудительно записать на диск), и происходит ли в этот момент ввод/вывод данных страницы.

Каждый узел базисного дерева может иметь до 64 указателей на другие узлы или на дескрипторы страниц. Узлы нижнего уровня содержат указатели на дескрипторы страниц (листья), а узлы на более высоких уровнях содержат указатели на другие узлы (потомки). Каждый узел представлен структурой radix tree node, состоящей из трех полей: slots, массива из 64 указателей, count, счетчика указателей, не равных null, и tags (двухэлементного массива флагов, который мы обсудим в разд. "Теги базисного дерева" далее в этой главе). Корень дерева представлен структурой radix tree root, которая имеет три поля, height обозначает текущую высоту дерева (количество уровней, исключая уровень листьев), gfpmask задает флаги, используемые при запросе памяти для нового узла, a mode указывает на структуру radix tree node, соответствующую узлу на уровне 1 (если таковой имеется).

Рассмотрим простой пример. Если ни один из индексов, хранящихся в дереве, не превышает 63, высота дерева равна 1, потому что все 64 потенциальных листа могут быть сохранены в узле первого уровня Если же в кэше страниц нужно сохранить новый дескриптор, соответствующий индексу 131, то высота дерева увеличивается до двух, чтобы оно могло указывать на индексы вплоть до 4095 приведены максимальные индексы страниц и соответствующие максимальные размеры файлов для каждой высоты базисного дерева в 32-разрядной архитектуре. В этом случае наибольшая высота базисного дерева равна шести, хотя маловероятно, что кэш страниц в вашей системе будет использовать такое огромное дерево. Поскольку индекс страницы хранится в 32-битовой переменной, то при высоте дерева в шесть уровней узел на самом верхнем уровне может иметь до четырех потомков.

Чтобы лучше понять, как происходит поиск страницы, вспомним, как система управления страницами использует Таблицы Страниц для преобразования линейных адресов в физические. Как было сказано в главе 2, 20 старших битов линейного адреса разбиваются на два поля по 10 битов: первое является смещением в каталоге страниц, а второе — смещением в Таблице Страниц, на которую указывает запись в каталоге страниц.

В базисном дереве предпринят аналогичный подход. Эквивалентом линейного адреса здесь является индекс страницы. Однако количество полей, рассматриваемых в индексе страницы, зависит от высоты базисного дерева. Если она равна 1, представлены только индексы от 0 до 63, и шесть младших битов индекса страницы интерпретируются как индекс в массиве slots для единственного узла на уровне 1. Если же базисное дерево имеет высоту 2, то индексы представляют диапазон от 0 до 4095. Тогда 12 младших битов индекса страницы разбиваются на два поля по 6 битов. Старшее поле служит индексом массива для узла на уровне 1, а младшее — индексом массива для узла на уровне 2. Для любой другой высоты базисного дерева предпринимается аналогичный подход. При высоте, равной 6, два старших бита индекса страницы содержат индекс массива для узла первого уровня, следующие 6 битов содержат индекс массива для узла на уровне 2, и т. д. до шести младших битов, содержащих индекс массива для узла на уровне 6.
Если максимальный индекс в базисном дереве меньше индекса страницы, которую нужно добавить, ядро соответственно увеличивает высоту дерева. Содержимое промежуточных узлов базисного дерева зависит от значения индекса страницы.