1. 24 Jan, 2018 1 commit
    • Josef Bacik's avatar
      Btrfs: fix stale entries in readdir · e4fd493c
      Josef Bacik authored
      In fixing the readdir+pagefault deadlock I accidentally introduced a
      stale entry regression in readdir.  If we get close to full for the
      temporary buffer, and then skip a few delayed deletions, and then try to
      add another entry that won't fit, we will emit the entries we found and
      retry.  Unfortunately we delete entries from our del_list as we find
      them, assuming we won't need them.  However our pos will be with
      whatever our last entry was, which could be before the delayed deletions
      we skipped, so the next search will add the deleted entries back into
      our readdir buffer.  So instead don't delete entries we find in our
      del_list so we can make sure we always find our delayed deletions.  This
      is a slight perf hit for readdir with lots of pending deletions, but
      hopefully this isn't a common occurrence.  If it is we can revist this
      and optimize it.
      
      cc: stable@vger.kernel.org
      Fixes: 23b5ec74 ("btrfs: fix readdir deadlock with pagefault")
      Signed-off-by: default avatarJosef Bacik <jbacik@fb.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      e4fd493c
  2. 02 Jan, 2018 2 commits
    • Chris Mason's avatar
      btrfs: fix refcount_t usage when deleting btrfs_delayed_nodes · ec35e48b
      Chris Mason authored
      refcounts have a generic implementation and an asm optimized one.  The
      generic version has extra debugging to make sure that once a refcount
      goes to zero, refcount_inc won't increase it.
      
      The btrfs delayed inode code wasn't expecting this, and we're tripping
      over the warnings when the generic refcounts are used.  We ended up with
      this race:
      
      Process A                                         Process B
                                                        btrfs_get_delayed_node()
      						  spin_lock(root->inode_lock)
      						  radix_tree_lookup()
      __btrfs_release_delayed_node()
      refcount_dec_and_test(&delayed_node->refs)
      our refcount is now zero
      						  refcount_add(2) <---
      						  warning here, refcount
                                                        unchanged
      
      spin_lock(root->inode_lock)
      radix_tree_delete()
      
      With the generic refcounts, we actually warn again when process B above
      tries to release his refcount because refcount_add() turned into a
      no-op.
      
      We saw this in production on older kernels without the asm optimized
      refcounts.
      
      The fix used here is to use refcount_inc_not_zero() to detect when the
      object is in the middle of being freed and return NULL.  This is almost
      always the right answer anyway, since we usually end up pitching the
      delayed_node if it didn't have fresh data in it.
      
      This also changes __btrfs_release_delayed_node() to remove the extra
      check for zero refcounts before radix tree deletion.
      btrfs_get_delayed_node() was the only path that was allowing refcounts
      to go from zero to one.
      
      Fixes: 6de5f18e ("btrfs: fix refcount_t usage when deleting btrfs_delayed_node")
      CC: <stable@vger.kernel.org> # 4.12+
      Signed-off-by: default avatarChris Mason <clm@fb.com>
      Reviewed-by: default avatarLiu Bo <bo.li.liu@oracle.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      ec35e48b
    • Nikolay Borisov's avatar
      btrfs: Fix flush bio leak · beed9263
      Nikolay Borisov authored
      Commit e0ae9994 ("btrfs: preallocate device flush bio") reworked
      the way the flush bio is allocated and used. Concretely it allocates
      the bio in __alloc_device and then re-uses it multiple times with a
      very simple endio routine that just calls complete() without consuming
      a reference. Allocated bios by default come with a ref count of 1,
      which is then consumed by the endio routine (or not, in which case they
      should be bio_put by the caller). The way the impleementation works now
      is that the flush bio has a refcount of 2 and we only ever bio_put it
      once, leaving it to hang indefinitely. Fix this by removing the extra
      bio_get in __alloc_device.
      
      Fixes: e0ae9994 ("btrfs: preallocate device flush bio")
      Signed-off-by: default avatarNikolay Borisov <nborisov@suse.com>
      Reviewed-by: default avatarLiu Bo <bo.li.liu@oracle.com>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      beed9263
  3. 06 Dec, 2017 5 commits
    • Nikolay Borisov's avatar
      btrfs: Fix possible off-by-one in btrfs_search_path_in_tree · c8bcbfbd
      Nikolay Borisov authored
      The name char array passed to btrfs_search_path_in_tree is of size
      BTRFS_INO_LOOKUP_PATH_MAX (4080). So the actual accessible char indexes
      are in the range of [0, 4079]. Currently the code uses the define but this
      represents an off-by-one.
      
      Implications:
      
      Size of btrfs_ioctl_ino_lookup_args is 4096, so the new byte will be
      written to extra space, not some padding that could be provided by the
      allocator.
      
      btrfs-progs store the arguments on stack, but kernel does own copy of
      the ioctl buffer and the off-by-one overwrite does not affect userspace,
      but the ending 0 might be lost.
      
      Kernel ioctl buffer is allocated dynamically so we're overwriting
      somebody else's memory, and the ioctl is privileged if args.objectid is
      not 256. Which is in most cases, but resolving a subvolume stored in
      another directory will trigger that path.
      
      Before this patch the buffer was one byte larger, but then the -1 was
      not added.
      
      Fixes: ac8e9819 ("Btrfs: add search and inode lookup ioctls")
      Signed-off-by: default avatarNikolay Borisov <nborisov@suse.com>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      [ added implications ]
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      c8bcbfbd
    • Omar Sandoval's avatar
      Btrfs: disable FUA if mounted with nobarrier · 1b9e619c
      Omar Sandoval authored
      I was seeing disk flushes still happening when I mounted a Btrfs
      filesystem with nobarrier for testing. This is because we use FUA to
      write out the first super block, and on devices without FUA support, the
      block layer translates FUA to a flush. Even on devices supporting true
      FUA, using FUA when we asked for no barriers is surprising.
      
      Fixes: 387125fc ("Btrfs: fix barrier flushes")
      Signed-off-by: default avatarOmar Sandoval <osandov@fb.com>
      Reviewed-by: default avatarQu Wenruo <wqu@suse.com>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      1b9e619c
    • Jeff Mahoney's avatar
      btrfs: fix missing error return in btrfs_drop_snapshot · e19182c0
      Jeff Mahoney authored
      If btrfs_del_root fails in btrfs_drop_snapshot, we'll pick up the
      error but then return 0 anyway due to mixing err and ret.
      
      Fixes: 79787eaa ("btrfs: replace many BUG_ONs with proper error handling")
      Cc: <stable@vger.kernel.org> # v3.4+
      Signed-off-by: default avatarJeff Mahoney <jeffm@suse.com>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      e19182c0
    • Jeff Mahoney's avatar
      btrfs: handle errors while updating refcounts in update_ref_for_cow · 692826b2
      Jeff Mahoney authored
      Since commit fb235dc0 (btrfs: qgroup: Move half of the qgroup
      accounting time out of commit trans) the assumption that
      btrfs_add_delayed_{data,tree}_ref can only return 0 or -ENOMEM has
      been false.  The qgroup operations call into btrfs_search_slot
      and friends and can now return the full spectrum of error codes.
      
      Fortunately, the fix here is easy since update_ref_for_cow failing
      is already handled so we just need to bail early with the error
      code.
      
      Fixes: fb235dc0 (btrfs: qgroup: Move half of the qgroup accounting ...)
      Cc: <stable@vger.kernel.org> # v4.11+
      Signed-off-by: default avatarJeff Mahoney <jeffm@suse.com>
      Reviewed-by: default avatarEdmund Nadolski <enadolski@suse.com>
      Reviewed-by: default avatarQu Wenruo <wqu@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      692826b2
    • Justin Maggard's avatar
      btrfs: Fix quota reservation leak on preallocated files · b430b775
      Justin Maggard authored
      Commit c6887cd1 ("Btrfs: don't do nocow check unless we have to")
      changed the behavior of __btrfs_buffered_write() so that it first tries
      to get a data space reservation, and then skips the relatively expensive
      nocow check if the reservation succeeded.
      
      If we have quotas enabled, the data space reservation also includes a
      quota reservation.  But in the rewrite case, the space has already been
      accounted for in qgroups.  So btrfs_check_data_free_space() increases
      the quota reservation, but it never gets decreased when the data
      actually gets written and overwrites the pre-existing data.  So we're
      left with both the qgroup and qgroup reservation accounting for the same
      space.
      
      This commit adds the missing btrfs_qgroup_free_data() call in the case
      of BTRFS_ORDERED_PREALLOC extents.
      
      Fixes: c6887cd1 ("Btrfs: don't do nocow check unless we have to")
      Signed-off-by: default avatarJustin Maggard <jmaggard@netgear.com>
      Reviewed-by: default avatarQu Wenruo <wqu@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      b430b775
  4. 28 Nov, 2017 2 commits
    • Filipe Manana's avatar
      Btrfs: incremental send, fix wrong unlink path after renaming file · ea37d599
      Filipe Manana authored
      Under some circumstances, an incremental send operation can issue wrong
      paths for unlink commands related to files that have multiple hard links
      and some (or all) of those links were renamed between the parent and send
      snapshots. Consider the following example:
      
      Parent snapshot
      
       .                                                      (ino 256)
       |---- a/                                               (ino 257)
       |     |---- b/                                         (ino 259)
       |     |     |---- c/                                   (ino 260)
       |     |     |---- f2                                   (ino 261)
       |     |
       |     |---- f2l1                                       (ino 261)
       |
       |---- d/                                               (ino 262)
             |---- f1l1_2                                     (ino 258)
             |---- f2l2                                       (ino 261)
             |---- f1_2                                       (ino 258)
      
      Send snapshot
      
       .                                                      (ino 256)
       |---- a/                                               (ino 257)
       |     |---- f2l1/                                      (ino 263)
       |             |---- b2/                                (ino 259)
       |                   |---- c/                           (ino 260)
       |                   |     |---- d3                     (ino 262)
       |                   |           |---- f1l1_2           (ino 258)
       |                   |           |---- f2l2_2           (ino 261)
       |                   |           |---- f1_2             (ino 258)
       |                   |
       |                   |---- f2                           (ino 261)
       |                   |---- f1l2                         (ino 258)
       |
       |---- d                                                (ino 261)
      
      When computing the incremental send stream the following steps happen:
      
      1) When processing inode 261, a rename operation is issued that renames
         inode 262, which currently as a path of "d", to an orphan name of
         "o262-7-0". This is done because in the send snapshot, inode 261 has
         of its hard links with a path of "d" as well.
      
      2) Two link operations are issued that create the new hard links for
         inode 261, whose names are "d" and "f2l2_2", at paths "/" and
         "o262-7-0/" respectively.
      
      3) Still while processing inode 261, unlink operations are issued to
         remove the old hard links of inode 261, with names "f2l1" and "f2l2",
         at paths "a/" and "d/". However path "d/" does not correspond anymore
         to the directory inode 262 but corresponds instead to a hard link of
         inode 261 (link command issued in the previous step). This makes the
         receiver fail with a ENOTDIR error when attempting the unlink
         operation.
      
      The problem happens because before sending the unlink operation, we failed
      to detect that inode 262 was one of ancestors for inode 261 in the parent
      snapshot, and therefore we didn't recompute the path for inode 262 before
      issuing the unlink operation for the link named "f2l2" of inode 262. The
      detection failed because the function "is_ancestor()" only follows the
      first hard link it finds for an inode instead of all of its hard links
      (as it was originally created for being used with directories only, for
      which only one hard link exists). So fix this by making "is_ancestor()"
      follow all hard links of the input inode.
      
      A test case for fstests follows soon.
      Signed-off-by: default avatarFilipe Manana <fdmanana@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      ea37d599
    • Qu Wenruo's avatar
      btrfs: tree-checker: Fix false panic for sanity test · 69fc6cbb
      Qu Wenruo authored
      [BUG]
      If we run btrfs with CONFIG_BTRFS_FS_RUN_SANITY_TESTS=y, it will
      instantly cause kernel panic like:
      
      ------
      ...
      assertion failed: 0, file: fs/btrfs/disk-io.c, line: 3853
      ...
      Call Trace:
       btrfs_mark_buffer_dirty+0x187/0x1f0 [btrfs]
       setup_items_for_insert+0x385/0x650 [btrfs]
       __btrfs_drop_extents+0x129a/0x1870 [btrfs]
      ...
      -----
      
      [Cause]
      Btrfs will call btrfs_check_leaf() in btrfs_mark_buffer_dirty() to check
      if the leaf is valid with CONFIG_BTRFS_FS_RUN_SANITY_TESTS=y.
      
      However quite some btrfs_mark_buffer_dirty() callers(*) don't really
      initialize its item data but only initialize its item pointers, leaving
      item data uninitialized.
      
      This makes tree-checker catch uninitialized data as error, causing
      such panic.
      
      *: These callers include but not limited to
      setup_items_for_insert()
      btrfs_split_item()
      btrfs_expand_item()
      
      [Fix]
      Add a new parameter @check_item_data to btrfs_check_leaf().
      With @check_item_data set to false, item data check will be skipped and
      fallback to old btrfs_check_leaf() behavior.
      
      So we can still get early warning if we screw up item pointers, and
      avoid false panic.
      
      Cc: Filipe Manana <fdmanana@gmail.com>
      Reported-by: default avatarLakshmipathi.G <lakshmipathi.g@gmail.com>
      Signed-off-by: default avatarQu Wenruo <wqu@suse.com>
      Reviewed-by: default avatarLiu Bo <bo.li.liu@oracle.com>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      69fc6cbb
  5. 27 Nov, 2017 3 commits
    • Liu Bo's avatar
      Btrfs: fix list_add corruption and soft lockups in fsync · ebb70442
      Liu Bo authored
      Xfstests btrfs/146 revealed this corruption,
      
      [   58.138831] Buffer I/O error on dev dm-0, logical block 2621424, async page read
      [   58.151233] BTRFS error (device sdf): bdev /dev/mapper/error-test errs: wr 1, rd 0, flush 0, corrupt 0, gen 0
      [   58.152403] list_add corruption. prev->next should be next (ffff88005e6775d8), but was ffffc9000189be88. (prev=ffffc9000189be88).
      [   58.153518] ------------[ cut here ]------------
      [   58.153892] WARNING: CPU: 1 PID: 1287 at lib/list_debug.c:31 __list_add_valid+0x169/0x1f0
      ...
      [   58.157379] RIP: 0010:__list_add_valid+0x169/0x1f0
      ...
      [   58.161956] Call Trace:
      [   58.162264]  btrfs_log_inode_parent+0x5bd/0xfb0 [btrfs]
      [   58.163583]  btrfs_log_dentry_safe+0x60/0x80 [btrfs]
      [   58.164003]  btrfs_sync_file+0x4c2/0x6f0 [btrfs]
      [   58.164393]  vfs_fsync_range+0x5f/0xd0
      [   58.164898]  do_fsync+0x5a/0x90
      [   58.165170]  SyS_fsync+0x10/0x20
      [   58.165395]  entry_SYSCALL_64_fastpath+0x1f/0xbe
      ...
      
      It turns out that we could record btrfs_log_ctx:io_err in
      log_one_extents when IO fails, but make log_one_extents() return '0'
      instead of -EIO, so the IO error is not acknowledged by the callers,
      i.e.  btrfs_log_inode_parent(), which would remove btrfs_log_ctx:list
      from list head 'root->log_ctxs'.  Since btrfs_log_ctx is allocated
      from stack memory, it'd get freed with a object alive on the
      list. then a future list_add will throw the above warning.
      
      This returns the correct error in the above case.
      
      Jeff also reported this while testing against his fsync error
      patch set[1].
      
      [1]: https://www.spinics.net/lists/linux-btrfs/msg65308.html
      "btrfs list corruption and soft lockups while testing writeback error handling"
      
      Fixes: 8407f553 ("Btrfs: fix data corruption after fast fsync and writeback error")
      Signed-off-by: default avatarLiu Bo <bo.li.liu@oracle.com>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      ebb70442
    • Qu Wenruo's avatar
      btrfs: Fix wild memory access in compression level parser · eae8d825
      Qu Wenruo authored
      [BUG]
      Kernel panic when mounting with "-o compress" mount option.
      KASAN will report like:
      ------
      ==================================================================
      BUG: KASAN: wild-memory-access in strncmp+0x31/0xc0
      Read of size 1 at addr d86735fce994f800 by task mount/662
      ...
      Call Trace:
       dump_stack+0xe3/0x175
       kasan_report+0x163/0x370
       __asan_load1+0x47/0x50
       strncmp+0x31/0xc0
       btrfs_compress_str2level+0x20/0x70 [btrfs]
       btrfs_parse_options+0xff4/0x1870 [btrfs]
       open_ctree+0x2679/0x49f0 [btrfs]
       btrfs_mount+0x1b7f/0x1d30 [btrfs]
       mount_fs+0x49/0x190
       vfs_kern_mount.part.29+0xba/0x280
       vfs_kern_mount+0x13/0x20
       btrfs_mount+0x31e/0x1d30 [btrfs]
       mount_fs+0x49/0x190
       vfs_kern_mount.part.29+0xba/0x280
       do_mount+0xaad/0x1a00
       SyS_mount+0x98/0xe0
       entry_SYSCALL_64_fastpath+0x1f/0xbe
      ------
      
      [Cause]
      For 'compress' and 'compress_force' options, its token doesn't expect
      any parameter so its args[0] contains uninitialized data.
      Accessing args[0] will cause above wild memory access.
      
      [Fix]
      For Opt_compress and Opt_compress_force, set compression level to
      the default.
      Signed-off-by: default avatarQu Wenruo <wqu@suse.com>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      [ set the default in advance ]
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      eae8d825
    • Josef Bacik's avatar
      btrfs: fix deadlock when writing out space cache · b77000ed
      Josef Bacik authored
      If we fail to prepare our pages for whatever reason (out of memory in
      our case) we need to make sure to drop the block_group->data_rwsem,
      otherwise hilarity ensues.
      Signed-off-by: default avatarJosef Bacik <jbacik@fb.com>
      Reviewed-by: default avatarOmar Sandoval <osandov@fb.com>
      Reviewed-by: default avatarLiu Bo <bo.li.liu@oracle.com>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      [ add label and use existing unlocking code ]
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      b77000ed
  6. 20 Nov, 2017 1 commit
    • Josef Bacik's avatar
      btrfs: clear space cache inode generation always · 8e138e0d
      Josef Bacik authored
      We discovered a box that had double allocations, and suspected the space
      cache may be to blame.  While auditing the write out path I noticed that
      if we've already setup the space cache we will just carry on.  This
      means that any error we hit after cache_save_setup before we go to
      actually write the cache out we won't reset the inode generation, so
      whatever was already written will be considered correct, except it'll be
      stale.  Fix this by _always_ resetting the generation on the block group
      inode, this way we only ever have valid or invalid cache.
      
      With this patch I was no longer able to reproduce cache corruption with
      dm-log-writes and my bpf error injection tool.
      
      Cc: stable@vger.kernel.org
      Signed-off-by: default avatarJosef Bacik <jbacik@fb.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      8e138e0d
  7. 15 Nov, 2017 7 commits
    • Filipe Manana's avatar
      Btrfs: fix reported number of inode blocks after buffered append writes · e3b8a485
      Filipe Manana authored
      The patch from commit a7e3b975 ("Btrfs: fix reported number of inode
      blocks") introduced a regression where if we do a buffered write starting
      at position equal to or greater than the file's size and then stat(2) the
      file before writeback is triggered, the number of used blocks does not
      change (unless there's a prealloc/unwritten extent). Example:
      
        $ xfs_io -f -c "pwrite -S 0xab 0 64K" foobar
        $ du -h foobar
        0	foobar
        $ sync
        $ du -h foobar
        64K	foobar
      
      The first version of that patch didn't had this regression and the second
      version, which was the one committed, was made only to address some
      performance regression detected by the intel test robots using fs_mark.
      
      This fixes the regression by setting the new delaloc bit in the range, and
      doing it at btrfs_dirty_pages() while setting the regular dealloc bit as
      well, so that this way we set both bits at once avoiding navigation of the
      inode's io tree twice. Doing it at btrfs_dirty_pages() is also the most
      meaninful place, as we should set the new dellaloc bit when if we set the
      delalloc bit, which happens only if we copied bytes into the pages at
      __btrfs_buffered_write().
      
      This was making some of LTP's du tests fail, which can be quickly run
      using a command line like the following:
      
        $ ./runltp -q -p -l /ltp.log -f commands -s du -d /mnt
      
      Fixes: a7e3b975 ("Btrfs: fix reported number of inode blocks")
      Signed-off-by: default avatarFilipe Manana <fdmanana@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      e3b8a485
    • Filipe Manana's avatar
      Btrfs: move definition of the function btrfs_find_new_delalloc_bytes · f48bf66b
      Filipe Manana authored
      Move the definition of the function btrfs_find_new_delalloc_bytes() closer
      to the function btrfs_dirty_pages(), because in a future commit it will be
      used exclusively by btrfs_dirty_pages(). This just moves the function's
      definition, with no functional changes at all.
      Signed-off-by: default avatarFilipe Manana <fdmanana@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      f48bf66b
    • Liu Bo's avatar
      Btrfs: bail out gracefully rather than BUG_ON · 56a0e706
      Liu Bo authored
      If a file's DIR_ITEM key is invalid (due to memory errors) and gets
      written to disk, a future lookup_path can end up with kernel panic due
      to BUG_ON().
      
      This gets rid of the BUG_ON(), meanwhile output the corrupted key and
      return ENOENT if it's invalid.
      Signed-off-by: default avatarLiu Bo <bo.li.liu@oracle.com>
      Reported-by: default avatarGuillaume Bouchard <bouchard@mercs-eng.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      56a0e706
    • David Sterba's avatar
      btrfs: dev_alloc_list is not protected by RCU, use normal list_del · 619c47f3
      David Sterba authored
      The dev_alloc_list list could be protected by various mutexes,
      depending on the context. The list tracks devices that can take part of
      allocating new chunks, so the closest mutex is chunk_mutex. Adding a new
      device from inside the ADD_DEV ioctl will need device_list_mutex and
      registering a new device from the ioctl needs uuid_mutex.
      
      All mutexes naturally guarantee exclusivity against the same context.
      The device ownership can move between the contexts and the exclusivity
      is guaranteed by other means, eg. during the mount with the uuid_mutex.
      
      There's no RCU involved for dev_alloc_list.
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      619c47f3
    • David Sterba's avatar
      btrfs: add missing device::flush_bio puts · 3065ae5b
      David Sterba authored
      This fixes potential bio leaks, in several error paths. Unfortunatelly
      the device structure freeing is opencoded in many places and I missed
      them when introducing the flush_bio.
      
      Most of the time, devices get freed through call_rcu(..., free_device),
      so it at least it's not that easy to hit the leak, but it's still
      possible through the path that frees stale devices.
      
      Fixes: e0ae9994 ("btrfs: preallocate device flush bio")
      Reviewed-by: default avatarNikolay Borisov <nborisov@suse.com>
      Reviewed-by: default avatarAnand Jain <anand.jain@oracle.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      3065ae5b
    • Nikolay Borisov's avatar
      btrfs: Fix transaction abort during failure in btrfs_rm_dev_item · 5e9f2ad5
      Nikolay Borisov authored
      btrfs_rm_dev_item calls several function under an active transaction,
      however it fails to abort it if an error happens. Fix this by adding
      explicit btrfs_abort_transaction/btrfs_end_transaction calls.
      Signed-off-by: default avatarNikolay Borisov <nborisov@suse.com>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      5e9f2ad5
    • Liu Bo's avatar
      Btrfs: add write_flags for compression bio · f82b7359
      Liu Bo authored
      Compression code path has only flaged bios with REQ_OP_WRITE no matter
      where the bios come from, but it could be a sync write if fsync starts
      this writeback or a normal writeback write if wb kthread starts a
      periodic writeback.
      
      It breaks the rule that sync writes and writeback writes need to be
      differentiated from each other, because from the POV of block layer,
      all bios need to be recognized by these flags in order to do some
      management, e.g. throttlling.
      
      This passes writeback_control to compression write path so that it can
      send bios with proper flags to block layer.
      Signed-off-by: default avatarLiu Bo <bo.li.liu@oracle.com>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      f82b7359
  8. 01 Nov, 2017 19 commits
    • Gu JinXiang's avatar
      btrfs: Fix bug for misused dev_t when lookup in dev state hash table. · d28e649a
      Gu JinXiang authored
      Fix bug of commit 74d46992 ("block: replace bi_bdev with a gendisk
      pointer and partitions index").
      
      bio_dev(bio) is used to find the dev state in function
      __btrfsic_submit_bio. But when dev_state is added to the hashtable, it
      is using dev_t of block_device.
      
      bio_dev(bio) returns a dev_t of part0 which is different from dev_t in
      block_device(bd_dev). bd_dev in block_device represents the exact
      partition.
      
      block_device.bd_dev =
      	bio->bi_partno (same as block_device.bd_partno) + bio_dev(bio).
      
      When adding a dev_state into hashtable, we use the exact partition dev_t.
      So when looking it up, it should also use the exact partition dev_t.
      
      Reproducer of this bug:
      
      Use MOUNT_OPTIONS="-o check_int" and run btrfs/001 in fstests.
      Then there will be WARNING like below.
      
      WARNING:
      btrfs: attempt to write superblock which references block M @29523968 (sda7     /1111654400/2) which is never written!
      Signed-off-by: default avatarGu JinXiang <gujx@cn.fujitsu.com>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      d28e649a
    • Timofey Titovets's avatar
      Btrfs: heuristic: add Shannon entropy calculation · 19562430
      Timofey Titovets authored
      Byte distribution check in heuristic will filter edge data cases and
      some time fail to classify input data.
      
      Let's fix that by adding Shannon entropy calculation, that will cover
      classification of most other data types.
      
      As Shannon entropy needs log2 with some precision to work, let's use
      ilog2(N) and for increased precision, by do ilog2(pow(N, 4)).
      
      Shannon entropy has been slightly changed to avoid signed numbers and
      division.
      
      The calculation is direct by the formula, successor of precalculated
      table or chains of if-else.
      
      The accuracy errors of ilog2 are compensated by
      
      @ENTROPY_LVL_ACEPTABLE 70 -> 65
      @ENTROPY_LVL_HIGH      85 -> 80
      Signed-off-by: default avatarTimofey Titovets <nefelim4ag@gmail.com>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      [ update comments ]
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      19562430
    • Timofey Titovets's avatar
      Btrfs: heuristic: add byte core set calculation · 858177d3
      Timofey Titovets authored
      Calculate byte core set for data sample:
      - sort buckets' numbers in decreasing order
      - count how many values cover 90% of the sample
      
      If the core set size is low (<=25%), data are easily compressible.
      If the core set size is high (>=80%), data are not compressible.
      Signed-off-by: default avatarTimofey Titovets <nefelim4ag@gmail.com>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      [ update comments ]
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      858177d3
    • Timofey Titovets's avatar
      Btrfs: heuristic: add byte set calculation · a288e92c
      Timofey Titovets authored
      Calculate byte set size for data sample:
      - calculate how many unique bytes have been in the sample
      - for all bytes count > 0, check if we're still in the low count range
        (~25%), such data are easily compressible, otherwise furhter analysis
        is needed
      Signed-off-by: default avatarTimofey Titovets <nefelim4ag@gmail.com>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      [ update comments ]
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      a288e92c
    • Timofey Titovets's avatar
      Btrfs: heuristic: add detection of repeated data patterns · 1fe4f6fa
      Timofey Titovets authored
      Walk over data sample and use memcmp to detect repeated patterns, like
      zeros, but a bit more general.
      Signed-off-by: default avatarTimofey Titovets <nefelim4ag@gmail.com>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      [ minor coding style fixes ]
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      1fe4f6fa
    • Timofey Titovets's avatar
      Btrfs: heuristic: implement sampling logic · a440d48c
      Timofey Titovets authored
      Copy sample data from the input data range to sample buffer then
      calculate byte value count for that sample into bucket.
      Signed-off-by: default avatarTimofey Titovets <nefelim4ag@gmail.com>
      [ minor comment updates ]
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      a440d48c
    • Timofey Titovets's avatar
      Btrfs: heuristic: add bucket and sample counters and other defines · 17b5a6c1
      Timofey Titovets authored
      Add basic defines and structures for data sampling.
      
      Added macros:
       - For future sampling algo
       - For bucket size
      
      Heuristic workspace:
       - Add bucket for storing byte type counters
       - Add sample array for storing partial copy of input data range
       - Add counter for store current sample size to workspace
      Signed-off-by: default avatarTimofey Titovets <nefelim4ag@gmail.com>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      [ minor coding style fixes, comments updated ]
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      17b5a6c1
    • Timofey Titovets's avatar
      Btrfs: compression: separate heuristic/compression workspaces · 4e439a0b
      Timofey Titovets authored
      Compression heuristic itself is not a compression type, as current
      infrastructure provides workspaces for several compression types, it's
      difficult to just add heuristic workspace.
      
      Just refactor the code to support compression/heuristic workspaces with
      maximum code sharing and minimum changes in it.
      Signed-off-by: default avatarTimofey Titovets <nefelim4ag@gmail.com>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      [ coding style fixes ]
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      4e439a0b
    • Josef Bacik's avatar
      btrfs: move btrfs_truncate_block out of trans handle · ddfae63c
      Josef Bacik authored
      Since we do a delalloc reserve in btrfs_truncate_block we can deadlock
      with freeze.  If somebody else is trying to allocate metadata for this
      inode and it gets stuck in start_delalloc_inodes because of freeze we
      will deadlock.  Be safe and move this outside of a trans handle.  This
      also has a side-effect of making sure that we're not leaving stale data
      behind in the other_encoding or encryption case.  Not an issue now since
      nobody uses it, but it would be a problem in the future.
      Signed-off-by: default avatarJosef Bacik <jbacik@fb.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      ddfae63c
    • Josef Bacik's avatar
      btrfs: don't call btrfs_start_delalloc_roots in flushoncommit · ce8ea7cc
      Josef Bacik authored
      We're holding the sb_start_intwrite lock at this point, and doing async
      filemap_flush of the inodes will result in a deadlock if we freeze the
      fs during this operation.  This is because we could do a
      btrfs_join_transaction() in the thread we are waiting on which would
      block at sb_start_intwrite, and thus deadlock.  Using
      writeback_inodes_sb() side steps the problem by not introducing all of
      these extra locking dependencies.
      Signed-off-by: default avatarJosef Bacik <jbacik@fb.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      ce8ea7cc
    • Josef Bacik's avatar
      btrfs: track refs in a rb_tree instead of a list · 0e0adbcf
      Josef Bacik authored
      If we get a significant amount of delayed refs for a single block (think
      modifying multiple snapshots) we can end up spending an ungodly amount
      of time looping through all of the entries trying to see if they can be
      merged.  This is because we only add them to a list, so we have O(2n)
      for every ref head.  This doesn't make any sense as we likely have refs
      for different roots, and so they cannot be merged.  Tracking in a tree
      will allow us to break as soon as we hit an entry that doesn't match,
      making our worst case O(n).
      
      With this we can also merge entries more easily.  Before we had to hope
      that matching refs were on the ends of our list, but with the tree we
      can search down to exact matches and merge them at insert time.
      Signed-off-by: default avatarJosef Bacik <jbacik@fb.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      0e0adbcf
    • Josef Bacik's avatar
      btrfs: add a comp_refs() helper · 1d148e59
      Josef Bacik authored
      Instead of open-coding the delayed ref comparisons, add a helper to do
      the comparisons generically and use that everywhere.  We compare
      sequence numbers last for following patches.
      Signed-off-by: default avatarJosef Bacik <jbacik@fb.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      1d148e59
    • Josef Bacik's avatar
      btrfs: switch args for comp_*_refs · c7ad7c84
      Josef Bacik authored
      Make it more consistent, we want the inserted ref to be compared against
      what's already in there.  This will make the order go from lowest seq ->
      highest seq, which will make us more likely to make forward progress if
      there's a seqlock currently held.
      Signed-off-by: default avatarJosef Bacik <jbacik@fb.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      c7ad7c84
    • Josef Bacik's avatar
      btrfs: make the delalloc block rsv per inode · 69fe2d75
      Josef Bacik authored
      The way we handle delalloc metadata reservations has gotten
      progressively more complicated over the years.  There is so much cruft
      and weirdness around keeping the reserved count and outstanding counters
      consistent and handling the error cases that it's impossible to
      understand.
      
      Fix this by making the delalloc block rsv per-inode.  This way we can
      calculate the actual size of the outstanding metadata reservations every
      time we make a change, and then reserve the delta based on that amount.
      This greatly simplifies the code everywhere, and makes the error
      handling in btrfs_delalloc_reserve_metadata far less terrifying.
      Signed-off-by: default avatarJosef Bacik <jbacik@fb.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      69fe2d75
    • Josef Bacik's avatar
      btrfs: add tracepoints for outstanding extents mods · dd48d407
      Josef Bacik authored
      This is handy for tracing problems with modifying the outstanding
      extents counters.
      Signed-off-by: default avatarJosef Bacik <jbacik@fb.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      dd48d407
    • Josef Bacik's avatar
      Btrfs: rework outstanding_extents · 8b62f87b
      Josef Bacik authored
      Right now we do a lot of weird hoops around outstanding_extents in order
      to keep the extent count consistent.  This is because we logically
      transfer the outstanding_extent count from the initial reservation
      through the set_delalloc_bits.  This makes it pretty difficult to get a
      handle on how and when we need to mess with outstanding_extents.
      
      Fix this by revamping the rules of how we deal with outstanding_extents.
      Now instead everybody that is holding on to a delalloc extent is
      required to increase the outstanding extents count for itself.  This
      means we'll have something like this
      
      btrfs_delalloc_reserve_metadata	- outstanding_extents = 1
       btrfs_set_extent_delalloc	- outstanding_extents = 2
      btrfs_release_delalloc_extents	- outstanding_extents = 1
      
      for an initial file write.  Now take the append write where we extend an
      existing delalloc range but still under the maximum extent size
      
      btrfs_delalloc_reserve_metadata - outstanding_extents = 2
        btrfs_set_extent_delalloc
          btrfs_set_bit_hook		- outstanding_extents = 3
          btrfs_merge_extent_hook	- outstanding_extents = 2
      btrfs_delalloc_release_extents	- outstanding_extnets = 1
      
      In order to make the ordered extent transition we of course must now
      make ordered extents carry their own outstanding_extent reservation, so
      for cow_file_range we end up with
      
      btrfs_add_ordered_extent	- outstanding_extents = 2
      clear_extent_bit		- outstanding_extents = 1
      btrfs_remove_ordered_extent	- outstanding_extents = 0
      
      This makes all manipulations of outstanding_extents much more explicit.
      Every successful call to btrfs_delalloc_reserve_metadata _must_ now be
      combined with btrfs_release_delalloc_extents, even in the error case, as
      that is the only function that actually modifies the
      outstanding_extents counter.
      
      The drawback to this is now we are much more likely to have transient
      cases where outstanding_extents is much larger than it actually should
      be.  This could happen before as we manipulated the delalloc bits, but
      now it happens basically at every write.  This may put more pressure on
      the ENOSPC flushing code, but I think making this code simpler is worth
      the cost.  I have another change coming to mitigate this side-effect
      somewhat.
      
      I also added trace points for the counter manipulation.  These were used
      by a bpf script I wrote to help track down leak issues.
      Signed-off-by: default avatarJosef Bacik <jbacik@fb.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      8b62f87b
    • Zygo Blaxell's avatar
      btrfs: increase output size for LOGICAL_INO_V2 ioctl · b115e3bc
      Zygo Blaxell authored
      Build-server workloads have hundreds of references per file after dedup.
      Multiply by a few snapshots and we quickly exhaust the limit of 2730
      references per extent that can fit into a 64K buffer.
      
      Raise the limit to 16M to be consistent with other btrfs ioctls
      (e.g. TREE_SEARCH_V2, FILE_EXTENT_SAME).
      
      To minimize surprising userspace behavior, apply this change only to
      the LOGICAL_INO_V2 ioctl.
      Signed-off-by: default avatarZygo Blaxell <ce3g8jdj@umail.furryterror.org>
      Reviewed-by: default avatarHans van Kranenburg <hans.van.kranenburg@mendix.com>
      Tested-by: default avatarHans van Kranenburg <hans.van.kranenburg@mendix.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      b115e3bc
    • Zygo Blaxell's avatar
      btrfs: add a flags argument to LOGICAL_INO and call it LOGICAL_INO_V2 · d24a67b2
      Zygo Blaxell authored
      Now that check_extent_in_eb()'s extent offset filter can be turned off,
      we need a way to do it from userspace.
      
      Add a 'flags' field to the btrfs_logical_ino_args structure to disable
      extent offset filtering, taking the place of one of the existing
      reserved[] fields.
      
      Previous versions of LOGICAL_INO neglected to check whether any of the
      reserved fields have non-zero values.  Assigning meaning to those fields
      now may change the behavior of existing programs that left these fields
      uninitialized.  The lack of a zero check also means that new programs
      have no way to know whether the kernel is honoring the flags field.
      
      To avoid these problems, define a new ioctl LOGICAL_INO_V2.  We can
      use the same argument layout as LOGICAL_INO, but shorten the reserved[]
      array by one element and turn it into the 'flags' field.  The V2 ioctl
      explicitly checks that reserved fields and unsupported flag bits are zero
      so that userspace can negotiate future feature bits as they are defined.
      
      Since the memory layouts of the two ioctls' arguments are compatible,
      there is no need for a separate function for logical_to_ino_v2 (contrast
      with tree_search_v2 vs tree_search where the layout and code are quite
      different).  A version parameter and an 'if' statement will suffice.
      
      Now that we have a flags field in logical_ino_args, add a flag
      BTRFS_LOGICAL_INO_ARGS_IGNORE_OFFSET to get the behavior we want,
      and pass it down the stack to iterate_inodes_from_logical.
      
      Motivation and background, copied from the patchset cover letter:
      
      Suppose we have a file with one extent:
      
          root@tester:~# zcat /usr/share/doc/cpio/changelog.gz > /test/a
          root@tester:~# sync
      
      Split the extent by overwriting it in the middle:
      
          root@tester:~# cat /dev/urandom | dd bs=4k seek=2 skip=2 count=1 conv=notrunc of=/test/a
      
      We should now have 3 extent refs to 2 extents, with one block unreachable.
      The extent tree looks like:
      
          root@tester:~# btrfs-debug-tree /dev/vdc -t 2
          [...]
                  item 9 key (1103101952 EXTENT_ITEM 73728) itemoff 15942 itemsize 53
                          extent refs 2 gen 29 flags DATA
                          extent data backref root 5 objectid 261 offset 0 count 2
          [...]
                  item 11 key (1103175680 EXTENT_ITEM 4096) itemoff 15865 itemsize 53
                          extent refs 1 gen 30 flags DATA
                          extent data backref root 5 objectid 261 offset 8192 count 1
          [...]
      
      and the ref tree looks like:
      
          root@tester:~# btrfs-debug-tree /dev/vdc -t 5
          [...]
                  item 6 key (261 EXTENT_DATA 0) itemoff 15825 itemsize 53
                          extent data disk byte 1103101952 nr 73728
                          extent data offset 0 nr 8192 ram 73728
                          extent compression(none)
                  item 7 key (261 EXTENT_DATA 8192) itemoff 15772 itemsize 53
                          extent data disk byte 1103175680 nr 4096
                          extent data offset 0 nr 4096 ram 4096
                          extent compression(none)
                  item 8 key (261 EXTENT_DATA 12288) itemoff 15719 itemsize 53
                          extent data disk byte 1103101952 nr 73728
                          extent data offset 12288 nr 61440 ram 73728
                          extent compression(none)
          [...]
      
      There are two references to the same extent with different, non-overlapping
      byte offsets:
      
          [------------------72K extent at 1103101952----------------------]
          [--8K----------------|--4K unreachable----|--60K-----------------]
          ^                                         ^
          |                                         |
          [--8K ref offset 0--][--4K ref offset 0--][--60K ref offset 12K--]
                               |
                               v
                               [-----4K extent-----] at 1103175680
      
      We want to find all of the references to extent bytenr 1103101952.
      
      Without the patch (and without running btrfs-debug-tree), we have to
      do it with 18 LOGICAL_INO calls:
      
          root@tester:~# btrfs ins log 1103101952 -P /test/
          Using LOGICAL_INO
          inode 261 offset 0 root 5
      
          root@tester:~# for x in $(seq 0 17); do btrfs ins log $((1103101952 + x * 4096)) -P /test/; done 2>&1 | grep inode
          inode 261 offset 0 root 5
          inode 261 offset 4096 root 5   <- same extent ref as offset 0
                                         (offset 8192 returns empty set, not reachable)
          inode 261 offset 12288 root 5
          inode 261 offset 16384 root 5  \
          inode 261 offset 20480 root 5  |
          inode 261 offset 24576 root 5  |
          inode 261 offset 28672 root 5  |
          inode 261 offset 32768 root 5  |
          inode 261 offset 36864 root 5  \
          inode 261 offset 40960 root 5   > all the same extent ref as offset 12288.
          inode 261 offset 45056 root 5  /  More processing required in userspace
          inode 261 offset 49152 root 5  |  to figure out these are all duplicates.
          inode 261 offset 53248 root 5  |
          inode 261 offset 57344 root 5  |
          inode 261 offset 61440 root 5  |
          inode 261 offset 65536 root 5  |
          inode 261 offset 69632 root 5  /
      
      In the worst case the extents are 128MB long, and we have to do 32768
      iterations of the loop to find one 4K extent ref.
      
      With the patch, we just use one call to map all refs to the extent at once:
          root@tester:~# btrfs ins log 1103101952 -P /test/
          Using LOGICAL_INO_V2
          inode 261 offset 0 root 5
          inode 261 offset 12288 root 5
      
      The TREE_SEARCH ioctl allows userspace to retrieve the offset and
      extent bytenr fields easily once the root, inode and offset are known.
      This is sufficient information to build a complete map of the extent
      and all of its references.  Userspace can use this information to make
      better choices to dedup or defrag.
      Signed-off-by: default avatarZygo Blaxell <ce3g8jdj@umail.furryterror.org>
      Reviewed-by: default avatarHans van Kranenburg <hans.van.kranenburg@mendix.com>
      Tested-by: default avatarHans van Kranenburg <hans.van.kranenburg@mendix.com>
      [ copy background and motivation from cover letter ]
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      d24a67b2
    • Zygo Blaxell's avatar
      btrfs: add a flag to iterate_inodes_from_logical to find all extent refs for uncompressed extents · c995ab3c
      Zygo Blaxell authored
      The LOGICAL_INO ioctl provides a backward mapping from extent bytenr and
      offset (encoded as a single logical address) to a list of extent refs.
      LOGICAL_INO complements TREE_SEARCH, which provides the forward mapping
      (extent ref -> extent bytenr and offset, or logical address).  These are
      useful capabilities for programs that manipulate extents and extent
      references from userspace (e.g. dedup and defrag utilities).
      
      When the extents are uncompressed (and not encrypted and not other),
      check_extent_in_eb performs filtering of the extent refs to remove any
      extent refs which do not contain the same extent offset as the 'logical'
      parameter's extent offset.  This prevents LOGICAL_INO from returning
      references to more than a single block.
      
      To find the set of extent references to an uncompressed extent from [a, b),
      userspace has to run a loop like this pseudocode:
      
      	for (i = a; i < b; ++i)
      		extent_ref_set += LOGICAL_INO(i);
      
      At each iteration of the loop (up to 32768 iterations for a 128M extent),
      data we are interested in is collected in the kernel, then deleted by
      the filter in check_extent_in_eb.
      
      When the extents are compressed (or encrypted or other), the 'logical'
      parameter must be an extent bytenr (the 'a' parameter in the loop).
      No filtering by extent offset is done (or possible?) so the result is
      the complete set of extent refs for the entire extent.  This removes
      the need for the loop, since we get all the extent refs in one call.
      
      Add an 'ignore_offset' argument to iterate_inodes_from_logical,
      [...several levels of function call graph...], and check_extent_in_eb, so
      that we can disable the extent offset filtering for uncompressed extents.
      This flag can be set by an improved version of the LOGICAL_INO ioctl to
      get either behavior as desired.
      
      There is no functional change in this patch.  The new flag is always
      false.
      Signed-off-by: default avatarZygo Blaxell <ce3g8jdj@umail.furryterror.org>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      [ minor coding style fixes ]
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      c995ab3c