Re: Worst recursion in the kernel

[Jörn Engel]

On Wed, 3 December 2003 22:57:43 +0000, Russell King wrote:
> 
> Yes, but the condition of the /data/ is such that it will not recurse.

Yes, so?

> 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

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