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, Caps, Held, Older, Runner};
18pub use priority::{Barrier, Drained, PRIORITY_AFTER, SERVED_PRIORITY_AFTER, Scarce};
19pub use waits::{Wait, Waits};
20
21pub const IDLE_TIMEOUT: Duration = Duration::from_secs(300);
24
25#[derive(Debug, Clone, Copy)]
27pub struct Hold {
28 pub until: SystemTime,
30 pub cause: crate::api::HoldCause,
32}
33
34#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
37pub struct Pool {
38 pub repository: String,
40 pub profile: String,
42}
43
44impl From<&crate::config::Repository> for Pool {
45 fn from(repository: &crate::config::Repository) -> Pool {
46 Pool {
47 repository: repository.name.clone(),
48 profile: repository.profile.clone(),
49 }
50 }
51}
52
53#[derive(Debug, Clone)]
56pub struct Repository {
57 pub name: String,
59 pub profile: String,
61 pub labels: Vec<String>,
63 pub paused: bool,
65 pub held: Option<Hold>,
67 pub queued: Vec<QueuedJob>,
69 pub runner_memory: Option<u64>,
72 pub runner_cpu: Option<u64>,
75 pub waits: Waits,
77 pub usual: Option<Duration>,
80 pub warm: usize,
82}
83
84impl Repository {
85 pub fn pool(&self) -> Pool {
87 Pool {
88 repository: self.name.clone(),
89 profile: self.profile.clone(),
90 }
91 }
92}
93
94#[derive(Debug, Clone)]
96pub struct Profile {
97 pub memory: u64,
99 pub cpus: u64,
102 pub preparing: Option<Preparing>,
104 pub upkeep_due: bool,
107 pub count: usize,
109 pub slots: Vec<Slot>,
111 pub ran: Vec<Option<Key>>,
114}
115
116#[derive(Debug, Clone, Copy, PartialEq, Eq)]
118pub enum Preparing {
119 Reseeding,
121 PullingImage,
123}
124
125#[derive(Debug, Clone, PartialEq, Eq)]
127pub enum Slot {
128 Free,
130 Runner(RunnerSlot),
132 Closed,
135}
136
137#[derive(Debug, Clone, PartialEq, Eq)]
139pub struct RunnerSlot {
140 pub repository: String,
142 pub busy: bool,
144 pub started_at: SystemTime,
146 pub memory: u64,
148 pub cpu: u64,
150 pub usual: Option<Duration>,
152 pub behind: Option<u64>,
155}
156
157#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
159pub struct SlotRef {
160 pub profile: String,
162 pub index: usize,
164}
165
166#[derive(Debug, Clone, PartialEq, Eq)]
168pub enum Decision {
169 Start {
171 slot: SlotRef,
173 repository: String,
175 memory: u64,
177 cpu: u64,
179 for_: StartFor,
181 replacing: Vec<SlotRef>,
184 behind: Option<u64>,
186 },
187 Stop {
189 slot: SlotRef,
191 reason: StopReason,
193 },
194}
195
196#[derive(Debug, Clone, Copy, PartialEq, Eq)]
198pub enum StartFor {
199 Job(u64),
201 Warm,
203}
204
205#[derive(Debug, Clone, PartialEq, Eq)]
208pub struct Demand {
209 pub pool: Pool,
211 pub job: u64,
213 pub scarce: Scarce,
215}
216
217#[derive(Debug, Clone, Copy, PartialEq, Eq)]
219pub enum StopReason {
220 Expired,
222 Room,
224 Upkeep,
226 Paused,
228 Closed,
230 Changed,
232 OverBudget,
234 Clean,
236 Shutdown,
238}
239
240impl StopReason {
241 pub fn as_str(self) -> &'static str {
243 match self {
244 StopReason::Expired => "expired",
245 StopReason::Room => "room",
246 StopReason::Upkeep => "upkeep",
247 StopReason::Paused => "paused",
248 StopReason::Closed => "closed",
249 StopReason::Changed => "changed",
250 StopReason::OverBudget => "over_budget",
251 StopReason::Clean => "clean",
252 StopReason::Shutdown => "shutdown",
253 }
254 }
255
256 pub fn words(self) -> &'static str {
258 match self {
259 StopReason::Expired => "no job came for it",
260 StopReason::Room => "a queued job takes its room",
261 StopReason::Upkeep => "its profile's upkeep waits for it",
262 StopReason::Paused => "its repository is paused",
263 StopReason::Closed => "its slot closed",
264 StopReason::Changed => "the config or runnerd changed its runners",
265 StopReason::OverBudget => "raised for a heavier job, it does not fit the budget",
266 StopReason::Clean => "a cache clean needs its volumes",
267 StopReason::Shutdown => "runnerd stops",
268 }
269 }
270}
271
272#[derive(Debug, Clone, Default, PartialEq, Eq)]
274pub struct Plan {
275 pub decisions: Vec<Decision>,
277 pub waiting: BTreeMap<u64, Waiting>,
281 pub warm: BTreeSet<SlotRef>,
283 pub slot_waiting: BTreeSet<u64>,
288 pub held: Vec<Demand>,
291 pub barrier: Option<Barrier>,
293}
294
295#[derive(Debug, Clone, Default, PartialEq, Eq)]
297pub struct Budget {
298 pub memory: Option<i64>,
301 pub cpu: Option<i64>,
304 pub host: Option<i64>,
307 pub held: bool,
311 pub drained: Drained,
313 pub credit_room: u64,
316 pub host_credit_room: u64,
319 pub recount: Option<Recount>,
323}
324
325#[derive(Debug, Clone, PartialEq, Eq)]
327pub struct Recount {
328 pub tally: pooled::Tally<SlotRef>,
330 pub memory_max: Option<u64>,
332 pub host: Option<HostLimit>,
334}
335
336#[derive(Debug, Clone, Copy, PartialEq, Eq)]
338pub struct HostLimit {
339 pub limit: u64,
341 pub stalled: bool,
343}
344
345impl Recount {
346 fn start(&mut self, left: &mut Left, memory: u64) {
348 self.tally.start(memory);
349 self.read(left);
350 }
351
352 fn stop(&mut self, left: &mut Left, slots: &[SlotRef]) {
354 for slot in slots {
355 self.tally.stop(slot);
356 }
357 self.read(left);
358 }
359
360 fn read(&self, left: &mut Left) {
362 let count = self.tally.count();
363 left.memory = self.memory_max.map(|max| self::left(max, count.pooled()));
364 left.host = self
365 .host
366 .map(|host| host::left(host.limit, count.hosted(), host.stalled));
367 }
368}
369
370const GITHUB_HOSTED: &[&str] = &[
376 "ubuntu-slim",
377 "ubuntu-latest",
378 "ubuntu-26.04",
379 "ubuntu-24.04",
380 "ubuntu-22.04",
381 "ubuntu-26.04-arm",
382 "ubuntu-24.04-arm",
383 "ubuntu-22.04-arm",
384 "windows-latest",
385 "windows-2025",
386 "windows-2025-vs2026",
387 "windows-2022",
388 "windows-11-arm",
389 "windows-11-vs2026-arm",
390 "macos-latest",
391 "macos-26",
392 "macos-15",
393 "macos-14",
394 "macos-26-intel",
395 "macos-15-intel",
396 "xcode-27",
397 "macos-latest-large",
398 "macos-26-large",
399 "macos-15-large",
400 "macos-14-large",
401 "macos-latest-xlarge",
402 "macos-26-xlarge",
403 "macos-15-xlarge",
404 "macos-14-xlarge",
405 "xcode-27-xlarge",
406];
407
408fn hosted_by_github(job: &QueuedJob) -> bool {
412 matches!(&job.labels[..], [label] if GITHUB_HOSTED.iter().any(|hosted| hosted.eq_ignore_ascii_case(label)))
413}
414
415pub fn matches(job: &QueuedJob, labels: &[String]) -> bool {
418 crate::config::labels_match(&job.labels, labels)
419}
420
421pub fn plan(
438 repositories: &[Repository],
439 profiles: &BTreeMap<String, Profile>,
440 mut budget: Budget,
441 now: SystemTime,
442) -> Plan {
443 let mut decided = Plan::default();
444 unserved(repositories, &mut decided);
445 let ToServe {
446 mut wanted,
447 jobs,
448 warm: warm_wanted,
449 } = to_serve(repositories, profiles, now, &mut decided);
450
451 let mut warm = Warm::new(&decided.warm, profiles, budget.held);
452 let mut taken = taken_slots(profiles);
453 let mut budgets = Budgets::new(&mut budget);
454 let mut started = Started::new(&taken, budgets.left);
455 let mut slot_bound = SlotBound::default();
456 let drained = (!budget.held).then_some(budget.drained);
458 let mut behind = Behind::new(profiles);
459 for (position, &(job, repository)) in jobs.iter().enumerate() {
460 let Some(missing) = wanted.get_mut(&pool_key(repository)) else {
461 continue;
462 };
463 if *missing == 0 {
464 continue;
465 }
466 let (Some(profile), Some(taken)) = (
467 profiles.get(&repository.profile),
468 taken.get_mut(repository.profile.as_str()),
469 ) else {
470 continue;
471 };
472 let memory = repository.runner_memory.unwrap_or(profile.memory);
473 let cpu = repository.runner_cpu.unwrap_or(profile.cpus);
474 let free_index = free_slot(taken, profile, repository, job, &jobs[position + 1..]);
475 let fits = free_index.is_some() && budgets.left.fits(memory, cpu);
476 let turn = Turn {
477 repository,
478 profile,
479 job,
480 memory,
481 cpu,
482 free_slot: free_index.is_some(),
483 left: budgets.left,
484 started: &started,
485 };
486 if let Some(barrier) = decided.barrier {
487 let free_slots = taken.iter().filter(|taken| !**taken).count();
488 if !fits || !behind.admits(repository, profile, free_slots) {
489 turn.behind(barrier, &mut decided);
490 continue;
491 }
492 }
493 let room = if fits || profile.preparing.is_some() {
494 None
495 } else {
496 warm.make_room(repository, free_index.is_none(), &budgets, memory, cpu)
497 };
498 let index = match (room.as_ref(), free_index) {
499 (Some(room), free) => free.or(room.slot).unwrap_or_default(),
500 (None, Some(index)) if fits => index,
501 (None, _) => {
502 turn.waits(drained, &mut slot_bound, now, &mut decided);
503 let job = Older {
504 profile: &repository.profile,
505 free_slot: free_index.is_some() || profile.preparing.is_some(),
506 memory,
507 cpu,
508 };
509 behind.left_waiting(job, decided.barrier, budgets.left, &budget, now);
510 continue;
511 }
512 };
513 let replacing =
514 room.map_or_else(Vec::new, |room| stop_for(room, &mut budgets, &mut decided));
515 taken[index] = true;
516 *missing -= 1;
517 started.note(&repository.profile, job);
518 budgets.take(memory, cpu);
519 behind.started(
520 &repository.profile,
521 profile.caps(),
522 memory,
523 cpu,
524 decided.barrier,
525 now,
526 );
527 decided.decisions.push(start(
528 repository,
529 job,
530 index,
531 memory,
532 cpu,
533 replacing,
534 decided.barrier,
535 ));
536 }
537 if !budget.held {
538 start_warm(&warm_wanted, profiles, &mut taken, budgets, &mut decided);
539 }
540 decided
541}
542
543#[derive(Debug, Clone)]
546struct Budgets {
547 left: Left,
548 recount: Option<Recount>,
549}
550
551impl Budgets {
552 fn new(budget: &mut Budget) -> Self {
554 Self {
555 left: Left {
556 memory: budget.memory,
557 cpu: budget.cpu,
558 host: budget.host,
559 },
560 recount: budget.recount.take(),
561 }
562 }
563
564 fn take(&mut self, memory: u64, cpu: u64) {
566 self.left.take(memory, cpu);
567 if let Some(recount) = &mut self.recount {
568 recount.start(&mut self.left, memory);
569 }
570 }
571
572 fn give(&mut self, room: &Room) {
575 self.left.give(room.memory, room.cpu);
576 if let Some(recount) = &mut self.recount {
577 recount.stop(&mut self.left, &room.stopped);
578 }
579 }
580}
581
582fn stop_for(room: Room, budgets: &mut Budgets, decided: &mut Plan) -> Vec<SlotRef> {
584 budgets.give(&room);
585 for slot in &room.stopped {
586 decided.warm.remove(slot);
587 decided.decisions.push(Decision::Stop {
588 slot: slot.clone(),
589 reason: StopReason::Room,
590 });
591 }
592 room.stopped
593}
594
595struct Behind<'plan> {
597 runners: Vec<Runner<'plan>>,
599 older: Vec<Older<'plan>>,
601 backfill: Option<Backfill<'plan>>,
603}
604
605impl<'plan> Behind<'plan> {
606 fn new(profiles: &'plan BTreeMap<String, Profile>) -> Behind<'plan> {
608 let mut runners = Vec::new();
609 for (name, profile) in profiles {
610 for slot in &profile.slots {
611 if let Slot::Runner(runner) = slot {
612 runners.push(Runner {
613 profile: name,
614 started_at: runner.started_at,
615 usual: runner.usual.filter(|_| runner.busy),
616 memory: runner.memory,
617 cpu: runner.cpu,
618 caps: profile.caps(),
619 passed: runner.behind.is_some(),
620 });
621 }
622 }
623 }
624 Behind {
625 runners,
626 older: Vec::new(),
627 backfill: None,
628 }
629 }
630
631 fn left_waiting(
633 &mut self,
634 job: Older<'plan>,
635 barrier: Option<Barrier>,
636 left: Left,
637 budget: &Budget,
638 now: SystemTime,
639 ) {
640 let Some(barrier) = barrier else {
641 self.older.push(job);
642 return;
643 };
644 let around = Around {
645 left,
646 credit_room: budget.credit_room,
647 host_credit_room: budget.host_credit_room,
648 drained: budget.drained,
649 runners: &self.runners,
650 older: &self.older,
651 };
652 self.backfill = Backfill::behind(barrier, job.profile, around, now);
653 }
654
655 fn admits(&mut self, repository: &Repository, profile: &Profile, free_slots: usize) -> bool {
658 let candidate = Candidate {
659 profile: &repository.profile,
660 free_slots,
661 usual: repository.usual,
662 caps: profile.caps(),
663 };
664 let backfill = self.backfill.as_mut();
665 backfill.is_some_and(|backfill| backfill.admits(candidate))
666 }
667
668 fn started(
671 &mut self,
672 profile: &'plan str,
673 caps: Caps,
674 memory: u64,
675 cpu: u64,
676 barrier: Option<Barrier>,
677 now: SystemTime,
678 ) {
679 self.runners.push(Runner {
680 profile,
681 started_at: now,
682 usual: None,
683 memory,
684 cpu,
685 caps,
686 passed: barrier.is_some(),
687 });
688 }
689}
690
691struct ToServe<'plan> {
693 wanted: BTreeMap<(&'plan str, &'plan str), usize>,
695 jobs: Vec<(u64, &'plan Repository)>,
697 warm: Vec<(&'plan Repository, usize)>,
699}
700
701fn to_serve<'plan>(
703 repositories: &'plan [Repository],
704 profiles: &BTreeMap<String, Profile>,
705 now: SystemTime,
706 decided: &mut Plan,
707) -> ToServe<'plan> {
708 let mut serve = ToServe {
709 wanted: BTreeMap::new(),
710 jobs: Vec::new(),
711 warm: Vec::new(),
712 };
713 for repository in repositories {
714 if let Some(sorted) = sort_out(repository, profiles, now, decided) {
715 serve
716 .wanted
717 .insert(pool_key(repository), sorted.serve.len());
718 serve
719 .jobs
720 .extend(sorted.serve.into_iter().map(|job| (job, repository)));
721 serve.warm.push((repository, sorted.warm));
722 }
723 }
724 serve.jobs.sort_by_key(|(id, _)| *id);
725 serve
726}
727
728#[derive(Debug, Default)]
731struct SlotBound {
732 memory: u64,
733 cpu: u64,
734}
735
736impl SlotBound {
737 fn takes(&mut self, left: Left, memory: u64, cpu: u64) -> bool {
739 let mut spare = left;
740 spare.take(self.memory, self.cpu);
741 let fits = spare.fits(memory, cpu);
742 if fits {
743 self.memory = self.memory.saturating_add(memory);
744 self.cpu = self.cpu.saturating_add(cpu);
745 }
746 fits
747 }
748}
749
750fn free_slot(
756 taken: &[bool],
757 profile: &Profile,
758 repository: &Repository,
759 job: u64,
760 later: &[(u64, &Repository)],
761) -> Option<usize> {
762 let ran = |index: usize| profile.ran.get(index).and_then(Option::as_ref);
763 let ran_it = |index: usize, repository: &Repository, job: u64| {
764 let queued = repository.queued.iter().find(|queued| queued.id == job);
765 queued.zip(ran(index)).is_some_and(|(queued, key)| {
766 key.repository == repository.name
767 && key.workflow == queued.workflow
768 && key.name == queued.name
769 })
770 };
771 taken
772 .iter()
773 .enumerate()
774 .filter(|(_, taken)| !**taken)
775 .map(|(index, _)| index)
776 .min_by_key(|&index| {
777 let wanted_later = later.iter().any(|&(id, other)| {
778 other.profile == repository.profile && ran_it(index, other, id)
779 });
780 let same_repository = ran(index).is_some_and(|key| key.repository == repository.name);
781 (
782 !ran_it(index, repository, job),
783 wanted_later,
784 !same_repository,
785 index,
786 )
787 })
788}
789
790fn hold(repository: &Repository, job: u64, scarce: Scarce, decided: &mut Plan) {
792 let pool = repository.pool();
793 let held = decided
794 .held
795 .iter()
796 .any(|demand| demand.pool == pool && demand.scarce == scarce);
797 if !held {
798 decided.held.push(Demand { pool, job, scarce });
799 }
800}
801
802struct Turn<'plan> {
804 repository: &'plan Repository,
805 profile: &'plan Profile,
806 job: u64,
807 memory: u64,
808 cpu: u64,
810 free_slot: bool,
811 left: Left,
812 started: &'plan Started<'plan>,
813}
814
815impl Turn<'_> {
816 fn why(&self) -> (Waiting, Short) {
818 why_waits(
819 &self.repository.profile,
820 self.profile,
821 self.free_slot,
822 self.memory,
823 self.cpu,
824 self.left,
825 self.started,
826 )
827 }
828
829 fn waits(
832 self,
833 drained: Option<Drained>,
834 slot_bound: &mut SlotBound,
835 now: SystemTime,
836 decided: &mut Plan,
837 ) {
838 let (reason, short) = self.why();
839 decided.waiting.insert(self.job, reason);
840 if !self.free_slot
841 && self.profile.preparing.is_none()
842 && slot_bound.takes(self.left, self.memory, self.cpu)
843 {
844 decided.slot_waiting.insert(self.job);
845 }
846 let Some(scarce) = short.scarce() else {
847 return;
848 };
849 if drained.is_some() {
850 hold(self.repository, self.job, scarce, decided);
851 }
852 decided.barrier = Barrier::of(
853 priority::Short {
854 job: self.job,
855 scarce,
856 held: short.held(),
857 memory: self.memory,
858 cpu: self.cpu,
859 },
860 &self.repository.waits,
861 drained,
862 now,
863 );
864 }
865
866 fn behind(self, barrier: Barrier, decided: &mut Plan) {
870 if self.free_slot && self.left.fits(self.memory, self.cpu) {
871 decided.waiting.insert(self.job, barrier.reason());
872 return;
873 }
874 let (reason, short) = self.why();
875 let reason = if self.free_slot {
876 barrier.reason()
877 } else {
878 reason
879 };
880 decided.waiting.insert(self.job, reason);
881 if let Some(scarce) = short.scarce() {
882 hold(self.repository, self.job, scarce, decided);
883 }
884 }
885}
886
887fn pool_key(repository: &Repository) -> (&str, &str) {
889 (&repository.name, &repository.profile)
890}
891
892fn unserved(repositories: &[Repository], decided: &mut Plan) {
894 let mut seen = BTreeSet::new();
895 for repository in repositories {
896 if !seen.insert(repository.name.as_str()) {
897 continue;
898 }
899 let pools: Vec<&Repository> = repositories
900 .iter()
901 .filter(|pool| pool.name == repository.name)
902 .collect();
903 decided.waiting.extend(
904 repository
905 .queued
906 .iter()
907 .filter(|job| {
908 !hosted_by_github(job) && !pools.iter().any(|pool| matches(job, &pool.labels))
909 })
910 .map(|job| {
911 (
912 job.id,
913 Waiting::NoPool {
914 labels: job.labels.clone(),
915 },
916 )
917 }),
918 );
919 }
920}
921
922#[derive(Debug, Clone, Copy, PartialEq, Eq)]
924enum Short {
925 Slot,
926 Memory,
927 Host,
928 Cpu,
929}
930
931impl Short {
932 fn scarce(self) -> Option<Scarce> {
934 match self {
935 Short::Slot => None,
936 Short::Memory | Short::Host => Some(Scarce::Memory),
937 Short::Cpu => Some(Scarce::Cpu),
938 }
939 }
940
941 fn held(self) -> Held {
943 match self {
944 Short::Host => Held::ByHost,
945 Short::Slot | Short::Memory | Short::Cpu => Held::ByBudget,
946 }
947 }
948}
949
950fn why_waits(
953 name: &str,
954 profile: &Profile,
955 free_slot: bool,
956 memory: u64,
957 cpu: u64,
958 left: Left,
959 started: &Started<'_>,
960) -> (Waiting, Short) {
961 let profile_name = || name.to_owned();
962 if !free_slot {
963 let reason = match profile.preparing {
964 Some(Preparing::Reseeding) => Waiting::Reseeding {
965 profile: profile_name(),
966 },
967 Some(Preparing::PullingImage) => Waiting::PullingImage {
968 profile: profile_name(),
969 },
970 None => started.for_slot(
971 name,
972 Waiting::NoSlot {
973 profile: profile_name(),
974 },
975 ),
976 };
977 return (reason, Short::Slot);
978 }
979 match (left.memory, left.host, left.cpu) {
980 (Some(free), _, _) if free < signed(memory) => (
981 started.for_memory(
982 memory,
983 Waiting::Memory {
984 needs: memory,
985 free: unsigned(free),
986 },
987 ),
988 Short::Memory,
989 ),
990 (_, Some(free), _) if free < signed(memory) => (
991 started.for_host(
992 memory,
993 Waiting::HostMemory {
994 needs: memory,
995 free: unsigned(free),
996 },
997 ),
998 Short::Host,
999 ),
1000 (_, _, Some(free)) => (
1001 started.for_cpu(
1002 cpu,
1003 Waiting::Cpu {
1004 needs: cpu,
1005 free: unsigned(free),
1006 },
1007 ),
1008 Short::Cpu,
1009 ),
1010 (_, _, None) => (
1012 Waiting::NoSlot {
1013 profile: profile_name(),
1014 },
1015 Short::Slot,
1016 ),
1017 }
1018}
1019
1020fn start(
1023 repository: &Repository,
1024 job: u64,
1025 index: usize,
1026 memory: u64,
1027 cpu: u64,
1028 replacing: Vec<SlotRef>,
1029 barrier: Option<Barrier>,
1030) -> Decision {
1031 Decision::Start {
1032 slot: SlotRef {
1033 profile: repository.profile.clone(),
1034 index,
1035 },
1036 repository: repository.name.clone(),
1037 memory,
1038 cpu,
1039 for_: StartFor::Job(job),
1040 replacing,
1041 behind: barrier.map(|barrier| barrier.job),
1042 }
1043}
1044
1045fn start_warm(
1049 wanted: &[(&Repository, usize)],
1050 profiles: &BTreeMap<String, Profile>,
1051 taken: &mut BTreeMap<&str, Vec<bool>>,
1052 mut budgets: Budgets,
1053 decided: &mut Plan,
1054) {
1055 let room_wanted = decided.waiting.values().any(|reason| {
1056 matches!(
1057 reason,
1058 Waiting::NoSlot { .. }
1059 | Waiting::Memory { .. }
1060 | Waiting::HostMemory { .. }
1061 | Waiting::Cpu { .. }
1062 | Waiting::BehindCpu { .. }
1063 | Waiting::BehindMemory { .. }
1064 | Waiting::BehindStart { .. }
1065 )
1066 });
1067 if room_wanted {
1068 return;
1069 }
1070 for round in 0.. {
1071 let mut any = false;
1072 for (repository, wants) in wanted {
1073 if *wants <= round {
1074 continue;
1075 }
1076 let (Some(profile), Some(taken)) = (
1077 profiles.get(&repository.profile),
1078 taken.get_mut(repository.profile.as_str()),
1079 ) else {
1080 continue;
1081 };
1082 let (memory, cpu) = (profile.memory, profile.cpus);
1083 let Some(index) = taken.iter().position(|taken| !taken) else {
1084 continue;
1085 };
1086 if !budgets.left.fits(memory, cpu) {
1087 continue;
1088 }
1089 taken[index] = true;
1090 budgets.take(memory, cpu);
1091 any = true;
1092 decided.decisions.push(Decision::Start {
1093 slot: SlotRef {
1094 profile: repository.profile.clone(),
1095 index,
1096 },
1097 repository: repository.name.clone(),
1098 memory,
1099 cpu,
1100 for_: StartFor::Warm,
1101 replacing: Vec::new(),
1102 behind: None,
1103 });
1104 }
1105 if !any {
1106 break;
1107 }
1108 }
1109}
1110
1111#[derive(Debug, Clone, Copy)]
1114pub(crate) struct Left {
1115 pub(crate) memory: Option<i64>,
1116 pub(crate) cpu: Option<i64>,
1117 pub(crate) host: Option<i64>,
1119}
1120
1121impl Profile {
1122 fn caps(&self) -> Caps {
1124 Caps {
1125 memory: self.memory,
1126 cpu: self.cpus,
1127 }
1128 }
1129}
1130
1131impl Left {
1132 fn fits(self, memory: u64, cpu: u64) -> bool {
1133 let fits = |free: Option<i64>, needs: u64| free.is_none_or(|free| free >= signed(needs));
1134 fits(self.memory, memory) && fits(self.host, memory) && fits(self.cpu, cpu)
1135 }
1136
1137 fn short(self, memory: u64, cpu: u64) -> Left {
1140 let lacks = |free: Option<i64>, needs: u64| {
1141 free.map(|free| signed(needs).saturating_sub(free).max(0))
1142 };
1143 Left {
1144 memory: lacks(self.memory, memory).max(lacks(self.host, memory)),
1145 cpu: lacks(self.cpu, cpu),
1146 host: None,
1147 }
1148 }
1149
1150 fn take(&mut self, memory: u64, cpu: u64) {
1151 let take = |free: &mut Option<i64>, used: u64| {
1152 *free = free.map(|free| free.saturating_sub(signed(used)));
1153 };
1154 take(&mut self.memory, memory);
1155 take(&mut self.host, memory);
1156 take(&mut self.cpu, cpu);
1157 }
1158
1159 fn give(&mut self, memory: u64, cpu: u64) {
1160 let give = |free: &mut Option<i64>, freed: u64| {
1161 *free = free.map(|free| free.saturating_add(signed(freed)));
1162 };
1163 give(&mut self.memory, memory);
1164 give(&mut self.host, memory);
1165 give(&mut self.cpu, cpu);
1166 }
1167}
1168
1169fn left(budget: u64, in_use: u64) -> i64 {
1172 signed(budget).saturating_sub(signed(in_use))
1173}
1174
1175fn signed(amount: u64) -> i64 {
1177 i64::try_from(amount).unwrap_or(i64::MAX)
1178}
1179
1180fn unsigned(free: i64) -> u64 {
1182 u64::try_from(free).unwrap_or(0)
1183}
1184
1185struct Sorted {
1187 serve: Vec<u64>,
1188 warm: usize,
1189}
1190
1191fn oldest_first(repository: &Repository) -> Vec<&QueuedJob> {
1194 let mut matching: Vec<&QueuedJob> = repository
1195 .queued
1196 .iter()
1197 .filter(|job| matches(job, &repository.labels))
1198 .collect();
1199 matching.sort_by_key(|job| job.id);
1200 matching
1201}
1202
1203fn sort_out(
1207 repository: &Repository,
1208 profiles: &BTreeMap<String, Profile>,
1209 now: SystemTime,
1210 decided: &mut Plan,
1211) -> Option<Sorted> {
1212 let mut matching = oldest_first(repository);
1213 let profile = profiles.get(&repository.profile);
1214 let mut warm = repository.warm;
1215 if repository.paused {
1216 decided
1217 .waiting
1218 .extend(matching.iter().map(|job| (job.id, Waiting::Paused)));
1219 matching.clear();
1221 warm = 0;
1222 }
1223 let upkeep_due = profile.is_some_and(|profile| profile.upkeep_due);
1226 let stop_now = upkeep_due || repository.paused;
1227 if upkeep_due {
1228 warm = 0;
1229 }
1230 let (idle, closing): (Vec<(SlotRef, &RunnerSlot)>, Vec<_>) = profile
1231 .into_iter()
1232 .flat_map(|profile| profile.slots.iter().enumerate())
1233 .filter_map(|(index, slot)| match slot {
1234 Slot::Runner(runner) if runner.repository == repository.name && !runner.busy => Some((
1235 SlotRef {
1236 profile: repository.profile.clone(),
1237 index,
1238 },
1239 runner,
1240 )),
1241 _ => None,
1242 })
1243 .partition(|(slot, _)| profile.is_none_or(|profile| slot.index < profile.count));
1244 decided
1246 .decisions
1247 .extend(closing.into_iter().map(|(slot, _)| Decision::Stop {
1248 slot,
1249 reason: StopReason::Closed,
1250 }));
1251 let surplus = idle.len().saturating_sub(matching.len());
1252 let stops: Vec<SlotRef> = idle
1253 .iter()
1254 .filter(|(_, runner)| {
1255 stop_now
1256 || now
1257 .duration_since(runner.started_at)
1258 .is_ok_and(|waited| waited >= IDLE_TIMEOUT)
1259 })
1260 .take(surplus.saturating_sub(warm))
1261 .map(|(slot, _)| slot.clone())
1262 .collect();
1263 let kept: Vec<&SlotRef> = idle
1265 .iter()
1266 .map(|(slot, _)| slot)
1267 .filter(|slot| !stops.contains(slot))
1268 .collect();
1269 decided
1270 .warm
1271 .extend(kept.iter().skip(matching.len()).map(|slot| (*slot).clone()));
1272 let warm = warm.saturating_sub(kept.len().saturating_sub(matching.len()));
1273 decided
1274 .decisions
1275 .extend(stops.into_iter().map(|slot| Decision::Stop {
1276 slot,
1277 reason: if repository.paused {
1278 StopReason::Paused
1279 } else if upkeep_due {
1280 StopReason::Upkeep
1281 } else {
1282 StopReason::Expired
1283 },
1284 }));
1285 let missing = matching.len().saturating_sub(idle.len());
1286 let skip = matching.len() - missing;
1288 decided.waiting.extend(
1289 matching
1290 .iter()
1291 .take(skip)
1292 .map(|job| (job.id, Waiting::RunnerStarting)),
1293 );
1294 let serve = matching.iter().skip(skip).map(|job| job.id);
1295 match repository.held.filter(|held| held.until > now) {
1296 Some(held) => {
1297 let until = crate::time::ms(held.until) / 1000;
1298 decided.waiting.extend(serve.map(|job| {
1299 (
1300 job,
1301 Waiting::Backoff {
1302 until,
1303 cause: held.cause,
1304 },
1305 )
1306 }));
1307 None
1308 }
1309 None => Some(Sorted {
1310 serve: serve.collect(),
1311 warm,
1312 }),
1313 }
1314}
1315
1316struct Warm<'plan> {
1318 runners: Vec<Option<(SlotRef, &'plan RunnerSlot)>>,
1320}
1321
1322struct Room {
1324 stopped: Vec<SlotRef>,
1326 slot: Option<usize>,
1328 memory: u64,
1329 cpu: u64,
1330}
1331
1332impl<'plan> Warm<'plan> {
1333 fn new(
1335 warm: &BTreeSet<SlotRef>,
1336 profiles: &'plan BTreeMap<String, Profile>,
1337 held: bool,
1338 ) -> Warm<'plan> {
1339 let runners = warm
1340 .iter()
1341 .filter(|_| !held)
1342 .filter_map(
1343 |slot| match profiles.get(&slot.profile)?.slots.get(slot.index)? {
1344 Slot::Runner(runner) => Some(Some((slot.clone(), runner))),
1345 Slot::Free | Slot::Closed => None,
1346 },
1347 )
1348 .collect();
1349 Warm { runners }
1350 }
1351
1352 fn make_room(
1357 &mut self,
1358 repository: &Repository,
1359 slot: bool,
1360 budgets: &Budgets,
1361 needs_memory: u64,
1362 needs_cpu: u64,
1363 ) -> Option<Room> {
1364 let short = budgets.left.short(needs_memory, needs_cpu);
1365 let (memory, cpu) = (
1366 unsigned(short.memory.unwrap_or(0)),
1367 unsigned(short.cpu.unwrap_or(0)),
1368 );
1369 let mut candidates: Vec<usize> = self
1370 .runners
1371 .iter()
1372 .enumerate()
1373 .filter_map(|(at, runner)| {
1374 runner
1375 .as_ref()
1376 .filter(|(slot, runner)| {
1377 runner.repository != repository.name || slot.profile != repository.profile
1378 })
1379 .map(|_| at)
1380 })
1381 .collect();
1382 candidates.sort_by_key(|at| {
1384 self.runners[*at]
1385 .as_ref()
1386 .is_some_and(|(slot, _)| slot.profile != repository.profile)
1387 });
1388 let mut room = Room {
1389 stopped: Vec::new(),
1390 slot: None,
1391 memory: 0,
1392 cpu: 0,
1393 };
1394 let mut picked = Vec::new();
1395 for at in candidates {
1396 let short = (slot && room.slot.is_none()) || room.memory < memory || room.cpu < cpu;
1397 if !short {
1398 break;
1399 }
1400 let Some((ref_, runner)) = &self.runners[at] else {
1401 continue;
1402 };
1403 let gives_slot = ref_.profile == repository.profile;
1404 let helps = (gives_slot && slot && room.slot.is_none())
1406 || (room.memory < memory && runner.memory > 0)
1407 || (room.cpu < cpu && runner.cpu > 0);
1408 if !helps {
1409 continue;
1410 }
1411 if gives_slot && room.slot.is_none() {
1412 room.slot = Some(ref_.index);
1413 }
1414 room.memory += runner.memory;
1415 room.cpu += runner.cpu;
1416 room.stopped.push(ref_.clone());
1417 picked.push(at);
1418 }
1419 let mut after = budgets.clone();
1422 after.give(&room);
1423 if (slot && room.slot.is_none()) || !after.left.fits(needs_memory, needs_cpu) {
1424 return None;
1425 }
1426 for at in picked {
1427 self.runners[at] = None;
1428 }
1429 Some(room)
1430 }
1431}
1432
1433struct Started<'plan> {
1436 free_slots: BTreeSet<&'plan str>,
1438 before: Left,
1440 by_profile: BTreeMap<&'plan str, u64>,
1442 first: Option<u64>,
1443}
1444
1445impl<'plan> Started<'plan> {
1446 fn new(taken: &BTreeMap<&'plan str, Vec<bool>>, before: Left) -> Started<'plan> {
1447 Started {
1448 free_slots: taken
1449 .iter()
1450 .filter(|(_, slots)| slots.contains(&false))
1451 .map(|(name, _)| *name)
1452 .collect(),
1453 before,
1454 by_profile: BTreeMap::new(),
1455 first: None,
1456 }
1457 }
1458
1459 fn note(&mut self, profile: &'plan str, job: u64) {
1461 self.by_profile.entry(profile).or_insert(job);
1462 self.first.get_or_insert(job);
1463 }
1464
1465 fn for_slot(&self, profile: &str, reason: Waiting) -> Waiting {
1467 match self.by_profile.get(profile) {
1468 Some(older) if self.free_slots.contains(profile) => {
1469 Waiting::BehindStart { job: *older }
1470 }
1471 _ => reason,
1472 }
1473 }
1474
1475 fn for_memory(&self, needs: u64, reason: Waiting) -> Waiting {
1477 Self::behind(self.first, self.before.memory, needs).unwrap_or(reason)
1478 }
1479
1480 fn for_host(&self, needs: u64, reason: Waiting) -> Waiting {
1482 Self::behind(self.first, self.before.host, needs).unwrap_or(reason)
1483 }
1484
1485 fn for_cpu(&self, needs: u64, reason: Waiting) -> Waiting {
1487 Self::behind(self.first, self.before.cpu, needs).unwrap_or(reason)
1488 }
1489
1490 fn behind(first: Option<u64>, free: Option<i64>, needs: u64) -> Option<Waiting> {
1491 first
1492 .filter(|_| free.is_some_and(|free| free >= signed(needs)))
1493 .map(|job| Waiting::BehindStart { job })
1494 }
1495}
1496
1497fn taken_slots(profiles: &BTreeMap<String, Profile>) -> BTreeMap<&str, Vec<bool>> {
1499 profiles
1500 .iter()
1501 .map(|(name, profile)| {
1502 let taken = profile
1503 .slots
1504 .iter()
1505 .map(|slot| profile.preparing.is_some() || *slot != Slot::Free)
1506 .collect();
1507 (name.as_str(), taken)
1508 })
1509 .collect()
1510}
1511
1512#[cfg(test)]
1513mod tests;