1use std::collections::{BTreeMap, BTreeSet};
6use std::time::{Duration, SystemTime};
7
8use crate::admission::{Key, host, pooled};
9use crate::api::Waiting;
10use crate::github::QueuedJob;
11
12pub mod engine;
13pub mod priority;
14mod waits;
15pub mod warm;
16
17use priority::{Around, Backfill, Candidate, Held, Older, Runner};
18pub use priority::{
19 Barrier, Caps, Drained, PRIORITY_AFTER, RunTimes, SERVED_PRIORITY_AFTER, SHORT_RUN, Scarce,
20};
21pub use waits::{Wait, Waits};
22
23pub const IDLE_TIMEOUT: Duration = Duration::from_secs(300);
26
27#[derive(Debug, Clone, Copy)]
29pub struct Hold {
30 pub until: SystemTime,
32 pub cause: crate::api::HoldCause,
34}
35
36#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
39pub struct Pool {
40 pub repository: String,
42 pub profile: String,
44}
45
46impl From<&crate::config::Repository> for Pool {
47 fn from(repository: &crate::config::Repository) -> Pool {
48 Pool {
49 repository: repository.name.clone(),
50 profile: repository.profile.clone(),
51 }
52 }
53}
54
55#[derive(Debug, Clone)]
58pub struct Repository {
59 pub name: String,
61 pub profile: String,
63 pub labels: Vec<String>,
65 pub paused: bool,
67 pub held: Option<Hold>,
69 pub queued: Vec<QueuedJob>,
71 pub runner_memory: Option<u64>,
74 pub runner_cpu: Option<u64>,
77 pub waits: Waits,
79 pub usual: Option<Duration>,
82 pub warm: usize,
84}
85
86impl Repository {
87 pub fn pool(&self) -> Pool {
89 Pool {
90 repository: self.name.clone(),
91 profile: self.profile.clone(),
92 }
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 pub usual: Option<Duration>,
154 pub caps: Caps,
157 pub behind: Option<u64>,
160}
161
162#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
164pub struct SlotRef {
165 pub profile: String,
167 pub index: usize,
169}
170
171#[derive(Debug, Clone, PartialEq, Eq)]
173pub enum Decision {
174 Start {
176 slot: SlotRef,
178 repository: String,
180 memory: u64,
182 cpu: u64,
184 for_: StartFor,
186 replacing: Vec<SlotRef>,
189 behind: Option<u64>,
191 },
192 Stop {
194 slot: SlotRef,
196 reason: StopReason,
198 },
199}
200
201#[derive(Debug, Clone, Copy, PartialEq, Eq)]
203pub enum StartFor {
204 Job(u64),
206 Warm,
208}
209
210#[derive(Debug, Clone, PartialEq, Eq)]
213pub struct Demand {
214 pub pool: Pool,
216 pub job: u64,
218 pub scarce: Scarce,
220}
221
222#[derive(Debug, Clone, Copy, PartialEq, Eq)]
224pub enum StopReason {
225 Expired,
227 Room,
229 Upkeep,
231 Paused,
233 Closed,
235 Changed,
237 OverBudget,
239 Clean,
241 Shutdown,
243}
244
245impl StopReason {
246 pub fn as_str(self) -> &'static str {
248 match self {
249 StopReason::Expired => "expired",
250 StopReason::Room => "room",
251 StopReason::Upkeep => "upkeep",
252 StopReason::Paused => "paused",
253 StopReason::Closed => "closed",
254 StopReason::Changed => "changed",
255 StopReason::OverBudget => "over_budget",
256 StopReason::Clean => "clean",
257 StopReason::Shutdown => "shutdown",
258 }
259 }
260
261 pub fn words(self) -> &'static str {
263 match self {
264 StopReason::Expired => "no job came for it",
265 StopReason::Room => "a queued job takes its room",
266 StopReason::Upkeep => "its profile's upkeep waits for it",
267 StopReason::Paused => "its repository is paused",
268 StopReason::Closed => "its slot closed",
269 StopReason::Changed => "the config or runnerd changed its runners",
270 StopReason::OverBudget => "raised for a heavier job, it does not fit the budget",
271 StopReason::Clean => "a cache clean needs its volumes",
272 StopReason::Shutdown => "runnerd stops",
273 }
274 }
275}
276
277#[derive(Debug, Clone, Default, PartialEq, Eq)]
279pub struct Plan {
280 pub decisions: Vec<Decision>,
282 pub waiting: BTreeMap<u64, Waiting>,
286 pub warm: BTreeSet<SlotRef>,
288 pub slot_waiting: BTreeSet<u64>,
293 pub held: Vec<Demand>,
296 pub barrier: Option<Barrier>,
298 pub cpu_short: BTreeSet<u64>,
300}
301
302impl Plan {
303 pub fn host_needs(&self) -> impl Iterator<Item = u64> + '_ {
307 self.waiting
308 .iter()
309 .filter_map(|(job, reason)| match reason {
310 Waiting::HostMemory { needs, .. } if self.cpu_short.contains(job) => Some(u64::MAX),
311 Waiting::HostMemory { needs, .. } => Some(*needs),
312 _ => None,
313 })
314 }
315}
316
317#[derive(Debug, Clone, Default, PartialEq, Eq)]
319pub struct Budget {
320 pub memory: Option<i64>,
323 pub cpu: Option<i64>,
326 pub host: Option<i64>,
329 pub held: bool,
333 pub drained: Drained,
335 pub credit_room: u64,
338 pub host_credit_room: u64,
341 pub recount: Option<Recount>,
345 pub run_times: RunTimes,
347 pub plain: Option<Box<Budget>>,
351 pub retired: Vec<Retired>,
354}
355
356#[derive(Debug, Clone, PartialEq, Eq)]
358pub struct Retired {
359 pub profile: String,
361 pub runner: RunnerSlot,
363}
364
365#[derive(Debug, Clone, PartialEq, Eq)]
367pub struct Recount {
368 pub tally: pooled::Tally<SlotRef>,
370 pub memory_max: Option<u64>,
372 pub host: Option<HostLimit>,
374}
375
376#[derive(Debug, Clone, Copy, PartialEq, Eq)]
378pub struct HostLimit {
379 pub limit: u64,
381 pub stalled: bool,
383}
384
385impl Recount {
386 fn start(&mut self, left: &mut Left, memory: u64) {
388 self.tally.start(memory);
389 self.read(left);
390 }
391
392 fn stop(&mut self, left: &mut Left, slots: &[SlotRef]) {
394 for slot in slots {
395 self.tally.stop(slot);
396 }
397 self.read(left);
398 }
399
400 fn read(&self, left: &mut Left) {
402 let count = self.tally.count();
403 left.memory = self.memory_max.map(|max| self::left(max, count.pooled()));
404 left.host = self
405 .host
406 .map(|host| host::left(host.limit, count.hosted(), host.stalled));
407 }
408}
409
410const GITHUB_HOSTED: &[&str] = &[
416 "ubuntu-slim",
417 "ubuntu-latest",
418 "ubuntu-26.04",
419 "ubuntu-24.04",
420 "ubuntu-22.04",
421 "ubuntu-26.04-arm",
422 "ubuntu-24.04-arm",
423 "ubuntu-22.04-arm",
424 "windows-latest",
425 "windows-2025",
426 "windows-2025-vs2026",
427 "windows-2022",
428 "windows-11-arm",
429 "windows-11-vs2026-arm",
430 "macos-latest",
431 "macos-26",
432 "macos-15",
433 "macos-14",
434 "macos-26-intel",
435 "macos-15-intel",
436 "xcode-27",
437 "macos-latest-large",
438 "macos-26-large",
439 "macos-15-large",
440 "macos-14-large",
441 "macos-latest-xlarge",
442 "macos-26-xlarge",
443 "macos-15-xlarge",
444 "macos-14-xlarge",
445 "xcode-27-xlarge",
446];
447
448fn hosted_by_github(job: &QueuedJob) -> bool {
452 matches!(&job.labels[..], [label] if GITHUB_HOSTED.iter().any(|hosted| hosted.eq_ignore_ascii_case(label)))
453}
454
455pub fn matches(job: &QueuedJob, labels: &[String]) -> bool {
458 crate::config::labels_match(&job.labels, labels)
459}
460
461pub fn plan(
478 repositories: &[Repository],
479 profiles: &BTreeMap<String, Profile>,
480 mut budget: Budget,
481 now: SystemTime,
482) -> Plan {
483 let mut decided = Plan::default();
484 unserved(repositories, &mut decided);
485 let ToServe {
486 mut wanted,
487 jobs,
488 warm: warm_wanted,
489 } = to_serve(repositories, profiles, now, &mut decided);
490
491 let mut warm = Warm::new(&decided.warm, profiles, budget.held);
492 let mut taken = taken_slots(profiles);
493 let mut budgets = Budgets::new(&mut budget);
494 let mut started = Started::new(&taken, budgets.left);
495 let mut slot_bound = SlotBound::default();
496 let drained = (!budget.held).then_some(budget.drained);
498 let mut behind = Behind::new(profiles, &budget.retired);
499 for (position, &(job, repository)) in jobs.iter().enumerate() {
500 let Some(missing) = wanted.get_mut(&pool_key(repository)) else {
501 continue;
502 };
503 if *missing == 0 {
504 continue;
505 }
506 let (Some(profile), Some(taken)) = (
507 profiles.get(&repository.profile),
508 taken.get_mut(repository.profile.as_str()),
509 ) else {
510 continue;
511 };
512 let memory = repository.runner_memory.unwrap_or(profile.memory);
513 let cpu = repository.runner_cpu.unwrap_or(profile.cpus);
514 let free_index = free_slot(taken, profile, repository, job, &jobs[position + 1..]);
515 let fits = free_index.is_some() && budgets.left.fits(memory, cpu);
516 let turn = Turn {
517 repository,
518 profile,
519 job,
520 memory,
521 cpu,
522 free_slot: free_index.is_some(),
523 left: budgets.left,
524 started: &started,
525 };
526 if let Some(barrier) = decided.barrier {
527 let free_slots = taken.iter().filter(|taken| !**taken).count();
528 let passes = behind.passes(repository, profile, free_slots);
529 if !fits || !passes {
530 turn.behind(barrier, passes, &mut decided);
531 continue;
532 }
533 behind.admit(repository, profile, free_slots);
534 }
535 let room = if fits || profile.preparing.is_some() {
536 None
537 } else {
538 warm.make_room(repository, free_index.is_none(), &budgets, memory, cpu)
539 };
540 let index = match (room.as_ref(), free_index) {
541 (Some(room), free) => free.or(room.slot).unwrap_or_default(),
542 (None, Some(index)) if fits => index,
543 (None, _) => {
544 turn.waits(drained, &mut slot_bound, now, &mut decided);
545 let job = Older {
546 profile: &repository.profile,
547 free_slot: free_index.is_some() || profile.preparing.is_some(),
548 memory,
549 cpu,
550 };
551 behind.left_waiting(job, decided.barrier, budgets.plain_left(), &budget, now);
552 continue;
553 }
554 };
555 let replacing =
556 room.map_or_else(Vec::new, |room| stop_for(room, &mut budgets, &mut decided));
557 taken[index] = true;
558 *missing -= 1;
559 started.note(&repository.profile, job);
560 budgets.take(memory, cpu);
561 behind.started(
562 &repository.profile,
563 profile.caps(),
564 memory,
565 cpu,
566 decided.barrier,
567 now,
568 );
569 decided.decisions.push(start(
570 repository,
571 job,
572 index,
573 memory,
574 cpu,
575 replacing,
576 decided.barrier,
577 ));
578 }
579 if !budget.held {
580 start_warm(&warm_wanted, profiles, &mut taken, budgets, &mut decided);
581 }
582 decided
583}
584
585#[derive(Debug, Clone)]
588struct Budgets {
589 left: Left,
590 recount: Option<Recount>,
591 plain: Option<Box<Budgets>>,
593}
594
595impl Budgets {
596 fn new(budget: &mut Budget) -> Self {
598 Self {
599 left: Left {
600 memory: budget.memory,
601 cpu: budget.cpu,
602 host: budget.host,
603 },
604 recount: budget.recount.take(),
605 plain: budget
606 .plain
607 .as_deref_mut()
608 .map(|plain| Box::new(Budgets::new(plain))),
609 }
610 }
611
612 fn plain_left(&self) -> Left {
614 self.plain.as_ref().map_or(self.left, |plain| plain.left)
615 }
616
617 fn take(&mut self, memory: u64, cpu: u64) {
619 self.left.take(memory, cpu);
620 if let Some(recount) = &mut self.recount {
621 recount.start(&mut self.left, memory);
622 }
623 if let Some(plain) = &mut self.plain {
624 plain.take(memory, cpu);
625 }
626 }
627
628 fn give(&mut self, room: &Room) {
631 self.left.give(room.memory, room.cpu);
632 if let Some(recount) = &mut self.recount {
633 recount.stop(&mut self.left, &room.stopped);
634 }
635 if let Some(plain) = &mut self.plain {
636 plain.give(room);
637 }
638 }
639}
640
641fn stop_for(room: Room, budgets: &mut Budgets, decided: &mut Plan) -> Vec<SlotRef> {
643 budgets.give(&room);
644 for slot in &room.stopped {
645 decided.warm.remove(slot);
646 decided.decisions.push(Decision::Stop {
647 slot: slot.clone(),
648 reason: StopReason::Room,
649 });
650 }
651 room.stopped
652}
653
654struct Behind<'plan> {
656 runners: Vec<Runner<'plan>>,
658 older: Vec<Older<'plan>>,
660 backfill: Option<Backfill<'plan>>,
662}
663
664impl<'plan> Behind<'plan> {
665 fn new(profiles: &'plan BTreeMap<String, Profile>, retired: &'plan [Retired]) -> Behind<'plan> {
667 let slots = profiles.iter().flat_map(|(name, profile)| {
668 profile.slots.iter().filter_map(move |slot| match slot {
669 Slot::Runner(runner) => Some((name.as_str(), runner)),
670 Slot::Free | Slot::Closed => None,
671 })
672 });
673 let retired = retired
674 .iter()
675 .map(|retired| (retired.profile.as_str(), &retired.runner));
676 let runners = slots
677 .chain(retired)
678 .map(|(profile, runner)| Runner {
679 profile,
680 started_at: runner.started_at,
681 usual: runner.usual.filter(|_| runner.busy),
682 memory: runner.memory,
683 cpu: runner.cpu,
684 caps: runner.caps,
685 passed: runner.behind.is_some(),
686 })
687 .collect();
688 Behind {
689 runners,
690 older: Vec::new(),
691 backfill: None,
692 }
693 }
694
695 fn left_waiting(
698 &mut self,
699 job: Older<'plan>,
700 barrier: Option<Barrier>,
701 left: Left,
702 budget: &Budget,
703 now: SystemTime,
704 ) {
705 let Some(barrier) = barrier else {
706 self.older.push(job);
707 return;
708 };
709 let plain = budget.plain.as_deref().unwrap_or(budget);
710 let around = Around {
711 left,
712 run_times: budget.run_times,
713 credit_room: plain.credit_room,
714 host_credit_room: plain.host_credit_room,
715 drained: budget.drained,
716 runners: &self.runners,
717 older: &self.older,
718 };
719 self.backfill = Backfill::behind(barrier, job.profile, around, now);
720 }
721
722 fn candidate(
724 repository: &'plan Repository,
725 profile: &Profile,
726 free_slots: usize,
727 ) -> Candidate<'plan> {
728 Candidate {
729 profile: &repository.profile,
730 free_slots,
731 usual: repository.usual,
732 caps: profile.caps(),
733 }
734 }
735
736 fn passes(&self, repository: &Repository, profile: &Profile, free_slots: usize) -> bool {
738 let candidate = Behind::candidate(repository, profile, free_slots);
739 self.backfill
740 .as_ref()
741 .is_some_and(|backfill| backfill.passes(candidate))
742 }
743
744 fn admit(&mut self, repository: &Repository, profile: &Profile, free_slots: usize) {
746 let candidate = Behind::candidate(repository, profile, free_slots);
747 if let Some(backfill) = self.backfill.as_mut() {
748 backfill.admit(candidate);
749 }
750 }
751
752 fn started(
755 &mut self,
756 profile: &'plan str,
757 caps: Caps,
758 memory: u64,
759 cpu: u64,
760 barrier: Option<Barrier>,
761 now: SystemTime,
762 ) {
763 self.runners.push(Runner {
764 profile,
765 started_at: now,
766 usual: None,
767 memory,
768 cpu,
769 caps,
770 passed: barrier.is_some(),
771 });
772 }
773}
774
775struct ToServe<'plan> {
777 wanted: BTreeMap<(&'plan str, &'plan str), usize>,
779 jobs: Vec<(u64, &'plan Repository)>,
781 warm: Vec<(&'plan Repository, usize)>,
783}
784
785fn to_serve<'plan>(
787 repositories: &'plan [Repository],
788 profiles: &BTreeMap<String, Profile>,
789 now: SystemTime,
790 decided: &mut Plan,
791) -> ToServe<'plan> {
792 let mut serve = ToServe {
793 wanted: BTreeMap::new(),
794 jobs: Vec::new(),
795 warm: Vec::new(),
796 };
797 for repository in repositories {
798 if let Some(sorted) = sort_out(repository, profiles, now, decided) {
799 serve
800 .wanted
801 .insert(pool_key(repository), sorted.serve.len());
802 serve
803 .jobs
804 .extend(sorted.serve.into_iter().map(|job| (job, repository)));
805 serve.warm.push((repository, sorted.warm));
806 }
807 }
808 serve.jobs.sort_by_key(|(id, _)| *id);
809 serve
810}
811
812#[derive(Debug, Default)]
815struct SlotBound {
816 memory: u64,
817 cpu: u64,
818}
819
820impl SlotBound {
821 fn takes(&mut self, left: Left, memory: u64, cpu: u64) -> bool {
823 let mut spare = left;
824 spare.take(self.memory, self.cpu);
825 let fits = spare.fits(memory, cpu);
826 if fits {
827 self.memory = self.memory.saturating_add(memory);
828 self.cpu = self.cpu.saturating_add(cpu);
829 }
830 fits
831 }
832}
833
834fn free_slot(
840 taken: &[bool],
841 profile: &Profile,
842 repository: &Repository,
843 job: u64,
844 later: &[(u64, &Repository)],
845) -> Option<usize> {
846 let ran = |index: usize| profile.ran.get(index).and_then(Option::as_ref);
847 let ran_it = |index: usize, repository: &Repository, job: u64| {
848 let queued = repository.queued.iter().find(|queued| queued.id == job);
849 queued.zip(ran(index)).is_some_and(|(queued, key)| {
850 key.repository == repository.name
851 && key.workflow == queued.workflow
852 && key.name == queued.name
853 })
854 };
855 taken
856 .iter()
857 .enumerate()
858 .filter(|(_, taken)| !**taken)
859 .map(|(index, _)| index)
860 .min_by_key(|&index| {
861 let wanted_later = later.iter().any(|&(id, other)| {
862 other.profile == repository.profile && ran_it(index, other, id)
863 });
864 let same_repository = ran(index).is_some_and(|key| key.repository == repository.name);
865 (
866 !ran_it(index, repository, job),
867 wanted_later,
868 !same_repository,
869 index,
870 )
871 })
872}
873
874fn hold(repository: &Repository, job: u64, scarce: Scarce, decided: &mut Plan) {
876 let pool = repository.pool();
877 let held = decided
878 .held
879 .iter()
880 .any(|demand| demand.pool == pool && demand.scarce == scarce);
881 if !held {
882 decided.held.push(Demand { pool, job, scarce });
883 }
884}
885
886struct Turn<'plan> {
888 repository: &'plan Repository,
889 profile: &'plan Profile,
890 job: u64,
891 memory: u64,
892 cpu: u64,
894 free_slot: bool,
895 left: Left,
896 started: &'plan Started<'plan>,
897}
898
899impl Turn<'_> {
900 fn why(&self) -> (Waiting, Short) {
902 why_waits(
903 &self.repository.profile,
904 self.profile,
905 self.free_slot,
906 self.memory,
907 self.cpu,
908 self.left,
909 self.started,
910 )
911 }
912
913 fn says(&self, reason: Waiting, decided: &mut Plan) {
915 let cpu_short = self.left.cpu.is_some_and(|free| free < signed(self.cpu));
916 if cpu_short && matches!(reason, Waiting::HostMemory { .. }) {
917 decided.cpu_short.insert(self.job);
918 }
919 decided.waiting.insert(self.job, reason);
920 }
921
922 fn waits(
925 self,
926 drained: Option<Drained>,
927 slot_bound: &mut SlotBound,
928 now: SystemTime,
929 decided: &mut Plan,
930 ) {
931 let (reason, short) = self.why();
932 self.says(reason, decided);
933 if !self.free_slot
934 && self.profile.preparing.is_none()
935 && slot_bound.takes(self.left, self.memory, self.cpu)
936 {
937 decided.slot_waiting.insert(self.job);
938 }
939 let Some(scarce) = short.scarce() else {
940 return;
941 };
942 if drained.is_some() {
943 hold(self.repository, self.job, scarce, decided);
944 }
945 decided.barrier = Barrier::of(
946 priority::Short {
947 job: self.job,
948 scarce,
949 held: short.held(),
950 memory: self.memory,
951 cpu: self.cpu,
952 },
953 &self.repository.waits,
954 drained,
955 now,
956 );
957 }
958
959 fn behind(self, barrier: Barrier, passes: bool, decided: &mut Plan) {
965 if self.free_slot && self.left.fits(self.memory, self.cpu) {
966 decided.waiting.insert(self.job, barrier.reason());
967 return;
968 }
969 let (reason, short) = self.why();
970 let reason = if self.free_slot && !passes {
971 barrier.reason()
972 } else {
973 reason
974 };
975 self.says(reason, decided);
976 if let Some(scarce) = short.scarce() {
977 hold(self.repository, self.job, scarce, decided);
978 }
979 }
980}
981
982fn pool_key(repository: &Repository) -> (&str, &str) {
984 (&repository.name, &repository.profile)
985}
986
987fn unserved(repositories: &[Repository], decided: &mut Plan) {
989 let mut seen = BTreeSet::new();
990 for repository in repositories {
991 if !seen.insert(repository.name.as_str()) {
992 continue;
993 }
994 let pools: Vec<&Repository> = repositories
995 .iter()
996 .filter(|pool| pool.name == repository.name)
997 .collect();
998 decided.waiting.extend(
999 repository
1000 .queued
1001 .iter()
1002 .filter(|job| {
1003 !hosted_by_github(job) && !pools.iter().any(|pool| matches(job, &pool.labels))
1004 })
1005 .map(|job| {
1006 (
1007 job.id,
1008 Waiting::NoPool {
1009 labels: job.labels.clone(),
1010 },
1011 )
1012 }),
1013 );
1014 }
1015}
1016
1017#[derive(Debug, Clone, Copy, PartialEq, Eq)]
1019enum Short {
1020 Slot,
1021 Memory,
1022 Host,
1023 Cpu,
1024}
1025
1026impl Short {
1027 fn scarce(self) -> Option<Scarce> {
1029 match self {
1030 Short::Slot => None,
1031 Short::Memory | Short::Host => Some(Scarce::Memory),
1032 Short::Cpu => Some(Scarce::Cpu),
1033 }
1034 }
1035
1036 fn held(self) -> Held {
1038 match self {
1039 Short::Host => Held::ByHost,
1040 Short::Slot | Short::Memory | Short::Cpu => Held::ByBudget,
1041 }
1042 }
1043}
1044
1045fn why_waits(
1048 name: &str,
1049 profile: &Profile,
1050 free_slot: bool,
1051 memory: u64,
1052 cpu: u64,
1053 left: Left,
1054 started: &Started<'_>,
1055) -> (Waiting, Short) {
1056 let profile_name = || name.to_owned();
1057 if !free_slot {
1058 let reason = match profile.preparing {
1059 Some(Preparing::Reseeding) => Waiting::Reseeding {
1060 profile: profile_name(),
1061 },
1062 Some(Preparing::PullingImage) => Waiting::PullingImage {
1063 profile: profile_name(),
1064 },
1065 None => started.for_slot(
1066 name,
1067 Waiting::NoSlot {
1068 profile: profile_name(),
1069 },
1070 ),
1071 };
1072 return (reason, Short::Slot);
1073 }
1074 match (left.memory, left.host, left.cpu) {
1075 (Some(free), _, _) if free < signed(memory) => (
1076 started.for_memory(
1077 memory,
1078 Waiting::Memory {
1079 needs: memory,
1080 free: unsigned(free),
1081 },
1082 ),
1083 Short::Memory,
1084 ),
1085 (_, Some(free), _) if free < signed(memory) => (
1086 started.for_host(
1087 memory,
1088 Waiting::HostMemory {
1089 needs: memory,
1090 free: unsigned(free),
1091 },
1092 ),
1093 Short::Host,
1094 ),
1095 (_, _, Some(free)) => (
1096 started.for_cpu(
1097 cpu,
1098 Waiting::Cpu {
1099 needs: cpu,
1100 free: unsigned(free),
1101 },
1102 ),
1103 Short::Cpu,
1104 ),
1105 (_, _, None) => (
1107 Waiting::NoSlot {
1108 profile: profile_name(),
1109 },
1110 Short::Slot,
1111 ),
1112 }
1113}
1114
1115fn start(
1118 repository: &Repository,
1119 job: u64,
1120 index: usize,
1121 memory: u64,
1122 cpu: u64,
1123 replacing: Vec<SlotRef>,
1124 barrier: Option<Barrier>,
1125) -> Decision {
1126 Decision::Start {
1127 slot: SlotRef {
1128 profile: repository.profile.clone(),
1129 index,
1130 },
1131 repository: repository.name.clone(),
1132 memory,
1133 cpu,
1134 for_: StartFor::Job(job),
1135 replacing,
1136 behind: barrier.map(|barrier| barrier.job),
1137 }
1138}
1139
1140fn start_warm(
1144 wanted: &[(&Repository, usize)],
1145 profiles: &BTreeMap<String, Profile>,
1146 taken: &mut BTreeMap<&str, Vec<bool>>,
1147 mut budgets: Budgets,
1148 decided: &mut Plan,
1149) {
1150 let room_wanted = decided.waiting.values().any(|reason| {
1151 matches!(
1152 reason,
1153 Waiting::NoSlot { .. }
1154 | Waiting::Memory { .. }
1155 | Waiting::HostMemory { .. }
1156 | Waiting::Cpu { .. }
1157 | Waiting::BehindCpu { .. }
1158 | Waiting::BehindMemory { .. }
1159 | Waiting::BehindStart { .. }
1160 )
1161 });
1162 if room_wanted {
1163 return;
1164 }
1165 for round in 0.. {
1166 let mut any = false;
1167 for (repository, wants) in wanted {
1168 if *wants <= round {
1169 continue;
1170 }
1171 let (Some(profile), Some(taken)) = (
1172 profiles.get(&repository.profile),
1173 taken.get_mut(repository.profile.as_str()),
1174 ) else {
1175 continue;
1176 };
1177 let (memory, cpu) = (profile.memory, profile.cpus);
1178 let Some(index) = taken.iter().position(|taken| !taken) else {
1179 continue;
1180 };
1181 if !budgets.left.fits(memory, cpu) {
1182 continue;
1183 }
1184 taken[index] = true;
1185 budgets.take(memory, cpu);
1186 any = true;
1187 decided.decisions.push(Decision::Start {
1188 slot: SlotRef {
1189 profile: repository.profile.clone(),
1190 index,
1191 },
1192 repository: repository.name.clone(),
1193 memory,
1194 cpu,
1195 for_: StartFor::Warm,
1196 replacing: Vec::new(),
1197 behind: None,
1198 });
1199 }
1200 if !any {
1201 break;
1202 }
1203 }
1204}
1205
1206#[derive(Debug, Clone, Copy)]
1209pub(crate) struct Left {
1210 pub(crate) memory: Option<i64>,
1211 pub(crate) cpu: Option<i64>,
1212 pub(crate) host: Option<i64>,
1214}
1215
1216impl Profile {
1217 fn caps(&self) -> Caps {
1219 Caps {
1220 memory: self.memory,
1221 cpu: self.cpus,
1222 }
1223 }
1224}
1225
1226impl Left {
1227 fn fits(self, memory: u64, cpu: u64) -> bool {
1228 let fits = |free: Option<i64>, needs: u64| free.is_none_or(|free| free >= signed(needs));
1229 fits(self.memory, memory) && fits(self.host, memory) && fits(self.cpu, cpu)
1230 }
1231
1232 fn short(self, memory: u64, cpu: u64) -> Left {
1235 let lacks = |free: Option<i64>, needs: u64| {
1236 free.map(|free| signed(needs).saturating_sub(free).max(0))
1237 };
1238 Left {
1239 memory: lacks(self.memory, memory).max(lacks(self.host, memory)),
1240 cpu: lacks(self.cpu, cpu),
1241 host: None,
1242 }
1243 }
1244
1245 fn take(&mut self, memory: u64, cpu: u64) {
1246 let take = |free: &mut Option<i64>, used: u64| {
1247 *free = free.map(|free| free.saturating_sub(signed(used)));
1248 };
1249 take(&mut self.memory, memory);
1250 take(&mut self.host, memory);
1251 take(&mut self.cpu, cpu);
1252 }
1253
1254 fn give(&mut self, memory: u64, cpu: u64) {
1255 let give = |free: &mut Option<i64>, freed: u64| {
1256 *free = free.map(|free| free.saturating_add(signed(freed)));
1257 };
1258 give(&mut self.memory, memory);
1259 give(&mut self.host, memory);
1260 give(&mut self.cpu, cpu);
1261 }
1262}
1263
1264fn left(budget: u64, in_use: u64) -> i64 {
1267 signed(budget).saturating_sub(signed(in_use))
1268}
1269
1270fn signed(amount: u64) -> i64 {
1272 i64::try_from(amount).unwrap_or(i64::MAX)
1273}
1274
1275fn unsigned(free: i64) -> u64 {
1277 u64::try_from(free).unwrap_or(0)
1278}
1279
1280struct Sorted {
1282 serve: Vec<u64>,
1283 warm: usize,
1284}
1285
1286fn oldest_first(repository: &Repository) -> Vec<&QueuedJob> {
1289 let mut matching: Vec<&QueuedJob> = repository
1290 .queued
1291 .iter()
1292 .filter(|job| matches(job, &repository.labels))
1293 .collect();
1294 matching.sort_by_key(|job| job.id);
1295 matching
1296}
1297
1298fn sort_out(
1302 repository: &Repository,
1303 profiles: &BTreeMap<String, Profile>,
1304 now: SystemTime,
1305 decided: &mut Plan,
1306) -> Option<Sorted> {
1307 let mut matching = oldest_first(repository);
1308 let profile = profiles.get(&repository.profile);
1309 let mut warm = repository.warm;
1310 if repository.paused {
1311 decided
1312 .waiting
1313 .extend(matching.iter().map(|job| (job.id, Waiting::Paused)));
1314 matching.clear();
1316 warm = 0;
1317 }
1318 let upkeep_due = profile.is_some_and(|profile| profile.upkeep_due);
1321 let stop_now = upkeep_due || repository.paused;
1322 if upkeep_due {
1323 warm = 0;
1324 }
1325 let (idle, closing): (Vec<(SlotRef, &RunnerSlot)>, Vec<_>) = profile
1326 .into_iter()
1327 .flat_map(|profile| profile.slots.iter().enumerate())
1328 .filter_map(|(index, slot)| match slot {
1329 Slot::Runner(runner) if runner.repository == repository.name && !runner.busy => Some((
1330 SlotRef {
1331 profile: repository.profile.clone(),
1332 index,
1333 },
1334 runner,
1335 )),
1336 _ => None,
1337 })
1338 .partition(|(slot, _)| profile.is_none_or(|profile| slot.index < profile.count));
1339 decided
1341 .decisions
1342 .extend(closing.into_iter().map(|(slot, _)| Decision::Stop {
1343 slot,
1344 reason: StopReason::Closed,
1345 }));
1346 let surplus = idle.len().saturating_sub(matching.len());
1347 let stops: Vec<SlotRef> = idle
1348 .iter()
1349 .filter(|(_, runner)| {
1350 stop_now
1351 || now
1352 .duration_since(runner.started_at)
1353 .is_ok_and(|waited| waited >= IDLE_TIMEOUT)
1354 })
1355 .take(surplus.saturating_sub(warm))
1356 .map(|(slot, _)| slot.clone())
1357 .collect();
1358 let kept: Vec<&SlotRef> = idle
1360 .iter()
1361 .map(|(slot, _)| slot)
1362 .filter(|slot| !stops.contains(slot))
1363 .collect();
1364 decided
1365 .warm
1366 .extend(kept.iter().skip(matching.len()).map(|slot| (*slot).clone()));
1367 let warm = warm.saturating_sub(kept.len().saturating_sub(matching.len()));
1368 decided
1369 .decisions
1370 .extend(stops.into_iter().map(|slot| Decision::Stop {
1371 slot,
1372 reason: if repository.paused {
1373 StopReason::Paused
1374 } else if upkeep_due {
1375 StopReason::Upkeep
1376 } else {
1377 StopReason::Expired
1378 },
1379 }));
1380 let missing = matching.len().saturating_sub(idle.len());
1381 let skip = matching.len() - missing;
1383 decided.waiting.extend(
1384 matching
1385 .iter()
1386 .take(skip)
1387 .map(|job| (job.id, Waiting::RunnerStarting)),
1388 );
1389 let serve = matching.iter().skip(skip).map(|job| job.id);
1390 match repository.held.filter(|held| held.until > now) {
1391 Some(held) => {
1392 let until = crate::time::ms(held.until) / 1000;
1393 decided.waiting.extend(serve.map(|job| {
1394 (
1395 job,
1396 Waiting::Backoff {
1397 until,
1398 cause: held.cause,
1399 },
1400 )
1401 }));
1402 None
1403 }
1404 None => Some(Sorted {
1405 serve: serve.collect(),
1406 warm,
1407 }),
1408 }
1409}
1410
1411struct Warm<'plan> {
1413 runners: Vec<Option<(SlotRef, &'plan RunnerSlot)>>,
1415}
1416
1417struct Room {
1419 stopped: Vec<SlotRef>,
1421 slot: Option<usize>,
1423 memory: u64,
1424 cpu: u64,
1425}
1426
1427impl<'plan> Warm<'plan> {
1428 fn new(
1430 warm: &BTreeSet<SlotRef>,
1431 profiles: &'plan BTreeMap<String, Profile>,
1432 held: bool,
1433 ) -> Warm<'plan> {
1434 let runners = warm
1435 .iter()
1436 .filter(|_| !held)
1437 .filter_map(
1438 |slot| match profiles.get(&slot.profile)?.slots.get(slot.index)? {
1439 Slot::Runner(runner) => Some(Some((slot.clone(), runner))),
1440 Slot::Free | Slot::Closed => None,
1441 },
1442 )
1443 .collect();
1444 Warm { runners }
1445 }
1446
1447 fn make_room(
1452 &mut self,
1453 repository: &Repository,
1454 slot: bool,
1455 budgets: &Budgets,
1456 needs_memory: u64,
1457 needs_cpu: u64,
1458 ) -> Option<Room> {
1459 let short = budgets.left.short(needs_memory, needs_cpu);
1460 let (memory, cpu) = (
1461 unsigned(short.memory.unwrap_or(0)),
1462 unsigned(short.cpu.unwrap_or(0)),
1463 );
1464 let mut candidates: Vec<usize> = self
1465 .runners
1466 .iter()
1467 .enumerate()
1468 .filter_map(|(at, runner)| {
1469 runner
1470 .as_ref()
1471 .filter(|(slot, runner)| {
1472 runner.repository != repository.name || slot.profile != repository.profile
1473 })
1474 .map(|_| at)
1475 })
1476 .collect();
1477 candidates.sort_by_key(|at| {
1479 self.runners[*at]
1480 .as_ref()
1481 .is_some_and(|(slot, _)| slot.profile != repository.profile)
1482 });
1483 let mut room = Room {
1484 stopped: Vec::new(),
1485 slot: None,
1486 memory: 0,
1487 cpu: 0,
1488 };
1489 let mut picked = Vec::new();
1490 for at in candidates {
1491 let short = (slot && room.slot.is_none()) || room.memory < memory || room.cpu < cpu;
1492 if !short {
1493 break;
1494 }
1495 let Some((ref_, runner)) = &self.runners[at] else {
1496 continue;
1497 };
1498 let gives_slot = ref_.profile == repository.profile;
1499 let helps = (gives_slot && slot && room.slot.is_none())
1501 || (room.memory < memory && runner.memory > 0)
1502 || (room.cpu < cpu && runner.cpu > 0);
1503 if !helps {
1504 continue;
1505 }
1506 if gives_slot && room.slot.is_none() {
1507 room.slot = Some(ref_.index);
1508 }
1509 room.memory += runner.memory;
1510 room.cpu += runner.cpu;
1511 room.stopped.push(ref_.clone());
1512 picked.push(at);
1513 }
1514 let mut after = budgets.clone();
1517 after.give(&room);
1518 if (slot && room.slot.is_none()) || !after.left.fits(needs_memory, needs_cpu) {
1519 return None;
1520 }
1521 for at in picked {
1522 self.runners[at] = None;
1523 }
1524 Some(room)
1525 }
1526}
1527
1528struct Started<'plan> {
1531 free_slots: BTreeSet<&'plan str>,
1533 before: Left,
1535 by_profile: BTreeMap<&'plan str, u64>,
1537 first: Option<u64>,
1538}
1539
1540impl<'plan> Started<'plan> {
1541 fn new(taken: &BTreeMap<&'plan str, Vec<bool>>, before: Left) -> Started<'plan> {
1542 Started {
1543 free_slots: taken
1544 .iter()
1545 .filter(|(_, slots)| slots.contains(&false))
1546 .map(|(name, _)| *name)
1547 .collect(),
1548 before,
1549 by_profile: BTreeMap::new(),
1550 first: None,
1551 }
1552 }
1553
1554 fn note(&mut self, profile: &'plan str, job: u64) {
1556 self.by_profile.entry(profile).or_insert(job);
1557 self.first.get_or_insert(job);
1558 }
1559
1560 fn for_slot(&self, profile: &str, reason: Waiting) -> Waiting {
1562 match self.by_profile.get(profile) {
1563 Some(older) if self.free_slots.contains(profile) => {
1564 Waiting::BehindStart { job: *older }
1565 }
1566 _ => reason,
1567 }
1568 }
1569
1570 fn for_memory(&self, needs: u64, reason: Waiting) -> Waiting {
1572 Self::behind(self.first, self.before.memory, needs).unwrap_or(reason)
1573 }
1574
1575 fn for_host(&self, needs: u64, reason: Waiting) -> Waiting {
1577 Self::behind(self.first, self.before.host, needs).unwrap_or(reason)
1578 }
1579
1580 fn for_cpu(&self, needs: u64, reason: Waiting) -> Waiting {
1582 Self::behind(self.first, self.before.cpu, needs).unwrap_or(reason)
1583 }
1584
1585 fn behind(first: Option<u64>, free: Option<i64>, needs: u64) -> Option<Waiting> {
1586 first
1587 .filter(|_| free.is_some_and(|free| free >= signed(needs)))
1588 .map(|job| Waiting::BehindStart { job })
1589 }
1590}
1591
1592fn taken_slots(profiles: &BTreeMap<String, Profile>) -> BTreeMap<&str, Vec<bool>> {
1594 profiles
1595 .iter()
1596 .map(|(name, profile)| {
1597 let taken = profile
1598 .slots
1599 .iter()
1600 .map(|slot| profile.preparing.is_some() || *slot != Slot::Free)
1601 .collect();
1602 (name.as_str(), taken)
1603 })
1604 .collect()
1605}
1606
1607#[cfg(test)]
1608mod tests;