Почему мы используем radix-tree (или xarray) для хранения кешей страниц?

Question

Я сейчас изучаю linux ядро ​​с пониманием linux ядра (3-е), и меня очень смущает причина, по которой используется дерево счисления для хранения целых кешей страниц с использованием дерева счисления. (Я слышал, что после версии 4.20 ядро ​​использует xarray).

Итак, вот мой вопрос:

Как только нам нужна некоторая информация об этом определенном I-узле, мы должны просмотреть кеш целых страниц, на который указывает «address_space».

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

Поиск в каких кешах страниц? Разве они не нужны нам все?

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

И дополнительные вопросы:

Если некий «I-узел» является хостом для address_space, и он содержит radix_tree_ root и в этом дереве radix, у нас есть все кэши страниц, содержащие все данные, относящиеся к файлу (на который указывает этот I- узел)?

Answer 1

Radix-дерево - это сжатый tr ie, где tr ie - это структура данных, которая реализует интерфейс ассоциативного массива и позволяет хранить значения как ключ-значение. Ключи обычно представляют собой строки, но можно использовать любой тип данных. Tr ie отличается от n-дерева своими узлами. Узлы тр ie не хранят ключи; вместо этого узел tr ie хранит односимвольные метки. Ключ, связанный с данным узлом, получается путем перехода от root дерева к этому узлу. Например:

    +-----------+
               |           |
               |    " "    |
               |           |
        +------+-----------+------+
        |                         |
        |                         |
   +----v------+            +-----v-----+
   |           |            |           |
   |    g      |            |     c     |
   |           |            |           |
   +-----------+            +-----------+
        |                         |
        |                         |
   +----v------+            +-----v-----+
   |           |            |           |
   |    o      |            |     a     |
   |           |            |           |
   +-----------+            +-----------+
                                  |
                                  |
                            +-----v-----+
                            |           |
                            |     t     |
                            |           |
                            +-----------+

Итак, в этом примере мы видим tr ie с ключами, go и cat. Сжатое дерево tr ie или основание системы счисления отличается от tr ie тем, что удаляются все промежуточные узлы, у которых есть только один дочерний элемент.

Деревья оснований имеют несколько пользователей в основном дереве ядра. Архитектура PowerP C использует дерево для сопоставления реальных и виртуальных номеров IRQ. Код NFS прикрепляет дерево к соответствующим структурам inode для отслеживания невыполненных запросов. Однако наиболее распространенное использование оснований системы счисления - это код управления памятью. Структура address_space, используемая для отслеживания резервного хранилища, содержит дерево счисления, которое отслеживает внутренние страницы, привязанные к этому сопоставлению . Среди прочего, это дерево позволяет коду управления памятью быстро находить страницы, которые загрязнены или подвергаются обратной записи.

Вот статья , в которой очень четко описан этот механизм проектирования.