Listas enlazadas del kernel

El kernel usa listas enlazadas por todas partes: procesos, archivos abiertos, páginas de memoria, drivers. Pero no son las listas que conoces: son intrusivas, con un diseño ingenioso basado en el container_of del nivel 2.2. Dominarlas es dominar la estructura de datos más común del kernel.

• Las listas intrusivas y struct list_head.
• Añadir, quitar y recorrer.
• list_for_each_entry y container_of.
• Por qué el diseño es genial.

Listas intrusivas: al revés de lo normal

En una lista normal, el nodo contiene tus datos. En el kernel es al revés: tus datos contienen el nodo. Embebes un struct list_head en tu struct:

#include <linux/list.h>struct tarea {    int id;    char nombre[32];    struct list_head lista;    // el nodo va DENTRO de tus datos};static LIST_HEAD(mi_lista);    // la cabeza de la lista

Añadir y quitar

struct tarea *t = kmalloc(sizeof(*t), GFP_KERNEL);t->id = 1;list_add(&t->lista, &mi_lista);        // añadir al principiolist_add_tail(&t->lista, &mi_lista);   // o al finallist_del(&t->lista);                    // quitar de la lista

Pasas siempre la dirección del campo list_head, no del struct.

Recorrer: list_for_each_entry

Aquí entra la magia del nivel 2.2. Al recorrer, tienes punteros a los campos list_head; list_for_each_entry usa container_of por debajo para darte de vuelta tu struct completo:

struct tarea *t;list_for_each_entry(t, &mi_lista, lista) {    // 't' es un 'struct tarea *' completo, recuperado con container_of    printk(KERN_INFO "tarea %d: %s\n", t->id, t->nombre);}// para borrar mientras recorres, usa la variante _safe:struct tarea *t, *tmp;list_for_each_entry_safe(t, tmp, &mi_lista, lista) {    list_del(&t->lista);    kfree(t);}

Por qué las listas intrusivas son superiores

El diseño intrusivo del kernel resuelve tres problemas de las listas normales de golpe. Uno: cero asignaciones extra — el nodo ya vive dentro de tu struct, no hay que reservar un contenedor aparte por elemento (menos malloc, menos fragmentación, nivel 13). Dos: un mismo objeto puede estar en varias listas a la vez, embebiendo varios list_head (una tarea en la lista global y en la lista de su proceso, con dos campos distintos) — imposible con listas que contienen los datos. Tres: es genérico y type-safe en C puro, sin macros de plantilla ni void* peligrosos, gracias a container_of. Este patrón —composición por embebido + container_of para volver al contenedor— es una de las técnicas de ingeniería más elegantes del kernel, y una vez la ves, la reconoces por todas partes: rbtrees, colas de espera, hash tables, todo el kernel enlaza objetos así. Es C llevado a su máxima expresión de diseño.

Enlaza objetos como el kernel

1. Define un struct con un struct list_head embebido y una LIST_HEAD.
2. Añade varios elementos con list_add_tail (reservados con kmalloc).
3. Recórrelos con list_for_each_entry e imprímelos.
4. Bórralos todos con list_for_each_entry_safe, liberando cada uno.
5. Investiga: ¿cómo pondrías un mismo objeto en dos listas a la vez?