mm: swap: Use swapfiles in priority order

According to the swapon documentation

Swap pages are allocated from areas in priority order, highest priority first. For areas with different priorities, a higher-priority area is exhausted before using a lower-priority area.

A user reported that the reality is different. When multiple swap files are enabled and a memory consumer started, the swap files are consumed in pairs after the highest priority file is exhausted. Early in the lifetime of the test, swapfile consumptions looks like

Filename                                Type            Size    Used    Priority
/testswap1                              file            100004  100004  8
/testswap2                              file            100004  23764   7
/testswap3                              file            100004  23764   6
/testswap4                              file            100004  0       5
/testswap5                              file            100004  0       4
/testswap6                              file            100004  0       3
/testswap7                              file            100004  0       2
/testswap8                              file            100004  0       1

This patch fixes the swap_list search in get_swap_page to use the swap files in the correct order. When applied the swap file consumptions looks like

Filename                                Type            Size    Used    Priority
/testswap1                              file            100004  100004  8
/testswap2                              file            100004  100004  7
/testswap3                              file            100004  29372   6
/testswap4                              file            100004  0       5
/testswap5                              file            100004  0       4
/testswap6                              file            100004  0       3
/testswap7                              file            100004  0       2
/testswap8                              file            100004  0       1

Signed-off-by Mel Gorman <[email protected]>

---
 mm/swapfile.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

mm/swapfile.c +0 -0

index 4a7f7e6..6d0ac2b 100644

mm/swapfile.c +0 -1

                hp_index = atomic_xchg(&highest_priority_index, -1);
                /*
                 * highest_priority_index records current highest priority swap
--

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Quoted 47 lines · Mel Gorman

According to the swapon documentation

Swap pages are allocated from areas in priority order, highest priority first. For areas with different priorities, a higher-priority area is exhausted before using a lower-priority area.

A user reported that the reality is different. When multiple swap files are enabled and a memory consumer started, the swap files are consumed in pairs after the highest priority file is exhausted. Early in the lifetime of the test, swapfile consumptions looks like

Filename                                Type            Size    Used    Priority
/testswap1                              file            100004  100004  8
/testswap2                              file            100004  23764   7
/testswap3                              file            100004  23764   6
/testswap4                              file            100004  0       5
/testswap5                              file            100004  0       4
/testswap6                              file            100004  0       3
/testswap7                              file            100004  0       2
/testswap8                              file            100004  0       1

This patch fixes the swap_list search in get_swap_page to use the swap files in the correct order. When applied the swap file consumptions looks like

Filename                                Type            Size    Used    Priority
/testswap1                              file            100004  100004  8
/testswap2                              file            100004  100004  7
/testswap3                              file            100004  29372   6
/testswap4                              file            100004  0       5
/testswap5                              file            100004  0       4
/testswap6                              file            100004  0       3
/testswap7                              file            100004  0       2
/testswap8                              file            100004  0       1

Signed-off-by Mel Gorman <[email protected]>

---
 mm/swapfile.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

mm/swapfile.c +0 -0

index 4a7f7e6..6d0ac2b 100644
@@ -651,7 +651,7 @@ swp_entry_t get_swap_page(void)
                goto noswap;
        atomic_long_dec(&nr_swap_pages);
 

mm/swapfile.c swp_entry_t get_swap_page(void) · line 654

Quoted 2 lines

mm/swapfile.c +1 -1

-       for (type = swap_list.next; type >= 0 && wrapped < 2; type = next) {
+       for (type = swap_list.head; type >= 0 && wrapped < 2; type = next) {

Does it lead to a "schlemiel the painter's algorithm"?
(please forgive my rude words, but I can't find a precise word to describe it because English is not my native language. My apologize.)

How about modify it like this?

Quoted 55 lines · Weijie Yang

Quoted 44 lines · Mel Gorman

According to the swapon documentation

Swap pages are allocated from areas in priority order, highest priority first. For areas with different priorities, a higher-priority area is exhausted before using a lower-priority area.

A user reported that the reality is different. When multiple swap files are enabled and a memory consumer started, the swap files are consumed in pairs after the highest priority file is exhausted. Early in the lifetime of the test, swapfile consumptions looks like

Filename                                Type            Size    Used    Priority
/testswap1                              file            100004  100004  8
/testswap2                              file            100004  23764   7
/testswap3                              file            100004  23764   6
/testswap4                              file            100004  0       5
/testswap5                              file            100004  0       4
/testswap6                              file            100004  0       3
/testswap7                              file            100004  0       2
/testswap8                              file            100004  0       1

This patch fixes the swap_list search in get_swap_page to use the swap files in the correct order. When applied the swap file consumptions looks like

Filename                                Type            Size    Used    Priority
/testswap1                              file            100004  100004  8
/testswap2                              file            100004  100004  7
/testswap3                              file            100004  29372   6
/testswap4                              file            100004  0       5
/testswap5                              file            100004  0       4
/testswap6                              file            100004  0       3
/testswap7                              file            100004  0       2
/testswap8                              file            100004  0       1

Signed-off-by Mel Gorman <[email protected]>

---
 mm/swapfile.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

mm/swapfile.c +0 -0

index 4a7f7e6..6d0ac2b 100644

mm/swapfile.c swp_entry_t get_swap_page(void) · line 654

Quoted 5 lines

mm/swapfile.c +1 -1

@@ -651,7 +651,7 @@ swp_entry_t get_swap_page(void)
                goto noswap;
        atomic_long_dec(&nr_swap_pages);
 
-       for (type = swap_list.next; type >= 0 && wrapped < 2; type = next) {
+       for (type = swap_list.head; type >= 0 && wrapped < 2; type = next) {

Does it lead to a "schlemiel the painter's algorithm"?
(please forgive my rude words, but I can't find a precise word to describe it because English is not my native language. My apologize.)

Quoted 2 lines

How about modify it like this?

I blindly applied your version without review to see how it behaved and found it uses every second swapfile like this

Filename                                Type            Size    Used    Priority
/testswap1                              file            100004  100004  8
/testswap2                              file            100004  16      7
/testswap3                              file            100004  100004  6
/testswap4                              file            100004  8       5
/testswap5                              file            100004  100004  4
/testswap6                              file            100004  8       3
/testswap7                              file            100004  100004  2
/testswap8                              file            100004  23504   1

I admit I did not review the swap priority search algorithm in detail because the fix superficially looked straight forward but this alternative is not the answer either.

--
Mel Gorman
SUSE Labs

On Thu, Feb 13, 2014 at 6:42 PM, Mel Gorman <mgorman <at> suse.de> wrote:

Quoted 2 lines

(quoted diff) +1 -1

-       for (type = swap_list.next; type >= 0 && wrapped < 2; type = next) {
+       for (type = swap_list.head; type >= 0 && wrapped < 2; type = next) {

Does it lead to a "schlemiel the painter's algorithm"?
(please forgive my rude words, but I can't find a precise word to describe it

How about modify it like this?

- next = swap_list.head;
+ next = type;

Quoted 2 lines · Weijie Yang <weijie.yang.kh <at> gmail.com> writes:

On Thu, Feb 13, 2014 at 6:42 PM, Mel Gorman <mgorman <at> suse.de> wrote:

[...]

Quoted 3 lines

Quoted 2 lines

mm/swapfile.c +1 -1

-       for (type = swap_list.next; type >= 0 && wrapped < 2; type = next) {
+       for (type = swap_list.head; type >= 0 && wrapped < 2; type = next) {

[...]

Quoted 5 lines

Does it lead to a "schlemiel the painter's algorithm"?
(please forgive my rude words, but I can't find a precise word to describe it

How about modify it like this?

[...]

Quoted 2 lines

- next = swap_list.head;
+ next = type;

[...]

Hi,
unfortunately withou studying the code more thoroughly I'm not even sure if you meant you code to extend or replace Mels patch.

To be sure about your intention. You refered to algorithm scaling because you were afraid the new code would scan the full list all the time right ?

But simply letting the machines give a try for both options I can now qualify both.

Just your patch creates a behaviour of jumping over priorities (see the following example), so I hope you meant combining both patches. With that in mind the patch I eventually tested the combined patch looking like this:

mm/swapfile.c +2 -2

index 612a7c9..53a3873 100644
@@ -650,7 +650,7 @@ swp_entry_t get_swap_page(void)
                goto noswap;
        atomic_long_dec(&nr_swap_pages);
 
-       for (type = swap_list.next; type >= 0 && wrapped < 2; type = next) {
+       for (type = swap_list.head; type >= 0 && wrapped < 2; type = next) {
                hp_index = atomic_xchg(&highest_priority_index, -1);
                /*
                 * highest_priority_index records current highest priority swap

@@ -675,7 +675,7 @@ swp_entry_t get_swap_page(void)
                next = si->next;
                if (next < 0 ||
                    (!wrapped && si->prio != swap_info[next]->prio)) {
-                       next = swap_list.head;
+                       next = type;
                        wrapped++;
                }
 

At least for the two different cases we identified to fix with it the new code works as well:
I) incrementing swap now in proper priority order

Filename                                Type            Size    Used    Priority
/testswap1                              file            100004  100004  8
/testswap2                              file            100004  100004  7
/testswap3                              file            100004  100004  6
/testswap4                              file            100004  100004  5
/testswap5                              file            100004  100004  4
/testswap6                              file            100004  68764   3
/testswap7                              file            100004  0       2
/testswap8                              file            100004  0       1

II) comparing a memory based block device "as one" vs "split into 8 pieces" as swap target(s).
Like with Mels patch alone I'm able to achieve 1.5G/s TP on the overcommitted memory no matter how much swap targets I split it into.

So while I can't speak for the logical correctness of your addition to the patch at least in terms of effectiveness it seems fine.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Quoted 26 lines · Christian Ehrhardt

Quoted 2 lines · Weijie Yang <weijie.yang.kh <at> gmail.com> writes:

On Thu, Feb 13, 2014 at 6:42 PM, Mel Gorman <mgorman <at> suse.de> wrote:

[...]

Quoted 3 lines

Quoted 2 lines

mm/swapfile.c +1 -1

-       for (type = swap_list.next; type >= 0 && wrapped < 2; type = next) {
+       for (type = swap_list.head; type >= 0 && wrapped < 2; type = next) {

[...]

Quoted 5 lines

Does it lead to a "schlemiel the painter's algorithm"?
(please forgive my rude words, but I can't find a precise word to describe it

How about modify it like this?

[...]

Quoted 2 lines

- next = swap_list.head;
+ next = type;

[...]

Hi,
unfortunately withou studying the code more thoroughly I'm not even sure if you meant you code to extend or replace Mels patch.

To be sure about your intention. You refered to algorithm scaling because you were afraid the new code would scan the full list all the time right ?

Quoted 7 lines

But simply letting the machines give a try for both options I can now qualify both.

Just your patch creates a behaviour of jumping over priorities (see the following example), so I hope you meant combining both patches. With that in mind the patch I eventually tested the combined patch looking like this:

Hi Christian,

My patch is not appropriate, so there is no need to combine it with Mel's patch.

What I worried about Mel's patch is not only the search efficiency, actually it has
negligible impact on system, but also the following scenario:

If two swapfiles have the same priority, in ordinary semantic, they should be used
in balance. But with Mel's patch, it will always get the free swap_entry from the
swap_list.head in priority order, I worry it could break the balance.

I think you can test this scenario if you have available test machines.

Appreciate for your done.

Replace the singly-linked list tracking active, i.e. swapon'ed, swap_info_struct entries with a doubly-linked list using struct list_heads. Simplify the logic iterating and manipulating the list of entries, especially get_swap_page(), by using standard list_head functions, and removing the highest priority iteration logic.

The change fixes the bug:
https://lkml.org/lkml/2014/2/13/181
in which different priority swap entries after the highest priority entry are incorrectly used equally in pairs. The swap behavior is now as advertised, i.e. different priority swap entries are used in order, and equal priority swap targets are used concurrently.

Signed-off-by Dan Streetman <[email protected]>

---
 include/linux/swap.h     |   7 +--
 include/linux/swapfile.h |   2 +-
 mm/frontswap.c           |  13 ++--
 mm/swapfile.c            | 156 +++++++++++++++++------------------------------
 4 files changed, 63 insertions(+), 115 deletions(-)

include/linux/swap.h +1 -6

index 3507115..96662d8 100644
@@ -214,8 +214,8 @@ struct percpu_cluster {
 struct swap_info_struct {
 	unsigned long	flags;		/* SWP_USED etc: see above */
 	signed short	prio;		/* swap priority of this type */
+	struct list_head list;		/* entry in swap list */
 	signed char	type;		/* strange name for an index */
-	signed char	next;		/* next type on the swap list */
 	unsigned int	max;		/* extent of the swap_map */
 	unsigned char *swap_map;	/* vmalloc'ed array of usage counts */
 	struct swap_cluster_info *cluster_info; /* cluster info. Only for SSD */

@@ -255,11 +255,6 @@ struct swap_info_struct {
 	struct swap_cluster_info discard_cluster_tail; /* list tail of discard clusters */
 };
 
-struct swap_list_t {
-	int head;	/* head of priority-ordered swapfile list */
-	int next;	/* swapfile to be used next */
-};
-
 /* linux/mm/workingset.c */
 void *workingset_eviction(struct address_space *mapping, struct page *page);
 bool workingset_refault(void *shadow);

include/linux/swapfile.h +1 -1

index e282624..2eab382 100644
@@ -6,7 +6,7 @@
  * want to expose them to the dozens of source files that include swap.h
  */
 extern spinlock_t swap_lock;
-extern struct swap_list_t swap_list;
+extern struct list_head swap_list_head;
 extern struct swap_info_struct *swap_info[];
 extern int try_to_unuse(unsigned int, bool, unsigned long);
 

mm/frontswap.c +1 -4

index 1b24bdc..fae1160 100644
@@ -327,15 +327,12 @@ EXPORT_SYMBOL(__frontswap_invalidate_area);
 
 static unsigned long __frontswap_curr_pages(void)
 {
-	int type;
 	unsigned long totalpages = 0;
 	struct swap_info_struct *si = NULL;
 
 	assert_spin_locked(&swap_lock);
-	for (type = swap_list.head; type >= 0; type = si->next) {
-		si = swap_info[type];
+	list_for_each_entry(si, &swap_list_head, list)
 		totalpages += atomic_read(&si->frontswap_pages);
-	}
 	return totalpages;
 }
 

@@ -347,11 +344,9 @@ static int __frontswap_unuse_pages(unsigned long total, unsigned long *unused,
 	int si_frontswap_pages;
 	unsigned long total_pages_to_unuse = total;

mm/frontswap.c +2 -2

@@ -366,7 +361,7 @@ static int __frontswap_unuse_pages(unsigned long total, unsigned long *unused,
 		}
 		vm_unacct_memory(pages);
 		*unused = pages_to_unuse;
-		*swapid = type;
+		*swapid = si->type;
 		ret = 0;
 		break;
 	}

@@ -413,7 +408,7 @@ void frontswap_shrink(unsigned long target_pages)
 	/*
 	 * we don't want to hold swap_lock while doing a very
 	 * lengthy try_to_unuse, but swap_list may change
-	 * so restart scan from swap_list.head each time
+	 * so restart scan from swap_list_head each time
 	 */
 	spin_lock(&swap_lock);
 	ret = __frontswap_shrink(target_pages, &pages_to_unuse, &type);

mm/swapfile.c +10 -41

index 4a7f7e6..b958645 100644
@@ -51,14 +51,14 @@ atomic_long_t nr_swap_pages;
 /* protected with swap_lock. reading in vm_swap_full() doesn't need lock */
 long total_swap_pages;
 static int least_priority;
-static atomic_t highest_priority_index = ATOMIC_INIT(-1);
 
 static const char Bad_file[] = "Bad swap file entry ";
 static const char Unused_file[] = "Unused swap file entry ";
 static const char Bad_offset[] = "Bad swap offset entry ";
 static const char Unused_offset[] = "Unused swap offset entry ";
 
-struct swap_list_t swap_list = {-1, -1};
+/* all active swap_info */
+LIST_HEAD(swap_list_head);
 
 struct swap_info_struct *swap_info[MAX_SWAPFILES];
 

@@ -640,66 +640,50 @@ no_page:
 
 swp_entry_t get_swap_page(void)
 {
-	struct swap_info_struct *si;
+	struct swap_info_struct *si, *next;
 	pgoff_t offset;
-	int type, next;
-	int wrapped = 0;
-	int hp_index;
+	struct list_head *tmp;
 
 	spin_lock(&swap_lock);
 	if (atomic_long_read(&nr_swap_pages) <= 0)
 		goto noswap;
 	atomic_long_dec(&nr_swap_pages);
 
-	for (type = swap_list.next; type >= 0 && wrapped < 2; type = next) {
-		hp_index = atomic_xchg(&highest_priority_index, -1);
-		/*
-		 * highest_priority_index records current highest priority swap
-		 * type which just frees swap entries. If its priority is
-		 * higher than that of swap_list.next swap type, we use it.  It
-		 * isn't protected by swap_lock, so it can be an invalid value
-		 * if the corresponding swap type is swapoff. We double check
-		 * the flags here. It's even possible the swap type is swapoff
-		 * and swapon again and its priority is changed. In such rare
-		 * case, low prority swap type might be used, but eventually
-		 * high priority swap will be used after several rounds of
-		 * swap.
-		 */
-		if (hp_index != -1 && hp_index != type &&
-		    swap_info[type]->prio < swap_info[hp_index]->prio &&
-		    (swap_info[hp_index]->flags & SWP_WRITEOK)) {
-			type = hp_index;
-			swap_list.next = type;
-		}
-
-		si = swap_info[type];
-		next = si->next;
-		if (next < 0 ||
-		    (!wrapped && si->prio != swap_info[next]->prio)) {
-			next = swap_list.head;
-			wrapped++;
-		}
-
+	list_for_each(tmp, &swap_list_head) {
+		si = list_entry(tmp, typeof(*si), list);
 		spin_lock(&si->lock);
-		if (!si->highest_bit) {
-			spin_unlock(&si->lock);
-			continue;
-		}
-		if (!(si->flags & SWP_WRITEOK)) {
+		if (!si->highest_bit || !(si->flags & SWP_WRITEOK)) {
 			spin_unlock(&si->lock);
 			continue;
 		}
 
-		swap_list.next = next;
+		/*
+		 * rotate the current swap_info that we're going to use
+		 * to after any other swap_info that have the same prio,

mm/swapfile.c +1 -1

 		spin_unlock(&swap_lock);
 		/* This is called for allocating swap entry for cache */
 		offset = scan_swap_map(si, SWAP_HAS_CACHE);
 		spin_unlock(&si->lock);
 		if (offset)
-			return swp_entry(type, offset);
+			return swp_entry(si->type, offset);

mm/swapfile.c +1 -27

 	atomic_long_inc(&nr_swap_pages);

@@ -766,27 +750,6 @@ out:
 	return NULL;
 }
 
-/*
- * This swap type frees swap entry, check if it is the highest priority swap
- * type which just frees swap entry. get_swap_page() uses
- * highest_priority_index to search highest priority swap type. The
- * swap_info_struct.lock can't protect us if there are multiple swap types
- * active, so we use atomic_cmpxchg.
- */
-static void set_highest_priority_index(int type)
-{
-	int old_hp_index, new_hp_index;
-
-	do {
-		old_hp_index = atomic_read(&highest_priority_index);
-		if (old_hp_index != -1 &&
-			swap_info[old_hp_index]->prio >= swap_info[type]->prio)
-			break;
-		new_hp_index = type;
-	} while (atomic_cmpxchg(&highest_priority_index,
-		old_hp_index, new_hp_index) != old_hp_index);
-}
-
 static unsigned char swap_entry_free(struct swap_info_struct *p,
 				     swp_entry_t entry, unsigned char usage)
 {

@@ -830,7 +793,6 @@ static unsigned char swap_entry_free(struct swap_info_struct *p,
 			p->lowest_bit = offset;
 		if (offset > p->highest_bit)
 			p->highest_bit = offset;
-		set_highest_priority_index(p->type);
 		atomic_long_inc(&nr_swap_pages);
 		p->inuse_pages--;
 		frontswap_invalidate_page(p->type, offset);

@@ -1765,7 +1727,7 @@ static void _enable_swap_info(struct swap_info_struct *p, int prio,
 				unsigned char *swap_map,
 				struct swap_cluster_info *cluster_info)
 {
-	int i, prev;
+	struct swap_info_struct *si;
 
 	if (prio >= 0)
 		p->prio = prio;

@@ -1777,18 +1739,21 @@ static void _enable_swap_info(struct swap_info_struct *p, int prio,
 	atomic_long_add(p->pages, &nr_swap_pages);
 	total_swap_pages += p->pages;
 
-	/* insert swap space into swap_list: */
-	prev = -1;
-	for (i = swap_list.head; i >= 0; i = swap_info[i]->next) {
-		if (p->prio >= swap_info[i]->prio)

mm/swapfile.c +21 -27

 	}
-	p->next = i;
-	if (prev < 0)
-		swap_list.head = swap_list.next = p->type;
-	else
-		swap_info[prev]->next = p->type;
+	/*
+	 * this covers two cases:
+	 * 1) p->prio is less than all existing prio
+	 * 2) the swap list is empty
+	 */
+	list_add_tail(&p->list, &swap_list_head);
 }
 
 static void enable_swap_info(struct swap_info_struct *p, int prio,

@@ -1823,8 +1788,7 @@ SYSCALL_DEFINE1(swapoff, const char __user *, specialfile)
 	struct address_space *mapping;
 	struct inode *inode;
 	struct filename *pathname;
-	int i, type, prev;
-	int err;
+	int err, found = 0;
 	unsigned int old_block_size;
 
 	if (!capable(CAP_SYS_ADMIN))

@@ -1842,17 +1806,16 @@ SYSCALL_DEFINE1(swapoff, const char __user *, specialfile)
 		goto out;
 
 	mapping = victim->f_mapping;
-	prev = -1;
 	spin_lock(&swap_lock);
-	for (type = swap_list.head; type >= 0; type = swap_info[type]->next) {
-		p = swap_info[type];
+	list_for_each_entry(p, &swap_list_head, list) {
 		if (p->flags & SWP_WRITEOK) {
-			if (p->swap_file->f_mapping == mapping)
+			if (p->swap_file->f_mapping == mapping) {
+				found = 1;
 				break;
+			}
 		}
-		prev = type;
 	}
-	if (type < 0) {
+	if (!found) {
 		err = -EINVAL;
 		spin_unlock(&swap_lock);
 		goto out_dput;

@@ -1864,20 +1827,15 @@ SYSCALL_DEFINE1(swapoff, const char __user *, specialfile)
 		spin_unlock(&swap_lock);
 		goto out_dput;
 	}
-	if (prev < 0)
-		swap_list.head = p->next;
-	else
-		swap_info[prev]->next = p->next;
-	if (type == swap_list.next) {
-		/* just pick something that's safe... */
-		swap_list.next = swap_list.head;
-	}
 	spin_lock(&p->lock);
 	if (p->prio < 0) {
-		for (i = p->next; i >= 0; i = swap_info[i]->next)
-			swap_info[i]->prio = p->prio--;
+		struct swap_info_struct *si = p;
+		list_for_each_entry_continue(si, &swap_list_head, list) {
+			si->prio++;
+		}
 		least_priority++;
 	}
+	list_del_init(&p->list);
 	atomic_long_sub(p->pages, &nr_swap_pages);
 	total_swap_pages -= p->pages;
 	p->flags &= ~SWP_WRITEOK;

@@ -1885,7 +1843,7 @@ SYSCALL_DEFINE1(swapoff, const char __user *, specialfile)
 	spin_unlock(&swap_lock);
 
 	set_current_oom_origin();
-	err = try_to_unuse(type, false, 0); /* force all pages to be unused */
+	err = try_to_unuse(p->type, false, 0); /* force unuse all pages */
 	clear_current_oom_origin();
 
 	if (err) {

@@ -1926,7 +1884,7 @@ SYSCALL_DEFINE1(swapoff, const char __user *, specialfile)
 	frontswap_map = frontswap_map_get(p);
 	spin_unlock(&p->lock);
 	spin_unlock(&swap_lock);
-	frontswap_invalidate_area(type);
+	frontswap_invalidate_area(p->type);
 	frontswap_map_set(p, NULL);
 	mutex_unlock(&swapon_mutex);
 	free_percpu(p->percpu_cluster);

@@ -1935,7 +1893,7 @@ SYSCALL_DEFINE1(swapoff, const char __user *, specialfile)
 	vfree(cluster_info);
 	vfree(frontswap_map);
 	/* Destroy swap account information */
-	swap_cgroup_swapoff(type);
+	swap_cgroup_swapoff(p->type);
 
 	inode = mapping->host;
 	if (S_ISBLK(inode->i_mode)) {

@@ -2142,8 +2100,8 @@ static struct swap_info_struct *alloc_swap_info(void)
 		 */
 	}
 	INIT_LIST_HEAD(&p->first_swap_extent.list);
+	INIT_LIST_HEAD(&p->list);
 	p->flags = SWP_USED;
-	p->next = -1;
 	spin_unlock(&swap_lock);
 	spin_lock_init(&p->lock);
 

Signature · 1 line

1.8.3.1

Quoted 102 lines

mm/frontswap.c +2 -2

@@ -366,7 +361,7 @@ static int __frontswap_unuse_pages(unsigned long total, unsigned long *unused,
 		}
 		vm_unacct_memory(pages);
 		*unused = pages_to_unuse;
-		*swapid = type;
+		*swapid = si->type;
 		ret = 0;
 		break;
 	}

@@ -413,7 +408,7 @@ void frontswap_shrink(unsigned long target_pages)
 	/*
 	 * we don't want to hold swap_lock while doing a very
 	 * lengthy try_to_unuse, but swap_list may change
-	 * so restart scan from swap_list.head each time
+	 * so restart scan from swap_list_head each time
 	 */
 	spin_lock(&swap_lock);
 	ret = __frontswap_shrink(target_pages, &pages_to_unuse, &type);

mm/swapfile.c +10 -41

index 4a7f7e6..b958645 100644
@@ -51,14 +51,14 @@ atomic_long_t nr_swap_pages;
 /* protected with swap_lock. reading in vm_swap_full() doesn't need lock */
 long total_swap_pages;
 static int least_priority;
-static atomic_t highest_priority_index = ATOMIC_INIT(-1);
 
 static const char Bad_file[] = "Bad swap file entry ";
 static const char Unused_file[] = "Unused swap file entry ";
 static const char Bad_offset[] = "Bad swap offset entry ";
 static const char Unused_offset[] = "Unused swap offset entry ";
 
-struct swap_list_t swap_list = {-1, -1};
+/* all active swap_info */
+LIST_HEAD(swap_list_head);
 
 struct swap_info_struct *swap_info[MAX_SWAPFILES];
 

@@ -640,66 +640,50 @@ no_page:
 
 swp_entry_t get_swap_page(void)
 {
-	struct swap_info_struct *si;
+	struct swap_info_struct *si, *next;
 	pgoff_t offset;
-	int type, next;
-	int wrapped = 0;
-	int hp_index;
+	struct list_head *tmp;
 
 	spin_lock(&swap_lock);
 	if (atomic_long_read(&nr_swap_pages) <= 0)
 		goto noswap;
 	atomic_long_dec(&nr_swap_pages);
 
-	for (type = swap_list.next; type >= 0 && wrapped < 2; type = next) {
-		hp_index = atomic_xchg(&highest_priority_index, -1);
-		/*
-		 * highest_priority_index records current highest priority swap
-		 * type which just frees swap entries. If its priority is
-		 * higher than that of swap_list.next swap type, we use it.  It
-		 * isn't protected by swap_lock, so it can be an invalid value
-		 * if the corresponding swap type is swapoff. We double check
-		 * the flags here. It's even possible the swap type is swapoff
-		 * and swapon again and its priority is changed. In such rare
-		 * case, low prority swap type might be used, but eventually
-		 * high priority swap will be used after several rounds of
-		 * swap.
-		 */
-		if (hp_index != -1 && hp_index != type &&
-		    swap_info[type]->prio < swap_info[hp_index]->prio &&
-		    (swap_info[hp_index]->flags & SWP_WRITEOK)) {
-			type = hp_index;
-			swap_list.next = type;
-		}
-
-		si = swap_info[type];
-		next = si->next;
-		if (next < 0 ||
-		    (!wrapped && si->prio != swap_info[next]->prio)) {
-			next = swap_list.head;
-			wrapped++;
-		}
-
+	list_for_each(tmp, &swap_list_head) {
+		si = list_entry(tmp, typeof(*si), list);
 		spin_lock(&si->lock);
-		if (!si->highest_bit) {
-			spin_unlock(&si->lock);
-			continue;
-		}
-		if (!(si->flags & SWP_WRITEOK)) {
+		if (!si->highest_bit || !(si->flags & SWP_WRITEOK)) {
 			spin_unlock(&si->lock);
 			continue;
 		}
 
-		swap_list.next = next;
+		/*
+		 * rotate the current swap_info that we're going to use
+		 * to after any other swap_info that have the same prio,

mm/swapfile.c no_page: · line 672

Quoted 10 lines

mm/swapfile.c +9 -0

+		 * so that all equal-priority swap_info get used equally
+		 */
+		next = si;
+		list_for_each_entry_continue(next, &swap_list_head, list) {
+			if (si->prio != next->prio)
+				break;
+			list_rotate_left(&si->list);
+			next = si;
+		}
 

The list manipulations will be a lot of cache writes as the list is shuffled around. On slow storage I do not think this will be noticable but it may be noticable on faster swap devices that are SSD based. I've added Shaohua Li to the cc as he has been concerned with the performance of swap in the past. Shaohua, can you run this patchset through any of your test cases with the addition that multiple swap files are used to see if the cache writes are noticable? You'll need multiple swap files, some of which are at equal priority so the list shuffling logic is triggered.

Quoted 113 lines · Mel Gorman

Quoted 102 lines

mm/frontswap.c +2 -2

@@ -366,7 +361,7 @@ static int __frontswap_unuse_pages(unsigned long total, unsigned long *unused,
 		}
 		vm_unacct_memory(pages);
 		*unused = pages_to_unuse;
-		*swapid = type;
+		*swapid = si->type;
 		ret = 0;
 		break;
 	}

@@ -413,7 +408,7 @@ void frontswap_shrink(unsigned long target_pages)
 	/*
 	 * we don't want to hold swap_lock while doing a very
 	 * lengthy try_to_unuse, but swap_list may change
-	 * so restart scan from swap_list.head each time
+	 * so restart scan from swap_list_head each time
 	 */
 	spin_lock(&swap_lock);
 	ret = __frontswap_shrink(target_pages, &pages_to_unuse, &type);

mm/swapfile.c +10 -41

index 4a7f7e6..b958645 100644
@@ -51,14 +51,14 @@ atomic_long_t nr_swap_pages;
 /* protected with swap_lock. reading in vm_swap_full() doesn't need lock */
 long total_swap_pages;
 static int least_priority;
-static atomic_t highest_priority_index = ATOMIC_INIT(-1);
 
 static const char Bad_file[] = "Bad swap file entry ";
 static const char Unused_file[] = "Unused swap file entry ";
 static const char Bad_offset[] = "Bad swap offset entry ";
 static const char Unused_offset[] = "Unused swap offset entry ";
 
-struct swap_list_t swap_list = {-1, -1};
+/* all active swap_info */
+LIST_HEAD(swap_list_head);
 
 struct swap_info_struct *swap_info[MAX_SWAPFILES];
 

@@ -640,66 +640,50 @@ no_page:
 
 swp_entry_t get_swap_page(void)
 {
-	struct swap_info_struct *si;
+	struct swap_info_struct *si, *next;
 	pgoff_t offset;
-	int type, next;
-	int wrapped = 0;
-	int hp_index;
+	struct list_head *tmp;
 
 	spin_lock(&swap_lock);
 	if (atomic_long_read(&nr_swap_pages) <= 0)
 		goto noswap;
 	atomic_long_dec(&nr_swap_pages);
 
-	for (type = swap_list.next; type >= 0 && wrapped < 2; type = next) {
-		hp_index = atomic_xchg(&highest_priority_index, -1);
-		/*
-		 * highest_priority_index records current highest priority swap
-		 * type which just frees swap entries. If its priority is
-		 * higher than that of swap_list.next swap type, we use it.  It
-		 * isn't protected by swap_lock, so it can be an invalid value
-		 * if the corresponding swap type is swapoff. We double check
-		 * the flags here. It's even possible the swap type is swapoff
-		 * and swapon again and its priority is changed. In such rare
-		 * case, low prority swap type might be used, but eventually
-		 * high priority swap will be used after several rounds of
-		 * swap.
-		 */
-		if (hp_index != -1 && hp_index != type &&
-		    swap_info[type]->prio < swap_info[hp_index]->prio &&
-		    (swap_info[hp_index]->flags & SWP_WRITEOK)) {
-			type = hp_index;
-			swap_list.next = type;
-		}
-
-		si = swap_info[type];
-		next = si->next;
-		if (next < 0 ||
-		    (!wrapped && si->prio != swap_info[next]->prio)) {
-			next = swap_list.head;
-			wrapped++;
-		}
-
+	list_for_each(tmp, &swap_list_head) {
+		si = list_entry(tmp, typeof(*si), list);
 		spin_lock(&si->lock);
-		if (!si->highest_bit) {
-			spin_unlock(&si->lock);
-			continue;
-		}
-		if (!(si->flags & SWP_WRITEOK)) {
+		if (!si->highest_bit || !(si->flags & SWP_WRITEOK)) {
 			spin_unlock(&si->lock);
 			continue;
 		}
 
-		swap_list.next = next;
+		/*
+		 * rotate the current swap_info that we're going to use
+		 * to after any other swap_info that have the same prio,

mm/swapfile.c no_page: · line 672

Quoted 10 lines

mm/swapfile.c +9 -0

+		 * so that all equal-priority swap_info get used equally
+		 */
+		next = si;
+		list_for_each_entry_continue(next, &swap_list_head, list) {
+			if (si->prio != next->prio)
+				break;
+			list_rotate_left(&si->list);
+			next = si;
+		}
 

Quoted 8 lines

The list manipulations will be a lot of cache writes as the list is shuffled around. On slow storage I do not think this will be noticable but it may be noticable on faster swap devices that are SSD based. I've added Shaohua Li to the cc as he has been concerned with the performance of swap in the past. Shaohua, can you run this patchset through any of your test cases with the addition that multiple swap files are used to see if the cache writes are noticable? You'll need multiple swap files, some of which are at equal priority so the list shuffling logic is triggered.

get_swap_page isn't hot so far (and we hold the swap_lock, which isn't contended), guess it's because other problems hide it, for example tlb flush overhead.

Quoted 87 lines · Dan Streetman

Replace the singly-linked list tracking active, i.e. swapon'ed, swap_info_struct entries with a doubly-linked list using struct list_heads. Simplify the logic iterating and manipulating the list of entries, especially get_swap_page(), by using standard list_head functions, and removing the highest priority iteration logic.

The change fixes the bug:
https://lkml.org/lkml/2014/2/13/181
in which different priority swap entries after the highest priority entry are incorrectly used equally in pairs. The swap behavior is now as advertised, i.e. different priority swap entries are used in order, and equal priority swap targets are used concurrently.

Signed-off-by Dan Streetman <[email protected]>

---
 include/linux/swap.h     |   7 +--
 include/linux/swapfile.h |   2 +-
 mm/frontswap.c           |  13 ++--
 mm/swapfile.c            | 156 +++++++++++++++++------------------------------
 4 files changed, 63 insertions(+), 115 deletions(-)

include/linux/swap.h +1 -6

index 3507115..96662d8 100644
@@ -214,8 +214,8 @@ struct percpu_cluster {
 struct swap_info_struct {
      unsigned long   flags;          /* SWP_USED etc: see above */
      signed short    prio;           /* swap priority of this type */
+     struct list_head list;          /* entry in swap list */
      signed char     type;           /* strange name for an index */
-     signed char     next;           /* next type on the swap list */
      unsigned int    max;            /* extent of the swap_map */
      unsigned char *swap_map;        /* vmalloc'ed array of usage counts */
      struct swap_cluster_info *cluster_info; /* cluster info. Only for SSD */

@@ -255,11 +255,6 @@ struct swap_info_struct {
      struct swap_cluster_info discard_cluster_tail; /* list tail of discard clusters */
 };
 
-struct swap_list_t {
-     int head;       /* head of priority-ordered swapfile list */
-     int next;       /* swapfile to be used next */
-};
-
 /* linux/mm/workingset.c */
 void *workingset_eviction(struct address_space *mapping, struct page *page);
 bool workingset_refault(void *shadow);

include/linux/swapfile.h +1 -1

index e282624..2eab382 100644
@@ -6,7 +6,7 @@
  * want to expose them to the dozens of source files that include swap.h
  */
 extern spinlock_t swap_lock;
-extern struct swap_list_t swap_list;
+extern struct list_head swap_list_head;
 extern struct swap_info_struct *swap_info[];
 extern int try_to_unuse(unsigned int, bool, unsigned long);
 

mm/frontswap.c +1 -5

index 1b24bdc..fae1160 100644
@@ -327,15 +327,12 @@ EXPORT_SYMBOL(__frontswap_invalidate_area);
 
 static unsigned long __frontswap_curr_pages(void)
 {
-     int type;
      unsigned long totalpages = 0;
      struct swap_info_struct *si = NULL;
 
      assert_spin_locked(&swap_lock);
-     for (type = swap_list.head; type >= 0; type = si->next) {
-             si = swap_info[type];
+     list_for_each_entry(si, &swap_list_head, list)
              totalpages += atomic_read(&si->frontswap_pages);
-     }
      return totalpages;
 }
 

@@ -347,11 +344,9 @@ static int __frontswap_unuse_pages(unsigned long total, unsigned long *unused,
      int si_frontswap_pages;
      unsigned long total_pages_to_unuse = total;
      unsigned long pages = 0, pages_to_unuse = 0;
-     int type;
 

mm/frontswap.c static int __frontswap_unuse_pages(unsigned long total, unsigned long *unused, · line 352

Quoted 7 lines

mm/frontswap.c +1 -2

      assert_spin_locked(&swap_lock);
-     for (type = swap_list.head; type >= 0; type = si->next) {
-             si = swap_info[type];
+     list_for_each_entry(si, &swap_list_head, list) {
              si_frontswap_pages = atomic_read(&si->frontswap_pages);
              if (total_pages_to_unuse < si_frontswap_pages) {
                      pages = pages_to_unuse = total_pages_to_unuse;

The frontswap shrink code looks suspicious. If the target is smaller than the total number of frontswap pages then it does nothing. The callers appear to get this right at least. Similarly, if the first swapfile has fewer frontswap pages than the target then it does not unuse the target number of pages because it only handles one swap file. It's outside the scope of your patch to address this or wonder if xen balloon driver is really using it the way it's expected.

The old code scanned the files in priority order. Superficially this does not appear to but it actually does because you add the swap files to the list in priority order during swapon. If you do another revision it's worth adding a comment above swap_list_head that the list is ordered by priority and protected by the swap_lock.

Quoted 103 lines

mm/frontswap.c +2 -2

@@ -366,7 +361,7 @@ static int __frontswap_unuse_pages(unsigned long total, unsigned long *unused,
              }
              vm_unacct_memory(pages);
              *unused = pages_to_unuse;
-             *swapid = type;
+             *swapid = si->type;
              ret = 0;
              break;
      }

@@ -413,7 +408,7 @@ void frontswap_shrink(unsigned long target_pages)
      /*
       * we don't want to hold swap_lock while doing a very
       * lengthy try_to_unuse, but swap_list may change
-      * so restart scan from swap_list.head each time
+      * so restart scan from swap_list_head each time
       */
      spin_lock(&swap_lock);
      ret = __frontswap_shrink(target_pages, &pages_to_unuse, &type);

mm/swapfile.c +10 -41

index 4a7f7e6..b958645 100644
@@ -51,14 +51,14 @@ atomic_long_t nr_swap_pages;
 /* protected with swap_lock. reading in vm_swap_full() doesn't need lock */
 long total_swap_pages;
 static int least_priority;
-static atomic_t highest_priority_index = ATOMIC_INIT(-1);
 
 static const char Bad_file[] = "Bad swap file entry ";
 static const char Unused_file[] = "Unused swap file entry ";
 static const char Bad_offset[] = "Bad swap offset entry ";
 static const char Unused_offset[] = "Unused swap offset entry ";
 
-struct swap_list_t swap_list = {-1, -1};
+/* all active swap_info */
+LIST_HEAD(swap_list_head);
 
 struct swap_info_struct *swap_info[MAX_SWAPFILES];
 

@@ -640,66 +640,50 @@ no_page:
 
 swp_entry_t get_swap_page(void)
 {
-     struct swap_info_struct *si;
+     struct swap_info_struct *si, *next;
      pgoff_t offset;
-     int type, next;
-     int wrapped = 0;
-     int hp_index;
+     struct list_head *tmp;
 
      spin_lock(&swap_lock);
      if (atomic_long_read(&nr_swap_pages) <= 0)
              goto noswap;
      atomic_long_dec(&nr_swap_pages);
 
-     for (type = swap_list.next; type >= 0 && wrapped < 2; type = next) {
-             hp_index = atomic_xchg(&highest_priority_index, -1);
-             /*
-              * highest_priority_index records current highest priority swap
-              * type which just frees swap entries. If its priority is
-              * higher than that of swap_list.next swap type, we use it.  It
-              * isn't protected by swap_lock, so it can be an invalid value
-              * if the corresponding swap type is swapoff. We double check
-              * the flags here. It's even possible the swap type is swapoff
-              * and swapon again and its priority is changed. In such rare
-              * case, low prority swap type might be used, but eventually
-              * high priority swap will be used after several rounds of
-              * swap.
-              */
-             if (hp_index != -1 && hp_index != type &&
-                 swap_info[type]->prio < swap_info[hp_index]->prio &&
-                 (swap_info[hp_index]->flags & SWP_WRITEOK)) {
-                     type = hp_index;
-                     swap_list.next = type;
-             }
-
-             si = swap_info[type];
-             next = si->next;
-             if (next < 0 ||
-                 (!wrapped && si->prio != swap_info[next]->prio)) {
-                     next = swap_list.head;
-                     wrapped++;
-             }
-
+     list_for_each(tmp, &swap_list_head) {
+             si = list_entry(tmp, typeof(*si), list);
              spin_lock(&si->lock);
-             if (!si->highest_bit) {
-                     spin_unlock(&si->lock);
-                     continue;
-             }
-             if (!(si->flags & SWP_WRITEOK)) {
+             if (!si->highest_bit || !(si->flags & SWP_WRITEOK)) {
                      spin_unlock(&si->lock);
                      continue;
              }
 
-             swap_list.next = next;
+             /*
+              * rotate the current swap_info that we're going to use
+              * to after any other swap_info that have the same prio,

mm/swapfile.c no_page: · line 672

Quoted 10 lines

mm/swapfile.c +9 -0

+              * so that all equal-priority swap_info get used equally
+              */
+             next = si;
+             list_for_each_entry_continue(next, &swap_list_head, list) {
+                     if (si->prio != next->prio)
+                             break;
+                     list_rotate_left(&si->list);
+                     next = si;
+             }
 

The list manipulations will be a lot of cache writes as the list is shuffled around. On slow storage I do not think this will be noticable but it may be noticable on faster swap devices that are SSD based. I've added Shaohua Li to the cc as he has been concerned with the performance of swap in the past. Shaohua, can you run this patchset through any of your test cases with the addition that multiple swap files are used to see if the cache writes are noticable? You'll need multiple swap files, some of which are at equal priority so the list shuffling logic is triggered.

Quoted 8 lines

mm/swapfile.c +1 -1

              spin_unlock(&swap_lock);
              /* This is called for allocating swap entry for cache */
              offset = scan_swap_map(si, SWAP_HAS_CACHE);
              spin_unlock(&si->lock);
              if (offset)
-                     return swp_entry(type, offset);
+                     return swp_entry(si->type, offset);

mm/swapfile.c no_page: · line 687

Quoted 10 lines

mm/swapfile.c +7 -1

              spin_lock(&swap_lock);
-             next = swap_list.next;
+             /*
+              * shouldn't really have got here, but for some reason the
+              * scan_swap_map came back empty for this swap_info.
+              * Since we dropped the swap_lock, there may now be
+              * non-full higher prio swap_infos; let's start over.
+              */
+             tmp = &swap_list_head;
      }

Has this ever triggered? The number of swap pages was examined under the swap lock so no other process should have been iterating through the swap files. Once a candidate was found, the si lock was acquired for the swap scan map so nothing else should have raced with it.

Quoted 61 lines

mm/swapfile.c +4 -29

      atomic_long_inc(&nr_swap_pages);

@@ -766,27 +750,6 @@ out:
      return NULL;
 }
 
-/*
- * This swap type frees swap entry, check if it is the highest priority swap
- * type which just frees swap entry. get_swap_page() uses
- * highest_priority_index to search highest priority swap type. The
- * swap_info_struct.lock can't protect us if there are multiple swap types
- * active, so we use atomic_cmpxchg.
- */
-static void set_highest_priority_index(int type)
-{
-     int old_hp_index, new_hp_index;
-
-     do {
-             old_hp_index = atomic_read(&highest_priority_index);
-             if (old_hp_index != -1 &&
-                     swap_info[old_hp_index]->prio >= swap_info[type]->prio)
-                     break;
-             new_hp_index = type;
-     } while (atomic_cmpxchg(&highest_priority_index,
-             old_hp_index, new_hp_index) != old_hp_index);
-}
-
 static unsigned char swap_entry_free(struct swap_info_struct *p,
                                   swp_entry_t entry, unsigned char usage)
 {

@@ -830,7 +793,6 @@ static unsigned char swap_entry_free(struct swap_info_struct *p,
                      p->lowest_bit = offset;
              if (offset > p->highest_bit)
                      p->highest_bit = offset;
-             set_highest_priority_index(p->type);
              atomic_long_inc(&nr_swap_pages);
              p->inuse_pages--;
              frontswap_invalidate_page(p->type, offset);

@@ -1765,7 +1727,7 @@ static void _enable_swap_info(struct swap_info_struct *p, int prio,
                              unsigned char *swap_map,
                              struct swap_cluster_info *cluster_info)
 {
-     int i, prev;
+     struct swap_info_struct *si;
 
      if (prio >= 0)
              p->prio = prio;

@@ -1777,18 +1739,21 @@ static void _enable_swap_info(struct swap_info_struct *p, int prio,
      atomic_long_add(p->pages, &nr_swap_pages);
      total_swap_pages += p->pages;
 
-     /* insert swap space into swap_list: */
-     prev = -1;
-     for (i = swap_list.head; i >= 0; i = swap_info[i]->next) {
-             if (p->prio >= swap_info[i]->prio)
-                     break;
-             prev = i;
+     assert_spin_locked(&swap_lock);
+     BUG_ON(!list_empty(&p->list));
+     /* insert into swap list: */

mm/swapfile.c static void _enable_swap_info(struct swap_info_struct *p, int prio, · line 1749

Quoted 5 lines

mm/swapfile.c +5 -0

+     list_for_each_entry(si, &swap_list_head, list) {
+             if (p->prio >= si->prio) {
+                     list_add_tail(&p->list, &si->list);
+                     return;
+             }

An additional comment saying that it must be priority ordered for get_swap_page wouldn't kill.

Quoted 112 lines

mm/swapfile.c +21 -27

      }
-     p->next = i;
-     if (prev < 0)
-             swap_list.head = swap_list.next = p->type;
-     else
-             swap_info[prev]->next = p->type;
+     /*
+      * this covers two cases:
+      * 1) p->prio is less than all existing prio
+      * 2) the swap list is empty
+      */
+     list_add_tail(&p->list, &swap_list_head);
 }
 
 static void enable_swap_info(struct swap_info_struct *p, int prio,

@@ -1823,8 +1788,7 @@ SYSCALL_DEFINE1(swapoff, const char __user *, specialfile)
      struct address_space *mapping;
      struct inode *inode;
      struct filename *pathname;
-     int i, type, prev;
-     int err;
+     int err, found = 0;
      unsigned int old_block_size;
 
      if (!capable(CAP_SYS_ADMIN))

@@ -1842,17 +1806,16 @@ SYSCALL_DEFINE1(swapoff, const char __user *, specialfile)
              goto out;
 
      mapping = victim->f_mapping;
-     prev = -1;
      spin_lock(&swap_lock);
-     for (type = swap_list.head; type >= 0; type = swap_info[type]->next) {
-             p = swap_info[type];
+     list_for_each_entry(p, &swap_list_head, list) {
              if (p->flags & SWP_WRITEOK) {
-                     if (p->swap_file->f_mapping == mapping)
+                     if (p->swap_file->f_mapping == mapping) {
+                             found = 1;
                              break;
+                     }
              }
-             prev = type;
      }
-     if (type < 0) {
+     if (!found) {
              err = -EINVAL;
              spin_unlock(&swap_lock);
              goto out_dput;

@@ -1864,20 +1827,15 @@ SYSCALL_DEFINE1(swapoff, const char __user *, specialfile)
              spin_unlock(&swap_lock);
              goto out_dput;
      }
-     if (prev < 0)
-             swap_list.head = p->next;
-     else
-             swap_info[prev]->next = p->next;
-     if (type == swap_list.next) {
-             /* just pick something that's safe... */
-             swap_list.next = swap_list.head;
-     }
      spin_lock(&p->lock);
      if (p->prio < 0) {
-             for (i = p->next; i >= 0; i = swap_info[i]->next)
-                     swap_info[i]->prio = p->prio--;
+             struct swap_info_struct *si = p;
+             list_for_each_entry_continue(si, &swap_list_head, list) {
+                     si->prio++;
+             }
              least_priority++;
      }
+     list_del_init(&p->list);
      atomic_long_sub(p->pages, &nr_swap_pages);
      total_swap_pages -= p->pages;
      p->flags &= ~SWP_WRITEOK;

@@ -1885,7 +1843,7 @@ SYSCALL_DEFINE1(swapoff, const char __user *, specialfile)
      spin_unlock(&swap_lock);
 
      set_current_oom_origin();
-     err = try_to_unuse(type, false, 0); /* force all pages to be unused */
+     err = try_to_unuse(p->type, false, 0); /* force unuse all pages */
      clear_current_oom_origin();
 
      if (err) {

@@ -1926,7 +1884,7 @@ SYSCALL_DEFINE1(swapoff, const char __user *, specialfile)
      frontswap_map = frontswap_map_get(p);
      spin_unlock(&p->lock);
      spin_unlock(&swap_lock);
-     frontswap_invalidate_area(type);
+     frontswap_invalidate_area(p->type);
      frontswap_map_set(p, NULL);
      mutex_unlock(&swapon_mutex);
      free_percpu(p->percpu_cluster);

@@ -1935,7 +1893,7 @@ SYSCALL_DEFINE1(swapoff, const char __user *, specialfile)
      vfree(cluster_info);
      vfree(frontswap_map);
      /* Destroy swap account information */
-     swap_cgroup_swapoff(type);
+     swap_cgroup_swapoff(p->type);
 
      inode = mapping->host;
      if (S_ISBLK(inode->i_mode)) {

@@ -2142,8 +2100,8 @@ static struct swap_info_struct *alloc_swap_info(void)
               */
      }
      INIT_LIST_HEAD(&p->first_swap_extent.list);
+     INIT_LIST_HEAD(&p->list);
      p->flags = SWP_USED;
-     p->next = -1;
      spin_unlock(&swap_lock);
      spin_lock_init(&p->lock);
 

Quoted 3 lines

--
1.8.3.1

--
Mel Gorman
SUSE Labs

Quoted 88 lines · Mel Gorman

Quoted 87 lines · Dan Streetman

Replace the singly-linked list tracking active, i.e. swapon'ed, swap_info_struct entries with a doubly-linked list using struct list_heads. Simplify the logic iterating and manipulating the list of entries, especially get_swap_page(), by using standard list_head functions, and removing the highest priority iteration logic.

The change fixes the bug:
https://lkml.org/lkml/2014/2/13/181
in which different priority swap entries after the highest priority entry are incorrectly used equally in pairs. The swap behavior is now as advertised, i.e. different priority swap entries are used in order, and equal priority swap targets are used concurrently.

Signed-off-by Dan Streetman <[email protected]>

---
 include/linux/swap.h     |   7 +--
 include/linux/swapfile.h |   2 +-
 mm/frontswap.c           |  13 ++--
 mm/swapfile.c            | 156 +++++++++++++++++------------------------------
 4 files changed, 63 insertions(+), 115 deletions(-)

include/linux/swap.h +1 -6

index 3507115..96662d8 100644
@@ -214,8 +214,8 @@ struct percpu_cluster {
 struct swap_info_struct {
      unsigned long   flags;          /* SWP_USED etc: see above */
      signed short    prio;           /* swap priority of this type */
+     struct list_head list;          /* entry in swap list */
      signed char     type;           /* strange name for an index */
-     signed char     next;           /* next type on the swap list */
      unsigned int    max;            /* extent of the swap_map */
      unsigned char *swap_map;        /* vmalloc'ed array of usage counts */
      struct swap_cluster_info *cluster_info; /* cluster info. Only for SSD */

@@ -255,11 +255,6 @@ struct swap_info_struct {
      struct swap_cluster_info discard_cluster_tail; /* list tail of discard clusters */
 };
 
-struct swap_list_t {
-     int head;       /* head of priority-ordered swapfile list */
-     int next;       /* swapfile to be used next */
-};
-
 /* linux/mm/workingset.c */
 void *workingset_eviction(struct address_space *mapping, struct page *page);
 bool workingset_refault(void *shadow);

include/linux/swapfile.h +1 -1

index e282624..2eab382 100644
@@ -6,7 +6,7 @@
  * want to expose them to the dozens of source files that include swap.h
  */
 extern spinlock_t swap_lock;
-extern struct swap_list_t swap_list;
+extern struct list_head swap_list_head;
 extern struct swap_info_struct *swap_info[];
 extern int try_to_unuse(unsigned int, bool, unsigned long);
 

mm/frontswap.c +1 -5

index 1b24bdc..fae1160 100644
@@ -327,15 +327,12 @@ EXPORT_SYMBOL(__frontswap_invalidate_area);
 
 static unsigned long __frontswap_curr_pages(void)
 {
-     int type;
      unsigned long totalpages = 0;
      struct swap_info_struct *si = NULL;
 
      assert_spin_locked(&swap_lock);
-     for (type = swap_list.head; type >= 0; type = si->next) {
-             si = swap_info[type];
+     list_for_each_entry(si, &swap_list_head, list)
              totalpages += atomic_read(&si->frontswap_pages);
-     }
      return totalpages;
 }
 

@@ -347,11 +344,9 @@ static int __frontswap_unuse_pages(unsigned long total, unsigned long *unused,
      int si_frontswap_pages;
      unsigned long total_pages_to_unuse = total;
      unsigned long pages = 0, pages_to_unuse = 0;
-     int type;
 

Quoted 15 lines

mm/frontswap.c static int __frontswap_unuse_pages(unsigned long total, unsigned long *unused, · line 352

Quoted 7 lines

mm/frontswap.c +1 -2

      assert_spin_locked(&swap_lock);
-     for (type = swap_list.head; type >= 0; type = si->next) {
-             si = swap_info[type];
+     list_for_each_entry(si, &swap_list_head, list) {
              si_frontswap_pages = atomic_read(&si->frontswap_pages);
              if (total_pages_to_unuse < si_frontswap_pages) {
                      pages = pages_to_unuse = total_pages_to_unuse;

The frontswap shrink code looks suspicious. If the target is smaller than the total number of frontswap pages then it does nothing. The callers appear to get this right at least. Similarly, if the first swapfile has fewer frontswap pages than the target then it does not unuse the target number of pages because it only handles one swap file. It's outside the scope of your patch to address this or wonder if xen balloon driver is really using it the way it's expected.

I didn't look into the frontswap shrinking code, but I agree the existing logic there doesn't look right. I'll review frontswap in more detail to see if it needs changing here, unless anyone else gets it to first :-)

And as you said, it's outside the scope of this particular patch.

Quoted 6 lines

The old code scanned the files in priority order. Superficially this does not appear to but it actually does because you add the swap files to the list in priority order during swapon. If you do another revision it's worth adding a comment above swap_list_head that the list is ordered by priority and protected by the swap_lock.

Yep you're right, I will add a comment to make clear it's also priority ordered, and why. The only reason it needs to be priority ordered is because swapoff has to adjust the auto-priority of any following swap_info_structs when one is removed, that has an automatically assigned (i.e. negative) priority.

Quoted 114 lines

Quoted 103 lines

mm/frontswap.c +2 -2

@@ -366,7 +361,7 @@ static int __frontswap_unuse_pages(unsigned long total, unsigned long *unused,
              }
              vm_unacct_memory(pages);
              *unused = pages_to_unuse;
-             *swapid = type;
+             *swapid = si->type;
              ret = 0;
              break;
      }

@@ -413,7 +408,7 @@ void frontswap_shrink(unsigned long target_pages)
      /*
       * we don't want to hold swap_lock while doing a very
       * lengthy try_to_unuse, but swap_list may change
-      * so restart scan from swap_list.head each time
+      * so restart scan from swap_list_head each time
       */
      spin_lock(&swap_lock);
      ret = __frontswap_shrink(target_pages, &pages_to_unuse, &type);

mm/swapfile.c +10 -41

index 4a7f7e6..b958645 100644
@@ -51,14 +51,14 @@ atomic_long_t nr_swap_pages;
 /* protected with swap_lock. reading in vm_swap_full() doesn't need lock */
 long total_swap_pages;
 static int least_priority;
-static atomic_t highest_priority_index = ATOMIC_INIT(-1);
 
 static const char Bad_file[] = "Bad swap file entry ";
 static const char Unused_file[] = "Unused swap file entry ";
 static const char Bad_offset[] = "Bad swap offset entry ";
 static const char Unused_offset[] = "Unused swap offset entry ";
 
-struct swap_list_t swap_list = {-1, -1};
+/* all active swap_info */
+LIST_HEAD(swap_list_head);
 
 struct swap_info_struct *swap_info[MAX_SWAPFILES];
 

@@ -640,66 +640,50 @@ no_page:
 
 swp_entry_t get_swap_page(void)
 {
-     struct swap_info_struct *si;
+     struct swap_info_struct *si, *next;
      pgoff_t offset;
-     int type, next;
-     int wrapped = 0;
-     int hp_index;
+     struct list_head *tmp;
 
      spin_lock(&swap_lock);
      if (atomic_long_read(&nr_swap_pages) <= 0)
              goto noswap;
      atomic_long_dec(&nr_swap_pages);
 
-     for (type = swap_list.next; type >= 0 && wrapped < 2; type = next) {
-             hp_index = atomic_xchg(&highest_priority_index, -1);
-             /*
-              * highest_priority_index records current highest priority swap
-              * type which just frees swap entries. If its priority is
-              * higher than that of swap_list.next swap type, we use it.  It
-              * isn't protected by swap_lock, so it can be an invalid value
-              * if the corresponding swap type is swapoff. We double check
-              * the flags here. It's even possible the swap type is swapoff
-              * and swapon again and its priority is changed. In such rare
-              * case, low prority swap type might be used, but eventually
-              * high priority swap will be used after several rounds of
-              * swap.
-              */
-             if (hp_index != -1 && hp_index != type &&
-                 swap_info[type]->prio < swap_info[hp_index]->prio &&
-                 (swap_info[hp_index]->flags & SWP_WRITEOK)) {
-                     type = hp_index;
-                     swap_list.next = type;
-             }
-
-             si = swap_info[type];
-             next = si->next;
-             if (next < 0 ||
-                 (!wrapped && si->prio != swap_info[next]->prio)) {
-                     next = swap_list.head;
-                     wrapped++;
-             }
-
+     list_for_each(tmp, &swap_list_head) {
+             si = list_entry(tmp, typeof(*si), list);
              spin_lock(&si->lock);
-             if (!si->highest_bit) {
-                     spin_unlock(&si->lock);
-                     continue;
-             }
-             if (!(si->flags & SWP_WRITEOK)) {
+             if (!si->highest_bit || !(si->flags & SWP_WRITEOK)) {
                      spin_unlock(&si->lock);
                      continue;
              }
 
-             swap_list.next = next;
+             /*
+              * rotate the current swap_info that we're going to use
+              * to after any other swap_info that have the same prio,

mm/swapfile.c no_page: · line 672

Quoted 10 lines

mm/swapfile.c +9 -0

+              * so that all equal-priority swap_info get used equally
+              */
+             next = si;
+             list_for_each_entry_continue(next, &swap_list_head, list) {
+                     if (si->prio != next->prio)
+                             break;
+                     list_rotate_left(&si->list);
+                     next = si;
+             }
 

Quoted 8 lines

The list manipulations will be a lot of cache writes as the list is shuffled around. On slow storage I do not think this will be noticable but it may be noticable on faster swap devices that are SSD based. I've added Shaohua Li to the cc as he has been concerned with the performance of swap in the past. Shaohua, can you run this patchset through any of your test cases with the addition that multiple swap files are used to see if the cache writes are noticable? You'll need multiple swap files, some of which are at equal priority so the list shuffling logic is triggered.

One performance improvement could be instead of rotating the current entry past each following same-prio entry, just scan to the end of the same-prio entries and move the current entry there; that would skip the extra writes. Especially since this code will run for each get_swap_page(), no need for any unnecessary writes.

Quoted 19 lines

Quoted 8 lines

mm/swapfile.c +1 -1

              spin_unlock(&swap_lock);
              /* This is called for allocating swap entry for cache */
              offset = scan_swap_map(si, SWAP_HAS_CACHE);
              spin_unlock(&si->lock);
              if (offset)
-                     return swp_entry(type, offset);
+                     return swp_entry(si->type, offset);

mm/swapfile.c no_page: · line 687

Quoted 10 lines

mm/swapfile.c +7 -1

              spin_lock(&swap_lock);
-             next = swap_list.next;
+             /*
+              * shouldn't really have got here, but for some reason the
+              * scan_swap_map came back empty for this swap_info.
+              * Since we dropped the swap_lock, there may now be
+              * non-full higher prio swap_infos; let's start over.
+              */
+             tmp = &swap_list_head;
      }

Quoted 4 lines

Has this ever triggered? The number of swap pages was examined under the swap lock so no other process should have been iterating through the swap files. Once a candidate was found, the si lock was acquired for the swap scan map so nothing else should have raced with it.

Well scan_swap_map() does drop the si->lock if it has any trouble at all finding an offset to use, so I think it's possible that for a nearly-full si multiple concurrent get_swap_page() calls could enter scan_swap_map() with the same si, only some of them actually get pages from the si and then the si becomes full, and the other threads in scan_swap_map() see it's full and exit in failure. I can update the code comment there to better indicate why it was reached, instead of just saying "we shouldn't have got here" :-)

It may also be worth trying to get a better indicator of "available" swap_info_structs for use in get_swap_page(), either by looking at something other than si->highest_bit and/or keeping the si out of the prio_list until it's actually available for use, not just has a single entry free. However, that probably won't be simple and might be better as a separate patch to the rest of these changes.

Quoted 61 lines

Quoted 61 lines

mm/swapfile.c +4 -29

      atomic_long_inc(&nr_swap_pages);

@@ -766,27 +750,6 @@ out:
      return NULL;
 }
 
-/*
- * This swap type frees swap entry, check if it is the highest priority swap
- * type which just frees swap entry. get_swap_page() uses
- * highest_priority_index to search highest priority swap type. The
- * swap_info_struct.lock can't protect us if there are multiple swap types
- * active, so we use atomic_cmpxchg.
- */
-static void set_highest_priority_index(int type)
-{
-     int old_hp_index, new_hp_index;
-
-     do {
-             old_hp_index = atomic_read(&highest_priority_index);
-             if (old_hp_index != -1 &&
-                     swap_info[old_hp_index]->prio >= swap_info[type]->prio)
-                     break;
-             new_hp_index = type;
-     } while (atomic_cmpxchg(&highest_priority_index,
-             old_hp_index, new_hp_index) != old_hp_index);
-}
-
 static unsigned char swap_entry_free(struct swap_info_struct *p,
                                   swp_entry_t entry, unsigned char usage)
 {

@@ -830,7 +793,6 @@ static unsigned char swap_entry_free(struct swap_info_struct *p,
                      p->lowest_bit = offset;
              if (offset > p->highest_bit)
                      p->highest_bit = offset;
-             set_highest_priority_index(p->type);
              atomic_long_inc(&nr_swap_pages);
              p->inuse_pages--;
              frontswap_invalidate_page(p->type, offset);

@@ -1765,7 +1727,7 @@ static void _enable_swap_info(struct swap_info_struct *p, int prio,
                              unsigned char *swap_map,
                              struct swap_cluster_info *cluster_info)
 {
-     int i, prev;
+     struct swap_info_struct *si;
 
      if (prio >= 0)
              p->prio = prio;

@@ -1777,18 +1739,21 @@ static void _enable_swap_info(struct swap_info_struct *p, int prio,
      atomic_long_add(p->pages, &nr_swap_pages);
      total_swap_pages += p->pages;
 
-     /* insert swap space into swap_list: */
-     prev = -1;
-     for (i = swap_list.head; i >= 0; i = swap_info[i]->next) {
-             if (p->prio >= swap_info[i]->prio)
-                     break;
-             prev = i;
+     assert_spin_locked(&swap_lock);
+     BUG_ON(!list_empty(&p->list));
+     /* insert into swap list: */

Quoted 8 lines

mm/swapfile.c static void _enable_swap_info(struct swap_info_struct *p, int prio, · line 1749

Quoted 5 lines

mm/swapfile.c +5 -0

+     list_for_each_entry(si, &swap_list_head, list) {
+             if (p->prio >= si->prio) {
+                     list_add_tail(&p->list, &si->list);
+                     return;
+             }

An additional comment saying that it must be priority ordered for get_swap_page wouldn't kill.

will do.

Quoted 112 lines

Quoted 112 lines

mm/swapfile.c +21 -27

      }
-     p->next = i;
-     if (prev < 0)
-             swap_list.head = swap_list.next = p->type;
-     else
-             swap_info[prev]->next = p->type;
+     /*
+      * this covers two cases:
+      * 1) p->prio is less than all existing prio
+      * 2) the swap list is empty
+      */
+     list_add_tail(&p->list, &swap_list_head);
 }
 
 static void enable_swap_info(struct swap_info_struct *p, int prio,

@@ -1823,8 +1788,7 @@ SYSCALL_DEFINE1(swapoff, const char __user *, specialfile)
      struct address_space *mapping;
      struct inode *inode;
      struct filename *pathname;
-     int i, type, prev;
-     int err;
+     int err, found = 0;
      unsigned int old_block_size;
 
      if (!capable(CAP_SYS_ADMIN))

@@ -1842,17 +1806,16 @@ SYSCALL_DEFINE1(swapoff, const char __user *, specialfile)
              goto out;
 
      mapping = victim->f_mapping;
-     prev = -1;
      spin_lock(&swap_lock);
-     for (type = swap_list.head; type >= 0; type = swap_info[type]->next) {
-             p = swap_info[type];
+     list_for_each_entry(p, &swap_list_head, list) {
              if (p->flags & SWP_WRITEOK) {
-                     if (p->swap_file->f_mapping == mapping)
+                     if (p->swap_file->f_mapping == mapping) {
+                             found = 1;
                              break;
+                     }
              }
-             prev = type;
      }
-     if (type < 0) {
+     if (!found) {
              err = -EINVAL;
              spin_unlock(&swap_lock);
              goto out_dput;

@@ -1864,20 +1827,15 @@ SYSCALL_DEFINE1(swapoff, const char __user *, specialfile)
              spin_unlock(&swap_lock);
              goto out_dput;
      }
-     if (prev < 0)
-             swap_list.head = p->next;
-     else
-             swap_info[prev]->next = p->next;
-     if (type == swap_list.next) {
-             /* just pick something that's safe... */
-             swap_list.next = swap_list.head;
-     }
      spin_lock(&p->lock);
      if (p->prio < 0) {
-             for (i = p->next; i >= 0; i = swap_info[i]->next)
-                     swap_info[i]->prio = p->prio--;
+             struct swap_info_struct *si = p;
+             list_for_each_entry_continue(si, &swap_list_head, list) {
+                     si->prio++;
+             }
              least_priority++;
      }
+     list_del_init(&p->list);
      atomic_long_sub(p->pages, &nr_swap_pages);
      total_swap_pages -= p->pages;
      p->flags &= ~SWP_WRITEOK;

@@ -1885,7 +1843,7 @@ SYSCALL_DEFINE1(swapoff, const char __user *, specialfile)
      spin_unlock(&swap_lock);
 
      set_current_oom_origin();
-     err = try_to_unuse(type, false, 0); /* force all pages to be unused */
+     err = try_to_unuse(p->type, false, 0); /* force unuse all pages */
      clear_current_oom_origin();
 
      if (err) {

@@ -1926,7 +1884,7 @@ SYSCALL_DEFINE1(swapoff, const char __user *, specialfile)
      frontswap_map = frontswap_map_get(p);
      spin_unlock(&p->lock);
      spin_unlock(&swap_lock);
-     frontswap_invalidate_area(type);
+     frontswap_invalidate_area(p->type);
      frontswap_map_set(p, NULL);
      mutex_unlock(&swapon_mutex);
      free_percpu(p->percpu_cluster);

@@ -1935,7 +1893,7 @@ SYSCALL_DEFINE1(swapoff, const char __user *, specialfile)
      vfree(cluster_info);
      vfree(frontswap_map);
      /* Destroy swap account information */
-     swap_cgroup_swapoff(type);
+     swap_cgroup_swapoff(p->type);
 
      inode = mapping->host;
      if (S_ISBLK(inode->i_mode)) {

@@ -2142,8 +2100,8 @@ static struct swap_info_struct *alloc_swap_info(void)
               */
      }
      INIT_LIST_HEAD(&p->first_swap_extent.list);
+     INIT_LIST_HEAD(&p->list);
      p->flags = SWP_USED;
-     p->next = -1;
      spin_unlock(&swap_lock);
      spin_lock_init(&p->lock);
 

Quoted 7 lines

Quoted 3 lines

--
1.8.3.1

--
Mel Gorman
SUSE Labs

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Quoted 2 lines · Dan Streetman

Quoted 1 line · Mel Gorman

On Sat, Apr 12, 2014 at 05:00:53PM -0400, Dan Streetman wrote:

Quoted 43 lines

Quoted 42 lines

Quoted 24 lines

mm/frontswap.c +1 -4

index 1b24bdc..fae1160 100644
@@ -327,15 +327,12 @@ EXPORT_SYMBOL(__frontswap_invalidate_area);
 
 static unsigned long __frontswap_curr_pages(void)
 {
-     int type;
      unsigned long totalpages = 0;
      struct swap_info_struct *si = NULL;
 
      assert_spin_locked(&swap_lock);
-     for (type = swap_list.head; type >= 0; type = si->next) {
-             si = swap_info[type];
+     list_for_each_entry(si, &swap_list_head, list)
              totalpages += atomic_read(&si->frontswap_pages);
-     }
      return totalpages;
 }
 

@@ -347,11 +344,9 @@ static int __frontswap_unuse_pages(unsigned long total, unsigned long *unused,
      int si_frontswap_pages;
      unsigned long total_pages_to_unuse = total;

mm/frontswap.c static int __frontswap_unuse_pages(unsigned long total, unsigned long *unused, · line 352

Quoted 10 lines

mm/frontswap.c +1 -3

      unsigned long pages = 0, pages_to_unuse = 0;
-     int type;
 
      assert_spin_locked(&swap_lock);
-     for (type = swap_list.head; type >= 0; type = si->next) {
-             si = swap_info[type];
+     list_for_each_entry(si, &swap_list_head, list) {
              si_frontswap_pages = atomic_read(&si->frontswap_pages);
              if (total_pages_to_unuse < si_frontswap_pages) {
                      pages = pages_to_unuse = total_pages_to_unuse;

The frontswap shrink code looks suspicious. If the target is smaller than the total number of frontswap pages then it does nothing. The callers appear to get this right at least. Similarly, if the first swapfile has fewer frontswap pages than the target then it does not unuse the target number of pages because it only handles one swap file. It's outside the scope of your patch to address this or wonder if xen balloon driver is really using it the way it's expected.

Quoted 5 lines

I didn't look into the frontswap shrinking code, but I agree the existing logic there doesn't look right. I'll review frontswap in more detail to see if it needs changing here, unless anyone else gets it to first :-)

FYI, I drop the frontswap_shrink code in a patch
see: https://lkml.org/lkml/2014/1/27/98

Quoted 3 lines · Weijie Yang

Quoted 2 lines · Dan Streetman

Quoted 1 line · Mel Gorman

On Sat, Apr 12, 2014 at 05:00:53PM -0400, Dan Streetman wrote:

<SNIP>

Quoted 27 lines

Quoted 27 lines

Quoted 27 lines

Quoted 27 lines

mm/frontswap.c +1 -5

index 1b24bdc..fae1160 100644
@@ -327,15 +327,12 @@ EXPORT_SYMBOL(__frontswap_invalidate_area);
 
 static unsigned long __frontswap_curr_pages(void)
 {
-     int type;
      unsigned long totalpages = 0;
      struct swap_info_struct *si = NULL;
 
      assert_spin_locked(&swap_lock);
-     for (type = swap_list.head; type >= 0; type = si->next) {
-             si = swap_info[type];
+     list_for_each_entry(si, &swap_list_head, list)
              totalpages += atomic_read(&si->frontswap_pages);
-     }
      return totalpages;
 }
 

@@ -347,11 +344,9 @@ static int __frontswap_unuse_pages(unsigned long total, unsigned long *unused,
      int si_frontswap_pages;
      unsigned long total_pages_to_unuse = total;
      unsigned long pages = 0, pages_to_unuse = 0;
-     int type;
 

Quoted 10 lines

Quoted 10 lines

Quoted 10 lines

mm/frontswap.c static int __frontswap_unuse_pages(unsigned long total, unsigned long *unused, · line 352

Quoted 7 lines

mm/frontswap.c +1 -2

      assert_spin_locked(&swap_lock);
-     for (type = swap_list.head; type >= 0; type = si->next) {
-             si = swap_info[type];
+     list_for_each_entry(si, &swap_list_head, list) {
              si_frontswap_pages = atomic_read(&si->frontswap_pages);
              if (total_pages_to_unuse < si_frontswap_pages) {
                      pages = pages_to_unuse = total_pages_to_unuse;

The frontswap shrink code looks suspicious. If the target is smaller than the total number of frontswap pages then it does nothing. The callers

Quoted 6 lines

Quoted 6 lines

Quoted 5 lines

appear to get this right at least. Similarly, if the first swapfile has fewer frontswap pages than the target then it does not unuse the target number of pages because it only handles one swap file. It's outside the scope of your patch to address this or wonder if xen balloon driver is really using it the way it's expected.

Quoted 8 lines

Quoted 5 lines

I didn't look into the frontswap shrinking code, but I agree the existing logic there doesn't look right. I'll review frontswap in more detail to see if it needs changing here, unless anyone else gets it to first :-)

FYI, I drop the frontswap_shrink code in a patch
see: https://lkml.org/lkml/2014/1/27/98

frontswap_shrink() is actually used (only) by drivers/xen/xen-selfballoon.c.

However, I completely agree with you that the backend should be doing the shrinking, not from a frontswap api. Forcing frontswap to shrink is backwards - xen-selfballoon appears to be assuming that xem/tmem is the only possible frontswap backend. It certainly doensn't make any sense for xen-selfballoon to force zswap to shrink itself, does it?

If xen-selfballoon wants to shrink its frontswap backend tmem, it should do that by telling tmem directly to shrink itself (which it looks like tmem would have to implement, just like zswap sends its LRU pages back to swapcache when it becomes full).

Quoted 3 lines · Weijie Yang

Quoted 2 lines · Dan Streetman

Quoted 1 line · Mel Gorman

On Sat, Apr 12, 2014 at 05:00:53PM -0400, Dan Streetman wrote:

<SNIP>

Quoted 27 lines

Quoted 27 lines

Quoted 27 lines

Quoted 27 lines

mm/frontswap.c +1 -5

index 1b24bdc..fae1160 100644
@@ -327,15 +327,12 @@ EXPORT_SYMBOL(__frontswap_invalidate_area);
 
 static unsigned long __frontswap_curr_pages(void)
 {
-     int type;
      unsigned long totalpages = 0;
      struct swap_info_struct *si = NULL;
 
      assert_spin_locked(&swap_lock);
-     for (type = swap_list.head; type >= 0; type = si->next) {
-             si = swap_info[type];
+     list_for_each_entry(si, &swap_list_head, list)
              totalpages += atomic_read(&si->frontswap_pages);
-     }
      return totalpages;
 }
 

@@ -347,11 +344,9 @@ static int __frontswap_unuse_pages(unsigned long total, unsigned long *unused,
      int si_frontswap_pages;
      unsigned long total_pages_to_unuse = total;
      unsigned long pages = 0, pages_to_unuse = 0;
-     int type;
 

Quoted 10 lines

Quoted 10 lines

Quoted 10 lines

mm/frontswap.c static int __frontswap_unuse_pages(unsigned long total, unsigned long *unused, · line 352

Quoted 7 lines

mm/frontswap.c +1 -2

      assert_spin_locked(&swap_lock);
-     for (type = swap_list.head; type >= 0; type = si->next) {
-             si = swap_info[type];
+     list_for_each_entry(si, &swap_list_head, list) {
              si_frontswap_pages = atomic_read(&si->frontswap_pages);
              if (total_pages_to_unuse < si_frontswap_pages) {
                      pages = pages_to_unuse = total_pages_to_unuse;

The frontswap shrink code looks suspicious. If the target is smaller than the total number of frontswap pages then it does nothing. The callers

Quoted 6 lines

Quoted 6 lines

Quoted 5 lines

appear to get this right at least. Similarly, if the first swapfile has fewer frontswap pages than the target then it does not unuse the target number of pages because it only handles one swap file. It's outside the scope of your patch to address this or wonder if xen balloon driver is really using it the way it's expected.

Quoted 8 lines

Quoted 5 lines

I didn't look into the frontswap shrinking code, but I agree the existing logic there doesn't look right. I'll review frontswap in more detail to see if it needs changing here, unless anyone else gets it to first :-)

FYI, I drop the frontswap_shrink code in a patch
see: https://lkml.org/lkml/2014/1/27/98

frontswap_shrink() is actually used (only) by drivers/xen/xen-selfballoon.c.

However, I completely agree with you that the backend should be doing the shrinking, not from a frontswap api. Forcing frontswap to shrink is backwards - xen-selfballoon appears to be assuming that xem/tmem is the only possible frontswap backend. It certainly doensn't make any sense for xen-selfballoon to force zswap to shrink itself, does it?

If xen-selfballoon wants to shrink its frontswap backend tmem, it should do that by telling tmem directly to shrink itself (which it looks like tmem would have to implement, just like zswap sends its LRU pages back to swapcache when it becomes full).

Quoted 32 lines · Dan Streetman

Quoted 3 lines · Weijie Yang

Quoted 2 lines · Dan Streetman

Quoted 1 line · Mel Gorman

On Sat, Apr 12, 2014 at 05:00:53PM -0400, Dan Streetman wrote:

<SNIP>

Quoted 27 lines

Quoted 27 lines

Quoted 27 lines

Quoted 27 lines

mm/frontswap.c +1 -5

index 1b24bdc..fae1160 100644
@@ -327,15 +327,12 @@ EXPORT_SYMBOL(__frontswap_invalidate_area);
 
 static unsigned long __frontswap_curr_pages(void)
 {
-     int type;
      unsigned long totalpages = 0;
      struct swap_info_struct *si = NULL;
 
      assert_spin_locked(&swap_lock);
-     for (type = swap_list.head; type >= 0; type = si->next) {
-             si = swap_info[type];
+     list_for_each_entry(si, &swap_list_head, list)
              totalpages += atomic_read(&si->frontswap_pages);
-     }
      return totalpages;
 }
 

@@ -347,11 +344,9 @@ static int __frontswap_unuse_pages(unsigned long total, unsigned long *unused,
      int si_frontswap_pages;
      unsigned long total_pages_to_unuse = total;
      unsigned long pages = 0, pages_to_unuse = 0;
-     int type;
 

Quoted 10 lines

Quoted 10 lines

Quoted 10 lines

Quoted 10 lines

mm/frontswap.c static int __frontswap_unuse_pages(unsigned long total, unsigned long *unused, · line 352

Quoted 7 lines

mm/frontswap.c +1 -2

      assert_spin_locked(&swap_lock);
-     for (type = swap_list.head; type >= 0; type = si->next) {
-             si = swap_info[type];
+     list_for_each_entry(si, &swap_list_head, list) {
              si_frontswap_pages = atomic_read(&si->frontswap_pages);
              if (total_pages_to_unuse < si_frontswap_pages) {
                      pages = pages_to_unuse = total_pages_to_unuse;

The frontswap shrink code looks suspicious. If the target is smaller than the total number of frontswap pages then it does nothing. The callers

__frontswap_unuse_pages() is called only to get the correct value of pages_to_unuse which will pass to try_to_unuse(), perhaps we should rename it to __frontswap_unuse_pages_nr()..

------

ret = __frontswap_shrink(target_pages, &pages_to_unuse, &type);
        ->  __frontswap_unuse_pages(total_pages_to_unuse, pages_to_unuse, type);

try_to_unuse(type, true, pages_to_unuse);
------

Quoted 23 lines

Quoted 6 lines

Quoted 6 lines

Quoted 5 lines

appear to get this right at least. Similarly, if the first swapfile has fewer frontswap pages than the target then it does not unuse the target number of pages because it only handles one swap file. It's outside the scope of your patch to address this or wonder if xen balloon driver is really using it the way it's expected.

Quoted 8 lines

Quoted 5 lines

I didn't look into the frontswap shrinking code, but I agree the existing logic there doesn't look right. I'll review frontswap in more detail to see if it needs changing here, unless anyone else gets it to first :-)

FYI, I drop the frontswap_shrink code in a patch
see: https://lkml.org/lkml/2014/1/27/98

frontswap_shrink() is actually used (only) by drivers/xen/xen-selfballoon.c.

However, I completely agree with you that the backend should be doing the shrinking, not from a frontswap api. Forcing frontswap to shrink is backwards - xen-selfballoon appears to be assuming that xem/tmem is the only possible frontswap backend. It certainly doensn't make any sense for xen-selfballoon to force zswap to shrink itself, does it?

Quoted 5 lines

If xen-selfballoon wants to shrink its frontswap backend tmem, it should do that by telling tmem directly to shrink itself (which it looks like tmem would have to implement, just like zswap sends its LRU pages back to swapcache when it becomes full).

Yes, it's possible in theory, but tmem is located in xen(host) which can't put back pages to swap cache(in guest os) directly. Use frontswap_shrink() can make things simple and easier.

And I think frontswap shrink isn't a blocker of this patch set, so please keep it.

Quoted 32 lines · Dan Streetman

Quoted 3 lines · Weijie Yang

Quoted 2 lines · Dan Streetman

Quoted 1 line · Mel Gorman

On Sat, Apr 12, 2014 at 05:00:53PM -0400, Dan Streetman wrote:

<SNIP>

Quoted 27 lines

Quoted 27 lines

Quoted 27 lines

Quoted 27 lines

mm/frontswap.c +1 -5

index 1b24bdc..fae1160 100644
@@ -327,15 +327,12 @@ EXPORT_SYMBOL(__frontswap_invalidate_area);
 
 static unsigned long __frontswap_curr_pages(void)
 {
-     int type;
      unsigned long totalpages = 0;
      struct swap_info_struct *si = NULL;
 
      assert_spin_locked(&swap_lock);
-     for (type = swap_list.head; type >= 0; type = si->next) {
-             si = swap_info[type];
+     list_for_each_entry(si, &swap_list_head, list)
              totalpages += atomic_read(&si->frontswap_pages);
-     }
      return totalpages;
 }
 

@@ -347,11 +344,9 @@ static int __frontswap_unuse_pages(unsigned long total, unsigned long *unused,
      int si_frontswap_pages;
      unsigned long total_pages_to_unuse = total;
      unsigned long pages = 0, pages_to_unuse = 0;
-     int type;
 

Quoted 10 lines

Quoted 10 lines

Quoted 10 lines

Quoted 10 lines

mm/frontswap.c static int __frontswap_unuse_pages(unsigned long total, unsigned long *unused, · line 352

Quoted 7 lines

mm/frontswap.c +1 -2

      assert_spin_locked(&swap_lock);
-     for (type = swap_list.head; type >= 0; type = si->next) {
-             si = swap_info[type];
+     list_for_each_entry(si, &swap_list_head, list) {
              si_frontswap_pages = atomic_read(&si->frontswap_pages);
              if (total_pages_to_unuse < si_frontswap_pages) {
                      pages = pages_to_unuse = total_pages_to_unuse;

The frontswap shrink code looks suspicious. If the target is smaller than the total number of frontswap pages then it does nothing. The callers

__frontswap_unuse_pages() is called only to get the correct value of pages_to_unuse which will pass to try_to_unuse(), perhaps we should rename it to __frontswap_unuse_pages_nr()..

------

ret = __frontswap_shrink(target_pages, &pages_to_unuse, &type);
        ->  __frontswap_unuse_pages(total_pages_to_unuse, pages_to_unuse, type);

try_to_unuse(type, true, pages_to_unuse);
------

Quoted 23 lines

Quoted 6 lines

Quoted 6 lines

Quoted 5 lines

appear to get this right at least. Similarly, if the first swapfile has fewer frontswap pages than the target then it does not unuse the target number of pages because it only handles one swap file. It's outside the scope of your patch to address this or wonder if xen balloon driver is really using it the way it's expected.

Quoted 8 lines

Quoted 5 lines

I didn't look into the frontswap shrinking code, but I agree the existing logic there doesn't look right. I'll review frontswap in more detail to see if it needs changing here, unless anyone else gets it to first :-)

FYI, I drop the frontswap_shrink code in a patch
see: https://lkml.org/lkml/2014/1/27/98

frontswap_shrink() is actually used (only) by drivers/xen/xen-selfballoon.c.

However, I completely agree with you that the backend should be doing the shrinking, not from a frontswap api. Forcing frontswap to shrink is backwards - xen-selfballoon appears to be assuming that xem/tmem is the only possible frontswap backend. It certainly doensn't make any sense for xen-selfballoon to force zswap to shrink itself, does it?

Quoted 5 lines

If xen-selfballoon wants to shrink its frontswap backend tmem, it should do that by telling tmem directly to shrink itself (which it looks like tmem would have to implement, just like zswap sends its LRU pages back to swapcache when it becomes full).

Yes, it's possible in theory, but tmem is located in xen(host) which can't put back pages to swap cache(in guest os) directly. Use frontswap_shrink() can make things simple and easier.

And I think frontswap shrink isn't a blocker of this patch set, so please keep it.

Quoted 2 lines · Dan Streetman

Quoted 1 line · Mel Gorman

On Sat, Apr 12, 2014 at 05:00:53PM -0400, Dan Streetman wrote:

Quoted 43 lines

Quoted 42 lines

Quoted 24 lines

mm/frontswap.c +1 -4

index 1b24bdc..fae1160 100644
@@ -327,15 +327,12 @@ EXPORT_SYMBOL(__frontswap_invalidate_area);
 
 static unsigned long __frontswap_curr_pages(void)
 {
-     int type;
      unsigned long totalpages = 0;
      struct swap_info_struct *si = NULL;
 
      assert_spin_locked(&swap_lock);
-     for (type = swap_list.head; type >= 0; type = si->next) {
-             si = swap_info[type];
+     list_for_each_entry(si, &swap_list_head, list)
              totalpages += atomic_read(&si->frontswap_pages);
-     }
      return totalpages;
 }
 

@@ -347,11 +344,9 @@ static int __frontswap_unuse_pages(unsigned long total, unsigned long *unused,
      int si_frontswap_pages;
      unsigned long total_pages_to_unuse = total;

mm/frontswap.c static int __frontswap_unuse_pages(unsigned long total, unsigned long *unused, · line 352

Quoted 10 lines

mm/frontswap.c +1 -3

      unsigned long pages = 0, pages_to_unuse = 0;
-     int type;
 
      assert_spin_locked(&swap_lock);
-     for (type = swap_list.head; type >= 0; type = si->next) {
-             si = swap_info[type];
+     list_for_each_entry(si, &swap_list_head, list) {
              si_frontswap_pages = atomic_read(&si->frontswap_pages);
              if (total_pages_to_unuse < si_frontswap_pages) {
                      pages = pages_to_unuse = total_pages_to_unuse;

The frontswap shrink code looks suspicious. If the target is smaller than the total number of frontswap pages then it does nothing. The callers appear to get this right at least. Similarly, if the first swapfile has fewer frontswap pages than the target then it does not unuse the target number of pages because it only handles one swap file. It's outside the scope of your patch to address this or wonder if xen balloon driver is really using it the way it's expected.

Quoted 5 lines

I didn't look into the frontswap shrinking code, but I agree the existing logic there doesn't look right. I'll review frontswap in more detail to see if it needs changing here, unless anyone else gets it to first :-)

FYI, I drop the frontswap_shrink code in a patch
see: https://lkml.org/lkml/2014/1/27/98

Quoted 31 lines

Quoted 20 lines

<SNIP>

mm/swapfile.c +5 -8

-             }
-
+     list_for_each(tmp, &swap_list_head) {
+             si = list_entry(tmp, typeof(*si), list);
              spin_lock(&si->lock);
-             if (!si->highest_bit) {
-                     spin_unlock(&si->lock);
-                     continue;
-             }
-             if (!(si->flags & SWP_WRITEOK)) {
+             if (!si->highest_bit || !(si->flags & SWP_WRITEOK)) {
                      spin_unlock(&si->lock);
                      continue;
              }
 
-             swap_list.next = next;
+             /*
+              * rotate the current swap_info that we're going to use

mm/swapfile.c no_page: · line 671

Quoted 10 lines

mm/swapfile.c +10 -0

+              * to after any other swap_info that have the same prio,
+              * so that all equal-priority swap_info get used equally
+              */
+             next = si;
+             list_for_each_entry_continue(next, &swap_list_head, list) {
+                     if (si->prio != next->prio)
+                             break;
+                     list_rotate_left(&si->list);
+                     next = si;
+             }

Quoted 8 lines

The list manipulations will be a lot of cache writes as the list is shuffled around. On slow storage I do not think this will be noticable but it may be noticable on faster swap devices that are SSD based. I've added Shaohua Li to the cc as he has been concerned with the performance of swap in the past. Shaohua, can you run this patchset through any of your test cases with the addition that multiple swap files are used to see if the cache writes are noticable? You'll need multiple swap files, some of which are at equal priority so the list shuffling logic is triggered.

One performance improvement could be instead of rotating the current entry past each following same-prio entry, just scan to the end of the same-prio entries and move the current entry there; that would skip the extra writes. Especially since this code will run for each get_swap_page(), no need for any unnecessary writes.

Quoted 19 lines

Quoted 8 lines

              spin_unlock(&swap_lock);
              /* This is called for allocating swap entry for cache */
              offset = scan_swap_map(si, SWAP_HAS_CACHE);
              spin_unlock(&si->lock);
              if (offset)

mm/swapfile.c +1 -1

-                     return swp_entry(type, offset);
+                     return swp_entry(si->type, offset);

mm/swapfile.c no_page: · line 687

Quoted 10 lines

mm/swapfile.c +7 -1

              spin_lock(&swap_lock);
-             next = swap_list.next;
+             /*
+              * shouldn't really have got here, but for some reason the
+              * scan_swap_map came back empty for this swap_info.
+              * Since we dropped the swap_lock, there may now be
+              * non-full higher prio swap_infos; let's start over.
+              */
+             tmp = &swap_list_head;
      }

Quoted 4 lines

Has this ever triggered? The number of swap pages was examined under the swap lock so no other process should have been iterating through the swap files. Once a candidate was found, the si lock was acquired for the swap scan map so nothing else should have raced with it.

Well scan_swap_map() does drop the si->lock if it has any trouble at all finding an offset to use, so I think it's possible that for a nearly-full si multiple concurrent get_swap_page() calls could enter scan_swap_map() with the same si, only some of them actually get pages from the si and then the si becomes full, and the other threads in scan_swap_map() see it's full and exit in failure. I can update the code comment there to better indicate why it was reached, instead of just saying "we shouldn't have got here" :-)

It may also be worth trying to get a better indicator of "available" swap_info_structs for use in get_swap_page(), either by looking at something other than si->highest_bit and/or keeping the si out of the prio_list until it's actually available for use, not just has a single entry free. However, that probably won't be simple and might be better as a separate patch to the rest of these changes.

Originally get_swap_page() started iterating through the singly-linked list of swap_info_structs using swap_list.next or highest_priority_index, which both were intended to point to the highest priority active swap target that was not full. The previous patch in this series changed the singly-linked list to a doubly-linked list, and removed the logic to start at the highest priority non-full entry; it starts scanning at the highest priority entry each time, even if the entry is full.

Add a new list, also priority ordered, to track only swap_info_structs that are available, i.e. active and not full. Use a new spinlock so that entries can be added/removed outside of get_swap_page; that wasn't possible previously because the main list is protected by swap_lock, which can't be taken when holding a swap_info_struct->lock because of locking order. The get_swap_page() logic now does not need to hold the swap_lock, and it iterates only through swap_info_structs that are available.

Signed-off-by Dan Streetman <[email protected]>

---
 include/linux/swap.h |   1 +
 mm/swapfile.c        | 128 ++++++++++++++++++++++++++++++++++-----------------
 2 files changed, 87 insertions(+), 42 deletions(-)

include/linux/swap.h +1 -0

index 96662d8..d9263db 100644
@@ -214,6 +214,7 @@ struct percpu_cluster {
 struct swap_info_struct {
 	unsigned long	flags;		/* SWP_USED etc: see above */
 	signed short	prio;		/* swap priority of this type */
+	struct list_head prio_list;	/* entry in priority list */
 	struct list_head list;		/* entry in swap list */
 	signed char	type;		/* strange name for an index */
 	unsigned int	max;		/* extent of the swap_map */

mm/swapfile.c +0 -0

index b958645..3c38461 100644
@@ -57,9 +57,13 @@ static const char Unused_file[] = "Unused swap file entry ";
 static const char Bad_offset[] = "Bad swap offset entry ";

mm/swapfile.c +11 -0

 struct swap_info_struct *swap_info[MAX_SWAPFILES];
 
 static DEFINE_MUTEX(swapon_mutex);

@@ -73,6 +77,27 @@ static inline unsigned char swap_count(unsigned char ent)
 	return ent & ~SWAP_HAS_CACHE;	/* may include SWAP_HAS_CONT flag */
 }
 
+/*
+ * add, in priority order, swap_info (p)->(le) list_head to list (lh)
+ * this list-generic function is needed because both swap_list_head
+ * and prio_head need to be priority ordered:
+ * swap_list_head in swapoff to adjust lower negative prio swap_infos
+ * prio_list in get_swap_page to scan highest prio swap_info first
+ */
+#define swap_info_list_add(p, lh, le) do {			\
+	struct swap_info_struct *_si;				\
+	BUG_ON(!list_empty(&(p)->le));				\
+	list_for_each_entry(_si, (lh), le) {			\

Quoted 40 lines · Dan Streetman

Originally get_swap_page() started iterating through the singly-linked list of swap_info_structs using swap_list.next or highest_priority_index, which both were intended to point to the highest priority active swap target that was not full. The previous patch in this series changed the singly-linked list to a doubly-linked list, and removed the logic to start at the highest priority non-full entry; it starts scanning at the highest priority entry each time, even if the entry is full.

Add a new list, also priority ordered, to track only swap_info_structs that are available, i.e. active and not full. Use a new spinlock so that entries can be added/removed outside of get_swap_page; that wasn't possible previously because the main list is protected by swap_lock, which can't be taken when holding a swap_info_struct->lock because of locking order. The get_swap_page() logic now does not need to hold the swap_lock, and it iterates only through swap_info_structs that are available.

Signed-off-by Dan Streetman <[email protected]>

---
 include/linux/swap.h |   1 +
 mm/swapfile.c        | 128 ++++++++++++++++++++++++++++++++++-----------------
 2 files changed, 87 insertions(+), 42 deletions(-)

include/linux/swap.h +1 -0

index 96662d8..d9263db 100644
@@ -214,6 +214,7 @@ struct percpu_cluster {
 struct swap_info_struct {
      unsigned long   flags;          /* SWP_USED etc: see above */
      signed short    prio;           /* swap priority of this type */
+     struct list_head prio_list;     /* entry in priority list */
      struct list_head list;          /* entry in swap list */
      signed char     type;           /* strange name for an index */
      unsigned int    max;            /* extent of the swap_map */

mm/swapfile.c +0 -0

index b958645..3c38461 100644
@@ -57,9 +57,13 @@ static const char Unused_file[] = "Unused swap file entry ";
 static const char Bad_offset[] = "Bad swap offset entry ";

mm/swapfile.c static const char Unused_file[] = "Unused swap file entry "; · line 66

Quoted 10 lines

mm/swapfile.c +5 -1

 static const char Unused_offset[] = "Unused swap offset entry ";
 
-/* all active swap_info */
+/* all active swap_info; protected with swap_lock */
 LIST_HEAD(swap_list_head);
 
+/* all available (active, not full) swap_info, priority ordered */
+static LIST_HEAD(prio_head);
+static DEFINE_SPINLOCK(prio_lock);
+

I get why you maintain two lists with separate locking but it's code that is specific to swap and in many respects, it's very similar to a plist. Is there a reason why plist was not used at least for prio_head? They're used for futex's so presumably the performance is reasonable. It might reduce the size of swapfile.c further.

It is the case that plist does not have the equivalent of rotate which you need to recycle the entries of equal priority but you could add a plist_shuffle helper that "rotates the list left if the next entry is of equal priority".

I was going to suggest that you could then get rid of swap_list_head but it's a relatively big change. swapoff wouldn't care but frontswap would suffer if it had to walk all of swap_info[] to find all active swap files.

Quoted 18 lines

mm/swapfile.c +11 -0

 struct swap_info_struct *swap_info[MAX_SWAPFILES];
 
 static DEFINE_MUTEX(swapon_mutex);

@@ -73,6 +77,27 @@ static inline unsigned char swap_count(unsigned char ent)
      return ent & ~SWAP_HAS_CACHE;   /* may include SWAP_HAS_CONT flag */
 }
 
+/*
+ * add, in priority order, swap_info (p)->(le) list_head to list (lh)
+ * this list-generic function is needed because both swap_list_head
+ * and prio_head need to be priority ordered:
+ * swap_list_head in swapoff to adjust lower negative prio swap_infos
+ * prio_list in get_swap_page to scan highest prio swap_info first
+ */
+#define swap_info_list_add(p, lh, le) do {                   \
+     struct swap_info_struct *_si;                           \
+     BUG_ON(!list_empty(&(p)->le));                          \
+     list_for_each_entry(_si, (lh), le) {                    \

mm/swapfile.c static inline unsigned char swap_count(unsigned char ent) · line 100

Quoted 10 lines

mm/swapfile.c +10 -0

+             if ((p)->prio >= _si->prio) {                   \
+                     list_add_tail(&(p)->le, &_si->le);      \
+                     break;                                  \
+             }                                               \
+     }                                                       \
+     /* lh empty, or p lowest prio */                        \
+     if (list_empty(&(p)->le))                               \
+             list_add_tail(&(p)->le, (lh));                  \
+} while (0)
+

Why is this a #define instead of a static uninlined function?

That aside, it's again very similar to what a plist does with some minor structure modifications.

--
Mel Gorman
SUSE Labs

Quoted 58 lines · Mel Gorman

Quoted 40 lines · Dan Streetman

Originally get_swap_page() started iterating through the singly-linked list of swap_info_structs using swap_list.next or highest_priority_index, which both were intended to point to the highest priority active swap target that was not full. The previous patch in this series changed the singly-linked list to a doubly-linked list, and removed the logic to start at the highest priority non-full entry; it starts scanning at the highest priority entry each time, even if the entry is full.

Add a new list, also priority ordered, to track only swap_info_structs that are available, i.e. active and not full. Use a new spinlock so that entries can be added/removed outside of get_swap_page; that wasn't possible previously because the main list is protected by swap_lock, which can't be taken when holding a swap_info_struct->lock because of locking order. The get_swap_page() logic now does not need to hold the swap_lock, and it iterates only through swap_info_structs that are available.

Signed-off-by Dan Streetman <[email protected]>

---
 include/linux/swap.h |   1 +
 mm/swapfile.c        | 128 ++++++++++++++++++++++++++++++++++-----------------
 2 files changed, 87 insertions(+), 42 deletions(-)

include/linux/swap.h +1 -0

index 96662d8..d9263db 100644
@@ -214,6 +214,7 @@ struct percpu_cluster {
 struct swap_info_struct {
      unsigned long   flags;          /* SWP_USED etc: see above */
      signed short    prio;           /* swap priority of this type */
+     struct list_head prio_list;     /* entry in priority list */
      struct list_head list;          /* entry in swap list */
      signed char     type;           /* strange name for an index */
      unsigned int    max;            /* extent of the swap_map */

mm/swapfile.c +0 -0

index b958645..3c38461 100644
@@ -57,9 +57,13 @@ static const char Unused_file[] = "Unused swap file entry ";
 static const char Bad_offset[] = "Bad swap offset entry ";

mm/swapfile.c static const char Unused_file[] = "Unused swap file entry "; · line 66

Quoted 10 lines

mm/swapfile.c +5 -1

 static const char Unused_offset[] = "Unused swap offset entry ";
 
-/* all active swap_info */
+/* all active swap_info; protected with swap_lock */
 LIST_HEAD(swap_list_head);
 
+/* all available (active, not full) swap_info, priority ordered */
+static LIST_HEAD(prio_head);
+static DEFINE_SPINLOCK(prio_lock);
+

I get why you maintain two lists with separate locking but it's code that is specific to swap and in many respects, it's very similar to a plist. Is there a reason why plist was not used at least for prio_head? They're used for futex's so presumably the performance is reasonable. It might reduce the size of swapfile.c further.

Quoted 4 lines

It is the case that plist does not have the equivalent of rotate which you need to recycle the entries of equal priority but you could add a plist_shuffle helper that "rotates the list left if the next entry is of equal priority".

I did look at plist, but as you said there's no plist_rotate_left() so that would either need to be implemented in plist or a helper specific to swap added.

The plist sort order is also reverse from swap sort order; plist orders low->high while swap orders high->low. So either the prio would need to be negated when storing in the plist to correct the order, or plist_for_each_entry_reverse() would need to be added (or another helper specific for swap).

I think the main (only?) benefit of plist is during adds; insertion for lists is O(N) while insertion for plists is O(K) where K is the number of different priorities. And for swap, the add only happens in two places: on swapon (or if swapoff fails and reinserts it) and in swap_entry_free() when the swap_info_struct changes from full to not-full. The swapon and swapoff failure cases don't matter, and a swap_info_struct changing from full to not-full is (probably?) going to be a relatively rare occurrence. And even then, unless there are a significant number of not-full same-priority swap_info_structs that are higher prio than the one being added, there should (?) be no difference between plist and normal list add speed.

Finally, using a plist further increases the size of each swap_info_struct.

So to me, it seemed list plists were best used in situations where list entries were constantly being added/removed, and the add speed needed to be as fast as possible. That isn't typically the case with the swap_info_struct priority list, where adding/removing is a relatively rare occurrence. However, in the case where there are multiple groups of many same-priority swap devices/files, using plists may reduce the add insertion time when one of the lower-priority swap_info_struct changes from full to not-full after some of the higher prio ones also have changed from full to not-full. If you think it would be good to change to using a plist, I can update the patch.

Add PLIST_HEAD() to plist.h, equivalent to LIST_HEAD() from list.h, to define and initialize a struct plist_head.

Add plist_for_each_continue() and plist_for_each_entry_continue(), equivalent to list_for_each_continue() and list_for_each_entry_continue(), to iterate over a plist continuing after the current position.

Add plist_prev() and plist_next(), equivalent to (struct list_head*)->prev and ->next, implemented by list_prev_entry() and list_next_entry(), to access the prev/next struct plist_node entry. These are needed because unlike struct list_head, direct access of the prev/next struct plist_node isn't possible; the list must be navigated via the contained struct list_head. e.g. instead of accessing the prev by list_prev_entry(node, node_list) it can be accessed by plist_prev(node).

Signed-off-by Dan Streetman <[email protected]>

Cc Mel Gorman <[email protected]>

Cc Paul Gortmaker <[email protected]>

Cc Steven Rostedt <[email protected]>

Cc Thomas Gleixner <[email protected]>

Add plist_rotate(), which moves the specified plist_node after all other same-priority plist_nodes in the list.

This is needed by swap, which has a plist of swap_info_structs and needs to use each same-priority swap_info_struct equally.

Also add plist_test_rotate() test function, for use by plist_test() to test plist_rotate() function.

Signed-off-by Dan Streetman <[email protected]>

Cc Mel Gorman <[email protected]>

Cc Paul Gortmaker <[email protected]>

Cc Steven Rostedt <[email protected]>

Cc Thomas Gleixner <[email protected]>

---

This patch is new to this patch set, and it's required by the next patch, which needs a way to move a plist entry to the end of all following same-priority entries. This is possible to do manually instead of adding a new plist function, but having a common plist function instead of code specific only to swap seems preferable.

 include/linux/plist.h |  2 ++
 lib/plist.c           | 48 ++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 50 insertions(+)

include/linux/plist.h +2 -0

index c815491..06e6925 100644
@@ -141,6 +141,8 @@ static inline void plist_node_init(struct plist_node *node, int prio)
 extern void plist_add(struct plist_node *node, struct plist_head *head);
 extern void plist_del(struct plist_node *node, struct plist_head *head);
 
+extern void plist_rotate(struct plist_node *node, struct plist_head *head);
+
 /**
  * plist_for_each - iterate over the plist
  * @pos:	the type * to use as a loop counter

lib/plist.c +0 -0

index 1ebc95f..a8b54e5 100644
@@ -134,6 +134,42 @@ void plist_del(struct plist_node *node, struct plist_head *head)
 	plist_check_head(head);
 }
 

lib/plist.c +34 -0

+
+	plist_check_head(head);
+	BUG_ON(plist_head_empty(head));
+	BUG_ON(plist_node_empty(node));
+
+	if (node == plist_last(head))
+		return;
+
+	next = plist_next(node);
+
+	if (node->prio != next->prio)
+		return;
+
+	plist_del(node, head);
+
+	plist_for_each_continue(next, head) {
+		if (node->prio != next->prio) {
+			next_node_list = &next->node_list;
+			break;
+		}
+	}
+	list_add_tail(&node->node_list, next_node_list);
+
+	plist_check_head(head);
+}
+
 #ifdef CONFIG_DEBUG_PI_LIST
 #include <linux/sched.h>
 #include <linux/module.h>

@@ -170,6 +206,14 @@ static void __init plist_test_check(int nr_expect)
 	BUG_ON(prio_pos->prio_list.next != &first->prio_list);
 }
 
+static void __init plist_test_rotate(struct plist_node *node)
+{
+	plist_rotate(node, &test_head);
+
+	if (node != plist_last(&test_head))
+		BUG_ON(node->prio == plist_next(node)->prio);
+}
+
 static int  __init plist_test(void)
 {
 	int nr_expect = 0, i, loop;

Quoted 2 lines · On Fri, 2 May 2014 15:02:29 -0400 Dan Streetman <[email protected]> wrote:

Add plist_rotate(), which moves the specified plist_node after all other same-priority plist_nodes in the list.

This is a little confusing? You mean it takes a plist_node from a plist and simply moves it to the end of the list of all other nodes of the same priority?

Kind of like what a sched_yield() would do with a SCHED_FIFO task? I wonder if we should call this "plist_yield()" then?

Quoted 4 lines

This is needed by swap, which has a plist of swap_info_structs and needs to use each same-priority swap_info_struct equally.

"needs to use each same-priority swap_info_struct equally"

-ENOCOMPUTE

Quoted 44 lines

Also add plist_test_rotate() test function, for use by plist_test() to test plist_rotate() function.

Signed-off-by Dan Streetman <[email protected]>

Cc Mel Gorman <[email protected]>

Cc Paul Gortmaker <[email protected]>

Cc Steven Rostedt <[email protected]>

Cc Thomas Gleixner <[email protected]>

---

This patch is new to this patch set, and it's required by the next patch, which needs a way to move a plist entry to the end of all following same-priority entries. This is possible to do manually instead of adding a new plist function, but having a common plist function instead of code specific only to swap seems preferable.

 include/linux/plist.h |  2 ++
 lib/plist.c           | 48 ++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 50 insertions(+)

include/linux/plist.h +2 -0

index c815491..06e6925 100644
@@ -141,6 +141,8 @@ static inline void plist_node_init(struct plist_node *node, int prio)
 extern void plist_add(struct plist_node *node, struct plist_head *head);
 extern void plist_del(struct plist_node *node, struct plist_head *head);
 
+extern void plist_rotate(struct plist_node *node, struct plist_head *head);
+
 /**
  * plist_for_each - iterate over the plist
  * @pos:     the type * to use as a loop counter

lib/plist.c +0 -0

index 1ebc95f..a8b54e5 100644
@@ -134,6 +134,42 @@ void plist_del(struct plist_node *node, struct plist_head *head)
      plist_check_head(head);
 }
 

lib/plist.c void plist_del(struct plist_node *node, struct plist_head *head) · line 146

Quoted 10 lines

lib/plist.c +10 -0

+/**
+ * plist_rotate - Rotate @node to end of same-prio entries.
+ *
+ * @node:    &struct plist_node pointer - entry to be moved
+ * @head:    &struct plist_head pointer - list head
+ */
+void plist_rotate(struct plist_node *node, struct plist_head *head)
+{
+     struct plist_node *next;
+     struct list_head *next_node_list = &head->node_list;

Naming convention should be the same as plist_add() and call this node_next instead of next_node_list.

-- Steve

Quoted 54 lines

lib/plist.c +38 -0

+
+     plist_check_head(head);
+     BUG_ON(plist_head_empty(head));
+     BUG_ON(plist_node_empty(node));
+
+     if (node == plist_last(head))
+             return;
+
+     next = plist_next(node);
+
+     if (node->prio != next->prio)
+             return;
+
+     plist_del(node, head);
+
+     plist_for_each_continue(next, head) {
+             if (node->prio != next->prio) {
+                     next_node_list = &next->node_list;
+                     break;
+             }
+     }
+     list_add_tail(&node->node_list, next_node_list);
+
+     plist_check_head(head);
+}
+
 #ifdef CONFIG_DEBUG_PI_LIST
 #include <linux/sched.h>
 #include <linux/module.h>

@@ -170,6 +206,14 @@ static void __init plist_test_check(int nr_expect)
      BUG_ON(prio_pos->prio_list.next != &first->prio_list);
 }
 
+static void __init plist_test_rotate(struct plist_node *node)
+{
+     plist_rotate(node, &test_head);
+
+     if (node != plist_last(&test_head))
+             BUG_ON(node->prio == plist_next(node)->prio);
+}
+
 static int  __init plist_test(void)
 {
      int nr_expect = 0, i, loop;

@@ -193,6 +237,10 @@ static int  __init plist_test(void)
                      nr_expect--;
              }
              plist_test_check(nr_expect);
+             if (!plist_node_empty(test_node + i)) {
+                     plist_test_rotate(test_node + i);
+                     plist_test_check(nr_expect);
+             }
      }
 

lib/plist.c static int __init plist_test(void) · line 246

Quoted 1 line

lib/plist.c +0 -0

      for (i = 0; i < ARRAY_SIZE(test_node); i++) {

Quoted 9 lines · Steven Rostedt

Quoted 2 lines · On Fri, 2 May 2014 15:02:29 -0400 Dan Streetman <[email protected]> wrote:

Add plist_rotate(), which moves the specified plist_node after all other same-priority plist_nodes in the list.

This is a little confusing? You mean it takes a plist_node from a plist and simply moves it to the end of the list of all other nodes of the same priority?

yes, exactly

Quoted 2 lines

Kind of like what a sched_yield() would do with a SCHED_FIFO task? I wonder if we should call this "plist_yield()" then?

I suppose it is similar, yes...I'll rename it in a v2 patch.

Quoted 6 lines

Quoted 5 lines

This is needed by swap, which has a plist of swap_info_structs and needs to use each same-priority swap_info_struct equally.

Quoted 3 lines

"needs to use each same-priority swap_info_struct equally"

-ENOCOMPUTE

heh, yeah that needs a bit more explaining doesn't it :-)

by "equally", I mean as swap writes pages out to its swap devices, it must write to any same-priority devices on a round-robin basis.

I'll update the comment in the v2 patch to try to explain clearer.

Quoted 13 lines · On Tue, 6 May 2014 16:12:54 -0400 Dan Streetman <[email protected]> wrote:

Quoted 9 lines · Steven Rostedt

Quoted 2 lines · On Fri, 2 May 2014 15:02:29 -0400 Dan Streetman <[email protected]> wrote:

Add plist_rotate(), which moves the specified plist_node after all other same-priority plist_nodes in the list.

This is a little confusing? You mean it takes a plist_node from a plist and simply moves it to the end of the list of all other nodes of the same priority?

yes, exactly

Quoted 4 lines

Quoted 2 lines

Kind of like what a sched_yield() would do with a SCHED_FIFO task? I wonder if we should call this "plist_yield()" then?

I suppose it is similar, yes...I'll rename it in a v2 patch.

I'm open to other suggestions as well. What else can give you the idea that it's putting a node at the end of its priority?