40 · Implementación de un sistema de ficheros

Apuntes propios sobre el capítulo 40 de OSTEP (File System Implementation). Fuente: https://ostep.org

40.1 El método: estructuras + rutas de acceso

Para entender cualquier FS, dos preguntas: ¿qué estructuras hay en disco? y ¿qué pasa (qué se lee/escribe) en cada operación (open, read, write…)? El capítulo construye un FS mínimo (“VSFS”) al estilo del FS original de Unix.

40.2 Layout en disco

Partición de N bloques (bloque = 4 KiB):

| S | ib | db | I I I I I | D D D D D D D D ... |
 superbloque  bitmaps      tabla de inodes    bloques de datos
  • Superbloque: metadatos del FS (tamaños, dónde empieza cada región, magic number). Se lee al montar.
  • Bitmaps de inodes y de datos: qué está libre/ocupado.
  • Tabla de inodes: array de inodes; el inode number es el índice (por eso localizar un inode es aritmética simple).
  • Bloques de datos: la mayoría del disco.

40.3 El inode

La estructura por-fichero: tipo, tamaño, permisos, dueño, tiempos, contador de enlaces… y sobre todo dónde están los datos:

  • Punteros directos (~12): bloques de datos directamente.
  • Puntero indirecto: apunta a un bloque lleno de punteros (~1024 más).
  • Doble/triple indirecto: árbol desbalanceado a favor de los ficheros pequeños — decisión respaldada por la realidad medida: la mayoría de los ficheros son pequeños (~2 KiB de mediana; la tabla de “verdades sobre ficheros” de Agrawal et al. que cita el capítulo).
  • Alternativa: extents (rango contiguo: inicio+longitud) — más compacto, menos flexible; lo usan ext4, XFS, NTFS.

Los directorios: simplemente ficheros cuyo contenido son entradas (inode, longitud, nombre); borrar deja huecos (por eso las entradas llevan longitud de registro). FS reales usan estructuras mejores (árboles B en XFS/ext4-htree) para dirs enormes.

Gestión de libres: los bitmaps al asignar/liberar; con heurísticas (buscar secuencias contiguas, pre-asignación) para la contigüidad.

40.4 Rutas de acceso — el corazón del capítulo

Leer /foo/bar: cada nivel de la ruta cuesta lecturas — inode de / → datos de / (buscar “foo”) → inode de foo → datos de foo (buscar “bar”) → inode de bar → ya con permiso comprobado, read(): inode (localizar bloque) → bloque de datos → actualizar inode (atime). La longitud de la ruta multiplica las E/S.

Crear y escribir es peor: create toca bitmap de inodes (leer+escribir), datos y del directorio, inode nuevo y del directorio…; cada write() que asigna bloque: 5 E/S (bitmap ×2, inode ×2, dato). Una escritura “sencilla” son decenas de E/S. Conclusión: un FS sin cachés sería inutilizable.

40.5 Caching y buffering

  • Lecturas: la page cache unificada (memoria dinámica compartida con la MV, no particiones fijas como antaño) absorbe la mayoría — el tráfico de rutas populares (inodes de /, /usr…) se sirve de RAM.
  • Escrituras: el write buffering las retrasa (5–30 s): agrupa (el bitmap tocado por 2 ficheros se escribe una vez), planifica mejor, y a veces evita E/S (fichero temporal creado y borrado antes del flush: cero escrituras). El precio: un crash pierde lo no volcado → las aplicaciones que no pueden permitírselo usan fsync() o E/S directa (bases de datos). El eterno compromiso durabilidad/rendimiento.

Ampliación (no está en OSTEP)

  • Mapa a FS reales: ext4 = este diseño + extents + grupos de bloques (cap. 41) + journal (cap. 42) + htree; XFS = extents + B+trees por todas partes; Btrfs/ZFS = copy-on-write total (parientes del cap. 43).
  • Explora en vivo: dumpe2fs /dev/sdX (superbloque y grupos), debugfs (inodes y entradas de dir a mano), stat fichero (inode, bloques), df -i (inodes agotables: sí, puedes quedarte sin inodes con disco libre).
  • El coste de las rutas largas es real hoy: el kernel lo amortigua con la dcache (caché de dentry nombre→inode), una de las estructuras más calientes de Linux.

Referencias

  • OSTEP cap. 40.
  • Agrawal et al., A Five-Year Study of File-System Metadata, FAST 2007.
  • Bach, The Design of the UNIX Operating System — el FS clásico de Unix con todo detalle.
  • Documentation/filesystems/ext4/ del kernel.