Ядро включает в себя множество библиотечных функций для реализации полезных структур данных. Среди этих структур два типа деревьев: базисные деревья (radix trees или дерево остатков в некоторых источниках) и красно-чёрные деревья. Данная статья даёт обзор API для работы с базисными деревьями.
В Википедии есть статья о базисных деревьях, но применительно к базисным деревьям Linux описание не очень хорошее. Базисные деревья Linux являются механизмом, который сопоставляет (указатель) значение целочисленному ключу (тип long). Этот механизм эффективен, как хранилище и предоставляет достаточно быстую операцию поиска. Кроме того, базисные деревья Linux имеют некоторые свойства, обеспечиваемые ядром, включая тэги для конкретных вхождений.
Диаграмма чуть ниже изображает листовой узел базисного дерева Linux.
Узел содержит множество слотов, каждый из которых может хранить указатель на какие-то данные в зависимости от замысла того, кто создал это дерево. Пустые слоты содержат указатели на NULL. Эти деревья довольно широкие - в ядрах 2.6.16-rc листья имеют по 64 слотов каждый. Слоты индексируются по части целочисленного ключа (тип long). Если максимальное значение ключа меньше 64, всё дерево может быть представлено одним единственным узлом. Однако, как правило используются большие множества ключей - в противном же случае в подобных целях может быть использован обычный массив. Большое дерево может выглядеть, как показано на рисунке:
Это дерево имеет глубину 3 уровня. Когда ядро ищет определённый ключ, для поиска нужного слота в корневом узле используются первые 6 значащих битов. Следующие 6 битов индексируют средний узел, а последние 6 битов будут указывать на слот, содержащий указатель на нужные данные. Узлы, не имеющие потомков, не представлены в дереве, таким образом базисное дерево предоставляет эффективное хранилище данных ввиде разреженных деревьев.
Так выглядят структуры корня (include/linux/radix-tree.h) и обычного узла (lib/radix-tree.c) базисного дерева:
/*** radix-tree API starts here ***/
#define RADIX_TREE_MAX_TAGS 2
/* root tags are stored in gfp_mask, shifted by __GFP_BITS_SHIFT */
struct radix_tree_root {
unsigned int height;
gfp_t gfp_mask;
struct radix_tree_node *rnode;
};
#define RADIX_TREE_INIT(mask) { \
.height = 0, \
.gfp_mask = (mask), \
.rnode = NULL, \
}
#define RADIX_TREE(name, mask) \
struct radix_tree_root name = RADIX_TREE_INIT(mask)
#define INIT_RADIX_TREE(root, mask) \
do { \
(root)->height = 0; \
(root)->gfp_mask = (mask); \
(root)->rnode = NULL; \
} while (0)
struct radix_tree_node {
unsigned int height; /* Height from the bottom */
unsigned int count;
struct rcu_head rcu_head;
void *slots[RADIX_TREE_MAP_SIZE];
unsigned long tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
};В основной версии ядра базисные деревья используются в нескольких местах. На архитектуре PowerPC они используются для отображения реальных и виртуальных номеров линий запроса прерывания (IRQ). Код NFS ставит в соответствие релевантному индексному узлу (inode) дерево для отслеживания запросов. Наиболее широко используются базисные деревья в подсистеме управления памятью. Структура address_space, используемая в страничном кэше ядра для хранения информации об устройстве резервной памяти и отображения страниц, содержит базисное дерево для отслеживания страниц, назначенных данному отображению. Кроме всего прочего, это дерево позволяет коду подсистемы управления памятью быстро находить грязные страницы и страницы в режиме обратной записи (dirty and writeback pages).
Как и в случаях с другими структурами данных ядра, есть два способа объявить и проинициализировать базисное дерево:
#include <linux/radix-tree.h> RADIX_TREE(name, gfp_mask); /* Declare and initialize */ struct radix_tree_root my_tree; INIT_RADIX_TREE(my_tree, gfp_mask);
Первое - объявление и инициализация переменной базисного дерева с заданным именем; второе - инициализация дерева во время выполнения. В любом случае неоходимо указать значение gfp_mask, чтобы уведомить ядро, каким образом должна быть выделена память под дерево. Если операции базисного дерева, такие, как вставка, в частности, будут выполняться в атомарном контексте, маска должна содержать флаг GFP_ATOMIC.
Функции добавления и удаления записей:
int radix_tree_insert(struct radix_tree_root *tree, unsigned long key,
void *item);
void *radix_tree_delete(struct radix_tree_root *tree, unsigned long key);Вызов функции radix_tree_insert() приведёт ко вставке новых данных (сопоставленных с ключом) в дерево. Операция вставки может потребовать выделения памяти; если выделение завершилось неудачей, операция вставки также завершается с кодом возврата -ENOMEM. Код вставки не допустит затирания существующих данных; если в дереве уже присутствует заданный ключ, radix_tree_insert() возвратит -EEXIST. В случае успеха код возврата равен нулю. radix_tree_delete() удаляет данные, сопоставленные с данным ключом дерева, возвращая указатель на эти данные, если он был.
Возможны ситуации, в которых ошибка вставки новых данных в базисное дерево стала бы значительной проблемой. Чтобы помочь избежать таких ситуаций предусмотрены две специальные функции:
int radix_tree_preload(gfp_t gfp_mask); void radix_tree_preload_end(void);
Эта функция попытается выделить для дерева достаточно памяти (используя значение gfp_mask), чтобы гарантировать, что последующая операция вставки в базисное дерево не завершится неудачей. Структуры, под которые выделена память, хранятся в переменной, привязанной к процессору, а это значит, что вызывающая функция должна произвести вставку до перепланирования или миграции на другой процессор. Таким образом, в случае успеха radix_tree_preload() возвратит управление вызывающей функции с запретом вытеснения; впоследствии вызывающий код должен обеспечить разрешение вытеснения с помощью вызова функции radix_tree_preload_end(). В случае неудачи код возврата равен значению -ENOMEM, а вытеснение не запрещено.
Поиск в базисном дереве может осуществляться несколькими способами:
void *radix_tree_lookup(struct radix_tree_root *tree, unsigned long key);
void **radix_tree_lookup_slot(struct radix_tree_root *tree, unsigned long key);
unsigned int radix_tree_gang_lookup(struct radix_tree_root *root,
void **results,
unsigned long first_index,
unsigned int max_items);Самый простой способ - использование функции radix_tree_lookup(). Эта функция ищет в дереве ключ и возвращает ассоциированную с ним запись (или NULL при неудаче). radix_tree_lookup_slot() напротив возратит слот, содержащий необходимые данные. Вызывающий код затем может изменить ассоциированный с ключом указатель. Если запись не существовала на момент вызова функции radix_tree_lookup_slot() не создаст новый слот для указателя. В таких случаях для вставки новых данных необходимо использовать radix_tree_insert().
Наконец radix_tree_gang_lookup() возратит до max_items записей, отсортированных по ключам в возрастающем порядке, начиная со значения first_index. Число возвращаемых записей может быть меньше запрошенного, но меньшее значение (не нуль) не означает, что в дереве больше нет значений.
Необходимо также иметь ввиду, что при поиске или сортировке базисное дерево не держит блокировок само по себе. Задача обеспечения когерентности данных в дереве при работе с несколькими потоками полностью ложится на вызывающий код. Доступен патч Ника Пиджина (Nick Piggin), который добавляет поддержку механизма RCU при удалении узлов дерева; этот патч позволяет осуществлять поиск без блокировки, пока (1) результирующий указатель используется в атомарном контексте и (2) вызывающий код сам не способствует появлению ситуации гонок. Однако, неизвестно, когда патч будет принят в основную ветку ядра (К сожалению, я не могу сказать точно, с какой версии, но патч уже принят и в ядре 2.6.30, например, RCU-синхронизация доступна в основной ветке. Очевидно, патч был принят уже довольно давно. Основной для этой статьи является сообщение на lwn.net, датированное 2006 годом, поэтому такая неточность вполне закономерна).
Базисное дерево поддерживает "тэги", которые позволяют устанавливать отдельные биты на записях, хранимых в дереве. В частности, тэги используются для маркировки грязных страниц и страниц в режиме обратной записи. API для работы с тэгами выглядит так:
void *radix_tree_tag_set(struct radix_tree_root *tree,
unsigned long key, int tag);
void *radix_tree_tag_clear(struct radix_tree_root *tree,
unsigned long key, int tag);
int radix_tree_tag_get(struct radix_tree_root *tree,
unsigned long key, int tag);radix_tree_tag_set() присвоит данный тэг (tag) записи, идентифицируемой ключом (key); попытка присвоить тэг по несуществующму ключу будет являться ошибкой. Возвращаемое значение в случае успеха - указатель на запись, помеченную тэгом. Тэг выглядит, как обычное целое число, а текущий код позволяет использование не более двух тэгов (Как видно из кода, приведённого в самом начале статьи, это ограничение справедливо и сейчас. См. значение макроопределения RADIX_TREE_MAX_TAGS. Код взят из ветки 2.6.30). Имейте ввиду, что использование в качестве тэга любого значения, отличного от 0 или 1 приведёт к порче памяти в нежелательном месте; вас предупредили.
Тэг может быть уалён вызовом функции radix_tree_tag_clear(); и снова, в качестве возврата функция отдаст указатель на данные, с который снели тэг. Функция radix_tree_tag_get() производит проверку, был ли данный тэг установлен на записи, идентифицируемой данным ключом; если ключ не найден, функция возвратит 0, -1 - если ключ найден, но записи не был присвоен данный тэг, и +1 - в противном случае. Сейчас эта функция закомментирована в исходном коде, т.к. она не используется кодом текущей версии ядра (Опять же, если судить по коду версии 2.6.30, функция на месте, но в комментариях дано пояснение, что она используется исключительно кодом для внутреннего тестирования ядра).
Для получения тэгов, писвоенных записям предусмотрены две функции:
int radix_tree_tagged(struct radix_tree_root *tree, int tag);
unsigned int radix_tree_gang_lookup_tag(struct radix_tree_root *tree,
void **results,
unsigned long first_index,
unsigned int max_items,
int tag);radix_tree_tagged() возвращает ненулевое значение, если какой-либо из записей, хранимых в дереве присвоен данный тэг. Список записей с данным тэгом может быть получен с помощью функции radix_tree_gang_lookup_tag().
В заключение можно отметить интересную особенность API базисных деревьев: отсутствует функция, уничтожающая базисное дерево. Как очевидно подразумевается, базисное дерево будет существовать вечно. На самом деле, удаление всех записей из не корневых узлов базисного дерева освободит память, выделенную для хранения данных, а после этого дерево можно удалить обычным способом, освободив память, занятую корневым узлом.
No comments:
Post a Comment