1. 15 Feb, 2023 27 commits
    • Christoph Hellwig's avatar
      btrfs: simplify the btrfs_csum_one_bio calling convention · f8c44673
      Christoph Hellwig authored
      To prepare for further bio submission changes btrfs_csum_one_bio
      should be able to take all it's arguments from the btrfs_bio structure.
      It can always use the bbio->inode already, and once the compression code
      is updated to set ->file_offset that one can be used unconditionally
      as well instead of looking at the page mapping now that btrfs doesn't
      allow ordered extents to span discontiguous data ranges.
      
      The only slightly tricky bit is the one_ordered flag set by the
      compressed writes.  Replace that one with the driver private bio
      flag, which gets cleared before the bio is handed off to the block layer
      so that we don't get in the way of driver use.
      
      Note: this leaves an argument and a flag to btrfs_wq_submit_bio unused.
      But that whole mechanism will be removed in its current form in the
      next patch.
      Reviewed-by: default avatarJosef Bacik <josef@toxicpanda.com>
      Reviewed-by: default avatarJohannes Thumshirn <johannes.thumshirn@wdc.com>
      Signed-off-by: default avatarChristoph Hellwig <hch@lst.de>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      f8c44673
    • Christoph Hellwig's avatar
      btrfs: open code the submit_bio_start helpers · deb6216f
      Christoph Hellwig authored
      The submit helpers are now trivial and can be called directly.  Note
      that btree_csum_one_bio has to be moved up in the file a bit to avoid a
      forward declaration.
      Reviewed-by: default avatarJosef Bacik <josef@toxicpanda.com>
      Reviewed-by: default avatarJohannes Thumshirn <johannes.thumshirn@wdc.com>
      Signed-off-by: default avatarChristoph Hellwig <hch@lst.de>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      deb6216f
    • Christoph Hellwig's avatar
      btrfs: remove struct btrfs_bio::is_metadata flag · 295fe46f
      Christoph Hellwig authored
      This flag is unused now, so remove it.  Re-expand the mirror_num field
      to 8 bits, and move it to the I/O completion internal section of the
      structure.
      Reviewed-by: default avatarJohannes Thumshirn <johannes.thumshirn@wdc.com>
      Signed-off-by: default avatarChristoph Hellwig <hch@lst.de>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      295fe46f
    • Christoph Hellwig's avatar
      btrfs: rename btrfs_bio::iter field · 0d3acb25
      Christoph Hellwig authored
      Rename iter to saved_iter and move it next to the repair internals
      and nothing outside of bio.c should be touching it.
      Reviewed-by: default avatarJohannes Thumshirn <johannes.thumshirn@wdc.com>
      Signed-off-by: default avatarChristoph Hellwig <hch@lst.de>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      0d3acb25
    • Christoph Hellwig's avatar
      btrfs: remove the io_failure_record infrastructure · 0571b635
      Christoph Hellwig authored
      struct io_failure_record and the io_failure_tree tree are unused now,
      so remove them. This in turn makes struct btrfs_inode smaller by 16
      bytes.
      Reviewed-by: default avatarJohannes Thumshirn <johannes.thumshirn@wdc.com>
      Signed-off-by: default avatarChristoph Hellwig <hch@lst.de>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      0571b635
    • Christoph Hellwig's avatar
      btrfs: remove struct btrfs_bio::device field · 860c8c45
      Christoph Hellwig authored
      The device field is only used by the simple end I/O handler, and for
      that it can simply be stored in the bi_private field of the bio,
      which is currently used for the fs_info that can be retrieved through
      bbio->inode as well.
      Reviewed-by: default avatarJohannes Thumshirn <johannes.thumshirn@wdc.com>
      Signed-off-by: default avatarChristoph Hellwig <hch@lst.de>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      860c8c45
    • Christoph Hellwig's avatar
      btrfs: remove now unused checksumming helpers · 3d49d0d3
      Christoph Hellwig authored
      Remove the unused btrfs_verify_data_csum helper, and fold
      btrfs_check_data_csum into its only caller.
      Reviewed-by: default avatarJohannes Thumshirn <johannes.thumshirn@wdc.com>
      Signed-off-by: default avatarChristoph Hellwig <hch@lst.de>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      3d49d0d3
    • Christoph Hellwig's avatar
      btrfs: remove btrfs_bio_for_each_sector · ac9f942e
      Christoph Hellwig authored
      btrfs_bio_for_each_sector is unused now, so remove it.
      Reviewed-by: default avatarJohannes Thumshirn <johannes.thumshirn@wdc.com>
      Signed-off-by: default avatarChristoph Hellwig <hch@lst.de>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      ac9f942e
    • Christoph Hellwig's avatar
      btrfs: open code btrfs_bio_free_csum · 7ab0fdfc
      Christoph Hellwig authored
      btrfs_bio_free_csum has only one caller left, and that caller is always
      for an data inode and doesn't need zeroing of the csum pointer as that
      pointer will never be touched again.  Just open code the conditional
      kfree there.
      Reviewed-by: default avatarJohannes Thumshirn <johannes.thumshirn@wdc.com>
      Signed-off-by: default avatarChristoph Hellwig <hch@lst.de>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      7ab0fdfc
    • Christoph Hellwig's avatar
      btrfs: handle checksum validation and repair at the storage layer · 7609afac
      Christoph Hellwig authored
      Currently btrfs handles checksum validation and repair in the end I/O
      handler for the btrfs_bio.  This leads to a lot of duplicate code
      plus issues with varying semantics or bugs, e.g.
      
      - the until recently broken repair for compressed extents
      - the fact that encoded reads validate the checksums but do not kick
        of read repair
      - the inconsistent checking of the BTRFS_FS_STATE_NO_CSUMS flag
      
      This commit revamps the checksum validation and repair code to instead
      work below the btrfs_submit_bio interfaces.
      
      In case of a checksum failure (or a plain old I/O error), the repair
      is now kicked off before the upper level ->end_io handler is invoked.
      
      Progress of an in-progress repair is tracked by a small structure
      that is allocated using a mempool for each original bio with failed
      sectors, which holds a reference to the original bio.   This new
      structure is allocated using a mempool to guarantee forward progress
      even under memory pressure.  The mempool will be replenished when
      the repair completes, just as the mempools backing the bios.
      
      There is one significant behavior change here:  If repair fails or
      is impossible to start with, the whole bio will be failed to the
      upper layer.  This is the behavior that all I/O submitters except
      for buffered I/O already emulated in their end_io handler.  For
      buffered I/O this now means that a large readahead request can
      fail due to a single bad sector, but as readahead errors are ignored
      the following readpage if the sector is actually accessed will
      still be able to read.  This also matches the I/O failure handling
      in other file systems.
      Reviewed-by: default avatarJosef Bacik <josef@toxicpanda.com>
      Reviewed-by: default avatarJohannes Thumshirn <johannes.thumshirn@wdc.com>
      Signed-off-by: default avatarChristoph Hellwig <hch@lst.de>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      7609afac
    • Christoph Hellwig's avatar
      btrfs: add a btrfs_data_csum_ok helper · e5219044
      Christoph Hellwig authored
      Add a new checksumming helper that wraps btrfs_check_data_csum and
      does all the checks to if we're dealing with some form of nodatacsum
      I/O.  This helper will be used by the new storage layer checksum
      validation and repair code.
      Reviewed-by: default avatarJohannes Thumshirn <johannes.thumshirn@wdc.com>
      Signed-off-by: default avatarChristoph Hellwig <hch@lst.de>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      e5219044
    • Christoph Hellwig's avatar
      btrfs: pre-load data checksum for reads in btrfs_submit_bio · 1c2b3ee3
      Christoph Hellwig authored
      Instead of calling btrfs_lookup_bio_sums in every caller of
      btrfs_submit_bio that reads data, do the call once in btrfs_submit_bio.
      Reviewed-by: default avatarJohannes Thumshirn <johannes.thumshirn@wdc.com>
      Signed-off-by: default avatarChristoph Hellwig <hch@lst.de>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      1c2b3ee3
    • Christoph Hellwig's avatar
      btrfs: save the bio iter for checksum validation in common code · 7276aa7d
      Christoph Hellwig authored
      All callers of btrfs_submit_bio that want to validate checksums
      currently have to store a copy of the iter in the btrfs_bio.  Move
      the assignment into common code.
      Reviewed-by: default avatarJohannes Thumshirn <johannes.thumshirn@wdc.com>
      Signed-off-by: default avatarChristoph Hellwig <hch@lst.de>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      7276aa7d
    • Christoph Hellwig's avatar
      btrfs: refactor error handling in btrfs_submit_bio · 9ba0004b
      Christoph Hellwig authored
      Add a bbio local variable and to prepare for calling functions that
      return a blk_status_t, rename the existing int used for error handling
      so that ret can be reused for the blk_status_t, and a label that can be
      reused for failing the passed in bio.
      Reviewed-by: default avatarAnand Jain <anand.jain@oracle.com>
      Reviewed-by: default avatarJohannes Thumshirn <johannes.thumshirn@wdc.com>
      Signed-off-by: default avatarChristoph Hellwig <hch@lst.de>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      9ba0004b
    • Christoph Hellwig's avatar
      btrfs: simplify parameters of btrfs_lookup_bio_sums · 4ae2edf1
      Christoph Hellwig authored
      The csums argument is always NULL now, so remove it and always allocate
      the csums array in the btrfs_bio.  Also pass the btrfs_bio instead of
      inode + bio to document that this function requires a btrfs_bio and
      not just any bio.
      Reviewed-by: default avatarJohannes Thumshirn <johannes.thumshirn@wdc.com>
      Reviewed-by: default avatarAnand Jain <anand.jain@oracle.com>
      Signed-off-by: default avatarChristoph Hellwig <hch@lst.de>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      4ae2edf1
    • Christoph Hellwig's avatar
      btrfs: remove the direct I/O read checksum lookup optimization · 5fa35653
      Christoph Hellwig authored
      To prepare for pending changes drop the optimization to only look up
      csums once per bio that is submitted from the iomap layer.  In the
      short run this does cause additional lookups for fragmented direct
      reads, but later in the series, the bio based lookup will be used on
      the entire bio submitted from iomap, restoring the old behavior
      in common code.
      Reviewed-by: default avatarAnand Jain <anand.jain@oracle.com>
      Reviewed-by: default avatarJohannes Thumshirn <johannes.thumshirn@wdc.com>
      Signed-off-by: default avatarChristoph Hellwig <hch@lst.de>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      5fa35653
    • Christoph Hellwig's avatar
      btrfs: add a btrfs_inode pointer to struct btrfs_bio · d0e5cb2b
      Christoph Hellwig authored
      All btrfs_bio I/Os are associated with an inode.  Add a pointer to that
      inode, which will allow to simplify a lot of calling conventions, and
      which will be needed in the I/O completion path in the future.
      
      This grow the btrfs_bio structure by a pointer, but that grows will
      be offset by the removal of the device pointer soon.
      Reviewed-by: default avatarAnand Jain <anand.jain@oracle.com>
      Reviewed-by: default avatarJohannes Thumshirn <johannes.thumshirn@wdc.com>
      Signed-off-by: default avatarChristoph Hellwig <hch@lst.de>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      d0e5cb2b
    • Christoph Hellwig's avatar
      btrfs: better document struct btrfs_bio · e0cfbb2c
      Christoph Hellwig authored
      Update the comments on btrfs_bio to better describe the structure.
      Reviewed-by: default avatarAnand Jain <anand.jain@oracle.com>
      Reviewed-by: default avatarJohannes Thumshirn <johannes.thumshirn@wdc.com>
      Signed-off-by: default avatarChristoph Hellwig <hch@lst.de>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      e0cfbb2c
    • Christoph Hellwig's avatar
      block: export bio_split_rw · fd8f8ede
      Christoph Hellwig authored
      bio_split_rw can be used by file systems to split and incoming write
      bio into multiple bios fitting the hardware limit for use as ZONE_APPEND
      bios.  Export it for initial use in btrfs.
      Reviewed-by: default avatarJosef Bacik <josef@toxicpanda.com>
      Reviewed-by: default avatarChaitanya Kulkarni <kch@nvidia.com>
      Reviewed-by: default avatarJohannes Thumshirn <johannes.thumshirn@wdc.com>
      Signed-off-by: default avatarChristoph Hellwig <hch@lst.de>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      fd8f8ede
    • Qu Wenruo's avatar
      btrfs: raid56: reduce overhead to calculate the bio length · c9a43aaf
      Qu Wenruo authored
      In rbio_update_error_bitmap(), we need to calculate the length of the
      rbio.  As since it's called in the endio function, we can not directly
      grab the length from bi_iter.
      
      Currently we call bio_for_each_segment_all(), which will always return a
      range inside a page.  But that's not necessary as we don't really care
      about anything inside the page.
      
      So use bio_for_each_bvec_all(), which can return a bvec across multiple
      continuous pages thus reduce the loops.
      Reviewed-by: default avatarChristoph Hellwig <hch@lst.de>
      Signed-off-by: default avatarQu Wenruo <wqu@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      c9a43aaf
    • Colin Ian King's avatar
      btrfs: fix spelling mistakes found using codespell · 67da05b3
      Colin Ian King authored
      There quite a few spelling mistakes as found using codespell. Fix them.
      Signed-off-by: default avatarColin Ian King <colin.i.king@gmail.com>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      67da05b3
    • Filipe Manana's avatar
      btrfs: skip backref walking during fiemap if we know the leaf is shared · e2fd8306
      Filipe Manana authored
      During fiemap, when checking if a data extent is shared we are doing the
      backref walking even if we already know the leaf is shared, which is a
      waste of time since if the leaf shared then the data extent is also
      shared. So skip the backref walking when we know we are in a shared leaf.
      
      The following test was measures the gains for a case where all leaves
      are shared due to a snapshot:
      
         $ cat test.sh
         #!/bin/bash
      
         DEV=/dev/sdj
         MNT=/mnt/sdj
      
         umount $DEV &> /dev/null
         mkfs.btrfs -f $DEV
         # Use compression to quickly create files with a lot of extents
         # (each with a size of 128K).
         mount -o compress=lzo $DEV $MNT
      
         # 40G gives 327680 extents, each with a size of 128K.
         xfs_io -f -c "pwrite -S 0xab -b 1M 0 40G" $MNT/foobar
      
         # Add some more files to increase the size of the fs and extent
         # trees (in the real world there's a lot of files and extents
         # from other files).
         xfs_io -f -c "pwrite -S 0xcd -b 1M 0 20G" $MNT/file1
         xfs_io -f -c "pwrite -S 0xef -b 1M 0 20G" $MNT/file2
         xfs_io -f -c "pwrite -S 0x73 -b 1M 0 20G" $MNT/file3
      
         # Create a snapshot so all the extents become indirectly shared
         # through subtrees, with a generation less than or equals to the
         # generation used to create the snapshot.
         btrfs subvolume snapshot -r $MNT $MNT/snap1
      
         # Unmount and mount again to clear cached metadata.
         umount $MNT
         mount -o compress=lzo $DEV $MNT
      
         start=$(date +%s%N)
         # The filefrag tool  uses the fiemap ioctl.
         filefrag $MNT/foobar
         end=$(date +%s%N)
         dur=$(( (end - start) / 1000000 ))
         echo "fiemap took $dur milliseconds (metadata not cached)"
         echo
      
         start=$(date +%s%N)
         filefrag $MNT/foobar
         end=$(date +%s%N)
         dur=$(( (end - start) / 1000000 ))
         echo "fiemap took $dur milliseconds (metadata cached)"
      
         umount $MNT
      
      The results were the following on a non-debug kernel (Debian's default
      kernel config).
      
      Before this patch:
      
         (...)
         /mnt/sdi/foobar: 327680 extents found
         fiemap took 1821 milliseconds (metadata not cached)
      
         /mnt/sdi/foobar: 327680 extents found
         fiemap took 399 milliseconds (metadata cached)
      
      After this patch:
      
         (...)
         /mnt/sdi/foobar: 327680 extents found
         fiemap took 591 milliseconds (metadata not cached)
      
         /mnt/sdi/foobar: 327680 extents found
         fiemap took 123 milliseconds (metadata cached)
      
      That's a speedup of 3.1x and 3.2x.
      Signed-off-by: default avatarFilipe Manana <fdmanana@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      e2fd8306
    • Filipe Manana's avatar
      btrfs: assert commit root semaphore is held when accessing backref cache · 4e4488d4
      Filipe Manana authored
      During fiemap, when accessing the cache that stores the sharedness of an
      extent, we need to either be holding a transaction handle or the commit
      root semaphore. I left comments about this in the comment that precedes
      store_backref_shared_cache() and lookup_backref_shared_cache(), but have
      actually not enforced it through assertions. So assert that the commit
      root semaphore is held if we are not holding a transaction handle.
      Reviewed-by: default avatarJohannes Thumshirn <johannes.thumshirn@wdc.com>
      Signed-off-by: default avatarFilipe Manana <fdmanana@suse.com>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      4e4488d4
    • Boris Burkov's avatar
      btrfs: hold block group refcount during async discard · 2b5463fc
      Boris Burkov authored
      Async discard does not acquire the block group reference count while it
      holds a reference on the discard list. This is generally OK, as the
      paths which destroy block groups tend to try to synchronize on
      cancelling async discard work. However, relying on cancelling work
      requires careful analysis to be sure it is safe from races with
      unpinning scheduling more work.
      
      While I am unable to find a race with unpinning in the current code for
      either the unused bgs or relocation paths, I believe we have one in an
      older version of auto relocation in a Meta internal build. This suggests
      that this is in fact an error prone model, and could be fragile to
      future changes to these bg deletion paths.
      
      To make this ownership more clear, add a refcount for async discard. If
      work is queued for a block group, its refcount should be incremented,
      and when work is completed or canceled, it should be decremented.
      
      CC: stable@vger.kernel.org # 5.15+
      Signed-off-by: default avatarBoris Burkov <boris@bur.io>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      2b5463fc
    • Filipe Manana's avatar
      btrfs: send: cache utimes operations for directories if possible · 3e49363b
      Filipe Manana authored
      Whenever we add or remove an entry to a directory, we issue an utimes
      command for the directory. If we add 1000 entries to a directory (create
      1000 files under it or move 1000 files to it), then we issue the same
      utimes command 1000 times, which increases the send stream size, results
      in more pipe IO, one search in the send b+tree, allocating one path for
      the search, etc, as well as making the receiver do a system call for each
      duplicated utimes command.
      
      We also issue an utimes command when we create a new directory, but later
      we might add entries to it corresponding to inodes with an higher inode
      number, so it's pointless to issue the utimes command before we create
      the last inode under the directory.
      
      So use a lru cache to track directories for which we must send a utimes
      command. When we need to remove an entry from the cache, we issue the
      utimes command for the respective directory. When finishing the send
      operation, we go over each cache element and issue the respective utimes
      command. Finally the caching is entirely optional, just a performance
      optimization, meaning that if we fail to cache (due to memory allocation
      failure), we issue the utimes command right away, that is, we fallback
      to the previous, unoptimized, behaviour.
      
      This patch belongs to a patchset comprised of the following patches:
      
        btrfs: send: directly return from did_overwrite_ref() and simplify it
        btrfs: send: avoid unnecessary generation search at did_overwrite_ref()
        btrfs: send: directly return from will_overwrite_ref() and simplify it
        btrfs: send: avoid extra b+tree searches when checking reference overrides
        btrfs: send: remove send_progress argument from can_rmdir()
        btrfs: send: avoid duplicated orphan dir allocation and initialization
        btrfs: send: avoid unnecessary orphan dir rbtree search at can_rmdir()
        btrfs: send: reduce searches on parent root when checking if dir can be removed
        btrfs: send: iterate waiting dir move rbtree only once when processing refs
        btrfs: send: initialize all the red black trees earlier
        btrfs: send: genericize the backref cache to allow it to be reused
        btrfs: adapt lru cache to allow for 64 bits keys on 32 bits systems
        btrfs: send: cache information about created directories
        btrfs: allow a generation number to be associated with lru cache entries
        btrfs: add an api to delete a specific entry from the lru cache
        btrfs: send: use the lru cache to implement the name cache
        btrfs: send: update size of roots array for backref cache entries
        btrfs: send: cache utimes operations for directories if possible
      
      The following test was run before and after applying the whole patchset,
      and on a non-debug kernel (Debian's default kernel config):
      
         #!/bin/bash
      
         MNT=/mnt/sdi
         DEV=/dev/sdi
      
         mkfs.btrfs -f $DEV > /dev/null
         mount $DEV $MNT
      
         mkdir $MNT/A
         for ((i = 1; i <= 20000; i++)); do
             echo -n > $MNT/A/file_$i
         done
      
         btrfs subvolume snapshot -r $MNT $MNT/snap1
      
         mkdir $MNT/B
         for ((i = 20000; i <= 40000; i++)); do
             echo -n > $MNT/B/file_$i
         done
      
         mv $MNT/A/file_* $MNT/B/
      
         btrfs subvolume snapshot -r $MNT $MNT/snap2
      
         start=$(date +%s%N)
         btrfs send -p $MNT/snap1 $MNT/snap2 > /dev/null
         end=$(date +%s%N)
      
         dur=$(( (end - start) / 1000000 ))
         echo "Incremental send took $dur milliseconds"
      
         umount $MNT
      
      Before the whole patchset: 18408 milliseconds
      After the whole patchset:   1942 milliseconds  (9.5x speedup)
      
      Using 60000 files instead of 40000:
      
      Before the whole patchset: 39764 milliseconds
      After the whole patchset:   3076 milliseconds  (12.9x speedup)
      
      Using 20000 files instead of 40000:
      
      Before the whole patchset:  5072 milliseconds
      After the whole patchset:    916 milliseconds  (5.5x speedup)
      Signed-off-by: default avatarFilipe Manana <fdmanana@suse.com>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      3e49363b
    • Filipe Manana's avatar
      btrfs: send: update size of roots array for backref cache entries · ace79df8
      Filipe Manana authored
      Currently we limit the size of the roots array, for backref cache entries,
      to 12 elements. This is because that number is enough for most cases and
      to make the backref cache entry size to be exactly 128 bytes, so that
      memory is allocated from the kmalloc-128 slab and no space is wasted.
      
      However recent changes in the series refactored the backref cache to be
      more generic and allow it to be reused for other purposes, which resulted
      in increasing the size of the embedded structure btrfs_lru_cache_entry in
      order to allow for supporting inode numbers as keys on 32 bits system and
      allow multiple generations per key. This resulted in increasing the size
      of struct backref_cache_entry from 128 bytes to 152 bytes. Since the cache
      entries are allocated with kmalloc(), it means we end up using the slab
      kmalloc-192, so we end up wasting 40 bytes of memory. So bump the size of
      the roots array from 12 elements to 17 elements, so we end up using 192
      bytes for each backref cache entry.
      
      This patch is part of a larger patchset and the changelog of the last
      patch in the series contains a sample performance test and results.
      The patches that comprise the patchset are the following:
      
        btrfs: send: directly return from did_overwrite_ref() and simplify it
        btrfs: send: avoid unnecessary generation search at did_overwrite_ref()
        btrfs: send: directly return from will_overwrite_ref() and simplify it
        btrfs: send: avoid extra b+tree searches when checking reference overrides
        btrfs: send: remove send_progress argument from can_rmdir()
        btrfs: send: avoid duplicated orphan dir allocation and initialization
        btrfs: send: avoid unnecessary orphan dir rbtree search at can_rmdir()
        btrfs: send: reduce searches on parent root when checking if dir can be removed
        btrfs: send: iterate waiting dir move rbtree only once when processing refs
        btrfs: send: initialize all the red black trees earlier
        btrfs: send: genericize the backref cache to allow it to be reused
        btrfs: adapt lru cache to allow for 64 bits keys on 32 bits systems
        btrfs: send: cache information about created directories
        btrfs: allow a generation number to be associated with lru cache entries
        btrfs: add an api to delete a specific entry from the lru cache
        btrfs: send: use the lru cache to implement the name cache
        btrfs: send: update size of roots array for backref cache entries
        btrfs: send: cache utimes operations for directories if possible
      Signed-off-by: default avatarFilipe Manana <fdmanana@suse.com>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      ace79df8
    • Filipe Manana's avatar
      btrfs: send: use the lru cache to implement the name cache · c48545de
      Filipe Manana authored
      The name cache in send is basically a lru cache implemented with a radix
      tree and linked lists, very similar to the lru cache module which is used
      for the send backref cache and the cache of previously created directories
      during a send operation. So remove all the custom caching code for the
      name cache and make it use the lru cache instead.
      
      One particular detail to note is that the current cache behaves a bit
      differently when it comes to eviction of entries. Namely when after
      inserting a new name in the cache, if the cache now has 256 entries, we
      evict the last 128 LRU entries. The lru_cache.{c,h} module behaves a bit
      differently in that once we reach the cache limit, we evict a single LRU
      entry. In practice this doesn't make much difference, but it's actually
      better to evict just one entry instead of half of the entries, as there's
      always a chance we will need a name stored in one of that last 128 removed
      entries.
      
      This patch is part of a larger patchset and the changelog of the last
      patch in the series contains a sample performance test and results.
      The patches that comprise the patchset are the following:
      
        btrfs: send: directly return from did_overwrite_ref() and simplify it
        btrfs: send: avoid unnecessary generation search at did_overwrite_ref()
        btrfs: send: directly return from will_overwrite_ref() and simplify it
        btrfs: send: avoid extra b+tree searches when checking reference overrides
        btrfs: send: remove send_progress argument from can_rmdir()
        btrfs: send: avoid duplicated orphan dir allocation and initialization
        btrfs: send: avoid unnecessary orphan dir rbtree search at can_rmdir()
        btrfs: send: reduce searches on parent root when checking if dir can be removed
        btrfs: send: iterate waiting dir move rbtree only once when processing refs
        btrfs: send: initialize all the red black trees earlier
        btrfs: send: genericize the backref cache to allow it to be reused
        btrfs: adapt lru cache to allow for 64 bits keys on 32 bits systems
        btrfs: send: cache information about created directories
        btrfs: allow a generation number to be associated with lru cache entries
        btrfs: add an api to delete a specific entry from the lru cache
        btrfs: send: use the lru cache to implement the name cache
        btrfs: send: update size of roots array for backref cache entries
        btrfs: send: cache utimes operations for directories if possible
      Signed-off-by: default avatarFilipe Manana <fdmanana@suse.com>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      c48545de
  2. 13 Feb, 2023 13 commits
    • Filipe Manana's avatar
      btrfs: add an api to delete a specific entry from the lru cache · d588adae
      Filipe Manana authored
      In order to replace the open coded name cache in send with the lru cache,
      we need an API for the lru cache to delete a specific entry for which we
      did a previous lookup. This adds the API for it, and a next patch in the
      series will use it.
      
      This patch is part of a larger patchset and the changelog of the last
      patch in the series contains a sample performance test and results.
      The patches that comprise the patchset are the following:
      
        btrfs: send: directly return from did_overwrite_ref() and simplify it
        btrfs: send: avoid unnecessary generation search at did_overwrite_ref()
        btrfs: send: directly return from will_overwrite_ref() and simplify it
        btrfs: send: avoid extra b+tree searches when checking reference overrides
        btrfs: send: remove send_progress argument from can_rmdir()
        btrfs: send: avoid duplicated orphan dir allocation and initialization
        btrfs: send: avoid unnecessary orphan dir rbtree search at can_rmdir()
        btrfs: send: reduce searches on parent root when checking if dir can be removed
        btrfs: send: iterate waiting dir move rbtree only once when processing refs
        btrfs: send: initialize all the red black trees earlier
        btrfs: send: genericize the backref cache to allow it to be reused
        btrfs: adapt lru cache to allow for 64 bits keys on 32 bits systems
        btrfs: send: cache information about created directories
        btrfs: allow a generation number to be associated with lru cache entries
        btrfs: add an api to delete a specific entry from the lru cache
        btrfs: send: use the lru cache to implement the name cache
        btrfs: send: update size of roots array for backref cache entries
        btrfs: send: cache utimes operations for directories if possible
      Signed-off-by: default avatarFilipe Manana <fdmanana@suse.com>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      d588adae
    • Filipe Manana's avatar
      btrfs: allow a generation number to be associated with lru cache entries · 0da0c560
      Filipe Manana authored
      This allows an optional generation number to be associated to each entry
      of the lru cache. Entries with the same key but different generations, are
      stored in the linked list to which the maple tree points to. This is meant
      to be used when there's a small number of different generations, so the
      impact of searching a linked list is negligible. The goal is to get rid of
      the open coded name cache in the send code (which uses a radix tree and
      a similar linked list of values/entries) and use instead the lru cache
      module. For that particular use case we have at most 2 generations that
      are associated to each key (inode number): one generation for the send
      root and another generation for the parent root. The actual migration of
      the send name cache is done in the next patch in the series.
      
      This patch is part of a larger patchset and the changelog of the last
      patch in the series contains a sample performance test and results.
      The patches that comprise the patchset are the following:
      
        btrfs: send: directly return from did_overwrite_ref() and simplify it
        btrfs: send: avoid unnecessary generation search at did_overwrite_ref()
        btrfs: send: directly return from will_overwrite_ref() and simplify it
        btrfs: send: avoid extra b+tree searches when checking reference overrides
        btrfs: send: remove send_progress argument from can_rmdir()
        btrfs: send: avoid duplicated orphan dir allocation and initialization
        btrfs: send: avoid unnecessary orphan dir rbtree search at can_rmdir()
        btrfs: send: reduce searches on parent root when checking if dir can be removed
        btrfs: send: iterate waiting dir move rbtree only once when processing refs
        btrfs: send: initialize all the red black trees earlier
        btrfs: send: genericize the backref cache to allow it to be reused
        btrfs: adapt lru cache to allow for 64 bits keys on 32 bits systems
        btrfs: send: cache information about created directories
        btrfs: allow a generation number to be associated with lru cache entries
        btrfs: add an api to delete a specific entry from the lru cache
        btrfs: send: use the lru cache to implement the name cache
        btrfs: send: update size of roots array for backref cache entries
        btrfs: send: cache utimes operations for directories if possible
      Signed-off-by: default avatarFilipe Manana <fdmanana@suse.com>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      0da0c560
    • Filipe Manana's avatar
      btrfs: send: cache information about created directories · e8a7f49d
      Filipe Manana authored
      During an incremental send, when processing the reference for an inode
      we need to check if the directory where the new reference is located was
      already created before creating the new reference. This check, which is
      done by the helper did_create_dir(), can be expensive if the directory
      has many entries, since it consists in searching the send root's b+tree
      and visiting every single dir index key until we either find one which
      points to an inode with a number smaller than the current inode's number
      or until we visited all index keys. So it doesn't scale well for very
      large directories.
      
      So improve on this by caching created directories using a lru cache, and
      limiting its size to 64 entries, which results in using at most 4096
      bytes of memory. The caching is optional, if we fail to allocate memory,
      we just proceed as before and use the existing slower path.
      
      This patch is part of a larger patchset and the changelog of the last
      patch in the series contains a sample performance test and results.
      The patches that comprise the patchset are the following:
      
        btrfs: send: directly return from did_overwrite_ref() and simplify it
        btrfs: send: avoid unnecessary generation search at did_overwrite_ref()
        btrfs: send: directly return from will_overwrite_ref() and simplify it
        btrfs: send: avoid extra b+tree searches when checking reference overrides
        btrfs: send: remove send_progress argument from can_rmdir()
        btrfs: send: avoid duplicated orphan dir allocation and initialization
        btrfs: send: avoid unnecessary orphan dir rbtree search at can_rmdir()
        btrfs: send: reduce searches on parent root when checking if dir can be removed
        btrfs: send: iterate waiting dir move rbtree only once when processing refs
        btrfs: send: initialize all the red black trees earlier
        btrfs: send: genericize the backref cache to allow it to be reused
        btrfs: adapt lru cache to allow for 64 bits keys on 32 bits systems
        btrfs: send: cache information about created directories
        btrfs: allow a generation number to be associated with lru cache entries
        btrfs: add an api to delete a specific entry from the lru cache
        btrfs: send: use the lru cache to implement the name cache
        btrfs: send: update size of roots array for backref cache entries
        btrfs: send: cache utimes operations for directories if possible
      Signed-off-by: default avatarFilipe Manana <fdmanana@suse.com>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      e8a7f49d
    • Filipe Manana's avatar
      btrfs: adapt lru cache to allow for 64 bits keys on 32 bits systems · 6273ee62
      Filipe Manana authored
      The lru cache is backed by a maple tree, which uses the unsigned long
      type for keys, and that type has a width of 32 bits on 32 bits systems
      and a width of 64 bits on 64 bits systems.
      
      Currently there is only one user of the lru cache, the send backref cache,
      which uses a sector number as a key, a logical address right shifted by
      fs_info->sectorsize_bits, so a 32 bits width is not yet a problem (the
      same happens with the radix tree we use to track extent buffers,
      fs_info->buffer_radix).
      
      However the next patches in the series will start using the lru cache for
      cases where inode numbers are the keys, and the inode numbers are always
      64 bits, even if we are running on a 32 bits system.
      
      So adapt the lru cache to allow multiple values under the same key, by
      having the maple tree store a head entry that points to a list of entries
      instead of pointing to a single entry. This is a similar approach to what
      we currently do for the name cache in send (which uses a radix tree that
      has indexes with an unsigned long type as well), and will allow later to
      use the lru cache for the send name cache as well.
      
      This patch is part of a larger patchset and the changelog of the last
      patch in the series contains a sample performance test and results.
      The patches that comprise the patchset are the following:
      
        btrfs: send: directly return from did_overwrite_ref() and simplify it
        btrfs: send: avoid unnecessary generation search at did_overwrite_ref()
        btrfs: send: directly return from will_overwrite_ref() and simplify it
        btrfs: send: avoid extra b+tree searches when checking reference overrides
        btrfs: send: remove send_progress argument from can_rmdir()
        btrfs: send: avoid duplicated orphan dir allocation and initialization
        btrfs: send: avoid unnecessary orphan dir rbtree search at can_rmdir()
        btrfs: send: reduce searches on parent root when checking if dir can be removed
        btrfs: send: iterate waiting dir move rbtree only once when processing refs
        btrfs: send: initialize all the red black trees earlier
        btrfs: send: genericize the backref cache to allow it to be reused
        btrfs: adapt lru cache to allow for 64 bits keys on 32 bits systems
        btrfs: send: cache information about created directories
        btrfs: allow a generation number to be associated with lru cache entries
        btrfs: add an api to delete a specific entry from the lru cache
        btrfs: send: use the lru cache to implement the name cache
        btrfs: send: update size of roots array for backref cache entries
        btrfs: send: cache utimes operations for directories if possible
      Signed-off-by: default avatarFilipe Manana <fdmanana@suse.com>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      6273ee62
    • Filipe Manana's avatar
      btrfs: send: genericize the backref cache to allow it to be reused · 90b90d4a
      Filipe Manana authored
      The backref cache is a cache backed by a maple tree and a linked list to
      keep track of temporal access to cached entries (the LRU entry always at
      the head of the list). This type of caching method is going to be useful
      in other scenarios, so make the cache implementation more generic and
      move it into its own header and source files.
      
      This patch is part of a larger patchset and the changelog of the last
      patch in the series contains a sample performance test and results.
      The patches that comprise the patchset are the following:
      
        btrfs: send: directly return from did_overwrite_ref() and simplify it
        btrfs: send: avoid unnecessary generation search at did_overwrite_ref()
        btrfs: send: directly return from will_overwrite_ref() and simplify it
        btrfs: send: avoid extra b+tree searches when checking reference overrides
        btrfs: send: remove send_progress argument from can_rmdir()
        btrfs: send: avoid duplicated orphan dir allocation and initialization
        btrfs: send: avoid unnecessary orphan dir rbtree search at can_rmdir()
        btrfs: send: reduce searches on parent root when checking if dir can be removed
        btrfs: send: iterate waiting dir move rbtree only once when processing refs
        btrfs: send: initialize all the red black trees earlier
        btrfs: send: genericize the backref cache to allow it to be reused
        btrfs: adapt lru cache to allow for 64 bits keys on 32 bits systems
        btrfs: send: cache information about created directories
        btrfs: allow a generation number to be associated with lru cache entries
        btrfs: add an api to delete a specific entry from the lru cache
        btrfs: send: use the lru cache to implement the name cache
        btrfs: send: update size of roots array for backref cache entries
        btrfs: send: cache utimes operations for directories if possible
      Signed-off-by: default avatarFilipe Manana <fdmanana@suse.com>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      90b90d4a
    • Filipe Manana's avatar
      btrfs: send: initialize all the red black trees earlier · d307d2f3
      Filipe Manana authored
      After we allocate the send context object and before we initialize all
      the red black trees, we can jump to the 'out' label if some errors happen,
      and then under the 'out' label we use RB_EMPTY_ROOT() against some of the
      those trees, which we have not yet initialized. This happens to work out
      ok because the send context object was initialized to zeroes with kzalloc
      and the RB_ROOT initializer just happens to have the following definition:
      
          #define RB_ROOT (struct rb_root) { NULL, }
      
      But it's really neither clean nor a good practice as RB_ROOT is supposed
      to be opaque and in case it changes or we change those red black trees to
      some other data structure, it leaves us in a precarious situation.
      
      So initialize all the red black trees immediately after allocating the
      send context and before any jump into the 'out' label.
      
      This patch is part of a larger patchset and the changelog of the last
      patch in the series contains a sample performance test and results.
      The patches that comprise the patchset are the following:
      
        btrfs: send: directly return from did_overwrite_ref() and simplify it
        btrfs: send: avoid unnecessary generation search at did_overwrite_ref()
        btrfs: send: directly return from will_overwrite_ref() and simplify it
        btrfs: send: avoid extra b+tree searches when checking reference overrides
        btrfs: send: remove send_progress argument from can_rmdir()
        btrfs: send: avoid duplicated orphan dir allocation and initialization
        btrfs: send: avoid unnecessary orphan dir rbtree search at can_rmdir()
        btrfs: send: reduce searches on parent root when checking if dir can be removed
        btrfs: send: iterate waiting dir move rbtree only once when processing refs
        btrfs: send: initialize all the red black trees earlier
        btrfs: send: genericize the backref cache to allow it to be reused
        btrfs: adapt lru cache to allow for 64 bits keys on 32 bits systems
        btrfs: send: cache information about created directories
        btrfs: allow a generation number to be associated with lru cache entries
        btrfs: add an api to delete a specific entry from the lru cache
        btrfs: send: use the lru cache to implement the name cache
        btrfs: send: update size of roots array for backref cache entries
        btrfs: send: cache utimes operations for directories if possible
      Signed-off-by: default avatarFilipe Manana <fdmanana@suse.com>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      d307d2f3
    • Filipe Manana's avatar
      btrfs: send: iterate waiting dir move rbtree only once when processing refs · 8c139e1d
      Filipe Manana authored
      When processing the new references for an inode, we unnecessarily iterate
      twice the waiting dir moves rbtree, once with is_waiting_for_move() and
      if we found an entry in the rbtree, we iterate it again with a call to
      get_waiting_dir_move(). This is pointless, we can make this simpler and
      more efficient by calling only get_waiting_dir_move(), so just do that.
      
      This patch is part of a larger patchset and the changelog of the last
      patch in the series contains a sample performance test and results.
      The patches that comprise the patchset are the following:
      
        btrfs: send: directly return from did_overwrite_ref() and simplify it
        btrfs: send: avoid unnecessary generation search at did_overwrite_ref()
        btrfs: send: directly return from will_overwrite_ref() and simplify it
        btrfs: send: avoid extra b+tree searches when checking reference overrides
        btrfs: send: remove send_progress argument from can_rmdir()
        btrfs: send: avoid duplicated orphan dir allocation and initialization
        btrfs: send: avoid unnecessary orphan dir rbtree search at can_rmdir()
        btrfs: send: reduce searches on parent root when checking if dir can be removed
        btrfs: send: iterate waiting dir move rbtree only once when processing refs
        btrfs: send: initialize all the red black trees earlier
        btrfs: send: genericize the backref cache to allow it to be reused
        btrfs: adapt lru cache to allow for 64 bits keys on 32 bits systems
        btrfs: send: cache information about created directories
        btrfs: allow a generation number to be associated with lru cache entries
        btrfs: add an api to delete a specific entry from the lru cache
        btrfs: send: use the lru cache to implement the name cache
        btrfs: send: update size of roots array for backref cache entries
        btrfs: send: cache utimes operations for directories if possible
      Signed-off-by: default avatarFilipe Manana <fdmanana@suse.com>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      8c139e1d
    • Filipe Manana's avatar
      btrfs: send: reduce searches on parent root when checking if dir can be removed · 474e4761
      Filipe Manana authored
      During an incremental send, every time we remove a reference (dentry) for
      an inode and the parent directory does not exists anymore in the send
      root, we go check if we can remove the directory by making a call to
      can_rmdir(). This helper can only return true (value 1) if all dentries
      were already removed, and for that it always does a search on the parent
      root for dir index keys - if it finds any dentry referring to an inode
      with a number higher then the inode currently being processed, then the
      directory can not be removed and it must return false (value 0).
      
      However that means if a directory that was deleted had 1000 dentries, and
      each one pointed to an inode with a number higher then the number of the
      directory's inode, we end up doing 1000 searches on the parent root.
      Typically files are created in a directory after the directory was created
      and therefore they get an higher inode number than the directory. It's
      also common to have the each dentry pointing to an inode with a higher
      number then the inodes the previous dentries point to, for example when
      creating a series of files inside a directory, a very common pattern.
      
      So improve on that by having the first call to can_rmdir() for a directory
      to check the number of the inode that the last dentry points to and cache
      that inode number in the orphan dir structure. Then every subsequent call
      to can_rmdir() can avoid doing a search on the parent root if the number
      of the inode currently being processed is smaller than cached inode number
      at the directory's orphan dir structure.
      
      This patch is part of a larger patchset and the changelog of the last
      patch in the series contains a sample performance test and results.
      The patches that comprise the patchset are the following:
      
        btrfs: send: directly return from did_overwrite_ref() and simplify it
        btrfs: send: avoid unnecessary generation search at did_overwrite_ref()
        btrfs: send: directly return from will_overwrite_ref() and simplify it
        btrfs: send: avoid extra b+tree searches when checking reference overrides
        btrfs: send: remove send_progress argument from can_rmdir()
        btrfs: send: avoid duplicated orphan dir allocation and initialization
        btrfs: send: avoid unnecessary orphan dir rbtree search at can_rmdir()
        btrfs: send: reduce searches on parent root when checking if dir can be removed
        btrfs: send: iterate waiting dir move rbtree only once when processing refs
        btrfs: send: initialize all the red black trees earlier
        btrfs: send: genericize the backref cache to allow it to be reused
        btrfs: adapt lru cache to allow for 64 bits keys on 32 bits systems
        btrfs: send: cache information about created directories
        btrfs: allow a generation number to be associated with lru cache entries
        btrfs: add an api to delete a specific entry from the lru cache
        btrfs: send: use the lru cache to implement the name cache
        btrfs: send: update size of roots array for backref cache entries
        btrfs: send: cache utimes operations for directories if possible
      Signed-off-by: default avatarFilipe Manana <fdmanana@suse.com>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      474e4761
    • Filipe Manana's avatar
      btrfs: send: avoid unnecessary orphan dir rbtree search at can_rmdir() · 78cf1a95
      Filipe Manana authored
      At can_rmdir() we start by searching the orphan dirs rbtree for an orphan
      dir object for the target directory. Later when iterating over the dir
      index keys, if we find that any dir entry points to inode for which there
      is a pending dir move or the inode was not yet processed, we exit because
      we can't remove the directory yet. However we end up always calling
      add_orphan_dir_info(), which will iterate again the rbtree and if there is
      already an orphan dir object (created by the first call to can_rmdir()),
      it returns the existing object. This is unnecessary work because in case
      there is already an existing orphan dir object, we got a reference to it
      at the start of can_rmdir(). So skip the call to add_orphan_dir_info()
      if we already have a reference for an orphan dir object.
      
      This patch is part of a larger patchset and the changelog of the last
      patch in the series contains a sample performance test and results.
      The patches that comprise the patchset are the following:
      
        btrfs: send: directly return from did_overwrite_ref() and simplify it
        btrfs: send: avoid unnecessary generation search at did_overwrite_ref()
        btrfs: send: directly return from will_overwrite_ref() and simplify it
        btrfs: send: avoid extra b+tree searches when checking reference overrides
        btrfs: send: remove send_progress argument from can_rmdir()
        btrfs: send: avoid duplicated orphan dir allocation and initialization
        btrfs: send: avoid unnecessary orphan dir rbtree search at can_rmdir()
        btrfs: send: reduce searches on parent root when checking if dir can be removed
        btrfs: send: iterate waiting dir move rbtree only once when processing refs
        btrfs: send: initialize all the red black trees earlier
        btrfs: send: genericize the backref cache to allow it to be reused
        btrfs: adapt lru cache to allow for 64 bits keys on 32 bits systems
        btrfs: send: cache information about created directories
        btrfs: allow a generation number to be associated with lru cache entries
        btrfs: add an api to delete a specific entry from the lru cache
        btrfs: send: use the lru cache to implement the name cache
        btrfs: send: update size of roots array for backref cache entries
        btrfs: send: cache utimes operations for directories if possible
      Signed-off-by: default avatarFilipe Manana <fdmanana@suse.com>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      78cf1a95
    • Filipe Manana's avatar
      btrfs: send: avoid duplicated orphan dir allocation and initialization · d921b9cf
      Filipe Manana authored
      At can_rmdir() we are allocating and initializing an orphan dir object
      twice. This can be deduplicated outside of the loop that iterates over
      the dir index keys. So deduplicate that code, even because other patch
      in the series will need to add more initialization code and another one
      will add one more condition.
      
      This patch is part of a larger patchset and the changelog of the last
      patch in the series contains a sample performance test and results.
      The patches that comprise the patchset are the following:
      
        btrfs: send: directly return from did_overwrite_ref() and simplify it
        btrfs: send: avoid unnecessary generation search at did_overwrite_ref()
        btrfs: send: directly return from will_overwrite_ref() and simplify it
        btrfs: send: avoid extra b+tree searches when checking reference overrides
        btrfs: send: remove send_progress argument from can_rmdir()
        btrfs: send: avoid duplicated orphan dir allocation and initialization
        btrfs: send: avoid unnecessary orphan dir rbtree search at can_rmdir()
        btrfs: send: reduce searches on parent root when checking if dir can be removed
        btrfs: send: iterate waiting dir move rbtree only once when processing refs
        btrfs: send: initialize all the red black trees earlier
        btrfs: send: genericize the backref cache to allow it to be reused
        btrfs: adapt lru cache to allow for 64 bits keys on 32 bits systems
        btrfs: send: cache information about created directories
        btrfs: allow a generation number to be associated with lru cache entries
        btrfs: add an api to delete a specific entry from the lru cache
        btrfs: send: use the lru cache to implement the name cache
        btrfs: send: update size of roots array for backref cache entries
        btrfs: send: cache utimes operations for directories if possible
      Signed-off-by: default avatarFilipe Manana <fdmanana@suse.com>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      d921b9cf
    • Filipe Manana's avatar
      btrfs: send: remove send_progress argument from can_rmdir() · 24970ccb
      Filipe Manana authored
      All callers of can_rmdir() pass sctx->cur_ino as the value for the
      send_progress argument, so remove the argument and directly use
      sctx->cur_ino.
      
      This patch is part of a larger patchset and the changelog of the last
      patch in the series contains a sample performance test and results.
      The patches that comprise the patchset are the following:
      
        btrfs: send: directly return from did_overwrite_ref() and simplify it
        btrfs: send: avoid unnecessary generation search at did_overwrite_ref()
        btrfs: send: directly return from will_overwrite_ref() and simplify it
        btrfs: send: avoid extra b+tree searches when checking reference overrides
        btrfs: send: remove send_progress argument from can_rmdir()
        btrfs: send: avoid duplicated orphan dir allocation and initialization
        btrfs: send: avoid unnecessary orphan dir rbtree search at can_rmdir()
        btrfs: send: reduce searches on parent root when checking if dir can be removed
        btrfs: send: iterate waiting dir move rbtree only once when processing refs
        btrfs: send: initialize all the red black trees earlier
        btrfs: send: genericize the backref cache to allow it to be reused
        btrfs: adapt lru cache to allow for 64 bits keys on 32 bits systems
        btrfs: send: cache information about created directories
        btrfs: allow a generation number to be associated with lru cache entries
        btrfs: add an api to delete a specific entry from the lru cache
        btrfs: send: use the lru cache to implement the name cache
        btrfs: send: update size of roots array for backref cache entries
        btrfs: send: cache utimes operations for directories if possible
      Signed-off-by: default avatarFilipe Manana <fdmanana@suse.com>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      24970ccb
    • Filipe Manana's avatar
      btrfs: send: avoid extra b+tree searches when checking reference overrides · 498581f3
      Filipe Manana authored
      During an incremental send, when processing the new references of an inode
      (either it's a new inode or an existing one renamed/moved), he will search
      the b+tree of the send or parent roots in order to find out the inode item
      of the parent directory and extract its generation. However we are doing
      that search twice, once with is_inode_existent() -> get_cur_inode_state()
      and then again at did_overwrite_ref() or will_overwrite_ref().
      
      So avoid that and get the generation at get_cur_inode_state() and then
      propagate it up to did_overwrite_ref() and will_overwrite_ref().
      
      This patch is part of a larger patchset and the changelog of the last
      patch in the series contains a sample performance test and results.
      The patches that comprise the patchset are the following:
      
        btrfs: send: directly return from did_overwrite_ref() and simplify it
        btrfs: send: avoid unnecessary generation search at did_overwrite_ref()
        btrfs: send: directly return from will_overwrite_ref() and simplify it
        btrfs: send: avoid extra b+tree searches when checking reference overrides
        btrfs: send: remove send_progress argument from can_rmdir()
        btrfs: send: avoid duplicated orphan dir allocation and initialization
        btrfs: send: avoid unnecessary orphan dir rbtree search at can_rmdir()
        btrfs: send: reduce searches on parent root when checking if dir can be removed
        btrfs: send: iterate waiting dir move rbtree only once when processing refs
        btrfs: send: initialize all the red black trees earlier
        btrfs: send: genericize the backref cache to allow it to be reused
        btrfs: adapt lru cache to allow for 64 bits keys on 32 bits systems
        btrfs: send: cache information about created directories
        btrfs: allow a generation number to be associated with lru cache entries
        btrfs: add an api to delete a specific entry from the lru cache
        btrfs: send: use the lru cache to implement the name cache
        btrfs: send: update size of roots array for backref cache entries
        btrfs: send: cache utimes operations for directories if possible
      Signed-off-by: default avatarFilipe Manana <fdmanana@suse.com>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      498581f3
    • Filipe Manana's avatar
      btrfs: send: directly return from will_overwrite_ref() and simplify it · b3047a42
      Filipe Manana authored
      There are no resources to release before will_overwrite_ref() returns, so
      we don't really need the 'out' label and jumping to it when conditions are
      met - we can directly return and get rid of the label and jumps. Also we
      can deal with -ENOENT and other errors in a single if-else logic, as it's
      more straightforward.
      
      This helps the next patch in the series to be more simple as well.
      
      This patch is part of a larger patchset and the changelog of the last
      patch in the series contains a sample performance test and results.
      The patches that comprise the patchset are the following:
      
        btrfs: send: directly return from did_overwrite_ref() and simplify it
        btrfs: send: avoid unnecessary generation search at did_overwrite_ref()
        btrfs: send: directly return from will_overwrite_ref() and simplify it
        btrfs: send: avoid extra b+tree searches when checking reference overrides
        btrfs: send: remove send_progress argument from can_rmdir()
        btrfs: send: avoid duplicated orphan dir allocation and initialization
        btrfs: send: avoid unnecessary orphan dir rbtree search at can_rmdir()
        btrfs: send: reduce searches on parent root when checking if dir can be removed
        btrfs: send: iterate waiting dir move rbtree only once when processing refs
        btrfs: send: initialize all the red black trees earlier
        btrfs: send: genericize the backref cache to allow it to be reused
        btrfs: adapt lru cache to allow for 64 bits keys on 32 bits systems
        btrfs: send: cache information about created directories
        btrfs: allow a generation number to be associated with lru cache entries
        btrfs: add an api to delete a specific entry from the lru cache
        btrfs: send: use the lru cache to implement the name cache
        btrfs: send: update size of roots array for backref cache entries
        btrfs: send: cache utimes operations for directories if possible
      Signed-off-by: default avatarFilipe Manana <fdmanana@suse.com>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      b3047a42