Possible false NULL dereference warning in doubly-linked list

[llvmbot]

Bugzilla Link	16782
Resolution	INVALID
Resolved on	Oct 24, 2013 22:41
Version	trunk
OS	MacOS X
Attachments	C++ source and header, preprocessed source (zipped)
Reporter	LLVM Bugzilla Contributor
CC	@AnnaZaks

Extended Description

Overview:

The static analyzer says that in traversing a doubly linked list, a NULL pointer can be dereferenced, but I can't see how that can happen.

Steps to reproduce:

Analyze the attached source, like:

clang -DDEBUG=1 --analyze micropather.cpp

Actual results:

micropather.h:206:45: warning: Access to field 'next' results in a dereference of a null pointer (loaded from variable 'it'

Expected results:

No warning.

Build date:

clang version 3.4 (trunk 187678) Target: x86_64-apple-darwin11.4.2 Thread model: posix

Additional information:

The code is from http://sourceforge.net/projects/micropather/. I don't claim to be intimately familiar with it. But it appears to me that the next and prev pointers only become NULL when a node is removed from the doubly linked list, so traversing the list should not encounter a NULL.

[0f73b9cf-134f-41af-a8b1-14d9f305ee95]

The warning trace spans multiple functions. It starts at micropather.cpp:984:2 and ends in ./micropather.h:249:45. (The format of the text output is the final warning line followed by the trace.) So Pop calls checkList, which traverses the list. (In my example, trigger is similar to your Pop.)

The analyzer assumes that all lists are possible. So if there is a list on which we could warn, we do. (This cover all cases/cover all paths behavior is what the analyzer is checking.)

[llvmbot]

Anna, I don't understand why you say this is "a warning in pop, not in a traversal", given that the immediate line being warned about is

for( PathNode* it = next; it != this; it=it->next )

which is traversal.

I wasn't convinced by your small example, so I modified it:

include

struct list { list next; list prev;

void unlink() {
    next->prev = prev;
    prev->next = next;
    next = prev = 0;
}

void check() {
    for (list* it = next; it != this; it = it->next ) {}
}

};

void trigger(list sentinel) { assert( sentinel->next != sentinel ); assert( sentinel->next != NULL ); list pNode = sentinel->next; pNode->unlink(); sentinel->check(); }

I still get the warning, and still don't understand why. Of course you could make a malformed list that has a NULL pointer in it, but you don't have to.

[0f73b9cf-134f-41af-a8b1-14d9f305ee95]

This is the same as what I am seeing. I thought that you have a different output because you mentioned that the issue happens on a list traversal, however, here we see that the error is reported on a pop: "PathNode* node = open.Pop(); // smallest dist"

See the reduced test case that I've posted.

[llvmbot]

The result of

$clang -DDEBUG=1 --analyze micropather.cpp -Xclang -analyzer-output=text

is:

In file included from micropather.cpp:44: ./micropather.h:249:45: warning: Access to field 'next' results in a dereference of a null pointer (loaded from variable 'it') for( PathNode it = next; it != this; it=it->next ) { ^~~~ micropather.cpp:984:2: note: Loop condition is true. Entering loop body while ( !open.Empty() ) ^ micropather.cpp:986:20: note: Calling 'OpenQueue::Pop' PathNode node = open.Pop(); // smallest dist ^ micropather.cpp:114:2: note: Calling 'PathNode::Unlink' pNode->Unlink(); ^ ./micropather.h:237:4: note: Null pointer value stored to field 'next' next = prev = 0; ^ micropather.cpp:114:2: note: Returning from 'PathNode::Unlink' pNode->Unlink(); ^ micropather.cpp:116:2: note: Calling 'PathNode::CheckList' sentinel->CheckList(); ^ ./micropather.h:249:4: note: Loop condition is true. Entering loop body for( PathNode it = next; it != this; it=it->next ) { ^ ./micropather.h:249:42: note: Null pointer value stored to 'it' for( PathNode it = next; it != this; it=it->next ) { ^ ./micropather.h:249:4: note: Loop condition is true. Entering loop body for( PathNode it = next; it != this; it=it->next ) { ^ ./micropather.h:249:45: note: Access to field 'next' results in a dereference of a null pointer (loaded from variable 'it') for( PathNode it = next; it != this; it=it->next ) { ^ 1 warning generated.

If I run

$clang --analyze preprocessed.cpp -Xclang -analyzer-output=text

the output looks the same except for line numbers and spaces.

[0f73b9cf-134f-41af-a8b1-14d9f305ee95]

It's possible that this is a false positive. However, running clang on the preprocessed file triggers a warning in pop, not in a traversal. $clang --analyze ~/Downloads/preprocessed.cpp -Xclang -analyzer-output=text

Also, looks like the warning could be legitimate; it's similar to the small example below. struct list { list next; list (list n) : next(n) {} void unlink() { next = 0; } void check() { for (list it = next; it != this; it = it->next ) {} } }; void trigger(list sentinel) { list pNode = sentinel->next; pNode->unlink(); sentinel->check();
} /int main() { list l = list(list(list(0))); trigger(&l); }*/

From the report below, it is unclear which top-level function has triggered the warning. Could you send the output of $clang -DDEBUG=1 --analyze micropather.cpp -Xclang -analyzer-output=text

This will show the full path and why the analyzer thinks there is a problem.

[llvmbot]

assigned to @tkremenek