Frr: clang Static Analysis always warns about RB trees

Created on 25 Apr 2017 · 7Comments · Source: FRRouting/frr

When we run clang's SA over the source base, we get a bunch of warnings about the RB tree implementation:

25-Apr-2017 07:02:40 25-Apr-2017 07:02:40 25-Apr-2017 07:02:40 25-Apr-2017 07:02:40 25-Apr-2017 07:02:40 25-Apr-2017 07:02:40 25-Apr-2017 07:02:40 25-Apr-2017 07:02:40 25-Apr-2017 07:02:40 25-Apr-2017 07:02:40 25-Apr-2017 07:02:40 25-Apr-2017 07:02:40 25-Apr-2017 07:02:40 25-Apr-2017 07:02:40 25-Apr-2017 07:02:40 25-Apr-2017 07:02:40 25-Apr-2017 07:02:40 25-Apr-2017 07:02:40 25-Apr-2017 07:02:40 25-Apr-2017 07:02:40 25-Apr-2017 07:02:40 25-Apr-2017 07:02:40 25-Apr-2017 07:02:40 25-Apr-2017 07:02:40 25-Apr-2017 07:02:40 25-Apr-2017 07:02:40 25-Apr-2017 07:02:40 25-Apr-2017 07:02:40 25-Apr-2017 07:02:40 25-Apr-2017 07:02:40 25-Apr-2017 07:02:40 25-Apr-2017 07:02:40 25-Apr-2017 07:02:40 25-Apr-2017 07:02:40 25-Apr-2017 07:02:40 25-Apr-2017 07:02:40 25-Apr-2017 07:02:40 25-Apr-2017 07:02:40 25-Apr-2017 07:02:40 25-Apr-2017 07:02:40 25-Apr-2017 07:02:40 25-Apr-2017 07:02:40 25-Apr-2017 07:02:40 25-Apr-2017 07:02:40 25-Apr-2017 07:02:40 25-Apr-2017 07:02:40 25-Apr-2017 07:02:40 25-Apr-2017 07:02:40 25-Apr-2017 07:02:40 25-Apr-2017 07:02:40 25-Apr-2017 07:02:40 25-Apr-2017 07:02:40 if ((RB_LEFT(tmp, field) == NULL || \
^~~~~
../lib/openbsd-tree.h:313:30: note: expanded from macro 'RB_LEFT'
#define RB_LEFT(elm, field) (elm)->field.rbe_left
^~~~~
neighbor.c:47:1: warning: Dereference of null pointer
RB_GENERATE(nbr_pid_head, nbr, pid_tree, nbr_pid_compare)
^~~~~~~~~~~~~
../lib/openbsd-tree.h:396:2: note: expanded from macro 'RB_GENERATE'
RB_GENERATE_INTERNAL(name, type, field, cmp,)
^~~~~~~~~~~
../lib/openbsd-tree.h:489:9: note: expanded from macro 'RB_GENERATE_INTERNAL'
if ((RB_LEFT(tmp, field) == NULL || \
^~~~~
../lib/openbsd-tree.h:313:30: note: expanded from macro 'RB_LEFT'
#define RB_LEFT(elm, field) (elm)->field.rbe_left
^~~~~
neighbor.c:48:1: warning: Dereference of null pointer
RB_GENERATE(nbrp_head, nbr_params, entry, nbr_params_compare)
^~~~~~~~~~~~~
../lib/openbsd-tree.h:396:2: note: expanded from macro 'RB_GENERATE'
RB_GENERATE_INTERNAL(name, type, field, cmp,)
^~~~~~~~~~~
../lib/openbsd-tree.h:407:17: note: expanded from macro 'RB_GENERATE_INTERNAL'
if (parent == RB_LEFT(gparent, field)) { \
^~~~~~~
../lib/openbsd-tree.h:313:30: note: expanded from macro 'RB_LEFT'
#define RB_LEFT(elm, field) (elm)->field.rbe_left
^~~~~
neighbor.c:48:1: warning: Dereference of null pointer
RB_GENERATE(nbrp_head, nbr_params, entry, nbr_params_compare)
^~~~~~~~~~~~~
../lib/openbsd-tree.h:396:2: note: expanded from macro 'RB_GENERATE'
RB_GENERATE_INTERNAL(name, type, field, cmp,)
^~~~~~~~~~~
../lib/openbsd-tree.h:457:9: note: expanded from macro 'RB_GENERATE_INTERNAL'
if ((RB_LEFT(tmp, field) == NULL || \
^~~~~
../lib/openbsd-tree.h:313:30: note: expanded from macro 'RB_LEFT'
#define RB_LEFT(elm, field) (elm)->field.rbe_left
^~~~~
neighbor.c:48:1: warning: Dereference of null pointer
RB_GENERATE(nbrp_head, nbr_params, entry, nbr_params_compare)
^~~~~~~~~~~~~
../lib/openbsd-tree.h:396:2: note: expanded from macro 'RB_GENERATE'
RB_GENERATE_INTERNAL(name, type, field, cmp,)
^~~~~~~~~~~
../lib/openbsd-tree.h:489:9: note: expanded from macro 'RB_GENERATE_INTERNAL'
if ((RB_LEFT(tmp, field) == NULL || \
^~~~~
../lib/openbsd-tree.h:313:30: note: expanded from macro 'RB_LEFT'
#define RB_LEFT(elm, field) (elm)->field.rbe_left

We need to have someone investigate and fix this issue.

bug question

Source

donaldsharp

All 7 comments

I use the scan-build make to scan the branch "stable-2.0" and get the whole report

Most of those warning are caused by accessing NULL pointer in some case.
Maybe I can send a PR after I have solved all of them.

hwchiu on 28 Apr 2017

Every pull request and every push to the repo creates a full clang report.
As an example, see https://ci1.netdef.org/browse/FRR-FRR4/latestSuccessful/artifact/shared/static_analysis/index.html for the report on the last successful CI build in 3.0 branch.

But maybe I need to make this more visible...

mwinter-osr on 28 Apr 2017

👍1

Thanks your sharing, I will use those reports to check all warnings and try to fix.

hwchiu on 28 Apr 2017

Hi @donaldsharp .
I thinks those warning all are caused by calling followings MACRO without checking it's first parameter

#define RB_LEFT(elm, field)     (elm)->field.rbe_left
#define RB_RIGHT(elm, field)        (elm)->field.rbe_right
#define RB_PARENT(elm, field)       (elm)->field.rbe_parent
#define RB_COLOR(elm, field)        (elm)->field.rbe_color
#define RB_ROOT(head)           (head)->rbh_root
...
(tmp) = RB_LEFT(elm, field);
if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) {  /* occur here */

We can check its first parameter before calling those macro or do you have any ideas?

hwchiu on 28 Apr 2017

Unfortunately I think the best thing we can do is ignore these warnings.

The biggest problem seems to be the RB_GENERATE macro, which is expanded by the preprocessor into a lengthy piece of code (example: https://hastebin.com/efasuyoxon.c). clang complains about a "Dereference of null pointer" that's very hard to track down. Maybe we can add a few NULL checks here and there to get rid of the warnings, but I think this is unnecessary. This red-black tree implementation we're using was imported from OpenBSD, where it's used quite extensively by the kernel and several daemons. It's really a mature implementation that is proven safe and reliable. IMO adding some NULL checks will only hinder its performance for no benefit other than silencing these harmless warnings.

Also, clang's static analyzer throws a lot of warnings when any of these macros is used: RB_ROOT, LIST_FIRST and TAILQ_FIRST. These macros are generally used when you want to remove all elements of a tree or list. Example:

while ((elem = TAILQ_FIRST(list)) != NULL) {
        TAILQ_REMOVE(list, elem, entry);
        free(elem);
}

clang in this case is incapable to realize that TAILQ_FIRST() returns different elements every time it's called, so we get a lot of "Use-after-free" warnings. One solution to this problem is stop using these macros and convert the code to use *_FOREACH_SAFE loops instead. But does that make any sense? I'd prefer to wait until clang's code is improved rather to fix what's not broken on our side.

rwestphal on 2 May 2017

👍1

Should we tell clang to ignore these issues?

donaldsharp on 2 May 2017

Suggestion: use the new RBT_* data structure family to avoid generating the amount of code that these macros do and probably fix this warnings by using functions that can do compiler type checks.

The new macros can be found here:
http://cvsweb.openbsd.org/cgi-bin/cvsweb/src/sys/sys/tree.h?rev=1.27&content-type=text/x-cvsweb-markup

The function implementations can be found here:
http://cvsweb.openbsd.org/cgi-bin/cvsweb/src/sys/kern/subr_tree.c?rev=1.9&content-type=text/x-cvsweb-markup