Re: Using qsort(3) in the kernel

[Matt Thomas <matt%3am-software.com@localhost>]

On Nov 16, 2008, at 3:58 PM, Johnny Billquist wrote:

> 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.
>
> Or put another way: not all recursions are tail recursions.

And not all architectures can do tail call optimizations...