ViewerLocksImpl.mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.
Russ Atkinson (RRA) June 11, 1985 11:47:54 am PDT
Doug Wyatt, April 15, 1985 0:08:27 am PST
DIRECTORY
AMEvents USING [Debugged, Debugging],
Process USING [GetCurrent, MsecToTicks, Pause],
DebuggerSwap USING [CallDebugger],
ViewerClasses USING [Column, Lock, Viewer],
ViewerDebug USING [debugging],
ViewerLocks USING [],
ViewerGroupLocks USING [],
ViewerOps USING [BlinkDisplay, EnumerateChildren, EnumerateViewers, EnumProc],
ViewerPrivate;
ViewerLocksImpl: CEDAR MONITOR
IMPORTS AMEvents, Process, DebuggerSwap, ViewerOps
EXPORTS ViewerLocks, ViewerGroupLocks, ViewerPrivate
= BEGIN
Rationale
There are 3 tiers of locks: tree, column, and viewer.
Tree:
write lock gives exclusive access to the whole viewer tree
read lock prevents tree write locks
at least a read lock is required for column access
Column:
write lock gives exclusive access to the column
read lock prevents write locks on the column
at least a read lock is required for viewer access
Viewer:
write lock gives exclusive access to the viewer
read lock prevents write locks
(currently the readLocksExclusive flag causes read locks to be exclusive)
Write locks are owned by processes.
Multiple requests by a process for a lock it already owns will be granted.
Possession of a read lock without a write lock prevents acquiring a write lock.
Acquisition order:
Locks must be acquired first by tree, then by column, then by viewer.
Within a tier, locks are acquired by column number or viewer address.
Locks may be released in any order, but once a lock is released, no more should be acquired!
Types
CARD: TYPE = LONG CARDINAL;
Column: TYPE = ViewerClasses.Column;
Lock: TYPE = ViewerClasses.Lock;
Viewer: TYPE = ViewerClasses.Viewer;
Global variables
lockFree: CONDITION;
BROADCAST when any lock is released
readLocksExclusive: BOOL ← FALSE;
If TRUE, then read locks on viewers will be exclusive access to the locking process. This is a hack for debugging purposes right now.
treeOwner: PROCESS ← NIL;
The current process holding onto the whole tree
treeUsers: CARDINAL ← 0;
The current # of users of the tree (should be the sum of the column locks)
ColumnInfo: TYPE = RECORD [lock: Lock, wedgeCount: CARDINAL];
columns: ARRAY Column OF ColumnInfo ← ALL[[lock: [process: NIL, count: 0], wedgeCount: 0]];
Root viewer operations
CallRootUnderWriteLock: PUBLIC PROC [proc: PROC, viewer: Viewer] = {
Note: no longer different than CallUnderWriteLock
CallUnderWriteLock[proc, viewer];
};
CallRootAndLinksUnderWriteLock: PUBLIC PROC [proc: PROC, viewer: Viewer] = {
WHILE viewer # NIL AND NOT viewer.destroyed DO
root: Viewer ← GetRoot[viewer];
link1: Viewer ← IF root = NIL THEN NIL ELSE root.link;
link2: Viewer ← IF link1 = NIL THEN NIL ELSE link1.link;
quick: BOOL ← TRUE;
inner: PROC = {
First check to see if the viewer structure is the same as when we started
IF root # GetRoot[viewer] THEN RETURN;
IF root.link # link1 THEN RETURN;
IF quick AND (link1 # NIL AND link2 # root) THEN RETURN;
proc[];
win ← TRUE;
};
win: BOOL ← FALSE;
SELECT TRUE FROM
root = viewer AND link1 = NIL => CallUnderWriteLock[inner, viewer];
link1 = NIL OR link2 = root => CallUnderWriteLocks[inner, viewer, root, link1];
ENDCASE => {quick ← FALSE; CallUnderViewerTreeLock[inner]};
IF win THEN RETURN;
ENDLOOP;
};
Tree lock tier
LockViewerTree: PUBLIC ENTRY PROC = {
This entry acquires a write lock on the tree to get exclusive access to all columns and viewers.
ENABLE UNWIND => NULL;
process: PROCESS = CurrentProcess[];
DO
If we already own the lock then we exit quickly.
IF treeOwner = process THEN EXIT;
At each iteration, check for any column being wedged.
FOR c: Column IN Column DO
IF columns[c].wedgeCount # 0 THEN RETURN WITH ERROR Wedged[c];
ENDLOOP;
IF treeUsers = 0 THEN {
IF treeOwner # NIL THEN Error[];
EXIT;
};
WAIT lockFree;
ENDLOOP;
treeUsers ← treeUsers + 1;
treeOwner ← process;
};
ReleaseViewerTree: PUBLIC ENTRY PROC = {
This entry releases the write lock on the tree.
ENABLE UNWIND => NULL;
IF CurrentProcess[] # treeOwner THEN Error[];
IF treeUsers = 0 THEN Error[];
treeOwner ← NIL;
treeUsers ← treeUsers - 1;
BROADCAST lockFree;
};
CallUnderViewerTreeLock: PUBLIC PROC [proc: PROC] = {
LockViewerTree[];
proc[! UNWIND => ReleaseViewerTree[]];
ReleaseViewerTree[];
};
Column lock tier
Wedged: PUBLIC SAFE ERROR [wedged: Column] = CODE;
CallUnderColumnLock: PUBLIC PROC [proc: PROC, column: Column] = {
ENABLE {
AMEvents.Debugging => MarkColumnWedged[column];
AMEvents.Debugged => MarkColumnUnWedged[column]};
Wait: ENTRY PROC = {ENABLE UNWIND => NULL; WAIT lockFree};
AcquireColumnWriteLock[column ! Wedged => {Wait[]; RETRY}];
proc[! UNWIND => ReleaseColumnWriteLock[column]];
ReleaseColumnWriteLock[column];
};
CallUnderColumnLocks: PUBLIC PROC [proc: PROC, c0, c1: Column] = {
ENABLE {
AMEvents.Debugging => {MarkColumnWedged[c0]; MarkColumnWedged[c1]};
AMEvents.Debugged => {MarkColumnUnWedged[c0]; MarkColumnUnWedged[c1]};
};
Wait: ENTRY PROC = {ENABLE UNWIND => NULL; WAIT lockFree};
IF c0 > c1 THEN {c: Column ← c0; c0 ← c1; c1 ← c};
AcquireColumnWriteLock[c0 ! Wedged => {Wait[]; RETRY}];
AcquireColumnWriteLock[c1 ! Wedged => {Wait[]; RETRY}];
proc[! UNWIND => {ReleaseColumnWriteLock[c1]; ReleaseColumnWriteLock[c0]}];
ReleaseColumnWriteLock[c1];
ReleaseColumnWriteLock[c0];
};
AcquireColumnWriteLock: PUBLIC ENTRY PROC [column: Column] = {
ENABLE UNWIND => NULL;
IF ~ColumnWriteLockInternal[column] THEN RETURN WITH ERROR Wedged[column];
};
ColumnWriteLockInternal: INTERNAL PROC [column: Column] RETURNS [success: BOOL ← TRUE] = {
process: PROCESS ~ CurrentProcess[];
count: CARDINAL ← 0;
Get a read lock on the tree and a write lock on the column. Don't exit unless we can get both of them simultaneously.
DO
IF columns[column].wedgeCount>0 THEN
The column is wedged, so we can't get acquire the lock.
RETURN [FALSE];
count ← columns[column].lock.count;
IF count=0 OR columns[column].lock.process = process THEN
We can have the column write lock
IF treeOwner = process OR treeOwner = NIL THEN EXIT;
We can have the tree read lock, too.
WAIT lockFree;
When we can't get the tree read lock OR the column write lock we wait for something to happen and retry. So far we have not made any global changes.
ENDLOOP;
Finally bump the counts on the locks for the tree and column
treeUsers ← treeUsers + 1;
columns[column].lock ← [process, count+1];
};
ReleaseColumnWriteLock: PUBLIC ENTRY PROC [column: Column] = {
ENABLE UNWIND => NULL;
ReleaseColumnLockInternal[column];
};
ReleaseColumnLockInternal: INTERNAL PROC [column: Column] = {
First, test for error conditions and crash if they show up.
IF columns[column].lock.count = 0 THEN Error[];
IF treeUsers = 0 THEN Error[];
Now release the tree read lock that we got for this column
treeUsers ← treeUsers - 1;
IF treeUsers = 0 THEN {
treeOwner ← NIL;
BROADCAST lockFree;
};
Now release the column read|write lock
IF (columns[column].lock.count ← columns[column].lock.count-1) = 0 THEN {
columns[column].lock.process ← NIL;
BROADCAST lockFree;
};
};
ReadLockColumn: INTERNAL PROC [viewer: Viewer ← NIL, column: Column ← static] RETURNS [success: BOOL ← TRUE] = {
process: PROCESS ~ CurrentProcess[];
Get a read lock on the column and the tree. Don't exit unless we can get both of them simultaneously.
DO
IF viewer # NIL THEN column ← ViewerColumn[viewer];
IF columns[column].wedgeCount>0 THEN
The column is wedged, so we can't get acquire the lock.
RETURN [FALSE];
SELECT columns[column].lock.process FROM
NIL, process =>
We can have the read lock
IF treeOwner = process OR treeOwner = NIL THEN EXIT;
We can have the tree lock, too.
ENDCASE;
WAIT lockFree;
When we can't get the tree read lock OR the column read lock we wait for something to happen and retry. So far we have not made any global changes.
ENDLOOP;
Finally bump the counts on the locks for the tree and column
treeUsers ← treeUsers + 1;
columns[column].lock.count ← columns[column].lock.count+1;
};
ColumnWedged: PUBLIC ENTRY PROC [column: Column] RETURNS [wedged, write: BOOL] = TRUSTED {
ENABLE UNWIND => NULL;
RETURN [columns[column].wedgeCount # 0, columns[column].lock.process # NIL];
};
MarkViewerWedged: PUBLIC PROC [viewer: Viewer] = {
ENABLE UNWIND => NULL;
IF viewer # NIL THEN {
viewer.paintingWedged ← TRUE;
MarkColumnUnWedged[ViewerColumn[viewer]];
};
};
MarkViewerUnWedged: PUBLIC PROC [viewer: Viewer] = {
ENABLE UNWIND => NULL;
IF viewer # NIL THEN {
viewer.paintingWedged ← FALSE;
MarkColumnUnWedged[ViewerColumn[viewer]];
};
};
MarkColumnWedged: PUBLIC ENTRY PROC [column: Column] = {
ENABLE UNWIND => NULL;
IF ViewerDebug.debugging THEN RETURN;
IF columns[column].wedgeCount = 0 THEN THROUGH [0..2) DO
ViewerOps.BlinkDisplay[];
Process.Pause[Process.MsecToTicks[200]];
ENDLOOP;
columns[column].wedgeCount ← columns[column].wedgeCount+1;
};
MarkColumnUnWedged: PUBLIC ENTRY PROC [column: Column] = {
ENABLE UNWIND => NULL;
IF ViewerDebug.debugging THEN RETURN;
IF (columns[column].wedgeCount ← columns[column].wedgeCount-1) = 0
THEN BROADCAST lockFree;
};
Viewer lock tier
LockOrder: PUBLIC PROC [v0, v1: Viewer] RETURNS [BOOL] = {
SELECT TRUE FROM
v0 = NIL => GO TO swapped;
v1 = NIL => {};
ENDCASE => {
c0: Column ← IF v0.iconic THEN static ELSE v0.column;
c1: Column ← IF v1.iconic THEN static ELSE v1.column;
SELECT TRUE FROM
c0 > c1 => {};
c0 < c1 => GO TO swapped;
LOOPHOLE[v0, CARD] < LOOPHOLE[v1, CARD] => GO TO swapped;
ENDCASE;
};
RETURN [TRUE];
EXITS swapped => RETURN [FALSE];
};
CallUnderWriteLock: PUBLIC PROC [proc: PROC, viewer: Viewer] = {
IF viewer # NIL AND NOT viewer.destroyed THEN DO
root: Viewer ← GetRoot[viewer];
AcquireWriteLock[root];
IF root # GetRoot[viewer] THEN {ReleaseWriteLock[root]; LOOP};
proc[
!
UNWIND => ReleaseWriteLock[root];
AMEvents.Debugging => MarkViewerWedged[root];
AMEvents.Debugged => MarkViewerUnWedged[root];
];
ReleaseWriteLock[root];
RETURN;
ENDLOOP;
};
CallUnderWriteLocks: PUBLIC PROC [proc: PROC, v0, v1, v2: Viewer ← NIL] = {
DO
r0: Viewer ← GetRoot[v0];
r1: Viewer ← GetRoot[v1];
r2: Viewer ← GetRoot[v2];
AcquireWriteLocks[r0, r1, r2];
IF r0 = GetRoot[v0] AND r1 = GetRoot[v1] AND r2 = GetRoot[v2] THEN {
proc[
!
UNWIND => ReleaseWriteLocks[r0, r1, r2];
AMEvents.Debugging => {
IF r0 # NIL THEN MarkViewerWedged[r0];
IF r1 # NIL THEN MarkViewerWedged[r1];
IF r2 # NIL THEN MarkViewerWedged[r2]};
AMEvents.Debugged => {
IF r0 # NIL THEN MarkViewerUnWedged[r0];
IF r1 # NIL THEN MarkViewerUnWedged[r1];
IF r2 # NIL THEN MarkViewerUnWedged[r2]};
];
ReleaseWriteLocks[r0, r1, r2];
RETURN;
};
ReleaseWriteLocks[r0, r1, r2];
ENDLOOP;
};
CallUnderReadLock: PUBLIC PROC [proc: PROC, viewer: Viewer] = {
IF viewer # NIL AND NOT viewer.destroyed THEN DO
root: Viewer ← GetRoot[viewer];
AcquireReadLock[root];
proc[
!
UNWIND => ReleaseReadLock[root];
AMEvents.Debugging => MarkViewerWedged[root];
AMEvents.Debugged => MarkViewerUnWedged[root];
];
ReleaseReadLock[root];
ENDLOOP;
};
CallUnderReadLocks: PUBLIC PROC [proc: PROC, v0, v1, v2: Viewer ← NIL] = {
DO
r0: Viewer ← GetRoot[v0];
r1: Viewer ← GetRoot[v1];
r2: Viewer ← GetRoot[v2];
AcquireReadLocks[r0, r1, r2];
IF r0 = GetRoot[v0] AND r1 = GetRoot[v1] AND r2 = GetRoot[v2] THEN {
proc[
!
UNWIND => ReleaseReadLocks[r0, r1, r2];
AMEvents.Debugging => {
IF r0 # NIL THEN MarkViewerWedged[r0];
IF r1 # NIL THEN MarkViewerWedged[r1];
IF r2 # NIL THEN MarkViewerWedged[r2]};
AMEvents.Debugged => {
IF r0 # NIL THEN MarkViewerUnWedged[r0];
IF r1 # NIL THEN MarkViewerUnWedged[r1];
IF r2 # NIL THEN MarkViewerUnWedged[r2]};
];
ReleaseReadLocks[r0, r1, r2];
RETURN;
};
ReleaseReadLocks[r0, r1, r2];
ENDLOOP;
};
AcquireWriteLock: PUBLIC ENTRY PROC [viewer: Viewer] = {
ENABLE UNWIND => NULL;
IF NOT ReadLockColumn[viewer] THEN
RETURN WITH ERROR Wedged[ViewerColumn[viewer]];
WriteLockInternal[viewer];
};
WriteLockInternal: INTERNAL PROC [viewer: Viewer] = {
Locks the given viewer, assuming that the columns are already locked. No errors should occur in this routine.
IF viewer # NIL THEN {
process: PROCESS ~ CurrentProcess[];
UNTIL (viewer.lock.count=0 OR viewer.lock.process=process) DO WAIT lockFree; ENDLOOP;
viewer.lock ← [process, viewer.lock.count+1];
};
};
ReleaseWriteLock: PUBLIC ENTRY PROC [viewer: Viewer] = {
ENABLE UNWIND => NULL;
IF viewer # NIL THEN ReleaseLockInternal[viewer];
};
AcquireWriteLocks: PUBLIC ENTRY PROC [v0, v1, v2: Viewer ← NIL] = {
Viewers must be sorted so that they are locked from highest to lowest, by column and by address. We also need to lock the columns BEFORE locking the viewers themselves, since we can otherwise get deadlock for viewers in multiple columns.
ENABLE UNWIND => NULL;
c: Column;
{
[v0, v1, v2] ← LockColumnsForViewers[v0, v1, v2
! Wedged => {c ← wedged; GO TO wedgedError}
];
EXITS wedgedError => RETURN WITH ERROR Wedged[c];
};
IF v0 # NIL THEN WriteLockInternal[v0];
IF v1 # NIL THEN WriteLockInternal[v1];
IF v2 # NIL THEN WriteLockInternal[v2];
};
ReleaseWriteLocks: PUBLIC ENTRY PROC [v0, v1, v2: Viewer ← NIL] = {
no sort required
ENABLE UNWIND => NULL;
IF v0 # NIL THEN ReleaseLockInternal[v0];
IF v1 # NIL THEN ReleaseLockInternal[v1];
IF v2 # NIL THEN ReleaseLockInternal[v2];
};
AcquireReadLock: PUBLIC ENTRY PROC [viewer: Viewer] = {
ENABLE UNWIND => NULL;
IF NOT ReadLockColumn[viewer] THEN
RETURN WITH ERROR Wedged[ViewerColumn[viewer]];
ReadLockInternal[viewer];
};
ReadLockInternal: INTERNAL PROC [viewer: Viewer] = {
Acquires the read lock for the viewer, assuming that the column lock is already acquired
process: PROCESS = CurrentProcess[];
UNTIL (viewer.lock.process=NIL OR viewer.lock.process=process) DO WAIT lockFree; ENDLOOP;
IF readLocksExclusive THEN viewer.lock.process ← process;
RRA: note this test. It is a debugging aid to determine if it prevents painting bugs.
viewer.lock.count ← viewer.lock.count+1;
};
ReleaseReadLock: PUBLIC ENTRY PROC [viewer: Viewer] = {
ENABLE UNWIND => NULL;
IF viewer # NIL THEN ReleaseLockInternal[viewer];
};
AcquireReadLocks: PUBLIC ENTRY PROC [v0, v1, v2: Viewer ← NIL] = {
viewers must be sorted so that they are locked from highest to lowest. As with write locks, we need to acquire the columns first to prevent deadlocks with multiple columns
ENABLE UNWIND => NULL;
c: Column;
{
[v0, v1, v2] ← LockColumnsForViewers[v0, v1, v2
! Wedged => {c ← wedged; GO TO wedgedError}
];
EXITS wedgedError => RETURN WITH ERROR Wedged[c];
};
IF v0 # NIL THEN ReadLockInternal[v0];
IF v1 # NIL THEN ReadLockInternal[v1];
IF v2 # NIL THEN ReadLockInternal[v2];
};
ReleaseReadLocks: PUBLIC ENTRY PROC [v0, v1, v2: Viewer ← NIL] = {
no sort required
ENABLE UNWIND => NULL;
IF v0 # NIL THEN ReleaseLockInternal[v0];
IF v1 # NIL THEN ReleaseLockInternal[v1];
IF v2 # NIL THEN ReleaseLockInternal[v2];
};
ReleaseLockInternal: INTERNAL PROC [viewer: Viewer] = {
ReleaseColumnLockInternal[ViewerColumn[viewer]];
IF viewer.lock.count = 0 THEN Error[];
IF (viewer.lock.count ← viewer.lock.count-1) = 0 THEN {
viewer.lock.process ← NIL;
BROADCAST lockFree;
};
};
Utilities
Error: PROC = {
DebuggerSwap.CallDebugger["ViewerLocks bug"L];
};
GetRoot: ENTRY PROC [viewer: Viewer] RETURNS [root: Viewer] = {
root ← viewer;
IF root # NIL THEN DO
next: Viewer ← root.parent;
IF next = NIL THEN EXIT;
root ← next;
ENDLOOP;
};
SetReadExclusive: PROC [state: BOOL ← TRUE] = {
Safely change the state of readLocksExclusive.
LockViewerTree[];
readLocksExclusive ← state;
ReleaseViewerTree[];
};
ClearAllLocks: ENTRY PROC = {
This is a desperately unsafe operation!
ClearLock: ViewerOps.EnumProc = {
IF v.parent = NIL THEN ViewerOps.EnumerateChildren[v, ClearLock];
v.lock ← [NIL, 0];
};
FOR c: Column IN Column DO columns[c] ← [[NIL, 0], 0]; ENDLOOP;
ViewerOps.EnumerateViewers[ClearLock];
treeOwner ← NIL;
treeUsers ← 0;
BROADCAST lockFree;
};
LockColumnsForViewers: INTERNAL PROC [v0, v1, v2: Viewer] RETURNS [Viewer, Viewer, Viewer] = {
Given three viewers, first sort them by column and address order. Then try to acquire the column lock(s) for those viewers in that order. There are two ways that this will fail:
1. If any column in the viewers is wedged, then release all of the column locks acquired, and raise ERROR Wedged[column] for the wedged column.
2. If any viewer column changes before all of the locks are acquired, then release all of the acquired column locks and try again. Since column changes are rare, this should eventually succeed.
The viewers are returned in sorted order so that subsequent read or write locks can be acquired in the proper (non-deadlock) order. This relies on everyone acquiring locks in the same order.
DO
c0, c1, c2: Column ← static;
b0, b1, b2: BOOL ← FALSE;
FreeAllColumns: INTERNAL PROC = {
IF b0 THEN ReleaseColumnLockInternal[c0];
IF b1 THEN ReleaseColumnLockInternal[c1];
IF b2 THEN ReleaseColumnLockInternal[c2];
};
[v0, v1] ← SortViewers2[v0, v1];
[v1, v2] ← SortViewers2[v1, v2];
[v0, v1] ← SortViewers2[v0, v1];
Now the viewers are in column order (and address order). The column order should not change while we are waiting, or there will be trouble! For now, we check this to make sure that it stays the same, and loop if it changes.
IF v0 = NIL THEN EXIT;
b0 ← ReadLockColumn[column: c0 ← ViewerColumn[v0]];
IF ~b0 THEN {FreeAllColumns[]; ERROR Wedged[c0]};
IF c0 # ViewerColumn[v0] THEN {FreeAllColumns[]; LOOP};
IF v1 = NIL THEN EXIT;
b1 ← ReadLockColumn[column: c1 ← ViewerColumn[v1]];
IF ~b1 THEN {FreeAllColumns[]; ERROR Wedged[c1]};
IF c1 # ViewerColumn[v1] THEN {FreeAllColumns[]; LOOP};
IF v2 = NIL THEN EXIT;
b2 ← ReadLockColumn[column: c2 ← ViewerColumn[v2]];
IF ~b2 THEN {FreeAllColumns[]; ERROR Wedged[c2]};
IF c2 # ViewerColumn[v2] THEN {FreeAllColumns[]; LOOP};
EXIT;
ENDLOOP;
RETURN [v0, v1, v2];
};
SortViewers2: PROC [v0, v1: Viewer] RETURNS [Viewer, Viewer] = INLINE {
This is a helpful routine for LockColumnsForViewers. It is INLINE to save on procedure calls (is this necessary?), and should have the same sort order as LockOrder.
SELECT TRUE FROM
v0 = NIL => GO TO swapped;
v1 = NIL => {};
ENDCASE => {
c0: Column ← IF v0.iconic THEN static ELSE v0.column;
c1: Column ← IF v1.iconic THEN static ELSE v1.column;
SELECT TRUE FROM
c0 > c1 => {};
c0 < c1 => GO TO swapped;
LOOPHOLE[v0, CARD] < LOOPHOLE[v1, CARD] => GO TO swapped;
ENDCASE;
};
RETURN [v0, v1];
EXITS swapped => RETURN [v1, v0];
};
ViewerColumn: PROC [viewer: Viewer] RETURNS [column: Column] = INLINE {
RETURN [IF viewer.iconic THEN static ELSE viewer.column];
};
CurrentProcess: PROC RETURNS [PROCESS] = TRUSTED INLINE {
RETURN [LOOPHOLE[Process.GetCurrent[]]];
};
END.