slab reclaim balancing
Quoted 3 lines
Slab caches no longer hold onto completely empty pages. Instead, pages are freed as soon as they have zero objects. This is possibly a performance hit for slabs which have constructors, but it's doubtful.
It could be a performance hit for slab with just one object - e.g the page sized names cache, used in every syscall that has a path name as a parameter.
Ed, have you benchmarked that there is no noticable slowdown?
e.g. test the time needed for stat("."). on UP, otherwise the SMP arrays would perform the caching.
--
Manfred
Quoted 3 lines · Ed Tomlinson
Quoted 3 lines
Slab caches no longer hold onto completely empty pages. Instead, pages are freed as soon as they have zero objects. This is possibly a performance hit for slabs which have constructors, but it's doubtful.
Quoted 6 lines · Manfred Spraul
It could be a performance hit for slab with just one object - e.g the page sized names cache, used in every syscall that has a path name as a parameter.
Ed, have you benchmarked that there is no noticable slowdown? e.g. test the time needed forstat("."). on UP, otherwise the SMP arrays would perform the caching.
This might need testing on large-memory 64-bit boxen for that, since ZONE_NORMAL pressure outweighs many other considerations on my boxen.
Cheers,
Bill
Quoted 4 lines · William Lee Irwin III
This might need testing on large-memory 64-bit boxen for that, since
ZONE_NORMALpressure outweighs many other considerations on my boxen.
Most of them will be SMP, correct? For SMP, 95% of the memory operations occur in the per-cpu arrays. I'm not sure if a slab is really the right backend behind the per-cpu arrays - perhaps a algorithms that's more aggressive toward finding freeable pages would be a better choice, even if it needs more cpu time for sorting/searching through the partially allocated pages.
--
Manfred
Quoted 5 lines · Manfred Spraul
Quoted 4 lines
Slab caches no longer hold onto completely empty pages. Instead, pages are freed as soon as they have zero objects. This is possibly a performance hit for slabs which have constructors, but it's doubtful.
Quoted 8 lines
It could be a performance hit for slab with just one object - e.g the page sized names cache, used in every syscall that has a path name as a parameter.
Ed, have you benchmarked that there is no noticable slowdown? e.g. test the time needed for
stat("."). on UP, otherwise the SMP arrays would perform the caching.
(What Ed said - we do hang onto one page. And I _have_ measured cost in kmem_cache_shrink...)
For those things, the caching should be performed in the page allocator. This way, when names_cache requests a cache-hot page, it may get a page which was very recently a (say) pagetable page, rather than restricting itself only to pages which used to be a names_cache page.
CPU caches are per-cpu global. So the hot pages list should be per-cpu global also.
Martin Bligh seems to have the patches up and running. It isn't very finetuned yet, but initial indications are promising:
Before:
Elapsed: 20.18s User: 192.914s System: 48.292s CPU: 1195.6%
After:
Elapsed: 19.798s User: 191.61s System: 43.322s CPU: 1186.4%
That's for a kernel compile.
And from the profiles, it appears that the benefit is coming from cache locality, not from the buddylist lock amortisation which we've also designed into those patches.
I need to stop being slack, and get that code into the pipeline.
Quoted 4 lines · Andrew Morton
(What Ed said - we do hang onto one page. And I _have_ measured cost in
kmem_cache_shrink...)
I totally agree about kmem_cache_shrink - it's total abuse that fs/dcache.c calls it regularly. It was intended to be called before module unload, or during ifdown, etc. On NUMA, it's probably worse, because it does an IPI to all cpus. dcache.c should not call kmem_cache_shrink, and kmem_cache_reap should be improved.
Quoted 8 lines
Before:
Elapsed: 20.18s User: 192.914s System: 48.292s CPU: 1195.6%After:
Elapsed: 19.798s User: 191.61s System: 43.322s CPU: 1186.4%That's for a kernel compile.
UP or SMP?
And was that the complete patch, or just the modification to slab.c?
I've made a microbenchmark of kmem_cache_alloc/free of 4 kb objects, on UP, AMD Duron:
1 object 4 objects
cur 145 cycles 662 cycles
patched 133 cycles 2733 cycles
Summary:
* for one object, the patch is a slight performance improvement. The reason is that the fallback from partial to free list in kmem_cache_alloc_one is avoided.
* the overhead of kmem_cache_grow/shrink is around 500 cycles, nearly a slowdown of factor 4. The cache had no constructor/destructor.
* everything cache hot state. [100 runs in a loop, loop overhead substracted. 98 or 99 runs completed in the given time, except for patched-4obj, where 24 runs completed in 2735 cycles, 72 in 2733 cycles]
For SMP and slabs that are per-cpu cached, the change could be right, because the arrays should absorb bursts. But I do not think that the change is the right approach for UP.
--
Manfred
Quoted 6 lines · Manfred Spraul
Quoted 4 lines · Andrew Morton
(What Ed said - we do hang onto one page. And I _have_ measured cost in
kmem_cache_shrink...)
Quoted 6 lines
I totally agree about
kmem_cache_shrink- it's total abuse thatfs/dcache.ccalls it regularly. It was intended to be called before module unload, or during ifdown, etc.
On NUMA, it's probably worse, because it does an IPI to all cpus.dcache.cshould not callkmem_cache_shrink, andkmem_cache_reapshould be improved.
Sorry, I meant kmem_cache_reap. It was the call into there from vmscan.c which was the problem. On my 4-way (which is fairly immune to lock contention for some reason), I was seeing *25%* contention on the spinlock inside the cache_chain_sem semaphore. With, of course, tons of context switching going on.
And it was giving a sort of turnstile effect, where each CPU needed to pass through kmem_cache_reap before entering page reclaim proper. Which maybe wasn't so bad in the 2.4 setup. But in 2.5 the VM is basically per-zone, so different CPUs can run reclaim against different zones with no contention of any form. This is especially important on NUMA.
But the above could have been solved in different ways, and there are still global effects with the requirement to prune slab. I expect that the batching and perhaps a per-slab exclusion mechanism will fix up any remaining problems.
Quoted 10 lines
Quoted 8 lines
Before:
Elapsed: 20.18s User: 192.914s System: 48.292s CPU: 1195.6%After:
Elapsed: 19.798s User: 191.61s System: 43.322s CPU: 1186.4%That's for a kernel compile.
UP or SMP?
And was that the complete patch, or just the modification toslab.c?
That is the effect of per-cpu hotlist within the page allocator on a 16- or 32-way NUMAQ.
It shows some of the benefit which we can get by carefully recycling known-to-be-hot pages back into places where the page is known to soon be touched by this CPU. Most of the gains were in do_anonymous_page, copy_foo_user(), zap_pte_range(), etc. Where you'd expect.
I expect to end up with two forms of page allocation and freeing:
alloc_hot_page/alloc_cold_page and free_hot_page/free_cold_page
Quoted 6 lines
I've made a microbenchmark of kmem_cache_alloc/free of 4 kb objects, on UP, AMD Duron:
1 object 4 objects
cur 145 cycles 662 cycles
patched 133 cycles 2733 cycles
Quoted 9 lines
Summary:
* for one object, the patch is a slight performance improvement. The reason is that the fallback from partial to free list inkmem_cache_alloc_oneis avoided.
* the overhead of kmem_cache_grow/shrink is around 500 cycles, nearly a slowdown of factor 4. The cache had no constructor/destructor.
* everything cache hot state. [100 runs in a loop, loop overhead substracted. 98 or 99 runs completed in the given time, except for patched-4obj, where 24 runs completed in 2735 cycles, 72 in 2733 cycles]
Was the microbenchmark actually touching the memory which it was allocating from slab? If so then yes, we'd expect to see cache misses against those cold pages coming out of the buddy.
Quoted 3 lines
For SMP and slabs that are per-cpu cached, the change could be right, because the arrays should absorb bursts. But I do not think that the change is the right approach for UP.
I'd suggest that we wait until we have slab freeing its pages into the hotlists, and allocating from them. That should pull things back.
Quoted 5 lines · Andrew Morton
Was the microbenchmark actually touching the memory which it was allocating from slab? If so then yes, we'd expect to see cache misses against those cold pages coming out of the buddy.
No, it was just measuring the cost of the kmem_cache_grow/shrink.
Btw, 140 cycles for kmem_cache_alloc+free is inflated - someone enabled kmem_cache_alloc_head() even in the no-debugging version. As expected, done by Andrea, who neither bothered to cc me, nor actually understood the code.
Quoted 9 lines
Quoted 4 lines
For SMP and slabs that are per-cpu cached, the change could be right, because the arrays should absorb bursts. But I do not think that the change is the right approach for UP.
I'd suggest that we wait until we have slab freeing its pages into the hotlists, and allocating from them. That should pull things back.
You are asking a interesting question:
The slab is by design far from LIFO - it tries to find pages with no allocated objects, that are possible to return to the page allocator. It doesn't try to optimize for cache hit rates.
Is that actually the right approach? For large objects, it would be possible to cripple the freeable slabs list, and to perform the cache hit optimization (i.e. per-cpu LIFO) in page_alloc.c, but that doesn't work with small objects.
On SMP, the per-cpu arrays are the LIFO and should give good cache hit rates. On UP, I haven't enabled them, because they could increase the internal fragmentation of the slabs.
Perhaps we should enable the arrays on UP, too, and thus improve the cache hit rates? If there is no increase in fragmentation, we could ignore it. Otherwise we could replace the 3-list Bonwick slab with another backend, something that's stronger at reducing the internal fragmentation.
--
Manfred
Quoted 8 lines · Manfred Spraul
Quoted 5 lines · Andrew Morton
Was the microbenchmark actually touching the memory which it was allocating from slab? If so then yes, we'd expect to see cache misses against those cold pages coming out of the buddy.
Quoted 6 lines
No, it was just measuring the cost of the kmem_cache_grow/shrink.
Btw, 140 cycles for kmem_cache_alloc+free is inflated - someone enabled
kmem_cache_alloc_head()even in the no-debugging version.
As expected, done by Andrea, who neither bothered to cc me, nor actually understood the code.
hm, OK. Sorry, I did not realise that you were this closely interested/involved with slab, so things have been sort of going on behind your back :(
Quoted 11 lines
Quoted 9 lines
Quoted 4 lines
For SMP and slabs that are per-cpu cached, the change could be right, because the arrays should absorb bursts. But I do not think that the change is the right approach for UP.
I'd suggest that we wait until we have slab freeing its pages into the hotlists, and allocating from them. That should pull things back.
You are asking a interesting question:
Quoted 8 lines
The slab is by design far from LIFO - it tries to find pages with no allocated objects, that are possible to return to the page allocator. It doesn't try to optimize for cache hit rates.
Is that actually the right approach? For large objects, it would be possible to cripple the freeable slabs list, and to perform the cache hit optimization (i.e. per-cpu LIFO) in
page_alloc.c, but that doesn't work with small objects.
Well with a, what? 100:1 speed ratio, we'll generally get best results from optimising for locality/recency of reference.
Quoted 9 lines
On SMP, the per-cpu arrays are the LIFO and should give good cache hit rates. On UP, I haven't enabled them, because they could increase the internal fragmentation of the slabs.
Perhaps we should enable the arrays on UP, too, and thus improve the cache hit rates? If there is no increase in fragmentation, we could ignore it. Otherwise we could replace the 3-list Bonwick slab with another backend, something that's stronger at reducing the internal fragmentation.
Definitely worthy of investigation. Memory sizes are increasing, and the cached-versus-noncached latencies are increasing. Both these say "optimise for cache hits".
Plus we'd lose a ton of ifdefs if we enabled it on UP as well...
Bill wrote a couple of handy slab-monitoring tools, btw.
http://www.zip.com.au/~akpm/linux/patches/ - I use bloatmeter.
Quoted 10 lines · Andrew Morton
Quoted 5 lines · Manfred Spraul
Andrew Morton wrote:
Btw, 140 cycles for kmem_cache_alloc+free is inflated - someone enabledkmem_cache_alloc_head()even in the no-debugging version.
As expected, done by Andrea, who neither bothered to cc me, nor actually understood the code.hm, OK. Sorry, I did not realise that you were this closely interested/involved with slab, so things have been sort of going on behind your back :(
Nor did I realize this... The reasoning behind quickly giving pages back to the system was fairly simple. Previous vm experiements showed that lazy freeing of pages from the lru was not a good performer. When the first versions of slablru went into mm we noticed that large numbers of pages (thousands) were free but not reclaimed. This was working as designed - the conclusion was that slablru was over designed and that lazy removal was probably not such a good idea. The slabasap patch that started this thread was the fix for this.
There is no dispute that in some cases it will be slower from a slab perspective. As Andrew and you have discussed there are things that can be done to speed things up. Is not the question really, "Are the vm and slab faster together when slab pages are freed asap?"
As it stands now we could remove quite a bit of code from slab. There is no longer a need for most of the kmem_cache_shrink family, nor is kmem_cache_reap needed any more. This simpilifes slab. If we also enable the per cpu arrays for UP the code is even cleaner (and hopefully faster).
Manfred, slab is currently using typedefs. Andrews has stated that he and Linus are trying to remove these from the kernel. When I code the cleanup patches for slabasap (provided it proves itself) shall I clean them out too?
Ed Tomlinson
Quoted 10 lines · Andrew Morton
Quoted 5 lines
Is that actually the right approach? For large objects, it would be possible to cripple the freeable slabs list, and to perform the cache hit optimization (i.e. per-cpu LIFO) in
page_alloc.c, but that doesn't work with small objects.Well with a, what? 100:1 speed ratio, we'll generally get best results from optimising for locality/recency of reference.
You misunderstood me:
AFAICS slab.c has 2 weaks spots:
* cache hit rates are ignored on UP, and for objects > PAGE_SIZE on both SMP and UP.
* freeable pages are not returned efficiently to page_alloc.c, neither on SMP nor on UP. On SMP, this is a big problems, because the cache_chain_semaphore is overloaded.
I just wanted to say that a hotlist in page_alloc.c is not able to replace a hotlist in slab.c, because many objects are smaller than page size. Both lists are needed.
--
Manfred
Quoted 4 lines · Ed Tomlinson
There is no dispute that in some cases it will be slower from a slab perspective. As
Andrew and you have discussed there are things that can be done to speed things up. Is not the question really, "Are the vm and slab faster together when slab pages are freed asap?"
Some caches are quite bursty - what about the 2 kB generic cache that is used for the MTU sized socket buffers? With interrupt mitigation enabled, I'd expect that a GigE nic could allocate a few dozend 2kb objects in every interrupt, and I don't think it's the right approach to
effectively disable the cache in slab.c for such loads.
I do not have many data points, but in a netbench run on 4-way Xeon, kmem_cache_free is called 5 million times/minute, and additional 4 million calls to kfree - I agree that _reap right now is bad, but IMHO it's questionable if the fix should be inside the hot-path of the allocator.
What about this approach:
* enable batching even on UP, with a LIFO array in front of the lists.
* After flushing a batch back into the lists, the number of free objects in the lists is calculated. If freeable pages exist and the number exceeds a target, then the freeable pages above the target are returned to the page buddy.
* The target of freeable pages is increased by kmem_cache_grow - if we had to get another page from gfp, then our own cache was too small.
Since the test for the number of freeable objects only happens after batching, i.e. in the worst case once for every 30 kmem_cache_free calls, it doesn't matter if it's a bit expensive.
Open problems:
* What about cache with large objects (>PAGE_SIZE, e.g. the bio MAX_PAGES object, or the 16 kb socket buffers used over loopback)? Right now, they are not cached in the per-cpu arrays, to reduce the memory pressure. If the list processing becomes slower, we would slow down these slab users. But OTHO if you memcpy 16 kB, then a few cycles in kmalloc probably won't matter much.
* Where to flush the per-cpu caches? On a 16-way system, they can contain up to 4000 objects, for each cache. Right now that happens in kmem_cache_reap(). One flush per second would be enough, just to avoid that on lightly loaded slabs, objects remain forever in the per-cpu arrays and prevent pages from becoming freeable.
* where is the freeable pages limit decreased?
--
Manfred
Quoted 9 lines · Manfred Spraul
Quoted 6 lines · Ed Tomlinson
There is no dispute that in some cases it will be slower from a slab perspective. As Andrew and you have discussed there are things that can be done to speed things up. Is not the question really, "Are the vm and slab faster together when slab pages are freed asap?"
Quoted 5 lines
Some caches are quite bursty - what about the 2 kB generic cache that is used for the MTU sized socket buffers? With interrupt mitigation enabled, I'd expect that a GigE nic could allocate a few dozend 2kb objects in every interrupt, and I don't think it's the right approach to
effectively disable the cache inslab.cfor such loads.
Well that's all rather broken at present. Your gigE NIC has just trashed 60k of cache-warm memory by putting it under busmastering receive.
It would be better to use separate slabs for Rx and Tx. Rx ones are backed by the cold page allocator and Tx ones by the hot page allocator. This is an improvement, but Rx is still doing suboptimal things because it "warms up" memory and we're not taking advantage of that. That's starting to get tricky.
There are many things we can do. We need to get the core in place and start using, tuning and using it in a few places before deciding whether to go nuts using the same technique everywhere. I hope we do ;)
Quoted 8 lines
I do not have many data points, but in a netbench run on 4-way Xeon,
kmem_cache_freeis called 5 million times/minute, and additional 4 million calls to kfree - I agree that_reapright now is bad, but IMHO it's questionable if the fix should be inside the hot-path of the allocator.What about this approach:
* enable batching even on UP, with a LIFO array in front of the lists.
That has to be right.
Quoted 4 lines
* After flushing a batch back into the lists, the number of free objects in the lists is calculated. If freeable pages exist and the number exceeds a target, then the freeable pages above the target are returned to the page buddy.
Probably OK for now. But slab should _not_ hold onto an unused, cache-warm page. Because do_anonymous_page() may want one.
Quoted 16 lines
* The target of freeable pages is increased by
kmem_cache_grow- if we had to get another page from gfp, then our own cache was too small.Since the test for the number of freeable objects only happens after batching, i.e. in the worst case once for every 30
kmem_cache_freecalls, it doesn't matter if it's a bit expensive.Open problems:
* What about cache with large objects (>PAGE_SIZE, e.g. the bio
MAX_PAGESobject, or the 16 kb socket buffers used over loopback)? Right now, they are not cached in the per-cpu arrays, to reduce the memory pressure. If the list processing becomes slower, we would slow down these slab users. But OTHO if you memcpy 16 kB, then a few cycles in kmalloc probably won't matter much.
Quoted 5 lines
* Where to flush the per-cpu caches? On a 16-way system, they can contain up to 4000 objects, for each cache. Right now that happens in
kmem_cache_reap(). One flush per second would be enough, just to avoid that on lightly loaded slabs, objects remain forever in the per-cpu arrays and prevent pages from becoming freeable.
kswapd could do that, or set up a timer and use pdflush_operation,
Quoted 10 lines · Andrew Morton
Quoted 5 lines
* After flushing a batch back into the lists, the number of free objects in the lists is calculated. If freeable pages exist and the number exceeds a target, then the freeable pages above the target are returned to the page buddy.
Probably OK for now. But slab should _not_ hold onto an unused, cache-warm page. Because
do_anonymous_page()may want one.
If the per-cpu caches are enabled on UP, too, then this is a moot point: by the time a batch is freed from the per-cpu array, it will be cache cold. And btw, why do you think a page is cache-warm when the last object on a
page is freed? If the last 32-byte kmalloc is released on a page, 40xx
bytes are probably cache-cold.
Back to your first problem: You've mentioned excess hits on the cache_chain_semaphore. Which app did you use for stress testing? Could you run a stress test with the applied patch?
I've tried dbench 50, with 128 MB RAM, on uniprocessor, with 2.4:
There were 9100 calls to kmem_cache_reap, and in 90% of the calls, no freeable memory was found. Alltogether, only 1300 pages were freed from the slabs.
Are there just too many calls to kmem_cache_reap()? Perhaps we should try to optimize the "nothing freeable exists" logic?
--
Manfred
mm/slab.c +7 -0
@@ -1727,6 +1735,9 @@ }#endif +unsigned long g_calls =0 ; +unsigned long g_pages =0 ; +unsigned long g_success =0 ;/** * kmem_cache_reap - Reclaim memory from caches. * @gfp_mask: the type of memory required.
@@ -1749,6 +1760,7 @@if (down_trylock (&cache_chain_sem))return 0 ; +g_calls++; scan =REAP_SCANLEN ; best_len =0 ; best_pages =0 ;
@@ -1827,6 +1839,8 @@ perfect:/* free only 50% of the free slabs */ best_len = (best_len +1 )/2 ; +g_success++; +g_pages+=best_len;for (scan =0 ; scan < best_len; scan++) {struct list_head *p;
@@ -1907,6 +1921,7 @@* Output format version, so at least we can change it * without _too_ many complaints. */ +seq_printf (m,"%lu %lu %lu.\n" ,g_calls, g_pages, g_success);seq_puts (m,"slabinfo - version: 1.1" #if STATS " (statistics)"
Quoted 9 lines · Manfred Spraul
Quoted 7 lines · Andrew Morton
Quoted 5 lines
* After flushing a batch back into the lists, the number of free objects in the lists is calculated. If freeable pages exist and the number exceeds a target, then the freeable pages above the target are returned to the page buddy.
Quoted 5 lines
Quoted 3 lines
Probably OK for now. But slab should _not_ hold onto an unused, cache-warm page. Because
do_anonymous_page()may want one.If the per-cpu caches are enabled on UP, too, then this is a moot point:
by the time a batch is freed from the per-cpu array, it will be cache cold.
Well yes, it's all smoke, mirrors and wishful thinking. All we can do is to apply local knowledge of typical behaviour in deciding whether a page is likely to be usefully reused.
Quoted 3 lines
And btw, why do you think a page is cache-warm when the last object on a
page is freed? If the last 32-byte kmalloc is released on a page, 40xx
bytes are probably cache-cold.
L2 caches are hundreds of K, and a single P4 cacheline is 1/32nd of a page. Things are tending in that direction.
Quoted 2 lines
Back to your first problem: You've mentioned excess hits on the
cache_chain_semaphore. Which app did you use for stress testing?
I think it was dd-to-six-disks.
Quoted 1 line
Could you run a stress test with the applied patch?
Shall try to.
Quoted 8 lines
I've tried dbench 50, with 128 MB RAM, on uniprocessor, with 2.4:
There were 9100 calls to
kmem_cache_reap, and in 90% of the calls, no freeable memory was found. Alltogether, only 1300 pages were freed from the slabs.Are there just too many calls to
kmem_cache_reap()? Perhaps we should try to optimize the "nothing freeable exists" logic?
It certainly sounds like it. Some sort of counter which is accessed outside locks would be appropriate. Test that before deciding to take the lock.