def __init__(self, allow_writes, fs, storedir):
        logging.debug('Initializing Journal for %s' % storedir)
        self.allow_writes = allow_writes
        self.fs = fs
        self.storedir = storedir
        if not self.storedir.endswith(os.sep):
            self.storedir += os.sep
        self.newdir = os.path.join(self.storedir, 'new/')
        self.deletedir = os.path.join(self.storedir, 'delete/')
        self.flag_file = os.path.join(self.storedir, self.flag_basename)
        self.new_flag = os.path.join(self.newdir, self.flag_basename)

        self.new_flag_seen = self.fs.exists(self.new_flag)
        tracing.trace('self.new_flag_seen: %s' % self.new_flag_seen)
        if self.allow_writes:
            if self.new_flag_seen:
                logging.debug('Automatically committing remaining changes')
                self.commit()
            else:
                logging.debug('Automatically rolling back remaining changes')
                self.rollback()
        else:
            logging.debug('Not committing/rolling back since read-only')
        self.new_files = set()
        self.deleted_files = set()

 def _raw_unlock_client(self, client_name):
     tracing.trace('client_name=%s', client_name)
     client_id = self._get_client_id(client_name)
     client_dir = self._get_client_dir(client_id)
     self._lockmgr.unlock([client_dir])
     if client_name in self._open_client_infos:
         del self._open_client_infos[client_name]

 def chmod_symlink(self, pathname, mode):  # pragma: no cover
     tracing.trace('chmod_symlink %s %o', pathname, mode)
     if self.got_lchmod:
         lchmod = getattr(os, 'lchmod')
         lchmod(self.join(pathname), mode)
     else:
         self.lstat(pathname)

    def backup_dir_contents(self, root):
        '''Back up the list of files in a directory.'''

        tracing.trace('backup_dir: %s', root)
        if self.pretend:
            return

        new_basenames = self.fs.listdir(root)
        new_pathnames = [os.path.join(root, x) for x in new_basenames]
        if self.repo.file_exists(self.new_generation, root):
            old_pathnames = self.repo.get_file_children(
                    self.new_generation, root)
        else:
            old_pathnames = []

        for old in old_pathnames:
            if old not in new_pathnames:
                self.repo.remove_file(self.new_generation, old)
            else:
                try:
                    st = self.fs.lstat(old)
                except OSError:
                    pass
                else:
                    if not self.can_be_backed_up(old, st): 
                        self.repo.remove_file(self.new_generation, old)

    def save_refcounts(self):
        '''Save all modified refcounts.'''
        tracing.trace('saving refcounts (len(dirty) = %s)' % 
                            (len(self.dirty)))
        if self.dirty:
            dirname = os.path.join(self.node_store.dirname, self.refcountdir)
            if not self.node_store.journal.exists(dirname):
                self.node_store.journal.makedirs(dirname)
            ids = sorted(self.dirty)
            all_ids_in_memory = set(self.refcounts.keys())
            for start_id in range(self._start_id(ids[0]), 
                                  self._start_id(ids[-1]) + 1, 
                                  self.per_group):

                all_ids_in_group = set(
                    range(start_id, start_id + self.per_group))
                keys = all_ids_in_group.intersection(all_ids_in_memory)
                if keys:
                    encoded = encode_refcounts(
                        self.refcounts, start_id, self.per_group, keys)
                    filename = self._group_filename(start_id)
                    self.node_store.journal.overwrite_file(filename, encoded)

        # We re-initialize these so that they don't grow indefinitely.
        self.refcounts = dict()
        self.dirty = set()

    def put_chunk_only(self, data):
        '''Put chunk of data into repository.

        If the same data is already in the repository, it will be put there
        a second time. It is the caller's responsibility to check
        that the data is not already in the repository.

        Return the unique identifier of the new chunk.

        '''

        def random_chunkid():
            return random.randint(0, obnamlib.MAX_ID)

        self.require_started_generation()

        if self.prev_chunkid is None:
            self.prev_chunkid = random_chunkid()

        while True:
            chunkid = (self.prev_chunkid + 1) % obnamlib.MAX_ID
            filename = self._chunk_filename(chunkid)
            try:
                self.fs.write_file(filename, data)
            except OSError, e: # pragma: no cover
                if e.errno == errno.EEXIST:
                    self.prev_chunkid = random_chunkid()
                    continue
                raise
            else:
                tracing.trace('chunkid=%s', chunkid)
                break

    def lock_client(self, client_name):
        '''Lock a client for exclusive write access.

        Raise obnamlib.LockFail if locking fails. Lock will be released
        by commit_client() or unlock_client().

        '''

        tracing.trace('client_name=%s', client_name)
        self.require_no_client_lock()
        self.require_no_shared_lock()

        self.check_format_version()
        client_id = self.clientlist.get_client_id(client_name)
        if client_id is None:
            raise LockFail('client %s does not exist' % client_name)

        client_dir = self.client_dir(client_id)
        if not self.fs.exists(client_dir):
            self.fs.mkdir(client_dir)
            self.hooks.call('repository-toplevel-init', self, client_dir)

        self.lockmgr.lock([client_dir])
        self.got_client_lock = True
        self.current_client = client_name
        self.current_client_id = client_id
        self.added_generations = []
        self.removed_generations = []
        self.client = obnamlib.ClientMetadataTree(self.fs, client_dir,
                                                  self.node_size,
                                                  self.upload_queue_size,
                                                  self.lru_size, self)
        self.client.init_forest()

 def do(self):
     tracing.trace("CheckForest: checking forest %s" % self.name )
     for tree in self.fsck.forest.trees:
         self.fsck.count(tree.root.id)
         root_node = self.get_node(tree.root.id)
         tracing.trace('root_node.id=%s' % root_node.id)
         yield CheckIndexNode(self.fsck, root_node)

    def get_repository_object(self, create=False, repofs=None):
        '''Return an implementation of obnamlib.RepositoryInterface.'''

        logging.info('Opening repository: %s', self.settings['repository'])
        tracing.trace('create=%s', create)
        tracing.trace('repofs=%s', repofs)

        repopath = self.settings['repository']
        if repofs is None:
            repofs = self.fsf.new(repopath, create=create)
            if self.settings['crash-limit'] > 0:
                repofs.crash_limit = self.settings['crash-limit']
            repofs.connect()
        else:
            repofs.reinit(repopath)

        kwargs = {
            'lock_timeout': self.settings['lock-timeout'],
            'node_size': self.settings['node-size'],
            'upload_queue_size': self.settings['upload-queue-size'],
            'lru_size': self.settings['lru-size'],
            'idpath_depth': self.settings['idpath-depth'],
            'idpath_bits': self.settings['idpath-bits'],
            'idpath_skip': self.settings['idpath-skip'],
            'hooks': self.hooks,
            'current_time': self.time,
            'chunk_size': self.settings['chunk-size'],
            }

        if create:
            return self.repo_factory.create_repo(
                repofs, self.get_default_repository_class(), **kwargs)
        else:
            return self.repo_factory.open_existing_repo(repofs, **kwargs)

 def _write_format_version(self, version):
     '''Write the desired format version to the repository.'''
     tracing.trace('write format version')
     if not self.fs.exists('metadata'):
         self.fs.mkdir('metadata')
     self.fs.overwrite_file('metadata/format', '%s\n' % version,
                            runfilters=False)

 def _new_index(self, keys, values):
     '''Create a new index node.'''
     index = larch.IndexNode(self._new_id(), keys, values)
     for child_id in values:
         self._increment(child_id)
     tracing.trace('id=%s' % index.id)
     return index

    def remove_chunk_from_indexes(self, chunk_id, client_id):
        tracing.trace('chunk_id=%s', chunk_id)

        self._require_chunk_indexes_lock()
        checksum = self._chunklist.get_checksum(chunk_id)
        self._chunksums.remove(checksum, chunk_id, client_id)
        self._chunklist.remove(chunk_id)

    def _write_to_tempfile(self, pathname, contents):
        path = self.join(pathname)
        dirname = os.path.dirname(path)
        if not os.path.exists(dirname):
            tracing.trace('os.makedirs(%s)' % dirname)
            try:
                os.makedirs(dirname)
            except OSError as e: # pragma: no cover
                # This avoids a race condition: another Obnam process
                # may have created the directory between our check and
                # creation attempt. If so, we ignore it. As long as
                # the directory exists, all's good.
                if e.errno != errno.EEXIST:
                    raise

        fd, tempname = tempfile.mkstemp(dir=dirname)
        os.close(fd)
        f = self.open(tempname, 'wb')

        pos = 0
        while pos < len(contents):
            chunk = contents[pos:pos+self.chunk_size]
            f.write(chunk)
            pos += len(chunk)
            self.bytes_written += len(chunk)
        f.close()
        return tempname

 def remove_chunk(self, chunk_id):
     tracing.trace('chunk_id=%s', chunk_id)
     filename = self._chunk_filename(chunk_id)
     try:
         self._fs.remove(filename)
     except OSError:
         raise obnamlib.RepositoryChunkDoesNotExist(str(chunk_id))

    def needs_backup(self, pathname, current):
        '''Does a given file need to be backed up?'''

        # Directories always require backing up so that backup_dir_contents
        # can remove stuff that no longer exists from them.
        if current.isdir():
            tracing.trace('%s is directory, so needs backup' % pathname)
            return True
        if self.pretend:
            gens = self.repo.list_generations()
            if not gens:
                return True
            gen = gens[-1]
        else:
            gen = self.repo.new_generation
        tracing.trace('gen=%s' % repr(gen))
        try:
            old = self.repo.get_metadata(gen, pathname)
        except obnamlib.Error, e:
            # File does not exist in the previous generation, so it
            # does need to be backed up.
            tracing.trace('%s not in previous gen, so needs backup' % pathname)
            tracing.trace('error: %s' % str(e))
            tracing.trace(traceback.format_exc())
            return True

    def _raw_unlock_client(self, client_name):
        tracing.trace('client_name=%s', client_name)
        self._require_client_lock(client_name)

        open_client = self._open_clients[client_name]
        self._lockmgr.unlock([open_client.client.dirname])
        del self._open_clients[client_name]

    def remove(self, filename):
        tracing.trace('filename=%s', filename)

        file_id = self.get_file_id(self.tree, filename)
        genid = self.get_generation_id(self.tree)

        # Remove any children.
        minkey = self.fskey(file_id, self.DIR_CONTENTS, 0)
        maxkey = self.fskey(file_id, self.DIR_CONTENTS, obnamlib.MAX_ID)
        for key, basename in self.tree.lookup_range(minkey, maxkey):
            self.remove(os.path.join(filename, basename))

        # Remove chunk refs.
        for chunkid in self.get_file_chunks(genid, filename):
            key = self.chunk_key(chunkid, file_id)
            self.tree.remove_range(key, key)

        # Remove this file's metadata.
        minkey = self.fskey(file_id, 0, 0)
        maxkey = self.fskey(file_id, self.TYPE_MAX, self.SUBKEY_MAX)
        self.tree.remove_range(minkey, maxkey)

        # Remove filename.
        default_file_id = self.default_file_id(filename)
        key = self.fskey(default_file_id, self.FILE_NAME, file_id)
        self.tree.remove_range(key, key)

        # Also remove from parent's contents.
        parent = os.path.dirname(filename)
        if parent != filename:  # root dir is its own parent
            parent_id = self.set_file_id(parent)
            key = self.fskey(parent_id, self.DIR_CONTENTS, file_id)
            # The range removal will work even if the key does not exist.
            self.tree.remove_range(key, key)

    def find_files(self, root):
        '''Find all files and directories that need to be backed up.

        This is a generator. It yields (pathname, metadata) pairs.

        The caller should not recurse through directories, just backup
        the directory itself (name, metadata, file list).

        '''

        for pathname, st in self.fs.scan_tree(root, ok=self.can_be_backed_up):
            tracing.trace('considering %s' % pathname)
            try:
                metadata = obnamlib.read_metadata(self.fs, pathname, st=st)
                self.progress.update_progress_with_file(pathname, metadata)
                if self.needs_backup(pathname, metadata):
                    self.progress.backed_up_count += 1
                    yield pathname, metadata
                else:
                    self.progress.update_progress_with_scanned(
                        metadata.st_size)
            except GeneratorExit:
                raise
            except KeyboardInterrupt:
                logging.error('Keyboard interrupt')
                raise
            except BaseException, e:
                msg = 'Cannot back up %s: %s' % (pathname, str(e))
                self.error(msg, e)

    def _add_or_merge(self, parent, node, merge):
        assert not parent.frozen
        assert node.frozen

        keys = parent.keys()
        
        key = node.first_key()
        i = bisect.bisect_left(keys, key)
        
        new_node = None
        if i > 0:
            new_node = merge(parent, node, i-1)
        if new_node is None and i < len(keys):
            new_node = merge(parent, node, i)
        if new_node is None:
            new_node = node

        assert new_node is not None
        self._put_node(new_node)
        parent.add(new_node.first_key(), new_node.id)
        self._increment(new_node.id)
        if new_node != node: # pragma: no cover
            # We made a new node, so get rid of the old one.
            tracing.trace('decrementing unused node id=%s' % node.id)
            self._decrement(node.id)

    def create(self, filename, encoded_metadata):
        tracing.trace('filename=%s', filename)
        file_id = self.set_file_id(filename)
        gen_id = self.get_generation_id(self.tree)
        try:
            old_metadata = self.get_metadata(gen_id, filename)
        except KeyError:
            old_metadata = None

        if encoded_metadata != old_metadata:
            tracing.trace('new or changed metadata')
            self.set_metadata(filename, encoded_metadata)

        # Add to parent's contents, unless already there.
        parent = os.path.dirname(filename)
        tracing.trace('parent=%s', parent)
        if parent != filename:  # root dir is its own parent
            basename = os.path.basename(filename)
            parent_id = self.set_file_id(parent)
            key = self.fskey(parent_id, self.DIR_CONTENTS, file_id)
            # We could just insert, but that would cause unnecessary
            # churn in the tree if nothing changes.
            try:
                self.tree.lookup(key)
                tracing.trace('was already in parent')  # pragma: no cover
            except KeyError:
                self.tree.insert(key, basename)
                tracing.trace('added to parent')