mm: prototype: rid swapoff of quadratic complexity

The function try_to_unuse() is of quadratic complexity, with a lot of wasted effort. It unuses swap entries one by one, potentially iterating over all the page tables for all the processes in the system for each one.

This new proposed implementation of try_to_unuse simplifies its complexity to linear. It iterates over the system's mms once, unusing all the affected entries as it walks each set of page tables. It also makes similar changes to shmem_unuse.

Improvement

Time took by swapoff on a swap partition containing about 240M of data, with about 1.1G free memory and about 520M swap available. Swap partition was on a laptop with a hard disk drive (not SSD).

Present implementation....about 13.8s
Prototype.................about 5.5s

Details

In shmem_unuse, iterate over the shmem_swaplist and, for each shmem_inode_info that contains a swap entry, pass it to shmem_unuse_inode, along with the swap type. In shmem_unuse_inode, iterate over its associated radix tree, and store the index of each exceptional entry in an array for passing to shmem_getpage_gfp outside of the RCU critical section.

In try_to_unuse, instead of iterating over the entries in the type and unusing them one by one, perhaps walking all the page tables for all the processes for each one, iterate over the mmlist, making one pass. Pass each mm to unuse_mm to begin its page table walk, and during the walk, unuse all the ptes that have backing store in the swap type received by try_to_unuse. After the walk, check the type for orphaned swap entries with find_next_to_unuse, and remove them from the swap cache.

Change unuse_mm and the intervening walk functions down to unuse_pte_range to take the type as a parameter, and to iterate over their entire range, calling the next function down on every iteration. In unuse_pte_range, make a swap entry from each pte in the range using the passed in type. If it has backing store in the type, call swapin_readahead to retrieve the page, and then pass this page to unuse_pte.

TODO

* Handle count of unused pages for frontswap.

---
 include/linux/shmem_fs.h |   2 +-
 mm/shmem.c               | 185 +++++++++++------------
 mm/swapfile.c            | 371 +++++++++++++++--------------------------------
 3 files changed, 205 insertions(+), 353 deletions(-)

index 9d55438..af78151 100644
@@ -55,7 +55,7 @@ extern void shmem_unlock_mapping(struct address_space *mapping);
 extern struct page *shmem_read_mapping_page_gfp(struct address_space *mapping,
 					pgoff_t index, gfp_t gfp_mask);
 extern void shmem_truncate_range(struct inode *inode, loff_t start, loff_t end);
-extern int shmem_unuse(swp_entry_t entry, struct page *page);
+extern int shmem_unuse(unsigned int type);
 
 static inline struct page *shmem_read_mapping_page(
 				struct address_space *mapping, pgoff_t index)

1.8.3.2

--
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>

That should probably wait for a follow-up patch. This patch is big enough as is.

All rights reversed

--
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>

I have now given this v5 a try, and it seems to be working well for the normal case, but not when under global memory pressure: swapoff gets stuck going round and around in the find_next_to_unuse() loop.

The reason is, that loop thinks it's just cleaning up the orphaned swapcache pages, but in fact there can be swap entries reinserted back into process space since the mmlist loop passed over them: on those the find_next_to_unuse() loop keeps on reading in from swap, then deleting from swapcache; but does nothing actually to free up the swap.

Which draws attention to a feature of the old per-page approach, which you need to incorporate into your approach. To make forward progress under global memory pressure, a page should be mapped into all its mms and the swap then freed as soon as possible. Any delay makes it more likely that page reclaim will reinsert a swap entry; and until the page is removed from swapcache, reclaim cannot assign new swap to it.

So, don't just add allowance for still-mapped pages into that final find_next_to_unuse() loop - that's necessary (a goto back to the start, or perhaps to after the shmem_unuse - I'm not certain), but you also need to delete_from_swap_cache() each page in turn as soon as its swapcount goes down to 0, to minimize the chance of reusing the swap.

Given the way copy_one_pte() adds dst_mm to mmlist after src_mm, mms sharing the same page should be clustered closely in the mmlist. For this patch it will probably be good enough not to complicate your current structure, but just add the delete_from_swap_cache() when swapcount 0 into unuse_pte() or nearby.

(And don't be disheartened if once you've put it in, I suggest you move it around: this code has been stable for a long while, there's a lot to consider in reorganizing it, not obvious to either of us.)

I think a further patch, which does an rmap walk when the first pte has been found (if swapcount indicates more entries to update) while still holding the page lock, will probably be a good addition on top. (That ksm_might_need_to_copy(): hmm, yes, KSM complicates this.)

It's tempting to think that with such an rmap walk under page lock in place, there would no longer be a need for the find_next_to_unuse() loop to terminate and go back to mmlist. Tempting, but I wouldn't bet on it: we shall probably find odd corners which still make retry necessary (KSM? mremap move? others?).

While I remember, two other things you can address in separate patches (no need to worry until this is stable). Don't forget to delete __locate() and radix_tree_locate_item() from lib/radix-tree.c and include/linux/radix-tree.h: that will improve your diffstat. And I think it would help everyone if you change the ancient strange "unuse" throughout to "swapoff" (particularly now that s390 are adding a pte_unused() which has nothing to do with all this).

Hugh

--
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>