Operační systém UNIX a jazyk C

Jan Brodský
Luděk Skočovský

SNTL Nakladatelství technické literatury Praha 1989, ISBN 80-03-00049-1

10. Implementace


10.4 Svazky a soubory

Svazek je z hlediska blokových zařízení chápán jako posloupnost bloků standardní délky očíslovaných od nuly.

10.4.1 Struktura svazku

Blok nula se ve většině svazků nepoužívá. Na systémovém svazku, tj. na svazku, který obsahuje kořenový adresář, však tento (boot) blok obsahuje zaváděcí program.

[OBR. 10.9]

Blok číslo 1 je tzv. superblokem, který obsahuje potřebné údaje o svazku. V superbloku je uložna struktura filesys, v níž jsou použity definice typů

typedef long daddr_t;
typedef unsigned int ino_t;
typedef long time_t;
a konstant
#define NF 50
#define NI 100

struct filsys {
	unsigned short isize;	/* velikost i-seznamu v blocích */
	daddr_t fsize;		/* velikost svazku v blocích */
	int nfree;		/* počet volných bloků */
	daddr_t free[NF];	/* f-seznam volných bloků */
	char flock;		/* zámek na f-seznam */
	char ilock;		/* zámek pro i-seznam */
	char fmod;		/* příznak modifikovaného superbloku */
	char ronly;		/* příznak připojení svazku pouze pro čtení */
	time_t time;		/* čas posledního zápisu do superbloku */
}

Struktura filsys má v různých verzích Unixu ještě další složky, avšak ty, co jsme uvedli, jsou podstatné a všem variantám společné.

Za superblokem jsou uloženy i-uzly souborů, jejichž datové bloky jsou uloženy v následující části svazku (obr. 10.9).

10.4.2 Seznam volných bloků

Volný prostor na disku je evidován v řetězeném seznamu. Prvním členem seznamu posledních uvolněných bloků je pole free[NF] v superbloku. Jejich adresy jsou uloženy v prvních free[1], ... ,free[nfree]. Je-li volných bloků více, obsahuje free[0] adresu bloku, který obsahuje seznam dalších NF volných bloků. Jde vlastně vždy o další kopii zcela zaplněného pole free (obr. 10.10).

[OBR. 10.10]

počet volných bloků přímo adresovatelných ze superbloku je udržován ve složce nfree superbloku. Přidělení volného bloku je jednoduché. Je-li nfree > 0, sníží se o 1 a je přidělen blok free[nfree]. Je-li nfree = 0, načte se na místo pole free obsah bloku free[0], nfree se nastaví na NF a tím se situace převede na předchozí případ. Je-li free[0] nulové, není žádný blok volný a žádající proces se zablokuje.

Při vracení bloku se postupuje obráceně. Je-li nfree > NF, zapíše se číslo uvolňovaného bloku do free[nfree] a nfree se zvýší o 1. Pro nfree = NF se pole free uloží do uvolňovaného bloku na disk, hodnota nfree se vynuluje a číslo uvolněného bloku se uloží do free[nfree], tj. do free[0].

Přidělení i uvolnění bloku je časově nenáročná operace. Bloky jsou přidělovány v náhodném pořadí, linearitta souborů se dosahuje seznamem bloků obsazených souborem a mechnismem systémových vyrovnávacích pamětí. Není třeba bloky slučovat, ani uklízet (garbage collection).

10.4.3 Diskové i-uzly

Diskové i-uzly obsahují údaje o všech typech souborů. Na každém svazku jsou očíslovány od 1. Každý diskový i-uzel obsahuje strukturu

struct dinode {
	unsigned short type;	/* typ a příznak ochrany souboru */
	short nlink;		/* počet odkazů v adresáři */
	short uid;		/* uid vlastníka souboru */
	short gid;		/* gid vlastníka souboru */
	off_t size;		/* délka souboru ve slabikách */
	char addr[40];		/* adresy bloků souboru */
	time_t atime;		/* čas posledního přístupu */
	time_t mtime;		/* čas posledního zápisu */
	time_t ctime;		/* čas vytvoření souboru */
}

Přijmeme-li ještě definici typu

typedef long off_t;
pak se při délce bloku 512 slabik do jednoho bloku vejde 8 i-uzlů (po 64 slabikách).

· V položce type (obr. 10.11) je uložen bitový kód typu souboru a příznaky přístupových práv. Speciální soubory nemají speciální čísla i-uzlů; odlišují se pouze svým typem a tím, že v poli addr mají místo adres bloků své hlavní a vedlejší číslo. Adresáře se rovněž odlišují pouze příznakem v položce type.

· Unix udržuje v adresovém prostoru jádra tabulku aktivních i-uzlů. Tato tabulka sestává z pole struktur inode.

#define NADDR 13
extern struct inode {
	char flag;		/* stav i-uzlu a souboru */
	char count;		/* kolikrát je otevřen */
	dev_t dev;		/* zařízení, kde je diskový i-uzel */
	ino_t ino;		/* číslo diskového i-uzlu na dev */
	ushort type;		/* typ */
	short nlink;		/* počet odkazů v adresáři */
	short uid;		/* uid vlastníka souboru */
	short gid;		/* gid vlastníka souboru */
	off_t size;		/* velikost souboru */
	daddr_t addr[NADDR];	/* diskové adresy */
	time_t lastt;		/* čas poslední operace s daty */
}inode[];

Začne-li se pracovat s novým souborem (zpravidla funkcí open), jádro najde odpovídající diskový i-uzel v tabulce aktivních i-uzlů, přidělí volnou strukturu inode a naplní ji daty z diskového i-uzlu. Některé položky mají stejný formát, diskové adresy (tj. čísla) datových bloků souboru jsou na disku komprimovány po třech slabikách a dojde k jejich konverzi na daddr_t, tj. na long.

[OBR. 10.11]

Od tohoto okamžiku je struktura inode v tabulce aktivních i-uzlů považována za aktuální verzi i-uzlu a v ní se odehrávají všechny operace. Po ukončení práce se souborem (close) se okopíruje obsah struktury inode zpět do diskového i-uzlu a její místo v tabulce se uvolní.

Do tabulky aktivních i-uzlů se soubor dostane explicitní žádostí o otevření (voláním open) nebo tak, že odpovídá pracovnímu adresáři některého procesu nebo reprezentuje speciální soubor blokového zařízení s připojeným svazkem.

10.4.4 Datové bloky souborů

Diskový i-uzel obsahuje adresy 13 diskovývh bloků. Prvních deset udává přímo prvních deset datových bloků souboru (což se samozřejmě netýká souborů speicálních). Předpokládáme-li délku bloku 512 slabik, mají soubory s nejvýše 5120 slabikami bloky přímo dostupné z i-uzlu. Další soubory musí využít mechanismus nepřímého adresování diskových bloků. Tento mechanismus je až trojnásobný.

Blok určený jedenáctou adresou neobsahuje data souboru, ale adresy dalších 128 bloků s daty. Tato úroveň adresování tedy stačí na 5120 + 128 * 512 = 70656 slabik souboru. Ještě delší soubory využívají dvouúrovňové nepřímé adresování. Blok určený dvanáctou adresou obsahuje adresy 128 bloků, z nichž každý obsahuje 128 adres datových bloků. Soubor teď může mít 5120 + 128 * 512 + 128 * 128 * 512 = 8459264 slabik. Pokud to nestačí, je poslední možností blok určený třináctou adresou v i-uzlu, obsahující 128 čísel bloků, z nichž každý obsahuje 128 adres bloků, z nichž každý obsahuje 128 adres datových bloků. Maximální rozsah souboru (pro délku bloku 512 slabik) je 5120 + 128 * 512 + 128 * 128 * 512 + 128 * 128 * 128 * 512 = 1082201087 slabik, tedy přibližně 1GB.

Pro soubory delší než 512 slabik se tedy spotřebují režijní diskové bloky na adresy. Současně se přístup k datům zpomaluje o jeden, dva či tři diskové (režijní) přístupy. Pro násobné operace s daty, uloženými dál v souboru, se uplatní systémové vyrovnávací paměti. Prostor na disku, spotřebovaný na režijní bloky, nepřesahuje zpravidla 10% celkového rozsahu datových souborů [4].

10.4.5 Adresáře a připojitelné svazky

V předchozích odstavcích jsme popsali, jak je souborům přidělován prostor na disku a jak podle identifikace zařízení (dev) a čísla i-uzlu lze najít datové bloky souboru. Přes i-uzly procházejí všechny operace se soubory. Uživatel však často o i-uzlech a jejich číslech nemusí vědět. Používá symbolická jména, zapsaná jako cesta od kořenového nebo pracovního adresáře k souboru.

Vraťme se nyní detailně k adresářům. Adresář obsahuje pole struktur

#define DIRSIZ 14
struct direct {
	ino_t ino;		/* číslo i-uzlu */
	char name[DIRSIZ];	/* prosté jméno souboru */
}

Převod úplného jména na číslo i-uzlu je přímý. Vejde se do i-uzlu známého adresáře. Je to pracovní nebo kořenový adresář a čísla jejich i-uzlů jsou uložena ve struktuře user procesu (odst. 10.2.3). Prohlédnutím tohoto adresáře se najde další prosté jméno cesty a z položky ino se získá číslo i-uzlu. Bylo-li nalezeno poslední prosté jméno cesty, jsme u cíle. Je-li v cestě ještě další, získané číslo i-uzlu náleží adresáři a algoritmus se opakuje.

Zatím zde chybí zmínka o výchozím i-uzlu. Tím je konvencí stanovený i-uzel kořenového adresáře každého svazku. Má vždy číslo ROOTINO = 2.

Další zajímavou vlastností adresářů jsou zkrácená jména pracovního a nadřazeného adresáře (tj. "." a ".."). Jejich implementace je triviální, jak je patrné z obr. 10.12.

Soubor je jednoznačně určen svazkem a číslem i-uzlu v rámci tohoto svazku. Při prohledávání adresářů se k získanému číslu i-uzlu přidruží svazek, na němž je adresář uložen.

Kromě pevného výchozího i-uzlu je třeba pevně stanovit i výchozí svazek. Je to systémový svazek založený v zařízení /dev/root. Na tomto svazku musí být umístěn kořenový adresář celé adresářové hierarchie souborů a adresářů.

Hierarchii lze poměrně snadno rozšířit připojením dalšího svazku do listu stromové struktury. K tomu stačí zavést tabulku připojených svazků (mount table) obsahující pole struktur

extern struct mount {
	dev_t_dev;		/* identifikace zařízení */
	struct inode *inodp;	/* ukazatel do tabulky aktivních i-uzlů */
} mount[];
a při procházení adresáři ověřovat, zda *inodp neobsahuje získané číslo i-uzlu.

[OBR. 10.12]

Pokud obsahuje a jde např. o j-tou strukturu, pak jádro změní identifikaci zařízení na mount[j].dev a místo získaného čísla i-uzlu dosadí číslo 2. Tím se jako další adresář v pořadí bude prohledávat kořenový adresář na svazku právě založeném v zařízení mount[j].dev.

Ukažme si postup na příkladě. Nechť je systémový svazek založen v zařízení /dev/rk0. To má identifikaci (0,0) - ve shodě s příkladem obsazení tabulky bdevsw v odst. 10.3.6. Vyjdeme-li dále ze situace na obr. 10.12, má tabulka aktivních i-uzlů obsah znázorněný na obr. 10.13a.

Systémový svazek není v tabulce připojených svazků evidován. Pro jiné svazky se do této tabulky provede zápis, provede-li se příkaz mount. Na obr. 10.13b je znázorněn její obsah a obsah tabulky aktivních i-uzlů po připojení svazku založeného do zařízení /dev/rk1 s identifikací (0,1) do místa /usr hierarchie souborů a adresářů. V tabulce aktivních i-uzlů jsou nyní dva záznamy pro podstrom /usr. Vzhledem k popsanému prohledávání adresářů však po připojení platí až druhý z nich. Prověřme to na příkladě hledání i-uzlu souboru /usr/xxx.

Vyjdeme ze známého i-uzlu s číslem 2, na zařízení /dev/root. V tabulce aktivních i-uzlů najdeme odpovídající záznam, načteme datové bloky adresáře /. Jeho prohlédnutím (obr. 10.12) najdeme, že jménu usr přísluší i-uzel s číslem 24. V tabulce aktivních i-uzlů najdeme odpovídající záznam a zjistíme, že na něj vede odkaz z tabulky připojených svazků. Změníme tedy číslo i-uzlu na 2 a identifikaci zařízení na (0,1) z této tabulky a opět prohledáváme tabulku aktivních i-uzlů. Pro zařízení (0,1) a i-uzel číslo 2 najdeme záznam, načteme datové bloky adresáře a hledáme v nich jméno xxx (na obr. 10.13 není naznačeno).

[OBR. 10.13]

Po odpojení svazku příkazem mount se ruší příslušná položka tabulky připojených svazků a tabulky aktivních i-uzlů a použitému místu připojení (v našem případě /usr) se obnoví jeho původní obsah. Ten je po dobu připojení svazku nedostupný. Proto se obvykle na místo připojení volí prázdné adresáře (obsahující pouze jména "." a "..").