lib/bup/hashsplit.py

   1 import math
   2 from bup import _helpers
   3 from bup.helpers import *
   4
   5 BLOB_LWM = 8192*2
   6 BLOB_MAX = BLOB_LWM*2
   7 BLOB_HWM = 1024*1024
   8 MAX_PER_TREE = 256
   9 progress_callback = None
  10 max_pack_size = 1000*1000*1000  # larger packs will slow down pruning
  11 max_pack_objects = 200*1000  # cache memory usage is about 83 bytes per object
  12 fanout = 16
  13
  14 class Buf:
  15     def __init__(self):
  16         self.data = ''
  17         self.start = 0
  18
  19     def put(self, s):
  20         if s:
  21             self.data = buffer(self.data, self.start) + s
  22             self.start = 0
  23
  24     def peek(self, count):
  25         return buffer(self.data, self.start, count)
  26
  27     def eat(self, count):
  28         self.start += count
  29
  30     def get(self, count):
  31         v = buffer(self.data, self.start, count)
  32         self.start += count
  33         return v
  34
  35     def used(self):
  36         return len(self.data) - self.start
  37
  38
  39 def splitbuf(buf):
  40     b = buf.peek(buf.used())
  41     (ofs, bits) = _helpers.splitbuf(b)
  42     if ofs:
  43         buf.eat(ofs)
  44         return (buffer(b, 0, ofs), bits)
  45     return (None, 0)
  46
  47
  48 def blobiter(files):
  49     for f in files:
  50         ofs = 0
  51         while 1:
  52             fadvise_done(f, max(0, ofs - 1024*1024))
  53             b = f.read(BLOB_HWM)
  54             ofs += len(b)
  55             if not b:
  56                 fadvise_done(f, ofs)
  57                 break
  58             yield b
  59
  60
  61 def drainbuf(buf, finalize):
  62     while 1:
  63         (blob, bits) = splitbuf(buf)
  64         if blob:
  65             yield (blob, bits)
  66         else:
  67             break
  68     if buf.used() > BLOB_MAX:
  69         # limit max blob size
  70         yield (buf.get(buf.used()), 0)
  71     elif finalize and buf.used():
  72         yield (buf.get(buf.used()), 0)
  73
  74
  75 def _hashsplit_iter(files):
  76     assert(BLOB_HWM > BLOB_MAX)
  77     buf = Buf()
  78     fi = blobiter(files)
  79     while 1:
  80         for i in drainbuf(buf, finalize=False):
  81             yield i
  82         while buf.used() < BLOB_HWM:
  83             bnew = next(fi)
  84             if not bnew:
  85                 # eof
  86                 for i in drainbuf(buf, finalize=True):
  87                     yield i
  88                 return
  89             buf.put(bnew)
  90
  91
  92 def _hashsplit_iter_keep_boundaries(files):
  93     for f in files:
  94         for i in _hashsplit_iter([f]):
  95             yield i
  96
  97
  98 def hashsplit_iter(files, keep_boundaries):
  99     if keep_boundaries:
 100         return _hashsplit_iter_keep_boundaries(files)
 101     else:
 102         return _hashsplit_iter(files)
 103
 104
 105 total_split = 0
 106 def _split_to_blobs(w, files, keep_boundaries):
 107     global total_split
 108     for (blob, bits) in hashsplit_iter(files, keep_boundaries):
 109         sha = w.new_blob(blob)
 110         total_split += len(blob)
 111         if w.outbytes >= max_pack_size or w.count >= max_pack_objects:
 112             w.breakpoint()
 113         if progress_callback:
 114             progress_callback(len(blob))
 115         yield (sha, len(blob), bits)
 116
 117
 118 def _make_shalist(l):
 119     ofs = 0
 120     shalist = []
 121     for (mode, sha, size) in l:
 122         shalist.append((mode, '%016x' % ofs, sha))
 123         ofs += size
 124     total = ofs
 125     return (shalist, total)
 126
 127
 128 def _squish(w, stacks, n):
 129     i = 0
 130     while i<n or len(stacks[i]) > MAX_PER_TREE:
 131         while len(stacks) <= i+1:
 132             stacks.append([])
 133         if len(stacks[i]) == 1:
 134             stacks[i+1] += stacks[i]
 135         elif stacks[i]:
 136             (shalist, size) = _make_shalist(stacks[i])
 137             tree = w.new_tree(shalist)
 138             stacks[i+1].append(('40000', tree, size))
 139         stacks[i] = []
 140         i += 1
 141
 142
 143 def split_to_shalist(w, files, keep_boundaries):
 144     sl = _split_to_blobs(w, files, keep_boundaries)
 145     if not fanout:
 146         shal = []
 147         for (sha,size,bits) in sl:
 148             shal.append(('100644', sha, size))
 149         return _make_shalist(shal)[0]
 150     else:
 151         base_bits = _helpers.blobbits()
 152         fanout_bits = int(math.log(fanout, 2))
 153         def bits_to_idx(n):
 154             assert(n >= base_bits)
 155             return (n - base_bits)/fanout_bits
 156         stacks = [[]]
 157         for (sha,size,bits) in sl:
 158             assert(bits <= 32)
 159             stacks[0].append(('100644', sha, size))
 160             if bits > base_bits:
 161                 _squish(w, stacks, bits_to_idx(bits))
 162         #log('stacks: %r\n' % [len(i) for i in stacks])
 163         _squish(w, stacks, len(stacks)-1)
 164         #log('stacks: %r\n' % [len(i) for i in stacks])
 165         return _make_shalist(stacks[-1])[0]
 166
 167
 168 def split_to_blob_or_tree(w, files, keep_boundaries):
 169     shalist = list(split_to_shalist(w, files, keep_boundaries))
 170     if len(shalist) == 1:
 171         return (shalist[0][0], shalist[0][2])
 172     elif len(shalist) == 0:
 173         return ('100644', w.new_blob(''))
 174     else:
 175         return ('40000', w.new_tree(shalist))
 176
 177
 178 def open_noatime(name):
 179     fd = _helpers.open_noatime(name)
 180     try:
 181         return os.fdopen(fd, 'rb', 1024*1024)
 182     except:
 183         try:
 184             os.close(fd)
 185         except:
 186             pass
 187         raise
 188
 189
 190 def fadvise_done(f, ofs):
 191     assert(ofs >= 0)
 192     if ofs > 0:
 193         _helpers.fadvise_done(f.fileno(), ofs)