¿Cómo funcionan los sistemas basados en inodos?

Después de ver como funcionan de forma genérica los sistemas FAT, saltamos a los sistemas de inodos. Estos se han usado tradicionalmente en sistemas UNIX (UFS, ext2), así que tradicionalmente ha existido una cierta rivalidad  en las redes entre FAT e inodos similar a la de Windows/Linux. Lo cierto es que a nivel técnico cada uno tiene fortalezas y debilidades.

Partición

Tomando la base de FAT, una partición de un sistema basado en inodos también contiene un sector de arranque y un superbloque con metadatos. También es necesario un bloque dedicado al directorio raíz presente en el disco. Además es necesario espacio para almacenar todos los inodos y un mapa de bits de espacio libre que en FAT no hacía falta, ya que la propia tabla nos indicaba que bloques del disco estaban libres.

Los inodos

¿Qué es inodo te podrás preguntar? Es una estructura de datos, su nombre proviene de index node y es que los inodos no son más que índices, que almacenan los números de bloque de las diferentes partes del archivo. Además, contienen metadatos como permisos, propietario, tamaño, fecha de modificación, referencias, tipo de fichero (directorio, archivo, enlace duro, enlace blando,…) salvo el nombre del propio archivo, que en ningún sitio del inodo aparece.

Este sistema tiene una ventaja de rendimiento respecto a FAT en cuanto al acceso aleatorio a los archivos, ya que es mucho más rápido de esta forma que con FAT. En FAT para hacer lo mismo tenemos que ir recorriendo la tabla arriba y abajo siguiendo los números de bloque hasta encontrar el bloque deseado.

Normalmente un inodo tiene un tamaño fijo, lo que implica que el índice no se puede alargar hasta el infinito. Esto hace que haya un número limitado de bloques que puede usar un archivo y por ende, que haya un tamaño máximo de archivo que no es muy elevado. Para solventar este problema hay varias soluciones. El enfoque de UFS y de ext2/3/4 consiste en múltiples niveles de indexado progresivo.

Esto significa que los primeros bloques son números de bloque directos pero los siguientes son números de bloque que llevan a tablas de inodo secundarias que ya sí, hacen referencia al archivo real. Más adelante los números de bloque hacen referencias a tablas de inodo secundarias que a su vez llaman a tablas de inodos terciarias.

Esto provoca algo que en principio puede parecer paradójico y es que es más lento leer una zona final de un archivo que una zona del principio, aunque en una lectura secuencial no se nota demasiado.

Otra solución a esto es enlazar los inodos a modo de lista enlazada añadiendo al final de cada inodo un número de inodo al que continuar la lectura de índices.

Localización de los inodos

Los inodos se crean cuando se formatea el disco y permanecen en un estado libre. No se pueden añadir más inodos ni quitar inodos y no puede haber más archivos y directorios que inodos por esta misma razón. Esto es una desventaja respecto a FAT, ya que en FAT puede haber tantos archivos como bloques haya/entradas tenga la tabla. En sistemas de inodos como ext2/3/4 puede ocurrir que no queden inodos libres pero haya todavía bloques libres, dejando todo ese espacio inutilizado (aunque en realidad lo podrían usar los archivos existentes si creciesen).

Los inodos se pueden ubicar de dos formas distintas. Un enfoque consiste en ponerlos al principio del disco todos juntos. Otro enfoque, el que sigue ext3, consiste en dividir el disco en 4 zonas y ubicar inodos en cada inicio de zona. La idea es que los inodos de esa zona usen bloques de esa zona y de esta forma reducir los desplazamientos de las cabezas lectoras del disco (en unidades SSD esto da completamente igual como podréis suponer).

Gestión del espacio libre

Una de las grandes ventajas de FAT era que la tabla podía mantener a la vez un listado de bloques libres, listos para ser usados. Con inodos no tenemos esa facilidad y tenemos que recurrir a otros tipos de estructura. Aquí hay muchos planteamientos siendo el más común el mapa de bits. El mapa de bits es una estructura que se compone de un listado de bits. Cada bit corresponde a un bloque y dependiendo de si el bit es 1 o 0 podemos saber si el bloque está libre u ocupado.

Como veis, los sistemas basados en inodos tienen que mantener varias estructuras de datos de forma paralela. Esto aumenta las probabilidades de inconsistencias en el sistema. Por este motivo, muchos sistemas más avanzados como ext4 mantienen un journal o diario.

Fragmentación

Veamos como se comportan los sistemas de inodos ante los tres tipos de fragmentación. Respecto a la fragmentación interna, que es aquella que sucede cuando asignamos espacio de más a archivos que no necesitan tanto, tiene los mismos valores que FAT, ya que los bloques siguen pudiendo pertenecer únicamente a un archivo. Realmente, para mejorar la fragmentación interna tenemos que saltar a sistemas como XFS o JFS.

La fragmentación externa de los sistemas basados en inodos es la misma que la de FAT, 0, ya que todo se asigna mediante bloques del mismo tamaño.

Respecto a la fragmentación de datos, históricamente las implementaciones como UFS o ext2/3 se han comportado relativamente bien, aunque a nivel teórico nada impide que se comporten igual de mal que FAT, no existen mecanismos preventivos. Ext4 por contra, sí que tiene mecanismos de prevención (delayed allocation).

Directorios y enlaces duros

En los sistemas basados en inodos los directorios son más sencillos que en FAT, ya que no tienen que almacenar los metadatos del archivo en cuestión. En un fichero de directorio simplemente se almacena el nombre y el número de inodo correspondiente.

Aquí surge un concepto muy interesante, el de enlaces duros. Un enlace duro no es más que otra entrada de directorio que apunta a un mismo inodo. Realmente desde el punto de vista del sistema de archivos no existe un fichero original y su enlace. Simplemente dos entradas diferentes apuntando al mismo inodo. ¿Y cómo reacciona esto a los borrados? Imagina la siguiente situación: tengo un fichero y creo un enlace duro. Borro el fichero original y su inodo se libera. Ahora creo otro archivo y reutiliza ese mismo inodo que estaba libre. ¡Ahora el enlace duro apunta a un contenido totalmente distinto sin darse cuenta! Para prevenir esto, los inodos no se liberan hasta que no quede ninguna entrada de directorio apuntando a ellos. Para eso sirve el campo referencias dentro del inodo, para llevar la cuenta de cuántas veces se hace referencia al inodo en el sistema de archivos. Cuando el valor de referencias llega a cero, se puede liberar sin problema.

Conclusiones

Los sistemas basados en inodos son conceptualmente algo más complejos que los basados en FAT. Comparten además limitaciones comunes, usan más espacio de disco, aunque suelen ser más rápidos.

Actualmente existen sistemas basados en inodos mucho más avanzados y complejos que UFS y ext2/3/4 y que mejoran este sistema de forma sustancial. Por ejemplo en XFS los inodos tienen una estructura totalmente distinta donde se indica un bloque de inicio y una longitud en número de bloques contiguos que pertenecen al archivo. Muchos sistemas además usan estructuras de árbol B+ como pueden ser ZFS o Btrfs.

¿Cómo funcionan los sistemas de archivos basados en FAT?

Voy a dedicar unas entradas en el blog a hablar del funcionamiento de los sistemas de archivos, un componente fundamental en la gran mayoría de sistemas informáticos. Voy a empezar con los basados en FAT sin centrarme en ninguno en concreto (FAT16, FAT32, exFAT,…). Intentaré escribir también sobre inodos y mecanismos más raros y avanzados.

En esencia un sistema de archivos es un método ordenado que permite guardar datos sobre un soporte físico para luego poder acceder a ellos. Históricamente ha habido muchos enfoques a este problema: los sistemas más usados usan archivos, directorios y enlaces.

Bloques y sectores: la división del disco

Esta parte es común a muchos sistemas de archivos, tanto FAT como inodos, como otros. A nivel físico los dipositivos están divididos. En el caso del disco duro, el dispositivo de almacenamiento más común, los discos se dividen en sectores de N bytes, según parámetros de la fabricación. Estos sectores cuentan con código de control de errores incorporado y todo ello es manejado por la controladora de disco que opera ajena al sistema operativo. Los sistemas de archivos dividen a su vez el disco en bloques. Es importante dejar claro que bloque no es igual a sector. El bloque es una división que hace el sistema de archivos y los sectores los hace la controladora de disco. Usualmente un bloque equivale a varios sectores, aunque la equivalencia real depende del sistema de archivos en concreto.

Algunos bloques especiales: boot y superbloque y raíz

Antes de entrar en el mecanismo específico de FAT es necesario comentar que en un disco existirán dos bloques de vital importancia ajenos a FAT. El primero es el bloque de boot o arranque (también llamado MBR). Normalmente situado en el sector 0 del disco duro, contiene código para iniciar el sistema operativo. El superbloque suele ser el bloque siguiente, contiene metadatos del sistema de archivos (por ejemplo, puede decir que usamos FAT con bloques de 32KiB, etc). Además en FAT es necesario que exista un fichero siempre, el fichero del directorio raíz.

Directorios

Los directorios o carpetas son archivos como otros cualquiera, solamente que en sus metadatos se indica que es un directorio y no un fichero corriente. Los ficheros de directorios son los encargados de almacenar los metadatos de los ficheros (paras saber si son ficheros, otros directorios, su fecha de modificación, propietario y tamaño entre otros) que se encuentran en el directorio así como una referencia al bloque.

Un fichero en FAT

Vamos al asunto. Supongamos que en un determinado bloque N tenemos un fichero. Este bloque es de 64 KiB. Si un fichero ocupa menos de 64 KiB, perfecto, todos los datos entran en el bloque. Simplemente ajustamos los metadatos de tamaño con el valor correcto y el resto del espacio que queda en el bloque queda inutilizado.

Este espacio perdido se denomina fragmentación interna y dependiendo de los datos que se almacenen en un disco duro, el porcentaje de pérdida puede ser mayor o menor. Evidentemente si tenemos bloques muy grandes y ficheros muy pequeños perderemos mucho espacio debido a la fragmentación interna. Tener bloques muy pequeños y ficheros muy grandes también es problemático pero por otros motivos.

Tipos de fragmentación

En un sistema de archivos existen 3 tipos de fragmentación: interna, externa y de datos. La interna se refiere al espacio perdido en bloques asignados a ficheros que no están llenos por completo. La externa se refiere al espacio que perdemos por no tener un espacio libre contiguo lo suficientemente grande como para guardar el fichero allí. Ningún sistema FAT o de inodos tiene fragmentación externa al usar todos bloques de tamaño predefinido. Por último la fragmentación de datos, o fragmentación a secas, se refiere a que los bloques asignados estén contiguos o no. Esto tiene implicaciones a nivel de rendimiento pero no al número de bytes que se vuelven inútiles como los otros dos tipos de fragmentación.

¿Pero qué pasa si el contenido de nuestro fichero no puede entrar en el tamaño de bloque? Aquí viene la gracia de FAT, la File-Allocation-Table. La FAT es una tabla compuesta por entradas que indican el siguiente bloque del archivo. La tabla está indexada por bloque y además de indicar cuál es el siguiente bloque del archivo también indica si el archivo acaba ahí o si ese bloque está libre y puede usarse para un archivo nuevo.

En la foto el archivo /home/user/hola.txt tiene una longitud menor al tamaño de bloque. Así que miramos en la FAT la entrada 150 y efectivamente comprobamos que no hay bloque siguiente ya que es un End-of-File.

Pongamos un ejemplo con un archivo largo. Cada celda de la tabla correspondiente al índice del bloque actual indica el siguiente bloque a leer. Estos bloques pueden estar en cualquier parte. Si en un disco duro muchos ficheros tienen los bloques muy dispersos, se dice que necesita ser desfragmentado.

Conclusiones

FAT es muy rápido si la tabla FAT consigue ser cargada en memoria, ya que obtener los datos necesarios de ella será muy rápido. Desgraciadamente, dependiendo del tamaño del disco duro y del tamaño de los bloques, esta tabla puede ocupar mucho y ser impráctico.

El mecanismo FAT como vemos es simple pero efectivo. Dispone de una fragmentación interna limitada y carece de fragmentación externa. Un inconveniente es que FAT cuando busca un archivo necesita empezar siempre desde el directorio raíz. Esto implica accesos cada vez más lentos a medida que vayamos haciendo carpetas, aunque con sistemas de caché se puede reducir.

El esquema FAT tampoco impone restricciones propiamente dichas al número archivos de un sistema ni a su tamaño. Sin embargo en la práctica suelen existir límites.

Edito: He explicado mejor que significa la fragmentación y sus tipos

9front, un fork de Plan9 desarrollado por dementes

Hace poco, por IRC conocí la existencia de este sistema operativo, 9front, derivado de Plan9. En principio pensé que sería un fork normal y corriente. Cuando entré en su página descubrí sin embargo que era algo completamente distinto.

La 9community, formada por Henry Kissinger y Hillary Clinton, promotores del nuevo orden mundial

Su página web está cargada de minimalismo y memes, la gran mayoría de ellos inspirados en la guerra fría. Al entrar respiramos la esencia de 9front. Por ejemplo, el servidor web de la página es werc. Werc se define a sí mismo como el anti-framework anti-web. Sin bases de datos, solo ficheros y ¡programado en rc! Rc es un componente fundamental de 9front, una piedra angular. Se trata del lenguaje de shell de 9front. El equivalente en Linux sería Bash.

Werc es solo una de las cosas que acoge bajo su paraguas la organización Cat-V (de System-V, marcándose un chiste Unix de cuidado). El lema de Cat-V, Considered harmful (considerado peligroso) nos alerta de que encontraremos contenido que ha sido ajeno para la mayoría de la población. ¿Realmente estamos entrando en Cat-V en la iluminación de Internet? ¿Es entrar en Cat-V un equivalente moderno a salir de la cueva de Platón?

Algunos proyectos de Cat-V son:

  • 9P, un sistema de archivos distribuido. Es usado por 9front.
  • Acme, un editor de texto hecho por Rob Pike
  • Sam, otro editor de texto, también de Rob Pike
  • Fortune, una colección de archivos fortune de varios sistemas UNIX. Parémonos ante este fortune etiquetado dentro de OpenBSD:

Corramos un tupido velo y sigamos.

¡La web oficial de Glenda!

Por si te lo preguntas, sí, la mascota de Go se encuentra inspirada en Glenda

El subdominio harmful está reservado para pensamientos y para expresar opiniones.

Se habla de economía, películas, periodismo, relaciones personales (de tratar con estúpidos, un artículo muy bueno), de lo políticamente correcto, de ciencia, de la seguridad post 11S, de sociedad (y para mi sorpresa contiene una opinión que yo también tengo pero que apenas he visto, el matrimonio debe ser eliminado del sistema legal de los países para pasar a ser algo cultural/religioso, similar al bautizo), se habla de software, de estándares y de palabras. Pretenden hablar de: SQL, fútbol, la Matrix, svn, postmodernismo, gnu, religión, vi, educación, apache, respeto, teoría de cuerdas, complejidad, comida ‘orgánica’, etanol, igualdad, metadata, lógica de “sentirse bien”, teoría del trabajo, …

HTTP 0.2, un intento de simplificar HTTP.

NineTimes, la web de noticias del mundo Plan9, Inferno y 9front.

Y por supuesto, un archivo de citas célebres.

Volvamos a 9front

Continué en la página de 9front, vi que tenía un Código de Conducta (algo que han introducido algunos proyectos open source pero que bajo mi punto de vista es innecesario y en algunos casos peligroso). Sin embargo en 9front no hay un código de conducta, hay varios. Cada vez que te metes en la página sale uno distinto. Y todos son muy random. Desde el credo en latín hasta una especie de receta para crear desarrolladores químicamente. La mitad son cánticos de alabanza a 9front. Yo veo en esto una sátira perfecta de lo que son algunos Códigos de Conducta.

Luego vemos para descargar las ISO, pero a estas alturas es lo que menos importa. A continuación encontramos una recopilación de webs alternativas para 9front. Hay una basada en 4chan, pero esta me gusta más:

Y llegamos a mi sección favorita, Propaganda.

Porque el boot de 9front es explosivo, nuclearmente explosivo
La comunidad 9front

Los altos mandos de 9front
The front fell off

Man es un comando muy propenso a chistes
Mothra es el navegador web de 9front
Orwell dirige NineTimes
El comando timesync no es más que una modernización de Stonehenge

Posiblemente haga una entrada seria hablando de 9front, pero es que la comunidad 9front tiene mucha tela que cortar.

Y donde dije dementes, quise decir genios. Son absolutos genios.

Emulando a Linus Torvalds: Crea tu propio sistema operativo desde 0 (VIII)

Este artículo lo escribí para el blog en español DesdeLinux el 23 de diciembre de 2014 y ahora lo dejo aquí, en mi blog personal. El artículo está tal cual, sin ninguna modificación desde aquella fecha.

Volvemos a la serie de tutoriales sobre como crear nuestro propio sistema operativo. Supongo que este capítulo os gustará mucho porque por fin podremos interactuar con nuestro sistema operativo. Hoy leeremos la entrada del teclado. Para ello el esquema es similar al del timer. Tenemos que usar los IRQ igualmente así que empezaremos igual que con el timer.

Nuestro handler de teclado sin embargo es algo más complejo ya que vamos leyendo las teclas y las vamos depositando en un buffer.

Podemos comprobar como llamamos a una función llamada ND::Keyboard::GetChar. Allí obtenemos el caracter y después si no es un caracter vacío (aquí he usado 255, habría que usar un sistema mejor) ponemos el caracter en pantalla y lo almacenamos en un buffer simple de chars (esto también es susceptible de mejora, el sistema actual puede desbordarse).

Aquí podemos ver como se obtiene la tecla que ha sido pulsada. En 0x60 siempre va a estar la última tecla pulsada. De hecho se puede leer directamente sin tener que usar el IRQ, pero entonces no sabremos indentificar cuando se ha producido un cambio. Allí comprobamos con la operación AND que el código de obtuvimos corresponde a una tecla que se ha dejado de pulsar.

En ese caso devolvemos 255 (porque luego lo ignoraremos) y en caso contrario la tecla ha sido pulsada. En ese caso devolvemos la posición de un array llamado enUS. ¿Qué información contiene este array? Este array es lo que llamaríamos un keymap o un mapa de caracteres. Como sabrán diferentes idiomas tienen diferentes teclados y no son compatibles ya que sobreescriben las teclas. Así enUS nos dará la tecla correspondiente a cada código y funcionará en un teclado americano.

También había una función definida que obtenía una frase. El propósito es simplemente obtener acceso más fácilmente a los strings desde las aplicaciones que lo necesiten, de momento solo una. Hablo de NextShellLite, una versión reducida del posible futuro shell que tendría NextDivel. El propósito de NextShellLite es únicamente el de proveer de un shell reducido para ir probando poco a poco nuevas funcionalidades. No voy a poner el código del shell aquí pero lo he incluido dentro del código de NextDivel.

De momento no funciona como un programa aparte sino como una función que llama el kernel, principalmente porque todavía no añadimos la opción de ejecutar ejecutables. Y claro, unas imágenes de como funciona el shell con las nuevas funciones de entrada de teclado.

NextShellLite

Emulando a Linus Torvalds: Crea tu propio sistema operativo desde 0 (VII)

Este artículo lo escribí para el blog en español DesdeLinux el 25 de agosto de 2014 y ahora lo dejo aquí, en mi blog personal. El artículo está tal cual, sin ninguna modificación desde aquella fecha.

Bienvenidos a otro post sobre cómo crear nuestro propio sistema operativo. Ha pasado mucho tiempo desde el último post, debido principalmente a un bug que encontré en lo que nos toca hoy. Veremos cómo manejar el reloj en arquitecturas x86.

Anteriormente habíamos activado los IRQ de manera genérica, pero hubo un pequeño problema ya que no los activábamos correctamente y pasábamos datos extra. Finalmente lo solucionamos carlosorta y yo y os puedo seguir comentando cómo seguir.

Bien, el reloj es un IRQ, concretamente el primero. Para configurarlo usaremos la función que definimos anteriormente para instalar de manera genérica los IRQ, la NDIRQInstallHandler.

El código se ejecuta de la siguiente manera: el sistema de inicialización llama a ND::Timer::Setup, que llama a NDIRQInstallHandler para insertar en la primera posición, el IRQ0, una función de callback cuando el evento se produzca, esa es NDTimerHandler que aumenta los ticks. Como hemos puesto la velocidad del reloj a 18 Hz, como veremos más adelante, si lo dividiésemos entre 18 y nos diese entero habría pasado un segundo.

La función ND::Timer::Phase nos sirve para ajustar la velocidad del timer, ese número tan extravagante es 1.19 MHz que es un valor común. Bien, esta función la deberemos llamar si quisiésemos cambiar la velocidad del timer, por defecto va a 18,22 Hz, un valor peculiar que debió de decidir alguien dentro de IBM y se ha quedado hasta nuestros días.

La función ND::Timer::Wait es bastante simple, solamente espera con un bucle while hasta que se hayan alcanzado los ticks necesarios para continuar.

En la imagen podemos comprobar que si descomentamos el código dentro del NDTimerHandler obtenemos esto:

NextDivelSegundos