Keep shadow stacks to help heap checker unwind without frame pointers

This CL introduces the stack shadowing mechanism that should help TCMalloc's
heap leak checker to unwind the memory allocation stacks better.

Currently, if a memory region is allocated from a library built without frame
pointers heapchecker is unable to unwind the stack and records only the top
frame. This is inconvenient, because:
 -- several leaks from different places are treated as leaks from the same
    source
 -- it's hard to suppress such leaks, because a one-line suppression is
    uninformative

linux_shadow_stacks.cc keeps the threads' IP and SP values in thread-local
stacks upon each function entry/exit using gcc function instrumentation
(-finstrument-functions).
The GetStackTrace routine from stacktrace_shadow-inl.h unwinds the stack as
usual (using frame pointers), but then updates the result with the shadow stack
frames which SP values are below the bottom frame of the unwind result.

Note that -finstrument-functions affects only Chromium code, not the libraries.
This means that we cannot get more than one library function frame at the top
of the stack.
For example, consider a libfoo library that has a public foo_do_something()
routine which allocates memory via foo_alloc(). If Chromium calls
foo_do_something() from ChromeCallFoo(), then the following call chain
effectively happens:
  main -> ChromeCallFoo -> foo_do_something -> foo_alloc

If libfoo is built with -fomit-frame-pointers, heapcheck can unwind only the
last stack frame:
  foo_alloc

On the other hand, the shadow stack at the allocation site contains everything
below the libfoo calls:
  main -> ChromeCallFoo

As a result the following allocation stack is recorded:
  main -> ChromeCallFoo -> foo_alloc

This is enough to distinguish between e.g. ChromeCallFoo1 and ChromeCallFoo2


Committed: http://src.chromium.org/viewvc/chrome?view=rev&revision=57658

[Alexander Potapenko, 2010-08-19 14:33:29]

Folks,
could you please take a look?

This code is to be used for heapcheck runs only, so I want to make sure that the
gyp changes are correct enough to instrument the whole Chromium codebase using
-finstrument-functions iff keep_shadow_stacks==1 and do nothing otherwise.

[Alexander Potapenko, 2010-08-19 14:35:18]

Please refer to http://code.google.com/p/chromium/issues/detail?id=51988 for the
problem discussion and the stacktrace samples.

[willchan no longer on Chromium, 2010-08-19 14:35:37]

Why aren't we just using libunwind for this?

On Thu, Aug 19, 2010 at 7:33 AM, <glider@chromium.org> wrote:

> Reviewers: Mike Belshe, willchan,
>
> Message:
> Folks,
> could you please take a look?
>
> This code is to be used for heapcheck runs only, so I want to make sure
> that the
> gyp changes are correct enough to instrument the whole Chromium codebase
> using
> -finstrument-functions iff keep_shadow_stacks==1 and do nothing otherwise.
>
> Description:
> This CL introduces the stack shadowing mechanism that should help
> TCMalloc's
> heap leak checker to unwind the memory allocation stacks better.
>
> Currently, if a memory region is allocated from a library built without
> frame
> pointers heapchecker is unable to unwind the stack and records only the top
> frame. This is inconvenient, because:
>  -- several leaks from different places are treated as leaks from the same
>    source
>  -- it's hard to suppress such leaks, because a one-line suppression is
>    uninformative
>
> linux_shadow_stacks.cc keeps the threads' IP and SP values in thread-local
> stacks upon each function entry/exit using gcc function instrumentation
> (-finstrument-functions).
> The GetStackTrace routine from stacktrace_shadow-inl.h unwinds the stack as
> usual (using frame pointers), but then updates the result with the shadow
> stack
> frames which SP values are below the bottom frame of the unwind result.
>
> Note that -finstrument-functions affects only Chromium code, not the
> libraries.
> This means that we cannot get more than one library function frame at the
> top
> of the stack.
> For example, consider a libfoo library that has a public foo_do_something()
> routine which allocates memory via foo_alloc(). If Chromium calls
> foo_do_something() from ChromeCallFoo(), then the following call chain
> effectively happens:
>  main -> ChromeCallFoo -> foo_do_something -> foo_alloc
>
> If libfoo is built with -fomit-frame-pointers, heapcheck can unwind only
> the
> last stack frame:
>  foo_alloc
>
> On the other hand, the shadow stack at the allocation site contains
> everything
> below the libfoo calls:
>  main -> ChromeCallFoo
>
> As a result the following allocation stack is recorded:
>  main -> ChromeCallFoo -> foo_alloc
>
> This is enough to distinguish between e.g. ChromeCallFoo1 and
> ChromeCallFoo2
>
>
> Please review this at http://codereview.chromium.org/3120017/show
>
> SVN Base: svn://svn.chromium.org/chrome/trunk/src/
>
> Affected files:
>  M     base/allocator/allocator.gyp
>  M     build/common.gypi
>  A     third_party/tcmalloc/chromium/src/linux_shadow_stacks.cc
>  M     third_party/tcmalloc/chromium/src/stacktrace_config.h
>  A     third_party/tcmalloc/chromium/src/stacktrace_shadow-inl.h
>
>
>

[Alexander Potapenko, 2010-08-19 14:48:27]

Unfortunately libunwind cannot be used together with perftools.
As far as I know, it relies on dl_iterate_phdr to read the DWARF info (if the
frame pointers are missing, DWARF is the only option), which is not async signal
safe and calls malloc -- this can just deadlock everything. We need to patch
glibc in order to fix that.

On 2010/08/19 14:35:37, willchan wrote:
> Why aren't we just using libunwind for this?

[willchan no longer on Chromium, 2010-08-19 14:57:29]

Ah yes, that's right.  I forgot that, thanks for reminding me!

Is this a change we can contribute directly to google-perftools?  Is your
plan to implement in chromium first and then upstream?

On Thu, Aug 19, 2010 at 7:48 AM, <glider@chromium.org> wrote:

> Unfortunately libunwind cannot be used together with perftools.
> As far as I know, it relies on dl_iterate_phdr to read the DWARF info (if
> the
> frame pointers are missing, DWARF is the only option), which is not async
> signal
> safe and calls malloc -- this can just deadlock everything. We need to
> patch
> glibc in order to fix that.
>
>
> On 2010/08/19 14:35:37, willchan wrote:
>
>> Why aren't we just using libunwind for this?
>>
>
> http://codereview.chromium.org/3120017/show
>

[Alexander Potapenko, 2010-08-19 15:00:28]

On 2010/08/19 14:57:29, willchan wrote:
> Ah yes, that's right.  I forgot that, thanks for reminding me!
> 
> Is this a change we can contribute directly to google-perftools?  Is your
> plan to implement in chromium first and then upstream?
> 
I'm not sure google-perftools need this change, because it always requires
rebuilding all client code with -finstrument-functions. Let me ask the perftools
people.

[willchan no longer on Chromium, 2010-08-19 15:34:25]

Which file did you branch stacktrace_shadow-inl.h from?  I want to run a diff so
I can see what changed.  I don't really want to review it from scratch if I can
avoid it.

http://codereview.chromium.org/3120017/diff/1/3
File build/common.gypi (right):

http://codereview.chromium.org/3120017/diff/1/3#newcode840
build/common.gypi:840: '-finstrument-functions',
Why is this being done by default?  Shouldn't it only be done when
linux_keep_shadow_stacks==1?

[Alexander Potapenko, 2010-08-19 15:40:29]

It's stacktrace_x86-inl.h
In fact I can just change it under #ifdef without forking if necessary -- the
diff is not that big.
On 2010/08/19 15:34:25, willchan wrote:
> Which file did you branch stacktrace_shadow-inl.h from?  I want to run a diff
so
> I can see what changed.  I don't really want to review it from scratch if I
can
> avoid it.
>

[willchan no longer on Chromium, 2010-08-22 16:30:46]

There doesn't seem to be a resolution on this approach on the google-perftools
thread.  Do you mind if I wait for that being reviewing this?  Or do you think I
should go ahead with this?  If so, then yes, please make the change without
forking.

On 2010/08/19 15:40:29, Alexander Potapenko wrote:
> It's stacktrace_x86-inl.h
> In fact I can just change it under #ifdef without forking if necessary -- the
> diff is not that big.
> On 2010/08/19 15:34:25, willchan wrote:
> > Which file did you branch stacktrace_shadow-inl.h from?  I want to run a
diff
> so
> > I can see what changed.  I don't really want to review it from scratch if I
> can
> > avoid it.
> >

[Alexander Potapenko, 2010-08-23 13:35:00]

> 
> http://codereview.chromium.org/3120017/diff/1/3
> File build/common.gypi (right):
> 
> http://codereview.chromium.org/3120017/diff/1/3#newcode840
> build/common.gypi:840: '-finstrument-functions',
> Why is this being done by default?  Shouldn't it only be done when
> linux_keep_shadow_stacks==1?

Fixed

[Alexander Potapenko, 2010-08-23 13:40:24]

On 2010/08/22 16:30:46, willchan wrote:
> There doesn't seem to be a resolution on this approach on the google-perftools
> thread.  Do you mind if I wait for that being reviewing this?  Or do you think
I
> should go ahead with this? 
I think it's better to submit the current version before we find out how to make
libunwind usable by external developers.
> If so, then yes, please make the change without
> forking.
Done

[willchan no longer on Chromium, 2010-08-24 15:20:36]

Functionally the code looks good to me.  I only have stylistic nits.

http://codereview.chromium.org/3120017/diff/14001/15004
File third_party/tcmalloc/chromium/src/stacktrace_x86-inl.h (right):

http://codereview.chromium.org/3120017/diff/14001/15004#newcode328
third_party/tcmalloc/chromium/src/stacktrace_x86-inl.h:328: int shadow_index =
stack_size-1;
http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml#Horizontal_Whi...

In particular:
"v = w * x + y / z;  // Binary operators usually have spaces around them,"

Please fix the instances of these in your change.

http://codereview.chromium.org/3120017/diff/14001/15004#newcode330
third_party/tcmalloc/chromium/src/stacktrace_x86-inl.h:330: if (sp ==
shadow_sp_stack[i]) shadow_index = i;
should you also break; if you find the matching stack pointer?

http://codereview.chromium.org/3120017/diff/14001/15004#newcode346
third_party/tcmalloc/chromium/src/stacktrace_x86-inl.h:346: shadow_index--;
Doesn't shadow_index only exist when KEEP_SHADOW_STACKS is defined?  Will this
break the compile when it's not defined?

http://codereview.chromium.org/3120017/diff/14001/15004#newcode378
third_party/tcmalloc/chromium/src/stacktrace_x86-inl.h:378: } else {
I'm not sure, but it might be cleaner if you continue; after the n++, and then
break; if not, rather than having two else clauses that break;.  Up to you.

http://codereview.chromium.org/3120017/diff/14001/15004#newcode386
third_party/tcmalloc/chromium/src/stacktrace_x86-inl.h:386: #endif
comment KEEP_SHADOW_STACKS

[Alexander Potapenko, 2010-08-25 10:01:18]

http://codereview.chromium.org/3120017/diff/14001/15004
File third_party/tcmalloc/chromium/src/stacktrace_x86-inl.h (right):

http://codereview.chromium.org/3120017/diff/14001/15004#newcode328
third_party/tcmalloc/chromium/src/stacktrace_x86-inl.h:328: int shadow_index =
stack_size-1;
On 2010/08/24 15:20:36, willchan wrote:
>
http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml#Horizontal_Whi...
> 
> In particular:
> "v = w * x + y / z;  // Binary operators usually have spaces around them,"
> 
> Please fix the instances of these in your change.

Done.

http://codereview.chromium.org/3120017/diff/14001/15004#newcode330
third_party/tcmalloc/chromium/src/stacktrace_x86-inl.h:330: if (sp ==
shadow_sp_stack[i]) shadow_index = i;
On 2010/08/24 15:20:36, willchan wrote:
> should you also break; if you find the matching stack pointer?

Yes, assuming that the shadow stack is valid. Fixed.

http://codereview.chromium.org/3120017/diff/14001/15004#newcode346
third_party/tcmalloc/chromium/src/stacktrace_x86-inl.h:346: shadow_index--;
On 2010/08/24 15:20:36, willchan wrote:
> Doesn't shadow_index only exist when KEEP_SHADOW_STACKS is defined?  Will this
> break the compile when it's not defined?

True. I've added an ifdef here.

http://codereview.chromium.org/3120017/diff/14001/15004#newcode378
third_party/tcmalloc/chromium/src/stacktrace_x86-inl.h:378: } else {
On 2010/08/24 15:20:36, willchan wrote:
> I'm not sure, but it might be cleaner if you continue; after the n++, and then
> break; if not, rather than having two else clauses that break;.  Up to you.

Done.

http://codereview.chromium.org/3120017/diff/14001/15004#newcode386
third_party/tcmalloc/chromium/src/stacktrace_x86-inl.h:386: #endif
On 2010/08/24 15:20:36, willchan wrote:
> comment KEEP_SHADOW_STACKS

Fixed here and above.

[Alexander Potapenko, 2010-08-25 10:17:22]

PTAL

(Patch Set 4) Fixed some nits in linux_shadow_stacks.cc
(Patch Set 5) Added linux_shadow_stacks.h (sorry for missing it originally)

BTW, is it ok to have Chromium-licensed files (linux_shadow_stacks.*) in the
third_party/ dir?

[willchan no longer on Chromium, 2010-08-25 16:16:31]

LGTM

http://codereview.chromium.org/3120017/diff/22002/25004
File third_party/tcmalloc/chromium/src/linux_shadow_stacks.h (right):

http://codereview.chromium.org/3120017/diff/22002/25004#newcode8
third_party/tcmalloc/chromium/src/linux_shadow_stacks.h:8: #define NO_INSTRUMENT
__attribute__((no_instrument_function))
You should #undef this afterward.

[Alexander Potapenko, 2010-08-26 10:44:55]

> http://codereview.chromium.org/3120017/diff/22002/25004#newcode8
> third_party/tcmalloc/chromium/src/linux_shadow_stacks.h:8: #define
NO_INSTRUMENT
> __attribute__((no_instrument_function))
> You should #undef this afterward.

Fixed.

Yet again: is it ok to put non-3rd party code into third_party/?
And is it ok to reuse a piece of code from perftools in that non-3rd party code?
(I assume this won't violate any policies. Anyway, we're going to upstream that
change)

[willchan no longer on Chromium, 2010-08-26 14:35:00]

On Thu, Aug 26, 2010 at 6:44 AM, <glider@chromium.org> wrote:

> http://codereview.chromium.org/3120017/diff/22002/25004#newcode8
>> third_party/tcmalloc/chromium/src/linux_shadow_stacks.h:8: #define
>>
> NO_INSTRUMENT
>
>> __attribute__((no_instrument_function))
>> You should #undef this afterward.
>>
>
> Fixed.
>
> Yet again: is it ok to put non-3rd party code into third_party/?
>

I view this as totally fine.  We've added extra files for TCMalloc plenty of
times.


> And is it ok to reuse a piece of code from perftools in that non-3rd party
> code?
> (I assume this won't violate any policies. Anyway, we're going to upstream
> that
> change)


Yeah, I think this is fine too.  You should copy the file comment block into
the place where you use it, since it says that redistributions and use in
source must include the comment block.


>
>
> http://codereview.chromium.org/3120017/show
>