Базовая реализация файловой системы
Мне дали 2 килобайта, чтобы создать ультра минималистичную файловую систему, и я подумал о создании урезанной версии FAT16.
Моя единственная проблема - понять, как мне хранить FAT в томе. Допустим, я использую 2 байта на блок, следовательно, у меня будет 1024 блока. Мне нужна таблица с 1024 строками, и в каждой строке я буду сохранять следующий блок файла.
Поскольку каждый из этих блоков может адресовать другие 1023 блока, я не вижу, как эта таблица не будет использовать все мое пространство 2 КБ. Я не понимаю, как сохранить эту таблицу на моем жестком диске и использовать только несколько байтов, а не просто использовать блок 1024 для записи таблицы из 1024 строк.
1 ответ
Учитывая, что вам разрешено реализовать плоскую файловую систему и иметь такое небольшое пространство для работы, я бы посмотрел на что-то вроде файловой системы Apple DOS 3.3, а не на иерархическую файловую систему, такую как FAT16. Даже плоская файловая система-предшественник FAT16, FAT12, слишком сложна для ваших целей.
Я предлагаю разделить объем в 2 КБ на 256-байтовые "дорожки" с 16-байтовыми "секторами", чтобы использовать номенклатуру Apple DOS 3.3. Называйте их как хотите в своей собственной реализации. Это просто поможет вам сопоставить концепции, если вы будете использовать те же термины здесь на этапе проектирования.
Вам не нужен загрузочный образ DOS, и у вас нет времени для поиска движущейся головки диска, поэтому вместо установки дорожек 0-2 и размещения дорожки VTOC в середине диска давайте поместим наш VTOC на дорожку 0. VTOC, который содержит растровое изображение свободного сектора, местоположение первого сектора каталога и другие вещи.
Если мы зарезервируем всю дорожку 0 для VTOC, у нас останется 112 наших 16-байтовых секторов. Они будут упакованы только в 14 байтов для растрового изображения, что говорит о том, что нам действительно не нужен весь трек 0 для этого.
Вместо этого давайте отложим первые два сектора дорожки 0 и включим дорожку 0 в растровое изображение свободного сектора. Это вызывает определенную избыточность, поскольку первые два сектора всегда будут отображаться как "используемые", но это упрощает реализацию, поскольку в настоящее время особых случаев нет.
Давайте разделим концепцию VTOC в Apple DOS 3.3 на две части: сектор меток томов (VLS) и битовый массив свободных томов (VFSB).
Мы разместим VLS на дорожке 0 сектора 0.
Давайте отложим первые 2-4 байта VLS для магического числа, чтобы идентифицировать этот файл тома как принадлежащий вашей файловой системе. Без этого единственная отличительная черта ваших файлов томов - это то, что они имеют размер 2 КБ, что означает, что ваш код может быть вызван для удаления невинного файла, который оказался того же размера. Вы хотите больше страхования от уничтожения данных, чем это.
VLS также должен назвать этот том. Apple DOS 3.3 просто использовала номер тома, но, возможно, мы хотим использовать несколько байтов для имени ASCII.
VLS также должен указывать на первый сектор каталога. Нам нужно как минимум 2 байта для этого. У нас 128 треков, а это значит, что нам нужно как минимум 7 бит. Давайте использовать два байта: дорожка и сектор. Вот где вы попадаете в мельчайшие мысли о выборе дизайна. Теперь мы можем рассмотреть возможность перехода к размеру тома 4 КБ, определив 256 дорожек. Или, может быть, в этот момент мы решаем, что 16-байтовые сектора слишком малы, и увеличиваем их, чтобы мы могли выйти за пределы 4 КБ позже. Давайте пока придерживаемся 16-байтовых секторов.
Нам нужен только один сектор для VFSB: объем 2 КБ ÷ 16 байтов на сектор = 128 секторов ÷ 8 бит на байт = 16 байтов. Но, учитывая вышесказанное, мы могли бы рассмотреть возможность выделить в VLS байт для числа секторов VFSB, следующих за VL, чтобы обеспечить большие объемы.
Идея сектора каталога Apple DOS 3.3 должна быть в значительной степени напрямую переведена в эту новую файловую систему, за исключением того, что при игре только 16 байтов на сектор мы не можем описать 7 файлов на сектор. Нам нужно 2 байта для указателя на следующий сектор каталога, оставляя 14 байтов. Каждый файл должен иметь байт для флагов: удаленный, только для чтения и т. Д. Это означает, что у нас может быть 13-байтовое имя файла для 1 файла на сектор каталога или два 6-байтовых имени файла для 2 файлов на сектор каталога. Мы могли бы сделать 7 однобуквенных имен файлов, но это неубедительно. Если мы пойдем с вашей 3-символьной идеей имени файла, то это 3 файла на сектор каталога после учета байта флага на файл, оставляя 2 дополнительных байта для определения. Я бы пошел с 1 или 2 файлами на сектор, хотя.
Это в значительной степени то, что вам нужно. Остальное - реализация и расширение.
Еще одна идея для расширения: что, если мы хотим использовать это в качестве загрузочного носителя? Такие вещи обычно нуждаются в загрузчике, поэтому нам нужно переместить секторы VLS и VFSB вниз на 1, чтобы оставить сектор 0 дорожки 0 в стороне для загрузочного образа? Или, может быть, VLS содержит указатель на первый сектор каталога, который описывает файл, содержащий образ загрузки.