rhg: use persistent nodemap when available

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

Differential Revision: https://phab.mercurial-scm.org/D9520

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

@@ -0,0 +1,119 b''
+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
+    ///   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()
+        {
+            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)?;
+        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)?;
+
+        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/requirements.rs

@@ -69,4 +69,8 b' const SUPPORTED: &[&str] = &['
     "revlogv1",
     "sparserevlog",
     "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

@@ -7,6 +7,7 b''
 
 pub mod node;
 pub mod nodemap;
+mod nodemap_docket;
 pub mod path_encode;
 pub use node::{Node, NodeError, NodePrefix, NodePrefixRef};
 pub mod changelog;

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

@@ -132,6 +132,16 b' impl Index {'
     }
 }
 
+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)]
 pub struct IndexEntry<'a> {
     bytes: &'a [u8],
@@ -190,7 +200,7 b" impl<'a> IndexEntry<'a> {"
     ///
     /// Currently, SHA-1 is used and only the first 20 bytes of this field
     /// are used.
-    pub fn hash(&self) -> &Node {
+    pub fn hash(&self) -> &'a Node {
         (&self.bytes[32..52]).try_into().unwrap()
     }
 }

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

@@ -14,6 +14,9 b' use zstd;'
 
 use super::index::Index;
 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 crate::revlog::Revision;
 
@@ -27,7 +30,7 b' pub enum RevlogError {'
     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 mmap = unsafe { MmapOptions::new().map(&file) }?;
     Ok(mmap)
@@ -41,6 +44,8 b' pub struct Revlog {'
     index: Index,
     /// When index and data are not interleaved: bytes of the revlog data
     data_bytes: Option<Box<dyn Deref<Target = [u8]> + Send>>,
+    /// When present on disk: the persistent nodemap for this revlog
+    nodemap: Option<nodemap::NodeTree>,
 }
 
 impl Revlog {
@@ -77,7 +82,20 b' impl Revlog {'
                 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`.
@@ -96,8 +114,20 b' impl Revlog {'
         &self,
         node: NodePrefixRef,
     ) -> Result<Revision, RevlogError> {
-        // This is brute force. But it is fast enough for now.
-        // Optimization will come later.
+        if let Some(nodemap) = &self.nodemap {
+            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;
         for rev in (0..self.len() as Revision).rev() {
             let index_entry =

rust/hg-core/src/utils.rs

@@ -167,3 +167,12 b" impl<'a> Escaped for &'a HgPath {"
         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

@@ -196,5 +196,9 b' Persistent nodemap'
   .hg/store/00changelog.d
   .hg/store/00changelog.i
   .hg/store/00changelog.n
+
+Specifying revisions by changeset ID
   $ rhg files -r c3ae8dec9fad
-  [252]
+  of
+  $ rhg cat -r c3ae8dec9fad of
+  r5000