Synchronizing access to a linked list

[OSR_Community_User]

I have a linked list that grows dinamically. I use this list to store data
that is used in different threads in a kernel driver.

By one side, updating(writing) to the list occurs a few times (say several
times per minute) while reading the list occurs many times (say thousand of
times per minute).
The writing routine works always at passive level, while the reading routine
works always at above passive level (sometimes at DPC level, sometimes at
DISPATCH level).

I have detected that working on multi processor machines this scheme does
not work well. It does work, but it incurs in great performance penalty.
If I remove the reading synchronization it works much faster, but removing
it is not a solution because the list can be updated at any time from the
writing thread.

I use SpinLocks to synchronize.

Having this picture, what would be the best method to synchronize access to
the list ?
I have been thinking on remove synchronization at reading and replacing the
linked dynamic list by a static list, though it sounds a little dirty
method.

Any suggestions ?

[OSR_Community_User]

“DPC” level and “DISPATCH_LEVEL” are the same thing, right?

Make sure your reader does not hold the lock needlessly. It frequently helps
to first run the list looking for work items and removing them onto a
private list, then (with your lock not held,) process the private list:

lock();
moveWorkItemsToPrivateList();
unlock();
processPrivateList();

If “processPrivateList()” is relatively expensive this may help as it
reduces the serialized code.

Other strategies are to partition lists (by cpu for example) in an effort to
allow some forward processing on some other list while one list is locked.

=====================
Mark Roddy

---

From: I?aki Castillo [mailto:xxxxx@pandasoftware.es]
Sent: Friday, December 19, 2003 12:49 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] Synchronizing access to a linked list

I have a linked list that grows dinamically. I use this list to
store data that is used in different threads in a kernel driver.

By one side, updating(writing) to the list occurs a few times (say
several times per minute) while reading the list occurs many times (say
thousand of times per minute).

The writing routine works always at passive level, while the reading
routine works always at above passive level (sometimes at DPC level,
sometimes at DISPATCH level).

I have detected that working on multi processor machines this scheme
does not work well. It does work, but it incurs in great performance
penalty.

If I remove the reading synchronization it works much faster, but
removing it is not a solution because the list can be updated at any time
from the writing thread.

I use SpinLocks to synchronize.

Having this picture, what would be the best method to synchronize
access to the list ?
I have been thinking on remove synchronization at reading and
replacing the linked dynamic list by a static list, though it sounds a
little dirty method.

Any suggestions ?

---

Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256

You are currently subscribed to ntdev as: xxxxx@stratus.com
To unsubscribe send a blank email to xxxxx@lists.osr.com

[OSR_Community_User]

Synchronizing access to a linked listThere might be some API’s on ddk that
does what you are looking for , multiple reader, single writer, but if I
recall most of them is defined as macro’s so that would be of some help…

Based on your access pattern, the nodes of the list has to be from Non-paged
memory, since readers are at high irql.

Using two locks, you can simulate multiple reader, single writer, and the
locks should be general enough so that you can use at any irql. And there is
hardly any need to use spinlock here I suppose

-prokash
-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of I?aki Castillo
Sent: Friday, December 19, 2003 9:49 AM
To: Windows System Software Devs Interest List
Subject: [ntdev] Synchronizing access to a linked list

I have a linked list that grows dinamically. I use this list to store data
that is used in different threads in a kernel driver.

By one side, updating(writing) to the list occurs a few times (say several
times per minute) while reading the list occurs many times (say thousand of
times per minute).

The writing routine works always at passive level, while the reading
routine works always at above passive level (sometimes at DPC level,
sometimes at DISPATCH level).

I have detected that working on multi processor machines this scheme does
not work well. It does work, but it incurs in great performance penalty.

If I remove the reading synchronization it works much faster, but removing
it is not a solution because the list can be updated at any time from the
writing thread.

I use SpinLocks to synchronize.

Having this picture, what would be the best method to synchronize access
to the list ?
I have been thinking on remove synchronization at reading and replacing
the linked dynamic list by a static list, though it sounds a little dirty
method.

Any suggestions ?

---

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

[OSR_Community_User]

Readers/Writers is a well known problem, get yourself a copy of any standard
OS book and copy the algorithm into your code; the strategy changes
depending on whether you want to give priority to reads, to writes, or no
special priority. You may be able to speed up your spinlocks by using
test-test-and-set instead of plain vanilla test-end-set, and you should
consider inserting a pause instruction into your code, as Intel recommends.
The test-test-and-set works like this:

while (yourlock);
while (testAndSet(yourlock));

It moves much of the testing to the local processor cache and basically
generates no bus traffic and little contention, the reason is, the first
while loop operates on the processor’s cached copy of that “yourlock”
synchronization variable.

Another trick is waiting a little bit before retrying , that again reduces
contention and may reduce latency as well. You can also try to structure
your list as a circular array of dword pointers, for example, use a ticket
algorithm and have it synchornize itself with a lock-exchange-add, but
that’s trickier because of the boundary conditions.

Hope this helps…

Alberto.

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of I?aki Castillo
Sent: Friday, December 19, 2003 12:49 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] Synchronizing access to a linked list

I have a linked list that grows dinamically. I use this list to store data
that is used in different threads in a kernel driver.

By one side, updating(writing) to the list occurs a few times (say several
times per minute) while reading the list occurs many times (say thousand of
times per minute).

The writing routine works always at passive level, while the reading routine
works always at above passive level (sometimes at DPC level, sometimes at
DISPATCH level).

I have detected that working on multi processor machines this scheme does
not work well. It does work, but it incurs in great performance penalty.

If I remove the reading synchronization it works much faster, but removing
it is not a solution because the list can be updated at any time from the
writing thread.

I use SpinLocks to synchronize.

Having this picture, what would be the best method to synchronize access to
the list ?
I have been thinking on remove synchronization at reading and replacing the
linked dynamic list by a static list, though it sounds a little dirty
method.

Any suggestions ?

---

Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256

You are currently subscribed to ntdev as: xxxxx@compuware.com
To unsubscribe send a blank email to xxxxx@lists.osr.com

The contents of this e-mail are intended for the named addressee only. It
contains information that may be confidential. Unless you are the named
addressee or an authorized designee, you may not copy or use it, or disclose
it to anyone else. If you received it in error please notify us immediately
and then destroy it.

[OSR_Community_User]

Alberto, you are a one-trick pony these days. KeAcquireSpinlock is correctly
written, so there is no need to reinvent that particular wheel.

=====================
Mark Roddy

---

From: Moreira, Alberto [mailto:xxxxx@compuware.com]
Sent: Friday, December 19, 2003 2:50 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] RE: Synchronizing access to a linked list

Readers/Writers is a well known problem, get yourself a copy of any
standard OS book and copy the algorithm into your code; the strategy changes
depending on whether you want to give priority to reads, to writes, or no
special priority. You may be able to speed up your spinlocks by using
test-test-and-set instead of plain vanilla test-end-set, and you should
consider inserting a pause instruction into your code, as Intel recommends.
The test-test-and-set works like this:

while (yourlock);
while (testAndSet(yourlock));

It moves much of the testing to the local processor cache and
basically generates no bus traffic and little contention, the reason is, the
first while loop operates on the processor’s cached copy of that “yourlock”
synchronization variable.

Another trick is waiting a little bit before retrying , that again
reduces contention and may reduce latency as well. You can also try to
structure your list as a circular array of dword pointers, for example, use
a ticket algorithm and have it synchornize itself with a lock-exchange-add,
but that’s trickier because of the boundary conditions.

Hope this helps…

Alberto.

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of I?aki Castillo
Sent: Friday, December 19, 2003 12:49 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] Synchronizing access to a linked list

I have a linked list that grows dinamically. I use this list
to store data that is used in different threads in a kernel driver.

By one side, updating(writing) to the list occurs a few
times (say several times per minute) while reading the list occurs many
times (say thousand of times per minute).

The writing routine works always at passive level, while the
reading routine works always at above passive level (sometimes at DPC level,
sometimes at DISPATCH level).

I have detected that working on multi processor machines
this scheme does not work well. It does work, but it incurs in great
performance penalty.

If I remove the reading synchronization it works much
faster, but removing it is not a solution because the list can be updated at
any time from the writing thread.

I use SpinLocks to synchronize.

Having this picture, what would be the best method to
synchronize access to the list ?
I have been thinking on remove synchronization at reading
and replacing the linked dynamic list by a static list, though it sounds a
little dirty method.

Any suggestions ?

---

Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256

You are currently subscribed to ntdev as:
xxxxx@compuware.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@stratus.com
To unsubscribe send a blank email to xxxxx@lists.osr.com

The contents of this e-mail are intended for the named addressee
only. It contains information that may be confidential. Unless you are the
named addressee or an authorized designee, you may not copy or use it, or
disclose it to anyone else. If you received it in error please notify us
immediately and then destroy it.

[OSR_Community_User]

Golly, Mark, I’ve seen lemming behavior before, but this is one step beyond.

I didn’t look inside their code, and I won’t, so, I’ll reverse the charges:
give me one good reason to use a facility I have no clue how it’s
implemented, specially in a performance-sensitive case !

In this case I have many questions: do they or do they not use
test-and-test-and-set ? Do they have exponential backoff after each
test-and-set, if so, which exponent do they use ? Do they use the pause
instruction, how, and where ? Do they use test-and-set, compare-replace,
exchange-add, what ?

And if they do it the most possible effective way, why is Inaki having
performance issues ?

There’s no such a thing as “correctly written” here. There’s a zillion ways
of implementing a lock. No harm done in experimenting and trying to find a
faster one.

Alberto.

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of Roddy, Mark
Sent: Friday, December 19, 2003 3:16 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] RE: Synchronizing access to a linked list

Alberto, you are a one-trick pony these days. KeAcquireSpinlock is correctly
written, so there is no need to reinvent that particular wheel.

=====================
Mark Roddy

---

From: Moreira, Alberto [mailto:xxxxx@compuware.com]
Sent: Friday, December 19, 2003 2:50 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] RE: Synchronizing access to a linked list

Readers/Writers is a well known problem, get yourself a copy of any
standard OS book and copy the algorithm into your code; the strategy changes
depending on whether you want to give priority to reads, to writes, or no
special priority. You may be able to speed up your spinlocks by using
test-test-and-set instead of plain vanilla test-end-set, and you should
consider inserting a pause instruction into your code, as Intel recommends.
The test-test-and-set works like this:

while (yourlock);
while (testAndSet(yourlock));

It moves much of the testing to the local processor cache and
basically generates no bus traffic and little contention, the reason is, the
first while loop operates on the processor’s cached copy of that “yourlock”
synchronization variable.

Another trick is waiting a little bit before retrying , that again
reduces contention and may reduce latency as well. You can also try to
structure your list as a circular array of dword pointers, for example, use
a ticket algorithm and have it synchornize itself with a lock-exchange-add,
but that’s trickier because of the boundary conditions.

Hope this helps…

Alberto.

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of I?aki Castillo
Sent: Friday, December 19, 2003 12:49 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] Synchronizing access to a linked list

I have a linked list that grows dinamically. I use this list
to store data that is used in different threads in a kernel driver.

By one side, updating(writing) to the list occurs a few
times (say several times per minute) while reading the list occurs many
times (say thousand of times per minute).

The writing routine works always at passive level, while the
reading routine works always at above passive level (sometimes at DPC level,
sometimes at DISPATCH level).

I have detected that working on multi processor machines
this scheme does not work well. It does work, but it incurs in great
performance penalty.

If I remove the reading synchronization it works much
faster, but removing it is not a solution because the list can be updated at
any time from the writing thread.

I use SpinLocks to synchronize.

Having this picture, what would be the best method to
synchronize access to the list ?
I have been thinking on remove synchronization at reading
and replacing the linked dynamic list by a static list, though it sounds a
little dirty method.

Any suggestions ?

---

Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256

You are currently subscribed to ntdev as:
xxxxx@compuware.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@stratus.com
To unsubscribe send a blank email to xxxxx@lists.osr.com

The contents of this e-mail are intended for the named addressee
only. It contains information that may be confidential. Unless you are the
named addressee or an authorized designee, you may not copy or use it, or
disclose it to anyone else. If you received it in error please notify us
immediately and then destroy it.

---

Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256

You are currently subscribed to ntdev as: xxxxx@compuware.com
To unsubscribe send a blank email to xxxxx@lists.osr.com

The contents of this e-mail are intended for the named addressee only. It
contains information that may be confidential. Unless you are the named
addressee or an authorized designee, you may not copy or use it, or disclose
it to anyone else. If you received it in error please notify us immediately
and then destroy it.

[Duane_Souder]

Well, I believe that KeAcquireSpinlock is THE supported Windows
mechanism for
single, multi, and HT Windows OS’s. It works. It is guarenteed to be
cache safe
and cache consistent.
If you write your own, you must be aware of memory cache, TLB’s,
cache flushes,
and so forth. Use the mechanisms that MS provides.
The author should review the implementation of their data structures
and the access
they need to them and the contexts (process, dispatch, APC, DPC,
Interrupt) in which
that access can occur. It can be very easy to get it wrong.
Microsoft kernel folks, any comments?
Duane

Moreira, Alberto wrote:

Golly, Mark, I’ve seen lemming behavior before, but this is one step beyond.

I didn’t look inside their code, and I won’t, so, I’ll reverse the charges:
give me one good reason to use a facility I have no clue how it’s
implemented, specially in a performance-sensitive case !

In this case I have many questions: do they or do they not use
test-and-test-and-set ? Do they have exponential backoff after each
test-and-set, if so, which exponent do they use ? Do they use the pause
instruction, how, and where ? Do they use test-and-set, compare-replace,
exchange-add, what ?

And if they do it the most possible effective way, why is Inaki having
performance issues ?

There’s no such a thing as “correctly written” here. There’s a zillion ways
of implementing a lock. No harm done in experimenting and trying to find a
faster one.

Alberto.

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of Roddy, Mark
Sent: Friday, December 19, 2003 3:16 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] RE: Synchronizing access to a linked list

Alberto, you are a one-trick pony these days. KeAcquireSpinlock is correctly
written, so there is no need to reinvent that particular wheel.

=====================
Mark Roddy

---

From: Moreira, Alberto [mailto:xxxxx@compuware.com]
Sent: Friday, December 19, 2003 2:50 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] RE: Synchronizing access to a linked list

Readers/Writers is a well known problem, get yourself a copy of any
standard OS book and copy the algorithm into your code; the strategy changes
depending on whether you want to give priority to reads, to writes, or no
special priority. You may be able to speed up your spinlocks by using
test-test-and-set instead of plain vanilla test-end-set, and you should
consider inserting a pause instruction into your code, as Intel recommends.
The test-test-and-set works like this:

while (yourlock);
while (testAndSet(yourlock));

It moves much of the testing to the local processor cache and
basically generates no bus traffic and little contention, the reason is, the
first while loop operates on the processor’s cached copy of that “yourlock”
synchronization variable.

Another trick is waiting a little bit before retrying , that again
reduces contention and may reduce latency as well. You can also try to
structure your list as a circular array of dword pointers, for example, use
a ticket algorithm and have it synchornize itself with a lock-exchange-add,
but that’s trickier because of the boundary conditions.

Hope this helps…

Alberto.

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of Iñaki Castillo
Sent: Friday, December 19, 2003 12:49 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] Synchronizing access to a linked list

I have a linked list that grows dinamically. I use this list
to store data that is used in different threads in a kernel driver.

By one side, updating(writing) to the list occurs a few
times (say several times per minute) while reading the list occurs many
times (say thousand of times per minute).

The writing routine works always at passive level, while the
reading routine works always at above passive level (sometimes at DPC level,
sometimes at DISPATCH level).

I have detected that working on multi processor machines
this scheme does not work well. It does work, but it incurs in great
performance penalty.

If I remove the reading synchronization it works much
faster, but removing it is not a solution because the list can be updated at
any time from the writing thread.

I use SpinLocks to synchronize.

Having this picture, what would be the best method to
synchronize access to the list ?
I have been thinking on remove synchronization at reading
and replacing the linked dynamic list by a static list, though it sounds a
little dirty method.

Any suggestions ?

---

Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256

You are currently subscribed to ntdev as:
xxxxx@compuware.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@stratus.com
To unsubscribe send a blank email to xxxxx@lists.osr.com

The contents of this e-mail are intended for the named addressee
only. It contains information that may be confidential. Unless you are the
named addressee or an authorized designee, you may not copy or use it, or
disclose it to anyone else. If you received it in error please notify us
immediately and then destroy it.

---

Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256

You are currently subscribed to ntdev as: xxxxx@compuware.com
To unsubscribe send a blank email to xxxxx@lists.osr.com

The contents of this e-mail are intended for the named addressee only. It
contains information that may be confidential. Unless you are the named
addressee or an authorized designee, you may not copy or use it, or disclose
it to anyone else. If you received it in error please notify us immediately
and then destroy it.

---

Questions? First check the Kernel Driver FAQ at http://www.osronline.com/article.cfm?id=256

You are currently subscribed to ntdev as: xxxxx@cisco.com
To unsubscribe send a blank email to xxxxx@lists.osr.com

[OSR_Community_User]

> -----Original Message-----

From: Moreira, Alberto [mailto:xxxxx@compuware.com]
Sent: Friday, December 19, 2003 3:32 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] RE: Synchronizing access to a linked list

Golly, Mark, I’ve seen lemming behavior before, but this is
one step beyond.

I didn’t look inside their code, and I won’t, so, I’ll
reverse the charges:
give me one good reason to use a facility I have no clue how
it’s implemented, specially in a performance-sensitive case !

Use your nifty debugger to educate yourself.

So your advice is for somebody to first go off and re-write OS primitives
even though you have no idea if the existing implementation is correct nor
do you know if his problem is lock acquisition cost. And you wonder why
quite a few of us get exasperated with your standard canned answer to all
problems?

Did it occur to you that it might be the time spent serialized, and not the
efficiency of the implementation of spinlocks themselves, causing the
problem? Did the OP complain about bus utilization? Did it occur to you that
the OP ought to look at his own code first BEFORE re-writing the OS? Is the
most common cause of poor performance related to serialization faulty lock
implementations or faulty lock-using algorithms? Don’t know? Take a wild ass
guess. Did you consider that you were advising some poor fellow to go off on
a wild goose chase likely to consume quite a bit of his time, for no
particular reason other than your own personal obsession with not using
defined OS interfaces? Somehow I suspect not.

=====================
Mark Roddy

In this case I have many questions: do they or do they not
use test-and-test-and-set ? Do they have exponential backoff
after each test-and-set, if so, which exponent do they use ?
Do they use the pause instruction, how, and where ? Do they
use test-and-set, compare-replace, exchange-add, what ?

And if they do it the most possible effective way, why is
Inaki having performance issues ?

There’s no such a thing as “correctly written” here. There’s
a zillion ways of implementing a lock. No harm done in
experimenting and trying to find a faster one.

Alberto.

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of Roddy, Mark
Sent: Friday, December 19, 2003 3:16 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] RE: Synchronizing access to a linked list

Alberto, you are a one-trick pony these days.
KeAcquireSpinlock is correctly written, so there is no need
to reinvent that particular wheel.

=====================
Mark Roddy

---

From: Moreira, Alberto [mailto:xxxxx@compuware.com]
Sent: Friday, December 19, 2003 2:50 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] RE: Synchronizing access to a linked list

Readers/Writers is a well known problem, get yourself a
copy of any standard OS book and copy the algorithm into your
code; the strategy changes depending on whether you want to
give priority to reads, to writes, or no special priority.
You may be able to speed up your spinlocks by using
test-test-and-set instead of plain vanilla test-end-set, and
you should consider inserting a pause instruction into your
code, as Intel recommends.
The test-test-and-set works like this:

while (yourlock);
while (testAndSet(yourlock));

It moves much of the testing to the local processor
cache and basically generates no bus traffic and little
contention, the reason is, the first while loop operates on
the processor’s cached copy of that “yourlock”
synchronization variable.

Another trick is waiting a little bit before retrying ,
that again reduces contention and may reduce latency as well.
You can also try to structure your list as a circular array
of dword pointers, for example, use a ticket algorithm and
have it synchornize itself with a lock-exchange-add, but
that’s trickier because of the boundary conditions.

Hope this helps…

Alberto.

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of I?aki Castillo
Sent: Friday, December 19, 2003 12:49 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] Synchronizing access to a linked list

I have a linked list that grows dinamically. I
use this list to store data that is used in different threads
in a kernel driver.

By one side, updating(writing) to the list
occurs a few times (say several times per minute) while
reading the list occurs many times (say thousand of times per
minute).

The writing routine works always at passive
level, while the reading routine works always at above
passive level (sometimes at DPC level, sometimes at DISPATCH level).

I have detected that working on multi processor
machines this scheme does not work well. It does work, but it
incurs in great performance penalty.

If I remove the reading synchronization it
works much faster, but removing it is not a solution because
the list can be updated at any time from the writing thread.

I use SpinLocks to synchronize.

Having this picture, what would be the best
method to synchronize access to the list ?
I have been thinking on remove synchronization
at reading and replacing the linked dynamic list by a static
list, though it sounds a little dirty method.

Any suggestions ?

---

Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256

You are currently subscribed to ntdev as:
xxxxx@compuware.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@stratus.com
To unsubscribe send a blank email to
xxxxx@lists.osr.com

The contents of this e-mail are intended for the named
addressee only. It contains information that may be
confidential. Unless you are the named addressee or an
authorized designee, you may not copy or use it, or disclose
it to anyone else. If you received it in error please notify
us immediately and then destroy it.

---

Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256

You are currently subscribed to ntdev as:
xxxxx@compuware.com To unsubscribe send a blank
email to xxxxx@lists.osr.com

The contents of this e-mail are intended for the named
addressee only. It contains information that may be
confidential. Unless you are the named addressee or an
authorized designee, you may not copy or use it, or disclose
it to anyone else. If you received it in error please notify
us immediately and then destroy it.

---

Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256

You are currently subscribed to ntdev as:
xxxxx@stratus.com To unsubscribe send a blank email to
xxxxx@lists.osr.com

[OSR_Community_User]

Oh, puh-leeze. You do too have a clue how the NT implementation of
KeAcquireSpinLock works. Any monkey with a debugger can read the
assembly. “I have no clue!” is a disengenuous lie, unless you’ve
intentionally avoided looking at it. It’s all of 20 lines of assembly.
It consists – shockingly! – of an interlocked bts instruction, a test
instruction, a pause instruction, a conditional return, and and
unconditional jump to the top of the loop. How simple can you get??

The original poster is obviously rather new to kernel-mode development.
Why blast them with the internals of spin-lock design? They need to
learn the basics (like wtf KeAcquireSpinLock is) before building their
own.

And it doesn’t really MATTER how KeAcquireSpinLock is implemented.
Empirically, it works fairly well. Certainly well enough for a new
developer to use. And I guarantee that it has been tested and debugged
on far more platforms than whatever you can concoct has. Unless you’ve
built your own WHQL lab and had hundreds of vendors bring their
platforms to you for certification.

Oh, god, we’re really going to have this argument all over again. This
is nauseating.

– arlie

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com] On Behalf Of Moreira, Alberto
Sent: Friday, December 19, 2003 3:32 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] RE: Synchronizing access to a linked list

Golly, Mark, I’ve seen lemming behavior before, but this is one step
beyond.

I didn’t look inside their code, and I won’t, so, I’ll reverse the
charges: give me one good reason to use a facility I have no clue how
it’s implemented, specially in a performance-sensitive case !

In this case I have many questions: do they or do they not use
test-and-test-and-set ? Do they have exponential backoff after each
test-and-set, if so, which exponent do they use ? Do they use the pause
instruction, how, and where ? Do they use test-and-set, compare-replace,
exchange-add, what ?

And if they do it the most possible effective way, why is Inaki having
performance issues ?

There’s no such a thing as “correctly written” here. There’s a zillion
ways of implementing a lock. No harm done in experimenting and trying to
find a faster one.

Alberto.

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of Roddy, Mark
Sent: Friday, December 19, 2003 3:16 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] RE: Synchronizing access to a linked list

Alberto, you are a one-trick pony these days. KeAcquireSpinlock is
correctly written, so there is no need to reinvent that particular
wheel.

=====================
Mark Roddy

---

From: Moreira, Alberto [mailto:xxxxx@compuware.com]
Sent: Friday, December 19, 2003 2:50 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] RE: Synchronizing access to a linked list

Readers/Writers is a well known problem, get yourself a copy of
any standard OS book and copy the algorithm into your code; the strategy
changes depending on whether you want to give priority to reads, to
writes, or no special priority. You may be able to speed up your
spinlocks by using test-test-and-set instead of plain vanilla
test-end-set, and you should consider inserting a pause instruction into
your code, as Intel recommends. The test-test-and-set works like this:

while (yourlock);
while (testAndSet(yourlock));

It moves much of the testing to the local processor cache and
basically generates no bus traffic and little contention, the reason is,
the first while loop operates on the processor’s cached copy of that
“yourlock” synchronization variable.

Another trick is waiting a little bit before retrying , that
again reduces contention and may reduce latency as well. You can also
try to structure your list as a circular array of dword pointers, for
example, use a ticket algorithm and have it synchornize itself with a
lock-exchange-add, but that’s trickier because of the boundary
conditions.

Hope this helps…

Alberto.

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of I?aki Castillo
Sent: Friday, December 19, 2003 12:49 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] Synchronizing access to a linked list

I have a linked list that grows dinamically. I use this
list to store data that is used in different threads in a kernel driver.

By one side, updating(writing) to the list occurs a few
times (say several times per minute) while reading the list occurs many
times (say thousand of times per minute).

The writing routine works always at passive level, while
the reading routine works always at above passive level (sometimes at
DPC level, sometimes at DISPATCH level).

I have detected that working on multi processor machines
this scheme does not work well. It does work, but it incurs in great
performance penalty.

If I remove the reading synchronization it works much
faster, but removing it is not a solution because the list can be
updated at any time from the writing thread.

I use SpinLocks to synchronize.

Having this picture, what would be the best method to
synchronize access to the list ?
I have been thinking on remove synchronization at
reading
and replacing the linked dynamic list by a static list, though it sounds
a little dirty method.

Any suggestions ?

---

Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256

You are currently subscribed to ntdev as:
xxxxx@compuware.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@stratus.com
To unsubscribe send a blank email to
xxxxx@lists.osr.com

The contents of this e-mail are intended for the named addressee
only. It contains information that may be confidential. Unless you are
the named addressee or an authorized designee, you may not copy or use
it, or disclose it to anyone else. If you received it in error please
notify us immediately and then destroy it.

---

Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256

You are currently subscribed to ntdev as: xxxxx@compuware.com
To unsubscribe send a blank email to xxxxx@lists.osr.com

The contents of this e-mail are intended for the named addressee only.
It contains information that may be confidential. Unless you are the
named addressee or an authorized designee, you may not copy or use it,
or disclose it to anyone else. If you received it in error please notify
us immediately and then destroy it.

---

Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256

You are currently subscribed to ntdev as: xxxxx@sublinear.org To
unsubscribe send a blank email to xxxxx@lists.osr.com

[OSR_Community_User]

Cache consistency is implemented by the hardware.

Alberto.

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of Duane Souder
Sent: Friday, December 19, 2003 3:49 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] RE: Synchronizing access to a linked list

Well, I believe that KeAcquireSpinlock is THE supported Windows
mechanism for
single, multi, and HT Windows OS’s. It works. It is guarenteed to be
cache safe
and cache consistent.
If you write your own, you must be aware of memory cache, TLB’s,
cache flushes,
and so forth. Use the mechanisms that MS provides.
The author should review the implementation of their data structures
and the access
they need to them and the contexts (process, dispatch, APC, DPC,
Interrupt) in which
that access can occur. It can be very easy to get it wrong.
Microsoft kernel folks, any comments?
Duane

Moreira, Alberto wrote:

Golly, Mark, I’ve seen lemming behavior before, but this is one step
beyond.

I didn’t look inside their code, and I won’t, so, I’ll reverse the charges:
give me one good reason to use a facility I have no clue how it’s
implemented, specially in a performance-sensitive case !

In this case I have many questions: do they or do they not use
test-and-test-and-set ? Do they have exponential backoff after each
test-and-set, if so, which exponent do they use ? Do they use the pause
instruction, how, and where ? Do they use test-and-set, compare-replace,
exchange-add, what ?

And if they do it the most possible effective way, why is Inaki having
performance issues ?

There’s no such a thing as “correctly written” here. There’s a zillion ways
of implementing a lock. No harm done in experimenting and trying to find a
faster one.

Alberto.

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of Roddy, Mark
Sent: Friday, December 19, 2003 3:16 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] RE: Synchronizing access to a linked list

Alberto, you are a one-trick pony these days. KeAcquireSpinlock is
correctly
written, so there is no need to reinvent that particular wheel.

=====================
Mark Roddy

---

From: Moreira, Alberto [mailto:xxxxx@compuware.com]
Sent: Friday, December 19, 2003 2:50 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] RE: Synchronizing access to a linked list

Readers/Writers is a well known problem, get yourself a copy of any
standard OS book and copy the algorithm into your code; the strategy
changes
depending on whether you want to give priority to reads, to writes, or no
special priority. You may be able to speed up your spinlocks by using
test-test-and-set instead of plain vanilla test-end-set, and you should
consider inserting a pause instruction into your code, as Intel recommends.
The test-test-and-set works like this:

while (yourlock);
while (testAndSet(yourlock));

It moves much of the testing to the local processor cache and
basically generates no bus traffic and little contention, the reason is,
the
first while loop operates on the processor’s cached copy of that “yourlock”
synchronization variable.

Another trick is waiting a little bit before retrying , that again
reduces contention and may reduce latency as well. You can also try to
structure your list as a circular array of dword pointers, for example, use
a ticket algorithm and have it synchornize itself with a lock-exchange-add,
but that’s trickier because of the boundary conditions.

Hope this helps…

Alberto.

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of Iñaki Castillo
Sent: Friday, December 19, 2003 12:49 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] Synchronizing access to a linked list

I have a linked list that grows dinamically. I use this list
to store data that is used in different threads in a kernel driver.

By one side, updating(writing) to the list occurs a few
times (say several times per minute) while reading the list occurs many
times (say thousand of times per minute).

The writing routine works always at passive level, while the
reading routine works always at above passive level (sometimes at DPC
level,
sometimes at DISPATCH level).

I have detected that working on multi processor machines
this scheme does not work well. It does work, but it incurs in great
performance penalty.

If I remove the reading synchronization it works much
faster, but removing it is not a solution because the list can be updated
at
any time from the writing thread.

I use SpinLocks to synchronize.

Having this picture, what would be the best method to
synchronize access to the list ?
I have been thinking on remove synchronization at reading
and replacing the linked dynamic list by a static list, though it sounds a
little dirty method.

Any suggestions ?

---

Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256

You are currently subscribed to ntdev as:
xxxxx@compuware.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@stratus.com
To unsubscribe send a blank email to xxxxx@lists.osr.com

The contents of this e-mail are intended for the named addressee
only. It contains information that may be confidential. Unless you are the
named addressee or an authorized designee, you may not copy or use it, or
disclose it to anyone else. If you received it in error please notify us
immediately and then destroy it.

---

Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256

You are currently subscribed to ntdev as: xxxxx@compuware.com
To unsubscribe send a blank email to xxxxx@lists.osr.com

The contents of this e-mail are intended for the named addressee only. It
contains information that may be confidential. Unless you are the named
addressee or an authorized designee, you may not copy or use it, or
disclose
it to anyone else. If you received it in error please notify us immediately
and then destroy it.

---

Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256

You are currently subscribed to ntdev as: xxxxx@cisco.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@compuware.com
To unsubscribe send a blank email to xxxxx@lists.osr.com

The contents of this e-mail are intended for the named addressee only. It
contains information that may be confidential. Unless you are the named
addressee or an authorized designee, you may not copy or use it, or disclose
it to anyone else. If you received it in error please notify us immediately
and then destroy it.

[OSR_Community_User]

It used to be a no-no to pry into other people’s machine code. And I belong
to the old school.

Now, things point to a performance problem. Some experimentation is in order
to figure out what’s going on. If I can’t achieve what I need by calling the
OS, I’ll do it my way. So, if I have my own loop, a couple of rdmsr’s here
and there and I will know whether the problem is in my code or wherever, but
if I do not have my own code, I can’t do that.

And you know what ? Two lines of code talking to the hardware isn’t that big
a deal. It takes less time for your average computer science grad student to
write that code and test it than to go read the manual to figure out how the
API call works. Big deal !

Yet, you know, my personal preference is none of the above. It’s not that
hard to write code for a self-synchronizing list that requires no spinlocks,
but here again, one must use some machine code programming.

I keep saying, I’ll reuse any code, provided I wrote it.

Alberto.

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of Roddy, Mark
Sent: Friday, December 19, 2003 3:51 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] RE: Synchronizing access to a linked list

-----Original Message-----
From: Moreira, Alberto [mailto:xxxxx@compuware.com]
Sent: Friday, December 19, 2003 3:32 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] RE: Synchronizing access to a linked list

Golly, Mark, I’ve seen lemming behavior before, but this is
one step beyond.

I didn’t look inside their code, and I won’t, so, I’ll
reverse the charges:
give me one good reason to use a facility I have no clue how
it’s implemented, specially in a performance-sensitive case !

Use your nifty debugger to educate yourself.

So your advice is for somebody to first go off and re-write OS primitives
even though you have no idea if the existing implementation is correct nor
do you know if his problem is lock acquisition cost. And you wonder why
quite a few of us get exasperated with your standard canned answer to all
problems?

Did it occur to you that it might be the time spent serialized, and not the
efficiency of the implementation of spinlocks themselves, causing the
problem? Did the OP complain about bus utilization? Did it occur to you that
the OP ought to look at his own code first BEFORE re-writing the OS? Is the
most common cause of poor performance related to serialization faulty lock
implementations or faulty lock-using algorithms? Don’t know? Take a wild ass
guess. Did you consider that you were advising some poor fellow to go off on
a wild goose chase likely to consume quite a bit of his time, for no
particular reason other than your own personal obsession with not using
defined OS interfaces? Somehow I suspect not.

=====================
Mark Roddy

In this case I have many questions: do they or do they not
use test-and-test-and-set ? Do they have exponential backoff
after each test-and-set, if so, which exponent do they use ?
Do they use the pause instruction, how, and where ? Do they
use test-and-set, compare-replace, exchange-add, what ?

And if they do it the most possible effective way, why is
Inaki having performance issues ?

There’s no such a thing as “correctly written” here. There’s
a zillion ways of implementing a lock. No harm done in
experimenting and trying to find a faster one.

Alberto.

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of Roddy, Mark
Sent: Friday, December 19, 2003 3:16 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] RE: Synchronizing access to a linked list

Alberto, you are a one-trick pony these days.
KeAcquireSpinlock is correctly written, so there is no need
to reinvent that particular wheel.

=====================
Mark Roddy

---

From: Moreira, Alberto [mailto:xxxxx@compuware.com]
Sent: Friday, December 19, 2003 2:50 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] RE: Synchronizing access to a linked list

Readers/Writers is a well known problem, get yourself a
copy of any standard OS book and copy the algorithm into your
code; the strategy changes depending on whether you want to
give priority to reads, to writes, or no special priority.
You may be able to speed up your spinlocks by using
test-test-and-set instead of plain vanilla test-end-set, and
you should consider inserting a pause instruction into your
code, as Intel recommends.
The test-test-and-set works like this:

while (yourlock);
while (testAndSet(yourlock));

It moves much of the testing to the local processor
cache and basically generates no bus traffic and little
contention, the reason is, the first while loop operates on
the processor’s cached copy of that “yourlock”
synchronization variable.

Another trick is waiting a little bit before retrying ,
that again reduces contention and may reduce latency as well.
You can also try to structure your list as a circular array
of dword pointers, for example, use a ticket algorithm and
have it synchornize itself with a lock-exchange-add, but
that’s trickier because of the boundary conditions.

Hope this helps…

Alberto.

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of Iñaki Castillo
Sent: Friday, December 19, 2003 12:49 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] Synchronizing access to a linked list

I have a linked list that grows dinamically. I
use this list to store data that is used in different threads
in a kernel driver.

By one side, updating(writing) to the list
occurs a few times (say several times per minute) while
reading the list occurs many times (say thousand of times per
minute).

The writing routine works always at passive
level, while the reading routine works always at above
passive level (sometimes at DPC level, sometimes at DISPATCH level).

I have detected that working on multi processor
machines this scheme does not work well. It does work, but it
incurs in great performance penalty.

If I remove the reading synchronization it
works much faster, but removing it is not a solution because
the list can be updated at any time from the writing thread.

I use SpinLocks to synchronize.

Having this picture, what would be the best
method to synchronize access to the list ?
I have been thinking on remove synchronization
at reading and replacing the linked dynamic list by a static
list, though it sounds a little dirty method.

Any suggestions ?

---

Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256

You are currently subscribed to ntdev as:
xxxxx@compuware.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@stratus.com
To unsubscribe send a blank email to
xxxxx@lists.osr.com

The contents of this e-mail are intended for the named
addressee only. It contains information that may be
confidential. Unless you are the named addressee or an
authorized designee, you may not copy or use it, or disclose
it to anyone else. If you received it in error please notify
us immediately and then destroy it.

---

Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256

You are currently subscribed to ntdev as:
xxxxx@compuware.com To unsubscribe send a blank
email to xxxxx@lists.osr.com

The contents of this e-mail are intended for the named
addressee only. It contains information that may be
confidential. Unless you are the named addressee or an
authorized designee, you may not copy or use it, or disclose
it to anyone else. If you received it in error please notify
us immediately and then destroy it.

---

Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256

You are currently subscribed to ntdev as:
xxxxx@stratus.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@compuware.com
To unsubscribe send a blank email to xxxxx@lists.osr.com

The contents of this e-mail are intended for the named addressee only. It
contains information that may be confidential. Unless you are the named
addressee or an authorized designee, you may not copy or use it, or disclose
it to anyone else. If you received it in error please notify us immediately
and then destroy it.

[OSR_Community_User]

Indeed, Arlie, it’s not my custom to look at other people’s machine code.

Now, if I’m going to use your report over that piece of code, I may be able
to safely say, it does not use test-and-test-and-set. I made one suggestion,
which was, try to use test-and-test-and-set to see if there’s any
performance increase: that suggestion is still valid. Further, if what you
write about that code is right, they don’t use any kind of backoff in case
of a test and set conflict either. Which was the second suggestion I made:
try to put some backoff between retries to see if things improve: that
suggestion is still valid.

Now, why blast the poster with internals of spinlock design ? Because this
is an elementary part of Operating Systems 101, which every kernel developer
should know inside out. If you don’t know what’s a test and set, if you
limit yourself to believe that a spinlock is a Windows call, then I’m not
sure I’m going to call you a kernel developer - I’ll send you to the lab and
give you a homework: implement a test and set, implement a
test-test-and-set, add a pause to it, add backoff to it, experiment with
exponential backoff, grok the difference - now you are ready to use the API,
because you know some of the things that are going on under the hood.

We’re talking about two lines of code, no ? Big deal. And ah, it’s YOU GUYS
who keep bringing this nonsense over and again. All I did was to give two
rather pertinent suggestions of how to address a performance problem.

Alberto.

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of Arlie Davis
Sent: Friday, December 19, 2003 4:01 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] RE: Synchronizing access to a linked list

Oh, puh-leeze. You do too have a clue how the NT implementation of
KeAcquireSpinLock works. Any monkey with a debugger can read the
assembly. “I have no clue!” is a disengenuous lie, unless you’ve
intentionally avoided looking at it. It’s all of 20 lines of assembly.
It consists – shockingly! – of an interlocked bts instruction, a test
instruction, a pause instruction, a conditional return, and and
unconditional jump to the top of the loop. How simple can you get??

The original poster is obviously rather new to kernel-mode development.
Why blast them with the internals of spin-lock design? They need to
learn the basics (like wtf KeAcquireSpinLock is) before building their
own.

And it doesn’t really MATTER how KeAcquireSpinLock is implemented.
Empirically, it works fairly well. Certainly well enough for a new
developer to use. And I guarantee that it has been tested and debugged
on far more platforms than whatever you can concoct has. Unless you’ve
built your own WHQL lab and had hundreds of vendors bring their
platforms to you for certification.

Oh, god, we’re really going to have this argument all over again. This
is nauseating.

– arlie

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com] On Behalf Of Moreira, Alberto
Sent: Friday, December 19, 2003 3:32 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] RE: Synchronizing access to a linked list

Golly, Mark, I’ve seen lemming behavior before, but this is one step
beyond.

I didn’t look inside their code, and I won’t, so, I’ll reverse the
charges: give me one good reason to use a facility I have no clue how
it’s implemented, specially in a performance-sensitive case !

In this case I have many questions: do they or do they not use
test-and-test-and-set ? Do they have exponential backoff after each
test-and-set, if so, which exponent do they use ? Do they use the pause
instruction, how, and where ? Do they use test-and-set, compare-replace,
exchange-add, what ?

And if they do it the most possible effective way, why is Inaki having
performance issues ?

There’s no such a thing as “correctly written” here. There’s a zillion
ways of implementing a lock. No harm done in experimenting and trying to
find a faster one.

Alberto.

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of Roddy, Mark
Sent: Friday, December 19, 2003 3:16 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] RE: Synchronizing access to a linked list

Alberto, you are a one-trick pony these days. KeAcquireSpinlock is
correctly written, so there is no need to reinvent that particular
wheel.

=====================
Mark Roddy

---

From: Moreira, Alberto [mailto:xxxxx@compuware.com]
Sent: Friday, December 19, 2003 2:50 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] RE: Synchronizing access to a linked list

Readers/Writers is a well known problem, get yourself a copy of
any standard OS book and copy the algorithm into your code; the strategy
changes depending on whether you want to give priority to reads, to
writes, or no special priority. You may be able to speed up your
spinlocks by using test-test-and-set instead of plain vanilla
test-end-set, and you should consider inserting a pause instruction into
your code, as Intel recommends. The test-test-and-set works like this:

while (yourlock);
while (testAndSet(yourlock));

It moves much of the testing to the local processor cache and
basically generates no bus traffic and little contention, the reason is,
the first while loop operates on the processor’s cached copy of that
“yourlock” synchronization variable.

Another trick is waiting a little bit before retrying , that
again reduces contention and may reduce latency as well. You can also
try to structure your list as a circular array of dword pointers, for
example, use a ticket algorithm and have it synchornize itself with a
lock-exchange-add, but that’s trickier because of the boundary
conditions.

Hope this helps…

Alberto.

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of Iñaki Castillo
Sent: Friday, December 19, 2003 12:49 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] Synchronizing access to a linked list

I have a linked list that grows dinamically. I use this
list to store data that is used in different threads in a kernel driver.

By one side, updating(writing) to the list occurs a few
times (say several times per minute) while reading the list occurs many
times (say thousand of times per minute).

The writing routine works always at passive level, while
the reading routine works always at above passive level (sometimes at
DPC level, sometimes at DISPATCH level).

I have detected that working on multi processor machines
this scheme does not work well. It does work, but it incurs in great
performance penalty.

If I remove the reading synchronization it works much
faster, but removing it is not a solution because the list can be
updated at any time from the writing thread.

I use SpinLocks to synchronize.

Having this picture, what would be the best method to
synchronize access to the list ?
I have been thinking on remove synchronization at
reading
and replacing the linked dynamic list by a static list, though it sounds
a little dirty method.

Any suggestions ?

---

Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256

You are currently subscribed to ntdev as:
xxxxx@compuware.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@stratus.com
To unsubscribe send a blank email to
xxxxx@lists.osr.com

The contents of this e-mail are intended for the named addressee
only. It contains information that may be confidential. Unless you are
the named addressee or an authorized designee, you may not copy or use
it, or disclose it to anyone else. If you received it in error please
notify us immediately and then destroy it.

---

Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256

You are currently subscribed to ntdev as: xxxxx@compuware.com
To unsubscribe send a blank email to xxxxx@lists.osr.com

The contents of this e-mail are intended for the named addressee only.
It contains information that may be confidential. Unless you are the
named addressee or an authorized designee, you may not copy or use it,
or disclose it to anyone else. If you received it in error please notify
us immediately and then destroy it.

---

Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256

You are currently subscribed to ntdev as: xxxxx@sublinear.org 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@compuware.com
To unsubscribe send a blank email to xxxxx@lists.osr.com

The contents of this e-mail are intended for the named addressee only. It
contains information that may be confidential. Unless you are the named
addressee or an authorized designee, you may not copy or use it, or disclose
it to anyone else. If you received it in error please notify us immediately
and then destroy it.

[OSR_Community_User]

>

I keep saying, I’ll reuse any code, provided I wrote it.

Alberto.

Isn’t that ironic? You do understand that your employer, Compuware/Numega,
sells a re-useable c++ class library, right? I think that phrase of yours
ought to be their next advertising campaign slogan.

I apologize for getting sucked into Alberto’s trolling. The only reason I
responded is that he was giving some newbie a bum steer.

=====================
Mark Roddy

[OSR_Community_User]

Well, Bubba, lemming is as lemming does. Do I follow Alberto over the cliff,
or follow Jake Ohins, Nathan Obr, Peter Weiland, Walter Oney, Jamey Kirby,
Gary Little (oh that’s me) AWAY from the cliff.

'Nuff said.

–
Gary G. Little
Seagate Technologies, LLC

“Moreira, Alberto” wrote in message
news:xxxxx@ntdev…

Golly, Mark, I’ve seen lemming behavior before, but this is one step beyond.

I didn’t look inside their code, and I won’t, so, I’ll reverse the charges:
give me one good reason to use a facility I have no clue how it’s
implemented, specially in a performance-sensitive case !

In this case I have many questions: do they or do they not use
test-and-test-and-set ? Do they have exponential backoff after each
test-and-set, if so, which exponent do they use ? Do they use the pause
instruction, how, and where ? Do they use test-and-set, compare-replace,
exchange-add, what ?

And if they do it the most possible effective way, why is Inaki having
performance issues ?

There’s no such a thing as “correctly written” here. There’s a zillion ways
of implementing a lock. No harm done in experimenting and trying to find a
faster one.

Alberto.

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of Roddy, Mark
Sent: Friday, December 19, 2003 3:16 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] RE: Synchronizing access to a linked list

Alberto, you are a one-trick pony these days. KeAcquireSpinlock is correctly
written, so there is no need to reinvent that particular wheel.

=====================
Mark Roddy

________________________________

From: Moreira, Alberto [mailto:xxxxx@compuware.com]
Sent: Friday, December 19, 2003 2:50 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] RE: Synchronizing access to a linked list

Readers/Writers is a well known problem, get yourself a copy of any
standard OS book and copy the algorithm into your code; the strategy changes
depending on whether you want to give priority to reads, to writes, or no
special priority. You may be able to speed up your spinlocks by using
test-test-and-set instead of plain vanilla test-end-set, and you should
consider inserting a pause instruction into your code, as Intel recommends.
The test-test-and-set works like this:

while (yourlock);
while (testAndSet(yourlock));

It moves much of the testing to the local processor cache and
basically generates no bus traffic and little contention, the reason is, the
first while loop operates on the processor’s cached copy of that “yourlock”
synchronization variable.

Another trick is waiting a little bit before retrying , that again
reduces contention and may reduce latency as well. You can also try to
structure your list as a circular array of dword pointers, for example, use
a ticket algorithm and have it synchornize itself with a lock-exchange-add,
but that’s trickier because of the boundary conditions.

Hope this helps…

Alberto.

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of Iñaki Castillo
Sent: Friday, December 19, 2003 12:49 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] Synchronizing access to a linked list

I have a linked list that grows dinamically. I use this list
to store data that is used in different threads in a kernel driver.

By one side, updating(writing) to the list occurs a few
times (say several times per minute) while reading the list occurs many
times (say thousand of times per minute).

The writing routine works always at passive level, while the
reading routine works always at above passive level (sometimes at DPC level,
sometimes at DISPATCH level).

I have detected that working on multi processor machines
this scheme does not work well. It does work, but it incurs in great
performance penalty.

If I remove the reading synchronization it works much
faster, but removing it is not a solution because the list can be updated at
any time from the writing thread.

I use SpinLocks to synchronize.

Having this picture, what would be the best method to
synchronize access to the list ?
I have been thinking on remove synchronization at reading
and replacing the linked dynamic list by a static list, though it sounds a
little dirty method.

Any suggestions ?

—
Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256

You are currently subscribed to ntdev as:
xxxxx@compuware.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@stratus.com
To unsubscribe send a blank email to xxxxx@lists.osr.com

The contents of this e-mail are intended for the named addressee
only. It contains information that may be confidential. Unless you are the
named addressee or an authorized designee, you may not copy or use it, or
disclose it to anyone else. If you received it in error please notify us
immediately and then destroy it.

—
Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256

You are currently subscribed to ntdev as: xxxxx@compuware.com
To unsubscribe send a blank email to xxxxx@lists.osr.com

The contents of this e-mail are intended for the named addressee only. It
contains information that may be confidential. Unless you are the named
addressee or an authorized designee, you may not copy or use it, or disclose
it to anyone else. If you received it in error please notify us immediately
and then destroy it.

[OSR_Community_User]

Gary, our product’s alive and kicking, lots of people use it. And we’re not
known for dropping the ball that often either, nor are we bashful to bypass
the OS when we need to.

Alberto.

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of Gary G. Little
Sent: Friday, December 19, 2003 4:30 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] Re: Synchronizing access to a linked list

Well, Bubba, lemming is as lemming does. Do I follow Alberto over the cliff,
or follow Jake Ohins, Nathan Obr, Peter Weiland, Walter Oney, Jamey Kirby,
Gary Little (oh that’s me) AWAY from the cliff.

'Nuff said.

–
Gary G. Little
Seagate Technologies, LLC

“Moreira, Alberto” wrote in message
news:xxxxx@ntdev…

Golly, Mark, I’ve seen lemming behavior before, but this is one step beyond.

I didn’t look inside their code, and I won’t, so, I’ll reverse the charges:
give me one good reason to use a facility I have no clue how it’s
implemented, specially in a performance-sensitive case !

In this case I have many questions: do they or do they not use
test-and-test-and-set ? Do they have exponential backoff after each
test-and-set, if so, which exponent do they use ? Do they use the pause
instruction, how, and where ? Do they use test-and-set, compare-replace,
exchange-add, what ?

And if they do it the most possible effective way, why is Inaki having
performance issues ?

There’s no such a thing as “correctly written” here. There’s a zillion ways
of implementing a lock. No harm done in experimenting and trying to find a
faster one.

Alberto.

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of Roddy, Mark
Sent: Friday, December 19, 2003 3:16 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] RE: Synchronizing access to a linked list

Alberto, you are a one-trick pony these days. KeAcquireSpinlock is correctly
written, so there is no need to reinvent that particular wheel.

=====================
Mark Roddy

________________________________

From: Moreira, Alberto [mailto:xxxxx@compuware.com]
Sent: Friday, December 19, 2003 2:50 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] RE: Synchronizing access to a linked list

Readers/Writers is a well known problem, get yourself a copy of any
standard OS book and copy the algorithm into your code; the strategy changes
depending on whether you want to give priority to reads, to writes, or no
special priority. You may be able to speed up your spinlocks by using
test-test-and-set instead of plain vanilla test-end-set, and you should
consider inserting a pause instruction into your code, as Intel recommends.
The test-test-and-set works like this:

while (yourlock);
while (testAndSet(yourlock));

It moves much of the testing to the local processor cache and
basically generates no bus traffic and little contention, the reason is, the
first while loop operates on the processor’s cached copy of that “yourlock”
synchronization variable.

Another trick is waiting a little bit before retrying , that again
reduces contention and may reduce latency as well. You can also try to
structure your list as a circular array of dword pointers, for example, use
a ticket algorithm and have it synchornize itself with a lock-exchange-add,
but that’s trickier because of the boundary conditions.

Hope this helps…

Alberto.

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of I?aki Castillo
Sent: Friday, December 19, 2003 12:49 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] Synchronizing access to a linked list

I have a linked list that grows dinamically. I use this list
to store data that is used in different threads in a kernel driver.

By one side, updating(writing) to the list occurs a few
times (say several times per minute) while reading the list occurs many
times (say thousand of times per minute).

The writing routine works always at passive level, while the
reading routine works always at above passive level (sometimes at DPC level,
sometimes at DISPATCH level).

I have detected that working on multi processor machines
this scheme does not work well. It does work, but it incurs in great
performance penalty.

If I remove the reading synchronization it works much
faster, but removing it is not a solution because the list can be updated at
any time from the writing thread.

I use SpinLocks to synchronize.

Having this picture, what would be the best method to
synchronize access to the list ?
I have been thinking on remove synchronization at reading
and replacing the linked dynamic list by a static list, though it sounds a
little dirty method.

Any suggestions ?

—
Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256

You are currently subscribed to ntdev as:
xxxxx@compuware.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@stratus.com
To unsubscribe send a blank email to xxxxx@lists.osr.com

The contents of this e-mail are intended for the named addressee
only. It contains information that may be confidential. Unless you are the
named addressee or an authorized designee, you may not copy or use it, or
disclose it to anyone else. If you received it in error please notify us
immediately and then destroy it.

—
Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256

You are currently subscribed to ntdev as: xxxxx@compuware.com
To unsubscribe send a blank email to xxxxx@lists.osr.com

The contents of this e-mail are intended for the named addressee only. It
contains information that may be confidential. Unless you are the named
addressee or an authorized designee, you may not copy or use it, or disclose
it to anyone else. If you received it in error please notify us immediately
and then destroy it.

—
Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256

You are currently subscribed to ntdev as: xxxxx@compuware.com
To unsubscribe send a blank email to xxxxx@lists.osr.com

The contents of this e-mail are intended for the named addressee only. It
contains information that may be confidential. Unless you are the named
addressee or an authorized designee, you may not copy or use it, or disclose
it to anyone else. If you received it in error please notify us immediately
and then destroy it.

[OSR_Community_User]

Someone please make the bad men stop.

-----Original Message-----
From: Moreira, Alberto [mailto:xxxxx@compuware.com]
Sent: Friday, December 19, 2003 3:38 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] Re: Synchronizing access to a linked list

Gary, our product’s alive and kicking, lots of people use it. And we’re not
known for dropping the ball that often either, nor are we bashful to bypass
the OS when we need to.

Alberto.

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of Gary G. Little
Sent: Friday, December 19, 2003 4:30 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] Re: Synchronizing access to a linked list

Well, Bubba, lemming is as lemming does. Do I follow Alberto over the cliff,
or follow Jake Ohins, Nathan Obr, Peter Weiland, Walter Oney, Jamey Kirby,
Gary Little (oh that’s me) AWAY from the cliff.

'Nuff said.

–
Gary G. Little
Seagate Technologies, LLC

“Moreira, Alberto” wrote in message
news:xxxxx@ntdev…

Golly, Mark, I’ve seen lemming behavior before, but this is one step beyond.

I didn’t look inside their code, and I won’t, so, I’ll reverse the charges:
give me one good reason to use a facility I have no clue how it’s
implemented, specially in a performance-sensitive case !

In this case I have many questions: do they or do they not use
test-and-test-and-set ? Do they have exponential backoff after each
test-and-set, if so, which exponent do they use ? Do they use the pause
instruction, how, and where ? Do they use test-and-set, compare-replace,
exchange-add, what ?

And if they do it the most possible effective way, why is Inaki having
performance issues ?

There’s no such a thing as “correctly written” here. There’s a zillion ways
of implementing a lock. No harm done in experimenting and trying to find a
faster one.

Alberto.

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of Roddy, Mark
Sent: Friday, December 19, 2003 3:16 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] RE: Synchronizing access to a linked list

Alberto, you are a one-trick pony these days. KeAcquireSpinlock is correctly
written, so there is no need to reinvent that particular wheel.

=====================
Mark Roddy

________________________________

From: Moreira, Alberto [mailto:xxxxx@compuware.com]
Sent: Friday, December 19, 2003 2:50 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] RE: Synchronizing access to a linked list

Readers/Writers is a well known problem, get yourself a copy of any standard
OS book and copy the algorithm into your code; the strategy changes
depending on whether you want to give priority to reads, to writes, or no
special priority. You may be able to speed up your spinlocks by using
test-test-and-set instead of plain vanilla test-end-set, and you should
consider inserting a pause instruction into your code, as Intel recommends.
The test-test-and-set works like this:

while (yourlock);
while (testAndSet(yourlock));

It moves much of the testing to the local processor cache and basically
generates no bus traffic and little contention, the reason is, the first
while loop operates on the processor’s cached copy of that “yourlock”
synchronization variable.

Another trick is waiting a little bit before retrying , that again reduces
contention and may reduce latency as well. You can also try to structure
your list as a circular array of dword pointers, for example, use a ticket
algorithm and have it synchornize itself with a lock-exchange-add, but
that’s trickier because of the boundary conditions.

Hope this helps…

Alberto.

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of Iñaki Castillo
Sent: Friday, December 19, 2003 12:49 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] Synchronizing access to a linked list

I have a linked list that grows dinamically. I use this list
to store data that is used in different threads in a kernel driver.

By one side, updating(writing) to the list occurs a few
times (say several times per minute) while reading the list occurs many
times (say thousand of times per minute).

The writing routine works always at passive level, while the reading routine
works always at above passive level (sometimes at DPC level, sometimes at
DISPATCH level).

I have detected that working on multi processor machines
this scheme does not work well. It does work, but it incurs in great
performance penalty.

If I remove the reading synchronization it works much
faster, but removing it is not a solution because the list can be updated at
any time from the writing thread.

I use SpinLocks to synchronize.

Having this picture, what would be the best method to synchronize access to
the list ? I have been thinking on remove synchronization at reading and
replacing the linked dynamic list by a static list, though it sounds a
little dirty method.

Any suggestions ?

—
Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256

You are currently subscribed to ntdev as: xxxxx@compuware.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@stratus.com To
unsubscribe send a blank email to xxxxx@lists.osr.com

The contents of this e-mail are intended for the named addressee only. It
contains information that may be confidential. Unless you are the named
addressee or an authorized designee, you may not copy or use it, or disclose
it to anyone else. If you received it in error please notify us immediately
and then destroy it.

—
Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256

You are currently subscribed to ntdev as: xxxxx@compuware.com To
unsubscribe send a blank email to xxxxx@lists.osr.com

The contents of this e-mail are intended for the named addressee only. It
contains information that may be confidential. Unless you are the named
addressee or an authorized designee, you may not copy or use it, or disclose
it to anyone else. If you received it in error please notify us immediately
and then destroy it.

—
Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256

You are currently subscribed to ntdev as: xxxxx@compuware.com To
unsubscribe send a blank email to xxxxx@lists.osr.com

The contents of this e-mail are intended for the named addressee only. It
contains information that may be confidential. Unless you are the named
addressee or an authorized designee, you may not copy or use it, or disclose
it to anyone else. If you received it in error please notify us immediately
and then destroy it.

—
Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256

You are currently subscribed to ntdev as: xxxxx@xiotech.com To
unsubscribe send a blank email to xxxxx@lists.osr.com

[OSR_Community_User]

Well it’s the holiday time. And in particular I dont see anyside is wrong.
That is the beauty of engineering, as opposed to pure science ( where most
of the things are soldered with proof). If it were extreemly bad, then I
would have taken my right “Dirty Harry” and fireoff on both side. It is so
f’ing easy to chat this shitout of the any region, since it is primarily
based on *policy* and *decision*…

So everyone here is right in their own way.

If Dekker’s algorithm is invented to circumvent test-and-set for machines
that doesnothave this, anything and everything is possible, just one has to
bear the pain of bearing a child …

-prokash
FROM THE DESK OF DIRTY HARRY.

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of Swanson, Tom
Sent: Friday, December 19, 2003 1:53 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] Re: Synchronizing access to a linked list

Someone please make the bad men stop.

-----Original Message-----
From: Moreira, Alberto [mailto:xxxxx@compuware.com]
Sent: Friday, December 19, 2003 3:38 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] Re: Synchronizing access to a linked list

Gary, our product’s alive and kicking, lots of people use it. And we’re not
known for dropping the ball that often either, nor are we bashful to bypass
the OS when we need to.

Alberto.

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of Gary G. Little
Sent: Friday, December 19, 2003 4:30 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] Re: Synchronizing access to a linked list

Well, Bubba, lemming is as lemming does. Do I follow Alberto over the cliff,
or follow Jake Ohins, Nathan Obr, Peter Weiland, Walter Oney, Jamey Kirby,
Gary Little (oh that’s me) AWAY from the cliff.

'Nuff said.

–
Gary G. Little
Seagate Technologies, LLC

“Moreira, Alberto” wrote in message
news:xxxxx@ntdev…

Golly, Mark, I’ve seen lemming behavior before, but this is one step beyond.

I didn’t look inside their code, and I won’t, so, I’ll reverse the charges:
give me one good reason to use a facility I have no clue how it’s
implemented, specially in a performance-sensitive case !

In this case I have many questions: do they or do they not use
test-and-test-and-set ? Do they have exponential backoff after each
test-and-set, if so, which exponent do they use ? Do they use the pause
instruction, how, and where ? Do they use test-and-set, compare-replace,
exchange-add, what ?

And if they do it the most possible effective way, why is Inaki having
performance issues ?

There’s no such a thing as “correctly written” here. There’s a zillion ways
of implementing a lock. No harm done in experimenting and trying to find a
faster one.

Alberto.

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of Roddy, Mark
Sent: Friday, December 19, 2003 3:16 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] RE: Synchronizing access to a linked list

Alberto, you are a one-trick pony these days. KeAcquireSpinlock is correctly
written, so there is no need to reinvent that particular wheel.

=====================
Mark Roddy

________________________________

From: Moreira, Alberto [mailto:xxxxx@compuware.com]
Sent: Friday, December 19, 2003 2:50 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] RE: Synchronizing access to a linked list

Readers/Writers is a well known problem, get yourself a copy of any standard
OS book and copy the algorithm into your code; the strategy changes
depending on whether you want to give priority to reads, to writes, or no
special priority. You may be able to speed up your spinlocks by using
test-test-and-set instead of plain vanilla test-end-set, and you should
consider inserting a pause instruction into your code, as Intel recommends.
The test-test-and-set works like this:

while (yourlock);
while (testAndSet(yourlock));

It moves much of the testing to the local processor cache and basically
generates no bus traffic and little contention, the reason is, the first
while loop operates on the processor’s cached copy of that “yourlock”
synchronization variable.

Another trick is waiting a little bit before retrying , that again reduces
contention and may reduce latency as well. You can also try to structure
your list as a circular array of dword pointers, for example, use a ticket
algorithm and have it synchornize itself with a lock-exchange-add, but
that’s trickier because of the boundary conditions.

Hope this helps…

Alberto.

-----Original Message-----
From: xxxxx@lists.osr.com
[mailto:xxxxx@lists.osr.com]On Behalf Of I?aki Castillo
Sent: Friday, December 19, 2003 12:49 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] Synchronizing access to a linked list

I have a linked list that grows dinamically. I use this list
to store data that is used in different threads in a kernel driver.

By one side, updating(writing) to the list occurs a few
times (say several times per minute) while reading the list occurs many
times (say thousand of times per minute).

The writing routine works always at passive level, while the reading routine
works always at above passive level (sometimes at DPC level, sometimes at
DISPATCH level).

I have detected that working on multi processor machines
this scheme does not work well. It does work, but it incurs in great
performance penalty.

If I remove the reading synchronization it works much
faster, but removing it is not a solution because the list can be updated at
any time from the writing thread.

I use SpinLocks to synchronize.

Having this picture, what would be the best method to synchronize access to
the list ? I have been thinking on remove synchronization at reading and
replacing the linked dynamic list by a static list, though it sounds a
little dirty method.

Any suggestions ?

—
Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256

You are currently subscribed to ntdev as: xxxxx@compuware.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@stratus.com To
unsubscribe send a blank email to xxxxx@lists.osr.com

The contents of this e-mail are intended for the named addressee only. It
contains information that may be confidential. Unless you are the named
addressee or an authorized designee, you may not copy or use it, or disclose
it to anyone else. If you received it in error please notify us immediately
and then destroy it.

—
Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256

You are currently subscribed to ntdev as: xxxxx@compuware.com To
unsubscribe send a blank email to xxxxx@lists.osr.com

The contents of this e-mail are intended for the named addressee only. It
contains information that may be confidential. Unless you are the named
addressee or an authorized designee, you may not copy or use it, or disclose
it to anyone else. If you received it in error please notify us immediately
and then destroy it.

—
Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256

You are currently subscribed to ntdev as: xxxxx@compuware.com To
unsubscribe send a blank email to xxxxx@lists.osr.com

The contents of this e-mail are intended for the named addressee only. It
contains information that may be confidential. Unless you are the named
addressee or an authorized designee, you may not copy or use it, or disclose
it to anyone else. If you received it in error please notify us immediately
and then destroy it.

—
Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256

You are currently subscribed to ntdev as: xxxxx@xiotech.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

[Nick_Ryan]

Moreira, Alberto wrote:

It used to be a no-no to pry into other people’s machine code. And I belong
to the old school.

Alberto, try to write a filesystem filter driver without having to dive
into NTFS and redirector assembly and I promise I will found a new
religion with you as chief diety. You can’t bypass the OS since there’s
no hardware to talk to here.

–
Nick Ryan (MVP for DDK)

[OSR_Community_User]

On Sat, 2003-12-20 at 13:03, Nick Ryan wrote:

Moreira, Alberto wrote:
> It used to be a no-no to pry into other people’s machine code. And I belong
> to the old school.

Alberto, try to write a filesystem filter driver without having to dive
into NTFS and redirector assembly and I promise I will found a new
religion with you as chief diety. You can’t bypass the OS since there’s
no hardware to talk to here.

Not to take sides in this issue but it does raise an interesting
question - my EULA tells me I cannot reverse-engineer Windows (other
than for an exception relating to my local laws, with which I am
generally unfamiliar). Lots of people here advocate tracing into the OS
with WinDbg or SoftICE, but would those same people advocate opening up
ntoskrnl.exe in IDA and doing a proper disassembly?

I wonder what Microsoft’s position is on this issue - if you’re not
going to document chunks of code (which is fine by me), you have to let
people get their jobs done in other ways (i.e. reverse engineering for
the purpose of understanding).

I wonder how many driver writers are forced to violate the EULA just to
do their job, hoping that Microsoft will not decide to call them on it.
I don’t see why Microsoft *would* make a stink about this, but the fact
that they *can* is enough to cause worry.

-sd

[Nick_Ryan]

I believe that Microsoft would have a very hard time doing this. Of
course I’m no lawyer, but there has clearly been tacit acceptance of
this technique for years by Microsoft in certain categories of Windows
development. Maybe this will change now that the driver development
environment is improving, but if Microsoft does want to begin
enforcement, they have to give clear and fair warning.

Steve Dispensa wrote:

On Sat, 2003-12-20 at 13:03, Nick Ryan wrote:

>Moreira, Alberto wrote:
>
>>It used to be a no-no to pry into other people’s machine code. And I belong
>>to the old school.
>
>Alberto, try to write a filesystem filter driver without having to dive
>into NTFS and redirector assembly and I promise I will found a new
>religion with you as chief diety. You can’t bypass the OS since there’s
>no hardware to talk to here.

Not to take sides in this issue but it does raise an interesting
question - my EULA tells me I cannot reverse-engineer Windows (other
than for an exception relating to my local laws, with which I am
generally unfamiliar). Lots of people here advocate tracing into the OS
with WinDbg or SoftICE, but would those same people advocate opening up
ntoskrnl.exe in IDA and doing a proper disassembly?

I wonder what Microsoft’s position is on this issue - if you’re not
going to document chunks of code (which is fine by me), you have to let
people get their jobs done in other ways (i.e. reverse engineering for
the purpose of understanding).

I wonder how many driver writers are forced to violate the EULA just to
do their job, hoping that Microsoft will not decide to call them on it.
I don’t see why Microsoft *would* make a stink about this, but the fact
that they *can* is enough to cause worry.

-sd

–
Nick Ryan (MVP for DDK)