strat9_kernel/ipc/
mailbox.rs

1//! N1 IntrusiveMailbox : lock-free LIFO mailbox for kernel-internal IPC.
2//!
3//! This is a **stack (LIFO)** structure, not a FIFO queue.  Messages are
4//! inserted at the head and popped from the head.  This is acceptable for
5//! notification-style IPC between trusted kernel components (scheduler <==>
6//! VFS, scheduler <==> memory manager) where message ordering is not critical.
7//!
8//! For FIFO-guaranteed IPC, use the [`LockFreeRing`] (N2) instead.
9//!
10//! # Safety
11//!
12//! The mailbox uses tagged pointers (x86-64 canonical addresses) for ABA-safe
13//! lock-free push/pop.  See [`tag_ptr`] and [`untag_ptr`].
14
15use alloc::boxed::Box;
16use core::sync::atomic::{AtomicU64, AtomicUsize, Ordering};
17
18/// Default number of pre-allocated node slots in the freelist.
19/// Chosen to cover the maximum expected number of in-flight N1 messages.
20const FREELIST_CAPACITY: usize = 32;
21
22use super::transport::{
23    IpcConsumer, IpcError, IpcProducer, IpcTransport, TransportCapabilities, TransportLevel,
24};
25use crate::ipc::message::IpcMessage;
26
27// ---------------------------------------------------------------------------
28// Tagged-pointer constants (x86-64 4-level paging only)
29// ---------------------------------------------------------------------------
30
31#[cfg(target_arch = "x86_64")]
32const TAG_SHIFT: usize = 48;
33#[cfg(target_arch = "x86_64")]
34const TAG_MASK: usize = 0xFFFF_0000_0000_0000;
35#[cfg(target_arch = "x86_64")]
36const PTR_MASK: usize = !TAG_MASK;
37
38// riscv64 Sv48: tag in the top 16 bits above the 56-bit VA space.
39#[cfg(target_arch = "riscv64")]
40const TAG_SHIFT: usize = 56;
41#[cfg(target_arch = "riscv64")]
42const TAG_MASK: usize = 0xFF00_0000_0000_0000;
43#[cfg(target_arch = "riscv64")]
44const PTR_MASK: usize = !TAG_MASK;
45
46static TAG_COUNTER: AtomicUsize = AtomicUsize::new(0);
47
48/// Encode a wrapped tag into the upper bits of a pointer value.
49fn tag_ptr(ptr: usize) -> usize {
50    let tag = TAG_COUNTER.fetch_add(1, Ordering::Relaxed) & 0xFFFF;
51    (ptr & PTR_MASK) | (tag << TAG_SHIFT)
52}
53
54/// Strip the tag and recover the real pointer.
55fn untag_ptr(tagged: usize) -> *mut MailboxMessage {
56    (tagged & PTR_MASK) as *mut MailboxMessage
57}
58
59// ---------------------------------------------------------------------------
60// MailboxError
61// ---------------------------------------------------------------------------
62
63/// Errors from mailbox operations.
64#[derive(Debug, Clone, Copy, PartialEq, Eq)]
65pub enum MailboxError {
66    /// Allocation of a new message node failed.
67    AllocFailed,
68}
69
70// ---------------------------------------------------------------------------
71// MailboxMessage : intrusive node
72// ---------------------------------------------------------------------------
73
74/// A single message node in the intrusive linked list.
75#[repr(C)]
76pub struct MailboxMessage {
77    /// Intrusive link to the next node (null = end of list).
78    next: AtomicUsize,
79    /// Message payload.
80    pub data: IpcMessage,
81}
82
83// ---------------------------------------------------------------------------
84// IntrusiveMailbox
85// ---------------------------------------------------------------------------
86
87/// A lock-free LIFO mailbox (stack) for kernel-internal IPC.
88///
89/// Messages are pushed atomically to the head of an intrusive linked list
90/// and popped from the head.  This is **not** a FIFO queue : message order
91/// is reversed on reception.
92///
93/// # Use case
94///
95/// Use for notification-style IPC between trusted kernel components where
96/// low latency (~10 cycles) matters more than message ordering.  For
97/// FIFO-guaranteed IPC, use [`LockFreeRing`](super::lockfree_ring::LockFreeRing).
98/// Lock-free LIFO pool of reusable `MailboxMessage` nodes.
99///
100/// Used by `IntrusiveMailbox` to avoid heap allocation in IRQ context.
101/// Nodes are recycled: after `pop()`, the node is returned to the pool
102/// instead of freed; on `push()`, the pool is checked first before
103/// allocating a fresh node.
104///
105/// ABA protection: the head pointer is tagged with a monotonic generation
106/// counter to prevent the ABA problem on concurrent pop/push cycles.
107#[derive(Debug)]
108struct NodePool {
109    head: AtomicU64,
110}
111
112/// Mask for the pointer portion of a tagged pool pointer.
113const POOL_PTR_MASK: u64 = 0x0000_FFFF_FFFF_FFFF;
114/// Shift for the generation counter in a tagged pool pointer.
115const POOL_GEN_SHIFT: u64 = 48;
116
117impl NodePool {
118    const fn new() -> Self {
119        NodePool {
120            head: AtomicU64::new(0),
121        }
122    }
123
124    /// Pre-allocate `count` nodes into the pool.
125    fn preallocate(&self, count: usize) {
126        for _ in 0..count {
127            let msg = MailboxMessage {
128                next: AtomicUsize::new(0),
129                data: IpcMessage::new(0),
130            };
131            let ptr = Box::into_raw(Box::new(msg)) as u64;
132            self.push_raw(ptr as *mut MailboxMessage);
133        }
134    }
135
136    /// Try to pop a node from the pool (lock-free, ABA-safe).
137    fn try_pop_raw(&self) -> Option<*mut MailboxMessage> {
138        loop {
139            let tagged = self.head.load(Ordering::Acquire);
140            let ptr = (tagged & POOL_PTR_MASK) as *mut MailboxMessage;
141            if ptr.is_null() {
142                return None;
143            }
144            let gen = tagged >> POOL_GEN_SHIFT;
145            let next = unsafe { (*ptr).next.load(Ordering::Relaxed) } as u64;
146            let new_tagged = (next & POOL_PTR_MASK) | ((gen + 1) << POOL_GEN_SHIFT);
147            if self
148                .head
149                .compare_exchange_weak(tagged, new_tagged, Ordering::Acquire, Ordering::Relaxed)
150                .is_ok()
151            {
152                return Some(ptr);
153            }
154        }
155    }
156
157    /// Push a raw node pointer back into the pool (lock-free, ABA-safe).
158    fn push_raw(&self, ptr: *mut MailboxMessage) {
159        loop {
160            let tagged = self.head.load(Ordering::Relaxed);
161            let gen = tagged >> POOL_GEN_SHIFT;
162            unsafe {
163                (*ptr)
164                    .next
165                    .store((tagged & POOL_PTR_MASK) as usize, Ordering::Relaxed);
166            }
167            let new_tagged = (ptr as u64 & POOL_PTR_MASK) | ((gen + 1) << POOL_GEN_SHIFT);
168            if self
169                .head
170                .compare_exchange_weak(tagged, new_tagged, Ordering::Release, Ordering::Relaxed)
171                .is_ok()
172            {
173                return;
174            }
175        }
176    }
177}
178
179#[derive(Debug)]
180pub struct IntrusiveMailbox {
181    head: AtomicUsize,
182    /// Pool of pre-allocated nodes for IRQ-safe push/pop without heap alloc.
183    pool: NodePool,
184}
185
186impl IntrusiveMailbox {
187    /// Create a new empty mailbox with `FREELIST_CAPACITY` pre-allocated nodes.
188    pub fn new() -> Self {
189        let mb = IntrusiveMailbox {
190            head: AtomicUsize::new(0),
191            pool: NodePool::new(),
192        };
193        // Pre-allocate nodes to avoid heap allocation in IRQ context.
194        mb.pool.preallocate(FREELIST_CAPACITY);
195        mb
196    }
197
198    /// Create a new empty mailbox without pre-allocation.
199    /// Only for const contexts (e.g., static initialisers); the caller must
200    /// call `preallocate_nodes()` at runtime before use in IRQ context.
201    pub const fn new_empty() -> Self {
202        IntrusiveMailbox {
203            head: AtomicUsize::new(0),
204            pool: NodePool::new(),
205        }
206    }
207
208    /// Pre-allocate additional nodes at runtime.
209    pub fn preallocate_nodes(&self, count: usize) {
210        self.pool.preallocate(count);
211    }
212
213    /// Push a message onto the mailbox (LIFO : inserted at head).
214    ///
215    /// Tries the pre-allocated node pool first. Falls back to heap
216    /// allocation only if the pool is empty.  In IRQ context the pool
217    /// should never be empty if `FREELIST_CAPACITY` is large enough.
218    pub fn push(&self, msg: &[u8]) -> Result<(), MailboxError> {
219        // Try pool first (IRQ-safe, no heap alloc).
220        let node_ptr = if let Some(ptr) = self.pool.try_pop_raw() {
221            // Write the message payload into the recycled node.
222            let node = unsafe { &mut *ptr };
223            let len = msg.len().min(256);
224            node.data = IpcMessage::new(0);
225            node.data.payload[..len].copy_from_slice(&msg[..len]);
226            ptr as usize
227        } else {
228            // Fall back to heap allocation.
229            let node = MailboxMessage::try_from_slice(msg).ok_or(MailboxError::AllocFailed)?;
230            Box::into_raw(Box::new(node)) as usize
231        };
232
233        loop {
234            let current = self.head.load(Ordering::Acquire);
235            unsafe {
236                (*(node_ptr as *mut MailboxMessage))
237                    .next
238                    .store(current & PTR_MASK, Ordering::Relaxed);
239            }
240            let new_tagged = tag_ptr(node_ptr);
241            if self
242                .head
243                .compare_exchange_weak(current, new_tagged, Ordering::Release, Ordering::Relaxed)
244                .is_ok()
245            {
246                return Ok(());
247            }
248        }
249    }
250
251    /// Pop a message from the mailbox (LIFO : from head).
252    ///
253    /// Copies the message data out of the intrusive node, then returns the
254    /// node to the pre-allocated pool.  The caller receives an owned
255    /// `IpcMessage` value : no pointers into recycled memory.
256    pub fn pop(&self) -> Option<IpcMessage> {
257        loop {
258            let current = self.head.load(Ordering::Acquire);
259            if current & PTR_MASK == 0 {
260                return None;
261            }
262            let current_ptr = untag_ptr(current);
263            let next = unsafe { (*current_ptr).next.load(Ordering::Relaxed) };
264            let new_tagged = tag_ptr(next);
265            if self
266                .head
267                .compare_exchange_weak(current, new_tagged, Ordering::Acquire, Ordering::Relaxed)
268                .is_ok()
269            {
270                // P0 fix: copy the message out BEFORE recycling the node.
271                // This eliminates the UAF: the caller gets an owned value,
272                // not a pointer into pool-managed memory.
273                let msg = unsafe { (*current_ptr).data };
274                // Return the node to the pool for reuse.
275                self.pool.push_raw(current_ptr);
276                return Some(msg);
277            }
278        }
279    }
280
281    /// Whether the mailbox is empty.
282    pub fn is_empty(&self) -> bool {
283        self.head.load(Ordering::Relaxed) & PTR_MASK == 0
284    }
285}
286
287impl MailboxMessage {
288    /// Allocate a new `MailboxMessage` from a byte slice.
289    fn try_from_slice(data: &[u8]) -> Option<MailboxMessage> {
290        let len = data.len().min(256);
291        let mut msg = MailboxMessage {
292            next: AtomicUsize::new(0),
293            data: IpcMessage::new(0),
294        };
295        msg.data.payload[..len].copy_from_slice(&data[..len]);
296        Some(msg)
297    }
298}
299
300// ---------------------------------------------------------------------------
301// IpcTransport impl for IntrusiveMailbox
302// ---------------------------------------------------------------------------
303
304impl IpcTransport for IntrusiveMailbox {
305    fn level(&self) -> TransportLevel {
306        TransportLevel::TypeSafe
307    }
308
309    fn capabilities(&self) -> TransportCapabilities {
310        TransportCapabilities {
311            max_message_size: 256,
312            blocking: false,
313            zero_copy: false,
314            vectored: false,
315            directions: 1,
316            estimated_cost_cycles: 10,
317        }
318    }
319
320    fn name(&self) -> &'static str {
321        "mailbox"
322    }
323}
324
325impl IpcProducer for IntrusiveMailbox {
326    fn send(&self, msg: &[u8]) -> Result<(), IpcError> {
327        self.push(msg).map_err(|_| IpcError::TransportFailed)
328    }
329
330    fn try_send(&self, msg: &[u8]) -> Result<(), IpcError> {
331        self.send(msg)
332    }
333}
334
335impl IpcConsumer for IntrusiveMailbox {
336    fn recv(&self, buf: &mut [u8]) -> Result<usize, IpcError> {
337        match self.pop() {
338            Some(msg) => {
339                let len = msg.payload.len().min(buf.len());
340                buf[..len].copy_from_slice(&msg.payload[..len]);
341                Ok(len)
342            }
343            None => Err(IpcError::WouldBlock),
344        }
345    }
346
347    fn try_recv(&self, buf: &mut [u8]) -> Result<Option<usize>, IpcError> {
348        match self.recv(buf) {
349            Ok(n) => Ok(Some(n)),
350            Err(IpcError::WouldBlock) => Ok(None),
351            Err(e) => Err(e),
352        }
353    }
354}
355
356// ---------------------------------------------------------------------------
357// Tests
358// ---------------------------------------------------------------------------
359
360#[cfg(test)]
361mod tests {
362    use super::*;
363
364    #[test]
365    fn push_pop_single() {
366        let mb = IntrusiveMailbox::new();
367        mb.push(b"hello").unwrap();
368        let msg = mb.pop().unwrap();
369        assert_eq!(&msg.payload[..5], b"hello");
370    }
371
372    #[test]
373    fn push_pop_lifo_order() {
374        let mb = IntrusiveMailbox::new();
375        mb.push(b"first").unwrap();
376        mb.push(b"second").unwrap();
377        // LIFO: second popped first
378        let msg2 = mb.pop().unwrap();
379        assert_eq!(&msg2.payload[..6], b"second");
380        let msg1 = mb.pop().unwrap();
381        assert_eq!(&msg1.payload[..5], b"first");
382    }
383
384    #[test]
385    fn pop_empty() {
386        let mb = IntrusiveMailbox::new();
387        assert!(mb.pop().is_none());
388    }
389}
strat9_kernel/ipc/mailbox.rs

strat9_kernel/ipc/
mailbox.rs
