Bill Studenmund wrote:

>On Thu, Nov 24, 2005 at 12:41:59AM +0100, Martin Husemann wrote:
>  
>
>>On Wed, Nov 23, 2005 at 02:51:12PM -0800, Bill Studenmund wrote:
>>    
>>
>>>My concern is that with some dependnecy orders, we can end
>>>up gobbling up a lot of kernel stack and blow it, whereas with another
>>>order order the exact same modules load with little stack.
>>>      
>>>
>>I like the coded-dependency/init-at-first-use aproach. It also sounds
>>easy to implement without major changes in our tree, on a subsystem-
>>by-subsytem basis.
>>
>>I don't think the kernel stack and unpredictable initialization call
>>stacks will be a big problem, since most initializations will happen
>>early at certain events
>>    
>>
>
>How does that matter?
>
>The problem I was discussing was that A can trigger B can trigger C can
>trigger D. The only ways to prevent that are to: 1) not let dependency
>chains get that big, 2) manually call inits on some often-needed systems, 
>or 3) sort them.
>
>The problem is we have from 8k to 16k of stack. That should be more than 
>enough for one routine, and probably two. But if we nest a few routines 
>and we already had a few routines in progress, we can run out.
>
>Sure, we aren't going to do this when we are in the bottom of some deep 
>call path. But we can still smash the stack to bits.
>
>  
>
>> - during outconfig (network driver attaches -> networking is initialized)
>> - during certain syscalls (mount_msdos initializes msdos file system)
>>
>>and it can be pushed even further - like having IPv6 in the kernel but
>>not initializing it untill the first IPv6 route is added (or interface
>>address assigned; which then would, of course, cause link local addresses
>>to pop up on all interfaces). I'm not sure we want to go there, but
>>the flexibility sounds like a good think to have.
>>    
>>
>
>I like the on-demand aspect of the above. I just don't think that gets us 
>out of the way of worrying about nesting initialization.
>  
>
As I suggested before, if the initialization is not done explicitly by
the caller, but rather by some master function that can walk the the
dependency tree by examining some dependency list "off the stack", then
it isn't a problem.

Let me give a concrete example:

A depends on B, B depends on C and on D, and D depends on E.

The first time someone tries to access "A", by some magic the kernel
discovers it needs to initialize A.  But before it actually *calls* any
initialization in A, it looks at As dependency list and sees A needs B.

So then it looks it B's dependency list.  Sees C and D are required,
etc. etc.

This is tree walking without using a call stack or recursion.  But you
might need a FIFO structure to keep track of where you were.

Or, the "satisfy dependents" routine can be recursive, because frankly
it never needs to go very deep.  (The module initialization is always a
leaf routine.)  Here's a sample call stack:

satisfy(A) ->
    satisfy(B) ->
       satisfy(C) ->
          satisfy(E) ->
              init(E)
          init(C)
       satisfy(D)
       .. E already loaded
           init(D)
       init(B)
    init(A)

Notice that the meaty "init" routines are never nested.  If you assume
that only a few bytes of stack space are needed for the recursion of
satisfy(), then the total overhead of the above stack is only a couple
of words larger than that needed by init().

And as I mentioned, if that still isn't enough stack space, you can
unroll the recursion and track the "stack" using a FIFO data structure
and normal iterative programming.  (This moves the "stack" as it were,
into the heap.)

    -- Garrett
   

>Take care,
>
>Bill
>  
>


-- 
Garrett D'Amore                          http://www.tadpolecomputer.com/
Sr. Staff Engineer          Extending the Power of 64-bit UNIX Computing
Tadpole Computer, Inc.                             Phone: (951) 325-2134