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

Файловые операции Ext2

Файловые операции, специфичные для Ext2, перечислены в табл. 18.10. Как видно из таблицы, несколько методов виртуальной файловой системы реализованы функциями общего назначения, существующими во многих файловых системах. Адреса этих методов хранятся в таблице ext2_fiie operations.
Обратите внимание, что в Ext2 методы read и write реализованы, соответственно, функциями generic_file_read() И generic f ile write , которые ОПИ- саны в разд.

Управление пространством на диске в Ext2

Расположение файла на диске отличается от того, как файл представлен программисту. Принципиальных отличий два: блоки могут быть разбросаны по всему диску (хотя файловая система и делает все возможное, чтобы разместить файл в последовательных блоках, сократив тем самым время поиска), и файлы могут казаться больше, чем на самом деле, потому что программа может ВНОСИТЬ В НИХ дыры” (с ПОМОЩЬЮ системного вызова lseek ).
В этом разделе мы опишем, как файловая система Ext2 управляет дисковым пространством — как она выделяет и освобождает индексные дескрипторы и блоки. При этом ей приходится решать две основные проблемы:
- управление пространством диска должно происходить так, чтобы отсутствовала фрагментация файлов, т. е. физическое разбиение файлов на несколько небольших фрагментов, находящихся в несмежных блоках. Фрагментация увеличивает среднее время последовательных операций чтения файлов, поскольку магнитные головки должны часто менять положение по ходу операции . Эта проблема аналогична проблеме внешней фрагментации оперативной памяти
- управление дисковым пространством должно быть эффективно с точки зрения времени. Иными словами, ядро должно быть в состоянии быстро вычислить по смещению в файле номер логического блока в разделе Ext2. При этом должно быть минимизировано количество обращений к таблицам адресации, хранящимся на диске, поскольку каждое промежуточное обращение значительно увеличивает среднее время операции.

Создание индексных дескрипторов

Функция ext2_new_inode создает новый индексный дескриптор Ext2 и возвращает адрес соответствующего объекта (или null, если операция закончилась неудачей). Функция тщательно выбирает группу блоков для нового индексного дескриптора. Это делается для того, чтобы каталоги, не связанные друг с другом, были расположены в разных группах, и, в то же время, файлы находились в тех же группах, что их родительские каталоги. Чтобы сбалансировать количество обычных файлов и каталогов в одной группе блоков, в Ext2 было введено понятие долга” для каждой группы блоков.

Функция ext2_new_inode принимает два параметра: dir— адрес объекта индексный дескриптор”, ссылающегося на каталог, в который должен быть помещен новый индексный дескриптор, и mode — индикатор типа создаваемого индексного дескриптора. Второй параметр также содержит флаг монтирования ms synchronous который требует приостановки текущего процесса, пока не будет создан индексный дескриптор. Функция выполняет следующие действия:
1. Вызывает функцию new inode для выделения нового объекта, индексного дескриптора виртуальной файловой системы, инициализирует его поле i_sb адресом суперблока, хранящимся в поле dir->i_sb, а затем заносит новый объект в список используемых индексных дескрипторов и в список индексных дескрипторов, принадлежащих суперблоку
2. Если новый индексный дескриптор соответствует каталогу, функция вызывает функцию f ind group orlov , ЧТОбы наЙТИ ПОДХОДЯЩУЮ Группу блоков для этого каталога6. Вызванная функция реализует следующую эвристику:
• каталоги, родителем которых является корневой каталог файловой системы, должны быть распределены по всем группам блоков. Таким об
разом, функция ищет группу, у которой количество свободных индексных дескрипторов и количество свободных блоков выше среднего. Если такой группы не окажется, функция переходит на два шага вперед;
• вложенные каталоги (родитель которых — не корневой каталог) должны быть размещены в группе родителя, если она удовлетворяет следующим требованиям:
п группа не содержит слишком много каталогов;
п группа имеет достаточное количество свободных индексных дескрипторов;
п группа имеет небольшой долг” (величина долга” хранится в массиве счетчиков, на который указывает поле s debts дескриптора ext2_sb_info; долг увеличивается каждый раз, когда добавляется новый каталог, и уменьшается при добавлении файла другого типа);
Если группа родителя не удовлетворяет этим требованиям, функция выбирает первую группу, которая им удовлетворяет. Если такой группы нет, функция переходит к следующему шагу.
• если подходящую группу найти не удалось, применяется следующее правило для отступления”. Функция начинает поиск с группы блоков, содержащей родительский каталог, и останавливает свой выбор на первой группе, в которой количество свободных индексных дескрипторов превышает среднее по всем группам.
3. Если новый индексный дескриптор не соответствует каталогу, функция вызывает функцию f ind group other для размещения его в группе блоков, имеющей свободный индексный дескриптор. Вызванная функция выбирает группу, начиная просмотр с той, которая содержит родительский каталог, и двигаясь дальше. Более конкретно, она делает следующее:
• выполняет быстрый логарифмический поиск, начиная с группы блоков, содержащей родительский каталог dir. Алгоритм просматривает log(w) групп, где п — их общее количество. Алгоритм работает, пока не найдет подходящую группу блоков. Например, если i — номер группы, в которой начался поиск, то алгоритм просматривает группы с номерами i mod(w), /+1 mod(w), /+1+2 mod(w), /+1+2+4 mod(w) и т. д.;
• если логарифмический поиск не позволил найти группу со свободным индексным дескриптором, функция выполняет исчерпывающий линейный поиск, начиная с группы блоков, содержащей родительский каталог dir.
4. Вызывает функцию read_inode_bitmap , чтобы ПОЛУЧИТЬ битовую карту индексных дескрипторов выбранной группы блоков, и ищет в карте первый нулевой бит, получая номер первого свободного индексного дескриптора на диске.
5. Выделяет индексный дескриптор на диске: устанавливает соответствующий бит в карте индексных дескрипторов и помечает буфер, который ее содержит, как "грязный”. Кроме того, если файловая система была смонтирована с флагом ms synchronous функция вызывает функцию sync_dirty_ buffer , чтобы запустить операцию ввода/вывода, и ждет окончания пересылки данных.
6. Уменьшает поле bg_free_inodes_count дескриптора группы. Если новый индексный дескриптор соответствует каталогу, функция увеличивает поле bg used dirs count и помечает буфер, содержащий дескриптор группы, как грязный”.
7. Увеличивает или уменьшает счетчик группы в массиве s debts суперблока, в зависимости от того, ссылается индексный дескриптор на обычный файл или каталог.
8. Уменьшает поле s_freeinodes_counter структуры ext2_sb_info. Кроме ТОГО, если новый индексный дескриптор соответствует каталогу, функция увеличивает поле s_dirs_counter В структуре ext2_sb_info.
9. Устанавливает в единицу поле s dirt суперблока и помечает буфер, содержащий его, как грязный”.
10. Устанавливает в единицу поле s dirt суперблока и виртуальной файловой системы.
11. Инициализирует поля индексного дескриптора. В частности, устанавливает номер индексного дескриптора i_no и копирует значение
xtime. tv_sec В ПОЛе i_atime, i_mtime И i_ctime. Кроме ТОГО, Загружает В поле i block group Структуры ext2_inode_info Индекс группы блОКОВ
12. Инициализирует списки управления доступом, принадлежащего индексному дескриптору.
13. Заносит новый объект индексный дескриптор” в хеш-таблицу inode_ hashtable И ВЫЗЫВает фуНКЦИЮ markinodedirty о, чтобы перенести ИН- дексный дескриптор в список грязных” индексных дескрипторов суперблока
14. Вызывает функцию ext2_preread_inode , чтобы прочитать с диска блок, содержащий индексный дескриптор, и поместить этот блок в кэш стра
ниц. Этот вид опережающего чтения применяется, поскольку велика вероятность, что недавно созданный индексный дескриптор будет вскоре записан на диск.
15. Возвращает адрес нового объекта индексный дескриптор”.