Asignación de bloques y punteros indirectos

1. Del byte al bloque de contenido

En el tema 17 separamos nombre, inodo y contenido. Ahora estudiaremos el mapa que relaciona el espacio de offsets del archivo con las regiones que lo respaldan. El proceso pide bytes; el sistema de archivos debe localizar las unidades correspondientes y atender posibles huecos u otras representaciones.

Bloque lógico del archivo: posición de un bloque dentro de su contenido, numerada desde cero. No es el número de inodo ni una dirección absoluta del dispositivo. El mapa de asignación traduce esa posición a su representación de almacenamiento.

offset de byte x = 2500

bloque lógico L = x / B = 2           división entera
desplazamiento dentro del bloque = x % B = 452

archivo:       bloque 0 │ bloque 1 │ bloque 2 │ ...
mapa:            40          9          71
                                      │
                     buscar el byte 452 de esa unidad de contenido

El ejemplo usa números de bloques de un volumen didáctico. En un sistema real puede haber capas de volúmenes, compresión, compartición y dispositivos que realizan su propia traducción. El objetivo aquí es comprender la estructura del mapa del archivo, sin suponer que un número observado permite acceder directamente a un sector físico.

Para un archivo de tamaño S, los bytes válidos van de cero a S - 1 si no está vacío. Si cada bloque representa B bytes de contenido, el número de bloques lógicos necesarios es ceil(S / B). Un archivo de 1025 bytes con bloques de 1024 necesita dos posiciones de bloque, aunque la segunda solo contenga un byte lógico válido.

Los cálculos de las siguientes secciones suponen bloques de contenido de tamaño fijo. Cuando una estructura consume parte del bloque para enlazarlo o añade índices externos, se indicará qué capacidad estamos contando.

2. Asignación contigua

En la forma contigua más sencilla, un archivo ocupa una secuencia consecutiva de bloques. Su descripción puede guardar un inicio y una longitud. Para localizar el bloque lógico L se suma ese índice al inicio, después de comprobar que pertenece al intervalo.

inicio = 20; cantidad = 6

L del archivo:       0   1   2   3   4   5
bloque del volumen: 20  21  22  23  24  25

para L=4: bloque = inicio + L = 24

El acceso aleatorio requiere una traducción sencilla y el recorrido secuencial aprovecha la cercanía. El problema aparece al crecer: si el bloque siguiente ya pertenece a otro archivo, la descripción de un único tramo no puede ampliarse allí. Se necesita reservar margen, mover contenido, elegir otro lugar o admitir más tramos.

Espacio total y tramo disponible

Si hay diez bloques libres repartidos en huecos de dos, tres y cinco, existe capacidad total para ocho bloques, pero no un tramo contiguo de ocho. Esta es la diferencia entre disponibilidad agregada y disponibilidad con la geometría exigida por la asignación.

La asignación contigua describe una estrategia conceptual. No significa que todo formato moderno obligue a mover el archivo completo cuando crece: una lista o árbol de extensiones permite representar varios tramos.

3. Asignación enlazada

En una asignación enlazada, cada unidad conduce a la siguiente. Los bloques pueden estar dispersos y el archivo puede crecer incorporando otro bloque libre sin encontrar un tramo completo.

inicio → bloque 8 → bloque 31 → bloque 5 → bloque 42 → fin
          L=0          L=1         L=2         L=3

Para llegar al bloque lógico 3 desde el inicio se recorren los enlaces previos.

La lectura secuencial puede seguir los enlaces. El acceso aleatorio a una posición lejana, si solo se conoce el inicio y no se dispone de otra ayuda, exige recorrer posiciones anteriores. Mantener información auxiliar en memoria puede cambiar ese costo observado, pero no convierte la representación básica en un índice directo.

Dónde se guarda el enlace

En una variante, el enlace se guarda dentro de cada bloque, por lo que no todos sus bytes quedan disponibles para contenido. Si un bloque de 1024 bytes reserva cuatro para el siguiente puntero, su carga útil sería 1020 en ese modelo. La traducción del offset tendría que usar esa carga útil, no reutilizar automáticamente la fórmula de bloques de contenido de 1024.

Otra organización mantiene los enlaces en una tabla aparte, como la idea de una tabla de asignación. Eso desplaza el costo y puede favorecer la consulta si la tabla está disponible en memoria. Se debe especificar la variante antes de calcular capacidad o cantidad de accesos.

Una cadena también debe poder detectar su final y mantener consistencia: un enlace roto, un ciclo o una unidad asignada a dos archivos no son estados válidos del modelo simple. La verificación del mapa necesita comprobar más que “todos los números están dentro del volumen”.

4. Asignación indexada

Una asignación indexada guarda las referencias a los bloques en una estructura separada. El bloque lógico selecciona una entrada del índice. Los bloques de contenido no necesitan ser contiguos y la consulta no recorre una cadena de contenido anterior.

inodo → bloque índice
             entrada 0 → bloque 8
             entrada 1 → bloque 31
             entrada 2 → bloque 5
             entrada 3 → bloque 42

Para L=3 se consulta la entrada 3 del índice y después su bloque de contenido.

Si un bloque índice tiene B bytes utilizables para punteros y cada puntero ocupa P, caben N = B / P entradas cuando la división es exacta y no se reservan cabeceras. Ese índice puede referenciar N bloques de datos. El propio índice consume espacio adicional.

Para archivos pequeños, reservar un bloque índice completo puede ser un costo importante. Para archivos grandes, un solo índice tiene capacidad limitada. Una combinación de referencias directas y varios niveles de índices adapta el recorrido al tamaño del archivo.

Estas estrategias permiten comparar responsabilidades. Su complejidad estructural no proporciona por sí sola el rendimiento de una aplicación: también importan tamaño de transferencia, caché, patrón, profundidad de E/S y asignación efectiva.

5. Directos e indirectos en el esquema clásico

El esquema clásico que estudiaremos combina D punteros directos con un puntero indirecto simple, uno doble y uno triple. Los directos se encuentran en el inodo y conducen a bloques de datos; los otros conducen a estructuras de índices.

inodo
 ├─ D referencias directas ───────────────────────────→ datos
 ├─ simple → índice ──────────────────────────────────→ datos
 ├─ doble  → índice → índice ─────────────────────────→ datos
 └─ triple → índice → índice → índice ────────────────→ datos

Cada bloque índice puede contener N referencias en este modelo.
Capacidad de datos por región: D, N, N² y N³ bloques.

La documentación del mapa directo e indirecto de ext2/3 describe la variante con doce referencias directas y referencias de cuatro bytes. El modelo de este tema permite variar esos parámetros; no afirma que todo inodo de UNIX o todo archivo ext4 use esa representación.

Los archivos pequeños pueden quedar cubiertos por referencias directas. Cuando se utiliza la región simple aparece un bloque índice. Al llegar a la doble se incorpora una raíz de segundo nivel y los índices necesarios por debajo. La triple añade otro nivel de selección.

Referencias dentro del inodo y bloques adicionales

Los D punteros directos ya ocupan bytes del inodo. No se suma un bloque de índice externo por cada puntero directo. En cambio, los índices de las regiones indirectas requieren bloques adicionales cuando se utilizan. Distinguir esas dos formas de almacenamiento evita sumar metadatos de más.

La profundidad es el número de índices atravesados, no una promesa de accesos físicos. Con el inodo y todos los índices en memoria puede no ser necesario leer metadatos del dispositivo. Sin esa información disponible, el recorrido incorpora dependencias antes de localizar el contenido.

Un bloque no asignado puede representar un hueco según las reglas del formato. Los cálculos de metadatos de la sección 8 suponen un prefijo de archivo completamente asignado, sin huecos. Si se asigna solo una posición lejana, el árbol necesario es distinto.

6. Calcular la ruta de un bloque

Primero se obtiene el bloque lógico L dividiendo el offset de byte por B. Después se identifica la región. En cada paso se resta la capacidad de las regiones anteriores; los índices locales siempre empiezan en cero.

si L < D:
    directo[L]
si no:
    q = L - D
    si q < N:
        simple[q]
    si no:
        q = q - N
        si q < N²:
            doble[q / N][q % N]
        si no:
            q = q - N²
            si q < N³:
                triple[q / N²][(q / N) % N][q % N]
            si no:
                fuera de capacidad

Ejemplo con B = 1024, P = 4 y D = 12

Caben N = 256 referencias por bloque índice. Las fronteras del mapa son las siguientes; el fin exclusivo indica el primer bloque que ya no pertenece a esa región.

Para L = 600, se restan los doce directos y los 256 simples: q = 332. Su ruta es doble[1][76], porque 332 = 1 × 256 + 76. Para el primer triple, L = 65804, el resto local es cero y la ruta resulta triple[0][0][0].

Para un byte en posición x = 600 × 1024 + 17 = 614417, la ruta de índices es la misma que para L=600; al llegar al contenido se selecciona el desplazamiento 17. La posición dentro del bloque no es otro nivel de índice.

7. Capacidad máxima del modelo

Con un puntero para cada nivel indirecto y sin limitar todavía el volumen, el mapa cubre la suma de sus regiones. La fórmula cuenta bloques de datos direccionables, no bloques totales consumidos por el árbol.

N = B / P
K = D + N + N² + N³
S_máximo_del_modelo = K × B

Para B=1024, P=4, D=12:
    N = 256
    K = 12 + 256 + 65536 + 16777216 = 16843020
    S = 17247252480 bytes
    último byte = 17247252479

Para B=4096, P=4, D=12:
    N = 1024
    K = 1074791436
    S = 4402345721856 bytes

El segundo resultado ronda cuatro TiB, pero no declara el límite efectivo de un sistema de archivos concreto. Puede haber restricciones del campo de tamaño, contadores de asignación, formato, arquitectura, APIs, tamaño del volumen y características habilitadas. La capacidad de una estructura es solo una de esas cotas.

Capacidad y ancho del puntero

En este modelo un puntero de P bytes también tiene un espacio de valores limitado para identificar bloques del respaldo. No todos los números de bloque posibles tienen por qué estar disponibles para datos; puede haber valores reservados. Aumentar B hace caber más referencias por índice, pero no elimina los otros límites del formato.

Al resolver un ejercicio, conviene declarar qué se pide: capacidad de direccionamiento por archivo, volumen máximo representable, mayor longitud admitida por la implementación o capacidad disponible ahora. Son resultados relacionados, pero no intercambiables.

Un cálculo entero debe evitar desbordamientos. Las potencias y el producto final se calculan en un tipo suficientemente amplio y con comprobaciones; usar un entero de 32 bits para el resultado de varios GiB puede producir un número pequeño que parezca plausible.

También se deben indicar las unidades. Un KiB son 1024 bytes y un MiB, 1048576. El programa imprimirá bytes y cantidades enteras de bloques para que la comprobación no dependa de redondeos de una cifra decimal.

8. Cuántos bloques de índices hacen falta

Supongamos un archivo cuyo prefijo está completamente asignado. Sea k la cantidad de bloques de datos que utiliza y sean s, d y t los que caen en las regiones simple, doble y triple. Se llenan en ese orden después de los directos.

si s > 0: metadatos simples = 1
si d > 0: metadatos dobles = 1 + ceil(d / N)
si t > 0: metadatos triples = 1 + ceil(t / N²) + ceil(t / N)

Si una región no tiene datos, su contribución es cero.

total del modelo en bloques = k + índices simples + dobles + triples
No incluye el espacio del inodo, bitmaps, directorios, journal ni otras estructuras.

El salto entre 268 y 269 bloques de datos es especialmente útil: añadir un bloque de contenido requiere además dos bloques nuevos de índices. El archivo sigue teniendo una única identidad; lo que crece es su mapa de asignación.

Árbol completo

Si todas las regiones están llenas, la simple usa un bloque; la doble, 1 + N; y la triple, 1 + N + N². En conjunto los índices externos suman 3 + 2N + N². Para N=256 son 66051, además de los 16843020 bloques de datos.

La fórmula depende de un prefijo denso. Si solo se asigna un bloque en una posición triple lejana, hacen falta los índices de esa ruta, pero no todos los índices correspondientes a los bloques lógicos anteriores. El tamaño lógico puede abarcar huecos. El próximo tema medirá ese tipo de diferencias.

Un costo de metadatos del mapa tampoco es la ocupación completa del volumen. Sumar únicamente datos e índices deja fuera otras estructuras y políticas. Al comparar con st_blocks o herramientas de un formato, hay que revisar qué contabilidad devuelve cada una.

9. Extents y límites de la comparación

Cuando varias posiciones lógicas consecutivas corresponden a un tramo consecutivo del respaldo, se puede describir la relación mediante inicio lógico, inicio del respaldo y longitud. Esa representación evita enumerar un puntero por bloque para cada tramo.

inicio lógico    inicio del volumen    cantidad de bloques
       0                  100                  4
       4                   50                  3

L=2 → 100 + (2-0) = 102
L=5 →  50 + (5-4) = 51

Los tramos son contiguos por dentro; el archivo completo no exige un único tramo.

Los extents pueden organizarse en árboles para escalar a muchas regiones. La documentación del árbol de extents de ext4 describe una representación distinta del mapa clásico de punteros. No debemos aplicar automáticamente la fórmula D+N+N²+N³ a un archivo que utiliza ese árbol.

La fragmentación cambia cuántas regiones hacen falta, pero el número de extents no es por sí solo una predicción de milisegundos. Hay que considerar tamaños, patrón de acceso y capas de almacenamiento. Un extent lógico informado por una interfaz tampoco identifica necesariamente un único comando físico del dispositivo.

Una interfaz de regiones no prueba el formato de índices

FIEMAP informa regiones del mapa mediante una interfaz de Linux. Puede describir archivos respaldados por distintos esquemas y entregar regiones combinadas cuando el formato usa referencias por bloque. Ver una lista de extents en esa interfaz no demuestra que el inodo contenga un árbol de extents.

El laboratorio tendrá dos vistas complementarias: consulta del mapa de un archivo del sistema anfitrión y una imagen ext2 creada para observar un esquema clásico. La primera enseña a leer una interfaz; la segunda fija un formato para contrastar una frontera de indirección.

10. Calculador de capacidad en C

calcular-indirectos.c recibe B, P, D y un tamaño lógico. Acepta bloques potencia de dos de 512 a 65536 bytes, punteros de cuatro u ocho bytes y entre uno y 32 directos. Calcula capacidad, datos e índices para un prefijo denso, y la ruta del último byte cuando el archivo no está vacío.

No crea un archivo con ese tamaño ni reserva un árbol gigante: usa aritmética. Las operaciones verificadas y la división con resto permiten calcular techos sin sumar divisor - 1 a un numerador cercano al límite del tipo.

#define _POSIX_C_SOURCE 200809L
#include <errno.h>
#include <inttypes.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static int numero(const char *s, uint64_t *resultado)
{
    char *fin;
    uintmax_t n;
    if (!s[0] || strspn(s, "0123456789") != strlen(s)) return -1;
    errno = 0;
    n = strtoumax(s, &fin, 10);
    if (errno || *fin || n > UINT64_MAX) return -1;
    *resultado = (uint64_t)n;
    return 0;
}

static uint64_t sumar(uint64_t a, uint64_t b)
{
    if (a > UINT64_MAX - b) { fprintf(stderr, "Desbordamiento de suma\n"); exit(1); }
    return a + b;
}

static uint64_t multiplicar(uint64_t a, uint64_t b)
{
    if (b && a > UINT64_MAX / b) { fprintf(stderr, "Desbordamiento de producto\n"); exit(1); }
    return a * b;
}

static uint64_t techo(uint64_t n, uint64_t d) { return n / d + (n % d != 0); }
static uint64_t minimo(uint64_t a, uint64_t b) { return a < b ? a : b; }

int main(int argc, char **argv)
{
    uint64_t b, p, directos, bytes, n, n2, n3, capacidad, maxbytes;
    uint64_t datos, resto, s, d, t, ms, md, mt, meta;
    if (argc != 5 || numero(argv[1], &b) || numero(argv[2], &p) ||
        numero(argv[3], &directos) || numero(argv[4], &bytes) ||
        b < 512 || b > 65536 || (b & (b - 1)) ||
        (p != 4 && p != 8) || directos < 1 || directos > 32) {
        fprintf(stderr, "Uso: %s B(512..65536,potencia2) P(4|8) D(1..32) TAMANO\n", argv[0]);
        return 1;
    }
    n = b / p;
    n2 = multiplicar(n, n);
    n3 = multiplicar(n2, n);
    capacidad = sumar(sumar(directos, n), sumar(n2, n3));
    maxbytes = multiplicar(capacidad, b);
    if (bytes > maxbytes) { fprintf(stderr, "Tamaño fuera de capacidad del modelo\n"); return 1; }
    datos = techo(bytes, b);
    resto = datos > directos ? datos - directos : 0;
    s = minimo(resto, n); resto -= s;
    d = minimo(resto, n2); resto -= d;
    t = resto;
    ms = s ? 1 : 0;
    md = d ? sumar(1, techo(d, n)) : 0;
    mt = t ? sumar(sumar(1, techo(t, n2)), techo(t, n)) : 0;
    meta = sumar(sumar(ms, md), mt);
    if (printf("B=%" PRIu64 " P=%" PRIu64 " D=%" PRIu64 " N=%" PRIu64 "\n"
               "capacidad_bloques=%" PRIu64 " capacidad_bytes=%" PRIu64 "\n"
               "tamano=%" PRIu64 " datos=%" PRIu64 " simple_datos=%" PRIu64
               " doble_datos=%" PRIu64 " triple_datos=%" PRIu64 "\n"
               "indices_simple=%" PRIu64 " indices_doble=%" PRIu64
               " indices_triple=%" PRIu64 " indices_total=%" PRIu64 "\n"
               "asignacion_modelo_bytes=%" PRIu64 "\n",
               b, p, directos, n, capacidad, maxbytes, bytes, datos, s, d, t,
               ms, md, mt, meta, multiplicar(sumar(datos, meta), b)) < 0) return 1;
    if (bytes) {
        uint64_t l = (bytes - 1) / b, q = l;
        int r;
        if (printf("ultimo_byte=%" PRIu64 " bloque_logico=%" PRIu64
                   " desplazamiento=%" PRIu64 "\n", bytes - 1, l, (bytes - 1) % b) < 0) return 1;
        if (q < directos) r = printf("ruta=directo[%" PRIu64 "]\n", q);
        else if ((q -= directos) < n) r = printf("ruta=simple[%" PRIu64 "]\n", q);
        else if ((q -= n) < n2) r = printf("ruta=doble[%" PRIu64 "][%" PRIu64 "]\n", q / n, q % n);
        else { q -= n2;
            r = printf("ruta=triple[%" PRIu64 "][%" PRIu64 "][%" PRIu64 "]\n",
                       q / n2, (q / n) % n, q % n);
        }
        if (r < 0) return 1;
    } else if (puts("ruta=archivo_vacio") == EOF) return 1;
    if (fflush(stdout) == EOF) { perror("salida"); return 1; }
    return 0;
}

El tamaño máximo que imprime pertenece al modelo parametrizado. La asignación calculada suma datos e índices externos; no incluye el inodo ni otros recursos del volumen. La ruta impresa corresponde al último byte del tamaño pedido, no al máximo de la estructura salvo que ambos coincidan.

El archivo vacío es un caso explícito: no hay último byte ni bloque de datos. Restar uno a cero con enteros sin signo produciría un valor enorme; por eso el código separa esa rama antes del cálculo.

11. Observar regiones con FIEMAP

El segundo programa consulta FS_IOC_FIEMAP. Solicita regiones por lotes, verifica que el recorrido progrese y conserva un máximo de 128 entradas. La documentación de FIEMAP define coordenadas en bytes, banderas y la posibilidad de que una región exceda el rango solicitado.

El programa no fuerza sincronización ni accede al dispositivo. La preparación del laboratorio sincroniza previamente sus datos. Las coordenadas inciertas o especiales se imprimen como NA en la columna de respaldo; las banderas se conservan para interpretar la respuesta.

#define _GNU_SOURCE
#define _FILE_OFFSET_BITS 64
#include <errno.h>
#include <fcntl.h>
#include <inttypes.h>
#include <linux/fiemap.h>
#include <linux/fs.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/ioctl.h>
#include <sys/stat.h>
#include <unistd.h>

enum { LOTE = 32, MAXIMO = 128, LIMITE = 64 * 1024 * 1024 };

int main(int argc, char **argv)
{
    int fd = -1, estado = 1, completo = 0;
    struct stat inicial, final;
    struct fiemap_extent encontrados[MAXIMO];
    struct fiemap *mapa = NULL;
    uint64_t cursor = 0, anterior = 0;
    unsigned int total = 0;
    if (argc != 2) { fprintf(stderr, "Uso: %s ARCHIVO\n", argv[0]); return 1; }
    fd = open(argv[1], O_RDONLY | O_CLOEXEC | O_NOFOLLOW | O_NONBLOCK);
    if (fd == -1) { perror("open"); goto salir; }
    if (fstat(fd, &inicial) == -1) { perror("fstat"); goto salir; }
    if (!S_ISREG(inicial.st_mode) || inicial.st_size < 0 || inicial.st_size > LIMITE) {
        fprintf(stderr, "Se exige archivo regular de hasta 64 MiB\n"); goto salir;
    }
    mapa = calloc(1, sizeof *mapa + LOTE * sizeof(struct fiemap_extent));
    if (!mapa) { perror("calloc"); goto salir; }
    completo = inicial.st_size == 0;
    for (unsigned int consulta = 0; !completo && consulta < MAXIMO / LOTE; ++consulta) {
        memset(mapa, 0, sizeof *mapa + LOTE * sizeof(struct fiemap_extent));
        mapa->fm_start = cursor;
        mapa->fm_length = (uint64_t)inicial.st_size - cursor;
        mapa->fm_extent_count = LOTE;
        int r;
        do { r = ioctl(fd, FS_IOC_FIEMAP, mapa); } while (r == -1 && errno == EINTR);
        if (r == -1) {
            int error = errno;
            fprintf(stderr, "FIEMAP: %s\n", strerror(error));
            estado = error == EOPNOTSUPP || error == ENOTTY || error == ENOSYS ? 77 : 1;
            goto salir;
        }
        if (mapa->fm_mapped_extents > LOTE || total + mapa->fm_mapped_extents > MAXIMO) {
            fprintf(stderr, "Respuesta fuera de los límites de la consulta\n"); goto salir;
        }
        if (!mapa->fm_mapped_extents) { completo = 1; break; }
        for (unsigned int i = 0; i < mapa->fm_mapped_extents; ++i) {
            struct fiemap_extent e = mapa->fm_extents[i];
            if (!e.fe_length || e.fe_logical > UINT64_MAX - e.fe_length ||
                e.fe_logical < anterior || e.fe_logical >= (uint64_t)inicial.st_size) {
                fprintf(stderr, "Regiones inválidas o mapa que cambió\n"); goto salir;
            }
            anterior = e.fe_logical + e.fe_length;
            encontrados[total++] = e;
        }
        if (anterior <= cursor) { fprintf(stderr, "La consulta no progresa\n"); goto salir; }
        cursor = anterior;
        completo = cursor >= (uint64_t)inicial.st_size ||
            (encontrados[total - 1].fe_flags & FIEMAP_EXTENT_LAST);
    }
    if (!completo) { fprintf(stderr, "Mapa incompleto: límite de 128 entradas/4 consultas\n");
        estado = 77; goto salir; }
    if (fstat(fd, &final) == -1) { perror("fstat final"); goto salir; }
    if (inicial.st_size != final.st_size ||
        inicial.st_mtim.tv_sec != final.st_mtim.tv_sec || inicial.st_mtim.tv_nsec != final.st_mtim.tv_nsec ||
        inicial.st_ctim.tv_sec != final.st_ctim.tv_sec || inicial.st_ctim.tv_nsec != final.st_ctim.tv_nsec) {
        fprintf(stderr, "Cambió el archivo durante la consulta\n"); goto salir;
    }
    int viejo = fd;
    fd = -1;
    if (close(viejo) == -1) { perror("close"); goto salir; }
    if (puts("indice,logico,longitud,respaldo_bytes,flags") == EOF) goto salir;
    for (unsigned int i = 0; i < total; ++i) {
        struct fiemap_extent *e = &encontrados[i];
        unsigned int especiales = FIEMAP_EXTENT_UNKNOWN | FIEMAP_EXTENT_DELALLOC |
            FIEMAP_EXTENT_ENCODED | FIEMAP_EXTENT_NOT_ALIGNED |
            FIEMAP_EXTENT_DATA_INLINE | FIEMAP_EXTENT_DATA_TAIL;
        if (printf("%u,%" PRIu64 ",%" PRIu64 ",", i,
                   (uint64_t)e->fe_logical, (uint64_t)e->fe_length) < 0) goto salir;
        if (e->fe_flags & especiales) { if (printf("NA,") < 0) goto salir; }
        else if (printf("%" PRIu64 ",", (uint64_t)e->fe_physical) < 0) goto salir;
        if (printf("0x%08x\n", e->fe_flags) < 0) goto salir;
    }
    if (fflush(stdout) == EOF) { perror("salida CSV"); goto salir; }
    estado = 0;
salir:
    free(mapa);
    if (fd != -1 && close(fd) == -1) { perror("close limpieza"); estado = 1; }
    return estado;
}

El estado 77 es una convención del programa: consulta no disponible o mapa que supera sus límites. Un archivo vacío produce solo la cabecera porque no hay rango que consultar; eso no comprueba si el montaje admitiría FIEMAP para otro archivo.

Las respuestas se guardan antes de imprimirlas para no presentar un prefijo truncado del mapa como si la consulta completa hubiera terminado bien. El chequeo final de tamaño y marcas detecta cambios observables, pero no crea una instantánea atómica: el laboratorio exige una entrada estable.

Una región puede extenderse más allá de EOF en la contabilidad de asignación. El programa conserva su longitud informada; no la recorta para hacerla coincidir con los bytes lógicos del archivo. Tampoco afirma que las coordenadas de respaldo sean direcciones de un SSD físico concreto.

12. Laboratorio de cálculo y de mapas reales

Preparar y compilar

Crea un directorio nuevo en una ubicación de trabajo de Linux y guarda allí los dos programas. El calculador solo hace aritmética; el lector de FIEMAP solo consulta metadatos de la ruta. La entrada para el segundo se prepara de forma exclusiva y se mantiene sin escritores.

$ LAB18=$(mktemp -d ./tema18.XXXXXX)
$ cd "$LAB18"
Guarda aquí calcular-indirectos.c y ver-fiemap.c antes de compilar.
$ uname -r
$ findmnt -T .
$ gcc -std=c11 -O2 -Wall -Wextra -Wpedantic -Werror calcular-indirectos.c -o calcular-indirectos
$ gcc -std=c11 -O2 -Wall -Wextra -Wpedantic -Werror ver-fiemap.c -o ver-fiemap

Fronteras y metadatos

$ ./calcular-indirectos 1024 4 12 0
$ ./calcular-indirectos 1024 4 12 12288
$ ./calcular-indirectos 1024 4 12 12289
$ ./calcular-indirectos 1024 4 12 274432
$ ./calcular-indirectos 1024 4 12 274433
$ ./calcular-indirectos 1024 4 12 307200 > calculo-300.log
$ cat calculo-300.log

12288 bytes llenan los doce directos; añadir un byte utiliza el primer bloque de datos de la simple. 274432 bytes llenan directos y simple; añadir un byte abre la doble. El tamaño 307200 corresponde a 300 bloques de datos y tres índices: uno simple, una raíz doble y una hoja bajo esa raíz.

Para verificar estas relaciones guarda verificar-indirectos.py. Ejecuta casos en ambos lados de cada frontera y también el máximo; usa enteros arbitrarios de Python como comprobación independiente de la aritmética acotada de C.

import subprocess
import sys

def comprobar(b, p, d, tamano):
    n = b // p
    capacidad = d + n + n*n + n*n*n
    r = subprocess.run(["./calcular-indirectos", str(b), str(p), str(d), str(tamano)],
                       check=True, capture_output=True, text=True)
    f = dict(c.split("=", 1) for c in r.stdout.split())
    k = (tamano + b - 1) // b
    resto = max(0, k - d)
    s = min(resto, n)
    doble = min(max(0, resto - n), n*n)
    triple = max(0, resto - n - n*n)
    techo = lambda x, y: (x + y - 1) // y
    meta = int(s > 0) + (1 + techo(doble, n) if doble else 0)
    meta += 1 + techo(triple, n*n) + techo(triple, n) if triple else 0
    esperados = {"capacidad_bloques": capacidad, "capacidad_bytes": capacidad*b,
                 "datos": k, "indices_total": meta, "asignacion_modelo_bytes": (k+meta)*b}
    if any(int(f[clave]) != valor for clave, valor in esperados.items()):
        raise ValueError("capacidad o costo incorrectos")
    if tamano == 0:
        ruta = "archivo_vacio"
    else:
        l = (tamano - 1) // b
        if l < d:
            ruta = f"directo[{l}]"
        elif l < d+n:
            ruta = f"simple[{l-d}]"
        elif l < d+n+n*n:
            q = l-d-n
            ruta = f"doble[{q//n}][{q%n}]"
        else:
            q = l-d-n-n*n
            ruta = f"triple[{q//(n*n)}][{(q//n)%n}][{q%n}]"
        if int(f["bloque_logico"]) != l or int(f["desplazamiento"]) != (tamano-1)%b:
            raise ValueError("posición del último byte incorrecta")
    if f["ruta"] != ruta:
        raise ValueError("ruta incorrecta")

try:
    casos = 0
    for b, p, d in ((1024,4,12), (4096,4,12), (512,8,4)):
        n = b // p
        topes = (d, d+n, d+n+n*n, d+n+n*n+n*n*n)
        tamanos = {0, 1, b-1, b}
        for limite in topes:
            tamanos.update((limite*b-1, limite*b))
            if limite != topes[-1]:
                tamanos.add(limite*b+1)
        for tamano in sorted(tamanos):
            comprobar(b,p,d,tamano)
            casos += 1
    print(f"{casos} casos correctos: capacidad, metadatos y rutas en las fronteras")
except (OSError, ValueError, KeyError, subprocess.SubprocessError) as error:
    sys.exit(f"Verificación fallida: {error}")

$ python3 verificar-indirectos.py

Mapa del archivo del sistema anfitrión

$ mkdir contenido
$ python3 -c 'import os; f=open("contenido/trescientos.bin","xb"); f.write(os.urandom(300*1024)); f.flush(); os.fsync(f.fileno()); f.close()'
$ MAPA18=0; ./ver-fiemap contenido/trescientos.bin > regiones.csv 2> regiones.log || MAPA18=$?; printf 'estado_fiemap=%s\n' "$MAPA18"; cat regiones.log
$ cat regiones.csv

Si el estado es cero, describe coordenadas y banderas; no impongas un número de regiones esperado. Si es 77, conserva el diagnóstico de consulta no disponible o límite del ejemplo. Un archivo vacío puede tener salida sin regiones válida, pero una consulta fallida no debe interpretarse como un archivo sin asignación.

La región final puede cubrir capacidad de un bloque más allá del tamaño lógico. Los índices internos del formato no se obtienen sumando filas FIEMAP. Tampoco la cantidad de filas identifica cuántas operaciones de disco necesitará una lectura.

Una imagen ext2 para contrastar el esquema clásico

Este apartado requiere e2fsprogs. Solo formatea un archivo nuevo llamado mapa.ext2, de 32 MiB, dentro del directorio del laboratorio. No usa dispositivos, montaje ni privilegios. mke2fs -t ext2 fija el formato y -d incorpora el archivo preparado; las opciones se describen en mke2fs(8).

$ command -v mke2fs dumpe2fs debugfs
$ python3 -c 'f=open("mapa.ext2","xb"); f.truncate(32*1048576); f.close()'
$ mke2fs -q -t ext2 -b 1024 -I 256 -m 0 -d contenido mapa.ext2
$ LC_ALL=C dumpe2fs -h mapa.ext2 > formato.txt
$ LC_ALL=C debugfs -R 'stat /trescientos.bin' mapa.ext2 > mapa-clasico.txt
$ cat formato.txt mapa-clasico.txt

Con esta entrada densa de 300 bloques y bloques de 1024 bytes, busca en el mapa una indicación de indirección simple y doble, además de los bloques de contenido. Los números asignados concretos pueden variar. Los tres índices del modelo se contrastan con esa estructura, no con tres filas obligatorias de FIEMAP del archivo anfitrión.

debugfs abre de solo lectura si no se solicita -w; su manual describe la consulta stat. dumpe2fs muestra las características de la imagen para que se compruebe qué formato se creó realmente.

El archivo de imagen pertenece al sistema anfitrión y tiene su propia asignación exterior. El mapa interior corresponde a otro sistema de archivos. No mezcles sus números de bloques ni multipliques una coordenada de una vista por el tamaño de bloque de la otra.

Cómo escribir una conclusión del ensayo

1. Declara el modelo. B, P, D, prefijo denso y estructuras excluidas del costo.
2. Comprueba fronteras. Primer y último índice de cada región, capacidad y último byte.
3. Separa mapas. FIEMAP del archivo anfitrión y mapa clásico de la imagen ext2.
4. Registra el entorno. Montaje, herramientas y características informadas.
5. Expón el límite. No se midieron latencias físicas ni recuperación después de un fallo.

13. Simuladores de asignación y recorrido

Asignar un archivo a un volumen fragmentado

El primer modelo tiene 32 bloques; seis pertenecen a otros objetos. Cada construcción empieza desde ese mismo patrón base, para comparar estrategias sobre la misma disponibilidad. El archivo se representa por una cantidad de bloques de contenido, no por un texto de usuario.

Con ocho bloques pedidos, puede haber capacidad agregada suficiente y ningún tramo contiguo de ocho. Prueba las otras estrategias. La indexada reserva además un bloque para su índice, capaz de representar todas las peticiones permitidas. La enlazada muestra enlaces abstractos, sin descontar bytes de carga útil: no uses ese dibujo para calcular el tamaño de un bloque con puntero interno.

Resolver un byte en un árbol clásico

Para B=1024, P=4 y D=12, consulta offsets 12287, 12288, 274431, 274432, 67383295 y 67383296. Corresponden a los lados de las fronteras directa/simple, simple/doble y doble/triple. El offset de la capacidad total se rechaza: ya es uno posterior al último byte.

Alcance: son modelos independientes. El volumen pequeño no intenta contener el árbol de capacidad completa del segundo. No hay caché, fallos de E/S, límites del formato real, huecos ni accesos al equipo. La ruta indica índices de una representación teórica; no proporciona direcciones físicas ni tiempos de un dispositivo.

14. Resumen

• Primero se convierte el offset de byte en bloque lógico y desplazamiento; después se consulta el mapa.
• La asignación contigua simplifica la traducción, pero un tramo grande exige continuidad disponible.
• La enlazada admite dispersión; su acceso aleatorio básico depende del recorrido de enlaces.
• La indexada guarda referencias aparte y consume metadatos para representar los datos.
• El esquema clásico combina D directos con regiones de N, N² y N³ bloques.
• Las rutas se obtienen restando regiones anteriores y dividiendo el índice local; los índices empiezan en cero.
• La capacidad de contenido del modelo es B×(D+N+N²+N³), no una garantía del límite de una implementación.
• Los índices externos también consumen bloques. Para calcularlos hay que declarar si el archivo es un prefijo denso.
• Un extent describe un tramo; un árbol de extents no usa automáticamente la fórmula del mapa clásico.
• FIEMAP informa regiones y banderas; no certifica el esquema interno del inodo ni autoriza accesos al dispositivo.
• La imagen ext2 permite contrastar una estructura clásica sin montar ni modificar almacenamiento del equipo.

15. Preguntas de repaso y práctica

Para practicar

1. Con B=1024, convierte offsets 0, 1023, 1024 y 614417 en bloque lógico y desplazamiento.
2. Diseña un mapa libre con capacidad total para ocho bloques y sin un tramo de ocho. Comprueba el caso en el simulador.
3. Compara cuántas referencias debe seguir la cadena del ejemplo para consultar L=0 y L=3, distinguiendo recorrido estructural de lecturas físicas.
4. Calcula N para B=512, 1024 y 4096 con P=4 y P=8. Explica cómo afecta a cada nivel de capacidad.
5. Escribe las fronteras del mapa con D=4 y N=64. Comprueba el primer y último bloque de cada región.
6. Obtén una ruta triple con sus tres índices distintos de cero y reconstruye L a partir de ellos.
7. Calcula índices para 268, 269, 524 y 525 bloques con D=12 y N=256. Identifica qué estructura nueva aparece en cada salto.
8. Prueba el calculador con tamaño cero, capacidad máxima, capacidad más uno, números negativos y una potencia de dos no admitida.
9. Ejecuta el verificador y añade otra geometría válida. Conserva los resultados sin crear archivos gigantes.
10. Examina regiones FIEMAP y sus banderas en el archivo preparado. Describe qué información es conocida y qué interpretación queda fuera.
11. Compara el cálculo de 300 bloques con el mapa de la imagen ext2. Separa datos, índices y otros metadatos del volumen.
12. Explica qué cambiaría al asignar únicamente un bloque triple lejano en lugar de un prefijo denso. Reserva la medición de huecos para el tema siguiente.

En el tema 19 estudiaremos cómo pueden agotarse de forma distinta el espacio y los inodos, y mediremos la diferencia entre longitud lógica y asignación en archivos dispersos.