"Складні" файлові системи

Структури "складних" файлових систем відрізняються великою різноманітністю, проте можна виділити декілька загальних принципів.
Зазвичай файлова система починається із заголовка, або, як це називається в системах сімейства Unix суперблоку (superblock). Суперблок зберігає інформацію про розміри дискового тому, відведеного під ФС, покажчики на початок системних структур даних і іншу інформацію, залежну від типа ФС. Наприклад, для статичних структур може зберігатися їх розмір. Часто суперблок містить також магічне число — ідентифікатор типа файлової системи. Аналог суперблоку існує навіть в FAT — це так звана завантажувальний запис (boot record).
Практично всі сучасні ФС розділяють список вільних блоків і структури, що відстежують розміщення файлів. Найчастіше замість списку вільних блоків використовується бітова карта, в якій кожному блоку відповідає один біт: занят/свободен. У свою чергу, список блоків для кожного файлу зазвичай пов'язаний з описувачем файлу. На перший погляд, ці описувачі здається природним зберігати в каталозі, але їх, як правило, виносять в окремі області, часто зібрані в спеціальні області диска — таблицю инодов, метафайл і так далі Таке рішення зменшує об'єм каталога і, відповідно, прискорює пошук файлу по імені. До того ж багато ФС сортують записи в каталозі по імені файлу, також з метою прискорення пошуку. Зрозуміло, що сортування записів меншого розміру відбувається швидше.
У файловій системі HPFS, використовуваній в OS/2 і Windows NT, кожен запис в каталозі містить ім'я файлу і покажчик vtajhode (файловий запис). Каталоги в цій ФС організовані у вигляді в-дерев і відсортовані по іменах файлів.
Файловий запис займає один блок на диску і містить список так званих extent ("розширень") — (біля цього терміну немає прийнятного російського аналога. У перекладах документації по OS/360 (ОС ЄС) так і писали: экстент.). Кожен экстент описує безперервну послідовність дискових блоків, виділених файлу. Він задає початковий блок такої послідовності і її довжину. Замість списку вільних блоків використовується бітова карта диска, в якій кожному блоку відповідає один біт: занят/свободен.
Потрібно відзначити, що ідея экстентов далеко не нова: аншюгичная структура використовується в деяких версіях Unix з початку 80-х років, а витоки цієї ідеї втрачаються в глибині 60-х.
Файловий запис зазвичай розміщується перед початком першого экстента файлу, хоча це і не обов'язково. Вона займає один блок (512 байт) і може містити до десяти описувачів экстентов (мал. 11.11). Крім того, вона містить інформацію про час створення файлу, його ім'я і розширені атрибути (див. разд. Тип файлу). Якщо для списку экстентов або розширених атрибутів місця не хапає, то для них також виділяються экстенты. В цьому випадку экстенты розміщуються у вигляді в-дерева для прискорення пошуку. Максимальна кількість экстентов у файлі не обмежена нічим, окрім розміру диска.
Призначена для користувача програма може вказати розмір файлу при його створенні. В цьому випадку система відразу спробує виділити місце під файл так, щоб він займав якомога менше экстентов. Якщо програма не повідомила розміру файлу, використовується значення за умовчанням. Фактично, HPFS розміщує місце під файл за принципом worst fit (найменш відповідного), починаючи виділення з найбільшої безперервної ділянки вільного простору. В результаті фрагментованими виявляються лише файли, довжина яких збільшувалася багато разів або ж ті, які створювалися при майже заповненому диску. При нормальній роботі файл рідко займає більше 3—4 экстентов.

Мал. 11.11. Каталог і файловий запис в HPFS

Ще один цікавий наслідок вживання стратегії worst fit полягає в тому, що простір, звільнений стертим файлом, зазвичай використовується не відразу. Наголошувалися випадки, коли файл на активно використовуваному диску удавалося відновити через декілька днів після стирання.
Екстенти відкритих файлів і карта вільних блоків під час роботи розміщуються в ОЗУ, тому продуктивність такий ФС в більшості ситуацій набагато (у 1,5—2 рази і більш) вищий, ніж біля FAT з тим же об'ємом кеша, при сповна прийнятних потребах в пам'яті і розмірі кластера 512 байт.
Видно також, що структура HPFS спрощує довільний доступ до файлу: замість дослідження ланцюжка блоків нам потрібно прослідити ланцюжок экстентов, яка набагато коротше.
Детальніший опис структури HPFS можна знайти в статті [РС Magazine 1995|. Користувачі OS/2 вважають за доцільне форматувати всі розділи ємкістю більш 12SM під HPFS, оскільки при цьому виграється швидкість і збільшується ефективність використання дискового простору; крім того, зникає необхідність в дефрагментацин і з'являється можливість створювати файли і каталоги з довгими іменами, що не укладаються в модель 8.3, прийняту в MS DOS.
За ці переваги доводиться платити нестійкістю до збоїв (проблема стійкості до системних збоїв обговорюється в разд. Стійкість ФС до збоїв). На відміну від ДОС, спонтанні руйнування системи з подальшим зависанням в OS/2 трапляються відносно рідко, навіть при запуску програм, що свідомо містять помилки (як при розробці або тестуванні прикладного програмного забезпечення). З іншого боку, на практиці "нестійкість" наводить лише до того, що після аварійного перезавантаження автоматично запускається програма відновлення ФС, що збільшує час перезавантаження у декілька разів; реальний же ризик втратити дані при збої не вище, а як показує практика, навіть істотно нижче, ніж при використанні FAT, тому гра явно коштує свічок.
Найцікавіша структура файлових систем в ОС сімейства Unix. У цих ФС каталог не містить майже жодній інформації про файл. Там зберігається лише ім'я файлу і номер його инода (i-node — очевидно, скорочення від index node: індексний запис). Іноди всіх файлів в даній ФС зібрані в таблицю, яка так і називається: таблиця инодов. У ранніх версіях Unix таблиця инодов займала фіксований простір на початку пристрою; у сучасних файлових системах ця таблиця розбита на ділянки, розподілені по диску.
Наприклад, у файловій системі BSD Unix FFS (Fast File System — швидка файлова система), яка в Unix SVR4 називається просто UFS (Unix File System), диск розбитий на групи циліндрів. Кожна група циліндрів містить копію суперблоку, бітову карту вільних блоків для даної ділянки і таблицю инодов для файлів, розташованих в межах цієї ділянки (мал. 11.12). Така розподілена структура має дві переваги.

• Прискорення доступу до системних структур даних. Коли системні дані розташовані поблизу від блоків призначених для користувача даних, зменшується відстань, на яку переміщаються голівки дисковода.
• Підвищена стійкість до збоїв носія. При пошкодженні ділянки поверхні диска втрачається лише невелика частина системних даних. Навіть втрата суперблоку не наводить до втрати структури файлової системи.

Мал. 11.12. Блоки циліндрів FFS

Інод зберігає інформацію про сам файл і його розміщення на диску (мал. 11.13, приклад 11.2). Інформаційна частина инода може бути отримана системним викликом
int stat(const char * fname, struct stat * buf);
Формат структури stat описаний в багатьох керівництві по мові С. Ос UNIX і стандарту POSIX, наприклад, в роботі (Керніган-рітчи 2000|. Ця структура містить наступну інформацію.

• Тип файлу. Досліджуючи це поле, можна зрозуміти, є даний об'єкт файлом даних або спеціальним файлом. У цьому ж полі закодовані права доступу до файлу.
• Ідентифікатори власника файлу і групи. Разом з правами доступу ці два ідентифікатори утворюють список контролю доступу файлу (см разд. Списки контролю доступу).
• Час:
  • створення файлу;
  • останній модифікації файлу;
  • останнього доступу до файлу.
• Довжина файлу. Для спеціальних файлів це поле часто має інший сенс.
• Ідентифікатор файлової системи, в якій розташований файл.
• Кількість зв'язків файлу. Це поле заслуговує на окреме обговорення.

Мал. 11.13. Каталоги і иноды файлових систем сімейства Unix

Приклад 11.2. Структура инода файлової системи ext2fs

/* * Структура даних инода second extended file system, лічена в пам'ять
*/
i- struct ext2_inode_info { _u32 i_data[15]; _ u32 i_flags; _u32 i^faddr; _ u8 i_frag_no; _ u8 i_f rag_size; _ u!6 i_osync; _ u32 i_file_acl; _ u32 i_dir_acl; _ u32 i_dtime;
_ u32 not_used_l; /* FIX: не используется/зарезервировано для 2.2 */ _ u32 i_block_group; _ u32 i_next_alioc_block;
u32 i next alloc goal; _ u32 i_prealloc_block;
u32 i prealloc count; __ u32 i_high_size;
int i_new _inode : 1 ; /* Цей инод тільки що вьделен */

Структура, що описує фізичне розміщення файлу на диску, недоступна призначеним для користувача програмам. Власне, формат цієї структури може бути не дуже елегантний. Наприклад, у файловій системі Veritas це список экстентов, схожий на HPFS; у файлових системах s5, Xenix і FFS це масив з 13 чисел, задаючих номери фізичних блоків файлу. Якщо файл в s5 містить більше десяти блоків (тобто його довжина більше 5 Кбайт), то передостанні три покажчики позначають не блоки даних, а так звані непрямі блоки (indirection blocks) у яких зберігаються покажчики на наступні блоки даних і, можливо, на наступні непрямі блоки.
Найцікавіша особливість ФС сімейства Unix полягає не в цьому. Уважний читач, можливо, відмітив, що инод не містить імені файлу. З іншого боку, він містить лічильник зв'язків (link) — заслань на цей файл з каталогів. Таким чином, на один і той же инод можна посилатися з різних каталогів або з одного каталога під різними іменами (мал. 11.14). Іншими словами, один і той же файл в цих ФС може мати декілька різних імен. Саме це і малося на увазі, коли го вірилося, що структура каталогів в ОС UNIX не зобов'язана бути деревом.
Ця властивість надає неоцінимі можливості для організації не рархии каталогів, але має і деякі оборотні сторони.

1. 1. Створення декількох зв'язків для каталога потенційно опасно— воно може привести до виникнення кільця, в якому каталог є своїм власним підкаталогом. Відстежувати таку ситуацію складно тому розробники ОС UNIX заборонили створювати додаткові імена для каталогів.
2. 2. Видалення файлу перетворюється на проблему: аби видалити файл, потрібно прослідити всі його зв'язки. Тому UNIX не має засобів для удатсния файлу, а володіє лише системним викликом unlink — видалити зв'язок. Коли біля файлу не залишається зв'язків, він дійсно віддаляється. Цей підхід сповна розумний, але також має несподівану оборотну сторону: оскільки тепер стирання файлу — це операція не над файлом, а над каталогом, то для видалення файлу не потрібно мати жодних прав доступу до нього. Досить мати право запису в каталог.
   На практиці, механізм захисту від стирання окремих файлів передбачений — при установці в атрибутах каталога так званого sticky bit ("липкий біт"), система забороняє стирати файли, для яких ви не маєте права запису, але і цей механізм не позбавлений недоліків.
3. 3. Такі зв'язки (звані ще жорсткими (hard) зв'язками), як легко зрозуміти, можуть створюватися лише в межах однієї файлової системи, оскільки кожна ФС має власну таблицю инодов, і відповідно власну їх нумерацію.

Мал. 11.14. Жорсткі зв'язки в Unix

Остання обставина різко зменшує корисність жорстких зв'язків для організації ієрархії каталогів. Ця проблема була усвідомлена ще в 70-і роки, і програмісти з групи BSD придумали цікаве нове поняття - символічний зв'язок (symbolic link) абоsymlink.
Символічний зв'язок є спеціальним файлом. Замість блоків даних инод такого файлу містить текстовий рядок — ім'я того файлу, з яким створений зв'язок (мал. 11.15). Це може бути файл з іншої файлової системи, у тому числі і з такої, яка сама по собі не підтримує ні жорстких, ні символічних зв'язків, наприклад, FAT, HPFS або файловий сервер Novell Netware. Такого файлу може і взагалі не існувати, наприклад, тому, що його вже видалили, або тому, що файлова система, в якій він знаходиться, не змонтована, або просто тому, що ім'я було задане неправильно. Тоді спроби відкрити символічний зв'язок завершуватимуться невдачею з кодом помилки "файлу не існує".

Мал. 11.15. Символічний зв'язок

Єдиним недоліком символічних зв'язків є їх відносно низька "дуракоустойчивость" (fool-tolerance): безглуздий користувач може не розпізнати ситуації, коли символічний зв'язок вказує в нікуди. Зате вони забезпечують повну свободу в розміщенні і іменуванні файлів.

Приклад з життя
На двох Unix-системах з іменами orasrv і Indy встановлений один і той же програмний продукт: редакторная система GNU Emacs. Бінарні завантажувальні модулі для цих систем розрізняються, але велика частина Emacs — це файли на мові Emacs Lisp, які з однаковим успіхом можуть використовуватися обома системами. Тому у адміністратора системи виникає бажання використовувати одну копію lisp-файлов. При цьому Emacs встановлена таким обра зом, що вона шукає всі свої lisp-файлы в каталозі /usr/local/lib/emacs/19.27/lisp Зміна цього каталога зажадала б часткового переустановлення продукту Але його не треба міняти! Ми просто подмонтируем на машині orasrv каталог / машини Indy як /fs/lndy і виконуємо наступні команди прикладу 11.3.

Приклад 11.3. Перенесення каталога без зміни його путнього імені

cd /usr/local/lib/emacs/19.27 # перейти в заданий каталог rm -Rf lisp
# стерти каталог lisp зі всім вмістом
In -s /fs/Indy/usr/local/lib/emacs/19.27/lisp lisp
# створити символічний зв'язок з ім'ям lisp з відповідним
# каталогом на машині Indy

Вся операція разом з її планеруванням займає близько двох хвилин. Звільняється близько 9 Мбайт дискового простору. Emacs нічого не помічає, і працює без всяких проблем.
Через тиждень у адміністратора виникає ідея, що для зручності адміністрування непогано було б вмонтовувати з orasrv не всю файлову систему Indy, а лише її каталог /home. За чим справа стала: переносимо на Indy каталог lisp в каталог /home/emacs/19.27/lisp; створюємо в старому каталозі символічний зв'язок з новим; редагуємо файл /etc/mnttab на-машині orasrv так, щоб з Indy вмонтовувався лише /home; міняємо символічний зв'язок каталога lisp на машині orasrv. Заставляємо orasrv подмонтировать диски відповідно до нового /etc/mnttab. Готово.
Операція займає трохи більше двох хвилин, тому що потрібно переносити 9 Мбайт з однієї файлової системи в іншу. Emacs знову нічого не помічає і знову працює без всяких проблем. Адміністратор щасливий. Всі задоволено. Порівняєте цей опис з враженнями користувача, який намагається перемістити з одного Дос-вського драйву на іншій типову програму для Win32, яка при установці записує в багато місць своєї конфігурації і системного реєстру повне ім'я каталога, в який її ставили...

Символічні зв'язки властиві лише системам сімейства Unix. Навпаки, еквіваленти жорстких зв'язків є в інших ОС. Фактично жорсткі зв'язки можна створювати в будь-який ФС, де каталоги містять заслання на централізовану базу даних замість самого дескриптора файлу.

Жорсткі зв'язки в VMS і Windows NT/2000/XP
Наприклад, у файловій системі VAX/VMS дані про розміщення файлів на диску зберігаються в спеціальному індексному (index) файлі; каталоги ж зберігають лише індекси записів в цьому файлі. Основна відмінність цієї структури від прийнятої в Unix полягає в тому, що замість статичної таблиці або набору таблиць використовується динамічна таблиця, простір для якої виділяється тим же методом, що і для призначених для користувача файлів. Цей же підхід реалізований у файловій системі NTFS, використовуваній в Windows NT/2000/XP, але в ній індексний файл називається MFT (Main File Table — головна таблиця файлів). Детальніший опис структури NTFS наводиться в статті [www.digit-life.com NTFS].
VAX/VMS і Windows NT дозволяють створювати додаткові імена для файлів, хоча в VMS утиліти відновлення ФС видають попередження, виявивши таке додаткове ім'я. Всі імена файлу в цих ФС зобов'язані знаходитися в одній файловій системі. Крім того, операція видалення файлу в VMS поводиться не так, як в Unix: застосування операції видалення до будь-якого з імен наводить до видалення самого файлу, навіть якщо існували і інші імена.