use super::Coordinator;
use indicatrix_dispatch::ParkedBudget;
use std::{
collections::{BTreeMap, HashMap, VecDeque},
fmt,
sync::{Arc, Condvar, Mutex, PoisonError},
time::Duration,
};
const BYTES_PER_PIXEL: u64 = 12;
pub const FRAME_BUFFERS_PER_JOB: u64 = 4;
pub const FRAME_BUFFERS_PER_LANE: u64 = 3;
#[must_use]
pub fn job_bytes(width: u32, height: u32) -> u64 {
frame_bytes(width, height) * FRAME_BUFFERS_PER_JOB
}
#[must_use]
pub fn lane_bytes(width: u32, height: u32, lanes: u32) -> u64 {
frame_bytes(width, height) * FRAME_BUFFERS_PER_LANE * u64::from(lanes)
}
#[must_use]
pub fn contribution_bytes(width: u32, height: u32) -> u64 {
frame_bytes(width, height)
}
#[must_use]
pub fn hdr_bytes(encoded_len: u64, decoded_texels: Option<u64>) -> u64 {
encoded_len.saturating_add(decoded_texels.map_or(0, |texels| texels.saturating_mul(12)))
}
#[must_use]
pub fn job_estimate_bytes(width: u32, height: u32, lanes: u32, extra_bytes: u64) -> u64 {
job_bytes(width, height)
.saturating_add(lane_bytes(width, height, lanes))
.saturating_add(extra_bytes)
}
fn frame_bytes(width: u32, height: u32) -> u64 {
u64::from(width) * u64::from(height) * BYTES_PER_PIXEL
}
pub struct MemoryBudget {
cap: u64,
used: Mutex<u64>,
}
pub struct Reservation<'a> {
budget: &'a MemoryBudget,
bytes: u64,
}
impl MemoryBudget {
#[must_use]
pub const fn new(cap: u64) -> Self {
Self {
cap,
used: Mutex::new(0),
}
}
#[must_use]
pub const fn cap(&self) -> u64 {
self.cap
}
pub fn try_reserve(&self, bytes: u64) -> Result<Reservation<'_>, u64> {
let mut used = self.used.lock().unwrap_or_else(PoisonError::into_inner);
if used.saturating_add(bytes) > self.cap {
return Err(*used);
}
*used += bytes;
drop(used);
Ok(Reservation {
budget: self,
bytes,
})
}
#[must_use]
pub fn in_use(&self) -> u64 {
*self.used.lock().unwrap_or_else(PoisonError::into_inner)
}
pub fn charge(&self, bytes: u64) -> bool {
let mut used = self.used.lock().unwrap_or_else(PoisonError::into_inner);
if used.saturating_add(bytes) > self.cap {
return false;
}
*used += bytes;
true
}
pub fn uncharge(&self, bytes: u64) {
let mut used = self.used.lock().unwrap_or_else(PoisonError::into_inner);
*used = used.saturating_sub(bytes);
}
}
impl Drop for Reservation<'_> {
fn drop(&mut self) {
let mut used = self
.budget
.used
.lock()
.unwrap_or_else(PoisonError::into_inner);
*used = used.saturating_sub(self.bytes);
}
}
#[derive(Default)]
pub struct ViewerQueues {
queues: Mutex<(u64, Queues)>,
changed: Condvar,
slots: Mutex<BTreeMap<Arc<str>, u32>>,
slot_freed: Condvar,
}
type Queues = HashMap<Arc<str>, VecDeque<u64>>;
pub struct Turn<'a> {
queues: &'a ViewerQueues,
viewer: Arc<str>,
ticket: u64,
}
pub struct SlotGuard<'a> {
queues: &'a ViewerQueues,
viewer: Arc<str>,
}
#[derive(Default)]
pub struct Admission<'a> {
_turn: Option<Turn<'a>>,
_slot: Option<SlotGuard<'a>>,
}
impl<'a> Admission<'a> {
#[must_use]
pub const fn turn(turn: Turn<'a>) -> Self {
Self {
_turn: Some(turn),
_slot: None,
}
}
#[must_use]
pub const fn slot(slot: SlotGuard<'a>) -> Self {
Self {
_turn: None,
_slot: Some(slot),
}
}
}
impl ViewerQueues {
const RECHECK: Duration = Duration::from_millis(50);
pub fn wait_turn(&self, viewer: &Arc<str>, cancelled: impl Fn() -> bool) -> Option<Turn<'_>> {
let mut guard = self.queues.lock().unwrap_or_else(PoisonError::into_inner);
let ticket = guard.0;
guard.0 += 1;
guard
.1
.entry(Arc::clone(viewer))
.or_default()
.push_back(ticket);
loop {
if guard.1.get(viewer).and_then(VecDeque::front) == Some(&ticket) {
return Some(Turn {
queues: self,
viewer: Arc::clone(viewer),
ticket,
});
}
if cancelled() {
Self::remove(&mut guard.1, viewer, ticket);
drop(guard);
self.changed.notify_all();
return None;
}
guard = self
.changed
.wait_timeout(guard, Self::RECHECK)
.unwrap_or_else(PoisonError::into_inner)
.0;
}
}
pub fn wait_slot(
&self,
viewer: &Arc<str>,
cap: u32,
cancelled: impl Fn() -> bool,
) -> Option<SlotGuard<'_>> {
let cap = cap.max(1);
let mut slots = self.slots.lock().unwrap_or_else(PoisonError::into_inner);
loop {
if slots.get(viewer).copied().unwrap_or(0) < cap {
*slots.entry(Arc::clone(viewer)).or_insert(0) += 1;
return Some(SlotGuard {
queues: self,
viewer: Arc::clone(viewer),
});
}
if cancelled() {
return None;
}
slots = self
.slot_freed
.wait_timeout(slots, Self::RECHECK)
.unwrap_or_else(PoisonError::into_inner)
.0;
}
}
#[cfg(test)]
#[must_use]
pub fn queued(&self, viewer: &str) -> usize {
self.queues
.lock()
.unwrap_or_else(PoisonError::into_inner)
.1
.get(viewer)
.map_or(0, VecDeque::len)
}
#[cfg(test)]
#[must_use]
pub fn slots_held(&self, viewer: &str) -> u32 {
self.slots
.lock()
.unwrap_or_else(PoisonError::into_inner)
.get(viewer)
.copied()
.unwrap_or(0)
}
fn remove(queues: &mut Queues, viewer: &Arc<str>, ticket: u64) {
if let Some(queue) = queues.get_mut(viewer) {
queue.retain(|&t| t != ticket);
if queue.is_empty() {
queues.remove(viewer);
}
}
}
}
impl Drop for Turn<'_> {
fn drop(&mut self) {
let mut guard = self
.queues
.queues
.lock()
.unwrap_or_else(PoisonError::into_inner);
ViewerQueues::remove(&mut guard.1, &self.viewer, self.ticket);
drop(guard);
self.queues.changed.notify_all();
}
}
impl Drop for SlotGuard<'_> {
fn drop(&mut self) {
let mut slots = self
.queues
.slots
.lock()
.unwrap_or_else(PoisonError::into_inner);
if let Some(running) = slots.get_mut(&self.viewer) {
*running = running.saturating_sub(1);
if *running == 0 {
slots.remove(&self.viewer);
}
}
drop(slots);
self.queues.slot_freed.notify_all();
}
}
pub struct JobParkedBudget(pub Arc<Coordinator>);
impl fmt::Debug for JobParkedBudget {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_struct("JobParkedBudget").finish_non_exhaustive()
}
}
impl ParkedBudget for JobParkedBudget {
fn reserve(&self, bytes: u64) -> bool {
self.0.budget().charge(bytes)
}
fn release(&self, bytes: u64) {
self.0.budget().uncharge(bytes);
}
}
#[cfg(test)]
mod tests {
use super::*;
use std::sync::atomic::{AtomicBool, Ordering};
#[test]
fn the_budget_refuses_past_its_cap_and_frees_on_drop() {
let budget = MemoryBudget::new(100);
let a = budget.try_reserve(60).unwrap();
assert_eq!(budget.try_reserve(50).err(), Some(60));
drop(a);
assert_eq!(budget.in_use(), 0);
assert!(budget.try_reserve(100).is_ok());
assert_eq!(job_bytes(10, 10), 100 * 12 * FRAME_BUFFERS_PER_JOB);
}
#[test]
fn charge_and_uncharge_share_the_cap_with_try_reserve() {
let budget = MemoryBudget::new(100);
let reservation = budget.try_reserve(60).unwrap();
assert!(budget.charge(40));
assert_eq!(budget.in_use(), 100);
assert!(!budget.charge(1), "past the shared cap");
budget.uncharge(40);
assert_eq!(budget.in_use(), 60);
drop(reservation);
assert_eq!(budget.in_use(), 0);
}
#[test]
fn one_viewer_runs_one_job_at_a_time_in_arrival_order() {
let queues = Arc::new(ViewerQueues::default());
let viewer: Arc<str> = Arc::from("laptop");
let other: Arc<str> = Arc::from("desktop");
let first = queues.wait_turn(&viewer, || false).unwrap();
drop(queues.wait_turn(&other, || false).unwrap());
let started = Arc::new(AtomicBool::new(false));
let (pass_tx, pass_rx) = std::sync::mpsc::channel();
let waiter = {
let (queues, viewer, started) = (
Arc::clone(&queues),
Arc::clone(&viewer),
Arc::clone(&started),
);
std::thread::spawn(move || {
let _turn = queues
.wait_turn(&viewer, || {
let _ = pass_tx.send(());
false
})
.unwrap();
started.store(true, Ordering::SeqCst);
})
};
for pass in 1..=3 {
pass_rx
.recv_timeout(Duration::from_secs(5))
.unwrap_or_else(|_| {
panic!("the second job never reached wait pass {pass} of its viewer's queue")
});
}
assert!(!started.load(Ordering::SeqCst), "the second job must wait");
assert_eq!(queues.queued("laptop"), 2);
drop(first);
waiter.join().unwrap();
assert!(started.load(Ordering::SeqCst));
assert_eq!(queues.queued("laptop"), 0);
}
const DEFAULT_BUDGET: u64 = 2048 * 1024 * 1024;
#[test]
fn the_estimate_charges_every_lane_its_frame_buffers() {
let (w, h) = (100, 10);
let frame = 100 * 10 * 12;
assert_eq!(lane_bytes(w, h, 1), frame * FRAME_BUFFERS_PER_LANE);
assert_eq!(lane_bytes(w, h, 0), 0);
assert_eq!(
job_estimate_bytes(w, h, 5, 7),
frame * (FRAME_BUFFERS_PER_JOB + 5 * FRAME_BUFFERS_PER_LANE) + 7
);
assert_eq!(contribution_bytes(w, h), frame);
assert_eq!(hdr_bytes(1000, None), 1000);
assert_eq!(hdr_bytes(1000, Some(10)), 1000 + 120);
}
#[test]
fn an_8k_job_on_ten_lanes_exceeds_the_default_budget_while_1080p_on_two_lanes_fits() {
let budget = MemoryBudget::new(DEFAULT_BUDGET);
let huge = job_estimate_bytes(7680, 4320, 10, 0);
assert!(huge > DEFAULT_BUDGET, "{huge} bytes must not fit");
assert!(budget.try_reserve(huge).is_err());
let small = job_estimate_bytes(1920, 1080, 2, 0);
assert!(small < DEFAULT_BUDGET, "{small} bytes must fit");
assert!(budget.try_reserve(small).is_ok());
}
#[test]
fn a_cancelled_waiter_leaves_the_queue() {
let queues = ViewerQueues::default();
let viewer: Arc<str> = Arc::from("laptop");
let _first = queues.wait_turn(&viewer, || false).unwrap();
assert!(queues.wait_turn(&viewer, || true).is_none());
assert_eq!(queues.queued("laptop"), 1);
}
#[test]
fn wait_slot_admits_cap_jobs_and_blocks_the_next_until_one_drops() {
let queues = Arc::new(ViewerQueues::default());
let viewer: Arc<str> = Arc::from("laptop");
let other: Arc<str> = Arc::from("desktop");
let first = queues.wait_slot(&viewer, 2, || false).unwrap();
let second = queues.wait_slot(&viewer, 2, || false).unwrap();
assert_eq!(queues.slots_held("laptop"), 2);
drop(queues.wait_slot(&other, 1, || false).unwrap());
assert_eq!(
queues.slots_held("desktop"),
0,
"a dropped slot is given back"
);
let started = Arc::new(AtomicBool::new(false));
let (pass_tx, pass_rx) = std::sync::mpsc::channel();
let waiter = {
let (queues, viewer, started) = (
Arc::clone(&queues),
Arc::clone(&viewer),
Arc::clone(&started),
);
std::thread::spawn(move || {
let _slot = queues
.wait_slot(&viewer, 2, || {
let _ = pass_tx.send(());
false
})
.unwrap();
started.store(true, Ordering::SeqCst);
})
};
for pass in 1..=3 {
pass_rx
.recv_timeout(Duration::from_secs(5))
.unwrap_or_else(|_| {
panic!("the third job never reached wait pass {pass} of its viewer's slots")
});
}
assert!(!started.load(Ordering::SeqCst), "the third job must wait");
assert_eq!(queues.slots_held("laptop"), 2);
drop(first);
waiter.join().unwrap();
assert!(started.load(Ordering::SeqCst));
assert_eq!(queues.slots_held("laptop"), 1, "only `second` is left");
drop(second);
assert_eq!(queues.slots_held("laptop"), 0);
}
#[test]
fn a_cancelled_slot_waiter_takes_nothing_and_a_zero_cap_means_one() {
let queues = ViewerQueues::default();
let viewer: Arc<str> = Arc::from("laptop");
let first = queues.wait_slot(&viewer, 0, || false).unwrap();
assert!(queues.wait_slot(&viewer, 0, || true).is_none());
assert_eq!(queues.slots_held("laptop"), 1);
drop(first);
assert_eq!(queues.slots_held("laptop"), 0);
}
#[test]
fn an_admission_releases_its_turn_or_slot_when_dropped() {
let queues = ViewerQueues::default();
let viewer: Arc<str> = Arc::from("laptop");
let turn = Admission::turn(queues.wait_turn(&viewer, || false).unwrap());
let slot = Admission::slot(queues.wait_slot(&viewer, 1, || false).unwrap());
assert_eq!(
(queues.queued("laptop"), queues.slots_held("laptop")),
(1, 1)
);
drop(slot);
assert_eq!(
(queues.queued("laptop"), queues.slots_held("laptop")),
(1, 0)
);
drop(turn);
assert_eq!(
(queues.queued("laptop"), queues.slots_held("laptop")),
(0, 0)
);
drop(Admission::default());
}
}