Бітові карти блоків і фрагментів

Стан виділення блоків і фрагментів визначається по бітових картах. Насправді інформація про кожен блок UFSзберігається в двох бітових картах: бітовій карті фрагментів і бітовій карті блоків. Врахуємо, що ці бітові карти зберігають інформацію у форматі, зворотному тому, який зазвичай використовується на практиці: їх біти встановлюються в 1 для вільних об'єктів, і скидаються в 0 для виділених об'єктів.

Почнемо з бітової карти фрагментів. Для кожної групи циліндрів ведеться бітова карта фрагментів, яка зберігається в дескрипторі групи. Зсув бітової карти в байтах задається в дескрипторі, а її розмір визначається по кількості фрагментів в групі. Аби знайти біт, що представляє конкретний фрагмент, слід визначити його адресу відносно початку групи циліндрів відніманням адреси першого фрагмента в групі. Скажімо, якщо фрагмент є 50-м в групі, його стан виділення зберігається в 50-му біті, тобто другому біті байта 6.

В розглянутій раніше файловій системі UFS1 дескриптор групи розташовувався в блоці 24, а бітова карта фрагментів зберігалася із зсувом 504 байти. Аби проглянути її вміст, слід запустити dcat з параметром 8 для перегляду всіх 8 фрагментів блоку:

# dcat -f openbsd openbsd.dd 24 | xxd

0000496: 0000 0000 0000 0000 0000 0000 0000 0000..........

0000512: 0000 0000 0000 0000 0000 0000 0000 0000..........

0000528: 0000 0000 0000 0000 0000 f0fe 0000 0000..........

0000544: 0000 0000 ffff ffff 00ff 0000 0000 0000..........

0000560: 0000 0000 0000 0000 0000 0000 0000 0000..........

0000576: 0000 0000 0000 0000 0000 0000 0000 0000..........

[...]

Байт 504 є першим байтом в бітовій карті фрагментів. Він дорівнює 0; це означає, що перші 8 фрагментів виділено. Вільні фрагменти відсутні аж до байту 538, який є байтом 34 бітових карт. Старші 4 біта цього байту рівні 1, тобто фрагменти 276-279 вільні. Дані відносяться до першої групи, тому ці номери відповідають їх фактичним адресам; інакше до них довелося б додати початкову адресу групи. Звернемо увагу: ці чотири вільні фрагменти не представляють повний блок, оскільки кожен блок складається з восьми фрагментів. В даному випадку перші 4 фрагменти блоку виділено, а останні 4 — ні.

Байти 548-551 описують серію із 32 суміжних невиділених фрагментів. Байт 548 відповідає байту 44 бітових карт, тому перший біт відноситься до фрагмента 352.

Бітова карта фрагментів малоефективна при виділенні окремих блоків або великих груп суміжних блоків, тому разом з нею існує бітова карта блоків. Вона дублює інформацію, що знаходиться в бітовій карті фрагментів, але кожен біт в ній позначає цілий блок, тому адресація блоків повинна проводитися інакше. Блоки нумеруються послідовними числами — наприклад, якщо один блок складається із 8 фрагментів, замість блоків 0, 8, 16, 24 і так далі використовуватимуться номери 0, 1, 2, 3 і так далі. Аби обчислити адресу блоку, досить розділити адресу фрагмента на кількість фрагментів в блоці. Якщо відповідний біт дорівнює 1, блок вільний для виділення.

Як було показано раніше, в системі UFS1 бітова карта блоків зберігається в дескрипторі групи із зсувом 1540:

# dcat -f openbsd openbsd.dd 24 8 | xxd

0001536: 0100 0000 0000 0000 00f0 0200 0000 0000...........

0001552: 0000 0000 0000 0000 0000 0000 c0ff ffff...........

0001568: ffff ffff ffff ffff ffff ffff ffff ffff...........

[...]

Ми бачимо, що байт 1540 рівний 0, після чого встановлені біти з'являються лише в байті 1545, в якому встановлені 4 старших біта. Цей байт є 5-м байтом бітової карти; його біти відповідають відносним блокам 40-47, а біти відносних блоків 44-47 встановлені рівними 1. Перетворивши ці адреси в адреси фрагментів, ми отримаємо фрагменти 352-383, які ми бачили в бітовій карті фрагментів як набір вільних суміжних фрагментів.

Індексні вузли UFS1

У структурах даних індексних вузлів зберігаються метадані, файли, що описують, і каталоги. І знову в UFS1 і UFS2 використовуються різні структури даних, оскільки поля UFS2 мають більший розмір. Індексні вузли діляться між групами циліндрів; кількість індексних вузлів в одній групі вказується в суперблоці. Кожна група циліндрів володіє власною таблицею індексних вузлів, її зсув також задається в суперблоці. У UFS1 величина початкового зрушення таблиці індексних вузлів змінюється залежно від групи цилінідрів (розкид), але в UFS2 індексні таблиці завжди розташовуються з однаковим зсувом відносно початку групи.

Довжина індексних вузлів UFS1 складає 128 байт, а їх поля перераховані в таблиці 23.7.

 

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

Діапазон	Опис	Необхідність
0-1	Режим файлу (тип і дозволи)	Так
2-3	Лічильник посилань	Так
4-7	Не використовується	Немає
8-15	Розмір	Так
16-19	Час звернення	Немає
20-23	Час звернення (Наносекунда)	Немає
24-27	Час модифікації	Немає
28-31	Час модифікації (Наносекунда)	Немає
32-35	Час зміни	Немає
36-39	Час зміни (Наносекунда)	Немає
40-87	12 прямих покажчиків на блоки	Так
88-91	Непрямий покажчик 1 рівня	Так
92-95	Непрямий покажчик другого рівня	Так
96-99	Непрямий покажчик третього рівня	Так
100-103	Прапори стану	Немає
104-107	Кількість блоків	Немає
108-111	Номер покоління (NFS)	Немає
112-115	Ідентифікатор користувача	Немає
116-119	Ідентифікатор групи	Немає
120-127	Не використовується	Немає

 

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

Розглянемо індексний вузол з образу UFS1. На початку розділу ми вже говорили про те, що таблиця індексних вузлів зміщена на 32 фрагменти від базової адреси групи, а оскільки йдеться про групу 0, ми знаємо, що таблиця знаходиться у фрагменті 32. Першим використовуваним індексним вузлом файлової системи є вузол 3, тому ми витягуємо його вміст за допомогою dcat і dd:

 

Лістинг 23.6 – Вмісту вузла 3

# dcat -f openbsd openbsd.dd 32 | dd bs=128 skip=3 count=l | xxd

0000000: a481 0100 0000 0000 0074 1300 0000 0000.........t......

0000016: 689d 0f41 8033 023b 7a9d 0f41 0057 a616 h..A.3.;zt.A.W..

0000032: 7a9d 0f41 0057 a616 2001 0000 2801 0000 Z..A.W.....(...

0000048: 3001 0000 3801 0000 4001 0000 4801 0000 0...8...@...H...

0000064: 5001 0000 5801 0000 9001 0000 9801 0000 P...X...........

0000080: a00l 0000 a801 0000 8001 0000 0000 0000................

0000096: 0000 0000 0000 0000 d009 0000 5ade 19aс............Z...

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

 

Перші 4 байти визначають режим. Біти 12-15 містять значення 8 — це ознака звичайного файлу. Розмір (байти 8-15) складає 1274880 байт (0x00137400). А-час задається в байтах 16-19. Після перетворення в звичайний формат ми отримуємо 14:12:56, 3 серпня 2008 р. по UTC.

Адреса першого блоку в байтах 40-43 рівний 288 (0x0120). Другий блок володіє адресою 296 (0x0128). Ці блоки є суміжними, оскільки у файловій системі один блок складається з 8 фрагментів. У байтах 88-91 міститься непрямий покажчик на блок, що містить покажчики на блоки; у нашому прикладі це блок 384.

Програма istat виводить для цього файлу наступний результат:

 

Лістинг 23.7 – Результат виводу istat

# istat -f openbsd -z UTC openbsd.dd 3

і node: 3

Allocated Group: 0

uid / gid: 0 / 0

mode: -rw-r--r—

size: 1274880

num of links: 1

 

Inode Times:

Accessed: Tue Aug 3 14:12:56 2008

File Modified: Tue Aug 3 14:13:14 2008

Inode Modified: Tue Aug 3 14:13:14 2008

 

Direct Blocks:

288 289 290 291 292 293 294 295

296 297 298 299 300 301 301 303

304 305 306 307 308 309 310 311

[...]

1568 1569 1570 1571 1572 1573 1574 1575

1576 1577 1578 1579 1580

Indirect Blocks:

384 385 386 387 388 389 390 391

У вихідних даних istat перераховуються всі виділені фрагменти; в останньому рядку вказано всього п'ять фрагментів.

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

# dcat -f openbsd openbsd.dd 24 8 | xxd

[...]

0000256: 3f00 3f00 3f00 3f00 ff00 0000 0000 0000?.?.?.?.........

0000272: 0000 0000 0000 0000 0000 0000 0000 0000................

[...]

Байт 264 рівний 0xff; це означає, що індексні вузли 0-7 виділені (вміст вузла 3 було проаналізовано раніше). Індексні вузли 8 і далі в цій групі циліндрів вільні.

Індексні вузли UFS2

Індексні вузли UFS2 на 128 байт більше своїх аналогів в UFS1, а багато 32-розрядних полів в них замінено 64-розрядними. Вони також зберігаються в таблиці індексних вузлів, зсув яких задається в суперблоці, але, на відміну від UFS1, зсув таблиці залишається постійним. Поля індексних вузлів UFS2 перераховані в таблиці 23.8.

 

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

 

Діапазон	Опис	Необхідність
0-1	Режим файлу (тип і дозволи)	Так
2-3	Лічильник посилань	Так
4-7	Ідентифікатор користувача	Немає
8-11	Ідентифікатор групи	Немає
12-15	Розмір блоку індексних вузлів	Немає
16-23	Розмір	Так
24-31	Кількість утримуваних байт	Немає
32-39	Час звернення	Немає
40-47	Час модифікації	Немає
48-55	Час зміни	Немає
56-63	Час створення	Немає
64-67	Час модифікації (Наносекунда)	Немає
68-71	Час звернення (Наносекунда)	Немає
72-75	Час зміни (Наносекунда)	Немає
76-79	Час створення (Наносекунда)	Немає
80-83	Номер покоління (NFS)	Немає
84-87	Прапори ядра	Немає
88-91	Прапори стану	Немає
92-95	Розмір розширених атрибутів	Немає
96-111	2 прямих покажчика на блоки розширених атрибутів	Немає
112-207	12 прямих покажчиків на блоки	Так
208-215	Непрямий покажчик першого рівня	Так
216-223	Непрямий покажчик другого рівня	Так
224-231	Непрямий покажчик третього рівня	Так
232-255	Не використовується	Немає

 

Найпомітніша відмінність між версіями UFS1 і UFS2 полягає в тому, що покажчики на блоки і тимчасові штампи стали 64-розрядними. Адреси в блоках непрямої адресації також займають 64 біта.

При аналізі образу UFS2 було показано, що таблиця індексних вузлів починається у фрагменті 56. Вміст індексного вузла 5 виглядає так, як показано нижче:

 

Лістинг 23.8 – Вміст індексного вузла 5

# dcat -f freebsd freebsd.dd 56 8 | dd bs=256 skip=5 count=l | xxd

0000000: a481 0100 0000 0000 0000 0000 0000 0000...............

0000016: 0000 2000 0000 0000 2010 0000 0000 0000.............

0000032: b5b3 0f41 0000 0000 b6b3 0f41 0000 0000...A......A....

0000048: b6b3 0f41 0000 0000 b5b3 0f41 0000 0000...А......А....

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

0000080: 11fe 8458 0000 0000 0000 0000 0000 0000...X...........

0000096: 0000 0000 0000 0000 0000 0000 0000 0000...............

0000112: е800 0000 0000 0000 f000 0000 0000 0000...............

0000128: f800 0000 0000 0000 0001 0000 0000 0000...............

0000144: 0801 0000 0000 0000 1001 0000 0000 0000...............

0000160: 1801 0000 0000 0000 2001 0000 0000 0000..............

0000176: 5801 0000 0000 0000 6001 0000 0000 0000 X.......’......

0000192: 6801 0000 0000 0000 7001 0000 0000 0000 h.......p......

0000208: 4801 0000 0000 0000 7001 0000 0000 0000 H..............

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

0000240: 0000 0000 0000 0000 0000 0000 0000 0000...............

 

В байтах 0-1 відображується режим; значення 8 є ознакою звичайного файлу. Байти 16-23 показують, що розмір файлу дорівнює 2097152 байтам (0x00200000). У байтах 32-39 зберігається 8-байтовий А-час, який після перетворення приймає вигляд 15:48:05, 3 серпня 2008 р. по UTC.

Байти 112-119 містять перший прямий покажчик на блок файлу. У даному прикладі це блок 232 (0хе8). Другий покажчик посилається на блок 240 (0xf0); в тестовому образі розмір блоку дорівнює 8 фрагментам. Байти 208-215 містять перший непрямий покажчик 328 (0x0148).

Виведення istat для цього індексного вузла виглядає так, як представлено на лістингу 23.9:

 

Лістинг 23.9 – Вивід istat

# istat -f freebsd -z UTC freebsd.dd 5

і node: 5

Allocated

Group: 0

uid / gid: 0 / 0

mode: -rw-r--r--

size: 2097152

num of links: 1

 

Inode Times:

Accessed: Tue Aug 3 15:48:05 2008

File Modified: Tue Aug 3 15:48:06 2008

Inode Modified: Tue Aug 3 15:48:06 2008

 

Direct Blocks:

232 233 234 235 236 237 238 239

240 241 242 243 244 245 246 247

[...]

1296 1297 1298 1299 1300 1301 1302 1303

Indirect Blocks:

328 329 330 331 332 333 334 335

Розширені атрибути UFS2

Файли і каталоги UFS2 також можуть володіти розширеними атрибутами — парами «ім'я-значення», заданим користувачем або системою. Розширені атрибути зберігаються в звичайних блоках даних, адреси яких задаються в індексному вузлі. Кожен блок містить список структур даних змінної довжини, поля яких перераховані в таблиці 23.9.

 

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

 

Діапазон	Опис	Необхідність
0-3	Довжина запису	Так
4-4	Простір імен (див. таблиці. 2.10)	Немає
5-5	Доповнення вмісту	Так
6-6	Довжина імені	Так
7-(7+довжина імені)	Ім'я	Так
(Після імені, з вирівнюванням по кордону 8 байт)	Значення	Так

 

Ім'я доповнюється так, щоб значення починалося з кордону 8 байт. Значення також доповнюється, аби наступний запис був вирівняний по 8-байтовому кордону. Величина вирівнювання імені обчислюється по довжині імені, а величина вирівнювання значення задається в байті 5. Поле простору імен містить одне із значень, представлених в таблиці 23.10.

 

Таблиця 23.10 – Значення поля простору імен в розширених атрибутах

 

Значення	Опис
	Призначений для користувача простір імен
	Системний простір імен

 

Вміст блоку розширених атрибутів з двома атрибутами виглядає згідно лістингу 23.10:

 

Лістинг 23.10 – Вміст блоку розширених атрибутів з двома атрибутами

0000000: 3000 0000 0107 0673 6f75 7263 6500 0000 0.......source...

0000016: 7777 7777 2е64 6967 6974 616с 2d65 7669 www.digital-evi.

0000032: 6465 6e63 652e 6f72 6700 0000 0000 0000 dence.org.......

0000048: 2000 0000 0104 0464 6174 6500 0000 0000.....date......

0000064: 4175 6720 3132 2c20 3230 3034 0000 0000 Aug 12. 2008....

0000080: 0000 0000 0000 0000 0000 0000 0000 0000................

 

Байти 0-3 показують, що довжина запису дорівнює 48 байтам (0x30). Простір імен в байті 4 рівний 1; отже, атрибут є призначеним для користувача. У вмісті присутні 7 байт доповнення, довжина імені рівна б байтам, а ім'я атрибуту є рядком «source». Ім'я закінчується в байті 12, а найближчий 8-байтовий кордон знаходиться в байті 16. Аби визначити завершаючу адресу значення, слід відняти з довжини запису початковий байт і довжину доповнення (48-16-7=25). Значенням атрибуту є рядок «www.digital-evidence.org».

Записи каталогів

Структури даних записів каталогів призначені для зберігання імен файлів і каталогів. Вони зберігаються в блоках, виділених каталогам. Кожна структура даних містить ім'я файлу і адресу індексного вузла з метаданими. Поля записів каталогів в UFS1 і UFS2 представлені в таблиці 23.11.

 

Таблиця 23.11 – Структура даних записів каталогів UFS1 і UFS2

 

Діапазон	Опис	Необхідність
0-3	Індексний вузол	Так
4-5	Довжина запису каталога	Так
6-6	Довжина імені	Так
7-7	Тип файлу (див. таблицю 2.12)	Немає
8+	Ім'я в кодуванні ASCII	Так

 

Допустимі значення поля типу файлу перераховані в таблиці 23.12.

 

Таблиця 23.12. Значення поля типу в записі каталогу

 

Значення	Опис
	Невідомий тип
	FIFO
	Символьний пристрій
	Каталог
	Блоковий пристрій
	Звичайний файл
	Символічне заслання
	Сокет
	Дублікат

 

Для одного з файлів встановлюється прапор дубліката, і ОС не відображує його по запиту користувача.

Поле довжини запису каталога використовується для пошуку наступного виділеного запису, а поле довжини імені — для визначення кінця імені і фактичної довжини запису.

Вміст каталога UFS1 в тестовій файловій системі виглядає так:

 

Лістинг 23.11 – Вміст каталога UFS1

# icat -f openbsd openbsd.dd 1921 | xxd

0000000: 8107 0000 OCOO 0102 2e00 0000 0200 0000................

0000016: 0c00 0402 2e2e 0000 8c07 0000 1400 0809................

0000032: 6669 6c65 312e 7478 7400 93e7 8d07 0000 file1.txt.......

0000048: 1400 0809 6669 6c65 382e 7478 7400 93e7....file8.txt...

0000064: 8e07 0000 2800 0809 6669 6c65 372e 7478....(...file7.tx

0000080: 7400 93e7 8f07 0000 1400 0809 6669 6c65 t...........file

0000096: 362e 7478 7400 93e7 9007 0000 1400 0809 6.txt...........

0000112: 6669 6c65 352e 7478 7400 93e7 9107 0000 file5.txt.......

0000128: 2800 0809 6669 6c65 342e 7478 7400 93e7 (...file4.txt...

0000144: 9207 0000 1400 0809 6669 6c65 372e 7478........file7.tx

[...]

Перші чотири байти описують індексний вузол запису «.»; як видно з лістингу 23.11, це індексний вузол 1921 (0x0781). Байти 24-27 містять номер індексного вузла для першого запису файлу filel.txt; це індексний вузол 1932 (0x078с). Байти 68-69 містять поле довжини для файлу file7.txt. Його довжина складає 40 байт (0x28), хоча ім'я займає всього 9 байт.Наступний запис (для файлу file6.txt) був видалений, а поле довжини файлу file7.txt посилається на запис після file6.txt.