HPFS
Материал из Википедии — свободной энциклопедии
HPFS — High Perfomance File System, файловая система разработанная специалистами Microsoft и IBM на основе опыта IBM по созданию файловых систем MVS, VM/CMS и виртуального метода доступа. Со стороны Microsoft проектом руководил опытный системный программист Gordon Letwin.
Впервые поддержка HPFS появилась в операционной системе OS/2 версии 1.2. С тех пор штатная поддержка HPFS присутствует во всех версиях OS/2. В Windows NT поддержка HPFS существовала до версии 3.51 включительно (хотя есть успешные прецеденты использования старого драйвера HPFS в Windows NT 4.0 и даже Windows 2000). Впоследствии Microsoft отказалась от HPFS в пользу своей новой файловой системы NTFS, при разработке которой был учтён опыт создания HPFS.
В OS/2 существует серверный вариант драйвера для HPFS, называемый HPFS386, который обладает некоторыми дополнительными возможностями.
[править] Структура HPFS
Диск в HPFS делится на сектора фиксированного размера (512 байт в текущей реализации, при этом номер сектора или их количество кодируются во внутренних структурах как 4-байтовое беззнаковое целое, что позволяет адресовать диски размером до (232 — 1) * 512 = 2 терабайта).
В начале диска расположены несколько управляющих блоков:
- Загрузочный сектор DOS-овского вида.
- SuperBlock содержит информацию о геометрии диска, указатели на битмапы свободного пространства, указатель на корневой каталог, размер дисковой полосы, номер полосы с каталогами, указатель на список сбойных блоков и т. п. SuperBlock также содержит дату последнего запуска CHKDSK. Обычно изменяют SuperBlock только программы CHKDSK и FORMAT.
- SpareBlock содержит указатели на пул HOTFIX-areas, пул Fault-Tolerance областей (только HPFS386 использует Fault-Tolerance), пул блоков для операций на почти переполненном диске и другие указатели, флаги и дескрипторы.
- Область начальной загрузки.
- Область секторов используемых (временно) для выполнения операций требующих дополнительную дисковую память. Эта область например, иногда задействуется при переименовании файла на заполненном диске.
- Другие области.
Для определения свободен сектор или занят HPFS использует битмапы, в которых каждый бит соответствует одному сектору. Если бит содержит 1 то это означает что сектор занят, иначе он свободен. Если бы на весь диск был бы только один битмап, то для его подкачки приходилось бы перемещать головки чтения/записи в среднем через половину диска. Чтобы избежать этого, HPFS разбивает диск на «полосы» (bands) длиной по 8 мегабайт и хранит битмапы свободных секторов в начале или конце каждой полосы. При этом битмапы соседних полос располагаются рядом:
±-------- 16MB --------+ *** — Use/Free sector bitmap. | | ±-|-----------±----------|--±-------------±-------------+ |*** Полоса 0 | Полоса 1 ***|*** Полоса 2 | Полоса 3 ***| ±-------------±-------------±-------------±-------------+ 0MB 8MB 16MB 24MB 32MB
Расстояние между двумя битмапами равно 16MB. Размер полосы (8MB) может быть изменён в следующих версиях HPFS, так как на него нет прямых завязок. HPFS определяет размер полосы при чтении управляющих блоков с диска во время выполнения операции FSHelperAttach.
Размер битмапа равен 2K (8MB/512/8 = 2K).
Полоса находящаяся в центре диска используется для хранения каталогов. Эта полоса называется Directory Band. Однако, если она будет полностью заполнена, HPFS начнёт располагать каталоги файлов в других полосах.
Файлы и каталоги в HPFS базируются на фундаментальном объекте называемом FNode. Каждая FNode занимает один сектор и всегда располагается в HPFS поблизости от своего файла или каталога (обычно непосредственно перед файлом или каталогом). FNode содержит длину и первые 15 символов имени файла, статистику по доступу к файлу, внутреннюю информацию, расширенные атрибуты и ACL (или только часть, если они очень большие), ассоциативную информацию о расположении и подчинении файла и т. д.
Имена файлов и каталогов при полной подстановке (от корня) не должны превышать 260 символов, при этом каждая компонента пути не должна быть длиннее 255 символов. В именах файлов недопустимы символы: 0h-31h, 7Fh, "/", "|", "\", "*", "?", '"', "<", ">". Последовательности конечных пробелов игнорируются, если на конце файла стоит точка, то она тоже игнорируется (для программной совместимости). Внутри имени файла точка — такой же символ как и остальные. С русскими буквами проблем нет. При создании файла HPFS запоминает написание его имени, хотя и не различает регистров в дальнейших операциях, кроме тех, что возвращают информацию о файле.
Примеры имен:
- "FILE.ASM"
- "Злобный Файл.ASM.OBJ.EXE"
- "Ещё более злобный файл . TXT"
С точки зрения размещения файлы, каталоги и их расширенные атрибуты (если они не помещаются в FNode) рассматриваются HPFS как наборы экстентов. Экстент — это кусок файла лежащий в последовательных секторах. Каждый экстент описывается двумя числами: номером первого сектора и длиной (в секторах). Два последовательных экстента всегда объединяются HPFS в один. Минимальный размер экстента — один сектор. Так как расстояние между соседними битмапами свободных секторов равно 16MB, то и размер максимального экстента равен 16MB. Если файл состоит из восьми или менее экстентов, то его описание целиком хранится в FNode.
Если файл состоит более чем из восьми экстентов, то его описание может занимать несколько секторов расположенных поближе к файлу, при этом эти сектора содержат не список, а прошитое сбалансированное дерево экстентов (B±Tree). Дерево построено так, что его разбалансировка никогда не превышает 1/3 по объёму, и оно не отличается от оптимального более чем на один уровень. Корень дерева находится в FNode, причём может содержать до 12 элементов. Каждый дополнительный сектор представляющий собой ветку дерева содержит до 60 элементов, а лист — 40 элементов. Таким образом, если файл состоит из экстентов по одному сектору (этого никогда не будет!) и имеет размер 2GB, для его описания потребуется дерево следующей структуры: 12*60*60*60*40=53MB листьев и 1.7MB веток. Для случайном доступа к любой части файла при этом потребуется (в худшем случае) 5 операций чтения управляющих структур.
Реальные файлы состоят из 1-3 экстентов.
Максимальный размер файла в HPFS сейчас 2GB, однако он обусловлен только размером поля под размер файла и файловый указатель (4 байта) в самой OS/2 и её API. Это не предел HPFS. Следует помнить, что в HPFS отсутствует понятие кластера, файл может занимать 1, 2, 3, 4 или любое другое количество секторов.
При создании/расширении файлов HPFS пытается минимизировать количество экстентов, используя для этого статистику, битмапы свободных секторов и другую информацию. Например, HPFS старается условно резервировать хотя бы 4 килобайта места в конце файлов, которые растут. Другой прием: расположение конкурентно растущих файлов или файлов открытых разными цепочками или процессами в разных полосах диска.
Каталоги в HPFS как и в FAT образуют древовидную структуру. Но при этом внутри каталога HPFS строит сбалансированное дерево (B*-Tree) на основе имён файлов для быстрого поиска файла по имени внутри каталога. Так, если каталог содержит 4096 файлов, FAT будет читать в среднем 64 сектора для поиска файла внутри каталога, а HPFS считает 2-4 сектора и найдёт файл.
Размер блока в терминах которых выделяются каталоги равен 2KB в текущей версии HPFS. Размер записи описывающей файл зависит от размера имени файла. Если имя занимает 13 байтов (8.3), то 2-килобайтовый блок вмещает 41 описатель файлов. Блоки прошиты списком (как и описатели экстентов) для облегчения последовательного обхода.
HPFS не имеет FAT-овских проблем «утекания» дискового пространства при удалении большого количества файлов в каталоге.
При переименовании файла может возникнуть перебалансировка дерева. Эта операция может потребовать выделения дополнительных блоков на заполненном диске. В этом случае блоки берутся из специального пула, указатель на который лежит в SpareBlock.
Расширенные атрибуты и их разновидность ACL HPFS хранит в FNode. Если они не влезают в FNode HPFS хранит из почти как файл построив для этого B±Tree. Имена расширенных атрибутов до HPFS386 не выстраивались в B-Tree.
[править] Использованная и рекомендуемая литература
Горявский Ю.А. Кое-что об HPFS.
О B*/B±деревьях: Кнут, Д. Искусство программирования.
