<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<title>Projekt a diplomky tykajici se LFS</title>
<meta http-equiv="Content-language" content="cs">
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-2">
<style type="text/css">
body {width: 85ex}
p {text-indent: 2ex}
</style>
</head>
<body>
<h1>Projekt a diplomky týkající se LFS</h1>
<a name="obsah">
<h3>Obsah</h3>
<ol>
<li><a href="#obsah">Obsah</a></li>
<li><a href="#cojelfs">Co je to LFS</a></li>
<li><a href="#diplomka">Diplomová práce</a></li>
<li><a href="#kohoproc">Koho chceme a proè do toho jít</a></li>
<li><a href="#literatura">Související Literatura</a></li>
</ol>
<a name="cojelfs">
<h3>Co je to LFS</h3>
<p>
Log-structured file system (LFS) je file systém, který zapisuje
ve¹keré zmìny sekvenènì na disk jakoby do logu (to napøíklad znamená,
¾e zmìny v daném souboru se nezapisují na stejné místo jako pøedchozí
obsah), èím¾ urychluje jak zápis tak zotavení z havárií. Log je
jediná struktura na disku. Ta obsahuje ale také klasický index,
tak¾e soubory jsou z logu èteny efektivním zpùsobem. V pøípadì zájmu
detaily a informace o LFS a konkrétnì o na¹em projektu najdete v
<a href="#literatura">literatuøe</a> uvedené úplnì na konci
tohoto textu.
</p>
<a name="projekt">
<h3>Projekt</h3>
<p>
Námi momentálnì navrhovaný projekt je <b>pøevá¾nì</b> v user space,
pøesto je urèitì dùle¾itý a zajímavý a není snadný. Pokud by nìjaká
skupina skuteènì chtìla projekt v kernelu a pouze kernelu, podívejte
se do èásti o diplomových pracích, s trochou spoleèného úsilí by
jistì nìco z toho ¹lo pøedlo¾it i projektové komisi.
</p>
<p>
Pro produkèní nasazení file systému je dùle¾ité nejen to, jak se
chová za normálního provozu, ale také jak se zotavuje z havárií, chyb
a po¹kození dat na disku. Za to, ¾e jsou linuxové ext[23] file
systémy tolik populární, vdìèí mimo jiné i pokroèilým
fsck utilitám, které doká¾í disk zkontrolovat a obnovit jeho
konzistenci, a to i kdy¾ jsou nìkterá dùle¾itá data nenávratnì
ztracena.
</p>
<p>
LFS kromì toho funguje nejlépe, kdy¾ se mù¾e spolehnout na existenci
utility, která v pøípadì pádu umí v¹echny plnì zapsané segmenty od
posledního syncu zaèlenit do filesystému. Takové utilitì øíkáme
roll-forward a bohu¾el ta stávající vìt¹inou nefunguje a je ji tøeba
zcela nahradit.
</p>
<p>
Øe¹itelé projektu budou mít za úkol implementovat roll-forward a fsck
utility. Nároky na roll-forward budou vysoké, bude muset byt schopný
spadlý systém v¾dy vrátit do konzistentního stavu. Po¾adavky na fsck
mo¾no formulovat mírnìji, ale mìl by být schopný opravit alespoò
vìt¹inu toho, co umí e2fsck.
</p>
<p>
Kdyby to náhodou bylo nutné èi vhodné, budou moci øe¹itelé zásahem do
kernelového zdrojového kódu LFS mírnì zmìnit formát dat na disku.
Jinak pøedpokládám, ¾e pou¾itý jazyk pro user space èást bude C++
nebo C. Pøesto¾e to bude projekt pomìrnì tì¾ký a rozsáhlý (vskutku se
file systém naimplementuje skoro je¹tì jednou), mìl by být mnohem
jednodu¹¹í na odladìní ne¾ práce s file systémem v kernelu (a tím
pádem by mìla být jednodu¹¹í zejména závìreèná hektická èást projektu
:-).
</p>
<a name="diplomka">
<h3>Diplomová práce</h3>
<p>
Pøíhodné okruhy diplomových prací jsou zdá se v¹echny kernelové.
Øe¹itel by si mohl vybrat nìjakou kombinaci z øe¹ení nìkolika
zajímavých problematik:
</p>
<ol>
<li> <b>Zvý¹ení konfigurovatelnosti.</b> Toto se týká zejména podpory
i jiných velikostí blokù a segmentù, ne¾ té jedné kombinace, která
je podporována dnes. Pøesto¾e teoreticky je mnoho kódu ji¾
napsáno, je neotestován a bude asi slou¾it spí¹e jako vodítko,
proto¾e øe¹itel s nejvìt¹í pravdìpodobností narazí na mnoho
problémù, mimo jiné i synchronizaèních, které si vy¾ádají komplexní
úpravy. <br>
Kdyby se podaøilo sehnat nìjaký exotiètìj¹í hardware, bylo by jistì
zajímavé vyzkou¹et LFS napøíklad na big-endian strojích a pøípadnì
opravit odhalené chyby.
</li>
<li> <b>Reakce na chyby.</b> Jak se filesystém zachová pøi chybách
zápisu na disk (selhání blokového zaøízení) je dosud velká neznáma.
Øe¹itel by nejprve analyzoval chování stávající implementace pøi
simulaci chyb a poté by navrhl a implementoval opatøení, je¾ by
odstranila zjevné chyby v momentální implementaci, vedla k záchranì
co nejvìt¹ího mno¾ství dat a zajistila co mo¾ná nejvìt¹í
konzistenci dat, zejména metadat. <br>
Obdobnì by stálo za to analyzovat a øe¹it i chyby ètení, zejména
chyby ètení metadat v rámci zápisu.
</li>
<li> <b>Garbage collection ve snapshotu.</b> Velmi zajímavé,
ale pravdìpodobnì také docela nároèné téma. Terminologii nejspí¹
nelze zkratkovitì vysvìtlovat, proto opìt odká¾i na literaturu nebo
osobní konzultaci. Momentálnì je snapshot mo¾no rozumnì realizovat
jen pokud je k dispozici mnoho zcela volných segmentù. Øe¹itel by
musel komplexnì modifikovat nìkolik subsystémù, aby dovolil garbage
collection a tím vytváøení volných segmentù i v oblastech, kde je
snapshot, tedy napøíklad pøesouvání více verzí dat najednou.<br>
Také by bylo záhodno pøidat podporu pro více ne¾ jeden snapshot.
</li>
<li> <b>Wear levelling a pou¾ití pøímo na NAND Flash "disku."</b>
Mo¾ná nejpraktiètìj¹í okruh, o kterém ov¹em pøíli¹ nikdo nevíme, a
proto teï nedoká¾eme odhadnout jeho obtí¾nost.
</li>
</ol>
<p>
Samozøejmì mo¾ností je urèitì více a my rádi pomù¾eme i s pøípadnými
va¹imi nápady.
</p>
<p>
V ka¾dém pøípadì by práce zahrnovala i malinko jakéhosi udr¾ování a
uklízení, ale toho by jednak nemìlo být mnoho a jednak s ním
v omezené míøe pomù¾eme.
</p>
<a name="kohoproc">
<h3>Koho chceme a proè do toho jít</h3>
<p>
Pokud vás ale systémové programování nebo file systémy a související
problematika zajímá, potom byste tuto nabídku mìli skuteènì zvá¾it,
proto¾e Vás mù¾e posunout hodnì dopøedu. Pouze a¾ si v
<b>produkèním</b> kernelu naimplementujete netriviální vìc, budete
mít dobrou pøedstavu, co to systémové programování je. I ná¹ user
space návrh projektu Vám dá náhled do problematiky ukládání dat, jaký
má jen málokdo, proto¾e zdá se, ¾e fsck pro LFS není téma pøíli¹
probádané, alespoò se mi o tom nepodaøilo najít ¾ádnou publikaci.
</p>
<p>
Nám se podaøilo o na¹em projektu
publikovat èlánek v èasopise Operating Systems Review, ACM. Kdyby dal¹í
projekt èi diplomka také podaøila, urèitì se budeme sna¾it publikovat
i nové výsledky. Myslím, ¾e mít publikaci z magisterského studia
urèitì není k zahození (ale je to samozøejmì práce navíc).
</p>
<p>
Log-structured file systémy jsou navíc sice konceptem starým, ale
dnes opìt zajímavým, zejména v souvislosti s NAND Flash "disky,"
nebo» v LFS lze pøímo implementovat wear-levelling, zatímco tradièní
file systémy potøebují pomocnou mezivrstvu.
</p>
<p>
Jak projekt, tak okruhy pro diplomové práce jsou spí¹e z tìch
tì¾¹ích. Proto také prosím ale zva¾te, jaké jsou va¹e mo¾nosti,
zejména èasové, a zda sledujete pouze splnìní studijních povinností
nebo i nabytí cenných zku¹eností.
</p>
<p>
V pøípadì zájmu nebo jakéhokoliv relevantního dotazu mi prosím
napi¹te na jamborm (at) matfyz.cz.
</p>
<p>
Martin Jambor
</p>
<a name="literatura">
<h3>Související Literatura</h3>
<pre>
[1] M. Rosenblum and J. K. Ousterhout:
The Design and Implementation of a Log-Structured File System.
ACM Transactions on Computer Systems
<a href="http://citeseer.ist.psu.edu/rosenblum91design.html">http://citeseer.ist.psu.edu/rosenblum91design.html</a>
[2] M. Seltzer, K. Bostic, M. K. McKusick, C. Staelin:
An Implementation of a Log-Structured File System for UNIX.
USENIX Winter
<a href="http://citeseer.ist.psu.edu/26730.html">http://citeseer.ist.psu.edu/26730.html</a>
[3] M. Jambor, T. Hruby, J. Taus, K. Krchak, V. Holub:
Implementation of a Linux log-structured file system with a
garbage collector
ACM SIGOPS Operating Systems Review
<a href="http://doi.acm.org/10.1145/1228291.1228299">http://doi.acm.org/10.1145/1228291.1228299</a> (z matfyzu zadarmo)
[4] M. Jambor, T. Hruby, J. Taus, K. Krchak, V. Holub:
Log-structured file system for Linux 2.6 - Project Documentation
<a href="http://aiya.ms.mff.cuni.cz/lfs/doc.shtml">http://aiya.ms.mff.cuni.cz/lfs/doc.shtml</a>
[5] M. McKusick and T. Kowalski:
Fsck -- The UNIX File System Check Program.
4.4 BSD System Manager's Manual
<a href="http://citeseer.ist.psu.edu/mckusick94fsck.html">http://citeseer.ist.psu.edu/mckusick94fsck.html</a>
</pre>
<hr>
<!-- Created: Wed Oct 24 11:51:02 CEST 2007 -->
<!-- hhmts start -->
Last modified: Thu Oct 25 01:01:07 CEST 2007
<!-- hhmts end -->
</body>
</html>