Skip to contentSkip to conversation

Worst recursion in the kernel

DISCUSSION Jörn Engel 5 participants 12 messages Dec 3, 2003 – Dec 4, 2003

lore
Share & tools
lore
#0 lore raw

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

Signature · 3 lines
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
#1 lore raw
Quoted 20 lines · 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
Quoted 4 lines

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().

Quoted 4 lines

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

#2 lore raw
Quoted 21 lines · David Hinds
Quoted 15 lines · Jörn Engel

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
Quoted 4 lines

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.

Quoted 5 lines

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.

Quoted 6 lines
Quoted 4 lines

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.

Quoted 7 lines

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.

Quoted 5 lines

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

Signature · 84 lines
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
#3 lore raw
Quoted 14 lines · Jörn Engel

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);
	...
Quoted 4 lines

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.

Signature · 4 lines
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
#4 lore raw
Quoted 5 lines · Russell King

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?

#5 lore raw
Quoted 8 lines · Mike Fedyk
Quoted 5 lines · Russell King

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

#6 lore raw
In reply to Russell King
Quoted 2 lines · Russell King

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

Yes, so?

Quoted 3 lines

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

Signature · 3 lines
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
#7 lore raw
In reply to Russell King

hi :)

Quoted 5 lines · Russell King

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

Signature · 5 lines
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.   /
#8 lore raw
Quoted 5 lines · Martin Waitz

hi :)

Quoted 2 lines · Russell King

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

Quoted 7 lines
Quoted 3 lines

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.

Signature · 4 lines
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
#9 lore raw
Quoted 10 lines · Russell King

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

Signature · 4 lines
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
#10 lore raw
In reply to Jörn Engel
Quoted 5 lines · Jörn Engel

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.

Quoted 9 lines

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.

Quoted 5 lines

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

#11 lore raw
Quoted 7 lines · David Hinds

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. ;)

Quoted 2 lines

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

Signature · 4 lines
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