A lista encadeada do kernel Linux e a arte de fazer o impossível em C
Todo mundo aprende lista encadeada em algum momento.
Normalmente ela aparece mais ou menos assim:
struct node {
int value;
struct node *next;
};
Cada nó guarda um valor e um ponteiro para o próximo nó. Se for uma lista duplamente encadeada, guarda também um ponteiro para o anterior:
struct node {
int value;
struct node *next;
struct node *prev;
};
A ideia é simples: diferente de um array, os elementos não precisam estar contíguos na memória. Cada elemento sabe onde está o próximo. Isso permite inserir e remover elementos sem realocar um bloco inteiro de memória.
Até aqui, nada demais. O problema começa quando você quer fazer isso em C de forma genérica. Porque C não tem generics.
Em C++, você faria algo como std::list<T>. Em Rust, LinkedList<T>. Em Java, LinkedList<T>. Em C, você olha para o teto, respira fundo e pensa em uma gambiarra.
A forma tradicional é colocar um void * dentro do nó:
struct list_node {
void *data;
struct list_node *next;
struct list_node *prev;
};
Funciona.
Mas agora você perdeu o tipo. A lista aceita qualquer coisa. Um struct user, um struct file, um struct banana, um ponteiro errado, um cast mentiroso, a esperança, o desespero. Tudo entra. O compilador não consegue te proteger de nada.
Outra alternativa é usar macros para gerar uma lista para cada tipo:
#define DECLARE_LIST(type) \
struct type##_node { \
type data; \
struct type##_node *next; \
struct type##_node *prev; \
};
Também funciona.
Mas agora você está programando em C e em uma segunda linguagem secreta feita de macros. Todas as funções que operam na lista também precisam ser macros. Impossível de debuggar e as mensagens de erro viram poesia abstrata.
O kernel Linux precisava de algo melhor.
O kernel usa listas ligadas para tudo. Lista de tarefas do escalonador, lista módulos carregados, lista dispositivos registrados, lista de conexões de rede. A lista ligada é a estrutura de dados mais onipresente do kernel. Justamente por isso, o kernel não reimplementa uma lista para cada subsistema: existe uma implementação oficial em <linux/list.h> e todo mundo é fortemente encorajado a usar.
A solução é uma das coisas mais bonitas da programação em C. A lista do kernel não guarda o dado. O dado guarda a lista. A estrutura central é absurdamente simples:
struct list_head {
struct list_head *next;
struct list_head *prev;
};
Só isso. Não tem void *data. Não tem int value. Não tem payload. Parece inútil. Mas aí vem o truque. Em vez de fazer isso:
struct fox {
unsigned long weight;
struct fox *next;
struct fox *prev;
};
O kernel faz isso:
struct fox {
unsigned long weight;
bool is_fantastic;
struct list_head list;
};
Agora o código genérico da lista só precisa saber manipular struct list_head. Ele não precisa saber se aquilo está dentro de uma struct fox, struct task_struct, struct inode, struct file, ou qualquer outro objeto do kernel.
Para adicionar uma raposa na lista:
struct fox red_fox;
struct list_head fox_list
list_add(&red_fox.list, &fox_list);
Repare que a função lista recebe apenas o endereço do campo list.
Mas aí surge a pergunta: se a função recebe um struct list_head *, como volto para a struct fox * original? A resposta é o belíssima GAMBIARRA chamada container_of. A versão clássica é mais ou menos assim:
#define offsetof(TYPE, MEMBER) ((size_t)&((TYPE *)0)->MEMBER) \
#define container_of(ptr, type, member) ({ \
const typeof(((type *)0)->member) *__mptr = (ptr); \
(type *)((char *)__mptr - offsetof(type, member)); \
})
Parece bruxaria, mas a ideia é simples.
Imagine esta estrutura:
struct fox {
unsigned long weight;
bool is_fantastic;
struct list_head list;
};
O campo list está em algum offset fixo dentro de struct fox.
Algo como:
início da struct fox
|
v
+----------------+
| weight |
+----------------+
| is_fantastic |
+----------------+
| list | <- você tem este endereço
+----------------+
Se você sabe o endereço de list e sabe quantos bytes list está distante do começo de struct fox, basta subtrair esse offset.
endereço da struct fox = endereço do campo list - offset(list)
É isso.
O kernel pega o endereço de um membro e reconstrói o endereço da estrutura que contém aquele membro.
O detalhe genial é que o offset de um campo dentro de uma struct é conhecido em tempo de compilação. O compilador sabe onde cada campo mora. O ABI sabe. A máquina sabe. O programador comum só não costuma pensar nisso.
E aqui mora a beleza da coisa.
A lista é genérica sem usar void *. Ela é reutilizável sem gerar uma lista nova para cada tipo. Ela mantém parte da checagem de tipo porque o macro usa typeof para verificar se o ponteiro passado combina com o tipo do membro esperado.
Isso é muito mais do que uma lista encadeada. É uma aula sobre o que significa conhecer uma linguagem de verdade. Porque o programador médio olha para C e diz:
“C não tem generics.”
E ele está certo.
Mas o programador do kernel olha para C e diz:
“C não tem generics, mas tem layout de memória, ponteiros, offset de campos, macros, extensões do compilador e coragem moral duvidosa.”
E também está certo.
Essa é a diferença entre saber a sintaxe de uma linguagem e entender de verdade o que existe por baixo dela. Muita coisa que parece impossível em uma linguagem é impossível apenas no nível superficial da linguagem. Quando você desce um nível, começam a aparecer portas secretas. Isso não significa que você deve sair usando container_of no sistema de cadastro da padaria.
A moral não é “faça bruxaria em C”. A moral é: fundamentos importam. Estruturas de dados importam. Layout de memória importa. Saber o que a máquina realmente está fazendo importa. Porque, de vez em quando, esse conhecimento permite construir uma solução que parece impossível para quem só conhece a superfície. A lista encadeada do Linux é genial porque mostra uma forma de pensar. O tipo de pensamento que olha para uma limitação da linguagem e pergunta:
“Tá. Mas isso é uma limitação semântica ou só falta de sintaxe?”
É nesse pequeno intervalo que mora boa parte da engenharia de software de verdade.