Úvod Virtual File System Filesystems. VFS a lesystémy. Petr Uzel. Matematicko-fyzikální fakulta UK. Linux kernel, 2007

Úvod Virtual File System Filesystems

VFS a lesystémy Petr Uzel Matematicko-fyzikální fakulta UK

Linux kernel, 2007

Petr Uzel

VFS a lesystémy


Osnova 1

Úvod

2

Virtual File System P°ehled VFS Caches Vazba VFS na proces Vyhledání souboru

3

Filesystems Ext2 Ext3 Ext4 ReiserFS XFS

Petr Uzel

VFS a lesystémy


Filesystem Wikipedia : Denition File system is a method for storing and organizing computer les and the data they contain to make it easy to nd and access them.

vlastní data mohou být

Data Storage Device)

na datových médiích ( ashdisk, ...

na vzdálených serverech - NFS, SMB, ... virtuální - procfs, sysfs, ...

Petr Uzel

VFS a lesystémy

- HDD, CDROM,


Filesystémy z pohledu uºivatele

/home/petr/le.txt : fd = open(le, ...)

soubory, cesty : le descriptory

atributy : vlastník, skupina, práva, mtime, ...

write, read, lseek directory handle : DIR *d = opendir(/dir/) directory entry : struct dirent *de = readdir(d) oset :

Petr Uzel

VFS a lesystémy


Linux a lesystémy

linux podporuje mnoho lesystém· diskové : ext2, ext3, ext4, ReiserFS, XFS, Minix, ISO9660, UDF, FAT, NTFS, MSDOS clusterové : GFS2, OCFS2, sí´ové : NFS, SMB, CIFS, Coda, AFS virtuální

:

procfs, sysfs

podporu pro dal²í FS lze p°idávat za b¥hu - moduly seznam aktuáln¥ podporovaných FS v

Petr Uzel

/proc/lesystems

VFS a lesystémy


1

Úvod

2

Virtual File System

P°ehled VFS Caches Vazba VFS na proces Vyhledání souboru


3


Petr Uzel

VFS a lesystémy



Virtual File System

virtual lesystem switch abstraktní vrstva nad jednotlivými souborovými systémy specikuje interface mezi kernelem a FS p°edává poºadavky (syscally) odpovídajícím FS

Petr Uzel

VFS a lesystémy



High-level architektura

Petr Uzel

VFS a lesystémy



Datové struktury VFS pouºívá obecné datové struktry (nezávislé na jednotlivých FS)

superblock - lesystém inode - soubor na disku le - otev°ený soubor dentry - adresá°ová poloºka obsahují informace o objektu a tabulku metod pro manipulaci s tímto objektem programování FS znamená p°edev²ím denici metod pro manipulaci s t¥mito objekty zp·sobem, jenº je dán strukturou FS

Petr Uzel

VFS a lesystémy



Superblock struct super_block reprezentuje lesystém typicky bývá na£ten z disku, m·ºe být ale vytvo°en pouze v pam¥ti struktury tvo°í spojový seznam

super_blocks s_list spinlocku : sb_lock

první poloºka uloºena v prom¥nné

dal²í jsou p°ipojeny pomocí pointeru seznam chrán¥n pomocí

data specická pro konkrétní FS :

ext2_sb_info) s_dirt : p°íznak

s_fs_info

udávající, zda je t°eba superblock zapsat na

disk (zda byl modikován)

s_blocksize

(nap°.

: velikost bloku

Petr Uzel

VFS a lesystémy



Superblock II s_type

: pointer na strukturu reprezentující typ lesystému

(nap°. ext2) - viz dále

struct lesystem_type

s_op

: tabulka metod pro manipulaci se superblockem

struct super_operations magic number mount ags synchroniza£ní primitiva seznam v²ech inod· seznam zm¥n¥ných inod· seznam inod· £ekajících na zápis na disk ...

Petr Uzel

VFS a lesystémy



Inode

struct inode inode reprezentuje objekt FS : soubory, adresá°e, FIFO, symlinky, ...

i_ino)

p°i°azen unikátní identikátor v rámci FS ( název souboru

není

sou£ástí inode

m·ºe být reprezentován na disku (FS na blokových za°ízeních) nebo existuje pouze v pam¥ti (virtuální FS)

Petr Uzel

VFS a lesystémy



Inode II inode obsahuje : informace o vlastníkovi souboru, právech typ (soubor, adresá°, symlink, ...) £asy modikace délka souboru £íta£ odkaz· ...

také tabulky metod pro operace : s inode :

struct inode_operations struct le_operations

s otev°enými soubory :

Petr Uzel

VFS a lesystémy



File struct le reprezentuje soubor otev°ený procesem struktura je vytvo°ena v okamºiku otev°ení souboru obsahuje : oset v souboru (kde bude pokra£ovat £tení/zápis) p°ístupový mód (r, w, ...) tabulku metod pro manipulaci se souborem -

le_operations

...

Petr Uzel

VFS a lesystémy

struct



Dentry struct dentry

(directory entry)

reprezentuje název souboru/adresá°e kernel vytvá°í tyto struktury p°i p°ístupu k soubor·m, nap°. p°i otev°ení souboru

/tmp/le.txt

ies

jsou vytvo°eny tyto dentr

dentry pro / dentry pro /tmp dentry pro /tmp/le.txt

struktura obsahuje odkaz na odpovídající inode odkaz na rodi£ovský adresá° tabulku metod pro manipulaci s dentry -

dentry_operations ...

Petr Uzel

VFS a lesystémy

struct

:



Seznam podporovaných FS

struct le_system_type struct file_system_type { const char *name; int fs_flags; int (*get_sb) (struct file_system_type *, int, const char *, void *, struct vfsmount *) void (*kill_sb) (struct super_block *); struct module *owner; struct file_system_type * next; struct list_head fs_supers; ... }; kernel udrºuje seznam podporovaných FS ve struktu°e

lze prohlíºet p°es

/proc/lesystems Petr Uzel

VFS a lesystémy



Registrace FS pro registraci nového (typu) lesystému slouºí funkce

int register_filesystem(struct file_system_type * fs) p°edaná struktura obsahuje jméno FS odkaz na funkci pro na£tení superblocku -

read_super

agy :

zda FS existuje na blokovém za°ízení (jinak je to virtuálni FS)

obvykle volána z funkce

init_module

pro odebrání lesystému slouºí

int unregister_filesystem(struct file_system_type * fs) Petr Uzel

VFS a lesystémy



Mount mount = p°ipojení FS do adresá°ového stromu funkce

long do_mount(char *dev_name, char *dir_name, char *type_page, unsigned long flags, void *data_page) vytvo°í

struct super_block

a za°adí ji do spojového seznamu

k na£tení superblocku volá funkci

read_super

p°ipojený souborový systém je reprezentován strukturou

vfsmount Petr Uzel

VFS a lesystémy

struct



struct super_operations tabulka obsahující seznam funkcí pro práci se superblockem, které poskytuje ovlada£ FS obsahuje bu¤ adresu funkce nebo

NULL

- v tom p°ípad¥ se

pouºije standardní funkce z VFS

alloc_inode

- alokuje pam¥t pro inode

v£etn¥ místa pro data specická pro FS

destroy_inode

read_inode

- na£te inode z FS

£íslo inode vyplní VFS, zbytek struktury vyplní read_inode

dirty_inode

- VFS volá tuto metodu, £ímº ozna£í inode jako

dirty

write_inode

- VFS volá pro zápis inode na disk

jen pokud je inode dirty druhý parametr udává, zda má být zápis synchronní

Petr Uzel

VFS a lesystémy



struct super_operations II put_inode - voláno, kdyº se sníºí po£et referencí na inode drop_inode - voláno, kdyº má být inode odstran¥n (po£et odkaz· klesne na 0) lze vyuºít generickou variantu

generic_drop_inode

- odstraní

v²echny odkazy na inode a zavolá delete_inode()

write_super - voláno pro zápis superblocku sync_fs - zápis v²ech dirty inode na disk

na disk

druhý parametr udává, zda se má volání zablokovat aº do dokon£ení zápisu

statfs - získání statistik lesystému, remountfs - voláno pro remount FS

nap° statfs syscall

...

Petr Uzel

VFS a lesystémy



inode_operations II struktura obsahuje krom¥ metod pro manipulaci s inode také poloºku

struct file_operations *default_file_ops; výchozí tabulka metod pro manipulaci s objektem

le

p°i otev°ení nového souboru a vytvo°ení objektu le jsou

le_operations

inicializovány touto tabulkou

le_operations

lze pak zm¥nit

nap°. p°i otev°ení speciálního souboru

Petr Uzel

VFS a lesystémy



inode_operations - adresá°e create - vytvo°í inode pro normální soubor v daném adresá°i lookup - zkontroluje, zda objekt identikovaný dentry existuje v adresá°i

link

- vytvo°í new_dentry jako hardlink na old_dentry v

daném adresá°i

unlink - odstraní soubor z adresá°e symlink - vytvo°í nový adresá° rmdir - odstraní adresá° mknod - vytvo°í speciální za°ízení

Petr Uzel

VFS a lesystémy



inode_operations II

rename - p°ejmenuje soubor readlink - p°e£te cestu k odkazovanému

souboru ze

symbolického odkazu do bueru

follow_link - vrátí dentry, na n¥jº ukazuje symbolický odkaz truncate - zm¥ní velikost souboru permission - kontrola p°ístupových práv - zda odpovídají zadanému vzoru

Petr Uzel

VFS a lesystémy



le_operations llseek - zm¥ní pozici ukazatele v souboru read - p°e£te data od pozice ukazatele a uloºi

je do bueru

je t°eba aktualizovat hodnotu oset

write

- zapí²e count data z bueru na pozici ukazatele

taktéº nutné aktualizovat oset

readdir - vrátí dal²í poloºku z adresá°e poll - kontroluje aktivitu na souboru, p°ípadn¥ select, poll

ioctl

- po²le p°íkaz HW za°ízení pouze pro speciální soubory

Petr Uzel

VFS a lesystémy

se uspí



le_operations II mmap - mapuje soubor open - otev°e soubor

do adresního prostoru procesu

vytvo°í strukturu le k danému inode

fsync - zapí²e data na disk readv - vektorové £tení souboru £tení do nesouvislých oblastí pam¥ti

writev

- vektorový zápis

...

Petr Uzel

VFS a lesystémy



dentry_operations obvykle jsou ponechány

NULL,

tzn. kernel pouºije generické

varianty

d_revalidate, d_delete, d_release

: generické varianty jsou

prázdné funkce

d_compare

: porovná dva dentry

generická varianta :

strcmp

VFAT : case insensitive strcmp

d_hash - vytvo°í hash z názvu d_iput - voláno, kdyº dentry ztratí

Petr Uzel

sv·j inode

VFS a lesystémy



Programování FS

je t°eba p°ipravit struktury reprezentující privátní data naprogramovat callbacky, naplnit jimi struktury a p°edat je kernelu net°eba denovat v²echny callbacky - VFS m·ºe pouºít generické varianty

/usr/src/linux/fs/romfs/ /usr/src/linux/fs/ramfs/

Petr Uzel

VFS a lesystémy


1

Úvod

2

Virtual File System



3


Petr Uzel

VFS a lesystémy



Dentry cache directory cache, dcache cachuje adresá°ové poloºky nalezení souboru p°ímo na FS by trvalo neúm¥rn¥ dlouho

cachují se pouze poloºky krat²í neº 15 znak· tvo°ena hashovací tabulkou indexováno pomocí dvojice

rodi£ovský adresá° - poloºka

v tabulce jsou uloºena £ísla odpovídajících inode a odkazy na bloková za°ízení pro kaºdou poloºku v dentry cache existuje i odpovídající záznam v inode cache (dále) staré poloºky vyhazovány algoritmem LRU

Petr Uzel

VFS a lesystémy



Buer cache

cachuje fyzické bloky diskových oddíl· cache spole£ná v²em oddíl·m poloºky indexovány dvojicí

blokové za°ízení - £íslo bloku

spravuje bloky r·zných velikostí (512 - 8192) spojový seznam volných blok· staré bloky nahrazovány LRU algoritmem

bdush)

buery pravideln¥ zapisovány na disk (

Petr Uzel

VFS a lesystémy



Inode cache cachuje inody (virtuální) hashovací tabulka, indexována dvojicí

inode

blokové za°ízení - £íslo

pokud není poºadovaný inode nalezen, je t°eba alokovat nový p°i vy£erpání maximálního po£tu inode v cache musí být n¥jaký uvoln¥n nepouºívané inode (nulové po£ítadlo referencí) pokud byl p°ed uvoln¥ním modikován, jsou data zapsána na disk

ko°enové inode namountovaných FS mají po£ítadla vºdy nenulová

Petr Uzel

VFS a lesystémy


1

Úvod

2

Virtual File System



3


Petr Uzel

VFS a lesystémy



fs_struct struktura p°i°azená kaºdému procesu

struct task_struct { ... struct fs_struct *fs; /* FS info */ struct files_struct *files; /* open files */ ... ( poloºky v fs_struct : root : dentry pro / pwd : dentry pro pracovní adresá° ...

Petr Uzel

VFS a lesystémy



les_struct specikuje soubory otev°ené procesem

struct files_struct { unsigned int max_fds; struct file ** fd; int next_fd; ... } poloºka

fd

ukazuje na pole le deskriptor·

velikost pole je v

max_fds

velikost pole se dynamicky m¥ní podle pot°eby, za£íná na 32 dv¥ poloºky v

fd

mohou ukazovat na stejný soubor

Petr Uzel

VFS a lesystémy


1

Úvod

2

Virtual File System



3


Petr Uzel

VFS a lesystémy



Vyhledání souboru

open(/tmp/le.txt) je t°eba získat odpovídající inode analyzuje se cesta k souboru - ²t¥pí se podle / kdyº cesta za£íná na /, je absolutní vyhledávání za£íná v

current->fs->root

jinak je relativní vyhladávání za£íná v

current->fs->pwd

Petr Uzel

VFS a lesystémy



Vyhledání souboru II p°edchozím krokem byl získán dentry adresá°e, ze kterého se za£ne vyhledávat odpovídající inode je p°e£ten a tak je získána dentry dal²í £ásti cesty postupuje se rekurzivn¥

vyhledávání obvykle urychluje dentry cache komplikace : p°ístupová práva mezilehlých adresá°· symbolické odkazy cyklické symbolické odkazy

Petr Uzel

VFS a lesystémy



path_lookup funkce, která provádí vlastní vyhledávání souboru parametrem je název souboru funkce vrací vícero informací z vyhledávání, nejd·leºit¥j²í je dentry souboru po provedení

path_lookup

je t°eba zavolat

path_release

výsledky vyhledávání uº nejsou t°eba

kompletní popis algoritmu : http://www.linux-security.cn/ebooks/ulk3html/0596005652/understandlk-CHP-12-SECT-5.html

Petr Uzel

VFS a lesystémy


1

Úvod

2

Virtual File System

Ext2 Ext3 Ext4 ReiserFS XFS


3


Petr Uzel

VFS a lesystémy



Ext2 - historie

second Extended File System následovník p·vodního

linuxového

FS - Minix

minix : mnoho omezení, nap°. max velikost souboru 64MB mezikrok : Ext FS (Extended File System)

1992, Linux 0.96c

ext2 : 1993

Petr Uzel

VFS a lesystémy



Ext2 - fyzická struktura FS je tvo°en skupinou blok· (Block Groups) Boot Sector

BG1

BG2

...

BG3

kaºdá skupina blok· obsahuje kopii superbloku a £ást vlastního FS : block bitmap inode bitmap £ást inode table datové bloky

struktura skupiny blok· : SB

Block BM

Inode BM

Petr Uzel

Inode Table

Data Blocks

VFS a lesystémy



Ext2 - fyzická struktura II

datové bloky :

direct, indirect, double indirect, triple indirect

viz. dále bitmapy : jeden bit pro kaºdý blok/inode (volný/vyuºitý) skupiny blok· : spolehlivost (kopie superblocku) výkon - men²í vzdálenost mezi inode table a datovými bloky

Petr Uzel

VFS a lesystémy

-



Ext2 - datové bloky struct ext2_inode { ... __le32 i_block[EXT2_N_BLOCKS]; ... } inode m·ºe p°ímo obsahovat adresy 15 datových blok·

EXT2_N_BLOCKS)

(

0..11 : prvních 12 datových blok· souboru 12 : odkaz na blok, který obsahuje adresy dal²ích blok·

indirect block 13 : 14 :

double indirect block triple indirect block Petr Uzel

VFS a lesystémy



Ext2 - datové bloky II

Petr Uzel

VFS a lesystémy



Ext2 - superblock data specická pro Ext2

struct ext2_sb_info { unsigned long s_frag_size; unsigned long s_frags_per_block; unsigned long s_inodes_per_block; unsigned long s_frags_per_group; unsigned long s_blocks_per_group; unsigned long s_inodes_per_group; ... } funkce

ext2_read_super Petr Uzel

VFS a lesystémy



Ext2 - Adresá°e

mapování jméno souboru <-> inode number spojový seznam, kaºdá poloºka obsahuje : inode number délka názvu souboru název souboru

první dv¥ poloºky jsou vºdy standardní . a ..

Petr Uzel

VFS a lesystémy



Ext2 - zm¥na velikosti souboru nalezení volného bloku - problém fragmentace snaha alokovat nový blok ve stejné skupin¥ blok·

p°i alokaci nových blok· je uzam£en superblock inody mohou mít p°id¥leny prealokované bloky - místo rezervované v bitmap¥ pokud nelze uspokojit poºadavek na nové bloky pomocí prealokovaných blok·, prohledávají se následující bloky : blok bezprost°edn¥ za posledním alokovaným blokem blok max 64 blok· za posledním alokovaným blokem hledají se klastry 8mi volných blok· v ostatních skupinách blok·

Petr Uzel

VFS a lesystémy



Ext2 - features

velikost FS aº 4TB 5% prostoru rezervováno pro roota volitelná velikost bloku (1k, 2k, 4k)

fast symbolic links

: jméno odkazovaného souboru m·ºe být

uloºeno p°ímo v inodu bezpe£né mazání soubor· : náhodná data

immutable, append-only tune2fs

soubory (

Petr Uzel

chattr)

VFS a lesystémy



Ext3 - úvod následník ext2

Stephen Tweedie,

1999

v kernelu od verze 2.4.15 (2003) stejný formát dat na fyzickém médiu jako ext2 rozdíly (oproti ext2) : ºurnál

lze p°evést online z ext2 bez nutnosti backup/restore

jen p°idání ºurnálu tune2fs -j /dev/hdaX

Petr Uzel

VFS a lesystémy



Ext3 - ºurnálování zm¥ny na FS - velké IO operace, náchylné k soub¥h·m p°i výpadku stroje smazání souboru : odstran¥ní

directory entry

ozna£ení datových blok· a inode jako volné

obnova (fsck) neºurnálovaného FS : sloºité procházení datových struktur a hledání nekonzistencí ºurnálování = logování zm¥n na FS, lze

p°ehrát

stroje zaru£ena atomicita transakce

lze ºurnálovat jen metadata, nebo i data

Petr Uzel

VFS a lesystémy

po výpadku



Ext3 - ºurnál vyuºívá

Journaling Block Device layer

(JBD)

obecná vrstva, ale vyuºito jen ext3/4 ºurnál uloºen v inode - m·ºe/nemusí být vid¥t fyzické ºurnálování - JBD ukládá celé zm¥n¥né bloky

3 úrovn¥ ºurnálování :

data=writeback

: nejrychlej²í, ºurnálována jsou pouze

metadata

rychlé fsck, jinak srovnatelné s ext2

data=ordered

: zaru£uje konzistenci dat vynucením jejich

zápisu p°ed zápisem metadat

ºurnálována jsou pouze metadata defaultní úrove¬

data=journal

: ºurnáluje se v²e, nejpomalej²í (data se musí

zapisovat dvakrát)

Petr Uzel

VFS a lesystémy



Ext4 2006, kernel 2.6.19 stále experimentální status zp¥tná kompatibilita s ext3 (jednosm¥rn¥) odstra¬uje n¥které ²kálovací nedostatky ext3 max. velikost FS 16TB -> 1EB

48b £ísla blok· nové JBD (JBD2) max. velikost souboru 2TB -> 16TB

extents jednoduchá adresace souvislých fyzických blok· výhoda pro velké soubory

...

Petr Uzel

VFS a lesystémy



ReiserFS Namesys,

Hans Reiser

ReiserFS 3, Reiser4 ºurnálování (metadata, data i metadata) tail-packing konce soubor· uloºeny v separátním oddílu sniºuje fragmentaci, zvy²uje zát¥º

metadata, adresá°ové poloºky, seznamy datových blok· a jsou uloºeny spole£n¥ v B+ stromu univerzální

object-ID

Petr Uzel

VFS a lesystémy

tails



XFS SGI, 1994 - IRIX 5.3 2000 - GPL 64b FS ºurnálování : metadata

logický ºurnál

m·ºe probíhat na samostatné partition

FS rozd¥len na stejn¥ velké

allocation groups

spravují vlastní inody a volné místo ²kálovatelnost - kaºdé vlákno m·ºe soub¥ºn¥ pracovat ve své

AG

Petr Uzel

VFS a lesystémy



XFS II

extents volné místo : dvojice B+ strom· pro kaºdou allocation group jeden indexován délkou volných extents druhý indexován za£átky volných extents efektivní vyhledání volného místa

velikost bloku 512B - 64k ...

Petr Uzel

VFS a lesystémy



Konec

Petr Uzel

VFS a lesystémy

Úvod Virtual File System Filesystems. VFS a lesystémy. Petr Uzel. Matematicko-fyzikální fakulta UK. Linux kernel, 2007

Recommend Documents