/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-06-06 13:24:18 UTC
  • Revision ID: mbp@sourcefrog.net-20050606132418-1082c87e2473e266
- manpage generator by Hans Ulrich Niedermann

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
 
 
19
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):
 
95
    try:
 
96
        fs = os.lstat(abspath)
 
97
    except OSError:
 
98
        # might be missing, etc
 
99
        return None
 
100
 
 
101
    if stat.S_ISDIR(fs.st_mode):
 
102
        return None
 
103
 
 
104
    return (fs.st_size, fs.st_mtime,
 
105
            fs.st_ctime, fs.st_ino, fs.st_dev)
 
106
 
 
107
 
 
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
 
147
    cache = {}
 
148
    seen_paths = {}
 
149
    from bzrlib.trace import warning
 
150
 
 
151
    sha_re = re.compile(r'[a-f0-9]{40}')
 
152
 
 
153
    try:
 
154
        cachefn = os.path.join(basedir, '.bzr', 'stat-cache')
 
155
        cachefile = open(cachefn, 'rb')
 
156
    except IOError:
 
157
        return cache
 
158
 
 
159
    line1 = cachefile.readline().rstrip('\r\n')
 
160
    if line1 != CACHE_HEADER:
 
161
        mutter('cache header marker not found at top of %s; discarding cache'
 
162
               % cachefn)
 
163
        return cache
 
164
 
 
165
    for l in cachefile:
 
166
        f = l.split('\0')
 
167
 
 
168
        file_id = f[0].decode('utf-8')
 
169
        if file_id in cache:
 
170
            warning("duplicated file_id in cache: {%s}" % file_id)
 
171
 
 
172
        text_sha = f[1]
 
173
        if len(text_sha) != 40 or not sha_re.match(text_sha):
 
174
            raise BzrCheckError("invalid file SHA-1 in cache: %r" % text_sha)
 
175
        
 
176
        path = f[2].decode('utf-8')
 
177
        if path in seen_paths:
 
178
            warning("duplicated path in cache: %r" % path)
 
179
        seen_paths[path] = True
 
180
        
 
181
        entry = (file_id, text_sha, path) + tuple([long(x) for x in f[3:]])
 
182
        if len(entry) != 8:
 
183
            raise ValueError("invalid statcache entry tuple %r" % entry)
 
184
 
 
185
        cache[file_id] = entry
 
186
    return cache
 
187
 
 
188
 
 
189
 
 
190
def _files_from_inventory(inv):
 
191
    for path, ie in inv.iter_entries():
 
192
        if ie.kind != 'file':
 
193
            continue
 
194
        yield ie.file_id, path
 
195
    
 
196
 
 
197
 
 
198
def update_cache(basedir, inv, flush=False):
 
199
    """Update and return the cache for the branch.
 
200
 
 
201
    The returned cache may contain entries that have not been written
 
202
    to disk for files recently touched.
 
203
 
 
204
    flush -- discard any previous cache and recalculate from scratch.
 
205
    """
 
206
 
 
207
    # load the existing cache; use information there to find a list of
 
208
    # files ordered by inode, which is alleged to be the fastest order
 
209
    # to stat the files.
 
210
    
 
211
    to_update = _files_from_inventory(inv)
 
212
 
 
213
    assert isinstance(flush, bool)
 
214
    if flush:
 
215
        cache = {}
 
216
    else:
 
217
        cache = load_cache(basedir)
 
218
 
 
219
        by_inode = []
 
220
        without_inode = []
 
221
        for file_id, path in to_update:
 
222
            if file_id in cache:
 
223
                by_inode.append((cache[file_id][SC_INO], file_id, path))
 
224
            else:
 
225
                without_inode.append((file_id, path))
 
226
        by_inode.sort()
 
227
 
 
228
        to_update = [a[1:] for a in by_inode] + without_inode
 
229
            
 
230
    stat_cnt = missing_cnt = new_cnt = hardcheck = change_cnt = 0
 
231
 
 
232
    # dangerfiles have been recently touched and can't be committed to
 
233
    # a persistent cache yet, but they are returned to the caller.
 
234
    dangerfiles = []
 
235
    
 
236
    now = int(time.time())
 
237
 
 
238
    ## mutter('update statcache under %r' % basedir)
 
239
    for file_id, path in to_update:
 
240
        abspath = os.path.join(basedir, path)
 
241
        fp = fingerprint(abspath)
 
242
        stat_cnt += 1
 
243
        
 
244
        cacheentry = cache.get(file_id)
 
245
 
 
246
        if fp == None: # not here
 
247
            if cacheentry:
 
248
                del cache[file_id]
 
249
                change_cnt += 1
 
250
            missing_cnt += 1
 
251
            continue
 
252
        elif not cacheentry:
 
253
            new_cnt += 1
 
254
 
 
255
        if (fp[FP_MTIME] >= now) or (fp[FP_CTIME] >= now):
 
256
            dangerfiles.append(file_id)
 
257
 
 
258
        if cacheentry and (cacheentry[3:] == fp):
 
259
            continue                    # all stat fields unchanged
 
260
 
 
261
        hardcheck += 1
 
262
 
 
263
        dig = sha.new(file(abspath, 'rb').read()).hexdigest()
 
264
 
 
265
        # We update the cache even if the digest has not changed from
 
266
        # last time we looked, so that the fingerprint fields will
 
267
        # match in future.
 
268
        cacheentry = (file_id, dig, path) + fp
 
269
        cache[file_id] = cacheentry
 
270
        change_cnt += 1
 
271
 
 
272
    mutter('statcache: statted %d files, read %d files, %d changed, %d dangerous, '
 
273
           '%d deleted, %d new, '
 
274
           '%d in cache'
 
275
           % (stat_cnt, hardcheck, change_cnt, len(dangerfiles),
 
276
              missing_cnt, new_cnt, len(cache)))
 
277
        
 
278
    if change_cnt:
 
279
        mutter('updating on-disk statcache')
 
280
 
 
281
        if dangerfiles:
 
282
            safe_cache = cache.copy()
 
283
            for file_id in dangerfiles:
 
284
                del safe_cache[file_id]
 
285
        else:
 
286
            safe_cache = cache
 
287
        
 
288
        _try_write_cache(basedir, safe_cache.itervalues())
 
289
 
 
290
    return cache