Структура хранения информации о составе каталога в файловой системе NTFS

Общая постановка проблемы

Для специалистов, занятых разработкой утилит для операционных систем, и, в частности файловых систем, важно понимать структуру хранения информации на логическом диске. Использование знаний о структуре существующих файловых систем также позволяет создавать новые файловые системы, используя преимущества имеющихся. Одной из самых используемых файловых систем операционных систем семейства Windows NT на сегодняшний день, является файловая система NTFS. Однако ее структуру нельзя назвать простой. В частности, способ хранения информации о составе директории в виде В-дерева, состоящего из индексных записей, не является очевидным. Поэтому актуальной является задача разработки программного приложения, позволяющего в удобном для пользователя виде отобразить структуру каталога NTFS-раздела.

Обзор утилит для анализа внутренней структуры NTFS-раздела

Из существующих решений одним из самых популярных является приложение DiskEditor (рис.1), которое обеспечивает чтение, запись, редактирование содержимого как физического, так и логического раздела. Информация выводится шестнадцатеричными кодами, а также разбита на полям в соответствии с выбранным шаблоном. Системные программисты могут использовать данную программу для понимания структуры данных и проверки правильности их реализации. Однако DiskEditor не может предоставить программисту полной структуры индексных записей каталога NTFS-раздела, т.е. не содержит шаблона для отображения информации в виде отдельных полей. Анализ структуры индексных записей с помощью этой утилиты приходится выполнять по шестнадцатеричным кодам.

Так же существует программа DiskExplorer for NTFS, благодаря которой системный программист может увидеть содержимое индексных узлов каталога и получить ссылку на их записи в MFT-таблице (рис.2).

Однако приложение DiskExplorer также не отображает структуру В-дерева. Поэтому целью работы является разработка программного обеспечения для просмотра и анализа NTFS раздела, отображения структуры индексных записей в виде B-деревьев.

Структура хранения информации о составе каталога в NTFS

Все данные в NTFS – это файлы и информация о них храниться в MFT-таблице (аббревиатура с англ. Master File Table). Каждый файл или каталог в файловой системе представлен как запись в MFT-таблице. Размер записи составляет 1 Кбайт. Первые 42 байта содержат в себе заголовок записи MFT. Остальные байты записи хранят в себе атрибуты файла. Атрибут записи – это небольшая структура данных, которая служит для хранения к примеру имени, или содержимого файла (рис.3) [1].

Один из флагов в заголовке записи MFT показывает, что запись описывает каталог. Содержимое каталога сгруппировано в виде В-дерева.

B-дерево - сильноветвящееся сбалансированное дерево поиска, позволяющее проводить поиск, добавление и удаление элементов. B-дерево может применяться для структурирования информации (как правило, метаданных). Время доступа к произвольному блоку очень велико. Поэтому важно уменьшить количество узлов, просматриваемых при каждой операции. Использование поиска по списку каждый раз для нахождения случайного блока могло бы привести к чрезмерному количеству обращений к диску вследствие необходимости последовательного прохода по всем его элементам, предшествующим заданному, тогда как поиск в B-дереве, благодаря свойствам сбалансированности и высокой ветвистости, позволяет значительно сократить количество таких операций [2]. Принцип хранения информации о составе каталога в виде В-дерева следующий: узел дерева хранит имена файлов (атрибут $FILE_NAME) отсортированными. Узел может иметь дочерние узлы, количество которых всегда на единицу больше, чем количество файлов в узле (рис.4) [3]. Самый левый дочерний узел содержит в себе имена, которые в отсортированном списке предшествуют первому имени файла узла. Следующий дочерний узел содержит имена файлов, находящихся в диапазоне между первым и вторым элементом родительского узла в отсортированном списке имен файлов каталога и т.д.

Для реализации В-дерева в NTFS используется понятие индекса, которое пришло из баз данных. Индекс - это коллекция элементов, хранящихся в отсортированном порядке. В качестве индексного элемента может выступать любой атрибут, по которому будет производиться индексация. Для индексов каталогов это всегда атрибут $FILE_NAME, для каждого файла или каталога, содержащегося в нем. На каждый файл или каталог приходится как минимум две структуры FILE_NAME, первый как атрибут у файла, а второй, используемый для индекса. Узел дерева хранит последовательность атрибутов $FILE_NAME [4].

Для хранения узлов дерева используются два типа атрибутов $INDEX_ROOT, который присутствует всегда для любой директории и $INDEX_ALLOCATION, который может и не присутствовать для небольших каталогов.

Атрибут $INDEX_ROOT представляет собой корневой узел индексного дерева. Индексное дерево состоит из индексных элементов, которые являются файлами или каталогами. Атрибут INDEX_ALLOCATION не ограничен по количеству узлов и поэтому он будет содержать индексные элементы, которые не поместились в INDEX_ROOT.

Разработка приложения анализа структуры директории

Разработано приложение для анализа информации каталогов NTFS раздела на языке программирования С#. Для чтения информации с логического диска использовались функции Windows API (CreateFile, ReadFile, SetFilePointer). Алгоритм приложения включает в себя следующие этапы:

1. Чтение первого сектора логического диска для определения расположения MFT-таблицы и других параметров раздела;
2. Организация цикла чтения записей MFT. Для каждой записи производится анализ ее заголовка и атрибутов.
3. Определение записи, принадлежащей каталогу и считывание его атрибута $INDEX_ROOT. Перебор всех элементов индексного узла. Для перехода от одного элемента к другому следует к адресу индексного элемента добавлять смещение следующего элемента относительно текущего.
4. Определение наличия дочерних узлов В-дерева и считывание атрибута $INDEX_ALLOCATION. Атрибут представляет собой последовательность индексных записей, количество которых может быть вычислено делением размера атрибута на размер индексной записи. Зная количество индексных записей, их можно обойти как линейный массив элементов. Каждая индексная запись состоит из индексных узлов, которые просматриваются аналогично индексным узлам атрибута $INDEX_ROOT.

В ходе разработки были использованы основные особенности ООП, такие как классы, методы, интерфейсы, инкапсуляция, полиморфизм и наследование. Функциональные возможности разработанного приложения включают в себя чтение MFT-таблицы, перемещаться по записям MFT-таблицы, а так демонстрацию пользователю структуры индексных записей каталога в виде списка.