Inter-Office Memorandum


To MBrown, Taft Date September 30, 1982

From Kolling Location Palo Alto

Subject Internal Functioning of Alpine's AccessControl Organization CSL
Filed on: <Alpine>Doc>AccessControlInternals.tioga DRAFT


This memo describes the non-obvious parts of the internal functioning of AccessControl and supersedes all previous memos on this subject.

When a public procedure in AccessControl is called, it expects the volume group to have already been locked in the appropriate mode by the caller. In addition, only one process per transaction at a time is expected to call AccessControl. The former is done so that opens on the owner files can be done inside monitors (they won't have to wait), as it seemed more natural to write the AccessControl code this way, and also to prevent a volume group from being unregistered out from underneath a process or similar thrilling things. The one process per transaction restriction is necessary because AccessControl depends on locking to avoid conflicts, and consequently is defenseless against more than one process per transaction.

There are two top level modules: AccessControlLightImpl and AccessControlHeavyImpl:
AccessControlHeavyImpl implements the infrequently used "heavy" operations, such as RegisterVolumeGroup, which tie up the entire volume group and owner file; these operations open the owner file in write mode and expect the volume group to have been locked in write mode.
AccessControlLightImpl implements the "light" operations, such as AddOwner and ChangeSpaceViaOwner, which generally deal with just one owner record; these operations open the owner file in intend write and expect the volume group to have been locked in read.

Support for AccessControlHeavyImpl and AccessControlLightImpl is provided by AccessControlVolatileImpl, AccessControlFileImpl, AccessControlCacheImpl, and AccessControlUtilityImpl:
AccessControlUtilityImpl: trivial utilities.
AccessControlCacheImpl: verifies via Grapevine that a client name exists in an access list, and keeps some info about this in a cache.
AccessControlFileImpl: given an open file id and owner name, read the record. given an open file id and a record number, read the record. read header record, do similar writes, etc. Generally, knows about the nitty gritty file structure, and its callers don't.
AccessControlVolatileImpl: maintains and retrieves data from the volatile structure. For each volume group, the volatile structure keeps track of the owner file id, quota information, enumeration cache, and pending owner allocation changes on a transaction basis.

More details about how locks are used:
The object locked below the level of the volume group/owner file is the owner record (actually the page) in the owner file. The owner record may be an empty record, in the case of AddOwner.

The allocation routines in AccessControlLightImpl lock the record in read mode, make an allocation change entry in the volatile structure, and then unlock the record. This allows multiple transactions to use the same owner's space in parallel. At PhaseOne, the transaction gets the record in write mode and updates it to reflect only this transaction's changes. Thus serialization takes place at PhaseOne. If the transaction subsequently aborts, the record will, of course, disappear.

Some other routines in AccessControlLightImpl, such as AddOwner and RemoveOwner, lock the record in write mode, thus locking out other transactions with the exception of any allocators who may have gotten in ahead of them. These "write" routines therefore have to explicitly check for previous allocators and do something couth. For example, if RemoveOwner finds a previous allocator it knows that it cannot yet do the remove; this is because the spaceInUse for that owner on the volume group must be zero before the remove can legally be done, and the previous allocator has some of that space "tied up".

Some other routines in AccessControlLightImpl, such as PermissionToCreateFilesForThisOwner, that want primarily to read the access lists in the owner record, lock the record in read mode and then unlock it, thus allowing interactions between transactions. This is because we don't much care about short time frames and transactions when dealing with changes in permissions, since we are caching a lot of permission information anyway via AccessControlCacheImpl.

Since the AccessControlHeavyImpl procedures have the owner file locked in write mode, there can be no previous allocators for other transactions for that volume group, since those allocators' read locks on the volume group would have blocked the heavy's write lock, and so all the AccessControlHeavyImpl procedures have to worry about is dealing with previous allocations by their own transaction.

A bird's eye view of some representative or particularly interesting routines in AccessControlLightImpl, omitting uninteresting details, such as most permission checking:
AddOwner:
read the header record in write mode.
read the (empty) owner data record in write mode.
check via the header record that enough room is left on this vol group to get the new space required. (Done after read of owner data record due to sharing code with ChangeOwnerSpaceQuota.)
fill in the owner record.
update info in the header record.
write both records.
note that no entry needs to be made in the volatile structure at this point, as these new file records will disappear if this transaction aborts, and only this transaction can read them if it later decides to allocate. We are guaranteed that no entry for this owner can already be in the volatile structure, since we got the empty record write locked.
RemoveOwner:
read the header record in write mode.
read the owner data record in write mode.
call ACVolatile: unless our transaction is the only one for this owner record and the file record info + volatile info about allocation sums to zero, send back the error message "space in use". (It's a thorn that we can't wait for the other transactions to finish.)
remove this owner's info from the volatile structure.
mark the owner record empty.
update info in the header record.
write both records.
ChangeOwnerSpaceQuota:
read the header record in write mode.
read the owner data record in write mode.
check via the header record and owner data record that enough room is left on this vol group to get any new space required.
call ACVolatile: if there is an entry for this owner on this vol group and other transactions are there, error return (thorn). Otherwise, if there is an entry for this owner on this vol group, change the quota info. (The current space in use may be > the new quota, but at least it prevents any more allocation in that case.) Nothing to do to the volatile structure if no entry there.
change the owner record.
update info in the header record.
write both records.
ChangeOwnerAccessLists:
read the owner data record in write mode.
check via the owner data record that it's okay to make change.
change the owner record.
write the owner record.
note: we don't care very much about consistency of permissions within a transaction.
EnumerateThisOwner:
read the owner data record in read mode.
check via the owner data record that it's okay to report this info.
report the info (include this transaction's state from the volatile structure).
ChangeSpaceViaOwner:
read the owner data record in read mode.
call ACVolatile to decide on the basis of the file record and the volatile record if we have room for this allocate; if yes, update the volatile record (we may create it).
release this read lock on the record.
note: the client doesn't "get credit" for deallocations until the transaction commits.
PermissionToCreateFilesForThisOwner:
read the owner data record in read mode.
check the access list in the record to see if we have permission.
release this read lock on the record.
PhaseOneSpaceAndOwnerChanges:
for each pending allocation change, update the appropriate owner record in write mode.
PhaseTwoOrAbortSpaceAndOwnerChanges:
for PhaseTwo: for each pending allocation change for this transaction, update the basic volatile structure to reflect that these changes are now final. If there are heavy operations pending, reflect them as final in the structure.
for abort: for each pending allocation change for this transaction, remove these information from the structure. If there are heavy operations pending, remove them from the structure.