use std::collections::BTreeMap;
use std::sync::Mutex;
use knot_git::{GitError, MAX_TREE_DEPTH};
use super::packs::Reader;
use super::revindex::Order;
use super::writer::{Changed, Fill, ROOT_PATH, child_bit, fill_tree, path_of};
use super::{BitPosition, Bitset};
struct Task {
roots: Vec<BitPosition>,
path: u64,
depth: usize,
weight: usize,
branching: bool,
}
pub(super) fn fill<R: Order + Sync>(
reader: &mut Reader<'_, R>,
roots: Vec<gix::ObjectId>,
bits: &mut Bitset,
workers: usize,
) -> Result<(), GitError> {
let rev = reader.rev();
let roots = roots
.iter()
.filter_map(|tree| child_bit(rev, tree).transpose())
.collect::<Result<Vec<_>, _>>()?;
let root = Task {
roots,
path: ROOT_PATH,
depth: MAX_TREE_DEPTH,
weight: 0,
branching: true,
};
let mut tasks = split(reader, root, bits, workers, SLICE)?;
while tasks.len() < workers * 8 {
let total: usize = tasks.iter().map(|task| task.weight).sum();
let Some((index, largest)) = tasks
.iter()
.enumerate()
.filter(|(_, task)| task.branching)
.max_by_key(|(_, task)| task.weight)
else {
break;
};
if largest.weight <= total / (workers * 2) {
break;
}
let task = tasks.swap_remove(index);
tasks.extend(split(reader, task, bits, workers, SLICE)?);
}
if tasks.is_empty() {
return Ok(());
}
tasks.sort_unstable_by_key(|task| task.weight);
let queue = Mutex::new(tasks);
let packs = reader.packs();
let base = &*bits;
let parts = knot_resource::map_spans(workers, |_, _| {
let mut reader = Reader::new(packs, rev);
// a rename can put one tree in two domains. each worker's set is unioned back.
let mut local = base.clone();
let mut fill = Fill::new(&mut local);
loop {
let task = queue
.lock()
.map_err(|_| GitError::Backend("bitmap work queue poisoned".into()))?
.pop();
let Some(task) = task else {
break;
};
for root in task.roots {
fill_tree(&mut reader, &mut fill, root, task.path, task.depth)?;
}
}
drop(fill);
Ok::<_, GitError>(vec![local])
})?;
for part in parts {
bits.union_with(&part);
}
Ok(())
}
/// a split slice reads at least this many roots. small domains stay on one thread.
const SLICE: usize = 256;
type Children = BTreeMap<Vec<u8>, Vec<BitPosition>>;
fn split<R: Order + Sync>(
reader: &mut Reader<'_, R>,
task: Task,
bits: &mut Bitset,
workers: usize,
slice: usize,
) -> Result<Vec<Task>, GitError> {
if task.depth == 0 {
return Err(GitError::DepthExceeded("tree nesting"));
}
let (rev, packs) = (reader.rev(), reader.packs());
let lanes = workers.min(task.roots.len().div_ceil(slice)).max(1);
let chunk = task.roots.len().div_ceil(lanes);
let base = &*bits;
let roots = &task.roots;
let parts = knot_resource::map_spans(lanes, |start, end| {
let part = &roots[(start * chunk).min(roots.len())..(end * chunk).min(roots.len())];
Ok::<_, GitError>(vec![read_roots(&mut Reader::new(packs, rev), part, base)?])
})?;
let mut children = Children::new();
for (found, set) in parts {
for (name, mut roots) in found {
children.entry(name).or_default().append(&mut roots);
}
set.into_iter().for_each(|bit| bits.set(bit));
}
let mut tree = Vec::new();
children
.into_iter()
.map(|(name, mut roots)| {
roots.sort_unstable_by_key(|bit| bit.get());
roots.dedup();
// a few versions estimate the edge work without reading the whole domain.
let mut entries = 0usize;
let mut samples = 0usize;
let mut branching = false;
for root in roots.iter().step_by((roots.len() / 4).max(1)).take(4) {
reader.tree(*root, &mut tree)?;
for entry in gix::objs::TreeRefIter::from_bytes(&tree, reader.kind()) {
let entry = entry.map_err(|error| GitError::Decode(error.to_string()))?;
entries += 1;
branching |= entry.mode.kind() == gix::objs::tree::EntryKind::Tree;
}
samples += 1;
}
let weight = roots.len().saturating_mul(entries) / samples.max(1);
Ok(Task {
roots,
path: path_of(task.path, &name),
depth: task.depth - 1,
weight,
branching,
})
})
.collect()
}
fn read_roots<R: Order>(
reader: &mut Reader<'_, R>,
roots: &[BitPosition],
base: &Bitset,
) -> Result<(Children, Vec<BitPosition>), GitError> {
let rev = reader.rev();
let kind = reader.kind();
let (mut tree, mut last) = (Vec::new(), Vec::new());
let mut children = Children::new();
let mut set = Vec::new();
for root in roots {
if base.get(*root) {
continue;
}
set.push(*root);
reader.tree(*root, &mut tree)?;
for entry in Changed::new(&tree, &last, kind) {
let entry = entry?;
if entry.mode.kind() == gix::objs::tree::EntryKind::Commit {
continue;
}
let Some(bit) = child_bit(rev, entry.oid)? else {
continue;
};
match entry.mode.kind() {
gix::objs::tree::EntryKind::Tree => match children.get_mut(&entry.filename[..]) {
Some(roots) => roots.push(bit),
None => {
children.insert(entry.filename.to_vec(), vec![bit]);
}
},
_ => set.push(bit),
}
}
std::mem::swap(&mut tree, &mut last);
}
Ok((children, set))
}
#[cfg(test)]
mod tests {
use super::*;
use crate::bitmap::packs::Packs;
use crate::bitmap::revindex::OrderTable;
use crate::midx_rev::tests::git;
use knot_git::Repo;
fn walk_fill(repo: &Repo, rev: &OrderTable, roots: &[gix::ObjectId], bits: &mut Bitset) {
fn tree(repo: &Repo, rev: &OrderTable, oid: gix::ObjectId, bits: &mut Bitset) {
let Some(bit) = child_bit(rev, &oid).unwrap() else {
return;
};
if bits.get(bit) {
return;
}
bits.set(bit);
for entry in repo.git().find_tree(oid).unwrap().iter() {
let entry = entry.unwrap();
match entry.mode().kind() {
gix::objs::tree::EntryKind::Tree => tree(repo, rev, entry.object_id(), bits),
gix::objs::tree::EntryKind::Commit => {}
_ => bits.set(child_bit(rev, entry.oid()).unwrap().unwrap()),
}
}
}
for root in roots {
tree(repo, rev, *root, bits);
}
}
fn assert_fills(
repo: &Repo,
rev: &OrderTable,
packs: &Packs,
roots: &[gix::ObjectId],
seed: &Bitset,
label: &str,
) {
let mut expected = seed.clone();
walk_fill(repo, rev, roots, &mut expected);
let mut reader = Reader::new(packs, rev);
let mut serial = seed.clone();
let mut into = Fill::new(&mut serial);
for root in roots {
if let Some(bit) = child_bit(rev, root).unwrap() {
fill_tree(&mut reader, &mut into, bit, ROOT_PATH, MAX_TREE_DEPTH).unwrap();
}
}
drop(into);
let mut filled = vec![("serially", serial)];
for (workers, how) in [(1, "by one worker"), (4, "by four")] {
let mut actual = seed.clone();
fill(&mut reader, roots.to_vec(), &mut actual, workers).unwrap();
filled.push((how, actual));
}
let root_bits: Vec<_> = roots
.iter()
.filter_map(|root| child_bit(rev, root).unwrap())
.collect();
let mut split_by = |workers, slice| {
let mut bits = seed.clone();
let task = Task {
roots: root_bits.clone(),
path: ROOT_PATH,
depth: MAX_TREE_DEPTH,
weight: 0,
branching: true,
};
let tasks: Vec<_> = split(&mut reader, task, &mut bits, workers, slice)
.unwrap()
.into_iter()
.map(|task| {
let roots: Vec<_> = task.roots.iter().map(|bit| bit.get()).collect();
(task.path, roots, task.depth, task.weight, task.branching)
})
.collect();
let set: Vec<_> = bits.difference_indices(seed).map(|bit| bit.get()).collect();
(tasks, set)
};
assert_eq!(
split_by(4, 1),
split_by(1, usize::MAX),
"{label}: split in slices"
);
for (how, actual) in filled {
let missing: Vec<_> = expected.difference_indices(&actual).collect();
let extra: Vec<_> = actual.difference_indices(&expected).collect();
assert!(
missing.is_empty() && extra.is_empty(),
"{label} {how}: missing {missing:?}, extra {extra:?}"
);
}
}
#[test]
fn private_path_workers_match_the_serial_forest() {
for format in ["sha1", "sha256"] {
let dir = tempfile::tempdir().unwrap();
let path = dir.path();
git(
path,
&[
"init",
"--bare",
"-q",
"-b",
"main",
&format!("--object-format={format}"),
],
"",
);
let shared_blob = git(path, &["hash-object", "-w", "--stdin"], "shared");
let shared = git(
path,
&["mktree"],
&format!("100644 blob {shared_blob}\tfile\n"),
);
let mut parent = String::new();
let mut roots = Vec::new();
for number in 0..16 {
let blob = git(path, &["hash-object", "-w", "--stdin"], &number.to_string());
let leaf = git(path, &["mktree"], &format!("100644 blob {blob}\tfile\n"));
let entries: String = (0..8)
.map(|index| {
format!(
"040000 tree {}\tdir{index}\n",
if index == 0 { &leaf } else { &shared }
)
})
.collect();
let wide = git(path, &["mktree"], &entries);
let root = git(
path,
&["mktree"],
&format!(
"040000 tree {wide}\twide\n040000 tree {wide}\tcopy\n040000 tree {shared}\ttiny\n"
),
);
let mut args = vec!["commit-tree", &root, "-m", "forest"];
if !parent.is_empty() {
args.extend(["-p", &parent]);
}
parent = git(path, &args, "");
roots.push(gix::ObjectId::from_hex(root.as_bytes()).unwrap());
}
git(path, &["update-ref", "refs/heads/main", &parent], "");
git(path, &["repack", "-adq"], "");
git(path, &["multi-pack-index", "write"], "");
let repo = Repo::open(path).unwrap();
let index = gix_pack::multi_index::File::at(
repo.objects_dir().join("pack/multi-pack-index"),
None,
)
.unwrap();
let packs = Packs::of_midx(&index, repo.object_format().kind()).unwrap();
let rev = OrderTable::from_file(index);
let mut seed = Bitset::zeros(rev.len());
walk_fill(&repo, &rev, &roots[..1], &mut seed);
roots.push(gix::ObjectId::empty_tree(repo.object_format().kind()));
assert_fills(&repo, &rev, &packs, &roots, &seed, format);
}
}
/// a version only counts as a skip base if the same fill read it, not if its bit came from the base.
#[test]
fn skips_trust_only_trees_their_fill_read() {
for format in ["sha1", "sha256"] {
let dir = tempfile::tempdir().unwrap();
let path = dir.path();
let object_format = format!("--object-format={format}");
git(
path,
&["init", "--bare", "-q", "-b", "main", &object_format],
"",
);
let blob = |text: &str| git(path, &["hash-object", "-w", "--stdin"], text);
let tree = |entries: &[(&str, &str, &str)]| {
let listed: String = entries
.iter()
.map(|(mode, oid, name)| {
let kind = if *mode == "040000" { "tree" } else { "blob" };
format!("{mode} {kind} {oid}\t{name}\n")
})
.collect();
git(path, &["mktree"], &listed)
};
let blobs: Vec<String> = (0..8).map(|n| blob(&n.to_string())).collect();
let changed = blob("changed");
let sub = tree(&[("100644", &blobs[0], "a"), ("100644", &blobs[1], "b")]);
let names = ["f0", "f1", "f2", "f3", "f4", "f5", "f6", "f7"];
let version = |last: &str| {
let entries: Vec<_> = (0..7)
.map(|n| ("100644", blobs[n].as_str(), names[n]))
.chain([("100644", last, names[7]), ("040000", &sub, "sub")])
.collect();
tree(&entries)
};
let (old, new) = (version(&blobs[7]), version(&changed));
let under = |name: &str, dir: &str, top: &str| {
tree(&[("040000", dir, name), ("100644", top, "top")])
};
let roots = [
under("dir", &old, &blobs[0]),
under("dir", &new, &changed),
under("copy", &old, &blobs[1]),
under("copy", &new, &blobs[2]),
];
let mut parent = String::new();
for root in &roots {
let mut args = vec!["commit-tree", root.as_str(), "-m", "version"];
if !parent.is_empty() {
args.extend(["-p", &parent]);
}
parent = git(path, &args, "");
}
git(path, &["update-ref", "refs/heads/main", &parent], "");
git(path, &["repack", "-adq"], "");
git(path, &["multi-pack-index", "write"], "");
let repo = Repo::open(path).unwrap();
let index = gix_pack::multi_index::File::at(
repo.objects_dir().join("pack/multi-pack-index"),
None,
)
.unwrap();
let packs = Packs::of_midx(&index, repo.object_format().kind()).unwrap();
let rev = OrderTable::from_file(index);
let roots: Vec<_> = roots
.iter()
.map(|root| gix::ObjectId::from_hex(root.as_bytes()).unwrap())
.collect();
let empty = Bitset::zeros(rev.len());
assert_fills(
&repo,
&rev,
&packs,
&roots,
&empty,
&format!("{format} read here"),
);
let mut base = empty.clone();
let old = gix::ObjectId::from_hex(old.as_bytes()).unwrap();
base.set(child_bit(&rev, &old).unwrap().unwrap());
assert_fills(
&repo,
&rev,
&packs,
&roots,
&base,
&format!("{format} from the base"),
);
}
}
}