Intrusive Linked Lists: Embedding Pointers for Efficient Data Management

1. The "Intrusive" Philosophy: What and Why?

A standard, or non-intrusive, linked list typically involves two separate memory allocations for each item you want to add: one for your data (PacketBuffer) and another for the list node (ListNode) that contains pointers to the next and previous nodes, plus a pointer to your data.

An intrusive linked list takes a different approach. Instead of a separate node, the pointers required for linking (next and prev) are embedded directly inside the data structure you want to link.

To explore this concept and its advantages, please study the following article.

As the article highlights, the primary benefits are:

• Reduced Memory Allocations: You only need one allocation for your object, as the list pointers are included. This is critical in embedded systems where dynamic memory allocation might be restricted or undesirable.
• Improved Cache Performance: The list pointers and the data reside in the same block of memory. When you access a list node, the associated data is often pulled into the CPU cache along with it, reducing the chance of a cache miss compared to the double-pointer-chase of a non-intrusive list.

For a broader perspective on why this pattern is so valued in systems programming, especially in environments without standard libraries or allocators, the following video offers excellent insights.

2. The Linux Kernel Model: A Battle-Tested Design

Rather than inventing our own system, we will adopt the highly optimized and widely used intrusive linked list implementation from the Linux kernel. It is elegant, efficient, and serves as a gold standard.

The core of this design is a simple struct list_head.

struct list_head {
    struct list_head *next, *prev;
};

That's it. This small struct contains the forward and backward pointers that will form our doubly-linked, circular list. The "intrusive" part is that we embed this struct directly into our PacketBuffer from the previous lesson.

// From the previous lesson
typedef struct {
    unsigned char* head;
    unsigned char* data;
    unsigned char* tail;
    unsigned char* end;
    // NEW: The embedded list node for linking PacketBuffers together
    struct list_head list; 
} PacketBuffer;

With this, every PacketBuffer is now also a node that can be part of any number of different lists (though only one at a time), without needing any extra memory allocation.

3. Implementing the Core List Operations

Let's build the functions and macros to manage our list. We'll be creating a simplified version of the API found in <linux/list.h>.

Initializing a List Head

A list is represented by a standalone struct list_head, often called the "head" or "anchor." An empty list is one where the head's next and prev pointers point to itself.

// Initializes a list head to represent an empty list
static inline void INIT_LIST_HEAD(struct list_head *list) {
    list->next = list;
    list->prev = list;
}

// A macro for static initialization
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name)

We can now declare our packet queues:

// Example queues for managing packets
LIST_HEAD(free_packet_list); // A list of available, unused packets
LIST_HEAD(transmit_queue);   // A list of packets waiting to be sent

Adding and Deleting Nodes

The logic for adding a node involves wiring up the next and prev pointers of the new node and its neighbors. We'll create a private helper __list_add to do the core work.

// Private helper: inserts a new node between two known neighbors.
static inline void __list_add(struct list_head *new_node,
                            struct list_head *prev,
                            struct list_head *next) {
    next->prev = new_node;
    new_node->next = next;
    new_node->prev = prev;
    prev->next = new_node;
}

// Adds a new node right after the list head (for stack-like behavior)
static inline void list_add(struct list_head *new_node, struct list_head *head) {
    __list_add(new_node, head, head->next);
}

// Adds a new node right before the list head (for queue-like behavior)
static inline void list_add_tail(struct list_head *new_node, struct list_head *head) {
    __list_add(new_node, head->prev, head);
}

// Private helper: connects two neighbors, effectively removing a node.
static inline void __list_del(struct list_head *prev, struct list_head *next) {
    next->prev = prev;
    prev->next = next;
}

// Removes a node from its list.
static inline void list_del(struct list_head *entry) {
    __list_del(entry->prev, entry->next);
    // "Poison" the pointers to help catch use-after-delete bugs.
    entry->next = NULL; 
    entry->prev = NULL;
}

Getting from the Node to the Container

This is the most ingenious part of the system. When we iterate the list, we get a struct list_head*. But what we really want is a pointer to the containing PacketBuffer. We do this with a macro, conventionally called container_of.

// The offsetof macro is standard in <stddef.h>
#include <stddef.hh>

#define container_of(ptr, type, member) ({ \
    const typeof( ((type *)0)->member ) *__mptr = (ptr); \
    (type *)( (char *)__mptr - offsetof(type, member) ); \
})

Let's break this down:

1. ptr: This is the pointer to the member, e.g., a struct list_head*.
2. type: The type of the container struct, e.g., PacketBuffer.
3. member: The name of the member within the container, e.g., list.
4. offsetof(type, member): A standard macro that calculates the byte offset of member from the beginning of struct type.
5. (char *)__mptr - offsetof(...): We cast the member pointer to a char* so that the subtraction is in bytes. We subtract the offset from the member's address to get the starting address of the containing structure.
6. (type *): We cast the resulting address back to a pointer of the container type.

The typeof and the ({...}) statement are GCC extensions, but they are standard practice in systems C code for creating type-safe expressions that can be used like functions.

Safe Iteration

We need a way to loop through our list. A simple for loop is risky: what if we delete the current node inside the loop? The for loop would no longer have a valid current->next to proceed. The solution is to fetch the next node before processing the current one.

// Iterates over a list of given type.
#define list_for_each_entry(pos, head, member) \
    for (pos = container_of((head)->next, typeof(*pos), member); \
         &pos->member != (head); \
         pos = container_of(pos->member.next, typeof(*pos), member))

// Iterates safely, allowing deletion of 'pos' within the loop.
#define list_for_each_entry_safe(pos, n, head, member) \
    for (pos = container_of((head)->next, typeof(*pos), member), \
         n = container_of(pos->member.next, typeof(*pos), member); \
         &pos->member != (head); \
         pos = n, n = container_of(n->member.next, typeof(*pos), member))

The _safe version uses a temporary variable n (for "next") to store the pointer to the next item before the loop body executes, ensuring the iteration is safe even if pos is de-linked.

For a comprehensive guide and code examples of this API, the Linux kernel documentation is the ultimate reference.

4. Practical Application: A Packet Buffer Pool

Now, let's put all the pieces together into a working program. We'll create a fixed-size pool of PacketBuffers and use our intrusive list implementation to manage them, moving them between a free_list and a transmit_queue.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stddef.h>

// --- Our list implementation from above ---
struct list_head {
    struct list_head *next, *prev;
};

#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name)

static inline void INIT_LIST_HEAD(struct list_head *list) {
    list->next = list;
    list->prev = list;
}

static inline void __list_add(struct list_head *new_node, struct list_head *prev, struct list_head *next) {
    next->prev = new_node;
    new_node->next = next;
    new_node->prev = prev;
    prev->next = new_node;
}

static inline void list_add_tail(struct list_head *new_node, struct list_head *head) {
    __list_add(new_node, head->prev, head);
}

static inline void __list_del(struct list_head *prev, struct list_head *next) {
    next->prev = prev;
    prev->next = next;
}

static inline void list_del(struct list_head *entry) {
    __list_del(entry->prev, entry->next);
    entry->next = NULL;
    entry->prev = NULL;
}

#define container_of(ptr, type, member) ({ \
    const typeof( ((type *)0)->member ) *__mptr = (ptr); \
    (type *)( (char *)__mptr - offsetof(type, member) ); \
})

#define list_for_each_entry_safe(pos, n, head, member) \
    for (pos = container_of((head)->next, typeof(*pos), member), \
         n = container_of(pos->member.next, typeof(*pos), member); \
         &pos->member != (head); \
         pos = n, n = container_of(n->member.next, typeof(*pos), member))

static inline int list_empty(const struct list_head *head) {
    return head->next == head;
}
// --- End of list implementation ---

// --- PacketBuffer struct with embedded list ---
typedef struct {
    unsigned char* head_ptr;
    unsigned char* data;
    unsigned char* tail;
    unsigned char* end;
    struct list_head list;
    int id; // For tracking
} PacketBuffer;

// --- Our Buffer Pool ---
#define POOL_SIZE 5
PacketBuffer packet_pool[POOL_SIZE];

LIST_HEAD(free_list);
LIST_HEAD(tx_queue);

// --- Main Program ---
int main() {
    // 1. Initialize the pool and add all buffers to the free_list
    printf("Initializing packet pool...\n");
    for (int i = 0; i < POOL_SIZE; ++i) {
        packet_pool[i].id = i;
        // In a real system, you'd allocate memory for head_ptr here.
        // We are just managing the descriptors.
        list_add_tail(&packet_pool[i].list, &free_list);
    }
    printf("Pool initialized. All %d packets are in free_list.\n\n", POOL_SIZE);

    // 2. Simulate getting packets for transmission
    printf("--- Getting 3 packets from free_list and adding to tx_queue ---\n");
    for (int i = 0; i < 3; ++i) {
        if (list_empty(&free_list)) {
            printf("Error: free_list is empty!\n");
            break;
        }
        // Get the first entry from the free_list
        struct list_head* node = free_list.next;
        PacketBuffer* pkt = container_of(node, PacketBuffer, list);

        // Remove from free_list and add to tx_queue
        list_del(node);
        list_add_tail(node, &tx_queue);
        printf("Moved Packet ID %d from free_list to tx_queue.\n", pkt->id);
    }
    printf("\n");

    // 3. Process the transmit queue
    printf("--- Processing tx_queue ---\n");
    PacketBuffer *current_pkt, *next_pkt;
    list_for_each_entry_safe(current_pkt, next_pkt, &tx_queue, list) {
        printf("Transmitting Packet ID %d...\n", current_pkt->id);

        // "Transmission" complete, return the packet to the free_list
        list_del(&current_pkt->list);
        list_add_tail(&current_pkt->list, &free_list);
        printf("Returned Packet ID %d to free_list.\n", current_pkt->id);
    }

    if (list_empty(&tx_queue)) {
        printf("tx_queue is now empty.\n\n");
    }

    // 4. Verify all packets are back in the free list
    int count = 0;
    list_for_each_entry_safe(current_pkt, next_pkt, &free_list, list) {
        count++;
    }
    printf("Final state: %d packets in free_list.\n", count);
    
    return 0;
}

This example fully demonstrates the lifecycle: initializing a list, moving nodes between lists (list_del from one, list_add_tail to another), and safely iterating to process a queue. All of this is done without a single malloc or free for list nodes.

void count_packets(struct list_head *head, const char* list_name) {
    int count = 0;
    PacketBuffer *pkt, *next; // 'next' is needed for the _safe macro
    
    // We can use list_for_each_entry_safe even if we don't delete
    list_for_each_entry_safe(pkt, next, head, list) {
        count++;
    }
    printf("Status: %s contains %d packets.\n", list_name, count);
}

// In main(), after the first for loop in step 2:
// ...
    printf("\n");
    count_packets(&free_list, "free_list");
    count_packets(&tx_queue, "tx_queue");
    printf("\n");
// ...

// The expected output would be:
// Status: free_list contains 2 packets.
// Status: tx_queue contains 3 packets.

Conclusion

In this lesson, you have implemented one of the most fundamental and efficient data structures used in systems programming. By embedding list pointers directly into our PacketBuffer struct, we've created a system for managing collections of objects that is both memory-efficient and performant.

Key Takeaways:

• An intrusive linked list embeds next/prev pointers directly into the data structure it links, avoiding separate allocations for list nodes.
• The Linux kernel's struct list_head provides a robust, circular, doubly-linked list model.
• The container_of macro is the key to retrieving a pointer to the parent structure from a pointer to an embedded member, using the offsetof macro and pointer arithmetic.
• Safe iteration macros like list_for_each_entry_safe are essential for correctly traversing a list while modifying it.
• This pattern is ideal for managing pools of resources, such as packet buffers, task control blocks, or device objects in an OS or embedded firmware.

Preview of the Next Lesson

The container_of macro is a carefully crafted piece of code that uses pointer casting in a well-defined way. However, arbitrary casting between pointer types can lead to undefined behavior due to a concept called aliasing. In our next lesson, we will explore this in detail: Explain pointer aliasing and the implications of violating the strict aliasing rule. Understanding this rule is critical for writing correct, portable, and optimizer-friendly C code.