[Перевод] Как написать собственную файловую систему на языке Rust29.07.2020 15:48

Исходные данные и результаты работы программ должны где-то храниться для дальнейшего использования. Их хранение нужно организовать так, чтобы мы могли быстро получить нужную информацию. За эту задачу отвечает Файловая система (FS): она предоставляет абстракцию для устройств, на которых физически хранятся данные.

В этом посте мы больше узнаем о концепциях, используемых файловыми системами, и о том, как, зная их, можно написать свою файловую систему на языке Rust.

Файловая система и диск

Когда данные нужно сохранить на жестком диске (HDD) или твёрдотельном накопителе (SSD), они записываются небольшими секторами (или страницами в случае SSD). Диски не знают о том, что представляет собой тот или иной фрагмент данных. Диск всего лишь хранит массив секторов. А управлять и взаимодействовать с ними должна файловая система.

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

На следующем рисунке приведен пример того, как файловая система структурирует информацию на диске:

Далее мы разберёмся, какие бывают типы блоков.

Суперблоки и битовые карты (bitmaps)

Суперблок хранит большую часть метаданных о файловой системе: размер блока, временные метки, сколько блоков и файлов используется, сколько свободно и так далее.

Битовые карты являются одним из способов отслеживания того, какие блоки данных и индексные дескрипторы (иноды) являются свободными. Каждому сектору в файловой системе соответствует один бит карты. Если сектор занят, то значение соответствующего бита в битовой карте устанавливается в 1, если свободен — в 0.

Инод

Инод — это структура, в которой хранятся метаданные о файле: разрешения, размер, расположение блоков данных, из которых состоит файл и многое другое.

Иноды хранятся вместе с блоками, которые вместе образуют таблицу инодов, как показано на следующем рисунке.

Для каждого сектора в битовой карте инодов с индексом, установленным в 1, в таблице будет соответствующий инод. Индекс сектора совпадает с индексом в таблице.

Блоки данных

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

Указатели на блоки данных

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

Чтобы получить представление о максимальном размере файла для каждого уровня, давайте возьмём фиксированный размер блока в 4 КиБ. Большинство файлов имеют небольшой размер, поэтому 12 прямых указателей позволят хранить файлы размером до 48 КиБ. Учитывая, что каждый указатель занимает 4 байта, один косвенный указатель позволит увеличить размер файла до 4 МиБ:

(12 + 1024) * 4 KiB

С введением двойных косвенных указателей размер файла вырастает до 4 ГиБ:

(12 + 1024 + 10242) * 4 KiB

С добавлением тройных косвенных указателей мы получаем 4 TиБ:

(12 + 1024 + 10242 + 10243) * 4 KiB

Поэтому такой подход может быть не очень эффективным для обработки больших файлов.

Например, файл размером 100 МБ потребует 25600 блоков. В случае фрагментации блоков на диске производительность может сильно пострадать.

Некоторые файловые системы используют экстенты, которые позволяют объединить несколько логических блоков. В этом случае мы используем один указатель и задаём длину диапазона объединённых блоков. В нашем примере выше для описания файла будет использован один экстент размером 100 МБ. Для работы с более крупными файлами можно использовать несколько экстентов.

Каталоги

Возможно, вы заметили, что у каталогов нет собственной структуры. Дело в том, что инод представляет как файлы, так и каталоги. Разница заключается в том, что именно хранится в соответствующих блоках данных. Каталог — это по сути список всех файлов, которые он включает. Каждая запись имеет вид (имя, порядковый номер), поэтому при поиске определённого файла (или другого каталога) система использует имя для поиска соответствующего инода.

Поиск файла может быть медленным, если каталог содержит большое количество файлов. Эту проблему можно решить, поддерживая отсортированный список и используя бинарный поиск. Или вместо списка, можно также использовать хеш-таблицу или сбалансированное дерево поиска.

Чтение и запись

Чтение

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

Запись

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

Моя файловая система (GotenksFS)

Я некоторое время изучал язык Rust и решил написать на нём свою собственную файловую систему. Я во многом опирался на ext4, а также использовал FUSE, свободный модуль для ядер UNIX-подобных ОС. Вместо диска я использовал обычный файл. Размер блока можно выставить в 1 КиБ, 2 КиБ или 4 КиБ. Файлы могут иметь размер до 4 ГиБ для блоков размером 4 КиБ. Потенциально файловая система может занимать до 16 ТиБ.

Начинаем

Первым шагом стало создание образа со значениями конфигурации для файловой системы. Это достигается с помощью команды mkfs:

$ ./gotenksfs mkfs disk.img -s "10 GiB" -b 4096

После выполнения команды создаётся образ с общим размером 10 ГиБ, а каждый блок в файловой системе имеет размер 4 КиБ.

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

Монтирование

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

$ ./gotenksfs mount disk.img gotenks

Основные структуры

Суперблок записывается в первых 1024 байтах и ​​содержит значения конфигурации, указанные в команде mkfs.

pub struct Superblock {
    pub magic: u32,
    pub block_size: u32,
    pub created_at: u64,
    pub modified_at: Option,
    pub last_mounted_at: Option,
    pub block_count: u32,
    pub inode_count: u32,
    pub free_blocks: u32,
    pub free_inodes: u32,
    pub groups: u32,
    pub data_blocks_per_group: u32,
    pub uid: u32,
    pub gid: u32,
    pub checksum: u32,
}

Следующие два блока — это битовые карты для данных и для инода. Для таблицы инодов используется набор из n блоков. А в последующие блоки будут записываться пользовательские данные.

Инод я сформировал так:

pub struct Inode {
    pub mode: libc::mode_t,
    pub hard_links: u16,
    pub user_id: libc::uid_t,
    pub group_id: libc::gid_t,
    pub block_count: u32, // should be in 512 bytes blocks
    pub size: u64,
    pub created_at: u64,
    pub accessed_at: Option,
    pub modified_at: Option,
    pub changed_at: Option,
    pub direct_blocks: [u32; DIRECT_POINTERS as usize],
    pub indirect_block: u32,
    pub double_indirect_block: u32,
    pub checksum: u32,
}

Я реализовал поддержку двойных косвенных указателей — то есть, для диска с размером блока 4 КиБ максимальная ёмкость файла составит 4 ГиБ. Количество прямых указателей я ограничил двенадцатью:

pub const DIRECT_POINTERS: u64 = 12;

При первом запуске FS она создаёт корневой каталог:

pub struct Directory {
    pub entries: BTreeMap,
    checksum: u32,
}

Формируем группы блоков

Размер битовой карты для инода равен 4 КиБ, то есть в каждом блоке можно разместить 32768 инодов. Округлим это число до 128 байт: соответствующая таблица инодов потребует 4 МБ свободного места. Один из способов их структурирования выглядит так: есть множество блоков, выделенных для битовых карт, затем соответствующие числовые блоки для хранения инодов и оставшиеся блоки для пользовательских данных.

Но вместо этого мы можем создать группы блоков, которые всегда будут иметь один блок для битовой карты данных и один для битовой карты инода. Следующие 1024 блока содержат таблицу инодов, а затем идут 32768 блоков, которые используются для пользовательских данных.

Реализуем чтение и запись

Когда наш «диск» создан, можно заняться файловыми операциями. Создадим новый каталог с помощью mkdir:

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

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

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

fn write(&mut self, path: &Path, buf: &[u8], offset: u64, file_info: &mut fuse_rs::fs::WriteFileInfo)

В этом случае вместо повторного обхода пути для поиска инода система использует дескриптор файла (FS предварительно инициализирует его при создании файла). И тогда FS сможет собрать структуру, вычислив точный адрес инода:

fn inode_offsets(&self, index: u32) -> (u64, u64) {
    let inodes_per_group = self.superblock().data_blocks_per_group as u64;
    let inode_bg = (index as u64 - 1) / inodes_per_group;
    let bitmap_index = (index as u64 - 1) & (inodes_per_group - 1);
    (inode_bg, bitmap_index)
}

fn inode_seek_position(&self, index: u32) -> u64 {
    let (group_index, bitmap_index) = self.inode_offsets(index);
    let block_size = self.superblock().block_size;
    group_index * util::block_group_size(block_size)
        + 2 * block_size as u64
        + bitmap_index * INODE_SIZE
        + SUPERBLOCK_SIZE
}

Теперь, когда FS имеет информацию о том, какие блоки данных выделены для инода, она может использовать их для поиска точного адреса, чтобы записать туда данные. Новые блоки сначала добавляются в массив прямых указателей, и если размер файла превышает (12 * BLOCK_SIZE), FS выдаёт косвенный указатель (поле indirect_block). Для очень больших файлов система добавляет двойной косвенный указатель, используя поле double_indirect_block. Чтение из файла реализуется аналогично.

Ниже вы можете увидеть, как у меня работают чтение и запись:

Вывод

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

Важный момент — реализация косвенных указателей для хранения больших файлов. Если вам интересно узнать о файловых системах больше, я бы рекомендовал почитать о таких вещах, как журналирование, копирование при записи (Copy-On-Write), Лог-структурированные файловые системы.

Код для моего проекта файловой системы GotenksFS находится по адресу https://github.com/carlosgaldino/gotenksfs

На правах рекламы

Эпичные серверы — это надёжные серверы на Linux или Windows с мощными процессорами семейства AMD EPYC и очень быстрой файловой системой, используем исключительно NVMe диски от Intel. Попробуйте как можно быстрее!

© Habrahabr.ru