Re: [PATCH v4] zswap: replace RB tree with xarray

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



On Wed, Mar 6, 2024 at 6:17 PM Chengming Zhou
<zhouchengming@xxxxxxxxxxxxx> wrote:
>
> On 2024/3/7 05:12, Chris Li wrote:
> > Hi Chengming,
> >
> > On Mon, Mar 4, 2024 at 6:52 PM Chengming Zhou
> > <zhouchengming@xxxxxxxxxxxxx> wrote:
> >>
> >> Hi Chris,
> >>
> >> On 2024/3/5 05:32, Chris Li wrote:
> >>> Very deep RB tree requires rebalance at times. That
> >>> contributes to the zswap fault latencies. Xarray does not
> >>> need to perform tree rebalance. Replacing RB tree to xarray
> >>> can have some small performance gain.
> >>>
> >>> One small difference is that xarray insert might fail with
> >>> ENOMEM, while RB tree insert does not allocate additional
> >>> memory.
> >>>
> >>> The zswap_entry size will reduce a bit due to removing the
> >>> RB node, which has two pointers and a color field. Xarray
> >>> store the pointer in the xarray tree rather than the
> >>> zswap_entry. Every entry has one pointer from the xarray
> >>> tree. Overall, switching to xarray should save some memory,
> >>> if the swap entries are densely packed.
> >>>
> >>> Notice the zswap_rb_search and zswap_rb_insert always
> >>> followed by zswap_rb_erase. Use xa_erase directly. The entry
> >>> erase into zswap_xa_insert as well. That saves one tree
> >>> lookup as well.
> >>>
> >>> Remove zswap_invalidate_entry due to no need to call
> >>> zswap_rb_erase any more. Use zswap_free_entry instead.
> >>>
> >>> The "struct zswap_tree" has been replaced by "struct xarray".
> >>> The tree spin lock has transferred to the xarray lock.
> >>>
> >>> Run the kernel build testing 10 times for each version, averages:
> >>> (memory.max=2GB, zswap shrinker and writeback enabled, one 50GB swapfile.)
> >>>
> >>> mm-9a0181a3710eb                    xarray v4
> >>> user       3526.829                            3526.930
> >>> sys        532.754                             526.525
> >>> real       198.748                             198.850
> >>>
> >>> ---
> >>>
> >>>
> >>> Signed-off-by: Chris Li <chrisl@xxxxxxxxxx>
> >>> ---
> >>> Changes in v4:
> >>> - Remove zswap_xa_search_and_earse, use xa_erase directly.
> >>> - Move charge of objcg after zswap_xa_insert.
> >>> - Avoid erase old entry on insert fail error path.
> >>> - Remove not needed swap_zswap_tree change
> >>> - Link to v3: https://lore.kernel.org/r/20240302-zswap-xarray-v3-1-5900252f2302@xxxxxxxxxx
> >>>
> >>> Changes in v3:
> >>> - Use xa_cmpxchg instead of zswap_xa_search_and_delete in zswap_writeback_entry.
> >>> - Use xa_store in zswap_xa_insert directly. Reduce the scope of spinlock.
> >>> - Fix xa_store error handling for same page fill case.
> >>> - Link to v2: https://lore.kernel.org/r/20240229-zswap-xarray-v2-1-e50284dfcdb1@xxxxxxxxxx
> >>>
> >>> Changes in v2:
> >>> - Replace struct zswap_tree with struct xarray.
> >>> - Remove zswap_tree spinlock, use xarray lock instead.
> >>> - Fold zswap_rb_erase() into zswap_xa_search_and_delete() and zswap_xa_insert().
> >>> - Delete zswap_invalidate_entry(), use zswap_free_entry() instead.
> >>> - Link to v1: https://lore.kernel.org/r/20240117-zswap-xarray-v1-0-6daa86c08fae@xxxxxxxxxx
> >>> ---
> >>>  mm/zswap.c | 186 ++++++++++++++++++++++++-------------------------------------
> >>>  1 file changed, 72 insertions(+), 114 deletions(-)
> >>>
> >>> diff --git a/mm/zswap.c b/mm/zswap.c
> >>> index 011e068eb355..4f4a3f452b76 100644
> >>> --- a/mm/zswap.c
> >>> +++ b/mm/zswap.c
> >>> @@ -20,7 +20,6 @@
> >>>  #include <linux/spinlock.h>
> >>>  #include <linux/types.h>
> >>>  #include <linux/atomic.h>
> >>> -#include <linux/rbtree.h>
> >>>  #include <linux/swap.h>
> >>>  #include <linux/crypto.h>
> >>>  #include <linux/scatterlist.h>
> >>> @@ -71,6 +70,8 @@ static u64 zswap_reject_compress_poor;
> >>>  static u64 zswap_reject_alloc_fail;
> >>>  /* Store failed because the entry metadata could not be allocated (rare) */
> >>>  static u64 zswap_reject_kmemcache_fail;
> >>> +/* Store failed because xarray can't insert the entry*/
> >>> +static u64 zswap_reject_xarray_fail;
> >>>
> >>>  /* Shrinker work queue */
> >>>  static struct workqueue_struct *shrink_wq;
> >>> @@ -196,7 +197,6 @@ static struct {
> >>>   * This structure contains the metadata for tracking a single compressed
> >>>   * page within zswap.
> >>>   *
> >>> - * rbnode - links the entry into red-black tree for the appropriate swap type
> >>>   * swpentry - associated swap entry, the offset indexes into the red-black tree
> >>>   * length - the length in bytes of the compressed page data.  Needed during
> >>>   *          decompression. For a same value filled page length is 0, and both
> >>> @@ -208,7 +208,6 @@ static struct {
> >>>   * lru - handle to the pool's lru used to evict pages.
> >>>   */
> >>>  struct zswap_entry {
> >>> -     struct rb_node rbnode;
> >>>       swp_entry_t swpentry;
> >>>       unsigned int length;
> >>>       struct zswap_pool *pool;
> >>> @@ -220,12 +219,7 @@ struct zswap_entry {
> >>>       struct list_head lru;
> >>>  };
> >>>
> >>> -struct zswap_tree {
> >>> -     struct rb_root rbroot;
> >>> -     spinlock_t lock;
> >>> -};
> >>> -
> >>> -static struct zswap_tree *zswap_trees[MAX_SWAPFILES];
> >>> +static struct xarray *zswap_trees[MAX_SWAPFILES];
> >>>  static unsigned int nr_zswap_trees[MAX_SWAPFILES];
> >>>
> >>>  /* RCU-protected iteration */
> >>> @@ -253,7 +247,7 @@ static bool zswap_has_pool;
> >>>  * helpers and fwd declarations
> >>>  **********************************/
> >>>
> >>> -static inline struct zswap_tree *swap_zswap_tree(swp_entry_t swp)
> >>> +static inline struct xarray *swap_zswap_tree(swp_entry_t swp)
> >>>  {
> >>>       return &zswap_trees[swp_type(swp)][swp_offset(swp)
> >>>               >> SWAP_ADDRESS_SPACE_SHIFT];
> >>> @@ -805,60 +799,33 @@ void zswap_memcg_offline_cleanup(struct mem_cgroup *memcg)
> >>>  }
> >>>
> >>>  /*********************************
> >>> -* rbtree functions
> >>> +* xarray functions
> >>>  **********************************/
> >>> -static struct zswap_entry *zswap_rb_search(struct rb_root *root, pgoff_t offset)
> >>> -{
> >>> -     struct rb_node *node = root->rb_node;
> >>> -     struct zswap_entry *entry;
> >>> -     pgoff_t entry_offset;
> >>> -
> >>> -     while (node) {
> >>> -             entry = rb_entry(node, struct zswap_entry, rbnode);
> >>> -             entry_offset = swp_offset(entry->swpentry);
> >>> -             if (entry_offset > offset)
> >>> -                     node = node->rb_left;
> >>> -             else if (entry_offset < offset)
> >>> -                     node = node->rb_right;
> >>> -             else
> >>> -                     return entry;
> >>> -     }
> >>> -     return NULL;
> >>> -}
> >>>
> >>>  /*
> >>>   * In the case that a entry with the same offset is found, a pointer to
> >>> - * the existing entry is stored in dupentry and the function returns -EEXIST
> >>> + * the existing entry is stored in old and erased from the tree.
> >>> + * Function return error on insert.
> >>>   */
> >>> -static int zswap_rb_insert(struct rb_root *root, struct zswap_entry *entry,
> >>> -                     struct zswap_entry **dupentry)
> >>> +static int zswap_xa_insert(struct xarray *tree, struct zswap_entry *entry,
> >>> +                        struct zswap_entry **old)
> >>>  {
> >>> -     struct rb_node **link = &root->rb_node, *parent = NULL;
> >>> -     struct zswap_entry *myentry;
> >>> -     pgoff_t myentry_offset, entry_offset = swp_offset(entry->swpentry);
> >>> -
> >>> -     while (*link) {
> >>> -             parent = *link;
> >>> -             myentry = rb_entry(parent, struct zswap_entry, rbnode);
> >>> -             myentry_offset = swp_offset(myentry->swpentry);
> >>> -             if (myentry_offset > entry_offset)
> >>> -                     link = &(*link)->rb_left;
> >>> -             else if (myentry_offset < entry_offset)
> >>> -                     link = &(*link)->rb_right;
> >>> -             else {
> >>> -                     *dupentry = myentry;
> >>> -                     return -EEXIST;
> >>> -             }
> >>> -     }
> >>> -     rb_link_node(&entry->rbnode, parent, link);
> >>> -     rb_insert_color(&entry->rbnode, root);
> >>> -     return 0;
> >>> -}
> >>> +     int err;
> >>> +     struct zswap_entry *e;
> >>> +     pgoff_t offset = swp_offset(entry->swpentry);
> >>>
> >>> -static void zswap_rb_erase(struct rb_root *root, struct zswap_entry *entry)
> >>> -{
> >>> -     rb_erase(&entry->rbnode, root);
> >>> -     RB_CLEAR_NODE(&entry->rbnode);
> >>> +     e = xa_store(tree, offset, entry, GFP_KERNEL);
> >>> +     err = xa_err(e);
> >>> +
> >>> +     if (err) {
> >>> +             e = xa_erase(tree, offset);
> >>> +             if (err == -ENOMEM)
> >>> +                     zswap_reject_alloc_fail++;
> >>> +             else
> >>> +                     zswap_reject_xarray_fail++;
> >>> +     }
> >>> +     *old = e;
> >>> +     return err;
> >>>  }
> >>>
> >>>  /*********************************
> >>> @@ -872,7 +839,6 @@ static struct zswap_entry *zswap_entry_cache_alloc(gfp_t gfp, int nid)
> >>>       entry = kmem_cache_alloc_node(zswap_entry_cache, gfp, nid);
> >>>       if (!entry)
> >>>               return NULL;
> >>> -     RB_CLEAR_NODE(&entry->rbnode);
> >>>       return entry;
> >>>  }
> >>>
> >>> @@ -914,17 +880,6 @@ static void zswap_entry_free(struct zswap_entry *entry)
> >>>       zswap_update_total_size();
> >>>  }
> >>>
> >>> -/*
> >>> - * The caller hold the tree lock and search the entry from the tree,
> >>> - * so it must be on the tree, remove it from the tree and free it.
> >>> - */
> >>> -static void zswap_invalidate_entry(struct zswap_tree *tree,
> >>> -                                struct zswap_entry *entry)
> >>> -{
> >>> -     zswap_rb_erase(&tree->rbroot, entry);
> >>> -     zswap_entry_free(entry);
> >>> -}
> >>> -
> >>>  /*********************************
> >>>  * compressed storage functions
> >>>  **********************************/
> >>> @@ -1113,7 +1068,9 @@ static void zswap_decompress(struct zswap_entry *entry, struct page *page)
> >>>  static int zswap_writeback_entry(struct zswap_entry *entry,
> >>>                                swp_entry_t swpentry)
> >>>  {
> >>> -     struct zswap_tree *tree;
> >>> +     struct xarray *tree;
> >>> +     pgoff_t offset = swp_offset(swpentry);
> >>> +     struct zswap_entry *e;
> >>>       struct folio *folio;
> >>>       struct mempolicy *mpol;
> >>>       bool folio_was_allocated;
> >>> @@ -1150,19 +1107,14 @@ static int zswap_writeback_entry(struct zswap_entry *entry,
> >>>        * be dereferenced.
> >>>        */
> >>>       tree = swap_zswap_tree(swpentry);
> >>> -     spin_lock(&tree->lock);
> >>> -     if (zswap_rb_search(&tree->rbroot, swp_offset(swpentry)) != entry) {
> >>> -             spin_unlock(&tree->lock);
> >>> +     e = xa_cmpxchg(tree, offset, entry, NULL, GFP_KERNEL);
> >>> +     if (e != entry) {
> >>
> >> Maybe "if (xa_cmpxchg() != entry)" look better, so "e" variable can be removed,
> >> since we don't use it.
> >
> > I thought about that. The main reason "if (xa_cmpxchg(tree, offset,
> > entry, NULL, GFP_KERNEL) != entry)" is a long expression. Having
> > != entry at the end of the expression makes it harder to read. Have
> > the temporary variable IMHO help reading the comparison.
> >
> > Not sure I understand the motivation to save a temporary variable. The
> > compiler always generates temporary variables internally. Having one
> > here does not affect the compiling result at all. It is just there to
> > help reading. If you still think it has the reverse effect on reading
> > I can of course remove it. It generates the same code anyway.
> You are right, just a minor type suggestion, no much difference if you keep it.

Thanks for the understanding and flexibility. I agree this is more a
personal flavor kind of thing,
Doesn't have a big enough impact on readability which has to flip one
way or the other.

Chris





[Index of Archives]     [Linux ARM Kernel]     [Linux ARM]     [Linux Omap]     [Fedora ARM]     [IETF Annouce]     [Bugtraq]     [Linux OMAP]     [Linux MIPS]     [eCos]     [Asterisk Internet PBX]     [Linux API]

  Powered by Linux