# MINIX-fs
<!--
## TODO
- Ajouter slide expliquant comment débogger une image:
- en la montant puis en la parcourant
- "ls -i file" affiche le n° d'inode de "file
- "stat file" affiche n° inode, link count, etc.
- "tree --inodes -p -s -a" affiche arborescence avec n°inodes, permissions+type, tailles
- "-a" affiche également les fichiers cachés
-->
--
## Introduction à MINIX-fs
- MINIX-fs est le système de fichiers (FS) natif du système d'exploitation MINIX écrit par Andrew S. Tanenbaum en 1987
- Le but de MINIX-fs était :
- de répliquer la structure du FS de UNIX, mais sans les fonctionnalités avancées et complexes de ce dernier
- de fournir une aide à l'enseignement des systèmes de fichiers et des OS
--
## Linux et MINIX-fs
- Les premières versions du noyau Linux (1992) utilisaient MINIX-fs comme FS
- 1992 : Rémy Card implémente ext (Extended Filesystem) pour remplacer MINIX-fs
- ext est basé sur une structure similaire à MINIX-fs
- 1993 : Rémy Card publie ext2
- 2001 : Theodore Ts'o et d'autres publient ext3
- 2006 : la version instable de ext4 est publiée
- 2008 : la version stable de ext4 est publiée
--
## Versions de MINIX-fs
- Il existe 3 versions de MINIX-fs : v1, v2 et v3
- Nous présentons ici la v1 car c'est la plus simple
- Il existe deux variantes de MINIX-fs v1 :
- variante avec noms de fichiers de 14 caractères max (superblock magic value `0x137F`)
- variante avec noms de fichiers de 30 caractères max (superblock magic value `0x138F`)
--
## Comparaison MINIX-fs et ext2/3/4
Valeurs max pour les caractéristiques principales des FS :
Name | FS | File | Block | Extent | File length
--------------|--------|-------- |-------------|---------- |---------------
MINIX-fs v1.0 |256 MB |256 MB |1 KB (fixed) |n/a |14/30
ext |2 GB |2 GB |? |n/a |255
ext2 |32 TB |2 TB |8 KB |n/a |255
ext3 |32 TB |2 TB |8 KB |n/a |255
ext4 |1 EB |16 TB |4 KB |128 MB |255
<br>
<div style="font-size:0.85em">Remarque : ext3 est simplement ext2 avec l'ajout d'un journal</div>
--
## Structure générale
Structure générale sur disque de MINIX-fs v1.0
--
## Structure des inodes
Structure d'un inode dans MINIX-fs v1.0 :
```c
struct minix_inode {
u16 i_mode; // file type and permissions for file
u16 i_uid; // user id
u32 i_size; // file size in bytes
u32 i_time; // inode time
u8 i_gid; // group id
u8 i_nlinks; // number of dir entry pointing to
// this inode
u16 i_zone[7]; // direct pointers
u16 i_indir_zone; // indirect pointer
u16 i_dbl_indir_zone; // double indirect pointer
};
```
- **Important** : structure sur disque stockée selon l'ordre *little-endian*
- Taille d'un inode en bytes ?
--
## Structure du mode du fichier
Format du champs `i_mode` (16 bits) de l'inode :
<div style="font-size:0.8em">
Bits | Description ||
----------------| -------------------------- |---------------------------
`12-15` | Type de fichier |`0x1` : named pipe (FIFO)<br>`0x2` : char device<br>`0x4` : directory<br>`0x6` : block device<br>`0x8` : regular file<br>`0xA` : symbolic link
`11` | SUID bit |
`10` | SGID bit |
`9` | Sticky bit |
`6-8` | user permissions (rwx) |
`3-5` | group permissions (rwx) |
`0-2` | others permissions (rwx) |
</div>
--
## Structure des entrées de répertoires
Structure d'une entrée de répertoire dans MINIX-fs v1.0 :
```c
// Variante : superblock magic 0x137F
#define MINIX_NAME_LEN 14
struct minix_dir_entry {
u16 inode;
char name[MINIX_NAME_LEN];
};
```
- Taille d'un `dir_entry` en bytes ? \
`$14*sizeof(char) + 2$ bytes ($16$ bits) $= 16$ bytes si $sizeof(char)=1$ byte` <!-- .element class="fragment" -->
--
## Structure du superbloc
Structure du superbloc dans MINIX-fs v1.0 :
```c
struct minix_super_block {
u16 s_ninodes; // total number of inodes
u16 s_nzones; // total number of blocks (including superblock)
u16 s_imap_blocks; // inodes bitmap size in blocks
u16 s_zmap_blocks; // data blocks bitmap size in blocks
u16 s_firstdatazone; // index of first data block
u16 s_log_zone_size; // block size in bytes = 1024*2^s_log_zone_size
u32 s_max_size; // max file size in bytes
u16 s_magic; // 0x137f = v1 with 14 characters dir_entry
// 0x138f = v1 with 30 characters dir_entry
u16 s_state; // was the FS properly unmounted?
};
```
- Taille du superbloc en bytes ? \
`$20$ bytes` <!-- .element class="fragment" -->
--
## Exemple de superbloc
- Soit un disque de 20 MB et une taille de bloc de 1 KB\
`$\rightarrow$ fs_blocks` = nombre de blocs au total
- Nombre inodes = `(fs_blocks/3 + 32) & 0xFFFFFFE0`<sup>1</sup>
```c
struct minix_super_block {
u16 s_ninodes = 6848; // total number of inodes
u16 s_nzones = 20480; // total number of blocks
// = (20*1024^2)/1024
u16 s_imap_blocks = 1; // inodes bitmap size in blocks
// need 6848 bits
// -> 1 block = 8192 bits
u16 s_zmap_blocks = 3; // data blocks bitmap size in blocks
// need 20480 bits -> 3 blocks = 8192*3 bits
u16 s_firstdatazone = 220; // index of first data block
u16 s_log_zone_size = 0; // block size = 1024*2^s_log_zone_size
// = 1024*2^0 = 1024
u32 s_max_size = 268966912; // max file size in bytes
// = (7+(1024/2)+(1024/2)^2)*1024
u16 s_magic = 0x137F; // 0x137f Minix filesystem version 1
u16 s_state = 1; // was the FS properly unmounted?
};
```
<!-- .element style="font-size:0.5em" -->
<small>1: permet d'arrondir au prochain multiple de la taille d'un inode</small>
--
## Exemple de superbloc
```c
struct minix_super_block {
u16 s_ninodes = 6848; // total number of inodes
u16 s_nzones = 20480; // total number of blocks
// = (20*1024^2)/1024
u16 s_imap_blocks = 1; // inodes bitmap size in blocks
// need 6848 bits
// -> 1 block = 8192 bits
u16 s_zmap_blocks = 3; // data blocks bitmap size in blocks
// need 20480 bits -> 3 blocks = 8192*3 bits
u16 s_firstdatazone = 220; // index of first data block
u16 s_log_zone_size = 0; // block size = 1024*2^s_log_zone_size
// = 1024*2^0 = 1024
u32 s_max_size = 268966912; // max file size in bytes
// = (7+(1024/2)+(1024/2)^2)*1024
u16 s_magic = 0x137F; // 0x137f Minix filesystem version 1
u16 s_state = 1; // was the FS properly unmounted?
};
```
<!-- .element style="font-size:0.5em" -->
--
## Exemple d'inode - fichier répertoire
Contenu de l'inode 1, la racine du FS
```c
struct minix_inode {
u16 i_mode = 0x41ED; // 0x4 = directory
// 0x1ED = 755 in octal
// = rwx r-x r-x
u16 i_uid = 0; // 0 = root
u32 i_size = 256; // 256/16 = 16 dir_entry
u32 i_time = 1701436374; // seconds since 1/1/1970
u8 i_gid = 0; // 0 = root
u8 i_nlinks = 8; // 8 dir entries point to
// this inode
u16 i_zone[7] = {220, 0, 0, 0, 0, 0, 0 }; // 1 data block
u16 i_indir_zone = 0; // no indirect block
u16 i_dbl_indir_zone = 0; // no double indirect block
};
```
--
## Exemple de bloc de données - contenu répertoire
1er bloc de données référencé par l'inode 1
- bloc 220 (offset = 220*1024 = 0x37000)
```
00037000 01 00 2E 00 00 00 00 00 00 00 00 00 00 00 00 00 ................
00037010 00 00 79 6F 00 00 00 00 00 00 00 00 00 00 00 00 ..yo............
00037020 01 00 2E 2E 00 00 00 00 00 00 00 00 00 00 00 00 ................
00037030 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................
00037040 02 00 72 6F 6F 74 00 00 00 00 00 00 00 00 00 00 ..root..........
00037050 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................
00037060 03 00 62 69 6E 00 00 00 00 00 00 00 00 00 00 00 ..bin...........
00037070 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................
00037080 04 00 75 73 72 00 00 00 00 00 00 00 00 00 00 00 ..usr...........
00037090 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................
000370A0 0A 00 65 74 63 00 00 00 00 00 00 00 00 00 00 00 ..etc...........
000370B0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................
000370C0 0F 00 74 6D 70 00 00 00 00 00 00 00 00 00 00 00 ..tmp...........
000370D0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................
000370E0 32 00 64 65 76 00 00 00 00 00 00 00 00 00 00 00 2.dev...........
000370F0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................
```
<!-- .element style="font-size:0.4em" -->
<div style="font-size: 0.8em">
- Les noms `.` (0x2E) et `..` (0x2E2E) pointent sur l'inode 1 (la racine)
- 7 répertoires : `root`, `bin`, `usr`, `etc`, `tmp`, `dev` (inodes 1, 2, 3, 4, 0xA, 0xF, 0x32)
- 8 `dir_entry` inutilisées (inodes à 0) ; rappel : une entrée fait 16 bytes
</div>
--
## Exemple d'inode - fichier répertoire
Contenu de l'inode 2, répertoire `/root`
```c
struct minix_inode {
u16 i_mode = 0x41ED; // 0x4 = directory
// 0x1ED = 755 in octal
// = rwx r-x r-x
u16 i_uid = 0; // 0 = root
u32 i_size = 160; // 160/16 = 10 dir_entry
u32 i_time = 1701436512; // seconds since 1/1/1970
u8 i_gid = 0; // 0 = root
u8 i_nlinks = 2; // 2 dir entries point to
// this inode
u16 i_zone[7] = {221, 0, 0, 0, 0, 0, 0 }; // 1 data block
u16 i_indir_zone = 0; // no indirect block
u16 i_dbl_indir_zone = 0; // no double indirect block
};
```
--
## Exemple de bloc de données - contenu répertoire
1er bloc de données référencé par l'inode 2
- bloc 221 (offset = 221*1024 = 0x37400)
```
00037400 02 00 2E 00 00 00 00 00 00 00 00 00 00 00 00 00 ................
00037410 6C 03 6C 69 6E 75 78 00 00 00 00 00 00 00 00 00 l.linux.........
00037420 01 00 2E 2E 00 00 00 00 00 00 00 00 00 00 00 00 ................
00037430 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................
00037440 09 00 73 79 73 74 65 6D 00 00 00 00 00 00 00 00 ..system........
00037450 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................
00037460 0B 00 68 65 6C 6C 6F 2E 63 00 00 00 00 00 00 00 ..hello.c.......
00037470 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................
00037480 0E 00 2E 62 61 73 68 5F 6C 6F 67 69 6E 00 00 00 ...bash_login...
00037490 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................
```
<!-- .element style="font-size:0.5em" -->
<div style="font-size: 0.8em">
- Le nom `.` (0x2E) pointe sur l'inode 2 (lui même)
- Le nom `.` (0x2E2E) pointe sur le répertoire parent, l'inode 1 (la racine)
- Il y a 2 répertoires : `linux` (inode 0x36C) et `system` (inode 0x9)
- Il y a 2 fichiers : `hello.c` (inode 0xB) et `.bash_login` (inode 0xE)
- Il y a 4 `dir_entry` inutilisées (inodes à 0)
</div>
--
## Exemple d'inode - fichier régulier
Contenu de l'inode 11 (0xB)
```c
struct minix_inode {
u16 i_mode = 0x81A4; // 0x8 = regular file
// 0x1A4 = 644 in octal
// = rw- r-- r--
u16 i_uid = 0; // 0 = root
u32 i_size = 63; // 1 data block (1 KB/block)
u32 i_time = 1426700385; // seconds since 1/1/1970
u8 i_gid = 0; // 0 = root
u8 i_nlinks = 1; // 1 dir entry points to this inode
u16 i_zone[7] = { 583 0 0 0 0 0 0 }; // 1 data block
u16 i_indir_zone = 0; // no indirect block
u16 i_dbl_indir_zone = 0; // no double indirect block
};
```
--
## Exemple de bloc de données - contenu fichier régulier
Contenu du 1er bloc de données référencé par l'inode 11\
- bloc 583 (offset = 583*1024 = 0x91C00)
```
00091C00 23 69 6E 63 6C 75 64 65 20 3C 73 74 64 69 6F 2E #include <stdio.
00091C10 68 3E 0A 0A 76 6F 69 64 20 6D 61 69 6E 28 29 0A h>..void main().
00091C20 7B 0A 09 09 70 72 69 6E 74 66 28 22 48 65 6C 6C {...printf("Hell
00091C30 6F 20 57 6F 72 6C 64 5C 6E 22 29 3B 0A 7D 0A 00 o World\n");.}..
00091C40 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................
00091C50 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................
00091C60 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................
00091C70 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................
00091C80 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................
00091C90 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................
00091CA0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................
00091CB0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................
00091CC0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................
00091CD0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................
```
--
## Exemple d'inode - fichier régulier
Contenu de l'inode 16
```c
struct minix_inode {
u16 i_mode = 0x81C9; // 0x8 = regular file
// 0x1C9 = 711 in octal
// = rwx --x --x
u16 i_uid = 0; // 0 = root
u32 i_size = 283652; // 278 data blocks (1 KB/block)
u32 i_time = 1426700385; // seconds since 1/1/1970
u8 i_gid = 0; // 0 = root
u8 i_nlinks = 2; // 2 dir entries point to this inode
u16 i_zone[7] = { 588 589 590 591 592 593 594 };
// 7 data blocks
u16 i_indir_zone = 595; // block 595 contains 271 pointers
u16 i_dbl_indir_zone = 0; // no double indirect block
};
```
--
## Exemple de bloc de données - contenu fichier régulier
Contenu du bloc indirect référencé par l'inode 11\
- bloc 595 (offset = 595*1024 = 0x94C00)
```
00094C00 54 02 55 02 56 02 57 02 58 02 59 02 5A 02 5B 02 T.U.V.W.X.Y.Z.[.
00094C10 5C 02 5D 02 5E 02 5F 02 60 02 61 02 62 02 63 02 \.].^._.`.a.b.c.
00094C20 64 02 65 02 66 02 67 02 68 02 69 02 6A 02 6B 02 d.e.f.g.h.i.j.k.
00094C30 6C 02 6D 02 6E 02 6F 02 70 02 71 02 72 02 73 02 l.m.n.o.p.q.r.s.
00094C40 74 02 75 02 76 02 77 02 78 02 79 02 7A 02 7B 02 t.u.v.w.x.y.z.{.
00094C50 7C 02 7D 02 7E 02 7F 02 80 02 81 02 82 02 83 02 |.}.~...........
00094C60 84 02 85 02 86 02 87 02 88 02 89 02 8A 02 8B 02 ................
00094C70 8C 02 8D 02 8E 02 8F 02 90 02 91 02 92 02 93 02 ................
00094C80 94 02 95 02 96 02 97 02 98 02 99 02 9A 02 9B 02 ................
00094C90 9C 02 9D 02 9E 02 9F 02 A0 02 A1 02 A2 02 A3 02 ................
00094CA0 A4 02 A5 02 A6 02 A7 02 A8 02 A9 02 AA 02 AB 02 ................
...
```
- Prochains blocs de données : 0x254, 0x255, 0x256, 0x257, ...
--
## Important : inodes
<div style="font-size: 0.8em">
- Le nombre total d'inodes pouvant être créés dans le FS est indiqué par le champs `ninodes` du superbloc
- La table des inodes possède `ninodes` entrées
- Le premier inode de la table (à l'indice 0) est l'inode 1, il n'y a donc pas d'inode 0 !
- **Attention** : le bit 0 du bitmap indique l'état de l'inode 0 !
- le bit 0 est toujours à 1 (utilisé), bien que l'inode 0 n'existe pas
- un FS vide aura donc 2 bits à 1 dans le bitmap\ : le bit 0 (inode 0) et le bit 1 (inode 1 = répertoire racine)
</div>
<br>
<fieldset>
<legend>En conséquence :</legend>
- Pour lire le contenu de l'inode `n`, il faut lire l'entrée à l'indice `(n-1)` dans la table des inodes
- Pour savoir si l'inode `n` est utilisé, il faut lire le bit à l'indice `n` dans le bitmap des inodes
</fieldset>
</div>
--
## Important : blocs de données
<div style="font-size: 0.8em">
- Les n° de blocs dans l'inode sont relatifs au début du FS
- Le bitmap des blocs de données indique uniquement l'état des **blocs de données** utilisés (donc pas superbloc, bitmaps, etc.)
- **Attention** : le bit 0 du bitmap des blocs de données est à **ignorer** !
- \footnotesize il est toujours à 1 et ne représente aucun bloc de données
- le bit 1 du bitmap correspond au bloc `firstdatazone` indiqué dans le superbloc
- il correspond donc au premier bloc de données
</div>
<br>
<fieldset>
<legend>En conséquence :</legend>
- Tout bloc n indiqué dans l'inode correspond à l'indice `(n-firstdatazone+1)` dans le bitmap des blocs de données
- Nombre total de blocs de données : `(nzones-firstdatazone)`
<small> *firstdatazone* et *nzones* sont les champs du même nom dans le superbloc</small>
</fieldset>
<!--
- où `firstdatazone` est le champs du même nom dans le superbloc (= nombre de blocs utilisés par\ : superbloc + bitmaps + table d'inodes)
- \footnotesize si le premier bloc de données est le bloc 110, celui-ci correspond au bit 1 dans le bitmap
- le bit 3 du bitmap correspond donc au bloc 113, etc.
-->
--
## Rappel : *endianness* (1/2)
- L'*endianness* défini la manière dont les entiers sont stockés en mémoire
- ***Big-endian***
- le byte le plus significatif (d'un mot) est stocké à l'adresse la plus basse
- le byte le moins significatif est stocké à l'adresse la plus haute
- ***Little-endian***
- le byte le plus significatif (d'un mot) est stocké à l'adresse la plus haute
- le byte le moins significatif est stocké à l'adresse la plus basse
--
## Rappel : *endianness* (2/2)
Exemple de valeurs 8 bits, 16 bits et 32 bits, en représentation hexadécimale, où les adresses "grandissent" de gauche à droite :
**Taille de mot** | **Valeur** | **Big-endian** | **Little-endian**
----------------- | ----------- | -------------- | -----------------
8 bits (1 byte) | `4c` | `4c` | `4c`
16 bits (2 bytes) | `4c3f` | `4c 3f` | `3f 4c`
32 bits (4 bytes) | `4c3f85ed` | `4c 3f 85 ed` | `ed 85 3f 4c`
--
## Sérialisation/déserialisation de structure
- **Sérialisation** de structure = écriture, en une opération, d'une structure sur un fichier, un socket, un pipe, etc.
- typiquement via un appel à `write` ou `fwrite`
<br></br>
- **Déserialisation** de structure = lecture, en une opération, depuis un fichier, un socket, un pipe, etc. dans une structure
- typiquement via un appel à `read` ou `fread`
--
## Danger avec la sérialisation/déserialisation
```c
struct st1 { struct __attribute__ ((__packed__)) st2 {
uint8_t tab[7]; uint8_t tab[7];
uint16_t n; uint16_t n;
uint32_t big; uint32_t big;
uint8_t x; uint8_t x;
uint8_t y; uint8_t y;
}; };
int main() {
printf("%ld %ld\n", sizeof(struct st1), sizeof(struct st2));
return 0;
}
```
- Affichage ? `20 15` <!-- .element class="fragment" -->
- Pourquoi ? <text>Le compilateur ajoute des bytes de padding pour optimiser l'alignement des structures.</text> <!-- .element class="fragment" -->
- Conséquence : <text>**toujours** utiliser l'attribut `__packed__` sur les structures sérialisées !</text> <!-- .element class="fragment" -->