Opened 8 years ago

Closed 8 years ago

#1058 closed defect (fixed)

Stress test failure with conditional-store

Reported by: jlawrence Owned by: gb
Priority: normal Milestone:
Component: Runtime (threads, GC) Version: trunk
Keywords: Cc:


(This assumes ccl::conditional-store should work even though it's not officially supported.)

The RUN function below eventually hangs on Linux and Darwin. On 32-bit it generally hangs sooner. The time until hanging decreases as the thread count increases. The number of threads reported by ccl:all-processes is relatively constant, and hanging still occurs with a 2-second sleep added to the loop.

Unfortunately I could not reproduce with a CAS-based stack, and CAS spin locks have been fixed (#1030), which leaves us with the more complex CAS queue. I hope the implementation below is straightforward enough. I'm confident that it is correct, so please double-check before blaming the queue. I've included SBCL support for reference (it runs on SBCL without a problem).

(defmacro conditional-store (&rest args)
  `(ccl::conditional-store ,@args))

(eval-when (:compile-toplevel :load-toplevel :execute)
  (import '(sb-thread:make-semaphore
  (defmacro conditional-store (place old new)
    (check-type old symbol)
    `(eq ,old (sb-ext:compare-and-swap ,place ,old ,new)))
  (defun process-run-function (name function)
    (sb-thread:make-thread function :name name)))

;;;; queue

;;; The following invariants hold except during lag across threads:
;;; (node-cdr (queue-tail queue)) == nil
;;; If the queue is empty, (queue-head queue) == (queue-tail queue).
;;; If the queue is non-empty, (node-car (node-cdr (queue-head queue)))
;;; is the next value to be dequeued and (node-car (queue-tail queue))
;;; is the most recently enqueued value.

(defstruct (node (:constructor make-node (car cdr)))
  (car (error "no car"))
  (cdr (error "no cdr")))

(defstruct (queue (:constructor %make-queue (head tail)))
  (head (error "no head"))
  (tail (error "no tail")))

(defconstant +dummy+ 'dummy)

(defun make-queue ()
  (let ((dummy (make-node +dummy+ nil)))
    (%make-queue dummy dummy)))

(defun enqueue (value queue)
  (let ((new (make-node value nil)))
    (loop (when (conditional-store (node-cdr (queue-tail queue)) nil new)
            (setf (queue-tail queue) new)
            (return value)))))

(defun dequeue (queue)
  (loop (let* ((head (queue-head queue))
               (next (node-cdr head)))
          (cond ((null next)
                 (return (values nil nil)))
                ((eq next +dummy+)) ; try again
                ((conditional-store (queue-head queue) head next)
                 (let ((result (node-car next)))
                   (setf (node-cdr head) +dummy+
                         (node-car head) +dummy+)
                   (return (values result t))))))))

;;;; test

(defun test (message-count thread-count)
  (let ((queue (make-queue)))
    (loop repeat thread-count
          do (process-run-function
              (lambda ()
                (loop repeat message-count
                      do (enqueue :hello queue))
                (enqueue :done queue))))
    (loop with done-count = 0
          until (and (eq :done (dequeue queue))
                     (= (incf done-count) thread-count)))))

(defun run ()
     (test 10000 64)
     (format t ".")

Change History (10)

comment:1 Changed 8 years ago by jlawrence

Of course the place to clear in DEQUEUE is (node-car next), not (node-car head), but this doesn't affect the functionality or the stress test.

comment:2 Changed 8 years ago by gb

  • Owner set to gb
  • Status changed from new to assigned

comment:3 Changed 8 years ago by gb

I've looked at this for the last couple of days and still don't know whether the problem is caused by a CCL bug or by a memory-ordering artifact.

Some notes:

I haven't been able to parse the note above about changes to DEQUEUE, so I've basically been running the original version of DEQUEUE without modifications.

The problem doesn't seem to occur in CCL on an ARM; the loop in RUN ran for several thousand iterations before I stopped it.

It ran substantially longer on an old single-core Celeron x86 box than it does on more modern systems, but it eventually hung in much the same way.

When I've seen it hang, the queue usually looks like:


e.g., (NODE-CDR (QUEUE-TAIL queue)) is non-NIL, and ENQUEUE can't make any progress in that case. The TAIL of the queue in this case is the original NODE that was used to initialize the queue.

The only code in your example that sets the NODE-CDR of any node to DUMMY is the code in DEQUEUE that you seem to be saying isn't quite correct in some way that isn't significant. That code (as written) affects the queue's head and it's the tail's node-cdr that's affected; the head and the tail are of course the same node when the queue is empty. (Note also that DEQUEUE is checking to see if NEXT - the NODE-CDR of the queue's HEAD - to see if it's EQ to +DUMMY+; DEQUEUE is the only thing that sets a NODE's NODE-CDR to +DUMMY+, and nothing seems to set any NODE-CDR to NIL.)

I don't know that this isn't a CCL bug, but I have difficulty understanding what bug would cause a symbol to be stored in the NODE-CDR of a NODE instead of in the NODE-CAR, or in the wrong NODE structure. (The kinds of things that I can imagine going wrong tend to be less predictable/consistent than

comment:4 Changed 8 years ago by jlawrence

No, I said (NODE-CAR NEXT) should be set instead of (NODE-CAR HEAD). Setting (NODE-CDR HEAD) to DUMMY is correct. That is necessary to distinguish the tail from a discarded node.

The correction doesn't make any difference here. Setting NODE-CAR is just there to remove the old reference to stored object, which doesn't matter for this test since we are storing :HELLO and :DONE.

comment:5 Changed 8 years ago by jlawrence

Here's a possible scenario which would produce the queue instance you gave. Suppose ENQUEUE and DEQUEUE are called concurrently. ENQUEUE makes partial progress while DEQUEUE fully completes. Then for some reason ENQUEUE doesn't complete.

For the sake of notation let's use conses instead of NODEs.

  1. start: head = tail = (dummy . nil)
  1. partial ENQUEUE: head = tail = (dummy . (:hello . nil)). Tail is

not updated yet.

  1. complete DEQUEUE: head = (dummy . nil), tail = (dummy . dummy)
  1. picking up where ENQUEUE left off, tail should be set to the

(:hello . nil) cons, which now looks like (dummy . nil). But ENQUEUE doesn't set tail.

comment:6 Changed 8 years ago by jlawrence

Placing a lock around SETF in ENQUEUE fixes the hang.

comment:7 Changed 8 years ago by gb

  • Resolution set to notabug
  • Status changed from assigned to closed

Replacing that SETF with a CONDITIONAL-STORE also seems to fix things. (Acquiring a lock also involves one or more "lock cmpxchg" instructions, and these instructions have the side-effect of imposing memory ordering.)

At the point where ENQUEUE does/did the SETF, only one thread should have had its CONDITIONAL-STORE succeed and should therefore be in a position to update the queue's tail. Using a lock or another conditional store isn't necessary to avoid contention, but it's entirely believable that using some form of memory barrier (to ensure that all threads/cores see the change in memory immediately) may very well be necessary to ensure that all threads have a consistent view of memory.

I tried making that new CONDITIONAL-STORE error if it returned NIL, and I made the other CONDITIONAL-STORE in ENQUEUE check to make sure that it didn't return NIL in a case where the store had succeeded. (The primitive that implements that case of CONDITIONAL-STORE can be interrupted if the GC suspends the thread and the code that handles that is complicated.) I didn't see either of those consistency checks fail; at this point, I don't see a CCL bug here.

comment:8 Changed 8 years ago by jlawrence

It seems to me that the single CAS in ENQUEUE provides necessary and sufficient ordering.

After a thread writes to the tail slot, another thread may read the old tail for some length of time. If so then that's fine -- CAS will fail for some number of iterations, and no harm is done.

Therefore a write to the tail slot is always preceded by a valid read. And a valid read must have been preceded by a completed write. Therefore writes to the tail slot are ordered as a consequence of CAS writes being ordered.

comment:9 Changed 8 years ago by jlawrence

  • Resolution notabug deleted
  • Status changed from closed to reopened

The claim that a memory barrier would solve this is not supported by evidence or theory. If there is a fix that adds a barrier and keeps the SETF then please show it. If you think CONDITIONAL-STORE is OK then the problem might lie in SETF.

comment:10 Changed 8 years ago by gb

  • Resolution set to fixed
  • Status changed from reopened to closed

(In [15746]) On x86{32,64}:

In write-barrier subprims that do an unconditional store (rplaca/rplacd, set_hash_key, gvset) do the store as the first instruction.

In pc_luser_xp: do nothing if suspended at the first instruction of these subprims. Otherwise, assume that the unconditional store has already occurred and don't emulate it. (Other values may have been stored in the same location since the thread was suspended.)

Fixes ticket:1058 in the trunk.

Note: See TracTickets for help on using tickets.