This is an archive of the discontinued Mercurial Phabricator instance.

Differential D9106

hg-core: make `Index` owner of its bytes (D8958#inline-14994 followup 1/2)
ClosedPublic

Authored by acezar on Sep 28 2020, 9:49 AM.

Details

Reviewers
Alphare
Group Reviewers
hg-reviewers
Commits
rHG900b9b79b99c: hg-core: make `Index` owner of its bytes (D8958#inline-14994 followup 1/2)
Summary

Prevent building Index every time it is needed. It was a bad idea anyway.

When Index::new will return Result it will avoid things like Revlog::len
returning Result<usize> instead of usize.

  • make Index owner of its bytes
  • make Index::new return an error if offset != bytes.len()

Diff Detail

Repository
rHG Mercurial
Branch
default
Lint
No Linters Available
Unit
No Unit Test Coverage

Event Timeline

acezar created this revision.Sep 28 2020, 9:49 AM
Alphare accepted this revision.Sep 28 2020, 10:28 AM
Alphare added a subscriber: Alphare.

Yep, this is a lot better. Does this affect the benchmarks at all?

acezar updated this revision to Diff 22910.Sep 29 2020, 4:20 AM
acezar added a comment.Sep 29 2020, 4:22 AM
In D9106#136640, @Alphare wrote:

Yep, this is a lot better. Does this affect the benchmarks at all?

The whole series improves rhg cat by 2ms

Antoine cezar <acezar@chwitlabs.fr> added a commit: rHG900b9b79b99c: hg-core: make `Index` owner of its bytes (D8958#inline-14994 followup 1/2).Sep 29 2020, 1:52 PM
This revision was not accepted when it landed; it landed in state Needs Review.
Closed by commit rHG900b9b79b99c: hg-core: make `Index` owner of its bytes (D8958#inline-14994 followup 1/2) (authored by Antoine cezar <acezar@chwitlabs.fr>). · Explain Why
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

Diff 22910

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

use std::ops::Deref;
use byteorder::{BigEndian, ByteOrder}; use byteorder::{BigEndian, ByteOrder};
use crate::revlog::{Revision, NULL_REVISION}; use crate::revlog::{Revision, NULL_REVISION};
pub const INDEX_ENTRY_SIZE: usize = 64; pub const INDEX_ENTRY_SIZE: usize = 64;
/// A Revlog index /// A Revlog index
#[derive(Debug)] pub struct Index {
pub struct Index<'a> { bytes: Box<dyn Deref<Target = [u8]> + Send>,
bytes: &'a [u8],
/// Offsets of starts of index blocks. /// Offsets of starts of index blocks.
/// Only needed when the index is interleaved with data. /// Only needed when the index is interleaved with data.
offsets: Option<Vec<usize>>, offsets: Option<Vec<usize>>,
} }
impl<'a> Index<'a> { impl Index {
/// Create an index from bytes. /// Create an index from bytes.
/// Calculate the start of each entry when is_inline is true. /// Calculate the start of each entry when is_inline is true.
pub fn new(bytes: &'a [u8], is_inline: bool) -> Self { pub fn new(bytes: Box<dyn Deref<Target = [u8]> + Send>) -> Self {
if is_inline { if is_inline(&bytes) {
let mut offset: usize = 0; let mut offset: usize = 0;
let mut offsets = Vec::new(); let mut offsets = Vec::new();
while INDEX_ENTRY_SIZE + offset <= bytes.len() { while INDEX_ENTRY_SIZE + offset <= bytes.len() {
offsets.push(offset); offsets.push(offset);
let end = offset + INDEX_ENTRY_SIZE; let end = offset + INDEX_ENTRY_SIZE;
let entry = IndexEntry { let entry = IndexEntry {
bytes: &bytes[offset..end], bytes: &bytes[offset..end],
} else { } else {
Self { Self {
bytes, bytes,
offsets: None, offsets: None,
} }
} }
} }
/// Value of the inline flag.
pub fn is_inline(&self) -> bool {
is_inline(&self.bytes)
}
/// Return a slice of bytes if `revlog` is inline. Panic if not.
pub fn data(&self, start: usize, end: usize) -> &[u8] {
if !self.is_inline() {
panic!("tried to access data in the index of a revlog that is not inline");
}
&self.bytes[start..end]
}
/// Return number of entries of the revlog index. /// Return number of entries of the revlog index.
pub fn len(&self) -> usize { pub fn len(&self) -> usize {
if let Some(offsets) = &self.offsets { if let Some(offsets) = &self.offsets {
offsets.len() offsets.len()
} else { } else {
self.bytes.len() / INDEX_ENTRY_SIZE self.bytes.len() / INDEX_ENTRY_SIZE
} }
} }
/// ///
/// 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) -> &[u8] { pub fn hash(&self) -> &[u8] {
&self.bytes[32..52] &self.bytes[32..52]
} }
} }
/// Value of the inline flag.
pub fn is_inline(index_bytes: &[u8]) -> bool {
match &index_bytes[0..=1] {
[0, 0] | [0, 2] => false,
_ => true,
}
}
#[cfg(test)] #[cfg(test)]
mod tests { mod tests {
use super::*; use super::*;
#[cfg(test)] #[cfg(test)]
#[derive(Debug, Copy, Clone)] #[derive(Debug, Copy, Clone)]
pub struct IndexEntryBuilder { pub struct IndexEntryBuilder {
is_first: bool, is_first: bool,
bytes.extend(&self.compressed_len.to_be_bytes()[4..]); bytes.extend(&self.compressed_len.to_be_bytes()[4..]);
bytes.extend(&self.uncompressed_len.to_be_bytes()[4..]); bytes.extend(&self.uncompressed_len.to_be_bytes()[4..]);
bytes.extend(&self.base_revision.to_be_bytes()); bytes.extend(&self.base_revision.to_be_bytes());
bytes bytes
} }
} }
#[test] #[test]
fn is_not_inline_when_no_inline_flag_test() {
let bytes = IndexEntryBuilder::new()
.is_first(true)
.with_general_delta(false)
.with_inline(false)
.build();
assert_eq!(is_inline(&bytes), false)
}
#[test]
fn is_inline_when_inline_flag_test() {
let bytes = IndexEntryBuilder::new()
.is_first(true)
.with_general_delta(false)
.with_inline(true)
.build();
assert_eq!(is_inline(&bytes), true)
}
#[test]
fn is_inline_when_inline_and_generaldelta_flags_test() {
let bytes = IndexEntryBuilder::new()
.is_first(true)
.with_general_delta(true)
.with_inline(true)
.build();
assert_eq!(is_inline(&bytes), true)
}
#[test]
fn test_offset() { fn test_offset() {
let bytes = IndexEntryBuilder::new().with_offset(1).build(); let bytes = IndexEntryBuilder::new().with_offset(1).build();
let entry = IndexEntry { let entry = IndexEntry {
bytes: &bytes, bytes: &bytes,
offset_override: None, offset_override: None,
}; };
assert_eq!(entry.offset(), 1) assert_eq!(entry.offset(), 1)

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

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_bytes: Box<dyn Deref<Target = [u8]> + Send>, 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>>,
} }
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]
pub fn open(index_path: &Path) -> Result<Self, RevlogError> { pub fn open(index_path: &Path) -> Result<Self, RevlogError> {
let index_mmap = let index_mmap =
mmap_open(&index_path).map_err(RevlogError::IoError)?; mmap_open(&index_path).map_err(RevlogError::IoError)?;
let version = get_version(&index_mmap); let version = get_version(&index_mmap);
if version != 1 { if version != 1 {
return Err(RevlogError::UnsuportedVersion(version)); return Err(RevlogError::UnsuportedVersion(version));
} }
let is_inline = is_inline(&index_mmap); let index = Index::new(Box::new(index_mmap));
let index_bytes = Box::new(index_mmap);
// TODO load data only when needed // // TODO load data only when needed //
// type annotation required // type annotation required
// won't recognize Mmap as Deref<Target = [u8]> // won't recognize Mmap as Deref<Target = [u8]>
let data_bytes: Option<Box<dyn Deref<Target = [u8]> + Send>> = let data_bytes: Option<Box<dyn Deref<Target = [u8]> + Send>> =
if is_inline { if index.is_inline() {
None None
} else { } else {
let data_path = index_path.with_extension("d"); let data_path = index_path.with_extension("d");
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 { Ok(Revlog { index, data_bytes })
index_bytes,
data_bytes,
})
} }
/// 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(&self, node: &[u8]) -> Result<Revision, RevlogError> { pub fn get_node_rev(&self, node: &[u8]) -> Result<Revision, RevlogError> {
let index = self.index();
// This is brute force. But it is fast enough for now. // This is brute force. But it is fast enough for now.
// Optimization will come later. // Optimization will come later.
for rev in (0..self.len() as Revision).rev() { for rev in (0..self.len() as Revision).rev() {
let index_entry = let index_entry =
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);
} }
} }
Err(RevlogError::InvalidRevision) Err(RevlogError::InvalidRevision)
} }
/// Return the full data associated to a revision. /// Return the full data associated to a revision.
while let Some(base_rev) = entry.base_rev { while let Some(base_rev) = entry.base_rev {
delta_chain.push(entry); delta_chain.push(entry);
entry = self entry = self
.get_entry(base_rev) .get_entry(base_rev)
.map_err(|_| RevlogError::Corrupted)?; .map_err(|_| RevlogError::Corrupted)?;
} }
// TODO do not look twice in the index // TODO do not look twice in the index
let index = self.index(); let index_entry = self
let index_entry = .index
index.get_entry(rev).ok_or(RevlogError::InvalidRevision)?; .get_entry(rev)
.ok_or(RevlogError::InvalidRevision)?;
let data: Vec<u8> = if delta_chain.is_empty() { let data: Vec<u8> = if delta_chain.is_empty() {
entry.data()?.into() entry.data()?.into()
} else { } else {
Revlog::build_data_from_deltas(entry, &delta_chain)? Revlog::build_data_from_deltas(entry, &delta_chain)?
}; };
if self.check_hash( if self.check_hash(
/// Check the hash of some given data against the recorded hash. /// Check the hash of some given data against the recorded hash.
pub fn check_hash( pub fn check_hash(
&self, &self,
p1: Revision, p1: Revision,
p2: Revision, p2: Revision,
expected: &[u8], expected: &[u8],
data: &[u8], data: &[u8],
) -> bool { ) -> bool {
let index = self.index(); let e1 = self.index.get_entry(p1);
let e1 = index.get_entry(p1);
let h1 = match e1 { let h1 = match e1 {
Some(ref entry) => entry.hash(), Some(ref entry) => entry.hash(),
None => &NULL_NODE_ID, None => &NULL_NODE_ID,
}; };
let e2 = index.get_entry(p2); let e2 = self.index.get_entry(p2);
let h2 = match e2 { let h2 = match e2 {
Some(ref entry) => entry.hash(), Some(ref entry) => entry.hash(),
None => &NULL_NODE_ID, None => &NULL_NODE_ID,
}; };
hash(data, &h1, &h2).as_slice() == expected hash(data, &h1, &h2).as_slice() == expected
} }
.map(RevlogEntry::data) .map(RevlogEntry::data)
.collect::<Result<Vec<Cow<'_, [u8]>>, RevlogError>>()?; .collect::<Result<Vec<Cow<'_, [u8]>>, RevlogError>>()?;
let patches: Vec<_> = let patches: Vec<_> =
deltas.iter().map(|d| patch::PatchList::new(d)).collect(); deltas.iter().map(|d| patch::PatchList::new(d)).collect();
let patch = patch::fold_patch_lists(&patches); let patch = patch::fold_patch_lists(&patches);
Ok(patch.apply(&snapshot)) Ok(patch.apply(&snapshot))
} }
/// Return the revlog index.
pub fn index(&self) -> Index {
let is_inline = self.data_bytes.is_none();
Index::new(&self.index_bytes, is_inline)
}
/// Return the revlog data. /// Return the revlog data.
fn data(&self) -> &[u8] { fn data(&self) -> &[u8] {
match self.data_bytes { match self.data_bytes {
Some(ref data_bytes) => &data_bytes, Some(ref data_bytes) => &data_bytes,
None => &self.index_bytes, None => panic!(
"forgot to load the data or trying to access inline data"
),
} }
} }
/// Get an entry of the revlog. /// Get an entry of the revlog.
fn get_entry(&self, rev: Revision) -> Result<RevlogEntry, RevlogError> { fn get_entry(&self, rev: Revision) -> Result<RevlogEntry, RevlogError> {
let index = self.index(); let index_entry = self
let index_entry = .index
index.get_entry(rev).ok_or(RevlogError::InvalidRevision)?; .get_entry(rev)
.ok_or(RevlogError::InvalidRevision)?;
let start = index_entry.offset(); let start = index_entry.offset();
let end = start + index_entry.compressed_len(); let end = start + index_entry.compressed_len();
let data = if self.index.is_inline() {
self.index.data(start, end)
} else {
&self.data()[start..end]
};
let entry = RevlogEntry { let entry = RevlogEntry {
rev, rev,
bytes: &self.data()[start..end], bytes: data,
compressed_len: index_entry.compressed_len(), compressed_len: index_entry.compressed_len(),
uncompressed_len: index_entry.uncompressed_len(), uncompressed_len: index_entry.uncompressed_len(),
base_rev: if index_entry.base_revision() == rev { base_rev: if index_entry.base_revision() == rev {
None None
} else { } else {
Some(index_entry.base_revision()) Some(index_entry.base_revision())
}, },
}; };
/// Tell if the entry is a snapshot or a delta /// Tell if the entry is a snapshot or a delta
/// (influences on decompression). /// (influences on decompression).
fn is_delta(&self) -> bool { fn is_delta(&self) -> bool {
self.base_rev.is_some() self.base_rev.is_some()
} }
} }
/// Value of the inline flag.
pub fn is_inline(index_bytes: &[u8]) -> bool {
match &index_bytes[0..=1] {
[0, 0] | [0, 2] => false,
_ => true,
}
}
/// Format version of the revlog. /// Format version of the revlog.
pub fn get_version(index_bytes: &[u8]) -> u16 { pub fn get_version(index_bytes: &[u8]) -> u16 {
BigEndian::read_u16(&index_bytes[2..=3]) BigEndian::read_u16(&index_bytes[2..=3])
} }
/// Calculate the hash of a revision given its data and its parents. /// Calculate the hash of a revision given its data and its parents.
fn hash(data: &[u8], p1_hash: &[u8], p2_hash: &[u8]) -> Vec<u8> { fn hash(data: &[u8], p1_hash: &[u8], p2_hash: &[u8]) -> Vec<u8> {
let mut hasher = Sha1::new(); let mut hasher = Sha1::new();
} }
#[cfg(test)] #[cfg(test)]
mod tests { mod tests {
use super::*; use super::*;
use super::super::index::IndexEntryBuilder; use super::super::index::IndexEntryBuilder;
#[cfg(test)]
pub struct RevlogBuilder {
version: u16,
is_general_delta: bool,
is_inline: bool,
offset: usize,
index: Vec<Vec<u8>>,
data: Vec<Vec<u8>>,
}
#[cfg(test)]
impl RevlogBuilder {
pub fn new() -> Self {
Self {
version: 2,
is_inline: false,
is_general_delta: true,
offset: 0,
index: vec![],
data: vec![],
}
}
pub fn with_inline(&mut self, value: bool) -> &mut Self {
self.is_inline = value;
self
}
pub fn with_general_delta(&mut self, value: bool) -> &mut Self {
self.is_general_delta = value;
self
}
pub fn with_version(&mut self, value: u16) -> &mut Self {
self.version = value;
self
}
pub fn push(
&mut self,
mut index: IndexEntryBuilder,
data: Vec<u8>,
) -> &mut Self {
if self.index.is_empty() {
index.is_first(true);
index.with_general_delta(self.is_general_delta);
index.with_inline(self.is_inline);
index.with_version(self.version);
} else {
index.with_offset(self.offset);
}
self.index.push(index.build());
self.offset += data.len();
self.data.push(data);
self
}
pub fn build_inline(&self) -> Vec<u8> {
let mut bytes =
Vec::with_capacity(self.index.len() + self.data.len());
for (index, data) in self.index.iter().zip(self.data.iter()) {
bytes.extend(index);
bytes.extend(data);
}
bytes
}
}
#[test]
fn is_not_inline_when_no_inline_flag_test() {
let bytes = RevlogBuilder::new()
.with_general_delta(false)
.with_inline(false)
.push(IndexEntryBuilder::new(), vec![])
.build_inline();
assert_eq!(is_inline(&bytes), false)
}
#[test]
fn is_inline_when_inline_flag_test() {
let bytes = RevlogBuilder::new()
.with_general_delta(false)
.with_inline(true)
.push(IndexEntryBuilder::new(), vec![])
.build_inline();
assert_eq!(is_inline(&bytes), true)
}
#[test]
fn is_inline_when_inline_and_generaldelta_flags_test() {
let bytes = RevlogBuilder::new()
.with_general_delta(true)
.with_inline(true)
.push(IndexEntryBuilder::new(), vec![])
.build_inline();
assert_eq!(is_inline(&bytes), true)
}
#[test] #[test]
fn version_test() { fn version_test() {
let bytes = RevlogBuilder::new() let bytes = IndexEntryBuilder::new()
.is_first(true)
.with_version(1) .with_version(1)
.push(IndexEntryBuilder::new(), vec![]) .build();
.build_inline();
assert_eq!(get_version(&bytes), 1) assert_eq!(get_version(&bytes), 1)
} }
} }