lkml.org 
[lkml]   [2003]   [Dec]   [4]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectRe: Worst recursion in the kernel
    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/

    \
     
     \ /
      Last update: 2005-03-22 13:59    [W:3.380 / U:0.436 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site