Linux Kernel (Ядро линукса) (часть 3)

Адресация блоков данных

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

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

Предположим, например, что размер блока равен 4 Кбайт. Если меньше 4096, символ содержится в первом блоке данных файла, т. е. блоке номер 0. Если / больше или равно 4096 и меньше 8192, символ находится во втором блоке с номером 1 и т. д.

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

Следовательно, файловая система должна предоставить способ хранения соответствия между номером каждого блока в файле и логическим номером этого блока на диске. Это отображение, имеющееся уже в ранних версиях Unix от AT&T, реализовано частично внутри индексного дескриптора. Оно также применяет специализированные блоки, в которых содержатся дополнительные указатели, являющиеся расширением индексного дескриптора, используемым при работе с большими файлами.

Поле i biock индексного дескриптора на диске является массивом из EXT2 N BLOCKS элементов, содержащим логические номера блоков. Далее мы будем предполагать, что константа ext2_n_blocks имеет значение по умолчанию, а именно 15. Массив является первой частью большой структуры Как видно из рисунка, пятнадцать элементов массива имеют четыре различных типа:
- первые 12 элементов содержат логические номера, соответствующие первым 12 блокам файла, т. е. блокам с 0 по 11;
- элемент с индексом 12 содержит логический номер блока, называемого косвенным. Этот блок представляет массив второго эшелона, содержащий логические номера блоков. Они соответствуют номерам блоков в файле от 12 до Ы4+11, где Ъ — размер блока в файловой системе (каждый логический номер блока занимает 4 байта, отсюда деление на 4 в приведенной формуле). Следовательно, ядро должно искать в этом элементе указатель на блок, а в том блоке — еще один указатель на блок, который и содержит данные файла;
- элемент с индексом 13 содержит логический номер косвенного блока, в котором находится массив второго эшелона с логическими номерами блоков. В свою очередь, элементы этого массива являются указателями на массивы третьего эшелона, содержащие логические номера блоков, соответствующие номерам блоков в файле в диапазоне от 6/4+12 до (6/4)2+(6/4)+11;
- наконец, элемент с индексом 14, использует тройное косвенное указание. Массивы четвертого эшелона содержат логические номера, соответствующие номерам блоков в файле в диапазоне от (6/4)2+(6/4)+12 до (b/4f+(b/4f+(b/4)+l 1.
число внутри блока обозначает номер блока в файле. Стрелки, обозначающие логические номера блоков, хранящиеся в элементах массива, показывают, как ядро проходит по косвенным блокам, чтобы достичь блока, в котором содержатся данные файла.

Обратите внимание, насколько этот механизм благоприятен для небольших файлов. Если файлу требуется не более 12 блоков, любые его данные могут быть получены за два обращения к диску: одно для чтения элемента массива
1 biock индексного дескриптора на диске, а другое — для чтения запрошенного блока с данными. Для более длинных файлов может потребоваться три или даже четыре последовательных обращения к диску, чтобы получить нужный блок данных. На практике это оказывается самой пессимистичной оценкой, потому что кэши элементов каталога, индексных дескрипторов и страниц значительно уменьшают количество реальных обращений к диску.
Обратите также внимание на то, как размер блока в файловой системе влияет на механизм адресации. Большой размер блока позволяет файловой системе Ext2 хранить больше логических номеров блоков в одном блоке. Табл. 18.11 показывает верхний предел для размера файла при каждом размере блока и каждом режиме адресации. Например, если размер блока составляет 1024 байта, а файл содержит до 268 Кбайт данных, первые 12 Кбайт файла доступны при помощи прямой адресации, а остальные килобайты, с 13 по 268, могут быть адресованы с одним уровнем косвенности. Файлы больше
2 Гбайт в 32-битовой архитектуре следует открывать с установленным флагом О LARGEFILE.
Дыры в файлах
Дыра в файле — это часть обычного файла, которая содержит нулевые символы и не хранится ни в каком блоке на диске. Дыры являются давней особенностью файлов в Unix. Например, следующая команда Unix создает файл, в котором первые байты являются дырой:
$ echo -n "X" | dd of=/tmp/hole bs=1024 seek=6
Файл /tmp/hole содержит 6145 символов (6144 нулевых символа и символ "X"), однако, занимает он только один блок диска.
Дыры в файлах были введены, чтобы избежать непроизводительного расходования места на диске. Они активно используются приложениями, работающими с базами данных, и, вообще, всеми приложениями, выполняющими хеширование файлов.

Реализация дыр в файлах в Ext2 основана на динамическом выделении блоков: блок фактически назначается файлу, только когда процессу нужно произвести в него запись. Поле i size каждого индексного дескриптора определяет размер файла, видимый программе, включая дыры, в то время как поле i biocks хранит количество блоков, фактически выделенных файлу (измеренное в единицах по 512 байтов).

Вернувшись к примеру с командой dd, предположим, что файл /tmp/hole был создан в разделе Ext2, имеющем размер блока 4096. Поле i size индексного дескриптора на диске содержит число 6145, а поле i biocks — число 8 (поскольку блок в 4096 байтов содержит восемь 512-байтовых блоков). Второй элемент массива i biock (соответствующий блоку, имеющему в файле номер 1) содержит логический номер выделенного блока, а остальные элементы этого массива содержат нули