| hg-reviewers |
Rewriting the full nodemap for each transaction has a cost we would like to
avoid. We introduce a new way to write persistent nodemap data by adding new
information at the end for file. Any new and updated block as added at the end
of the file. The last block is the new root node.
With this method, some of the block already on disk get "dereferenced" and
become dead data. In later changesets, We'll start tracking the amount of dead
data to eventually re-generate a full nodemap.
| Automatic diff as part of commit; lint not applicable. |
| Automatic diff as part of commit; unit tests not applicable. |
| tests/test-persistent-nodemap.t | ||
|---|---|---|
| 53 | Which patch introduced the C code? I have not looked at all patches yet, but I thought the idea was that this entire stack was just pure Python and then you'd add a Rust version (not C) in a separate series. | |
| tests/test-persistent-nodemap.t | ||
|---|---|---|
| 53 | There are no C code (and is non planned). This should be the C path or the cext policy. | |
| Path | Packages | |||
|---|---|---|---|---|
| M | mercurial/pure/parsers.py (20 lines) | |||
| M | mercurial/revlogutils/nodemap.py (86 lines) | |||
| M | tests/test-persistent-nodemap.t (11 lines) |
| Status | Author | Revision | |
|---|---|---|---|
| Closed | marmoute | ||
| Closed | marmoute | ||
| Closed | marmoute | ||
| Closed | marmoute | ||
| Closed | marmoute | ||
| Closed | marmoute | ||
| Closed | marmoute | ||
| Closed | marmoute | ||
| Closed | marmoute | ||
| Closed | marmoute | ||
| Closed | marmoute | ||
| Closed | marmoute | ||
| Closed | marmoute | ||
| Closed | marmoute | ||
| Closed | marmoute | ||
| Closed | marmoute | ||
| Closed | marmoute | ||
| Closed | marmoute | ||
| Closed | marmoute | ||
| Closed | marmoute | ||
| Closed | marmoute | ||
| Closed | marmoute | ||
| Closed | marmoute | ||
| Closed | marmoute | ||
| Closed | marmoute | ||
| Closed | marmoute |
| def nodemap_data_all(self): | def nodemap_data_all(self): | ||||
| """Return bytes containing a full serialization of a nodemap | """Return bytes containing a full serialization of a nodemap | ||||
| The nodemap should be valid for the full set of revisions in the | The nodemap should be valid for the full set of revisions in the | ||||
| index.""" | index.""" | ||||
| return nodemaputil.persistent_data(self) | return nodemaputil.persistent_data(self) | ||||
| def nodemap_data_incremental(self): | |||||
| """Return bytes containing a incremental update to persistent nodemap | |||||
| This containst the data for an append-only update of the data provided | |||||
| in the last call to `update_nodemap_data`. | |||||
| """ | |||||
| if self._nm_root is None: | |||||
| return None | |||||
| data = nodemaputil.update_persistent_data( | |||||
| self, self._nm_root, self._nm_max_idx, self._nm_rev | |||||
| ) | |||||
| self._nm_root = self._nm_max_idx = self._nm_rev = None | |||||
| return data | |||||
| def update_nodemap_data(self, nm_data): | def update_nodemap_data(self, nm_data): | ||||
| """provide full blokc of persisted binary data for a nodemap | """provide full blokc of persisted binary data for a nodemap | ||||
| The data are expected to come from disk. See `nodemap_data_all` for a | The data are expected to come from disk. See `nodemap_data_all` for a | ||||
| produceur of such data.""" | produceur of such data.""" | ||||
| if nm_data is not None: | if nm_data is not None: | ||||
| nodemaputil.parse_data(nm_data) | self._nm_root, self._nm_max_idx = nodemaputil.parse_data(nm_data) | ||||
| if self._nm_root: | |||||
| self._nm_rev = len(self) - 1 | |||||
| else: | |||||
| self._nm_root = self._nm_max_idx = self._nm_rev = None | |||||
| class InlinedIndexObject(BaseIndexObject): | class InlinedIndexObject(BaseIndexObject): | ||||
| def __init__(self, data, inline=0): | def __init__(self, data, inline=0): | ||||
| self._data = data | self._data = data | ||||
| self._lgt = self._inline_scan(None) | self._lgt = self._inline_scan(None) | ||||
| self._inline_scan(self._lgt) | self._inline_scan(self._lgt) | ||||
| self._extra = [] | self._extra = [] | ||||
| """ | """ | ||||
| if getattr(revlog, 'filteredrevs', ()): | if getattr(revlog, 'filteredrevs', ()): | ||||
| raise error.ProgrammingError( | raise error.ProgrammingError( | ||||
| "cannot persist nodemap of a filtered changelog" | "cannot persist nodemap of a filtered changelog" | ||||
| ) | ) | ||||
| if revlog.nodemap_file is None: | if revlog.nodemap_file is None: | ||||
| msg = "calling persist nodemap on a revlog without the feature enableb" | msg = "calling persist nodemap on a revlog without the feature enableb" | ||||
| raise error.ProgrammingError(msg) | raise error.ProgrammingError(msg) | ||||
| can_incremental = util.safehasattr(revlog.index, "nodemap_data_incremental") | |||||
| ondisk_docket = revlog._nodemap_docket | |||||
| # first attemp an incremental update of the data | |||||
| if can_incremental and ondisk_docket is not None: | |||||
| target_docket = revlog._nodemap_docket.copy() | |||||
| data = revlog.index.nodemap_data_incremental() | |||||
| datafile = _rawdata_filepath(revlog, target_docket) | |||||
| # EXP-TODO: if this is a cache, this should use a cache vfs, not a | |||||
| # store vfs | |||||
| with revlog.opener(datafile, b'a') as fd: | |||||
| fd.write(data) | |||||
| else: | |||||
| # otherwise fallback to a full new export | |||||
| target_docket = NodeMapDocket() | |||||
| datafile = _rawdata_filepath(revlog, target_docket) | |||||
| if util.safehasattr(revlog.index, "nodemap_data_all"): | if util.safehasattr(revlog.index, "nodemap_data_all"): | ||||
| data = revlog.index.nodemap_data_all() | data = revlog.index.nodemap_data_all() | ||||
| else: | else: | ||||
| data = persistent_data(revlog.index) | data = persistent_data(revlog.index) | ||||
| target_docket = NodeMapDocket() | |||||
| datafile = _rawdata_filepath(revlog, target_docket) | |||||
| olds = _other_rawdata_filepath(revlog, target_docket) | |||||
| if olds: | |||||
| realvfs = getattr(revlog, '_realopener', revlog.opener) | |||||
| def cleanup(tr): | |||||
| for oldfile in olds: | |||||
| realvfs.tryunlink(oldfile) | |||||
| callback_id = b"revlog-cleanup-nodemap-%s" % revlog.nodemap_file | |||||
| tr.addpostclose(callback_id, cleanup) | |||||
| # EXP-TODO: if this is a cache, this should use a cache vfs, not a | # EXP-TODO: if this is a cache, this should use a cache vfs, not a | ||||
| # store vfs | # store vfs | ||||
| with revlog.opener(datafile, b'w') as fd: | with revlog.opener(datafile, b'w') as fd: | ||||
| fd.write(data) | fd.write(data) | ||||
| # EXP-TODO: if this is a cache, this should use a cache vfs, not a | # EXP-TODO: if this is a cache, this should use a cache vfs, not a | ||||
| # store vfs | # store vfs | ||||
| with revlog.opener(revlog.nodemap_file, b'w', atomictemp=True) as fp: | with revlog.opener(revlog.nodemap_file, b'w', atomictemp=True) as fp: | ||||
| fp.write(target_docket.serialize()) | fp.write(target_docket.serialize()) | ||||
| revlog._nodemap_docket = target_docket | revlog._nodemap_docket = target_docket | ||||
| # EXP-TODO: if the transaction abort, we should remove the new data and | # EXP-TODO: if the transaction abort, we should remove the new data and | ||||
| # reinstall the old one. | # reinstall the old one. | ||||
| # search for old index file in all cases, some older process might have | |||||
| # left one behind. | |||||
| olds = _other_rawdata_filepath(revlog, target_docket) | |||||
| if olds: | |||||
| realvfs = getattr(revlog, '_realopener', revlog.opener) | |||||
| def cleanup(tr): | |||||
| for oldfile in olds: | |||||
| realvfs.tryunlink(oldfile) | |||||
| callback_id = b"revlog-cleanup-nodemap-%s" % revlog.nodemap_file | |||||
| tr.addpostclose(callback_id, cleanup) | |||||
| ### Nodemap docket file | ### Nodemap docket file | ||||
| # | # | ||||
| # The nodemap data are stored on disk using 2 files: | # The nodemap data are stored on disk using 2 files: | ||||
| # | # | ||||
| # * a raw data files containing a persistent nodemap | # * a raw data files containing a persistent nodemap | ||||
| # (see `Nodemap Trie` section) | # (see `Nodemap Trie` section) | ||||
| # | # | ||||
| def persistent_data(index): | def persistent_data(index): | ||||
| """return the persistent binary form for a nodemap for a given index | """return the persistent binary form for a nodemap for a given index | ||||
| """ | """ | ||||
| trie = _build_trie(index) | trie = _build_trie(index) | ||||
| return _persist_trie(trie) | return _persist_trie(trie) | ||||
| def update_persistent_data(index, root, max_idx, last_rev): | |||||
| """return the incremental update for persistent nodemap from a given index | |||||
| """ | |||||
| trie = _update_trie(index, root, last_rev) | |||||
| return _persist_trie(trie, existing_idx=max_idx) | |||||
| S_BLOCK = struct.Struct(">" + ("l" * 16)) | S_BLOCK = struct.Struct(">" + ("l" * 16)) | ||||
| NO_ENTRY = -1 | NO_ENTRY = -1 | ||||
| # rev 0 need to be -2 because 0 is used by block, -1 is a special value. | # rev 0 need to be -2 because 0 is used by block, -1 is a special value. | ||||
| REV_OFFSET = 2 | REV_OFFSET = 2 | ||||
| def _transform_rev(rev): | def _transform_rev(rev): | ||||
| """ | """ | ||||
| root = Block() | root = Block() | ||||
| for rev in range(len(index)): | for rev in range(len(index)): | ||||
| hex = nodemod.hex(index[rev][7]) | hex = nodemod.hex(index[rev][7]) | ||||
| _insert_into_block(index, 0, root, rev, hex) | _insert_into_block(index, 0, root, rev, hex) | ||||
| return root | return root | ||||
| def _update_trie(index, root, last_rev): | |||||
| """consume""" | |||||
| for rev in range(last_rev + 1, len(index)): | |||||
| hex = nodemod.hex(index[rev][7]) | |||||
| _insert_into_block(index, 0, root, rev, hex) | |||||
| return root | |||||
| def _insert_into_block(index, level, block, current_rev, current_hex): | def _insert_into_block(index, level, block, current_rev, current_hex): | ||||
| """insert a new revision in a block | """insert a new revision in a block | ||||
| index: the index we are adding revision for | index: the index we are adding revision for | ||||
| level: the depth of the current block in the trie | level: the depth of the current block in the trie | ||||
| block: the block currently being considered | block: the block currently being considered | ||||
| current_rev: the revision number we are adding | current_rev: the revision number we are adding | ||||
| current_hex: the hexadecimal representation of the of that revision | current_hex: the hexadecimal representation of the of that revision | ||||
| """ | """ | ||||
| if block.ondisk_id is not None: | |||||
| block.ondisk_id = None | |||||
| hex_digit = _to_int(current_hex[level : level + 1]) | hex_digit = _to_int(current_hex[level : level + 1]) | ||||
| entry = block.get(hex_digit) | entry = block.get(hex_digit) | ||||
| if entry is None: | if entry is None: | ||||
| # no entry, simply store the revision number | # no entry, simply store the revision number | ||||
| block[hex_digit] = current_rev | block[hex_digit] = current_rev | ||||
| elif isinstance(entry, dict): | elif isinstance(entry, dict): | ||||
| # need to recurse to an underlying block | # need to recurse to an underlying block | ||||
| _insert_into_block(index, level + 1, entry, current_rev, current_hex) | _insert_into_block(index, level + 1, entry, current_rev, current_hex) | ||||
| else: | else: | ||||
| # collision with a previously unique prefix, inserting new | # collision with a previously unique prefix, inserting new | ||||
| # vertices to fit both entry. | # vertices to fit both entry. | ||||
| other_hex = nodemod.hex(index[entry][7]) | other_hex = nodemod.hex(index[entry][7]) | ||||
| other_rev = entry | other_rev = entry | ||||
| new = Block() | new = Block() | ||||
| block[hex_digit] = new | block[hex_digit] = new | ||||
| _insert_into_block(index, level + 1, new, other_rev, other_hex) | _insert_into_block(index, level + 1, new, other_rev, other_hex) | ||||
| _insert_into_block(index, level + 1, new, current_rev, current_hex) | _insert_into_block(index, level + 1, new, current_rev, current_hex) | ||||
| def _persist_trie(root): | def _persist_trie(root, existing_idx=None): | ||||
| """turn a nodemap trie into persistent binary data | """turn a nodemap trie into persistent binary data | ||||
| See `_build_trie` for nodemap trie structure""" | See `_build_trie` for nodemap trie structure""" | ||||
| block_map = {} | block_map = {} | ||||
| if existing_idx is not None: | |||||
| base_idx = existing_idx + 1 | |||||
| else: | |||||
| base_idx = 0 | |||||
| chunks = [] | chunks = [] | ||||
| for tn in _walk_trie(root): | for tn in _walk_trie(root): | ||||
| block_map[id(tn)] = len(chunks) | if tn.ondisk_id is not None: | ||||
| block_map[id(tn)] = tn.ondisk_id | |||||
| else: | |||||
| block_map[id(tn)] = len(chunks) + base_idx | |||||
| chunks.append(_persist_block(tn, block_map)) | chunks.append(_persist_block(tn, block_map)) | ||||
| return b''.join(chunks) | return b''.join(chunks) | ||||
| def _walk_trie(block): | def _walk_trie(block): | ||||
| """yield all the block in a trie | """yield all the block in a trie | ||||
| Children blocks are always yield before their parent block. | Children blocks are always yield before their parent block. | ||||
| """ | """ | ||||
| def parse_data(data): | def parse_data(data): | ||||
| """parse parse nodemap data into a nodemap Trie""" | """parse parse nodemap data into a nodemap Trie""" | ||||
| if (len(data) % S_BLOCK.size) != 0: | if (len(data) % S_BLOCK.size) != 0: | ||||
| msg = "nodemap data size is not a multiple of block size (%d): %d" | msg = "nodemap data size is not a multiple of block size (%d): %d" | ||||
| raise error.Abort(msg % (S_BLOCK.size, len(data))) | raise error.Abort(msg % (S_BLOCK.size, len(data))) | ||||
| if not data: | if not data: | ||||
| return Block() | return Block(), None | ||||
| block_map = {} | block_map = {} | ||||
| new_blocks = [] | new_blocks = [] | ||||
| for i in range(0, len(data), S_BLOCK.size): | for i in range(0, len(data), S_BLOCK.size): | ||||
| block = Block() | block = Block() | ||||
| block.ondisk_id = len(block_map) | block.ondisk_id = len(block_map) | ||||
| block_map[block.ondisk_id] = block | block_map[block.ondisk_id] = block | ||||
| block_data = data[i : i + S_BLOCK.size] | block_data = data[i : i + S_BLOCK.size] | ||||
| values = S_BLOCK.unpack(block_data) | values = S_BLOCK.unpack(block_data) | ||||
| new_blocks.append((block, values)) | new_blocks.append((block, values)) | ||||
| for b, values in new_blocks: | for b, values in new_blocks: | ||||
| for idx, v in enumerate(values): | for idx, v in enumerate(values): | ||||
| if v == NO_ENTRY: | if v == NO_ENTRY: | ||||
| continue | continue | ||||
| elif v >= 0: | elif v >= 0: | ||||
| b[idx] = block_map[v] | b[idx] = block_map[v] | ||||
| else: | else: | ||||
| b[idx] = _transform_rev(v) | b[idx] = _transform_rev(v) | ||||
| return block | return block, i // S_BLOCK.size | ||||
| # debug utility | # debug utility | ||||
| def check_data(ui, index, data): | def check_data(ui, index, data): | ||||
| """verify that the provided nodemap data are valid for the given idex""" | """verify that the provided nodemap data are valid for the given idex""" | ||||
| ret = 0 | ret = 0 | ||||
| ui.status((b"revision in index: %d\n") % len(index)) | ui.status((b"revision in index: %d\n") % len(index)) | ||||
| root = parse_data(data) | root, __ = parse_data(data) | ||||
| all_revs = set(_all_revisions(root)) | all_revs = set(_all_revisions(root)) | ||||
| ui.status((b"revision in nodemap: %d\n") % len(all_revs)) | ui.status((b"revision in nodemap: %d\n") % len(all_revs)) | ||||
| for r in range(len(index)): | for r in range(len(index)): | ||||
| if r not in all_revs: | if r not in all_revs: | ||||
| msg = b" revision missing from nodemap: %d\n" % r | msg = b" revision missing from nodemap: %d\n" % r | ||||
| ui.write_err(msg) | ui.write_err(msg) | ||||
| ret = 1 | ret = 1 | ||||
| else: | else: | ||||
Which patch introduced the C code? I have not looked at all patches yet, but I thought the idea was that this entire stack was just pure Python and then you'd add a Rust version (not C) in a separate series.