headers/private/shared/RWLocker.h

   1 /*
   2  * Copyright 2006, Haiku.
   3  * Distributed under the terms of the MIT License.
   4  *
   5  * Authors:
   6  *              IngoWeinhold <bonefish@cs.tu-berlin.de>
   7  */
   8
   9 // This class provides a reader/writer locking mechanism:
  10 // * A writer needs an exclusive lock.
  11 // * For a reader a non-exclusive lock to be shared with other readers is
  12 //   sufficient.
  13 // * The ownership of a lock is bound to the thread that requested the lock;
  14 //   the same thread has to call Unlock() later.
  15 // * Nested locking is supported: a number of XXXLock() calls needs to be
  16 //   bracketed by the same number of XXXUnlock() calls.
  17 // * The lock acquiration strategy is fair: a lock applicant needs to wait
  18 //   only for those threads that already own a lock or requested one before
  19 //   the current thread. No one can overtake. E.g. if a thread owns a read
  20 //   lock, another one is waiting for a write lock, then a third one
  21 //   requesting a read lock has to wait until the write locker is done.
  22 //   This does not hold for threads that already own a lock (nested locking).
  23 //   A read lock owner is immediately granted another read lock and a write
  24 //   lock owner another write or a read lock.
  25 // * A write lock owner is allowed to request a read lock and a read lock
  26 //   owner a write lock. While the first case is not problematic, the
  27 //   second one needs some further explanation: A read lock owner requesting
  28 //   a write lock temporarily looses its read lock(s) until the write lock
  29 //   is granted. Otherwise two read lock owning threads trying to get
  30 //   write locks at the same time would dead lock each other. The only
  31 //   problem with this solution is, that the write lock acquiration must
  32 //   not fail, because in that case the thread could not be given back
  33 //   its read lock(s), since another thread may have been given a write lock
  34 //   in the mean time. Fortunately locking can fail only either, if the
  35 //   locker has been deleted, or, if a timeout occured. Therefore
  36 //   WriteLockWithTimeout() immediatlely returns with a B_WOULD_BLOCK error
  37 //   code, if the caller already owns a read lock (but no write lock) and
  38 //   another thread already owns or has requested a read or write lock.
  39 // * Calls to read and write locking methods may interleave arbitrarily,
  40 //   e.g.: ReadLock(); WriteLock(); ReadUnlock(); WriteUnlock();
  41 //
  42 // Important note: Read/WriteLock() can fail only, if the locker has been
  43 // deleted. However, it is NOT save to invoke any method on a deleted
  44 // locker object.
  45 //
  46 // Implementation details:
  47 // A locker needs three semaphores (a BLocker and two semaphores): one
  48 // to protect the lockers data, one as a reader/writer mutex (to be
  49 // acquired by each writer and the first reader) and one for queueing
  50 // waiting readers and writers. The simplified locking/unlocking
  51 // algorithm is the following:
  52 //
  53 //              writer                          reader
  54 //      queue.acquire()         queue.acquire()
  55 //      mutex.acquire()         if (first reader) mutex.acquire()
  56 //      queue.release()         queue.release()
  57 //               ...                             ...
  58 //      mutex.release()         if (last reader) mutex.release()
  59 //
  60 // One thread at maximum waits at the mutex, the others at the queueing
  61 // semaphore. Unfortunately features as nested locking and timeouts make
  62 // things more difficult. Therefore readers as well as writers need to check
  63 // whether they already own a lock before acquiring the queueing semaphore.
  64 // The data for the readers are stored in a list of ReadLockInfo structures;
  65 // the writer data are stored in some special fields. /fReaderCount/ and
  66 // /fWriterCount/ contain the total count of unbalanced Read/WriteLock()
  67 // calls, /fWriterReaderCount/ and /fWriterWriterCount/ only from those of
  68 // the current write lock owner (/fWriter/). To be a bit more precise:
  69 // /fWriterReaderCount/ is not contained in /fReaderCount/, but
  70 // /fWriterWriterCount/ is contained in /fWriterCount/. Therefore
  71 // /fReaderCount/ can be considered to be the count of true reader's read
  72 // locks.
  73
  74 #ifndef RW_LOCKER_H
  75 #define RW_LOCKER_H
  76
  77 #include <List.h>
  78 #include <Locker.h>
  79
  80 #include "AutoLocker.h"
  81
  82 class RWLocker {
  83  public:
  84                                                                 RWLocker();
  85                                                                 RWLocker(const char* name);
  86         virtual                                         ~RWLocker();
  87
  88                         bool                            ReadLock();
  89                         status_t                        ReadLockWithTimeout(bigtime_t timeout);
  90                         void                            ReadUnlock();
  91                         bool                            IsReadLocked() const;
  92
  93                         bool                            WriteLock();
  94                         status_t                        WriteLockWithTimeout(bigtime_t timeout);
  95                         void                            WriteUnlock();
  96                         bool                            IsWriteLocked() const;
  97
  98  private:
  99         struct  ReadLockInfo;
 100         struct  Benaphore {
 101                         sem_id  semaphore;
 102                         int32   counter;
 103         };
 104
 105  private:
 106                         void                            _Init(const char* name);
 107                         status_t                        _ReadLock(bigtime_t timeout);
 108                         status_t                        _WriteLock(bigtime_t timeout);
 109
 110                         int32                           _AddReadLockInfo(ReadLockInfo* info);
 111                         int32                           _NewReadLockInfo(thread_id thread,
 112                                                                                                  int32 count = 1);
 113                         void                            _DeleteReadLockInfo(int32 index);
 114                         ReadLockInfo*           _ReadLockInfoAt(int32 index) const;
 115                         int32                           _IndexOf(thread_id thread) const;
 116
 117         static  status_t                        _AcquireBenaphore(Benaphore& benaphore,
 118                                                                                                   bigtime_t timeout);
 119         static  void                            _ReleaseBenaphore(Benaphore& benaphore);
 120
 121  private:
 122         mutable BLocker                         fLock;                          // data lock
 123                         Benaphore                       fMutex;                         // critical code mutex
 124                         Benaphore                       fQueue;                         // queueing semaphore
 125                         int32                           fReaderCount;           // total count...
 126                         int32                           fWriterCount;           // total count...
 127                         BList                           fReadLockInfos;
 128                         thread_id                       fWriter;                        // current write lock owner
 129                         int32                           fWriterWriterCount;     // write lock owner count
 130                         int32                           fWriterReaderCount;     // writer read lock owner
 131                                                                                                         // count
 132 };
 133
 134 typedef AutoLocker<RWLocker, AutoLockerReadLocking<RWLocker> > AutoReadLocker;
 135 typedef AutoLocker<RWLocker, AutoLockerWriteLocking<RWLocker> > AutoWriteLocker;
 136
 137 #endif  // RW_LOCKER_H