Примечание. Авторы рекомендуют читать книгу вместе с исходным текстом xv6. Авторы подготовили и лабораторные работы по xv6.

Xv6 работает на RISC-V, поэтому для его сборки нужны RISC-V версии инструментов: QEMU 5.1+, GDB 8.3+, GCC, и Binutils. Инструкция поможет поставить инструменты.

Файловая система организует и хранит данные. Пользователи и программы работают с данными, а файловая система сохранит данные даже после перезагрузки компьютера.

Файловая система xv6 предлагает Unix-подобные файлы, директории и пути и хранит данные на virtio-диске. Файловая система решает такие задачи:

• Определяет структуры данных, чтобы хранить директории, файлы, части файлов в блоках диска и запоминать свободные области диска. Файловая система назначает имена файлам и директориям.

• Восстанавливается после сбоев. Сбой питания компьютера повредит файловую систему, если произойдет во время записи на диск.

• Упорядочивает работу параллельных процессов - соблюдает инварианты с помощью блокировок.

• Кеширует блоки диска в оперативной памяти. Диск работает на порядки медленнее памяти.

Глава расскажет, как xv6 решает эти задачи.

Обзор файловой системы

Файловая система состоит из 7 уровней, как показывает рисунок.

• Уровень диска читает и пишет блоки на virtio-диске.

• Кеш блоков хранит копии блоков диска в памяти и упорядочивает работу процессов с блоками так, что процессы пишут в один и тот же блок по очереди.

• Журнал объединяет операции записи блоков в транзакции и выполняет транзакции атомарно, чтобы защититься от сбоев.

• Уровень inode работает с файлами. Каждый inode описывает отдельный файл - содержит уникальный номер и набор блоков содержимого файла.

• Уровень директорий работает с директориями. Директория - inode, который хранит ссылки на другие файлы и директории. Каждая запись в директории содержит имя и номер inode, на который ссылается.

• Уровень путей предлагает иерархию имен вида /usr/rtm/xv6/fs.c и рекурсивный поиск по иерархии.

• Уровень файловых дескрипторов представляет системные ресурсы - каналы, устройства, сетевые соединения - как файлы и облегчает программисту жизнь.

Диск разбит на секторы - блоки по 512 байтов. Секторы диска последовательно пронумерованы - сектор 0 содержит первые 512 байтов диска, сектор 1 - следующие 512 байтов и т.д. Размер блока файловой системы не обязан совпадать с размером сектора, но часто размер блока кратен размеру сектора.

Xv6 копирует блоки диска в память и хранит в буфере типа struct buf. Содержимое буфера в памяти не совпадает с содержимым блока на диске, когда:

• Ядро еще не скопировало блок с диска.

• Процесс изменил содержимое буфера, но ядро еще не записало блок на диск.

Файловая система решает, где на диске хранить inode, а где - содержимое файлов. Xv6 делит диск на части, как показывает рисунок.

• Блок 0 - загрузочный. Файловая система не использует этот раздел.

• Блок 1 - суперблок - описывает файловую систему. Этот раздел содержит размер файловой системы в блоках, число блоков содержимого, число inode и число блоков журнала.

• Блоки со 2-го содержат журнал файловой системы.

• За журналом следуют блоки inode - по нескольку inode на блок.

• За блоками inode следуют блоки с битовыми масками, которые определяют свободные блоки содержимого.

• Остальные блоки - содержимого - хранят содержимое файлов и директорий.

Программа mkfs создает файловую систему и заполняет суперблок.

Глава расскажет о каждом уровне файловой системы и начнет с кеша блоков. Обратите внимание, как абстракции нижних уровней облегчают работу верхних.

Кеш блоков

Кеш блоков решает две задачи:

• Упорядочивает доступ к блокам диска так, чтобы каждому блоку диска соответствовал единственный буфер памяти - копия блока - и потоки ядра работали с буфером по очереди.

• Хранит популярные блоки в памяти, чтобы не читать блоки диска снова и снова.

Файл bio.c реализует кеш блоков.

Кеш блоков предлагает две основные функции:

• bread возвращает буфер памяти с копией блока диска. Поток читает и пишет буфер.

• bwrite пишет содержимое буфера в блок диска.

Каждый буфер содержит блокировку, чтобы потоки работали с буфером по очереди. Вызов bread блокирует буфер, который возвращает - только один поток работает с буфером и блоком диска, пока буфер заблокирован. Поток освободит блокировку вызовом brelse - теперь другой поток обратится к блоку диска.

Размер кеша ограничен - если кеш заполнен, а поток обращается к блоку диска, которого нет в кеше, придется вытолкнуть буфер из кеша. Кеш выбирает наименее востребованный - Less Recently Used - буфер и записывает в него новый блок диска.

Код: кеш блоков диска

Кеш блоков ведет двусвязный список буферов. Функция main вызывает binit, чтобы создать список из NBUF буферов в статическом массиве buf. Остальной код работает с кешем блоков по указателю bcache.head и не обращается к массиву buf.

Буфер кеша хранит два флага - valid и disk. Буфер содержит копию блока диска, когда valid = 1. Драйвер диска работает с буфером, когда disk = 1 - читает блок с диска или пишет содержимое буфера на диск.

Функция bread вызывает bget, чтобы получить буфер кеша для блока диска. Функция bread вызовет virtio_disk_rw, чтобы прочесть блок диска, если блока нет в кеше.

Вызов bget(dev, blockno) обойдет список буферов кеша в поисках блока с номером blockno на диске с номером dev, блокирует буфер и вернет указатель на буфер. Вызов bget вернет указатель на свободный буфер, если не найдет в кеше блок диска. Вызов bget освободит буфер, если кеш полон - обойдет список еще раз в поисках буфера, который никто не использует - b->refcnt == 0. Вызов bget запишет номера диска и блока в буфер и блокирует буфер. Вызов bget сбросит флаг b->valid = 0, чтобы код не использовал старое содержимое буфера, а снова прочел блок диска.

Важно, что каждому блоку диска соответствует единственный буфер кеша. Потоки, которые читают блок, сразу видят то, что другие потоки в блок пишут. Поток не обратится к блоку диска в обход блокировки единственного буфера. Вызов bget соблюдает инвариант с помощью блокировки bcache.lock. Вызов bget ищет буфер кеша и создает буфер для блока диска атомарно.

Ненулевой счетчик ссылок b->refcnt запретит назначить буфер кеша другому блоку диска, поэтому bget освободит bcache.lock, прежде чем захватит b->lock. Блокировка буфера b->lock защищает содержимое буфера, а bcache.lock защищает связи буферов с блоками диска.

Функция bget вызовет panic и остановит работу ядра, если не найдет свободного буфера кеша - слишком много процессов работают с файловой системой. Код мог бы использовать блокировку и усыпить процесс, пока буфер не освободится.

Процесс единолично владеет буфером кеша, который вернула bread. Процесс вызовет bwrite, если изменил содержимое буфера, чтобы записать изменения на диск, прежде чем освободит буфер. Процедура bwrite вызывает virtio_disk_rw, чтобы обратиться к диску.

Процесс вызывает brelse, чтобы освободить буфер кеша, когда завершит работу с ним. Имя brelse - сокращение b-release - выглядит, как шифровка, но имя стоит запомнить - имя появилось в Unix и до сих пор живет в BSD, Linux и Solaris. Вызов brelse разблокирует буфер и переместит в начало списка. Список упорядочен по давности использования буфера. Первый буфер в списке - недавний, а последний - древнейший. Оба цикла bget пользуются порядком - поиск буфера требует обойти весь список в худшем случае, но проверка недавних буферов сократит время поиска, когда процессы работают в одной и той же области диска. Поиск свободного буфера выиграет, когда начнет поиск с древнейшего - конца списка.

Уровень журнала

Часто операции файловой системы требуют нескольких операций записи на диск. Сбой повредит файловую систему, если произойдет, когда лишь часть операций записи выполнена. Представьте, что сбой произошел, пока файловая система усекала файл до размера 0 и освобождала блоки содержимого файла. Сбой оставит в inode ссылку на свободный блок диска или оставит блок занятым, но без ссылки из inode - зависит от порядка, в котором файловая система выполняла операции.

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

Журнал защищает xv6 от сбоев. Системный вызов пишет не на диск, а в журнал. Журнал объединяет операции записи в транзакции - системный вызов завершает последовательность операций записи командой commit, которая завершает транзакцию. Теперь ядро выполнит транзакцию - выполнит операции из журнала со структурами данных на диске - и уничтожит журнал.

Xv6 восстанавливает файловую систему после сбоя и перезагрузки компьютера так:

• Выполнит операции из журнала с диском, если журнал содержит транзакцию, и уничтожит журнал.

• Игнорирует содержимое журнала, если транзакция журнала не завершена, и уничтожит журнал.

Блоки диска останутся нетронуты, если сбой произошел, когда код писал в журнал, но не завершил транзакцию.

Код восстановления повторит часть операций записи из журнала, если сбой произошел, когда xv6 выполняла транзакцию журнала на диске. Код пишет в те же блоки диска, поэтому информация не пострадает.

Транзакция - атомарное действие. Код восстановления выполнит каждую операцию завершенной транзакции и не выполнит ни одной, если транзакция не завершена.

Как устроен журнал

Суперблок определяет расположение журнала. Журнал состоит из блока-заголовка и копий блоков диска с изменениями. Заголовок содержит массив номеров блоков - по одному на каждый блок журнала - и число блоков журнала. Счетчик блоков равен нулю, когда транзакция журнала еще не завершена, и равен числу блоков журнала, когда транзакция завершена. Xv6 запишет число блоков в заголовок журнала, когда завершит транзакцию в журнале, и сбросит счетчик в 0, когда запишет транзакцию на диск. Сбой оставит в счетчике 0, если произошел до завершения транзакции в журнале, и ненулевое значение, если произошел после.

Код системных вызовов объявляет начало и конец транзакции. Журнал способен объединить работу нескольких системных вызовов или процессов в одну транзакцию. Файловая система пишет транзакцию на диск, когда не работает ни один вызов файловой системы, чтобы операции одного системного вызова не попали в разные транзакции.

Групповая транзакция состоит из нескольких транзакций - сокращает число дисковых операций, потому что амортизирует фиксированную стоимость записи транзакции на диск при выполнении нескольких операций. Диск выполнит больше операций записи за один оборот, когда выполнит групповую транзакцию. Драйвер virtio в xv6 не поддерживает групповые транзакции, но файловая система xv6 способна это реализовать.

Xv6 ограничивает размер журнала на диске. Системный вызов не запишет блоков больше, чем умещает журнал. Два системных вызова способны писать больше блоков, чем умещает журнал - write и unlink. Запись или удаление большого файла заставит файловую систему записать много блоков содержимого, битовых масок и блок inode. Вызов write разбивает операции записи так, чтобы уместить в журнал. Вызов unlink не создаст проблем, потому что файловая система xv6 отводит под битовые маски единственный блок.

Вызов begin_op убедится, что в журнале хватит места для работы системного вызова, прежде чем начать транзакцию.

Код: журнал

Пример работы с журналом:

begin_op();
...
bp = bread(...);
bp->data[...] = ...;
log_write(bp);
...
end_op();

Вызов begin_op ждет, пока журнал запишет предыдущую транзакцию на диск и когда в журнале освободится место. Счетчик log.outstanding равен числу системных вызовов, которые заняли место в журнале. Размер занятого пространства равен log.outstanding * MAXOPBLOCKS. Вызов begin_op увеличивает счетчик log.outstanding - занимает место в журнале и запрещает журналу записывать транзакцию на диск, пока системный вызов работает. Журнал разрешает каждому системному вызову записать до MAXOPBLOCKS различных блоков.

Процедура log_write, как и bwrite, записывает блок на диск, но делает это через журнал. Вызов log_write записывает номер блока в память, занимает слот журнала на диске и закрепляет буфер в кеше. Кеш хранит блок, пока журнал не запишет транзакцию на диск - до этих пор только буфер кеша содержит изменения. Операции чтения и записи сразу видят изменения блока, а позже журнал запишет изменения на диск. Вызов log_write замечает, когда код пишет в тот же блок, и пишет в тот же слот журнала. Такую оптимизацию называют поглощением. Часто блок диска содержит inode нескольких файлов, которые транзакция изменяет. Поглощение экономит место в журнале и помогает писать транзакции на диск быстрее - журнал пишет каждый блок диска единственный раз.

Процедура end_op уменьшает счетчик log.outstanding системных вызовов, что работают с журналом. Вызов end_op пишет транзакцию на диск - вызывает процедуру commit, когда счетчик окажется равен 0. Процедура commit выполняет четыре шага:

• write_log копирует каждый блок, который изменила транзакция, из кеша в слот журнала на диске.

• write_head пишет заголовок журнала на диск. Теперь код восстановления запишет блоки журнала на диск, если случится сбой.

• install_trans читает блоки журнала и пишет на диск.

• Сбрасывает в заголовке журнала счетчик блоков в 0. Теперь журнал готов начать следующую транзакцию.

Процедура recover_from_log восстанавливает файловую систему после сбоя - читает заголовок журнала, записывает транзакцию журнала на диск, если транзакция завершена, и сбрасывает счетчик блоков журнала в 0.

Вот как функция filewrite записывает транзакцию в журнал:

begin_op();
ilock(f->ip);
r = writei(f->ip, ...);
iunlock(f->ip);
end_op();

Функция filewrite выполняет этот код в цикле, который разбивает многочисленные операции записи на транзакции по нескольку блоков, чтобы уместить в журнал. Этот вызов writei провоцирует запись многих блоков в ходе транзакции: блоков inode, блоков битовых масок и блоков содержимого файлов.

Код: аллокатор блоков

Xv6 ведет пул свободных блоков диска. Аллокатор блоков содержит битовую маску свободных блоков - по одному биту на каждый блок. Блок свободен, когда бит сброшен - равен 0 - и занят, когда бит установлен - равен 1. Программа mkfs занимает загрузочный сектор диска, суперблок, блоки журнала, inode, битовых масок и устанавливает соответствующие биты.

Аллокатор блоков предоставляет две функции: balloc занимает блок диска, а bfree освобождает. Цикл balloc обходит блоки диска с номерами от 0 до sb.size и ищет свободный блок, чей бит в маске сброшен, устанавливает бит и возвращает блок. Код выполняет два цикла: внешний цикл обходит блоки битовых масок, а внутренний - биты блока. Кеш блока запрещает двум процессам одновременно работать с одним и тем же блоком, поэтому состязания не возникает.

Вызов bfree(dev, b) находит на диске dev блок маски, который хранит бит для блока с номером b и сбрасывает бит. Вызовы bread и brelse и здесь упорядочивают доступ параллельных потоков к блоку.

Код вызывает функции balloc, bfree и другие, которые пишут на диск, только внутри транзакции.

Уровень inode

inode обозначает:

• Структуру данных на диске, которая описывает файл - содержит размер файла и номера блоков содержимого файла.

• Структуру данных в памяти, которая содержит копию inode с диска и дополнительную информацию.

Файловая система хранит inode на диске в блоках inode. Блоки inode занимают непрерывную область диска, а структуры inode - одинакового размера, поэтому структуру inode на диске легко найти по номеру. Номер inode уникален.

Структура dinode описывает структуру inode на диске. Поле type обозначает тип inode - файл, директория или устройство. Структура dinode свободна, когда type = 0. Поле nlink хранит число записей директорий, которые ссылаются на inode. ОС освободит inode и блоки содержимого файла, когда nlink окажется равен 0. Поле size хранит число байтов, которое занимает содержимое файла. Массив addrs хранит номера блоков содержимого файла.

Ядро хранит в памяти таблицу itable со структурами inode. Структура inode - копия структуры dinode в памяти. Ядро хранит inode в памяти, только когда код хранит указатель на inode. Поле ref хранит число указателей на inode в памяти. Ядро уничтожит inode, когда ref окажется равен 0. Функции iget и iput захватывают и освобождают указатели на inode - увеличивают и уменьшают ref. На inode указывают файловые дескрипторы, текущие рабочие директории процессов, преходящий код ядра такой, как exec.

Структура inode предлагает четыре механизма блокирования:

• Блокировка itable.lock защищает инварианты "inode не повторяются в itable" и "счетчик ref равен числу указателей на inode".

• Каждый inode владеет блокировкой lock, которая защищает поля структуры inode.

• Значение 0 < ref запрещает ядру загружать другой inode в этот слот таблицы.

• Значение 0 < nlink запрещает файловой системе уничтожать inode и блоки содержимого, на которые он ссылается.

Вызов iget возвращает указатель на inode и гарантирует, что указатель останется корректным, пока код не вызовет iput. Вызов iget не блокирует inode - код вызывает iget сколько угодно раз и хранит сколько угодно указателей на inode. Файловая система полагается на поведение iget - открытые файлы и текущие директории процессов подолгу хранят указатели на inode, а отдельные функции iget и ilock помогают коду поиска пути справиться с состязаниями и взаимоблокировками.

Вызов iget способен вернуть inode, который еще не загрузил данные с диска. Код вызывает ilock, чтобы убедиться - файловая система загрузила данные inode с диска. Вызов ilock блокирует inode, чтобы другой процесс не работал с ним, и читает inode с диска, если нужно. Вызов iunlock разблокирует inode.

Отдельные функции iget, ilock и iunlock помогают избежать взаимоблокировок. Процессы хранят указатели на один тот же inode, но работают с ним по очереди. Код поиска по директориям не обойдется без этих функций.

Таблица itable только хранит inode, на которые указывает код. Цель itable - упорядочить работу процессов с inode. Таблица itable выглядит как кеш inode, но кеш блоков диска и так хранит в памяти блоки inode, к которым часто обращаются.

Вызов iupdate сохранит изменения inode на диск.

Код: inode

Xv6 создает inode на диске с помощью вызова ialloc. Вызов ialloc похож на balloc - обходит структуры inode на диске в поисках свободной, занимает и возвращает указатель на inode в памяти вызовом iget. Код ialloc полагает, что только один процесс работает с bp - другие процессы не видят, что inode свободен, и не займут inode.

Вызов iget ищет inode в памяти, у которого 0 < ref, а попутно запоминает свободный слот таблицы на случай, если inode в памяти не окажется.

Код блокирует inode вызовом ilock, прежде чем читает или пишет поля структуры inode или блоки содержимого файла. Вызов ilock захватит спящую блокировку, а iunlock освободит блокировку и разбудит спящие процессы.

Вызов iput освободит указатель на inode - уменьшит счетчик указателей ref. Вызов iput освободит слот таблицы itable, который inode занимает, когда освободит последний указатель.

Вызов iput освободит блоки содержимого файла на диске вызовом itrunc, если ни одна директория больше не ссылается на файл - nlink == 0.

Опасно, если бы другой поток ожидал блокировки inode в ilock, а iput уничтожила файл. Этого не произойдет, потому что перед ilock поток вызывает iget и увеличивает счетчик указателей на inode. Значение 1 < ref говорит iput, что другие потоки еще способны обратиться к inode и файл уничтожать нельзя.

Опасно, если параллельный вызов ialloc выберет inode, который iput освобождает. Вызов ialloc выберет inode, только когда iput запишет в inode на диске type = 0. Блокировка inode->lock упорядочивает работу ialloc и iput с inode - iput блокирует inode, пока освобождает и пишет на диск, а ialloc ожидает разблокирования inode.

Системный вызов, который работает с файловой системой, вызывает iput, когда завершает работу с файлом. Вызов iput способен писать на диск, поэтому системный вызов способен писать на диск, поэтому системные вызовы файловой системы работают в транзакции.

Вызов iput не освобождает блоки содержимого файла сразу, как только счетчик ссылок nlink окажется равен 0, потому что другие процессы еще ссылаются на inode в памяти. Блоки диска останутся заняты, если случится сбой. Файловые системы решают проблему двумя способами:

• Код восстановления ищет на диске файлы, на которые не ссылается ни одна директория, и удаляет.

• Файловая система запоминает номера inode, чей nlink = 0, но 0 < ref. Файловая система удалит файл, как только ref окажется равен 0, или код восстановления просмотрит список и удалит файлы.

Xv6 не реализует эти способы и оставляет файлы без ссылок на диске. Это значит, что со временем свободное место на диске закончится.

Код: содержимое inode

Структура dinode содержит размер файла и массив addrs номеров блоков диска с содержимым файла. Массив addrs содержит первые NDIRECT номеров блоков и номер косвенного блока, который содержит следующие NINDIRECT номеров блоков содержимого файла. Таким образом код способен обратиться к первым NDIRECT * BSIZE = 12 Кб файла напрямую из inode, а к следующим NINDIRECT * BSIZE = 256 Кб - косвенно.

Такая структура inode хороша для хранения на диске, но трудна в использовании. Функция bmap помогает работать с блоками файла так, что функции readi, writei и подобные не знают, как блоки хранятся. Функция bmap логически нумерует блоки файла от 0 до N - вызов bmap(ip, bn) вернет номер блока диска для блока с логическим номером bn. Вызов bmap займет новый блок и поместит в inode, если inode блок еще не содержит.

Вызов bmap сперва проверит первые NDIRECT блоков из inode, затем NINDIRECT блоков из косвенного блока ip->addrs[NDIRECT]. Вызов bmap читает косвенный блок, а затем номера блоков диска из него. Вызов bmap остановит работу ядра вызовом panic, если логический номер блока bn превосходит NDIRECT + NINDIRECT. Функция writei проверяет это условие, чтобы не допустить краха.

Вызов bmap занимает новые блоки, если нужно. Массив ip->addrs и косвенный блок содержат нули, когда файл еще не содержит этих блоков. Вызов bmap заменит 0 номером блока диска, который запросит у файловой системы.

Вызов itrunc освобождает блоки содержимого файла и обнуляет размер файла ip->size = 0. Сперва itrunc освобождает блоки из массива addrs[], затем из косвенного блока, а затем и сам косвенный блок.

Функция bmap облегчает работу readi и writei. Сперва readi(ip, user_dst, dst, off, n) проверит, что позиция off не выйдет за конец файла и что сумма off + n умещается в тип unsigned int, иначе сообщит об ошибке. Вызов readi вернет меньше байтов, чем запрошено, если off + n окажется за концом файла. Цикл for обходит блоки содержимого файла и копирует байты по адресу dst. Вызов writei работает аналогично readi с тремя исключениями:

• writei увеличит размер файла, если off совпадет с концом файла или лежит за ним - вплоть до MAXFILE * BSIZE.

• Цикл копирует байты в файл, а не из него.

• writei обновит поле ip->size, если увеличит размер файла.

Вызов stati копирует метаданные inode в структуру stat, которую возвращает системный вызов stat.

Код: уровень директорий

Структура inode директории содержит type = T_DIR, а блоки содержимого - записи директории. Структура dirent представляет запись директории - содержит имя и номер inode, на который запись ссылается. Константа DIRSIZ ограничивает длину имени. Имя короче DIRSIZ оканчивается нулевым байтом. Запись директории свободна, когда номер inode равен 0.

Функция dirlookup(dp, name, poff) ищет в директории dp запись с именем name, запоминает в poff позицию записи в директории и возвращает указатель на inode записи. Функция dirlookup получает указатель на inode вызовом iget, поэтому не блокирует inode. Функция dirlookup не могла бы работать без деления iget и ilock - код поиска пути последовательно вызывает dirlookup и зависнет, когда встретит ., которая обозначает текущую директорию. Существуют и другие сценарии взаимоблокировки с параллельными процессами и родительской директорией ...

Вызов dirlink(dp, name, inum) создаст запись с именем name и номером inode inum в директории dp. Вызов dirlink вернет ошибку, если запись с именем name уже существует. Цикл перебирает записи директории в поиске свободной и запоминает позицию off свободной записи.

Код: пути к файлам

Поиск пути состоит из последовательных вызовов dirlookup - по одному на каждый компонент пути. Функция namei возвращает inode файла, к которому путь ведет. Функция nameiparent(path, name) возвращает inode предпоследнего компонента пути - родительской директории - и копирует последний компонент в name. Функции namei и nameiparent вызывают namex, которая выполняет основную работу.

Сперва namex решает, откуда начать поиск пути - с корневой директории, если путь начинается с /, иначе - с текущей директории. Затем namex вызывает skipelem в цикле, чтобы разобрать каждый компонент пути и добраться до последнего. Каждая итерация цикла блокирует текущий inode, убеждается, что inode - директория - и ищет запись директории с именем name. Вызов ilock убедится, что inode загружен с диска. Цикл ищет следующий компонент пути с помощью dirlookup и готовит следующую итерацию - присваивает ip = next. Цикл завершится, когда закончатся компоненты пути.

Цикл завершится раньше, если работает nameiparent - name уже содержит последний компонент пути - namex разблокирует и вернет ip.

Функция namex способна работать долго и провоцировать множество дисковых операций - читать inode и блоки содержимого директорий. В xv6 один поток вызывает namex и ожидает ввода-вывода диска, а другой поток способен параллельно искать другой путь.

Опасно, если поток удалит директорию, пока другой ищет путь. Xv6 упорядочивает работу параллельных потоков. Пример: поток выполняет dirlookup в namex, блокирует директорию, а dirlookup возвращает указатель на следующий компонент пути вызовом iget, который увеличит счетчик ip->ref. Теперь namex разблокирует директорию, а другой поток удалит ссылку на inode из директории, но xv6 не удалит inode, пока в памяти остается указатель.

Другая опасность - взаимоблокировка. Пример: next указывает на тот же inode, что и ip, когда поиск пути встречает .. Повторная блокировка повесит поток. Функция namex разблокирует ip, прежде чем блокировать next, чтобы этого не случилось. Это еще раз подтверждает важность отдельных функций iget и ilock.

Уровень файловых дескрипторов

Уровень файловых дескрипторов помогает Unix предоставлять большинство ресурсов как файлы.

Глава 1 рассказывала, как xv6 ведет таблицы открытых файлов - файловых дескрипторов - каждого процесса. Структура file описывает открытый файл и обобщает интерфейс inode и канала. Системный вызов open открывает файл - создает структуру file. Процессы открывают один и тот же файл независимо друг от друга - каждая структура file запоминает позицию в файле.

Таблицы открытых файлов включают одну и ту же структуру file по нескольку раз. Пример: процесс открыл файл вызовом open, копировал файловый дескриптор вызовом dup и поделился открытыми файлами с дочерним процессом вызовом fork. Открытый файл ведет счетчик ref указателей на него.

Процесс открывает файл только для чтения, только для записи, для чтения и записи - поля readable и writeable структуры file следят за этим.

Глобальная таблица ftable содержит каждый открытый файл, какой бы процесс файл ни открыл. Функция filealloc занимает слот таблицы, filedup копирует указатель на file, fileclose освобождает указатель на file, fileread читает из файла, а filewrite пишет в файл.

Вызов filealloc ищет свободный слот таблицы ftable, в котором f->ref == 0, занимает и возвращает указатель на него. Вызов fileclose уменьшает счетчик указателей f->ref и закрывает файл или канал, когда счетчик окажется равен 0.

Функции filestat, fileread и filewrite реализуют операции stat, read и write над файлами. Функция filestat работает только с inode и вызывает stati. Функции fileread и filewrite проверяют, что режим открытия файла разрешает операцию, и передают управление функциям канала или inode. Функции fileread и filewrite сдвигают позицию в файле, когда работают с inode. Канал не разрешает читать и писать в указанной позиции. Функции inode требуют, чтобы вызывающий код блокировал inode. Блокировка inode делает атомарным сдвиг позиции в файле. Параллельные операции записи в файл не уничтожат друг друга, но порядок выполнения операций непредсказуем.

Код: системные вызовы

Функции sys_link и sys_unlink правят директории - создают и уничтожают ссылки на inode. Эти функции - еще один пример использования транзакций. Вызов sys_link принимает два аргумента - old и new. Файл old существует и не директория. Вызов sys_link найдет inode для old, увеличит ip->nlink, вызовет nameiparent, чтобы найти родительскую директорию для new, и добавит в нее запись с именем new и номером inode old. Вызов sys_link требует, чтобы родительская директория new существовала и находилась на том же диске - номер inode уникален только внутри одного диска. Вызов sys_link вернет ip->nlink к прошлому значению, если случится ошибка.

Транзакции упрощают работу - можем не думать о порядке записи блоков, когда пишем блоки диска. Увеличение ip->nlink вне транзакции нарушит инвариант файловой системы, пока код не создаст запись директории со ссылкой на ip. Сбой нарушит целостность файловой системы, если случится, когда инвариант нарушен. Транзакции помогают соблюдать инварианты.

Вызов sys_link дает новое имя существующему inode. Функция create создает новый inode. Это обобщение трех системных вызовов, которые создают файлы:

• open с флагом O_CREATE создает файл данных.

• mkdir создает директорию.

• mkdev создает файл устройства.

Сперва create вызовет nameiparent, чтобы получить inode родительской директории, затем вызовет dirlookup и проверит, что файл еще не существует. Дальше поведение create зависит от системного вызова:

• create завершится успехом, как и open, если файл существует и type = T_FILE.

• create сообщит об ошибке, если файл существует, но type != T_FILE.

• create создаст inode вызовом ialloc, если файла не существует.

• create создаст записи директории . и .., если вызван из mkdir, свяжет . с inode и .. с родительской директорией.

Вызов create блокирует два inode одновременно, как и sys_link - ip и dp. Взаимоблокировки не случится, потому что ip только что создан - другие процессы не заблокируют ip, прежде чем попытаются блокировать dp.

Функция create упрощает код sys_open, sys_mkdir и sys_mknod. Вызов sys_open сложнее остальных, потому что создание файла - малая часть того, что умеет sys_open. Вызов sys_open вызовет create, если open получил флаг O_CREATE, иначе вызовет namei. Вызов create вернет заблокированный inode, а namei нет, поэтому sys_open блокирует inode. Вызов sys_open разрешает открывать директории только для чтения. Вызов sys_open занимает слот таблицы itable вызовом filealloc и свяжет открытый файл с новым файловым дескриптором вызовом fdalloc. Другие процессы не обращаются к частично сконструированной структуре file, потому что только таблица файлов текущего процесса содержит этот файл.

Глава 7 рассказала о каналах, прежде чем мы узнали о файловой системе. Функция sys_pipe соединяет файловую систему с каналами. Вызов sys_pipe принимает аргументом адрес памяти p, создает пару файловых дескрипторов, связывает с каналом и записывает по адресу p.

Реальность

Кеш блоков в других ОС устроен сложнее, чем в xv6, но служит тем же целям - кеширует блоки диска и упорядочивает работу процессов с ними. Кеш блоков xv6 вытесняет блоки из кеша по алгоритму LRU - Less Recently Used - как и V6. Существуют и другие алгоритмы, которые рассчитаны на специальные режимы работы ОС. LRU-кеш работает эффективнее, когда хранит блоки не в списке, а хеш-таблице. Кеш блоков современных ОС умеет отображать файлы в память - интегрирован с виртуальной памятью.

Журнал xv6 работает неэффективно. Журнал не завершит транзакцию, пока работают другие вызовы файловой системы. Журнал записывает блоки, даже если код изменил пару байтов. Журнал записывает блоки на диск по одному и лишний раз вращает диск. Другие ОС решают эти проблемы.

Журнал - не единственная защита от сбоев. Раньше файловые системы собирали мусор, когда перезагружались - проверяли файлы, директории, списки свободных блоков и inode в поисках несоответствий. Так работала программа fsck на Unix. Сборка мусора займет часы на больших файловых системах и часто не способна разрешить несоответствия так, чтобы системные вызовы работали атомарно. Восстановление по журналу работает быстрее и помогает системным вызовам работать атомарно.

Xv6 располагает файловую систему на диске так же, как ранние Unix - эта схема работает и по сей день. Файловые системы UFS и FFS в BSD, ext2 и ext3 в Linux основаны на тех же структурах inode и директорий. Директории замедляют работу файловой системы, потому что поиск в директории требует просмотреть каждую запись директории. Линейный поиск работает быстро, когда директория занимает пару блоков диска, но дорого обойдется директории с большим количеством файлов. Файловые системы NTFS в Windows, HFS в macOS, ZFS в Solaris и другие хранят блоки директорий на диске в сбалансированном дереве, в которых поиск работает за логарифмическое время.

Xv6 остановит работу, когда операция диска завершится ошибкой. Другие ОС справляются с ошибками диска - потеря блока одного файла не обрушит систему. RAID-массивы дисков обрабатывают ошибки так, что ОС не видит ошибок диска.

Xv6 располагает файловую систему на одном диске и не меняет размер файловой системы. Базы данных и файлы мультимедиа растут в размерах и ОС изобретают способы избавиться от ограничения "один диск = одна файловая система". Основная идея - объединить физические диски в один логический диск. ОС стремятся реализовать как можно больше функций программно, хотя массивы физических дисков RAID все еще популярны. Код помогает увеличивать и уменьшать размер логического диска на лету. Такой диск требует, чтобы и файловая система расширялась и сжималась. Массив блоков inode фиксированного размера не подходит такому диску.

Файловая система ZFS берет управление дисками на себя. Файловые системы ZFS работают с пулом доступного для записи пространства - администратор добавляет или убирает диски из пула, а файловая система автоматически подстраивает размер.

Другие файловые системы предлагают еще многие функции, которых нет в xv6. Пример: снимки и инкрементное резервное копирование.

Современные Unix предоставляют ресурсы как файлы - именованные каналы, сетевые соединения, сетевые файловые системы, интерфейсы наблюдения и управления процессами /proc. Такие ОС дают каждому открытому файлу таблицу указателей на функции, которые реализуют операции над файлом. Пример: операция read вызовет нужный код по указателю, а не станет проверять тип файла и подбирать код, как это делает fileread в xv6. Сетевые файловые системы реализуют операции над файлом как вызовы удаленных процедур по сети.

Упражнения

• Почему xv6 вызывает panic в balloc? Можно ли справиться с ошибкой?

• Почему xv6 вызывает panic в ialloc? Можно ли справиться с ошибкой?

• Почему filealloc не вызывает panic, когда исчерпала лимит файлов? Почему это часто случается?

• Представьте, что другой процесс удалит ссылку из директории на ip, пока процесс выполняет код sys_link между вызовами iunlock(ip) и dirlink. Создаст ли dirlink ссылку на файл? Почему?

• Функция create требует, чтобы четыре системных вызова - один ialloc и три dirlink - завершились успехом, иначе вызовет panic. Почему?

• Функция sys_chdir вызывает iunlock(ip) до iput(p->cwd), которая может блокировать p->cwd. Почему вызов iunlock(ip) после iput(p->cwd) не ведет к взаимоблокировке?

• Реализуйте системный вызов lseek. Придется изменить код filewrite, чтобы заполнить нулями пробелы в файле, когда lseek выходит за конец файла f->ip->size.

• Научите open работать с флагами O_TRUNC и O_APPEND, чтобы реализовать операторы > и >> в программе shell.

• Научите файловую систему работать с символическими ссылками.

• Научите файловую систему отображать файлы в память.