Internal Memo
XEROX
To
From
CedarImplementors^.pa Russ Atkinson
PARC/CSL
Subject
Date
Viewers and Tioga locking June 10, 1985
Viewers and Tioga locking
Background
Viewers and Tioga provide a situation where multiple processes are accessing multiple interacting objects. In such a situation one is obliged to perform locking most carefully. We know that a safe locking order is obtained by following these rules:
1. No process reads or writes an object without locking it.
2. Each process acquires locks in a consistent order, so that whenever lock A and lock B are both acquired either A is always acquired before B, or B is always acquired before A.
3. Once a process releases a lock, it must not acquire more locks.
4. For operations that do not modify their objects, a read lock (non-exclusive) may be held.
5. For operations that modify their objects, a write lock (exclusive) must be held.
Unfortunately, the design of Viewers and Tioga did not include the design of the locking structure. Up through the Viewers and Tioga of 10 June 1985 it was possible to acquire the lock for a viewer and the document lock associated with that viewer in either order. This would have led to frequent deadlock except for the fact that the viewers locks were read locks, and allowed multiple access. This had the effect of allowing multiple painters into a viewer at once, which led to numerous painting bugs. By studious hacking most of the bugs were rendered infrequent and largely innocuous, although there was always a residual combination of deadlocks and race conditions.
The new rules
1. Given a viewer with an associated document, the viewer lock must be acquired before the document lock. This is handled correctly by TEditLocks.LockDocAndTdd, so most clients need not use any other locking for a document.
2. When painting a viewer, its write lock must be acquired. If the viewer is not a top-level viewer, a write lock for its root viewer must also be acquired. This is handled correctly by ViewerOps.PaintViewer, so most clients need not become involved with locking at this level.
The viewer read lock is not good for much besides preventing write locks.
3. Acquiring either a read lock or write lock for a viewer requires a read lock on the containing column. Adjusting viewers within a column requires a write lock. A process that acquires a write lock on a column should always succeed in acquiring the locks on any viewers within the column.
4. Acquiring either a read or write lock on a column requires a read lock on the whole viewer tree. A process that has a write lock on the whole viewer tree should always succeed in acquiring the locks of any viewers in the whole tree.
5. Modifying the structure of a split viewer requires write locks for all of its links. This is handled correctly by the new interface ViewerGroupLocks (CallRootAndLinksUnderWriteLock), and clients should not try anything fancy on their own.
6. If it becomes necessary to cause painting while holding a lock that precludes acquiring the viewer write lock, the painting should be forked (see the new ViewerForkers interface).
Bugs in the new rules
Because we did not have the time to completely redesign Viewers and Tioga, there are some residual bugs and performance problems.
1. Long-lasting operations (like Load and Save) more completely lock up the viewers they are using. This prevents clicking Save and then adjusting the column, although it does not prevent clicking Save and then doing something in the other column(s).
2. Split viewers are not always properly locked. For example, when a document is locked, only its root viewer is locked along with it. This is adequate except for operations that change the root of a document. Such operations must acquire write locks for all of the split viewers.
3. Interactions with the caret have not been completely fixed. Carets are disabled when painting starts, and are resumed when painting ends, but painting is not inhibited while carets are being painted! This allows little caret droppings to be left on the screen. It is not clear if this can be easily fixed within the current framework.
Remaining problems
Because we did not have the time to completely redesign Viewers and Tioga, there are some residual bugs and performance problems.
1. Paint operations that get an uncaught signal will wedge the painting for the viewer (and will prevent adjustments on the column). Ideally they would only prevent further paints for the viewer, but that has not been realized.
2. Refresh is not as good as it might be. Even the casual user will notice situations in which a viewer is painted too often. This is slightly annoying on a Dorado, but is more than slightly annoying on a smaller machine.
3. Scrolling is not quite right. Auto-scrolling will sometimes fail to keep up with column changes. Explicit scrolling (using the scroll-bar) will sometimes be ignored if the viewer is modified by another process (as is the case for typescripts).