Центр информации по операционным системам: Контент / Статьи / Дисковая структура ReiserFS

Добро пожаловать,

Свежие материалы

Производительность программных RAID-массивов из разных дисков в Linux
bullet

Лицензия раздора
bullet

Патч Reiser4 для Linux 2.6.22
bullet

Подготовка к экзамену LPI Linux.
bullet

Архитектура файловой системы UFS2

Обсуждения

Микропроцессор "Эверест" (1)
bullet

Запрет регистрации на osrc.info (1)
bullet

Ответ Javе и Flash'у (70)
bullet

Новая программа поддержки от Microsoft (2)
bullet

Solaris будет портирован на Itanium и POWER? (3)
bullet

9 декабря вышла новая сборка Xameleon (9)
bullet

рассылка (2)
bullet

ЗРОС (3)

Новый стиль OSRC.info (2)
bullet

Обсуждение статьи "Взгляд на развитие YellowTAB" (124)

В Сети

Гостей: 4, Пользователей: 0 ...

рекорд он-лайн: 2015
(Пользователей: 1, Гостей: 2014) в 29.03.2010 00:07

Пользователей: 1007
Новичок: alicemokas

Дисковая структура ReiserFS

на Понедельник, 31 Октябрь 2005, 12:48
добавил: Пешеходов А. П. aka fresco

категория Статьи
комментарии: 0
просмотров: 5189

Bitmap-блоки

Bitmap-блоки – это простые битовые карты, где каждый бит сопоставляется с номером блока. Один такой блок может адресовать 8*blocksize блоков. Если бит установлен – блок занят, если сброшен – свободен.

File System Tree

Файловая система reiserfs предствлена в виде сбалансированноо дерева внешнего поиска (B+, или S+ дерево, как оно называется в документации на reiserfs). Дерево состоит из внутренних и листовых узлов. Каждый узел (node) – это дисковый блок. Каждому объекту (называемому item (запись)) в reiserfs (файлу, каталогу, stat-item)назначается уникальный ключ, аналогичный номеру inode в других файловых системах. Внутренние узлы, главным образом, состоят из ключей и указателей на узлы-потомки. Указателей всегда на один больше, чем ключей. Если P[i] указывает на объект, имеющий ключ меньше K[i], то P[i] – на объект с ключем >= K[i].

Заголовки блоков

Каждый дисковый блок, содержащий внутренний или листовой узел, начинается с заголовка блока.

См. include/linux/reiserfs_fs.h



struct block_head {

 __le16 blk_level; /* Уровень блока в дереве */

 __le16 blk_nr_item; /* Количество ключей/записей в блоке */

 __le16 blk_free_space; /* Свободно (в байтах) */

 __le16 blk_reserved; /* Не используется */

 struct reiserfs_key blk_right_delim_key; /* Раньше использовался для листьев,

        сохранен для совместимости */

};

Ключи

Ключи используются в reiserfs в качестве уникальных идентификаторовзаписей, а также для определения положения записей в дереве. Ключ состоит из четырех объектов: ID родительского каталога, ID объекта (object ID), смещения объекта и его типа. Примечательно, что фактически идентификатор объекта – это только одна часть ключа. Directory ID нужен, для группировки объектов, принадлежащих одному каталогу, и размещения большей их части в одном поддереве. Хранить смещение необходимо потому, что косвенная запись (см. ниже) может содержать самое большее (blocksize-48)/4 указателей на неформатированне блоки. Для размера блока в 4 kb это будет означать, что размер файла ограничен 4048 kb. Что бы обеспечить возможность обработки больших файлов, для их описания используется множество ключей. Все поля таких ключей одинаковы, за исключением offset, которое указывает на положение в файле той его части, на которую ссылается данный ключ.

В reiserfs до версии 3.5 поля type и offset были 32-хбитными величинами. Из-за этого размер файла был ограничен приблизительно четырьмя Gb (точнее 2^32 плюс данные еще одной косвенной записи плюс “хвост” (tail)). Для снятия этого ограничения в версии 3.6 поле offset было увеличено до 60 бит, а поле type – сокращено до 4 бит. Теперь теоретически доступны файлы размером до 2^60 байт, однако фактически мы можем адресовать только 2^32 блоков с максимально возможными 2^16 байт на блок – то есть не более 2^48 байт на файл. Для совместимости со старыми версиями reiserfs (и старыми ключами) был введен достаточно запутанный интерфейс – т.к. сам ключ не несет в себе номера версии. Для решения этой проблемы ранее зарезервирванны последние 16 бит заголовка записи (item header, см. ниже) теперь являются индикатором номера версии. Для ключей в листьях определить версию доволбно просто, однако если нужно получить версию ключа во внутреннем узле, то придется спуститься вниз по дереву – к соответствующему листу.

Идентификатор типа
Тип v1 v2
stat-item 0 0
прямая запись 0xfffffffe 1
косвенная запись 0xffffffff 2
директория 500 3
any 555 15

Отсюда следует, что stat-item будет всегда определяться как запсиь с KEY_FORMAY_1 – она имеет идентификатор типа = 0 в обоих версиях ключа.

См. include/linux/reiserfs_fs.h



struct in_core_key {

 __u32 k_dir_id; /* Object ID родительского каталога */

 __u32 k_objectid; /* Object ID */

 __u64 k_offset; /* Смещение (в байтах) части объекта, на которую ссылается ключ */

 __u8 k_type; /* Тип записи. */

};



struct cpu_key {

 struct in_core_key on_disk_key; /* Дисковый ключ */

 int version; /* версия */

 int key_length; /* = 3 во всех случаях, используется для direct->indirect и

        indirect->direct преобразования*/

};

Только stat-item имеет поле offset=0. Файлы (прямые и косвенные записи) и каталоги всегда начинаются со смещения 1 для того, что бы в результате сортировки они расположились в листе позади stat-записей. Для директорных записей поле offset хранит хэш имени и номер поколения крайнего левого directory header (см. ниже) записи каталога.

При сравнении ключей их поля стравниваются в таком порядке: сперва directory ID, если равны – object ID, offset, type. Код reiserfs в Linux генерирует предупреждение (warning), если дело доходит до сравнения типов, т.к. это сравнение не имеет смысла со струтурной точки зрения. Единственная ситуация, когда типы ключей должны быть протестированы – tail conversion, когда прямые записи становятся косвенными или наоборот.

Внутренние узлы

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

См. include/linux/reiser_fs.h



____________________________________________

|         |           |          |          |

| Block   | Array of  | Array of | Free     |

| header  | keys      | pointers | space    |

|_________|___________|__________|__________|

Поле blk_level заголовка блока для внутренних узлов всегда больше 1. blk_nr_item в заголовке блока означает количество ключей в блоке (а не количество ключей и указателей). Указателей всегда на 1 больше, чем ключей!

См. include/linux/reiserfs_fs.h



/* Указатель на блок-потомок */

struct disk_child {

 __le32 dc_block_number; /* Номер блока, содержащего потомка */

 __le16 dc_size; /* Использовано байт в блоке */

 __le16 dc_reserved; /* Зарезерсиврован */

};

Пусть имеем ключ n (его смещение в блоке равно 24 + n*16 байт) и всего k ключей в блоке. Тогда левый указатель, относящийся к этому ключу (и определяющий его меньшего потомка) может быть найден по смещению 24 + k*16 + n*8 байт.

индекс статьи
страница 1 : страница без заголовка
страница 2 - текущая : страница без заголовка
страница 3 : страница без заголовка
страница 4 : страница без заголовка