Re: Moving smatch to use sparse

Re: Moving smatch to use sparse

[Dan Carpenter]

On 7/14/06, Dan Carpenter <error27@gmail.com> wrote:
> I've been porting smatch to c using sparse as a front end.

I'm going to post the diff's at http://smatch.sourceforge.net/sparse/

I'll send another email once some checks are working...

regards,
dan carpenter

Re: Moving smatch to use sparse

[Dan Carpenter]

Work on smatch is going ahead.  I have one real life check is working
and I've added a patched up the core code quite a bit.

 Makefile               |   15
 check_derefed_params.c |  171 +++++
 check_null_deref.c     |  178 +++++
 smatch.c               |   33 +
 smatch.h               |  138 ++++
 smatch_flow.c          |  462 ++++++++++++++
 smatch_helper.c        |  180 +++++
 smatch_hooks.c         |  125 ++++
 smatch_states.c        |  587 +++++++++++++++++++
 9 files changed, 1888 insertions(+), 1 deletion(-)

check_derefed_params prints out a message every time a function
dereferences a parameter without checking.  check_null_deref.c prints
out a message whenever code calls a funtion with possibly null
parameters.  Afterwards you sort the output for functions that are in
both lists like this:

   grep Und warns.out | cut -d ' ' -f 6,7 | sort | uniq > tmp
   grep unchecked warns.out | cut -d ' ' -f 7,8 | sort | uniq > tmp2
   cat tmp* | sort | uniq -c | sort -n | grep " 2 "

If you run the code with an allno config then you get 9 potential
errors but only one is real...

In drivers/char/tty_ioctl.c line 549, ld could possibly NULL if arg is
TCIFLUSH, TCIOFLUSH or TCOFLUSH which leads to a BUG_ON when
tty_ldisc_deref() is called.

It kind sucks to get so many false positives, but the old version of
smatch would have had more even more because it wasn't as good at
handling compound conditions.

The code is on:  http://smatch.sourceforge.net/sparse/

regards,
dan carpenter

Re: Moving smatch to use sparse

[Sam Ravnborg]

On Thu, Oct 05, 2006 at 01:41:03AM -0700, Dan Carpenter wrote:
> Work on smatch is going ahead.  I have one real life check is working
> and I've added a patched up the core code quite a bit.

For the mindless - can you please repeat what smatch does?

	Sam

Re: Moving smatch to use sparse

[Dan Carpenter]

On 10/5/06, Sam Ravnborg <sam@ravnborg.org> wrote:
> On Thu, Oct 05, 2006 at 01:41:03AM -0700, Dan Carpenter wrote:
> > Work on smatch is going ahead.  I have one real life check is working
> > and I've added a patched up the core code quite a bit.
>
> For the mindless - can you please repeat what smatch does?
>
>         Sam
>

It's a static code checker.  Take a look at check_null_deref.c.

You've got a function called match_assign() that gets called for every
assignment:

       name = get_variable_from_expr(expr->left, &sym);
       name = alloc_string(name);
       if (is_null(expr->right))
               set_state(name, my_id, sym, ISNULL);
       else
               set_state(name, my_id, sym, NONNULL);

Say it encounter the code:  a = foo(), then it's going to set the
state of 'a' to NONNULL;

Then say it encounters a call to tty_ldisc_deref(), it's going to
check the state of 'a' and if it's ISNULL or UNDEFINED it's going to
print a message out.

More often you have something like:
a = NULL;
if (b) {
       a = foo();
}
a->x;  <---Error.  'a' is Undefined.

The idea is that it's easy to write checks once all the state tracking
code is in place.

Use it like this:
make C=1 CHECK=/path/to/smatch > warns.out 2>&1

regards,
dan carpenter

Re: Moving smatch to use sparse

[Jörn Engel]

On Thu, 5 October 2006 02:49:36 -0700, Dan Carpenter wrote:
> On 10/5/06, Sam Ravnborg <sam@ravnborg.org> wrote:
> >
> >For the mindless - can you please repeat what smatch does?
> 
> It's a static code checker.  Take a look at check_null_deref.c.
> 
> You've got a function called match_assign() that gets called for every
> assignment:
> 
>       name = get_variable_from_expr(expr->left, &sym);
>       name = alloc_string(name);
>       if (is_null(expr->right))
>               set_state(name, my_id, sym, ISNULL);
>       else
>               set_state(name, my_id, sym, NONNULL);
> 
> Say it encounter the code:  a = foo(), then it's going to set the
> state of 'a' to NONNULL;
> 
> Then say it encounters a call to tty_ldisc_deref(), it's going to
> check the state of 'a' and if it's ISNULL or UNDEFINED it's going to
> print a message out.
> 
> More often you have something like:
> a = NULL;
> if (b) {
>       a = foo();
> }
> a->x;  <---Error.  'a' is Undefined.
> 
> The idea is that it's easy to write checks once all the state tracking
> code is in place.
> 
> Use it like this:
> make C=1 CHECK=/path/to/smatch > warns.out 2>&1

One advantage over gcc or plain sparse is that code checking can be
done in two passes.  Pass one collects all sorts of information for
every compilation unit.  Pass two can then combine the information for
all compilation units and do global checking of some sort.

For example, the currently debated "may be used uninitialized" warning
in gcc is simply not able to detect something like:

foo.c:
	int foo;
	do_initialize(&foo);
	do_something(foo);
bar.c:
void do_initialize(int *bar)
{
	*bar = 0;
}

The code is 100% correct, but gcc only looks at foo.c and spits out a
warning.  Smatch can do better than that - if someone writes a
checker.

Jörn

-- 
But this is not to say that the main benefit of Linux and other GPL
software is lower-cost. Control is the main benefit--cost is secondary.
-- Bruce Perens

Re: Moving smatch to use sparse

[Dan Carpenter]

On 10/5/06, Jörn Engel <joern@wohnheim.fh-wedel.de> wrote:
>
> One advantage over gcc or plain sparse is that code checking can be
> done in two passes.  Pass one collects all sorts of information for
> every compilation unit.  Pass two can then combine the information for
> all compilation units and do global checking of some sort.
>
> For example, the currently debated "may be used uninitialized" warning
> in gcc is simply not able to detect something like:
>
> foo.c:
>         int foo;
>         do_initialize(&foo);
>         do_something(foo);
> bar.c:
> void do_initialize(int *bar)
> {
>         *bar = 0;
> }
>
> The code is 100% correct, but gcc only looks at foo.c and spits out a
> warning.  Smatch can do better than that - if someone writes a
> checker.
>
> Jörn
>

Actually, I think gcc handles that specific example correctly...  If
do_initialize() is in the same file it looks to see if it actually
initializes it or not.  If it's in a seperate file then it assumes
that it initializes it and doesn't print a warning.

I'm using gcc 4.0.3.

regards,
dan carpenter

Re: Moving smatch to use sparse

[Michael Stefaniuc]

Hello Dan,

Dan Carpenter wrote:
> Work on smatch is going ahead.  I have one real life check is working
> and I've added a patched up the core code quite a bit.
great work! What about the old smatch.pm and perl scripts? Will i be
still able to use those or would i have to port them over? I'm still
using the old smatch on checking Wine.

bye
	michael

> 
> Makefile               |   15
> check_derefed_params.c |  171 +++++
> check_null_deref.c     |  178 +++++
> smatch.c               |   33 +
> smatch.h               |  138 ++++
> smatch_flow.c          |  462 ++++++++++++++
> smatch_helper.c        |  180 +++++
> smatch_hooks.c         |  125 ++++
> smatch_states.c        |  587 +++++++++++++++++++
> 9 files changed, 1888 insertions(+), 1 deletion(-)
> 
> check_derefed_params prints out a message every time a function
> dereferences a parameter without checking.  check_null_deref.c prints
> out a message whenever code calls a funtion with possibly null
> parameters.  Afterwards you sort the output for functions that are in
> both lists like this:
> 
>   grep Und warns.out | cut -d ' ' -f 6,7 | sort | uniq > tmp
>   grep unchecked warns.out | cut -d ' ' -f 7,8 | sort | uniq > tmp2
>   cat tmp* | sort | uniq -c | sort -n | grep " 2 "
> 
> If you run the code with an allno config then you get 9 potential
> errors but only one is real...
> 
> In drivers/char/tty_ioctl.c line 549, ld could possibly NULL if arg is
> TCIFLUSH, TCIOFLUSH or TCOFLUSH which leads to a BUG_ON when
> tty_ldisc_deref() is called.
> 
> It kind sucks to get so many false positives, but the old version of
> smatch would have had more even more because it wasn't as good at
> handling compound conditions.
> 
> The code is on:  http://smatch.sourceforge.net/sparse/


-- 
Michael Stefaniuc               Tel.: +49-711-96437-199
Sr. Network Engineer            Fax.: +49-711-96437-111
Red Hat GmbH                    Email: mstefani@redhat.com
Hauptstaetterstr. 58            http://www.redhat.de/
D-70178 Stuttgart

Re: Moving smatch to use sparse

[Dan Carpenter]

On 10/5/06, Michael Stefaniuc <mstefani@redhat.com> wrote:
> Hello Dan,
>
> Dan Carpenter wrote:
> > Work on smatch is going ahead.  I have one real life check is working
> > and I've added a patched up the core code quite a bit.
> great work! What about the old smatch.pm and perl scripts? Will i be
> still able to use those or would i have to port them over? I'm still
> using the old smatch on checking Wine.
>
> bye
>         michael
>

They'll have to be ported I'm afraid.

Rewrites are a pain, but it's worth it because now it's easier to
install, it's easier to use, and it runs a bajillion times faster.
Using sparse also buys us a bunch of features for free, for example if
you have 'i' defined in two different scopes with sparse handles that.
 Another example is compound conditions.  The old code was confused by
stuff like:
if (a && a->foo() || a && a->bar())
there wasn't a good way to deal with that with the old way.

Which checks do you use most?  I'll port those first...

regards,
dan carpenter

Re: Moving smatch to use sparse

[Michael Stefaniuc]

Dan Carpenter wrote:
> On 10/5/06, Michael Stefaniuc <mstefani@redhat.com> wrote:
>> Dan Carpenter wrote:
>> > Work on smatch is going ahead.  I have one real life check is working
>> > and I've added a patched up the core code quite a bit.
>> great work! What about the old smatch.pm and perl scripts? Will i be
>> still able to use those or would i have to port them over? I'm still
>> using the old smatch on checking Wine.
> 
> They'll have to be ported I'm afraid.
That's not realy a problem especialy as i can keep using the old smatch
for a while.

> Rewrites are a pain, but it's worth it because now it's easier to
> install, it's easier to use, and it runs a bajillion times faster.
I'm more concerned about how easy it is to write new "scripts" or modify
existing ones. For Wine I use only unreached-code.pl as is. Due to the
Win32 API i had to modify unfree.pl quite a bit.

> Using sparse also buys us a bunch of features for free, for example if
> you have 'i' defined in two different scopes with sparse handles that.
> Another example is compound conditions.  The old code was confused by
> stuff like:
> if (a && a->foo() || a && a->bar())
> there wasn't a good way to deal with that with the old way.
> 
> Which checks do you use most?  I'll port those first...
The scripts used regularly for Wine are on
http://people.redhat.com/mstefani/wine/smatch/scripts.html. Except that
i use only unreached-code.pl from the original smatch scripts.
Though not all scripts are that usefull; i probably could throw out
immediately while_for_check.pl and crosscalls_WtoA.pl. Most successfull
script is redundant_null_check.pl (finds "if (bla) free(bla);") as i had
only 2 false positives until now. unfree-wine.pl is the adaptation+bug
fixes of the original unfree.pl (usefull but lots of false positives).
The other usefull script is wine_locks.pl that found quite a few missing
unlocks on error paths. And i have some other ideas about a couple of
usefull smatch scripts for Wine but lack the time to implement them.

So most usefull would be a short documentation how to port things. Maybe
a short mapping between the most importand smatch.pm functions and their
 C counter part would be enough for the start. I looked at the smatch
sparse diff and it didn't look that complicated to use. I have anyway a
longish train ride next week so i will give it a try; maybe with an easy
and dumb version of redundant_null_check.pl

bye
	michael
-- 
Michael Stefaniuc               Tel.: +49-711-96437-199
Sr. Network Engineer            Fax.: +49-711-96437-111
Red Hat GmbH                    Email: mstefani@redhat.com
Hauptstaetterstr. 58            http://www.redhat.de/
D-70178 Stuttgart

Re: Moving smatch to use sparse

[Dan Carpenter]

Sparse reads the source and creates a parse tree.  At the base, are
function symbols, the function has a bunch statements and the
statements have a bunch of expressions which branch out into even more
expressions.  If you have data that's a symbol.

struct expression is defined in expression.h
struct symbol is defined in symbol.h
struct statement is in parse.h

The important functions are:
set_state(name, my_id, sym, ISNULL);
get_state(deref, my_id, sym)
set_true_false_states(left, my_id, sym_left, ISNULL, NONNULL);
add_hook(&match_assign, ASSIGNMENT_HOOK);
void register_your_check(int id)
left = get_variable_from_expr(expr->left, &sym_left);
left = alloc_string(left);

my_id is a different int for every check script.
sym is a symbol * to the sparse symbol.
The condition hook feeds you one condition at a time.
add_hook() sets up a call back that will be called for every
assignment in this case.
add the register_your_check() to smatch.c.
get_variable_from_expr() is a bit buggy still but it's supposed to
give a string representation of an expression and it also gives you a
symbol pointer.  If you want to keep the string instead of just
printing it out or using it for get_state() then you have to call
alloc_string().

I haven't added setting up custom merge_rules yet.  Will do.

Internally smatch_states are a struct.  I'm going to add some more
fields to that so it might be useful to have a get_state_struct()
function...

smatch_flow.c interprets that sparse tree.  If you want to add another
hook that's the place to do it.

That's pretty much it.

regards,
dan carpenter