« back to all changes in this revision
Viewing changes to bzrlib/cache.py
- browse files at revision 363
- compare with another revision
- download diff
- download tarball
- view history from revision 363
- Committer: Martin Pool
- Date: 2005-05-05 06:38:18 UTC
- Revision ID: mbp@sourcefrog.net-20050505063818-3eb3260343878325
- do upload CHANGELOG to web server, even though it's autogenerated
- files added:
- bzrlib/tests.py
- files removed:
- bzr-man.py
- patches
- files renamed:
- bzrlib/statcache.py => bzrlib/cache.py
- contrib/bash/bzr.simple => contrib/bash/bzr
- files modified:
- .bzrignore
added
removed
bzrlib/cache.py
15
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
16
16
17
17
import stat, os, sha, time
18
from binascii import b2a_qp, a2b_qp
18
19
19
20
from trace import mutter
20
from errors import BzrError, BzrCheckError
21
22
23
"""File stat cache to speed up tree comparisons.
24
25
This module basically gives a quick way to find the SHA-1 and related
26
information of a file in the working directory, without actually
27
reading and hashing the whole file.
28
29
30
31
Implementation
32
==============
33
34
Users of this module should not need to know about how this is
35
implemented, and in particular should not depend on the particular
36
data which is stored or its format.
37
38
This is done by maintaining a cache indexed by a file fingerprint of
39
(path, size, mtime, ctime, ino, dev) pointing to the SHA-1. If the
40
fingerprint has changed, we assume the file content has not changed
41
either and the SHA-1 is therefore the same.
42
43
If any of the fingerprint fields have changed then the file content
44
*may* have changed, or it may not have. We need to reread the file
45
contents to make sure, but this is not visible to the user or
46
higher-level code (except as a delay of course).
47
48
The mtime and ctime are stored with nanosecond fields, but not all
49
filesystems give this level of precision. There is therefore a
50
possible race: the file might be modified twice within a second
51
without changing the size or mtime, and a SHA-1 cached from the first
52
version would be wrong. We handle this by not recording a cached hash
53
for any files which were modified in the current second and that
54
therefore have the chance to change again before the second is up.
55
56
The only known hole in this design is if the system clock jumps
57
backwards crossing invocations of bzr. Please don't do that; use ntp
58
to gradually adjust your clock or don't use bzr over the step.
59
60
At the moment this is stored in a simple textfile; it might be nice
61
to use a tdb instead to allow faster lookup by file-id.
62
63
The cache is represented as a map from file_id to a tuple of (file_id,
64
sha1, path, size, mtime, ctime, ino, dev).
65
66
The SHA-1 is stored in memory as a hexdigest.
67
68
This version of the file on disk has one line per record, and fields
69
separated by \0 records.
70
"""
71
72
# order of fields returned by fingerprint()
73
FP_SIZE = 0
74
FP_MTIME = 1
75
FP_CTIME = 2
76
FP_INO = 3
77
FP_DEV = 4
78
79
# order of fields in the statcache file and in the in-memory map
80
SC_FILE_ID = 0
81
SC_SHA1 = 1
82
SC_PATH = 2
83
SC_SIZE = 3
84
SC_MTIME = 4
85
SC_CTIME = 5
86
SC_INO = 6
87
SC_DEV = 7
88
89
90
91
CACHE_HEADER = "### bzr statcache v4"
92
93
94
def fingerprint(abspath):
21
22
23
# file fingerprints are: (path, size, mtime, ctime, ino, dev).
24
#
25
# if this is the same for this file as in the previous revision, we
26
# assume the content is the same and the SHA-1 is the same.
27
28
# This is stored in a fingerprint file that also contains the file-id
29
# and the content SHA-1.
30
31
# Thus for any given file we can quickly get the SHA-1, either from
32
# the cache or if the cache is out of date.
33
34
# At the moment this is stored in a simple textfile; it might be nice
35
# to use a tdb instead.
36
37
38
# What we need:
39
40
# build a new cache from scratch
41
# load cache, incrementally update it
42
43
# TODO: Have a paranoid mode where we always compare the texts and
44
# always recalculate the digest, to trap modification without stat
45
# change and SHA collisions.
46
47
48
49
def fingerprint(path, abspath):
95
50
try:
96
51
fs = os.lstat(abspath)
97
52
except OSError:
105
60
fs.st_ctime, fs.st_ino, fs.st_dev)
106
61
107
62
108
109
def _write_cache(basedir, entries):
110
from atomicfile import AtomicFile
111
112
cachefn = os.path.join(basedir, '.bzr', 'stat-cache')
113
outf = AtomicFile(cachefn, 'wb')
114
try:
115
outf.write(CACHE_HEADER + '\n')
116
117
for entry in entries:
118
if len(entry) != 8:
119
raise ValueError("invalid statcache entry tuple %r" % entry)
120
outf.write(entry[0].encode('utf-8')) # file id
121
outf.write('\0')
122
outf.write(entry[1]) # hex sha1
123
outf.write('\0')
124
outf.write(entry[2].encode('utf-8')) # name
125
for nf in entry[3:]:
126
outf.write('\0%d' % nf)
127
outf.write('\n')
128
129
outf.commit()
130
finally:
131
if not outf.closed:
132
outf.abort()
133
134
135
def _try_write_cache(basedir, entries):
136
try:
137
return _write_cache(basedir, entries)
138
except IOError, e:
139
mutter("cannot update statcache in %s: %s" % (basedir, e))
140
except OSError, e:
141
mutter("cannot update statcache in %s: %s" % (basedir, e))
142
143
144
145
def load_cache(basedir):
146
import re
63
def write_cache(branch, entry_iter):
64
outf = branch.controlfile('work-cache.tmp', 'wt')
65
for entry in entry_iter:
66
outf.write(entry[0] + ' ' + entry[1] + ' ')
67
outf.write(b2a_qp(entry[2], True))
68
outf.write(' %d %d %d %d %d\n' % entry[3:])
69
70
outf.close()
71
os.rename(branch.controlfilename('work-cache.tmp'),
72
branch.controlfilename('work-cache'))
73
74
75
76
def load_cache(branch):
147
77
cache = {}
148
seen_paths = {}
149
from bzrlib.trace import warning
150
151
assert isinstance(basedir, basestring)
152
153
sha_re = re.compile(r'[a-f0-9]{40}')
154
78
155
79
try:
156
cachefn = os.path.join(basedir, '.bzr', 'stat-cache')
157
cachefile = open(cachefn, 'rb')
80
cachefile = branch.controlfile('work-cache', 'rt')
158
81
except IOError:
159
82
return cache
160
161
line1 = cachefile.readline().rstrip('\r\n')
162
if line1 != CACHE_HEADER:
163
mutter('cache header marker not found at top of %s; discarding cache'
164
% cachefn)
165
return cache
166
83
167
84
for l in cachefile:
168
f = l.split('\0')
169
170
file_id = f[0].decode('utf-8')
85
f = l.split(' ')
86
file_id = f[0]
171
87
if file_id in cache:
172
warning("duplicated file_id in cache: {%s}" % file_id)
173
174
text_sha = f[1]
175
if len(text_sha) != 40 or not sha_re.match(text_sha):
176
raise BzrCheckError("invalid file SHA-1 in cache: %r" % text_sha)
177
178
path = f[2].decode('utf-8')
179
if path in seen_paths:
180
warning("duplicated path in cache: %r" % path)
181
seen_paths[path] = True
182
183
entry = (file_id, text_sha, path) + tuple([long(x) for x in f[3:]])
184
if len(entry) != 8:
185
raise ValueError("invalid statcache entry tuple %r" % entry)
186
187
cache[file_id] = entry
88
raise BzrError("duplicated file_id in cache: {%s}" % file_id)
89
cache[file_id] = (f[0], f[1], a2b_qp(f[2])) + tuple([long(x) for x in f[3:]])
188
90
return cache
189
91
190
92
191
93
94
192
95
def _files_from_inventory(inv):
193
96
for path, ie in inv.iter_entries():
194
97
if ie.kind != 'file':
196
99
yield ie.file_id, path
197
100
198
101
199
200
def update_cache(basedir, inv, flush=False):
201
"""Update and return the cache for the branch.
202
203
The returned cache may contain entries that have not been written
204
to disk for files recently touched.
205
206
flush -- discard any previous cache and recalculate from scratch.
102
def build_cache(branch):
103
inv = branch.read_working_inventory()
104
105
cache = {}
106
_update_cache_from_list(branch, cache, _files_from_inventory(inv))
107
108
109
110
def update_cache(branch, inv):
111
# TODO: It's supposed to be faster to stat the files in order by inum.
112
# We don't directly know the inum of the files of course but we do
113
# know where they were last sighted, so we can sort by that.
114
115
cache = load_cache(branch)
116
return _update_cache_from_list(branch, cache, _files_from_inventory(inv))
117
118
119
120
def _update_cache_from_list(branch, cache, to_update):
121
"""Update the cache to have info on the named files.
122
123
to_update is a sequence of (file_id, path) pairs.
207
124
"""
208
209
# load the existing cache; use information there to find a list of
210
# files ordered by inode, which is alleged to be the fastest order
211
# to stat the files.
212
213
to_update = _files_from_inventory(inv)
214
215
assert isinstance(flush, bool)
216
if flush:
217
cache = {}
218
else:
219
cache = load_cache(basedir)
220
221
by_inode = []
222
without_inode = []
223
for file_id, path in to_update:
224
if file_id in cache:
225
by_inode.append((cache[file_id][SC_INO], file_id, path))
226
else:
227
without_inode.append((file_id, path))
228
by_inode.sort()
229
230
to_update = [a[1:] for a in by_inode] + without_inode
231
232
stat_cnt = missing_cnt = new_cnt = hardcheck = change_cnt = 0
233
234
# dangerfiles have been recently touched and can't be committed to
235
# a persistent cache yet, but they are returned to the caller.
236
dangerfiles = []
237
238
now = int(time.time())
239
240
## mutter('update statcache under %r' % basedir)
125
hardcheck = dirty = 0
241
126
for file_id, path in to_update:
242
abspath = os.path.join(basedir, path)
243
fp = fingerprint(abspath)
244
stat_cnt += 1
245
127
fap = branch.abspath(path)
128
fp = fingerprint(fap, path)
246
129
cacheentry = cache.get(file_id)
247
130
248
131
if fp == None: # not here
249
132
if cacheentry:
250
133
del cache[file_id]
251
change_cnt += 1
252
missing_cnt += 1
134
dirty += 1
253
135
continue
254
elif not cacheentry:
255
new_cnt += 1
256
257
if (fp[FP_MTIME] >= now) or (fp[FP_CTIME] >= now):
258
dangerfiles.append(file_id)
259
136
260
137
if cacheentry and (cacheentry[3:] == fp):
261
138
continue # all stat fields unchanged
262
139
263
140
hardcheck += 1
264
141
265
dig = sha.new(file(abspath, 'rb').read()).hexdigest()
266
267
# We update the cache even if the digest has not changed from
268
# last time we looked, so that the fingerprint fields will
269
# match in future.
270
cacheentry = (file_id, dig, path) + fp
271
cache[file_id] = cacheentry
272
change_cnt += 1
273
274
mutter('statcache: statted %d files, read %d files, %d changed, %d dangerous, '
275
'%d deleted, %d new, '
276
'%d in cache'
277
% (stat_cnt, hardcheck, change_cnt, len(dangerfiles),
278
missing_cnt, new_cnt, len(cache)))
279
280
if change_cnt:
281
mutter('updating on-disk statcache')
282
283
if dangerfiles:
284
safe_cache = cache.copy()
285
for file_id in dangerfiles:
286
del safe_cache[file_id]
287
else:
288
safe_cache = cache
289
290
_try_write_cache(basedir, safe_cache.itervalues())
142
dig = sha.new(file(fap, 'rb').read()).hexdigest()
143
144
if cacheentry == None or dig != cacheentry[1]:
145
# if there was no previous entry for this file, or if the
146
# SHA has changed, then update the cache
147
cacheentry = (file_id, dig, path) + fp
148
cache[file_id] = cacheentry
149
dirty += 1
150
151
mutter('work cache: read %d files, %d changed' % (hardcheck, dirty))
152
153
if dirty:
154
write_cache(branch, cache.itervalues())
291
155
292
156
return cache
Loggerhead is a web-based interface for Breezy
Version: 2.0.1