« back to all changes in this revision
Viewing changes to bzrlib/cache.py
- browse files at revision 400
- compare with another revision
- download diff
- download tarball
- view history from revision 400
- Committer: Martin Pool
- Date: 2005-05-09 01:23:17 UTC
- Revision ID: mbp@sourcefrog.net-20050509012317-a503ae2eed842146
- doc: please run tests after installation
- files added:
- bzrlib/tests.py
- files removed:
- bzrlib/atomicfile.py
- patches
- files renamed:
- bzrlib/statcache.py => bzrlib/cache.py
- 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.
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
File names and file-ids are written out with non-ascii or whitespace
69
characters given as python-style unicode escapes. (file-ids shouldn't
70
contain wierd characters, but it might happen.)
71
"""
72
73
# order of fields returned by fingerprint()
74
FP_SIZE = 0
75
FP_MTIME = 1
76
FP_CTIME = 2
77
FP_INO = 3
78
FP_DEV = 4
79
80
# order of fields in the statcache file and in the in-memory map
81
SC_FILE_ID = 0
82
SC_SHA1 = 1
83
SC_PATH = 2
84
SC_SIZE = 3
85
SC_MTIME = 4
86
SC_CTIME = 5
87
SC_INO = 6
88
SC_DEV = 7
89
90
91
92
CACHE_HEADER = "### bzr statcache v3"
93
94
95
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):
96
50
try:
97
51
fs = os.lstat(abspath)
98
52
except OSError:
106
60
fs.st_ctime, fs.st_ino, fs.st_dev)
107
61
108
62
109
110
def safe_quote(s):
111
return s.encode('unicode_escape') \
112
.replace('\n', '\\u000a') \
113
.replace(' ', '\\u0020') \
114
.replace('\r', '\\u000d')
115
116
117
def _write_cache(basedir, entries):
118
from atomicfile import AtomicFile
119
120
cachefn = os.path.join(basedir, '.bzr', 'stat-cache')
121
outf = AtomicFile(cachefn, 'wb')
122
outf.write(CACHE_HEADER + '\n')
123
try:
124
for entry in entries:
125
if len(entry) != 8:
126
raise ValueError("invalid statcache entry tuple %r" % entry)
127
outf.write(safe_quote(entry[0])) # file id
128
outf.write(' ')
129
outf.write(entry[1]) # hex sha1
130
outf.write(' ')
131
outf.write(safe_quote(entry[2])) # name
132
for nf in entry[3:]:
133
outf.write(' %d' % nf)
134
outf.write('\n')
135
136
outf.commit()
137
finally:
138
if not outf.closed:
139
outf.abort()
140
141
142
def _try_write_cache(basedir, entries):
143
try:
144
return _write_cache(basedir, entries)
145
except IOError, e:
146
mutter("cannot update statcache in %s: %s" % (basedir, e))
147
except OSError, e:
148
mutter("cannot update statcache in %s: %s" % (basedir, e))
149
150
151
152
def load_cache(basedir):
153
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):
154
77
cache = {}
155
seen_paths = {}
156
157
sha_re = re.compile(r'[a-f0-9]{40}')
158
78
159
79
try:
160
cachefn = os.path.join(basedir, '.bzr', 'stat-cache')
161
cachefile = open(cachefn, 'rb')
80
cachefile = branch.controlfile('work-cache', 'rt')
162
81
except IOError:
163
82
return cache
164
165
line1 = cachefile.readline().rstrip('\r\n')
166
if line1 != CACHE_HEADER:
167
mutter('cache header marker not found at top of %s' % cachefn)
168
return cache
169
83
170
84
for l in cachefile:
171
85
f = l.split(' ')
172
173
file_id = f[0].decode('unicode_escape')
86
file_id = f[0]
174
87
if file_id in cache:
175
raise BzrCheckError("duplicated file_id in cache: {%s}" % file_id)
176
177
text_sha = f[1]
178
if len(text_sha) != 40 or not sha_re.match(text_sha):
179
raise BzrCheckError("invalid file SHA-1 in cache: %r" % text_sha)
180
181
path = f[2].decode('unicode_escape')
182
if path in seen_paths:
183
raise BzrCheckError("duplicated path in cache: %r" % path)
184
seen_paths[path] = True
185
186
entry = (file_id, text_sha, path) + tuple([long(x) for x in f[3:]])
187
if len(entry) != 8:
188
raise ValueError("invalid statcache entry tuple %r" % entry)
189
190
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:]])
191
90
return cache
192
91
193
92
200
99
yield ie.file_id, path
201
100
202
101
203
204
def update_cache(basedir, inv, flush=False):
205
"""Update and return the cache for the branch.
206
207
The returned cache may contain entries that have not been written
208
to disk for files recently touched.
209
210
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.
211
124
"""
212
213
# load the existing cache; use information there to find a list of
214
# files ordered by inode, which is alleged to be the fastest order
215
# to stat the files.
216
217
to_update = _files_from_inventory(inv)
218
219
assert isinstance(flush, bool)
220
if flush:
221
cache = {}
222
else:
223
cache = load_cache(basedir)
224
225
by_inode = []
226
without_inode = []
227
for file_id, path in to_update:
228
if file_id in cache:
229
by_inode.append((cache[file_id][SC_INO], file_id, path))
230
else:
231
without_inode.append((file_id, path))
232
by_inode.sort()
233
234
to_update = [a[1:] for a in by_inode] + without_inode
235
236
stat_cnt = missing_cnt = new_cnt = hardcheck = change_cnt = 0
237
238
# dangerfiles have been recently touched and can't be committed to
239
# a persistent cache yet, but they are returned to the caller.
240
dangerfiles = []
241
242
now = int(time.time())
243
244
## mutter('update statcache under %r' % basedir)
125
hardcheck = dirty = 0
245
126
for file_id, path in to_update:
246
abspath = os.path.join(basedir, path)
247
fp = fingerprint(abspath)
248
stat_cnt += 1
249
127
fap = branch.abspath(path)
128
fp = fingerprint(fap, path)
250
129
cacheentry = cache.get(file_id)
251
130
252
131
if fp == None: # not here
253
132
if cacheentry:
254
133
del cache[file_id]
255
change_cnt += 1
256
missing_cnt += 1
134
dirty += 1
257
135
continue
258
elif not cacheentry:
259
new_cnt += 1
260
261
if (fp[FP_MTIME] >= now) or (fp[FP_CTIME] >= now):
262
dangerfiles.append(file_id)
263
136
264
137
if cacheentry and (cacheentry[3:] == fp):
265
138
continue # all stat fields unchanged
266
139
267
140
hardcheck += 1
268
141
269
dig = sha.new(file(abspath, 'rb').read()).hexdigest()
270
271
# We update the cache even if the digest has not changed from
272
# last time we looked, so that the fingerprint fields will
273
# match in future.
274
cacheentry = (file_id, dig, path) + fp
275
cache[file_id] = cacheentry
276
change_cnt += 1
277
278
mutter('statcache: statted %d files, read %d files, %d changed, %d dangerous, '
279
'%d deleted, %d new, '
280
'%d in cache'
281
% (stat_cnt, hardcheck, change_cnt, len(dangerfiles),
282
missing_cnt, new_cnt, len(cache)))
283
284
if change_cnt:
285
mutter('updating on-disk statcache')
286
287
if dangerfiles:
288
safe_cache = cache.copy()
289
for file_id in dangerfiles:
290
del safe_cache[file_id]
291
else:
292
safe_cache = cache
293
294
_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())
295
155
296
156
return cache
Loggerhead is a web-based interface for Breezy
Version: 2.0.1