OSDev.org

The Place to Start for Operating System Developers
It is currently Thu Mar 28, 2024 8:56 am

All times are UTC - 6 hours




Post new topic Reply to topic  [ 20 posts ]  Go to page 1, 2  Next
Author Message
 Post subject: The case for lack of recursive functions in kernel
PostPosted: Wed Oct 07, 2015 3:46 pm 
Offline
Member
Member

Joined: Sat Oct 16, 2010 3:38 pm
Posts: 587
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).


Top
 Profile  
 
 Post subject: Re: The case for lack of recursive functions in kernel
PostPosted: Wed Oct 07, 2015 7:13 pm 
Offline
Member
Member

Joined: Mon Oct 11, 2010 11:37 pm
Posts: 52
Location: Milwaukee, Wisconsin
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?

_________________
Microsoft is over if you want it.


Top
 Profile  
 
 Post subject: Re: The case for lack of recursive functions in kernel
PostPosted: Wed Oct 07, 2015 10:10 pm 
Offline
Member
Member

Joined: Thu Mar 25, 2010 11:26 pm
Posts: 1801
Location: Melbourne, Australia
This piece of code form the wiki http://wiki.osdev.org/PCI_IDE_Controller might tempt people to use recursion.

Code:
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.

_________________
If a trainstation is where trains stop, what is a workstation ?


Top
 Profile  
 
 Post subject: Re: The case for lack of recursive functions in kernel
PostPosted: Thu Oct 08, 2015 5:23 am 
Offline
Member
Member
User avatar

Joined: Wed Oct 18, 2006 3:45 am
Posts: 9301
Location: On the balcony, where I can actually keep 1½m distance
gerryg400 wrote:
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.

_________________
"Certainly avoid yourself. He is a newbie and might not realize it. You'll hate his code deeply a few years down the road." - Sortie
[ My OS ] [ VDisk/SFS ]


Top
 Profile  
 
 Post subject: Re: The case for lack of recursive functions in kernel
PostPosted: Thu Oct 08, 2015 1:47 pm 
Offline
Member
Member

Joined: Sat Oct 16, 2010 3:38 pm
Posts: 587
Combuster wrote:
gerryg400 wrote:
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.


Top
 Profile  
 
 Post subject: Re: The case for lack of recursive functions in kernel
PostPosted: Thu Oct 08, 2015 7:22 pm 
Offline
Member
Member

Joined: Mon Jan 03, 2011 6:58 pm
Posts: 283
mariuszp wrote:
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.

mariuszp wrote:
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


Top
 Profile  
 
 Post subject: Re: The case for lack of recursive functions in kernel
PostPosted: Fri Oct 09, 2015 1:57 am 
Offline
Member
Member

Joined: Tue Mar 04, 2014 5:27 am
Posts: 1108
tjmonk15 wrote:
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?


Top
 Profile  
 
 Post subject: Re: The case for lack of recursive functions in kernel
PostPosted: Fri Oct 09, 2015 1:58 am 
Offline
Member
Member
User avatar

Joined: Sat Jan 15, 2005 12:00 am
Posts: 8561
Location: At his keyboard!
Hi,

mariuszp wrote:
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

_________________
For all things; perfection is, and will always remain, impossible to achieve in practice. However; by striving for perfection we create things that are as perfect as practically possible. Let the pursuit of perfection be our guide.


Top
 Profile  
 
 Post subject: Re: The case for lack of recursive functions in kernel
PostPosted: Fri Oct 09, 2015 2:26 am 
Offline
Member
Member
User avatar

Joined: Sat Mar 31, 2012 3:07 am
Posts: 4591
Location: Chichester, UK
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.


Top
 Profile  
 
 Post subject: Re: The case for lack of recursive functions in kernel
PostPosted: Fri Oct 09, 2015 4:05 am 
Offline
User avatar

Joined: Fri Oct 09, 2015 3:57 am
Posts: 1
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.

_________________
# whoami
SEGMENTATION FAULT
#


Top
 Profile  
 
 Post subject: Re: The case for lack of recursive functions in kernel
PostPosted: Fri Oct 09, 2015 5:24 am 
Offline
Member
Member
User avatar

Joined: Sat Mar 31, 2012 3:07 am
Posts: 4591
Location: Chichester, UK
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.


Top
 Profile  
 
 Post subject: Re: The case for lack of recursive functions in kernel
PostPosted: Fri Oct 09, 2015 6:20 am 
Offline
Member
Member

Joined: Mon Apr 09, 2007 12:10 pm
Posts: 775
Location: London, UK
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.

_________________
Tysos | rpi-boot


Top
 Profile  
 
 Post subject: Re: The case for lack of recursive functions in kernel
PostPosted: Fri Oct 09, 2015 6:52 am 
Offline
Member
Member
User avatar

Joined: Sat Jan 15, 2005 12:00 am
Posts: 8561
Location: At his keyboard!
Hi,

jnc100 wrote:
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

_________________
For all things; perfection is, and will always remain, impossible to achieve in practice. However; by striving for perfection we create things that are as perfect as practically possible. Let the pursuit of perfection be our guide.


Top
 Profile  
 
 Post subject: Re: The case for lack of recursive functions in kernel
PostPosted: Fri Oct 09, 2015 7:19 am 
Offline
Member
Member

Joined: Mon Apr 09, 2007 12:10 pm
Posts: 775
Location: London, UK
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.

_________________
Tysos | rpi-boot


Top
 Profile  
 
 Post subject: Re: The case for lack of recursive functions in kernel
PostPosted: Fri Oct 09, 2015 9:02 am 
Offline
Member
Member
User avatar

Joined: Fri Apr 03, 2015 9:41 am
Posts: 492
tjmonk15 wrote:
mariuszp wrote:
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.

mariuszp wrote:
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.

_________________
Developing U365.
Source:
only testing: http://gitlab.com/bps-projs/U365/tree/testing

OSDev newbies can copy any code from my repositories, just leave a notice that this code was written by U365 development team, not by you.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 20 posts ]  Go to page 1, 2  Next

All times are UTC - 6 hours


Who is online

Users browsing this forum: No registered users and 16 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group