FAT

O FAT (File Allocation Table) continua sendo um dos primeiros sistemas de arquivos mais comuns que um kernel hobby implementa, não porque seja moderno (remonta aos primeiros sistemas MS-DOS), mas porque sua estrutura em disco é incomumente simples de analisar corretamente, bem documentada, e ainda universalmente legível, tornando-o uma escolha prática para qualquer coisa, de uma partição de boot ao primeiro driver de sistema de arquivos funcional de um kernel hobby.

Layout geral

Um volume FAT é organizado como um pequeno número de regiões grandes e contíguas, em ordem fixa: um boot sector (contendo tanto código de boot quanto uma estrutura descrevendo a geometria do volume), uma ou mais cópias da própria File Allocation Table, uma região de diretório raiz (apenas FAT12/16; o FAT32 armazena o diretório raiz como uma cadeia de cluster comum, descrita abaixo), e finalmente a região de dados, contendo o conteúdo real de todo arquivo e subdiretório.

O boot sector e o BIOS Parameter Block

O primeiro setor descreve a própria geometria do volume através de uma estrutura chamada BIOS Parameter Block (BPB), embutida dentro de código de boot que, de outra forma, é executável, com campos incluindo bytes por setor, setores por cluster, o número de setores reservados antes da região FAT começar, o número de cópias da FAT, e (para FAT32) o cluster inicial do diretório raiz:

struct fat_bpb {
    uint8_t  jump[3];
    char     oem_name[8];
    uint16_t bytes_per_sector;
    uint8_t  sectors_per_cluster;
    uint16_t reserved_sectors;
    uint8_t  fat_count;
    uint16_t root_entry_count;   // 0 no FAT32
    uint16_t total_sectors_16;   // 0 se grande demais; ver total_sectors_32
    uint8_t  media_type;
    uint16_t sectors_per_fat_16; // 0 no FAT32; ver extensão específica do FAT32
    uint16_t sectors_per_track;
    uint16_t head_count;
    uint32_t hidden_sectors;
    uint32_t total_sectors_32;
} __attribute__((packed));

Toda outra estrutura no volume (onde a própria FAT começa, onde o diretório raiz ou a região de dados começa, quão grande um cluster é em bytes) é calculada a partir desses campos, em vez de presumida em qualquer offset fixo, o que é o que permite que um único driver trate corretamente volumes formatados com tamanhos de cluster ou contagens de setor diferentes.

A File Allocation Table

O conteúdo de um arquivo não é necessariamente armazenado de forma contígua; é armazenado como uma cadeia de clusters de tamanho fixo, e a File Allocation Table é, funcionalmente, um array com uma entrada por cluster no volume, onde cada entrada contém ou o número do próximo cluster na cadeia daquele arquivo, um valor reservado marcando o fim da cadeia, ou zero marcando o cluster como livre. Ler um arquivo, portanto, significa começar do número de seu primeiro cluster (encontrado em sua entrada de diretório) e repetidamente consultar a entrada FAT do cluster atual para encontrar o próximo, até que um marcador de fim de cadeia seja alcançado:

uint32_t fat_next_cluster(uint8_t *fat, uint32_t cluster, int fat_bits) {
    if (fat_bits == 16) {
        uint16_t *table = (uint16_t *)fat;
        return table[cluster]; // >= 0xFFF8 marca fim de cadeia
    }
    // FAT12 empacota entradas em 1,5 bytes cada, exigindo extração em nível de bit
    // FAT32 usa entradas de 32 bits com os 4 bits superiores reservados
    return 0; // simplificado para ilustração
}

As entradas do FAT12 são o caso complicado: com 12 bits cada, duas entradas consecutivas se empacotam em exatamente 3 bytes, exigindo uma leitura de byte seguida de um shift e máscara para extrair os 12 bits baixos ou altos, dependendo de o número do cluster ser par ou ímpar, um detalhe que pega implementações mais ingênuas que presumem que toda variante de FAT usa um número inteiro de bytes por entrada.

Entradas de diretório

Um diretório é simplesmente uma região de armazenamento (uma área fixa para o diretório raiz do FAT12/16, uma cadeia de cluster comum para tudo mais, incluindo o diretório raiz do FAT32), formatada como uma sequência de entradas de tamanho fixo de 32 bytes, cada uma descrevendo um arquivo ou subdiretório:

struct fat_dirent {
    char     name[8];
    char     ext[3];
    uint8_t  attributes;
    uint8_t  reserved;
    uint8_t  create_time_tenths;
    uint16_t create_time;
    uint16_t create_date;
    uint16_t access_date;
    uint16_t first_cluster_high; // 0 no FAT12/16
    uint16_t modify_time;
    uint16_t modify_date;
    uint16_t first_cluster_low;
    uint32_t file_size;
} __attribute__((packed));

A divisão 8+3 entre name/ext é a origem da limitação tradicional “8.3” de nome curto do FAT: oito caracteres, um ponto, depois uma extensão de três caracteres, tudo em maiúsculas, sem suporte a minúsculas ou muitos caracteres especiais no formato base. Long File Names, uma extensão posterior, contornam isso sem mudar em nada o formato subjacente de entrada de 32 bytes: um nome longo é armazenado ao longo de várias entradas de diretório adicionais imediatamente precedendo a entrada real, cada uma marcada com um valor especial de atributo (0x0F) identificando-a como um fragmento de nome longo, não um arquivo real, e cada uma contendo uma porção do nome codificada em UTF-16. Tais entradas são algo que um driver que só suporta nomes curtos pode (e, conforme a especificação, deveria) simplesmente pular como não reconhecidas, recorrendo ao nome curto sempre presente ao lado delas.

Notas de implementação

O FAT32, apesar do nome, não usa de fato os 32 bits completos de um número de cluster: os 4 bits superiores de cada entrada FAT de 32 bits são reservados e precisam ser mascarados antes do uso, um detalhe fácil de perder que produz números de cluster que parecem válidos mas na verdade estão corrompidos por bits reservados residuais de o que quer que tenha escrito a entrada anteriormente. A FAT também é convencionalmente armazenada em mais de uma cópia idêntica (fat_count no BPB, tipicamente 2), especificamente para que um verificador de sistema de arquivos possa potencialmente se recuperar de corrupção em uma cópia comparando com a outra, um detalhe que um driver mínimo somente-leitura pode ignorar com segurança, lendo apenas a primeira cópia, mas que um driver que escreve no sistema de arquivos precisa tratar corretamente, mantendo toda cópia sincronizada.

Referências

^ Microsoft, FAT32 File System Specification (a referência autoritativa para o layout do BPB, codificação de entrada FAT, e formato de entrada de diretório descritos acima).

Ver também

The VFS: a camada atrás da qual um driver FAT ficaria em um kernel suportando múltiplos formatos de sistema de arquivos.
Physical Memory: de onde buffers contendo setores lidos do disco são, em última instância, alocados.