container_of in Linux Intrusive Data Structures

This article explores how the Linux kernel uses the container_of macro to power intrusive data structures. In traditional data structures, a generic node wraps a pointer to the payload, whereas intrusive structures embed generic links directly inside domain-specific objects. The container_of macro is the foundational mechanism that allows kernel code to recover the outer enclosing structure from a pointer to an internal embedded member, providing memory efficiency, cache locality, and compile-time type safety.

The Problem with Non-Intrusive Structures

In standard C development, generic data structures—such as linked lists—are typically non-intrusive. A list node usually contains pointers to the next and previous nodes, along with a generic void * pointer referencing the user data:

struct list_node {
    struct list_node *next;
    struct list_node *prev;
    void *data;
};

This model has major drawbacks for an operating system kernel:

  1. Dynamic Allocation Overhead: Adding an item to a list requires allocating memory for both the item and the list node.
  2. Cache Misses: Navigating the structure requires dereferencing multiple disjoint pointers in memory.
  3. Redundant Metadata: Managing multiple independent list memberships requires allocating multiple wrappers.

Intrusive Data Structures in the Linux Kernel

The Linux kernel avoids these overheads by turning the model inside out using intrusive data structures. Instead of placing the payload inside a container node, the link node is placed inside the payload.

The canonical example is the kernel's circular doubly linked list, represented by struct list_head:

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

A kernel developer embeds struct list_head directly into their custom struct:

struct task_struct {
    pid_t pid;
    /* ... other fields ... */
    struct list_head tasks;
};

List traversal operations (list_add, list_del, list_for_each) only operate on the struct list_head pointers. Consequently, list operations do not need to know the type or memory layout of the outer object.

The Role of container_of

While intrusive structures simplify generic list manipulation, they introduce a fundamental challenge: when traversing a list, the algorithm only has access to a pointer to the embedded member (struct list_head *), not the enclosing structure (struct task_struct *).

The container_of macro bridges this gap. It calculates the base address of the enclosing structure given:

  1. A pointer to the embedded member.
  2. The type of the outer container structure.
  3. The name of the member within that container structure.

How container_of Operates

The container_of macro is defined in <linux/kernel.h> (derived from build_bug.h and stddef.h) as follows:

#define container_of(ptr, type, member) ({                      \
    void *__mptr = (void *)(ptr);                               \
    BUILD_BUG_ON_MSG(!__same_type(*(ptr), ((type *)0)->member) &&\
                     !__same_type(*(ptr), void),                \
                     "pointer type mismatch in container_of()");\
    ((type *)(__mptr - offsetof(type, member))); })

The macro functions in two key phases:

  1. Compile-Time Type Verification: The macro uses compiler intrinsics (__same_type) and BUILD_BUG_ON_MSG to verify that the pointer passed in actually matches the type of the declared member (or is a generic void *). If an incorrect pointer type is supplied, compilation fails immediately, preventing silent memory corruption.

  2. Pointer Arithmetic via offsetof: The offsetof(type, member) macro computes the byte distance from the start of type to member. By subtracting this byte offset from the memory address of the member (__mptr), the macro yields the exact starting address of the enclosing container. Finally, it casts that address to type *.

Architectural Benefits

The symbiotic relationship between intrusive structures and container_of provides several architectural guarantees essential for high-performance systems programming:

  • Zero Allocation Costs: Inserting an object into a list, red-black tree, or hash table involves no secondary memory allocations. Nodes cannot fail insertion due to out-of-memory errors.
  • Multiple Simultaneous Collections: A single object can contain multiple struct list_head members, allowing it to reside on multiple lists simultaneously (e.g., an active task list and a sleep queue) without extra memory tracking.
  • Cache Locality: Because node pointers are embedded directly in the data block, traversing and accessing object fields minimizes CPU cache line loads.