Реализация файловой системы. Файловая система NTFS

Управление свободным и занятым дисковым пространством

В системе Windows учет свободных и занятых дисковых блоков ведется при помощи битового вектора (bit map или bit vector), например, 00111100111100011000001, где каждый блок представлен одним битом, принимающим значение 0 или 1, в зависимости от того, занят он или свободен. В файловой системе NTFS битовый массив сам является файлом. Его атрибуты и дисковые адреса хранятся в 6-й записи таблицы MFT.

Реализация директорий

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

Как и любому файлу, каталогу соответствует запись в таблице MFT. Эта запись включает в себя совокупность записей о файлах, входящих в данный каталог и индексирована таким образом, чтобы обеспечить эффективный поиск имени файла. Каждая запись о файле включает в себя его имя, метку времени, размер и ссылку на MFT-запись для данного файла. Все это позволяет поисковым программам быстро получать основную информацию о файле из записи в каталоге без обращения к MFT-записи самого файла. Запись MFT для небольшого каталога, где записи о файлах являются резидентным атрибутом, показана на рис 12.4.

Для больших каталогов совокупность записей о файлах не помещается в MFT-запись каталога. Она является нерезидентным атрибутом и организована в виде B+ дерева, обеспечивающего быстрый поиск имени файла в алфавитном порядке. MFT-запись каталога содержит корень этого дерева, а его ветви размещаются в отдельных блоках диска.

Поиск файла по имени

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

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

Для поиска файлов в каталоге применяются функции FindFirstFile и FindNextFile (см. MSDN).

Прогон программы, осуществляющей поиск файла в каталоге

Приведенная программа выводит список файлов в каталоге с заданным шаблоном поиска. Информация о найденных файлах содержится в структуре WIN32_FIND_DATA, которая является одним из параметров функций FindFirstFile и FindNextFile. Входным параметром функции FindFirstFile служит шаблон поиска, а выходным - дескриптор поиска, который является входным параметром функции FindNextFile и хранит информацию о текущем состоянии поиска (аналог указателя текущей позиции). Для закрытия описателя в данном случае применяется функция FindClose (а не CloseHandle как обычно).

Точки повторного анализа. Монтирование дисков. Образование ссылок

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

Монтирование файловых систем

Операция монтирования файловой системы, хранящейся на разделе диска, обеспечивает ей связь с уже существующей иерархией файловых систем и делает ее файлы доступными для процессов. Техника монтирования описана в предыдущей лекции. Монтирование базовых дисков осуществляется автоматически при первом обращении к диску. Это делает диспетчер монтирования (Mountmgr.sys). Сведения о монтированных дисках имеются в реестре в разделе HKLM\SYSTEM\MountedDevices.

Создание точек монтирования (mount points) - связывание каталога NTFS реализовано с помощью точек повторного анализа. Программы, осуществляющие навигацию по каталогам, должны, обнаружив точку повторного анализа (в данном случае точку монтирования), прибегнуть к помощи кода, направляющего процесс дальнейшей навигацию на новый том. Программы, предоставляющие информацию о суммарном количестве файлов на диске или в каталоге, также должны учитывать наличие точек монтирования.

Точки монтирования в системе можно найти при помощи Win32-функций FindFirstVolumeMountPoint и FindNextVolumeMountPoint.

Создание связей

Связывание файлов - техника, заимствованная из Unix, - образование для файла или каталога нескольких родительских каталогов, см. рис 12.6.

Соединение между директорией и разделяемым файлом называется "связью" или "ссылкой" (link). Дерево файловой системы превращается в циклический граф.

ОС Windows (как и Unix) поддерживает два вида связей - жесткие (hard link) и символические (symbolic link). В случае жесткой связи запись о файле появляется в новом каталоге, а MFT-запись этого файла включает счетчик количества ссылок на данный файл. Удаление файла приводит к уменьшению счетчика на 1, и реальное удаление и освобождение его блоков происходит, когда значение счетчика равно 0.

Символическая линковка - создание нового файла, который содержит путь к связываемому файлу. Обычно в системе создается каталог, который связывается с уже существующим каталогом. Этот метод удобен для "подъема" (уменьшения степени вложенности) каталогов. Удаление символической связи на связываемый файл никак не влияет. Удаление связываемого файла делает символическую связь недействительной.

Жесткие связи создаются вызовом Win32-функции CreateHardLink. Штатной утилиты, поддерживающей жесткие связи, нет, хотя в состав ресурсов Windows для этих целей включена POSIX утилита ln.

Символическую связь (иногда говорят точку соединения, junction) можно образовать при помощи входящей в состав ресурсов Windows утилиты linkd.exe или при помощи свободно распространяемой утилиты junction.exe с сайта http://www.sysinternals.com.

Тот факт, что операции монтирования и связывания могут превратить иерархическое дерево файловой системы в циклический граф, делает работу с ней более сложной. Поскольку теперь к файлу существует несколько путей, программа поиска файла может найти его на диске несколько раз. Простейшее практическое решение данной проблемы - ограничить число директорий при поиске. С этой целью при поиске файлов Windows Explorer останавливает рекурсию по достижении 32-го уровня вложенности или при превышении длины пути в 256 символов. Это зависит от того, какое событие наступит раньше..

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

Образование циклического графа можно проиллюстрировать на примере образования рекурсивной точки монтирования.

Написание, компиляция и прогон программы, определяющей, помечен ли указанный каталог в качестве точки повторного анализа

Создайте пустой каталог и сделайте его точкой монтирования или символической связью. При помощи функции GetFileAttributes установите у данного каталога наличие флага FILE_ATTRIBUTE_REPARSE_POINT.

Совместный доступ к файлу

Пользователи часто нуждаются в разделении файлов и совместном доступе к ним.

Как уже было сказано выше, операция открытия файла имеет следствием создание объекта "открытый файл". Специфика объекта "открытый файл" состоит в том, что он содержит лишь уникальные данные (например, указатель текущей позиции), тогда как собственно файл - совместно используемые данные. Поэтому, если два раза осуществить операцию открытия одного и того же файла, то система создаст два объекта "файл". Данная ситуация проиллюстрирована рис 12.7 для случая одновременного открытия файла потоками разных процессов.

Очевидно, что потоки должны синхронизировать доступ к совместно используемым файлам или каталогам, чтобы получить предсказуемый результат. Между двумя операциями read одного потока другой поток может модифицировать данные, что для многих приложений неприемлемо. ОС Windows предлагает стандартное решение данной проблемы на уровне пользователя - предоставить возможность одному из потоков захватить часть файла между двумя записями для монопольного доступа. Для этого используются Win32-функции LockFile и UnlockFile.

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

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

Производительность файловой системы

Эффективность работы - одна из важнейших задач подсистемы управления файлами.

Кэширование

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

Устройство кэша ОС Windows отличается от традиционного. В традиционной реализации кэш - буфер в оперативной памяти, содержащий ряд блоков диска и расположенный между файловой системой и системой ввода-вывода. Если имеется запрос на чтение (запись) в файл, файловая система вычисляет номер блока в файле и номер соответствующего ему блока диска. Перед чтением/записью блока диска производится проверка на предмет наличия этого блока в кэше. Если блок в кэше имеется, то запрос удовлетворяется из кэша, в противном случае запрошенный блок считывается в кэш с диска.

В ОС Windows кэш работает на более высоком уровне, нежели файловая система (см. рис 12.8).

С помощью техники файлов, отображаемых в память, часть считываемого (записываемого) файла проецируется в 256-килобайтный буфер кэша (см. рис 12.9).

В результате запрос на чтение с текущей позиции может быть непосредственно удовлетворен из кэша. Если же нужных байтов файла в кэше нет, то файловая система вычисляет логический номер блока в файле (LCN), затем логический номер блока на диске (VCN). После этого делается запрос к системе ввода-вывода на чтение этого блока, точнее, проецирование в буфер кэша части файла, содержащей данный блок. Подобная организация позволяет системе поддерживать единый централизованный кэш для всех используемых файловых систем (NTFS, FAT, CDFS, удаленная FS и др.), а файловые системы не обязаны управлять своими кэшами.

Важным свойством кэша является его когерентность. Менеджер кэша следит за соответствием открытых файлов и файлов, отображаемых в память (с помощью функции MapViewOfFile ). Каждый раз, когда процесс считывает файл или отображает его в память, этот запрос удовлетворяется из кэша путем копирования соответствующего блока в адресное пространство процесса. Поэтому, независимо от того, сколько процессов откроют файл или отобразят его в память, реальное отображение в память происходит один раз. В итоге все процессы будут "видеть" одну и ту же версию файла.

Аккуратная реализация кэширования требует решения нескольких проблем.

Во-первых, емкость буфера кэша ограничена. У системного кэша нет собственного рабочего набора - он входит в единый системный рабочий набор. Размером системного рабочего набора управляет менеджер памяти, отвечающий за его расширение или усечение. При этом величина, помеченная как размер системного кэша на панели диспетчера задач, относится к размеру всего системного рабочего набора.

Во-вторых, поскольку кэширование использует механизм отложенной записи (lazy write), при котором модификация буфера не вызывает немедленной записи на диск, серьезной проблемой является "старение" информации в дисковых блоках кэшируемого файла. Несвоевременная синхронизация буфера кэша и диска может привести к очень нежелательным последствиям в случае отказов оборудования или программного обеспечения.

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

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

Кроме того в любой момент можно принудительно сбросить содержимое кэша открытого файла на диск с помощью функции FlushFileBuffers. Напомним, что для отображаемого файла имеется аналогичная функция FlushViewOfFile.

Прогон программы, иллюстрирующей функционирование кэша

#include <windows.h>
#include <stdio.h>

void main(void) {

HANDLE hFile, hHeap;
int iRet = 0;
void *pMem;
long FileSize = 0, FilePos = 0;
DWORD iRead = 0, iWrite = 0;
char * String;

hFile = CreateFile("MYFILE.TXT", GENERIC_READ| GENERIC_WRITE,0,
                    NULL, OPEN_EXISTING,FILE_ATTRIBUTE_NORMAL |0, NULL);
if (hFile == INVALID_HANDLE_VALUE) printf("Could not open file \n");


FileSize = GetFileSize(hFile, NULL);
printf("FileSize = %d\n",FileSize);

hHeap = GetProcessHeap();
pMem = HeapAlloc(hHeap, HEAP_ZERO_MEMORY, FileSize + 2);
String = (char *)pMem;

ReadFile(hFile, pMem, FileSize, iRead, NULL);
printf("Read %d bytes \n", iRead);

for(FilePos = 0; FilePos < FileSize; FilePos++)
String[FilePos] = '1';

SetFilePointer(hFile, 0, NULL, FILE_BEGIN);
getchar();

WriteFile(hFile, pMem, FileSize, iWrite, NULL);
printf("Write %d bytes \n", iWrite);

iRet = FlushFileBuffers(hFile);
 if(iRet == 0) printf("FlushFileBuffer Error\n");
 
HeapFree(hHeap, 0, pMem);
CloseHandle(hFile); 
}

Приведенная программа считывает большой файл (рекомендуемый размер - несколько мегабайт) в буфер памяти. Затем она меняет содержимое буфера и записывает его на диск. При этом программа пытается сбросить содержимое кэша с помощью функции FlushFileBuffers.

За результатами работы программы можно наблюдать с помощью счетчика "сбросов данных" кэша. Счетчик ведет себя в соответствии с рисунком, где максимальный пик появляется вслед за нажатием клавиши "Enter".

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

Оптимальное размещение информации на диске

Кэширование - не единственный способ увеличения производительности системы. Другая важная техника - сокращение количества движений считывающей головки диска за счет разумной стратегии размещения информации. Для этого целесообразно периодически осуществлять дефрагментацию диска (сборку мусора). Дефрагментацию можно выполнить с помощью соответствующей вкладки на административной консоли панели управления.

Hадежность файловой системы

Поскольку разрушение файловой системы зачастую более опасно, чем разрушение компьютера, файловые системы должны разрабатываться с учетом подобной возможности. Сохранность информации может быть обеспечена за счет ее избыточности (резервное копирование, зеркалирование, образование RAID массивов). Файловые системы современных ОС содержат специальные средства для поддержки собственной целостности и непротиворечивости.

Восстанавливаемая файловая система NTFS

Как правило, файловая операция затрагивает сразу несколько объектов файловой системы. Например, запись в файл предполагает выделение ему блоков диска, модификацию MFT-записей о занятом пространстве, файле и каталоге, содержащем файл и т.д. В течение короткого периода времени между этими шагами информация в файловой системе оказывается несогласованной. И, если вследствие непредсказуемого останова системы на диске будут сохранены изменения только для части этих объектов (нарушена атомарность файловой операции), файловая система на диске может быть оставлена в противоречивом состоянии. В современных ОС предусмотрены меры, которые позволяют свести к минимуму ущерб от порчи файловой системы и затем полностью или частично восстановить ее целостность.

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

Одним из средств поддержки целостности является журналирование. Последовательность действий с объектами во время транзакции протоколируется, и, если произошел останов системы, то, имея в наличии протокол, можно осуществить откат системы назад в исходное целостное состояние, в котором она пребывала до начала транзакции.

В журнал заносятся не все изменения, а лишь изменения метаданных (MFT-записей и др.). Изменения в данных пользователя в протокол не заносятся. Если протоколировать изменения пользовательских данных, то этим будет нанесен серьезный ущерб производительности системы, поскольку кэширование потеряет смысл. Затраты на журналирование могут быть частично скомпенсированы за счет увеличения интервала между сбросами кэша на диск.

Для файла-журнала отводится вторая запись таблицы MFT тома NTFS. Для минимизации возможных пагубных последствий сервис файла журнала (log file service, LFS) осуществляет записи в следующей последовательности .

Применяемая схема - это результат компромисса между полной отказоустойчивостью системы и максимальной производительностью файловых операций. Разумеется, в распоряжении пользователя остаются средства организации сквозной записи на диск и принудительного сброса на диск кэша NTFS ( FlushFileBuffer ).

Проверка целостности файловой системы при помощи утилит

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

Решение проблемы плохих блоков

Наличие дефектных блоков на диске - обычное дело. Под "плохими" блоками обычно понимают блоки диска, для которых вычисленная контрольная сумма считываемых данных не совпадает с хранимой контрольной суммой. В NTFS применяется один из способов нейтрализации данной проблемы - конструирование файла, содержащего дефектные блоки. Для этого файла зарезервирована запись 8 в таблице MFT. В результате плохие блоки изымаются из списка свободных блоков и, следовательно, становятся недоступны для приложений.

Фиксация изменений в файловой системе

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

Для решения подобных задач ОС Windows располагает самыми широкими возможностями. Для знакомства с данной техникой рекомендуется изучить работу программных примеров из MSDN (см. раздел MSDN Using File I/O), или особенности применения функции FindFirstChangeNotification.

Поддержка нескольких файловых систем

Подобно многим современным операционным системам ОС Windows поддерживает несколько файловых систем (CDFS, UDF, FAT, NTFS, удаленные FS). Эта возможность заложена в архитектуре системы ввода-вывода. Список зарегистрированных файловых систем можно "увидеть" с помощью утилиты WinObj.

Код, реализующий функциональность каждой файловой подсистемы ОС, входит в состав соответствующего драйвера файловой системы. Запрос прикладной программы на чтение (запись) из файла передается диспетчеру ввода-вывода, который пытается обслужить этот запрос с помощью единого интегрированного кэша (см. рис 12.8).

Если нужная информация в кэше отсутствует, диспетчер ввода-вывода обращается к устройству, содержащему данный файл, подбирая драйвер, соответствующий данному устройству. Драйвер конкретной файловой системы по имени файла и байтовому смещению определяет номер блока на диске и переадресует запрос на обработку этого блока драйверу диска.

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

Заключение

Настоящая лекция описывает отдельные аспекты реализации файловой системы NTFS. Главная функция файловой системы - связь символьного имени с блоками диска - реализована за счет поддержки списка блоков в записи о файле в главной файловой таблице MFT. Для быстрого поиска файла по имени каталог может быть организован в виде B+ дерева. Проблемы монтирования дисков и связывания файлов решаются с помощью точек повторного анализа. Производительность файловой системы обеспечивается менеджером кэша, а также путем оптимального размещения информации на диске. Для восстановления системы после отказа питания ведется журнал файловых операций с метаданными. Поддержка нескольких файловых систем в ОС Windows обеспечивается оригинальной структурой подсистемы ввода-вывода, в рамках которой для каждой файловой системы имеется соответствующий драйвер.