# Ext2

O ext2 (do inglês: second extended file system, em português: segundo sistema de arquivos estendido) é um sistema de arquivos para o núcleo do Linux. Foi inicialmente desenvolvido por Rémy Card como um substituto para o extended file system (ext). Projetado de acordo com os mesmos princípios do Berkeley Fast File System do BSD, foi o primeiro sistema de arquivos de nível comercial para Linux.
A implementação da Canonical do ext2 é o controlador (driver) do sistema de arquivos "ext2fs" no kernel do Linux. Outras implementações (de qualidade e completude variadas) existem no GNU Hurd, no MINIX 3, em alguns núcleos do BSD, no MiNT e como drivers Microsoft Windows e macOS de terceiros.
O ext2 era o sistema de arquivos padrão em várias distribuições Linux, incluindo o Debian e o Red Hat Linux, até ser suplantado pelo ext3, que é quase totalmente compatível com o ext2 e é um sistema de arquivos de registro. O ext2 ainda é o sistema de arquivos de escolha para mídia de armazenamento baseada em flash (como cartões SD e unidades flash USB) porque a falta de um registro (journal) aumenta o desempenho e minimiza o número de gravações, e os dispositivos flash têm um número limitado de ciclos de gravação. No entanto, os núcleos do Linux recentes suportam um modo sem registro do ext4, que fornece benefícios não encontrados no ext2.

## História

Esta seção é baseada no texto de Card, Ts'o e Tweedie [1994].
Linus Torvalds adaptou o sistema de arquivos do MINIX, de Andrew Tanenbaum, para o Linux. Entretanto, aquele sistema tinha várias limitações, como o tamanho do volume suportado (máximo de 64 MiB) e nome de arquivos (até 14 caracteres).
Após a inclusão do VFS (Virtual Filesystem) no núcleo inicialmente escrito por Chris Provenzano, depois reescrito por Torvalds, Rémy Card criou o Ext em 1992, que foi incluído no Linux 0.96c. Esse sistema de arquivos estendeu o limite do volume para 2 GiB e o tamanho do nome de arquivo para 255 caracteres.
O Ext ainda tinha alguns problemas, como a falta de suporte a modificação em nós-i e no tempo de modificação do arquivo. E com o uso, o sistema ficava fragmentado e lento. No início de 1993 foram disponibilizados 2 novos sistemas: o XiaFS, de Frank Xia, também baseado no Minix; e o Ext2, que tornou-se o sistema de arquivos padrão para instalações Linux.

## Características técnicas

Ext2 foi projetado e implementado para corrigir as deficiências do Ext e prover um sistema que respeitasse a semântica UNIX. A influência do UNIX pode ser vista, por exemplo, na utilização de grupos de blocos, que são análogos aos grupos de cilindros utilizados pelo FFS [CARD, TS'O & TWEEDIE, 1994]. A versão original do FFS originou o que é hoje conhecido como UFS1 (Unix File System 1) [MCKUSIC & NEVILLE-NEIL, 2005].
O bloco, que consiste num conjunto de setores (cada setor tem 512 bytes), é a menor unidade de alocação para o Ext2. O tamanho pode ser de 1024, 2048 ou 4096 bytes e é definido na formatação. [BOVET e CESATI, 2005, p. 739].
O tamanho máximo de um volume Ext2 é de 8 TiB [MINGMING CAO et al, 2005]. Embora o superbloco (v. abaixo) contenha um campo de 32 bits que determina o número de blocos (s_blocks_count), o que permitiria armazenar até 16 TiB, o tamanho é limitado pelo número de grupos de bloco, que é de 65 536 (determinado pelo campo s_block_group_nr), pois o campo ocupa dois bytes (16 bits). Assim, caso o volume seja formatado usando blocos de 4 KiB, cada grupo de blocos tem até 32 768 blocos; com 65 536 blocos obtém-se o limite indicado (4 KiB * 32 768 * 65 536 = 8 589 934 592 KiB = 8 TiB).
As subseções a seguir descrevem, resumidamente, as estruturas do Ext2 (superbloco, nó-i, grupos de blocos, mapas de bits de blocos e de nós-i e tabelas de nós-i), que são mostradas com mais profundidade e detalhamento por Carrier [2005, pp. 449–460], Bovet & Cesati [2005, pp. 741–746] e, principalmente, no código fonte do Linux—neste texto foi usado como referência a versão 2.6.28.8 (de março de 2009) [TORVALDS et al, 2009].

### Superbloco

O superbloco é a estrutura básica do Ext2. Ocupa 1024 bytes e inicia no terceiro setor do volume.
| Bytes | Campo | Descrição | Bytes | Campo | Descrição |
| 0-3 | s_inodes_count | Número de nós-i | 68-71 | s_checkinterval | Intervalo entre verificações |
| 4-7 | s_blocks_count | Número de blocos | 72-75 | s_creator_os | Criador (SO) |
| 8-11 | s_r_blocks_count | Número de blocos reservados | 76-79 | s_rev_level | Versão maior |
| 12-15 | s_free_blocks_count | Número de blocos não alocados | 80-81 | s_def_resuid | UID do dono dos blocos reservados |
| 16-19 | s_free_inodes_count | Número de nós-i não alocados | 82-83 | s_def_resgid | GID do dono dos blocos reservados |
| 20-23 | s_first_data_block | Primeiro bloco do grupo 0 | 84-87 | s_first_ino | Primeiro nó-i não reservado |
| 24-27 | s_log_block_size | Tamanho do bloco | 88-89 | s_inode_size | Tamanho do nó-i |
| 28-31 | s_log_frag_size | Tamanho do fragmento | 90-91 | s_block_group_nr | Número deste grupo de blocos [1] |
| 32-35 | s_blocks_per_group | Número de blocos por grupo | 92-95 | s_feature_compat | Sinalizadores de compatibilidade |
| 36-39 | s_frags_per_group | Número de fragmentos por grupo | 96-99 | s_feature_incompat | Sinalizadores de incompatibilidade |
| 40-43 | s_inodes_per_group | Número de nós-i por grupo | 100-103 | s_feature_ro_compat | Indicadores de somente leitura |
| 44-47 | s_mtime | Tempo da última montagem | 104-119 | s_uuid | ID do sistema de arquivos |
| 48-51 | s_wtime | Tempo da última alteração | 120-135 | s_volume_name | Nome do volume |
| 52-53 | s_mnt_count | Contador de montagens | 136-199 | s_last_mounted | Caminho da última montagem |
| 54-55 | s_max_mnt_count | Número máximo de montagens | 200-203 | s_algorithm_usage_bitmap | Algoritmo de uso de mapa de bits |
| 56-57 | s_magic | Assinatura (0xef53) | 204 | s_prealloc_blocks | Número de blocos pré-alocados para arquivos |
| 58-59 | s_state | Estado do sistema de arquivos | 205 | s_prealloc_dir_blocks | Número de blocos pré-alocados para diretórios |
| 60-61 | s_errors | Método de manipulação de erros | 206-231 | | Sem uso para Ext2 |
| 62-63 | s_minor_rev_level | Versão menor | 232-235 | s_last_orphan | Cabeçalho da lista de nós-i órfãos |
| 64-67 | s_lastcheck | Tempo da última verificação | 236-1023 | | Sem uso |
Observações sobre a tabela:
[1] O superbloco possui cópia(s) espalhadas no volume, e este número identifica o grupo de blocos em que o superbloco está contido.

### Nó-i

Um arquivo é descrito (a menos do seu nome e seu diretório pai) por um nó-i (inode ou index node). O nó-i é uma estrutura de dados com tamanho padrão de 128 bytes. O tamanho é definido na formatação (mke2fs -I tamanho). Alguns parâmetros são obrigatórios (ou essenciais), como as permissões, o tamanho do arquivo e o endereçamento dos blocos alocados. Outros, embora úteis e quase sempre definidos, são opcionais, como o UID, GID, rótulos de tempo, etc. A tabela seguinte mostra sua estrutura.
| Bytes | Campo | Descrição | Bytes | Campo | Descrição |
| 0-1 | i_mode | Permissões e atributos [1] | 40-87 | i_block | 12 endereços de blocos |
| 2-3 | i_uid | UID: 16 bits menos significativos | 88-91 | i_block | Um endereço de bloco indireto simples |
| 4-7 | i_size | Tamanho do arquivo [2] | 92-95 | i_block | Um endereço de bloco indireto duplo |
| 8-11 | i_atime | Último acesso ao arquivo | 96-99 | i_block | Um endereço de bloco indireto triplo |
| 12-15 | i_ctime | Última modificação do nó-i | 100-103 | i_generation | Número de geração (NFS) |
| 16-19 | i_mtime | Última modificação do arquivo | 104-107 | i_file_acl | Atributo estendido (ACL) do arquivo |
| 20-23 | i_dtime | Tempo de remoção do arquivo | 108-111 | i_dir_acl | ACL de diretório ou tamanho de arquivo [3] |
| 24-25 | i_gid | GID: 16 bits menos significativos | 112-117 | i_faddr | Informações de fragmentos [4] |
| 26-27 | i_links_count | Contador de links | 118-119 | | Não usado |
| 28-31 | i_blocks | Contador de setores | 120-121 | l_i_uid_high | UID: 16 bits mais significativos |
| 32-35 | i_flags | Sinalizadores | 122-123 | l_i_gid_high | GID: 16 bits mais significativos |
| 36-39 | | Reservado | 124-127 | | Não usado |
Observações sobre a tabela:
[4] O Ext2 não usa fragmentos.
O nó-i contém dois registros para contar o tamanho do arquivo: (i) i_size, que mostra o tamanho em bytes (definido por dois campos de 32 bits); (ii) i_blocks, que, apesar do nome, mostra o número de setores ocupados pelo arquivo. O registro i_size permite um valor de 8 EiB ((2$^{63}$ - 1) bytes pois, segundo Bovet e Cesati [2005, p. 746], um dos bits não é usado). O número máximo de setores definido por i_blocks é 4 294 967 295 (2$^{32}$ - 1); como um setor tem 512 bytes, o valor suportado é de 2 TiB. Portanto, o Ext2 suporta arquivos com, no máximo, 2 TiB de tamanho.
São usados 48 bytes para o endereçamento direto de 12 blocos. Caso o arquivo ocupe mais espaço, os quatro bytes seguintes do nó-i endereçam um bloco indireto simples, que contém endereços de blocos de dados; se ainda não for suficiente, mais quatro bytes identificam um bloco indireto duplo (o qual endereça blocos indiretos simples); finalmente, quatro bytes apontam para um bloco indireto triplo (que endereça blocos indiretos duplos). Nesse esquema, usando-se blocos de 4 KiB, podem-se alocar mais de 4 TiB para um arquivo, embora o limite para o tamanho do arquivo seja menor, como visto anteriormente.
Existem quatro campos (i_atime, i_ctime, i_mtime, i_dtime), cada um com 32 bits, para contar o tempo em segundos, a partir de 00:00:00 de primeiro de janeiro de 1970. Os quatro tempos marcados são: access time – atime (marca o último acesso ao arquivo); change time – ctime (tempo de alteração do nó-i); modification time – mtime (tempo de modificação do arquivo); deletion time (marca quando o arquivo foi apagado, enquanto o nó-i não for reaproveitado).

### Grupos de blocos

Um volume (partição ou unidade lógica) Ext2 é dividido em grupos de blocos de mesmo tamanho (à exceção do último, que pode ser menor). Com um tamanho de bloco de 4 KiB, um grupo contém 32 768 blocos.
Cada grupo de blocos possui uma tabela de descritores que endereçam os mapas de bits dos blocos e dos nós-i e a tabela de nós-i. O primeiro grupo contém o superbloco, que possui cópia em alguns outros grupos. No mapa de bits de blocos, cada byte mapeia 8 blocos (um por bit). O bit menos significativo identifica o bloco de menor número. O mapa de bits de nós-i é análogo.

#### Mapa de bits de blocos

Um mapa de bits de bloco é usado para mostrar quais os blocos que, dentro do grupo, estão livres ou alocados. Quando o tamanho de bloco é de 4 KiB, podem ser mostrados 32 768 blocos (4096 * 8). Um bit "1" indica que o bloco correspondente está alocado e um bit "0" indica que o bloco está livre. O primeiro byte do bloco mostra os primeiros 8 blocos do grupo; o bit menos significativo mostra o primeiro bloco e o bit mais significativo mostra o oitavo bloco.

#### Mapa de bits de nós-i

Um mapa de bits de nós-i é usado para indicar a alocação de nós-i, de modo análogo à alocação de blocos vista anteriormente. Como o número de nós-i é, geralmente, menor que o número de blocos, somente uma parte do bloco é usada.

#### Tabela de nós-i

A tabela de nós-i é formada por blocos consecutivos após os mapas de bits. Cada entrada na tabela é um nó-i; assim, um bloco de 4 KiB pode conter até 32 nós-i.

### Alocação de blocos

Quando é realizada uma operação de escrita em um arquivo, o Ext2 tenta, sempre que possível, alocar blocos de dados no mesmo grupo que contém o nó-i. Esse comportamento reduz o movimento da(s) cabeça(s) de leitura-gravação da unidade de disco.
Em um sistema de arquivos ocorrem dois tipos de fragmentação: (i) a fragmentação interna (ou de espaço) é causada pelo fato do tamanho do arquivo geralmente não ser múltiplo do tamanho do bloco (portanto o último bloco terá um espaço não utilizado) -- a consequência é a perda de espaço; (ii) a fragmentação externa (ou de arquivo) decorre da impossibilidade do sistema determinar, a priori, qual o tamanho do arquivo (p.ex., arquivos de texto e de logs são muito modificados, e o seu tamanho pode aumentar ou diminuir) -- assim um arquivo pode alocar blocos não contíguos, prejudicando o desempenho.
Para diminuir o impacto do primeiro tipo, existem duas estratégias básicas. A primeira, mais simples, é determinar, na formatação, o menor tamanho de bloco possível. O Ext2 permite tamanhos de blocos de 1024, 2048 e 4096 bytes. Um tamanho de bloco pequeno, como 1024 bytes, diminui a fragmentação e perda de espaço, mas em contrapartida gera um impacto negativo no desempenho, pois acarreta o gerenciamento de uma maior quantidade de blocos. O tamanho de bloco padrão para volumes grandes é de 4096 bytes.
A segunda estratégia é alocar a parte final de um arquivo, menor que o tamanho de um bloco, juntamente com pedaços de outros arquivos. O Reiserfs chama esse método de tail packing; o UFS usa fragmentos, que são submúltiplos do tamanho do bloco. Apesar do Ext2 possuir, no superbloco, a previsão para uso de fragmentos, esse método não foi implementado.
Para diminuir o impacto da fragmentação externa, o Ext2 pré-aloca (reserva) até oito blocos quando um arquivo é aberto para gravação. Esses blocos reservados, quando possível, são adjacentes ao último bloco utilizado pelo arquivo. [CARD, TS'O e TWEEDIE, 1994]