escola universitÀria d‟enginyeria tÈcnica de...

ESCOLA UNIVERSITÀRIA D‟ENGINYERIA

TÈCNICA DE TELECOMUNICACIÓ LA SALLE

TREBALL FI DE CARRERA

ENGINYERIA TÈCNICA EN INFORMÀTICA DE SISTEMES

ALUMNE PROFESSOR PONENT

Oriol Martí Agustí Xavier Canaleta Llampallas

ESTUDI DEL SISTEMA DE

FITXERS REISERFS

ACTA DE L'EXAMEN DEL TREBALL FI DE CARRERA

Reunit el Tribunal qualificador en el dia de la data, l'alumne

D. Oriol Martí Agustí

va exposar el seu Treball de Fi de Carrera, el qual va tractar sobre el tema següent:

ESTUDI DEL SISTEMA DE FITXERS REISERFS

Acabada l'exposició i contestades per part de l'alumne les objeccions formulades pels Srs. membres del tribunal, aquest valorà l'esmentat Treball amb la qualificació de

Barcelona,

VOCAL DEL TRIBUNAL VOCAL DEL TRIBUNAL

PRESIDENT DEL TRIBUNAL

Estudi del Sistema de Fitxers ReiserFS

Abstract

Aquest treball pretén fer un estudi, disseny i implementació d‟una eina docent que ajudi

a l‟estudiant a entendre el funcionament d‟un sistema de fitxers específic en profunditat.

En aquest cas es centra en el sistema de fitxers ReiserFS per a Linux i donar suport a

l‟assignatura de sistemes operatius mitjançant una aplicació docent que doni una visió a

nivell de programació.


Resum

Aquest treball pretén fer un estudi dels sistemes de fitxers de Linux, ens centrarem en

un sistema de fitxers ReiserFS que va integrar funcionalitats que més endavant van ser

usades per altres sistemes de fitxers.

També farem una referència als sistemes operatius per a situar-nos, on es troba el

sistema de fitxers en el sistema operatiu i de quines altres capes esta compost.

L‟estudi pretén donar més informació d‟alguns sistemes de fitxers que han aparegut, la

importància que ha significat l‟aparició del ReiserFS, mes enllà d‟un sistema que

implementa journaling i una comparativa entre els sistemes de fitxers per Linux.

El treball també consta d‟una part de documentació dels orígens d‟aquest sistema de

fitxers, les noves funcionalitats que va incorporar i una mirada al futur als nous sistemes

de fitxers que estan sortint i sortiran en l‟actualitat.

A continuació analitzarem totes les parts d‟aquest sistema de fitxers part per part i

profunditat de programador per entendre tot el seu funcionament tant a l‟hora

d‟emmagatzemar les dades com les eines per organitzar-les.

Per acabar implementarem la nostra eina docent i la compararem amb altres aplicacions

semblants, la intenció d‟aquesta aplicació docent creada amb la intenció d‟ajudar als

alumnes de l‟assignatura de sistemes operatius, és que mitjançant aquesta eina i altres

eines ja creades en altres TFC ( ext2 i FAT16) , tinguin una visió més àmplia dels

sistemes de fitxers i les diferents funcionalitats.


Índex

1.Introducció ................................................................................. 4

1.1 Enfocament del treball ......................................................................... 4

1.2 Objectius .............................................................................................. 4

1.3 Estructura de la memòria ..................................................................... 5

2.Descripció de l’entorn ............................................................... 6

2.1. Introducció als sistemes operatius ...................................................... 6

2.2. Introducció als sistemes de fitxers ...................................................... 7

2.3. Origen de ReiserFS ............................................................................. 8

2.4. Funcionalitats de ReiserFS ................................................................. 8

2.5. Nous sistemes de fitxers ................................................................... 10

2.6 Evolució del Sistemes de Fitxers ....................................................... 11

2.6.1 Sistemes de Fitxers “Prehistòrics” ................................................................. 11

2.6.2 CP/M .............................................................................................................. 11 2.6.3 Temps de FAT ............................................................................................... 12

2.6.4 HFS ................................................................................................................ 13 2.6.5 Sistemes de Fitxers Amiga ............................................................................ 13

2.6.6 Sistemes de Fitxers Unix i Linux .................................................................. 14 2.6.6.1 Minix .................................................................................................. 14 2.6.6.2 EXT2 .................................................................................................. 15

2.6.6.3 ReiserFS ............................................................................................. 15 2.6.6.4 EXT3 .................................................................................................. 15 2.6.6.5 JFS ...................................................................................................... 16

2.6.6.6 XFS ..................................................................................................... 16 2.6.6.7 Reiser4 ................................................................................................ 16

2.6.7 IBM i Microsoft ............................................................................................. 17 2.6.7.1 OS2/2 i HPFS ..................................................................................... 17

2.6.7.2 NTFS .................................................................................................. 17 2.6.8 ZFS ................................................................................................................ 18 2.6.9 Figura de la evolució dels sistemes Linux. .................................................... 19

3.Estructura física de dades ...................................................... 20

3.1 SuperBlock ......................................................................................... 20

3.2 Bitmap Block ..................................................................................... 23

3.3 Arbre del Sistema de Fitxers .............................................................. 25

3.3.1 Block Header ................................................................................................. 26 3.3.2 Key Block ...................................................................................................... 26

3.3.2.1 Key versió 1 ........................................................................................ 27


3.3.2.2 Key versió 2 ........................................................................................ 27 3.3.3 Tipus de Node ................................................................................................ 28

3.3.3.1 Node Intern ......................................................................................... 28 3.3.3.2 Node Fulla .......................................................................................... 29

3.3.4 Items .............................................................................................................. 30 3.3.4.1 Stat items ............................................................................................ 30 3.3.4.2 Directory Ítems ................................................................................... 32 3.3.4.3 Direct Ítems ........................................................................................ 33 3.3.4.4 Indirect Ítems ...................................................................................... 34

3.4 Journal ................................................................................................ 35

3.4.1 Journal Header ............................................................................................... 35

3.4.2 Transaccions .................................................................................................. 36 3.4.2.1 Description bloc .................................................................................. 36 3.4.2.2 Commit bloc ....................................................................................... 38

4.Explicació comandes bàsiques ............................................... 40

4.1. Llistat root ......................................................................................... 40

4.2. Arbre de directoris ............................................................................ 41

4.3. Mostrar el contingut d‟un fitxer ........................................................ 42

4.3.1 Fitxer petit (direct item) ................................................................................. 43 4.3.2 Fitxer gran (indirect item) ............................................................................. 44

4.4. Creació d‟una carpeta ....................................................................... 46

4.5. Creació d‟un fitxer ............................................................................ 47

4.6. Esborrat d‟un fitxer ........................................................................... 48

4.7. Esborrat d‟un directori ...................................................................... 49

5.Aplicacions similars ................................................................ 50

5.1.RFSTOOL .......................................................................................... 50

5.2.UFS Explorer Batch ........................................................................... 51

6.Aplicació resiserfs_rdr ............................................................ 52

6.1. Introducció ........................................................................................ 52

6.2. Anàlisi requisits ................................................................................ 52

6.2.1. Requisits funcionals ...................................................................................... 52 6.2.2. Requisits usabilitat ........................................................................................ 53

6.3. Decisions disseny .............................................................................. 53

6.3.1. Entorn execució ............................................................................................ 53 6.3.2. Entorn programació ...................................................................................... 53


6.4. Anàlisi funcional ............................................................................... 54

6.4.1. Modelat estàtic .............................................................................................. 54 6.4.1.1. Diagrama de casos d‟ús ..................................................................... 54 6.4.1.2. Diagrama de classes........................................................................... 58

6.4.2. Modelat dinàmic ........................................................................................... 64

6.5. Proves realitzades ............................................................................. 64

6.6. Posada en explotació ......................................................................... 65

7.Manual de funcionament ........................................................ 66

7.1 Partició ReiserFs ................................................................................ 66

7.1.1 Creació de la partició ReiserFS ..................................................................... 66

7.1.2 Muntar partició en Linux ............................................................................... 66

7.2 Execució del programa ...................................................................... 67

7.2.1 Contingut Superblock .................................................................................... 68

7.2.2 Contingut Bitmap Block ................................................................................ 69

7.2.3 Arbre de directoris ......................................................................................... 70 7.2.4 Journal ........................................................................................................... 71

8.Cost realització projecte ......................................................... 75

9.Conclusions .............................................................................. 76

10.Línies de futur ....................................................................... 77

11.Bibliografia ............................................................................ 78


Índex de figures Figura 1. Model 4 capes d‟un sistema operatiu [1] .......................................................... 6 Figura 2. Floppy Disck amb FAT ................................................................................... 12

Figura 3. Piscines d'emmagatzemament, ZFS [2] .......................................................... 18 Figura 4. Evolució dels sistemes Linux .......................................................................... 19 Figura 5. Imatge d‟una partició ReiserFS ....................................................................... 20 Figura 6. SuperBlock ...................................................................................................... 20 Figura 7. Part del bitmap bloc del journal ...................................................................... 23

Figura 8. Part d‟un bitmap bloc de dades ....................................................................... 24 Figura 9. Block Header ................................................................................................... 26

Figura 10. Key Versió 1 ................................................................................................. 27

Figura 11. Key Versió 2 ................................................................................................. 27 Figura 12.Esquema d'un node intern .............................................................................. 28 Figura 13. Camps del Node Intern.................................................................................. 28 Figura 14. Camps del Punter .......................................................................................... 28 Figura 15. Esquema d'un node fulla ............................................................................... 29

Figura 16. Camps Item Header ....................................................................................... 29 Figura 17.Stat Item i direct item ..................................................................................... 30 Figura 18. Posició dels bytes en un stat item versió 1 [3] .............................................. 30 Figura 19. Estructura d'un Stat item versió 2 ................................................................. 31

Figura 20. Directory Item ............................................................................................... 32 Figura 21. Capçalera d'un item de directori .................................................................... 32

Figura 22. Exemple d‟ítem directe ................................................................................. 34 Figura 23. Fitxer amb item indirecte .............................................................................. 34

Figura 24. Journal del sistema ReiserFS ........................................................................ 35 Figura 25. Journal Header .............................................................................................. 35 Figura 26. Esquema d‟una Transacció ........................................................................... 36

Figura 27. Description Block.......................................................................................... 37 Figura 28. Modificació del Superblock desprès d‟una transacció .................................. 38

Figura 29. Commit Block ............................................................................................... 39 Figura 30. Camí cap al Root node .................................................................................. 40 Figura 31. Llistat del directori de root ............................................................................ 41 Figura 32. Contingut del directori arrel. ......................................................................... 41

Figura 33. Funcions de hash i keys dels elements .......................................................... 42 Figura 34. Arbre de directoris ........................................................................................ 42

Figura 35. Root node ...................................................................................................... 43 Figura 36. Item del Fitxer i contingut. ............................................................................ 44 Figura 37.Root node fitxer indirecte .............................................................................. 44 Figura 38.Fitxer Indirecte ............................................................................................... 45 Figura 39. Part del bloc 8704 ......................................................................................... 46

Figura 40. Un disc local consultat amb RFSTOOL [4] .................................................. 50 Figura 41. Exemple UFS Explorer Batch [5] ................................................................. 51 Figura 42. Diagrama casos d'ús ...................................................................................... 54 Figura 43. Diagrama de classes ...................................................................................... 58

Figura 44. Classe Program ............................................................................................. 58 Figura 45. Classe principal ............................................................................................. 59 Figura 46.Classe info_superbloc .................................................................................... 59

Figura 47.Classe superblock ........................................................................................... 60 Figura 48. Classe Bitm_bloc .......................................................................................... 60


Figura 49. Classe ItemTreeAux ...................................................................................... 61 Figura 50. Formulari de L'arbre de directoris ................................................................. 61 Figura 51. Classe journal ................................................................................................ 62 Figura 52. Classe frmRealBlocks ................................................................................... 62

Figura 53.Classe frmCommitBlock ................................................................................ 63 Figura 54. Classe frmDescriptionBlock ......................................................................... 63 Figura 55. Diagrama de seqüència d'obrir una imatge ReiserFS .................................... 64 Figura 56. Finestra Principal ReiserFs_reader ............................................................... 67 Figura 57. Informació del Superblock ............................................................................ 68

Figura 58. Superblock valors nivell de bytes ................................................................. 68 Figura 59. Bitmap Block ................................................................................................ 69 Figura 60. Propietats del fitxer ....................................................................................... 70

Figura 61. Contingut d'un fitxer ..................................................................................... 71 Figura 62. Journal ........................................................................................................... 72 Figura 63.Formulari del Description Block .................................................................... 73 Figura 64. Formulari de Blocs Modificats...................................................................... 74

Figura 65.Formulari del Commit Block ......................................................................... 74


Índex de taules

Taula 1. Explicació dels diferents camps del SuperBlock............................................. 21

Taula 2. Offset i numero de bytes dels camps del SuperBlock ...................................... 22 Taula 3. Localització dels blocs de bitmap..................................................................... 24 Taula 4. Camps Block Header ........................................................................................ 26 Taula 5. Camps de la Key versió 1 ................................................................................. 27 Taula 6. Camps de la Key versió 2 ................................................................................. 27

Taula 7.Camps del Node intern ...................................................................................... 29 Taula 8.Camps del Item Header ..................................................................................... 29 Taula 9.Stat Item versió 1 ............................................................................................... 31

Taula 10. Descripció dels camps d'un stat item versió 2 ................................................ 31 Taula 11. Valors de tipus d'arxius .................................................................................. 32 Taula 12. Camps d'un directori item ............................................................................... 33 Taula 13. Dades del Journal Header ............................................................................... 36 Taula 14. Description bloc de la Figura 9 ...................................................................... 38

Taula 15. Dades del Commit Block................................................................................ 39 Taula 16. Especificació cas d'ús mostrar ajuda .............................................................. 55 Taula 17. Especificació cas d'ús Obrir Imatge ............................................................... 55 Taula 18. Especificacio cas d'ús Mostrar Superblock .................................................... 56

Taula 19. Especificació Mostrar BitmapBlock............................................................... 56 Taula 20. Especificació cas d'ús Mostrar Journaling ...................................................... 57

Taula 21. Especificació cas d'ús Mostrar arbre directoris .............................................. 57 Taula 22.Estimació del cost de realització de cada etapa ............................................... 75


4

1.Introducció

1.1 Enfocament del treball

Aquest treball esta enfocat com ha material de suport per a l‟assignatura de sistemes

operatius que es cursa a 3r d‟informàtica, en l‟apartat de sistemes de fitxers.

El Reiserfs és una eina del sistema operatiu pionera en implementar un sistema de

journaling o “diari” per a contrarestar la pèrdua d‟informació en front de caigudes

fortuïtes del sistema. En aquest treball no veurem tot el funcionament del ReiserFS, sinó

que inicialment ens limitarem a veure com organitza les dades i com accedeix a elles,

les diferents eines i mètodes que empleades per aquest sistema, com gestiona d‟espai

lliure

A continuació explicarem una mica dels sistemes de fitxers, per entendre com s‟ha

arribat a desenvolupar el ReiserFS i perquè va caldre implementar un sistema de

journaling. Tot seguit analitzarem les línies de futur, l‟evolució de ResiserFs, el Reiser4

i les millores que implementa, i també altres sistemes d‟arxius importants com son el

ext3, XFS, JFS.

Un cop ja estem introduïts en el ReiserFS continuarem amb l‟estudi en detall de les

seves estructures internes, el Superblock, Bitmap Bloc, l‟arbre S+ on es guarda tota la

informació i el journaling. Aquesta última la part mes innovadora.

Posteriorment s‟explicarà el comportament bàsic del sistema de fitxers, mostrar l‟arbre

de directoris, com els organitza el contingut d‟un directori, i com els esborrarà.

Per acabar un estudi de les diferents eines que ja existeixen, passarem a detallar tot el

procés de creació de la nostra eina docent començant per l‟anàlisi de requisits, passant

per les decisions de disseny així com l‟anàlisi funcional per tal d‟acabar finalment en la

fase de proves i la posterior posada en explotació de l‟aplicació.

1.2 Objectius

Els objectius que aquest treball pretén assolir son els següents:

Entendre que és un sistema de fitxers i el paper que desenvolupa en el sistema

operatiu.

Entendre el funcionament dels sistemes de fitxers.

Entendre el funcionament del sistema de fitxers ReiserFS.


5

Entendre el funcionament del journaling que avui en dia esta estès a molts

sistemes de fitxers a part de sistemes gestors de bases de dades.

1.3 Estructura de la memòria

L‟estructura d‟aquest treball esta dividida en 3 parts:

Descripció dels sistemes de fitxers.

Estudi del funcionament de ReiserFS.

Disseny, implementació de l‟eina docent.


6

2.Descripció de l’entorn

Per entendre l‟entorn en el que treballarem hem de fer una introducció del que entenem

per sistema operatiu i de quines parts esta format, i en quina es troba el sistema de

fitxers.

2.1. Introducció als sistemes operatius

Un sistema operatiu és un conjunt de programes d‟un computador destinat a permetre

una administració eficient dels seus recursos. Comença a treballar quan es carrega a

memòria un programa específic, que s‟executa al iniciar la màquina, gestiona el

hardware de la maquina des dels nivells més bàsics, mantenint una interfície amb

l‟usuari.

En la figura següent podem veure les 4 capes que intervenen en un sistema operatiu.

Figura 1. Model 4 capes d’un sistema operatiu [1]

El sistema de fitxers es troba en la capa “Gestió d‟informació”, a continuació definirem

les diferents capes i a què es dedica cada una.

Interfície amb l’usuari : és la part del sistema operatiu que permet comunicar-

se amb l‟usuari, de tal manera que es poden carregar programes, accedir a

fitxers. Existeixen tres tipus bàsics d‟interfícies, les que es basen en línia de

comandes, les que utilitzen menús i les interfícies gràfiques d‟usuari.

Gestió d’informació: un sistema d‟informació que conté els programes

d‟administració de fitxers que controlen la creació, esborrat i accés de fitxers de

dades i de programes. També implica mantenir un registre de la ubicació física


7

dels fitxers en els dispositius d‟emmagatzemament. En aquest nivell és on és

centre aquest treball, manipulació i tractament de la informació de l‟usuari.

Gestió de Memòria: Els programes d‟administració de tasques d‟un sistema

operatiu administren la realització de les tasques informàtiques dels usuaris. Els

programadors controlen quines àrees tenen accés a la CPU i per a quan de

temps. Les funcions d‟administració de tasques poden distribuir una part

específica del temps de la CPU per a una tasca en particular, e irrompre la CPU

en qualsevol moment per substituir-la per una tasca de major prioritat. Un

exemple serien les tècniques de scheduling.

Gestió d’Entrada/Sortida: Serveix per administrar els recursos hardware i de

xarxes d‟un sistema informàtic, com la CPU, memòria, dispositius

d‟emmagatzemament secundari i perifèrics d‟entrada i de sortida.

2.2. Introducció als sistemes de fitxers

Un sistema de fitxers és l‟estructura que emmagatzema la informació en els discs. Un

sistema de fitxers és una estructura lògica que és la més adequada pel maneig de dades

en base a les característiques del hardware disponible. Per aquesta raó, el seu estudi es

troba en la frontera entre el hardware i el software.

El disseny del sistema de fitxers té una gran influencia en l‟eficiència, seguretat,

flexibilitat i capacitat de creixement dels emmagatzemaments en disc, i per tant, en el

rendiment del propi Sistema Operatiu. Una de les seves funcionalitats més importants

és la manipulació de les dades.

Precisament el SO Unix va néixer a partir de la idea de crear un sistema de fitxers que

permetés als usuaris GE 635 dels Laboratoris BELL & AT&T, treballar simultàniament

sense interferir-se.

En els sistemes de fitxers hi ha dos tipus de dades:

Les Dades, que és la informació que l‟usuari guarda ( fitxers, directoris,

programes...)

Les Metadades, que son les estructures que organitzen e indexen les dades, en

aquest punt és on resideix la importància del resultat final del sistema de fitxers.

En el cas del ReiserFs, és un sistema de fitxers implementat en Linux, un

sistema desenvolupat per un estudiant (Linux Benedict Thorwald). Aquest sistema va

ser inspirat per Minix, un dialecte de UNIX i posteriorment convertit en un SO

"freeware" pel seu creador i ràpidament "adoptat" per la comunitat informàtica

internacional, amb el temps se li han afegit infinitat d‟opcions, utilitats i millores, això

ha fet que s‟hagi convertit en un sistema ràpid, fiable i molt optimitzat.


8

Amb el temps s‟ha dotat Linux de diferents sistemes de fitxers, de forma que els

usuaris poden escollir entre una amplia varietat d‟opcions i tenir a accés a una gran

quantitat de formats. El sistema és molt flexible, permetent inclòs muntar un sistema de

fitxers a partir d‟una arrel amb unitats físiques amb sistemes diferents entre si, més

endavant en el punt 2.6 farem un estudi de la evolució dels sistemes operatius i dels

sistemes de fitxers.

2.3. Origen de ReiserFS

ReiserFS és un sistema de fitxers de propòsit general, dissenyat e implementat per un

equip de l‟empresa Namesys, liderat per Hans Reiser. Actualment suportat per Linux i

existeixen plans futurs per incloure‟l en altres sistemes operatius.

També té suport amb Windows no oficial de manera inestable i rudimentària. A partir

de la versió 2.4.1 del nucli de Windows, ReiserFS va ser el primer sistema de fitxers en

incorporar el journal al nucli estàndard. També és el sistema d‟arxius per defecte a

vàries distribucions, com SuSE ( excepte en openSuSE 10.2 que el seu format per

defecte es ext3), Xandros, Yoper, Linspire, Kurumin Linux, FTOSX, Libranet i

Knoppix.

Les tres funcionalitats principals del sistema ReiserFS són:

Journaling, protegeix del risc de corrupció del sistema d‟arxius

Repartiment amb el sistema de fitxers muntat i desmuntat. Podem augmentar la

mida del sistema mentre el tenim muntat i desmuntat. Per a disminuir-lo,

únicament es permet estant desmuntat.

Tail packing, és un esquema per reduir la fragmentació interna.

2.4. Funcionalitats de ReiserFS

Una de les raons pel qual el ReiserFs va ser tan important va ser la incorporació del

journaling, que és un mecanisme per al qual un sistema informàtic pot implementar

transaccions.

El journaling es basa en journal en el que s‟emmagatzema la informació necessària per

restablir les dades afectades per la transacció en cas que aquesta sigui errònia.

El procediment és el següent:

1. Es bloquegen les estructures de dades afectades per la transacció per a

que cap altre procés pugui modificar-les mentre dura la transacció.


9

2. Es reserva un recurs per emmagatzemar el journal. En general solen ser

blocs de disc, de manera que si el sistema es para de forma abrupta ( tall

elèctric, fallada del sistema operatiu, etc..) el journal segueixi disponible

un cop reiniciat el sistema.

3. S‟efectuen una a una les modificacions en les estructures de dades. Per a

cada una:

S‟apunta en el journal com desfer la modificació i s‟assegura de

què aquesta informació s‟escriu físicament al disc.

Es realitza la modificació

4. Si en qualsevol moment es vol cancel·lar la transacció es desfan els

canvis un a un llegint i esborrant del journal

5. Si tot és correcte, s‟elimina el journal i es desbloquen les estructures de

dades afectades.

Les aplicacions mes freqüent dels sistemes de journaling s‟utilitzen per implementar

transaccions de sistemes de bases de dades i, mes recentment, per evitar la corrupció de

les estructures de dades en la que es basen els sistemes de fitxers moderns.

En el cas dels sistemes de fitxers, el journaling sol limitar les operacions que afecten a

les estructures que mantenen informació sobre:

Estructures de directoris ( S+Tree cas ReiserFS)

Blocs lliures de disc

Descriptors d‟arxius ( Mida, data, ...)

Una de les funcions del journaling dels sistemes d‟arxius és evitar les comprovacions de

disc que efectuen els sistemes al apagar-se de forma abrupte, ja que el sistema al posar-

se en marxa només haurà de desfer el journal per tenir un sistema coherent de nou.

Una altra funcionalitat del sistema ReiserFs és el reparticionament amb el sistema

muntat o desmuntat, Es pot augmentar la mida del sistema online o offline. Per a reduir-

lo només es permet offline. Namesys ens proporciona les eines per aquestes operacions,

inclòs es poden utilitzar sota gestors de volums lògics com per exemple LVM o EVMS,

que es detallaran a continuació.

LVM és una implementació d‟un administrador de volums pel kernel Linux. No

implementa RAID1 o RAID5. Inclou la gestió de volums lògics proporcionant

una visió d‟alt nivell d‟emmagatzemament d‟un ordinador, en comptes de la

tradicional visió de discs i particions, entre altres.


10

EVMS és un software de gestió de volums flexible e integrat a Linux, les

principals característiques són, primer que és compatible amb diferents sistemes

de fitxers, gestió multi disc, RAID software de tipus 0, 1, 4, 5. Pot expandir i

contraure volums i sistemes de fitxers online i offline, reorganització de blocs

erronis, entre altres.

L‟ultima funcionalitat que detallarem és el Tail packing que és un esquema per a reduir

la fragmentació interna, també anomenada Block suballocation permet que els blocs

grans que han d‟utilitzar-ne al mateix temps fent un ús eficient del "slack" al final de

fitxers llargs . Espai que d‟altra manera es desaprofitaria i quedaria com a fragmentació

interna. Se l‟anomena Tail packing, perquè intenta arrodonir aquest espai final de

diversos fitxers per formar un sol bloc.

2.5. Nous sistemes de fitxers

Amb l‟excepció d‟actualitzacions de seguretat i errors crítics, Namesys ha deixat de

banda el desenvolupament de ReiserFS( també anomenat Reiser3) per a centrar-ne el

seu successor Reiser4.

Reiser4 és un sistema de fitxers per computadors, es tracta de la versió mes recent del

sistema de fitxers ReiserFS, rescrit des de zero, desenvolupat per Namesys i patrocinat

per la DARPA i Linspire.

Actualment no es distribueix de forma conjunta amb kernel de Linux. Els programadors

del kernel Linux argumenten que Reiser4 no es regeix per la convenció de codificació

estàndard.

Millores respecte ReiserFS:

Journaling mes eficient gràcies a la tècnica de "wandering log".

Suport mes eficient de fitxers petits, en termes d‟espai en disc i gràcies a "tail

packing".

Optimització dinàmica de l‟estructura del disc mitjançant "allocate-on-flush",

anomenat "delayed allocation" en el sistema de fitxers.

Transaccions atòmiques

Integració de metadades en l‟espai de noms del sistema de fitxers

En qüestió de rendiment Reiser4 utilitza dancing trees, on els inodes poc poblats no es

fusionen fins que les guarda a disc, aquest sistema permet crear fitxers i directoris sense

perdre temps i espai mitjançant blocs de mida prefixada.


11

2.6 Evolució del Sistemes de Fitxers

A continuació explicarem la evolució dels Sistemes de Fitxers, perquè va ser necessària

aquesta evolució i mostrarem un figura on es veu aquesta evolució.

2.6.1 Sistemes de Fitxers “Prehistòrics”

La companyia Digital Equipment Corporation, va donar nom al primer sistema físic per

emmagatzemar els fitxers dels DECTape. Eren cintes que actuaven com disc durs molt

lents, aquets emmagatzemaven 184 Kilobytes, de dades per cinta.

Es considerava mini computadora, ja que encara que fos de la mida d'una nevera, era

més petit que les computadores behemoth de IBM, que ocupaven sales senceres.

Després del invent del transistor i del circuit integrat (silicon chip) va permetre la

minimització. DEC es va quedar extingit, mentre que la resta del món es va canviar a

microcomputadores.

2.6.2 CP/M

Al 1973 Gary Kildall va inventar un programa anomenat “Control Program for

Microcomputers” que el permetia guardar fitxers i fer funcionar programes des de un

Shugart floppy drive, en el seu ordinador de casa, aquest tenia un sistema de fitxers,

però no tenia nom.

Aquest sistema estava basat en una jerarquia de “flat” sense directoris, Els noms dels

fitxers tenien un límit de 8 caràcters, més tres caràcters d‟extensió que determinaven el

tipus de fitxers.

El motiu per al qual Gary va fer aquest programa va ser, que no volia conduir fins al

treball cada dia, es curiós que la peresa pot ser en algunes ocasions una cosa

increïblement intel·ligent.

Tim Patterson, al 1977, va escriure el seu propi sistema operatiu, QDOS (Quick & Dirt

Operating Sistem), ja que era una copia “bruta” i “ràpida” del sistema CP/M, el sistema

de fitxers era lleugerament diferent, encara que era la mateixa idea i tampoc tenia

directoris.

Es va basar en un programa de Microsoft anomenat Microsoft Disk Basic, on es podia

copiar els fitxers en floppy disks. Utilitzava una organització anomenada File

Allocation Table, així que el van anomenar FAT.

Aleshores Bill Gates va comprar el QDOS de Patterson, per $50.000, i el va renombrar

a MS-DOS.


12

2.6.3 Temps de FAT

El sistema FAT descrivia quines àrees del disc es guardaven els fitxers, a quines els

espais lliures i quines estaven en mal estat, “bad sectors”. Ja que el floppy disk tenia poc

espai, la taula havia de ser petita, per mantenir-la la taula es dividia en clústers (grups de

sectors), la primera versió de FAT, es va anomenar FAT-12, perquè utilitzava un

número de 12 bits per comptar els clústers.

Figura 2. Floppy Disck amb FAT

Aquest discs no tenien intencionalitat de incorporar directoris o optimització de

emmagatzemar el fitxers, en part aquests discs eren simplement per guardar pocs fitxers.

En canvi IBM estava a punt d‟alliberar el PC-XT amb un disc opcional de 20 MB, en

aquella època un gran espai i aleshores va significar que la FAT necessitaria un sistema

per emmagatzemar els fitxers en una jerarquia adequadament. Per MS-DOS 2.0, van

afegir els directoris que els hi van assignar la contrabarra „\‟ com a separador

“C:\MYFILES\NOTES”, en aquest cas no es podia usar la „/‟ ja que s‟usava per altres

opcions, com ara a l‟hora de formatjar el floppy disk i afegir fitxers “FORMAT A: /S” i

es va anomenar C, perquè A i B estaven reservats per el primer i segon floppy disk, que

tothom en aquell moment tenia i es va quedar com un estàndard.

En aquest moment el FAT-12 queda obsolet, així que Microsoft va treure una versió de

16 bits en DOS 3.31, alliberada en 1987. Tenia clústers de 32KB i podia adreçar 216,

per una mida de disk de 2 GB.

Aquí podien aparèixer problemes de memòria, apareix el concepte de fragmentació

interna.


13

Per el 1995, els discs es feien més grans i el límit de 8.3 era un problema que havia de

desaparèixer.

Per solucionar aquests problemes, Microsoft va introduir la FAT-32 amb 8TB de límit i

amb una habilitat per donar noms llargs als fitxers, aquesta habilitat era VFAT. Podia

tenir qualsevol nom fins a 255 caràcters i la feia ajustar-se al 8.3, consistia en qualsevol

nom, per exemple “nom_de_fitxer_llarg.txt” el guardava com “nom_d~1.TXT” les

lletres pendents quedaven guardades com a directoris fantasma que estaven marcades en

els atributs de metadades com Volum Label, System, Hidden, i Read-Only.

2.6.4 HFS

Al 1984 Macintosh va aparèixer a un únic floppy drive, quan la gent començava a

utilitzar els discs durs. El sistema de fitxers s‟anomenava MFS (Macintosh File

System). Tenia directoris i al mateix temps no en tenia. L‟usuari podia crear directoris

gràfics i podia deixar fitxers, però no es mostraven, tot estava en un “Directori Buit”,

que s‟anava esborrant i creant a cada modificació, per a un floppy disk funcionava

correctament però per als discs durs es realentitzava molt. Els noms per contra es va

permetre que poguessin tenir 63 caràcters.

El MFS va ser reemplaçat al 1985 per un sistema que tenia jerarquia de directoris, per

això es va anomenar Hierarchal File System, o HFS. En aquesta ocasió els noms

estaven limitats a 31 caràcters. La informació del directori, fitxer i el espai lliure es

guardava en un arbre B, aquesta estructura permetia una ordenació ràpida. HFS emprava

clúster de 512KB amb punter de 16 bits, i la mida màxima del disc dur es limitava a

32GB.

Les últimes versions arribaven a punters de 32 bits, i això feia arribar a 2TB de

indexació.

El MFS i HFS van introduir una innovació per la manipulació dels fitxers, anomenada

“fork”. En comptes d‟emmagatzemar les metadades en llocs separats, en el cas de HFS

feia que cada fitxer en creava dos, el fitxer (data fork) i l‟invisible (resource fork) que

contenia informació estructurada, incloent informació sobre el fitxer, per exemple la

icona. Aquests forks tenien utilitat mes enllà de les metadades.

El sistema HFS utilitzava un codi de quatre lletres per a definir la extensió en comptes

de les tres. Aquests s‟emmagatzemaven en les metadades del sistema de fitxers, on es

tractava com si fos la data de creació del fitxer.

2.6.5 Sistemes de Fitxers Amiga

Amiga, va sortir un any després que el Macintosh, tenia capacitats multimèdia que eren

avançades al seu temps. En canvi, el sistema de fitxers era una de les parts més dèbils,

degut a la pressió per treure el AmigaOS al mercat, el sistema de fitxers venia del

TripOS, utilitzava blocs de 512KB, però reservava 24KB de cada bloc per a les

Metadades.


14

Aquest sistema el van anomenar OFS (Old File System) per els enginyers d‟Amiga, que

el van reemplaçar tan aviat com va ser possible

El FFS (Fast File System) va sortir al mercat l‟any 1987 en els sistemes Amiga 500,

2000, AmigaOS 1.3. La principal diferència era que les metadades es van treure dels

blocs individuals a un bloc a part. Els noms dels fitxers estaven limitats a 32 caràcters

igual que el HFS

El sistema operatiu d‟Amiga va ser dissenyat de nou principalment per a que pogués

suportar els dos sistemes OFS i FFS, però també per a qualsevol altre sistema de fitxers

que mantingués el format, es a dir, qualsevol podia escriure el seu propi sistema de

fitxers. Gràcies això va donar com a resultat el PFS (Professional File System) i SFS

(Smart File System). Per al sistema operatiu Amiga OS4, va sortir el FFS2 que

acceptava noms de fitxers fins 105 caràcters de longitud.

2.6.6 Sistemes de Fitxers Unix i Linux

El sistema UFS (FFS) va començar com un sistema multi usuari time-sharing. Unix va

fer tot tipus de estàndards de com els usuaris haurien d‟emmagatzemar els fitxers. El

UFS o també conegut com Barkley Fast File System, es va convertir en el estàndard

quan els programadors de la Universitat de Barkley van desenvolupar una versió

millorada que el UFS.

El sistema es case-sensitive, això vol dir que diferencia entre minúscules i majúscules,

per exemple FITXER.TXT es un fitxer diferent que Fitxer.txt.

Com a altres sistemes de fitxers, la informació esta emmagatzemada en components

anomenats blocs. La mida de bloc estava estandarditzada a 8KB, perquè una mida més

gran podia significar una pèrdua d‟espai important, BSD va implementar un algoritme

anomenat bloc suballocation, on els blocs que no estan plens podrien emmagatzemar-ne

en un únic bloc.

Unix va dominar el mercat servidors abans de ser substituït per clon anomenat Linux.

2.6.6.1 Minix

Minix és el sistema de fitxers natiu del SO que te el mateix nom. Va ser el primer

disponible per Linux. Encara que Minix és un sistema dirigit a la docència que a

l‟explotació comercial. Encara se segueix utilitzant en disquets i en unitats de RAM.

"As most of you know, for me MINIX is a hobby, something that I do in the evening

when I get bored writing books and there are no major wars, revolutions, or senate

hearings being televised live on CNN. My real job is a professor and researcher in the

area of operating systems"...


15

..."I think the real issue is something else. I've been repeatedly offered virtual memory,

paging, symbolic links, window systems, and all manner of features. I have usually

declined because I am still trying to keep the system simple enough for students to

understand".

Andrew S. Tanenbaum en "Linus vs. Tanenbaum"

2.6.6.2 EXT2

ext2 és actualment una segona "extensió" del sistema Minix, és un sistema de fitxers

d‟alt rendiment que, en qüestió de velocitat i consum de CPU, presenta les millors

prestacions entre els sistemes suportats per Linux, tot i així té els seus avantatges i

desavantatges. El principal problema de ext2 és que utilitza una estructura estàtica i poc

espai per anotar particions de gran mida, els límits són considerables (32768

subdirectoris en cada directori, de 10k a 15k fitxers per directori i 4 TeraBytes de

capacitat). En canvi la principal limitació és que les metadades de llistes encadenades no

és adequada per volums molt grans.

2.6.6.3 ReiserFS

ReiserFS és un sistema de fitxers que implementa el journaling (apartat 2.3) de codi

lliure i disponible en la majoria de distribucions de Linux, dissenyat per Hans Reiser i

col·laboradors en Namesys. És un sistema que presenta unes excel·lents prestacions en

la manipulació de fitxers grans, encara que una de les seves característiques distintives

és la maniobrabilitat per a manipular infinitat de fitxers petits. La filosofia d‟aquest

sistema de fitxers es "Els fitxers petits estimulen la senzillesa del codi". El sistema

ReiserFS té un factor de 8 a 15 cops mes ràpid que ext2 a l‟hora de manipular els fitxers

de menys 1KB, i amb la configuració adequada, pot emmagatzemar un 6% més de

dades que ext2 en el mateix dispositiu. En comparació amb ext2 en comptes d‟utilitzar

clústers de mida fixa, el disseny de ReiserFS permet utilitzar l‟espai exacte que

necessita. Les metadades estan organitzades en un arbre ordenat (B+Tree o S+Tree) que

a mes de gestionar les metadades, emmagatzema i comprimeix les parts dels fitxers que

no arriben a ocupar un clúster ( Tail packing).

2.6.6.4 EXT3

Ext3 es la extensió de ext2, implementa el journaling el qual ajuda a la recuperació del

sistema, es un dels sistemes de fitxers usats per defecte per Linux, un dels avantatges

mes significatius es que permet la evolució de ext2 a ext3 sense pèrdua de informació

en el disc dur. Es considerat un dels sistemes mes segur a pesar de la seva simplicitat.

Les millores de ext3 respecte ext2 son les següents:

un sistema de journaling

permet augmentar la mida del sistema de fitxer online.

utilitza un Htree per indexar directoris grans.


16

Diferents nivells de journaling (journaling - lowest risk, ordered - medium risk,

writeback - highest risk)

Per contra els seus desavantatges son:

Fragmentació

Compressió

Límits de mida

No té checksum en el journal.

2.6.6.5 JFS

JFS a l‟igual que ReiserFS i ext3 és un sistema de fitxers "journalista". Desenvolupat

inicialment per IBM per al seu sistema operatiu OS/2 Warp, el seu codi ca ser

incorporat al Open Source Consortium a principis del 2000 i portat a Linux poc desprès.

És un sistema molt adequat per a entorns empresarials que permet volums molt grans i

utilitza tècniques avançades per a millorar el rendiment. Una de les característiques és

que utilitza un sistema d‟assignació dinàmica per als inodes, que assigna o allibera

l‟espai, segons les necessitats. L‟avantatge al contrari que en altres sistemes, no és

necessari una estimació prèvia de l‟espai que es reservarà als inodes a l‟hora de crear el

sistema de fitxers.

2.6.6.6 XFS

XFS és un sistema de fitxers implementat per la companyia Silicon Graphics,

inicialment va ser dissenyat pels seus sistemes IRIX, però va fer una versió per Linux.

Es tracta d‟un sistema journalista d‟altes prestacions, suporta un diari de bitàcola,

"granges" de discs (disk farms) extremadament extenses. Un d‟aquests sistemes té la

capacitat de gestionar 18000 Petabytes i un sol fitxer pot arribar als 9000 Petabytes.

2.6.6.7 Reiser4

Evolució del ReiserFS, aquesta evolució presenta un sistema de fitxers molt ràpid, a

més aquest sistema presenta una característica important atomicitat, les operacions

internes del sistema de fitxers es fan, o no es fan, d‟aquesta manera no es corrupteixen

les dades ja que s‟han implementat algoritmes que no dupliquen les dades.

Presenta una diferencia respecte al seu predecessor, dancing trees, ja que els algoritmes

per als arbres balancejats queden obsolets. Aquests arbres presentes una gran millora en

quan a crear infinitat de fitxers en un directori mentre altres sistemes de fitxers donen

problemes.

Està basat en pluggins per tant té tot de contribuïdors externs que faran que el sistema

s‟actualitzi amb innovacions.


17

2.6.7 IBM i Microsoft

IBM competia amb Microsoft per el domini dels sistemes operatius a nivell de

ordinadors personals. Però més inusual era el fet que més que una competició era

cooperació.

2.6.7.1 OS2/2 i HPFS

Amb una nova interfície gràfica, OS/2 havia de ser un sistema operatiu multi tasca, però

va tardar en arribar, tenia problemes al executar aplicacions per DOS i requeria més

RAM de la que la majoria d‟usuaris es podien permetre en aquella època. Al 1987 la

versió 1.2 va sortir al mercat i IBM va voles crear un nou sistema de fitxers per

substituir el FAT. Així va néixer High Performance File System (HPFS), escrit per un

equip dirigit per un empleat de Microsoft Gordon Letwin.

HPFS utilitzava arbres b, els noms de fitxers arribaven fins a 255 caràcters i emprava

extents. El directori de root, estava emmagatzemada en mig del disc, en comptes del

principi, per a millorar el temps d‟accés. No tenia suport de journaling, però tenia

l‟opció de forks i metadades molt extenses. Aquestes metadades van ser anomenades

Extended Attirbutes i es podia emmagatzemar inclòs en particions FAT, guarden els

atributs en fitxers anomenats EA_DATA.SF.

Quan Microsoft estava a punt de treure Windows 3, va haver problemes en la relació

entre Microsoft i IBM, Microsoft va enfocar de nou els seus esforços desprès que fos un

fracàs. En canvi IBM es va quedar el codi i va afegir un munt d‟extres d‟interfície

d‟usuaris. Va aparèixer OS/2 2.0 i la orientació d‟objectes de Shell, abans de la aparició

de Windows 95 que va enfonsar-lo. Més tard IBM va portar JFS a OS/2.

2.6.7.2 NTFS

Microsoft també sabia que el DOS necessitava un canvi, així que Bill Gates va decidir

contractar Dave Cutler, programador de DEC, aquest va agafar a tot el seu equip i va fer

un nou sistema operatiu, amb un nou sistema de fitxers, encara no tenia nom, però més

endavant se‟l va anomenar New Technology File System (NTFS), del nom del sistema

operatiu Windows NT, on NT era de New Technology. Una petita coincidència, que el

projecte de Dave Cutler a DEC fos el VMS que substituint la lletra per la següent es el

WNT.

Era un sistema de fitxers amb un volum màxim de 264

, que emmagatzemava tots els

noms de fitxers en Unicode, d‟aquesta manera qualsevol llenguatge podia llegir-lo. Els

atributs dels fitxers els van limitar a límits exagerats, des de el 1601 AD, fins a dates

posteriors al 60056 AD. La primera versió que va sortir al mercat de Windows NT es va

dir 3.1, va ser al voltant de 1993.


18

NTFS utilitzava B+Trees, incloïa journaling, també emprava opcions de seguretat ACL

(Access Control Lists, afegides al NT 3.5, 1994). NTFS té un suport de metadades molt

extens. Degut a això van haver d‟implementar un sistema de indexació que va trigar

cinc anys a tenir una interfície gràfica.

Aquest sistema guarda totes les metadades en fitxers separats, ocults, indicats amb el

nom de fitxer iniciat amb el caràcter $. En el moment que tot es guarda com a fitxer,

NTFS permet estructures que creixen dinàmicament. Resisteix la fragmentació al

implementar “Best Fit” això vol dir que no guarda la informació en el primer espai

lliure si no que busca el que millor s‟adapta en l‟espai de disc.

Per a facilitar la transició de FAT a NTFS, Microsoft proveït d‟una utilitat per usuaris

de Windows 98, que convertia de forma segura particions de FAT16 i FAT32 a NTFS.

Una cosa amb la que no estaria d‟acord sobre el NTFS era que el seu disseny era

propietat de Microsoft. D‟aquesta manera els codis de open-source van aconseguir

donar suport per a llegir la partició i més endavant, escriure. De particions NTFS des de

altres sistemes operatius. El projecte NTFS-3G permet qualsevol sistema operatiu llegir

i escriure en les particions NTFS.

2.6.8 ZFS

El sistema de fitxers Zettabyte, anunciat per al 2004, era un sistema de fitxers de 128

bytes que podia guardar fitxers des de una mida molt petita (16 exabytes) fins a fitxers

d‟una mida exagerada ( 256 zettabytes, 278

) com a màxim per a tot el sistema. El

director del projecte era Jeff Bonwick. Una particularitat es que el sistema ZFS té una

forma per tractar diverses particions, crea una especia de piscina anomenada “zpools”, i

així sembla que tots els discs durs connectats sembla que siguin part d‟una partició

gegant.

La opció del RAID fa el mateix en el sentit de que uneix tots els discs durs i pot

recuperar-se si un disc dur es danya. El sistema ZFS pot automàticament agafar petites

imatges de cada canvi fet en el sistema, salvant nomes les diferències, així les dades no

es perden mai.

Figura 3. Piscines d'emmagatzemament, ZFS [2]


19

2.6.9 Figura de la evolució dels sistemes Linux.

Figura 4. Evolució dels sistemes Linux


20

3.Estructura física de dades

Una partició del sistema Reiserfs esta composta per blocs d‟una mida fixa, aquests blocs

estan numerats de forma seqüencial començant pel bloc 0. En una partició hi ha un

número màxim de 2^32 blocs per partició.

La partició Reiserfs esta composta per:

SuperBlock, un en tota la partició.

Bitmap Block, un o més depenent de la quantitat que necessitem per adreçar tots

els blocs de la partició.

Arbre S+ pel sistema de fitxers, un arbre auto balancejat que conte tots els

directoris i fitxers de la partició.

Journal, el journal en Reiserfs és un conjunt de blocs de disc que descriu les

transaccions realitzades als sistemes d‟arxius

Un esquema lògic de una possible partició del sistema ReiserFs

Figura 5. Imatge d’una partició ReiserFS

3.1 SuperBlock

La partició comenta amb els 64kB inicials sense servir, aquest espai es deixa lliure per

possibles labels o boot loaders. Tot seguit be el Superblock, que conte tota la informació

important sobre la partició, mida del bloc, numero de blocs (mes endavant es detalla).

La quantitat de blocs que contenen el superblock difereix depenen de la mida de bloc,

però sempre comença en el 65536d.

Els camps del SuperBlock són els següents,

Figura 6. SuperBlock


21

Els camps més importants són,

Nombre de Blocs (groc) tenim 19000h en 102400d blocs

Nombre de Blocs Lliures (verd), 16FF3h en decimal 94195 blocs lliures

Numero del Bloc del root (blau) 2001h es el bloc 8193,

Numero del Bloc del journal (vermell) 42h es troba en el 66 decimal.

Mida de Bloc (Negre) 400h, equival a 1024d

Numero de Bitmaps (taronja) el D, son 13 blocs de bitmap.

Estat Partició (Morat), el estat es correcte que marca 1 igual en decimal.

A continuació es detalla l‟explicació dels diferents camps del Superblock

Nom del camp Explicació

Nombre de Blocs el número de blocs que hi ha a la partició.

Nombre de Blocs

Lliures

el número de blocs lliures que hi ha a la partició.

Numero de Bloc del

root

el número de bloc que conte el node del root.

Num. de Bloc del

Journal

el número de bloc que conte el primer node de journal

journal device és el journal device number¿?

Mida del journal mida del journal, es necessita quan usem la partició amb

altres sistemes amb un journaling diferent

Transaccions

màximes journal

Nombre de transaccions màximes que permet el journal

Journal Màgic un número aleatori

Màxims Blocs per

transacció

el nombre màxim de blocs en una transacció

Màxim temps de

commit

temps en segons de la màxima antiguitat un commit

asíncron pot ser.

Transacció més

antiga

temps en segons de la màxima antiguitat d‟una transacció

Mida de Block mida en bytes d‟un bloc

OID Mida mínim el mida màxim de cadena id d‟un objecte

OID Mida actual mida actual d‟una cadena íd d‟un objecte

Estat partició estat de la partició, vàlid (1) o error (2).

Màgic string La Màgic String de ReiserFs, ha de ser “ReIsEr2Fs”.

Codi Funció de Hash la funció de hash que s‟utilitza per ordenar els fitxers en

els directoris.

Profunditat arbre

directoris

la profunditat actual de l‟arbre

Nombre de bitmaps la quantitat de bitmaps que es necessiten per adreçar tots

els blocs del sistema de fitxers.

Versió el número de versió ReiserFS

Reservat camp reservat

Generació Inode número de l‟actua-la generació inode. Taula 1. Explicació dels diferents camps del SuperBlock


22

Tots els camps del SuperBlock, en aquesta taula es troba amb l‟offset a partir de la

posició en decimal 65536 i el número de bytes que ocupa cada camp, amb referència

dels camps més importants que s‟han detallat a la Figura 2.

Nom del camp Offset # Bytes Color

Nombre de Blocs 0 4 Groc

Nombre de Blocs Lliures 4 4 Verd

Numero de Bloc del root 8 4 Blau

Numero de Block de journal 12 4 Vermell

journal device 24 4

Mida del journal 28 4

Transaccions màximes journal 32 4

Journal Màgic 36 4

Màxims Blocs per transacció 40 4

Màxim temps de commit 44 4

Transacció més antiga 48 4

Mida de Block 50 2 Negre

OID Mida mínim 52 2

OID Mida actual 54 2

Estat partició 56 2 Morat

Màgic string 58 12

Codi Funció de Hash 70 4

Profunditat arbre directoris 74 2

Nombre de bitmaps 76 2 Taronja

Versió 78 2

Reservat 80 2

Generació Inode 82 4 Taula 2. Offset i numero de bytes dels camps del SuperBlock

Recordem que les dades es troben en l.e. ( little endian) vol dir que les dades de major

pes es troben en el byte de menys pes, és a dir, es fa un swap de les dades en

hexadecimal real.


23

3.2 Bitmap Block

Desprès del SuperBlock ve el bitmap bloc, aquest indica l‟estat dels blocs d‟informació,

amb un 1 esta ocupat i amb un 0 esta lliure, cada byte mostra l‟estat de 8 blocs. En el

cas de què els blocs no es puguin adreçar en un bitmap bloc, s‟afegiran tants blocs de

bitmap com facin falta.

Figura 7. Part del bitmap bloc del journal

En aquest cas veiem que tots els bytes estan ocupats (FF), si mirem la adreça veiem que

aquest es el primer bitmap bloc, que esta just després del superblock, aquest bitmap

sempre mapeja els blocs del journal i estan marcats com ocupats.

Per altra banda un altre bitmap bloc ja marcaria l‟estat dels seus blocs, en la figura a

continuació veurem una part d‟un bitmap bloc de dades, en aquesta figura veiem que

esta buit nomes els tres primers blocs de la partició estan ocupats

En el cas del número de blocs llegim 4 bytes, 00640000.

Separem els bytes 00 64 00 00, apliquem l.e. de tot el camp, per tant ens queda

64 00h, que convertit a decimal són el 25600 blocs.

Per a verificar que és correcte agafem la mida de bloc i apliquem la mateixa

tècnica, llegim dos bytes amb offset de 50, i obtenim 0010, els separem en

bytes 00 10, apliquem l.e. 10 00, convertim a decimal i el resultat és 4096

Bytes per Bloc.

Ara multipliquem la mida de bloc pel número de blocs ens ha de donar la mida

de la partició que en aquest cas és de 100MB.

25600 Blocs x 4096 Bytes / Blocs = 104857600 Bytes ≈ 100MB


24

Figura 8. Part d’un bitmap bloc de dades

En aquesta figura si mirem la adreça veiem que es el segon bitmap bloc, el 03 marca

que dels vuit primers blocs dels 8192 que avarca aquest bitmap, nomes estan ocupats els

3 primers (0000 0011)

Donat un número de bloc b, podem saber el seu estat com es mostra a continuació,

r div 8: byte dintre del bitmap bloc.

r mod 8: bit dintre del byte..

Els blocs de bitmap en el ReiserFS no estan consecutius, tot el contrari, després del bloc

de bitmap estan els blocs als que fa referència aquell bitmap bloc, i tot seguit el següent

bitmap bloc i els blocs, i així consecutivament.

La localització dels bitmap blocs vindrà donada, segons la mida del bloc, a continuació

tenim una taula amb alguns exemples de les mides del bloc i el número de bloc en el

que es troben els bitmap blocs.

Mida bloc (bytes) 512 1024 4096

# blocs un bitmap pot adreçar 4096 8192 32768

# bloc Superblock 128 64 16

# bloc del primer bitmap bloc 129 65 17

# bloc del segon bitmap bloc 4096 8192 32768

# bloc del tercer bitmap bloc 8192 16384 65536

Taula 3. Localització dels blocs de bitmap

b div (8 * mida_de_bloc) : bitmap block # (divisió entera)

r = b mod (8* mida_de_bloc)


25

Aquí veiem una figura d‟exemple de la Taula 3, en el cas de la mida de bloc a 1024, el

bitmap #1, estaria situat en el bloc número 65 a continuació del superblock, els 1024

blocs consecutius a aquest bitmap estan mapejats dintre el bitmap #1. El bitmap #2 es

trobaria en el bloc 8192 després dels blocs del bitmap #1, i el mateix amb el bitmap #3.

Figura 4. Posició dels bitmap blocks en la partició (no a escala)

En el cas que un bitmap bloc no s‟arribi a ocupar en la seva totalitat, la part restant

constarà com ocupada. Emprant l‟exemple de la figura 4, en el cas que necessitéssim

2,5 blocs de bitmap per mapejar tots els blocs de la partició, la segona meitat del tercer

bitmap bloc es marcarà amb els bytes a FF, aquests bytes no compten com a blocs

ocupats, ja que no existeixen dintre de la partició.

Els blocs que avarca el primer bloc de bitmap, sempre estan reservats pel journal

depenent de la mida de la partició necessitarà tots els blocs o menys, sempre esta fixat a

un número de 8192, sempre que la partició ho permeti, en el cas de que la mida de bloc

sigui de 4096 o més gran, sempre hi hauran els 8192 a més del journal header. Per altra

banda si la mida de bloc es més petita el bloc de bitmap no podrà assolir aquest número

de blocs, però ocuparà tot l‟espai que un bitmap bloc pot adreçar, deixant espai per un

últim bloc, el bloc header del journal.

Això es pot observar en el camp Num_blocs_journal del superblock.

3.3 Arbre del Sistema de Fitxers

L‟arbre de sistema de fitxers esta compost per un arbre balancejat, utilitzant un arbre B+

o S+, aquest arbre esta compost de nodes i fulles, cada node és un bloc. Cada objecte o

ítem en ReiserFS se li assigna una clau única que es pot comparar amb les claus dels

altres objectes.


26

3.3.1 Block Header

Dintre de cada bloc que pertany a un node intern o a un node fulla de l‟arbre comença

amb un bloc header. Un bloc header sempre esta compost per 24 bytes. Només els blocs

formatjats contenen el bloc header.

El bloc header està compost de cinc camps,

Camp Definició #Bytes Color

Nivell Indica el nivell en el que ens trobem dins de l‟arbre 2 Groc

# Items Indica el número de ítems que conté el bloc 2 Verd

Espai lliure Espai lliure que hi ha dins del bloc 2 Blau

Reservat Camp reservat 2 Taronja

Key Indica la clau que limita la dreta del node 16 Vermell

Taula 4. Camps Block Header

Figura 9. Block Header

En aquesta figura mostrem,

El nivell d‟aquest node es el root ( 8389632 / 1024 = 8193)

El nivell de l‟arbre indica que es un node fulla

En aquest node tenim set elements.

Tenim 328 bytes lliures en aquest bloc.

El camp de nivell de l‟arbre del bloc header no nomes indica a quina profunditat estem,

també ens indica si es un node intern o un node fulla, si el nivell de l‟arbre es superior a

1, vol dir que es un node intern. Si es igual a 1 vol dir que és un node fulla.

3.3.2 Key Block

Un node intern o un node fulla també conte una clau, aquesta clau s‟utilitza per

identificar els ítems, però també per a localitzar-los dintre de l‟arbre i per agrupar els

ítems que pertanyen als mateixos grups locals.

Hi han dos versions de Keys, les dues estan compostes pels mateixos camps però amb

un nombre de bytes diferents. El fet de tenir dos tipus de keys fa que al no tenir la versió

de la clau inclosa en si mateixa fa que sigui problemàtic. Per solucionar això els 16 bits

reservats en el bloc header ara contenen el número de versió, així que es pot obtenir

d‟allà. En el cas dels nodes fulla això es simple, el problema ve quan el sistema es troba

en un node intern, per tant hauria d‟anar fins al node fulla per mirar la key.


27

3.3.2.1 Key versió 1

Figura 10. Key Versió 1

Nom Valor

Hex/ Dec # Bytes Descripció

ID Directori 01/ 1 4 Identificador del directori on es troba l‟objecte

(Vermell)

ID Objecte 02 / 2 4 Identificador actual de l‟objecte (Verd)

Offset 01/ 1 4 L‟offset en bytes al que aquesta clau fa

referència ( taronja)

Tipus 1F4/ 500 4

El tipus de l‟ítem, els possibles valors són:

Stat: 0

Indirect: 0xfffffffe

Direct: 0xffffffff

Directori: 500

Qualsevol: 555

(Lila) Taula 5. Camps de la Key versió 1

En la figura 9 veiem que es tracta de un directori ( 1F4h = 500d ), es una de les claus

que es troba en bloc de root.

3.3.2.2 Key versió 2

Figura 11. Key Versió 2

Nom Valor


ID

Directori 01/ 1 4

Identificador del directori on es troba l‟objecte

(vermell)

ID Objecte 02 / 2 4 Identificador actual de l‟objecte (verd)

Offset 00/ 0 60 bits L‟offset en bytes al que aquesta clau fa

referència (taronja)

Tipus 00/ 0 4 bits

El tipus de l‟ítem, els possibles valors són:

Stat: 0

Indirect: 1

Direct: 2

Directory: 3

Any: 15

(lila) Taula 6. Camps de la Key versió 2

En el cas de que sigui un Stat Item té un offset de 0. Els Fitxers ( ítems directes i

indirectes) i els directoris sempre comencen amb offset de 1 així estan ordenats desprès

del stat item en el node fulla. Per als directoris el camp “offset” conté el valor de hash i


28

el generation number de la capçalera del directori que es troba més a la esquerra, no el

offset en bytes.

3.3.3 Tipus de Node

Cada node de l‟arbre pertany a un bloc del sistema de fitxers, aquest node pot ser intern,

vol dir que no està al nivell més baix de l‟arbre i que té punters als seus fills, o be que és

un node fulla que aquest està al nivell més baix de l‟arbre i els seus punters realment

apunten als fitxers i a les meta dades

3.3.3.1 Node Intern

Un bloc d‟un node intern està format pel Block header, les claus, i punters a nodes fills (

ja poden ser un altre node intern o node fulla). Totes les claus estan ordenades pel seu

valor, i seguit de l‟ultima clau els punters en el mateix ordre de les claus. En el bloc

header ve indicat com a nivell de l‟arbre més gran que 1.

Figura 12.Esquema d'un node intern

A continuació detallarem un node intern amb el bloc header inclòs, en el bloc header el

camp marcat amb morat es el nivell de l‟arbre, 02 00 veiem que és un node intern.

Figura 13. Camps del Node Intern

Sempre hi ha un punter més que el nombre de keys, ja que es marquen les menors i les

majors.

Punters

Mirarem l‟exemple de la figura 13 el punter encerclat en verd, l‟estructura d‟un punter

en els nodes interns te aquesta forma,

Figura 14. Camps del Punter


29

Camp Valor

Hex/Dec #Bytes Definició

Numero de

Bloc 2001 / 8193 4

Numero de bloc en el que estan les keys. En

aquest cas les keys menors.

Mida 394 / 916 2 Mida de la informació que conte.

Camp

Reservat 00 / 0 2 Camp reservat

Taula 7.Camps del Node intern

3.3.3.2 Node Fulla

Un bloc d‟un node fulla, també està compost igual que els nodes interns per un bloc

header, també conté item headers i els ítems, entre els ítems headers i els ítems hi ha un

espai lliure. En aquest cas els ítems estan en ordre invers als ítems headers

Figura 15. Esquema d'un node fulla

En cas d' insertar un nou element, el item header corresponent es trobaria al final del

Item Header n i el item es ficaria abans del Item n. D‟aquesta manera no s‟han de

reorganitzar les dades.

Ítem Headers

Un node fulla, és la situació anterior a mirar el contingut de les dades ja que conté la

informació del item, ja sigui stat, direct, indirect o directori.

Figura 16. Camps Item Header

Nom Valor


Key 01/ 1 16 La Key que pertany a l‟objecte (Vermell)

Count FF / 0xffff 2

Espai lliure del últim node sense format per

ítems indirectes.

0xffff per stat items i direct items

Numero de entrades de directori per a

directory item.

(Verd)

Longitud 98/ 152 2 Mida de l‟ítem en el bloc (Groc)

Localització 204/ 516 2 Offset de l‟ítem dintre del bloc (Lila)

Versió 01/ 1 2 0 per les Key versió 1, 1 per les noves(versió 2)

(taronja)

Taula 8.Camps del Item Header


30

3.3.4 Items

Els ítems en ReiserFS és tota la informació que es guarda en el node fulla després del

espai lliure, són els fitxers o directoris, es tracta de forma genèrica però hi han quatre

tipus de ítems, on guardem les meta dades (stat item), directoris i depenent de la mida

del fitxer tindrem un direct item (fitxer petit) o indirect item (fitxer gran).

3.3.4.1 Stat items

El stat item mostra els atributs del item, una de les propietats del item header d‟aquests

és que l‟offset i el tipus de la key és igual a 0 (8 bytes), la resta de la key és la mateixa

que la del item header següent que és el fitxer o directori, en aquesta figura d‟un node

fulla veiem un exemple, en verd el stat item i en blau el direct item al que correspon el

stat item. Com veiem tenen la mateixa key, però amb els camps offset i tipus a 0. Sabem

que es un node fulla, per l‟ordre en el que es troba el item header i el item, que tenen

un ordre palíndrom.

Figura 17.Stat Item i direct item

El stat item al igual que la key, té dos versions, degut a que el camp de offset es va

augmentar per a que la màxima mida de fitxer fos de 260

, però com a màxim poden ser

232

blocs per 216

bytes per bloc, coma màxim suporta 248

bytes. Aprofitant aquest canvi

també es va augmentar la mida dels hard links, dels user id i dels grup id de 16 bytes a

32 bytes.

Stat item versió 1

En la versió 3.5 utilitzen la versió 1, té una mida de 32 bytes mentre que la versió 2

(3.6) és de 44 bytes.

Figura 18. Posició dels bytes en un stat item versió 1 [3]


31

Nom #Bytes Descripció

Mode 2 Tipus de fitxer i permisos

Num. links 2 Numero de hard links

UID 2 User id

GID 2 Grup id

Size 4 Mida del fitxer en bytes

Atime 4 Temps des de l‟últim accés

Mtime 4 Temps des de l‟ultima modificació del fitxer

Ctime 4 Temps des de l‟ultima modificació del stat item

Rdev/Blocs 4 Device

First dir.

byte 4

Primer byte del fitxer que s‟emmagatzema en un item directe

si es igual 1 és un symlink

si es igual 0xFFFF no hi ha direct item. Taula 9.Stat Item versió 1

Stat item versió 2

En la figura següent veiem un exemple de la estructura del stat item de la figura 17,

aquestes junt amb la informació del item header formen el conjunt de les meta dades.

Figura 19. Estructura d'un Stat item versió 2

Nom #Bytes Descripció Color

Mode 2 Tipus de fitxer i permisos Vermell

Numero links 4 Numero de hard links Groc

Mida 8 Mida fitxer en bytes Verd

UID 4 User id Blau

GID 4 Grup id Rosa

Atime 4 Temps des de l‟últim accés Taronja

Mtime 4 Temps des de l‟ultima modificació Verd

Fosc

Ctime 4 Temps des de l‟ultima modificació del stat Negre

Blocs 4 Número de blocs que utilitza el fitxer Marró

Rdev/gen/first 4

Device number/

Generació del fitxer/

Primer byte del fitxer que s‟emmagatzema en

un item directe

si es igual 1 és un symlink

si es igual 0xFFFF no hi ha direct item.

Turquesa

Taula 10. Descripció dels camps d'un stat item versió 2


32

En el camp mode, els 9 bits de menor pes indiquen els permisos per a tots, grup i usuari,

els 3 següents són el sticky bit, GID bit i UID bit. Els 4 bits de més pes indiquen el tipus

d‟arxiu, per un sistema Linux, els possibles valors són els següents:

Nom constant Màscara 16 bits Valor 4 bits Tipus Arxiu

S_IFSOCK 0xC000 12 socket

S_IFLNK 0xA000 10 symbolic link

S_IFREG 0x8000 8 regular file

S_IFBLK 0x6000 6 bloc device

S_IFDIR 0x4000 4 directory

S_IFCHR 0x2000 2 character device

S_IFIFO 0x1000 1 fifo Taula 11. Valors de tipus d'arxius

En aquesta figura extraiem la següent informació del fitxer,

Mode: 81A4h

Numero de links: 01h

Mida: 91h

UID: 00h

GID: 00h

Atime: 492C10DDh

Mtime: 492C10D8h

Ctime: 492C10D8h

Blocs: 2h

Rdev/gen/first: 00h

3.3.4.2 Directory Ítems

Els Directory Item, representen els directoris, si el directori té més entrades que les que

pot contenir l‟ítem, s‟expandirà a diversos directory items.

Al igual que els nodes fulla, en primer lloc van les capçaleres i desprès els noms dels

arxius.

Figura 20. Directory Item

Les capçaleres contenen el offset, les dos claus d‟ítems de referència, la localització del

nom dins del bloc i el estatus.

Figura 21. Capçalera d'un item de directori


33

Nom Valor

Hex/Dec #Bytes Descripció Color

Offset 01 / 1 4 Valor de hash i generation number Vermell

Dir ID 02 / 2 4 Referència al object id del directori

pare Verd

Object ID 06/ 6 4 Object ID del item Morat

Localització 50/ 80 2 Offset dintre del item Blau

Estat 04/ 4 2

Bit 0 indica stat data (no s‟usa)

Bit 2 indica que es visible(bit a 1) o

hidden (bit a 0)

Taronja

Taula 12. Camps d'un directori item

El camp de offset, els bits del 7 al 30 indiquen la funció de hash i els bits de 0 a 6

indiquen la generació en cas de que dos noms de fitxers tinguin la mateixa funció de

hash. La funció de hash té el propòsit de crear diferents valors per a dos strings amb

possibilitats altes de col·lisió.

En la figura 19, es pot extreure la següent informació,

Capçalera 0: {hash 0, gen. 1, 2, 6, byte 0x50, 4 (bit 2 set: visible)}



Nom 2: "fitxerdirectori1.txt"

Nom 1: ".."

Nom 0: "."

En cas que un directori contingui un número de elements elevat i no es pugui guardar la

informació del contingut en un sol bloc, es propagarà el contingut al següent bloc del

node pare, aquest dividirà la informació del directori i indicarà que es un directori ( els

quatre últims bytes indicaran 1F4) i del byte num 9 al 13 mostraran un número diferent

de cero. D‟aquesta manera queda una part del contingut en el bloc inicial i l‟altre part

queda en el bloc següent.

3.3.4.3 Direct Ítems

Un ítem directe és aquell que conté tot el contingut del fitxer, la resta de la informació

es troba en el stat item corresponent i en el item header.

En la figura a continuació veiem que el item header ( @8389824) marca,

Key del item: {2,5,1,2} en vermell

Count: 0xffff en groc

Mida: 98h / 152d bytes en verd

Offset: 204h / 516d bytes en blau

Versió: 1 (nova) en morat

El contingut del fitxer en turquesa.


34

Figura 22. Exemple d’ítem directe

3.3.4.4 Indirect Ítems

Els fitxers indirectes contenen punters que apunten a blocks sense format que pertanyen

al fitxer. Cada punter ocupa 4 bytes i conté el número de bloc del bloc. Cada bloc fulla

conté com a màxim (mida_bloc – 48) / 4 bytes, els 48 anteriors contenen el bloc i el

ítem header. Els fitxers llargs com veurem en un exemple en el punt 4.3.2 estan

compostos per múltiples punters, en la figura següent veiem un exemple d‟un fitxer

indirecte.

Figura 23. Fitxer amb item indirecte


35

3.4 Journal

El journal en ReiserFS és un conjunt de blocs que indiquen transaccions realitzades pel

sistema de fitxers. Cada cop que el sistema es modifica en comptes d‟aplicar els canvis

directament en el sistema es guarden primer al journal. Més endavant quan els canvis

s‟han realitzat es fa un “flush” de la transacció i es marcarà com a correcte.

El journal en ReiserFS es troba després del primer bloc de bitmap, està fixat a 8192

blocs més un bloc de journal header, sempre que la mida de bloc sigui igual o superior a

4096, els blocs estan formats per transaccions de mida variable. Una transacció ocupa

almenys tres blocs, en canvi el header ocupa un.

Aquest journal empra una cua circular estàtica, el funcionament consisteix a que el

journal comença pel primer bloc reservat per transaccions, i les va omplint, quan arriba

a la última després d‟utilitzar-la torna a la primera, i busca la que estigui disponible.

Figura 24. Journal del sistema ReiserFS

En una transacció es podria considerar que es guarden dades redundants, ja que en

l‟arbre hi ha informació que també es guarden en el journal, aquestes dades però estan

per guardar la consistència del journal i un cop que s‟ha realitzat el “commit” la

transacció passa a disponible, per tant quan la cua circular torni a arribar en aquest punt

pugui reescriure les dades.

3.4.1 Journal Header

El Journal Header, com el seu nom indica, és la capçalera del journal que conté la

informació de la última transacció feta amb resultat correcte, el offset fins a la següent

transacció a realitzar i l‟identificador de muntatge d‟aquesta.

Aquesta capçalera es troba al final de totes les transaccions, es tot un bloc però en

realitat només s‟utilitzen els 12 Bytes inicials tota la resta del bloc no està definit.

Les tres dades que guarda el journal header es detalla un exemple en al figura següent.

Figura 25. Journal Header


36

Els tres camps del journal header són els següents.

Nom del camp #

Bytes

Explicació camp Color

Figura

Id Ultima

transacció

4 Identificador de la última transacció

realitzada amb èxit

Vermell

Offset prox

Transacció

4 Offset fins a la següent transacció del journal Verd

Id Mount 4 Identificador de Mount de la Transacció Groc

Taula 13. Dades del Journal Header

En aquesta figura podem veure que ens trobem en la adreça 8387584d, la partició que

hem emprat d‟exemple, es la mateixa que en les figures anteriors, mida de bloc 1024,

per tant el numero de blocs pel journaling és menor 8192, en aquest cas és de 8125

blocs (extret del superblock). En aquest cas trobem aquesta adreça després de sumar als

blocs de journal, els blocs inicials fins al primer bloc de bitmap (66 blocs), aquests blocs

es multipliquen per la mida de bloc (1024) i obtenim la adreça del header. Aquesta

adreça es el bloc anterior al segon bloc de bitmap.

3.4.2 Transaccions

Les Transaccions són les operacions que s‟han fet en el nostre sistema, en comptes de

modificar-les directament sobre l‟arbre de fitxers, d‟aquesta manera mantenim una

l‟estabilitat. Primer són escrites en el journal i desprès les escrivim en la seva posició

real.

Una transacció esta composta per un description bloc, un llistat de blocs i un Commit

bloc, tots aquests blocs estan col·locats seqüencialment en el sistema de fitxers.

Figura 26. Esquema d’una Transacció

En el Superblock esta la informació de quantes transaccions i quants blocs per

transacció podem tenir com a màxim. A continuació descriurem les parts d‟una

transacció.

3.4.2.1 Description bloc


37

El Description bloc esta al inici de la transacció, en aquest bloc conté tres camps

importants.

L‟identificador de la transacció

El número de blocs que es modificaran en aquesta transacció (En aquest camp

no es compten ni el Description bloc ni el commit bloc.

L‟identificador de Muntatge.

Apart d‟aquests tres camps que són els 12 bytes inicials (4 bytes per camp), tenim a

continuació el que s‟anomena “blocs reals”. Aquest blocs indiquen quins blocks es

modificaran. Les modificacions que es faran venen donades en el mateix ordre dels

blocs posteriors ordenats seqüencialment.

El superblock al ser el nucli d‟aquest sistema de fitxers, es un bloc que es modificarà

quasi be a totes les transaccions, ja que gestiona el numero blocs lliures, els nivells de

l‟arbre, etc... Per tant ja que es modificarà molts cops s‟ha de assegurar la consistència

de les dades, cosa que el journaling ho aconsegueix, ja que en els blocs següents que

s‟han de modificar pel journaling, venen els blocs que s‟han de reemplaçar pels que

estan escrits a l‟adreça pertinent.

Es pot pensar que les metadades d‟aquest sistema de fitxers es redueixen al journaling,

ja que com hem explicat en el paràgraf anterior guarda una copia, però tota la

informació que es troba en el journaling també es troba al arbre, per tant d‟aquesta

manera apareix redundància “temporal”.

Un exemple pràctic del Description Block veurem a la figura següent.

Figura 27. Description Block

Nom del

camp

Valor

Hex/decimal

Descripció Color


38

Id

transacció

0A / 10 Id. de la transacció Vermell

#blocs 02 / 2 Número de blocs que es modificaran en

la transacció

Verd

Id Mount 0A /10 Id. del muntatge Blau

“Blocs

reals”

40 / 64

2001 / 8193

Blocs que es modificaran Morat

Magic ReIsErLB “Frase Màgica” Marró

Taula 14. Description bloc de la Figura 9

En aquest exemple veiem com aquesta transacció modificarà dos blocs, el Superblock

(bloc # 64) i el bloc de root (8193). A continuació d‟aquest bloc vindrà el bloc que

substituirà el superblock, aquí veiem la comparativa de com quedaria el superblock

desprès de la transacció.

En la figura següent podem veure que el bloc envoltat en verd seria el equivalent al

Superblock si mirem les adreces es la consecutiva de la última de la figura 9, en aquest

cas es modifica tot el bloc original pel bloc modificat del journal. En vermell veiem que

la adreça correspon a la del Superblock original. Encerclat en blau tenim el resultat de

les modificacions en el camp estat de la partició. De correcte a incorrecte.

Figura 28. Modificació del Superblock desprès d’una transacció

En aquest cas marca la partició com ha no vàlida perquè està modificant blocs, mentre

no acabi la transacció no tornarà a posar el camp a vàlid, d‟aquesta manera si hi ha una

caiguda del sistema es podrà recuperar gràcies al journal. Quan es torni a encendre, el

sistema veurà que no es vàlid, llavors mirarà el journal i desfarà les operacions per a

recuperar un estat correcte i estable abans de la caiguda.

El camp en verd ja és part d‟un “bloc real”, en realitat és un bloc sencer però només ens

interessen aquests 80 bytes que són els valors del superblock, no és part del Description

bloc.

3.4.2.2 Commit bloc


39

El Commit bloc es l‟últim bloc de la transacció aquest bloc indica si la transacció ha

finalitzat. No té més utilitat que aquesta, té una copia del identificador de la transacció i

dels blocs que ocupa, a part té un camp a final “digest” o resum que en la actualitat no

fa servei.

En la Figura 11 mostrem l‟exemple del Commit Block de la transacció mostrada en les

Figures anteriors.

Figura 29. Commit Block

En la Taula 6, veiem els valors d‟aquest bloc.

Nom del

camp

Valor

Hex/decimal

Descripció Color

Id

transacció

0A / 10 Id. de la transacció Vermell

#blocs 02 / 2 Número de blocs que es modificaran en

la transacció

Verd

Digest 00 /0 Resum de la transacció Morat

Taula 15. Dades del Commit Block


40

4.Explicació comandes bàsiques

En aquest apartat s‟exposa l‟explicació de com s‟han efectuat les “comandes bàsiques”

necessàries per a entendre el funcionament d‟aquest sistema de fitxers, en alguns dels

casos l‟explicació serà més especifica, ja que estan contemplades en l‟aplicatiu i té

suport d‟algoritme, en canvi el que es esborrat serà a nivell informatiu però també baix

nivell de programació.

4.1. Llistat root

Per a llistar el contingut de la arrel del directori, primerament ens hem de situar en

l‟arrel de l‟arbre del sistema de directoris, aquest node té la estructura idèntica a un node

intern, per tant no es fa diferencia en el tractament d‟aquest. Seleccionem aquest node,

que ens ve donat el seu numero en el Superblock, el contingut del root es troba en el

bloc fulla que es troba en el primer bloc desprès de l‟últim Bitmap Block. Per tant

sempre aniríem al root de l‟arbre del sistema ReiserFS i avançaríem pel primer punter.

Figura 30. Camí cap al Root node

En l‟exemple de la figura 31, veiem que hem de desplaçar-nos al bloc 2001h/8193d per

a trobar el bloc de root. En aquest node fulla trobem en primer lloc el Block header del

node son els 24 bytes inicials, a continuació trobem el stat item del root node (blau) amb

la key {1,2,0,0} que ens diu les metadades del directori, seguit (en vermell) tenim la key

{1,2,1,500} aquí indica que es el directori arrel per el 500d del tercer element de la key,

com hem vist en apartats anteriors, a continuació de la key ens diu, el número de

elements, l‟offset fins a la informació entre altres.

En verd veiem tota la informació del directori, com hem explicat en apartats anteriors.


41

Figura 31. Llistat del directori de root

La informació que conté el directori de root veiem que es la següent,

Figura 32. Contingut del directori arrel.

4.2. Arbre de directoris

Per a pintar tot l‟arbre de directoris seguirem una tècnica molt semblant a la esmentada

en l‟apartat anterior, però en aquest cas més genèric.

Seguirem el procediment per a llistar els elements del node arrel, en quan estem mirant

els elements mirem llegim les keys i busquem l‟element, es a dir, tornem al node arrel i

busquem per l‟arbre de directoris aquest element, que encara no sabem si es un fitxer

directe, indirecte o un directori, en la figura que ve a continuació podem observar que


42

en vermell es troba la funció de hash que diferencia els elements en cas que el nom sigui

igual. En verd i morat, trobem els dos primers elements d‟uns key que ens son suficient

per a buscar el fitxer o directori, les guardem i un cop les tenim tronem al node arrel a

buscar-les, si es un directori repetim operació, si es un fitxer acaba la recursivitat i

segueix amb el següent element així fins que recórrer tot l‟arbre de directoris.

Figura 33. Funcions de hash i keys dels elements

A continuació veiem el resultat del recorregut de l‟arbre en una partició d‟exemple.

Figura 34. Arbre de directoris

4.3. Mostrar el contingut d’un fitxer

A continuació estudiarem com el sistema reiserfs arriba a un fitxer que estem buscant en

tres casos, un fitxer amb un item directe, amb un item indirecte i amb un fitxer gran.


43

En tots casos el recorregut s‟inicia en el root node tenim el número de bloc i té la clau

{1,2,0,0}. En aquest apartat donem per fet que comencem en el root node ja que en el

apartat 4.1 ja es parla de com s‟accedeix al root i com es llista el seu contingut, en canvi

si que seguirem pas per pas el camí a seguir a partir del root node.

4.3.1 Fitxer petit (direct item)

Per exemple estem buscant el fitxer “/directori1/fitxerdirectori1.txt” en aquest cas té el

número de key {2,9,1,0}.

Ens situem en el root node que en aquest cas es el bloc numero 8195, que pertany a la

@8391680d, en aquest cas podem comprovar que es troba al nivell 2 de l‟arbre ( com es

marca amb verd) , per tant es un node intern, aquest node estava compost de keys i a

continuació els punters que apunten en aquest cas al node fulla, que conté la informació

d‟aquest fitxer, com estem comparant les keys anem avançant fins que es compleix la

condició que la key que estem mirant sigui inferior, un cop ho trobem (groc) anem al

punter on ens indica a quin numero de bloc pertany (els dos primers bytes de la secció

en vermell indica el número de bloc en little endian) en aquest cas el 2006h/8198d.

Figura 35. Root node

El punter 2006h ens porta a la @8394752d com podem veure en la figura 30, es un node

fulla, en primer lloc trobem una key que es igual a la que estem buscant (vermell fosc),

aquest mostra l‟stat item ja que la key te la forma {2,9,0,0} i indica totes les propietats

del fitxer.

En vermell a continuació del stat item ve el item, que en vermell indica la clau del

directori i veiem com el valor de l‟últim byte de la key es 2d, això ens indica que es un


44

fitxer directe. En groc indica la longitud del fitxer en aquest cas veiem que es 10d, per

tant es un fitxer realment petit que conté 10 bytes d‟informació, i finalment en morat,

podem veure l‟offset on es troba la informació respecte el començament del bloc

25Ch/604d, per tant en l‟@8395356 trobem el principi del contingut del fitxer contem

10 bytes i tenim tota la informació.

Figura 36. Item del Fitxer i contingut.

Així tenim que en el fitxer “/directori1/fitxerdirectori1.txt” tenim en valor hexadecimal

els següents valors, 62 6C 61 62 6C 61 62 6C 61 0A, aquest valors se li aplica el codi

ASCII i tenim que el contingut d‟aquest fitxer es “blablabla”.

4.3.2 Fitxer gran (indirect item)

El fitxer que es troba “/directori3/reiserf.txt” té la key {2,20,1,0} en aquest cas com la

key es més gran que l‟última key que guarda el root node, ens anirem pel punter n+1, en

aquest cas el bloc destí es el 2009h/8201d.

Figura 37.Root node fitxer indirecte

Un cop ens desplacem al bloc seleccionat i trobem l‟ítem indirecte (podem veure que a

sobre de l‟ítem header trobem l‟ítem header del stat item del fitxer, en aquest cas ara ens

interessa troba els punters a blocs sense format, per el número de punter utilitzats (41)

veiem que ocupa al voltant de 42KB en cas que tots estiguin plens. Si mirem l‟ítem


45

header del item indirecte, veiem que ens indica que es troba a un desplaçament de

202h/544d, i que ocupa A4h/164d, que són els punters (cadascun de 4 Bytes com hem

vist en apartats anteriors.

Veiem en la figura 37 que a partir de la @8398368 tota aquesta informació són punters

a blocs sense format, que mantenen les dades tal qual les llegeixen, cada 4 Bytes són

blocs, comencen en el bloc 2200h i el fitxer acaba en el bloc 2228h.

En aquest cas estan tots consecutius però no te perquè se així poden estar en llocs

diferents depenen com estigui distribuïda la memòria.

Figura 38.Fitxer Indirecte

Aquest punters indirectes, finalment apunten a la informació del fitxer, en la figura

següent mostrem la informació d‟un dels blocs en aquest cas el 2200h/8704d.


46

Figura 39. Part del bloc 8704

4.4. Creació d’una carpeta

En aquest apartat avaluarem com crea les carpetes el sistema ReiserFS, a més a més

comentarem i avaluarem algunes de les complexitats que presenta un sistema com

aquest, el arbre balancejat assegura més robustesa en la organització i seguretat de les

dades però també incrementa la problemàtica a l‟hora de tractar la informació i per

suposat generar el codi que implementa.

En la creació de la carpeta s‟han de tenir en compte diversos aspectes, en primer lloc

s‟ha d‟entendre que la creació del directory item, no es en si el final, ja que es pot

modificar a mesura que creix. Sabem que el sistema ReiserFS treballa amb un arbre

balancejat, es a dir a cada cop que es crea un node nou s‟ha d‟ordenar i balancejar

l‟arbre, es un cost molt elevat de recursos i es en aquest punt on la creació del ítem

directori (tant directori com en fitxer) entra en un fase que necessita d‟optimitzacions i

de disseny d‟algoritmes avançats.

A continuació diferenciarem entre prerequisits i seguidament explicarem el procés que

segueix el ReiserFS per crear la carpeta.

Prerequisits:

Mida de Bloc : l‟obtenim del Superblock.

Bitmapblock: En aquest cas hi han diverses tècniques empleades per a trobar el

bitmapblock buit, no en totes les compilacions d‟aquest sistema s‟agafa el

primer buit que seria la evident, sinó que en alguns casos es comença per l‟últim

bitmapblock i es llegeix cap enrere fins a trobar el primer buit, això es fa per

evitar salts innecessaris a memòria (optimitzacions de codi).

Generar la Key que pertany a l‟element.


47

Explicació:

Crear nou node: que es situa en la part esquerra del node fulla de més a la

esquerra, allà es situa el item juntament amb el seu stat item.

Optimitzacions de balancejar el node: En aquest cas es fan servir 4

optimitzacions per a balancejar l‟arbre:

1. Minimitzar el nombre de nodes utilitzats.

2. Minimitzar el nombre de nodes afectats a l‟hora de balancejar

l‟arbre.

3. Minimitzar el nombre de nodes lliures durant les operacions de

balancejar l‟arbre.

4. Si la mida del directori sobrepassa fa que sobrepassi la mida de

bloc, shiftar el màxim d‟elements a un nou node, d‟aquesta

manera s‟evita balancejar més cops.

Generar una entrada per al journaling amb els bloc afectats per a les

modificacions realitzades.

En el cas dels directoris pot anar creixent per tant cada cop que es guardi un fitxer o es

creï un nou directori es repetiran les operacions d‟aquesta manera es tindrà control i si

es necessari es farà un nova redistribució del contingut entenent-se al bloc següent.

4.5. Creació d’un fitxer

En aquest cas el prerequisits passant a ser el mateix, la diferencia es a l‟hora de guardar

el contingut, aquí apareix una de les principals característiques del ReiserFS Tail

Packing, que ens pot estalviar espai en el disc dur.

Prerequisits:

Mida de Bloc: l‟obtenim del Superblock.







Explicació:

Comprovem mida del fitxer, que no superi l‟espai restant al disc.

Mida de fitxer: en cas que no sobrepassi la mida prefixada pel tail packing

(4kB) s‟afegeix en el mateix node, d‟aquesta manera evitem crear un altre node

i perdre espai. En cas que sobrepassi aquest mida crearem els links als nodes on


48

esta el contingut del fitxer i el final del fitxer el ficarem com si fos un node

directe en el mateix node (Tail Packing).

Crear nou node: que es situa en la part esquerra del node fulla de més a la

esquerra, allà es situa el item juntament amb el seu stat item.

Copiar el fitxer al nou node.

Optimitzacions de balancejar el node: En aquest cas es fan servir 4

optimitzacions per a balancejar l‟arbre:

5. Minimitzar el nombre de nodes utilitzats.

6. Minimitzar el nombre de nodes afectats a l‟hora de balancejar

l‟arbre.

7. Minimitzar el nombre de nodes lliures durant les operacions de

balancejar l‟arbre.

8. Si la mida del directori sobrepassa fa que sobrepassi la mida de

bloc, shiftar el màxim d‟elements a un nou node, d‟aquesta

manera s‟evita balancejar més cops.

Generar una entrada per al journaling amb el bloc anterior a la modificació i

posterior.

En cas que el contingut del directori que emmagatzema els fitxers augmenti seguirem el

mateix pas, s‟expandirà als nodes veïns.

Són els mateixos passos que en la creació de la carpeta ja que la veritable dificultat

d‟aquest procés es la optimització dels algoritmes de balanceig.

4.6. Esborrat d’un fitxer

Per al esborrat d‟un fitxer, tant si es directe com indirecte, s‟allibera amb els següents

passos.

Prerequisits:








Explicació:

Es localitza l‟element a l‟arbre de directoris. S‟elimina la entrada del node i es

balanceja, en cas que sigui un node indirecte els nodes sense format, es


49

mantenen com a lliures al bitmap block, d‟aquesta manera si un altre els

requereix, el reescriu.

4.7. Esborrat d’un directori

Consisteix en esborrar una entrada de directori, en aquest cas recordem que el directori

té els noms dels elements que conté i les seves keys.

Prerequisits:








Explicació:

S‟elimina els elements de dins del directori, mitjançant la seva key, com s‟ha

especificat en el cas anterior, un cop el directori es troba buit, s‟elimina

l‟element es marquen els blocs que es modifiquen per deixar-ho al journaling, i

es procedeix als algoritmes de balanceig de l‟arbre i es modifiquen els blocs.


50

5.Aplicacions similars

5.1.RFSTOOL

Aquesta eina permet accedir a les particions de ReiserFS des de un sistema Windows.

Ara també té la opció d‟accedir a la inversa, dissenyat per Gerson Kurz.

El conjunt de funcionalitats que ens dona aquest eina:

o Eina de consulta d‟una partició formatada amb ReiserFS.

o Interfície amigable i simple.

o Enfocada únicament per funcionalitat, consulta del arbre de directoris.

o Permet copiar al directori actual fitxers de la partició ReiserFS.

Alguns inconvenients, o mancances

o No modifica la partició de ReiserFS.

o Ignora el journaling.

o No mostra informació Superblock.

o No mostra informació del arbre de directoris.

o No permet muntar particions externes.

Figura 40. Un disc local consultat amb RFSTOOL [4]


51

5.2.UFS Explorer Batch

UFS Explorer Batch no es exclusiva per consultar particions de ReiserFS, també llegeix

de ext2, ext3, XFS, etc...

Aquesta es un eina bastant potent en quan a exportació, copia i lectura de fitxers d‟altres

particions. Algunes de les avantatges són,

o Permet carregar particions des de un disc local, un USB i des de particions

virtuals.

o Serveix per a més d‟un sistema de fitxers.

o Permet copiar i crear carpetes i directoris a les particions.

Alguns del desavantatges són:

o Interfície poc amigable, ja que s‟ha de fer en mode consola.

o Enfocada únicament per funcionalitat, no consulta cap tipus d‟informació

respecte el sistema de fitxers.

Figura 41. Exemple UFS Explorer Batch [5]


52

6.Aplicació resiserfs_rdr

6.1. Introducció

ReiserFS_rdr es tracta d‟una eina docent orientada a l‟estudi i aprenentatge dels

sistemes de fitxers de Linux i més concretament del sistema de fitxers ReiserFS.

Com ens suggereix el seu nom es tracta d‟una eina que permet la lectura de particions

ReiserFS fent especial èmfasi en com s‟accedeix a la informació que s‟està mostrant.

A continuació veurem com està dissenyada i implementada l‟eina i en detallarem el seu

funcionament tant des d‟una visió d‟usuari com de programador.

6.2. Anàlisi requisits

Aquesta eina esta destinada als alumnes de la assignatura de Sistemas Operatius com a

suport del sistema ReiserFS.

L‟assignatura té poc material respecte a varietat de sistemes, fins al moment disposen

del sistema FAT i ext2, d‟aquesta manera amb aquest treball s‟amplia la matèria i per

tant dona una visió més amplia dels sistemes de fitxers.

6.2.1. Requisits funcionals

Per a la elaboració d‟aquest treball s‟han tingut en compte els requisits funcionals

següents,

L‟usuari pot carregar qualsevol imatge i poder accedir a les funcionalitats del

aplicatiu.

Disposarà de botons d’ajuda, aquí podrà extreure la informació més

significativa, i petites ajudes per a entendre el que esta veient.

L‟usuari podrà veure tota la informació que fa referència al sistema de fitxers, es

a dir,

Informació sobre el Superblock, i la localització en el mapa de

memòria.

Informació sobre el Bitmap Block, posició de memòria, número

de bloc.

Informació sobre el arbre de directoris, i veure les propietats

d‟aquests com dates de consulta, permisos, tipus de fitxers.

Visió de Fitxers dins la partició en ASCII, com en hexadecimal,

ambdues traduccions per que l‟alumne pugui entendre el

funcionament.

Observar el journaling i les seves transaccions com estan

formades, com les tracta i la seva funció.


53

6.2.2. Requisits usabilitat

Apart de les funcionalitats anteriorment esmentades, l‟eina havia de ser usable. Per

aquest motiu, l‟eina havia de complir amb un seguit de requisits que tot seguit

assenyalarem:

L‟aplicació com a eina didàctica ha de tenir una interfície amigable i

intel·ligible.

Es comptarà en tot moment amb una ajuda que permetrà a l‟usuari entendre què

fa l‟aplicació.

Es tractarà de minimitzar el nombre de clics que hagi de fer l‟usuari per tal

d‟accedir a una determinada informació.

6.3. Decisions disseny

6.3.1. Entorn execució

Degut a que ja s‟han entregat treballs d‟estudis de fitxers per l‟assignatura, hem decidit

seguir l‟exemple d‟anys anteriors ja que han donat molt bon resultat i dona la

possibilitat de que l‟alumne pugui treballar en el mateix entorn, al ser una aplicació

semblant, la interacció amb l‟usuari no es més dificultosa sinó que agilitza la consulta, i

es manté la interfície amigable i senzilla.

6.3.2. Entorn programació

Com ha entorn de programació també vam seguir les pautes dels treballs anteriors, en

.NET, més concretament C#, ja que no només servia per aprendre sinó que es un tipus

de programació que es semblant a altres amb els que si s‟havia treballat com C++ i no

resultava tant costos.

També el fet de que l‟ interfície gràfica fos senzilla va animar a seguir amb aquest

llenguatge.


54

6.4. Anàlisi funcional

6.4.1. Modelat estàtic

6.4.1.1. Diagrama de casos d’ús

L‟aplicació disposa de un seguit de funcionalitats que detallarem en el diagrama de

casos d‟ús

Figura 42. Diagrama casos d'ús


55

Ara detallarem cada cas d‟ús,

Cas ús: Mostrar Ajuda

ID CU1

Objectiu Mostrar manual d‟ajuda

Actors A1 Usuari

Precondició -

CU Relacionats Tots

Activació A discreció de l‟usuari

Flux Principal 1. L‟usuari clica sobre l‟opció d‟ajuda.

2. S‟escull sobre quina opció es vol

seleccionar

Variacions -

Excepcions -

Postcondicions -

Comentaris - Taula 16. Especificació cas d'ús mostrar ajuda

Cas ús: Obrir Imatge

ID CU2

Objectiu Obrir una imatge de ReiserFS

Actors A1 Usuari

Precondició -

CU Relacionats -


Flux Principal 1. Obrir una imatge valida de ReiserFS

2. Guardar certa informació relativa al

Superblock

Variacions -

Excepcions Imatge no vàlida

Postcondicions -

Comentaris - Taula 17. Especificació cas d'ús Obrir Imatge


56

Cas ús: Mostrar Superblock

ID CU3

Objectiu Mostrar La Informació del Superblock

Actors A1 Usuari

Precondició Haver obert una imatge de ReiserFS

vàlida

CU Relacionats -


Flux Principal 1. L‟usuari clica la opció del Superblock

Variacions -

Excepcions -

Postcondicions -

Comentaris - Taula 18. Especificació cas d'ús Mostrar Superblock

Cas ús: Mostrar Bitmap Block

ID CU4

Objectiu Mostrar contingut dels Bitmapblock en

format hex

Actors A1 Usuari


vàlida

CU Relacionats -


Flux Principal 1.L‟usuari clica sobre la opció mostrar el

bitmapblock

2.L‟usuari pot clicar per mostrar un

bitmapblock concret.

Variacions -

Excepcions -

Postcondicions -

Comentaris - Taula 19. Especificació Mostrar Bitmap Block


57

Cas ús: Mostrar Journaling

ID CU5

Objectiu Mostrar informació relativa al sistema de

Journaling de ReiserFS

Actors A1 Usuari


vàlida

CU Relacionats -


Flux Principal 1. L‟usuari clica sobre la opció mostrar el

Journaling

2. L‟usuari clica per consultar la

informació del Journaling

Variacions -

Excepcions -

Postcondicions -

Comentaris - Taula 20. Especificació cas d'ús Mostrar Journaling

Cas ús: Mostrar Arbre Directoris

ID CU6

Objectiu Navegar per l‟estructura de directoris de la

imatge ReiserFS

Actors A1 Usuari


vàlida

CU Relacionats -


Flux Principal 1.L‟usuari clica sobre la opció mostrar

arbre directoris.

2. L‟usuari clica sobre els

fitxers/directoris per veure les propietats i

opcions.

Variacions -

Excepcions -

Postcondicions -

Comentaris - Taula 21. Especificació cas d'ús Mostrar arbre directoris


58

6.4.1.2. Diagrama de classes

L‟aplicació està formada per un gran nombre de classes. Tot seguit passarem a detallar

les relacions entre aquestes fent ús d‟un diagrama de classes.

Figura 43. Diagrama de classes

A continuació comentarem cadascun de les classes (atributs i mètodes), també

descriurem per a que serveixen així com una breu descripció de la seva funció dins del

programa principal.

Figura 44. Classe Program

Aquesta classe es la que comença el programa, de fet aquesta classe es crea per defecte

sempre que es fa un programa amb C#, aquesta crida conté la crida al formulari

principal del nostre aplicatiu.


59

Figura 45. Classe principal

La classe principal es el formulari principal, aquesta es crida a al començament de

l‟execució, dona la opció d‟obrir la partició de ReiserFS. Un cop validada correctament

permet accedir als diferents apartats de l‟aplicació

Figura 46.Classe info_superbloc

Aquesta classe conté tota la informació del Superblock d‟aquesta manera per consultar

alguna propietats, farem accés a memòria i no haurem de llegir de la partició, d‟aquesta

manera evitem salts innecessaris i agilitzem el procés.


60

Figura 47.Classe superblock

La classe Superblock conté tots els atributs i mètodes necessaris per a mostrar tota la

informació rellevant, i crear el formulari de la aplicació.

Figura 48. Classe Bitm_bloc

El Bitmapblock és el formulari amb tots els mètodes per a mostrar el contingut agrupar

les seves propietats i la interfície.


61

Figura 49. Classe ItemTreeAux

Per crear aquest ítem s‟ha utilitzat herència del ItemTree ja que ens interessava guardar

molta més informació de cada node. No teníem prou amb guardar l‟adreça on

començava pel que hem comentat abans, agilitzar les consultes i no llegir del fitxer tota

la informació. Si la podem guardar en una classe més senzill.

Figura 50. Formulari de L'arbre de directoris

La classe Tree s‟encarrega de la consulta i visió del arbre de directoris, tenim les

diferents opcions per veure tot el necessari per a consultar els fitxers i directoris de la

partició.


62

Figura 51. Classe journal

La classe journal s‟activa quan l‟usuari vol consultar la informació referent al

journaling, també conté la interfície per a consultar la seva informació

Figura 52. Classe frmRealBlocks

Aquest formulari conté la interfície, els mètodes i els atributs necessaris per a consultar

la informació dels blocs que es guarden en el journal, també guardem les dades

principals a memòria per evitar estar saltant dins de la imatge, sense comptar que la

velocitat d‟accés a memòria es més ràpida que la lectura de disc.


63

Figura 53.Classe frmCommitBlock

Al igual que la classe anterior s‟encarrega de la part gràfica de la consulta del commit

block de la part del journaling, en aquest cas només cal emmagatzemar la informació

bàsica.

Figura 54. Classe frmDescriptionBlock

Al igual que en el cas anterior dona la informació necessària i les propietats per a l‟

interfície gràfica dels description block de la part de journaling


64

6.4.2. Modelat dinàmic

Tot seguit passarem a veure els diagrames de seqüència dels processos més

rellevants que porta a cap l’aplicació.

Figura 55. Diagrama de seqüència d'obrir una imatge ReiserFS

6.5. Proves realitzades

Les proves realitzades per la posta a punt del treball i la verificació de totes les seves

funcionalitats en tot tipus de particions són les següents.

Particions de diverses mides: Es van utilitzar tres mides de particions 500KB,

100MB i de 200MB, per a comprovar que per gran que sigui la partició es pot

treballar sense problemes de mida.

Diverses mides de Bloc: S‟ha treballat també amb tres mides de bloc en aquest

cas son les mides de 1K, 4K i 8K. Aquestes proves van certificar no nomes la

mobilitat de totes les parts, aquesta part poc problemàtica en el sentit que aquest

sistema acostuma a utilitzar blocs més grans de 8k, per a la millor distribució de

l‟espai.

Profunditat de directoris: En aquest aspecte s‟ha arribat fins a 10 nivells de

directoris, simplement per garantir que la recursivitat es correcte.

Mida de fitxers: Aquesta prova consistia en el tractament de fitxers de gran

capacitat que no canvien en un bloc, en aquest cas s‟han passat fitxers des de 1K

fins a 100k, també es interessant per veure el funcionament del tail packing, que

optimitza la gestió d‟espai.


65

Nombre de fitxers dins d’un directori: S‟ha provat amb un nombre de fitxers

dins d‟un directori igual a 30, com hem explicat amb anterioritat, el

comportament varia, ja que el directori (en un node) s‟expandeix al node

contigu, maximitzant l‟aprofitament de l‟espai i la minimització del balanceig de

l‟arbre.

6.6. Posada en explotació

Per tal de poder utilitzar l‟aplicació i com s‟explica en el punt 7.1 es necessita tenir una

imatge ReiserFS creada. Apart de la imatge ReiserFS necessitarem òbviament el binari

amb l‟aplicació. Aquest binari però, no ens funcionarà en qualsevol màquina ja que en

estar creat amb .NET es necessitarà el framework de .NET que inclou les API‟s i

llibreries més comuns per al correcte funcionament d‟una aplicació desenvolupada en

aquest entorn.

Trobem diverses opcions per generar el binari:

Directament: Ens generarà un .exe que només es podrà executar en màquines

amb el framework .NET instal·lat.

Fent ús de la opció publish: Aquesta és una opció que ofereix el Visual Studio

que permet publicar una aplicació ja sigui en una web com en un cd. Aquesta

opció resulta molt útil ja que ens generarà un fitxer setup.exe que quan s‟executi

en qualsevol màquina es comprovarà si aquesta disposa del framework, en cas

negatiu es procedirà a la descarrega del framework i posteriorment s‟instal·larà

l‟aplicació en la màquina. Finalment tindrem instal·lada l‟aplicació en la

màquina completament funcional.


66

7.Manual de funcionament

7.1 Partició ReiserFs

Per a estudiar aquest sistema de fitxers, prèviament s‟ha de preparar una partició

formatada en ReiserFS, per a la creació hem utilitzat Ubuntu, una distribució de Linux

basat en Debian.

7.1.1 Creació de la partició ReiserFS

Primer per a crear una partició buida i indiquem la mida de la partició amb la

comanda

o dd if=/dev/zero of=<nomImatge> bs=1024 count=104857600

En aquest cas em indicat que creem una partició buida amb la mida de bloc

de 1024 (bs) i 100MB de mida de la partició (count).

A continuació hem de formatar la nostra partició buida, utilitzarem les següents

comandes.

o mkreiserfs -b 1024 -l label -d -f <nomImatge>

Per aquesta instrucció indiquem la mida de bloc ( -b 1024), una etiqueta

temporal, també forcem i mostrem totes les possibles errades que puguin

sorgir ( -f, -d respectivament), per últim indiquem a quina imatge apliquem

aquest format.

7.1.2 Muntar partició en Linux

Muntar la partició en Linux dona la opció per a tractar-lo com si fos un altre sistema de

fitxers a part del que ja tenim instal·lat, es a dir, ens permet introduir informació ja

siguin fitxers o directoris.

Utilitzem la següent comanda en Linux:

o mount <nomImatge> /mnt -t reiserfs -o loop=/dev/loop0

Aquí muntem la imatge en el /mnt, li indiquem que es tracta de una partició

amb el sistema de fitxers ReiserFS ( -t reiserfs), accedirem a aquesta partició

a traves de la carpeta /mnt.

o umount /mnt

Amb aquesta comanda estem desmuntant la partició i deixem lliure la

carpeta /mnt.


67

7.2 Execució del programa

Aquest software permetrà obrir les particions formatades en ReiserFS, desprès de fer

unes comprovacions i validar que és una partició vàlida, podrem realitzar diferents

operacions.

Un cop executem el programa s‟obre la finestra principal.

Figura 56. Finestra Principal ReiserFs_reader

En la finestra principal l‟única operació que es pot fer és la de carregar una imatge en

ReiserFS, un cop validat, els camps que estan a la part inferior esquerra s‟actualitzen

amb les dades del superblock i podem realitzar les quatre operacions per a estudiar la

partició.


68

7.2.1 Contingut Superblock

Com ja hem dit, després de validar la partició tenim accés al contingut del Superblock,

en la finestra que s‟obre a continuació tenim dos pastilles, la primera que esta per

defecte mostra la informació del Superblock, el nom del camp i el seu valor en decimal.

Figura 57. Informació del Superblock

La segona ens dona la opció de mirar com estan les dades a nivell de byte, un cop es

polsa el botó es marca en el camp de text el valor en hexadecimal del camp, en aquest

camp de text es veu l‟adreça en decimal i els valors en hexadecimal. També apareix el

valor en decimal.

Figura 58. Superblock valors nivell de bytes

Els camps més importants del Superblock ordenats per ordre d‟aparició són els

següents:

Mida de partició


69

Bloc del root

Bloc del Journal

Mida del Journal

Mida de bloc

Estat de la partició

Nombre de bitmaps

7.2.2 Contingut Bitmap Block

Aquesta part mostra l‟estat dels bitmap blocks, si hi ha més d‟un tenim l‟opció de

seleccionar quin volem veure.

Figura 59. Bitmap Block

El bitmap mostra l‟estat dels blocs que venen a continuació, en aquests cas els bits tenen

dos estats possibles.

Si el bloc està ocupat es marcarà amb 1

Si el bloc està lliure es marcarà amb 0.


70

Cada byte hexadecimal s‟indica de la següent manera

0xFF indica que els 8 blocs als que corresponen estan ocupats

7.2.3 Arbre de directoris

Podem veure en la figura 58, que aquest apartat ens dona l‟esquema de l‟arbre de fitxers

de la partició, disposem de l‟esquema a la part dreta, mentre que a l‟esquerra podem

veure les Propietats de l‟ítem, la codificació hexadecimal, tant pel fitxer en ASCII com

el seu contingut traduït.

En aquest apartat es disposa de varies opcions per a l‟usuari, en aquest cas, podem

consultar, les propietats del ítem com es veu en la captura següent. Veurem totes les

opcions que ens dona del fitxer només clicant a sobre del fitxer en l‟arbre de directoris.

Figura 60. Propietats del fitxer

L‟altre opció es mostra a continuació poder veure el contingut del fitxer.


71

Figura 61. Contingut d'un fitxer

7.2.4 Journal

Aquesta funcionalitat té mostra el funcionament del Journal amb detall, també esta

compost per dos opcions.

Journal Header, que mostra l‟identificador de la transacció, offset fins a

la següent transacció i l‟identificador del mount. A més de la adreça i els

bytes que mostren aquests valors.

Transaccions, es correspon amb la Figura 16, aquí es mostra la

transacció sencera, també tenim la opció de veure totes les transaccions

que hi ha al journal, a més a cadascun dels botons de la banda dreta es

mostra la part per separat a la que correspon, en aquest cas, el description

bloc, els blocs que es modifiquen en el journal i el commit bloc per a cada

transacció.


72

Figura 62. Journal

A més com a totes les finestres tenim la opció d‟ajuda que explicarà a que correspon

cada part i quines són les parts més importants.

Prement el botó de description bloc s‟activa el següent formulari, com es mostra en la

Figura 57, aquesta dona la opció de veure els valors del camps, i el seu valor en

hexadecimal al mapa de memòria i en decimal al costat del nom del camp.

En aquest formulari podem veure, els diferents camps, però el més important es els

blocs que s‟han modificat.


73

Figura 63.Formulari del Description Block

Al fer clic al botó “blocs Transició” activem el formulari i es pot veure els dos blocs,

tant el nou com el substituït, per en cas de restaurar el sistema a un punt anterior estable

es desfaran les transaccions.

També ens ofereix la opció de veure tots els blocs que s‟han modificat, tot això amb el

codi hexadecimal d‟aquesta manera es pot comparar els dos blocs i veure les

diferencies. També es pot apreciar, que el camp “Estat de partició” del SuperBlock es va

modificant.


74

Figura 64. Formulari de Blocs Modificats

L`última captura mostra el Commit Block que es un formulari similar al del Description

Block, mostra el mapeig de memòria i mostra els camps més importants.

Figura 65.Formulari del Commit Block


75

8.Cost realització projecte

El cost del projecte el desglossarem en les següents 5 etapes:

Documentació

Disseny

Implementació

Memòria

Proves

Un cop calculat el temps total aquest ens dóna unes 650 hores aproximadament. La

següent taula mostra la distribució d‟aquestes hores en les 5 etapes esmentades

anteriorment.

Etapes Hores Percentatge

Documentació 160 24%

Disseny 40 6%

Implementació 315 46%

Memòria 120 17%

Proves 45 7%

TOTAL 680 100%

Taula 22.Estimació del cost de realització de cada etapa

Com es pot observar la etapa que té un cost més elevat ha estat la d‟implementació

motivada pel fet de que s‟ha programat amb un llenguatge que no havíem tocat mai

(Visual C#). També caldria destacar la etapa de documentació ja que aquesta ens ha

portat un gran nombre d‟hores motivat pel fet de que pocs llibres aprofundeixen sobre el

funcionament intern del ReiserFS. Finalment també caldria esmentar la fase de proves

en que s‟han realitzat diferents proves d‟usabilitat per part del professorat de

l‟assignatura.


76

9.Conclusions

Amb l‟elaboració d‟aquest treball hem vist que el sistema de fitxers ReiserFS presenta

innovacions i millores respecte altres sistemes de fitxers. Mitjançant la creació de l‟eina

docent hem vist que ReiserFS empra una estructura de dades complexa però que

garanteix més robustesa en quan a la seguretat i la durabilitat de les dades.

El sistemes de fitxers el ReiserFS, va ser dissenyat per Hans Reiser com

desenvolupador en cap amb la col·laboració de l‟empresa namesys, va sortir al 2001 i va

introduir tres millores que han fet que sigui un bon sistema, la primera que té un sistema

de journaling ràpid, el cas es que una recuperació del sistema suposa molt poc temps en

cas d‟una caiguda de corrent o desconnexió inesperada del sistema. També esta basat en

arbres balancejats que presenta més robustesa en la seva implementació i amb

algoritmes més sofisticats preparats per a un sistema de fitxers, al inici del projecte els

programadors van veure aquesta problemàtica, però si es dissenya des de cero pensant

en la seva utilitat final es fan millor, finalment es més eficient respecte a la utilització de

l‟espai, en comparació amb alguns sistemes de fitxers, si s‟escriuen una gran quantitat

de fitxers petits, cadascun està en un bloc i es perd espai, en canvi en el sistema

ReiserFS minimitza l‟espai arribant a ser capaç de ficar una gran quantitat de fitxers en

un sol bloc, d‟aquesta manera s‟acostuma a estalviar una mitja del 6% de la capacitat

del disc dur.

En l‟actualitat a sortit al mercat un nou sistema de fitxers desenvolupat per la empresa

Namesys, el Reiser4, la evolució de ReiserFS que com ja hem vist presenta millores

considerables.

Per al estudiant aquest estudi també suposa una visió més amplia respecte als sistemes

de fitxers vistos a la assignatura de sistemes operatius, no només disposaran d‟un nou

sistema per ampliar els coneixements, sinó que és disposarà d‟una eina per acaba

d‟assolir els coneixements.

El procés per a realitzar l‟aplicatiu s‟ha empleat amb un entorn de programació dels que

no tenia coneixements previs, el programa s‟ha fet amb .NET, i més concretament

Visual C#. Es un llenguatge que s‟assembla a altres ja treballats com és el cas de C++

però presenta peculiaritats i característiques pròpies el que va fer que haguéssim de

documentar-nos i preparar amb més cautela la programació.

Per finalitzar dir que en certs casos al ser un sistema de fitxers open source fa que es

trobi molta informació variada el que dificulta que en certs casos el fet de consultar a un

lloc o a un altre fa que la informació varií i complica la feina, ja que s‟ha de validar. Per

altra banda en certs punts la mancança de fonts ha fet que la documentació s‟hagi hagut

de validar amb la poca informació disponible i certificar-la mitjançant l‟observació de la

informació a memòria.


77

10.Línies de futur

Un cop finalitzat el treball se‟ns acudeixen algunes línies de futur, tant per continuar el

treball com d‟altres nous, com es detalla a continuació.

Creació d’imatges ReiserFS: Per començar aquesta seria la primera millora

que se‟ns ha acudit respecte al aplicatiu per conseqüentment dotar l‟aplicatiu

com una eina completa respecte estudi del sistema ReiserFS. L‟usuari escolliria

la mida de la partició i la mida del bloc. Aquesta s‟hauria de mirar la

compatibilitat amb el compilador Linux per a crear particions ReiserFS

(mkreiserfs).

Creació / Esborrat de carpetes i fitxers: Aquesta millora implicaria en dotar

l‟aplicatiu de capacitat de modificar la imatge afegint carpetes i fitxers, aquesta

part es una part complicada ja que com hem explicat en l‟apartat 4.4 consisteix

en la creació de nodes, omplir l‟arbre, aplicar algoritmes d‟ordenació i tot això

sense tenir en compte l‟escriptura en el journal.

Estudis dels algoritmes d’ordenació d’arbres i possibles millors: Aquesta

millora de futur se‟ns ha ocorregut quan vam plantejar la opció de fer lectura i

escriptura en l‟aplicatiu, com hem plantejat anteriorment hi ha també diverses

opcions i es podria mirar quina es l‟opció més eficient i possibles millores tant

en l‟algorisme d‟ordenació, com en el tractament d‟inserció de nodes.

Accés a particions locals: Aquí podríem dotar l‟aplicació d‟accés a les

particions del disc local ReiserFS. Per poder accedir i compartir fitxers amb les

particions Windows, seria complicat ja que s‟hauria d‟estudiar la compatibilitat

dels sistemes de fitxers.

Creació d’un propi sistema de fitxers: Aquesta última opció es una línia de

futur que consistiria més encarada a un sistema de fitxers, amb el coneixement

adquirit a la assignatura es podria formar un sistema de fitxers amb les millors

prestacions dels diferents que s‟estudien a l‟assignatura com per exemple (Ext2,

ReiserFS, XFS), en aquest cas caldria un estudi profund i gran anàlisis, seria

més propi d‟un PFC.


78

11.Bibliografia

Pàgines Web

ELIE DE BRAUDER ( 2008, 12 de desembre).CodeDump: EliteDeBrauder [en línia].

CodeDump: ReiserSuperBlock. [Consultat: 13 agost 2008]. Disponible a Internet:

http://www.de-brauwer.be/wiki/wikka.php?wakka=ReiserSuperBlockw

[3] FLORIAN BUCHHLOZ ( 2006, gener). The Structure of the Reiser File System [en

línia]. [Consultat: 15 agost 2008]. Disponible a Internet:

http://homes.cerias.purdue.edu/~florian/reiser/reiserfs.php

GERSON KURZ ( 2007, 9 setembre).p-nand-q.com:Computer:rfstool:reiserFS docs

[en línia]: The ReiserFS filesystem [Consultat: 7 agost 2008]. Disponible a Internet:

http://p-nand-q.com/download/rfstool/reiserfs_docs.html

[2] JEREMY REIMER( 2008, 16 Març). From BFS to ZFS: past, present, and future of

file system[en línia].[Consultat: 11 desembre 2008]. Disponible a Internet :

http://arstechnica.com/articles/paedia/past-present-future-file-systems.ars/1

OPTIMUM DATA RECOVERY, INC. ( 2007, 21 d‟agost ). Linux ReiserFS File

System Data Recovery [en línia] : File System for Linux. [Consultat: 9 agost 2008].

Disponible a Internet: http://www.optimumrecovery.com/data/linux-reiserfs.html

[1]ZATOR SYSTEMS ( 2008, 25 d‟abril). Sistemas de ficheros [en línia] : Tecnologías

del PC. [Consultat: 9 desembre 2008]. Disponible a Internet:

http://www.zator.com/Hardware/H8_1_2a.htm

[4] ANDREAS KUNZ( 2004, 7 Març). YAReG - Yet Another R(eiser)FStool GUI.

[Consultat: 25 de setembre 2009]. Disponible a Internet: http://yareg.akucom.de/

[5] SOFTWARE PICKS NETWORK ( 2009, 2 gener). SPN Software Picks Network.

[Consultat: 25 de setembre 2009]. Disponible a Internet:

http://www.softpicks.net/software/UFS-Explorer-Batch-30500.htm

TFC’s

VELASCO, Albert (2008). Anàlisi de l’estructura del sistema d'arxius Ext2 i disseny i

implementació d’una aplicació de caire docent de suport a l’aprenentatge, Treball

Final de Carrera, Enginyeria i Arquitectura La Salle, Universitat Ramon Llull.

http://www.de-brauwer.be/wiki/wikka.php?wakka=ReiserSuperBlock

http://homes.cerias.purdue.edu/~florian/reiser/reiserfs.php

http://p-nand-q.com/download/rfstool/reiserfs_docs.html

http://arstechnica.com/articles/paedia/past-present-future-file-systems.ars/1

http://www.optimumrecovery.com/data/linux-reiserfs.html

http://www.zator.com/Hardware/H8_1_2a.htm

http://yareg.akucom.de/

http://www.softpicks.net/software/UFS-Explorer-Batch-30500.htm


79

FORCADA, Ricard (2008). Estudi del sistema de fitxers FAT32 i implementació d'una

aplicació docent, Treball Final de Carrera, Enginyeria i Arquitectura La Salle,

Universitat Ramon Llull.

escola universitÀria d‟enginyeria tÈcnica de...

Documents