ext2

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.

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.

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.

Observações sobre a tabela:

[1] Contém sinalizadores (flags) de permissão e tipo: nove bits de permissão “rwx” - leitura, escrita e execução para o dono, grupo e outros; três bits definem o sticky bit, SGID e SUID; quatro bits identificam os tipos de arquivo (regular, diretório, dispositivo, link simbólico, etc.).

[2] Se o arquivo tiver menos que 4 GiB; caso contrário, mostra os 32 bits mais significativos do tamanho—v. [3].

[3] Caso o arquivo tenha 4 GiB ou mais, este campo mostra os 32 bits mais significativos do tamanho—v. [2].

[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⁶³ - 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³² - 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]

1. BOVET, Daniel P.; CESATI, Marco. Understanding the Linux kernel. 3.ed. Sebastopol: O'Reilly. 2005.
2. CARD, Rémy; TS'O, Theodore; TWEEDIE, Stephen. Design and implementation of the Second Extended Filesystem. Proceedings of the First Dutch International Symposium on Linux. 1994. Disponível em <http://web.mit.edu/tytso/www/linux/ext2intro.html>. Acessado em 01 out. 2007.
3. CARRIER, Brian. File system forensic analysis. Upper Saddle River: Addison-Wesley. 2005.
4. TORVALDS, Linus et al. Linux kernel v. 2.6.28.8: include/linux/ext2_fs.h. The Linux Kernel Archives. 2009. Disponível em <http://www.kernel.org/pub/linux/kernel/v2.6/>. Acesso em 19 mar. 2009.
5. MCKUSIC, Marshall K.; NEVILLE-NEIL, George V. The design and implementation of the FreeBSD operating system. Upper Saddle River: Addison-Wesley, 2005.
6. MINGMING CAO et al. State of the art: where we are with the Ext3 filesystem. Ottawa Linux Symposium. 2005. v. 1, pp. 69–96 Disponível em <http://www.linuxsymposium.org/2005/> Acessado em 28 dez. 2008.
7. TS'O, Theodore; TWEEDIE, Stephen. Planned extensions to the Linux Ext2/Ext3 Filesystem. USENIX 2002 Annual Technical Conference. [2002]. Disponível em <http://www.usenix.org/publications/library/proceedings/usenix02/tech/freenix/full_papers/tso/tso.pdf>. Acessado em 17 dez. 2009.

• ReiserFS
• Reiser4
• EXT3
• EXT4