blob: 2af6ea9bf5bedee952c2a802f2e0bf142bb76832 [file]
// Copyright 2023 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
use crate::task::CurrentTask;
use starnix_uapi::errors::Errno;
use starnix_sync::{
DynamicLockTracking, InterruptibleEvent, LockDepMutex, LockLevel, LockLevelToken,
RwQueueInnerLock,
};
use std::collections::VecDeque;
use std::sync::Arc;
use lock_api as _;
#[cfg(any(test, debug_assertions))]
use lock_api::RawRwLock;
#[derive(Debug)]
pub struct RwQueue {
inner: LockDepMutex<RwQueueInner, RwQueueInnerLock>,
tracking: DynamicLockTracking,
// Used to inform our deadlock detector about the waiters in the queue.
#[cfg(any(test, debug_assertions))]
tracer: tracer::MutexTracer,
}
impl RwQueue {
pub fn new<L: LockLevel>() -> Self {
Self {
inner: Default::default(),
tracking: DynamicLockTracking::new::<L>(),
#[cfg(any(test, debug_assertions))]
tracer: Default::default(),
}
}
fn unlock_read(&self) {
self.inner.lock().unlock_read();
#[allow(
clippy::undocumented_unsafe_blocks,
reason = "Force documented unsafe blocks in Starnix"
)]
#[cfg(any(test, debug_assertions))]
unsafe {
self.tracer.unlock_shared();
}
}
fn unlock_write(&self) {
self.inner.lock().unlock_write();
#[allow(
clippy::undocumented_unsafe_blocks,
reason = "Force documented unsafe blocks in Starnix"
)]
#[cfg(any(test, debug_assertions))]
unsafe {
self.tracer.unlock_exclusive();
}
}
fn cancel_read(&self, event: &Arc<InterruptibleEvent>) {
self.inner.lock().cancel_read(event);
// SAFETY: Paired with `self.tracer.lock_shared()` in `Self::read`.
#[cfg(any(test, debug_assertions))]
unsafe {
self.tracer.unlock_shared();
}
}
fn cancel_write(&self, event: &Arc<InterruptibleEvent>) {
self.inner.lock().cancel_write(event);
// SAFETY: Paired with `self.tracer.lock_exclusive()` in `Self::write`.
#[cfg(any(test, debug_assertions))]
unsafe {
self.tracer.unlock_exclusive();
}
}
#[track_caller]
pub fn read<'a>(&'a self, current_task: &CurrentTask) -> Result<RwQueueReadGuard<'a>, Errno> {
let token = self.tracking.acquire();
#[cfg(any(test, debug_assertions))]
self.tracer.lock_shared();
let mut inner = self.inner.lock();
if !inner.try_read() {
let event = InterruptibleEvent::new();
let guard = event.begin_wait();
inner.waiters.push_back(Waiter::Reader(event.clone()));
std::mem::drop(inner);
current_task.block_until(guard, zx::MonotonicInstant::INFINITE).map_err(|e| {
self.cancel_read(&event);
e
})?;
}
Ok(RwQueueReadGuard { queue: self, _token: token })
}
#[track_caller]
pub fn write<'a>(&'a self, current_task: &CurrentTask) -> Result<RwQueueWriteGuard<'a>, Errno> {
let token = self.tracking.acquire();
#[cfg(any(test, debug_assertions))]
self.tracer.lock_exclusive();
let mut inner = self.inner.lock();
if !inner.try_write() {
let event = InterruptibleEvent::new();
let guard = event.begin_wait();
inner.waiters.push_back(Waiter::Writer(event.clone()));
std::mem::drop(inner);
current_task.block_until(guard, zx::MonotonicInstant::INFINITE).map_err(|e| {
self.cancel_write(&event);
e
})?;
}
Ok(RwQueueWriteGuard { queue: self, _token: token })
}
}
/// The queue is ready for any operation.
const READY: usize = 0;
/// The queue has exactly one writer.
const WRITER: usize = 0b01;
/// Each reader in the queue increments the state by this amount.
const READER: usize = 0b10;
/// A writer is currently running.
fn has_writer(state: usize) -> bool {
state & WRITER != 0
}
/// At least one reader is currently running.
fn has_reader(state: usize) -> bool {
state >= READER
}
fn debug_assert_consistent(state: usize) {
debug_assert!(!has_writer(state) || !has_reader(state));
}
#[derive(Debug, Clone)]
enum Waiter {
Reader(Arc<InterruptibleEvent>),
Writer(Arc<InterruptibleEvent>),
}
#[derive(Debug, Default)]
struct RwQueueInner {
/// What operations are currently ongoing.
///
/// See READY, READER, WRITER above for what these bits mean.
state: usize,
/// The operations that are waiting for the ongoing operations to complete.
waiters: VecDeque<Waiter>,
}
impl RwQueueInner {
fn has_waiters(&self) -> bool {
!self.waiters.is_empty()
}
fn try_read(&mut self) -> bool {
debug_assert_consistent(self.state);
if !has_writer(self.state) && !self.has_waiters() {
if let Some(new_state) = self.state.checked_add(READER) {
self.state = new_state;
return true;
}
}
false
}
fn try_write(&mut self) -> bool {
debug_assert_consistent(self.state);
if self.state == READY && !self.has_waiters() {
self.state += WRITER;
true
} else {
false
}
}
fn unlock_read(&mut self) {
debug_assert!(has_reader(self.state) && !has_writer(self.state));
self.state -= READER;
if !has_reader(self.state) && self.has_waiters() {
self.notify_next();
}
}
fn unlock_write(&mut self) {
debug_assert!(has_writer(self.state) && !has_reader(self.state));
self.state -= WRITER;
if self.has_waiters() {
self.notify_next();
}
}
fn notify_next(&mut self) {
while let Some(waiter) = self.waiters.front() {
match waiter {
Waiter::Reader(reader) => {
if has_writer(self.state) {
return;
}
// We need to use `checked_add` to ensure we do not
// overflow the number of readers. If that happens, we just
// need to wait for the enormous number of readers to finish.
let Some(new_state) = self.state.checked_add(READER) else {
return;
};
self.state = new_state;
reader.notify();
}
Waiter::Writer(writer) => {
if has_reader(self.state) || has_writer(self.state) {
return;
}
// We can never overflow writers because we only let one
// through at a time.
self.state += WRITER;
writer.notify();
}
}
self.waiters.pop_front();
}
debug_assert_consistent(self.state);
}
fn remove_waiter(&mut self, event: &Arc<InterruptibleEvent>) -> bool {
let len_before = self.waiters.len();
self.waiters.retain(|waiter| {
let (Waiter::Reader(other) | Waiter::Writer(other)) = waiter;
!Arc::ptr_eq(event, other)
});
self.waiters.len() != len_before
}
fn cancel_read(&mut self, event: &Arc<InterruptibleEvent>) {
if !self.remove_waiter(event) {
// The event was already removed from the queue, so we're already holding a read lock.
// We should unlock to avoid leaving the queue locked.
self.unlock_read();
}
}
fn cancel_write(&mut self, event: &Arc<InterruptibleEvent>) {
if !self.remove_waiter(event) {
// The event was already removed from the queue, so we're already holding a write lock.
// We should unlock to avoid leaving the queue locked.
self.unlock_write();
} else if has_reader(self.state) {
// Readers may be blocked in the queue behind the writer we just removed. We should
// wake them up.
self.notify_next();
}
}
}
pub struct RwQueueReadGuard<'a> {
queue: &'a RwQueue,
_token: LockLevelToken,
}
impl<'a> Drop for RwQueueReadGuard<'a> {
fn drop(&mut self) {
self.queue.unlock_read();
}
}
pub struct RwQueueWriteGuard<'a> {
queue: &'a RwQueue,
_token: LockLevelToken,
}
impl<'a> Drop for RwQueueWriteGuard<'a> {
fn drop(&mut self) {
self.queue.unlock_write();
}
}
#[cfg(any(test, debug_assertions))]
mod tracer {
#[derive(Debug, Default)]
pub struct FakeRwLock {}
#[allow(
clippy::undocumented_unsafe_blocks,
reason = "Force documented unsafe blocks in Starnix"
)]
unsafe impl lock_api::RawRwLock for FakeRwLock {
const INIT: Self = Self {};
type GuardMarker = lock_api::GuardNoSend;
fn lock_shared(&self) {}
fn try_lock_shared(&self) -> bool {
false
}
unsafe fn unlock_shared(&self) {}
fn lock_exclusive(&self) {}
fn try_lock_exclusive(&self) -> bool {
false
}
unsafe fn unlock_exclusive(&self) {}
fn is_locked(&self) -> bool {
false
}
}
// We should replace this type with tracing_mutex::MutexId once that type is public.
pub type MutexTracer = tracing_mutex::lockapi::TracingWrapper<FakeRwLock>;
}
// We use tracing_mutex in tests and debug assertions, but we don't want to pull it in for
// production.
#[cfg(not(any(test, debug_assertions)))]
use tracing_mutex as _;
#[cfg(test)]
mod test {
use super::*;
use crate::task::dynamic_thread_spawner::SpawnRequestBuilder;
use crate::task::{Kernel, TaskFlags};
use crate::testing::*;
use futures::executor::block_on;
use futures::future::join_all;
use starnix_sync::lock_ordering;
use starnix_uapi::errno;
use std::future::Future;
use std::pin::Pin;
use std::sync::Barrier;
use std::sync::atomic::{AtomicUsize, Ordering};
#[::fuchsia::test]
fn test_remove_from_queue() {
let mut inner = RwQueueInner::default();
let event1 = InterruptibleEvent::new();
let event2 = InterruptibleEvent::new();
let event3 = InterruptibleEvent::new();
inner.waiters.push_back(Waiter::Writer(event1.clone()));
inner.waiters.push_back(Waiter::Writer(event2.clone()));
inner.waiters.push_back(Waiter::Writer(event3.clone()));
inner.remove_waiter(&event2);
let waiter = inner.waiters.pop_front().expect("should have a waiter");
let Waiter::Writer(event) = waiter else {
unreachable!();
};
assert!(Arc::ptr_eq(&event1, &event));
let waiter = inner.waiters.pop_front().expect("should have a waiter");
let Waiter::Writer(event) = waiter else {
unreachable!();
};
assert!(Arc::ptr_eq(&event3, &event));
assert!(inner.waiters.is_empty());
}
#[::fuchsia::test]
async fn test_write_and_read() {
lock_ordering! {
Unlocked => TestLevel
}
spawn_kernel_and_run(async |current_task| {
let queue = RwQueue::new::<TestLevel>();
let read_guard1 = queue.read(current_task).expect("shouldn't be interrupted");
std::mem::drop(read_guard1);
let write_guard = queue.write(current_task).expect("shouldn't be interrupted");
std::mem::drop(write_guard);
let read_guard2 = queue.read(current_task).expect("shouldn't be interrupted");
std::mem::drop(read_guard2);
})
.await;
}
#[::fuchsia::test]
async fn test_read_in_parallel() {
spawn_kernel_and_run(async |current_task| {
let kernel = current_task.kernel();
lock_ordering! {
Unlocked => TestLevel
}
struct Info {
barrier: Barrier,
queue: RwQueue,
}
let info =
Arc::new(Info { barrier: Barrier::new(2), queue: RwQueue::new::<TestLevel>() });
let info1 = Arc::clone(&info);
let closure1 = move |current_task: &CurrentTask| {
let guard = info1.queue.read(current_task).expect("shouldn't be interrupted");
info1.barrier.wait();
std::mem::drop(guard);
};
let (thread1, req) =
SpawnRequestBuilder::new().with_sync_closure(closure1).build_with_async_result();
kernel.kthreads.spawner().spawn_from_request(req);
let info2 = Arc::clone(&info);
let closure2 = move |current_task: &CurrentTask| {
let guard = info2.queue.read(current_task).expect("shouldn't be interrupted");
info2.barrier.wait();
std::mem::drop(guard);
};
let (thread2, req) =
SpawnRequestBuilder::new().with_sync_closure(closure2).build_with_async_result();
kernel.kthreads.spawner().spawn_from_request(req);
block_on(async {
thread1.await.expect("failed to join thread");
thread2.await.expect("failed to join thread");
});
})
.await;
}
lock_ordering! {
Unlocked => A
}
struct State {
queue: RwQueue,
gate: Barrier,
writer_count: AtomicUsize,
reader_count: AtomicUsize,
}
impl State {
fn new(n: usize) -> State {
State {
queue: RwQueue::new::<A>(),
gate: Barrier::new(n),
writer_count: Default::default(),
reader_count: Default::default(),
}
}
fn spawn_writer(
state: Arc<Self>,
kernel: Arc<Kernel>,
count: usize,
) -> Pin<Box<dyn Future<Output = Result<(), Errno>> + Send>> {
let closure = move |current_task: &CurrentTask| {
state.gate.wait();
for _ in 0..count {
let guard = state.queue.write(current_task).expect("shouldn't be interrupted");
let writer_count = state.writer_count.fetch_add(1, Ordering::Acquire) + 1;
let reader_count = state.reader_count.load(Ordering::Acquire);
state.writer_count.fetch_sub(1, Ordering::Release);
std::mem::drop(guard);
assert_eq!(writer_count, 1, "More than one writer held the lock at once.");
assert_eq!(
reader_count, 0,
"A reader and writer held the lock at the same time."
);
}
};
let (result, req) =
SpawnRequestBuilder::new().with_sync_closure(closure).build_with_async_result();
kernel.kthreads.spawner().spawn_from_request(req);
Box::pin(result)
}
fn spawn_reader(
state: Arc<Self>,
kernel: Arc<Kernel>,
count: usize,
) -> Pin<Box<dyn Future<Output = Result<(), Errno>> + Send>> {
let closure = move |current_task: &CurrentTask| {
state.gate.wait();
for _ in 0..count {
let guard = state.queue.read(current_task).expect("shouldn't be interrupted");
let reader_count = state.reader_count.fetch_add(1, Ordering::Acquire) + 1;
let writer_count = state.writer_count.load(Ordering::Acquire);
state.reader_count.fetch_sub(1, Ordering::Release);
std::mem::drop(guard);
assert_eq!(
writer_count, 0,
"A reader and writer held the lock at the same time."
);
assert!(reader_count > 0, "A reader held the lock without being counted.");
}
};
let (result, req) =
SpawnRequestBuilder::new().with_sync_closure(closure).build_with_async_result();
kernel.kthreads.spawner().spawn_from_request(req);
Box::pin(result)
}
}
#[::fuchsia::test]
async fn test_thundering_reads_and_writes() {
spawn_kernel_and_run(async |current_task| {
let kernel = current_task.kernel();
const THREAD_PAIRS: usize = 10;
let state = Arc::new(State::new(THREAD_PAIRS * 2));
let mut threads = vec![];
for _ in 0..THREAD_PAIRS {
threads.push(State::spawn_writer(Arc::clone(&state), kernel.clone(), 100));
threads.push(State::spawn_reader(Arc::clone(&state), kernel.clone(), 100));
}
block_on(join_all(threads)).into_iter().for_each(|r| r.expect("failed to join thread"));
})
.await;
}
#[::fuchsia::test]
fn test_cancel_read() {
let mut inner = RwQueueInner::default();
assert!(inner.try_write());
let reader1 = InterruptibleEvent::new();
let reader2 = InterruptibleEvent::new();
let writer2 = InterruptibleEvent::new();
inner.waiters.push_back(Waiter::Reader(reader1.clone()));
inner.waiters.push_back(Waiter::Reader(reader2.clone()));
inner.waiters.push_back(Waiter::Writer(writer2));
// Cancelling a reader while still in the queue simply removes it.
inner.cancel_read(&reader1);
assert_eq!(inner.state, WRITER);
assert_eq!(inner.waiters.len(), 2);
// Unlocking pops `reader2` and transfers a read lock to it.
inner.unlock_write();
assert_eq!(inner.state, READER);
assert_eq!(inner.waiters.len(), 1);
// Cancelling `reader2` after `notify_next()` must release its read lock and wake
// `writer2`.
inner.cancel_read(&reader2);
assert_eq!(inner.state, WRITER);
assert!(inner.waiters.is_empty());
}
#[::fuchsia::test]
fn test_cancel_write() {
let mut inner = RwQueueInner::default();
assert!(inner.try_read());
let writer1 = InterruptibleEvent::new();
let reader2 = InterruptibleEvent::new();
inner.waiters.push_back(Waiter::Writer(writer1.clone()));
inner.waiters.push_back(Waiter::Reader(reader2));
// Cancelling a queued writer while a reader is active wakes readers queued behind it.
inner.cancel_write(&writer1);
assert_eq!(inner.state, 2 * READER);
assert!(inner.waiters.is_empty());
inner.unlock_read();
inner.unlock_read();
assert_eq!(inner.state, READY);
// While a writer holds the lock, cancelling a second queued writer must not wake a reader
// queued behind it until the active writer unlocks.
assert!(inner.try_write());
let writer2 = InterruptibleEvent::new();
let reader3 = InterruptibleEvent::new();
inner.waiters.push_back(Waiter::Writer(writer2.clone()));
inner.waiters.push_back(Waiter::Reader(reader3));
inner.cancel_write(&writer2);
assert_eq!(inner.state, WRITER);
assert_eq!(inner.waiters.len(), 1);
inner.unlock_write();
assert_eq!(inner.state, READER);
assert!(inner.waiters.is_empty());
// Cancelling a writer after `notify_next()` popped it must release its write lock and
// wake the next waiter.
let writer3 = InterruptibleEvent::new();
let reader4 = InterruptibleEvent::new();
inner.waiters.push_back(Waiter::Writer(writer3.clone()));
inner.waiters.push_back(Waiter::Reader(reader4));
inner.unlock_read();
assert_eq!(inner.state, WRITER);
assert_eq!(inner.waiters.len(), 1);
inner.cancel_write(&writer3);
assert_eq!(inner.state, READER);
assert!(inner.waiters.is_empty());
}
#[::fuchsia::test]
async fn test_interrupted_read_and_write() {
lock_ordering! {
Unlocked => TestLevel
}
spawn_kernel_and_run(async |current_task| {
let kernel = current_task.kernel();
let queue = Arc::new(RwQueue::new::<TestLevel>());
let barrier = Arc::new(Barrier::new(2));
let write_guard = queue.write(current_task).expect("shouldn't be interrupted");
let queue_clone = Arc::clone(&queue);
let barrier_clone = Arc::clone(&barrier);
let (thread, req) = SpawnRequestBuilder::new()
.with_sync_closure(move |task: &CurrentTask| {
task.write().set_flags(TaskFlags::WORK_CANCELLED, true);
assert_eq!(queue_clone.read(task).err(), Some(errno!(EINTR)));
assert_eq!(queue_clone.write(task).err(), Some(errno!(EINTR)));
task.write().set_flags(TaskFlags::WORK_CANCELLED, false);
barrier_clone.wait();
barrier_clone.wait();
// Re-acquiring on the same thread verifies `tracer` was unlocked on `EINTR`.
let read_guard = queue_clone.read(task).expect("should acquire read");
std::mem::drop(read_guard);
let write_guard = queue_clone.write(task).expect("should acquire write");
std::mem::drop(write_guard);
})
.build_with_async_result();
kernel.kthreads.spawner().spawn_from_request(req);
barrier.wait();
std::mem::drop(write_guard);
barrier.wait();
block_on(thread).expect("failed to join thread");
})
.await;
}
}