Владимир Мешков

Общая характеристика файловой системы FAT. Структура раздела с файловой системой FAT

Файловая система FAT (File Allocation Table) была разработана Биллом Гейтсом и Марком Макдональдом в 1977 году и первоначально использовалась в операционной системе 86-DOS. Чтобы добиться переносимости программ из операционной системы CP/M в 86-DOS, в ней были сохранены ранее принятые ограничения на имена файлов. В дальнейшем 86-DOS была приобретена Microsoft и стала основой для ОС MS-DOS 1.0, выпущенной в августе 1981 года. FAT была предназначена для работы с гибкими дисками размером менее 1 Мб и вначале не предусматривала поддержки жёстких дисков. Структура раздела FAT изображена на рисунке.

Рисунок 1. Структура раздела с файловой системой FAT

 

В файловой системе FAT дисковое пространство логического раздела делится на две области – системную и область данных (см. рис. 1). Системная область создается и инициализируется при форматировании, а впоследствии обновляется при манипулировании файловой структурой. Системная область файловых систем FAT состоит из следующих компонентов:

n  загрузочная запись (boot record, BR);

n  резервная область;

n  таблицы размещения файлов;

n  область корневого каталога (не существует в FAT32).

Область данных логического диска содержит файлы и каталоги, подчиненные корневому, и разделена на участки одинакового размера – кластеры. Кластер может состоять из одного или нескольких последовательно расположенных на диске секторов. Число секторов в кластере должно быть кратно 2N и может принимать значения от 1 до 64. Размер кластера зависит от типа используемой файловой системы и объема логического диска.

Назначение, структура и типы таблицы размещения файлов

Своё название FAT получила от одноимённой таблицы размещения файлов – File Allocation Table, FAT. В таблице размещения файлов хранится информация о кластерах логического диска. Каждому кластеру соответствует элемент таблицы FAT, содержащий информацию о том, свободен данный кластер или занят данными файла. Если кластер занят под файл, то в соответствующем элементе таблицы размещения файлов указывается адрес кластера, содержащего следующую часть файла. Номер начального кластера, занятого файлом, хранится в элементе каталога, содержащего запись об этом файле. Последний элемент списка кластеров содержит признак конца файла (EOF – End Of File). Первые два элемента FAT являются резервными.

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

Существуют следующие типы FAT – FAT12, FAT16, FAT32. Названия типов FAT ведут свое происхождение от размера элемента: элемент FAT12 имеет размер 12 бит (1,5 байт), FAT16 – 16 бит (2 байта), FAT32 – 32 бита (4 байта). В FAT32 четыре старших двоичных разряда зарезервированы и игнорируются в процессе работы операционной системы.

Корневой каталог

За таблицами размещения файлов следует корневой каталог. Каждому файлу и подкаталогу в корневом каталоге соответствует 32-байтный элемент каталога (directory entry), содержащий имя файла, его атрибуты (архивный, скрытый, системный и «только для чтения»), дату и время создания (или внесения в него последних изменений), а также прочую информацию. Для файловых систем FAT12 и FAT16 положение корневого каталога на разделе и его размер жестко зафиксированы. В FAT32 корневой каталог может быть расположен в любом месте области данных раздела и иметь произвольный размер.

Форматы имен файлов

Одной из характеристик ранних версий FAT (FAT12 и FAT16) является использование коротких имен файлов. Короткое имя состоит из двух полей – 8-байтного поля, содержащего собственно имя файла, и 3-байтного поля, содержащего расширение (формат «8.3»). Если введенное пользователем имя файла короче 8 символов, то оно дополняется пробелами (код 0x20); если введенное расширение короче трёх байтов, то оно также дополняется пробелами.

Структура элемента каталога для короткого имени файла представлена в таблице 1.

Первый байт короткого имени выполняет функции признака занятости каталога:

n  если первый байт равен 0xE5, то элемент каталога свободен и его можно использовать при создании нового файла;

n  если первый байт равен 0x00, то элемент каталога свободен и является началом чистой области каталога (после него нет ни одного задействованного элемента).

 

Таблица 1. Структура элемента каталога для короткого имени файла

 

Смещение	Размер (байт)	Содержание
0x00	11	Короткое имя файла
0x0B	1	Атрибуты файла
0x0C	1	Зарезервировано для Windows NT. Поле обрабатывается только в FAT32
0x0D	1	Поле, уточняющее время создания файла (содержит десятки миллисекунд). Поле обрабатывается только в FAT32
0x0E	1	Время создания файла. Поле обрабатывается только в FAT32
0x10	2	Дата создания файла. Поле обрабатывается только в FAT32
0x12	2	Дата последнего обращения к файлу для записи или считывания данных. Поле обрабатывается только в FAT32
0x14	2	Старшее слово номера первого кластера файла. Поле обрабатывается только в FAT32
0x16	2	Время выполнения последней операции записи в файл
0x18	2	Дата выполнения последней операции записи в файл
0x1A	2	Младшее слово номера первого кластера файла
0x1C	4	Размер файла в байтах

 

На использование ASCII-символов в коротком имени накладывается ряд ограничений:

n  нельзя использовать символы с кодами меньше 0x20 (за исключением кода 0x05 в первом байте короткого имени);

n  нельзя использовать символы с кодами 0x22, 0x2A, 0x2B, 0x2C, 0x2E, 0x2F, 0x3A, 0x3B, 0x3C, 0x3D, 0x3E, 0x3F, 0x5B, 0x5C, 0x5D, 0x7C;

n  нельзя использовать символ пробела (0x20) в первом байте имени.

В файловых системах FAT32 и VFAT (виртуальная FAT, расширение FAT16) включена поддержка длинных имен файлов (long file name, LFN). Для хранения длинного имени используются элементы каталога, смежные с основным элементом. Имя файла записывается не ASCII-символами, а в Unicode. В одном элементе каталога можно сохранить фрагмент длиной до 13 символов Unicode. Неиспользованный участок последнего фрагмента заполняется кодами 0xFFFF. Структура элемента каталога для длинного имени файла представлена в таблице 2.

Таблица 2. Структура элемента каталога для длинного имени файла

 

Смещение	Размер (байт)	Содержание
0x00	1	Номер фрагмента
0x01	10	Символы 1-5 имени файла в Unicode
0x0B	1	Атрибуты файла
0x0C	1	Байт флагов
0x0D	1	Контрольная сумма короткого имени
0x0E	12	Символы 6-11 имени файла в Unicode
0x1A	2	Номер первого кластера (заполняется нулями)
0x1C	4	Символы 12-13 имени файла в Unicode

Длинное имя записывается в каталог первым, причем фрагменты размещены в обратном порядке, начиная с последнего. Вслед за длинным (полным) именем размещается стандартный описатель файла, содержащий укороченный по специальному алгоритму вариант этого имени. Пример хранения длинного имени файла показан здесь: http://www.ntfs.com/fat-filenames.htm.

Загрузочный сектор

В первом секторе логического диска с системой FAT располагается загрузочный сектор и блок параметров BIOS. Начальный участок данного блока для всех типов FAT идентичен (таблица 3). Различия в структуре загрузочных секторов для разных типов FAT начинаются со смещения 0x24. Для FAT12 и FAT16 структура имеет вид, показанный в таблице 4, для FAT32 – в таблице 5.

Таблица 3. Начальный участок загрузочного сектора

 

Смещение	Размер, байт	Описание
0x00	3	Безусловный переход (jmp) на загрузочный код
0x03	8	Идентификатор фирмы-изготовителя
0x0B	2	Число байт в секторе (512)
0x0D	1	Число секторов в кластере
0x0E	2	Число резервных секторов в резервной области раздела, начиная с первого сектора раздела
0x10	1	Число таблиц (копий) FAT
0x11	2	Для FAT12/FAT16 - количество 32-байтных дескрипторов файлов в корневом каталоге; для FAT32 это поле имеет значение 0
0x13	2	Общее число секторов в разделе; если данное поле содержит 0, то число секторов задается полем по смещению 0x20
0x15	1	Тип носителя. Для жесткого диска имеет значение 0xF8; для гибкого диска (2 стороны, 18 секторов на дорожке) – 0xF0
0x16	2	Для FAT12/FAT16 это поле содержит количество секторов, занимаемых одной копией FAT; для FAT32 это поле имеет значение 0
0x18	2	Число секторов на дорожке (для прерывания 0x13)
0x1A	2	Число рабочих поверхностей (для прерывания 0x13)
0x1C	4	Число скрытых секторов перед разделом
0x20	4	Общее число секторов в разделе. Поле используется, если в разделе свыше 65535 секторов, в противном случае поле содержит 0.

 

Таблица 4. Структура загрузочного сектора FAT12/FAT16

 

Смещение	Размер, байт	Описание
0x24	1	Номер дисковода для прерывания 0х13
0x25	1	Зарезервировано для Windows NT, имеет значение 0
0x26	1	Признак расширенной загрузочной записи (0x29)
0x27	4	Номер логического диска
0x2B	11	Метка диска
0x36	8	Текстовая строка с аббревиатурой типа файловой системы

 

Таблица 5. Структура загрузочного сектора FAT32

 

Смещение	Размер, байт	Описание
0x24	4	Количество секторов, занимаемых одной копией FAT
0x28	2	Номер активной FAT
0x2A	2	Номер версии FAT32: старший байт - номер версии, младший – номер ревизии. В настоящее время используется значение 0:0
0x2С	4	Номер кластера для первого кластера корневого каталога
0x30	2	Номер сектора структуры FSINFO в резервной области логического диска
0x32	2	Номер сектора(в резервной области логического диска), используемого для хранения резервной копии загрузочного сектора
0x34	12	Зарезервировано (содержит 0)

 Кроме перечисленных в таблицах 2-го и 3-го полей, нулевой сектор логического диска должен содержать в байте со смещением 0x1FE код 0x55, а в следующем байте (смещение 0x1FF) – код 0xAA. Указанные два байта являются признаком загрузочного диска.

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

На логическом диске с организацией FAT32 дополнительно присутствует структура FSInfo, размещаемая в первом секторе резервной области. Эта структура содержит информацию о количестве свободных кластеров на диске и о номере первого свободного кластера в таблице FAT. Формат структуры описан в таблице 6.

Таблица 6. Структура сектора FSInfo и резервного загрузочного сектора FAT32

 

Смещение	Размер, байт	Описание
0x000	4	Значение 0x41615252 – сигнатура, которая служит признаком того, данный сектор содержит структуру FSInfo
0x004	480	Зарезервировано (содержит 0)
0x1E4	4	Значение 0x61417272 (сигнатура)
0x1E8	4	Содержит текущее число свободных кластеров на диске. Если в поле записано значение 0xFFFFFFFF, то число свободных кластеров неизвестно, и его необходимо вычислять
0x1EC	4	Содержит номер кластера, с которого дисковый драйвер должен начинать поиск свободных кластеров. Если в поле записано значение 0xFFFFFFFF, то поиск свободных кластеров нужно начинать с кластера номер 2
0x1F0	12	Зарезервировано (содержит 0)
0x1FC	4	Сигнатура 0xAA550000 – признак конца структуры FSInfo

Для доступа к содержимому файла, находящемуся на разделе с файловой системой FAT, необходимо получить номер первого кластера файла. Этот номер, как мы уже установили, входит в состав элемента каталога, содержащего запись о файле. Номеру первого кластера соответствует элемент таблицы FAT, в котором хранится адрес кластера, содержащего следующую часть файла. Элемент FAT, соответствующий последнему кластеру в цепочке, содержит сигнатуру конца файла. Для FAT12 это значение составляет 0xFFF, для FAT16 – 0xFFFF, для FAT32 – 0xFFFFFFFF.

Рассмотрим программную реализацию алгоритма чтения для каждого типа FAT, и начнём с FAT16.

Все исходные тексты, рассматриваемые в статье, доступны на сайте журнала.

Программная реализация алгоритма чтения файла с логического раздела с файловой системой FAT16

Разработаем модуль, выполняющий чтение N первых кластеров файла, созданного на разделе с файловой системой FAT16. Параметр N (число кластеров для считывания) является переменной величиной и задается пользователем. Имя файла соответствует формату «8.3», т.е. является коротким. Модуль функционирует под управлением ОС Linux.

Определим необходимые заголовочные файлы:

#include <stdio.h>

#include <unistd.h>

#include <fcntl.h>

#include <errno.h>

#include <linux/msdos_fs.h>

#include "split.h"

Заголовочный файл split.h имеет следующее содержание:

#include <linux/types.h>

#define SHORT_NAME 13   // максимальная длина короткого имени файла

 

struct split_name {

           __u8 name[9]; // имя файла

   __u8 ext[4]; // расширение файла

           int name_len, // длина имени файла

           ext_len;            // длина расширения файла

};

Cтруктура split_name предназначена для хранения составных частей короткого имени файла (имени и расширения) и их длин.

В заголовочном файле <linux/msdos_fs.h> определены структурные типы, описывающие основные компоненты файловой системы FAT – загрузочный сектор, сектор FSInfo, структуры элементов каталога для короткого и длинного имён файлов.

Рассмотрим кратко поля, которые входят в каждую из этих структур.

1. Структура загрузочного сектора struct fat_boot_sector:

n  __s8 system_id[8] – системный идентификатор;

n  __u8 sector_size[2] – размер сектора в байтах;

n  __u8 cluster_size – размер кластера в секторах;

n  __u16 reserved – число резервных секторов в резервной области раздела;

n  __u8 fats – количество копий FAT;

n  __u8 dir_entries[2] – количество 32-байтных дескрипторов файлов в корневом каталоге;

n  __u8 sectors[2] – число секторов на разделе; если это поле равно 0, используется поле total_sect;

n  __u8 media – тип носителя, на котором создана файловая система;

n  __u16 fat_length – размер FAT в секторах;

n  __u32 total_sect – размер раздела FAT в секторах (если поле sectors == 0).

 

Следующие поля данной структуры используются только FAT32:

n  __u32 fat32_length – размер FAT32 в секторах;

n  __u32 root_cluster – номер первого кластера корневого каталога;

n  __u16 info_sector – номер сектора, содержащего структуру FSInfo.

 

2. Структура сектора FSInfo struct fat_boot_fsinfo:

n  __u32 signature1 – сигнатура       0x41615252;

n  __u32 signature2 – сигнатура       0x61417272;

n  __u32 free_clusters – количество свободных кластеров. Если поле содержит -1, поиск свободных кластеров нужно начинать с кластера номер 2.

 

3. Структура элемента каталога короткого имени struct msdos_dir_entry:

n  __s8 name[8],ext[3] – имя и расширение файла;

n  __u8 attr – атрибуты файла;

n  __u8 ctime_ms – это поле уточняет время создания файла до мс (используется только FAT32);

n  __u16 ctime – время создания файла (используется только FAT32);

n  __u16 cdate – дата создания файла (используется только FAT32);

n  __u16 adate – дата последнего доступа к файлу (используется только FAT32);

n  __u16 starthi – старшие 16 бит номера первого кластера файла (используется только FAT32);

n  __u16 time,date,start – время и дата создания файла, номер первого кластер файла;

n  __u32 size – размер файла (в байтах).

 

4. Структура элемента каталога длинного имени:

n  __u8 id – номер элемента;

n  __u8 name0_4[10] – символы 1 – 5 имени;

n  __u8 attr – атрибуты файла;

n  __u8 alias_checksum – контрольная сумма короткого имени;

n  __u8 name5_10[12] – символы 6 – 11 имени;

n  __u8 name11_12[4] – символы 12 – 13 имени.

Продолжим рассмотрение программной реализации алгоритма и определим имя раздела, на котором создана файловая система FAT16:

#ifndef FAT16_PART_NAME

#define FAT16_PART_NAME "/dev/hda1"

#endif

Глобальные структуры:

struct fat_boot_sector fbs; // структура загрузочного сектора

struct msdos_dir_entry dentry; // структура элемента каталога

Глобальные переменные:

__u16 *fat16;           // сюда копируем таблицу FAT16

__u16 sector_size;      // размер сектора (из FAT16)

__u16 dir_entries;      // число 32-байтных дескрипторов

                        // в root-каталоге (0 для FAT32)

__u16 sectors;          // общее число секторов в разделе

__u32 fat16_size;       // размер FAT16

__u32 root_size;        // размер корневого каталога

__u32 data_start;       // начало области данных

__u16 byte_per_cluster; // размер кластера в байтах

__u16 next_cluster;     // очередной кластер в цепочке

__u8 *dir_entry = NULL; // указатель на записи каталога

 

int hard;               // дескриптор файла устройства

int fat;

Начнём рассмотрение с главной функции:

int main()

{

    int num;

Задаем полное имя файла, содержимое которого мы хотим прочитать. Напомню, что мы работаем только с короткими именами файлов. Порядок работы с длинными именами в данной статье не рассматривается.

    __u8 *full_path = "/Folder1/Folder2/text.txt";

Открываем файл устройства:

    hard = open(FAT16_PART_NAME, O_RDONLY);

    if(hard < 0) {

    perror(FAT16_PART_NAME);

    exit(-1);

    }

Считываем первые 10 кластеров файла. Считывание выполняет функция fat16_read_file(). Параметры функции – полное имя файла и число кластеров для чтения. Функция возвращает число прочитанных кластеров или -1, если при чтении произошла ошибка:

    num = fat16_read_file(full_path, 10);

    if(num < 0) perror("fat16_read_file");

    else printf("Read %d clusters\n", num);

Закрываем файл устройства и выходим:

    close(hard);

    return 0;

}

Функция чтения кластеров файла имеет следующий вид:

int fat16_read_file(__u8 *full_path, int num)

{

    struct split_name sn;             // структура для хранения составных частей файла

    __u8 tmp_name_buff[SHORT_NAME]; // буфер для временного хранения составных элементов полного пути файла

    static int i = 1;

    int n;

 

    __u8 *tmp_buff;

    __u16 start_cluster, next_cluster;

Параметры функции мы перечислили при рассмотрении функции main.

Подготовительные операции – обнуляем буфер tmp_name_buff и структуру struct split_name sn:

    memset(tmp_name_buff, 0, SHORT_NAME);

    memset((void *)&sn, 0, sizeof(struct split_name));

Первым символом в абсолютном путевом имени файла должен быть прямой слэш (/). Проверяем это:

    if(full_path[0] != '/') return -1;

Считываем с раздела загрузочный сектор:

    if(read_fbs() < 0) return -1;

Считанный загрузочный сектор находится сейчас в глобальной структуре struct fat_boot_sector fbs. Скопируем из этой структуры размер сектора, число записей в корневом каталоге и общее число секторов на разделе:

    memcpy((void *)&sector_size, (void *)fbs.sector_size, 2);

    memcpy((void *)&dir_entries, (void *)fbs.dir_entries, 2);