Способ выделения памяти для файлов - это способ, применяемый операционной системой для размещения данных в физической памяти. Ядро выделяет дисковую память для файлов и каталогов в виде логических блоков. Логический блок - это блок данных файла или каталога размером 512, 1024, 2048 или 4096 байт. Размер блока указывается при создании файловой системы JFS2. В действительности логические блоки не создаются на диске, однако для относящихся к ним данных выделяется дисковая память. Любой файл или каталог состоит из логических блоков.
Файл или каталог может занимать весь логический блок или только его часть. Логический блок может содержать 512, 1024, 2048 или 4096 байт данных, в зависимости от размера блока, указанного при создании файловой системы JFS2. Неполный логический блок образуется тогда, когда размер файла или каталога не кратен размеру блока.
Например, в файловой системе JFS2 с размером блока 4096 байт файл размером 8192 байта будет занимать два логических блока. В каждом из них будет содержаться 4096 байт данных. В то же время файл размером 4608 тоже будет состоять из двух логических блоков. При этом второй логический блок будет содержать лишь 512 байт данных файла. Неполным может быть только последний логический блок файла.
По умолчанию размер блока равен 4096 байтам. При создании файловой системы можно указать другой размер блока в команде mkfs. Допустимы блоки размером 512, 1024, 2048 и 4096 байт. Во всей файловой системе применяется единый размер блока. Дополнительная информация о структуре файловых систем приведена в разделе Структура файловой системы JFS.
Ядро выделяет дисковую память таким образом, что только последний блок данных файла будет заполнен не полностью. После заполнения этого блока будет выделен новый.
Перемещение фрагментов осуществляется также при добавлении данных в логический блок, соответствующий пустому пространству в файле. Пустое пространство в файле - это "пустой" логический блок, расположенный перед последним логическим блоком с данными. (В каталогах пустых пространств не бывает.) Пустые блоки не записываются на диск. Фрагменты для такого блока выделяются только при заполнении пустого пространства данными. Для логического блока, который ранее не был записан на диск, выделяется полный блок файловой системы.
При записи данных поверх старых данных файла или каталога дополнительные блоки не выделяются. Для логического блока, содержавшего эти данные, блоки файловой системы уже были выделены ранее.
Для размещения логических блоков файла или каталога JFS всегда пытается выделить непрерывную область дисковой памяти. Это позволяет сократить время поиска, так как данные файла или каталога размещаются в одной области памяти и их можно считывать последовательно. Это связано с тем, что область диска, смежная с одним из фрагментов, может быть уже занята другим файлом или каталогом.
Для хранения информации о состоянии фрагментов в файловой системе применяется битовая таблица, которая называется картой размещения блоков. С помощью этой карты файловая система ищет свободные блоки, которые могут быть выделены для размещения данных файла. В каждый момент времени блок может принадлежать только одному файлу или каталогу.
Область - это непрерывная последовательность блоков файловой системы, целиком выделенная объекту JFS2. Большие области могут находиться в нескольких группах размещения.
Каждый объект JFS2 представлен i-узлом. i-узлы содержат такую информацию, как даты, связанные с файлом, тип файла (обычный или каталог) и пр. Кроме того, они содержат двоичное дерево, описывающее расположение областей.
Файл состоит из последовательности областей. Каждая область - это непрерывная последовательность блоков файловой системы, целиком выделенная одному объекту. Области могут находиться в нескольких группах размещения. Для индексации областей применяется двоичное (B+) дерево.
Каждая область идентифицируется длиной и адресом. Длина измеряется в блоках файловой системы. Для хранения длины области отведено 24 разряда, поэтому длина области принимает значения от 1 до 224-1 блоков файловой системы. Таким образом, максимальный размер области зависит от размера блока файловой системы. Адрес области - это адрес первого блока области. Адрес также измеряется в блоках файловой системы от ее начала.
Файловая система, основанная на областях, в сочетании с пользовательским размером блока позволяет системе JFS2 не поддерживать отдельно внутреннюю фрагментацию. Пользователь может указать небольшой размер блока (например, 512 байт) для минимизации внутренней фрагментации при большом количестве небольших файлов.
Стратегия выделения памяти JFS2 в целом направлена на наиболее последовательное выделение памяти путем минимизации числа областей. Это увеличивает производительность за счет подсистемы ввода-вывода. Однако, размещение всех файлов в одном блоке не всегда возможно.
В этом разделе описана структура данных двоичного (B+) дерева, адаптированная для JFS2 и применяемая для описания размещения областей файлов.
Двоичные деревья были выбраны для увеличения производительности чтения и записи.
Описатель размещения областей (структура xad_t) описывает область и содержит для дополнительных поля: логическое смещение области в файле и поле флагов. Структура xad_t определена в файле /usr/include/j2/j2_xtree.h.
Структура xad описывает два абстрактных диапазона:
Физический диапазон и логический диапазон имеют одинаковую длину в байтах. Учтите, что смещение измеряется в блоках файловой системе; например, 3 означает 3 блока файловой системы, а на 3 байта. Области файла всегда выровнены по размеру блока файловой системы.
Для описания всех индексируемых объектов JFS, кроме каталогов, применяется одна и та же структура. Индексируемые данные зависят от объекта. Двоичное (B+) дерево индексировано по смещению xad данных, описанных в дереве. Записи отсортированы по смещению структур xad. Структура xad представляет собой запись в узле двоичного дерева.
В конце второго раздела i-узла диска находится описатель данных, в котором хранится тип содержимого второй половины i-узла. Для маленьких файлов вторая половина i-узла содержит сами данные файла. Если файл не помещается в область, выделенную для этого в i-узле, он будет размещен в областях диска, а i-узел будет содержать корневой узел двоичного дерева, описывающего размещение областей файла. Кроме того, заголовок содержит информацию о том, сколько записей xad занято и сколько свободно. Обычно i-узел содержит 8 структур xad для двоичного дерева. Если в файле не больше 8 областей, эти структуры будут описывать области (листья дерева). В противном случае они будут указывать на листья или внутренние узлы двоичного дерева.
После заполнения всех доступных структур xad i-узла двоичное дерево разделяется. Для каждого листа дерева выделяется 4 Кб дискового пространства. Лист дерева - это массив записей xad с заголовком. Заголовок указывает на первую свободную запись узла, все записи xad после этой записи также свободны. Восемь записей xad копируются из i-узла в лист, а в заголовок записывается адрес девятой записи в качестве первой свободной. Затем обновляется корень двоичного дерева - в первую структуру xad i-узла записывается адрес созданного листа. В качестве адреса используется смещение первой записи листа. Кроме того, в заголовке указывается, что для двоичного дерева занята только одна структура xad. Кроме того, в заголовке указывается, что i-узел содержит истинный корень двоичного дерева.
По мере добавления к файлу новых областей они будут добавляться в структуры лист в правильном порядке. Этот процесс будет продолжаться до заполнения листа. После этого выделяется еще 4 Кб дискового пространства и создается другой лист дерева. Вторая структура xad i-узла будет указывать на новый узел.
После заполнения всех восьми структур xad i-узла вновь потребуется разделение дерева. В этом случае будут созданы внутренние узлы двоичного дерева, применяемые только для перехода по дереву. Для этого будет выделено еще 4 Кб дискового пространства. Внутренние узлы дерева выглядят так же, как и листы. Восемь записей xad копируются из i-узла во внутренний узел, а в заголовок записывается адрес девятой записи в качестве первой свободной. Затем в первую структуру xad i-узла записывается адрес первой структуры внутреннего листа. Кроме того, в заголовке указывается, что для двоичного дерева занята только одна структура xad.
Заголовок корня двоичного дерева описан в файле /usr/include/j2/j2_xtree.h в структуре struct xtpage_t. Структура struct btpage_t в файле /usr/include/j2/j2_btree.h описывает заголовок внутреннего узла или листа.
Структура файловой системы JFS