Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1625022 > unrolled thread

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

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: [PATCH -mm -v3] mm, swap: Sort swap entries before free Minchan Kim <minchan@kernel.org> - 2017-04-18 07:00 +0200
    Re: [PATCH -mm -v3] mm, swap: Sort swap entries before free "Huang\, Ying" <ying.huang@intel.com> - 2017-04-19 10:20 +0200
      Re: [PATCH -mm -v3] mm, swap: Sort swap entries before free Minchan Kim <minchan@kernel.org> - 2017-04-20 08:40 +0200
        Re: [PATCH -mm -v3] mm, swap: Sort swap entries before free "Huang\, Ying" <ying.huang@intel.com> - 2017-04-20 09:20 +0200
          Re: [PATCH -mm -v3] mm, swap: Sort swap entries before free "Huang\, Ying" <ying.huang@intel.com> - 2017-04-21 14:30 +0200
            Re: [PATCH -mm -v3] mm, swap: Sort swap entries before free Tim Chen <tim.c.chen@linux.intel.com> - 2017-04-22 01:30 +0200
              Re: [PATCH -mm -v3] mm, swap: Sort swap entries before free "Huang\, Ying" <ying.huang@intel.com> - 2017-04-23 15:20 +0200
                Re: [PATCH -mm -v3] mm, swap: Sort swap entries before free Tim Chen <tim.c.chen@linux.intel.com> - 2017-04-24 18:10 +0200
            Re: [PATCH -mm -v3] mm, swap: Sort swap entries before free Minchan Kim <minchan@kernel.org> - 2017-04-24 07:00 +0200
              Re: [PATCH -mm -v3] mm, swap: Sort swap entries before free "Huang\, Ying" <ying.huang@intel.com> - 2017-04-24 09:00 +0200

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

Hi Huang,

On Fri, Apr 07, 2017 at 02:49:01PM +0800, Huang, Ying wrote:
> From: Huang Ying <ying.huang@intel.com>
> 
> 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.
> 
> Test the patch via measuring the run time of swap_cache_free_entries()
> during the exit phase of the applications use much swap space.  The
> results shows that the average run time of swap_cache_free_entries()
> reduced about 20% after applying the patch.
> 
> Signed-off-by: Huang Ying <ying.huang@intel.com>
> Acked-by: Tim Chen <tim.c.chen@intel.com>
> Cc: Hugh Dickins <hughd@google.com>
> Cc: Shaohua Li <shli@kernel.org>
> Cc: Minchan Kim <minchan@kernel.org>
> Cc: Rik van Riel <riel@redhat.com>
> 
> 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 | 12 ++++++++++++
>  1 file changed, 12 insertions(+)
> 
> diff --git a/mm/swapfile.c b/mm/swapfile.c
> index 90054f3c2cdc..f23c56e9be39 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,6 +1066,13 @@ 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 (long)(swp_type(*e1) - swp_type(*e2));
> +}
> +
>  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.

Thanks.

[toc] | [next] | [standalone]

#1625912

Minchan Kim <minchan@kernel.org> writes:

> Hi Huang,
>
> On Fri, Apr 07, 2017 at 02:49:01PM +0800, Huang, Ying wrote:
>> From: Huang Ying <ying.huang@intel.com>
>> 
>> 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.
>> 
>> Test the patch via measuring the run time of swap_cache_free_entries()
>> during the exit phase of the applications use much swap space.  The
>> results shows that the average run time of swap_cache_free_entries()
>> reduced about 20% after applying the patch.
>> 
>> Signed-off-by: Huang Ying <ying.huang@intel.com>
>> Acked-by: Tim Chen <tim.c.chen@intel.com>
>> Cc: Hugh Dickins <hughd@google.com>
>> Cc: Shaohua Li <shli@kernel.org>
>> Cc: Minchan Kim <minchan@kernel.org>
>> Cc: Rik van Riel <riel@redhat.com>
>> 
>> 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 | 12 ++++++++++++
>>  1 file changed, 12 insertions(+)
>> 
>> diff --git a/mm/swapfile.c b/mm/swapfile.c
>> index 90054f3c2cdc..f23c56e9be39 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,6 +1066,13 @@ 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 (long)(swp_type(*e1) - swp_type(*e2));
>> +}
>> +
>>  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.

Best Regards,
Huang, Ying

[toc] | [prev] | [next] | [standalone]

#1627033

On Wed, Apr 19, 2017 at 04:14:43PM +0800, Huang, Ying wrote:
> Minchan Kim <minchan@kernel.org> writes:
> 
> > Hi Huang,
> >
> > On Fri, Apr 07, 2017 at 02:49:01PM +0800, Huang, Ying wrote:
> >> From: Huang Ying <ying.huang@intel.com>
> >> 
> >> 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.
> >> 
> >> Test the patch via measuring the run time of swap_cache_free_entries()
> >> during the exit phase of the applications use much swap space.  The
> >> results shows that the average run time of swap_cache_free_entries()
> >> reduced about 20% after applying the patch.
> >> 
> >> Signed-off-by: Huang Ying <ying.huang@intel.com>
> >> Acked-by: Tim Chen <tim.c.chen@intel.com>
> >> Cc: Hugh Dickins <hughd@google.com>
> >> Cc: Shaohua Li <shli@kernel.org>
> >> Cc: Minchan Kim <minchan@kernel.org>
> >> Cc: Rik van Riel <riel@redhat.com>
> >> 
> >> 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 | 12 ++++++++++++
> >>  1 file changed, 12 insertions(+)
> >> 
> >> diff --git a/mm/swapfile.c b/mm/swapfile.c
> >> index 90054f3c2cdc..f23c56e9be39 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,6 +1066,13 @@ 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 (long)(swp_type(*e1) - swp_type(*e2));
> >> +}
> >> +
> >>  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.

Do not add such bogus code.

Nacked.

[toc] | [prev] | [next] | [standalone]

#1627155

Minchan Kim <minchan@kernel.org> writes:

> On Wed, Apr 19, 2017 at 04:14:43PM +0800, Huang, Ying wrote:
>> Minchan Kim <minchan@kernel.org> writes:
>> 
>> > Hi Huang,
>> >
>> > On Fri, Apr 07, 2017 at 02:49:01PM +0800, Huang, Ying wrote:
>> >> From: Huang Ying <ying.huang@intel.com>
>> >> 
>> >> 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.
>> >> 
>> >> Test the patch via measuring the run time of swap_cache_free_entries()
>> >> during the exit phase of the applications use much swap space.  The
>> >> results shows that the average run time of swap_cache_free_entries()
>> >> reduced about 20% after applying the patch.
>> >> 
>> >> Signed-off-by: Huang Ying <ying.huang@intel.com>
>> >> Acked-by: Tim Chen <tim.c.chen@intel.com>
>> >> Cc: Hugh Dickins <hughd@google.com>
>> >> Cc: Shaohua Li <shli@kernel.org>
>> >> Cc: Minchan Kim <minchan@kernel.org>
>> >> Cc: Rik van Riel <riel@redhat.com>
>> >> 
>> >> 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 | 12 ++++++++++++
>> >>  1 file changed, 12 insertions(+)
>> >> 
>> >> diff --git a/mm/swapfile.c b/mm/swapfile.c
>> >> index 90054f3c2cdc..f23c56e9be39 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,6 +1066,13 @@ 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 (long)(swp_type(*e1) - swp_type(*e2));
>> >> +}
>> >> +
>> >>  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.

Best Regards,
Huang, Ying

> Do not add such bogus code.
>
> Nacked.

[toc] | [prev] | [next] | [standalone]

#1628198

"Huang, Ying" <ying.huang@intel.com> writes:

> Minchan Kim <minchan@kernel.org> writes:
>
>> On Wed, Apr 19, 2017 at 04:14:43PM +0800, Huang, Ying wrote:
>>> Minchan Kim <minchan@kernel.org> writes:
>>> 
>>> > Hi Huang,
>>> >
>>> > On Fri, Apr 07, 2017 at 02:49:01PM +0800, Huang, Ying wrote:
>>> >> From: Huang Ying <ying.huang@intel.com>
>>> >> 
>>> >>  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;
+	}
+
+	/* 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?

I will send out the formal patch soon.

Best Regards,
Huang, Ying

[toc] | [prev] | [next] | [standalone]

#1628680

On Fri, 2017-04-21 at 20:29 +0800, Huang, Ying wrote:
> "Huang, Ying" <ying.huang@intel.com> writes:
> 
> > 
> > Minchan Kim <minchan@kernel.org> writes:
> > 
> > > 
> > > On Wed, Apr 19, 2017 at 04:14:43PM +0800, Huang, Ying wrote:
> > > > 
> > > > Minchan Kim <minchan@kernel.org> writes:
> > > > 
> > > > > 
> > > > > Hi Huang,
> > > > > 
> > > > > On Fri, Apr 07, 2017 at 02:49:01PM +0800, Huang, Ying wrote:
> > > > > > 
> > > > > > From: Huang Ying <ying.huang@intel.com>
> > > > > > 
> > > > > >  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).  

It is possible that nr_swapfiles > 1 when we have only 1 swapfile due
to swapoff.  The nr_swapfiles never decrement on swapoff.
We will need to use another counter in alloc_swap_info and
swapoff to track the true number of swapfiles in use to have a fast path
that avoid the search and sort for the 1 swap case.

Tim

[toc] | [prev] | [next] | [standalone]

#1629023

Tim Chen <tim.c.chen@linux.intel.com> writes:

> On Fri, 2017-04-21 at 20:29 +0800, Huang, Ying wrote:
>> "Huang, Ying" <ying.huang@intel.com> writes:
>> 
>> > 
>> > Minchan Kim <minchan@kernel.org> writes:
>> > 
>> > > 
>> > > On Wed, Apr 19, 2017 at 04:14:43PM +0800, Huang, Ying wrote:
>> > > > 
>> > > > Minchan Kim <minchan@kernel.org> writes:
>> > > > 
>> > > > > 
>> > > > > Hi Huang,
>> > > > > 
>> > > > > On Fri, Apr 07, 2017 at 02:49:01PM +0800, Huang, Ying wrote:
>> > > > > > 
>> > > > > > From: Huang Ying <ying.huang@intel.com>
>> > > > > > 
>> > > > > >  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).  
>
> It is possible that nr_swapfiles > 1 when we have only 1 swapfile due
> to swapoff.  The nr_swapfiles never decrement on swapoff.
> We will need to use another counter in alloc_swap_info and
> swapoff to track the true number of swapfiles in use to have a fast path
> that avoid the search and sort for the 1 swap case.

Yes.  That is a possible optimization.  But it doesn't cover another use
cases raised by Minchan (two swap device with different priority).  So
in general, we still need to check whether there are entries from
multiple swap devices in the array.  Given the cost of the checking code
is really low, I think maybe we can just always use the checking code.
Do you think so?

Best Regards,
Huang, Ying

[toc] | [prev] | [next] | [standalone]

#1629739

On Sun, 2017-04-23 at 21:16 +0800, Huang, Ying wrote:
> Tim Chen <tim.c.chen@linux.intel.com> writes:
> 
> > 
> > On Fri, 2017-04-21 at 20:29 +0800, Huang, Ying wrote:
> > > 
> > > "Huang, Ying" <ying.huang@intel.com> writes:
> > > 
> > > > 
> > > > 
> > > > Minchan Kim <minchan@kernel.org> writes:
> > > > 
> > > > > 
> > > > > 
> > > > > On Wed, Apr 19, 2017 at 04:14:43PM +0800, Huang, Ying wrote:
> > > > > > 
> > > > > > 
> > > > > > Minchan Kim <minchan@kernel.org> writes:
> > > > > > 
> > > > > > > 
> > > > > > > 
> > > > > > > Hi Huang,
> > > > > > > 
> > > > > > > On Fri, Apr 07, 2017 at 02:49:01PM +0800, Huang, Ying wrote:
> > > > > > > > 
> > > > > > > > 
> > > > > > > > From: Huang Ying <ying.huang@intel.com>
> > > > > > > > 
> > > > > > > >  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).  
> > It is possible that nr_swapfiles > 1 when we have only 1 swapfile due
> > to swapoff.  The nr_swapfiles never decrement on swapoff.
> > We will need to use another counter in alloc_swap_info and
> > swapoff to track the true number of swapfiles in use to have a fast path
> > that avoid the search and sort for the 1 swap case.
> Yes.  That is a possible optimization.  But it doesn't cover another use
> cases raised by Minchan (two swap device with different priority).  So
> in general, we still need to check whether there are entries from
> multiple swap devices in the array.  Given the cost of the checking code
> is really low, I think maybe we can just always use the checking code.
> Do you think so?

The single swap case is very common. It will be better if we can bypass the
extra logic and cost for multiple swap.  Yes, we still need the proper
check to see if sort is necessary as you proposed for the multiple swap case.

Tim

[toc] | [prev] | [next] | [standalone]

#1629175

On Fri, Apr 21, 2017 at 08:29:30PM +0800, Huang, Ying wrote:
> "Huang, Ying" <ying.huang@intel.com> writes:
> 
> > Minchan Kim <minchan@kernel.org> writes:
> >
> >> On Wed, Apr 19, 2017 at 04:14:43PM +0800, Huang, Ying wrote:
> >>> Minchan Kim <minchan@kernel.org> writes:
> >>> 
> >>> > Hi Huang,
> >>> >
> >>> > On Fri, Apr 07, 2017 at 02:49:01PM +0800, Huang, Ying wrote:
> >>> >> From: Huang Ying <ying.huang@intel.com>
> >>> >> 
> >>> >>  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.

diff --git a/mm/swapfile.c b/mm/swapfile.c
index f23c56e9be39..0d76a492786f 100644
--- a/mm/swapfile.c
+++ b/mm/swapfile.c
@@ -1073,30 +1073,40 @@ static int swp_entry_cmp(const void *ent1, const void *ent2)
 	return (long)(swp_type(*e1) - swp_type(*e2));
 }
 
-void swapcache_free_entries(swp_entry_t *entries, int n)
+void swapcache_free_entries(swp_entry_t *entries, int nr)
 {
-	struct swap_info_struct *p, *prev;
 	int i;
+	struct swap_info_struct *cur, *prev = NULL;
+	bool sorted = false;
 
-	if (n <= 0)
+	if (nr <= 0)
 		return;
 
-	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);
-	for (i = 0; i < n; ++i) {
-		p = swap_info_get_cont(entries[i], prev);
-		if (p)
-			swap_entry_free(p, entries[i]);
-		else
+	for (i = 0; i < nr; i++) {
+		cur = swap_info_get_cont(entries[i], prev);
+		if (!cur)
 			break;
-		prev = p;
+		if (cur != prev && !sorted && prev) {
+			spin_unlock(&cur->lock);
+			/*
+			 * Sort swap entries by swap device,
+			 * so each lock is only taken once.
+			 */
+			sort(entries + i, nr - i,
+					sizeof(swp_entry_t),
+					swp_entry_cmp, NULL);
+			sorted = true;
+			prev = NULL;
+			i--;
+			continue;
+		}
+
+		swap_entry_free(cur, entries[i]);
+		prev = cur;
 	}
-	if (p)
-		spin_unlock(&p->lock);
+
+	if (cur)
+		spin_unlock(&cur->lock);
 }
 
 /*

[toc] | [prev] | [next] | [standalone]

#1629246

Minchan Kim <minchan@kernel.org> writes:

> On Fri, Apr 21, 2017 at 08:29:30PM +0800, Huang, Ying wrote:
>> "Huang, Ying" <ying.huang@intel.com> writes:
>> 
>> > Minchan Kim <minchan@kernel.org> writes:
>> >
>> >> On Wed, Apr 19, 2017 at 04:14:43PM +0800, Huang, Ying wrote:
>> >>> Minchan Kim <minchan@kernel.org> writes:
>> >>> 
>> >>> > Hi Huang,
>> >>> >
>> >>> > On Fri, Apr 07, 2017 at 02:49:01PM +0800, Huang, Ying wrote:
>> >>> >> From: Huang Ying <ying.huang@intel.com>
>> >>> >> 
>> >>> >>  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.

Yes.  What I concerned is that one swap device may be locked twice
instead of once during the freeing.  I will give it some test.

Best Regards,
Huang, Ying

> diff --git a/mm/swapfile.c b/mm/swapfile.c
> index f23c56e9be39..0d76a492786f 100644
> --- a/mm/swapfile.c
> +++ b/mm/swapfile.c
> @@ -1073,30 +1073,40 @@ static int swp_entry_cmp(const void *ent1, const void *ent2)
>  	return (long)(swp_type(*e1) - swp_type(*e2));
>  }
>  
> -void swapcache_free_entries(swp_entry_t *entries, int n)
> +void swapcache_free_entries(swp_entry_t *entries, int nr)
>  {
> -	struct swap_info_struct *p, *prev;
>  	int i;
> +	struct swap_info_struct *cur, *prev = NULL;
> +	bool sorted = false;
>  
> -	if (n <= 0)
> +	if (nr <= 0)
>  		return;
>  
> -	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);
> -	for (i = 0; i < n; ++i) {
> -		p = swap_info_get_cont(entries[i], prev);
> -		if (p)
> -			swap_entry_free(p, entries[i]);
> -		else
> +	for (i = 0; i < nr; i++) {
> +		cur = swap_info_get_cont(entries[i], prev);
> +		if (!cur)
>  			break;
> -		prev = p;
> +		if (cur != prev && !sorted && prev) {
> +			spin_unlock(&cur->lock);
> +			/*
> +			 * Sort swap entries by swap device,
> +			 * so each lock is only taken once.
> +			 */
> +			sort(entries + i, nr - i,
> +					sizeof(swp_entry_t),
> +					swp_entry_cmp, NULL);
> +			sorted = true;
> +			prev = NULL;
> +			i--;
> +			continue;
> +		}
> +
> +		swap_entry_free(cur, entries[i]);
> +		prev = cur;
>  	}
> -	if (p)
> -		spin_unlock(&p->lock);
> +
> +	if (cur)
> +		spin_unlock(&cur->lock);
>  }
>  
>  /*

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web