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

[Minchan Kim]

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.

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);
 }
 
 /*