This is an archive of the discontinued Mercurial Phabricator instance.

Differential D11655

dirstate-v2: Add storage space for nanoseconds precision in file mtimes
ClosedPublic

Authored by SimonSapin on Oct 13 2021, 11:39 AM.

Details

Reviewers
pulkit
Group Reviewers
hg-reviewers
Commits
rHG308d9c245337: dirstate-v2: Add storage space for nanoseconds precision in file mtimes
Summary

For now the sub-second component is always set to zero for tracked files and
symlinks. (The mtime of directories for the readdir-skipping optimization
is a different code path and already uses the full precision available.)

This extra storage uses the space previously freed by replacing the 32-bit
mode field by two bits in the existing flags field, so the overall size
of nodes is unchanged. (This space had been left as padding for this purpose.)

Also move things around in the node layout and documentation to have less
duplication. Now that they have the same representation, directory mtime and
file mtime are kept in the same field. (Only either one can exist for a given
node.)

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.

Revision Contents
Changeset List

Diff 30795

mercurial/helptext/internals/dirstate-v2.txt

* Offset 26: * Offset 26:
Number as a 32-bit integer of descendant nodes in this subtree, Number as a 32-bit integer of descendant nodes in this subtree,
not including this node itself, not including this node itself,
that represent files tracked in the working directory. that represent files tracked in the working directory.
(For example, `hg rm` makes a file untracked.) (For example, `hg rm` makes a file untracked.)
This counter is used to implement `has_tracked_dir`. This counter is used to implement `has_tracked_dir`.
* Offset 30: * Offset 30:
Some boolean values packed as bits of a single byte. A single `flags` byte that packs some boolean values as bits.
Starting from least-significant, bit masks are:: Starting from least-significant, bit masks are::
WDIR_TRACKED = 1 << 0 WDIR_TRACKED = 1 << 0
P1_TRACKED = 1 << 1 P1_TRACKED = 1 << 1
P2_INFO = 1 << 2 P2_INFO = 1 << 2
HAS_MODE_AND_SIZE = 1 << 3 HAS_MODE_AND_SIZE = 1 << 3
HAS_MTIME = 1 << 4 HAS_MTIME = 1 << 4
MODE_EXEC_PERM = 1 << 5 MODE_EXEC_PERM = 1 << 5
MODE_IS_SYMLINK = 1 << 7 MODE_IS_SYMLINK = 1 << 6
The meaning of each bit is described below.
Other bits are unset.
Other bits are unset. The meaning of these bits are: * Offset 31:
A `size` field described below, as a 32-bit integer.
Unlike in dirstate-v1, negative values are not used.
* Offset 35:
The seconds component of an `mtime` field described below,
as a 32-bit integer.
Unlike in dirstate-v1, negative values are not used.
* Offset 39:
The nanoseconds component of an `mtime` field described below,
as a 32-bit integer.
* (Offset 43: end of this node)
The meaning of the boolean values packed in `flags` is:
`WDIR_TRACKED` `WDIR_TRACKED`
Set if the working directory contains a tracked file at this node’s path. Set if the working directory contains a tracked file at this node’s path.
This is typically set and unset by `hg add` and `hg rm`. This is typically set and unset by `hg add` and `hg rm`.
`P1_TRACKED` `P1_TRACKED`
set if the working directory’s first parent changeset Set if the working directory’s first parent changeset
(whose node identifier is found in tree metadata) (whose node identifier is found in tree metadata)
contains a tracked file at this node’s path. contains a tracked file at this node’s path.
This is a cache to reduce manifest lookups. This is a cache to reduce manifest lookups.
`P2_INFO` `P2_INFO`
Set if the file has been involved in some merge operation. Set if the file has been involved in some merge operation.
Either because it was actually merged, Either because it was actually merged,
or because the version in the second parent p2 version was ahead, or because the version in the second parent p2 version was ahead,
or because some rename moved it there. or because some rename moved it there.
In either case `hg status` will want it displayed as modified. In either case `hg status` will want it displayed as modified.
Files that would be mentioned at all in the `dirstate-v1` file format Files that would be mentioned at all in the `dirstate-v1` file format
have a node with at least one of the above three bits set in `dirstate-v2`. have a node with at least one of the above three bits set in `dirstate-v2`.
Let’s call these files "tracked anywhere", Let’s call these files "tracked anywhere",
and "untracked" the nodes with all three of these bits unset. and "untracked" the nodes with all three of these bits unset.
Untracked nodes are typically for directories: Untracked nodes are typically for directories:
they hold child nodes and form the tree structure. they hold child nodes and form the tree structure.
Additional untracked nodes may also exist. Additional untracked nodes may also exist.
Although implementations should strive to clean up nodes Although implementations should strive to clean up nodes
that are entirely unused, other untracked nodes may also exist. that are entirely unused, other untracked nodes may also exist.
For example, a future version of Mercurial might in some cases For example, a future version of Mercurial might in some cases
add nodes for untracked files or/and ignored files in the working directory add nodes for untracked files or/and ignored files in the working directory
in order to optimize `hg status` in order to optimize `hg status`
by enabling it to skip `readdir` in more cases. by enabling it to skip `readdir` in more cases.
When a node is for a file tracked anywhere: `HAS_MODE_AND_SIZE`
- If `HAS_MODE_AND_SIZE` is set, the file is expected Must be unset for untracked nodes.
to be a symbolic link or a normal file based on `MODE_IS_SYMLINK`. For files tracked anywhere, if this is set:
- If `HAS_MODE_AND_SIZE` is set, the file’s owner is expected - The `size` field is the expected file size,
to have execute permission or not based on `MODE_EXEC_PERM`. in bytes truncated its lower to 31 bits,
- If `HAS_MODE_AND_SIZE` is unset, for the file to be clean.
the expected type of file and permission are unknown. - The expected execute permission for the file’s owner
The rest of the node data is three fields: is given by `MODE_EXEC_PERM`
- The expected file type is given by `MODE_IS_SIMLINK`:
* Offset 31: a symbolic link if set, or a normal file if unset.
4 unused bytes, set to zero If this is unset the expected size, permission, and file type are unknown.
The `size` field is unused (set to zero).
* Offset 35:
If `HAS_MODE_AND_SIZE` is unset, four zero bytes. `HAS_MTIME`
Otherwise, a 32-bit integer for expected size of the file If unset, the `mtime` field is unused (set to zero).
truncated to its 31 least-significant bits. If set, it contains a timestamp represented as
Unlike in dirstate-v1, negative values are not used. - the number of seconds since the Unix epoch,
truncated to its lower 31 bits.
* Offset 39: - and the number of nanoseconds since `mtime.seconds`,
If `HAS_MTIME` is unset, four zero bytes. always stritctly less than one billion.
Otherwise, a 32-bit integer for expected modified time of the file This may be zero if more precision is not available.
(as in `stat_result.st_mtime`), (This can happen because of limitations in any of Mercurial, Python,
truncated to its 31 least-significant bits. libc, the operating system, …)
Unlike in dirstate-v1, negative values are not used.
If an untracked node `HAS_MTIME` *unset*, this space is unused:
* Offset 31:
12 unused bytes, set to zero
If an untracked node `HAS_MTIME` *set*,
what follows is the modification time of a directory
represented similarly to the C `timespec` struct:
* Offset 31: If set for a file tracked anywhere,
4 unused bytes, set to zero `mtime` is the expected modification time for the file to be clean.
* Offset 35:
The number of seconds elapsed since the Unix epoch,
truncated to its lower 31 bits,
as a 32-bit integer.
* Offset 39: If set for an untracked node, at some point,
The sub-second number of nanoseconds elapsed since the Unix epoch,
as 32-bit integer.
Always greater than or equal to zero, and strictly less than a billion.
The presence of a directory modification time means that at some point,
this path in the working directory was observed: this path in the working directory was observed:
- To be a directory - To be a directory
- With the given modification time - With the modification time given in `mtime`
- That time was already strictly in the past when observed, - That time was already strictly in the past when observed,
meaning that later changes cannot happen in the same clock tick meaning that later changes cannot happen in the same clock tick
and must cause a different modification time and must cause a different modification time
(unless the system clock jumps back and we get unlucky, (unless the system clock jumps back and we get unlucky,
which is not impossible but deemed unlikely enough). which is not impossible but deemed unlikely enough).
- All direct children of this directory - All direct children of this directory
(as returned by `std::fs::read_dir`) (as returned by `std::fs::read_dir`)
either have a corresponding dirstate node, either have a corresponding dirstate node,
or are ignored by ignore patterns whose hash is in tree metadata. or are ignored by ignore patterns whose hash is in tree metadata.
This means that if `std::fs::symlink_metadata` later reports This means that if `std::fs::symlink_metadata` later reports
the same modification time the same modification time
and ignored patterns haven’t changed, and ignored patterns haven’t changed,
a run of status that is not listing ignored files a run of status that is not listing ignored files
can skip calling `std::fs::read_dir` again for this directory, can skip calling `std::fs::read_dir` again for this directory,
and iterate child dirstate nodes instead. and iterate child dirstate nodes instead.
`MODE_EXEC_PERM`
* (Offset 43: end of this node) Must be unset if `HAS_MODE_AND_SIZE` is unset.
If `HAS_MODE_AND_SIZE` is set,
this indicates whether the file’s own is expected
to have execute permission.
`MODE_IS_SYMLINK`
Must be unset if `HAS_MODE_AND_SIZE` is unset.
If `HAS_MODE_AND_SIZE` is set,
this indicates whether the file is expected to be a symlink
as opposed to a normal file.

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

/// In bytes from `self.full_path.start` /// In bytes from `self.full_path.start`
base_name_start: PathSize, 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,
flags: Flags, flags: Flags,
data: Entry, size: U32Be,
mtime: PackedTruncatedTimestamp,
} }
bitflags! { bitflags! {
#[derive(BytesCast)] #[derive(BytesCast)]
#[repr(C)] #[repr(C)]
struct Flags: u8 { struct Flags: u8 {
const WDIR_TRACKED = 1 << 0; const WDIR_TRACKED = 1 << 0;
const P1_TRACKED = 1 << 1; const P1_TRACKED = 1 << 1;
const P2_INFO = 1 << 2; const P2_INFO = 1 << 2;
const HAS_MODE_AND_SIZE = 1 << 3; const HAS_MODE_AND_SIZE = 1 << 3;
const HAS_MTIME = 1 << 4; const HAS_MTIME = 1 << 4;
const MODE_EXEC_PERM = 1 << 5; const MODE_EXEC_PERM = 1 << 5;
const MODE_IS_SYMLINK = 1 << 7; const MODE_IS_SYMLINK = 1 << 6;
}
} }
#[derive(BytesCast, Copy, Clone, Debug)]
#[repr(C)]
struct Entry {
_padding: U32Be,
size: U32Be,
mtime: U32Be,
} }
/// Duration since the Unix epoch /// Duration since the Unix epoch
#[derive(BytesCast, Copy, Clone)] #[derive(BytesCast, Copy, Clone)]
#[repr(C)] #[repr(C)]
struct PackedTimestamp { struct PackedTruncatedTimestamp {
_padding: U32Be,
truncated_seconds: U32Be, truncated_seconds: U32Be,
nanoseconds: U32Be, nanoseconds: U32Be,
} }
/// 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;
} }
} }
pub(super) fn cached_directory_mtime( pub(super) fn cached_directory_mtime(
&self, &self,
) -> Result<Option<TruncatedTimestamp>, DirstateV2ParseError> { ) -> Result<Option<TruncatedTimestamp>, DirstateV2ParseError> {
Ok( Ok(
if self.flags.contains(Flags::HAS_MTIME) && !self.has_entry() { if self.flags.contains(Flags::HAS_MTIME) && !self.has_entry() {
Some(self.data.as_timestamp()?) Some(self.mtime.try_into()?)
} else { } else {
None None
}, },
) )
} }
fn synthesize_unix_mode(&self) -> u32 { fn synthesize_unix_mode(&self) -> u32 {
let file_type = if self.flags.contains(Flags::MODE_IS_SYMLINK) { let file_type = if self.flags.contains(Flags::MODE_IS_SYMLINK) {
} }
fn assume_entry(&self) -> DirstateEntry { fn assume_entry(&self) -> DirstateEntry {
// TODO: convert through raw bits instead? // TODO: convert through raw bits instead?
let wdir_tracked = self.flags.contains(Flags::WDIR_TRACKED); let wdir_tracked = self.flags.contains(Flags::WDIR_TRACKED);
let p1_tracked = self.flags.contains(Flags::P1_TRACKED); let p1_tracked = self.flags.contains(Flags::P1_TRACKED);
let p2_info = self.flags.contains(Flags::P2_INFO); let p2_info = self.flags.contains(Flags::P2_INFO);
let mode_size = if self.flags.contains(Flags::HAS_MODE_AND_SIZE) { let mode_size = if self.flags.contains(Flags::HAS_MODE_AND_SIZE) {
Some((self.synthesize_unix_mode(), self.data.size.into())) Some((self.synthesize_unix_mode(), self.size.into()))
} else { } else {
None None
}; };
let mtime = if self.flags.contains(Flags::HAS_MTIME) { let mtime = if self.flags.contains(Flags::HAS_MTIME) {
Some(self.data.mtime.into()) Some(self.mtime.truncated_seconds.into())
} else { } else {
None None
}; };
DirstateEntry::from_v2_data( DirstateEntry::from_v2_data(
wdir_tracked, wdir_tracked,
p1_tracked, p1_tracked,
p2_info, p2_info,
mode_size, mode_size,
copy_source: self.copy_source(on_disk)?.map(Cow::Borrowed), copy_source: self.copy_source(on_disk)?.map(Cow::Borrowed),
data: self.node_data()?, data: self.node_data()?,
descendants_with_entry_count: self descendants_with_entry_count: self
.descendants_with_entry_count .descendants_with_entry_count
.get(), .get(),
tracked_descendants_count: self.tracked_descendants_count.get(), tracked_descendants_count: self.tracked_descendants_count.get(),
}) })
} }
}
impl Entry { fn from_dirstate_entry(
fn from_dirstate_entry(entry: &DirstateEntry) -> (Flags, Self) { entry: &DirstateEntry,
) -> (Flags, U32Be, PackedTruncatedTimestamp) {
let (wdir_tracked, p1_tracked, p2_info, mode_size_opt, mtime_opt) = let (wdir_tracked, p1_tracked, p2_info, mode_size_opt, mtime_opt) =
entry.v2_data(); entry.v2_data();
// TODO: convert throug raw flag bits instead? // TODO: convert throug raw flag bits instead?
let mut flags = Flags::empty(); let mut flags = Flags::empty();
flags.set(Flags::WDIR_TRACKED, wdir_tracked); flags.set(Flags::WDIR_TRACKED, wdir_tracked);
flags.set(Flags::P1_TRACKED, p1_tracked); flags.set(Flags::P1_TRACKED, p1_tracked);
flags.set(Flags::P2_INFO, p2_info); flags.set(Flags::P2_INFO, p2_info);
let (size, mtime); let size = if let Some((m, s)) = mode_size_opt {
if let Some((m, s)) = mode_size_opt {
let exec_perm = m & libc::S_IXUSR != 0; let exec_perm = m & libc::S_IXUSR != 0;
let is_symlink = m & libc::S_IFMT == libc::S_IFLNK; let is_symlink = m & libc::S_IFMT == libc::S_IFLNK;
flags.set(Flags::MODE_EXEC_PERM, exec_perm); flags.set(Flags::MODE_EXEC_PERM, exec_perm);
flags.set(Flags::MODE_IS_SYMLINK, is_symlink); flags.set(Flags::MODE_IS_SYMLINK, is_symlink);
size = s; flags.insert(Flags::HAS_MODE_AND_SIZE);
flags.insert(Flags::HAS_MODE_AND_SIZE) s.into()
} else {
size = 0;
}
if let Some(m) = mtime_opt {
mtime = m;
flags.insert(Flags::HAS_MTIME);
} else { } else {
mtime = 0; 0.into()
}
let raw_entry = Entry {
_padding: 0.into(),
size: size.into(),
mtime: mtime.into(),
}; };
(flags, raw_entry) let mtime = if let Some(m) = mtime_opt {
flags.insert(Flags::HAS_MTIME);
PackedTruncatedTimestamp {
truncated_seconds: m.into(),
nanoseconds: 0.into(),
} }
} else {
fn from_timestamp(timestamp: TruncatedTimestamp) -> Self { PackedTruncatedTimestamp::null()
let packed = PackedTimestamp {
_padding: 0.into(),
truncated_seconds: timestamp.truncated_seconds().into(),
nanoseconds: timestamp.nanoseconds().into(),
}; };
// Safety: both types implement the `ByteCast` trait, so we could (flags, size, mtime)
// safely use `as_bytes` and `from_bytes` to do this conversion. Using
// `transmute` instead makes the compiler check that the two types
// have the same size, which eliminates the error case of
// `from_bytes`.
unsafe { std::mem::transmute::<PackedTimestamp, Entry>(packed) }
}
fn as_timestamp(self) -> Result<TruncatedTimestamp, DirstateV2ParseError> {
// Safety: same as above in `from_timestamp`
let packed =
unsafe { std::mem::transmute::<Entry, PackedTimestamp>(self) };
TruncatedTimestamp::from_already_truncated(
packed.truncated_seconds.get(),
packed.nanoseconds.get(),
)
} }
} }
fn read_hg_path( fn read_hg_path(
on_disk: &[u8], on_disk: &[u8],
slice: PathSlice, slice: PathSlice,
) -> Result<&HgPath, DirstateV2ParseError> { ) -> Result<&HgPath, DirstateV2ParseError> {
read_slice(on_disk, slice.start, slice.len.get()).map(HgPath::new) read_slice(on_disk, slice.start, slice.len.get()).map(HgPath::new)
} else { } else {
PathSlice { 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 (flags, data) = match &node.data { let (flags, size, mtime) = match &node.data {
dirstate_map::NodeData::Entry(entry) => { dirstate_map::NodeData::Entry(entry) => {
Entry::from_dirstate_entry(entry) Node::from_dirstate_entry(entry)
} }
dirstate_map::NodeData::CachedDirectory { mtime } => { dirstate_map::NodeData::CachedDirectory { mtime } => {
(Flags::HAS_MTIME, Entry::from_timestamp(*mtime)) (Flags::HAS_MTIME, 0.into(), (*mtime).into())
} }
dirstate_map::NodeData::None => ( dirstate_map::NodeData::None => (
Flags::empty(), Flags::empty(),
Entry { 0.into(),
_padding: 0.into(), PackedTruncatedTimestamp::null(),
size: 0.into(),
mtime: 0.into(),
},
), ),
}; };
Node { Node {
children, children,
copy_source, copy_source,
full_path, full_path,
base_name_start: u16::try_from(path.base_name_start()) base_name_start: u16::try_from(path.base_name_start())
// Could only panic for paths over 64 KiB // Could only panic for paths over 64 KiB
.expect("dirstate-v2 path length 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(),
flags, flags,
data, size,
mtime,
} }
} }
NodeRef::OnDisk(node) => Node { NodeRef::OnDisk(node) => Node {
children, children,
copy_source, copy_source,
full_path, full_path,
..*node ..*node
}, },
} }
fn path_len_from_usize(x: usize) -> PathSize { fn path_len_from_usize(x: usize) -> PathSize {
u16::try_from(x) u16::try_from(x)
// Could only panic for paths over 64 KiB // Could only panic for paths over 64 KiB
.expect("dirstate-v2 path length overflow") .expect("dirstate-v2 path length overflow")
.into() .into()
} }
impl From<TruncatedTimestamp> for PackedTruncatedTimestamp {
fn from(timestamp: TruncatedTimestamp) -> Self {
Self {
truncated_seconds: timestamp.truncated_seconds().into(),
nanoseconds: timestamp.nanoseconds().into(),
}
}
}
impl TryFrom<PackedTruncatedTimestamp> for TruncatedTimestamp {
type Error = DirstateV2ParseError;
fn try_from(
timestamp: PackedTruncatedTimestamp,
) -> Result<Self, Self::Error> {
Self::from_already_truncated(
timestamp.truncated_seconds.get(),
timestamp.nanoseconds.get(),
)
}
}
impl PackedTruncatedTimestamp {
fn null() -> Self {
Self {
truncated_seconds: 0.into(),
nanoseconds: 0.into(),
}
}
}