← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/statcache.py

  • Committer: Martin Pool
  • Date: 2005-05-11 01:09:41 UTC
  • Revision ID: mbp@sourcefrog.net-20050511010941-6438198e54086ddb
todo

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
 
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
This is done by maintaining a cache indexed by a file fingerprint of
 
31
(path, size, mtime, ctime, ino, dev) pointing to the SHA-1.  If the
 
32
fingerprint has changed, we assume the file content has not changed
 
33
either and the SHA-1 is therefore the same.
 
34
 
 
35
If any of the fingerprint fields have changed then the file content
 
36
*may* have changed, or it may not have.  We need to reread the file
 
37
contents to make sure, but this is not visible to the user or
 
38
higher-level code (except as a delay of course).
 
39
 
 
40
The mtime and ctime are stored with nanosecond fields, but not all
 
41
filesystems give this level of precision.  There is therefore a
 
42
possible race: the file might be modified twice within a second
 
43
without changing the size or mtime, and a SHA-1 cached from the first
 
44
version would be wrong.  We handle this by not recording a cached hash
 
45
for any files which were modified in the current second and that
 
46
therefore have the chance to change again before the second is up.
 
47
 
 
48
The only known hole in this design is if the system clock jumps
 
49
backwards crossing invocations of bzr.  Please don't do that; use ntp
 
50
to gradually adjust your clock or don't use bzr over the step.
 
51
 
 
52
At the moment this is stored in a simple textfile; it might be nice
 
53
to use a tdb instead.
 
54
 
 
55
The cache is represented as a map from file_id to a tuple of (file_id,
 
56
sha1, path, size, mtime, ctime, ino, dev).
 
57
"""
 
58
 
 
59
 
 
60
FP_SIZE  = 0
 
61
FP_MTIME = 1
 
62
FP_CTIME = 2
 
63
FP_INO   = 3
 
64
FP_DEV   = 4
 
65
 
 
66
 
 
67
SC_FILE_ID = 0
 
68
SC_SHA1    = 1 
 
69
 
 
70
 
 
71
def fingerprint(path, abspath):
 
72
    try:
 
73
        fs = os.lstat(abspath)
 
74
    except OSError:
 
75
        # might be missing, etc
 
76
        return None
 
77
 
 
78
    if stat.S_ISDIR(fs.st_mode):
 
79
        return None
 
80
 
 
81
    return (fs.st_size, fs.st_mtime,
 
82
            fs.st_ctime, fs.st_ino, fs.st_dev)
 
83
 
 
84
 
 
85
def _write_cache(branch, entry_iter, dangerfiles):
 
86
    from atomicfile import AtomicFile
 
87
    
 
88
    outf = AtomicFile(branch.controlfilename('stat-cache'), 'wb', 'utf-8')
 
89
    try:
 
90
        for entry in entry_iter:
 
91
            if entry[0] in dangerfiles:
 
92
                continue
 
93
            outf.write(entry[0] + ' ' + entry[1] + ' ')
 
94
            outf.write(b2a_qp(entry[2], True))
 
95
            outf.write(' %d %d %d %d %d\n' % entry[3:])
 
96
 
 
97
        outf.commit()
 
98
    finally:
 
99
        if not outf.closed:
 
100
            outf.abort()
 
101
        
 
102
        
 
103
def load_cache(branch):
 
104
    cache = {}
 
105
 
 
106
    try:
 
107
        cachefile = branch.controlfile('stat-cache', 'r')
 
108
    except IOError:
 
109
        return cache
 
110
    
 
111
    for l in cachefile:
 
112
        f = l.split(' ')
 
113
        file_id = f[0]
 
114
        if file_id in cache:
 
115
            raise BzrError("duplicated file_id in cache: {%s}" % file_id)
 
116
        cache[file_id] = (f[0], f[1], a2b_qp(f[2])) + tuple([long(x) for x in f[3:]])
 
117
    return cache
 
118
 
 
119
 
 
120
 
 
121
 
 
122
def _files_from_inventory(inv):
 
123
    for path, ie in inv.iter_entries():
 
124
        if ie.kind != 'file':
 
125
            continue
 
126
        yield ie.file_id, path
 
127
    
 
128
 
 
129
 
 
130
def update_cache(branch, inv=None, flush=False):
 
131
    """Update and return the cache for the branch.
 
132
 
 
133
    The returned cache may contain entries that have not been written
 
134
    to disk for files recently touched.
 
135
 
 
136
    flush -- discard any previous cache and recalculate from scratch.
 
137
    """
 
138
 
 
139
    
 
140
    # TODO: It's supposed to be faster to stat the files in order by inum.
 
141
    # We don't directly know the inum of the files of course but we do
 
142
    # know where they were last sighted, so we can sort by that.
 
143
 
 
144
    assert isinstance(flush, bool)
 
145
    if flush:
 
146
        cache = {}
 
147
    else:
 
148
        cache = load_cache(branch)
 
149
    if inv == None:
 
150
        inv = branch.read_working_inventory()
 
151
    return _update_cache_from_list(branch, cache, _files_from_inventory(inv))
 
152
 
 
153
 
 
154
 
 
155
def _update_cache_from_list(branch, cache, to_update):
 
156
    """Update and return the cache for given files.
 
157
 
 
158
    cache -- Previously cached values to be validated.
 
159
 
 
160
    to_update -- Sequence of (file_id, path) pairs to check.
 
161
    """
 
162
 
 
163
    from sets import Set
 
164
 
 
165
    hardcheck = dirty = 0
 
166
 
 
167
    # files that have been recently touched and can't be
 
168
    # committed to a persistent cache yet.
 
169
    
 
170
    dangerfiles = Set()
 
171
    now = int(time.time())
 
172
    
 
173
    for file_id, path in to_update:
 
174
        fap = branch.abspath(path)
 
175
        fp = fingerprint(fap, path)
 
176
        cacheentry = cache.get(file_id)
 
177
 
 
178
        if fp == None: # not here
 
179
            if cacheentry:
 
180
                del cache[file_id]
 
181
                dirty += 1
 
182
            continue
 
183
 
 
184
        if (fp[FP_MTIME] >= now) or (fp[FP_CTIME] >= now):
 
185
            dangerfiles.add(file_id)
 
186
 
 
187
        if cacheentry and (cacheentry[3:] == fp):
 
188
            continue                    # all stat fields unchanged
 
189
 
 
190
        hardcheck += 1
 
191
 
 
192
        dig = sha.new(file(fap, 'rb').read()).hexdigest()
 
193
 
 
194
        if cacheentry == None or dig != cacheentry[1]: 
 
195
            # if there was no previous entry for this file, or if the
 
196
            # SHA has changed, then update the cache
 
197
            cacheentry = (file_id, dig, path) + fp
 
198
            cache[file_id] = cacheentry
 
199
            dirty += 1
 
200
 
 
201
    mutter('statcache: read %d files, %d changed, %d dangerous, '
 
202
           '%d in cache'
 
203
           % (hardcheck, dirty, len(dangerfiles), len(cache)))
 
204
        
 
205
    if dirty:
 
206
        mutter('updating on-disk statcache')
 
207
        _write_cache(branch, cache.itervalues(), dangerfiles)
 
208
 
 
209
    return cache