use std::collections::{BTreeMap, BTreeSet, VecDeque};
use std::io::Write as _;
use std::path::{Path, PathBuf};
use std::process::Stdio;
use std::rc::Rc;
use std::time::{Duration, Instant, SystemTime};
use crate::test_rng::Rng;
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
enum Chain {
Cold,
Git,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
enum Transfer {
Exact,
Thin,
Haveless,
Loose,
}
#[derive(Clone, PartialEq, Eq)]
struct Entry {
mode: &'static str,
data: Data,
}
#[derive(Clone, PartialEq, Eq)]
enum Data {
Inline(String),
Object(String),
}
type Tree = BTreeMap<String, Entry>;
struct Commit {
oid: String,
tree: Option<Rc<Tree>>,
}
const HELD_TREES: usize = 3000;
const PER_TIP: usize = 100;
struct Shape {
nights: usize,
grown: (usize, usize),
files: usize,
pushes: (usize, usize),
commits: (usize, usize),
garbage: usize,
merges: usize,
tags: usize,
cobs: usize,
}
struct Fuzz {
rng: Rng,
shape: Shape,
client: PathBuf,
hosted: PathBuf,
marks: PathBuf,
clock: i64,
next_mark: usize,
next_name: usize,
commits: BTreeMap<usize, Commit>,
held: VecDeque<usize>,
format: knot_types::ObjectFormat,
by_oid: BTreeMap<String, usize>,
refs: BTreeMap<String, String>,
stats: Stats,
}
#[derive(Default)]
struct Stats {
pushes: usize,
commits: usize,
deleted: usize,
forced: usize,
transfers: BTreeMap<Transfer, usize>,
}
const EPOCH: i64 = 1_700_000_000;
/// one pack thread and no auto gc keeps a seed's packs the same on each run.
fn git_at(dir: &Path, clock: i64) -> std::process::Command {
let mut command = crate::test_git();
command.current_dir(dir);
let date = format!("{clock} +0000");
command
.env("GIT_AUTHOR_DATE", &date)
.env("GIT_COMMITTER_DATE", &date)
.env("GIT_CONFIG_COUNT", "3")
.env("GIT_CONFIG_KEY_1", "pack.threads")
.env("GIT_CONFIG_VALUE_1", "1")
.env("GIT_CONFIG_KEY_2", "gc.auto")
.env("GIT_CONFIG_VALUE_2", "0");
command
}
struct Ran {
ok: bool,
stdout: Vec<u8>,
stderr: String,
}
fn run(mut command: std::process::Command, stdin: &[u8]) -> Ran {
let mut child = command
.stdin(Stdio::piped())
.stdout(Stdio::piped())
.stderr(Stdio::piped())
.spawn()
.expect("spawn git");
let mut input = child.stdin.take().unwrap();
let stdin = stdin.to_vec();
let writer = std::thread::spawn(move || {
let _ = input.write_all(&stdin);
});
let output = child.wait_with_output().expect("wait for git");
writer.join().unwrap();
Ran {
ok: output.status.success(),
stdout: output.stdout,
stderr: String::from_utf8_lossy(&output.stderr).into_owned(),
}
}
impl Fuzz {
fn new(seed: u64, dir: &Path, nights: Option<usize>) -> Self {
let mut rng = Rng(seed);
let large = std::env::var("FUZZ_SIZE").as_deref() == Ok("large");
let shape = Shape {
nights: nights.unwrap_or_else(|| match large {
true => rng.range(3, 5),
false => rng.range(5, 20),
}),
grown: match large {
true => (rng.range(25_000, 80_000), rng.range(10, 60)),
false => (0, 0),
},
files: if large { 400 } else { usize::MAX },
pushes: (1, rng.range(1, 6)),
commits: (1, *rng.pick(&[3, 8, 20, 60])),
garbage: *rng.pick(&[0, 10, 30, 60, 90]),
merges: *rng.pick(&[0, 10, 25, 50]),
tags: *rng.pick(&[0, 10, 30]),
cobs: *rng.pick(&[0, 15, 40]),
};
let format = std::env::var("FUZZ_FORMAT")
.ok()
.and_then(|name| knot_types::ObjectFormat::from_capability(&name))
.unwrap_or_default();
let object_format = format!("--object-format={}", format.capability());
let (client, hosted) = (dir.join("client.git"), dir.join("hosted.git"));
for repo in [&client, &hosted] {
std::fs::create_dir_all(repo).unwrap();
let mut command = git_at(repo, EPOCH);
command.args(["init", "-q", "--bare", "-b", "main", &object_format]);
assert!(run(command, b"").ok);
}
Self {
rng,
shape,
marks: dir.join("marks"),
client,
hosted,
clock: EPOCH,
next_mark: 1,
next_name: 0,
commits: BTreeMap::new(),
held: VecDeque::new(),
format,
by_oid: BTreeMap::new(),
refs: BTreeMap::new(),
stats: Stats::default(),
}
}
fn git(&self, repo: &Path, args: &[&str], stdin: &[u8]) -> Result<Vec<u8>, String> {
let mut command = git_at(repo, self.clock);
command.args(args);
let ran = run(command, stdin);
if ran.ok {
Ok(ran.stdout)
} else {
Err(format!(
"git {args:?} in {}: {}",
repo.display(),
ran.stderr.trim()
))
}
}
fn text(&self, repo: &Path, args: &[&str], stdin: &[u8]) -> Result<String, String> {
Ok(String::from_utf8(self.git(repo, args, stdin)?)
.unwrap()
.trim()
.to_string())
}
fn tick(&mut self) -> i64 {
self.clock += self.rng.range(1, 600) as i64;
if self.rng.odds(3) {
return self.clock - self.rng.range(1, 100_000) as i64;
}
self.clock
}
fn name(&mut self) -> usize {
self.next_name += 1;
self.next_name
}
fn path(&mut self) -> String {
let depth = *self.rng.pick(&[0, 0, 1, 1, 2, 3, 6]);
let mut path = String::new();
for _ in 0..depth {
path.push_str(&format!("d{}/", self.rng.below(4)));
}
path.push_str(&format!("f{}", self.rng.below(12)));
path
}
fn entry(&mut self, tree: &Tree) -> Entry {
let inline = |mode, data| Entry {
mode,
data: Data::Inline(data),
};
match self.rng.below(20) {
0 => inline("120000", format!("../f{}", self.rng.below(12))),
1 => {
let hex: String = (0..self.format.kind().len_in_bytes())
.map(|_| format!("{:02x}", self.rng.below(256)))
.collect();
Entry {
mode: "160000",
data: Data::Object(hex),
}
}
2 | 3 if !tree.is_empty() => {
let (_, entry) = tree.iter().nth(self.rng.below(tree.len())).unwrap();
entry.clone()
}
n => inline(
if n == 4 { "100755" } else { "100644" },
format!("blob {} {}\n", self.name(), self.rng.next()),
),
}
}
fn edit(&mut self, mut tree: Tree) -> Tree {
for _ in 0..self.rng.range(1, 4) {
let existing = (!tree.is_empty())
.then(|| tree.keys().nth(self.rng.below(tree.len())).unwrap().clone());
let roll = match tree.len() >= self.shape.files {
true => self.rng.below(4),
false => self.rng.below(10),
};
match (roll, existing) {
(0, Some(path)) => {
tree.remove(&path);
}
(1, Some(path)) => {
let entry = tree.remove(&path).unwrap();
let to = self.path();
tree.insert(to, entry);
}
(2, Some(path)) => {
let entry = tree.get_mut(&path).unwrap();
entry.mode = match entry.mode {
"100644" => "100755",
"100755" => "100644",
other => other,
};
}
(3, Some(path)) => {
let entry = self.entry(&tree);
tree.insert(path, entry);
}
_ => {
let (path, entry) = (self.path(), self.entry(&tree));
tree.insert(path, entry);
}
}
}
if self.rng.odds(2) {
tree.clear();
}
tree
}
fn tree(&self, mark: usize) -> Result<Rc<Tree>, String> {
let commit = &self.commits[&mark];
if let Some(tree) = &commit.tree {
return Ok(tree.clone());
}
let listed = self.git(&self.client, &["ls-tree", "-r", "-z", &commit.oid], b"")?;
let mut tree = Tree::new();
for line in listed
.split(|byte| *byte == 0)
.filter(|line| !line.is_empty())
{
let line = std::str::from_utf8(line).unwrap();
let (meta, path) = line.split_once('\t').unwrap();
let mut fields = meta.split(' ');
let mode = match fields.next().unwrap() {
"100755" => "100755",
"120000" => "120000",
"160000" => "160000",
_ => "100644",
};
let oid = fields.nth(1).unwrap().to_string();
tree.insert(
path.to_string(),
Entry {
mode,
data: Data::Object(oid),
},
);
}
Ok(Rc::new(tree))
}
fn held_tree(&mut self) -> Option<Rc<Tree>> {
let mark = *self.held.get(self.rng.below(self.held.len().max(1)))?;
self.commits[&mark].tree.clone()
}
fn import(&mut self, planned: Vec<(Vec<usize>, Tree)>) -> Result<Vec<usize>, String> {
let mut stream = Vec::new();
let mut marks = Vec::new();
let mut batch: BTreeMap<usize, &Tree> = BTreeMap::new();
for (parents, tree) in &planned {
let mark = self.next_mark;
self.next_mark += 1;
let when = self.tick();
let message = format!("c{mark}\n");
write!(
stream,
"reset refs/fuzz/scratch\ncommit refs/fuzz/scratch\nmark :{mark}\n\
author A <a@a> {when} +0000\ncommitter C <c@c> {when} +0000\n\
data {}\n{message}",
message.len()
)
.unwrap();
for (n, parent) in parents.iter().enumerate() {
let verb = if n == 0 { "from" } else { "merge" };
writeln!(stream, "{verb} :{parent}").unwrap();
}
let held;
let base: &Tree = match parents.first() {
Some(parent) => match batch.get(parent) {
Some(tree) => tree,
None => {
held = self.tree(*parent)?;
&held
}
},
None => &Tree::new(),
};
for path in base.keys().filter(|path| !tree.contains_key(*path)) {
writeln!(stream, "D {path}").unwrap();
}
for (path, entry) in tree {
if base.get(path) == Some(entry) {
continue;
}
match &entry.data {
Data::Object(oid) => writeln!(stream, "M {} {oid} {path}", entry.mode),
Data::Inline(data) => write!(
stream,
"M {} inline {path}\ndata {}\n{data}\n",
entry.mode,
data.len()
),
}
.unwrap();
}
stream.push(b'\n');
batch.insert(mark, tree);
marks.push(mark);
}
drop(batch);
let marks_file = self.marks.to_str().unwrap().to_string();
self.git(
&self.client.clone(),
&[
"fast-import",
"--quiet",
"--force",
"--done",
&format!("--import-marks-if-exists={marks_file}"),
&format!("--export-marks={marks_file}"),
],
&[stream, b"done\n".to_vec()].concat(),
)?;
let exported = std::fs::read_to_string(&self.marks).unwrap();
let first = marks[0];
let oids: BTreeMap<usize, String> = exported
.lines()
.filter_map(|line| {
let (mark, oid) = line.split_once(' ')?;
let mark: usize = mark.trim_start_matches(':').parse().ok()?;
(mark >= first).then(|| (mark, oid.to_string()))
})
.collect();
for ((_, tree), mark) in planned.into_iter().zip(&marks) {
let oid = oids[mark].clone();
self.by_oid.insert(oid.clone(), *mark);
self.commits.insert(
*mark,
Commit {
oid,
tree: Some(Rc::new(tree)),
},
);
self.held.push_back(*mark);
if self.held.len() > HELD_TREES {
let dropped = self.held.pop_front().unwrap();
self.commits.get_mut(&dropped).unwrap().tree = None;
}
self.stats.commits += 1;
}
Ok(marks)
}
fn some_commit(&mut self) -> Option<usize> {
let tips: Vec<usize> = self
.refs
.values()
.filter_map(|oid| self.by_oid.get(oid).copied())
.collect();
if !tips.is_empty() && self.rng.odds(70) {
return Some(*self.rng.pick(&tips));
}
let all: Vec<usize> = self.commits.keys().copied().collect();
(!all.is_empty()).then(|| *self.rng.pick(&all))
}
fn next_tree(&mut self, tree: Tree) -> Tree {
if self.rng.odds(5) {
if let Some(old) = self.held_tree() {
return (*old).clone();
}
}
self.edit(tree)
}
fn line(&mut self, base: Option<usize>, count: usize) -> Result<usize, String> {
let mut planned = Vec::new();
let mut tree = match base {
Some(mark) => (*self.tree(mark)?).clone(),
None => Tree::new(),
};
for n in 0..count {
tree = self.next_tree(tree);
let parents = match (n, base) {
(0, None) => vec![],
(0, Some(base)) => vec![base],
_ => vec![self.next_mark + planned.len() - 1],
};
planned.push((parents, tree.clone()));
}
Ok(*self.import(planned)?.last().unwrap())
}
fn merged(&mut self, trees: &[&Tree]) -> Tree {
let mut tree = trees[0].clone();
for other in &trees[1..] {
for (path, entry) in other.iter() {
if self.rng.odds(50) {
tree.insert(path.clone(), entry.clone());
}
}
}
if self.rng.odds(50) {
tree = self.edit(tree);
}
tree
}
fn merge(&mut self, parents: Vec<usize>) -> Result<usize, String> {
let trees = (parents.iter())
.map(|parent| self.tree(*parent))
.collect::<Result<Vec<_>, _>>()?;
let tree = self.merged(&trees.iter().map(|tree| &**tree).collect::<Vec<_>>());
Ok(self.import(vec![(parents, tree)])?[0])
}
fn grow(&mut self) -> Result<(), String> {
let (total, branches) = self.shape.grown;
if total == 0 {
return Ok(());
}
let root = self.line(None, 1)?;
let mut tips: Vec<(String, usize, Tree)> = vec![(
"refs/heads/main".to_string(),
root,
(*self.tree(root)?).clone(),
)];
let mut grown = 1;
let mut updates: BTreeMap<String, Option<String>> = BTreeMap::new();
while grown < total {
let mut planned: Vec<(Vec<usize>, Tree)> = Vec::new();
for _ in 0..1000.min(total - grown) {
let next = self.next_mark + planned.len();
if tips.len() < branches && self.rng.odds(2) {
let (_, base, tree) = tips[0].clone();
tips.push((format!("refs/heads/b{}", self.name()), base, tree));
}
let at = match self.rng.odds(40) {
true => 0,
false => self.rng.below(tips.len()),
};
let (tree, parents) = if self.rng.odds(5) && tips.len() > 1 {
let other = self.rng.below(tips.len());
if other == at {
continue;
}
let tree = self.merged(&[&tips[at].2, &tips[other].2]);
(tree, vec![tips[at].1, tips[other].1])
} else {
let tree = self.next_tree(tips[at].2.clone());
(tree, vec![tips[at].1])
};
planned.push((parents, tree.clone()));
tips[at].1 = next;
tips[at].2 = tree;
}
grown += planned.len();
let marks = self.import(planned)?;
for mark in marks {
if self.rng.below(1000) != 0 {
continue;
}
let oid = self.oid(mark);
let target = match self.rng.odds(50) {
true => self.mktag(&oid, "commit")?,
false => oid,
};
updates.insert(format!("refs/tags/v{}", self.name()), Some(target));
}
for (name, mark, _) in &tips {
updates.insert(name.clone(), Some(self.oid(*mark)));
}
if self.rng.odds(30) || grown >= total {
self.send(std::mem::take(&mut updates), true)?;
}
}
Ok(())
}
fn oid(&self, mark: usize) -> String {
self.commits[&mark].oid.clone()
}
fn mktag(&mut self, object: &str, kind: &str) -> Result<String, String> {
let name = format!("t{}", self.name());
let when = self.tick();
let tag = format!(
"object {object}\ntype {kind}\ntag {name}\ntagger T <t@t> {when} +0000\n\n{name}\n"
);
self.text(&self.client.clone(), &["mktag"], tag.as_bytes())
}
fn kind(&self, oid: &str) -> Result<String, String> {
self.text(&self.client.clone(), &["cat-file", "-t", oid], b"")
}
fn refs_under(&self, prefix: &str) -> Vec<String> {
self.refs
.keys()
.filter(|name| name.starts_with(prefix))
.cloned()
.collect()
}
fn plan_push(&mut self) -> Result<BTreeMap<String, Option<String>>, String> {
let mut updates: BTreeMap<String, Option<String>> = BTreeMap::new();
let ops = self.rng.range(1, 4);
for _ in 0..ops {
let roll = self.rng.below(100);
let branches = self.refs_under("refs/heads/");
let garbage = self.shape.garbage;
let (merges, tags, cobs) = (self.shape.merges, self.shape.tags, self.shape.cobs);
let commits = self.rng.range(self.shape.commits.0, self.shape.commits.1);
if branches.is_empty() || roll < 8 {
let name = if branches.is_empty() {
"refs/heads/main".to_string()
} else {
format!("refs/heads/b{}", self.name())
};
let base = if self.rng.odds(30) {
None
} else {
self.some_commit()
};
let tip = self.line(base, commits)?;
updates.insert(name, Some(self.oid(tip)));
} else if roll < 8 + garbage / 3 {
let name = self.rng.pick(&branches).clone();
let base = if self.rng.odds(20) {
None
} else {
self.some_commit()
};
let tip = self.line(base, commits)?;
updates.insert(name, Some(self.oid(tip)));
self.stats.forced += 1;
} else if roll < 8 + garbage / 2 {
let all: Vec<String> = self
.refs
.keys()
.filter(|name| *name != "refs/heads/main")
.cloned()
.collect();
if !all.is_empty() {
updates.insert(self.rng.pick(&all).clone(), None);
self.stats.deleted += 1;
}
} else if roll < 30 + merges / 2 {
let name = self.rng.pick(&branches).clone();
let Some(&head) = self.refs.get(&name).and_then(|oid| self.by_oid.get(oid)) else {
continue;
};
let mut parents = vec![head];
for _ in 0..*self.rng.pick(&[1, 1, 1, 2, 3, 4]) {
if let Some(other) = self.some_commit() {
if !parents.contains(&other) {
parents.push(other);
}
}
}
if parents.len() == 2 && self.rng.odds(40) && branches.len() > 1 {
let other_name = self.rng.pick(&branches).clone();
if let Some(&other) = self
.refs
.get(&other_name)
.and_then(|oid| self.by_oid.get(oid))
{
if other != head && other_name != name {
let one = self.merge(vec![head, other])?;
let two = self.merge(vec![other, head])?;
updates.insert(name, Some(self.oid(one)));
updates.insert(other_name, Some(self.oid(two)));
continue;
}
}
}
if parents.len() < 2 {
continue;
}
let merge = self.merge(parents)?;
let tip = if self.rng.odds(50) {
self.line(Some(merge), commits)?
} else {
merge
};
updates.insert(name, Some(self.oid(tip)));
} else if roll < 55 + tags / 2 && tags > 0 {
let name = if self.rng.odds(20) && !self.refs_under("refs/tags/").is_empty() {
self.rng.pick(&self.refs_under("refs/tags/")).clone()
} else {
format!("refs/tags/v{}", self.name())
};
let Some(commit) = self.some_commit() else {
continue;
};
let commit = self.oid(commit);
let target = match self.rng.below(7) {
0 => commit,
1 | 2 => self.mktag(&commit, "commit")?,
3 => {
let tree = self.text(
&self.client.clone(),
&["rev-parse", &format!("{commit}^{{tree}}")],
b"",
)?;
if self.rng.odds(50) {
tree
} else {
self.mktag(&tree, "tree")?
}
}
4 => {
let data = format!("tagged blob {}\n", self.name());
let blob = self.text(
&self.client.clone(),
&["hash-object", "-w", "--stdin"],
data.as_bytes(),
)?;
self.mktag(&blob, "blob")?
}
_ => {
let tags = self.refs_under("refs/tags/");
let mut inner = match tags.is_empty() {
true => self.mktag(&commit, "commit")?,
false => self.refs[self.rng.pick(&tags)].clone(),
};
for _ in 0..self.rng.range(1, 2) {
let kind = self.kind(&inner)?;
inner = self.mktag(&inner, &kind)?;
}
inner
}
};
updates.insert(name, Some(target));
} else if roll < 70 + cobs / 2 && cobs > 0 {
let n = self.rng.below(6);
let length = self.rng.range(1, 3);
let (name, tip) = match self.rng.below(3) {
0 => {
let name = format!("refs/cobs/org.tangled.track.ticket/{n}");
let base = self
.refs
.get(&name)
.and_then(|oid| self.by_oid.get(oid))
.copied();
(name, self.line(base, length)?)
}
1 => {
let Some(commit) = self.some_commit() else {
continue;
};
let tip = if self.rng.odds(50) {
self.line(Some(commit), 1)?
} else {
commit
};
(format!("refs/tngl/keep/did/patch/{n}"), tip)
}
_ => {
let Some(commit) = self.some_commit() else {
continue;
};
(format!("refs/hidden/{n}"), self.line(Some(commit), length)?)
}
};
updates.insert(name, Some(self.oid(tip)));
} else {
let name = self.rng.pick(&branches).clone();
let head = self
.refs
.get(&name)
.and_then(|oid| self.by_oid.get(oid))
.copied();
let tip = self.line(head, commits)?;
updates.insert(name, Some(self.oid(tip)));
}
}
Ok(updates)
}
fn push(&mut self) -> Result<(), String> {
let updates = self.plan_push()?;
self.send(updates, false)
}
fn send(
&mut self,
updates: BTreeMap<String, Option<String>>,
bulk: bool,
) -> Result<(), String> {
let wants: BTreeSet<String> = updates.values().flatten().cloned().collect();
let transfer = *self.rng.pick(&[
Transfer::Exact,
Transfer::Exact,
Transfer::Thin,
Transfer::Thin,
Transfer::Loose,
if self.shape.garbage >= 30 {
Transfer::Haveless
} else {
Transfer::Thin
},
]);
let transfer = match (bulk, transfer) {
(true, Transfer::Loose | Transfer::Haveless) => Transfer::Exact,
(_, transfer) => transfer,
};
if !wants.is_empty() {
let mut revs = String::new();
for want in &wants {
revs.push_str(&format!("{want}\n"));
}
if !matches!(transfer, Transfer::Haveless) {
for have in self.refs.values() {
revs.push_str(&format!("^{have}\n"));
}
}
let mut args = vec!["pack-objects", "--revs", "--stdout", "-q"];
if matches!(transfer, Transfer::Thin) {
args.push("--thin");
}
let pack = self.git(&self.client.clone(), &args, revs.as_bytes())?;
let objects = u32::from_be_bytes(pack[8..12].try_into().unwrap());
if objects > 0 {
let hosted = self.hosted.clone();
match transfer {
Transfer::Loose => {
self.git(&hosted, &["unpack-objects", "-q"], &pack)?;
}
_ => {
let mut args = vec!["index-pack", "--stdin"];
if matches!(transfer, Transfer::Thin) {
args.push("--fix-thin");
}
let out = self.text(&hosted, &args, &pack)?;
let hash = out
.split_whitespace()
.last()
.unwrap_or_default()
.to_string();
// a multi-pack index picks duplicates by pack mtime,
// which are set from the fuzzer's clock here.
let when = SystemTime::UNIX_EPOCH + Duration::from_secs(self.clock as u64);
for ext in ["pack", "idx"] {
let path = hosted.join(format!("objects/pack/pack-{hash}.{ext}"));
std::fs::File::open(&path)
.and_then(|file| file.set_modified(when))
.map_err(|error| format!("age {}: {error}", path.display()))?;
}
}
}
*self.stats.transfers.entry(transfer).or_default() += 1;
}
}
let mut stdin = String::new();
for (name, target) in &updates {
match target {
Some(oid) => stdin.push_str(&format!("update {name} {oid}\n")),
None => stdin.push_str(&format!("delete {name}\n")),
}
}
self.git(
&self.hosted.clone(),
&["update-ref", "--stdin"],
stdin.as_bytes(),
)?;
for (name, target) in updates {
match target {
Some(oid) => self.refs.insert(name, oid),
None => self.refs.remove(&name),
};
}
self.stats.pushes += 1;
Ok(())
}
}
#[derive(Default, Debug)]
struct Night {
midx: String,
packs: (usize, usize),
objects: u32,
unreachable: usize,
refs: usize,
selected: usize,
previous: bool,
tested: usize,
sets: usize,
}
impl Fuzz {
fn pack_dir(&self) -> PathBuf {
self.hosted.join("objects/pack")
}
fn pack_files(&self, ext: &str) -> Vec<PathBuf> {
let mut found: Vec<PathBuf> = std::fs::read_dir(self.pack_dir())
.map(|entries| entries.map(|entry| entry.unwrap().path()).collect())
.unwrap_or_default();
found.retain(|path| {
let name = path.file_name().unwrap().to_string_lossy();
name.starts_with("pack-") && name.ends_with(ext)
});
found.sort();
found
}
fn open_repo(&self) -> knot_git::Repo {
knot_git::Repo::open(&self.hosted).expect("open the hosted repo")
}
fn night(&mut self, number: usize, chain: Chain) -> Result<Night, String> {
let mut night = Night::default();
let previous = match number {
1 => None,
_ => crate::bitmap::open_bitmap_index(&self.open_repo())
.map_err(|error| format!("open the last bitmap: {error}"))?,
};
night.previous = previous.is_some();
if number > 1 && previous.is_none() {
return Err("the last night's bitmap doesn't open as a previous".into());
}
night.packs.0 = self.pack_files(".pack").len();
self.git(
&self.hosted.clone(),
&["repack", "-d", "-q", "--geometric=2"],
b"",
)?;
night.packs.1 = self.pack_files(".pack").len();
if !self.pack_files(".bitmap").is_empty() {
return Err("the roll-up wrote a pack bitmap".into());
}
for entry in std::fs::read_dir(self.pack_dir()).unwrap() {
let path = entry.unwrap().path();
if path
.file_name()
.unwrap()
.to_string_lossy()
.starts_with("multi-pack-index")
{
std::fs::remove_file(path).unwrap();
}
}
if number == 1 && chain == Chain::Git {
self.git(
&self.hosted.clone(),
&["multi-pack-index", "write", "--bitmap"],
b"",
)?;
crate::midx_rev::complete(&self.pack_dir(), self.format)
.map_err(|error| format!("write the .rev of git's RIDX chunk: {error:#}"))?;
} else {
self.git(&self.hosted.clone(), &["multi-pack-index", "write"], b"")?;
let wrote = crate::bitmap::write_midx_bitmap(&self.open_repo(), previous.as_ref())
.map_err(|error| format!("knot_git's write failed: {error}"))?;
if !wrote && !self.commits.is_empty() {
return Err("knot_git wrote no bitmap".into());
}
if previous.is_some() {
self.same_as_cold()?;
}
}
drop(previous);
self.check(&mut night)?;
Ok(night)
}
fn same_as_cold(&self) -> Result<(), String> {
let midx =
gix::odb::pack::multi_index::File::at(self.pack_dir().join("multi-pack-index"), None)
.map_err(|error| format!("open the multi-pack index: {error}"))?;
let path = self
.pack_dir()
.join(format!("multi-pack-index-{}.bitmap", midx.checksum()));
let built_on = std::fs::read(&path).unwrap();
crate::bitmap::write_midx_bitmap(&self.open_repo(), None)
.map_err(|error| format!("knot_git's cold write failed: {error}"))?;
let cold = std::fs::read(&path).unwrap();
if cold != built_on {
let at = cold.iter().zip(&built_on).position(|(a, b)| a != b);
return Err(format!(
"the bitmap built on the last night's ({} bytes) isn't the one built afresh ({} bytes); first difference at byte {at:?}",
built_on.len(),
cold.len()
));
}
Ok(())
}
fn check(&mut self, night: &mut Night) -> Result<(), String> {
let dir = self.pack_dir();
let midx = gix::odb::pack::multi_index::File::at(dir.join("multi-pack-index"), None)
.map_err(|error| format!("open the multi-pack index: {error}"))?;
night.objects = midx.num_objects();
night.midx = midx.checksum().to_string()[..8].to_string();
let bitmap = dir.join(format!("multi-pack-index-{}.bitmap", midx.checksum()));
let bytes = std::fs::read(&bitmap)
.map_err(|error| format!("read {}: {error}", bitmap.display()))?;
let positions = bitmap_commits(&bytes, self.format.kind().len_in_bytes())?;
night.selected = positions.len();
let hosted = self.hosted.clone();
for position in positions {
let commit = midx.oid_at_index(position).to_string();
let mut command = git_at(&hosted, self.clock);
command.args(["rev-list", "--test-bitmap", &commit]);
let ran = run(command, b"");
let noisy = ran.stderr.lines().any(|line| {
line.starts_with("warning")
|| line.starts_with("error")
|| line.starts_with("fatal")
});
if !ran.ok
|| noisy
|| !ran.stderr.contains("OK!")
|| !ran.stderr.contains("Found bitmap for")
{
return Err(format!(
"git rev-list --test-bitmap {commit} (bitmapped at midx position {position}):\n{}",
ran.stderr.trim()
));
}
night.tested += 1;
}
let is =
|name: &str, prefixes: &[&str]| prefixes.iter().any(|prefix| name.starts_with(prefix));
let public: Vec<String> = self
.refs
.iter()
.filter(|(name, _)| is(name, &["refs/heads/", "refs/tags/"]))
.map(|(_, oid)| oid.clone())
.collect();
let exported: Vec<String> = self
.refs
.iter()
.filter(|(name, _)| {
is(
name,
&["refs/heads/", "refs/tags/", "refs/cobs/", "refs/tngl/keep/"],
)
})
.map(|(_, oid)| oid.clone())
.collect();
let all: Vec<String> = self.refs.values().cloned().collect();
let mut sets: Vec<(String, String)> = vec![
("public".into(), lines(&public)),
("exported".into(), lines(&exported)),
("all".into(), lines(&all)),
];
let (tags, others): (Vec<_>, Vec<_>) =
(self.refs.iter()).partition(|(name, _)| name.starts_with("refs/tags/"));
let mut tips = others;
let room = PER_TIP.saturating_sub(tips.len());
match tags.len() <= room {
true => tips.extend(tags),
false => tips.extend((0..room).map(|_| *self.rng.pick(&tags))),
}
for (name, oid) in tips {
sets.push((name.clone(), format!("{oid}\n")));
}
let mut reached = BTreeSet::new();
for (name, revs) in &sets {
if revs.is_empty() {
continue;
}
let walk = self.walk(revs, false)?;
let through = self.walk(revs, true)?;
if walk != through {
let extra: Vec<&String> = through.difference(&walk).take(10).collect();
let missing: Vec<&String> = walk.difference(&through).take(10).collect();
return Err(format!(
"{name}: through the bitmap {} objects, walking {}; extra {extra:?}, missing {missing:?}\nrevs:\n{revs}",
through.len(),
walk.len()
));
}
if name == "all" {
reached = walk;
}
night.sets += 1;
}
// `a ^b` isn't exact for trees and blobs. the check compares against walk(a) minus walk(b).
for _ in 0..3.min(all.len() / 2) {
let (a, b) = (self.rng.pick(&all).clone(), self.rng.pick(&all).clone());
let revs = format!("{a}\n^{b}\n");
let through = self.walk(&revs, true)?;
let minus: BTreeSet<String> = (self.walk(&format!("{a}\n"), false)?)
.difference(&self.walk(&format!("{b}\n"), false)?)
.cloned()
.collect();
if through != minus {
return Err(format!(
"{a} ^{b}: through the bitmap {} objects, {} by two walks\nrevs:\n{revs}",
through.len(),
minus.len()
));
}
night.sets += 1;
}
night.unreachable = night.objects as usize - reached.len().min(night.objects as usize);
night.refs = self.refs.len();
Ok(())
}
fn walk(&self, revs: &str, bitmap: bool) -> Result<BTreeSet<String>, String> {
let mut command = git_at(&self.hosted, self.clock);
command.args(["rev-list", "--objects", "--no-object-names", "--stdin"]);
if bitmap {
command.arg("--use-bitmap-index");
}
let ran = run(command, revs.as_bytes());
if !ran.ok || (bitmap && !ran.stderr.is_empty()) {
return Err(format!(
"git rev-list --objects (bitmap {bitmap}) of\n{revs}: {}",
ran.stderr.trim()
));
}
let listed: Vec<String> = String::from_utf8(ran.stdout)
.unwrap()
.lines()
.map(str::to_string)
.collect();
let set: BTreeSet<String> = listed.iter().cloned().collect();
if set.len() != listed.len() {
return Err(format!(
"git rev-list --objects (bitmap {bitmap}) listed an object twice:\n{revs}"
));
}
Ok(set)
}
}
fn lines(oids: &[String]) -> String {
oids.iter().map(|oid| format!("{oid}\n")).collect()
}
fn bitmap_commits(bytes: &[u8], hash: usize) -> Result<Vec<u32>, String> {
let u32_at = |at: usize| -> Result<u32, String> {
bytes
.get(at..at + 4)
.map(|word| u32::from_be_bytes(word.try_into().unwrap()))
.ok_or_else(|| format!("a bitmap cut short at {at}"))
};
if bytes.get(..4) != Some(b"BITM") {
return Err("not a bitmap".into());
}
let count = u32_at(8)? as usize;
let mut at = 12 + hash;
let skip_ewah =
|at: usize| -> Result<usize, String> { Ok(at + 8 + 8 * u32_at(at + 4)? as usize + 4) };
for _ in 0..4 {
at = skip_ewah(at)?;
}
let mut positions = Vec::with_capacity(count);
for _ in 0..count {
positions.push(u32_at(at)?);
at = skip_ewah(at + 6)?;
}
Ok(positions)
}
fn env<T: std::str::FromStr>(name: &str) -> Option<T> {
std::env::var(name)
.ok()
.and_then(|value| value.parse().ok())
}
fn fuzz_seed(seed: u64, dir: &Path, chain: Chain, nights: Option<usize>) -> Result<String, String> {
let started = Instant::now();
let mut fuzz = Fuzz::new(seed, dir, nights);
fuzz.grow()
.map_err(|error| format!("growing the history: {error}"))?;
let mut report = vec![format!("grown {} ms", started.elapsed().as_millis())];
for number in 1..=fuzz.shape.nights {
let night_started = Instant::now();
let pushes = fuzz.rng.range(fuzz.shape.pushes.0, fuzz.shape.pushes.1);
for _ in 0..pushes {
fuzz.push()
.map_err(|error| format!("night {number}, push: {error}"))?;
}
let night = fuzz
.night(number, chain)
.map_err(|error| format!("night {number}: {error}"))?;
report.push(format!(
"n{number}: midx {} packs {}->{} objects {} unreachable {} refs {} selected {} tested {} sets {} ms {}",
night.midx, night.packs.0, night.packs.1, night.objects, night.unreachable, night.refs, night.selected, night.tested, night.sets,
night_started.elapsed().as_millis()
));
}
let stats = &fuzz.stats;
Ok(format!(
"seed={seed} chain={chain:?} format={} nights={} pushes={} commits={} forced={} deleted={} transfers={:?} ms={}\n {}",
fuzz.format.capability(),
fuzz.shape.nights,
stats.pushes,
stats.commits,
stats.forced,
stats.deleted,
stats.transfers,
started.elapsed().as_millis(),
report.join("\n ")
))
}
#[test]
#[ignore = "a fuzzer: FUZZ_SEED, FUZZ_SEEDS, FUZZ_NIGHTS, FUZZ_CHAIN, FUZZ_SIZE, FUZZ_FORMAT, FUZZ_KEEP"]
fn fuzz_bitmap() {
let first: Option<u64> = env("FUZZ_SEED");
let count: u64 = env("FUZZ_SEEDS").unwrap_or(1);
let nights: Option<usize> = env("FUZZ_NIGHTS").or(first.is_none().then_some(5));
let first = first.unwrap_or(0);
let chain_for = |seed: u64| match std::env::var("FUZZ_CHAIN").as_deref() {
Ok("git") => Chain::Git,
Ok("cold") => Chain::Cold,
_ if seed % 4 == 3 => Chain::Git,
_ => Chain::Cold,
};
let mut failed = Vec::new();
for seed in first..first + count {
let dir = tempfile::tempdir().unwrap();
match fuzz_seed(seed, dir.path(), chain_for(seed), nights) {
Ok(report) => println!("FUZZ ok {report}"),
Err(error) => {
let kept = std::env::var_os("FUZZ_KEEP").map(|_| dir.keep());
println!(
"FUZZ FAIL seed={seed} chain={:?} kept={kept:?}: {error}",
chain_for(seed)
);
failed.push(seed);
}
}
}
assert!(failed.is_empty(), "failing seeds: {failed:?}");
}
fn claim_one_more(path: &Path, hash: usize) -> u32 {
let mut bytes = std::fs::read(path).unwrap();
let be32 = |bytes: &[u8], at: usize| u32::from_be_bytes(bytes[at..at + 4].try_into().unwrap());
let count = be32(&bytes, 8);
let mut at = 12 + hash;
for _ in 0..4 {
at += 8 + 8 * be32(&bytes, at + 4) as usize + 4;
}
for _ in 0..count {
let (commit, ewah) = (be32(&bytes, at), at + 6);
let (size, words) = (be32(&bytes, ewah) as u64, be32(&bytes, ewah + 4) as usize);
{
let word = |n: usize| ewah + 8 + 8 * n;
let (mut n, mut bit) = (0, 0u64);
while n < words {
let marker = u64::from_be_bytes(bytes[word(n)..word(n) + 8].try_into().unwrap());
bit += 64 * ((marker >> 1) & 0xffff_ffff);
for literal in 1..=(marker >> 33) as usize {
let at = word(n + literal);
let value = u64::from_be_bytes(bytes[at..at + 8].try_into().unwrap());
let clear = (!value).trailing_zeros() as u64;
if clear < 64 && bit + clear < size {
bytes[at..at + 8].copy_from_slice(&(value | 1 << clear).to_be_bytes());
crate::cas::atomic_write(path, &bytes).unwrap();
return commit;
}
bit += 64;
}
n += 1 + (marker >> 33) as usize;
}
}
at = ewah + 8 + 8 * words + 4;
}
panic!("no entry with a clear literal bit");
}
#[test]
fn the_fuzzer_catches_a_bitmap_that_claims_one_more_object() {
let dir = tempfile::tempdir().unwrap();
let mut fuzz = Fuzz::new(0, dir.path(), Some(1));
while fuzz.stats.commits < 5 {
fuzz.push().unwrap();
}
fuzz.night(1, Chain::Cold).unwrap();
let pack_dir = fuzz.pack_dir();
let midx =
gix::odb::pack::multi_index::File::at(pack_dir.join("multi-pack-index"), None).unwrap();
let bitmap = pack_dir.join(format!("multi-pack-index-{}.bitmap", midx.checksum()));
let commit = midx
.oid_at_index(claim_one_more(&bitmap, fuzz.format.kind().len_in_bytes()))
.to_string();
let error = fuzz.check(&mut Night::default()).unwrap_err();
assert!(error.contains("--test-bitmap"), "{error}");
let revs = format!("{commit}\n");
assert_ne!(
fuzz.walk(&revs, true).unwrap(),
fuzz.walk(&revs, false).unwrap()
);
}