Фрагментация в Linux: мифы и реальность
Введение
Мир Linux можно разделить на несколько больших групп, среди которых наиболее ярко представлены три. Первая — это ортодоксы (фанаты). Они призывают устанавливать их любимую ОС на все, что можно подключить к сети 220 В. Как правило, саму систему они знают весьма поверхностно, но компенсируют этот недостаток своим воинствующим нонконформизмом. Вторая — это, так сказать, патриархи. Свое знакомство с UNIX они начинали еще с PDP-11, в эпоху MS-DOS они писали драйверы, а сейчас развлекаются редактированием исходников ядра системы. Третья — это колеблющиеся. О них стоит поговорить особо. На их компьютерах, как правило, установлены две ОС. Поработав некоторое время в одной, они пытаются сделать то же в другой, надеясь, что получится лучше. Чаще всего не получается. Тогда они решают снести разочаровавшую их систему, но агрессивная реклама ее сторонников в сети и книги из серии "освой за 3 дня" заставляют отложить казнь системы до другого раза и задуматься в стиле: "а вдруг я делаю все неправильно". Время проходит, бесполезная ОС продолжает жить на жестком диске, хотя загружается все реже и реже, а у вчерашнего потенциального ее пользователя развивается комплекс неполноценности. Так система теряет сторонников. А виноваты в этом та самая агрессивная реклама и книги из той же серии. Реклама содержит множество ничем не подтвержденных мифов, ну, а о книгах вообще не хотелось бы упоминать. Я не помню случая, чтобы Microsoft позиционировала свою ОС как самую устойчивую и надежную. Теперь откройте любой учебник формата "Linux для начинающих". Открыли? Где-то там, в самом начале, где описаны преимущества Linux перед другими ОС, и будет искомая фраза о ее непревзойденной надежности. Не беда, что это нигде по тексту книги не обосновано. Пользователь уже перевернул страницу.
Похожая ситуация наблюдается с предметом нашего обсуждения — фрагментацией. Ни один из известных мне дистрибутивов Linux не содержит встроенных средств для дефрагментации дискового пространства, имеющего честь нести на себе эту ОС. Что, может, забыли написать? Да нет же. Откроем любой учебник системного администратора UNIX. Если там описывается файловая система ufs, то наверняка будет фраза о ее врожденной нефрагментируемости. А что же файловые системы ext2fs и ext3fs? Да ведь это прямые наследники ufs, скажут нам ортодоксы. Прямые да не очень, прошу прощения за каламбур. Наша задача — показать это. Мы сделаем это, построив карту дискового пространства, занимаемого файлом, и посмотрим, можно ли ее оптимизировать.
Поколение EXT
Для того, чтобы осуществить задуманное, мы должны пройти весь путь, который проходит драйвер файловой системы, выполняя загрузку требуемого файла в память. Поэтому вначале будет дан некоторый теоретический материал о строении файловых систем, используемых в Linux. Мы будем работать с ext2fs и ext3fs, создаваемыми по умолчанию при установке подавляющего большинства дистрибутивов Linux. Это две файловые системы-близнецы, отличающиеся лишь поддержкой журналирования и слегка видоизмененной процедурой удаления файлов в ext3fs. Перед тем, как излагать структуры данных этих близнецов, определим, что такое фрагментация вообще и ее разновидности. Итак, внешней дисковой фрагментацией будем называть расположение данных в несмежных областях физического дискового пространства. Далее в тексте под термином "фрагментация" мы будем подразумевать именно этот ее вид. В отличие от нее, внутренней дисковой фрагментацией будем считать потерю физического дискового пространства из-за недостаточного заполнения его областей данными. Здесь мы вплотную подошли к такому ключевому понятию любой файловой системы, как блок данных, или кластер. Дадим определение и ему. Блоком данных, или кластером, называется атомарная (минимальная) часть физического дискового пространства, которая может быть выделена файлу. Отсюда становится ясным происхождение внутренней фрагментации. Она возникает, когда размер файла не кратен размеру блока данных (кластера). Тема размера блока данных и внутренней фрагментации требует отдельного обширного обсуждения и здесь затрагиваться не будет. Отметим только, что термин "кластер" применяется для ОС от Microsoft. Мы же, как и принято в мире UNIX, будем оперировать понятием "блок данных" (далее по тексту — просто "блок"). Еще одного разъяснения требуют использующиеся далее термины "раздел (partition)" и "том (volume)". Многие считают, что это одно и то же. Например, если у типичного ортодокса спросить, чем на его домашней системе является /dev/hda1 — томом или разделом — он наверняка ответит: "а какая разница". Поэтому это следует разъяснить. Томом является структура данных ОС, содержащая указатели на множество физических секторов диска. Разделом также является структура данных ОС, содержащая указатели, опять же, на множество физических секторов диска, но при этом обязательно являющихся смежными. Теперь становится ясным соотношение между ними. Раздел является томом (ярый поклонник ООП написал бы что-то вроде "class partition : public volume", или лучше "class partition extends volume"). Далее, употребляя термин "диск", я буду иметь в виду именно раздел. Теперь настала пора описывать структуры данных наших файловых систем. Замечу, что здесь будут описаны основные функциональные возможности этих структур и тот минимум их полей, который необходим для решения нашей задачи. Остальную информацию можно найти в многочисленных HOWTO (да и изучение "голых" заголовочных файлов Linux может при желании (вашем) дать исчерпывающие сведения по большинству вопросов). Например, все описываемые ниже структуры в дистрибутиве Red Hat Enterprise Linux 5 находятся в файле /usr/include/linux/ext3_fs.h. Соответственно, будут приводиться описания полей структур, содержащиеся в этом файле этого дистрибутива. Итак, тремя китами, на которых стоят (чуть не написал "покоятся") файловые системы ext2 и ext3, являются следующие сущности:
1. Суперблок, struct ext3_super_block. Начинается по смещению 1024 байт от начала диска и содержит наиболее общую и важную информацию о файловой системе. В суперблоке нам понадобятся следующие поля:
1.1. Размер блока, __u32 s_log_block_size. Заметим, что он хранится в логарифмической шкале — т.е. содержит число, на которое нужно сдвинуть влево число 1024, чтобы получить искомый размер блока. Неплохо, да? Если учесть, что размер блока редко превышает 4096 байт, что вполне умещается в двухбайтовом слове, непонятно, зачем разработчикам понадобилось так "заворачивать" это простое поле.
1.2. Число блоков на группу, __u32 s_blocks_per_group. О группах блоков весь разговор впереди — пока лишь отметим, что для удобства адресации блоки логически объединяются в группы. Тогда абсолютное смещение блока на диске становится относительным его смещением в группе блоков. 1.3. Число инодов (inodes) на группу, __u32 s_inodes_per_group. Индексный узел (инод) — еще одна структура данных, информация в которой имеет критическое значение для функционирования системы. Достаточно сказать, что она содержит указатели на блоки, выделенные файлу. О ней также весь разговор впереди.
1.4. Сигнатура суперблока, __u16 s_magic. Содержит "магическое" число EF53h. Его волшебство заключается в том, что оно помогает идентифицировать суперблок, ведь его резервная копия находится в каждой группе блоков. Разработчики почему-то решили, что вероятность встречи именно с этой сигнатурой вне суперблока наиболее низка.
2. Группа блоков и ее дескриптор, которому соответствует struct ext3_group_desc. В блоке, следующем сразу за суперблоком, содержится таблица дескрипторов групп, представляющая собой массив указателей на struct ext3_group_desc .Структура содержит следующие нужные нам поля: 2.1. Битовая карта блоков, __u32 bg_block_bitmap. Указатель на блок, содержащий битовую карту блоков группы. Битовая карта представляет собой последовательность нулей и единиц (1 — блок занят, 0 — блок свободен), причем каждый байт этой структуры записан справа налево (меньшие по порядковому номеру блоки содержатся по старшим адресам).
2.2. Таблица инодов, __u32 bg_inode_table. Каждая группа блоков содержит свою таблицу инодов, указатель на которую находится в этом поле. Нумерация инодов начинается с 1. Несколько номеров инодов зарезервировано для специальных целей. Например, инод 2 отведен для корневого каталога ("/").
3. Индексный узел (инод), struct ext3_inode. Помимо такой интересной информации, как временные штампы файлов, содержит следующие поля, которыми мы будем активно оперировать:
3.1. Число блоков, занимаемых файлом, __u32 i_blocks.
3.2. Массив указателей на блоки, __u32 i_block[EXT3_N_BLOCKS]. Размер этого массива определяется следующим образом:
#define EXT3_NDIR_BLOCKS 12
#define EXT3_IND_BLOCK EXT3_NDIR_BLOCKS
#define EXT3_DIND_BLOCK (EXT3_IND_BLOCK + 1)
#define EXT3_TIND_BLOCK (EXT3_DIND_BLOCK + 1)
#define EXT3_N_BLOCKS (EXT3_TIND_BLOCK + 1),
что, как вы уже, наверное, успели подсчитать, является всего-навсего числом 15. Кроме того, так как массив статический, Linux забивает вакантные места в нем нулями. Но ведь нулевой блок тоже существует! Более того, он содержит суперблок, а если раздел загрузочный — еще и главную загрузочную запись (master boot record,MBR). О последствиях записи в этот блок даже думать не хочется. Поэтому в полученном списке блоков нужно сразу же отсечь нули. Здесь следует отметить одну важную деталь. Для указания на блоки Linux использует трехуровневую адресацию. Это означает, что, если файл не умещается в описанном выше массиве указателей, в действие вступают указатели второго уровня, а первые, соответственно, становятся указателями на указатели. Так продолжается до третьего уровня указания включительно. Дотошный читатель может легко подсчитать, файл какой максимальной длины можно таким образом адресовать. Остается лишь один вопрос: что происходит, когда заканчиваются указатели третьего уровня? Но это не входит в тему нашего обсуждения. Мы просто не будем создавать такие большие файлы. Еще одной важной структурой данных, без которой не обойтись, является структура каталога. Я намеренно не включил ее в перечень трех вышеописанных структур, так как само понятие каталога в той или иной форме существует в любой ОС и не является прерогативой UNIX-культуры (хотя кое-где считается, что является ее изобретением). UNIX-культура говорит нам, что все является файлом и различается лишь типом файла. Рассмотрим структуру каталога EXT. Вначале была структура struct ext3_dir_entry, описывавшаяся следующим образом:
struct ext3_dir_entry {
__u32 inode; /*Номер инода*/
__u16 rec_len; /* Длина записи структуры каталога */
__u16 name_len; /* Длина имени */
char name[EXT3_NAME_LEN]; /* Имя файла */ };
Затем разработчики решили, что нецелесообразно отводить под длину имени файла, которое все равно не может быть больше 255 символов, двухбайтовое поле. В результате вместо одного 16-битового поля name_len появились два 8-битовых — name_len и file_type, а новая структура стала называться struct ext3_dir_entry_2. Поле file_type, как ясно из названия, содержит тип файла. Например, его значение, равное 1, соответствует обычному файлу, а 3 — символьному устройству. Имя файла хранится как Паскаль-строка: сначала длина, а затем массив символов. Это не потому, что разработчики сначала учили Паскаль (или Дельфи), а затем Си. Просто Паскаль-строка удобнее и безопаснее нуль-терминированных Си-строк, с которыми так приятно устраивать небольшие переполнения буфера.
Сейчас, наверное, настало время поговорить о нашем инструментарии. Мы будем писать на Си и использовать компилятор gcc (все равно какой версии). Можно также использовать Perl, Pascal (пишущим на Дельфи настоятельно советую Free Pascal). Только одна просьба: не пытайтесь с Си++. Вы просто погубите все дело. Теперь подведем итог и посмотрим, как все это работает. Вся низкоуровневая информация файлов хранится в блоках. Размер блока хранится в суперблоке. Блоки логически объединяются в группы. Таблица дескрипторов групп находится в блоке, следующем за суперблоком. Каждая группа блоков содержит копию суперблока, таблицу инодов, таблицу каталогов. Иноды содержат указатели на блоки данных. Такова общая схема работы EXT. Нам осталось лишь развернуть ее в программный код.
Система, свободная от пользователя
Итак, приступим. Для работы нам понадобятся свежеустановленная Red Hat Linux (версия ядра не имеет значения) и подопытный каталог. Создадим его вручную. Советую создать его в корневом каталоге. Причина кроется не в моей (нашей) лени, а в принципе неопределенности Гейзенберга, который говорит нам, что любое измерение воздействует на измеряемый объект и изменяет его. Поэтому, создавая глубоко вложенные каталоги и длинные файлы в них, мы будем увеличивать ту самую фрагментацию дискового пространства, с которой решили бороться. Этим же объясняется требование свежей ОС. С принципом неопределенности бороться бесполезно, но свести к минимуму его последствия можно. Итак, создадим каталог /experimental, а в нем файл произвольного содержания размером, например, в восемь блоков:
void create_big_file(int fsize)
{
FILE *stream;
int handle;
int i=0;
if((stream=fopen(BIG_FILE,"w+"))==NULL)
{printf("Failed creating big_file");exit(1);}
while(i<fsize)
{ putc((int)'X',stream);
i++;}
}
Нам потребуются две вспомогательные структуры. Первая выглядит следующим образом:
struct directory_parameters
{ __u_quad_t inode;
struct ext3_super_block *superblock;
FILE *file;
} *dir_prs;
и содержит номер инода подопытного файла, указатели на суперблок и на раздел диска (который также является файлом). Указатель на эту структуру будет подаваться на вход функции, выводящей карту дискового пространства под файлом. Вторая представляет собой элемент связанного списка блоков: struct file_block
{ __u32 block;
struct file_block *next;
};
В этом списке мы будем хранить указатели на ненулевые блоки файла. Этим мы в какой-то мере исправим ошибку разработчиков, которые отвели статическое хранилище для структуры данных переменной длины. Кроме этого, мы напишем две процедуры, вычисляющие математические функции "пол (floor)" и "остаток(mod)":
__u_quad_t _floor(__u_quad_t x,__u_quad_t y)
{return x/y-(x%y)/y;}
__u_quad_t _mod(__u_quad_t x,__u_quad_t y)
{return x-y*_floor(x,y);}
Что делают эти функции, пояснять не надо. Для вычисления остатка по модулю можно было воспользоваться оператором "%", но мы делаем это по- своему, и причина этого выяснится по мере изложения. Оговорюсь сразу: здесь приводятся только ключевые фрагменты кода, иначе пришлось бы писать отдельную статью с комментариями. Итак, наша первая функция получает на входе строку с именем подопытного каталога и возвращает указатель на struct directory_parameters:
struct directory_parameters* _get_dir_logical_info(char *name);
Коль мы упомянули, что все в UNIX является файлом, то и откроем наш логический диск как обычный файл:
if((hdd=fopen(DEVICE,"r"))==NULL)
{printf("Failed opening device");exit(1);}
Затем считываем суперблок:
handle=fileno(hdd);
if(lseek(handle,1024,SEEK_SET)==-1)
{fprintf(stderr,"superblock lseek error");exit(1);}
super_buf=malloc(sizeof(struct ext3_super_block));
if (bytes=read(handle,super_buf,sizeof(struct ext3_super_block))==-1)
{fprintf(stderr,"Error reading superblock");exit(1);}
super=(struct ext3_super_block*)super_buf;
Теперь нужно определить группу блоков для каталога "/":
bl_group_for_root=_floor(2,super->s_inodes_per_group);
Инод под номером 2 зарезервирован для "/", а группа блоков для него — это функция "floor", примененная к этому иноду и числу инодов на группу, взятому из суперблока. Теперь нужно просто переместиться к соответствующей записи в таблице дескрипторов групп, памятуя о том, что она начинается в блоке, следующем за суперблоком:
if (lseek(handle,1024<<super->s_log_block_size+
bl_group_for_root*sizeof(struct ext3_group_desc),SEEK_SET)==-1)
{printf("lseek error");exit(1);}
bg_table_entry=malloc(sizeof(struct ext3_group_desc));
itable_buf=malloc(1024<<super->s_log_block_size);
if (bytes=read(handle,bg_table_entry,sizeof(struct ext3_group_desc))==-1)
{fprintf(stderr,"Error reading group block descriptor");exit(1);}
bg_entry=(struct ext3_group_desc*)bg_table_entry;
itable_for_root=bg_entry->bg_inode_table;
Иными словами, мы считали запись из таблицы дескрипторов групп в соответствующую структуру и взяли из нее номер блока, в котором находится таблица инодов для "/". Что ж, идем к этой таблице и берем из нее запись номер 2, также считывая ее в структуру.
if (lseek(handle,(1024<<super->s_log_block_size)*itable_for_root+
sizeof(struct ext3_inode),SEEK_SET)==-1)
{fprintf(stderr,"Fseek for itable failed");exit(1);}
inode_buf=malloc(sizeof(struct ext3_inode));
if (bytes=read(handle,inode_buf,sizeof(struct ext3_inode))==-1)
{fprintf(stderr,"Error reading group block descriptor");exit(1);}
inode=(struct ext3_inode*)inode_buf;
Из этого инода нам всего-то и нужны указатели на блоки данных. Вот здесь и начинается самое интересное. Как мы выяснили, Linux хранит их в статическом массиве, где у большинства файлов находятся длинные цепочки нулей. Поэтому нам нужно еще создать свой динамический массив (block_list), где мы будем хранить указатели на ненулевые блоки. Затем мы считываем полученные блоки в буфер (dir_table_buf), и весь полученный конгломерат преобразуем в таблицу записей каталогов. Ну как, программисты на Си++, у вас еще не посыпались искры из глаз? Это еще только начало.
j=0;
for(i=0;i<sizeof(block_list)/sizeof(__u32);i++)
{
if(lseek(handle,(1024<<super->s_log_block_size)*block_list[i],SEEK_SET)==-1)
{fprintf(stderr,"Fseek failed in block reading");exit(1);}
if (bytes=read(handle,(dir_table_buf+j),1024<<super->s_log_block_size)==-1)
{fprintf(stderr,"Error reading block");exit(1);}
j+=1024<<super->s_log_block_size;
buf_sz=j;
}
В полученной таблице мы находим по имени наш каталог /experimental, берем из него указатель на инод и заполняем полученными данными выходную структуру directory_parameters.
j=0;
while (j+SIZEOF_DIR_ENTRY<buf_sz)
{jtemp=j;
for(i=0;i<SIZEOF_DIR_ENTRY;i++)
{dir_entry_buf[i]=dir_table_buf[j];j++;}
dir_entry=(struct ext3_dir_entry_2*)dir_entry_buf;
if(!strncmp(name,dir_entry->name,(size_t)dir_entry->name_len))
{dir_found=1;
entry=dir_entry->name;
exp_inode=dir_entry->inode;}
j=jtemp+dir_entry->rec_len;}
if(!dir_found)
{ printf("Entry not found\n");exit(1);}
dir_prs=malloc(sizeof (struct directory_parameters));
dir_prs->inode=(__u_quad_t)exp_inode;
dir_prs->superblock=super;
dir_prs->file=hdd;
Теперь осталось проделать то же, что мы делали с "/", с каталогом /experimental, и мы получим на выходе номер инода подопытного файла. Наконец, мы готовы к тому, чтобы построить долгожданную карту файла. Это будет единственная функция, код которой я приведу целиком, чтобы связать воедино все, о чем говорилось до этого.
void build_file_map(struct directory_parameters *param)
{ struct ext3_inode *inode;
struct ext3_dir_entry_2 *dir_entry;
struct ext3_group_desc *gr_desc;
struct file_block *list_start;
struct file_block *list_curr;
unsigned char *inode_buf=malloc(sizeof(struct ext3_inode));
unsigned char *dir_buf=malloc(sizeof(struct ext3_dir_entry_2));
unsigned char *gr_entry=malloc(sizeof(struct ext3_group_desc));
printf("Seeking in inode %Ld\n",param->inode);
__u32 sz_of_block=1024<<param->superblock->s_log_block_size;
int bl_group=_floor(param->inode,param->superblock->s_inodes_per_group);
int block_bitmap[sz_of_block*8];
int *buff;
unsigned char *block_buf=malloc(sz_of_block);
//1
__u_quad_t ino=param->inode%param->superblock->s_inodes_per_group-1;
unsigned char *map_buffer=malloc(sz_of_block);
int bytes,i,j,k,n_zero;
__u32 *t_block_list,*block_list;
int block;
int h=fileno(param->file);
__u_quad_t entry=((1024<<param->superblock->s_log_block_size)+
bl_group*sizeof(struct ext3_group_desc));
__u_quad_t itable;
if(lseek(h,entry,SEEK_SET)==-1)
{fprintf(stderr,"Fseek for rabbit failed");exit(1);}
if (bytes=read(h,gr_entry,sizeof(struct ext3_group_desc))==-1)
{fprintf(stderr,"Error reading group block descriptor");exit(1);}
gr_desc=(struct ext3_group_desc*)gr_entry;
itable=gr_desc->bg_inode_table;
__off64_t seek=sz_of_block*itable+ino*sizeof(struct ext3_inode);
//2
if(fseeko64(param->file,seek,SEEK_SET)<0)
{fprintf(stderr,"BIG seek error in build_map");exit(1);}
i=0;
while(i<sizeof(struct ext3_inode))
{ inode_buf[i]=fgetc(param->file);i++;}
inode=(struct ext3_inode*)inode_buf;
printf("LIST OF BLOCKS OF RABBIT\n");
for(i=0;i<EXT3_N_BLOCKS;i++)
{ printf("%x ",inode->i_block[i]);}
t_block_list=inode->i_block;
i=0; n_zero=0;
list_curr=malloc(sizeof (struct file_block));
list_start=list_curr;
//3
for(i=0;i<EXT3_N_BLOCKS;i++)
{ if(inode->i_block[i])
n_zero++;
printf("%x ",inode->i_block[i]);
list_curr->block=inode->i_block[i];
list_curr->next=malloc(sizeof(struct file_block));
list_curr=list_curr->next;}
block_list=malloc(n_zero*sizeof(__u32));
i=0;j=0;
//4
printf("LIST OF BLOCKS\n");
list_curr=list_start;
while(i<n_zero)
{ printf("%x ",list_curr->block);
i++;
list_curr=list_curr->next;}
close(h);
}
После изложенного код, приведенный выше, не должен вызывать вопросов. Под ником RABBIT скрывается, конечно, подопытный файл. Отметим только ключевые моменты. Соответствующие строки помечены цифрами. В строке 1 мы находим относительный номер инода нашего файла в таблице инодов группы. В строке 2 мы перемещаемся к интересующему нас иноду. Обратите внимание, что здесь используется функция для перемещения по большим файлам fseeko64, работающая с 64-разрядными аргументами (а вдруг Linux поместила блоки нашего файла в самый конец раздела? Тогда мы нормально откомпилируемся, но получим ошибку времени исполнения "Segmentation fault"). В строке 3 мы перемещаемся по массиву блоков и добавляем в наш связанный список ненулевые блоки. И, наконец, в строке 4 мы выводим долгожданный список блоков. И какие же блоки выделила самая свободная ОС в мире для файла, содержащего восемь блоков? Вот их номера в моей системе: 2283,2285,2286,2291,2292,2294,2307,2308. Не очень-то упорядоченно и вполне свободно. А разрыв между шестым и седьмым блоком составляет 13 единиц! Зато теперь мы знаем алгоритм, по которому Linux выделяет дисковое пространство файлам. Этот алгоритм носит название "первого доступного". Меня часто упрекают за излишнюю математизированность моих статей, но здесь я не могу удержаться от подсчета вероятности того, что файл длиной n блоков окажется нефрагментированным при использовании этого алгоритма. Она составляет 1/2n. Нам говорят, что Linux старается выделять блоки для файла в одной группе блоков. Помилуйте, да что это дает? Пускай бы выделяла в разных группах, но в смежных блоках. Ведь в конечном итоге все сводится к времени, затрачиваемому на перемещения головок винчестера.
Заключение
Принимая во внимание полученный результат, я рассматриваю эту статью как антируководство для рекламного агента в области IT (хотя приведенных сведений и кода достаточно, чтобы написать простейший дефрагментатор). Ведь были же, в самом деле, случаи, когда люди покупали дистрибутивы Windows 95, не имея компьютера. Теперь компьютеры есть у всех, а люди по-прежнему покупают дистрибутивы, не вполне представляя, для чего им это нужно. Я просто призываю некоторых людей осторожнее использовать такие слова, как "надежная", "устойчивая", "свободная", "открытая" и т.п. Они содержат количество информации, меньшее, чем, скажем, фраза "лучшие хот-доги только у нас", но при этом оказывают необратимое воздействие на сознание миллионов.
Вадим Шандриков, qnx999@tut.by
Мир Linux можно разделить на несколько больших групп, среди которых наиболее ярко представлены три. Первая — это ортодоксы (фанаты). Они призывают устанавливать их любимую ОС на все, что можно подключить к сети 220 В. Как правило, саму систему они знают весьма поверхностно, но компенсируют этот недостаток своим воинствующим нонконформизмом. Вторая — это, так сказать, патриархи. Свое знакомство с UNIX они начинали еще с PDP-11, в эпоху MS-DOS они писали драйверы, а сейчас развлекаются редактированием исходников ядра системы. Третья — это колеблющиеся. О них стоит поговорить особо. На их компьютерах, как правило, установлены две ОС. Поработав некоторое время в одной, они пытаются сделать то же в другой, надеясь, что получится лучше. Чаще всего не получается. Тогда они решают снести разочаровавшую их систему, но агрессивная реклама ее сторонников в сети и книги из серии "освой за 3 дня" заставляют отложить казнь системы до другого раза и задуматься в стиле: "а вдруг я делаю все неправильно". Время проходит, бесполезная ОС продолжает жить на жестком диске, хотя загружается все реже и реже, а у вчерашнего потенциального ее пользователя развивается комплекс неполноценности. Так система теряет сторонников. А виноваты в этом та самая агрессивная реклама и книги из той же серии. Реклама содержит множество ничем не подтвержденных мифов, ну, а о книгах вообще не хотелось бы упоминать. Я не помню случая, чтобы Microsoft позиционировала свою ОС как самую устойчивую и надежную. Теперь откройте любой учебник формата "Linux для начинающих". Открыли? Где-то там, в самом начале, где описаны преимущества Linux перед другими ОС, и будет искомая фраза о ее непревзойденной надежности. Не беда, что это нигде по тексту книги не обосновано. Пользователь уже перевернул страницу.
Похожая ситуация наблюдается с предметом нашего обсуждения — фрагментацией. Ни один из известных мне дистрибутивов Linux не содержит встроенных средств для дефрагментации дискового пространства, имеющего честь нести на себе эту ОС. Что, может, забыли написать? Да нет же. Откроем любой учебник системного администратора UNIX. Если там описывается файловая система ufs, то наверняка будет фраза о ее врожденной нефрагментируемости. А что же файловые системы ext2fs и ext3fs? Да ведь это прямые наследники ufs, скажут нам ортодоксы. Прямые да не очень, прошу прощения за каламбур. Наша задача — показать это. Мы сделаем это, построив карту дискового пространства, занимаемого файлом, и посмотрим, можно ли ее оптимизировать.
Поколение EXT
Для того, чтобы осуществить задуманное, мы должны пройти весь путь, который проходит драйвер файловой системы, выполняя загрузку требуемого файла в память. Поэтому вначале будет дан некоторый теоретический материал о строении файловых систем, используемых в Linux. Мы будем работать с ext2fs и ext3fs, создаваемыми по умолчанию при установке подавляющего большинства дистрибутивов Linux. Это две файловые системы-близнецы, отличающиеся лишь поддержкой журналирования и слегка видоизмененной процедурой удаления файлов в ext3fs. Перед тем, как излагать структуры данных этих близнецов, определим, что такое фрагментация вообще и ее разновидности. Итак, внешней дисковой фрагментацией будем называть расположение данных в несмежных областях физического дискового пространства. Далее в тексте под термином "фрагментация" мы будем подразумевать именно этот ее вид. В отличие от нее, внутренней дисковой фрагментацией будем считать потерю физического дискового пространства из-за недостаточного заполнения его областей данными. Здесь мы вплотную подошли к такому ключевому понятию любой файловой системы, как блок данных, или кластер. Дадим определение и ему. Блоком данных, или кластером, называется атомарная (минимальная) часть физического дискового пространства, которая может быть выделена файлу. Отсюда становится ясным происхождение внутренней фрагментации. Она возникает, когда размер файла не кратен размеру блока данных (кластера). Тема размера блока данных и внутренней фрагментации требует отдельного обширного обсуждения и здесь затрагиваться не будет. Отметим только, что термин "кластер" применяется для ОС от Microsoft. Мы же, как и принято в мире UNIX, будем оперировать понятием "блок данных" (далее по тексту — просто "блок"). Еще одного разъяснения требуют использующиеся далее термины "раздел (partition)" и "том (volume)". Многие считают, что это одно и то же. Например, если у типичного ортодокса спросить, чем на его домашней системе является /dev/hda1 — томом или разделом — он наверняка ответит: "а какая разница". Поэтому это следует разъяснить. Томом является структура данных ОС, содержащая указатели на множество физических секторов диска. Разделом также является структура данных ОС, содержащая указатели, опять же, на множество физических секторов диска, но при этом обязательно являющихся смежными. Теперь становится ясным соотношение между ними. Раздел является томом (ярый поклонник ООП написал бы что-то вроде "class partition : public volume", или лучше "class partition extends volume"). Далее, употребляя термин "диск", я буду иметь в виду именно раздел. Теперь настала пора описывать структуры данных наших файловых систем. Замечу, что здесь будут описаны основные функциональные возможности этих структур и тот минимум их полей, который необходим для решения нашей задачи. Остальную информацию можно найти в многочисленных HOWTO (да и изучение "голых" заголовочных файлов Linux может при желании (вашем) дать исчерпывающие сведения по большинству вопросов). Например, все описываемые ниже структуры в дистрибутиве Red Hat Enterprise Linux 5 находятся в файле /usr/include/linux/ext3_fs.h. Соответственно, будут приводиться описания полей структур, содержащиеся в этом файле этого дистрибутива. Итак, тремя китами, на которых стоят (чуть не написал "покоятся") файловые системы ext2 и ext3, являются следующие сущности:
1. Суперблок, struct ext3_super_block. Начинается по смещению 1024 байт от начала диска и содержит наиболее общую и важную информацию о файловой системе. В суперблоке нам понадобятся следующие поля:
1.1. Размер блока, __u32 s_log_block_size. Заметим, что он хранится в логарифмической шкале — т.е. содержит число, на которое нужно сдвинуть влево число 1024, чтобы получить искомый размер блока. Неплохо, да? Если учесть, что размер блока редко превышает 4096 байт, что вполне умещается в двухбайтовом слове, непонятно, зачем разработчикам понадобилось так "заворачивать" это простое поле.
1.2. Число блоков на группу, __u32 s_blocks_per_group. О группах блоков весь разговор впереди — пока лишь отметим, что для удобства адресации блоки логически объединяются в группы. Тогда абсолютное смещение блока на диске становится относительным его смещением в группе блоков. 1.3. Число инодов (inodes) на группу, __u32 s_inodes_per_group. Индексный узел (инод) — еще одна структура данных, информация в которой имеет критическое значение для функционирования системы. Достаточно сказать, что она содержит указатели на блоки, выделенные файлу. О ней также весь разговор впереди.
1.4. Сигнатура суперблока, __u16 s_magic. Содержит "магическое" число EF53h. Его волшебство заключается в том, что оно помогает идентифицировать суперблок, ведь его резервная копия находится в каждой группе блоков. Разработчики почему-то решили, что вероятность встречи именно с этой сигнатурой вне суперблока наиболее низка.
2. Группа блоков и ее дескриптор, которому соответствует struct ext3_group_desc. В блоке, следующем сразу за суперблоком, содержится таблица дескрипторов групп, представляющая собой массив указателей на struct ext3_group_desc .Структура содержит следующие нужные нам поля: 2.1. Битовая карта блоков, __u32 bg_block_bitmap. Указатель на блок, содержащий битовую карту блоков группы. Битовая карта представляет собой последовательность нулей и единиц (1 — блок занят, 0 — блок свободен), причем каждый байт этой структуры записан справа налево (меньшие по порядковому номеру блоки содержатся по старшим адресам).
2.2. Таблица инодов, __u32 bg_inode_table. Каждая группа блоков содержит свою таблицу инодов, указатель на которую находится в этом поле. Нумерация инодов начинается с 1. Несколько номеров инодов зарезервировано для специальных целей. Например, инод 2 отведен для корневого каталога ("/").
3. Индексный узел (инод), struct ext3_inode. Помимо такой интересной информации, как временные штампы файлов, содержит следующие поля, которыми мы будем активно оперировать:
3.1. Число блоков, занимаемых файлом, __u32 i_blocks.
3.2. Массив указателей на блоки, __u32 i_block[EXT3_N_BLOCKS]. Размер этого массива определяется следующим образом:
#define EXT3_NDIR_BLOCKS 12
#define EXT3_IND_BLOCK EXT3_NDIR_BLOCKS
#define EXT3_DIND_BLOCK (EXT3_IND_BLOCK + 1)
#define EXT3_TIND_BLOCK (EXT3_DIND_BLOCK + 1)
#define EXT3_N_BLOCKS (EXT3_TIND_BLOCK + 1),
что, как вы уже, наверное, успели подсчитать, является всего-навсего числом 15. Кроме того, так как массив статический, Linux забивает вакантные места в нем нулями. Но ведь нулевой блок тоже существует! Более того, он содержит суперблок, а если раздел загрузочный — еще и главную загрузочную запись (master boot record,MBR). О последствиях записи в этот блок даже думать не хочется. Поэтому в полученном списке блоков нужно сразу же отсечь нули. Здесь следует отметить одну важную деталь. Для указания на блоки Linux использует трехуровневую адресацию. Это означает, что, если файл не умещается в описанном выше массиве указателей, в действие вступают указатели второго уровня, а первые, соответственно, становятся указателями на указатели. Так продолжается до третьего уровня указания включительно. Дотошный читатель может легко подсчитать, файл какой максимальной длины можно таким образом адресовать. Остается лишь один вопрос: что происходит, когда заканчиваются указатели третьего уровня? Но это не входит в тему нашего обсуждения. Мы просто не будем создавать такие большие файлы. Еще одной важной структурой данных, без которой не обойтись, является структура каталога. Я намеренно не включил ее в перечень трех вышеописанных структур, так как само понятие каталога в той или иной форме существует в любой ОС и не является прерогативой UNIX-культуры (хотя кое-где считается, что является ее изобретением). UNIX-культура говорит нам, что все является файлом и различается лишь типом файла. Рассмотрим структуру каталога EXT. Вначале была структура struct ext3_dir_entry, описывавшаяся следующим образом:
struct ext3_dir_entry {
__u32 inode; /*Номер инода*/
__u16 rec_len; /* Длина записи структуры каталога */
__u16 name_len; /* Длина имени */
char name[EXT3_NAME_LEN]; /* Имя файла */ };
Затем разработчики решили, что нецелесообразно отводить под длину имени файла, которое все равно не может быть больше 255 символов, двухбайтовое поле. В результате вместо одного 16-битового поля name_len появились два 8-битовых — name_len и file_type, а новая структура стала называться struct ext3_dir_entry_2. Поле file_type, как ясно из названия, содержит тип файла. Например, его значение, равное 1, соответствует обычному файлу, а 3 — символьному устройству. Имя файла хранится как Паскаль-строка: сначала длина, а затем массив символов. Это не потому, что разработчики сначала учили Паскаль (или Дельфи), а затем Си. Просто Паскаль-строка удобнее и безопаснее нуль-терминированных Си-строк, с которыми так приятно устраивать небольшие переполнения буфера.
Сейчас, наверное, настало время поговорить о нашем инструментарии. Мы будем писать на Си и использовать компилятор gcc (все равно какой версии). Можно также использовать Perl, Pascal (пишущим на Дельфи настоятельно советую Free Pascal). Только одна просьба: не пытайтесь с Си++. Вы просто погубите все дело. Теперь подведем итог и посмотрим, как все это работает. Вся низкоуровневая информация файлов хранится в блоках. Размер блока хранится в суперблоке. Блоки логически объединяются в группы. Таблица дескрипторов групп находится в блоке, следующем за суперблоком. Каждая группа блоков содержит копию суперблока, таблицу инодов, таблицу каталогов. Иноды содержат указатели на блоки данных. Такова общая схема работы EXT. Нам осталось лишь развернуть ее в программный код.
Система, свободная от пользователя
Итак, приступим. Для работы нам понадобятся свежеустановленная Red Hat Linux (версия ядра не имеет значения) и подопытный каталог. Создадим его вручную. Советую создать его в корневом каталоге. Причина кроется не в моей (нашей) лени, а в принципе неопределенности Гейзенберга, который говорит нам, что любое измерение воздействует на измеряемый объект и изменяет его. Поэтому, создавая глубоко вложенные каталоги и длинные файлы в них, мы будем увеличивать ту самую фрагментацию дискового пространства, с которой решили бороться. Этим же объясняется требование свежей ОС. С принципом неопределенности бороться бесполезно, но свести к минимуму его последствия можно. Итак, создадим каталог /experimental, а в нем файл произвольного содержания размером, например, в восемь блоков:
void create_big_file(int fsize)
{
FILE *stream;
int handle;
int i=0;
if((stream=fopen(BIG_FILE,"w+"))==NULL)
{printf("Failed creating big_file");exit(1);}
while(i<fsize)
{ putc((int)'X',stream);
i++;}
}
Нам потребуются две вспомогательные структуры. Первая выглядит следующим образом:
struct directory_parameters
{ __u_quad_t inode;
struct ext3_super_block *superblock;
FILE *file;
} *dir_prs;
и содержит номер инода подопытного файла, указатели на суперблок и на раздел диска (который также является файлом). Указатель на эту структуру будет подаваться на вход функции, выводящей карту дискового пространства под файлом. Вторая представляет собой элемент связанного списка блоков: struct file_block
{ __u32 block;
struct file_block *next;
};
В этом списке мы будем хранить указатели на ненулевые блоки файла. Этим мы в какой-то мере исправим ошибку разработчиков, которые отвели статическое хранилище для структуры данных переменной длины. Кроме этого, мы напишем две процедуры, вычисляющие математические функции "пол (floor)" и "остаток(mod)":
__u_quad_t _floor(__u_quad_t x,__u_quad_t y)
{return x/y-(x%y)/y;}
__u_quad_t _mod(__u_quad_t x,__u_quad_t y)
{return x-y*_floor(x,y);}
Что делают эти функции, пояснять не надо. Для вычисления остатка по модулю можно было воспользоваться оператором "%", но мы делаем это по- своему, и причина этого выяснится по мере изложения. Оговорюсь сразу: здесь приводятся только ключевые фрагменты кода, иначе пришлось бы писать отдельную статью с комментариями. Итак, наша первая функция получает на входе строку с именем подопытного каталога и возвращает указатель на struct directory_parameters:
struct directory_parameters* _get_dir_logical_info(char *name);
Коль мы упомянули, что все в UNIX является файлом, то и откроем наш логический диск как обычный файл:
if((hdd=fopen(DEVICE,"r"))==NULL)
{printf("Failed opening device");exit(1);}
Затем считываем суперблок:
handle=fileno(hdd);
if(lseek(handle,1024,SEEK_SET)==-1)
{fprintf(stderr,"superblock lseek error");exit(1);}
super_buf=malloc(sizeof(struct ext3_super_block));
if (bytes=read(handle,super_buf,sizeof(struct ext3_super_block))==-1)
{fprintf(stderr,"Error reading superblock");exit(1);}
super=(struct ext3_super_block*)super_buf;
Теперь нужно определить группу блоков для каталога "/":
bl_group_for_root=_floor(2,super->s_inodes_per_group);
Инод под номером 2 зарезервирован для "/", а группа блоков для него — это функция "floor", примененная к этому иноду и числу инодов на группу, взятому из суперблока. Теперь нужно просто переместиться к соответствующей записи в таблице дескрипторов групп, памятуя о том, что она начинается в блоке, следующем за суперблоком:
if (lseek(handle,1024<<super->s_log_block_size+
bl_group_for_root*sizeof(struct ext3_group_desc),SEEK_SET)==-1)
{printf("lseek error");exit(1);}
bg_table_entry=malloc(sizeof(struct ext3_group_desc));
itable_buf=malloc(1024<<super->s_log_block_size);
if (bytes=read(handle,bg_table_entry,sizeof(struct ext3_group_desc))==-1)
{fprintf(stderr,"Error reading group block descriptor");exit(1);}
bg_entry=(struct ext3_group_desc*)bg_table_entry;
itable_for_root=bg_entry->bg_inode_table;
Иными словами, мы считали запись из таблицы дескрипторов групп в соответствующую структуру и взяли из нее номер блока, в котором находится таблица инодов для "/". Что ж, идем к этой таблице и берем из нее запись номер 2, также считывая ее в структуру.
if (lseek(handle,(1024<<super->s_log_block_size)*itable_for_root+
sizeof(struct ext3_inode),SEEK_SET)==-1)
{fprintf(stderr,"Fseek for itable failed");exit(1);}
inode_buf=malloc(sizeof(struct ext3_inode));
if (bytes=read(handle,inode_buf,sizeof(struct ext3_inode))==-1)
{fprintf(stderr,"Error reading group block descriptor");exit(1);}
inode=(struct ext3_inode*)inode_buf;
Из этого инода нам всего-то и нужны указатели на блоки данных. Вот здесь и начинается самое интересное. Как мы выяснили, Linux хранит их в статическом массиве, где у большинства файлов находятся длинные цепочки нулей. Поэтому нам нужно еще создать свой динамический массив (block_list), где мы будем хранить указатели на ненулевые блоки. Затем мы считываем полученные блоки в буфер (dir_table_buf), и весь полученный конгломерат преобразуем в таблицу записей каталогов. Ну как, программисты на Си++, у вас еще не посыпались искры из глаз? Это еще только начало.
j=0;
for(i=0;i<sizeof(block_list)/sizeof(__u32);i++)
{
if(lseek(handle,(1024<<super->s_log_block_size)*block_list[i],SEEK_SET)==-1)
{fprintf(stderr,"Fseek failed in block reading");exit(1);}
if (bytes=read(handle,(dir_table_buf+j),1024<<super->s_log_block_size)==-1)
{fprintf(stderr,"Error reading block");exit(1);}
j+=1024<<super->s_log_block_size;
buf_sz=j;
}
В полученной таблице мы находим по имени наш каталог /experimental, берем из него указатель на инод и заполняем полученными данными выходную структуру directory_parameters.
j=0;
while (j+SIZEOF_DIR_ENTRY<buf_sz)
{jtemp=j;
for(i=0;i<SIZEOF_DIR_ENTRY;i++)
{dir_entry_buf[i]=dir_table_buf[j];j++;}
dir_entry=(struct ext3_dir_entry_2*)dir_entry_buf;
if(!strncmp(name,dir_entry->name,(size_t)dir_entry->name_len))
{dir_found=1;
entry=dir_entry->name;
exp_inode=dir_entry->inode;}
j=jtemp+dir_entry->rec_len;}
if(!dir_found)
{ printf("Entry not found\n");exit(1);}
dir_prs=malloc(sizeof (struct directory_parameters));
dir_prs->inode=(__u_quad_t)exp_inode;
dir_prs->superblock=super;
dir_prs->file=hdd;
Теперь осталось проделать то же, что мы делали с "/", с каталогом /experimental, и мы получим на выходе номер инода подопытного файла. Наконец, мы готовы к тому, чтобы построить долгожданную карту файла. Это будет единственная функция, код которой я приведу целиком, чтобы связать воедино все, о чем говорилось до этого.
void build_file_map(struct directory_parameters *param)
{ struct ext3_inode *inode;
struct ext3_dir_entry_2 *dir_entry;
struct ext3_group_desc *gr_desc;
struct file_block *list_start;
struct file_block *list_curr;
unsigned char *inode_buf=malloc(sizeof(struct ext3_inode));
unsigned char *dir_buf=malloc(sizeof(struct ext3_dir_entry_2));
unsigned char *gr_entry=malloc(sizeof(struct ext3_group_desc));
printf("Seeking in inode %Ld\n",param->inode);
__u32 sz_of_block=1024<<param->superblock->s_log_block_size;
int bl_group=_floor(param->inode,param->superblock->s_inodes_per_group);
int block_bitmap[sz_of_block*8];
int *buff;
unsigned char *block_buf=malloc(sz_of_block);
//1
__u_quad_t ino=param->inode%param->superblock->s_inodes_per_group-1;
unsigned char *map_buffer=malloc(sz_of_block);
int bytes,i,j,k,n_zero;
__u32 *t_block_list,*block_list;
int block;
int h=fileno(param->file);
__u_quad_t entry=((1024<<param->superblock->s_log_block_size)+
bl_group*sizeof(struct ext3_group_desc));
__u_quad_t itable;
if(lseek(h,entry,SEEK_SET)==-1)
{fprintf(stderr,"Fseek for rabbit failed");exit(1);}
if (bytes=read(h,gr_entry,sizeof(struct ext3_group_desc))==-1)
{fprintf(stderr,"Error reading group block descriptor");exit(1);}
gr_desc=(struct ext3_group_desc*)gr_entry;
itable=gr_desc->bg_inode_table;
__off64_t seek=sz_of_block*itable+ino*sizeof(struct ext3_inode);
//2
if(fseeko64(param->file,seek,SEEK_SET)<0)
{fprintf(stderr,"BIG seek error in build_map");exit(1);}
i=0;
while(i<sizeof(struct ext3_inode))
{ inode_buf[i]=fgetc(param->file);i++;}
inode=(struct ext3_inode*)inode_buf;
printf("LIST OF BLOCKS OF RABBIT\n");
for(i=0;i<EXT3_N_BLOCKS;i++)
{ printf("%x ",inode->i_block[i]);}
t_block_list=inode->i_block;
i=0; n_zero=0;
list_curr=malloc(sizeof (struct file_block));
list_start=list_curr;
//3
for(i=0;i<EXT3_N_BLOCKS;i++)
{ if(inode->i_block[i])
n_zero++;
printf("%x ",inode->i_block[i]);
list_curr->block=inode->i_block[i];
list_curr->next=malloc(sizeof(struct file_block));
list_curr=list_curr->next;}
block_list=malloc(n_zero*sizeof(__u32));
i=0;j=0;
//4
printf("LIST OF BLOCKS\n");
list_curr=list_start;
while(i<n_zero)
{ printf("%x ",list_curr->block);
i++;
list_curr=list_curr->next;}
close(h);
}
После изложенного код, приведенный выше, не должен вызывать вопросов. Под ником RABBIT скрывается, конечно, подопытный файл. Отметим только ключевые моменты. Соответствующие строки помечены цифрами. В строке 1 мы находим относительный номер инода нашего файла в таблице инодов группы. В строке 2 мы перемещаемся к интересующему нас иноду. Обратите внимание, что здесь используется функция для перемещения по большим файлам fseeko64, работающая с 64-разрядными аргументами (а вдруг Linux поместила блоки нашего файла в самый конец раздела? Тогда мы нормально откомпилируемся, но получим ошибку времени исполнения "Segmentation fault"). В строке 3 мы перемещаемся по массиву блоков и добавляем в наш связанный список ненулевые блоки. И, наконец, в строке 4 мы выводим долгожданный список блоков. И какие же блоки выделила самая свободная ОС в мире для файла, содержащего восемь блоков? Вот их номера в моей системе: 2283,2285,2286,2291,2292,2294,2307,2308. Не очень-то упорядоченно и вполне свободно. А разрыв между шестым и седьмым блоком составляет 13 единиц! Зато теперь мы знаем алгоритм, по которому Linux выделяет дисковое пространство файлам. Этот алгоритм носит название "первого доступного". Меня часто упрекают за излишнюю математизированность моих статей, но здесь я не могу удержаться от подсчета вероятности того, что файл длиной n блоков окажется нефрагментированным при использовании этого алгоритма. Она составляет 1/2n. Нам говорят, что Linux старается выделять блоки для файла в одной группе блоков. Помилуйте, да что это дает? Пускай бы выделяла в разных группах, но в смежных блоках. Ведь в конечном итоге все сводится к времени, затрачиваемому на перемещения головок винчестера.
Заключение
Принимая во внимание полученный результат, я рассматриваю эту статью как антируководство для рекламного агента в области IT (хотя приведенных сведений и кода достаточно, чтобы написать простейший дефрагментатор). Ведь были же, в самом деле, случаи, когда люди покупали дистрибутивы Windows 95, не имея компьютера. Теперь компьютеры есть у всех, а люди по-прежнему покупают дистрибутивы, не вполне представляя, для чего им это нужно. Я просто призываю некоторых людей осторожнее использовать такие слова, как "надежная", "устойчивая", "свободная", "открытая" и т.п. Они содержат количество информации, меньшее, чем, скажем, фраза "лучшие хот-доги только у нас", но при этом оказывают необратимое воздействие на сознание миллионов.
Вадим Шандриков, qnx999@tut.by
Компьютерная газета. Статья была опубликована в номере 15 за 2008 год в рубрике ос
