Trabalho II: Sistema de Gestão de Ficheiros

Objetivo

O objetivo 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 a 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 diretórios.

Trabalho

Um sistema de gestão de ficheiros do tipo FAT 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 9999

  typedef struct superblock_entry {
    int check_number;   // número que permite identificar o sistema como válido
    int block_size;     // tamanho de um bloco {128, 256 (default), 512 ou 1024 bytes}
    int fat_type;       // tipo de FAT {7, 8 (default), 9 ou 10}
    int root_block;     // número do 1º bloco a que corresponde o diretório raiz
    int free_block;     // número do 1º bloco da lista de blocos não utilizados
    int n_free_blocks;  // total 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/diretó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 diretó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/diretó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 diretórios é de certa forma idêntica à dos ficheiros (o primeiro bloco do diretório raiz "/" é definido pelo campo root_block do superblock), a diferença reside no facto dos blocos de dados para diretórios seguirem um formato predefinido. Um bloco de dados para um diretó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/subdiretório do diretório em causa.

  #define TYPE_DIR  'D'
  #define TYPE_FILE 'F'
  #define MAX_NAME_LENGHT 20

  typedef struct directory_entry {
    char type;                   // tipo da entrada (TYPE_DIR ou TYPE_FILE)
    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 total de blocos num sistema de ficheiros pode ser calculado pela seguinte expressão:

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.

A emulação do sistema de gestão 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: 128, 256, 512 ou 1024), o tipo de FAT (opção -f seguido do tipo: 7, 8, 9 ou 10) e o nome do ficheiro sobre o qual o emulador deverá funcionar (exemplo: vfs -b128 -f7 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 diretórios. O código base que define as estruturas de dados mencionadas acima e que implementa o parsing dos argumentos, o parsing da linha de comandos e a formatação inicial do sistema de ficheiros pode ser obtido aqui.

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)

Etapas do Trabalho

Etapa 1: Manipulação de Diretórios

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

ls - lista o conteúdo do diretório actual. Numa primeira fase, enquanto não tem os restantes utilitários a funcionar corretamente, comece por implementar uma listagem básica. Mais tarde, implemente a listagem de modo a que esta seja apresentada ordenada pelo nome de cada entrada, usando o código ascii dos caracteres (para tal pode tirar partido da função qsort()), e cada entrada deve seguir o seguinte formato: <name> <day>-<month>-<year> [<DIR>|<size>]. Segue-se um pequeno exemplo:

  .                    01-Fev-2015 DIR
  ..                   01-Fev-2015 DIR
  Diretorio            27-Ago-2015 DIR
  fich_tamanho_1024    01-Abr-2016 1024
  fich_tamanho_1025    09-Mai-2015 1025
  fich_tamanho_3073    01-Out-2015 3073
  nome_com_tamanho_max 29-Jan-2016 DIR

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

Para todos os utilitários, considere apenas os casos em que o argumento dir é o diretório corrente (.), o diretório pai (..), ou um subdiretório do diretó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 diretório só está a usar um bloco de dados.
Adicionar uma nova entrada (directory entry) ao diretório corrente para guardar a informação do novo diretório (em particular, guardar a informação relativa à entrada K da FAT).
Iniciar o novo diretório criando as entradas (directory entries) "." e ".." no bloco de dados de índice K.

Etapa 2: 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
cat fich - escreve para o ecrã o conteúdo do ficheiro fich
cp fich1 fich2 - copia o ficheiro fich1 para fich2
cp fich dir - copia o ficheiro fich para o subdiretório dir
mv fich1 fich2 - move o ficheiro fich1 para fich2
mv fich dir - move o ficheiro fich para o subdiretório dir
rm fich - remove o ficheiro fich

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

Visualizador do Sistema de Gestão de ficheiros

(desenvolvido por Filipe Esteves)
Caso encontre erros no visualizador, reporte-os ao Filipe Esteves através do email up201104044@fc.up.pt