Trabalho II: Sistema de Ficheiros Virtual

Objectivo

O objectivo principal deste trabalho é permitir que os alunos adquiram uma maior sensibilidade e conhecimento do funcionamento de um sistema de gestão de ficheiros. Em particular, pretende-se que os alunos desenvolvam uma aplicação capaz de emular um sistema simplificado de gestão de ficheiros do tipo FAT. Mais concretamente, isso inclui o compreensão da estrutura de dados para organização de um tal sistema, a implementação de rotinas de I/O para acesso ao mesmo, e a implementação de um conjunto de utilitários de mais alto-nível para manipulação de ficheiros e directórios.

O que é um Sistema de Ficheiros?

Um sistema de ficheiros pode ser visto como um conjunto contíguo de blocos em que se destacam três regiões principais: o superblock (a que corresponde o bloco 0), a FAT (a que correspondem os blocos seguintes, começando no 1) e a região para dados propriamente dita (a que correspondem os restantes blocos).

O superblock serve para guardar informação geral sobre o sistema de ficheiros. Considere a seguinte estrutura para o superblock:

#define CHECK_NUMBER 2008 typedef struct superblock_entry { int check_number; // número que permite identificar o sistema como válido int block_size; // tamanho de um bloco {256, 512(default) ou 1024 bytes} int fat_type; // tipo de FAT {8, 10(default) ou 12} int root_block; // número do 1º bloco a que corresponde o directório raíz int free_block; // número do 1º bloco da lista de blocos não utilizados } superblock;

A FAT (file allocation table) é um conjunto contíguo de entradas, numeradas de 0 até 2^fat_type - 1, que permite referenciar os blocos de dados livres e os blocos de dados utilizados por cada ficheiro/directório. Através do valor de free_block é possível aceder ao primeiro bloco de dados não utilizado. Para percorrer a lista completa dos blocos não utilizados deve seguir-se a referência guardada na entrada FAT de igual ordem. Um valor de -1 numa entrada FAT marca o fim da lista.

Os blocos de dados (data blocks) são utilizados para guardar os dados dos ficheiros e dos directórios. O número de blocos de dados é igual ao número de entradas na FAT, e cada bloco de dados corresponde à entrada na FAT de igual ordem. À semelhança dos blocos não utilizados, os blocos de dados utilizados por um ficheiro/directório são mantidos através de uma lista na FAT. Um ficheiro não é nada mais do que um conjunto de blocos de dados. A FAT especifica quais os blocos de dados utilizados pelo ficheiro e a ordem dos blocos no ficheiro é a ordem representada na FAT. A implementação de directórios é de certa forma idêntica à dos ficheiros (o primeiro bloco do directório raíz "/" é definido pelo campo root_block do superblock), a diferença reside no facto dos blocos de dados para directórios seguirem um formato predefinido. Um bloco de dados para um directório, pode ser visto como um array de estruturas de dados do tipo que se segue, em que cada uma dessas estruturas corresponde a um ficheiro/subdirectório do directório em causa.

#define TYPE_DIR 'D' #define TYPE_FILE 'F' #define TYPE_FREE '-' #define MAX_NAME_LENGHT 20 typedef struct directory_entry { char type; // tipo da entrada (TYPE_DIR, TYPE_FILE ou TYPE_FREE) char name[MAX_NAME_LENGHT]; // nome da entrada unsigned char day; // dia em que foi criada (entre 1 e 31) unsigned char month; // mes em que foi criada (entre 1 e 12) unsigned char year; // ano em que foi criada (entre 0 e 255 - 0 representa o ano de 1900) int size; // tamanho em bytes (0 se TYPE_DIR) int first_block; // primeiro bloco de dados } dir_entry;

Como simplificação, vamos considerar que cada entrada na FAT é sempre representada por um inteiro (4 bytes). Sendo assim o número de blocos necessários para guardar a FAT é igual a 2^fat_type * 4 / block_size. Como o número de blocos de dados deverá ser igual ao número de entradas na FAT, o número de blocos total num sistema de ficheiros resulta da fórmula 1 + 2^fat_type * 4 / block_size + 2^fat_type. Multiplicando o número de blocos por block_size obtemos o tamanho do sistema de ficheiros.

Trabalho

A emulação do sistema de ficheiros deverá ser feita sobre ficheiros comuns estruturados segundo a organização descrita acima. Sendo assim, ao iniciar o emulador (vfs) deverá indicar-se como argumento o ficheiro sobre o qual o emulador deverá funcionar (exemplo: vfs discoC). Se o ficheiro não corresponder a um sistema de ficheiros válido (verificar o check_number e se o tamanho do ficheiro está de acordo com o block_size e o fat_type) deve ser reportado um erro e o emulador deve terminar. Para iniciar um novo sistema de ficheiros, deverá indicar-se o tamanho de cada bloco (opção -b seguido do tamanho em bytes: 256, 512 ou 1024), o tipo de FAT (opção -f seguido do tipo: 8, 10 ou 12) e o nome do ficheiro sobre o qual o emulador deverá funcionar (exemplo: vfs -b1024 -f12 discoC).

Após iniciar o emulador do sistema de gestão de ficheiros, o utilizador deve poder comunicar com o emulador através de uma linha de comandos onde poderão ser invocados uma série de utilitários para manipulação de ficheiros e directórios. Reutilize o código do primeiro trabalho para lidar com a linha de comandos. O código que implementa a parte da formatação do sistema de ficheiros pode ser obtido aqui.

Manipulação de directórios

Nesta etapa pretende-se que implemente os utilitários para manipulação de directórios. Segue-se uma breve descrição de cada um deles:

mkdir dir - cria um subdirectório com nome dir no directório actual.
rmdir dir - remove o subdirectório dir (se vazio) do directório actual.
cd dir - move o directório actual para dir.
pwd - escreve o caminho absoluto do directório actual.

ls - lista o conteúdo do directório actual. A listagem deve ser apresentada ordenada pelo nome de cada entrada (usando o código ascii dos caracteres) e cada entrada deve seguir o seguinte formato: <name> <day>-<month>-<year> [<DIR>|<size>]. Segue-se um pequeno exemplo:

. 01-Fev-2005 DIR .. 01-Fev-2005 DIR Directorio 27-Ago-2005 DIR fich_tamanho_1024 01-Abr-2006 1024 fich_tamanho_1025 09-Mai-2005 1025 fich_tamanho_3073 01-Out-2005 3073 nome_com_tamanho_max 29-Jan-2006 DIR

Para todos os utilitários, considere apenas os casos em que o argumento dir é o directório corrente (.), o directório pai (..), ou um subdirectório do directório actual. Para todos os outros casos, reporte um erro apropriado (ou seja, não considere o uso de caminhos como dir_1/.../dir_n).

Note que a implementação de cada um dos utilitários pode envolver vários passos. Por exemplo, a implementação do utilitário mkdir dir envolve os seguintes passos:

Obter a próxima entrada livre na FAT, seja ela K, e colocar lá o valor -1 para indicar que, para já, o novo directório só está a usar um bloco de dados.
Adicionar uma nova entrada (directory entry) ao directório corrente para guardar a informação do novo directório (em particular, guardar a informação relativa à entrada K da FAT).
Iniciar o novo directório criando as entradas (directory entries) "." e ".." no bloco de dados de índice K.

Manipulação de ficheiros

Nesta etapa pretende-se que implemente os utilitários para manipulação de ficheiros. Segue-se uma breve descrição de cada um deles:

get fich1 fich2 - copia um ficheiro normal UNIX fich1 para um ficheiro no nosso sistema fich2
put fich1 fich2 - copia um ficheiro do nosso sistema fich1 para um ficheiro normal UNIX fich2
cp fich1 fich2 - copia o ficheiro fich1 para fich2
cp fich dir - copia o ficheiro fich para o subdirectório dir
mv fich1 fich2 - move o ficheiro fich1 para fich2
mv fich dir - move o ficheiro fich para o subdirectório dir
rm fich - remove o ficheiro fich
cat fich - escreve para o ecrã o conteúdo do ficheiro fich

Tal como na etapa anterior, não considere o uso de caminhos nos argumentos dir e fich.

Tratamento de erros

Todos os erros que possam ocorrer durante uma sessão de utilização do emulador deverão ser reportados tal como se indica a seguir.

Erros de sintaxe devem ser reportados numa única linha e segundo o seguinte formato: ERROR(input: <mensagem de erro apropriada>). Exemplos:
ERROR(input: command not found) ERROR(input: too many arguments)
Erros de semântica (i.e., erros em que, apesar do comando estar sintacticamente correcto, este não pode ser executado por alguma razão) devem ser reportados numa única linha e segundo o seguinte formato: ERROR(<nome do comando>: <mensagem de erro apropriada>). Exemplos:
ERROR(mkdir: cannot create directory `..' - entry exists) ERROR(rmdir: cannot remove directory `dir' - entry not empty) ERROR(cat: cannot print `dir' - entry is a directory)

Prazos

O trabalho deve ser entregue via web até às 12 horas do dia 23 de Maio de 2008, sendo a sua demonstração feita na aula prática imediatamente a seguir.

O que entregar? Um ficheiro .tar que inclua:

Os ficheiros que implementam o conjunto das etapas (pode ser só um);
A makefile que gera o executável do trabalho (utilizar o nome vfs).

O código deve compilar e executar nas máquinas da sala das aulas práticas. Uma boa estruturação e legibilidade do código será valorizada.