Worst recursion in the kernel
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_cacheExplanation: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
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_cachecallsread_cis_mem, which callsset_cis_map, which call ..., which callsread_cis_cache, which finally callsverify_cis_cacheagain.
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
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_cacheQuoted 4 lines
Explanation:
verify_cis_cachecallsread_cis_mem, which callsset_cis_map, which call ..., which callsread_cis_cache, which finally callsverify_cis_cacheagain.
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 thinkset_cis_map()should besetup_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 tovalidate_mem()which first does that thing, and then does some stuff that leads toread_cis_mem()being called again. Whenread_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
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 callvalidate_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 coreQuoted 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?
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
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
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. /
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 coreQuoted 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
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 callvalidate_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
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 callsread_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