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

Теги базисного дерева

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

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

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

Та же идея применяется и в отношении флага PG writeback, который означает, что страница в данный момент записывается на диск. Таким образом, каждый узел базисного дерева размножает два флага дескриптора страницы: PG dirty и PG writeback Для их хранения каждый узел содержит два массива из 64 битов в поле tags. Массив tags[0] (или pagecache_ tag_dirty) является тегом грязь”, а массив tags[i] (или pagecache_tag_ writeback) является тегом обратной записи.

Функция radix tree tag set вызывается при установке флага PG dirty или PG writeback в кэшированной странице. Она принимает три параметра: корень базисного дерева, индекс страницы и тип устанавливаемого флага ( pagecache_tag_dirty или pagecache_tag_writeback). Функция совершает обход от корня дерева вниз до листа, соответствующего заданному индексу. Для каждого узла на пути от корня до листа функция устанавливает тег, ассоциированный с указателем на следующий узел пути. Затем она возвращает адрес дескриптора страницы. В результате каждый узел на пути от корня до листа помечен должным образом.

Функция radix tree tag clear вызывается при сбросе флага PG dirty или PG writeback в кэшированной странице. Она принимает те же параметры, что и функция radix tree tag set о. Функция совершает обход от корня дерева ВНИЗ ДО листа, строя массив структур radix_tree_path, описывающих путь. Затем функция идет в обратном направлении, от листа до корня: она сбрасывает тег узла на самом нижнем уровне, затем проверяет, все ли теги в массиве этого узла сброшены. Если это так, функция сбрасывает соответствующий тег в родительском узле на более высоком уровне, проверяет, все ли теги сброшены у этого узла, и т. д. По окончании работы она возвращает адрес дескриптора страницы.

Когда дескриптор страницы удаляется из базисного дерева, соответствующие теги в узлах на пути от корня к листу должны быть обновлены. Функция radix tree deieteo делает это корректно (хотя мы и не упомянули об этом факте в предыдущем разделе). Однако функция radix tree insert о не обновляет теги, поскольку предполагается, что у каждого дескриптора страницы, вставляемого В базисное дерево, флаги PG dirty И PG writeback сброшены. Впоследствии, если понадобится, ядро сможет вызвать функцию radix_tree_tag_set.

Функция radix tree tagged о использует массивы флагов, имеющиеся во всех узлах дерева, для проверки, содержит ли базисное дерево хотя бы одну
страницу с заданным состоянием. Функция без труда справляется с этим заданием, выполняя следующий код (root — указатель на структуру radix_ tree root базисного дерева, a tag — проверяемый флаг):
for (idx = 0; idx rnode->tags[tag][idx]) return 1;}return 0;
Поскольку можно предположить, что теги во всех узлах базисного дерева обновлены корректно, функции radix tree taggedo достаточно проверить теги узла на уровне 1. Эта функция полезна при определении, содержит ли индексный дескриптор грязные” страницы, которые следует записать на диск. Обратите внимание, что на каждом шаге цикла функция проверяет, установлен ли хотя бы один из 32 флагов, хранящихся в переменной типа unsigned long.
Функция f ind get pages tag аналогична функции f ind get pages , НО она возвращает только страницы, помеченные с помощью параметра tag. Как мы увидим в разд. "Запись "грязных" страниц на диск", эта функция очень важна для быстрого поиска всех грязных” страниц индексного дескриптора.