Josef Troch (troch@mail.ru)
26.2.2002 (poslední změna 28.2.2002)

HPFS - High Performance File System

Tento filesystém byl vyvinut ve spolupráci IBM s Microsoftem a poprvé se objevil v operačním systému OS/2 verse 1.2 (rok 1989?). Jeho původním účelem bylo nahradit FAT filesystém, který byl zcela nevyhovující pro větší HDD.
HPFS podporuje dlouhá jména souborů (až 254 jedno či dvoubajtových znaků), automatické třídění obsahu adresáře dle jmen souborů/adresářů, přidávání uživatelsky definovaných "extended atributů" k souborům (seznam dvojic (klíč, hodnota) pro každý soubor). Názvy souborů mohou obsahovat velká i malá písmena, ale práce s cestami a jmény souborů je case-insensitive.
IBM HPFS používala jako nativní OS/2 filesystém až do poslední verse, Microsoft ho podporoval ve Windows NT verse 3.x - ve versích 4.0 a novějších již ne (ale pro NT 4.x i Windows 2000 existuje patch, který by měl používání HPFS umožnit - netestováno). Pro Linux existuje read-write driver.

Základní struktura

Alokační jednotkou jsou zde sektory o velikosti 512 B, číslují se od 0.
Sektory 0 - 15 obsahují BootBlock, v sektoru 0 je jméno disku (volume name) a 32bitový identifikátor disku (a asi ještě nějaké nepotřebné informace), sektory 1 - 15 jsou rezervovány pro zavaděč OS (ten může HPFS používat pro čtení souborů OS).
Sektor 16 zabírá SuperBlock (obsahuje pointery na seznam bitmap volného místa na disku, na seznam bad block-ů, na directory block band, na kořenový adresář; datum posledního CHKDSK /F) a sektor 17 SpareBlock (obsahuje různé flagy a pointery, ty podstatnější budou zmíněny později).

Zbytek disku je rozdělen na 8 MB "bands" - každý z nich má svou vlastní bitmapu volného prostoru - 1 bit odpovídá 1 sektoru (0 = used, 1 = free). Tato bitmapa je obvykle uložena na začátku (pro liché) či konci (pro sudé sektory) band-u - takže takto lze získat skoro 16 MB (16MB - 2 x 2kB za bitmapy) souvislého prostoru pro soubor (souvislá alokace se používá, je-li to možné) a bitmapa je zároveň blízko odpovídajících dat.

(Pozn.: Obecně lze mít bitmapy kdekoli - zajistí nám to adresář bitmap, což je několik po sobě jdoucích sektorů, ve kterých jsou pointery na jednotlivé bitmapy. Bitmapy bývaji obvykle umístěny tak, jak je uvedeno výše, ale není to nutné. Pointer na počáteční sektor adresáře bitmap je v superbloku; délka adresáře bitmap se spočítá z velikosti filesystému.)
Jeden band má specielní určení a je uložen poblíž středu disku - directory block band - více později.
(Velikost band-u je vlastnost implementace, mohla by se změnit.)

Soubory a fnode-y

Každý soubor či adresář (včetně kořenového) má přiřazen systémový objekt nazývaný "fnode" - ten je dlouhý 1 sektor a může být alokován kdekoli na disku (ač se je OS/2 snaží držet poblíž dat daného souboru/adresáře).
Fnode obsahuje pointer na nadřazený adresář, délku a prvních 15 znaků jména příslušného souboru / adresáře, informace o extended atributech (jsou-li krátké, jsou tam celé), accesss control lists (něco jako EA, pro přístupová práva) a alokační strukturu.

Alokační struktura ve fnode-u může mít několik forem - dle velikosti a fragmentovanosti dat souboru. Má-li soubor 8 či méně fragmentů, jsou všechny fragmenty ("runs") vypsány ve fnode. Jestliže má soubor fragmentů více, alokační struktura fnode-u se stane kořenem B+ stromu (typ B stromu - hodnoty jen v listech) - tato má prostor pro 12 pointrů na podstromy. Vnitřní uzly B+ stromu mohou mít až 60 synů, každý list může obsahovat až 40 pointrů na fragmenty (ty mohou být jen v listech).
Každý fragment je uložen jako trojice (sektor v souboru, délka, sektor na disku) - vše po 32 bitech. (Tomuto uložení pomocí délky se říká runlenght encoding.) (Toto by rovněž umožňovalo vytvářet "děravé" soubory, ale OS/2 je nepoužívá.)
Pozn.: 3 úrovňový B+ strom může odkazovat až na 12 x 60 x 40 = 28 800 fragmentů.

Adresáře

Pointer na fnode pro kořenový adresář je uložen v SuperBlock-u, ostatní získáme procházením níže uvedené struktury obsahu adresářů.
Fnode adresáře obsahuje pointer na kořenový directory block adresáře (každý directory block je spojitý, 2kB dlouhý a rovněž zarovnaný na 2kB). Filesystém se tyto blocky snaží alokovat v directory block band-u - pro rychlost. Je-li tento zaplněn, mohou být alokovány kdekoliv na disku. (Pozice a délka directory block band-u je v superblocku, stejně i pointer na speciální bitmapu pro tento band (v normální bitmapě se tváří jako full)).

Každý directory block obsahuje 1 či více položek adresáře (directory entries) setříděných dle jména souboru / adresáře. Je-li těchto položek moc (nevejdou se to 1 directory blocku), je tento directory block rozdělen a vzniká zde B-strom (klasický - data i ve vnitřních vrcholech). Za tímto účelem může každá položka obsahovat down pointer na příslušný podstrom (tvořený directory blocky) - ten obsahuje soubory, jejichž jméno je lexikograficky menší než to v nadřazeném directory blocku (prostě B-strom:-) ). Každý directory block musí obsahovat poslední "dummy" položku - obsah je nedefinován, podstatný je jen down pointer.
Vyhledání souboru v adresáři zabere tedy logaritmický čas vzhledem k počtu položek adresáře (jde o klasický průchod B stromem).
(Předpokládáme-li 40 položek na directory block (průměrné filename 13 znaků), 3 úrovňový strom může obsahovat 65640 položek! - 3 přístupy na disk ve srovnání s nejhorší možností u FAT = 4000+.)

Položka adresáře obsahuje všechny potřebné informace o souboru / adresáři (t.j. to, co se v UNIXu vypisuje pomocí "ls - la" - takže při tomto příkazu není třeba seekovat do příslušných fnode-ů) - svou délku, pointer na fnode souboru / adresáře, délku souboru, flagy souboru, délku extended atributů, čas vytvoření, zápisu a čtení, délku jména a jméno souboru / adresáře a případný B-stromový down pointer.
Délka položky závisí na délce jména souboru a je zarovnána na 4 B => počet položek v directory blocku je proměnlivý.

Pozn.: Použití B-stromů pro obsah adresářů může vést ke kaskádě složitějších operací nad B-stromem při operacích se souborem - stačí přejmenování. Přejmenování by mohlo neuspět z důvodu nedostatku místa na disku, ačkoliv se velikost souboru nemění - proto si HPFS udržuje několik volných bloků (Emergency Free Block List) k tomuto účelu v případě nouze - pointer na tyto blocky je ve SpareBlock-u.

Extended atributy

Každý soubor či adresář na HPFS může mít libovolné uživatelsky definované "extended atributy" (dále jen EA) - jedná se o dvojice (klíč, hodnota), kde klíč je ASCII řetězec a hodnota je buď také (0-terminated) ASCII řetězec nebo libovolná sekvence bytů. (OS/2 verse 1.2 má limit 64kB na EA pro 1 soubor / adresář.)
Ukládání EA - je-li jich dostatečně málo, přímo ve fnode-u, jinak jsou ukládány do fragmentů (runs) a odkazovány pomocí B+ stromu.

Souvislá alokace atp.

HPFS v OS/2 se snaží (pro urychlení práce - minimalizace pohybu hlav na disku) souborům přidělovat souvislé bloky sektorů na disku, je-li to možné. Zároveň se snaží udržovat bitmapy volného prostoru a fnode-y blízko příslušných dat.
První strategie je nově vytvořené soubory "rozsypávat" po disku - do různých band-ů, aby se mohly rozrůstat bez fragmentace. Druhá předalokovávat 4kB souvislého prostoru po každé, když je soubor prodloužen (přes hranici sektoru) a po zavření souboru případné přebytečné místo uvolnit.
Pokud aplikace zná velikost vytvářeného souboru předem, může to sdělit file systému při vytváření souboru a ten se pokusí naalokovat soubor v nejmenším možném počtu fragmentů (prochází se bitmapy volného místa - v nejhorším případě všechny).

Kódové stránky (code pages)

Pro správné převody velikosti písmen a porovnávání názvů (souborů / adresářů) obsahuje filesystem informace o kódových stránkách (až 62 ks?) - používá se 437 (USA), 850 (Latin 1), 852 (Latin 2). Spareblock obsahuje pointer na adresář kódových stránek, odkud jsou další pointery na jednotlivé tabulky. Každá položka directory blocku obsahuje index kodové stránky, ve které je jeho jméno - teoreticky lze používat více kódových stránek ve filesystému najednou, prakticky to v OS/2 prý nechodí (nepřístupné soubory, pády systému atp.).

Další vylepšení HPFS či jeho implementace v OS/2

Shrnutí - výhody HPFS

Jeden obrázek na závěr

Takto může vypadat část stromových struktur filesystému (samozřejmě, je-li dat či položek adresáře " málo", B a B+ stromy se nepoužijí - viz výše).
E. A. zde značí extended atributy - ty mohou být také uloženy pro každý soubor / adresář v samostatném B+ stromě (je-li jich "moc") či přímo v fnodu (je-li jich málo).
Obrázek možné struktury filesystému HPFS

Zdroje a odkazy:

  1. Duncan Roy: Design goals and implementation of the new High Performance File System. (includes related article on B-Trees and B+ Trees), Microsoft Systems Journal, Sept 1989 v4 n5 p1(13) - tady nebo tady i s obrázky - ale nepřehledně.
  2. Dan Bridges: Série článků o HPFS z OS2Zone - zde.
  3. Mikuláš Patočka: Specifikace filesystému HPFS, 1999 - zde.
  4. Mikuláš Patočka: Virtual File System (VFS), 1999 - zde.
  5. Filesystems HOWTO - zde.
Tento článek smí být používán libovolně, za předpokladu, že nebude modifikován a že takto bude učiněno se zmínkou o autorovi a odkazem na stránku http://jt.sf.cz, odkud by měla být dostupná aktuální verse tohoto článku.
Snažím se, aby informace zde uvedené byly pravdivé a pokud možno přesné, nicméně nenesu žádnou odpovědnost za to, že tomu tak opravdu je, ani za jakékoli škody, které by někomu v důsledku případných špatných či nepřesných informací z tohoto článku mohly vzniknout.

Jakékoliv dotazy či připomínky mi můžete poslat mailem.

Zpět na stránku referátů a jiných výtvorů