« back to all changes in this revision
Viewing changes to bzrlib/statcache.py
- browse files at revision 334
- compare with another revision
- download diff
- download tarball
- view history from revision 334
- Committer: Martin Pool
- Date: 2005-05-03 08:00:27 UTC
- Revision ID: mbp@sourcefrog.net-20050503080027-908edb5b39982198
doc
- files added:
- bzrlib/tests.py
- files removed:
- bzrlib/atomicfile.py
- patches
- files modified:
- .bzrignore
added
removed
bzrlib/statcache.py
1
# (C) 2005 Canonical Ltd
2
3
# This program is free software; you can redistribute it and/or modify
4
# it under the terms of the GNU General Public License as published by
5
# the Free Software Foundation; either version 2 of the License, or
6
# (at your option) any later version.
7
8
# This program is distributed in the hope that it will be useful,
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11
# GNU General Public License for more details.
12
13
# You should have received a copy of the GNU General Public License
14
# along with this program; if not, write to the Free Software
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
16
17
import stat, os, sha, time
18
from binascii import b2a_qp, a2b_qp
19
20
from trace import mutter
21
from errors import BzrError, BzrCheckError
22
23
24
"""File stat cache to speed up tree comparisons.
25
26
This module basically gives a quick way to find the SHA-1 and related
27
information of a file in the working directory, without actually
28
reading and hashing the whole file.
29
30
31
32
Implementation
33
==============
34
35
Users of this module should not need to know about how this is
36
implemented, and in particular should not depend on the particular
37
data which is stored or its format.
38
39
This is done by maintaining a cache indexed by a file fingerprint of
40
(path, size, mtime, ctime, ino, dev) pointing to the SHA-1. If the
41
fingerprint has changed, we assume the file content has not changed
42
either and the SHA-1 is therefore the same.
43
44
If any of the fingerprint fields have changed then the file content
45
*may* have changed, or it may not have. We need to reread the file
46
contents to make sure, but this is not visible to the user or
47
higher-level code (except as a delay of course).
48
49
The mtime and ctime are stored with nanosecond fields, but not all
50
filesystems give this level of precision. There is therefore a
51
possible race: the file might be modified twice within a second
52
without changing the size or mtime, and a SHA-1 cached from the first
53
version would be wrong. We handle this by not recording a cached hash
54
for any files which were modified in the current second and that
55
therefore have the chance to change again before the second is up.
56
57
The only known hole in this design is if the system clock jumps
58
backwards crossing invocations of bzr. Please don't do that; use ntp
59
to gradually adjust your clock or don't use bzr over the step.
60
61
At the moment this is stored in a simple textfile; it might be nice
62
to use a tdb instead.
63
64
The cache is represented as a map from file_id to a tuple of (file_id,
65
sha1, path, size, mtime, ctime, ino, dev).
66
67
The SHA-1 is stored in memory as a hexdigest.
68
69
File names and file-ids are written out as the quoted-printable
70
encoding of their UTF-8 representation. (file-ids shouldn't contain
71
wierd characters, but it might happen.)
72
"""
73
74
# order of fields returned by fingerprint()
75
FP_SIZE = 0
76
FP_MTIME = 1
77
FP_CTIME = 2
78
FP_INO = 3
79
FP_DEV = 4
80
81
# order of fields in the statcache file and in the in-memory map
82
SC_FILE_ID = 0
83
SC_SHA1 = 1
84
SC_PATH = 2
85
SC_SIZE = 3
86
SC_MTIME = 4
87
SC_CTIME = 5
88
SC_INO = 6
89
SC_DEV = 7
90
91
92
93
CACHE_HEADER = "### bzr statcache v2"
94
95
96
def fingerprint(abspath):
97
try:
98
fs = os.lstat(abspath)
99
except OSError:
100
# might be missing, etc
101
return None
102
103
if stat.S_ISDIR(fs.st_mode):
104
return None
105
106
return (fs.st_size, fs.st_mtime,
107
fs.st_ctime, fs.st_ino, fs.st_dev)
108
109
110
def _write_cache(basedir, entry_iter, dangerfiles):
111
from atomicfile import AtomicFile
112
113
cachefn = os.path.join(basedir, '.bzr', 'stat-cache')
114
outf = AtomicFile(cachefn, 'wb')
115
outf.write(CACHE_HEADER + '\n')
116
try:
117
for entry in entry_iter:
118
if len(entry) != 8:
119
raise ValueError("invalid statcache entry tuple %r" % entry)
120
121
if entry[SC_FILE_ID] in dangerfiles:
122
continue # changed too recently
123
outf.write(b2a_qp(entry[0].encode('utf-8'))) # file id
124
outf.write(' ')
125
outf.write(entry[1]) # hex sha1
126
outf.write(' ')
127
outf.write(b2a_qp(entry[2].encode('utf-8'), True)) # name
128
for nf in entry[3:]:
129
outf.write(' %d' % nf)
130
outf.write('\n')
131
132
outf.commit()
133
finally:
134
if not outf.closed:
135
outf.abort()
136
137
138
def load_cache(basedir):
139
import re
140
cache = {}
141
seen_paths = {}
142
143
sha_re = re.compile(r'[a-f0-9]{40}')
144
145
try:
146
cachefn = os.path.join(basedir, '.bzr', 'stat-cache')
147
cachefile = open(cachefn, 'rb')
148
except IOError:
149
return cache
150
151
line1 = cachefile.readline().rstrip('\r\n')
152
if line1 != CACHE_HEADER:
153
mutter('cache header marker not found at top of %s' % cachefn)
154
return cache
155
156
for l in cachefile:
157
f = l.split(' ')
158
159
file_id = a2b_qp(f[0]).decode('utf-8')
160
if file_id in cache:
161
raise BzrCheckError("duplicated file_id in cache: {%s}" % file_id)
162
163
text_sha = f[1]
164
if len(text_sha) != 40 or not sha_re.match(text_sha):
165
raise BzrCheckError("invalid file SHA-1 in cache: %r" % text_sha)
166
167
path = a2b_qp(f[2]).decode('utf-8')
168
if path in seen_paths:
169
raise BzrCheckError("duplicated path in cache: %r" % path)
170
seen_paths[path] = True
171
172
entry = (file_id, text_sha, path) + tuple([long(x) for x in f[3:]])
173
if len(entry) != 8:
174
raise ValueError("invalid statcache entry tuple %r" % entry)
175
176
cache[file_id] = entry
177
return cache
178
179
180
181
182
def _files_from_inventory(inv):
183
for path, ie in inv.iter_entries():
184
if ie.kind != 'file':
185
continue
186
yield ie.file_id, path
187
188
189
190
def update_cache(basedir, inv, flush=False):
191
"""Update and return the cache for the branch.
192
193
The returned cache may contain entries that have not been written
194
to disk for files recently touched.
195
196
flush -- discard any previous cache and recalculate from scratch.
197
"""
198
199
200
# TODO: It's supposed to be faster to stat the files in order by inum.
201
# We don't directly know the inum of the files of course but we do
202
# know where they were last sighted, so we can sort by that.
203
204
assert isinstance(flush, bool)
205
if flush:
206
cache = {}
207
else:
208
cache = load_cache(basedir)
209
return _update_cache_from_list(basedir, cache, _files_from_inventory(inv))
210
211
212
213
def _update_cache_from_list(basedir, cache, to_update):
214
"""Update and return the cache for given files.
215
216
cache -- Previously cached values to be validated.
217
218
to_update -- Sequence of (file_id, path) pairs to check.
219
"""
220
stat_cnt = missing_cnt = hardcheck = change_cnt = 0
221
222
# dangerfiles have been recently touched and can't be
223
# committed to a persistent cache yet.
224
dangerfiles = {}
225
226
now = int(time.time())
227
228
## mutter('update statcache under %r' % basedir)
229
for file_id, path in to_update:
230
abspath = os.path.join(basedir, path)
231
fp = fingerprint(abspath)
232
stat_cnt += 1
233
234
cacheentry = cache.get(file_id)
235
236
if fp == None: # not here
237
if cacheentry:
238
del cache[file_id]
239
change_cnt += 1
240
missing_cnt += 1
241
continue
242
243
if (fp[FP_MTIME] >= now) or (fp[FP_CTIME] >= now):
244
dangerfiles[file_id] = True
245
246
if cacheentry and (cacheentry[3:] == fp):
247
continue # all stat fields unchanged
248
249
hardcheck += 1
250
251
dig = sha.new(file(abspath, 'rb').read()).hexdigest()
252
253
# We update the cache even if the digest has not changed from
254
# last time we looked, so that the fingerprint fields will
255
# match in future.
256
cacheentry = (file_id, dig, path) + fp
257
cache[file_id] = cacheentry
258
change_cnt += 1
259
260
mutter('statcache: statted %d files, read %d files, %d changed, %d dangerous, '
261
'%d in cache'
262
% (stat_cnt, hardcheck, change_cnt, len(dangerfiles), len(cache)))
263
264
if change_cnt:
265
mutter('updating on-disk statcache')
266
_write_cache(basedir, cache.itervalues(), dangerfiles)
267
268
return cache
Loggerhead is a web-based interface for Breezy
Version: 2.0.1