1
# Copyright (C) 2008-2011 Canonical Ltd
1
# Copyright (C) 2008, 2009 Canonical Ltd
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
43
42
from bzrlib import lazy_import
44
43
lazy_import.lazy_import(globals(), """
45
44
from bzrlib import (
49
49
from bzrlib import (
57
from bzrlib.static_tuple import StaticTuple
60
57
# If each line is 50 bytes, and you have 255 internal pages, with 255-way fan
61
58
# out, it takes 3.1MB to cache the layer.
62
59
_PAGE_CACHE_SIZE = 4*1024*1024
63
# Per thread caches for 2 reasons:
64
# - in the server we may be serving very different content, so we get less
66
# - we avoid locking on every cache lookup.
67
_thread_caches = threading.local()
69
_thread_caches.page_cache = None
72
"""Get the per-thread page cache.
74
We need a function to do this because in a new thread the _thread_caches
75
threading.local object does not have the cache initialized yet.
77
page_cache = getattr(_thread_caches, 'page_cache', None)
78
if page_cache is None:
79
# We are caching bytes so len(value) is perfectly accurate
80
page_cache = lru_cache.LRUSizeCache(_PAGE_CACHE_SIZE)
81
_thread_caches.page_cache = page_cache
60
# We are caching bytes so len(value) is perfectly accurate
61
_page_cache = lru_cache.LRUSizeCache(_PAGE_CACHE_SIZE)
89
66
# If a ChildNode falls below this many bytes, we check for a remap
90
67
_INTERESTING_NEW_SIZE = 50
91
68
# If a ChildNode shrinks by more than this amount, we check for a remap
92
69
_INTERESTING_SHRINKAGE_LIMIT = 20
70
# If we delete more than this many nodes applying a delta, we check for a remap
71
_INTERESTING_DELETES_LIMIT = 5
95
74
def _search_key_plain(key):
104
83
class CHKMap(object):
105
84
"""A persistent map from string to string backed by a CHK store."""
107
__slots__ = ('_store', '_root_node', '_search_key_func')
109
86
def __init__(self, store, root_key, search_key_func=None):
110
87
"""Create a CHKMap object.
133
110
into the map; if old_key is not None, then the old mapping
134
111
of old_key is removed.
137
114
# Check preconditions first.
138
as_st = StaticTuple.from_sequence
139
new_items = set([as_st(key) for (old, key, value) in delta
140
if key is not None and old is None])
115
new_items = set([key for (old, key, value) in delta if key is not None
141
117
existing_new = list(self.iteritems(key_filter=new_items))
143
119
raise errors.InconsistentDeltaDelta(delta,
146
122
for old, new, value in delta:
147
123
if old is not None and old != new:
148
124
self.unmap(old, check_remap=False)
150
126
for old, new, value in delta:
151
127
if new is not None:
152
128
self.map(new, value)
129
if delete_count > _INTERESTING_DELETES_LIMIT:
130
trace.mutter("checking remap as %d deletions", delete_count)
154
131
self._check_remap()
155
132
return self._save()
157
134
def _ensure_root(self):
158
135
"""Ensure that the root node is an object not a key."""
159
if type(self._root_node) is StaticTuple:
136
if type(self._root_node) is tuple:
160
137
# Demand-load the root
161
138
self._root_node = self._get_node(self._root_node)
170
147
:param node: A tuple key or node object.
171
148
:return: A node object.
173
if type(node) is StaticTuple:
150
if type(node) is tuple:
174
151
bytes = self._read_bytes(node)
175
152
return _deserialise(bytes, node,
176
153
search_key_func=self._search_key_func)
180
157
def _read_bytes(self, key):
182
return _get_cache()[key]
159
return _page_cache[key]
184
161
stream = self._store.get_record_stream([key], 'unordered', True)
185
162
bytes = stream.next().get_bytes_as('fulltext')
186
_get_cache()[key] = bytes
163
_page_cache[key] = bytes
189
166
def _dump_tree(self, include_keys=False):
217
194
for key, value in sorted(node._items.iteritems()):
218
195
# Don't use prefix nor indent here to line up when used in
219
196
# tests in conjunction with assertEqualDiff
220
result.append(' %r %r' % (tuple(key), value))
197
result.append(' %r %r' % (key, value))
241
218
root_key = klass._create_directly(store, initial_value,
242
219
maximum_size=maximum_size, key_width=key_width,
243
220
search_key_func=search_key_func)
244
if type(root_key) is not StaticTuple:
245
raise AssertionError('we got a %s instead of a StaticTuple'
264
238
node = LeafNode(search_key_func=search_key_func)
265
239
node.set_maximum_size(maximum_size)
266
240
node._key_width = key_width
267
as_st = StaticTuple.from_sequence
268
node._items = dict([(as_st(key), val) for key, val
269
in initial_value.iteritems()])
241
node._items = dict(initial_value)
270
242
node._raw_size = sum([node._key_value_len(key, value)
271
for key,value in node._items.iteritems()])
243
for key,value in initial_value.iteritems()])
272
244
node._len = len(node._items)
273
245
node._compute_search_prefix()
274
246
node._compute_serialised_prefix()
510
482
def iteritems(self, key_filter=None):
511
483
"""Iterate over the entire CHKMap's contents."""
512
484
self._ensure_root()
513
if key_filter is not None:
514
as_st = StaticTuple.from_sequence
515
key_filter = [as_st(key) for key in key_filter]
516
485
return self._root_node.iteritems(self._store, key_filter=key_filter)
519
488
"""Return the key for this map."""
520
if type(self._root_node) is StaticTuple:
489
if type(self._root_node) is tuple:
521
490
return self._root_node
523
492
return self._root_node._key
532
501
:param key: A key to map.
533
502
:param value: The value to assign to key.
535
key = StaticTuple.from_sequence(key)
536
504
# Need a root object.
537
505
self._ensure_root()
538
506
prefix, node_details = self._root_node.map(self._store, key, value)
549
517
def _node_key(self, node):
550
518
"""Get the key for a node whether it's a tuple or node."""
551
519
if type(node) is tuple:
552
node = StaticTuple.from_sequence(node)
553
if type(node) is StaticTuple:
558
524
def unmap(self, key, check_remap=True):
559
525
"""remove key from the map."""
560
key = StaticTuple.from_sequence(key)
561
526
self._ensure_root()
562
527
if type(self._root_node) is InternalNode:
563
528
unmapped = self._root_node.unmap(self._store, key,
570
535
"""Check if nodes can be collapsed."""
571
536
self._ensure_root()
572
537
if type(self._root_node) is InternalNode:
573
self._root_node = self._root_node._check_remap(self._store)
538
self._root_node._check_remap(self._store)
576
541
"""Save the map completely.
578
543
:return: The key of the root node.
580
if type(self._root_node) is StaticTuple:
545
if type(self._root_node) is tuple:
582
547
return self._root_node
583
548
keys = list(self._root_node.serialise(self._store))
591
556
adding the header bytes, and without prefix compression.
594
__slots__ = ('_key', '_len', '_maximum_size', '_key_width',
595
'_raw_size', '_items', '_search_prefix', '_search_key_func'
598
559
def __init__(self, key_width=1):
599
560
"""Create a node.
689
650
the key/value pairs.
692
__slots__ = ('_common_serialised_prefix',)
694
653
def __init__(self, search_key_func=None):
695
654
Node.__init__(self)
696
655
# All of the keys in this leaf node share this common prefix
697
656
self._common_serialised_prefix = None
657
self._serialise_key = '\x00'.join
698
658
if search_key_func is None:
699
659
self._search_key_func = _search_key_plain
738
698
:param bytes: The bytes of the node.
739
699
:param key: The key that the serialised node has.
741
key = static_tuple.expect_static_tuple(key)
742
701
return _deserialise_leaf_node(bytes, key,
743
702
search_key_func=search_key_func)
884
843
raise AssertionError('%r must be known' % self._search_prefix)
885
844
return self._search_prefix, [("", self)]
887
_serialise_key = '\x00'.join
889
846
def serialise(self, store):
890
847
"""Serialise the LeafNode to store.
916
873
lines.append(serialized[prefix_len:])
917
874
lines.extend(value_lines)
918
875
sha1, _, _ = store.add_lines((None,), (), lines)
919
self._key = StaticTuple("sha1:" + sha1,).intern()
876
self._key = ("sha1:" + sha1,)
920
877
bytes = ''.join(lines)
921
878
if len(bytes) != self._current_size():
922
879
raise AssertionError('Invalid _current_size')
923
_get_cache().add(self._key, bytes)
880
_page_cache.add(self._key, bytes)
924
881
return [self._key]
990
947
LeafNode or InternalNode.
993
__slots__ = ('_node_width',)
995
950
def __init__(self, prefix='', search_key_func=None):
996
951
Node.__init__(self)
997
952
# The size of an internalnode with default values and no children.
1039
994
:param key: The key that the serialised node has.
1040
995
:return: An InternalNode instance.
1042
key = static_tuple.expect_static_tuple(key)
1043
997
return _deserialise_internal_node(bytes, key,
1044
998
search_key_func=search_key_func)
1070
1024
# for whatever we are missing
1071
1025
shortcut = True
1072
1026
for prefix, node in self._items.iteritems():
1073
if node.__class__ is StaticTuple:
1027
if node.__class__ is tuple:
1074
1028
keys[node] = (prefix, None)
1076
1030
yield node, None
1105
1059
# A given key can only match 1 child node, if it isn't
1106
1060
# there, then we can just return nothing
1108
if node.__class__ is StaticTuple:
1062
if node.__class__ is tuple:
1109
1063
keys[node] = (search_prefix, [key])
1111
1065
# This is loaded, and the only thing that can match,
1138
1092
# We can ignore this one
1140
1094
node_key_filter = prefix_to_keys[search_prefix]
1141
if node.__class__ is StaticTuple:
1095
if node.__class__ is tuple:
1142
1096
keys[node] = (search_prefix, node_key_filter)
1144
1098
yield node, node_key_filter
1153
1107
if sub_prefix in length_filter:
1154
1108
node_key_filter.extend(prefix_to_keys[sub_prefix])
1155
1109
if node_key_filter: # this key matched something, yield it
1156
if node.__class__ is StaticTuple:
1110
if node.__class__ is tuple:
1157
1111
keys[node] = (prefix, node_key_filter)
1159
1113
yield node, node_key_filter
1193
1147
prefix, node_key_filter = keys[record.key]
1194
1148
node_and_filters.append((node, node_key_filter))
1195
1149
self._items[prefix] = node
1196
_get_cache().add(record.key, bytes)
1150
_page_cache.add(record.key, bytes)
1197
1151
for info in node_and_filters:
1308
1262
lines.append('%s\n' % (self._search_prefix,))
1309
1263
prefix_len = len(self._search_prefix)
1310
1264
for prefix, node in sorted(self._items.items()):
1311
if type(node) is StaticTuple:
1265
if type(node) is tuple:
1314
1268
key = node._key[0]
1318
1272
% (serialised, self._search_prefix))
1319
1273
lines.append(serialised[prefix_len:])
1320
1274
sha1, _, _ = store.add_lines((None,), (), lines)
1321
self._key = StaticTuple("sha1:" + sha1,).intern()
1322
_get_cache().add(self._key, ''.join(lines))
1275
self._key = ("sha1:" + sha1,)
1276
_page_cache.add(self._key, ''.join(lines))
1323
1277
yield self._key
1325
1279
def _search_key(self, key):
1369
1323
return self._search_prefix
1371
1325
def unmap(self, store, key, check_remap=True):
1372
"""Remove key from this node and its children."""
1326
"""Remove key from this node and it's children."""
1373
1327
if not len(self._items):
1374
1328
raise AssertionError("can't unmap in an empty InternalNode.")
1375
1329
children = [node for node, _
1474
1428
def __init__(self, store, new_root_keys, old_root_keys,
1475
1429
search_key_func, pb=None):
1476
# TODO: Should we add a StaticTuple barrier here? It would be nice to
1477
# force callers to use StaticTuple, because there will often be
1478
# lots of keys passed in here. And even if we cast it locally,
1479
# that just meanst that we will have *both* a StaticTuple and a
1480
# tuple() in memory, referring to the same object. (so a net
1481
# increase in memory, not a decrease.)
1482
1430
self._store = store
1483
1431
self._new_root_keys = new_root_keys
1484
1432
self._old_root_keys = old_root_keys
1486
1434
# All uninteresting chks that we have seen. By the time they are added
1487
1435
# here, they should be either fully ignored, or queued up for
1489
# TODO: This might grow to a large size if there are lots of merge
1490
# parents, etc. However, it probably doesn't scale to O(history)
1491
# like _processed_new_refs does.
1492
1437
self._all_old_chks = set(self._old_root_keys)
1493
1438
# All items that we have seen from the old_root_keys
1494
1439
self._all_old_items = set()
1495
1440
# These are interesting items which were either read, or already in the
1496
1441
# interesting queue (so we don't need to walk them again)
1497
# TODO: processed_new_refs becomes O(all_chks), consider switching to
1499
1442
self._processed_new_refs = set()
1500
1443
self._search_key_func = search_key_func
1508
1451
self._state = None
1510
1453
def _read_nodes_from_store(self, keys):
1511
# We chose not to use _get_cache(), because we think in
1512
# terms of records to be yielded. Also, we expect to touch each page
1513
# only 1 time during this code. (We may want to evaluate saving the
1514
# raw bytes into the page cache, which would allow a working tree
1515
# update after the fetch to not have to read the bytes again.)
1516
as_st = StaticTuple.from_sequence
1454
# We chose not to use _page_cache, because we think in terms of records
1455
# to be yielded. Also, we expect to touch each page only 1 time during
1456
# this code. (We may want to evaluate saving the raw bytes into the
1457
# page cache, which would allow a working tree update after the fetch
1458
# to not have to read the bytes again.)
1517
1459
stream = self._store.get_record_stream(keys, 'unordered', True)
1518
1460
for record in stream:
1519
1461
if self._pb is not None:
1526
1468
if type(node) is InternalNode:
1527
1469
# Note we don't have to do node.refs() because we know that
1528
1470
# there are no children that have been pushed into this node
1529
# Note: Using as_st() here seemed to save 1.2MB, which would
1530
# indicate that we keep 100k prefix_refs around while
1531
# processing. They *should* be shorter lived than that...
1532
# It does cost us ~10s of processing time
1533
#prefix_refs = [as_st(item) for item in node._items.iteritems()]
1534
1471
prefix_refs = node._items.items()
1537
1474
prefix_refs = []
1538
# Note: We don't use a StaticTuple here. Profiling showed a
1539
# minor memory improvement (0.8MB out of 335MB peak 0.2%)
1540
# But a significant slowdown (15s / 145s, or 10%)
1541
1475
items = node._items.items()
1542
1476
yield record, node, prefix_refs, items
1551
1485
if p_r[1] not in all_old_chks]
1552
1486
new_refs = [p_r[1] for p_r in prefix_refs]
1553
1487
all_old_chks.update(new_refs)
1554
# TODO: This might be a good time to turn items into StaticTuple
1555
# instances and possibly intern them. However, this does not
1556
# impact 'initial branch' performance, so I'm not worrying
1558
1488
self._all_old_items.update(items)
1559
1489
# Queue up the uninteresting references
1560
1490
# Don't actually put them in the 'to-read' queue until we have
1613
1543
# current design allows for this, as callers will do the work
1614
1544
# to make the results unique. We might profile whether we
1615
1545
# gain anything by ensuring unique return values for items
1616
# TODO: This might be a good time to cast to StaticTuple, as
1617
# self._new_item_queue will hold the contents of multiple
1618
# records for an extended lifetime
1619
1546
new_items = [item for item in items
1620
1547
if item not in self._all_old_items]
1621
1548
self._new_item_queue.extend(new_items)
1647
1574
yield None, new_items
1648
1575
refs = refs.difference(all_old_chks)
1649
processed_new_refs.update(refs)
1651
# TODO: Using a SimpleSet for self._processed_new_refs and
1652
# saved as much as 10MB of peak memory. However, it requires
1653
# implementing a non-pyrex version.
1654
1577
next_refs = set()
1655
1578
next_refs_update = next_refs.update
1656
1579
# Inlining _read_nodes_from_store improves 'bzr branch bzr.dev'
1657
1580
# from 1m54s to 1m51s. Consider it.
1658
1581
for record, _, p_refs, items in self._read_nodes_from_store(refs):
1660
# using the 'if' check saves about 145s => 141s, when
1661
# streaming initial branch of Launchpad data.
1662
items = [item for item in items
1663
if item not in all_old_items]
1582
items = [item for item in items
1583
if item not in all_old_items]
1664
1584
yield record, items
1665
1585
next_refs_update([p_r[1] for p_r in p_refs])
1667
# set1.difference(set/dict) walks all of set1, and checks if it
1668
# exists in 'other'.
1669
# set1.difference(iterable) walks all of iterable, and does a
1670
# 'difference_update' on a clone of set1. Pick wisely based on the
1671
# expected sizes of objects.
1672
# in our case it is expected that 'new_refs' will always be quite
1674
1586
next_refs = next_refs.difference(all_old_chks)
1675
1587
next_refs = next_refs.difference(processed_new_refs)
1676
1588
processed_new_refs.update(next_refs)
1683
1595
self._old_queue = []
1684
1596
all_old_chks = self._all_old_chks
1685
1597
for record, _, prefix_refs, items in self._read_nodes_from_store(refs):
1686
# TODO: Use StaticTuple here?
1687
1598
self._all_old_items.update(items)
1688
1599
refs = [r for _,r in prefix_refs if r not in all_old_chks]
1689
1600
self._old_queue.extend(refs)
1726
1637
from bzrlib._chk_map_pyx import (
1728
1638
_search_key_16,
1729
1639
_search_key_255,
1730
1640
_deserialise_leaf_node,
1731
1641
_deserialise_internal_node,
1733
except ImportError, e:
1734
osutils.failed_to_load_extension(e)
1735
1644
from bzrlib._chk_map_py import (
1737
1645
_search_key_16,
1738
1646
_search_key_255,
1739
1647
_deserialise_leaf_node,
1742
1650
search_key_registry.register('hash-16-way', _search_key_16)
1743
1651
search_key_registry.register('hash-255-way', _search_key_255)
1746
def _check_key(key):
1747
"""Helper function to assert that a key is properly formatted.
1749
This generally shouldn't be used in production code, but it can be helpful
1752
if type(key) is not StaticTuple:
1753
raise TypeError('key %r is not StaticTuple but %s' % (key, type(key)))
1755
raise ValueError('key %r should have length 1, not %d' % (key, len(key),))
1756
if type(key[0]) is not str:
1757
raise TypeError('key %r should hold a str, not %r'
1758
% (key, type(key[0])))
1759
if not key[0].startswith('sha1:'):
1760
raise ValueError('key %r should point to a sha1:' % (key,))
added
removed
bzrlib/chk_map.py
