[Info-vax] writing a lock free linked list

[Bob Gezelter]

On Oct 2, 2:30 am, Joshua Lehrer <usenet_... at lehrerfamily.com> wrote:
> > Since you asked about memory barriers, I'd read up on the memory ordering
> > rules for Itanium in architecture manuals.  There are sections on Vol 1
> > (read 4.4.6 and 4.4.7) and Vol 2 (read 2.1) about memory ordering and the
> > instructions are listed in Vol 3.
>
> I just spent the last hour reading those sections of the manuals and,
> I can honestly say, I am no closer to any answers to my questions.
> Can anyone else give me a push in the right direction, or point me
> towards an explanation that isn't written for someone with technical
> knowledge far superior to mine?
>
> My remaining questions are:
>
> 1) are memory barriers needed in my code
> and
> 2) is the test for the head of the list of NULL okay?

Joshua,

I concur with John.

I am in the middle of things, and do not have the time to look in
detail at what you are doing today. However, I can share some notes
and cautions, having done this type of thing in the past on a variety
of platforms. There are several classic errors that are made when
writing this class of code. Interestingly enough, the general types of
errors are not specific to any one architecture, but are almost
universal across different architectures. By the same token, errors of
these types can live a very long time before they are actually
encountered, understood, and corrected. I personally know of several
that lived for in excess of five years after release. One was not
found for almost a decade and survived numerous reviews by senior
computer scientists.

The question is not whether the code will execute correctly on a
single CPU in a linear fashion. The question is whether the code
handles all the cases of data in write back caches, multiple
processors, multiple threads, and multiple processes at various
priorities being time sliced in an arbitrary fashion.

There is also a potential for confusion of terminology. "Locking" in
this case almost certainly DOES NOT mean OpenVMS locks as administered
by the Lock Manager using system services. Locking when mentioned in
the context of a linked list in shared storage means setting a bit to
prevent another thread of execution from trying to update the link or
the listhead at the same time, more along the lines of the spin locks
used by OpenVMS internally for access to data structures.

This is not an optional feature. It is required by the presumption
that the linked list is a data structure shared by multiple processes,
threads, and processors. Memory barriers are used to ensure that the
actual in memory contents are synchronized. Otherwise, it is possible
for another CPU to fetch stale data.

Before going down this path, I always ask clients to verify that their
application truly needs this level of access. If the frequency of
access is moderate, then a shared data structure may not be the best
alternative. In any event, I always counsel that the access to a
structure that is considered for this treatment be hidden behind an
internal API. As an initial step, a the simple implementation is done.
If the performance is inadequate, a higher performance access method
can be engineered with the same interface.

One of the likely problems with the Intel documentation is presumed
background. I would recommend getting a computer science text on
operating systems and reading about semaphores and controlling access
to shared data structures in a multiple processor environment.

- Bob Gezelter, http://www.rlgsc.com