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

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

SetPageDirty(page);

Ядро выполняет запись этой страницы памяти позже с помощью вызова метода writepage. Операции записи для файлов, открытых обычным образом (без отображения в память), выполняются более сложным путем. В основном, общая операция записи, которая реализована в файле mm/filemap.с, включает следующие шаги.

page =

 __grab_cache_page(mapping, index, &cached_page, &lru_pvec);

status =

 a_ops->prepare_write(file, page, offset, offset+bytes);

page_fault =

 filemap_copy_from_user(page, offset, buf, bytes);

status =

 a_ops->commit_write(file, page, offset, offset+bytes);

Выполняется поиск необходимой страницы памяти в кэше. Если такая страница в кэше не найдена, то создается соответствующий элемент кэша. Затем вызывается метод prepare_write, чтобы подготовить запрос на запись. После этого данные копируются из пространства пользователя в буфер памяти в пространстве ядра. И наконец данные записываются на диск с помощью функции commit_write.

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

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

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

Как было показано в предыдущем разделе, поиск в страничном кэше выполняется на основании информации объекта address_space и значения смещения. Каждый объект address_space имеет свое уникальное базисное дерево (radix tree), которое хранится в поле page_tree. Базисное дерево — это один из типов бинарных деревьев. Базисное дерево позволяет выполнять очень быстрый поиск необходимой страницы только на основании значения смещения в файле. Функции поиска в страничном кэше, такие как find_get_page и radix_tree_lookup, выполняют поиск с использованием заданного дерева и заданного объекта.

Основной код для работы с базисными деревьями находится в файле lib/radix-tree.c. Для использования базисных деревьев необходимо подключить заголовочный файл .

Старая хеш-таблица страниц

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

Использование глобальной хеш-таблицы приводило к четырем основным проблемам.

• Хеш-таблица защищалась одной глобальной блокировкой. Количество конфликтов при захвате этой блокировки было достаточно большим даже для не очень больших машин. В результате страдала производительность.

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

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

• Хеш-таблица требовала больше памяти, чем другие возможные решения.

Применение в ядрах серии 2.6 страничного кэша на основании базисных деревьев позволило решить эти проблемы.

Буферный кэш