Re: [MIT-Scheme-devel] Symmetric MultiProcessing

[Taylor R Campbell]

   Date: Wed, 19 Aug 2015 17:36:38 -0700
   From: Matt Birkholz <address@hidden>

   > From: Taylor R Campbell <address@hidden>
   > Date: Tue, 18 Aug 2015 22:39:22 +0000
   > 
   > [...] or prove that the memory barriers are not necessary for other
   > reasons.

   I thought we were all cool with assuming word-sized memory coherency.
   Doesn't the x86-64 architecture guarantee that a word like constant-
   space-queue will be written atomically?

This is not about atomicity of single-word writes.  This is about
ordering of multiple writes.

When CPU 0 does

(set! constant-space-queue (cons item constant-space-queue)),

it has to write to (at least) three locations in memory: store item at
Free[0], store the value of constant-space-queue at Free[1], and then
store Free at constant-space-queue.

When CPU 1 does

(if (and (not (eq? '() constant-space-queue))
         (not (object-constant? constant-space-queue)))
    ...read (car constant-space-queue) and use it...)

it may read the car of constant-space-queue as it was before CPU 0
wrote something to that location (i.e., before CPU 0 stored item at
Free[0]), if CPU 1 had that location cached -- even though CPU 1 meant
to write to constant-space-queue only after writing to Free[0].

The safe way to do this is:

(let ((p (cons item constant-space-queue)))
  (membar-write)
  (set! constant-space-queue p))

(let ((queue constant-space-queue))
  (membar-read)
  (if (and (not (eq? '() queue))
           (not (object-constant? queue)))
      ...read (car queue) and use it...))

Now, in this case, particular on x86 and most current CPUs, the bad
situation is guaranteed not to occur.  But not all CPUs guarantee this
-- in particular, it may happen on a multiprocessor Alpha >=21264.

So, e.g., Linux has separate read barriers (for ordering `(if (fetch
p) (process (fetch q)))') and dependent-read barriers (for ordering
`(let ((q (fetch p))) (process (fetch q)))'), the latter of which are
no-ops on most CPUs.

A little more broadly, my point is that if you're going to skip a
lock, then the burden is on you to prove that it's safe, either by
inserting appropriate memory barriers or showing a convincing argument
that they're not necessary.

   > I'm also a little puzzled about the queue scheme.  It seems like now
   > we waste constant space for all the pairs that were used only for the
   > purpose of queueing objects to be purified.

   Yes, you puzzled that one out.  I traded a few pairs for a straight-
   forward implementation.  You would prefer that the queue not be
   purified during a GC interrupt?  Only by explicit application of
   flush-purification-queue!?  I'm cool with that.

As long as that's an intentional change that has only trivial adverse
consequences, that's OK.  But I wonder how much space it takes up on,
e.g., i386.