/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-19 11:11:53 UTC
  • Revision ID: mbp@sourcefrog.net-20050519111153-7f799c5987a540c7
- --forward option for log

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
    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