See DESIGN for more information.
Update the index format header to 'BUPI\0\0\0\5' (version 5).
Signed-off-by: Rob Browning <rlb@defaultvalue.org>
Reviewed-by: Zoran Zaric <zz@zoranzaric.de>
tree information.
The nice thing about this design is that you can walk through each
-file in a tree just by opening the tree and the .bupmeta contents, and
+file in a tree just by opening the tree and the .bupm contents, and
iterating through both at the same time.
+Since the contents of any .bupm file should match the state of the
+filesystem when it was *indexed*, bup must record the detailed
+metadata in the index. To do this, bup records four values in the
+index, the atime, mtime, and ctime (as timespecs), and an integer
+offset into a secondary "metadata store" which has the same name as
+the index, but with ".meta" appended. This secondary store contains
+the encoded Metadata object corresponding to each path in the index.
+
+Currently, in order to decrease the storage required for the metadata
+store, bup only writes unique values there, reusing offsets when
+appropriate across the index. The effectiveness of this approach
+relies on the expectation that there will be many duplicate metadata
+records. Storing the full timestamps in the index is intended to make
+that more likely, because it makes it unnecessary to record those
+values in the secondary store. So bup clears them before encoding the
+Metadata objects destined for the index, and timestamp differences
+don't contribute to the uniqueness of the metadata.
+
Bup supports recording and restoring hardlinks, and it does so by
tracking sets of paths that correspond to the same dev/inode pair when
indexing. This information is stored in an optional file with the
for separating the two steps are described in the man page
for `bup-index`(1).
-By default, metadata will be saved for every path. However, if
-`--strip`, `--strip-path`, or `--graft` is specified, metadata will
-not be saved for the root directory (*/*). See `bup-restore`(1) for
-more information about the handling of metadata.
+By default, metadata will be saved for every path, and the metadata
+for any unindexed parent directories of indexed paths will be taken
+directly from the filesystem. However, if `--strip`, `--strip-path`,
+or `--graft` is specified, metadata will not be saved for the root
+directory (*/*). See `bup-restore`(1) for more information about the
+handling of metadata.
# OPTIONS
#!/usr/bin/env python
+
import sys, stat, time, os
-from bup import options, git, index, drecurse, hlinkdb
+from bup import metadata, options, git, index, drecurse, hlinkdb
from bup.helpers import *
from bup.hashsplit import GIT_MODE_TREE, GIT_MODE_FILE
# tmax and start must be epoch nanoseconds.
tmax = (time.time() - 1) * 10**9
ri = index.Reader(indexfile)
- wi = index.Writer(indexfile, tmax)
+ msw = index.MetaStoreWriter(indexfile + '.meta')
+ wi = index.Writer(indexfile, msw, tmax)
rig = IterHelper(ri.iter(name=top))
tstart = int(time.time()) * 10**9
hlinks.del_path(rig.cur.name)
if not stat.S_ISDIR(pst.st_mode) and pst.st_nlink > 1:
hlinks.add_path(path, pst.st_dev, pst.st_ino)
- rig.cur.from_stat(pst, tstart)
+ meta = metadata.from_path(path, statinfo=pst)
+ # Clear these so they don't bloat the store -- they're
+ # already in the index (since they vary a lot and they're
+ # fixed length). If you've noticed "tmax", you might
+ # wonder why it's OK to do this, since that code may
+ # adjust (mangle) the index mtime and ctime -- producing
+ # fake values which must not end up in a .bupm. However,
+ # it looks like that shouldn't be possible: (1) When
+ # "save" validates the index entry, it always reads the
+ # metadata from the filesytem. (2) Metadata is only
+ # read/used from the index if hashvalid is true. (3) index
+ # always invalidates "faked" entries, because "old != new"
+ # in from_stat().
+ meta.ctime = meta.mtime = meta.atime = 0
+ meta_ofs = msw.store(meta)
+ rig.cur.from_stat(pst, meta_ofs, tstart)
if not (rig.cur.flags & index.IX_HASHVALID):
if hashgen:
(rig.cur.gitmode, rig.cur.sha) = hashgen(path)
rig.cur.repack()
rig.next()
else: # new paths
- wi.add(path, pst, hashgen = hashgen)
+ meta = metadata.from_path(path, statinfo=pst)
+ # See same assignment to 0, above, for rationale.
+ meta.atime = meta.mtime = meta.ctime = 0
+ meta_ofs = msw.store(meta)
+ wi.add(path, pst, meta_ofs, hashgen = hashgen)
if not stat.S_ISDIR(pst.st_mode) and pst.st_nlink > 1:
hlinks.add_path(path, pst.st_dev, pst.st_ino)
check_index(ri)
log('check: before merging: newfile\n')
check_index(wr)
- mi = index.Writer(indexfile, tmax)
+ mi = index.Writer(indexfile, msw, tmax)
for e in index.merge(ri, wr):
# FIXME: shouldn't we remove deleted entries eventually? When?
else:
wi.close()
+ msw.close()
hlinks.commit_save()
indexfile = opt.indexfile or git.repo('bupindex')
r = index.Reader(indexfile)
+msr = index.MetaStoreReader(indexfile + '.meta')
hlink_db = hlinkdb.HLinkDB(indexfile + '.hlink')
def already_saved(ent):
if first_root == None:
dir_name, fs_path = dirp[0]
first_root = dirp[0]
+ # Not indexed, so just grab the FS metadata or use empty metadata.
meta = metadata.from_path(fs_path) if fs_path else metadata.Metadata()
_push(dir_name, meta)
elif first_root != dirp[0]:
# If switching to a new sub-tree, start a new sub-tree.
for path_component in dirp[len(parts):]:
dir_name, fs_path = path_component
+ # Not indexed, so just grab the FS metadata or use empty metadata.
meta = metadata.from_path(fs_path) if fs_path else metadata.Metadata()
_push(dir_name, meta)
git_info = (ent.gitmode, git_name, id)
shalists[-1].append(git_info)
sort_key = git.shalist_item_sort_key((ent.mode, file, id))
- hlink = find_hardlink_target(hlink_db, ent)
- metalists[-1].append((sort_key,
- metadata.from_path(ent.name,
- hardlink_target=hlink)))
+ meta = msr.metadata_at(ent.meta_ofs)
+ meta.hardlink_target = find_hardlink_target(hlink_db, ent)
+ # Restore the times that were cleared to 0 in the metastore.
+ (meta.atime, meta.mtime, meta.ctime) = (ent.atime, ent.mtime, ent.ctime)
+ metalists[-1].append((sort_key, meta))
else:
if stat.S_ISREG(ent.mode):
try:
# Finish the root directory.
tree = _pop(force_tree = None,
+ # When there's a collision, use empty metadata for the root.
dir_metadata = metadata.Metadata() if root_collision else None)
if opt.tree:
if opt.commit:
print commit.encode('hex')
+msr.close()
w.close() # must close before we can update the ref
if opt.name:
-import os, stat, struct, tempfile
+import metadata, os, stat, struct, tempfile
from bup import xstat
from bup.helpers import *
EMPTY_SHA = '\0'*20
FAKE_SHA = '\x01'*20
-INDEX_HDR = 'BUPI\0\0\0\4'
+INDEX_HDR = 'BUPI\0\0\0\5'
# Time values are handled as integer nanoseconds since the epoch in
# memory, but are written as xstat/metadata timespecs. This behavior
# Record times (mtime, ctime, atime) as xstat/metadata timespecs, and
# store all of the times in the index so they won't interfere with the
# forthcoming metadata cache.
-INDEX_SIG = '!QQQqQqQqQIIQII20sHII'
+INDEX_SIG = '!QQQqQqQqQIIQII20sHIIQ'
ENTLEN = struct.calcsize(INDEX_SIG)
FOOTER_SIG = '!Q'
pass
+class MetaStoreReader:
+ def __init__(self, filename):
+ self._file = open(filename, 'rb')
+
+ def close(self):
+ if self._file:
+ self._file.close()
+ self._file = None
+
+ def __del__(self):
+ self.close()
+
+ def metadata_at(self, ofs):
+ self._file.seek(ofs)
+ return metadata.Metadata.read(self._file)
+
+
+class MetaStoreWriter:
+ # For now, we just append to the file, and try to handle any
+ # truncation or corruption somewhat sensibly.
+
+ def __init__(self, filename):
+ # Map metadata hashes to bupindex.meta offsets.
+ self._offsets = {}
+ self._filename = filename
+ # FIXME: see how slow this is; does it matter?
+ m_file = open(filename, 'ab+')
+ try:
+ m_file.seek(0)
+ try:
+ m = metadata.Metadata.read(m_file)
+ while m:
+ m_encoded = m.encode()
+ self._offsets[m_encoded] = m_file.tell() - len(m_encoded)
+ m = metadata.Metadata.read(m_file)
+ except EOFError:
+ pass
+ except:
+ log('index metadata in %r appears to be corrupt' % filename)
+ raise
+ finally:
+ m_file.close()
+ self._file = open(filename, 'ab')
+
+ def close(self):
+ if self._file:
+ self._file.close()
+ self._file = None
+
+ def __del__(self):
+ # Be optimistic.
+ self.close()
+
+ def store(self, metadata):
+ meta_encoded = metadata.encode(include_path=False)
+ ofs = self._offsets.get(meta_encoded)
+ if ofs:
+ return ofs
+ ofs = self._file.tell()
+ self._file.write(meta_encoded)
+ self._offsets[meta_encoded] = ofs
+ return ofs
+
+
class Level:
def __init__(self, ename, parent):
self.parent = parent
return (ofs,n)
-def _golevel(level, f, ename, newentry, tmax):
+def _golevel(level, f, ename, newentry, metastore, tmax):
# close nodes back up the tree
assert(level)
+ default_meta_ofs = metastore.store(metadata.Metadata())
while ename[:len(level.ename)] != level.ename:
- n = BlankNewEntry(level.ename[-1], tmax)
+ n = BlankNewEntry(level.ename[-1], default_meta_ofs, tmax)
n.flags |= IX_EXISTS
(n.children_ofs,n.children_n) = level.write(f)
level.parent.list.append(n)
# are we in precisely the right place?
assert(ename == level.ename)
- n = newentry or BlankNewEntry(ename and level.ename[-1] or None, tmax)
+ n = newentry or \
+ BlankNewEntry(ename and level.ename[-1] or None, default_meta_ofs, tmax)
(n.children_ofs,n.children_n) = level.write(f)
if level.parent:
level.parent.list.append(n)
class Entry:
- def __init__(self, basename, name, tmax):
+ def __init__(self, basename, name, meta_ofs, tmax):
self.basename = str(basename)
self.name = str(name)
+ self.meta_ofs = meta_ofs
self.tmax = tmax
self.children_ofs = 0
self.children_n = 0
def __repr__(self):
- return ("(%s,0x%04x,%d,%d,%d,%d,%d,%d,%d,%d,%s/%s,0x%04x,0x%08x/%d)"
+ return ("(%s,0x%04x,%d,%d,%d,%d,%d,%d,%d,%d,%s/%s,0x%04x,%d,0x%08x/%d)"
% (self.name, self.dev, self.ino, self.nlink,
self.ctime, self.mtime, self.atime, self.uid, self.gid,
self.size, self.mode, self.gitmode,
- self.flags, self.children_ofs, self.children_n))
+ self.flags, self.meta_ofs,
+ self.children_ofs, self.children_n))
def packed(self):
try:
atime[0], atime[1],
self.uid, self.gid, self.size, self.mode,
self.gitmode, self.sha, self.flags,
- self.children_ofs, self.children_n)
+ self.children_ofs, self.children_n,
+ self.meta_ofs)
except (DeprecationWarning, struct.error), e:
log('pack error: %s (%r)\n' % (e, self))
raise
- def from_stat(self, st, tstart):
+ def from_stat(self, st, meta_ofs, tstart):
old = (self.dev, self.ino, self.nlink, self.ctime, self.mtime,
self.uid, self.gid, self.size, self.flags & IX_EXISTS)
new = (st.st_dev, st.st_ino, st.st_nlink, st.st_ctime, st.st_mtime,
self.size = st.st_size
self.mode = st.st_mode
self.flags |= IX_EXISTS
+ self.meta_ofs = meta_ofs
# Check that the ctime's "second" is at or after tstart's.
ctime_sec_in_ns = xstat.fstime_floor_secs(st.st_ctime) * 10**9
if ctime_sec_in_ns >= tstart or old != new \
class NewEntry(Entry):
def __init__(self, basename, name, tmax, dev, ino, nlink,
ctime, mtime, atime,
- uid, gid, size, mode, gitmode, sha, flags,
+ uid, gid, size, mode, gitmode, sha, flags, meta_ofs,
children_ofs, children_n):
- Entry.__init__(self, basename, name, tmax)
+ Entry.__init__(self, basename, name, meta_ofs, tmax)
(self.dev, self.ino, self.nlink, self.ctime, self.mtime, self.atime,
self.uid, self.gid, self.size, self.mode, self.gitmode, self.sha,
self.flags, self.children_ofs, self.children_n
class BlankNewEntry(NewEntry):
- def __init__(self, basename, tmax):
+ def __init__(self, basename, meta_ofs, tmax):
NewEntry.__init__(self, basename, basename, tmax,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
- 0, EMPTY_SHA, 0, 0, 0)
+ 0, EMPTY_SHA, 0, meta_ofs, 0, 0)
class ExistingEntry(Entry):
def __init__(self, parent, basename, name, m, ofs):
- Entry.__init__(self, basename, name, None)
+ Entry.__init__(self, basename, name, None, None)
self.parent = parent
self._m = m
self._ofs = ofs
(self.dev, self.ino, self.nlink,
self.ctime, ctime_ns, self.mtime, mtime_ns, self.atime, atime_ns,
self.uid, self.gid, self.size, self.mode, self.gitmode, self.sha,
- self.flags, self.children_ofs, self.children_n
+ self.flags, self.children_ofs, self.children_n, self.meta_ofs
) = struct.unpack(INDEX_SIG, str(buffer(m, ofs, ENTLEN)))
self.atime = xstat.timespec_to_nsecs((self.atime, atime_ns))
self.mtime = xstat.timespec_to_nsecs((self.mtime, mtime_ns))
class Writer:
- def __init__(self, filename, tmax):
+ def __init__(self, filename, metastore, tmax):
self.rootlevel = self.level = Level([], None)
self.f = None
self.count = 0
self.lastfile = None
self.filename = None
self.filename = filename = realpath(filename)
+ self.metastore = metastore
self.tmax = tmax
(dir,name) = os.path.split(filename)
(ffd,self.tmpname) = tempfile.mkstemp('.tmp', filename, dir)
def flush(self):
if self.level:
- self.level = _golevel(self.level, self.f, [], None, self.tmax)
+ self.level = _golevel(self.level, self.f, [], None,
+ self.metastore, self.tmax)
self.count = self.rootlevel.count
if self.count:
self.count += 1
raise Error('%r must come before %r'
% (''.join(e.name), ''.join(self.lastfile)))
self.lastfile = e.name
- self.level = _golevel(self.level, self.f, ename, entry, self.tmax)
+ self.level = _golevel(self.level, self.f, ename, entry,
+ self.metastore, self.tmax)
- def add(self, name, st, hashgen = None):
+ def add(self, name, st, meta_ofs, hashgen = None):
endswith = name.endswith('/')
ename = pathsplit(name)
basename = ename[-1]
st.st_ctime, st.st_mtime, st.st_atime,
st.st_uid, st.st_gid,
st.st_size, st.st_mode, gitmode, sha, flags,
- 0, 0)
+ meta_ofs, 0, 0)
else:
assert(endswith)
- e = BlankNewEntry(basename, tmax)
+ meta_ofs = self.metastore.store(metadata.Metadata())
+ e = BlankNewEntry(basename, meta_ofs, tmax)
e.gitmode = gitmode
e.sha = sha
e.flags = flags
import os
import time
-from bup import index
+from bup import index, metadata
from bup.helpers import *
import bup.xstat as xstat
from wvtest import *
unlink('index.tmp')
ds = xstat.stat('.')
fs = xstat.stat('tindex.py')
- w = index.Writer('index.tmp', time.time() - 1)
- w.add('/var/tmp/sporky', fs)
- w.add('/etc/passwd', fs)
- w.add('/etc/', ds)
- w.add('/', ds)
+ unlink('index.meta.tmp')
+ ms = index.MetaStoreWriter('index.meta.tmp');
+ tmax = (time.time() - 1) * 10**9
+ w = index.Writer('index.tmp', ms, tmax)
+ w.add('/var/tmp/sporky', fs, 0)
+ w.add('/etc/passwd', fs, 0)
+ w.add('/etc/', ds, 0)
+ w.add('/', ds, 0)
+ ms.close()
w.close()
# Dec 31, 1969
os.utime("foo", (-86400, -86400))
- now = time.time()
- e = index.BlankNewEntry("foo", now - 1)
- e.from_stat(xstat.stat("foo"), now)
+ ns_per_sec = 10**9
+ tstart = time.time() * ns_per_sec
+ tmax = tstart - ns_per_sec
+ e = index.BlankNewEntry("foo", 0, tmax)
+ e.from_stat(xstat.stat("foo"), 0, tstart)
assert len(e.packed())
WVPASS()
# Jun 10, 1893
os.utime("foo", (-0x80000000, -0x80000000))
- e = index.BlankNewEntry("foo", now - 1)
- e.from_stat(xstat.stat("foo"), now)
+ e = index.BlankNewEntry("foo", 0, tmax)
+ e.from_stat(xstat.stat("foo"), 0, tstart)
assert len(e.packed())
WVPASS()
@wvtest
def index_dirty():
+ unlink('index.meta.tmp')
+ unlink('index2.meta.tmp')
+ unlink('index3.meta.tmp')
+ default_meta = metadata.Metadata()
+ ms1 = index.MetaStoreWriter('index.meta.tmp')
+ ms2 = index.MetaStoreWriter('index2.meta.tmp')
+ ms3 = index.MetaStoreWriter('index3.meta.tmp')
+ meta_ofs1 = ms1.store(default_meta)
+ meta_ofs2 = ms2.store(default_meta)
+ meta_ofs3 = ms3.store(default_meta)
unlink('index.tmp')
unlink('index2.tmp')
+ unlink('index3.tmp')
+
ds = xstat.stat('.')
fs = xstat.stat('tindex.py')
- tmax = time.time() - 1
+ tmax = (time.time() - 1) * 10**9
- w1 = index.Writer('index.tmp', tmax)
- w1.add('/a/b/x', fs)
- w1.add('/a/b/c', fs)
- w1.add('/a/b/', ds)
- w1.add('/a/', ds)
+ w1 = index.Writer('index.tmp', ms1, tmax)
+ w1.add('/a/b/x', fs, meta_ofs1)
+ w1.add('/a/b/c', fs, meta_ofs1)
+ w1.add('/a/b/', ds, meta_ofs1)
+ w1.add('/a/', ds, meta_ofs1)
#w1.close()
WVPASS()
- w2 = index.Writer('index2.tmp', tmax)
- w2.add('/a/b/n/2', fs)
+ w2 = index.Writer('index2.tmp', ms2, tmax)
+ w2.add('/a/b/n/2', fs, meta_ofs2)
#w2.close()
WVPASS()
- w3 = index.Writer('index3.tmp', tmax)
- w3.add('/a/c/n/3', fs)
+ w3 = index.Writer('index3.tmp', ms3, tmax)
+ w3.add('/a/c/n/3', fs, meta_ofs3)
#w3.close()
WVPASS()
ln hardlink-target hardlink-3
)
+ # Add some trivial files for the index, modify, save tests.
+ (
+ cd "$TOP/bupmeta.tmp"/src
+ mkdir volatile
+ touch volatile/{1,2,3}
+ )
+
# Regression test for metadata sort order. Previously, these two
# entries would sort in the wrong order because the metadata
# entries were being sorted by mangled name, but the index isn't.
test-src-save-restore
)
+# Test that we pull the index (not filesystem) metadata for any
+# unchanged files whenever we're saving other files in a given
+# directory.
+WVSTART 'metadata save/restore (using index metadata)'
+(
+ setup-test-tree
+ cd "$TOP/bupmeta.tmp"
+
+ # ...for now -- might be a problem with hardlink restores that was
+ # causing noise wrt this test.
+ rm -rf src/hardlink*
+
+ # Pause here to keep the filesystem changes far enough away from
+ # the first index run that bup won't cap their index timestamps
+ # (see "bup help index" for more information). Without this
+ # sleep, the compare-trees test below "Bup should *not* pick up
+ # these metadata..." may fail.
+ sleep 1
+
+ set -x
+ rm -rf src.bup
+ mkdir src.bup
+ export BUP_DIR=$(pwd)/src.bup
+ WVPASS bup init
+ WVPASS bup index src
+ WVPASS bup save -t -n src src
+
+ force-delete src-restore-1
+ mkdir src-restore-1
+ WVPASS bup restore -C src-restore-1 "/src/latest$(pwd)/"
+ WVPASS test -d src-restore-1/src
+ WVPASS "$TOP/t/compare-trees" -c src/ src-restore-1/src/
+
+ echo "blarg" > src/volatile/1
+ cp -a src/volatile/1 src-restore-1/src/volatile/
+ WVPASS bup index src
+
+ # Bup should *not* pick up these metadata changes.
+ touch src/volatile/2
+
+ WVPASS bup save -t -n src src
+
+ force-delete src-restore-2
+ mkdir src-restore-2
+ WVPASS bup restore -C src-restore-2 "/src/latest$(pwd)/"
+ WVPASS test -d src-restore-2/src
+ WVPASS "$TOP/t/compare-trees" -c src-restore-1/src/ src-restore-2/src/
+
+ rm -rf src.bup
+ set +x
+)
+
setup-hardlink-test()
{
(
hardlink-test-run-restore
WVPASS "$TOP/t/compare-trees" -c src/ src-restore/src/
+ # Test the case where the hardlink hasn't changed, but the tree
+ # needs to be saved again. i.e. the save-cmd.py "if hashvalid:"
+ # case.
+ (
+ cd "$TOP/bupmeta.tmp"/src
+ echo whatever > something-new
+ )
+ WVPASS bup index src
+ WVPASS bup save -t -n src src
+ hardlink-test-run-restore
+ WVPASS "$TOP/t/compare-trees" -c src/ src-restore/src/
+
# Test hardlink changes between index runs.
#
setup-hardlink-test
projects / bup.git / commitdiff