sparse using insane amounts of memory

sparse using insane amounts of memory

[Johannes Berg]

[-- Attachment #1: Type: text/plain, Size: 494 bytes --]

Hi,

I was running make C=2 over the current wireless-dev tree (as of commit
4533da881f2d8c3e0dbb5b3dbc7a919e12438a8a) and reached
drivers/net/wireless/mac80211/rt2x00/rt2400pci.c when sparse started
using more and more memory. It went up to about 1 GB. Now I don't know
whether to blame sparse or if something's wrong with that file but it
does seem to be a bit excessive... Similar with all the other driver
files in that directory, yet I've not seen such a case before.

johannes

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 190 bytes --]

Re: sparse using insane amounts of memory

[Pavel Roskin]

On Thu, 2007-03-08 at 03:02 +0100, Johannes Berg wrote:
> Hi,
> 
> I was running make C=2 over the current wireless-dev tree (as of commit
> 4533da881f2d8c3e0dbb5b3dbc7a919e12438a8a) and reached
> drivers/net/wireless/mac80211/rt2x00/rt2400pci.c when sparse started
> using more and more memory. It went up to about 1 GB. Now I don't know
> whether to blame sparse or if something's wrong with that file but it
> does seem to be a bit excessive... Similar with all the other driver
> files in that directory, yet I've not seen such a case before.

You forgot the version of sparse.  I cannot reproduce the problem with
the current sparse from git
(git://git.kernel.org/pub/scm/linux/kernel/git/josh/sparse.git)

There were some bad bugs fixed recently.  If you are using the snapshot,
please download the latest snapshot now, as they were out-of-date until
very recently.

If you still have the problem, please remove rt2400pci.o and run:

make CC="gcc -save-temps -D__CHECKER__" KBUILD_NOCMDDEP=1

rt2400pci.i will be found in the root of the build tree.  Please see if
you have a problem with it.  If you do, please put it online and post
the URL.

If git sparse resolves the problem, I urge sparse developers to make
another release soon.

-- 
Regards,
Pavel Roskin

Re: sparse using insane amounts of memory

[Johannes Berg]

[-- Attachment #1: Type: text/plain, Size: 1079 bytes --]

On Thu, 2007-03-08 at 11:33 -0500, Pavel Roskin wrote:

> You forgot the version of sparse.

Good point. The commit is c4670dfcbe52b598e263c452762a66d22e636585.

>   I cannot reproduce the problem with
> the current sparse from git
> (git://git.kernel.org/pub/scm/linux/kernel/git/josh/sparse.git)

I just upgraded to 309f3805ddec9ab2f9c62da573586a7cf7c1f17a and still
observe that it uses a lot of memory.

> If you still have the problem, please remove rt2400pci.o and run:
> 
> make CC="gcc -save-temps -D__CHECKER__" KBUILD_NOCMDDEP=1
> 
> rt2400pci.i will be found in the root of the build tree.  Please see if
> you have a problem with it.  If you do, please put it online and post
> the URL.

I ran 

  make CC="gcc -save-temps -D__CHECKER__" KBUILD_NOCMDDEP=1 M=drivers/net/wireless/mac80211/rt2x00/

and aborted when I got lots of errors, rt2400pci.i was created and has
about 26k lines. Running sparse on it (sparse rt2400pci.i) takes a lot
of memory too. I put the file up at
http://johannes.sipsolutions.net/files/rt2400pci.i

johannes

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 190 bytes --]

Re: sparse using insane amounts of memory

[Pavel Roskin]

[Dropping linux-wireless, as there is nothing wireless below]

On Thu, 2007-03-08 at 17:45 +0100, Johannes Berg wrote:
>   make CC="gcc -save-temps -D__CHECKER__" KBUILD_NOCMDDEP=1 M=drivers/net/wireless/mac80211/rt2x00/
> 
> and aborted when I got lots of errors, rt2400pci.i was created and has
> about 26k lines. Running sparse on it (sparse rt2400pci.i) takes a lot
> of memory too. I put the file up at
> http://johannes.sipsolutions.net/files/rt2400pci.i

Thanks!  I see it now.  Sparse is taking about 700M on x86 and 1100M on
x86_64, which is much more than it uses for other files.

Valgrind reports something interesting, but not necessarily related to
the memory hogging:

==15775== Warning: invalid file descriptor -1 in syscall read()
==15775== Source and destination overlap in memcpy(0xBEFA84B4, 0xBEFA84D0, 48)
==15775==    at 0x4007242: memcpy (mc_replace_strmem.c:402)
==15775==    by 0x805E5CB: sort_list (sort.c:207)
==15775==    by 0x8061D7C: cleanup_and_cse (cse.c:247)
==15775==    by 0x805DE7B: linearize_symbol (linearize.c:2147)
==15775==    by 0x804AEC2: check_symbols (sparse.c:266)
==15775==    by 0x804B296: main (sparse.c:284)

If sparse is compiled without optimization, the "overlap" warning is not
reported.  I think it can be ignored.

It takes several minutes for sparse to process rt2400pci.i under
valgrind.  I haven't tried looking for leaks yet.

Reducing the file may be tricky, since there is no definite way to say
if the problem exists once the code becomes shorter.  But I'll try.

-- 
Regards,
Pavel Roskin

Re: sparse using insane amounts of memory

[Chris Wedgwood]

On Thu, Mar 08, 2007 at 12:13:30PM -0500, Pavel Roskin wrote:

> Reducing the file may be tricky, since there is no definite way to
> say if the problem exists once the code becomes shorter.  But I'll
> try.

Some lines are thousands of characters long, probably the result of
cpp macro expansion?  I see many lines over 10,000 characters long,
some as much as 81,000 characters long.

I'm not saying that is the cause of this, but i'd certainly be
suspicious of those.

I have to wonder about code that expands *that* much, more a case of
macro abuse than use perhaps?

Re: sparse using insane amounts of memory

[Pavel Roskin]

On Thu, 2007-03-08 at 17:45 +0100, Johannes Berg wrote:
> and aborted when I got lots of errors, rt2400pci.i was created and has
> about 26k lines. Running sparse on it (sparse rt2400pci.i) takes a lot
> of memory too. I put the file up at
> http://johannes.sipsolutions.net/files/rt2400pci.i

FIELDS32 expands to some monstrosities.  Look for rt2x00_bbp_write in
the dump.  Also behold the amount of parentheses in LOWEST_BIT32.
That's almost certainly the culprit.

I understand the idea is to make gcc calculate integer logarithms at the
compile time.  That's nice, but sparse has to do the same, and it's
probably not optimized for such misuse.

-- 
Regards,
Pavel Roskin

Re: sparse using insane amounts of memory

[Johannes Berg]

[-- Attachment #1: Type: text/plain, Size: 581 bytes --]

On Thu, 2007-03-08 at 12:34 -0500, Pavel Roskin wrote:

> FIELDS32 expands to some monstrosities.  Look for rt2x00_bbp_write in
> the dump.  Also behold the amount of parentheses in LOWEST_BIT32.
> That's almost certainly the culprit.

Ouch, yeah, looks pretty bad.

> I understand the idea is to make gcc calculate integer logarithms at the
> compile time.  That's nice, but sparse has to do the same, and it's
> probably not optimized for such misuse.

The whole logic there is beyond me without giving it some serious look
so I'll trust you on that :)

johannes

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 190 bytes --]

Re: sparse using insane amounts of memory

[Johannes Berg]

[-- Attachment #1: Type: text/plain, Size: 336 bytes --]

On Thu, 2007-03-08 at 12:34 -0500, Pavel Roskin wrote:

> FIELDS32 expands to some monstrosities.  Look for rt2x00_bbp_write in
> the dump.  Also behold the amount of parentheses in LOWEST_BIT32.
> That's almost certainly the culprit.

And I even had CONFIG_RT2X00_DEBUG enabled so it's worse that the
regular case.

johannes

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 190 bytes --]

Re: sparse using insane amounts of memory

[Linus Torvalds]

On Thu, 8 Mar 2007, Pavel Roskin wrote:
> 
> Reducing the file may be tricky, since there is no definite way to say
> if the problem exists once the code becomes shorter.  But I'll try.

I would guess at

	static inline __attribute__((always_inline)) void device_rate_entry(..)

because while that function *looks* really simple ("Hey, it's just ten 
lines"), those lines expand to some nested compile-time constant macros 
from hell, and the end result is hundreds and hundreds of lines of really 
dense code because the macros are set up to be able to handle constant 
arguments asa constant.

That thing is a thing from hell.

			Linus

Re: sparse using insane amounts of memory

[Ivo van Doorn]

On Thursday 08 March 2007 18:43, Johannes Berg wrote:
> On Thu, 2007-03-08 at 12:34 -0500, Pavel Roskin wrote:
> 
> > FIELDS32 expands to some monstrosities.  Look for rt2x00_bbp_write in
> > the dump.  Also behold the amount of parentheses in LOWEST_BIT32.
> > That's almost certainly the culprit.
> 
> And I even had CONFIG_RT2X00_DEBUG enabled so it's worse that the
> regular case.

Those checks are intended to doublecheck the register FIELD{16,32}
defines. Since all register definitions were rewritten from the legacy driver,
(legacy driver used unions and structs for all registers) some of those
defines weren't done correctly (A bitmask could for example be in binary 000110111
which is very wrong).

To check those the register checks were added to ensure the register defines
were at least correct. I am however open to suggestions on how this should be improved
and cleaned up, since it is not my favorite piece of code. ;)

Ivo

Re: sparse using insane amounts of memory

[Linus Torvalds]

On Thu, 8 Mar 2007, Ivo van Doorn wrote:
> 
> Those checks are intended to doublecheck the register FIELD{16,32}
> defines. Since all register definitions were rewritten from the legacy driver,
> (legacy driver used unions and structs for all registers) some of those
> defines weren't done correctly (A bitmask could for example be in binary 000110111
> which is very wrong).
>
> To check those the register checks were added to ensure the register defines
> were at least correct. I am however open to suggestions on how this should be improved
> and cleaned up, since it is not my favorite piece of code. ;)

What is the check? Just checking that something is an exact power of two?

To check a value for being a nice range of consecutive bits, you can 
simply do:

	#define is_power_of_two(x) (!((x) & ((x)-1)))
	#define low_bit_mask(x) (((x)-1) & ~(x))
	#define is_contiguous_mask(x) is_power_of_two(1 + (x) + low_bit_mask(x))

and now you have a nice and simple (and efficient) expression for whether 
something is a contiguous mask of bits.

You can then make it a compile-time failure with something like

	extern unsigned int this_doesnt_exist_and_wont_link;

	is_contiguous_mask(x) ? (x) : this_doesnt_exist_and_wont_link;

which returns "x" if it's ok, and an unlinkable expression if it isn't.

[ Explanation, if anybody cares:

 - is_power_of_two(x) is hopefully obvious to all. But anyway: the "x-1" 
   means that the lowest bit set will be borrowed out of, turning all bits 
   *below* it to 1, and leaving all bits *above* it unchanged. So when you 
   do "x & (x-1)" that's zero *only* if "x" itself was zero, or it was a 
   power of two (ie there was just a single bit set - otherwise the bits 
   above that bit would survive the bitwise 'and' operation, and the end 
   result would be non-zero.

 - low_bits_mask(x) takes "x", and turns the lowest zero bits on, and 
   clears all other bits. It does so by again subtracting 1 (same trick as 
   above: the bits below the first 1-bit will become 1 through the borrow, 
   and the lowest bit itself will be cleared.

   Doing the "& ~x" will then mask off all the higher bits if there were 
   any (and obviouly the lowest bit too, since that was cleared by the 
   "-1" when we borrowed out of it).

 - "is_contiguous_mask()" basically just says: if we take the low zero 
   bits, and turn them into ones, and add one, the end result should then 
   carry out to become a power-of-two.

  Example:  x = 0x01c ( 0000.0001.1100 )

	x - 1 = 0x01b ( 0000.0001.1011 )

	   ~x = 0xfe3 ( 1111.1110.0011 )
	
	low   = 0x003 ( 0000.0000.0011 ) (bitwise "and")

    x + low   = 0x01f ( 0000.0001.1111 ) (effectively just the bitwise "or")

    1+x+low   = 0x020 ( 0000.0010.0000 )

   and that's obviously a power of two (test with the trivial thing). ]

Thus endeth Linus' "games with bits" lecture. It was probably more than 
you really wanted to know. There's a ton of games you can play with simple 
"x-1" and bitmasking ops like this).

		Linus

Re: sparse using insane amounts of memory

[Sam Ravnborg]

> 
> You can then make it a compile-time failure with something like
> 
> 	extern unsigned int this_doesnt_exist_and_wont_link;
> 
> 	is_contiguous_mask(x) ? (x) : this_doesnt_exist_and_wont_link;
> 
> which returns "x" if it's ok, and an unlinkable expression if it isn't.

Or you can use the already defined macros in kernel.h for this:

/* Force a compilation error if condition is true */
#define BUILD_BUG_ON(condition) ((void)sizeof(char[1 - 2*!!(condition)]))

/* Force a compilation error if condition is true, but also produce a
   result (of value 0 and type size_t), so the expression can be used
   e.g. in a structure initializer (or where-ever else comma expressions
   aren't permitted). */
#define BUILD_BUG_ON_ZERO(e) (sizeof(char[1 - 2 * !!(e)]) - 1)

	Sam

Re: sparse using insane amounts of memory

[Linus Torvalds]

On Thu, 8 Mar 2007, Linus Torvalds wrote:
> 
> To check a value for being a nice range of consecutive bits, you can 
> simply do:
> 
> 	#define is_power_of_two(x) (!((x) & ((x)-1)))
> 	#define low_bit_mask(x) (((x)-1) & ~(x))
> 	#define is_contiguous_mask(x) is_power_of_two(1 + (x) + low_bit_mask(x))

Side note: I didn't check this. So if you actually do this, please 
double-check. The math should all be good, but there's a few caveats:

 - I might have made a mistake

 - 0 is special, and is generally considered to be a power of two (and 
   this is more fundamental than you'd think: it's not just fall-out from 
   the particular expression chosen, it is fundamentally *required* to 
   handle overflow, and you can think of 0 as 2**x, x > wordsize if that 
   makes you more comfortable with the notion that zero is a power-of-two 
   in any finite representation of 2's complement)

The "zero is special" thing means that if you don't want to accept zero as 
a valid mask (it technically *is* a contiguous set of bits set - it's just 
the empty set) you'd need to check for it specially.

But the "I might have made a mistake" part is worth just remembering, and 
just double-checking it all.

		Linus

Re: sparse using insane amounts of memory

[Ivo van Doorn]

> > 	#define is_power_of_two(x) (!((x) & ((x)-1)))
> > 	#define low_bit_mask(x) (((x)-1) & ~(x))
> > 	#define is_contiguous_mask(x) is_power_of_two(1 + (x) + low_bit_mask(x))
> 
> Side note: I didn't check this. So if you actually do this, please 
> double-check. The math should all be good, but there's a few caveats:

Checked, and seems to work. Even sparse appears to be very happy. :)
I'll do some more extensive testing later today before submitting a patch.
 
> The "zero is special" thing means that if you don't want to accept zero as 
> a valid mask (it technically *is* a contiguous set of bits set - it's just 
> the empty set) you'd need to check for it specially.

Good point, I'll add a check for that as well.

> Thus endeth Linus' "games with bits" lecture. It was probably more than 
> you really wanted to know. There's a ton of games you can play with simple 
> "x-1" and bitmasking ops like this).

Thanks, for both the macro's and the lecture. ;)

Ivo

OT [Re: sparse using insane amounts of memory]

[Tommy Thorn]

Linus Torvalds said:
....
> Thus endeth Linus' "games with bits" lecture. It was probably more than you
> really wanted to know. There's a ton of games you can play with simple "x-1"
and
> bitmasking ops like this).

For anyone who enjoy this stuff (don't we all?), I heartily recommend Knuth's
recent "Bitwise Tricks and Techniques" Pre-Fascicle:
http://www-cs-faculty.stanford.edu/~knuth/news.html

Regards,
Tommy

Re: OT

[David Miller]

From: "Tommy Thorn" <tommy@numba-tu.com>
Date: Thu, 8 Mar 2007 17:12:44 -0800 (PST)

> Linus Torvalds said:
> ....
> > Thus endeth Linus' "games with bits" lecture. It was probably more than you
> > really wanted to know. There's a ton of games you can play with simple "x-1"
> and
> > bitmasking ops like this).
> 
> For anyone who enjoy this stuff (don't we all?), I heartily recommend Knuth's
> recent "Bitwise Tricks and Techniques" Pre-Fascicle:
> http://www-cs-faculty.stanford.edu/~knuth/news.html

Or "Hacker's Delight" which comes up from time to time on these
lists as well.

Re: sparse using insane amounts of memory

[Darren Jenkins]

On 3/9/07, Linus Torvalds <torvalds-de/tnXTf+JLsfHDXvbKv3WD2FQJk+8+b@public.gmane.org> wrote:
>
>
> On Thu, 8 Mar 2007, Linus Torvalds wrote:
> >
> > To check a value for being a nice range of consecutive bits, you can
> > simply do:
> >
> >       #define is_power_of_two(x) (!((x) & ((x)-1)))

There is already an inline for this in log2.h

/*
 *  Determine whether some value is a power of two, where zero is
 * *not* considered a power of two.
 */

static inline __attribute__((const))
bool is_power_of_2(unsigned long n)
{
	return (n != 0 && ((n & (n - 1)) == 0));
}

>  - 0 is special, and is generally considered to be a power of two (and
>    this is more fundamental than you'd think: it's not just fall-out from
>    the particular expression chosen, it is fundamentally *required* to
>    handle overflow, and you can think of 0 as 2**x, x > wordsize if that
>    makes you more comfortable with the notion that zero is a power-of-two
>    in any finite representation of 2's complement)
>
> The "zero is special" thing means that if you don't want to accept zero as
> a valid mask (it technically *is* a contiguous set of bits set - it's just
> the empty set) you'd need to check for it specially.

I guess the person who wrote it wasn't thinking discrete maths at the time.

Darren J.