MODULE; IMPORT Thread, ThreadF, IntList, IntListFuncs, Process, Fmt, IO; IMPORT ParseParams, Stdio; VAR debug: BOOLEAN := FALSE; REVEAL T = Public BRANDED "RdWrMutex.T" OBJECT count: INTEGER; cv: Thread.Condition; mu: Thread.Mutex; id: INTEGER := -1; readers: IntList.T := NIL; OVERRIDES init := Init; acquireRead := AcquireRead; acquireWrite := AcquireWrite; releaseRead := ReleaseRead; releaseWrite := ReleaseWrite; wait := Wait; END; PROCEDURE RdWrMutex RemoveReader (self: T) = BEGIN WITH num = IntList.Length(self.readers) DO IF IntListFuncs.DeleteD(self.readers, ThreadF.MyId()) = NIL THEN Process.Crash("RdWrMutex: releaseRead called by non-locker.\n" & "Releasing Reader with " & Fmt.Int(num) & " readers resulting in " & Fmt.Int(IntList.Length(self.readers)) & " readers.\n"); END; END; END RemoveReader; PROCEDUREGetReaders (self: T): IntList.T = BEGIN RETURN IntListFuncs.DeleteAllD(self.readers, ThreadF.MyId()); END GetReaders; PROCEDUREInit (self: T): T = BEGIN self.count := 0; self.cv := NEW(Thread.Condition); self.mu := NEW(Thread.Mutex); RETURN self; END Init; PROCEDUREAcquireRead (self: T) = BEGIN LOCK self.mu DO IF self.count < 0 THEN IF self.id # ThreadF.MyId() THEN (* If the lock is held by a writer other than ourself, wait for the write lock to be released. *) WHILE self.count < 0 DO Thread.Wait(self.mu, self.cv) END; (* Now it's ours, so mark it as acquired by another reader *) INC(self.count); ELSE (* Otherwise, it is held by ourself as a writer, so we don't change the count and continue on *) END; ELSE (* If the lock is free or held by readers, increment the count of readers. *) INC(self.count); END; (* add to the list of readers. *) self.readers := IntList.Cons(ThreadF.MyId(), self.readers); IF debug THEN IO.Put("RdWrMutex: AcquireRead succeeded for " & Fmt.Int(ThreadF.MyId()) & ", count=" & Fmt.Int(self.count) & "\n"); END; END; END AcquireRead; PROCEDUREAcquireWrite (self: T) = VAR myReaders: IntList.T := NIL; BEGIN LOCK self.mu DO IF self.count < 0 THEN IF self.id = ThreadF.MyId() THEN (* We already have the write lock, increment our lock count and return. *) DEC(self.count); IF debug THEN IO.Put("RdWrMutex: AcquireWrite recursively called by " & Fmt.Int(ThreadF.MyId()) & ", count=" & Fmt.Int(self.count) & "\n"); END; RETURN; END; ELSIF self.count > 0 THEN (* temporarily "release" our read locks. *) WITH num = IntList.Length(self.readers) DO myReaders := GetReaders(self); <* ASSERT IntList.Length(myReaders) + IntList.Length(self.readers) = num *> IF myReaders # NIL THEN DEC(self.count, IntList.Length(myReaders)); END; END; END; (* Someone else has the write lock or a read lock. Wait. *) WHILE self.count # 0 DO Thread.Wait(self.mu, self.cv) END; self.count := -1; self.id := ThreadF.MyId(); self.readers := myReaders; IF debug THEN IO.Put("RdWrMutex: AcquireWrite succeeded for " & Fmt.Int(ThreadF.MyId()) & ", count=" & Fmt.Int(self.count) & ", numreaders=" & Fmt.Int(IntList.Length(self.readers)) & "\n"); END; END; END AcquireWrite; PROCEDUREReleaseRead (self: T) = BEGIN LOCK self.mu DO (* First, remove our entry. *) RemoveReader(self); (* If the lock is held by readers, decrease the count. *) IF self.count > 0 THEN DEC(self.count); END; IF self.count = 0 THEN Thread.Broadcast(self.cv) END; IF debug THEN IO.Put("RdWrMutex: ReleaseRead succeeded for " & Fmt.Int(ThreadF.MyId()) & ", count=" & Fmt.Int(self.count) & "\n"); END; END; END ReleaseRead; PROCEDUREReleaseWrite (self: T) = BEGIN LOCK self.mu DO (* replace asserts by if statements for now *) IF (self.count >= 0) OR (self.id # ThreadF.MyId()) THEN Process.Crash("RdWrMutex: releaseWrite called by non-locker, " & "count=" & Fmt.Int(self.count) & " \n"); END; IF self.count = -1 THEN self.id := -1; self.count := IntList.Length(self.readers); Thread.Broadcast(self.cv); ELSE INC(self.count); END; IF debug THEN IO.Put("RdWrMutex: ReleaseWrite succeeded for " & Fmt.Int(ThreadF.MyId()) & ", count=" & Fmt.Int(self.count) & "\n"); END; END; END ReleaseWrite; PROCEDUREWait (self: T; mu: Thread.Mutex; cv: Thread.Condition) = VAR myReaders: IntList.T := NIL; writeLockCount: INTEGER := 0; myId: INTEGER := -1; BEGIN LOCK self.mu DO IF debug THEN IO.Put("RdWrMutex: Wait going to sleep for " & Fmt.Int(ThreadF.MyId()) & ", count=" & Fmt.Int(self.count) & "\n"); END; (* remember our state *) IF self.count < 0 THEN myId := self.id; myReaders := self.readers; writeLockCount := self.count; self.id := -1; self.count := 0; self.readers := NIL; ELSIF self.count > 0 THEN (* temporarily "release" our read locks. *) WITH num = IntList.Length(self.readers) DO myReaders := GetReaders(self); <* ASSERT IntList.Length(myReaders) + IntList.Length(self.readers) = num *> IF myReaders # NIL THEN DEC(self.count, IntList.Length(myReaders)); END; END; END; (* Wait *) IF self.count = 0 THEN Thread.Broadcast(self.cv) END; END; Thread.Wait(mu, cv); Thread.Release(mu); LOCK self.mu DO IF debug THEN IO.Put("RdWrMutex: Wait awoken, attempting to reacquire " & "lock for " & Fmt.Int(ThreadF.MyId()) & "\n"); END; IF writeLockCount < 0 THEN (* Now, attempt to reacquire the write lock! *) (* While someone else has the write lock or a read lock, wait. *) WHILE self.count # 0 DO Thread.Wait(self.mu, self.cv) END; (* Restore state *) self.count := writeLockCount; self.id := myId; self.readers := myReaders; ELSIF myReaders # NIL THEN (* Now, attempt to reacquire the read lock! *) (* While someone else has the write lock, wait. *) WHILE self.count < 0 DO Thread.Wait(self.mu, self.cv) END; (* add to the list of readers. *) self.readers := IntList.AppendD(self.readers, myReaders); INC(self.count, IntList.Length(myReaders)); END; IF debug THEN IO.Put("RdWrMutex: Wait has reacquired write lock for " & Fmt.Int(ThreadF.MyId()) & ", count=" & Fmt.Int(self.count) & ", numreaders=" & Fmt.Int(IntList.Length(self.readers)) & "\n"); END; END; Thread.Acquire(mu); END Wait; BEGIN debug := NEW(ParseParams.T).init(Stdio.stderr).keywordPresent("@EVdebugrwm"); END RdWrMutex.