1. 15 Feb, 2023 37 commits
  2. 13 Feb, 2023 3 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