Как работает алгоритм поиска данных в файловой системе FAT

Автор: Michael Miroshnichenko
Редактор: Andrey Mareev
Обновлено: 9.12.2024 16:18

В этой статье мы разберемся, как работает алгоритм поиска данных в файловой системе FAT и какие возможности он предоставляет для восстановления утерянных файлов. Если вы интересуетесь техническими аспектами файловых систем и хотите узнать больше о том, как работает алгоритм поиска данных в FAT, эта статья для вас! Мы предоставим подробное объяснение и практические примеры работы этого алгоритма.

Содержание

Файловая система FAT

FAT используется в большинстве портативных аудиоплееров и навигаторов. Даже мобильные телефоны и планшеты под управлением Android используют карты памяти (к примеру, miniSD, microSD), отформатированные в FAT32.

Да, FAT обладает рядом ограничений, как на максимальный объём раздела, так и на максимальный размер файла (в частности, фильмы в HD качестве бывает невозможно разместить одним файлом на разделе, отформатированном в FAT). Да, эта файловая система достаточно примитивна и не обладает встроенными средствами контроля целостности информации, встроенным сжатием и шифрованием, а также разделением прав доступа. Зато у FAT есть свои преимущества: компактность (под нужды файловой системы отводится совсем немного места), простота реализации и низкая ресурсоёмкость. Все эти достоинства и обусловили популярность файловой системы FAT среди разработчиков мобильных устройств.

Характеристика	Описание
Аббревиатура	FAT (File Allocation Table) — таблица размещения файлов.
Разработчик	Microsoft.
Основная структура	Boot-сектор: содержит информацию о файловой системе и загрузочный код. FAT-таблица: управляет размещением данных на диске. Root Directory: корневая директория, содержит записи о файлах и папках. Data Area: область хранения файловых данных.
Основные версии	FAT12: для устройств с малым объёмом памяти (диски до 16 МБ). FAT16: поддерживает диски до 2 ГБ. FAT32: поддерживает диски до 2 ТБ.
Преимущества	Простота реализации. Совместимость с большинством операционных систем. Поддержка сменных носителей (USB, SD-карты).
Недостатки	Ограничение на размер файла (до 4 ГБ для FAT32). Ограниченная надёжность и защита данных. Проблемы с производительностью на больших носителях.
Целевая область применения	Сменные носители, устройства с ограниченным объёмом памяти.

Перейти к просмотру

Восстановление данных с USB флешки после случайного удаления, форматирования или вирусной атаки 📁🔥⚕️

Перейти к просмотру

Восстановление файлов карты памяти фотоаппарата, телефона, планшета, видеокамеры, регистратора 📁🔥⚕️

Файловая система FAT: а что внутри?

Раз файловая система FAT настолько популярна, то востребованы и инструменты для восстановления данных с дисков, отформатированных с использованием этой файловой системы. В этой статье мы расскажем о внутреннем устройстве файловой системы в контексте алгоритмов, использованных в программах для восстановления FAT раздела.

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

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

К сожалению, такой простой подход возможен не всегда. Если файл был удалён какое-то время назад, или если записи в файловой системе были стёрты или перезаписаны, программе придётся сканировать всю поверхность диска с помощью алгоритмов сигнатурного поиска. Эти алгоритмы работают по принципу антивируса, идентифицируя файлы по известным сигнатурам. У такого подхода есть ряд ограничений: низкая скорость работы, ограниченное количество поддерживаемых форматов и невозможность полноценного восстановления фрагментированных файлов. Тем не менее, на практике эти алгоритмы прекрасно работают, ведь наиболее ценные файлы (документы, фотографии и т.п.) часто бывают небольшого размера и практически не фрагментируются.

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

Перейти к просмотру

Флешка не работает с автомагнитолой, телевизором, TV приставкой, камерой, видеорегистратором 🛠️👨‍💻🤔

Данные файловой системы

Итак, предположим, что нам нужно восстановить достаточно большой файл, который записан на диске в виде множества фрагментов. С помощью сигнатурного поиска мы сможем найти начало файла, проанализировать заголовок и определить его длину. Но если мы попытаемся сохранить данные, записанные на диске последовательно после заголовка нужного файла, то успешно восстановится только его начало – самый первый сектор. Остальные секторы могут принадлежать другим файлам. Соответственно, наша задача – использовать данные из файловой системы для того, чтобы точно определить: в какой последовательности и в какие именно секторы на диске записаны данные этого файла.

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

В поисках файловой системы

Рис.1 Жесткий диск разбит на разделы.

Для того чтобы использовать данные из файловой системы, саму файловую систему требуется найти. Прежде, чем говорить о файловой системе, нужно кратко описать систему разделов Windows.

Диски в Windows описываются системой разделов, которая содержит одну или несколько таблиц. Каждая таблица описывает один раздел. В записи указывается физический адрес начального сектора раздела и его конечный сектор (или длина). Помимо этого указывается также и тип раздела.

Для того чтобы найти файловую систему, программа проанализирует таблицу разделов Windows, если таковая сохранилась. Но что, если таблицы разделов не существует или в ней содержится неактуальная информация (например, нужный нам раздел был удалён, а на его месте был создан другой раздел)? В этом случае программа прибегнет к сканированию диска с целью поиска файловой системы.

Раздел	Начало	Конец	Тип
System (С:)	0	199	NTFS
Archive (D:)	200	399	FAT
Work (E:)	400	599	FAT

Таб.1 Таблица с информацией о начале, конце и типе каждого раздела.

Для поиска файловой системы будем исходить из предположения, что в каждом разделе диска находилась файловая система. Как правило, файловые системы можно идентифицировать по некоторой постоянной сигнатуре. Например, файловую систему FAT можно идентифицировать по значениям, записанным в байты 510 и 511 первого сектора. Если значения по этим адресам – 0x55 и 0хАА соответственно, то можно приступить к дополнительной проверке.

Дополнительные проверки позволяют отличить случайно встреченную последовательность данных от истинной сигнатуры файловой системы. Проверяется, например, диапазон значений, допустимых для некоторых полей структуры данных. Одно из полей файловой системы FAT определяет количество секторов в кластере. Его значение всегда представляет собой степень двойки из последовательности: 1, 2, 4, 8, 16, 32, 64 или 128. Если по данному адресу содержится любое другое значение, то найденная нами структура не принадлежит файловой системе FAT.

В статье «Алгоритм восстановления файла на диске FAT» мы рассмотрим поиск содержимого удаленного файла на конкретном примере.