Optimize backtrace code for perf PMI handler.

Optimize backtrace code for perf PMI handler.

[Andi Kleen]

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

[Andi Kleen]

From: Andi Kleen <ak@linux.intel.com>

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.

Signed-off-by: Andi Kleen <ak@linux.intel.com>
---
 arch/x86/kernel/dumpstack.c | 12 ++++++++++++
 1 file changed, 12 insertions(+)

diff --git a/arch/x86/kernel/dumpstack.c b/arch/x86/kernel/dumpstack.c
index b74ebc7..b7cbae3 100644
--- a/arch/x86/kernel/dumpstack.c
+++ b/arch/x86/kernel/dumpstack.c
@@ -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;
-- 
1.9.3

Re: [PATCH 1/2] Use faster check for modules in backtrace on 64bit

[Peter Zijlstra]

On Fri, Sep 26, 2014 at 04:31:16PM -0700, Andi Kleen wrote:
> 
> 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

[Andi Kleen]

On Mon, Sep 29, 2014 at 01:42:12PM +0200, Peter Zijlstra wrote:
> On Fri, Sep 26, 2014 at 04:31:16PM -0700, Andi Kleen wrote:
> > 
> > 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

-- 
ak@linux.intel.com -- Speaking for myself only

Re: [PATCH 1/2] Use faster check for modules in backtrace on 64bit

[Andi Kleen]

On Mon, Sep 29, 2014 at 08:21:45AM -0700, Andi Kleen wrote:
> On Mon, Sep 29, 2014 at 01:42:12PM +0200, Peter Zijlstra wrote:
> > On Fri, Sep 26, 2014 at 04:31:16PM -0700, Andi Kleen wrote:
> > > 
> > > 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?

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

Re: [PATCH 1/2] Use faster check for modules in backtrace on 64bit

[Peter Zijlstra]

On Mon, Sep 29, 2014 at 10:30:23PM +0200, Andi Kleen wrote:
> On Mon, Sep 29, 2014 at 08:21:45AM -0700, Andi Kleen wrote:
> > On Mon, Sep 29, 2014 at 01:42:12PM +0200, Peter Zijlstra wrote:
> > > On Fri, Sep 26, 2014 at 04:31:16PM -0700, Andi Kleen wrote:
> > > > 
> > > > 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?
> 
> 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

[Andi Kleen]

> > 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
-- 
ak@linux.intel.com -- Speaking for myself only.

Re: [PATCH 1/2] Use faster check for modules in backtrace on 64bit

[Peter Zijlstra]

On Tue, Sep 30, 2014 at 10:10:00PM +0200, Andi Kleen wrote:
> > > 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.

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

> 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

[Andi Kleen]

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

> But the biggest issue is that its x86_64 only.

Fair enough. I'll look into something that works there too.

-Andi

-- 
ak@linux.intel.com -- Speaking for myself only.

[PATCH 2/2] x86: Only do a single page fault for copy_from_user_nmi

[Andi Kleen]

From: Andi Kleen <ak@linux.intel.com>

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.

Cc: torvalds@linux-foundation.org
Cc: Vitaly Mayatskikh <v.mayatskih@gmail.com>
Signed-off-by: Andi Kleen <ak@linux.intel.com>
---
 arch/x86/lib/usercopy_64.c | 9 +++++++++
 1 file changed, 9 insertions(+)

diff --git a/arch/x86/lib/usercopy_64.c b/arch/x86/lib/usercopy_64.c
index c905e89..1b581e7 100644
--- a/arch/x86/lib/usercopy_64.c
+++ b/arch/x86/lib/usercopy_64.c
@@ -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;
 }
-- 
1.9.3

Re: [PATCH 2/2] x86: Only do a single page fault for copy_from_user_nmi

[Peter Zijlstra]

On Fri, Sep 26, 2014 at 04:31:17PM -0700, Andi Kleen wrote:
> From: Andi Kleen <ak@linux.intel.com>
> 
> 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).

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.

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

For now, changing the semantics of the function seems like a sure way to
fail in the future though.

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

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

[Andi Kleen]

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

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

-- 
ak@linux.intel.com -- Speaking for myself only

Re: [PATCH 2/2] x86: Only do a single page fault for copy_from_user_nmi

[Ingo Molnar]

* Andi Kleen <ak@linux.intel.com> wrote:

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

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

[Andi Kleen]

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

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

> 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