Worst recursion in the kernel

Worst recursion in the kernel

[Jörn Engel]

Really bad code demand really rude words, sorry.


After playing with stack checking again, I've found this little beauty
in 2.6.0-test3: [1]

WARNING: recursion detected:
      20  read_cis_cache
      36  pcmcia_get_tuple_data
     308  read_tuple
     448  pcmcia_validate_cis
      12  readable
      24  cis_readable
      28  do_mem_probe
      24  inv_probe
      16  validate_mem
      32  set_cis_map
      28  read_cis_mem
     284  verify_cis_cache

Explanation:
verify_cis_cache calls read_cis_mem, which calls set_cis_map, which
call ..., which calls read_cis_cache, which finally calls
verify_cis_cache again.

The numbers to the left is the stack space consumed by each function.
See drivers/pcmcia/cistpl.c and drivers/pcmcia/rsrc_mgr.c for all the
glory.


Most likely this recursion will never occur, as one of those calls can
depends on circumstances that prohibit recursion, but semantic
checking is a bitch for software and in this case even for humans.
Put another way: THERE IS NO WAY TO MAKE SURE THIS WORKS.

If the code cannot be made simpler, how can anyone fix bugs in it.
Just reread the famous signature about code being as smart as
possible.


*sigh*


Ok David, sorry about this.  There are more cases of similar
recursions in the kernel, just not quite as bad.  And I had to pick
someone as a bad example and start a small public flamefest, so people
realize the problem.

Still, you should have a close look at that code path during 2.7 and
see if it really makes sense the way it is now.


[1] Yes, it is outdated, but I need stable test data for now.

Jörn

-- 
Measure. Don't tune for speed until you've measured, and even then
don't unless one part of the code overwhelms the rest.
-- Rob Pike

Re: Worst recursion in the kernel

[David Hinds]

On Wed, Dec 03, 2003 at 03:31:22PM +0100, Jörn Engel wrote:
> Really bad code demand really rude words, sorry.
> 
> 
> After playing with stack checking again, I've found this little beauty
> in 2.6.0-test3: [1]
> 
> WARNING: recursion detected:
>       20  read_cis_cache
>       36  pcmcia_get_tuple_data
>      308  read_tuple
>      448  pcmcia_validate_cis
>       12  readable
>       24  cis_readable
>       28  do_mem_probe
>       24  inv_probe
>       16  validate_mem
>       32  set_cis_map
>       28  read_cis_mem
>      284  verify_cis_cache
> 
> Explanation:
> verify_cis_cache calls read_cis_mem, which calls set_cis_map, which
> call ..., which calls read_cis_cache, which finally calls
> verify_cis_cache again.

Err... no it doesn't.  verify_cis_cache() is called from exactly one
place which is not in the list of functions here.  I do not understand
how this recursion checking is being done but there's something weird
going on.  set_cis_map() does not call any function on this list.  I
think set_cis_map() should be setup_cis_mem().

> Most likely this recursion will never occur, as one of those calls can
> depends on circumstances that prohibit recursion, but semantic
> checking is a bitch for software and in this case even for humans.
> Put another way: THERE IS NO WAY TO MAKE SURE THIS WORKS.

Isn't that a bit strong a statement?

The semantics of the code goes like this.  read_cis_mem() checks to
see if something has been done.  If it hasn't been done, it leads to
validate_mem() which first does that thing, and then does some stuff
that leads to read_cis_mem() being called again.  When read_cis_mem()
is reentered, it is guaranteed that the condition for recursion does
not exist.

Is that so complex as to be incomprehensible by a mere human?  To
remove the apparent recursion seems to me to require duplicating a
fairly long code path, which is why I did it this way in the first
place.  The stack usage of this code path is definitely something that
should be (and can be easily) fixed.

-- Dave

Re: Worst recursion in the kernel

[Jörn Engel]

On Wed, 3 December 2003 10:07:09 -0800, David Hinds wrote:
> On Wed, Dec 03, 2003 at 03:31:22PM +0100, Jörn Engel wrote:
> > 
> > WARNING: recursion detected:
> >       20  read_cis_cache
> >       36  pcmcia_get_tuple_data
> >      308  read_tuple
> >      448  pcmcia_validate_cis
> >       12  readable
> >       24  cis_readable
> >       28  do_mem_probe
> >       24  inv_probe
> >       16  validate_mem
> >       32  set_cis_map
> >       28  read_cis_mem
> >      284  verify_cis_cache
> > 
> > Explanation:
> > verify_cis_cache calls read_cis_mem, which calls set_cis_map, which
> > call ..., which calls read_cis_cache, which finally calls
> > verify_cis_cache again.
> 
> Err... no it doesn't.  verify_cis_cache() is called from exactly one
> place which is not in the list of functions here.  I do not understand
> how this recursion checking is being done but there's something weird
> going on.  set_cis_map() does not call any function on this list.  I
> think set_cis_map() should be setup_cis_mem().

You are right, verify_cis_cache() does not belong into the list.
Gotta see where that bug comes from.  set_cis_map() is correct,
though.  It does call validate_mem(), at least in my copy of
2.6.0-test11:

static unsigned char *
set_cis_map(struct pcmcia_socket *s, unsigned int card_offset, unsigned int flags)
{
    pccard_mem_map *mem = &s->cis_mem;
    if (!(s->features & SS_CAP_STATIC_MAP) &&
	mem->sys_start == 0) {
	validate_mem(s);
	...

You can have the current code if you are really interested.  It takes
the call graph as generated by smatch and follows all function calls.
If it ever revisits a function that was already on the path, it prints
out a warning like above.

> > Most likely this recursion will never occur, as one of those calls can
> > depends on circumstances that prohibit recursion, but semantic
> > checking is a bitch for software and in this case even for humans.
> > Put another way: THERE IS NO WAY TO MAKE SURE THIS WORKS.
> 
> Isn't that a bit strong a statement?

Maybe, but my preference for simple code is just as strong.  "NO WAY"
may not be quite right, but it is very close from my experience.
Enough complexity and my little brain will be unable to expand any
program.  Almost enough complexity and working with the code takes an
awful amount of time because mistakes are so much more likely.

Simple code is good.

But your opinion may differ and you are ultimately the maintainer, so
feel free to ignore me.  It least I would like people to think twice
before creating such a construct and then think again after having
done so.

> The semantics of the code goes like this.  read_cis_mem() checks to
> see if something has been done.  If it hasn't been done, it leads to
> validate_mem() which first does that thing, and then does some stuff
> that leads to read_cis_mem() being called again.  When read_cis_mem()
> is reentered, it is guaranteed that the condition for recursion does
> not exist.
> 
> Is that so complex as to be incomprehensible by a mere human?  To
> remove the apparent recursion seems to me to require duplicating a
> fairly long code path, which is why I did it this way in the first
> place.  The stack usage of this code path is definitely something that
> should be (and can be easily) fixed.

I have no better alternative availlable right now, but there must be
another way.  Maybe something like this:

read_cis_mem() {
	if (__read_cis_mem() != -EAGAIN)
		return;
	validate_mem();
	__read_cis_mem();
}

__read_cis_mem() now contains the previous functionality of
read_cis_mem() and returns -EGAIN instead of calling validate_mem()
directly.


Not sure about you, but it would make my program much happier.  If you
look at the relevant part of the call graph (below), you will notice
that inv_probe() alone is already recursive.  Having multiple
recursions to worry about in the same function is where the problem
stops being difficult and becomes impossible.

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

NAME:	read_tuple
SCOPE:	g
SIZE:	308
CALLS:	pcmcia_get_first_tuple
CALLS:	pcmcia_get_tuple_data
CALLS:	pcmcia_parse_tuple
NAME:	pcmcia_get_tuple_data
SCOPE:	g
SIZE:	36
CALLS:	read_cis_cache
NAME:	read_cis_cache
SCOPE:	l
SIZE:	20
CALLS:	__builtin_constant_p
CALLS:	__constant_c_and_count_memset
CALLS:	__constant_c_memset
CALLS:	__constant_memcpy
CALLS:	__memcpy
CALLS:	kmalloc
CALLS:	list_add
CALLS:	prefetch
CALLS:	read_cb_mem
CALLS:	read_cis_mem
NAME:	read_cis_mem
SCOPE:	g
SIZE:	28
CALLS:	__builtin_constant_p
CALLS:	__constant_c_and_count_memset
CALLS:	__constant_c_memset
CALLS:	set_cis_map
NAME:	set_cis_map
SCOPE:	l
SIZE:	32
CALLS:	find_mem_region
CALLS:	ioremap
CALLS:	iounmap
CALLS:	printk
CALLS:	validate_mem
NAME:	validate_mem
SCOPE:	g
SIZE:	16
CALLS:	do_mem_probe
CALLS:	down
CALLS:	inv_probe
CALLS:	printk
CALLS:	sub_interval
CALLS:	up
NAME:	inv_probe
SCOPE:	l
SIZE:	24
CALLS:	do_mem_probe
CALLS:	inv_probe
CALLS:	sub_interval
NAME:	do_mem_probe
SCOPE:	l
SIZE:	28
CALLS:	checksum_match
CALLS:	cis_readable
CALLS:	printk
CALLS:	sub_interval
NAME:	cis_readable
SCOPE:	l
SIZE:	24
CALLS:	__request_region
CALLS:	readable
CALLS:	release_resource
NAME:	readable
SCOPE:	l
SIZE:	12
CALLS:	destroy_cis_cache
CALLS:	ioremap
CALLS:	iounmap
CALLS:	pcmcia_validate_cis
NAME:	pcmcia_validate_cis
SCOPE:	g
SIZE:	448
CALLS:	pcmcia_get_first_tuple
CALLS:	pcmcia_get_next_tuple
CALLS:	read_tuple

Re: Worst recursion in the kernel

[Russell King]

On Wed, Dec 03, 2003 at 08:04:40PM +0100, Jörn Engel wrote:
> You are right, verify_cis_cache() does not belong into the list.
> Gotta see where that bug comes from.  set_cis_map() is correct,
> though.  It does call validate_mem(), at least in my copy of
> 2.6.0-test11:
> 
> static unsigned char *
> set_cis_map(struct pcmcia_socket *s, unsigned int card_offset, unsigned int flags)
> {
>     pccard_mem_map *mem = &s->cis_mem;
>     if (!(s->features & SS_CAP_STATIC_MAP) &&
> 	mem->sys_start == 0) {
> 	validate_mem(s);
> 	...
> 
> You can have the current code if you are really interested.  It takes
> the call graph as generated by smatch and follows all function calls.
> If it ever revisits a function that was already on the path, it prints
> out a warning like above.

Yes, but the condition of the /data/ is such that it will not recurse.

A pure "can this function call that function" analysis ignoring the
state of the data will say this will infinitely recuse.  Include
the data, and you'll find it has a very definite recursion limit.

-- 
Russell King
 Linux kernel    2.6 ARM Linux   - http://www.arm.linux.org.uk/
 maintainer of:  2.6 PCMCIA      - http://pcmcia.arm.linux.org.uk/
                 2.6 Serial core

Re: Worst recursion in the kernel

[Mike Fedyk]

On Wed, Dec 03, 2003 at 10:57:43PM +0000, Russell King wrote:
> Yes, but the condition of the /data/ is such that it will not recurse.
> 
> A pure "can this function call that function" analysis ignoring the
> state of the data will say this will infinitely recuse.  Include
> the data, and you'll find it has a very definite recursion limit.

Is the data verified?

Re: Worst recursion in the kernel

[David Hinds]

On Wed, Dec 03, 2003 at 03:08:32PM -0800, Mike Fedyk wrote:
> On Wed, Dec 03, 2003 at 10:57:43PM +0000, Russell King wrote:
> > Yes, but the condition of the /data/ is such that it will not recurse.
> > 
> > A pure "can this function call that function" analysis ignoring the
> > state of the data will say this will infinitely recuse.  Include
> > the data, and you'll find it has a very definite recursion limit.
> 
> Is the data verified?

Russell is using "data" loosely.  Basically the logic goes like this:

read_cis_mem():
  if sys_start is NULL then call validate_mem()

validate_mem():
  set sys_start
  call stuff that calls read_cis_mem()

so the functions do not require consistency of any external program
data to avoid recursion.

-- Dave

Re: Worst recursion in the kernel

[Jörn Engel]

On Wed, 3 December 2003 22:57:43 +0000, Russell King wrote:
> 
> Yes, but the condition of the /data/ is such that it will not recurse.

Yes, so?

> A pure "can this function call that function" analysis ignoring the
> state of the data will say this will infinitely recuse.  Include
> the data, and you'll find it has a very definite recursion limit.

That is what I do.  My program takes hints saying "this recursion can
only loop n times".  But I don't want to add semantic checking of the
source itself, so a human has to give the hint.  Also, the human has
to uniquely hint at a single recursion.

If you accept this approach, there is no way to deal with multiple
linked recursions like this:
a->b->c->d
      `->b

The human would have to say something like "the big recursion can only
happen five times, unless the short recursion from c to b happened.
In this case...".  No thanks.

In fact, most recursions in the kernel are functions calling itself
again, there are just a few over several functions.  So I honestly
wonder if recursion over multiple functions should be handled by my
program at all, or if I should just warn when seeing them.

There might be valid cases for two or three functions involved, so I
am not sure yet.  But I sure as hell won't handle those cases before
seeing a valid use first and the one causing this thread sure isn't.

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: Worst recursion in the kernel

[Martin Waitz]

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

hi :)

On Wed, Dec 03, 2003 at 10:57:43PM +0000, Russell King wrote:
> Yes, but the condition of the /data/ is such that it will not recurse.
> 
> A pure "can this function call that function" analysis ignoring the
> state of the data will say this will infinitely recuse.  Include
> the data, and you'll find it has a very definite recursion limit.

but it makes sense to restrucure the code to make it more
readable/understandable even if it can be proven that the code is
correct


-- 
CU,		  / Friedrich-Alexander University Erlangen, Germany
Martin Waitz	//  Department of Computer Science 3       _________
______________/// - - - - - - - - - - - - - - - - - - - - ///
dies ist eine manuell generierte mail, sie beinhaltet    //
tippfehler und ist auch ohne grossbuchstaben gueltig.   /

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: Worst recursion in the kernel

[Russell King]

On Thu, Dec 04, 2003 at 04:08:46PM +0100, Martin Waitz wrote:
> hi :)
> 
> On Wed, Dec 03, 2003 at 10:57:43PM +0000, Russell King wrote:
> > Yes, but the condition of the /data/ is such that it will not recurse.
> > 
> > A pure "can this function call that function" analysis ignoring the
> > state of the data will say this will infinitely recuse.  Include
> > the data, and you'll find it has a very definite recursion limit.
> 
> but it makes sense to restrucure the code to make it more
> readable/understandable even if it can be proven that the code is
> correct

Oddly that's what I have been doing, but we've run out of time to
completely eliminate the recursions in PCMCIA before the 2.6 brakes
were turned on.  Sure, if someone wants to try submitting a PCMCIA
rewrite to Linus right now and wants to receive Linus' flames, go
ahead. 8)

So, for the time being, live with the fact that current automated
program analysis detects the recusion.  Inteligent human examination
will tell you that it can't infinitely recurse.

-- 
Russell King
 Linux kernel    2.6 ARM Linux   - http://www.arm.linux.org.uk/
 maintainer of:  2.6 PCMCIA      - http://pcmcia.arm.linux.org.uk/
                 2.6 Serial core

Re: Worst recursion in the kernel

[Jörn Engel]

On Thu, 4 December 2003 18:40:32 +0000, Russell King wrote:
> 
> Oddly that's what I have been doing, but we've run out of time to
> completely eliminate the recursions in PCMCIA before the 2.6 brakes
> were turned on.  Sure, if someone wants to try submitting a PCMCIA
> rewrite to Linus right now and wants to receive Linus' flames, go
> ahead. 8)
> 
> So, for the time being, live with the fact that current automated
> program analysis detects the recusion.  Inteligent human examination
> will tell you that it can't infinitely recurse.

Thank you!  "Not yet" is perfectly acceptable to me. :)

Jörn

-- 
Don't worry about people stealing your ideas. If your ideas are any good,
you'll have to ram them down people's throats.
-- Howard Aiken quoted by Ken Iverson quoted by Jim Horning quoted by
   Raph Levien, 1979

Re: Worst recursion in the kernel

[David Hinds]

On Wed, Dec 03, 2003 at 08:04:40PM +0100, Jörn Engel wrote:
> 
> You are right, verify_cis_cache() does not belong into the list.
> Gotta see where that bug comes from.  set_cis_map() is correct,
> though.  It does call validate_mem(), at least in my copy of
> 2.6.0-test11:

Oh, so it does; I was looking at the older version I wrote.

> I have no better alternative availlable right now, but there must be
> another way.  Maybe something like this:
> 
> read_cis_mem() {
> 	if (__read_cis_mem() != -EAGAIN)
> 		return;
> 	validate_mem();
> 	__read_cis_mem();
> }

The issue is that validate_mem() doesn't need to use read_cis_mem's
functionality directly (so it can't just be modified to use the __*
form).  It calls other stuff, which calls other stuff, which
eventually calls read_cis_mem(), and all that other stuff is used by
other callers.  So there isn't an obvious place to insert this
bifurcation.

> Not sure about you, but it would make my program much happier.  If you
> look at the relevant part of the call graph (below), you will notice
> that inv_probe() alone is already recursive.  Having multiple
> recursions to worry about in the same function is where the problem
> stops being difficult and becomes impossible.

inv_probe() is pretty comprehensible, it calls itself directly, in
order to traverse a short linked list from tail to head.

-- Dave

Re: Worst recursion in the kernel

[Jörn Engel]

On Wed, 3 December 2003 15:08:04 -0800, David Hinds wrote:
> 
> The issue is that validate_mem() doesn't need to use read_cis_mem's
> functionality directly (so it can't just be modified to use the __*
> form).  It calls other stuff, which calls other stuff, which
> eventually calls read_cis_mem(), and all that other stuff is used by
> other callers.  So there isn't an obvious place to insert this
> bifurcation.

This explanation sounds a bit like "that mess is too fragile, there is
no way to touch it without everything falling apart."  Just one more
reason to change it and make it more maintainable.  I agree, it is a
big piece of work waiting for 2.7 to open up, but your only excuse not
to do it eventually is lack of time. ;)

> inv_probe() is pretty comprehensible, it calls itself directly, in
> order to traverse a short linked list from tail to head.

Sounds like a valid candidate for <list.h>, but if you can prove the
list to always be short, it is ok.

Jörn

-- 
Write programs that do one thing and do it well. Write programs to work
together. Write programs to handle text streams, because that is a
universal interface. 
-- Doug MacIlroy