ext2

O ext2 é um sistema de arquivos baseado em blocos construído em torno de dividir um volume em block groups de tamanho fixo, cada um guardando sua própria cópia dos metadados necessários para alocar espaço dentro dele, em vez de concentrar toda essa contabilidade em um único lugar. A camada VFS já define o que um superbloco, inode, e entrada de diretório são de forma abstrata; este artigo cobre a aparência desses mesmos conceitos como bytes reais em um volume ext2, uma questão diferente do modelo de alocação por lista ligada do FAT, coberto separadamente.

Block groups

Um volume é dividido em block groups consecutivos, cada um cobrindo um número fixo de blocos (uma escolha comum é um grupo a cada 8.192 blocos de 4 KB, exatamente o número de blocos que um único bitmap do tamanho de um bloco consegue descrever). Todo grupo carrega seu próprio bitmap de blocos e bitmap de inodes, um bit por bloco ou inode naquele grupo marcando-o usado ou livre, sua própria fatia da tabela de inodes, e, para ao menos alguns grupos, uma cópia de backup do superbloco e da tabela de descritores de grupo. Dividir a contabilidade de alocação dessa forma mantém uma busca em bitmap local a qualquer grupo em que um arquivo esteja sendo alocado, em vez de varrer uma estrutura única que abrange todo o sistema de arquivos, e manter os blocos de dados de um arquivo e seu inode no mesmo grupo, quando possível, reduz quão longe a cabeça de leitura de um disco precisa se deslocar entre ler um inode e ler os dados que ele aponta.

O superbloco

O superbloco, guardado em um offset fixo (1.024 bytes a partir do início do volume, para deixar espaço para um setor de boot antes dele) e espelhado em cópias de backup em outros lugares, guarda os fatos de todo o volume dos quais toda outra estrutura depende.

struct ext2_superblock {
    uint32_t s_inodes_count;
    uint32_t s_blocks_count;
    uint32_t s_r_blocks_count;     // blocos reservados para o superusuário
    uint32_t s_free_blocks_count;
    uint32_t s_free_inodes_count;
    uint32_t s_first_data_block;   // 0 para blocos de 1 KB, 1 nos demais casos
    uint32_t s_log_block_size;     // tamanho de bloco = 1024 << s_log_block_size
    uint32_t s_blocks_per_group;
    uint32_t s_inodes_per_group;
    uint16_t s_mnt_count;
    uint16_t s_max_mnt_count;
    uint16_t s_magic;              // 0xEF53
    uint16_t s_state;
    uint16_t s_errors;
    uint32_t s_rev_level;
    uint32_t s_feature_compat;
    uint32_t s_feature_incompat;
    uint32_t s_feature_ro_compat;
    uint8_t  s_uuid[16];
    char     s_volume_name[16];
    // ...
} __attribute__((packed));

s_mnt_count e s_max_mnt_count rastreiam uma contagem de montagem, incrementando a primeira a cada montagem e forçando uma checagem completa do sistema de arquivos quando atinge a segunda, uma defesa antecipada contra corrupção que se acumula lentamente e passaria despercebida indefinidamente entre checagens. Um campo de estado (s_state) distingue um sistema de arquivos desmontado de forma limpa de um ainda marcado como montado; encontrar o último no momento da montagem é exatamente o sinal de que o sistema caiu de forma suja da última vez (uma queda ou falta de energia) e uma checagem de consistência deveria rodar antes de confiar mais no volume, a varredura completa de fsck que journaling foi depois projetado para evitar. Um campo separado, s_errors, governa o que um driver faz ao descobrir corrupção durante operação comum em vez de só na montagem: continuar e apenas registrar o problema, remontar o volume como somente leitura para impedir que piore, ou parar o sistema por completo, o mesmo último recurso que Panics de Kernel cobre de forma geral.

Dois níveis de revisão mudam o que o resto do superbloco de fato contém. O original EXT2_GOOD_OLD_REV fixa todo inode em 128 bytes e não define nada além de s_inodes_count e seus vizinhos imediatos; EXT2_DYNAMIC_REV, registrado em s_rev_level, adiciona os campos listados acima a partir de s_uuid, incluindo um tamanho de inode real e visível ao driver no lugar dos 128 bytes fixos, permitindo que um volume mais novo faça inodes crescerem (para abrir espaço para timestamps em nanossegundos ou atributos estendidos, por exemplo) sem quebrar um driver que só entende o layout antigo e fixo. s_feature_compat, s_feature_incompat, e s_feature_ro_compat refinam essa mesma negociação bit a bit em vez de como um único número de revisão: um bit definido em s_feature_incompat que um dado driver não reconhece (compressão, historicamente) significa que o driver precisa recusar montar o volume por completo, já que não tem como saber como os dados organizados sob esse recurso estão de fato estruturados, enquanto um bit não reconhecido em s_feature_ro_compat (posicionamento esparso de superbloco, por exemplo) só rebaixa a montagem para somente leitura, seguro porque nada sobre interpretar dados já existentes no volume muda, só a capacidade do próprio driver de adicionar novos dados a ele com segurança.

s_r_blocks_count reserva uma porcentagem dos blocos totais do volume (5% por padrão do próprio mke2fs) que só um processo rodando como superusuário pode alocar: uma escrita de um usuário comum além do limite efetivo de espaço livre falha com ENOSPC enquanto a própria escrita do superusuário ainda tem sucesso, uma folga especificamente pensada para manter um processo crítico do sistema (um daemon de log, por exemplo) capaz de escrever pequenas quantidades de dados mesmo depois que processos controlados por usuário tenham de outra forma preenchido todo bloco visível a eles. s_uuid e s_volume_name servem à identificação em vez da alocação: uma configuração de bootloader ou entrada de /etc/fstab referenciando um volume por qualquer um dos dois continua funcionando depois que esse volume muda para outro disco ou número de partição, o que uma referência ao próprio caminho de dispositivo não sobreviveria.

Descritores de grupo e bitmaps

Imediatamente após o superbloco (ou seu backup, em grupos que carregam um) fica a tabela de descritores de grupo, um descritor de 32 bytes por block group, presente por completo em todo grupo que tem um backup de superbloco, em vez de dividida. Cada descritor guarda os números de bloco do próprio bitmap de blocos, bitmap de inodes, e tabela de inodes daquele grupo, mais algumas contagens resumo (blocos livres, inodes livres, e diretórios naquele grupo) mantidas para relatório rápido sem percorrer os bitmaps diretamente. Encontrar um bloco livre para alocação é então uma questão de localizar um grupo com espaço livre via a contagem resumo do descritor, depois varrer o bitmap de blocos daquele grupo por um bit limpo, virá-lo, e decrementar tanto a contagem de blocos livres do descritor de grupo quanto a do superbloco para manter os dois níveis de contabilidade consistentes.

Inodes e a árvore de ponteiros de bloco

Um inode ext2 (128 bytes no formato original) guarda os metadados de um arquivo (dono, permissões, tamanho, timestamps) e, diferente de como o FAT localiza dados através de uma única cadeia, um array de quinze ponteiros de bloco, i_block[15], que juntos localizam todo bloco que o arquivo ocupa. As primeiras doze entradas são ponteiros diretos, cada um nomeando um bloco de dados diretamente, o que já é suficiente por si só para a grande maioria dos arquivos pequenos comuns, sem indireção alguma. A entrada doze é um ponteiro indireto simples: em vez de apontar para dados, aponta para um bloco inteiramente preenchido com mais ponteiros diretos, estendendo o alcance em mais um bloco inteiro de ponteiros adicionais (1.024 blocos diretos a mais com um bloco de 4 KB, já que cada ponteiro tem 4 bytes). A entrada treze é um ponteiro duplamente indireto, apontando para um bloco cheio de ponteiros indiretos simples, cada um dos quais aponta para um bloco cheio de ponteiros diretos; a entrada quatorze é triplamente indireta, adicionando mais um nível assim. Ler o offset de byte N de um arquivo é então uma questão de dividir pelo tamanho do bloco para obter um número de bloco lógico, depois decidir em qual dos quatro níveis aquele número de bloco cai e percorrer quantos níveis de indireção aquele nível exigir antes de alcançar um ponteiro de bloco de dados real.

uint32_t block_from_offset(struct ext2_inode *inode, uint32_t block_size, uint32_t logical_block) {
    uint32_t ptrs_per_block = block_size / 4;

    if (logical_block < 12)
        return inode->i_block[logical_block];

    logical_block -= 12;
    if (logical_block < ptrs_per_block) {
        uint32_t *indirect = read_block(inode->i_block[12]);
        return indirect[logical_block];
    }

    logical_block -= ptrs_per_block;
    if (logical_block < ptrs_per_block * ptrs_per_block) {
        uint32_t *dbl = read_block(inode->i_block[13]);
        uint32_t *indirect = read_block(dbl[logical_block / ptrs_per_block]);
        return indirect[logical_block % ptrs_per_block];
    }

    // tripla indireção segue o mesmo padrão um nível mais fundo
    return 0;
}

Essa estrutura significa que o tamanho máximo de um arquivo é limitado por quantos blocos quinze ponteiros com até tripla indireção conseguem endereçar no fim das contas, cerca de dois tebibytes com um bloco de 4 KB, mas também significa que localizar um byte distante em um arquivo grande custa mais leituras de bloco do que localizar um perto do início, já que alcançar território triplamente indireto significa ler três blocos de indireção antes de sequer o ponteiro de bloco de dados real ser conhecido.

Entradas de diretório

Um diretório em ext2 é, estruturalmente, um arquivo comum: seus blocos de dados, alcançados através do exato mesmo mecanismo i_block descrito acima, guardam uma sequência de registros de entrada de diretório em vez de conteúdo de arquivo arbitrário. Cada entrada carrega o número de inode que nomeia, um comprimento de registro (rec_len) que vai do início dessa entrada até o início da próxima, um comprimento de nome, uma dica de tipo de arquivo, e o próprio nome, guardado inline em vez de em um offset fixo. O comprimento de registro sendo separado do comprimento de nome é o que permite que uma entrada de diretório seja apagada de forma barata: remover uma entrada só estende o rec_len da entrada anterior para engolir o espaço da apagada, deixando os bytes subjacentes intocados e evitando ter que deslocar toda entrada subsequente para fechar uma lacuna. Uma busca em diretório percorre esses registros linearmente comparando nomes, o que é simples mas significa que um diretório com um número muito grande de entradas não tem busca por nome melhor do que tempo linear, uma limitação que sistemas de arquivos derivados do ext2 posteriores trataram indexando opcionalmente diretórios grandes com uma B-tree com hash em vez disso.

Notas de implementação

As contagens de blocos livres e inodes livres de um descritor de grupo são um cache de informação que os próprios bitmaps já contêm por completo, e uma implementação que atualiza uma sem a outra, ou que trava entre as duas atualizações, produz um volume inconsistente onde as contagens resumo rápidas discordam de uma varredura direta do bitmap; isso é uma das coisas específicas que uma passagem completa no estilo fsck detecta, recalculando as contagens a partir dos bitmaps diretamente em vez de confiar nos resumos em cache. Determinar bem a estratégia de alocação de bloco de um arquivo novo, alocando os blocos de um arquivo do mesmo grupo de seu inode quando o espaço livre permite, em vez de onde quer que o primeiro bloco livre por acaso esteja, não é necessário para correção alguma, mas afeta perceptivelmente o desempenho em mídia rotativa, onde blocos próximos custam bem menos tempo de busca do que blocos espalhados por grupos distantes. Por fim, blocos indiretos são eles mesmos blocos alocados comuns rastreados nos mesmos bitmaps que blocos de dados, então um arquivo grande com várias camadas de indireção consome perceptivelmente mais do orçamento total de blocos de um volume do que seu próprio tamanho de dados sugeriria, inteiramente em contabilidade de ponteiros em vez de conteúdo de arquivo.

Referências

^ The Second Extended File System (a referência de formato em disco mantida há muito tempo por Dave Poirier)
^ OSDev Wiki, “Ext2” (uma referência hobbyist de implementação com exemplos de offset de byte trabalhados)

Ver também

VFS: as abstrações genéricas de superbloco/inode/dentry que as estruturas em disco deste artigo implementam.
FAT: um modelo de alocação por lista ligada, uma resposta estruturalmente diferente ao mesmo problema que a árvore de ponteiros de bloco deste artigo resolve.
Journaling: a técnica de write-ahead logging que sistemas de arquivos posteriores adicionaram para evitar a varredura completa de recuperação deste formato.
ISO 9660: um formato somente leitura e write-once que não precisa de bitmap de alocação algum deste artigo.
Panics de Kernel e Stack Backtraces: a resposta de último recurso que s_errors pode selecionar ao descobrir corrupção.