mm, swap: use rbtree for swap_extent
Subsystems (2)
PATCH 1/1 mm, swap: use rbtree for swap_extent
From: Aaron Lu <[email protected]>
swap_extent is used to map swap page offset to backing device's block offset. For a continuous block range, one swap_extent is used and all these swap_extents are managed in a linked list.
These swap_extents are used by map_swap_entry() during swap's read and write path. To find out the backing device's block offset for a page offset, the swap_extent list will be traversed linearly, with curr_swap_extent being used as a cache to speed up the search.
This works well as long as swap_extents are not huge or when the number of processes that access swap device are few, but when the swap device has many extents and there are a number of processes accessing the swap device concurrently, it can be a problem. On one of our servers, the disk's remaining size is tight:
$df -h
Filesystem Size Used Avail Use% Mounted on
... .../dev/nvme0n1p1 1.8T 1.3T 504G 72% /home/t4
When creating a 80G swapfile there, there are as many as 84656 swap extents. The end result is, kernel spends abou 30% time in map_swap_entry() and swap throughput is only 70MB/s. As a comparison, when I used smaller sized swapfile, like 4G whose swap_extent dropped to 2000, swap throughput is back to 400-500MB/s and map_swap_entry() is about 3%.
One downside of using rbtree for swap_extent is, 'struct rbtree' takes 24 bytes while 'struct list_head' takes 16 bytes, that's 8 bytes more for each swap_extent. For a swapfile that has 80k swap_extents, that means 625KiB more memory consumed.
Test:
Since it's not possible to reboot that server, I can not test this patch diretly there. Instead, I tested it on another server with NVMe disk.
I created a 20G swapfile on an NVMe backed XFS fs. By default, the filesystem is quite clean and the created swapfile has only 2 extents. Testing vanilla and this patch shows no obvious performance difference when swapfile is not fragmented.
To see the patch's effects, I used some tweaks to manually fragment the swapfile by breaking the extent at 1M boundary. This made the swapfile have 20K extents.
nr_task=4
kernel swapout(KB/s) map_swap_entry(perf) swapin(KB/s) map_swap_entry(perf) vanilla 165191 90.77% 171798 90.21% patched 858993 +420% 2.16% 715827 +317% 0.77%
nr_task=8
kernel swapout(KB/s) map_swap_entry(perf) swapin(KB/s) map_swap_entry(perf) vanilla 306783 92.19% 318145 87.76% patched 954437 +211% 2.35% 1073741 +237% 1.57%
swapout: the throughput of swap out, in KB/s, higher is better 1st map_swap_entry: cpu cycles percent sampled by perf
swapin: the throughput of swap in, in KB/s, higher is better. 2nd map_swap_entry: cpu cycles percent sampled by perf
nr_task=1 doesn't show any difference, this is due to the curr_swap_extent can be effectively used to cache the correct swap extent for single task workload.
--- include/linux/swap.h | 5 +- mm/page_io.c | 2 +- mm/swapfile.c | 137 +++++++++++++++++++++++-------------------- 3 files changed, 78 insertions(+), 66 deletions(-)
include/linux/swap.h +2 -3
@@ -148,7 +148,7 @@ struct zone;* We always assume that blocks are of size PAGE_SIZE. */ struct swap_extent { -struct list_head list; +struct rb_node rb_node;pgoff_t start_page;pgoff_t nr_pages;sector_t start_block;
@@ -247,8 +247,7 @@ struct swap_info_struct {unsigned int cluster_next;/* likely index for next allocation */ unsigned int cluster_nr;/* countdown to next cluster search */ struct percpu_cluster __percpu *percpu_cluster;/* per cpu's swap location */ -struct swap_extent *curr_swap_extent; -struct swap_extent first_swap_extent; +struct rb_root swap_extent_root;/* root of the swap extent rbtree */ struct block_device *bdev;/* swap device or bdev of swap file */ struct file *swap_file;/* seldom referenced */ unsigned int old_block_size;/* seldom referenced */
mm/page_io.c +1 -1
@@ -164,7 +164,7 @@ int generic_swapfile_activate(struct swap_info_struct *sis, blocks_per_page =PAGE_SIZE >> blkbits;/* -* Map all the blocks into the extent list. This code doesn't try +* Map all the blocks into the extent tree. This code doesn't try * to be very smart. */ probe_block =0 ;
mm/swapfile.c +75 -62
227 lines not on this page · raw message
Signature · 1 line
2.19.1.3.ge56e4f7
Andrew Morton
maintainerQuoted 56 lines · On Thu, 23 May 2019 22:24:15 +0800 Aaron Lu <[email protected]> wrote:
From: Aaron Lu <[email protected]>
swap_extentis used to map swap page offset to backing device's block offset. For a continuous block range, oneswap_extentis used and all theseswap_extentsare managed in a linked list.These
swap_extentsare used bymap_swap_entry()during swap's read and write path. To find out the backing device's block offset for a page offset, theswap_extentlist will be traversed linearly, withcurr_swap_extentbeing used as a cache to speed up the search.This works well as long as
swap_extentsare not huge or when the number of processes that access swap device are few, but when the swap device has many extents and there are a number of processes accessing the swap device concurrently, it can be a problem. On one of our servers, the disk's remaining size is tight:
$df -h
Filesystem Size Used Avail Use% Mounted on
... .../dev/nvme0n1p11.8T 1.3T 504G 72%/home/t4When creating a 80G swapfile there, there are as many as 84656 swap extents. The end result is, kernel spends abou 30% time in
map_swap_entry()and swap throughput is only 70MB/s. As a comparison, when I used smaller sized swapfile, like 4G whoseswap_extentdropped to 2000, swap throughput is back to 400-500MB/s andmap_swap_entry()is about 3%.One downside of using rbtree for
swap_extentis, 'struct rbtree' takes 24 bytes while 'structlist_head' takes 16 bytes, that's 8 bytes more for eachswap_extent. For a swapfile that has 80kswap_extents, that means 625KiB more memory consumed.Test:
Since it's not possible to reboot that server, I can not test this patch diretly there. Instead, I tested it on another server with NVMe disk.
I created a 20G swapfile on an NVMe backed XFS fs. By default, the filesystem is quite clean and the created swapfile has only 2 extents. Testing vanilla and this patch shows no obvious performance difference when swapfile is not fragmented.
To see the patch's effects, I used some tweaks to manually fragment the swapfile by breaking the extent at 1M boundary. This made the swapfile have 20K extents.
nr_task=4
kernel swapout(KB/s) map_swap_entry(perf) swapin(KB/s) map_swap_entry(perf) vanilla 165191 90.77% 171798 90.21% patched 858993 +420% 2.16% 715827 +317% 0.77%nr_task=8
kernel swapout(KB/s) map_swap_entry(perf) swapin(KB/s) map_swap_entry(perf) vanilla 306783 92.19% 318145 87.76% patched 954437 +211% 2.35% 1073741 +237% 1.57%
Quoted 8 lines
swapout: the throughput of swap out, in KB/s, higher is better 1st
map_swap_entry: cpu cycles percent sampled by perf
swapin: the throughput of swap in, in KB/s, higher is better. 2ndmap_swap_entry: cpu cycles percent sampled by perfnr_task=1 doesn't show any difference, this is due to the
curr_swap_extentcan be effectively used to cache the correct swap extent for single task workload.
Seems sensible and the code looks straightforward. Hopefully Hugh will be able to cast a gimlet eye over it.
Quoted 11 lines
...
(quoted diff) +8
-0+static struct swap_extent * +offset_to_swap_extent(struct swap_info_struct *sis, unsigned long offset) +{ + struct swap_extent *se; + struct rb_node *rb; + + rb = sis->swap_extent_root.rb_node; + while (rb) {
Review
Quoted 10 lines
(quoted diff) +10
-0+ se = rb_entry(rb, struct swap_extent, rb_node); + if (offset < se->start_page) + rb = rb->rb_left; + else if (offset >= se->start_page + se->nr_pages) + rb = rb->rb_right; + else + return se; + } + /* It *must* be present */ + BUG_ON(1);
I'm surprised this doesn't generate a warning about the function failing to return a value. I guess the compiler figured out that BUG_ON(non-zero-constant) is equivalent to BUG(), which is noreturn.
Let's do this?
mm/swapfile.c renamed from mm/swapfile.c~mm-swap-use-rbtree-for-swap_extent-fix +1 -1
@@ -218,7 +218,7 @@ offset_to_swap_extent(struct swap_info_sreturn se; }/* It *must* be present */ -BUG_ON (1 ); +BUG (); }
On 2019/5/24 3:00, Andrew Morton wrote:
...
Quoted 15 lines · On Thu, 23 May 2019 22:24:15 +0800 Aaron Lu <[email protected]> wrote:
Quoted 14 lines
...
(quoted diff) +12
-0+static struct swap_extent * +offset_to_swap_extent(struct swap_info_struct *sis, unsigned long offset) +{ + struct swap_extent *se; + struct rb_node *rb; + + rb = sis->swap_extent_root.rb_node; + while (rb) { + se = rb_entry(rb, struct swap_extent, rb_node); + if (offset < se->start_page) + rb = rb->rb_left; + else if (offset >= se->start_page + se->nr_pages)
Quoted 8 lines
Review
Quoted 6 lines
(quoted diff) +6
-0+ rb = rb->rb_right; + else + return se; + } + /* It *must* be present */ + BUG_ON(1);I'm surprised this doesn't generate a warning about the function
Ah right, I'm also surprised after you mentioned. This BUG_ON(1) here is meant to serve the same purpose as the original code in map_swap_entry():
static sector_t map_swap_entry(swp_entry_t entry, struct block_device **bdev)
{
...
offset = swp_offset(entry);
start_se = sis->curr_swap_extent;
se = start_se;
for ( ; ; ) {
if (se->start_page <= offset &&
offset < (se->start_page + se->nr_pages)) {
return se->start_block + (offset - se->start_page);
}
se = list_next_entry(se, list);
sis->curr_swap_extent = se;
BUG_ON(se == start_se); /* It *must* be present */
}
}I just copied the pattern and changed the condition to 1 without much thought.
Quoted 4 lines
failing to return a value. I guess the compiler figured out that
BUG_ON(non-zero-constant)is equivalent toBUG(), which is noreturn.Let's do this?
Yes, it doesn't make much sense to use BUG_ON when the condition is 1...Thanks for the cleanup.
Quoted 11 lines
mm/swapfile.c renamed from mm/swapfile.c~mm-swap-use-rbtree-for-swap_extent-fix +1
-1@@ -218,7 +218,7 @@ offset_to_swap_extent(struct swap_info_sreturn se; }/* It *must* be present */ -BUG_ON (1 ); +BUG (); }