swap: add a simple buddy allocator

I'm using a fast SSD to do swap. scan_swap_map() sometimes uses up to 20~30% CPU time (when cluster is hard to find, the CPU time can be up to 80%), which becomes a bottleneck. scan_swap_map() scans a byte array to search a 256 page cluster, which is very slow.

Here I introduced a simple buddy allocator. Since we only care about 256 pages cluster, we can just use a counter to implement the buddy allocator. Every 256 pages use one int to store the counter. All free clusters will be added to a list, so searching cluster is very efficient. With this, scap_swap_map() overhead disappears.

Since searching cluster with a list is easy, we can easily implement a per-cpu cluster algorithm to do block allocation, which can make swapout more efficient. This is in my TODO list.

This might help low end SD card swap too. Because if the cluster is aligned, SD firmware can do flash erase more efficiently.

We only enable the buddy allocator for SSD. Hard disk swap isn't fast enough and has downside with a buddy allocator which might introduce regression.

The patch slightly changes which cluster is choosen. It always adds free cluster to list tail. This can help wear leveling for low end SSD too. And if no cluster found, the scan_swap_map() will do search from the end of last cluster. So if no cluster found, the scan_swap_map() will do search from the end of last free cluster, which is random. For SSD, this isn't a problem at all.

Another downside is the cluster must be aligned to 256 pages, which will reduce the chance to find a cluster. I would expect this isn't a big problem for SSD because of the non-seek penality.

Changes from V1 to V2:
1. free cluster is added to a list, which makes searching cluster more efficient
2. only enable the buddy allocator for SSD.

---
 include/linux/swap.h |    3 
 mm/swapfile.c        |  178 +++++++++++++++++++++++++++++++++++++++++++++++----
 2 files changed, 170 insertions(+), 11 deletions(-)

Index: linux/include/linux/swap.h
===================================================================
@@ -185,6 +185,9 @@ struct swap_info_struct {
 	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 */
+	unsigned int *cluster_info;	/* cluster info. Only for SSD */
+	unsigned int free_cluster_head;
+	unsigned int free_cluster_tail;
 	unsigned int lowest_bit;	/* index of first free in swap_map */
 	unsigned int highest_bit;	/* index of last free in swap_map */
 	unsigned int pages;		/* total of usable pages of swap */

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

Oh. My fault, not yours at all, but I wish I'd known this was coming. I spent today testing and fixing (a couple of hangs in discard 2/2) V1, was about to send you a patch, but looks like none of it relevant to V2.

It's nice work you've done, I thoroughly approve of V1 (very minor mods), but it'll take me a few more days to get around to looking at V2, sorry.

Though, it may be my ignorance, I entirely fail to see what this has to do with a buddy allocator: you've speeded up scan_swap_map()'s search for a cluster by adding an additional cluster map, then extended that neatly for a much better discard implementation. Good work yes, but a buddy allocator??

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

Appologize for this. I was in travel last whole week, a little lagged to fully test the V2 patch till yesterday. Had no confidence to bother again before I know it really works.

That is just the name I called. I thought it's a variant of buddy allocator, don't take it serious.

Thanks,
Shaohua

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