FAT датируется аж 1977-годом и пришла к нам из проприетарного DOS. Благодаря простой реализации, сейчас это способ хранения данных на таких носителях как USB-брелки, карты-памяти телефонов и ЦФК, в EFI для хранения кода загрузчика, в системах реального времени RTOS, и многое другое. В данной статье рассматриваются гендерные признаки зоопарка FAT, и в какую сущность превратила эволюция конкретно взятую FAT32. Детальный её разбор позволит понять алгоритм восстановления удалённых файлов, а так-же подтолкнёт на создание своих утилит форматирования, с широким спектром логической геометрии. Из инструментов понадобится любой (способный работать с дисками) HEX-редактор типа WinHex или HxD, штатный калькулятор Win, и
Оглавление:
1. Вводная часть
В основе проектирования операционных систем лежит работа с информацией. Здесь перед инженерами встают три задачи: во-первых определиться с типом накопителей (HDD, SSD, Flash), чтобы предоставить системе соответствующий драйвер. Второй момент – это способ хранения данных в виде файловых систем Ext, HPFS, FAT, NTFS и прочие. Но что ещё немаловажно, это предусмотреть возможность восстановления инфы в случае критических сбоев. Последний вопрос стоит ребром, что побудило Microsoft создать до блеска отшлифованную NTFS (New-Technology-File-System). Её мы не будем пока трогать, и отправив на скамейку запасных, рассмотрим только FAT.
1.1. Иерархия: диск[сектор] + том[кластер]
Для начала разберём геометрию накопителей.
• На нижнем уровне, производитель делит всю поверхность на 512-байтные сектора (отсчёт с единицы). Но утилиты и ОС могут предоставлять нам секторы > 512-байт, однако они по-любому будут кратны 512, например 1024-байт. Сектор – мин.порция обмена с диском, мы не сможем прочитать с него кол-во байт не кратное 512. Это нужно учитывать при вызове функций Read/WriteFile().
Самый первый сектор всегда отводится под MBR (MasterBootRecord), где указывается объём накопителя, и смещение к его логическому тому. Вместо устаревшей трехмерной CHS с лимитом в 8 ГБ, в современном мире используется уже линейный подход LBA48 (48-bit Logical Block Address), в которой секторы нумеруются с нуля, а не как прежде с единицы. LBA позволяет адресовать диск размером 128 ПетаБайт, при размере блока 512.
• ОС не может хранить файлы на дисках без логических разделов (том, volume, макс=26 с литерами от А: до Z
. Значит нужно создать этот том, и установить на него какую-нибудь файловую систему (далее FS), чтобы ОС знала о порядке расположения файлов – эта операция известна как форматирование. Бинарные файлы можно сбрасывать и на "сырой" RAW-том, только за доступ к ним будем отвечать уже сами. Такой изврат применяется редко, например при работе с дисками без поддержки их со-стороны ОС (см.прерывание BIOS int-13h).
• Допустим, имеем первый раздел C:\. Его смещение от начала диска указывается в секторе(1) MBR. У всех накопителей, первый раздел начинается как-минимум с сектора(63). Если учесть, что непосредственно данные и код MBR занимают всего 1-сектор, следовательно перед началом тома в загашнике остаётся аж 62 свободных, а это: 62*512=31 КБ пространства, где можно скрыть от FS конфиденциальную инфу. Важно понять, что FS устанавливается не на диск, а на его логический том, поэтому драйвер считает началом тома LBA(0), хотя в глазах биоса это сектор(63).
Такой расклад создаёт путаницу, но достаточно запомнить, что функцией CreateFile() можно открыть как физ.диск (тогда LBA(0) указывает на его начало), а можно запросить и логический том диска, например по букве C:\. В этом случае LBA(0) считается уже указателем на начало раздела. То-есть всё зависит от того, какой объект мы открываем.
• Каждая запись в таблице FAT указывает на определённый блок-информации в области данных. Если указателями адресовать мелкие секторы диска, то во-первых нужно будет увеличить разрядность этих указателей до 64-бит (т.к. диски могут быть исполинских размеров), а во-вторых потребуется огромное кол-во самих линков, что повлияет на размер таблицы. Файлы до 512-байт встречаются редко, а значит нет смысла искать их в каждом секторе. По этой причине, несколько секторов всегда собираются в "кластер", что позволяет увеличить полезное пространство, за счёт уменьшения таблицы FAT.
C дефолтными настройками, все FS создают кластеры размером 4096-байт, а это 8-секторов. В служебной таблице FAT лежат теперь указатели не на секторы, а на кластеры, и соответственно размер её сокращается в 8-раз! Но помимо плюсов есть и минусы.. Если в txt-файле у нас 11-байтная строка "Hello World", на диске этот файл будет занимать 4 КБ, т.к. мин.блоком хранения данных уже получается кластер. Зайдите в свойства любого файла и посмотрите, какой он имеет реальный размер, и сколько ему выделено на диске:
Как видим – картина удручающая, и при кластерном распределении у нас улетает в трубу огромная часть пространства. Но говорят, "случaйнaя удaчa принocит бoльшe рaдocти, чeм зaкoнoмeрный уcпex", и видимо инженеры с этим согласны. Здесь они вынуждены сесть на шпагат и только надеяться, что большинство файлов юзера будут размером больше 4КБ. Исключительно в этом случае экономия на размере таблицы оправдает себя.
Чтобы предотвратить суицид крайне впечатлительных юзверей, инженеры построили себе хату-с-краю, и предложили нам самостоятельно выбирать кол-во секторов в кластере – данный параметр имеется у большинства приличных утилит форматирования и называется "SectorPerCluster". Если у вас много мелких файлов и вы считаете 4КБ для хранения каждого из них слишком расточительным, то всегда можете изменить размер кластера в диапазоне от 512-байт, до 64КБ. Вот скрин одной из таких утилит "Fat32format":
1.2. Организация FAT – вид сверху
На рис.ниже представлены основные отличия FAT12/16, от более совершенной FAT32.
Здесь видно, что раньше, в системной области четыре служебные структуры располагались плотно друг-к-другу: это блок параметров BPB с адресом LBA(0) (не путать с MBR), далее основная таблица FAT, следом её резервная копия FAT2, и в хвосте корневой каталог. Размер таблицы зависит от общего кол-ва секторов в накопителе. Очевидно, что чем больше размер диска, тем больше в нём кластеров, и соответственно больше указателей на кластеры в таблице FAT.
Теперь посмотрим на организацию FAT32 справа..
Корневой каталог уже съехал с насиженных мест и может находится где угодно. Драйвер FS считает его обычным файлом с доступом на запись, что даёт возможность каталогу RootDir расширяться динамически. Кроме того, блок BPB разбух с одного до трёх секторов, хотя в FSInfo нет ничего интересного, а последний отправлен в резерв для наших потомков. Причём имеется и зеркало ВРВ, всегда по адресу LBA(6). В доке на FAT32 эту область назвали "Резервные сектора", сразу после которых расположилась уже таблица FAT со-своей копией. Благодаря такой организации, драйвер FS может восстанавливать теперь не только таблицу FAT, но и загрузочный сектор ОС в блоке параметров BPB.
2. Загрузочная запись и блок BPB – Bios Parametr Block
В самом начале тома с адресом LBA(0), во всех версиях FAT лежит блок параметров биос ВРВ. Он занимает ровно один 512-байтный сектор и содержит в себе базовые параметры файловой системы, а так-же код загрузчика ОС с сигнатурой 0x55AA. Запустим HEX-редактор и через меню "Инструменты" откроем в нём свою флэш – вот как это выглядит у меня:
Загрузчик нас не интересует, ..более того, если Flash не загрузочная, Boot-block вообще забит нулями, и это часто практикуется (например на microSD телефонов). Зато ВРВ критически важен для драйвера, посколько именно в нём зарыта инфа о расположении оставшихся трёх/системных структур – это парочка FAT, и корневой каталог RootDir. Для программного доступа к этому блоку я создал инклуд, и поместил в него структуру ВРВ с описанием каждого поля. Здесь-же перечислю только те поля, которые откроют нам доступ к FAT и корневому каталогу:
В спеке на FAT32 от Microsoft говорится, что положение корневого каталога "RootDir" строго не регламентируется, и он может лежать в произвольном кластере области данных. Однако на практике, Root в моих тестах всегда расположен сразу после двух таблиц FAT, т.е. адрес его фиксирован. Не знаю, может и есть в природе отбившиеся от стада утилиты форматирования, но лично мне таковые ещё не встречались.
В любом случае, найти каталог можно по приведённой выше формуле, и если это штатный форматер Win (как и большинство других), то вторая часть формулы
3. Таблица FAT – File Allocation Table
Теперь выйдем из матрицы, и поговорим о более насущном..
Организация любой файловой системы – невероятно сложный механизм. Однако в случае с FAT, это утверждение сильно притянуто за-уши. Именно благодаря свой простоте она дожила до наших дней и не собирается уходить со-сцены, а наоборот мутировала в 64-битную ExFAT.
Значит чтобы получить указатель на таблицу, нужно прочитать поле "RsvdSectorCount" структуры ВРВ. В данном случае там прописан сектор(1000), и если умножить его на 512, получим смещение в байтах от начала тома = 0x0007D000. Далее, читаем из той-же ВРВ поле "FATSz32" с размером, и передаём оба полученных значения функции ReadFile(). Так, в приёмном буфере функции получим дамп таблицы FAT, для её детального разбора.
Таблица – это массив указателей на кластеры, без каких-либо служебных полей. Отсчёт кластеров в массиве начинается с нуля, а разрядность указателей 32-бит (отсюда и название FAT). Старшие 4-бита отправлены в резерв, остаётся 28. Тогда получается, что FAT32 может адресовать всего:
На рисунке ниже представлен фрагмент таблицы FAT (для удобства, в меню "Вид" сгруппируйте отображение по 4-байта).
• Два/первых элемента массива всегда равны
• 32-битные элементы начиная со-смещения(8), отображают уже состояние соответствующих кластеров в области-данных диска. Он может быть свободным(0), выделенным(2), зарезервированным(F6) или повреждённым(F7). Элемент с макс.значением
• Древовидная структура расположения файлов на диске, начинается с корневого каталога – мы не видим его среди привычных нам папок, но он присутствует всегда. Ему назначается имя в виде "метки тома", которую запрашивает у нас система, при форматировании раздела. Именно поэтому второй элемент таблицы по смещению(8) имеет маркер окончания
Чтобы продемонстрировать организацию таблицы FAT, я форматнул свою флэш и сбросил на неё всего два файла. Первый размером 7.4КБ, поэтому занимает на диске два 4К-байтных кластера (выделен зелёным), а второй размером 20.2КБ и как видим, загребает 5 (выделенных синим) кластеров. Далее следуют null-элементы, которые информируют о свободном пространстве.
Обратите внимание, что после кластера(2), следующий элемент таблицы указывает сразу на кластер
Дело в том, что в таблице FAT хранятся указатели на следующие кластеры файла, а первый – прописывается в корневом каталоге RootDir, где лежит полный паспорт файла. То-есть когда файл меньше 4096-байт, выделенный под него первый кластер указывается в корневом каталоге, а в таблице получим лишь связанный с ним EOC. Но если файл выходит за границы одного кластера, то следующие указываются уже в таблице FAT, пока не встретится маркер окончания.
4. Корневой каталог "RootDirectory"
Файловая система требует базы, где хранилась-бы информация о всех, существующих на диске, файлах. Для FAT32(16) такой базой является "корневой каталог". Чтобы описать свойства одного файла, инженерам потребовался блок размером в 32-байта, где можно найти: имя файла/каталога в формате 8.3, его размер, дату создания, атрибуты, а так-же номер первого кластера, с которого начинается данный файл. Если-же хвост файла торчит снаружи выделенного кластера, номер следующего указывается уже в таблице FAT. Иначе, в таблице будет прописан только маркер окончания EOC. Таким образом, таблица и корневой-каталог логически связаны между собой, и потеря любого из них приведёт к краху всей FS.
В доках, 32-байтную запись каталога назвали SFN, что подразумевает "Short File Name". Короткая (short) она потому, что хранит имя в досовском формате(8.3). Но в современном мире мы уже отвыкли от всевозможных рамок, и предпочитаем для файлов более длинные имена, которые Win всё-же ограничивает до 256-символов. Поэтому в FAT предусмотрена родственная к SFN структура LFN (Long) – она имеет такой-же размер 32-байт, но является не самостоятельной, а дополнением к SFN. Если в имени файла меньше 8-ми символов, структура LFN может вообще отсутствовать, но SFN в наличии всегда.
Нужно признать, что организация длинных имён в FAT выполнена через известное место. Так, каждая структура LFN несёт в себе макс. 13-символов имени файла, а если их больше, то добавляется ещё одна структура и получаем 26-символов. Если-же и этого мало, то подключается сл.структура и т.д. Причём имя задаётся в Unicode (где на каждый символ расходуются по 2-байта) и внутри одной структуры разбросано по трём/разным полям. Более того, порядок следования цепочки структур обратный – т.е. сначала идёт последняя LFN(x), после неё LFN(x-1) и далее в том-же духе. Общее кол-во структур указывается в первом байте "Ordinal". Здесь становится очевидным, что разработчик явно был под веществами.
Выше упоминалось, что LBA каталога можно найти по формуле из ВРВ:
Для своей флэш я получил LBA=16384, и прыгнув на него в редакторе, попал в начало каталога.
Проясним некоторые моменты..
Из чёрной таблицы с расшифровкой полей видно, что номер первого кластера разделён на две части Hi/Low. Первый файл "dCrypt.asm" размером 7.4КБ и начинается с кластера(3). Но поскольку он требует два 4К-байтных, следующий указывается уже в таблице FAT (см.зелёный dword на предыдущем скрине). Здесь нужно отметить, что номера кластеров представляются относительно начала области-данных, которая совпадает с началом рассматриваемого корневого-каталога RootDir.
Так как-же найти злополучный файл на диске?
Для этого в спеке FAT32 приведена формула такого вида:
Если учесть, что в стандартной реализации FAT32 поле "RootCluster" в структуре ВРВ всегда равно 2, то для первого файла получаем следующий сектор LBA:
4.1. Алгоритм поиска удалённых файлов
Когда мы удаляем файл с диска FAT, он фактически остаётся на своём месте и так-же занимает свой кластер. Просто в соответствующей структуре SFN, первому байту присваивается маркер(Е5). Аналогичную ситуацию наблюдаем и в случае "Быстрого форматирования" тома. Такой расклад способствует восстановлению удалённых файлов. Чтобы создать их список, достаточно в корневом-каталоге с шагом в 32, проверять каждый/первый байт на маркер(Е5).
В качестве доказательства, я удалил со-своей флэш "usbVIDbase.txt", а второй файл оставил. В результате, SFN удалённого файла (и две предшествующие ей LFN) приобрели вид как на скрине ниже, а причастные к файлу элементы таблицы FAT сбросились в нуль. т.е. кластеры освободились для последующей записи. Таким образом, информация в кластерах удалённых файлов будет доступна нам до тех пор, пока драйвер FS не перезапишет их новыми данными.
5. Практика – разбор служебных структур
Теперь попробуем автоматизировать весь изложенный процесс..
Код ниже покажет основную информацию об USB-Flash или карте-памяти, если они имею формат FAT32.
Здесь есть нюанс, на который советую обратить внимание..
Значит получаем букву диска, и проверяем его на съёмный носитель "Removable". Если ок, то открываем раздел диска через CreateFile(), и пытаемся прочитать с него сектор ВРВ. Суть в том, что читать рекомендуется в асинхронном режиме, поскольку том может быть занят кем-то другим, например антивирусом. Если функцией ReadFile() читать синхронно, то функция может вернуть ошибку, мол диск недоступен. Поэтому мы используем асинхронный режим, в котором запрос ставится в очередь, а нам после вызова необходимо выждать пару секунд при помощи Sleep(). Этот способ требует в параметрах ReadFile() указатель на структуру "OVERLAPPED" и никогда не даёт осечек.
Во-втором случае я решил поинтересоваться картой-памяти своего телефона и обнаружил, что размер кластера у неё 32КБ, поэтому и таблица FAT намного меньшего размера: была 7.692 секторов в длину, а стала 951. Более того, и сам том начинается не как обычно с физ.сектора(63), а съехал аж к сектору(8192), о чём говорит поле "Volume First LBA". В такой организации пространства есть смысл, т.к. нам заранее известны ориентировочные размеры файлов – это фотки, мультимедиа и прочие, т.е. больше стандартного кластера 4КБ:
6. Заключение
Если не брать во-внимание детали оформления служебных структур, основным недостатком FAT32 является полное отсутствие "инстинкта самосохранения" при критических сбоях. Хорошо хоть инженеры предусмотрели некую пародию, в виде резервных блоков ВРВ и таблицы FAT2. Зато в NTFS всё продумано до мелочей, и в этом большое её преимущество. Например метафайл NTFS под названием "$LogFile" представляет собой журнал последней удачной конфигурации. Если случается крах, то при следующей перезагрузке, все параметры считываются уже из этого журнала, который драйвер NTFS обновляет при обычном выключении компьютера. Однако выбор у пользователей должен быть всегда, и FAT как-раз нам его предоставляет.
В скрепке лежит инклуд, и ехе-файл для тестов. Увидимся теперь на пороге Нового года, пока!
Ссылка скрыта от гостей
от Microsoft.Оглавление:
1. Вводная часть;
2. Загрузочная запись и блок BPB – Bios Parametr Block;
3. Таблицы FAT – File Allocation Table;
4. Корневой каталог "RootDir";
5. Практика – разбор служебных структур;
6. Заключение.
1. Вводная часть
В основе проектирования операционных систем лежит работа с информацией. Здесь перед инженерами встают три задачи: во-первых определиться с типом накопителей (HDD, SSD, Flash), чтобы предоставить системе соответствующий драйвер. Второй момент – это способ хранения данных в виде файловых систем Ext, HPFS, FAT, NTFS и прочие. Но что ещё немаловажно, это предусмотреть возможность восстановления инфы в случае критических сбоев. Последний вопрос стоит ребром, что побудило Microsoft создать до блеска отшлифованную NTFS (New-Technology-File-System). Её мы не будем пока трогать, и отправив на скамейку запасных, рассмотрим только FAT.
1.1. Иерархия: диск[сектор] + том[кластер]
Для начала разберём геометрию накопителей.
• На нижнем уровне, производитель делит всю поверхность на 512-байтные сектора (отсчёт с единицы). Но утилиты и ОС могут предоставлять нам секторы > 512-байт, однако они по-любому будут кратны 512, например 1024-байт. Сектор – мин.порция обмена с диском, мы не сможем прочитать с него кол-во байт не кратное 512. Это нужно учитывать при вызове функций Read/WriteFile().
Самый первый сектор всегда отводится под MBR (MasterBootRecord), где указывается объём накопителя, и смещение к его логическому тому. Вместо устаревшей трехмерной CHS с лимитом в 8 ГБ, в современном мире используется уже линейный подход LBA48 (48-bit Logical Block Address), в которой секторы нумеруются с нуля, а не как прежде с единицы. LBA позволяет адресовать диск размером 128 ПетаБайт, при размере блока 512.
• ОС не может хранить файлы на дисках без логических разделов (том, volume, макс=26 с литерами от А: до Z
• Допустим, имеем первый раздел C:\. Его смещение от начала диска указывается в секторе(1) MBR. У всех накопителей, первый раздел начинается как-минимум с сектора(63). Если учесть, что непосредственно данные и код MBR занимают всего 1-сектор, следовательно перед началом тома в загашнике остаётся аж 62 свободных, а это: 62*512=31 КБ пространства, где можно скрыть от FS конфиденциальную инфу. Важно понять, что FS устанавливается не на диск, а на его логический том, поэтому драйвер считает началом тома LBA(0), хотя в глазах биоса это сектор(63).
Такой расклад создаёт путаницу, но достаточно запомнить, что функцией CreateFile() можно открыть как физ.диск (тогда LBA(0) указывает на его начало), а можно запросить и логический том диска, например по букве C:\. В этом случае LBA(0) считается уже указателем на начало раздела. То-есть всё зависит от того, какой объект мы открываем.
• Каждая запись в таблице FAT указывает на определённый блок-информации в области данных. Если указателями адресовать мелкие секторы диска, то во-первых нужно будет увеличить разрядность этих указателей до 64-бит (т.к. диски могут быть исполинских размеров), а во-вторых потребуется огромное кол-во самих линков, что повлияет на размер таблицы. Файлы до 512-байт встречаются редко, а значит нет смысла искать их в каждом секторе. По этой причине, несколько секторов всегда собираются в "кластер", что позволяет увеличить полезное пространство, за счёт уменьшения таблицы FAT.
C дефолтными настройками, все FS создают кластеры размером 4096-байт, а это 8-секторов. В служебной таблице FAT лежат теперь указатели не на секторы, а на кластеры, и соответственно размер её сокращается в 8-раз! Но помимо плюсов есть и минусы.. Если в txt-файле у нас 11-байтная строка "Hello World", на диске этот файл будет занимать 4 КБ, т.к. мин.блоком хранения данных уже получается кластер. Зайдите в свойства любого файла и посмотрите, какой он имеет реальный размер, и сколько ему выделено на диске:
Как видим – картина удручающая, и при кластерном распределении у нас улетает в трубу огромная часть пространства. Но говорят, "случaйнaя удaчa принocит бoльшe рaдocти, чeм зaкoнoмeрный уcпex", и видимо инженеры с этим согласны. Здесь они вынуждены сесть на шпагат и только надеяться, что большинство файлов юзера будут размером больше 4КБ. Исключительно в этом случае экономия на размере таблицы оправдает себя.
Чтобы предотвратить суицид крайне впечатлительных юзверей, инженеры построили себе хату-с-краю, и предложили нам самостоятельно выбирать кол-во секторов в кластере – данный параметр имеется у большинства приличных утилит форматирования и называется "SectorPerCluster". Если у вас много мелких файлов и вы считаете 4КБ для хранения каждого из них слишком расточительным, то всегда можете изменить размер кластера в диапазоне от 512-байт, до 64КБ. Вот скрин одной из таких утилит "Fat32format":
1.2. Организация FAT – вид сверху
На рис.ниже представлены основные отличия FAT12/16, от более совершенной FAT32.
Здесь видно, что раньше, в системной области четыре служебные структуры располагались плотно друг-к-другу: это блок параметров BPB с адресом LBA(0) (не путать с MBR), далее основная таблица FAT, следом её резервная копия FAT2, и в хвосте корневой каталог. Размер таблицы зависит от общего кол-ва секторов в накопителе. Очевидно, что чем больше размер диска, тем больше в нём кластеров, и соответственно больше указателей на кластеры в таблице FAT.
Теперь посмотрим на организацию FAT32 справа..
Корневой каталог уже съехал с насиженных мест и может находится где угодно. Драйвер FS считает его обычным файлом с доступом на запись, что даёт возможность каталогу RootDir расширяться динамически. Кроме того, блок BPB разбух с одного до трёх секторов, хотя в FSInfo нет ничего интересного, а последний отправлен в резерв для наших потомков. Причём имеется и зеркало ВРВ, всегда по адресу LBA(6). В доке на FAT32 эту область назвали "Резервные сектора", сразу после которых расположилась уже таблица FAT со-своей копией. Благодаря такой организации, драйвер FS может восстанавливать теперь не только таблицу FAT, но и загрузочный сектор ОС в блоке параметров BPB.
2. Загрузочная запись и блок BPB – Bios Parametr Block
В самом начале тома с адресом LBA(0), во всех версиях FAT лежит блок параметров биос ВРВ. Он занимает ровно один 512-байтный сектор и содержит в себе базовые параметры файловой системы, а так-же код загрузчика ОС с сигнатурой 0x55AA. Запустим HEX-редактор и через меню "Инструменты" откроем в нём свою флэш – вот как это выглядит у меня:
Загрузчик нас не интересует, ..более того, если Flash не загрузочная, Boot-block вообще забит нулями, и это часто практикуется (например на microSD телефонов). Зато ВРВ критически важен для драйвера, посколько именно в нём зарыта инфа о расположении оставшихся трёх/системных структур – это парочка FAT, и корневой каталог RootDir. Для программного доступа к этому блоку я создал инклуд, и поместил в него структуру ВРВ с описанием каждого поля. Здесь-же перечислю только те поля, которые откроют нам доступ к FAT и корневому каталогу:
C-подобный:
struct BPB ;//<------------- BIOS Parameter Block
JmpBoot rb 3 ;// JMP на загрузчик (0xEB5890)
OemName rb 8 ;// <----- строка форматера ОС
BytePerSector dw 0 ;// Байт в секторе
SecPerCluster db 0 ;// Секторов к кластере
RsvdSecCounter dw 0 ;// Резервная область в секторах
NumFats db 0 ;// Сколько копий FAT-таблицы
RootEntCnt dw 0 ;// Объектов в корневом каталоге (нуль для FAT-32)
TotSec16 dw 0 ;// Всего секторов на диске (нуль для FAT-32)
Media db 0 ;// Тип диска (F8)
FATSz16 dw 0 ;// Размер таблицы FAT-16 в секторах (нуль для FAT-32)
SecPerTrk dw 0 ;// Секторов в дорожке
NumHeads dw 0 ;// Всего головок Head
HiddSec dd 0 ;// Cекторов перед началом раздела
TotSec32 dd 0 ;// Всего секторов на диске
ends
struct BPB_32 ;//<------------ FAT-32
Header BPB ;// Заголовок (одинаковый для FAT16/32)
FATSz32 dd 0 ;// Размер таблицы FAT-32 в секторах
ExtFlags dw 0 ;// Флаги
FSVer dw 0 ;// Версия файловой системы
RootCluster dd 0 ;// Кластер корневого каталога
FSInfo dw 0 ;// Сектор структуры FSINFO
BkBootSec dw 0 ;// Сектор копии этой записи (6)
Reserved rb 12 ;//
DrvNum db 0 ;// Номер диска для INT-13h (00 или 80h)
Reserved1 db 0 ;//
BootSig db 0 ;// Сигнатура 29h, если имеются сл.три поля
VolID dd 0 ;// Серийник тома
VolLabel rb 11 ;//<----- Строка с меткой тома
FilSysType rb 08 ;//<----- Строка "FAT32 ".
Reserved2 rb 420 ;//
Signature dw 0 ;// 55AAh
ends
В спеке на FAT32 от Microsoft говорится, что положение корневого каталога "RootDir" строго не регламентируется, и он может лежать в произвольном кластере области данных. Однако на практике, Root в моих тестах всегда расположен сразу после двух таблиц FAT, т.е. адрес его фиксирован. Не знаю, может и есть в природе отбившиеся от стада утилиты форматирования, но лично мне таковые ещё не встречались.
В любом случае, найти каталог можно по приведённой выше формуле, и если это штатный форматер Win (как и большинство других), то вторая часть формулы
(RootCluster-2) * SectorPerCluster
будет всегда возвращать нуль. Тогда получается, что каталог лежит сразу после резервных секторов + размеры двух таблиц FAT (см.первый скрин FAT16). А вообще, жить без идеологии и надеяться на случай не есть гуд, а потому лучше использовать полную формулу, тем-более что мягкие уже грозно предупредили нас об этом.3. Таблица FAT – File Allocation Table
Теперь выйдем из матрицы, и поговорим о более насущном..
Организация любой файловой системы – невероятно сложный механизм. Однако в случае с FAT, это утверждение сильно притянуто за-уши. Именно благодаря свой простоте она дожила до наших дней и не собирается уходить со-сцены, а наоборот мутировала в 64-битную ExFAT.
Значит чтобы получить указатель на таблицу, нужно прочитать поле "RsvdSectorCount" структуры ВРВ. В данном случае там прописан сектор(1000), и если умножить его на 512, получим смещение в байтах от начала тома = 0x0007D000. Далее, читаем из той-же ВРВ поле "FATSz32" с размером, и передаём оба полученных значения функции ReadFile(). Так, в приёмном буфере функции получим дамп таблицы FAT, для её детального разбора.
Таблица – это массив указателей на кластеры, без каких-либо служебных полей. Отсчёт кластеров в массиве начинается с нуля, а разрядность указателей 32-бит (отсюда и название FAT). Старшие 4-бита отправлены в резерв, остаётся 28. Тогда получается, что FAT32 может адресовать всего:
2^28=268.435.456
кластеров, и если размер каждого из них 4096-байт, то макс.объём диска = 1ТБ. Однако это теоретический предел, ведь всегда можно увеличить размер кластера в 2,4,8 и даже в 16-раз, при этом оставив 28-битные линки. Так-что на практике становится доступным диск 16ТБ, а если требуется больше, нужно переходить на ExFAT, в которой разрядность указателей расширена до 64-бит.На рисунке ниже представлен фрагмент таблицы FAT (для удобства, в меню "Вид" сгруппируйте отображение по 4-байта).
• Два/первых элемента массива всегда равны
0x0FFFFFF8
+ 0xFFFFFFFF
, и не используются в качестве указателей на кластеры – это просто сигнатура таблицы, а байт(F8) определяет "MediaType" (варианты: F0=Floppy, F8=Hard, FA=Ram). Когда блок ВРВ и его резервная копия безвозвратно утеряны (бэд-сектор или вирь), по данной сигнатуре можно будет найти таблицу, чтобы попытаться спасти информацию.• 32-битные элементы начиная со-смещения(8), отображают уже состояние соответствующих кластеров в области-данных диска. Он может быть свободным(0), выделенным(2), зарезервированным(F6) или повреждённым(F7). Элемент с макс.значением
0x0FFFFFFF
является маркером последнего кластера файла EOC (EndOfCluster). Если файл большой и занимает несколько кластеров, указатели связываются в цепочку до тех пор, пока не встретится этот маркер (выделены красным).• Древовидная структура расположения файлов на диске, начинается с корневого каталога – мы не видим его среди привычных нам папок, но он присутствует всегда. Ему назначается имя в виде "метки тома", которую запрашивает у нас система, при форматировании раздела. Именно поэтому второй элемент таблицы по смещению(8) имеет маркер окончания
0x0FFFFFFF
, т.к. под корневой каталог отводится всего один кластер(2) (см.структуру ВРВ-->RootCluster).Чтобы продемонстрировать организацию таблицы FAT, я форматнул свою флэш и сбросил на неё всего два файла. Первый размером 7.4КБ, поэтому занимает на диске два 4К-байтных кластера (выделен зелёным), а второй размером 20.2КБ и как видим, загребает 5 (выделенных синим) кластеров. Далее следуют null-элементы, которые информируют о свободном пространстве.
Обратите внимание, что после кластера(2), следующий элемент таблицы указывает сразу на кластер
0х00000004
. Это-же касается и записи после маркера EOC по смещению(14h) – перепрыгнув через один, она линкует сразу на кластер(6). Здесь возникает вопрос: куда подевались кластеры 3 и 5, ведь значения 0х0FFFFFFF
это не указатели, а просто маркеры окончания цепочки?Дело в том, что в таблице FAT хранятся указатели на следующие кластеры файла, а первый – прописывается в корневом каталоге RootDir, где лежит полный паспорт файла. То-есть когда файл меньше 4096-байт, выделенный под него первый кластер указывается в корневом каталоге, а в таблице получим лишь связанный с ним EOC. Но если файл выходит за границы одного кластера, то следующие указываются уже в таблице FAT, пока не встретится маркер окончания.
4. Корневой каталог "RootDirectory"
Файловая система требует базы, где хранилась-бы информация о всех, существующих на диске, файлах. Для FAT32(16) такой базой является "корневой каталог". Чтобы описать свойства одного файла, инженерам потребовался блок размером в 32-байта, где можно найти: имя файла/каталога в формате 8.3, его размер, дату создания, атрибуты, а так-же номер первого кластера, с которого начинается данный файл. Если-же хвост файла торчит снаружи выделенного кластера, номер следующего указывается уже в таблице FAT. Иначе, в таблице будет прописан только маркер окончания EOC. Таким образом, таблица и корневой-каталог логически связаны между собой, и потеря любого из них приведёт к краху всей FS.
В доках, 32-байтную запись каталога назвали SFN, что подразумевает "Short File Name". Короткая (short) она потому, что хранит имя в досовском формате(8.3). Но в современном мире мы уже отвыкли от всевозможных рамок, и предпочитаем для файлов более длинные имена, которые Win всё-же ограничивает до 256-символов. Поэтому в FAT предусмотрена родственная к SFN структура LFN (Long) – она имеет такой-же размер 32-байт, но является не самостоятельной, а дополнением к SFN. Если в имени файла меньше 8-ми символов, структура LFN может вообще отсутствовать, но SFN в наличии всегда.
Нужно признать, что организация длинных имён в FAT выполнена через известное место. Так, каждая структура LFN несёт в себе макс. 13-символов имени файла, а если их больше, то добавляется ещё одна структура и получаем 26-символов. Если-же и этого мало, то подключается сл.структура и т.д. Причём имя задаётся в Unicode (где на каждый символ расходуются по 2-байта) и внутри одной структуры разбросано по трём/разным полям. Более того, порядок следования цепочки структур обратный – т.е. сначала идёт последняя LFN(x), после неё LFN(x-1) и далее в том-же духе. Общее кол-во структур указывается в первом байте "Ordinal". Здесь становится очевидным, что разработчик явно был под веществами.
C-подобный:
;//*********************************************************************
;// Время: Биты[4:0]= пары секунд (0-29), [10:5]= минуты, [15:11]= часы
;// Дата: Биты[4:0]= день, [8:5]= месяц, [15:9]= год начиная с 1980
;//*********************************************************************
struct SFN ;//<----------- 32-байта под описатель файла (DirEntry)
DIR_Name rb 11 ;// 00 = Имя 8.3
DIR_Attr db 0 ;// 0B = см.ATTR_xx
DIR_NTRes db 0 ;// 0C = Резерв
DIR_CrtTimeMs db 0 ;// 0D = Сотые времени создания файла
DIR_CrtTime dw 0 ;// 0E = Время создания файла в 2-сек.
DIR_CrtDate dw 0 ;// 10 = Дата создания
DIR_LstAccDate dw 0 ;// 12 = Дата посл.доступа
DIR_FstClusHi dw 0 ;// 14 = Первый кластер файла/каталога (High)
DIR_WrtTime dw 0 ;// 16 = Время записи
DIR_WrtDate dw 0 ;// 18 = Дата записи
DIR_FstClusLo dw 0 ;// 1A = Первый кластер файла/каталога (Low)
DIR_FileSize dd 0 ;// 1С = Размер файла
ends
struct LFN ;//<----------- 32-байта под длинное имя файла
LDIR_Ord db 1 ;// Маска 40h + кол-во структур LFN
LDIR_Name rb 10 ;// Символы 1-5 Unicode имени
LDIR_Attr db 0 ;// см.ATTR_xx
LDIR_Type db 0 ;// Резерв
LDIR_Chksum db 0 ;// CRC
LDIR_Name2 rb 12 ;// Символы 6-11
LDIR_FstClusLo dw 0 ;// Резерв
LDIR_Name3 rb 4 ;// Символы 12-13
ends
ATTR_READ_ONLY = 0x01
ATTR_HIDDEN = 0x02
ATTR_SYSTEM = 0x04
ATTR_VOLUME_ID = 0x08
ATTR_LONG_NAME = 0x0F
ATTR_DIRECTORY = 0x10
ATTR_ARCHIVE = 0x20
Выше упоминалось, что LBA каталога можно найти по формуле из ВРВ:
RsvdSecCount + (FATSz*2) + ((RootCluster-2) * SecPerCluster)
Для своей флэш я получил LBA=16384, и прыгнув на него в редакторе, попал в начало каталога.
Проясним некоторые моменты..
1. Первая структура SFN (синий блок) будет всегда описывать корневую папку диска. Это единственная структура, которой может быть присвоен атрибут "VolumeID" со-значением 08h. Атрибуты файлов/каталогов лежат по смещению(0Вh) от начала структур, и я заключил их в синий овал. Все остальные поля первой структуры SFN считаются не действительными!
2. На моей флэш всего два файла с именами "dCrypt.asm" и "usbVIDbase.txt". Чем руководствуется драйвер FAT при добавлении к SFN структуры LFN остаётся загадкой, поскольку имя первого файла меньше 8-ми символов, но дров всё-равно вставил LFN (см.красный блок). А вот имя второго файла уже 10-символов, и для него выделено две LFN в зелёном блоке. Обратите внимание, что у первой в поле-ординала лежит значение(1) (+40h маска), а у второй LFN ординал равен(2). Эти поля я выделил чёрным, и они определяют кол-во структур LFN для текущего файла. Записи LFN можно обнаружить по атрибуту(0F).
Из чёрной таблицы с расшифровкой полей видно, что номер первого кластера разделён на две части Hi/Low. Первый файл "dCrypt.asm" размером 7.4КБ и начинается с кластера(3). Но поскольку он требует два 4К-байтных, следующий указывается уже в таблице FAT (см.зелёный dword на предыдущем скрине). Здесь нужно отметить, что номера кластеров представляются относительно начала области-данных, которая совпадает с началом рассматриваемого корневого-каталога RootDir.
Так как-же найти злополучный файл на диске?
Для этого в спеке FAT32 приведена формула такого вида:
FileFirstCluster = RootDir + (SFN.FstClus - RootCluster)
Если учесть, что в стандартной реализации FAT32 поле "RootCluster" в структуре ВРВ всегда равно 2, то для первого файла получаем следующий сектор LBA:
Код:
RootDir = сектор 16384
SFN.FstClus = кластер(3)
Формула: 3-2 = кластер(1) = 8 секторов
-----------------------------------------
FileFirstClus = 16384 + 8 = сектор(16392)
4.1. Алгоритм поиска удалённых файлов
Когда мы удаляем файл с диска FAT, он фактически остаётся на своём месте и так-же занимает свой кластер. Просто в соответствующей структуре SFN, первому байту присваивается маркер(Е5). Аналогичную ситуацию наблюдаем и в случае "Быстрого форматирования" тома. Такой расклад способствует восстановлению удалённых файлов. Чтобы создать их список, достаточно в корневом-каталоге с шагом в 32, проверять каждый/первый байт на маркер(Е5).
В качестве доказательства, я удалил со-своей флэш "usbVIDbase.txt", а второй файл оставил. В результате, SFN удалённого файла (и две предшествующие ей LFN) приобрели вид как на скрине ниже, а причастные к файлу элементы таблицы FAT сбросились в нуль. т.е. кластеры освободились для последующей записи. Таким образом, информация в кластерах удалённых файлов будет доступна нам до тех пор, пока драйвер FS не перезапишет их новыми данными.
5. Практика – разбор служебных структур
Теперь попробуем автоматизировать весь изложенный процесс..
Код ниже покажет основную информацию об USB-Flash или карте-памяти, если они имею формат FAT32.
Здесь есть нюанс, на который советую обратить внимание..
Значит получаем букву диска, и проверяем его на съёмный носитель "Removable". Если ок, то открываем раздел диска через CreateFile(), и пытаемся прочитать с него сектор ВРВ. Суть в том, что читать рекомендуется в асинхронном режиме, поскольку том может быть занят кем-то другим, например антивирусом. Если функцией ReadFile() читать синхронно, то функция может вернуть ошибку, мол диск недоступен. Поэтому мы используем асинхронный режим, в котором запрос ставится в очередь, а нам после вызова необходимо выждать пару секунд при помощи Sleep(). Этот способ требует в параметрах ReadFile() указатель на структуру "OVERLAPPED" и никогда не даёт осечек.
C-подобный:
format pe console
include 'win32ax.inc'
include 'equates\fat.inc'
entry start
;//----------
.data
fatBuff rb 512*3
ntName db '\\?\GLOBALROOT'
dosName db 32 dup(0)
usbHndl dd 0
align 16
fpuRes0 dq 0
fpuRes1 dq 0
fpuRes2 dq 0
secSize dd 0
clsSize dd 0
kByte dd 1024
mByte dd 1024*1024
gByte dd 1024*1024*1024
ol OVERLAPPED
rootDir dd 0
dumpByte dd 16
dumpLen db 8
dumpStr db 16 dup('.'),0
buff db 0
;//----------
.code
start: invoke SetConsoleTitle,<'*** USB-Flash FAT info ***',0>
;//---- Проверим наличие клиента в портах USB
invoke GetLogicalDriveStringsA,64,buff
mov esi,buff
@@: push esi
invoke GetDriveType,esi ;// запрашиваем тип драйва..
pop esi
cmp eax,DRIVE_REMOVABLE ;// извлекаемое устройство?
je @ok
add esi,4
cmp byte[esi],0 ;// последнее в списке?
jne @b
cinvoke printf,<10,' ERROR! USB-Flash not found.',0>
jmp @exit
;//---- Получаем имя и открываем девайс на асинх.чтение
@ok: push esi
cinvoke printf,<10,' MS-DOS name...: %s',0>,esi
pop esi
mov byte[esi+2],0
invoke QueryDosDevice,esi,dosName,32
cinvoke printf,<10,' Object link...: %s',10,0>,ntName
invoke CreateFile,ntName,GENERIC_READ + GENERIC_WRITE,\
FILE_SHARE_READ + FILE_SHARE_WRITE,\
0,OPEN_EXISTING,\
FILE_FLAG_OVERLAPPED + FILE_ATTRIBUTE_NORMAL,0
mov [usbHndl],eax
;//---- Читаем структуру "Bios Parametr Block"
invoke ReadFile,[usbHndl],fatBuff,512,0,ol
invoke Sleep,1000
;//---- Проверим ф.систему на FAT32, иначе ошибка
mov esi,fatBuff
cmp word[esi+BPB.FATSz16],0
je @f
cinvoke printf,<10,' ERROR! This is FAT16.',0>
jmp @exit
;//---- Есть FAT32! - собираем инфу..
@@: mov eax,BPB_32.FilSysType
add eax,esi
movzx ebx,[esi+BPB_32.Header.BytePerSector]
movzx ecx,[esi+BPB_32.Header.SecPerCluster]
mov edx,ecx
imul ecx,ebx
mov [secSize],ebx
mov [clsSize],ecx
shr ecx,10
cinvoke printf,<10,' File system..........: %.8s',\
10,' Sector size.........: %d Byte',\
10,' Sector per Cluster...: %d',\
10,' Cluster size.........: %d KB',10,0>,\
eax,ebx,edx,ecx
;//------------------------
mov esi,fatBuff
mov eax,[esi+BPB_32.Header.HiddSec]
mov ebx,[esi+BPB_32.Header.TotSec32]
movzx ecx,[esi+BPB_32.Header.RsvdSecCounter]
mov edx,ecx
shl edx,9
shr edx,10
push 0 ebx
fild qword[esp]
fimul [secSize]
fidiv [gByte]
fstp [fpuRes0]
add esp,8
cinvoke printf,<10,' Volume first LBA.....: %u',\
10,' Volume total LBA.....: %u',\
10,' Volume capacity......: %.2f GB',\
10,' BPB reserved sectors.: %d (%d KB)',10,0>,\
eax,ebx,dword[fpuRes0],dword[fpuRes0+4],ecx,edx
;//------------------------
mov esi,fatBuff
movzx eax,[esi+BPB_32.Header.NumFats]
movzx ebx,[esi+BPB_32.BkBootSec]
movzx ecx,[esi+BPB_32.Header.RsvdSecCounter]
mov edx,[esi+BPB_32.FATSz32]
imul edx,[secSize]
shr edx,10
cinvoke printf,<10,' FATs count...........: %d',\
10,' BPB backup LBA.......: %d',\
10,' FAT first LBA.......: %d',\
10,' FAT size (sectors)...: %d (%d KB)',0>,\
eax,ebx,ecx,[esi+BPB_32.FATSz32],edx
;//------------------------
;// RootDir = (RsvdSecCount + (FATSz32 * NumFats)) + (RootCluster - 2) * SecPerCluster
mov esi,fatBuff
mov eax,[esi+BPB_32.FATSz32]
movzx ebx,[esi+BPB_32.Header.RsvdSecCounter]
shl eax,1
add eax,ebx ;// RsvdSecCount + (FATSz32 * NumFats)
mov ebx,[esi+BPB_32.RootCluster]
sub ebx,2
movzx ecx,[esi+BPB_32.Header.SecPerCluster]
imul ebx,ecx ;// (RootCluster - 2) * SecPerCluster
add eax,ebx
mov [rootDir],eax
cinvoke printf,<10,' Root Dir cluster.....: %d',\
10,' Root Dir LBA.........: %d',10,0>,\
[esi+BPB_32.RootCluster],eax
;//------------------------
mov esi,fatBuff
mov eax,BPB_32.Header.OemName
mov ebx,BPB_32.VolLabel
mov ecx,[esi+BPB_32.VolID]
movzx edx,cx
shr ecx,16
add eax,esi
add ebx,esi
cinvoke printf,<10,' Volume formater......: %.8s',\
10,' Volume label.........: %.11s',\
10,' Volume serial........: %04X-%04X',10,0>,eax,ebx,ecx,edx
;//---- Читаем таблицу FAT, и выводим фрагмент её дампа
xor al,al
mov ecx,sizeof.OVERLAPPED
mov edi,ol
rep stosb
mov esi,fatBuff
movzx eax,[esi+BPB_32.Header.RsvdSecCounter]
shl eax,9
mov [ol.Offset],eax
invoke ReadFile,[usbHndl],fatBuff,512,0,ol
invoke Sleep,1000
cinvoke printf,<10,' FAT dump....: ',0>
call PrintDump
;//---- Читаем корневой каталог, и так-же дампим фрагмент
xor al,al
mov ecx,sizeof.OVERLAPPED
mov edi,ol
rep stosb
mov eax,[rootDir]
shl eax,9
mov [ol.Offset],eax
invoke ReadFile,[usbHndl],fatBuff,512,0,ol
invoke Sleep,1000
cinvoke printf,<10,' RootDir dump: ',0>
call PrintDump
@exit: invoke CloseHandle,[usbHndl]
cinvoke _getch
cinvoke exit,0
;//------------------------------------------
;// Вспомогательная процедура - выводит дамп
;//------------------------------------------
PrintDump:
mov esi,fatBuff
@next: mov edi,dumpStr
xor ebx,ebx
@prn: xor eax,eax
lodsb
push ebx eax
cinvoke printf,<'%02X',0>,eax
pop eax
cmp al,20h
jb @f
mov byte[edi],al
@@: inc edi
pop ebx
inc ebx
cmp ebx,4
jb @f
cinvoke printf,<' ',0>
xor ebx,ebx
@@: dec [dumpByte]
jnz @prn
push esi
mov [dumpByte],16
invoke CharToOem,dumpStr,dumpStr
cinvoke printf,<' %.16s',0>,dumpStr
mov eax,'....'
mov edi,dumpStr
mov ecx,4
rep stosd
cinvoke printf,<10,15 dup(' '),0>
pop esi
dec [dumpLen]
jnz @next
mov [dumpLen],8
ret
;//----------
section '.idata' import data readable
library msvcrt,'msvcrt.dll',kernel32,'kernel32.dll',user32,'user32.dll'
include 'api\msvcrt.inc'
include 'api\kernel32.inc'
include 'api\user32.inc'
Во-втором случае я решил поинтересоваться картой-памяти своего телефона и обнаружил, что размер кластера у неё 32КБ, поэтому и таблица FAT намного меньшего размера: была 7.692 секторов в длину, а стала 951. Более того, и сам том начинается не как обычно с физ.сектора(63), а съехал аж к сектору(8192), о чём говорит поле "Volume First LBA". В такой организации пространства есть смысл, т.к. нам заранее известны ориентировочные размеры файлов – это фотки, мультимедиа и прочие, т.е. больше стандартного кластера 4КБ:
6. Заключение
Если не брать во-внимание детали оформления служебных структур, основным недостатком FAT32 является полное отсутствие "инстинкта самосохранения" при критических сбоях. Хорошо хоть инженеры предусмотрели некую пародию, в виде резервных блоков ВРВ и таблицы FAT2. Зато в NTFS всё продумано до мелочей, и в этом большое её преимущество. Например метафайл NTFS под названием "$LogFile" представляет собой журнал последней удачной конфигурации. Если случается крах, то при следующей перезагрузке, все параметры считываются уже из этого журнала, который драйвер NTFS обновляет при обычном выключении компьютера. Однако выбор у пользователей должен быть всегда, и FAT как-раз нам его предоставляет.
В скрепке лежит инклуд, и ехе-файл для тестов. Увидимся теперь на пороге Нового года, пока!