Trapos sucios de Unix: readdir()

Una de las cosas más curiosas de los sistemas Unix es cómo han ido cambiando su propia imagen a lo largo de los años. Hoy Unix se entiende como sinónimo de fiable, eficiente, buen diseño, profesional, etc; a pesar de que Unix era un sistema operativo muy simplista, con importantes fallos y carencias  que tuvieron que arreglarse o añadirse posteriormente, a menudo no de la mejor manera. Un buen ejemplo de ello es la historia de readdir(), una función que devuelve la lista de archivos y/o subdirectorios presentes dentro de un directorio.

Uno de los principios fundamentales de la filosofía Unix es el de "Todo es un archivo", es decir, la unificación de toda clase de I/O sobre un sistema de archivos jerárquico en el que los archivos, además de archivos, pueden representar a dispositivos de hardware. Tal fuerza dogmática tiene este principio que cuando se diseñó Unix se decidió, o se asumió de manera natural, que los directorios también eran archivos normales y corrientes. Así que las primeras versiones de Unix no tenían llamadas al sistema para algo tan común como listar un directorio.

¿Cómo averiguaba entonces un programa, como por ejemplo ls, los contenidos de un directorio? Pues tratándolos literalmente como archivos. Se abría el directorio con fopen() y se leía el contenido con fread(). El contenido de los archivos de tipo directorio era simplemente una lista consecutiva de parejas nombre/número de inodo, cada una representando un archivo y/o subdirectorio. Y el programa tenía que echar un ojo a esas estructuras e interpretarlas él mismo para saber qué había dentro del directorio, no existía ninguna llamada al sistema que lo hiciera por ti.

Por esa razón, la primera función readdir() no fue una llamada al sistema, sino una función implementada dentro de los programas que lo necesitaban. Si no lo creen, pueden verlo ustedes mismos en la función readdir() del ls.c de Unix Version 7, de 1979. Cuando los diferentes sistemas Unix fueron incorporando características que hacían de esta manera de trabajar con directorios un inconveniente, acabaron añadiendo llamadas al sistema (getdents()) que sirvieran de ayuda para implementar readdir(), la cual se acabaría incorporando a la libc.

Como prueba de esta herencia, han quedado ciertos retazos en algunos sistemas Unix (por ejemplo, FreeBSD), en los que el comando cat directorio es un comando válido, que se ejecuta sin errores, e imprime en la pantalla algo que parece "basura" sin formato del tipo de /dev/random pero que, en realidad, es el contenido del directorio, tal y como ocurría en los Unix originales (en Linux esto no ocurre, se ha asumido que los directorios son directorios, y tratar de leer un directorio como archivo devuelve el error EISDIR).

Pero no se acaba aquí esta historia. Que el diseño original de Unix tuviera estos entresijos acabaría teniendo consecuencias que se heredaron con el tiempo, hasta llegar a hoy.

El hecho de que los directorios originales de Unix fueran simples concatenaciones lineales de parejas nombre/númerodeinodo hizo que las interfaces asumieran que el contenido de un directorio sería siempre lineal. De ese modo surgieron APIs como telldir(), la cual obtiene la posición de un elemento dentro del listado de un directorio. Esta posición puede utilizarse en seekdir() para mover un listado a una posición determinada del directorio. Es decir, se trata a un directorio como un archivo en el que un programa puede moverse de un lado a otro sin problemas.

Esto causó un gran problema con el advenimiento de los sistemas de archivos modernos, basados en estructuras de árbol. Las estructuras de árbol utilizadas en sistemas de archivo (B-Tree y similares) tienen como una de sus características fundamentales el rebalanceo para redistribuir los nodos del árbol a medida que se crean o eliminan archivos. Este rebalanceo puede cambiar el orden en el que un determinado elemento aparece en un listado de directorio, es decir, no se garantiza que usar seekdir() en una posición determinada dos veces consecutivas nos lleve al mismo elemento.

¿Que han hecho los sistemas de archivo Unix basados en B-Trees para lidiar con este problema? Esencialmente, tratar de parchear el problema (resolverlo no es posible, siempre habrá que mantener la compatibilidad con la tradición Unix). Por ejemplo, JFS tiene un B-Tree extra exclusivamente dedicado a mantener una doble indexación que permita satisfacer las garantías de readdir() y compañía. Btrfs, un sistema de archivos de última generación, también mantiene una doble indexación, por cada elemento añadido a un directorio se crean dos items: uno ordenado por hash y otro ordenado secuencialmente. Ext3/4 por su parte sólo ordena los elementos por hash, pero trata de mantener la secuencialidad leyendo los contenidos del directorio por el orden de hash.

Estas técnicas suponen, por supuesto, un trabajo y E/S extra que tiene un impacto en el rendimiento. ¡Ah, y por supuesto, la concepción lineal de los directorios implica que listarlos con readdir() y operar con ellos puede tener una complejidad algorítmica lineal! Así que resulta que Unix, culmen del buen diseño de sistemas operativos, implementa los directorios de una forma verdaderamente patética, y nos hacer pagar sus errores con impacto en el rendimiento (hay software que usa diferentes trucos para evitar acumular miles de archivos en un mismo directorio).

La lección de toda esta historia es que por muy genial que sea el diseño de tu software, obsesionarse con abstracciones perfectas e intentar imponerlas bajo la creencia de que su pureza es la única forma decente de hacer las cosas puede llegar a ser un gran error.