1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
//! What:
//! How many workers a set of independent items may use together: the CPUs the process is allowed minus a margin, the memory
//! that is free, an optional ceiling the shared storage was measured to need, and the person's own cap.
//! Why:
//! Real jobs may use almost the whole host, so a bare constant is wrong in both directions: too low on a large host, too high
//! inside a container with a quota or on a host whose memory other sessions already hold. The budget is derived from the
//! facts of the moment, and the facts are a value so a control can state them.
//!
//! In TS you'd write (pseudocode):
//! ```ts
//! const workers = workerBudget({ items: 48, perItemMemory: 256 * MiB, ceiling: undefined, cap: undefined, host: readHost() });
//! ```
use std::path::{Path, PathBuf};
/// The share of the CPUs the process is allowed that stays free: one in this many, at least one when there are more than two.
const CPU_MARGIN_DIVISOR: usize = 8;
/// The fraction of the memory that is free which the items may use together: one over this many. The rest stays for the
/// operating system's caches and for the other sessions of the host.
const MEMORY_SHARE_DIVISOR: u64 = 2;
/// Where the kernel lists the memory it can still give out.
const MEMORY_INFORMATION: &str = "/proc/meminfo";
/// Where the kernel names the control group of the process.
const CONTROL_GROUP_NAME: &str = "/proc/self/cgroup";
/// The root of the unified control-group hierarchy.
const CONTROL_GROUP_ROOT: &str = "/sys/fs/cgroup";
/// What:
/// The facts a budget is derived from.
/// Why:
/// Reading the host is one place and the arithmetic another, so a control states a host of any size.
///
/// In TS you'd write (pseudocode):
/// ```ts
/// type HostResources = { parallelism: number; memoryAvailable?: number };
/// ```
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub struct HostResources {
/// The threads the process may run at once (a container's CPU quota included).
pub parallelism: usize,
/// The bytes that can still be given out without pushing others out, or nothing when the host does not say.
pub memory_available: Option<u64>,
}
/// What:
/// What one budget asks for.
/// Why:
/// One value keeps the call sites short and names every input.
///
/// In TS you'd write (pseudocode):
/// ```ts
/// type BudgetRequest = { items: number; perItemMemory: number; ceiling?: number; cap?: number; host: HostResources };
/// ```
#[derive(Clone, Copy, Debug)]
pub struct BudgetRequest<'host> {
/// How many independent items there are; more workers than items would idle.
pub items: usize,
/// The bytes one item holds at its peak, a measured figure of the caller.
pub per_item_memory: u64,
/// The most workers the shared storage was measured to use usefully, or nothing when it was not measured to flatten.
pub ceiling: Option<usize>,
/// The most workers the person allows (`--jobs`), or nothing.
pub cap: Option<usize>,
/// The facts of this host now.
pub host: &'host HostResources,
}
impl HostResources {
/// What:
/// The resources of this process now: the threads it may run, and the least of the system's available memory and the
/// room left in its control group and the groups above it.
/// Why:
/// The memory figure that matters is the one the kernel would enforce, which a quota can make smaller than the host's.
///
/// In TS you'd write (pseudocode):
/// ```ts
/// const host = HostResources.read();
/// ```
pub fn read() -> HostResources {
let parallelism: usize = std::thread::available_parallelism().map_or(1, std::num::NonZeroUsize::get);
let system: Option<u64> = std::fs::read_to_string(MEMORY_INFORMATION).ok().and_then(|text: String| { return memory_available_from(text.as_str()); });
let group: Option<u64> = std::fs::read_to_string(CONTROL_GROUP_NAME)
.ok()
.and_then(|text: String| { return control_group_path(text.as_str()); })
.and_then(|path: String| { return group_headroom(Path::new(CONTROL_GROUP_ROOT), path.as_str()); });
let memory_available: Option<u64> = match (system, group) {
(Some(left), Some(right)) => Some(left.min(right)),
(left, right) => left.or(right),
};
return HostResources { parallelism, memory_available };
}
}
/// The `MemAvailable` figure of `/proc/meminfo` text, in bytes.
pub fn memory_available_from(text: &str) -> Option<u64> {
let line: &str = text.lines().find(|candidate: &&str| { return candidate.starts_with("MemAvailable:"); })?;
let kibibytes: u64 = line.split_whitespace().nth(1)?.parse().ok()?;
return kibibytes.checked_mul(1024);
}
/// The path of the unified (version 2) control group in `/proc/self/cgroup` text: the line that starts with `0::`.
pub fn control_group_path(text: &str) -> Option<String> {
return text.lines().find_map(|line: &str| { return line.strip_prefix("0::").map(String::from); });
}
/// The bytes a control group can still take under its limit: `max` minus `current`, nothing when there is no numeric limit.
pub fn headroom_from(max: &str, current: &str) -> Option<u64> {
let limit: u64 = max.trim().parse().ok()?;
let used: u64 = current.trim().parse().ok()?;
return Some(limit.saturating_sub(used));
}
/// The least headroom of the group at `path` below `root` and of every group above it, nothing when none has a limit.
fn group_headroom(root: &Path, path: &str) -> Option<u64> {
let mut least: Option<u64> = None;
let mut directory: PathBuf = root.join(path.trim_start_matches('/'));
loop {
let limit: Option<String> = std::fs::read_to_string(directory.join("memory.max")).ok();
let current: Option<String> = std::fs::read_to_string(directory.join("memory.current")).ok();
if let (Some(max_text), Some(current_text)) = (limit, current)
&& let Some(room) = headroom_from(max_text.as_str(), current_text.as_str())
{
least = Some(least.map_or(room, |known: u64| { return known.min(room); }));
}
if directory == root || !directory.pop() || !directory.starts_with(root) {
break;
}
}
return least;
}
/// The threads left free for everything else: an eighth of them, at least one, and none when the process may run only two.
pub fn cpu_margin(parallelism: usize) -> usize {
if parallelism <= 2 {
return 0;
}
return (parallelism / CPU_MARGIN_DIVISOR).max(1);
}
/// What:
/// The number of workers for independent items.
/// Why:
/// The least of the items, the CPUs minus the margin, the memory that is free over what one item holds, the ceiling the
/// storage was measured to use, and the person's cap; never fewer than one, so a starved host still makes progress.
///
/// In TS you'd write (pseudocode):
/// ```ts
/// const workers = Math.max(1, Math.min(items, cpus - margin, memoryShare / perItem, ceiling, cap));
/// ```
pub fn worker_budget(request: &BudgetRequest<'_>) -> usize {
let by_cpu: usize = request.host.parallelism.saturating_sub(cpu_margin(request.host.parallelism)).max(1);
let by_memory: usize = match request.host.memory_available {
Some(bytes) => usize::try_from((bytes / MEMORY_SHARE_DIVISOR) / request.per_item_memory.max(1)).unwrap_or(usize::MAX),
None => usize::MAX,
};
return request
.items
.min(by_cpu)
.min(by_memory)
.min(request.ceiling.unwrap_or(usize::MAX))
.min(request.cap.unwrap_or(usize::MAX))
.max(1);
}
/// The bytes one slice of a file-copy or file-removal job holds at its peak: a batch of entries and the handles it opens, estimated
/// at sixteen mebibytes.
pub const SLICE_MEMORY: u64 = 16 << 20;
/// What:
/// The workers for file-tree jobs that split their entries into slices: the host's budget up to a ceiling the filesystem was
/// measured or chosen to use.
/// Why:
/// The copy, install and removal of a worktree's files share the filesystem's metadata locks, so a ceiling stays, but the CPUs
/// left free for other sessions and the memory of the control group bound them too, which a bare `min(available, 8)` ignored.
///
/// In TS you'd write (pseudocode):
/// ```ts
/// const workers = slicedWorkers({ items, ceiling: 8, host });
/// ```
pub fn sliced_workers(items: usize, ceiling: usize, host: &HostResources) -> usize {
return worker_budget(&BudgetRequest { items, per_item_memory: SLICE_MEMORY, ceiling: Some(ceiling), cap: None, host });
}
/// Budget controls stay out of the release executable.
#[cfg(test)]
#[path = "parallel_budget_tests.rs"]
mod tests;