( )⚙ D12170 dirstate-v2: fix infinite loop in pure packer

This is an archive of the discontinued Mercurial Phabricator instance.

Differential D12170

dirstate-v2: fix infinite loop in pure packer
ClosedPublic

Authored by Alphare on Feb 11 2022, 6:27 PM.

Details

Reviewers
SimonSapin
Group Reviewers
hg-reviewers
Commits
rHG46d12f7762e4: dirstate-v2: fix infinite loop in pure packer
Summary

Due to the naive approach to path relative-ness, some tree shapes
like the one introduced in the associated test could result in the
packer going into an endless loop which allocated new Node objects
endlessly until the process was killed by Linux's OOM killer.

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

Alphare created this revision.Feb 11 2022, 6:27 PM
SimonSapin accepted this revision.Feb 12 2022, 3:08 AM
Alphare added a commit: rHG46d12f7762e4: dirstate-v2: fix infinite loop in pure packer.Feb 15 2022, 10:17 AM
This revision was not accepted when it landed; it landed in state Needs Review.
Closed by commit rHG46d12f7762e4: dirstate-v2: fix infinite loop in pure packer (authored by Alphare). · Explain Why
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

Diff 32211

mercurial/dirstateutils/v2.py

stack.append(Node(path, entry, current_node)) stack.append(Node(path, entry, current_node))
should_pack = True should_pack = True
next_path = None next_path = None
if index < len(sorted_map): if index < len(sorted_map):
# Determine if the next entry is in the same sub-tree, if so don't # Determine if the next entry is in the same sub-tree, if so don't
# pack yet # pack yet
next_path = sorted_map[index][0] next_path = sorted_map[index][0]
should_pack = not get_folder(next_path).startswith(current_folder) should_pack = not is_ancestor(next_path, current_folder)
if should_pack: if should_pack:
pack_directory_children(current_node, copy_map, data, stack) pack_directory_children(current_node, copy_map, data, stack)
while stack and current_node.path != b"": while stack and current_node.path != b"":
# Go up the tree and write until we reach the folder of the next # Go up the tree and write until we reach the folder of the next
# entry (if any, otherwise the root) # entry (if any, otherwise the root)
parent = current_node.parent parent = current_node.parent
in_parent_folder_of_next_entry = next_path is not None and ( in_ancestor_of_next_path = next_path is not None and (
get_folder(next_path).startswith(get_folder(stack[-1].path)) is_ancestor(next_path, get_folder(stack[-1].path))
) )
if parent is None or in_parent_folder_of_next_entry: if parent is None or in_ancestor_of_next_path:
break break
pack_directory_children(parent, copy_map, data, stack) pack_directory_children(parent, copy_map, data, stack)
current_node = parent current_node = parent
# Special case for the root node since we don't write it to disk, only its # Special case for the root node since we don't write it to disk, only its
# children to the docket # children to the docket
current_node = stack.pop() current_node = stack.pop()
assert current_node.path == b"", current_node.path assert current_node.path == b"", current_node.path
def get_folder(path): def get_folder(path):
""" """
Return the folder of the path that's given, an empty string for root paths. Return the folder of the path that's given, an empty string for root paths.
""" """
return path.rsplit(b'/', 1)[0] if b'/' in path else b'' return path.rsplit(b'/', 1)[0] if b'/' in path else b''
def is_ancestor(path, maybe_ancestor):
"""Returns whether `maybe_ancestor` is an ancestor of `path`.
>>> is_ancestor(b"a", b"")
True
>>> is_ancestor(b"a/b/c", b"a/b/c")
False
>>> is_ancestor(b"hgext3rd/__init__.py", b"hgext")
False
>>> is_ancestor(b"hgext3rd/__init__.py", b"hgext3rd")
True
"""
if maybe_ancestor == b"":
return True
if path <= maybe_ancestor:
return False
path_components = path.split(b"/")
ancestor_components = maybe_ancestor.split(b"/")
return all(c == o for c, o in zip(path_components, ancestor_components))
def move_to_correct_node_in_tree(target_folder, current_node, stack): def move_to_correct_node_in_tree(target_folder, current_node, stack):
""" """
Move inside the dirstate node tree to the node corresponding to Move inside the dirstate node tree to the node corresponding to
`target_folder`, creating the missing nodes along the way if needed. `target_folder`, creating the missing nodes along the way if needed.
""" """
while target_folder != current_node.path: while target_folder != current_node.path:
if target_folder.startswith(current_node.path): if is_ancestor(target_folder, current_node.path):
# We need to go down a folder # We need to go down a folder
prefix = target_folder[len(current_node.path) :].lstrip(b'/') prefix = target_folder[len(current_node.path) :].lstrip(b'/')
subfolder_name = prefix.split(b'/', 1)[0] subfolder_name = prefix.split(b'/', 1)[0]
if current_node.path: if current_node.path:
subfolder_path = current_node.path + b'/' + subfolder_name subfolder_path = current_node.path + b'/' + subfolder_name
else: else:
subfolder_path = subfolder_name subfolder_path = subfolder_name
next_node = stack[-1] next_node = stack[-1]

tests/test-dirstate.t

$ echo "dirstateex=../dirstateexception.py" >> .hg/hgrc $ echo "dirstateex=../dirstateexception.py" >> .hg/hgrc
$ hg up 0 $ hg up 0
abort: simulated error while recording dirstateupdates abort: simulated error while recording dirstateupdates
[255] [255]
$ hg log -r . -T '{rev}\n' $ hg log -r . -T '{rev}\n'
1 1
$ hg status $ hg status
? a ? a
#if dirstate-v2
Check that folders that are prefixes of others do not throw the packer into an
infinite loop.
$ cd ..
$ hg init infinite-loop
$ cd infinite-loop
$ mkdir hgext3rd hgext
$ touch hgext3rd/__init__.py hgext/zeroconf.py
$ hg commit -Aqm0
$ hg st -c
C hgext/zeroconf.py
C hgext3rd/__init__.py
$ cd ..
#endif

tests/test-doctest.py

('hgext.convert.p4', '{}'), ('hgext.convert.p4', '{}'),
('hgext.convert.subversion', '{}'), ('hgext.convert.subversion', '{}'),
('hgext.fix', '{}'), ('hgext.fix', '{}'),
('hgext.mq', '{}'), ('hgext.mq', '{}'),
('mercurial.changelog', '{}'), ('mercurial.changelog', '{}'),
('mercurial.cmdutil', '{}'), ('mercurial.cmdutil', '{}'),
('mercurial.color', '{}'), ('mercurial.color', '{}'),
('mercurial.dagparser', "{'optionflags': 4}"), ('mercurial.dagparser', "{'optionflags': 4}"),
('mercurial.dirstateutils.v2', '{}'),
('mercurial.encoding', '{}'), ('mercurial.encoding', '{}'),
('mercurial.fancyopts', '{}'), ('mercurial.fancyopts', '{}'),
('mercurial.formatter', '{}'), ('mercurial.formatter', '{}'),
('mercurial.hg', '{}'), ('mercurial.hg', '{}'),
('mercurial.hgweb.hgwebdir_mod', '{}'), ('mercurial.hgweb.hgwebdir_mod', '{}'),
('mercurial.match', '{}'), ('mercurial.match', '{}'),
('mercurial.mdiff', '{}'), ('mercurial.mdiff', '{}'),
('mercurial.minirst', '{}'), ('mercurial.minirst', '{}'),