Журналната файлова система ext3 за Hurd

Ext2 е измислена, за да бъде стандартната файлова система за Linux. Тя много прилича на файловата система UFS на операционната система BSD, която се води за класическа в UNIX®.

Ext3 е ext2 с добавен журнал, който се реализира от библиотеката JBD (Journal Block Device) вътре в Linux. Предимството на този подход е, че се стъпва на една изпитана технология (ext2), като просто се добавят журнални способности. Недостатъкът проличава в много сравнения с другите журнални файлови системи, където често ext3 заема последното място или последните места. Причината е именно в неоптимизираността на файловата система като цяло поради силната връзка с класическата файлова система за UNIX®.

Това е една от най-дискутираните файлови системи за Linux. Проектът reiserfs има далечни цели, които ще позволят използването на файловата система да бъде толкова ефективно, колкото и база данни. Използването на много малки файлове (например от по няколко байта), разхвърляни в дълбока йерархия от директории, е доста бързо.

Технически reiserfs има няколко важни особености. Директорията съдържа не само имената на файловете, но и цялата метаинформация за тях. При това файловете са подредени в дърво, така че намирането на файл е много бързо. Присъствието на метаинформацията в дървото означава, че веднъж като се намери, можем направо да започнем да работим с файла, без да се обръщаме допълнително към друго място на диска, откъдето да взимаме метаинформация.

Важно подобрение е специалното отношение към опашките на файловете. Всяка файлова система разделя пространството си на равни по големина блокове. Когато се запазва файл, последният блок почти винаги съдържа празно пространство, просто защото големината на файла не се дели точно на блока. Данните на файла в последния блок се наричат опашка на файла. Във файловата система reiserfs опашката на блока се записва в метаинформацията, т.е. в директорията. Това позволява още по-голямо ускоряване на достъпа, особено за малки файлове. Излиза, че с достъпа до файл, по-малък от блок, вече е прочел и самия файл!

Както виждаме, reiserfs ще е особено силен, когато директориите съдържат голямо количество файлове, също и когато файловете са малки. Но даже и да не е така, reiserfs е много бърза.

Reiserfs4 е включен на 29 август 2004 г. във версия 2.6.8.1-mm2 на Linux. Кодът е пренаписан и структурите са силно променени, което значи, че имаме напълно нова файлова система. Основната цел на reiserfs4 е да затвърди позициите й на най-бързата файлова система. Тестовете показват, че тази цел е постигната. Затова бъдещите версии на reiserfs ще се концентрират върху споменатите по-горе далечни цели – създаване на добри условия файловата система да се използва като база данни.

Вместо B+ дървета се използват танцуващи дървета, който се използва при системите за бази данни. Още по-сериозна промяна е възможността да се пишат плъгини. Това няма да бъде разглеждано тук.

В сайта на XFS тя е определена като високопроизводителна журнална файлова система. Целите при конструирането на тази файлова система са различни от тези на reiserfs. Тя е създадена с мисъл за мащабируемост на капацитета и производителността, поддържайки много големи файлови системи. Това включва боравене с много големи файлове, голям общ брой файлове, големи директории и високопроизводителна входно-изходна система.

За тези цели се стъпва силно върху употребата на B+ дървета. Те се използват за следното:

XFS е напълно 64-битова: за брой на блоковете и файловете например. Обаче пространството е разделено на allocation groups, където за някои неща се използват локални 32-битови числа. Тези allocation groups се използват и в промяната на големината на файловата система.

За висока производителност е обърнато внимание на следните неща:

JFS, също както и XFS, е направена от голяма фирма (IBM) с цел голяма производителност и използване на транзакции за много по-бързо рестартира на системата. Системата е напълно 64-битова. Големината на блока е до 4K. Част от метаинформацията за цялата файлова система се съхранява във файлове. Използват се отрязъци (extents) за блоковете на файловете, които B+ дървета. Свободните блокове се отбелязват във вектор от битове, като има някои оптимизации. Възлите за файлове (inodes) могат динамично да се заделят. Директориите се съхраняват в един блок, ако файловете са до 8, и в B+ дърво ако няма място.

Файловата система е построена с мисъл за поддръжка на DCE DFS (Distributed Computing Environment Distributed File System). Най-голямата единица е агрегатът, който е дял в обикновения смисъл. Той може да съдържа няколко fileset, които могат да се монтират. Засега обаче се поддържа само един fileset. Пространството на един fileset се разделя на aggregation groups, съдържащи данни и метаданни. Стремежът е данните винаги да са в същата aggregaтion group като метаданните. Поддържа се промяна на големината на файловата система, както и дефрагментиране.

В някои тестове се отбелязва, че JFS заема сравнително малко памет в ядрото.

Всички файлови системи за UNIX-системите по необходимост имат еднакви свойства. Дискът условно може да бъде разделен на четири части: главен блок (super block), възли (i-nodes), таблица на свободните блокове и място за данни. Всеки възел се достъпва чрез номера му, който е число от тип ino_t. Там се съдържа всички метаданни за файл, като например време на последна промяна и големина, освен самото име на файла. Пълният списък на метаданните във възел може да се види в определението на struct stat от sys/stat.h (или bits/stat.h в GNU, който файл никога не се включва направо). Директориите се представят по същия начин като файловете, но във възела са отбелязани като директории. Съдържанието на тези директории-файлове е списък от двойки име на файл и номер на възел. По този начин се позволява различни имена на файлове в една файлова система да сочат към един и същ файл. Това са твърди връзки към файл (hard links).

В областта за данни няма само и единствено съдържание на файловете. Списъкът на блоковете на съдържанието също се държи в блокове от областта за данни. Класическото изпълнение е във възела да има номерата на първите 10 блока от данни. Ако файлът е голям до 10 блока, използваното пространство от областта за данни ще е само за съдържанието на файла. Това насърчава използването на кратки файлове. При повече от 10 блока се добавя един косвен блок, чието съдържание е само от списък от блокове с данни. Ако това не стигне, добавя се двоен косвен блок, който съдържа номерата на единични косвени блокове. Ако и това не стигне, добавя се троен косвен блок, който съдържа номерата на двойни косвени блокове.

Оттук нататък конкретното представяне на файловите системи върху диска се различава. В ext2 вторият 1024-байтов блок от дяла е на главния блок. Останалата част от дяла е разделена на блокови групи. Всяка блокова група си поддържа таблица на свободните блокове и масив от възли, чиите файлове са разположени най-вече върху същата блокова група. Смисълът зад всичко това е работата с файлове да предизвиква възможно най-малко преместване на главата на твърдия диск. Ако искаме да създадем нов файл, след избиране на възела ще се работи най-вече с таблицата на свободните блокове на същата блокова група, като и блоковете на файла ще се изберат от там.

Главният блок се намира във втория 1024-байтов блок на дяла. Там се съдържат основните данни за файловата система като големина на блока, брой на блоковете и възлите, брой на свободните блокове и възли. Понеже трябва все пак през определено време да се проверява файловата система, поддържат се брояч на монтиранията, време на последната проверка, както и настройка при какъв брой на монтиранията или след колко време да се извърши нова проверка.

От първия блок веднага след главния блок започват описателите на всички блокови групи. Всеки описател съдържа информация колко е голям блока, броя на всичките и свободните блокове и възли в тази блокова група, както и в кои блокове са таблицата на свободните блокове и таблицата на възлите.

В началото на всяка блокова група винаги стоят главен блок и описатели на блоковите групи. Обаче промяната им винаги е само в първата блокова група, освен ако при монтирането на файловата система не е зададено друго. В останалите информацията не е актуална и съвпада само в непроменливите части. Например във всички копия на описателя на дадена блокова група има верен общ брой на блоковете, но само в един описател ще има актуален брой на свободните блокове. Цялото това излишество на важна метаинформация е за да може в случай на разваляне на първта блокова група, все пак използвайки останалите блокови групи да се възстанови донякъде файловата система. Неактуалността на променливата метаинформация не е толкова важна, защото тя може да се възстанови. Например броя на свободните блокове може да се възстанови просто като се преброят тези блокове в таблицата на свободните блокове.

В блоковата група се нейните таблица на свободните блокове, таблица на свободните възли и таблица на самите възлите. Таблиците на свободните блокове и възли са от по един блок, в който всеки блок или възел от блоковата група е представен от един бит, показващ дали е свободен или не. Разположението на тези таблици изцяло се определя от описателя на блоковата група.

Почти всичко от информацията във възела може да се получи от програмите чрез системното извикване stat. Във възела обаче информацията е представена в един по-“разпръснат” вид. Например големината на файла се съдържа в две 32-битови полета, i_size и i_size_high, които съвсем не са едно до друго физически на диска. Това е резултат от стремежа за съвместимост с по-старите версии на ext2.

От полетата, които не се връщат от stat, най-важен е векторът с номерата на блоковете с данни. Първите 12 номера са на първите 12 блока с данни. 13-ият номер е на косвен блок, който изцяло е вектор с номера на блокове с данни. 14-ият номер е на косвен блок, който изцяло е вектор с номера на косвени блокове, приличащи на 13-ия. 15-ият номер е на косвен блок, който изцяло е вектор с номера на блокове, приличащи на 14. По този начин могат да бъдат представени наистина много големи файлове, но колкото е по-малък файла, толкова по-малко ще заема и метаинформацията за файла. Номер 0 на блок означава празен блок, който трябва да се запълни с нули, ако се изиска. Това са така наречените дупки във файла. Те не са нещо специфично за ext2, а се поддържат от почти всички файлови системи за UNIX®.

Алгоритмите за заделяне са важна част от ext2. Принципът е блоковете и възлите да са близо един до друг, ако се очаква да се използват заедно. По отношение на възлите това значи възелът да е в същата блокова група, където е и съдържащата го директория. По отношение на блоковете функцията за заделяне на нов блок приема като параметър блок-цел, около която да се задели новия блок. Първо се пробва дали има свободен блок малко по-напред, после малко по-назад, след това изобщо някакъв блок в същата блокова група, и чак когато всичко е неуспешно, се търси из другите блокови групи. Едно от усъвършенстванията е предварителното заделяне на блокове. Когато се заделя блок, с това се заделят по специален начин и следващите 7 блока. При следващото искане на блок направо се връща вече заделения следващ блок.

Принципът на работа на журнала е да се запишат предварително действията, които ще се извършат. След това се извършват самите действия. Тези две записвания могат да се нарекат предварителен запис и същински запис. Ако предварителният запис се прекъсне, още нищо не е записано в действителност и всичко е консистентно. Ако същинския запис се прекъсне, при ново стартиране на системата предварителният запис е пълен и той се преиграва (replay). Частичен предварителен запис не се преиграва. Затова последният блок от предварителния запис е завършващия блок. Ако той липсва, частичният предварителен запис не се преиграва.

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

Самият журнал е цикличен и се състои от последователност от транзакции, които съдържат най-вече предварителни записи. Всяка транзакция има номер и номерата се раздават в нарастващ ред. Главният блок на журнала съдържа две важни полета – началния блок и номера на най-старата транзакция, която не е завършила същинския си запис. При преиграването се започва от тази транзакция и се продължава или до достигане на недовършена транзакция, или до такава с по-малък номер.

Обикновено журналът се използва променен. Вместо да се записват и данни, и метаданни, само данните се слагат в журнала. Това ускорява журналната файлова система, като тя пак си остава консистентна. Но консистентни остават метаданните, не и данните. В повечето случаи това е приемливо, защото една от основните цели на журнала е да се избегне проверяването на файловата система след всяко неочаквано прекъсване на системата. Това проверяване е изцяло за метаданните, но не и за данните.

Обаче с тази промяна има един случай, при който може да има разваляне на данни. Той се може да се прояви само ако в един момент блок, който е бил с метаданни, се използва за данни. Такива метаданни са косвените блокове (indirect blocks), които съдържат номерата на блокове с данни или на други косвени блокове. Когато някой файл се изтрие или се смали, такива косвени блокове могат да бъдат освободени и по-късно да бъдат използвани за данни. Ако системата обаче се прекъсне, в журнала може да има транзакции, които да презапишат стария косвен блок върху новите данни. Нека проследим постъпково какво се случва:

Това положение може да се постигне и с по-малко транзакции, но тук са представени повече за по-голяма яснота.

Това е еднственият проблем, свързан с отделянето на данните от журнала. Решението е просто – поддържа се списък на освободените блокове (revoked blocks) и те не се преиграват. Точният алгоритъм се състои от следните правила:

След като имаме крайния списък на освободените блокове, по време на преиграването на предварителните записи никога не са записва върху тези блокове. Това е и причината за второто условие – един освободен блок може да се използва по-късно пак за метаданни. Тогава въпреки че в по-ранна транзакция е обявен за освободен, този блок трябва да се включи в преиграването.

Всички останали описания на блокове започват с общото начало.

Самият журнал представлява последователност от транзакция. Смесени са revoke и descriptor блоковете, а последният блок е commit блокът. Без commit блок цялата транзакция е невалидна.

Самият descriptor блок има само обща част и последователност от тагове на блокове с данни.

Последният таг има флаг JFS_FLAG_LAST_TAG. Всеки таг трябва да има UUID на файловата система, на който е блока. Това UUID се записва в 16 байта веднага след тага. Ако то е същото като предишното, може просто да се използва флага JFS_FLAG_SAME_UUID и да не се добавя след тага.

Веднага след descriptor блока има по един блок за всеки таг. Там се записва новото съдържание на блока от файловата система. Това съдържание не трябва да започват с магическата стойност JFS_MAGIC_NUMBER, защото иначе ще бъдат разпознати като журнални блокове. В такъв случай там се записва 0 и това се отбелязва чрез флага JFS_FLAG_ESCAPE. При преиграването нулата ще се замени обратно с истинската стойност.

Revoke блоковете имат само едно поле r_count от тип uint32_t. След него следват толкова на брой номера на блокове, които са обявени като вече несъдържащи метаданни на файловата система.

Микроядрото Mach е първото популярно микроядро, което и до днес има силно влияние, макар и не в оригиналния си вид. Всичко започва през 1975 в Университета на Рочестър. Там е било демонстрирано как операционните системи могат да се построят на модулен принцип, като общуването между процесите се осъществява чрез предаване на съобщения. Тази абстракция на общуването позволява програмите да са на различни машини в мрежа, но самите програми да не знаят това. Това и не ги засяга, понеже това предаване на съобщения е абстракция, които скрива тези детайли.

Един от инженерите в проекта е бил Ричард Рашид. През 1979 той се премества в Университета Карнеги Мелон, където продължава изследванията си върху операционните системи за предаване на съобщения, и през 1981 излиза резултатът – системата Accent.

Системата е била популярна в CMU, но през 1984 е изместена от UNIX®. Тогава Рашид решава да работи върху третото поколение на проекта, което той нарича Mach. Една от целите на Mach е да може да се използва огромното количество софтуер, написано за UNIX®. Други подобрения спрямо предишните проекти са въвеждането на нишки, подобрено общуване между процесите, многопроцесорна поддръжка и съвременна система за виртуална памет. По това време DARPA (същите, които са финансирали реализацията на TCP/IP) търсят многопроцесорна операционна система и харесват Mach. Така проектът си осигурява финансиране и е добавена поддръжка на 4.2BSD направо в ядрото, правейки го доста голямо, но за сметка на това съвместимо с UNIX®.

По това време започват проблемите на BSD с лицензите на AT&T, която е имала силно влияние тогава. Големи компании като IBM и DEC създават OSF (Open Software Foundation), опитвайки се да се справят с проблема. Те взимат Mach 2.5 и издават операционната система OSF/1. В крайна сметка този клон не става популярен, но има своето влияние в развитието на операционните системи. Ядрото Darwin на MacOS X е произлязло от OSF/1 и FreeBSD. Може би това е най-популярната операционна система в момента, използваща в крайна сметка Mach.

Решението на CMU относно лицензните проблеми е да отдели BSD функционалността в отделен процес на системата, изчиствайки по този начин Mach от всички лицензионни проблеми. Тази версия е 3.0 и излиза през 1989. Интересно е, че системата за виртуална памет на Mach по-късно е прехвърлена върху BSD. По-късно този клонинг се развива до UVM, който обаче не е върнат обратно в Mach.

Развитието на Mach продължава в Университета на Юта, където през 1984 излиза Mach 4, която е и последната версия на оригиналния Mach. Там е пренаписана поддръжката на компютърната архитектура IA-32 (x86) на Intel, както и са включени драйверите на версия 2.0 на изгряващата звезда Linux. От Mach 4 е създаден GNU Mach 1, който се използва от Hurd. През това време в Университета на Юта, използвайки опита си от Mach, създават библиотеката за операционни системи oskit, където се използват драйверите на Linux 2.2. Започвайки като частен проект, през 1999 Роланд МакГрад променя GNU Mach да използва изцяло oskit. По-късно е обявено, че това ще е GNU Mach 2, но към настоящия момент този клон е нестабилен и не се развива от никого.

Mach използва някои понятия, които са по-бедни на съдържание от обикновено. Основната единица е задача, която обикновено се нарича процес, което е по-технически термин на програма или приложение. Задачата в Mach не е нищо повече от контейнер на останалите понятия: адресно пространство, нишки, портови права.

Както и случая с обектите за памет, прякото програмиране чрез предаване на съобщения е трудна задача, изискваща много внимание и програмиране. Затова често се използват генератора на код MiG (Mach Interface Generator). Приликите с COM и CORBA не са случайни – имат общи корени. Мисленето при този подход се променя към обектно-ориентирано. Вместо да се предават съобщения, имаме манипулатори на обекти (object references). Чрез тези манипулатори програмите извикват методи на обектите. Списъкът на методите на един обект се нарича интерфейс. Ето пример за извикване на метод:

error_t err;
mach_port_t port;
void *buf;
size_t buf_len;
off_t offset;
size_t size;
err = io_read (port, &buf, &buf_len, offset, size);

Първият аргумент на метода е манипулатора на обекта, който всъщност е порт. По традиция тези методи се наричат отдалечени извиквания на процедури (Remote Procedure Calls), защото отвънка изглежда просто като извикване на функция, но зад това извикване стоят много действия, докато заявката стигне до същинската функция в някоя друга задача или някоя друга машина и резултатът се върне.

kern_return_t
trivfs_S_io_read (struct trivfs_protid *cred,
                  mach_port_t reply,
                  mach_msg_type_name_t replytype,
                  char **data,
                  mach_msg_type_number_t *datalen,
                  off_t off,
                  mach_msg_type_number_t amt)
{
  return EOPNOTSUPP;
}

Остава да разгледаме въпроса как така от клиентското извикване на io_read се стига до trivfs_S_io_read, включително и връщането на резултата обратно. Всичко това се изпълнява от генериран от mig код. Този код генерира две библиотеки: една за сървъра и една за клиенти. Всички подробности по приемането и изпращането на съобщения се съдържа в тези библиотеки. За целта обаче mig трябва да има подробна информация за отдалечените процедури. Тя се доставя от файл, написан на специален език за определяне на интерфейси (Interface Definition Language). Този език е специфичен за mig, както са специфични и езиците на COM и CORBA, които също се наричат IDL. Ето примерно описание на интерфейс, взето от hurd/io.defs:

subsystem io 21000;

#include <hurd/hurd_types.defs>
routine io_read (
        io_object: io_t;
        RPT
        out data: data_t, dealloc;
        offset: loff_t;
        amount: vm_size_t);

Може да се каже, че UNIX® наложи дървовидното категоризиране на файлове, както е разпространено навсякъде сега. По този начин всички файлове са разпръснати в директории^[5]. От своя страна директориите се водят като различен вид файлове, които са вътре в други директории. Една директория е по-специална: кореновата директория – началото на всички други директории.

Тази проста представа за файловете и директориите обаче не е достатъчна. В компютрите понякога има няколко диска, особено в сървърите, и всеки диск има по няколко дяла, които съдържат файлови системи. Затова някои директории на файловата система, така, както се виждат от потребителите, всъщност препращат към файлова система на друг дял. Тези директории се наричат точки на монтиране и е нормално в монтирана файлова система да има друга точка на монтиране. По този начин потребителят все още продължава да има единен поглед върху всички файлови системи на всички дялове, или поне тези, които са монтирани.

Концепцията за монтиране на файлови системи има интересни развития. Например не е задължително да се монтира дял от диск, а например споделена директория от друг компютър, чрез протокола NFS. Или пък направо FTP директория на някой сървър. А може и въобще да не става въпрос за физически файлове, а за генерирано съдържание, например /proc/123/cmdline в Linux съдържа командния ред, довел до стартирането на процес 123. Или стандартният начин за включване на маршрутизирането в Linux чрез командата echo 1 > /proc/sys/net/ipv4/ip_forward.

Продължавайки в същия дух, стигаме до понятието транслатор, както се употребява в Hurd. Транслаторът е директория или файл, заявките към който се изпълняват от обикновена програма, обикновено наричана сървър на транслатора. От своя страна в транслираната файлова система може да има още транслатори, които да препращат към сървъри.

Така получаваме една “разпределена” файлова система, в смисъл, че обработката на файловите операции, като четене и запис например, се извършва между разпръснати процеси. Транслатори може да поставя всеки потребител, което значи, че един потребител може влезе в транслирана от друга потребител част от файловата система. Несъмнено това поставя нови предизвикателства пред безопасността на цялата операционна система, които още не са добре проучени.

Както беше посочено в началото, микроядрото осигурява само и единствено общуването между отделните потребителски процеси^[6]. Затова голяма част от Hurd-а се заема от разнообразни библиотеки, които улесняват системното програмиране. Важните за нашето разглеждане са следните:

Всички общувания между процесите в Hurd се осъществяват чрез интерфейси. В тях има изброени функциите и техните входни и изходни параметри. Описват се във файлове с разширение defs. Следните интерфейси се използват пряко във файловите системи:

Всички тези интерфейси се реализират от libdiskfs и са точно отражение на основните единици във виртуалната файлова система (VFS) в Linux. Библиотеката се опитва да свърши максимално работа, използвайки callback функции на програмата. От своя страна програмата се очаква да е получила store, който да достъпва с libstore.

Така стигаме до ограничението от 1G за файлова система. Понеже кодът е писан около 1995–1996, целият store на файловата система се изобразява върху адресното пространство на сървърския процес за файловата система. Заявките към това адресно пространство се управляват чрез libpager, който от своя страна работи със store-а. И понеже цялото адресно пространство е 32-битово, имаме 4G, половината от които обаче се използват за системни цели. Затова за изобразяването на целия store се използват гигабайт и нещо.

В ядрото Linux достъпа до блоковите устройства почти винаги се извършва през block layer. Основните операции в него са взимане на блок и даване на блок, като явно се указва дали блокът е променен при даването. Същият подход се използва и в решаването на ограничението от 1G за store на файлова система.

Отбелязва началото на атомарно действие, предизвикано от потребител. Тази потребителска функция трябва да създаде структура rpc_context и да върне указател към нея в *context. cred е стойността, която да се запише в структурата, като тя може да е NULL.

Отбелязва края на атомарно действие, предизвикано от потребител.

Първата стъпка в правенето на дипломната работа беше премахване на гореспоменатото ограничение от 2G за големината на файл. За решаване на този проблем се използва като отправна точка реализирания в почти всички операционни системи кеш на буферите (buffer cache), но по различен начин.

Имаме кеш от буфери, в които слагаме съдържанието на блоковете от диска. Сървърът на файловата система иска все повече и повече блокове и в един момент целия кеш се запълва. Въпросът е съдържанието на кой буфер да изхвърлим, за да сложим новия блок.

Преди всички ние трябва да сме сигурни, че няма да изхвърлим буфер, който се използва в момента. За целта всеки буфер има брояч на потребителите (reference count). Един буфер никога не сменя съдържанието си, ако има потребител.

Целият код на ext2fs обаче въобще не води такова “счетоводство” за това кой използва каква част от диска. Затова всичко беше променено да използва тази нова дисциплина за работа с блок от диска.

От останалите буфери трябва да изберем някой, който вече да има ново съдържание. В помощ на това идва микроядрото, което има глобален поглед върху това кои страници от адресното пространство се употребяват повече от други. Най-малко употребяваните просто се изваждат, когато е нужна памет за други страници. Това изваждане се прихваща и така се знае във всеки един момент от време кои страници са извадени и кои са заредени в адресното пространство. За нов блок винаги се избира буфер, чиято страница е извадена и който няма потребители.

Сега цялата тази логика е изнесена в libscache.

Навсякъде за достъп до блоковете се използват функциите за взимане и освобождаване на буфери на libjstore. Осигуряват се необходимите функции, за да може libe3diskfs да започва и приключва атомарни промени. pokel.c въобще не се ползва.