En este post vamos a ver uno de esos pequeños detalles que te hacen esbozar una
sonrisa cuando los ves. Código que parece que literalmente, hace magia. Vamos a
analizar una pequeñísima porción del código fuente de Linux.
A lo largo de las miles de lineas de código que tiene Linux se usan
continuamente listas circulares. En el principio de los tiempos, cada
programador se hacía su propia implementación, haciendo que el código fuese
poco mantenible.
Hasta que llegado cierto momento en el desarrollo de la v2.1 se decidió
realizar una implementación genérica, y portar todo el código existente a este
nuevo sistema. Estas listas se usan actualmente en todo el kernel (lista de
procesos, drivers, sistemas de ficheros soportados, ...). Pero antes de ver por
qué el diseño que usan en Linux es tan bonito, hagamos una pequeña introducción
sobre lo que es una lista circular, y como se suelen implementar.
Si todo esto ya te lo sabes, puedes saltar a la siguiente sección.
Listas Circulares
Las listas circulares son una de las estructuras de datos más básicas que
existen. Consisten en una sucesión de elementos (una lista normal y corriente),
en la que el último elemento apunta al primero, de tal manera que se puede
recorrer de forma circular.
Dentro de estas listas circulares, podemos subdividirlas mediante muchos
criterios. Uno de los más usados es el número de enlaces que tiene. Las que son
enlazadas simples (permiten recorrerse solo en un orden), y las que son
doblemente enlazadas (a partir de un elemento, podemos visitar al anterior y al
siguiente).
A diferencia de los arrays estáticos (como pudiese ser uno de C), nuestra lista
circular no necesita saber cuantos elementos va a tener en tiempo de
compilación, debido a que gracias al tratamiento de punteros y a la memoria
dinámica del sistema, podremos ir variando su tamaño a nuestro antojo.
Típicamente las listas enlazadas se suelen implementar mediante un struct que
contiene, aparte del elemento en cuestión, un puntero a una estructura de su
mismo tipo, mediante el cual apuntar al elemento siguiente.
En caso de que quisiésemos implementar una lista doblemente enlazada, sólo
tendríamos que añadir un puntero más, en este caso apuntado al elemento
anterior.
struct nodo {
int elemento;
struct nodo * siguiente;
};
Así de simple. Para usar esta lista, nos bastaría con crear un par de elementos
e iniciar sus atributos de forma correcta.
Como con una lista se suelen realizar tareas muy comunes (añadir, eliminar,
iterar, ...) lo lógico sería crear un par de funciones que nos facilitasen la
tarea.
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
typedef struct nodo {
int elemento;
struct nodo * siguiente;
} nodo;
int add_nodo(nodo **l, int e) {
nodo *nuevo = (nodo *) malloc(sizeof(nodo));
if (!nuevo)
return -ENOMEM;
nuevo->elemento = e;
nuevo->siguiente = *l;
*l = nuevo;
return 0;
}
void imprimir_lista(nodo *l) {
printf("Los elementos de la lista son: ");
while (l != NULL) {
printf("%d, ", l->elemento);
l = l->siguiente;
}
printf("\n");
}
int main(void) {
nodo *l1 = NULL;
add_nodo(&l1, 10);
add_nodo(&l1, 20);
add_nodo(&l1, 50);
imprimir_lista(l1);
// No estamos liberando la memoria solicitada... ¬¬
return 0;
}
En este código podemos ver como tenemos dos funciones (es un ejemplo muy
escueto).
La primera, add_nodo, nos sirve para añadir una elemento a la lista circular.
Este elemento se reserva en el heap del sistema, usando para ello la llamada
malloc(3). Una vez reservada la memoria,
se introduce delante del nodo que le pasamos como parámetro.
La segunda, imprimir_lista, simplemente itera a partir de un nodo
recorriéndolos todos hasta llegar al pasado como parámetro de nuevo.
Esta implementación, que es muy parecida a la que se sigue en muchísimos casos,
tiene como problema que no se puede generalizar la solución para otros tipos de
datos.
Es decir, en nuestro anterior ejemplo, los elementos que guardamos son enteros
(en la estructura que identifica nuestra lista podemos ver como el elemento es
un int). Si queremos crear otra lista con otro tipo de elementos, tendremos
que implementar un nuevo struct (con otro nuevo set de funciones para añadir,
eliminar, iterar...).
Como podéis ver, este es un trabajo muy repetitivo, que al final hace que se
repita muchísimo código, con pequeñas diferencias.
Formas de solucionar esto hay varias.
Por ejemplo, podríamos usar punteros genéricos, lo que nos permite guardar en
la lista cualquier tipo de objeto.
Básicamente consiste en guardar un puntero a algo (void*), de tal manera
que al añadir un elemento en la lista no guardaremos el elemento en sí, si no
un puntero al mismo. Debido a que un puntero siempre ocupa lo mismo
(independientemente del tipo del dato apuntado), este sistema nos permitiría
guardar cualquier tipo de dato.
Esta solución, sin embargo, aunque arregla este problema, crea otros tantos,
como que hay que castear el objeto antes de poder usarlo, o que al pasar a
guardar un puntero del objeto, en vez del objeto en si, tenemos que tener
cuidado con que a lo largo de la vida de la lista ese objeto no deje de existir
(porque fue creado en la pila de otra función por ejemplo).
La solución de Linux
Linux implementa una lista doblemente enlazada circular.
Aparte, no existe el concepto de primer y último nodo. No le dan ningún tipo de
importancia a esta información. Facilitan formas de recorrer la lista entera,
independientemente de que nodo cojamos como cabecera de la lista.
Pero lo que hace especial a la solución de Linux es que pasa por embeber la
propia lista dentro de nuestra estructura... y no al revés; es decir, le dan la
vuelta a la tortilla.
En vez de tener nuestro elemento guardado dentro del struct, lo que se hace es
meter la estructura que representa a un nodo, dentro de nuestro propio dato.
Así explicado suena un poco raro, así que pasemos a ver código real. El
struct que representa estas listas se llama list_head. Y si miramos como
está implementado veremos que tiene únicamente dos elementos:
struct list_head {
struct list_head *next, *prev;
};
Un puntero al siguiente elemento, y otro al anterior (como vimos
anteriormente).
Para usar estas listas únicamente tendremos que insertar un elemento struct
list_head en nuestra propia estructura. Vamos a realizar un ejemplo parecido
al anterior, pero ahora usando las listas circulares de Linux.
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include "list.h"
typedef struct {
struct list_head lista;
int elemento;
} nodo;
int main(void) {
struct list_head *iter;
nodo n_head, *aux;
// Inicializamos la lista
INIT_LIST_HEAD(&n_head.lista);
for (i=0; i<5; i++) {
aux = (nodo*) malloc(sizeof(nodo));
if (!aux)
return -ENOMEM;
aux->elemento = i;
// Añadimos un elemento más a la lista
list_add(&aux->lista, &n_head.lista);
}
// Recorremos todos los elementos
printf("Los elementos de la lista son: ");
list_for_each(iter, &n_head.lista) {
// Extraemos nuestro struct de la lista
aux = list_entry(iter, nodo, lista);
printf("%d, ", aux->elemento);
}
printf("\n");
// Volvemos a olvidarnos de liberar la memoria
return 0;
}
Es un ejemplo muy sencillo en el que podemos ver la potencia de la API de estas
listas. Como podemos ver, tenemos una estructura nodo, que aparte de
guardar nuestro elemento (igual que en el caso anterior), contiene un elemento
de tipo struct list_head, que será el que guarde la referencia a nuestra
lista circular.
Mencionar, que se pueden insertar tantos list_head como se quiera; es
decir, que un mismo elemento puede pertenecer a infinitas listas circulares.
En este caso, creamos un nodo que usaremos como cabecera de la lista (aunque
como ya dijimos, para estas listas todos los nodos tienen la misma
importancia), y a partir de él, inicializamos la lista con la macro
INIT_LIST_HEAD.
A continuación, con list_add, añadimos un total de 5 elementos. Esta macro
recibe dos parámetros. Como primer parámetro, el nodo a insertar. Y como
segundo, el nodo tras el cual queremos insertar el elemento.
Y por último, imprimimos los números insertados. Especial atención a las dos
macros usadas aquí. list_for_each, que se expande a un bucle for normal
y corriente (con prefetching), que a partir del pivote usado (el segundo
parámetro) empieza a recorrer todos los nodos de la lista (guardándolos en el
iterador, el primer parámetro) hasta llegar al nodo pivote de nuevo.
Y list_entry, que es la macro que hace realmente la magia (la analizaremos
con más calma después). Gracias a esta macro conseguiremos extraer el elemento
(nuestro struct nodo), a partir del list_head que tenemos guardado en
la variable iter.
La API de estas listas es muy rica, proporcionando funciones (macros realmente)
para insertar elementos antes o después de nuestro pivote, para recorrerlas del
derecho o del revés, para activar o desactivar el prefetching, ...
Es un módulo a usar siempre que necesitemos listas, independientemente de que
estemos desarrollando para el kernel o no (todo el código está contenido en un
fichero que no tiene dependencias externas).
¿Y cómo demonios hace eso?
Pasemos a ver un poco el código del kernel. La implementación de las listas
circulares la podemos ver en el fichero include/linux/list.h
Merece la pena leer todo el código de la librería, llamando poderosamente la
atención una cosa. ¿Cómo consigue la lista devolver la estructura contenedora a
partir de la referencia a su propio campo? Es decir, y usando nuestro ejemplo
anterior... ¿Como puede C, a partir de una referencia al struct list_head,
sacar el struct nodo en el cual está contenido?
La encargada de ello es la función list_entry, que a parte de que resulta
ser una macro, tiene un código muy sencillo. Únicamente llama a la macro
container_of.
Esta macro es la que realiza toda la magia (no solo se usa para las listas
circulares), y podemos encontrarla desarrollada en el fichero include/linux/kernel.h.
Recibe tres parámetros (los mismos que list_entry):
- ptr
- El puntero al campo de la estructura.
- type
- El tipo de estructura que queremos sacar (a la cual pertenece el campo
anterior)
- member
- El nombre del campo que estamos pasando desde el primer parámetro.
Analicemos paso a paso el código de la macro container_of.
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
Es muy poco código (apenas dos líneas), pero veremos como condensa mucha
información.
Para empezar, la estructura principal es bastante rara. Contiene dos
instrucciones rodeadas mediante un par de paréntesis y llaves. Para entender que
es esta estructura, vamos a poner un ejemplo muy simple
#include <stdio.h>
int main(void) {
int num = ({int i = 0; i+100;});
printf("%d\n", num);
return 0;
}
Como podemos ver, en la línea 4 se ejecutan dos instrucciones, y finalmente el
printf imprime por pantalla el valor 100. Pues esta extraña estructura no es
más que una extensión de GCC (sí, el código de Linux no es, por lo general,
portable a otros compiladores), llamada Statement Expression
Básicamente, permite ejecutar varias expresiones como si fuesen una sola. La
última de la lista, que deberá terminar en un punto y coma, será el valor que
devolverá la expresión.
En el ejemplo anterior, podemos ver como inicializamos una variable llamada i,
y a continuación le sumamos a su valor (que es 0), el número 100. El resultado
de esta operación es la que se devolverá al entero num. Es decir, que valdrá
100.
Pues análogamente, nuestra macro container_of contiene dos instrucciones con
este formato, de tal manera que en la primera instrucción creamos una variable,
y en la segunda operamos con ella, devolviendo como valor de la expresión el
resultado de esta operación.
Pero antes de ver que operación se hace concretamente sigamos viendo con calma
el código de la macro, en concreto podemos ver como se hace uso de otras dos
funciones: typeof y offsetof.
La primera, typeof, no tiene mucho misterio, es otra extensión de GCC que en base
a una variable, nos devuelve el tipo del que es. De esta manera podremos crear
una variable del mismo tipo que otra, aunque no sepamos a priori de que tipo es
la primera.
La segunda, offsetof, es una macro definida en el estándar ANSI C, pero que
el kernel redeclara. Esto es debido a que esta macro realiza operaciones que no
están aseguradas por el estándar de C, si no que el resultado puede variar de un
compilador a otro.
Por ello, la mayor parte de los compiladores definen una función (por lo general
llamada __builtin_offsetof). Linux simplemente comprueba si tal función
existe; y en caso afirmativo, la usa sobre la predeterminada.
Lo que hace esta macro es devolver el offset (la distancia) que separa un campo
de un struct, del inicio del mismo.
El código suele ser parecido al siguiente:
#define offsetof(st, m) \
((size_t) ( (char *)&((st *)(0))->m - (char *)0 ))
Esta macro realiza las siguientes operaciones:
- Castea el elemento 0 (NULL), a un puntero del tipo de estructura requerido,
y a continuación accede al elemento especificado. Por último, obtiene la
dirección. Es decir, devuelve el número de bytes que hay entre el inicio de la
estructura (que está en la posición 0 en este caso), y el elemento que
queremos devolver.
- A continuación, hace lo propio con el valor 0.
- Castea ambos elementos a punteros a carácter. Esto es debido a que el estándar
de C asegura que un carácter ocupa 1 Byte.
- Por último, resta ambos valores, obteniendo el offset del campo que queremos
(el número de bytes que lo separa del inicio de la estructura).
Con estas aclaraciones ya estamos listos para entender que hace la macro
container_of. Vamos a volver a poner el código para tenerlo más cerquita.
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
Como vemos, concatena dos expresiones en una.
La primera crea un puntero a una variable (llamada __mptr) de la
estructura interna, list_head en nuestro ejemplo. Para ello, accede al
miembro (lista en nuestro caso), y a continuación usa typeof para crear
una nueva variable de este tipo. A continuación la inicializa con el valor del
primer parámetro, que recordad, en el caso de las listas circulares, es el
elemento sobre el que estamos iterando.
Es decir, si en cierto momento de la ejecución de nuestro código anterior
llamamos a la macro container_of(&nodo1, nodo, lista) pasándole como
primer parámetro la dirección del nodo1, la primera línea lo que hará será
crear una variable de tipo list_head, que apunte al elemento lista de
ese nodo1. Esa variable, a grandes rasgos, guarda la dirección de memoria
donde está el elemento list_head de nodo1 (un puntero no es más que una
dirección, un numerito).
La segunda, obtiene el offset del campo list_head en nuestra estructura (con
la macro offsetof tal como explicamos anteriormente), y a continuación, le
resta este valor a la dirección de la variable creada anteriormente. Por
último, castea este valor a un puntero a nuestro tipo de estructura.
Y el valor devuelto es el resultado de esta última operación, que no es más que
la dirección de memoria donde empieza nuestra estructura nodo.
Es decir, que, poniendo números concretos, la primera línea de esta macro
devuelve la dirección donde está la estructura contenida (la 0x200 por
ejemplo). Y la segunda, obtiene el offset de esta estructura contenida, sobre la
exterior (un offset de 0x4 bytes por ejemplo, que es lo que suele ocupar un
int).
Para terminar, si queremos acceder a la estructura exterior, no tendremos más
que restar 0x4 a 0x200, dando 0x1FC, que es la dirección de memoria donde
está la estructura exterior.
Y eso es todo... como dije al principio, auténtica magia :)
