This is an archive of the discontinued Mercurial Phabricator instance.

Differential D8097

rust-nodemap: accounting for dead blocks
ClosedPublic

Authored by marmoute on Feb 8 2020, 12:45 PM.

Details

Reviewers
kevincox
Group Reviewers
hg-reviewers
Commits
rHG6329ce04c69f: rust-nodemap: accounting for dead blocks
rHG706c1bd7f71c: rust-nodemap: accounting for dead blocks
Summary

By the very append-only nature of the NodeTree, inserting
new blocks has the effect of making some of the older ones
useless as they become unreachable.

Therefore some automatic housekeeping will need to be provided.
This is standard procedure in the word of databases, under names
such as "repack" or "vacuum".

The new masked_readonly_blocks() will provide callers with
useful information to decide if the nodetree is ripe for
repacking, but all the NodeTree can provide is how many
blocks have been masked in the currently mutable part. Analysing
the readonly part would be way too long to do it for each
transaction and defeat the whole purpose of nodemap persistence.
Serializing callers (from the Python layer) will get this figure
before each extraction and maintain an aggregate counter of
unreachable blocks separately.

Note: at this point, the most efficient repacking is just to restart
afresh with a full rescan.

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

marmoute created this revision.Feb 8 2020, 12:45 PM
Alphare updated this revision to Diff 20219.Feb 14 2020, 6:02 AM
Alphare updated this revision to Diff 20238.Feb 15 2020, 6:50 AM
Alphare updated this revision to Diff 20279.Feb 24 2020, 5:13 AM
kevincox accepted this revision.Feb 24 2020, 5:45 AM
Alphare updated this revision to Diff 20284.Feb 24 2020, 8:15 AM
gracinet added a commit: rHG706c1bd7f71c: rust-nodemap: accounting for dead blocks.Feb 26 2020, 10:33 AM
This revision was not accepted when it landed; it landed in state Needs Review.
Closed by commit rHG706c1bd7f71c: rust-nodemap: accounting for dead blocks (authored by gracinet). · Explain Why
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

PathPackages
Mrust/hg-core/src/revlog/nodemap.rs (31 lines)

Diff 20315

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

/// keep the original untouched and store new blocks separately. /// keep the original untouched and store new blocks separately.
/// ///
/// The mutable root `Block` is kept apart so that we don't have to rebump /// The mutable root `Block` is kept apart so that we don't have to rebump
/// it on each insertion. /// it on each insertion.
pub struct NodeTree { pub struct NodeTree {
readonly: Box<dyn Deref<Target = [Block]> + Send>, readonly: Box<dyn Deref<Target = [Block]> + Send>,
growable: Vec<Block>, growable: Vec<Block>,
root: Block, root: Block,
masked_inner_blocks: usize,
} }
impl Index<usize> for NodeTree { impl Index<usize> for NodeTree {
type Output = Block; type Output = Block;
fn index(&self, i: usize) -> &Block { fn index(&self, i: usize) -> &Block {
let ro_len = self.readonly.len(); let ro_len = self.readonly.len();
if i < ro_len { if i < ro_len {
let root = readonly let root = readonly
.last() .last()
.map(|b| b.clone()) .map(|b| b.clone())
.unwrap_or_else(|| Block::new()); .unwrap_or_else(|| Block::new());
NodeTree { NodeTree {
readonly: readonly, readonly: readonly,
growable: Vec::new(), growable: Vec::new(),
root: root, root: root,
masked_inner_blocks: 0,
} }
} }
/// Create from an opaque bunch of bytes /// Create from an opaque bunch of bytes
/// ///
/// The created `NodeTreeBytes` from `buffer`, /// The created `NodeTreeBytes` from `buffer`,
/// of which exactly `amount` bytes are used. /// of which exactly `amount` bytes are used.
/// ///
/// ///
/// Note: the caller wouldn't be allowed to query `self.growable.len()` /// Note: the caller wouldn't be allowed to query `self.growable.len()`
/// itself because of the mutable borrow taken with the returned `Block` /// itself because of the mutable borrow taken with the returned `Block`
fn mutable_block(&mut self, idx: usize) -> (usize, &mut Block, usize) { fn mutable_block(&mut self, idx: usize) -> (usize, &mut Block, usize) {
let ro_blocks = &self.readonly; let ro_blocks = &self.readonly;
let ro_len = ro_blocks.len(); let ro_len = ro_blocks.len();
let glen = self.growable.len(); let glen = self.growable.len();
if idx < ro_len { if idx < ro_len {
self.masked_inner_blocks += 1;
// TODO OPTIM I think this makes two copies // TODO OPTIM I think this makes two copies
self.growable.push(ro_blocks[idx].clone()); self.growable.push(ro_blocks[idx].clone());
(glen + ro_len, &mut self.growable[glen], glen + 1) (glen + ro_len, &mut self.growable[glen], glen + 1)
} else if glen + ro_len == idx { } else if glen + ro_len == idx {
(idx, &mut self.root, glen) (idx, &mut self.root, glen)
} else { } else {
(idx, &mut self.growable[idx - ro_len], glen) (idx, &mut self.growable[idx - ro_len], glen)
} }
if block.get(visited.nybble) == to_write { if block.get(visited.nybble) == to_write {
break; break;
} }
block.set(visited.nybble, to_write); block.set(visited.nybble, to_write);
block_idx = new_idx; block_idx = new_idx;
} }
Ok(()) Ok(())
} }
/// Return the number of blocks in the readonly part that are currently
/// masked in the mutable part.
///
/// The `NodeTree` structure has no efficient way to know how many blocks
/// are already unreachable in the readonly part.
pub fn masked_readonly_blocks(&self) -> usize {
if let Some(readonly_root) = self.readonly.last() {
if readonly_root == &self.root {
return 0;
}
} else {
return 0;
}
self.masked_inner_blocks + 1
}
} }
pub struct NodeTreeBytes { pub struct NodeTreeBytes {
buffer: Box<dyn Deref<Target = [u8]> + Send>, buffer: Box<dyn Deref<Target = [u8]> + Send>,
len_in_blocks: usize, len_in_blocks: usize,
} }
impl NodeTreeBytes { impl NodeTreeBytes {
pad_insert(&mut idx, 2, "cafe"); pad_insert(&mut idx, 2, "cafe");
pad_insert(&mut idx, 3, "15"); pad_insert(&mut idx, 3, "15");
pad_insert(&mut idx, 1, "10"); pad_insert(&mut idx, 1, "10");
let nt = NodeTree { let nt = NodeTree {
readonly: sample_nodetree().readonly, readonly: sample_nodetree().readonly,
growable: vec![block![0: Rev(1), 5: Rev(3)]], growable: vec![block![0: Rev(1), 5: Rev(3)]],
root: block![0: Block(1), 1:Block(3), 12: Rev(2)], root: block![0: Block(1), 1:Block(3), 12: Rev(2)],
masked_inner_blocks: 1,
}; };
assert_eq!(nt.find_hex(&idx, "10")?, Some(1)); assert_eq!(nt.find_hex(&idx, "10")?, Some(1));
assert_eq!(nt.find_hex(&idx, "c")?, Some(2)); assert_eq!(nt.find_hex(&idx, "c")?, Some(2));
assert_eq!(nt.unique_prefix_len_hex(&idx, "c")?, Some(1)); assert_eq!(nt.unique_prefix_len_hex(&idx, "c")?, Some(1));
assert_eq!(nt.find_hex(&idx, "00"), Err(MultipleResults)); assert_eq!(nt.find_hex(&idx, "00"), Err(MultipleResults));
assert_eq!(nt.find_hex(&idx, "000")?, Some(NULL_REVISION)); assert_eq!(nt.find_hex(&idx, "000")?, Some(NULL_REVISION));
assert_eq!(nt.unique_prefix_len_hex(&idx, "000")?, Some(3)); assert_eq!(nt.unique_prefix_len_hex(&idx, "000")?, Some(3));
assert_eq!(nt.find_hex(&idx, "01")?, Some(9)); assert_eq!(nt.find_hex(&idx, "01")?, Some(9));
assert_eq!(nt.masked_readonly_blocks(), 2);
Ok(()) Ok(())
} }
struct TestNtIndex { struct TestNtIndex {
index: TestIndex, index: TestIndex,
nt: NodeTree, nt: NodeTree,
} }
// now let's make it split and create more than one additional block // now let's make it split and create more than one additional block
idx.insert(3, "1a345")?; idx.insert(3, "1a345")?;
assert_eq!(idx.nt.growable.len(), 4); assert_eq!(idx.nt.growable.len(), 4);
assert_eq!(idx.find_hex("1a340")?, Some(1)); assert_eq!(idx.find_hex("1a340")?, Some(1));
assert_eq!(idx.find_hex("1a345")?, Some(3)); assert_eq!(idx.find_hex("1a345")?, Some(3));
assert_eq!(idx.find_hex("1a341")?, None); assert_eq!(idx.find_hex("1a341")?, None);
// there's no readonly block to mask
assert_eq!(idx.nt.masked_readonly_blocks(), 0);
Ok(()) Ok(())
} }
#[test] #[test]
fn test_unique_prefix_len_zero_prefix() { fn test_unique_prefix_len_zero_prefix() {
let mut idx = TestNtIndex::new(); let mut idx = TestNtIndex::new();
idx.insert(0, "00000abcd").unwrap(); idx.insert(0, "00000abcd").unwrap();
idx.insert(1, "1235")?; idx.insert(1, "1235")?;
idx.insert(2, "131")?; idx.insert(2, "131")?;
idx.insert(3, "cafe")?; idx.insert(3, "cafe")?;
let mut idx = idx.commit(); let mut idx = idx.commit();
assert_eq!(idx.find_hex("1234")?, Some(0)); assert_eq!(idx.find_hex("1234")?, Some(0));
assert_eq!(idx.find_hex("1235")?, Some(1)); assert_eq!(idx.find_hex("1235")?, Some(1));
assert_eq!(idx.find_hex("131")?, Some(2)); assert_eq!(idx.find_hex("131")?, Some(2));
assert_eq!(idx.find_hex("cafe")?, Some(3)); assert_eq!(idx.find_hex("cafe")?, Some(3));
// we did not add anything since init from readonly
assert_eq!(idx.nt.masked_readonly_blocks(), 0);
idx.insert(4, "123A")?; idx.insert(4, "123A")?;
assert_eq!(idx.find_hex("1234")?, Some(0)); assert_eq!(idx.find_hex("1234")?, Some(0));
assert_eq!(idx.find_hex("1235")?, Some(1)); assert_eq!(idx.find_hex("1235")?, Some(1));
assert_eq!(idx.find_hex("131")?, Some(2)); assert_eq!(idx.find_hex("131")?, Some(2));
assert_eq!(idx.find_hex("cafe")?, Some(3)); assert_eq!(idx.find_hex("cafe")?, Some(3));
assert_eq!(idx.find_hex("123A")?, Some(4)); assert_eq!(idx.find_hex("123A")?, Some(4));
// we masked blocks for all prefixes of "123", including the root
assert_eq!(idx.nt.masked_readonly_blocks(), 4);
eprintln!("{:?}", idx.nt);
idx.insert(5, "c0")?; idx.insert(5, "c0")?;
assert_eq!(idx.find_hex("cafe")?, Some(3)); assert_eq!(idx.find_hex("cafe")?, Some(3));
assert_eq!(idx.find_hex("c0")?, Some(5)); assert_eq!(idx.find_hex("c0")?, Some(5));
assert_eq!(idx.find_hex("c1")?, None); assert_eq!(idx.find_hex("c1")?, None);
assert_eq!(idx.find_hex("1234")?, Some(0)); assert_eq!(idx.find_hex("1234")?, Some(0));
// inserting "c0" is just splitting the 'c' slot of the mutable root,
// it doesn't mask anything
assert_eq!(idx.nt.masked_readonly_blocks(), 4);
Ok(()) Ok(())
} }
#[test] #[test]
fn test_into_added_empty() { fn test_into_added_empty() {
assert!(sample_nodetree().into_readonly_and_added().1.is_empty()); assert!(sample_nodetree().into_readonly_and_added().1.is_empty());
assert!(sample_nodetree() assert!(sample_nodetree()