openentropy_core/sources/scheduling/

dispatch_queue_timing.rs

//! GCD dispatch queue timing — entropy from the libdispatch thread pool.
//!
//! Grand Central Dispatch maintains a system-wide worker thread pool shared
//! across all running processes. When we dispatch a block to the low-priority
//! global queue and wait for it to complete, the round-trip latency encodes the
//! instantaneous state of that shared pool: how many threads are busy, what
//! their current work items are, and how the kernel's scheduler has decided
//! to interleave our dispatch with all other queued work.
//!
//! ## Physics
//!
//! Unlike process-local scheduling (which only sees our own threads), the GCD
//! global queues are **process-shared**. Every background task from every
//! running process — Spotlight indexing, Time Machine backups, photo analysis,
//! iCloud sync, app prewarming — competes for the same thread pool slots.
//!
//! The BACKGROUND priority queue shows the highest variance (CV up to 248%)
//! because it receives the lowest-priority work: when the system is under load,
//! background tasks get preempted and queued behind higher-priority work.
//! Our timing measurement captures the full system-wide load distribution at
//! the moment of dispatch.
//!
//! Empirically measured on M4 Mac mini:
//! - `LOW` queue: CV up to 248%, range 131–16,412 ticks
//! - `BACKGROUND` queue: CV ~50%, H≈7.3 bits/low-byte
//! - `HIGH` queue: CV ~41%, H≈7.1 bits/low-byte (less entropy, less jitter)
//!
//! Each measurement completes in ~200–600 ticks (~8–25 µs), making this one
//! of the faster frontier sources.
//!
//! ## Uniqueness
//!
//! This is the first entropy source to exploit GCD's process-shared thread pool.
//! Every other scheduling-based entropy source is per-process. This source
//! aggregates nondeterminism from the entire running system in a single
//! measurement.

use crate::source::{EntropySource, Platform, SourceCategory, SourceInfo};
#[cfg(target_os = "macos")]
use crate::sources::helpers::{extract_timing_entropy, mach_time};

static DISPATCH_QUEUE_TIMING_INFO: SourceInfo = SourceInfo {
    name: "dispatch_queue_timing",
    description: "GCD libdispatch global queue timing — system-wide thread pool entropy",
    physics: "Dispatches a no-op block to the BACKGROUND and LOW GCD global queues and \
              measures round-trip latency. GCD\u{2019}s global queues are shared across all \
              running processes; our measurement reflects the instantaneous load from \
              every background task on the system (Spotlight, iCloud, photo analysis, \
              app prewarming, etc.). LOW queue CV up to 248%, BACKGROUND H\u{2248}7.3 bits/byte \
              on M4 Mac mini. Unlike thread scheduling sources, this captures \
              system-wide nondeterminism from a single dispatch call.",
    category: SourceCategory::Scheduling,
    platform: Platform::MacOS,
    requirements: &[],
    entropy_rate_estimate: 3.0,
    composite: false,
    is_fast: false,
};

/// Entropy source that harvests GCD global queue scheduling jitter.
pub struct DispatchQueueTimingSource;

/// libdispatch FFI (macOS only).
///
/// We use `dispatch_async_f` (C function pointer variant of `dispatch_async`)
/// because Rust cannot construct Objective-C blocks directly. The block
/// alternative `dispatch_async` takes a Block_literal — `dispatch_async_f`
/// takes a plain `void (*)(void *)` function pointer and a context pointer,
/// which maps cleanly to Rust.
#[cfg(target_os = "macos")]
mod libdispatch {
    use std::ffi::c_void;

    /// Opaque GCD queue handle.
    pub type DispatchQueueT = *mut c_void;
    /// Opaque GCD semaphore handle.
    pub type DispatchSemaphoreT = *mut c_void;
    /// `DISPATCH_TIME_NOW` — base for computing dispatch timeouts.
    pub const DISPATCH_TIME_NOW: u64 = 0;

    // GCD priority levels.
    pub const _DISPATCH_QUEUE_PRIORITY_HIGH: i64 = 2;
    pub const DISPATCH_QUEUE_PRIORITY_LOW: i64 = -2;
    pub const DISPATCH_QUEUE_PRIORITY_BACKGROUND: i64 = i16::MIN as i64;

    /// 100ms timeout in nanoseconds — more than enough for a GCD dispatch
    /// round-trip (typical: 8–25 µs). Prevents indefinite blocking if the
    /// thread pool is saturated.
    pub const SEMAPHORE_TIMEOUT_NS: i64 = 100_000_000;

    #[link(name = "System", kind = "dylib")]
    unsafe extern "C" {
        pub fn dispatch_get_global_queue(identifier: i64, flags: usize) -> DispatchQueueT;
        pub fn dispatch_semaphore_create(value: isize) -> DispatchSemaphoreT;
        pub fn dispatch_semaphore_signal(dsema: DispatchSemaphoreT) -> isize;
        pub fn dispatch_semaphore_wait(dsema: DispatchSemaphoreT, timeout: u64) -> isize;
        pub fn dispatch_time(when: u64, delta: i64) -> u64;
        pub fn dispatch_async_f(
            queue: DispatchQueueT,
            context: *mut c_void,
            work: unsafe extern "C" fn(*mut c_void),
        );
        pub fn dispatch_release(obj: *mut c_void);
    }

    /// The work function dispatched to the GCD queue.
    ///
    /// Receives a raw pointer to a `DispatchSemaphoreT` and signals it.
    ///
    /// # Safety
    /// `ctx` must point to a valid `DispatchSemaphoreT` that will not be
    /// freed until after the signal returns.
    pub unsafe extern "C" fn signal_semaphore(ctx: *mut std::ffi::c_void) {
        let sem = ctx as DispatchSemaphoreT;
        // SAFETY: caller ensures sem is valid for the duration of dispatch.
        unsafe { dispatch_semaphore_signal(sem) };
    }
}

#[cfg(target_os = "macos")]
mod imp {
    use super::libdispatch::*;
    use super::*;

    impl EntropySource for DispatchQueueTimingSource {
        fn info(&self) -> &SourceInfo {
            &DISPATCH_QUEUE_TIMING_INFO
        }

        fn is_available(&self) -> bool {
            // libdispatch is always available on macOS.
            true
        }

        fn collect(&self, n_samples: usize) -> Vec<u8> {
            // 8× oversampling for robust extraction.
            let raw_count = n_samples * 8 + 64;
            let mut timings = Vec::with_capacity(raw_count);

            // Rotate between LOW and BACKGROUND queues to capture both
            // interrupt-phase jitter (LOW, higher peaks) and steady-state
            // pool saturation (BACKGROUND, higher mean entropy).
            let priorities = [
                DISPATCH_QUEUE_PRIORITY_LOW,
                DISPATCH_QUEUE_PRIORITY_BACKGROUND,
            ];

            // Warm up: let the GCD thread pool reach its normal distribution.
            for i in 0..32_usize {
                let queue =
                    unsafe { dispatch_get_global_queue(priorities[i % priorities.len()], 0) };
                let sem = unsafe { dispatch_semaphore_create(0) };
                if sem.is_null() {
                    continue;
                }
                unsafe {
                    let timeout = dispatch_time(DISPATCH_TIME_NOW, SEMAPHORE_TIMEOUT_NS);
                    dispatch_async_f(queue, sem, signal_semaphore);
                    dispatch_semaphore_wait(sem, timeout);
                    dispatch_release(sem);
                }
            }

            for i in 0..raw_count {
                let queue =
                    unsafe { dispatch_get_global_queue(priorities[i % priorities.len()], 0) };

                let sem = unsafe { dispatch_semaphore_create(0) };
                if sem.is_null() {
                    continue;
                }

                let t0 = mach_time();
                let timed_out = unsafe {
                    let timeout = dispatch_time(DISPATCH_TIME_NOW, SEMAPHORE_TIMEOUT_NS);
                    dispatch_async_f(queue, sem, signal_semaphore);
                    dispatch_semaphore_wait(sem, timeout) != 0
                };
                let elapsed = mach_time().wrapping_sub(t0);

                unsafe { dispatch_release(sem) };

                // Skip timed-out samples and suspend/resume artifacts (>10ms).
                if !timed_out && elapsed < 240_000 {
                    timings.push(elapsed);
                }
            }

            extract_timing_entropy(&timings, n_samples)
        }
    }
}

#[cfg(not(target_os = "macos"))]
impl EntropySource for DispatchQueueTimingSource {
    fn info(&self) -> &SourceInfo {
        &DISPATCH_QUEUE_TIMING_INFO
    }

    fn is_available(&self) -> bool {
        false
    }

    fn collect(&self, _n_samples: usize) -> Vec<u8> {
        Vec::new()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn info() {
        let src = DispatchQueueTimingSource;
        assert_eq!(src.info().name, "dispatch_queue_timing");
        assert!(matches!(src.info().category, SourceCategory::Scheduling));
        assert_eq!(src.info().platform, Platform::MacOS);
        assert!(!src.info().composite);
    }

    #[test]
    #[cfg(target_os = "macos")]
    fn is_available_on_macos() {
        assert!(DispatchQueueTimingSource.is_available());
    }

    #[test]
    #[ignore] // Requires live GCD thread pool
    fn collects_bytes_with_variation() {
        let src = DispatchQueueTimingSource;
        if !src.is_available() {
            return;
        }
        let data = src.collect(32);
        assert!(!data.is_empty());
        let unique: std::collections::HashSet<u8> = data.iter().copied().collect();
        assert!(unique.len() > 4, "expected variation from GCD pool jitter");
    }
}