Prompt and context
A kernel subsystem must maintain many non-overlapping integer ranges with lookup, insert, delete, and gap iteration. Explain Maple Tree’s structure, concurrent access, allocation constraints, and how you would validate a migration from the old structure.
Linux kernel documentation describes Maple Tree as a B-tree optimized for non-overlapping ranges. It stores point indices and ranges, supports ordinary and constrained allocation modes, and can be read under its lock or with RCU. The interview tests lifecycle, locking, and allocation semantics rather than a claim that it is simply “faster than a red-black tree.”
What the interviewer evaluates
The interviewer looks for a distinction between index values, range values, and gaps; an explanation of node splits, merges, and operation state; correct GFP, lock, reference-count, and RCU handling; preserved non-overlap, iteration order, and deletion semantics during migration; and benchmarks that include concurrency and memory pressure.
Clarifying questions
Range model
Confirm whether ranges are closed, whether endpoints can be the maximum integer, whether adjacent ranges may merge, whether gaps have meaning, and whether one index maps to one object.
Concurrency and context
Confirm whether callers run in process, interrupt, or non-sleepable context; whether readers can use RCU; and whether writers rely on Maple Tree’s internal lock or an outer lock.
Migration target
Confirm the old structure’s complexity, memory budget, stable ABI, debugging tools, and error codes that must remain compatible. Migration cannot be judged on single-thread throughput alone.
30-second answer
“Maple Tree uses range-oriented B-tree nodes to pack indices and intervals, which suits non-overlapping ranges and gap queries. Ordinary updates may allocate with GFP rules; atomic or non-sleepable paths need prepared operation state and constrained allocation. Readers can use a lock, or under RCU they acquire an object reference before leaving the read section. I would establish invariants and a dual-write comparison, test boundaries, gaps, deletion, concurrency, and memory pressure, then compare real-workload latency and footprint.”
Step-by-step solution
Step 1: Define range invariants
Specify each entry’s start and end indices, whether empty values are allowed, and whether adjacent ranges merge. Every insert, replace, and delete must preserve non-overlap, with explicit behavior for endpoint overflow and empty ranges.
Step 2: Understand nodes and operation state
Maple Tree nodes store multiple pivots and slots, reducing pointer depth and improving range locality. Complex iteration or updates can use ma_state for the current position and operation context; do not reuse state across unsupported concurrency boundaries.
Step 3: Choose an allocation mode
Ordinary updates may allocate with GFP_KERNEL and sleep. Non-sleepable paths need preallocation or constrained GFP flags and prepared operation state. Never invoke a potentially sleeping allocation path while holding a spinlock or inside an RCU read section.
Step 4: Design read consistency
Lock-based reads are straightforward. With RCU, acquire a reference or copy the required data before leaving the RCU section. Object release must align reference counting, callbacks, and tree deletion; protecting the node alone does not protect the value lifetime.
Step 5: Implement range and gap lookup
Lookup at an index returns the covering range or no value. Gap iteration continues from the previous entry’s end so first and last boundaries are not skipped. The iterator records its next index and handles concurrent deletion and the maximum index; “no value” is not automatically end-of-iteration.
lookup(index):
lock_or_rcu_read()
entry = maple_lookup(index)
if entry != null:
refcount_inc(entry.owner)
unlock_or_rcu_read()
return entry
find_gap(start, end):
state = maple_state(start)
while state.index <= end:
range = maple_next_range(state)
if gap_before(range, state.index): return [state.index, range.start - 1]
state.index = range.end + 1
return [state.index, end]Step 6: Migrate the old structure
Keep the old structure as the source of truth while building a dual-write or side index. Compare random boundaries, overlapping inserts, post-delete gaps, and concurrent reads. Switch the read path only after error codes, lock order, allocation failure, and recovery behavior match.
Step 7: Validate gains and rollback
Record latency percentiles for lookup, range iteration, gap search, and update, along with node memory, allocation failures, and lock wait. Keep a feature switch and consistency counters; stop and roll back on divergence rather than replacing production workload testing with one microbenchmark.
Model answer
I would define non-overlap, endpoint, and gap invariants first, then store ranges in Maple Tree’s range-oriented B-tree. Sleepable ordinary paths can use GFP_KERNEL; non-sleepable paths prepare state and avoid allocation inside lock or RCU sections. Readers either hold a lock or acquire an object reference under RCU before using it, with reference counting protecting value lifetime. I would dual-write during migration and compare lookup, gap, delete, and boundary behavior, then switch using latency, memory, and allocation-failure metrics while keeping the old implementation as a rollback path.
Common mistakes
- Mistake: Treating Maple Tree as a point-key map. → Why it fails: Its value is non-overlapping ranges and gap operations. → Fix: Define endpoints, covering lookup, and gap iteration.
- Mistake: Calling a potentially sleeping update under a spinlock or in an RCU read section. → Why it fails: GFP allocation context cannot sleep there. → Fix: Preallocate, choose the correct mode, and separate lock boundaries.
- Mistake: Protecting only the tree node, not the value object. → Why it fails: The value can be freed after unlock. → Fix: Copy or take a reference before leaving the RCU or lock section.
- Mistake: Measuring only lookup throughput during migration. → Why it fails: Splits, deletion, gaps, and memory pressure can dominate. → Fix: Compare realistic ranges, concurrency, and allocation-failure scenarios.
Follow-ups and responses
Maple Tree or a red-black tree?
For simple ordered point keys, a red-black tree may be enough. Large sets of non-overlapping ranges, gap queries, and locality favor Maple Tree. Let workload and concurrency metrics decide.
When would you use RCU?
Use it for read-heavy paths with low lock contention when values can be reclaimed safely after a grace period. If readers must mutate objects immediately or references cannot be managed, lock-based access is clearer.
Why can mtree_erase() require GFP_KERNEL?
Deletion can trigger node restructuring or related allocation work, so the caller’s context must permit the required memory operations. Non-sleepable paths need the documented constrained interface and prepared state.
How do you prove that no gap is skipped?
Generate an exact model with exhaustive boundaries, adjacent ranges, maximum indices, and random deletion; compare every gap’s endpoints, including concurrent deletion and iterator restart.