Re: [PATCH -mm -v3] mm, swap: Sort swap entries before free

[Huang\, Ying]

Minchan Kim <minchan@xxxxxxxxxx> writes:

> On Wed, Apr 26, 2017 at 08:42:10PM +0800, Huang, Ying wrote:
>> Minchan Kim <minchan@xxxxxxxxxx> writes:
>> 
>> > On Fri, Apr 21, 2017 at 08:29:30PM +0800, Huang, Ying wrote:
>> >> "Huang, Ying" <ying.huang@xxxxxxxxx> writes:
>> >> 
>> >> > Minchan Kim <minchan@xxxxxxxxxx> writes:
>> >> >
>> >> >> On Wed, Apr 19, 2017 at 04:14:43PM +0800, Huang, Ying wrote:
>> >> >>> Minchan Kim <minchan@xxxxxxxxxx> writes:
>> >> >>> 
>> >> >>> > Hi Huang,
>> >> >>> >
>> >> >>> > On Fri, Apr 07, 2017 at 02:49:01PM +0800, Huang, Ying wrote:
>> >> >>> >> From: Huang Ying <ying.huang@xxxxxxxxx>
>> >> >>> >> 
>> >> >>> >>  void swapcache_free_entries(swp_entry_t *entries, int n)
>> >> >>> >>  {
>> >> >>> >>  	struct swap_info_struct *p, *prev;
>> >> >>> >> @@ -1075,6 +1083,10 @@ void swapcache_free_entries(swp_entry_t *entries, int n)
>> >> >>> >>  
>> >> >>> >>  	prev = NULL;
>> >> >>> >>  	p = NULL;
>> >> >>> >> +
>> >> >>> >> +	/* Sort swap entries by swap device, so each lock is only taken once. */
>> >> >>> >> +	if (nr_swapfiles > 1)
>> >> >>> >> +		sort(entries, n, sizeof(entries[0]), swp_entry_cmp, NULL);
>> >> >>> >
>> >> >>> > Let's think on other cases.
>> >> >>> >
>> >> >>> > There are two swaps and they are configured by priority so a swap's usage
>> >> >>> > would be zero unless other swap used up. In case of that, this sorting
>> >> >>> > is pointless.
>> >> >>> >
>> >> >>> > As well, nr_swapfiles is never decreased so if we enable multiple
>> >> >>> > swaps and then disable until a swap is remained, this sorting is
>> >> >>> > pointelss, too.
>> >> >>> >
>> >> >>> > How about lazy sorting approach? IOW, if we found prev != p and,
>> >> >>> > then we can sort it.
>> >> >>> 
>> >> >>> Yes.  That should be better.  I just don't know whether the added
>> >> >>> complexity is necessary, given the array is short and sort is fast.
>> >> >>
>> >> >> Huh?
>> >> >>
>> >> >> 1. swapon /dev/XXX1
>> >> >> 2. swapon /dev/XXX2
>> >> >> 3. swapoff /dev/XXX2
>> >> >> 4. use only one swap
>> >> >> 5. then, always pointless sort.
>> >> >
>> >> > Yes.  In this situation we will do unnecessary sorting.  What I don't
>> >> > know is whether the unnecessary sorting will hurt performance in real
>> >> > life.  I can do some measurement.
>> >> 
>> >> I tested the patch with 1 swap device and 1 process to eat memory
>> >> (remove the "if (nr_swapfiles > 1)" for test).  I think this is the
>> >> worse case because there is no lock contention.  The memory freeing time
>> >> increased from 1.94s to 2.12s (increase ~9.2%).  So there is some
>> >> overhead for some cases.  I change the algorithm to something like
>> >> below,
>> >> 
>> >>  void swapcache_free_entries(swp_entry_t *entries, int n)
>> >>  {
>> >>  	struct swap_info_struct *p, *prev;
>> >>  	int i;
>> >> +	swp_entry_t entry;
>> >> +	unsigned int prev_swp_type;
>> >>  
>> >>  	if (n <= 0)
>> >>  		return;
>> >>  
>> >> +	prev_swp_type = swp_type(entries[0]);
>> >> +	for (i = n - 1; i > 0; i--) {
>> >> +		if (swp_type(entries[i]) != prev_swp_type)
>> >> +			break;
>> >> +	}
>> >
>> > That's really what I want to avoid. For many swap usecases,
>> > it adds unnecessary overhead.
>> >
>> >> +
>> >> +	/* Sort swap entries by swap device, so each lock is only taken once. */
>> >> +	if (i)
>> >> +		sort(entries, n, sizeof(entries[0]), swp_entry_cmp, NULL);
>> >>  	prev = NULL;
>> >>  	p = NULL;
>> >>  	for (i = 0; i < n; ++i) {
>> >> -		p = swap_info_get_cont(entries[i], prev);
>> >> +		entry = entries[i];
>> >> +		p = swap_info_get_cont(entry, prev);
>> >>  		if (p)
>> >> -			swap_entry_free(p, entries[i]);
>> >> +			swap_entry_free(p, entry);
>> >>  		prev = p;
>> >>  	}
>> >>  	if (p)
>> >> 
>> >> With this patch, the memory freeing time increased from 1.94s to 1.97s.
>> >> I think this is good enough.  Do you think so?
>> >
>> > What I mean is as follows(I didn't test it at all):
>> >
>> > With this, sort entries if we found multiple entries in current
>> > entries. It adds some condition checks for non-multiple swap
>> > usecase but it would be more cheaper than the sorting.
>> > And it adds a [un]lock overhead for multiple swap usecase but
>> > it should be a compromise for single-swap usecase which is more
>> > popular.
>> >
>> 
>> How about the following solution?  It can avoid [un]lock overhead and
>> double lock issue for multiple swap user case and has good performance
>> for one swap user case too.
>
> How worse with approach I suggested compared to as-is?

The performance difference between your version and my version is small
for my testing.

> Unless it's too bad, let's not add more complicated thing to just
> enhance the minor usecase in such even *slow* path.
> It adds code size/maintainance overead.
> With your suggestion, it might enhance a bit with speicific benchmark
> but not sure it's really worth for real practice.

I don't think the code complexity has much difference between our latest
versions.  As for complexity, I think my original version which just
uses nr_swapfiles to avoid sort() for single swap device is simple and
good enough for this task.  Maybe we can just improve the correctness of
swap device counting as Tim suggested.

Best Regards,
Huang, Ying

>> 
>> Best Regards,
>> Huang, Ying
>> 
>> From 7bd903c42749c448ef6acbbdee8dcbc1c5b498b9 Mon Sep 17 00:00:00 2001
>> From: Huang Ying <ying.huang@xxxxxxxxx>
>> Date: Thu, 23 Feb 2017 13:05:20 +0800
>> Subject: [PATCH -v5] mm, swap: Sort swap entries before free
>> 
>> To reduce the lock contention of swap_info_struct->lock when freeing
>> swap entry.  The freed swap entries will be collected in a per-CPU
>> buffer firstly, and be really freed later in batch.  During the batch
>> freeing, if the consecutive swap entries in the per-CPU buffer belongs
>> to same swap device, the swap_info_struct->lock needs to be
>> acquired/released only once, so that the lock contention could be
>> reduced greatly.  But if there are multiple swap devices, it is
>> possible that the lock may be unnecessarily released/acquired because
>> the swap entries belong to the same swap device are non-consecutive in
>> the per-CPU buffer.
>> 
>> To solve the issue, the per-CPU buffer is sorted according to the swap
>> device before freeing the swap entries.  Test shows that the time
>> spent by swapcache_free_entries() could be reduced after the patch.
>> 
>> With the patch, the memory (some swapped out) free time reduced
>> 13.6% (from 2.59s to 2.28s) in the vm-scalability swap-w-rand test
>> case with 16 processes.  The test is done on a Xeon E5 v3 system.  The
>> swap device used is a RAM simulated PMEM (persistent memory) device.
>> To test swapping, the test case creates 16 processes, which allocate
>> and write to the anonymous pages until the RAM and part of the swap
>> device is used up, finally the memory (some swapped out) is freed
>> before exit.
>> 
>> Signed-off-by: Huang Ying <ying.huang@xxxxxxxxx>
>> Acked-by: Tim Chen <tim.c.chen@xxxxxxxxx>
>> Cc: Hugh Dickins <hughd@xxxxxxxxxx>
>> Cc: Shaohua Li <shli@xxxxxxxxxx>
>> Cc: Minchan Kim <minchan@xxxxxxxxxx>
>> Cc: Rik van Riel <riel@xxxxxxxxxx>
>> 
>> v5:
>> 
>> - Use a smarter way to determine whether sort is necessary.
>> 
>> v4:
>> 
>> - Avoid unnecessary sort if all entries are from one swap device.
>> 
>> v3:
>> 
>> - Add some comments in code per Rik's suggestion.
>> 
>> v2:
>> 
>> - Avoid sort swap entries if there is only one swap device.
>> ---
>>  mm/swapfile.c | 43 ++++++++++++++++++++++++++++++++++++++-----
>>  1 file changed, 38 insertions(+), 5 deletions(-)
>> 
>> diff --git a/mm/swapfile.c b/mm/swapfile.c
>> index 71890061f653..10e75f9e8ac1 100644
>> --- a/mm/swapfile.c
>> +++ b/mm/swapfile.c
>> @@ -37,6 +37,7 @@
>>  #include <linux/swapfile.h>
>>  #include <linux/export.h>
>>  #include <linux/swap_slots.h>
>> +#include <linux/sort.h>
>>  
>>  #include <asm/pgtable.h>
>>  #include <asm/tlbflush.h>
>> @@ -1065,20 +1066,52 @@ void swapcache_free(swp_entry_t entry)
>>  	}
>>  }
>>  
>> +static int swp_entry_cmp(const void *ent1, const void *ent2)
>> +{
>> +	const swp_entry_t *e1 = ent1, *e2 = ent2;
>> +
>> +	return (int)(swp_type(*e1) - swp_type(*e2));
>> +}
>> +
>>  void swapcache_free_entries(swp_entry_t *entries, int n)
>>  {
>>  	struct swap_info_struct *p, *prev;
>> -	int i;
>> +	int i, m;
>> +	swp_entry_t entry;
>> +	unsigned int prev_swp_type;
>>  
>>  	if (n <= 0)
>>  		return;
>>  
>>  	prev = NULL;
>>  	p = NULL;
>> -	for (i = 0; i < n; ++i) {
>> -		p = swap_info_get_cont(entries[i], prev);
>> -		if (p)
>> -			swap_entry_free(p, entries[i]);
>> +	m = 0;
>> +	prev_swp_type = swp_type(entries[0]);
>> +	for (i = 0; i < n; i++) {
>> +		entry = entries[i];
>> +		if (likely(swp_type(entry) == prev_swp_type)) {
>> +			p = swap_info_get_cont(entry, prev);
>> +			if (likely(p))
>> +				swap_entry_free(p, entry);
>> +			prev = p;
>> +		} else if (!m)
>> +			m = i;
>> +	}
>> +	if (p)
>> +		spin_unlock(&p->lock);
>> +	if (likely(!m))
>> +		return;
>> +
>> +	/* Sort swap entries by swap device, so each lock is only taken once. */
>> +	sort(entries + m, n - m, sizeof(entries[0]), swp_entry_cmp, NULL);
>> +	prev = NULL;
>> +	for (i = m; i < n; i++) {
>> +		entry = entries[i];
>> +		if (swp_type(entry) == prev_swp_type)
>> +			continue;
>> +		p = swap_info_get_cont(entry, prev);
>> +		if (likely(p))
>> +			swap_entry_free(p, entry);
>>  		prev = p;
>>  	}
>>  	if (p)
>> -- 
>> 2.11.0
>>