File Allocation Table

z Wikipédie, slobodnej encyklopédie

File Allocation Table, skrátene FAT, je čiastočne patentovaný súborový systém, ktorý sa používal v systéme MS-DOS (a kompatibilných systémoch) a v prvých 16/32-bitových verziách operačného systému Microsoft Windows. Existuje niekoľko verzií systému FAT, napríklad FAT12, FAT16 a FAT32. Systém FAT32 sa používal od Windows 95 OSR2 až po Windows ME. Súborový systém FAT je relatívne jednoduchý a je podporovaný všetkými operačnými systémami pre PC. Táto vlastnosť ho činí vhodným pre použitie na disketách, flash diskoch a pamäťových kartách, ako schodnú cestu na prenášanie dát medzi rôznymi operačnými systémami.

FAT je tabuľka obsahujúca informácie o obsadení disku v súborovom systéme vytvorenom pre DOS. Zároveň sa tak označuje zmienený súborový systém. Používa sa pre nájdenie súboru (allocation), ktorý je zapísaný na disku.

Súborový systém FAT bol vytvorený Billom Gatesom a Marcom McDonaldom v roku 1977. V auguste 1980 Tim Paterson začlenil FAT do operačného systému 86-DOS. Prvá verzia FAT bola nazvaná FAT 12. Mala množstvo obmedzení: adresy klasterov boli 12 bitové (to obmedzovalo počet klasterov na 4096) a počet sektorov disku bol daný ako 16 bitové číslo, čo obmedzovalo veľkosť diskového oddielu na 16 MB (pri 4 kB klastroch) resp. 32 MB (pri 8 kB klastroch).

Zoznam použitých skratiek[upraviť | upraviť zdroj]

FAT – File Allocation Table
BS – boot sector
CLI – Clear interrupt flag
OEM – Original Equipment Manufacture
DBCS – Double Byte Character Set
OS – operačný systém (Operating System)

Štruktúra pevného disku[upraviť | upraviť zdroj]

Pevný disk sa skladá z niekoľkých platní, každá z platní má dva povrchy. Tieto povrchy sú číslované od 0. Na každom povrchu sú stopy (taktiež číslované od 0) a sektory (číslované od 1). Stopa je sústredná kružnica a sektor kruhový výsek tejto kružnice. Prienikom jednej stopy a jedného sektoru vznikne oblasť, na ktorú sa dá zapísať obvykle 1/2 KB (teda 512 B).

Na pevnom disku sa používajú súborové systémy FAT16 nebo FAT32, pre diskety sa dá použiť FAT12. Prienikom jednej stopy a jedného alebo viacerých sektorov vznikne tzv. alokovatelná jednotka alebo tiež klaster (cluster). U FAT16 to sú dva sektory, do jedného klastera môžeme zapísať 2*512 = 1024 B, u FAT32 štyri sektory (dá sa vybrať pri prevode na FAT32), môžeme tu zapísať napr. 4*512 = 2048 B.

Pokiaľ chceme uložiť nejaký súbor, operačný systém vezme prvý voľný klaster, ak tento kapacitne nestačí, pridá ďalší voľný ktorý nájde, pričom hľadá od začiatku disku.

Dôsledkom je:

  • dochádza k fragmentácii priestoru na disku (ďalší voľný klaster sa nenachádza za použitým pre predchádzajúcu časť súboru)
  • ak je súbor kratší ako jeden klaster (stačí jeden bajt), je vždy zabraný celý klaster (2 alebo 4 KB)

Boot sektor[upraviť | upraviť zdroj]

BIOS po POSTe (POST = Power on self test) načíta nultý LBA sektor jednotky na adresu 0x0000:0x7C00 a prenesie sem kontrolu (inštrukcia JMP 0x0:0x7C000). Nultý LBA sektor pevného disku a napr. diskety sa odlišuje tým, že na pevnom disku sú zaznamenané oddiely a je zvyčajne naprogramovaný tak aby načítal a spustil boot sektor aktívnej oblasti disku. Tento typ zápisu sa nazýva Master Boot Record (MBR). Ten na diskete je rovnaký ako boot sektor oddielu disku a nazýva sa Volume Boot Record.

Štruktúra Volume Boot Record[upraviť | upraviť zdroj]

adresa (hex) obsah poznámka
00h-002h inštrukcie obsahuje inštrukcie NOP/CLI JMP 03Eh na preskočenie tabuľky (offset 03Eh sa môže líšiť od toho kde je začiatok kódu)
003h-00Ah OEM ID Nachádza sa tu 8 znakov dlhý textový reťazec, ktorý identifikuje operačný systém. Prázdne miesto je vyplnene medzerami (ASCII 32, 20h) napr. MSWIN4.1 značí DOS 7 (Windows 9x)
00Bh-00Ch počet bytov na sektor skoro vždy 512
00Dh počet sektorov na cluster
00Eh-00Fh Počet rezervovaných sektorov
010h počet FAT (File allocation table) Tu je zapísaná štruktúra rozloženia súborov na disku. FAT 12 a FAT 16 podporujú 2 FAT tabuľky – hlavnú FAT a záložnú FAT. Záložná FAT je úplnou kópiou hlavnej FAT. Používa sa len pri rekonštrukcii poškodenej hlavnej FAT
011h-012h počet zápisov koreňového adresára (Number of Root Entries) Toto číslo udáva počet adresárových zápisov (Directory Entry) – max. toľko súborov môže byť v koreňovom adresári.
013h-014h Celkový počet LBA sektorov jednotky
015h popisovač média byte, ktorý určuje typ média podľa BIOSu
016h-017h počet sektorov na FAT veľkosť FAT v sektoroch ⇒ miesto na disku ktoré zaberá FAT
018h-019h počet sektorov na stopu/cylinder
01Ah-01Bh počet hláv
01Ch-01Fh počet skrytých sektorov
020h-023h celkový 'veľký' počet LBA sektorov Pokiaľ je „celkový počet sektorov“ na adrese 013h-014h nulový potom je tento parameter správny. Tento parameter je používaný len pri pevných diskoch. Pri diskete sa nepoužíva, pretože počet sektorov neprekročí 3000 (2880 sektorov je na diskete 3.5")
024h číslo jednotky číslo jednotky podľa BIOSu
025h rezervované
026h extended boot signature = 029h Indikuje, či je informácia správna
027h-02Ah sériové číslo disku
02Bh-035h menovka disku 11 znakov dlhý textový reťazec. Prázdne miesto je vyplnené medzerami (ASCII kód 32, 20h)
036h-03Dh identifikátor súborového systému môže byť „FAT12“, „FAT16“, „FAT32“
03Eh-1FDh bootstrap program tu môže byť hlavný strojový kód zavádzača
1FEh-1FFh Bootsignature = AA55h alebo db 55h, AAh Táto značka je používaná, pokiaľ pMaster BootStrapRecord rozdeleného harddisku zisťuje či je BootStrapRecord vybraného oddielu správny. Ak nie je tak BIOS / Bootloader nespusí kód.

Štruktúra súborového systému FAT[upraviť | upraviť zdroj]

Súborový systém v MS DOSe a jemu podobných systémoch je organizovaný pomocou FAT. Rozoznávame FAT12 a FAT16 (FAT32) podľa toho, koľko bitov vyhradzuje na (logickú) adresáciu disku. FAT je jednorozmerná tabuľka (pole), ktorá obsahuje údaje o obsadenosti jednotlivých oblastí (cluster=klaster) disku/diskety. Väčšinou existujú dve kópie (ak by sa jedna (prvá) fyzicky porušila). FAT spolu s adresármi určuje fyzické uloženie súborov.

Disketa aj disk sú delené na klastre, ktoré sú z hľadiska súborového systému MS DOSu najmenšou adresovateľnou jednotkou (sú to vlastne logické bloky). Priestor na diskete sa súborom prideľuje po klasteroch. Ak napr. klaster pozostáva z 8 sektorov, t. j. má 4KB, a v adresári je 100 súborov po 100B, vznikne 10KB údajov, ale v súborovom systéme zaberajú 100x4KB=400KB miesta, t. j. využívate priestor na 2,5%. Nanešťastie počet klasterov je zhora ohraničený typom FAT: 4096 pre FAT12 (reálne o niečo menej), 65536 pre FAT16 (reálne zase o niečo menej). To je najväčší problém súborového systému typu FAT hlavne pri veľkých diskoch – vynucuje veľké klastre a tým plýtva priestorom.

Štruktúra boot sektoru[upraviť | upraviť zdroj]

Prvá dátová štruktúra na zväzku FAT sa nazýva BPB (Bios Parameter Block). Je umiestená v prvom sektore zväzku v „rezervovanej oblasti“ (tento sektor sa tiež nazýva „boot sektor“, „reserved sektor“ alebo „nultý sektor“). Ide o prvý sektor zväzku.

Časti BPB[upraviť | upraviť zdroj]

Oblasť Začiatok (offset) Veľkosť Popis
Bytes Per Sector 11 2 Fyzická veľkosť sektoru v bytoch, zvyčajne 512
Sectors Per Cluster 13 1 Počet sektorov v jednom logickom klasteri. Počer klasterov vo FAT je obmedzený, preto veľkosť klasterov závisí na veľkosti disku. Väčší disk znamená viac sektorov na klaster.
Reserved Sectors 14 2 Počet sektorov partície pred FAT tabuľkou, vrátane boot sektora. Vždy má hodnotu aspoň 1.
FATs 16 1 Počet tabuliek FAT (typicky 2)
Root Entries 17 2 Počet položiek mien rootovského adresára
Small Sectors 19 2 Počet sektorov disku ak je menší ako 65535, inak 0
Media Descriptor 21 1 Informácia o type média
Sectors Per FAT 22 2 Počet sektorov tabuľky FAT
Sectors Per Track 24 2 Počet sektorov na stopu
Heads 26 2 Počet hláv. Počet sektorov a hláv určuje geometriu disku
Hidden Sectors 28 4 Počet sektorov fyzického disku pred danou partíciou
Large Sectors 32 4 Počet sektorov, ak je oblasť Small Sector, potom 0

Štruktúra FAT tabuľky[upraviť | upraviť zdroj]

FAT je najdôležitejšia popisná tabuľka média. Definuje, ktoré sektory sú voľné, ktoré sú použité, pre ktorý súbor, v akom poradí idú sektory súboru za sebou, definuje rezervované sektory, sú v nej zakódované aj všetky dĺžky súborov. Najdôležitejšia informácia je informácia o tom, ako za sebou idú sektory jednotlivých súborov.

Na médiu môže byť jedna alebo dve FAT. V prípade, že na médiu je len jedna FAT, logické číslo prvého sektora druhej FAT je nulové a tak isto je nulový aj bit 6 v identifikačnom bajte média (offset #20). Každá FAT je umiestnená na médiu kvôli efektívnemu prístupu v sektoroch ktoré idú bezprostredne za sebou od prvého sektora, ktorého číslo je definované v boot sektore. Tento prístup umožňuje mať FAT umiestnenú kdekoľvek na médiu (hoci aj kvôli efektívnemu seekovaniu v strede média) ale FAT musí ostať celá pokope, nemôže byť rozptýlená po médiu.

FAT sa skladá z položiek, každá položka zodpovedá jednému sektoru média. Položky zaberajú podľa potreby 16 alebo 32 bitov. Podľa toho potom rozlišujeme či ide o systém FAT16 alebo FAT32. Bajty sú v položke usporiadané vždy od najnižšieho po najvyšší. FAT32 sa používa, ak počet sektorov na médiu je väčší než umožňuje adresovať FAT16, čo je 2^14 – 256 alebo 16128 sektorov, alebo ak veľkosť sektora (klastera) je väčšia ako 2^14 alebo 16384 bajtov.

Posledný sektor súboru obsahuje po vynulovaní najvyššieho bitu položky presný počet bajtov ktoré ešte súbor zaberá v tomto sektore. Ak je tento počet nulový, potom skutočný počet týchto bajtov je rovný veľkosti sektora, t. j. sektor je využitý celý, čiže dĺžka súboru je deliteľná veľkosťou sektora v bajtoch.

Zmazanie súboru len vynuluje najvyšší bit FAT položky. Všetky položky od 00.00.00.00 do 7F.FF.FF.FF sa chápu ako volné sektory ktoré sa môžu ďalej použiť. Špeciálny sektor je napr. boot, prípadne na bootovateľnom médiu operačný systém, ktorý sa nenachádza v klasickom súbore. Neexistujúci sektor je keď napr. médium má len 250 sektorov, FAT je dlhá 250*4=1000 bajtov ale keďže FAT zaberá celočíselný počet sektorov tak zvyšných 24 bajtov FAT obsahuje hodnotu FF.FF.FF.FF.

Voľné sektory pripravené na alokovanie sa od už obsadených alokovaných sektorov jednoznačne líšia najvyšším bitom položky. Voľné sektory ho majú nulový, obsadené položky jednotkový. Preto sa pri alokácii ďalších sektorov na médiu môžu vyberať len sektory ktoré majú tento bit nulový.

FAT tabuľka definuje spojový zoznam rozsahu súboru (klastery). FAT začína na logickom sektore prvého segmentu.

Prvý byte FAT sa nazýva Deskriptor media alebo tiež identifikačný byte FAT. Od ďalšieho 5 bytu (12b FAT) alebo 7 bytu (16b FAT) sú samé 0ffH. Zvyšok FAT sa skladá z 12 alebo 16 bitových buniek, ktoré reprezentujú jeden klaster disku. Význam hodnôt položiek vo FAT:

FAT 12 FAT 16 význam
000 0000 voľný klaster
002 – FEF 0002 – FFEF obsadený klaster
FF0 – FF6 FFF0 – FFF6 rezervovaný klaster
FF7 FFF7 chybný klaster (fyzická chyba diskety)
FF8 – FFF FFF8 – FFFF posledný klaster súboru

Štruktúra dátovej časti[upraviť | upraviť zdroj]

Klastery (cluster) dátovej časti sú očíslované. FAT obsahuje pre každý klaster jeden záznam ktorý zaberá 2 alebo 4 bajty (podľa typu FAT). Ak je v klastri súbor alebo adresár, záznam obsahuje odkaz na záznam klastrov na ktorom súbor pokračuje ak nejde o posledý klaster súboru (0xFF). Adresárový alebo súborový kontajner vo FAT je bežný súbor – 32 bajtový záznam FAT adresára. FAT mapuje oblasti dát vo zväzku podľa čísla klastera. Prvý dátový klaster je klaster 2. Prvý sektor klastera 2 je vypočítaný použitím BPB polí pre zväzok.

Dátová oblasť sa skládá z položiek:

  • meno súboru, poklal je kratšie je doplnené medzerami
  • prípona
  • atribúty – jednotlivé bity: xxADLSHR
    • x voľný
    • x voľný
    • A – k archivácii
    • D – adresár (Directory)
    • L – menovka disku (Label)
    • S – systémový (System)
    • H – skrytý (Hidden)
    • R – iba na čítanie (Read only)
  • čas poslednej zmeny
  • dátum poslednej zmeny
  • odkaz na prvý klaster súboru (podadresára)
  • veľkosť súboru v B
Menovka disku (Label) môže zabrať priestor pre meno a príponu, zaberá teda 11 znakov.
Atribút A – je nastavený, pokiaľ chceme pri spustení archivačného programu zálohovať aj tento súbor. Pri archivácii sa tento atribút zruší, pri každej zmene súboru sa nastaví.
Atribút D – znamená, že nejde o súbor, ale o adresár, potom predposledný riadok tabuľky obsahuje odkaz na oblasť, v ktorej nájdeme miesto obsahu súboru rad položiek rovnako štrukturovaných.
Atribút L – určuje, že ide o menovku disku
Atribút S – určuje súbory dôležité pre operačný systém.
Atribút H – označuje skryté súbory. Aby sme ju mohli vidieť napr. v Prieskumníkovi Windows alebo pri použití DIR v DOS-e, musíme tuto voľbu nastaviť v menu Nástroje-Možnosti.
Atribút R – znamená, že súbor sa dá iba čítať, ale nedá sa doň zapisovať.

Štruktúra adresára[upraviť | upraviť zdroj]

Adresár FAT nie je nič iné ako „súbor“ zložený z lineárneho zoznamu 32 bajtových štruktúr. Jediný adresár, ktorý musí byť vždy prítomný je koreňový adresár. U médií s FAT12 / FAT16 je koreňový adresár umiestený hneď za poslednou FAT a má pevnú veľkosť v sektoroch, spočítanú z hodnoty BPB_RootEntCnt. Pre tieto média je prvý sektor koreňového adresára daný číslom sektora vzťahujúcim sa k prvému sektoru zväzku FAT

Zložka rootu (Root directory)[upraviť | upraviť zdroj]

Zložka rootu je umiestená za FAT. Jej dĺžka nie je jednoznačná a závisí na konkrétnom disku. Aby bola možnosť použiť stromovú štruktúru zložiek, pozerá sa systém na všetky zložky (až na root) ako na súbor. Každá položka zložky má dĺžku 32 B. Prvých 8 B sa tyká názvu súboru, kde prvý B je rozhodujúci. Pre bežný súbor alebo zložku je ním prvý znak názvu. Môže však obsahovať aj iný znak, napr. ide o zmazaný súbor. O tom sa môžeme presvedčiť, pokiaľ sa snažíme obnoviť zmazaný súbor. Ďalšie 3 B zaberá 3 bytová prípona. Nasleduje 1 bytová položka, u ktorej jednotlivé bity znamenajú atribúty súboru. V poradí od nultého sú to:

1. ReadOnly – súbor je chránený proti zápisu.
2. Hidden – súbor je skrytý a je vylúčený z normálneho prezerania zložky.
3. System – súbor je označený ako systémový a je vylúčený z normálneho prezerania zložky.
4. ID Volume – položka obsahuje v prvých jedenástich bytoch názov disku.
5. SubDirectory – položka definuje označujúci element ako zložku.
6. Archive – archívny bit – nastavuje sa pri modifikácii súboru.
7. 6. a 7. bit nie sú využité.

Ďalej nasledujú 2 byty nesúce informácie o čase poslednej modifikácie súboru. Ďalšie 2 byty nesú informácie o dátume poslednej modifikácie. Ešte sú tu dva byty, ktoré ukazujú na číslo prvého klastera súboru alebo adresára. Posledná informácia je 4 bytová položka, ktorá udáva dĺžku súboru. Pre adresár je tam 0.

Dlhý adresárový záznam[upraviť | upraviť zdroj]

Dlhé mena sú obmedzene na 255 znakov bez zakončovacieho NUL. Celková dĺžka potom nesmie prekročiť 260 znakov. Dá použiť akákoľvek kombinácia znakov definovaných pre krátke mená a navyše je pridaná bodka („.“), ktorá môže byť použitá opakovane. Medzera je tiež platný znak dlhého mena, rovnako ako u krátkeho mena kde sa tiež často nevyužívala. Nasledujúcich šesť znakov bolo v prípade krátkeho mena zakázané, ale u dlhého mena je možno ich použiť.

$ + , ; = [ ]

Vložené medzery vo vnútri dlhého mena sú povolené, ale na začiatku a na konci názvu sa ignorujú. Počiatočné a vložené bodky sú povolené, ale bodky na konci sa ignorujú. Dlhé mená sú uložene v DAZ v kódovaní UNICODE. Znak v UNICODE je má 16 bitov a je tiež nemožné uložiť takýto znak v KAZ, pretože tu sú znaky uložene osembitovo alebo v DBSC kóde. Dlhé mena prešli cez súborový systém nie sú prevedené na veľké znaky a ich pôvodná hodnota je zachovaná. UNICODE rieši problém s mapovaním veľkých a malých písmen bežných u niektorých OEM kódových stránok automatickým prevodom malých znakov na jednotné veľké znaky.

Krátky adresárový záznam[upraviť | upraviť zdroj]

Krátke mená sú obmedzené na 8 znakov nasledovaných voliteľnou bodkou a maximálne 3-písmenovou príponou. Celková dĺžka cesty krátkeho mena nemôže prekročiť 80 znakov (64 znakov cesta + 3 písmeno jednotky + 12 pre meno 8.3 + NUL) vrátané ukončenia NUL. Znaky môžu byť ľubovoľnou kombináciou písmen, číslic alebo znakov s kódovou hodnotou väčšou ako 127. Nasledujúce znaky sú taktiež povolené:

$ % ' - _ @ ~ ` ! ( ) { } ^ # &

Mená sú uložene v KAZ v OEM kódovej stránke systému, na ktorú je systém nakonfigurovný v dobe vytvorenia AZ. KAZ zostávajú v OEM kvôli kompatibilite so staršími verziami OS. OEM znaky sú jednotlivé 8 bitové znaky alebo pre určité kódové stránky to môžu byť DBCS znakové páry.

Algoritmy[upraviť | upraviť zdroj]

Určenie začiatku dátovej oblasti[upraviť | upraviť zdroj]

FirstDataSector = BPB_ResvdSecCnt + (BPB_NumFATs * FATSz) + RootDirSectors;

Vytvorenie položky v adresári (krátky, dlhý názov)[upraviť | upraviť zdroj]

1. alokuj voľný klaster
2. zapíš prvú časť súboru do tohoto klastera
3. ak neexistuje ďalšia časť súboru koniec
4. alokuj voľný klaster
5. zápis ďalšiu časť súboru do tohto klastera
6. goto 3

Zmazanie položky v adresári (krátky, dlhy názov)[upraviť | upraviť zdroj]

1. nájdi začiatočný klaster súboru
2. nastav obsah tohto klastera na hodnotu 0xE5

Prehľadávanie adresára – hľadanie zadaného súboru[upraviť | upraviť zdroj]

1. načítaj ďalší klaster adresára (ak neexistuje, koniec – súbor sa nenašiel)
2. ak je klaster začiatkom súbora porovnaj názov s názvom súboru (ak sa rovnajú, koniec – našiel)
3. ak nie, goto 1

Určenie nasledujúceho klastera v reťazci[upraviť | upraviť zdroj]

1. načítaj hodnotu v FAT tabuľke z indexu zodpovedajúcemu číslu aktuálneho klastera

Alokácia voľného klastera[upraviť | upraviť zdroj]

1. prehľadaj FAT dokiaľ nenájdeš voľný klaster
2. nastav tento klaster ako nasledujúci použiteľný

Čítanie n bajtov zo súboru[upraviť | upraviť zdroj]

1. nájdi prvý klaster súboru
2. prečítaj obsah klastera
3. i = i + 1
4. ak je n > veľkosť klastera*1 goto 1