lib/bup/hashsplit.py

   1 import math
   2 from bup import _helpers
   3 from bup.helpers import *
   4
   5 BLOB_MAX = 8192*4   # 8192 is the "typical" blob size for bupsplit
   6 BLOB_READ_SIZE = 1024*1024
   7 MAX_PER_TREE = 256
   8 progress_callback = None
   9 fanout = 16
  10
  11 GIT_MODE_FILE = 0100644
  12 GIT_MODE_TREE = 040000
  13 GIT_MODE_SYMLINK = 0120000
  14 assert(GIT_MODE_TREE != 40000)  # 0xxx should be treated as octal
  15
  16 # The purpose of this type of buffer is to avoid copying on peek(), get(),
  17 # and eat().  We do copy the buffer contents on put(), but that should
  18 # be ok if we always only put() large amounts of data at a time.
  19 class Buf:
  20     def __init__(self):
  21         self.data = ''
  22         self.start = 0
  23
  24     def put(self, s):
  25         if s:
  26             self.data = buffer(self.data, self.start) + s
  27             self.start = 0
  28
  29     def peek(self, count):
  30         return buffer(self.data, self.start, count)
  31
  32     def eat(self, count):
  33         self.start += count
  34
  35     def get(self, count):
  36         v = buffer(self.data, self.start, count)
  37         self.start += count
  38         return v
  39
  40     def used(self):
  41         return len(self.data) - self.start
  42
  43
  44 def readfile_iter(files, progress=None):
  45     for filenum,f in enumerate(files):
  46         ofs = 0
  47         b = ''
  48         while 1:
  49             if progress:
  50                 progress(filenum, len(b))
  51             fadvise_done(f, max(0, ofs - 1024*1024))
  52             b = f.read(BLOB_READ_SIZE)
  53             ofs += len(b)
  54             if not b:
  55                 fadvise_done(f, ofs)
  56                 break
  57             yield b
  58
  59
  60 def _splitbuf(buf, basebits, fanbits):
  61     while 1:
  62         b = buf.peek(buf.used())
  63         (ofs, bits) = _helpers.splitbuf(b)
  64         if ofs > BLOB_MAX:
  65             ofs = BLOB_MAX
  66         if ofs:
  67             buf.eat(ofs)
  68             level = (bits-basebits)//fanbits  # integer division
  69             yield buffer(b, 0, ofs), level
  70         else:
  71             break
  72     while buf.used() >= BLOB_MAX:
  73         # limit max blob size
  74         yield buf.get(BLOB_MAX), 0
  75
  76
  77 def _hashsplit_iter(files, progress):
  78     assert(BLOB_READ_SIZE > BLOB_MAX)
  79     basebits = _helpers.blobbits()
  80     fanbits = int(math.log(fanout or 128, 2))
  81     buf = Buf()
  82     for inblock in readfile_iter(files, progress):
  83         buf.put(inblock)
  84         for buf_and_level in _splitbuf(buf, basebits, fanbits):
  85             yield buf_and_level
  86     if buf.used():
  87         yield buf.get(buf.used()), 0
  88
  89
  90 def _hashsplit_iter_keep_boundaries(files, progress):
  91     for real_filenum,f in enumerate(files):
  92         if progress:
  93             def prog(filenum, nbytes):
  94                 # the inner _hashsplit_iter doesn't know the real file count,
  95                 # so we'll replace it here.
  96                 return progress(real_filenum, nbytes)
  97         else:
  98             prog = None
  99         for buf_and_level in _hashsplit_iter([f], progress=prog):
 100             yield buf_and_level
 101
 102
 103 def hashsplit_iter(files, keep_boundaries, progress):
 104     if keep_boundaries:
 105         return _hashsplit_iter_keep_boundaries(files, progress)
 106     else:
 107         return _hashsplit_iter(files, progress)
 108
 109
 110 total_split = 0
 111 def split_to_blobs(makeblob, files, keep_boundaries, progress):
 112     global total_split
 113     for (blob, level) in hashsplit_iter(files, keep_boundaries, progress):
 114         sha = makeblob(blob)
 115         total_split += len(blob)
 116         if progress_callback:
 117             progress_callback(len(blob))
 118         yield (sha, len(blob), level)
 119
 120
 121 def _make_shalist(l):
 122     ofs = 0
 123     l = list(l)
 124     total = sum(size for mode,sha,size, in l)
 125     vlen = len('%x' % total)
 126     shalist = []
 127     for (mode, sha, size) in l:
 128         shalist.append((mode, '%0*x' % (vlen,ofs), sha))
 129         ofs += size
 130     assert(ofs == total)
 131     return (shalist, total)
 132
 133
 134 def _squish(maketree, stacks, n):
 135     i = 0
 136     while i<n or len(stacks[i]) > MAX_PER_TREE:
 137         while len(stacks) <= i+1:
 138             stacks.append([])
 139         if len(stacks[i]) == 1:
 140             stacks[i+1] += stacks[i]
 141         elif stacks[i]:
 142             (shalist, size) = _make_shalist(stacks[i])
 143             tree = maketree(shalist)
 144             stacks[i+1].append((GIT_MODE_TREE, tree, size))
 145         stacks[i] = []
 146         i += 1
 147
 148
 149 def split_to_shalist(makeblob, maketree, files,
 150                      keep_boundaries, progress=None):
 151     sl = split_to_blobs(makeblob, files, keep_boundaries, progress)
 152     assert(fanout != 0)
 153     if not fanout:
 154         shal = []
 155         for (sha,size,level) in sl:
 156             shal.append((GIT_MODE_FILE, sha, size))
 157         return _make_shalist(shal)[0]
 158     else:
 159         stacks = [[]]
 160         for (sha,size,level) in sl:
 161             stacks[0].append((GIT_MODE_FILE, sha, size))
 162             if level:
 163                 _squish(maketree, stacks, level)
 164         #log('stacks: %r\n' % [len(i) for i in stacks])
 165         _squish(maketree, stacks, len(stacks)-1)
 166         #log('stacks: %r\n' % [len(i) for i in stacks])
 167         return _make_shalist(stacks[-1])[0]
 168
 169
 170 def split_to_blob_or_tree(makeblob, maketree, files, keep_boundaries):
 171     shalist = list(split_to_shalist(makeblob, maketree,
 172                                     files, keep_boundaries))
 173     if len(shalist) == 1:
 174         return (shalist[0][0], shalist[0][2])
 175     elif len(shalist) == 0:
 176         return (GIT_MODE_FILE, makeblob(''))
 177     else:
 178         return (GIT_MODE_TREE, maketree(shalist))
 179
 180
 181 def open_noatime(name):
 182     fd = _helpers.open_noatime(name)
 183     try:
 184         return os.fdopen(fd, 'rb', 1024*1024)
 185     except:
 186         try:
 187             os.close(fd)
 188         except:
 189             pass
 190         raise
 191
 192
 193 def fadvise_done(f, ofs):
 194     assert(ofs >= 0)
 195     if ofs > 0 and hasattr(f, 'fileno'):
 196         _helpers.fadvise_done(f.fileno(), ofs)