1use std::collections::{BTreeMap, BTreeSet};
6use std::time::{Duration, SystemTime};
7
8use crate::admission::Key;
9use crate::api::Waiting;
10use crate::github::QueuedJob;
11
12pub mod engine;
13pub mod warm;
14
15pub const IDLE_TIMEOUT: Duration = Duration::from_secs(300);
18
19pub const CPU_PRIORITY_AFTER: Duration = Duration::from_secs(120);
22
23#[derive(Debug, Clone, Copy)]
25pub struct Hold {
26 pub until: SystemTime,
28 pub cause: crate::api::HoldCause,
30}
31
32#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
35pub struct Pool {
36 pub repository: String,
38 pub profile: String,
40}
41
42impl From<&crate::config::Repository> for Pool {
43 fn from(repository: &crate::config::Repository) -> Pool {
44 Pool {
45 repository: repository.name.clone(),
46 profile: repository.profile.clone(),
47 }
48 }
49}
50
51#[derive(Debug, Clone)]
54pub struct Repository {
55 pub name: String,
57 pub profile: String,
59 pub labels: Vec<String>,
61 pub paused: bool,
63 pub held: Option<Hold>,
65 pub queued: Vec<QueuedJob>,
67 pub runner_memory: Option<u64>,
70 pub runner_cpu: Option<u64>,
73 pub cpu_waiting_since: Option<SystemTime>,
75 pub warm: usize,
77}
78
79impl Repository {
80 pub fn pool(&self) -> Pool {
82 Pool {
83 repository: self.name.clone(),
84 profile: self.profile.clone(),
85 }
86 }
87
88 fn starved_of_cpu(&self, now: SystemTime) -> bool {
90 self.cpu_waiting_since
91 .and_then(|since| now.duration_since(since).ok())
92 .is_some_and(|waited| waited >= CPU_PRIORITY_AFTER)
93 }
94}
95
96#[derive(Debug, Clone)]
98pub struct Profile {
99 pub memory: u64,
101 pub cpus: u64,
104 pub preparing: Option<Preparing>,
106 pub upkeep_due: bool,
109 pub count: usize,
111 pub slots: Vec<Slot>,
113 pub ran: Vec<Option<Key>>,
116}
117
118#[derive(Debug, Clone, Copy, PartialEq, Eq)]
120pub enum Preparing {
121 Reseeding,
123 PullingImage,
125}
126
127#[derive(Debug, Clone, PartialEq, Eq)]
129pub enum Slot {
130 Free,
132 Runner(RunnerSlot),
134 Closed,
137}
138
139#[derive(Debug, Clone, PartialEq, Eq)]
141pub struct RunnerSlot {
142 pub repository: String,
144 pub busy: bool,
146 pub started_at: SystemTime,
148 pub memory: u64,
150 pub cpu: u64,
152}
153
154#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
156pub struct SlotRef {
157 pub profile: String,
159 pub index: usize,
161}
162
163#[derive(Debug, Clone, PartialEq, Eq)]
165pub enum Decision {
166 Start {
168 slot: SlotRef,
170 repository: String,
172 memory: u64,
174 cpu: u64,
176 warm: bool,
178 replacing: Vec<SlotRef>,
181 },
182 HeldForCpu {
185 repository: String,
187 profile: String,
189 },
190 Stop {
192 slot: SlotRef,
194 reason: StopReason,
196 },
197}
198
199#[derive(Debug, Clone, Copy, PartialEq, Eq)]
201pub enum StopReason {
202 Expired,
204 Room,
206 Upkeep,
208 Paused,
210 Closed,
212 Changed,
214 OverBudget,
216 Clean,
218 Shutdown,
220}
221
222impl StopReason {
223 pub fn as_str(self) -> &'static str {
225 match self {
226 StopReason::Expired => "expired",
227 StopReason::Room => "room",
228 StopReason::Upkeep => "upkeep",
229 StopReason::Paused => "paused",
230 StopReason::Closed => "closed",
231 StopReason::Changed => "changed",
232 StopReason::OverBudget => "over_budget",
233 StopReason::Clean => "clean",
234 StopReason::Shutdown => "shutdown",
235 }
236 }
237
238 pub fn words(self) -> &'static str {
240 match self {
241 StopReason::Expired => "no job came for it",
242 StopReason::Room => "a queued job takes its room",
243 StopReason::Upkeep => "its profile's upkeep waits for it",
244 StopReason::Paused => "its repository is paused",
245 StopReason::Closed => "its slot closed",
246 StopReason::Changed => "the config or runnerd changed its runners",
247 StopReason::OverBudget => "raised for a heavier job, it does not fit the budget",
248 StopReason::Clean => "a cache clean needs its volumes",
249 StopReason::Shutdown => "runnerd stops",
250 }
251 }
252}
253
254#[derive(Debug, Clone, Default, PartialEq, Eq)]
256pub struct Plan {
257 pub decisions: Vec<Decision>,
259 pub waiting: BTreeMap<u64, Waiting>,
263 pub warm: BTreeSet<SlotRef>,
265 pub slot_waiting: BTreeSet<u64>,
270}
271
272#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
274pub struct Budget {
275 pub memory: Option<i64>,
278 pub cpu: Option<i64>,
281 pub host: Option<i64>,
284 pub held: bool,
287}
288
289const GITHUB_HOSTED: &[&str] = &[
295 "ubuntu-slim",
296 "ubuntu-latest",
297 "ubuntu-26.04",
298 "ubuntu-24.04",
299 "ubuntu-22.04",
300 "ubuntu-26.04-arm",
301 "ubuntu-24.04-arm",
302 "ubuntu-22.04-arm",
303 "windows-latest",
304 "windows-2025",
305 "windows-2025-vs2026",
306 "windows-2022",
307 "windows-11-arm",
308 "windows-11-vs2026-arm",
309 "macos-latest",
310 "macos-26",
311 "macos-15",
312 "macos-14",
313 "macos-26-intel",
314 "macos-15-intel",
315 "xcode-27",
316 "macos-latest-large",
317 "macos-26-large",
318 "macos-15-large",
319 "macos-14-large",
320 "macos-latest-xlarge",
321 "macos-26-xlarge",
322 "macos-15-xlarge",
323 "macos-14-xlarge",
324 "xcode-27-xlarge",
325];
326
327fn hosted_by_github(job: &QueuedJob) -> bool {
331 matches!(&job.labels[..], [label] if GITHUB_HOSTED.iter().any(|hosted| hosted.eq_ignore_ascii_case(label)))
332}
333
334pub fn matches(job: &QueuedJob, labels: &[String]) -> bool {
337 crate::config::labels_match(&job.labels, labels)
338}
339
340pub fn plan(
355 repositories: &[Repository],
356 profiles: &BTreeMap<String, Profile>,
357 budget: Budget,
358 now: SystemTime,
359) -> Plan {
360 let mut decided = Plan::default();
361 unserved(repositories, &mut decided);
362 let ToServe {
363 mut wanted,
364 jobs,
365 warm: warm_wanted,
366 } = to_serve(repositories, profiles, now, &mut decided);
367
368 let mut warm = Warm::new(&decided.warm, profiles, budget.held);
369 let mut taken = taken_slots(profiles);
370 let mut left = Left {
371 memory: budget.memory,
372 cpu: budget.cpu,
373 host: budget.host,
374 };
375 let mut started = Started::new(&taken, left);
376 let mut slot_bound = SlotBound::default();
377 let mut first_for_cpu = None;
379 for (position, &(job, repository)) in jobs.iter().enumerate() {
380 let Some(missing) = wanted.get_mut(&pool_key(repository)) else {
381 continue;
382 };
383 if *missing == 0 {
384 continue;
385 }
386 let (Some(profile), Some(taken)) = (
387 profiles.get(&repository.profile),
388 taken.get_mut(repository.profile.as_str()),
389 ) else {
390 continue;
391 };
392 if let Some(older) = first_for_cpu {
393 decided
394 .waiting
395 .insert(job, Waiting::BehindCpu { job: older });
396 continue;
397 }
398 let memory = repository.runner_memory.unwrap_or(profile.memory);
399 let cpu = repository.runner_cpu.unwrap_or(profile.cpus);
400 let free_index = free_slot(taken, profile, repository, job, &jobs[position + 1..]);
401 let fits = free_index.is_some() && left.fits(memory, cpu);
402 let room = if fits || profile.preparing.is_some() {
403 None
404 } else {
405 warm.make_room(repository, free_index.is_none(), left, memory, cpu)
406 };
407 let index = match (room.as_ref(), free_index) {
408 (Some(room), free) => free.or(room.slot).unwrap_or_default(),
409 (None, Some(index)) if fits => index,
410 (None, free) => {
411 let (reason, short) = why_waits(
412 &repository.profile,
413 profile,
414 free.is_some(),
415 memory,
416 cpu,
417 left,
418 &started,
419 );
420 decided.waiting.insert(job, reason);
421 if free.is_none()
422 && profile.preparing.is_none()
423 && slot_bound.takes(left, memory, cpu)
424 {
425 decided.slot_waiting.insert(job);
426 }
427 if short == Short::Cpu {
428 let held = held_for_cpu(repository);
429 if !decided.decisions.contains(&held) {
430 decided.decisions.push(held);
431 }
432 if repository.starved_of_cpu(now) {
434 first_for_cpu = Some(job);
435 }
436 }
437 continue;
438 }
439 };
440 let replacing = room.map_or_else(Vec::new, |room| {
442 left.give(room.memory, room.cpu);
443 for slot in &room.stopped {
444 decided.warm.remove(slot);
445 decided.decisions.push(Decision::Stop {
446 slot: slot.clone(),
447 reason: StopReason::Room,
448 });
449 }
450 room.stopped
451 });
452 taken[index] = true;
453 *missing -= 1;
454 started.note(&repository.profile, job);
455 left.take(memory, cpu);
456 decided
457 .decisions
458 .push(start(repository, index, memory, cpu, replacing));
459 }
460 if !budget.held {
461 start_warm(&warm_wanted, profiles, &mut taken, left, &mut decided);
462 }
463 decided
464}
465
466struct ToServe<'plan> {
468 wanted: BTreeMap<(&'plan str, &'plan str), usize>,
470 jobs: Vec<(u64, &'plan Repository)>,
472 warm: Vec<(&'plan Repository, usize)>,
474}
475
476fn to_serve<'plan>(
478 repositories: &'plan [Repository],
479 profiles: &BTreeMap<String, Profile>,
480 now: SystemTime,
481 decided: &mut Plan,
482) -> ToServe<'plan> {
483 let mut serve = ToServe {
484 wanted: BTreeMap::new(),
485 jobs: Vec::new(),
486 warm: Vec::new(),
487 };
488 for repository in repositories {
489 if let Some(sorted) = sort_out(repository, profiles, now, decided) {
490 serve
491 .wanted
492 .insert(pool_key(repository), sorted.serve.len());
493 serve
494 .jobs
495 .extend(sorted.serve.into_iter().map(|job| (job, repository)));
496 serve.warm.push((repository, sorted.warm));
497 }
498 }
499 serve.jobs.sort_by_key(|(id, _)| *id);
500 serve
501}
502
503#[derive(Debug, Default)]
506struct SlotBound {
507 memory: u64,
508 cpu: u64,
509}
510
511impl SlotBound {
512 fn takes(&mut self, left: Left, memory: u64, cpu: u64) -> bool {
514 let mut spare = left;
515 spare.take(self.memory, self.cpu);
516 let fits = spare.fits(memory, cpu);
517 if fits {
518 self.memory = self.memory.saturating_add(memory);
519 self.cpu = self.cpu.saturating_add(cpu);
520 }
521 fits
522 }
523}
524
525fn free_slot(
531 taken: &[bool],
532 profile: &Profile,
533 repository: &Repository,
534 job: u64,
535 later: &[(u64, &Repository)],
536) -> Option<usize> {
537 let ran = |index: usize| profile.ran.get(index).and_then(Option::as_ref);
538 let ran_it = |index: usize, repository: &Repository, job: u64| {
539 let queued = repository.queued.iter().find(|queued| queued.id == job);
540 queued.zip(ran(index)).is_some_and(|(queued, key)| {
541 key.repository == repository.name
542 && key.workflow == queued.workflow
543 && key.name == queued.name
544 })
545 };
546 taken
547 .iter()
548 .enumerate()
549 .filter(|(_, taken)| !**taken)
550 .map(|(index, _)| index)
551 .min_by_key(|&index| {
552 let wanted_later = later.iter().any(|&(id, other)| {
553 other.profile == repository.profile && ran_it(index, other, id)
554 });
555 let same_repository = ran(index).is_some_and(|key| key.repository == repository.name);
556 (
557 !ran_it(index, repository, job),
558 wanted_later,
559 !same_repository,
560 index,
561 )
562 })
563}
564
565fn held_for_cpu(repository: &Repository) -> Decision {
567 Decision::HeldForCpu {
568 repository: repository.name.clone(),
569 profile: repository.profile.clone(),
570 }
571}
572
573fn pool_key(repository: &Repository) -> (&str, &str) {
575 (&repository.name, &repository.profile)
576}
577
578fn unserved(repositories: &[Repository], decided: &mut Plan) {
580 let mut seen = BTreeSet::new();
581 for repository in repositories {
582 if !seen.insert(repository.name.as_str()) {
583 continue;
584 }
585 let pools: Vec<&Repository> = repositories
586 .iter()
587 .filter(|pool| pool.name == repository.name)
588 .collect();
589 decided.waiting.extend(
590 repository
591 .queued
592 .iter()
593 .filter(|job| {
594 !hosted_by_github(job) && !pools.iter().any(|pool| matches(job, &pool.labels))
595 })
596 .map(|job| {
597 (
598 job.id,
599 Waiting::NoPool {
600 labels: job.labels.clone(),
601 },
602 )
603 }),
604 );
605 }
606}
607
608#[derive(Debug, Clone, Copy, PartialEq, Eq)]
610enum Short {
611 Slot,
612 Memory,
613 Cpu,
614}
615
616fn why_waits(
619 name: &str,
620 profile: &Profile,
621 free_slot: bool,
622 memory: u64,
623 cpu: u64,
624 left: Left,
625 started: &Started<'_>,
626) -> (Waiting, Short) {
627 let profile_name = || name.to_owned();
628 if !free_slot {
629 let reason = match profile.preparing {
630 Some(Preparing::Reseeding) => Waiting::Reseeding {
631 profile: profile_name(),
632 },
633 Some(Preparing::PullingImage) => Waiting::PullingImage {
634 profile: profile_name(),
635 },
636 None => started.for_slot(
637 name,
638 Waiting::NoSlot {
639 profile: profile_name(),
640 },
641 ),
642 };
643 return (reason, Short::Slot);
644 }
645 match (left.memory, left.host, left.cpu) {
646 (Some(free), _, _) if free < signed(memory) => (
647 started.for_memory(
648 memory,
649 Waiting::Memory {
650 needs: memory,
651 free: unsigned(free),
652 },
653 ),
654 Short::Memory,
655 ),
656 (_, Some(free), _) if free < signed(memory) => (
657 started.for_host(
658 memory,
659 Waiting::HostMemory {
660 needs: memory,
661 free: unsigned(free),
662 },
663 ),
664 Short::Memory,
665 ),
666 (_, _, Some(free)) => (
667 started.for_cpu(
668 cpu,
669 Waiting::Cpu {
670 needs: cpu,
671 free: unsigned(free),
672 },
673 ),
674 Short::Cpu,
675 ),
676 (_, _, None) => (
678 Waiting::NoSlot {
679 profile: profile_name(),
680 },
681 Short::Slot,
682 ),
683 }
684}
685
686fn start(
689 repository: &Repository,
690 index: usize,
691 memory: u64,
692 cpu: u64,
693 replacing: Vec<SlotRef>,
694) -> Decision {
695 Decision::Start {
696 slot: SlotRef {
697 profile: repository.profile.clone(),
698 index,
699 },
700 repository: repository.name.clone(),
701 memory,
702 cpu,
703 warm: false,
704 replacing,
705 }
706}
707
708fn start_warm(
712 wanted: &[(&Repository, usize)],
713 profiles: &BTreeMap<String, Profile>,
714 taken: &mut BTreeMap<&str, Vec<bool>>,
715 mut left: Left,
716 decided: &mut Plan,
717) {
718 let room_wanted = decided.waiting.values().any(|reason| {
719 matches!(
720 reason,
721 Waiting::NoSlot { .. }
722 | Waiting::Memory { .. }
723 | Waiting::HostMemory { .. }
724 | Waiting::Cpu { .. }
725 | Waiting::BehindCpu { .. }
726 | Waiting::BehindStart { .. }
727 )
728 });
729 if room_wanted {
730 return;
731 }
732 for round in 0.. {
733 let mut any = false;
734 for (repository, wants) in wanted {
735 if *wants <= round {
736 continue;
737 }
738 let (Some(profile), Some(taken)) = (
739 profiles.get(&repository.profile),
740 taken.get_mut(repository.profile.as_str()),
741 ) else {
742 continue;
743 };
744 let (memory, cpu) = (profile.memory, profile.cpus);
745 let Some(index) = taken.iter().position(|taken| !taken) else {
746 continue;
747 };
748 if !left.fits(memory, cpu) {
749 continue;
750 }
751 taken[index] = true;
752 left.take(memory, cpu);
753 any = true;
754 decided.decisions.push(Decision::Start {
755 slot: SlotRef {
756 profile: repository.profile.clone(),
757 index,
758 },
759 repository: repository.name.clone(),
760 memory,
761 cpu,
762 warm: true,
763 replacing: Vec::new(),
764 });
765 }
766 if !any {
767 break;
768 }
769 }
770}
771
772#[derive(Debug, Clone, Copy)]
775struct Left {
776 memory: Option<i64>,
777 cpu: Option<i64>,
778 host: Option<i64>,
780}
781
782impl Left {
783 fn fits(self, memory: u64, cpu: u64) -> bool {
784 let fits = |free: Option<i64>, needs: u64| free.is_none_or(|free| free >= signed(needs));
785 fits(self.memory, memory) && fits(self.host, memory) && fits(self.cpu, cpu)
786 }
787
788 fn short(self, memory: u64, cpu: u64) -> Left {
791 let lacks = |free: Option<i64>, needs: u64| {
792 free.map(|free| signed(needs).saturating_sub(free).max(0))
793 };
794 Left {
795 memory: lacks(self.memory, memory).max(lacks(self.host, memory)),
796 cpu: lacks(self.cpu, cpu),
797 host: None,
798 }
799 }
800
801 fn take(&mut self, memory: u64, cpu: u64) {
802 let take = |free: &mut Option<i64>, used: u64| {
803 *free = free.map(|free| free.saturating_sub(signed(used)));
804 };
805 take(&mut self.memory, memory);
806 take(&mut self.host, memory);
807 take(&mut self.cpu, cpu);
808 }
809
810 fn give(&mut self, memory: u64, cpu: u64) {
811 let give = |free: &mut Option<i64>, freed: u64| {
812 *free = free.map(|free| free.saturating_add(signed(freed)));
813 };
814 give(&mut self.memory, memory);
815 give(&mut self.host, memory);
816 give(&mut self.cpu, cpu);
817 }
818}
819
820fn left(budget: u64, in_use: u64) -> i64 {
823 signed(budget).saturating_sub(signed(in_use))
824}
825
826fn signed(amount: u64) -> i64 {
828 i64::try_from(amount).unwrap_or(i64::MAX)
829}
830
831fn unsigned(free: i64) -> u64 {
833 u64::try_from(free).unwrap_or(0)
834}
835
836struct Sorted {
838 serve: Vec<u64>,
839 warm: usize,
840}
841
842fn sort_out(
846 repository: &Repository,
847 profiles: &BTreeMap<String, Profile>,
848 now: SystemTime,
849 decided: &mut Plan,
850) -> Option<Sorted> {
851 let mut matching: Vec<&QueuedJob> = repository
852 .queued
853 .iter()
854 .filter(|job| matches(job, &repository.labels))
855 .collect();
856 let profile = profiles.get(&repository.profile);
857 let mut warm = repository.warm;
858 if repository.paused {
859 decided
860 .waiting
861 .extend(matching.iter().map(|job| (job.id, Waiting::Paused)));
862 matching.clear();
864 warm = 0;
865 }
866 let upkeep_due = profile.is_some_and(|profile| profile.upkeep_due);
869 let stop_now = upkeep_due || repository.paused;
870 if upkeep_due {
871 warm = 0;
872 }
873 let (idle, closing): (Vec<(SlotRef, &RunnerSlot)>, Vec<_>) = profile
874 .into_iter()
875 .flat_map(|profile| profile.slots.iter().enumerate())
876 .filter_map(|(index, slot)| match slot {
877 Slot::Runner(runner) if runner.repository == repository.name && !runner.busy => Some((
878 SlotRef {
879 profile: repository.profile.clone(),
880 index,
881 },
882 runner,
883 )),
884 _ => None,
885 })
886 .partition(|(slot, _)| profile.is_none_or(|profile| slot.index < profile.count));
887 decided
889 .decisions
890 .extend(closing.into_iter().map(|(slot, _)| Decision::Stop {
891 slot,
892 reason: StopReason::Closed,
893 }));
894 let surplus = idle.len().saturating_sub(matching.len());
895 let stops: Vec<SlotRef> = idle
896 .iter()
897 .filter(|(_, runner)| {
898 stop_now
899 || now
900 .duration_since(runner.started_at)
901 .is_ok_and(|waited| waited >= IDLE_TIMEOUT)
902 })
903 .take(surplus.saturating_sub(warm))
904 .map(|(slot, _)| slot.clone())
905 .collect();
906 let kept: Vec<&SlotRef> = idle
908 .iter()
909 .map(|(slot, _)| slot)
910 .filter(|slot| !stops.contains(slot))
911 .collect();
912 decided
913 .warm
914 .extend(kept.iter().skip(matching.len()).map(|slot| (*slot).clone()));
915 let warm = warm.saturating_sub(kept.len().saturating_sub(matching.len()));
916 decided
917 .decisions
918 .extend(stops.into_iter().map(|slot| Decision::Stop {
919 slot,
920 reason: if repository.paused {
921 StopReason::Paused
922 } else if upkeep_due {
923 StopReason::Upkeep
924 } else {
925 StopReason::Expired
926 },
927 }));
928 let missing = matching.len().saturating_sub(idle.len());
929 let skip = matching.len() - missing;
931 decided.waiting.extend(
932 matching
933 .iter()
934 .take(skip)
935 .map(|job| (job.id, Waiting::RunnerStarting)),
936 );
937 let serve = matching.iter().skip(skip).map(|job| job.id);
938 match repository.held.filter(|held| held.until > now) {
939 Some(held) => {
940 let until = crate::time::ms(held.until) / 1000;
941 decided.waiting.extend(serve.map(|job| {
942 (
943 job,
944 Waiting::Backoff {
945 until,
946 cause: held.cause,
947 },
948 )
949 }));
950 None
951 }
952 None => Some(Sorted {
953 serve: serve.collect(),
954 warm,
955 }),
956 }
957}
958
959struct Warm<'plan> {
961 runners: Vec<Option<(SlotRef, &'plan RunnerSlot)>>,
963}
964
965struct Room {
967 stopped: Vec<SlotRef>,
969 slot: Option<usize>,
971 memory: u64,
972 cpu: u64,
973}
974
975impl<'plan> Warm<'plan> {
976 fn new(
978 warm: &BTreeSet<SlotRef>,
979 profiles: &'plan BTreeMap<String, Profile>,
980 held: bool,
981 ) -> Warm<'plan> {
982 let runners = warm
983 .iter()
984 .filter(|_| !held)
985 .filter_map(
986 |slot| match profiles.get(&slot.profile)?.slots.get(slot.index)? {
987 Slot::Runner(runner) => Some(Some((slot.clone(), runner))),
988 Slot::Free | Slot::Closed => None,
989 },
990 )
991 .collect();
992 Warm { runners }
993 }
994
995 fn make_room(
1000 &mut self,
1001 repository: &Repository,
1002 slot: bool,
1003 left: Left,
1004 needs_memory: u64,
1005 needs_cpu: u64,
1006 ) -> Option<Room> {
1007 let short = left.short(needs_memory, needs_cpu);
1008 let (memory, cpu) = (
1009 unsigned(short.memory.unwrap_or(0)),
1010 unsigned(short.cpu.unwrap_or(0)),
1011 );
1012 let mut candidates: Vec<usize> = self
1013 .runners
1014 .iter()
1015 .enumerate()
1016 .filter_map(|(at, runner)| {
1017 runner
1018 .as_ref()
1019 .filter(|(slot, runner)| {
1020 runner.repository != repository.name || slot.profile != repository.profile
1021 })
1022 .map(|_| at)
1023 })
1024 .collect();
1025 candidates.sort_by_key(|at| {
1027 self.runners[*at]
1028 .as_ref()
1029 .is_some_and(|(slot, _)| slot.profile != repository.profile)
1030 });
1031 let mut room = Room {
1032 stopped: Vec::new(),
1033 slot: None,
1034 memory: 0,
1035 cpu: 0,
1036 };
1037 let mut picked = Vec::new();
1038 for at in candidates {
1039 let short = (slot && room.slot.is_none()) || room.memory < memory || room.cpu < cpu;
1040 if !short {
1041 break;
1042 }
1043 let Some((ref_, runner)) = &self.runners[at] else {
1044 continue;
1045 };
1046 let gives_slot = ref_.profile == repository.profile;
1047 let helps = (gives_slot && slot && room.slot.is_none())
1049 || (room.memory < memory && runner.memory > 0)
1050 || (room.cpu < cpu && runner.cpu > 0);
1051 if !helps {
1052 continue;
1053 }
1054 if gives_slot && room.slot.is_none() {
1055 room.slot = Some(ref_.index);
1056 }
1057 room.memory += runner.memory;
1058 room.cpu += runner.cpu;
1059 room.stopped.push(ref_.clone());
1060 picked.push(at);
1061 }
1062 let mut after = left;
1064 after.give(room.memory, room.cpu);
1065 if (slot && room.slot.is_none()) || !after.fits(needs_memory, needs_cpu) {
1066 return None;
1067 }
1068 for at in picked {
1069 self.runners[at] = None;
1070 }
1071 Some(room)
1072 }
1073}
1074
1075struct Started<'plan> {
1078 free_slots: BTreeSet<&'plan str>,
1080 before: Left,
1082 by_profile: BTreeMap<&'plan str, u64>,
1084 first: Option<u64>,
1085}
1086
1087impl<'plan> Started<'plan> {
1088 fn new(taken: &BTreeMap<&'plan str, Vec<bool>>, before: Left) -> Started<'plan> {
1089 Started {
1090 free_slots: taken
1091 .iter()
1092 .filter(|(_, slots)| slots.contains(&false))
1093 .map(|(name, _)| *name)
1094 .collect(),
1095 before,
1096 by_profile: BTreeMap::new(),
1097 first: None,
1098 }
1099 }
1100
1101 fn note(&mut self, profile: &'plan str, job: u64) {
1103 self.by_profile.entry(profile).or_insert(job);
1104 self.first.get_or_insert(job);
1105 }
1106
1107 fn for_slot(&self, profile: &str, reason: Waiting) -> Waiting {
1109 match self.by_profile.get(profile) {
1110 Some(older) if self.free_slots.contains(profile) => {
1111 Waiting::BehindStart { job: *older }
1112 }
1113 _ => reason,
1114 }
1115 }
1116
1117 fn for_memory(&self, needs: u64, reason: Waiting) -> Waiting {
1119 Self::behind(self.first, self.before.memory, needs).unwrap_or(reason)
1120 }
1121
1122 fn for_host(&self, needs: u64, reason: Waiting) -> Waiting {
1124 Self::behind(self.first, self.before.host, needs).unwrap_or(reason)
1125 }
1126
1127 fn for_cpu(&self, needs: u64, reason: Waiting) -> Waiting {
1129 Self::behind(self.first, self.before.cpu, needs).unwrap_or(reason)
1130 }
1131
1132 fn behind(first: Option<u64>, free: Option<i64>, needs: u64) -> Option<Waiting> {
1133 first
1134 .filter(|_| free.is_some_and(|free| free >= signed(needs)))
1135 .map(|job| Waiting::BehindStart { job })
1136 }
1137}
1138
1139fn taken_slots(profiles: &BTreeMap<String, Profile>) -> BTreeMap<&str, Vec<bool>> {
1141 profiles
1142 .iter()
1143 .map(|(name, profile)| {
1144 let taken = profile
1145 .slots
1146 .iter()
1147 .map(|slot| profile.preparing.is_some() || *slot != Slot::Free)
1148 .collect();
1149 (name.as_str(), taken)
1150 })
1151 .collect()
1152}
1153
1154#[cfg(test)]
1155mod tests;