[Userspace RCU] Introducing a new data structure: Fractal Trie

[Mathieu Desnoyers]

Hi!

I've implemented a new RCU Trie data structure, and would welcome
your feedback while it's in development stage.

It's currently sitting in a development branch of my private
userspace-rcu repository. It's currently targeting userspace
applications, but could be ported to the Linux kernel if there is a
use-case for it.

https://github.com/compudj/userspace-rcu-dev/tree/fractal-trie-dev

I've started working on this project around 2012, and I've recently
been able to find time to pursue this work. (Many thanks to ISC.org
for funding this!).

Here are a few major use-cases I see are a good fit:

- DNS resolver,
- IP routing tables.
- Real-time application data structure lookups with strict real-time
   bound limits (wait-free, guaranteed bounded number of cache line
   loads per key byte).

I'm pasting the API header top comment as summary of the feature set
here:

/*
  * urcu/fractal-trie.h
  *
  * Userspace RCU library - Fractal Trie
  *
  * A concurrent, RCU-protected ordered trie mapping variable or
  * fixed-length byte keys to user-defined nodes. Keys are opaque
  * byte sequences with no reserved or sentinel values; unlike
  * tries that rely on NUL or other terminal characters, any byte
  * value may appear at any position in a key. Lookups and
  * traversals are wait-free under the RCU read-side lock and can
  * proceed concurrently with mutations. The internal structure is
  * acyclic by construction: no sequence of concurrent updates can
  * introduce a cycle, ensuring that all lookups and traversals
  * complete in bounded time. Supports exact lookup, partial
  * (prefix) match, ordered iteration, duplicate key chains, and
  * range queries (<=, >=, <, >). A longest-match lookup reports
  * the deepest trie position matching a prefix of the input key,
  * even if that position has no external node.
  *
  * Performance characteristics:
  *
  * - Lookup: At most 2 cache-line accesses per key byte.
  * - Ordered traversal: At most 3 cache-line accesses per node.
  *
  * Internal node configurations:
  *
  * Internal nodes self-adapt to the key population using several
  * configurations (linear, 1D pool, 2D pool, pigeon), each with
  * a different indexing strategy suited to its child density.
  * The appropriate configuration is chosen automatically based
  * on the number of children. Node sizes are powers of 2 between
  * 16 bytes and 2048 bytes on 64-bit architectures (1024 bytes
  * on 32-bit). Mutations use in-place updates when possible to
  * minimize node recompaction, and hysteresis at size thresholds
  * prevents repeated recompaction when the child count oscillates
  * near a boundary.
  *
  * The 1D and 2D pool configurations partition the 8-bit key
  * byte space using one or two bit positions respectively,
  * distributing children across sub-nodes. This provides a
  * range of intermediate node sizes between the compact linear
  * configuration and the full 256-entry pigeon configuration,
  * allowing memory-efficient representation of medium-density
  * populations without requiring the full pigeon footprint.
  * The bit positions are selected to minimize the maximum
  * sub-node population, using a minimax criterion. The
  * transition thresholds and worst-case sub-node sizes were
  * empirically validated by brute-force enumeration of optimal
  * bit selections across millions of random populations.
  * Alternative approaches such as Judy use a population bitmap
  * with a dense child array, which requires recompacting the
  * array on every insertion or removal. This is incompatible
  * with wait-free RCU lookups, since a reader could observe a
  * partially recompacted array. The pool approach avoids this
  * by using fixed index positions derived from key bits,
  * allowing children to be added or removed with single-pointer
  * updates visible atomically to concurrent readers.
  *
  * Node type and configuration are encoded in the low bits of
  * child pointers (tagged pointers), so determining a node's
  * layout during lookup requires no extra memory access.
  *
  * The 2D pool and pigeon configurations use a 32-byte bitmap
  * to locate populated children via bit scanning, reducing the
  * number of cache-line accesses needed for ordered traversal.
  *
  * Memory layout:
  *
  * Per-node metadata is stored in a separate page via a strided
  * allocator and reached by pointer offset from the node address,
  * keeping metadata out of the node's cache lines. This avoids
  * padding overhead within nodes and ensures that lookups and
  * traversals only touch the data they need. Internal nodes are
  * reclaimed via RCU (call_rcu), so readers never access freed
  * memory even for the trie's own internal structure.
  *
  * This provides memory efficiency comparable to adaptive radix
  * tree schemes without requiring user tuning or configuration.
  *
  * Graft, graft-swap, and detach:
  *
  * The graft, graft-swap, and detach operations move entire
  * sub-tries between trie instances within the same group. Each
  * operation is a single pointer store visible atomically to
  * concurrent RCU readers: a reader sees either the complete
  * sub-trie or nothing, never a partial state.
  *
  * - Graft (cds_ft_graft) attaches the content of a source trie
  *   at a key position in a destination trie. The destination
  *   must have no content at or below the graft point. On
  *   success the source trie becomes empty and can be reused or
  *   destroyed.
  *
  * - Graft-swap (cds_ft_graft_swap) exchanges the content at a
  *   key position in a destination trie with the content of
  *   another trie. Unlike plain graft, the destination does not
  *   need to be empty at the graft point: any pre-existing
  *   content is moved into the swap trie. Concurrent readers
  *   see either the old content or the new content, never an
  *   empty intermediate state.
  *
  * - Detach (cds_ft_detach) removes the sub-structure rooted at
  *   a key position and returns it as a new, independent trie
  *   instance whose key lengths are relative to the detach
  *   point.
  *
  * Root-level operations (key_len 0) work with both fixed-length
  * and variable-length key groups. Non-root operations (key_len
  * > 0) require a variable-length key group
  * (CDS_FT_LEN_VARIABLE): in a fixed-length group every key
  * must equal the group's fixed length, so a shorter prefix
  * needed to address an interior graft or detach point cannot be
  * expressed, and the call returns
  * CDS_FT_STATUS_INVALID_ARGUMENT_ERROR.
  *
  * Together, these operations serve as the transplant, exchange,
  * and split primitives for bulk operations. A typical bulk-load
  * pattern populates a staging trie offline — with no RCU or
  * locking overhead — and then grafts it into the live trie in
  * a single O(1) step, keeping the writer critical section
  * minimal regardless of the number of nodes being moved. A
  * complementary bulk-removal pattern detaches (or graft-swaps)
  * a sub-trie in O(1), waits for a single grace period, and
  * then drains the detached trie locally, reducing the cost
  * from one grace period per node to one grace period total.
  *
  * Iterator Lifecycle and RCU Locking:
  *
  * The `cds_ft_iter` object can operate in two path modes, selected via
  * cds_ft_iter_set_path_mode():
  *
  * CDS_FT_ITER_PATH_CACHED (default):
  *
  * The iterator caches the traversal path (RCU protected pointers) to
  * accelerate subsequent sequential operations like cds_ft_next(),
  * cds_ft_prev(), or cds_ft_remove().
  *
  * Because of this caching, the RCU read-side lock must be held
  * CONTINUOUSLY between the operation that populates the iterator
  * (e.g., cds_ft_lookup) and the operation that consumes it. If the
  * RCU read-side lock is dropped, the cached path may point to freed
  * memory.
  *
  * If you need to drop the RCU read-side lock between operations, you
  * MUST invalidate the iterator's cached path before reusing it. This
  * is done by calling:
  * - cds_ft_iter_invalidate_path()
  *
  * Calling this function clears the internal path state while keeping
  * your key intact. The next operation (e.g., cds_ft_remove) will
  * automatically fall back to a safe, fresh top-down traversal.
  *
  * Example A (Continuous Lock - Fast):
  * rcu_read_lock();
  * cds_ft_lookup(ft, iter);
  * cds_ft_remove(ft, iter, node); // Uses cached path O(1)
  * rcu_read_unlock();
  *
  * Example B (Dropped Lock - CDS_FT_ITER_PATH_CACHED only):
  * rcu_read_lock();
  * cds_ft_lookup(ft, iter);
  * rcu_read_unlock();
  * // ... time passes, lock is dropped ...
  *
  * lock(&writer_mutex);
  * cds_ft_iter_invalidate_path(iter); // Flush the stale RCU cache
  * cds_ft_remove(ft, iter, node);     // Safe: Fresh traversal protected by writer lock
  * unlock(&writer_mutex);
  *
  * Note: CDS_FT_ITER_PATH_UNCACHED iterators do not require
  * cds_ft_iter_invalidate_path() — the path is discarded
  * automatically after each operation.
  *
  * Debug validation (URCU_FRACTAL_TRIE_DEBUG_PATH):
  *
  * Building with URCU_FRACTAL_TRIE_DEBUG_PATH defined enables run-time
  * detection of stale cached paths.  Each path population records an RCU
  * grace-period snapshot (via the flavor's
  * update_start_poll_synchronize_rcu); each path consumption polls it
  * (via update_poll_state_synchronize_rcu).  If a full grace period has
  * elapsed since the path was populated, the cached pointers may
  * reference freed memory — the program aborts with a diagnostic.
  * Since struct cds_ft_iter is opaque, this option does not affect the
  * application ABI — only the library needs to be rebuilt.
  *
  * CDS_FT_ITER_PATH_UNCACHED:
  *
  * The iterator automatically discards the traversal path after each
  * operation returns. Every subsequent operation performs a fresh
  * top-down traversal from the current key. The RCU read-side lock
  * only needs to be held during each individual operation and while
  * accessing the returned node — it may be dropped between operations.
  *
  * This mode is suited for iteration patterns where the caller needs
  * to drop the RCU read-side lock between steps (e.g. to perform
  * blocking work or acquire other locks).
  *
  * Example C (Uncached mode, per-step locking with refcount):
  * cds_ft_iter_set_path_mode(iter, CDS_FT_ITER_PATH_UNCACHED);
  * rcu_read_lock();
  * cds_ft_for_each_rcu(ft, iter) {
  *         struct my_entry *e = cds_ft_entry(
  *                 cds_ft_iter_node(iter),
  *                 struct my_entry, ft_node);
  *         refcount_inc(&e->refcount);
  *         rcu_read_unlock();
  *
  *         do_blocking_work(e);
  *         refcount_dec(&e->refcount);
  *
  *         rcu_read_lock();
  * }
  * rcu_read_unlock();
  */

Your feedback is welcome!

Thanks,

Mathieu

-- 
Mathieu Desnoyers
EfficiOS Inc.
https://www.efficios.com