> If I have a code like this in my CREATE Dispatch routine. And if my
Link List can be of 100 elements or more.
Acquire Spin Lock
If Create Link List has elements
{
If this filename found in Create Link List
{
Release Spin lock
Return SpyPassthrough
}
}
Release Spin lockIs there a need to do this operation using spin locks ? Will this lead
to unexpected behavior or performance loss for my driver.Any comments ??
Regards,
Anurag
if another processor could be modifying this list at the same time then
you have to have some protection. You're the only one who can tell us
whether "Create List Links" can be modified by another thread at the
same time as this code is running. And once you tell us that you'll
have your answer.
-p
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com] On Behalf Of Anurag Sarin
Sent: Monday, September 13, 2004 6:27 AM
To: Windows System Software Devs Interest List
Subject: [ntdev] Spinlocks
Is there a need to do this operation using spin locks ? Will
this lead to unexpected behavior or performance loss for my driver.
Any comments ??
Regards,
Anurag
Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256
You are currently subscribed to ntdev as: unknown lmsubst tag
argument: ''
To unsubscribe send a blank email to
xxxxx@lists.osr.com
As Peter said…
However, if you find that other threads can modify the list, there may be
ways to avoid the spin-lock, if you can live with the side-effects:
But one thing that’s always going to be a problem if you have multiple
threads access a list (or any other data structure) is what happens when an
entry isn’t consistant: Consider a delete of an element, just after the
element was found and passed on to some other place… so this ‘other place’
is now using the element that is being deleted. Of course, spinlocks on the
list don’t help here, and you can’t always spinlock the entire use of the
data that came out of the list (especially if you pass it to a different
piece of code than yours and for an undefined time). This has to be worked
around by for instance having reference counts for the data in the list, so
that you can’t delete the count.
Another thing to consider: If this code is ALWAYS running at passive level,
you can use for instance (fast)mutex’s to protect the code from being
re-entered. This will not help your code in itself, but it will give the
time waiting for the mutex to someone else, rather than using a spinlock
which just spins away the cycles in a tight loop. Most unfriendly on other
tasks in the system. Of course, if this code runs at a higher than PASSIVE
IRQL, then you MUST use the spinlock, as asking the OS to wait for you
isn’t allowed at higher IRQL.
–
Mats
xxxxx@lists.osr.com wrote on 09/13/2004 03:09:57 PM:
if another processor could be modifying this list at the same time
then you have to have some protection. You’re the only one who can
tell us whether “Create List Links” can be modified by another
thread at the same time as this code is running. And once you tell
us that you’ll have your answer.-p
From: xxxxx@lists.osr.com [mailto:
xxxxx@lists.osr.com] On Behalf Of Anurag Sarin
Sent: Monday, September 13, 2004 6:27 AM
To: Windows System Software Devs Interest List
Subject: [ntdev] Spinlocks
If I have a code like this in my CREATE Dispatch routine. And if my
Link List can be of 100 elements or more.Acquire Spin Lock
If Create Link List has elements
{
If this filename found in Create Link List
{
Release Spin lock
Return SpyPassthrough
}
}
Release Spin lockIs there a need to do this operation using spin locks ? Will this
lead to unexpected behavior or performance loss for my driver.
Any comments ??
Regards,
AnuragQuestions? First check the Kernel Driver FAQ at http://www.
osronline.com/article.cfm?id=256You are currently subscribed to ntdev as: unknown lmsubst tag argument:
‘’
To unsubscribe send a blank email to xxxxx@lists.osr.comQuestions? First check the Kernel Driver FAQ at http://www.
osronline.com/article.cfm?id=256You are currently subscribed to ntdev as: unknown lmsubst tag argument:
‘’
To unsubscribe send a blank email to xxxxx@lists.osr.com
ForwardSourceID:NT0000353E
Ah, I’m always too slow 
One thing still left to say - you could think
about alternative data-structures if your list can get very big. Like
hash-maps, b-trees or even a red-black-tree. That way you don’t avoid the
lock but you can reduce the time it takes to find one entry. The downside
is that the structures are more complicated and you have to allocate
additional storage for them (at least for hash-map and b-tree).
Regards,
Paul Groke
Mats PETERSSON
Gesendet von: xxxxx@lists.osr.com
13.09.2004 16:40
Bitte antworten an “Windows System Software Devs Interest List”
An: “Windows System Software Devs Interest List”
Kopie:
Thema: RE: [ntdev] Spinlocks
As Peter said…
However, if you find that other threads can modify the list, there may be
ways to avoid the spin-lock, if you can live with the side-effects:
1. Don’t ever REMOVE entries from the list, just mark them invalid. This
means that you don’t have to worry about entries “going away” whilst
you’re
working on them (doing p = p->next isn’t a good thing if p isn’t valid
because it’s been freed!).
2. If you want to ADD things, make sure that it’s done in a safe manner.
This can be done in many different ways, but it’s fairly easy to use the
ExchangeInterLocked to write to the “next” pointer, which makes the
operation atomic. Of course, if the list if double linked, it may be a bit
harder to achieve an atomic write.
But one thing that’s always going to be a problem if you have multiple
threads access a list (or any other data structure) is what happens when
an
entry isn’t consistant: Consider a delete of an element, just after the
element was found and passed on to some other place… so this ‘other
place’
is now using the element that is being deleted. Of course, spinlocks on
the
list don’t help here, and you can’t always spinlock the entire use of the
data that came out of the list (especially if you pass it to a different
piece of code than yours and for an undefined time). This has to be worked
around by for instance having reference counts for the data in the list,
so
that you can’t delete the count.
Another thing to consider: If this code is ALWAYS running at passive
level,
you can use for instance (fast)mutex’s to protect the code from being
re-entered. This will not help your code in itself, but it will give the
time waiting for the mutex to someone else, rather than using a spinlock
which just spins away the cycles in a tight loop. Most unfriendly on other
tasks in the system. Of course, if this code runs at a higher than PASSIVE
IRQL, then you MUST use the spinlock, as asking the OS to wait for you
isn’t allowed at higher IRQL.
–
Mats
xxxxx@lists.osr.com wrote on 09/13/2004 03:09:57 PM:
> if another processor could be modifying this list at the same time
> then you have to have some protection. You’re the only one who can
> tell us whether “Create List Links” can be modified by another
> thread at the same time as this code is running. And once you tell
> us that you’ll have your answer.
>
> -p
>
> From: xxxxx@lists.osr.com [mailto:
> xxxxx@lists.osr.com] On Behalf Of Anurag Sarin
> Sent: Monday, September 13, 2004 6:27 AM
> To: Windows System Software Devs Interest List
> Subject: [ntdev] Spinlocks
> If I have a code like this in my CREATE Dispatch routine. And if my
> Link List can be of 100 elements or more.
> ---------------------------------------------------
> Acquire Spin Lock
> If Create Link List has elements
> {
> If this filename found in Create Link List
> {
> Release Spin lock
> Return SpyPassthrough
> }
> }
> Release Spin lock
> ----------------------------------------------------
> Is there a need to do this operation using spin locks ? Will this
> lead to unexpected behavior or performance loss for my driver.
> Any comments ??
> Regards,
> Anurag
> —
> Questions? First check the Kernel Driver FAQ at http://www.
> osronline.com/article.cfm?id=256
>
> You are currently subscribed to ntdev as: unknown lmsubst tag argument:
‘’
> To unsubscribe send a blank email to xxxxx@lists.osr.com
> —
> Questions? First check the Kernel Driver FAQ at http://www.
> osronline.com/article.cfm?id=256
>
> You are currently subscribed to ntdev as: unknown lmsubst tag argument:
‘’
> To unsubscribe send a blank email to xxxxx@lists.osr.com
> ForwardSourceID:NT0000353E
—
Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256
You are currently subscribed to ntdev as: xxxxx@tab.at
To unsubscribe send a blank email to xxxxx@lists.osr.com
Please visit us: www.tab.at www.championsnet.net
www.silverball.com
In this instance, being slow means less typing 
Indeed a good suggestion, using a faster way to find the relevant data
doesn’t remove the problem, but it certainly helps reduce the locked time.
Good suggestion, I should’ve thought of it…
–
Mats
xxxxx@lists.osr.com wrote on 09/13/2004 04:13:59 PM:
Ah, I’m always too slow
about alternative data-structures if your list can get very big. Like
hash-maps, b-trees or even a red-black-tree. That way you don’t avoid the
lock but you can reduce the time it takes to find one entry. The downside
is that the structures are more complicated and you have to allocate
additional storage for them (at least for hash-map and b-tree).Regards,
Paul Groke
Mats PETERSSON
> Gesendet von: xxxxx@lists.osr.com
> 13.09.2004 16:40
> Bitte antworten an “Windows System Software Devs Interest List”
>
> An: “Windows System Software Devs Interest List”
>
> Kopie:
> Thema: RE: [ntdev] Spinlocks
>
>
>
>
>
>
>
> As Peter said…
>
> However, if you find that other threads can modify the list, there may be
> ways to avoid the spin-lock, if you can live with the side-effects:
> 1. Don’t ever REMOVE entries from the list, just mark them invalid. This
> means that you don’t have to worry about entries “going away” whilst
> you’re
> working on them (doing p = p->next isn’t a good thing if p isn’t valid
> because it’s been freed!).
> 2. If you want to ADD things, make sure that it’s done in a safe manner.
> This can be done in many different ways, but it’s fairly easy to use the
> ExchangeInterLocked to write to the “next” pointer, which makes the
> operation atomic. Of course, if the list if double linked, it may be a
bit
> harder to achieve an atomic write.
>
> But one thing that’s always going to be a problem if you have multiple
> threads access a list (or any other data structure) is what happens when
> an
> entry isn’t consistant: Consider a delete of an element, just after the
> element was found and passed on to some other place… so this ‘other
> place’
> is now using the element that is being deleted. Of course, spinlocks on
> the
> list don’t help here, and you can’t always spinlock the entire use of the
> data that came out of the list (especially if you pass it to a different
> piece of code than yours and for an undefined time). This has to be
worked
> around by for instance having reference counts for the data in the list,
> so
> that you can’t delete the count.
>
> Another thing to consider: If this code is ALWAYS running at passive
> level,
> you can use for instance (fast)mutex’s to protect the code from being
> re-entered. This will not help your code in itself, but it will give the
> time waiting for the mutex to someone else, rather than using a spinlock
> which just spins away the cycles in a tight loop. Most unfriendly on
other
> tasks in the system. Of course, if this code runs at a higher than
PASSIVE
> IRQL, then you MUST use the spinlock, as asking the OS to wait for you
> isn’t allowed at higher IRQL.
>
> –
> Mats
>
>
> xxxxx@lists.osr.com wrote on 09/13/2004 03:09:57 PM:
>
> > if another processor could be modifying this list at the same time
> > then you have to have some protection. You’re the only one who can
> > tell us whether “Create List Links” can be modified by another
> > thread at the same time as this code is running. And once you tell
> > us that you’ll have your answer.
> >
> > -p
> >
> > From: xxxxx@lists.osr.com [mailto:
> > xxxxx@lists.osr.com] On Behalf Of Anurag Sarin
> > Sent: Monday, September 13, 2004 6:27 AM
> > To: Windows System Software Devs Interest List
> > Subject: [ntdev] Spinlocks
>
> > If I have a code like this in my CREATE Dispatch routine. And if my
> > Link List can be of 100 elements or more.
> > ---------------------------------------------------
> > Acquire Spin Lock
> > If Create Link List has elements
> > {
> > If this filename found in Create Link List
> > {
> > Release Spin lock
> > Return SpyPassthrough
> > }
> > }
> > Release Spin lock
> > ----------------------------------------------------
> > Is there a need to do this operation using spin locks ? Will this
> > lead to unexpected behavior or performance loss for my driver.
> > Any comments ??
> > Regards,
> > Anurag
> > —
> > Questions? First check the Kernel Driver FAQ at http://www.
> > osronline.com/article.cfm?id=256
> >
> > You are currently subscribed to ntdev as: unknown lmsubst tag argument:
> ‘’
> > To unsubscribe send a blank email to xxxxx@lists.osr.com
> > —
> > Questions? First check the Kernel Driver FAQ at http://www.
> > osronline.com/article.cfm?id=256
> >
> > You are currently subscribed to ntdev as: unknown lmsubst tag argument:
> ‘’
> > To unsubscribe send a blank email to xxxxx@lists.osr.com
> > ForwardSourceID:NT0000353E
>
>
>
> —
> Questions? First check the Kernel Driver FAQ at
> http://www.osronline.com/article.cfm?id=256
>
> You are currently subscribed to ntdev as: xxxxx@tab.at
> To unsubscribe send a blank email to xxxxx@lists.osr.com
>
> Please visit us: www.tab.at www.championsnet.net
> www.silverball.com
>
>
>
> —
> Questions? First check the Kernel Driver FAQ at http://www.
> osronline.com/article.cfm?id=256
>
> You are currently subscribed to ntdev as: xxxxx@3dlabs.com
> To unsubscribe send a blank email to xxxxx@lists.osr.com
> ForwardSourceID:NT00003572
> In this instance, being slow means less typing
Nah, in this instance I just typed a lot of food for my backspace key *g*
Fast “find” structures would be a really nice thing to have from the DDK.
If they were implemented in the DDK using one fixed block-size (for e.g.
b-trees) from one common lookaside-list (private lal optional?) and if the
implementation was fast and rock-solid they’d surely be a nice thing for
some driver-developers. Anything like an FS or even a firewall could
surely make use of that.
Anyway, for 100 entries max. I’d probably stick with a list, for 100+
entries avg. I’d prefer something else. With strings as keys (did someone
mention filenames?) I’d probably use some form of hash anyway
(adler32/crc32) - even if it’s only a list. The comparsion of one DWORD
vs. a whole string should also give some noticable speedup.
Regards,
Paul Groke
Mats PETERSSON
Gesendet von: xxxxx@lists.osr.com
13.09.2004 17:19
Bitte antworten an “Windows System Software Devs Interest List”
An: “Windows System Software Devs Interest List”
Kopie:
Thema: Re: [ntdev] Spinlocks
In this instance, being slow means less typing
Indeed a good suggestion, using a faster way to find the relevant data
doesn’t remove the problem, but it certainly helps reduce the locked time.
Good suggestion, I should’ve thought of it…
–
Mats
xxxxx@lists.osr.com wrote on 09/13/2004 04:13:59 PM:
> Ah, I’m always too slow One thing still left to say - you could
think
> about alternative data-structures if your list can get very big. Like
> hash-maps, b-trees or even a red-black-tree. That way you don’t avoid
the
> lock but you can reduce the time it takes to find one entry. The
downside
> is that the structures are more complicated and you have to allocate
> additional storage for them (at least for hash-map and b-tree).
>
> Regards,
>
> Paul Groke
>
>
>
>
>
> Mats PETERSSON
> Gesendet von: xxxxx@lists.osr.com
> 13.09.2004 16:40
> Bitte antworten an “Windows System Software Devs Interest List”
>
> An: “Windows System Software Devs Interest List”
>
> Kopie:
> Thema: RE: [ntdev] Spinlocks
>
>
>
>
>
>
>
> As Peter said…
>
> However, if you find that other threads can modify the list, there may
be
> ways to avoid the spin-lock, if you can live with the side-effects:
> 1. Don’t ever REMOVE entries from the list, just mark them invalid. This
> means that you don’t have to worry about entries “going away” whilst
> you’re
> working on them (doing p = p->next isn’t a good thing if p isn’t valid
> because it’s been freed!).
> 2. If you want to ADD things, make sure that it’s done in a safe manner.
> This can be done in many different ways, but it’s fairly easy to use the
> ExchangeInterLocked to write to the “next” pointer, which makes the
> operation atomic. Of course, if the list if double linked, it may be a
bit
> harder to achieve an atomic write.
>
> But one thing that’s always going to be a problem if you have multiple
> threads access a list (or any other data structure) is what happens when
> an
> entry isn’t consistant: Consider a delete of an element, just after the
> element was found and passed on to some other place… so this ‘other
> place’
> is now using the element that is being deleted. Of course, spinlocks on
> the
> list don’t help here, and you can’t always spinlock the entire use of
the
> data that came out of the list (especially if you pass it to a different
> piece of code than yours and for an undefined time). This has to be
worked
> around by for instance having reference counts for the data in the list,
> so
> that you can’t delete the count.
>
> Another thing to consider: If this code is ALWAYS running at passive
> level,
> you can use for instance (fast)mutex’s to protect the code from being
> re-entered. This will not help your code in itself, but it will give the
> time waiting for the mutex to someone else, rather than using a spinlock
> which just spins away the cycles in a tight loop. Most unfriendly on
other
> tasks in the system. Of course, if this code runs at a higher than
PASSIVE
> IRQL, then you MUST use the spinlock, as asking the OS to wait for you
> isn’t allowed at higher IRQL.
>
> –
> Mats
>
>
> xxxxx@lists.osr.com wrote on 09/13/2004 03:09:57 PM:
>
> > if another processor could be modifying this list at the same time
> > then you have to have some protection. You’re the only one who can
> > tell us whether “Create List Links” can be modified by another
> > thread at the same time as this code is running. And once you tell
> > us that you’ll have your answer.
> >
> > -p
> >
> > From: xxxxx@lists.osr.com [mailto:
> > xxxxx@lists.osr.com] On Behalf Of Anurag Sarin
> > Sent: Monday, September 13, 2004 6:27 AM
> > To: Windows System Software Devs Interest List
> > Subject: [ntdev] Spinlocks
>
> > If I have a code like this in my CREATE Dispatch routine. And if my
> > Link List can be of 100 elements or more.
> > ---------------------------------------------------
> > Acquire Spin Lock
> > If Create Link List has elements
> > {
> > If this filename found in Create Link List
> > {
> > Release Spin lock
> > Return SpyPassthrough
> > }
> > }
> > Release Spin lock
> > ----------------------------------------------------
> > Is there a need to do this operation using spin locks ? Will this
> > lead to unexpected behavior or performance loss for my driver.
> > Any comments ??
> > Regards,
> > Anurag
> > —
> > Questions? First check the Kernel Driver FAQ at http://www.
> > osronline.com/article.cfm?id=256
> >
> > You are currently subscribed to ntdev as: unknown lmsubst tag
argument:
> ‘’
> > To unsubscribe send a blank email to xxxxx@lists.osr.com
> > —
> > Questions? First check the Kernel Driver FAQ at http://www.
> > osronline.com/article.cfm?id=256
> >
> > You are currently subscribed to ntdev as: unknown lmsubst tag
argument:
> ‘’
> > To unsubscribe send a blank email to xxxxx@lists.osr.com
> > ForwardSourceID:NT0000353E
>
>
>
> —
> Questions? First check the Kernel Driver FAQ at
> http://www.osronline.com/article.cfm?id=256
>
> You are currently subscribed to ntdev as: xxxxx@tab.at
> To unsubscribe send a blank email to xxxxx@lists.osr.com
>
> Please visit us: www.tab.at www.championsnet.net
> www.silverball.com
>
>
>
> —
> Questions? First check the Kernel Driver FAQ at http://www.
> osronline.com/article.cfm?id=256
>
> You are currently subscribed to ntdev as: xxxxx@3dlabs.com
> To unsubscribe send a blank email to xxxxx@lists.osr.com
> ForwardSourceID:NT00003572
—
Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256
You are currently subscribed to ntdev as: xxxxx@tab.at
To unsubscribe send a blank email to xxxxx@lists.osr.com
Please visit us: www.tab.at www.championsnet.net
www.silverball.com
Just dropping my A* wide open :-). Kick as you please
May be one or more thing to remember is not such the size of the list :).
How frequently
it would execute, it is possible that the list might not go over 300, and
each element ie. sizeof (struct node) might be 32 or 64 bytes, then ddk/os
provided TLB would be a choice . Sometime hash-collison, and the cost of
hash-function might become a overhead too !!. If it is on a really busy
execution path, hashing cost should be looked carefully too
-pro
-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of xxxxx@tab.at
Sent: Monday, September 13, 2004 8:41 AM
To: Windows System Software Devs Interest List
Subject: Re: [ntdev] Spinlocks
In this instance, being slow means less typing
Nah, in this instance I just typed a lot of food for my backspace key *g*
Fast “find” structures would be a really nice thing to have from the DDK.
If they were implemented in the DDK using one fixed block-size (for e.g.
b-trees) from one common lookaside-list (private lal optional?) and if the
implementation was fast and rock-solid they’d surely be a nice thing for
some driver-developers. Anything like an FS or even a firewall could
surely make use of that.
Anyway, for 100 entries max. I’d probably stick with a list, for 100+
entries avg. I’d prefer something else. With strings as keys (did someone
mention filenames?) I’d probably use some form of hash anyway
(adler32/crc32) - even if it’s only a list. The comparsion of one DWORD
vs. a whole string should also give some noticable speedup.
Regards,
Paul Groke
Mats PETERSSON
Gesendet von: xxxxx@lists.osr.com
13.09.2004 17:19
Bitte antworten an “Windows System Software Devs Interest List”
An: “Windows System Software Devs Interest List”
Kopie:
Thema: Re: [ntdev] Spinlocks
In this instance, being slow means less typing
Indeed a good suggestion, using a faster way to find the relevant data
doesn’t remove the problem, but it certainly helps reduce the locked time.
Good suggestion, I should’ve thought of it…
–
Mats
xxxxx@lists.osr.com wrote on 09/13/2004 04:13:59 PM:
> Ah, I’m always too slow One thing still left to say - you could
think
> about alternative data-structures if your list can get very big. Like
> hash-maps, b-trees or even a red-black-tree. That way you don’t avoid
the
> lock but you can reduce the time it takes to find one entry. The
downside
> is that the structures are more complicated and you have to allocate
> additional storage for them (at least for hash-map and b-tree).
>
> Regards,
>
> Paul Groke
>
>
>
>
>
> Mats PETERSSON
> Gesendet von: xxxxx@lists.osr.com
> 13.09.2004 16:40
> Bitte antworten an “Windows System Software Devs Interest List”
>
> An: “Windows System Software Devs Interest List”
>
> Kopie:
> Thema: RE: [ntdev] Spinlocks
>
>
>
>
>
>
>
> As Peter said…
>
> However, if you find that other threads can modify the list, there may
be
> ways to avoid the spin-lock, if you can live with the side-effects:
> 1. Don’t ever REMOVE entries from the list, just mark them invalid. This
> means that you don’t have to worry about entries “going away” whilst
> you’re
> working on them (doing p = p->next isn’t a good thing if p isn’t valid
> because it’s been freed!).
> 2. If you want to ADD things, make sure that it’s done in a safe manner.
> This can be done in many different ways, but it’s fairly easy to use the
> ExchangeInterLocked to write to the “next” pointer, which makes the
> operation atomic. Of course, if the list if double linked, it may be a
bit
> harder to achieve an atomic write.
>
> But one thing that’s always going to be a problem if you have multiple
> threads access a list (or any other data structure) is what happens when
> an
> entry isn’t consistant: Consider a delete of an element, just after the
> element was found and passed on to some other place… so this ‘other
> place’
> is now using the element that is being deleted. Of course, spinlocks on
> the
> list don’t help here, and you can’t always spinlock the entire use of
the
> data that came out of the list (especially if you pass it to a different
> piece of code than yours and for an undefined time). This has to be
worked
> around by for instance having reference counts for the data in the list,
> so
> that you can’t delete the count.
>
> Another thing to consider: If this code is ALWAYS running at passive
> level,
> you can use for instance (fast)mutex’s to protect the code from being
> re-entered. This will not help your code in itself, but it will give the
> time waiting for the mutex to someone else, rather than using a spinlock
> which just spins away the cycles in a tight loop. Most unfriendly on
other
> tasks in the system. Of course, if this code runs at a higher than
PASSIVE
> IRQL, then you MUST use the spinlock, as asking the OS to wait for you
> isn’t allowed at higher IRQL.
>
> –
> Mats
>
>
> xxxxx@lists.osr.com wrote on 09/13/2004 03:09:57 PM:
>
> > if another processor could be modifying this list at the same time
> > then you have to have some protection. You’re the only one who can
> > tell us whether “Create List Links” can be modified by another
> > thread at the same time as this code is running. And once you tell
> > us that you’ll have your answer.
> >
> > -p
> >
> > From: xxxxx@lists.osr.com [mailto:
> > xxxxx@lists.osr.com] On Behalf Of Anurag Sarin
> > Sent: Monday, September 13, 2004 6:27 AM
> > To: Windows System Software Devs Interest List
> > Subject: [ntdev] Spinlocks
>
> > If I have a code like this in my CREATE Dispatch routine. And if my
> > Link List can be of 100 elements or more.
> > ---------------------------------------------------
> > Acquire Spin Lock
> > If Create Link List has elements
> > {
> > If this filename found in Create Link List
> > {
> > Release Spin lock
> > Return SpyPassthrough
> > }
> > }
> > Release Spin lock
> > ----------------------------------------------------
> > Is there a need to do this operation using spin locks ? Will this
> > lead to unexpected behavior or performance loss for my driver.
> > Any comments ??
> > Regards,
> > Anurag
> > —
> > Questions? First check the Kernel Driver FAQ at http://www.
> > osronline.com/article.cfm?id=256
> >
> > You are currently subscribed to ntdev as: unknown lmsubst tag
argument:
> ‘’
> > To unsubscribe send a blank email to xxxxx@lists.osr.com
> > —
> > Questions? First check the Kernel Driver FAQ at http://www.
> > osronline.com/article.cfm?id=256
> >
> > You are currently subscribed to ntdev as: unknown lmsubst tag
argument:
> ‘’
> > To unsubscribe send a blank email to xxxxx@lists.osr.com
> > ForwardSourceID:NT0000353E
>
>
>
> —
> Questions? First check the Kernel Driver FAQ at
> http://www.osronline.com/article.cfm?id=256
>
> You are currently subscribed to ntdev as: xxxxx@tab.at
> To unsubscribe send a blank email to xxxxx@lists.osr.com
>
> Please visit us: www.tab.at www.championsnet.net
> www.silverball.com
>
>
>
> —
> Questions? First check the Kernel Driver FAQ at http://www.
> osronline.com/article.cfm?id=256
>
> You are currently subscribed to ntdev as: xxxxx@3dlabs.com
> To unsubscribe send a blank email to xxxxx@lists.osr.com
> ForwardSourceID:NT00003572
—
Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256
You are currently subscribed to ntdev as: xxxxx@tab.at
To unsubscribe send a blank email to xxxxx@lists.osr.com
Please visit us: www.tab.at www.championsnet.net
www.silverball.com
—
Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256
You are currently subscribed to ntdev as: xxxxx@garlic.com
To unsubscribe send a blank email to xxxxx@lists.osr.com
Also link list or any truely dynamically allocated structure is a pain in
the horrendous thinking from the cache-point-of-view, so any pre-fabricated
ddk/os provided api for TLB emulation would surely help here !!!
-pro
-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of Prokash Sinha
Sent: Monday, September 13, 2004 9:08 AM
To: Windows System Software Devs Interest List
Subject: RE: [ntdev] Spinlocks
Just dropping my A* wide open :-). Kick as you please
May be one or more thing to remember is not such the size of the list :).
How frequently
it would execute, it is possible that the list might not go over 300, and
each element ie. sizeof (struct node) might be 32 or 64 bytes, then ddk/os
provided TLB would be a choice . Sometime hash-collison, and the cost of
hash-function might become a overhead too !!. If it is on a really busy
execution path, hashing cost should be looked carefully too
-pro
-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of xxxxx@tab.at
Sent: Monday, September 13, 2004 8:41 AM
To: Windows System Software Devs Interest List
Subject: Re: [ntdev] Spinlocks
In this instance, being slow means less typing
Nah, in this instance I just typed a lot of food for my backspace key *g*
Fast “find” structures would be a really nice thing to have from the DDK.
If they were implemented in the DDK using one fixed block-size (for e.g.
b-trees) from one common lookaside-list (private lal optional?) and if the
implementation was fast and rock-solid they’d surely be a nice thing for
some driver-developers. Anything like an FS or even a firewall could
surely make use of that.
Anyway, for 100 entries max. I’d probably stick with a list, for 100+
entries avg. I’d prefer something else. With strings as keys (did someone
mention filenames?) I’d probably use some form of hash anyway
(adler32/crc32) - even if it’s only a list. The comparsion of one DWORD
vs. a whole string should also give some noticable speedup.
Regards,
Paul Groke
Mats PETERSSON
Gesendet von: xxxxx@lists.osr.com
13.09.2004 17:19
Bitte antworten an “Windows System Software Devs Interest List”
An: “Windows System Software Devs Interest List”
Kopie:
Thema: Re: [ntdev] Spinlocks
In this instance, being slow means less typing
Indeed a good suggestion, using a faster way to find the relevant data
doesn’t remove the problem, but it certainly helps reduce the locked time.
Good suggestion, I should’ve thought of it…
–
Mats
xxxxx@lists.osr.com wrote on 09/13/2004 04:13:59 PM:
> Ah, I’m always too slow One thing still left to say - you could
think
> about alternative data-structures if your list can get very big. Like
> hash-maps, b-trees or even a red-black-tree. That way you don’t avoid
the
> lock but you can reduce the time it takes to find one entry. The
downside
> is that the structures are more complicated and you have to allocate
> additional storage for them (at least for hash-map and b-tree).
>
> Regards,
>
> Paul Groke
>
>
>
>
>
> Mats PETERSSON
> Gesendet von: xxxxx@lists.osr.com
> 13.09.2004 16:40
> Bitte antworten an “Windows System Software Devs Interest List”
>
> An: “Windows System Software Devs Interest List”
>
> Kopie:
> Thema: RE: [ntdev] Spinlocks
>
>
>
>
>
>
>
> As Peter said…
>
> However, if you find that other threads can modify the list, there may
be
> ways to avoid the spin-lock, if you can live with the side-effects:
> 1. Don’t ever REMOVE entries from the list, just mark them invalid. This
> means that you don’t have to worry about entries “going away” whilst
> you’re
> working on them (doing p = p->next isn’t a good thing if p isn’t valid
> because it’s been freed!).
> 2. If you want to ADD things, make sure that it’s done in a safe manner.
> This can be done in many different ways, but it’s fairly easy to use the
> ExchangeInterLocked to write to the “next” pointer, which makes the
> operation atomic. Of course, if the list if double linked, it may be a
bit
> harder to achieve an atomic write.
>
> But one thing that’s always going to be a problem if you have multiple
> threads access a list (or any other data structure) is what happens when
> an
> entry isn’t consistant: Consider a delete of an element, just after the
> element was found and passed on to some other place… so this ‘other
> place’
> is now using the element that is being deleted. Of course, spinlocks on
> the
> list don’t help here, and you can’t always spinlock the entire use of
the
> data that came out of the list (especially if you pass it to a different
> piece of code than yours and for an undefined time). This has to be
worked
> around by for instance having reference counts for the data in the list,
> so
> that you can’t delete the count.
>
> Another thing to consider: If this code is ALWAYS running at passive
> level,
> you can use for instance (fast)mutex’s to protect the code from being
> re-entered. This will not help your code in itself, but it will give the
> time waiting for the mutex to someone else, rather than using a spinlock
> which just spins away the cycles in a tight loop. Most unfriendly on
other
> tasks in the system. Of course, if this code runs at a higher than
PASSIVE
> IRQL, then you MUST use the spinlock, as asking the OS to wait for you
> isn’t allowed at higher IRQL.
>
> –
> Mats
>
>
> xxxxx@lists.osr.com wrote on 09/13/2004 03:09:57 PM:
>
> > if another processor could be modifying this list at the same time
> > then you have to have some protection. You’re the only one who can
> > tell us whether “Create List Links” can be modified by another
> > thread at the same time as this code is running. And once you tell
> > us that you’ll have your answer.
> >
> > -p
> >
> > From: xxxxx@lists.osr.com [mailto:
> > xxxxx@lists.osr.com] On Behalf Of Anurag Sarin
> > Sent: Monday, September 13, 2004 6:27 AM
> > To: Windows System Software Devs Interest List
> > Subject: [ntdev] Spinlocks
>
> > If I have a code like this in my CREATE Dispatch routine. And if my
> > Link List can be of 100 elements or more.
> > ---------------------------------------------------
> > Acquire Spin Lock
> > If Create Link List has elements
> > {
> > If this filename found in Create Link List
> > {
> > Release Spin lock
> > Return SpyPassthrough
> > }
> > }
> > Release Spin lock
> > ----------------------------------------------------
> > Is there a need to do this operation using spin locks ? Will this
> > lead to unexpected behavior or performance loss for my driver.
> > Any comments ??
> > Regards,
> > Anurag
> > —
> > Questions? First check the Kernel Driver FAQ at http://www.
> > osronline.com/article.cfm?id=256
> >
> > You are currently subscribed to ntdev as: unknown lmsubst tag
argument:
> ‘’
> > To unsubscribe send a blank email to xxxxx@lists.osr.com
> > —
> > Questions? First check the Kernel Driver FAQ at http://www.
> > osronline.com/article.cfm?id=256
> >
> > You are currently subscribed to ntdev as: unknown lmsubst tag
argument:
> ‘’
> > To unsubscribe send a blank email to xxxxx@lists.osr.com
> > ForwardSourceID:NT0000353E
>
>
>
> —
> Questions? First check the Kernel Driver FAQ at
> http://www.osronline.com/article.cfm?id=256
>
> You are currently subscribed to ntdev as: xxxxx@tab.at
> To unsubscribe send a blank email to xxxxx@lists.osr.com
>
> Please visit us: www.tab.at www.championsnet.net
> www.silverball.com
>
>
>
> —
> Questions? First check the Kernel Driver FAQ at http://www.
> osronline.com/article.cfm?id=256
>
> You are currently subscribed to ntdev as: xxxxx@3dlabs.com
> To unsubscribe send a blank email to xxxxx@lists.osr.com
> ForwardSourceID:NT00003572
—
Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256
You are currently subscribed to ntdev as: xxxxx@tab.at
To unsubscribe send a blank email to xxxxx@lists.osr.com
Please visit us: www.tab.at www.championsnet.net
www.silverball.com
—
Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256
You are currently subscribed to ntdev as: xxxxx@garlic.com
To unsubscribe send a blank email to xxxxx@lists.osr.com
—
Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256
You are currently subscribed to ntdev as: xxxxx@garlic.com
To unsubscribe send a blank email to xxxxx@lists.osr.com
Hash collision is only a big issue if you use a very simple hash-map. You
should have a secondary hash-function that covers much of that problem -
ie. one that’s “different” enough from the primary hash-function. And if
you only uses hash-codes to speed up the comparsion of 2 strings (with
entries in a list/array)… well - in that case I’d use a very very basic
hash-function, maybe even a simple “16bit sum of all unsigned bytes”; with
at least 3-4 entries that should be faster than to compare the whole
strings.
The problem I see with custom allocated structures is less cache-pollution
than non-paged-pool fragmentation… memory is quite fast nowadays… (and
getting faster
Ah, and yes, a linked list will most-times not be allocated “on it’s own”
Boy, are we OT here
Regards,
Paul Groke
“Prokash Sinha”
Gesendet von: xxxxx@lists.osr.com
13.09.2004 18:29
Bitte antworten an “Windows System Software Devs Interest List”
An: “Windows System Software Devs Interest List”
Kopie:
Thema: RE: [ntdev] Spinlocks
Also link list or any truely dynamically allocated structure is a pain in
the horrendous thinking from the cache-point-of-view, so any
pre-fabricated
ddk/os provided api for TLB emulation would surely help here !!!
-pro
-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of Prokash Sinha
Sent: Monday, September 13, 2004 9:08 AM
To: Windows System Software Devs Interest List
Subject: RE: [ntdev] Spinlocks
Just dropping my A* wide open :-). Kick as you please
May be one or more thing to remember is not such the size of the list :).
How frequently
it would execute, it is possible that the list might not go over 300, and
each element ie. sizeof (struct node) might be 32 or 64 bytes, then ddk/os
provided TLB would be a choice . Sometime hash-collison, and the cost of
hash-function might become a overhead too !!. If it is on a really busy
execution path, hashing cost should be looked carefully too
-pro
-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of xxxxx@tab.at
Sent: Monday, September 13, 2004 8:41 AM
To: Windows System Software Devs Interest List
Subject: Re: [ntdev] Spinlocks
> In this instance, being slow means less typing
Nah, in this instance I just typed a lot of food for my backspace key g
Fast “find” structures would be a really nice thing to have from the DDK.
If they were implemented in the DDK using one fixed block-size (for e.g.
b-trees) from one common lookaside-list (private lal optional?) and if the
implementation was fast and rock-solid they’d surely be a nice thing for
some driver-developers. Anything like an FS or even a firewall could
surely make use of that.
Anyway, for 100 entries max. I’d probably stick with a list, for 100+
entries avg. I’d prefer something else. With strings as keys (did someone
mention filenames?) I’d probably use some form of hash anyway
(adler32/crc32) - even if it’s only a list. The comparsion of one DWORD
vs. a whole string should also give some noticable speedup.
Regards,
Paul Groke
Mats PETERSSON
Gesendet von: xxxxx@lists.osr.com
13.09.2004 17:19
Bitte antworten an “Windows System Software Devs Interest List”
An: “Windows System Software Devs Interest List”
Kopie:
Thema: Re: [ntdev] Spinlocks
In this instance, being slow means less typing
Indeed a good suggestion, using a faster way to find the relevant data
doesn’t remove the problem, but it certainly helps reduce the locked time.
Good suggestion, I should’ve thought of it…
–
Mats
xxxxx@lists.osr.com wrote on 09/13/2004 04:13:59 PM:
> Ah, I’m always too slow One thing still left to say - you could
think
> about alternative data-structures if your list can get very big. Like
> hash-maps, b-trees or even a red-black-tree. That way you don’t avoid
the
> lock but you can reduce the time it takes to find one entry. The
downside
> is that the structures are more complicated and you have to allocate
> additional storage for them (at least for hash-map and b-tree).
>
> Regards,
>
> Paul Groke
>
>
>
>
>
> Mats PETERSSON
> Gesendet von: xxxxx@lists.osr.com
> 13.09.2004 16:40
> Bitte antworten an “Windows System Software Devs Interest List”
>
> An: “Windows System Software Devs Interest List”
>
> Kopie:
> Thema: RE: [ntdev] Spinlocks
>
>
>
>
>
>
>
> As Peter said…
>
> However, if you find that other threads can modify the list, there may
be
> ways to avoid the spin-lock, if you can live with the side-effects:
> 1. Don’t ever REMOVE entries from the list, just mark them invalid. This
> means that you don’t have to worry about entries “going away” whilst
> you’re
> working on them (doing p = p->next isn’t a good thing if p isn’t valid
> because it’s been freed!).
> 2. If you want to ADD things, make sure that it’s done in a safe manner.
> This can be done in many different ways, but it’s fairly easy to use the
> ExchangeInterLocked to write to the “next” pointer, which makes the
> operation atomic. Of course, if the list if double linked, it may be a
bit
> harder to achieve an atomic write.
>
> But one thing that’s always going to be a problem if you have multiple
> threads access a list (or any other data structure) is what happens when
> an
> entry isn’t consistant: Consider a delete of an element, just after the
> element was found and passed on to some other place… so this ‘other
> place’
> is now using the element that is being deleted. Of course, spinlocks on
> the
> list don’t help here, and you can’t always spinlock the entire use of
the
> data that came out of the list (especially if you pass it to a different
> piece of code than yours and for an undefined time). This has to be
worked
> around by for instance having reference counts for the data in the list,
> so
> that you can’t delete the count.
>
> Another thing to consider: If this code is ALWAYS running at passive
> level,
> you can use for instance (fast)mutex’s to protect the code from being
> re-entered. This will not help your code in itself, but it will give the
> time waiting for the mutex to someone else, rather than using a spinlock
> which just spins away the cycles in a tight loop. Most unfriendly on
other
> tasks in the system. Of course, if this code runs at a higher than
PASSIVE
> IRQL, then you MUST use the spinlock, as asking the OS to wait for you
> isn’t allowed at higher IRQL.
>
> –
> Mats
>
>
> xxxxx@lists.osr.com wrote on 09/13/2004 03:09:57 PM:
>
> > if another processor could be modifying this list at the same time
> > then you have to have some protection. You’re the only one who can
> > tell us whether “Create List Links” can be modified by another
> > thread at the same time as this code is running. And once you tell
> > us that you’ll have your answer.
> >
> > -p
> >
> > From: xxxxx@lists.osr.com [mailto:
> > xxxxx@lists.osr.com] On Behalf Of Anurag Sarin
> > Sent: Monday, September 13, 2004 6:27 AM
> > To: Windows System Software Devs Interest List
> > Subject: [ntdev] Spinlocks
>
> > If I have a code like this in my CREATE Dispatch routine. And if my
> > Link List can be of 100 elements or more.
> > ---------------------------------------------------
> > Acquire Spin Lock
> > If Create Link List has elements
> > {
> > If this filename found in Create Link List
> > {
> > Release Spin lock
> > Return SpyPassthrough
> > }
> > }
> > Release Spin lock
> > ----------------------------------------------------
> > Is there a need to do this operation using spin locks ? Will this
> > lead to unexpected behavior or performance loss for my driver.
> > Any comments ??
> > Regards,
> > Anurag
> > —
> > Questions? First check the Kernel Driver FAQ at http://www.
> > osronline.com/article.cfm?id=256
> >
> > You are currently subscribed to ntdev as: unknown lmsubst tag
argument:
> ‘’
> > To unsubscribe send a blank email to xxxxx@lists.osr.com
> > —
> > Questions? First check the Kernel Driver FAQ at http://www.
> > osronline.com/article.cfm?id=256
> >
> > You are currently subscribed to ntdev as: unknown lmsubst tag
argument:
> ‘’
> > To unsubscribe send a blank email to xxxxx@lists.osr.com
> > ForwardSourceID:NT0000353E
>
>
>
> —
> Questions? First check the Kernel Driver FAQ at
> http://www.osronline.com/article.cfm?id=256
>
> You are currently subscribed to ntdev as: xxxxx@tab.at
> To unsubscribe send a blank email to xxxxx@lists.osr.com
>
> Please visit us: www.tab.at www.championsnet.net
> www.silverball.com
>
>
>
> —
> Questions? First check the Kernel Driver FAQ at http://www.
> osronline.com/article.cfm?id=256
>
> You are currently subscribed to ntdev as: xxxxx@3dlabs.com
> To unsubscribe send a blank email to xxxxx@lists.osr.com
> ForwardSourceID:NT00003572
—
Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256
You are currently subscribed to ntdev as: xxxxx@tab.at
To unsubscribe send a blank email to xxxxx@lists.osr.com
Please visit us: www.tab.at www.championsnet.net
www.silverball.com
—
Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256
You are currently subscribed to ntdev as: xxxxx@garlic.com
To unsubscribe send a blank email to xxxxx@lists.osr.com
—
Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256
You are currently subscribed to ntdev as: xxxxx@garlic.com
To unsubscribe send a blank email to xxxxx@lists.osr.com
—
Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256
You are currently subscribed to ntdev as: xxxxx@tab.at
To unsubscribe send a blank email to xxxxx@lists.osr.com
Please visit us: www.tab.at www.championsnet.net
www.silverball.com
It would only “surely help here” if this is the sort of code path where
cache effects are likely to cause a noticible drop off in performance.
Given the length of the typical file-system create path (and this seems
to be a filter on top of those) I doubt that an OS provided cache is
going to solve anything here.
While I love the discussions we get when our threads spin off into the
weeds like this, it’s not always productive for the person who just
wants to know “do I need to have some synchronization here?”
-p
-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com] On Behalf Of Prokash Sinha
Sent: Monday, September 13, 2004 9:30 AM
To: Windows System Software Devs Interest List
Subject: RE: [ntdev] SpinlocksAlso link list or any truely dynamically allocated structure
is a pain in the horrendous thinking from the
cache-point-of-view, so any pre-fabricated ddk/os provided
api for TLB emulation would surely help here !!!-pro
-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of Prokash Sinha
Sent: Monday, September 13, 2004 9:08 AM
To: Windows System Software Devs Interest List
Subject: RE: [ntdev] SpinlocksJust dropping my A* wide open :-). Kick as you please
May be one or more thing to remember is not such the size of
the list :).
How frequently
it would execute, it is possible that the list might not go
over 300, and each element ie. sizeof (struct node) might be
32 or 64 bytes, then ddk/os provided TLB would be a choice .
Sometime hash-collison, and the cost of hash-function might
become a overhead too !!. If it is on a really busy execution
path, hashing cost should be looked carefully too-pro
-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of xxxxx@tab.at
Sent: Monday, September 13, 2004 8:41 AM
To: Windows System Software Devs Interest List
Subject: Re: [ntdev] Spinlocks> In this instance, being slow means less typing
Nah, in this instance I just typed a lot of food for my
backspace key *g* Fast “find” structures would be a really
nice thing to have from the DDK.
If they were implemented in the DDK using one fixed
block-size (for e.g.
b-trees) from one common lookaside-list (private lal
optional?) and if the implementation was fast and rock-solid
they’d surely be a nice thing for some driver-developers.
Anything like an FS or even a firewall could surely make use of that.Anyway, for 100 entries max. I’d probably stick with a list,
for 100+ entries avg. I’d prefer something else. With strings
as keys (did someone mention filenames?) I’d probably use
some form of hash anyway
(adler32/crc32) - even if it’s only a list. The comparsion of
one DWORD vs. a whole string should also give some noticable speedup.Regards,
Paul Groke
Mats PETERSSON Gesendet von:
> xxxxx@lists.osr.com
> 13.09.2004 17:19
> Bitte antworten an “Windows System Software Devs Interest List”
>
> An: “Windows System Software Devs Interest List”
>
> Kopie:
> Thema: Re: [ntdev] Spinlocks
>
>
>
>
>
>
>
> In this instance, being slow means less typing
>
> Indeed a good suggestion, using a faster way to find the
> relevant data doesn’t remove the problem, but it certainly
> helps reduce the locked time.
> Good suggestion, I should’ve thought of it…
>
> –
> Mats
>
> xxxxx@lists.osr.com wrote on 09/13/2004 04:13:59 PM:
>
> > Ah, I’m always too slow
> think
>
> > about alternative data-structures if your list can get very
> big. Like
> > hash-maps, b-trees or even a red-black-tree. That way you
> don’t avoid
> the
>
> > lock but you can reduce the time it takes to find one entry. The
> downside
>
> > is that the structures are more complicated and you have to
> allocate
> > additional storage for them (at least for hash-map and b-tree).
> >
> > Regards,
> >
> > Paul Groke
> >
> >
> >
> >
> >
> > Mats PETERSSON Gesendet von:
> > xxxxx@lists.osr.com
> > 13.09.2004 16:40
> > Bitte antworten an “Windows System Software Devs Interest List”
> >
> > An: “Windows System Software Devs Interest List”
> >
> > Kopie:
> > Thema: RE: [ntdev] Spinlocks
> >
> >
> >
> >
> >
> >
> >
> > As Peter said…
> >
> > However, if you find that other threads can modify the
> list, there may
> be
> > ways to avoid the spin-lock, if you can live with the side-effects:
> > 1. Don’t ever REMOVE entries from the list, just mark them invalid.
> > This means that you don’t have to worry about entries “going away”
> > whilst you’re working on them (doing p = p->next isn’t a
> good thing if
> > p isn’t valid because it’s been freed!).
> > 2. If you want to ADD things, make sure that it’s done in a
> safe manner.
> > This can be done in many different ways, but it’s fairly
> easy to use
> > the ExchangeInterLocked to write to the “next” pointer, which makes
> > the operation atomic. Of course, if the list if double
> linked, it may
> > be a
> bit
> > harder to achieve an atomic write.
> >
> > But one thing that’s always going to be a problem if you
> have multiple
> > threads access a list (or any other data structure) is what happens
> > when an entry isn’t consistant: Consider a delete of an
> element, just
> > after the element was found and passed on to some other place… so
> > this ‘other place’
> > is now using the element that is being deleted. Of course,
> spinlocks
> > on the list don’t help here, and you can’t always spinlock
> the entire
> > use of
> the
> > data that came out of the list (especially if you pass it to a
> > different piece of code than yours and for an undefined time). This
> > has to be
> worked
> > around by for instance having reference counts for the data in the
> > list, so that you can’t delete the count.
> >
> > Another thing to consider: If this code is ALWAYS running
> at passive
> > level, you can use for instance (fast)mutex’s to protect
> the code from
> > being re-entered. This will not help your code in itself,
> but it will
> > give the time waiting for the mutex to someone else, rather
> than using
> > a spinlock which just spins away the cycles in a tight loop. Most
> > unfriendly on
> other
> > tasks in the system. Of course, if this code runs at a higher than
> PASSIVE
> > IRQL, then you MUST use the spinlock, as asking the OS to
> wait for you
> > isn’t allowed at higher IRQL.
> >
> > –
> > Mats
> >
> >
> > xxxxx@lists.osr.com wrote on 09/13/2004 03:09:57 PM:
> >
> > > if another processor could be modifying this list at the
> same time
> > > then you have to have some protection. You’re the only
> one who can
> > > tell us whether “Create List Links” can be modified by another
> > > thread at the same time as this code is running. And
> once you tell
> > > us that you’ll have your answer.
> > >
> > > -p
> > >
> > > From: xxxxx@lists.osr.com [mailto:
> > > xxxxx@lists.osr.com] On Behalf Of Anurag Sarin
> > > Sent: Monday, September 13, 2004 6:27 AM
> > > To: Windows System Software Devs Interest List
> > > Subject: [ntdev] Spinlocks
> >
> > > If I have a code like this in my CREATE Dispatch routine.
> And if my
> > > Link List can be of 100 elements or more.
> > > ---------------------------------------------------
> > > Acquire Spin Lock
> > > If Create Link List has elements
> > > {
> > > If this filename found in Create Link List
> > > {
> > > Release Spin lock
> > > Return SpyPassthrough
> > > }
> > > }
> > > Release Spin lock
> > > ----------------------------------------------------
> > > Is there a need to do this operation using spin locks ? Will this
> > > lead to unexpected behavior or performance loss for my driver.
> > > Any comments ??
> > > Regards,
> > > Anurag
> > > —
> > > Questions? First check the Kernel Driver FAQ at http://www.
> > > osronline.com/article.cfm?id=256
> > >
> > > You are currently subscribed to ntdev as: unknown lmsubst tag
> argument:
> > ‘’
> > > To unsubscribe send a blank email to
> xxxxx@lists.osr.com
> > > —
> > > Questions? First check the Kernel Driver FAQ at http://www.
> > > osronline.com/article.cfm?id=256
> > >
> > > You are currently subscribed to ntdev as: unknown lmsubst tag
> argument:
> > ‘’
> > > To unsubscribe send a blank email to
> xxxxx@lists.osr.com
> > > ForwardSourceID:NT0000353E
> >
> >
> >
> > —
> > Questions? First check the Kernel Driver FAQ at
> > http://www.osronline.com/article.cfm?id=256
> >
> > You are currently subscribed to ntdev as: xxxxx@tab.at To
> unsubscribe
> > send a blank email to xxxxx@lists.osr.com
> >
> > Please visit us: www.tab.at www.championsnet.net
> > www.silverball.com
> >
> >
> >
> > —
> > Questions? First check the Kernel Driver FAQ at http://www.
> > osronline.com/article.cfm?id=256
> >
> > You are currently subscribed to ntdev as:
> xxxxx@3dlabs.com To
> > unsubscribe send a blank email to xxxxx@lists.osr.com
>
> > ForwardSourceID:NT00003572
>
>
>
> —
> Questions? First check the Kernel Driver FAQ at
> http://www.osronline.com/article.cfm?id=256
>
> You are currently subscribed to ntdev as: xxxxx@tab.at To
> unsubscribe send a blank email to xxxxx@lists.osr.com
>
> Please visit us: www.tab.at www.championsnet.net
> www.silverball.com
>
>
>
> —
> Questions? First check the Kernel Driver FAQ at
> http://www.osronline.com/article.cfm?id=256
>
> You are currently subscribed to ntdev as: xxxxx@garlic.com
> To unsubscribe send a blank email to xxxxx@lists.osr.com
>
>
>
>
>
> —
> Questions? First check the Kernel Driver FAQ at
> http://www.osronline.com/article.cfm?id=256
>
> You are currently subscribed to ntdev as: xxxxx@garlic.com
> To unsubscribe send a blank email to xxxxx@lists.osr.com
>
>
>
>
>
> —
> Questions? First check the Kernel Driver FAQ at
> http://www.osronline.com/article.cfm?id=256
>
> You are currently subscribed to ntdev as:
> xxxxx@windows.microsoft.com To unsubscribe send a blank
> email to xxxxx@lists.osr.com
>
Finally how bad is bad in terms of spin lock usage, if it is not too coarse
grained !
while ( lock !=0 & lock=1)
while (lock !=0 ) ;
Traffic jam doing bus locking ??? No not quite, this is optimized … as far
as it gets, of course I dont remember offhand all the ramification, but for
write-thru caches …
Yes may be I’m OT, but I’ve to make a point too. Frankly anytime we try to
do optimisation on our own hand, should be based on a comparative studies
along with the OS provided APIs, and please note I’m not trying to say or
object about the suggestion(s) others and mine too. There is a high
likelyhood that the implementor would be missing something, so I would first
evaluate what is in existence, does it fit my model, if not what lacks, and
how mine is better …
All the points are very good, I just wanted to give it a twist for good
discussion or to think about things that we might forget to consider …
that’s all !
Finally between cache and memory, what order of magnitude differences ???,
the hw providers would not go at length to comeup with 3 or more levels of
cache if memory speed were close to cache( ~ register) speeds …
-pro
-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of Prokash Sinha
Sent: Monday, September 13, 2004 9:30 AM
To: Windows System Software Devs Interest List
Subject: RE: [ntdev] Spinlocks
Also link list or any truely dynamically allocated structure is a pain in
the horrendous thinking from the cache-point-of-view, so any pre-fabricated
ddk/os provided api for TLB emulation would surely help here !!!
-pro
-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of Prokash Sinha
Sent: Monday, September 13, 2004 9:08 AM
To: Windows System Software Devs Interest List
Subject: RE: [ntdev] Spinlocks
Just dropping my A* wide open :-). Kick as you please
May be one or more thing to remember is not such the size of the list :).
How frequently
it would execute, it is possible that the list might not go over 300, and
each element ie. sizeof (struct node) might be 32 or 64 bytes, then ddk/os
provided TLB would be a choice . Sometime hash-collison, and the cost of
hash-function might become a overhead too !!. If it is on a really busy
execution path, hashing cost should be looked carefully too
-pro
-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of xxxxx@tab.at
Sent: Monday, September 13, 2004 8:41 AM
To: Windows System Software Devs Interest List
Subject: Re: [ntdev] Spinlocks
In this instance, being slow means less typing
Nah, in this instance I just typed a lot of food for my backspace key *g*
Fast “find” structures would be a really nice thing to have from the DDK.
If they were implemented in the DDK using one fixed block-size (for e.g.
b-trees) from one common lookaside-list (private lal optional?) and if the
implementation was fast and rock-solid they’d surely be a nice thing for
some driver-developers. Anything like an FS or even a firewall could
surely make use of that.
Anyway, for 100 entries max. I’d probably stick with a list, for 100+
entries avg. I’d prefer something else. With strings as keys (did someone
mention filenames?) I’d probably use some form of hash anyway
(adler32/crc32) - even if it’s only a list. The comparsion of one DWORD
vs. a whole string should also give some noticable speedup.
Regards,
Paul Groke
Mats PETERSSON
Gesendet von: xxxxx@lists.osr.com
13.09.2004 17:19
Bitte antworten an “Windows System Software Devs Interest List”
An: “Windows System Software Devs Interest List”
Kopie:
Thema: Re: [ntdev] Spinlocks
In this instance, being slow means less typing
Indeed a good suggestion, using a faster way to find the relevant data
doesn’t remove the problem, but it certainly helps reduce the locked time.
Good suggestion, I should’ve thought of it…
–
Mats
xxxxx@lists.osr.com wrote on 09/13/2004 04:13:59 PM:
> Ah, I’m always too slow One thing still left to say - you could
think
> about alternative data-structures if your list can get very big. Like
> hash-maps, b-trees or even a red-black-tree. That way you don’t avoid
the
> lock but you can reduce the time it takes to find one entry. The
downside
> is that the structures are more complicated and you have to allocate
> additional storage for them (at least for hash-map and b-tree).
>
> Regards,
>
> Paul Groke
>
>
>
>
>
> Mats PETERSSON
> Gesendet von: xxxxx@lists.osr.com
> 13.09.2004 16:40
> Bitte antworten an “Windows System Software Devs Interest List”
>
> An: “Windows System Software Devs Interest List”
>
> Kopie:
> Thema: RE: [ntdev] Spinlocks
>
>
>
>
>
>
>
> As Peter said…
>
> However, if you find that other threads can modify the list, there may
be
> ways to avoid the spin-lock, if you can live with the side-effects:
> 1. Don’t ever REMOVE entries from the list, just mark them invalid. This
> means that you don’t have to worry about entries “going away” whilst
> you’re
> working on them (doing p = p->next isn’t a good thing if p isn’t valid
> because it’s been freed!).
> 2. If you want to ADD things, make sure that it’s done in a safe manner.
> This can be done in many different ways, but it’s fairly easy to use the
> ExchangeInterLocked to write to the “next” pointer, which makes the
> operation atomic. Of course, if the list if double linked, it may be a
bit
> harder to achieve an atomic write.
>
> But one thing that’s always going to be a problem if you have multiple
> threads access a list (or any other data structure) is what happens when
> an
> entry isn’t consistant: Consider a delete of an element, just after the
> element was found and passed on to some other place… so this ‘other
> place’
> is now using the element that is being deleted. Of course, spinlocks on
> the
> list don’t help here, and you can’t always spinlock the entire use of
the
> data that came out of the list (especially if you pass it to a different
> piece of code than yours and for an undefined time). This has to be
worked
> around by for instance having reference counts for the data in the list,
> so
> that you can’t delete the count.
>
> Another thing to consider: If this code is ALWAYS running at passive
> level,
> you can use for instance (fast)mutex’s to protect the code from being
> re-entered. This will not help your code in itself, but it will give the
> time waiting for the mutex to someone else, rather than using a spinlock
> which just spins away the cycles in a tight loop. Most unfriendly on
other
> tasks in the system. Of course, if this code runs at a higher than
PASSIVE
> IRQL, then you MUST use the spinlock, as asking the OS to wait for you
> isn’t allowed at higher IRQL.
>
> –
> Mats
>
>
> xxxxx@lists.osr.com wrote on 09/13/2004 03:09:57 PM:
>
> > if another processor could be modifying this list at the same time
> > then you have to have some protection. You’re the only one who can
> > tell us whether “Create List Links” can be modified by another
> > thread at the same time as this code is running. And once you tell
> > us that you’ll have your answer.
> >
> > -p
> >
> > From: xxxxx@lists.osr.com [mailto:
> > xxxxx@lists.osr.com] On Behalf Of Anurag Sarin
> > Sent: Monday, September 13, 2004 6:27 AM
> > To: Windows System Software Devs Interest List
> > Subject: [ntdev] Spinlocks
>
> > If I have a code like this in my CREATE Dispatch routine. And if my
> > Link List can be of 100 elements or more.
> > ---------------------------------------------------
> > Acquire Spin Lock
> > If Create Link List has elements
> > {
> > If this filename found in Create Link List
> > {
> > Release Spin lock
> > Return SpyPassthrough
> > }
> > }
> > Release Spin lock
> > ----------------------------------------------------
> > Is there a need to do this operation using spin locks ? Will this
> > lead to unexpected behavior or performance loss for my driver.
> > Any comments ??
> > Regards,
> > Anurag
> > —
> > Questions? First check the Kernel Driver FAQ at http://www.
> > osronline.com/article.cfm?id=256
> >
> > You are currently subscribed to ntdev as: unknown lmsubst tag
argument:
> ‘’
> > To unsubscribe send a blank email to xxxxx@lists.osr.com
> > —
> > Questions? First check the Kernel Driver FAQ at http://www.
> > osronline.com/article.cfm?id=256
> >
> > You are currently subscribed to ntdev as: unknown lmsubst tag
argument:
> ‘’
> > To unsubscribe send a blank email to xxxxx@lists.osr.com
> > ForwardSourceID:NT0000353E
>
>
>
> —
> Questions? First check the Kernel Driver FAQ at
> http://www.osronline.com/article.cfm?id=256
>
> You are currently subscribed to ntdev as: xxxxx@tab.at
> To unsubscribe send a blank email to xxxxx@lists.osr.com
>
> Please visit us: www.tab.at www.championsnet.net
> www.silverball.com
>
>
>
> —
> Questions? First check the Kernel Driver FAQ at http://www.
> osronline.com/article.cfm?id=256
>
> You are currently subscribed to ntdev as: xxxxx@3dlabs.com
> To unsubscribe send a blank email to xxxxx@lists.osr.com
> ForwardSourceID:NT00003572
—
Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256
You are currently subscribed to ntdev as: xxxxx@tab.at
To unsubscribe send a blank email to xxxxx@lists.osr.com
Please visit us: www.tab.at www.championsnet.net
www.silverball.com
—
Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256
You are currently subscribed to ntdev as: xxxxx@garlic.com
To unsubscribe send a blank email to xxxxx@lists.osr.com
—
Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256
You are currently subscribed to ntdev as: xxxxx@garlic.com
To unsubscribe send a blank email to xxxxx@lists.osr.com
—
Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256
You are currently subscribed to ntdev as: xxxxx@garlic.com
To unsubscribe send a blank email to xxxxx@lists.osr.com
Yep, the thd should have ended right after your last note ! But weeds grows
by itself really, wild fires starts …
It is just an honest effort to make sure we have enough water, and good
fire-fighting engine at hand :-).
-pro
-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of Peter Wieland
Sent: Monday, September 13, 2004 10:03 AM
To: Windows System Software Devs Interest List
Subject: RE: [ntdev] Spinlocks
It would only “surely help here” if this is the sort of code path where
cache effects are likely to cause a noticible drop off in performance.
Given the length of the typical file-system create path (and this seems
to be a filter on top of those) I doubt that an OS provided cache is
going to solve anything here.
While I love the discussions we get when our threads spin off into the
weeds like this, it’s not always productive for the person who just
wants to know “do I need to have some synchronization here?”
-p
-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com] On Behalf Of Prokash Sinha
Sent: Monday, September 13, 2004 9:30 AM
To: Windows System Software Devs Interest List
Subject: RE: [ntdev] SpinlocksAlso link list or any truely dynamically allocated structure
is a pain in the horrendous thinking from the
cache-point-of-view, so any pre-fabricated ddk/os provided
api for TLB emulation would surely help here !!!-pro
-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of Prokash Sinha
Sent: Monday, September 13, 2004 9:08 AM
To: Windows System Software Devs Interest List
Subject: RE: [ntdev] SpinlocksJust dropping my A* wide open :-). Kick as you please
May be one or more thing to remember is not such the size of
the list :).
How frequently
it would execute, it is possible that the list might not go
over 300, and each element ie. sizeof (struct node) might be
32 or 64 bytes, then ddk/os provided TLB would be a choice .
Sometime hash-collison, and the cost of hash-function might
become a overhead too !!. If it is on a really busy execution
path, hashing cost should be looked carefully too-pro
-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of xxxxx@tab.at
Sent: Monday, September 13, 2004 8:41 AM
To: Windows System Software Devs Interest List
Subject: Re: [ntdev] Spinlocks> In this instance, being slow means less typing
Nah, in this instance I just typed a lot of food for my
backspace key *g* Fast “find” structures would be a really
nice thing to have from the DDK.
If they were implemented in the DDK using one fixed
block-size (for e.g.
b-trees) from one common lookaside-list (private lal
optional?) and if the implementation was fast and rock-solid
they’d surely be a nice thing for some driver-developers.
Anything like an FS or even a firewall could surely make use of that.Anyway, for 100 entries max. I’d probably stick with a list,
for 100+ entries avg. I’d prefer something else. With strings
as keys (did someone mention filenames?) I’d probably use
some form of hash anyway
(adler32/crc32) - even if it’s only a list. The comparsion of
one DWORD vs. a whole string should also give some noticable speedup.Regards,
Paul Groke
Mats PETERSSON Gesendet von:
> xxxxx@lists.osr.com
> 13.09.2004 17:19
> Bitte antworten an “Windows System Software Devs Interest List”
>
> An: “Windows System Software Devs Interest List”
>
> Kopie:
> Thema: Re: [ntdev] Spinlocks
>
>
>
>
>
>
>
> In this instance, being slow means less typing
>
> Indeed a good suggestion, using a faster way to find the
> relevant data doesn’t remove the problem, but it certainly
> helps reduce the locked time.
> Good suggestion, I should’ve thought of it…
>
> –
> Mats
>
> xxxxx@lists.osr.com wrote on 09/13/2004 04:13:59 PM:
>
> > Ah, I’m always too slow
> think
>
> > about alternative data-structures if your list can get very
> big. Like
> > hash-maps, b-trees or even a red-black-tree. That way you
> don’t avoid
> the
>
> > lock but you can reduce the time it takes to find one entry. The
> downside
>
> > is that the structures are more complicated and you have to
> allocate
> > additional storage for them (at least for hash-map and b-tree).
> >
> > Regards,
> >
> > Paul Groke
> >
> >
> >
> >
> >
> > Mats PETERSSON Gesendet von:
> > xxxxx@lists.osr.com
> > 13.09.2004 16:40
> > Bitte antworten an “Windows System Software Devs Interest List”
> >
> > An: “Windows System Software Devs Interest List”
> >
> > Kopie:
> > Thema: RE: [ntdev] Spinlocks
> >
> >
> >
> >
> >
> >
> >
> > As Peter said…
> >
> > However, if you find that other threads can modify the
> list, there may
> be
> > ways to avoid the spin-lock, if you can live with the side-effects:
> > 1. Don’t ever REMOVE entries from the list, just mark them invalid.
> > This means that you don’t have to worry about entries “going away”
> > whilst you’re working on them (doing p = p->next isn’t a
> good thing if
> > p isn’t valid because it’s been freed!).
> > 2. If you want to ADD things, make sure that it’s done in a
> safe manner.
> > This can be done in many different ways, but it’s fairly
> easy to use
> > the ExchangeInterLocked to write to the “next” pointer, which makes
> > the operation atomic. Of course, if the list if double
> linked, it may
> > be a
> bit
> > harder to achieve an atomic write.
> >
> > But one thing that’s always going to be a problem if you
> have multiple
> > threads access a list (or any other data structure) is what happens
> > when an entry isn’t consistant: Consider a delete of an
> element, just
> > after the element was found and passed on to some other place… so
> > this ‘other place’
> > is now using the element that is being deleted. Of course,
> spinlocks
> > on the list don’t help here, and you can’t always spinlock
> the entire
> > use of
> the
> > data that came out of the list (especially if you pass it to a
> > different piece of code than yours and for an undefined time). This
> > has to be
> worked
> > around by for instance having reference counts for the data in the
> > list, so that you can’t delete the count.
> >
> > Another thing to consider: If this code is ALWAYS running
> at passive
> > level, you can use for instance (fast)mutex’s to protect
> the code from
> > being re-entered. This will not help your code in itself,
> but it will
> > give the time waiting for the mutex to someone else, rather
> than using
> > a spinlock which just spins away the cycles in a tight loop. Most
> > unfriendly on
> other
> > tasks in the system. Of course, if this code runs at a higher than
> PASSIVE
> > IRQL, then you MUST use the spinlock, as asking the OS to
> wait for you
> > isn’t allowed at higher IRQL.
> >
> > –
> > Mats
> >
> >
> > xxxxx@lists.osr.com wrote on 09/13/2004 03:09:57 PM:
> >
> > > if another processor could be modifying this list at the
> same time
> > > then you have to have some protection. You’re the only
> one who can
> > > tell us whether “Create List Links” can be modified by another
> > > thread at the same time as this code is running. And
> once you tell
> > > us that you’ll have your answer.
> > >
> > > -p
> > >
> > > From: xxxxx@lists.osr.com [mailto:
> > > xxxxx@lists.osr.com] On Behalf Of Anurag Sarin
> > > Sent: Monday, September 13, 2004 6:27 AM
> > > To: Windows System Software Devs Interest List
> > > Subject: [ntdev] Spinlocks
> >
> > > If I have a code like this in my CREATE Dispatch routine.
> And if my
> > > Link List can be of 100 elements or more.
> > > ---------------------------------------------------
> > > Acquire Spin Lock
> > > If Create Link List has elements
> > > {
> > > If this filename found in Create Link List
> > > {
> > > Release Spin lock
> > > Return SpyPassthrough
> > > }
> > > }
> > > Release Spin lock
> > > ----------------------------------------------------
> > > Is there a need to do this operation using spin locks ? Will this
> > > lead to unexpected behavior or performance loss for my driver.
> > > Any comments ??
> > > Regards,
> > > Anurag
> > > —
> > > Questions? First check the Kernel Driver FAQ at http://www.
> > > osronline.com/article.cfm?id=256
> > >
> > > You are currently subscribed to ntdev as: unknown lmsubst tag
> argument:
> > ‘’
> > > To unsubscribe send a blank email to
> xxxxx@lists.osr.com
> > > —
> > > Questions? First check the Kernel Driver FAQ at http://www.
> > > osronline.com/article.cfm?id=256
> > >
> > > You are currently subscribed to ntdev as: unknown lmsubst tag
> argument:
> > ‘’
> > > To unsubscribe send a blank email to
> xxxxx@lists.osr.com
> > > ForwardSourceID:NT0000353E
> >
> >
> >
> > —
> > Questions? First check the Kernel Driver FAQ at
> > http://www.osronline.com/article.cfm?id=256
> >
> > You are currently subscribed to ntdev as: xxxxx@tab.at To
> unsubscribe
> > send a blank email to xxxxx@lists.osr.com
> >
> > Please visit us: www.tab.at www.championsnet.net
> > www.silverball.com
> >
> >
> >
> > —
> > Questions? First check the Kernel Driver FAQ at http://www.
> > osronline.com/article.cfm?id=256
> >
> > You are currently subscribed to ntdev as:
> xxxxx@3dlabs.com To
> > unsubscribe send a blank email to xxxxx@lists.osr.com
>
> > ForwardSourceID:NT00003572
>
>
>
> —
> Questions? First check the Kernel Driver FAQ at
> http://www.osronline.com/article.cfm?id=256
>
> You are currently subscribed to ntdev as: xxxxx@tab.at To
> unsubscribe send a blank email to xxxxx@lists.osr.com
>
> Please visit us: www.tab.at www.championsnet.net
> www.silverball.com
>
>
>
> —
> Questions? First check the Kernel Driver FAQ at
> http://www.osronline.com/article.cfm?id=256
>
> You are currently subscribed to ntdev as: xxxxx@garlic.com
> To unsubscribe send a blank email to xxxxx@lists.osr.com
>
>
>
>
>
> —
> Questions? First check the Kernel Driver FAQ at
> http://www.osronline.com/article.cfm?id=256
>
> You are currently subscribed to ntdev as: xxxxx@garlic.com
> To unsubscribe send a blank email to xxxxx@lists.osr.com
>
>
>
>
>
> —
> Questions? First check the Kernel Driver FAQ at
> http://www.osronline.com/article.cfm?id=256
>
> You are currently subscribed to ntdev as:
> xxxxx@windows.microsoft.com To unsubscribe send a blank
> email to xxxxx@lists.osr.com
>
—
Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256
You are currently subscribed to ntdev as: unknown lmsubst tag argument: ‘’
To unsubscribe send a blank email to xxxxx@lists.osr.com
I read the question differently -- not is synchronization needed, but are
spinlocks (specifically) needed? Windows has a rich and diverse zoo of
sync'n objects; why use spinlocks here? Monopolizing the processor and
retaining an exclusive lock where a shared mode may suffice, while
performing 100 string compares, seem worth questioning. ERESOURCEs could
considered, for example.
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com] On Behalf Of Peter Wieland
Sent: Monday, September 13, 2004 7:10 AM
To: Windows System Software Devs Interest List
Subject: RE: [ntdev] Spinlocks
if another processor could be modifying this list at the same time then you
have to have some protection. You're the only one who can tell us whether
"Create List Links" can be modified by another thread at the same time as
this code is running. And once you tell us that you'll have your answer.
-p
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com] On Behalf Of Anurag Sarin
Sent: Monday, September 13, 2004 6:27 AM
To: Windows System Software Devs Interest List
Subject: [ntdev] Spinlocks
Is there a need to do this operation using spin locks ? Will this lead to
unexpected behavior or performance loss for my driver.
Any comments ??
Regards,
Anurag
Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256
You are currently subscribed to ntdev as: unknown lmsubst tag argument: ''
To unsubscribe send a blank email to xxxxx@lists.osr.com
Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256
You are currently subscribed to ntdev as: unknown lmsubst tag argument: ''
To unsubscribe send a blank email to xxxxx@lists.osr.com
Well I am glad to provide a spark for a power full discussion.
My driver is for single processer systems. And I have a code to add the
elements in the list if not found in the loopp mentioned below.
I finally under stand that I would keep the spin locks and need
syncronization here as my next code after this is to add more elements
in the same list.
Change my data structure to another structure and another searching
methord hike hash table will lead to rework for which I have no time at
the moment.
Thanks & Regards,
Anurag
-----Original Message-----
From: Peter Wieland [mailto:xxxxx@windows.microsoft.com]
Sent: Monday, September 13, 2004 10:33 PM
To: Windows System Software Devs Interest List
Subject: RE: [ntdev] Spinlocks
It would only “surely help here” if this is the sort of code path where
cache effects are likely to cause a noticible drop off in performance.
Given the length of the typical file-system create path (and this seems
to be a filter on top of those) I doubt that an OS provided cache is
going to solve anything here.
While I love the discussions we get when our threads spin off into the
weeds like this, it’s not always productive for the person who just
wants to know “do I need to have some synchronization here?”
-p
-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com] On Behalf Of Prokash Sinha
Sent: Monday, September 13, 2004 9:30 AM
To: Windows System Software Devs Interest List
Subject: RE: [ntdev] SpinlocksAlso link list or any truely dynamically allocated structure
is a pain in the horrendous thinking from the
cache-point-of-view, so any pre-fabricated ddk/os provided
api for TLB emulation would surely help here !!!-pro
-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of Prokash Sinha
Sent: Monday, September 13, 2004 9:08 AM
To: Windows System Software Devs Interest List
Subject: RE: [ntdev] SpinlocksJust dropping my A* wide open :-). Kick as you please
May be one or more thing to remember is not such the size of
the list :).
How frequently
it would execute, it is possible that the list might not go
over 300, and each element ie. sizeof (struct node) might be
32 or 64 bytes, then ddk/os provided TLB would be a choice .
Sometime hash-collison, and the cost of hash-function might
become a overhead too !!. If it is on a really busy execution
path, hashing cost should be looked carefully too-pro
-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of xxxxx@tab.at
Sent: Monday, September 13, 2004 8:41 AM
To: Windows System Software Devs Interest List
Subject: Re: [ntdev] Spinlocks> In this instance, being slow means less typing
Nah, in this instance I just typed a lot of food for my
backspace key *g* Fast “find” structures would be a really
nice thing to have from the DDK.
If they were implemented in the DDK using one fixed
block-size (for e.g.
b-trees) from one common lookaside-list (private lal
optional?) and if the implementation was fast and rock-solid
they’d surely be a nice thing for some driver-developers.
Anything like an FS or even a firewall could surely make use of that.Anyway, for 100 entries max. I’d probably stick with a list,
for 100+ entries avg. I’d prefer something else. With strings
as keys (did someone mention filenames?) I’d probably use
some form of hash anyway
(adler32/crc32) - even if it’s only a list. The comparsion of
one DWORD vs. a whole string should also give some noticable speedup.Regards,
Paul Groke
Mats PETERSSON Gesendet von:
> xxxxx@lists.osr.com
> 13.09.2004 17:19
> Bitte antworten an “Windows System Software Devs Interest List”
>
> An: “Windows System Software Devs Interest List”
>
> Kopie:
> Thema: Re: [ntdev] Spinlocks
>
>
>
>
>
>
>
> In this instance, being slow means less typing
>
> Indeed a good suggestion, using a faster way to find the
> relevant data doesn’t remove the problem, but it certainly
> helps reduce the locked time.
> Good suggestion, I should’ve thought of it…
>
> –
> Mats
>
> xxxxx@lists.osr.com wrote on 09/13/2004 04:13:59 PM:
>
> > Ah, I’m always too slow
> think
>
> > about alternative data-structures if your list can get very
> big. Like
> > hash-maps, b-trees or even a red-black-tree. That way you
> don’t avoid
> the
>
> > lock but you can reduce the time it takes to find one entry. The
> downside
>
> > is that the structures are more complicated and you have to
> allocate
> > additional storage for them (at least for hash-map and b-tree).
> >
> > Regards,
> >
> > Paul Groke
> >
> >
> >
> >
> >
> > Mats PETERSSON Gesendet von:
> > xxxxx@lists.osr.com
> > 13.09.2004 16:40
> > Bitte antworten an “Windows System Software Devs Interest List”
> >
> > An: “Windows System Software Devs Interest List”
> >
> > Kopie:
> > Thema: RE: [ntdev] Spinlocks
> >
> >
> >
> >
> >
> >
> >
> > As Peter said…
> >
> > However, if you find that other threads can modify the
> list, there may
> be
> > ways to avoid the spin-lock, if you can live with the side-effects:
> > 1. Don’t ever REMOVE entries from the list, just mark them invalid.
> > This means that you don’t have to worry about entries “going away”
> > whilst you’re working on them (doing p = p->next isn’t a
> good thing if
> > p isn’t valid because it’s been freed!).
> > 2. If you want to ADD things, make sure that it’s done in a
> safe manner.
> > This can be done in many different ways, but it’s fairly
> easy to use
> > the ExchangeInterLocked to write to the “next” pointer, which makes
> > the operation atomic. Of course, if the list if double
> linked, it may
> > be a
> bit
> > harder to achieve an atomic write.
> >
> > But one thing that’s always going to be a problem if you
> have multiple
> > threads access a list (or any other data structure) is what happens
> > when an entry isn’t consistant: Consider a delete of an
> element, just
> > after the element was found and passed on to some other place… so
> > this ‘other place’
> > is now using the element that is being deleted. Of course,
> spinlocks
> > on the list don’t help here, and you can’t always spinlock
> the entire
> > use of
> the
> > data that came out of the list (especially if you pass it to a
> > different piece of code than yours and for an undefined time). This
> > has to be
> worked
> > around by for instance having reference counts for the data in the
> > list, so that you can’t delete the count.
> >
> > Another thing to consider: If this code is ALWAYS running
> at passive
> > level, you can use for instance (fast)mutex’s to protect
> the code from
> > being re-entered. This will not help your code in itself,
> but it will
> > give the time waiting for the mutex to someone else, rather
> than using
> > a spinlock which just spins away the cycles in a tight loop. Most
> > unfriendly on
> other
> > tasks in the system. Of course, if this code runs at a higher than
> PASSIVE
> > IRQL, then you MUST use the spinlock, as asking the OS to
> wait for you
> > isn’t allowed at higher IRQL.
> >
> > –
> > Mats
> >
> >
> > xxxxx@lists.osr.com wrote on 09/13/2004 03:09:57 PM:
> >
> > > if another processor could be modifying this list at the
> same time
> > > then you have to have some protection. You’re the only
> one who can
> > > tell us whether “Create List Links” can be modified by another
> > > thread at the same time as this code is running. And
> once you tell
> > > us that you’ll have your answer.
> > >
> > > -p
> > >
> > > From: xxxxx@lists.osr.com [mailto:
> > > xxxxx@lists.osr.com] On Behalf Of Anurag Sarin
> > > Sent: Monday, September 13, 2004 6:27 AM
> > > To: Windows System Software Devs Interest List
> > > Subject: [ntdev] Spinlocks
> >
> > > If I have a code like this in my CREATE Dispatch routine.
> And if my
> > > Link List can be of 100 elements or more.
> > > ---------------------------------------------------
> > > Acquire Spin Lock
> > > If Create Link List has elements
> > > {
> > > If this filename found in Create Link List
> > > {
> > > Release Spin lock
> > > Return SpyPassthrough
> > > }
> > > }
> > > Release Spin lock
> > > ----------------------------------------------------
> > > Is there a need to do this operation using spin locks ? Will this
> > > lead to unexpected behavior or performance loss for my driver.
> > > Any comments ??
> > > Regards,
> > > Anurag
> > > —
> > > Questions? First check the Kernel Driver FAQ at http://www.
> > > osronline.com/article.cfm?id=256
> > >
> > > You are currently subscribed to ntdev as: unknown lmsubst tag
> argument:
> > ‘’
> > > To unsubscribe send a blank email to
> xxxxx@lists.osr.com
> > > —
> > > Questions? First check the Kernel Driver FAQ at http://www.
> > > osronline.com/article.cfm?id=256
> > >
> > > You are currently subscribed to ntdev as: unknown lmsubst tag
> argument:
> > ‘’
> > > To unsubscribe send a blank email to
> xxxxx@lists.osr.com
> > > ForwardSourceID:NT0000353E
> >
> >
> >
> > —
> > Questions? First check the Kernel Driver FAQ at
> > http://www.osronline.com/article.cfm?id=256
> >
> > You are currently subscribed to ntdev as: xxxxx@tab.at To
> unsubscribe
> > send a blank email to xxxxx@lists.osr.com
> >
> > Please visit us: www.tab.at www.championsnet.net
> > www.silverball.com
> >
> >
> >
> > —
> > Questions? First check the Kernel Driver FAQ at http://www.
> > osronline.com/article.cfm?id=256
> >
> > You are currently subscribed to ntdev as:
> xxxxx@3dlabs.com To
> > unsubscribe send a blank email to xxxxx@lists.osr.com
>
> > ForwardSourceID:NT00003572
>
>
>
> —
> Questions? First check the Kernel Driver FAQ at
> http://www.osronline.com/article.cfm?id=256
>
> You are currently subscribed to ntdev as: xxxxx@tab.at To
> unsubscribe send a blank email to xxxxx@lists.osr.com
>
> Please visit us: www.tab.at www.championsnet.net
> www.silverball.com
>
>
>
> —
> Questions? First check the Kernel Driver FAQ at
> http://www.osronline.com/article.cfm?id=256
>
> You are currently subscribed to ntdev as: xxxxx@garlic.com
> To unsubscribe send a blank email to xxxxx@lists.osr.com
>
>
>
>
>
> —
> Questions? First check the Kernel Driver FAQ at
> http://www.osronline.com/article.cfm?id=256
>
> You are currently subscribed to ntdev as: xxxxx@garlic.com
> To unsubscribe send a blank email to xxxxx@lists.osr.com
>
>
>
>
>
> —
> Questions? First check the Kernel Driver FAQ at
> http://www.osronline.com/article.cfm?id=256
>
> You are currently subscribed to ntdev as:
> xxxxx@windows.microsoft.com To unsubscribe send a blank
> email to xxxxx@lists.osr.com
>
—
Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256
You are currently subscribed to ntdev as: unknown lmsubst tag argument:
‘’
To unsubscribe send a blank email to xxxxx@lists.osr.com
How do you know that your driver will only be run on a single-processor
system? what about HyperThreading single processor, is that not allowed
either?
Sorry, but unless your driver is written to only work on a specific
hardware platform that doesn’t have options to change the processor, then
it’s very likely that sometime soon, you’ll be forced to accept that the
driver will need to restist multiprocessor systems.
–
Mats
xxxxx@lists.osr.com wrote on 09/14/2004 01:06:49 PM:
Well I am glad to provide a spark for a power full discussion.
My driver is for single processer systems. And I have a code to add the
elements in the list if not found in the loopp mentioned below.
I finally under stand that I would keep the spin locks and need
syncronization here as my next code after this is to add more elements
in the same list.
Change my data structure to another structure and another searching
methord hike hash table will lead to rework for which I have no time at
the moment.Thanks & Regards,
Anurag-----Original Message-----
From: Peter Wieland [mailto:xxxxx@windows.microsoft.com]
Sent: Monday, September 13, 2004 10:33 PM
To: Windows System Software Devs Interest List
Subject: RE: [ntdev] SpinlocksIt would only “surely help here” if this is the sort of code path where
cache effects are likely to cause a noticible drop off in performance.
Given the length of the typical file-system create path (and this seems
to be a filter on top of those) I doubt that an OS provided cache is
going to solve anything here.While I love the discussions we get when our threads spin off into the
weeds like this, it’s not always productive for the person who just
wants to know “do I need to have some synchronization here?”-p
> -----Original Message-----
> From: xxxxx@lists.osr.com
> [mailto:xxxxx@lists.osr.com] On Behalf Of Prokash Sinha
> Sent: Monday, September 13, 2004 9:30 AM
> To: Windows System Software Devs Interest List
> Subject: RE: [ntdev] Spinlocks
>
> Also link list or any truely dynamically allocated structure
> is a pain in the horrendous thinking from the
> cache-point-of-view, so any pre-fabricated ddk/os provided
> api for TLB emulation would surely help here !!!
>
> -pro
>
> -----Original Message-----
> From: xxxxx@lists.osr.com
> [mailto:xxxxx@lists.osr.com]On Behalf Of Prokash Sinha
> Sent: Monday, September 13, 2004 9:08 AM
> To: Windows System Software Devs Interest List
> Subject: RE: [ntdev] Spinlocks
>
>
> Just dropping my A* wide open :-). Kick as you please
>
> May be one or more thing to remember is not such the size of
> the list :).
> How frequently
> it would execute, it is possible that the list might not go
> over 300, and each element ie. sizeof (struct node) might be
> 32 or 64 bytes, then ddk/os provided TLB would be a choice .
> Sometime hash-collison, and the cost of hash-function might
> become a overhead too !!. If it is on a really busy execution
> path, hashing cost should be looked carefully too
>
> -pro
>
> -----Original Message-----
> From: xxxxx@lists.osr.com
> [mailto:xxxxx@lists.osr.com]On Behalf Of xxxxx@tab.at
> Sent: Monday, September 13, 2004 8:41 AM
> To: Windows System Software Devs Interest List
> Subject: Re: [ntdev] Spinlocks
>
>
> > In this instance, being slow means less typing
>
> Nah, in this instance I just typed a lot of food for my
> backspace key *g* Fast “find” structures would be a really
> nice thing to have from the DDK.
> If they were implemented in the DDK using one fixed
> block-size (for e.g.
> b-trees) from one common lookaside-list (private lal
> optional?) and if the implementation was fast and rock-solid
> they’d surely be a nice thing for some driver-developers.
> Anything like an FS or even a firewall could surely make use of that.
>
> Anyway, for 100 entries max. I’d probably stick with a list,
> for 100+ entries avg. I’d prefer something else. With strings
> as keys (did someone mention filenames?) I’d probably use
> some form of hash anyway
> (adler32/crc32) - even if it’s only a list. The comparsion of
> one DWORD vs. a whole string should also give some noticable speedup.
>
> Regards,
>
> Paul Groke
>
>
>
>
>
> Mats PETERSSON Gesendet von:
> > xxxxx@lists.osr.com
> > 13.09.2004 17:19
> > Bitte antworten an “Windows System Software Devs Interest List”
> >
> > An: “Windows System Software Devs Interest List”
> >
> > Kopie:
> > Thema: Re: [ntdev] Spinlocks
> >
> >
> >
> >
> >
> >
> >
> > In this instance, being slow means less typing
> >
> > Indeed a good suggestion, using a faster way to find the
> > relevant data doesn’t remove the problem, but it certainly
> > helps reduce the locked time.
> > Good suggestion, I should’ve thought of it…
> >
> > –
> > Mats
> >
> > xxxxx@lists.osr.com wrote on 09/13/2004 04:13:59 PM:
> >
> > > Ah, I’m always too slow
> > think
> >
> > > about alternative data-structures if your list can get very
> > big. Like
> > > hash-maps, b-trees or even a red-black-tree. That way you
> > don’t avoid
> > the
> >
> > > lock but you can reduce the time it takes to find one entry. The
> > downside
> >
> > > is that the structures are more complicated and you have to
> > allocate
> > > additional storage for them (at least for hash-map and b-tree).
> > >
> > > Regards,
> > >
> > > Paul Groke
> > >
> > >
> > >
> > >
> > >
> > > Mats PETERSSON Gesendet von:
> > > xxxxx@lists.osr.com
> > > 13.09.2004 16:40
> > > Bitte antworten an “Windows System Software Devs Interest List”
> > >
> > > An: “Windows System Software Devs Interest List”
> > >
> > > Kopie:
> > > Thema: RE: [ntdev] Spinlocks
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > > As Peter said…
> > >
> > > However, if you find that other threads can modify the
> > list, there may
> > be
> > > ways to avoid the spin-lock, if you can live with the side-effects:
> > > 1. Don’t ever REMOVE entries from the list, just mark them invalid.
> > > This means that you don’t have to worry about entries “going away”
> > > whilst you’re working on them (doing p = p->next isn’t a
> > good thing if
> > > p isn’t valid because it’s been freed!).
> > > 2. If you want to ADD things, make sure that it’s done in a
> > safe manner.
> > > This can be done in many different ways, but it’s fairly
> > easy to use
> > > the ExchangeInterLocked to write to the “next” pointer, which makes
> > > the operation atomic. Of course, if the list if double
> > linked, it may
> > > be a
> > bit
> > > harder to achieve an atomic write.
> > >
> > > But one thing that’s always going to be a problem if you
> > have multiple
> > > threads access a list (or any other data structure) is what happens
> > > when an entry isn’t consistant: Consider a delete of an
> > element, just
> > > after the element was found and passed on to some other place… so
> > > this ‘other place’
> > > is now using the element that is being deleted. Of course,
> > spinlocks
> > > on the list don’t help here, and you can’t always spinlock
> > the entire
> > > use of
> > the
> > > data that came out of the list (especially if you pass it to a
> > > different piece of code than yours and for an undefined time). This
> > > has to be
> > worked
> > > around by for instance having reference counts for the data in the
> > > list, so that you can’t delete the count.
> > >
> > > Another thing to consider: If this code is ALWAYS running
> > at passive
> > > level, you can use for instance (fast)mutex’s to protect
> > the code from
> > > being re-entered. This will not help your code in itself,
> > but it will
> > > give the time waiting for the mutex to someone else, rather
> > than using
> > > a spinlock which just spins away the cycles in a tight loop. Most
> > > unfriendly on
> > other
> > > tasks in the system. Of course, if this code runs at a higher than
> > PASSIVE
> > > IRQL, then you MUST use the spinlock, as asking the OS to
> > wait for you
> > > isn’t allowed at higher IRQL.
> > >
> > > –
> > > Mats
> > >
> > >
> > > xxxxx@lists.osr.com wrote on 09/13/2004 03:09:57 PM:
> > >
> > > > if another processor could be modifying this list at the
> > same time
> > > > then you have to have some protection. You’re the only
> > one who can
> > > > tell us whether “Create List Links” can be modified by another
> > > > thread at the same time as this code is running. And
> > once you tell
> > > > us that you’ll have your answer.
> > > >
> > > > -p
> > > >
> > > > From: xxxxx@lists.osr.com [mailto:
> > > > xxxxx@lists.osr.com] On Behalf Of Anurag Sarin
> > > > Sent: Monday, September 13, 2004 6:27 AM
> > > > To: Windows System Software Devs Interest List
> > > > Subject: [ntdev] Spinlocks
> > >
> > > > If I have a code like this in my CREATE Dispatch routine.
> > And if my
> > > > Link List can be of 100 elements or more.
> > > > ---------------------------------------------------
> > > > Acquire Spin Lock
> > > > If Create Link List has elements
> > > > {
> > > > If this filename found in Create Link List
> > > > {
> > > > Release Spin lock
> > > > Return SpyPassthrough
> > > > }
> > > > }
> > > > Release Spin lock
> > > > ----------------------------------------------------
> > > > Is there a need to do this operation using spin locks ? Will this
> > > > lead to unexpected behavior or performance loss for my driver.
> > > > Any comments ??
> > > > Regards,
> > > > Anurag
> > > > —
> > > > Questions? First check the Kernel Driver FAQ at http://www.
> > > > osronline.com/article.cfm?id=256
> > > >
> > > > You are currently subscribed to ntdev as: unknown lmsubst tag
> > argument:
> > > ‘’
> > > > To unsubscribe send a blank email to
> > xxxxx@lists.osr.com
> > > > —
> > > > Questions? First check the Kernel Driver FAQ at http://www.
> > > > osronline.com/article.cfm?id=256
> > > >
> > > > You are currently subscribed to ntdev as: unknown lmsubst tag
> > argument:
> > > ‘’
> > > > To unsubscribe send a blank email to
> > xxxxx@lists.osr.com
> > > > ForwardSourceID:NT0000353E
> > >
> > >
> > >
> > > —
> > > Questions? First check the Kernel Driver FAQ at
> > > http://www.osronline.com/article.cfm?id=256
> > >
> > > You are currently subscribed to ntdev as: xxxxx@tab.at To
> > unsubscribe
> > > send a blank email to xxxxx@lists.osr.com
> > >
> > > Please visit us: www.tab.at www.championsnet.net
> > > www.silverball.com
> > >
> > >
> > >
> > > —
> > > Questions? First check the Kernel Driver FAQ at http://www.
> > > osronline.com/article.cfm?id=256
> > >
> > > You are currently subscribed to ntdev as:
> > xxxxx@3dlabs.com To
> > > unsubscribe send a blank email to xxxxx@lists.osr.com
> >
> > > ForwardSourceID:NT00003572
> >
> >
> >
> > —
> > Questions? First check the Kernel Driver FAQ at
> > http://www.osronline.com/article.cfm?id=256
> >
> > You are currently subscribed to ntdev as: xxxxx@tab.at To
> > unsubscribe send a blank email to xxxxx@lists.osr.com
> >
> > Please visit us: www.tab.at www.championsnet.net
> > www.silverball.com
> >
> >
> >
> > —
> > Questions? First check the Kernel Driver FAQ at
> > http://www.osronline.com/article.cfm?id=256
> >
> > You are currently subscribed to ntdev as: xxxxx@garlic.com
> > To unsubscribe send a blank email to xxxxx@lists.osr.com
> >
> >
> >
> >
> >
> > —
> > Questions? First check the Kernel Driver FAQ at
> > http://www.osronline.com/article.cfm?id=256
> >
> > You are currently subscribed to ntdev as: xxxxx@garlic.com
> > To unsubscribe send a blank email to xxxxx@lists.osr.com
> >
> >
> >
> >
> >
> > —
> > Questions? First check the Kernel Driver FAQ at
> > http://www.osronline.com/article.cfm?id=256
> >
> > You are currently subscribed to ntdev as:
> > xxxxx@windows.microsoft.com To unsubscribe send a blank
> > email to xxxxx@lists.osr.com
> >
>
>
> —
> Questions? First check the Kernel Driver FAQ at
> http://www.osronline.com/article.cfm?id=256
>
> You are currently subscribed to ntdev as: unknown lmsubst tag argument:
> ‘’
> To unsubscribe send a blank email to xxxxx@lists.osr.com
>
>
>
> —
> Questions? First check the Kernel Driver FAQ at http://www.
> osronline.com/article.cfm?id=256
>
> You are currently subscribed to ntdev as: unknown lmsubst tag argument:
‘’
> To unsubscribe send a blank email to xxxxx@lists.osr.com
> ForwardSourceID:NT000036C2
Anurag, do you have any place where you have to access that list from
DISPATCH_LEVEL or higher? If not you could still think of using a
FAST_MUTEX or another synchronization-primitive. The code would be 95% the
same (no structural changes), the speed should be about the same for
FAST_MUTEX (as I am told) and it would cooperate more smoothly on MP as
well as UP. You can use a spinlock, it’s just very likely not “optimal”
for 100+ string-compares.
Regards,
Paul
Mats PETERSSON
Gesendet von: xxxxx@lists.osr.com
14.09.2004 14:16
Bitte antworten an “Windows System Software Devs Interest List”
An: “Windows System Software Devs Interest List”
Kopie:
Thema: RE: [ntdev] Spinlocks
How do you know that your driver will only be run on a single-processor
system? what about HyperThreading single processor, is that not allowed
either?
Sorry, but unless your driver is written to only work on a specific
hardware platform that doesn’t have options to change the processor, then
it’s very likely that sometime soon, you’ll be forced to accept that the
driver will need to restist multiprocessor systems.
–
Mats
xxxxx@lists.osr.com wrote on 09/14/2004 01:06:49 PM:
> Well I am glad to provide a spark for a power full discussion.
>
> My driver is for single processer systems. And I have a code to add the
> elements in the list if not found in the loopp mentioned below.
> I finally under stand that I would keep the spin locks and need
> syncronization here as my next code after this is to add more elements
> in the same list.
> Change my data structure to another structure and another searching
> methord hike hash table will lead to rework for which I have no time at
> the moment.
>
>
> Thanks & Regards,
> Anurag
>
> -----Original Message-----
> From: Peter Wieland [mailto:xxxxx@windows.microsoft.com]
> Sent: Monday, September 13, 2004 10:33 PM
> To: Windows System Software Devs Interest List
> Subject: RE: [ntdev] Spinlocks
>
>
> It would only “surely help here” if this is the sort of code path where
> cache effects are likely to cause a noticible drop off in performance.
> Given the length of the typical file-system create path (and this seems
> to be a filter on top of those) I doubt that an OS provided cache is
> going to solve anything here.
>
> While I love the discussions we get when our threads spin off into the
> weeds like this, it’s not always productive for the person who just
> wants to know “do I need to have some synchronization here?”
>
> -p
>
> > -----Original Message-----
> > From: xxxxx@lists.osr.com
> > [mailto:xxxxx@lists.osr.com] On Behalf Of Prokash Sinha
> > Sent: Monday, September 13, 2004 9:30 AM
> > To: Windows System Software Devs Interest List
> > Subject: RE: [ntdev] Spinlocks
> >
> > Also link list or any truely dynamically allocated structure
> > is a pain in the horrendous thinking from the
> > cache-point-of-view, so any pre-fabricated ddk/os provided
> > api for TLB emulation would surely help here !!!
> >
> > -pro
> >
> > -----Original Message-----
> > From: xxxxx@lists.osr.com
> > [mailto:xxxxx@lists.osr.com]On Behalf Of Prokash Sinha
> > Sent: Monday, September 13, 2004 9:08 AM
> > To: Windows System Software Devs Interest List
> > Subject: RE: [ntdev] Spinlocks
> >
> >
> > Just dropping my A* wide open :-). Kick as you please
> >
> > May be one or more thing to remember is not such the size of
> > the list :).
> > How frequently
> > it would execute, it is possible that the list might not go
> > over 300, and each element ie. sizeof (struct node) might be
> > 32 or 64 bytes, then ddk/os provided TLB would be a choice .
> > Sometime hash-collison, and the cost of hash-function might
> > become a overhead too !!. If it is on a really busy execution
> > path, hashing cost should be looked carefully too
> >
> > -pro
> >
> > -----Original Message-----
> > From: xxxxx@lists.osr.com
> > [mailto:xxxxx@lists.osr.com]On Behalf Of xxxxx@tab.at
> > Sent: Monday, September 13, 2004 8:41 AM
> > To: Windows System Software Devs Interest List
> > Subject: Re: [ntdev] Spinlocks
> >
> >
> > > In this instance, being slow means less typing
> >
> > Nah, in this instance I just typed a lot of food for my
> > backspace key g Fast “find” structures would be a really
> > nice thing to have from the DDK.
> > If they were implemented in the DDK using one fixed
> > block-size (for e.g.
> > b-trees) from one common lookaside-list (private lal
> > optional?) and if the implementation was fast and rock-solid
> > they’d surely be a nice thing for some driver-developers.
> > Anything like an FS or even a firewall could surely make use of that.
> >
> > Anyway, for 100 entries max. I’d probably stick with a list,
> > for 100+ entries avg. I’d prefer something else. With strings
> > as keys (did someone mention filenames?) I’d probably use
> > some form of hash anyway
> > (adler32/crc32) - even if it’s only a list. The comparsion of
> > one DWORD vs. a whole string should also give some noticable speedup.
> >
> > Regards,
> >
> > Paul Groke
> >
> >
> >
> >
> >
> > Mats PETERSSON Gesendet von:
> > xxxxx@lists.osr.com
> > 13.09.2004 17:19
> > Bitte antworten an “Windows System Software Devs Interest List”
> >
> > An: “Windows System Software Devs Interest List”
> >
> > Kopie:
> > Thema: Re: [ntdev] Spinlocks
> >
> >
> >
> >
> >
> >
> >
> > In this instance, being slow means less typing
> >
> > Indeed a good suggestion, using a faster way to find the
> > relevant data doesn’t remove the problem, but it certainly
> > helps reduce the locked time.
> > Good suggestion, I should’ve thought of it…
> >
> > –
> > Mats
> >
> > xxxxx@lists.osr.com wrote on 09/13/2004 04:13:59 PM:
> >
> > > Ah, I’m always too slow One thing still left to say - you could
> > think
> >
> > > about alternative data-structures if your list can get very
> > big. Like
> > > hash-maps, b-trees or even a red-black-tree. That way you
> > don’t avoid
> > the
> >
> > > lock but you can reduce the time it takes to find one entry. The
> > downside
> >
> > > is that the structures are more complicated and you have to
> > allocate
> > > additional storage for them (at least for hash-map and b-tree).
> > >
> > > Regards,
> > >
> > > Paul Groke
> > >
> > >
> > >
> > >
> > >
> > > Mats PETERSSON Gesendet von:
> > > xxxxx@lists.osr.com
> > > 13.09.2004 16:40
> > > Bitte antworten an “Windows System Software Devs Interest List”
> > >
> > > An: “Windows System Software Devs Interest List”
> > >
> > > Kopie:
> > > Thema: RE: [ntdev] Spinlocks
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > > As Peter said…
> > >
> > > However, if you find that other threads can modify the
> > list, there may
> > be
> > > ways to avoid the spin-lock, if you can live with the side-effects:
> > > 1. Don’t ever REMOVE entries from the list, just mark them invalid.
> > > This means that you don’t have to worry about entries “going away”
> > > whilst you’re working on them (doing p = p->next isn’t a
> > good thing if
> > > p isn’t valid because it’s been freed!).
> > > 2. If you want to ADD things, make sure that it’s done in a
> > safe manner.
> > > This can be done in many different ways, but it’s fairly
> > easy to use
> > > the ExchangeInterLocked to write to the “next” pointer, which makes
> > > the operation atomic. Of course, if the list if double
> > linked, it may
> > > be a
> > bit
> > > harder to achieve an atomic write.
> > >
> > > But one thing that’s always going to be a problem if you
> > have multiple
> > > threads access a list (or any other data structure) is what happens
> > > when an entry isn’t consistant: Consider a delete of an
> > element, just
> > > after the element was found and passed on to some other place… so
> > > this ‘other place’
> > > is now using the element that is being deleted. Of course,
> > spinlocks
> > > on the list don’t help here, and you can’t always spinlock
> > the entire
> > > use of
> > the
> > > data that came out of the list (especially if you pass it to a
> > > different piece of code than yours and for an undefined time). This
> > > has to be
> > worked
> > > around by for instance having reference counts for the data in the
> > > list, so that you can’t delete the count.
> > >
> > > Another thing to consider: If this code is ALWAYS running
> > at passive
> > > level, you can use for instance (fast)mutex’s to protect
> > the code from
> > > being re-entered. This will not help your code in itself,
> > but it will
> > > give the time waiting for the mutex to someone else, rather
> > than using
> > > a spinlock which just spins away the cycles in a tight loop. Most
> > > unfriendly on
> > other
> > > tasks in the system. Of course, if this code runs at a higher than
> > PASSIVE
> > > IRQL, then you MUST use the spinlock, as asking the OS to
> > wait for you
> > > isn’t allowed at higher IRQL.
> > >
> > > –
> > > Mats
> > >
> > >
> > > xxxxx@lists.osr.com wrote on 09/13/2004 03:09:57 PM:
> > >
> > > > if another processor could be modifying this list at the
> > same time
> > > > then you have to have some protection. You’re the only
> > one who can
> > > > tell us whether “Create List Links” can be modified by another
> > > > thread at the same time as this code is running. And
> > once you tell
> > > > us that you’ll have your answer.
> > > >
> > > > -p
> > > >
> > > > From: xxxxx@lists.osr.com [mailto:
> > > > xxxxx@lists.osr.com] On Behalf Of Anurag Sarin
> > > > Sent: Monday, September 13, 2004 6:27 AM
> > > > To: Windows System Software Devs Interest List
> > > > Subject: [ntdev] Spinlocks
> > >
> > > > If I have a code like this in my CREATE Dispatch routine.
> > And if my
> > > > Link List can be of 100 elements or more.
> > > > ---------------------------------------------------
> > > > Acquire Spin Lock
> > > > If Create Link List has elements
> > > > {
> > > > If this filename found in Create Link List
> > > > {
> > > > Release Spin lock
> > > > Return SpyPassthrough
> > > > }
> > > > }
> > > > Release Spin lock
> > > > ----------------------------------------------------
> > > > Is there a need to do this operation using spin locks ? Will this
> > > > lead to unexpected behavior or performance loss for my driver.
> > > > Any comments ??
> > > > Regards,
> > > > Anurag
> > > > —
> > > > Questions? First check the Kernel Driver FAQ at http://www.
> > > > osronline.com/article.cfm?id=256
> > > >
> > > > You are currently subscribed to ntdev as: unknown lmsubst tag
> > argument:
> > > ‘’
> > > > To unsubscribe send a blank email to
> > xxxxx@lists.osr.com
> > > > —
> > > > Questions? First check the Kernel Driver FAQ at http://www.
> > > > osronline.com/article.cfm?id=256
> > > >
> > > > You are currently subscribed to ntdev as: unknown lmsubst tag
> > argument:
> > > ‘’
> > > > To unsubscribe send a blank email to
> > xxxxx@lists.osr.com
> > > > ForwardSourceID:NT0000353E
> > >
> > >
> > >
> > > —
> > > Questions? First check the Kernel Driver FAQ at
> > > http://www.osronline.com/article.cfm?id=256
> > >
> > > You are currently subscribed to ntdev as: xxxxx@tab.at To
> > unsubscribe
> > > send a blank email to xxxxx@lists.osr.com
> > >
> > > Please visit us: www.tab.at www.championsnet.net
> > > www.silverball.com
> > >
> > >
> > >
> > > —
> > > Questions? First check the Kernel Driver FAQ at http://www.
> > > osronline.com/article.cfm?id=256
> > >
> > > You are currently subscribed to ntdev as:
> > xxxxx@3dlabs.com To
> > > unsubscribe send a blank email to xxxxx@lists.osr.com
> >
> > > ForwardSourceID:NT00003572
> >
> >
> >
> > —
> > Questions? First check the Kernel Driver FAQ at
> > http://www.osronline.com/article.cfm?id=256
> >
> > You are currently subscribed to ntdev as: xxxxx@tab.at To
> > unsubscribe send a blank email to xxxxx@lists.osr.com
> >
> > Please visit us: www.tab.at www.championsnet.net
> > www.silverball.com
> >
> >
> >
> > —
> > Questions? First check the Kernel Driver FAQ at
> > http://www.osronline.com/article.cfm?id=256
> >
> > You are currently subscribed to ntdev as: xxxxx@garlic.com
> > To unsubscribe send a blank email to xxxxx@lists.osr.com
> >
> >
> >
> >
> >
> > —
> > Questions? First check the Kernel Driver FAQ at
> > http://www.osronline.com/article.cfm?id=256
> >
> > You are currently subscribed to ntdev as: xxxxx@garlic.com
> > To unsubscribe send a blank email to xxxxx@lists.osr.com
> >
> >
> >
> >
> >
> > —
> > Questions? First check the Kernel Driver FAQ at
> > http://www.osronline.com/article.cfm?id=256
> >
> > You are currently subscribed to ntdev as:
> > xxxxx@windows.microsoft.com To unsubscribe send a blank
> > email to xxxxx@lists.osr.com
> >
>
>
> —
> Questions? First check the Kernel Driver FAQ at
> http://www.osronline.com/article.cfm?id=256
>
> You are currently subscribed to ntdev as: unknown lmsubst tag argument:
> ‘’
> To unsubscribe send a blank email to xxxxx@lists.osr.com
>
>
>
> —
> Questions? First check the Kernel Driver FAQ at http://www.
> osronline.com/article.cfm?id=256
>
> You are currently subscribed to ntdev as: unknown lmsubst tag argument:
‘’
> To unsubscribe send a blank email to xxxxx@lists.osr.com
> ForwardSourceID:NT000036C2
—
Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256
You are currently subscribed to ntdev as: xxxxx@tab.at
To unsubscribe send a blank email to xxxxx@lists.osr.com
Please visit us: www.tab.at www.championsnet.net
www.silverball.com
I am making a File System Driver on Windows 2000
I have the following code (explained as Pseudo code below) added in the
CREATE Routine of FileSpy Example in IFS Kit .
CREAT Dispatch Routine
Control for filter :
irpStack = IoGetCurrentIrpStackLocation( Irp );
Get File name from irpStack and File Object and Store in Unicode String
If File is one from My Buffer
{
Return SpyPassthrough
}
If Create Link List is empty
{
Add the file name in Link List using Spin Locks
If file is one of my files, log files using ZWCreate Function
Return SpyPassthrough
}
Acquire Spin Lock
If Create Link List has elements
{
If this filename found in Create Link List
{
KeReleaseSpinLock(&CreateListSpinLock,OldIrql);
Return SpyPassthrough
}
}
KeReleaseSpinLock(&CreateListSpinLock,OldIrql);
Insert Filename in Link List Using Spin Locks
If file is one of my files
{
log files using ZWCreate Function
Return SpyPassthrough
}
Return SpyPassthrough
SpyPassthrough routine is same as the filespy example.
Do you think Spin Lock is spoilling the show some where ??
Well be glad to here some deep comments now.
Regards,
Anurag
-----Original Message-----
From: xxxxx@tab.at [mailto:xxxxx@tab.at]
Sent: Tuesday, September 14, 2004 6:49 PM
To: Windows System Software Devs Interest List
Subject: Re: [ntdev] Spinlocks
Anurag, do you have any place where you have to access that list from
DISPATCH_LEVEL or higher? If not you could still think of using a
FAST_MUTEX or another synchronization-primitive. The code would be 95%
the
same (no structural changes), the speed should be about the same for
FAST_MUTEX (as I am told) and it would cooperate more smoothly on MP as
well as UP. You can use a spinlock, it's just very likely not
"optimal"
for 100+ string-compares.
Regards,
Paul
Mats PETERSSON
Gesendet von: xxxxx@lists.osr.com
14.09.2004 14:16
Bitte antworten an "Windows System Software Devs Interest List"
An: "Windows System Software Devs Interest List"
Kopie:
Thema: RE: [ntdev] Spinlocks
How do you know that your driver will only be run on a single-processor
system? what about HyperThreading single processor, is that not allowed
either?
Sorry, but unless your driver is written to only work on a specific
hardware platform that doesn't have options to change the processor,
then it's very likely that sometime soon, you'll be forced to accept
that the driver will need to restist multiprocessor systems.
--
Mats
xxxxx@lists.osr.com wrote on 09/14/2004 01:06:49 PM:
> Well I am glad to provide a spark for a power full discussion.
>
> My driver is for single processer systems. And I have a code to add
> the elements in the list if not found in the loopp mentioned below. I
> finally under stand that I would keep the spin locks and need
> syncronization here as my next code after this is to add more elements
> in the same list. Change my data structure to another structure and
> another searching methord hike hash table will lead to rework for
> which I have no time at the moment.
>
>
> Thanks & Regards,
> Anurag
>
> -----Original Message-----
> From: Peter Wieland [mailto:xxxxx@windows.microsoft.com]
> Sent: Monday, September 13, 2004 10:33 PM
> To: Windows System Software Devs Interest List
> Subject: RE: [ntdev] Spinlocks
>
>
> It would only "surely help here" if this is the sort of code path
> where cache effects are likely to cause a noticible drop off in
> performance. Given the length of the typical file-system create path
> (and this seems to be a filter on top of those) I doubt that an OS
> provided cache is going to solve anything here.
>
> While I love the discussions we get when our threads spin off into the
> weeds like this, it's not always productive for the person who just
> wants to know "do I need to have some synchronization here?"
>
> -p
>
> > -----Original Message-----
> > From: xxxxx@lists.osr.com
> > [mailto:xxxxx@lists.osr.com] On Behalf Of Prokash Sinha
> > Sent: Monday, September 13, 2004 9:30 AM
> > To: Windows System Software Devs Interest List
> > Subject: RE: [ntdev] Spinlocks
> >
> > Also link list or any truely dynamically allocated structure is a
> > pain in the horrendous thinking from the cache-point-of-view, so any
> > pre-fabricated ddk/os provided api for TLB emulation would surely
> > help here !!!
> >
> > -pro
> >
> > -----Original Message-----
> > From: xxxxx@lists.osr.com
> > [mailto:xxxxx@lists.osr.com]On Behalf Of Prokash Sinha
> > Sent: Monday, September 13, 2004 9:08 AM
> > To: Windows System Software Devs Interest List
> > Subject: RE: [ntdev] Spinlocks
> >
> >
> > Just dropping my A* wide open :-). Kick as you please 
> >
> > May be one or more thing to remember is not such the size of the
> > list :). How frequently
> > it would execute, it is possible that the list might not go
> > over 300, and each element ie. sizeof (struct node) might be
> > 32 or 64 bytes, then ddk/os provided TLB would be a choice .
> > Sometime hash-collison, and the cost of hash-function might
> > become a overhead too !!. If it is on a really busy execution
> > path, hashing cost should be looked carefully too
> >
> > -pro
> >
> > -----Original Message-----
> > From: xxxxx@lists.osr.com
> > [mailto:xxxxx@lists.osr.com]On Behalf Of xxxxx@tab.at
> > Sent: Monday, September 13, 2004 8:41 AM
> > To: Windows System Software Devs Interest List
> > Subject: Re: [ntdev] Spinlocks
> >
> >
> > > In this instance, being slow means less typing 
> >
> > Nah, in this instance I just typed a lot of food for my backspace
> > key g Fast "find" structures would be a really nice thing to have
> > from the DDK. If they were implemented in the DDK using one fixed
> > block-size (for e.g.
> > b-trees) from one common lookaside-list (private lal
> > optional?) and if the implementation was fast and rock-solid
> > they'd surely be a nice thing for some driver-developers.
> > Anything like an FS or even a firewall could surely make use of
that.
> >
> > Anyway, for 100 entries max. I'd probably stick with a list, for
> > 100+ entries avg. I'd prefer something else. With strings as keys
> > (did someone mention filenames?) I'd probably use some form of hash
> > anyway
> > (adler32/crc32) - even if it's only a list. The comparsion of one
> > DWORD vs. a whole string should also give some noticable speedup.
> >
> > Regards,
> >
> > Paul Groke
> >
> >
> >
> >
> >
> > Mats PETERSSON Gesendet von:
> > xxxxx@lists.osr.com 13.09.2004 17:19
> > Bitte antworten an "Windows System Software Devs Interest List"
> >
> > An: "Windows System Software Devs Interest List"
> >
> > Kopie:
> > Thema: Re: [ntdev] Spinlocks
> >
> >
> >
> >
> >
> >
> >
> > In this instance, being slow means less typing
> >
> > Indeed a good suggestion, using a faster way to find the relevant
> > data doesn't remove the problem, but it certainly helps reduce the
> > locked time. Good suggestion, I should've thought of it...
> >
> > --
> > Mats
> >
> > xxxxx@lists.osr.com wrote on 09/13/2004 04:13:59 PM:
> >
> > > Ah, I'm always too slow One thing still left to say - you
> > > could
> > think
> >
> > > about alternative data-structures if your list can get very
> > big. Like
> > > hash-maps, b-trees or even a red-black-tree. That way you
> > don't avoid
> > the
> >
> > > lock but you can reduce the time it takes to find one entry. The
> > downside
> >
> > > is that the structures are more complicated and you have to
> > allocate
> > > additional storage for them (at least for hash-map and b-tree).
> > >
> > > Regards,
> > >
> > > Paul Groke
> > >
> > >
> > >
> > >
> > >
> > > Mats PETERSSON Gesendet von:
> > > xxxxx@lists.osr.com 13.09.2004 16:40
> > > Bitte antworten an "Windows System Software Devs Interest List"
> > >
> > > An: "Windows System Software Devs Interest List"
> > >
> > > Kopie:
> > > Thema: RE: [ntdev] Spinlocks
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > > As Peter said...
> > >
> > > However, if you find that other threads can modify the
> > list, there may
> > be
> > > ways to avoid the spin-lock, if you can live with the
> > > side-effects: 1. Don't ever REMOVE entries from the list, just
> > > mark them invalid. This means that you don't have to worry about
> > > entries "going away" whilst you're working on them (doing p =
> > > p->next isn't a
> > good thing if
> > > p isn't valid because it's been freed!).
> > > 2. If you want to ADD things, make sure that it's done in a
> > safe manner.
> > > This can be done in many different ways, but it's fairly
> > easy to use
> > > the ExchangeInterLocked to write to the "next" pointer, which
> > > makes the operation atomic. Of course, if the list if double
> > linked, it may
> > > be a
> > bit
> > > harder to achieve an atomic write.
> > >
> > > But one thing that's always going to be a problem if you
> > have multiple
> > > threads access a list (or any other data structure) is what
> > > happens when an entry isn't consistant: Consider a delete of an
> > element, just
> > > after the element was found and passed on to some other place.. so
> > > this 'other place' is now using the element that is being deleted.
> > > Of course,
> > spinlocks
> > > on the list don't help here, and you can't always spinlock
> > the entire
> > > use of
> > the
> > > data that came out of the list (especially if you pass it to a
> > > different piece of code than yours and for an undefined time).
> > > This has to be
> > worked
> > > around by for instance having reference counts for the data in the
> > > list, so that you can't delete the count.
> > >
> > > Another thing to consider: If this code is ALWAYS running
> > at passive
> > > level, you can use for instance (fast)mutex's to protect
> > the code from
> > > being re-entered. This will not help your code in itself,
> > but it will
> > > give the time waiting for the mutex to someone else, rather
> > than using
> > > a spinlock which just spins away the cycles in a tight loop. Most
> > > unfriendly on
> > other
> > > tasks in the system. Of course, if this code runs at a higher than
> > PASSIVE
> > > IRQL, then you MUST use the spinlock, as asking the OS to
> > wait for you
> > > isn't allowed at higher IRQL.
> > >
> > > --
> > > Mats
> > >
> > >
> > > xxxxx@lists.osr.com wrote on 09/13/2004 03:09:57 PM:
> > >
> > > > if another processor could be modifying this list at the
> > same time
> > > > then you have to have some protection. You're the only
> > one who can
> > > > tell us whether "Create List Links" can be modified by another
> > > > thread at the same time as this code is running. And
> > once you tell
> > > > us that you'll have your answer.
> > > >
> > > > -p
> > > >
> > > > From: xxxxx@lists.osr.com [mailto:
> > > > xxxxx@lists.osr.com] On Behalf Of Anurag Sarin
> > > > Sent: Monday, September 13, 2004 6:27 AM
> > > > To: Windows System Software Devs Interest List
> > > > Subject: [ntdev] Spinlocks
> > >
> > > > If I have a code like this in my CREATE Dispatch routine.
> > And if my
> > > > Link List can be of 100 elements or more.
> > > > ---------------------------------------------------
> > > > Acquire Spin Lock
> > > > If Create Link List has elements
> > > > {
> > > > If this filename found in Create Link List
> > > > {
> > > > Release Spin lock
> > > > Return SpyPassthrough
> > > > }
> > > > }
> > > > Release Spin lock
> > > > ----------------------------------------------------
> > > > Is there a need to do this operation using spin locks ? Will
> > > > this lead to unexpected behavior or performance loss for my
> > > > driver. Any comments ?? Regards,
> > > > Anurag
> > > > ---
> > > > Questions? First check the Kernel Driver FAQ at http://www.
> > > > osronline.com/article.cfm?id=256
> > > >
> > > > You are currently subscribed to ntdev as: unknown lmsubst tag
> > argument:
> > > ''
> > > > To unsubscribe send a blank email to
> > xxxxx@lists.osr.com
> > > > ---
> > > > Questions? First check the Kernel Driver FAQ at http://www.
> > > > osronline.com/article.cfm?id=256
> > > >
> > > > You are currently subscribed to ntdev as: unknown lmsubst tag
> > argument:
> > > ''
> > > > To unsubscribe send a blank email to
> > xxxxx@lists.osr.com
> > > > ForwardSourceID:NT0000353E
> > >
> > >
> > >
> > > ---
> > > Questions? First check the Kernel Driver FAQ at
> > > http://www.osronline.com/article.cfm?id=256
> > >
> > > You are currently subscribed to ntdev as: xxxxx@tab.at To
> > unsubscribe
> > > send a blank email to xxxxx@lists.osr.com
> > >
> > > Please visit us: www.tab.at www.championsnet.net
> > > www.silverball.com
> > >
> > >
> > >
> > > ---
> > > Questions? First check the Kernel Driver FAQ at http://www.
> > > osronline.com/article.cfm?id=256
> > >
> > > You are currently subscribed to ntdev as:
> > xxxxx@3dlabs.com To
> > > unsubscribe send a blank email to xxxxx@lists.osr.com
> >
> > > ForwardSourceID:NT00003572
> >
> >
> >
> > ---
> > Questions? First check the Kernel Driver FAQ at
> > http://www.osronline.com/article.cfm?id=256
> >
> > You are currently subscribed to ntdev as: xxxxx@tab.at To
> > unsubscribe send a blank email to xxxxx@lists.osr.com
> >
> > Please visit us: www.tab.at www.championsnet.net
> > www.silverball.com
> >
> >
> >
> > ---
> > Questions? First check the Kernel Driver FAQ at
> > http://www.osronline.com/article.cfm?id=256
> >
> > You are currently subscribed to ntdev as: xxxxx@garlic.com To
> > unsubscribe send a blank email to xxxxx@lists.osr.com
> >
> >
> >
> >
> >
> > ---
> > Questions? First check the Kernel Driver FAQ at
> > http://www.osronline.com/article.cfm?id=256
> >
> > You are currently subscribed to ntdev as: xxxxx@garlic.com To
> > unsubscribe send a blank email to xxxxx@lists.osr.com
> >
> >
> >
> >
> >
> > ---
> > Questions? First check the Kernel Driver FAQ at
> > http://www.osronline.com/article.cfm?id=256
> >
> > You are currently subscribed to ntdev as:
> > xxxxx@windows.microsoft.com To unsubscribe send a blank email to
> > xxxxx@lists.osr.com
> >
>
>
> ---
> Questions? First check the Kernel Driver FAQ at
> http://www.osronline.com/article.cfm?id=256
>
> You are currently subscribed to ntdev as: unknown lmsubst tag
> argument: '' To unsubscribe send a blank email to
> xxxxx@lists.osr.com
>
>
>
> ---
> Questions? First check the Kernel Driver FAQ at http://www.
> osronline.com/article.cfm?id=256
>
> You are currently subscribed to ntdev as: unknown lmsubst tag
> argument:
''
> To unsubscribe send a blank email to xxxxx@lists.osr.com
> ForwardSourceID:NT000036C2
---
Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256
You are currently subscribed to ntdev as: xxxxx@tab.at
To unsubscribe send a blank email to xxxxx@lists.osr.com
Please visit us: www.tab.at www.championsnet.net
www.silverball.com
---
Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256
You are currently subscribed to ntdev as: xxxxx@divassoftware.com To
unsubscribe send a blank email to xxxxx@lists.osr.com
I doubt the spinlock has anything to do with your multiple IRP
completion problem.
-p
-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com] On Behalf Of Anurag Sarin
Sent: Tuesday, September 14, 2004 7:01 AM
To: Windows System Software Devs Interest List
Subject: RE: [ntdev] SpinlocksPaul
well I don’t think I will excess the list from DISPATCH_LEVEL
or higher.
I would like to take your advise . But honestly my main
concern is a BSOD MULTIPLE_IRP_COMPLETE_REQUESTS which I
thought may be a reason of spin locks in that sipnet.
I may be very wrong but I see this BSOD only on high
asynchronous operations and see when I pass the Irp down
after comparing in the 100 odd long list.
Else is list is shot it gives no bug check.
Below is my more detailed explanation.I am making a File System Driver on Windows 2000 I have the
following code (explained as Pseudo code below) added in the
CREATE Routine of FileSpy Example in IFS Kit .CREAT Dispatch Routine
Control for filter :
irpStack = IoGetCurrentIrpStackLocation( Irp ); Get File name
from irpStack and File Object and Store in Unicode String If
File is one from My Buffer {
Return SpyPassthrough
}
If Create Link List is empty
{
Add the file name in Link List using Spin Locks
If file is one of my files, log files using ZWCreate Function
Return SpyPassthrough
}
Acquire Spin Lock
If Create Link List has elements
{
If this filename found in Create Link List
{
KeReleaseSpinLock(&CreateListSpinLock,OldIrql);
Return SpyPassthrough
}
}
KeReleaseSpinLock(&CreateListSpinLock,OldIrql);
Insert Filename in Link List Using Spin Locks If file is one
of my files {
log files using ZWCreate Function
Return SpyPassthrough
}
Return SpyPassthrough
SpyPassthrough routine is same as the filespy example.
Do you think Spin Lock is spoilling the show some where ??
Well be glad to here some deep comments now.Regards,
Anurag-----Original Message-----
From: xxxxx@tab.at [mailto:xxxxx@tab.at]
Sent: Tuesday, September 14, 2004 6:49 PM
To: Windows System Software Devs Interest List
Subject: Re: [ntdev] SpinlocksAnurag, do you have any place where you have to access that list from
DISPATCH_LEVEL or higher? If not you could still think of using a
FAST_MUTEX or another synchronization-primitive. The code would be 95%
the
same (no structural changes), the speed should be about the same for
FAST_MUTEX (as I am told) and it would cooperate more
smoothly on MP as
well as UP. You can use a spinlock, it’s just very likely not
“optimal”
for 100+ string-compares.Regards,
PaulMats PETERSSON
> Gesendet von: xxxxx@lists.osr.com
> 14.09.2004 14:16
> Bitte antworten an “Windows System Software Devs Interest List”
>
> An: “Windows System Software Devs Interest List”
>
> Kopie:
> Thema: RE: [ntdev] Spinlocks
>
>
>
>
>
>
>
> How do you know that your driver will only be run on a
> single-processor
> system? what about HyperThreading single processor, is that
> not allowed
> either?
>
> Sorry, but unless your driver is written to only work on a specific
> hardware platform that doesn’t have options to change the processor,
> then it’s very likely that sometime soon, you’ll be forced to accept
> that the driver will need to restist multiprocessor systems.
>
> –
> Mats
>
> xxxxx@lists.osr.com wrote on 09/14/2004 01:06:49 PM:
>
> > Well I am glad to provide a spark for a power full discussion.
> >
> > My driver is for single processer systems. And I have a code to add
> > the elements in the list if not found in the loopp
> mentioned below. I
> > finally under stand that I would keep the spin locks and need
> > syncronization here as my next code after this is to add
> more elements
>
> > in the same list. Change my data structure to another structure and
> > another searching methord hike hash table will lead to rework for
> > which I have no time at the moment.
> >
> >
> > Thanks & Regards,
> > Anurag
> >
> > -----Original Message-----
> > From: Peter Wieland [mailto:xxxxx@windows.microsoft.com]
> > Sent: Monday, September 13, 2004 10:33 PM
> > To: Windows System Software Devs Interest List
> > Subject: RE: [ntdev] Spinlocks
> >
> >
> > It would only “surely help here” if this is the sort of code path
> > where cache effects are likely to cause a noticible drop off in
> > performance. Given the length of the typical file-system
> create path
> > (and this seems to be a filter on top of those) I doubt that an OS
> > provided cache is going to solve anything here.
> >
> > While I love the discussions we get when our threads spin
> off into the
>
> > weeds like this, it’s not always productive for the person who just
> > wants to know “do I need to have some synchronization here?”
> >
> > -p
> >
> > > -----Original Message-----
> > > From: xxxxx@lists.osr.com
> > > [mailto:xxxxx@lists.osr.com] On Behalf Of
> Prokash Sinha
> > > Sent: Monday, September 13, 2004 9:30 AM
> > > To: Windows System Software Devs Interest List
> > > Subject: RE: [ntdev] Spinlocks
> > >
> > > Also link list or any truely dynamically allocated structure is a
> > > pain in the horrendous thinking from the
> cache-point-of-view, so any
>
> > > pre-fabricated ddk/os provided api for TLB emulation would surely
> > > help here !!!
> > >
> > > -pro
> > >
> > > -----Original Message-----
> > > From: xxxxx@lists.osr.com
> > > [mailto:xxxxx@lists.osr.com]On Behalf Of
> Prokash Sinha
> > > Sent: Monday, September 13, 2004 9:08 AM
> > > To: Windows System Software Devs Interest List
> > > Subject: RE: [ntdev] Spinlocks
> > >
> > >
> > > Just dropping my A* wide open :-). Kick as you please
> > >
> > > May be one or more thing to remember is not such the size of the
> > > list :). How frequently
> > > it would execute, it is possible that the list might not go
> > > over 300, and each element ie. sizeof (struct node) might be
> > > 32 or 64 bytes, then ddk/os provided TLB would be a choice .
> > > Sometime hash-collison, and the cost of hash-function might
> > > become a overhead too !!. If it is on a really busy execution
> > > path, hashing cost should be looked carefully too
> > >
> > > -pro
> > >
> > > -----Original Message-----
> > > From: xxxxx@lists.osr.com
> > > [mailto:xxxxx@lists.osr.com]On Behalf Of
> xxxxx@tab.at
> > > Sent: Monday, September 13, 2004 8:41 AM
> > > To: Windows System Software Devs Interest List
> > > Subject: Re: [ntdev] Spinlocks
> > >
> > >
> > > > In this instance, being slow means less typing
> > >
> > > Nah, in this instance I just typed a lot of food for my backspace
> > > key g Fast “find” structures would be a really nice
> thing to have
> > > from the DDK. If they were implemented in the DDK using one fixed
> > > block-size (for e.g.
> > > b-trees) from one common lookaside-list (private lal
> > > optional?) and if the implementation was fast and rock-solid
> > > they’d surely be a nice thing for some driver-developers.
> > > Anything like an FS or even a firewall could surely make use of
> that.
> > >
> > > Anyway, for 100 entries max. I’d probably stick with a list, for
> > > 100+ entries avg. I’d prefer something else. With strings as keys
> > > (did someone mention filenames?) I’d probably use some
> form of hash
> > > anyway
> > > (adler32/crc32) - even if it’s only a list. The comparsion of one
> > > DWORD vs. a whole string should also give some noticable speedup.
> > >
> > > Regards,
> > >
> > > Paul Groke
> > >
> > >
> > >
> > >
> > >
> > > Mats PETERSSON Gesendet von:
> > > xxxxx@lists.osr.com 13.09.2004 17:19
> > > Bitte antworten an “Windows System Software Devs Interest List”
> > >
> > > An: “Windows System Software Devs Interest List”
> > >
> > > Kopie:
> > > Thema: Re: [ntdev] Spinlocks
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > > In this instance, being slow means less typing
> > >
> > > Indeed a good suggestion, using a faster way to find the relevant
> > > data doesn’t remove the problem, but it certainly helps
> reduce the
> > > locked time. Good suggestion, I should’ve thought of it…
> > >
> > > –
> > > Mats
> > >
> > > xxxxx@lists.osr.com wrote on 09/13/2004 04:13:59 PM:
> > >
> > > > Ah, I’m always too slow
> > > > could
> > > think
> > >
> > > > about alternative data-structures if your list can get very
> > > big. Like
> > > > hash-maps, b-trees or even a red-black-tree. That way you
> > > don’t avoid
> > > the
> > >
> > > > lock but you can reduce the time it takes to find one entry. The
> > > downside
> > >
> > > > is that the structures are more complicated and you have to
> > > allocate
> > > > additional storage for them (at least for hash-map and b-tree).
> > > >
> > > > Regards,
> > > >
> > > > Paul Groke
> > > >
> > > >
> > > >
> > > >
> > > >
> > > > Mats PETERSSON Gesendet von:
> > > > xxxxx@lists.osr.com 13.09.2004 16:40
> > > > Bitte antworten an “Windows System Software Devs Interest List”
> > > >
> > > > An: “Windows System Software Devs Interest List”
> > > >
> > > > Kopie:
> > > > Thema: RE: [ntdev] Spinlocks
> > > >
> > > >
> > > >
> > > >
> > > >
> > > >
> > > >
> > > > As Peter said…
> > > >
> > > > However, if you find that other threads can modify the
> > > list, there may
> > > be
> > > > ways to avoid the spin-lock, if you can live with the
> > > > side-effects: 1. Don’t ever REMOVE entries from the list, just
> > > > mark them invalid. This means that you don’t have to
> worry about
> > > > entries “going away” whilst you’re working on them (doing p =
> > > > p->next isn’t a
> > > good thing if
> > > > p isn’t valid because it’s been freed!).
> > > > 2. If you want to ADD things, make sure that it’s done in a
> > > safe manner.
> > > > This can be done in many different ways, but it’s fairly
> > > easy to use
> > > > the ExchangeInterLocked to write to the “next” pointer, which
> > > > makes the operation atomic. Of course, if the list if double
> > > linked, it may
> > > > be a
> > > bit
> > > > harder to achieve an atomic write.
> > > >
> > > > But one thing that’s always going to be a problem if you
> > > have multiple
> > > > threads access a list (or any other data structure) is what
> > > > happens when an entry isn’t consistant: Consider a delete of an
> > > element, just
> > > > after the element was found and passed on to some other
> place… so
>
> > > > this ‘other place’ is now using the element that is
> being deleted.
>
> > > > Of course,
> > > spinlocks
> > > > on the list don’t help here, and you can’t always spinlock
> > > the entire
> > > > use of
> > > the
> > > > data that came out of the list (especially if you pass it to a
> > > > different piece of code than yours and for an undefined time).
> > > > This has to be
> > > worked
> > > > around by for instance having reference counts for the
> data in the
>
> > > > list, so that you can’t delete the count.
> > > >
> > > > Another thing to consider: If this code is ALWAYS running
> > > at passive
> > > > level, you can use for instance (fast)mutex’s to protect
> > > the code from
> > > > being re-entered. This will not help your code in itself,
> > > but it will
> > > > give the time waiting for the mutex to someone else, rather
> > > than using
> > > > a spinlock which just spins away the cycles in a tight
> loop. Most
> > > > unfriendly on
> > > other
> > > > tasks in the system. Of course, if this code runs at a
> higher than
> > > PASSIVE
> > > > IRQL, then you MUST use the spinlock, as asking the OS to
> > > wait for you
> > > > isn’t allowed at higher IRQL.
> > > >
> > > > –
> > > > Mats
> > > >
> > > >
> > > > xxxxx@lists.osr.com wrote on 09/13/2004
> 03:09:57 PM:
> > > >
> > > > > if another processor could be modifying this list at the
> > > same time
> > > > > then you have to have some protection. You’re the only
> > > one who can
> > > > > tell us whether “Create List Links” can be modified
> by another
> > > > > thread at the same time as this code is running. And
> > > once you tell
> > > > > us that you’ll have your answer.
> > > > >
> > > > > -p
> > > > >
> > > > > From: xxxxx@lists.osr.com [mailto:
> > > > > xxxxx@lists.osr.com] On Behalf Of Anurag Sarin
> > > > > Sent: Monday, September 13, 2004 6:27 AM
> > > > > To: Windows System Software Devs Interest List
> > > > > Subject: [ntdev] Spinlocks
> > > >
> > > > > If I have a code like this in my CREATE Dispatch routine.
> > > And if my
> > > > > Link List can be of 100 elements or more.
> > > > > ---------------------------------------------------
> > > > > Acquire Spin Lock
> > > > > If Create Link List has elements
> > > > > {
> > > > > If this filename found in Create Link List
> > > > > {
> > > > > Release Spin lock
> > > > > Return SpyPassthrough
> > > > > }
> > > > > }
> > > > > Release Spin lock
> > > > > ----------------------------------------------------
> > > > > Is there a need to do this operation using spin locks ? Will
> > > > > this lead to unexpected behavior or performance loss for my
> > > > > driver. Any comments ?? Regards,
> > > > > Anurag
> > > > > —
> > > > > Questions? First check the Kernel Driver FAQ at http://www.
> > > > > osronline.com/article.cfm?id=256
> > > > >
> > > > > You are currently subscribed to ntdev as: unknown lmsubst tag
> > > argument:
> > > > ‘’
> > > > > To unsubscribe send a blank email to
> > > xxxxx@lists.osr.com
> > > > > —
> > > > > Questions? First check the Kernel Driver FAQ at http://www.
> > > > > osronline.com/article.cfm?id=256
> > > > >
> > > > > You are currently subscribed to ntdev as: unknown lmsubst tag
> > > argument:
> > > > ‘’
> > > > > To unsubscribe send a blank email to
> > > xxxxx@lists.osr.com
> > > > > ForwardSourceID:NT0000353E
> > > >
> > > >
> > > >
> > > > —
> > > > Questions? First check the Kernel Driver FAQ at
> > > > http://www.osronline.com/article.cfm?id=256
> > > >
> > > > You are currently subscribed to ntdev as: xxxxx@tab.at To
> > > unsubscribe
> > > > send a blank email to xxxxx@lists.osr.com
> > > >
> > > > Please visit us: www.tab.at www.championsnet.net
> > > > www.silverball.com
> > > >
> > > >
> > > >
> > > > —
> > > > Questions? First check the Kernel Driver FAQ at http://www.
> > > > osronline.com/article.cfm?id=256
> > > >
> > > > You are currently subscribed to ntdev as:
> > > xxxxx@3dlabs.com To
> > > > unsubscribe send a blank email to
> xxxxx@lists.osr.com
> > >
> > > > ForwardSourceID:NT00003572
> > >
> > >
> > >
> > > —
> > > Questions? First check the Kernel Driver FAQ at
> > > http://www.osronline.com/article.cfm?id=256
> > >
> > > You are currently subscribed to ntdev as: xxxxx@tab.at To
> > > unsubscribe send a blank email to xxxxx@lists.osr.com
> > >
> > > Please visit us: www.tab.at www.championsnet.net
> > > www.silverball.com
> > >
> > >
> > >
> > > —
> > > Questions? First check the Kernel Driver FAQ at
> > > http://www.osronline.com/article.cfm?id=256
> > >
> > > You are currently subscribed to ntdev as: xxxxx@garlic.com To
> > > unsubscribe send a blank email to xxxxx@lists.osr.com
> > >
> > >
> > >
> > >
> > >
> > > —
> > > Questions? First check the Kernel Driver FAQ at
> > > http://www.osronline.com/article.cfm?id=256
> > >
> > > You are currently subscribed to ntdev as: xxxxx@garlic.com To
> > > unsubscribe send a blank email to xxxxx@lists.osr.com
> > >
> > >
> > >
> > >
> > >
> > > —
> > > Questions? First check the Kernel Driver FAQ at
> > > http://www.osronline.com/article.cfm?id=256
> > >
> > > You are currently subscribed to ntdev as:
> > > xxxxx@windows.microsoft.com To unsubscribe send a
> blank email to
> > > xxxxx@lists.osr.com
> > >
> >
> >
> > —
> > Questions? First check the Kernel Driver FAQ at
> > http://www.osronline.com/article.cfm?id=256
> >
> > You are currently subscribed to ntdev as: unknown lmsubst tag
> > argument: ‘’ To unsubscribe send a blank email to
> > xxxxx@lists.osr.com
> >
> >
> >
> > —
> > Questions? First check the Kernel Driver FAQ at http://www.
> > osronline.com/article.cfm?id=256
> >
> > You are currently subscribed to ntdev as: unknown lmsubst tag
> > argument:
> ‘’
> > To unsubscribe send a blank email to xxxxx@lists.osr.com
>
> > ForwardSourceID:NT000036C2
>
>
>
> —
> Questions? First check the Kernel Driver FAQ at
> http://www.osronline.com/article.cfm?id=256
>
> You are currently subscribed to ntdev as: xxxxx@tab.at
> To unsubscribe send a blank email to xxxxx@lists.osr.com
>
> Please visit us: www.tab.at www.championsnet.net
> www.silverball.com
>
>
>
> —
> Questions? First check the Kernel Driver FAQ at
> http://www.osronline.com/article.cfm?id=256
>
> You are currently subscribed to ntdev as: xxxxx@divassoftware.com To
> unsubscribe send a blank email to xxxxx@lists.osr.com
>
>
>
> —
> Questions? First check the Kernel Driver FAQ at
> http://www.osronline.com/article.cfm?id=256
>
> You are currently subscribed to ntdev as: unknown lmsubst tag
> argument: ‘’
> To unsubscribe send a blank email to xxxxx@lists.osr.com
>
I doubt that too. One likely flaw in your code - you can’t do something
like:
if list is empty
lock list
insert element in list
unlock list
else
lock list
do something else with list
unlock list
endif
The “if list is empty” part already is access to the list, so you have to
rewrite like:
lock list
if list is empty
insert element in list
unlock list
return whatever()
else
do something else with list
unlock list
return whatever_else()
endif
You have to make sure that before you do the 1st check (or any access) to
the list you lock that spinlock, and that you hold it until you’re done
with the last check/operation/access to the list. If you unlock/relock
along the way you can’t be sure that the lists contents was not modified
inbetween. If you have everything running fine using spinlocks and you’re
sure that IRQL will never be above APC_LEVEL you can rewrite it using a
FAST_MUTEX.
Regards,
Paul Groke
“Peter Wieland”
Gesendet von: xxxxx@lists.osr.com
14.09.2004 16:07
Bitte antworten an “Windows System Software Devs Interest List”
An: “Windows System Software Devs Interest List”
Kopie:
Thema: RE: [ntdev] Spinlocks
I doubt the spinlock has anything to do with your multiple IRP
completion problem.
-p
> -----Original Message-----
> From: xxxxx@lists.osr.com
> [mailto:xxxxx@lists.osr.com] On Behalf Of Anurag Sarin
> Sent: Tuesday, September 14, 2004 7:01 AM
> To: Windows System Software Devs Interest List
> Subject: RE: [ntdev] Spinlocks
>
> Paul
> well I don’t think I will excess the list from DISPATCH_LEVEL
> or higher.
> I would like to take your advise . But honestly my main
> concern is a BSOD MULTIPLE_IRP_COMPLETE_REQUESTS which I
> thought may be a reason of spin locks in that sipnet.
> I may be very wrong but I see this BSOD only on high
> asynchronous operations and see when I pass the Irp down
> after comparing in the 100 odd long list.
> Else is list is shot it gives no bug check.
> Below is my more detailed explanation.
> ---------------------------
> I am making a File System Driver on Windows 2000 I have the
> following code (explained as Pseudo code below) added in the
> CREATE Routine of FileSpy Example in IFS Kit .
>
> CREAT Dispatch Routine
> Control for filter :
> irpStack = IoGetCurrentIrpStackLocation( Irp ); Get File name
> from irpStack and File Object and Store in Unicode String If
> File is one from My Buffer {
> Return SpyPassthrough
> }
> If Create Link List is empty
> {
> Add the file name in Link List using Spin Locks
> If file is one of my files, log files using ZWCreate Function
> Return SpyPassthrough
> }
> Acquire Spin Lock
> If Create Link List has elements
> {
> If this filename found in Create Link List
> {
> KeReleaseSpinLock(&CreateListSpinLock,OldIrql);
> Return SpyPassthrough
> }
> }
> KeReleaseSpinLock(&CreateListSpinLock,OldIrql);
> Insert Filename in Link List Using Spin Locks If file is one
> of my files {
> log files using ZWCreate Function
> Return SpyPassthrough
> }
> Return SpyPassthrough
>
> ------------------
> SpyPassthrough routine is same as the filespy example.
>
> Do you think Spin Lock is spoilling the show some where ??
> Well be glad to here some deep comments now.
>
> Regards,
> Anurag
>
>
>
> -----Original Message-----
> From: xxxxx@tab.at [mailto:xxxxx@tab.at]
> Sent: Tuesday, September 14, 2004 6:49 PM
> To: Windows System Software Devs Interest List
> Subject: Re: [ntdev] Spinlocks
>
>
> Anurag, do you have any place where you have to access that list from
> DISPATCH_LEVEL or higher? If not you could still think of using a
> FAST_MUTEX or another synchronization-primitive. The code would be 95%
> the
> same (no structural changes), the speed should be about the same for
> FAST_MUTEX (as I am told) and it would cooperate more
> smoothly on MP as
> well as UP. You can use a spinlock, it’s just very likely not
> “optimal”
> for 100+ string-compares.
>
> Regards,
> Paul
>
>
>
>
>
> Mats PETERSSON
> Gesendet von: xxxxx@lists.osr.com
> 14.09.2004 14:16
> Bitte antworten an “Windows System Software Devs Interest List”
>
> An: “Windows System Software Devs Interest List”
>
> Kopie:
> Thema: RE: [ntdev] Spinlocks
>
>
>
>
>
>
>
> How do you know that your driver will only be run on a
> single-processor
> system? what about HyperThreading single processor, is that
> not allowed
> either?
>
> Sorry, but unless your driver is written to only work on a specific
> hardware platform that doesn’t have options to change the processor,
> then it’s very likely that sometime soon, you’ll be forced to accept
> that the driver will need to restist multiprocessor systems.
>
> –
> Mats
>
> xxxxx@lists.osr.com wrote on 09/14/2004 01:06:49 PM:
>
> > Well I am glad to provide a spark for a power full discussion.
> >
> > My driver is for single processer systems. And I have a code to add
> > the elements in the list if not found in the loopp
> mentioned below. I
> > finally under stand that I would keep the spin locks and need
> > syncronization here as my next code after this is to add
> more elements
>
> > in the same list. Change my data structure to another structure and
> > another searching methord hike hash table will lead to rework for
> > which I have no time at the moment.
> >
> >
> > Thanks & Regards,
> > Anurag
> >
> > -----Original Message-----
> > From: Peter Wieland [mailto:xxxxx@windows.microsoft.com]
> > Sent: Monday, September 13, 2004 10:33 PM
> > To: Windows System Software Devs Interest List
> > Subject: RE: [ntdev] Spinlocks
> >
> >
> > It would only “surely help here” if this is the sort of code path
> > where cache effects are likely to cause a noticible drop off in
> > performance. Given the length of the typical file-system
> create path
> > (and this seems to be a filter on top of those) I doubt that an OS
> > provided cache is going to solve anything here.
> >
> > While I love the discussions we get when our threads spin
> off into the
>
> > weeds like this, it’s not always productive for the person who just
> > wants to know “do I need to have some synchronization here?”
> >
> > -p
> >
> > > -----Original Message-----
> > > From: xxxxx@lists.osr.com
> > > [mailto:xxxxx@lists.osr.com] On Behalf Of
> Prokash Sinha
> > > Sent: Monday, September 13, 2004 9:30 AM
> > > To: Windows System Software Devs Interest List
> > > Subject: RE: [ntdev] Spinlocks
> > >
> > > Also link list or any truely dynamically allocated structure is a
> > > pain in the horrendous thinking from the
> cache-point-of-view, so any
>
> > > pre-fabricated ddk/os provided api for TLB emulation would surely
> > > help here !!!
> > >
> > > -pro
> > >
> > > -----Original Message-----
> > > From: xxxxx@lists.osr.com
> > > [mailto:xxxxx@lists.osr.com]On Behalf Of
> Prokash Sinha
> > > Sent: Monday, September 13, 2004 9:08 AM
> > > To: Windows System Software Devs Interest List
> > > Subject: RE: [ntdev] Spinlocks
> > >
> > >
> > > Just dropping my A* wide open :-). Kick as you please
> > >
> > > May be one or more thing to remember is not such the size of the
> > > list :). How frequently
> > > it would execute, it is possible that the list might not go
> > > over 300, and each element ie. sizeof (struct node) might be
> > > 32 or 64 bytes, then ddk/os provided TLB would be a choice .
> > > Sometime hash-collison, and the cost of hash-function might
> > > become a overhead too !!. If it is on a really busy execution
> > > path, hashing cost should be looked carefully too
> > >
> > > -pro
> > >
> > > -----Original Message-----
> > > From: xxxxx@lists.osr.com
> > > [mailto:xxxxx@lists.osr.com]On Behalf Of
> xxxxx@tab.at
> > > Sent: Monday, September 13, 2004 8:41 AM
> > > To: Windows System Software Devs Interest List
> > > Subject: Re: [ntdev] Spinlocks
> > >
> > >
> > > > In this instance, being slow means less typing
> > >
> > > Nah, in this instance I just typed a lot of food for my backspace
> > > key g Fast “find” structures would be a really nice
> thing to have
> > > from the DDK. If they were implemented in the DDK using one fixed
> > > block-size (for e.g.
> > > b-trees) from one common lookaside-list (private lal
> > > optional?) and if the implementation was fast and rock-solid
> > > they’d surely be a nice thing for some driver-developers.
> > > Anything like an FS or even a firewall could surely make use of
> that.
> > >
> > > Anyway, for 100 entries max. I’d probably stick with a list, for
> > > 100+ entries avg. I’d prefer something else. With strings as keys
> > > (did someone mention filenames?) I’d probably use some
> form of hash
> > > anyway
> > > (adler32/crc32) - even if it’s only a list. The comparsion of one
> > > DWORD vs. a whole string should also give some noticable speedup.
> > >
> > > Regards,
> > >
> > > Paul Groke
> > >
> > >
> > >
> > >
> > >
> > > Mats PETERSSON Gesendet von:
> > > xxxxx@lists.osr.com 13.09.2004 17:19
> > > Bitte antworten an “Windows System Software Devs Interest List”
> > >
> > > An: “Windows System Software Devs Interest List”
> > >
> > > Kopie:
> > > Thema: Re: [ntdev] Spinlocks
> > >
> > >
> > >
> > >
> > >
> > >
> > >
> > > In this instance, being slow means less typing
> > >
> > > Indeed a good suggestion, using a faster way to find the relevant
> > > data doesn’t remove the problem, but it certainly helps
> reduce the
> > > locked time. Good suggestion, I should’ve thought of it…
> > >
> > > –
> > > Mats
> > >
> > > xxxxx@lists.osr.com wrote on 09/13/2004 04:13:59 PM:
> > >
> > > > Ah, I’m always too slow One thing still left to say - you
> > > > could
> > > think
> > >
> > > > about alternative data-structures if your list can get very
> > > big. Like
> > > > hash-maps, b-trees or even a red-black-tree. That way you
> > > don’t avoid
> > > the
> > >
> > > > lock but you can reduce the time it takes to find one entry. The
> > > downside
> > >
> > > > is that the structures are more complicated and you have to
> > > allocate
> > > > additional storage for them (at least for hash-map and b-tree).
> > > >
> > > > Regards,
> > > >
> > > > Paul Groke
> > > >
> > > >
> > > >
> > > >
> > > >
> > > > Mats PETERSSON Gesendet von:
> > > > xxxxx@lists.osr.com 13.09.2004 16:40
> > > > Bitte antworten an “Windows System Software Devs Interest List”
> > > >
> > > > An: “Windows System Software Devs Interest List”
> > > >
> > > > Kopie:
> > > > Thema: RE: [ntdev] Spinlocks
> > > >
> > > >
> > > >
> > > >
> > > >
> > > >
> > > >
> > > > As Peter said…
> > > >
> > > > However, if you find that other threads can modify the
> > > list, there may
> > > be
> > > > ways to avoid the spin-lock, if you can live with the
> > > > side-effects: 1. Don’t ever REMOVE entries from the list, just
> > > > mark them invalid. This means that you don’t have to
> worry about
> > > > entries “going away” whilst you’re working on them (doing p =
> > > > p->next isn’t a
> > > good thing if
> > > > p isn’t valid because it’s been freed!).
> > > > 2. If you want to ADD things, make sure that it’s done in a
> > > safe manner.
> > > > This can be done in many different ways, but it’s fairly
> > > easy to use
> > > > the ExchangeInterLocked to write to the “next” pointer, which
> > > > makes the operation atomic. Of course, if the list if double
> > > linked, it may
> > > > be a
> > > bit
> > > > harder to achieve an atomic write.
> > > >
> > > > But one thing that’s always going to be a problem if you
> > > have multiple
> > > > threads access a list (or any other data structure) is what
> > > > happens when an entry isn’t consistant: Consider a delete of an
> > > element, just
> > > > after the element was found and passed on to some other
> place… so
>
> > > > this ‘other place’ is now using the element that is
> being deleted.
>
> > > > Of course,
> > > spinlocks
> > > > on the list don’t help here, and you can’t always spinlock
> > > the entire
> > > > use of
> > > the
> > > > data that came out of the list (especially if you pass it to a
> > > > different piece of code than yours and for an undefined time).
> > > > This has to be
> > > worked
> > > > around by for instance having reference counts for the
> data in the
>
> > > > list, so that you can’t delete the count.
> > > >
> > > > Another thing to consider: If this code is ALWAYS running
> > > at passive
> > > > level, you can use for instance (fast)mutex’s to protect
> > > the code from
> > > > being re-entered. This will not help your code in itself,
> > > but it will
> > > > give the time waiting for the mutex to someone else, rather
> > > than using
> > > > a spinlock which just spins away the cycles in a tight
> loop. Most
> > > > unfriendly on
> > > other
> > > > tasks in the system. Of course, if this code runs at a
> higher than
> > > PASSIVE
> > > > IRQL, then you MUST use the spinlock, as asking the OS to
> > > wait for you
> > > > isn’t allowed at higher IRQL.
> > > >
> > > > –
> > > > Mats
> > > >
> > > >
> > > > xxxxx@lists.osr.com wrote on 09/13/2004
> 03:09:57 PM:
> > > >
> > > > > if another processor could be modifying this list at the
> > > same time
> > > > > then you have to have some protection. You’re the only
> > > one who can
> > > > > tell us whether “Create List Links” can be modified
> by another
> > > > > thread at the same time as this code is running. And
> > > once you tell
> > > > > us that you’ll have your answer.
> > > > >
> > > > > -p
> > > > >
> > > > > From: xxxxx@lists.osr.com [mailto:
> > > > > xxxxx@lists.osr.com] On Behalf Of Anurag Sarin
> > > > > Sent: Monday, September 13, 2004 6:27 AM
> > > > > To: Windows System Software Devs Interest List
> > > > > Subject: [ntdev] Spinlocks
> > > >
> > > > > If I have a code like this in my CREATE Dispatch routine.
> > > And if my
> > > > > Link List can be of 100 elements or more.
> > > > > ---------------------------------------------------
> > > > > Acquire Spin Lock
> > > > > If Create Link List has elements
> > > > > {
> > > > > If this filename found in Create Link List
> > > > > {
> > > > > Release Spin lock
> > > > > Return SpyPassthrough
> > > > > }
> > > > > }
> > > > > Release Spin lock
> > > > > ----------------------------------------------------
> > > > > Is there a need to do this operation using spin locks ? Will
> > > > > this lead to unexpected behavior or performance loss for my
> > > > > driver. Any comments ?? Regards,
> > > > > Anurag
> > > > > —
> > > > > Questions? First check the Kernel Driver FAQ at http://www.
> > > > > osronline.com/article.cfm?id=256
> > > > >
> > > > > You are currently subscribed to ntdev as: unknown lmsubst tag
> > > argument:
> > > > ‘’
> > > > > To unsubscribe send a blank email to
> > > xxxxx@lists.osr.com
> > > > > —
> > > > > Questions? First check the Kernel Driver FAQ at http://www.
> > > > > osronline.com/article.cfm?id=256
> > > > >
> > > > > You are currently subscribed to ntdev as: unknown lmsubst tag
> > > argument:
> > > > ‘’
> > > > > To unsubscribe send a blank email to
> > > xxxxx@lists.osr.com
> > > > > ForwardSourceID:NT0000353E
> > > >
> > > >
> > > >
> > > > —
> > > > Questions? First check the Kernel Driver FAQ at
> > > > http://www.osronline.com/article.cfm?id=256
> > > >
> > > > You are currently subscribed to ntdev as: xxxxx@tab.at To
> > > unsubscribe
> > > > send a blank email to xxxxx@lists.osr.com
> > > >
> > > > Please visit us: www.tab.at www.championsnet.net
> > > > www.silverball.com
> > > >
> > > >
> > > >
> > > > —
> > > > Questions? First check the Kernel Driver FAQ at http://www.
> > > > osronline.com/article.cfm?id=256
> > > >
> > > > You are currently subscribed to ntdev as:
> > > xxxxx@3dlabs.com To
> > > > unsubscribe send a blank email to
> xxxxx@lists.osr.com
> > >
> > > > ForwardSourceID:NT00003572
> > >
> > >
> > >
> > > —
> > > Questions? First check the Kernel Driver FAQ at
> > > http://www.osronline.com/article.cfm?id=256
> > >
> > > You are currently subscribed to ntdev as: xxxxx@tab.at To
> > > unsubscribe send a blank email to xxxxx@lists.osr.com
> > >
> > > Please visit us: www.tab.at www.championsnet.net
> > > www.silverball.com
> > >
> > >
> > >
> > > —
> > > Questions? First check the Kernel Driver FAQ at
> > > http://www.osronline.com/article.cfm?id=256
> > >
> > > You are currently subscribed to ntdev as: xxxxx@garlic.com To
> > > unsubscribe send a blank email to xxxxx@lists.osr.com
> > >
> > >
> > >
> > >
> > >
> > > —
> > > Questions? First check the Kernel Driver FAQ at
> > > http://www.osronline.com/article.cfm?id=256
> > >
> > > You are currently subscribed to ntdev as: xxxxx@garlic.com To
> > > unsubscribe send a blank email to xxxxx@lists.osr.com
> > >
> > >
> > >
> > >
> > >
> > > —
> > > Questions? First check the Kernel Driver FAQ at
> > > http://www.osronline.com/article.cfm?id=256
> > >
> > > You are currently subscribed to ntdev as:
> > > xxxxx@windows.microsoft.com To unsubscribe send a
> blank email to
> > > xxxxx@lists.osr.com
> > >
> >
> >
> > —
> > Questions? First check the Kernel Driver FAQ at
> > http://www.osronline.com/article.cfm?id=256
> >
> > You are currently subscribed to ntdev as: unknown lmsubst tag
> > argument: ‘’ To unsubscribe send a blank email to
> > xxxxx@lists.osr.com
> >
> >
> >
> > —
> > Questions? First check the Kernel Driver FAQ at http://www.
> > osronline.com/article.cfm?id=256
> >
> > You are currently subscribed to ntdev as: unknown lmsubst tag
> > argument:
> ‘’
> > To unsubscribe send a blank email to xxxxx@lists.osr.com
>
> > ForwardSourceID:NT000036C2
>
>
>
> —
> Questions? First check the Kernel Driver FAQ at
> http://www.osronline.com/article.cfm?id=256
>
> You are currently subscribed to ntdev as: xxxxx@tab.at
> To unsubscribe send a blank email to xxxxx@lists.osr.com
>
> Please visit us: www.tab.at www.championsnet.net
> www.silverball.com
>
>
>
> —
> Questions? First check the Kernel Driver FAQ at
> http://www.osronline.com/article.cfm?id=256
>
> You are currently subscribed to ntdev as: xxxxx@divassoftware.com To
> unsubscribe send a blank email to xxxxx@lists.osr.com
>
>
>
> —
> Questions? First check the Kernel Driver FAQ at
> http://www.osronline.com/article.cfm?id=256
>
> You are currently subscribed to ntdev as: unknown lmsubst tag
> argument: ‘’
> To unsubscribe send a blank email to xxxxx@lists.osr.com
>
—
Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256
You are currently subscribed to ntdev as: unknown lmsubst tag argument: ‘’
To unsubscribe send a blank email to xxxxx@lists.osr.com
Please visit us: www.tab.at www.championsnet.net
www.silverball.com
> My driver is for single processer systems.
Forget this.
With HT, there is no more single processor systems in the world.
MS required for years that all NT kernel modules must be SMP safe, and now in
late 2004 I see the person who declares “I do not want to support SMP”.
Then go Windows 98, it has no SMP support.
I finally under stand that I would keep the spin locks and need
The law is (wait for deadlocks if you violate it):
The only exception from this is the paging IO in FSDs which arrives with FCB
locks held, but this is by far special case requring lots of additional
framework like AcquireForLazyWrite and such, and also ERESOURCE is not a
spinlock.
If there is really a need to do this - design some “transition” state in your
data structures, move to “transition” state while under a lock, and then unlock
and do IoCallDriver. Then lock back and move away from “transition” state.
Another recommendation (not a law, but a strong recommendation):
Another good recommendation:
Ideally, you must hold a lock only for short (screenful) code paths which
update some states, attach/detach the structures to the list/container etc.
Maxim Shatskih, Windows DDK MVP
StorageCraft Corporation
xxxxx@storagecraft.com
http://www.storagecraft.com