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/

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.

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

[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

[dewar]

<<Well, just because somebody has proven that something is not computable
doesn't mean you have to believe him.
>>

Actually that's more true than you might think. Just because something is
non-computable in general does not mean that it is impractical to compute
it in specific cases, and it can even happen that in practice all cases
that actually arise are in this category.