Build a spinlock from AtomicBool and UnsafeCell

Build a small lock from two standard library types: AtomicBool, which records whether the lock is held, and UnsafeCell<T>, which holds the protected value.

pub struct SpinLock<T> { /* AtomicBool + UnsafeCell<T> */ }

impl<T> SpinLock<T> {
    pub fn new(value: T) -> Self;
    pub fn lock(&self) -> SpinLockGuard<'_, T>;
    pub fn into_inner(self) -> T;
}

pub fn spin_counter(increments: usize, workers: usize) -> usize

lock waits until the lock is free, claims it, and returns a guard: a value that gives access to the protected data and releases the lock when it is dropped. SpinLockGuard<'_, T> must implement Deref, DerefMut and Drop. into_inner consumes the lock and returns the value it protected.

The exercise contract

spin_counter(increments, workers) does the following:

1. Treat workers == 0 as 1.
2. Create a SpinLock<Vec<u64>> holding four zeros.
3. Start workers scoped threads (std::thread::scope). Worker w runs increments iterations; on iteration i it takes the lock and adds 1 to slot (w + i) % 4, then releases the lock.
4. After every worker has finished, take the vector out with into_inner and return the sum of the four slots.

With a correct lock the result is exactly increments * max(workers, 1). The tests use increments from 0 to 20,000 and workers from 0 to 8, so the result never comes close to overflowing. Each test has a 10 second time limit. The output is the single number, which the harness prints as JSON.

The protected value is a Vec rather than an integer, so your lock has to work for a type that is not Copy: it owns a heap allocation and has a destructor, and into_inner must move it out of the lock rather than copy it.

Why the lock contains its data

A shared reference &T normally promises that the value behind it will not change. UnsafeCell<T> is the language's exception: its get method turns a &UnsafeCell<T> into a raw pointer *mut T, and the compiler does not assume that data inside an UnsafeCell stays unchanged while shared references to it exist. The standard library documentation calls it the core primitive for interior mutability, and Cell, RefCell, Mutex, RwLock and the atomic types are all built on it. Turning that raw pointer into a &mut T is still unsafe: you must guarantee that no other reference to the same data is in use at the same time.

The lock provides that guarantee. Because the data lives inside the SpinLock, and the only safe way to reach it is through a guard, and the only way to get a guard is to call lock, safe code cannot touch the data without holding the lock. std::sync::Mutex<T> is designed the same way for the same reason. A lock can also be kept separate from the data it protects, as C-style APIs do, but then the compiler can no longer check that callers took the lock first.

The protocol

Lock, in lock:

while self
    .locked
    .compare_exchange_weak(false, true, Ordering::Acquire, Ordering::Relaxed)
    .is_err()
{
    spin_loop();
}

compare_exchange_weak(false, true, ...) checks that locked is false and, only if it is, sets it to true, as one indivisible (atomic) step. It returns Ok if it made the change and Err otherwise, so the loop keeps trying until this thread is the one that flipped the flag. std::hint::spin_loop() tells the processor that this is a busy-wait loop; on some processors it emits an instruction such as x86 pause, and on others it does nothing.

Unlock, in the guard's Drop:

self.lock.locked.store(false, Ordering::Release);

The orderings matter. A Release store followed by an Acquire operation on the same atomic that reads the stored value creates a happens-before edge: every write the previous holder made before unlocking is visible to the next holder after it locks. That is what makes it sound to give the next holder a &mut T to data another thread just modified. If you weaken either ordering to Relaxed, the flag itself still lets only one thread in at a time, but the data accesses are no longer ordered, which is a data race and undefined behavior. Such a program can still pass these tests, so a passing grade does not prove the orderings are right.

Use the weak form inside the loop. compare_exchange_weak is allowed to fail even when the value matched (a spurious failure). On processors that build compare-and-swap from a load-linked/store-conditional pair, such as older ARM cores, the strong compare_exchange needs an internal retry loop to rule that out; since you are already looping, the weak form avoids the extra loop. On processors with a single compare-and-swap instruction, the two usually compile to the same code. The failure ordering can be Relaxed because a failed attempt reads nothing the thread then relies on; it just tries again.

The starter has two problems, and only one is a compile error

First, the starter does not compile. thread::scope requires every spawned closure to be Send, and a closure that captures &SpinLock<Vec<u64>> is Send only if SpinLock<Vec<u64>> is Sync. It is not, because it contains an UnsafeCell, and UnsafeCell<T> never implements Sync. The compiler reports error E0277, saying that UnsafeCell<Vec<u64>> cannot be shared between threads safely.

The compiler cannot see that your lock serializes access, so you state it with an unsafe impl, which is a promise the compiler does not check:

unsafe impl<T: Send> Sync for SpinLock<T> {}

Work out why the bound is T: Send and not T: Sync. Sync on a type means several threads may hold & references to it at once; Send means a value may be moved to, or used exclusively from, another thread. Through the lock, only one thread at a time can reach the T, and it gets exclusive access, so the value is effectively handed from thread to thread rather than shared. That is what Send permits. std::sync::Mutex<T> uses the same bound. RwLock<T> needs T: Send + Sync, because several readers can hold &T at the same time.

Second, and the compiler will not report this one, the starter's lock is test-then-set:

while self.locked.load(Ordering::Acquire) { spin_loop(); }
self.locked.store(true, Ordering::Release);

Two threads can both load false before either stores true, and then both believe they hold the lock. Their unsynchronized accesses to the Vec are a data race, which is undefined behavior; in practice it usually shows up as lost increments and a total that is too small, but nothing guarantees any particular symptom, and a given run may even happen to produce the right answer. Checking and claiming must be one atomic operation, which is what compare_exchange provides.

Who may share the guard

The starter and solution also contain this line, which is already correct:

unsafe impl<T: Sync> Sync for SpinLockGuard<'_, T> {}

Without it, the compiler would derive the guard's Sync from its field &SpinLock<T>, which is Sync whenever T: Send. That is too weak. If two threads share a &SpinLockGuard, both can call deref and hold &T at the same time, which is only safe when T: Sync. With T = Cell<i32> (which is Send but not Sync), the derived version would let safe code call set on the same Cell from two threads at once. Writing the impl yourself replaces the derived one, and this bound matches the one std::sync::MutexGuard uses.

When a spinlock is a poor choice

A thread waiting on a spinlock does not sleep; it keeps a CPU core busy checking the flag. If there are more runnable threads than cores, the operating system may pause the thread that holds the lock while the waiters keep spinning, and none of the waiters can make progress until the holder runs again. That is one reason the inputs here are small.

Spinning can pay off when the critical section is a few instructions long and contention is low, because it avoids the cost of putting a thread to sleep and waking it. General-purpose locks usually combine the two approaches: spin briefly, then ask the operating system to put the thread to sleep. On Linux, for example, std::sync::Mutex spins a bounded number of times before sleeping, but that is an implementation detail, not a documented guarantee.

The timeline below shows contention: one thread waits while another holds the lock, and continues once it is released. In a spinlock that wait is spent spinning.

What Clippy does and does not catch

Clippy is not a substitute for reasoning about this code. On this toolchain, clippy::missing_spin_loop warns about an empty while loop whose condition calls load or compare_exchange_weak directly on an AtomicBool that is a local variable or a struct field, including self.locked inside a &self method. It did not warn when the loop read the atomic through a &AtomicBool or Arc<AtomicBool> variable, or when the compare_exchange_weak result was tested with .is_err(), which is the shape of the loop in this exercise. So write the spin_loop() hint yourself rather than counting on the lint to remind you.

clippy::mut_from_ref is an error by default. It rejects a safe method such as fn get(&self) -> &mut T, which would hand out a mutable reference from a shared one with nothing to stop two callers from doing it at once. The guard avoids that shape: deref_mut takes &mut self, so each guard can produce only one live &mut T at a time.