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) содержит логический номер выделенного блока, а остальные элементы этого массива содержат нули

Предыдущая страница | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 | Следующая страница




Возможно, Вас также заинтересует:

ОС Knoppix - это Linux без про...

ВведениеЕсли вы цените свое время, умеете считать деньги и знаете стоимость информации, то эта книга...

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

Спин-блокировкаСпин-блокировка необходима в многопроцессорной системе, потому что могут возникнуть...

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

Копирование при записи В системах Unix первых поколений создание процесса было реализовано довольно...

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

Буферы блоков и головы буферовУ каждого буфера есть дескриптор голова буфера, имеющий тип buffer...