Hello, All!
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.
How to call my code in the my own, allocated in the NonPagedPool memory,
stack (like an 9x _Call_On_My_Stack function) in the NT? Is it possible? Is
there another ways to avoid this deep recurse problem?
What about allocating structure to keep call parameters and local variables
in the system memory instead passing they to the stack, then pass only
pointer to this structure into my recursive function? Is it unique solution?
I know that each recurse could be modified to the linear algorithm, but it’s
not OK for my case now.
Thanks,
Valery A. Boronin,
System Software Engineer, Novosoft
Web: http://www.novosoft-us.com
Email: xxxxx@novosoft.ru
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
Consider using a balanced binary tree or approximately balanced binary tree
such as an AVL tree or red-black tree. This will limit the depth of the
tree thereby limiting the recursion. (IIRC, for an AVL tree the maximum
recursion would be “log n + 1;” for a red-black tree, “2 log n + 1.”)
-----Original Message-----
From: Valery A. Boronin [mailto:xxxxx@novosoft.ru]
Sent: Tuesday, May 22, 2001 3:47 PM
To: File Systems Developers
Subject: [ntfsd] not enough kernel stack question
Hello, All!
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.
How to call my code in the my own, allocated in the
NonPagedPool memory,
stack (like an 9x _Call_On_My_Stack function) in the NT? Is
it possible? Is
there another ways to avoid this deep recurse problem?
What about allocating structure to keep call parameters and
local variables
in the system memory instead passing they to the stack, then pass only
pointer to this structure into my recursive function? Is it
unique solution?
I know that each recurse could be modified to the linear
algorithm, but it’s
not OK for my case now.
Thanks,
Valery A. Boronin,
System Software Engineer, Novosoft
Web: http://www.novosoft-us.com
Email: xxxxx@novosoft.ru
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
> I know that each recurse could be modified to the linear algorithm, but it’s
not OK for my case now.
Not each recursive can be changed to iterative (linear) algorithm, but
binary trees can. Depending on what you need, though. A two way linked binary
tree can certainly be made iteratively.
Trust me, I did it in the last 2-3 years, on competitions.
–
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: Tuesday, May 22, 2001 11:08 PM
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. It can be
of course complicated and inelegant but is possible. For binary tree it is
easy and I believe it is easier than play with kernel stack.
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
You should just simply flatten out your recursion & make it iterative.
It shouldn’t be too difficult with a simple binary tree.
You’ll probably get better perf. & be more sensitive to the already
existing stack situation in NT .
-----Original Message-----
From: Valery A. Boronin [mailto:xxxxx@novosoft.ru]
Sent: Tuesday, May 22, 2001 1:47 PM
To: File Systems Developers
Subject: [ntfsd] not enough kernel stack question
Hello, All!
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.
How to call my code in the my own, allocated in the NonPagedPool memory,
stack (like an 9x _Call_On_My_Stack function) in the NT? Is it possible?
Is there another ways to avoid this deep recurse problem?
What about allocating structure to keep call parameters and local
variables in the system memory instead passing they to the stack, then
pass only pointer to this structure into my recursive function? Is it
unique solution?
I know that each recurse could be modified to the linear algorithm, but
it’s not OK for my case now.
Thanks,
Valery A. Boronin,
System Software Engineer, Novosoft
Web: http://www.novosoft-us.com
Email: xxxxx@novosoft.ru
You are currently subscribed to ntfsd as: xxxxx@windows.microsoft.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
>What about allocating structure to keep call parameters and local variables
in the system memory instead passing they to the stack, then pass only
pointer to this structure into my recursive function? Is it unique solution?
Of course doing a call itself will use the stack, so this wouldn’t
eliminate stack usage entirely unless you are willing to resort to
assembler and use jumps (instead of calls) and register based
parameters. Compilers also have a tendency to use stack space even
if you don’t explicitly declare local variables.
Shaun
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
> How to call my code in the my own, allocated in the NonPagedPool memory,
stack (like an 9x _Call_On_My_Stack function) in the NT? Is it possible?
Is
there another ways to avoid this deep recurse problem?
No, KTHREAD and other kernel internals keeps pointers to the thread’s stack
location.
I know that each recurse could be modified to the linear algorithm, but
it’s
not OK for my case now.
You can queue a DPC or a work item to do the rest of the job if you have
consumed too large stack space instead of continuing recursion.
So, in fact, ExQueueWorkItem or KeInsertQueueDpc are things you want to do.
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
Thanks all of us, who answer me!
I know all about features of trees, just want to notice, in my case it’s
not a simple string tree: I use an N-tree based search algorithm that
breaks strings down by their leading characters. Identical portions are
‘clipped’ and stored in a single node, with the remainder of the string in
similarly divided child nodes. So, manipulation with such tree a little
harder then in simple tree case. Anyway, I understand common opinion that
to solve it, i need to rewrite all recursive code.
But the question still exists: is it possible to use my own stack somehow?
Why I can’t load my allocated memory to the ESP, cal my code and restore
ESP? On 9x it’s work perfect, for example.
What’s you think about it?
Valery
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
> > 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-
Consider a string matching algorithm, used by DOS. What are the chances to
change it to iterative?
It can be of course complicated and inelegant but is possible. For binary tree
it is easy and I believe it is easier than play with kernel stack.
Yes, binary trees can be implemented as iterative.
–
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