Implementing Linux-style Intrusive Linked Lists

1. The Intrusive Philosophy: Why It Matters in Embedded Systems

First, let's define what makes a linked list "intrusive." In a traditional (non-intrusive) linked list, the list node is a separate object that contains a pointer to the actual data. In an intrusive list, the list pointers (next and prev) are embedded directly within the data structure you want to link.

This design choice has profound implications for embedded systems:

• Fewer Allocations: A non-intrusive list requires two allocations per item: one for the data and one for the list node. An intrusive list requires only one. This reduces memory overhead and simplifies error handling, especially in environments without an MMU or a sophisticated heap.
• No Dynamic Allocation Required: Because the list pointers are part of the object, you can create lists of statically or stack-allocated objects without ever calling malloc.
• Improved Cache Performance: The list pointers and the data reside together in memory. When you traverse the list and access an object's data, it's more likely that the data is already in the CPU cache along with the pointers, leading to fewer cache misses.

To get a better sense of these trade-offs, the following resources provide excellent conceptual overviews.

2. The Linux Kernel's list_head and container_of Pattern

The Linux kernel contains what is arguably the most famous and widely-used implementation of an intrusive list. It's elegant, efficient, and built almost entirely with C macros.

The two key components are:

1. struct list_head: A simple struct containing only next and prev pointers. This is the "node" that you embed in your own data structures.
2. container_of macro: The magic that makes it all work. Given a pointer to a list_head member, this macro calculates the address of the parent structure that contains it.

Let's break down how this is achieved.

The container_of Trick

As you just read, the central challenge is: if you have a pointer ptr to a list_head member inside a larger struct, how do you get a pointer to the start of that containing struct?

The solution relies on the offsetof macro, a standard C feature (<stddef.h>) that returns the byte offset of a member from the beginning of its parent struct.

The container_of macro uses this masterfully:
#define container_of(ptr, type, member) ((type *)((char *)(ptr) - offsetof(type, member)))

Let's dissect this:

1. (char *)(ptr): Casts the member pointer ptr to a char*. This is crucial for byte-level pointer arithmetic.
2. offsetof(type, member): Gets the byte offset of the member within the struct of type.
3. ... - offsetof(...): Subtracts the offset from the member's address. This effectively "rewinds" the pointer back to the beginning of the struct.
4. ((type *) ...): Casts the resulting address back to a pointer of the correct container type.

3. A Practical User-Space Implementation

Now, let's synthesize these concepts into a complete C implementation that you can compile and run. We will recreate the essential parts of the Linux list.h API for a user-space application.

This is exactly the kind of hands-on task you might face in a coding interview.

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

// 1. The core list structure from the Linux kernel.
// It's a circular doubly-linked list.
struct list_head {
    struct list_head *next, *prev;
};

// 2. A static initializer for a list head.
// An empty list is one where the head's next and prev pointers point to itself.



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

// 3. The magical `container_of` macro.



#define container_of(ptr, type, member) \
    ((type *)((char *)(ptr) - offsetof(type, member)))

// Helper function for list insertion.
static inline void __list_add(struct list_head *new_entry,
                              struct list_head *prev,
                              struct list_head *next)
{
    next->prev = new_entry;
    new_entry->next = next;
    new_entry->prev = prev;
    prev->next = new_entry;
}

// 4. Functions/macros to manipulate the list.

// Adds a new entry after the specified head. Good for stacks (LIFO).
static inline void list_add(struct list_head *new_entry, struct list_head *head) {
    __list_add(new_entry, head, head->next);
}

// Adds a new entry before the specified head. Good for queues (FIFO).
static inline void list_add_tail(struct list_head *new_entry, struct list_head *head) {
    __list_add(new_entry, head->prev, head);
}

// Deletes an entry by making its neighbors point to each other.
static inline void list_del(struct list_head *entry) {
    entry->next->prev = entry->prev;
    entry->prev->next = entry->next;
    entry->next = NULL; // Optional: helps catch use-after-free bugs
    entry->prev = NULL;
}

// 5. Macros for safe and easy iteration.

// Gets the container struct for a given list entry.



#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)

// Iterates over a list. `pos` is the `struct list_head*` cursor.



#define list_for_each(pos, head) \
    for (pos = (head)->next; pos != (head); pos = pos->next)

// Iterates over a list of a given type. `member` is the name of the list_head
// struct within the container. `iter` is the cursor of the container type.



#define list_for_each_entry(iter, head, member) \
    for (iter = list_entry((head)->next, typeof(*iter), member); \
         &iter->member != (head); \
         iter = list_entry(iter->member.next, typeof(*iter), member))


// --- DEMONSTRATION ---

// Our custom data structure that will be part of the list.
typedef struct {
    int id;
    struct list_head list; // The embedded list node.
} car_t;

int main() {
    // Initialize the list head.
    LIST_HEAD(car_list);

    printf("Adding cars to the list...\n");

    // Create and add some car objects to the list.
    // In a real system, these could be allocated differently.
    car_t car1 = { .id = 101 };
    list_add_tail(&car1.list, &car_list);

    car_t car2 = { .id = 202 };
    list_add_tail(&car2.list, &car_list);
    
    car_t car3 = { .id = 303 };
    list_add_tail(&car3.list, &car_list);

    printf("Iterating through the car list:\n");
    
    // Iterate using the powerful list_for_each_entry macro.
    car_t *current_car;
    list_for_each_entry(current_car, &car_list, list) {
        printf("  - Found Car ID: %d\n", current_car->id);
    }
    
    printf("\nDeleting car with ID 202...\n");
    list_del(&car2.list);
    
    printf("Iterating again after deletion:\n");
    list_for_each_entry(current_car, &car_list, list) {
        printf("  - Found Car ID: %d\n", current_car->id);
    }

    return 0;
}

Take some time to study this code. Compile and run it. The list_for_each_entry macro is particularly insightful; it combines iteration and container_of into a clean, type-safe loop that directly gives you a pointer to your container struct (car_t *current_car).

4. Intrusive Lists in Action

To see how these same APIs are used in a real-world context, this final video shows a developer building a simple Linux kernel module using the very list.h we've been modeling.

Conclusion

In this lesson, you've gone deep into one of C's most powerful and elegant patterns. This is far beyond textbook data structures; it's a technique used to build the world's most complex and performance-critical software.

Key Takeaways:

• Intrusive lists embed linking pointers within the data structure, saving memory allocations and improving cache locality.
• The Linux kernel's implementation uses a circular, doubly-linked struct list_head.
• The container_of macro is the core mechanism that enables retrieving a parent struct from a pointer to one of its members, using pointer arithmetic and the offsetof macro.
• A rich set of macros like list_add, list_del, and list_for_each_entry provide a safe and efficient API for manipulating these lists.

Being able to explain and implement this pattern from scratch is a significant differentiator in an interview for an experienced embedded role.

Preview of the Next Lesson:

Now that we have explored two fundamental data structures—circular buffers and linked lists—our next lesson will focus on a classic algorithm related to them. We will look at how to detect cycles in a linked list using Floyd's tortoise-and-hare algorithm. This is a famous interview problem that tests your algorithmic thinking and problem-solving skills with pointers.