Что будет в этой статье

Продолжаем цикл статей о создании файловой системы в ядре Linux, основанный на материалах курса ОС в Академическом университете ^[1].

В прошлый раз ^[2] мы настроили окружение, которое понадобится нам, чтобы знакомится с ядром. Затем мы взглянули на загружаемые модули ядра и написали простой «Hello, World!». Ну и наконец, мы написали простую и бесполезную файловую систему. Пришло время продолжить.

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

Почему так мало? Дело в том, что в этом посте нам потребуется определить структуру нашей файловой системы — то как она будет хранится на диске. Кроме того мы столкнемся с парой интересных моментов, таких как SLAB и RCU. Все это потребует некоторых объяснений — много слов и мало кода, так что пост и так будет довольно объемным.

Скучное начало

Наша файловая система должна быть простой, поэтому и хранится на диске она будет просто:

Начнем с конца:

• data blocks — блоки полезных данных, т. е. содержимое файлов и папок;
• table of inodes — таблица индексных узлов; количество индексных узлов определяется при форматировании и хранятся они в непрерывной последовательности блоков;
• free inodes — битовая карта свободных/занятых индексных узлов, которая занимает ровно 1 блок;
• free blocks — битовая карта свободных/занятых блоков, так же занимает 1 блок;
• super block — очевидно, суперблок нашей файловой системы; он хранит размер блока, количество блоков в таблице индексных узлов, номер индексного узла корневой папки;

Собственно похожая разметка диска используется и в других файловых системах. Например, группа блоков ^[3] в ext2/3 имеет похожую структуру, только ext2/3 работает с несколькими такими группами, а мы ограничимся одной. Такой формат считается устаревшим, и новые файловые системы отходят от него. Например, btrfs использует более интересную схему ^[4], которая дает ряд преимуществ над семейством ext. Но да вернемся к нашим баранам.

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

В утилите mke2fs, которая используется для форматирования диска под файловые системы ext2/3, есть ключик -i ^[5], который указывает на какой объем диска нужно создавать индексный узел, т. е. если указать -i 16384, то на каждые 16 килобайт дискового пространства будет создано по индексному узлу. Я воспользуюсь самым простым вариантом — буду создавать индексный узел на каждые 16 Кб дискового пространства, без возможности изменения этого значения (пока по крайней мере).

Последний общий момент, который стоит затронуть — размер блока. Файловая система может работать с блоками разного размера, я буду поддерживать блоки в 512, 1024, 2048 и 4096 байт — ничего необычного. Это связано с тем, что с блоками, влезающими в страницу работать проще (мы вернемся к этому чуть позже), но делать так совсем не обязательно, более того, большие размеры блоков могут способствовать большей производительности.

Вообще подбор правильного размера блока для классических файловых систем — довольно занятная тема. Например, в известной книге по ОС ^[6] приводятся информация о том, что при размере блока в 4 Кб 60 — 70% файлов будут помещаться в один блок. Чем больше файлов помещается в один блок, тем меньше фрагментация, выше скорость чтения, но и больше места используется впустую. В нашем случае, ко всему прочему, размер блока является главным ограничителем файловой системы — при размере блока в 4 Кб битовая карта свободных блоков может покрыть всего 128 Мб дискового пространства.

Назад к практике

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

struct aufs_disk_super_block
{
	__be32	dsb_magic;
	__be32	dsb_block_size;
	__be32	dsb_root_inode;
	__be32	dsb_inode_blocks;
};

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

Учитывая, что мы будем поддерживать разные размеры блоков (что, впрочем, не потребует от нас никаких усилий), мы должны знать какой размер используется в данной конкретной файловой системе, и суперблок хранит для нас эту информацию в поле dsb_block_size.

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

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

Обратите внимание, что для полей используются типы фиксированного размера. Это потому что мы будем записывать эту структуру на диск «как есть». Однако зафиксировать размер недостаточно, нужно зафиксировать еще порядок байт. Я буду использовать big endian ^[7], он же сетевой порядок байт, о чем говорит название типа (__be32).

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

Тип __be32, по факту, является синонимом uint32_t, но его название подчеркивает, что переменная хранит данные в big endian (этакий способ документации). В ядре есть аналогичный тип и для little endian.

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

struct aufs_disk_inode
{
	__be32	di_first;
	__be32	di_blocks;
	__be32	di_size;
	__be32	di_gid;
	__be32	di_uid;
	__be32	di_mode;
	__be64	di_ctime;
};

Индексный узел, в первую очередь, определяет где на диске хранится файл/каталог. Способы хранения файлов могут быть самыми разнообразными, я буду использовать довольно простой — один экстент на один файл. Экстент — непрерывная последовательность блоков диска, т. е. каждый файл/каталог будет храниться в непрерывной последовательности блоков. Поля di_first и di_blocks хранят первый блок и количество блоков в экстенте соответственно.

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

Однако у такой организации есть и положительные моменты — файлы не фрагментированы, а это хорошо влияет на скорость последовательного чтения. Поэтому такая структура может замечательно использоваться в файловых системах рассчитанных только на чтение, например, в iso 9660 ^[8] (хотя и она уже поддерживает фрагментацию файлов).

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

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

Поля di_gid и di_uid — идентификаторы группы и пользователя. Сохранять такую информацию в файловой системе не всегда имеет смысл, я вставил их для примера.

Поле di_mode — хранит права доступа для группы владельца файла, владельца файла и всех остальных пользователей. Раз уж я сохранил группу и владельца то и права доступа стоит сохранить. Еще di_mode хранит тип объекта, который описывает индексный узел, например, является ли объект каталогом или файлом.

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

Форматируем диск

Итак, когда мы определили формат хранения файловой системы на диске, пора написать утилиту, которая приведет диск в правильный формат. Диск в Linux — это просто файл (тут уместно вспомнить известное дизайнерское решение Unix ^[9]). Так что форматирование диска — просто запись в файл нужных данных. А нужные данные в нашем случае — суперблок, битовые карты, и корневой каталог (пока пустой).

Чтобы не превращать статью о ядре Linux в статью о C++ (особенно в свете отношения Линуса к последнему ^[10]) я предлагаю вам самостоятельно разобраться с исходниками на github, но кратко пройдусь по основным классам:

• Configuration — класс который хранит конфигурацию будущей файловой системы (размер блока, размер таблицы индексных узлов, количество блоков, имя файла устройства).
• Block — представляет один блок диска. Данные пишутся и читаются с диска блоками.
• BlocksCache — предоставляет доступ к блокам.
• Inode — обертка над индексным узлом. Она скрывает преобразования порядка байт, запись и чтение данных индексного узла из блока.
• SuperBlock — обертка на суперблоком. Как и в случае с Inode скрывает запись и чтение из блока, заполняет битовые карты, выделяет индексные узлы и блоки, т. е. по факту выполняет форматирование.

Утилита позволяет изменять размер блока через ключи -s или --block_size, и количество блоков, которые будут использованы под файловую систему через ключи -b или --blocks.

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

Назад к файловой системе

Теперь вернемся к нашему загружаемому модулю. Начнем мы с чтения суперблока с диска. Но перед этим заведем еще одну структуру для суперблока:

struct aufs_super_block
{
	uint32_t	asb_magic;
	uint32_t	asb_inode_blocks;
	uint32_t	asb_block_size;
	uint32_t	asb_root_inode;
	uint32_t	asb_inodes_in_block;
};

Эта структура будет представлять суперблок в памяти. Идея простая — читаем с диска aufs_disk_super_block и преобразуем его в aufs_super_block выполняя преобразования порядка байт и попутно вычисляя всякие полезные данные (в данном случае asb_inodes_in_block). Вообще эта структура — отличное место для всяких глобальных переменных файловой системы.

Вспоминая прошлый пост, мы имеем уже три структуры для представления суперблока:

• super_block — структура, которую предоставляет ядро;
• aufs_disk_super_block — структура, которая хранится на диске;
• aufs_super_block — еще одна структура, которая будет хранится в памяти;

Две структуры — это понятно, но зачем нам третья? Дело в том, что Linux не знает ничего о нашей файловой системе, поэтому вполне вероятно, что super_block (как и inode, как и любая другая структура ядра Linux) не содержит всех нужных нам полей. Поэтому мы вынуждены заводить свои дополнительные структуры и связывать их со структурами ядра. Как же их связать?

В ядре есть два распространенных способа организации такой связи (назовем их композицией и наследованием). Для супер блока мы воспользуемся композицией. Этот способ требует поддержки со стороны ядра — внутри структуры super_block ^[11] есть интересное поле:

struct super_block {
	...
	void	*s_fs_info;
	...
};

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

static struct aufs_super_block *aufs_super_block_read(struct super_block *sb)
{
	struct aufs_super_block *asb = (struct aufs_super_block *)kzalloc(sizeof(struct aufs_super_block), GFP_NOFS);
	struct aufs_disk_super_block *dsb = NULL;
	struct buffer_head *bh = NULL;

	if (!asb)
	{
		pr_err("aufs cannot allocate super blockn");
		return NULL;
	}

	bh = sb_bread(sb, 0);
	if (!bh)
	{
		pr_err("cannot read 0 blockn");
		goto free_memory;
	}

	dsb = (struct aufs_disk_super_block *)bh->b_data;
	aufs_super_block_fill(asb, dsb);
	brelse(bh);

	if (asb->asb_magic != AUFS_MAGIC)
	{
		pr_err("wrong magic number %un", (unsigned)asb->asb_magic);
		goto free_memory;
	}

	return asb;

free_memory:
	kfree(asb);
	return NULL;
}

Первое, что делает эта функция — это выделяет память под структуру суперблока. Для выделения памяти в ядре есть довольно много способов, kzalloc ^[12] (и kmalloc ^[13] вместе с ним) — самый простой. Работает как и обычный malloc, только требует передачи дополнительного набора флагов. Отличие kzalloc от kmalloc в том, что первый заполняет выделенную память нулями (что просто сводится к передаче дополнительно флага внутрь kmalloc).

Я упомянул о флагах, зачем они? Дело в том, что разные части ядра должны удовлетворять различным гарантиям. Например, в контексте обработки сетевого пакета нельзя блокироваться, а чтобы задействовать DMA ^[14] требуется выделять память в специальном регионе памяти. Так как выделение памяти используется везде, требуется механизм «настройки». В нашем случае используется флаг GFP_NOFS, который говорит, что аллокатор памяти не будет обращаться к средствам файловой системы, что логично при реализации файловой системы, хотя в данном конкретном случае и не обязательно.

Естественно в ядре не забываем проверить, что память была выделена без проблем.

Следующий принципиальный момент — вызов функции sb_bread ^[15]. Вот оно чтение с диска! Функция принимает указатель на суперблок и номер блока, который нужно прочитать — совсем просто. Возвращает функция указатель на структуру buffer_head ^[16], а сами данные блока доступны через поле b_data этой структуры.

Естественно и в этом случае не забываем проверить, что чтение прошло удачно.

Далее мы просто преобразуем указатель на char к указателю на структуру aufs_disk_super_block. Функция aufs_super_block_fill заполняет структуру aufs_super_block используя aufs_disk_super_block не делая ничего необычного:

static inline void aufs_super_block_fill(struct aufs_super_block *asb,
			struct aufs_disk_super_block const *dsb)
{
	asb->asb_magic = be32_to_cpu(dsb->dsb_magic);
	asb->asb_inode_blocks = be32_to_cpu(dsb->dsb_inode_blocks);
	asb->asb_block_size = be32_to_cpu(dsb->dsb_block_size);
	asb->asb_root_inode = be32_to_cpu(dsb->dsb_root_inode);
	asb->asb_inodes_in_block =
		asb->asb_block_size / sizeof(struct aufs_disk_inode);
}

Как не трудно догадаться функция be32_to_cpu преобразует число из big endian в порядок байт используемый платформой.

После того, как мы закончили работу с блоком его нужно освободить, для этого существует функция brelse ^[17]. Она на самом деле просто уменьшает счетчик ссылок на этот блок. Блок не будет освобожден сразу, как только счетчик ссылок дойдет до 0 — для блоков в ядре работает сборщик мусора, который без серьезной необходимости не будет освобождать блок. Причина в том, что чтение блоков с диска — довольно дорогая операция, поэтому разумно поддерживать кеш прочитанных блоков, и при повторном чтении того же блока возвращать уже прочитанный (если, конечно, он еще присутствует в кеше).

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

Для обративших внимание на goto, в ядре goto используется довольно часто. В основном, для организации обработки ошибок — в языке C нет исключений, а идея разделения основного пути выполнения и обработки ошибок довольно привлекательна, тут то нам и приходит на выручку goto. В данном случае использование goto почти ничего не дает — я вставил его сюда намерено, как пример того, зачем он используется. Вообще среди разработчиков ядра ненавистников goto не так уж и много, так что есть места в коде злоупотребляющие злосчастным оператором ^[18] — стоит быть к этому готовым.

Внимательный читатель, наверно, обратил внимание на одну нестыковку. Как я уже говорил, файловые системы могут работать с разными размерами блока, и хранится эта информация скорее всего в суперблоке. Так какого же размера блок прочитает функция sb_bread при чтении суперблока? В нашем случае все просто, по-умолчанию, размер блока устанавливается в размер блока блочного устройства (как много блоков...). И мы надеемся, что его размера достаточно для структуры суперблока — в нашем случае так и есть.

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

static int aufs_fill_sb(struct super_block *sb, void *data, int silent)
{
	struct inode *root = NULL;
	struct aufs_super_block *asb = aufs_super_block_read(sb);

	if (!asb)
		return -EINVAL;

	sb->s_magic = asb->asb_magic;
	sb->s_fs_info = asb;
	sb->s_op = &aufs_super_ops;

	if (sb_set_blocksize(sb, asb->asb_block_size) == 0)
	{
		pr_err("device does not support block size %un",
					(unsigned)asb->asb_block_size);
		return -EINVAL;
	}

	root = aufs_inode_get(sb, asb->asb_root_inode);
	if (IS_ERR(root))
		return PTR_ERR(root);

	sb->s_root = d_make_root(root);
	if (!sb->s_root)
	{
		pr_err("aufs cannot create rootn");
		return -ENOMEM;
	}

	return 0;
}

Как я уже упоминал, мы сохраняем указатель на aufs_super_block в поле s_fs_info. Кроме того мы устанавливаем правильный размер блока вызовом sb_set_blocksize ^[19]. Как говорит комментарий внутри функции размер блока должен быть от 512 байт до размера страницы — этим и обусловлен наш выбор размеров блока. Если файловая система должна работать с большим размером блока — потребуются дополнительные усилия (впрочем не такие большие).

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

static void aufs_put_super(struct super_block *sb)
{
	struct aufs_super_block *asb = (struct aufs_super_block *)sb->s_fs_info;
	if (asb)
		kfree(asb);
	sb->s_fs_info = NULL;
	pr_debug("aufs super block destroyedn");
}

Не трудно догадаться что парной к функции kmalloc является функция kfree ^[20], точнее даже функции, так как есть несколько реализаций kfree в ядре (еще тут ^[21] и тут ^[22]), но не будем углубляться в детали.

Еще одно важное изменение внутри функции aufs_fill_sb — вызов aufs_inode_get. В прошлой статье мы создавали фиктивный inode, теперь мы научимся читать их с диска.

Но перед этим обращу ваше внимание на интересный момент — пару IS_ERR ^[23] и PTR_ERR ^[24]. Это простые преобразования указателей к числу и обратно, основанные на том, что ядро владеет полной информацией о расположении своей памяти и, соответственно, о том какие биты указателя можно использовать не по прямому назначению. Это самый простой пример использования знания о структуре указателя, есть и более интересные, причем не только в ядре ^[25].

Работу с индексными узлами мы начнем с расширения структуры super_operations ^[26], с которой мы познакомились в прошлый раз. Теперь мы заполним ее таким образом:

static struct super_operations const aufs_super_ops = {
	.alloc_inode = aufs_inode_alloc,
	.destroy_inode = aufs_inode_free,
	.put_super = aufs_put_super,
};

Мы добавили в нее еще пару указателей на функции aufs_inode_alloc и aufs_inode_free. Это специфичные функции для аллокации и освобождения inode, тут то мы и столкнемся с SLAB (с этим зверем мы, на самом, деле уже столкнулись в виде kmalloc) и RCU (совсем чуть-чуть).

Итак выделение памяти для индексного узла начнем с определения еще одной структуры — представления индексного узла в памяти (как это было с суперблоком):

struct aufs_inode
{
	struct inode	ai_inode;
	uint32_t	ai_block;
};

В этот раз мы будем использовать «наследование» вместо композиции. Наследование в C выглядит совсем не хитро (что не удивительно, учитывая, что в C нет поддержки наследования). Для этого мы просто делаем первым полем структуры aufs_inode базовую структуру (базовый класс) — структуру inode ^[27]. Таким образом указатель на aufs_inode можно использовать в качестве указателя на inode, как впрочем и наоборот (если конечно мы точно знаем, что данный указатель ссылается именно на aufs_inode).

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

Для выделения памяти под индексные узлы мы будем использовать SLAB аллокатор. SLAB аллокатор — кэширующий аллокатор, который позволяет выделять блоки памяти одного размера. Не трудно догадаться, что за счет этого ограничения можно упростить управление памятью и ускорить выделение памяти. SLAB аллокатор запрашивает у ОС большие куски памяти и выделяет из них небольшие участки по запросу, соответственно, запросы к менеджеру памяти ОС происходят реже, а запросы пользователей удовлетворяются быстрее.

Но изначально выигрыш в скорости выделения памяти при использовании SLAB-ов был не только (и не столько) за счет более простого управления памяти, а за счет сокращения расходов на инициализацию этой памяти. Действительно, SLAB аллокатор зачастую используется не просто для выделения объектов одного размера, а для выделения объектов одного типа, что позволяет пропустить инициализацию некоторых полей при повторном выделении одного участка памяти. Например, мьютексы, спинлоки и другие подобные объекты при освобождении объекта скорее всего имеют «правильное» значение, и при повторном выделении не нуждаются в повторной инициализации. За деталями и результатами измерений прошу обратиться к оригинальной статье ^[28].

На данный момент в Linux имеется три различных вида SLAB аллокаторов — SLAB, SLUB и SLOB. Не будем вдаваться в различия между ними, интерфейс они предоставляют один и тот же. Итак, для создания SLAB аллокатора мы будем использовать следующую функцию:

int aufs_inode_cache_create(void)
{
	aufs_inode_cache = kmem_cache_create("aufs_inode",
				sizeof(struct aufs_inode),
				0, (SLAB_RECLAIM_ACCOUNT|SLAB_MEM_SPREAD),
				aufs_inode_init_once);

	if (aufs_inode_cache == NULL)
		return -ENOMEM;

	return 0;
}

При создании SLAB-а функции kmem_cache_create ^[29] передаются имя, размер объекта, функция инициализации (функция, которая будет вызвана только один раз, при первом выделении объекта), и еще пара параметров, в суть которых я вдаваться не буду. Но чтобы не оставлять интересующихся совсем без информации я скажу, что создание SLAB-а для индексных узлов во всех файловых системах выглядит одинаково — различия не существенны.

Вызывать функцию aufs_inode_cache_create мы будем при загрузке модуля, перед регистрацией файловой системы в ядре. Есть так же парная функция, которую мы вызовем при выгрузке модуля:

void aufs_inode_cache_destroy(void)
{
	rcu_barrier();
	kmem_cache_destroy(aufs_inode_cache);
	aufs_inode_cache = NULL;
}

Функция kmem_cache_destroy ^[30] уничтожает SLAB аллокатор. К моменту уничтожения все объекты из этого кеша должны быть освобождены, иначе мы получим неприятное сообщение об ошибке в системном логе, вместе с целым букетом трудно отлавливаемых неприятностей.

Теперь обещанное касание RCU. В двух словах, RCU — распространенный в ядре механизм синхронизации (а также безопасного освобождения памяти для lock-free алгоритмов). RCU сам по себе заслуживает отдельной статьи и на хабре есть такая ^[31]. Более того, создатель этой техники, а по совместительству, мейнтейнер RCU в ядре Linux написал целую книгу ^[32], в которой коснулся и своего детища тоже.

Но нам из всего зоопарка RCU функций необходимо разобраться только с rcu_barrier ^[33] (как и с kfree, есть и другая реализация этой функции тут ^[34]). Если по-простому, то эта функция дождется, пока все отложенные работы над защищенными RCU данными завершатся, после чего вернет управление тому, кто ее вызвал, соответственно функция блокирующая. Зачем нам это нужно мы увидим чуть ниже.

Вернемся к выделению памяти, рассмотрим уже упомянутую выше функцию:

struct inode *aufs_inode_alloc(struct super_block *sb)
{
	struct aufs_inode *const i = (struct aufs_inode *)
				kmem_cache_alloc(aufs_inode_cache, GFP_KERNEL);

	if (!i)
		return NULL;

	return &i->ai_inode;
}

Она использует созданный ранее SLAB аллокатор (через одну из реализаций kmem_cache_alloc ^[35]) и возвращает указатель на inode — ничего необычного, а вот функция освобождения немного более интересная:

void aufs_inode_free(struct inode *inode)
{
	call_rcu(&inode->i_rcu, aufs_free_callback);
}

Тут мы опять сталкиваемся с RCU. Тут стоит сказать пару слов о lock-free алгоритмах, проблема таких алгоритмов в том, что без блокировок нет гарантий, что объект не используется параллельно каким-либо другим потоком исполнения, а значит освобождать память занятую этим объектом нельзя — другой поток может хранить указатель на него. Поэтому в lock-free алгоритмах приходится задумываться о стратегиях безопасного освобождения памяти, а RCU предоставляет средства для решения этой проблемы. Все реализации функции call_rcu ^[36] откладывают выполнение некоторой функции (в нашем случае функции освобождения aufs_free_callback) до тех пор, пока это не станет безопасным. А уже упомянутая выше rcu_barrier ждет завершения всех отложенных функций.

Вы устали? Ничего страшного, мы уже приближаемся к финалу. Теперь мы будем читать индексный узел с диска. Для этого я написал уже упомянутую функцию aufs_inode_get:

struct inode *aufs_inode_get(struct super_block *sb, uint32_t no)
{
	struct aufs_super_block const *const asb = AUFS_SB(sb);
	struct buffer_head *bh = NULL;
	struct aufs_disk_inode *di = NULL;
	struct aufs_inode *ai = NULL;
	struct inode *inode = NULL;
	uint32_t block = 0, offset = 0;

	inode = iget_locked(sb, no);
	if (!inode)
		return ERR_PTR(-ENOMEM);

	if (!(inode->i_state & I_NEW))
		return inode;

	ai = AUFS_INODE(inode);
	block = aufs_inode_block(asb, no);
	offset = aufs_inode_offset(asb, no);

	pr_debug("aufs reads inode %u from %u block with offset %un",
				(unsigned)no, (unsigned)block,
				(unsigned)offset);

	bh = sb_bread(sb, block);
	if (!bh)
	{
		pr_err("cannot read block %un", (unsigned)block);
		goto read_error;
	}

	di = (struct aufs_disk_inode *)(bh->b_data + offset);
	aufs_inode_fill(ai, di);
	brelse(bh);

	unlock_new_inode(inode);

	return inode;

read_error:
	pr_err("aufs cannot read inode %un", (unsigned)no);
	iget_failed(inode);

	return ERR_PTR(-EIO);
}

Объяснение я начну с простых моментов — функции AUFS_SB и AUFS_INODE позволяют получить указатель на структуры aufs_super_block и aufs_inode, через указатели на super_block и inode соответственно. Я не буду приводить их код (он довольно простой), потому что я уже описал выше как эти структуры связаны.

Функции aufs_inode_block и aufs_inode_offset позволяют получить номер блока и смещение внутри блока по номеру индексного узла — никакой магии, простая арифметика, так что останавливаться на них я тоже не буду.

А вот теперь интересный момент — пара функций iget_locked ^[37] и unlock_new_inode ^[38]. Как и в случае с блоками ядро поддерживает кеш inode-ов, это нужно не только для того, чтобы лишний раз не читать индексный узел с диска. Дело в том, что один и тот же файл/каталог может быть открыт сразу несколькими процессами, в этом случае все они должны оперировать одним экземпляром inode, чтобы их можно было синхронизировать друг с другом. Аналогичное рассуждение справедливо для блоков пожалуй даже в большей степени, так что к блока это тоже применимо.

Итак функция idet_locked в первую очередь ищет inode в кеше и выделяет память под новый, если inode не найден. Если индексный узел был выделен заново, а не найден в кеше, в поле i_state будет установлен флаг I_NEW, а также будет захвачен спинлок этого узла (поле i_lock). Поэтому наша функция сначала проверяет поле i_state, и если флаг I_NEW сброшен просто возвращаем кешированный inode. В противном случае мы должны заполнить inode, для этого мы читаем нужный блок с диска (с помощью уже известной вам sb_bread).

Функция aufs_inode_fill как раз и занимается заполнением:

static void aufs_inode_fill(struct aufs_inode *ai,
			struct aufs_disk_inode const *di)
{
	ai->ai_block = be32_to_cpu(di->di_first);
	ai->ai_inode.i_mode = be32_to_cpu(di->di_mode);
	ai->ai_inode.i_size = be32_to_cpu(di->di_size);
	ai->ai_inode.i_blocks = be32_to_cpu(di->di_blocks);
	ai->ai_inode.i_ctime.tv_sec = be64_to_cpu(di->di_ctime);
	ai->ai_inode.i_mtime.tv_sec = ai->ai_inode.i_atime.tv_sec =
				ai->ai_inode.i_ctime.tv_sec;
	ai->ai_inode.i_mtime.tv_nsec = ai->ai_inode.i_atime.tv_nsec =
				ai->ai_inode.i_ctime.tv_nsec = 0;
	i_uid_write(&ai->ai_inode, (uid_t)be32_to_cpu(di->di_uid));
	i_gid_write(&ai->ai_inode, (gid_t)be32_to_cpu(di->di_gid));
}

Опять никакой магии, за исключением пары функций i_uid_write ^[39] и i_gid_write ^[40]. Но и они не делают ничего особенного — просто присваивают значения соответствующим полям.

Кроме того обращу внимание на представление времени в виде структуры timespec ^[41], эта структура состоит всего из пары чисел — количество секунд и наносекунд. Т. е. потенциально время можно хранить довольно точно.

Наконец в самом конце функции мы должны освободить спинлок и вернуть указатель, для этого и используется функция unlock_new_inode.

Вместо заключения

Пост получился действительно большим и даже так не покрывает всех моментов. Я постарался объяснить все ключевые части реализации.

Все исходники доступны по ссылке ^[42]. В репозитории теперь две папки — kern и user. Как не трудно догадаться, одна хранит код нашего модуля, вторая — код утилиты для форматирования. Кода стало больше, а значит вероятность появления в нем ошибок стала больше — замечания, исправления, любая конструктивная критика и pull request-ы приветствуются.

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

dd bs=1M count=100 if=/dev/zero of=image
./mkfs.aufs ./image

Теперь можно использовать файл image так, как это показано в предыдущем посте.

Из примеров кода в этой статье убрано некоторое количество дебажного вывода, но если вы буде использовать код из репозитория, вы сможете убедиться, что модуль работает используя команду dmesg.

Автор: kmu1990

Источник ^[43]