This is an archive of the discontinued Mercurial Phabricator instance.

Differential D11091

dirstate-v2: shrink on-disk path lengths to 16-bits
ClosedPublic

Authored by SimonSapin on Jul 13 2021, 3:50 PM.

Details

Reviewers
Alphare
marmoute
Group Reviewers
hg-reviewers
Commits
rHGda1c0cd68d53: dirstate-v2: shrink on-disk path lengths to 16-bits

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

SimonSapin created this revision.Jul 13 2021, 3:50 PM
Alphare accepted this revision.Jul 16 2021, 5:28 AM
This revision is now accepted and ready to land.Jul 16 2021, 5:28 AM
marmoute accepted this revision.Jul 16 2021, 5:55 AM
SimonSapin updated this revision to Diff 29333.Jul 16 2021, 8:37 AM
baymax updated this revision to Diff 29609.Jul 20 2021, 3:41 PM

✅ refresh by Heptapod after a successful CI run (🐙 💚)

SimonSapin added a commit: rHGda1c0cd68d53: dirstate-v2: shrink on-disk path lengths to 16-bits.Jul 20 2021, 3:48 PM
Closed by commit rHGda1c0cd68d53: dirstate-v2: shrink on-disk path lengths to 16-bits (authored by SimonSapin). · Explain Why
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

Diff 29620

rust/hg-core/src/dirstate_tree/on_disk.rs

use crate::dirstate_tree::dirstate_map::{self, DirstateMap, NodeRef}; use crate::dirstate_tree::dirstate_map::{self, DirstateMap, NodeRef};
use crate::dirstate_tree::path_with_basename::WithBasename; use crate::dirstate_tree::path_with_basename::WithBasename;
use crate::errors::HgError; use crate::errors::HgError;
use crate::utils::hg_path::HgPath; use crate::utils::hg_path::HgPath;
use crate::DirstateEntry; use crate::DirstateEntry;
use crate::DirstateError; use crate::DirstateError;
use crate::DirstateParents; use crate::DirstateParents;
use crate::EntryState; use crate::EntryState;
use bytes_cast::unaligned::{I32Be, I64Be, U32Be}; use bytes_cast::unaligned::{I32Be, I64Be, U16Be, U32Be};
use bytes_cast::BytesCast; use bytes_cast::BytesCast;
use format_bytes::format_bytes; use format_bytes::format_bytes;
use std::borrow::Cow; use std::borrow::Cow;
use std::convert::{TryFrom, TryInto}; use std::convert::{TryFrom, TryInto};
use std::time::{Duration, SystemTime, UNIX_EPOCH}; use std::time::{Duration, SystemTime, UNIX_EPOCH};
/// Added at the start of `.hg/dirstate` when the "v2" format is used. /// Added at the start of `.hg/dirstate` when the "v2" format is used.
/// This a redundant sanity check more than an actual "magic number" since /// This a redundant sanity check more than an actual "magic number" since
// Must match `HEADER` in `mercurial/dirstateutils/docket.py` // Must match `HEADER` in `mercurial/dirstateutils/docket.py`
#[derive(BytesCast)] #[derive(BytesCast)]
#[repr(C)] #[repr(C)]
struct DocketHeader { struct DocketHeader {
marker: [u8; V2_FORMAT_MARKER.len()], marker: [u8; V2_FORMAT_MARKER.len()],
parent_1: [u8; STORED_NODE_ID_BYTES], parent_1: [u8; STORED_NODE_ID_BYTES],
parent_2: [u8; STORED_NODE_ID_BYTES], parent_2: [u8; STORED_NODE_ID_BYTES],
/// Counted in bytes
data_size: Size, data_size: Size,
uuid_size: u8, uuid_size: u8,
} }
pub struct Docket<'on_disk> { pub struct Docket<'on_disk> {
header: &'on_disk DocketHeader, header: &'on_disk DocketHeader,
uuid: &'on_disk [u8], uuid: &'on_disk [u8],
} }
} }
#[derive(BytesCast)] #[derive(BytesCast)]
#[repr(C)] #[repr(C)]
pub(super) struct Node { pub(super) struct Node {
full_path: PathSlice, full_path: PathSlice,
/// In bytes from `self.full_path.start` /// In bytes from `self.full_path.start`
base_name_start: Size, base_name_start: PathSize,
copy_source: OptPathSlice, copy_source: OptPathSlice,
children: ChildNodes, children: ChildNodes,
pub(super) descendants_with_entry_count: Size, pub(super) descendants_with_entry_count: Size,
pub(super) tracked_descendants_count: Size, pub(super) tracked_descendants_count: Size,
/// Depending on the value of `state`: /// Depending on the value of `state`:
/// ///
/// Counted in bytes from the start of the file /// Counted in bytes from the start of the file
/// ///
/// NOTE: not supporting `.hg/dirstate` files larger than 4 GiB. /// NOTE: not supporting `.hg/dirstate` files larger than 4 GiB.
type Offset = U32Be; type Offset = U32Be;
/// Counted in number of items /// Counted in number of items
/// ///
/// NOTE: not supporting directories with more than 4 billion direct children, /// NOTE: we choose not to support counting more than 4 billion nodes anywhere.
/// or filenames more than 4 GiB.
type Size = U32Be; type Size = U32Be;
/// Location of consecutive, fixed-size items. /// Counted in bytes
/// ///
/// An item can be a single byte for paths, or a struct with /// NOTE: we choose not to support file names/paths longer than 64 KiB.
/// `derive(BytesCast)`. type PathSize = U16Be;
#[derive(BytesCast, Copy, Clone)]
#[repr(C)]
struct Slice {
start: Offset,
len: Size,
}
/// A contiguous sequence of `len` times `Node`, representing the child nodes /// A contiguous sequence of `len` times `Node`, representing the child nodes
/// of either some other node or of the repository root. /// of either some other node or of the repository root.
/// ///
/// Always sorted by ascending `full_path`, to allow binary search. /// Always sorted by ascending `full_path`, to allow binary search.
/// Since nodes with the same parent nodes also have the same parent path, /// Since nodes with the same parent nodes also have the same parent path,
/// only the `base_name`s need to be compared during binary search. /// only the `base_name`s need to be compared during binary search.
type ChildNodes = Slice; #[derive(BytesCast, Copy, Clone)]
#[repr(C)]
struct ChildNodes {
start: Offset,
len: Size,
}
/// A `HgPath` of `len` bytes /// A `HgPath` of `len` bytes
type PathSlice = Slice; #[derive(BytesCast, Copy, Clone)]
#[repr(C)]
struct PathSlice {
start: Offset,
len: PathSize,
}
/// Either nothing if `start == 0`, or a `HgPath` of `len` bytes /// Either nothing if `start == 0`, or a `HgPath` of `len` bytes
type OptPathSlice = Slice; type OptPathSlice = PathSlice;
/// Make sure that size-affecting changes are made knowingly /// Make sure that size-affecting changes are made knowingly
fn _static_assert_size_of() { fn _static_assert_size_of() {
let _ = std::mem::transmute::<DocketHeader, [u8; 81]>; let _ = std::mem::transmute::<DocketHeader, [u8; 81]>;
let _ = std::mem::transmute::<Root, [u8; 36]>; let _ = std::mem::transmute::<Root, [u8; 36]>;
let _ = std::mem::transmute::<Node, [u8; 49]>; let _ = std::mem::transmute::<Node, [u8; 43]>;
} }
/// Unexpected file format found in `.hg/dirstate` with the "v2" format. /// Unexpected file format found in `.hg/dirstate` with the "v2" format.
/// ///
/// This should only happen if Mercurial is buggy or a repository is corrupted. /// This should only happen if Mercurial is buggy or a repository is corrupted.
#[derive(Debug)] #[derive(Debug)]
pub struct DirstateV2ParseError; pub struct DirstateV2ParseError;
on_disk: &'on_disk [u8], on_disk: &'on_disk [u8],
) -> Result<DirstateMap<'on_disk>, DirstateV2ParseError> { ) -> Result<DirstateMap<'on_disk>, DirstateV2ParseError> {
if on_disk.is_empty() { if on_disk.is_empty() {
return Ok(DirstateMap::empty(on_disk)); return Ok(DirstateMap::empty(on_disk));
} }
let root = read_root(on_disk)?; let root = read_root(on_disk)?;
let dirstate_map = DirstateMap { let dirstate_map = DirstateMap {
on_disk, on_disk,
root: dirstate_map::ChildNodes::OnDisk(read_slice::<Node>( root: dirstate_map::ChildNodes::OnDisk(read_nodes(
on_disk, on_disk,
root.root_nodes, root.root_nodes,
)?), )?),
nodes_with_entry_count: root.nodes_with_entry_count.get(), nodes_with_entry_count: root.nodes_with_entry_count.get(),
nodes_with_copy_source_count: root.nodes_with_copy_source_count.get(), nodes_with_copy_source_count: root.nodes_with_copy_source_count.get(),
ignore_patterns_hash: root.ignore_patterns_hash, ignore_patterns_hash: root.ignore_patterns_hash,
}; };
Ok(dirstate_map) Ok(dirstate_map)
.state()? .state()?
.map(|state| self.entry_with_given_state(state))) .map(|state| self.entry_with_given_state(state)))
} }
pub(super) fn children<'on_disk>( pub(super) fn children<'on_disk>(
&self, &self,
on_disk: &'on_disk [u8], on_disk: &'on_disk [u8],
) -> Result<&'on_disk [Node], DirstateV2ParseError> { ) -> Result<&'on_disk [Node], DirstateV2ParseError> {
read_slice::<Node>(on_disk, self.children) read_nodes(on_disk, self.children)
} }
pub(super) fn to_in_memory_node<'on_disk>( pub(super) fn to_in_memory_node<'on_disk>(
&self, &self,
on_disk: &'on_disk [u8], on_disk: &'on_disk [u8],
) -> Result<dirstate_map::Node<'on_disk>, DirstateV2ParseError> { ) -> Result<dirstate_map::Node<'on_disk>, DirstateV2ParseError> {
Ok(dirstate_map::Node { Ok(dirstate_map::Node {
children: dirstate_map::ChildNodes::OnDisk( children: dirstate_map::ChildNodes::OnDisk(
} else { } else {
UNIX_EPOCH - Duration::new((-secs) as u64, nanos) UNIX_EPOCH - Duration::new((-secs) as u64, nanos)
} }
} }
} }
fn read_hg_path( fn read_hg_path(
on_disk: &[u8], on_disk: &[u8],
slice: Slice, slice: PathSlice,
) -> Result<&HgPath, DirstateV2ParseError> { ) -> Result<&HgPath, DirstateV2ParseError> {
let bytes = read_slice::<u8>(on_disk, slice)?; read_slice(on_disk, slice.start, slice.len.get()).map(HgPath::new)
Ok(HgPath::new(bytes)) }
fn read_nodes(
on_disk: &[u8],
slice: ChildNodes,
) -> Result<&[Node], DirstateV2ParseError> {
read_slice(on_disk, slice.start, slice.len.get())
} }
fn read_slice<T>( fn read_slice<T, Len>(
on_disk: &[u8], on_disk: &[u8],
slice: Slice, start: Offset,
len: Len,
) -> Result<&[T], DirstateV2ParseError> ) -> Result<&[T], DirstateV2ParseError>
where where
T: BytesCast, T: BytesCast,
Len: TryInto<usize>,
{ {
// Either `usize::MAX` would result in "out of bounds" error since a single // Either `usize::MAX` would result in "out of bounds" error since a single
// `&[u8]` cannot occupy the entire addess space. // `&[u8]` cannot occupy the entire addess space.
let start = usize::try_from(slice.start.get()).unwrap_or(std::usize::MAX); let start = start.get().try_into().unwrap_or(std::usize::MAX);
let len = usize::try_from(slice.len.get()).unwrap_or(std::usize::MAX); let len = len.try_into().unwrap_or(std::usize::MAX);
on_disk on_disk
.get(start..) .get(start..)
.and_then(|bytes| T::slice_from_bytes(bytes, len).ok()) .and_then(|bytes| T::slice_from_bytes(bytes, len).ok())
.map(|(slice, _rest)| slice) .map(|(slice, _rest)| slice)
.ok_or_else(|| DirstateV2ParseError) .ok_or_else(|| DirstateV2ParseError)
} }
pub(crate) fn for_each_tracked_path<'on_disk>( pub(crate) fn for_each_tracked_path<'on_disk>(
on_disk: &'on_disk [u8], on_disk: &'on_disk [u8],
mut f: impl FnMut(&'on_disk HgPath), mut f: impl FnMut(&'on_disk HgPath),
) -> Result<(), DirstateV2ParseError> { ) -> Result<(), DirstateV2ParseError> {
let root = read_root(on_disk)?; let root = read_root(on_disk)?;
fn recur<'on_disk>( fn recur<'on_disk>(
on_disk: &'on_disk [u8], on_disk: &'on_disk [u8],
nodes: Slice, nodes: ChildNodes,
f: &mut impl FnMut(&'on_disk HgPath), f: &mut impl FnMut(&'on_disk HgPath),
) -> Result<(), DirstateV2ParseError> { ) -> Result<(), DirstateV2ParseError> {
for node in read_slice::<Node>(on_disk, nodes)? { for node in read_nodes(on_disk, nodes)? {
if let Some(state) = node.state()? { if let Some(state) = node.state()? {
if state.is_tracked() { if state.is_tracked() {
f(node.full_path(on_disk)?) f(node.full_path(on_disk)?)
} }
} }
recur(on_disk, node.children, f)? recur(on_disk, node.children, f)?
} }
Ok(()) Ok(())
fn write_nodes( fn write_nodes(
dirstate_map: &DirstateMap, dirstate_map: &DirstateMap,
nodes: dirstate_map::ChildNodesRef, nodes: dirstate_map::ChildNodesRef,
out: &mut Vec<u8>, out: &mut Vec<u8>,
) -> Result<ChildNodes, DirstateError> { ) -> Result<ChildNodes, DirstateError> {
// `dirstate_map::ChildNodes` is a `HashMap` with undefined iteration // `dirstate_map::ChildNodes` is a `HashMap` with undefined iteration
// order. Sort to enable binary search in the written file. // order. Sort to enable binary search in the written file.
let nodes = nodes.sorted(); let nodes = nodes.sorted();
let nodes_len = nodes.len();
// First accumulate serialized nodes in a `Vec` // First accumulate serialized nodes in a `Vec`
let mut on_disk_nodes = Vec::with_capacity(nodes.len()); let mut on_disk_nodes = Vec::with_capacity(nodes_len);
for node in nodes { for node in nodes {
let children = write_nodes( let children = write_nodes(
dirstate_map, dirstate_map,
node.children(dirstate_map.on_disk)?, node.children(dirstate_map.on_disk)?,
out, out,
)?; )?;
let full_path = node.full_path(dirstate_map.on_disk)?; let full_path = node.full_path(dirstate_map.on_disk)?;
let full_path = write_slice::<u8>(full_path.as_bytes(), out); let full_path = write_path(full_path.as_bytes(), out);
let copy_source = let copy_source =
if let Some(source) = node.copy_source(dirstate_map.on_disk)? { if let Some(source) = node.copy_source(dirstate_map.on_disk)? {
write_slice::<u8>(source.as_bytes(), out) write_path(source.as_bytes(), out)
} else { } else {
Slice { PathSlice {
start: 0.into(), start: 0.into(),
len: 0.into(), len: 0.into(),
} }
}; };
on_disk_nodes.push(match node { on_disk_nodes.push(match node {
NodeRef::InMemory(path, node) => { NodeRef::InMemory(path, node) => {
let (state, data) = match &node.data { let (state, data) = match &node.data {
dirstate_map::NodeData::Entry(entry) => ( dirstate_map::NodeData::Entry(entry) => (
size: 0.into(), size: 0.into(),
}, },
), ),
}; };
Node { Node {
children, children,
copy_source, copy_source,
full_path, full_path,
base_name_start: u32::try_from(path.base_name_start()) base_name_start: u16::try_from(path.base_name_start())
// Could only panic for paths over 4 GiB // Could only panic for paths over 64 KiB
.expect("dirstate-v2 offset overflow") .expect("dirstate-v2 path length overflow")
.into(), .into(),
descendants_with_entry_count: node descendants_with_entry_count: node
.descendants_with_entry_count .descendants_with_entry_count
.into(), .into(),
tracked_descendants_count: node tracked_descendants_count: node
.tracked_descendants_count .tracked_descendants_count
.into(), .into(),
state, state,
data, data,
} }
} }
NodeRef::OnDisk(node) => Node { NodeRef::OnDisk(node) => Node {
children, children,
copy_source, copy_source,
full_path, full_path,
..*node ..*node
}, },
}) })
} }
// … so we can write them contiguously // … so we can write them contiguously, after writing everything else they
Ok(write_slice::<Node>(&on_disk_nodes, out)) // refer to.
let start = current_offset(out);
let len = u32::try_from(nodes_len)
// Could only panic with over 4 billion nodes
.expect("dirstate-v2 path length overflow")
.into();
out.extend(on_disk_nodes.as_bytes());
Ok(ChildNodes { start, len })
} }
fn write_slice<T>(slice: &[T], out: &mut Vec<u8>) -> Slice fn current_offset(out: &Vec<u8>) -> Offset {
where u32::try_from(out.len())
T: BytesCast,
{
let start = u32::try_from(out.len())
// Could only panic for a dirstate file larger than 4 GiB // Could only panic for a dirstate file larger than 4 GiB
.expect("dirstate-v2 offset overflow") .expect("dirstate-v2 offset overflow")
.into(); .into()
let len = u32::try_from(slice.len()) }
// Could only panic for paths over 4 GiB or nodes with over 4 billions
// child nodes fn write_path(slice: &[u8], out: &mut Vec<u8>) -> PathSlice {
.expect("dirstate-v2 offset overflow") let start = current_offset(out);
let len = u16::try_from(slice.len())
// Could only panic for paths over 64 KiB
.expect("dirstate-v2 path length overflow")
.into(); .into();
out.extend(slice.as_bytes()); out.extend(slice.as_bytes());
Slice { start, len } PathSlice { start, len }
} }