Файловая система extX. Как адресуются блоки файлов?

В extX (как и многих других файловых системах из семейства UNIX), так называемый индексный дескриптор (inode) играет ту же самую роль, что и файловая запись в NTFS. Здесь сосредоточена вся информация о файле: тип файла (обычный файл, каталог, символьная ссылка и т. д.), его логический и физический размер, схема размещения на диске, время создания, модифика­ции, последнего доступа или удаления, права доступа, а также ссылки на файл.

Количество полей в каждом индексном узле является статической величиной. Дополнительная информация сохраняется в расширенных атрибутах и косвенных указателях, о которых речь пойдет далее в этой главе. Состояние выделения индексного узла определяется по карте индексных узлов, местонахождение которой задается в дескрипторе группы. Поле размера в новых версияхextX является 64-разрядным, но в старых версиях оно содержало всего 32 бита, что делало невозможной работу с файлами, размер которых превышал 4 Гбайт. В новых версиях старшие 32 бита размера хранятся в поле, которое ранее не использовалось. Индексный узел содержит информацию о размере файла, его владельце и временных штампах.

Файловая система extX проектировалась еще в расчете на эффективную работу с небольшими файлами.

По этой причине в каждом индексном узле могут храниться адреса первых 12 блоков, выделенных файлу. Эти адреса называются прямыми указателями. Если для хранения файла потребуется более 12 блоков, выделяется специальный блок для хранения остальных адресов. Указатель на него называется косвенным указателем блоков. Все адреса блоков занимают 4 байта, а общее количество адресов в блоке зависит от размера блока. Косвенный указатель хранится в индексных узлах.

Если файл содержит больше блоков, чем помещается в 12 прямых указателях и в косвенном блоке, используется механизм двойной косвенной адресации. Другими словами, индексный узел ссылается на блок, содержащий список косвенных указателей на блоки; каждый такой указатель ссылается на блоки, содержащие список прямых указателей.

Если ли же файлу потребуется еще больше места, можно воспользоваться тройной косвенной адресацией: такой блок содержат набор адресов блоков с двойной адресацией, которые, в свою очередь, содержат адреса блоков косвенной адресации. Графическое представление каждой из этих структур данных показано на рис. 1. Каждый индексный узел содержит :

- 12 прямых указателей,

- один косвенный указатель,

- один указатель двойной адресации,

- и один указатель тройной адресации.

Рис. 1. Примеры реализации косвенной адресации на одном (а), двух (б) и трех уровнях (в)

Первые 12 блоков, занимаемых файлом, называются непосредственными блоками. Они хранятся в массиве directblocksнепосредственно в теле inode. Каждый элемент массива представляет собой 32-битный номер блока.

При среднем значении block_size, равном 4 Кбайт, непосредственные блоки могут адресовать до 4x12 == 48 Кбайт данных. Если файл превышает этот размер, создаются один или несколько блоков косвенной адресации (indirectblock).

Первый блок косвенной адресации (1xindirectblock или просто indirectblock) хранит ссылки на другие непосредственные блоки. Адрес этого блока хранится в поле i_indirect_block в inode.

Как легко вычислить, он адресует порядка BLOCK_SIZE/sizeof(DWORD) * block_size= 4096/4 *4 Мбайт данных. Еслиэтогоокажетсянедостаточно, создаетсякосвенныйблокдвойнойкосвеннойадресации (2хindirect block или double indirect block), хранящийуказателинакосвенныеблоки, чтопозволяетадресовать(BLOCK_SIZE/sizeof(DWORD))**2* BLOCK_SIZE =4096/4 ** 4096 == 4 Гбайтданных. Если же и этого все равно недостаточно, создается блок тройной косвенной адресации (3х indirectblockили tripleindirectblock), содержащий ссылки на блоки двойной косвенной адресации.

Иерархия непосредственных блоков и блоков косвенной адресации показана на рис. 2 (от индексного дескриптора до блоков файла).

По сравнению с NTFS такая схема хранения информации о размещении устроена намного проще. Вместе с тем, она и гораздо "прожорливее". С другой стороны, ее несомненное достоинство по сравнению с NTFS состоит в том, что поскольку все ссылки хранятся в неупакованном виде, для каждого блока файла можно быстро найти соответствующий ему косвенный блок, даже если inode полностью разрушен.

Логическое представление файла отличается от его физического представления. Логическое представление – можно получить распечатав файл (мы видим массив символов, которые представляют содержимое файла). Физическое представление определяет истинную организацию файла на диске. Файл, размер которого превышает один блок, обычно разбросан по диску. При доступе к файлу, система находит отдельные его блоки, и в правильном порядке организует логическое представление информации в файле.

Рис. 2. Варианты порядка размещения блоков файла на диске - иерархия непосредственных и косвенных блоков (блок косвенной адресации третьего порядка здесь не показан – см. рис. 1 - в)

Индексный дескриптор.

При такой организации файлов в ОС существует список, который показывает, где и в какой последовательности расположены физические блоки, составляющие файл, чтобы можно было конвертировать физическое представление файла в логическое. Этот список называют списком индексных дескрипторов, или i-узлов (i-nodes).

Каждый файл определяется индексным дескриптором, который содержит всю необходимую информацию о данном файле. Сюда записываются режим, тип файла, его длина в байтах, идентификаторы владельца и группы, дата последней модификации. Длина индексного дескриптора составляет 64 байта (его структуру можно найти в файле /usr/include/sys/inode.h).

Наиболее важная частъ i-узла (индексного дескриптора) это список адресов на диске (пример списка адресов см. табл.1).

 Таблица 1

Список адресов на диске - это 13 номеров блоков на диске, хранящихся в индексном дескрипторе. Первые 10 номеров задают первые 10 блоков файла. Длина блока, которую использует файловая система, может быть различна, но обыкновенно составляет 1024 байта в блоке. Если данные файла умещаются в первых 10 блоках или даже не занимают их все, то лишь несколько элементов списка содержат дисковые адреса. Так, если файлу достаточно четырех блоков, то первые четыре элемента списка включают соответствующие адреса, а остальные 9 заполнены нулями.

В том случае когда, длина данных превышает 10 блоков (10 240 байт), первые 10 элементов списка ссылаются на блоки файла, а 11-й - на блок, где размещается список следующих 256 номеров блоков. Этот блок называют косвенным. Это удобно для файлов, чей размер не превышает 10 + 256 (272 384 байта).

Если файл не умещается даже в 266 блоков, 12-й блок содержит адрес блока, включающего адреса 256 номеров блоков, каждый из которых, в свою очередь, содержит 256 номеров блоков, которые используются для нахождения содержания файла.

Тринадцатый блок используется подобным же способом, только уже на следующем уровне. Таким образом, в12-м блоке содержится адрес двойного косвенного блока, а в 13-м блоке - адрес тройного косвенного блока.

Максимальный размер одного файла может занимать 16 842 762 блока (17 246 988 Кбайт), но обычно файловая система налагает ограничения на размер файлов, чтобы случайно не создали файл, который займет все блоки на диске.

Так как каталог, представляет собою файл, содержащий таблицу с информацией, файловая система переводит имена файлов в индексные дескрипторы, достаточно просто. Для каждого файла в каталоге существует строка в таблице, которая содержит имя файла и номер индексного дескриптора, который ассоциируется с файлом. Получив, например, команду catproba.txt (система должна распечатать содержимое файла на дисплее), файловая система начинает прежде всего искать в таблице текущего каталога строку с именем proba.txt, находит номер i-узла (индексного дескриптора), связанного с этим файлом, и после этого начинает извлекать последовательно 165, 172 и 183 блоки, которые содержат информацию, записанную в файл proba.txt (рис. 3).

Рис. 3. Прослеживание дocтупа к блокам файла (165, 172, 183) пo имени proba.txt в текущем каталоге

После открытия файла соответствующий индексный дескриптор считывается в оперативную память и, таким образом, системе становятся доступны все номера блоков данного файла (кэширование диска и хранение в памяти копий индексных дескрипторов активных файлов существенно повышают эффективность файловой системы. Внезапное отключение питания крайне нежелательно для файловых систем типа LINUX, если система работает без UPS (бесперебойного источника питания). Это может привести к потере блоков, некорректным индексным дескрипторам, каталогам и т. д. Чтобы смягчить последствия таких потерь связи системы с диском, система выполняет регулярное копирование резидентных структур данных на диск. Все монтированные файловые системы периодическим образом обновляются. Кроме того, некоторые файловые системы ведут специальный журнал и обладают способностью к самовосстановлению. Архитектура LINUX представляет собой воплощение идей, кристаллизованных в течение исторического промежутка времени, когда были выработаны все основные идеи и концепции, воплощенные в стандартах, которым следуют все основные группировки разработчиков ОС.

В ExtX файлы могут содержать разреженные блоки. Разреженный блок создается в ситуации, когда исходный блок либо не определен, либо заполнен одними нулями. Неопределенные блоки появляются в том случае, если программа при создании файла потребовала, чтобы файл имел определенный размер, но не стала записывать данные в некоторые из его частей. Вместо того чтобы заполнять блок нулями, операционная система (ОС) помещает в указатель значение 0. Средства анализа и ОС должны обрабатывать разреженные блоки так, как если бы они были заполнены нулями.

Имя файла в inode не хранится. Его надо искать внутри каталогов, представляющих собой массив записей, формат которого представлен в листинге рис. 4.

Рис. 4. Формат представления массива каталогов (листинг)

При удалении файла операционная система находит соответствующую запись в каталоге, обнуляет поле inode и увеличивает размер предшествующей записи (поле rec_len – см. рис. 4) на величину удаляемой записи. Таким образом, предшествующая запись "поглощает" удаленную. Хотя имя файла в течение некоторого времени остается нетронутым, ссылка на соответствующий ему индексный дескриптор (inode) оказывается уничтоженной. Это создает проблему, так как теперь придется разбираться, какому файлу принадлежит обнаруженное имя.

В самом индексном дескрипторе при удалении файла тоже происходят большие изменения. Количество ссылок (i_links_count – см. рис. 2) обнуляется и обновляется поле последнего удаления (i_dtime). Все блоки, принадлежащие файлу, в карте свободного пространства (blockbitmap) помечаются как неиспользуемые, после чего данный inode также освобождается (обновляется inodebitmap).

В extX, к сожалению, полное восстановление файлов обычно невозможно, даже если эти файлы были только что удалены (в этом отношении данная файловая система проигрывает как FAT, так и NTFS - как минимум, теряется имя файла). Теряется связь имен файлов с их содержимым (при удалении небольшого количества хорошо известных файлов эта проблема остается решаемой, но ситуация серьезно осложняется, если вы удалили несколько служебных подкаталогов, в которые никогда ранее не заглядывали). Но достаточно часто индексные дескрипторы назначаются в том же порядке, в котором создаются записи в таблице каталогов. Благодаря наличию расширений имен файлов (.с, .gz, .mpg, и т. д.) количество возможных комбинаций соответствий обычно оказывается сравнительно небольшим. Тем не менее, восстановить, например, удаленный корневой каталог в автоматическом режиме никому не удастся (зато NTFS с этим справляется без проблем).

При удалении файла в Linux количество ссылок на него в индексном узле уменьшается на 1. Если счетчик ссылок уменьшается до нуля, индексная запись освобождается. Если файл все еще открыт каким-либо процессом, он причисляется к зависшим файлам и помещается в список, хранящийся в суперблоке. После закрытия файла процессом или перезагрузки системы индексный узел освобождается (в ext2 и ext3 используются разные реализации удаления файлов: ext3 обнуляет размер файла и стирает указатели на блоки в индексном узле и косвенных блоках, c другой стороны, ext2 не стирает эти данные, что упрощает восстановление).