Алгоритм чтения файла
Каждый inode, как и блок, имеет порядковый номер, уникальный в пределах файловой системы, и содержит информацию только об одном файле. Таким образом, для получения доступа к содержимому файла необходимо знать порядковый номер соответствующего ему inode-а.
Как было сказано выше, информация о физическом расположении файла содержится в inode. Эта информация представляет собой последовательность 32-х битных номеров блоков, содержащих данные файла (рис.1). Первые 12 номеров - это прямые ссылки на информационные блоки (direct blocks number). 13-й номер является косвенной ссылкой (indirect blocks number). В нём находится адрес блока, в котором хранятся адреса информационных блоков. 14-й номер - двойная косвенная ссылка (double blocks number), 15-й номер - тройная косвенная ссылка (triple blocks number).
Имя файла в состав inode не входит, установление соответствия между именами файлов и порядковыми номерами inode-ов выполняется через каталоги.
Каталоги
Файлы в UNIX- и POSIX-системах хранятся в древовидной иерархической файловой системе. Корень файловой системы - это корневой каталог, обозначенный символом "/". Каждый промежуточный узел в дереве файловой системы - это каталог. Конечные вершины дерева файловой системы являются либо пустыми каталогами, либо файлами. Абсолютное путевое имя файла состоит из имен всех каталогов, ведущих к указанному файлу, начиная с корневого каталога. Так, путевое имя /home/test.file означает, что файл test.file расположен в каталоге home, который, в свою очередь, находится в корневом каталоге "/".
Каталог, также как и файл, описывается при помощи inode. Содержимое каталога представляет собой массив записей, каждая из которых содержит информацию о файле, который находятся "внутри" текущего каталога.
Запись каталога имеет следующий формат:
- порядковый номер inode файла
- длина записи в байтах
- имя файла
- длина имени файла
Поиск номера inode файла всегда начинается с корневого каталога. Например, чтобы получить порядковый номер inode файла, находящегося в корневом каталоге, операционная система должна получить содержимое корневого каталога, найти в нем запись с именем этого файла, и извлечь из этой записи порядковый номер inode-a файла.
Несколько первых номеров inode зарезервированы файловой системой, их перечень содержится в заголовочном файле <linux/ext2_fs.h>:
/*
* Special inode numbers
*/
#define EXT2_BAD_INO 1 /* Bad blocks inode */
#define EXT2_ROOT_INO 2 /* Root inode */
#define EXT2_ACL_IDX_INO 3 /* ACL inode */
#define EXT2_ACL_DATA_INO 4 /* ACL inode */
#define EXT2_BOOT_LOADER_INO 5 /* Boot loader inode */
#define EXT2_UNDEL_DIR_INO 6 /* Undelete directory inode */
Для записи корневого каталога зарезервирован inode под номером 2 (root inode). Этот inode находится в группе блоков 0 и занимает вторую позицию в таблице inode-ов этой группы. Номер первого незарезервированного inode хранится в суперблоке.
Определив порядковый номер inode файла, ядро вычисляет номер группы, в которой этот inode расположен, и его позицию в таблице inode-ов группы. Считав из этой позиции inode, операционная система получает полную информацию о файле, включая адреса блоков, в которых хранится содержимое файла.
Номер группы блоков, в которой расположен inode, вычисляется по формуле:
group = (inode_num - 1) / inodes_per_group,
где group - искомый номер группы блоков
inode_num - порядковый номер inode, определяющего файл
inodes_per_group - число inode-ов в группе (эта информация находится в суперблоке).
Позиция inode-а в таблице inode-ов группы определяется по формуле:
index = (inode_num - 1) % inodes_per_groupe,
где index - позиция inode-а в таблице
Рассмотрим пример получения содержимого файла test.file, находящегося в корневом каталоге. Для чтения файла /test.file необходимо:
- в массиве записей корневого каталога найти запись об этом файле
- извлечь порядковый номер inode файла, вычислить номер группы, в которой этот inode расположен
- из дескриптора данной группы извлечь адрес таблицы inode-ов группы
- вычислить позицию inode-а в этой таблице
- считать inode файла
- из inode-а извлечь адреса информационных блоков и осуществить чтение информации, находящейся в этих блоках
На рис. 4 подробно показаны этапы чтения файла /test.file.
Этапы 1-6 - чтение корневого каталога:
1. Из группы блоков 0 считывается таблица дескрипторов групп
2. Из таблицы дескрипторов групп извлекается дескриптор группы блоков 0 и из него считывается адрес таблицы inode-ов группы 0
3. Из группы блоков 0 считывается таблица inode-ов
4. Порядковый номер inode корневого каталога фиксирован и равен 2, поэтому из таблицы inode-ов группы 0 считывается второй элемент, который содержит адрес блока с содержимым корневого каталога. Предположим, что этот блок расположен в группе блоков A
5. Из группы блоков A считывается блок, содержащий записи корневого каталога.
6. Выполняется поиск записи с именем "test.file". Если такая запись найдена, из нее извлекается порядковый номер inode файла "test.file".
Определив номер inode, можно получить доступ к информационным блокам файла (этапы 7-11):
7. Вычисляется номер группы, в которой находится данный inode, и его позиция в таблице inode-ов группы (предположим, что номер группы равен B, а позиция в таблице - X)
8. Из таблицы дескрипторов групп извлекаем дескриптор группы блоков B и из него считывается адрес таблицы inode-ов этой группы блоков
9. Из группы блоков B считывается таблица inode-ов
10. Из таблицы inode-ов группы блоков B считывается inode, находящийся в позиции X
11. Из считанного inode извлекается адреса блока с содержимым файла /test.file и выполняется чтение информации из блока с указанным адресом
Структурные типы, описывающие основные компоненты файловой системы ext2 - суперблок, дескриптор группы блоков, информационный узел, запись каталога - определены в заголовочном файле <linux/ext2_fs.h>. Рассмотрим кратко поля, которые входят в каждую из этих структур.
1. Структура суперблока struct ext2_super_block
__u32 s_inodes_count - общее число inode-ов в файловой системе
__u32 s_blocks_count - общее число блоков в файловой системе
__u32 s_free_blocks_count - количество свободных блоков
__u32 s_free_inodes_count - количество свободных inode-ов
__u32 s_first_data_block - номер первого блока данных (номер блока, в котором находится суперблок)
__u32 s_log_block_size - это значение используется для вычисления размера блока. Размер блока определяется по формуле: block size = 1024 << s_log_block_size
__u32 s_blocks_per_group - количество блоков в группе
__u32 s_inodes_per_group - количество inode-ов в группе
__u16 s_magic - идентификатор файловой системы ext2 (сигнатура 0xEF53)
__u16 s_inode_size - размер информационного узла (inode)
__u32 s_first_ino - номер первого незарезервированного inode
2. Структура дескриптора группы блоков struct ext2_group_desc
__u32 bg_block_bitmap - битовая карта занятости блоков группы
__u32 bg_inode_bitmap - битовая карта занятости inode-ов группы
__u32 bg_inode_table - адрес таблицы inode-ов группы
3. Структура инфрмационного узла struct ext2_inode
__u16 i_mode - тип файла и права доступа к нему. Тип файла определяют биты 12-15 этого поля:
- 0xA000 - символическая ссылка
- 0x8000 - обычный файл
- 0x6000 - файл блочного устройства
- 0x4000 - каталог
- 0x2000 - файл символьного устройства
- 0x1000 - канал FIFO
__u32 i_size - размер в байтах
__u32 i_atime - время последнего доступа к файлу
__u32 i_ctime - время создания файла
__u32 i_mtime - время последней модификации
__u32 i_blocks - количество блоков, занимаемых файлом
__u32 i_block[EXT2_N_BLOCKS] - адреса информационых блоков (включая все косвенные ссылки)
Значение EXT2_N_BLOCKS также определено в файле <linux/ext2_fs.h>:
/*
* Constants relative to the data blocks
*/
#define EXT2_NDIR_BLOCKS 12
#define EXT2_IND_BLOCK EXT2_NDIR_BLOCKS
#define EXT2_DIND_BLOCK (EXT2_IND_BLOCK + 1)
#define EXT2_TIND_BLOCK (EXT2_DIND_BLOCK + 1)
#define EXT2_N_BLOCKS (EXT2_TIND_BLOCK + 1)
4. Структура записи каталога struct ext2_dir_entry_2
#define EXT2_NAME_LEN 255
__u32 inode - номер inode-а файла
__u16 rec_len - длина записи каталога
__u8 name_len - длина имени файла
char name[EXT2_NAME_LEN] - имя файла
Ознакомившись со структурой файловой системы ext2, можно приступить к рассмотрению программной реализации драйвера файловой системы.
