python/cumulus/metadata.py

   1 # Cumulus: Efficient Filesystem Backup to the Cloud
   2 # Copyright (C) 2008 The Cumulus Developers
   3 # See the AUTHORS file for a list of contributors.
   4 #
   5 # This program is free software; you can redistribute it and/or modify
   6 # it under the terms of the GNU General Public License as published by
   7 # the Free Software Foundation; either version 2 of the License, or
   8 # (at your option) any later version.
   9 #
  10 # This program is distributed in the hope that it will be useful,
  11 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 # GNU General Public License for more details.
  14 #
  15 # You should have received a copy of the GNU General Public License along
  16 # with this program; if not, write to the Free Software Foundation, Inc.,
  17 # 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  18
  19 """Advanced metadata iterator for Cumulus snapshots.
  20
  21 Allow fast random access to Cumulus metadata logs.  This requires that the
  22 underlying metadata log have been generated by a depth-first-search traversal
  23 of the filesystem, in sorted order.
  24 """
  25
  26 import cumulus
  27
  28 class Metadata:
  29     def __init__(self, object_store, root):
  30         self.store = object_store
  31         self.root = root
  32
  33     def _load(self, ref):
  34         """Return the contents of the given object, as a list of text lines."""
  35
  36         data = self.store.get(ref)
  37         return data.splitlines()
  38
  39     def _read(self, ptr):
  40         """Parse the metadata item at the given address and return it."""
  41
  42         if ptr is None or ptr == []: return {}
  43
  44         (ref, n) = ptr[-1]
  45         lines = self._load(ref)[n:]
  46
  47         try:
  48             return cumulus.parse(lines, lambda l: len(l) == 0).next()
  49         except StopIteration:
  50             return {}
  51
  52     def _advance(self, ptr):
  53         """Advance the specified metadata pointer to the next metadata item."""
  54
  55         if ptr == None:
  56             return None
  57
  58         advanced = False
  59         ptr = list(ptr)
  60         if ptr == []:
  61             ptr.append((self.root, 0))
  62             advanced = True
  63
  64         while True:
  65             last = ptr.pop(-1)
  66             lines = self._load(last[0])
  67
  68             # Reached the end of the current object?  Advance pointer by one
  69             # line in the containing object (or return None if reached the very
  70             # end of input).
  71             if last[1] >= len(lines):
  72                 if ptr == []: return None
  73                 last = ptr.pop(-1)
  74                 ptr.append((last[0], last[1] + 1))
  75                 advanced = True
  76                 continue
  77
  78             # Reached a line with an indirect reference?  Recurse.
  79             line = lines[last[1]]
  80             if line.startswith('@'):
  81                 ptr.append(last)
  82                 ptr.append((line[1:], 0))
  83                 advanced = True
  84                 continue
  85
  86             # Skip over blank lines.
  87             if line == "":
  88                 ptr.append((last[0], last[1] + 1))
  89                 advanced = True
  90                 continue
  91
  92             # Skip over the remainder of a metadata stanza, if we started in
  93             # the middle of one.
  94             if not advanced:
  95                 ptr.append((last[0], last[1] + 1))
  96                 continue
  97
  98             # Done!  Found a non-blank line which is not an indirect reference.
  99             ptr.append(last)
 100             return ptr
 101
 102     def _cmp(self, ptr1, ptr2):
 103         if ptr1 is None and ptr2 is None: return 0
 104         if ptr1 is None: return 1
 105         if ptr2 is None: return -1
 106         return cmp(ptr1, ptr2)
 107
 108     def _get_path(self, metadata):
 109         if metadata is None or 'name' not in metadata:
 110             return None
 111         path = metadata['name']
 112         path = cumulus.MetadataItem.decode_str(path)
 113         if path == '.': return []
 114         return path.split('/')
 115
 116     def _midpoint(self, ptr1, ptr2):
 117         """Return a pointer to some metadata item in the range [ptr1, ptr2)."""
 118
 119         if ptr1 == []: ptr1 = self._advance([])
 120         if ptr1 is None: return None
 121         if self._cmp(ptr1, ptr2) > 0: return None
 122
 123         #print "ptr1:", ptr1
 124         #print "ptr2:", ptr2
 125
 126         level = 0
 127         while True:
 128             if level >= len(ptr1): return ptr1
 129
 130             if ptr2 is not None and level < len(ptr2) and ptr1[level] == ptr2[level]:
 131                 level += 1
 132                 continue
 133
 134             midpoint = ptr1[0:level]
 135             lastref = ptr1[level][0]
 136             limit = len(self._load(lastref))
 137             if ptr2 is not None and level < len(ptr2) \
 138                     and ptr1[level][0] == ptr2[level][0]:
 139                 limit = ptr2[level][1]
 140             midpoint.append((lastref, (ptr1[level][1] + limit) // 2))
 141
 142             if self._cmp(midpoint, ptr1) < 0:
 143                 #print "    ...descend"
 144                 level += 1
 145                 continue
 146
 147             #print "Guess midpoint:", midpoint
 148             midpoint = self._advance(midpoint)
 149             #print "    ...advanced to", midpoint
 150
 151             if self._cmp(midpoint, ptr2) >= 0:
 152                 #print "    ...overshoot, trying again"
 153                 level += 1
 154                 continue
 155
 156             return midpoint
 157
 158     def search(self, searchfunc, ptr1=[], ptr2=None):
 159         """Perform a binary search for name.
 160
 161         The search is restricted to the interval [ptr1, ptr2).  Return either a
 162         pointer to the item for name, or if it doesn't exist the pointer to the
 163         item which follows where it would have been (assuming the original
 164         search interval included that location)."""
 165
 166         def _printable(ptr):
 167             if ptr is None: return None
 168             return tuple(x[1] for x in ptr)
 169
 170         while True:
 171             #print _printable(ptr1), "...", _printable(ptr2)
 172             if self._cmp(ptr1, ptr2) >= 0:
 173                 #print "    X", _printable(ptr1)
 174                 return ptr1
 175
 176             mid = self._midpoint(ptr1, ptr2)
 177             midpath = self._get_path(self._read(mid))
 178
 179             c = searchfunc(midpath)
 180             if c == 0:
 181                 #print "    =", _printable(mid), midpath
 182                 return mid
 183             elif c < 0:
 184                 #print "    >", _printable(mid), midpath
 185                 ptr1 = self._advance(mid)
 186             else:
 187                 #print "    <", _printable(mid), midpath
 188                 ptr2 = mid
 189
 190 if __name__ == '__main__':
 191     import cumulus
 192
 193     store = cumulus.ObjectStore(cumulus.LowlevelDataStore('/backups/lbs/turin'))
 194     root = '9e0be287-a74c-4527-aa26-0a10e8f40f7d/00000243(sha1=316e034bb5b86e5ba00b1d54335427d7b742f4f9)'
 195
 196     metadata = Metadata(store, root)
 197     ptr = metadata.search(['home', 'mvrable', 'docs'])
 198     print ptr
 199     print metadata._read(ptr)
 200     store.cleanup()