Struct Summary 

pub struct Summary { /* private fields */ }

Single-level summary tree for task work-stealing.

This tree tracks ONLY task signals - no yield or worker state. Each leaf represents a set of task signal words.

The Summary coordinates with SignalWakers to notify partition owners when their assigned leafs become active/inactive.

Thread Safety

This struct is designed for high-concurrency scenarios with the following guarantees:

• All operations use atomic primitives for lock-free operation
• Raw pointers are used for performance but are guaranteed safe by WorkerService lifetime
• Implements Send and Sync for cross-thread usage

Memory Layout

• leaf_words: Atomic bitfields tracking which signals have pending tasks
• task_reservations: Atomic bitfields for task slot reservations within each signal
• Round-robin cursors distribute load evenly across leaves and signals
• Partition mapping enables work-stealing between worker threads

Implementations

impl Summary

pub fn new( leaf_count: usize, signals_per_leaf: usize, wakers: &[Arc<WorkerWaker>], worker_count: &Arc<AtomicUsize>, ) -> Self

Creates a new Summary with the specified dimensions.

Arguments

• leaf_count - Number of leaf nodes (typically matches worker partition count)
• signals_per_leaf - Number of task signal words per leaf (typically tasks_per_leaf / 64)
• wakers - Slice of SignalWakers for partition owner notification
• worker_count - Reference to WorkerService’s worker_count atomic (single source of truth)

Safety

The wakers slice and worker_count reference must remain valid for the lifetime of this Summary. This is guaranteed when Summary is owned by WorkerService which also owns the wakers and worker_count.

Memory Allocation

Allocates leaf_count * signals_per_leaf * 8 bytes for reservations plus overhead for leaf words and cursors.

pub fn get_worker_count(&self) -> usize

Get the current worker count from WorkerService. Reads directly from the single source of truth.

Atomic Semantics

Uses Relaxed ordering since this is only used for informational purposes and doesn’t require synchronization with other memory operations.

pub fn mark_signal_active(&self, leaf_idx: usize, signal_idx: usize) -> bool

Sets the summary bit for a task signal.

Returns

true if the leaf was empty before setting this signal (useful for work-stealing decisions)

Atomic Semantics

Uses fetch_or with AcqRel ordering to atomically set bits and get previous state. Notifies the partition owner if new bits were added.

pub fn mark_signal_inactive(&self, leaf_idx: usize, signal_idx: usize) -> bool

Clears the summary bit for a task signal.

Returns

true if bits were successfully cleared, false if indices are invalid or bits were already cleared

Atomic Semantics

Uses fetch_and with AcqRel ordering to atomically clear bits and get previous state. Notifies the partition owner if the leaf became empty.

pub fn reserve_task_in_leaf( &self, leaf_idx: usize, signal_idx: usize, ) -> Option<u8>

Attempts to reserve a task slot within (leaf_idx, signal_idx).

Returns

The bit index (0-63) of the reserved slot, or None if all slots are taken

Atomic Semantics

Implements a lock-free reservation system using atomic CAS (Compare-And-Swap) loops.

• Uses Acquire ordering for loads to see completed reservations
• Uses AcqRel for successful CAS to make reservation visible to others
• Uses Acquire for failed CAS to see the updated state

Algorithm

1. Load current reservation bitmap
2. Use a per-signal round-robin cursor to pick a starting bit
3. Rotate the bitmap so trailing_zeros finds the next free slot after the cursor
4. Attempt to atomically set that bit with CAS
5. If CAS fails (another thread reserved it), retry with updated value
6. Continue until success or no free bits remain

pub fn release_task_in_leaf( &self, leaf_idx: usize, signal_idx: usize, bit: usize, )

Clears a previously reserved task slot.

Atomic Semantics

Uses fetch_and with SeqCst ordering to atomically clear the reservation bit. This ensures the release is visible to other threads attempting reservations.

pub fn reserve_task(&self) -> Option<(usize, usize, u8)>

Convenience function: reserve the first available task slot across the arena.

Atomic Semantics

Uses round-robin cursors with SeqCst ordering to ensure proper synchronization between threads when selecting partitions, leaves, and signals. The actual reservation uses the CAS loop in reserve_task_in_leaf which provides proper synchronization.

pub fn mark_signal_inactive_if_empty( &self, leaf_idx: usize, signal_idx: usize, signal: &AtomicU64, )

Clears the summary bit when the corresponding task signal becomes empty.

⚠️ CORRECTNESS ISSUE - TOCTOU Race Condition

This function has an unfixed race condition between checking and clearing:

Race scenario:

1. Thread A: signal.load() sees 0
2. Thread B: Enqueues task, signal becomes 1, calls mark_signal_active()
3. Thread A: Calls mark_signal_inactive(), clearing the bit Thread B just set
4. Result: signal has tasks but summary bit is cleared → lost work notification

Why this is problematic:

• Work-stealing threads rely on summary bits to find available work
• Clearing the bit while tasks exist makes those tasks invisible to stealers
• The task enqueue won’t re-set the bit because it already set it in step 2

Proper fix requires one of:

1. Caller-side synchronization ensuring signal cannot be modified during this call
2. API change: pass mutable/exclusive access to signal to perform atomic check-and-clear
3. Accepting false negatives: allow summary bit to remain set even when signal is empty (wastes stealer cycles but is always safe)

Current mitigation: None - callers must ensure signal stability externally.

Atomic Semantics

Uses Acquire ordering to ensure visibility of all prior writes to the signal.

pub fn leaf_count(&self) -> usize

pub fn signals_per_leaf(&self) -> usize

pub fn compute_partition_owner( &self, leaf_idx: usize, worker_count: usize, ) -> usize

Compute which worker owns a given leaf based on partition assignments.

This is the inverse of Worker::compute_partition(). Given a leaf index, it determines which worker is responsible for processing tasks in that leaf.

Partition Algorithm

Uses a balanced distribution where:

• First leaf_count % worker_count workers get (leaf_count / worker_count) + 1 leaves
• Remaining workers get leaf_count / worker_count leaves This ensures leaves are distributed as evenly as possible.

Arguments

• leaf_idx - The global leaf index (0..leaf_count)
• worker_count - Total number of active workers

Returns

Worker ID (0..worker_count) that owns this leaf

Example

let owner_id = summary_tree.compute_partition_owner(leaf_idx, worker_count);
let owner_waker = &service.wakers[owner_id];
owner_waker.mark_partition_leaf_active(local_idx);

pub fn partition_start_for_worker( &self, worker_id: usize, worker_count: usize, ) -> usize

Compute the partition start index for a given worker.

Arguments

• worker_id - Worker ID (0..worker_count)
• worker_count - Total number of active workers

Returns

First leaf index in this worker’s partition

pub fn partition_end_for_worker( &self, worker_id: usize, worker_count: usize, ) -> usize

Compute the partition end index for a given worker.

Arguments

• worker_id - Worker ID (0..worker_count)
• worker_count - Total number of active workers

Returns

One past the last leaf index in this worker’s partition (exclusive)

pub fn global_to_local_leaf_idx( &self, leaf_idx: usize, worker_id: usize, worker_count: usize, ) -> Option<usize>

Convert a global leaf index to a local index within a worker’s partition.

Arguments

• leaf_idx - Global leaf index
• worker_id - Worker ID
• worker_count - Total number of workers

Returns

Local leaf index (0..partition_size) for use with SignalWaker partition bitmap, or None if the leaf is not in this worker’s partition

Trait Implementations

impl Send for Summary

impl Sync for Summary