Scalability problem (kmap_lock) with -aa kernels

OK, I finally got the -aa kernel series running in conjunction with the NUMA-Q discontigmem stuff. For some reason which I haven't debugged yet 2.4.19-pre3-aa2 won't boot on the NUMA-Q even without the discontigmem stuff in ... so I went back to 2.4.19-pre1-aa1, which I knew worked from last time around (thanks again for that patch).

So just comparing aa+discontigmem to standard 2.4.18+discontigmem, I see kernel compile times are about 35s vs 26.5s .... hmmm. Looking at the top part of the profiles, I see this:

standard:

23991 total 0.0257
7679 default_idle 147.6731
3044 _text_lock_dcache 8.7221
2340 _text_lock_swap 43.3333

  1160 do_anonymous_page                          3.4940
   776 d_lookup                                   2.8116
   650 __free_pages_ok                            1.2405
   627 lru_cache_add                              6.8152
   608 do_generic_file_read                       0.5468
   498 __generic_copy_from_user                   4.7885

480 lru_cache_del 21.8182
437 atomic_dec_and_lock 6.0694
426 schedule 0.3017
402 _text_lock_dec_and_lock 16.7500
...
109 kmap_high 0.3028
46 _text_lock_highmem 0.4071

andrea:
38549 total 0.0405
13102 _text_lock_highmem 108.2810
8627 default_idle 165.9038
2578 kunmap_high 14.3222
2556 kmap_high 6.0857
1242 do_anonymous_page 3.2684
1052 _text_lock_swap 22.8696

   942 _text_lock_dcache                          2.4987
   683 do_page_fault                              0.4337
   587 pte_alloc                                  1.2332
   535 __generic_copy_from_user                   5.1442
   518 d_lookup                                   1.8768
   443 __free_pages_ok                            0.7745
   422 lru_cache_add                              2.7763

_text_lock_highmem appears to be kmap_lock, looking at dissassembly. Recompiling with the trusty lockmeter, I see this (on -aa).

 33.4% 63.5%  5.4us(7893us)  155us(  16ms)(37.8%)   2551814 36.5% 63.5%    0%  kmap_lock_cacheline
 17.4% 64.9%  5.7us(7893us)  158us(  16ms)(19.7%)   1275907 35.1% 64.9%    0%    kmap_high+0x34
 16.0% 62.1%  5.2us( 982us)  152us(  13ms)(18.1%)   1275907 37.9% 62.1%    0%    kunmap_high+0x40

Ick. On a vaguely comparible mainline kernel we're looking at:

  1.6%  2.7%  0.5us(4208us)   28us(3885us)(0.14%)    716044 97.3%  2.7%    0%  kmap_lock
  1.2%  2.9%  0.9us(4208us)   35us(3885us)(0.09%)    358022 97.1%  2.9%    0%    kmap_high+0x10
 0.33%  2.5%  0.2us(  71us)   21us(2598us)(0.05%)    358022 97.5%  2.5%    0%    kunmap_high+0xc

Andrea - is this your new highmem pte stuff doing this? Or is that not even in your tree as yet? Would be a shame if that's the problem as I really want to get the highmem pte stuff - allows me to put processes pagetables on their own nodes ....

Thanks,

Martin.

That's probably Andrea's pte-highmem code, which uses the global kmap pool instead of doing cpu-local atomic kmaps.

He's been told about this becoming a scalability problem but didn't believe it since I didn't have any numbers for him. Maybe he believes it now since you've measured it ;)

You really want the pte-highmem by Arjan and Ingo, which uses kmap_atomic (which is CPU-local and doesn't suffer the same scalability problem as the global kmap pool).

regards,

Rik

<insert bitkeeper endorsement here>

http://www.surriel.com/		http://distro.conectiva.com/

If you have PIII cpus pre3 mainline has a bug in the machine check code, this one liner will fix it:

diff -urN 2.4.19pre3/arch/i386/kernel/bluesmoke.c mcheck/arch/i386/kernel/bluesmoke.c
@@ -169,7 +169,7 @@
 	if(l&(1<<8))
 		wrmsr(MSR_IA32_MCG_CTL, 0xffffffff, 0xffffffff);
 	banks = l&0xff;
-	for(i=0;i<banks;i++)
+	for(i=1;i<banks;i++)
 	{
 		wrmsr(MSR_IA32_MC0_CTL+4*i, 0xffffffff, 0xffffffff);
 	}

One thing I see is not only a scalability problem with the locking, but it seems kmap_high is also spending an huge amount of time in kernel compared to the "standard" profiling. That maybe because I increased too much the size of the pool (the algorithm is O(N)). Can you try again with this incremental patch applied?

@@ -47,7 +47,7 @@
 	KM_NR_SERIES,
 };
 
-#define LAST_PKMAP 1024
+#define LAST_PKMAP 128
 #define PKMAP_SIZE ((LAST_PKMAP*KM_NR_SERIES) << PAGE_SHIFT)
 #define PKMAP_BASE (FIXADDR_START - PKMAP_SIZE - PAGE_SIZE) /* left a page in between */
 #define PKMAP_NR(virt)  (((virt)-PKMAP_BASE) >> PAGE_SHIFT)

If kmap_high was dogslow, all cpus had to stall for a very long time into _text_lock_highmem (OTOH also kunmap_high has a quite high rate, infact it has an higher rate, that doesn't make much sense).

The pte-highmem stuff has nothing to do with the kmap_high O(N) complexity that maybe the real reason of this slowdown. (the above patch decreases N of an order of magnitude and so we'll see if that was the real problem or not)

However avoiding completly persistent kmaps would definitely give you an additional scalability at the cost of an additional tlb overhead and uglier code. I never questioned this point. If you want to run a 1024 CPU system then you don't want the persistent kmaps, period.

So avoiding persistent kmaps in the pte handling would in turn you give you additional scalability __if__ your workload is very pagetable intensive (a kernel compile is very pagetable intensive incidentally), but the very same scalability problem you can find with the pagetables you will have it also for the cache in different workloads because all the pagecache is in highmem too and every time you execute a read syscall you will also need to kmap-persistent a pagecache.

So I will never agree that avoiding the persistent kmaps in the pagetable handling is a final solution, if the persistent kmaps are a bottleneck they have to be removed completly, not just from the pagetable handling. 512 pages = 2M of cache being cached isn't enough if it doesn't work well for the pagetables (infact such pool of mapped pages sounds much nicer for the pagetables, where the ram footprint is much smaller than for the pagecache, and also thanks to the quicklist that will make more likely to have page->virtual just in cache, btw removing the quicklist from 2.5 was a bad idea, the global allocator affinity can be completly polluted under high I/O loads, and the quicklist was still useful as an active list, but this is totally offtopic here, it just happened to be broken in 2.5 with the high-pte patch and that's why it came to mind).

Avoiding persistent kmaps for the whole pagetable handling doesn't guarantee your scalability problem will go away, you will run in the _very_same_scalability_problem_ with a just little different workload, it depends completly on the workload, and lots of common applications are going to be hurted by the pagecache I/O the same or more than the pagetable kmaps.

The 2.5 kernel avoids using persistent kmaps for pagetables, that's the only interesting difference with pte-highmem in 2.4 (all other differences are not interesting and I prefer pte-highmem for all other parts for sure), but note that you will still have to pay for an hit if you want the feature compared to the "standard" 2.4 that you benchmarked
against: in 2.5 the CPU will have to walk pagetables for the kmap areas after every new kmap because the kmap will be forced to flush the tlb entry without persistence. The pagetables relative to the kmap atomic area are shared across all cpus and the cpu issues locked cycles to walk them.

The whole persistent kmap design is superior in common machines where people doesn't need to scale up to 16-way and it allows us to write simpler code compared to the atomic kmaps. It wasn't really designed for 16-way machines. It's not a matter of pte-highmem vs high-pte, it's a matter of persistent kmaps vs atomic kmaps, not just for the pagetables but for everything. If you need to avoid the global spinlock you don't want the persistent kmaps, no matter where they came from (pagetable/pagecache).

As soon as I'll get your result for the above patch, we'll be able to choose if the right thing is to remove all persistent kmaps from pte-highmem (removing them from the pagecache would be too complicated in 2.4 because it would break the fs API, while just for pte-highmem is doable in a few hours). It will be a choice oriented for the very high end 32bit x86 though, my 2-way x86 doesn't showup any locking problem in the profiles yet.

Many thanks for the useful feedback.

Andrea

Thanks - that'll probably save me a bunch of time ...

May I assume, for the sake of discussion, that there's not much difference between pre1-aa1 and your latest stuff in the area we're talking about here?

One other wierd thing to note in the profiling is that kunmap_high is way up in the profile as well - seeing as kunmap_high doesn't do the same sort of scanning as kmap_high, it shouldn't be O(N). I'm wondering if somehow the profiling attributes some of the spinning cost to the calling function. Pure speculation, but there's defintely something strange there ....

Sure ... will retest. But by shrinking the size of the pool back down, won't you just increase the number of global tlbflushes? Any way you cut it, the kmaps are going to be expensive ... according to the lockmeter stuff, you're doing about 3.5 times as many kmaps.

I appreciate the scanning doesn't scale well, but is the pte-highmem stuff the cause of the increase of kmap frequency? There seems to be both a frequency and duration problem.

I don't think anyone would deny that making kmap faster / more scalable would be a Good Thing ;-) I haven't stared at the pagecache code too much - once we avoid the bounce buffers with Jens' patches, do we still need to do a kmap for the pagecache situation you mention?

OK, I guess we're back to the question of whether a local tlb_flush_one per kmap is cheaper than a global tlb_flush_all once per LAST_PKMAP kmaps. Not just in terms of time to execute, but in terms of how much we slow down others by trashing the cache ... I guess that's going to be tough to really measure.

It would be nice to be able to compare the two different kmap approaches against each other - AFAIK, the 2.5 implementation isn't available for 2.4 to compare though ... if your stuff is easy to change over to atomic_kmap, I'd be happy to compare it (unless shrinking the pool size fixes it, in which case we're done).

Thanks for taking the time to explain all of this - I have a much better idea what's going on now. I'll get you the new numbers tommorow.

M.

Yep. What's the profile buffer size? Just make sure to boot with profile=2 so you'll have a quite accurate precision.

Yes.

the frequency is higher during a kernel compile due the pte-highmem, but if you just change the workload and you start 16 tasks simultaenous reading from a file in cache, you will get the same very frequency no matter of pte-highmem or not. What you found is a scalability issue with the persistent kmaps, not introduced by pte-highmem (however with pte-highmem I have increased its visibility due the additional usages of the persistent kmaps for certain pte intensive workload and with a larger pool to scan).

of course yes. bounce buffers are completly transparent with the pagecache layer. The very same persistent kmap that is hurting you with the pagetable handling is happening also in every generic_file_read/write, it will happen even if you are using ramfs that doesn't do any I/O at all.

On a 16-way considering all cpus will hit the mem bus to re-read all the pagetables at the very same time plus there will be an IPI flood to 16 cpus, so depending on the design of your hardware it may be bad. More cpus also means a potential much higher kmap frequency. So I'm pretty sure for NUMA-Q you don't want the persistent kmaps in pagetables and in pagecache. Persistent kmaps aren't meant to scale, they're meant to optimize the more common x86 machines (also UP with say 1G of ram) and to make the kernel code dealing with highmem simpler and more readable. Those are the very same reasons I'm using the persistent kmaps in pte-highmem indeed. But on a 16-way you have different scalability needs for both pagecache and pagetables.

BTW, I would also clarify that it's not that I never checked any number/profiling of high end systems yet with pte-highmem, it's just that your hardware and your workload has to be quite different from the one where pte-highmem is been developed for. The workloads that were running out of pagetables due the too many tasks mapping the same 512M SGA, didn't show any bottleneck in the persistent kmap during the profiling.

Correct. If shrinking the pool doesn't make significant difference (for example it may be acceptable if it would reduce the level of overhead to the same one of lru_cache_add in the anonymous memory page fault that you also don't want on a NUMA-Q just for kernel compiles without the need of swapout anything) I can very easily drop the persistent kmap usage from my tree so you can try that way too (without adding the kernel pagetables in kernel stuff in 2.5 and without dropping the quicklist cpu affine cache like what happened in 2.5).

BTW, before I drop the persistent kmaps from the pagetable handling you can also make a quick check by removing __GFP_HIGHMEM from the allocation in mm/memory.c:pte_alloc_one() and verifying the kmap_high overhead goes away during the kernel compiles (that basically disables the pte-highmem feature).

You're welcome. Thanks to you to help fixing very-high-end scalability problems in my tree.

Andrea