This is an archive of the discontinued Mercurial Phabricator instance.

Differential D11882

rhg: fix a crash on non-generaldelta revlogs
ClosedPublic

Authored by aalekseyev on Dec 7 2021, 1:58 PM.

Details

Reviewers
Alphare
Group Reviewers
hg-reviewers
Commits
rHG96ea4db4741b: rhg: fix a crash on non-generaldelta revlogs

Diff Detail

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

Event Timeline

aalekseyev created this revision.Dec 7 2021, 1:58 PM
aalekseyev updated this revision to Diff 31367.Dec 7 2021, 2:04 PM
aalekseyev updated this revision to Diff 31368.Dec 7 2021, 2:06 PM
aalekseyev updated this revision to Diff 31391.Dec 8 2021, 6:25 AM
aalekseyev updated this revision to Diff 31393.Dec 8 2021, 6:40 AM
aalekseyev updated this revision to Diff 31395.Dec 8 2021, 7:36 AM
aalekseyev updated this revision to Diff 31397.Dec 8 2021, 12:27 PM
Alphare requested changes to this revision.Dec 10 2021, 6:04 AM
Alphare added a subscriber: Alphare.

Looks good aside from the docstrings needing to be docstrings or absorbed

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

These changes should be absorbed into the previous changeset

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

This comment should have three leading slashes ///

This revision now requires changes to proceed.Dec 10 2021, 6:04 AM
aalekseyev updated this revision to Diff 31405.Dec 10 2021, 6:10 AM
aalekseyev updated this revision to Diff 31412.Dec 10 2021, 6:50 AM
aalekseyev added a comment.Dec 10 2021, 6:52 AM

While working on comments I discovered that the rust implementation was different from the C/Python implementation in how it deals with a wrong value of delta chain base.
I made sure that rust code behaves the same as hg there (which is: ignore the corruption) and added a test that checks that.

aalekseyev updated this revision to Diff 31413.Dec 10 2021, 6:55 AM
Alphare requested changes to this revision.Dec 10 2021, 8:21 AM

I was about to come back to this and talk about the same bug you found. So all good, thanks for spotting it!

The last test is a bit fragile, we should gate it for revlog-v1 only.

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

Might as well address this at the same time

This revision now requires changes to proceed.Dec 10 2021, 8:21 AM
aalekseyev added a comment.Dec 10 2021, 8:39 AM
In D11882#182409, @Alphare wrote:

...
The last test is a bit fragile, we should gate it for revlog-v1 only.

Do you have a specific mechanism in mind? (which "require" to use)

Alphare accepted this revision.Dec 10 2021, 8:51 AM

I thought we had a revlog-v2 in hghave but we don't. Don't worry about it then, we'll come to it when we come back around to revlog-v2 work. I'll amend the docstring.

This revision is now accepted and ready to land.Dec 10 2021, 8:51 AM
aalekseyev updated this revision to Diff 31414.Dec 10 2021, 8:59 AM
aalekseyev added a comment.Dec 10 2021, 9:05 AM

I don't know about revlog-v1 (it seems there are tests in the tree that are revlog-v1-specific and don't gate against it), but (the lack of) zstd compression is also changing the result, so clearly needs to be guarded against, since it's breaking the --pure build.
I pushed that change. If you have ideas how to make the test less fragile, those would be appreciated. One possibility is to remove the test of corrupted repo altogether, if you think that's better.

Alphare requested changes to this revision.Dec 10 2021, 10:22 AM

I tried to test the series before your last update and it was well in the red (https://foss.heptapod.net/mercurial/mercurial-devel/-/pipelines/30072), and it looks like it's not limited to pure builds. Please test your series through the CI next time.

In D11882#182421, @aalekseyev wrote:

I don't know about revlog-v1 (it seems there are tests in the tree that are revlog-v1-specific and don't gate against it), but (the lack of) zstd compression is also changing the result, so clearly needs to be guarded against, since it's breaking the --pure build.
I pushed that change. If you have ideas how to make the test less fragile, those would be appreciated. One possibility is to remove the test of corrupted repo altogether, if you think that's better.

I think we can forgo that test, it's more trouble than it's worth.

This revision now requires changes to proceed.Dec 10 2021, 10:22 AM
aalekseyev added a comment.Dec 10 2021, 11:06 AM

The shell strikes again. :-\
I removed the problematic test, so it should be good now.

I tested the series through a CI as originally submitted, but of course new issues were introduced while it was in review.
Sorry, I need to develop some workflow that allows me to push both to phabricator and to a repo with a CI. Currently I can only do one or the other.

Alphare added a comment.Dec 10 2021, 11:59 AM
In D11882#182449, @aalekseyev wrote:

I tested the series through a CI as originally submitted, but of course new issues were introduced while it was in review.
Sorry, I need to develop some workflow that allows me to push both to phabricator and to a repo with a CI. Currently I can only do one or the other.

Heptapod's CI will re-send revisions with a differential revision attached to them on pipeline success. Unfortunately, the Windows CI is *very* flaky as of now, which is something we're trying to tackle at the moment.

Believe me, no one is more aggravated than me by the current submission/review workflow.
I'll take a look at your patches later, thank you for re-sending fast.

aalekseyev updated this revision to Diff 31426.Dec 10 2021, 2:09 PM
Alphare added a comment.Dec 13 2021, 6:38 AM

I'm not sure I understand the point of the hashing done at the very end of the tests: this even causes an issue for Windows for no real reason (rhg doesn't work on Windows yet, but still). Couldn't we just output the file?

aalekseyev updated this revision to Diff 31450.Dec 13 2021, 8:42 AM
aalekseyev added a comment.Dec 13 2021, 8:45 AM

The point is to make the output smaller.
Seems ok to output the whole file, too (pushed). (it was 50 lines, not 20, when I introduced it)

Alphare accepted this revision.Dec 13 2021, 8:45 AM

Thanks!

This revision is now accepted and ready to land.Dec 13 2021, 8:45 AM
aalekseyev added a commit: rHG96ea4db4741b: rhg: fix a crash on non-generaldelta revlogs.Dec 13 2021, 8:51 AM
Closed by commit rHG96ea4db4741b: rhg: fix a crash on non-generaldelta revlogs (authored by aalekseyev). · Explain Why
This revision was automatically updated to reflect the committed changes.
aalekseyev added a comment.Dec 13 2021, 11:23 AM

Thanks for your review!

Revision Contents
Changeset List

Diff 31391

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

header_bytes: [u8; 4], header_bytes: [u8; 4],
} }
#[derive(Copy, Clone)] #[derive(Copy, Clone)]
pub struct IndexHeaderFlags { pub struct IndexHeaderFlags {
flags: u16, flags: u16,
} }
// Corresponds to the high bits of `_format_flags` in python /// Corresponds to the high bits of `_format_flags` in python
AlphareUnsubmitted
Not Done

These changes should be absorbed into the previous changeset

Alphare: These changes should be absorbed into the previous changeset
impl IndexHeaderFlags { impl IndexHeaderFlags {
// Corresponds to FLAG_INLINE_DATA in python /// Corresponds to FLAG_INLINE_DATA in python
pub fn is_inline(self) -> bool { pub fn is_inline(self) -> bool {
return self.flags & 1 != 0; return self.flags & 1 != 0;
} }
// Corresponds to FLAG_GENERALDELTA in python /// Corresponds to FLAG_GENERALDELTA in python
pub fn uses_generaldelta(self) -> bool { pub fn uses_generaldelta(self) -> bool {
return self.flags & 2 != 0; return self.flags & 2 != 0;
} }
} }
// Corresponds to the INDEX_HEADER structure, /// Corresponds to the INDEX_HEADER structure,
// which is parsed as a `header` variable in `_loadindex` in `revlog.py` /// which is parsed as a `header` variable in `_loadindex` in `revlog.py`
impl IndexHeader { impl IndexHeader {
fn format_flags(&self) -> IndexHeaderFlags { fn format_flags(&self) -> IndexHeaderFlags {
// No "unknown flags" check here, unlike in python. Maybe there should // No "unknown flags" check here, unlike in python. Maybe there should
// be. // be.
return IndexHeaderFlags { return IndexHeaderFlags {
flags: BigEndian::read_u16(&self.header_bytes[0..2]), flags: BigEndian::read_u16(&self.header_bytes[0..2]),
}; };
} }
} }
/// A Revlog index /// A Revlog index
pub struct Index { pub struct Index {
bytes: Box<dyn Deref<Target = [u8]> + Send>, bytes: Box<dyn Deref<Target = [u8]> + Send>,
/// 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>>,
uses_generaldelta: bool,
} }
impl Index { 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( pub fn new(
bytes: Box<dyn Deref<Target = [u8]> + Send>, bytes: Box<dyn Deref<Target = [u8]> + Send>,
) -> Result<Self, HgError> { ) -> Result<Self, HgError> {
let header = IndexHeader::parse(bytes.as_ref())?; let header = IndexHeader::parse(bytes.as_ref())?;
if header.format_version() != IndexHeader::REVLOGV1 { if header.format_version() != IndexHeader::REVLOGV1 {
// A proper new version should have had a repo/store // A proper new version should have had a repo/store
// requirement. // requirement.
return Err(HgError::corrupted("unsupported revlog version")); return Err(HgError::corrupted("unsupported revlog version"));
} }
// This is only correct because we know version is REVLOGV1.
// In v2 we always use generaldelta, while in v0 we never use
// generaldelta. Similar for [is_inline] (it's only used in v1).
let uses_generaldelta = header.format_flags().uses_generaldelta();
if header.format_flags().is_inline() { if header.format_flags().is_inline() {
let mut offset: usize = 0; let mut offset: usize = 0;
let mut offsets = Vec::new(); let mut offsets = Vec::new();
while offset + INDEX_ENTRY_SIZE <= bytes.len() { while offset + INDEX_ENTRY_SIZE <= 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],
offset_override: None, offset_override: None,
}; };
offset += INDEX_ENTRY_SIZE + entry.compressed_len(); offset += INDEX_ENTRY_SIZE + entry.compressed_len();
} }
if offset == bytes.len() { if offset == bytes.len() {
Ok(Self { Ok(Self {
bytes, bytes,
offsets: Some(offsets), offsets: Some(offsets),
uses_generaldelta,
}) })
} else { } else {
Err(HgError::corrupted("unexpected inline revlog length") Err(HgError::corrupted("unexpected inline revlog length")
.into()) .into())
} }
} else { } else {
Ok(Self { Ok(Self {
bytes, bytes,
offsets: None, offsets: None,
uses_generaldelta,
}) })
} }
} }
pub fn uses_generaldelta(&self) -> bool {
self.uses_generaldelta
}
/// Value of the inline flag. /// Value of the inline flag.
pub fn is_inline(&self) -> bool { pub fn is_inline(&self) -> bool {
self.offsets.is_some() self.offsets.is_some()
} }
/// Return a slice of bytes if `revlog` is inline. Panic if not. /// Return a slice of bytes if `revlog` is inline. Panic if not.
pub fn data(&self, start: usize, end: usize) -> &[u8] { pub fn data(&self, start: usize, end: usize) -> &[u8] {
if !self.is_inline() { if !self.is_inline() {
} }
/// Return the uncompressed length of the data. /// Return the uncompressed length of the data.
pub fn uncompressed_len(&self) -> usize { pub fn uncompressed_len(&self) -> usize {
BigEndian::read_u32(&self.bytes[12..=15]) as usize BigEndian::read_u32(&self.bytes[12..=15]) as usize
} }
/// Return the revision upon which the data has been derived. /// Return the revision upon which the data has been derived.
pub fn base_revision(&self) -> Revision { pub fn base_revision_or_base_of_delta_chain(&self) -> Revision {
// TODO Maybe return an Option when base_revision == rev? // TODO Maybe return an Option when base_revision == rev?
// Requires to add rev to IndexEntry // Requires to add rev to IndexEntry
BigEndian::read_i32(&self.bytes[16..]) BigEndian::read_i32(&self.bytes[16..])
} }
pub fn p1(&self) -> Revision { pub fn p1(&self) -> Revision {
BigEndian::read_i32(&self.bytes[24..]) BigEndian::read_i32(&self.bytes[24..])
pub struct IndexEntryBuilder { pub struct IndexEntryBuilder {
is_first: bool, is_first: bool,
is_inline: bool, is_inline: bool,
is_general_delta: bool, is_general_delta: bool,
version: u16, version: u16,
offset: usize, offset: usize,
compressed_len: usize, compressed_len: usize,
uncompressed_len: usize, uncompressed_len: usize,
base_revision: Revision, base_revision_or_base_of_delta_chain: Revision,
} }
#[cfg(test)] #[cfg(test)]
impl IndexEntryBuilder { impl IndexEntryBuilder {
pub fn new() -> Self { pub fn new() -> Self {
Self { Self {
is_first: false, is_first: false,
is_inline: false, is_inline: false,
is_general_delta: true, is_general_delta: true,
version: 2, version: 2,
offset: 0, offset: 0,
compressed_len: 0, compressed_len: 0,
uncompressed_len: 0, uncompressed_len: 0,
base_revision: 0, base_revision_or_base_of_delta_chain: 0,
} }
} }
pub fn is_first(&mut self, value: bool) -> &mut Self { pub fn is_first(&mut self, value: bool) -> &mut Self {
self.is_first = value; self.is_first = value;
self self
} }
self self
} }
pub fn with_uncompressed_len(&mut self, value: usize) -> &mut Self { pub fn with_uncompressed_len(&mut self, value: usize) -> &mut Self {
self.uncompressed_len = value; self.uncompressed_len = value;
self self
} }
pub fn with_base_revision(&mut self, value: Revision) -> &mut Self { pub fn with_base_revision_or_base_of_delta_chain(
self.base_revision = value; &mut self,
value: Revision,
) -> &mut Self {
self.base_revision_or_base_of_delta_chain = value;
self self
} }
pub fn build(&self) -> Vec<u8> { pub fn build(&self) -> Vec<u8> {
let mut bytes = Vec::with_capacity(INDEX_ENTRY_SIZE); let mut bytes = Vec::with_capacity(INDEX_ENTRY_SIZE);
if self.is_first { if self.is_first {
bytes.extend(&match (self.is_general_delta, self.is_inline) { bytes.extend(&match (self.is_general_delta, self.is_inline) {
(false, false) => [0u8, 0], (false, false) => [0u8, 0],
(false, true) => [0u8, 1], (false, true) => [0u8, 1],
(true, false) => [0u8, 2], (true, false) => [0u8, 2],
(true, true) => [0u8, 3], (true, true) => [0u8, 3],
}); });
bytes.extend(&self.version.to_be_bytes()); bytes.extend(&self.version.to_be_bytes());
// Remaining offset bytes. // Remaining offset bytes.
bytes.extend(&[0u8; 2]); bytes.extend(&[0u8; 2]);
} else { } else {
// Offset stored on 48 bits (6 bytes) // Offset stored on 48 bits (6 bytes)
bytes.extend(&(self.offset as u64).to_be_bytes()[2..]); bytes.extend(&(self.offset as u64).to_be_bytes()[2..]);
} }
bytes.extend(&[0u8; 2]); // Revision flags. bytes.extend(&[0u8; 2]); // Revision flags.
bytes.extend(&(self.compressed_len as u32).to_be_bytes()); bytes.extend(&(self.compressed_len as u32).to_be_bytes());
bytes.extend(&(self.uncompressed_len as u32).to_be_bytes()); bytes.extend(&(self.uncompressed_len as u32).to_be_bytes());
bytes.extend(&self.base_revision.to_be_bytes()); bytes.extend(
&self.base_revision_or_base_of_delta_chain.to_be_bytes(),
);
bytes bytes
} }
} }
#[test] #[test]
fn is_not_inline_when_no_inline_flag_test() { fn is_not_inline_when_no_inline_flag_test() {
let bytes = IndexEntryBuilder::new() let bytes = IndexEntryBuilder::new()
.is_first(true) .is_first(true)
bytes: &bytes, bytes: &bytes,
offset_override: None, offset_override: None,
}; };
assert_eq!(entry.uncompressed_len(), 1) assert_eq!(entry.uncompressed_len(), 1)
} }
#[test] #[test]
fn test_base_revision() { fn test_base_revision_or_base_of_delta_chain() {
let bytes = IndexEntryBuilder::new().with_base_revision(1).build(); let bytes = IndexEntryBuilder::new()
.with_base_revision_or_base_of_delta_chain(1)
.build();
let entry = IndexEntry { let entry = IndexEntry {
bytes: &bytes, bytes: &bytes,
offset_override: None, offset_override: None,
}; };
assert_eq!(entry.base_revision(), 1) assert_eq!(entry.base_revision_or_base_of_delta_chain(), 1)
} }
} }
#[cfg(test)] #[cfg(test)]
pub use tests::IndexEntryBuilder; pub use tests::IndexEntryBuilder;

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

#[timed] #[timed]
pub fn get_rev_data(&self, rev: Revision) -> Result<Vec<u8>, RevlogError> { pub fn get_rev_data(&self, rev: Revision) -> Result<Vec<u8>, RevlogError> {
if rev == NULL_REVISION { if rev == NULL_REVISION {
return Ok(vec![]); return Ok(vec![]);
}; };
// Todo return -> Cow // Todo return -> Cow
let mut entry = self.get_entry(rev)?; let mut entry = self.get_entry(rev)?;
let mut delta_chain = vec![]; let mut delta_chain = vec![];
while let Some(base_rev) = entry.base_rev {
if self.index.uses_generaldelta() {
while let Some(base_rev) = entry.base_rev_or_base_of_delta_chain {
delta_chain.push(entry); delta_chain.push(entry);
entry = self entry = self.get_entry_internal(base_rev)?;
.get_entry(base_rev) }
.map_err(|_| RevlogError::corrupted())?; } else {
if let Some(base_rev) = entry.base_rev_or_base_of_delta_chain {
delta_chain.push(entry);
entry = self.get_entry_internal(base_rev)?;
for rev in (base_rev + 1..rev).rev() {
delta_chain.push(self.get_entry_internal(rev)?);
}
}
} }
// TODO do not look twice in the index // TODO do not look twice in the index
let index_entry = self let index_entry = self
.index .index
.get_entry(rev) .get_entry(rev)
.ok_or(RevlogError::InvalidRevision)?; .ok_or(RevlogError::InvalidRevision)?;
} else { } else {
&self.data()[start..end] &self.data()[start..end]
}; };
let entry = RevlogEntry { let entry = RevlogEntry {
rev, rev,
bytes: data, 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_or_base_of_delta_chain: if index_entry
.base_revision_or_base_of_delta_chain()
== rev
{
None None
} else { } else {
Some(index_entry.base_revision()) Some(index_entry.base_revision_or_base_of_delta_chain())
}, },
}; };
Ok(entry) Ok(entry)
} }
// when resolving internal references within revlog, any errors
AlphareUnsubmitted
Not Done

This comment should have three leading slashes ///

Alphare: This comment should have three leading slashes `///`
AlphareUnsubmitted
Not Done

Might as well address this at the same time

Alphare: Might as well address this at the same time
// should be reported as corruption, instead of e.g. "invalid revision"
fn get_entry_internal(
&self,
rev: Revision,
) -> Result<RevlogEntry, RevlogError> {
return self.get_entry(rev).map_err(|_| RevlogError::corrupted());
}
} }
/// The revlog entry's bytes and the necessary informations to extract /// The revlog entry's bytes and the necessary informations to extract
/// the entry's data. /// the entry's data.
#[derive(Debug)] #[derive(Debug)]
pub struct RevlogEntry<'a> { pub struct RevlogEntry<'a> {
rev: Revision, rev: Revision,
bytes: &'a [u8], bytes: &'a [u8],
compressed_len: usize, compressed_len: usize,
uncompressed_len: usize, uncompressed_len: usize,
base_rev: Option<Revision>, base_rev_or_base_of_delta_chain: Option<Revision>,
} }
impl<'a> RevlogEntry<'a> { impl<'a> RevlogEntry<'a> {
pub fn revision(&self) -> Revision { pub fn revision(&self) -> Revision {
self.rev self.rev
} }
/// Extract the data contained in the entry. /// Extract the data contained in the entry.
Ok(buf) Ok(buf)
} }
} }
} }
/// 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_or_base_of_delta_chain.is_some()
} }
} }
/// 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( fn hash(
data: &[u8], data: &[u8],
p1_hash: &[u8], p1_hash: &[u8],
p2_hash: &[u8], p2_hash: &[u8],

tests/test-rhg-no-generaldelta.t

$ (seq.py 50; echo x) | (read; cat) > f $ (seq.py 50; echo x) | (read; cat) > f
$ hg commit -q -Am y $ hg commit -q -Am y
$ hg debugdeltachain f $ hg debugdeltachain f
rev chain# chainlen prev delta size rawsize chainsize ratio lindist extradist extraratio rev chain# chainlen prev delta size rawsize chainsize ratio lindist extradist extraratio
0 1 1 -1 base 79 141 79 0.56028 79 0 0.00000 0 1 1 -1 base 79 141 79 0.56028 79 0 0.00000
1 1 2 0 prev 14 143 93 0.65035 93 0 0.00000 1 1 2 0 prev 14 143 93 0.65035 93 0 0.00000
2 1 3 1 prev 12 141 105 0.74468 105 0 0.00000 2 1 3 1 prev 12 141 105 0.74468 105 0 0.00000
rhg breaks on non-generaldelta revlogs: rhg works on non-generaldelta revlogs:
$ $NO_FALLBACK hg cat f -r . | f --sha256 --size $ $NO_FALLBACK hg cat f -r . | f --sha256 --size
abort: corrupted revlog (rhg !) size=141, sha256=1a7fe778e33d64d5e14a9a126b77038b328356e67bacf308797bc0e39bf204f3
size=0, sha256=e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855 (rhg !)
size=141, sha256=1a7fe778e33d64d5e14a9a126b77038b328356e67bacf308797bc0e39bf204f3 (no-rhg !)