This is an archive of the discontinued Mercurial Phabricator instance.

Differential D1469

nodemap: implement nodemap in rust
ClosedPublic

Authored by quark on Nov 20 2017, 7:11 PM.
Tags
None
Subscribers
durham

Details

Reviewers
durham
Group Reviewers
Restricted Project
Commits
rFBHGX5cb0d9198ff9: nodemap: implement nodemap in rust
Summary

A simple nodemap index (node -> rev, and prefix -> node). See comment in
the code for the actual format.

Note this does not cover every features of a Mecurial nodemap. For example,
it does not have __setitem__, __delitem__, and does not treat rev -1
specially. Those could be implemented in a higher level.

Diff Detail

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

Event Timeline

quark created this revision.Nov 20 2017, 7:11 PM
Herald added a reviewer: Restricted Project. · View Herald TranscriptNov 20 2017, 7:11 PM
quark edited the summary of this revision. (Show Details)Nov 22 2017, 9:31 PM
quark updated this revision to Diff 3792.
quark updated this revision to Diff 3795.Nov 22 2017, 9:42 PM
durham requested changes to this revision.Nov 30 2017, 7:41 PM
durham added a subscriber: durham.

Mostly questions.

rust/indexes/src/nodemap.rs
41

Maybe mention that the side index is in-memory only. It says it in the diagram above, but not here.

70

So this code doesn't currently support inlined revlogs? Are are we just relying on the caller to turn an inlined revlog into a inmemory non-inlined [u8]? If it's just not supported anywhere, we should make that restriction obvious somewhere.

Also, s/NodeMap/NodeRevMap/ ?

81

from_le here?

118

Why 'cloned()' here?

136

Might be worth making the root node position a constant, instead of having magic '1' variables all over. Same for 0 for the side index root.

147

from_le, in line 156 too

167

Probably use a constant for the revlog entry width

172

I wonder if it's worth it to start putting these revlog accessor functions in their own file. To start building our revlog handling rust code for reuse outside of individual cases like this. Maybe by defining a RevlogIndex type as just a [u8] for now and putting a bunch of these function on it?

175

What does "forked" mean in this case?

196

more magic numbers

201

noob question: I thought this would return a reference to the slice of the buffer. But the lifetime isn't tied to the buffer, so that doesn't seem right. What am I missing?

215

Should the return None one be a panic or something? Since it should never happen right?

This revision now requires changes to proceed.Nov 30 2017, 7:41 PM
quark added inline comments.Nov 30 2017, 8:04 PM
rust/indexes/src/nodemap.rs
70

clindex does the inline check. It falls back to the old index if the revlog is inlined.

In theory we can convert inline revlog to non-inlined on the fly but I think it's cleaner to just skip supporting them.

81

Will do a scan for the entire series switching to be (for catching errors) and use from correctly.

118

The Rust iter() by default return references (&u8) for its elements. .cloned() converts those references to actual values (u8). It does not clone the iterator. It's like:

.map(|&x| x)
136

Good point.

172

A later patch does that. But the code here is in theory somehow "de-coupled" from the actual revlog format. i.e. other append-only format should also work.

175

Since main_index is read-only. It's copied to a Vec and then modifications are done to it. Maybe "copied on write".

201

The lifetime is implicitly tied. It's equivalent to:

fn rev_to_node<'a, K: AsRef<[u8]>>(changelog: &'a K, rev: KeyId) -> rerrors::Result<&'a [u8]>

The compiler knows that because there is only one reference type (changelog) in input arguments. If there are many, the compiler will complain.

215

IIRC, the Python code might feed all kinds of strange things like a revset string to paritalmatch. So it's also nicer to support that.

I checked the revlog.c behavior, it returns None for partialmatch('xxxx'). I also think it makes sense to return None (no match).

durham added inline comments.Dec 1 2017, 12:03 PM
rust/indexes/src/nodemap.rs
175

Hmm, just seems odd to mention that in the function description, since the function doesn't care if it's a fork or not. It just puts new entries in the index it was given.

201

So it will associate any return reference with whichever argument is a reference? That doesn't seem safe. Or is only because this slice is a slice of the changelog as_ref that it knows its related to the changelog?

quark added inline comments.Dec 1 2017, 1:29 PM
rust/indexes/src/nodemap.rs
175

This is O(len(index)) time complexity in theory, although memcpy without parsing is relatively fast. But there are no other places with that time complexity so I'd like to label that.

Shall we have more advanced ways to deal with filesystem confidently, that time complexity can be reduced.

201

It does both. First, desugar the code to the explicit lifetime version. Then run the borrow checker which knows the returned slice comes from changelog.

quark marked 4 inline comments as done.Dec 8 2017, 9:32 PM
quark updated this revision to Diff 4283.
quark added inline comments.Dec 8 2017, 9:54 PM
rust/indexes/src/nodemap.rs
175

I made a mistake. I thought the comment was at build_incrementally. Will change.

quark updated this revision to Diff 4369.Dec 11 2017, 7:20 PM
durham accepted this revision.Dec 14 2017, 7:21 PM
durham added inline comments.
rust/indexes/src/nodemap.rs
222

s/64/CHANGELOG_ENTRY_SIZE/

This revision is now accepted and ready to land.Dec 14 2017, 7:21 PM
quark updated this revision to Diff 4451.Dec 14 2017, 9:21 PM
quark updated this revision to Diff 4460.Dec 14 2017, 10:15 PM
Closed by commit rFBHGX5cb0d9198ff9: nodemap: implement nodemap in rust (authored by quark). · Explain WhyDec 15 2017, 2:35 PM
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

Diff 4509

rust/indexes/Cargo.toml

  • This file was added.
[package]
name = "indexes"
version = "0.1.0"
[profile.release]
lto = true
[lib]
name = "indexes"
crate-type = ["cdylib"]
[dependencies]
radixbuf = { path = "../radixbuf" }
error-chain = "0.11"

rust/indexes/src/errors.rs

  • This file was added.
// Copyright 2017 Facebook, Inc.
//
// This software may be used and distributed according to the terms of the
// GNU General Public License version 2 or any later version.
error_chain! {
foreign_links {
Radix(::radixbuf::errors::Error);
}
errors {
IndexCorrupted {
description("corrupted index")
}
}
}

rust/indexes/src/lib.rs

  • This file was added.
// Copyright 2017 Facebook, Inc.
//
// This software may be used and distributed according to the terms of the
// GNU General Public License version 2 or any later version.
#[macro_use]
extern crate error_chain;
extern crate radixbuf;
pub mod errors;
pub mod nodemap;

rust/indexes/src/nodemap.rs

  • This file was added.
// Copyright 2017 Facebook, Inc.
//
// This software may be used and distributed according to the terms of the
// GNU General Public License version 2 or any later version.
use std::u32;
use errors::{Result, ResultExt, ErrorKind};
use radixbuf::radix::{radix_lookup, radix_prefix_lookup, radix_lookup_unchecked, radix_insert,
RADIX_NCHILDREN};
use radixbuf::key::KeyId;
use radixbuf::errors as rerrors;
/// An index for node to rev lookups.
///
/// The index depends entirely on an append-only changelog.i source
/// of truth. It does not support in-memory overrides, which could be
/// implemented at a higher level.
///
/// ```text
///
/// changelogi
/// +------------+
/// | ... | node | < rev 0 \
/// +------------+ |
/// | ... | node | < rev 1 |> included in the main (on-disk) index
/// +------------+ |
/// | .......... | ... /
/// +------------+
/// | ... | node | < next_index_rev \
/// +------------+ |
/// | ... | node | < next_index_rev + 1 | will be built on-demand
/// +------------+ |> in the side (in-memory)
/// | .......... | ... | index
/// +------------+ |
/// | ... | node | < next_changelog_rev - 1 /
/// +------------+
/// < next_changelog_rev
/// ```
///
/// The main index is an immutable, periodically-rebuilt, on-disk radix buffer
/// with an extra metadata about what's the next revision unknown to the index.
durhamUnsubmitted
Done

Maybe mention that the side index is in-memory only. It says it in the diagram above, but not here.

durham: Maybe mention that the side index is in-memory only. It says it in the diagram above, but not…
/// The side index covers remaining revisions in changelogi, built on-demand and
/// is in-memory only. The side index is usually much smaller than the main index
/// so it can be built quickly.
///
/// ```
/// main index side index
/// +---------------------+ +----------------------+
/// | next_index_rev: u32 | | (small radix buffer) |
/// +---------------------+ +----------------------+
/// | | (in-memory only)
/// |(large radix buffer) |
/// | |
/// +---------------------+
/// (backed by filesystem)
/// ```
///
/// Having the side index allows us to make the main index immutable for most
/// of the time even if the source of truth has changed. It's possible to update
/// the main index in-place. But that requires extra efforts to deal with possible
/// filesystem issues like locking, or unexpected poweroff.
pub struct NodeRevMap<C, I> {
changelogi: C,
main_index: I, // Immutable main index
side_index: Vec<u32>, // Mutable side index
}
// Offsets in the main radix and key buffers
const RADIX_NEXT_REV_OFFSET: usize = 0;
const RADIX_HEADER_LEN: usize = RADIX_NEXT_REV_OFFSET + 1;
durhamUnsubmitted
Not Done

So this code doesn't currently support inlined revlogs? Are are we just relying on the caller to turn an inlined revlog into a inmemory non-inlined [u8]? If it's just not supported anywhere, we should make that restriction obvious somewhere.

Also, s/NodeMap/NodeRevMap/ ?

durham: So this code doesn't currently support inlined revlogs? Are are we just relying on the caller…
quarkAuthorUnsubmitted
Not Done

clindex does the inline check. It falls back to the old index if the revlog is inlined.

In theory we can convert inline revlog to non-inlined on the fly but I think it's cleaner to just skip supporting them.

quark: clindex does the inline check. It falls back to the old index if the revlog is inlined. In…
// Offsets of root nodes in radix buffers
const MAIN_RADIX_OFFSET: u32 = 1;
const SIDE_RADIX_OFFSET: u32 = 0;
const CHANGELOG_ENTRY_SIZE: u64 = 64;
impl<C: AsRef<[u8]>, I: AsRef<[u32]>> NodeRevMap<C, I>
{
/// Initialize NodeMap from a non-inlined version of changelog.i and an incomplete index.
pub fn new(changelogi: C, main_index: I) -> Result<Self> {
durhamUnsubmitted
Done

from_le here?

durham: `from_le` here?
quarkAuthorUnsubmitted
Done

Will do a scan for the entire series switching to be (for catching errors) and use from correctly.

quark: Will do a scan for the entire series switching to `be` (for catching errors) and use `from`…
// Sanity check if the index is corrupted or not.
// The index must contain at least 17 elements. index[0] tracks the last rev the index has.
// index[1..17] is the root radix node.
if main_index.as_ref().len() < RADIX_HEADER_LEN + RADIX_NCHILDREN {
bail!(ErrorKind::IndexCorrupted);
}
// Check if the index is behind and build incrementally
let next_rev = u32::from_be(main_index.as_ref()[RADIX_NEXT_REV_OFFSET]);
let end_rev = changelog_end_rev(&changelogi);
if next_rev > end_rev {
// next_rev cannot be larger than what changelogi has.
bail!(ErrorKind::IndexCorrupted);
} else if next_rev > 0 {
// Sanity check: if the last node stored in the index does not match the changelogi,
// the index is broken and needs rebuilt. That could happen if strip happens.
let rev: KeyId = (next_rev - 1).into();
let node = rev_to_node(&changelogi, rev)?;
if let Ok(Some(id)) = radix_lookup_unchecked(&main_index, MAIN_RADIX_OFFSET, &node) {
if id != rev {
bail!(ErrorKind::IndexCorrupted);
}
} else {
bail!(ErrorKind::IndexCorrupted);
}
}
// Build side_index for the revisions not in the main index
let mut side_index = vec![0u32; RADIX_NCHILDREN];
build(
&changelogi,
&mut side_index,
SIDE_RADIX_OFFSET,
next_rev,
end_rev,
durhamUnsubmitted
Not Done

Why 'cloned()' here?

durham: Why 'cloned()' here?
quarkAuthorUnsubmitted
Not Done

The Rust iter() by default return references (&u8) for its elements. .cloned() converts those references to actual values (u8). It does not clone the iterator. It's like:

.map(|&x| x)
quark: The Rust `iter()` by default return references (`&u8`) for its elements. `.cloned()` converts…
)?;
Ok(NodeRevMap {
changelogi,
main_index,
side_index,
})
}
/// Return an empty index that can be used as "main_index" when passed to `new`.
pub fn empty_index_buffer() -> Vec<u32> {
return vec![0u32; RADIX_HEADER_LEN + RADIX_NCHILDREN];
}
/// Convert hex prefix to node.
pub fn hex_prefix_to_node<T: AsRef<[u8]>>(&self, hex_prefix: T) -> Result<Option<&[u8]>> {
let bin_prefix = match hex_to_bin_base16(hex_prefix) {
Some(v) => v,
durhamUnsubmitted
Not Done

Might be worth making the root node position a constant, instead of having magic '1' variables all over. Same for 0 for the side index root.

durham: Might be worth making the root node position a constant, instead of having magic '1' variables…
quarkAuthorUnsubmitted
Not Done

Good point.

quark: Good point.
None => return Ok(None),
};
let iter = bin_prefix.iter().cloned();
let cl = &self.changelogi;
let main_res = radix_prefix_lookup(
&self.main_index,
MAIN_RADIX_OFFSET,
iter.clone(),
rev_to_node,
cl,
)?;
durhamUnsubmitted
Not Done

from_le, in line 156 too

durham: from_le, in line 156 too
let side_res =
radix_prefix_lookup(&self.side_index, SIDE_RADIX_OFFSET, iter, rev_to_node, cl)?;
match (main_res, side_res) {
(Some(_), Some(_)) => {
let err: rerrors::Error = rerrors::ErrorKind::AmbiguousPrefix.into();
Err(err.into())
}
(Some(rev), None) |
(None, Some(rev)) => Ok(Some(rev_to_node(&self.changelogi, rev)?)),
_ => Ok(None),
}
}
/// Convert node to rev.
pub fn node_to_rev<T: AsRef<[u8]>>(&self, node: T) -> Result<Option<u32>> {
let cl = &self.changelogi;
if let Some(rev) = radix_lookup(&self.main_index, 1, &node, rev_to_node, cl)? {
Ok(Some(rev.into()))
} else if let Some(rev) = radix_lookup(&self.side_index, 0, &node, rev_to_node, cl)? {
Ok(Some(rev.into()))
durhamUnsubmitted
Done

Probably use a constant for the revlog entry width

durham: Probably use a constant for the revlog entry width
} else {
Ok(None)
}
}
durhamUnsubmitted
Not Done

I wonder if it's worth it to start putting these revlog accessor functions in their own file. To start building our revlog handling rust code for reuse outside of individual cases like this. Maybe by defining a RevlogIndex type as just a [u8] for now and putting a bunch of these function on it?

durham: I wonder if it's worth it to start putting these revlog accessor functions in their own file.
quarkAuthorUnsubmitted
Not Done

A later patch does that. But the code here is in theory somehow "de-coupled" from the actual revlog format. i.e. other append-only format should also work.

quark: A later patch does that. But the code here is in theory somehow "de-coupled" from the actual…
/// How many revisions the side index has.
pub fn lag(&self) -> u32 {
let next_rev = u32::from_be(self.main_index.as_ref()[0]);
durhamUnsubmitted
Not Done

What does "forked" mean in this case?

durham: What does "forked" mean in this case?
quarkAuthorUnsubmitted
Not Done

Since main_index is read-only. It's copied to a Vec and then modifications are done to it. Maybe "copied on write".

quark: Since `main_index` is read-only. It's copied to a `Vec` and then modifications are done to it.
durhamUnsubmitted
Not Done

Hmm, just seems odd to mention that in the function description, since the function doesn't care if it's a fork or not. It just puts new entries in the index it was given.

durham: Hmm, just seems odd to mention that in the function description, since the function doesn't…
quarkAuthorUnsubmitted
Not Done

This is O(len(index)) time complexity in theory, although memcpy without parsing is relatively fast. But there are no other places with that time complexity so I'd like to label that.

Shall we have more advanced ways to deal with filesystem confidently, that time complexity can be reduced.

quark: This is O(len(index)) time complexity in theory, although memcpy without parsing is relatively…
quarkAuthorUnsubmitted
Not Done

I made a mistake. I thought the comment was at build_incrementally. Will change.

quark: I made a mistake. I thought the comment was at `build_incrementally`. Will change.
let end_rev = changelog_end_rev(&self.changelogi);
end_rev - next_rev
}
/// Incrementally build the main index based on the existing one.
/// Note: this will memcpy the immutable main index so the new buffer
/// could be written and resized.
pub fn build_incrementally(&self) -> Result<Vec<u32>> {
// Copy the main index since we need to modify it.
let mut index = self.main_index.as_ref().to_vec();
let end_rev = changelog_end_rev(&self.changelogi);
let next_rev = u32::from_be(index[0]);
build(
&self.changelogi,
&mut index,
MAIN_RADIX_OFFSET,
next_rev,
end_rev,
)?;
index[0] = end_rev.to_be();
Ok(index)
durhamUnsubmitted
Not Done

more magic numbers

durham: more magic numbers
}
}
/// Return the minimal revision number the changelog.i does not have.
fn changelog_end_rev<T: AsRef<[u8]>>(changelogi: &T) -> u32 {
durhamUnsubmitted
Not Done

noob question: I thought this would return a reference to the slice of the buffer. But the lifetime isn't tied to the buffer, so that doesn't seem right. What am I missing?

durham: noob question: I thought this would return a reference to the slice of the buffer. But the…
quarkAuthorUnsubmitted
Not Done

The lifetime is implicitly tied. It's equivalent to:

fn rev_to_node<'a, K: AsRef<[u8]>>(changelog: &'a K, rev: KeyId) -> rerrors::Result<&'a [u8]>

The compiler knows that because there is only one reference type (changelog) in input arguments. If there are many, the compiler will complain.

quark: The lifetime is implicitly tied. It's equivalent to: fn rev_to_node<'a, K: AsRef<[u8]>>…
durhamUnsubmitted
Not Done

So it will associate any return reference with whichever argument is a reference? That doesn't seem safe. Or is only because this slice is a slice of the changelog as_ref that it knows its related to the changelog?

durham: So it will associate any return reference with whichever argument is a reference? That doesn't…
quarkAuthorUnsubmitted
Not Done

It does both. First, desugar the code to the explicit lifetime version. Then run the borrow checker which knows the returned slice comes from changelog.

quark: It does both. First, desugar the code to the explicit lifetime version. Then run the borrow…
let changelogi = changelogi.as_ref();
let rev = changelogi.len() as u64 / CHANGELOG_ENTRY_SIZE;
if rev > u32::MAX as u64 {
panic!("rev exceeds 32 bit integers")
}
rev as u32
}
/// Read the given range of revisions (from `start_rev` (inclusive) to
/// `end_rev` (exclusive)) from changelogi. Insert them to the radix
/// index.
fn build<T>(changelogi: &T, index: &mut Vec<u32>, radix_offset: u32, start_rev: u32, end_rev: u32)
-> Result<()>
where
durhamUnsubmitted
Not Done

Should the return None one be a panic or something? Since it should never happen right?

durham: Should the return None one be a panic or something? Since it should never happen right?
quarkAuthorUnsubmitted
Not Done

IIRC, the Python code might feed all kinds of strange things like a revset string to paritalmatch. So it's also nicer to support that.

I checked the revlog.c behavior, it returns None for partialmatch('xxxx'). I also think it makes sense to return None (no match).

quark: IIRC, the Python code might feed all kinds of strange things like a revset string to…
T: AsRef<[u8]>,
{
// Reserve the approximate size needed for the index - 28 bytes for each revision.
// See D1291 for a table of number of revisions and index sizes.
index.reserve(7 * (end_rev - start_rev) as usize);
for i in start_rev..end_rev {
let res = radix_insert(index, radix_offset, i.into(), rev_to_node, changelogi);
durhamUnsubmitted
Not Done

s/64/CHANGELOG_ENTRY_SIZE/

durham: s/64/CHANGELOG_ENTRY_SIZE/
res.chain_err(|| ErrorKind::IndexCorrupted)?;
}
Ok(())
}
/// Helper method similar to `radixbuf::key::FixedKey::read`, but takes a revision number instead.
fn rev_to_node<K: AsRef<[u8]>>(changelogi: &K, rev: KeyId) -> rerrors::Result<&[u8]> {
let buf = changelogi.as_ref();
let rev_usize: usize = rev.into();
let start_pos = rev_usize * 64 + 32;
let end_pos = start_pos + 20;
if buf.len() < end_pos {
Err(rerrors::ErrorKind::InvalidKeyId(rev).into())
} else {
Ok(&buf[start_pos..end_pos])
}
}
/// Convert hex base16 sequence to binary base16 sequence.
fn hex_to_bin_base16<T: AsRef<[u8]>>(base16: T) -> Option<Vec<u8>> {
let base16 = base16.as_ref();
let len = base16.len();
let mut result = vec![0u8; len];
for (i, &ch) in base16.iter().enumerate() {
result[i] = match ch {
b'a'...b'f' => ch - b'a' + 10,
b'A'...b'F' => ch - b'A' + 10,
b'0'...b'9' => ch - b'0',
_ => return None,
}
}
Some(result)
}