mm: Implement Swap Prefetching v22

Here's a significant rewrite of the swap prefetching code. I've tried to address the numa issues Nick and Paul brought up. I use the node id of the swapped page to create an appropriate zonelist to prefetch pages into now,
and the watermarks for prefetching are done on a per-node basis.

Index: linux-2.6.16-rc2-sp/mm/page_alloc.c
===================================================================

mm/page_alloc.c +2 -2

@@ -833,7 +833,7 @@ int zone_watermark_ok(struct zone *z, in
 		min -= min / 4;
 
 	if (free_pages <= min + z->lowmem_reserve[classzone_idx])
-		return 0;
+		goto out_failed;
 	for (o = 0; o < order; o++) {
 		/* At the next order, this order's pages become unavailable */
 		free_pages -= z->free_area[o].nr_free << o;

@@ -842,9 +842,15 @@ int zone_watermark_ok(struct zone *z, in
 		min >>= 1;
 
 		if (free_pages <= min)
-			return 0;
+			goto out_failed;

mm/page_alloc.c +0 -0

 /*

Index: linux-2.6.16-rc2-sp/mm/swap.c
===================================================================

mm/swap.c +3 -0

@@ -502,5 +502,8 @@ void __init swap_setup(void)
 	 * Right now other parts of the system means that we
 	 * _really_ don't want to cluster much more
 	 */
+
+	prepare_swap_prefetch();
+
 	hotcpu_notifier(cpu_swap_callback, 0);
 }

Index: linux-2.6.16-rc2-sp/mm/swap_prefetch.c
===================================================================

mm/swap_prefetch.c new file +25 -0

@@ -0,0 +1,478 @@
+/*
+ * linux/mm/swap_prefetch.c
+ *
+ * Copyright (C) 2005-2006 Con Kolivas
+ *
+ * Written by Con Kolivas <[email protected]>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation.
+ */
+
+#include <linux/fs.h>
+#include <linux/swap.h>
+#include <linux/ioprio.h>
+#include <linux/kthread.h>
+#include <linux/pagemap.h>
+#include <linux/syscalls.h>
+#include <linux/writeback.h>
+
+/*
+ * Time to delay prefetching if vm is busy or prefetching unsuccessful. There
+ * needs to be at least this duration of idle time meaning in practice it can
+ * be much longer
+ */

mm/swap_prefetch.c new file +20 -0

+	unsigned int		count;		/* Number of entries */
+	unsigned int		maxcount;	/* Maximum entries allowed */
+	kmem_cache_t		*cache;		/* Of struct swapped_entry */
+};
+
+static struct swapped_root swapped = {
+	.busy 		= 0,			/* Any vm activity */
+	.lock		= SPIN_LOCK_UNLOCKED,
+	.list  		= LIST_HEAD_INIT(swapped.list),
+	.swap_tree	= RADIX_TREE_INIT(GFP_ATOMIC),
+	.count 		= 0,			/* Number of swapped entries */
+};
+
+struct swapped_entry {
+	swp_entry_t		swp_entry;	/* The actual swap entry */
+	struct list_head	swapped_list;	/* Linked list of entries */
+	int			node;		/* Node id */
+} __attribute__((packed));
+
+static task_t *kprefetchd_task;

mm/swap_prefetch.c new file +33 -0

+/*
+ * Drop behind accounting which keeps a list of the most recently used swap
+ * entries.
+ */
+void add_to_swapped_list(struct page *page)
+{
+	struct swapped_entry *entry;
+	unsigned long index;
+
+	spin_lock(&swapped.lock);
+	if (swapped.count >= swapped.maxcount) {
+		/*
+		 * We limit the number of entries to the size of physical ram.
+		 * Once the number of entries exceeds this we start removing
+		 * the least recently used entries.
+		 */
+		entry = list_entry(swapped.list.next,
+			struct swapped_entry, swapped_list);
+		radix_tree_delete(&swapped.swap_tree, entry->swp_entry.val);
+		list_del(&entry->swapped_list);
+		swapped.count--;
+	} else {
+		entry = kmem_cache_alloc(swapped.cache, GFP_ATOMIC);
+		if (unlikely(!entry))
+			/* bad, can't allocate more mem */
+			goto out_locked;
+	}
+
+	index = page_private(page);
+	entry->swp_entry.val = index;
+	/*
+	 * On numa we need to store the node id to ensure that we prefetch to
+	 * the same node it came from.

mm/swap_prefetch.c new file +10 -0

+		list_add(&entry->swapped_list, &swapped.list);
+		swapped.count++;
+	}
+
+out_locked:
+	spin_unlock(&swapped.lock);
+	return;
+}
+
+/*

mm/swap_prefetch.c new file +55 -0

+	entry = radix_tree_delete(&swapped.swap_tree, index);
+	if (likely(entry)) {
+		list_del_init(&entry->swapped_list);
+		swapped.count--;
+		kmem_cache_free(swapped.cache, entry);
+	}
+	spin_unlock_irqrestore(&swapped.lock, flags);
+}
+
+enum trickle_return {
+	TRICKLE_SUCCESS,
+	TRICKLE_FAILED,
+	TRICKLE_DELAY,
+};
+
+/*
+ * prefetch_stats stores the free ram data of each node and this is used to
+ * determine if a node is suitable for prefetching into.
+ */
+struct prefetch_stats{
+	unsigned long	last_free[MAX_NUMNODES];
+	/* Free ram after a cycle of prefetching */
+	unsigned long	current_free[MAX_NUMNODES];
+	/* Free ram on this cycle of checking prefetch_suitable */
+	unsigned long	prefetch_watermark[MAX_NUMNODES];
+	/* Maximum amount we will prefetch to */
+	nodemask_t	prefetch_nodes;
+	/* Which nodes are currently suited to prefetching */
+	unsigned long	prefetched_pages;
+	/* Total pages we've prefetched on this wakeup of kprefetchd */
+};
+
+static struct prefetch_stats sp_stat;
+
+/*
+ * This tries to read a swp_entry_t into swap cache for swap prefetching.
+ * If it returns TRICKLE_DELAY we should delay further prefetching.
+ */
+static enum trickle_return trickle_swap_cache_async(const swp_entry_t entry,
+	const int node)
+{
+	enum trickle_return ret = TRICKLE_FAILED;
+	struct zonelist *zonelist;
+	struct page *page;
+
+	read_lock(&swapper_space.tree_lock);
+	/* Entry may already exist */
+	page = radix_tree_lookup(&swapper_space.page_tree, entry.val);
+	read_unlock(&swapper_space.tree_lock);
+	if (page) {
+		remove_from_swapped_list(entry.val);
+		goto out;
+	}
+
+	/*

mm/swap_prefetch.c new file +68 -0

+	if (unlikely(!page)) {
+		ret = TRICKLE_DELAY;
+		goto out;
+	}
+
+	if (add_to_swap_cache(page, entry)) {
+		/* Failed to add to swap cache */
+		goto out_release;
+	}
+
+	lru_cache_add(page);
+	if (unlikely(swap_readpage(NULL, page))) {
+		ret = TRICKLE_DELAY;
+		goto out_release;
+	}
+
+	sp_stat.last_free[node]--;
+	ret = TRICKLE_SUCCESS;
+out_release:
+	page_cache_release(page);
+out:
+	return ret;
+}
+
+static void clear_last_prefetch_free(void)
+{
+	int node;
+
+	/*
+	 * Reset the nodes suitable for prefetching to all nodes. We could
+	 * update the data to take into account memory hotplug if desired..
+	 */
+	sp_stat.prefetch_nodes = node_online_map;
+	for_each_node_mask(node, sp_stat.prefetch_nodes)
+		sp_stat.last_free[node] = 0;
+}
+
+static void clear_current_prefetch_free(void)
+{
+	int node;
+
+	sp_stat.prefetch_nodes = node_online_map;
+	for_each_node_mask(node, sp_stat.prefetch_nodes)
+		sp_stat.current_free[node] = 0;
+}
+
+/*
+ * We want to be absolutely certain it's ok to start prefetching.
+ */
+static int prefetch_suitable(void)
+{
+	struct page_state ps;
+	unsigned long limit;
+	struct zone *z;
+	int node, ret = 0;
+
+	/* Purposefully racy and might return false positive which is ok */
+	if (__test_and_clear_bit(0, &swapped.busy))
+		goto out;
+
+	clear_current_prefetch_free();
+
+	/*
+	 * Have some hysteresis between where page reclaiming and prefetching
+	 * will occur to prevent ping-ponging between them.
+	 */
+	for_each_zone(z) {
+		unsigned long free;

mm/swap_prefetch.c new file +107 -0

+		sp_stat.current_free[node] += free;
+	}
+
+	/*
+	 * We iterate over each node testing to see if it is suitable for
+	 * prefetching and clear the nodemask if it is not.
+	 */
+	for_each_node_mask(node, sp_stat.prefetch_nodes) {
+		/*
+		 * We check to see that pages are not being allocated
+		 * elsewhere at any significant rate implying any
+		 * degree of memory pressure (eg during file reads)
+		 */
+		if (sp_stat.last_free[node]) {
+			if (sp_stat.current_free[node] + SWAP_CLUSTER_MAX <
+				sp_stat.last_free[node]) {
+					sp_stat.last_free[node] =
+						sp_stat.current_free[node];
+					node_clear(node,
+						sp_stat.prefetch_nodes);
+					continue;
+			}
+		} else
+			sp_stat.last_free[node] = sp_stat.current_free[node];
+
+		/*
+		 * get_page_state is super expensive so we only perform it
+		 * every SWAP_CLUSTER_MAX prefetched_pages
+		 */
+		if (sp_stat.prefetched_pages % SWAP_CLUSTER_MAX)
+			continue;
+
+		get_page_state_node(&ps, node);
+
+		/* We shouldn't prefetch when we are doing writeback */
+		if (ps.nr_writeback) {
+			node_clear(node, sp_stat.prefetch_nodes);
+			continue;
+		}
+
+		/*
+		 * >2/3 of the ram on this node is mapped, slab, swapcache or
+		 * dirty, we need to leave some free for pagecache.
+		 * Note that currently nr_slab is innacurate on numa because
+		 * nr_slab is incremented on the node doing the accounting
+		 * even if the slab is being allocated on a remote node. This
+		 * would be expensive to fix and not of great significance.
+		 */
+		limit = ps.nr_mapped + ps.nr_slab + ps.nr_dirty +
+			ps.nr_unstable + total_swapcache_pages;
+		if (limit > sp_stat.prefetch_watermark[node]) {
+			node_clear(node, sp_stat.prefetch_nodes);
+			continue;
+		}
+	}
+
+	if (nodes_empty(sp_stat.prefetch_nodes))
+		goto out;
+
+	/* Survived all that? Hooray we can prefetch! */
+	ret = 1;
+out:
+	return ret;
+}
+
+/*
+ * trickle_swap is the main function that initiates the swap prefetching. It
+ * first checks to see if the busy flag is set, and does not prefetch if it
+ * is, as the flag implied we are low on memory or swapping in currently.
+ * Otherwise it runs until prefetch_suitable fails which occurs when the
+ * vm is busy, we prefetch to the watermark, or the list is empty.
+ */
+static enum trickle_return trickle_swap(void)
+{
+	enum trickle_return ret = TRICKLE_DELAY;
+	struct swapped_entry *entry;
+	struct list_head *mru = NULL;
+
+	if (!swap_prefetch)
+		return ret;
+
+	for ( ; ; ) {
+		enum trickle_return got_page;
+		swp_entry_t swp_entry;
+		int node;
+
+		if (!prefetch_suitable())
+			break;
+
+		/* Check we haven't iterated over everything */
+		if (unlikely(swapped.list.next == mru))
+			break;
+
+		spin_lock(&swapped.lock);
+		if (list_empty(&swapped.list)) {
+			ret = TRICKLE_FAILED;
+			spin_unlock(&swapped.lock);
+			goto out;
+		}
+		entry = list_entry(swapped.list.next,
+			struct swapped_entry, swapped_list);
+		node = entry->node;
+		if (!node_isset(node, sp_stat.prefetch_nodes)) {
+			/*
+			 * We found an entry that belongs to a node that is
+			 * not suitable for prefetching so skip it, storing
+			 * the mru position if necessary

mm/swap_prefetch.c new file +6 -0

+		got_page = trickle_swap_cache_async(swp_entry, node);
+		switch (got_page) {
+		case TRICKLE_FAILED:
+			break;
+		case TRICKLE_SUCCESS:
+			sp_stat.prefetched_pages++;

mm/swap_prefetch.c new file +6 -0

+				swapped.list.next = mru;
+		spin_unlock(&swapped.lock);
+	}
+	if (sp_stat.prefetched_pages) {
+		lru_add_drain();
+		sp_stat.prefetched_pages = 0;

mm/swap_prefetch.c new file +58 -0

+	do {
+		try_to_freeze();
+
+		/*
+		 * TRICKLE_FAILED implies no entries left - we do not schedule
+		 * a wakeup, and further delay the next one.
+		 */
+		if (trickle_swap() == TRICKLE_FAILED)
+			schedule_timeout_interruptible(MAX_SCHEDULE_TIMEOUT);
+		clear_last_prefetch_free();
+		schedule_timeout_interruptible(PREFETCH_DELAY);
+	} while (!kthread_should_stop());
+
+	return 0;
+}
+
+/*
+ * Create kmem cache for swapped entries
+ */
+void __init prepare_swap_prefetch(void)
+{
+	pg_data_t *pgdat;
+	int node;
+
+	swapped.cache = kmem_cache_create("swapped_entry",
+		sizeof(struct swapped_entry), 0, SLAB_PANIC, NULL, NULL);
+
+	/*
+	 * Set max number of entries to 2/3 the size of physical ram  as we
+	 * only ever prefetch to consume 2/3 of the ram.
+	 */
+	swapped.maxcount = nr_free_pagecache_pages() / 3 * 2;
+
+	for_each_pgdat(pgdat) {
+		unsigned long present;
+
+		present = pgdat->node_present_pages;
+		if (!present)
+			continue;
+		node = pgdat->node_id;
+		sp_stat.prefetch_watermark[node] += present / 3 * 2;
+	}
+}
+
+static int __init kprefetchd_init(void)
+{
+	kprefetchd_task = kthread_run(kprefetchd, NULL, "kprefetchd");
+
+	return 0;
+}
+
+static void __exit kprefetchd_exit(void)
+{
+	kthread_stop(kprefetchd_task);
+}
+
+module_init(kprefetchd_init);
+module_exit(kprefetchd_exit);

busy Con Kolivas wrote:

- Looking a lot better from an impact-on-rest-of-vm code wise inspection.

I got a couple of suggestions to make it even better.

- I still have big reservations about it. For example the fact that if you thrash memory and force everything to swap out, then exit your memory hog, it won't do anything if you just happened to cat bigfile > /dev/null

- Then, it has the potential to make *useful* swapping much less useful (ie. it will page back in your unused programs and libraries, which will kick out unmapped pagecache on desktop workloads).

- It does not appear to necessarily solve the updatedb problem.

- People complaining about their browser getting swapped out of their 1GB+ desktop systems due to a midnight cron run must be angering the VM gods. I'd rather try to work out what to sacrifice in order to appease them before sending another one up there to beat them into submission.

Sorry to sound negative about it.

Lucky for you nobody listens to me.

Quoted 1 line · Nick Piggin

busy Con Kolivas wrote:

busy? that's an interesting mua comment...

Quoted 1 line

- Looking a lot better from an impact-on-rest-of-vm code wise inspection.

That's good to hear, thanks.

Quoted 12 lines

I got a couple of suggestions to make it even better.

- I still have big reservations about it. For example the fact that if you thrash memory and force everything to swap out, then exit your memory hog, it won't do anything if you just happened to cat bigfile > /dev/null

- Then, it has the potential to make *useful* swapping much less useful (ie. it will page back in your unused programs and libraries, which will kick out unmapped pagecache on desktop workloads).

- It does not appear to necessarily solve the updatedb problem.

Quoted 4 lines

- People complaining about their browser getting swapped out of their 1GB+ desktop systems due to a midnight cron run must be angering the VM gods. I'd rather try to work out what to sacrifice in order to appease them before sending another one up there to beat them into submission.

I really don't want to go throwing out pagecache without some smart semantics and then swap in random stuff that could be crap I agree. The answer to this

is for the vm itself to have an ageing algorithm like the clockpro stuff which does this in a smart way. It could certainly age away the updatedb wrinkles and leave some free ram - which would help/be helped by prefetching.

I don't think I've ever said it fixes the updatedb debacle. Updatedb gets to

rule another day, but that does not constitute every swap workload out there. It helps my daily workloads, and as you might have missed, others have reported demonstrable benefits (and not just the "it seems faster" type).

Quoted 2 lines

Sorry to sound negative about it.

Well you're honest and that's worth respecting.

Quoted 2 lines

Lucky for you nobody listens to me.

After some thought I've decided I ain't touching that one.

Well at least you do.... Just to be sure, you did see my comments through the code right?

I really don't want to go throwing out pagecache without some smart semantics and then swap in random stuff that could be crap I agree. The answer to this is for the vm itself to have an ageing algorithm like the clockpro stuff which does this in a smart way. It could certainly age away the updatedb wrinkles and leave some free ram - which would help/be helped by prefetching.

Quoted 6 lines · Con Kolivas

I really don't want to go throwing out pagecache without some smart semantics and then swap in random stuff that could be crap I agree. The answer to this is for the vm itself to have an ageing algorithm like the clockpro stuff which does this in a smart way. It could certainly age away the updatedb wrinkles and leave some free ram - which would help/be helped by prefetching.

AFAIK clockpro will not leave free ram, will it?

Getting a little hand-wavy; I don't think the updatedb problem needs to be fixed by a really fancy page reclaim algorithm (IMO, and that's not to say that a fancy reclaim algorithm wouldn't be nice for other reasons). Just small improvements here and there, and there will always be a tradeoff between throughput and interactive pagein latency so in the end it might need a tunable (hey there is one - maybe it needs to be improved)

mm/page_alloc.c int zone_watermark_ok(struct zone *z, in · line 854

Quoted 5 lines · busy Con Kolivas

mm/page_alloc.c +4 -0

+	/* Swap prefetching is delayed if any watermark is low */
+	delay_swap_prefetch();
+
+	return 0;
 }

Do we really need to delay here? We do the watermark check anyway and it would eliminate a hot cacheline bouncing site and further reduce impact on vm code.

mm/swap_prefetch.c line 35

Quoted 1 line

mm/swap_prefetch.c new file +1 -0

+	struct radix_tree_root	swap_tree;	/* Lookup tree of pages */

Umm... what is swap_tree for, exactly?

mm/swap_prefetch.c line 65

Quoted 3 lines

mm/swap_prefetch.c new file +3 -0

+	__set_bit(0, &swapped.busy);
+}
+

Test this first so you don't bounce the cacheline around in page reclaim too much.

mm/swap_prefetch.c line 108

Quoted 2 lines

mm/swap_prefetch.c new file +2 -0

+		if (list_empty(&swapped.list))
+			wake_up_process(kprefetchd_task);

Move this wake up outside the swapped.lock to keep lock hold times down.

mm/swap_prefetch.c line 128

Quoted 2 lines

mm/swap_prefetch.c new file +2 -0

+	if (unlikely(!spin_trylock_irqsave(&swapped.lock, flags)))
+		return;

You never really hold swapped.lock long do you? By the time you disable interrupts and hit the cacheline here, if it is contended you may as well wait the few extra cycles for it to become unlocked no?

mm/swap_prefetch.c line 193

Quoted 1 line

mm/swap_prefetch.c new file +1 -0

+	page = __alloc_pages(GFP_HIGHUSER & ~__GFP_WAIT, 0, zonelist);

We have an alloc_pages_node for this.

The whole function reminds me of read_swap_cache_async. I wonder if there could be some sharing, or at least format it similarly and use things like find_get_page rather than open coding?

mm/swap_prefetch.c line 271

Quoted 4 lines

mm/swap_prefetch.c new file +4 -0

+		if (z->pages_high * 3 > free) {
+			node_clear(node, sp_stat.prefetch_nodes);
+			continue;
+		}

This ignores the reserve ratio stuff.

Doing this in pagevecs should improve icache utilisation and locking efficiency. However at this stage you probably don't need to worry about that.

mm/swap_prefetch.c line 404

Quoted 3 lines

mm/swap_prefetch.c new file +3 -0

+	if (mru) {
+		spin_lock(&swapped.lock);
+			if (likely(mru))

Why do you need to retest mru here?

The list manipulation in this routine is a bit ugly. You should be able to do basically the whole thing without touching .next or .prev (except maybe to find the initial entry) shouldn't you?

mm/swap_prefetch.c line 420

Quoted 2 lines

mm/swap_prefetch.c new file +2 -0

+	sys_ioprio_set(IOPRIO_WHO_PROCESS, 0, IOPRIO_CLASS_IDLE);
+

What happens if your app suddenly faults the page while it is being read in? Gets stuck with low prio still, I guess.

Probably not a big deal.

Can you make it delay prefetch if the swap device is busy as well?

Quoted 4 lines · Nick Piggin

mm/swap_prefetch.c line 35

Quoted 1 line · busy Con Kolivas

mm/swap_prefetch.c new file +1 -0

+	struct radix_tree_root	swap_tree;	/* Lookup tree of pages */

Umm... what is swap_tree for, exactly?

To avoid ...

/me looks around

It's because...

/me scratches head

wtf..

/me comes up with the answer

legacy that must die

Quoted 4 lines

+/*
+ * We check to see no part of the vm is busy. If it is this will interrupt
+ * trickle_swap and wait another PREFETCH_DELAY. Purposefully racy.
+ */

mm/swap_prefetch.c line 65

Quoted 5 lines

mm/swap_prefetch.c new file +5 -0

+inline void delay_swap_prefetch(void)
+{
+	__set_bit(0, &swapped.busy);
+}
+

Test this first so you don't bounce the cacheline around in page reclaim too much.

Nick Piggin writes:

[...]

Quoted 4 lines

Quoted 4 lines

+/*
+ * We check to see no part of the vm is busy. If it is this will interrupt + * trickle_swap and wait another PREFETCH_DELAY. Purposefully racy. + */

Quoted 8 lines

mm/swap_prefetch.c line 65

Quoted 5 lines

mm/swap_prefetch.c new file +5 -0

+inline void delay_swap_prefetch(void)
+{
+	__set_bit(0, &swapped.busy);
+}
+

Test this first so you don't bounce the cacheline around in page reclaim too much.

Shouldn't we have special macros/inlines for this? Like, e.g.,

static inline void __set_bit_weak(int nr, volatile unsigned long * addr)

{
        if (!__test_bit(nr, addr))
                __set_bit(nr, addr);
}

? These test-then-set sequences start to proliferate throughout the code.

(/me looks at PJ pleadingly)

Quoted 1 line

(/me looks at PJ pleadingly)

So much to do, so little time ...

Maybe in a few days I can fit it in.

Hi,

mm/swap_prefetch.c line 76

Quoted 7 lines · Con Kolivas

mm/swap_prefetch.c new file +7 -0

+void add_to_swapped_list(struct page *page)
+{
+	struct swapped_entry *entry;
+	unsigned long index;
+
+	spin_lock(&swapped.lock);
+	if (swapped.count >= swapped.maxcount) {

Assume x86 system with 8G memory, swapped_maxcount is maybe 5G+ here. Then, swapped_entry can consume 5G/PAGE_SIZE * 16bytes = 10 M byte more slabs from ZONE_NORMAL. Could you add check like this?
==
void add_to_swapped_list(struct page *page)

{
	<snip>
	if (!swap_prefetch)
		return;
	spin_lcok(&spwapped.lock);
}

==