Heading:qjk40(635) Alpine access control design, version 7y756qjk40 Page Numbers: Yes X: 527 Y: 10.5"qjk40 DRAFT - DRAFT - DRAFT - DRAFTz18592l4445y762\f5b29B To Alpine designers Date September 11, 1981z18592l4445d2998e21(0,65535)(1,4445)(5,11684)(6,14146)\f1 2f0t2 1t0 16t6 1f1t0 4f0t7 1t0 From Karen Kolling Location PARC/CSLz18592l4445d2998y716e25\f1 4f0t2 1t0 13t6 1f1t0 8f0t7 1t0g8G Subject Alpine access control design, version 7 File [Ivy]Doc>AccessControlDesign7.bravoz18592l4445d2998e25\f1 7f0t2 1t0 39t6 1f1t0g4f0t7G3f1t0g43f0G z18592l4445 XEROX z18697l508y644e14(2116)\f2 5f0 Attributes: informal, technical, Alpine, filing, access control, protectionz18697l4896d2999e10(0,4904)(1,65535)(5,65535)(6,65535)\f1 11f0 Abstract: This memo proposes the scope of and interface to Alpine's access control module, and contains notes on its implementation.z18697l4896d2999e10j\f1 9f0 (1792) Overview\b8B --------------- 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\b13B --------------------------- 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. l3520d3008 l3520d3008 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.l3520d3008\46g l3520d3008 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.l3520d3008 l3520d3008 4. Disk space control involves a data structure containing owner-based items. These include the disk quota, disk usage, and these access lists: l3520d3008 who can create files with this ownerName.l5504d4800 who can read and set these owner access lists.l5504d4800 The defaults for these access lists and the minimum below which each cannot be reduced are:l3520 l3520 default minimuml3520 create owner ownerl3520 read/set owner owner l3520 l3520 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.l3520 l3520d3008 5. File access involves a data structure containing file-based items. These include these access lists: l3520d3008 who can read the file.l5504d4800 who can modify the file (including extend, truncate, and delete).l5504d4800 The defaults for these access lists and the minimum below which each cannot be reduced are:l3520 l3520 default minimuml3520 read world ownerl3520 modify owner,ownercreatelistatthetimethisfilewascreated nulll3520 l5504d3520 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.l3520 l4288 6. The minimums for access lists for both owners and files are enforced by oring them in rather than complaining to the user.l3520d3008 l3520d3008 7. We encourage clients to allocate space in a non-piecemeal fashion.l3520d3008 l3520d3008 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.l3552d2999 l3552d2999 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.l3552d2999 l3552d2999 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.l3552d2999 l3552d2999 11. The owner data base file will be entered in the root directory.l3552d2999 What AccessControl expects from FileProperties\b46B -------------------------------------------------------------------------- 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\b41B ------------------------------------------------------------------- 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.) OpenFile CheckAccessFile (appropriate mode) SetSize ChangeSpaceViaOpenFileID DeleteFile ChangeSpaceViaOpenFileID GetProperties CheckExtraAccessFileAccessList\g13G ExpandFileAccessList SetProperties CheckExtraAccessFileAccessList\1g13G 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.l3008 l4416d3744 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: l4800 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.l4800 l4800 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.l4800 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.l4800d4224 l4800d4224 (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.)l4800d4224 l4800d4224 (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.l4800d4224 What AccessControl expects from Locks\b37B -------------------------------------------------------------- In addition to the usual implicit file locking, etc., AccessControl expects: d4224 (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.).l4800d4224 l4800d4224 (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.l4800d4224 l5376d4928 l3008 \b Interface to AccessControl\b26B ----------------------------------------- AccessControl: DEFS = BEGIN\b13B OwnerName: TYPE = Rope.Ref;l3712d2999\b9B ClientName: TYPE = Rope.Ref;\b10B -- access lists. Do these definitions belong in this interface? FileAccessType: TYPE = {read, modify};\b14B FileAccessList: TYPE = LIST OF RName; l3520d2998\b14B FileAccessListSpecification: TYPE = RECORD[type: FileAccessType, accessList: FileAccessList];l3520d2998\b27B l3520d2998 ShortFileAccessList: TYPE = RECORD[owner, world: BOOLEAN, lists: ARRAY [0..NumShortFileAccessListRNames) OF Rope.Ref]; l3520d2998\b19B ShortFileAccessListSpecification: TYPE = RECORD[type: FileAccessType, shortAccessList: ShortFileAccessList];l3520d2998\b32B NumShortFileAccessListRNames: CARDINAL = 2; \b28B OwnerAccessType: TYPE = {create, readAndSet};\b15B OwnerAccessList: TYPE = LIST OF RName; l3520d2998\b15B OwnerAccessListSpecification: TYPE = RECORD[type: OwnerAccessType, accessList: OwnerAccessList];l3520d2998\b28B l3520d2998 ShortOwnerAccessList: TYPE = RECORD[owner, world: BOOLEAN, lists: ARRAY [0..NumShortOwnerAccessListRNames) OF Rope.Ref]; l3520d2998\b20B NumShortOwnerAccessListRNames: CARDINAL = 2; \b29B l3520d2998 l3520d2998 -- ERRORs reported. BadlyFormedParameter: --CALLER-- ERROR [paramInError: BadlyFormedParameterType];\b20g1B33G20g BadlyFormedParameterType: = {ClientName, OwnerName, AccessList, etc.};\b20g4B47G SequencingError: --CALLER-- ERROR [seqError: SequencingErrorType];\bg16B SequencingErrorType: = {UnregisteredVolumeGroup, VolumeGroupAlreadyRegistered, etc.}; \bg19B NoRegistrationServersAvailable: --ABSTRACTION-- ERROR;\bg31B 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.l3552d2999 l3552d2999\bg DefaultNumberOfBuffers: CARDINAL = 10;l3552d2999\bg22B16b MaxNumberOfBuffers: CARDINAL = 30; -- a little self defense.l3552d2999\bg18B16G DefaultAccessCacheEntries: CARDINAL = 50;l3552d2999\b25B MaxAccessCacheEntries: CARDINAL = 100;l3552d2999\b21B InitVolatileData: PROCEDURE [nBuffers: CARDINAL _ DefaultNumberOfBuffers, accessCacheEntries: CARDINAL _ DefaultAccessCacheEntries, AlpineWheels: Rope.Ref _ "AlpineWheels^.PA"];l3520d2999\b16B11g78G25g --Caller errors: SequencingError, TooManyBuffersRequested, TooManyAccessCacheEntriesRequested, xxxmaybesomechecksonvalidityofAlpineWheels.l3520d2999\g34G103g TooManyBuffersRequested: --CALLER-- ERROR;l3520d2999\b23Bg TooManyAccessCacheEntriesRequested: --CALLER-- ERROR;l3520d2999\b34Bg l3552d2999 DefaultNumberOfOwnerEntries: CARDINAL = 500;\b27B DefaultSizeFactor: CARDINAL = 4;\b17B MaxSizeFactor: CARDINAL = 20;\b13B LengthToSetOwnerDatabaseFile: PROCEDURE[maxEntries: CARDINAL _ DefaultNumberOfOwnerEntries, sizeFactor: CARDINAL _ DefaultSizeFactor] RETURNS [length: PageCount];l3520d2999\b28B76g8G50g --Caller errors: SizeFactorTooLarge, NumberOfEntriesOrSizeFactorEQ0.l3520d2999\g SizeFactorTooLarge: --CALLER-- ERROR; -- these two errors also may bel3520d2998\bg18B19G NumberOfEntriesOrSizeFactorEQ0: --CALLER-- ERROR; -- returned by ReorganizeAccessControlDataBase.l3520d2998\bg30B23G44g \b \b 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.l3520d2998\b32B MinimumSpaceOnVolumeGroup: PageCount = xxxxxxxx;\b25B InitAndRegisterVolumeGroup: PROCEDURE[volumeGroup: VolumeGroup, ownerFileID: FileID, spaceQuotaForAlpineWheels: PageCount _ DefaultSpaceQuotaForAlpineWheels, spaceInUseForAlpineWheels: PageCount, totalSpaceOnVolumeGroup: PageCount] ;l3520d2999\b26B12g31G43g9G64g9G39g --Caller errors: BadlyFormedParameter, SequencingError, AlpineWheelsInUseExceedsQuota, AlpineWheelsInUseLTOwnerFileSize, AlpineWheelsQuotaGTVolumeSpace, VolumeSpaceLTorEQ0.l3520d2999\g17G22g AlpineWheelsInUseExceedsQuota: --CALLER-- ERROR;l3520d2999\bg29B AlpineWheelsInUseLTOwnerFileSize: --CALLER-- ERROR;l3520d2999\bg32B13G6g AlpineWheelsQuotaGTVolumeSpace: --CALLER-- ERROR;l3520d2999\bg30B13G6g VolumeSpaceLTorEQ0: --CALLER-- ERROR;l3520d2999\bg18B13G6g l3520 l3520 RegisterVolumeGroup: PROCEDURE [volumeGroup: VolumeGroup, ownerFileID: FileID];l3520d2999\b21B9g --Caller errors: BadlyFormedParameter, SequencingError.l3520d2999\g17G20g -- 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^.l3520d2999\g AssertAlpineWheel: PROCEDURE[transID: TransID, clientName: ClientName] RETURNS[okay: BOOLEAN];l3520d2999\b17B19g9G25g --Caller errors: BadlyFormedParameter, SequencingError.l3520d2999\g17G22g l3520d2999\g l3520d2999\g -- 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.l3008d2998 l3520d2998 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];l3520d2999\b8B19g11G70g118G28g --Caller errors: BadlyFormedParameter, SequencingError.l3520d2999\g17G22g l4352d3520 ChangeOwnerSpaceQuota: PROCEDURE[transID: TransID, clientName: ClientName, volumeGroup: VolumeGroup, ownerName: OwnerName, overCommitQuotasIfNeeded: BOOLEAN _ FALSE, diskSpaceQuota: PageCount _ DefaultSpaceQuota] RETURNS [result: {okay, insufficientPrivilege, noSuchOwner, notEnoughSpaceOnFileStore}, spaceLeftOnFileStore: PageCount];l3520d2999\b21B19g11G70g --Caller errors: BadlyFormedParameter, SequencingError. l3520d2998\g17G22g 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.l3520d2999\b22B19g11G70g28G28g --Caller errors: BadlyFormedParameter, SequencingError.l3520d2998\g17G22g l3520d2998\g RemoveOwner: PROCEDURE[transID: TransID, clientName: ClientName, volumeGroup: VolumeGroup, ownerName: OwnerName] RETURNS [result: {okay, insufficientPrivilege, noSuchOwner, spaceInUseByThisOwner}];l3520d2999\b11B19g11G70g --Caller errors: BadlyFormedParameter, SequencingError.l3520d2998\g17G22g l4352d3520 EnumerateThisOwner: PROCEDURE[transID: TransID, clientName: ClientName, volumeGroup: VolumeGroup, ownerName: OwnerName] RETURNS [result: {okay, insufficientPrivilege, noSuchOwner}, diskSpaceQuota, diskSpaceInUse: PageCount, ownerAccessLists: LIST OF OwnerAccessListSpecification];l3520d2999\b18B19g11G22g2G35g143G28g --Caller errors: BadlyFormedParameter, SequencingError.l3520d3008\g17G22g16G l3520d3008 InitialContinuationKey: ContinuationKey = -1;l3520d2999\b24B ContinuationKey: TYPE = PageCount;l3520d2999\b15B 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];l3520d2999\b18B19g11G22g2G41g2G15g3G22g109G20g71G28g2G19g2G15g --Caller errors: BadlyFormedParameter, SequencingError.l3520d2999\g17G22g -- 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.l3520d3008\3g4G15g114G15g94G l3520d3008 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];l3520d2999\b22B19g11G22g2G41g2G15g3G22g89G57g71G28g2G15g2G15g --Caller errors: BadlyFormedParameter, SequencingError.l3520d3008\g17G22g16G -- For debugging, etc. Locks up the entire owner file while this transaction is in progress.l3520\3g19G71g -- 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];l3520d2999\b31B126g8G76g44G29g --Caller errors: BadlyFormedParameter, SequencingError, SizeFactorTooLarge, NumberOfEntriesOrSizeFactorEQ0.l3520d2999\g17G22g -- 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}];l3520d2999\b34B19g11G10g2G10g2G35g2G9g --Caller errors: BadlyFormedParameter, SequencingError, DeallocationAttempted.l3520d2999\g17G20g --Abstraction errors: NoRegistrationServersAvailable.l3520d2999\g DeallocationAttempted: -- CALLER-- ERROR;l3520d2999\bg21B -- 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}];l3520d2999\b15B19g11G10g2G10g2G10g2G10g19G14g --Caller errors: BadlyFormedParameter, SequencingError.l3520d2999\g17G20g --Abstraction errors: NoRegistrationServersAvailable.l3520d2999\g -- 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}];l3520d2999\b30B19g11G10g2G10g2G10g2G10g29G14g --Caller errors: BadlyFormedParameter, SequencingError.l3520d2999\g17G20g --Abstraction errors: NoRegistrationServersAvailable.l3520d2999\g -- 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];l3520d2999\b19B11g18G46g --Caller errors: BadlyFormedParameter, SequencingError.l3520d2999\g17G20g --Abstraction errors: NoRegistrationServersAvailable.l3520d2999\g ChangeSpaceViaOpenFileID: PROCEDURE [trans: TransID, volumeGroup: VolumeGroup, openFileID: OpenFileID, nPages: PageCount] RETURNS[okay: BOOLEAN];l3520d2999\b24B11g18G48g --Caller errors: BadlyFormedParameter, SequencingError.l3520d2999\g17G20g --Abstraction errors: NoRegistrationServersAvailable.l3552d2999\g53G -- 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] ;l3520d2999\b42B19g11G26g47G34g87G32g --Caller errors: BadlyFormedParameter, SequencingError.l3520d2999\g17G22g -- no such owner is horrible error??l3520d2999\g -- "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];l3520d2999\b30B19g11G36g2G10g27G28g73G32g --Caller errors: BadlyFormedParameter, SequencingError.l3520d2999\g17G22g l3520d2999\g l3520d2999\g -- 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];l3520d2999\b21B19g11G36g2G10g27G28g39G32g --Caller errors: BadlyFormedParameter, SequencingError.l3520d2999\g17G22g l3520d2999\g l3520d2999\g -- 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];l3552d2999\b28B11g18G -- Nearly a noop. PhaseTwoSpaceAndOwnerChanges: PROCEDURE [trans: TransID];l3552d2999\b28B11g18G -- Invalidates this transaction's buffer pool pages, etc.l3008 AbortChangesForTrans: PROCEDURE [trans: TransID];l3552d2999\b20B11g18G l3552d2999 l3552d2999 -- 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.)l3552d2999 l4576d3008 ReportAccessControlStatistics: PROCEDURE [xxxxx] RETURNS [xxxxx];\b30B35b l3552d2999 l3552d2999 -- debugging. At least this should report the currently registered volume groups.l3552d2999 l3552d2999 ReportInternalDataStructures: PROCEDURE [xxxxx] RETURNS [xxxxx];l3552d2999\b28B Implementation notes\b20B ---------------------------------- The permanent owner-based data structure contains entries with at least this information: ownerNamed6240 {valid, deleted, empty}d6240 createAccessListd6240 readOrSetAccessListd6240 disk space quotad6240 disk space in used6240 l4736d3872 The only locks and monitors involved in this implementation are as follows: d3872 Monitor: on the buffer pool.d3520 d3872 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.l4928d3520 d3872 l3008d2999 There is a pool of buffers, each of which has associated with it a record containing this information:l3008d2999 l3008d2999 OwnerBuffer: TYPE = RECORD[l3008d2999 page: LONG POINTER TO Page,l3008d4960 state: {noValidData, clean, dirty},l3008d4960 pageNumInFile: PageNumber,l3008d4960 volGroup: VolumeGroup,l3008d4960 InUse: BOOLEAN,l3008d4960 transUsingID: TransID, -- some type of distinguishing "NIL" must exist. Maybe this is a pointer to a transID or somesuch.l6272d4960 lruNext, lruPrev: LONG POINTER TO OwnerBuffer];l3008d4960 l3008d2999 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.l3008d2999 l3008d2999 The actual reading of pages of the owner database files takes place through calls on FileStore, using the client transaction's openFileID.l3008d2999 l3008d2999 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:l3008d2999 l3008d2999 TransInProgress: TYPE = RECORD[l3008d2999 transID: TransID or something,l3008d4960 volumes: REF Volumes,l3008d4960 alpineWheels: LIST OF ClientName];l3008d4960 l3008d4960 Volumes: TYPE = RECORD[l3008 volGroup: VolumeGroup,l4278d4960 ownerOpenFileID: OpenFileID,l4278d4960 owners: REF OwnerDeallocates];l4278d4960 l4278d4960 OwnerDeallocates: TYPE = RECORD[l3008 ownerID: OwnerID,l4278d4960 spaceToDelete: PageCount,l4278d4960 nextOwner: REF OwnerDeallocates];l4278d4960 l3008d2999 There will be some sort of lru caching mechanism to save [clientName, accessListName] pairs. l3008d2999 l3008d2999 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.l3008d2999 l3008d2999 ********************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.********************l3008d2999 l3008d2999 l3008d2999 l3552d2999 Here are some internal routines involving the buffer pool:l3552d2999 l3552d2999 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.)l3552d2999 l4576d4192 Calculate the probable file page number we want (Perhaps maintain a little list of pages out of place?).l4576d4192 Write lock it.l4576d4192 Monitor: buffer pool.l4576d4192 Is our pageNumber in the pool?l4576d4192 Yes: If inUse, (someone must be getting this buffer), wait on SlotWritten and then try again.l6432d5472\62b11B No: If all buffers are inUse, wait on SlotAvail then try again.l6432d5472\38b9B Set inUse.l5162d4192 Set our transID.l5162d4192 Exit monitor: buffer pool.l5162d4192 If not our page:l5162d4192 If dirty, write the page.l6432d5462 Set our page number.l6432d5462 Set noValidData.l6432d5462 If noValidData, do the read and set clean.l5162d4192 Is this the owner we specified and is it valid?l5162d4192 Yes: if out of place, update the little list of pages out of place.l6432d5462 if wantOwner: success. done.l6432 if wantEmpty: ownerAlreadyExists/ReleasePage[lru]/done.l6432 Is this entry empty?l5162d4192 Yes: if wantOwner: noSuchOwner/ReleasePage[lru]/done.l6432d5462 If wantEmpty: success. done.l6432 Must be a deleted entry or a valid nonmatch:l7808d4192 ReleasePage[lru]. Calc the next probable page and loop to the writelock step. If wrap completely without finding a stop:l5984d5472 if wantOwner: noSuchOwner/done.l8320d6432 if wantEmpty: noEmptySlots/done.l8320d6432 l7808d8320 l3552d2999 ReleasePage [{lru, mru}]:l3552d2999 Monitor: buffer pool.l4576d4192 Clear inUse.l4576d4192 Relink it as lru or mru.l4576d4192 Notify SlotAvail.l4576d4192\7b9B Exit monitor: buffer pool.l5162d4192 l3552d2999 PhaseOne:l3552d2999 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.)l4576d4192 Monitor: buffer pool.l4576d4192 For each buffer with our transID: l4576d4192 If dirty and NOT inUse:l5846d5462 Set inUse.l7116d6732 Exit monitor: buffer pool.l7116d6732 Write the page.l7116d6732 Set clean.l7116d6732 Monitor: buffer pool.l7116d6732 Clear inUse.l7116d6732 Notify SlotAvail.l7116d6732\7b9B For each buffer with our transID: l4576d4192 If dirty and inUse: wait on SlotWritten then restart.l4576d5472\28b11B Exit monitor: buffer pool.l5162d4192 l3552d2999 l3552d2999 PhaseTwo:l3552d2999 Monitor: buffer pool.l4576d4192 For each buffer with our transID, clear our transID. l4576d4192 Exit monitor: buffer pool.l5162d4192 l3552d2999 l3552d2999 AbortTrans:l3552d2999 Monitor: buffer pool.l4576d4192 For each buffer with our transID and NOT inUse: l4576d4192 Clear our transID.l5846d5472 Set noValidData.l5846d5472 Relink the slot as lru.l5846d5472 For each slot with our transID and inUse: wait on SlotWritten then restart.l4576d4192\50b11B Clean up the volatile data structure.l4576d4192 Exit monitor: buffer pool.l5162d4192 l5152d4192 l3552d2999 These are routines that involve only the file properties database:l3552d2999 l3552d2999 l3552d2999 CheckAccessFile:l3552d2999\b15B l3552d2999 Call FileProperties to get the appropriate access list and check the access. Password is guaranteed. (A registered AlpineWheel for this transaction is also valid.)l4032 l4576d3008 ApplyMinimumsToFileAccessLists\b30B Ensure minimums are set (don't complain if they weren't).l4032 Compact lists to FileProperties form.l4032 l4576d3008 ExpandFileAccessList\b20B Convert from FileProperties to FileStore form.d4032 l4192 l3552d2999 These are routines that involve only the owner database:l3552d2999 l3552d2999 l3552d2999 CheckExtraAccessFileAccessList:l3552d2999\b30B l3552d2999 Check for the owner, AlpineWheels, or in the current owner create list. l4448d4032 Have some smarts so know what minimums have already been checked?l4448d4032 Password is guaranteed.l4032 l4576d3008 InitVolatileData:l3552d2999\b16B l3552d2999 Make a new buffer pool (better not already exist) and maybe do some other initializing. Perhaps check that the AlpineWheels list is valid?l4576d4032 l4576d3008 RegisterVolumeGroup:l3552d2999\b19B l3552d2999 Tuck away the volumeID and the FileID of its owner database file in some list we have.l4576d4032 l4576d3008 LengthToSetOwnerDatabaseFile:l3552d2999\b28B l3552d2999 Doesn't actually touch the owner database, but knows about record sizes, etc.l4576d4032 l4576d3008 InitAndRegisterVolumeGroup:l4576d3008\b27Bg l4576d4032\g "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).l4576d4032 Register the volume group.l4576d4032 l3648d2999 l4576d3008 CheckAccessOwnerCreateThenAllocate:l3552d2999\b34B l3552d2999 GetPage[wantOwner].l4576d4192 If no valid handle, error return noSuchOwner.l4576d4192 Check the access.l4576d4192 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.l4576d4192 Release the page.l6432d4192 l4192 l3552d2999 ChangeSpaceViaOwner:l3552d2999\b19B l3552d2999 GetPage[wantOwner].l4576d4192 If no valid handle, error return noSuchOwner.l4576d4192 Like last part of CheckAccessOwnerCreateThenAllocate, except we defer deallocates by using our volatile structure.l4576d4192 RemoveOwner:\b l4576d3008 If NOT AlpineWheels, error return insufficientPrivilege.l4576d4032\33g22G GetPage[wantOwner].l4576d4032 If no valid handle, error return noSuchOwner.l4576d4032 If space in use, error return spaceInUseByThisOwner (take into account deferred deletes).l4576d4032\30g21G Mark the owner deleted.l4576d4032 Mark the page dirty and release it.l4576d4032 d4032 l4576d3008 AddOwner:\b l4576d3008 If NOT AlpineWheels, error return insufficientPrivilege.l4576d4032\33g22G GetPage[wantEmpty].l4576d4032 If NOT valid handle, error return ownerAlreadyExists.l4576d4032\34g18G If not overcommit space and not enough space available for the requested quota, error return.l5312d4032 If requested access lists are messed up, error return.l5312d4032 Build an owner record in the page.l4576d4032 Mark the page dirty and release the page.l4576d4032 d4032 l4576d3008 ChangeOwnerSpaceQuota:\b l4576d3008 If NOT AlpineWheels, error return insufficientPrivilege.l4576d4032\33g22G GetPage[wantOwner].l4576d4032 If no valid handle, error return noSuchOwner.l4576d4032 If not overcommit space and not enough space available for the requested quota, error return.l5312d4032 Do the change.l4576d4032 Mark the page dirty and release it.l4576d4032 d4032 d4032 ChangeOwnerAccessLists:\b l4576d3008 GetPage[wantOwner].l4576d4032 If no valid handle, error return noSuchOwner.l4576d4032 If NOT (AlpineWheels or in the owner readOrSetAccessList), error return insufficientPrivilege.l4576d4032\71g22G If requested access lists are messed up, error return.l5312d4032 Do the changes.l4576d4032 Mark the page dirty and release it.l4576d4032 d4032 d4032 EnumerateThisOwner:\b l4576d3008 GetPage[wantOwner].l4576d4032 If no valid handle, error return noSuchOwner.l4576d4032 If NOT (AlpineWheels or in the owner readOrSetAccessList), error return insufficientPrivilege.l4576d4032\71g22G Read the information.l4576d4032 Release the page.l4576d4032 \b \b EnumerateAllOwners:\b l4576d3008 If not an AlpineWheel, error return.l4576d4032 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).l4576d4032 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. l4576d4032 Any better way to enumerate a hash table easily than the continuation crock proposed?l4576d4032 \b \b EnumerateOwnerDatabase:\b l4576d3008 This is like EnumerateAllOwners, except it reports the empty and deleted entries as well, and it always exclusive locks the entire file.l4576d4032 d4032 PhaseOneSpaceAndOwnerChanges:\b28B1b l4576d3008 Just the phase one buffer routine described previously.l4576d4032 l3552d2999 PhaseTwoSpaceAndOwnerChanges:\b28B1b l4576d3008 Just the phase two buffer routine described previously.l4576d4032 l3552d2999 AbortChangesForTrans:\b20B l4576d4032 Just the abort buffer routine described previously.l4576d4032 l3552d2999 l4576d4032 ReorganizeAccessControlDataBase:l4576d3008\b32Bg l4576d3008\g If NOT AlpineWheels, error return.l4576d4032 Wait for a write lock on the owner database file.l4576d4032 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.l4576d4032 l4576d3008 l3648d2999 l3552d2999 These are routines that involve both the file properties and the owner database:l3552d2999 l4576d4032 l3552d2999 ChangeSpaceViaOpenFileID:l3552d2999\b l3552d2999 Like ChangeSpaceViaOwner, but first we have to ask FileProperties what the owner is (use the openFileID.)l4576d4032 l4576d4032 l3008d2999\b ApplyDefaultsAndMinimumsForFileAccessListsl3008d2999\b42B l3008d2999 Supply any missing lists, set the defaults via reading the owner create list.l4032 Compact lists to FileProperties form.l5312d4032 l4576d4032 l4576d4032 ReportAccessControlStatistics:\b l4576d3008 Return the statistics we have been keeping.d4032 ReportInternalDataStructures:l3552d2999\b28B l3552d2999 At least this should report the currently registered volume groups.l4576d4032 l4576d3008 l3552d2999 These are routines that involve neither the file properties nor the owner database:l3552d2999 l3552d2999 AssertAlpineWheel:l3552d2999\b l3552d2999 Checks membership in the registered AlpineWheels list and enters this client name as an Alpine wheel for this transaction.l4576d4032 l4576d4032 l4576d4032 l3552d2999 Misc:l3008d2999 l3008d2999 AccessControl defends itself against calls during recovery, duplicate attempts at initialization, etc. (Some okay stuff gets thru by design while initializing.)l3008d2999 l3008d2999 Modularize authentication calls.l3008d2999 l3008d2999 l3008d2999 Other things still to do:l3008d2999 l3008d2999 Note "distinguished" names.l3008d2999 l3008d2999 Scavenging a bad owner data base file. l3008d2999 Twitching the file in the root directory isn't transaction protected. Releasing locks problem. Don't like properties snarl. END. -- AccessControl\b