use crate::smp::SpinLock;
use crate::tcb::KERNEL;
use core::cell::UnsafeCell;
use core::sync::atomic::{AtomicPtr, AtomicU32, Ordering};
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub struct LockId(pub u32);
impl LockId {
pub const fn new(raw: u32) -> LockId {
LockId(raw)
}
}
static NEXT_LOCK_ID: AtomicU32 = AtomicU32::new(1);
fn alloc_lock_id() -> LockId {
LockId(NEXT_LOCK_ID.fetch_add(1, Ordering::Relaxed))
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum LockError {
Timeout,
OrderViolation {
held: LockId,
requested: LockId,
},
AlreadyOwnedBySelf,
NotRunning,
}
impl core::fmt::Display for LockError {
fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
match *self {
LockError::Timeout => write!(f, "lock acquisition timed out"),
LockError::OrderViolation { held, requested } => write!(
f,
"lock order violation: holding {} while acquiring {} \
(acquire in increasing LockId order)",
held.0, requested.0
),
LockError::AlreadyOwnedBySelf => write!(f, "lock already held by this task"),
LockError::NotRunning => write!(f, "scheduler not running"),
}
}
}
pub use crate::tcb::MAX_HELD_LOCKS;
pub struct MutexHeader {
id: LockId,
owner: AtomicU32,
pub(crate) state: SpinLock,
pub(crate) release: fn(&MutexHeader),
}
pub struct Mutex<T> {
pub(crate) header: MutexHeader,
data: UnsafeCell<T>,
}
unsafe impl<T: Send> Sync for Mutex<T> {}
unsafe impl<T: Send> Send for Mutex<T> {}
impl<T> Mutex<T> {
pub fn new(data: T) -> Self {
Mutex {
header: MutexHeader {
id: alloc_lock_id(),
owner: AtomicU32::new(0),
state: SpinLock::new(),
release: release_shim,
},
data: UnsafeCell::new(data),
}
}
pub const fn with_id(id: LockId, data: T) -> Self {
Mutex {
header: MutexHeader {
id,
owner: AtomicU32::new(0),
state: SpinLock::new(),
release: release_shim,
},
data: UnsafeCell::new(data),
}
}
#[inline]
pub fn id(&self) -> LockId {
self.header.id
}
#[inline]
pub fn owner(&self) -> u32 {
self.header.owner.load(Ordering::Relaxed)
}
#[inline]
pub fn is_free(&self) -> bool {
self.owner() == 0
}
fn try_acquire(&self) -> Result<bool, LockError> {
let me = crate::scheduler::current_task_id();
if me == 0 {
return Err(LockError::NotRunning);
}
let _g = self.header.state.lock();
let owner = self.header.owner.load(Ordering::Relaxed);
if owner == me {
return Err(LockError::AlreadyOwnedBySelf);
}
if owner != 0 {
return Ok(false);
}
unsafe { held_check_order(self.header.id)? };
self.header.owner.store(me, Ordering::Relaxed);
unsafe { held_push(self.header.id) };
Ok(true)
}
pub fn try_lock(&self) -> Result<MutexGuard<'_, T>, LockError> {
if self.try_acquire()? {
return Ok(MutexGuard { lock: self });
}
Err(LockError::Timeout)
}
pub fn lock(&self) -> Result<MutexGuard<'_, T>, LockError> {
loop {
let g = crate::critical::enter();
if self.try_acquire()? {
drop(g);
return Ok(MutexGuard { lock: self });
}
let outcome = unsafe { crate::scheduler::mark_blocked_locked(self.header.id.0, 0) };
drop(g); if outcome == crate::scheduler::BlockOutcome::NoCurrentTask {
return Err(LockError::NotRunning);
}
}
}
pub fn try_lock_for(&self, timeout_ms: u64) -> Result<MutexGuard<'_, T>, LockError> {
let deadline = crate::scheduler::deadline_after_ticks(ms_to_ticks(timeout_ms));
loop {
let g = crate::critical::enter();
if self.try_acquire()? {
drop(g);
return Ok(MutexGuard { lock: self });
}
if crate::scheduler::tick_count() >= deadline {
drop(g);
return Err(LockError::Timeout);
}
let outcome =
unsafe { crate::scheduler::mark_blocked_locked(self.header.id.0, deadline) };
drop(g);
if outcome == crate::scheduler::BlockOutcome::NoCurrentTask {
return Err(LockError::NotRunning);
}
}
}
pub fn lock_with_backoff<F, R>(
&self,
timeout_ms: u64,
attempts: u32,
mut attempt: F,
) -> Result<R, LockError>
where
F: FnMut(&Mutex<T>) -> Result<R, LockError>,
{
let mut tries = 0u32;
loop {
match attempt(self) {
Ok(ok) => return Ok(ok),
Err(LockError::Timeout) if tries + 1 < attempts => {
let released = release_all_held_locks();
backoff(tries, released + (timeout_ms as usize % 3));
tries += 1;
}
Err(e) => return Err(e),
}
}
}
pub fn unlock(&self) {
self.release_lock();
}
pub(crate) fn release_lock(&self) {
(self.header.release)(&self.header);
}
}
#[must_use = "the lock is held only for the lifetime of this guard"]
pub struct MutexGuard<'a, T> {
lock: &'a Mutex<T>,
}
impl<T> core::ops::Deref for MutexGuard<'_, T> {
type Target = T;
#[inline]
fn deref(&self) -> &T {
unsafe { &*self.lock.data.get() }
}
}
impl<T> core::ops::DerefMut for MutexGuard<'_, T> {
#[inline]
fn deref_mut(&mut self) -> &mut T {
unsafe { &mut *self.lock.data.get() }
}
}
impl<T> Drop for MutexGuard<'_, T> {
#[inline]
fn drop(&mut self) {
self.lock.release_lock();
}
}
fn release_shim(header: &MutexHeader) {
{
let _g = header.state.lock();
header.owner.store(0, Ordering::Relaxed);
}
unsafe { held_remove(header.id) };
crate::scheduler::wake_blocked_on(header.id.0);
}
fn ms_to_ticks(ms: u64) -> u64 {
let slice_ns = crate::scheduler::slice_ns();
if slice_ns == 0 {
return ms;
}
ms.saturating_mul(1_000_000).div_ceil(slice_ns)
}
pub fn backoff(attempt: u32, jitter: usize) {
let ticks = (1u64 << attempt.min(6)) + (jitter as u64 % 3);
crate::scheduler::sleep_ticks(ticks);
}
static REGISTRY: SpinLock = SpinLock::new();
static REGISTRY_SLOTS: [AtomicPtr<MutexHeader>; 8] =
[const { AtomicPtr::new(core::ptr::null_mut()) }; 8];
impl<T: Send> Mutex<T> {
pub fn register(&'static self) {
let _g = REGISTRY.lock();
let slot_ptr = &self.header as *const MutexHeader as *mut MutexHeader;
for slot in REGISTRY_SLOTS.iter() {
if slot.load(Ordering::Relaxed).is_null() {
let _ = slot.compare_exchange(
core::ptr::null_mut(),
slot_ptr,
Ordering::Relaxed,
Ordering::Relaxed,
);
return;
}
}
}
}
fn registered(id: LockId) -> Option<&'static MutexHeader> {
let _g = REGISTRY.lock();
for slot in REGISTRY_SLOTS.iter() {
let p = slot.load(Ordering::Relaxed);
if !p.is_null() {
let h = unsafe { &*p };
if h.id == id {
return Some(h);
}
}
}
None
}
unsafe fn held_check_order(id: LockId) -> Result<(), LockError> {
let me = KERNEL.current();
if me.is_null() {
return Ok(());
}
let n = (*me).held_count as usize;
if n == 0 || n > MAX_HELD_LOCKS {
return Ok(());
}
let last = LockId((*me).held_locks[n - 1]);
if id.0 <= last.0 {
return Err(LockError::OrderViolation {
held: last,
requested: id,
});
}
Ok(())
}
unsafe fn held_push(id: LockId) {
let me = KERNEL.current();
if me.is_null() {
return;
}
let n = (*me).held_count as usize;
if n < MAX_HELD_LOCKS {
(*me).held_locks[n] = id.0;
(*me).held_count = (n + 1) as u8;
}
}
unsafe fn held_remove(id: LockId) {
let me = KERNEL.current();
if me.is_null() {
return;
}
let n = ((*me).held_count as usize).min(MAX_HELD_LOCKS);
let mut k = 0;
while k < n {
if (*me).held_locks[k] == id.0 {
let mut j = k;
while j + 1 < n {
(*me).held_locks[j] = (*me).held_locks[j + 1];
j += 1;
}
(*me).held_count -= 1;
return;
}
k += 1;
}
}
unsafe fn held_clear() {
let me = KERNEL.current();
if !me.is_null() {
(*me).held_count = 0;
}
}
pub fn held_count() -> usize {
let g = crate::critical::enter();
let n = unsafe {
let me = KERNEL.current();
if me.is_null() {
0
} else {
(*me).held_count as usize
}
};
drop(g);
n
}
pub fn release_all_held_locks() -> usize {
let mut ids = [LockId(0); MAX_HELD_LOCKS];
let mut n = 0usize;
{
let g = crate::critical::enter();
unsafe {
let me = KERNEL.current();
if !me.is_null() {
n = ((*me).held_count as usize).min(MAX_HELD_LOCKS);
let mut k = 0;
while k < n {
ids[k] = LockId((*me).held_locks[k]);
k += 1;
}
held_clear();
}
}
drop(g);
}
let mut released = 0;
for id in ids.iter().take(n) {
if let Some(h) = registered(*id) {
(h.release)(h);
released += 1;
}
}
released
}