allocate page caches pages in round robin fasion
Subsystems (4)
PATCH 1/1 allocate page caches pages in round robin fasion
[ugg, attach the patch this time]
On a NUMA machine, page cache pages should be spread out across the system since they're generally global in nature and can eat up whole nodes worth of memory otherwise. This can end up hurting performance since jobs will have to make off node references for much or all of their non-file data.
The patch works by adding an alloc_page_round_robin routine that simply allocates on successive nodes each time its called, based on the value of a per-cpu variable modulo the number of nodes. The variable is per-cpu to avoid cacheline contention when many cpus try to do page cache allocations at once.
After dd if=/dev/zero of=/tmp/bigfile bs=1G count=2 on a stock kernel:
Node 7 MemUsed: 49248 kB Node 6 MemUsed: 42176 kB Node 5 MemUsed: 316880 kB Node 4 MemUsed: 36160 kB Node 3 MemUsed: 45152 kB Node 2 MemUsed: 50000 kB Node 1 MemUsed: 68704 kB Node 0 MemUsed: 2426256 kB
and after the patch:
Node 7 MemUsed: 328608 kB Node 6 MemUsed: 319424 kB Node 5 MemUsed: 318608 kB Node 4 MemUsed: 321600 kB Node 3 MemUsed: 319648 kB Node 2 MemUsed: 327504 kB Node 1 MemUsed: 389504 kB Node 0 MemUsed: 744752 kB
Thanks,
Jesse
===== include/linux/gfp.h 1.18 vs edited =====
include/linux/gfp.h +2 -0
@@ -86,6 +86,8 @@ NODE_DATA(nid)->node_zonelists + (gfp_mask & GFP_ZONEMASK)); } +extern struct page *alloc_page_round_robin (unsigned int gfp_mask); +#ifdef CONFIG_NUMA extern struct page *alloc_pages_current (unsigned gfp_mask,unsigned order);
===== include/linux/pagemap.h 1.43 vs edited =====
include/linux/pagemap.h +2 -2
@@ -52,12 +52,12 @@static inline struct page *page_cache_alloc (struct address_space *x) { -return alloc_pages (mapping_gfp_mask (x),0 ); +return alloc_page_round_robin (mapping_gfp_mask (x)); }static inline struct page *page_cache_alloc_cold (struct address_space *x) { -return alloc_pages (mapping_gfp_mask (x)|__GFP_COLD,0 ); +return alloc_page_round_robin (mapping_gfp_mask (x)|__GFP_COLD); }typedef int filler_t (void *,struct page *);
===== mm/page_alloc.c 1.224 vs edited =====
mm/page_alloc.c +19 -0
@@ -31,6 +31,7 @@#include <linux/topology.h> #include <linux/sysctl.h> #include <linux/cpu.h> +#include <linux/percpu.h> #include <asm/tlbflush.h>
@@ -41,6 +42,7 @@long nr_swap_pages;int numnodes =1 ;int sysctl_lower_zone_protection =0 ; +static DEFINE_PER_CPU(int, next_rr_node);EXPORT_SYMBOL (totalram_pages);EXPORT_SYMBOL (nr_swap_pages);
@@ -577,6 +579,23 @@ }return page; } + +/** +* alloc_page_round_robin - distribute pages across nodes +* @gfp_mask: GFP_* flags +* +* alloc_page_round_robin() will simply allocate from a different node +* than was allocated from in the last call using the next_rr_node variable. +* We use __get_cpu_var since we don't care about disabling preemption (we're +* using a mod function so nid will always be less than numnodes). A per-cpu +* variable will make round robin allocations scale a bit better. +*/ +struct page *alloc_page_round_robin (unsigned int gfp_mask) +{ +return alloc_pages_node (__get_cpu_var (next_rr_node)++ % numnodes, + gfp_mask,0 ); +} +/* * This is the 'heart' of the zoned buddy allocator.
mm/page_alloc.c line 598
Quoted 6 lines · Jesse Barnes
mm/page_alloc.c +6
-0+struct page *alloc_page_round_robin (unsigned int gfp_mask) +{ +return alloc_pages_node (__get_cpu_var (next_rr_node)++ % numnodes, + gfp_mask,0 ); +} +
Interesting. This may attempt to allocate from offlined nodes, assuming one adds on sufficient hotplug bits atop mainline and/or -mm. The following almost does it hotplug-safe except that it needs to enter the allocator with preemption disabled and drop the preempt_count internally to it.
static struct page *alloc_page_round_robin(unsigned gfp_mask)
{
int nid, next_nid, *rr_node = &__get_cpu_var(next_rr_node);
nid = *rr_node;
next_nid = next_node(nid, node_online_map);
if (next_nid >= MAX_NR_NODES)
*rr_node = first_node(node_online_map);
else
*rr_node = next_nid;
return alloc_pages_node(nid, gfp_mask, 0);
}I suspect we are better off punting this in the direction of hotplug people than trying to address it ourselves. I think we should go with this now, as the node hotplug bits are yet to hit the tree.
-- wli
Quoted 5 lines · William Lee Irwin III
Interesting. This may attempt to allocate from offlined nodes, assuming one adds on sufficient hotplug bits atop mainline and/or -mm. The following almost does it hotplug-safe except that it needs to enter the allocator with preemption disabled and drop the
preempt_countinternally to it.
Can we make alloc_pages_node take offline nodes instead? Maybe it could just allocate from the next nearest node or something?
Quoted 3 lines
I suspect we are better off punting this in the direction of hotplug people than trying to address it ourselves. I think we should go with this now, as the node hotplug bits are yet to hit the tree.
Yeah, agreed.
Jesse
Quoted 5 lines · William Lee Irwin III
Quoted 5 lines
Interesting. This may attempt to allocate from offlined nodes, assuming one adds on sufficient hotplug bits atop mainline and/or -mm. The following almost does it hotplug-safe except that it needs to enter the allocator with preemption disabled and drop the
preempt_countinternally to it.
Quoted 2 lines · Jesse Barnes
Can we make
alloc_pages_nodetake offline nodes instead? Maybe it could just allocate from the next nearest node or something?
I don't think we should do anything but point it out for those writing the hotplug patches to look for. There are enough interactions in general we're not even looking for that making the whole tree hotplug-safe is hopeless unless the hotplug ppl get involved with e.g. more complete patches, being able to actually test things, etc.
Quoted 3 lines · William Lee Irwin III
Quoted 3 lines
I suspect we are better off punting this in the direction of hotplug people than trying to address it ourselves. I think we should go with this now, as the node hotplug bits are yet to hit the tree.
Quoted 1 line · Jesse Barnes
Yeah, agreed.
Yes... their patch, their implementation burden.
-- wli
Quoted 10 lines
On a NUMA machine, page cache pages should be spread out across the system since they're generally global in nature and can eat up whole nodes worth of memory otherwise. This can end up hurting performance since jobs will have to make off node references for much or all of their non-file data.
The patch works by adding an
alloc_page_round_robinroutine that simply allocates on successive nodes each time its called, based on the value of a per-cpu variable modulo the number of nodes. The variable is per-cpu to avoid cacheline contention when many cpus try to do page cache allocations at once.
I really don't think this is a good idea - you're assuming there's really no locality of reference, which I don't think is at all true in most cases.
If we round-robin it ... surely 7/8 of your data (on your 8 node machine) will ALWAYS be off-node ? I thought we discussed this at KS/OLS - what is needed is to punt old pages back off onto another node, rather than swapping them out. That way all your pages are going to be local.
Quoted 11 lines
After dd if=/dev/zero of=/tmp/bigfile bs=1G count=2 on a stock kernel:
Node 7 MemUsed: 49248 kB Node 6 MemUsed: 42176 kB Node 5 MemUsed: 316880 kB Node 4 MemUsed: 36160 kB Node 3 MemUsed: 45152 kB Node 2 MemUsed: 50000 kB Node 1 MemUsed: 68704 kB Node 0 MemUsed: 2426256 kBand after the patch:
Quoted 8 lines
Node 7 MemUsed: 328608 kB Node 6 MemUsed: 319424 kB Node 5 MemUsed: 318608 kB Node 4 MemUsed: 321600 kB Node 3 MemUsed: 319648 kB Node 2 MemUsed: 327504 kB Node 1 MemUsed: 389504 kB Node 0 MemUsed: 744752 kB
OK, so it obviously does something ... but is the dd actually faster? I'd think it's slower ...
M.
PS. I think it prob makes sense to make the *receiving* node's kswapd do the transfer if possible for work distribution reasons ... however I'm pretty sure there are some locking assumptions that mean this won't be easy / possible.
Quoted 2 lines · Martin J. Bligh
I really don't think this is a good idea - you're assuming there's really no locality of reference, which I don't think is at all true in most cases.
No, not at all, just that locality of reference matters more for stack and anonymous pages than it does for page cache pages. I.e. we don't want a node to be filled up with page cache pages causing all other memory references from the process to be off node.
Quoted 4 lines
If we round-robin it ... surely 7/8 of your data (on your 8 node machine) will ALWAYS be off-node ? I thought we discussed this at KS/OLS - what is needed is to punt old pages back off onto another node, rather than swapping them out. That way all your pages are going to be local.
That gets complicated pretty quickly I think. We don't want to constantly shuffle pages between nodes with kswapd, and there's also the problem of deciding when to do it.
Quoted 2 lines
OK, so it obviously does something ... but is the dd actually faster? I'd think it's slower ...
Sure, it's probably a tiny bit slower, but assume that dd actually had some compute work to do after it read in a file (like an encoder or fp app), w/o the patch, most of it's time critical references would be off node. The important thing is to get the file data in memory, since that'll be way faster than reading from disk, but it doesn't really matter *where* it is in memory. Especially since we want an app's code and data to be node local.
Jesse
Quoted 7 lines
Quoted 2 lines
I really don't think this is a good idea - you're assuming there's really no locality of reference, which I don't think is at all true in most cases.
No, not at all, just that locality of reference matters more for stack and anonymous pages than it does for page cache pages. I.e. we don't want a node to be filled up with page cache pages causing all other memory references from the process to be off node.
Does that actually happen though? Looking at the current code makes me think it'll keep some pages free on all nodes at all times, and if kswapd does it's job, we'll never fall back across nodes. Now ... I think that's broken, but I think that's what currently happens - that was what we discussed at KS ... I might be misreading it though, I should test it.
Even if that's not true, allocating all your most recent stuff off-node is still crap (so either way, I'd agree the current situation is broken), but I don't think the solution is to push ALL your accesses (with n-1/n probability) off-node ... we need to be more careful than that ...
Quoted 8 lines
Quoted 4 lines
If we round-robin it ... surely 7/8 of your data (on your 8 node machine) will ALWAYS be off-node ? I thought we discussed this at KS/OLS - what is needed is to punt old pages back off onto another node, rather than swapping them out. That way all your pages are going to be local.
That gets complicated pretty quickly I think. We don't want to constantly shuffle pages between nodes with kswapd, and there's also the problem of deciding when to do it.
When the other zone is above the high watermark (or even some newer watermark, ie it has lots of free pages). If we have any sort of locality of reference, we want the most recently used pages on-node, and less recently ones off-node, and then the least-recently used on disk.
Quoted 9 lines
Quoted 2 lines
OK, so it obviously does something ... but is the dd actually faster? I'd think it's slower ...
Sure, it's probably a tiny bit slower, but assume that dd actually had some compute work to do after it read in a file (like an encoder or fp app), w/o the patch, most of it's time critical references would be off node. The important thing is to get the file data in memory, since that'll be way faster than reading from disk, but it doesn't really matter *where* it is in memory. Especially since we want an app's code and data to be node local.
Not sure I'd agree with that - it's the same problem as swappiness on a global basis for non-NUMA machines. We want the pages we're using MOST to be local, the others to be not-local, and that doesn't equate (necessarily) to whether it's pagecache or not. Shared pages could indeed be dealt with differently, and spread more global ... but I don't agree that pagecache pages equate 1-1 with being globally shared - in fact, I think most often the opposite is true.
So when we're making such decisions, we need to consider the usage of a page in more careful of a way than whether it's pagecache or not. page->mapcount would be a better start, I think, than simply pagecache or not. Spreading pagecache around will just make the most common case slower, I think.
I understand the desire to make node mem pressures equalize somewhat - having dynamically altered fallback schemes for NUMA nodes to the node with the most free mem, etc would help ... but we need to be really careful what we keep local, and what we push remote. Most apps seem to have fairly good locality
M.
PS. The obvious exceptions to these rules are shmem and shared libs ... shmem should probably go round-robin amongst its users nodes by default, and shared libs replicate ... I'll look at fixing up shmem at least.
Quoted 9 lines · Martin J. Bligh
Quoted 8 lines
Quoted 3 lines
I really don't think this is a good idea - you're assuming there's really no locality of reference, which I don't think is at all true in most cases.
No, not at all, just that locality of reference matters more for stack and anonymous pages than it does for page cache pages. I.e. we don't want a node to be filled up with page cache pages causing all other memory references from the process to be off node.
Quoted 5 lines
Does that actually happen though? Looking at the current code makes me think it'll keep some pages free on all nodes at all times, and if kswapd does it's job, we'll never fall back across nodes. Now ... I think that's broken, but I think that's what currently happens - that was what we discussed at KS ... I might be misreading it though, I should test it.
Not nearly enough pages for any sizeable app though. Maybe the behavior could be configurable?
Quoted 4 lines
Even if that's not true, allocating all your most recent stuff off-node is still crap (so either way, I'd agree the current situation is broken), but I don't think the solution is to push ALL your accesses (with n-1/n probability) off-node ... we need to be more careful than that ...
Only page cache references...
Quoted 7 lines
Not sure I'd agree with that - it's the same problem as swappiness on a global basis for non-NUMA machines. We want the pages we're using MOST to be local, the others to be not-local, and that doesn't equate (necessarily) to whether it's pagecache or not. Shared pages could indeed be dealt with differently, and spread more global ... but I don't agree that pagecache pages equate 1-1 with being globally shared - in fact, I think most often the opposite is true.
Yeah, that's a good point. That argues for configurability too. We should behave differently depending on whether the page is shared or not.
Quoted 3 lines
PS. The obvious exceptions to these rules are shmem and shared libs ... shmem should probably go round-robin amongst its users nodes by default, and shared libs replicate ... I'll look at fixing up shmem at least.
Cool, that would be good.
Jesse
--Jesse Barnes <[email protected]> wrote (on Friday, August 13, 2004 09:34:20 -0700):
Quoted 10 lines · Martin J. Bligh
Quoted 9 lines
Quoted 8 lines
Quoted 3 lines
I really don't think this is a good idea - you're assuming there's really no locality of reference, which I don't think is at all true in most cases.
No, not at all, just that locality of reference matters more for stack and anonymous pages than it does for page cache pages. I.e. we don't want a node to be filled up with page cache pages causing all other memory references from the process to be off node.
Quoted 8 lines
Quoted 5 lines
Does that actually happen though? Looking at the current code makes me think it'll keep some pages free on all nodes at all times, and if kswapd does it's job, we'll never fall back across nodes. Now ... I think that's broken, but I think that's what currently happens - that was what we discussed at KS ... I might be misreading it though, I should test it.
Not nearly enough pages for any sizeable app though. Maybe the behavior could be configurable?
Well, either we're:
1. Falling back and putting all our most recent accesses off-node.
or.
2. Not falling back and only able to use one node's memory for any one (single threaded) app.
Either situation is crap, though I'm not sure which turd we picked right now ... I'd have to look at the code again ;-) I thought it was 2, but I might be wrong.
Quoted 6 lines
Quoted 4 lines
Even if that's not true, allocating all your most recent stuff off-node is still crap (so either way, I'd agree the current situation is broken), but I don't think the solution is to push ALL your accesses (with n-1/n probability) off-node ... we need to be more careful than that ...
Only page cache references...
Yeah, depends how important those are to the app though ;-) I absolutely agree with you that the current situation is broken ... we need to do *something*.
Quoted 10 lines
Quoted 7 lines
Not sure I'd agree with that - it's the same problem as swappiness on a global basis for non-NUMA machines. We want the pages we're using MOST to be local, the others to be not-local, and that doesn't equate (necessarily) to whether it's pagecache or not. Shared pages could indeed be dealt with differently, and spread more global ... but I don't agree that pagecache pages equate 1-1 with being globally shared - in fact, I think most often the opposite is true.
Yeah, that's a good point. That argues for configurability too. We should behave differently depending on whether the page is shared or not.
Right. An app that mmap'ed a big file then thrashed on it would be a good example, though simple read-write heavily across a small fileset would do much same thing.
M.
Quoted 27 lines · Martin J. Bligh
--Jesse Barnes <[email protected]> wrote (on Friday, August 13, 2004 09:34:20 -0700):
Quoted 11 lines · Martin J. Bligh
Quoted 10 lines
Quoted 9 lines
Quoted 4 lines
I really don't think this is a good idea - you're assuming there's really no locality of reference, which I don't think is at all true in most cases.
No, not at all, just that locality of reference matters more for stack and anonymous pages than it does for page cache pages. I.e. we don't want a node to be filled up with page cache pages causing all other memory references from the process to be off node.
Quoted 7 lines
Quoted 5 lines
Does that actually happen though? Looking at the current code makes me think it'll keep some pages free on all nodes at all times, and if kswapd does it's job, we'll never fall back across nodes. Now ... I think that's broken, but I think that's what currently happens - that was what we discussed at KS ... I might be misreading it though, I should test it.
Not nearly enough pages for any sizeable app though. Maybe the behavior could be configurable?
Well, either we're:
1. Falling back and putting all our most recent accesses off-node.
Quoted 8 lines
or.
2. Not falling back and only able to use one node's memory for any one (single threaded) app.
Either situation is crap, though I'm not sure which turd we picked right now ... I'd have to look at the code again ;-) I thought it was 2, but I might be wrong.
I'm looking at this now. We are doing 1 currently.
There are a couple of issues. The first is that you need to minimise regressions for when working set size is bigger than the local node. The second is a fundamental tradeoff where purely FIFO touch patterns will never be allowed to expand past local node memory for any sane and simple (ie 2.6 worthy) scanning algorithms that I can think of.
I have a patch going now that just reclaims use-once file cache before going off node. Seems to help a bit for basic things that just push pagecache through the system. It definitely reduces remote allocations by several orders of magnitude for those cases.
Quoted 9 lines
Quoted 9 lines
Well, either we're:
1. Falling back and putting all our most recent accesses off-node.
or.
2. Not falling back and only able to use one node's memory for any one (single threaded) app.
Quoted 6 lines
Quoted 4 lines
Either situation is crap, though I'm not sure which turd we picked right now ... I'd have to look at the code again ;-) I thought it was 2, but I might be wrong.
I'm looking at this now. We are doing 1 currently.
In theory, yes. In practice, I have a feeling kswapd will keep us above the level of free memory where we'd fall back to another zone to allocate, won't it?
Quoted 2 lines
There are a couple of issues. The first is that you need to minimise regressions for when working set size is bigger than the local node.
Good point ... that is, indeed, a total bitch to fix.
Quoted 4 lines
I have a patch going now that just reclaims use-once file cache before going off node. Seems to help a bit for basic things that just push pagecache through the system. It definitely reduces remote allocations by several orders of magnitude for those cases.
Makes sense, but doesn't the same thing make sense on a global basis? I don't feel NUMA is anything magical here ...
M.
Quoted 14 lines
Quoted 14 lines
Quoted 13 lines
Well, either we're:
1. Falling back and putting all our most recent accesses off-node.
or.
2. Not falling back and only able to use one node's memory for any one (single threaded) app.
Either situation is crap, though I'm not sure which turd we picked right now ... I'd have to look at the code again ;-) I thought it was 2, but I might be wrong.
Quoted 5 lines
Quoted 1 line
I'm looking at this now. We are doing 1 currently.
In theory, yes. In practice, I have a feeling kswapd will keep us above the level of free memory where we'd fall back to another zone to allocate, won't it?
Nope - tested it. Buggered if I can see how that works, but it does ;-)
M.
Quoted 13 lines · Martin J. Bligh
Quoted 13 lines
Quoted 12 lines
Well, either we're:
1. Falling back and putting all our most recent accesses off-node.
or.
2. Not falling back and only able to use one node's memory for any one (single threaded) app.
Either situation is crap, though I'm not sure which turd we picked right now ... I'd have to look at the code again ;-) I thought it was 2, but I might be wrong.
Quoted 7 lines
Quoted 1 line
I'm looking at this now. We are doing 1 currently.
In theory, yes. In practice, I have a feeling kswapd will keep us above the level of free memory where we'd fall back to another zone to allocate, won't it?
Nope. Take a look at the first loop-through-the-zones in alloc_pages (preferably in akpm's tree that is cleaned up a bit).
We go through *all* zones first and allocate them down to pages_low before kicking kswapd.
I have tried kicking kswapd before going off node, but it frees memory really aggressively - so you're nearly left with a local alloc policy.
Quoted 7 lines
Quoted 3 lines
There are a couple of issues. The first is that you need to minimise regressions for when working set size is bigger than the local node.
Good point ... that is, indeed, a total bitch to fix.
At the end of the day we'll possibly just have to have a sysctl. I don't think all regressions could be eliminated completely. We'll see.
Quoted 10 lines
Quoted 5 lines
I have a patch going now that just reclaims use-once file cache before going off node. Seems to help a bit for basic things that just push pagecache through the system. It definitely reduces remote allocations by several orders of magnitude for those cases.
Makes sense, but doesn't the same thing make sense on a global basis? I don't feel NUMA is anything magical here ...
Didn't parse that. If you mean the transition from highmem->normal->dma zones, I don't think that should be treated in this way. Imagine small highmem zones for example. We have the lower zone protection in place for that case - and that is something that in turn isn't good for NUMA, because the SGI guys (I think) already ran into that and fixed it to be per-node only.