This is an archive of the discontinued Mercurial Phabricator instance.

Differential D9843

revlog: introduce v2 format
ClosedPublic

Authored by Alphare on Jan 20 2021, 3:45 PM.

Details

Reviewers
indygreg
durin42
marmoute
Group Reviewers
hg-reviewers
Commits
rHG913485776542: revlog: introduce v2 format
Summary

As documented in [1], this is still tentative and could be subject to change,
but we need to lay down the foundations in order to work on the next abstraction
layers.

[1] https://www.mercurial-scm.org/wiki/RevlogV2Plan

Diff Detail

Repository
rHG Mercurial
Branch
default
Lint
No Linters Available
Unit
No Unit Test Coverage

Event Timeline

Alphare created this revision.Jan 20 2021, 3:45 PM
mharbison72 added a subscriber: mharbison72.Jan 20 2021, 5:39 PM

Can we get space for extra flags for things not supported by the filesystem? I'm thinking specifically +x and symlink support on Windows.

https://www.mercurial-scm.org/wiki/DirState#Proposed_extensions

marmoute added a subscriber: marmoute.Jan 20 2021, 6:04 PM
In D9843#149035, @mharbison72 wrote:

Can we get space for extra flags for things not supported by the filesystem? I'm thinking specifically +x and symlink support on Windows.
https://www.mercurial-scm.org/wiki/DirState#Proposed_extensions

That would be a dirstate thing, not a revlog thing, right ?

mharbison72 added a comment.Jan 20 2021, 6:36 PM
In D9843#149037, @marmoute wrote:
In D9843#149035, @mharbison72 wrote:

Can we get space for extra flags for things not supported by the filesystem? I'm thinking specifically +x and symlink support on Windows.
https://www.mercurial-scm.org/wiki/DirState#Proposed_extensions

That would be a dirstate thing, not a revlog thing, right ?

Oops, yeah. It’s been one of those days...

pulkit added a subscriber: pulkit.Jan 22 2021, 11:40 AM

Couple of changes from this patch can be separated and send individually as prepare for revlog v2 which will help speed up review.

mercurial/localrepo.py
3639 ↗(On Diff #25185)

This can be a separate patch and will be easy one to push.

mercurial/pure/parsers.py
45

IIUC, this change can also be a separate patch.

indygreg added a comment.Jan 24 2021, 8:50 PM

I'm not going to review this right now, but I have prior art at https://www.mercurial-scm.org/pipermail/mercurial-devel/2017-February/093657.html and https://www.mercurial-scm.org/pipermail/mercurial-devel/2017-May/097960.html that might be worth a read. I believe the wiki page on this format only contains a subset of the deficiencies I outlined in the 1st link.

Alphare marked an inline comment as done.Jan 28 2021, 10:02 AM
In D9843#149373, @indygreg wrote:

I'm not going to review this right now, but I have prior art at https://www.mercurial-scm.org/pipermail/mercurial-devel/2017-February/093657.html and https://www.mercurial-scm.org/pipermail/mercurial-devel/2017-May/097960.html that might be worth a read. I believe the wiki page on this format only contains a subset of the deficiencies I outlined in the 1st link.

Thanks for pasting these links. I'll look at them pretty soon, and we'll definitely have to account for whatever deficiencies I haven't covered in the plan page before we actually settle on a format.

This patch series is still valid for the short-term because it enables work around side-data and copytracing that would not be possible without a new format.

baymax updated this revision to Diff 25603.Feb 12 2021, 7:46 AM

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

baymax updated this revision to Diff 25615.Feb 12 2021, 6:58 PM

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

baymax updated this revision to Diff 25664.Feb 19 2021, 6:12 AM

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

durin42 added a subscriber: durin42.Feb 24 2021, 11:17 AM
durin42 added inline comments.
mercurial/revlogutils/constants.py
17

Was this change intentional? Don't we want to _not_ use 2 for this version until the format is locked down?

marmoute added inline comments.Feb 24 2021, 11:20 AM
mercurial/revlogutils/constants.py
17

+1 on Augie comment

durin42 requested changes to this revision.Feb 24 2021, 11:21 AM

(marking as request changes in that case)

This revision now requires changes to proceed.Feb 24 2021, 11:21 AM
baymax updated this revision to Diff 25964.Feb 25 2021, 11:45 AM

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

Alphare added inline comments.Feb 25 2021, 11:45 AM
mercurial/revlogutils/constants.py
17

Right, updated.

baymax updated this revision to Diff 26000.Mar 1 2021, 12:11 PM

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

marmoute requested changes to this revision.Mar 2 2021, 11:25 AM
marmoute added inline comments.
mercurial/pure/parsers.py
239–245

I don't think the meaning of these are documented anywhere, it would be nice to use the fact you know what they mean to document them.

mercurial/revlog.py
383

should the constant be factored beetween the previous file and this one ?

like indexformatv2 = struct.Struct(pureparser.Index2Mixin.index_format) in this case, the documentation would move to the pureparser module.

tests/test-revlog.t
25–28

Should this be in an independant changeset ? Should we bump it to something much hight than (3) to avoid the same problem in the next iteration ?

This revision now requires changes to proceed.Mar 2 2021, 11:25 AM
Alphare marked 2 inline comments as done.Mar 4 2021, 3:32 AM
Alphare edited parent revisions, added: D10109: requirements: also add a fncache constant; removed: D9903: revlog: prepare pure parser for being overloaded.
Alphare updated this revision to Diff 26046.
Alphare added inline comments.Mar 4 2021, 3:34 AM
tests/test-revlog.t
25–28

I don't think this is worth another changeset, but I can definitely use a better value.

Alphare updated this revision to Diff 26084.Mar 4 2021, 10:11 AM
marmoute accepted this revision.Mar 9 2021, 10:43 AM

Thanks for the fix.

baymax updated this revision to Diff 26215.Mar 10 2021, 2:10 PM

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

Alphare added a commit: rHG913485776542: revlog: introduce v2 format.Mar 15 2021, 2:29 PM
This revision was not accepted when it landed; it landed in state Needs Review.
Closed by commit rHG913485776542: revlog: introduce v2 format (authored by Alphare). · Explain Why
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

Diff 25347

mercurial/pure/parsers.py

return int(q & 0xFFFF) return int(q & 0xFFFF)
def offset_type(offset, type): def offset_type(offset, type):
return int(int(offset) << 16 | type) return int(int(offset) << 16 | type)
class BaseIndexObject(object): class BaseIndexObject(object):
index_format = b">Qiiiiii20s12x" index_format = b">Qiiiiii20s12x"
pulkitUnsubmitted
Done

IIUC, this change can also be a separate patch.

pulkit: IIUC, this change can also be a separate patch.
big_int_size = struct.calcsize(b'Q') big_int_size = struct.calcsize(b'Q')
int_size = struct.calcsize(b'i') int_size = struct.calcsize(b'i')
index_size = struct.calcsize(index_format) index_size = struct.calcsize(index_format)
null_item = (0, 0, 0, -1, -1, -1, -1, nullid) null_item = (0, 0, 0, -1, -1, -1, -1, nullid)
@property @property
def nodemap(self): def nodemap(self):
msg = b"index.nodemap is deprecated, use index.[has_node|rev|get_rev]" msg = b"index.nodemap is deprecated, use index.[has_node|rev|get_rev]"
self._extra = [] self._extra = []
else: else:
self._extra = self._extra[: i - self._lgt] self._extra = self._extra[: i - self._lgt]
def _calculate_index(self, i): def _calculate_index(self, i):
return self._offsets[i] return self._offsets[i]
def parse_index2(data, inline): def parse_index2(data, inline, revlogv2=False):
if not inline: if not inline:
return IndexObject(data), None cls = IndexObject2 if revlogv2 else IndexObject
return InlinedIndexObject(data, inline), (0, data) return cls(data), None
cls = InlinedIndexObject2 if revlogv2 else InlinedIndexObject
return cls(data, inline), (0, data)
class Index2Mixin(object):
index_format = b">Qiiiiii20s12xQiQi8x"
bit_int_size = struct.calcsize(b'Q')
int_size = struct.calcsize(b'i')
index_size = struct.calcsize(index_format)
assert index_size == 96, index_size
null_item = (0, 0, 0, -1, -1, -1, -1, nullid, 0, 0, 0, 0, 0)
marmouteUnsubmitted
Done

I don't think the meaning of these are documented anywhere, it would be nice to use the fact you know what they mean to document them.

marmoute: I don't think the meaning of these are documented anywhere, it would be nice to use the fact…
class IndexObject2(Index2Mixin, IndexObject):
pass
class InlinedIndexObject2(Index2Mixin, InlinedIndexObject):
def _inline_scan(self, lgt):
sidedata_length_pos = 84
off = 0
if lgt is not None:
self._offsets = [0] * lgt
count = 0
while off <= len(self._data) - self.index_size:
start = off + self.bit_int_size
(data_size,) = struct.unpack(
b'>i',
self._data[start : start + self.int_size],
)
start = off + sidedata_length_pos
(side_data_size,) = struct.unpack(
b'>i', self._data[start : start + self.int_size]
)
if lgt is not None:
self._offsets[count] = off
count += 1
off += self.index_size + data_size + side_data_size
if off != len(self._data):
raise ValueError(b"corrupted data")
return count
def parse_index_devel_nodemap(data, inline): def parse_index_devel_nodemap(data, inline):
"""like parse_index2, but alway return a PersistentNodeMapIndexObject""" """like parse_index2, but alway return a PersistentNodeMapIndexObject"""
return PersistentNodeMapIndexObject(data), None return PersistentNodeMapIndexObject(data), None
def parse_dirstate(dmap, copymap, st): def parse_dirstate(dmap, copymap, st):

mercurial/requirements.py

# of stripping them # of stripping them
INTERNAL_PHASE_REQUIREMENT = b'internal-phase' INTERNAL_PHASE_REQUIREMENT = b'internal-phase'
# Stores manifest in Tree structure # Stores manifest in Tree structure
TREEMANIFEST_REQUIREMENT = b'treemanifest' TREEMANIFEST_REQUIREMENT = b'treemanifest'
# Increment the sub-version when the revlog v2 format changes to lock out old # Increment the sub-version when the revlog v2 format changes to lock out old
# clients. # clients.
REVLOGV2_REQUIREMENT = b'exp-revlogv2.1' REVLOGV2_REQUIREMENT = b'exp-revlogv2.2'
# A repository with the sparserevlog feature will have delta chains that # A repository with the sparserevlog feature will have delta chains that
# can spread over a larger span. Sparse reading cuts these large spans into # can spread over a larger span. Sparse reading cuts these large spans into
# pieces, so that each piece isn't too big. # pieces, so that each piece isn't too big.
# Without the sparserevlog capability, reading from the repository could use # Without the sparserevlog capability, reading from the repository could use
# huge amounts of memory, because the whole span would be read at once, # huge amounts of memory, because the whole span would be read at once,
# including all the intermediate revisions that aren't pertinent for the chain. # including all the intermediate revisions that aren't pertinent for the chain.
# This is why once a repository has enabled sparse-read, it becomes required. # This is why once a repository has enabled sparse-read, it becomes required.

mercurial/revlog.py

dagop, dagop,
error, error,
mdiff, mdiff,
policy, policy,
pycompat, pycompat,
templatefilters, templatefilters,
util, util,
) )
from .pure import parsers as pureparsers
from .interfaces import ( from .interfaces import (
repository, repository,
util as interfaceutil, util as interfaceutil,
) )
from .revlogutils import ( from .revlogutils import (
deltas as deltautil, deltas as deltautil,
flagutil, flagutil,
nodemap as nodemaputil, nodemap as nodemaputil,
def packentry(self, entry, node, version, rev): def packentry(self, entry, node, version, rev):
p = indexformatng_pack(*entry) p = indexformatng_pack(*entry)
if rev == 0: if rev == 0:
p = versionformat_pack(version) + p[4:] p = versionformat_pack(version) + p[4:]
return p return p
# index v2:
# 6 bytes: offset
# 2 bytes: flags
# 4 bytes: compressed length
# 4 bytes: uncompressed length
# 4 bytes: base rev
# 4 bytes: link rev
# 4 bytes: parent 1 rev
# 4 bytes: parent 2 rev
# 32 bytes: nodeid
# 8 bytes: UnifiedRevlog identifier
# 4 bytes: rank (number of changesets under this one, this one included)
# 8 bytes: sidedata offset
# 4 bytes: sidedata compressed length
# 8 bytes: Padding to align to 96 bytes
indexformatv2 = struct.Struct(b">Qiiiiii20s12xQiQi8x")
marmouteUnsubmitted
Done

should the constant be factored beetween the previous file and this one ?

like indexformatv2 = struct.Struct(pureparser.Index2Mixin.index_format) in this case, the documentation would move to the pureparser module.

marmoute: should the constant be factored beetween the previous file and this one ? like `indexformatv2…
indexformatv2_pack = indexformatv2.pack
class revlogv2io(object):
def __init__(self):
self.size = indexformatv2.size
def parseindex(self, data, inline):
index, cache = parsers.parse_index2(data, inline, revlogv2=True)
return index, cache
def packentry(self, entry, node, version, rev):
p = indexformatv2_pack(*entry)
if rev == 0:
p = versionformat_pack(version) + p[4:]
return p
NodemapRevlogIO = None NodemapRevlogIO = None
if util.safehasattr(parsers, 'parse_index_devel_nodemap'): if util.safehasattr(parsers, 'parse_index_devel_nodemap'):
class NodemapRevlogIO(revlogio): class NodemapRevlogIO(revlogio):
"""A debug oriented IO class that return a PersistentNodeMapIndexObject """A debug oriented IO class that return a PersistentNodeMapIndexObject
The PersistentNodeMapIndexObject object is meant to test the persistent nodemap feature. The PersistentNodeMapIndexObject object is meant to test the persistent nodemap feature.
if self.nodemap_file is not None: if self.nodemap_file is not None:
use_rust_index = True use_rust_index = True
else: else:
use_rust_index = self.opener.options.get(b'rust.index') use_rust_index = self.opener.options.get(b'rust.index')
self._io = revlogio() self._io = revlogio()
if self.version == REVLOGV0: if self.version == REVLOGV0:
self._io = revlogoldio() self._io = revlogoldio()
elif fmt == REVLOGV2:
self._io = revlogv2io()
elif devel_nodemap: elif devel_nodemap:
self._io = NodemapRevlogIO() self._io = NodemapRevlogIO()
elif use_rust_index: elif use_rust_index:
self._io = rustrevlogio() self._io = rustrevlogio()
try: try:
d = self._io.parseindex(indexdata, self._inline) d = self._io.parseindex(indexdata, self._inline)
index, _chunkcache = d index, _chunkcache = d
use_nodemap = ( use_nodemap = (
offset_type(offset, flags), offset_type(offset, flags),
deltainfo.deltalen, deltainfo.deltalen,
textlen, textlen,
deltainfo.base, deltainfo.base,
link, link,
p1r, p1r,
p2r, p2r,
node, node,
0,
0,
0,
0,
) )
if self.version & 0xFFFF != REVLOGV2:
e = e[:8]
self.index.append(e) self.index.append(e)
entry = self._io.packentry(e, self.node, self.version, curr) entry = self._io.packentry(e, self.node, self.version, curr)
self._writeentry( self._writeentry(
transaction, ifh, dfh, entry, deltainfo.data, link, offset transaction, ifh, dfh, entry, deltainfo.data, link, offset
) )
rawtext = btext[0] rawtext = btext[0]

mercurial/revlogutils/constants.py

# revlogdeltas.py - constant used for revlog logic # revlogdeltas.py - constant used for revlog logic
# #
# Copyright 2005-2007 Matt Mackall <mpm@selenic.com> # Copyright 2005-2007 Matt Mackall <mpm@selenic.com>
# Copyright 2018 Octobus <contact@octobus.net> # Copyright 2018 Octobus <contact@octobus.net>
# #
# This software may be used and distributed according to the terms of the # This software may be used and distributed according to the terms of the
# GNU General Public License version 2 or any later version. # GNU General Public License version 2 or any later version.
"""Helper class to compute deltas stored inside revlogs""" """Helper class to compute deltas stored inside revlogs"""
from __future__ import absolute_import from __future__ import absolute_import
from ..interfaces import repository from ..interfaces import repository
# revlog header flags # revlog header flags
REVLOGV0 = 0 REVLOGV0 = 0
REVLOGV1 = 1 REVLOGV1 = 1
# Dummy value until file format is finalized. REVLOGV2 = 2
durin42Unsubmitted
Not Done

Was this change intentional? Don't we want to _not_ use 2 for this version until the format is locked down?

durin42: Was this change intentional? Don't we want to _not_ use 2 for this version until the format is…
marmouteUnsubmitted
Not Done

+1 on Augie comment

marmoute: +1 on Augie comment
AlphareAuthorUnsubmitted
Done

Right, updated.

Alphare: Right, updated.
# Reminder: change the bounds check in revlog.__init__ when this is changed.
REVLOGV2 = 0xDEAD
# Shared across v1 and v2. # Shared across v1 and v2.
FLAG_INLINE_DATA = 1 << 16 FLAG_INLINE_DATA = 1 << 16
# Only used by v1, implied by v2. # Only used by v1, implied by v2.
FLAG_GENERALDELTA = 1 << 17 FLAG_GENERALDELTA = 1 << 17
REVLOG_DEFAULT_FLAGS = FLAG_INLINE_DATA REVLOG_DEFAULT_FLAGS = FLAG_INLINE_DATA
REVLOG_DEFAULT_FORMAT = REVLOGV1 REVLOG_DEFAULT_FORMAT = REVLOGV1
REVLOG_DEFAULT_VERSION = REVLOG_DEFAULT_FORMAT | REVLOG_DEFAULT_FLAGS REVLOG_DEFAULT_VERSION = REVLOG_DEFAULT_FORMAT | REVLOG_DEFAULT_FLAGS
REVLOGV1_FLAGS = FLAG_INLINE_DATA | FLAG_GENERALDELTA REVLOGV1_FLAGS = FLAG_INLINE_DATA | FLAG_GENERALDELTA

tests/test-parseindex2.py

b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x01F' b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x01F'
b'\x13\x00\x00\x00\x00\x01\xec\x00\x00\x03\x06\x00\x00\x00\x01' b'\x13\x00\x00\x00\x00\x01\xec\x00\x00\x03\x06\x00\x00\x00\x01'
b'\x00\x00\x00\x03\x00\x00\x00\x02\xff\xff\xff\xff\x12\xcb\xeby1' b'\x00\x00\x00\x03\x00\x00\x00\x02\xff\xff\xff\xff\x12\xcb\xeby1'
b'\xb6\r\x98B\xcb\x07\xbd`\x8f\x92\xd9\xc4\x84\xbdK\x00\x00\x00' b'\xb6\r\x98B\xcb\x07\xbd`\x8f\x92\xd9\xc4\x84\xbdK\x00\x00\x00'
b'\x00\x00\x00\x00\x00\x00\x00\x00\x00' b'\x00\x00\x00\x00\x00\x00\x00\x00\x00'
) )
def parse_index2(data, inline): def parse_index2(data, inline, revlogv2=False):
index, chunkcache = parsers.parse_index2(data, inline) index, chunkcache = parsers.parse_index2(data, inline, revlogv2=revlogv2)
return list(index), chunkcache return list(index), chunkcache
def importparsers(hexversion): def importparsers(hexversion):
"""Import mercurial.parsers with the given sys.hexversion.""" """Import mercurial.parsers with the given sys.hexversion."""
# The file parsers.c inspects sys.hexversion to determine the version # The file parsers.c inspects sys.hexversion to determine the version
# of the currently-running Python interpreter, so we monkey-patch # of the currently-running Python interpreter, so we monkey-patch
# sys.hexversion to simulate using different versions. # sys.hexversion to simulate using different versions.

tests/test-revlog-v2.t

> [experimental] > [experimental]
> revlogv2 = enable-unstable-format-and-corrupt-my-data > revlogv2 = enable-unstable-format-and-corrupt-my-data
> EOF > EOF
$ hg init empty-repo $ hg init empty-repo
$ cd empty-repo $ cd empty-repo
$ cat .hg/requires $ cat .hg/requires
dotencode dotencode
exp-revlogv2.1 exp-revlogv2.2
fncache fncache
sparserevlog sparserevlog
store store
$ hg log $ hg log
Unknown flags to revlog are rejected Unknown flags to revlog are rejected
>>> with open('.hg/store/00changelog.i', 'wb') as fh: >>> with open('.hg/store/00changelog.i', 'wb') as fh:
... fh.write(b'\xff\x00\xde\xad') and None ... fh.write(b'\xff\x00\x00\x02') and None
$ hg log $ hg log
abort: unknown flags (0xff00) in version 57005 revlog 00changelog.i abort: unknown flags (0xff00) in version 2 revlog 00changelog.i
[50] [50]
$ cd .. $ cd ..
Writing a simple revlog v2 works Writing a simple revlog v2 works
$ hg init simple $ hg init simple
$ cd simple $ cd simple
$ touch foo $ touch foo
$ hg -q commit -A -m initial $ hg -q commit -A -m initial
$ hg log $ hg log
changeset: 0:96ee1d7354c4 changeset: 0:96ee1d7354c4
tag: tip tag: tip
user: test user: test
date: Thu Jan 01 00:00:00 1970 +0000 date: Thu Jan 01 00:00:00 1970 +0000
summary: initial summary: initial
Header written as expected Header written as expected
$ f --hexdump --bytes 4 .hg/store/00changelog.i $ f --hexdump --bytes 4 .hg/store/00changelog.i
.hg/store/00changelog.i: .hg/store/00changelog.i:
0000: 00 01 de ad |....| 0000: 00 01 00 02 |....|
$ f --hexdump --bytes 4 .hg/store/data/foo.i $ f --hexdump --bytes 4 .hg/store/data/foo.i
.hg/store/data/foo.i: .hg/store/data/foo.i:
0000: 00 01 de ad |....| 0000: 00 01 00 02 |....|

tests/test-revlog.t

$ hg log $ hg log
abort: unknown flags (0x04) in version 1 revlog 00changelog.i abort: unknown flags (0x04) in version 1 revlog 00changelog.i
[50] [50]
Unknown version is rejected Unknown version is rejected
>>> with open('.hg/store/00changelog.i', 'wb') as fh: >>> with open('.hg/store/00changelog.i', 'wb') as fh:
... fh.write(b'\x00\x00\x00\x02') and None ... fh.write(b'\x00\x00\x00\x03') and None
$ hg log $ hg log
abort: unknown version (2) in revlog 00changelog.i abort: unknown version (3) in revlog 00changelog.i
marmouteUnsubmitted
Not Done

Should this be in an independant changeset ? Should we bump it to something much hight than (3) to avoid the same problem in the next iteration ?

marmoute: Should this be in an independant changeset ? Should we bump it to something much hight than (3)…
AlphareAuthorUnsubmitted
Done

I don't think this is worth another changeset, but I can definitely use a better value.

Alphare: I don't think this is worth another changeset, but I can definitely use a better value.
[50] [50]
$ cd .. $ cd ..
Test for CVE-2016-3630 Test for CVE-2016-3630
$ hg init $ hg init