src/allmydata/dirnode.py

   1
   2 import os, time, math
   3
   4 from zope.interface import implements
   5 from twisted.internet import defer
   6 import simplejson
   7 from allmydata.mutable.common import NotMutableError
   8 from allmydata.mutable.filenode import MutableFileNode
   9 from allmydata.interfaces import IMutableFileNode, IDirectoryNode,\
  10      IURI, IFileNode, IMutableFileURI, IFilesystemNode, \
  11      ExistingChildError, NoSuchChildError, ICheckable, IDeepCheckable
  12 from allmydata.check_results import DeepCheckResults, \
  13      DeepCheckAndRepairResults
  14 from allmydata.monitor import Monitor
  15 from allmydata.util import hashutil, mathutil, base32, log
  16 from allmydata.util.assertutil import _assert, precondition
  17 from allmydata.util.hashutil import netstring
  18 from allmydata.util.netstring import split_netstring
  19 from allmydata.uri import NewDirectoryURI, LiteralFileURI, from_string
  20 from pycryptopp.cipher.aes import AES
  21
  22 class Deleter:
  23     def __init__(self, node, name, must_exist=True):
  24         self.node = node
  25         self.name = name
  26         self.must_exist = True
  27     def modify(self, old_contents, servermap, first_time):
  28         children = self.node._unpack_contents(old_contents)
  29         if self.name not in children:
  30             if first_time and self.must_exist:
  31                 raise NoSuchChildError(self.name)
  32             self.old_child = None
  33             return None
  34         self.old_child, metadata = children[self.name]
  35         del children[self.name]
  36         new_contents = self.node._pack_contents(children)
  37         return new_contents
  38
  39 class MetadataSetter:
  40     def __init__(self, node, name, metadata):
  41         self.node = node
  42         self.name = name
  43         self.metadata = metadata
  44
  45     def modify(self, old_contents, servermap, first_time):
  46         children = self.node._unpack_contents(old_contents)
  47         if self.name not in children:
  48             raise NoSuchChildError(self.name)
  49         children[self.name] = (children[self.name][0], self.metadata)
  50         new_contents = self.node._pack_contents(children)
  51         return new_contents
  52
  53
  54 class Adder:
  55     def __init__(self, node, entries=None, overwrite=True):
  56         self.node = node
  57         if entries is None:
  58             entries = []
  59         self.entries = entries
  60         self.overwrite = overwrite
  61
  62     def set_node(self, name, node, metadata):
  63         precondition(isinstance(name, unicode), name)
  64         precondition(IFilesystemNode.providedBy(node), node)
  65         self.entries.append( [name, node, metadata] )
  66
  67     def modify(self, old_contents, servermap, first_time):
  68         children = self.node._unpack_contents(old_contents)
  69         now = time.time()
  70         for e in self.entries:
  71             if len(e) == 2:
  72                 name, child = e
  73                 new_metadata = None
  74             else:
  75                 assert len(e) == 3
  76                 name, child, new_metadata = e
  77                 assert _assert(IFilesystemNode.providedBy(child), child)
  78             assert isinstance(name, unicode)
  79             if name in children:
  80                 if not self.overwrite:
  81                     raise ExistingChildError("child '%s' already exists" % name)
  82                 metadata = children[name][1].copy()
  83             else:
  84                 metadata = {"ctime": now,
  85                             "mtime": now}
  86             if new_metadata is None:
  87                 # update timestamps
  88                 if "ctime" not in metadata:
  89                     metadata["ctime"] = now
  90                 metadata["mtime"] = now
  91             else:
  92                 # just replace it
  93                 metadata = new_metadata.copy()
  94             children[name] = (child, metadata)
  95         new_contents = self.node._pack_contents(children)
  96         return new_contents
  97
  98 class NewDirectoryNode:
  99     implements(IDirectoryNode, ICheckable, IDeepCheckable)
 100     filenode_class = MutableFileNode
 101
 102     def __init__(self, client):
 103         self._client = client
 104         self._most_recent_size = None
 105
 106     def __repr__(self):
 107         return "<%s %s %s>" % (self.__class__.__name__, self.is_readonly() and "RO" or "RW", hasattr(self, '_uri') and self._uri.abbrev())
 108     def init_from_uri(self, myuri):
 109         self._uri = IURI(myuri)
 110         self._node = self.filenode_class(self._client)
 111         self._node.init_from_uri(self._uri.get_filenode_uri())
 112         return self
 113
 114     def create(self, keypair_generator=None):
 115         """
 116         Returns a deferred that eventually fires with self once the directory
 117         has been created (distributed across a set of storage servers).
 118         """
 119         # first we create a MutableFileNode with empty_contents, then use its
 120         # URI to create our own.
 121         self._node = self.filenode_class(self._client)
 122         empty_contents = self._pack_contents({})
 123         d = self._node.create(empty_contents, keypair_generator)
 124         d.addCallback(self._filenode_created)
 125         return d
 126     def _filenode_created(self, res):
 127         self._uri = NewDirectoryURI(IMutableFileURI(self._node.get_uri()))
 128         return self
 129
 130     def get_size(self):
 131         # return the size of our backing mutable file, in bytes, if we've
 132         # fetched it.
 133         return self._most_recent_size
 134
 135     def _set_size(self, data):
 136         self._most_recent_size = len(data)
 137         return data
 138
 139     def _read(self):
 140         d = self._node.download_best_version()
 141         d.addCallback(self._set_size)
 142         d.addCallback(self._unpack_contents)
 143         return d
 144
 145     def _encrypt_rwcap(self, rwcap):
 146         assert isinstance(rwcap, str)
 147         IV = os.urandom(16)
 148         key = hashutil.mutable_rwcap_key_hash(IV, self._node.get_writekey())
 149         cryptor = AES(key)
 150         crypttext = cryptor.process(rwcap)
 151         mac = hashutil.hmac(key, IV + crypttext)
 152         assert len(mac) == 32
 153         return IV + crypttext + mac
 154         # The MAC is not checked by readers in Tahoe >= 1.3.0, but we still produce it for the sake of older readers.
 155
 156     def _decrypt_rwcapdata(self, encwrcap):
 157         IV = encwrcap[:16]
 158         crypttext = encwrcap[16:-32]
 159         key = hashutil.mutable_rwcap_key_hash(IV, self._node.get_writekey())
 160         cryptor = AES(key)
 161         plaintext = cryptor.process(crypttext)
 162         return plaintext
 163
 164     def _create_node(self, child_uri):
 165         return self._client.create_node_from_uri(child_uri)
 166
 167     def _unpack_contents(self, data):
 168         # the directory is serialized as a list of netstrings, one per child.
 169         # Each child is serialized as a list of four netstrings: (name,
 170         # rocap, rwcap, metadata), in which the name,rocap,metadata are in
 171         # cleartext. The 'name' is UTF-8 encoded. The rwcap is formatted as:
 172         # pack("16ss32s", iv, AES(H(writekey+iv), plaintextrwcap), mac)
 173         assert isinstance(data, str)
 174         # an empty directory is serialized as an empty string
 175         if data == "":
 176             return {}
 177         writeable = not self.is_readonly()
 178         children = {}
 179         while len(data) > 0:
 180             entry, data = split_netstring(data, 1, True)
 181             name, rocap, rwcapdata, metadata_s = split_netstring(entry, 4)
 182             name = name.decode("utf-8")
 183             if writeable:
 184                 rwcap = self._decrypt_rwcapdata(rwcapdata)
 185                 child = self._create_node(rwcap)
 186             else:
 187                 child = self._create_node(rocap)
 188             metadata = simplejson.loads(metadata_s)
 189             assert isinstance(metadata, dict)
 190             children[name] = (child, metadata)
 191         return children
 192
 193     def _pack_contents(self, children):
 194         # expects children in the same format as _unpack_contents
 195         assert isinstance(children, dict)
 196         entries = []
 197         for name in sorted(children.keys()):
 198             child, metadata = children[name]
 199             assert isinstance(name, unicode)
 200             assert (IFileNode.providedBy(child)
 201                     or IMutableFileNode.providedBy(child)
 202                     or IDirectoryNode.providedBy(child)), (name,child)
 203             assert isinstance(metadata, dict)
 204             rwcap = child.get_uri() # might be RO if the child is not writeable
 205             assert isinstance(rwcap, str), rwcap
 206             rocap = child.get_readonly_uri()
 207             assert isinstance(rocap, str), rocap
 208             entry = "".join([netstring(name.encode("utf-8")),
 209                              netstring(rocap),
 210                              netstring(self._encrypt_rwcap(rwcap)),
 211                              netstring(simplejson.dumps(metadata))])
 212             entries.append(netstring(entry))
 213         return "".join(entries)
 214
 215     def is_readonly(self):
 216         return self._node.is_readonly()
 217     def is_mutable(self):
 218         return self._node.is_mutable()
 219
 220     def get_uri(self):
 221         return self._uri.to_string()
 222
 223     def get_readonly_uri(self):
 224         return self._uri.get_readonly().to_string()
 225
 226     def get_verify_cap(self):
 227         return self._uri.get_verify_cap()
 228
 229     def get_repair_cap(self):
 230         if self._node.is_readonly():
 231             return None
 232         return self._uri
 233
 234     def get_storage_index(self):
 235         return self._uri._filenode_uri.storage_index
 236
 237     def check(self, monitor, verify=False):
 238         """Perform a file check. See IChecker.check for details."""
 239         return self._node.check(monitor, verify)
 240     def check_and_repair(self, monitor, verify=False):
 241         return self._node.check_and_repair(monitor, verify)
 242
 243     def list(self):
 244         """I return a Deferred that fires with a dictionary mapping child
 245         name to a tuple of (IFileNode or IDirectoryNode, metadata)."""
 246         return self._read()
 247
 248     def has_child(self, name):
 249         """I return a Deferred that fires with a boolean, True if there
 250         exists a child of the given name, False if not."""
 251         assert isinstance(name, unicode)
 252         d = self._read()
 253         d.addCallback(lambda children: children.has_key(name))
 254         return d
 255
 256     def _get(self, children, name):
 257         child = children.get(name)
 258         if child is None:
 259             raise NoSuchChildError(name)
 260         return child[0]
 261
 262     def _get_with_metadata(self, children, name):
 263         child = children.get(name)
 264         if child is None:
 265             raise NoSuchChildError(name)
 266         return child
 267
 268     def get(self, name):
 269         """I return a Deferred that fires with the named child node,
 270         which is either an IFileNode or an IDirectoryNode."""
 271         assert isinstance(name, unicode)
 272         d = self._read()
 273         d.addCallback(self._get, name)
 274         return d
 275
 276     def get_child_and_metadata(self, name):
 277         """I return a Deferred that fires with the (node, metadata) pair for
 278         the named child. The node is either an IFileNode or an
 279         IDirectoryNode, and the metadata is a dictionary."""
 280         assert isinstance(name, unicode)
 281         d = self._read()
 282         d.addCallback(self._get_with_metadata, name)
 283         return d
 284
 285     def get_metadata_for(self, name):
 286         assert isinstance(name, unicode)
 287         d = self._read()
 288         d.addCallback(lambda children: children[name][1])
 289         return d
 290
 291     def set_metadata_for(self, name, metadata):
 292         assert isinstance(name, unicode)
 293         if self.is_readonly():
 294             return defer.fail(NotMutableError())
 295         assert isinstance(metadata, dict)
 296         s = MetadataSetter(self, name, metadata)
 297         d = self._node.modify(s.modify)
 298         d.addCallback(lambda res: self)
 299         return d
 300
 301     def get_child_at_path(self, path):
 302         """Transform a child path into an IDirectoryNode or IFileNode.
 303
 304         I perform a recursive series of 'get' operations to find the named
 305         descendant node. I return a Deferred that fires with the node, or
 306         errbacks with IndexError if the node could not be found.
 307
 308         The path can be either a single string (slash-separated) or a list of
 309         path-name elements.
 310         """
 311         d = self.get_child_and_metadata_at_path(path)
 312         d.addCallback(lambda (node, metadata): node)
 313         return d
 314
 315     def get_child_and_metadata_at_path(self, path):
 316         """Transform a child path into an IDirectoryNode or IFileNode and
 317         a metadata dictionary from the last edge that was traversed.
 318         """
 319
 320         if not path:
 321             return defer.succeed((self, {}))
 322         if isinstance(path, (list, tuple)):
 323             pass
 324         else:
 325             path = path.split("/")
 326         for p in path:
 327             assert isinstance(p, unicode)
 328         childname = path[0]
 329         remaining_path = path[1:]
 330         if remaining_path:
 331             d = self.get(childname)
 332             d.addCallback(lambda node:
 333                           node.get_child_and_metadata_at_path(remaining_path))
 334             return d
 335         d = self.get_child_and_metadata(childname)
 336         return d
 337
 338     def set_uri(self, name, child_uri, metadata=None, overwrite=True):
 339         """I add a child (by URI) at the specific name. I return a Deferred
 340         that fires with the child node when the operation finishes. I will
 341         replace any existing child of the same name.
 342
 343         The child_uri could be for a file, or for a directory (either
 344         read-write or read-only, using a URI that came from get_uri() ).
 345
 346         If this directory node is read-only, the Deferred will errback with a
 347         NotMutableError."""
 348         precondition(isinstance(name, unicode), name)
 349         precondition(isinstance(child_uri, str), child_uri)
 350         child_node = self._create_node(child_uri)
 351         d = self.set_node(name, child_node, metadata, overwrite)
 352         d.addCallback(lambda res: child_node)
 353         return d
 354
 355     def set_children(self, entries, overwrite=True):
 356         # this takes URIs
 357         a = Adder(self, overwrite=overwrite)
 358         node_entries = []
 359         for e in entries:
 360             if len(e) == 2:
 361                 name, child_uri = e
 362                 metadata = None
 363             else:
 364                 assert len(e) == 3
 365                 name, child_uri, metadata = e
 366             assert isinstance(name, unicode)
 367             a.set_node(name, self._create_node(child_uri), metadata)
 368         return self._node.modify(a.modify)
 369
 370     def set_node(self, name, child, metadata=None, overwrite=True):
 371         """I add a child at the specific name. I return a Deferred that fires
 372         when the operation finishes. This Deferred will fire with the child
 373         node that was just added. I will replace any existing child of the
 374         same name.
 375
 376         If this directory node is read-only, the Deferred will errback with a
 377         NotMutableError."""
 378
 379         precondition(IFilesystemNode.providedBy(child), child)
 380
 381         if self.is_readonly():
 382             return defer.fail(NotMutableError())
 383         assert isinstance(name, unicode)
 384         assert IFilesystemNode.providedBy(child), child
 385         a = Adder(self, overwrite=overwrite)
 386         a.set_node(name, child, metadata)
 387         d = self._node.modify(a.modify)
 388         d.addCallback(lambda res: child)
 389         return d
 390
 391     def set_nodes(self, entries, overwrite=True):
 392         if self.is_readonly():
 393             return defer.fail(NotMutableError())
 394         a = Adder(self, entries, overwrite=overwrite)
 395         d = self._node.modify(a.modify)
 396         d.addCallback(lambda res: None)
 397         return d
 398
 399
 400     def add_file(self, name, uploadable, metadata=None, overwrite=True):
 401         """I upload a file (using the given IUploadable), then attach the
 402         resulting FileNode to the directory at the given name. I return a
 403         Deferred that fires (with the IFileNode of the uploaded file) when
 404         the operation completes."""
 405         assert isinstance(name, unicode)
 406         if self.is_readonly():
 407             return defer.fail(NotMutableError())
 408         d = self._client.upload(uploadable)
 409         d.addCallback(lambda results: results.uri)
 410         d.addCallback(self._client.create_node_from_uri)
 411         d.addCallback(lambda node:
 412                       self.set_node(name, node, metadata, overwrite))
 413         return d
 414
 415     def delete(self, name):
 416         """I remove the child at the specific name. I return a Deferred that
 417         fires (with the node just removed) when the operation finishes."""
 418         assert isinstance(name, unicode)
 419         if self.is_readonly():
 420             return defer.fail(NotMutableError())
 421         deleter = Deleter(self, name)
 422         d = self._node.modify(deleter.modify)
 423         d.addCallback(lambda res: deleter.old_child)
 424         return d
 425
 426     def create_empty_directory(self, name, overwrite=True):
 427         """I create and attach an empty directory at the given name. I return
 428         a Deferred that fires (with the new directory node) when the
 429         operation finishes."""
 430         assert isinstance(name, unicode)
 431         if self.is_readonly():
 432             return defer.fail(NotMutableError())
 433         d = self._client.create_empty_dirnode()
 434         def _created(child):
 435             entries = [(name, child, None)]
 436             a = Adder(self, entries, overwrite=overwrite)
 437             d = self._node.modify(a.modify)
 438             d.addCallback(lambda res: child)
 439             return d
 440         d.addCallback(_created)
 441         return d
 442
 443     def move_child_to(self, current_child_name, new_parent,
 444                       new_child_name=None, overwrite=True):
 445         """I take one of my children and move them to a new parent. The child
 446         is referenced by name. On the new parent, the child will live under
 447         'new_child_name', which defaults to 'current_child_name'. I return a
 448         Deferred that fires when the operation finishes."""
 449         assert isinstance(current_child_name, unicode)
 450         if self.is_readonly() or new_parent.is_readonly():
 451             return defer.fail(NotMutableError())
 452         if new_child_name is None:
 453             new_child_name = current_child_name
 454         assert isinstance(new_child_name, unicode)
 455         d = self.get(current_child_name)
 456         def sn(child):
 457             return new_parent.set_node(new_child_name, child,
 458                                        overwrite=overwrite)
 459         d.addCallback(sn)
 460         d.addCallback(lambda child: self.delete(current_child_name))
 461         return d
 462
 463
 464     def deep_traverse(self, walker):
 465         """Perform a recursive walk, using this dirnode as a root, notifying
 466         the 'walker' instance of everything I encounter.
 467
 468         I call walker.enter_directory(parent, children) once for each dirnode
 469         I visit, immediately after retrieving the list of children. I pass in
 470         the parent dirnode and the dict of childname->(childnode,metadata).
 471         This function should *not* traverse the children: I will do that.
 472         enter_directory() is most useful for the deep-stats number that
 473         counts how large a directory is.
 474
 475         I call walker.add_node(node, path) for each node (both files and
 476         directories) I can reach. Most work should be done here.
 477
 478         I avoid loops by keeping track of verifier-caps and refusing to call
 479         walker.add_node() or traverse a node that I've seen before. This
 480         means that any file or directory will only be given to the walker
 481         once. If files or directories are referenced multiple times by a
 482         directory structure, this may appear to under-count or miss some of
 483         them.
 484
 485         I return a Monitor which can be used to wait for the operation to
 486         finish, learn about its progress, or cancel the operation.
 487         """
 488
 489         # this is just a tree-walker, except that following each edge
 490         # requires a Deferred. We used to use a ConcurrencyLimiter to limit
 491         # fanout to 10 simultaneous operations, but the memory load of the
 492         # queued operations was excessive (in one case, with 330k dirnodes,
 493         # it caused the process to run into the 3.0GB-ish per-process 32bit
 494         # linux memory limit, and crashed). So we use a single big Deferred
 495         # chain, and do a strict depth-first traversal, one node at a time.
 496         # This can be slower, because we aren't pipelining directory reads,
 497         # but it brought the memory footprint down by roughly 50%.
 498
 499         monitor = Monitor()
 500         walker.set_monitor(monitor)
 501
 502         found = set([self.get_verify_cap()])
 503         d = self._deep_traverse_dirnode(self, [], walker, monitor, found)
 504         d.addCallback(lambda ignored: walker.finish())
 505         d.addBoth(monitor.finish)
 506         d.addErrback(lambda f: None)
 507
 508         return monitor
 509
 510     def _deep_traverse_dirnode(self, node, path, walker, monitor, found):
 511         # process this directory, then walk its children
 512         monitor.raise_if_cancelled()
 513         d = defer.maybeDeferred(walker.add_node, node, path)
 514         d.addCallback(lambda ignored: node.list())
 515         d.addCallback(self._deep_traverse_dirnode_children, node, path,
 516                       walker, monitor, found)
 517         return d
 518
 519     def _deep_traverse_dirnode_children(self, children, parent, path,
 520                                         walker, monitor, found):
 521         monitor.raise_if_cancelled()
 522         d = defer.maybeDeferred(walker.enter_directory, parent, children)
 523         # we process file-like children first, so we can drop their FileNode
 524         # objects as quickly as possible. Tests suggest that a FileNode (held
 525         # in the client's nodecache) consumes about 2440 bytes. dirnodes (not
 526         # in the nodecache) seem to consume about 2000 bytes.
 527         dirkids = []
 528         filekids = []
 529         for name, (child, metadata) in children.iteritems():
 530             verifier = child.get_verify_cap()
 531             # allow LIT files (for which verifier==None) to be processed
 532             if (verifier is not None) and (verifier in found):
 533                 continue
 534             found.add(verifier)
 535             childpath = path + [name]
 536             if IDirectoryNode.providedBy(child):
 537                 dirkids.append( (child, childpath) )
 538             else:
 539                 filekids.append( (child, childpath) )
 540         for (child, childpath) in filekids:
 541             d.addCallback(lambda ignored, child=child, childpath=childpath:
 542                           walker.add_node(child, childpath))
 543         for (child, childpath) in dirkids:
 544             d.addCallback(lambda ignored, child=child, childpath=childpath:
 545                           self._deep_traverse_dirnode(child, childpath,
 546                                                       walker, monitor,
 547                                                       found))
 548         return d
 549
 550
 551     def build_manifest(self):
 552         """Return a Monitor, with a ['status'] that will be a list of (path,
 553         cap) tuples, for all nodes (directories and files) reachable from
 554         this one."""
 555         walker = ManifestWalker(self)
 556         return self.deep_traverse(walker)
 557
 558     def start_deep_stats(self):
 559         # Since deep_traverse tracks verifier caps, we avoid double-counting
 560         # children for which we've got both a write-cap and a read-cap
 561         return self.deep_traverse(DeepStats(self))
 562
 563     def start_deep_check(self, verify=False):
 564         return self.deep_traverse(DeepChecker(self, verify, repair=False))
 565
 566     def start_deep_check_and_repair(self, verify=False):
 567         return self.deep_traverse(DeepChecker(self, verify, repair=True))
 568
 569
 570
 571 class DeepStats:
 572     def __init__(self, origin):
 573         self.origin = origin
 574         self.stats = {}
 575         for k in ["count-immutable-files",
 576                   "count-mutable-files",
 577                   "count-literal-files",
 578                   "count-files",
 579                   "count-directories",
 580                   "size-immutable-files",
 581                   #"size-mutable-files",
 582                   "size-literal-files",
 583                   "size-directories",
 584                   "largest-directory",
 585                   "largest-directory-children",
 586                   "largest-immutable-file",
 587                   #"largest-mutable-file",
 588                   ]:
 589             self.stats[k] = 0
 590         self.histograms = {}
 591         for k in ["size-files-histogram"]:
 592             self.histograms[k] = {} # maps (min,max) to count
 593         self.buckets = [ (0,0), (1,3)]
 594         self.root = math.sqrt(10)
 595
 596     def set_monitor(self, monitor):
 597         self.monitor = monitor
 598         monitor.origin_si = self.origin.get_storage_index()
 599         monitor.set_status(self.get_results())
 600
 601     def add_node(self, node, childpath):
 602         if IDirectoryNode.providedBy(node):
 603             self.add("count-directories")
 604         elif IMutableFileNode.providedBy(node):
 605             self.add("count-files")
 606             self.add("count-mutable-files")
 607             # TODO: update the servermap, compute a size, add it to
 608             # size-mutable-files, max it into "largest-mutable-file"
 609         elif IFileNode.providedBy(node): # CHK and LIT
 610             self.add("count-files")
 611             size = node.get_size()
 612             self.histogram("size-files-histogram", size)
 613             theuri = from_string(node.get_uri())
 614             if isinstance(theuri, LiteralFileURI):
 615                 self.add("count-literal-files")
 616                 self.add("size-literal-files", size)
 617             else:
 618                 self.add("count-immutable-files")
 619                 self.add("size-immutable-files", size)
 620                 self.max("largest-immutable-file", size)
 621
 622     def enter_directory(self, parent, children):
 623         dirsize_bytes = parent.get_size()
 624         dirsize_children = len(children)
 625         self.add("size-directories", dirsize_bytes)
 626         self.max("largest-directory", dirsize_bytes)
 627         self.max("largest-directory-children", dirsize_children)
 628
 629     def add(self, key, value=1):
 630         self.stats[key] += value
 631
 632     def max(self, key, value):
 633         self.stats[key] = max(self.stats[key], value)
 634
 635     def which_bucket(self, size):
 636         # return (min,max) such that min <= size <= max
 637         # values are from the set (0,0), (1,3), (4,10), (11,31), (32,100),
 638         # (101,316), (317, 1000), etc: two per decade
 639         assert size >= 0
 640         i = 0
 641         while True:
 642             if i >= len(self.buckets):
 643                 # extend the list
 644                 new_lower = self.buckets[i-1][1]+1
 645                 new_upper = int(mathutil.next_power_of_k(new_lower, self.root))
 646                 self.buckets.append( (new_lower, new_upper) )
 647             maybe = self.buckets[i]
 648             if maybe[0] <= size <= maybe[1]:
 649                 return maybe
 650             i += 1
 651
 652     def histogram(self, key, size):
 653         bucket = self.which_bucket(size)
 654         h = self.histograms[key]
 655         if bucket not in h:
 656             h[bucket] = 0
 657         h[bucket] += 1
 658
 659     def get_results(self):
 660         stats = self.stats.copy()
 661         for key in self.histograms:
 662             h = self.histograms[key]
 663             out = [ (bucket[0], bucket[1], h[bucket]) for bucket in h ]
 664             out.sort()
 665             stats[key] = out
 666         return stats
 667
 668     def finish(self):
 669         return self.get_results()
 670
 671 class ManifestWalker(DeepStats):
 672     def __init__(self, origin):
 673         DeepStats.__init__(self, origin)
 674         self.manifest = []
 675         self.storage_index_strings = set()
 676         self.verifycaps = set()
 677
 678     def add_node(self, node, path):
 679         self.manifest.append( (tuple(path), node.get_uri()) )
 680         si = node.get_storage_index()
 681         if si:
 682             self.storage_index_strings.add(base32.b2a(si))
 683         v = node.get_verify_cap()
 684         if v:
 685             self.verifycaps.add(v.to_string())
 686         return DeepStats.add_node(self, node, path)
 687
 688     def get_results(self):
 689         stats = DeepStats.get_results(self)
 690         return {"manifest": self.manifest,
 691                 "verifycaps": self.verifycaps,
 692                 "storage-index": self.storage_index_strings,
 693                 "stats": stats,
 694                 }
 695
 696
 697 class DeepChecker:
 698     def __init__(self, root, verify, repair):
 699         root_si = root.get_storage_index()
 700         self._lp = log.msg(format="deep-check starting (%(si)s),"
 701                            " verify=%(verify)s, repair=%(repair)s",
 702                            si=base32.b2a(root_si), verify=verify, repair=repair)
 703         self._verify = verify
 704         self._repair = repair
 705         if repair:
 706             self._results = DeepCheckAndRepairResults(root_si)
 707         else:
 708             self._results = DeepCheckResults(root_si)
 709         self._stats = DeepStats(root)
 710
 711     def set_monitor(self, monitor):
 712         self.monitor = monitor
 713         monitor.set_status(self._results)
 714
 715     def add_node(self, node, childpath):
 716         if self._repair:
 717             d = node.check_and_repair(self.monitor, self._verify)
 718             d.addCallback(self._results.add_check_and_repair, childpath)
 719         else:
 720             d = node.check(self.monitor, self._verify)
 721             d.addCallback(self._results.add_check, childpath)
 722         d.addCallback(lambda ignored: self._stats.add_node(node, childpath))
 723         return d
 724
 725     def enter_directory(self, parent, children):
 726         return self._stats.enter_directory(parent, children)
 727
 728     def finish(self):
 729         log.msg("deep-check done", parent=self._lp)
 730         self._results.update_stats(self._stats.get_results())
 731         return self._results
 732
 733
 734 # use client.create_dirnode() to make one of these
 735
 736