Skip to content

ADR 0005: Prefix Matching and Double-Buffered RCU for Rule Evaluation

Status

Approved

Context

Workers evaluate rules for every parsed packet, requiring sub-100ns execution. Furthermore, administrators must be able to reload rules dynamically at runtime without blocking worker execution.

Decision

We will represent rules using flat arrays (for subnets/CIDR) and reversed tries (for domains). We will use a double-buffered atomic pointer swap (Read-Copy-Update pattern) to reload rules.

Design Constraints:

  • The active rule table is accessed via a read-only pointer stored in a std::atomic<const RuleTable*>.
  • Worker threads load the pointer with std::memory_order_consume or std::memory_order_acquire.
  • Updates copy and allocate a new RuleTable, swap the atomic pointer, wait for worker epochs, and safely deallocate the old table.

Options Considered

  1. Mutex-Guarded Rule Container: Simple, but workers would block whenever rules are evaluated, destroying latency goals.
  2. Read-Write Lock (std::shared_mutex): Better than standard locks, but still causes cache invalidation across cores when the write lock is taken.
  3. Double-Buffered RCU Swap: Lock-free, zero overhead for readers (workers). Memory is cleanly reclaimed by the controller thread.

Consequences

  • Positive: Worker threads never block on rule evaluations, and rules are updated dynamically in real-time.
  • Negative: Slightly higher memory footprint during the reload transition because two tables exist in memory temporarily.