[_CD6_]<alpine>Doc>EarlyDesign>AccessControlDesign7.bravo!1

Heading:

Alpine access control design, version 7

Page Numbers: Yes X: 527 Y: 10.5"

DRAFT - DRAFT - DRAFT - DRAFT

ToAlpine designersDateSeptember 11, 1981

FromKaren KollingLocationPARC/CSL

SubjectAlpine access control design, version 7File [Ivy]<Alpine>Doc>AccessControlDesign7.bravo

XEROX

Attributes:informal, technical, Alpine, filing, access control, protection

Abstract:This memo proposes the scope of and interface to Alpine’s access control module, and contains notes on its implementation.

Overview

---------------

The AccessControl module is a component of FileStore’s implementation. It has two functions: (1) it provides disk space control and accounting, and (2) it controls access to individual files. It uses the Grapevine registration servers to implement protection.

This memo is based on discussions among Mark Brown, Ed Taft, and myself. Because we expect a universal file system and database managers with their own distributed protection facilities for files to exist in the future, we have decided to implement rudimentary file protection facilities which provide a reasonable level of service based on data structures local to the FileStore, while hopefully making it relatively painless to use a better mechanism in the future. In contrast, the space control facilities are viewed as being a permanent part of the file store implementation. Therefore, we will try to keep a division between these two different facilities in our implementation.

The remainder of this memo is organized as follows:

Some Comments
What AccessControl expects from FileProperties

What AccessControl expects from FileStore

What AccessControl expects from Locks

Interface to AccessControl

Implementation notes

Some Comments

---------------------------

1. An owner of space on the FileStore VolumeGroup is represented by an RName, which is either a Grapevine individual (ex: Taft.PA), Grapevine group (ex: UFS.PA), or a name with no Grapevine validity (ex: CedarDocs). We supply no defaults for registries.

2. There is a list (RName group) of privileged clients, hereafter called AlpineWheels, who can do things like register owners, etc. We expect this list to be potentially different for each FileStore.

3. In this memo, an "access list" should be taken to mean fields indicating owner, world, and some RNames which are Grapevine individuals or groups. An AlpineWheel has all possible permissions (upon its explicit request), and so AlpineWheels are not noted further in our access lists.

4. Disk space control involves a data structure containing owner-based items. These include the disk quota, disk usage, and these access lists:

who can create files with this ownerName.

who can read and set these owner access lists.

The defaults for these access lists and the minimum below which each cannot be reduced are:

default minimum

createownerowner

read/setownerowner

The defaults are used only on owner creation, not on change owner. We can allow 2 fixed-length RNames for create and 2 for read/set and still fit one owner record into one disk page with some space left for unforeseen requirements. We don’t presently plan to allow "world" to be set for any owner fields, but the field will be there at least internally.

5. File access involves a data structure containing file-based items. These include these access lists:

who can read the file.

who can modify the file (including extend, truncate, and delete).

The defaults for these access lists and the minimum below which each cannot be reduced are:

defaultminimum

readworldowner

modifyowner,ownercreatelistatthetimethisfilewascreatednull

We expect these access lists to be true "file properties", and to be kept in the file’s leader page and be managed by the FileProperties module. The defaults apply only on file creation, not on change file properties. We expect to store fixed-length RNames. We have considered the idea of storing variable length RNames or small indices or something of the sort instead, but have discarded it, as we do not wish to implement any more complicated a facility than necessary considering that it will become vestigial in the future. Because of space constraints, we will limit these access lists to the following number of RNames each: read: 2, modify: 2. These access lists control access to the file itself and to all of its file properties with the following exception: we will always allow the owner or any current member of the owner create list access to these access lists themselves; this rather awkward method is due to space constraints on storing RNames.

6. The minimums for access lists for both owners and files are enforced by oring them in rather than complaining to the user.

7. We encourage clients to allocate space in a non-piecemeal fashion.

8. We should have a little utility program which adds, changes, deletes, and enumerates owner entries. This owner control utility should be callable with some command list to make initialization of new FileStores easy. It uses normal FileStore-supplied procedures and does not require that the system be stand-alone or anything of the sort. It will type out the entire owner database upon request.

9. We also have a reorganizer (not exactly the right name, but I don’t want to call it a scavenger.....) for the owner data base which similarly does not require that the system be stand-alone. This reorganizer will adjust the length of the database file to something appropriate (caller-supplied subject to constraints, or what it decides itself), remove "deleted entries", and get entries "close" to their hash slots. It does not attempt to handle bad disk pages, garbaged pages, etc.

10. The interface which AccessControl presents is expected to be called by FileStore. It is not expected that clients will call AccessControl directly. AccessControl will call FileProperties, Locks, and FileStore.

11. The owner data base file will be entered in the root directory.

What AccessControl expects from FileProperties

--------------------------------------------------------------------------

FileProperties simply reads and writes the file properties which are access lists. It knows nothing about defaults, minimums, significance of internal fields, etc. It uses calls on FileStore.ReadPage, etc., so the locking, looking in the log map, etc. are handled automatically by FileStore.

AccessControl, when it is checking file permissions, reads the access lists via calls on FileProperties.

What AccessControl expects from FileStore

-------------------------------------------------------------------

It is expected that the client’s first call on FileStore will be some form of authentication request (Login?), which FileStore will do. All FileStore-exported procedures other than "Login" will reject calls from unauthenticated clients. The AccessControl module is therefore supposedly called only for clients who are valid FileStore users (and therefore valid Grapevine individuals) or by FileStore for internal purposes.

FileStore procedures:AccessControl procedures called:

----------------------------------------------------------------------------

CreateFile(WithID)CheckAccessOwnerCreateThenAllocate

ApplyDefaultsAndMinimumsForFileAccessLists

ChangeSpaceViaOwner (for leader page, etc.)

OpenFileCheckAccessFile (appropriate mode)

SetSizeChangeSpaceViaOpenFileID

DeleteFileChangeSpaceViaOpenFileID

GetPropertiesCheckExtraAccessFileAccessList

ExpandFileAccessList

SetPropertiesCheckExtraAccessFileAccessList

ApplyMinimumsToFileAccessLists

FileStore is assumed to cache the permissions received during CreateFile(WithID) or OpenFile in its open file table, so that subsequent FileStore procedures that read (WritePage, etc.) and write (SetSize, DeleteFile, etc.) check this cached permission rather than calling CheckAccessFile again. The one exception to this is Set/GetProperties for the file access lists may have to call CheckExtraAccessFileAccessList for the extra access we allow (see above).

FileStore exports to the client procedures which are thin films over ReportAccessControlStatistics, AddOwner, ChangeOwnerSpaceQuota, ChangeOwnerAccessLists, RemoveOwner, EnumerateThisOwner, EnumerateAllOwners, EnumerateOwnerDatabase, ReorganizeAccessControlDataBaseFile and AssertAlpineWheel.

AccessControl expects to be able to call FileStore routines which register procedures to be called at Phase1 (PhaseOneSpaceAndOwnerChanges), at Phase2 (PhaseTwoSpaceAndOwnerChanges), and at abort transaction (AbortChangesForTrans). These procedures have the form foo: PROCEDURE [TransID]. Possibly the parameter will not actually be the TransID, as long as it is possible to obtain the TransID, given the parameter.

FileStore, FileProperties, and AccessControl all mess about with file properties which are access lists. The following scenarios are based on the assumptions that FileProperties shouldn’t know anything about the meaning of the internals of the list, and that FileStore should do the read/write requests to FileProperties, since that’s how all the other file properties are handled:

FileStore reads a file property which is an access list by first checking the client’s permission to read the file in its open file table, (calling CheckExtraAccessFileAccessList if that fails), making a read request on FileProperties, and then calling AccessControl to expand the list into the client form.

FileStore writes a file property which is an access list by first checking the client’s permission to write the file in its open file table, (calling CheckExtraAccessFileAccessList if that fails), calling AccessControl to get the defaults for the lists or apply the minimums, as appropriate, and to compact the list into its file properties form, and then making a write request on FileProperties with these modified lists.

At system startup:

(1) FileStore must call AccessControl.InitVolatileData once and only once, regardless of the number of volume groups on the file store. A call to any other AccessControl procedure before InitVolatileData has been called is a fatal error.

(2) RegisterVolumeGroup has to be called for each previously initialized volume group to tell AccessControl the owner database FileID. No calls for a volume group will be accepted unless either RegisterVolumeGroup or InitAndRegisterVolumeGroup has been called for that group. (Maybe FileStore wants to send across a list, i.e., RegisterVolumeGroups.)

(3) For a brand new volume group, the following dance is performed: some stand-alone utility program has initialized a Pilot volume and written a root page with a unique FileID in it for the owner database file. Then FileStore creates a transaction, calls AccessControl.LengthToSetOwnerDatabaseFile (a function of the desired number of owners, etc.), and does a special CreateFileWithID which does not make any calls to AccessControl. Then FileStore calls AccessControl.InitAndRegisterVolumeGroup, which writes "empty" records in the preallocated file except for one record for AlpineWheels and puts the volumeGroup and FileID in some type of active list. FileStore then commits its transaction. InitAndRegisterVolumeGroup is also told the total amount of disk space available on the volume group, minus a fudge factor; I’m not sure if I will really track this yet, but the idea is AccessControl will allow the system administrator control over whether or not the total space in user quotas for this group can exceed this limit. Perhaps we want a provision to change this due to adding packs, etc.

What AccessControl expects from Locks

--------------------------------------------------------------

In addition to the usual implicit file locking, etc., AccessControl expects:

(1) To be able to explicitly release read locks on pages of the owner database file. (used by the enumerate routines when they do not lock the entire file.).

(2) If the lock manager detects a deadlock involving one of the transactions doing access control operations, it cannot just break the lock, instead it must abort the unlucky transaction.

Interface to AccessControl

-----------------------------------------

AccessControl: DEFS = BEGIN

OwnerName: TYPE = Rope.Ref;

ClientName: TYPE = Rope.Ref;

-- access lists. Do these definitions belong in this interface?

FileAccessType: TYPE = {read, modify};

FileAccessList: TYPE = LIST OF RName;

FileAccessListSpecification: TYPE = RECORD[type: FileAccessType, accessList: FileAccessList];

ShortFileAccessList: TYPE = RECORD[owner, world: BOOLEAN, lists: ARRAY [0..NumShortFileAccessListRNames) OF Rope.Ref];

ShortFileAccessListSpecification: TYPE = RECORD[type: FileAccessType, shortAccessList: ShortFileAccessList];

NumShortFileAccessListRNames: CARDINAL = 2;

OwnerAccessType: TYPE = {create, readAndSet};

OwnerAccessList: TYPE = LIST OF RName;

OwnerAccessListSpecification: TYPE = RECORD[type: OwnerAccessType, accessList: OwnerAccessList];

ShortOwnerAccessList: TYPE = RECORD[owner, world: BOOLEAN, lists: ARRAY [0..NumShortOwnerAccessListRNames) OF Rope.Ref];

NumShortOwnerAccessListRNames: CARDINAL = 2;

-- ERRORs reported.

BadlyFormedParameter: --CALLER-- ERROR [paramInError: BadlyFormedParameterType];

BadlyFormedParameterType: = {ClientName, OwnerName, AccessList, etc.};

SequencingError: --CALLER-- ERROR [seqError: SequencingErrorType];

SequencingErrorType: = {UnregisteredVolumeGroup, VolumeGroupAlreadyRegistered, etc.};

NoRegistrationServersAvailable: --ABSTRACTION-- ERROR;

Some other ERRORs are reported for individual procedures; see the description of each procedure for those. Does FileStore want its client’s errors, such as noSuchOwner, to come back as return codes or as ERRORS?

-- must be called before any other procedure is called.

DefaultNumberOfBuffers: CARDINAL = 10;

MaxNumberOfBuffers: CARDINAL = 30; -- a little self defense.

DefaultAccessCacheEntries: CARDINAL = 50;

MaxAccessCacheEntries: CARDINAL = 100;

InitVolatileData: PROCEDURE [nBuffers: CARDINAL ← DefaultNumberOfBuffers, accessCacheEntries: CARDINAL ← DefaultAccessCacheEntries, AlpineWheels: Rope.Ref ← "AlpineWheels↑.PA"];

--Caller errors: SequencingError, TooManyBuffersRequested, TooManyAccessCacheEntriesRequested, xxxmaybesomechecksonvalidityofAlpineWheels.

TooManyBuffersRequested: --CALLER-- ERROR;

TooManyAccessCacheEntriesRequested: --CALLER-- ERROR;

DefaultNumberOfOwnerEntries: CARDINAL = 500;

DefaultSizeFactor: CARDINAL = 4;

MaxSizeFactor: CARDINAL = 20;

LengthToSetOwnerDatabaseFile: PROCEDURE[maxEntries: CARDINAL ← DefaultNumberOfOwnerEntries, sizeFactor: CARDINAL ← DefaultSizeFactor] RETURNS [length: PageCount];

--Caller errors: SizeFactorTooLarge, NumberOfEntriesOrSizeFactorEQ0.

SizeFactorTooLarge: --CALLER-- ERROR; -- these two errors also may be

NumberOfEntriesOrSizeFactorEQ0: --CALLER-- ERROR; -- returned by ReorganizeAccessControlDataBase.

DefaultSpaceQuotaForAlpineWheels: PageCount = 2*((DefaultNumberOfOwnerEntries*DefaultSizeFactor) + OwnerFileHeaderPages) + 100; -- allow at least twice the size of an owner file. Believes one owner entry takes up one page. 100 is a guess at some fuzz.

MinimumSpaceOnVolumeGroup: PageCount = xxxxxxxx;

InitAndRegisterVolumeGroup: PROCEDURE[volumeGroup: VolumeGroup, ownerFileID: FileID, spaceQuotaForAlpineWheels: PageCount ← DefaultSpaceQuotaForAlpineWheels, spaceInUseForAlpineWheels: PageCount, totalSpaceOnVolumeGroup: PageCount] ;

--Caller errors: BadlyFormedParameter, SequencingError, AlpineWheelsInUseExceedsQuota, AlpineWheelsInUseLTOwnerFileSize, AlpineWheelsQuotaGTVolumeSpace, VolumeSpaceLTorEQ0.

AlpineWheelsInUseExceedsQuota: --CALLER-- ERROR;

AlpineWheelsInUseLTOwnerFileSize: --CALLER-- ERROR;

AlpineWheelsQuotaGTVolumeSpace: --CALLER-- ERROR;

VolumeSpaceLTorEQ0: --CALLER-- ERROR;

RegisterVolumeGroup: PROCEDURE [volumeGroup: VolumeGroup, ownerFileID: FileID];

--Caller errors: BadlyFormedParameter, SequencingError.

-- must be called to give the client "Alpine wheel" privileges during this transaction. Otherwise he or she is just an ordinary client, even if in AlpineWheels↑.

AssertAlpineWheel: PROCEDURE[transID: TransID, clientName: ClientName] RETURNS[okay: BOOLEAN];

--Caller errors: BadlyFormedParameter, SequencingError.

-- manipulating the owner-based permanent data structure. Only AlpineWheels can execute these procedures, except the owner and clients in the read/set access list can do EnumerateThisOwner and ChangeOwnerAccessLists. Note that owner access lists always have world = FALSE and owner = TRUE; we ignore attempts to set them otherwise. AddOwner and ChangeOwnerSpaceQuota worry about the total file space on the FileStore; think about how to track this without blocking. For the owner access lists, we supply defaults on AddOwner and "or" in minimums on AddOwner and ChangeOwnerAccessLists.

AddOwner: PROCEDURE[transID: TransID, clientName: ClientName, volumeGroup: VolumeGroup, ownerName: OwnerName, overCommitQuotasIfNeeded: BOOLEAN ← FALSE, diskSpaceQuota: PageCount ← DefaultSpaceQuota, ownerAccessLists: LIST OF OwnerAccessListSpecification] RETURNS [result: {okay, insufficientPrivilege, ownerAlreadyExists, notEnoughSpaceOnFileStore, noRoomLeftInOwnerDataBase, duplicatesInRequestedAccessLists}, spaceLeftOnFileStore: PageCount];

--Caller errors: BadlyFormedParameter, SequencingError.

ChangeOwnerSpaceQuota: PROCEDURE[transID: TransID, clientName: ClientName, volumeGroup: VolumeGroup, ownerName: OwnerName, overCommitQuotasIfNeeded: BOOLEAN ← FALSE, diskSpaceQuota: PageCount ← DefaultSpaceQuota] RETURNS [result: {okay, insufficientPrivilege, noSuchOwner, notEnoughSpaceOnFileStore}, spaceLeftOnFileStore: PageCount];

--Caller errors: BadlyFormedParameter, SequencingError.

ChangeOwnerAccessLists: PROCEDURE[transID: TransID, clientName: ClientName, volumeGroup: VolumeGroup, ownerName: OwnerName, ownerAccessLists: LIST OF OwnerAccessListSpecification] RETURNS [result: {okay, insufficientPrivilege, noSuchOwner, duplicatesInRequestedAccessLists, noRequestedAccessLists}]; -- The unspecified access lists are left unchanged.

--Caller errors: BadlyFormedParameter, SequencingError.

RemoveOwner: PROCEDURE[transID: TransID, clientName: ClientName, volumeGroup: VolumeGroup, ownerName: OwnerName] RETURNS [result: {okay, insufficientPrivilege, noSuchOwner, spaceInUseByThisOwner}];

--Caller errors: BadlyFormedParameter, SequencingError.

EnumerateThisOwner: PROCEDURE[transID: TransID, clientName: ClientName, volumeGroup: VolumeGroup, ownerName: OwnerName] RETURNS [result: {okay, insufficientPrivilege, noSuchOwner}, diskSpaceQuota, diskSpaceInUse: PageCount, ownerAccessLists: LIST OF OwnerAccessListSpecification];

--Caller errors: BadlyFormedParameter, SequencingError.

InitialContinuationKey: ContinuationKey = -1;

ContinuationKey: TYPE = PageCount;

EnumerateAllOwners: PROCEDURE[transID: TransID, clientName: ClientName, volumeGroup: VolumeGroup, continuationKey: ContinuationKey ← InitialContinuationKey, freezeFile: BOOLEAN] RETURNS [result: {okay, insufficientPrivilege, noMoreOwners, illegalContinuationKey}, ownerName: OwnerName, diskSpaceQuota, diskSpaceInUse: PageCount, ownerAccessLists: LIST OF OwnerAccessListSpecification, nextContinuationKey: ContinuationKey];

--Caller errors: BadlyFormedParameter, SequencingError.

-- The continuationKey sure is gross, but does it make life easy; otherwise enumerating the hashed owner file is gross. User supplied continuationKey = 0 means beginning of file, returned one is the one for the caller to supply the next time. If freezeFile, then locks out all other transactions from the owner file while this transaction is in progress.

EnumerateOwnerDatabase: PROCEDURE[transID: TransID, clientName: ClientName, volumeGroup: VolumeGroup, continuationKey: ContinuationKey ← InitialContinuationKey] RETURNS [result: {okay, insufficientPrivilege, noMoreEntries, illegalContinuationKey}, entryState: {valid, deleted, empty}, ownerName: OwnerName, diskSpaceQuota, diskSpaceInUse: PageCount, ownerAccessLists: LIST OF OwnerAccessListSpecification, continuationKey: ContinuationKey];

--Caller errors: BadlyFormedParameter, SequencingError.

-- For debugging, etc. Locks up the entire owner file while this transaction is in progress.

-- called when need to make room for more owner entries, clean up owner database, etc. Reorganizes the owner database. Will change the size of the file based on maxEntries and the requested sizeFactor.

ReorganizeAccessControlDataBase: PROCEDURE[volumeGroup: VolumeGroup, clientName: ClientName, maxEntries: CARDINAL ← DefaultNumberOfOwnerEntries, sizeFactor: CARDINAL ← DefaultSizeFactor] RETURNS [result: {okay, moreCurrentEntriesThanReqMax, notEnoughSpaceInAlpineWheelsQuotaForTempFile}, currentEntries: CARDINAL];

--Caller errors: BadlyFormedParameter, SequencingError, SizeFactorTooLarge, NumberOfEntriesOrSizeFactorEQ0.

-- can this client create files for this owner on this volume group? We expect FileStore to call this before allowing a client to create a file. (A client doesn’t need create permission to deallocate space, write permission for the file is sufficient.) The allocation request coming along allows an internal optimization for AccessControl; 0 is okay if the caller prefers. Only allocation is allowed, not deallocation, which is assumed to be a logic bug. Client permission is checked before space available is checked.

CheckAccessOwnerCreateThenAllocate: PROCEDURE[transID: TransID, clientName: ClientName, volumeGroup: VolumeGroup, ownerName: OwnerName, nPages: PageCount] RETURNS [result: {okay, insufficientPrivilege, noSuchOwner, exceedsSpaceQuota}];

--Caller errors: BadlyFormedParameter, SequencingError, DeallocationAttempted.

--Abstraction errors: NoRegistrationServersAvailable.

DeallocationAttempted: -- CALLER-- ERROR;

-- can this client access this file in the mode it requests? Called by OpenFile. FileStore has fudged an OpenFileID with enough access temporarily granted to prevent recursion.

CheckAccessFile: PROCEDURE[transID: TransID, clientName: ClientName, openFileID: OpenFileID, requestedAccess: FileAccessType] RETURNS [result: {okay, insufficientPrivilege, noSuchFile}];

--Caller errors: BadlyFormedParameter, SequencingError.

--Abstraction errors: NoRegistrationServersAvailable.

-- this checks the extra clients (owner, or any current member of the owner create list) we let through to read or modify file access lists.

CheckExtraAccessFileAccessList: PROCEDURE[transID: TransID, clientName: ClientName, openFileID: OpenFileID, requestedAccess, listType: FileAccessType] RETURNS [result: {okay, insufficientPrivilege, noSuchFile}];

--Caller errors: BadlyFormedParameter, SequencingError.

--Abstraction errors: NoRegistrationServersAvailable.

-- disk space control. called at the time the client requests the allocation (nPages > 0) and deallocation (nPages < 0). All disk space in an owner’s files, including leader pages, etc., counts as part of the owner’s quota. People who know the owner call ChangeSpaceViaOwner (CreateFile, CreateFileWithID), else they call ChangeSpaceViaOpenFileID (SetSize, DeleteFile), which has to work harder. Deallocations are deferred until PhaseOne.

ChangeSpaceViaOwner: PROCEDURE [trans: TransID, volumeGroup: VolumeGroup, ownerName: OwnerName, nPages: PageCount] RETURNS[okay: BOOLEAN];

--Caller errors: BadlyFormedParameter, SequencingError.

--Abstraction errors: NoRegistrationServersAvailable.

ChangeSpaceViaOpenFileID: PROCEDURE [trans: TransID, volumeGroup: VolumeGroup, openFileID: OpenFileID, nPages: PageCount] RETURNS[okay: BOOLEAN];

--Caller errors: BadlyFormedParameter, SequencingError.

--Abstraction errors: NoRegistrationServersAvailable.

-- fleshes out the list to include all possible file access lists; supplies defaults for missing ones, "ors" minimums into others, then compacts the lists to the FileProperties form. Expected to be called from CreateFile.

ApplyDefaultsAndMinimumsForFileAccessLists: PROCEDURE[transID: TransID, volumeGroup: VolumeGroup, ownerName: OwnerName, fileAccessLists: LIST OF FileAccessListSpecification ← NIL] RETURNS [result: {okay, noSuchOwner, duplicatesInList}, shortFileAccessLists: LIST OF ShortFileAccessListSpecification] ;

--Caller errors: BadlyFormedParameter, SequencingError.

-- no such owner is horrible error??

-- "ors" minimums into any file access lists supplied and then compacts the lists to the FileProperties form. Expected to be called from SetProperties.

ApplyMinimumsToFileAccessLists: PROCEDURE[transID: TransID, volumeGroup: VolumeGroup, openFileID: OpenFileID, fileAccessLists: LIST OF FileAccessListSpecification] RETURNS[result: {okay, duplicatesInList}, shortFileAccessLists: LIST OF ShortFileAccessListSpecification];

--Caller errors: BadlyFormedParameter, SequencingError.

-- Expands the lists to the FileStore form. Expected to be called by FileStore, after read from FileProperties.

ExpandFileAccessLists: PROCEDURE[transID: TransID, volumeGroup: VolumeGroup, openFileID: OpenFileID, fileAccessLists: LIST OF FileAccessListSpecification] RETURNS[shortFileAccessLists: LIST OF ShortFileAccessListSpecification];

--Caller errors: BadlyFormedParameter, SequencingError.

-- Called once by transaction commit BEFORE the commit record is written. Does the deallocations now. Forces the write of any dirty pages that belong to this transaction in the buffer pool.

PhaseOneSpaceAndOwnerChanges: PROCEDURE [trans: TransID];

-- Nearly a noop.

PhaseTwoSpaceAndOwnerChanges: PROCEDURE [trans: TransID];

-- Invalidates this transaction’s buffer pool pages, etc.

AbortChangesForTrans: PROCEDURE [trans: TransID];

-- misc. Some interesting statistics include the count of times someone had to wait for a buffer pool slot, stuff about the access cache, etc. (see implementation details later in this memo.)

ReportAccessControlStatistics: PROCEDURE [xxxxx] RETURNS [xxxxx];

-- debugging. At least this should report the currently registered volume groups.

ReportInternalDataStructures: PROCEDURE [xxxxx] RETURNS [xxxxx];

Implementation notes

----------------------------------

The permanent owner-based data structure contains entries with at least this information:

ownerName

{valid, deleted, empty}

createAccessList

readOrSetAccessList

disk space quota

disk space in use

The only locks and monitors involved in this implementation are as follows:

Monitor: on the buffer pool.

Locks: exclusive locks on the individual file pages, and on the file itself (only initialize, reorganize, and the enumeratealls). Also releasable read locks on the individual file pages, for the enumerate alls.

There is a pool of buffers, each of which has associated with it a record containing this information:

OwnerBuffer: TYPE = RECORD[

page: LONG POINTER TO Page,

state: {noValidData, clean, dirty},

pageNumInFile: PageNumber,

volGroup: VolumeGroup,

InUse: BOOLEAN,

transUsingID: TransID, -- some type of distinguishing "NIL" must exist. Maybe this is a pointer to a transID or somesuch.

lruNext, lruPrev: LONG POINTER TO OwnerBuffer];

The buffer pages are on a doubly linked lru/mru list. On release, a page with noValidData moves to lru. Dirty pages move to mru. Possibly clean "unsatisfactory" pages will be lru, but I haven’t decided exactly what "unsatisfactory" means.

The actual reading of pages of the owner database files takes place through calls on FileStore, using the client transaction’s openFileID.

Because we open the owner data file in the name of our client transactions, because deletes of space will be deferred until PhaseOne, and because of AlpineWheels "declaring" themselves, we have a small volatile data structure containing entries of the form:

TransInProgress: TYPE = RECORD[

transID: TransID or something,

volumes: REF Volumes,

alpineWheels: LIST OF ClientName];

Volumes: TYPE = RECORD[

volGroup: VolumeGroup,

ownerOpenFileID: OpenFileID,

owners: REF OwnerDeallocates];

OwnerDeallocates: TYPE = RECORD[

ownerID: OwnerID,

spaceToDelete: PageCount,

nextOwner: REF OwnerDeallocates];

There will be some sort of lru caching mechanism to save [clientName, accessListName] pairs.

Information about the current allocation of quota space, etc. probably will be kept in some header page(s) of the owner database file. AddOwner, RemoveOwner, and ChangeOwnerSpaceQuota (rare operations) will serialize transactions by write locking this page.

********************N.b., Only a little bit of bug checking is documented in the algorithm descriptions below. Releases, etc. aren’t generally documented on error returns. Basically these descriptions are just working notes and should not be interpreted as what the code will look like or even how things will be divided into routines.********************

Here are some internal routines involving the buffer pool:

GetPage [transID, {wantOwner, wantEmpty}, owner] RETURNS [handleValid: BOOLEAN, handle: xxxxx]. -- A valid handle is returned only if (wantOwner AND foundOwner) OR (wantEmpty AND NOT foundOwner). (There is something like GetAbsolutePage[transID, filePageNumber, modetolockthepage] for the initialization, reorganize, and enumeratealls.)

Calculate the probable file page number we want (Perhaps maintain a little list of pages out of place?).

Write lock it.

Monitor: buffer pool.

Is our pageNumber in the pool?

Yes: If inUse, (someone must be getting this buffer), wait on SlotWritten and then try again.

No: If all buffers are inUse, wait on SlotAvail then try again.

Set inUse.

Set our transID.

Exit monitor: buffer pool.

If not our page:

If dirty, write the page.

Set our page number.

Set noValidData.

If noValidData, do the read and set clean.

Is this the owner we specified and is it valid?

Yes: if out of place, update the little list of pages out of place.

if wantOwner: success. done.

if wantEmpty: ownerAlreadyExists/ReleasePage[lru]/done.

Is this entry empty?

Yes: if wantOwner: noSuchOwner/ReleasePage[lru]/done.

If wantEmpty: success. done.

Must be a deleted entry or a valid nonmatch:

ReleasePage[lru]. Calc the next probable page and loop to the writelock step. If wrap completely without finding a stop:

if wantOwner: noSuchOwner/done.

if wantEmpty: noEmptySlots/done.

ReleasePage [{lru, mru}]:

Monitor: buffer pool.

Clear inUse.

Relink it as lru or mru.

Notify SlotAvail.

Exit monitor: buffer pool.

PhaseOne:

For each owner deallocation we recorded, update the appropriate owner record and clean up the volatile data structure. (Beware the case where we removed the owner in this transaction.)

Monitor: buffer pool.

For each buffer with our transID:

If dirty and NOT inUse:

Set inUse.

Exit monitor: buffer pool.

Write the page.

Set clean.

Monitor: buffer pool.

Clear inUse.

Notify SlotAvail.

For each buffer with our transID:

If dirty and inUse: wait on SlotWritten then restart.

Exit monitor: buffer pool.

PhaseTwo:

Monitor: buffer pool.

For each buffer with our transID, clear our transID.

Exit monitor: buffer pool.

AbortTrans:

Monitor: buffer pool.

For each buffer with our transID and NOT inUse:

Clear our transID.

Set noValidData.

Relink the slot as lru.

For each slot with our transID and inUse: wait on SlotWritten then restart.

Clean up the volatile data structure.

Exit monitor: buffer pool.

These are routines that involve only the file properties database:

CheckAccessFile:

Call FileProperties to get the appropriate access list and check the access. Password is guaranteed. (A registered AlpineWheel for this transaction is also valid.)

ApplyMinimumsToFileAccessLists

Ensure minimums are set (don’t complain if they weren’t).

Compact lists to FileProperties form.

ExpandFileAccessList

Convert from FileProperties to FileStore form.

These are routines that involve only the owner database:

CheckExtraAccessFileAccessList:

Check for the owner, AlpineWheels, or in the current owner create list.

Have some smarts so know what minimums have already been checked?

Password is guaranteed.

InitVolatileData:

Make a new buffer pool (better not already exist) and maybe do some other initializing. Perhaps check that the AlpineWheels list is valid?

RegisterVolumeGroup:

Tuck away the volumeID and the FileID of its owner database file in some list we have.

LengthToSetOwnerDatabaseFile:

Doesn’t actually touch the owner database, but knows about record sizes, etc.

InitAndRegisterVolumeGroup:

"Zero" out the entire owner file for this volume group by writing empty records it in, except do a semi-CreateOwner for AlpineWheels as specified, fill in the header page(s).

CheckAccessOwnerCreateThenAllocate:

GetPage[wantOwner].

If no valid handle, error return noSuchOwner.

Check the access.

If okay and the requested allocation <> 0, check the allocation request and either error return or do it. If do it, mark the page dirty.

Release the page.

ChangeSpaceViaOwner:

GetPage[wantOwner].

If no valid handle, error return noSuchOwner.

Like last part of CheckAccessOwnerCreateThenAllocate, except we defer deallocates by using our volatile structure.

RemoveOwner:

If NOT AlpineWheels, error return insufficientPrivilege.

GetPage[wantOwner].

If no valid handle, error return noSuchOwner.

If space in use, error return spaceInUseByThisOwner (take into account deferred deletes).

Mark the owner deleted.

Mark the page dirty and release it.

AddOwner:

If NOT AlpineWheels, error return insufficientPrivilege.

GetPage[wantEmpty].

If NOT valid handle, error return ownerAlreadyExists.

If not overcommit space and not enough space available for the requested quota, error return.

If requested access lists are messed up, error return.

Build an owner record in the page.

Mark the page dirty and release the page.

ChangeOwnerSpaceQuota:

If NOT AlpineWheels, error return insufficientPrivilege.

GetPage[wantOwner].

If no valid handle, error return noSuchOwner.

If not overcommit space and not enough space available for the requested quota, error return.

Do the change.

Mark the page dirty and release it.

ChangeOwnerAccessLists:

GetPage[wantOwner].

If no valid handle, error return noSuchOwner.

If NOT (AlpineWheels or in the owner readOrSetAccessList), error return insufficientPrivilege.

If requested access lists are messed up, error return.

Do the changes.

Mark the page dirty and release it.

EnumerateThisOwner:

GetPage[wantOwner].

If no valid handle, error return noSuchOwner.

If NOT (AlpineWheels or in the owner readOrSetAccessList), error return insufficientPrivilege.

Read the information.

Release the page.

EnumerateAllOwners:

If not an AlpineWheel, error return.

If freezeFile, wait for a write lock on the entire owner database file. (If not freezeFile, get just a read lock on the page and release the lock after we have the data).

The user supplied continuation key is the file page number. Check it and if okay do a GetAbsolutePage on that page. Continue until we find a valid entry, then report it or if none report no more entries.

Any better way to enumerate a hash table easily than the continuation crock proposed?

EnumerateOwnerDatabase:

This is like EnumerateAllOwners, except it reports the empty and deleted entries as well, and it always exclusive locks the entire file.

PhaseOneSpaceAndOwnerChanges:

Just the phase one buffer routine described previously.

PhaseTwoSpaceAndOwnerChanges:

Just the phase two buffer routine described previously.

AbortChangesForTrans:

Just the abort buffer routine described previously.

ReorganizeAccessControlDataBase:

If NOT AlpineWheels, error return.

Wait for a write lock on the owner database file.

Do a simple number on it to reorganize it (deleted entries become empty, etc.), probably by just enumerating the valid entries into a scratch file of the appropriate length (prime) and then writing that back over the original file. Invalidate the pages for this volume group in the buffer pool, unless we kept them up to date or something.

These are routines that involve both the file properties and the owner database:

ChangeSpaceViaOpenFileID:

Like ChangeSpaceViaOwner, but first we have to ask FileProperties what the owner is (use the openFileID.)

ApplyDefaultsAndMinimumsForFileAccessLists

Supply any missing lists, set the defaults via reading the owner create list.

Compact lists to FileProperties form.

ReportAccessControlStatistics:

Return the statistics we have been keeping.

ReportInternalDataStructures:

At least this should report the currently registered volume groups.

These are routines that involve neither the file properties nor the owner database:

AssertAlpineWheel:

Checks membership in the registered AlpineWheels list and enters this client name as an Alpine wheel for this transaction.

Misc:

AccessControl defends itself against calls during recovery, duplicate attempts at initialization, etc. (Some okay stuff gets thru by design while initializing.)

Modularize authentication calls.

Other things still to do:

Note "distinguished" names.

Scavenging a bad owner data base file.

Twitching the file in the root directory isn’t transaction protected.

Releasing locks problem.

Don’t like properties snarl.

END. -- AccessControl