3 de diciembre de 2011

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.

11 comentarios:

  1. Anónimo5:06 a. m.

    Sería una locura cambiar las garantías de readdir() para evitar esas implementaciones? hay algún plan?

    ResponderEliminar
  2. Anónimo9:52 a. m.

    Vamos, llevamos 40 años con Unix como para que no se les hubiese ocurrido eso, ¿no crees?

    Unix lleva 40 años. Muchas tecnologías y paradigmas han salido en 40 años, y lo que parecía la perfección en 1969 ya no lo es ahora. Claro, Linux ha mejorado, pero sigue teniendo la misma base de Unix, con las mismas características obsoletas.

    Recomiendo ampliamente leer The Unix-Haters Handbook, es una recopilación de las discusiones de una vieja lista de correo llamada Unix-Haters (la versión viejita de Linux Hater´s Blog). Es gratuito y ofrece un interesante (y argumentado) punto de vista acerca de Unix.

    ResponderEliminar
  3. Curioso, supongo que tal como han llegado revoluciones al apartado gráfico, a demonio de init, acabarán llegando mejoras también en esa parte.

    Lo de que llevar al extremo eso de "todo es un archivo" es malo, no se me había ocurrido. Es un interesante punto de vista.

    ResponderEliminar
  4. El Unix Haters Handbook no ha envejecido nada bien. Que Apple adoptara años más tarde un Unix como base de su Mac OSX (uno de los autores trabajaba para Apple) le restó bastante credibilidad :-P

    Lo mejor, el "antiforeword" de Dennis Ritchie.

    ResponderEliminar
  5. Anónimo8:42 a. m.

    Yeah, es un libro viejo. Muchos de los ejemplos que explican ya no son aplicables en un Linux moderno, aunque eso sí hay algunos que aun persisten, y para ser errores y fallas en usabilidad documentadas por más de 15 años, es increíble que aun no se les haya dado solución.

    Lo importante es que el libro demuestra una vez más que UNIX nunca fue un buen SO, una perfección en seguridad y diseño como creen muchos. No significa nada que Apple haya usado un UNIX para crear OSX, pues también se ha demostrado que OSX es más inseguro que Windows.

    ResponderEliminar
  6. Ningún sistema operativo es "perfecto" y todos tienen sus "trapos sucios". ¿Quién de los que hemos leído este artículo, ha puesto el "ojo" y a leído con detenimiento el código fuente de un sistema operativo "real" y en "producción", y entendido que hace y por qué?. ¿Quién a revisado su arquitectura, sus APIs, sus utilerías con el suficiente detalle?

    Basta con inscribirse en cualquier lista de seguridad, para darse cuenta de la cantidad de "patches", "service pack", "PTFs" o el nombre que quieran usar, se producen mensualmente.

    Sólo los que lo desarrollaron tienen ese nivel de conocimiento (y no en todos los casos), como para reconocer todas sus fallas, y no lo harán por el simple hecho de la mala publicidad.

    Al menos en ambientes como UNIX (Linux, BSD, etc.) y otros contados, tenemos la oportunidad, aunque sólo un pequeño porcentaje la aproveche, de conocer internamente lo que realmente hace o falle, e incluso hasta proveer algunas soluciones al respecto.

    Se debe ser realista. El computador mas seguro, es uno apagado y desconectado de la red y hasta la fuente de energía. Sólamente una eficaz evaluación de las caracteristicas de un sistema operativo (e incluso del hardware) particular, nos podrá en el punto inicial del sistema que necesitamos.

    ResponderEliminar
  7. Anónimo5:01 a. m.

    voy a ser una fruta en una carniceria
    de casualidad viendo post antiguos encontre una parte en el que decias que no trabajas con algo q tenga q ver con ordenadores...
    es cierto eso????
    Xq tus conocimientos son bastantes extensos y profundos

    ResponderEliminar
  8. Anónimo: Si, es cierto. En cuando a saber estas cosas, es cuestión de leer.

    ResponderEliminar
  9. Anónimo10:40 p. m.

    Y vaaaya!!
    Te felicito por tu entusiasmo y ganas de aprender, es admirable!!!
    Pero de seguro llegaste a hacer algo de programación y cosas como esas...
    X cierto, por sobre todo tu conocimiento resalta tu empeño por ser lo más objetivo posible en tus criticas.
    Eso no todos lo tienen!!
    Saludos y felices fiestas desde Paraguay

    ResponderEliminar
  10. Interesante artículo contiene información importante, gracias por informarnos sobre este tema.

    ResponderEliminar
  11. Anónimo8:57 p. m.

    ¡Este es el primer blog que encuentro que habla de *nix a nivel técnico!

    ¡Felicidades!

    ResponderEliminar