Optimize backtrace code for perf PMI handler.
Subsystems (2)
While doing perf record -g I regularly exceed the time quote for the NMI:
This leads to perf shortening the period, which causes various problems.
This patchkit optimizes two sources of longer latencies in the NMI backtrace code. There's probably more work needed to fix other sources of latencies too.
-Andi
PATCH 1/2 Use faster check for modules in backtrace on 64bit
From: Andi Kleen <[email protected]>
On my workstation which has a lot of modules loaded:
$ lsmod | wc -l 80
backtrace from the NMI for perf record -g can take a quite long time.
This leads to frequent messages like:
perf interrupt took too long (7852 > 7812), lowering kernel.perf_event_max_sample_rate to 16000
One larger part of the PMI cost is each text address check during the backtrace taking upto to 3us, like this:
1) | print_context_stack_bp() {
1) | __kernel_text_address() {
1) | is_module_text_address() {
1) | __module_text_address() {
1) 1.611 us | __module_address();
1) 1.939 us | }
1) 2.296 us | }
1) 2.659 us | }
1) | __kernel_text_address() {
1) | is_module_text_address() {
1) | __module_text_address() {
1) 0.724 us | __module_address();
1) 1.064 us | }
1) 1.430 us | }
1) 1.798 us | }
1) | __kernel_text_address() {
1) | is_module_text_address() {
1) | __module_text_address() {
1) 0.656 us | __module_address();
1) 1.012 us | }
1) 1.356 us | }
1) 1.761 us | }So just with a reasonably sized backtrace easily 10-20us can be spent on just checking the frame pointer IPs.
The main cost is simply walking this long list of modules and checking it.
On 64bit kernels we can do a short cut. All modules are in a special reserved virtual address space area. So only check for that range, which is much cheaper.
This has the (small) potential to get a false positive on a pointer to a data segment in a module. However since we also use the frame pointer chain as initial sanity check I think the danger of this is very low.
--- arch/x86/kernel/dumpstack.c | 12 ++++++++++++ 1 file changed, 12 insertions(+)
arch/x86/kernel/dumpstack.c +12 -0
@@ -130,8 +130,20 @@ print_context_stack_bp(struct thread_info *tinfo,while (valid_stack_ptr (tinfo, ret_addr,sizeof (*ret_addr), end)) {unsigned long addr = *ret_addr; +#ifdef CONFIG_64BIT +/* +* On 64 bit the modules are in a special reserved +* area, so we can just check the range. +* It is not as exact as a full lookup, but together +* with the frame pointer it is good enough. +*/ +if (!core_kernel_text (addr) && + !(addr >=MODULES_VADDR && addr <MODULES_END )) +break ; +#else if (!__kernel_text_address (addr))break ; +#endif ops->address (data, addr,1 ); frame = frame->next_frame;
Signature · 1 line
1.9.3
Peter Zijlstra
maintainerRe: [PATCH 1/2] Use faster check for modules in backtrace on 64bit
Quoted 5 lines · Andi Kleen
This has the (small) potential to get a false positive on a pointer to a data segment in a module. However since we also use the frame pointer chain as initial sanity check I think the danger of this is very low.
So this has come up several times; and the answer has always been, why not make the __module_address() thing a rb-tree instead of a linear loop. So I suppose I'll ask that again, why not?
Re: [PATCH 1/2] Use faster check for modules in backtrace on 64bit
Quoted 10 lines · Peter Zijlstra
Quoted 5 lines · Andi Kleen
This has the (small) potential to get a false positive on a pointer to a data segment in a module. However since we also use the frame pointer chain as initial sanity check I think the danger of this is very low.
So this has come up several times; and the answer has always been, why not make the
__module_address()thing a rb-tree instead of a linear loop. So I suppose I'll ask that again, why not?
Why do things complicated, if they can be done simple too?
-Andi
Signature · 1 line
[email protected] -- Speaking for myself only
Re: [PATCH 1/2] Use faster check for modules in backtrace on 64bit
Quoted 8 lines · Andi Kleen
Quoted 7 lines · Peter Zijlstra
Quoted 5 lines · Andi Kleen
This has the (small) potential to get a false positive on a pointer to a data segment in a module. However since we also use the frame pointer chain as initial sanity check I think the danger of this is very low.
Quoted 5 lines
Quoted 3 lines
So this has come up several times; and the answer has always been, why not make the
__module_address()thing a rb-tree instead of a linear loop. So I suppose I'll ask that again, why not?Why do things complicated, if they can be done simple too?
Also I investigated it now, but we don't have RCU support for rbtrees. So it would need some kind of locking for the reader, which is a show stopper.
-Andi
Peter Zijlstra
maintainerRe: [PATCH 1/2] Use faster check for modules in backtrace on 64bit
Quoted 13 lines · Andi Kleen
Quoted 12 lines · Andi Kleen
Quoted 10 lines · Peter Zijlstra
Quoted 5 lines · Andi Kleen
This has the (small) potential to get a false positive on a pointer to a data segment in a module. However since we also use the frame pointer chain as initial sanity check I think the danger of this is very low.
So this has come up several times; and the answer has always been, why not make the
__module_address()thing a rb-tree instead of a linear loop. So I suppose I'll ask that again, why not?
Quoted 5 lines
Quoted 1 line
Why do things complicated, if they can be done simple too?
Also I investigated it now, but we don't have RCU support for rbtrees. So it would need some kind of locking for the reader, which is a show stopper.
Nah, we can trivially do that with a seqlock. Not read side locking required in the normal case.
Re: [PATCH 1/2] Use faster check for modules in backtrace on 64bit
Quoted 6 lines
Quoted 3 lines
Also I investigated it now, but we don't have RCU support for rbtrees. So it would need some kind of locking for the reader, which is a show stopper.
Nah, we can trivially do that with a seqlock. Not read side locking required in the normal case.
I'm not convinced. It wouldn't surprise me if it was possible to generate endless cycles with rcu freed memory on some rebalancing operation. If you think I'm wrong please show working code.
Also please explain clearly for the module maintainers and me what the problem with my original simple trivially show to be correct solution is.
Thanks,
-Andi
Signature · 1 line
[email protected] -- Speaking for myself only.
Peter Zijlstra
maintainerRe: [PATCH 1/2] Use faster check for modules in backtrace on 64bit
Quoted 10 lines · Andi Kleen
Quoted 6 lines
Quoted 3 lines
Also I investigated it now, but we don't have RCU support for rbtrees. So it would need some kind of locking for the reader, which is a show stopper.
Nah, we can trivially do that with a seqlock. Not read side locking required in the normal case.
I'm not convinced. It wouldn't surprise me if it was possible to generate endless cycles with rcu freed memory on some rebalancing operation.
I don't think so, every (tree) rotation still maintains the tree as a tree, therefore downward iteration will always get you to the end.
You might temporarily run in circles until you observe the new pointers, but that is not a problem, and strictly limited to however long it takes for the new pointers to become visible on the iterating CPU.
Deletion should not be a problem either, if the deleted node retains pointers, they'll point back into the tree, and by the previous argument, downward iteration terminates.
Quoted 1 line
If you think I'm wrong please show working code.
That is unrelated to the above, you're just not willing to work on it. Which is fine, then this problem will remain for a little while longer.
Quoted 3 lines
Also please explain clearly for the module maintainers and me what the problem with my original simple trivially show to be correct solution is.
It is not correct, you yourself said there were false positives with it. But the biggest issue is that its x86_64 only.
Re: [PATCH 1/2] Use faster check for modules in backtrace on 64bit
Quoted 3 lines
Quoted 1 line
If you think I'm wrong please show working code.
That is unrelated to the above, you're just not willing to work on it.
I'm willing to work on practical suggestions, which this one is not.
Speculative data structure research is not on my general agenda, and should not be required for Linx contributions.
Quoted 1 line
But the biggest issue is that its
x86_64only.
Fair enough. I'll look into something that works there too.
-Andi
Signature · 1 line
[email protected] -- Speaking for myself only.
PATCH 2/2 x86: Only do a single page fault for copy_from_user_nmi
In reply to Andi KleenFrom: Andi Kleen <[email protected]>
When copy_from_user_nmi faults the copy_user_tail code ends up "replaying" the page faults to compute the exact tail bytes, (added with 112958).
So we do an expensive page fault. And then we do it *again*.
This ends up being very expensive in the PMI handler for any page fault on a stack access, and is one the more common causes for the NMI handler exceeding its runtime limit.
1) 0.109 us | copy_from_user_nmi();
1) | copy_from_user_nmi() {
1) | __do_page_fault() {
1) | bad_area_nosemaphore() {
1) | __bad_area_nosemaphore() {
1) | no_context() {
1) | fixup_exception() {
1) | search_exception_tables() {
1) 0.079 us | search_extable();
1) 0.409 us | }
1) 0.757 us | }
1) 1.106 us | }
1) 1.466 us | }
1) 1.793 us | }
1) 2.233 us | }
1) | copy_user_handle_tail() {
1) | __do_page_fault() {
1) | bad_area_nosemaphore() {
1) | __bad_area_nosemaphore() {
1) | no_context() {
1) | fixup_exception() {
1) | search_exception_tables() {
1) 0.060 us | search_extable();
1) 0.412 us | }
1) 0.764 us | }
1) 1.074 us | }
1) 1.389 us | }
1) 1.665 us | }
1) 2.002 us | }
1) 2.784 us | }
1) 6.230 us | }The NMI code actually doesn't care about the exact tail value. It only needs to know if a fault happened (!= 0)
So check for in_nmi() in copy_user_tail and don't bother with the exact tail check. This way we save the extra ~2.7us.
In theory we could also duplicate the whole copy_*_ path for cases where the caller doesn't care about the exact bytes. But that seems overkill for just this issue, and I'm not sure anyone else cares about how fast this is. The simpler check works as well for now.
--- arch/x86/lib/usercopy_64.c | 9 +++++++++ 1 file changed, 9 insertions(+)
arch/x86/lib/usercopy_64.c +9 -0
@@ -67,6 +67,9 @@ EXPORT_SYMBOL(copy_in_user);* Try to copy last bytes and clear the rest if needed. * Since protection fault in copy_from/to_user is not a normal situation, * it is not necessary to optimize tail handling. +* +* It can be somewhat common in NMI handlers doing backtraces. +* So don't bother here with returning the exact tail. */ __visible unsigned long copy_user_handle_tail (char *to,char *from,unsigned len,unsigned zerorest)
@@ -74,6 +77,11 @@ copy_user_handle_tail(char *to, char *from, unsigned len, unsigned zerorest)char c;unsigned zero_len; +if (in_nmi ()) { + len =1 ;/* users only care about != 0 */ + goto out; + } +for (; len; --len, to++) {if (__get_user_nocheck (c, from++,sizeof (char )))break ;
@@ -84,6 +92,7 @@ copy_user_handle_tail(char *to, char *from, unsigned len, unsigned zerorest)for (c =0 , zero_len = len; zerorest && zero_len; --zero_len)if (__put_user_nocheck (c, to++,sizeof (char )))break ; +out:clac ();return len; }
Signature · 1 line
1.9.3
Peter Zijlstra
maintainerRe: [PATCH 2/2] x86: Only do a single page fault for copy_from_user_nmi
Quoted 5 lines · Andi Kleen
From: Andi Kleen <[email protected]>
When
copy_from_user_nmifaults thecopy_user_tailcode ends up "replaying" the page faults to compute the exact tail bytes, (added with 112958).
That is a wrong way to quote commits in two ways;
1) Linus 'requires' you use 12 character abreviated hashes (because we've already seen collisions with the default 8), yet you use 6.
2) the recommended quoting style is:
1129585a08ba ("x86: introduce copy_user_handle_tail() routine")You _should_ know this.
Quoted 38 lines
So we do an expensive page fault. And then we do it *again*.
This ends up being very expensive in the PMI handler for any page fault on a stack access, and is one the more common causes for the NMI handler exceeding its runtime limit.
1) 0.109 us | copy_from_user_nmi(); 1) | copy_from_user_nmi() { 1) | __do_page_fault() { 1) | bad_area_nosemaphore() { 1) | __bad_area_nosemaphore() { 1) | no_context() { 1) | fixup_exception() { 1) | search_exception_tables() { 1) 0.079 us | search_extable(); 1) 0.409 us | } 1) 0.757 us | } 1) 1.106 us | } 1) 1.466 us | } 1) 1.793 us | } 1) 2.233 us | } 1) | copy_user_handle_tail() { 1) | __do_page_fault() { 1) | bad_area_nosemaphore() { 1) | __bad_area_nosemaphore() { 1) | no_context() { 1) | fixup_exception() { 1) | search_exception_tables() { 1) 0.060 us | search_extable(); 1) 0.412 us | } 1) 0.764 us | } 1) 1.074 us | } 1) 1.389 us | } 1) 1.665 us | } 1) 2.002 us | } 1) 2.784 us | } 1) 6.230 us | }
Quoted 2 lines
The NMI code actually doesn't care about the exact tail value. It only needs to know if a fault happened (!= 0)
For now, changing the semantics of the function seems like a sure way to fail in the future though.
Quoted 8 lines
So check for
in_nmi()incopy_user_tailand don't bother with the exact tail check. This way we save the extra ~2.7us.In theory we could also duplicate the whole copy_*_ path for cases where the caller doesn't care about the exact bytes. But that seems overkill for just this issue, and I'm not sure anyone else cares about how fast this is. The simpler check works as well for now.
So I don't get that code, but why not fix it in general? Taking two faults seems silly.
Re: [PATCH 2/2] x86: Only do a single page fault for copy_from_user_nmi
Quoted 2 lines
For now, changing the semantics of the function seems like a sure way to fail in the future though.
I doubt it. Nearly nobody uses the exact return value semantics.
(iirc it's mostly write() and some bizarre code in mount)
In fact it's a regular mistake to assume it returns -errno.
Quoted 8 lines
Quoted 5 lines
In theory we could also duplicate the whole copy_*_ path for cases where the caller doesn't care about the exact bytes. But that seems overkill for just this issue, and I'm not sure anyone else cares about how fast this is. The simpler check works as well for now.
So I don't get that code, but why not fix it in general? Taking two faults seems silly.
It's really complicated to reconstruct the exact bytes, as an optimized memcpy is very complicated and has a lot of corner cases.
I tried it originally when writing the original copy function, but failed. That is why people came up later with this two-fault scheme.
I think two fault is fine for most cases, just not for NMIs.
-Andi
Signature · 1 line
[email protected] -- Speaking for myself only
Re: [PATCH 2/2] x86: Only do a single page fault for copy_from_user_nmi
Quoted 23 lines · Andi Kleen
Quoted 2 lines
For now, changing the semantics of the function seems like a sure way to fail in the future though.
I doubt it. Nearly nobody uses the exact return value semantics.
(iirc it's mostly
write()and some bizarre code in mount)In fact it's a regular mistake to assume it returns -errno.
Quoted 8 lines
Quoted 5 lines
In theory we could also duplicate the whole copy_*_ path for cases where the caller doesn't care about the exact bytes. But that seems overkill for just this issue, and I'm not sure anyone else cares about how fast this is. The simpler check works as well for now.
So I don't get that code, but why not fix it in general? Taking two faults seems silly.
It's really complicated to reconstruct the exact bytes, as an optimized memcpy is very complicated and has a lot of corner cases.
Quoted 5 lines
I tried it originally when writing the original copy function, but failed. That is why people came up later with this two-fault scheme.
I think two fault is fine for most cases, just not for NMIs.
Slapping an ugly in_nmi() check into a generic memcpy routine, especially if it changes semantics, is asking for trouble. It is a non-starter and I'm NAK-ing it.
There are cleaner ways to solve this problem - PeterZ offered one, but there are other options as well, such as:
- removing exact-bytes semantics explicitly from almost all cases and offering a separate (and more expensive, in the faulting case) memcpy variant for write() and other code that absolutely must know the number of copied bytes.
- or adding a special no-bytes-copied memcpy variant that the NMI code could use.
Use one of these or outline that they cannot possibly work.
It might be more work for you, but it gives us a cleaner and more maintainable kernel. The problem is that you should know this general principle already, instead you are wasting maintainer bandwidth via arguing in favor of ugly hacks again and again...
Thanks,
Ingo
Re: [PATCH 2/2] x86: Only do a single page fault for copy_from_user_nmi
Quoted 7 lines
There are cleaner ways to solve this problem - PeterZ offered one, but there are other options as well, such as:
- removing exact-bytes semantics explicitly from almost all cases and offering a separate (and more expensive, in the faulting case) memcpy variant for
write()and other code that absolutely must know the number of copied bytes.
That would be a full tree audit of thousands of calls. And any mistake would be a security hole.
Quoted 2 lines
- or adding a special no-bytes-copied memcpy variant that the NMI code could use.
That's the duplicated copy path I mentioned. If people really want that I can implement it, although I personally think it's ugly and bloated over engineering for this case.
Quoted 4 lines
It might be more work for you, but it gives us a cleaner and more maintainable kernel. The problem is that you should know this general principle already, instead you are wasting maintainer bandwidth via arguing in favor of ugly hacks again and again...
The duplicated path is unlikely to be more maintainable than the simple and obvious check.
-Andi