1pub mod host;
9pub mod pooled;
10pub mod recent;
11pub mod trace;
12
13use std::cell::RefCell;
14use std::collections::{BTreeMap, BTreeSet};
15use std::time::{Duration, SystemTime};
16
17use crate::api::Spread;
18use crate::api::{Basis, HostMemory, JobPeak};
19use crate::config::{self, Config};
20use crate::scheduler::priority::{Around, Backfill, Candidate, Caps, Held, Older, Runner, Short};
21use crate::scheduler::{Barrier, Drained, Left, Pool, Scarce, Waits};
22use crate::sizing::{GRANULE, History, Measure, Ran, spread};
23use crate::time;
24use recent::{Ending, RECENT_RUNS, Recent};
25use trace::{Hazard, OOMD_UNDER, Reading, RunId, RunTrace, STEP, THROTTLES_UNDER, Trace};
26
27pub const UNPREDICTABLE_FOR: u64 = 7 * 24 * 3600 * 1000;
31
32pub const OWN_RUNS: u64 = 2;
35
36pub const HIGH_WATER: u64 = 90;
38
39pub const CPU_GRANULE: u64 = 100;
41
42#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
44pub struct Key {
45 pub repository: String,
47 pub workflow: Option<String>,
49 pub name: String,
51}
52
53impl Key {
54 pub fn of(run: &Ran) -> Key {
56 Key {
57 repository: run.repository.clone(),
58 workflow: run.workflow.clone(),
59 name: run.name.clone(),
60 }
61 }
62}
63
64#[derive(Debug, Clone, Copy, PartialEq, Eq)]
67pub enum Copies {
68 Alone,
70 Several,
72}
73
74#[derive(Debug, Clone, Copy, PartialEq, Eq)]
76pub struct Prediction {
77 pub memory: u64,
79 pub basis: Basis,
81}
82
83#[derive(Debug, Clone, Copy, PartialEq, Eq)]
85pub struct CpuPrediction {
86 pub cpu: u64,
88 pub basis: Basis,
90}
91
92#[derive(Debug, Clone, Default)]
94struct Averages {
95 sorted: Vec<u64>,
96 succeeded: u64,
97}
98
99impl Averages {
100 fn add(&mut self, average: u64, succeeded: bool) {
101 let at = self.sorted.partition_point(|known| *known <= average);
102 self.sorted.insert(at, average);
103 self.succeeded += u64::from(succeeded);
104 }
105
106 fn runs(&self) -> u64 {
107 self.sorted.len() as u64
108 }
109
110 fn p95(&self) -> u64 {
111 spread(self.sorted.clone()).p95
112 }
113
114 fn max(&self) -> u64 {
115 self.sorted.last().copied().unwrap_or(0)
116 }
117}
118
119#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
121struct InProfile {
122 key: Key,
123 profile: String,
124}
125
126impl InProfile {
127 fn new(key: &Key, profile: &str) -> InProfile {
128 InProfile {
129 key: key.clone(),
130 profile: profile.to_owned(),
131 }
132 }
133}
134
135#[derive(Debug, Clone)]
137pub struct Predictor {
138 margin: u32,
139 min_jobs: u32,
140 recent: Recent,
142 cpu_jobs: BTreeMap<InProfile, Averages>,
145 cpu_profiles: BTreeMap<String, Averages>,
146}
147
148impl Predictor {
149 pub fn new(rules: &config::Sizing) -> Predictor {
151 Predictor {
152 margin: rules.margin,
153 min_jobs: rules.min_jobs,
154 recent: Recent::new(RECENT_RUNS.max(u64::from(rules.min_jobs))),
155 cpu_jobs: BTreeMap::new(),
156 cpu_profiles: BTreeMap::new(),
157 }
158 }
159
160 pub fn read(
163 rules: &config::Sizing,
164 history: &History,
165 cap_of: impl Fn(&str) -> Option<u64>,
166 ) -> Predictor {
167 let mut predictor = Predictor::new(rules);
168 predictor.read_until(history, u64::MAX, cap_of);
169 predictor
170 }
171
172 fn read_until(&mut self, history: &History, until: u64, cap_of: impl Fn(&str) -> Option<u64>) {
174 for (run, ending) in recent::rows(history) {
175 let cap = run
176 .memory_cap
177 .or_else(|| cap_of(&run.profile))
178 .unwrap_or(u64::MAX);
179 let at = recent::finished(run);
180 if at >= until {
181 break;
182 }
183 match ending {
184 Ending::Finished => self.learn(run, &run.profile, cap, at),
185 Ending::Cancelled => self.mark(run, &run.profile, cap, at),
186 }
187 }
188 }
189
190 pub fn learn(&mut self, run: &Ran, profile: &str, cap: u64, at: u64) {
193 self.recent.read(run, profile, Ending::Finished, cap, at);
194 self.learn_cpu(run, profile);
195 }
196
197 pub fn learn_cpu(&mut self, run: &Ran, profile: &str) {
199 let Some(average) = run.cpu_average else {
200 return;
201 };
202 self.cpu_profiles
203 .entry(profile.to_owned())
204 .or_default()
205 .add(average, run.succeeded);
206 self.cpu_jobs
207 .entry(InProfile::new(&Key::of(run), profile))
208 .or_default()
209 .add(average, run.succeeded);
210 }
211
212 pub fn predict_cpu(&self, key: &Key, profile: &str, cap: u64) -> CpuPrediction {
216 let job = self.cpu_jobs.get(&InProfile::new(key, profile));
217 let min_jobs = u64::from(self.min_jobs);
218 let peers = self
219 .cpu_profiles
220 .get(profile)
221 .filter(|peers| peers.runs() >= min_jobs);
222 let (cpu, basis) = match (job.filter(|job| job.runs() > 0), peers) {
223 (Some(job), _) if job.runs() >= min_jobs => (
224 job.p95(),
225 Basis::Job {
226 runs: job.runs(),
227 peak: JobPeak::P95,
228 },
229 ),
230 (Some(job), Some(_)) if job.succeeded >= OWN_RUNS => (
231 job.max(),
232 Basis::Job {
233 runs: job.runs(),
234 peak: JobPeak::Largest,
235 },
236 ),
237 (Some(job), Some(peers)) => (
238 job.max().max(peers.p95()),
239 Basis::Profile { runs: peers.runs() },
240 ),
241 (None, Some(peers)) => (peers.max(), Basis::ProfileMax { runs: peers.runs() }),
242 _ => (cap, Basis::Cap),
243 };
244 CpuPrediction {
245 cpu: cpu
246 .div_ceil(CPU_GRANULE)
247 .saturating_mul(CPU_GRANULE)
248 .clamp(CPU_GRANULE, cap.max(CPU_GRANULE)),
249 basis,
250 }
251 }
252
253 pub fn usual(&self, key: &Key, profile: &str) -> Option<Duration> {
255 self.recent.job(key, profile)?.usual()
256 }
257
258 pub fn longest_usual(
261 &self,
262 keys: impl IntoIterator<Item = Key>,
263 profile: &str,
264 ) -> Option<Duration> {
265 let usual: Option<Vec<Duration>> = keys
266 .into_iter()
267 .map(|key| self.usual(&key, profile))
268 .collect();
269 usual?.into_iter().max()
270 }
271
272 pub fn mark(&mut self, run: &Ran, profile: &str, cap: u64, at: u64) {
276 self.recent.read(run, profile, Ending::Cancelled, cap, at);
277 }
278
279 pub fn predict(
282 &self,
283 key: &Key,
284 profile: &str,
285 cap: u64,
286 now: u64,
287 copies: Copies,
288 ) -> Prediction {
289 let job = self.recent.job(key, profile);
290 if let Some(hold) = job.and_then(|job| job.held(now, Some(UNPREDICTABLE_FOR))) {
291 return Prediction {
292 memory: cap,
293 basis: Basis::Unpredictable {
294 until: hold.at.saturating_add(UNPREDICTABLE_FOR) / 1000,
295 },
296 };
297 }
298 let min_jobs = u64::from(self.min_jobs);
299 let peers = self.recent.profile(profile);
300 let peers_runs = peers.len() as u64;
301 let overran = job.and_then(|job| {
302 job.overruns(now, UNPREDICTABLE_FOR)
303 .fold(None, |most: Option<(u64, u64)>, overrun| {
304 let until = overrun.at.saturating_add(UNPREDICTABLE_FOR);
305 Some(most.map_or((overrun.peak, until), |(peak, last)| {
306 (peak.max(overrun.peak), last.max(until))
307 }))
308 })
309 });
310 let (memory, basis) = match (job, peers_runs >= min_jobs) {
311 (Some(job), _) if job.runs() == 0 => (cap, Basis::Cap),
313 (Some(job), _) if let Some((peak, until)) = overran => (
314 self.with_margin(job.max().max(peak)),
315 Basis::Overran {
316 until: until / 1000,
317 },
318 ),
319 (Some(job), _) if job.runs() >= min_jobs => (
320 self.with_margin(spread(job.peaks().to_vec()).p95),
321 Basis::Job {
322 runs: job.runs(),
323 peak: JobPeak::P95,
324 },
325 ),
326 (Some(job), true) if job.succeeded() >= OWN_RUNS && copies == Copies::Alone => (
327 self.with_margin(job.max()),
328 Basis::Job {
329 runs: job.runs(),
330 peak: JobPeak::Largest,
331 },
332 ),
333 (Some(job), true) => (
334 self.with_margin(job.max().max(spread(peers.to_vec()).p95)),
335 Basis::Profile { runs: peers_runs },
336 ),
337 (None, true) => (
339 self.with_margin(peers.last().copied().unwrap_or(0)),
340 Basis::ProfileMax { runs: peers_runs },
341 ),
342 _ => (cap, Basis::Cap),
343 };
344 Prediction {
345 memory: memory.min(cap),
346 basis,
347 }
348 }
349 fn with_margin(&self, peak: u64) -> u64 {
351 let memory = peak.saturating_add(peak.saturating_mul(u64::from(self.margin)) / 100);
352 memory
353 .div_ceil(GRANULE)
354 .saturating_mul(GRANULE)
355 .max(GRANULE)
356 }
357}
358
359#[derive(Debug, Clone, Copy, PartialEq, Eq)]
361pub enum Policy {
362 Caps,
364 Measured,
368}
369
370#[derive(Debug, Clone, Copy, PartialEq, Eq)]
372pub enum Barriers {
373 On,
375 Strict,
377 Off,
379}
380
381#[derive(Debug, Clone, Copy, PartialEq, Eq)]
383pub enum Arrivals {
384 AsQueued,
386 AfterNeeds,
390}
391
392#[derive(Debug, Clone, Copy)]
394pub struct Replaying<'known> {
395 pub barriers: Barriers,
397 pub arrivals: Arrivals,
399 pub known: Option<&'known History>,
402 pub trace: Option<&'known Trace>,
405 pub most_credit: u64,
407 pub host_hold: u64,
410 pub credit_room: CreditRoom,
412 pub band: Band,
414}
415
416#[derive(Debug, Clone, Copy, PartialEq, Eq)]
418pub enum Band {
419 NoWaiterFits,
421 AnyWaiter,
423}
424
425#[derive(Debug, Clone, Copy, PartialEq, Eq)]
427pub enum CreditRoom {
428 Counted,
430 LeftOut,
432}
433
434impl From<Barriers> for Replaying<'_> {
435 fn from(barriers: Barriers) -> Self {
436 Replaying {
437 barriers,
438 arrivals: Arrivals::AsQueued,
439 known: None,
440 trace: None,
441 most_credit: 0,
442 host_hold: u64::MAX,
443 credit_room: CreditRoom::Counted,
444 band: Band::NoWaiterFits,
445 }
446 }
447}
448
449#[derive(Debug, Clone, Default, PartialEq, Eq)]
451pub struct PoolReplay {
452 pub waits: Vec<u64>,
454 pub never_started: u64,
456}
457
458impl PoolReplay {
459 pub fn wait(&self) -> Spread {
461 spread(self.waits.clone())
462 }
463}
464
465#[derive(Debug, Clone, Default, PartialEq, Eq)]
467pub struct RunReplay {
468 pub took: u64,
470 pub profiles: BTreeSet<String>,
472}
473
474type RunKey = (String, u64, u32);
476
477#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
479pub struct Backfilled {
480 pub jobs: u64,
482 pub overran: u64,
484 pub most_overrun: u64,
486}
487
488#[derive(Debug, Clone, PartialEq, Eq)]
490pub struct Replay {
491 pub jobs: u64,
493 pub never_started: u64,
495 pub wait: Spread,
497 pub mean_wait: u64,
499 pub most_running: u64,
501 pub worst_overlap: u64,
506 pub makespan: u64,
508 pub under_predicted: u64,
510 pub held_back: u64,
512 pub cpu_held: u64,
514 pub worst_cpu: u64,
516 pub pools: BTreeMap<Pool, PoolReplay>,
518 pub charged: u128,
520 pub capacity: u128,
522 pub barrier_for: u64,
524 pub withheld: u128,
527 pub runs: Vec<RunReplay>,
529 pub backfilled: Backfilled,
531 pub slice_waited: u64,
533 pub host_waited: u64,
535 pub hazard: Hazard,
537}
538
539struct Running<'run> {
541 run: &'run Ran,
542 job: u64,
544 profile: &'run str,
545 started: u64,
547 ends: u64,
548 backfilled: Option<u64>,
550 reserved: u64,
551 peak: u64,
552 cpu: u64,
554 key: Key,
556 basis: Basis,
558 starting: u64,
560 trace: Option<&'run RunTrace>,
562}
563
564pub fn simulate<'known>(
589 config: &Config,
590 memory_max: Option<u64>,
591 cpu_budget: Option<u64>,
592 jobs: &[Ran],
593 policy: Policy,
594 slots: &BTreeMap<String, u32>,
595 how: impl Into<Replaying<'known>>,
596) -> Replay {
597 let Replaying {
598 barriers,
599 arrivals,
600 known,
601 trace,
602 most_credit,
603 host_hold,
604 credit_room,
605 band,
606 } = how.into();
607 let mirror = config.mirror_memory();
608 let budget = memory_max.map(|max| max.saturating_sub(mirror));
609 let queue = replayable(config, jobs);
610 let followers = match arrivals {
611 Arrivals::AsQueued => BTreeMap::new(),
612 Arrivals::AfterNeeds => followers(&queue),
613 };
614 let following: BTreeSet<u64> = followers
615 .values()
616 .flatten()
617 .map(|follower| queue[follower.at].job)
618 .collect();
619 let arriving = (0_usize..)
620 .zip(&queue)
621 .filter(|(_, queued)| !following.contains(&queued.job))
622 .map(|(at, queued)| (queued.run.queued_at, at))
623 .collect();
624 let mut predictor = Predictor::new(&config.sizing);
625 if let (Some(known), Some(first)) = (known, queue.first()) {
626 predictor.read_until(known, first.run.queued_at, |profile| {
627 config.profiles.get(profile).map(|limits| limits.memory.0)
628 });
629 }
630 let replayer = Replayer {
631 config,
632 budget,
633 cpu_budget,
634 policy,
635 slots,
636 predictor,
637 running: Vec::new(),
638 waits: Vec::new(),
639 most_running: 0,
640 worst_overlap: 0,
641 last_end: 0,
642 under_predicted: 0,
643 held_back: 0,
644 cpu_held: 0,
645 worst_cpu: 0,
646 barriers,
647 pool_waits: BTreeMap::new(),
648 pools: BTreeMap::new(),
649 barrier: None,
650 backfill: None,
651 usual: BTreeMap::new(),
652 arriving,
653 followers,
654 started: Vec::new(),
655 runs: BTreeMap::new(),
656 backfilled: Backfilled::default(),
657 moment: queue.first().map_or(0, |queued| queued.run.queued_at),
658 charged: 0,
659 capacity: 0,
660 barrier_for: 0,
661 withheld: 0,
662 memory_max,
663 mirror,
664 trace,
665 most_credit,
666 host_hold,
667 expects_credit: credit_room,
668 short: false,
669 next_plan: 0,
670 needs: RefCell::new(BTreeMap::new()),
671 held_for_slice: 0,
672 held_for_host: 0,
673 host_needs: Vec::new(),
674 band,
675 slice_waited: 0,
676 host_waited: 0,
677 hazard: Hazard::default(),
678 last_credit: 0,
679 cohorts: Vec::new(),
680 };
681 replayer.play(&queue)
682}
683
684fn replayable<'run>(config: &Config, jobs: &'run [Ran]) -> Vec<Queued<'run>> {
686 let mut queue: Vec<Queued<'_>> = (0_u64..)
687 .zip(jobs)
688 .filter(|(_, run)| config.profiles.contains_key(&run.profile))
689 .filter(|(_, run)| matches!((run.started_at, run.finished_at), (Some(start), Some(end)) if end >= start))
690 .map(|(job, run)| Queued {
691 job,
692 run,
693 arrived: run.queued_at,
694 })
695 .collect();
696 queue.sort_by_key(|queued| queued.run.queued_at);
697 queue
698}
699
700#[derive(Clone, Copy)]
702struct Queued<'run> {
703 job: u64,
705 run: &'run Ran,
706 arrived: u64,
708}
709
710#[derive(Clone, Copy)]
712struct Follower {
713 at: usize,
715 gap: u64,
717}
718
719fn followers(queue: &[Queued<'_>]) -> BTreeMap<u64, Vec<Follower>> {
723 let mut attempts: BTreeMap<RunKey, Vec<usize>> = BTreeMap::new();
724 for (at, queued) in queue.iter().enumerate() {
725 attempts.entry(run_key(queued.run)).or_default().push(at);
726 }
727 let mut followers: BTreeMap<u64, Vec<Follower>> = BTreeMap::new();
728 for attempt in attempts.values() {
729 for &at in attempt {
730 let queued_at = queue[at].run.queued_at;
731 let followed = attempt
732 .iter()
733 .map(|other| &queue[*other])
734 .filter(|other| other.run.queued_at < queued_at)
735 .filter_map(|other| Some((other.run.finished_at?, other.job)))
736 .filter(|(ended, _)| *ended <= queued_at)
737 .max();
738 if let Some((ended, job)) = followed {
739 let gap = queued_at - ended;
740 followers.entry(job).or_default().push(Follower { at, gap });
741 }
742 }
743 }
744 followers
745}
746
747fn run_key(run: &Ran) -> RunKey {
749 (run.repository.clone(), run.run_id, run.run_attempt)
750}
751
752struct RunSpan {
754 first_arrival: u64,
755 last_end: u64,
756 profiles: BTreeSet<String>,
757}
758
759impl RunSpan {
760 fn replay(self) -> RunReplay {
761 RunReplay {
762 took: self.last_end.saturating_sub(self.first_arrival) / 1000,
763 profiles: self.profiles,
764 }
765 }
766}
767
768fn pool_of(run: &Ran) -> Pool {
770 Pool {
771 repository: run.repository.clone(),
772 profile: run.profile.clone(),
773 }
774}
775
776struct Admitted {
778 reserved: u64,
779 starting: u64,
781 basis: Basis,
783 peak: u64,
784 cpu: u64,
786}
787
788fn same_job(one: &Ran, other: &Ran) -> bool {
791 one.name == other.name && one.repository == other.repository && one.workflow == other.workflow
792}
793
794struct Starting {
796 memory: u64,
798 reserved: u64,
800 basis: Basis,
802 cpu: u64,
804}
805
806enum Refused {
808 Slot,
810 Budget(Short),
812 Host(Short),
814 HighWater(Short),
816}
817
818struct Replayer<'run> {
820 config: &'run Config,
821 budget: Option<u64>,
822 cpu_budget: Option<u64>,
823 policy: Policy,
824 slots: &'run BTreeMap<String, u32>,
825 predictor: Predictor,
826 running: Vec<Running<'run>>,
827 waits: Vec<u64>,
828 most_running: u64,
829 worst_overlap: u64,
830 last_end: u64,
831 under_predicted: u64,
832 held_back: u64,
833 cpu_held: u64,
834 worst_cpu: u64,
835 barriers: Barriers,
836 pool_waits: BTreeMap<Pool, Waits>,
838 pools: BTreeMap<Pool, PoolReplay>,
839 barrier: Option<Barrier>,
841 backfill: Option<Backfill<'run>>,
843 usual: BTreeMap<Pool, Option<Duration>>,
845 arriving: BTreeSet<(u64, usize)>,
847 followers: BTreeMap<u64, Vec<Follower>>,
849 started: Vec<u64>,
851 runs: BTreeMap<RunKey, RunSpan>,
852 backfilled: Backfilled,
853 moment: u64,
855 charged: u128,
856 capacity: u128,
857 barrier_for: u64,
858 withheld: u128,
859 memory_max: Option<u64>,
860 mirror: u64,
861 trace: Option<&'run Trace>,
862 most_credit: u64,
863 host_hold: u64,
864 expects_credit: CreditRoom,
865 short: bool,
867 next_plan: u64,
869 needs: RefCell<BTreeMap<Pool, Need>>,
871 held_for_slice: u64,
873 held_for_host: u64,
875 host_needs: Vec<u64>,
877 band: Band,
878 slice_waited: u64,
879 host_waited: u64,
880 hazard: Hazard,
881 last_credit: u64,
883 cohorts: Vec<Cohort>,
885}
886
887#[derive(Clone, Copy)]
889struct Need {
890 memory: u64,
891 cpu: u64,
893}
894
895struct Cohort {
897 jobs: Vec<u64>,
899 count: u64,
901}
902
903impl<'run> Replayer<'run> {
904 fn play(mut self, queue: &[Queued<'run>]) -> Replay {
906 let mut waiting: Vec<Queued<'_>> = Vec::new();
907 loop {
908 let arrival = self.arriving.first().map(|(arrives, _)| *arrives);
909 let end = self.running.iter().map(|running| running.ends).min();
910 let event = [arrival, end, self.next_limit()]
911 .into_iter()
912 .flatten()
913 .min();
914 let Some(now) = [event, self.next_look(&waiting)]
915 .into_iter()
916 .flatten()
917 .min()
918 else {
919 break;
920 };
921 self.account(now);
922 self.finish(now);
923 if event != Some(now) && !self.plans_at(now) {
924 continue;
925 }
926 self.rereserve(now);
927 while let Some(&(arrived, at)) =
928 self.arriving.first().filter(|(arrives, _)| *arrives <= now)
929 {
930 self.arriving.remove(&(arrived, at));
931 waiting.push(Queued {
932 arrived,
933 ..queue[at]
934 });
935 }
936 waiting.sort_by_key(|queued| (queued.arrived, queued.job));
939 self.pass(&mut waiting, now);
940 self.note_worst(self.mirror);
941 }
942 self.replay(queue)
943 }
944
945 fn next_look(&self, waiting: &[Queued<'run>]) -> Option<u64> {
948 let trace = self.trace?;
949 let waits = !waiting.is_empty() && self.moment < trace.ends();
950 (!self.running.is_empty() || waits).then_some(self.moment + STEP)
951 }
952
953 fn plans_at(&mut self, now: u64) -> bool {
955 if now < self.next_plan {
956 return false;
957 }
958 let poll = u64::try_from(self.config.host.poll_interval.as_millis()).unwrap_or(u64::MAX);
959 self.next_plan = now.saturating_add(poll);
960 true
961 }
962
963 fn next_limit(&self) -> Option<u64> {
965 self.pool_waits
966 .values()
967 .flat_map(Waits::deadlines)
968 .map(time::ms)
969 .filter(|limit| *limit > self.moment)
970 .min()
971 }
972
973 fn account(&mut self, now: u64) {
975 let span = now.saturating_sub(self.moment);
976 self.look(span);
977 let taken = self.taken();
978 self.charged += u128::from(taken) * u128::from(span);
979 if let Some(budget) = self.budget {
980 self.capacity += u128::from(budget) * u128::from(span);
981 if self.barrier.is_some() {
982 self.withheld += u128::from(budget.saturating_sub(taken)) * u128::from(span);
983 }
984 }
985 if self.barrier.is_some() {
986 self.barrier_for += span;
987 }
988 self.moment = now;
989 }
990
991 fn look(&mut self, span: u64) {
994 let Some(trace) = self.trace else {
995 return;
996 };
997 self.slice_waited += self.held_for_slice * span;
998 self.host_waited += self.held_for_host * span;
999 if self.running.is_empty() {
1000 self.last_credit = 0;
1001 return;
1002 }
1003 let slice = self.slice();
1004 let host_slice = self.used_now() + trace.host_overhead;
1005 let hazard = &mut self.hazard;
1006 hazard.slice_peak = hazard.slice_peak.max(slice);
1007 hazard.active += span;
1008 if let Some(max) = self.memory_max {
1009 let mark = max / 100 * HIGH_WATER;
1010 hazard.over_mark.note(slice.checked_sub(mark), span);
1011 hazard.over_max.note(slice.checked_sub(max), span);
1012 }
1013 if let Some(outside) = trace.outside_at(self.moment) {
1014 let available = trace
1015 .total
1016 .saturating_sub(outside)
1017 .saturating_sub(host_slice);
1018 hazard.under_throttling += span * u64::from(available < THROTTLES_UNDER);
1019 hazard.under_oomd += span * u64::from(available < OOMD_UNDER);
1020 hazard.in_band += span * u64::from(self.short);
1021 hazard.lowest_available = Some(
1022 hazard
1023 .lowest_available
1024 .map_or(available, |lowest| lowest.min(available)),
1025 );
1026 }
1027 let count = self.count();
1028 let hazard = &mut self.hazard;
1029 hazard.credit += u128::from(count.credit) * u128::from(span);
1030 hazard.most_credit = hazard.most_credit.max(count.credit);
1031 if count.credit < self.last_credit {
1032 hazard.credit_falls += 1;
1033 let before = pooled::Count {
1034 credit: self.last_credit,
1035 ..count
1036 };
1037 self.hazard.overdrawn += u64::from(self.overdrawn(before, count));
1038 }
1039 self.last_credit = count.credit;
1040 self.note_unfunded(span);
1041 }
1042
1043 fn overdrawn(&self, before: pooled::Count, now: pooled::Count) -> bool {
1046 let max = self.memory_max.unwrap_or(u64::MAX);
1047 let host = self
1048 .host_memory()
1049 .map_or(u64::MAX, |memory| host::limit(&memory, self.short));
1050 (now.pooled() > max && before.pooled() <= max)
1051 || (self.hosted(now) > host && self.hosted(before) <= host)
1052 }
1053
1054 fn hosted(&self, count: pooled::Count) -> u64 {
1056 count.plain - count.credit.saturating_sub(self.host_hold)
1057 }
1058
1059 fn note_unfunded(&mut self, span: u64) {
1061 let used: BTreeMap<u64, u64> = self
1062 .running
1063 .iter()
1064 .map(|running| (running.job, self.used(running).unwrap_or(0)))
1065 .collect();
1066 self.cohorts
1067 .retain(|cohort| cohort.jobs.iter().any(|job| used.contains_key(job)));
1068 let all: u64 = used.values().sum();
1069 let lowest = self.cohorts.iter().map(|cohort| cohort.count).min();
1070 let mut worst = None;
1071 if lowest.is_some_and(|lowest| all > lowest) {
1073 for cohort in &self.cohorts {
1074 let of_cohort: u64 = cohort.jobs.iter().filter_map(|job| used.get(job)).sum();
1075 worst = worst.max(of_cohort.checked_sub(cohort.count).filter(|past| *past > 0));
1076 }
1077 }
1078 self.hazard.unfunded.note(worst, span);
1079 }
1080
1081 fn used(&self, running: &Running<'_>) -> Option<u64> {
1083 match running
1084 .trace?
1085 .at(self.moment.saturating_sub(running.started))
1086 {
1087 Reading::Used(memory) => Some(memory),
1088 Reading::NotYet | Reading::Stale => None,
1089 }
1090 }
1091
1092 fn slice(&self) -> u64 {
1094 self.used_now() + self.trace.map_or(0, |trace| trace.overhead)
1095 }
1096
1097 fn slice_read(&self) -> u64 {
1099 self.used_now() + self.trace.map_or(0, |trace| trace.guard_overhead)
1100 }
1101
1102 fn used_now(&self) -> u64 {
1104 self.running
1105 .iter()
1106 .map(|running| self.used(running).unwrap_or(0))
1107 .sum()
1108 }
1109
1110 fn host_memory(&self) -> Option<HostMemory> {
1113 let trace = self.trace.filter(|trace| trace.total > 0)?;
1114 let outside = trace.outside_at(self.moment)?;
1115 let slice = self.used_now() + trace.host_overhead;
1116 Some(HostMemory {
1117 at: self.moment / 1000,
1118 total: trace.total,
1119 available: trace.total.saturating_sub(outside).saturating_sub(slice),
1120 slice,
1121 some: None,
1122 full: None,
1123 holders: Vec::new(),
1124 ceiling: None,
1125 swap: None,
1126 })
1127 }
1128
1129 fn count(&self) -> pooled::Count {
1131 let held: Vec<pooled::Runner<'_>> = self
1132 .running
1133 .iter()
1134 .map(|running| {
1135 let ran = self.moment.saturating_sub(running.started);
1136 let named = running.trace.is_none_or(|trace| ran >= trace.named_after);
1137 pooled::Runner {
1138 key: named.then_some(&running.key),
1139 takes: self.charge(running),
1140 used: self
1141 .used(running)
1142 .filter(|_| running.run.measure == Measure::WithoutPageCache),
1143 ran: Some(Duration::from_millis(ran)),
1144 basis: Some(running.basis),
1145 }
1146 })
1147 .collect();
1148 let host = self.host_memory();
1149 pooled::count(&pooled::Snapshot {
1150 runners: &held,
1151 committed: self.mirror,
1152 slice: self.memory_max.map(|memory_max| pooled::Slice {
1153 memory: self.slice_read(),
1154 memory_max,
1155 }),
1156 host: host.map(|memory| {
1157 host::pooling(
1158 &memory,
1159 host::Remembered {
1160 short: self.short,
1161 stalled: false,
1162 },
1163 )
1164 }),
1165 most: if self.trace.is_some() && self.policy == Policy::Measured {
1166 self.most_credit
1167 } else {
1168 0
1169 },
1170 })
1171 }
1172
1173 fn host_left(&self) -> Option<i64> {
1175 let memory = self.host_memory()?;
1176 let limit = host::limit(&memory, self.short && !self.running.is_empty());
1177 Some(host::left(limit, self.hosted(self.count()), false))
1178 }
1179
1180 fn pass(&mut self, waiting: &mut Vec<Queued<'run>>, now: u64) {
1184 let at = instant(now);
1185 self.barrier = None;
1186 self.backfill = None;
1187 self.usual.clear();
1188 self.needs.borrow_mut().clear();
1189 self.held_for_slice = 0;
1190 self.held_for_host = 0;
1191 self.host_needs.clear();
1192 let listed = waiting.clone();
1193 let mut index = 0;
1194 while let Some(queued) = waiting.get(index).copied() {
1195 match self.admits(queued, waiting, now) {
1196 Ok(admitted) if self.barrier.is_none() => {
1197 waiting.remove(index);
1198 self.start(queued, &admitted, None, now);
1199 }
1200 Ok(admitted) => match self.passes(queued, &listed) {
1201 Some(usual) => {
1202 waiting.remove(index);
1203 self.start(queued, &admitted, Some(usual), now);
1204 }
1205 None => index += 1,
1206 },
1207 Err(Refused::Slot) => index += 1,
1208 Err(Refused::Budget(short)) => {
1209 if self.barrier.is_none() && short.scarce == Scarce::Cpu {
1210 self.cpu_held += 1;
1211 }
1212 self.held_for_slice += u64::from(short.scarce == Scarce::Memory);
1213 let first = self.barrier.is_none();
1214 self.hold(queued.run, short, at);
1215 if first && self.barrier.is_some() {
1216 self.backfill_behind(queued.run, &waiting[..index], &listed, now);
1217 }
1218 index += 1;
1219 }
1220 Err(Refused::Host(short)) => {
1221 self.held_for_host += 1;
1222 if self.barrier.is_none() {
1224 self.host_needs.push(short.memory);
1225 }
1226 let first = self.barrier.is_none();
1227 self.hold(queued.run, short, at);
1228 if first && self.barrier.is_some() {
1229 self.backfill_behind(queued.run, &waiting[..index], &listed, now);
1230 }
1231 index += 1;
1232 }
1233 Err(Refused::HighWater(short)) => {
1234 if self.barrier.is_none() {
1235 self.held_back += 1;
1236 }
1237 self.hold(queued.run, short, at);
1238 index += 1;
1239 }
1240 }
1241 }
1242 self.short = self.band_stands();
1243 self.settle_waits(waiting);
1244 }
1245
1246 fn band_stands(&self) -> bool {
1248 match self.band {
1249 Band::AnyWaiter => self.held_for_host > 0,
1250 Band::NoWaiterFits => self.host_memory().is_some_and(|memory| {
1251 let reserved = self.hosted(self.count());
1252 host::short(&memory, reserved, false, self.host_needs.iter().copied())
1253 }),
1254 }
1255 }
1256
1257 fn settle_waits(&mut self, waiting: &[Queued<'run>]) {
1260 let queued: BTreeSet<Pool> = waiting.iter().map(|queued| pool_of(queued.run)).collect();
1261 self.pool_waits.retain(|pool, waits| {
1262 if !queued.contains(pool) {
1263 waits.emptied();
1264 }
1265 !waits.is_empty()
1266 });
1267 }
1268
1269 fn hold(&mut self, run: &'run Ran, short: Short, at: SystemTime) {
1273 if self.barriers == Barriers::Off {
1274 return;
1275 }
1276 let drained = (!self.at_high_water()).then_some(self.drained());
1277 let waits = self.pool_waits.entry(pool_of(run)).or_default();
1278 if drained.is_some() {
1279 waits.note(short.scarce, short.job, at);
1280 }
1281 if self.barrier.is_none() {
1282 self.barrier = Barrier::of(short, waits, drained, at);
1283 if self.barrier.is_some() {
1284 waits.own(short.job);
1285 }
1286 }
1287 }
1288
1289 fn backfill_behind(
1292 &mut self,
1293 run: &'run Ran,
1294 older: &[Queued<'run>],
1295 listed: &[Queued<'run>],
1296 now: u64,
1297 ) {
1298 let Some(barrier) = self.barrier.filter(|_| self.barriers == Barriers::On) else {
1299 return;
1300 };
1301 let mut pools = BTreeSet::new();
1302 let older: Vec<Older<'_>> = older
1303 .iter()
1304 .filter(|queued| self.config.profiles.contains_key(&queued.run.profile))
1305 .filter(|queued| pools.insert(pool_of(queued.run)))
1306 .map(|queued| {
1307 let starting = self.starting(*queued, listed, now);
1308 Older {
1309 profile: &queued.run.profile,
1310 free_slot: self.free_slots(&queued.run.profile) > 0,
1311 memory: starting.memory,
1312 cpu: starting.cpu,
1313 }
1314 })
1315 .collect();
1316 let runners = self.runners();
1317 let around = Around {
1318 left: self.left(),
1319 credit_room: self.credit_room(),
1320 drained: self.drained(),
1321 runners: &runners,
1322 older: &older,
1323 };
1324 self.backfill = Backfill::behind(barrier, &run.profile, around, instant(now));
1325 }
1326
1327 fn credit_room(&self) -> u64 {
1329 if self.trace.is_none()
1330 || self.policy != Policy::Measured
1331 || self.expects_credit == CreditRoom::LeftOut
1332 {
1333 return 0;
1334 }
1335 self.most_credit.saturating_sub(self.count().credit)
1336 }
1337
1338 fn drained(&self) -> Drained {
1340 Drained {
1341 memory: self.budget.map(signed),
1342 cpu: self.cpu_budget.map(signed),
1343 host: self.host_memory().map(|memory| {
1344 let limit = host::limit(&memory, !self.running.is_empty());
1345 signed(limit).saturating_sub(signed(self.mirror))
1346 }),
1347 host_plain: self.host_memory().map(|memory| {
1348 signed(host::limit(&memory, false)).saturating_sub(signed(self.mirror))
1349 }),
1350 }
1351 }
1352
1353 fn free_slots(&self, profile: &str) -> usize {
1355 let limits = &self.config.profiles[profile];
1356 let slots = self.slots.get(profile).copied().unwrap_or(limits.slots);
1357 let in_profile = self
1358 .running
1359 .iter()
1360 .filter(|running| running.profile == profile)
1361 .count();
1362 (slots as usize).saturating_sub(in_profile)
1363 }
1364
1365 fn passes(&mut self, queued: Queued<'run>, listed: &[Queued<'run>]) -> Option<Duration> {
1368 let run = queued.run;
1369 self.backfill.as_ref()?;
1370 let predictor = &self.predictor;
1371 let usual = *self.usual.entry(pool_of(run)).or_insert_with(|| {
1372 let keys = listed
1373 .iter()
1374 .filter(|other| other.run.repository == run.repository)
1375 .filter(|other| other.run.profile == run.profile)
1376 .map(|other| Key::of(other.run));
1377 predictor.longest_usual(keys, &run.profile)
1378 });
1379 let candidate = Candidate {
1380 profile: &run.profile,
1381 free_slots: self.free_slots(&run.profile),
1382 usual,
1383 caps: self.caps(&run.profile),
1384 };
1385 let backfill = self.backfill.as_mut()?;
1386 backfill.admits(candidate).then_some(usual).flatten()
1387 }
1388
1389 fn left(&self) -> Left {
1391 let cpu: u64 = self.running.iter().map(|running| running.cpu).sum();
1392 let left = |budget: u64, taken: u64| signed(budget).saturating_sub(signed(taken));
1393 Left {
1394 memory: self.budget.map(|budget| left(budget, self.taken())),
1395 cpu: self.cpu_budget.map(|budget| left(budget, cpu)),
1396 host: self.host_left(),
1397 }
1398 }
1399
1400 fn caps(&self, profile: &str) -> Caps {
1402 let limits = &self.config.profiles[profile];
1403 let cpu = u64::from(limits.cpus).saturating_mul(1000);
1404 Caps {
1405 memory: limits.memory.0,
1406 cpu: self.cpu_budget.map_or(cpu, |budget| cpu.min(budget)),
1407 }
1408 }
1409
1410 fn note_worst(&mut self, mirror: u64) {
1412 self.most_running = self.most_running.max(self.running.len() as u64);
1413 let peaks: u64 = self.running.iter().map(|running| running.peak).sum();
1414 self.worst_overlap = self.worst_overlap.max(peaks + mirror);
1415 let cpu: u64 = self
1416 .running
1417 .iter()
1418 .map(|running| running.run.cpu_average.unwrap_or(0))
1419 .sum();
1420 self.worst_cpu = self.worst_cpu.max(cpu);
1421 }
1422
1423 fn replay(mut self, queue: &[Queued<'run>]) -> Replay {
1425 let started: BTreeSet<u64> = self.started.iter().copied().collect();
1426 let never_started: Vec<&Queued<'_>> = queue
1427 .iter()
1428 .filter(|queued| !started.contains(&queued.job))
1429 .collect();
1430 for queued in &never_started {
1431 self.pools
1432 .entry(pool_of(queued.run))
1433 .or_default()
1434 .never_started += 1;
1435 }
1436 let waits = self.waits;
1437 let first = queue.first().map_or(0, |queued| queued.run.queued_at);
1438 Replay {
1439 jobs: queue.len() as u64,
1440 never_started: never_started.len() as u64,
1441 mean_wait: waits.iter().sum::<u64>() / (waits.len() as u64).max(1),
1442 wait: spread(waits),
1443 most_running: self.most_running,
1444 worst_overlap: self.worst_overlap,
1445 makespan: self.last_end.saturating_sub(first) / 1000,
1446 under_predicted: self.under_predicted,
1447 held_back: self.held_back,
1448 cpu_held: self.cpu_held,
1449 worst_cpu: self.worst_cpu,
1450 pools: self.pools,
1451 charged: self.charged,
1452 capacity: self.capacity,
1453 barrier_for: self.barrier_for,
1454 withheld: self.withheld,
1455 runs: self.runs.into_values().map(RunSpan::replay).collect(),
1456 backfilled: self.backfilled,
1457 slice_waited: self.slice_waited,
1458 host_waited: self.host_waited,
1459 hazard: self.hazard,
1460 }
1461 }
1462
1463 fn runners(&self) -> Vec<Runner<'_>> {
1465 self.running
1466 .iter()
1467 .map(|running| Runner {
1468 profile: running.profile,
1469 started_at: instant(running.started),
1470 usual: self.predictor.usual(&Key::of(running.run), running.profile),
1471 memory: self.charge(running),
1472 cpu: running.cpu,
1473 caps: self.caps(running.profile),
1474 })
1475 .collect()
1476 }
1477
1478 fn at_high_water(&self) -> bool {
1481 if self.trace.is_some() {
1482 return self.policy == Policy::Measured
1483 && self.memory_max.is_some_and(|max| {
1484 self.slice_read().saturating_mul(100) >= max.saturating_mul(HIGH_WATER)
1485 });
1486 }
1487 let peaks: u64 = self.running.iter().map(|running| running.peak).sum();
1488 self.policy == Policy::Measured
1489 && self.budget.is_some_and(|budget| {
1490 peaks.saturating_mul(100) >= budget.saturating_mul(HIGH_WATER)
1491 })
1492 }
1493
1494 fn finish(&mut self, now: u64) {
1497 let (ended, running): (Vec<_>, Vec<_>) = std::mem::take(&mut self.running)
1498 .into_iter()
1499 .partition(|running| running.ends <= now);
1500 self.running = running;
1501 let mut ended = ended;
1502 ended.sort_by_key(|ended| ended.ends);
1503 for ended in ended {
1504 let cap = ended
1506 .run
1507 .memory_cap
1508 .unwrap_or(self.config.profiles[ended.profile].memory.0);
1509 self.under_predicted += u64::from(ended.peak > ended.reserved);
1510 let reserved = (self.policy == Policy::Measured).then_some(ended.reserved);
1511 let run = Ran {
1512 reserved,
1513 ..ended.run.clone()
1514 };
1515 self.predictor.learn(&run, ended.profile, cap, ended.ends);
1516 self.last_end = self.last_end.max(ended.ends);
1517 if let Some(by) = ended.backfilled {
1518 let overrun = ended.ends.saturating_sub(by);
1519 self.backfilled.overran += u64::from(overrun > 0);
1520 self.backfilled.most_overrun = self.backfilled.most_overrun.max(overrun / 1000);
1521 }
1522 let span = self.runs.get_mut(&run_key(ended.run));
1523 if let Some(span) = span {
1524 span.last_end = span.last_end.max(ended.ends);
1525 }
1526 for follower in self.followers.remove(&ended.job).unwrap_or_default() {
1527 self.arriving
1528 .insert((ended.ends + follower.gap, follower.at));
1529 }
1530 }
1531 }
1532
1533 fn rereserve(&mut self, now: u64) {
1537 if self.policy != Policy::Measured {
1538 return;
1539 }
1540 let cpus: Vec<u64> = self
1541 .running
1542 .iter()
1543 .map(|running| self.cpu(&Key::of(running.run), running.profile))
1544 .collect();
1545 let mut seen = BTreeSet::new();
1546 for (running, cpu) in self.running.iter_mut().zip(cpus) {
1547 let key = Key::of(running.run);
1548 let copies = if seen.insert(key.clone()) {
1549 Copies::Alone
1550 } else {
1551 Copies::Several
1552 };
1553 let limits = &self.config.profiles[running.profile];
1554 let prediction =
1555 self.predictor
1556 .predict(&key, running.profile, limits.memory.0, now, copies);
1557 running.reserved = prediction.memory;
1558 running.basis = prediction.basis;
1559 running.cpu = cpu;
1560 }
1561 }
1562
1563 fn cpu(&self, key: &Key, profile: &str) -> u64 {
1566 let cap = u64::from(self.config.profiles[profile].cpus).saturating_mul(1000);
1567 let cpu = match self.policy {
1568 Policy::Caps => cap,
1569 Policy::Measured => self.predictor.predict_cpu(key, profile, cap).cpu,
1570 };
1571 self.cpu_budget.map_or(cpu, |budget| cpu.min(budget))
1572 }
1573
1574 fn taken(&self) -> u64 {
1577 self.count().pooled().saturating_sub(self.mirror)
1578 }
1579
1580 fn charge(&self, running: &Running<'_>) -> u64 {
1584 let Some(trace) = running.trace.filter(|_| self.policy == Policy::Measured) else {
1585 return match self.policy {
1586 Policy::Caps => running.reserved,
1587 Policy::Measured => running.reserved.max(running.peak),
1588 };
1589 };
1590 let ran = self.moment.saturating_sub(running.started);
1591 let reserved = if ran < trace.named_after {
1592 running.starting.max(running.reserved)
1593 } else {
1594 running.reserved
1595 };
1596 match trace.at(ran) {
1597 Reading::NotYet => reserved,
1598 Reading::Used(memory) => reserved.max(memory),
1599 Reading::Stale => self.config.profiles[running.profile].memory.0,
1600 }
1601 }
1602
1603 fn admits(
1606 &self,
1607 queued: Queued<'run>,
1608 waiting: &[Queued<'run>],
1609 now: u64,
1610 ) -> Result<Admitted, Refused> {
1611 let run = queued.run;
1612 let Some(limits) = self.config.profiles.get(&run.profile) else {
1613 return Err(Refused::Slot);
1614 };
1615 if self.free_slots(&run.profile) == 0 {
1616 return Err(Refused::Slot);
1617 }
1618 let starting = self.starting(queued, waiting, now);
1619 let short = |scarce, held| Short {
1620 job: queued.job,
1621 scarce,
1622 held,
1623 memory: starting.memory,
1624 cpu: starting.cpu,
1625 };
1626 if let Some(budget) = self.budget {
1627 if self.taken() + starting.memory > budget {
1628 return Err(Refused::Budget(short(Scarce::Memory, Held::ByBudget)));
1629 }
1630 if self.at_high_water() {
1631 return Err(Refused::HighWater(short(Scarce::Memory, Held::ByBudget)));
1632 }
1633 }
1634 if self
1635 .host_left()
1636 .is_some_and(|left| left < signed(starting.memory))
1637 {
1638 return Err(Refused::Host(short(Scarce::Memory, Held::ByHost)));
1639 }
1640 if let Some(cpu_budget) = self.cpu_budget {
1641 let taken: u64 = self.running.iter().map(|running| running.cpu).sum();
1642 if taken + starting.cpu > cpu_budget {
1643 return Err(Refused::Budget(short(Scarce::Cpu, Held::ByBudget)));
1644 }
1645 }
1646 Ok(Admitted {
1647 reserved: starting.reserved,
1648 starting: starting.memory,
1649 basis: starting.basis,
1650 peak: run.memory_peak.min(limits.memory.0),
1652 cpu: self.cpu(&Key::of(run), &run.profile),
1653 })
1654 }
1655
1656 fn starting(&self, queued: Queued<'run>, waiting: &[Queued<'run>], now: u64) -> Starting {
1659 let run = queued.run;
1660 let profile = run.profile.as_str();
1661 let cap = self.config.profiles[profile].memory.0;
1662 let running = |job: &Ran| {
1663 self.running
1664 .iter()
1665 .any(|running| same_job(running.run, job))
1666 };
1667 let predicted = |job: &Ran| {
1669 let key = Key::of(job);
1670 let waiting = waiting
1671 .iter()
1672 .filter(|other| same_job(other.run, job))
1673 .count();
1674 let copies = if waiting > 1 || running(job) {
1675 Copies::Several
1676 } else {
1677 Copies::Alone
1678 };
1679 self.predictor
1680 .predict(&key, profile, cap, now, copies)
1681 .memory
1682 };
1683 let started = || {
1685 let key = Key::of(run);
1686 let copies = if running(run) {
1687 Copies::Several
1688 } else {
1689 Copies::Alone
1690 };
1691 self.predictor.predict(&key, profile, cap, now, copies)
1692 };
1693 let pool = || {
1694 waiting
1695 .iter()
1696 .map(|other| other.run)
1697 .filter(|job| job.repository == run.repository && job.profile == run.profile)
1698 };
1699 let own = started();
1700 let need = || Need {
1701 memory: pool().map(predicted).max().unwrap_or(0),
1702 cpu: pool()
1704 .map(|job| self.cpu(&Key::of(job), profile))
1705 .max()
1706 .unwrap_or(0),
1707 };
1708 let need = if self.trace.is_some() {
1709 *self
1710 .needs
1711 .borrow_mut()
1712 .entry(pool_of(run))
1713 .or_insert_with(need)
1714 } else {
1715 need()
1716 };
1717 let (memory, reserved, basis) = match self.policy {
1718 Policy::Caps => (cap, cap, Basis::Cap),
1719 Policy::Measured => (need.memory.max(own.memory), own.memory, own.basis),
1720 };
1721 Starting {
1722 memory,
1723 reserved,
1724 basis,
1725 cpu: need.cpu.max(self.cpu(&Key::of(run), profile)),
1726 }
1727 }
1728
1729 fn start(
1731 &mut self,
1732 queued: Queued<'run>,
1733 admitted: &Admitted,
1734 usual: Option<Duration>,
1735 now: u64,
1736 ) {
1737 let run = queued.run;
1738 let Some((profile, _)) = self.config.profiles.get_key_value(&run.profile) else {
1739 return;
1740 };
1741 let ran_for = run
1742 .finished_at
1743 .unwrap_or_default()
1744 .saturating_sub(run.started_at.unwrap_or_default());
1745 let waited = now.saturating_sub(queued.arrived) / 1000;
1746 let span = self.runs.entry(run_key(run)).or_insert(RunSpan {
1747 first_arrival: queued.arrived,
1748 last_end: now,
1749 profiles: BTreeSet::new(),
1750 });
1751 span.first_arrival = span.first_arrival.min(queued.arrived);
1752 span.profiles.insert(run.profile.clone());
1753 self.started.push(queued.job);
1754 self.backfilled.jobs += u64::from(usual.is_some());
1755 let pool = pool_of(run);
1756 if let Some(waits) = self.pool_waits.get_mut(&pool) {
1757 waits.started();
1758 }
1759 self.pools.entry(pool).or_default().waits.push(waited);
1760 self.waits.push(waited);
1761 self.running.push(Running {
1762 run,
1763 job: queued.job,
1764 profile,
1765 started: now,
1766 ends: now + ran_for,
1767 backfilled: usual.map(|usual| {
1768 now.saturating_add(u64::try_from(usual.as_millis()).unwrap_or(u64::MAX))
1769 }),
1770 reserved: admitted.reserved,
1771 peak: admitted.peak,
1772 cpu: admitted.cpu,
1773 key: Key::of(run),
1774 basis: admitted.basis,
1775 starting: admitted.starting,
1776 trace: self.trace.and_then(|trace| trace.runs.get(&RunId::of(run))),
1777 });
1778 self.needs.borrow_mut().clear();
1779 if self.trace.is_some() {
1780 self.cohorts.push(Cohort {
1781 jobs: self.running.iter().map(|running| running.job).collect(),
1782 count: self.taken(),
1783 });
1784 }
1785 }
1786}
1787
1788fn instant(ms: u64) -> SystemTime {
1790 SystemTime::UNIX_EPOCH + Duration::from_millis(ms)
1791}
1792
1793fn signed(amount: u64) -> i64 {
1795 i64::try_from(amount).unwrap_or(i64::MAX)
1796}
1797
1798#[cfg(test)]
1799mod tests;