Re: Using qsort(3) in the kernel

["Steven M. Bellovin" <smb%cs.columbia.edu@localhost>]

On Mon, 17 Nov 2008 01:00:18 +0100
Johnny Billquist <bqt%softjar.se@localhost> wrote:

> Martin S. Weber wrote:
> > On Sun, Nov 16, 2008 at 08:34:38PM +0100, Anders Magnusson wrote:
> >> Martin S. Weber wrote:
> >>> On Sun, Nov 16, 2008 at 01:41:34PM -0500, Steven M. Bellovin
> >>> wrote:
> >>>> (...)
> >>>> The kernel stack is limited in size; if the recursion is too
> >>>> deep, it can exceed that limit.  It's only safe to do recursion
> >>>> if you can (a) guarantee the maximum depth; and (b) show that
> >>>> for all uses of this routine, the total stack consumption will
> >>>> be low enough.
> >>> Doesn't gcc 4 in the meantime finally support that 70s technique
> >>> of tail call optimization? Thought I had read about that
> >>> somewhen.. could be mistaken tho.
> >>>
> >> Yes, gcc does, but that doesn't mean that it can use it for the
> >> qsort recursions. Not all recursive calls can be optimized away.
> > 
> > Yes that's obvious. Given my background in functional languages I'm
> > just intrigued by the statement 'recursive is bad, imperative
> > for/while loops are good'.
> 
> I think that was reading a bit much into it. What was said was that 
> recursion is potentially problematic if you have very little stack
> space. That's not the same as "recursive is bad".
> 
> Or atleast that's how I read it.
> 
Agreed, but we sometimes run very close to the limit.  I've had kernel
stack space problems in the past; we don't need to create situations
where some people will run into troubles that the developer who added
some code couldn't anticipate or test.


                --Steve Bellovin, http://www.cs.columbia.edu/~smb