Como funciona o ext2fs?

No, agora exinto, projeto Heisenberg OS, tinha deixado para decidir qual file system usar e, ao mesmo tempo, iniciado os estudos a respeito do ext2fs, usado no Linux e outros unixes por ai. Um filesystem é uma estrutura de dados que permite usarmos a abstração de “arquivos” para armazenamento de blocos de dados em dispositivos como HDs, disquetes, pen-drives etc. Ao invés de pedirmos ao sistema “leia 16 setores a partir da trilha 612, cabeça 2, setor 10”, podemos simplesmente pedir “leia 8 kB do arquivo ‘xpto.txt’, do diretório /var/tmp/”.

Como isso funciona? É típico que os dispositivos de armazenamento de blocos (discos) suportem um tamanho de bloco fixo de 512 bytes — que equivale a um único setor — mas, o ext2fs e seus descendentes usam tamanhos de blocos múltiplos de 1 kB (1, 2, 4 ou 8 kB, para ser mais exato). Um tamanho de bloco típico é 4 kB (existe um motivo para isso, explico depois). Assim, este é o tamanho mínimo de dados que podem ser lidos/gravados em disco.

blocks

Além dos blocos, ext2fs usa grupos de blocos… Com blocos de 4 kB temos grupos de 8192 blocos estruturados dessa maneira:

group_blocks4

Um superbloco descreve todo o filesystem. Ele não descreve o grupo de blocos, mas todo o seu disco. Além disso, um superbloco tem sempre o tamanho exato de 1 kB, mesmo que o bloco tenha 4 kB (neste caso os 3 kB restantes ficam inúteis).

O bloco dos descritores de grupo descrevem o grupo corrente e tem uma estrutura bem simples:

struct ext2_group_desc
{
  /* bloco do "bitmap de blocos". */
  unsigned int   bg_block_bitmap;

  /* bloco do "bitmap de i-ndes". */
  unsigned int   bg_inode_bitmap;

  /* bloco inicial da tabela de inodes. */
  unsigned int   bg_inode_table;

  /* Quantidade de blocos livres. */
  unsigned short bg_free_blocks_count; 

  /* Quantidade de inodes livres. */
  unsigned short bg_free_inodes_count;
 
  /* Quantidade de diretórios. */
  unsigned short bg_used_dirs_count;   

  unsigned short bg_reserved0;
  unsigned int   bg_reserved1;
};

Os dois blocos de bitmap, descrevem quais blocos estão ocupados ou livres (bitmap de blocos) e quais entradas da tabela de inodes estão ocupadas ou livres (bitmap de i-nodes). Seguem os n blocos de inodes e, por fim, os blocos que contém dados dos arquivos. Esses dois blocos são conjuntos de bits, onde cada bit indica um bloco ou item da tabela de inodes.

Um inode é um descritor de um arquivo… Ele diz qual é o tipo do arquivo, o tamanho, permissões, etc. Essa estrutura não contém o nome do arquivo, que estará localizado num arquivo especial de diretório… O número do inode é a identificação real de um arquivo, não o seu nome! Na figura acima temos os blocos de inodes e de dados contendo número variável de blocos. Todos as outras estruturas ocupam exatamente 1 bloco…

Determinando o tamanho dos blocos de inodes e dados:

Lembre-se: Cada bloco tem 4 kB de tamanho… Isso significa que no bitmap de blocos temos 4096 vezes 8 bits e cada bit corresponde a um bloco em uso ou livre no grupo. Assim, temos 32768 bits e, consequentemente, 32768 blocos no grupo.

Eis duas rotinas de exemplo de como determinar o primeiro bloco livre e determinar quantos blocos adjacentes estão livres:

#include <stdio.h>
#include <string.h>
#include <limits.h>

/* Tamanho de 1 bloco. */
#define BLOCK_MAP_SIZE  4096

/* Vou usar um "unsigned long" para acelerar as rotinas. */
#define BITMASK_SIZE    (sizeof(unsigned long)*8)

/* Faça de conta que um bitmap de blocos esteja carregado 
   aqui. */
extern unsigned char block_map[];

/* A partir de um bloco livre, conta quantos blocos 
   contiguos também estão livres. */
int count_contiguos_free_blocks(int blocknum)
{
  unsigned long *bptr;

  /* Usa bptr_end como "batente". */
  unsigned long *bptr_end = 
    (unsigned long *)(block_map + BLOCK_MAP_SIZE);

  int local_block_num;
  int count = 0;

  if (blocknum < BLOCK_MAP_SIZE)
  {
    bptr = (unsigned long *)block_map + 
             (blocknum / BITMASK_SIZE);

    local_block_num = blocknum % BITMASK_SIZE;

    while (bptr < bptr_end)
    {
      if (*bptr & (1UL << local_block_num)) 
        break; 

      count++; 

      if (++local_block_num >= BITMASK_SIZE)
      {
        local_block_num = 0;
        bptr++;
      }
    }
  }

  return count;
}

/* Acha o primeiro bloco livre no bitmap */
int get_first_free_block_index(void)
{
  unsigned long *bptr = (unsigned long *)block_map;

  /* Usa bptr_end como "batente". */
  unsigned long *bptr_end =
    (unsigned long *)(block_map + BLOCK_MAP_SIZE);

  int free_block = -1;
  int block_bit = 0;
  int bit_count = 0;

  while (bptr < bptr_end)
  {
    if ((*bptr & (1UL << bit_count)) == 0) 
      return block_bit; 

    block_bit++; 

    if (++bit_count >= BITMASK_SIZE)
    {
      bptr++;
      bit_count = 0;
    } 
  }

  return free_block;
}

A figura anterior nos diz que o bloco contendo o superbloco pode não existir “dependendo do grupo”. É que, ao invés de manter um único superbloco em todo o filesystem ou cópias em todos os grupos, para poupar espaço, a revisão 1 do ext2fs resolveu colocar cópias do superbloco apenas nos grupos 0, 1, 3n, 5n e 7n, onde n é um inteiro e n \geqslant 1. Isso permite manter cópias do superbloco para que, em caso de catástrofe, ele possa ser recuperado a partir de uma das (poucas) cópias espalhadas pelo disco.

Existe um detalhe importante para quem quiser implementar ext2fs por sua própria conta: O primeiro superbloco (no grupo 0) está sempre localizado na posição 1024 do bloco 0, do grupo 0 — o primeiro quilobyte é reservado para um bootloader (se existir um)! Nas demais cópias, o superbloco localiza-se no início do do bloco 0 do grupo (embora eu não tenha certeza absoluta desse fato!).

Para ilustrar a distribuição das cópias do superbloco, eis um mapa dos primeiros 1024 grupos de um disco de 500 GB. Os caracteres ‘S’ marcam o grupo que contém uma cópia do superbloco, os caracteres ‘.’ indicam grupos que não as possui:

Block group map (começa no grupo 0):
===================================
SS.S.S.S.S...............S.S.....................S..............
.................S...........................................S..
................................................................
...................................................S............
................................................................
.......................S........................................
................................................................
................................................................
................................................................
.................................................S..............
................................................................
.........................S......................................
................................................................
................................................................
................................................................
................................................................

Note que os blocos 0, 1, 3, 5, 7 ,9, 25, 27, 49, 81 etc contém as cópias… Com os superblocos dispersos desse jeito, sobra mais espaço para dados e temos um grande número de backups, se necessário!

Mas, o que dermina mesmo o tamanho do grupo é o bloco de bitmap de blocos. Neste bloco, cada bit, dos 32768 (4096 \cdot 8) indica a ocupação de cada um dos blocos do grupo. Neste bitmap teremos 1027 ou 1028 blocos “reservados” para:

  • Superbloco: 1 bloco (se existir a cópia);
  • Bloco descritor do grupo: 1 bloco;
  • Bitmap de blocos do grupo: 1 bloco;
  • Bitmap de inodes do grupo: 1 blocos;
  • inodes: 1024 blocos.

Porque 1024 blocos para os inodes? Pelo mesmo motivo que temos 8192 blocos num grupo. O Bitmap de inodes nos permite mander o estado de 32768 inodes e cada inode tem 128 bytes de tamanho. Portanto, 1 bloco contém 32 inodes. Logo, precisamos de 1024 blocos para conter todos os inodes. 7164 (se houver um superbloco) ou 7165 blocos para uso dos dados.

inodes:

Os inodes, dentro de um bloco são numerados de 0 até 8191, mas no contexto do filesystem eles são numerados de 0 até numero\_de\_grupos \cdot 4096. Isso permite que um inode num grupo faça referência a um inode em outro grupo e isso é útil para casos onde não há alternativa senão fragmentar um arquivo entre blocos…

A estrutura básica de um inode é:

struct ext2_inode {
  unsigned short i_mode;   /* "modo" como em 'chmod'. */
  unsigned short i_uid;    /* UserID do arquivo. */
  unsigned int   i_size;   /* Tamanho, em bytes. */
  unsigned int   i_atime;  /* timestamp do último acesso. */
  unsigned int   i_ctime;  /* timestamp da criação. */
  unsigned int   i_mtime;  /* timestamp da modificação. */
  unsigned int   i_dtime;  /* timestamp da "deleção". */
  unsigned short i_gid;    /* GroupID do arquivo. */
  unsigned short i_links_count;  /* Quantidade de HARD-links. */
  unsigned int   i_blocks; /* Quantidade de blocos. */
  unsigned int   i_flags;  /* Diversos flags. */
  unsigned int   i_reserved1;
  unsigned int   i_block[15];  /* "Ponteiros" para os blocos. */

  unsigned int   i_generation; /* Versão do arquivo (para NFS) */

  /* Informações sobre ACLs (selinux?). */
  unsigned int   i_file_acl;
  unsigned int   i_dir_acl;

  /* Informações sobre "fragmentos". */
  unsigned int   i_faddr;
  struct {
      unsigned char  l_i_frag;
      unsigned char  l_i_fsize;
      unsigned short i_pad1;
      unsigned short l_i_uid_high; /* Parte superio do UserID. */
      unsigned short l_i_gid_high; /* Parte superior do GroupID. */
      unsigned int   l_i_reserved2;
  } linux;
};

Existem muitos detalhes escondidos nessa estrutura. O que nos interessa são os campos i_blocks, que nos dá a quantidade de blocos usados pelo arquivo; e o array i_block[], que nos diz os blocos usados pelo arquivo… Isso pode parecer estranho, já que temos apenas 15 entradas… As 12 primeiras contém o número exato de um bloco de dados; a 13ª entrada contém o número de um bloco que contém um array com números de blocos de dados; a 14ª entrada faz a mesma coisa, mas é uma indireção dupla (contém um número do bloco que contém um array onde cada item é um nº de bloco que aponta para outro array que contém os números de blocos de dados)… A 15ª entrada faz o mesmo, mas com indireção tripla!!! A figura abaixo ilustra.
ext2_inode
Com esse esquema dá para alocar um espaço absurdamente grande para um único arquivo e usar uma única entrada de inode de 128 bytes!!! Se cada bloco tem 4 kB e cada número de bloco tem 32 bits de tamanho, então cada bloco comporta 1024 números de blocos de dados… Na indireção simples 1024 blocos podem ser indicados. Na indireção dupla, 1048576 (1024 tabelas com 1024 entradas). Na tripla: 1073741824. Somando isso tudo aos 12 blocos que já constam no inode temos a possibilidade de usar 1074791436 blocos de 4 kB para um único arquivo, ou seja, cerca de 4 TB!

Repare que, nos inodes, o que vai no array i_block é o número de um bloco (a mesma coisa nas tabelas de blocos, se usadas as indireções), portanto, o conteúdo de um arquivo pode cruzar a fronteira de um único grupo de blocos.

Diretórios:

Um diretório é um arquivo que contém uma lista da seguinte estrutura:

struct ext_dir_entry_2
{
  unsigned int   inode;     /* inode do "aquivo". */
  unsigned short rec_len;   /* Tamanho dessa entrada. */
  unsigned char  name_len;  /* Tamanho do nome do arquivo. */
  unsigned char  file_type; /* "tipo" do arquivo. */
  char           name[];    /* Nome, de até 255 caracteres. */
}

Onde o “tipo” é uma constante que diz se o “arquivo” é: desconhecido, regular, diretório, dispositivo do tipo caracter, dispositivo do tipo block, fifo, socket ou link simbólico. Repare que a única relação entre o nome e os dados do arquivo estão no primeiro campo: O número do inode associado a ele.

Anúncios

Deixe um comentário

Faça o login usando um destes métodos para comentar:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s