Роберт Лав - Разработка ядра Linux

struct address_space {

struct inode *host; /* файловый индекс, которому

принадлежит объект */

struct radix_tree_root page_tree; /* базисное дерево

всех страниц */

spinlock_t tree_lock; /* блокировка для защиты

поля page_tree */

unsigned int i_mmap_wrltable; /* количество областей

памяти с флагом VM_SHARED */

struct prio_tree_root i_mmap; /* список всех отображений */

struct list_head i_mmap_nonlinear; /* список областей

памяти с флагом VM_NONLINEAR */

spinlock_t i_mmap_lock; /* блокировка поля i_mmap */

atomic_t truncate_count; /* счетчик запросов

truncate */

unsigned long nrpages; /* общее количество страниц */

pgoff_t writeback_index; /* смещения начала

обратной записи */

struct address_space_operations *a_ops; /* таблица операций */

unsigned long flags; /* маска gfp_mask

и флаги ошибок */

struct backing_dev_info *backing_dev_info; /* информация

упреждающего чтения */

spinlock_t private_lock; /* блокировка

для частных отображений */

struct list_head private_list; /* список

частных отображений */

struct address_spacs *assoc_mapping; /* соответствующие

буферы */

};

Поле i_mmap— это дерево поиска по приоритетам для всех совместно используемых и частных отображений. Дерево поиска по приоритетам— это хитрая смесь базисных и частично упорядоченных бинарных деревьев [86] Реализация ядра основана на базисном дереве поиска по приоритетам, предложенном в работе Edward M. McCreight, опубликованной в журнале SIAM Journal of Computing, May 1985, vol. 14. №2, P. 257–276. .

Всего в адресном пространстве nrpages страниц памяти.

Объект address_spaceсвязан с некоторым другим объектом ядра, обычно с файловым индексом. Если это так, то поле hostуказывает на соответствующий файловый индекс. Если значение поля hostравно NULL, то соответствующий объект не является файловым индексом; например, объект address_spaceможет быть связан с процессом подкачки страниц (swapper).

Поле a_opsуказывает на таблицу операций с адресным пространством так же, как и в случае объектов подсистемы VFS. Таблица операций представлена с помощью структуры struct address_space_operations, которая определена в файле следующим образом.

struct address_space_operations {

int (*writepage)(struct page*, struct writeback_control*);

int (*readpage)(struct file*, struct page*);

int (*sync_page)(struct page*);

int (*writepages)(struct address_space*,

struct writeback_control*);

int (*set_page_dirty)(struct page*);

int (*readpages)(struct file*, struct address_space*,

struct list_head*, unsigned);

int (*prepare_write)(struct file*, struct page*,

unsigned, unsigned);

int (*commit_write)(struct file*, struct page*,

unsigned, unsigned);

sector_t (*bmap)(struct address_space*, sector_t);

int (*invalidatepage)(struct page*, unsigned long);

int (*releasepage)(struct page*, int);

int (*direct_IO)(int, struct kiocb*, const struct iovec*,

loff_t, unsigned long);

};

Методы read_pageи write_pageявляются наиболее важными. Рассмотрим шаги, которые выполняются при страничной операции чтения.

Методу чтения в качестве параметров передается пара значений: объект address_spaceи смещение. Эти значения используются следующим образом для поиска необходимых данных в страничном кэше.

page = find_get_page(mapping, index);

где параметр mapping— это заданное адресное пространство, a index— заданная позиция в файле.

Если в кэше нет необходимой страницы памяти, то новая страница памяти выделяется и добавляется в кэш следующим образом.

struct page *cached_page;

int error;

cached_page = page_cache_alloc_cold(mapping);

if (!cached_page)

/* ошибка выделения памяти */

error =

add_to_page_cache_lru(cached_page, mapping, index, GFP_KERNEL);

if (error)

/* ошибка добавления страницы памяти в страничный кэш */

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

error = mapping->a_ops->readpage(file, page);

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

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. Для использования базисных деревьев необходимо подключить заголовочный файл .