/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/statcache.py

  • Committer: Martin Pool
  • Date: 2005-05-18 12:08:22 UTC
  • Revision ID: mbp@sourcefrog.net-20050518120821-6f80eab9f273edcf
- fix import

Show diffs side-by-side

added added

removed removed

Lines of Context:
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
    from sets import Set
 
140
    import re
 
141
    cache = {}
 
142
    seen_paths = Set()
 
143
 
 
144
    sha_re = re.compile(r'[a-f0-9]{40}')
 
145
 
 
146
    try:
 
147
        cachefn = os.path.join(basedir, '.bzr', 'stat-cache')
 
148
        cachefile = open(cachefn, 'rb')
 
149
    except IOError:
 
150
        return cache
 
151
 
 
152
    line1 = cachefile.readline().rstrip('\r\n')
 
153
    if line1 != CACHE_HEADER:
 
154
        mutter('cache header marker not found at top of %s' % cachefn)
 
155
        return cache
 
156
 
 
157
    for l in cachefile:
 
158
        f = l.split(' ')
 
159
 
 
160
        file_id = a2b_qp(f[0]).decode('utf-8')
 
161
        if file_id in cache:
 
162
            raise BzrCheckError("duplicated file_id in cache: {%s}" % file_id)
 
163
 
 
164
        text_sha = f[1]
 
165
        if len(text_sha) != 40 or not sha_re.match(text_sha):
 
166
            raise BzrCheckError("invalid file SHA-1 in cache: %r" % text_sha)
 
167
        
 
168
        path = a2b_qp(f[2]).decode('utf-8')
 
169
        if path in seen_paths:
 
170
            raise BzrCheckError("duplicated path in cache: %r" % path)
 
171
        seen_paths.add(path)
 
172
        
 
173
        entry = (file_id, text_sha, path) + tuple([long(x) for x in f[3:]])
 
174
        if len(entry) != 8:
 
175
            raise ValueError("invalid statcache entry tuple %r" % entry)
 
176
 
 
177
        cache[file_id] = entry
 
178
    return cache
 
179
 
 
180
 
 
181
 
 
182
 
 
183
def _files_from_inventory(inv):
 
184
    for path, ie in inv.iter_entries():
 
185
        if ie.kind != 'file':
 
186
            continue
 
187
        yield ie.file_id, path
 
188
    
 
189
 
 
190
 
 
191
def update_cache(basedir, inv, flush=False):
 
192
    """Update and return the cache for the branch.
 
193
 
 
194
    The returned cache may contain entries that have not been written
 
195
    to disk for files recently touched.
 
196
 
 
197
    flush -- discard any previous cache and recalculate from scratch.
 
198
    """
 
199
 
 
200
    
 
201
    # TODO: It's supposed to be faster to stat the files in order by inum.
 
202
    # We don't directly know the inum of the files of course but we do
 
203
    # know where they were last sighted, so we can sort by that.
 
204
 
 
205
    assert isinstance(flush, bool)
 
206
    if flush:
 
207
        cache = {}
 
208
    else:
 
209
        cache = load_cache(basedir)
 
210
    return _update_cache_from_list(basedir, cache, _files_from_inventory(inv))
 
211
 
 
212
 
 
213
 
 
214
def _update_cache_from_list(basedir, cache, to_update):
 
215
    """Update and return the cache for given files.
 
216
 
 
217
    cache -- Previously cached values to be validated.
 
218
 
 
219
    to_update -- Sequence of (file_id, path) pairs to check.
 
220
    """
 
221
 
 
222
    from sets import Set
 
223
 
 
224
    stat_cnt = missing_cnt = hardcheck = change_cnt = 0
 
225
 
 
226
    # files that have been recently touched and can't be
 
227
    # committed to a persistent cache yet.
 
228
    
 
229
    dangerfiles = Set()
 
230
    now = int(time.time())
 
231
 
 
232
    ## mutter('update statcache under %r' % basedir)
 
233
    for file_id, path in to_update:
 
234
        abspath = os.path.join(basedir, path)
 
235
        fp = fingerprint(abspath)
 
236
        stat_cnt += 1
 
237
        
 
238
        cacheentry = cache.get(file_id)
 
239
 
 
240
        if fp == None: # not here
 
241
            if cacheentry:
 
242
                del cache[file_id]
 
243
                change_cnt += 1
 
244
            missing_cnt += 1
 
245
            continue
 
246
 
 
247
        if (fp[FP_MTIME] >= now) or (fp[FP_CTIME] >= now):
 
248
            dangerfiles.add(file_id)
 
249
 
 
250
        if cacheentry and (cacheentry[3:] == fp):
 
251
            continue                    # all stat fields unchanged
 
252
 
 
253
        hardcheck += 1
 
254
 
 
255
        dig = sha.new(file(abspath, 'rb').read()).hexdigest()
 
256
 
 
257
        # We update the cache even if the digest has not changed from
 
258
        # last time we looked, so that the fingerprint fields will
 
259
        # match in future.
 
260
        cacheentry = (file_id, dig, path) + fp
 
261
        cache[file_id] = cacheentry
 
262
        change_cnt += 1
 
263
 
 
264
    mutter('statcache: statted %d files, read %d files, %d changed, %d dangerous, '
 
265
           '%d in cache'
 
266
           % (stat_cnt, hardcheck, change_cnt, len(dangerfiles), len(cache)))
 
267
        
 
268
    if change_cnt:
 
269
        mutter('updating on-disk statcache')
 
270
        _write_cache(basedir, cache.itervalues(), dangerfiles)
 
271
 
 
272
    return cache