use std::collections::HashMap;
use std::sync::RwLock;
use crossbeam_skiplist::SkipMap;
use super::descriptor::{TransferDescriptor, WeakTransferDescriptor};
use crate::runtime::sync::sync::atomic::{AtomicBool, AtomicU64, AtomicUsize, Ordering};
use crate::runtime::sync::sync::Arc;
use crate::transfer::TransferId;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct ReadyKey {
vruntime: u64,
id: u64,
}
impl ReadyKey {
fn new(vruntime: u64, id: TransferId) -> Self {
Self {
vruntime,
id: id.id,
}
}
}
impl Ord for ReadyKey {
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
self.vruntime
.cmp(&other.vruntime)
.then_with(|| self.id.cmp(&other.id))
}
}
impl PartialOrd for ReadyKey {
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
Some(self.cmp(other))
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct GroupKey {
group_vruntime: u64,
group_id: u64,
}
impl Ord for GroupKey {
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
self.group_vruntime
.cmp(&other.group_vruntime)
.then_with(|| self.group_id.cmp(&other.group_id))
}
}
impl PartialOrd for GroupKey {
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
Some(self.cmp(other))
}
}
pub(super) struct GroupState {
min_vruntime: AtomicU64,
group_vruntime: Arc<AtomicU64>,
nr_queued: AtomicUsize,
in_root: AtomicBool,
}
impl GroupState {
pub(super) fn new(group_vruntime: Arc<AtomicU64>) -> Self {
Self {
min_vruntime: AtomicU64::new(0),
group_vruntime,
nr_queued: AtomicUsize::new(0),
in_root: AtomicBool::new(false),
}
}
pub(super) fn enqueue(&self) -> usize {
self.nr_queued.fetch_add(1, Ordering::SeqCst)
}
pub(super) fn dequeue(&self) -> usize {
self.nr_queued.fetch_sub(1, Ordering::SeqCst)
}
pub(super) fn try_enter_root(&self) -> bool {
self.in_root
.compare_exchange(false, true, Ordering::SeqCst, Ordering::SeqCst)
.is_ok()
}
pub(super) fn exit_root(&self) {
self.in_root.store(false, Ordering::SeqCst);
}
pub(super) fn nr_queued(&self) -> usize {
self.nr_queued.load(Ordering::SeqCst)
}
#[cfg(test)]
pub(super) fn min_vruntime(&self) -> u64 {
self.min_vruntime.load(Ordering::Acquire)
}
pub(super) fn advance_min_vruntime(&self, vruntime: u64) {
self.min_vruntime.fetch_max(vruntime, Ordering::AcqRel);
}
pub(super) fn group_vruntime(&self) -> u64 {
self.group_vruntime.load(Ordering::SeqCst)
}
pub(super) fn set_group_vruntime(&self, val: u64) {
self.group_vruntime.store(val, Ordering::SeqCst);
}
pub(super) fn group_vruntime_arc(&self) -> Arc<AtomicU64> {
Arc::clone(&self.group_vruntime)
}
}
struct GroupQueue {
state: GroupState,
inner: SkipMap<ReadyKey, WeakTransferDescriptor>,
}
impl GroupQueue {
fn new(group_vruntime: Arc<AtomicU64>) -> Self {
Self {
state: GroupState::new(group_vruntime),
inner: SkipMap::new(),
}
}
#[cfg(test)]
fn new_with_initial_vruntime(initial: u64) -> Self {
Self::new(Arc::new(AtomicU64::new(initial)))
}
fn insert(&self, descriptor: &TransferDescriptor) -> usize {
let vruntime = descriptor.vruntime();
let key = ReadyKey::new(vruntime, descriptor.id());
self.inner.insert(key, descriptor.downgrade());
self.state.enqueue()
}
fn pop(&self) -> Option<TransferDescriptor> {
let entry = self.inner.pop_front()?;
self.state.dequeue();
self.state.advance_min_vruntime(entry.key().vruntime);
entry.value().upgrade()
}
fn count(&self) -> usize {
self.state.nr_queued()
}
#[cfg(test)]
fn min_vruntime(&self) -> u64 {
self.state.min_vruntime()
}
fn group_vruntime(&self) -> u64 {
self.state.group_vruntime()
}
fn group_vruntime_arc(&self) -> Arc<AtomicU64> {
self.state.group_vruntime_arc()
}
}
pub(super) struct ReadySet {
groups: SkipMap<GroupKey, Arc<GroupQueue>>,
by_group: RwLock<HashMap<u64, Arc<GroupQueue>>>,
min_vruntime: AtomicU64,
}
impl Default for ReadySet {
fn default() -> Self {
Self::new()
}
}
impl ReadySet {
pub(super) fn new() -> Self {
Self {
groups: SkipMap::new(),
by_group: RwLock::new(HashMap::new()),
min_vruntime: AtomicU64::new(0),
}
}
pub(super) fn min_vruntime(&self) -> u64 {
self.min_vruntime.load(Ordering::Acquire)
}
pub(super) fn resolve_group_vruntime(&self, id: &TransferId) -> Option<Arc<AtomicU64>> {
match id.parent {
Some(parent_id) => {
let by_group = self.by_group.read().unwrap();
by_group.get(&parent_id).map(|g| g.group_vruntime_arc())
}
None => {
let by_group = self.by_group.read().unwrap();
if let Some(group) = by_group.get(&id.id) {
return Some(group.group_vruntime_arc());
}
drop(by_group);
Some(Arc::new(AtomicU64::new(self.min_vruntime())))
}
}
}
pub(super) fn insert(&self, descriptor: TransferDescriptor) -> Result<(), OrphanedChild> {
if !descriptor.try_claim() {
return Ok(());
}
let tid = descriptor.id();
match tid.parent {
None => {
self.insert_top_level(tid.id, descriptor);
Ok(())
}
Some(parent_id) => self.insert_child(parent_id, descriptor),
}
}
pub(super) fn reinsert_under_claim(&self, descriptor: TransferDescriptor) {
let tid = descriptor.id();
let group_id = tid.parent.unwrap_or(tid.id);
if self
.try_insert_into_existing_group(group_id, descriptor, false)
.is_err()
{
tracing::trace!(
target: crate::telemetry::TARGET_SCHEDULING,
tid = %tid,
"reinsert_under_claim: parent group gone (cancel during Ready); descriptor already terminal"
);
}
}
fn try_insert_into_existing_group(
&self,
group_id: u64,
descriptor: TransferDescriptor,
reset_group_vruntime: bool,
) -> Result<(), TransferDescriptor> {
let by_group = self.by_group.read().unwrap();
let group = match by_group.get(&group_id) {
Some(g) => Arc::clone(g),
None => return Err(descriptor),
};
let prev_count = group.insert(&descriptor);
if prev_count == 0 && group.state.try_enter_root() {
let gv = if reset_group_vruntime {
let root_min = self.min_vruntime();
group.state.set_group_vruntime(root_min);
root_min
} else {
group.group_vruntime()
};
let key = GroupKey {
group_vruntime: gv,
group_id,
};
self.groups.insert(key, group);
}
drop(by_group);
drop(descriptor);
Ok(())
}
pub(super) fn pop(&self) -> Option<TransferDescriptor> {
loop {
let entry = self.groups.pop_front()?;
let group_key = *entry.key();
let group = entry.value().clone();
let descriptor = group.pop();
group.state.exit_root();
self.min_vruntime
.fetch_max(group_key.group_vruntime, Ordering::AcqRel);
if group.count() > 0 && group.state.try_enter_root() {
let new_key = GroupKey {
group_vruntime: group.group_vruntime(),
group_id: group_key.group_id,
};
self.groups.insert(new_key, group);
}
if let Some(descriptor) = descriptor {
return Some(descriptor);
}
}
}
#[cfg(test)]
pub(super) fn advance_group_vruntime(&self, group_id: u64, units: u64) {
let by_group = self.by_group.read().unwrap();
if let Some(group) = by_group.get(&group_id) {
group
.state
.group_vruntime
.fetch_add(units, Ordering::SeqCst);
}
}
pub(super) fn remove_group(&self, group_id: u64) {
let removed = self.by_group.write().unwrap().remove(&group_id);
if removed.is_some() {
let key = self
.groups
.iter()
.find(|entry| entry.key().group_id == group_id)
.map(|entry| *entry.key());
if let Some(k) = key {
self.groups.remove(&k);
}
}
}
#[cfg(test)]
pub(crate) fn register_empty_group_for_test(&self, group_id: u64) {
let root_min = self.min_vruntime();
let group = Arc::new(GroupQueue::new_with_initial_vruntime(root_min));
self.by_group.write().unwrap().insert(group_id, group);
}
#[cfg(test)]
pub(super) fn is_empty(&self) -> bool {
self.groups.is_empty()
}
#[cfg(test)]
pub(super) fn group_count(&self) -> usize {
self.by_group.read().unwrap().len()
}
#[cfg(test)]
pub(super) fn member_count(&self, group_id: u64) -> Option<usize> {
let by_group = self.by_group.read().unwrap();
by_group.get(&group_id).map(|g| g.count())
}
#[cfg(test)]
pub(super) fn group_vruntime(&self, group_id: u64) -> Option<u64> {
let by_group = self.by_group.read().unwrap();
by_group.get(&group_id).map(|g| g.group_vruntime())
}
#[cfg(test)]
pub(super) fn group_min_vruntime(&self, group_id: u64) -> Option<u64> {
let by_group = self.by_group.read().unwrap();
by_group.get(&group_id).map(|g| g.min_vruntime())
}
#[cfg(test)]
pub(super) fn root_contains_group(&self, group_id: u64) -> bool {
self.groups
.iter()
.any(|entry| entry.key().group_id == group_id)
}
fn insert_top_level(&self, group_id: u64, descriptor: TransferDescriptor) {
let descriptor = match self.try_insert_into_existing_group(group_id, descriptor, true) {
Ok(()) => return,
Err(d) => d,
};
let root_min = self.min_vruntime();
let gv_arc = descriptor.group_vruntime_arc();
let group = Arc::new(GroupQueue::new(gv_arc));
group.insert(&descriptor);
group.state.in_root.store(true, Ordering::SeqCst);
let key = GroupKey {
group_vruntime: root_min,
group_id,
};
self.by_group
.write()
.unwrap()
.insert(group_id, Arc::clone(&group));
self.groups.insert(key, group);
}
fn insert_child(
&self,
parent_id: u64,
descriptor: TransferDescriptor,
) -> Result<(), OrphanedChild> {
match self.try_insert_into_existing_group(parent_id, descriptor, true) {
Ok(()) => Ok(()),
Err(descriptor) => {
descriptor.release_claim();
Err(OrphanedChild)
}
}
}
}
#[derive(Debug)]
pub(super) struct OrphanedChild;
#[cfg(test)]
mod tests {
use super::*;
use crate::scheduler::transfer::mock::FixedWorkCount;
use crate::scheduler::MockTransfer;
use std::sync::Arc as StdArc;
fn make_unheld_descriptor(
id: u64,
parent: Option<u64>,
priority: u8,
vruntime: u64,
) -> TransferDescriptor {
let tid = TransferId { id, parent };
let sm = StdArc::new(FixedWorkCount::new(1));
let transfer = Box::new(MockTransfer::new(tid, sm));
let desc = TransferDescriptor::new(transfer);
desc.set_priority(priority);
desc.set_vruntime(vruntime);
desc
}
fn make_descriptor(
id: u64,
parent: Option<u64>,
priority: u8,
vruntime: u64,
) -> TransferDescriptor {
let desc = make_unheld_descriptor(id, parent, priority, vruntime);
REGISTRY.with(|registry| registry.borrow_mut().push(desc.clone()));
desc
}
thread_local! {
static REGISTRY: std::cell::RefCell<Vec<TransferDescriptor>> =
const { std::cell::RefCell::new(Vec::new()) };
}
#[cfg_attr(miri, ignore)]
#[test]
fn group_queue_insert_pop_single() {
let gq = GroupQueue::new_with_initial_vruntime(0);
let desc = make_descriptor(1, None, 128, 0);
gq.insert(&desc);
assert_eq!(gq.count(), 1);
let popped = gq.pop().unwrap();
assert_eq!(popped.id().id, 1);
assert_eq!(gq.count(), 0);
assert!(gq.pop().is_none());
}
#[cfg_attr(miri, ignore)]
#[test]
fn group_queue_pop_lowest_vruntime() {
let gq = GroupQueue::new_with_initial_vruntime(0);
gq.insert(&make_descriptor(10, None, 128, 5));
gq.insert(&make_descriptor(11, None, 128, 1));
gq.insert(&make_descriptor(12, None, 128, 3));
assert_eq!(gq.pop().unwrap().id().id, 11); assert_eq!(gq.pop().unwrap().id().id, 12); assert_eq!(gq.pop().unwrap().id().id, 10); }
#[cfg_attr(miri, ignore)]
#[test]
fn ready_set_insert_no_parent_creates_group() {
let set = ReadySet::new();
let desc = make_descriptor(42, None, 128, 0);
set.insert(desc).unwrap();
assert_eq!(set.group_count(), 1);
assert_eq!(set.member_count(42), Some(1));
assert!(set.root_contains_group(42));
}
#[cfg_attr(miri, ignore)]
#[test]
fn ready_set_insert_with_parent_finds_existing_group() {
let set = ReadySet::new();
set.insert(make_descriptor(10, None, 128, 0)).unwrap();
set.insert(make_descriptor(20, Some(10), 128, 0)).unwrap();
assert_eq!(set.group_count(), 1);
assert_eq!(set.member_count(10), Some(2));
assert!(set.root_contains_group(10));
}
#[cfg_attr(miri, ignore)]
#[test]
fn ready_set_insert_child_with_unknown_parent() {
let set = ReadySet::new();
let desc = make_descriptor(20, Some(99), 128, 0);
let result = set.insert(desc);
assert!(result.is_err());
assert_eq!(set.group_count(), 0);
assert!(!set.root_contains_group(99));
}
#[cfg_attr(miri, ignore)]
#[test]
fn ready_set_pop_returns_lowest_group_lowest_member() {
let set = ReadySet::new();
set.insert(make_descriptor(1, None, 128, 0)).unwrap();
set.insert(make_descriptor(11, Some(1), 128, 5)).unwrap();
set.advance_group_vruntime(1, 100);
let first = set.pop().unwrap();
assert_eq!(first.id().id, 1);
set.insert(make_descriptor(2, None, 128, 0)).unwrap();
set.insert(make_descriptor(22, Some(2), 128, 3)).unwrap();
let popped = set.pop().unwrap();
assert_eq!(popped.id().id, 2);
}
#[cfg_attr(miri, ignore)]
#[test]
fn ready_set_does_not_keep_descriptors_alive() {
let set = ReadySet::new();
let desc = make_unheld_descriptor(1, None, 128, 0);
let weak = desc.downgrade();
set.insert(desc).unwrap();
assert!(
weak.upgrade().is_none(),
"the queued entry owns its descriptor"
);
assert!(set.pop().is_none(), "popped a dropped descriptor");
assert!(set.is_empty());
}
#[cfg_attr(miri, ignore)]
#[test]
fn pop_skips_dropped_descriptors_to_the_next_live_one() {
let set = ReadySet::new();
set.insert(make_unheld_descriptor(1, None, 128, 0)).unwrap();
set.insert(make_unheld_descriptor(11, Some(1), 128, 0))
.unwrap();
set.insert(make_descriptor(2, None, 128, 0)).unwrap();
assert_eq!(set.pop().map(|d| d.id().id), Some(2));
assert!(!set.root_contains_group(1));
assert_eq!(set.member_count(1), Some(0));
assert!(set.pop().is_none());
}
struct RemovesGroupOnDrop {
set: StdArc<ReadySet>,
group_id: u64,
}
impl std::fmt::Debug for RemovesGroupOnDrop {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.debug_struct("RemovesGroupOnDrop")
.field("group_id", &self.group_id)
.finish_non_exhaustive()
}
}
impl crate::scheduler::transfer::mock::MockStateMachine for RemovesGroupOnDrop {
fn poll_work(&self, _id: TransferId) -> crate::transfer::PollWork {
crate::transfer::PollWork::Done
}
fn execute<'a>(
&'a self,
_work: &'a mut crate::transfer::IoRequest,
) -> std::pin::Pin<
Box<dyn std::future::Future<Output = crate::transfer::WorkOutcome> + Send + 'a>,
> {
Box::pin(async { crate::transfer::WorkOutcome::Success { data: None } })
}
}
impl Drop for RemovesGroupOnDrop {
fn drop(&mut self) {
self.set.remove_group(self.group_id);
}
}
#[cfg_attr(miri, ignore)]
#[test]
fn insert_drops_an_unheld_descriptor_outside_the_ready_set_locks() {
let set = StdArc::new(ReadySet::new());
set.insert(make_descriptor(1, None, 128, 0)).unwrap();
let child = TransferDescriptor::new(Box::new(MockTransfer::new(
TransferId {
id: 11,
parent: Some(1),
},
StdArc::new(RemovesGroupOnDrop {
set: StdArc::clone(&set),
group_id: 2,
}),
)));
let (done_tx, done_rx) = std::sync::mpsc::channel();
let inserter = StdArc::clone(&set);
std::thread::spawn(move || {
inserter.insert(child).unwrap();
done_tx.send(()).unwrap();
});
done_rx
.recv_timeout(std::time::Duration::from_secs(5))
.expect("the insert deadlocked or panicked dropping its descriptor");
}
#[cfg_attr(miri, ignore)]
#[test]
fn pop_competes_composite_with_its_children() {
let set = ReadySet::new();
set.insert(make_descriptor(1, None, 128, 0)).unwrap(); set.insert(make_descriptor(11, Some(1), 128, 5)).unwrap(); set.insert(make_descriptor(12, Some(1), 128, 10)).unwrap();
let popped = set.pop().unwrap();
assert_eq!(popped.id().id, 1); }
#[cfg_attr(miri, ignore)]
#[test]
fn group_leaves_root_when_empty() {
let set = ReadySet::new();
assert!(set.is_empty());
set.insert(make_descriptor(1, None, 128, 0)).unwrap();
set.insert(make_descriptor(2, Some(1), 128, 0)).unwrap();
set.pop().unwrap();
assert!(set.root_contains_group(1));
assert_eq!(set.member_count(1), Some(1));
set.pop().unwrap();
assert!(!set.root_contains_group(1));
assert_eq!(set.member_count(1), Some(0));
assert_eq!(set.group_count(), 1);
}
#[cfg_attr(miri, ignore)]
#[test]
fn group_rejoins_root_on_next_insert() {
let set = ReadySet::new();
set.insert(make_descriptor(1, None, 128, 0)).unwrap();
set.pop().unwrap();
assert!(!set.root_contains_group(1));
set.insert(make_descriptor(2, None, 128, 0)).unwrap();
set.insert(make_descriptor(22, Some(2), 128, 0)).unwrap();
set.advance_group_vruntime(2, 50);
set.pop().unwrap();
set.pop().unwrap();
let floor = set.min_vruntime();
assert!(floor > 0, "root floor should have advanced past 0");
set.insert(make_descriptor(11, Some(1), 128, 0)).unwrap();
assert!(set.root_contains_group(1));
assert_eq!(set.group_vruntime(1), Some(floor));
}
#[cfg_attr(miri, ignore)]
#[test]
fn enqueue_no_parent_does_not_advance_anyone() {
let set = ReadySet::new();
set.insert(make_descriptor(1, None, 128, 0)).unwrap();
set.insert(make_descriptor(2, None, 128, 0)).unwrap();
assert_eq!(set.group_vruntime(1), Some(0));
assert_eq!(set.group_vruntime(2), Some(0));
}
#[cfg_attr(miri, ignore)]
#[test]
fn child_initial_vruntime_uses_group_min() {
let set = ReadySet::new();
set.insert(make_descriptor(1, None, 128, 100)).unwrap();
let popped = set.pop().unwrap();
assert_eq!(set.group_min_vruntime(1), Some(100));
set.reinsert_under_claim(popped);
let floor = set.group_min_vruntime(1).unwrap();
let child = make_descriptor(11, Some(1), 128, floor);
set.insert(child.clone()).unwrap();
assert_eq!(child.vruntime(), 100);
}
#[cfg_attr(miri, ignore)]
#[test]
fn reinsert_under_claim_in_group_bypasses_cas() {
let set = ReadySet::new();
set.insert(make_descriptor(1, None, 128, 0)).unwrap();
set.insert(make_descriptor(11, Some(1), 128, 0)).unwrap();
let popped = set.pop().unwrap();
popped.work_generated();
let new_vrt = popped.vruntime();
assert!(new_vrt > 0);
set.reinsert_under_claim(popped);
assert!(set.root_contains_group(1));
assert_eq!(set.member_count(1), Some(2));
}
#[cfg_attr(miri, ignore)]
#[test]
fn child_terminating_keeps_group_alive_until_last_child() {
let set = ReadySet::new();
set.insert(make_descriptor(1, None, 128, 0)).unwrap();
set.insert(make_descriptor(11, Some(1), 128, 0)).unwrap();
set.insert(make_descriptor(12, Some(1), 128, 0)).unwrap();
set.pop().unwrap();
assert!(set.root_contains_group(1));
assert_eq!(set.member_count(1), Some(2));
set.pop().unwrap();
assert!(set.root_contains_group(1));
assert_eq!(set.member_count(1), Some(1));
set.pop().unwrap();
assert!(!set.root_contains_group(1));
assert_eq!(set.member_count(1), Some(0));
}
#[cfg_attr(miri, ignore)]
#[test]
fn priority_change_on_top_level_reweights_group() {
let set = ReadySet::new();
let t1 = make_descriptor(1, None, 128, 0);
let t2 = make_descriptor(2, None, 128, 0);
set.insert(t1.clone()).unwrap();
set.insert(t2.clone()).unwrap();
t1.work_generated();
t2.work_generated();
t1.set_priority(255);
let p1 = set.pop().unwrap();
let p2 = set.pop().unwrap();
set.reinsert_under_claim(p1.clone());
set.reinsert_under_claim(p2.clone());
p1.work_generated();
p2.work_generated();
assert!(
p1.vruntime() < p2.vruntime(),
"higher priority should accumulate less vruntime: t1={}, t2={}",
p1.vruntime(),
p2.vruntime()
);
}
#[cfg_attr(miri, ignore)]
#[test]
fn remove_group_orphans_children_and_allows_recreation() {
let set = ReadySet::new();
set.insert(make_descriptor(1, None, 128, 0)).unwrap();
set.insert(make_descriptor(11, Some(1), 128, 0)).unwrap();
set.remove_group(1);
assert!(!set.root_contains_group(1));
assert_eq!(set.group_count(), 0);
let result = set.insert(make_descriptor(12, Some(1), 128, 0));
assert!(result.is_err());
set.insert(make_descriptor(1, None, 128, 0)).unwrap();
assert!(set.root_contains_group(1));
assert_eq!(set.group_count(), 1);
assert_eq!(set.member_count(1), Some(1));
}
}
#[cfg(all(test, s3_tm_loom))]
mod loom_tests {
use loom::sync::atomic::{AtomicUsize, Ordering};
use loom::sync::Arc;
use loom::thread;
struct LoomGroup {
state: super::GroupState,
root_entries: AtomicUsize,
}
impl LoomGroup {
fn new(initial_count: usize) -> Self {
let state = super::GroupState::new(Arc::new(
crate::runtime::sync::sync::atomic::AtomicU64::new(0),
));
for _ in 0..initial_count {
state.enqueue();
}
if initial_count > 0 {
state.in_root.store(true, Ordering::SeqCst);
}
Self {
state,
root_entries: AtomicUsize::new(if initial_count > 0 { 1 } else { 0 }),
}
}
fn insert(&self) {
let prev = self.state.enqueue();
if prev == 0 && self.state.try_enter_root() {
self.state.set_group_vruntime(0);
self.root_entries.fetch_add(1, Ordering::SeqCst);
}
}
fn pop(&self) {
self.root_entries.fetch_sub(1, Ordering::SeqCst);
self.state.exit_root();
self.state.dequeue();
if self.state.nr_queued() > 0 && self.state.try_enter_root() {
self.root_entries.fetch_add(1, Ordering::SeqCst);
}
}
fn is_in_root(&self) -> bool {
self.root_entries.load(Ordering::SeqCst) > 0
}
fn root_entries_valid(&self) -> bool {
self.root_entries.load(Ordering::SeqCst) <= 1
}
fn count(&self) -> usize {
self.state.nr_queued()
}
}
#[test]
fn concurrent_child_enqueue_under_same_parent() {
loom::model(|| {
let group = Arc::new(LoomGroup::new(1));
let g2 = Arc::clone(&group);
let a = thread::spawn(move || {
g2.insert(); });
let g3 = Arc::clone(&group);
let b = thread::spawn(move || {
g3.insert(); });
a.join().unwrap();
b.join().unwrap();
assert_eq!(group.count(), 3); assert!(group.is_in_root());
});
}
struct LoomMemberGroup {
group: LoomGroup,
members: loom::sync::Mutex<std::collections::VecDeque<usize>>,
}
impl LoomMemberGroup {
fn insert(&self, member: usize) {
self.members.lock().unwrap().push_front(member);
let prev = self.group.state.enqueue();
if prev == 0 && self.group.state.try_enter_root() {
self.group.state.set_group_vruntime(0);
self.group.root_entries.fetch_add(1, Ordering::SeqCst);
}
}
fn pop(&self) -> Option<usize> {
self.group.root_entries.fetch_sub(1, Ordering::SeqCst);
let member = self.members.lock().unwrap().pop_front();
if member.is_some() {
assert!(self.group.state.dequeue() > 0, "nr_queued underflow");
}
self.group.state.exit_root();
if self.group.state.nr_queued() > 0 && self.group.state.try_enter_root() {
self.group.root_entries.fetch_add(1, Ordering::SeqCst);
}
member
}
}
#[test]
fn pop_concurrent_with_member_publication_preserves_group_membership() {
loom::model(|| {
const FIRST: usize = 1;
const SECOND: usize = 2;
let group = Arc::new(LoomMemberGroup {
group: LoomGroup::new(1),
members: loom::sync::Mutex::new([FIRST].into_iter().collect()),
});
let g = Arc::clone(&group);
let insert = thread::spawn(move || g.insert(SECOND));
let popped = group.pop().expect("the initial member is available");
let remaining = match popped {
FIRST => SECOND,
SECOND => FIRST,
member => panic!("unexpected member {member}"),
};
insert.join().unwrap();
assert_eq!(
*group.members.lock().unwrap(),
[remaining],
"one root pop removes exactly one entry"
);
assert_eq!(group.group.count(), 1, "nr_queued drifted");
assert!(group.group.is_in_root(), "remaining member is unreachable");
assert!(group.group.root_entries_valid(), "duplicate root entry");
assert_eq!(group.pop(), Some(remaining));
assert!(group.members.lock().unwrap().is_empty());
assert_eq!(group.group.count(), 0);
assert!(!group.group.is_in_root());
assert!(group.group.root_entries_valid(), "duplicate root entry");
});
}
#[test]
fn pop_last_member_concurrent_with_insert() {
loom::model(|| {
let group = Arc::new(LoomGroup::new(1));
let g2 = Arc::clone(&group);
let a = thread::spawn(move || {
g2.pop();
});
let g3 = Arc::clone(&group);
let b = thread::spawn(move || {
g3.insert();
});
a.join().unwrap();
b.join().unwrap();
assert_eq!(group.count(), 1);
assert!(group.is_in_root());
assert!(
group.root_entries_valid(),
"duplicate root-tree entry detected"
);
});
}
#[test]
fn concurrent_pop_from_different_groups() {
loom::model(|| {
let g1 = Arc::new(LoomGroup::new(1));
let g2 = Arc::new(LoomGroup::new(1));
let g1c = Arc::clone(&g1);
let a = thread::spawn(move || {
g1c.pop();
});
let g2c = Arc::clone(&g2);
let b = thread::spawn(move || {
g2c.pop();
});
a.join().unwrap();
b.join().unwrap();
assert_eq!(g1.count(), 0);
assert_eq!(g2.count(), 0);
});
}
#[test]
fn enqueue_concurrent_with_pop_same_group() {
loom::model(|| {
let group = Arc::new(LoomGroup::new(2));
let g2 = Arc::clone(&group);
let a = thread::spawn(move || {
g2.pop();
});
let g3 = Arc::clone(&group);
let b = thread::spawn(move || {
g3.insert();
});
a.join().unwrap();
b.join().unwrap();
assert_eq!(group.count(), 2);
assert!(group.is_in_root());
assert!(
group.root_entries_valid(),
"duplicate root-tree entry detected"
);
});
}
#[test]
fn group_vruntime_advance_concurrent_with_pop() {
loom::model(|| {
let group = Arc::new(LoomGroup::new(2));
let g2 = Arc::clone(&group);
let a = thread::spawn(move || {
g2.state.group_vruntime.fetch_add(100, Ordering::SeqCst);
});
let g3 = Arc::clone(&group);
let b = thread::spawn(move || {
g3.pop();
});
a.join().unwrap();
b.join().unwrap();
let gv = group.state.group_vruntime();
assert_eq!(gv, 100);
assert_eq!(group.count(), 1);
assert!(group.is_in_root());
});
}
#[test]
fn concurrent_top_level_enqueue_creates_one_group() {
loom::model(|| {
let claim = Arc::new(super::super::descriptor::claim::ClaimState::new());
let insert_count = Arc::new(AtomicUsize::new(0));
let c2 = Arc::clone(&claim);
let ic2 = Arc::clone(&insert_count);
let a = thread::spawn(move || {
if c2.try_claim() {
ic2.fetch_add(1, Ordering::SeqCst);
}
});
let c3 = Arc::clone(&claim);
let ic3 = Arc::clone(&insert_count);
let b = thread::spawn(move || {
if c3.try_claim() {
ic3.fetch_add(1, Ordering::SeqCst);
}
});
a.join().unwrap();
b.join().unwrap();
assert_eq!(insert_count.load(Ordering::SeqCst), 1);
});
}
#[test]
fn claim_protocol_in_hierarchical_insert() {
loom::model(|| {
let claim = Arc::new(super::super::descriptor::claim::ClaimState::new());
assert!(claim.try_claim());
let group = Arc::new(LoomGroup::new(0));
let cl_a = Arc::clone(&claim);
let g_a = Arc::clone(&group);
let a = thread::spawn(move || {
cl_a.release_claim();
if cl_a.take_wake_requested() {
if cl_a.try_claim() {
g_a.insert();
}
}
});
let cl_b = Arc::clone(&claim);
let g_b = Arc::clone(&group);
let b = thread::spawn(move || {
cl_b.mark_wake_requested();
if cl_b.try_claim() {
g_b.insert();
}
});
a.join().unwrap();
b.join().unwrap();
assert!(
group.count() > 0,
"descriptor not reachable in group after claim/wake protocol"
);
assert!(group.is_in_root());
});
}
}