|
From: Bryan M. <om...@br...> - 2006-09-02 20:49:20
|
Julian,
I had an idea while writing this reply (6 odd hours ago) and as a
result, I have actually solved it, tested it on both boxes (in 32bit and
64bit mode on my Athlon64 box) and am just tidying up a couple of bits
and bobs before posting Beta05! :D
for the record:
Problem:
The accumulator contains the final live pointer to a memory block on
return from a function but should actually die at that point as the
function does not in fact return a value (a 'C' void type function).
Eventual overwrite of the value in the accumulator produces a stack
trace far from the actual point where the leak should have been reported.
Solution:
On function exit, note that the accumulator is the only live pointer to
that memory block and store a stack trace that references the end of the
function. When the accumulator is overwritten, note that it matches the
last live reference we stored earlier then use the stack trace that was
stored earlier in the leak report(s).
If another reference is added to the block (it was a return value after
all), clear the stored information so that any future leak can be
reported normally.
In the case of nested calls, we do not overwrite the cached stack trace
because we confirm that the accumulator is still the only live reference
so leave it pointing to the original "actual leak" position.
I have left some of the comments in below as I think it useful to have
them on record, should anyone come along asking questions about stuff
like optimised code or support or more usefully, what the test cases are
looking for and why.
Bryan
Julian Seward wrote:
> I can see that some info like that would be helpful, but I'm concerned
> that it might be a case of fixing the symptoms (and/or adding a fix
> which makes sense only for eg x86 and not generally).
I agree - that was the main reason for checking before going ahead.
Whilst it would partially solve my problems, there is undetermined
impact in other areas.
>
> What I think would be helpful is to make a concise, semi-formal
> statement of the problem. I think this would help by showing how this
> relates to standard compiler concepts of liveness and reachability.
> In particular I'd like to find a solution which gives accurate results
> and which works well even in the presence of optimised code, which AIUI
> Omega currently doesn't.
The main problem with optimised code is generating any sort of useful
information to clue the user into just where things are happening.
Tracking is not the problem (although there are some issues that I would
like to clean up when the un-optimised case is correct), its the lack of
correspondence to the original source code flow. You know what it's like
trying to debug optimised code when you single step and the debugger
does anything but on the source display, leaping up and down all over
the place. Function in-lining and tail calls are also a severe problem
as it makes function scope almost impossible to determine.
>
> My initial thoughts at such a statement are:
>
> - keep track of all allocated blocks
>
> - keep track of all potential roots. Potential roots at any
> time are
>
> * the words in all currently accessible memory, plus the words
> in the registers
> BUT
> only those for which the next event is a read
Omega handles a specialised case of this in order to cope with a common
program idiom. From the web page:
----------------------------------------------------
Lets say you have something along the lines of this:
1 secret *foo = (secret *)malloc(sizeof(bar) + sizeof(secret) +
alignment_correction);
2 foo->secret_stuff = magic_key;
3 etc.
4 foo++;
5 return (bar*)foo;
Internally, Omega uses shadow blocks to track references within an
allocated block. Thus, when you increase "foo" on line 4, Omega creates
a shadow block that ties back to the main block allocated at line 1
instead of raising a leak report.
----------------------------------------------------
Without this special case handling, Omega produces meaningless results
in the presence of any custom allocation.
>
> - If some part of the address space disappears, that can be thought of
> as a write.
>
> - If a write (to a potential root) happens, and that destroys the last
> pointer to a particular block, then we can complain at that point
> of a leak.
>
> - However, that may be too late. (as per current example)
>
> What we really want to find is something along the lines of
> 'dead writes' (to registers and memory). A dead write puts a value
> into that storage location which is never read, only overwritten
> (or the storage location goes out of scope, which is equivalent).
>
> Perhaps it should be that a leak is reported at a dead write of
> the last pointer to a block. Or something. Anyway, the general
> idea is: if you can characterise the problem in terms of dataflow
> and liveness, perhaps it becomes possible to build an implementation
> which is robust to ABI changes, compiler optimisation, and across
> different platforms.
>
> The above ideas are half-baked; don't take the details too literally.
They are actually pretty much all of it...
>
> ---
>
> Another thing that would help (perhaps the same thing, really)
> is to give a very precise specification of what the tool is intended
> to do.
>
> Originally I had the impression that it was "find where the last pointer
> to block X is overwritten"; but when looked at under a magnifying glass
> it's clear this can lead to error reports which point to some location
> in the code flow which may be arbitrarily far after the place where you
> really wanted to report the error. So (and I think this is the crux
> of the problem) how do you precisely specify those program points where
> you *do* want to report an error?
>
> J
>
When a block is allocated (through malloc(), realloc() etc), a pointer
is returned to the calling program. Omega tracks this pointer and any
copies that are created and destroyed until such time that the block is
free()ed (through free() or realloc() with a bigger block size) or the
last pointer is lost, either by being overwritten or the containing
storage going out of scope or "dying".
In the Omega source are a number of small test cases that demonstrate
the classes of situation where Omega should report a useful message for
the user. They fall into 3 main categories:
Block
Overwrite
Scope
Block
-----
These tests (and functionality) deal with pointers stored in other heap
allocated blocks ie. the pointer to allocated block B is stored within
allocated block A. The lifetime of the pointer to block B (assuming it
is never overwritten) is determined by the lifetime of block A. If block
A is returned to the OS or leaks, the pointer to block B dies at this
point. If this is the last pointer to block B, then block B leaks and so
on. This functionality is quite simple as it involves death of storage
and little else. Typically, if a leak occurs it will be within the
free() function because some malloc()ed structure has pointers to other
malloc()ed structures and they weren't cleaned up properly before the
base structure was free()ed. Singly linked lists can generate long
chains of leaks if you overwrite the head pointer.
Overwrite
---------
These tests deal with the destruction of the pointer itself, rather than
the lifetime of the storage where the pointer resides. The simplest case
is overwriting a pointer (in memory or a register) with another value
(ie. NULL). If the last pointer to a block is overwritten then a leak of
that block occurs at that point. There is a specialisation of this
namely the shadow block stuff mentioned inline above.
Scope
-----
These tests deal with the death of storage (the Block section above is a
specific form of this that deals with heap allocated storage). The
non-heap storage is either stack or register based. Automatic variables
live on the stack and as such, when the function exits and the stack
pointer is moved, their storage dies. Any pointers within automatic
variables are therefore lost when the stack unwinds generating a leak
report on the last line of the function. Seeing a report here is a sure
sign that your automatic variable went out of scope holding a pointer
that you didn't stash somewhere else or free().
(**next bit written just as the brain-wave hit**)
The other part of scope, and this is the bit that is currently standing
in the way of a full blown release candidate, is the scope of registers.
The ABI for each architecture (I can only cover x86 and x86_64 here -
whilst I don't actually know x86 assembler, I have never played with
Power Architecture assembler in my life) gives a preferred use or
purpose for each of the registers and also details function entry and
exit along with parameter passing in each direction. So, as a function
returns and the stack unwinds, any register that is described in the ABI
as belonging to the called function should now be classed as dead. This
is fine and works well apart from a single fly in the ointment - the
accumulator can optionally be used to return a value of some description
to the calling function. The problem is that there is no way to easily
determine if a function is going to return a value in the accumulator or
not. The accumulator is a scratch register so could well contain a valid
pointer that should not in fact survive past the end of the function.
scope2.c in the tests directory looks like this:
----------------------------------------------------
#include <stdlib.h>
static void func1(void)
{
char *pointer = 0;
pointer = malloc(64); /* Line 7 */
return;
} /* Leak report Line 10 */
int main(int argc, char *argv[])
{
func1();
return 0;
}
----------------------------------------------------
If you debug this program in mixed source/assembler, it is clear that at
the exit of func1(), the accumulator holds the value returned by
malloc(64) and also stored in the variable "pointer". Whilst the storage
for the variable dies as the stack unwinds, we cannot easily tell from
the assembler whether func1() is returning the value in the accumulator
or not. Ideally, the leak report should occur at line 10. If we do not
invalidate the accumulator, the leak report will occur at line 15 where
main() set's it's return value, finally overwriting the accumulator.
|