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
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/