В статье рассматривается процедура чтения файла c раздела жесткого диска с файловой системой ext2. С этой целью разработаем программный модуль, эмулирующий работу драйвера жесткого диска и драйвера файловой системы ext2 (далее модуль). Доступ к жесткому диску выполняется через пространство портов ввода-вывода ATA-контроллера (порядок доступа к диску через порты рассмотрен в [1]).
ЧАСТЬ 1
1. Структурная схема и алгоритм функционирования модуля
По сути, модуль является приложением пользователя, функционирующим под управлением операционной системы Linux. Структурная схема модуля показана на рис. 1.
В состав модуля входят следующие структурные элементы:
- эмулятор драйвера блочного устройства (жесткого диска) (далее драйвер жесткого диска);
- эмулятор драйвера файловой системы ext2 (далее драйвер файловой системы);
- подсистема ввода/вывода (I/O);
- таблица блочных устройств (ТБУ).
Адресное пространство процесса условно разделено на адресное пространство ядра и адресное пространство пользователя.
В UNIX-системах доступ к устройству на уровне пользователя выполняется через файл устройства, атрибутами которого являются старший и младший номера устройства. Старший номер указывает, к какому классу (типу) относится устройство, младший номер используется для непосредственной адресации устройства определенного типа. В нашем примере мы будем следовать этой традиции. Все АТА-устройства (жесткие диски с интерфейсом АТА) имеют единый старший номер, и обслуживаются одним драйвером. Младший номер определяет, к какому именно устройству драйвер должен обратиться для считывания/записи данных, т.к. к системе может быть подключено четыре АТА-устройства. Младший номер устройства - это 32-х разрядное число следующего формата:
0x00000XYY,
где X - номер канала (устройства)
YY - номер раздела на устройстве. Если этот номер равен нулю, драйвер будет обращаться к физическому устройству (RAW-режим), расположенному на канале X.
Как видно из схемы, все обращения к драйверу жесткого диска со стороны драйвера файловой системы выполняются через подсистему I/O.
В структуре драйвера блочного устройства определены следующие функции:
- функция инициализации и регистрации устройства в системе;
- функция, принимающая запросы подсистемы ввода/вывода (подсистема I/O) на чтение/запись данных (функция-диспетчер);
- функции чтения/записи данных
Перед обращением к драйверу выполняется его инициализацию. Команда инициализации поступает из подсистемы I/O. Во время инициализации драйвер выполняет следующие действия:
- опрашивает все каналы (их четыре) на предмет наличия АТА-устройств. Если устройство присутствует, драйвер считывает информацию о таблице разделов этого устройства и о самом устройстве (информацию идентификации устройства);
- выполняет процедуру регистрации в системе соответствующего блочного устройства путем заполнения таблицы блочных устройств (ТБУ). Каждая запись ТБУ содержит информацию об одном драйвере. Индексом в таблице является старший номер устройства.
После регистрации в системе драйвер готов к работе.
Для считывания (записи) данных с блочного устройства драйвер файловой системы обращается к подсистеме I/O. Одним из параметров, передаваемых подсистеме I/O, является старший номер устройства, для которого необходимо выполнить операцию считывания данных (записи данных). Используя старший номер в качестве индекса, подсистема I/O находит в ТБУ адрес функции-диспетчера соответствующего драйвера, и выполняет вызов данной функции, передав тем самым драйверу команду для выполнения, например, команду чтения. Функция-диспетчер драйвера принимает команду от подсистемы I/O, формирует запрос к устройству путем заполнения глобальной структуры ata_request, и вызывает функцию чтения с устройства. Считанные данные помещаются в буфер, адрес которого передается драйвером файловой системы через подсистему I/O. В случае, если поступила команда на запись, по этому адресу будут находяться данные, которые необходимо записать на устройство.
В нашем примере драйвер диска имеет ограничение - операции чтения/записи выполняются только для primary-разделов. О том, что такое primary-разделов и какие ещё бывают, нам расскажет следующий пункт.
2. Таблица разделов жесткого диска
На жестком диске по физическому адресу 0-0-1 располагается главная загрузочная запись (master boot record, MBR). В структуре MBR находятся следующие элементы:
- внесистемный загрузчик (non-system bootstrap - NSB);
- таблица описания разделов диска (partition table, PT). Располагается в MBR по смещению 0x1BE и занимает 64 байта;
- сигнатура MBR. Последние два байта MBR должны содержать число 0xAA55.
Таблица разделов описывает размещение и характеристики имеющихся на винчестере разделов. Разделы диска могут быть двух типов - primary (первичный, основной) и extended (расширенный). Максимальное число primary-разделов равно четырем. Наличие на диске хотя бы одного primary-раздела является обязательным. Extended-раздел может быть разделен на большое количество подразделов - логических дисков.
Упрощенно структура MBR представлена в таблице 1. Таблица разделов располагается в конце MBR, для описания раздела в таблице отводится 16 байт.
Таблица 1. Структура MBR.
Смещение (offset) Размер (Size) Содержимое (contents)
------------------------------------------------------------------------
0 446 Программа анализа таблицы разделов
и загрузки System Bootstrap
с активного раздела
-------------------------------------------------------------------------
0x1BE 16 Partition 1 entry (первый раздел)
-------------------------------------------------------------------------
0x1CE 16 Partition 2 entry
-------------------------------------------------------------------------
0x1DE 16 Partition 3 entry
-------------------------------------------------------------------------
0x1EE 16 Partition 4 entry
-------------------------------------------------------------------------
0x1FE 2 Сигнатура 0xAA55
Первым байтом в элементе раздела идет флаг активности раздела (0 - неактивен, 0x80 - активен). Он служит для определения, является ли раздел системным загрузочным и есть ли необходимость производить загрузку операционной системы с него при старте компьютера. Активным может быть только один раздел. За флагом активности раздела следуют координаты начала раздела - три байта, означающие номер головки, номер сектора и номер цилиндра. Затем следует кодовый идентификатор System ID, указывающий на принадлежность данного раздела к той или иной операционной системе. Идентификатор занимает один байт. За системным идентификатором расположены координаты конца раздела - три байта, содержащие номера головки, сектора и цилиндра, соответственно. Следующие четыре байта - это число секторов перед разделом, и последние четыре байта - размер раздела в секторах.
Таким образом, раздел можно описать при помощи следующей структуры:
struct pt_struct {
u8 bootable; // флаг активности раздела
u8 start_part[3]; // координаты начала раздела
u8 type_part; // системный идентификатор
u8 end_part[3]; // координаты конца раздела
u32 sect_before; // число секторов перед разделом
u32 sect_total; // размер раздела в секторах (число секторов в разделе)
};
Итак, все необходимые теоретические сведения у нас есть, можно приступить непосредственно к рассмотрению программной реализации модуля.
3. Структуры и переменные
Начнем с описания переменных и информационных структур, которые будут использованы при разработке.
Введем обозначение типов данных:
typedef unsigned char u8;
typedef unsigned short u16;
typedef unsigned int u32;
typedef unsigned long long u64;
Системные ресурсы, выделенные каналам:
#define CH0 0x1f0 // Primary Master, канал 0
#define CH1 0x1E8 // Primary Slave, канал 1
#define CH2 0x170 // Secondary Master, канал 2
#define CH3 0x168 // Secondary Slave, канал 3
Биты основного регистра состояния ATA-устройства (назначение каждого бита рассмотрено в [1]):
#define BSY 0x80 // флаг занятости устройства
#define DRDY 0x40 // готовность устройства к восприятию команд
#define DF 0x20 // индикатор отказа устройства
#define DRQ 0x08 // индикатор готовности устройства к обмену данными
#define ERR 0x01 // индикатор ошибки выполнения операции
Получение номера устройства и номера раздела из младшего номера файла устройства выполняют макросы:
#define GET_DEV(X) ((X & 0x00000F00) >> 8);
#define GET_PART(X) (X & 0x000000FF);
Размер записи таблицы разделов (0x10):
#define PT_SIZE 0x10
Следующий массив структур заполняется драйвером диска в процессе инициализации ATA-устройств, подключенных к системе:
struct dev_status_struct {
u8 status;
struct hd_driveid hd;
pt_t pt[4];
} dev_status[4];
Назначение полей структуры:
- status - информация о состоянии устройства (0/1 - отсутствие/наличие)
- struct hd_driveid hd - информация идентификации устройства. Данная структура содержится в заголовочном файле <linux/hdreg.h>
- pt - информация о таблице разделов на устройстве
Для работы с полями данной структуры определим несколько макросов:
#define DEV_STAT(X) dev_status[X].status
#define DEV_ID(X) dev_status[X].hd
#define DEV_PT(X,Y) dev_status[X].pt[Y]
Здесь X - номер устройства, Y - номер раздела
Поскольку жесткий диск - устройство блочное, то обмен данными осуществляется только блоками. Информация о том, сколько на разделе устройства блоков и размер одного блока будет находиться здесь:
typedef struct device_info_struct {
int blocks_num;
int block_size;
} device_info_t;
Размер блока на устройстве и размер одного сектора (в байтах):
#define BLK_SIZE 2048
#define BYTE_PER_SECT 512
Драйверу устройства можно послать три команды:
#define WRITE 0 // записать данные на устройство
#define READ 1 // прочитать данные с устройства
#define STAT 2 // получить характеристику раздела устройства
По команде STAT драйвер вернет о информацию о размере одного блока и число блоков на разделе устройстве. Данной информацией заполняется структура struct device_info_struct
Идентификатор ATA-устройства:
#define ATA 1
4. Драйвер ATA-устройства (жесткого диска)
Ресурсы, выделенные каналам, разместим в массиве:
u16 channels[4] = { CH0, CH1, CH2, CH3 };
Адресация к регистрам ATA-контроллера выполняется при помощи следующих макросов:
- фиксация ошибки выполнения команды:
int check_error(u8 dev)
{
unsigned char a;
IN_P_B(a, ATA_STATUS(dev));
if (a & ERR) return 1;
return 0;
}
В соответствии с алгоритмом, первая команда, посылаемая драйверу - это команда инициализации. Команда выполняется путем вызова функции инициализации, которая находится в теле драйвера:
/* Инициализация драйвера АТА */
int hd_init()
{
int i = 0, major = 0;
get_ata_info(); // опросить каналы на предмет наличия ATA-устройств
show_ata_info(); // отобразить информацию о найденых устройствах
get_pt_info(); // получить таблицу разделов с каждого устройства
major = reg_blkdev(MAJOR_ATA,"ATA",&hd_request); // зарегистрировать драйвер устройства
return major;
}
При выполнении инициализации драйвер опрашивает все каналы на предмет наличия ATA-устройств, отображает информацию о найденых устройствах, получает от каждого найденого устройства таблицу разделов и регистрируется в системе.
Опрос каналов выполняет функция get_ata_info(). Вот как она выглядит:
void get_ata_info()
{
Для поиска устройств организуем цикл из четырех итераций:
int dev = 0;
for(; dev < 4 ; dev++) {
Ожидаем освобождение устройства. Если таймаут исчерпан - на данном канале устройство отсутствует:
Если устройство на канале присутствует, то пытаемся получить от него информацию идентификации. Информация о наличии/отсутствии устройства на канале будет сохранена в поле status структуры struct dev_status_struct (см. раздел "Структуры и переменные"):
Вывод информации об устройствах, подключенных к системе, выполняет функция show_ata_info():
void show_ata_info()
{
int i = 0;
for(; i < 4; i++) {
printf("ATA%d - ",i);
if(!DEV_STAT(i)) printf("none\n");
if(DEV_STAT(i) == ATA) {
printf("exists\n");
printf("\tType - ATA Disk drive\n");
printf("\tModel - %s\n",DEV_ID(i).model);
printf("\tLBA capacipty - %d\n",DEV_ID(i).lba_capacity);
}
}
}
Получаем от каждого устройства таблицу разделов:
void get_pt_info()
{
u8 dev;
u32 minor = 0;
int i = 0;
unsigned char buff[0x200];
Опрашиваем все ATA устройства и получаем от каждого таблицу разделов:
for(; i < 4; i++) {
dev = GET_DEV(minor);
if(DEV_STAT(CURRENT) != ATA) continue;
if(hd_request(minor,READ,0,1,buff) < 0) break;
memcpy(dev_status[dev].pt,(struct pt_struct *)(buff+0x1BE),PT_SIZE*4);
minor += 0x100;
}
return;
}
Считывание таблицы разделов с устройства выполняет функция-диспетчер hd_request, одним из параметров которой является младший номер устройства. Опрос устройств начинается с нулевого канала, при этом поле номера раздела равно нулю, что означает работу с устройством в RAW-режиме.
После того, как информация о таблице разделов собрана с каждого устройства, драйвер регистрируется в системе, вызвав функцию reg_blkdev. В параметрах функции указывается старший номер устройства, соответствующий позиции в таблице блочных устройств, имя драйвера и адрес функции-диспетчера. Функция регистрации входит в состав подсистемы ввода-вывода, которую мы рассмотрим ниже.
4.1. Функция-диспетчер.
По определению, данная функция принимает запросы подсистемы I/O на чтения/запись данных.
Для выполнения команды функция-диспетчер формирует запрос к устройству, который представляет собой структуру следующего вида:
struct ata_request {
u8 dev; /* номер канала (устройства) : 0,1,2,3 */
u16 *buff; /* указатель на буфер с данными для чтения/записи (r/w) на устройство */
u32 nlba; /* номер логического сектора для r/w */
u32 nsect; /* число секторов для r/w */
u8 err; /* индикатор ошибки выполнения команды*/
u8 lock; /* флаг блокировки буфера данных на время выполнения поступившей команды */
u8 complite; /* флаг завершения операции (команды) */
} dev_r;
#define CURRENT dev_r.dev
Функция выглядит следующим образом:
int hd_request(u32 minor, u8 cmd, u32 start_sect, u32 s_count, u8 *buff)
{
Параметры функции-диспетчера:
- u32 minor - младший номер устройства;
- u8 cmd - команда, подлежащая выполнению. Их у нас целых три - READ, WRITE, STAT (см. раздел "Структуры и переменные");
- u32 start_sect - адрес стартового сектора для чтения/записи данных. Адрес задается в формате LBA и по сути является порядковым номером сектора на устройстве;
- u32 s_count - число секторов для чтения/записи;
- u8 *buff - указатель на буфер, куда необходимо поместить прочитанные с устройства данные, если поступила команда READ. Если поступила команда WRITE, по этому адресу будут находится данные, которые надо записать на устройство.
Извлекаем из младшего номера номер устройства и номер раздела на устройстве:
u16 part = GET_PART(minor);
u8 command;
CURRENT = GET_DEV(minor);
Проверяем, присутствует ли в системе устройство, с которого мы пытаемся прочесть данные (или записать):
if(DEV_STAT(CURRENT) != ATA) return -1;
Работать можно только с основными разделами, или со всем устройством в RAW-режиме, поэтому проверяем номер раздела. Он не должен быть больше четырех:
if(part > 4) return -1;
Проверяем, не заблокирован ли буфер для данных в структуре запроса struct ata_request. Если нет - блокируем его на время выполнения запроса, выставив флаг lock:
while(dev_r.lock) continue;
dev_r.lock = 1;
Заполняем поля структуры запроса значениями:
dev_r.nlba = start_sect; /* стартовый сектор */
dev_r.nsect = 1; /* число cекторов для чтения/записи */
dev_r.buff = (unsigned short *)buff;
Определяем, какая команда поступила:
switch(cmd) {
case STAT:
return stat_hd(part);
break;
case READ:
command = 0x20;
handler = &intr_read;
break;
case WRITE:
command = 0x30;
handler = &intr_write;
break;
Если приходит команда STAT, драйвер просто вернет подсистеме I/O информацию о характеристиках раздела устройства, такую как размер блока и число блоков на разделе устройстве, вызвав функцию stat_hd:
Уменьшаем счетчик секторов. Если он равен нулю - завершаем выполнение команды и выходим из цикла. Если нет - считываем следующий сектор и смещаем указатель в буфере на 512 байт (размер сектора):
Рассмотрение драйвера жесткого диска на этом завершим, и переходим к рассмотрению подсистемы ввода-вывода.
5. Подсистема I/O
В соответствии с алгоритмом, подсистема I/O выполняет инициализацию драйвера блочного устройства, и в дальнейшем принимает запросы драйвера файловой системы на чтение/запись данных на устройство. Во время инициализации соответствующий драйвер заполняет таблицу блочных устройств, которая представляет собой массив структур:
static struct blkdev_struct blkdev[MAX_BLKDEV],
где MAX_BLKDEV - число элементов в таблице блочных устройств, и, соответственно, количество блочных устройств, которое можно подключить к системе:
#define MAX_BLKDEV 256
Элемент таблицы блочных устройств представляет собой структуру следующего вида:
struct blkdev_struct {
const char name[20];
int (*dev_request)(u32, u8, u32, u32, unsigned char *);
};
Назначение полей структуры struct blkdev_struct:
- const char name[20] - имя драйвера блочного устройства
- int (*dev_request)(u32, u8, u32, u32, unsigned char *) - адрес функции-диспетчера драйвера блочного устройства.
Таблица блочных устройств проиндексирована при помощи старшего номера устройства. Для ATA-устройств старший номер равен 5:
#define MAJOR_ATA 5
Процедура инициализации выполняется путем вызова функции blkdev_init():
Во время инициализации вызывается функция hd_init(), находящаяся в теле драйвера. Эту функцию мы уже практически полностью рассмотрели, за исключением функции reg_blkdev - функции регистрации драйвера устройства в системе:
Параметры вызова функции мы уже рассмотрели. Эта функция заполняет соответствующий элемент таблицы блочных устройств, и, тем самым, у нас появляется возможность обратиться к функции-диспетчеру драйвера ATA-устройства.
Эту возможность реализует функция blkdev_io():
Параметры функции blkdev_io():
- u32 major - старший номер устройства, и, соответственно, индекс в таблице блочных устройств;
- u32 minor - младший номер, определяет номер устройства и номер раздела на устройстве;
- u8 cmd - команда, посылаемая устройству;
- u32 start_sect - адрес стартового сектора для чтения(записи);
- u32 count - число секторов для чтения(записи);
- u8 *buff - указатель на буфер для данных;
Перед выполнением операций чтения/записи данных на раздел устройства сперва необходимо получить характеристики раздела, такие как размер блока на разделе и количество этих блоков. Для этого устройству посылается команда STAT при помощи функции stat_blkdev():
Получив характеристики раздела устройства, можно приступать к чтению/записи данных. Функция read_blkdev(), которую мы сейчас рассмотрим, выполняет чтение данных с раздела жесткого диска. Одновременно эта функция является точкой входа для драйвера файловой системы.
Параметрами функции являются старший и младший номер устройства, смещение к данным на разделе в байтах (т.к. драйвер ФС "видит" раздел как последовательность байт), число байт для считывания и указатель на буфер, куда будут помещены считанные данные.
Так как драйвер жесткого диска считывает информацию блоками, то необходимо преобразовать величину смещения в номер блока на устройстве, и при этом нет никаких гарантий, что смещение к данным попадет точно на границу блока. Поэтому алгоритм считывания данных следующий с раздела жесткого диска следующий:
- определяется номер блока, в который "попадает" величина смещения, количество блоков для чтения, и эти блоки считываются в дисковый кеш;
- определяется величина смещения к данным в кеше, и эти данные копируются в область памяти, на которую указывает последний параметр вызова функции read_blkdev().
Весь этот процесс показан на рис. 2.
Определим необходимые переменные:
u32 start_lba, // стартовый сектор для чтения
s_count, // число секторов для чтения
start_block, // стартовый блок для чтения (0,1,2, ...)
end_block, // конечный блок для чтения. Может быть равен стартовому
tail, // смещение к данным в буферном кеше
num_block; // число блоков для считывания
device_info_t dev_i;
u8 *cache_buff; // указатель на начало буферного кешв
printf("Стартовый сектор для чтения на устройстве - %d\n",start_lba);
printf("Число секторов для чтения - %d\n\n",s_count);
И вот теперь вызываем функцию-диспетчер соответствующего блочного устройства (жесткого диска), передав ей команду для выполнения и необходимые параметры:
Перед тем, как приступить к рассмотрению драйвера файловой системы ext2, необходимо познакомиться с самой файловой системой, с её логической структурой. Об этом читайте во второй части статьи.
Исходники к статье
ЧАСТЬ 2
6. Структура файловой системы ext2
6.1. Основные компоненты файловой системы 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.
6.2. Формат группы блоков
Обобщенная структурная схема файловой системы ext2 представлена на рис.3.
Практически все группы блоков имеют одинаковый формат. В каждой группе, помимо информационных блоков, хранится информация о занятости блоков и inode-ов группы в виде битовой карты. В состав группы блоков 0 входят также суперблок и таблица дескрипторов групп, которую мы рассмотрим ниже.
Битовая карта занятости блоков обычно расположена в первом блоке группы. Если в группе присутствует резервная копия суперблока, битовая карта располагается во втором блоке группы. Размер битовой карты - один блок. Каждый бит этой карты обозначает состояние блока. Если бит установлен (1), то блок занят, если сброшен (0) - блок свободен. Первому блоку группы соответствует нулевой бит карты, второму блоку - первый бит и т.д.
Inode-ы, находящиеся в пределах одной группы, собраны в таблицу. В битовой карте занятости inode-ов группы каждый бит характеризует состояние элемента в таблице inode-ов группы.
Каждая группа блоков описывается при помощи дескриптора группы блоков. Дескриптор группы - это структура, которая содержит информацию о адресах битовой карты занятости блоков, битовой карты занятости inode-ов и таблицы inode-ов соответствующей группы. Все дескрипторы групп собраны в таблицу дескрипторов групп, которая хранится в группе блоков 0. Также, как и для суперблока, операционная система создает резервные копии таблицы дескрипторов групп.
6.3. Алгоритм чтения файла
Каждый 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-a файла.
Несколько первых номеров inode зарезервированы файловой системой, их перечень содержится в заголовочном файле <linux/ext2_fs.h>:
Для записи корневого каталога зарезервирован 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-а извлечь адреса информационных блоков и осуществить чтение информации, находящейся в этих блоках
На рис. 4 подробно показаны этапы чтения файла /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".
Определив номер inode, можно получить доступ к информационным блокам файла (этапы 7-11):
7. Вычисляется номер группы, в которой находится данный inode, и его позиция в таблице inode-ов группы (предположим, что номер группы равен B, а позиция в таблице - X)
8. Из таблицы дескрипторов групп извлекаем дескриптор группы блоков B и из него считывается адрес таблицы inode-ов этой группы блоков
9. Из группы блоков B считывается таблица inode-ов
10. Из таблицы inode-ов группы блоков B считывается inode, находящийся в позиции X
11. Из считанного inode извлекается адреса блока с содержимым файла /test.file и выполняется чтение информации из блока с указанным адресом
Структурные типы, описывающие основные компоненты файловой системы ext2 - суперблок, дескриптор группы блоков, информационный узел, запись каталога - определены в заголовочном файле <linux/ext2_fs.h>. Рассмотрим кратко поля, которые входят в каждую из этих структур.
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] - адреса информационых блоков (включая все косвенные ссылки)
Значение EXT2_N_BLOCKS также определено в файле <linux/ext2_fs.h>:
/*
* 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)
4. Структура записи каталога struct ext2_dir_entry_2
#define EXT2_NAME_LEN 255
__u32 inode - номер inode-а файла
__u16 rec_len - длина записи каталога
__u8 name_len - длина имени файла
char name[EXT2_NAME_LEN] - имя файла
Ознакомившись со структурой файловой системы ext2, можно приступить к рассмотрению программной реализации драйвера файловой системы.
7. Драйвер файловой системы
Начнем с описания заголовочных файлов и переменных.
Основным заголовочным файлом является <linux/ext2_fs.h>. С его составом мы только что ознакомились, теперь займемся переменными.
Введем временное ограничение на размер данных, считываемых из файла:
#define TEMP_SIZE_LIMIT 49152 // 12 блоков по 4096 байт
Буфер для хранения таблицы дескрипторов групп:
unsigned char buff_grp[4096];
Информационный буфер:
unsigned char buff[4096];
u32 major = 0; // старший номер устройства
u32 minor = 0; // младший номер устройства
u64 start = 0; // смещение к данным на разделе устройства
u64 count = 0; // размер блока считываемых данных
Рассмотрим несколько вспомогательных функций, которые нам понадобятся для работы:
Функция set_perm() запрашивает у системы разрешение доступа к портам ATA-контроллера
void set_perm()
{
ioperm(CH0,8,1);
ioperm(CH1,8,1);
ioperm(CH2,8,1);
ioperm(CH3,8,1);
return;
}
Функция release_perm() забирает у нас эти права:
void release_perm()
{
ioperm(CH0,8,0);
ioperm(CH1,8,0);
ioperm(CH2,8,0);
ioperm(CH3,8,0);
Задаем смещение к суперблоку и его размер:
start = 1024;
count = sizeof(sb);
Смещение к суперблоку равно 1024, т.к. первые 1024 байт на разделе с файловой системой ext2 зарезервированы для загрузчика.
memset(&sb,0,1024);
Для считывания данных обращаемся к подсистеме ввода/вывода, задав все необходимые параметры:
if(read_blkdev(major,minor,start,count,(u8 *)&sb) < 0) {
printf("Error read superblock\n");
exit(-1);
}
В результате структура sb будет содержать суперблок.
Если все в порядке и включен режим отладки, выведем информацию о файловой системе:
#ifdef DEBUG
printf("\nSuperblock info\n-----------\n");
printf("Inodes count\t\t-\t%u\n",sb.s_inodes_count);
printf("Blocks count\t\t-\t%u\n",sb.s_blocks_count);
printf("Block size\t\t-\t%u\n",1024 << sb.s_log_block_size);
printf("First inode\t\t-\t%d\n",sb.s_first_ino);
printf("Magic\t\t\t-\t0x%X\n",sb.s_magic);
printf("Inode size\t\t-\t%d\n",sb.s_inode_size);
printf("Inodes per group\t-\t%u\n",sb.s_inodes_per_group);
printf("Blosks per group\t-\t%u\n",sb.s_blocks_per_group);
printf("First data block\t-\t%u\n\n",sb.s_first_data_block);
#endif
return;
}
Функция read_gd() выполняет чтение дескрипторов групп:
void read_gd()
{
Определяем размер блока файловой системы:
BLKSIZE = 1024 << sb.s_log_block_size;
Вычисляем смещение к блоку, в котором находятся дескрипторы групп:
start = (sb.s_first_data_block + 1) * BLKSIZE;
count = BLKSIZE;
Следующая функция получает содержимое inode по его номеру:
void get_inode(int i_num, struct ext2_inode *in)
{
У функции только один параметр - i_num, номер inode файла
Структура дескриптора группы:
struct ext2_group_desc gd;
u64 group, index;
Вычисляем по формуле, приведенной в пункте 6.3, номер группы, в которой находится inode под номером i_num:
group = (i_num - 1) / sb.s_inodes_per_group;
Копируем этот дескриптор в структуру gd:
memset((void *)&gd, 0, sizeof(gd));
memcpy((void *)&gd, buff_grp + group*(sizeof(gd)), sizeof(gd));
Вычисляем по формуле из п. 6.3 позицию inode-а в таблице inode-ов данной группы:
index = (i_num - 1) % sb.s_inodes_per_group;
Вычисляем смещение к искомому inode-у и считываем его в структуру in:
start = (u64)(gd.bg_inode_table) * BLKSIZE + index * sb.s_inode_size;
count = sb.s_inode_size; // размер inode
Чтение информационных блоков файла выполняет функция read_iblock().
void read_iblock(struct ext2_inode *i, int blknum)
{
Параметры функции:
- struct ext2_inode *i - структура, содержащая информацию inode-а соответствующего файла
- int blknum - номер блока из последовательности номеров, содержащихся в этом inode, который мы хотим прочитать
Вычисляем смещение к информационному блоку файла и считываем его:
start = (u64)(i->i_block[blknum])*BLKSIZE;
count = BLKSIZE;
if(read_blkdev(major,minor,start,count,buff) < 0) {
printf("Error read info block\n");
exit(-1);
}
Получить номер inode по имени файла можно при помощи функции get_i_num:
int get_i_num(char *name)
{
Параметр функции - имя файла. Возвращаемое значение - номер inode файла.
int rec_len = 0;
Структура, описывающая формат записи корневого каталога:
struct ext2_dir_entry_2 dent;
В буфере buff находится массив записей каталога. Для определения порядкового номера inode файла необходимо найти в этом массиве запись с именем этого файла. Для этого организуем цикл:
Длина имени файла равная нулю означает, что мы перебрали все записи в буфере buff и записи с именем нашего файла не нашли. Значит, пора возвращаться:
if(!dent.name_len) return -1;
Поиск выполняется путем сравнения имен файлов. Если имена совпадают - выходим из цикла
if(!memcmp(dent.name, name, strlen(name))) break;
Если имена не совпали - смещаемся к следующей записи:
rec_len += dent.rec_len;
}
В случае успеха возвращаем номер inode файла:
return dent.inode;
}
Функция ata_init() выполняет запрос к подсистеме ввода/вывода с просьбой выполнить процедуру инициализации драйвера блочного устройства:
int ata_init()
{
int i = 0;
u8 dev = GET_DEV(minor); /* номер канала (0,1,2,3) */
#ifdef DEBUG
/* Информация об основных разделах на устройстве 0 */
for(;i < 4; i++) {
printf("\nТип %d раздела - 0x%x\n",i,DEV_PT(dev,i).type_part);
printf("Признак загрузки - 0x%x\n",DEV_PT(dev,i).bootable);
printf("Секторов в разделе %d - %d\n",i,DEV_PT(dev,i).sect_total);
printf("Размер раздела %d в блоках - %d\n",i,DEV_PT(dev,i).sect_total/(BLK_SIZE/512));
printf("Секторов перед разделом %d - %d\n\n",i,DEV_PT(dev,i).sect_before);
}
#endif
return 0;
}
"Главными воротами" драйвера файловой системы является функция ext2_read_file(). Через эту функцию драйвер взаимодействует с пользовательский приложением:
Параметры функции:
- maj_num - старший номер устройства
- min_num - младший номер устройства
- full_path - абсолютное путевое имя файла
- data_buff - буфер для данных
- num - сколько байт считывать из файла
- seek - смещение в файле
Переменные и структуры:
Структура информационного узла (inode):
struct ext2_inode in;
Буфер для временного хранения имени файла (будет нужен при разборе абсолютного путевого имени):
unsigned char tmp_buff[EXT2_NAME_LEN];
static int i = 1;
int n, i_num, outf, type;
Первым символом в абсолютном путевом имени файла должен быть прямой слэш (/). Проверяем это:
Сейчас в буфере buff находятся все записи корневого каталога (для контроля сохраним их в отдельном файле по имени root.dent). Теперь, имея записи корневого каталога, мы можем добраться до содержимого файла test.file, используя приведенный в пункте 6.3 алгоритм чтения файла. С этой целью организуем цикл. В теле цикла проведем разбор абсолютного путевого имени файла, выделяя его элементы - подкаталоги (он у нас одни, home) и имя искомого файла (test.file). Для каждого элемента определим порядковый номер inode-а, считаем этот inode и затем получим содержимое нулевого блока (из последовательности адресных блоков, находящихся в inode-е):
Функция read_file_blocks выполняет чтение информационных блоков файла:
int read_file_blocks(struct ext2_inode *in, u8 *data_buff, u32 *num, u32 seek)
{
Параметры функции:
- struct ext2_inode *in - структура, содержащая inode файла
- u8 *data_buff - буфер, куда будут считаны данные
- u32 *num - сколько байт считывать из файла. Этот параметр передается по ссылке, т.к. нам придется его подкорректировать при необходимости, и вернуть вызывающей функции измененным
- u32 seek - смещение к данным в файле
int i = 0, n = 0;
u16 start_block, end_block, num_block, tail;
u8 *cache_buff;
В нашем примере, в целях упрощения, мы ограничили объем данных, которые мы можем считать из файла, первыми 12-ю блоками (прямые ссылки, см. рис. 3). Поэтому, перед тем как прочитать файл, необходимо проверить, чтобы размер запрашиваемых данных (num) и смещение в файле (seek) не превысили установленные границы:
Если все в порядке, приступаем непосредственно к чтению файла.
В целом, алгоритм считывания данных из файла аналогичен алгоритму считывания данных с жесткого диска. Поэтому за комментариями обратитесь к п. 5 (функция read_blkdev()).
Считываем информационные блоки файла в буферный кеш:
i = start_block;
for(; n < num_block; n++) {
read_iblock(in,i);
memcpy((cache_buff + (n * BLKSIZE)), buff, BLKSIZE);
i += 1;
}
Копируем данные из буферного кеша:
memcpy(data_buff, (cache_buff + tail), (*num));
free(cache_buff);
return 0;
}
Итак, мы закончили рассмотрение драйвера файловой системы. Остался последний элемент схемы - приложение пользователя.
8. Приложение пользователя
Роль приложения пользователя у нас играет функция main:
int main()
{
u32 major_num = MAJOR_ATA; // старший номер устройства
u32 minor_num = 3; // младший номер устройства
u32 seek = 0; // смещение в файле
u32 num = 300; // сколько байт считываеть
u8 *data_buff; // буфер для данных
u8 *full_path = "/home/test.file"; // абсолютное путевое имя файла
int outf;
Младший номер равен 3. Это означает, что считывание информации производится с третьего основного раздела жесткого диска, который подключен как Primary Master.
Для сборки приложения введите команду make. В результате в текущем каталоге появиться исполняемый файл hdd. Далее, в каталоге /home создайте файл test.file любого содержания и введите команду sync. После этого запустите на выполнение файл hdd. В результате в текущем каталоге появиться файл out, в котором будет продублирована часть информации из файла /home/test.file, в соответствии с параметрами seek и num, заданными в функции main.
Литература:
1. "Работа с жестким диском на программном уровне", http://www.lowlevel.ru/articles/hdd_io.htm 2. А.В.Гордеев, А.Ю.Молчанов, "Системное программное обеспечение", издательский дом "Питер".
3. В.Мешков, "Архитектура файловой системы ext2", журнал "Системный администратор", ╧ 11(12), 2003 г., ЗОА "Издательский дом "Учительская газета".
Исходники к статье
