Worst recursion in the kernel

["Jörn Engel" <joern@wohnheim.fh-wedel.de>]

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