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 total_split = 0
  93 def _split_to_blobs(w, files):
  94     global total_split
  95     for (blob, bits) in hashsplit_iter(files):
  96         sha = w.new_blob(blob)
  97         total_split += len(blob)
  98         if w.outbytes >= max_pack_size or w.count >= max_pack_objects:
  99             w.breakpoint()
 100         if progress_callback:
 101             progress_callback(len(blob))
 102         yield (sha, len(blob), bits)
 103
 104
 105 def _make_shalist(l):
 106     ofs = 0
 107     shalist = []
 108     for (mode, sha, size) in l:
 109         shalist.append((mode, '%016x' % ofs, sha))
 110         ofs += size
 111     total = ofs
 112     return (shalist, total)
 113
 114
 115 def _squish(w, stacks, n):
 116     i = 0
 117     while i<n or len(stacks[i]) > MAX_PER_TREE:
 118         while len(stacks) <= i+1:
 119             stacks.append([])
 120         if len(stacks[i]) == 1:
 121             stacks[i+1] += stacks[i]
 122         elif stacks[i]:
 123             (shalist, size) = _make_shalist(stacks[i])
 124             tree = w.new_tree(shalist)
 125             stacks[i+1].append(('40000', tree, size))
 126         stacks[i] = []
 127         i += 1
 128
 129
 130 def split_to_shalist(w, files):
 131     sl = _split_to_blobs(w, files)
 132     if not fanout:
 133         shal = []
 134         for (sha,size,bits) in sl:
 135             shal.append(('100644', sha, size))
 136         return _make_shalist(shal)[0]
 137     else:
 138         base_bits = _helpers.blobbits()
 139         fanout_bits = int(math.log(fanout, 2))
 140         def bits_to_idx(n):
 141             assert(n >= base_bits)
 142             return (n - base_bits)/fanout_bits
 143         stacks = [[]]
 144         for (sha,size,bits) in sl:
 145             assert(bits <= 32)
 146             stacks[0].append(('100644', sha, size))
 147             if bits > base_bits:
 148                 _squish(w, stacks, bits_to_idx(bits))
 149         #log('stacks: %r\n' % [len(i) for i in stacks])
 150         _squish(w, stacks, len(stacks)-1)
 151         #log('stacks: %r\n' % [len(i) for i in stacks])
 152         return _make_shalist(stacks[-1])[0]
 153
 154
 155 def split_to_blob_or_tree(w, files):
 156     shalist = list(split_to_shalist(w, files))
 157     if len(shalist) == 1:
 158         return (shalist[0][0], shalist[0][2])
 159     elif len(shalist) == 0:
 160         return ('100644', w.new_blob(''))
 161     else:
 162         return ('40000', w.new_tree(shalist))
 163
 164
 165 def open_noatime(name):
 166     fd = _helpers.open_noatime(name)
 167     try:
 168         return os.fdopen(fd, 'rb', 1024*1024)
 169     except:
 170         try:
 171             os.close(fd)
 172         except:
 173             pass
 174         raise
 175
 176
 177 def fadvise_done(f, ofs):
 178     assert(ofs >= 0)
 179     if ofs > 0:
 180         _helpers.fadvise_done(f.fileno(), ofs)