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::{AtomicUsize, Ordering};
17
18use super::transport::{
19    IpcConsumer, IpcError, IpcProducer, IpcTransport, TransportCapabilities, TransportLevel,
20};
21use crate::ipc::message::IpcMessage;
22
23// ---------------------------------------------------------------------------
24// Tagged-pointer constants (x86-64 4-level paging only)
25// ---------------------------------------------------------------------------
26
27#[cfg(target_arch = "x86_64")]
28const TAG_SHIFT: usize = 48;
29#[cfg(target_arch = "x86_64")]
30const TAG_MASK: usize = 0xFFFF_0000_0000_0000;
31#[cfg(target_arch = "x86_64")]
32const PTR_MASK: usize = !TAG_MASK;
33
34#[cfg(not(target_arch = "x86_64"))]
35compile_error!("IntrusiveMailbox tagged-pointer requires x86-64 4-level paging. "
36    "See PML5 (TAG_SHIFT=57) or node-index allocator for other architectures.");
37
38static TAG_COUNTER: AtomicUsize = AtomicUsize::new(0);
39
40/// Encode a wrapped tag into the upper bits of a pointer value.
41fn tag_ptr(ptr: usize) -> usize {
42    let tag = TAG_COUNTER.fetch_add(1, Ordering::Relaxed) & 0xFFFF;
43    (ptr & PTR_MASK) | (tag << TAG_SHIFT)
44}
45
46/// Strip the tag and recover the real pointer.
47fn untag_ptr(tagged: usize) -> *mut MailboxMessage {
48    (tagged & PTR_MASK) as *mut MailboxMessage
49}
50
51// ---------------------------------------------------------------------------
52// MailboxError
53// ---------------------------------------------------------------------------
54
55/// Errors from mailbox operations.
56#[derive(Debug, Clone, Copy, PartialEq, Eq)]
57pub enum MailboxError {
58    /// Allocation of a new message node failed.
59    AllocFailed,
60}
61
62// ---------------------------------------------------------------------------
63// MailboxMessage : intrusive node
64// ---------------------------------------------------------------------------
65
66/// A single message node in the intrusive linked list.
67#[repr(C)]
68pub struct MailboxMessage {
69    /// Intrusive link to the next node (null = end of list).
70    next: AtomicUsize,
71    /// Message payload.
72    pub data: IpcMessage,
73}
74
75// ---------------------------------------------------------------------------
76// IntrusiveMailbox
77// ---------------------------------------------------------------------------
78
79/// A lock-free LIFO mailbox (stack) for kernel-internal IPC.
80///
81/// Messages are pushed atomically to the head of an intrusive linked list
82/// and popped from the head.  This is **not** a FIFO queue : message order
83/// is reversed on reception.
84///
85/// # Use case
86///
87/// Use for notification-style IPC between trusted kernel components where
88/// low latency (~10 cycles) matters more than message ordering.  For
89/// FIFO-guaranteed IPC, use [`LockFreeRing`](super::lockfree_ring::LockFreeRing).
90#[derive(Debug)]
91pub struct IntrusiveMailbox {
92    head: AtomicUsize,
93}
94
95impl IntrusiveMailbox {
96    /// Create a new empty mailbox.
97    pub const fn new() -> Self {
98        IntrusiveMailbox {
99            head: AtomicUsize::new(0),
100        }
101    }
102
103    /// Push a message onto the mailbox (LIFO : inserted at head).
104    ///
105    /// Allocates a new `MailboxMessage` from the kernel heap.
106    /// This allocation is the primary cost; for a deterministic fast path
107    /// consider a pre-allocated freelist (see design doc §12.15).
108    pub fn push(&self, msg: &[u8]) -> Result<(), MailboxError> {
109        let node = MailboxMessage::try_from_slice(msg).ok_or(MailboxError::AllocFailed)?;
110        let node_ptr = Box::into_raw(alloc::boxed::Box::new(node)) as usize;
111
112        loop {
113            let current = self.head.load(Ordering::Acquire);
114            unsafe {
115                (*(node_ptr as *mut MailboxMessage))
116                    .next
117                    .store(current & PTR_MASK, Ordering::Relaxed);
118            }
119            let new_tagged = tag_ptr(node_ptr);
120            if self
121                .head
122                .compare_exchange_weak(current, new_tagged, Ordering::Release, Ordering::Relaxed)
123                .is_ok()
124            {
125                return Ok(());
126            }
127        }
128    }
129
130    /// Pop a message from the mailbox (LIFO : from head).
131    pub fn pop(&self) -> Option<alloc::boxed::Box<MailboxMessage>> {
132        loop {
133            let current = self.head.load(Ordering::Acquire);
134            if current & PTR_MASK == 0 {
135                return None;
136            }
137            let current_ptr = untag_ptr(current);
138            let next = unsafe { (*current_ptr).next.load(Ordering::Relaxed) };
139            let new_tagged = tag_ptr(next);
140            if self
141                .head
142                .compare_exchange_weak(current, new_tagged, Ordering::Acquire, Ordering::Relaxed)
143                .is_ok()
144            {
145                return Some(unsafe { alloc::boxed::Box::from_raw(current_ptr) });
146            }
147        }
148    }
149
150    /// Whether the mailbox is empty.
151    pub fn is_empty(&self) -> bool {
152        self.head.load(Ordering::Relaxed) & PTR_MASK == 0
153    }
154}
155
156impl MailboxMessage {
157    /// Allocate a new `MailboxMessage` from a byte slice.
158    fn try_from_slice(data: &[u8]) -> Option<MailboxMessage> {
159        let len = data.len().min(256);
160        let mut msg = MailboxMessage {
161            next: AtomicUsize::new(0),
162            data: IpcMessage::new(0),
163        };
164        msg.data.payload[..len].copy_from_slice(&data[..len]);
165        Some(msg)
166    }
167}
168
169// ---------------------------------------------------------------------------
170// IpcTransport impl for IntrusiveMailbox
171// ---------------------------------------------------------------------------
172
173impl IpcTransport for IntrusiveMailbox {
174    fn level(&self) -> TransportLevel {
175        TransportLevel::TypeSafe
176    }
177
178    fn capabilities(&self) -> TransportCapabilities {
179        TransportCapabilities {
180            max_message_size: 256,
181            blocking: false,
182            zero_copy: false,
183            estimated_cost_cycles: 10,
184        }
185    }
186
187    fn name(&self) -> &'static str {
188        "mailbox"
189    }
190}
191
192impl IpcProducer for IntrusiveMailbox {
193    fn send(&self, msg: &[u8]) -> Result<(), IpcError> {
194        self.push(msg).map_err(|_| IpcError::TransportFailed)
195    }
196
197    fn try_send(&self, msg: &[u8]) -> Result<(), IpcError> {
198        self.send(msg)
199    }
200}
201
202impl IpcConsumer for IntrusiveMailbox {
203    fn recv(&self, buf: &mut [u8]) -> Result<usize, IpcError> {
204        match self.pop() {
205            Some(node) => {
206                let len = node.data.payload.len().min(buf.len());
207                buf[..len].copy_from_slice(&node.data.payload[..len]);
208                Ok(len)
209            }
210            None => Err(IpcError::WouldBlock),
211        }
212    }
213
214    fn try_recv(&self, buf: &mut [u8]) -> Result<Option<usize>, IpcError> {
215        match self.recv(buf) {
216            Ok(n) => Ok(Some(n)),
217            Err(IpcError::WouldBlock) => Ok(None),
218            Err(e) => Err(e),
219        }
220    }
221}
222
223// ---------------------------------------------------------------------------
224// Tests
225// ---------------------------------------------------------------------------
226
227#[cfg(test)]
228mod tests {
229    use super::*;
230
231    #[test]
232    fn push_pop_single() {
233        let mb = IntrusiveMailbox::new();
234        mb.push(b"hello").unwrap();
235        let node = mb.pop().unwrap();
236        assert_eq!(&node.data.payload[..5], b"hello");
237    }
238
239    #[test]
240    fn push_pop_lifo_order() {
241        let mb = IntrusiveMailbox::new();
242        mb.push(b"first").unwrap();
243        mb.push(b"second").unwrap();
244        // LIFO: second popped first
245        let node2 = mb.pop().unwrap();
246        assert_eq!(&node2.data.payload[..6], b"second");
247        let node1 = mb.pop().unwrap();
248        assert_eq!(&node1.data.payload[..5], b"first");
249    }
250
251    #[test]
252    fn pop_empty() {
253        let mb = IntrusiveMailbox::new();
254        assert!(mb.pop().is_none());
255    }
256}
strat9_kernel/ipc/mailbox.rs

strat9_kernel/ipc/
mailbox.rs
