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 priority;
14pub mod warm;
15
16use priority::{Around, Backfill, Candidate, Caps, Held, Older, Runner};
17pub use priority::{Barrier, Drained, PRIORITY_AFTER, SERVED_PRIORITY_AFTER, Scarce, Wait, Waits};
18
19pub const IDLE_TIMEOUT: Duration = Duration::from_secs(300);
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 waits: Waits,
75 pub usual: Option<Duration>,
78 pub warm: usize,
80}
81
82impl Repository {
83 pub fn pool(&self) -> Pool {
85 Pool {
86 repository: self.name.clone(),
87 profile: self.profile.clone(),
88 }
89 }
90}
91
92#[derive(Debug, Clone)]
94pub struct Profile {
95 pub memory: u64,
97 pub cpus: u64,
100 pub preparing: Option<Preparing>,
102 pub upkeep_due: bool,
105 pub count: usize,
107 pub slots: Vec<Slot>,
109 pub ran: Vec<Option<Key>>,
112}
113
114#[derive(Debug, Clone, Copy, PartialEq, Eq)]
116pub enum Preparing {
117 Reseeding,
119 PullingImage,
121}
122
123#[derive(Debug, Clone, PartialEq, Eq)]
125pub enum Slot {
126 Free,
128 Runner(RunnerSlot),
130 Closed,
133}
134
135#[derive(Debug, Clone, PartialEq, Eq)]
137pub struct RunnerSlot {
138 pub repository: String,
140 pub busy: bool,
142 pub started_at: SystemTime,
144 pub memory: u64,
146 pub cpu: u64,
148 pub usual: Option<Duration>,
150}
151
152#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
154pub struct SlotRef {
155 pub profile: String,
157 pub index: usize,
159}
160
161#[derive(Debug, Clone, PartialEq, Eq)]
163pub enum Decision {
164 Start {
166 slot: SlotRef,
168 repository: String,
170 memory: u64,
172 cpu: u64,
174 warm: bool,
176 replacing: Vec<SlotRef>,
179 behind: Option<u64>,
181 },
182 Stop {
184 slot: SlotRef,
186 reason: StopReason,
188 },
189}
190
191#[derive(Debug, Clone, PartialEq, Eq)]
194pub struct Demand {
195 pub pool: Pool,
197 pub job: u64,
199 pub scarce: Scarce,
201}
202
203#[derive(Debug, Clone, Copy, PartialEq, Eq)]
205pub enum StopReason {
206 Expired,
208 Room,
210 Upkeep,
212 Paused,
214 Closed,
216 Changed,
218 OverBudget,
220 Clean,
222 Shutdown,
224}
225
226impl StopReason {
227 pub fn as_str(self) -> &'static str {
229 match self {
230 StopReason::Expired => "expired",
231 StopReason::Room => "room",
232 StopReason::Upkeep => "upkeep",
233 StopReason::Paused => "paused",
234 StopReason::Closed => "closed",
235 StopReason::Changed => "changed",
236 StopReason::OverBudget => "over_budget",
237 StopReason::Clean => "clean",
238 StopReason::Shutdown => "shutdown",
239 }
240 }
241
242 pub fn words(self) -> &'static str {
244 match self {
245 StopReason::Expired => "no job came for it",
246 StopReason::Room => "a queued job takes its room",
247 StopReason::Upkeep => "its profile's upkeep waits for it",
248 StopReason::Paused => "its repository is paused",
249 StopReason::Closed => "its slot closed",
250 StopReason::Changed => "the config or runnerd changed its runners",
251 StopReason::OverBudget => "raised for a heavier job, it does not fit the budget",
252 StopReason::Clean => "a cache clean needs its volumes",
253 StopReason::Shutdown => "runnerd stops",
254 }
255 }
256}
257
258#[derive(Debug, Clone, Default, PartialEq, Eq)]
260pub struct Plan {
261 pub decisions: Vec<Decision>,
263 pub waiting: BTreeMap<u64, Waiting>,
267 pub warm: BTreeSet<SlotRef>,
269 pub slot_waiting: BTreeSet<u64>,
274 pub held: Vec<Demand>,
277 pub barrier: Option<Barrier>,
279}
280
281#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
283pub struct Budget {
284 pub memory: Option<i64>,
287 pub cpu: Option<i64>,
290 pub host: Option<i64>,
293 pub held: bool,
297 pub drained: Drained,
299 pub credit_room: u64,
302}
303
304const GITHUB_HOSTED: &[&str] = &[
310 "ubuntu-slim",
311 "ubuntu-latest",
312 "ubuntu-26.04",
313 "ubuntu-24.04",
314 "ubuntu-22.04",
315 "ubuntu-26.04-arm",
316 "ubuntu-24.04-arm",
317 "ubuntu-22.04-arm",
318 "windows-latest",
319 "windows-2025",
320 "windows-2025-vs2026",
321 "windows-2022",
322 "windows-11-arm",
323 "windows-11-vs2026-arm",
324 "macos-latest",
325 "macos-26",
326 "macos-15",
327 "macos-14",
328 "macos-26-intel",
329 "macos-15-intel",
330 "xcode-27",
331 "macos-latest-large",
332 "macos-26-large",
333 "macos-15-large",
334 "macos-14-large",
335 "macos-latest-xlarge",
336 "macos-26-xlarge",
337 "macos-15-xlarge",
338 "macos-14-xlarge",
339 "xcode-27-xlarge",
340];
341
342fn hosted_by_github(job: &QueuedJob) -> bool {
346 matches!(&job.labels[..], [label] if GITHUB_HOSTED.iter().any(|hosted| hosted.eq_ignore_ascii_case(label)))
347}
348
349pub fn matches(job: &QueuedJob, labels: &[String]) -> bool {
352 crate::config::labels_match(&job.labels, labels)
353}
354
355pub fn plan(
372 repositories: &[Repository],
373 profiles: &BTreeMap<String, Profile>,
374 budget: Budget,
375 now: SystemTime,
376) -> Plan {
377 let mut decided = Plan::default();
378 unserved(repositories, &mut decided);
379 let ToServe {
380 mut wanted,
381 jobs,
382 warm: warm_wanted,
383 } = to_serve(repositories, profiles, now, &mut decided);
384
385 let mut warm = Warm::new(&decided.warm, profiles, budget.held);
386 let mut taken = taken_slots(profiles);
387 let mut left = Left {
388 memory: budget.memory,
389 cpu: budget.cpu,
390 host: budget.host,
391 };
392 let mut started = Started::new(&taken, left);
393 let mut slot_bound = SlotBound::default();
394 let drained = (!budget.held).then_some(budget.drained);
396 let mut behind = Behind::new(profiles);
397 for (position, &(job, repository)) in jobs.iter().enumerate() {
398 let Some(missing) = wanted.get_mut(&pool_key(repository)) else {
399 continue;
400 };
401 if *missing == 0 {
402 continue;
403 }
404 let (Some(profile), Some(taken)) = (
405 profiles.get(&repository.profile),
406 taken.get_mut(repository.profile.as_str()),
407 ) else {
408 continue;
409 };
410 let memory = repository.runner_memory.unwrap_or(profile.memory);
411 let cpu = repository.runner_cpu.unwrap_or(profile.cpus);
412 let free_index = free_slot(taken, profile, repository, job, &jobs[position + 1..]);
413 let fits = free_index.is_some() && left.fits(memory, cpu);
414 let turn = Turn {
415 repository,
416 profile,
417 job,
418 memory,
419 cpu,
420 free_slot: free_index.is_some(),
421 left,
422 started: &started,
423 };
424 if let Some(barrier) = decided.barrier {
425 let candidate = Candidate {
426 profile: &repository.profile,
427 free_slots: taken.iter().filter(|taken| !**taken).count(),
428 usual: repository.usual,
429 caps: profile.caps(),
430 };
431 if !fits || !behind.admits(candidate) {
432 turn.behind(barrier, &mut decided);
433 continue;
434 }
435 }
436 let room = if fits || profile.preparing.is_some() {
437 None
438 } else {
439 warm.make_room(repository, free_index.is_none(), left, memory, cpu)
440 };
441 let index = match (room.as_ref(), free_index) {
442 (Some(room), free) => free.or(room.slot).unwrap_or_default(),
443 (None, Some(index)) if fits => index,
444 (None, _) => {
445 turn.waits(drained, &mut slot_bound, now, &mut decided);
446 let job = Older {
447 profile: &repository.profile,
448 free_slot: free_index.is_some() || profile.preparing.is_some(),
449 memory,
450 cpu,
451 };
452 behind.left_waiting(job, decided.barrier, left, &budget, now);
453 continue;
454 }
455 };
456 let replacing = room.map_or_else(Vec::new, |room| stop_for(room, &mut left, &mut decided));
457 taken[index] = true;
458 *missing -= 1;
459 started.note(&repository.profile, job);
460 left.take(memory, cpu);
461 behind.started(&repository.profile, profile.caps(), memory, cpu, now);
462 decided.decisions.push(start(
463 repository,
464 index,
465 memory,
466 cpu,
467 replacing,
468 decided.barrier,
469 ));
470 }
471 if !budget.held {
472 start_warm(&warm_wanted, profiles, &mut taken, left, &mut decided);
473 }
474 decided
475}
476
477fn stop_for(room: Room, left: &mut Left, decided: &mut Plan) -> Vec<SlotRef> {
479 left.give(room.memory, room.cpu);
480 for slot in &room.stopped {
481 decided.warm.remove(slot);
482 decided.decisions.push(Decision::Stop {
483 slot: slot.clone(),
484 reason: StopReason::Room,
485 });
486 }
487 room.stopped
488}
489
490struct Behind<'plan> {
492 runners: Vec<Runner<'plan>>,
494 older: Vec<Older<'plan>>,
496 backfill: Option<Backfill<'plan>>,
498}
499
500impl<'plan> Behind<'plan> {
501 fn new(profiles: &'plan BTreeMap<String, Profile>) -> Behind<'plan> {
503 let mut runners = Vec::new();
504 for (name, profile) in profiles {
505 for slot in &profile.slots {
506 if let Slot::Runner(runner) = slot {
507 runners.push(Runner {
508 profile: name,
509 started_at: runner.started_at,
510 usual: runner.usual.filter(|_| runner.busy),
511 memory: runner.memory,
512 cpu: runner.cpu,
513 caps: profile.caps(),
514 });
515 }
516 }
517 }
518 Behind {
519 runners,
520 older: Vec::new(),
521 backfill: None,
522 }
523 }
524
525 fn left_waiting(
527 &mut self,
528 job: Older<'plan>,
529 barrier: Option<Barrier>,
530 left: Left,
531 budget: &Budget,
532 now: SystemTime,
533 ) {
534 let Some(barrier) = barrier else {
535 self.older.push(job);
536 return;
537 };
538 let around = Around {
539 left,
540 credit_room: budget.credit_room,
541 drained: budget.drained,
542 runners: &self.runners,
543 older: &self.older,
544 };
545 self.backfill = Backfill::behind(barrier, job.profile, around, now);
546 }
547
548 fn admits(&mut self, candidate: Candidate<'_>) -> bool {
550 let backfill = self.backfill.as_mut();
551 backfill.is_some_and(|backfill| backfill.admits(candidate))
552 }
553
554 fn started(&mut self, profile: &'plan str, caps: Caps, memory: u64, cpu: u64, now: SystemTime) {
557 self.runners.push(Runner {
558 profile,
559 started_at: now,
560 usual: None,
561 memory,
562 cpu,
563 caps,
564 });
565 }
566}
567
568struct ToServe<'plan> {
570 wanted: BTreeMap<(&'plan str, &'plan str), usize>,
572 jobs: Vec<(u64, &'plan Repository)>,
574 warm: Vec<(&'plan Repository, usize)>,
576}
577
578fn to_serve<'plan>(
580 repositories: &'plan [Repository],
581 profiles: &BTreeMap<String, Profile>,
582 now: SystemTime,
583 decided: &mut Plan,
584) -> ToServe<'plan> {
585 let mut serve = ToServe {
586 wanted: BTreeMap::new(),
587 jobs: Vec::new(),
588 warm: Vec::new(),
589 };
590 for repository in repositories {
591 if let Some(sorted) = sort_out(repository, profiles, now, decided) {
592 serve
593 .wanted
594 .insert(pool_key(repository), sorted.serve.len());
595 serve
596 .jobs
597 .extend(sorted.serve.into_iter().map(|job| (job, repository)));
598 serve.warm.push((repository, sorted.warm));
599 }
600 }
601 serve.jobs.sort_by_key(|(id, _)| *id);
602 serve
603}
604
605#[derive(Debug, Default)]
608struct SlotBound {
609 memory: u64,
610 cpu: u64,
611}
612
613impl SlotBound {
614 fn takes(&mut self, left: Left, memory: u64, cpu: u64) -> bool {
616 let mut spare = left;
617 spare.take(self.memory, self.cpu);
618 let fits = spare.fits(memory, cpu);
619 if fits {
620 self.memory = self.memory.saturating_add(memory);
621 self.cpu = self.cpu.saturating_add(cpu);
622 }
623 fits
624 }
625}
626
627fn free_slot(
633 taken: &[bool],
634 profile: &Profile,
635 repository: &Repository,
636 job: u64,
637 later: &[(u64, &Repository)],
638) -> Option<usize> {
639 let ran = |index: usize| profile.ran.get(index).and_then(Option::as_ref);
640 let ran_it = |index: usize, repository: &Repository, job: u64| {
641 let queued = repository.queued.iter().find(|queued| queued.id == job);
642 queued.zip(ran(index)).is_some_and(|(queued, key)| {
643 key.repository == repository.name
644 && key.workflow == queued.workflow
645 && key.name == queued.name
646 })
647 };
648 taken
649 .iter()
650 .enumerate()
651 .filter(|(_, taken)| !**taken)
652 .map(|(index, _)| index)
653 .min_by_key(|&index| {
654 let wanted_later = later.iter().any(|&(id, other)| {
655 other.profile == repository.profile && ran_it(index, other, id)
656 });
657 let same_repository = ran(index).is_some_and(|key| key.repository == repository.name);
658 (
659 !ran_it(index, repository, job),
660 wanted_later,
661 !same_repository,
662 index,
663 )
664 })
665}
666
667fn hold(repository: &Repository, job: u64, scarce: Scarce, decided: &mut Plan) {
669 let pool = repository.pool();
670 let held = decided
671 .held
672 .iter()
673 .any(|demand| demand.pool == pool && demand.scarce == scarce);
674 if !held {
675 decided.held.push(Demand { pool, job, scarce });
676 }
677}
678
679struct Turn<'plan> {
681 repository: &'plan Repository,
682 profile: &'plan Profile,
683 job: u64,
684 memory: u64,
685 cpu: u64,
687 free_slot: bool,
688 left: Left,
689 started: &'plan Started<'plan>,
690}
691
692impl Turn<'_> {
693 fn why(&self) -> (Waiting, Short) {
695 why_waits(
696 &self.repository.profile,
697 self.profile,
698 self.free_slot,
699 self.memory,
700 self.cpu,
701 self.left,
702 self.started,
703 )
704 }
705
706 fn waits(
709 self,
710 drained: Option<Drained>,
711 slot_bound: &mut SlotBound,
712 now: SystemTime,
713 decided: &mut Plan,
714 ) {
715 let (reason, short) = self.why();
716 decided.waiting.insert(self.job, reason);
717 if !self.free_slot
718 && self.profile.preparing.is_none()
719 && slot_bound.takes(self.left, self.memory, self.cpu)
720 {
721 decided.slot_waiting.insert(self.job);
722 }
723 let Some(scarce) = short.scarce() else {
724 return;
725 };
726 if drained.is_some() {
727 hold(self.repository, self.job, scarce, decided);
728 }
729 decided.barrier = Barrier::of(
730 priority::Short {
731 job: self.job,
732 scarce,
733 held: short.held(),
734 memory: self.memory,
735 cpu: self.cpu,
736 },
737 &self.repository.waits,
738 drained,
739 now,
740 );
741 }
742
743 fn behind(self, barrier: Barrier, decided: &mut Plan) {
747 if self.free_slot && self.left.fits(self.memory, self.cpu) {
748 decided.waiting.insert(self.job, barrier.reason());
749 return;
750 }
751 let (reason, short) = self.why();
752 let reason = if self.free_slot {
753 barrier.reason()
754 } else {
755 reason
756 };
757 decided.waiting.insert(self.job, reason);
758 if let Some(scarce) = short.scarce() {
759 hold(self.repository, self.job, scarce, decided);
760 }
761 }
762}
763
764fn pool_key(repository: &Repository) -> (&str, &str) {
766 (&repository.name, &repository.profile)
767}
768
769fn unserved(repositories: &[Repository], decided: &mut Plan) {
771 let mut seen = BTreeSet::new();
772 for repository in repositories {
773 if !seen.insert(repository.name.as_str()) {
774 continue;
775 }
776 let pools: Vec<&Repository> = repositories
777 .iter()
778 .filter(|pool| pool.name == repository.name)
779 .collect();
780 decided.waiting.extend(
781 repository
782 .queued
783 .iter()
784 .filter(|job| {
785 !hosted_by_github(job) && !pools.iter().any(|pool| matches(job, &pool.labels))
786 })
787 .map(|job| {
788 (
789 job.id,
790 Waiting::NoPool {
791 labels: job.labels.clone(),
792 },
793 )
794 }),
795 );
796 }
797}
798
799#[derive(Debug, Clone, Copy, PartialEq, Eq)]
801enum Short {
802 Slot,
803 Memory,
804 Host,
805 Cpu,
806}
807
808impl Short {
809 fn scarce(self) -> Option<Scarce> {
811 match self {
812 Short::Slot => None,
813 Short::Memory | Short::Host => Some(Scarce::Memory),
814 Short::Cpu => Some(Scarce::Cpu),
815 }
816 }
817
818 fn held(self) -> Held {
820 match self {
821 Short::Host => Held::ByHost,
822 Short::Slot | Short::Memory | Short::Cpu => Held::ByBudget,
823 }
824 }
825}
826
827fn why_waits(
830 name: &str,
831 profile: &Profile,
832 free_slot: bool,
833 memory: u64,
834 cpu: u64,
835 left: Left,
836 started: &Started<'_>,
837) -> (Waiting, Short) {
838 let profile_name = || name.to_owned();
839 if !free_slot {
840 let reason = match profile.preparing {
841 Some(Preparing::Reseeding) => Waiting::Reseeding {
842 profile: profile_name(),
843 },
844 Some(Preparing::PullingImage) => Waiting::PullingImage {
845 profile: profile_name(),
846 },
847 None => started.for_slot(
848 name,
849 Waiting::NoSlot {
850 profile: profile_name(),
851 },
852 ),
853 };
854 return (reason, Short::Slot);
855 }
856 match (left.memory, left.host, left.cpu) {
857 (Some(free), _, _) if free < signed(memory) => (
858 started.for_memory(
859 memory,
860 Waiting::Memory {
861 needs: memory,
862 free: unsigned(free),
863 },
864 ),
865 Short::Memory,
866 ),
867 (_, Some(free), _) if free < signed(memory) => (
868 started.for_host(
869 memory,
870 Waiting::HostMemory {
871 needs: memory,
872 free: unsigned(free),
873 },
874 ),
875 Short::Host,
876 ),
877 (_, _, Some(free)) => (
878 started.for_cpu(
879 cpu,
880 Waiting::Cpu {
881 needs: cpu,
882 free: unsigned(free),
883 },
884 ),
885 Short::Cpu,
886 ),
887 (_, _, None) => (
889 Waiting::NoSlot {
890 profile: profile_name(),
891 },
892 Short::Slot,
893 ),
894 }
895}
896
897fn start(
900 repository: &Repository,
901 index: usize,
902 memory: u64,
903 cpu: u64,
904 replacing: Vec<SlotRef>,
905 barrier: Option<Barrier>,
906) -> Decision {
907 Decision::Start {
908 slot: SlotRef {
909 profile: repository.profile.clone(),
910 index,
911 },
912 repository: repository.name.clone(),
913 memory,
914 cpu,
915 warm: false,
916 replacing,
917 behind: barrier.map(|barrier| barrier.job),
918 }
919}
920
921fn start_warm(
925 wanted: &[(&Repository, usize)],
926 profiles: &BTreeMap<String, Profile>,
927 taken: &mut BTreeMap<&str, Vec<bool>>,
928 mut left: Left,
929 decided: &mut Plan,
930) {
931 let room_wanted = decided.waiting.values().any(|reason| {
932 matches!(
933 reason,
934 Waiting::NoSlot { .. }
935 | Waiting::Memory { .. }
936 | Waiting::HostMemory { .. }
937 | Waiting::Cpu { .. }
938 | Waiting::BehindCpu { .. }
939 | Waiting::BehindMemory { .. }
940 | Waiting::BehindStart { .. }
941 )
942 });
943 if room_wanted {
944 return;
945 }
946 for round in 0.. {
947 let mut any = false;
948 for (repository, wants) in wanted {
949 if *wants <= round {
950 continue;
951 }
952 let (Some(profile), Some(taken)) = (
953 profiles.get(&repository.profile),
954 taken.get_mut(repository.profile.as_str()),
955 ) else {
956 continue;
957 };
958 let (memory, cpu) = (profile.memory, profile.cpus);
959 let Some(index) = taken.iter().position(|taken| !taken) else {
960 continue;
961 };
962 if !left.fits(memory, cpu) {
963 continue;
964 }
965 taken[index] = true;
966 left.take(memory, cpu);
967 any = true;
968 decided.decisions.push(Decision::Start {
969 slot: SlotRef {
970 profile: repository.profile.clone(),
971 index,
972 },
973 repository: repository.name.clone(),
974 memory,
975 cpu,
976 warm: true,
977 replacing: Vec::new(),
978 behind: None,
979 });
980 }
981 if !any {
982 break;
983 }
984 }
985}
986
987#[derive(Debug, Clone, Copy)]
990pub(crate) struct Left {
991 pub(crate) memory: Option<i64>,
992 pub(crate) cpu: Option<i64>,
993 pub(crate) host: Option<i64>,
995}
996
997impl Profile {
998 fn caps(&self) -> Caps {
1000 Caps {
1001 memory: self.memory,
1002 cpu: self.cpus,
1003 }
1004 }
1005}
1006
1007impl Left {
1008 fn fits(self, memory: u64, cpu: u64) -> bool {
1009 let fits = |free: Option<i64>, needs: u64| free.is_none_or(|free| free >= signed(needs));
1010 fits(self.memory, memory) && fits(self.host, memory) && fits(self.cpu, cpu)
1011 }
1012
1013 fn short(self, memory: u64, cpu: u64) -> Left {
1016 let lacks = |free: Option<i64>, needs: u64| {
1017 free.map(|free| signed(needs).saturating_sub(free).max(0))
1018 };
1019 Left {
1020 memory: lacks(self.memory, memory).max(lacks(self.host, memory)),
1021 cpu: lacks(self.cpu, cpu),
1022 host: None,
1023 }
1024 }
1025
1026 fn take(&mut self, memory: u64, cpu: u64) {
1027 let take = |free: &mut Option<i64>, used: u64| {
1028 *free = free.map(|free| free.saturating_sub(signed(used)));
1029 };
1030 take(&mut self.memory, memory);
1031 take(&mut self.host, memory);
1032 take(&mut self.cpu, cpu);
1033 }
1034
1035 fn give(&mut self, memory: u64, cpu: u64) {
1036 let give = |free: &mut Option<i64>, freed: u64| {
1037 *free = free.map(|free| free.saturating_add(signed(freed)));
1038 };
1039 give(&mut self.memory, memory);
1040 give(&mut self.host, memory);
1041 give(&mut self.cpu, cpu);
1042 }
1043}
1044
1045fn left(budget: u64, in_use: u64) -> i64 {
1048 signed(budget).saturating_sub(signed(in_use))
1049}
1050
1051fn signed(amount: u64) -> i64 {
1053 i64::try_from(amount).unwrap_or(i64::MAX)
1054}
1055
1056fn unsigned(free: i64) -> u64 {
1058 u64::try_from(free).unwrap_or(0)
1059}
1060
1061struct Sorted {
1063 serve: Vec<u64>,
1064 warm: usize,
1065}
1066
1067fn sort_out(
1071 repository: &Repository,
1072 profiles: &BTreeMap<String, Profile>,
1073 now: SystemTime,
1074 decided: &mut Plan,
1075) -> Option<Sorted> {
1076 let mut matching: Vec<&QueuedJob> = repository
1077 .queued
1078 .iter()
1079 .filter(|job| matches(job, &repository.labels))
1080 .collect();
1081 let profile = profiles.get(&repository.profile);
1082 let mut warm = repository.warm;
1083 if repository.paused {
1084 decided
1085 .waiting
1086 .extend(matching.iter().map(|job| (job.id, Waiting::Paused)));
1087 matching.clear();
1089 warm = 0;
1090 }
1091 let upkeep_due = profile.is_some_and(|profile| profile.upkeep_due);
1094 let stop_now = upkeep_due || repository.paused;
1095 if upkeep_due {
1096 warm = 0;
1097 }
1098 let (idle, closing): (Vec<(SlotRef, &RunnerSlot)>, Vec<_>) = profile
1099 .into_iter()
1100 .flat_map(|profile| profile.slots.iter().enumerate())
1101 .filter_map(|(index, slot)| match slot {
1102 Slot::Runner(runner) if runner.repository == repository.name && !runner.busy => Some((
1103 SlotRef {
1104 profile: repository.profile.clone(),
1105 index,
1106 },
1107 runner,
1108 )),
1109 _ => None,
1110 })
1111 .partition(|(slot, _)| profile.is_none_or(|profile| slot.index < profile.count));
1112 decided
1114 .decisions
1115 .extend(closing.into_iter().map(|(slot, _)| Decision::Stop {
1116 slot,
1117 reason: StopReason::Closed,
1118 }));
1119 let surplus = idle.len().saturating_sub(matching.len());
1120 let stops: Vec<SlotRef> = idle
1121 .iter()
1122 .filter(|(_, runner)| {
1123 stop_now
1124 || now
1125 .duration_since(runner.started_at)
1126 .is_ok_and(|waited| waited >= IDLE_TIMEOUT)
1127 })
1128 .take(surplus.saturating_sub(warm))
1129 .map(|(slot, _)| slot.clone())
1130 .collect();
1131 let kept: Vec<&SlotRef> = idle
1133 .iter()
1134 .map(|(slot, _)| slot)
1135 .filter(|slot| !stops.contains(slot))
1136 .collect();
1137 decided
1138 .warm
1139 .extend(kept.iter().skip(matching.len()).map(|slot| (*slot).clone()));
1140 let warm = warm.saturating_sub(kept.len().saturating_sub(matching.len()));
1141 decided
1142 .decisions
1143 .extend(stops.into_iter().map(|slot| Decision::Stop {
1144 slot,
1145 reason: if repository.paused {
1146 StopReason::Paused
1147 } else if upkeep_due {
1148 StopReason::Upkeep
1149 } else {
1150 StopReason::Expired
1151 },
1152 }));
1153 let missing = matching.len().saturating_sub(idle.len());
1154 let skip = matching.len() - missing;
1156 decided.waiting.extend(
1157 matching
1158 .iter()
1159 .take(skip)
1160 .map(|job| (job.id, Waiting::RunnerStarting)),
1161 );
1162 let serve = matching.iter().skip(skip).map(|job| job.id);
1163 match repository.held.filter(|held| held.until > now) {
1164 Some(held) => {
1165 let until = crate::time::ms(held.until) / 1000;
1166 decided.waiting.extend(serve.map(|job| {
1167 (
1168 job,
1169 Waiting::Backoff {
1170 until,
1171 cause: held.cause,
1172 },
1173 )
1174 }));
1175 None
1176 }
1177 None => Some(Sorted {
1178 serve: serve.collect(),
1179 warm,
1180 }),
1181 }
1182}
1183
1184struct Warm<'plan> {
1186 runners: Vec<Option<(SlotRef, &'plan RunnerSlot)>>,
1188}
1189
1190struct Room {
1192 stopped: Vec<SlotRef>,
1194 slot: Option<usize>,
1196 memory: u64,
1197 cpu: u64,
1198}
1199
1200impl<'plan> Warm<'plan> {
1201 fn new(
1203 warm: &BTreeSet<SlotRef>,
1204 profiles: &'plan BTreeMap<String, Profile>,
1205 held: bool,
1206 ) -> Warm<'plan> {
1207 let runners = warm
1208 .iter()
1209 .filter(|_| !held)
1210 .filter_map(
1211 |slot| match profiles.get(&slot.profile)?.slots.get(slot.index)? {
1212 Slot::Runner(runner) => Some(Some((slot.clone(), runner))),
1213 Slot::Free | Slot::Closed => None,
1214 },
1215 )
1216 .collect();
1217 Warm { runners }
1218 }
1219
1220 fn make_room(
1225 &mut self,
1226 repository: &Repository,
1227 slot: bool,
1228 left: Left,
1229 needs_memory: u64,
1230 needs_cpu: u64,
1231 ) -> Option<Room> {
1232 let short = left.short(needs_memory, needs_cpu);
1233 let (memory, cpu) = (
1234 unsigned(short.memory.unwrap_or(0)),
1235 unsigned(short.cpu.unwrap_or(0)),
1236 );
1237 let mut candidates: Vec<usize> = self
1238 .runners
1239 .iter()
1240 .enumerate()
1241 .filter_map(|(at, runner)| {
1242 runner
1243 .as_ref()
1244 .filter(|(slot, runner)| {
1245 runner.repository != repository.name || slot.profile != repository.profile
1246 })
1247 .map(|_| at)
1248 })
1249 .collect();
1250 candidates.sort_by_key(|at| {
1252 self.runners[*at]
1253 .as_ref()
1254 .is_some_and(|(slot, _)| slot.profile != repository.profile)
1255 });
1256 let mut room = Room {
1257 stopped: Vec::new(),
1258 slot: None,
1259 memory: 0,
1260 cpu: 0,
1261 };
1262 let mut picked = Vec::new();
1263 for at in candidates {
1264 let short = (slot && room.slot.is_none()) || room.memory < memory || room.cpu < cpu;
1265 if !short {
1266 break;
1267 }
1268 let Some((ref_, runner)) = &self.runners[at] else {
1269 continue;
1270 };
1271 let gives_slot = ref_.profile == repository.profile;
1272 let helps = (gives_slot && slot && room.slot.is_none())
1274 || (room.memory < memory && runner.memory > 0)
1275 || (room.cpu < cpu && runner.cpu > 0);
1276 if !helps {
1277 continue;
1278 }
1279 if gives_slot && room.slot.is_none() {
1280 room.slot = Some(ref_.index);
1281 }
1282 room.memory += runner.memory;
1283 room.cpu += runner.cpu;
1284 room.stopped.push(ref_.clone());
1285 picked.push(at);
1286 }
1287 let mut after = left;
1289 after.give(room.memory, room.cpu);
1290 if (slot && room.slot.is_none()) || !after.fits(needs_memory, needs_cpu) {
1291 return None;
1292 }
1293 for at in picked {
1294 self.runners[at] = None;
1295 }
1296 Some(room)
1297 }
1298}
1299
1300struct Started<'plan> {
1303 free_slots: BTreeSet<&'plan str>,
1305 before: Left,
1307 by_profile: BTreeMap<&'plan str, u64>,
1309 first: Option<u64>,
1310}
1311
1312impl<'plan> Started<'plan> {
1313 fn new(taken: &BTreeMap<&'plan str, Vec<bool>>, before: Left) -> Started<'plan> {
1314 Started {
1315 free_slots: taken
1316 .iter()
1317 .filter(|(_, slots)| slots.contains(&false))
1318 .map(|(name, _)| *name)
1319 .collect(),
1320 before,
1321 by_profile: BTreeMap::new(),
1322 first: None,
1323 }
1324 }
1325
1326 fn note(&mut self, profile: &'plan str, job: u64) {
1328 self.by_profile.entry(profile).or_insert(job);
1329 self.first.get_or_insert(job);
1330 }
1331
1332 fn for_slot(&self, profile: &str, reason: Waiting) -> Waiting {
1334 match self.by_profile.get(profile) {
1335 Some(older) if self.free_slots.contains(profile) => {
1336 Waiting::BehindStart { job: *older }
1337 }
1338 _ => reason,
1339 }
1340 }
1341
1342 fn for_memory(&self, needs: u64, reason: Waiting) -> Waiting {
1344 Self::behind(self.first, self.before.memory, needs).unwrap_or(reason)
1345 }
1346
1347 fn for_host(&self, needs: u64, reason: Waiting) -> Waiting {
1349 Self::behind(self.first, self.before.host, needs).unwrap_or(reason)
1350 }
1351
1352 fn for_cpu(&self, needs: u64, reason: Waiting) -> Waiting {
1354 Self::behind(self.first, self.before.cpu, needs).unwrap_or(reason)
1355 }
1356
1357 fn behind(first: Option<u64>, free: Option<i64>, needs: u64) -> Option<Waiting> {
1358 first
1359 .filter(|_| free.is_some_and(|free| free >= signed(needs)))
1360 .map(|job| Waiting::BehindStart { job })
1361 }
1362}
1363
1364fn taken_slots(profiles: &BTreeMap<String, Profile>) -> BTreeMap<&str, Vec<bool>> {
1366 profiles
1367 .iter()
1368 .map(|(name, profile)| {
1369 let taken = profile
1370 .slots
1371 .iter()
1372 .map(|slot| profile.preparing.is_some() || *slot != Slot::Free)
1373 .collect();
1374 (name.as_str(), taken)
1375 })
1376 .collect()
1377}
1378
1379#[cfg(test)]
1380mod tests;