USB-polygon-10: Таблица памяти для имитации ФС

Структура памяти

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

Нужна таблица памяти. И даже не одна. Логично представить структуру фиктивной памяти в нескольких таблицах. Первая будет показывать область памяти, не зависящую от используемой ФС и необходимую любому носителю информации в той или иной форме: MBR, master boot record — главная загрузочная запись (или учет сапога хозяина, если хотите). Вторая таблица нужна для описания PBR, partition boot record, на первый взгляд не имеющей непосредственного отношения к ФС, но уже являющийся ее частью. Третья таблица будет описывать таблицу размещения файлов, FAT (file allocation table). Затем должна следовать запись, описывающая корневой каталог. В оставшейся памяти будет размещаться собственно информация носителя — папки и файлы. Эту зону можно тоже условно представить в виде примерной таблицы, хотя ее наполнение уже не является жестко фиксированным, в отличие от предыдущих.

Будет использоваться адресация LBA и термин «сектор», обозначающий в данном контексте не сектор физического диска, а логический блок, имеющий размер те же традиционные 512 байтов, что и сектор.

Главная загрузочная запись

MBR — запись, которая обязана присутствовать на любом носителе информации, если есть необходимость работать с ним стандартными способами. Есть оговорки. Во-первых, устройство хранения информации (микросхема, карта памяти, USB-носитель) может работать и в «сыром» режиме, без файловой системы с постраничной записью и посекторным чтением более-менее стандартными способами — функциями ОС вроде ReadFile(). Но это потребует изрядной порции дополнительной работы для обращения к носителю. Во-вторых, сегодня MBR — не единственный вариант, например, GPT — GUID Partition Table. Но в целях имитации флэш-памяти это все неважно, интересует именно MBR.

Общая структура MBR

Таблица 1. Структура классической MBR

Код загрузчика (первая строчка таблицы) — в сущности, программа, которую должен выполнить процессор, если в параметрах BIOS указано загружаться с данного устройства. Ему, процессору, предоставляют это устройство для чтения команд и выставляют счетчик команд в ноль. Если он — процессор — находит там команды, то начинает их выполнять. В эти 446 байтов можно попытаться запихать весь загрузчик, то есть программу, заставляющую загрузить ОС в оперативную память и передающую ей управление. Если загрузчик достаточно сложный (типа GRUB или из последних версий Windows), то в этот кусочек памяти он не поместится, придется разместить там предзагрузчик, который загрузит основной загрузчик и передаст управление ему. Существуют также другие варианты MBR, отличающиеся составом первых 446 байтов, где для кода загрузки отведено меньше места, зато добавлена всяческая дополнительная служебная информация.

Однако все это имеет смысл для носителей информации, которые могут использоваться в качестве загрузочных. К имитируемой флэшке это не относится, поэтому там будут нули.

И это очень хорошо. Нет необходимости хранить в памяти все необходимые записи целиком, из-за чего терялся бы смысл имитации, проще было бы разместить реальные записи в реальной памяти. А так можно не тратить память на хранение нулей, а просто отвечать нулями на адреса от 0 до 1BDh, и такой пустой участок не единственный.

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

Запись раздела

Таблица 2. Структура записи раздела

Адрес в таблице 2 относительный, то есть, от начала записи раздела.

Таких структур первичных разделов может быть 4. Первичный раздел может содержать ряд расширенных разделов. Но, опять же, в рамках проекта USB-polygon это не важно. Здесь вполне достаточно одного раздела, а это значит, что записи разделов 2, 3 и 4 будут заполнены нулями и сэкономят место при имитации.

MBR для имитации

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

Таблица 3. Итоговая MBR

Комментарии к таблице:

• Первая колонка (Адр.) — адрес в памяти устройства, при обращении к которому ОС ПК надеется получить информацию, описанную в данной строке.
• Вторая колонка (Описание) — что должно содержаться по указанному адресу.
• Третья колонка (Разм.) — размер поля в байтах.
• Четвертая колонка (r:c) — row:column — представление адреса в таком виде, как если бы блок информации отображался в традиционных HEX-редакторах, в виде набора строк по 16 байтов, то есть, номер строки и номер байта в ней. Эта колонка пригодится при реальной передаче данных от самодельного устройства в ответ на запросы ОС, так как при использовании библиотеки LUFA контроллер передает информацию пачками по 16 байтов. Таким образом, в этой колонке показаны номер пачки и номер байта в пачке.
• Пятая колонка (hex) — байты в шестнадцатеричной форме, которые должны быть переданы в данном конкретном случае.

В этой и следующих таблицах в пятой колонке кроме hex-данных могут быть десятичные числа, помеченные «dec», и строки, в которых пробелы заменены подчеркиванием «_». При передаче строк символы заменяются их кодами, естественно. В программе на языке С же можно в качестве передаваемого байта указать как его код, так и сам символ в одинарных кавычках, конечно же.

Пояснения по данным:

• Код загрузчика отсутствует, на запрос выдавать нули. Загружаться с фейковой флэшки не планируется (хотя, мысль интересная, можно однажды попробовать…)
• Статус первого раздела: неактивный, ноль, по той же причине — грузиться отсюда не будем.
• Головка, дорожка и сектор начала раздела выдаются нулями, потому что адресация CHS не используется, используется LBA.
• Тип раздела: 0C, что соответствует FAT32 с адресацией LBA.
• Головка, дорожка и сектор окончания раздела также выдается нулями.
• Начало первого сектора раздела: соответствует 62 сектору.
• Число секторов в разделе: попробуем для начала 4к секторов, а там посмотрим. Получится 2 097 152 байтов.
• Записи разделов 2, 3 и 4 забиваем нулями.
• Сигнатура фиксированная, может быть только 55AA.

Подробнее про начало сектора: почему именно 62? Не знаю. Так получилось. Во флэшках, отформатированных в Windows, обычно 62. Во флэшках, отформатированных в FAT32 в Linux может быть другой адрес, обычно меньше. Есть подозрение, что число появилось из порядка загрузки: MBR, найдя активный раздел (помеченный, как 80) считывает его загрузочный сектор и помещает по физическому адресу 7C00_hex, что в секторах соответствует как раз 62. Что мешает взять сектор, лежащий существенно ближе, и записать его в 62 сектор оперативки? Я не знаю. Предполагаю, что это может как-то упростить операции переписывания данных: с какого адреса взяли, по такому и записали, только в другое устройство. Но это не очень важно. Можно поэкспериментировать, «двигая» этот адрес. Для реальной флэшки смещение загрузочного сектора раздела поможет сэкономить напрасно неиспользуемое место, а для фиктивной флэшки вообще ни на что не влияет. Поэтому ставлю 62, оно реально работает, а там посмотрим.

Теперь про общее число секторов в разделе. Вообще-то, FAT32 сама хранит информацию о своем разделе, и я читал, что Windows игнорирует эту запись в MBR. Но пока оставлю так.

Итого: при запросе MBR устройству надо будет отдать всего 5 ненулевых байтов.

Загрузочная запись раздела

В литературе встречаются обозначения PBR и VBR — Partition и Volume Boot Record. Адресация здесь ведется от начала раздела, так как раздел может быть практически где угодно, проще будет потом прибавить смещение.

Загрузочначя запись начинает раздел. Раздел, как договаривались, будет «отформатирован» в FAT32. А файловые системы FAT состоят из 4 областей:

• 0: Зарезервированная область
• 1: Область FAT
• 2: Область корневого каталога (для версий FAT до FAT32)
• 3: Область файлов и каталогов

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

Таблица 4. Загрузочная запись раздела

Пояснения к таблице:

• Первая строка: инструкция перехода на программу загрузки. Если сектор является загрузочным, то загрузчик MBR разместит этот сектор, адрес которого найдет в таблице разделов, в положенном месте и передаст управление ему, то есть, первому его байту. Однако код загрузчика сектора начинается не здесь, а по адресу 5Ah. Вот эти три байта и перебрасывают управление туда: EBh = jmp, а 58h = смещение.
• Вторая строка иногда именуется «идентификатор изготовителя», «идентификатор ОС или файловой системы»,встречал даже «название и версия Windows». Строковая идентификация того, кто это все записал. Программа WinImage пишет сюда «WINIMAGE». Документ «FAT: General Overview of On-Disk Format» рекомендует строку «MSWIN4.1», как вызывающую минимум проблем совместимости. Имеет значение для некоторых FAT-драйверов. Для Windows вроде бы не имеет значения.

Далее начинается блок параметров BIOS (BIOS parameter block, BPB) — структура данных, описывающая логическую структуру хранилища данных:

• Байтов в секторе (логическом), как мы договаривались, 512
• Секторов в кластере 8, то есть, кластер четырехкилобайтный, довольно-таки распространенное значение.
• Зарезервированных секторов 1. Поле не должно быть равно 0. Для FAT32 обычно равно 32. ОС от Microsoft нормально воспринимают любое ненулевое значение.
• Таблиц FAT, традиционно, 2 — основная и резервная. Но мы-то знаем, что на самом деле ни одной.
• Количество элементов корневого каталога. Для FAT32 должно быть 0.
• Всего секторов в томе. 0 означает, что диск большой, больше 32МБ, поэтому размер будет задан по смещению 20h. Для FAT32 должно быть 0.
• Тип носителя — жесткий диск (строго говоря, фиксированный, неудаляемый носитель. Для съемных носителей значение F0h). Должно быть таким же, как первый байт таблицы FAT.
• Логических секторов в FAT12/FAT16, для FAT32 должно быть 0.
• Физических секторов на дорожку — 63. Поле имеет значение только для носителей, имеющих дисковую геометрию. Почему 63? Списал откуда-то…
• Число головок — FF. Тоже непонятно, зачем тут значение…
• Скрытых (зарезервированных) секторов перед данным разделом — 62
• Всего логических секторов в разделе (в 32-разрядном формате) — 1000h. Включает все сектора всех четырех областей раздела. Для FAT32 не должно быть равно 0.

Далее идут отличия BPB FAT32 от FAT12/FAT16:

• Размер одной таблицы FAT — 8 секторов или 1 кластер
• Главная таблица FAT нулевая. Вообще-то, поле флагов. Биты 0..3 — номер активной FAT, начиная с 0. Бит 7 равный 0 означает, что FAT в процессе работы отображается на все FAT, а равный 1 означает, что только одна FAT активна, и ее номер в битах 0..3. Биты 4..6 и 8..15 зарезервированы.
• Версия FAT — 0.0. Если не равно 0, старые версии Windows не будут монтировать диск.
• Начало корневого каталога — 2 кластер, так как 0 и 1 имеют особое значение в таблице FAT, ближе нельзя, дальше бессмысленно.
• Номер сектора структуры FSINFO в зарезервированной зоне тома FAT32, обычно 1. Структура содержит данные о количестве свободных кластеров и указатель на следующий свободный кластер, используется алгоритмом выделения свободных секторов диска.
• Резервный сектор. Если не 0, то указывает на номер сектора тома, в котором копия загрузочной записи. Обычно 6, другие значения не рекомендуются.
• Зарезервировано для будущего использования, должно быть установлено в 0.
• Номер физического диска — 80: первый диск в системе
• Зарезервировано.
• Сигнатура расширенного загрузчика, предопределенная константа. Показывает, что следующие три поля имеют место быть.
• ID диска — идентификатор, поддерживающий отслеживание томов съемных носителей. Обычно генерируется путем комбинации текущих даты и времени в 32-р. формате, поэтому иногда это поле называют «дата и время создания диска».
• Метка диска. Не очень-то нужно, потому что есть в записи корневого каталога.
• Аббревиатура файловой системы — «FAT32», дополнено пробелами.

Конец зоны BPB. Далее:

• Код загрузчика — заполняется нулями, загрузчика нет.
• Сигнатура загрузочного сектора — предопределенная константа.

UPD (03.07.2017):

Замечание относительно позиций по смещению 30h (Номер сектора структуры FSINFO) и по смещению 32h (Номер сектора - копии загрузочного).

В документе «FAT32 File System Specification» от Microsoft (fatgen103.pdf) первое поле — номер сектора структуры FSINFO в зарезервированной зоне тома FAT32 — обычно 1, а второе не просто обычно 6, но еще и значения, отличные от 6, не рекомендуются.

Я поставил рекомендуемые значения в программе для контроллера платы USB-polygon, и она замечательно работала под Windows 7 и XP. Однако в Debian 8 автоопределение флэшки для этой платы не сработало. Плата системе видна — fdisk -l выдает следующее:

Disk /dev/sdg: 8 MiB, 8388608 bytes, 16384 sectors
Units: sectors of 1 * 512 = 512 bytes
Sector size (logical/physical): 512 bytes / 512 bytes
I/O size (minimum/optimal): 512 bytes / 512 bytes
Disklabel type: dos
Disk identifier: 0x00000000

Device     Boot Start   End Sectors Size Id Type
/dev/sdg1          62  4157    4096   2M  c W95 FAT32 (LBA)

А при попытке монтирования вручную получаю ошибку:

mount: wrong fs type, bad option, bad superblock on /dev/sdg1,
       missing codepage or helper program, or other error

Однако ранние отладочные варианты этой программы под Linux вполне определялись в виде флэшки. Существенная разница была именно в этих полях: сначала я их занулял, а потом уже послушался умных документов и поставил рекомендуемые значения. А зря. Если ставлю значения, должен был и добавить в указанные сектора соответствующую информацию. А ее там нет. Винда это дело проглотила, а Линукс — отказался.

Так что в моем (сильно упрощенном) случае правильнее держать в этих полях нулевое значение, тогда работает в Windows 7, XP, Debian 8, Android 4 — проверено лично.

Таблица FAT

Важная структура данных, в честь которой и называется файловая система. Ну, здесь просто: список кластеров, занятых папками и файлами.

Причем, это односвязный список: каждый элемент является либо ссылкой на следующий элемент, либо признаком окончания цепочки элементов. Причем, для этого списка нет разницы между файлами и каталогами. Список состоит из 32-разрядных целых. Элемент, заполненный единицами (FFFFFFFFh), говорит о том, что он последний в цепи. Если он же и первый, значит, соответствующий ему файл (или каталог) занимает один кластер.

Строго говоря, в 32-разрядных элементах записаны 28-разрядные значения, старшие 4 бита зарезервированы и должны быть установлены в ноль, а точнее, должны сохранять предыдущее значение, для чего записываться с использованием маски. Но эти тонкости нужны для реализации программ чтения/записи структур FAT, например, драйверов ФС, а нам пока не важно. Поэтому маркер конца цепочки — элемент, заполненный единицами — на самом деле 0FFFFFFFh.

В FAT32 (в отличие от предыдущих версий FAT) корневой каталог равноправен с прочими папками и файлами. Указатель на него лежит в BPB, в загрузочной записи раздела. Обычно это 2, так как кластеры 0 и 1 имеют особое назначение. Теоретически корневой каталог можно разместить и дальше второй позиции, где-нибудь в середине таблицы (тогда физически он должен быть записан где-нибудь в середине памяти раздела), но в этом нет практического смысла.

Значит, кластер 2 соответствует корневому каталогу. В целях имитации ФС делать корневой каталог большего размера нет смысла: сильно много не наимитируешь. Поэтому элемент номер 2 будет 0FFFFFFFh. В области данных будет лежать кластер, соответствующий этому элементу, и там будет информация о том, где искать файлы, расположенные в корневом каталоге (а возможно, и вложенные папки второго уровня). То есть, будут ссылки на первые кластеры, а последующую цепочку драйвер ФС должен найти в таблице FAT: по ссылке найти первый кластер, и если он не заполнен единицами, то указывает на следующий элемент. Добравшись до последнего, драйвер будет знать, сколько в файле кластеров и где они лежат.

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

В целях имитации, когда точно известны параметры фейковых файлов, можно разместить их в фейковой же файловой таблице строго последовательно. Вразброс же файлы размещаются в результате фрагментации: когда записывается файл большего размера, чем первый свободный участок, и часть его пишется в ближайшее найденное пустое место, часть — в следующее пустое место. А у нас — все подряд. Допустим, в корне будет имитироваться файл, занимающий три кластера, тогда в файловой таблице элемент №3 будет содержать число 4 (запишется 04 00 00 00 00 00 00 00, младшим байтом вперед), элемент №4 будет содержать 5, а в элементе №5 будет записано 0FFFFFFFh. Дальше должны быть нули, сигнализирующие о том, что кластеры свободны.

Элементы файловой таблицы с номерами 0 и 1 имеют особое значение. Младший байт нулевого должен содержать тип носителя из BPB, в нашем случае — F8h. Остальные байты нулевого равны FFh. Второй элемент заполняется FFh целиком и может использоваться в FAT32 для указания необходимости проверки тома: верхние два бита обнуляются, а перед завершением работы с носителем туда снова записываютмя единицы. Если в свежезапущенном томе обнаружены в этом месте нули, значит он некорректно завершил работу, например, был внезапно обесточен или выдернут.

Стало быть, для примера начало файловой таблицы должно выглядеть, как в таблице 5, в предположении, что корневой каталог короткий (умещается в одном кластере, что естественно при малом количестве файлов), первый файл занимает три кластера, второй файл занимает один кластер, больше файлов и папок нет.

Таблица 5. Описатель файла в каталоге

Восемь столбцов — с третьего по десятый — соответствуют восьми байтам элементов таблицы (с нулевого по седьмой).

Файловая запись root

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

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

Каталог (ну, или папка, или директория) фактически является файлом. Лежит в области диска, соответствующей некоторому элементу файловой таблицы, содержит некоторые данные, занимает минимум кластер. Вот только эти данные не абы что, а набор описателей того, что принадлежит каталогу: файлы и папки. При этом в папке должны быть описатели папок с именами «.» и «..», указывающими на текущий и родительский каталоги соответственно. Описатель является структурой данных определенного размера, 32 байта.

Отсюда, кстати, следует, что пустой файл может быть записан в каталоге, но не занимать места на диске и иметь реальный размер, равный 0, однако пустой каталог не может быть совсем пустым, должен содержать минимум 2 описателя и будет занимать кластер. Значит, пустые каталоги — мусор, изрядно засоряющий носитель.

Запись корневого каталога все же имеет некоторые отличия от прочих папок. Она обязательно должна быть, она не имеет имени, даты и времени создания, не содержит файлы «.» и «..» в качестве первых двух подпапок, она единственная может иметь файл с установленным аттрибут VOLUME_ID, и тогда имя, записанное в соответствующем поле этой записи, будет именем тома. Адрес первого кластера (в полях «старшее слово первого кластера» и «младшее слова первого кластера») такой записи так же должен быть равен нулю, потому что для «файла», соответствующего метке тома, не выделяются реальные кластеры. Соответственно, размер этого «файла» тоже должен быть нулевым.

Тогда первый описатель «файла» в корневом каталоге должен выглядеть, как в таблице 6.

Таблица 6. Описатель файла-тома в каталоге

Прочие файловые записи

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

При имитации ФС это все надо будет формировать динамически, в соответствии с «файлами», которые планируется подсовывать читающей ОС.

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

Имя файла предполагается короткое, в формате «8.3», дополненное до нужной длины пробелами, непременно на латинице. Можно сделать и длиннее, и в другой кодировке, но это отдельный разговор. Для таких манипуляций потребуются дополнительные описатели, которые и подъедят ресурсы при имитации, и не являются действительно необходимыми.

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

Многие файловые системы FAT не поддерживают метки времени, кроме времени записи, поэтому поля «сотые доли секунды времени создания», «время создания», «дата создания» и «дата последнего обращения» являются необязательными и могут быть равны 0. Однако поля «время записи» и «дата записи» должны поддерживаться.

Поля даты считаются 16-разрядными словами относительно эпохи MS-DOS 01.01.1980. При этом:

• Биты 0..4 содержат число месяца в диапазоне от 1 до 31.
• Биты 5..8 содержат номер месяца в диапазоне от 1 до 12.
• Биты 9..15 содержат год от 1980-го в диапазоне от 0 до 127 (от 1980 до 2107).

Поля времени считаются 16-разрядными словами с двухсекундной дискретизацией. При этом:

• Биты 0..4 — число пар секунд в диапазоне от 0 до 29 (от 0 до 58 секунд).
• Биты 5..8 — минуты в диапазоне от 0 до 59.
• Биты 9..15 — часы в диапазоне от 0 до 23.

Номер первого кластера разбит на два слова, старшее и младшее, всего 32 разряда.

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

Важные константы

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

Константы с постфиксом _SHIFT полезны при вычислениях кратных величин. Так как число байтов в кластере кратно степени двойки, можно получить число байтов в N кластерах не умножая N на 512, а сдвинув влево на 8, на степень двойки. Это эконмит ресурсы: сдвиг проще и быстрее умножения.

Теперь можно попробовать реализовать имитацию этого всего в программе устройства.