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
-
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/