Эта статья описывает структуру файловой системы XFS (disk-layout). Она написана «по горячим следам» после создания утилиты build_xfs для проекта anyfs-tools (http://anyfs-tools.sourceforge.net ).
Причиной написания этой статьи стало практически полное отсутствие описания структуры XFS не только на русском, но даже на английском есть только старые документы о дизайне XFS (довольно устаревшие), а также `man xfs_db` (помог разобраться в некоторых сложных моментах, с подсказки самого Nathan Scott'а). Ну и разумеется - исходные коды, точнее заголовки (к сожалению описания структур там довольно запутаны) .
Все они довольно разрознены и такого описания как в 16-ой главе книги
В.Костромина "Linux для пользователя":
http://www.linuxcenter.ru/lib/books/kostromin
по Ext2FS, по XFS не найти.
Эта статья не является полным описанием структуры XFS. Она описывает её лишь в той степени, которая мне была необходима для написания build_xfs. Таким образом останутся незатронутыми назначения real-time блоков, структура журнала, расширенные аттрибуты и многие другие поля в структурах, от понимания назначения, которых я сам всё ещё далёк.
Перед знакомством с этой статьёй желательно иметь некоторое представление о том как устроены Файловые Системы вообще и Ext2FS в частности.
Итак, передо мной лежат 9 листов рукописи структур данных XFS, а ниже я попробую привести это всё в хоть каком-то упорядоченном виде. Писать постараюсь по возможности живым языком, чтобы читать эту статью было не слишком скучно.
Сообщения об ошибках, поправки и пожелания по поводу этой статьи прошу направлять по адресу: undefer@gmail.com
Сжатый html:
http://www.lugr.ru/files/XFS-layout-ru.html.gz
PDF (сжатый gzip):
http://www.lugr.ru/files/XFS-layout-ru.pdf.gz
Latex оригинал:
http://www.lugr.ru/files/XFS-layout-ru-latex.tar.gz
Итак, вся файловая система делится на так называемые Группы Выделения (Allocation Groups или просто AG), аналог групп Блоков в Ext2FS.
Размер/количество и прочее описание Групп Выделения находится в суперблоке, а суперблок находится в начале каждой из Групп Выделения (т.е. здесь пока всё как и в Ext2FS), а потому сразу перейдём к описанию её структуры.
По меньшей мере первые 0x800 байт (2048 байт, 2 Кб) каждой Группы Выделения имеют совершенно одинаковый формат. Причём нулевая (будем считать всё от нуля) Группа Выделения (а вместе с ней и нулевой суперблок) располагается прямо в начале устройства. Здесь, важное отличие от абсолютного числа других Файловых Систем: когда ребятами из SGI проектировалась их файловая система XFS ещё для платформы IRIX, они и думать не думали ни о каких загрузчиках в начале диска, а потому даже не пытайтесь ставить загрузчик в раздел с XFS.
Группа Выделения делится на ещё четыре структуры:
Я бы мог привести цитату этого файла, как обычно это делается в таких случаях, но для описания структуры в данном случае это вовсе не удобно уже потому, что названия типов вроде xfs_drfsbno_t ничего не говорят об их размере.
А потому, я буду записывать структуры в формате, который был более удобен для меня. Надеюсь, он также будет удобен и для Вас.
Так я буду описывать структуры используя 5 полей:
Структура xfs_sb
{
0x00 32 sb_magicnum = "XFSB" /* магическое число */
0x04 32 sb_blocksize = 4096 /* размер блока */
0x08 64 sb_dblocks = 131072 /* блоков данных */
0x10 64 sb_rblocks = 0 /* realtime блоков */
0x18 64 sb_rextents = 0 /* realtime фрагментов */
0x20 128 sb_uuid /* уникальный
идентификатор ФС */
0x30 64 sb_logstart = 65540 /* начало внутреннего журнала */
0x38 64 sb_rootino = 128 /* корневой инф. узел */
0x40 64 sb_rbmino = 129 /* bitmap inode for
realtime extents */
0x48 64 sb_rsumino = 130 /* summary inode for
rt bitmap */
0x50 32 sb_rextsize = 16 /* realtime extent size,
blocks */
0x54 32 sb_agblocks = 16384 /* размер Группы Выделения */
0x58 32 sb_agcount = 8 /* число Групп Выделения */
0x5C 32 sb_rbmblocks = 0 /* number of rt bitmap blocks */
0x60 32 sb_logblocks = 1200 /* размер журнала в блоках */
0x64 16 sb_versionnum = 0x3084 /* header version ==
XFS_SB_VERSION */
0x66 16 sb_sectsize = 512 /* размер сектора устройства */
0x68 16 sb_inodesize = 256 /* размер инф.узла */
0x6A 16 sb_inopblock = 16 /* инф.узлов на блок */
0x6C 8x12 sb_fname[12] = "Белая_Метка" /* имя (метка) ФС */
0x78 8 sb_blocklog = 12 /* log_2(sb_blocksize) */
0x79 8 sb_sectlog = 9 /* log_2(sb_sectsize) */
0x7A 8 sb_inodelog = 8 /* log_2(sb_inodesize) */
0x7B 8 sb_inopblog = 4 /* log_2(sb_inopblock) */
0x7C 8 sb_agblklog = 14 /* log_2(sb_agblocks)
округлённый в сторону
увеличения */
0x7D 8 sb_rextslog = 0 /* log_2(sb_rextents) */
0x7E 8 sb_inprogress = 1 /* mkfs в прогрессе,
не монтировать */
0x7F 8 sb_imax_pct = 25 /* max % of fs for inode
space statistics */
0x80 64 sb_icount = 64 /* выделено инф. узлов */
0x88 64 sb_ifree = 61 /* свободно инф. узлов */
0x90 64 sb_fdblocks = 129840 /* свободно блоков данных */
0x98 64 sb_frextents = 0 /* free realtime extents */
0xA0 64 sb_uquotino = 0 /* user quota inode */
0xA8 64 sb_gquotino = 0 /* group quota inode */
0xB0 16 sb_qflags = 0 /* quota flags */
0xB2 8 sb_flags = 0 /* misc. flags */
0xB3 8 sb_shared_vn = 0 /* shared version number */
0xB4 32 sb_inoalignmt = 2 /* inode chunk alignment,
fsblocks */
0xB8 32 sb_unit = 0 /* stripe or raid unit */
0xBC 32 sb_width = 0 /* stripe or raid width */
0xC0 8 sb_dirblklog = 0 /* логарифм размера блока
директорий измеренного
в блоках ФС */
0xC1 8 sb_logsectlog = 0 /* ilog2 of the log
sector size */
0xC2 16 sb_logsectsize = 0 /* sector size for
the log, bytes */
0xC4 32 sb_logsunit = 0 /* stripe unit size
for the log */
0xC8 32 sb_features2 = 0 /* additional feature bits */
0xCC
}
Вторым же полем в суперблоке идёт размер блока (sb_blocksize). И я думаю не надо объяснять с каким смещением в файловой системе должен находится скажем блок 12. Правильно, в нашем случае, со смещением 12 x 4096.
Файловая система XFS любопытна тем, что такой же метод как для блоков применён и в отношении инф.узлов, т.е. номер инф.узла одновременно однозначно определяет и его местоположение в файловой системе. В связи с чем существуют поля размера инф.узла (0x68 sb_inodesize) и числа инф.узлов на блок (0x6A sb_inopblock). Таким образом размер инф.узла должен быть меньше размера блока в число раз являющемся степенью двойки.
В приведённом примере корневой узел имеет номер 128 (0x38 sb_rootino). Таким образом его смещение можно вычислить как 128 x 256.
Ещё одной особенностью такой нумерации инф.узлов является то, что существование инф.узла 128, вовсе не означает существование инф.узлов 0-127. В данном примере выделены инф.узлы 128-191, а других инф.узлов пока не существует, но когда заполняться эти свободные 61 инф.узел, могут быть выделены ещё 64 инф.узла. Впрочем, об этом - ниже.
Если, теперь, я попрошу Вас назвать смещение блока номер 16384, выходящем за пределы первой Группы Выделения, вы смело можете назвать 16384 x 4096 и.. не ошибётесь.
Однако, не спешите думать что всё так просто. Формула
<смещение блока> = <номер блока> x <размер блока> верна не всегда.
Обратите внимание на поле 0x7C sb_agblklog. Это логарифм
размера Группы Выделения. В нашем случае 2^14 = 16384 и всё
сходится. Но нам повезло потому, что размер образа (512 Мб)
есть степень двойки. В реальности файловая система редко имеет такой красивый
размер...
Пусть теперь у нас размер Группы Выделения равен 16000... Угадайте, какое смещение тогда имеет блок 16384? 16384 x 4096? А вот и нет - 16000 x 4096.
Дело всё в том, что поле sb_agblklog существует не просто так, оно действительно округляет размер Группы Выделения, и для Групп Выделения в 16000 блоков, sb_agblklog по-прежнему равно 14.
Таким образом номер блока равен:
(<номер Группы Выделения> << sb_agblklog) | <Номер блока в Группе Выделения>
Схематично:
Номер блока (52 бита):
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAANNNNNNNNNNNNNN
+------------------------------------++------------+
| |
+-- (52 - sb_agblklog) бит +-- (sb_agblklog) бит
номер Группы Выделения Номер блока
в Группе Выделения
Для номеров инф.узлов будет тоже самое с заменой sb_agblklog на ( sb_agblklog + sb_inopblog ).
Определение структуры xfs_agf находится в файле /usr/include/xfs/xfs_ag.h.
Структура xfs_agf
{
0x00 32 agf_magicnum = "XAGF" /* магическое число */
0x04 32 agf_versionnum = 1 /* версия agf-заголовка */
0x08 32 agf_seqno = 0 /* номер Группы Выделения */
0x0C 32 agf_length = 16384 /* размер Группы Выделения */
0x10 32 agf_roots[XFS_BNO] = 1 /* Корень Би-дерева свободных
фрагментов с сортировкой
по номеру */
0x14 32 agf_roots[XFS_CNUM] = 2 /* Корень Би-дерева свободных
фрагментов с сортировкой
по размеру */
0x18 32 agf_spare0 = 0 /* запас */
0x1C 32 agf_levels[XFS_BNO] = 1 /* Уровень Би-дерева свободных
фрагментов с сортировкой
по номеру */
0x20 32 agf_levels[XFS_CNUM] = 1 /* Уровень Би-дерева свободных
фрагментов с сортировкой
по размеру */
0x24 32 agf_spare1 = 0 /* запас */
0x28 32 agf_flfirst = 0 /* Первый элемент списка
зарезервированных
свободных блоков */
0x2C 32 agf_fllast = 3 /* Последний элемент списка
зарезервированных
свободных блоков */
0x30 32 agf_flcount = 4 /* Количество элементов в списке
зарезервированных
свободных блоков */
0x34 32 agf_freeblks = 16376 /* Свободных блоков */
0x38 32 agf_longest = 16376 /* Размер длиннейшего фрагмента
свободных блоков
в Группе Выделения*/
0x3C
}
Внимательный читатель уже должен заметить и загореться вопросом, и я поспешу ему ответить: Да! Действительно, ребята из SGI решили хранить список свободных блоков не в bitmap'е, а в Би-дереве с элементами "Начальный блок фрагмента свободных блоков"/"Размер фрагмента", да не в одном Би-дереве, а сразу в двух дублирующих: в одном элементы отсортированы по номеру начального блока фрагмента, а во втором - по размеру этих фрагментов свободного пространства.
Это позволяет быстро найти группу свободных блоков наиболее подходящего размера.
В примере структуры указано, что корни этих деревьев (элементы массива 0x10 agf_roots) находятся в блоках 1 и 2. Т.к. уровни деревьев (элементы массива 0x1C agf_levels) равны единице, то эти корни одновременно являются и листьями. А подробнее структура Би-дереьев будет описана ниже.
Список этих зарезервированных блоков располагается со смещением 0x600 в Группе Выделения. Он представляет из себя простой массив с элементами по 32 бита каждый.
В приведённом примере в этом массиве хранится 4 элемента (0x30 agf_flcount) с индексами от 0 (0x28 agf_flstart) до 3 (0x2C agf_fllast).
А, вот, собственно, пример этого списка:
AGFL
0x00 32 = 4
0x04 32 = 5
0x08 32 = 6
0x0C 32 = 7
0x10 32 = 0
0x14 32 = 0
...
Структура xfs_agi
{
0x00 32 agi_magicnum = "XAGI" /* магическое число */
0x04 32 agi_versionnum = 1 /* версия agi-заголовка */
0x08 32 agi_seqno = 0 /* номер Группы Выделения */
0x0C 32 agi_length = 16384 /* размер Группы Выделения */
0x10 32 agi_count = 64 /* число выделенных инф.узлов */
0x14 32 agi_root = 3 /* корень Би-дерева */
0x18 32 agi_level = 1 /* уровень Би-дерева */
0x1C 32 agi_freecount = 61 /* свободных инф.узлов */
0x20 32 agi_newino = 128 /* последний созданный
инф.узел */
0x24 32 agi_dirino = -1 /* last directory inode chunk */
/*
* Hash table of inodes which have been unlinked but are
* still being referenced.
*/
0x28 64x32 agi_unlinked[64]
0x128
}
Инф.узлы выделяются группами по 64 штуки. Информация о занятости/свободе инф.узлов такой группы хранится всё в том же bitmap'е (64-битном числе).
Но т.к. каждая следующая группа инф.узлов вовсе не обязательно располагается за предыдущей, то эту информацию всё равно приходится хранить в Би-дереве.
Такая схема позволяет снять ограничение на количество инф.узлов присущее многим другим файловым системам. На XFS сообщение "Не достаточно места" однозначно, оно не может означать "Таблица инф.узлов переполнена" при создании файла.
Подробнее о всех Би-деревьях в следующем разделе.
Итак, Би-деревья.. Если быть точнее B+-tree:
http://en.wikipedia.org/wiki/B+_tree
Ну, ладно, ладно.. Не буду вас отправлять на английскую Википедию.. Скажу пару слов по-русски.
Итак, кратко, Би-деревья - это деревья, в которых ключи объединяются в блоки по несколько штук, что значительно позволяет увеличить их эффективность на дисковых носителях.
Свойства B+-деревьев:
Примерно так... Хотя очень не точно, но относительно XFS всё вышесказанное верно...
Структура xfs_btree_sblock | xfs_btree_lblock
{
0x00 32 bb_magic /* магическое число */
0x04 16 bb_level /* уровень блока. 0 -- для листьев. */
0x06 16 bb_numrecs /* число записей */
0x08 32|64 bb_leftsib /* указатель на брата
по уровню слева (или -1) */
0x0C|10 32|64 bb_rightsib /* указатель на брата
по уровню справа (или -1) */
0x10|18
}
Да, чтобы описать две структуры одной схемой нам пришлось немного «смухлевать», но как видите они отличаются лишь размером ссылок на братьев (32 или 64 бит).
Само собой заголовок это ещё не весь блок. Основные данные следуют далее.
Для листьев всё просто: сразу же за полем bb_rightsib следует массив записей (фиксированного размера) в количестве bb_numrecs штук.
Для узлов же всё несколько сложнее. Записи здесь разделены на две части: ключ и указатель на блок более нижнего уровня (на подветку) отвечающего этой записи.
При этом ключ и указатель в общем случае имеют разный размер. И главное - ключ и указатель хранятся в раздельных массивах. Если массив ключей начинается сразу же за полем bb_rightsib, то откуда начинается массив указателей одному ...мда... известны..
Чтобы стать этим ...мда..., которому всё известно, нужно:
Далее, для каждого из Би-деревьев будем описывать
Тут, Вы, вероятно, спросите: а как же 64-х битность XFS, если здесь ссылки могут быть 32-х битными? Всё просто - 32-х битные ссылки используются для Би-деревьев свободных блоков и инф.узлов, которые привязаны к своей Группе Выделения, и, соответственно, это ссылки относительно Группы Выделения, а размер Группы Выделения (в блоках) - это 32-х битное число.
Записи листьев и ключи узлов у Би-деревьев свободных блоков имеют одну и
ту же структуру
xfs_alloc_rec (файл /usr/include/xfs/xfs_alloc_btree.h)
Структура xfs_alloc_rec
{
0x00 32 ar_startblock /* Начальный блок фрагмента
свободного пространства */
0x04 32 ar_blockcount /* Размер фрагмента свободного
пространства в блоках */
0x08
}
Однако, ключи узлов Би-деревьев с сортировкой по размеру фрагментов
имеют перевёрнутую структуру:
{
0x00 32 ar_blockcount /* Размер фрагмента свободного
пространства в блоках */
0x04 32 ar_startblock /* Начальный блок фрагмента
свободного пространства */
0x08
}
Остаётся только удивляться почему же записи листьев в таком случае у них
всё равно имеют прямую структуру...
Записи листьев описываются структурой xfs_inobt_rec (файл /usr/include/xfs/pwd).
Структура xfs_inobt_rec
{
0x00 32 ir_startino /* Начальный инф.узел описываемый
записью */
0x04 32 ir_freecount /* Число свободных инф.узлов */
0x08 64 it_free /* Битовая карта инф.узлов.
1 -- значит свободен */
0x10
}
В структуре задан начальный инф.узел, описываемый записью. При этом количество
этих инф.узлов всегда одно - 64.
Стоит отметить также, что в поле ir_freecount, из 32 бит, в действительности, используется только 7 (1000000b = 64d). Но создатели XFS не стали жадничать - всё для выравнивания!
Ключом в данных деревьях является единственное значение:
Ключ узлов Би-деревьев свободных и выделенных инф.узлов
{
0x00 32 startino /* Начальный инф.узел описываемый
записью */
0x04
}
Записи листьев - структура xfs_bmbt_rec_32
(файл /usr/include/xfs/xfs_bmap_btree.h)
Структура xfs_bmbt_rec_32
{
0x00 32 l0
0x04 32 l1
0x08 32 l2
0x0C 32 l3
0x10
}
Не правда ли забавная структура? И безликая...
Реальное объяснение всего этого безобразия (иначе, я просто не могу это назвать) будет дано в пункте «Карта блоков» следующего раздела.
Ключом в Би-деревьях карты блоков является также единственное значение:
Ключ узлов Би-деревьев карты блоков
{
0x00 64 startoff /* Смещение фрагмента от начала
файла (в блоках) */
0x08
}
Структура инф.узлов делится на две части: общая для всех (ядро инф.узла) и зависимая от типа.
Ядро инф.узла - это структура xfs_dinode_core
(файл /usr/include/xfs/xfs_dinode.h).
Структура xfs_dinode_core
{
0x00 16 di_magic = "IN" /* Магическое число */
0x02 16 di_mode = 0x41ED /* тип и режим доступа */
0x04 8 di_version = 1 /* версия структуры */
0x05 8 di_format = 1 /* формат второй части
инф.узла */
0x06 16 di_onlink = 4 /* число ссылок (старое -
16-ти битное) */
0x08 32 di_uid /* UID (идентификатор
пользователя) */
0x0C 32 di_gid /* GID (идентификатор группы) */
0x10 32 di_nlink = 4 /* Число ссылок */
0x14 16 di_projid = 0 /* owner's project id */
0x16 8x8 di_pad[8] = 0 /* запас на будущее */
0x1E 16 di_flushiter = 14 /* incremented on flush */
0x20 64 di_atime /* последнее время доступа
(до миллисекунд) */
0x28 64 di_mtime /* последнее время изменения
(до миллисекунд) */
0x30 64 di_ctime /* время создания/модификации
инф.узла (до миллисекунд) */
0x38 64 di_size = 28 /* размер файла в байтах */
0x40 64 di_nblocks = 0 /* число блоков */
0x48 32 di_extsize /* basic/minimum extent
size for file */
0x4C 32 di_nextents /* число фрагментов */
0x50 16 di_anextents /* number of extents
in attribute fork */
0x52 8 di_forkoff /* attr fork offs, <<3 for
64b align */
0x53 8 di_aformat /* format of attr fork's data */
0x54 32 di_dmevmask /* DMIG event mask */
0x58 16 di_dmstate /* DMIG state info */
0x5A 16 di_flags /* random flags,
XFS_DIFLAG_... */
0x5C 32 di_gen /* generation number */
0x60
}
В основном данные предоставляемые этой структурой совпадают с данными структуры stat выдаваемой соотсветсвующим системным вызовом, что не удивительно.
Однако, нас сейчас более всего интересует формат второй части инф.узла.
Обратимся к структуре xfs_dinode (файл тот же):
Структура xfs_dinode
{
0x00 3072 di_core /* ядро инф.узла
(см. структуру выше) */
0x60 32 di_next_unlinked = -1 /* agi unlinked list ptr */
0x64 xx di_u
0x64+xx yy di_a
0x64+xx+yy
}
Так, за ядром следует некоторый указатель, который в отмонтированном состоянии
похоже всегда будет равен -1.
Далее следуют два union'а. Второй из них - описывает расширенные аттрибуты. Однако, мы не будем их рассматривать и тогда окажется что размер элемента di_a равен нулю.
Мы лучше сосредоточим своё внимание на элемент di_u - это собственно та вторая часть инф.узла которая нас более всего интересует сейчас. Её формат зависит от значения элемента di_format структуры xfs_dinode_core, рассмотренной чуть выше. Значения di_format описываются перечислением (enum'ом) xfs_dinode_fmt (файл всё тот же - /usr/include/xfs/xfs_dinode.h):
Значения для di_format
{
00 = XFS_DINODE_FMT_DEV, /* специальный файл (устройство) */
01 = XFS_DINODE_FMT_LOCAL, /* директория короткого формата
или символическая ссылка */
02 = XFS_DINODE_FMT_EXTENTS, /* карта блоков (для директорий,
простых файлов и симв.ссылок) */
03 = XFS_DINODE_FMT_BTREE, /* Би-дерево карты блоков (для
директорий и простых файлов) */
04 = XFS_DINODE_FMT_UUID /* MNT: di_uuid */
}
Значение di_format = XFS_DINODE_FMT_DEV предназначено для специальных файлов.
Специальные файлы описываются 32-х битным числом типа xfs_dev_t. Оно похоже на используемый в ядре Linux kdev_t. Но если там MINOR число имеет 20 бит, то в XFS - 18.
Надо сказать, что этот формат явно имеет исторические причины, и даже макрос-конструктор xfs_dev_t из MAJOR и MINOR-чисел имеет название IRIX_MKDEV.
Значение di_format = XFS_DINODE_FMT_LOCAL означает, что сам инф.узел находится прямо в хвосте его описания (со смещением 0x64).
Это применимо для символических ссылок и коротких директорий.
Тут стоит сказать об одном странном ограничении XFS: длина символических ссылок здесь не должна превышать (так же как имя файла) 255 символов. Если для имени файла такое ограничение вполне понятно, то о причинах такого же ограничения для символических ссылок остаётся только догадываться. В Ext2FS длина символической ссылки в свою очередь ограничена размером блока. (т.е. обычно это 4096 или 4095 символов)
Значение di_format = XFS_DINODE_FMT_EXTENTS означает, что в хвосте описания инф.узла находится карта блоков.
Карта блоков - это массив значений по 128 бит каждое, описывающих один фрагмент (extent) инф.узла (директории, симв.ссылки или простого файла).
Тут настаёт время объяснения той безликой структуры данной в разделе «Би-деревья карты блоков». 80 символов ширины - конечно, узко. Но мы попробуем уложиться (не забываем, что все данные в XFS находятся в Big-Endian формате):
31.30..........0 31........9.8..0 31.............0 31..21.20......0
LLLLLLLLLLLLLLL0 LLLLLLLLLLLLLLL1 LLLLLLLLLLLLLLL2 LLLLLLLLLLLLLLL3
++ +------------ ----------+ +--- ---------------- -----+ +-------+
| | | |
| +-- startoff (54 бита) +-- startblock (52 бита) +-- blockcount (21 бит)
| Смещение фрагмента Номер блока первого число блоков в
| в блоках от начала блока фрагмента фрагменте
| файла на диске.
|
+-- extent flag (1 бит)
Можете не сомневаться - что изображено на этом рисунке его автору совершенно ясно. Очень надеюсь, что уважаемый читатель тоже не слишком избалован качеством графических материалов, предоставляемых современным издательством, и он ещё способен ориентироваться в таких псевдографических рисунках.
Да, почему-то создатели пожадничали ещё 32 бита для этой структуры. О причинах этого нам опять же остаётся только догадываться (возможно, всё опять же для выравнивания).
А XFS, благодаря избыточности информации даваемой полем startoff, получает возможность вообще не хранить информацию о так называемых щелях (holes) в файлах.
Т.е. если есть фрагмент с startoff = 14 и blockcount = 5, вовсе не обязательно чтобы следующий фрагмент имел startfoff = 19. Может быть и больше (но, разумеется, не меньше).
Значение di_format = XFS_DINODE_FMT_BTREE означает, что в хвосте описания инф.узла находится корень Би-дерева карты блоков.
Би-деревья описаны в разделе выше, но здесь для этого корня мы имеем сокращённый формат - из структуры xfs_btree_sblock исключается магическое число (смысла в нём в середине блока мало) и ссылки на братьев (у корня нет братьев). Остаётся (смещение указано от начала описания инф.узла):
Сокращённая структура xfs_btree_sblock
{
0x64 16 bb_level /* уровень блока. 0 -- для листьев. */
0x66 16 bb_numrecs /* число записей */
0x68
}
Можно отметить, что уровень этого корня (высота Би-дерева) никогда не может быть нулевым - для этого есть di_format = XFS_DINODE_FMT_EXTENTS.
Вы, вероятно, уже обратили внимание на уровень вложенности содержания этого пункта..
Ну, так начнём наш сказ...
Короткий формат - тот самый, что используется в конце описания инф.узла, когда di_format = XFS_DINODE_FMT_LOCAL.
Директория в этом случае имеет структуру xfs_dir2_sf (файл /usr/include/xfs/xfs_dir2_sf.h):
Структура xfs_dir2_sf
{
0x64 48|80 hdr /* заголовок */
0x6A|0x6C ~~ list[count] /* элементы директории */
0x~~
}
Заголовок - это структура xfs_dir2_sf_hdr (файл тот же):
Структура xfs_dir2_sf_hdr
{
0x64 8 count /* число элементов */
0x65 8 i8count /* число элементов с
8-ми байтными номерами */
0x66 32|64 parent /* родительский инф.узел */
0x6A|0x6C
}
Элементы имеют структуру xfs_dir2_sf_entry (файл всё тот же):
Структура xfs_dir2_sf_entry
{
0x00 8 namelen /* длина имени */
0x01 16 offset /* сдвиг в одноблочной директории,
кратно восьми (см. ниже) */
0x03 8xlen name[len] /* имя файла */
0x03+len 32|64 inumber /* инф.узел */
}
В директории в коротком формате не упоминаются элементы '.' и '..'. Но вместо элемента '..' вводится поле parent.
Обратим Ваше внимание на ссылки parent и inumber - несмотря на неоднозначность их размера указанную в структурах, вы можете смело считать их 32-хбитными. Однако, привет счастливым обладателям Терабайтовых файловых систем - если хотя бы один элемент директории или её родитель - является инф.узлом с номером, который не укладывается в 32 бита, то все эти ссылки разом становятся 64-х битными, а драйвер файловой системы узнает об этом по ненулевому значению i8count.
Итак, это только присказка, сказка - впереди. Короткий формат - для коротких директорий. А что же делать с длинными? А об этом поведует следующий раздел.
Блоки директорий в XFS - это не совсем блоки файловой системы. Они могут быть больше, о чём будет свидетельствовать не нулевое значение элемента 0xC0 sb_dirblklog в суперблоке.
Смещение полей следующих структур имеет смысл привязывать не только к началу блока, но и к его концу. Так договоримся, считать что 0x00 - это начало блока, 0x08 - 8 байт от начала блока, 2x00 - конец блока, 1xF8 - 8 байт от конца блока.
Структура одноблочной директории xfs_dir2_block описана в файле /usr/include/xfs/xfs_dir2_block.h:
Структура xfs_dir2_block
{
0x00 128 hdr /* заголовок */
0x10 ~~ u[count] /* элементы директории */
1xF8-8xN 64xN leaf[count] /* отсортированный по ключу хэш */
1xF8 64 tail /* хвост, где указано число элементов */
2x00
}
Последующее описание структуры возможно имело бы смысл начать с конца (я подозреваю что драйвер файловой системы просматривает её именно так), тем не менее мы не будем переворачивать всё с ног на голову.. Пойдём попорядку.
Заголовок - структура xfs_dir2_data_hdr (файл /usr/include/xfs/xfs_dir2_data.h).
Структура xfs_dir2_data_hdr
{
0x00 32 magic = "XD2B" /* число элементов */
0x04 32x3 bestfree[3] /* лучшие свободные подблоки */
0x10
}
Где элементы массива bestfree имеют структуру xfs_dir2_data_free (файл тот же):
Структура xfs_dir2_data_free
{
0x00 16 offset /* смещение подблока с начала блока
(кратно восьми) */
0x02 16 length /* длина в байтах */
0x04
}
Тут уважаемый читатель, вероятно, пришёл в некоторое замешательство: «что это за подблоки такие?». Всё дело в том, что длина имён файлов всех разная (IRIX - вам не DOS), также как и длина файлов. И по тем же причинам (я надеюсь, Вы прекрасно все эти причины знаете и понимаете), по которым диск стали делить на блоки, блоки директорий создатели XFS решили разделить на подблоки.
Подблок - это 8 байт. Также, как блоки в файловой системе, подблоки могут быть свободными или занятыми. Существует фрагментация свободного пространства подблоков (но разумеется не самих записей). А так как создатели XFS очень заботяться о возможности быстро находить свободный фрагмент нужного размера, то здесь помещены эти записи bestfree.
Надеюсь, вы теперь также прекрасно понимаете почему offset кратен восьми.
Перейдём теперь непосредственно к этим подблокам:
В группе подблоков хранится union xfs_dir2_data_union_t (файл всё ещё /usr/include/xfs/xfs_dir2_data.h):
typedef union {
xfs_dir2_data_entry_t entry;
xfs_dir2_data_unused_t unused;
} xfs_dir2_data_union_t;
entry при этом описывает элемент директории, а unused - группу свободных подблоков. Разумеется, вы никогда не встретите в массиве u структуры xfs_dir2_block, две unused записи подряд (т.к. они должны быть сразу объединены).
Итак, элемент директории описывается структурой xfs_dir2_data_entry
(файл всё тот же):
Структура xfs_dir2_data_entry
{
0x00 64 inumber /* инф.узел */
0x08 8 namelen /* длина имени */
0x09 8xlen name[len] /* имя */
~~ /* пробел для выравнивания размера до
окончания подблока */
1xFE 16 tag /* смещение этого элемента от начала
блока (кратно 8-ми) */
2x00
Группа свободных подблоков описывается структурой xfs_dir2_data_unused
(тот же файл):
Структура xfs_dir2_data_unused
{
0x00 16 freetag = 0xFFFF /* инф.узел */
0x02 16 length /* длина имени */
~~ /* пробел для выравнивания размера до
окончания группы подблоков */
1xFE 16 tag /* смещение структуры от начала
блока (кратно 8-ми) */
2x00
В этих двух структурах 2x00 - размер структуры, который кратен восьми.
Теперь должно быть уже понятно, что за offset был в короткой форме директории.
В одноблочной директории уже присутствуют элементы '.' и '..'.
В конце блока следует хэш элементов директории. Хэш-функция - это функция libxfs_da_hashname(<строка>, <длина строки>);
Что она из себя представляет меня интересовало слабо - мне вполне хватило возможности её вызова, а потому мы сразу перейдём к описанию структуры элементов массива хэша. Структуры xfs_dir2_leaf_entry (файл /usr/include/xfs/xfs_dir2_leaf.h):
Структура xfs_dir2_leaf_entry
{
0x00 32 hashval /* ключ */
0x04 32 address /* смещение элемента от начала
блока (разделено на 8!) */
0x08
Т.е. каждый такой элемент состоит из значения хэша и указателя в виде номера подблока.
Каждый такой элемент хэша сам занимает один подблок. Элементы в массиве отсортированы по возрастанию хэша.
Это структура xfs_dir2_block_tail (файл /usr/include/xfs/xfs_dir2_block.h):
Структура xfs_dir2_leaf_entry
{
0x00 32 count /* число элементов в директории */
0x04 32 stale /* count of stale lf entries */
0x08
Смысла элемента stale к сожалению мною найдено не было (всегда ноль?).
Если директория не помещается в один блок, то он разделяется на несколько следующим способом...
Итак, во-первых, из одноблочной директории исключается хэш. Полученная структура (блок данных директории) xfs_dir2_data (файл /usr/include/xfs/xfs_dir2_data.h) также занимает целый блок, но в отличии от блока одноблочной директории, в многоблочной директории блоков данных может быть несколько:
Структура xfs_dir2_data
{
0x00 128 hdr /* заголовок */
0x10 ~~ u[count] /* элементы директории */
2x00
}
Заголовок здесь - та же структура xfs_dir2_data_hdr (см. выше), но с магическим числом magic = ''XD2D''.
Хэш же выделяется в отдельный блок - структуру xfs_dir2_leaf (файл /usr/include/xfs/xfs_dir2_leaf.h):
Структура xfs_dir2_leaf
{
0x00 128 hdr /* заголовок */
0x10 64xN ents[count] /* хэш всех элементов директории */
1xFC-2xN 16xM bests[blockcount] /* длины лучших свободных подблоков
каждого из блоков данных */
1xFC 32 tail = blockcount /* число блоков данных */
2x00
}
Формат элемента хэша (структура xfs_dir2_leaf_entry) уже была описана выше.
Элементы bests - это фактически максимум из трёх значений bestfree[3] соответсвующего блока данных.
Ну, а tail - это смешная структура xfs_dir2_leaf_tail
с единственным элементом:
Структура xfs_dir2_leaf
{
0x00 32 bestcount /* число блоков данных */
0x04
}
Действительно интересен здесь заголовок..
Итак, заголовок структуры выше - это структура xfs_dir2_leaf_hdr (файл тот же):
Структура xfs_dir2_leaf_hdr
{
0x00 96 info /* заголовок узла Би-дерева хэша */
0x0C 16 count /* число элементов в блоке хэша */
0x0E 16 stale /* count of stale entries */
0x10
}
Где заголовок узла Би-дерева хэша это структура xfs_da_blkinfo (файл /usr/include/xfs/xfs_da_btree.h):
Структура xfs_da_blkinfo
{
0x00 32 forw /* ссылка на брата справа */
0x04 32 back /* ссылка на брата слева */
0x08 16 magic = 0xd2f1 /* магическое число */
0x0A 16 pad /* для выравнивания */
0x0C
}
Указатели forw и back здесь пока равны -1.
Таким образом мы описали одноблочных хэш директории, но он может быть использован в директории лишь единожды, если же в один блок хэш не помещается то он уже превращается в полноценное Би-дерево следующим образом...
Из одноблочного хэша исключается список лучших свободных подблоков в блоках данных. И остаётся блок хэша - структура вида:
Структура блока хэша
{
0x00 128 hdr /* заголовок */
0x10 64xN ents[count] /* хэш части элементов директории */
2x00
}
Да, для массива bests[] здесь тоже выделяется отдельный блок. Это структура xfs_dir2_free (файл /usr/include/xfs/xfs_dir2_node.h):
Структура xfs_dir2_free
{
0x00 128 hdr /* заголовок */
0x10 16xN bests[nused] /* размер лучших свободных подблоков
блоков данных */
2x00
}
Где заголовок - это структура xfs_dir2_free_hdr (файл тот же):
Структура xfs_dir2_fre_hdr
{
0x00 32 magic = "XD2F" /* заголовок */
0x04 32 firstdb /* номер первого блока данных
описанного в этом блоке */
0x08 32 nvalid /* число описанных блоков данных
в этом блоке */
0x0C 32 nused /* похоже, всегда равно nvalid */
0x10
}
Таким образом таких блоков в одной директории тоже может быть несколько (при этом в каждом таком блоке поле firstdb равно сумме nvalid всех предыдущих блоков).
Очень важная вещь, о которой, до сих пор не было сказано, но далее мы уже без этого не обойдёмся..
Итак, до сих пор мы не упомянули, где же находятся ссылки на номера блоков директории. Но, вероятно, Вы уже догадались - карты блоков директорий уже упоминались. Они точно такие же как и у простых файлов, с одним большим НО - адресация.
Если у файла совершенно ясно что такое 0-ой байт, 5-ый, 10-ый.. То у директории с этим некоторый напряг..
Хорошо, пусть блоки данных мы уложим попорядку и соответсвующим образом проадресуем, но как же блоки хэша и блоки лучших свободных подблоков?
Тут разработчики XFS, чтобы уже по адресу можно было понять является ли блок блоком данных, хэша или блоком лучших свободных подблоков решили разделить адресное пространство директорий на соответсвенно три части (по 32 Гб):
Но это в байтах - не забывайте, что в карте блоков всё указывается в блоках (и не в блоках директорий, а в блоках файловой системы).
Итак, структура блока многоблочного хэша уже описана, тут нам остаётся только уточнить, что магическое число для узлов этого Би-дерева hdr.info.magic = 0xfebe.
А ссылки hdr.info.forw и hdr.info.back на братьев по уровню - это номера соответсвующих блоков, но в адресном пространстве директории (см. выше), т.е. номер блока файловой системы драйвер при этом получает обратившись к карте блоков.
В хэше узлов в качестве ключа указывается значение ключа самого последнего из всех его дочерних элементов.
В качестве адреса - номер дочернего блока в адресном пространстве директории.
Магическое число для листьев Би-дерева хэша hdr.info.magic = 0xd2ff.
Ссылки на братьев по уровню - снова номера блоков в адресном пространстве директории.
Ключи в хэше - хэш имени соответвующего элемента директории.
Адрес - номер подблока соответвующего элемента директории, т.е. адрес элемента директории в адресном пространстве директории делённый на 8.
Всё!
This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.70)
Copyright © 1993, 1994, 1995, 1996,
Nikos Drakos,
Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999,
Ross Moore,
Mathematics Department, Macquarie University, Sydney.
The command line arguments were:
latex2html -html_version 4.0 -auto_link -toc_depth 7 -nonavigation -split 0 XFS.tex
The translation was initiated by unDEFER on 2006-08-19