Skip to main content

orbit_atomic/
table.rs

1//! The slot table: in shared memory for an SHM fleet, on the heap otherwise.
2
3use std::collections::HashMap;
4use std::ptr::NonNull;
5use std::sync::atomic::{AtomicU8, AtomicU32, AtomicU64, Ordering};
6use std::sync::{Arc, LazyLock, Mutex, MutexGuard, Weak};
7
8use orbit_core::Fleet;
9#[cfg(unix)]
10use orbit_core::process::ProcessOwner;
11#[cfg(unix)]
12use orbit_core::shm::ShmRegion;
13
14use crate::wake::Wake;
15use crate::{Error, Kind, OrbitalId, Result};
16
17/// Reserved Orbit SHM kind for the table.
18pub const ATOMIC_KIND: u8 = 174;
19
20/// How many values one table can declare between two resets.
21///
22/// Compile-time geometry: `ORBIT_ATOMIC_CAPACITY` in the application's
23/// `.cargo/config.toml` overrides the default. Must be a power of two and
24/// fit the 24-bit slot index of an id. Peers built with a different value
25/// are refused when they open the table.
26pub const ATOMIC_CAPACITY: usize = orbit_core::compile::usize_from_env(
27    option_env!("ORBIT_ATOMIC_CAPACITY"),
28    4_096,
29);
30
31const _: () = assert!(ATOMIC_CAPACITY.is_power_of_two());
32const _: () = assert!(ATOMIC_CAPACITY <= 1 << crate::id::SLOT_BITS);
33const _: () = assert!(size_of::<Slot>() == 64);
34
35const SLOT_EMPTY: u8 = 0;
36const SLOT_OCCUPIED: u8 = 1;
37
38/// The epoch of a table that has never been reset. Zero is never current,
39/// so an id of all zeroes after its kind names nothing.
40const FIRST_EPOCH: u32 = 1;
41
42/// One value, laid out for shared memory: a cache line of its own, so two
43/// hot values never contend, and every field atomic, so the mapping is
44/// never borrowed `&mut` while another process reads it. All zeroes is an
45/// empty slot.
46#[repr(C, align(64))]
47pub(crate) struct Slot {
48    state: AtomicU8,
49    kind: AtomicU8,
50    _reserved: [u8; 6],
51    pub(crate) value: AtomicU64,
52    pub(crate) wake: Wake,
53    _padding: [u8; 40],
54}
55
56impl Slot {
57    /// By the one caller that drew this index from `next`.
58    fn install(
59        &self,
60        kind: Kind,
61        word: u64,
62    ) {
63        self.kind.store(kind as u8, Ordering::Relaxed);
64        self.value.store(word, Ordering::Relaxed);
65        self.state.store(SLOT_OCCUPIED, Ordering::Release);
66    }
67
68    /// `Acquire` on `state` publishes what `install` wrote.
69    fn holds(
70        &self,
71        kind: Kind,
72    ) -> bool {
73        self.state.load(Ordering::Acquire) == SLOT_OCCUPIED
74            && self.kind.load(Ordering::Relaxed) == kind as u8
75    }
76
77    /// Only at a quiescent reset.
78    fn clear(&self) {
79        self.state.store(SLOT_EMPTY, Ordering::Release);
80        self.kind.store(0, Ordering::Relaxed);
81        self.value.store(0, Ordering::Relaxed);
82        self.wake.clear();
83    }
84}
85
86pub(crate) struct Table {
87    backing: Backing,
88    /// Serializes resets within this process; the region's lock does the
89    /// same between processes.
90    reset_lock: Mutex<()>,
91}
92
93enum Backing {
94    Memory {
95        /// Held so the fleet's address, which keys the registry, cannot be
96        /// reused by another fleet while this table lives.
97        _fleet: Arc<Fleet>,
98        epoch: AtomicU32,
99        next: AtomicU32,
100        slots: Box<[Slot]>,
101    },
102    #[cfg(unix)]
103    Shm { region: ShmRegion, name: Box<str> },
104}
105
106impl Table {
107    fn memory(fleet: Arc<Fleet>) -> Self {
108        // SAFETY: a slot is atomics and bytes; all zeroes is an empty slot.
109        let slots = (0..ATOMIC_CAPACITY)
110            .map(|_| unsafe { std::mem::zeroed::<Slot>() })
111            .collect();
112        Self {
113            backing: Backing::Memory {
114                _fleet: fleet,
115                epoch: AtomicU32::new(FIRST_EPOCH),
116                next: AtomicU32::new(0),
117                slots,
118            },
119            reset_lock: Mutex::new(()),
120        }
121    }
122
123    fn epoch(&self) -> &AtomicU32 {
124        match &self.backing {
125            Backing::Memory { epoch, .. } => epoch,
126            #[cfg(unix)]
127            Backing::Shm { region, .. } => &shm::header(region).epoch,
128        }
129    }
130
131    fn next(&self) -> &AtomicU32 {
132        match &self.backing {
133            Backing::Memory { next, .. } => next,
134            #[cfg(unix)]
135            Backing::Shm { region, .. } => &shm::header(region).next,
136        }
137    }
138
139    fn slots(&self) -> &[Slot] {
140        match &self.backing {
141            Backing::Memory { slots, .. } => slots,
142            #[cfg(unix)]
143            Backing::Shm { region, .. } => shm::slots(region),
144        }
145    }
146
147    /// Hand out the next slot. One `fetch_add` decides the owner of an
148    /// index; the load before it keeps a full table from being written at
149    /// all, so `next` passes the capacity by at most the callers racing in
150    /// one window and never wraps.
151    pub(crate) fn allocate(
152        &self,
153        kind: Kind,
154        word: u64,
155    ) -> Result<(OrbitalId, NonNull<Slot>)> {
156        let full = || Error::Full { capacity: ATOMIC_CAPACITY };
157        let next = self.next();
158        if next.load(Ordering::Relaxed) as usize >= ATOMIC_CAPACITY {
159            return Err(full());
160        }
161        let index = next.fetch_add(1, Ordering::Relaxed);
162        let slot = self.slots().get(index as usize).ok_or_else(full)?;
163        slot.install(kind, word);
164        let epoch = self.epoch().load(Ordering::Acquire);
165        Ok((OrbitalId::new(kind, index, epoch), NonNull::from(slot)))
166    }
167
168    /// Resolve an id to its slot. Reads only.
169    pub(crate) fn open(
170        &self,
171        id: OrbitalId,
172        expected: Kind,
173    ) -> Result<NonNull<Slot>> {
174        let slot =
175            self.slots().get(id.slot() as usize).ok_or(Error::Stale(id))?;
176        if self.epoch().load(Ordering::Acquire) != id.epoch() {
177            return Err(Error::Stale(id));
178        }
179        if id.kind() != expected {
180            return Err(Error::KindMismatch { id, expected });
181        }
182        if !slot.holds(expected) {
183            return Err(Error::Stale(id));
184        }
185        Ok(NonNull::from(slot))
186    }
187
188    /// Start a new epoch with every slot empty. The caller guarantees that
189    /// nothing else uses the table.
190    pub(crate) fn reset(&self) -> Result<()> {
191        let _local = lock_unpoisoned(&self.reset_lock);
192        #[cfg(unix)]
193        let _process = match &self.backing {
194            Backing::Shm { region, .. } => Some(region.lock_exclusive()?),
195            Backing::Memory { .. } => None,
196        };
197        let epoch = self.epoch();
198        let advanced = epoch
199            .load(Ordering::Acquire)
200            .checked_add(1)
201            .ok_or(Error::EpochExhausted)?;
202        epoch.store(advanced, Ordering::Release);
203        for slot in self.slots() {
204            slot.clear();
205        }
206        self.next().store(0, Ordering::Release);
207        Ok(())
208    }
209
210    /// Remove the SHM object. Existing mappings stay valid until their
211    /// processes drop them; this process maps the name afresh next time.
212    #[cfg(unix)]
213    pub(crate) fn unlink(&self) -> Result<()> {
214        match &self.backing {
215            Backing::Memory { .. } => self.reset(),
216            Backing::Shm { region, name } => {
217                let mut tables = shm::TABLES.lock()?;
218                region.unlink()?;
219                tables.remove(&**name);
220                Ok(())
221            }
222        }
223    }
224}
225
226fn lock_unpoisoned<T>(mutex: &Mutex<T>) -> MutexGuard<'_, T> {
227    mutex.lock().unwrap_or_else(|error| error.into_inner())
228}
229
230type MemoryRegistry = HashMap<usize, Weak<Table>>;
231
232static MEMORY_TABLES: LazyLock<Mutex<MemoryRegistry>> =
233    LazyLock::new(|| Mutex::new(HashMap::new()));
234
235/// One table per in-memory fleet, found again by the fleet's address.
236pub(crate) fn memory_table(fleet: &Arc<Fleet>) -> Arc<Table> {
237    let identity = Arc::as_ptr(fleet) as usize;
238    let mut tables = lock_unpoisoned(&MEMORY_TABLES);
239    tables.retain(|_, table| table.strong_count() > 0);
240    if let Some(table) = tables.get(&identity).and_then(Weak::upgrade) {
241        return table;
242    }
243    let table = Arc::new(Table::memory(Arc::clone(fleet)));
244    tables.insert(identity, Arc::downgrade(&table));
245    table
246}
247
248#[cfg(unix)]
249pub(crate) use shm::table as shm_table;
250
251#[cfg(unix)]
252mod shm {
253    use std::sync::atomic::AtomicPtr;
254    use std::{io, ptr};
255
256    use super::*;
257
258    const MAGIC: u32 = 0x4f_52_42_4c; // "ORBL"
259    const VERSION: u16 = 1;
260
261    #[repr(C, align(64))]
262    pub(super) struct Header {
263        magic: u32,
264        version: u16,
265        header_size: u16,
266        capacity: u32,
267        slot_size: u32,
268        /// Advanced by every reset; an id carries the one it was minted in.
269        pub(super) epoch: AtomicU32,
270        /// The index the next allocation takes.
271        pub(super) next: AtomicU32,
272        _reserved: [u8; 40],
273    }
274
275    const _: () = assert!(size_of::<Header>() == 64);
276
277    const SEGMENT_SIZE: usize =
278        size_of::<Header>() + ATOMIC_CAPACITY * size_of::<Slot>();
279
280    pub(super) fn header(region: &ShmRegion) -> &Header {
281        // SAFETY: the region is `SEGMENT_SIZE` long, page aligned, and its
282        // header was written or validated at attach.
283        unsafe { &*region.as_ptr().cast::<Header>() }
284    }
285
286    pub(super) fn slots(region: &ShmRegion) -> &[Slot] {
287        // SAFETY: as above; the slots follow the header.
288        unsafe {
289            std::slice::from_raw_parts(
290                region.as_ptr().add(size_of::<Header>()).cast::<Slot>(),
291                ATOMIC_CAPACITY,
292            )
293        }
294    }
295
296    fn open_or_create(name: &str) -> Result<Table> {
297        let (region, _initialization_lock) =
298            ShmRegion::open_or_create_locked(name, SEGMENT_SIZE)?;
299        if region.created() {
300            // SAFETY: the mapping is `SEGMENT_SIZE` long and nobody else
301            // reads it before the initialization lock is released.
302            unsafe {
303                ptr::write_bytes(region.as_ptr(), 0, SEGMENT_SIZE);
304                ptr::write(
305                    region.as_ptr().cast::<Header>(),
306                    Header {
307                        magic: MAGIC,
308                        version: VERSION,
309                        header_size: size_of::<Header>() as u16,
310                        capacity: ATOMIC_CAPACITY as u32,
311                        slot_size: size_of::<Slot>() as u32,
312                        epoch: AtomicU32::new(FIRST_EPOCH),
313                        next: AtomicU32::new(0),
314                        _reserved: [0; 40],
315                    },
316                );
317            }
318        } else {
319            let header = header(&region);
320            if header.magic != MAGIC {
321                return Err(Error::Io(io::Error::new(
322                    io::ErrorKind::InvalidData,
323                    format!(
324                        "SHM segment {name} has wrong magic {:#010x} (expected {MAGIC:#010x})",
325                        header.magic
326                    ),
327                )));
328            }
329            if header.version != VERSION
330                || usize::from(header.header_size) != size_of::<Header>()
331                || header.capacity as usize != ATOMIC_CAPACITY
332                || header.slot_size as usize != size_of::<Slot>()
333            {
334                return Err(Error::Io(io::Error::new(
335                    io::ErrorKind::InvalidData,
336                    format!(
337                        "SHM segment {name} has an incompatible orbital table layout"
338                    ),
339                )));
340            }
341        }
342        Ok(Table {
343            backing: Backing::Shm { region, name: name.into() },
344            reset_lock: Mutex::new(()),
345        })
346    }
347
348    type TableMap = HashMap<Box<str>, Weak<Table>>;
349
350    struct Registry {
351        process: ProcessOwner,
352        tables: Mutex<TableMap>,
353    }
354
355    /// One mapping per table name in a process, and a registry of its own
356    /// for a fork child.
357    pub(super) struct Tables(AtomicPtr<Registry>);
358
359    pub(super) static TABLES: Tables = Tables(AtomicPtr::new(ptr::null_mut()));
360
361    impl Tables {
362        pub(super) fn lock(
363            &'static self
364        ) -> Result<MutexGuard<'static, TableMap>> {
365            let process = ProcessOwner::current()?;
366            loop {
367                let previous = self.0.load(Ordering::Acquire);
368                // SAFETY: published registries stay allocated until
369                // process exit.
370                if let Some(registry) = unsafe { previous.as_ref() }
371                    && registry.process.is_current()
372                {
373                    return Ok(lock_unpoisoned(&registry.tables));
374                }
375
376                // A fork child cannot lock a mutex inherited from its
377                // parent, and maps the tables again for itself.
378                let registry = Box::into_raw(Box::new(Registry {
379                    process,
380                    tables: Mutex::default(),
381                }));
382                if self
383                    .0
384                    .compare_exchange(
385                        previous,
386                        registry,
387                        Ordering::AcqRel,
388                        Ordering::Acquire,
389                    )
390                    .is_ok()
391                {
392                    // SAFETY: this registry is now published and retained.
393                    return Ok(lock_unpoisoned(unsafe { &(*registry).tables }));
394                }
395                // SAFETY: this candidate was never published.
396                drop(unsafe { Box::from_raw(registry) });
397            }
398        }
399    }
400
401    pub(crate) fn table(name: &str) -> Result<Arc<Table>> {
402        let mut tables = TABLES.lock()?;
403        tables.retain(|_, table| table.strong_count() != 0);
404        if let Some(table) = tables.get(name).and_then(Weak::upgrade) {
405            return Ok(table);
406        }
407        let table = Arc::new(open_or_create(name)?);
408        tables.insert(name.into(), Arc::downgrade(&table));
409        Ok(table)
410    }
411}