Sparse warning: bitmap.h: bad constant expression

Sparse warning: bitmap.h: bad constant expression

[Petri Koistinen]

Hi!

If I try to compile latest kernel with "make C=1" I'll get many warning
messages from sparse saying:

warning: include/linux/bitmap.h:85:2: bad constant expression
warning: include/linux/bitmap.h:98:2: bad constant expression

Sparse doesn't seem to like DECLARE_BITMAP macros.

#define DECLARE_BITMAP(name,bits) \
        unsigned long name[BITS_TO_LONGS(bits)]

So what is wrong with this and how it could be fixed so that sparse
wouldn't complain?

Best regards,
Petri Koistinen

Re: Sparse warning: bitmap.h: bad constant expression

[Dave Olien]

The problem seems to be that sparse currently will only accept array
declarations with a size that can be evaluated at compile time to
a fixed value.  So an array declaration of the form:

int asize;
int data[asize];

will fail.  sparse needs to be modified to recognize this type of 
declaration with a variable array size.  That'll take a few hours of
someone's time to fix.

On Mon, Sep 01, 2003 at 10:59:21PM +0300, Petri Koistinen wrote:
> Hi!
> 
> If I try to compile latest kernel with "make C=1" I'll get many warning
> messages from sparse saying:
> 
> warning: include/linux/bitmap.h:85:2: bad constant expression
> warning: include/linux/bitmap.h:98:2: bad constant expression
> 
> Sparse doesn't seem to like DECLARE_BITMAP macros.
> 
> #define DECLARE_BITMAP(name,bits) \
>         unsigned long name[BITS_TO_LONGS(bits)]
> 
> So what is wrong with this and how it could be fixed so that sparse
> wouldn't complain?
> 
> Best regards,
> Petri Koistinen
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/

Re: Sparse warning: bitmap.h: bad constant expression

[Jörn Engel]

On Mon, 1 September 2003 18:57:02 -0700, Dave Olien wrote:
> 
> The problem seems to be that sparse currently will only accept array
> declarations with a size that can be evaluated at compile time to
> a fixed value.  So an array declaration of the form:
> 
> int asize;
> int data[asize];
> 
> will fail.  sparse needs to be modified to recognize this type of 
> declaration with a variable array size.  That'll take a few hours of
> someone's time to fix.

Not quite true.  The above is an implicit call to alloca and should
not exist in the kernel.  No need to hack support into sparse.

Petri's code below has constant array bounds, once the preprocessing
is done, that should be fixed in sparse.

> On Mon, Sep 01, 2003 at 10:59:21PM +0300, Petri Koistinen wrote:
> > Hi!
> > 
> > If I try to compile latest kernel with "make C=1" I'll get many warning
> > messages from sparse saying:
> > 
> > warning: include/linux/bitmap.h:85:2: bad constant expression
> > warning: include/linux/bitmap.h:98:2: bad constant expression
> > 
> > Sparse doesn't seem to like DECLARE_BITMAP macros.
> > 
> > #define DECLARE_BITMAP(name,bits) \
> >         unsigned long name[BITS_TO_LONGS(bits)]
> > 
> > So what is wrong with this and how it could be fixed so that sparse
> > wouldn't complain?

Sorry, I've just had a casual glance at sparse so far.  Looks like a
preprocessing problem, that's all I can say.

Jörn

-- 
Fancy algorithms are slow when n is small, and n is usually small.
Fancy algorithms have big constants. Until you know that n is
frequently going to be big, don't get fancy.
-- Rob Pike

Re: Sparse warning: bitmap.h: bad constant expression

[Mikael Pettersson]

=?iso-8859-1?Q?J=F6rn?= Engel writes:
 > On Mon, 1 September 2003 18:57:02 -0700, Dave Olien wrote:
 > > 
 > > The problem seems to be that sparse currently will only accept array
 > > declarations with a size that can be evaluated at compile time to
 > > a fixed value.  So an array declaration of the form:
 > > 
 > > int asize;
 > > int data[asize];
 > > 
 > > will fail.  sparse needs to be modified to recognize this type of 
 > > declaration with a variable array size.  That'll take a few hours of
 > > someone's time to fix.
 > 
 > Not quite true.  The above is an implicit call to alloca and should
 > not exist in the kernel.  No need to hack support into sparse.

If data is a local variable then this is perfectly valid example of a
C99 variable-length array (VLA). This works at least with gcc-2.95.3
and newer, and gcc handles it by itself w/o calling alloca().

Of course, VLAs should be bounded in size to avoid overflowing the
kernel stack, but that doesn't make them illegal per se.

/Mikael

Re: Sparse warning: bitmap.h: bad constant expression

[Jörn Engel]

On Tue, 2 September 2003 12:23:44 +0200, Mikael Pettersson wrote:
> =?iso-8859-1?Q?J=F6rn?= Engel writes:
>  > On Mon, 1 September 2003 18:57:02 -0700, Dave Olien wrote:
>  > > 
>  > > The problem seems to be that sparse currently will only accept array
>  > > declarations with a size that can be evaluated at compile time to
>  > > a fixed value.  So an array declaration of the form:
>  > > 
>  > > int asize;
>  > > int data[asize];
>  > > 
>  > > will fail.  sparse needs to be modified to recognize this type of 
>  > > declaration with a variable array size.  That'll take a few hours of
>  > > someone's time to fix.
>  > 
>  > Not quite true.  The above is an implicit call to alloca and should
>  > not exist in the kernel.  No need to hack support into sparse.
> 
> If data is a local variable then this is perfectly valid example of a
> C99 variable-length array (VLA). This works at least with gcc-2.95.3
> and newer, and gcc handles it by itself w/o calling alloca().
> 
> Of course, VLAs should be bounded in size to avoid overflowing the
> kernel stack, but that doesn't make them illegal per se.

Ok, if you prefer this wording:
"It does exactly what alloca() would do, but is harder to grep for."

It uses an unknown amount of stack space, the stack is finite and
small and random bad things happen when it spills over.

Jörn

-- 
"Security vulnerabilities are here to stay."
-- Scott Culp, Manager of the Microsoft Security Response Center, 2001

Re: Sparse warning: bitmap.h: bad constant expression

[Linus Torvalds]

Mikael Pettersson wrote:
> 
> If data is a local variable then this is perfectly valid example of a
> C99 variable-length array (VLA). This works at least with gcc-2.95.3
> and newer, and gcc handles it by itself w/o calling alloca().

"alloca()" is not a function. It's a compiler intrisic, and Jörn is correct:
a variable-length array is _exactly_ the same as the historic "alloca()"
thing, and will generate the same code (modulo syntactic changes due to the
fact that one generates a pointer and the other generates an array).

And yes, it is legal in C99. However, it's not supposed to be legal in the
kernel, because it makes it impossible to check certain trivial things
about stack usage automatially. In particular, it totally breaks the
"objdump + grep" approach for finding bad stack users.

Also, trivial bugs (like not checking ranges etc) cause total stack
corruption with the feature, which means that such a kernel bug gets really
hard to track down.

So I consider the sparse warning to be appropriate.

That said, I do want to have a code-generation back-end for sparse some day,
if only because it's the only practical way to validate the front-end (ie
seeing if the back-end generates code that actually works - performance
doesn't matter). So I'd like to eventually extend sparse to handle variable
arrays, but I'd still want to have a flag to warn about them.

                Linus

Re: Sparse warning: bitmap.h: bad constant expression

[Jörn Engel]

On Tue, 2 September 2003 12:23:44 +0200, Mikael Pettersson wrote:
> 
> If data is a local variable then this is perfectly valid example of a
> C99 variable-length array (VLA). This works at least with gcc-2.95.3
> and newer, and gcc handles it by itself w/o calling alloca().

A lot of buggy code consists of perfectly valid C99. :)

> Of course, VLAs should be bounded in size to avoid overflowing the
> kernel stack, but that doesn't make them illegal per se.

There is a deeper problem to this.  At the moment, there is no way to
prove that the kernel doesn't contain a stack overflow somewhere.  In
order to do this, we can make some assumptions and do a formal proof
*as long as the assumptions are valid*.

This perfectly valid C99 code means either that we need very
complicated checker software - a problem in itself - or that the
assumptions are wrong and we are none the wiser.

And even if you ignore this pet project of mine, do you know of a sane
way to have an upper bound for a VLA?  And if there is, why not use a
static array with the upper bound as size in the first place?
Explicit is always simpler than implicit and simpler code has less
bugs. :)

Jörn

-- 
To recognize individual spam features you have to try to get into the
mind of the spammer, and frankly I want to spend as little time inside
the minds of spammers as possible.
-- Paul Graham

Re: Sparse warning: bitmap.h: bad constant expression

[Dave Olien]

I was lazy with my problem summary yesterday.  The sparse warning is actually
about the declaration of the functions bitmap_shift_right() and
bitmap_shift_left() in bitmap.h.  In these cases, the bits argument to
DECLARE_BITMAP() was an argument to the function, and th variable sized
array is in the scope of that function.

The only uses of these functions I can find are in the macros
physids_shift_right, physids_shift_left, in mpsec.h, and cpus_shift_rigt
and cpus_shift_left, in cpumask_array.h.

In all uses, the "bits" argument eventually resolves to being a constant.
It would require the inline expansion of the bitmap_shift_*() functions
to take advantage of that.

Otherwise, as has been pointed out, this is valid C99.

On Tue, Sep 02, 2003 at 11:56:28AM +0200, Jörn Engel wrote:
> 
> Not quite true.  The above is an implicit call to alloca and should
> not exist in the kernel.  No need to hack support into sparse.
> 
> Petri's code below has constant array bounds, once the preprocessing
> is done, that should be fixed in sparse.
> 
> > On Mon, Sep 01, 2003 at 10:59:21PM +0300, Petri Koistinen wrote:
> > > Hi!
> > > 
> > > If I try to compile latest kernel with "make C=1" I'll get many warning
> > > messages from sparse saying:
> > > 
> > > warning: include/linux/bitmap.h:85:2: bad constant expression
> > > warning: include/linux/bitmap.h:98:2: bad constant expression
> > > 
> > > Sparse doesn't seem to like DECLARE_BITMAP macros.
> > > 
> > > #define DECLARE_BITMAP(name,bits) \
> > >         unsigned long name[BITS_TO_LONGS(bits)]
> > > 
> > > So what is wrong with this and how it could be fixed so that sparse
> > > wouldn't complain?
> 
> Sorry, I've just had a casual glance at sparse so far.  Looks like a
> preprocessing problem, that's all I can say.
> 
> Jörn
> 
> -- 
> Fancy algorithms are slow when n is small, and n is usually small.
> Fancy algorithms have big constants. Until you know that n is
> frequently going to be big, don't get fancy.
> -- Rob Pike
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/

Re: Sparse warning: bitmap.h: bad constant expression

[Jörn Engel]

On Tue, 2 September 2003 10:38:44 -0700, Dave Olien wrote:
> 
> I was lazy with my problem summary yesterday.  The sparse warning is actually
> about the declaration of the functions bitmap_shift_right() and
> bitmap_shift_left() in bitmap.h.  In these cases, the bits argument to
> DECLARE_BITMAP() was an argument to the function, and th variable sized
> array is in the scope of that function.
> 
> The only uses of these functions I can find are in the macros
> physids_shift_right, physids_shift_left, in mpsec.h, and cpus_shift_rigt
> and cpus_shift_left, in cpumask_array.h.
> 
> In all uses, the "bits" argument eventually resolves to being a constant.
> It would require the inline expansion of the bitmap_shift_*() functions
> to take advantage of that.

If your analysis is correct, this looks safe enough for now.  It would
be nice to replace it with something more explicit, but I just don't
care enough yet.

Jörn

-- 
Fantasy is more important than knowlegde. Knowlegde is limited,
while fantasy embraces the whole world.
-- Albert Einstein

Re: Sparse warning: bitmap.h: bad constant expression

[William Lee Irwin III]

On Mon, Sep 01, 2003 at 10:59:21PM +0300, Petri Koistinen wrote:
> If I try to compile latest kernel with "make C=1" I'll get many warning
> messages from sparse saying:
> warning: include/linux/bitmap.h:85:2: bad constant expression
> warning: include/linux/bitmap.h:98:2: bad constant expression
> Sparse doesn't seem to like DECLARE_BITMAP macros.
> #define DECLARE_BITMAP(name,bits) \
>         unsigned long name[BITS_TO_LONGS(bits)]
> So what is wrong with this and how it could be fixed so that sparse
> wouldn't complain?

Basically, this thing is intended to be used with a constant bits
argument that's constant folded etc. at all times, but sparse doesn't
know that.

One way to deal with it is to turn the thing into a giant macro.


-- wli
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/
On Mon, Sep 01, 2003 at 10:59:21PM +0300, Petri Koistinen wrote:
> If I try to compile latest kernel with "make C=1" I'll get many warning
> messages from sparse saying:
> warning: include/linux/bitmap.h:85:2: bad constant expression
> warning: include/linux/bitmap.h:98:2: bad constant expression
> Sparse doesn't seem to like DECLARE_BITMAP macros.
> #define DECLARE_BITMAP(name,bits) \
>         unsigned long name[BITS_TO_LONGS(bits)]
> So what is wrong with this and how it could be fixed so that sparse
> wouldn't complain?

Basically, this thing is intended to be used with a constant bits
argument that's constant folded etc. at all times, but sparse doesn't
know that.

One way to deal with it is to turn the thing into a giant macro.


-- wli