This is an archive of the discontinued Mercurial Phabricator instance.

Differential D9520

rhg: use persistent nodemap when available
ClosedPublic

Authored by SimonSapin on Dec 4 2020, 12:28 PM.

Details

Reviewers
Alphare
pulkit
Group Reviewers
hg-reviewers
Commits
rHG9eb07ab3f2d4: rhg: use persistent nodemap when available
Summary

… for node ID → revision number lookups, instead on linear scan in a revlog.

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

SimonSapin created this revision.Dec 4 2020, 12:28 PM
Alphare requested changes to this revision.Dec 7 2020, 5:43 AM
Alphare added a subscriber: Alphare.
Alphare added inline comments.
rust/hg-core/src/revlog/nodemap_docket.rs
21

I would add a comment explaining why it's ok for the docket to not exist, even if it's kind of obvious.

39

32 bit systems will have other issues before running into this one, I don't think it's worth it.

51

I think we probably want to be able to disable mmap even in Rust contexts, although that will be done in a followup, since we need to have access to the config (storage.revlog.nodemap.mmap at the time of writing).

54

I think the Python code has a bug, and that the idea is to silently ignore the missing file.

rust/hg-core/src/revlog/revlog.rs
47

Please add a docstring

116–117

I think this comment should be adjusted now that the optimization has come

tests/test-rhg.t
201

I'd add a small header line to say "test partial node prefix" or something similar.

This revision now requires changes to proceed.Dec 7 2020, 5:43 AM
Alphare added a comment.Dec 7 2020, 5:44 AM

Note to other reviewers, we're discussing moving at least some of the binary parsing in hg-core to a crate like zerocopy or bytemuck in the near future.

SimonSapin added inline comments.Dec 7 2020, 12:53 PM
rust/hg-core/src/revlog/nodemap_docket.rs
21

I’ve restructured this code a bit and added a doc-comment.

54

I’ve added a separate patch to fix that Python code.

Alphare accepted this revision.Dec 7 2020, 2:38 PM
pulkit accepted this revision.Dec 10 2020, 3:51 AM
This revision is now accepted and ready to land.Dec 10 2020, 3:51 AM
SimonSapin added a commit: rHG9eb07ab3f2d4: rhg: use persistent nodemap when available.Dec 10 2020, 4:41 AM
Closed by commit rHG9eb07ab3f2d4: rhg: use persistent nodemap when available (authored by SimonSapin). · Explain Why
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

Diff 24161

rust/hg-core/src/requirements.rs

// TODO: set this to actually-supported features // TODO: set this to actually-supported features
const SUPPORTED: &[&str] = &[ const SUPPORTED: &[&str] = &[
"dotencode", "dotencode",
"fncache", "fncache",
"generaldelta", "generaldelta",
"revlogv1", "revlogv1",
"sparserevlog", "sparserevlog",
"store", "store",
// As of this writing everything rhg does is read-only.
// When it starts writing to the repository, it’ll need to either keep the
// persistent nodemap up to date or remove this entry:
"persistent-nodemap",
]; ];

rust/hg-core/src/revlog.rs

// Copyright 2018-2020 Georges Racinet <georges.racinet@octobus.net> // Copyright 2018-2020 Georges Racinet <georges.racinet@octobus.net>
// and Mercurial contributors // and Mercurial contributors
// //
// This software may be used and distributed according to the terms of the // This software may be used and distributed according to the terms of the
// GNU General Public License version 2 or any later version. // GNU General Public License version 2 or any later version.
//! Mercurial concepts for handling revision history //! Mercurial concepts for handling revision history
pub mod node; pub mod node;
pub mod nodemap; pub mod nodemap;
mod nodemap_docket;
pub mod path_encode; pub mod path_encode;
pub use node::{Node, NodeError, NodePrefix, NodePrefixRef}; pub use node::{Node, NodeError, NodePrefix, NodePrefixRef};
pub mod changelog; pub mod changelog;
pub mod index; pub mod index;
pub mod manifest; pub mod manifest;
pub mod patch; pub mod patch;
pub mod revlog; pub mod revlog;

rust/hg-core/src/revlog/index.rs

Some(IndexEntry { Some(IndexEntry {
bytes, bytes,
offset_override, offset_override,
}) })
} }
} }
impl super::RevlogIndex for Index {
fn len(&self) -> usize {
self.len()
}
fn node(&self, rev: Revision) -> Option<&Node> {
self.get_entry(rev).map(|entry| entry.hash())
}
}
#[derive(Debug)] #[derive(Debug)]
pub struct IndexEntry<'a> { pub struct IndexEntry<'a> {
bytes: &'a [u8], bytes: &'a [u8],
/// Allows to override the offset value of the entry. /// Allows to override the offset value of the entry.
/// ///
/// For interleaved index and data, the offset stored in the index /// For interleaved index and data, the offset stored in the index
/// corresponds to the separated data offset. /// corresponds to the separated data offset.
/// It has to be overridden with the actual offset in the interleaved /// It has to be overridden with the actual offset in the interleaved
pub fn p2(&self) -> Revision { pub fn p2(&self) -> Revision {
BigEndian::read_i32(&self.bytes[28..]) BigEndian::read_i32(&self.bytes[28..])
} }
/// Return the hash of revision's full text. /// Return the hash of revision's full text.
/// ///
/// Currently, SHA-1 is used and only the first 20 bytes of this field /// Currently, SHA-1 is used and only the first 20 bytes of this field
/// are used. /// are used.
pub fn hash(&self) -> &Node { pub fn hash(&self) -> &'a Node {
(&self.bytes[32..52]).try_into().unwrap() (&self.bytes[32..52]).try_into().unwrap()
} }
} }
/// Value of the inline flag. /// Value of the inline flag.
pub fn is_inline(index_bytes: &[u8]) -> bool { pub fn is_inline(index_bytes: &[u8]) -> bool {
match &index_bytes[0..=1] { match &index_bytes[0..=1] {
[0, 0] | [0, 2] => false, [0, 0] | [0, 2] => false,

rust/hg-core/src/revlog/nodemap_docket.rs

  • This file was added.
use memmap::Mmap;
use std::convert::TryInto;
use std::path::{Path, PathBuf};
use super::revlog::{mmap_open, RevlogError};
use crate::utils::strip_suffix;
const ONDISK_VERSION: u8 = 1;
pub(super) struct NodeMapDocket {
pub data_length: usize,
// TODO: keep here more of the data from `parse()` when we need it
}
impl NodeMapDocket {
/// Return `Ok(None)` when the caller should proceed without a persistent
/// nodemap:
///
/// * This revlog does not have a `.n` docket file (it is not generated for
/// small revlogs), or
/// * The docket has an unsupported version number (repositories created by
AlphareUnsubmitted
Done

I would add a comment explaining why it's ok for the docket to not exist, even if it's kind of obvious.

Alphare: I would add a comment explaining why it's ok for the docket to not exist, even if it's kind of…
SimonSapinAuthorUnsubmitted
Done

I’ve restructured this code a bit and added a doc-comment.

SimonSapin: I’ve restructured this code a bit and added a doc-comment.
/// later hg, maybe that should be a requirement instead?), or
/// * The docket file points to a missing (likely deleted) data file (this
/// can happen in a rare race condition).
pub fn read_from_file(
index_path: &Path,
) -> Result<Option<(Self, Mmap)>, RevlogError> {
let docket_path = index_path.with_extension("n");
let docket_bytes = match std::fs::read(&docket_path) {
Err(e) if e.kind() == std::io::ErrorKind::NotFound => {
return Ok(None)
}
Err(e) => return Err(RevlogError::IoError(e)),
Ok(bytes) => bytes,
};
let mut input = if let Some((&ONDISK_VERSION, rest)) =
docket_bytes.split_first()
{
AlphareUnsubmitted
Not Done

32 bit systems will have other issues before running into this one, I don't think it's worth it.

Alphare: 32 bit systems will have other issues before running into this one, I don't think it's worth it.
rest
} else {
return Ok(None);
};
let input = &mut input;
let uid_size = read_u8(input)? as usize;
let _tip_rev = read_be_u64(input)?;
// TODO: do we care about overflow for 4 GB+ nodemap files on 32-bit
// systems?
let data_length = read_be_u64(input)? as usize;
let _data_unused = read_be_u64(input)?;
AlphareUnsubmitted
Not Done

I think we probably want to be able to disable mmap even in Rust contexts, although that will be done in a followup, since we need to have access to the config (storage.revlog.nodemap.mmap at the time of writing).

Alphare: I think we probably want to be able to disable `mmap` even in Rust contexts, although that will…
let tip_node_size = read_be_u64(input)? as usize;
let uid = read_bytes(input, uid_size)?;
let _tip_node = read_bytes(input, tip_node_size)?;
AlphareUnsubmitted
Done

I think the Python code has a bug, and that the idea is to silently ignore the missing file.

Alphare: I think the Python code has a bug, and that the idea is to silently ignore the missing file.
SimonSapinAuthorUnsubmitted
Done

I’ve added a separate patch to fix that Python code.

SimonSapin: I’ve added a separate patch to fix that Python code.
let uid =
std::str::from_utf8(uid).map_err(|_| RevlogError::Corrupted)?;
let docket = NodeMapDocket { data_length };
let data_path = rawdata_path(&docket_path, uid);
// TODO: use `std::fs::read` here when the `persistent-nodemap.mmap`
// config is false?
match mmap_open(&data_path) {
Ok(mmap) => {
if mmap.len() >= data_length {
Ok(Some((docket, mmap)))
} else {
Err(RevlogError::Corrupted)
}
}
Err(error) => {
if error.kind() == std::io::ErrorKind::NotFound {
Ok(None)
} else {
Err(RevlogError::IoError(error))
}
}
}
}
}
fn read_bytes<'a>(
input: &mut &'a [u8],
count: usize,
) -> Result<&'a [u8], RevlogError> {
if let Some(start) = input.get(..count) {
*input = &input[count..];
Ok(start)
} else {
Err(RevlogError::Corrupted)
}
}
fn read_u8<'a>(input: &mut &[u8]) -> Result<u8, RevlogError> {
Ok(read_bytes(input, 1)?[0])
}
fn read_be_u64<'a>(input: &mut &[u8]) -> Result<u64, RevlogError> {
let array = read_bytes(input, std::mem::size_of::<u64>())?
.try_into()
.unwrap();
Ok(u64::from_be_bytes(array))
}
fn rawdata_path(docket_path: &Path, uid: &str) -> PathBuf {
let docket_name = docket_path
.file_name()
.expect("expected a base name")
.to_str()
.expect("expected an ASCII file name in the store");
let prefix = strip_suffix(docket_name, ".n.a")
.or_else(|| strip_suffix(docket_name, ".n"))
.expect("expected docket path in .n or .n.a");
let name = format!("{}-{}.nd", prefix, uid);
docket_path
.parent()
.expect("expected a non-root path")
.join(name)
}

rust/hg-core/src/revlog/revlog.rs

use std::borrow::Cow; use std::borrow::Cow;
use std::fs::File; use std::fs::File;
use std::io::Read; use std::io::Read;
use std::ops::Deref; use std::ops::Deref;
use std::path::Path; use std::path::Path;
use byteorder::{BigEndian, ByteOrder}; use byteorder::{BigEndian, ByteOrder};
use crypto::digest::Digest; use crypto::digest::Digest;
use crypto::sha1::Sha1; use crypto::sha1::Sha1;
use flate2::read::ZlibDecoder; use flate2::read::ZlibDecoder;
use memmap::{Mmap, MmapOptions}; use memmap::{Mmap, MmapOptions};
use micro_timer::timed; use micro_timer::timed;
use zstd; use zstd;
use super::index::Index; use super::index::Index;
use super::node::{NodePrefixRef, NODE_BYTES_LENGTH, NULL_NODE}; use super::node::{NodePrefixRef, NODE_BYTES_LENGTH, NULL_NODE};
use super::nodemap;
use super::nodemap::NodeMap;
use super::nodemap_docket::NodeMapDocket;
use super::patch; use super::patch;
use crate::revlog::Revision; use crate::revlog::Revision;
pub enum RevlogError { pub enum RevlogError {
IoError(std::io::Error), IoError(std::io::Error),
UnsuportedVersion(u16), UnsuportedVersion(u16),
InvalidRevision, InvalidRevision,
/// Found more than one entry whose ID match the requested prefix /// Found more than one entry whose ID match the requested prefix
AmbiguousPrefix, AmbiguousPrefix,
Corrupted, Corrupted,
UnknowDataFormat(u8), UnknowDataFormat(u8),
} }
fn mmap_open(path: &Path) -> Result<Mmap, std::io::Error> { pub(super) fn mmap_open(path: &Path) -> Result<Mmap, std::io::Error> {
let file = File::open(path)?; let file = File::open(path)?;
let mmap = unsafe { MmapOptions::new().map(&file) }?; let mmap = unsafe { MmapOptions::new().map(&file) }?;
Ok(mmap) Ok(mmap)
} }
/// Read only implementation of revlog. /// Read only implementation of revlog.
pub struct Revlog { pub struct Revlog {
/// When index and data are not interleaved: bytes of the revlog index. /// When index and data are not interleaved: bytes of the revlog index.
/// When index and data are interleaved: bytes of the revlog index and /// When index and data are interleaved: bytes of the revlog index and
/// data. /// data.
index: Index, index: Index,
/// When index and data are not interleaved: bytes of the revlog data /// When index and data are not interleaved: bytes of the revlog data
data_bytes: Option<Box<dyn Deref<Target = [u8]> + Send>>, data_bytes: Option<Box<dyn Deref<Target = [u8]> + Send>>,
/// When present on disk: the persistent nodemap for this revlog
AlphareUnsubmitted
Done

Please add a docstring

Alphare: Please add a docstring
nodemap: Option<nodemap::NodeTree>,
} }
impl Revlog { impl Revlog {
/// Open a revlog index file. /// Open a revlog index file.
/// ///
/// It will also open the associated data file if index and data are not /// It will also open the associated data file if index and data are not
/// interleaved. /// interleaved.
#[timed] #[timed]
None None
} else { } else {
let data_path = data_path.unwrap_or(&default_data_path); let data_path = data_path.unwrap_or(&default_data_path);
let data_mmap = let data_mmap =
mmap_open(data_path).map_err(RevlogError::IoError)?; mmap_open(data_path).map_err(RevlogError::IoError)?;
Some(Box::new(data_mmap)) Some(Box::new(data_mmap))
}; };
Ok(Revlog { index, data_bytes }) let nodemap = NodeMapDocket::read_from_file(index_path)?.map(
|(docket, data)| {
nodemap::NodeTree::load_bytes(
Box::new(data),
docket.data_length,
)
},
);
Ok(Revlog {
index,
data_bytes,
nodemap,
})
} }
/// Return number of entries of the `Revlog`. /// Return number of entries of the `Revlog`.
pub fn len(&self) -> usize { pub fn len(&self) -> usize {
self.index.len() self.index.len()
} }
/// Returns `true` if the `Revlog` has zero `entries`. /// Returns `true` if the `Revlog` has zero `entries`.
pub fn is_empty(&self) -> bool { pub fn is_empty(&self) -> bool {
self.index.is_empty() self.index.is_empty()
} }
/// Return the full data associated to a node. /// Return the full data associated to a node.
#[timed] #[timed]
pub fn get_node_rev( pub fn get_node_rev(
&self, &self,
node: NodePrefixRef, node: NodePrefixRef,
) -> Result<Revision, RevlogError> { ) -> Result<Revision, RevlogError> {
// This is brute force. But it is fast enough for now. if let Some(nodemap) = &self.nodemap {
AlphareUnsubmitted
Done

I think this comment should be adjusted now that the optimization has come

Alphare: I think this comment should be adjusted now that the optimization has come
// Optimization will come later. return nodemap
.find_bin(&self.index, node)
// TODO: propagate details of this error:
.map_err(|_| RevlogError::Corrupted)?
.ok_or(RevlogError::InvalidRevision);
}
// Fallback to linear scan when a persistent nodemap is not present.
// This happens when the persistent-nodemap experimental feature is not
// enabled, or for small revlogs.
//
// TODO: consider building a non-persistent nodemap in memory to
// optimize these cases.
let mut found_by_prefix = None; let mut found_by_prefix = None;
for rev in (0..self.len() as Revision).rev() { for rev in (0..self.len() as Revision).rev() {
let index_entry = let index_entry =
self.index.get_entry(rev).ok_or(RevlogError::Corrupted)?; self.index.get_entry(rev).ok_or(RevlogError::Corrupted)?;
if node == *index_entry.hash() { if node == *index_entry.hash() {
return Ok(rev); return Ok(rev);
} }
if node.is_prefix_of(index_entry.hash()) { if node.is_prefix_of(index_entry.hash()) {

rust/hg-core/src/utils.rs

} }
} }
impl<'a> Escaped for &'a HgPath { impl<'a> Escaped for &'a HgPath {
fn escaped_bytes(&self) -> Vec<u8> { fn escaped_bytes(&self) -> Vec<u8> {
self.as_bytes().escaped_bytes() self.as_bytes().escaped_bytes()
} }
} }
// TODO: use the str method when we require Rust 1.45
pub(crate) fn strip_suffix<'a>(s: &'a str, suffix: &str) -> Option<&'a str> {
if s.ends_with(suffix) {
Some(&s[..s.len() - suffix.len()])
} else {
None
}
}

tests/test-rhg.t

$ hg debugbuilddag .+5000 --overwritten-file --config "storage.revlog.nodemap.mode=warn" $ hg debugbuilddag .+5000 --overwritten-file --config "storage.revlog.nodemap.mode=warn"
$ hg id -r tip $ hg id -r tip
c3ae8dec9fad tip c3ae8dec9fad tip
$ ls .hg/store/00changelog* $ ls .hg/store/00changelog*
.hg/store/00changelog-*.nd (glob) .hg/store/00changelog-*.nd (glob)
.hg/store/00changelog.d .hg/store/00changelog.d
.hg/store/00changelog.i .hg/store/00changelog.i
.hg/store/00changelog.n .hg/store/00changelog.n
Specifying revisions by changeset ID
$ rhg files -r c3ae8dec9fad $ rhg files -r c3ae8dec9fad
AlphareUnsubmitted
Done

I'd add a small header line to say "test partial node prefix" or something similar.

Alphare: I'd add a small header line to say "test partial node prefix" or something similar.
[252] of
$ rhg cat -r c3ae8dec9fad of
r5000