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

* Determine the optimal batch size for retrieving and passing indices in shmem_unuse_inode. Maximum size is dependent on stack frame size, and may also be dependent on architecture and/or other factors.
* Determine the optimal number of passes to make over each part of the swapoff process to make sure all entries have been cleaned up, yet account for genuine failure.
* Handle count of unused pages for frontswap.
* determine when old comments and housekeeping are no longer needed (there are still some to serve as reminders of the housekeeping that needs to be accounted for). In particular, there are three occurences in unuse_pte_range that are marked as TODO.

---
 include/linux/shmem_fs.h |   2 +-
 mm/shmem.c               | 193 ++++++++++------------
 mm/swapfile.c            | 415 +++++++++++++++++++----------------------------
 3 files changed, 258 insertions(+), 352 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>