TecnicoFS

Project done in the scope of the course Operating Systems, IST 2022/2023.

List of contents

Enunciado (1º Exercício)
Enunciado (2º Exercício)
Pull updates

Enunciado (1º Exercício)

Projeto base (ponto de partida)

O projeto base é o TecnicoFS (Técnico File System), um sistema de ficheiros simplificado em modo utilizador. É implementado como uma biblioteca, que pode ser usada por qualquer processo cliente que pretenda ter uma instância privada de um sistema de ficheiros no qual pode manter os seus dados.

Interface de programação

O TecnicoFS oferece uma interface de programação (API) inspirada na API de sistema de ficheiros POSIX. No entanto, para simplificar o projeto, a API do TecnicoFS oferece apenas um subconjunto de funções com interface simplificada:

int tfs_open(char const *name, int flags);
int tfs_close(int fhandle);
ssize_t tfs_write(int fhandle, void const *buffer, size_t len);
ssize_t tfs_read(int fhandle, void *buffer, size_t len);

(Nota: o tipo de dados ssize_t é definido no standard POSIX para representar tamanhos em bytes, podendo também ter o valor -1 para representar erro. É, por exemplo, o tipo do retorno das funções read e write da API de sistema de ficheiros POSIX.)

Além destas funções, existem as funções de inicialização e destruição do sistema de ficheiros, tfs_init e tfs_destroy.

O código fonte do TecnicoFS encontra-se disponível neste repositório. A descrição detalhada de cada função pode ser encontrada na documentação no código fonte do TecnicoFS.

Estado do sistema de ficheiros

Tal como em FS tradicionais modernos, o conteúdo do FS encontra-se referenciado numa estrutura de dados principal chamada tabela de i-nodes, global ao FS. Cada i-node representa uma diretoria ou um ficheiro no TecnicoFS, que tem um identificador único chamado i-number. O i-number de uma diretoria/ficheiro corresponde ao índice do i-node correspondente na tabela de i-nodes. O i-node consiste numa estrutura de dados que descreve os atributos da diretoria/ficheiro (aquilo que normalmente se chamam os seus metadados) e que referencia o conteúdo da diretoria/ficheiro (ou seja, os dados).

Além da tabela de i-nodes, existe uma região de dados, organizada em blocos de tamanho fixo. Esta região mantém os dados de todos os ficheiros do FS, sendo esses dados referenciados a partir do i-node de cada ficheiro (na tabela de i-nodes). No caso de ficheiros normais, é na região de dados que é mantido o conteúdo do ficheiro (por exemplo, a sequência de caracteres que compõem um ficheiro de texto). No caso de diretorias, a região de dados mantém a respetiva tabela, que representa o conjunto de ficheiros (ficheiros normais e subdiretorias) que existem nessa diretoria.

Para facilitar a alocação e libertação de i-nodes e blocos, existe um vetor de alocação associado à tabela de i-nodes e à região de dados, respetivamente.

Além das estruturas de dados mencionadas acima, que mantêm o estado durável do sistema de ficheiros, o TecnicoFS mantém uma tabela de ficheiros abertos. Essencialmente, esta tabela conhece os ficheiros atualmente abertos pelo processo cliente do TecnicoFS e, para cada ficheiro aberto, indica onde está o cursor atual. A tabela de ficheiros abertos é descartada quando o sistema é desligado ou termina abruptamente (ou seja, não é durável).

Nas aulas teóricas da 2ª semana, o código base será apresentado e discutido. Recomendamos a todos os estudantes que frequentem essas aulas antes de começarem a desenvolver a solução.

Simplificações

Além de uma API simplificada, o desenho e implementação do TecnicoFS adotam algumas simplificações fundamentais, que sumarizamos de seguida:

Em vez de uma árvore de diretorias, o TecnicoFS tem apenas uma diretoria (a raiz "/"), dentro da qual podem existir ficheiros (e.g., "/f1", "/f2", etc.) mas não outras subdiretorias. O texto entre aspas nos exemplos anteriores é chamado o caminho de acesso ao ficheiro.
O conteúdo dos ficheiros e da diretoria raiz é limitado a um bloco (cuja dimensão é determinada em tempo de compilação e que é configurada para 1KB, por omissão). Como consequência, o i-node respetivo tem um campo simples que indica qual o índice desse bloco.
Assume-se que existe um único processo cliente, que é o único que pode aceder ao sistema de ficheiros. Consequentemente, existe apenas uma tabela de ficheiros abertos e não há permissões nem controlo de acesso.
A implementação das funções assume que estas são chamadas por um cliente sequencial, ou seja, a implementação pode resultar em erros caso uma ou mais funções sejam chamadas concorrentemente por duas ou mais tarefas (threads) do processo cliente. Por outras palavras, não é thread-safe.
As estruturas de dados que, em teoria, deveriam ser duráveis, não são mantidas em memória secundária. Quando o TecnicoFS é terminado, o conteúdo destas estruturas de dados é perdido.

1º Exercício

No 1º exercício pretende-se estender a versão base do TecnicoFS com as funcionalidades que são descritas de seguida.

1.1 Cópia de um sistema de ficheiros externo

Pretende-se que seja oferecida e implementada uma nova função:

int tfs_copy_from_external_fs(char const *source_path, char const *dest_path);

Esta função copia o conteúdo de um ficheiro source_path existente no sistema de ficheiros do sistema operativo no qual o TecnicoFs corre, para o ficheiro destPath guardado no TecnicoFS. Por outras palavras, importa o conteúdo de um ficheiro do sistema de ficheiros nativo para dentro do TecnicoFS (limitado à dimensão de 1 bloco).

Devolve 0 em caso de sucesso, -1 em caso de erro.

Caso o ficheiro identificado por dest_path não exista, este deve ser criado. Caso contrário, o conteúdo prévio do ficheiro já existente deve ser totalmente substituído pelo novo conteúdo.

Além de implementar esta funcionalidade no TecnicoFS, cada grupo deve desenvolver também pelo menos um programa de teste que demonstre e verifique a correção da solução proposta.

1.2 Nomes alternativos e Atalhos

Pretende-se permitir a criação e apagamento de nomes alternativos (hard links) e atalhos (soft links) para ficheiros. Ambos os tipos de links permitem criar ligações alternativas (i.e., pontos de acessos alternativos) para ficheiros pré-existentes no sistemas de ficheiros. Contudo, estes dois tipos de links têm semânticas diferentes, tal como ilustrado de seguida.

Nomes alternativos. Ao criar um hard link "/path_A/hard_link" para um ficheiro "/path_B/file_name", é acrescentada uma entrada na lista do diretório "/path_A" cujo nome é "hard_link" e que aponta para o i-node associado ao ficheiro "/path_B/file_name". Nesse i-node é também incrementado o contador de hard links. Um ficheiro é efetivamente apagado só quando o contador de hard links do relativo i-node atinge o valor 0. Nota: este contador é inicializado com o valor 1 ao criar o ficheiro no sistema de ficheiro (o que corresponde, na prática, à criação de um hard link para o ficheiro).

Atalhos. Ao criar um soft link "/path_A/soft_link" para um ficheiro "/path_B/file_name", é acrescentada uma entrada na lista do diretório "/path_A" cujo nome é "soft_link" e cujo conteúdo é "/path_B/file_name". A diferença de um hard link para um soft link é que este último não aponta para o i-node associado ao ficheiro "/path_B/file_name", mas armazena apenas uma referência para o nome do ficheiro para o qual esse link aponta. Consequentemente, caso o ficheiro "/path_B/file_name" venha a ser apagado após a criação de um soft link para ele, esse ficheiro ("/path_B/file_name") é imediatamente apagado do sistema de ficheiros e, portanto, as aplicações que tentem usar esse soft link irão incorrer em erros.

Para a criação de hard/soft link deverão ser implementadas as seguintes funções:

int tfs_link(char const *target_file, char const *source_file) // cria um hard link

int tfs_sym_link(char const *target_file, char const *source_file) // cria um soft link

Pretende-se também implementar uma função que permite apagar ficheiros e links:

int tfs_unlink(char const *target)

Simplificações/observações:

Podem ser criados hard links apenas para ficheiros (ou diretorias), e nunca para soft links;
Os soft links guardam a referência para o target no bloco de dados.

Cada grupo deverá também desenvolver pelo menos um programa de teste que demonstre e verifique a correção da solução proposta para cada função.

1.3 Suporte a chamadas concorrentes por cliente multitarefa

É desejável eliminar a restrição do programa cliente ser single thread, permitindo que seja constituído por múltiplas tarefas concorrentes (criadas por pthread_create). Pretende-se rever a implementação das funções do TecnicoFS para as tornar corretas quando executadas concorrentemente (i.e., thread-safe).

Para cumprir este requisito, devem ser usados trincos lógicos (pthread_mutex) ou trincos de leitura-escrita (pthread_rwlock), ficando a sua escolha ao critério dos estudantes.

A solução deve maximizar o paralelismo, recorrendo a sincronização fina. Uma solução baseada em trincos que colocam em exclusão mútua a totalidade ou grande parte das estruturas de dados do TecnicoFS será fortemente penalizada na avaliação.

Caso sintam que a interface de funções que gerem o estado do TecnicoFS (definida em fs/state.h) não é a mais apropriada para resolver este requisito, podem adaptar essa interface para uma alternativa mais apropriada. Recomendamos que, antes de começarem a implementar, discutam o desenho da vossa solução com o docente de laboratório.

Além da adaptação do TecnicoFS para o tornar thread-safe, cada grupo deve compor uma bateria de, pelo menos, três programas cliente paralelos.

Submissão e avaliação

A submissão é feita através do Fénix até ao dia 20/Dezembro/2022 às 23h59.

Os estudantes devem submeter um ficheiro no formato zip com o código fonte e o ficheiro Makefile. O arquivo submetido não deve incluir outros ficheiros (tais como binários). Além disso, o comando make clean deve limpar todos os ficheiros resultantes da compilação do projeto.

Recomendamos que os alunos se assegurem que o projeto compila/corre corretamente no ambiente de referência. Ao avaliar os projetos submetidos, em caso de dúvida sobre o funcionamento do código submetido, os docentes usarão o ambiente de referência para fazer a validação final. O uso de outros ambientes para o desenvolvimento/teste do projeto (e.g., macOS, Windows/WSL) é permitido, mas o corpo docente não dará apoio técnico a dúvidas relacionadas especificamente com esses ambientes.

A avaliação será feita de acordo com o método de avaliação descrito na página Fénix da cadeira.

Bom trabalho!

Enunciado (2º Exercício | Message Broker)

O segundo exercício do projeto pretende construir um sistema simples de publicação e subscrição de mensagens, que são armazenadas no sistema de ficheiros TecnicoFS. O sistema vai ter um processo servidor autónomo, ao qual diferentes processos clientes se podem ligar, para publicar ou receber mensagens numa dada caixa de armazenamento de mensagens.

Ponto de partida

Para resolver o segundo exercício, os grupos devem usar como base a sua solução do 1º exercício ou aceder ao novo código base, que estende a versão original do TecnicoFS das seguintes maneiras:

As operações principais do TecnicoFS estão sincronizadas usando um único trinco (mutex) global. Embora menos paralela que a solução pretendida para o primeiro exercício, esta solução de sincronização é suficiente para implementar os novos requisitos;
É implementada a operação tfs_unlink, que permite remover ficheiros.

Adicionalmente, o código base inclui esqueletos para:

O programa do servidor mbroker (na diretoria mbroker);
A implementação do cliente para publicação (na diretoria publisher);
A implementação do cliente para subscrição (na diretoria subscriber);
A implementação do cliente de gestão (diretoria manager).

Em vez do novo código base, os grupos que tenham uma solução robusta no 1º exercício são encorajados a construírem a solução com base na sua versão, que, à partida, estará mais otimizada em termos de concorrência.

1. Arquitetura do sistema

O sistema é formado pelo servidor (mbroker) e por vários publicadores (publishers), subscritores (subscribers) e gestores (manager).

Caixas de Mensagens

Um conceito fundamental do sistema são as caixas de mensagens. Cada caixa pode ter um publicador e múltiplos subscritores. O publisher coloca mensagens na caixa, e os vários subscribers lêem as mensagens da caixa. Cada caixa é suportada no servidor por um ficheiro no TFS. Por esta razão, o ciclo de vida de uma caixa é distinto do ciclo de vida do publisher que lá publica mensagens. Aliás, é possível que uma caixa venha a ter vários publishers ao longo da sua existência, embora apenas um de cada vez.

As operações de criação e remoção de caixa são geridas pelo manager. Adicionalmente, o manager permite listar as caixas existentes na mbroker.

1.1. Servidor

O servidor incorpora o TecnicoFS e é um processo autónomo, inicializado da seguinte forma:

$ mbroker <register_pipe_name> <max_sessions>

O servidor cria um named pipe cujo nome é o indicado no argumento acima. É através deste named pipe, criado pelo servidor, que os processos cliente se poderão ligar para se registarem.

Qualquer processo cliente pode ligar-se ao named pipe do servidor e enviar-lhe uma mensagem a solicitar o início de uma sessão. Uma sessão consiste em ter um named pipe do cliente, onde o cliente envia as mensagens (se for um publicador) ou onde o cliente recebe mensagens (se for um subscritor). Existe também o manager. Um dado cliente apenas assume um papel, ou seja, ou é exclusivamente publicador, subscritor, ou gestor.

O named pipe da sessão deve ser criado previamente pelo cliente. Na mensagem de registo, o cliente envia o nome do named pipe a usar durante a sessão.

O nome do named pipe da sessão deve ser escolhido manualmente quando um cliente é lançado e de forma a garantir que não existem conflitos com outros clientes concorrentes.

Uma sessão mantém-se aberta até que aconteça uma das seguintes situações:

Um cliente feche o seu named pipe, sinalizando implicitamente o fim de sessão;
A caixa é removida pelo gestor.

O named pipe deve ser removido do sistema de ficheiros pelo respetivo cliente após o fim da sessão.

O servidor aceita um número máximo de sessões em simultâneo, definido pelo valor do argumento max_sessions.

Nas subsecções seguintes descrevemos o protocolo cliente-servidor em maior detalhe, i.e., o conteúdo das mensagens de pedido e resposta trocadas entre clientes e servidor.

1.1.1. Arquitetura do servidor

O servidor deve usar a main thread para gerir o named pipe de registo e lançar max_sessions threads para processar sessões. Quando chega um novo pedido de registo, este deve ser encaminhado para uma thread que se encontre disponível, que irá processá-lo durante o tempo necessário. Para gerir estes pedidos, evitando que as threads fiquem em espera ativa, a main thread e as worker threads cooperam utilizando uma fila produtor-consumidor, segundo a interface disponibilizada no ficheiro producer-consumer.h. Desta forma, quando chega um novo pedido de registo, este é colocado na fila e assim que uma thread fique disponível, irá consumir e tratar esse pedido.

A arquitetura do servidor está sumarizada na seguinte figura:

O mbroker usa o TFS para armazenar as mensagens das caixas;
A main thread recebe pedidos através do register pipe e coloca-os numa fila de produtor-consumidor;
As worker threads executam os pedidos dos clientes, dedicando-se a atender um cliente de cada vez;
Cooperam com a main thread através de uma fila produtor-consumidor, que evita espera ativa.

1.2. Publisher

Um publicador é um processo lançado da seguinte forma:

pub <register_pipe_name> <pipe_name> <box_name>

Assim que é lançado, o publisher, pede para iniciar uma sessão no servidor de mbroker, indicando a caixa de mensagens para a qual pretende escrever mensagens. Se a ligação for aceite (pode ser rejeitada caso já haja um publisher ligado à caixa, por exemplo) fica a receber mensagens do stdin e depois publica-as. Uma mensagem corresponde a uma linha do stdin, sendo truncada a um dado valor máximo e delimitada por um \0, como uma string de C. A mensagem não deve incluir um \n final.

Se o publisher receber um EOF (End Of File, por exemplo, com um Ctrl-D), deve encerrar a sessão fechando o named pipe.

1.3. Subscriber

Um subscritor é um processo lançado da seguinte forma:

sub <register_pipe_name> <pipe_name> <box_name>

Assim que é lançado, o subscriber:

Liga-se à mbroker, indicando qual a caixa de mensagens que pretende subscrever;
Recolhe as mensagens já aí armazenadas e imprime-as uma a uma no stdout, delimitadas por \n;
Fica à escuta de novas mensagens;
Imprime novas mensagens quando são escritas para o named pipe para o qual tem uma sessão aberta.

Para terminar o subscriber, este deve processar adequadamente o SIGINT (i.e., o Ctrl-C), fechando a sessão e imprimindo no stdout o número de mensagens recebidas durante a sessão.

1.4. Manager

Um gestor é um processo lançado de uma das seguintes formas:

manager <register_pipe_name> <pipe_name> create <box_name>
manager <register_pipe_name> <pipe_name> remove <box_name>
manager <register_pipe_name> <pipe_name> list

Assim que é lançado, o manager:

Envia o pedido à mbroker;
Recebe a resposta no named pipe criado pelo próprio manager;
Imprime a resposta e termina.

1.5. Exemplos de execução

Um primeiro exemplo considera o funcionamento sequencial dos clientes:

Um manager cria a caixa bla;
Um publisher liga-se à mesma caixa, escreve 3 mensagens e desliga-se;
Um subscriber liga-se à mesma caixa e começa a receber mensagens;
Recebe as três, uma de cada vez, e depois fica à espera de mais mensagens.

Num segundo exemplo, mais interessante, vai existir concorrência entre clientes:

Um publisher liga-se;
Entretanto, um subscriber para a mesma caixa, liga-se também;
O publisher coloca mensagens na caixa e estas vão sendo entregues imediatamente ao subscriber, ficando à mesma registadas no ficheiro;
Um outro subscriber liga-se à mesma caixa, e começa a receber as mensagens todas desde o início;
Agora, quando o publisher escreve uma nova mensagem, ambos os subscriber recebem a mensagem diretamente.

2. Protocolo

Para moderar a interação entre o servidor e os clientes, é estabelecido um protocolo, que define como é que as mensagens são serializadas, ou seja, como é que ficam arrumadas num buffer de bytes. Este tipo de protocolo é por vezes referido como um wire protocol, numa alusão aos dados que efetivamente circulam no meio de transmissão, que neste caso, serão os named pipes.

O conteúdo de cada mensagem deve seguir o seguinte formato, onde:

O símbolo | denota a concatenação de elementos numa mensagem;
Todas as mensagens de pedido são iniciadas por um código que identifica a operação solicitada (OP_CODE);
As strings que transportam, por exemplo, os nomes de named pipes são de tamanho fixo, indicado na mensagem. No caso de texto com tamanho inferior, os caracteres adicionais devem ser preenchidos com \0.

2.1. Registo

O named pipe do servidor, que só recebe registos de novos clientes, deve receber mensagens do seguinte tipo:

Pedido de registo de publisher:

[ code = 1 (uint8_t) ] | [ client_named_pipe_path (char[256]) ] | [ box_name (char[32]) ]

Pedido de registo de subscriber:

[ code = 2 (uint8_t) ] | [ client_named_pipe_path (char[256]) ] | [ box_name (char[32]) ]

Pedido de criação de caixa:

[ code = 3 (uint8_t) ] | [ client_named_pipe_path (char[256]) ] | [ box_name (char[32]) ]

Resposta ao pedido de criação de caixa:

[ code = 4 (uint8_t) ] | [ return_code (int32_t) ] | [ error_message (char[1024]) ]

O return code deve ser 0 se a caixa foi criada com sucesso, e -1 em caso de erro. Em caso de erro a mensagem de erro é enviada (caso contrário, fica simplesmente inicializada com \0).

Pedido de remoção de caixa:

[ code = 5 (uint8_t) ] | [ client_named_pipe_path (char[256]) ] | [ box_name (char[32]) ]

Resposta ao pedido de remoção de caixa:

[ code = 6 (uint8_t) ] | [ return_code (int32_t) ] | [ error_message (char[1024]) ]

Pedido de listagem de caixas:

[ code = 7 (uint8_t) ] | [ client_named_pipe_path (char[256]) ]

A resposta à listagem de caixas vem em várias mensagens, do seguinte tipo:

[ code = 8 (uint8_t) ] | [ last (uint8_t) ] | [ box_name (char[32]) ] | [ box_size (uint64_t) ] | [ n_publishers (uint64_t) ] | [ n_subscribers (uint64_t) ]

O byte last é 1 se esta for a última caixa da listagem e a 0 em caso contrário. box_size é o tamanho (em bytes) da caixa, n_publisher (0 ou 1) indica se existe um publisher ligado à caixa naquele momento e n_subscriber indica o número de subscritores da caixa naquele momento.

Se não existirem caixas, a resposta é uma mensagem com last a 1 e box_name toda preenchida com \0.

2.2 Publisher

O publicador envia mensagens para o servidor do tipo:

[ code = 9 (uint8_t) ] | [ message (char[1024]) ]

2.3 Subscriber

O servidor envia mensagens para o subscritor do tipo:

[ code = 10 (uint8_t) ] | [ message (char[1024]) ]

3. Requisitos de implementação

3.1. Tratamento de clientes

Quando o servidor inicia, lança um conjunto de S tarefas (thread pool), que ficam à espera de pedidos de registo para tratar, que irão receber através da fila produtor-consumidor. A main thread gere o named pipe de registo, e coloca os pedidos de registo na fila produtor-consumidor. Quando uma thread termina uma sessão, fica à espera de nova sessão para tratar.

3.2 Caixas de armazenamento

As mensagens recebidas pelo servidor devem ser colocadas numa caixa. Na prática, uma caixa corresponde a um ficheiro no TecnicoFS. O ficheiro deve ser criado quando a caixa for criada pelo manager, e apagado quando a caixa for removida. Todas as mensagens que vão sendo recebidas são escritas no fim do ficheiro, separadas por \0.

Resumindo, as mensagens são acumuladas nas caixas. Quando um subscritor se liga a uma caixa, o ficheiro correspondente é aberto e as mensagens começam a ser lidas desde o início (mesmo que o mesmo subscritor ou outro já as tenha recebido antes). Ulteriores mensagens geradas pelo publisher de uma caixa deverão ser também entregues aos subscribers da caixa. Esta funcionalidade deverá ser implementada usando variáveis de condição com o objetivo de evitar esperas ativas.

3.3 Formatação de mensagens

Para uniformizar o output dos diversos comandos (para o stdout), é fornecido o formato com que estas devem ser impressas.

3.4 Fila Produtor-Consumidor

A fila produtor-consumidor é a estrutura de sincronização mais complexa do projeto. Por isso, esta componente vai ser avaliada em isolamento (i.e., existirão testes que usam apenas a interface descrita no producer-consumer.h) para garantir a sua correção. Como tal, a interface do producer-consumer.h não deve ser alterada.

De resto, os grupos são livres de alterar o código base como lhes for conveniente.

Mensagens do subscritor

fprintf(stdout, "%s\n", message);

Resultados das operações do gestor

Se o comando de criação ou remoção de caixa for bem sucedido, deve imprimir-se:

fprintf(stdout, "OK\n");

Se tiver ocorrido um erro:

fprintf(stdout, "ERROR %s\n", error_message);

Listagem de caixas

Cada linha da listagem de caixas deve ser impressa da seguinte forma:

fprintf(stdout, "%s %zu %zu %zu\n", box_name, box_size, n_publishers, n_subscribers);

As caixas devem estar ordenadas por ordem alfabética, não sendo garantido que o servidor as envie por essa ordem (i.e., o cliente deve ordenar as caixas antes das imprimir).

Se não existirem caixas, deve ser impresso o seguinte:

fprintf(stdout, "NO BOXES FOUND\n");

3.5 Espera Ativa

No projeto, nunca devem ser usados mecanismos de espera ativa.

4. Sugestão de implementação

Sugere-se que implementem o projeto através dos seguintes passos:

Implementar as interfaces de linha de comando (CLI) dos clientes;
Implementar a serialização do protocolo de comunicação;
Implementar uma versão básica do mbroker, onde só existe uma thread que, em ciclo, a) recebe um pedido de registo; b) trata a sessão correspondente; e c) volta a ficar à espera do pedido de registo;
Implementar a fila produtor-consumidor;
Utilizar a fila produtor-consumidor para gerir e encaminhar os pedidos de registo para as worker threads.

5. Submissão e avaliação

A submissão é feita através do Fénix até sexta-feira, dia 13/Janeiro/2023, às 20h00.

Os estudantes devem submeter um ficheiro no formato zip com o código fonte e o ficheiro Makefile. O arquivo submetido não deve incluir outros ficheiros (tais como binários). Além disso, o comando make clean deve limpar todos os ficheiros resultantes da compilação do projeto, bem como o comando make fmt, para formatar automaticamente o código.