[Info-vax] writing a lock free linked list

[John Wallace]

On Oct 3, 1:58 am, "John Reagan" <johnrrea... at earthlink.net> wrote:
> "Joshua Lehrer" <usenet_... at lehrerfamily.com> wrote in message
>
> news:ef3af335-dd4f-4fca-b608-f9599a497943 at e8g2000yqo.googlegroups.com...
>
>
>
> >> 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?
>
> Memory barriers give an order to your memory reads/writes.  Consider code
> that fills in a buffer and then sets a flag saying the buffer is ready.  If
> you don't use a barrier, the write to the ready-flag might actually be
> visible to others before the last write into the buffer.
>
> Or consider some shared global counter (ie, semaphore) which counts the
> number of threads reading some particular global section.  Of course, you'll
> want some atomic operation to increment/decrement the count, but also code
> that is checking the count prior to reading a buffer.  You might want
> barriers there as well if your algorithm cannot tolerate the read of the
> buffer occurring before the read of the flag.
>
> If the Itanium books are confusing, the memory ordering sections of the
> Alpha SRM might help understanding.
>
> John

They might, but afaik the SRM was restricted distribution and is not
available to the general public, and its close relative the Alpha
Architecture Reference Manual is a commercial publication not
(legitimately?) freely downloadable?

Fortunately there is an alternative for this particular case: the
Alpha Architecture Handbook was/is legitimately freely downloadable.
Its sections related to "Write Memory Barrier" will be relevant and
hopefully helpful. Unfortunately I have no idea how to relate that to
IA64 usage, but maybe it will magically become clear?

Try http://www.cs.cmu.edu/afs/cs/academic/class/15213-f98/doc/alpha-ref.pdf
but there should be plenty of others.