Analyzer discrepancy with __builtin_alloca

Hello,

I was working on adding alloca/valloc checks (as well as a small
cleanup) to UnixAPIChecker following the recent changes to detect
zero-sized allocations in calloc/realloc (SVN r147500,) when I noticed
a strange issue when attempting to identify calls to __builtin_alloca.

'alloca' seems to dissolve to __builtin_alloca via a CPP #define on OS
X, so for the check to work and be 'complete' it needs to identify
both names. However, it seems as if the checker callback -
checkPreStmt on a CallExpr - is not invoked for calls to
__builtin_alloca, but it does work just dandy in the case of say,
__builtin_expect. So presumably I'm missing something important and
it's expected behavior, or this is a bug I guess.

A little more concrete: I amended ./test/Analysis/unix-fns.c to
contain calls for alloca - with a prototyped definition so there
aren't complaints about implicit declarations - *and* calls to
__builtin_alloca, both of which should trigger a 0-sized allocation
warning. I also modified UnixAPIChecker to dump the name of every
callee it comes across, or dump some trivial output if it skips the
call due to getCalleeName returning an empty StringRef.

The results look like this on my machine:

$ /Users/a/code/llvm-build/Debug+Asserts/bin/clang -cc1
-internal-isystem
/Users/a/code/llvm-build/Debug+Asserts/bin/../lib/clang/3.1/include
-triple x86_64-apple-darwin10 -analyze
-analyzer-checker=unix.API,osx.API
/Users/a/code/llvm/tools/clang/test/Analysis/unix-fns.c
-analyzer-store=region -fblocks -verify
fname = open
fname = open
fname = close
fname = open
fname = __builtin_expect
fname = dispatch_once
fname = __builtin_expect
fname = dispatch_once
fname = pthread_once
fname = pthread_once
fname = malloc
fname = malloc
fname = calloc
fname = calloc
fname = calloc
fname = realloc
fname = realloc
fname = alloca
fname = alloca
fname = valloc
fname = valloc

The calls to __builtin_alloca should effectively appear in the same
spot as the 'alloca' calls, but they clearly aren't. There also isn't
any 'no name' output indicating the call was skipped as a result of an
empty StringRef from getCalleeName. So it seems as if checkPreStmt for
a CallExpr completely skips over __builtin_alloca. The calls do appear
in a dump of the CFG as you would likely expect.

Is __builtin_alloca handled specially in the analyzer somewhere, and
thus I'm missing something? If it is and this is unavoidable, I'll
just back out those changes and send a patch containing the valloc
addition as well as the small cleanup if they're worth it. But I don't
see off hand why it can't work for alloca as well, so I thought I'd
ask.

Hi Austin,

The logic for __builtin_alloca is being handled by BuiltinFunctionChecker, which explicitly models the semantics of the function. It does this by responding to 'evalCall()'. That should not interfere with the checkPreStmt() callback in UnixAPIChecker, and if that is the case there is a bug here.

What is likely the case is that builtins are just modeled slightly differently in the AST. I suggest that you take a look at BuiltinFunctionChecker for how we recognize calls to __builtin_alloca and see if that approach works for you. In any case, please follow-up on the list to see if that fixes or doesn't fix the issue you are seeing.

Cheers,
Ted

Hi Ted,

Thanks for the reply. I just found BuiltinFunctionChecker and see that
it deals with both __builtin_alloca and __builtin_expect, but there's
still something awry here I think.

For one, as I said before, I modified checkPreStmt to tell me both
when getCalleeName returns an empty StringRef (i.e. it is ignored,)
and in the case it doesn't, output the callee name. But per the output
above, it neither says the call exists, or that it skipped it due to
the empty StringRef - so it seems checkPreStmt is in fact -never-
called in the case of __builtin_alloca! I played around with
BuiltinFunctionChecker's route of getting the FunctionDecl and looking
if it corresponds to a builtin's ID, but as you would expect - no
dice.

The other concerning thing is that BuiltinFunctionChecker also has
logic to deal with __builtin_expect, but despite that it appears
perfectly normally as you would expect when checkPreStmt is invoked in
the testcase. There is no difference semantically or AST-wise between
__builtin_expect and any other function call here - you can just look
at the textual name. So if there -is- a discrepancy, it most certainly
seems to concern itself only with __builtin_alloca. Or,
__builtin_alloca is being handled correctly, and __builtin_expect is
in fact the buggy case here (my brain tells me it is likely the
former, since as far as the analyzer is concerned, I think __builtin's
would be recognized as a regular call expression like any other.)
Either way something weird is going on that should be fixed.

I went ahead and added a simplistic evalCall callback to
UnixAPIChecker to see if it could identify the call to
__builtin_alloca, much in the same way BuiltinFunctionChecker does.
This *does not work either* in fact! So now I'm pretty darn confused.

I think there's very clearly a bug or something lurking here, but I'm
at a loss as to how to proceed. Attached is my patch to UnixAPIChecker
with some helper debugging output, and appropriate modifications to
the testsuite which should expose the problem (the compiler will
complain that there was an expected warning, but none was found.)
Since the crappy debug output will fudge up the 'make test' runner I'd
just advise checking unix-fns.c for the easy case.

Please excuse the inclusion of iostream - a blatant violation of LLVM
coding practice; I just needed a quick and simple dump. I also
apologize that I had to include the small refactoring and valloc
addition I mentioned as part of the patch, but the work was already
there. I hope you find it useful in making sense of things.

Thanks for the help, and sorry for the long-winded rant.

PS. There seems to be further weirdness upon review of my test output
that doesn't concern itself with builtins, but, I'll go ahead and
mention it and possibly put it into another cfe-dev thread, or a
bugzilla ticket - look closely at the unix-fns.c analysis test, and
then look at the output produced in my example with my little patch.
The weird part is how the analyzer identifies the first 4 calls being
'open, open, close, open', in that order, but in the source code, the
analyzer *should* be seeing open, close, open, close! In fact, it only
sees 1 close call, period! After those 4 calls, all further calls are
identified properly, 'in order' as you would expect to see. I may be
missing something, but that seems to indicate something Very Bad is
happening.

no-dana-only-zuul.patch (9.22 KB)

Austin,

I think the issue here is that in the example you provide, the analyzer is caching out and stops analyzing the path after the first loop (due to us imprecisely handling loops).

If you split test_alloca function into two, the checker will get called on both alloca and __builtin_alloca:
void test_alloca() {
char *foo = alloca(0); // expected-warning{{Call to ‘alloca’ has an allocation size of 0 bytes}}
for(unsigned i = 0; i < 100; i++) {
foo[i] = 0;
}
}

void test_alloca2() {

char *foo2 = __builtin_alloca(0); // expected-warning{{Call to ‘alloca’ has an allocation size of 0 bytes}}
for(unsigned i = 0; i < 100; i++) {
foo2[i] = 0;
}
}

Cheers,
Anna.

Anna, Ted,

Thanks a lot for the help. That indeed seems to have cleared things up.

Attached is an updated patch for adding alloca/valloc checks to
UnixAPIChecker, following the recent getSVal API changes that occurred
yesterday (with tests, of course.) It includes a small refactoring for
the common *alloc functions as well as a few tiny wibbles (adds a note
to CWE/CERT advisory numbers in the bug output, and fixes a couple
80-column-wide violations.)

unixapi-alloca.patch (8.41 KB)

Looks great! Applied in r147931.