Лекція 23 Структури даних UFS1 і UFS2

↑

▷ Содержание

⇐ ПредыдущаяСтр 16 из 17Следующая ⇒

В цьому розділі приведені описи структур даних файлових систем UFS1 і UFS2. Методи аналізу UFS наведено в розділі 1, а тут розглянуто структури даних і їх місцезнаходження в тестовій файловій системі. Структури даних UFS інколи містять декілька полів для зберігання одного значення в різних форматах. Скажімо, розмір блоку зберігається вираженим як у фрагментах, так і в байтах. Завдяки наявності різних форматів ОС не приходиться кожного разу заново перераховувати одні і ті ж параметри. Хоча деякі ОС можуть вимагати, аби в обох полях використовувалися еквівалентні значення, наявність дублюючих даних не є формально необхідним. Та все ж визначити, яким з форматів потрібно вважати основним, а який — похідним, нелегко. Я виділятиму один з форматів як основний, але цей вибір може не поширюватися на всі програми або ОС.

Суперблок UFS1

У файловій системі UFS суперблок містить основні дані, що відносяться до категорії файлової системи, але в UFS1i UFS2 використовуються різні структури даних. Суперблок UFS1 знаходиться в секторі 16, а для його зберігання виділяється 2048 байт, але білшість даних, що зберігаються, необов'язкові або заповнений нулями. Далі я описуватиму лише обов'язкові дані, але в наступній таблиці присутні всі необов'язкові поля. В таблиці 23.1 перераховані поля суперблоку UFS1, використовуваного в FREEBSD, NETBSD і OPENBSD.

Таблиця 23.1 – Структура даних суперблоку UFS1

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

В байті 128 знаходиться поле методу оптимізації виділення блоків. В даний час для нього визначено два значення. Якщо поле рівне 0, ОС прагне заощадити час при виділенні нових блоків; це може привести до неефективного використання простору і фрагментації в міру заповнення файлової системи. Якщо поле дорівнює 1, ОС прагне оптимізувати витрати дискового простору при виділенні нових блоків і знайти ідеальне місцезнаходження. З іншого боку, це може уповільнити створення нових файлів. Знання методу оптимізації може виявитися корисним під час відновлення файлів.

Починаючи з байту 208, в суперблоці розташований набір прапорів. Перший прапор встановлюється при модифікації суперблоку і скидається при монтуванні. Прапор в байті 209 обнуляється, якщо файлова система пройшла перевірку на «чистоту» при монтуванні. Прапор в байті 210 встановлюється рівним, якщо файлова система була змонтована лише для читання. Нарешті, байт 211 може містити будь-які прапори з набору, представленого в таблиці. 23.2.

Таблиця 23.2 – Прапори поля загальних прапорів в суперблоці

Поле в байтах 1234-1237 ідентифікує тип індексного вузла, який використовується для зберігання метаданих файлу. Поле дорівнює 2 для індексних вузлів 4.4BSD або 0x0fffffff для індексних вузлів 4.2BSD. Останні дані суперблоку не є обов'язковими; вони можуть містити, а можуть і не містити дійсні дані.

Розглянемо систему OpenBSD. Суперблок знаходиться в секторі 16, а для його зберігання виділено 4 сектори, тому команда dd має вигляд, представлений в лістингу 23.1.

Лістинг 23.1 – Команда dd

# dd if=openbsdl.dd bs=512 skip=16 count=4 | xxd

0000000: 0000 0000 0000 0000 1000 0000 1800 0000.................

0000016: 2000 0000 1001 0000 2000 0000 f0ff ffff...............

0000032: dc9d 0f41 1027 0000 ff24 0000 0200 0000...A.'...$.......

0000048: 0020 0000 0004 0000 0800 0000 0500 0000................

0000064: 0000 0000 3с00 0000 00e0 ffff 00fc ffff....<............

0000080: 0d00 0000 0a00 0000 0700 0000 0008 0000.................

0000096: 0300 0000 0100 0000 0008 0000 00fe ffff.................

0000112: 0900 0000 0008 0000 4000 0000 0200 0000........@........

0000128: 0000 0000 3f00 0000 0100 0000 0000 0000....?............

0000144: 2c9d 0f41 8f5a 19a2 1001 0000 0004 0000...A.Z...........

0000160: 0008 0000 1000 0000 3f00 0000 f003 0000........?........

0000176: 1400 0000 1000 0000 8007 0000 801f 0000.................

0000192: 0400 0000 fe03 0000 e50e 0000 1000 0000.................

0000208: 0001 0000 2f6d 6e74 0000 0000 0000 0000..../mnt.........

0000224: 0000 0000 0000 0000 0000 0000 0000 0000.................

[…]

0000832: 0000 0000 0000 0000 0000 0000 00e6 d2d0.................

0000848: 0038 d3d0 003c d3d0 0100 0000 0000 0000.8...<...........

[…]

0001184: 0000 0000 0000 0000 0000 0000 0040 0000..............@..

0001200: 4000 0000 0000 0000 0000 0000 0040 0000 @................

[…]

0001312: 0000 0000 0700 0000 3с00 0000 0200 0000........<........

0001328: ff7f 0101 0840 0000 fflf 0000 0000 0000.....@...........

0001344: ff03 0000 0000 0000 0000 0000 0100 0000.................

0001360: 0100 0000 6005 0000 6205 0000 5419 0100....’...b...T....

0001376: 0000 0101 0101 0101 0101 0101 0101 0101.................

Дана файлова система працює на платформі IA32, тому в ній використовується формат з прямим порядком байтів. Якби файлова система відносилась до платформи із зворотним порядком байтів (скажімо, Sparc), то байти в кожному числовому полі слід було б переставити.

З вмісту байтів 8-11 видно, що резервні суперблоки зберігаються із зсувом 16 фрагментів (0x10) від базової адреси кожної групи циліндрів. Байти 12-15 показують, що дескриптор групи зберігається із зсувом 24 фрагменти (0x18) від базової адреси, а байти 16-19 — що таблиця індексних вузлів зміщена на 32 фрагменти (0x20).

Аби обчислити базову адресу для групи циліндрів UFS1, слід почати з байтів 24-27, в яких зберігається дельта 32 (0x20). Таким чином, в групі 0 база відповідає фрагменту 0, а в групі 1 — фрагменту 32. Маска циклу в байтах 28-31 рівна 0xfffffff0; це означає, що в номері групи нас цікавлять тільки 4 останніх біта. Отже, через кожних 16 груп відбувається повернення до початку, і зсув бази знову стає рівним 0. В даному прикладі в групи 15 зсув бази відповідає фрагменту 480, а в групи 16 воно повертається до фрагмента 0.

У байтах 32-35 зберігається час останнього запису у вигляді кількості секунд з 1 січня 1970 р. (GMT). Байти 36-39 показують, що система містить 10000 фрагментів (0x2710), а байти 44-47 — що в ній існує всього дві групи циліндрів. Розмір кожного блоку задається в байтах 48-51; ми бачимо, що він рівний 8192 байтам (0x2000). Розмір фрагмента в байтах 52-55 дорівнює 1024 байтам (0x0400). Для запобігання частому діленню цих двох чисел кількість фрагментів в блоці зберігається в байтах 56-59; у нашому випадку воно дорівнює 8.

По вмісту байтів 104-107 ми визначаємо, що суперблок займає 2048 байт (0x0800). Байти 152-155 задають місцезнаходження зведення груп циліндрів; у даній файловій системі вона знаходиться у фрагменті 272. Розмір зведення визначається байтами 156-159 і дорівнює 1024 байтам, або одному фрагменту. Кількість індексних вузлів в групі циліндрів (байти 184-187) в цій файловій системі дорівнює 1920 (0x0780). Кількість фрагментів в групі циліндрів (байти 188-191) дорівнює 8064 (0х1f80).

Поле прапорів починається з байта 208. Його перший байт дорівнює 0; це означає, що суперблок був змінений після останньої модифікації. Згідно байту 209, в системі використовуються м'які залежності, а прапори в байтах 210 і 211 знаходяться в стані за умовчанням. У байті 212 починається рядок останньої точки монтування; тестова файлова система востаннє вмонтовувалася в каталог /mnt/. Останні поля можна обробити самостійно. Вивід програми fsstat для цього образу був раніше наведений.

Суперблок UFS2

У суперблоці UFS2 зберігається та ж базова інформація, що і у версії UFS1, але з нього виключено багато невживаних полів, що дещо спростило структуру блоку. Деякі з 32-розрядних полів, що збереглися, були замінені 64-розрядними версіями. Суперблок UFS2 зазвичай знаходиться в секторі 128. Поля версії, використовуваної в FREEBSD і NETBSD, перераховані в таблиці. 23.3.

Таблиця 23.3 – Структура даних суперблоку UFS2

Деякі поля перемістилися на інші місця. З цікавих змін можна відзначити лише те, що точка монтування стала коротша, а в суперблоці з'явилося поле для імені тому. Поле прапорів тепер займає 4 байти замість одного, але в ньому використовуються ті ж прапори, які були перераховані в таблиці 23.2. Також звернемо увагу на сигнатуру, що змінилася, — по ній UFS1 можна відрізнити від UFS2.

В лістингу 23.2 наводимо вміст суперблоку UFS2 для системи FREEBSD 5:

Лістинг 23.2 – Вміст суперблоку UFS2

# dd if=freebsd5.dd skip=128 count=4 | xxd

0000000: 0000 0000 0000 0000 2800 0000 3000 0000........(...0...

0000016: 3800 0000 d801 0000 0000 0000 0000 0000 8...............

0000032: 0000 0000 0000 0000 0000 0000 0400 0000................

0000048: 0040 0000 0008 0000 0800 0000 0800 0000.@..............

0000064: 0000 0000 0000 0000 00c0 ffff 00f8 ffff................

0000080: 0e00 0000 0b00 0000 0800 0000 0008 0000................

0000096: 0300 0000 0200 0000 0008 0000 0000 0000................

0000112: 0000 0000 0008 0000 4000 0000 0000 0000........@.......

0000128: 0000 0000 0000 0000 0000 0000 0000 0000................

0000144: adb2 0f41 fd0l 4al7 0000 0000 0008 0000...A..J.........

0000160: 0008 0000 0000 0000 0000 0000 0003 0000................

0000176: 0000 0000 0000 0000 0005 0000 b813 0000................

0000192: 0000 0000 0000 0000 0000 0000 0000 0000................

0000208: 0000 0080 2f6d 6e74 0000 0000 0000 0000..../mnt........

[...]

0000672: 0000 0000 0000 0000 5546 5332 0000 0000........UFS2....

[...]

0000832: 0000 0000 0000 0000 1038 66c3 0030 66c3.........8f..0f.

0000848: 0038 66c3 0000 0000 0000 0000 0040 0000.8f..........@..

[...]

0000992: 0000 0000 0000 0000 0000 0100 0000 0000................

0001008: 0400 0000 0000 0000 f308 0100 0000 0000................

0001024: e213 0000 0000 0000 1800 0000 0000 0000................

[...]

0001072: bdb4 0f41 0000 0000 c04e 0000 0040 0000...A.....N......

0001088: d74b 0000 0000 0000 d800 0000 0040 0000.K..............

[...]

0001184: 0000 0000 0000 0000 0000 0000 0040 0000.............@..

0001200: 4000 0000 0000 0000 0000 0000 0000 0000 @...............

[...]

0001312: 0000 0000 0800 0000 7800 0000 0000 0000........x.......

0001328: ffff 0202 1080 0000 ff3f 0000 0000 0000.........?......

0001344: ff07 0000 0000 0000 0000 0000 0000 0000................

0001360: 0000 0000 0000 0000 0000 0000 1901 5419..............T.

0001376: 0000 0101 0101 0101 0101 0101 0101 0101................

З байтів 8-11, 12-15 і 16-19 видно, що суперблок зберігається із зсувом 40 фрагментів (0x28) від початку кожної групи циліндрів, дескриптор зміщений від початку на 48 фрагментів (0x30), а індексна таблиця — на 56 фрагментів (0x38). Байти 44-47 показують, що в системі існує чотири групи циліндрів.

Розмір блоку задається в байтах 48-51; ми бачимо, що він дорівнює 16 384 байтам (0x4000). Розмір фрагменту (байти 52-55) дорівнює 2048 байтам (0x0800). Байти 184-87 показують, що група циліндрів містить 1280 (0x0500) індексних вузлів, а байти 188-191 — що група містить 5048 фрагментів (0х13b8). Загальна кількість фрагментів задається в байтах 1080-1087. У тестовій файловій системі воно дорівнює всього 20160 байтам.

В лістингу 23.3 представлено результат виконання fsstat для образу UFS2:

Лістинг 23.3 – Результат виконання fsstat для образу UFS2

# fsstat -f freebsd freebsd5.dd

FILE SYSTEM INFORMATION

- - - - - - - - - - - - - - - - - - - -

File System Type: UFS 2

Last Written: Tue Aug 3 10:52:29 2008

Last Mount Point: /mnt

Volume Name: UFS2

System UID: 0

METADATA INFORMATION

- - - - - - - - - - - - - - - - - - - -

Inode Range: 0 – 5119

Root Directory: 2

Num of Avail Inodes: 5090

Num of Directories: 4

CONTENT INFORMATION

- - - - - - - - - - - - - - - - - - - -

Fragment Range: 0 - 20159

Block Size: 16384

Fragment Size: 2048

Num of Avail Full Blocks: 2291

Num of Avail Fragments: 24

Зведення груп циліндрів

Як у UFS1, так і в UFS2 присутні фрагменти, що містять структури даних зведення груп циліндрів. Ці структури збігаються в обох версіях UFS і містять статистичну інформацію про кожну групу циліндрів. Структури утворюють таблицю, кожен елемент якої відповідає одній групі. Адреса і розмір зведення задаються в суперблоці. У таблиці 23.4 перераховані поля записів таблиці.

Таблиця 23.4 – Структура даних записів зведення груп циліндрів

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

В тестовому образі файлової системи UFS1 зведення груп циліндрів розташовувалось в блоці 272 і займало 1024 байти. Вміст відповідного фрагменту виглядає так:

# dcat -f openbsd openbsd.dd 272 | xxd

0000000: 0200 0000 2f03 0000 7807 0000 0b00 0000..../...x.......

0000016: 0200 0000 cf00 0000 6d07 0000 0500 0000........m.......

У першому рядку виводиться запис групи 0. З неї видно, що група складається з двох каталогів з 815 (0x032f) вільних блоків. Байти 8-11 показують, що в групі є 1912 (0x0778) вільних індексних вузлів, а байти 12-15 — що в неповних блоках міститься 11 (0х0b) вільних фрагментів. Другий рядок містить дані другої групи.

Для образів UFS програма fsstat з пакету TSK виводить інформацію про групи циліндрів. Приклад вихідних даних fsstat для тестового образу наведений в лекції 22. Виведена в ній інформація про групи циліндрів береться з суперблоку, зведення груп циліндрів і дескрипторів груп.

Дескриптор групи UFS1

Структура даних дескриптора групи містить інформацію про конфігурацію групи циліндрів. В кожній групі циліндрів створюється одна структура даних. Її зсув по відношенню до базової адреси задається в суперблоці, а UFS1 і UFS2 використовують різні структури. В цьому розділі ми опишемо структури даних для UFS1.

Дескриптори груп в UFS1 зберігаються з розкидом, хоча відстань від базової адреси залишається постійною. Метод обчислення базової адреси описаний в попередньому розділі. Для зберігання дескриптора зазвичай виділяється повний блок, хоча і використовується він лише частково. Багато полів не є обов'язковими і використовуються лише для підвищення ефективності виділення ресурсів.

Поля дескрипторів груп у файловій системі UFS1 перераховані в таблиці 23.5.

Таблиця 23.5 – Структура даних дескриптора групи в UFS1

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

Аби проаналізувати дескриптор першої групи в нашій системі OpenBSD UFS1, необхідно визначити його місцезнаходження. Для першої групи базовий зсув відповідає фрагменту 0. З суперблоку відомо, що дескриптор групи зміщений від бази на 24 фрагменти, тому ми переглядаємо фрагмент 24 програмою dcat:

Лістинг 23.5 – Фрагмент 24

# dcat -f openbsd openbsd.dd 24

0000000: 0000 0000 5502 0900 c99d 0f41 0000 0000....U......A....

0000016: 1000 8007 801f 0000 0200 0000 2f03 0000............/...

0000032: 7807 0000 0b00 0000 8801 0000 1001 0000 x...............

0000048: 0700 0000 0000 0000 0000 0000 0000 0000................

0000064: 0000 0000 0100 0000 0000 0000 0000 0000................

0000080: 0100 0000 a800 0000 e800 0000 0801 0000................

0000096: f801 0000 8206 0000 e405 0000 0406 0000................

0000112: f003 0000 0000 0000 0000 0000 0000 0000................

[…]

Байти 4-7 містять сигнатуру, а в байті 24 починається інформація про кількість вільних індексних вузлів і блоків, яку ми вже бачили раніше в області зведення груп циліндрів. Також тут присутня службова інформація про виділення; з байтів 40-43 видно, що останній виділений блок мав адресу 392 (0x0188), а з байтів 44-47 — що останній виділений фрагмент (неповний блок) мав адресу 272 (0x0110). Останній виділений запис індексного вузла вказаний в байтах 48-51; ми бачимо, що це був індексний вузол 7.

Зсув бітової карти індексних вузлів зберігається в байтах 92-95; ми бачимо, що бітова карта зміщена на 264 байти (0x0108) від початку групи дескрипторів. Бітова карта фрагментів (байти 96-99) видалена на 504 байти (0x01f8) від початку дескриптора групи. Бітова карта блоків (байти 108-111) зберігається із зсувом 1540 байт (0x0604) від початку дескриптора.

Дескриптор групи UFS2

Дескриптор групи UFS2 містить ту ж базову інформацію, що і його аналог з UFS1, але деякі з його полів займають більше місця. Місцезнаходження дескриптора відносно початку групи циліндрів зберігається в суперблоці, але, на відміну від дескрипторів UFS1, додатковий розкид не використовується. Поля дескрипторів груп у файловій системі UFS2 перераховані в таблиці 23.6.

Таблиця 23.6 – Структура даних дескриптора групи в UFS2

В обох версіях дескрипторів необхідна інформація обмежується зміщеннями бітових карт індексних вузлів і фрагментів. Бітові карти знаходяться після байта 168, але всередині блоку, виділеного дескриптору групи.

Познавательные статьи:



Коммуникативные барьеры и пути их преодоления

Рынок недвижимости. Сущность недвижимости

Решение задач с использованием генеалогического метода

История происхождения и развития детской игры