This is an archive of the discontinued Mercurial Phabricator instance.

Differential D8215

rust-status: move to recursive traversal to prepare for parallel traversal
ClosedPublic

Authored by Alphare on Mar 4 2020, 10:29 AM.

Details

Reviewers
None
Group Reviewers
hg-reviewers
Commits
rHGf8a9922a02cb: rust-status: move to recursive traversal to prepare for parallel traversal
Summary

I have looked into traversing the working directory in parallel either
by a recursive or an iterative algorithm. The recursive approach won quite
decisively both in terms of performance and code readability.

You can look at my experiment here:
https://heptapod.octobus.net/Alphare/rayon-recursive-traversal

The chance of a stack overflow happening because the directories get too nested
seems slim.

This change does not yet do anything in parallel.

Diff Detail

Repository
rHG Mercurial
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

Alphare created this revision.Mar 4 2020, 10:29 AM
durin42 added a subscriber: durin42.Mar 4 2020, 4:29 PM

I'm broadly happy with this series, but:

  1. I get test-check-rust-format.t errors
  2. I don't seem to be having any luck running the tests. It looks like the rust module policy doesn't cause the right things to get installed? In particular, HGWITHRUSTEXT=cpython HGMODULEPOLICY=rust+c make clean tests flunks test-remotefilelog-datapack.py because it can't import parsers.so? And it looks like test-dirstate-race.t is just broken by this series?
  3. The re2-missing fallback message breaks tests for users that want rust things, but lack re2. This isn't going to work, I'm afraid.

The series is so big it's not practical for me to figure out which revision(s) I should be commenting on, so hopefully that's actionable feedback...

Alphare updated this revision to Diff 20500.Mar 5 2020, 3:34 AM
Alphare added a subscriber: marmoute.Mar 5 2020, 3:42 AM
In D8215#122325, @durin42 wrote:
  1. I get test-check-rust-format.t errors

Indeed. It appears that none of the machines I use to run the entire test suite (so... not my laptop) have rustfmt installed, which skips this test. I have updated the series to fix this issue, and will install rustfmt where needed.

  1. I don't seem to be having any luck running the tests. It looks like the rust module policy doesn't cause the right things to get installed? In particular, HGWITHRUSTEXT=cpython HGMODULEPOLICY=rust+c make clean tests flunks test-remotefilelog-datapack.py because it can't import parsers.so? And it looks like test-dirstate-race.t is just broken by this series?

I will look into this, this is bad.

  1. The re2-missing fallback message breaks tests for users that want rust things, but lack re2. This isn't going to work, I'm afraid.

@marmoute suggested I do something in debuginstall to check for re2 on the Rust side instead, I think it's a good idea.

The series is so big it's not practical for me to figure out which revision(s) I should be commenting on, so hopefully that's actionable feedback...

It is, thanks!

Alphare added a comment.Mar 6 2020, 3:48 AM
In D8215#122325, @durin42 wrote:

And it looks like test-dirstate-race.t is just broken by this series?

I can't reproduce that however. Do you have a particular way of doing so? Because it's a race test... it might be flaky.

I still don't have a clear solution for the modulepolicy thing, because everything is broken if we use strict policies.

Alphare added a comment.Mar 6 2020, 4:26 AM
In D8215#122642, @Alphare wrote:

I still don't have a clear solution for the modulepolicy thing, because everything is broken if we use strict policies.

It appears that I got confused by an unrelated issue. @marmoute pushed a fix for this as D8245.

Alphare updated this revision to Diff 20561.Mar 6 2020, 11:31 AM
Alphare added a commit: rHGf8a9922a02cb: rust-status: move to recursive traversal to prepare for parallel traversal.Mar 11 2020, 12:25 PM
This revision was not accepted when it landed; it landed in state Needs Review.
Closed by commit rHGf8a9922a02cb: rust-status: move to recursive traversal to prepare for parallel traversal (authored by Alphare). · Explain Why
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

PathPackages
Mrust/hg-core/src/dirstate/status.rs (291 lines)

Diff 20729

rust/hg-core/src/dirstate/status.rs

}, },
path_auditor::PathAuditor, path_auditor::PathAuditor,
}, },
CopyMap, DirstateEntry, DirstateMap, EntryState, FastHashMap, CopyMap, DirstateEntry, DirstateMap, EntryState, FastHashMap,
PatternError, PatternError,
}; };
use lazy_static::lazy_static; use lazy_static::lazy_static;
use rayon::prelude::*; use rayon::prelude::*;
use std::collections::VecDeque;
use std::{ use std::{
borrow::Cow, borrow::Cow,
collections::HashSet, collections::HashSet,
fs::{read_dir, DirEntry}, fs::{read_dir, DirEntry},
io::ErrorKind, io::ErrorKind,
ops::Deref, ops::Deref,
path::Path, path::Path,
}; };
/// Wrong type of file from a `BadMatch` /// Wrong type of file from a `BadMatch`
/// Note: a lot of those don't exist on all platforms. /// Note: a lot of those don't exist on all platforms.
#[derive(Debug)] #[derive(Debug, Copy, Clone)]
pub enum BadType { pub enum BadType {
CharacterDevice, CharacterDevice,
BlockDevice, BlockDevice,
FIFO, FIFO,
Socket, Socket,
Directory, Directory,
Unknown, Unknown,
} }
impl ToString for BadType { impl ToString for BadType {
fn to_string(&self) -> String { fn to_string(&self) -> String {
match self { match self {
BadType::CharacterDevice => "character device", BadType::CharacterDevice => "character device",
BadType::BlockDevice => "block device", BadType::BlockDevice => "block device",
BadType::FIFO => "fifo", BadType::FIFO => "fifo",
BadType::Socket => "socket", BadType::Socket => "socket",
BadType::Directory => "directory", BadType::Directory => "directory",
BadType::Unknown => "unknown", BadType::Unknown => "unknown",
} }
.to_string() .to_string()
} }
} }
/// Was explicitly matched but cannot be found/accessed /// Was explicitly matched but cannot be found/accessed
#[derive(Debug)] #[derive(Debug, Copy, Clone)]
pub enum BadMatch { pub enum BadMatch {
OsError(i32), OsError(i32),
BadType(BadType), BadType(BadType),
} }
/// Marker enum used to dispatch new status entries into the right collections. /// Marker enum used to dispatch new status entries into the right collections.
/// Is similar to `crate::EntryState`, but represents the transient state of /// Is similar to `crate::EntryState`, but represents the transient state of
/// entries during the lifetime of a command. /// entries during the lifetime of a command.
#[derive(Debug)] #[derive(Debug, Copy, Clone)]
enum Dispatch { enum Dispatch {
Unsure, Unsure,
Modified, Modified,
Added, Added,
Removed, Removed,
Deleted, Deleted,
Clean, Clean,
Unknown, Unknown,
pub last_normal_time: i64, pub last_normal_time: i64,
/// Whether we are on a filesystem with UNIX-like exec flags /// Whether we are on a filesystem with UNIX-like exec flags
pub check_exec: bool, pub check_exec: bool,
pub list_clean: bool, pub list_clean: bool,
pub list_unknown: bool, pub list_unknown: bool,
pub list_ignored: bool, pub list_ignored: bool,
} }
/// Dispatch a single file found during `traverse`. /// Dispatch a single entry (file, folder, symlink...) found during `traverse`.
/// If `file` is a folder that needs to be traversed, it will be pushed into /// If the entry is a folder that needs to be traversed, it will be pushed into
/// `work`. /// `work`.
fn traverse_worker<'a>( fn handle_traversed_entry<'a>(
work: &mut VecDeque<HgPathBuf>, dir_entry: &DirEntry,
matcher: &impl Matcher, matcher: &(impl Matcher + Sync),
root_dir: impl AsRef<Path>,
dmap: &DirstateMap, dmap: &DirstateMap,
filename: impl AsRef<HgPath>, filename: impl AsRef<HgPath>,
dir_entry: &DirEntry, old_results: &FastHashMap<Cow<'a, HgPath>, Dispatch>,
ignore_fn: &impl for<'r> Fn(&'r HgPath) -> bool, ignore_fn: &(impl for<'r> Fn(&'r HgPath) -> bool + Sync),
dir_ignore_fn: &impl for<'r> Fn(&'r HgPath) -> bool, dir_ignore_fn: &(impl for<'r> Fn(&'r HgPath) -> bool + Sync),
options: StatusOptions, options: StatusOptions,
) -> Option<IoResult<(Cow<'a, HgPath>, Dispatch)>> { ) -> IoResult<Vec<(Cow<'a, HgPath>, Dispatch)>> {
let file_type = match dir_entry.file_type() { let file_type = dir_entry.file_type()?;
Ok(x) => x,
Err(e) => return Some(Err(e.into())),
};
let filename = filename.as_ref(); let filename = filename.as_ref();
let entry_option = dmap.get(filename); let entry_option = dmap.get(filename);
if file_type.is_dir() { if file_type.is_dir() {
// Do we need to traverse it? // Do we need to traverse it?
if !ignore_fn(&filename) || options.list_ignored { if !ignore_fn(&filename) || options.list_ignored {
work.push_front(filename.to_owned()); return traverse_dir(
matcher,
root_dir,
dmap,
filename.to_owned(),
&old_results,
ignore_fn,
dir_ignore_fn,
options,
);
} }
// Nested `if` until `rust-lang/rust#53668` is stable // Nested `if` until `rust-lang/rust#53668` is stable
if let Some(entry) = entry_option { if let Some(entry) = entry_option {
// Used to be a file, is now a folder // Used to be a file, is now a folder
if matcher.matches_everything() || matcher.matches(&filename) { if matcher.matches_everything() || matcher.matches(&filename) {
return Some(Ok(( return Ok(vec![(
Cow::Owned(filename.to_owned()), Cow::Owned(filename.to_owned()),
dispatch_missing(entry.state), dispatch_missing(entry.state),
))); )]);
} }
} }
} else if file_type.is_file() || file_type.is_symlink() { } else if file_type.is_file() || file_type.is_symlink() {
if let Some(entry) = entry_option { if let Some(entry) = entry_option {
if matcher.matches_everything() || matcher.matches(&filename) { if matcher.matches_everything() || matcher.matches(&filename) {
let metadata = match dir_entry.metadata() { let metadata = dir_entry.metadata()?;
Ok(x) => x, return Ok(vec![(
Err(e) => return Some(Err(e.into())),
};
return Some(Ok((
Cow::Owned(filename.to_owned()), Cow::Owned(filename.to_owned()),
dispatch_found( dispatch_found(
&filename, &filename,
*entry, *entry,
HgMetadata::from_metadata(metadata), HgMetadata::from_metadata(metadata),
&dmap.copy_map, &dmap.copy_map,
options, options,
), ),
))); )]);
} }
} else if (matcher.matches_everything() || matcher.matches(&filename)) } else if (matcher.matches_everything() || matcher.matches(&filename))
&& !ignore_fn(&filename) && !ignore_fn(&filename)
{ {
if (options.list_ignored || matcher.exact_match(&filename)) if (options.list_ignored || matcher.exact_match(&filename))
&& dir_ignore_fn(&filename) && dir_ignore_fn(&filename)
{ {
if options.list_ignored { if options.list_ignored {
return Some(Ok(( return Ok(vec![(
Cow::Owned(filename.to_owned()), Cow::Owned(filename.to_owned()),
Dispatch::Ignored, Dispatch::Ignored,
))); )]);
} }
} else { } else {
return Some(Ok(( return Ok(vec![(
Cow::Owned(filename.to_owned()), Cow::Owned(filename.to_owned()),
Dispatch::Unknown, Dispatch::Unknown,
))); )]);
} }
} else if ignore_fn(&filename) && options.list_ignored {
return Ok(vec![(
Cow::Owned(filename.to_owned()),
Dispatch::Ignored,
)]);
} }
} else if let Some(entry) = entry_option { } else if let Some(entry) = entry_option {
// Used to be a file or a folder, now something else. // Used to be a file or a folder, now something else.
if matcher.matches_everything() || matcher.matches(&filename) { if matcher.matches_everything() || matcher.matches(&filename) {
return Some(Ok(( return Ok(vec![(
Cow::Owned(filename.to_owned()), Cow::Owned(filename.to_owned()),
dispatch_missing(entry.state), dispatch_missing(entry.state),
))); )]);
} }
} }
None return Ok(vec![]);
} }
/// Walk the working directory recursively to look for changes compared to the /// Decides whether the directory needs to be listed, and if so dispatches its
/// current `DirstateMap`. /// entries
fn traverse<'a>( fn traverse_dir<'a>(
matcher: &(impl Matcher + Sync), matcher: &(impl Matcher + Sync),
root_dir: impl AsRef<Path>, root_dir: impl AsRef<Path>,
dmap: &DirstateMap, dmap: &DirstateMap,
path: impl AsRef<HgPath>, path: impl AsRef<HgPath>,
old_results: FastHashMap<Cow<'a, HgPath>, Dispatch>, old_results: &FastHashMap<Cow<'a, HgPath>, Dispatch>,
ignore_fn: &(impl for<'r> Fn(&'r HgPath) -> bool + Sync), ignore_fn: &(impl for<'r> Fn(&'r HgPath) -> bool + Sync),
dir_ignore_fn: &(impl for<'r> Fn(&'r HgPath) -> bool + Sync), dir_ignore_fn: &(impl for<'r> Fn(&'r HgPath) -> bool + Sync),
options: StatusOptions, options: StatusOptions,
) -> IoResult<FastHashMap<Cow<'a, HgPath>, Dispatch>> { ) -> IoResult<Vec<(Cow<'a, HgPath>, Dispatch)>> {
let root_dir = root_dir.as_ref(); let directory = path.as_ref();
let mut new_results = FastHashMap::default();
let mut work = VecDeque::new();
work.push_front(path.as_ref().to_owned());
while let Some(ref directory) = work.pop_front() {
if directory.as_bytes() == b".hg" { if directory.as_bytes() == b".hg" {
continue; return Ok(vec![]);
} }
let visit_entries = match matcher.visit_children_set(directory) { let visit_entries = match matcher.visit_children_set(directory) {
VisitChildrenSet::Empty => continue, VisitChildrenSet::Empty => return Ok(vec![]),
VisitChildrenSet::This | VisitChildrenSet::Recursive => None, VisitChildrenSet::This | VisitChildrenSet::Recursive => None,
VisitChildrenSet::Set(set) => Some(set), VisitChildrenSet::Set(set) => Some(set),
}; };
let buf = hg_path_to_path_buf(directory)?; let buf = hg_path_to_path_buf(directory)?;
let dir_path = root_dir.join(buf); let dir_path = root_dir.as_ref().join(buf);
let skip_dot_hg = !directory.as_bytes().is_empty(); let skip_dot_hg = !directory.as_bytes().is_empty();
let entries = match list_directory(dir_path, skip_dot_hg) { let entries = match list_directory(dir_path, skip_dot_hg) {
Err(e) => match e.kind() { Err(e) => match e.kind() {
ErrorKind::NotFound | ErrorKind::PermissionDenied => { ErrorKind::NotFound | ErrorKind::PermissionDenied => {
new_results.insert( return Ok(vec![(
Cow::Owned(directory.to_owned()), Cow::Owned(directory.to_owned()),
Dispatch::Bad(BadMatch::OsError( Dispatch::Bad(BadMatch::OsError(
// Unwrapping here is OK because the error always // Unwrapping here is OK because the error always
// is a real os error // is a real os error
e.raw_os_error().unwrap(), e.raw_os_error().unwrap(),
)), )),
); )]);
continue;
} }
_ => return Err(e), _ => return Err(e),
}, },
Ok(entries) => entries, Ok(entries) => entries,
}; };
let mut new_results = vec![];
for (filename, dir_entry) in entries { for (filename, dir_entry) in entries {
if let Some(ref set) = visit_entries { if let Some(ref set) = visit_entries {
if !set.contains(filename.deref()) { if !set.contains(filename.deref()) {
continue; continue;
} }
} }
// TODO normalize // TODO normalize
let filename = if directory.is_empty() { let filename = if directory.is_empty() {
filename.to_owned() filename.to_owned()
} else { } else {
directory.join(&filename) directory.join(&filename)
}; };
if !old_results.contains_key(filename.deref()) { if !old_results.contains_key(filename.deref()) {
if let Some((res, dispatch)) = traverse_worker( new_results.extend(handle_traversed_entry(
&mut work, &dir_entry,
matcher, matcher,
root_dir.as_ref(),
&dmap, &dmap,
&filename, &filename,
&dir_entry, old_results,
&ignore_fn, ignore_fn,
&dir_ignore_fn, dir_ignore_fn,
options, options,
) )?);
.transpose()?
{
new_results.insert(res, dispatch);
}
} }
} }
}
new_results.extend(old_results.into_iter());
Ok(new_results) Ok(new_results)
} }
/// Stat all entries in the `DirstateMap` and mark them for dispatch. /// Stat all entries in the `DirstateMap` and mark them for dispatch.
fn stat_dmap_entries( fn stat_dmap_entries(
dmap: &DirstateMap, dmap: &DirstateMap,
root_dir: impl AsRef<Path> + Sync + Send, root_dir: impl AsRef<Path> + Sync + Send,
options: StatusOptions, options: StatusOptions,
false false
} }
}; };
let files = matcher.file_set(); let files = matcher.file_set();
// Step 1: check the files explicitly mentioned by the user // Step 1: check the files explicitly mentioned by the user
let explicit = walk_explicit(files, &dmap, root_dir, options); let explicit = walk_explicit(files, &dmap, root_dir, options);
let (work, mut results): (Vec<_>, FastHashMap<_, _>) = explicit
// Collect results into a `Vec` because we do very few lookups in most
// cases.
let (work, mut results): (Vec<_>, Vec<_>) = explicit
.filter_map(Result::ok) .filter_map(Result::ok)
.map(|(filename, dispatch)| (Cow::Borrowed(filename), dispatch)) .map(|(filename, dispatch)| (Cow::Borrowed(filename), dispatch))
.partition(|(_, dispatch)| match dispatch { .partition(|(_, dispatch)| match dispatch {
Dispatch::Directory { .. } => true, Dispatch::Directory { .. } => true,
_ => false, _ => false,
}); });
// Step 2: recursively check the working directory for changes if needed if !work.is_empty() {
// Hashmaps are quite a bit slower to build than vecs, so only build it
// if needed.
let old_results = results.iter().cloned().collect();
// Step 2: recursively check the working directory for changes if
// needed
for (dir, dispatch) in work { for (dir, dispatch) in work {
match dispatch { match dispatch {
Dispatch::Directory { was_file } => { Dispatch::Directory { was_file } => {
if was_file { if was_file {
results.insert(dir.to_owned(), Dispatch::Removed); results.push((dir.to_owned(), Dispatch::Removed));
} }
if options.list_ignored if options.list_ignored
|| options.list_unknown && !dir_ignore_fn(&dir) || options.list_unknown && !dir_ignore_fn(&dir)
{ {
results = traverse( results.par_extend(traverse_dir(
matcher, matcher,
root_dir, root_dir,
&dmap, &dmap,
&dir, &dir,
results, &old_results,
&ignore_fn, &ignore_fn,
&dir_ignore_fn, &dir_ignore_fn,
options, options,
)?; )?);
} }
} }
_ => unreachable!("There can only be directories in `work`"), _ => unreachable!("There can only be directories in `work`"),
} }
} }
}
if !matcher.is_exact() { if !matcher.is_exact() {
// Step 3: Check the remaining files from the dmap. // Step 3: Check the remaining files from the dmap.
// If a dmap file is not in results yet, it was either // If a dmap file is not in results yet, it was either
// a) not matched b) ignored, c) missing, or d) under a // a) not matched b) ignored, c) missing, or d) under a
// symlink directory. // symlink directory.
if options.list_unknown { if options.list_unknown {
let to_visit: Box<dyn Iterator<Item = (&HgPath, &DirstateEntry)>> = let to_visit: Box<dyn Iterator<Item = (&HgPath, &DirstateEntry)>> =
if results.is_empty() && matcher.matches_everything() { if results.is_empty() && matcher.matches_everything() {
Box::new(dmap.iter().map(|(f, e)| (f.deref(), e))) Box::new(dmap.iter().map(|(f, e)| (f.deref(), e)))
} else { } else {
Box::new(dmap.iter().filter_map(|(f, e)| { // Only convert to a hashmap if needed.
if !results.contains_key(f.deref()) let old_results: FastHashMap<_, _> =
results.iter().cloned().collect();
Box::new(dmap.iter().filter_map(move |(f, e)| {
if !old_results.contains_key(f.deref())
&& matcher.matches(f) && matcher.matches(f)
{ {
Some((f.deref(), e)) Some((f.deref(), e))
} else { } else {
None None
} }
})) }))
}; };
let mut to_visit: Vec<_> = to_visit.collect(); let mut to_visit: Vec<_> = to_visit.collect();
to_visit.sort_by(|a, b| a.0.cmp(&b.0)); to_visit.sort_by(|a, b| a.0.cmp(&b.0));
// We walked all dirs under the roots that weren't ignored, and // We walked all dirs under the roots that weren't ignored, and
// everything that matched was stat'ed and is already in results. // everything that matched was stat'ed and is already in results.
// The rest must thus be ignored or under a symlink. // The rest must thus be ignored or under a symlink.
let path_auditor = PathAuditor::new(root_dir); let path_auditor = PathAuditor::new(root_dir);
for (ref filename, entry) in to_visit { for (ref filename, entry) in to_visit {
// Report ignored items in the dmap as long as they are not // Report ignored items in the dmap as long as they are not
// under a symlink directory. // under a symlink directory.
if path_auditor.check(filename) { if path_auditor.check(filename) {
// TODO normalize for case-insensitive filesystems // TODO normalize for case-insensitive filesystems
let buf = hg_path_to_path_buf(filename)?; let buf = hg_path_to_path_buf(filename)?;
results.insert( results.push((
Cow::Borrowed(filename), Cow::Borrowed(filename),
match root_dir.as_ref().join(&buf).symlink_metadata() { match root_dir.as_ref().join(&buf).symlink_metadata() {
// File was just ignored, no links, and exists // File was just ignored, no links, and exists
Ok(meta) => { Ok(meta) => {
let metadata = HgMetadata::from_metadata(meta); let metadata = HgMetadata::from_metadata(meta);
dispatch_found( dispatch_found(
filename, filename,
*entry, *entry,
metadata, metadata,
&dmap.copy_map, &dmap.copy_map,
options, options,
) )
} }
// File doesn't exist // File doesn't exist
Err(_) => dispatch_missing(entry.state), Err(_) => dispatch_missing(entry.state),
}, },
); ));
} else { } else {
// It's either missing or under a symlink directory which // It's either missing or under a symlink directory which
// we, in this case, report as missing. // we, in this case, report as missing.
results.insert( results.push((
Cow::Borrowed(filename), Cow::Borrowed(filename),
dispatch_missing(entry.state), dispatch_missing(entry.state),
); ));
} }
} }
} else { } else {
// We may not have walked the full directory tree above, so stat // We may not have walked the full directory tree above, so stat
// and check everything we missed. // and check everything we missed.
let stat_results = stat_dmap_entries(&dmap, root_dir, options); let stat_results = stat_dmap_entries(&dmap, root_dir, options);
results.par_extend(stat_results.flatten().map( results.par_extend(stat_results.flatten().map(
|(filename, dispatch)| (Cow::Borrowed(filename), dispatch), |(filename, dispatch)| (Cow::Borrowed(filename), dispatch),
)); ));
} }
} }
let results = results.into_iter().filter_map(|(filename, dispatch)| {
match dispatch {
Dispatch::Bad(_) => return Some((filename, dispatch)),
_ => {}
};
// TODO do this in //, not at the end
if !dmap.contains_key(filename.deref()) {
if (options.list_ignored || matcher.exact_match(&filename))
&& dir_ignore_fn(&filename)
{
if options.list_ignored {
return Some((filename.to_owned(), Dispatch::Ignored));
}
} else {
if !ignore_fn(&filename) {
return Some((filename.to_owned(), Dispatch::Unknown));
}
}
return None;
}
Some((filename, dispatch))
});
Ok((build_response(results), warnings)) Ok((build_response(results), warnings))
} }