Лекция 4

начало 4 лекции в конце 3 лекции (для неразрывности логически целой части).

Структура list_head везде встречается в объявлении в ядре. Почему используются везде двухсвязные списки list_head? Для ускорения поиска. Двухсвязный список может обеспечить более быстрый поиск так как можем ходить в обе стороны(по условию). Бинарные деревья это слишком громоздко и они могут выраждаться в линейный список. Со сбалансированными деревьями тоже сложно работать(много действий).

Олег Цирюлик описывает функции ядра для работы с двухсвязными списками ядра. Эта информация была у нас в первом семестре, мы могли увидеть номера inode и делали упражнение на жёсткие ссылки и видели что у жёсткой ссылки номер inode будет как у исходного файла. Для того чтобы получить доступ к определённому файлу по его имени, необходимо иметь inode сопоставленный с данным файлом. То есть в системе должна быть информация которая сопоставляет имена файлов и номера inode. Для того чтобы это было более запоминающимся нарисуем простенькую картиночку.

Данная иллюстрация демонстрирует структуру inode каталога.

Допустим, inode каталога в котором находимся имеет номер 3470036. "."(текущая директория) будет иметь тот же самый номер. ".." родительский каталог с другим inode. В этой директориии могут быть поддиректории и файлы.

Как мы уже отметили в структуре struct inode имеется указатель на inode_operations. Это перечисление операций которые определены на inode в vfs.Но если пишем свою vfs, то можем определить свой перечень операций на inode. Если в вашей struct inode_operations не определены какие-то поля, то система просто присваивает им значение null. Всё что мы можем написать предопределено разработчиками ядра.

struct inode_operations.

Структура inode_operations содержит системные вызовы которые позволяют создавать директории, работать с директориями, обеспечивают поиск файлового индекса и соответственно мы рассмотрим только основные поля которые большей частью нам с вами знакомы по работе с соответствующими системными вызовами. Сейчас увидим перечень системных вызовов. Раньше просто использовали mkdir, теперь будем понимать, что этот системный вызов опеределен struct inode_operations.

struct inode_operations
{
	//поиск файлового индекса в указанном каталоге
	struct dentry *(*lookup)(struct inode*, struct dentry*, unsignes int);
	...
	int(*permission)(struct inode*, int);
	...
	//системный вызов для создания жёсткой ссылки на файл из каталога который указан первым(аргументом) и жёсткая ссылка будет существовать в каталоге который указан последним
	int (*link)(struct dentry*, struct inode*, struct dentry*);
	...
	int (*symlink)(struct inode*, struct dentry*, const char*);
	...
	//системный вызов тут параметры полностью соответствуют нашей с вами практике, фактически указываем имя каталога и права доступа к каталогу и тд.
	int (*mkdir)(struct inode*, struct dentry*, umode_t);
	...
}

Тут структура значительно сокращена, оставили минимум на основании которого можно показать общие вещи для работы с системными вызовами.

Везде видим struct dentry и это одна из четырёх основных структур интерфейса VFS. Любой dentry является компонентом пути к какому-либо файлу. Например если у нас имеется следующий путь:"/mnt/cdrom/foo" то компонентами каждый из которых будет отдельным dentry являются /, mnt, cdrom, foo. Компоненту каталога не соответствует никакой файл на диске, всё это создаётся налету. При этом надо понимать что в Linux всё файл и директория тоже файл. Любая созданная директория имеет inode.

struct dentry
{
        atomic_t d_count;     /* счетчик использования */
	unsigned int d_flags; /* флаги элемента каталога */
	...
	struct hlist_bl_node d_hash; /* lookup hash list*/
	struct dentry *d_parent /* объект dentry родительского каталога */
	struct qstr d_name; /* имя dentry */
	struct inode *d_inode; /* соответствующий файловый индекс */
	unsigned char d_iname[DName_INLINE_LEN]; /*small names*//* имя dentry */
	...
	const struct dentry_operations *d_op;   /* таблица операций с элементом каталога */
	struct super_block *d_sb;  /* связанный суперблок */
	struct list_head d_child;  /* список объектов у родительского экземпляра */
	struct list_head d_subdirs; /*our children */  /* подкаталоги */
	...
}

Видим, что здесь уже из самой структуры видно, что поддерживается дерево каталогов. Корневой каталог это struct superblock *superblock это корень данного дерева каталогов (данной файловой системы).

Любой dentry может находиться в одном из трёх состояний:

1. используемый (used)

2. неиспользуемый(unused)

3. негативный(часто используется обозначение противоречивый)(negative)

Используемый объект dentry соответствует существующему файловому индексу. То есть поле inode указывает на соответствующий объект типа mode, соответственно поле d_count имеет положительное значение, это поле указывает сколько раз используется данный объект dentry, соответственно такой dentry не может быть просто так удалён.

Неиспользуемый объект dentry соответствует существующему объекту inode, то есть поле d_inode указывает на соответствующий дескриптор файла, но d_count = 0 (это значит что vfs в данный момент поле не использует). Такой элемент каталога может быть удален поскольку он никем не используется.

Негативный объект dentry не связан с существующий inode. В поле d_inode стоит значение null. Такое возможно если или inode был удалён или соответствующий элемент пути объект dentry никогда не существовал. Такие объекты элементов каталога сохраняются, чтобы возможно в будущем поиск по соответствующему пути выполнялся быстрее(поиск по пути составной частью которого может являться такой объект dentry).

КЕШ ОБЪЕКТОВ DENTRY

Посмотрим и оценим работу которую необходимо выполнить системе для того чтобы получить доступ к файлу.

В примере демонстрируются выполняемые действия при доступе к user/ast/mbox.

mbox — общее название форматов файлов, используемых для хранения сообщений электронной почты.

Имя inode6 обращаемся к этому inode чтобы получить соответствующую информацию. В inode6 находится информация о блоке в котором находится соответствующий каталог user, то есть в блоке 132. Мы говорили что файлы хранятся во вторичной памяти, они разделены на блоки(мин адресуемая информация вторичного носителя - блок). Элемент каталога user, его информация находится в блоке 132. А эта информация находится в соответствующем inode. В блоке 132 находится содержимое этого элемента каталога. Это или поддиректории или файлы. Мы видим что следующий элемент пути ast имеет inode 26. Происходит обращение к inode. Из полученного inode видим, что данный dentry находится в блоке 406. Соответственно идёт обращение к диску к блоку 406 (здесь нет стреклочки так как это другое действие, это обращение к носителю). Происходит считывание информации из блока 406 это содержимое директории ast в которой находятся или поддиректории или файлы. Видим что у mbox inode 60. Далее обращаемся по этому inode и можем из соответствующего mbox считать нужную нам информацию.

Ядро кеширует объекты dentry, то есть в ядре имеется кеш объектов dentry который состоит из трёх частей.

1. Список используемых (used) объектов dentry которые связаны с определённым inode. То есть в поле d_inode находится номер(индекс) inode. Поскольку на один и тот же inode могут ссылаться несколько раз, то такому inode может соответствовать несколько объектов dentry(hardlink). Соответственно здесь будет связанный список.

2. Список неиспользуемых (unused) и негативных (negative) объектов dentry по алгоритму LRU(least recently used). Элементы такого списка отсортированы по времени. Мы знаем как выполняется работа с таким списком. Мы рассматривали алгоритм LRU по отношению к страницам. При каждом обращении к странице такая странца перемещается в хвост списка. Удаление осуществляется из головы. В таком списке находятся объекты к которым были недавние обращения.

3. Хеш-таблица и хеш функция которые позволяют быстро преобразовать заданный путь в объект dentry. Хеш таблица - массив dentry_hashtable. Каждый элемент этого массива является указателем на список тех объектов dentry, которые соответствуют определённому ключу. Размер такого массива в систем зависит от объёма памяти. Значение ключа определяется функцией d_hash(), что позволяет каждой файловой системе реализовать свою хеш-функцию.

Поиск хеш-таблицы выполняется с помощью функции d_lookup(). Если в кеше d_cache(?) соответствующий объект найден, то возвращается значение, иначе возвращается null. Очевидно что кеширование элементов каталога и файловых индексов крайне желательно, так как доступ к файлу это операция, которая выполняется как в пространстве, так и во времени. При этом доступ к одному и тому же файлу могут осуществлять разные процессы, причём неоднократно. Здесь заложена идея именно LRU. Будут из списка удаляться наименее используемые. Всё это безусловно уменьшает время доступа к соответствующему файлу. (Директория тоже файл.) Подразумевается когда говорят, что доступ к файлам выполняется в пространстве, то что в системе разные процессы желают получить доступ к файлам которые находятся в одном и том же каталоге. Соответственно если этот объект dentry будет храниться в хеш-таблице, то это существенно сократит доступ к файлам в этом элементе каталога. То есть хранение этой информации в соответствуюшем кеше как для использования одного и того же файла многократно крайне полезно, так и для использования разных файлов в одной и той же директории крайне полезно.

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