Does the linux kernel (specifically 2.6 onwards) have any recursive function?

Question

Given the limited fixed size of kernel stack, my guess is that although theoretically we might have a recursive function if its recursion doesn't go too deep, pragmatism would suggest to do away with recursive functions all together, to be on a safer side. After all, too much of recursion can result in wiping off the *thread_info_t* struct and a resultant kernel panic

Answer 1

Yes!

Maybe some of the recurive calls are either documented or part of function names? Then, a find/grep should reveal them. Here is a command to do it:

find /usr/src/linux/ -name "*.c" -exec grep recursive {} ";" -ls 

Piping this through | wc -l gives me 270, which is, since -ls prints one additional line per file, at least 135 files+functions.

Let's have a look at the first match:

/usr/src/linux/fs/jfs/jfs_dmap.c

The match is a comment:

• if the adjustment of the dmap control page, itself, causes its
• root to change, this change will be bubbled up to the next dmap
• control level by a recursive call to this routine, specifying
• the new root value and the next dmap control page level to
• be adjusted.

in front of the method

static int
dbAdjCtl(struct bmap * bmp, s64 blkno, int newval, int alloc, int level)

and in fact, line 2486 and neighbours are:

if (dcp->stree[ROOT] != oldroot) {
    /* are we below the top level of the map.  if so,
     * bubble the root up to the next higher level.
     */
    if (level < bmp->db_maxlevel) {
        /* bubble up the new root of this dmap control page to
         * the next level.
         */
        if ((rc =
             dbAdjCtl(bmp, blkno, dcp->stree[ROOT], alloc,
                  level + 1))) {
            /* something went wrong in bubbling up the new
             * root value, so backout the changes to the
             * current dmap control page.
             */

Since the question was, whether there is any recursive function, we don't have to visit the next 135 or more matches or search for not explicitly mentioned recursions. The answer is

Yes!

Answer 2

The Linux kernel coding style does not prohibit recursive functions.

You do need to be careful and not overflow the stack, but that caution is not specific to recursive functions. Don't gratuitously use recursion when a loop would do, and keep in mind that you and the functions calling you only get 8kB total, but occasionally recursion is the right tool.

Answer 3

Current kernels have over 10 million lines of code. I'm convinced somewhere some of all these lines of code are recursive. Recursive programming is very powerful and you don't have to run many levels deep to make it pay.