Comentarios de software

Resulta paradójico que el sistema de archivos más utilizado de Linux, y por lo tanto probablemente el más utilizado del mundo del código abierto, el llamado Ext2, Ext3 o Ext4 (según su versión) sea tan desconocido, y sin embargo el sistema FAT12, FAT16 o FAT32 (también según su versión) sea tan popular. Compárense por ejemplo los artículos correspondientes del la Wikipedia (en inglés): FAT frente a Ext2.
El siguiente artículo pretende corregir esta situación describiendo con detalle el sistema Ext2. Como origen principal de información he utilizado, cómo no, el código fuente de Linux.

Introducción

Lo primero que hay que observar es que no existen tres sistemas de archivos diferentes, Ext2, Ext3 y Ext4, sino que solamente existe uno, llamémosle simplemente Ext2, pero con un montón de características (features) opcionales; algunas de estas características son compatibles hacia atrás y otras no. Lo que sí existen son tres módulos de kernel diferentes en Linux, cada uno con un número creciente de características soportadas (más sobre esto más adelante).
A continuación es conveniente aclarar el significado de algunos términos:

• Bloque: un conjunto de bytes contiguos en disco, de un tamaño determinado y que comienza en una posición múltipla de ese mismo tamaño. Todos los bloques tienen el mismo tamaño, que debe ser una potencia de 2. Es importante observar que el espacio en disco siempre se asigna en bloques enteros. El tamaño mínimo de bloque es de 1024 bytes. Algunos bloques se utilizan para guardar datos de archivos y otros para estructuras auxiliares.
• Inodo: estructura en disco que representa un archivo u otro objeto similar (enlace simbólico, fifo, device, etc.). Se identifica de forma únivoca con un número llamado naturalmente “número de inodo”. Puedes ver el número de inodo que corresponde a un archivo con el comando ls -i.
• Grupo de bloques: un conjunto de bloques contiguos, junto con una tabla de inodos. La idea es que se intenten mantener cerca el inodo y los datos de un mismo archivo.
• Descriptor de grupo de bloques: estructura que describe los contenidos de un group de bloques.
• Bitmap: no es un dibujo sino un array de bits, donde cada uno indica si un bloque o inodo está libre o en uso. Se utiliza para buscar rápidamente huecos libres.

La estructura básica de un sistema Ext2 es la siguiente:

Y cada grupo de bloques tiene la siguiente estructura:

A continuación se describen con detalle cada uno de estos elementos.

Libre

Los primeros 1024 bytes del dispositivo de bloques no se utilizan para nada. La idea es que el principio de la partición suele utilizarse para instalar algún tipo de sistema de arranque o de tabla de particiones. Otros sistemas, como FAT, hacen malabarismos para integrar varias estructuras no relacionadas en el primer sector del disco sin que se pisen entre sí.

Superbloque

En la posición 1024 de la partición se encuentra el superbloque. Este contiene información clave del sistema, tanto estática (tamaño de las estructuras) como dinámica (espacio libre). Tan importante es esta estructura que se mantienen copias de ella desperdigadas por el disco, de manera que si se destruyera el comienzo del sistema se pudiera recuperar la mayor información posible (más sobre eso más adelante).

Como unas cuantas líneas de código valen más que mil palabras, aquí está la estructura del superbloque escrita en C (nótese que todos los datos en disco se guardan en Little-Endian, aunque no se indique en el código):

struct Superblock
{
    uint32_t inodes;
    uint32_t blocks;
    uint32_t reserved_blocks;
    uint32_t free_blocks;
    uint32_t free_inodes;
    uint32_t first_data_block;
    uint32_t log_block_size;
    uint32_t fragment_size;
    uint32_t blocks_per_group;
    uint32_t fragments_per_group;
    uint32_t inodes_per_group;
    uint32_t mount_time;
    uint32_t write_time;
    uint16_t mount_count;
    uint16_t max_mount;
    uint16_t magic;
    uint16_t state;
    uint16_t errors;
    uint16_t minor;
    uint32_t last_check;
    uint32_t check_int;
    uint32_t creator_os;
    uint32_t rev_level;
    uint16_t resv_uid;
    uint16_t resv_gid;
    //rev_level == 1
    uint32_t first_inode;
    uint16_t inode_size;
    uint16_t block_group;
    uint32_t feature_compat;
    uint32_t feature_incompat;
    uint32_t feature_ro_compat;
    uint8_t uuid[16];
};

Los campos a partir del comentario rev_level == 1 solo existen si rev_level es mayor o igual a 1 (tu disco es realmente viejo si tienes rev_level a 0). Y hay más campos a continuación de estos, pero que solo se usan con features particulares y no las comentaré aquí.
Los campos del superbloque significan lo siguiente:

• inodes: El número total de inodos en el sistema de archivos.
• blocks: El número total de bloques en el sistema de archivos.
• reserved_blocks: El número de bloques reservados para el usuaro root.
• free_blocks: El número de bloques libres.
• free_inodes: El número de inodos libres.
• first_data_block: El primer bloque utilizable para datos.
• log_block_size: El logaritmo base 2 del tamaño de bloque, menos 10. Es decir, 0 es 1024, 1 es 2048, 2 es 4096, 3 es 8192, etc.
• fragment_size: Los fragmentos son una obsolescencia, así que esto no sirve para nada.
• blocks_per_group: El número de bloques de datos por grupo de bloques.
• fragments_per_group: Véase dos más arriba.
• inodes_per_group: El número de inodos por grupo de bloques.
• mount_time: La fecha/hora de la última vez que se montó el sistema en lectura/escritura (como time_t).
• write_time: La fecha/hora de la última vez que se desmontó el sistema habiéndolo montado como lectura/escritura.
• mount_count: El número de veces que se montó el sistema desde el último chequeo.
• max_mount: Cuando el sistema se monta este número de veces se fuerza un chequeo de mantenimiento.
• magic: Un número fijo que identifica esta estructura. Debe ser 0xEF53.
• state: El estado general del sistema. 1 es correcto, otro valor indica errores.
• errors: Qué hacer si se encuentran errores en el formato de disco. 1 indica continuar como si nada; 2 conmuna el sistema a solo lectura; 3 genera un panic y bloquea el sistema operativo. Puede cambiarse con la opción de montaje errors.
• minor: El número menor de la revisión del formato. Básicamente no sirve para nada.
• last_check: La fecha/hora del último chequeo.
• check_int: Si el último chequeo ha sido hace más de este número de segundos se fuerza un chequeo de mantenimiento.
• creator_os: El sistema operativo en el que se creó este sistema. 0 es Linux, 1 es Hurd, 3 es FreeBSD.
• rev_level: Si es 1 o superior existen los campos posteriores a resv_gid. Es 1 siempre salvo en sistemas prehistóricos.
• resv_uid: El usuario para el que se reservan los reserved_blocks. Normalmente es 0 (root)
• resv_gid: Lo mismo que el anterior, pero el grupo.
• first_inode: El primero inodo disponible para uso general. Casi siempre es 11, que es el valor por defecto si rev_level==0.
• inode_size: El tamaño de la estructura de inodo en disco. Suele ser 128 o 256, pero puede ser cualquier potencia de 2 mayor. Si rev_level==0 es 128.
• block_group: Identifica la copia de este superbloque. Solo es útil para el diagnósticos.
• feature_compat: Features compatibles. Véase más abajo.
• feature_incompat: Features incompatibles. Véase más abajo.
• feature_ro_compat: Features compatibles en modo de solo lectura. Véase más abajo.

Features

Se llaman features (o características) a las modificaciones en el formato de archivos respecto a la implementación Ext2 original. Se clasifican en tres tipos según cómo afectan a la compatibilidad hacia atrás, es decir, a cómo debe comportarse un driver que no conozca esa feature.

• Compatibles: El driver puede funcionar perfectamente ignorando esta característica.
• Incompatibles: El driver no debe utilizar el sistema de archivos si no conoce esta característica.
• RO-compatibles: (ReadOnly o solo lectura) El driver puede leer el sistema de archivos ignorando esta característica, pero no debe modificarlo.

Cada una de estas features se representa con un bit en el campo del superbloque correspondiente.

Algunas features se pueden activar y/o desactivar de un sistema de archivos existente usando el comando tune2fs.
La diferencia entre los distintos drivers Ext2, Ext3 y Ext4 radica principalmente en las features disponibles y activadas por defecto. Así, Ext3 es básicamente igual que Ext2, pero con journal; y Ext4 es Ext3 con extents y flex_bg.

Descriptores de grupos de bloques

En el siguiente bloque al que contiene el superbloque comienza la lista de descriptores de grupos de bloques, que se prolonga por cuántos bloques sea necesario. Puedes calcular cúantos grupos de bloques tiene el sistema dividiendo inodes entre inodes_per_group y redondeando hacia arriba.
La estructura un descriptor de grupo de bloques es:

struct GroupDesc
{
    uint32_t block_bitmap;
    uint32_t inode_bitmap;
    uint32_t inode_table;
    uint16_t free_blocks_count;
    uint16_t free_inodes_count;
    uint16_t used_dirs_count;
    uint16_t dummy[7];
};

Los campos de esta estructura son:

• block_bitmap: El número de bloque donde comienza el bitmap de bloques de datos de este grupo.
• inode_bitmap: El número de bloque donde comienza el bitmap de inodos de este grupo.
• inode_table: El número de bloque donde comienza la tabla de inodos de este grupo.
• free_blocks_count: El número de bloques de datos libres en este grupo.
• free_inodes_count: El número de inodos libres en este grupo.
• used_dirs_count: Cúantos directorios hay en este grupo.
• dummy: Relleno para alinear la estructura. Algunas features utilizan alguno de estos bytes.

La idea es que el driver disponga de estos datos para decidir en qué grupo de bloques crear un fichero minimizando el riesgo de fragmentación.

Grupo de bloques

Un grupo de bloques viene descrito por el descriptor de grupo de bloques correspondiente. Los bloques de datos que corresponden a un grupo no se guardan en el descriptor porque se deducen directamente del campo blocks_per_group del superbloque: el grupo 0 va del 0 a blocks_per_group-1; el grupo 1 va de blocks_per_group a 2*blocks_per_group – 1; el grupo N va de N*blocks_per_group a (N+1)*blocks_per_group – 1. Naturalmente, puesto que los bitmaps y los inodos también son parte del grupo se solapan con los bloques de datos. Para evitar que se machaquen estas estructuras se marcan permanentemente como ocupados en el block_bitmap al crear el sistema de archivos.

En algunos grupos de bloques, al principio de los bloques de datos se guarda una copia del superbloque y de los descriptores de grupos. Naturalmente, en el block_bitmap se marcan estos bloques como ocupados.

La longitud de las estructuras de un grupo de bloques se deduce de campos del superbloque: el bitmap de bloques tiene blocks_per_group bits, alineado hacia arriba a un número entero de bloques; el bitmap de inodos tiene un inodes_per_group bits, alineado de la misma manera; la tabla de inodos tiene inodes_per_group inodos de inode_size bytes cada uno, alineado igualmente.

Tabla de inodos

La tabla de inodos de un grupo de bloques consiste simplemente en un array de inodos, uno tras otro, de inode_size bytes cada uno. La estructura de un inodo es:

struct INode
{
    uint16_t mode;
    uint16_t uid;
    uint32_t size;
    uint32_t atime;
    uint32_t ctime;
    uint32_t mtime;
    uint32_t dtime;
    uint16_t gid;
    uint16_t links;
    uint32_t nr_blocks;
    uint32_t flags;
    uint32_t reserved1;
    uint32_t blocks[12];
    uint32_t iblock;
    uint32_t iiblock;
    uint32_t iiiblock;
    uint32_t generation;
    uint32_t file_acl;
    uint32_t size_hi;
    uint32_t reserved2[4];
};

Los contenidos de esta estructura son intencionadamente similares a varios de los campos de la estructura stat devuelta por las llamadas al sistema stat y fstat (véase man 2 stat para más información).
El significado de los campos es el siguiente:

• mode: El tipo de inodo y los permisos, en un campo de bits. Los 9 bits menos significativos son los permisos (3 para el propietario, 3 para el grupo y 3 para otros), otros 3 bits son para opciones varias, y 4 bits más indican el tipo de inodo.
• uid: El identificador de usuario (uid) propietario del fichero.
• size: Los 32 bits menos significativos del tamaño del fichero, en bytes.
• atime: La fecha/hora del último acceso a los datos del archivo.
• ctime: La fecha/hora del último cambio al contenido de esta estructura (el inodo, no los datos del archivo).
• mtime: La fecha/hora del último cambio a los datos del archivo.
• dtime: La fecha/hora en la que se borró el inodo. Debe ser 0 para inodos existentes y distinto de 0 para inodos borrados.
• gid: El identificador de grupo (gid) propietario del fichero.
• links: El numero de enlaces (links) a este inodo. Se refiere a hard links, no links simbólicos.
• nr_blocks: El número de bloques total que ocupa este inodo. Es, más o menos, el dato devuelto por el comando du.
• flags: Bits varios. La mayoría solo pueden existir si está activada la feature correspondiente.
• reserved1: Este valor se usa en algunos sistemas operativos, para tareas particulares, pero en Linux no se usa para nada.
• blocks: Números de bloques de datos.
• iblock: Número de bloque indirecto.
• iiblock: Número de bloque doble-indirecto.
• iiiblock: Número de bloque triple-indirecto.
• generation: Este es un número secuencial que se incrementa cada vez que se reutiliza el inodo después de borrarlo. Lo necesitan algunos programas como NFS.
• file_acl: El número de bloque donde se guardan los attributos extendidos, si es que existen.
• size_hi: Los 32 bits más significativos del tamaño del fichero (para ficheros de más de 4 GB).
• reserved2: Esto sirve para hacer el tamaño de la estructura exactamente 128 bytes. Estos y los siguientes, si el inodo es mayor de 128 sirven para guardar attributos extendidos y otra información adicional.

Los campos blocks, iblock, iiblock y iiiblock merecen una mención especial. Los primeros 12 bloques de datos se guardan directamente en los valores blocks[0] a blocks[11]. A ficheros más grandes se les asigna un bloque de datos llamado bloque indirecto<, y se guarda su número en iblock. Este bloque se llena con los siguientes números de bloques de datos del fichero.
Así, si el tamaño de bloque es de 4 KB, y puesto que cada número de bloque son 4 bytes, en el bloque indirecto caben 1024 referencias a bloques de datos.
Para ficheros que necesiten más espacio se utiliza un bloque doble-indirecto y se guarda su número en iiblock. Este contiene números de bloques indirectos, así que con bloques de 4 KB puede referenciar 1024 bloques indirectos que son 1024 * 1024 = 1048576 bloques de datos.
Y para ficheros que necesiten aún más espacio existe el bloque triple-indirecto, que es fácil imaginar para qué sirve.

Esta relación puede verse en el siguiente gráfico (tomado prestado de la Wikipedia):

Como optimización especial, si el inodo es un link simbólico, y el tamaño es menor de 60 bytes (casi todos lo son) entonces no se guardan los datos en un bloque de datos, sino que se utiliza directamente el array blocks y los tres campos siguientes como si fuera un array de bytes. Tiene sentido hacerlo para los link simbólicos porque son inmutables, es decir, una vez creados no se pueden modificar.

Directorios

Un directorio es similar a un fichero ordinario, excepto que el campo mode del inodo indica que es un directorio ((mode & 0170000) == 0040000) y que el contenido de datos debe tener un formato particular. Básicamente contiene una lista de entradas de directorio o (direntries), que asocian un nombre con un número de inodo.
Los direntries tienen un tamaño variable, pero cumplen la siguiente estructura:

struct DirEntry
{
    uint32_t inode;
    uint16_t entry_len;
    uint8_t name_len;
    uint8_t type;
    char name[];
};

inode es el número de inodo al que corresponde esta entrada de directorio. Contando entry_len bytes desde el comienzo de una entrada de directorio se encuentra la siguiente, hasta encontrar una de longitud 0 que marca el final. name_len es el número de bytes en del nombre (debe ser menor o igual a entry_len – 8, adivina por qué).
Finalmente, type indica de qué tipo es el inodo al que apunta esta direntry (puede ser 0 si no se conoce). El uso de este campo está condicionado a la feature filetype, que está presente casi siempre.

En futuros post comentaré alguna de las features más populares, que me parece que este ya es bastante largo.

Artículos relacionados:

1. Extensiones de Ext2, Ext3 y Ext4 En el post anterior describía con más o menos detalle...
2. Utilidad para leer particiones Ext2/3/4 En los dos últimos posts describí el formato del sistema...
3. Jugando con device-mapper y loop Hace unos días tuve que mover un archivo grande de...

Filed under:
Formatos, Linux by rodrigo