use loom::sync::atomic::{AtomicBool, AtomicU8, AtomicU32, AtomicU64, AtomicUsize, Ordering};
use loom::sync::{Arc, RwLock};
use loom::thread;
const ACCOUNT_LIVE_BITS: u32 = 16;
const ACCOUNT_LIVE_MASK: u64 = (1_u64 << ACCOUNT_LIVE_BITS) - 1;
fn pack_accounting(live: u32, requested: usize) -> u64 {
(requested as u64) << ACCOUNT_LIVE_BITS | live as u64
}
fn accounting_live(value: u64) -> u32 {
(value & ACCOUNT_LIVE_MASK) as u32
}
fn accounting_requested(value: u64) -> usize {
(value >> ACCOUNT_LIVE_BITS) as usize
}
fn subtract_accounting(owned: u64, remote: u64) -> u64 {
pack_accounting(
accounting_live(owned) - accounting_live(remote),
accounting_requested(owned) - accounting_requested(remote),
)
}
fn snapshot_accounting(owned: &AtomicU64, remote: &AtomicU64) -> u64 {
let remote = remote.load(Ordering::Acquire);
subtract_accounting(owned.load(Ordering::Acquire), remote)
}
fn claim_run_bump(bump: &AtomicU32, capacity: u32) -> Option<u32> {
let mut current = bump.load(Ordering::Acquire);
loop {
if current >= capacity {
return None;
}
match bump.compare_exchange_weak(current, current + 1, Ordering::AcqRel, Ordering::Acquire)
{
Ok(_) => return Some(current),
Err(actual) => current = actual,
}
}
}
fn claim_run_bump_batch(bump: &AtomicU32, capacity: u32, batch: u32) -> Option<(u32, u32)> {
let mut current = bump.load(Ordering::Acquire);
loop {
if current >= capacity {
return None;
}
let end = current.saturating_add(batch).min(capacity);
match bump.compare_exchange_weak(current, end, Ordering::AcqRel, Ordering::Acquire) {
Ok(_) => return Some((current, end)),
Err(actual) => current = actual,
}
}
}
#[test]
fn shared_run_territory_bump_claims_distinct_extents() {
loom::model(|| {
let bump = Arc::new(AtomicU32::new(0));
let accounting = Arc::new(AtomicU64::new(0));
let first = {
let bump = Arc::clone(&bump);
let accounting = Arc::clone(&accounting);
thread::spawn(move || {
let index = claim_run_bump(&bump, 2).unwrap();
accounting.fetch_add(pack_accounting(1, 64 * 1024), Ordering::AcqRel);
index
})
};
let second = {
let bump = Arc::clone(&bump);
let accounting = Arc::clone(&accounting);
thread::spawn(move || {
let index = claim_run_bump(&bump, 2).unwrap();
accounting.fetch_add(pack_accounting(1, 64 * 1024), Ordering::AcqRel);
index
})
};
let first = first.join().unwrap();
let second = second.join().unwrap();
assert_ne!(first, second);
assert_eq!(bump.load(Ordering::Acquire), 2);
let accounting = accounting.load(Ordering::Acquire);
assert_eq!(accounting_live(accounting), 2);
assert_eq!(accounting_requested(accounting), 128 * 1024);
});
}
#[test]
fn owner_local_run_batches_claim_disjoint_ranges() {
loom::model(|| {
let bump = Arc::new(AtomicU32::new(0));
let first = {
let bump = Arc::clone(&bump);
thread::spawn(move || claim_run_bump_batch(&bump, 4, 2).unwrap())
};
let second = {
let bump = Arc::clone(&bump);
thread::spawn(move || claim_run_bump_batch(&bump, 4, 2).unwrap())
};
let first = first.join().unwrap();
let second = second.join().unwrap();
assert!(first.1 <= second.0 || second.1 <= first.0);
assert_eq!(first.1 - first.0, 2);
assert_eq!(second.1 - second.0, 2);
assert_eq!(bump.load(Ordering::Acquire), 4);
});
}
#[test]
fn unused_local_run_slot_publication_is_not_lost() {
loom::model(|| {
let recycled = Arc::new(AtomicU64::new(0));
let publish = {
let recycled = Arc::clone(&recycled);
thread::spawn(move || {
recycled.fetch_or(1 << 1, Ordering::Release);
})
};
let claim = {
let recycled = Arc::clone(&recycled);
thread::spawn(move || {
let mut observed = recycled.load(Ordering::Acquire);
while observed & (1 << 1) != 0 {
match recycled.compare_exchange_weak(
observed,
observed & !(1 << 1),
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => return true,
Err(actual) => observed = actual,
}
}
false
})
};
publish.join().unwrap();
let claimed = claim.join().unwrap();
assert!(claimed || recycled.load(Ordering::Acquire) & (1 << 1) != 0);
});
}
#[test]
fn run_territory_free_publication_is_reusable_or_visible() {
loom::model(|| {
let bump = Arc::new(AtomicU32::new(1));
let recycled = Arc::new(AtomicU64::new(0));
let accounting = Arc::new(AtomicU64::new(pack_accounting(1, 64 * 1024)));
let free = {
let recycled = Arc::clone(&recycled);
let accounting = Arc::clone(&accounting);
thread::spawn(move || {
accounting.fetch_sub(pack_accounting(1, 64 * 1024), Ordering::AcqRel);
recycled.fetch_or(1, Ordering::Release);
})
};
let allocate = {
let bump = Arc::clone(&bump);
let recycled = Arc::clone(&recycled);
let accounting = Arc::clone(&accounting);
thread::spawn(move || {
let mut word = recycled.load(Ordering::Acquire);
while word != 0 {
match recycled.compare_exchange_weak(
word,
word & !1,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => {
accounting.fetch_add(pack_accounting(1, 64 * 1024), Ordering::AcqRel);
return true;
}
Err(actual) => word = actual,
}
}
assert!(claim_run_bump(&bump, 1).is_none());
false
})
};
free.join().unwrap();
let reused = allocate.join().unwrap();
let live = accounting_live(accounting.load(Ordering::Acquire));
let visible = recycled.load(Ordering::Acquire) & 1 != 0;
assert!((reused && live == 1 && !visible) || (!reused && live == 0 && visible));
});
}
fn fold_remote_accounting(owned: &AtomicU64, remote: &AtomicU64) -> u64 {
let observed = remote.load(Ordering::Acquire);
let remote = if observed == 0 {
0
} else {
remote.swap(0, Ordering::AcqRel)
};
subtract_accounting(owned.load(Ordering::Acquire), remote)
}
#[test]
fn owner_allocation_and_remote_free_keep_split_accounting_exact() {
loom::model(|| {
let owned = Arc::new(AtomicU64::new(pack_accounting(1, 96)));
let remote = Arc::new(AtomicU64::new(0));
let allocator = {
let owned = Arc::clone(&owned);
let remote = Arc::clone(&remote);
thread::spawn(move || {
let current = fold_remote_accounting(&owned, &remote);
owned.store(current + pack_accounting(1, 96), Ordering::Release);
})
};
let deallocator = {
let remote = Arc::clone(&remote);
thread::spawn(move || {
remote.fetch_add(pack_accounting(1, 96), Ordering::AcqRel);
})
};
allocator.join().unwrap();
deallocator.join().unwrap();
let final_value = snapshot_accounting(&owned, &remote);
assert_eq!(accounting_live(final_value), 1);
assert_eq!(accounting_requested(final_value), 96);
});
}
#[test]
fn owner_and_remote_deallocation_keep_split_accounting_exact() {
loom::model(|| {
let owned = Arc::new(AtomicU64::new(pack_accounting(2, 176)));
let remote = Arc::new(AtomicU64::new(0));
let owner_free = {
let owned = Arc::clone(&owned);
thread::spawn(move || {
let current = owned.load(Ordering::Acquire);
owned.store(current - pack_accounting(1, 80), Ordering::Release);
})
};
let remote_free = {
let remote = Arc::clone(&remote);
thread::spawn(move || {
remote.fetch_add(pack_accounting(1, 96), Ordering::AcqRel);
})
};
owner_free.join().unwrap();
remote_free.join().unwrap();
let final_value = snapshot_accounting(&owned, &remote);
assert_eq!(accounting_live(final_value), 0);
assert_eq!(accounting_requested(final_value), 0);
});
}
#[test]
fn black_tls_delta_and_remote_free_converge_at_the_lease_boundary() {
loom::model(|| {
let owned = Arc::new(AtomicU64::new(0));
let remote = Arc::new(AtomicU64::new(0));
let published = Arc::new(AtomicBool::new(false));
let cached_allocator = {
let owned = Arc::clone(&owned);
let remote = Arc::clone(&remote);
let published = Arc::clone(&published);
thread::spawn(move || {
let local_delta = pack_accounting(1, 96);
published.store(true, Ordering::Release);
let remote = remote.swap(0, Ordering::AcqRel);
owned.store(local_delta - remote, Ordering::Release);
})
};
let remote_free = {
let remote = Arc::clone(&remote);
let published = Arc::clone(&published);
thread::spawn(move || {
while !published.load(Ordering::Acquire) {
thread::yield_now();
}
remote.fetch_add(pack_accounting(1, 96), Ordering::AcqRel);
})
};
cached_allocator.join().unwrap();
remote_free.join().unwrap();
let final_value = snapshot_accounting(&owned, &remote);
assert_eq!(accounting_live(final_value), 0);
assert_eq!(accounting_requested(final_value), 0);
});
}
#[test]
fn remote_free_publishes_slot_before_empty_becomes_visible() {
loom::model(|| {
let recycled = Arc::new(AtomicBool::new(false));
let remote_frees = Arc::new(AtomicU32::new(0));
let deallocator = {
let recycled = Arc::clone(&recycled);
let remote_frees = Arc::clone(&remote_frees);
thread::spawn(move || {
recycled.store(true, Ordering::Release);
remote_frees.fetch_add(1, Ordering::AcqRel);
})
};
let trimmer = {
let recycled = Arc::clone(&recycled);
let remote_frees = Arc::clone(&remote_frees);
thread::spawn(move || {
if remote_frees.load(Ordering::Acquire) == 1 {
assert!(recycled.load(Ordering::Acquire));
}
})
};
deallocator.join().unwrap();
trimmer.join().unwrap();
assert_eq!(remote_frees.load(Ordering::Acquire), 1);
assert!(recycled.load(Ordering::Acquire));
});
}
#[test]
fn owner_can_reuse_a_published_slot_before_remote_accounting_arrives() {
loom::model(|| {
let recycled = Arc::new(AtomicBool::new(false));
let owned = Arc::new(AtomicU64::new(pack_accounting(1, 96)));
let remote = Arc::new(AtomicU64::new(0));
let deallocator = {
let recycled = Arc::clone(&recycled);
let remote = Arc::clone(&remote);
thread::spawn(move || {
recycled.store(true, Ordering::Release);
remote.fetch_add(pack_accounting(1, 96), Ordering::AcqRel);
})
};
let allocator = {
let recycled = Arc::clone(&recycled);
let owned = Arc::clone(&owned);
thread::spawn(move || {
while recycled
.compare_exchange(true, false, Ordering::AcqRel, Ordering::Acquire)
.is_err()
{
thread::yield_now();
}
let current = owned.load(Ordering::Acquire);
owned.store(current + pack_accounting(1, 96), Ordering::Release);
})
};
deallocator.join().unwrap();
allocator.join().unwrap();
let final_value = snapshot_accounting(&owned, &remote);
assert_eq!(accounting_live(final_value), 1);
assert_eq!(accounting_requested(final_value), 96);
});
}
#[test]
fn published_owner_free_survives_concurrent_owner_transfer() {
loom::model(|| {
let owner = Arc::new(AtomicU8::new(1));
let recycled = Arc::new(AtomicBool::new(false));
let owned = Arc::new(AtomicU64::new(pack_accounting(1, 96)));
let deferred_frees = Arc::new(AtomicU64::new(0));
let deallocator = {
let owner = Arc::clone(&owner);
let recycled = Arc::clone(&recycled);
let deferred_frees = Arc::clone(&deferred_frees);
thread::spawn(move || {
let _observed_owner = owner.load(Ordering::Acquire);
recycled.store(true, Ordering::Release);
deferred_frees.fetch_add(pack_accounting(1, 96), Ordering::AcqRel);
})
};
let new_owner = {
let owner = Arc::clone(&owner);
let owned = Arc::clone(&owned);
let deferred_frees = Arc::clone(&deferred_frees);
thread::spawn(move || {
owner
.compare_exchange(1, 2, Ordering::AcqRel, Ordering::Acquire)
.unwrap();
let current = fold_remote_accounting(&owned, &deferred_frees);
owned.store(current + pack_accounting(1, 96), Ordering::Release);
})
};
deallocator.join().unwrap();
new_owner.join().unwrap();
let final_value = snapshot_accounting(&owned, &deferred_frees);
assert_eq!(owner.load(Ordering::Acquire), 2);
assert_eq!(accounting_live(final_value), 1);
assert_eq!(accounting_requested(final_value), 96);
assert!(recycled.load(Ordering::Acquire));
});
}
#[test]
fn recycled_bitmap_claims_each_slot_once() {
loom::model(|| {
let free = Arc::new(AtomicU64::new(0b11));
let claims = Arc::new(AtomicU32::new(0));
let mut workers = Vec::new();
for _ in 0..2 {
let free = Arc::clone(&free);
let claims = Arc::clone(&claims);
workers.push(thread::spawn(move || {
loop {
let current = free.load(Ordering::Acquire);
assert_ne!(current, 0);
let bit = current.trailing_zeros();
let mask = 1_u64 << bit;
if free
.compare_exchange_weak(
current,
current & !mask,
Ordering::AcqRel,
Ordering::Acquire,
)
.is_ok()
{
let previous = claims.fetch_or(mask as u32, Ordering::AcqRel);
assert_eq!(previous & mask as u32, 0);
break;
}
}
}));
}
for worker in workers {
worker.join().unwrap();
}
assert_eq!(free.load(Ordering::Acquire), 0);
assert_eq!(claims.load(Ordering::Acquire), 0b11);
});
}
#[test]
fn freeze_waits_for_entered_operation() {
loom::model(|| {
const ACTIVE: u32 = 0;
const FREEZING: u32 = 1;
const STATE_MASK: u32 = 0b11;
const ACTIVE_ONE: u32 = 1 << 3;
let control = Arc::new(AtomicU32::new(ACTIVE));
let completed = Arc::new(AtomicU8::new(0));
let operation = {
let control = Arc::clone(&control);
let completed = Arc::clone(&completed);
thread::spawn(move || {
let mut observed = control.load(Ordering::Acquire);
loop {
if observed & STATE_MASK != ACTIVE {
return;
}
match control.compare_exchange_weak(
observed,
observed + ACTIVE_ONE,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => break,
Err(actual) => observed = actual,
}
}
completed.store(1, Ordering::Release);
control.fetch_sub(ACTIVE_ONE, Ordering::Release);
})
};
let freezer = {
let control = Arc::clone(&control);
let completed = Arc::clone(&completed);
thread::spawn(move || {
let mut observed = control.load(Ordering::Acquire);
loop {
if observed & STATE_MASK != ACTIVE {
return;
}
let replacement = (observed & !STATE_MASK) | FREEZING;
match control.compare_exchange_weak(
observed,
replacement,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => break,
Err(actual) => observed = actual,
}
}
while control.load(Ordering::Acquire) / ACTIVE_ONE != 0 {
thread::yield_now();
}
let observed = completed.load(Ordering::Acquire);
assert!(observed <= 1);
})
};
operation.join().unwrap();
freezer.join().unwrap();
});
}
#[test]
fn owner_transfer_waits_for_thread_local_magazine_lease() {
loom::model(|| {
const ACTIVE: u32 = 0;
const FREEZING: u32 = 1;
const STATE_MASK: u32 = 0b11;
const ACTIVE_ONE: u32 = 1 << 3;
let control = Arc::new(AtomicU32::new(ACTIVE));
let owner = Arc::new(AtomicU64::new(1));
let cache = {
let control = Arc::clone(&control);
let owner = Arc::clone(&owner);
thread::spawn(move || {
let mut observed = control.load(Ordering::Acquire);
loop {
if observed & STATE_MASK != ACTIVE {
return;
}
match control.compare_exchange_weak(
observed,
observed + ACTIVE_ONE,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => break,
Err(actual) => observed = actual,
}
}
if owner.load(Ordering::Acquire) != 1 {
control.fetch_sub(ACTIVE_ONE, Ordering::Release);
return;
}
thread::yield_now();
assert_eq!(owner.load(Ordering::Acquire), 1);
control.fetch_sub(ACTIVE_ONE, Ordering::Release);
})
};
let stealer = {
let control = Arc::clone(&control);
let owner = Arc::clone(&owner);
thread::spawn(move || {
let mut observed = control.load(Ordering::Acquire);
loop {
if observed & STATE_MASK != ACTIVE {
return;
}
let freezing = (observed & !STATE_MASK) | FREEZING;
match control.compare_exchange_weak(
observed,
freezing,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => break,
Err(actual) => observed = actual,
}
}
while control.load(Ordering::Acquire) / ACTIVE_ONE != 0 {
thread::yield_now();
}
let _ = owner.compare_exchange(1, 2, Ordering::AcqRel, Ordering::Acquire);
control.store(ACTIVE, Ordering::Release);
})
};
cache.join().unwrap();
stealer.join().unwrap();
assert!(matches!(owner.load(Ordering::Acquire), 1 | 2));
assert_eq!(control.load(Ordering::Acquire), ACTIVE);
});
}
#[test]
fn cached_allocation_revalidates_owner_after_control_entry() {
loom::model(|| {
const ACTIVE: u32 = 0;
const FREEZING: u32 = 1;
const STATE_MASK: u32 = 0b11;
const ACTIVE_ONE: u32 = 1 << 3;
let control = Arc::new(AtomicU32::new(ACTIVE));
let owner = Arc::new(AtomicU64::new(1));
let generation = Arc::new(AtomicU64::new(1));
let accounted = Arc::new(AtomicBool::new(false));
let cached_allocator = {
let control = Arc::clone(&control);
let owner = Arc::clone(&owner);
let generation = Arc::clone(&generation);
let accounted = Arc::clone(&accounted);
thread::spawn(move || {
let cached_owner = owner.load(Ordering::Acquire);
let cached_generation = generation.load(Ordering::Acquire);
thread::yield_now();
let mut observed = control.load(Ordering::Acquire);
loop {
if observed & STATE_MASK != ACTIVE {
return;
}
match control.compare_exchange_weak(
observed,
observed + ACTIVE_ONE,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => break,
Err(actual) => observed = actual,
}
}
if owner.load(Ordering::Acquire) == cached_owner
&& generation.load(Ordering::Acquire) == cached_generation
{
accounted.store(true, Ordering::Release);
thread::yield_now();
assert_eq!(owner.load(Ordering::Acquire), cached_owner);
assert_eq!(generation.load(Ordering::Acquire), cached_generation);
}
control.fetch_sub(ACTIVE_ONE, Ordering::Release);
})
};
let stealer = {
let control = Arc::clone(&control);
let owner = Arc::clone(&owner);
let generation = Arc::clone(&generation);
thread::spawn(move || {
let mut observed = control.load(Ordering::Acquire);
loop {
if observed & STATE_MASK != ACTIVE {
return;
}
let freezing = (observed & !STATE_MASK) | FREEZING;
match control.compare_exchange_weak(
observed,
freezing,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => break,
Err(actual) => observed = actual,
}
}
while control.load(Ordering::Acquire) / ACTIVE_ONE != 0 {
thread::yield_now();
}
owner.store(2, Ordering::Release);
generation.store(2, Ordering::Release);
control.store(ACTIVE, Ordering::Release);
})
};
cached_allocator.join().unwrap();
stealer.join().unwrap();
assert!(matches!(owner.load(Ordering::Acquire), 1 | 2));
assert!(matches!(generation.load(Ordering::Acquire), 1 | 2));
assert_eq!(control.load(Ordering::Acquire), ACTIVE);
let _ = accounted.load(Ordering::Acquire);
});
}
#[test]
fn owner_entry_clears_only_a_published_foreign_probe() {
loom::model(|| {
const ACTIVE: u32 = 0;
const FOREIGN_PROBED: u32 = 1 << 2;
const ACTIVE_ONE: u32 = 1 << 3;
let control = Arc::new(AtomicU32::new(ACTIVE));
let misses = Arc::new(AtomicU32::new(0));
let touch = Arc::new(AtomicU32::new(0));
let foreign = {
let control = Arc::clone(&control);
let misses = Arc::clone(&misses);
thread::spawn(move || {
misses.store(1, Ordering::Relaxed);
control.fetch_or(FOREIGN_PROBED, Ordering::Release);
})
};
let owner = {
let control = Arc::clone(&control);
let misses = Arc::clone(&misses);
let touch = Arc::clone(&touch);
thread::spawn(move || {
let mut observed = control.load(Ordering::Acquire);
loop {
match control.compare_exchange_weak(
observed,
observed + ACTIVE_ONE,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => {
if observed & FOREIGN_PROBED != 0
&& control.fetch_and(!FOREIGN_PROBED, Ordering::AcqRel)
& FOREIGN_PROBED
!= 0
{
touch.fetch_add(1, Ordering::Relaxed);
misses.store(0, Ordering::Relaxed);
}
control.fetch_sub(ACTIVE_ONE, Ordering::Release);
break;
}
Err(actual) => observed = actual,
}
}
})
};
foreign.join().unwrap();
owner.join().unwrap();
let final_control = control.load(Ordering::Acquire);
let final_misses = misses.load(Ordering::Relaxed);
let final_touch = touch.load(Ordering::Relaxed);
assert_eq!(final_control & !(FOREIGN_PROBED), ACTIVE);
assert!(
(final_control & FOREIGN_PROBED != 0 && final_misses == 1)
|| (final_control & FOREIGN_PROBED == 0 && final_misses == 0 && final_touch == 1)
);
});
}
#[test]
fn reserved_activation_publishes_first_live_object_before_trim_can_freeze() {
loom::model(|| {
const ACTIVE: u8 = 0;
const FREEZING: u8 = 1;
const RESERVED: u8 = 0;
const SMALL: u8 = 1;
const RETIRED: u8 = 2;
let state = Arc::new(AtomicU8::new(ACTIVE));
let kind = Arc::new(AtomicU8::new(RESERVED));
let live = Arc::new(AtomicU32::new(0));
let anchor_ready = Arc::new(AtomicU8::new(0));
let activator = {
let state = Arc::clone(&state);
let kind = Arc::clone(&kind);
let live = Arc::clone(&live);
let anchor_ready = Arc::clone(&anchor_ready);
thread::spawn(move || {
if state
.compare_exchange(ACTIVE, FREEZING, Ordering::AcqRel, Ordering::Acquire)
.is_ok()
{
anchor_ready.store(1, Ordering::Relaxed);
live.store(1, Ordering::Relaxed);
kind.store(SMALL, Ordering::Release);
state.store(ACTIVE, Ordering::Release);
}
})
};
let trimmer = {
let state = Arc::clone(&state);
let kind = Arc::clone(&kind);
let live = Arc::clone(&live);
thread::spawn(move || {
if state
.compare_exchange(ACTIVE, FREEZING, Ordering::AcqRel, Ordering::Acquire)
.is_ok()
{
if kind.load(Ordering::Acquire) == RESERVED && live.load(Ordering::Acquire) == 0
{
kind.store(RETIRED, Ordering::Release);
} else {
state.store(ACTIVE, Ordering::Release);
}
}
})
};
activator.join().unwrap();
trimmer.join().unwrap();
if kind.load(Ordering::Acquire) == SMALL {
assert_eq!(live.load(Ordering::Acquire), 1);
assert_eq!(anchor_ready.load(Ordering::Acquire), 1);
}
});
}
#[test]
fn reserved_run_commit_and_first_live_publication_precede_activation() {
loom::model(|| {
const ACTIVE: u8 = 0;
const FREEZING: u8 = 1;
const RESERVED_RUN: u8 = 0;
const RUN: u8 = 1;
const RETIRED: u8 = 2;
let state = Arc::new(AtomicU8::new(ACTIVE));
let kind = Arc::new(AtomicU8::new(RESERVED_RUN));
let committed = Arc::new(AtomicU8::new(0));
let live = Arc::new(AtomicU32::new(0));
let activator = {
let state = Arc::clone(&state);
let kind = Arc::clone(&kind);
let committed = Arc::clone(&committed);
let live = Arc::clone(&live);
thread::spawn(move || {
if state
.compare_exchange(ACTIVE, FREEZING, Ordering::AcqRel, Ordering::Acquire)
.is_ok()
{
committed.store(1, Ordering::Relaxed);
live.store(1, Ordering::Relaxed);
kind.store(RUN, Ordering::Release);
state.store(ACTIVE, Ordering::Release);
}
})
};
let trimmer = {
let state = Arc::clone(&state);
let kind = Arc::clone(&kind);
let live = Arc::clone(&live);
thread::spawn(move || {
if state
.compare_exchange(ACTIVE, FREEZING, Ordering::AcqRel, Ordering::Acquire)
.is_ok()
{
if kind.load(Ordering::Acquire) == RESERVED_RUN
&& live.load(Ordering::Acquire) == 0
{
kind.store(RETIRED, Ordering::Release);
} else {
state.store(ACTIVE, Ordering::Release);
}
}
})
};
activator.join().unwrap();
trimmer.join().unwrap();
if kind.load(Ordering::Acquire) == RUN {
assert_eq!(committed.load(Ordering::Acquire), 1);
assert_eq!(live.load(Ordering::Acquire), 1);
}
});
}
#[test]
fn live_deallocation_can_join_a_stale_freeze_attempt() {
loom::model(|| {
const ACTIVE: u8 = 0;
const FREEZING: u8 = 1;
const FROZEN: u8 = 2;
let state = Arc::new(AtomicU8::new(ACTIVE));
let active_ops = Arc::new(AtomicU32::new(0));
let live = Arc::new(AtomicU32::new(1));
let deallocator = {
let state = Arc::clone(&state);
let active_ops = Arc::clone(&active_ops);
let live = Arc::clone(&live);
thread::spawn(move || {
loop {
let observed = state.load(Ordering::Acquire);
if observed != ACTIVE
&& !(observed == FREEZING && live.load(Ordering::Acquire) != 0)
{
thread::yield_now();
continue;
}
active_ops.fetch_add(1, Ordering::AcqRel);
let observed = state.load(Ordering::Acquire);
if observed == ACTIVE
|| (observed == FREEZING && live.load(Ordering::Acquire) != 0)
{
live.fetch_sub(1, Ordering::AcqRel);
active_ops.fetch_sub(1, Ordering::Release);
break;
}
active_ops.fetch_sub(1, Ordering::Release);
}
})
};
let freezer = {
let state = Arc::clone(&state);
let active_ops = Arc::clone(&active_ops);
let live = Arc::clone(&live);
thread::spawn(move || {
if state
.compare_exchange(ACTIVE, FREEZING, Ordering::AcqRel, Ordering::Acquire)
.is_ok()
{
while active_ops.load(Ordering::Acquire) != 0 {
thread::yield_now();
}
if live.load(Ordering::Acquire) == 0 {
state.store(FROZEN, Ordering::Release);
} else {
state.store(ACTIVE, Ordering::Release);
}
}
})
};
deallocator.join().unwrap();
freezer.join().unwrap();
assert_eq!(live.load(Ordering::Acquire), 0);
});
}
#[test]
fn remote_batch_detach_does_not_lose_concurrent_publishers() {
fn drain(head: &AtomicUsize, next: &[AtomicUsize], seen: &AtomicU32) {
let mut node = head.swap(0, Ordering::AcqRel);
while node != 0 {
let mask = 1_u32 << (node - 1);
assert_eq!(seen.fetch_or(mask, Ordering::AcqRel) & mask, 0);
node = next[node - 1].load(Ordering::Acquire);
}
}
let mut model = loom::model::Builder::new();
model.preemption_bound = Some(2);
model.check(|| {
let head = Arc::new(AtomicUsize::new(0));
let next = Arc::new([AtomicUsize::new(0), AtomicUsize::new(0)]);
let seen = Arc::new(AtomicU32::new(0));
let mut publishers = Vec::new();
for node in 1..=2 {
let head = Arc::clone(&head);
let next = Arc::clone(&next);
publishers.push(thread::spawn(move || {
let mut observed = head.load(Ordering::Acquire);
loop {
next[node - 1].store(observed, Ordering::Relaxed);
match head.compare_exchange_weak(
observed,
node,
Ordering::Release,
Ordering::Acquire,
) {
Ok(_) => break,
Err(actual) => observed = actual,
}
}
}));
}
let drainer = {
let head = Arc::clone(&head);
let next = Arc::clone(&next);
let seen = Arc::clone(&seen);
thread::spawn(move || drain(&head, &*next, &seen))
};
for publisher in publishers {
publisher.join().unwrap();
}
drainer.join().unwrap();
drain(&head, &*next, &seen);
assert_eq!(seen.load(Ordering::Acquire), 0b11);
});
}
#[test]
fn free_extent_claim_publishes_complete_partition_before_expansion() {
loom::model(|| {
const ACTIVE: u8 = 0;
const FROZEN: u8 = 1;
const RETIRED: u8 = 2;
const SOURCE_PAYLOAD: usize = 0;
const COMPLETE_PARTITION: usize = 1;
let stability = Arc::new(RwLock::new(()));
let source = Arc::new(AtomicU8::new(ACTIVE));
let leaf_payload = Arc::new(AtomicUsize::new(SOURCE_PAYLOAD));
let in_flight = Arc::new(AtomicUsize::new(0));
let expanded = Arc::new(AtomicU8::new(0));
let claimer = {
let stability = Arc::clone(&stability);
let source = Arc::clone(&source);
let leaf_payload = Arc::clone(&leaf_payload);
let in_flight = Arc::clone(&in_flight);
thread::spawn(move || {
let _stable = stability.read().unwrap();
in_flight.fetch_add(1, Ordering::AcqRel);
if source
.compare_exchange(ACTIVE, FROZEN, Ordering::AcqRel, Ordering::Acquire)
.is_ok()
{
assert!(
leaf_payload
.compare_exchange(
SOURCE_PAYLOAD,
COMPLETE_PARTITION,
Ordering::AcqRel,
Ordering::Acquire,
)
.is_ok()
);
source.store(RETIRED, Ordering::Release);
}
in_flight.fetch_sub(1, Ordering::Release);
})
};
let observer = {
let stability = Arc::clone(&stability);
let source = Arc::clone(&source);
let leaf_payload = Arc::clone(&leaf_payload);
let in_flight = Arc::clone(&in_flight);
let expanded = Arc::clone(&expanded);
thread::spawn(move || {
let candidate = source.load(Ordering::Acquire) == ACTIVE
|| leaf_payload.load(Ordering::Acquire) == COMPLETE_PARTITION;
if candidate {
return;
}
let pending = source.load(Ordering::Acquire) == FROZEN
|| in_flight.load(Ordering::Acquire) != 0;
if pending {
return;
}
if let Ok(_maintenance) = stability.try_write() {
let candidate = source.load(Ordering::Acquire) == ACTIVE
|| leaf_payload.load(Ordering::Acquire) == COMPLETE_PARTITION;
if !candidate {
expanded.store(1, Ordering::Release);
}
}
})
};
claimer.join().unwrap();
observer.join().unwrap();
assert_eq!(leaf_payload.load(Ordering::Acquire), COMPLETE_PARTITION);
assert_eq!(expanded.load(Ordering::Acquire), 0);
});
}
#[test]
fn root_collapse_publishes_redirect_before_root_pointer() {
const INIT: u8 = 0;
const FROZEN: u8 = 1;
const LINKED: u8 = 2;
const PARENTED: u8 = 3;
const DONE: u8 = 4;
const OLD_ROOT: usize = 0;
const CHILD_ROOT: usize = 1;
const SINGLE_CHILD: usize = 0;
const REDIRECT: usize = 1;
const OLD_PARENT: usize = 1;
const NO_PARENT: usize = 0;
let mut model = loom::model::Builder::new();
model.preemption_bound = Some(3);
model.check(|| {
let phase = Arc::new(AtomicU8::new(INIT));
let root = Arc::new(AtomicUsize::new(OLD_ROOT));
let old_payload = Arc::new(AtomicUsize::new(SINGLE_CHILD));
let child_parent = Arc::new(AtomicUsize::new(OLD_PARENT));
let helper = {
let phase = Arc::clone(&phase);
let root = Arc::clone(&root);
let old_payload = Arc::clone(&old_payload);
let child_parent = Arc::clone(&child_parent);
thread::spawn(move || {
loop {
match phase.load(Ordering::Acquire) {
INIT => phase.store(FROZEN, Ordering::Release),
FROZEN => {
assert!(
old_payload
.compare_exchange(
SINGLE_CHILD,
REDIRECT,
Ordering::AcqRel,
Ordering::Acquire,
)
.is_ok()
);
thread::yield_now();
assert!(
root.compare_exchange(
OLD_ROOT,
CHILD_ROOT,
Ordering::AcqRel,
Ordering::Acquire,
)
.is_ok()
);
phase.store(LINKED, Ordering::Release);
}
LINKED => {
child_parent.store(NO_PARENT, Ordering::Release);
phase.store(PARENTED, Ordering::Release);
}
PARENTED => phase.store(DONE, Ordering::Release),
DONE => break,
_ => unreachable!(),
}
thread::yield_now();
}
})
};
let reader = {
let root = Arc::clone(&root);
let old_payload = Arc::clone(&old_payload);
thread::spawn(move || {
let observed_root = root.load(Ordering::Acquire);
if observed_root == CHILD_ROOT {
assert_eq!(old_payload.load(Ordering::Acquire), REDIRECT);
} else if old_payload.load(Ordering::Acquire) == REDIRECT {
assert_eq!(observed_root, OLD_ROOT);
}
})
};
helper.join().unwrap();
reader.join().unwrap();
assert_eq!(root.load(Ordering::Acquire), CHILD_ROOT);
assert_eq!(old_payload.load(Ordering::Acquire), REDIRECT);
assert_eq!(child_parent.load(Ordering::Acquire), NO_PARENT);
});
}
#[test]
fn cross_parent_redirect_reopens_only_a_complete_transaction() {
const STABLE: usize = 0;
const FROZEN: usize = 1;
const NEXT: usize = 2;
const OLD: usize = 0;
const NEW: usize = 1;
let mut model = loom::model::Builder::new();
model.preemption_bound = Some(2);
model.check(|| {
let source_version = Arc::new(AtomicUsize::new(STABLE));
let left_version = Arc::new(AtomicUsize::new(STABLE));
let parent_version = Arc::new(AtomicUsize::new(STABLE));
let source_redirect = Arc::new(AtomicUsize::new(OLD));
let left_right = Arc::new(AtomicUsize::new(OLD));
let left_high = Arc::new(AtomicUsize::new(OLD));
let left_payload = Arc::new(AtomicUsize::new(OLD));
let parent_removed = Arc::new(AtomicUsize::new(OLD));
let helper = {
let source_version = Arc::clone(&source_version);
let left_version = Arc::clone(&left_version);
let parent_version = Arc::clone(&parent_version);
let source_redirect = Arc::clone(&source_redirect);
let left_right = Arc::clone(&left_right);
let left_high = Arc::clone(&left_high);
let left_payload = Arc::clone(&left_payload);
let parent_removed = Arc::clone(&parent_removed);
thread::spawn(move || {
assert!(
source_version
.compare_exchange(STABLE, FROZEN, Ordering::AcqRel, Ordering::Acquire)
.is_ok()
);
assert!(
parent_version
.compare_exchange(STABLE, FROZEN, Ordering::AcqRel, Ordering::Acquire)
.is_ok()
);
assert!(
left_version
.compare_exchange(STABLE, FROZEN, Ordering::AcqRel, Ordering::Acquire)
.is_ok()
);
left_right.store(NEW, Ordering::Release);
left_high.store(NEW, Ordering::Release);
left_payload.store(NEW, Ordering::Release);
parent_removed.store(NEW, Ordering::Release);
source_redirect.store(NEW, Ordering::Release);
left_version.store(NEXT, Ordering::Release);
parent_version.store(NEXT, Ordering::Release);
source_version.store(NEXT, Ordering::Release);
})
};
let observer = {
let source_version = Arc::clone(&source_version);
let left_version = Arc::clone(&left_version);
let parent_version = Arc::clone(&parent_version);
let source_redirect = Arc::clone(&source_redirect);
let left_right = Arc::clone(&left_right);
let left_high = Arc::clone(&left_high);
let left_payload = Arc::clone(&left_payload);
let parent_removed = Arc::clone(&parent_removed);
thread::spawn(move || {
for version in [&left_version, &parent_version, &source_version] {
let before = version.load(Ordering::Acquire);
if before == FROZEN {
thread::yield_now();
continue;
}
let right = left_right.load(Ordering::Acquire);
let high = left_high.load(Ordering::Acquire);
let payload = left_payload.load(Ordering::Acquire);
let removed = parent_removed.load(Ordering::Acquire);
let redirect = source_redirect.load(Ordering::Acquire);
let after = version.load(Ordering::Acquire);
if before == after && after == NEXT {
assert_eq!(
(right, high, payload, removed, redirect),
(NEW, NEW, NEW, NEW, NEW)
);
}
}
})
};
helper.join().unwrap();
observer.join().unwrap();
assert_eq!(left_right.load(Ordering::Acquire), NEW);
assert_eq!(left_high.load(Ordering::Acquire), NEW);
assert_eq!(left_payload.load(Ordering::Acquire), NEW);
assert_eq!(parent_removed.load(Ordering::Acquire), NEW);
assert_eq!(source_redirect.load(Ordering::Acquire), NEW);
});
}
#[test]
fn internal_redistribution_reopens_only_after_separator_and_payloads() {
const STABLE: usize = 0;
const FROZEN: usize = 1;
const NEXT: usize = 2;
const OLD: usize = 0;
const NEW: usize = 1;
let mut model = loom::model::Builder::new();
model.preemption_bound = Some(2);
model.check(|| {
let source_version = Arc::new(AtomicUsize::new(STABLE));
let sibling_version = Arc::new(AtomicUsize::new(STABLE));
let parent_version = Arc::new(AtomicUsize::new(STABLE));
let source_payload = Arc::new(AtomicUsize::new(OLD));
let sibling_payload = Arc::new(AtomicUsize::new(OLD));
let parent_separator = Arc::new(AtomicUsize::new(OLD));
let changed_fence = Arc::new(AtomicUsize::new(OLD));
let moved_parent = Arc::new(AtomicUsize::new(OLD));
let helper = {
let source_version = Arc::clone(&source_version);
let sibling_version = Arc::clone(&sibling_version);
let parent_version = Arc::clone(&parent_version);
let source_payload = Arc::clone(&source_payload);
let sibling_payload = Arc::clone(&sibling_payload);
let parent_separator = Arc::clone(&parent_separator);
let changed_fence = Arc::clone(&changed_fence);
let moved_parent = Arc::clone(&moved_parent);
thread::spawn(move || {
assert!(
source_version
.compare_exchange(STABLE, FROZEN, Ordering::AcqRel, Ordering::Acquire)
.is_ok()
);
assert!(
parent_version
.compare_exchange(STABLE, FROZEN, Ordering::AcqRel, Ordering::Acquire)
.is_ok()
);
assert!(
sibling_version
.compare_exchange(STABLE, FROZEN, Ordering::AcqRel, Ordering::Acquire)
.is_ok()
);
changed_fence.store(NEW, Ordering::Release);
sibling_payload.store(NEW, Ordering::Release);
parent_separator.store(NEW, Ordering::Release);
source_payload.store(NEW, Ordering::Release);
moved_parent.store(NEW, Ordering::Release);
sibling_version.store(NEXT, Ordering::Release);
parent_version.store(NEXT, Ordering::Release);
source_version.store(NEXT, Ordering::Release);
})
};
let observer = {
let source_version = Arc::clone(&source_version);
let sibling_version = Arc::clone(&sibling_version);
let parent_version = Arc::clone(&parent_version);
let source_payload = Arc::clone(&source_payload);
let sibling_payload = Arc::clone(&sibling_payload);
let parent_separator = Arc::clone(&parent_separator);
let changed_fence = Arc::clone(&changed_fence);
let moved_parent = Arc::clone(&moved_parent);
thread::spawn(move || {
for version in [&source_version, &sibling_version, &parent_version] {
let before = version.load(Ordering::Acquire);
if before == FROZEN {
thread::yield_now();
continue;
}
let observed = (
source_payload.load(Ordering::Acquire),
sibling_payload.load(Ordering::Acquire),
parent_separator.load(Ordering::Acquire),
changed_fence.load(Ordering::Acquire),
moved_parent.load(Ordering::Acquire),
);
let after = version.load(Ordering::Acquire);
if before == after && after == NEXT {
assert_eq!(observed, (NEW, NEW, NEW, NEW, NEW));
}
}
})
};
helper.join().unwrap();
observer.join().unwrap();
assert_eq!(source_payload.load(Ordering::Acquire), NEW);
assert_eq!(sibling_payload.load(Ordering::Acquire), NEW);
assert_eq!(parent_separator.load(Ordering::Acquire), NEW);
assert_eq!(changed_fence.load(Ordering::Acquire), NEW);
assert_eq!(moved_parent.load(Ordering::Acquire), NEW);
});
}
#[test]
fn maintenance_gate_excludes_new_extent_transactions_and_drains_old_ones() {
loom::model(|| {
const MAINTENANCE: usize = 1 << (usize::BITS - 1);
let control = Arc::new(AtomicUsize::new(0));
let critical = Arc::new(AtomicU8::new(0));
let transaction = {
let control = Arc::clone(&control);
let critical = Arc::clone(&critical);
thread::spawn(move || {
let mut observed = control.load(Ordering::Acquire);
loop {
if observed & MAINTENANCE != 0 {
return;
}
match control.compare_exchange_weak(
observed,
observed + 1,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => break,
Err(actual) => observed = actual,
}
}
assert_eq!(critical.load(Ordering::Acquire), 0);
thread::yield_now();
assert_eq!(critical.load(Ordering::Acquire), 0);
control.fetch_sub(1, Ordering::Release);
})
};
let maintainer = {
let control = Arc::clone(&control);
let critical = Arc::clone(&critical);
thread::spawn(move || {
control.fetch_or(MAINTENANCE, Ordering::AcqRel);
while control.load(Ordering::Acquire) != MAINTENANCE {
thread::yield_now();
}
critical.store(1, Ordering::Release);
assert_eq!(control.load(Ordering::Acquire), MAINTENANCE);
thread::yield_now();
assert_eq!(control.load(Ordering::Acquire), MAINTENANCE);
critical.store(0, Ordering::Release);
control.fetch_and(!MAINTENANCE, Ordering::Release);
})
};
transaction.join().unwrap();
maintainer.join().unwrap();
assert_eq!(control.load(Ordering::Acquire), 0);
});
}
#[test]
fn root_replace_descriptor_can_be_completed_by_any_helper() {
const INIT: u8 = 0;
const FROZEN: u8 = 1;
const LINKED: u8 = 2;
const PARENTED: u8 = 3;
const DONE: u8 = 4;
const OLD_ROOT: usize = 1;
const NEW_ROOT: usize = 2;
fn help(
phase: &AtomicU8,
root: &AtomicUsize,
left_parent: &AtomicUsize,
right_parent: &AtomicUsize,
) {
loop {
match phase.load(Ordering::Acquire) {
INIT => {
let _ =
phase.compare_exchange(INIT, FROZEN, Ordering::AcqRel, Ordering::Acquire);
}
FROZEN => {
let current = root.load(Ordering::Acquire);
let linked = current == NEW_ROOT
|| (current == OLD_ROOT
&& match root.compare_exchange(
OLD_ROOT,
NEW_ROOT,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => true,
Err(actual) => actual == NEW_ROOT,
});
assert!(linked);
let _ =
phase.compare_exchange(FROZEN, LINKED, Ordering::AcqRel, Ordering::Acquire);
}
LINKED => {
left_parent.store(NEW_ROOT, Ordering::Release);
right_parent.store(NEW_ROOT, Ordering::Release);
let _ = phase.compare_exchange(
LINKED,
PARENTED,
Ordering::AcqRel,
Ordering::Acquire,
);
}
PARENTED => {
let _ =
phase.compare_exchange(PARENTED, DONE, Ordering::AcqRel, Ordering::Acquire);
}
DONE => return,
_ => unreachable!(),
}
thread::yield_now();
}
}
let mut model = loom::model::Builder::new();
model.preemption_bound = Some(3);
model.check(|| {
let phase = Arc::new(AtomicU8::new(INIT));
let root = Arc::new(AtomicUsize::new(OLD_ROOT));
let left_parent = Arc::new(AtomicUsize::new(0));
let right_parent = Arc::new(AtomicUsize::new(0));
let mut helpers = Vec::new();
for _ in 0..2 {
let phase = Arc::clone(&phase);
let root = Arc::clone(&root);
let left_parent = Arc::clone(&left_parent);
let right_parent = Arc::clone(&right_parent);
helpers.push(thread::spawn(move || {
help(&phase, &root, &left_parent, &right_parent)
}));
}
for helper in helpers {
helper.join().unwrap();
}
assert_eq!(phase.load(Ordering::Acquire), DONE);
assert_eq!(root.load(Ordering::Acquire), NEW_ROOT);
assert_eq!(left_parent.load(Ordering::Acquire), NEW_ROOT);
assert_eq!(right_parent.load(Ordering::Acquire), NEW_ROOT);
});
}
#[test]
fn logical_remove_descriptor_can_be_completed_by_any_helper() {
const INIT: u8 = 0;
const FROZEN: u8 = 1;
const LINKED: u8 = 2;
const PARENTED: u8 = 3;
const DONE: u8 = 4;
const STABLE_VERSION: usize = 0;
const FROZEN_VERSION: usize = 1;
const NEXT_VERSION: usize = 2;
const OLD_PAYLOAD: usize = 1;
const REMOVED_PAYLOAD: usize = 2;
fn help(phase: &AtomicU8, version: &AtomicUsize, payload: &AtomicUsize) {
loop {
match phase.load(Ordering::Acquire) {
INIT => {
let acquired = match version.compare_exchange(
STABLE_VERSION,
FROZEN_VERSION,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => true,
Err(actual) => actual == FROZEN_VERSION,
};
assert!(acquired);
let _ =
phase.compare_exchange(INIT, FROZEN, Ordering::AcqRel, Ordering::Acquire);
}
FROZEN => {
thread::yield_now();
let replaced = match payload.compare_exchange(
OLD_PAYLOAD,
REMOVED_PAYLOAD,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => true,
Err(actual) => actual == REMOVED_PAYLOAD,
};
if replaced {
let _ = phase.compare_exchange(
FROZEN,
LINKED,
Ordering::AcqRel,
Ordering::Acquire,
);
}
}
LINKED => {
let _ = version.compare_exchange(
FROZEN_VERSION,
NEXT_VERSION,
Ordering::Release,
Ordering::Acquire,
);
let _ = phase.compare_exchange(
LINKED,
PARENTED,
Ordering::AcqRel,
Ordering::Acquire,
);
}
PARENTED => {
let _ =
phase.compare_exchange(PARENTED, DONE, Ordering::AcqRel, Ordering::Acquire);
}
DONE => return,
_ => unreachable!(),
}
thread::yield_now();
}
}
let mut model = loom::model::Builder::new();
model.preemption_bound = Some(3);
model.check(|| {
let phase = Arc::new(AtomicU8::new(INIT));
let version = Arc::new(AtomicUsize::new(STABLE_VERSION));
let payload = Arc::new(AtomicUsize::new(OLD_PAYLOAD));
let mut helpers = Vec::new();
for _ in 0..2 {
let phase = Arc::clone(&phase);
let version = Arc::clone(&version);
let payload = Arc::clone(&payload);
helpers.push(thread::spawn(move || help(&phase, &version, &payload)));
}
for helper in helpers {
helper.join().unwrap();
}
assert_eq!(phase.load(Ordering::Acquire), DONE);
assert_eq!(version.load(Ordering::Acquire), NEXT_VERSION);
assert_eq!(payload.load(Ordering::Acquire), REMOVED_PAYLOAD);
});
}
#[test]
fn immutable_payload_cas_upserts_do_not_lose_keys() {
let mut model = loom::model::Builder::new();
model.preemption_bound = Some(3);
model.check(|| {
let payload = Arc::new(AtomicUsize::new(1));
let mut writers = Vec::new();
for key_bit in [2, 4] {
let payload = Arc::clone(&payload);
writers.push(thread::spawn(move || {
let mut observed = payload.load(Ordering::Acquire);
loop {
let replacement = observed | key_bit;
match payload.compare_exchange_weak(
observed,
replacement,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => break,
Err(actual) => observed = actual,
}
}
}));
}
for writer in writers {
writer.join().unwrap();
}
assert_eq!(payload.load(Ordering::Acquire), 7);
});
}
#[test]
fn late_logical_remove_helper_cannot_erase_a_reinsert() {
const FROZEN: u8 = 1;
const LINKED: u8 = 2;
const DONE: u8 = 4;
const OLD: usize = 1;
const REMOVED: usize = 2;
const REINSERTED: usize = 3;
fn publish_frozen(phase: &AtomicU8, payload: &AtomicUsize) {
if phase.load(Ordering::Acquire) != FROZEN {
return;
}
thread::yield_now();
let _ = payload.compare_exchange(OLD, REMOVED, Ordering::AcqRel, Ordering::Acquire);
let _ = phase.compare_exchange(FROZEN, LINKED, Ordering::AcqRel, Ordering::Acquire);
}
let mut model = loom::model::Builder::new();
model.preemption_bound = Some(3);
model.check(|| {
let phase = Arc::new(AtomicU8::new(FROZEN));
let payload = Arc::new(AtomicUsize::new(OLD));
let version = Arc::new(AtomicUsize::new(FROZEN as usize));
let late_helper = {
let phase = Arc::clone(&phase);
let payload = Arc::clone(&payload);
thread::spawn(move || publish_frozen(&phase, &payload))
};
let completer = {
let phase = Arc::clone(&phase);
let payload = Arc::clone(&payload);
let version = Arc::clone(&version);
thread::spawn(move || {
publish_frozen(&phase, &payload);
loop {
match phase.load(Ordering::Acquire) {
FROZEN => thread::yield_now(),
LINKED => {
let _ = version.compare_exchange(
FROZEN as usize,
LINKED as usize,
Ordering::Release,
Ordering::Acquire,
);
phase.store(DONE, Ordering::Release);
}
DONE => break,
_ => unreachable!(),
}
}
assert!(
payload
.compare_exchange(REMOVED, REINSERTED, Ordering::AcqRel, Ordering::Acquire,)
.is_ok()
);
})
};
late_helper.join().unwrap();
completer.join().unwrap();
assert_eq!(payload.load(Ordering::Acquire), REINSERTED);
});
}
#[test]
fn redirect_is_not_visible_before_parent_cleanup() {
const INIT: u8 = 0;
const FROZEN: u8 = 1;
const LINKED: u8 = 2;
const PARENTED: u8 = 3;
const DONE: u8 = 4;
const STABLE_VERSION: usize = 0;
const FROZEN_VERSION: usize = 1;
const NEXT_VERSION: usize = 2;
const EMPTY_LEAF: usize = 1;
const REDIRECT: usize = 2;
let mut model = loom::model::Builder::new();
model.preemption_bound = Some(3);
model.check(|| {
let phase = Arc::new(AtomicU8::new(INIT));
let version = Arc::new(AtomicUsize::new(STABLE_VERSION));
let payload = Arc::new(AtomicUsize::new(EMPTY_LEAF));
let parent_contains_leaf = Arc::new(AtomicUsize::new(1));
let helper = {
let phase = Arc::clone(&phase);
let version = Arc::clone(&version);
let payload = Arc::clone(&payload);
let parent_contains_leaf = Arc::clone(&parent_contains_leaf);
thread::spawn(move || {
loop {
match phase.load(Ordering::Acquire) {
INIT => {
assert!(
version
.compare_exchange(
STABLE_VERSION,
FROZEN_VERSION,
Ordering::AcqRel,
Ordering::Acquire,
)
.is_ok()
);
phase.store(FROZEN, Ordering::Release);
}
FROZEN => {
assert!(
parent_contains_leaf
.compare_exchange(1, 0, Ordering::AcqRel, Ordering::Acquire)
.is_ok()
);
thread::yield_now();
assert_eq!(parent_contains_leaf.load(Ordering::Acquire), 0);
assert!(
payload
.compare_exchange(
EMPTY_LEAF,
REDIRECT,
Ordering::AcqRel,
Ordering::Acquire,
)
.is_ok()
);
phase.store(LINKED, Ordering::Release);
}
LINKED => {
version.store(NEXT_VERSION, Ordering::Release);
phase.store(PARENTED, Ordering::Release);
}
PARENTED => phase.store(DONE, Ordering::Release),
DONE => break,
_ => unreachable!(),
}
thread::yield_now();
}
})
};
let reader = {
let version = Arc::clone(&version);
let payload = Arc::clone(&payload);
let parent_contains_leaf = Arc::clone(&parent_contains_leaf);
thread::spawn(move || {
while version.load(Ordering::Acquire) != NEXT_VERSION {
thread::yield_now();
}
assert_eq!(payload.load(Ordering::Acquire), REDIRECT);
assert_eq!(parent_contains_leaf.load(Ordering::Acquire), 0);
})
};
helper.join().unwrap();
reader.join().unwrap();
assert_eq!(phase.load(Ordering::Acquire), DONE);
});
}
#[test]
fn late_leaf_split_helper_cannot_overwrite_a_newer_mutation() {
const FROZEN: u8 = 1;
const LINKED: u8 = 2;
const DONE: u8 = 4;
const OLD: usize = 1;
const SPLIT: usize = 2;
const NEWER: usize = 3;
fn publish_frozen(phase: &AtomicU8, payload: &AtomicUsize, sibling: &AtomicUsize) {
if phase.load(Ordering::Acquire) != FROZEN {
return;
}
thread::yield_now();
let _ = payload.compare_exchange(OLD, SPLIT, Ordering::AcqRel, Ordering::Acquire);
let _ = sibling.compare_exchange(OLD, SPLIT, Ordering::AcqRel, Ordering::Acquire);
let _ = phase.compare_exchange(FROZEN, LINKED, Ordering::AcqRel, Ordering::Acquire);
}
let mut model = loom::model::Builder::new();
model.preemption_bound = Some(3);
model.check(|| {
let phase = Arc::new(AtomicU8::new(FROZEN));
let payload = Arc::new(AtomicUsize::new(OLD));
let sibling = Arc::new(AtomicUsize::new(OLD));
let high_key = Arc::new(AtomicUsize::new(OLD));
let version = Arc::new(AtomicUsize::new(FROZEN as usize));
let late_helper = {
let phase = Arc::clone(&phase);
let payload = Arc::clone(&payload);
let sibling = Arc::clone(&sibling);
thread::spawn(move || publish_frozen(&phase, &payload, &sibling))
};
let completer = {
let phase = Arc::clone(&phase);
let payload = Arc::clone(&payload);
let sibling = Arc::clone(&sibling);
let high_key = Arc::clone(&high_key);
let version = Arc::clone(&version);
thread::spawn(move || {
publish_frozen(&phase, &payload, &sibling);
loop {
match phase.load(Ordering::Acquire) {
FROZEN => thread::yield_now(),
LINKED => {
let _ = high_key.compare_exchange(
OLD,
SPLIT,
Ordering::AcqRel,
Ordering::Acquire,
);
let _ = version.compare_exchange(
FROZEN as usize,
LINKED as usize,
Ordering::AcqRel,
Ordering::Acquire,
);
phase.store(DONE, Ordering::Release);
}
DONE => break,
_ => unreachable!(),
}
}
assert!(
payload
.compare_exchange(SPLIT, NEWER, Ordering::AcqRel, Ordering::Acquire)
.is_ok()
);
assert!(
sibling
.compare_exchange(SPLIT, NEWER, Ordering::AcqRel, Ordering::Acquire)
.is_ok()
);
assert!(
high_key
.compare_exchange(SPLIT, NEWER, Ordering::AcqRel, Ordering::Acquire)
.is_ok()
);
})
};
late_helper.join().unwrap();
completer.join().unwrap();
assert_eq!(payload.load(Ordering::Acquire), NEWER);
assert_eq!(sibling.load(Ordering::Acquire), NEWER);
assert_eq!(high_key.load(Ordering::Acquire), NEWER);
});
}
#[test]
fn late_multi_node_helper_accepts_completion_bits_after_reopen() {
const FROZEN: u8 = 1;
const LINKED: u8 = 2;
const DONE: u8 = 4;
const OLD: usize = 1;
const TRANSACTION: usize = 2;
const NEWER: usize = 3;
fn publish_component(
phase: &AtomicU8,
replaced: &AtomicU8,
bit: u8,
payload: &AtomicUsize,
) -> bool {
if replaced.load(Ordering::Acquire) & bit != 0 {
return true;
}
if phase.load(Ordering::Acquire) != FROZEN {
return replaced.load(Ordering::Acquire) & bit != 0;
}
thread::yield_now();
let published =
match payload.compare_exchange(OLD, TRANSACTION, Ordering::AcqRel, Ordering::Acquire) {
Ok(_) => true,
Err(current) => current == TRANSACTION,
};
if published {
replaced.fetch_or(bit, Ordering::AcqRel);
true
} else {
replaced.load(Ordering::Acquire) & bit != 0
}
}
fn publish_all(
phase: &AtomicU8,
replaced: &AtomicU8,
source: &AtomicUsize,
parent: &AtomicUsize,
sibling: &AtomicUsize,
) {
assert!(publish_component(phase, replaced, 1, source));
assert!(publish_component(phase, replaced, 2, parent));
assert!(publish_component(phase, replaced, 4, sibling));
if replaced.load(Ordering::Acquire) == 7 {
let _ = phase.compare_exchange(FROZEN, LINKED, Ordering::AcqRel, Ordering::Acquire);
}
}
let mut model = loom::model::Builder::new();
model.preemption_bound = Some(3);
model.check(|| {
let phase = Arc::new(AtomicU8::new(FROZEN));
let replaced = Arc::new(AtomicU8::new(0));
let source = Arc::new(AtomicUsize::new(OLD));
let parent = Arc::new(AtomicUsize::new(OLD));
let sibling = Arc::new(AtomicUsize::new(OLD));
let late_helper = {
let phase = Arc::clone(&phase);
let replaced = Arc::clone(&replaced);
let source = Arc::clone(&source);
let parent = Arc::clone(&parent);
let sibling = Arc::clone(&sibling);
thread::spawn(move || publish_all(&phase, &replaced, &source, &parent, &sibling))
};
let completer = {
let phase = Arc::clone(&phase);
let replaced = Arc::clone(&replaced);
let source = Arc::clone(&source);
let parent = Arc::clone(&parent);
let sibling = Arc::clone(&sibling);
thread::spawn(move || {
while phase.load(Ordering::Acquire) == FROZEN {
publish_all(&phase, &replaced, &source, &parent, &sibling);
}
assert_eq!(replaced.load(Ordering::Acquire), 7);
phase.store(DONE, Ordering::Release);
for payload in [&source, &parent, &sibling] {
assert!(
payload
.compare_exchange(
TRANSACTION,
NEWER,
Ordering::AcqRel,
Ordering::Acquire,
)
.is_ok()
);
}
})
};
late_helper.join().unwrap();
completer.join().unwrap();
assert_eq!(phase.load(Ordering::Acquire), DONE);
assert_eq!(replaced.load(Ordering::Acquire), 7);
assert_eq!(source.load(Ordering::Acquire), NEWER);
assert_eq!(parent.load(Ordering::Acquire), NEWER);
assert_eq!(sibling.load(Ordering::Acquire), NEWER);
});
}
#[test]
fn internal_predecessor_split_is_spliced_before_redirect_retirement() {
const SOURCE: usize = 1;
const TARGET: usize = 2;
const SPLIT_RIGHT: usize = 3;
let mut model = loom::model::Builder::new();
model.preemption_bound = Some(3);
model.check(|| {
let predecessor_right = Arc::new(AtomicUsize::new(SOURCE));
let split_right_link = Arc::new(AtomicUsize::new(SOURCE));
let retired = Arc::new(AtomicBool::new(false));
let splitter = {
let predecessor_right = Arc::clone(&predecessor_right);
let split_right_link = Arc::clone(&split_right_link);
thread::spawn(move || {
split_right_link.store(SOURCE, Ordering::Release);
let _ = predecessor_right.compare_exchange(
SOURCE,
SPLIT_RIGHT,
Ordering::AcqRel,
Ordering::Acquire,
);
})
};
let splicer = {
let predecessor_right = Arc::clone(&predecessor_right);
let split_right_link = Arc::clone(&split_right_link);
let retired = Arc::clone(&retired);
thread::spawn(move || {
loop {
match predecessor_right.load(Ordering::Acquire) {
SOURCE => {
let _ = predecessor_right.compare_exchange(
SOURCE,
TARGET,
Ordering::AcqRel,
Ordering::Acquire,
);
}
SPLIT_RIGHT => {
let _ = split_right_link.compare_exchange(
SOURCE,
TARGET,
Ordering::AcqRel,
Ordering::Acquire,
);
}
TARGET => {}
_ => unreachable!(),
}
let head = predecessor_right.load(Ordering::Acquire);
let incoming = head == SOURCE
|| (head == SPLIT_RIGHT
&& split_right_link.load(Ordering::Acquire) == SOURCE);
if !incoming {
retired.store(true, Ordering::Release);
break;
}
thread::yield_now();
}
})
};
splitter.join().unwrap();
splicer.join().unwrap();
assert!(retired.load(Ordering::Acquire));
let head = predecessor_right.load(Ordering::Acquire);
assert_ne!(head, SOURCE);
if head == SPLIT_RIGHT {
assert_eq!(split_right_link.load(Ordering::Acquire), TARGET);
}
});
}
#[test]
fn tree_node_slab_is_destroyed_once_after_owner_and_last_node_release() {
fn release(references: &AtomicUsize, destroyed: &AtomicBool) {
if references.fetch_sub(1, Ordering::Release) != 1 {
return;
}
loom::sync::atomic::fence(Ordering::Acquire);
assert!(!destroyed.swap(true, Ordering::AcqRel));
}
loom::model(|| {
let references = Arc::new(AtomicUsize::new(2));
let destroyed = Arc::new(AtomicBool::new(false));
let owner = {
let references = Arc::clone(&references);
let destroyed = Arc::clone(&destroyed);
thread::spawn(move || release(&references, &destroyed))
};
let node = {
let references = Arc::clone(&references);
let destroyed = Arc::clone(&destroyed);
thread::spawn(move || release(&references, &destroyed))
};
owner.join().unwrap();
node.join().unwrap();
assert_eq!(references.load(Ordering::Acquire), 0);
assert!(destroyed.load(Ordering::Acquire));
});
}
#[test]
fn retired_node_slot_is_not_reused_before_the_reader_grace_period() {
const EMPTY: usize = 0;
const OLD_NODE: usize = 1;
const NEW_NODE: usize = 2;
loom::model(|| {
let slot = Arc::new(AtomicUsize::new(OLD_NODE));
let reader_pinned = Arc::new(AtomicBool::new(false));
let reader_loaded = Arc::new(AtomicBool::new(false));
let reader_done = Arc::new(AtomicBool::new(false));
let reader = {
let slot = Arc::clone(&slot);
let reader_pinned = Arc::clone(&reader_pinned);
let reader_loaded = Arc::clone(&reader_loaded);
let reader_done = Arc::clone(&reader_done);
thread::spawn(move || {
reader_pinned.store(true, Ordering::Release);
let observed = slot.load(Ordering::Acquire);
assert_eq!(observed, OLD_NODE);
reader_loaded.store(true, Ordering::Release);
thread::yield_now();
assert_eq!(slot.load(Ordering::Acquire), OLD_NODE);
reader_pinned.store(false, Ordering::Release);
reader_done.store(true, Ordering::Release);
})
};
let reclaimer =
{
let slot = Arc::clone(&slot);
let reader_loaded = Arc::clone(&reader_loaded);
let reader_done = Arc::clone(&reader_done);
thread::spawn(move || {
while !reader_loaded.load(Ordering::Acquire) {
thread::yield_now();
}
while !reader_done.load(Ordering::Acquire) {
assert_eq!(slot.load(Ordering::Acquire), OLD_NODE);
thread::yield_now();
}
assert!(slot
.compare_exchange(OLD_NODE, EMPTY, Ordering::AcqRel, Ordering::Acquire,)
.is_ok());
assert!(slot
.compare_exchange(EMPTY, NEW_NODE, Ordering::AcqRel, Ordering::Acquire,)
.is_ok());
})
};
reader.join().unwrap();
reclaimer.join().unwrap();
assert_eq!(slot.load(Ordering::Acquire), NEW_NODE);
});
}
#[test]
fn tagged_node_free_head_rejects_an_aba_pop() {
const INDEX_ONE: u64 = 1;
const INDEX_BITS: u32 = 21;
const INDEX_MASK: u64 = (1_u64 << INDEX_BITS) - 1;
loom::model(|| {
let head = Arc::new(AtomicU64::new(INDEX_ONE));
let stale_loaded = Arc::new(AtomicBool::new(false));
let aba_complete = Arc::new(AtomicBool::new(false));
let stale_popper = {
let head = Arc::clone(&head);
let stale_loaded = Arc::clone(&stale_loaded);
let aba_complete = Arc::clone(&aba_complete);
thread::spawn(move || {
let stale = head.load(Ordering::Acquire);
stale_loaded.store(true, Ordering::Release);
while !aba_complete.load(Ordering::Acquire) {
thread::yield_now();
}
let stale_tag = stale >> INDEX_BITS;
let empty_with_next_tag = (stale_tag + 1) << INDEX_BITS;
assert!(
head.compare_exchange(
stale,
empty_with_next_tag,
Ordering::AcqRel,
Ordering::Acquire,
)
.is_err()
);
})
};
let recycler = {
let head = Arc::clone(&head);
let stale_loaded = Arc::clone(&stale_loaded);
let aba_complete = Arc::clone(&aba_complete);
thread::spawn(move || {
while !stale_loaded.load(Ordering::Acquire) {
thread::yield_now();
}
let old = head.load(Ordering::Acquire);
let first_tag = (old >> INDEX_BITS) + 1;
assert!(
head.compare_exchange(
old,
first_tag << INDEX_BITS,
Ordering::AcqRel,
Ordering::Acquire,
)
.is_ok()
);
let recycled = ((first_tag + 1) << INDEX_BITS) | INDEX_ONE;
assert!(
head.compare_exchange(
first_tag << INDEX_BITS,
recycled,
Ordering::AcqRel,
Ordering::Acquire,
)
.is_ok()
);
aba_complete.store(true, Ordering::Release);
})
};
stale_popper.join().unwrap();
recycler.join().unwrap();
assert_eq!(head.load(Ordering::Acquire) & INDEX_MASK, INDEX_ONE);
assert_eq!(head.load(Ordering::Acquire) >> INDEX_BITS, 2);
});
}
#[test]
fn sealed_cohort_recycles_only_after_last_free_publication() {
const SEALED: u64 = 1 << 63;
loom::model(|| {
let cohort = Arc::new(AtomicU64::new(SEALED | 9));
let live = Arc::new(AtomicU32::new(1));
let slot_published = Arc::new(AtomicBool::new(false));
let freezing = Arc::new(AtomicBool::new(false));
let owner = Arc::new(AtomicU64::new(7));
let generation = Arc::new(AtomicU64::new(3));
let remote_free = {
let live = Arc::clone(&live);
let slot_published = Arc::clone(&slot_published);
thread::spawn(move || {
slot_published.store(true, Ordering::Release);
live.fetch_sub(1, Ordering::Release);
})
};
let recycler = {
let cohort = Arc::clone(&cohort);
let live = Arc::clone(&live);
let slot_published = Arc::clone(&slot_published);
let freezing = Arc::clone(&freezing);
let owner = Arc::clone(&owner);
let generation = Arc::clone(&generation);
thread::spawn(move || {
if live.load(Ordering::Acquire) != 0
|| freezing
.compare_exchange(false, true, Ordering::AcqRel, Ordering::Acquire)
.is_err()
{
return;
}
if live.load(Ordering::Acquire) != 0 {
freezing.store(false, Ordering::Release);
return;
}
assert!(slot_published.load(Ordering::Acquire));
cohort.store(0, Ordering::Relaxed);
generation.fetch_add(1, Ordering::AcqRel);
owner.store(0, Ordering::Release);
freezing.store(false, Ordering::Release);
})
};
remote_free.join().unwrap();
recycler.join().unwrap();
if owner.load(Ordering::Acquire) == 0 {
assert_eq!(live.load(Ordering::Acquire), 0);
assert!(slot_published.load(Ordering::Acquire));
assert_eq!(cohort.load(Ordering::Acquire), 0);
assert_eq!(generation.load(Ordering::Acquire), 4);
} else {
assert_eq!(owner.load(Ordering::Acquire), 7);
assert_eq!(cohort.load(Ordering::Acquire), SEALED | 9);
assert_eq!(generation.load(Ordering::Acquire), 3);
}
});
}