какую структуру образуют файлы в фс файловой системе fat

ВЛАДИМИР МЕШКОВ

Архитектура файловой системы FAT

Общая характеристика файловой системы 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 состоит из следующих компонентов:

Область данных логического диска содержит файлы и каталоги, подчиненные корневому, и разделена на участки одинакового размера – кластеры. Кластер может состоять из одного или нескольких последовательно расположенных на диске секторов. Число секторов в кластере должно быть кратно 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

#define FAT16_PART_NAME «/dev/hda1»

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; // дескриптор файла устройства

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

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

__u8 *full_path = «/Folder1/Folder2/text.txt»;

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

hard = open(FAT16_PART_NAME, O_RDONLY);

num = fat16_read_file(full_path, 10);

else printf(«Read %d clusters «, num);

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

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

int fat16_read_file(__u8 *full_path, int num)

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

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

__u16 start_cluster, next_cluster;

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

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

memset(tmp_name_buff, 0, SHORT_NAME);

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

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

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

Определим размер кластера в байтах:

byte_per_cluster = fbs.cluster_size * 512

Отобразим информацию, находящуюся в загрузочном секторе:

Вычисляем размер FAT16 в байтах и считываем её:

fat16_size = fbs.fat_length * 512;

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

Сейчас указатель dir_entry позиционирован на область памяти, содержащую записи корневого каталога. Размер этой области памяти равен размеру корневого каталога (root_size).

Сохраним (для контроля) содержимое корневого каталога в отдельном файле:

fat = open(«dir16», O_CREAT|O_WRONLY, 0600);

write(fat, dir_entry, root_size);

Вычисляем начало области данных:

data_start = 512 * fbs.reserved + fat16_size * fbs.fats + root_size;

Имея все записи корневого каталога, мы можем добраться до содержимого файла test.txt. С этой целью организуем цикл. В теле цикла проведем разбор полного имени файла, выделяя его элементы – подкаталоги (их у нас два, Folder1 и Folder2) и имя искомого файла (test.txt).

memset(tmp_name_buff, 0, SHORT_NAME);

Заполняем структуру struct split_name sn соответствующей информацией. Заполнение выполняет функция split_name, при этом выполняется проверка имени файла на соответствие формату «8.3»:

printf(«not valid name «);

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

printf(«No such file! «);

Проверяем атрибуты файла. Если это каталог, считываем его содержимое и продолжаем цикл:

Если это файл – считываем первые num кластеров. Для контроля считанную информацию сохраним в отдельном файле:

tmp_buff = (__u8 *)malloc(byte_per_cluster); // сюда будет считываться содержимое кластера

n = open(«clust», O_CREAT|O_RDWR, 0600); // в этом файле сохраним считанную информацию

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

memset(tmp_buff, 0, byte_per_cluster);

Считываем содержимое кластера в буфер tmp_buff и сохраняем его в отдельном файле:

if(write(n, tmp_buff, byte_per_cluster)

Считываем из FAT16 номер следующего кластера, занятого под данный файл. Если это последний кластер – прерываем цикл и возвращаемся в главную функцию:

Чтение загрузочного сектора FAT16 выполняет функция read_fbs(). Результат помещается в глобальную структуру fbs:

if(read(hard,(__u8 *)&fbs, sizeof(fbs))

Чтение таблицы размещения файлов файловой системы FAT16 выполняет функция read_fat16():

__u64 seek = (__u64)(fbs.reserved) * 512; // смещение к FAT16 от начала раздела

fat16 = (void *)malloc(fat16_size);

if(pread64(hard, (__u8 *)fat16, fat16_size, seek)

Чтение корневого каталога выполняет функция read_root_dentry():

__u64 seek = (__u64)fbs.reserved * 512 + fat16_size * fbs.fats; // смещение к корневому каталогу от начала раздела

root_size = 32 * dir_entries; // вычисляем размер корневого каталога

dir_entry = (__u8 *)malloc(root_size);

memset(dir_entry, 0, root_size);

if(pread64(hard, dir_entry, root_size, seek)

Чтение кластера, принадлежащего файлу, выполняет функция read_cluster(). Входные параметры функции – номер кластера cluster_num и указатель на буфер __u8 *tmp_buff, куда нужно поместить результат чтения. Смещение к кластеру на разделе вычисляется по формуле (см. [1]):

int read_cluster(__u16 cluster_num, __u8 *tmp_buff)

if(pread64(hard, tmp_buff, byte_per_cluster, seek)

Функция read_directory выполняет чтение записей каталога (не корневого) и помещает результат в область памяти, на которую настроен указатель dir_entry:

int read_directory(__u16 start_cluster)

Выделяем память для хранения содержимого каталога, считываем содержимое стартового кластера и получаем из таблицы FAT16 значение очередного кластера:

dir_entry = (__u8 *)realloc(dir_entry, i * byte_per_cluster);

Сохраним содержимое каталога в отдельном файле (для контроля):

fat = open(«dir16», O_CREAT|O_WRONLY, 0600);

write(fat, dir_entry, root_size);

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

Поиск в содержимом каталога элемента, соответствующего искомому файлу, выполняет функция get_dentry(). Входные параметры этой функции – указатель на структуру struct split_name *sn, содержащую элементы короткого имени файла:

int get_dentry(struct split_name *sn)

В глобальном буфере dir_entry находится массив элементов каталога, в котором мы собираемся искать запись файла (или каталога). Для поиска организуем цикл. В теле цикла производим копирование элементов каталога в глобальную структуру dentry и сравниваем значение полей name и ext этой структуры с соответствующими полями структуры struct split_name *sn. Совпадение этих полей означает, что мы нашли в массиве элементов каталога запись искомого файла:

if(!(memcmp(dentry.name, sn->name, sn->name_len)) &&

!(memcmp(dentry.ext, sn->ext, sn->ext_len)))

Весь вышеприведенный код находится в каталоге FAT16, файл fat16.c. Для получения исполняемого модуля создадим Makefile следующего содержания:

fat16: fat16.o split.o

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

В целом алгоритм чтения файла с раздела FAT12 идентичен алгоритму чтения файла с раздела FAT16. Отличие заключается в процедуре чтения элементов из таблицы FAT12. Таблица FAT16 рассматривалась нами как простой массив 16-разрядных элементов. Для чтения элементов таблицы FAT12 в [1] предложен следующий алгоритм:

Базируясь на этом алгоритме, реализуем функцию чтения элементов из таблицы FAT12:

int get_cluster(__u16 cluster_num)

Вычисляем смещение в таблице FAT12 и считываем из таблицы 16-разрядное слово:

seek = (cluster_num * 3) / 2;

Если стартовый номер кластера – четное число, сдвигаем считанное из таблицы значение на 4 бита в сторону младших разрядов, если нечетное – суммируем его с 0x0FFF:

if(cluster_num % 2) clust >>= 4;

Этот фрагмент можно также реализовать на ассемблере:

:»d» (clust), «c» (cluster_num));

Остановимся чуть подробнее на самом алгоритме. Предположим, что на разделе с FAT12 создан файл, который занимает 9-й и 10-й кластеры. Каждый элемент FAT12 занимает 12 бит. Т.к. из таблицы мы считываем 16-разрядные элементы, то смещение к 9-му элементу будет равно 13 байт (9 * 1.5 = 13, остаток отбрасываем), при этом младшие 4 разряда будут принадлежать 8-му элементу FAT. Их необходимо отбросить, а для этого достаточно сдвинуть считанный элемент на 4 бита в сторону младших разрядов, что и предусмотрено алгоритмом. Смещение к 10-му элементу будет равно 15 байт, и старшие 4 бита будут принадлежать 11-му элементу FAT. Чтобы их отбросить, необходимо выполнить операцию AND над 10-м элементом и маской 0x0FFF, что так же соответствует вышеприведенному алгоритму.

Исходные тексты модуля чтения файла с раздела FAT12 находятся в каталоге FAT12, файл fat12.c.

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

Алгоритм чтения файла с раздела с файловой системой FAT32 практически не отличается от алгоритма для FAT16, за исключением того, что в FAT32 корневой каталог может располагаться в любом месте раздела и иметь произвольный размер. Поэтому, чтобы было интереснее, усложним задачу – предположим, что нам известен только номер раздела с файловой системой FAT32. Чтобы считать с этого раздела информацию, необходимо вначале определить его координаты – смещение к разделу от начала диска. А для этого надо иметь представление о логической структуре жесткого диска.

Логическая структура жесткого диска

Рассмотрим логическую структуру жесткого диска, соответствующую стандарту Microsoft – «основной раздел – расширенный раздел – разделы non-DOS».

Пространство на жестком диске может быть организовано в виде одного или нескольких разделов, а разделы могут содержать один или несколько логических дисков.

На жестком диске по физическому адресу 0-0-1 располагается главная загрузочная запись (Master Boot Record, MBR). В структуре MBR находятся следующие элементы:

Таблица разделов описывает размещение и характеристики имеющихся на винчестере разделов. Разделы диска могут быть двух типов – primary (первичный, основной) и extended (расширенный). Максимальное число primary-разделов равно четырем. Наличие на диске хотя бы одного primary-раздела является обязательным. Extended-раздел может быть разделен на большое количество подразделов – логических дисков. Упрощенно структура MBR представлена в таблице 7. Таблица разделов располагается в конце MBR, для описания раздела в таблице отводится 16 байт.

Таблица 7. Структура MBR

Смещение Размер, байт 0 446 0x1BE 16 0x1CE 16 0x1DE 16 0x1EE 16 0x1FE 2

Структура записи элемента таблицы разделов показана в таблице 8.

Таблица 8. Структура записи элемента таблицы разделов

Первым байтом в элементе раздела идет флаг активности раздела (0 – неактивен, 0x80 – активен). Он служит для определения, является ли раздел системным загрузочным и есть ли необходимость производить загрузку операционной системы с него при старте компьютера. Активным может быть только один раздел. За флагом активности раздела следуют координаты начала раздела – три байта, означающие номер головки, номер сектора и номер цилиндра. Номера цилиндра и сектора задаются в формате прерывания Int 0x13, т.е. биты 0-5 содержат номер сектора, биты 6-7 – старшие два бита 10-разрядного номера цилиндра, биты 8-15 – младшие восемь бит номера цилиндра. Затем следует кодовый идентификатор System ID, указывающий на принадлежность данного раздела к той или иной операционной системе. Идентификатор занимает один байт. За системным идентификатором расположены координаты конца раздела – три байта, содержащие номера головки, сектора и цилиндра соответственно. Следующие четыре байта – это число секторов перед разделом, и последние четыре байта – размер раздела в секторах.

Таким образом, элемент таблицы раздела можно описать при помощи следующей структуры:

u8 bootable; // флаг активности раздела

u8 start_part[3]; // координаты начала раздела

u8 type_part; // системный идентификатор

u8 end_part[3]; // координаты конца раздела

u32 sect_before; // число секторов перед разделом

u32 sect_total; // размер раздела в секторах (число секторов в разделе)

Элемент первичного раздела указывает сразу на загрузочный сектор логического диска (в первичном разделе всегда имеется только один логический диск), а элемент расширенного раздела – на список логических дисков, составленный из структур, которые именуются вторичными MBR (Secondary MBR, SMBR).

Свой блок SMBR имеется у каждого диска расширенного раздела. SMBR имеет структуру, аналогичную MBR, но загрузочная запись у него отсутствует (заполнена нулями), а из четырех полей описателей разделов используются только два. Первый элемент раздела при этом указывает на логический диск, второй элемент указывает на следующую структуру SMBR в списке. Последний SMBR списка содержит во втором элементе нулевой код раздела.

Вернемся к рассмотрению модуля чтения файла с раздела FAT32.

#define SIGNATURE 0xAA55

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

#define DEVICE «/dev/hda»

Размер элемента таблицы разделов (16 байт):

#define PT_SIZE 0x10

Следующий массив структур устанавливает соответствие между кодом типа раздела и его символьным отображением:

Источник

• ← какую структуру образуют папки каталоги
• какую структуру представляет собой гражданское общество →