AccessControlCacheImpl.mesa
Copyright © 1984 by Xerox Corporation. All rights reserved.
Last edited by
Kolling on June 10, 1983 12:50 pm
MBrown on January 30, 1984 2:57:34 pm PST
Last Edited by: Kupfer, August 6, 1984 1:47:40 pm PDT
Carl Hauser, August 7, 1985 6:05:01 pm PDT
Hauser, March 7, 1985 1:33:41 pm PST
DIRECTORY
AccessControl,
AccessControlCache,
AccessControlPrivate
USING[InternalAccessControlLogicError],
AlpineEnvironment
USING[AccessList, Principal, RName],
AlpineZones
USING[static],
Atom
USING[EmptyAtom, MakeAtom],
BasicTime
USING[earliestGMT, Now, Period],
GVNames
USING[IsMemberUpArrow],
RefTab
USING[Create, Delete, Fetch, Insert, RefTabRep],
SafeStorage
USING[GetSystemZone],
SkiPatrolLog
USING [notice, OpFailureInfo];
AccessControlCacheImpl:
CEDAR
MONITOR
IMPORTS
AC: AccessControl,
ACP: AccessControlPrivate,
AZ: AlpineZones, Atom, BasicTime,
GV: GVNames, RefTab, Rope, SafeStorage, SkiPatrolLog
EXPORTS AccessControlCache, AccessControl =
BEGIN OPEN AE: AlpineEnvironment;
emptyAtom: ATOM = Atom.EmptyAtom[];
cache: CacheEntryList ← NIL; -- points to mru entry.
CacheEntryList: TYPE = REF CacheEntry;
CacheEntry:
TYPE =
RECORD[
clientAtom: ATOM,
initTime: ACTime,
groupsMemberOf, groupsNotMemberOf: ACGroupsList,
next, prev: REF CacheEntry];
cacheTable: REF RefTab.RefTabRep ← NIL; -- to pass back and forth to RefTab.
ACTime:
TYPE =
LONG
CARDINAL;
-- seconds since epoch.
ExpirationTimeInterval: ACTime = 12*60*60; -- 12 hours, like Maxc.
RetryTimeInterval: ACTime = 30*60; -- After 30 minutes, retry "no" cache entries
ACGroupsList: TYPE = REF ACGroupsListEntry;
ACGroupsListEntry:
TYPE =
RECORD[
groupAtom: ATOM,
next: REF ACGroupsListEntry];
NCacheEntries: NAT ← 0;
CandidateGroupsList: TYPE = REF CandidateGroupEntry;
CandidateGroupEntry:
TYPE =
RECORD[name:
AE.RName, atom:
ATOM ← emptyAtom,
inList: CacheValue ← unknown, next, prev:
REF CandidateGroupEntry];
CacheValue: TYPE = {yes, no, unknown};
ACCacheZone: ZONE ← NIL;
RefTabError: ERROR = CODE; -- fatal.
VerifyClient:
PUBLIC
PROCEDURE[client:
AE.Principal, accessLists:
AE.AccessList]
RETURNS [okay:
BOOLEAN] =
BEGIN -- non system-fatal errors: AC.OperationFailed[regServersUnavailable].
clientAtom: ATOM;
candidateGroupsList: CandidateGroupsList;
nGrapeNotAuth: INT;
cacheEntryExpired, regServersDown: BOOLEAN;
cacheOkay: CacheValue;
[cacheOkay, clientAtom, candidateGroupsList, cacheEntryExpired] ←
MonitoredVerifyClientInCache[client, accessLists];
IF cacheOkay # unknown
THEN {
Break circular links
candidateGroupsList.next ← candidateGroupsList.prev ← NIL;
RETURN[cacheOkay = yes];
};
[okay, regServersDown, nGrapeNotAuth] ←
TryGrapevine[client, candidateGroupsList, cacheEntryExpired];
MonitoredUpdateCache[clientAtom, candidateGroupsList, okay, regServersDown,
nGrapeNotAuth];
Break circular links
candidateGroupsList.next ← candidateGroupsList.prev ← NIL;
IF regServersDown
THEN {
logProc: PROC [SkiPatrolLog.OpFailureInfo];
IF (logProc ← SkiPatrolLog.notice.operationFailed) #
NIL
THEN
logProc[[
what: regServersUnavailable,
where: "AccessControlCacheImpl.VerifyClient",
message: Rope.Concat["Couldn't verify access lists for ", client]
]];
ERROR AC.OperationFailed[regServersUnavailable];
};
END;
MonitoredVerifyClientInCache:
ENTRY
PROCEDURE[client:
AE.Principal, accessLists:
AE.AccessList] RETURNS [okay: CacheValue, clientAtom: ATOM, candidateGroupsList:
CandidateGroupsList, cacheEntryExpired:
BOOLEAN] =
BEGIN -- non system-fatal errors: none.
refCacheEntry: REF CacheEntry;
clientAtom ← Atom.MakeAtom[client];
refCacheEntry ←
NARROW[RefTab.Fetch[cacheTable, clientAtom].val,
REF CacheEntry];
candidateGroupsList ← SetUpCandidateGroups[accessLists];
IF refCacheEntry =
NIL
THEN
BEGIN
okay ← unknown;
cacheEntryExpired ← TRUE;
END
ELSE
BEGIN
-- look in "cache entry".
cacheEntryExpired ← ACTimeExpired[refCacheEntry.initTime];
IF (okay ← SearchCache[refCacheEntry, candidateGroupsList,
cacheEntryExpired]) # unknown
THEN statsCacheHits ← statsCacheHits + 1
ELSE OrderListForGrapevine[candidateGroupsList];
END;
END;
SetUpCandidateGroups:
INTERNAL
PROCEDURE[accessLists:
AE.AccessList]
RETURNS[candidateGroupsList: CandidateGroupsList] =
BEGIN -- non system-fatal errors: none.
candidateGroupsList ← ACCacheZone.
NEW[CandidateGroupEntry ←
["", emptyAtom, unknown, NIL, NIL]];
candidateGroupsList.next ← candidateGroupsList.prev ← candidateGroupsList;
FOR list:
AE.AccessList ← accessLists, list.rest
UNTIL list =
NIL
DO
candidateGroup:
REF CandidateGroupEntry ←
ACCacheZone.NEW[CandidateGroupEntry ← [list.first, emptyAtom,
unknown, candidateGroupsList, candidateGroupsList.prev]];
candidateGroupsList.prev.next ← candidateGroup;
candidateGroupsList.prev ← candidateGroup;
ENDLOOP;
END;
SearchCache:
INTERNAL
PROCEDURE[refCacheEntry:
REF CacheEntry, candidateGroupsList:
CandidateGroupsList, cacheEntryExpired:
BOOLEAN]
RETURNS [okay: CacheValue] =
BEGIN -- non system-fatal errors: none.
candidateGroup: REF CandidateGroupEntry ← candidateGroupsList.next;
groupsMemberOf: ACGroupsList ← refCacheEntry.groupsMemberOf;
groupsNotMemberOf: ACGroupsList;
MakeCacheEntryMru[refCacheEntry];
DO
IF candidateGroup = candidateGroupsList THEN EXIT;
candidateGroup.atom ← Atom.MakeAtom[candidateGroup.name];
IF InCacheGroupList[candidateGroup.atom, groupsMemberOf]
THEN
BEGIN
IF NOT cacheEntryExpired THEN RETURN[yes];
candidateGroup.inList ← yes;
END;
candidateGroup ← candidateGroup.next;
ENDLOOP;
groupsNotMemberOf ← refCacheEntry.groupsNotMemberOf;
candidateGroup ← candidateGroupsList.next;
okay ← no;
DO
IF candidateGroup = candidateGroupsList THEN EXIT;
IF candidateGroup.inList # yes
THEN {
candidateGroup.inList ←
(IF InCacheGroupList[candidateGroup.atom, groupsNotMemberOf] THEN no ELSE unknown);
IF candidateGroup.inList = unknown THEN okay ← unknown;
};
candidateGroup ← candidateGroup.next;
ENDLOOP;
RETURN[IF ACRetryPeriodExpired[refCacheEntry.initTime] THEN unknown ELSE okay];
END;
puts the list in the order: yes, unknown, no.
OrderListForGrapevine:
INTERNAL
PROCEDURE[candidateGroupsList: CandidateGroupsList]
=
BEGIN -- non system-fatal errors: none.
candidateGroup: REF CandidateGroupEntry ← candidateGroupsList.next;
nextCandidateGroup: REF CandidateGroupEntry;
betweenUnkAndNoGroups: REF CandidateGroupEntry;
DO
IF candidateGroup = candidateGroupsList THEN RETURN;
IF candidateGroup.inList # yes THEN EXIT;
candidateGroup ← candidateGroup.next;
ENDLOOP;
betweenUnkAndNoGroups ← candidateGroup;
DO
IF candidateGroup = candidateGroupsList THEN EXIT;
nextCandidateGroup ← candidateGroup.next;
SELECT candidateGroup.inList
FROM
yes, unknown =>
BEGIN
IF (candidateGroup.inList = unknown)
AND
(candidateGroup = betweenUnkAndNoGroups)
THEN betweenUnkAndNoGroups ← candidateGroup.next
ELSE
BEGIN
newFollower:
REF CandidateGroupEntry ←
(
IF candidateGroup.inList = yes
THEN candidateGroupsList.next
ELSE betweenUnkAndNoGroups);
IF betweenUnkAndNoGroups = candidateGroup
THEN betweenUnkAndNoGroups ← candidateGroup.next;
candidateGroup.next.prev ← candidateGroup.prev;
candidateGroup.prev.next ← candidateGroup.next;
candidateGroup.next ← newFollower;
candidateGroup.prev ← newFollower.prev;
newFollower.prev.next ← candidateGroup;
newFollower.prev ← candidateGroup;
END;
END;
ENDCASE => NULL;
candidateGroup ← nextCandidateGroup;
ENDLOOP;
END;
we're here because either the cache entry expired (or didn't exist) or else all the candidate groups were unk or no.
TryGrapevine:
PROCEDURE[client:
AE.Principal, candidateGroupsList:
CandidateGroupsList, cacheEntryExpired:
BOOLEAN]
RETURNS[okay, regServersDown:
BOOLEAN, nGrapeNotAuth:
INT] =
BEGIN -- non system-fatal errors: none.
candidateGroup: REF CandidateGroupEntry ← candidateGroupsList.next;
okay ← regServersDown ← FALSE;
nGrapeNotAuth ← 0;
DO
newState: CacheValue;
IF candidateGroup = candidateGroupsList THEN EXIT;
SELECT (
GV.IsMemberUpArrow[name: candidateGroup.name, member: client])
FROM
yes => newState ← yes;
no, notGroup => BEGIN newState ← no; nGrapeNotAuth ← nGrapeNotAuth + 1; END;
ENDCASE => GOTO regServersDown;
IF ((
NOT cacheEntryExpired)
AND (candidateGroup.inList = no)
AND
(newState = no))
THEN
BEGIN
-- save update cache routine some work.
candidateGroup.prev.next ← candidateGroup.next;
candidateGroup.next.prev ← candidateGroup.prev;
END
ELSE
BEGIN
IF candidateGroup.atom = emptyAtom
THEN candidateGroup.atom ← Atom.MakeAtom[candidateGroup.name];
IF (candidateGroup.inList ← newState) = yes
THEN
BEGIN
okay ← TRUE;
candidateGroup.next ← candidateGroupsList; -- dump stuff not updated.
RETURN;
END;
END;
candidateGroup ← candidateGroup.next;
REPEAT
regServersDown =>
BEGIN
lastUpdatedCandidateGroup:
REF CandidateGroupEntry ←
candidateGroup.prev;
IF cacheEntryExpired
THEN
BEGIN
-- use old data.
candidateGroup ← candidateGroupsList.next;
DO
IF candidateGroup = candidateGroupsList THEN EXIT;
IF candidateGroup.inList = yes
THEN BEGIN okay ← TRUE; EXIT; END;
candidateGroup ← candidateGroup.next;
ENDLOOP;
END;
lastUpdatedCandidateGroup.next ← candidateGroupsList;
regServersDown ← TRUE;
END;
ENDLOOP;
END;
MonitoredUpdateCache:
ENTRY
PROCEDURE[clientAtom:
ATOM, candidateGroupsList:
CandidateGroupsList, okay, regServersDown:
BOOLEAN, nGrapeNotAuth:
INT] =
BEGIN -- non system-fatal errors: none.
candidateGroup: REF CandidateGroupEntry;
refCacheEntry: REF CacheEntry;
cacheEntryHasEmptyGroupLists: BOOLEAN;
member: BOOLEAN;
SELECT
TRUE
FROM
regServersDown => statsRegSrvrsDown ← statsRegSrvrsDown + 1;
okay => statsGrapeAuthorized ← statsGrapeAuthorized + 1;
ENDCASE => statsGrapeNotAuthorized ← statsGrapeNotAuthorized + 1;
statsIndividualGrapeNotAuthorized ←
statsIndividualGrapeNotAuthorized + nGrapeNotAuth;
IF (candidateGroup ← candidateGroupsList.next) = candidateGroupsList
THEN RETURN;
refCacheEntry ←
NARROW[RefTab.Fetch[cacheTable, clientAtom].val,
REF CacheEntry];
cacheEntryHasEmptyGroupLists ← (refCacheEntry = NIL);
IF refCacheEntry =
NIL
THEN refCacheEntry ← CreateCacheEntryAsMru[clientAtom]
ELSE
BEGIN
IF ACTimeExpired[refCacheEntry.initTime]
THEN
BEGIN ReInitializeCacheEntry[refCacheEntry];
cacheEntryHasEmptyGroupLists ← TRUE;
END;
END;
DO
IF candidateGroup = candidateGroupsList THEN EXIT;
IF ((candidateGroup.inList # yes)
AND (candidateGroup.inList # no))
THEN RETURN WITH ERROR ACP.InternalAccessControlLogicError;
member ← (candidateGroup.inList = yes);
IF (
NOT cacheEntryHasEmptyGroupLists)
THEN RemoveFromCacheGroupsList[candidateGroup.atom, refCacheEntry, member];
AddToCacheGroupsList[candidateGroup.atom, refCacheEntry, member];
candidateGroup ← candidateGroup.next;
ENDLOOP;
[] ← RefTab.Delete[cacheTable, clientAtom];
IF (
NOT RefTab.Insert[cacheTable, clientAtom, refCacheEntry])
THEN RETURN WITH ERROR RefTabError;
CreateCacheEntryAsMru:
INTERNAL
PROCEDURE[clientAtom:
ATOM]
RETURNS[refCacheEntry:
REF CacheEntry] =
BEGIN -- non system-fatal errors: none.
refCacheEntry ← cache.prev; -- get lru.
IF refCacheEntry.clientAtom # emptyAtom
THEN
IF (
NOT RefTab.Delete[cacheTable, refCacheEntry.clientAtom])
THEN RETURN WITH ERROR RefTabError;
refCacheEntry.clientAtom ← clientAtom;
ReInitializeCacheEntry[refCacheEntry];
MakeCacheEntryMru[refCacheEntry];
END;
ReInitializeCacheEntry:
INTERNAL
PROCEDURE[refCacheEntry:
REF
CacheEntry] =
BEGIN -- non system-fatal errors: none.
refCacheEntry.initTime ← ACCurrentTime[];
refCacheEntry.groupsMemberOf ← ACCacheZone.
NEW[ACGroupsListEntry ←
[emptyAtom, NIL]];
refCacheEntry.groupsMemberOf.next ← refCacheEntry.groupsMemberOf;
refCacheEntry.groupsNotMemberOf ← ACCacheZone.
NEW[ACGroupsListEntry ←
[emptyAtom, NIL]];
refCacheEntry.groupsNotMemberOf.next ← refCacheEntry.groupsNotMemberOf;
END;
MakeCacheEntryMru:
INTERNAL
PROCEDURE[refCacheEntry:
REF CacheEntry] =
BEGIN -- non system-fatal errors: none.
refCacheEntry.next.prev ← refCacheEntry.prev;
refCacheEntry.prev.next ← refCacheEntry.next;
refCacheEntry.next ← cache.next;
refCacheEntry.prev ← cache;
cache.next.prev ← refCacheEntry;
cache.next ← refCacheEntry;
END;
InCacheGroupList:
INTERNAL
PROCEDURE[candidateAtom:
ATOM, groups: ACGroupsList]
RETURNS[yes:
BOOLEAN] =
BEGIN -- non system-fatal errors: none.
tempGroup: REF ACGroupsListEntry ← groups.next;
DO
IF tempGroup = groups THEN RETURN[FALSE];
IF candidateAtom = tempGroup.groupAtom THEN RETURN[TRUE];
tempGroup ← tempGroup.next;
ENDLOOP;
END;
AddToCacheGroupsList:
INTERNAL
PROCEDURE[candidateAtom:
ATOM, refCacheEntry:
REF
CacheEntry, member:
BOOLEAN] =
BEGIN -- non system-fatal errors: none.
groups: ACGroupsList ← (
IF member
THEN refCacheEntry.groupsMemberOf
ELSE
refCacheEntry.groupsNotMemberOf);
tempGroup: REF ACGroupsListEntry ← groups.next;
DO
-- beware duplicates.
IF tempGroup = groups THEN EXIT;
IF tempGroup.groupAtom = candidateAtom THEN RETURN;
tempGroup ← tempGroup.next;
ENDLOOP;
tempGroup ← ACCacheZone.NEW[ACGroupsListEntry ← [candidateAtom, groups.next]];
groups.next ← tempGroup;
END;
it's okay if the candidateAtom is not in the list.
RemoveFromCacheGroupsList:
INTERNAL
PROCEDURE[candidateAtom:
ATOM, refCacheEntry:
REF CacheEntry, member:
BOOLEAN] =
BEGIN -- non system-fatal errors: none.
groups: ACGroupsList ← (
IF member
THEN refCacheEntry.groupsMemberOf
ELSE
refCacheEntry.groupsNotMemberOf);
prev: REF ACGroupsListEntry ← groups;
tempGroup: REF ACGroupsListEntry ← groups.next;
DO
IF tempGroup = groups THEN RETURN;
IF tempGroup.groupAtom = candidateAtom THEN EXIT;
prev ← tempGroup;
tempGroup ← tempGroup.next;
ENDLOOP;
prev.next ← tempGroup.next;
END;
ACTimeExpired:
INTERNAL
PROCEDURE[initTime: ACTime]
RETURNS[expired:
BOOL] =
BEGIN -- non system-fatal errors: none.
currentTime: ACTime = BasicTime.Period[from: BasicTime.earliestGMT, to: BasicTime.Now[]];
RETURN[(currentTime - initTime) >= ExpirationTimeInterval];
END;
ACRetryPeriodExpired:
INTERNAL
PROCEDURE[initTime: ACTime]
RETURNS[expired:
BOOL] =
BEGIN -- non system-fatal errors: none.
currentTime: ACTime = BasicTime.Period[from: BasicTime.earliestGMT, to: BasicTime.Now[]];
RETURN[(currentTime - initTime) >= RetryTimeInterval];
END;
ACCurrentTime:
INTERNAL
PROCEDURE
RETURNS[currentTime: ACTime] =
BEGIN -- non system-fatal errors: none.
RETURN[BasicTime.Period[from: BasicTime.earliestGMT, to: BasicTime.Now[]]];
END;
expects caller to have checked that nAccessCacheEntries is > 0.
SetAccessControlCacheInitialized:
PUBLIC
ENTRY
PROCEDURE[nAccessCacheEntries:
NAT] =
BEGIN -- non system-fatal errors: none.
IF nAccessCacheEntries = 0
THEN RETURN WITH ERROR ACP.InternalAccessControlLogicError;
ACCacheZone ← SafeStorage.GetSystemZone[];
cache ← AZ.static.NEW[CacheEntry ← [emptyAtom, , NIL, NIL, NIL, NIL]];
cache.next ← cache.prev ← cache;
FOR index:
NAT
IN [0..nAccessCacheEntries)
DO
cacheEntry:
REF CacheEntry ←
AZ.static.
NEW[CacheEntry ← [emptyAtom,
, NIL, NIL, cache, cache.prev]];
cache.prev.next ← cacheEntry;
cache.prev ← cacheEntry;
ENDLOOP;
NCacheEntries ← nAccessCacheEntries;
cacheTable ← RefTab.Create[101];
END;
ClearAccessControlCache:
PUBLIC
ENTRY
PROCEDURE =
BEGIN -- non system-fatal errors: none.
refCacheEntry: REF CacheEntry ← cache.next;
UNTIL refCacheEntry = cache
DO
IF refCacheEntry.clientAtom # emptyAtom
THEN
BEGIN [] ← RefTab.Delete[cacheTable, refCacheEntry.clientAtom];
refCacheEntry.clientAtom ← emptyAtom;
ReInitializeCacheEntry[refCacheEntry];
END;
refCacheEntry ← refCacheEntry.next;
ENDLOOP;
END;
statsCacheHits: INT ← 0;
statsGrapeAuthorized, statsGrapeNotAuthorized, statsRegSrvrsDown: INT ← 0;
statsIndividualGrapeNotAuthorized: INT ← 0;
ReportCacheStats:
PUBLIC
ENTRY
PROCEDURE
RETURNS [nCacheEntries:
NAT,
statsCacheHit, statsGrapevineAuthorized, statsGrapevineNotAuthorized,
statsRegServersDown, statsIndivGrapeNotAuthorized:
INT] =
BEGIN -- non system-fatal errors: none.
RETURN[NCacheEntries, statsCacheHits, statsGrapeAuthorized, statsGrapeNotAuthorized,
statsRegSrvrsDown, statsIndividualGrapeNotAuthorized];
END;
END.
Initial: Kolling: 19-Nov-81 19:30:50: module implementing the access cache, for AccessControl.
Edited on July 17, 1984 11:30:35 am PDT, by Kupfer
Add SkiPatrolLog probe.
changes to: AccessControlCacheImpl, VerifyClient
Edited on August 6, 1984 1:42:36 pm PDT, by Kupfer
Remove the possible race condition in SkiPatrolLog probes by assigning the PROC to a temporary variable.
changes to: VerifyClient
Carl Hauser, July 29, 1985 3:36:21 pm PDT
changes to: VerifyClient break circular links
Carl Hauser, August 7, 1985 4:56:54 pm PDT
Formatting cleanup
changes to: VerifyClient break more circular links, MonitoredVerifyClientInCache, SearchCache, ACTime, ACRetryPeriodExpired, ACCurrentTime