Skip to content
  • Miao Xie's avatar
    btrfs: implement delayed inode items operation · 16cdcec7
    Miao Xie authored
    Changelog V5 -> V6:
    - Fix oom when the memory load is high, by storing the delayed nodes into the
      root's radix tree, and letting btrfs inodes go.
    
    Changelog V4 -> V5:
    - Fix the race on adding the delayed node to the inode, which is spotted by
      Chris Mason.
    - Merge Chris Mason's incremental patch into this patch.
    - Fix deadlock between readdir() and memory fault, which is reported by
      Itaru Kitayama.
    
    Changelog V3 -> V4:
    - Fix nested lock, which is reported by Itaru Kitayama, by updating space cache
      inode in time.
    
    Changelog V2 -> V3:
    - Fix the race between the delayed worker and the task which does delayed items
      balance, which is reported by Tsutomu Itoh.
    - Modify the patch address David Sterba's comment.
    - Fix the bug of the cpu recursion spinlock, reported by Chris Mason
    
    Changelog V1 -> V2:
    - break up the global rb-tree, use a list to manage the delayed nodes,
      which is created for every directory and file, and used to manage the
      delayed directory name index items and the delayed inode item.
    - introduce a worker to deal with the delayed nodes.
    
    Compare with Ext3/4, the performance of file creation and deletion on btrfs
    is very poor. the reason is that btrfs must do a lot of b+ tree insertions,
    such as inode item, directory name item, directory name index and so on.
    
    If we can do some delayed b+ tree insertion or deletion, we can improve the
    performance, so we made this patch which implemented delayed directory name
    index insertion/deletion and delayed inode update.
    
    Implementation:
    - introduce a delayed root object into the filesystem, that use two lists to
      manage the delayed nodes which are created for every file/directory.
      One is used to manage all the delayed nodes that have delayed items. And the
      other is used to manage the delayed nodes which is waiting to be dealt with
      by the work thread.
    - Every delayed node has two rb-tree, one is used to manage the directory name
      index which is going to be inserted into b+ tree, and the other is used to
      manage the directory name index which is going to be deleted from b+ tree.
    - introduce a worker to deal with the delayed operation. This worker is used
      to deal with the works of the delayed directory name index items insertion
      and deletion and the delayed inode update.
      When the delayed items is beyond the lower limit, we create works for some
      delayed nodes and insert them into the work queue of the worker, and then
      go back.
      When the delayed items is beyond the upper bound, we create works for all
      the delayed nodes that haven't been dealt with, and insert them into the work
      queue of the worker, and then wait for that the untreated items is below some
      threshold value.
    - When we want to insert a directory name index into b+ tree, we just add the
      information into the delayed inserting rb-tree.
      And then we check the number of the delayed items and do delayed items
      balance. (The balance policy is above.)
    - When we want to delete a directory name index from the b+ tree, we search it
      in the inserting rb-tree at first. If we look it up, just drop it. If not,
      add the key of it into the delayed deleting rb-tree.
      Similar to the delayed inserting rb-tree, we also check the number of the
      delayed items and do delayed items balance.
      (The same to inserting manipulation)
    - When we want to update the metadata of some inode, we cached the data of the
      inode into the delayed node. the worker will flush it into the b+ tree after
      dealing with the delayed insertion and deletion.
    - We will move the delayed node to the tail of the list after we access the
      delayed node, By this way, we can cache more delayed items and merge more
      inode updates.
    - If we want to commit transaction, we will deal with all the delayed node.
    - the delayed node will be freed when we free the btrfs inode.
    - Before we log the inode items, we commit all the directory name index items
      and the delayed inode update.
    
    I did a quick test by the benchmark tool[1] and found we can improve the
    performance of file creation by ~15%, and file deletion by ~20%.
    
    Before applying this patch:
    Create files:
            Total files: 50000
            Total time: 1.096108
            Average time: 0.000022
    Delete files:
            Total files: 50000
            Total time: 1.510403
            Average time: 0.000030
    
    After applying this patch:
    Create files:
            Total files: 50000
            Total time: 0.932899
            Average time: 0.000019
    Delete files:
            Total files: 50000
            Total time: 1.215732
            Average time: 0.000024
    
    [1] http://marc.info/?l=linux-btrfs&m=128212635122920&q=p3
    
    
    
    Many thanks for Kitayama-san's help!
    
    Signed-off-by: default avatarMiao Xie <miaox@cn.fujitsu.com>
    Reviewed-by: default avatarDavid Sterba <dave@jikos.cz>
    Tested-by: default avatarTsutomu Itoh <t-itoh@jp.fujitsu.com>
    Tested-by: default avatarItaru Kitayama <kitayama@cl.bb4u.ne.jp>
    Signed-off-by: default avatarChris Mason <chris.mason@oracle.com>
    16cdcec7