Topic 04: Intrusive Data Structures & Zero-Overhead Memory Layout

Target Duration: 2–4 minutes (~300–450 spoken words)
Focus: Pointwise verbal delivery covering intrusive data structures, the container_of macro, offsetof arithmetic, flexible array members (char name[0]), and multi-index membership in single heap allocations.

🎙️ Pointwise Spoken Speech (Word-for-Word Delivery)

• Opening & Scope:
  "Standard C++ containers like std::list or std::map wrap user data in separate node structures, causing multiple dynamic allocations per element, pointer indirection, and heavy heap fragmentation. In Radis, I adopted the Linux kernel's intrusive data structure paradigm, embedding linking nodes directly inside payload data structures."

• Step 1: The Intrusive Design Pattern:
  "First, instead of having a data structure allocate memory to store my payload, my payload structs (Entry in struct Entry (server.cpp:276-294), ZNode in struct ZNode (zset.h:16-24), Conn in struct Conn (server.cpp:48-59)) directly embed the structural nodes—like HNode in struct HNode (hashtable.h:8-12) for hash chains, AVLNode in struct AVLNode (avl.h:7-13) for binary trees, and DList in struct DList (list.h:6-9) for doubly-linked lists. The data structure code manipulates only these embedded nodes without knowing or caring what outer struct contains them."

• Step 2: Address Computation via the container_of Macro:
  "Second, to access the parent data structure given a pointer to an internal node, I implemented the classic Linux kernel container_of macro in container_of (common.h:8-13) using GCC statement expressions and offsetof. By casting a null pointer to the outer type, offsetof(type, member) computes the exact byte offset of the embedded member at compile time. Subtracting this offset from the member pointer yields the exact address of the parent struct with zero runtime overhead, exhaustively verified in test_offset.cpp:1-83."

• Step 3: Multi-Container Membership Without Duplication:
  "Third, a major advantage of intrusive data structures is simultaneous membership in multiple containers without data duplication. In struct ZNode (zset.h:16-24), an element embeds an AVLNode tree and an HNode hmap side-by-side. The exact same allocated memory block is simultaneously linked into an AVL tree ordered by score and a hash table indexed by name—eliminating pointer wrappers, synchronizing lifecycles, and cutting memory consumption in half."

• Step 4: Cache Locality with Flexible Array Members (char name[0]):
  "Fourth, for variable-length strings in Sorted Sets, I used a flexible array member: char name[0] at the end of struct ZNode (zset.h:20). When creating a node in znode_new() (zset.cpp:43-52), the server allocates malloc(sizeof(ZNode) + len). The payload struct, metadata, tree pointers, hash pointers, and the string characters themselves reside in a single contiguous memory block. This dramatically improves CPU L1/L2 cache locality during lookups and halves the workload on the OS heap allocator."

• Step 5: Circular Sentinel Doubly-Linked Lists (DList):
  "Finally, for tracking idle connection timeouts, I used an intrusive circular doubly-linked list struct DList (list.h:6-32) integrated into Conn in server.cpp:52. The list header initializes its prev and next pointers to point to itself (dlist_init() list.h:11-15). This circular sentinel pattern guarantees that insertions (dlist_insert_before() list.h:23-28) and detachments (dlist_detach() list.h:17-21) never encounter NULL pointers, removing conditional branching from the critical path."

📋 Step-by-Step Summary (What, How & Why)

❓ Anticipated Interview Questions & Crisp Answers

Q1: Why choose intrusive data structures over standard C++ STL containers (std::list, std::map, or smart pointers)?

Answer: In std::list<T> or std::map<K,V>, every insert performs a separate heap allocation for a wrapper node containing prev, next, and copied values. This causes severe heap fragmentation, allocator lock overhead, and pointer chasing across disconnected cache lines. With intrusive structures, the node pointers (HNode, AVLNode, DList) are directly embedded into the payload struct. Zero allocations happen when inserting into a table or list. Furthermore, traversing the structure brings payload data into CPU L1 cache along with tree/hash pointers.

Q2: What problems or alignment issues did you face with the container_of macro and flexible array members?

Answer: Two critical issues occurred: (1) offsetof alignment and strict aliasing: casting byte pointers via (type *)((char *)ptr - offsetof(...)) requires byte-level pointer arithmetic using char * to avoid undefined behavior; in C++ non-standard layout types can break standard offsetof, so structs had to remain standard layout (POD-like). (2) Flexible array member sizing: sizeof(ZNode) can include trailing struct padding bytes due to 64-bit alignment of prior members. If not careful when computing malloc(sizeof(ZNode) + len), off-by-one or buffer overflows could occur during string indexing. I authored test_offset.cpp with assert() checks to mathematically verify member offsets, padding, and container_of pointer recovery across GCC and Clang compilers before integrating into the engine.

Q3: How do you verify memory integrity and prevent use-after-free when an element belongs to multiple intrusive containers simultaneously?

Answer: Intrusive dual-membership (like ZNode belonging to both AVL tree and Hash Table) means unlinking from one container without unlinking from the other creates a catastrophic dangling pointer. I centralized node destruction behind strict lifecycle functions (znode_del() in zset.cpp and entry_del() in server.cpp). When deleting an entry, the code unlinks from the hash table first, then unlinks from the AVL tree or timer list, and only calls free() once all intrusive pointers are detached. I validated this using Valgrind and Clang AddressSanitizer (-fsanitize=address) under sustained high-concurrency fuzz testing (test_cmds.py), confirming zero leaks and zero use-after-free bugs.