• Chris Li's avatar
    zswap: replace RB tree with xarray · 796c2c23
    Chris Li authored
    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 often followed by
    zswap_rb_erase.  Use xa_erase and xa_store directly.  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 5 times for each version, averages:
    (memory.max=2GB, zswap shrinker and writeback enabled, one 50GB swapfile,
    24 HT core, 32 jobs)
    
               mm-unstable-4aaccadb5c04     xarray v9
    user       3548.902 			3534.375
    sys        522.232                      520.976
    real       202.796                      200.864
    
    [chrisl@kernel.org: restore original comment "erase" to "invalidate"]
      Link: https://lkml.kernel.org/r/20240326-zswap-xarray-v10-1-bf698417c968@kernel.org
    Link: https://lkml.kernel.org/r/20240326-zswap-xarray-v9-1-d2891a65dfc7@kernel.orgSigned-off-by: default avatarChris Li <chrisl@kernel.org>
    Acked-by: default avatarYosry Ahmed <yosryahmed@google.com>
    Acked-by: default avatarJohannes Weiner <hannes@cmpxchg.org>
    Reviewed-by: default avatarNhat Pham <nphamcs@gmail.com>
    Cc: Barry Song <v-songbaohua@oppo.com>
    Cc: Chengming Zhou <zhouchengming@bytedance.com>
    Cc: Matthew Wilcox (Oracle) <willy@infradead.org>
    Signed-off-by: default avatarAndrew Morton <akpm@linux-foundation.org>
    796c2c23
zswap.c 48.9 KB