-- AccessControlCacheImpl.mesa
-- Last edited by
-- Kolling on June 10, 1983 12:50 pm
-- MBrown on January 30, 1984 2:57:34 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];


AccessControlCacheImpl: CEDAR MONITOR
IMPORTS AC: AccessControl, ACP: AccessControlPrivate, AZ: AlpineZones, Atom, BasicTime,
GV: GVNames, RefTab, SafeStorage
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.
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;
[okay, clientAtom, candidateGroupsList, cacheEntryExpired] ←
MonitoredVerifyClientInCache[client, accessLists];
IF okay THEN RETURN[TRUE];
[okay, regServersDown, nGrapeNotAuth] ←
TryGrapevine[client, candidateGroupsList, cacheEntryExpired];
MonitoredUpdateCache[clientAtom, candidateGroupsList, okay, regServersDown,
nGrapeNotAuth];
IF regServersDown THEN ERROR AC.OperationFailed[regServersUnavailable];
END;



MonitoredVerifyClientInCache: ENTRY PROCEDURE[client: AE.Principal, accessLists:
AE.AccessList] RETURNS [okay: BOOLEAN, 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 ← FALSE;
cacheEntryExpired ← TRUE;
END
ELSE BEGIN -- look in "cache entry".
cacheEntryExpired ← ACTimeExpired[refCacheEntry.initTime];
IF (okay ← SearchCache[refCacheEntry, candidateGroupsList,
cacheEntryExpired])
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: BOOLEAN] =
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[TRUE];
candidateGroup.inList ← yes;
END;
candidateGroup ← candidateGroup.next;
ENDLOOP;
groupsNotMemberOf ← refCacheEntry.groupsNotMemberOf;
candidateGroup ← candidateGroupsList.next;
DO
IF candidateGroup = candidateGroupsList THEN EXIT;
IF candidateGroup.inList # yes THEN candidateGroup.inList ←
(IF InCacheGroupList[candidateGroup.atom, groupsNotMemberOf]
THEN no ELSE unknown);
candidateGroup ← candidateGroup.next;
ENDLOOP;
RETURN[FALSE];
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;
END;


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;


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.

Edit Log

Initial: Kolling: 19-Nov-81 19:30:50: module implementing the access cache, for AccessControl.