1. Qué construiremos y qué contrato tendrá
Los temas anteriores permitieron interpretar formatos ajenos y controlar E/S. Ahora definiremos nuestro formato MINIFS48, versión 1, y seremos responsables de mantener sus relaciones. Una entrada de directorio deberá conducir a un inodo válido, y cada bloque asignado tendrá un único propietario.
Mini sistema de archivos: formato persistente sobre un archivo imagen, con reglas de nombres, metadatos, asignación y contenido. El programa administra ese formato desde espacio de usuario; no lo registra en el VFS ni requiere montarlo.
- Imagen de 32768 bytes: 64 bloques de 512.
- Un directorio plano con 16 entradas y 16 inodos.
- Archivos binarios de 0 a 3072 bytes; hasta seis bloques directos por archivo.
- Nombres ASCII de 1 a 27 caracteres: letras, dígitos, punto, guion y guion bajo; se excluyen
.y... - Un solo proceso escritor por imagen y rutas de laboratorio confiables; no se implementa coordinación entre escritores.
- Las operaciones mutantes publican un archivo imagen nuevo, con modo 0600, en la misma ruta.
- No hay subdirectorios, hard links internos, enlaces simbólicos internos, permisos por archivo ni crecimiento de la geometría.
El alcance es deliberadamente pequeño para poder revisar el programa completo y sus pruebas. Las rutas de entrada y salida del host son diferentes de los nombres del directorio interno: importar nota.txt no crea una ruta /nota.txt dentro del sistema operativo.
2. Distribución de los 64 bloques
| Bloques | Offset en bytes | Contenido | Capacidad |
|---|---|---|---|
| 0 | 0 | Superbloque y CRC de la imagen. | 512 bytes. |
| 1 | 512 | Bitmap de ocupación. | 64 bits usados; el resto se reserva en cero. |
| 2 | 1024 | Tabla de inodos. | 16 registros de 32 bytes. |
| 3 | 1536 | Directorio raíz fijo. | 16 registros de 32 bytes. |
| 4 a 63 | 2048 a 32767 | Datos de archivos. | 60 bloques, 30720 bytes asignables. |
La capacidad de datos es independiente de la cantidad de nombres. Diez archivos de 3072 bytes agotan los 60 bloques, pero dejan seis inodos libres. Dieciséis archivos vacíos agotan entradas e inodos sin consumir bloques de datos.
3. Superbloque, representación y CRC32
La firma ocupa ocho bytes ASCII, MINIFS48. Los campos numéricos se codifican como uint32 little-endian mediante funciones de bytes; no se copia una estructura C nativa directamente al disco.
| Offset | Campo | Valor de la versión 1 |
|---|---|---|
| 0 a 7 | Firma. | MINIFS48. |
| 8, 12, 16 | Versión, bytes por bloque, bloques totales. | 1, 512, 64. |
| 20, 24 | Cantidad de inodos y entradas de directorio. | 16, 16. |
| 28, 32, 36, 40 | Bloques de bitmap, inodos, directorio y primer dato. | 1, 2, 3, 4. |
| 44 | Punteros directos por inodo. | 6. |
| 48 | CRC32 de la imagen completa. | Campo de cuatro bytes tratado como cero al calcular. |
| 52 a 511 | Reserva. | Todos los bytes en cero. |
El CRC usa el polinomio reflejado 0xEDB88320, semilla 0xffffffff y XOR final 0xffffffff. El verificador lo contrasta con zlib.crc32 sobre una copia cuyo campo de checksum está a cero. No es CRC32C ni una firma de autenticidad.
Una modificación accidental puede romper el CRC. Una imagen puede, además, tener un CRC recalculado que coincide y referencias incoherentes: las pruebas estructurales son una responsabilidad adicional. Tampoco se conserva una copia histórica para reconstruir datos corruptos.
4. Inodos con seis punteros directos
| Offset dentro del inodo | Campo uint32 little-endian | Regla |
|---|---|---|
| 0 | Estado. | 0 libre; 1 ocupado. |
| 4 | Longitud lógica. | De 0 a 3072 bytes. |
| 8 a 31 | Seis números de bloque. | Los usados apuntan a 4..63; los sobrantes son cero. |
bloques_necesarios = (longitud + 511) / 512 [division entera]
indice_del_puntero = offset_logico / 512
desplazamiento_dentro_del_bloque = offset_logico % 512
offset_en_imagen = puntero[indice_del_puntero] × 512 + desplazamiento
Estas formulas de acceso requieren offset_logico < longitud.Un archivo vacío sigue ocupando un inodo y una entrada, con longitud cero y seis punteros cero. Un archivo de 513 bytes necesita dos bloques; el último contiene un byte válido y 511 bytes de relleno cero.
Los bloques no tienen que ser contiguos. La lista de punteros conserva el orden lógico del contenido incluso cuando se reutilizan huecos físicos. El tope de seis punteros explica el límite por archivo, distinto del espacio libre del volumen.
5. Directorio plano e identidad de los archivos
Cada registro de directorio mide 32 bytes: cuatro para el identificador del inodo y 28 para el nombre terminado en NUL. En disco, identificador 0 indica entrada vacía; los valores 1..16 corresponden a índices de inodo 0..15.
El nombre vive en el directorio, no en el inodo. La versión 1 exige un único nombre por inodo, nombres sin duplicados y ningún inodo ocupado sin referencia. La separación entre ambas tablas sigue siendo útil aunque no implementemos hard links.
Se limitan los nombres a un alfabeto ASCII explícito para poder mostrarlos sin caracteres de control ni separadores de ruta. La comparación distingue mayúsculas y minúsculas. El relleno tras el primer NUL permanece en cero y una entrada libre debe contener 32 ceros.
Se reutilizan identificadores al borrar y crear. Por eso un número de inodo no identifica para siempre al mismo archivo: aquí no existen generaciones ni identificadores persistentes entre reutilizaciones.
6. Asignar y liberar bloques con un bitmap
El bit b representa el bloque b, comenzando por el bit menos significativo del byte correspondiente. Los bloques 0..3 siempre están marcados por ser metadatos. El resto debe coincidir exactamente con los bloques referenciados por inodos ocupados.
byte_del_mapa = 512 + b / 8
mascara = 1 << (b % 8)
Asignar: mapa[byte] |= mascara
Liberar: mapa[byte] &= ~mascara
Para importar, recorrer b=4..63 y seleccionar los primeros libres.
Comprobar que hay suficientes antes de modificar la imagen candidata.La estrategia es first fit por número de bloque, sin buscar un intervalo contiguo. Permite usar dos bloques separados para un mismo archivo. Todos los bloques libres y el relleno de la última unidad asignada se mantienen a cero como regla canónica del formato.
Los bloques libres pueden bastar para el contenido, pero faltar una entrada o un inodo. También puede quedar espacio en el disco y aun así superar el límite de 3072 bytes de un archivo. Las comprobaciones distinguen esos casos antes de publicar.
7. Crear, importar, exportar y borrar
- mkfs Construye una imagen vacía en memoria, marca los cuatro bloques reservados y calcula el CRC. La publicación inicial exige que la ruta final no exista.
- put Valida la imagen, lee un archivo regular propio y estable, reserva entrada, inodo y bloques, copia los bytes y publica una versión nueva. No reemplaza un nombre interno existente.
- get Valida y recorre los punteros para escribir un archivo de salida nuevo. No sobrescribe una ruta host existente.
- rm Retira entrada e inodo y libera sus bloques en la nueva imagen, poniéndolos a cero.
- ls y check Consultan la imagen sin reescribirla; ambas requieren que supere la validación.
Los archivos host se abren mediante descriptores y se tratan lecturas y escrituras cortas y EINTR. Se rechazan enlaces simbólicos en el componente final de las rutas de imagen y origen. Las rutas de directorios anteriores se consideran confiables.
get sincroniza el archivo exportado, pero no implementa una transacción de publicación del directorio host de esa salida. El protocolo de reemplazo de imagen de la sección siguiente se aplica a mkfs, put y rm.
La puesta a cero al borrar forma parte del contenido lógico de la versión nueva; no constituye borrado seguro de versiones antiguas en el almacenamiento del host.
8. Comprobar relaciones, no solo una firma
| Invariante | Fallo que detecta |
|---|---|
| Geometría y longitud exactas. | Otra versión, truncamiento o región incorrecta. |
| CRC32 de todos los bytes. | Alteraciones que no coinciden con el checksum almacenado. |
| Nombre válido, único y terminado. | Duplicados o lecturas fuera del campo del nombre. |
| Una referencia por inodo ocupado. | Inodos huérfanos, referencias repetidas o a un inodo libre. |
| Punteros usados dentro de 4..63 y sin propietario previo. | Acceso a metadatos, fuera de imagen o compartición indebida. |
| Bitmap igual a metadatos reservados más bloques referenciados. | Bloques perdidos o declarados libres mientras están en uso. |
| Campos libres y relleno canónico en cero. | Restos de referencias o representación no admitida. |
El validador reconstruye propietarios desde directorio e inodos y los contrasta con el mapa. No confía en el bitmap para demostrar que un puntero pertenece al archivo. Todas las operaciones sobre una imagen existente validan antes de interpretarla como un volumen utilizable.
check no repara. Rechaza incoherencias y conserva los bytes originales. La verificación de que el contenido corresponde a un archivo fuente conocido se realiza aparte, mediante comparación de bytes en las pruebas.
9. Publicar una nueva imagen completa
La imagen es pequeña: podemos trabajar sobre sus 32768 bytes en memoria y publicar una copia completa en vez de escribir metadatos parciales sobre el archivo original. Es una estrategia para este tamaño, no una implementación de journal ni un esquema general de snapshots.
1. Leer y validar la version actual, si existe.
2. Aplicar la operacion en memoria y validar el candidato con su CRC.
3. Crear un temporal exclusivo en el mismo directorio, modo 0600.
4. Escribir la imagen completa y fsync(temporal).
5. Publicar:
mkfs: linkat a un nombre final que no exista y retirar el nombre temporal.
put/rm: renameat para reemplazar la ruta de la imagen.
6. fsync(directorio).
Un fallo despues del paso 5 no equivale a que siga visible la version anterior.linkat permite exigir creación sin sobrescribir la ruta final. renameat reemplaza el nombre atómicamente dentro del protocolo, y los lectores que ya tenían abierto el inodo anterior siguen observándolo.
El protocolo distingue visibilidad y durabilidad: fsync(2) explica por qué la sincronización del archivo no sustituye a la del directorio. Un error posterior a publicar informa que la nueva imagen ya es visible y que su durabilidad no fue confirmada.
Solo se admite un escritor. Dos procesos que lean la misma versión y luego publiquen cambios diferentes podrían perder una actualización. Tampoco se usa un hard link del archivo host como acceso compartido a un volumen mutable: al reemplazar una ruta, otros enlaces al inodo viejo conservan la versión vieja.
La publicación crea un archivo host nuevo, con propietario del proceso y modo 0600, y no preserva ACL o atributos especiales de una imagen previa. El laboratorio trabaja con imágenes propias en un directorio privado. Los límites del sistema de archivos host y del almacenamiento siguen formando parte de las garantías.
10. Comandos y estados de salida
| Comando | Resultado |
|---|---|
| mini48 mkfs imagen | Crear una imagen vacía; rechazar una ruta final existente. |
| mini48 ls imagen | Mostrar inodo, tamaño, bloques y nombre interno. |
| mini48 check imagen | Validar y resumir archivos, bloques e inodos libres. |
| mini48 put imagen nombre origen | Crear nombre con el contenido binario del archivo host origen. |
| mini48 get imagen nombre destino-nuevo | Extraer a un archivo host que no exista. |
| mini48 rm imagen nombre | Retirar el archivo interno y publicar otra versión. |
Se devuelve 0 al completar la operación, 1 ante errores de formato, capacidad, contenido o llamadas del sistema, y 2 ante uso o nombre interno inválido. El estado 1 no permite deducir por sí solo si ya se publicó: debe leerse el diagnóstico y consultar de nuevo cuando corresponda.
MFS48_FALLO=antes y MFS48_FALLO=despues son puntos de fallo didácticos de publicación. En uso normal la variable permanece sin definir. No provocan un corte de energía; producen un error controlado antes de publicar o después de hacerlo y antes del fsync del directorio.
11. Implementación completa en C
Guarda mini48.c o descarga el fuente completo. No requiere bibliotecas externas. El formato se construye con arreglos de bytes y funciones de codificación; las estructuras nativas de directorios del host nunca se copian a la imagen.
#define _POSIX_C_SOURCE 200809L
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
#include <stdint.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
enum { B = 512, NB = 64, NI = 16, ND = 16, DIRECTOS = 6,
TAM = B * NB, MAX_ARCHIVO = B * DIRECTOS };
static unsigned char imagen[TAM], contenido[MAX_ARCHIVO];
_Static_assert(CHAR_BIT == 8, "Se requieren bytes de ocho bits");
static int error(const char *s) { fprintf(stderr, "%s\n", s); return -1; }
static uint32_t u32(const unsigned char *p)
{
return (uint32_t)p[0] | (uint32_t)p[1] << 8 |
(uint32_t)p[2] << 16 | (uint32_t)p[3] << 24;
}
static void poner32(unsigned char *p, uint32_t n)
{
for (unsigned i = 0; i < 4; ++i) p[i] = (unsigned char)(n >> (8 * i));
}
static unsigned char *inodo(unsigned i) { return imagen + 2 * B + i * 32; }
static unsigned char *entrada(unsigned i) { return imagen + 3 * B + i * 32; }
static int ocupado(unsigned b) { return (imagen[B + b / 8] >> (b % 8)) & 1; }
static void marcar(unsigned b, int valor)
{
unsigned char mascara = (unsigned char)(1u << (b % 8));
if (valor) imagen[B + b / 8] |= mascara;
else imagen[B + b / 8] &= (unsigned char)~mascara;
}
static int ceros(const unsigned char *p, size_t n)
{
for (size_t i = 0; i < n; ++i) if (p[i]) return 0;
return 1;
}
static uint32_t crc(void)
{
uint32_t c = UINT32_MAX;
for (size_t i = 0; i < TAM; ++i) {
c ^= i >= 48 && i < 52 ? 0 : imagen[i];
for (unsigned j = 0; j < 8; ++j)
c = (c >> 1) ^ ((c & 1) ? UINT32_C(0xEDB88320) : 0);
}
return c ^ UINT32_MAX;
}
static int nombre_valido(const char *s)
{
size_t n = strlen(s);
if (!n || n > 27 || !strcmp(s, ".") || !strcmp(s, "..")) return 0;
for (size_t i = 0; i < n; ++i) {
unsigned char c = (unsigned char)s[i];
if (!((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') ||
(c >= '0' && c <= '9') || c == '.' || c == '_' || c == '-')) return 0;
}
return 1;
}
static int validar(void)
{
const uint32_t campos[] = {1, B, NB, NI, ND, 1, 2, 3, 4, DIRECTOS};
if (memcmp(imagen, "MINIFS48", 8)) return error("Firma invalida");
for (unsigned i = 0; i < 10; ++i)
if (u32(imagen + 8 + i * 4) != campos[i]) return error("Formato no admitido");
if (!ceros(imagen + 52, B - 52) || !ceros(imagen + B + NB / 8, B - NB / 8))
return error("Relleno reservado no nulo");
if (u32(imagen + 48) != crc()) return error("CRC32 incorrecto");
unsigned char referencias[NI] = {0}, dueno[NB] = {0};
for (unsigned b = 0; b < 4; ++b) dueno[b] = 1;
for (unsigned d = 0; d < ND; ++d) {
unsigned char *e = entrada(d);
uint32_t id = u32(e);
if (!id) {
if (!ceros(e, 32)) return error("Entrada vacia no canonica");
continue;
}
unsigned char *fin = memchr(e + 4, 0, 28);
if (id > NI || referencias[id - 1] || !fin)
return error("Referencia o nombre de directorio invalido");
size_t n = (size_t)(fin - (e + 4));
if (!nombre_valido((char *)e + 4) || !ceros(fin, 28 - n))
return error("Nombre fuera del contrato");
for (unsigned anterior = 0; anterior < d; ++anterior)
if (u32(entrada(anterior)) && !strcmp((char *)entrada(anterior) + 4, (char *)e + 4))
return error("Nombre duplicado");
referencias[id - 1] = 1;
unsigned char *ino = inodo(id - 1);
uint32_t tamano = u32(ino + 4);
if (u32(ino) != 1 || tamano > MAX_ARCHIVO) return error("Inodo invalido");
unsigned bloques = (tamano + B - 1) / B;
for (unsigned j = 0; j < DIRECTOS; ++j) {
uint32_t b = u32(ino + 8 + j * 4);
if (j >= bloques) {
if (b) return error("Puntero sobrante");
} else {
if (b < 4 || b >= NB || dueno[b]) return error("Bloque invalido o compartido");
dueno[b] = 1;
unsigned resto = tamano % B;
if (j + 1 == bloques && resto && !ceros(imagen + b * B + resto, B - resto))
return error("Cola de archivo no canonica");
}
}
}
for (unsigned i = 0; i < NI; ++i)
if (!referencias[i] && !ceros(inodo(i), 32)) return error("Inodo huerfano");
for (unsigned b = 0; b < NB; ++b) {
if (ocupado(b) != dueno[b]) return error("Bitmap no coincide con referencias");
if (b >= 4 && !dueno[b] && !ceros(imagen + b * B, B))
return error("Bloque libre no canonico");
}
return 0;
}
static int transferir(int fd, unsigned char *p, size_t n, int escribir)
{
while (n) {
ssize_t r = escribir ? write(fd, p, n) : read(fd, p, n);
if (r > 0 && (size_t)r <= n) { p += r; n -= (size_t)r; }
else if (r == -1 && errno == EINTR) continue;
else { if (r >= 0) errno = EIO; return -1; }
}
return 0;
}
static int directorio_host(const char *ruta, char nombre[256])
{
char padre[4096];
size_t n = strlen(ruta);
if (!n || n >= sizeof padre) return error("Ruta demasiado larga o vacia");
memcpy(padre, ruta, n + 1);
char *barra = strrchr(padre, '/');
const char *ultimo = barra ? barra + 1 : padre;
size_t longitud = strlen(ultimo);
if (!longitud || longitud > 255 || !strcmp(ultimo, ".") || !strcmp(ultimo, ".."))
return error("Nombre host invalido");
memcpy(nombre, ultimo, longitud + 1);
if (!barra) strcpy(padre, ".");
else if (barra == padre) padre[1] = 0;
else *barra = 0;
int dir = open(padre, O_RDONLY | O_DIRECTORY | O_CLOEXEC);
if (dir == -1) perror("open directorio");
return dir;
}
static int cargar(int dir, const char *nombre)
{
int fd = openat(dir, nombre, O_RDONLY | O_CLOEXEC | O_NOFOLLOW | O_NONBLOCK);
if (fd == -1) { perror("open imagen"); return -1; }
struct stat st;
int r = 0;
if (fstat(fd, &st) || !S_ISREG(st.st_mode) || st.st_size != TAM)
r = error("La imagen debe ser regular y medir 32768 bytes");
if (!r && transferir(fd, imagen, TAM, 0)) { perror("read imagen"); r = -1; }
if (close(fd)) r = -1;
return r ? -1 : validar();
}
static int publicar(int dir, const char *nombre, int nueva)
{
char temporal[80];
int fd = -1, propio = 0, visible = 0, r = -1;
for (unsigned i = 0; i < 100; ++i) {
snprintf(temporal, sizeof temporal, ".mfs48.%ld.%u", (long)getpid(), i);
if (!strcmp(temporal, nombre)) continue;
fd = openat(dir, temporal, O_WRONLY | O_CREAT | O_EXCL | O_CLOEXEC | O_NOFOLLOW, 0600);
if (fd != -1) { propio = 1; break; }
if (errno != EEXIST) break;
}
if (fd == -1) { perror("crear temporal"); return -1; }
if (fchmod(fd, 0600) || transferir(fd, imagen, TAM, 1) || fsync(fd)) goto fin;
if (close(fd)) { fd = -1; goto fin; }
fd = -1;
const char *fallo = getenv("MFS48_FALLO");
if (fallo && !strcmp(fallo, "antes")) { errno = EIO; goto fin; }
if (nueva) {
if (linkat(dir, temporal, dir, nombre, 0)) goto fin;
visible = 1;
if (unlinkat(dir, temporal, 0)) goto fin;
propio = 0;
} else {
if (renameat(dir, temporal, dir, nombre)) goto fin;
visible = 1; propio = 0;
}
if (fallo && !strcmp(fallo, "despues")) { errno = EIO; goto fin; }
if (fsync(dir)) goto fin;
r = 0;
fin:
{
int guardado = errno;
if (fd != -1) close(fd);
if (propio) unlinkat(dir, temporal, 0);
if (r) {
if (visible) fprintf(stderr, "La nueva imagen ya es visible; durabilidad no confirmada\n");
errno = guardado; perror("publicar imagen");
}
}
return r;
}
static int buscar(const char *nombre)
{
for (unsigned d = 0; d < ND; ++d)
if (u32(entrada(d)) && !strcmp((char *)entrada(d) + 4, nombre)) return (int)d;
return -1;
}
static int importar(const char *nombre, const char *origen)
{
if (buscar(nombre) != -1) return error("El nombre interno ya existe");
int fd = open(origen, O_RDONLY | O_CLOEXEC | O_NOFOLLOW | O_NONBLOCK);
if (fd == -1) { perror("open origen"); return -1; }
struct stat st;
if (fstat(fd, &st) || !S_ISREG(st.st_mode) || st.st_size < 0 || st.st_size > MAX_ARCHIVO) {
close(fd); return error("Origen regular requerido, hasta 3072 bytes");
}
size_t tamano = (size_t)st.st_size;
int r = transferir(fd, contenido, tamano, 0);
unsigned char extra;
ssize_t mas;
do { mas = read(fd, &extra, 1); } while (mas == -1 && errno == EINTR);
if (mas != 0) r = -1;
if (close(fd)) r = -1;
if (r) return error("Origen truncado, cambiado o ilegible");
int d = -1, id = -1;
for (unsigned i = 0; i < ND; ++i) if (!u32(entrada(i))) { d = (int)i; break; }
for (unsigned i = 0; i < NI; ++i) if (!u32(inodo(i))) { id = (int)i; break; }
if (d < 0 || id < 0) return error("Sin entradas o inodos libres");
unsigned necesarios = ((unsigned)tamano + B - 1) / B, elegidos[DIRECTOS], usados = 0;
for (unsigned b = 4; b < NB && usados < necesarios; ++b)
if (!ocupado(b)) elegidos[usados++] = b;
if (usados != necesarios) return error("Sin bloques de datos suficientes");
unsigned char *ino = inodo((unsigned)id), *e = entrada((unsigned)d);
poner32(ino, 1); poner32(ino + 4, (uint32_t)tamano);
size_t copiados = 0;
for (unsigned j = 0; j < necesarios; ++j) {
unsigned b = elegidos[j];
size_t n = tamano - copiados;
if (n > B) n = B;
memset(imagen + b * B, 0, B);
memcpy(imagen + b * B, contenido + copiados, n);
copiados += n; marcar(b, 1); poner32(ino + 8 + j * 4, b);
}
poner32(e, (uint32_t)id + 1);
memcpy(e + 4, nombre, strlen(nombre) + 1);
return 0;
}
static int exportar(int d, const char *destino)
{
unsigned char *ino = inodo(u32(entrada((unsigned)d)) - 1);
int fd = open(destino, O_WRONLY | O_CREAT | O_EXCL | O_CLOEXEC | O_NOFOLLOW, 0600);
if (fd == -1) { perror("crear destino nuevo"); return -1; }
unsigned restantes = u32(ino + 4), j = 0;
int r = 0;
while (restantes) {
unsigned n = restantes > B ? B : restantes;
unsigned b = u32(ino + 8 + j++ * 4);
if (transferir(fd, imagen + b * B, n, 1)) { r = -1; break; }
restantes -= n;
}
if (!r && fsync(fd)) r = -1;
if (close(fd)) r = -1;
if (r) { unlink(destino); return error("Error al exportar; se retiro la salida parcial"); }
return 0;
}
static void borrar(int d)
{
unsigned char *ino = inodo(u32(entrada((unsigned)d)) - 1);
unsigned bloques = (u32(ino + 4) + B - 1) / B;
for (unsigned j = 0; j < bloques; ++j) {
unsigned b = u32(ino + 8 + j * 4);
memset(imagen + b * B, 0, B); marcar(b, 0);
}
memset(ino, 0, 32); memset(entrada((unsigned)d), 0, 32);
}
int main(int argc, char **argv)
{
if (argc < 3) goto uso;
int mk = !strcmp(argv[1], "mkfs"), ls = !strcmp(argv[1], "ls");
int chk = !strcmp(argv[1], "check"), put = !strcmp(argv[1], "put");
int get = !strcmp(argv[1], "get"), rm = !strcmp(argv[1], "rm");
if ((!mk && !ls && !chk && !put && !get && !rm) ||
((mk || ls || chk) && argc != 3) || ((put || get) && argc != 5) ||
(rm && argc != 4)) goto uso;
if ((put || get || rm) && !nombre_valido(argv[3])) goto uso;
char nombre[256];
int dir = directorio_host(argv[2], nombre);
if (dir == -1) return 1;
int r = 0;
if (mk) {
const uint32_t campos[] = {1, B, NB, NI, ND, 1, 2, 3, 4, DIRECTOS};
memset(imagen, 0, sizeof imagen); memcpy(imagen, "MINIFS48", 8);
for (unsigned i = 0; i < 10; ++i) poner32(imagen + 8 + i * 4, campos[i]);
for (unsigned b = 0; b < 4; ++b) marcar(b, 1);
} else if (cargar(dir, nombre)) { r = -1; goto fin; }
if (put) r = importar(argv[3], argv[4]);
if (get || rm) {
int d = buscar(argv[3]);
if (d == -1) r = error("Nombre interno inexistente");
else if (get) r = exportar(d, argv[4]);
else borrar(d);
}
if (!r && (mk || put || rm)) {
poner32(imagen + 48, crc());
if (validar()) r = -1;
else r = publicar(dir, nombre, mk);
}
if (!r && ls) {
puts("INODO BYTES BLOQUES NOMBRE");
for (unsigned d = 0; d < ND; ++d) if (u32(entrada(d))) {
uint32_t id = u32(entrada(d)), n = u32(inodo(id - 1) + 4);
printf("%u %u %u %s\n", id, n, (n + B - 1) / B, (char *)entrada(d) + 4);
}
}
if (!r && chk) {
unsigned archivos = 0, libres = 0;
for (unsigned d = 0; d < ND; ++d) archivos += u32(entrada(d)) != 0;
for (unsigned b = 4; b < NB; ++b) libres += !ocupado(b);
printf("OK archivos=%u bloques_libres=%u inodos_libres=%u\n", archivos, libres, NI - archivos);
}
fin:
if (close(dir)) r = -1;
if (fflush(stdout) == EOF) r = -1;
return r ? 1 : 0;
uso:
fprintf(stderr, "Uso: %s mkfs|ls|check imagen | put imagen nombre origen | get imagen nombre destino-nuevo | rm imagen nombre\n", argv[0]);
return 2;
}
El tamaño fijo mantiene acotados los buffers y los cálculos de asignación. Los punteros de una imagen se validan antes de usarlos para acceder a datos. El lector rechaza objetos que no sean archivos regulares de la longitud exacta y el exportador usa creación exclusiva.
El temporal se crea con O_EXCL en el directorio ya abierto. Solo se elimina su nombre si esta ejecución lo creó. Un error después de reemplazar la ruta no intenta deshacer la operación volviendo a instalar una versión que podría estar desactualizada.
12. Seguir un archivo y reutilizar un hueco
Imagina tres archivos A, B y C de 512 bytes. First fit les asigna los bloques 4, 5 y 6. Tras borrar B, el bloque 5 vuelve a estar libre. Un archivo D de 1024 bytes usa 5 y 7, los dos primeros libres en ese momento.
| Paso | Bloques ocupados de datos | Consecuencia |
|---|---|---|
| Crear A, B y C. | 4=A, 5=B, 6=C. | Tres inodos y entradas ocupados. |
| Borrar B. | 4=A, 6=C. | Se libera su entrada, su inodo y el bloque 5. |
| Importar D de 1024 bytes. | 4=A, 5=D, 6=C, 7=D. | D tiene dos punteros, en el orden 5,7. |
| Leer byte lógico 700 de D. | Segundo puntero, bloque 7. | 700/512=1; resto=188; offset de imagen=3584+188=3772. |
La posición física de D no es un intervalo contiguo de 1024 bytes. get reconstruye el orden mediante los punteros. El inodo liberado de B puede reutilizarse para D, pero la identidad de B no se conserva.
Al borrar D, la versión nueva deja a cero ambos bloques y los retira del mapa. No se mueve C ni se compacta la imagen. La fragmentación de huecos no impide usar bloques separados dentro del límite de punteros.
13. Laboratorio de contenido y capacidad
En Bash de Linux crea un directorio nuevo y guarda mini48.c y verificar-mini48.py. El proyecto requiere compilador C y Python 3; no monta nada ni necesita privilegios administrativos.
mkdir laboratorio48
cd laboratorio48
# Guardar aqui mini48.c y verificar-mini48.py.
cc -std=c11 -O2 -Wall -Wextra -Wpedantic mini48.c -o mini48
./mini48 mkfs volumen.img
./mini48 check volumen.img
python3 - <<'PY'
from pathlib import Path
for nombre, datos in [('nota.txt', b'Hola desde MINI48\n'),
('datos.bin', bytes(range(256)) * 4), ('vacio.bin', b'')]:
with Path(nombre).open('xb') as f:
f.write(datos)
PY
./mini48 put volumen.img nota nota.txt
./mini48 put volumen.img datos datos.bin
./mini48 put volumen.img vacio vacio.bin
./mini48 ls volumen.img
./mini48 get volumen.img datos extraido.bin
cmp datos.bin extraido.bin
./mini48 rm volumen.img nota
./mini48 check volumen.imgLa imagen vacía informa 60 bloques e inodos 16 libres. Tras las tres importaciones hay tres archivos y tres bloques de datos ocupados: uno para nota y dos para datos; vacio no consume datos. Después de borrar nota quedan dos archivos, 58 bloques y 14 inodos libres.
Repetir get sobre extraido.bin debe fallar sin sobrescribirlo. Repetir mkfs sobre volumen.img también falla sin formatearlo de nuevo. Para otro ensayo se usa una ruta nueva, no se modifica automáticamente una imagen existente.
Mirar metadatos sin confundirlos con un formato real
dd if=volumen.img bs=512 count=1 status=none | od -Ax -tx1
dd if=volumen.img bs=512 skip=1 count=1 status=none | od -Ax -tx1
dd if=volumen.img bs=512 skip=3 count=1 status=none | od -Ax -tx1Los campos corresponden exclusivamente a MINIFS48. No se entrega esta imagen a mkfs.ext4 ni se intenta montarla como ext4: su estructura y sus reglas son las que acabamos de definir.
14. Verificador independiente y carga reproducible
Guarda verificar-mini48.py o descarga el verificador. Crea sus imágenes en un directorio temporal propio. Decodifica el formato con struct, calcula CRC con zlib, reconstruye el contenido y mantiene un modelo de nombres y bytes independiente del programa C.
from pathlib import Path
from tempfile import TemporaryDirectory
import os
import random
import re
import struct
import subprocess
import sys
import zlib
def main():
if len(sys.argv) != 2:
raise SystemExit('Uso: python3 verificar-mini48.py ./mini48')
programa = str(Path(sys.argv[1]).resolve())
entorno = dict(os.environ)
entorno.pop('MFS48_FALLO', None)
with TemporaryDirectory(prefix='mini48-') as carpeta:
base = Path(carpeta)
def ejecutar(*args, estado=0, fallo=None):
env = dict(entorno)
if fallo is not None:
env['MFS48_FALLO'] = fallo
r = subprocess.run([programa, *map(str, args)], cwd=base, env=env,
text=True, capture_output=True, timeout=10)
assert r.returncode == estado, (args, r.returncode, r.stderr)
return r
def fuente(nombre, datos):
(base / nombre).write_bytes(datos)
return nombre
def comprobar(nombre, esperado):
raw = (base / nombre).read_bytes()
assert len(raw) == 32768 and raw[:8] == b'MINIFS48'
assert struct.unpack_from('<10I', raw, 8) == (1, 512, 64, 16, 16, 1, 2, 3, 4, 6)
copia = bytearray(raw)
copia[48:52] = bytes(4)
assert zlib.crc32(copia) == struct.unpack_from('<I', raw, 48)[0]
assert raw[52:512] == bytes(460)
assert raw[520:1024] == bytes(504)
referencias, duenos, encontrados = set(), set(range(4)), {}
for d in range(16):
e = raw[1536 + 32 * d:1568 + 32 * d]
id_ = struct.unpack_from('<I', e)[0]
if id_ == 0:
assert e == bytes(32)
continue
assert 1 <= id_ <= 16 and id_ not in referencias
referencias.add(id_)
nombre_bytes, _, cola = e[4:].partition(b'\0')
assert b'\0' in e[4:] and not any(cola)
nombre_archivo = nombre_bytes.decode('ascii')
assert re.fullmatch(r'[A-Za-z0-9._-]{1,27}', nombre_archivo)
assert nombre_archivo not in ('.', '..')
assert nombre_archivo not in encontrados
flags, longitud, *punteros = struct.unpack_from('<8I', raw, 1024 + (id_ - 1) * 32)
assert flags == 1 and longitud <= 3072
n = (longitud + 511) // 512
assert all(p == 0 for p in punteros[n:])
contenido = bytearray()
for p in punteros[:n]:
assert 4 <= p < 64 and p not in duenos
duenos.add(p)
contenido.extend(raw[p * 512:(p + 1) * 512])
assert not any(contenido[longitud:])
encontrados[nombre_archivo] = bytes(contenido[:longitud])
for i in range(16):
if i + 1 not in referencias:
assert raw[1024 + i * 32:1056 + i * 32] == bytes(32)
bitmap = int.from_bytes(raw[512:520], 'little')
assert {i for i in range(64) if bitmap & (1 << i)} == duenos
for b in set(range(4, 64)) - duenos:
assert raw[b * 512:(b + 1) * 512] == bytes(512)
assert encontrados == esperado
r = ejecutar('check', nombre)
assert f'archivos={len(esperado)} ' in r.stdout
assert f'bloques_libres={64 - len(duenos)} ' in r.stdout
listado = ejecutar('ls', nombre).stdout.splitlines()
assert listado[0] == 'INODO BYTES BLOQUES NOMBRE'
observados = {}
for linea in listado[1:]:
id_, longitud, bloques, archivo = linea.split()
assert archivo not in observados and 1 <= int(id_) <= 16
observados[archivo] = (int(longitud), int(bloques))
assert observados == {n: (len(b), (len(b) + 511) // 512) for n, b in esperado.items()}
assert (base / nombre).read_bytes() == raw
return raw
def sin_cambios(imagen, *args, estado=1):
antes = (base / imagen).read_bytes()
ejecutar(*args, estado=estado)
assert (base / imagen).read_bytes() == antes
modelo = {}
ejecutar('mkfs', 'principal.img')
comprobar('principal.img', modelo)
for n in (0, 1, 511, 512, 513, 3072):
nombre = f'f{n}'
datos = bytes((i * 17 + n) % 256 for i in range(n))
ejecutar('put', 'principal.img', nombre, fuente('origen', datos))
modelo[nombre] = datos
comprobar('principal.img', modelo)
destino = f'salida-{n}'
ejecutar('get', 'principal.img', nombre, destino)
assert (base / destino).read_bytes() == datos
sin_cambios('principal.img', 'get', 'principal.img', nombre, destino)
sin_cambios('principal.img', 'mkfs', 'principal.img')
sin_cambios('principal.img', 'put', 'principal.img', 'f1', 'origen')
sin_cambios('principal.img', 'put', 'principal.img', '../x', 'origen', estado=2)
sin_cambios('principal.img', 'put', 'principal.img', 'grande', fuente('grande', bytes(3073)))
(base / 'simbolico').symlink_to('origen')
sin_cambios('principal.img', 'put', 'principal.img', 'sim', 'simbolico')
sin_cambios('principal.img', 'rm', 'principal.img', 'ausente')
for i in range(10):
nombre = f'vacio{i}'
ejecutar('put', 'principal.img', nombre, fuente('vacio', b''))
modelo[nombre] = b''
comprobar('principal.img', modelo)
sin_cambios('principal.img', 'put', 'principal.img', 'extra', 'vacio')
ejecutar('mkfs', 'fragmentada.img')
frag = {}
for nombre in ('A', 'B', 'C'):
datos = nombre.encode() * 512
ejecutar('put', 'fragmentada.img', nombre, fuente('origen', datos))
frag[nombre] = datos
ejecutar('rm', 'fragmentada.img', 'B')
del frag['B']
frag['D'] = b'D' * 1024
ejecutar('put', 'fragmentada.img', 'D', fuente('origen', frag['D']))
raw = comprobar('fragmentada.img', frag)
# El inodo liberado de B se reutiliza para D: bloques 5 y 7.
assert struct.unpack_from('<2I', raw, 1024 + 32 + 8) == (5, 7)
ejecutar('get', 'fragmentada.img', 'D', 'D-extraido')
assert (base / 'D-extraido').read_bytes() == frag['D']
ejecutar('mkfs', 'llena.img')
llena = {}
for i in range(10):
nombre, datos = f'b{i}', bytes([i]) * 3072
ejecutar('put', 'llena.img', nombre, fuente('origen', datos))
llena[nombre] = datos
comprobar('llena.img', llena)
sin_cambios('llena.img', 'put', 'llena.img', 'uno', fuente('uno', b'X'))
ejecutar('put', 'llena.img', 'sin-datos', 'vacio')
llena['sin-datos'] = b''
comprobar('llena.img', llena)
ejecutar('mkfs', 'transaccion.img')
ejecutar('put', 'transaccion.img', 'base', fuente('origen', b'base'))
antes = (base / 'transaccion.img').read_bytes()
fuente('nuevo', b'nuevo')
ejecutar('put', 'transaccion.img', 'nuevo', 'nuevo', estado=1, fallo='antes')
assert (base / 'transaccion.img').read_bytes() == antes
r = ejecutar('put', 'transaccion.img', 'nuevo', 'nuevo', estado=1, fallo='despues')
assert 'ya es visible' in r.stderr
comprobar('transaccion.img', {'base': b'base', 'nuevo': b'nuevo'})
assert not list(base.glob('.mfs48.*'))
for caso in ('crc', 'bitmap', 'huerfano', 'puntero', 'truncada'):
malo = bytearray(raw)
if caso == 'crc': malo[4096] ^= 1
if caso == 'bitmap': malo[512] ^= 1
if caso == 'huerfano': malo[1536:1568] = bytes(32)
if caso == 'puntero': struct.pack_into('<I', malo, 1024 + 32 + 8, 4)
if caso == 'truncada': malo.pop()
if caso not in ('crc', 'truncada'):
malo[48:52] = bytes(4)
struct.pack_into('<I', malo, 48, zlib.crc32(malo))
ruta = f'mala-{caso}.img'
(base / ruta).write_bytes(malo)
sin_cambios(ruta, 'check', ruta)
sin_cambios(ruta, 'rm', ruta, 'A')
rng = random.Random(48)
ejecutar('mkfs', 'azar.img')
modelo = {}
for paso in range(80):
nombre = f'n{rng.randrange(20)}'
if rng.randrange(3) == 0:
ejecutar('rm', 'azar.img', nombre, estado=0 if nombre in modelo else 1)
modelo.pop(nombre, None)
else:
n = rng.choice((0, 1, 511, 512, 513, 1024, 3072))
datos = bytes(rng.randrange(256) for _ in range(n))
ocupados = sum((len(b) + 511) // 512 for b in modelo.values())
cabe = nombre not in modelo and len(modelo) < 16 and ocupados + (n + 511) // 512 <= 60
antes = (base / 'azar.img').read_bytes()
ejecutar('put', 'azar.img', nombre, fuente('azar-fuente', datos), estado=0 if cabe else 1)
if cabe: modelo[nombre] = datos
else: assert (base / 'azar.img').read_bytes() == antes
comprobar('azar.img', modelo)
print('OK: contenido, asignacion, agotamiento, corrupcion y fallos de publicacion')
print('80 operaciones reproducibles contrastadas con un modelo independiente')
if __name__ == '__main__':
main()
python3 verificar-mini48.py ./mini48Se prueban longitudes 0, 1, 511, 512, 513 y 3072, archivo demasiado grande, duplicados, extracción exclusiva, límites de entradas y de bloques, reutilización no contigua y dos puntos de fallo. Las imágenes corruptas incluyen CRC incorrecto y también inconsistencias con CRC recalculado.
La secuencia de 80 operaciones usa una semilla fija y revisa la imagen contra un diccionario de contenidos después de cada paso. Eso no prueba todas las ejecuciones posibles, pero contrasta comportamiento y formato en vez de limitarse a que los comandos retornen cero.
15. Fallos antes y después de publicar
| Punto del ensayo | Resultado del comando | Qué verifica la prueba |
|---|---|---|
| Antes de linkat/renameat, con temporal ya sincronizado. | Error 1; imagen anterior sigue visible. | La ruta conserva exactamente los bytes previos y se retira el temporal propio. |
| Después de publicar y antes de fsync del directorio. | Error 1 y diagnóstico de nueva imagen visible. | La ruta contiene la versión nueva completa y válida; durabilidad no confirmada. |
| Después de fsync del directorio. | Éxito de publicación si las llamadas completaron. | Archivo y entrada se sincronizaron según el contrato del host. |
Las pruebas no apagan la máquina, no simulan todos los fallos posibles de almacenamiento y no demuestran qué versión reaparecería después de un corte real. Verifican las decisiones del programa y su diagnóstico en puntos elegidos.
Después de un error posterior a publicar, no se debe asumir que repetir put sea una creación nueva: el nombre puede existir ya. Primero se consulta la imagen y su contenido. El mismo razonamiento aplica a rm: un error final no demuestra que el archivo siga presente.
Un cierre abrupto puede dejar un temporal con nombre .mfs48.*; no forma parte del directorio interno ni demuestra por sí solo que la ruta publicada esté dañada. Las limpiezas controladas del ejemplo solo retiran el temporal que crearon, y el programa no recorre ni borra restos ajenos.
16. Simuladores de asignación y publicación
Asignar por primera posición libre
Modelo local de tamaños, nombres y punteros, sin almacenar contenido ni escribir una imagen real. Comienza vacío y aplica los mismos límites de 16 archivos, 60 bloques y seis punteros. Puedes crear A, B y C de 512 bytes, borrar B y crear D de 1024 para ver el hueco reutilizado.
Directorio, inodos y bitmap
| Nombre | Inodo | Bytes | Punteros de datos | Sobrante asignado |
|---|
Separar candidato, visibilidad y sincronización
Este modelo representa una modificación de versión 1 a versión 2. Avanza por las etapas y provoca un error controlado antes o después de publicar. Los candidatos se suponen estructuralmente válidos; no es una simulación de cortes de energía ni del hardware.
Publicar una imagen completa
| Etapa | Estado |
|---|
17. Diagnóstico y resumen
| Observación | Qué revisar |
|---|---|
| Hay bloques libres, pero no puede crearse otro nombre. | Entradas e inodos: tienen límites independientes del espacio de datos. |
| Un archivo de 3073 bytes falla aunque sobre espacio. | Supera los seis punteros y el máximo por archivo. |
| El contenido exportado mezcla huecos de otros archivos. | Recorrer cada puntero en orden lógico; no asumir contigüidad. |
| CRC correcto y check rechaza la imagen. | La geometría, referencias, mapa y relleno requieren coherencia además del checksum. |
| Un archivo vacío desaparece al interpretar inodos. | Estado y referencia lo distinguen de un inodo libre; longitud cero no significa libre. |
| put informa error, pero el nombre ya existe. | Puede haber ocurrido un error después de publicar; consultar el diagnóstico y el estado visible. |
| Dos escritores pierden cambios. | El contrato es de un escritor; el reemplazo atómico no implementa exclusión mutua. |
- Un formato propio necesita unidades, posiciones y representación explícitas.
- El directorio relaciona nombres con inodos y los inodos relacionan el contenido lógico con bloques.
- El mapa se contrasta con propietarios reconstruidos, no se toma como una prueba independiente de validez.
- Archivos vacíos, archivos pequeños y límites de capacidad requieren casos distintos.
- Crear y borrar actualiza relaciones coherentes en una imagen candidata.
- La publicación completa evita exponer una edición parcial de la ruta bajo el contrato del proyecto.
- Visibilidad, sincronización del archivo y sincronización del directorio son etapas diferentes.
- Las pruebas contrastan contenido, estructura, rechazos y resultados después de fallos controlados.
18. Preguntas de repaso y práctica
1. ¿Cuánto mide la imagen del proyecto?
32768 bytes: 64 bloques de 512.
2. ¿Cuántos bloques quedan para datos?
60, desde el número 4 hasta el 63.
3. ¿Dónde se guarda el nombre?
En la entrada de directorio, separado del inodo.
4. ¿Qué significa identificador cero en el directorio?
Entrada vacía. Los identificadores ocupados son 1..16.
5. ¿Cuántos bloques necesita un archivo de 513 bytes?
Dos; el segundo contiene un byte válido y 511 de relleno cero.
6. ¿Qué distingue un archivo vacío de un inodo libre?
El estado ocupado del inodo y su entrada de directorio, aunque longitud y punteros sean cero.
7. ¿Puede un archivo usar los bloques 5 y 7?
Sí. Sus punteros preservan el orden lógico sin exigir contigüidad.
8. ¿Dónde está el byte 700 si los punteros son 5 y 7?
En el segundo bloque, offset 188: 7×512+188=3772 dentro de la imagen.
9. ¿Por qué no crear un archivo de 3073 bytes?
Necesitaría siete bloques y el inodo solo tiene seis punteros directos.
10. ¿Tener bloques libres garantiza otra creación?
No. También deben quedar entrada e inodo libres.
11. ¿Qué compara el validador con el bitmap?
Los bloques reservados y los propietarios reconstruidos desde directorio e inodos.
12. ¿CRC correcto significa relaciones correctas?
No. Hay que validar rangos, unicidad, referencias y representación canónica.
13. ¿Por qué el temporal se crea en el mismo directorio?
Para publicar en el mismo sistema de archivos y sincronizar la entrada de ese directorio.
14. ¿Cómo evita mkfs reemplazar una ruta existente?
Publica mediante linkat a un nombre que debe estar libre, sin sobrescribirlo.
15. ¿Un error después de rename demuestra que no cambió nada?
No. La nueva imagen puede estar visible aunque no se haya confirmado la sincronización del directorio.
16. ¿El reemplazo atómico coordina dos escritores?
No. Pueden calcular desde una versión vieja y perder una actualización; el contrato admite un solo escritor.
17. ¿get sobrescribe archivos del host?
No. Usa creación exclusiva y rechaza una ruta existente.
18. ¿rm es borrado seguro del almacenamiento?
No. Pone a cero la versión nueva del formato, sin garantizar la eliminación física de versiones previas del host.
19. ¿Los puntos de fallo simulan un apagado?
No. Producen errores controlados en etapas elegidas y comprueban estado visible y diagnóstico.
20. ¿Esta imagen puede montarse como ext4?
No. Es un formato didáctico propio administrado por mini48.
Para practicar
- Relaciona cada región de la imagen con su offset y su función.
- Calcula bloques y sobrante para tamaños 0,1,511,512,513 y 3072.
- Reproduce la secuencia A,B,C, borrar B y crear D; contrasta sus punteros.
- Importa bytes binarios, exporta a una ruta nueva y compara el contenido exacto.
- Agota entradas con archivos vacíos y explica por qué aún hay espacio de datos.
- Agota bloques con diez archivos máximos y crea después un archivo vacío.
- Recalcula el CRC de una imagen con bitmap incorrecto y comprueba que la validación estructural la rechaza.
- Ejecuta el verificador y explica cómo separa su modelo del algoritmo C.
- Observa el fallo anterior a publicar y contrasta la imagen con los bytes previos.
- Observa el fallo posterior a publicar y explica qué consultar antes de repetir la operación.
- Diseña una extensión con generaciones de inodo o subdirectorios y enumera qué invariantes deberían cambiar.
- Explica por qué una versión con escritura in situ necesitaría otro protocolo para manejar actualizaciones interrumpidas.
En el tema 49 construiremos un respaldo incremental con enlaces duros: versiones que comparten archivos sin confundir compartir un inodo con modificar de forma independiente su contenido.