Proof of concept: sorting per-cpu-page lists to reduce memory fragmentation

Hi,

Right now, the per-cpu page lists are interfering somewhat with the buddy allocator in terms of keeping the free memory pool unfragmented. This proof-of-concept patch (just to show the idea) tries to improve that situation by sorting the per-cpu page lists by physical address, with the idea that when the pcp list gives a chunk of itself back to the global pool, the chunk it gives back isn't random but actually very localized, if not already containing contiguous parts.. as opposed to pure random ordering.

Now, there's some issues I need to resolve before I can really propose this for merging:
1) Measuring success. Measuring fragmentation is a *hard* problem. Measurements I've done so far tend to show a little improvement, but that's very subjective since it's basically impossible to get reproducable results. Ideas on how to measure this are VERY welcome
2) Cache locality; the head of the pcp list in theory is cache hot; the current code doesn't take that into account. It's easy to not sort the, say, first 5 pages though; not done in the current implementation

The patch below implements this, and has a hacky sysreq to print cpu 0's pcp list out (I use this to verify that the sort works).

I'm posting this to get early feedback/comments on the approach; I fully realize that the code is far from perfect obviously...

---
 arch/x86/kernel/process_64.c |    3 +
 drivers/char/sysrq.c         |   30 +++++++++++++-
 mm/page_alloc.c              |   87 ++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 118 insertions(+), 2 deletions(-)

index 91dc9c1..341a775 100644
@@ -158,6 +158,8 @@ static inline void play_dead(void)
 }
 #endif /* CONFIG_HOTPLUG_CPU */
 
+extern void sort_pcp_list(void);
+
 /*
  * The idle thread. There's no useful work to be
  * done, so just try to conserve power and have a

@@ -181,6 +183,7 @@ void cpu_idle(void)
 	/* endless idle loop with no priority at all */
 	while (1) {
 		tick_nohz_stop_sched_tick();
+		sort_pcp_list();
 		while (!need_resched()) {
 			void (*idle)(void);
 

index de60e1e..21e42b5 100644
@@ -148,6 +148,32 @@ static struct sysrq_key_op sysrq_reboot_op = {
 	.enable_mask	= SYSRQ_ENABLE_BOOT,
 };
 
+extern void print_pcp_list(unsigned int cpu);
+extern void sort_pcp_list(void);
+
+static void sysrq_handle_memdump(int key, struct tty_struct *tty)
+{
+	 print_pcp_list(0);
+}
+static struct sysrq_key_op sysrq_memdump_op = {
+	.handler	= sysrq_handle_memdump,
+	.help_msg	= "memdumpY",
+	.action_msg	= "Dumping",
+	.enable_mask	= SYSRQ_ENABLE_BOOT,
+};
+
+static void sysrq_handle_memsort(int key, struct tty_struct *tty)
+{
+	sort_pcp_list();
+}
+static struct sysrq_key_op sysrq_memsort_op = {
+	.handler	= sysrq_handle_memsort,
+	.help_msg	= "memsortZ",
+	.action_msg	= "Sorting",
+	.enable_mask	= SYSRQ_ENABLE_BOOT,
+};
+
+
 static void sysrq_handle_sync(int key, struct tty_struct *tty)
 {
 	emergency_sync();

@@ -357,8 +383,8 @@ static struct sysrq_key_op *sysrq_key_table[36] = {
 	&sysrq_showstate_blocked_op,	/* w */
 	/* x: May be registered on ppc/powerpc for xmon */
 	NULL,				/* x */
-	NULL,				/* y */
-	NULL				/* z */
+	&sysrq_memdump_op,		/* y */
+	&sysrq_memsort_op		/* z */
 };
 
 /* key2index calculation, -1 on invalid index */

1.5.4.5

--
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 really hate the idea of doing stuff in the idle thread. It just destroys your predictability and reproduceability.

I'll kick myself for saying this because I dislike the using any CPU cycles are on anti-fragmentation heuristics ;) But one idea I had that you might want to look into if you're looking into this area is to instead check whether a given page is on a pcp list when checking for buddies. If it is, then you can perhaps flush anything from all pages out of all pcp lists, to just that single page from a given pcp list.

For now you could probably use page_count == 0 (&&!PageBuddy) as an heuristic. I actually have a patch that I want to merge, which allows page allocations without messing with page_count to avoid some atomic allocations in things like slab.... so you may eventually need a new page flag there if the idea is a success.

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