Re: Worst recursion in the kernel

From: Jörn Engel (joern_at_wohnheim.fh-wedel.de)
Date: 12/04/03

  • Next message: Jens Axboe: "Re: Errors and later panics in 2.6.0-test11." 
    Date:	Thu, 4 Dec 2003 15:14:40 +0100
To: David Hinds <dhinds@sonic.net>, linux-kernel@vger.kernel.org

    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@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/
  • Next message: Jens Axboe: "Re: Errors and later panics in 2.6.0-test11."

    Relevant Pages

    • Re: Simple recursion problem. Need help.
      ... I *did* use google and other search engines to find out anything even a HINT of how i'm supposed to solve this problem. ... this isn't a typical java problem. ... this is a question about recursion. ... asking anyone here to do my homework, as Thomas seems to be implying. ...
      (comp.lang.java.programmer)
    • Re: empty $SSH_CLIENT
      ... > $ cat ~.ssh/authorized_keys ... > Anyone a hint? ... It's bash: ... Recursion: see recursion ...
      (comp.security.ssh)
    • Re: empty $SSH_CLIENT
      ... >> When using an rsa login that runs a command from the ... >> Anyone a hint? ... > It's bash: ... Recursion: see recursion ...
      (comp.security.ssh)
    • Re: missing library
      ... -Bdynamic followed by libraries to be dynamically linked. ... Why don't you try it first (Hint: your advice doesn't work for libstdc++). ... In order to understand recursion you must first understand recursion. ...
      (comp.os.linux.development.system)
    • Re: oops with dual xeon 2.8ghz 4gb ram +smp, software raid, lvm, and xfs
      ... >> depth problems with stacked block devices, ... > around sticky situations. ... Recursion is like that (... ... send the line "unsubscribe linux-kernel" in ...
      (Linux-Kernel)