25 Mar, 2009

1 commit

  • btrfs_mark_buffer dirty would set dirty bits in the extent_io tree
    for the buffers it was dirtying. This may require a kmalloc and it
    was not atomic. So, anyone who called btrfs_mark_buffer_dirty had to
    set any btree locks they were holding to blocking first.

    This commit changes dirty tracking for extent buffers to just use a flag
    in the extent buffer. Now that we have one and only one extent buffer
    per page, this can be safely done without losing dirty bits along the way.

    This also introduces a path->leave_spinning flag that callers of
    btrfs_search_slot can use to indicate they will properly deal with a
    path returned where all the locks are spinning instead of blocking.

    Many of the btree search callers now expect spinning paths,
    resulting in better btree concurrency overall.

    Signed-off-by: Chris Mason

    Chris Mason
     

13 Feb, 2009

1 commit


04 Feb, 2009

3 commits

  • On fast devices that go from congested to uncongested very quickly, pdflush
    is waiting too often in congestion_wait, and the FS is backing off to
    easily in write_cache_pages.

    For now, fix this on the btrfs side by only checking congestion after
    some bios have already gone down. Longer term a real fix is needed
    for pdflush, but that is a larger project.

    Signed-off-by: Chris Mason

    Chris Mason
     
  • Most of the btrfs metadata operations can be protected by a spinlock,
    but some operations still need to schedule.

    So far, btrfs has been using a mutex along with a trylock loop,
    most of the time it is able to avoid going for the full mutex, so
    the trylock loop is a big performance gain.

    This commit is step one for getting rid of the blocking locks entirely.
    btrfs_tree_lock takes a spinlock, and the code explicitly switches
    to a blocking lock when it starts an operation that can schedule.

    We'll be able get rid of the blocking locks in smaller pieces over time.
    Tracing allows us to find the most common cause of blocking, so we
    can start with the hot spots first.

    The basic idea is:

    btrfs_tree_lock() returns with the spin lock held

    btrfs_set_lock_blocking() sets the EXTENT_BUFFER_BLOCKING bit in
    the extent buffer flags, and then drops the spin lock. The buffer is
    still considered locked by all of the btrfs code.

    If btrfs_tree_lock gets the spinlock but finds the blocking bit set, it drops
    the spin lock and waits on a wait queue for the blocking bit to go away.

    Much of the code that needs to set the blocking bit finishes without actually
    blocking a good percentage of the time. So, an adaptive spin is still
    used against the blocking bit to avoid very high context switch rates.

    btrfs_clear_lock_blocking() clears the blocking bit and returns
    with the spinlock held again.

    btrfs_tree_unlock() can be called on either blocking or spinning locks,
    it does the right thing based on the blocking bit.

    ctree.c has a helper function to set/clear all the locked buffers in a
    path as blocking.

    Signed-off-by: Chris Mason

    Chris Mason
     
  • extent_io.c has debugging code to report and free leaked extent_state
    and extent_buffer objects at rmmod time. This helps track down
    leaks and it saves you from rebooting just to properly remove the
    kmem_cache object.

    But, the code runs under a fairly expensive spinlock and the checks to
    see if it is currently enabled are not entirely consistent. Some use
    #ifdef and some #if.

    This changes everything to #if and disables the leak checking.

    Signed-off-by: Chris Mason

    Chris Mason
     

22 Jan, 2009

1 commit

  • Now that bmap support is gone, this is the only way to get extent
    mappings for userland. These are still not valid for IO, but they
    can tell us if a file has holes or how much fragmentation there is.

    Signed-off-by: Yehuda Sadeh

    Yehuda Sadeh
     

21 Jan, 2009

1 commit


06 Jan, 2009

3 commits


18 Dec, 2008

1 commit

  • bio_end_io for reads without checksumming on and btree writes were
    happening without using async thread pools. This means the extent_io.c
    code had to use spin_lock_irq and friends on the rb tree locks for
    extent state.

    There were some irq safe vs unsafe lock inversions between the delallock
    lock and the extent state locks. This patch gets rid of them by moving
    all end_io code into the thread pools.

    To avoid contention and deadlocks between the data end_io processing and the
    metadata end_io processing yet another thread pool is added to finish
    off metadata writes.

    Signed-off-by: Chris Mason

    Chris Mason
     

09 Dec, 2008

2 commits

  • It is possible that generic_bin_search will be called on a tree block
    that has not been locked. This happens because cache_block_block skips
    locking on the tree blocks.

    Since the tree block isn't locked, we aren't allowed to change
    the extent_buffer->map_token field. Using map_private_extent_buffer
    avoids any changes to the internal extent buffer fields.

    Signed-off-by: Chris Mason

    Chris Mason
     
  • Btrfs stores checksums for each data block. Until now, they have
    been stored in the subvolume trees, indexed by the inode that is
    referencing the data block. This means that when we read the inode,
    we've probably read in at least some checksums as well.

    But, this has a few problems:

    * The checksums are indexed by logical offset in the file. When
    compression is on, this means we have to do the expensive checksumming
    on the uncompressed data. It would be faster if we could checksum
    the compressed data instead.

    * If we implement encryption, we'll be checksumming the plain text and
    storing that on disk. This is significantly less secure.

    * For either compression or encryption, we have to get the plain text
    back before we can verify the checksum as correct. This makes the raid
    layer balancing and extent moving much more expensive.

    * It makes the front end caching code more complex, as we have touch
    the subvolume and inodes as we cache extents.

    * There is potentitally one copy of the checksum in each subvolume
    referencing an extent.

    The solution used here is to store the extent checksums in a dedicated
    tree. This allows us to index the checksums by phyiscal extent
    start and length. It means:

    * The checksum is against the data stored on disk, after any compression
    or encryption is done.

    * The checksum is stored in a central location, and can be verified without
    following back references, or reading inodes.

    This makes compression significantly faster by reducing the amount of
    data that needs to be checksummed. It will also allow much faster
    raid management code in general.

    The checksums are indexed by a key with a fixed objectid (a magic value
    in ctree.h) and offset set to the starting byte of the extent. This
    allows us to copy the checksum items into the fsync log tree directly (or
    any other tree), without having to invent a second format for them.

    Signed-off-by: Chris Mason

    Chris Mason
     

02 Dec, 2008

2 commits


20 Nov, 2008

3 commits

  • The btrfs write_cache_pages call has a flush function so that it submits
    the bio it has been building before it waits on any writeback pages.

    This adds a check so that flush only happens on writeback pages.

    Signed-off-by: Chris Mason

    Chris Mason
     
  • * open/close_bdev_excl -> open/close_bdev_exclusive
    * blkdev_issue_discard takes a GFP mask now
    * Fix blkdev_issue_discard usage now that it is enabled

    Signed-off-by: Chris Mason

    Chris Mason
     
  • While building large bios in writepages, btrfs may end up waiting
    for other page writeback to finish if WB_SYNC_ALL is used.

    While it is waiting, the bio it is building has a number of pages with the
    writeback bit set and they aren't getting to the disk any time soon. This
    lowers the latencies of writeback in general by sending down the bio being
    built before waiting for other pages.

    The bio submission code tries to limit the total number of async bios in
    flight by waiting when we're over a certain number of async bios. But,
    the waits are happening while writepages is building bios, and this can easily
    lead to stalls and other problems for people calling wait_on_page_writeback.

    The current fix is to let the congestion tests take care of waiting.

    sync() and others make sure to drain the current async requests to make
    sure that everything that was pending when the sync was started really get
    to disk. The code would drain pending requests both before and after
    submitting a new request.

    But, if one of the requests is waiting for page writeback to finish,
    the draining waits might block that page writeback. This changes the
    draining code to only wait after submitting the bio being processed.

    Signed-off-by: Chris Mason

    Chris Mason
     

11 Nov, 2008

3 commits


10 Nov, 2008

1 commit


07 Nov, 2008

2 commits

  • The allocator uses the last allocation as a starting point for metadata
    allocations, and tries to allocate in clusters of at least 256k.

    If the search for a free block fails to find the expected block, this patch
    forces a new cluster to be found in the free list.

    Signed-off-by: Chris Mason

    Chris Mason
     
  • When reading compressed extents, try to put pages into the page cache
    for any pages covered by the compressed extent that readpages didn't already
    preload.

    Add an async work queue to handle transformations at delayed allocation processing
    time. Right now this is just compression. The workflow is:

    1) Find offsets in the file marked for delayed allocation
    2) Lock the pages
    3) Lock the state bits
    4) Call the async delalloc code

    The async delalloc code clears the state lock bits and delalloc bits. It is
    important this happens before the range goes into the work queue because
    otherwise it might deadlock with other work queue items that try to lock
    those extent bits.

    The file pages are compressed, and if the compression doesn't work the
    pages are written back directly.

    An ordered work queue is used to make sure the inodes are written in the same
    order that pdflush or writepages sent them down.

    This changes extent_write_cache_pages to let the writepage function
    update the wbc nr_written count.

    Signed-off-by: Chris Mason

    Chris Mason
     

01 Nov, 2008

1 commit

  • Make sure we keep page->mapping NULL on the pages we're getting
    via alloc_page. It gets set so a few of the callbacks can do the right
    thing, but in general these pages don't have a mapping.

    Don't try to truncate compressed inline items in btrfs_drop_extents.
    The whole compressed item must be preserved.

    Don't try to create multipage inline compressed items. When we try to
    overwrite just the first page of the file, we would have to read in and recow
    all the pages after it in the same compressed inline items. For now, only
    create single page inline items.

    Make sure we lock pages in the correct order during delalloc. The
    search into the state tree for delalloc bytes can return bytes before
    the page we already have locked.

    Signed-off-by: Chris Mason

    Chris Mason
     

31 Oct, 2008

2 commits

  • This patch updates btrfs-progs for fallocate support.

    fallocate is a little different in Btrfs because we need to tell the
    COW system that a given preallocated extent doesn't need to be
    cow'd as long as there are no snapshots of it. This leverages the
    -o nodatacow checks.

    Signed-off-by: Yan Zheng

    Yan Zheng
     
  • When dropping middle part of an extent, btrfs_drop_extents truncates
    the extent at first, then inserts a bookend extent.

    Since truncation and insertion can't be done atomically, there is a small
    period that the bookend extent isn't in the tree. This causes problem for
    functions that search the tree for file extent item. The way to fix this is
    lock the range of the bookend extent before truncation.

    Signed-off-by: Yan Zheng

    Yan Zheng
     

30 Oct, 2008

2 commits

  • This patch removes the giant fs_info->alloc_mutex and replaces it with a bunch
    of little locks.

    There is now a pinned_mutex, which is used when messing with the pinned_extents
    extent io tree, and the extent_ins_mutex which is used with the pending_del and
    extent_ins extent io trees.

    The locking for the extent tree stuff was inspired by a patch that Yan Zheng
    wrote to fix a race condition, I cleaned it up some and changed the locking
    around a little bit, but the idea remains the same. Basically instead of
    holding the extent_ins_mutex throughout the processing of an extent on the
    extent_ins or pending_del trees, we just hold it while we're searching and when
    we clear the bits on those trees, and lock the extent for the duration of the
    operations on the extent.

    Also to keep from getting hung up waiting to lock an extent, I've added a
    try_lock_extent so if we cannot lock the extent, move on to the next one in the
    tree and we'll come back to that one. I have tested this heavily and it does
    not appear to break anything. This has to be applied on top of my
    find_free_extent redo patch.

    I tested this patch on top of Yan's space reblancing code and it worked fine.
    The only thing that has changed since the last version is I pulled out all my
    debugging stuff, apparently I forgot to run guilt refresh before I sent the
    last patch out. Thank you,

    Signed-off-by: Josef Bacik

    Josef Bacik
     
  • This is a large change for adding compression on reading and writing,
    both for inline and regular extents. It does some fairly large
    surgery to the writeback paths.

    Compression is off by default and enabled by mount -o compress. Even
    when the -o compress mount option is not used, it is possible to read
    compressed extents off the disk.

    If compression for a given set of pages fails to make them smaller, the
    file is flagged to avoid future compression attempts later.

    * While finding delalloc extents, the pages are locked before being sent down
    to the delalloc handler. This allows the delalloc handler to do complex things
    such as cleaning the pages, marking them writeback and starting IO on their
    behalf.

    * Inline extents are inserted at delalloc time now. This allows us to compress
    the data before inserting the inline extent, and it allows us to insert
    an inline extent that spans multiple pages.

    * All of the in-memory extent representations (extent_map.c, ordered-data.c etc)
    are changed to record both an in-memory size and an on disk size, as well
    as a flag for compression.

    From a disk format point of view, the extent pointers in the file are changed
    to record the on disk size of a given extent and some encoding flags.
    Space in the disk format is allocated for compression encoding, as well
    as encryption and a generic 'other' field. Neither the encryption or the
    'other' field are currently used.

    In order to limit the amount of data read for a single random read in the
    file, the size of a compressed extent is limited to 128k. This is a
    software only limit, the disk format supports u64 sized compressed extents.

    In order to limit the ram consumed while processing extents, the uncompressed
    size of a compressed extent is limited to 256k. This is a software only limit
    and will be subject to tuning later.

    Checksumming is still done on compressed extents, and it is done on the
    uncompressed version of the data. This way additional encodings can be
    layered on without having to figure out which encoding to checksum.

    Compression happens at delalloc time, which is basically singled threaded because
    it is usually done by a single pdflush thread. This makes it tricky to
    spread the compression load across all the cpus on the box. We'll have to
    look at parallel pdflush walks of dirty inodes at a later time.

    Decompression is hooked into readpages and it does spread across CPUs nicely.

    Signed-off-by: Chris Mason

    Chris Mason
     

30 Sep, 2008

1 commit

  • This improves the comments at the top of many functions. It didn't
    dive into the guts of functions because I was trying to
    avoid merging problems with the new allocator and back reference work.

    extent-tree.c and volumes.c were both skipped, and there is definitely
    more work todo in cleaning and commenting the code.

    Signed-off-by: Chris Mason

    Chris Mason
     

26 Sep, 2008

2 commits

  • * Add an EXTENT_BOUNDARY state bit to keep the writepage code
    from merging data extents that are in the process of being
    relocated. This allows us to do accounting for them properly.

    * The balancing code relocates data extents indepdent of the underlying
    inode. The extent_map code was modified to properly account for
    things moving around (invalidating extent_map caches in the inode).

    * Don't take the drop_mutex in the create_subvol ioctl. It isn't
    required.

    * Fix walking of the ordered extent list to avoid races with sys_unlink

    * Change the lock ordering rules. Transaction start goes outside
    the drop_mutex. This allows btrfs_commit_transaction to directly
    drop the relocation trees.

    Signed-off-by: Chris Mason

    Zheng Yan
     
  • Btrfs had compatibility code for kernels back to 2.6.18. These have
    been removed, and will be maintained in a separate backport
    git tree from now on.

    Signed-off-by: Chris Mason

    Chris Mason
     

25 Sep, 2008

8 commits

  • This patch makes the back reference system to explicit record the
    location of parent node for all types of extents. The location of
    parent node is placed into the offset field of backref key. Every
    time a tree block is balanced, the back references for the affected
    lower level extents are updated.

    Signed-off-by: Chris Mason

    Zheng Yan
     
  • 1) replace the per fs_info extent_io_tree that tracked free space with two
    rb-trees per block group to track free space areas via offset and size. The
    reason to do this is because most allocations come with a hint byte where to
    start, so we can usually find a chunk of free space at that hint byte to satisfy
    the allocation and get good space packing. If we cannot find free space at or
    after the given offset we fall back on looking for a chunk of the given size as
    close to that given offset as possible. When we fall back on the size search we
    also try to find a slot as close to the size we want as possible, to avoid
    breaking small chunks off of huge areas if possible.

    2) remove the extent_io_tree that tracked the block group cache from fs_info and
    replaced it with an rb-tree thats tracks block group cache via offset. also
    added a per space_info list that tracks the block group cache for the particular
    space so we can lookup related block groups easily.

    3) cleaned up the allocation code to make it a little easier to read and a
    little less complicated. Basically there are 3 steps, first look from our
    provided hint. If we couldn't find from that given hint, start back at our
    original search start and look for space from there. If that fails try to
    allocate space if we can and start looking again. If not we're screwed and need
    to start over again.

    4) small fixes. there were some issues in volumes.c where we wouldn't allocate
    the rest of the disk. fixed cow_file_range to actually pass the alloc_hint,
    which has helped a good bit in making the fs_mark test I run have semi-normal
    results as we run out of space. Generally with data allocations we don't track
    where we last allocated from, so everytime we did a data allocation we'd search
    through every block group that we have looking for free space. Now searching a
    block group with no free space isn't terribly time consuming, it was causing a
    slight degradation as we got more data block groups. The alloc_hint has fixed
    this slight degredation and made things semi-normal.

    There is still one nagging problem I'm working on where we will get ENOSPC when
    there is definitely plenty of space. This only happens with metadata
    allocations, and only when we are almost full. So you generally hit the 85%
    mark first, but sometimes you'll hit the BUG before you hit the 85% wall. I'm
    still tracking it down, but until then this seems to be pretty stable and make a
    significant performance gain.

    Signed-off-by: Chris Mason

    Josef Bacik
     
  • * Pin down data blocks to prevent them from being reallocated like so:

    trans 1: allocate file extent
    trans 2: free file extent
    trans 3: free file extent during old snapshot deletion
    trans 3: allocate file extent to new file
    trans 3: fsync new file

    Before the tree logging code, this was legal because the fsync
    would commit the transation that did the final data extent free
    and the transaction that allocated the extent to the new file
    at the same time.

    With the tree logging code, the tree log subtransaction can commit
    before the transaction that freed the extent. If we crash,
    we're left with two different files using the extent.

    * Don't wait in start_transaction if log replay is going on. This
    avoids deadlocks from iput while we're cleaning up link counts in the
    replay code.

    * Don't deadlock in replay_one_name by trying to read an inode off
    the disk while holding paths for the directory

    * Hold the buffer lock while we mark a buffer as written. This
    closes a race where someone is changing a buffer while we write it.
    They are supposed to mark it dirty again after they change it, but
    this violates the cow rules.

    Signed-off-by: Chris Mason

    Chris Mason
     
  • Fix a bunch of trivial sparse complaints.

    Signed-off-by: Christoph Hellwig
    Signed-off-by: Chris Mason

    Christoph Hellwig
     
  • Signed-off-by: Chris Mason

    Chris Mason
     
  • These ended up freeing objects while they were still using them. Under
    guidance from Chris, just rip out the 'clever' bits and do things the
    simple way.

    Signed-off-by: David Woodhouse
    Signed-off-by: Chris Mason

    David Woodhouse
     
  • Add backwards compatibility in compat.h

    Signed-off-by: David Woodhouse
    ---
    compat.h | 3 +++
    extent_io.c | 3 ++-
    2 files changed, 5 insertions(+), 1 deletions(-)

    Signed-off-by: Chris Mason

    David Woodhouse
     
  • Add a couple of #if's to follow API changes.

    Signed-off-by: Sven Wegener
    Signed-off-by: Chris Mason

    Sven Wegener