Архитектура файловой системы ext2::Журнал СА 11.2003
www.samag.ru
Льготная подписка для студентов      
Поиск   
              
 www.samag.ru    Web  0 товаров , сумма 0 руб.
E-mail
Пароль  
 Запомнить меня
Регистрация | Забыли пароль?
О журнале
Журнал «БИТ»
Подписка
Где купить
Авторам
Рекламодателям
Магазин
Архив номеров
Вакансии
Контакты
   

Jobsora


  Опросы

Какие курсы вы бы выбрали для себя?  

Очные
Онлайновые
Платные
Бесплатные
Я и так все знаю

 Читать далее...

1001 и 1 книга  
28.05.2019г.
Просмотров: 2271
Комментарии: 2
Анализ вредоносных программ

 Читать далее...

28.05.2019г.
Просмотров: 2257
Комментарии: 1
Микросервисы и контейнеры Docker

 Читать далее...

28.05.2019г.
Просмотров: 1805
Комментарии: 0
Django 2 в примерах

 Читать далее...

28.05.2019г.
Просмотров: 1328
Комментарии: 0
Введение в анализ алгоритмов

 Читать далее...

27.03.2019г.
Просмотров: 1853
Комментарии: 1
Arduino Uno и Raspberry Pi 3: от схемотехники к интернету вещей

 Читать далее...

Друзья сайта  

Форум системных администраторов  

sysadmins.ru

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

Архив номеров / 2003 / Выпуск №11 (12) / Архитектура файловой системы ext2

Рубрика: Администрирование /  Архитектура

ВЛАДИМИР МЕШКОВ

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

В статье рассматривается логическая структура ext2 – файловой системы операционной системы Linux.

Основные компоненты файловой системы ext2

Как и в любой файловой системе UNIX, в составе файловой системы ext2 можно выделить следующие составляющие:

  • блоки и группы блоков;
  • информационный узел (information node);
  • суперблок (superblock).

Блоки и группы блоков

Все пространство раздела диска разбивается на блоки фиксированного размера, кратные размеру сектора – 1024, 2048 и 4096 байт. Размер блока указывается при создании файловой системы на разделе жесткого диска. Меньший размер блока позволяет экономить место на жестком диске, но также ограничивает максимальный размер файловой системы. Все блоки имеют порядковые номера. С целью уменьшения фрагментации и количества перемещений головок жесткого диска при чтении больших массивов данных блоки объединяются в группы.

Информационный узел

Базовым понятием файловой системы является информационный узел, information node, или inode. Это специальная структура, которая содержит информацию об атрибутах и физическом расположении файла. Атрибутами файла являются его тип (обычный файл, каталог и т. д.), права доступа к нему, идентификатор владельца, размер, время создания. Информация о физическом расположении представляет собой последовательность абсолютных номеров блоков, содержащих данные файла.

Суперблок

Суперблок – основной элемент файловой системы ext2. Он содержит следующую информацию о файловой системе (список неполный):

  • общее число блоков и inode в файловой системе;
  • число свободных блоков и inode в файловой системе;
  • размер блока файловой системы;
  • количество блоков и inode в группе;
  • размер inode;
  • идентификатор файловой системы;
  • номер первого блока данных.

Другими словами, это номер блока, содержащего суперблок. Этот номер всегда равен 0, если размер блока файловой системы больше 1024 байт, и 1, если размер блока равен 1024 байт.

От целостности суперблока напрямую зависит работоспособность файловой системы. Операционная система создает несколько резервных копий суперблока для возможности его восстановления в случае повреждения. Главная копия находится по смещению 1024 байт от начала раздела, на котором создана файловая система (первые 1024 байта зарезервированы для загрузчика операционной системы).

Ранние версии файловой системы ext2 создавали копии суперблока в начале каждой группы блоков. Это приводило к большим потерям дискового пространства, поэтому позже количество резервных копий суперблока было уменьшено, и для их размещения были выделены группы блоков 0, 1, 3, 5 и 7.

Формат группы блоков

Обобщенная структурная схема файловой системы ext2 представлена на рис. 1.

Рисунок 1. Обобщенная структурная схема файловой системы ext2

 

Рисунок 1. Обобщенная структурная схема файловой системы ext2

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

Битовая карта занятости блоков обычно расположена в первом блоке группы. Если в группе присутствует резервная копия суперблока, битовая карта располагается во втором блоке группы. Размер битовой карты – один блок. Каждый бит этой карты обозначает состояние блока. Если бит установлен (1), то блок занят, если сброшен (0) – блок свободен. Первому блоку группы соответствует нулевой бит карты, второму блоку – первый бит и т. д.

Inode, находящиеся в пределах одной группы, собраны в таблицу. В битовой карте занятости inode группы каждый бит характеризует состояние элемента в таблице inode группы.

Каждая группа блоков описывается при помощи дескриптора группы блоков. Дескриптор группы – это структура, которая содержит информацию об адресах битовой карты занятости блоков, битовой карты занятости inode и таблицы inode соответствующей группы. Все дескрипторы групп собраны в таблицу дескрипторов групп, которая хранится в группе блоков 0. Так же, как и для суперблока, операционная система создает резервные копии таблицы дескрипторов групп.

Алгоритм чтения файла

Каждый inode, как и блок, имеет порядковый номер, уникальный в пределах файловой системы, и содержит информацию только об одном файле. Таким образом, для получения доступа к содержимому файла необходимо знать порядковый номер соответствующего ему inode.

Как было сказано выше, информация о физическом расположении файла содержится в inode. Эта информация представляет собой последовательность 32-битных номеров блоков, содержащих данные файла (рис. 1). Первые 12 номеров – это прямые ссылки на информационные блоки (direct blocks number). 13-й номер является косвенной ссылкой (indirect blocks number). В нем находится адрес блока, в котором хранятся адреса информационных блоков. 14-й номер – двойная косвенная ссылка (double blocks number), 15-й номер – тройная косвенная ссылка (triple blocks number).

Имя файла в состав inode не входит, установление соответствия между именами файлов и порядковыми номерами inode выполняется через каталоги.

Каталоги

Файлы в UNIX- и POSIX-системах хранятся в древовидной иерархической файловой системе. Корень файловой системы – это корневой каталог, обозначенный символом «/». Каждый промежуточный узел в дереве файловой системы – это каталог. Конечные вершины дерева файловой системы являются либо пустыми каталогами, либо файлами. Абсолютное путевое имя файла состоит из имен всех каталогов, ведущих к указанному файлу, начиная с корневого каталога. Так, путевое имя /home/test.file означает, что файл test.file расположен в каталоге home, который, в свою очередь, находится в корневом каталоге «/».

Каталог, так же как и файл, описывается при помощи inode. Содержимое каталога представляет собой массив записей, каждая из которых содержит информацию о файле, который находится «внутри» текущего каталога.

Запись каталога имеет следующий формат:

  • порядковый номер inode файла;
  • длина записи в байтах;
  • имя файла;
  • длина имени файла.

Поиск номера inode файла всегда начинается с корневого каталога. Например, чтобы получить порядковый номер inode файла, находящегося в корневом каталоге, операционная система должна получить содержимое корневого каталога, найти в нем запись с именем этого файла и извлечь из этой записи порядковый номер inode файла.

Несколько первых номеров inode зарезервированы файловой системой, их перечень содержится в заголовочном файле :

/*

 * Special inode numbers

 */

#define EXT2_BAD_INO 1 /* Bad blocks inode */

#define EXT2_ROOT_IN 2 /* Root inode */

#define EXT2_ACL_IDX_IN 3 /* ACL inode */

#define EXT2_ACL_DATA_INO 4 /* ACL inode */

#define EXT2_BOOT_LOADER_INO 5 /* Boot loader inode */

#define EXT2_UNDEL_DIR_INO 6 /* Undelete directory inode */

Для записи корневого каталога зарезервирован inode под номером 2 (root inode). Этот inode находится в группе блоков 0 и занимает вторую позицию в таблице inode этой группы. Номер первого незарезервированного inode хранится в суперблоке.

Определив порядковый номер inode файла, ядро вычисляет номер группы, в которой этот inode расположен, и его позицию в таблице inode группы. Считав из этой позиции inode, операционная система получает полную информацию о файле, включая адреса блоков, в которых хранится содержимое файла.

Номер группы блоков, в которой расположен inode, вычисляется по формуле:

group = (inode_num - 1) / inodes_per_group

где:

  • group – искомый номер группы блоков;
  • inode_num – порядковый номер inode, определяющего файл;
  • inodes_per_group – число inode в группе (эта информация находится в суперблоке).

Позиция inode в таблице inode группы определяется по формуле:

index = (inode_num - 1) % inodes_per_groupe

где index – позиция inode в таблице.

Рассмотрим пример получения содержимого файла test.file, находящегося в корневом каталоге. Для чтения файла /test.file необходимо:

  • в массиве записей корневого каталога найти запись об этом файле;
  • извлечь порядковый номер inode файла, вычислить номер группы, в которой этот inode расположен;
  • из дескриптора данной группы извлечь адрес таблицы inode группы;
  • вычислить позицию inode в этой таблице;
  • считать inode файла;
  • из inode извлечь адреса информационных блоков и осуществить чтение информации, находящейся в этих блоках.

На рис. 2 подробно показаны этапы чтения файла /test.file.

Рисунок 2. Порядок выполнения процедуры чтения файла в файловой системе ext2 (на примере файла /test.file)

Рисунок 2. Порядок выполнения процедуры чтения файла в файловой системе ext2 (на примере файла /test.file)

    Этапы 1-6 – чтение корневого каталога:

  1. Из группы блоков 0 считывается таблица дескрипторов групп.
  2. Из таблицы дескрипторов групп извлекается дескриптор группы блоков 0 и из него считывается адрес таблицы inode группы 0.
  3. Из группы блоков 0 считывается таблица inode.
  4. Порядковый номер inode корневого каталога фиксирован и равен 2, поэтому из таблицы inode группы 0 считывается второй элемент, который содержит адрес блока с содержимым корневого каталога. Предположим, что этот блок расположен в группе блоков A.
  5. Из группы блоков A считывается блок, содержащий записи корневого каталога.
  6. Выполняется поиск записи с именем «test.file». Если такая запись найдена, из нее извлекается порядковый номер inode файла «test.file».
  7. Определив номер inode, можно получить доступ к информационным блокам файла (этапы 7-11):

  8. Вычисляется номер группы, в которой находится данный inode, и его позицию в таблице inode группы (предположим, что номер группы равен B, а позиция в таблице – X).
  9. Из таблицы дескрипторов групп извлекаем дескриптор группы блоков B, и из него считывается адрес таблицы inode этой группы блоков.
  10. Из группы блоков B считывается таблица inode.
  11. Из таблицы inode группы блоков B считывается inode, находящийся в позиции X.
  12. Из считанного inode извлекаются адреса блока с содержимым файла /test.file и выполняется чтение информации из блока с указанным адресом.

Программная реализация алгоритма чтения файла

Исходные данные: имеется раздел жесткого диска, на котором создана файловая система ext2. Этому разделу соответствует файл устройства /dev/hda3. В корневом каталоге раздела создан подкаталог home, а в нем находится файл test.file следующего содержания:

В чащах юга жил бы цитрус?

Да, но фальшивый экземпляр!

1234567890-=

Не подумайте плохого, это не бред, а тестовое упражнение из курса подготовки телеграфистов в войсках связи бывшего СССР!

Внимание! Следует учесть один важный момент. Созданный файл не будет сразу записан на диск, а сначала попадет в дисковый буфер. Попытка сразу же получить содержимое файла по вышеприведенному алгоритму ни к чему не приведет, так как информация об этом файле физически на диске отсутствует. Необходимо «заставить» систему записать дисковый буфер на диск. Самый простой способ сделать это – выполнить операцию перезагрузки. Поэтому после того, как файл создан, перезагрузите систему.

Наша задача – используя файл устройства /dev/hda3, осуществить чтение файла /home/test.file методом прямого доступа к его информационным блокам.

Рассмотрим программную реализацию модуля, выполняющего эту операцию.

Заголовочные файлы:

#include <stdio.h>

#include <sys/types.h>

#include <fcntl.h>

#include <unistd.h>

#include <errno.h>

#include <linux/ext2_fs.h>

В заголовочном файле определены структурные типы, описывающие основные компоненты файловой системы ext2 – суперблок, дескриптор группы блоков, информационный узел, запись каталога.

Рассмотрим кратко поля, которые входят в каждую из этих структур:

  1. Структура суперблока struct ext2_super_block:
    • __u32 s_inodes_count – общее число inode в файловой системе;
    • __u32 s_blocks_count – общее число блоков в файловой системе;
    • __u32 s_free_blocks_count – количество свободных блоков;
    • __u32 s_free_inodes_count – количество свободных inode;
    • __u32 s_first_data_block – номер первого блока данных (номер блока, в котором находится суперблок);
    • __u32 s_log_block_size – это значение используется для вычисления размера блока. Размер блока определяется по формуле: block size = 1024 << s_log_block_size;
    • __u32 s_blocks_per_group – количество блоков в группе;
    • __u32 s_inodes_per_group – количество inode в группе;
    • __u16 s_magic – идентификатор файловой системы ext2 (сигнатура 0xEF53);
    • __u16 s_inode_size – размер информационного узла (inode);
    • __u32 s_first_ino – номер первого незарезервированного inode.
  2. Структура дескриптора группы блоков struct ext2_group_desc:
    • __u32 bg_block_bitmap – битовая карта занятости блоков группы;
    • __u32 bg_inode_bitmap – битовая карта занятости inode группы;
    • __u32 bg_inode_table – адрес таблицы inode группы.
  3. Структура информационного узла struct ext2_inode:
    • __u16 i_mode – тип файла и права доступа к нему. Тип файла определяют биты 12-15 этого поля:
      • 0xA000 – символическая ссылка;
      • 0x8000 – обычный файл;
      • 0x6000 – файл блочного устройства;
      • 0x4000 – каталог;
      • 0x2000 – файл символьного устройства;
      • 0x1000 – канал FIFO.
    • __u32 i_size – размер в байтах;
    • __u32 i_atime – время последнего доступа к файлу;
    • __u32 i_ctime – время создания файла;
    • __u32 i_mtime – время последней модификации;
    • __u32 i_blocks – количество блоков, занимаемых файлом;
    • __u32 i_block[EXT2_N_BLOCKS] – адреса информационных блоков (включая все косвенные ссылки).
  4. Значение EXT2_N_BLOCKS определено в файле :

    /*

     * Constants relative to the data blocks

     */

    #define EXT2_NDIR_BLOCKS 12

    #define EXT2_IND_BLOCK     EXT2_NDIR_BLOCKS

    #define EXT2_DIND_BLOCK (EXT2_IND_BLOCK + 1)

    #define EXT2_TIND_BLOCK (EXT2_DIND_BLOCK + 1)

    #define EXT2_N_BLOCKS   (EXT2_TIND_BLOCK + 1)

  5. Структура записи каталога struct ext2_dir_entry_2:
  6. #define EXT2_NAME_LEN 255

  • __u32 inode – номер inode файла;
  • __u16 rec_len – длина записи каталога;
  • __u8 name_len – длина имени файла;
  • char name[EXT2_NAME_LEN]имя файла.

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

#define PART_NAME "/dev/hda3" 

struct ext2_super_block sb;

/* буфер для хранения таблицы дескрипторов групп */

unsigned char buff_grp[4096];

unsigned char buff[4096]; /* информационный буфер */

int indev; /* дескриптор файла устройства */

int BLKSIZE; /* размер блока файловой системы */

Определим несколько функций, которые нам понадобятся для работы:

Функция чтения суперблока:

void read_sb()

{

   memset(&sb,0,1024);

Смещаемся на 1024 байта от начала раздела и считываем суперблок в структуру struct ext2_super_block sb:

   if(lseek(indev,1024,0) < 0) {

     perror("lseek");

     exit(-1);

   }

   if(read(indev,(char *)&sb,sizeof(sb)) < 0) {

     perror("read");

     exit(-1);

   }

Проверяем идентификатор файловой системы:

   if(sb.s_magic != EXT2_SUPER_MAGIC) {

     printf("Неизвестный тип файловой системы! ");

     exit(-1);

   }

Значение EXT2_SUPER_MAGIC определено в заголовочном файле .

Отображаем информацию о файловой системе, которая находится в суперблоке:

   printf(" Superblock info ----------- ");

   printf("Inodes count - %u ",sb.s_inodes_count);

   printf("Blocks count - %u ",sb.s_blocks_count);

   printf("Block size - %u ",1024 << sb.s_log_block_size);

   printf("First inode - %d ",sb.s_first_ino);

   printf("Magic - 0x%X ",sb.s_magic);

   printf("Inode size - %d ",sb.s_inode_size);

   printf("Inodes per group - %u ",sb.s_inodes_per_group);

   printf("Blosks per group - %u ",sb.s_blocks_per_group);

   printf("First data block - %u ",sb.s_first_data_block);

    return;

}

Функция чтения таблицы дескрипторов групп:

void read_gdt()

{

Вычисляем размер блока файловой системы:

   BLKSIZE = 1024 << sb.s_log_block_size

Таблица дескрипторов групп находится в блоке, который расположен сразу же за первым блоком данных (за суперблоком).

Считываем таблицу:

   if(lseek(indev, (sb.s_first_data_block + 1) * BLKSIZE, 0) < 0) {

     perror("lseek");

     exit(-1);

   }

   if(read(indev,buff_grp,BLKSIZE) < 0) {

     perror("read");

     exit(-1);

   }

   return;

}

Функция получения содержимого inode по его номеру:

void get_inode(int inode_num, struct ext2_inode *in)

{

Входные параметры функции – порядковый номер inode и структура struct ext2_inode.

   struct ext2_group_desc gd;

   __u64 group, index, pos;

Вычисляем номер группы блоков, в которой находится inode с порядковым номером inode_num:

   group = (inode_num - 1) / sb.s_inodes_per_group;

Из таблицы дескрипторов групп извлекаем дескриптор группы group и копируем его в структуру struct ext2_group_desc gd:

   memset((void *)&gd, 0, sizeof(gd));

   memcpy((void *)&gd, buff_grp + (group * (sizeof(gd))), sizeof(gd));

Вычисляем позицию inode c порядковым номером inode_num в таблице inode группы group и считываем этот inode в структуру struct ext2_inode:

   index = (inode_num - 1) % sb.s_inodes_per_group;

   pos = ((__u64)gd.bg_inode_table) * BLKSIZE + (index * sb.s_inode_size);

   pread64(indev, in, sb.s_inode_size, pos);

   return;

}

Функция чтения блока данных:

void read_iblock(struct ext2_inode *in, int blk_num)

{

   __u64 pos;

Входные параметры функции – структура inode и номер блока (имеется в виду номер из последовательности адресных блоков, расположенных в inode).

Вычисляем смещение к информационному блоку на разделе и считываем этот блок в глобальный буфер buff:

   pos = ((__u64)in->i_block[blk_num]) * BLKSIZE;

   pread64(indev, buff, BLKSIZE, pos);

   return;

}

Функция получения содержимого корневого каталога:

void get_root_dentry()

{

   struct ext2_inode in;

Порядковый номер inode корневого каталога известен, поэтому получаем содержимое inode корневого каталога и считываем в буфер buff его содержимое:

   get_inode(EXT2_ROOT_INO, &in);

   read_iblock(&in, 0);

В буфере buff будет находиться содержимое корневого каталога.

   return;

}

Функция получения номера inode по имени файла:

int get_i_num(char *name)

{

Входные параметры функции – имя файла. Возвращаемое значение – порядковый номер inode файла.

   int i = 0, rec_len = 0;

   struct ext2_dir_entry_2 dent;

В буфере buff находится массив записей каталога. Для определения порядкового номера inode файла необходимо найти в этом массиве запись с именем этого файла:

   for(; i < 700; i++) {

   memcpy((void *)&dent, (buff + rec_len), sizeof(dent));

   if(!memcmp(dent.name, name, dent.name_len)) break;

   rec_len += dent.rec_len;

   }

   return dent.inode;

}

А теперь распишем главную функцию:

int main()

{

Переменные и структуры:

   struct ext2_inode in;

   // абсолютное путевое имя файла

   unsigned char *full_path = "/home/test.file";

   unsigned char buff1[EXT2_NAME_LEN];

   static int i = 1;

   int n, i_num, outf, type;

Первым символом в абсолютном путевом имени файла должен быть прямой слэш (/). Проверяем это:

   if(full_path[0] != "/") {

   perror("slash");

   exit(-1);

   }

Открываем файл устройства, считываем суперблок и таблицу дескрипторов групп:

   indev = open(PART_NAME,O_RDONLY);

   if(indev < 0) {

     perror("open");

     exit(-1);

   }

   read_sb();

   read_gdt();

Получаем содержимое корневого каталога:

   get_root_dentry();

Сейчас в буфере buff находятся все записи корневого каталога (если хотите, можете сохранить их в отдельном файле). Теперь, имея записи корневого каталога, мы можем добраться до содержимого файла test.file, используя вышеприведенный алгоритм чтения файла. С этой целью организуем цикл. В теле цикла проведем разбор абсолютного путевого имени файла, выделяя его элементы – подкаталоги (он у нас один, home) и имя искомого файла (test.file). Для каждого элемента определим порядковый номер inode, считаем этот inode и затем получим содержимое нулевого блока (из последовательности адресных блоков, находящихся в inode):

while(1) {

   memset(buff1,0,sizeof(buff1));

   for(n = 0 ; n < EXT2_NAME_LEN; n++, i++) {

     buff1[n] = full_path[i];

     if((buff1[n] == "/") || (buff1[n] == "?")) {

        i++;

        break;

   }

}

buff1[n] = "?";

Для каждого элемента абсолютного путевого имени файла определяем порядковый номер inode, считываем этот inode в память и затем получаем содержимое нулевого блока:

   i_num = get_i_num(buff1);

   get_inode(i_num, &in);

   read_iblock(&in, 0);

Отобразим информацию о файле (имя, порядковый номер inode, размер файла и его тип):

   printf("Inode number - %u ", i_num);

   printf("File name - %s ", buff1);

   printf("File size - %u ",in.i_size);

Тип файла определяют старшие четыре бита поля i_mode структуры struct ext2_inode:

   type = ((in.i_mode & 0xF000) >> 12);

   printf("Type - %d ",type);

   switch(type) {

       case(0x04) :

     printf("(каталог) ");

     break;

       case(0x08) :

     printf("(обычный файл) ");

     break;

       case(0x06) :

     printf("(файл блочного устройства) ");

     break;

       case(0x02) :

     printf("(файл символьного устройства) ");

     break;

       default:

     printf("(unknown type) ");

     break;

   }

Проверяем тип файла. Если это обычный файл – прерываем цикл:

   if(type & 0x08) {

В буфере buff будет находиться информация, считанная из информационных блоков файла /home/test.file. Запишем эту информацию в файл:

     outf = open("out",O_CREAT|O_RDWR,0600);

     write(outf, buff, sizeof(buff));

     close(outf);

     break;

   }

}

Выходим:

    close(indev);

    return 0;

}

На этом рассмотрение логической структуры файловой системы ext2 завершим.

Ссылки:

  1. http://www.nongnu.org/ext2-doc
  2. http://e2fsprogs.sourceforge.net/ext2intro.html

Комментарии
 
  04.05.2014 - 12:49 |  clank

Очень интересная статья -- спасибо!
Все четко, подробно, лаконично и понятно написано, как теория, так и практика.

Добавить комментарий

Комментарии могут оставлять только зарегистрированные пользователи

               Copyright © Системный администратор

Яндекс.Метрика
Tel.: (499) 277-12-41
Fax: (499) 277-12-45
E-mail: sa@samag.ru