The case for lack of recursive functions in kernel

[mariuszp]

I don't know how many people have come up with this but here's a thought/suggestions:

NEVER write any recursive functions in your kernels. By recursive I mean functions that call themselves an amount of times that cannot be determined at compile-time, or does not have a compile-time absolute maximum.

Since any function in the kernel could be directly or indirectly called by a userspace system call, it would be possible to pass a combination of arguments that would cause a stack overflow in the kernel!

What are your thought about this? Perhaps we could put this on some kind of wiki 'suggestions' page (if one already exists with this suggestion, i'm sorry, i did not see it).

[CelestialMechanic]

This sounds like sensible advice for limiting recursive functions in general. Recursive functions have their uses, but I can't think of any in the context of an operating system kernel. Can you give an example where someone might be tempted to use a recursive function in a kernel?

[gerryg400]

This piece of code form the wiki http://wiki.osdev.org/PCI_IDE_Controller might tempt people to use recursion.

Code: Select all

void ide_write(unsigned char channel, unsigned char reg, unsigned char data) {
    if (reg > 0x07 && reg < 0x0C)
        ide_write(channel, ATA_REG_CONTROL, 0x80 | channels[channel].nIEN);
    if (reg < 0x08)
        outb(channels[channel].base  + reg - 0x00, data);
    else if (reg < 0x0C)
        outb(channels[channel].base  + reg - 0x06, data);
    else if (reg < 0x0E)
        outb(channels[channel].ctrl  + reg - 0x0A, data);
    else if (reg < 0x16)
        outb(channels[channel].bmide + reg - 0x0E, data);
    if (reg > 0x07 && reg < 0x0C)
        ide_write(channel, ATA_REG_CONTROL, channels[channel].nIEN);
}

One place where recursion might be used in a kernel is in symlink resolution.

[Combuster]

One place where recursion might be used in a kernel is in symlink resolution.

But you don't want to program that as a recursion.

[mariuszp]

One place where recursion might be used in a kernel is in symlink resolution.

But you don't want to program that as a recursion.

Well, you could implement that using recursion, for the simple reason that there is a symlink limit, so there is an absolute maximum amount of stack space the function will use, so will not cause a stack overflow if you allocate enough stack space.

[FallenAvatar]

I don't know how many people have come up with this but here's a thought/suggestions:

NEVER write any recursive functions in your kernels. By recursive I mean functions that call themselves an amount of times that cannot be determined at compile-time, or does not have a compile-time absolute maximum.

Since any function in the kernel could be directly or indirectly called by a userspace system call, it would be possible to pass a combination of arguments that would cause a stack overflow in the kernel!

What are your thought about this? Perhaps we could put this on some kind of wiki 'suggestions' page (if one already exists with this suggestion, i'm sorry, i did not see it).

There is zero issue with using recursion. There are plenty of issues with programmers who don't know what they are doing using recursion.

Well, you could implement that using recursion, for the simple reason that there is a symlink limit, so there is an absolute maximum amount of stack space the function will use, so will not cause a stack overflow if you allocate enough stack space.

Until someone points a symlink to a symlink that points to the first symlink (circular symlinks)...

- Monk

[alexfru]

Until someone points a symlink to a symlink that points to the first symlink (circular symlinks)...

There are multiple problems here.

First, deep recursion is dangerous not only because it can potentially overflow the stack, but because you don't quite know when it will. The reason is that the amount of stack used for every call depends a lot on the code and on how the compiler optimizes said code and there's no way to ask the compiler about the size and take feed that information in an automatic manner back into the code (linker scripts, definitions of low level system structures and such). So, you'll need to find it out experimentally. But again, should you change the code or the compiler, you need to do it again.

Second, while symlinks seem be an obvious thing to take care of w.r.t. loops, loops may occur in pretty much any hierarchical file system simply because many parts of it are interlinked. A corrupt file system without any symlinks will hang or crash the driver or the OS if there's no mechanism to validate the FS and detect and handle loops. How many of you guys have actually implemented loop detection in your file systems?

[Brendan]

Hi,

I don't know how many people have come up with this but here's a thought/suggestions:

NEVER write any recursive functions in your kernels. By recursive I mean functions that call themselves an amount of times that cannot be determined at compile-time, or does not have a compile-time absolute maximum.

The main constraint is typically ensuring that your kernel stack/s are large enough for "worst case".

If you use too much kernel stack without recursion your kernel will probably crash; and if you don't use much kernel stack with recursion (e.g. potentially due to "tail call optimisation" done by the compiler, or even just by limiting recursion depth) then that's not a problem at all.


Cheers,

Brendan

[iansjack]

Or you could just allow your kernel stack to expand dynamically (although you would obviously need some check that it wasn't doing so indefinitely) and recover stack space when it is no longer needed.

It seems to me that if you don't use recursion you still have the potential problem of infinite loops so you always need some sort of check to guard against that.

[weland]

True -- however, an infinite loop doesn't require infinite stack space. It's hard to exploit an infinite loop to mount a meaningful stack-related attack. Even with support for dynamically growing the stack, there's a non-zero chance that it'll eventually be eschewed.

Frankly, as long as the function works and checks are in place to ensure that a) the call chain doesn't go on forever and b) the stack can't outgrow its limit, I see no problem with it. E.g. if you're doing something on a tree that's never going to be more than three or four levels high, the gain in readability is probably worth it.

But it's usually a red flag as far as I'm concerned. It's one more thing to check for in a code review. I tend to avoid writing recursive functions unless I have a very good reason to do it and am able to guarantee a) and b) above. They're pretty hard to guarantee sometimes, and I don't think the effort is worth it.

[iansjack]

It should be far easier to trust a kernel function not to lead to a runaway stack, and to build in the appropriate protection, than in a userspace program.

An infinite loop resolving, for example, a symbolic link is not something to be desired in a kernel. Without careful design it is possible that it will lock up the whole system.

[jnc100]

Bear in mind it may not always be possible to completely eliminate all recursive functions from kernel code. For example, if you use other libraries in your kernel (things like ACPICA, malloc implementations and firmware routines spring to mind) then they may do this. If you will at some point allow 3rd party drivers, then they may do the same. I'd advise that (along with trying to eliminate such possibilities in your own code) you concentrate more on recovery from when kernel stack overflows eventually do happen: do you halt the entire kernel? just the process currently running (if using per-task kernel stacks)? If using a microkernel do you handle it gracefully and restart the server whilst informing the client that it needs to rerequest the data somehow?

As to infinite loops, then the specific solution is to never allow the same path element to be passed twice in the parsing (after first resolving all parent references ('..' etc)). The more general solution is to have a timeout on all kernel functions, with a default 'TIMEOUT' return if nothing happens within a pre-set period. Alternatively have all kernel functions pre-emptible, so that only a single process if affected.

Regards,
John.

[Brendan]

Hi,

Bear in mind it may not always be possible to completely eliminate all recursive functions from kernel code. For example, if you use other libraries in your kernel (things like ACPICA, malloc implementations and firmware routines spring to mind) then they may do this. If you will at some point allow 3rd party drivers, then they may do the same. I'd advise that (along with trying to eliminate such possibilities in your own code) you concentrate more on recovery from when kernel stack overflows eventually do happen: do you halt the entire kernel? just the process currently running (if using per-task kernel stacks)? If using a microkernel do you handle it gracefully and restart the server whilst informing the client that it needs to rerequest the data somehow?

For a micro-kernel; if you need to worry about this at all then you're doing it wrong..

For a monolithic kernel; the problem with recovery (and/or schemes to extend kernel stack) is that if a normal/innocent page fault occurs but the CPU doesn't have enough kernel stack to start the page fault handler, you get second page fault that trashes the first page fault's CR2. This leaves you in the double fault exception handler wondering what went wrong, with no possible way to fix the original/first page fault. The only way around that is to make sure nothing in the kernel benefits from any virtual memory management tricks (which cripples the kernel), and also to make sure nothing crashes and causes page fault when kernel stack is almost full (and if you can't guarantee that third party code won't overflow the kernel stack then you can't guarantee that third party code won't crash at the wrong time either).

Basically; it's a monolithic kernel so you should probably just give up and go directly to kernel panic every time the USB coffee cup warmer driver has a minor hiccup (or any of the millions of other bugs that will be scattered everywhere occurs).


Cheers,

Brendan

[jnc100]

Obviously I was offering solutions for various different kernel types.

As regards the specific issue of not having enough stack for the page fault handler to run, then at least on x86_64 this can be worked around with the IST mechanism.

Regards,
John.

[osdever]

I don't know how many people have come up with this but here's a thought/suggestions:

NEVER write any recursive functions in your kernels. By recursive I mean functions that call themselves an amount of times that cannot be determined at compile-time, or does not have a compile-time absolute maximum.

Since any function in the kernel could be directly or indirectly called by a userspace system call, it would be possible to pass a combination of arguments that would cause a stack overflow in the kernel!

What are your thought about this? Perhaps we could put this on some kind of wiki 'suggestions' page (if one already exists with this suggestion, i'm sorry, i did not see it).

There is zero issue with using recursion. There are plenty of issues with programmers who don't know what they are doing using recursion.

Well, you could implement that using recursion, for the simple reason that there is a symlink limit, so there is an absolute maximum amount of stack space the function will use, so will not cause a stack overflow if you allocate enough stack space.

Until someone points a symlink to a symlink that points to the first symlink (circular symlinks)...

- Monk

Just make if(symlink.pointsTo->pointsTo!=symlink)return; and be happy.