Compile Time Memory Leak Analyses

Compile Time Memory Leak Analyses

[Kevin Atkinson]

I was wondering if anyone has given the following idea any thought:

Provide a method of tagging functions (perhaps automatically) on the
memory behavior of there parameters and what they return.  That is tagging
each parameter which is a pointer as either unconditionally freeing a
pointer passed in, conditionally freeing a pointer, or never freeing a
pointer.  And tagging the pointer returned as always needing to be freed,
sometimes needing to be freed, or never needing to be freed.

This information can then be used to detect simple memory problems by
performing flow analyses on a pointer and determine if:
1) A pointer is never freed when should be
2) An already deleted pointer is freed
3) A pointer is freed that shouldn't be

Of course when functions are used that are in the "conditional" class, or
a pointer is copied around several times and it is not possible to
determine if it all of them go out of scope before the data pointed to by
them is freed.  However, it will get a good deal of the simpler cases and
can help a lot of people out by detecting the obvious memory problems.

A similar analyses can be used when a garbage collector is used to
automatically delete blocks of memory when it can be determined that all
pointers pointing to by that memory goes out of scope.  This has the
potential to greatly red using memory usage.

I am not saying that it will be easy (especially the part of the automatic
tagging) however I defiantly think it is possible and would greatly reduce
memory problems in some programs.

---
Kevin Atkinson
kevina at users sourceforge net
http://www.ibiblio.org/kevina/

Re: Compile Time Memory Leak Analyses

[Tim Hollebeek]

On Mon, Jul 16, 2001 at 08:58:03AM -0400, Kevin Atkinson wrote:
> I was wondering if anyone has given the following idea any thought:
> 
> Provide a method of tagging functions (perhaps automatically) on the
> memory behavior of there parameters and what they return.  That is tagging
> each parameter which is a pointer as either unconditionally freeing a
> pointer passed in, conditionally freeing a pointer, or never freeing a
> pointer.  And tagging the pointer returned as always needing to be freed,
> sometimes needing to be freed, or never needing to be freed.

LCLint does something like this.

-Tim

Re: Compile Time Memory Leak Analyses

[Kevin Atkinson]

On Mon, 16 Jul 2001, Tim Hollebeek wrote:

> On Mon, Jul 16, 2001 at 08:58:03AM -0400, Kevin Atkinson wrote:
> > I was wondering if anyone has given the following idea any thought:
> >
> > Provide a method of tagging functions (perhaps automatically) on the
> > memory behavior of there parameters and what they return.  That is tagging
> > each parameter which is a pointer as either unconditionally freeing a
> > pointer passed in, conditionally freeing a pointer, or never freeing a
> > pointer.  And tagging the pointer returned as always needing to be freed,
> > sometimes needing to be freed, or never needing to be freed.
>
> LCLint does something like this.

Yes but is only good for C not C++.  It would be really nice if the type
of extensive analyses the LCLint program does could be part of the Gcc
compiler, as it will work with all the languages Gcc supports.

---
Kevin Atkinson
kevina at users sourceforge net
http://www.ibiblio.org/kevina/

Re: Compile Time Memory Leak Analyses

[Joern Rennecke]

> I am not saying that it will be easy (especially the part of the automatic
> tagging) however I defiantly think it is possible and would greatly reduce
> memory problems in some programs.

In thinking so, you defy Rice's theorem.
Well, just because somebody has proven that something is not computable
doesn't mean you have to believe him.

Re: Compile Time Memory Leak Analyses

[Joe Buck]

> > I am not saying that it will be easy (especially the part of the automatic
> > tagging) however I defiantly think it is possible and would greatly reduce
> > memory problems in some programs.
> 
> In thinking so, you defy Rice's theorem.
> Well, just because somebody has proven that something is not computable
> doesn't mean you have to believe him.

Not at all.  Undecidability theorems mean only that an analysis routine
that tries to establish whether property P is true must return a
three-valued result (yes, no, and "I don't know").  gcc is full of
such code.  If there are many cases where a definite answer can be
given, the tool can be useful.

After all, reachability is also undecidable, but we still eliminate dead
code.

Re: Compile Time Memory Leak Analyses

[Joern Rennecke]

> Not at all.  Undecidability theorems mean only that an analysis routine
> that tries to establish whether property P is true must return a
> three-valued result (yes, no, and "I don't know").  gcc is full of
> such code.  If there are many cases where a definite answer can be
> given, the tool can be useful.
> 
> After all, reachability is also undecidable, but we still eliminate dead
> code.

Well, but that's an optimization.  We optimize only when we know that it
is safe (at least that's the theory ;-), so while we can't tolerate false
positives, we can tolerate false negatives.

However, for warnings, false positives are extremely annoying, while
false negatives mean that you can miss potential bugs while you are
lulled into a false security that the compiler will warn about problems.

So we set ourselves up for a warning that is likely to become as awkward as
the uninitialized warnings.

Re: Compile Time Memory Leak Analyses

[Kevin Atkinson]

On Tue, 17 Jul 2001, Joern Rennecke wrote:

> > Not at all.  Undecidability theorems mean only that an analysis routine
> > that tries to establish whether property P is true must return a
> > three-valued result (yes, no, and "I don't know").  gcc is full of
> > such code.  If there are many cases where a definite answer can be
> > given, the tool can be useful.
> >
> > After all, reachability is also undecidable, but we still eliminate dead
> > code.
>
> Well, but that's an optimization.  We optimize only when we know that it
> is safe (at least that's the theory ;-), so while we can't tolerate false
> positives, we can tolerate false negatives.
>
> However, for warnings, false positives are extremely annoying, while
> false negatives mean that you can miss potential bugs while you are
> lulled into a false security that the compiler will warn about problems.
>
> So we set ourselves up for a warning that is likely to become as awkward as
> the uninitialized warnings.

Actually I find the uninitialized warnings rather useful and every know
and then compile by program with "-O -Wall" just so I can get them and
make sure everything is OK.

---
Kevin Atkinson
kevina at users sourceforge net
http://www.ibiblio.org/kevina/

Uninitialized warnings

[Dale Johannesen]

On Monday, July 16, 2001, at 08:25 PM, Kevin Atkinson wrote:
> On Tue, 17 Jul 2001, Joern Rennecke wrote:
>> So we set ourselves up for a warning that is likely to become as 
>> awkward as
>> the uninitialized warnings.
>
> Actually I find the uninitialized warnings rather useful and every know
> and then compile by program with "-O -Wall" just so I can get them and
> make sure everything is OK.

Ah yes, the uninitialized warnings.  Some of our users have noticed they 
only appear when optimization is on, and they don't like it.  It seems 
that the dataflow analysis required could be done even without other 
optimization, and probably wouldn't cost too much in terms of execution 
speed.  OTOH, gcc has behaved this way for about 15 years, and I doubt 
we're the first people to think of this, which gives me pause.  Is a 
patch that checks for uninitalized variables even without optimization 
likely to be accepted?

Re: Uninitialized warnings

[Carlo Wood]

On Tue, Jul 17, 2001 at 09:51:06AM -0700, Dale Johannesen wrote:
> we're the first people to think of this, which gives me pause.  Is a 
> patch that checks for uninitalized variables even without optimization 
> likely to be accepted?

Please don't add any warning that can generate false positives.
I'd rather have no warning at all for 100 actual bugs than
100 correct warnings and a false positive.  The reason for
that is that I always use -Werror: I want gcc to abort when
a warning is generated.  The reason for THAT is that a warning
always means that something *is* wrong and will (likely) cause
a runtime error.

If I'd have to suggest an alternative/compromise, then I'd say:
make it possible to temporally turn off a specific warning in
the source code.

For example:

void bar(int k)
{
  int i;
  assert( k >= -1 );
  if (k == -1)
    i = 2;
  else if (k == 0)
    i = 3;
  if (k > 0)
    foo(3);
  else
#pragma warning 45 push,off		// suppress 'possible uninitialized use of i'
    foo(i);
#pragma warning 45 pop
}

-- 
Carlo Wood <carlo@alinoe.com>

Re: Uninitialized warnings

[Dale Johannesen]

On Tuesday, July 17, 2001, at 03:33 PM, Carlo Wood wrote:

> On Tue, Jul 17, 2001 at 09:51:06AM -0700, Dale Johannesen wrote:
>> we're the first people to think of this, which gives me pause.  Is a
>> patch that checks for uninitalized variables even without optimization
>> likely to be accepted?
>
> Please don't add any warning that can generate false positives.
> I'd rather have no warning at all for 100 actual bugs than
> 100 correct warnings and a false positive.

Believe it or not, I agree with you, but I'm definitely in a small 
minority (1?) around here.  Is there a consensus on how the 
uninitialized-variable check should behave?

Re: Uninitialized warnings

[Stan Shebs]

On Tuesday, July 17, 2001, at 03:33 PM, Carlo Wood wrote:

> On Tue, Jul 17, 2001 at 09:51:06AM -0700, Dale Johannesen wrote:
>> we're the first people to think of this, which gives me pause.  Is a
>> patch that checks for uninitalized variables even without optimization
>> likely to be accepted?
>
> Please don't add any warning that can generate false positives.
> I'd rather have no warning at all for 100 actual bugs than
> 100 correct warnings and a false positive. [...]

I think there's some confusion here.  What Dale is getting at
is that -Wuninitialized is basically useless without -O<something>,
so why not make -Wuninitialized turn on enough dataflow analysis
to be meaningful, but without letting it alter the output?  In other
words, fix -Wuninitialized, even it means making the compiler run
a little more slowly when the flag is on.

The current documented behavior just seems lame to me, one of
those snake-pit-in-the-middle-of-the-living-room-floor traditional
things that don't make any sense to an objective observer.

Stan

Re: Uninitialized warnings

[Diego Novillo]

On Tue, 17 Jul 2001, Stan Shebs wrote:

> On Tuesday, July 17, 2001, at 03:33 PM, Carlo Wood wrote:
> 
> > On Tue, Jul 17, 2001 at 09:51:06AM -0700, Dale Johannesen wrote:
> >> we're the first people to think of this, which gives me pause.  Is a
> >> patch that checks for uninitalized variables even without optimization
> >> likely to be accepted?
> >
> > Please don't add any warning that can generate false positives.
> > I'd rather have no warning at all for 100 actual bugs than
> > 100 correct warnings and a false positive. [...]
> 
> I think there's some confusion here.  What Dale is getting at
> is that -Wuninitialized is basically useless without -O<something>,
> so why not make -Wuninitialized turn on enough dataflow analysis
> to be meaningful, but without letting it alter the output?  In other
> words, fix -Wuninitialized, even it means making the compiler run
> a little more slowly when the flag is on.
> 
FWIW, this should be relatively straightforward to implement once
the tree SSA infrastructure is incorporated.  The current
version is already doing reachability analysis for
-Wunreachable-code using the flowgraph.

Checking for potentially uninitialized variables is just a matter
of traversing the use-def web.  It might take a while until the
code is stable enough to be of any real use, of course.

Diego.

Re: Compile Time Memory Leak Analyses

[Joe Buck]

I wrote:
> > Not at all.  Undecidability theorems mean only that an analysis routine
> > that tries to establish whether property P is true must return a
> > three-valued result (yes, no, and "I don't know").  gcc is full of
> > such code.  If there are many cases where a definite answer can be
> > given, the tool can be useful.
> > 
> > After all, reachability is also undecidable, but we still eliminate dead
> > code.

Joern writes:
> Well, but that's an optimization.  We optimize only when we know that it
> is safe (at least that's the theory ;-), so while we can't tolerate false
> positives, we can tolerate false negatives.
> 
> However, for warnings, false positives are extremely annoying, while
> false negatives mean that you can miss potential bugs while you are
> lulled into a false security that the compiler will warn about problems.
> 
> So we set ourselves up for a warning that is likely to become as awkward as
> the uninitialized warnings.

It has been frequently argued that gcc should make no attempt to try to
detect dangerous condition X (e.g. aliasing violations, or leaks in this
case), because it cannot detect all violations and would thus lead users
into a false sense of security.

I disagree; I think we're doing the world a service if we detect more
bugs.  Perhaps the limitations can be stressed in option naming:
-Wobvious-leaks, -Wobvious-alias-violations.  As the names suggest,
I would bias the test to avoid reporting any false positives.  The
tests could then be enabled as part of -Wall.

Re: Compile Time Memory Leak Analyses

[J.T. Conklin]

>>>>> "Joe" == Joe Buck <jbuck@synopsys.COM> writes:
>> Well, but that's an optimization.  We optimize only when we know
>> that it is safe (at least that's the theory ;-), so while we can't
>> tolerate false positives, we can tolerate false negatives.
>> 
>> However, for warnings, false positives are extremely annoying,
>> while false negatives mean that you can miss potential bugs while
>> you are lulled into a false security that the compiler will warn
>> about problems.
>> 
>> So we set ourselves up for a warning that is likely to become as
>> awkward as the uninitialized warnings.

Joe> It has been frequently argued that gcc should make no attempt to
Joe> try to detect dangerous condition X (e.g. aliasing violations, or
Joe> leaks in this case), because it cannot detect all violations and
Joe> would thus lead users into a false sense of security.

Joe> I disagree; I think we're doing the world a service if we detect
Joe> more bugs.  Perhaps the limitations can be stressed in option
Joe> naming: -Wobvious-leaks, -Wobvious-alias-violations.  As the
Joe> names suggest, I would bias the test to avoid reporting any false
Joe> positives.  The tests could then be enabled as part of -Wall.

A commercial lint package I'm quite fond of "solves" this problem by
having multiple layers of warnings.  For example, "may not have been
initialized", "conceivably not initialized", and "not initialized".
Since every warning can be individually enabled/disabled, a user can
choose whether or not to include possible false hits in the output.
For what it's worth, I've found this to be very useful.

        --jtc
-- 
J.T. Conklin
RedBack Networks

Re: Uninitialized warnings

[dewar]

One request I have, and please ignore it if it has already been discussed,
is that the uninitialized variable warning is currently very uninformative,
since it does not indicate the site at which the uninitialized reference
may occur, and sometimes it takes a big effort to determine why the warning
is being issued. Is this information that can be provided?

Re: Uninitialized warnings

[Richard Henderson]

On Wed, Jul 18, 2001 at 12:55:04PM -0400, dewar@gnat.com wrote:
> One request I have, and please ignore it if it has already been discussed,
> is that the uninitialized variable warning is currently very uninformative,
> since it does not indicate the site at which the uninitialized reference
> may occur, and sometimes it takes a big effort to determine why the warning
> is being issued. Is this information that can be provided?

Not with the current code.

The way this works is that we solve global data flow, and for
every variable that is live on entry to the function we check
that it is either a global register or a function argument.
Anything else gets a warning.


r~

Re: Uninitialized warnings

[dewar]

<<Believe it or not, I agree with you, but I'm definitely in a small
minority (1?) around here.  Is there a consensus on how the
uninitialized-variable check should behave?
>>

A bug that is found by examining a warning at compile time represents a huge
cost savings over having to find this same bug during unit testing, system
integration testing, or worse, not finding it at all and having it cause
damage after deployment.

That means to me that one is willing to tolerate quite a few false positives
to find one real bug at compile time.

I do agree that you need a way to selectively turn off warnings so that
sources can be kept clean.

A specific case in point is that when we first ran the GNAT sources through
GCC 3.x, we got about 60 warnings about possibly uninitialized variables.
Six of these were definite bugs, and one of them was a potentially serious
bug. Going through those 60 warnings to find that potentially serious bug
*before* it caused someone trouble was *well* worth the effort.

Re: Uninitialized warnings

[dewar]

<<Please don't add any warning that can generate false positives.
I'd rather have no warning at all for 100 actual bugs than
100 correct warnings and a false positive.  The reason for
that is that I always use -Werror: I want gcc to abort when
a warning is generated.  The reason for THAT is that a warning
always means that something *is* wrong and will (likely) cause
a runtime error.
>>

I strongly disagree with this point of view. Any warning by its nature
may have false positives, you are after all dealing with legal code with
a well defined meaning, you are just guessing that it is not the intended
meaning, but you cannot be sure your guess is correct.

Obviously you don't want too many false positives, but the 100-1 suggestion
here is way off the reasonable compromise point.

<<If I'd have to suggest an alternative/compromise, then I'd say:
make it possible to temporally turn off a specific warning in
the source code.
>>

In GNAT, we have added pragma Warnings (On | Off); to handle this problem
when it occasionally arises, since it is a requirement of the GNAT build
that no warnings are generated

uninitialized warnings

[Jeffrey A Law]

I'd recommend we hold off just a little while fixing these -- I
want to look into fixing the compiler to produce fewer false
positives.



jeff