Static analyzer run

[Lorenz Minder]

Hi,

I've run PARI through a static source code analyzer to see if it finds
any bugs (and to see if the tool is worth anything).

It found a couple of minor things, such as duplicate assignments.  I
think the benefit of fixing those is mostly code readability.  Those
are in the attached minor_bugs.patch.

Then it uncovered a few real bugs. I (hope I) fixed those in
sa_bugfixes.patch.

All tests still run fine with those patches attached.

And then it gave a couple of messages I did not investigate closer,
but that look very suspicious.  I think it would probably be a
worthwhile time investment if some PARI guru looked into those.
See below.

Best,
--Lorenz

../src/basemath/base2.c:1637:16: warning: Dereference of null pointer
      S->phi = typ(opa) == t_INT? RgX_Rg_add_shallow(S->phi, opa)
               ^
../src/basemath/base2.c:2383:3: warning: Branch condition evaluates to an uninitialized value.
  if (den)
  ^   ~~~
../src/basemath/base3.c:1553:7: warning: Value stored to 'ex' is never read
      ex = EX;
      ^    ~~
../src/basemath/base3.c:1563:16: warning: Value stored to 'ex' is never read
        if (v) ex = mulii(ex, powiu(p, v));
               ^    ~~~~~~~~~~~~~~~~~~~~~~
../src/basemath/bibli1.c:2129:14: warning: Value stored to 'j' is never read
        for (j = 0; i <= s; i++)
             ^   ~
../src/basemath/polarit3.c:2257:36: warning: Dereference of null pointer
  if (av2) { avma = av2; *lambda = next_lambda(*lambda); }
                                   ^
../src/basemath/rootpol.c:2255:27: warning: Value stored to 'av2' is never read
      xd = RgX_deriv(xc); av2 = avma;
                          ^     ~~~~
../src/language/eval.c:625:11: warning: Dereference of null pointer
      if (typ(base)!=t_VEC) sbase = GSTR(base);
          ^
../src/modules/QX_factor.c:1147:63: warning: Pass-by-value argument in function call is undefined.
    if (DEBUGLEVEL>5) msgtimer("gcd mod %lu (bound 2^%ld)", p,expi(q));
                                                              ^    ~
../src/modules/QX_factor.c:1154:10: warning: Pass-by-value argument in function call is undefined.
    qp = muliu(q,p);
         ^     ~

--
GRATIS für alle GMX-Mitglieder: Die maxdome Movie-FLAT!
Jetzt freischalten unter http://portal.gmx.net/de/go/maxdome01

[Bill Allombert-3]

On Mon, Sep 14, 2009 at 10:00:32AM +0200, Lorenz Minder wrote:
> Hi,
>
> Then it uncovered a few real bugs. I (hope I) fixed those in
> sa_bugfixes.patch.

I applied this one (revision 11911).

I need more checks for the other issues.
(For example
-  prec = polred_init(T, &F, &d);
+  polred_init(T, &F, &d);

The problem is that some other analyzer report that polred_init() return value
is ignored, so we have to write
(void)polred_init(T, &F, &d);
or decide it is not improper to call the return value 'prec', even if we
do not use it.

Thanks a lot for all this work!

Cheers,
Bill.

[Bill Allombert-3]

On Mon, Sep 14, 2009 at 10:00:32AM +0200, Lorenz Minder wrote:
> Hi,
>
> I've run PARI through a static source code analyzer to see if it finds
> any bugs (and to see if the tool is worth anything).
>
> It found a couple of minor things, such as duplicate assignments.  I
> think the benefit of fixing those is mostly code readability.  Those
> are in the attached minor_bugs.patch.

I have commited your patch with very small changes.

> Then it uncovered a few real bugs. I (hope I) fixed those in
> sa_bugfixes.patch.

Also done.

> All tests still run fine with those patches attached.
>
> And then it gave a couple of messages I did not investigate closer,
> but that look very suspicious.  I think it would probably be a
> worthwhile time investment if some PARI guru looked into those.

Can you tell the analyzer that pari_err does not return ?
This is a large source of false positive with gcc.
 
> ../src/basemath/base2.c:1637:16: warning: Dereference of null pointer
>       S->phi = typ(opa) == t_INT? RgX_Rg_add_shallow(S->phi, opa)
>                ^

I do not understand why it work, but clearly the statement
opa = NULL;
is useless. Somehow the code assume that getprime will work the first
time.

> ../src/basemath/base2.c:2383:3: warning: Branch condition evaluates to an uninitialized value.
>   if (den)
>   ^   ~~~

Probably the analyzer does not know that pari_err(typeer,"Rg_to_ff");
will not return.

> ../src/basemath/base3.c:1553:7: warning: Value stored to 'ex' is never read
>       ex = EX;
>       ^    ~~
and
> ../src/basemath/base3.c:1563:16: warning: Value stored to 'ex' is never read
>         if (v) ex = mulii(ex, powiu(p, v));
>                ^    ~~~~~~~~~~~~~~~~~~~~~~

Looking at the code, one wonder why this variable ex exists at all.
Maybe the intent was 'EX = ex' instead, but that does not work.

> ../src/basemath/bibli1.c:2129:14: warning: Value stored to 'j' is never read
>         for (j = 0; i <= s; i++)
>              ^   ~

Of course this is wrong, but what is the fix ???

> ../src/basemath/polarit3.c:2257:36: warning: Dereference of null pointer
>   if (av2) { avma = av2; *lambda = next_lambda(*lambda); }
>                                    ^



> ../src/basemath/rootpol.c:2255:27: warning: Value stored to 'av2' is never read
>       xd = RgX_deriv(xc); av2 = avma;
>                           ^     ~~~~

It probably should be avma = av2 instead.

> ../src/language/eval.c:625:11: warning: Dereference of null pointer
>       if (typ(base)!=t_VEC) sbase = GSTR(base);
>           ^

This a false positive.

> ../src/modules/QX_factor.c:1147:63: warning: Pass-by-value argument in function call is undefined.
>     if (DEBUGLEVEL>5) msgtimer("gcd mod %lu (bound 2^%ld)", p,expi(q));
>                                                               ^    ~
and
> ../src/modules/QX_factor.c:1154:10: warning: Pass-by-value argument in function call is undefined.
>     qp = muliu(q,p);
>          ^     ~

This looks like a false positive.

Cheers,
Bill.

[Lorenz Minder]

Hi,

BA:
> On Mon, Sep 14, 2009 at 10:00:32AM +0200, Lorenz Minder wrote:
> > It found a couple of minor things, such as duplicate assignments.  I
> > think the benefit of fixing those is mostly code readability.  Those
> > are in the attached minor_bugs.patch.
>
> I have committed your patch with very small changes.

Thanks for looking into those.  FWIW, I agree that possibly not all of
them were desirable.  I'd in fact already weeded out quite a few changes
which I thought didn't improve matters before sending in, but there
may have been some more.

> > Then it uncovered a few real bugs. I (hope I) fixed those in
> > sa_bugfixes.patch.
>
> Also done.

Great.

> Can you tell the analyzer that pari_err does not return ?
> This is a large source of false positive with gcc.

Hmm, isn't it gcc-clean at the moment?   In any case, maybe we should
declare pari_err() with __attribute__((noreturn)).  That would
presumably help both gcc and clang (whose analyzer I used to find these
problems).

I've had no time yet to look into how to make such a change in
a portable manner.

FWIW, I've indeed had a large number of false positives with clang due
to this.

> > ../src/basemath/base2.c:1637:16: warning: Dereference of null pointer
> >       S->phi = typ(opa) == t_INT? RgX_Rg_add_shallow(S->phi, opa)
> >                ^
>
> I do not understand why it work, but clearly the statement
> opa = NULL;
> is useless. Somehow the code assume that getprime will work the first
> time.
[...]

Ok, thanks for those assessments.  I hope I'll get around looking at
some of the ones that probably aren't false at some point. (Most of
them are in code I don't understand and therefore won't touch, though.)

BTW, I accidentally stumbled over a problem in the SEA module today.
Can you check the attached patch?

Best,
--Lorenz
--
GRATIS für alle GMX-Mitglieder: Die maxdome Movie-FLAT!
Jetzt freischalten unter http://portal.gmx.net/de/go/maxdome01

[Bill Allombert-3]

On Wed, Sep 16, 2009 at 06:00:49AM +0200, Lorenz Minder wrote:
> Hi,
>
> > Can you tell the analyzer that pari_err does not return ?
> > This is a large source of false positive with gcc.
>
> Hmm, isn't it gcc-clean at the moment?   In any case, maybe we should

It is, but only due to the addition of lot of useless return NULL;

> declare pari_err() with __attribute__((noreturn)).  That would
> presumably help both gcc and clang (whose analyzer I used to find these
> problems).
>
> I've had no time yet to look into how to make such a change in
> a portable manner.

Yes... Karim objection that this would non-gcc compilers to output contractory
warning from gcc compilers, and we could not shut them both down:

An example:

GEN foo()
{
  ...
  pari_err(talker,"...");
  return NULL;
}

With __attribute__((noreturn)):
  Warning statement not reached:
  return NULL;
Without __attribute__((noreturn)) and without "return NULL"
  Warning: function foo does not return.

> Ok, thanks for those assessments.  I hope I'll get around looking at
> some of the ones that probably aren't false at some point. (Most of
> them are in code I don't understand and therefore won't touch, though.)

Unfortunately I am sometimes in the same situation as you see...

> BTW, I accidentally stumbled over a problem in the SEA module today.
> Can you check the attached patch?

Commited in revision 11921. I find very unfortunate that gerepileall
take an explicit argument number. I was hopping for some preprocessing
trickery to avoid that, but I found none. We should probably change it
to a NULL-terminated list instead, though this would cause other problems
with argument accidentally equal to NULL.

Cheers,
Bill.

[Karim Belabas-4]

* Bill Allombert [2009-09-15 22:41]:
> > ../src/basemath/base2.c:1637:16: warning: Dereference of null pointer
> >       S->phi = typ(opa) == t_INT? RgX_Rg_add_shallow(S->phi, opa)
> >                ^
>
> I do not understand why it work, but clearly the statement
> opa = NULL;
> is useless. Somehow the code assume that getprime will work the first
> time.

This is correct. It cannot return NULL when oE = 0 (and the last
argument is 0). Thus it *will* work the first time it is called.

The opa = NULL was necessary to silence an "uninitialized variable"
Warning...

Added a comment.

> > ../src/basemath/base3.c:1553:7: warning: Value stored to 'ex' is never read
> >       ex = EX;
> >       ^    ~~
> and
> > ../src/basemath/base3.c:1563:16: warning: Value stored to 'ex' is never read
> >         if (v) ex = mulii(ex, powiu(p, v));
> >                ^    ~~~~~~~~~~~~~~~~~~~~~~
>
> Looking at the code, one wonder why this variable ex exists at all.
> Maybe the intent was 'EX = ex' instead, but that does not work.

The intent was to call famat_makecoprime with last argument 'ex', not 'EX'
( both are correct, the former divides the latter, making the call more
efficient ).

The whole "idealstar" structure (and all related code) is ridiculous in
any case : it stores mostly useless data and recomputes all the time the
actually needed quantities (such as this 'ex').  

Background : a few remaining code pieces still (wrongly) insist on
working with global algebraic integers instead of working locally modulo
suitable powers of primes; the idealstar structure was created when all
the code was entirely global. Have been working on cleaning it once and for
all for some time now. Unfortunately, it in turn affects the bnr
structure, and changes all results in most regression tests, some of
them in annoying ways (much slower); never got to actually commit my
changes ...

> > ../src/basemath/bibli1.c:2129:14: warning: Value stored to 'j' is never read
> >         for (j = 0; i <= s; i++)
> >              ^   ~
>
> Of course this is wrong, but what is the fix ???

No initialization needed:

         for (; i <= s; i++)

> > ../src/basemath/polarit3.c:2257:36: warning: Dereference of null pointer
> >   if (av2) { avma = av2; *lambda = next_lambda(*lambda); }
> >                                    ^

This is fine, we can never have lambda = NULL when av2 != 0. I made the
code less cryptic.

> > ../src/basemath/rootpol.c:2255:27: warning: Value stored to 'av2' is never read
> >       xd = RgX_deriv(xc); av2 = avma;
> >                           ^     ~~~~
>
> It probably should be avma = av2 instead.

It should be deleted.

Thanks for looking into this !

Cheers,

    K.B.
--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux1.fr/~belabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux1.fr/  [PARI/GP]
`

[Karim Belabas-4]

* Lorenz Minder [2009-09-14 10:07]:
> I've run PARI through a static source code analyzer to see if it finds
> any bugs (and to see if the tool is worth anything).
[...]
> * Flx_resultant():  variables still in use were garbage collected.
>   (In the old code, try replacing "if(++cnt == 100)" by "if(++cnt == 1)"
>   to see those problems.)

diff --git a/src/basemath/Flx.c b/src/basemath/Flx.c
--- a/src/basemath/Flx.c
+++ b/src/basemath/Flx.c
@@ -1280,7 +1280,7 @@

     if (both_odd(da,db)) res = p - res;
     if (lb != 1) res = Fl_mul(res, Fl_powu(lb, da - dc, p), p);
-    if (++cnt == 100) { cnt = 0; c = gerepileuptoleaf(av, c); }
+    if (++cnt == 100) { cnt = 0; gerepileall(av, 2, &a, &b); }
     da = db; /* = degpol(a) */
     db = dc; /* = degpol(b) */
   }
diff --git a/src/basemath/base1.c b/src/basemath/

A note on this one: the old code was actually "not completely incorrect"
since a,b are non-recursive objects of bounded size, a priori less
than 100 times the stack space used up in a the 2 loop iterations during
which they must survive. A simple avma = av would have been fine (and
better).

This technique of using for a very limited time an object that has just
been reclaimed by the garbage collector is not infrequent in our code,
and mandatorily flagged with a /* HACK */ comment. It saves a little
time by avoiding an actual gerepile.

The code becomes completely wrong if you replace 100 by a much smaller
number of course. Or if the Flx_rem implementation is replaced by
something needing much more stack space (Newton + FTT, say). So I agree
that in this case, the code should be fixed.


The true culprit is of course the stack/gerepile model here. We'd much rather
have the successive Flx_rem() store their result in pre-allocated storage
(whose size is easy to estimate; only the 2 last results need to be kept),
instead of endlessly adding to the stack then reclaiming garbage in
either hackish or inefficient way.

It's actually very simple to implement such an Flx_remz(a, b, z)
function (stores Flx_rem(a, b) in pre-allocated z), because in the case
where this would be difficult (Newton), the current code already calls a
gerepile, which could be replaced by a copy at not coѕe. >> TODO :-).

Cheers,

    K.B.
--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux1.fr/~belabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux1.fr/  [PARI/GP]
`

[Karim Belabas-4]

* Bill Allombert [2009-09-16 12:46]:
> Commited in revision 11921. I find very unfortunate that gerepileall
> take an explicit argument number. I was hopping for some preprocessing
> trickery to avoid that, but I found none.

Neither did I when I orignally implemented it.

> We should probably change it to a NULL-terminated list instead, though
> this would cause other problems with argument accidentally equal to
> NULL.

Valid arguments cannot be equal to NULL unless we actually want to
terminate the list at this point and ignore all following arguments.

This wouldn't be nice for another reaѕon: the gerepileall() function
should be as fast as possible, and it needs to know its number of
arguments before starting to actually process them. I don't want to
traverse the arg list twice to count them first...

    K.B.
--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux1.fr/~belabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux1.fr/  [PARI/GP]
`

[Lorenz Minder]

Hi,

KB:
> This technique of using for a very limited time an object that has just
> been reclaimed by the garbage collector is not infrequent in our code,
> and mandatorily flagged with a /* HACK */ comment. It saves a little
> time by avoiding an actual gerepile.

Thanks, that's very instructive for newcomers to the PARI source code.
The idea that this way to use the stack could be intentional hadn't
occurred to me before.

Best,
--Lorenz
--
Neu: GMX Doppel-FLAT mit Internet-Flatrate + Telefon-Flatrate
für nur 19,99 Euro/mtl.!* http://portal.gmx.net/de/go/dsl02

[Lorenz Minder]

Hi,

KB:
> * Bill Allombert [2009-09-16 12:46]:
> > Commited in revision 11921. I find very unfortunate that gerepileall
> > take an explicit argument number. I was hopping for some preprocessing
> > trickery to avoid that, but I found none.
>
> Neither did I when I orignally implemented it.

C89 does not have variadic macros, so I think it's unlikely this can be
done in C89.

But in the context it may be worth pointing out that users of libpari
who do not care for C89 compatibility can use C99's __VA_LIST__ for this
if they want the convenience.
   
#define gerepileall_a(av, ...) \
  gerepileall(av, sizeof((GEN*[]){__VA_LIST__})/sizeof(GEN*), __VA_LIST__)

Best,
--Lorenz

--
Jetzt kostenlos herunterladen: Internet Explorer 8 und Mozilla Firefox 3 -
sicherer, schneller und einfacher! http://portal.gmx.net/de/go/atbrowser

[Lorenz Minder]

LM:
>[...]
>    
> #define gerepileall_a(av, ...) \
>   gerepileall(av, sizeof((GEN*[]){__VA_LIST__})/sizeof(GEN*), __VA_LIST__)

Uhm, I meant __VA_ARGS__, not __VA_LIST__. Sorry.

--L
--
Jetzt kostenlos herunterladen: Internet Explorer 8 und Mozilla Firefox 3 -
sicherer, schneller und einfacher! http://portal.gmx.net/de/go/atbrowser

[Bill Allombert-3]

On Fri, Sep 18, 2009 at 07:40:37AM +0200, Lorenz Minder wrote:

> Hi,
>
> KB:
> > * Bill Allombert [2009-09-16 12:46]:
> > > Commited in revision 11921. I find very unfortunate that gerepileall
> > > take an explicit argument number. I was hopping for some preprocessing
> > > trickery to avoid that, but I found none.
> >
> > Neither did I when I orignally implemented it.
>
> C89 does not have variadic macros, so I think it's unlikely this can be
> done in C89.
>
> But in the context it may be worth pointing out that users of libpari
> who do not care for C89 compatibility can use C99's __VA_LIST__ for this
> if they want the convenience.
>    
> #define gerepileall_a(av, ...) \
>   gerepileall(av, sizeof((GEN*[]){__VA_LIST__})/sizeof(GEN*), __VA_LIST__)

Nice trick! At least we can use it in test-build, to check whether n
match the actual number of argument...

Unfortunately the idiom
gerepileall(av, A?2:1,A,B);
has become very common.

An unrelated issue is that gerepileall() does not call va_end

Cheers,
Bill.

[Bill Allombert-3]

On Thu, Sep 17, 2009 at 12:00:36PM +0200, Karim Belabas wrote:

> A note on this one: the old code was actually "not completely incorrect"
> since a,b are non-recursive objects of bounded size, a priori less
> than 100 times the stack space used up in a the 2 loop iterations during
> which they must survive. A simple avma = av would have been fine (and
> better).
>
> This technique of using for a very limited time an object that has just
> been reclaimed by the garbage collector is not infrequent in our code,
> and mandatorily flagged with a /* HACK */ comment. It saves a little
> time by avoiding an actual gerepile.

But it is actually unsafe: for example Fp_mul()
INLINE GEN
Fp_mul(GEN a, GEN b, GEN m)
{
  pari_sp av=avma;
  GEN p; /*HACK: assume modii use <=lg(p)+(lg(m)<<1) space*/
  (void)new_chunk(lg(a)+lg(b)+(lg(m)<<1));
  p = mulii(a,b);
  avma = av; <^C> return modii(p,m);
}

Assume the user press ^C just after 'avma = av;' and before 'return
modii(p,m);'and do some computation in the breakloop before continuing. The
computation will destroy the part of the stack below avma and modii() will
fail.

Cheers,
Bill.