Listas Circulares en Linux

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.

|filename|images/0004-listas-circulares-linux/lista-simple.png

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.

|filename|images/0004-listas-circulares-linux/lista-circular.png

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:

  1. 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.
  2. A continuación, hace lo propio con el valor 0.
  3. 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.
  4. 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).

|filename|images/0004-listas-circulares-linux/struct.png

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 :)