condition-wait may signal deadline twice

[Tobias C. Rittweiler]

I think I found a subtle bug in CONDITION-WAIT and deadlines:

  Let's say the FUTEX-WAIT in CONDITION-WAIT's definition returns due to
  ETIMEOUT.

  After the return of FUTEX-WAIT, the mutex is reaquired.

  Notice, however, that GET-MUTEX may involve signaling due to
  exhaustion of the current deadline!

  Let's say that deadline is signaled there, and defered in the handler.

  We return from GET-MUTEX back into CONDITION-WAIT,

    get into the (1) clause of the CASE due to FUTEX-WAIT's previous
    ETIMEOUT,

    and signal the old deadline _again_!!!

[Tobias C. Rittweiler (tcr)]

Test case.

;;; This explanation refers to 1.0.26.5 <= SBCL version <= 2010-01-26.
;;;
;;; (As of 2010-01-26, only when using platforms with futexes,
;;; CONDITION-WAIT supported deadlines. The test case was written
;;; on Linux-x86-32.)
;;;
;;; Explanation of the bug:
;;;
;;; Be A the thread that first runs the deadline handler.
;;; Be B the other thread.
;;;
;;; At the place marked by [*], A is still (or perhaps rather
;;; "again") holding on the MUTEX, then going to sleep long enough
;;; for B to wake up (and also for triggering the deadline in B.)
;;;
;;; B wakes up from FUTEX-WAIT in CONDITION-WAIT due to ETIMEOUT,
;;; tries to reaquire the lock via GET-MUTEX, but the mutex is
;;; contended by A. So B's waiting on the MUTEX until its deadline
;;; is reached, and the deadline condition is signalled from within
;;; GET-MUTEX.
;;;
;;; B's deadline handler tries to defer that deadline way into the
;;; future. However, after continuing from the handler, GET-MUTEX
;;; successfully acquires the mutex now because A is gone.
;;; So GET-MUTEX returns, we're back in CONDITION-WAIT.
;;;
;;; As of 2010-01-26, CONDITION-WAIT _unconditionally_ calls
;;; SIGNAL-DEADLINE in case FUTEX-WAIT returned with ETIMEOUT (which
;;; it did here) -- so CONDITION-WAIT will signal a deadline again,
;;; even though B's handler just a moment ago defered the deadline
;;; way into the future.
;;;
;;; That's the bug.

(defun test (n)
  (let ((mutex (sb-thread:make-mutex))
        (waitq (sb-thread:make-waitqueue))
        (threads nil)
        (deadline-handler-run-twice? nil))
    (dotimes (i n)
      (let ((child
             (sb-thread:make-thread
              #'(lambda ()
                  (handler-bind
                      ((sb-sys:deadline-timeout
                        (let ((already? nil))
                          #'(lambda (c)
                              (when already?
                                (setq deadline-handler-run-twice? t))
                              (setq already? t)
                              (sleep 0.2) ; [*]
                              (sb-thread:condition-broadcast waitq)
                              (sb-sys:defer-deadline 10.0 c)))))
                    (sb-sys:with-deadline (:seconds 0.1)
                      (sb-thread:with-mutex (mutex)
                        (sb-thread:condition-wait waitq mutex))))))))
        (push child threads)))
    (mapc #'sb-thread:join-thread threads)
    (assert (not deadline-handler-run-twice?))))

;;; (test 2) should be enough

[Tobias C. Rittweiler (tcr)]

In 1.0.35.1.