Hi Inaki,
Not sure how much help I can add to this, but having a big mouth (or is it
big fingers), I thought I’d add something:
Have you tried running your driver with VTune, and thus get to see where the
additional time is spent? I beleive you can download a “trial version” of
VTune for free from Intel’s web-site.
Using VTune would at least confirm that you’re spending the time in the
spin-lock.
The fact that it takes 30% more time with locks than without doesn’t
necessarily mean that it’s the locks themselves that take the time. Consider
this:
process 1:
lock();
do_some_processing();
unlock();
process 2:
lock();
do_some_other_thing();
unlock();
If process 2 spends 60% of the time in lock() waiting for process 1 to
release the lock, then it will obviously cause the penalty that we’re
talking of.
On a single processor system, it’s most likely that process 2 will not get
to run until process 1 has released the lock.
I may be off on some tangent here, but at least it’s my understanding that
this could be the case.
Then comes the second question: Do you actually need to have the lock around
the whole lookup of the linked list. If you only have one side that actually
modifies the structure, you can play tricks:
p = find_node(x); // Locate a candidate node.
if (found)
lock();
if (is_still_valid(x))
do_some_processing();
unlock();
This way, you don’t have the lock for the whole period of the finding the
node. Sure, it takes longer and is a bit more complex than holding the lock
for the entire block of “find and process”, but has the advantage of letting
the other side of things in when it’s able to.
You may also want to consider other things, like for instance: Having a
separate linked list with items that are ready for the reader, and another
waiting for the writer to fill them in (this of course assumes that the
writer has enough knowledge to know when something is available or not,
which may not be the case. But still, you know when you’ve filled in a node,
I presume.)
Hope this helps.
–
Mats
-----Original Message-----
From: I?aki Castillo [mailto:xxxxx@pandasoftware.es]
Sent: Wednesday, December 24, 2003 12:12 PM
To: Windows System Software Devs Interest List
Subject: [ntdev] Synchornizing Access to a Linked List: complete picture
Thanks for your answers. Here is the whole picture.
The linked list I am using stores data in non paged pool space.
The writer runs always at PASSIVE level. It allocates new nodes if necessary
and fills up the fields on each node.
Writing and allocating new nodes is rare. At most, it may happen 10 times
per minute on an average loaded machine.
Reading is another story. Readers are arbitrary threads that run at APC or
DPC levels. They never run at PASSIVE level.
The actual IRQL depends on the point from which my code is called. I assume
DPC level all the time.
Reading may be performed a lot of times, in the order of hundred of times
per second.
The reader perfoms each read in two steps: first it looks for the right
node, and, if it exists on the list, it reads all the fields in the node.
Both, writing and reading are synchronized using an ordinary (no Stack)
Spinlock.
While reading, the following tasks are performed:
1-Acquire Spinlock
2-Check the first field on each node, to look for a certain value
3-If found the right value, read the others fields of that node on local
variables .
4-Release Spinlock
There may be many nodes but I have checked that performance problem occurs
even with only a couple of nodes in the list.
I have checked also that node checking is performed correctly.
There are no calls to other functions from within the spinlock and the data
is located always in non paged pool.
Removing synchronization completely (just for testing) improves speed about
30% when code is runing on multi processor machines.
Of course this is not a solution but it means that synchronization is taking
too much time.
I know there are others ways to synchronize but I need one available at DPC.
I have not tried the new version of queued SpinLocks.
Thanks for your comments.
Inaki.
Questions? First check the Kernel Driver FAQ at
http://www.osronline.com/article.cfm?id=256
You are currently subscribed to ntdev as: xxxxx@3dlabs.com
To unsubscribe send a blank email to xxxxx@lists.osr.com