use core::cell::Cell;
use core::ptr;
use core::sync::atomic::{AtomicBool, AtomicU32, Ordering};
use std::sync::{Arc, OnceLock};
use std::thread::{self, JoinHandle};
use crate::sched::flynnel_ring::{FlynnelRing, PopResult, PushResult};
use crate::sched::injector::{Injector, InjectorSteal as Steal};
use crate::sched::adaptive_worker::{
AdaptiveStash, AdaptiveStealer, AdaptiveSteal2, AdaptiveWorker,
new_adaptive, steal_via_stash,
};
use crate::sched::deque_tier::{DequeTier, N_TIERS, peer_distance};
use crate::sched::job::JobRef;
use crate::sched::k_gating::KGating;
use crate::sched::sleep::Parker;
const MAILBOX_CAPACITY: usize = 16;
pub(crate) struct WorkerCtx {
pub(crate) workers: [AdaptiveWorker; N_TIERS],
#[allow(dead_code)]
pub(crate) index: usize,
pub(crate) burst_pushed: Cell<u32>,
pub(crate) stealers: Vec<[AdaptiveStealer; N_TIERS]>,
pub(crate) steal_stash: core::cell::UnsafeCell<AdaptiveStash>,
pub(crate) ccx_size: usize,
pub(crate) mailbox: Arc<FlynnelRing<JobRef>>,
pub(crate) peer_mailboxes: Vec<Arc<FlynnelRing<JobRef>>>,
pub(crate) injector: Arc<Injector<JobRef>>,
pub(crate) rng: Cell<u64>,
pub(crate) parkers: Arc<Vec<Arc<OnceLock<Arc<Parker>>>>>,
pub(crate) wake_rotor: Cell<usize>,
pub(crate) stats: Arc<WorkerStats>,
pub(crate) peer_stats: Vec<Arc<WorkerStats>>,
pub(crate) sleep: Arc<crate::sched::jec_sleep::Sleep>,
pub(crate) last_victim: Cell<usize>,
pub(crate) is_external_slot: bool,
pub(crate) join_parker: Box<Parker>,
}
#[derive(Debug, Default)]
#[repr(align(128))]
pub struct WorkerStats {
pub local_pops: core::sync::atomic::AtomicU64,
pub peer_steal_hits: core::sync::atomic::AtomicU64,
pub peer_steal_misses: core::sync::atomic::AtomicU64,
pub times_stolen_from: core::sync::atomic::AtomicU64,
pub single_pushes: core::sync::atomic::AtomicU64,
pub burst_pushes: core::sync::atomic::AtomicU64,
pub push_refusals: core::sync::atomic::AtomicU64,
}
impl WorkerStats {
pub fn burst_ratio(&self) -> f32 {
use core::sync::atomic::Ordering;
let b = self.burst_pushes.load(Ordering::Relaxed) as f32;
let s = self.single_pushes.load(Ordering::Relaxed) as f32;
let total = b + s;
if total == 0.0 {
0.5
} else {
b / total
}
}
}
impl WorkerCtx {
pub(crate) fn push_to_mailbox(
&self,
target_idx: usize,
job: JobRef,
) -> Result<(), JobRef> {
if target_idx >= self.peer_mailboxes.len() {
return Err(job);
}
match self.peer_mailboxes[target_idx].push(job) {
PushResult::Ok => {}
PushResult::Full(j) => return Err(j),
}
MAILBOX_EVER_USED.store(true, Ordering::Release);
self.sleep.wake_worker(target_idx);
Ok(())
}
#[inline]
pub(crate) fn push_burst(&self, job: JobRef) {
self.push_tier_burst(job, DequeTier::default());
}
#[inline]
pub(crate) fn push_tier_burst(&self, job: JobRef, tier: DequeTier) {
self.workers[tier.idx()].push_burst(job);
self.burst_pushed.set(self.burst_pushed.get().saturating_add(1));
self.stats
.burst_pushes
.fetch_add(1, core::sync::atomic::Ordering::Relaxed);
}
#[inline]
pub(crate) fn flush_all(&self) {
for tier in DequeTier::all() {
self.workers[tier.idx()].flush();
}
let n = self.burst_pushed.get();
self.burst_pushed.set(0);
if n > 0 && DISPATCH_USE_JEC_WAKE.with(|c| c.get()) {
self.sleep.new_internal_jobs(n, true);
}
}
#[inline]
pub(crate) fn try_push(&self, job: JobRef) -> Result<(), JobRef> {
self.try_push_tier(job, DequeTier::default())
}
#[inline]
pub(crate) fn try_push_tier(&self, job: JobRef, tier: DequeTier) -> Result<(), JobRef> {
let any_was_empty = self.workers.iter().all(|w| w.is_empty());
match self.workers[tier.idx()].try_push(job) {
Ok(()) => {}
Err(job) => {
self.stats
.push_refusals
.fetch_add(1, core::sync::atomic::Ordering::Relaxed);
return Err(job);
}
}
self.stats
.single_pushes
.fetch_add(1, core::sync::atomic::Ordering::Relaxed);
if DISPATCH_USE_JEC_WAKE.with(|c| c.get()) {
self.sleep.new_internal_jobs(1, any_was_empty);
}
Ok(())
}
#[inline]
#[allow(dead_code)]
fn wake_all_peers(&self) {
let n = self.parkers.len();
if n <= 1 {
return;
}
for (i, slot) in self.parkers.iter().enumerate() {
if i == self.index {
continue;
}
if let Some(p) = slot.get() {
p.unpark();
}
}
}
#[inline]
#[allow(dead_code)]
fn wake_one_peer(&self) {
let n = self.parkers.len();
if n <= 1 {
return;
}
let mut r = self.wake_rotor.get();
r = (r + 1) % n;
if r == self.index {
r = (r + 1) % n;
}
self.wake_rotor.set(r);
if let Some(p) = self.parkers[r].get() {
p.unpark();
}
}
pub(crate) fn find_work(&self) -> Option<JobRef> {
if let Some(job) = self.workers[DequeTier::Public.idx()].pop() {
return Some(job);
}
{
let stash = unsafe { &mut *self.steal_stash.get() };
if let Some(job) = stash.drain_one() {
return Some(job);
}
}
if MAILBOX_EVER_USED.load(Ordering::Acquire)
&& let PopResult::Ok(job) = self.mailbox.pop()
{
return Some(job);
}
for tier in [DequeTier::SmtLocal, DequeTier::IntraCcx, DequeTier::CrossCcx] {
if let Some(job) = self.workers[tier.idx()].pop() {
return Some(job);
}
}
if let Steal::Success(job) = self.injector.steal() {
crate::sched::prefetch::prefetch_into_l2_inline(unsafe {
core::slice::from_raw_parts(job.data_ptr() as *const u8, 64)
});
return Some(job);
}
let n = self.stealers.len();
if n < 2 {
return None;
}
let n_workers = self.sleep.worker_count();
let mut claimed = self.sleep.claimed_slots();
while claimed != 0 {
let slot = n_workers + claimed.trailing_zeros() as usize;
claimed &= claimed - 1;
if slot < n
&& slot != self.index
&& let Some(job) = self.steal_from_peer_tiered(slot)
{
return Some(job);
}
}
let last = self.last_victim.get();
if last != usize::MAX
&& last != self.index
&& last < n
&& let Some(job) = self.steal_from_peer_tiered(last)
{
return Some(job);
}
if n_workers < 2 {
return None;
}
let mut x = self.rng.get();
if x == 0 {
x = 0x9E37_79B9_7F4A_7C15;
}
x ^= x << 13;
x ^= x >> 7;
x ^= x << 17;
self.rng.set(x);
let mut victim = (x as usize) % n_workers;
if victim == self.index {
victim = (victim + 1) % n_workers;
}
self.steal_from_peer_tiered(victim)
}
#[inline]
pub(crate) fn prefetch_last_victim_stealer(&self) {
let last = self.last_victim.get();
if last == usize::MAX || last >= self.stealers.len() {
return;
}
let stealer = &self.stealers[last][DequeTier::SmtLocal.idx()];
let addr = stealer as *const _ as *const u8;
#[cfg(target_arch = "x86_64")]
{
unsafe {
std::arch::x86_64::_mm_prefetch(
addr as *const i8,
std::arch::x86_64::_MM_HINT_T0,
);
}
}
#[cfg(not(target_arch = "x86_64"))]
{
std::hint::black_box(addr);
}
}
fn steal_from_peer_tiered(&self, peer: usize) -> Option<JobRef> {
if peer == usize::MAX || peer == self.index || peer >= self.stealers.len() {
return None;
}
let stash = unsafe { &mut *self.steal_stash.get() };
let distance = peer_distance(self.index, peer, self.ccx_size);
for tier_idx in distance.idx()..N_TIERS {
match steal_via_stash(&self.stealers[peer][tier_idx], stash) {
AdaptiveSteal2::Success(job) => {
crate::sched::prefetch::prefetch_into_l2_inline(unsafe {
core::slice::from_raw_parts(job.data_ptr() as *const u8, 64)
});
if peer < self.peer_stats.len() {
self.peer_stats[peer]
.times_stolen_from
.fetch_add(1, core::sync::atomic::Ordering::Relaxed);
}
self.last_victim.set(peer);
self.prefetch_last_victim_stealer();
return Some(job);
}
AdaptiveSteal2::Empty | AdaptiveSteal2::Retry => continue,
}
}
None
}
}
thread_local! {
static WORKER_CTX: Cell<*const WorkerCtx> = const { Cell::new(ptr::null()) };
}
#[inline]
pub(crate) fn current_worker_ctx() -> *const WorkerCtx {
WORKER_CTX.with(|c| c.get())
}
unsafe fn set_current_worker_ctx(ctx: *const WorkerCtx) {
WORKER_CTX.with(|c| {
debug_assert!(c.get().is_null(),
"worker ctx already set on this thread; double-registration");
c.set(ctx);
});
}
fn clear_current_worker_ctx() {
WORKER_CTX.with(|c| c.set(ptr::null()));
}
fn pin_disabled_env() -> bool {
static CACHE: std::sync::OnceLock<bool> = std::sync::OnceLock::new();
*CACHE.get_or_init(|| {
match std::env::var("FLYNNEL_SCHED_PIN") {
Ok(v) => {
let v = v.to_ascii_lowercase();
if v == "on" || v == "1" || v == "true" {
false } else {
true }
}
Err(_) => true,
}
})
}
pub(crate) const LOCAL_SPIN_ROUNDS: u32 = 64;
const PROBE_FULL_CUTOFF: usize = 8;
const PROBE_LARGE: usize = 4;
pub struct LocalArena {
injector: Arc<Injector<JobRef>>,
stealers: Vec<[AdaptiveStealer; N_TIERS]>,
parkers: Vec<Arc<OnceLock<Arc<Parker>>>>,
stats: Vec<Arc<WorkerStats>>,
workers: Vec<Option<JoinHandle<()>>>,
primary_count: usize,
smt_requests: Arc<AtomicU32>,
shutdown_flag: Arc<AtomicBool>,
pub(crate) sleep: Arc<crate::sched::jec_sleep::Sleep>,
pub(crate) k_gating_tags: Vec<[Arc<core::sync::atomic::AtomicU32>; N_TIERS]>,
mailboxes: Vec<Arc<FlynnelRing<JobRef>>>,
pub(crate) external_slots: Vec<Arc<ExternalSlot>>,
}
thread_local! {
pub(crate) static DISPATCH_USE_JEC_WAKE: core::cell::Cell<bool>
= const { core::cell::Cell::new(true) };
}
pub(crate) static MAILBOX_EVER_USED: AtomicBool = AtomicBool::new(false);
pub(crate) struct DispatchScope {
prev: bool,
}
impl DispatchScope {
#[inline]
#[allow(dead_code)]
pub(crate) fn new(use_jec_wake: bool) -> Self {
let prev = DISPATCH_USE_JEC_WAKE.with(|c| {
let p = c.get();
c.set(use_jec_wake);
p
});
Self { prev }
}
#[inline]
pub(crate) fn new_if_change(use_jec_wake: bool) -> Option<Self> {
DISPATCH_USE_JEC_WAKE.with(|c| {
let prev = c.get();
if prev == use_jec_wake {
None
} else {
c.set(use_jec_wake);
Some(Self { prev })
}
})
}
}
impl Drop for DispatchScope {
#[inline]
fn drop(&mut self) {
DISPATCH_USE_JEC_WAKE.with(|c| c.set(self.prev));
}
}
impl std::fmt::Debug for LocalArena {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.debug_struct("LocalArena")
.field("n_workers", &self.workers.len())
.field("injector_len", &self.injector.len())
.finish()
}
}
impl LocalArena {
pub fn new(n_workers: usize) -> Arc<Self> {
let core_ids: Option<Vec<core_affinity::CoreId>> = if pin_disabled_env() {
None
} else {
core_affinity::get_core_ids()
};
Self::with_cpu_set(n_workers, core_ids)
}
pub fn with_cpu_set(
n_workers: usize,
cpu_set: Option<Vec<core_affinity::CoreId>>,
) -> Arc<Self> {
Self::with_smt_extension(n_workers, 0, cpu_set)
}
pub fn with_smt_extension(
primary_count: usize,
smt_extension: usize,
cpu_set: Option<Vec<core_affinity::CoreId>>,
) -> Arc<Self> {
let primary = primary_count.max(1);
let smt = smt_extension;
let n = primary + smt;
let injector: Arc<Injector<JobRef>> = Arc::new(Injector::new());
let initial_gating = KGating::Auto;
let mut workers_per_idx: Vec<[Option<AdaptiveWorker>; N_TIERS]> =
(0..n).map(|_| [const { None }; N_TIERS]).collect();
let mut stealers: Vec<[AdaptiveStealer; N_TIERS]> = Vec::with_capacity(n);
let mut k_gating_tags: Vec<[Arc<core::sync::atomic::AtomicU32>; N_TIERS]>
= Vec::with_capacity(n);
for slot in workers_per_idx.iter_mut() {
let (w0, s0) = new_adaptive(ADAPTIVE_SLOT_CAPACITY, initial_gating);
let (w1, s1) = new_adaptive(ADAPTIVE_SLOT_CAPACITY, initial_gating);
let (w2, s2) = new_adaptive(ADAPTIVE_SLOT_CAPACITY, initial_gating);
let (w3, s3) = new_adaptive(ADAPTIVE_SLOT_CAPACITY, initial_gating);
let tags = [w0.active_tag(), w1.active_tag(), w2.active_tag(), w3.active_tag()];
slot[0] = Some(w0);
slot[1] = Some(w1);
slot[2] = Some(w2);
slot[3] = Some(w3);
stealers.push([s0, s1, s2, s3]);
k_gating_tags.push(tags);
}
let mut slot_workers_per_idx: Vec<[Option<AdaptiveWorker>; N_TIERS]> =
(0..EXTERNAL_SLOT_COUNT)
.map(|_| [const { None }; N_TIERS]).collect();
for slot in slot_workers_per_idx.iter_mut() {
let (w0, s0) = new_adaptive(EXTERNAL_SLOT_DEQUE_CAPACITY, initial_gating);
let (w1, s1) = new_adaptive(EXTERNAL_SLOT_DEQUE_CAPACITY, initial_gating);
let (w2, s2) = new_adaptive(EXTERNAL_SLOT_DEQUE_CAPACITY, initial_gating);
let (w3, s3) = new_adaptive(EXTERNAL_SLOT_DEQUE_CAPACITY, initial_gating);
let tags = [w0.active_tag(), w1.active_tag(), w2.active_tag(), w3.active_tag()];
slot[0] = Some(w0);
slot[1] = Some(w1);
slot[2] = Some(w2);
slot[3] = Some(w3);
stealers.push([s0, s1, s2, s3]);
k_gating_tags.push(tags);
}
let total_n = n + EXTERNAL_SLOT_COUNT;
let parkers_vec: Vec<Arc<OnceLock<Arc<Parker>>>> =
(0..total_n).map(|_| Arc::new(OnceLock::new())).collect();
let parkers_handle: Arc<Vec<Arc<OnceLock<Arc<Parker>>>>> =
Arc::new(parkers_vec.clone());
let stats_vec: Vec<Arc<WorkerStats>> =
(0..total_n).map(|_| Arc::new(WorkerStats::default())).collect();
let core_ids = cpu_set;
let shutdown_flag = Arc::new(AtomicBool::new(false));
let smt_requests: Arc<AtomicU32> = Arc::new(AtomicU32::new(0));
let sleep_arc = Arc::new(crate::sched::jec_sleep::Sleep::new(n));
let ccx_size_for_workers = {
let topo = crate::numa_topology();
1usize << topo.cluster_size_log2 as usize
};
let mailboxes: Vec<Arc<FlynnelRing<JobRef>>> =
(0..total_n).map(|_| Arc::new(FlynnelRing::new(MAILBOX_CAPACITY))).collect();
let mut handles: Vec<Option<JoinHandle<()>>> = Vec::with_capacity(n);
for idx in 0..n {
let my_tier_deques: [AdaptiveWorker; N_TIERS] = {
let slot = &mut workers_per_idx[idx];
[
slot[0].take().expect("tier 0 deque present"),
slot[1].take().expect("tier 1 deque present"),
slot[2].take().expect("tier 2 deque present"),
slot[3].take().expect("tier 3 deque present"),
]
};
let peer_stealers = stealers.clone();
let inj = Arc::clone(&injector);
let park_slot = Arc::clone(&parkers_vec[idx]);
let shutdown = Arc::clone(&shutdown_flag);
let parkers_for_worker = Arc::clone(&parkers_handle);
let stats_for_worker = Arc::clone(&stats_vec[idx]);
let my_mailbox = Arc::clone(&mailboxes[idx]);
let peer_mailboxes_for_worker: Vec<Arc<FlynnelRing<JobRef>>> =
mailboxes.iter().map(Arc::clone).collect();
let peer_stats_for_worker: Vec<Arc<WorkerStats>> =
stats_vec.iter().map(Arc::clone).collect();
let smt_req_for_worker = Arc::clone(&smt_requests);
let sleep_for_worker = Arc::clone(&sleep_arc);
let is_primary = idx < primary;
let assigned_core = core_ids.as_ref().map(|ids| ids[idx % ids.len()]);
let h = thread::Builder::new()
.name(format!("flynnel-sched-{idx}"))
.stack_size(8 * 1024 * 1024)
.spawn(move || {
if shutdown.load(Ordering::Acquire) {
return;
}
if let Some(core) = assigned_core {
let _ = core_affinity::set_for_current(core);
}
let parker = Arc::new(Parker::new(LOCAL_SPIN_ROUNDS));
park_slot
.set(Arc::clone(&parker))
.expect("park_slot must only be set once per worker");
if shutdown.load(Ordering::Acquire) {
return;
}
worker_loop(
idx,
my_tier_deques,
peer_stealers,
ccx_size_for_workers,
my_mailbox,
peer_mailboxes_for_worker,
inj,
parker,
shutdown,
parkers_for_worker,
stats_for_worker,
peer_stats_for_worker,
sleep_for_worker,
is_primary,
smt_req_for_worker,
);
})
.expect("worker thread spawn must succeed");
handles.push(Some(h));
}
let mut external_slots: Vec<Arc<ExternalSlot>> =
Vec::with_capacity(EXTERNAL_SLOT_COUNT);
for (slot_id, slot_entry) in slot_workers_per_idx.iter_mut().enumerate() {
let arena_index = n + slot_id;
let deques: [AdaptiveWorker; N_TIERS] = [
slot_entry[0].take().expect("slot tier 0 present"),
slot_entry[1].take().expect("slot tier 1 present"),
slot_entry[2].take().expect("slot tier 2 present"),
slot_entry[3].take().expect("slot tier 3 present"),
];
let slot_mailbox = Arc::clone(&mailboxes[arena_index]);
let slot_peer_mailboxes: Vec<Arc<FlynnelRing<JobRef>>> =
mailboxes.iter().map(Arc::clone).collect();
let slot_stats = Arc::clone(&stats_vec[arena_index]);
let slot_peer_stats: Vec<Arc<WorkerStats>> =
stats_vec.iter().map(Arc::clone).collect();
let slot_stealers = stealers.clone();
let ctx = WorkerCtx {
workers: deques,
index: arena_index,
burst_pushed: Cell::new(0),
stealers: slot_stealers,
steal_stash: core::cell::UnsafeCell::new(AdaptiveStash::empty()),
ccx_size: ccx_size_for_workers,
mailbox: slot_mailbox,
peer_mailboxes: slot_peer_mailboxes,
injector: Arc::clone(&injector),
rng: Cell::new(0x9E37_79B9_7F4A_7C15u64
.wrapping_mul(arena_index as u64 + 1)),
parkers: Arc::clone(&parkers_handle),
wake_rotor: Cell::new(arena_index),
stats: slot_stats,
peer_stats: slot_peer_stats,
sleep: Arc::clone(&sleep_arc),
last_victim: Cell::new(usize::MAX),
is_external_slot: true,
join_parker: Box::new(Parker::with_strategy(
0,
crate::sched::sleep::WaitStrategy::StdPark,
)),
};
external_slots.push(Arc::new(ExternalSlot {
claimed: AtomicBool::new(false),
ctx: core::cell::UnsafeCell::new(ctx),
index_in_arena: arena_index,
}));
}
Arc::new(Self {
injector,
stealers,
parkers: parkers_vec,
stats: stats_vec,
workers: handles,
primary_count: primary,
smt_requests,
shutdown_flag,
sleep: sleep_arc,
k_gating_tags,
mailboxes,
external_slots,
})
}
pub fn mailbox_census(&self) -> Vec<usize> {
self.mailboxes
.iter()
.enumerate()
.filter(|(_, m)| !m.is_empty())
.map(|(i, _)| i)
.collect()
}
pub fn parked_census(&self) -> Vec<usize> {
self.sleep
.debug_state()
.blocked
.iter()
.enumerate()
.filter(|(_, parked)| **parked)
.map(|(i, _)| i)
.collect()
}
pub(crate) fn try_claim_external_slot(self: &Arc<Self>)
-> Option<ExternalSlotGuard>
{
for slot in self.external_slots.iter() {
if slot.is_claimed() {
continue;
}
if slot.claimed
.compare_exchange(false, true, Ordering::AcqRel, Ordering::Relaxed)
.is_ok()
{
debug_assert_eq!(
slot.index(),
unsafe { (*slot.ctx.get()).index },
"slot index_in_arena must match ctx.index",
);
let prev = current_worker_ctx();
let ctx_ptr: *const WorkerCtx = slot.ctx.get();
unsafe {
let ctx = &*ctx_ptr;
ctx.rng.set(0x9E37_79B9_7F4A_7C15u64
.wrapping_mul(slot.index_in_arena as u64 + 1));
ctx.last_victim.set(usize::MAX);
ctx.burst_pushed.set(0);
ctx.wake_rotor.set(slot.index_in_arena);
}
clear_current_worker_ctx();
unsafe { set_current_worker_ctx(ctx_ptr) };
self.sleep
.note_slot_claimed(slot.index_in_arena - self.sleep.worker_count());
return Some(ExternalSlotGuard {
slot: Arc::clone(slot),
prev_ctx: prev,
});
}
}
None
}
pub fn migrate_all_workers_k_gating(&self, gating: KGating) {
use core::sync::atomic::Ordering;
let target = match gating.resolved() {
KGating::CounterOnly => 1u32,
_ => 0u32, };
for tier_arr in &self.k_gating_tags {
for tag in tier_arr.iter() {
tag.store(target, Ordering::Release);
}
}
}
pub fn global_burst_ratio(&self) -> f32 {
use core::sync::atomic::Ordering;
let mut bursts: u64 = 0;
let mut singles: u64 = 0;
for w in &self.stats {
bursts = bursts.saturating_add(w.burst_pushes.load(Ordering::Relaxed));
singles = singles.saturating_add(w.single_pushes.load(Ordering::Relaxed));
}
let total = bursts + singles;
if total == 0 {
0.5
} else {
(bursts as f32) / (total as f32)
}
}
pub fn worker_stats(&self) -> &[Arc<WorkerStats>] {
&self.stats
}
pub fn primary_count(&self) -> usize {
self.primary_count
}
pub fn smt_extension_count(&self) -> usize {
self.workers.len().saturating_sub(self.primary_count)
}
pub fn acquire_smt(self: &Arc<Self>) -> SmtGuard {
let prev = self.smt_requests.fetch_add(1, Ordering::AcqRel);
if prev == 0 {
for slot in self.parkers.iter().skip(self.primary_count) {
if let Some(p) = slot.get() {
p.unpark();
}
}
}
SmtGuard {
arena: Arc::clone(self),
}
}
pub fn debug_snapshot(&self) -> String {
use core::sync::atomic::Ordering::Relaxed;
let n = self.workers.len();
let sleep = self.sleep.debug_state();
let occupancy = |idx: usize| -> String {
self.stealers[idx]
.iter()
.map(|st| {
if st.is_empty() {
".".to_string()
} else {
format!("{}", st.khl_len().max(1))
}
})
.collect::<Vec<_>>()
.join(",")
};
let mut s = format!(
"workers={n} primary={} smt_requests={} injector_empty={} \
sleeping={} inactive={} jec={}\n",
self.primary_count,
self.smt_requests.load(Ordering::Acquire),
self.injector.is_empty(),
sleep.sleeping,
sleep.inactive,
sleep.jec,
);
for i in 0..n {
let st = &self.stats[i];
let state = match sleep.blocked.get(i) {
Some(true) => "blocked",
Some(false) => "awake",
None => "unreported",
};
s.push_str(&format!(
" w{i:02} deques[{}] {state} pops={} steals={} stolen_from={} refused={}\n",
occupancy(i),
st.local_pops.load(Relaxed),
st.peer_steal_hits.load(Relaxed),
st.times_stolen_from.load(Relaxed),
st.push_refusals.load(Relaxed),
));
}
for (k, slot) in self.external_slots.iter().enumerate() {
let occ = occupancy(n + k);
if slot.is_claimed() || occ.chars().any(|c| c.is_ascii_digit()) {
s.push_str(&format!(
" slot{k:02} claimed={} deques[{occ}]\n",
slot.is_claimed()
));
}
}
s
}
}
pub(crate) const EXTERNAL_SLOT_COUNT: usize = 32;
const _: () = assert!(EXTERNAL_SLOT_COUNT <= 64);
const EXTERNAL_SLOT_DEQUE_CAPACITY: usize = 64;
pub(crate) const ADAPTIVE_SLOT_CAPACITY: usize = 256;
pub(crate) const JOBS_PER_SLOT: usize = 3;
pub(crate) struct ExternalSlot {
claimed: AtomicBool,
ctx: core::cell::UnsafeCell<WorkerCtx>,
index_in_arena: usize,
}
unsafe impl Sync for ExternalSlot {}
impl ExternalSlot {
#[inline]
pub(crate) fn is_claimed(&self) -> bool {
self.claimed.load(Ordering::Acquire)
}
#[inline]
pub(crate) fn index(&self) -> usize {
self.index_in_arena
}
}
pub(crate) struct ExternalSlotGuard {
slot: Arc<ExternalSlot>,
prev_ctx: *const WorkerCtx,
}
impl ExternalSlotGuard {
#[inline]
pub(crate) fn ctx_ref(&self) -> &WorkerCtx {
unsafe { &*self.slot.ctx.get() }
}
}
impl Drop for ExternalSlotGuard {
fn drop(&mut self) {
clear_current_worker_ctx();
if !self.prev_ctx.is_null() {
unsafe { set_current_worker_ctx(self.prev_ctx) };
}
let sleep = &self.ctx_ref().sleep;
sleep.note_slot_released(self.slot.index_in_arena - sleep.worker_count());
self.slot.claimed.store(false, Ordering::Release);
}
}
#[derive(Debug)]
pub struct SmtGuard {
arena: Arc<LocalArena>,
}
impl Drop for SmtGuard {
fn drop(&mut self) {
self.arena.smt_requests.fetch_sub(1, Ordering::AcqRel);
}
}
impl LocalArena {
pub(crate) unsafe fn submit(&self, job: JobRef) {
let was_empty = self.injector.is_empty();
self.injector.push(job);
self.sleep.new_internal_jobs(1, was_empty);
}
pub fn try_run_one(&self, rng_state: &mut u64) -> bool {
if let Steal::Success(job) = self.injector.steal() {
crate::sched::prefetch::prefetch_into_l2_inline(unsafe {
core::slice::from_raw_parts(job.data_ptr() as *const u8, 64)
});
unsafe { job.execute() };
return true;
}
let n = self.stealers.len();
if n == 0 {
return false;
}
let mut x = *rng_state;
if x == 0 {
x = 0x9E37_79B9_7F4A_7C15;
}
x ^= x << 13;
x ^= x >> 7;
x ^= x << 17;
*rng_state = x;
let idx = (x as usize) % n;
thread_local! {
static EXTERNAL_STEAL_STASH: core::cell::RefCell<AdaptiveStash>
= core::cell::RefCell::new(AdaptiveStash::empty());
}
let drained = EXTERNAL_STEAL_STASH.with(|s| s.borrow_mut().drain_one());
if let Some(job) = drained {
crate::sched::prefetch::prefetch_into_l2_inline(unsafe {
core::slice::from_raw_parts(job.data_ptr() as *const u8, 64)
});
unsafe { job.execute() };
return true;
}
let steal_result = EXTERNAL_STEAL_STASH.with(|s| {
steal_via_stash(&self.stealers[idx][DequeTier::Public.idx()], &mut s.borrow_mut())
});
if let AdaptiveSteal2::Success(job) = steal_result {
crate::sched::prefetch::prefetch_into_l2_inline(unsafe {
core::slice::from_raw_parts(job.data_ptr() as *const u8, 64)
});
unsafe { job.execute() };
return true;
}
false
}
pub fn worker_count(&self) -> usize {
self.workers.len()
}
#[cfg(test)]
#[allow(dead_code)]
pub(crate) fn injector_len(&self) -> usize {
self.injector.len()
}
#[allow(dead_code)]
pub(crate) fn injector_view(&self) -> &Injector<JobRef> {
&self.injector
}
pub fn wait_injector_drained(&self) {
while !self.injector.is_empty() {
thread::yield_now();
}
}
}
impl Drop for LocalArena {
fn drop(&mut self) {
self.shutdown_flag.store(true, Ordering::Release);
for p in &self.parkers {
if let Some(parker) = p.get() {
parker.shutdown();
}
}
self.sleep.wake_all_for_shutdown();
for slot in &mut self.workers {
if let Some(h) = slot.take()
&& h.join().is_err()
{
notice!("flynnel: worker thread panicked before shutdown join");
}
}
}
}
#[allow(clippy::too_many_arguments)]
fn worker_loop(
idx: usize,
my_tier_deques: [AdaptiveWorker; N_TIERS],
stealers: Vec<[AdaptiveStealer; N_TIERS]>,
ccx_size: usize,
mailbox: Arc<FlynnelRing<JobRef>>,
peer_mailboxes: Vec<Arc<FlynnelRing<JobRef>>>,
injector: Arc<Injector<JobRef>>,
parker: Arc<Parker>,
arena_shutdown: Arc<AtomicBool>,
parkers: Arc<Vec<Arc<OnceLock<Arc<Parker>>>>>,
stats: Arc<WorkerStats>,
peer_stats: Vec<Arc<WorkerStats>>,
sleep: Arc<crate::sched::jec_sleep::Sleep>,
is_primary: bool,
smt_requests: Arc<AtomicU32>,
) {
let ctx = WorkerCtx {
workers: my_tier_deques,
index: idx,
burst_pushed: Cell::new(0),
stealers,
steal_stash: core::cell::UnsafeCell::new(AdaptiveStash::empty()),
ccx_size,
mailbox,
peer_mailboxes,
injector,
rng: Cell::new(0x9E37_79B9_7F4A_7C15u64.wrapping_mul(idx as u64 + 1)),
parkers,
wake_rotor: Cell::new(idx),
stats,
peer_stats,
sleep,
last_victim: Cell::new(usize::MAX),
is_external_slot: false,
join_parker: Box::new(Parker::with_strategy(
0,
crate::sched::sleep::WaitStrategy::StdPark,
)),
};
unsafe { set_current_worker_ctx(&ctx as *const WorkerCtx) };
struct ClearOnDrop;
impl Drop for ClearOnDrop {
fn drop(&mut self) {
clear_current_worker_ctx();
}
}
let _clear_guard = ClearOnDrop;
let n = ctx.stealers.len();
let n_workers = ctx.sleep.worker_count();
let mut rng_state: u64 = 0x9E37_79B9_7F4A_7C15u64.wrapping_mul(idx as u64 + 1);
let trace_label = format!("flynnel-worker-{idx}");
let mut jec_idle: Option<crate::sched::jec_sleep::IdleState> = None;
macro_rules! jec_account_work_found {
() => {{
if let Some(idle) = jec_idle.take() {
ctx.sleep.work_found(&idle);
}
}};
}
while !parker.is_shutdown() && !arena_shutdown.load(Ordering::Acquire) {
crate::sched::trace::worker_loop_maybe_flush(&trace_label);
if !is_primary && smt_requests.load(Ordering::Acquire) == 0 {
const SMT_SIBLING_SPIN_ROUNDS: u32 = 1000;
let mut spun = 0u32;
let mut acquired_again = false;
while spun < SMT_SIBLING_SPIN_ROUNDS {
if smt_requests.load(Ordering::Acquire) > 0 {
acquired_again = true;
break;
}
if parker.is_shutdown() || arena_shutdown.load(Ordering::Acquire) {
return;
}
std::thread::yield_now();
spun += 1;
}
if acquired_again {
continue;
}
const SMT_SIBLING_SLEEP_ROUNDS: u32 = 100;
const SMT_SIBLING_SLEEP_US: u64 = 100;
let mut slept = 0u32;
while slept < SMT_SIBLING_SLEEP_ROUNDS {
if smt_requests.load(Ordering::Acquire) > 0 {
acquired_again = true;
break;
}
if parker.is_shutdown() || arena_shutdown.load(Ordering::Acquire) {
return;
}
std::thread::sleep(std::time::Duration::from_micros(SMT_SIBLING_SLEEP_US));
slept += 1;
}
if acquired_again {
continue;
}
let smt_ref = &*smt_requests;
let parker_ref = &*parker;
let arena_shutdown_ref = &*arena_shutdown;
let _wait_rc = parker.park_until(|| {
smt_ref.load(Ordering::Acquire) > 0
|| parker_ref.is_shutdown()
|| arena_shutdown_ref.load(Ordering::Acquire)
});
continue;
}
{
let stash = unsafe { &mut *ctx.steal_stash.get() };
if let Some(job) = stash.drain_one() {
jec_account_work_found!();
unsafe { job.execute() };
continue;
}
}
if let PopResult::Ok(job) = ctx.mailbox.pop() {
ctx.stats
.local_pops
.fetch_add(1, core::sync::atomic::Ordering::Relaxed);
jec_account_work_found!();
unsafe { job.execute() };
continue;
}
let mut popped_local = false;
for tier in DequeTier::all() {
if let Some(job) = ctx.workers[tier.idx()].pop() {
ctx.stats
.local_pops
.fetch_add(1, core::sync::atomic::Ordering::Relaxed);
jec_account_work_found!();
unsafe { job.execute() };
popped_local = true;
break;
}
}
if popped_local {
continue;
}
match ctx.injector.steal() {
Steal::Success(job) => {
jec_account_work_found!();
unsafe { job.execute() };
continue;
}
Steal::Empty | Steal::Retry => {}
}
{
let mut claimed = ctx.sleep.claimed_slots();
let mut found = false;
while claimed != 0 {
let slot = n_workers + claimed.trailing_zeros() as usize;
claimed &= claimed - 1;
if slot < n
&& let Some(job) = ctx.steal_from_peer_tiered(slot)
{
jec_account_work_found!();
unsafe { job.execute() };
found = true;
break;
}
}
if found {
continue;
}
}
if n_workers >= 2 {
let n = n_workers;
let probe_count = if n <= PROBE_FULL_CUTOFF {
n - 1
} else {
PROBE_LARGE
};
let mut found = false;
let start = pick_victim(&mut rng_state, idx, n);
let mut probed = 0usize;
let mut offset = 0usize;
while probed < probe_count && offset < n {
let victim = (start + offset) % n;
offset += 1;
if victim == idx {
continue;
}
probed += 1;
let distance = peer_distance(idx, victim, ccx_size);
for tier_idx in distance.idx()..N_TIERS {
let stash = unsafe { &mut *ctx.steal_stash.get() };
let job_opt = match steal_via_stash(&ctx.stealers[victim][tier_idx], stash) {
AdaptiveSteal2::Success(j) => Some(j),
AdaptiveSteal2::Empty => None,
AdaptiveSteal2::Retry => {
match steal_via_stash(&ctx.stealers[victim][tier_idx], stash) {
AdaptiveSteal2::Success(j) => Some(j),
_ => None,
}
}
};
if let Some(job) = job_opt {
ctx.stats
.peer_steal_hits
.fetch_add(1, core::sync::atomic::Ordering::Relaxed);
if victim < ctx.peer_stats.len() {
ctx.peer_stats[victim]
.times_stolen_from
.fetch_add(1, core::sync::atomic::Ordering::Relaxed);
}
ctx.last_victim.set(victim);
ctx.prefetch_last_victim_stealer();
jec_account_work_found!();
unsafe { job.execute() };
found = true;
break;
}
}
if found {
break;
}
}
if found {
continue;
}
ctx.stats
.peer_steal_misses
.fetch_add(1, core::sync::atomic::Ordering::Relaxed);
}
let idle = jec_idle.get_or_insert_with(|| ctx.sleep.start_looking(idx));
let inj_ref = &ctx.injector;
let mailbox_ref = &ctx.mailbox;
ctx.sleep.no_work_found(idle, || {
!inj_ref.is_empty()
|| (MAILBOX_EVER_USED.load(core::sync::atomic::Ordering::Acquire)
&& !mailbox_ref.is_empty())
});
}
if let Some(idle) = jec_idle.take() {
ctx.sleep.work_found(&idle);
}
}
fn pick_victim(state: &mut u64, self_idx: usize, n: usize) -> usize {
let mut x = *state;
x ^= x << 13;
x ^= x >> 7;
x ^= x << 17;
*state = x;
let mut v = (x as usize) % n;
if v == self_idx {
v = (v + 1) % n;
}
v
}
#[cfg(test)]
mod tests {
use super::*;
use std::sync::atomic::AtomicU32;
use std::time::{Duration, Instant};
use crate::foundation::Variant;
use crate::sched::job::{NUMA_HINT_ANY, StackJob};
use crate::sched::latch::CoreLatch;
#[test]
fn external_slots_preallocated_and_indexed() {
let arena = LocalArena::with_smt_extension(2, 0, None);
assert_eq!(arena.external_slots.len(), EXTERNAL_SLOT_COUNT);
for (i, slot) in arena.external_slots.iter().enumerate() {
assert!(!slot.is_claimed(), "slot {i} unclaimed at init");
assert_eq!(slot.index(), 2 + i,
"slot {i} indexed at workers.len() + i");
}
assert_eq!(arena.stealers.len(),
arena.workers.len() + EXTERNAL_SLOT_COUNT);
}
#[test]
fn external_slot_claim_release_lifecycle() {
let arena = LocalArena::with_smt_extension(1, 0, None);
let guard = arena.try_claim_external_slot()
.expect("first claim must succeed");
let slot_idx = guard.ctx_ref().index;
assert_eq!(slot_idx, 1, "first claim takes slot 0 at index n=1");
assert!(arena.external_slots[0].is_claimed(),
"slot 0 marked claimed");
drop(guard);
assert!(!arena.external_slots[0].is_claimed(),
"slot 0 released on guard drop");
}
#[test]
fn claimed_slot_mask_indexes_from_the_worker_count() {
let arena = LocalArena::with_smt_extension(2, 1, None);
let n = arena.workers.len();
assert_eq!(arena.sleep.worker_count(), n,
"sleep coordinator counts the workers the slots index from");
assert_eq!(arena.sleep.claimed_slots(), 0, "no slot held at rest");
let first = arena.try_claim_external_slot().expect("a free slot");
let second = arena.try_claim_external_slot().expect("a second free slot");
assert_eq!(arena.sleep.claimed_slots(), 0b11, "both held slots in the mask");
for bit in 0..2u32 {
let idx = n + bit as usize;
assert!(idx < arena.stealers.len(),
"held slot {bit} addresses a registered stealer");
}
drop(second);
assert_eq!(arena.sleep.claimed_slots(), 0b01, "released slot leaves the mask");
drop(first);
assert_eq!(arena.sleep.claimed_slots(), 0, "mask empty once both are released");
}
#[test]
fn new_arena_spawns_workers() {
let (done_tx, done_rx) = std::sync::mpsc::channel::<usize>();
let built = std::thread::spawn(move || {
let a = LocalArena::new(4);
let count = a.worker_count();
drop(a);
if done_tx.send(count).is_err() {
eprintln!("the arena finished after the test stopped waiting for it");
}
count
});
let count = match done_rx.recv_timeout(Duration::from_secs(30)) {
Ok(count) => count,
Err(std::sync::mpsc::RecvTimeoutError::Timeout) => panic!(
"LocalArena::new(4) and its drop did not complete within 30 seconds; \
a worker is parked with nothing left to wake it"
),
Err(std::sync::mpsc::RecvTimeoutError::Disconnected) => {
built.join().expect("the arena thread panicked without reporting");
unreachable!("a join over a dropped sender re-raises the panic that dropped it")
}
};
built.join().expect("the arena thread reported before this join");
assert_eq!(count, 4);
}
#[test]
fn new_arena_with_zero_workers_clamps_to_one() {
let a = LocalArena::new(0);
assert_eq!(a.worker_count(), 1);
}
#[test]
fn submit_one_job_runs_to_completion() {
let arena = LocalArena::new(2);
let counter = Arc::new(AtomicU32::new(0));
let c = Arc::clone(&counter);
let job = StackJob::new(
move |_stolen| {
c.fetch_add(1, Ordering::SeqCst);
},
CoreLatch::new(),
);
unsafe {
let r = job.as_job_ref(2, NUMA_HINT_ANY, Variant::Faithful);
arena.submit(r);
}
let deadline = Instant::now() + Duration::from_secs(5);
while !job.latch.is_set() {
if Instant::now() > deadline {
panic!("submitted job did not complete within 5s");
}
thread::yield_now();
}
assert_eq!(counter.load(Ordering::SeqCst), 1);
drop(arena);
}
#[test]
fn submit_many_jobs_all_run_exactly_once() {
const N: u32 = 256;
let arena = LocalArena::new(4);
let counter = Arc::new(AtomicU32::new(0));
let jobs: Vec<_> = (0..N)
.map(|_| {
let c = Arc::clone(&counter);
StackJob::new(
move |_stolen| {
c.fetch_add(1, Ordering::SeqCst);
},
CoreLatch::new(),
)
})
.collect();
for j in &jobs {
unsafe {
arena.submit(j.as_job_ref(2, NUMA_HINT_ANY, Variant::Faithful));
}
}
let deadline = Instant::now() + Duration::from_secs(10);
loop {
let pending = jobs.iter().filter(|j| !j.latch.is_set()).count();
if pending == 0 {
break;
}
if Instant::now() > deadline {
panic!("only {}/{N} jobs completed within 10s",
N as usize - pending);
}
thread::yield_now();
}
assert_eq!(counter.load(Ordering::SeqCst), N);
drop(arena);
}
#[test]
fn pick_victim_never_returns_self() {
let mut state: u64 = 0x1234_5678_9ABC_DEF0;
for _ in 0..1000 {
let v = pick_victim(&mut state, 3, 8);
assert_ne!(v, 3, "victim must not be self");
assert!(v < 8, "victim must be in range");
}
}
#[test]
fn pick_victim_distributes_across_n_minus_one_peers() {
let mut state: u64 = 0x9E37_79B9_7F4A_7C15;
let mut hits = [0u32; 8];
let self_idx = 0;
for _ in 0..1000 {
let v = pick_victim(&mut state, self_idx, 8);
hits[v] += 1;
}
assert_eq!(hits[self_idx], 0, "self never picked");
for (i, &h) in hits.iter().enumerate() {
if i != self_idx {
assert!(h > 50, "peer {i} got only {h} hits / 1000");
}
}
}
#[test]
fn mailbox_push_from_worker_routes_to_target_worker() {
let arena = LocalArena::new(2);
const N: u32 = 8;
let counter = Arc::new(AtomicU32::new(0));
type ChildBody = Box<dyn FnOnce(bool) + Send + 'static>;
type ChildJob = StackJob<CoreLatch, ChildBody, ()>;
let children: Vec<Box<ChildJob>> = (0..N)
.map(|_| {
let c = Arc::clone(&counter);
let body: ChildBody = Box::new(move |_| {
c.fetch_add(1, Ordering::SeqCst);
});
Box::new(StackJob::new(body, CoreLatch::new()))
})
.collect();
struct SendAddrs(Vec<usize>);
unsafe impl Send for SendAddrs {}
let addrs = SendAddrs(
children.iter().map(|b| Box::as_ref(b) as *const _ as usize).collect(),
);
let parent_done = Arc::new(AtomicU32::new(0));
let parent_done_clone = Arc::clone(&parent_done);
let parent_body: Box<dyn FnOnce(bool) + Send + 'static> = Box::new(move |_| {
let ctx_ptr = current_worker_ctx();
assert!(!ctx_ptr.is_null(), "parent must run on a worker thread");
let ctx = unsafe { &*ctx_ptr };
let target = if ctx.index == 0 { 1 } else { 0 };
for addr in &addrs.0 {
let sj_ptr = *addr as *const ChildJob;
let job = unsafe {
(*sj_ptr).as_job_ref(2, NUMA_HINT_ANY, Variant::Faithful)
};
if let Err(j) = ctx.push_to_mailbox(target, job) {
assert!(ctx.try_push(j).is_ok(), "test deque has room");
}
}
parent_done_clone.store(1, Ordering::Release);
});
let parent = StackJob::new(parent_body, CoreLatch::new());
unsafe {
arena.submit(parent.as_job_ref(2, NUMA_HINT_ANY, Variant::Faithful));
}
let deadline = Instant::now() + Duration::from_secs(10);
loop {
let pending = children.iter().filter(|j| !j.latch.is_set()).count();
let parent_set = parent.latch.is_set();
if pending == 0 && parent_set && parent_done.load(Ordering::Acquire) == 1 {
break;
}
if Instant::now() > deadline {
panic!(
"mailbox routing failed: {}/{N} children completed; \
parent_done={}; parent_latch={}",
N as usize - pending,
parent_done.load(Ordering::Acquire),
parent_set,
);
}
thread::yield_now();
}
assert_eq!(counter.load(Ordering::SeqCst), N);
drop(arena);
}
#[test]
fn push_tier_smt_local_is_drained_by_owner_or_sibling() {
let arena = LocalArena::new(2);
const N: u32 = 8;
let counter = Arc::new(AtomicU32::new(0));
type ChildBody = Box<dyn FnOnce(bool) + Send + 'static>;
type ChildJob = StackJob<CoreLatch, ChildBody, ()>;
let children: Vec<Box<ChildJob>> = (0..N)
.map(|_| {
let c = Arc::clone(&counter);
let body: ChildBody = Box::new(move |_| {
c.fetch_add(1, Ordering::SeqCst);
});
Box::new(StackJob::new(body, CoreLatch::new()))
})
.collect();
struct SendAddrs(Vec<usize>);
unsafe impl Send for SendAddrs {}
let addrs = SendAddrs(
children.iter().map(|b| Box::as_ref(b) as *const _ as usize).collect(),
);
let parent_done = Arc::new(AtomicU32::new(0));
let parent_done_clone = Arc::clone(&parent_done);
let parent_body: Box<dyn FnOnce(bool) + Send + 'static> = Box::new(move |_| {
let ctx_ptr = current_worker_ctx();
assert!(!ctx_ptr.is_null());
let ctx = unsafe { &*ctx_ptr };
for addr in &addrs.0 {
let sj_ptr = *addr as *const ChildJob;
let job = unsafe {
(*sj_ptr).as_job_ref(2, NUMA_HINT_ANY, Variant::Faithful)
};
assert!(ctx.try_push_tier(job, DequeTier::SmtLocal).is_ok(), "test deque has room");
}
parent_done_clone.store(1, Ordering::Release);
});
let parent = StackJob::new(parent_body, CoreLatch::new());
unsafe {
arena.submit(parent.as_job_ref(2, NUMA_HINT_ANY, Variant::Faithful));
}
let deadline = Instant::now() + Duration::from_secs(10);
loop {
let pending = children.iter().filter(|j| !j.latch.is_set()).count();
if pending == 0 && parent_done.load(Ordering::Acquire) == 1 {
break;
}
if Instant::now() > deadline {
panic!(
"push_tier SmtLocal: {}/{N} children pending; parent_done={}",
pending,
parent_done.load(Ordering::Acquire)
);
}
thread::yield_now();
}
assert_eq!(counter.load(Ordering::SeqCst), N);
drop(arena);
}
#[test]
fn arena_drop_joins_workers_cleanly() {
let arena = LocalArena::new(4);
let counter = Arc::new(AtomicU32::new(0));
for _ in 0..16 {
let c = Arc::clone(&counter);
let _ = c;
}
let t0 = Instant::now();
drop(arena);
let elapsed = t0.elapsed();
assert!(elapsed < Duration::from_secs(2),
"arena drop took {elapsed:?}, expected < 2s");
}
}