Add Reader/Writer locks

[sionescu]

[sionescu]

Some pointers:

• https://eli.thegreenplace.net/2019/implementing-reader-writer-locks/
• https://stackoverflow.com/questions/12033188/how-would-you-implement-your-own-reader-writer-lock-in-c11
• https://www.arangodb.com/2018/05/an-implementation-of-phase-fair-reader-writer-locks/

[anon00000000]

I've made https://git.sr.ht/~q3cpma/cl-rwlock but it uses atomics to get portable struct slot atomic access (which doesn't seem replacable by bordeaux's atomic-integer thing) and needs a bit more testing/effort.

[gendl]

Here's what I came up with in Gendl because i'm a lot better at writing in Gendl than in raw CLOS. I think this could be translated directly into CLOS (ask me if you care to try and anything is unclear -- basically the define-object would map to a defclass and the :functions correspond to defmethods which specialize on the 'rwlock type). And I threw the operators into gdl package for quick convenience but of course the package should be bt2 if something like this would be added to bordeaux-threads.

The below implementation depends only on bt2's locks and condition variables.

Note this implementation does not try to do anything with "fairness" or "writer preference" as mentioned in some of the links above. Specifically, in an application where there may be constant unrelenting overlapping readers, it's possible that a writer would never get a chance to wake up and run. I think "fairness" (for some definition of same) can be added by extending the while condition for the read-lock function.

;;
;; Public Domain
;;

(in-package :gdl)

(defmacro while (condition &body body)
  `(do ()
       ((not ,condition))
     ,@body))

(define-object rwlock ()

  :input-slots
  ((name "anonymous read/write lock"))
  
  :computed-slots
  ((num-readers 0 :settable)
   (num-writers 0 :settable)
   (rw-mutex (bt2:make-lock))
   (waiting-readers (bt2:make-condition-variable))
   (waiting-writers (bt2:make-condition-variable)))

  :functions
  ((read-lock
    ()
    (bt2:with-lock-held ((the rw-mutex))
      (while (plusp (the num-writers))
        (bt2:condition-wait (the waiting-readers) (the rw-mutex)))
      (the (set-slot! :num-readers (1+ (the num-readers))))))

   (read-unlock
    ()
    (bt2:with-lock-held ((the rw-mutex))
      (the (set-slot! :num-readers (1- (the num-readers))))
      (when (zerop (the num-readers))
        (bt2:condition-notify (the waiting-writers)))))

   (write-lock
    ()
    (bt2:with-lock-held ((the rw-mutex))
      (while (or (plusp (the num-readers))
                 (plusp (the num-writers)))
        (bt2:condition-wait (the waiting-writers) (the rw-mutex)))
      (the (set-slot! :num-writers (1+ (the num-writers))))))

   (write-unlock
       ()
       (bt2:with-lock-held ((the rw-mutex))
         (the (set-slot! :num-writers (1- (the num-writers))))
         (bt2:condition-notify (the waiting-writers))
         (bt2:condition-broadcast (the waiting-readers))))))

(defun make-rwlock (&key (name "anonymous read/write lock"))
  (make-object 'rwlock :name name))

(defmacro with-read-lock-held ((lock) &body body)
  `(progn
     (the-object ,lock read-lock)
     (unwind-protect (progn ,@body)
       (the-object ,lock read-unlock))))

(defmacro with-write-lock-held ((lock) &body body)
  `(progn
     (the-object ,lock write-lock)
     (unwind-protect (progn ,@body)
       (the-object ,lock write-unlock))))
  
(eval-when (:compile-toplevel :load-toplevel :execute)
  (export '(make-rwlock with-read-lock-held with-write-lock-held) :gdl))

(defmethod print-object ((self rwlock) stream)
  (print-unreadable-object (self stream :type t)
    (format stream "~a readers: ~a writers: ~a"
            (the name) (the num-readers) (the num-writers))))
  

[Lovesan]

I have one in my bike library https://github.com/Lovesan/bike/blob/master/src/rwlock.lisp

It is implemented using bt APIv2 and uses lock and condition variables.

It is reentrant (i.e. allows for recursive read and write acquire/release), and it allows for upgrading from read lock to write lock(and for downgrading back on exit from write lock).

It is partially based on .NET ReaderWriterLockSlim implementation, although I have revisited its API (i.e. no separate Enter/ExitUpgradableReadLock and conditional support for recursion(recursion is always supported)).

One of the possible downsides is that it is interrupt-unsafe(like the aforementioned .NET implementation, however).

It also has read preference(because of that being important for my library).

I started with a simple(and incorrect) implementation and gradually reworked it into its current state. It should be pretty usable now.

Feel free to copy/modify/whatever.

Although I regularly test it using my library (the most important parts of which depend on it), it does need some unit tests. I caught race conditions and deadlocks in the past. It is quite hard to write proper unit tests for such things as basic synchronization primitives, though.

[gendl]

@Lovesan Thank you for posting. What are the practical ramifications of "interrupt-unsafe" ? Are the core bt2 locks and cvs interrupt-safe to begin with?

[Lovesan]

@gendl

What are the practical ramifications of "interrupt-unsafe" ?

What I mean by interrupt safety is, basically, lock state safety in a situation like this:

1. Thread A enters one of the begin/end functions.
2. Thread B executes bt2:interrupt-thread against thread A with a function, which causes stack unwinding and/or thread abort(say, by means of bt2:error-in-thread).

There can be other cases of similar situations, which would involve not the bt2:interrupt-thread function, but say POSIX signals, SEH/VEH exception during memory allocation and/or GC, and the like.

In the case of my lock implementation, should such an interrupt occur while the thread is executing one of the begin/end operations(excluding the actual waiting on the condvar), it may leave the lock in an incorrect state(say, internal counters would contain wrong values), which would lead to deadlocks and data corruption.

Are the core bt2 locks and cvs interrupt-safe to begin with?

This heavily depends on the CL implementation. On SBCL, for example, bt2:with-lock-held is safe against maskable* interrupts, while bt2:acquire-lock(which calls sb-thread:grab-mutex internally) is not. Condition variables are interrupt-safe(again, against maskable interrupts) on SBCL, but I'm not sure about other CL implementations.

* Non-maskable interrupts include, say, SIGKILL on Unix-like systems, or TerminateThread on Windows.

[ILoveGoulash]

Losing the speed advantage of only having atomics in the read path (like Go) is sad, but being upgradable is extra nice!