OT: Re: not enough kernel stack question

> ----------

From: Dejan Maksimovic[SMTP:xxxxx@ptt.yu]
Reply To: File Systems Developers
Sent: Wednesday, May 23, 2001 1:42 AM
To: File Systems Developers
Subject: [ntfsd] Re: not enough kernel stack question

> > Not each recursive can be changed to iterative (linear) algorithm,
but
> Sorry, but every recursive algorithm can be changed to iterative.

How? Without reallocating a dynamic array of stacked values, of
course-:wink:
Consider a string matching algorithm, used by DOS. What are the chances to
change it to iterative?

This is a bit of topic… I believe it can be proven mathematical way and if
I remember correctly, it isn’t very complicated. Maybe somebody will know
the link or a book with more info. The most trivial way would be an array
with slots for ‘stack’ variables and the loop which simulates recursion over
this ‘stack’. With some improvements and clever use of variables it can be
much more efficient than recursion way.

How to do it depends on the concrete case and I haven’t said it is easy or
practical, only it is always possible :slight_smile:

Best regards,

Michal Vodicka
Veridicom
(RKK - Skytale)
[WWW: http://www.veridicom.com , http://www.skytale.com]


You are currently subscribed to ntfsd as: $subst(‘Recip.EmailAddr’)
To unsubscribe send a blank email to leave-ntfsd-$subst(‘Recip.MemberIDChar’)@lists.osr.com

> This is a bit of topic… I believe it can be proven mathematical way and if

I remember correctly, it isn’t very complicated. Maybe somebody will know
the link or a book with more info. The most trivial way would be an array
with slots for ‘stack’ variables and the loop which simulates recursion over
this ‘stack’. With some improvements and clever use of variables it can be
much more efficient than recursion way.

Hmm, I guess I understand you. If you allocate a big enough “stack”, you can
push on it. Something I wanted to avoid-:wink:

How to do it depends on the concrete case and I haven’t said it is easy or
practical, only it is always possible :slight_smile:

I’ve done an iterative algorithm for traversing a directory tree, but I use
a local array of strings to store the last visited directory.
Something like this can be done, the Q is how efficient it is.


Kind regards, Dejan M. CEO Alfa Co. www.alfaunits.co.yu and www.register.co.yu
E-mail : xxxxx@ptt.yu, xxxxx@register.co.yu and xxxxx@alfaunits.co.yu
ICQ# : 56570367
Professional file&system related components and libraries for Win32 developers.
Alfa File Monitor - #1 file monitoring system for Win32 developers.
Alfa File Protector - #1 file protection and hiding system for Win32 developers.

Alfa Units - #1 file and system handling units for Delphi.


You are currently subscribed to ntfsd as: $subst(‘Recip.EmailAddr’)
To unsubscribe send a blank email to leave-ntfsd-$subst(‘Recip.MemberIDChar’)@lists.osr.com

> ----------

From: Dejan Maksimovic[SMTP:xxxxx@ptt.yu]
Reply To: File Systems Developers
Sent: Wednesday, May 23, 2001 2:48 AM
To: File Systems Developers
Subject: [ntfsd] Re: OT: Re: not enough kernel stack question

> This is a bit of topic… I believe it can be proven mathematical way
and if
> I remember correctly, it isn’t very complicated. Maybe somebody will
know
> the link or a book with more info. The most trivial way would be an
array
> with slots for ‘stack’ variables and the loop which simulates recursion
over
> this ‘stack’. With some improvements and clever use of variables it can
be
> much more efficient than recursion way.

Hmm, I guess I understand you. If you allocate a big enough “stack”,
you can
push on it. Something I wanted to avoid-:wink:

As I said, it was trivial example. But you can’t avoid it in principle,
naturally recursive algorithm needs an info about ‘backtrack’. You can only
make clever data representation which gives you this info (but takes more
memory). For example, if you have one way linked binary tree, you need the
stack or array which saves the way from the root to actual node to traverse
it. If you have double linked tree, all you need is the actual node because
there is a pointer to parent node. If you are interested about it, take some
book about graph theory, there should be a lot of examples.

I’ve done an iterative algorithm for traversing a directory tree, but
I use
a local array of strings to store the last visited directory.
Something like this can be done, the Q is how efficient it is.

What means efficient? Fast and memory hogger or slow which doesn’t consume
memory? If the stack is sparse resource, efficient algorithm must not
consume it too much. I want to say algorithm should be chosen according to
actual conditions.

Best regards,

Michal Vodicka
Veridicom
(RKK - Skytale)
[WWW: http://www.veridicom.com , http://www.skytale.com]


You are currently subscribed to ntfsd as: $subst(‘Recip.EmailAddr’)
To unsubscribe send a blank email to leave-ntfsd-$subst(‘Recip.MemberIDChar’)@lists.osr.com

This is really not too hard.

  1. collect all the local variables of the recursive procedures.
  2. put them in a struct.
  3. use the STL stack class
    4) push and pop by hand, instead of by calling and returning

    I’m not, of course, entirely sure that STL can be used safely in the kernel,
    but you get the idea.

    I’ve done this in the past to implement co-routines.


    You are currently subscribed to ntfsd as: $subst(‘Recip.EmailAddr’)
    To unsubscribe send a blank email to leave-ntfsd-$subst(‘Recip.MemberIDChar’)@lists.osr.com

> As I said, it was trivial example. But you can’t avoid it in principle,

naturally recursive algorithm needs an info about ‘backtrack’. You can only
make clever data representation which gives you this info (but takes more
memory). For example, if you have one way linked binary tree, you need the
stack or array which saves the way from the root to actual node to traverse
it. If you have double linked tree, all you need is the actual node because
there is a pointer to parent node. If you are interested about it, take some
book about graph theory, there should be a lot of examples.

No need, I need to implement them this June, and already did within the last
year or so.

What means efficient?

Fast and non memory hogger.
You don’t know how much memory you need to allocate.
Another thing the original poster can try is __forceinline and #pragma
inline_recution(on) inline_depth(10) which would take forever to compile,
probably, but will not use as much stack.


Kind regards, Dejan M. CEO Alfa Co. www.alfaunits.co.yu and www.register.co.yu
E-mail : xxxxx@ptt.yu, xxxxx@register.co.yu and xxxxx@alfaunits.co.yu
ICQ# : 56570367
Professional file&system related components and libraries for Win32 developers.
Alfa File Monitor - #1 file monitoring system for Win32 developers.
Alfa File Protector - #1 file protection and hiding system for Win32 developers.

Alfa Units - #1 file and system handling units for Delphi.


You are currently subscribed to ntfsd as: $subst(‘Recip.EmailAddr’)
To unsubscribe send a blank email to leave-ntfsd-$subst(‘Recip.MemberIDChar’)@lists.osr.com

On the 23 of May Valery A. Boronin wrote:

Does anybody knows how to avoid folowing:
in the my filter driver I do searching by binary tree structures with a
recursive calls.
So, sometimes when recurse level large enough, I’ve got stack fault due
drivers has limited stack size for their own needs.

IMHO there’s a few points to note:

  1. One can use fastcall to prevent passing the arguments on the stack.

  2. emulate stack as a data structure that you can expand (push) unwind (to place your auto variables). Place the object
    dynamically.

  3. There’s a call to augment the stack size for the thread.
    I remember seeing it in the first articles of the list (96???).
    There’s no Nt under my hand but I’m sure there’s a whole squad which could give the particular proto.

Best regards,
Aulexii


You are currently subscribed to ntfsd as: $subst(‘Recip.EmailAddr’)
To unsubscribe send a blank email to leave-ntfsd-$subst(‘Recip.MemberIDChar’)@lists.osr.com

> 3. There’s a call to augment the stack size for the thread.

Wrong.
Kernel stack size is always 12KB (3 pages).

Max


You are currently subscribed to ntfsd as: $subst(‘Recip.EmailAddr’)
To unsubscribe send a blank email to leave-ntfsd-$subst(‘Recip.MemberIDChar’)@lists.osr.com

Wrong. Threads that invoke WIN32K functions have special “large” kernel
stacks that are 64K in size. You can see this with one of the windbg
commands, such as “!process 0 7” or “!thread”. I don’t remember which of
the two shows it offhand. Some of the threads are marked as “large” in the
output, and if you calculate the difference between the stack base and
limit, you will find it is 64K.

-----Original Message-----
From: Maxim S. Shatskih [mailto:xxxxx@storagecraft.com]
Sent: Thursday, May 24, 2001 7:30 AM
To: File Systems Developers
Subject: [ntfsd] Re: not enough kernel stack question

> 3. There’s a call to augment the stack size for the thread.

Wrong.
Kernel stack size is always 12KB (3 pages).

Max


You are currently subscribed to ntfsd as: xxxxx@nsisw.com
To unsubscribe send a blank email to leave-ntfsd-$subst(‘Recip.MemberIDChar’)@lists.osr.com


You are currently subscribed to ntfsd as: $subst(‘Recip.EmailAddr’)
To unsubscribe send a blank email to leave-ntfsd-$subst(‘Recip.MemberIDChar’)@lists.osr.com

You can find out current stack limits by using
the routine IoGetStackLimits(). Its prototype resides
in both the NTIFS.H and NTDDK.H.
Also you can use the macro IoGetRemainingStackSize() to
find out how much stack is currently available.

Note: This macro is used by Microsoft FSDs in read and write
dispatch routines and if the remaining stack is below
some threshold, the read or write is posted using
FsRtlPostStackOverflow or FsRtlPostPagingFileStackOverflow.

Hope this helps.

Paul

PS: But I completely agrre with Michal Vodicka that your situation
can be solved by some kind of emulating the stack by allocating
memory and by a loop. Not by posting some work item when reamining
stack is too low or some other insane things - like changing the
value of ESP.

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of Alexei Chentsov
Sent: Thursday, May 24, 2001 11:55 AM
To: File Systems Developers
Subject: [ntfsd] Re: not enough kernel stack question

On the 23 of May Valery A. Boronin wrote:

Does anybody knows how to avoid folowing:
in the my filter driver I do searching by binary tree structures with
a
recursive calls.
So, sometimes when recurse level large enough, I’ve got stack fault
due
drivers has limited stack size for their own needs.

IMHO there’s a few points to note:

  1. One can use fastcall to prevent passing the arguments on the stack.

  2. emulate stack as a data structure that you can expand (push) unwind
    (to place your auto variables). Place the object
    dynamically.

  3. There’s a call to augment the stack size for the thread.
    I remember seeing it in the first articles of the list (96???).
    There’s no Nt under my hand but I’m sure there’s a whole squad which
    could give the particular proto.

Best regards,
Aulexii


You are currently subscribed to ntfsd as: xxxxx@compelson.com
To unsubscribe send a blank email to leave-ntfsd-$subst(‘Recip.MemberIDChar’)@lists.osr.com


You are currently subscribed to ntfsd as: $subst(‘Recip.EmailAddr’)
To unsubscribe send a blank email to leave-ntfsd-$subst(‘Recip.MemberIDChar’)@lists.osr.com

> > 3. There’s a call to augment the stack size for the thread.

Wrong.
Kernel stack size is always 12KB (3 pages).

Max


Consider the MmGrowKernelStack exported by ntoskrnl.

Proto:
NTSTATUS MmGrowKernelStack(PVOID SomeStackPtr);

Flow:
You can expand stack with another 3 pages. If condition
(SomeStackPtr - 3 * PAGE_SIZE >= KeGetCurrentThread()->StackBase - 0xf * PAGE_SIZE) fulfilled kernel stack gets more pages. Otherwise
you the kernel stack overflow is returned.

MmGrowKernelStack called in some unexported ntoskrnl function
after it has found there’s less than 3 pages on the stack
left.

Regards,
Alexei.


You are currently subscribed to ntfsd as: $subst(‘Recip.EmailAddr’)
To unsubscribe send a blank email to leave-ntfsd-$subst(‘Recip.MemberIDChar’)@lists.osr.com