28 de septiembre de 2009

Haciendo dinero con Linux

¿Cuántas veces no se ha afirmado que con el software libre no se puede hacer negocio? Aun se pasa algún despistado por aquí afirmandolo en los comentarios. Me pregunto como se explicarán estos resultados de Red Hat: Un aumento de las ventas del 11% y de los beneficios del 36.9%. En plena crisis. Para ser un negocio del que es imposible sacar dinero, no está nada mal.

¿Cómo es posible que en plena crisis la gente siga insistiendo en gastarse dinero en Linux, y mucho menos en Red Hat, que no se conforman precisamente cuatro duros? Quizás la mejor explicación la haya dado hoy Michael Tiemann, fundador de Cygnus, la empresa especializada en GCC que Red Hat compró en 1999: "Todo se reduce a mi creencia en que los mercados libres son el mejor modo de hacer funcionar una economía, y si sabes hacer algo de una manera mejor, debe ser posible conseguir hacerlo rentable y exitoso". Un corolario a esta frase es que si Red Hat está mejorando sus resultados, es porque sabe hacer algo mejor que los demás.

Es muy significativo que de los 30 contratos que dicen haber firmado en el trimestre anterior, 23 incluyan virtualización, a pesar de que hacer poquísimo que anunciaron la primera versión con soporte de KVM, RHEL 5.4. Aquí Red Hat tiene una gran ventaja, y es que puede ofrecer KVM como parte dentro de un contrato más amplio que incluya otras cosas. VMware es el rey de la virtualización, pero no tienen un SO. Si uno echa un ojo de vez en cuando, comprobará que los del sombrero rojo están poniendo toda la carne en el asador en lo que concierte a cosas relacionadas con la virtualización, asi que cabe esperar grandes alegrías y esperemos que mucho dinero para Red Hat, Novell y compañía.

Parece que el tal Jim Whitehurst, el CEO de Red Hat, está montándoselo bastante bien.

Como curiosidad al margen de este post, me han pasado el enlace a esta fantástica página: inudge.net, donde se pueden hacer melodías simples y compartirlas en plan 2.0. Para que no se quejen de que este blog es aburrido, aquí pueden escuchar una melodía psicodélica de un servidor, en la que comprobarán los destrozos que puede ocasionar ser fan acérrimo de Mike Oldfield (silenciando todos los instrumentos excepto el primero, el azul, suena remotamente a música de videojuego). De lo más entretenido que he visto en muchísimo tiempo.

24 de septiembre de 2009

Btrfs: Una jungla de B-Trees

Este artículo describe la estructura interna de Btrfs, enfocado en su B-Tree y en como ha sido combinado en muchas y variadas formas para llegar a implementar la funcionalidad completa de un sistema de archivos de última generación. El texto es largo, pero bastante completo.

Introducción

Btrfs es un alias de "B-tree filesystem". La referencia a los B-trees podría parecer poco importante, los sistemas de archivos (en adelante SdA) y bases de datos los utilizan desde hace décadas. Pero no es casual que Btrfs tenga ese nombre, su estructura está muy influenciada por este concepto y, en realidad, es la característica que mejor lo define y diferencia de otros SdA, incluso de ZFS.

Siendo más concretos, Btrfs no implementa un B-tree tradicional, ya que son poco apropiados para técnicas de COW y snapshots y requerimientos de escalabilidad. ZFS optó, debido a ello, por una técnica inspirada en el slab. Btrfs no ha ido por el mismo camino, escogió otro a raiz de una conferencia para desarrolladores de SdA Linux celebrada en Febrero del 2007. Allí, un tal Ohad Rodeh, trabajador de IBM en sus laboratorios de I+D en Israel, presentó un nuevo tipo de B-tree optimizado para técnicas de COW y snapshots con escalabilidad y snapshots muy eficientes -tanto en términos de tiempo como de espacio-. De hecho presentó sus algoritmos como una ayuda para aquellos interesados en crear algo equivalente a ZFS/WAFL en Linux. Chris Mason, que había trabajado en Reiserfsv3, tomó nota y e implementó esa técnica, y de ahí el código evolucionó hasta convertirse en Btrfs. Queda claro que para comprender cómo funciona Btrfs hay que comprender cómo funciona su B-tree.

El B-tree: nodos e ítems

Los B-trees utilizados en SdA solamente almacenan datos en las hojas del extremo del árbol, concretamente en los ítems. Cada hoja puede contener varios ítems. El resto de nodos solo se utilizan para crear rutas hacia los ítems. Todos los B-trees se ordenan respecto a una clave, la que el programador decida, en el caso de Btrfs es esta:

struct btrfs_key {
u64 objectid;
u8 type;
u64 offset;
}

El primer campo, objectid, de 64 bits, es un identificador de objecto, único para cada objeto (pero un objeto puede estar compuesto por varios ítems, asi que puede haber varios ítems con el mismo objectid). Luego tenemos type, de 8 bits, que indica el tipo de item, es decir, el tipo de datos que contiene. offset indica una posición dentro del SdA (su uso concreto depende del tipo de ítem).

Tanto los ítems como los nodos tiene esta clave, sin embargo, ya se dijo que los nodos solo crean rutas hacia los ítems, por lo que a la clave solo añaden un puntero de 64 bits que indica dónde se encuentra el siguiente nodo/ítem en la estructura. Los ítems por su parte a la clave añaden alguna cosa más:

struct btrfs_item {
struct btrfs_key key;
u32 offset;
u32 size;
}
La clave tan solo identifica al ítem, no es el ítem en sí. En esta estructura se indica, en offset, la localización del ítem en la hoja del B-Tree, y en size su tamaño. Este offset es distinto del offset de la clave, que indicaba una posición absoluta en el SdA. Así es como se agrupan en una hoja los ítems:

[Struct Item0 | Struct Item1 | Struct Item2 | ... |Item2    |Item1 |Item0          ]

El espacio entre paréntesis representa una hoja del árbol. Como se ve, las estructuras que describen los ítems (struct btrfs_item) se agrupan al principio del bloque, y el item de verdad, cuyo tamaño varía dependiendo del tipo de objeto, se encuentra al final, esa localización es la que indica el offset de la estructura btrfs_item. Esta organización responde a motivos de eficiencia. Un detalle curioso es que en el caso de archivos pequeños, los ítems correspondientes al archivo almacenan los datos directamente en el ítem (idea derivada del "tail packaging del reiser v3), permitiendo así un acceso rápido a archivos pequeños.

Esta es una descripción quizás más detallada de lo necesario. Como resumen, lo único que hay que tener presente por encima de todo es que se trata de un B-Tree cuyos ítems se identifican con un identificador de objeto objectid de 64 bits y cuyo formato es especificado por el campo type.

Btrfs utiliza este B-Tree para almacenar todo tipo de cosas en forma de ítems: inodos, atributos extendidos, directorios, snapshots...cada elemento con un objectid independiente y un type que indique lo que son. Esto simplifica la implementación del SdA, pues cualquier operación termina siendo una búsqueda, inserción, modificación o eliminación de ítems de un B-Tree. El código se encuentra en el archivo fs/btrfs/ctree.c, y se encarga de hacer todas las modificaciones de bajo nivel, de rebalancear el árbol cuando es necesario, de aplicar COW, etc, todo automáticamente, sin que las otras capas del SdA tengan que preocuparse de ello.

Un bosque de B-trees: Root B-Tree

Una vez que se conoce el B-Tree, entender el funcionamiento de Btrfs es relativamente simple, solo hay que comprender las ramificaciones y combinaciones de sus conceptos básicos.

Todo SdA tiene un superbloque, es la primera estructura que se lee y la que describe las ubicaciones de todas las demás. Es tambien la única que tiene una localización fija en el disco, todas las demás pueden estar en cualquier parte. El superbloque tiene el formato de la estructura struct btrfs_super_block, que no se muestra aquí debido a su extensión. De sus campos destacaremos csum, que al igual que el csum de struct btrfs_header sirve para detectar corrupción. Y los mas importantes: root y chunk_root, de 64 bits, que indican la localización de dos B-Trees.

¿Dos B-Trees? Si, Btrfs tiene varios. De hecho, el B-Tree root es en realidad la raiz de raices, un árbol que almacena punteros a otros árboles. Actua, por así decirlo, como una especie de directorio de B-Trees.

Una gran ayuda para entender más visualmente Btrfs es la herramienta btrfs-debug-tree, que muestra la estructura del árbol. En el caso de Root tree la salida de btrfs-debug-tree correspondiente es:

root tree
leaf 29364224 items 9 free space 2349 generation 7 owner 1
fs uuid 56650d3d-a7bf-463c-a59f-fc87a454d47e
chunk uuid e7457d2d-b783-4cb1-9f43-aa4843ab02fd
  item 0 key (EXTENT_TREE ROOT_ITEM 0) itemoff 3756 itemsize 239
      root data bytenr 29368320 level 0 dirid 0 refs 1
  item 1 key (DEV_TREE ROOT_ITEM 0) itemoff 3517 itemsize 239
      root data bytenr 29372416 level 0 dirid 0 refs 1
En la primera línea se indica que es el Root tree, la segunda indica el comienzo de una hoja, el número total de ítems que contiene y el espacio libre que le queda para albergar más, y otros datos irrelevantes. La tercera y la cuarta indican las UUIDs del SdA y del Chunk tree (hablaremos de él más adelante). Tras ellos, los ítems. Los datos de la clave son los que están entre paréntesis, y a continuación de éste, el tamaño del ítem y su offset dentro de la hoja. Centrándonos en la clave, presentada en formato (objectid, type, offset), vemos que ambos ítems son de tipo ROOT_ITEM (un tipo de ítems que almacenan información sobre la ubicación de otros B-Trees), y sus objectid indican el tipo de árbol, Extent tree y Device tree respectivamente. Esos objectids presentados en forma de constantes pertenecen a unos rangos reservados. El offset, como vemos, no se utiliza. En la segunda línea de cada item, vemos el texto "root data bytenr", que quiere decir "byte donde se encuentra el inicio del B-Tree". El resto de datos se pueden obviar.

Device Tree

Btrfs no utiliza todo el espacio de un dispositivo tras añadirlo al SdA, sino que utiliza una parte y, según va requiriéndolo, recurre al resto. El Device tree, escogido a propósito del ejemplo anterior, sirve para almacenar información sobre qué partes del dispositivo están siendo utilizadas. Por razones que veremos más adelante, este espacio utilizado no se describe como un solo rango, se divide en varios rangos más pequeños, uno trás de otro. Estos son los ítems.

device tree key (DEV_TREE ROOT_ITEM 0)
leaf 29372416 items 7 free space 3484 generation 5 owner 4
fs uuid 56650d3d-a7bf-463c-a59f-fc87a454d47e
chunk uuid e7457d2d-b783-4cb1-9f43-aa4843ab02fd
  item 0 key (1 DEV_EXTENT 0) itemoff 3947 itemsize 48
      dev extent chunk_tree 3
      chunk objectid 256 chunk offset 0 length 4194304
  item 1 key (1 DEV_EXTENT 4194304) itemoff 3899 itemsize 48
      dev extent chunk_tree 3
      chunk objectid 256 chunk offset 4194304 length 8388608
  item 2 key (1 DEV_EXTENT 12582912) itemoff 3851 itemsize 48
      dev extent chunk_tree 3
      chunk objectid 256 chunk offset 12582912 length 8388608

Los ítems tienen claves con el type DEV_EXTENT (alias de "extent de dispositivo", o sea, rango continuo de bloques en un dispositivo). Su objectid es el identificador de dispositivo al que se hace referencia, que es 1 para el primer dispositivo. Este extraño uso del objectid clarifica cómo usa Btrfs sus diversos B-Trees: Cada uno se utiliza de una forma distinta, o más bien, cada árbol utiliza solo unos tipos concretos de ítems relacionados con su función. El offset indica la parte del disco que se quiere describir, y en los datos del item se indica el tamaño que abarcará esa parte (length), además de repetirse el offset(chunk offset). La primera línea tras cada ítem puede pasarse por alto.

Chunk Tree

El Chunk tree ya se mencionó antes, era aquel cuya posición está especificada en el campo chunk_root del superbloque. Su función es traducir entre el direccionamiento lógico del SdA y el direccionamiento físico del disco. Esto es necesario y se hace en todos los SdA: consideremos un SdA creado en una partición que se encuentra en la mitad del disco, su byte cero podría ser el byte 100.000.000 del disco. En Btrfs esa diferenciación es aun más necesaria, ya que un SdA se expande a varios discos simultaneamente, cada uno con su propio direccionamiento físico.

Es debido a esta función de traducción de direcciones lógicas a físicas que la ubicación del Chunk tree se encuentre en el propio superbloque: para encontrar la ubicación física del Root tree es necesario leer primero el Chunk tree. ¿Y la dirección del propio Chunk tree? Tambien se expresa en direcciones lógicas, asi que el superbloque duplica en su estructura una pequeña parte de información para poder encontrarlo.

Decíamos que el Chunk tree mantiene esas equivalencias lógico<->físicas no en forma de un solo gran rango, sino dividido en trozos (chunks, en inglés). Esos chunks suelen tener entre 256MB y varios GB. ¿De dónde se saca información sobre las direcciones físicas de los dispositivos? Del Device tree, naturalmente. Ya dijimos que ese B-Tree tampoco se definía en un solo gran rango, sino en varios. Y es que el principio y el final de los chunks coinciden exactamente con el principio y fin de los rangos del Device Tree. Un chunk es, por tanto, la representación lógica de una porción de disco.

En este árbol los ítems tienen el type CHUNK_ITEM, que indica que es un ítem con información sobre un chunk. El objectid siempre se asigna al valor de FIRST_CHUNK_TREE (se podría decir que en este caso no se utiliza). El offset indica la dirección lógica inicial del rango con el que se pretende tener una equivalencia física. En el ítem se indica el dispositivo donde éste se encuentra y el comienzo de su dirección física.

FS Tree

Este B-Tree se encarga de almacenar lo que se definiría tradicionalmente como metadatos: Nombres de los archivos y de los directorios, los inodos, información de los atributos extendidos, extents; se trata de la concepción más cercana que la gente tiene del interior de un SdA.

Los ítems de este árbol son algo complejos y de muchos tipos. En Unix, como es sabido, cada archivo tiene su correspondiente inodo, en el FS tree cada archivo tiene varios items, todos con el objectid de su inodo: uno del tipo INODE_ITEM que describe el tamaño y los permisos de acceso de ese archivo, otro de tipo INODE_REF que describe el nombre y número de inodo del directorio en el que se halla, otro EXTENT_DATA que describe la ubicación de los datos del archivo, en el caso de tenerlos. Los directorios, por su parte, tienen tambien varios ítems con el objectid de su inodo, uno de tipo INODE_ITEM, otro de tipo INODE_REF y, por cada archivo que haya dentro del directorio, dos items, uno del tipo DIR_ITEM y otro del tipo DIR_INDEX, ambos conteniendo el nombre y número de inodo de cada archivo correspondiente (la razón de que haya dos ítems por cada archivo se debe a la deficiencia de ciertas APIs de Unix, otros SdA han tenido que hacer cosas similares)

Los items del tipo EXTENT_DATA son los que informan de la ubicación de los datos de los archivos, es decir extents. Contienen en su interior la dirección lógica donde empiezan los datos del archivo, la extensión del extent, si el extent está comprimido, etc.

Extent Allocation Tree

Este es una especie de gestor de espacio libre de Btrfs. Es equivalente a los free space map de otros SdA. En realidad el nombre correcto de este árbol debería ser "used space tree", guarda información sobre las partes de los chunks que están usadas usadas. Se podría decir que su nombre despista un poco.

Este árbol no se toca para nada cuando se leen archivos. El proceso de lectura de un archivo consiste en buscar el archivo en el FS tree, y los ítems indicarán la dirección del disco en la que se encuentran los datos. Btrfs entonces solo tiene que mirar al Chunk tree para saber en qué dispositivo y en qué dirección física tiene que empezar a leer. Solo cuando se añaden, modifican o borran datos es necesario marcar en el Extent tree las partes de espacio que se van a usar, o a liberar las que estaban usadas.

Aparte de esa información, en éste árbol se forman una especie de "grupos de bloques" lógicos, que hacen referencia a grandes extents lógicos de los chunks. El objeto de estos "grupos de bloques" es subdividir el espacio disponible en partes que pueden ser dedicadas a los datos o a los metadatos. Esto se utiliza para poder agrupar separar los datos y los metadatos en chunks distintos.

Checksum tree

Este es el último B-tree. Como su nombre indica, almacena los checksums. Cada item, de type EXTENT_CSUM, contiene el número del byte de cada extent y su checksum.

Subvolúmenes y snapshots

Antes de hablar de estos conceptos, hay que definirlos y diferenciarlos. El snapshot es bien conocido, se trata de una copia idéntica del SdA en el momento en que se toma y que se mantiene inalterado con el tiempo. El subvolumen es un concepto menos conocido: se trata de una especie de nuevo SdA, pero un SdA nuevo de acuerdo con la gestión el espacio en forma de pool. Es decir, no un SdA literalmente aparte, sino uno obtenido del pool.

Un subvolumen vacío no tiene nada dentro, solo los directorios "." y "..". Puede montarse en cualquier directorio. De hecho, existe un subvolumen en todo SdA nuevo llamado "default", que es el que se crea y usa por defecto. Un subvolumen puede tener configurado un límite de espacio, de modo que puede utilizarse como un sustituto de las tradicionales quotas, creando en /home un subvolumen para cada usuario con un límite de espacio determinado.

Sin embargo, internamente subvolúmenes y snapshots son la misma cosa: un FS tree. Uno por cada subvolumen o snapshot. Se diferencian en que el subvolumen es un FS tree vacío, sin archivos ni directorios, mientras que el snapshot tiene ya un montón de archivos y directorios. En realidad los snapshots inicialmente comparten su FS tree con el subvolumen en que se toma, solo se deja una "marca" en nodos e ítems afectados, de modo que cuando cualquiera intente hacer una modificación de su FS tree compartido, el mecanismo COW duplicará las partes modificadas del B-Tree. Puesto que hasta que no sean modificados los ítems que hacen referencia a extents son los mismos para ámbos árboles, los extents que contienen los datos de los archivos se comparten inicialmente, con lo que todo nuevo snapshot comparte todos sus extents de datos y no ocupa prácticamente nada de espacio adicional, solo cuando se modifica un archivo se crea un nuevo extent al que apunta el FS tree que lo haya modificado.

La lista de todos los snapshots y subvolúmenes del SdA se almacena en la raiz de raices, el Root tree. Se almacenan como directorios: literalmente. Cada snapshot o subvolumen tiene un nombre, y en el Root tree se almacena un item de tipo directorio con el nombre e información para encontrar la raiz del FS tree correspondiente.

Mirroring y stripping: regreso al Chunk Tree

El lector sagaz tal vez se haya dado cuenta de hasta ahora no se han mencionado nada sobre la replicación de datos entre varios dispositivos de almacenamiento, ni sobre la capacidad de reescribir, a partir de una réplica, un bloque cuyo checksum erroneo indique corrupción.

Todo se hace en el Chunk tree. Cada item de ese árbol almacenaba equivalencias entre un rango físico de un disco y uno lógico del SdA. Lo que no se mencionó entonces es que cada chunk, además de almacenar información del rango del dispositivo al que quiere representar lógicamente, puede tambien almacenar información sobre más de un dispositivo, e indicar si se quiere que sobre ellos se haga mirroring (copia exacta de los datos) o stripping ("repartir", o dividir los datos del chunk en varios dispositivos).

Esto significa que toda la cuestión de mirroring y stripping se hace a nivel de chunk, cada uno se puede configurar independientemente. Este sistema es muy flexible. Ya dijimos que cada chunk se puede dedicar, por medio del Extent tree, a almacenar solo datos o metadatos. Así es que se pueden configurar los chunks de metadatos con mirroring y los de datos con stripping, por ejemplo. De hecho, esta es la configuración que se utiliza por defecto, se replican los metadatos -esto ocurre incluso dentro de un SdA compuesto por un solo dispositivo- para que las estructuras más importantes del SdA estén salvaguardadas, y los datos se reparten entre varios dispositivos, de haber varios disponibles.

Back references

Esto no tiene nada que ver con B-Trees, pero de todos modos es muy interesante, porque es una característica única de Btrfs. Se trata de una idea extraida de chunkfs, un proyecto creado para resolver la "reparabilidad" de los SdA actuales y que propone una serie de ideas que permitirían crear lo que ellos llaman un SdA "diseñado para ser reparado". Btrfs incorpora buena parte de esas ideas (el nombre "chunk" probablemente derive de chunkfs) , y una de ellas son las "back references", o referencias inversas.

Un ítem de un Fs tree apunta al extent del Extent tree donde se guardan sus datos. Una referencia inversa sería un puntero del extent hacia el ítem del FS tree que lo apuntó. Mantener estas referencias tiene cierto coste, por eso pueden desactivarse, pero aun así se activan por defecto.

Es una información muy preciada que aunque parezca algo paranoica, puede ser muy útil: desde servir para encontrar el ítem que apuntaba a un extent tras descubrirse que éste está corrupto, a poder escanear el disco en busca de extents y poder identificar los que forman parte de un solo archivo fijándose en que los que tienen una misma referencia inversa. Tambien permite reducir el tamaño del SdA, de una forma sencilla, segura y rápida, algo que los SdA tradicionales suelen implementar tarde y mal (por ejemplo, ZFS aun no lo soporta).

Resumiendo...

Se puede sopesar ahora hasta que punto es acertado que el nombre "Btrfs" sea un alias de "B-Tree filesystem". En otros SdA, se crean unas estructuras de datos y se utilizan B-Trees para organizar alguna o algunas de ellas. En Btrfs es al reves, el B-Tree es la estructura de datos fundamental, todas las demás se implementan sobre él. Cada árbol listado en este texto es una especie de instancia del B-Tree modelo.

Toda esta maraña de árboles -más bien jungla- quizás parezca compleja. Incluso podría ser que este texto diera a algunas personas la sensación de que un B-Tree es una estructura demasiado pesada y complicada, y quizás les lleve a pensar que podría haberse ganado en simplicidad no utilizándo tanto árbol excepto en los casos verdaderamente necesarios. Si es así, me temo que mi escritura no es capaz de reflejar la sencillez y limpieza del diseño de Btrfs, en realidad un B-Tree es algo liviano, y es bastante rápido incluso cuando contiene muchos items. Juega a su favor el hecho de que esté preparado para ser escalable en máquinas multicore; diseñar un SdA con las estructuras de datos aptas para ser escalables sería más complicado. La utilización de un B-Tree común que ya ha resuelto esos problemas libra a los programadores de gran parte (pero no todo) ese trabajo.

En cuanto a complejidad, en realidad es sorprendente lo fácil que es comprender todo el diseño a partir de unos pocos conceptos. Una vez que se tienen en la cabeza, cualquiera puede lanzarse a leer gran parte del código y entenderlo sin muchas complicaciones. Hay que hacer notar la limpieza con la que se abstraen ciertos conceptos de otras capas y estructuras. Como comparación, ZFS tambien tiene diferentes niveles bien separados, pero en las estructuras esa diferencia no es tan radical; por ejemplo la estructura encargada de apuntar a un objeto (blockptr_t) contiene el checksum y tres campos de 32+64 bits cada uno en los que se almacena el identificador de dispositivo+desplazamiento de tres copias alternativas, para recurrir a ellas en caso de corrupción. En Btrfs esa información se mantiene separada en el Chunk tree (y una sola vez, no duplicada en cada puntero) y en el Checksum tree , ambos relacionados con los extents del Extent tree por simples rangos de bytes. Podrían añadirse nuevos B-Trees para vaya-a-saber-usted-qué sin que el código ni las estructuras existentes notaran cambio alguno.

En definitiva, Btrfs es un sistema de archivos moderno, con fundaciones muy sólidas y conceptos renovadores que lo harán durar muchos años. Por sus capacidades está muy preparado para sustituir al veterano (pero aun enérgico) Ext4, en cuanto alcance la categoría de estable. Pero tambien sustituirá a reiserfs (v3 o v4), XFS y JFS, lo cual centrará sobre él una mayor atención colectiva de la que Ext4 tiene hoy, que es mucha. En estos momentos su estado de desarrollo podría considerarse como de las últimas versiones alpha; las distros ya empiezan a ofrecer opción experimental en las instalaciones nuevas. Es de suponer que la versión 1.0 vea la luz en la primera parte del año que viene y que pase a usarse como SdA por defecto en las distros a lo largo del 2011.

(Notas: -todo lo referente al Extent Tree y parte del FS Tree han sido revisados desde su redacción original debido a un error conceptual, -se ha eliminado la información sobre la cabecera de cada bloque del btree, no viene mucho a cuento, -se ha simplificado la explicación del B-Tree, -la explicación de los ítems de cada árbol se ha reescrito para ser más visual)

23 de septiembre de 2009

Citas

"I really enjoy arguing, a big part of my life are these occasional flame threads that I love getting into and telling people they are idiots" - Linus Torvalds

17 de septiembre de 2009

ARMándose

En este blog ya he citado más de una vez aquella frase de Linus Torvals que decía que si había una arquitectura con alguna posibilidad de acabar con el predominio de x86, era ARM. Posibilidad remota, remotísima, claro, pero posibilidad. Tambien he enlazado aquí a muchos artículos que hablan sobre la guerra declarada por Intel a esta arquitectura en lo que vienen a ser los netbooks y ese otro sector de dispositivos que pueden ser clasificados de forma vaga como "Cosas-Parecidas-al-iPhone".

Hoy se han publicado en los medios noticias sobre la presentación del Cortex A9 que parecen confirmar que ARM se toma su guerra en serio (de la que ya teníamos noticias por sus propuestas de crear netbooks ARM) y que ha decidido presentar batalla. Y, al parecer, pretende presentarla no solo en netbooks y cosas-parecidas-al-iPhone, sino incluso ¡en servidores! Se referirá, obviamente, a grandes clusters de mini-ordenadores ARM para cálculo científico, clouds, y cosas así.

Y es que los ARM son, a día de hoy, mucho más eficientes que cualquier oferta de Intel, lo cual implica ser superior en rendimiento en cualquier cosa que use baterías (pueden crear una CPU que tenga un consumo idéntico que el del competidor, pero con mejor rendimiento), lo cual es muy comprensible si, como dice en el enlace, el tamaño del Cortex A9 es 1/3 del de un Atom. Para que nos vamos a engañar, esa gente sabe hacer procesadores. Sus características técnicas parecen decentes; Jon Stokes dice que espera que sea "extremadamente competitivo" contra sus rivales de Intel en cuanto a rendimiento/Watio.

No todo es bonito, claro. Uno de los problemas de ARM, si tomamos sus planes imperiales en serio, es que es una plataforma de 32 bits. Eso no le supondrá un gran problema en términos de rendimiento, ARM no es tan mala plataforma de 32 bits como lo eran los x86 (en particular su patética escasez de registros, que según cuentan en ciertos programas obligaba a pasarse porcentajes de tiempo de dos cifras moviendo datos de los registros a la memoria y viceversa para "hacer hueco") pero si que les limita en su supuesta pretensión de atacar en el escritorio y en los servidores, 4GB de RAM no son tan raros hoy. Aunque por otra parte ARM podría sacarse un equivalente al PAE de x86...y sacar versiones de 64-bits, por supuesto.

Otro problema es la falta de soporte de Windows NT. El artículo cita estas palabras de un ejecutivo de ARM: "Hemos estado hablando con Microsoft y ya puede usted imaginarse sobre qué". Claro que nos lo imaginamos: Portar Windows 7 a ARM, un Windows de verdad. Ya dije aquí en el pasado que uno de los problemas de Microsoft hoy es no tener un verdadero port de Windows 7 a ARM para poder usarlo en una Cosa-Parecida-al-iPhone, eso les está dejando en desventaja respecto a Apple y Android/Palm. ¿Estaría dispuesto Microsoft a portar Windows 7 a ARM? ¿Y pedir a sus partners y a todos los desarrolladores Windows que recompilen y se adapten a ese port (o, mejor aun, que usen .NET)? Pues la verdad, no sería raro. ¿No portaron acaso Windows XP, un SO de escritorio, a Itanium? Apostar por la muerte de ARM a manos de Intel parece demasiado prematuro: No se sabe si acabará ocurriendo, si de ocurrir será una aniquilación o un arrinconamiento, y de ocurrir sería algo que tardaría mucho tiempo, del mismo modo que tardó una década y más en acabar con las grandes CPUs RISC propietarias (y no acabó con todas). En ese tiempo, no soportar ARM podría suponer un zarpazo mortal para los de Redmond. Si tuviera que apostar por ello apostaría que si, que se decidirán a portar Windows 7 (o 8, o el que venga) a ARM. Hay que arriesgarse, demonios.

Mientras tanto, pueden usar Linux. No soporta las aplicaciones que la gente quiere, se critica a Linux, pero por otra parte en un Windows portado a ARM tampoco habría montones de aplicaciones, como todas aquellas no soportadas, asi que yo tampoco veo que sea un gran problema. Pero ya sabemos como es de rara la gente...

Pongamos que se alinean los planetas, que Microsoft porta Windows a ARM, que tiene un éxito tremendo en los netbooks -probablemente lo tendrá, teniendo en cuenta que aumenta drásticamente la vida de la batería, algo fundamental en esos trastos-, que tiene cierto éxito en los servidores -clusters baratos y con un consumo ínfimo-, tal vez entonces ARM tendría una remota -remota- posibilidad de ir más allá de todo eso y plantearse la posibilidad de acabar con la dominancia de x86. No creo que ocurra, pero es divertido imaginarlo.

10 de septiembre de 2009

Lo que trae 2.6.31

Este es un resumen de las novedades más importantes de Linux 2.6.31, que acaba de salir hace unos momentos. Resumen: soporte de USB 3.0, un equivalente de FUSE para dispositivos de carácteres, mejora de interactividad del escritorio en escritorios con poca memoria, KMS para ATI Radeon, soporte para "performance counters", un detector de pérdidas de memoria, mejoras de readahead y de btrfs, nuevos drivers...

· Soporte de USB 3: Esta versión añade soporte de USB 3.0, contribuido por Sarah Sharp (Intel), y del hardware que soporta la especificación "eXtensible Host Controller Interface (xHCI) 0.95". Aun no hay hardware xHCI en el mercado, pero estos parches han sido probados en el prototipo de Fresco Logic

· CUSE (dispositivos de caracter en espacio de usuario) y OSS Proxy: CUSE es una extension de FUSE que permite implementar en espacio de usuario dispositivos de caracteres y que ha sido contribuido por Tejun Heo (SUSE).

Puede ser utilizado para muchas cosas, por ejemplo para crear un proxy que envie el audio OSS a través de ALSA o a un sistema de sonido que pueda enviar sonido sobre la red. ALSA tiene una emulación de OSS en el kernel pero desgraciadamente esta emulación está en el kernel y se encuentra detrás de la librería en espacio de usuario que multiplexa el sonido, lo cual significa que si tu tarjeta de sonido no soporta múltiples streams de audio concurrentes (la mayoría de las tarjetas modernas no lo soportan), en un momento dado solamente podrás utilizar ALSA o la emulación OSS, pero no ambas a la vez.

OSS Proxy utiliza CUSE para implementar la interfaz OSS - /dev/dsp, /dev/adsp y /dev/mixer. Desde el punto de vista de las aplicaciones, estos dispositivos son verdaderos dispositivos de carácter, y se comportan exactamente igual, asi que puede utilizarse como un sustituto de la capa de emulación OSS. La aplicación envía audio a esos dispositivos, y el Proxy OSS lo reenviará a un "esclavo". En estos momentos solamente hay un esclavo implementado (pulseaudio)

· Mejora de la interactividad bajo presión de memoria: Las páginas de memoria marcadas como PROT_EXEC son páginas que normalmente pertenecen a programas y librerías que se están ejecutando, asi que debería estar cachearse muy bien para proporcionar buenas experiencias de usuario, porque si no están bien cacheadas, las aplicaciones de escritorio sufrirán largas pausas cuando las rutas de código de la aplicación salten a una parte del código que no está cacheada en memoria y tenga que ser releida desde el disco, que es muy lento. Debido a ciertas mejoras de escalabilidad en la gestión de memoria en los últimos kernels, hay ciertos tipos de carga (comunes) que pueden causar que esas páginas PROT_EXEC sean enviadas a la lista de páginas respaldadas por sistema de archivos (las utilizadas para mapear archivos) que son inactivas y pueden ser borradas de la memoria. El resultado es un entorno de escritorio con poca interactividad: las aplicaciones empiezan a responder mal con demasiada facilidad.

En esta versión, se han aplicacion ciertas heurísticas para que sea mucho más dificil sacar a las páginas de código ejecutable de las listas de páginas activas. El resultado es una experiencia de escritorio mejorada: Benchmarks en escritorios con poca memoria miestran que el tiempo de reloj y las faltas "mayores" de memoria (cuando una aplicación salta a una parte del código que no está mapeada en la memoria) se reducen en un 50%, y los números de pswpin se reducen aproximadamente 1/3, eso significa que la interactividad de los escritorios se dobla en condiciones de presión de memoria. Benchmarks de "flusheado" de memoria en un servidor de archivos muestran que el número de faltas mayores cae de 50 a 3 durante lecturas "calientes" del caché.

· Soporte de Mode Setting para ATI Radeon: En esta versión se añade soporte de Kernel Mode Setting (KMS) para ATI Radeon. El hardware soportado es R1XX,R2XX,R3XX,R4XX,R5XX (hasta la X1950). Se está trabajando para proporcionar soporte para R6XX, R7XX y hardware más moderno (radeon de HD2XXX a HD4XXX).

· Performance counters: El subsistema de Contadores de Rendimiento implementa una abstracción de una serie de registros dedicados a medir el rendimiento que están disponibles en la mayoría de CPUs modernas. Miden el número de eventos como: instrucciones ejecutadas, "cpumisses", errores de predicción en las instrucciones condicionales...sin enlentecer el kernel o las aplicaciones. Estos registros tambien pueden generar una interrupción cuando se pasa de cierto número de eventos - y pueden por tanto utilizarse para analizar el código que se ejecuta en esa CPU. En esta versión, se añade soporte para x86, PPC y soporte parcial para S390 y FRV.

No se espera que los usuarios utilizen ellos mismos la API. En lugar de ello, se ha escrito una poderosa herramienta de análisis: "perf", que está disponible en el directorio tools/perf.

perf soporta varios modos de operacion, como "perf top", que muestra una interfaz semejante a la del comando "top", y que puede restringirse a cualquier conjunto de eventos, procesos o CPU. Existe tambien "perf record", que almacena el registro de un análisis en un archivo, y "perf report", que lee el registro y lo muestra en pantalla, o "perf annotate", que muestra la lista de eventos soportados por el hardware, y "perf stat", que ejecuta un comando y muestra sus estadísticas de rendimiento en la pantalla. Toda la documentación y las páginas man están disponibles en el subdirectorio "Documentation". Algunos ejemplos:

$ ./perf stat -r 3 -- echo -n

Performance counter stats for 'echo -n' (3 runs):

2.337404  task-clock-msecs         #      0.566 CPUs    ( +-   1.704% )
     1  context-switches         #      0.000 M/sec   ( +-   0.000% )
     0  CPU-migrations           #      0.000 M/sec   ( +-   0.000% )
   184  page-faults              #      0.079 M/sec   ( +-   0.000% )
4319963  cycles                   #   1848.188 M/sec   ( +-   1.615% )
5024608  instructions             #      1.163 IPC     ( +-   0.722% )
 73278  cache-references         #     31.350 M/sec   ( +-   1.636% )
  2019  cache-misses             #      0.864 M/sec   ( +-   6.535% )

0.004126139  seconds time elapsed   ( +-  24.603% )


$ perf report -s comm,dso,symbol -C firefox -d /usr/lib64/xulrunner-1.9.1/libxul.so | grep :: | head
2.21%  [.] nsDeque::Push(void*)
1.78%  [.] GraphWalker::DoWalk(nsDeque&)
1.30%  [.] GCGraphBuilder::AddNode(void*, nsCycleCollectionParticipant*)
1.27%  [.] XPCWrappedNative::CallMethod(XPCCallContext&, XPCWrappedNative::CallMode)
1.18%  [.] imgContainer::DrawFrameTo(gfxIImageFrame*, gfxIImageFrame*, nsRect&)
1.13%  [.] nsDeque::PopFront()
1.11%  [.] nsGlobalWindow::RunTimeout(nsTimeout*)
0.97%  [.] nsXPConnect::Traverse(void*, nsCycleCollectionTraversalCallback&)
0.95%  [.] nsJSEventListener::cycleCollection::Traverse(void*, nsCycleCollectionTraversalCallback&)
0.95%  [.] nsCOMPtr_base::~nsCOMPtr_base()

· Soporte de IEE 802.15.4 (Low-Rate Wireless Personal Area Networks): El estándar IEEE 802.15.4 define una red inalámbrica de área personal de corto alcance, bajos ratios de transferencia, bajo consumo de energía y poca complejidad. Ha sido diseñada para organizar redes de sensores, interruptores y otros dispositivos automatizadores. El máximo ratio de transferencia permitido es 250 kb/s y el espacio de operaciones es de alrededor de 10m.

· Soporte de Gcov: Esta versión permite la utilización de Gcov, una herramienta de GCC utilizara para analizar ciertos aspectos del código, con el kernel. Gcov es útil para depurar (¿se ha llegado a este código alguna vez?), mejora de tests (¿como cambio mi test para cubrir estas líneas?), minimizar configuraciones del kernel (¿necesito esta opción si el código asociado no se ejecuta nunca?) y otras cosas.

· Kmemcheck: Kmemcheck es una herramienta de depuración. En concreto, es un comprobador dinámico que detecta y advierte sobre memoria no inicializada. Los programadores de espacio de usuario puede que conozcan el memcheck de Valgrind. La principal diferencia entre kmemcheck y memcheck es que memcheck solamente funciona para programas de espacio de usuario, y kmemcheck solo funciona para el kernel.

Activar kmemcheck en un kernel lo enlentece hasta el punto que la máquina no será usable para cargas comunes, como por ejemplo un escritorio interactivo. kmemcheck tambien hace que el kernel use el doble de memoria de lo normal. Por esta razón, kmemcheck es solamente una opción de depuración.

· Kmemleak: Kmemleak detecta posibles pérdidas de memoria de una manera similar a este recolector de basura, con la diferencia de que los objetos huérfanos no son liberados. En vez de eso, un thread del kernel escanea la memoria cada 10 minutos (por defecto) y muestra cualquier nuevo objeto no referenciado en /sys/kernel/debug/kmemleak y advierte de ello en dmesg. Un método similar es utilizado por la herramienta Valgrind (memcheck --leak-check) para detectar pérdidas de memoria en aplicaciones en espacio de usuario.

· Fsnotify: Fsnotify es un subsistema utilizado para notificaciones del sistema de archivos. Fsnotify por si solo no tiene ninguna API a espacio de usuario, proporciona la base para implementar otros sistemas de notificación como dnotify, inotify y fanotify (este último será incluido en futuras versiones). De hecho, en esta version dnotify e inotify han sido reescritos sobre Fsnotify, eliminando al mismo tiempo el horrible y complejo código que utilizaban esos sistemas. Fsnotify proporciona un mecanismo para que "grupos" se registren para ser notificados de una serie de eventos del sistema de archivos a los que envía dichos eventos, y el bloqueo es mucho más sencillo. Fsnotify tiene otros beneficios, como reducir el tamaño de la estructura que almacena información de un inodo.

· Soporte preliminar para clientes NFS 4.1: 2.6.30 Añadió cierto soporte orientado a desarrolladores de NFS 4.1. Esta versión añade soporte opcional para los borradores de la versión 4.1 en el cliente NFS del kernel.

· Mejoras de readahead: Esta versión incluye un algoritmo de readahead "basado en contexto". El actual algoritmo detecta lecturas entremezcladas de un modo pasivo, el algoritmo nuevo garantiza descubrir la secuencialidad sin importar como estén entremezclados los streams. Los beneficiarios de este algoritmo son las lecturas estrictamente entremezcladas y los procesos con ES cooperativa (por ejemplo, NFS y SCST). Benchmarks de SCST muestran mejoras del 6%~40% en varios casos y consiguen igual rendimiento en otros.

Tambien hay algunas mejoras al readahead de memoria mapeada. En un escritorio NFS-root, el readahead de mmap redujo las faltas mayores de memoria 1/3 sin sobrecargas notables, el IO llevado a cabo por mmap puede reducirse en 1/4.

Esto es todo. Hay otras mejoras, como un driver para dispositivos Intel Wireless Multicomm 3200, mejoras notables de btrfs, IPv4 sobre Firewire...para ver la lista completa, aquí.

2 de septiembre de 2009

¿Grand Central Dispatch, retorno de M:N?

Como es sabido, a grandes rasgos hay dos maneras de implementar threads en los sistemas operativos, 1:1 y M:N, durante años se mantuvo que M:N era lo más apropiado, sin embargo 1:1 acabó ganando la batalla. Solaris, que era uno de los mayores representantes de M:N, hizo que en Solaris 9 cambiara por defecto a 1:1 por la simple razón de que era más rápido y tenía mucho menos código, Linux 2.6 optó tambien por 1:1 en su NTPL. Con el tiempo, NetBSD y FreeBSD, que se resistían, tambien se pasaron a 1:1.

En OS X 10.6 Apple ha implementado una serie de mecanismos con el propósito de facilitar a los programadores la utilización de todos los cores y procesadores de los sistemas modernos. Es muy recomendable leer la parte del análisis de OS X 10.6 de Arstechnica que habla sobre este tema, concretamente de la página 10 a la 14. Esos mecanismos, que son una de las cosas más interesantes que se han hecho en OS X (no faltará quien diga que eso de gestionar threads es viejo y que no tiene nada de interesante, o que me cite a BeOS sin pararse a leer la parte del artículo donde explica claramente por qué lo que ha hecho Apple es mucho más práctico y eficiente que el "pervasive multithreading"). Todo ello se basa en unas extensiones a C y en una especie de gestor de threads llamado "Grand Central Dispatch".

Este "dispatcher" se encarga de mantener unas listas de los "bloques" que las aplicaciones crean gracias a la ya referida extensión de C, y repartirlos entre unos pocos threads creados a tal efecto. Se podría decir que huele un poco a M:N, es decir, un proceso que ofrece su contexto de ejecución a threads que son controlados por una especie de gestor de procesos (Grand Central Dispatch) que funciona en espacio de usuario...¿o no?

En cierto modo, a primera vista hay analogías, pero mirado en detalle no creo que se pueda afirmar que tiene que ver con M:N. Fundamentalmente porque M:N es un diseño para implementar threads, mientras que GCD es un sistema que gestiona bloques. Aunque estos bloques podrían compararse con threads no parece apropiado hacerlo. Pretenden ser más bien una especie de subunidades de trabajo, mientras que los threads son más bien subprocesos (si alguien tiene opinión al respecto sería interesante). Se podría argumentar que un thread puede utilizarse tambien para crear "subunidades de trabajo" en un programa, pero tambien puede no serlo. Un bloque hace su trabajo y desaparece, un thread puede durar tanto como el proceso que lo creo. De ahí que GCD no sea (y quizás ni tenga) en realidad un verdadero "gestor de procesos", porque no reasigna el tiempo de ejecución de un bloque-proceso a otro dependiendo de diferentes variables, como haría M:N, tan solo se limita a asignar un bloque a un thread y esperar a que termine (aun está por ver/documentar como gestiona GCD un bloque que se queda en un loop). Pero todo este tema de GCD es muy nuevo, y habrá que ver como evoluciona con los años, y como lo imitan en otros SOs que reimplementen la idea.