Elaborato di Sistemi Operativi I, II e Laboratorio; A.A. 2006/07
Autori: Rossi Paolo 123456 e Bianchi Mario 234567
Appello: giugno 2007
Implementerete comandi per gestire floppy disk formattati secondo il filesystem FAT. La vostra soluzione funzionerà in spazio utente. Il floppy disk verrà manipolato per mezzo del file speciale /dev/fd0. Sarà possibile utilizzare un'immagine del floppy salvata su file. Quest'ultima feature sarà molto utile per realizzare test automatizzati di correttezza della soluzione.
$ fatdir aaa txt 4 05-16-2004 21:55 bbb txt 1600 05-16-2004 22:10 ccc txt 4 05-16-2004 21:55 sub <DIR> 05-16-2004 21:57 ggg txt 4 05-16-2004 22:01 iii txt 4 05-16-2004 22:01 $ fatdir sub . <DIR> 05-16-2004 21:57 .. <DIR> 05-16-2004 21:57 ddd txt 4 05-16-2004 21:58 eee txt 4 05-16-2004 21:58 fff txt 4 05-16-2004 21:58 $L'indicazione <DIR> indica che il file è una directory. Se il file non è una directory, allora viene listato il numero di byte che contiene. Segue la data di ultima modifica. Per l'appello di giugno è sufficiente implementare accettare nomi di directory semplici, come nell'esempio qui sopra. A partire da luglio sarà necessario accettare anche un pathname arbitrario, assoluto o relativo, utilizzando come separatore il carattere "/". Ad esempio: "/foo/bar.txt", oppure "zot/zap.html".
$ fatcat aaa.txt ciao $ fatcat foobar fatcat: file foobar does not exist $
$ fatdir aaa txt 4 05-16-2004 21:55 bbb txt 1600 05-16-2004 22:10 $ fatdel aaa.txt $ fatdir bbb txt 1600 05-16-2004 22:10 $
$ fatdir aaa txt 4 05-16-2004 21:55 aaa.txt bbb txt 1600 05-16-2004 22:10 aaa.txt SISTEM~1 TXT 479 05-16-2004 22:13 sistemi-operativi-1-e-2.txt $
$ fatdir aaa txt 4 05-16-2004 21:55 bbb txt 1600 05-16-2004 22:10 $ fatren aaa.txt foo.bar $ fatdir foo bar 4 05-16-2004 21:55 bbb txt 1600 05-16-2004 22:10 $
Il lavoro deve essere opportunamente documentato. La documentazione deve comprendere:
La documentazione deve essere presentata sotto forma di file di testo, di nome fat.txt. Cercate di fare in modo che si presenti bene, anche se si tratta di un semplice file di testo. (File in formati proprietari prodotti da word processor non verranno presi in considerazione).
Prendete spunto da questo documento per lo stile grafico in cui formattare la vostra documentazione.
La documentazione deve essere concisa. Non eccedete le quattro pagine.
Evitate gli errori di ortografia e di sintassi. La precisione è una qualità fondamentale per un informatico, e va coltivata anche nella scrittura di documentazione. (Saremo tolleranti sotto questo punto di vista con gli studenti di origine straniera.)
La directory skel contiene uno scheletro di soluzione. Potete partire da questi file per realizzare la vostra soluzione. Fornisco anche alcune immagini di floppy disk (file con estensione .img) per i vostri test.
Nota. Per ottenere da un floppy il file immagine, si usa un comando simile a questo:
dd if=/dev/fd0 of=floppy.imgPer copiare dal file immagine al floppy, si usa il comando
dd if=floppy.img of=/dev/fd0
The File Allocation Table (FAT) was designed and coded in Feb., 1976 by a kid named Bill Gates during a five day stay at the Hilton Hotel in Albuquerque. He developed it for a version of Basic that could store programs and data on floppy disks. The FAT design was incorporated by Tim Patterson in an early version of an operating system for the Intel 8086 chip. Gates bought the rights to the system, then rewrote it to create the first version of DOS. As a direct result, Gates is the richest man in America. — H. Gilbert, FAT File SystemIl sistema operativo MS-DOS definisce un particolare formato per i floppy disk. Un concetto importante è il logical sector address, o indirizzo logico dei settori (intendiamo qui per "settore" sia lo "spicchio" individuato da due raggi sulla superficie del disco, che il "blocco" di informazioni più piccolo che è possibile individuare all'interno del disco; nel caso dei floppy il blocco contiene 512 byte. Il contesto del discorso dovrebbe permettere di disambiguare i due usi della parola. Quest'ambiguità si riscontra in tutta la letteratura sui dischi magnetici, per cui tanto vale abituarcisi.) Il settore logico 0 corrisponde al settore sulla faccia 0, traccia 0 e settore 1 del disco. (Facce e tracce sono numerate da 0, mentre i settori sono numerati da 1, per motivi "storici", cioè nessuno sa spiegare perché ma è così lo stesso.)
Prima che un floppy possa essere usato deve essere formattato. In particolare, il settore logico 0 contiene un area riservata, detta anche boot sector o boot record. Il boot sector deve essere organizzato secondo la seguente tabella:
Field Offset Length ... Bytes per sector 0x0b 2 Sectors per cluster 0x0d 1 Reserved Sectors 0x0e 2 Number of FATs 0x10 1 Number of root direct. entries 0x11 2 Number of logical sectors 0x13 2 Media descriptor 0x15 1 Sectors Per FAT 0x16 2 Sectors Per Track 0x18 2 Number of heads 0x1a 2 Number of hidden sectors 0x1c 4 ...
La struttura generale di un floppy è illustrata nella seguente tabella:
Settore logico contenuto
-------------- ---------
0 boot sector
1 primo settore della prima FAT
...
10 primo settore della seconda FAT, se esiste; vedi
0x10 nel boot sector
19 primo settore della root directory
xx ultimo settore della root directory; vedi 0x11
nel boot sector
xx+1 inizio dell'area dati del floppy
La FAT di solito è duplicata, per cui il byte all'indirizzo 0x10 nel
boot sector ci dice quante copie della FAT esistono nel disco; di
solito 2. La FAT è replicata perché è la struttura dati più
importante; se la prima copia è danneggiata, se ne usa un'altra. La
locazione 0x11 nel boot sector indica quante posizioni al massimo sono
disponibili nella root directory. Un floppy da 1.44 MB può contenere
un massimo di 224 entries, usando 14 settori per la root directory.
In questo caso xx = 18+14 = 32.
Ogni floppy ha una geometria, specificata da:
Per gestire dischi di dimensioni sempre più grandi, il filesystem FAT utilizza la nozione di cluster di settori: invece di allocare i settori uno per volta, li alloco a gruppi di due o quattro. In questo modo le entry della FAT indicano il numero di cluster, e non il numero di settore. Dunque la dimensione del cluster definisce la quantità minima di spazio che può essere allocata per un file.
Ciascuna directory entry occupa 32 byte. Il formato di ciascuna entry è il seguente:
offset lung. descrizione ------ ----- ----------- 0x00 8 nome 0x08 3 estensione 0x0B 1 attributi (bit fields) 0x0C 10 (non usato) 0x16 2 ora di ultima modifica (codificata come ora*2048 + min*32 + sec/2) 0x18 2 data di ultima modifica (codif. come (anno-1980)*512 + mese*32 + giorno) 0x1A 2 numero del primo cluster 0x1C 4 dimensione del file in bytesTutti gli interi sono rappresentati in formato little-endian: il byte meno significativo viene salvato per primo.
Il filename e l'estensione sono rappresentati come caratteri ASCII maiuscoli. Le entries non valide hanno il nome che inizia con il byte 0x00 (che indica che la entry non è mai stata usata) o il byte 0xe5 (la entry è stata usata, ma poi è stata cancellata.)
Il numero del primo cluster può trarre in inganno. Non può fare riferimento a settori che sono utilizzati per il boot sector, la FAT, la root directory, e così via. Quindi il numero è sempre relativo al primo cluster utilizzabile: il cluster numero k corrisponde al settore logico 31 + k (assumendo, come è usuale per i floppy, che il numero di settori per cluster sia 1)
Il byte degli attributi è una mappa di bit:
bit mask attributo -------------------- 0 0x01 read-only 1 0x02 hidden 2 0x04 system 3 0x08 volume label 4 0x10 subdirectory 5 0x20 archive 6 0x40 non usato 7 0x80 non usato
Il formato delle directory entries è lo stesso sia per la root directory che per le subdirectories. La root directory viene realizzata in un insieme di settori contigui, e ha un numero massimo di entries, specificato nel boot sector. Le subdirectories invece sono rappresentate come gli altri file, come un insieme di settori non necessariamente contigui.
Le prime due entries della FAT (per i settori 0 e 1) sono riservate. La prima entry contiene un descrittore del formato del floppy. Per un comune floppy da 1.44 MB il descrittore ha il valore 0x0f0, che indica che il floppy ha 2 facce, 80 cilindri, e 18 settori per traccia.
I possibili valori le entries nella FAT sono:
0x000 il cluster è libero 0xff0-0xff6 il cluster è riservato 0xff7 cluster danneggiato 0xff8-0xfff ultimo cluster del file altrimenti il numero del cluster successivo a questo in un file
La FAT viene rappresentata in formato impaccato, per risparmiare spazio sul disco. Questo significa che, anche se sarebbe stato più semplice rappresentare una FAT entry di 12 bit su due byte, in realtà si usano 3 byte per rappresentare 2 entries.
Se la FAT entry ha un numero pari, diciamo 2k, allora
Facciamo un esempio. Supponiamo di avere un floppy da 1.44MB appena formattato, e di scriverci sopra un file. Il nuovo file inizia nel cluster 2 (perché le prime due entry della FAT sono riservate.) Gli altri cluster del file seguono in maniera consecutiva, perché il floppy non era frammentato quando abbiamo scritto il file. L'inizio della FAT è ora come segue:
f0 ff ff 03 40 00 05 60 00 07 80 00 09 f0 ff 00 00 00 00 00 00 00 00 ...I primi 3 byte f0 ff ff sono le due entry riservate e li possiamo ignorare. La entry numero 2 si trova nei byte 3 e 4; poiché il byte 4 contiene i bit più significativi, otteniamo 0x003; questo indica che il file che inizia al cluster 2 continua al cluster 3. La entry numero 3 si trova nei byte 4 e 5; dalle formule otteniamo 0x004; quindi il file che usa il cluster 3 prosegue nel cluster 4. Alla entry 4 troviamo 0x005, e così via. Proseguendo così arriviamo alla entry 9, che contiene 0xfff. Tutti gli altri cluster sono ancora inutilizzati, così le entry corrispondenti hanno il valore riservato 0x000.