-- lsdimpl.mesa
-- Implementation of the Local System Directory component of the
-- Interim Cedar File System.
-- Mike Schroeder September 23, 1982 3:19 pm
DIRECTORY
ConvertUnsafe: TYPE USING [AppendRope],
DCSFileTypes: TYPE USING [tLeaderPage],
Directory: TYPE USING [LookupUnlimited, Error, CreateFile],
File: TYPE USING [Capability],
Environment: TYPE USING [wordsPerPage],
Rope: TYPE USING [ROPE, Size, Fetch],
RopeInline: TYPE USING [Lower],
Inline: TYPE USING [LowHalf, BITXOR, BITOR, BITSHIFT],
LSD,
Space: TYPE USING [Create, Handle, ForceOut, Map, LongPointer, virtualMemory,
WindowOrigin, CreateUniformSwapUnits],
System: TYPE USING [GetGreenwichMeanTime];
LSDImpl: MONITOR
IMPORTS ConvertUnsafe, Directory, Inline, Space, System, Rope, RopeInline
EXPORTS LSD = {
-- base of the LSD in memory (it is always mapped)
base: LSD.Base ← NIL;
-- data type for internal link mainipulation
LinkP: TYPE = LONG POINTER TO LSD.Link;
-- Global data strucutres (volatile)
-- DEATH TO THE MDS!!
global: REF Global ← NIL;
maxLocks: CARDINAL = 1000;
Global: TYPE = RECORD [
lsdSize: LONG CARDINAL,
fc: File.Capability,
sh: Space.Handle,
used: CARDINAL ← 0,
lockTable: SEQUENCE max: CARDINAL OF LockEntry
];
LockEntry: TYPE = RECORD [
entry: LSD.Entry,
-- lock is -1 for exclusive, 0 for free entry, n for n readers
lock: INTEGER
];
ClearDirty: PUBLIC ENTRY PROC[entry: LSD.Entry] = {
-- Marks an entry as clean.
-- If the entry was not dirty ClearDirty is a nop.
IF entry.dirtyF THEN {
Unlink[@entry.dirty];
entry.dirtyF ← FALSE;
};
WriteOutLSD[];
};
Create: PUBLIC ENTRY PROC[name: Rope.ROPE, fc: File.Capability, create: LONG CARDINAL]
RETURNS [entry: LSD.Entry] = {
-- Creates an entry in the LSD, links it into the hash chain,
-- and makes it MRU. The new entry is locked in exclusive mode.
-- If an entry already existed under name, it will be updated
-- with the new information
length: CARDINAL;
entry ← LookupInternal[name];
IF entry=NIL THEN {
-- not in the LSD. Let's add it.
length ← Inline.LowHalf[Rope.Size[name]];
entry ← AllocateEntry[SIZE[LSD.EntryObject]+(length+1)/2];
-- if LSD is full, return an error indication
IF entry=NIL THEN RETURN[NIL];
-- set maxLength of name
LOOPHOLE[@entry.name+1, LONG POINTER TO CARDINAL]↑ ← length;
entry.name.length ← 0;
ConvertUnsafe.AppendRope[to: @entry.name, from: name];
Link[to: @base.hash[ComputeHash[name]], node: @entry.hash];
[] ← LockInternal[entry, TRUE];
entry.dirtyF ← entry.free ← FALSE;
} ELSE {
-- if already in LSD, see if we can lock it.
[] ← LockInternal[entry, TRUE];
-- unlink from mru list (so we can make it MRU)
Unlink[@entry.mru];
};
entry.create ← create;
entry.checked ← System.GetGreenwichMeanTime[];
entry.fc ← fc;
Link[to: @base.mruChain, node: @entry.mru];
WriteOutLSD[];
RETURN[entry];
};
Delete: PUBLIC ENTRY PROC[entry: LSD.Entry] = {
-- Deletes an entry in the LSD. Any locks are released.
relp: LSD.LPtr;
coalesce: BOOLEAN;
-- if we already deleted the entry, then return
IF entry.free THEN RETURN;
-- Unlink entry and mark it free
Unlink[node: @entry.mru];
Unlink[node: @entry.hash];
IF entry.dirtyF THEN Unlink[node: @entry.dirty];
UnlockInternal[entry];
entry.free ← TRUE;
Link[to: @base.freeChain, node: @entry.hash];
-- now coalesce free entries at the end of the LSD
-- if the entry we deleted was at the end of the LSD
coalesce ← ((entry-LOOPHOLE[base, LSD.Entry])+entry.size)=base.freePointer;
WHILE coalesce DO
coalesce ← FALSE;
-- unlink from free chain
Unlink[node: @entry.hash];
-- move back free pointer
base.freePointer ← base.freePointer - entry.size;
-- now see if the last entry in the LSD is on the free chain
-- if so, then move free space pointer back
FOR relp ← base.freeChain.next, base[relp].next
UNTIL relp = LSD.freeHeadOffset DO
entry ← LOOPHOLE[@base[relp] - LSD.hashOffset, LSD.Entry];
IF ((entry-LOOPHOLE[base, LSD.Entry])+entry.size)=base.freePointer
THEN {
-- coalesce entry
coalesce ← TRUE;
EXIT;
};
ENDLOOP;
ENDLOOP; -- coalesce loop --
-- write out new LSD
WriteOutLSD[];
};
Enumerate: PUBLIC ENTRY PROC[p: LSD.EProc] = {
-- Enumerates entries in MRU order.
relp: LSD.LPtr;
entry: LSD.Entry;
FOR relp ← base.mruChain.next, base[relp].next
UNTIL relp=LSD.mruHeadOffset DO
entry ← LOOPHOLE[@base[relp] - LSD.mruOffset, LSD.Entry];
IF p[entry ! UNWIND => NULL] THEN EXIT;
ENDLOOP;
};
EnumerateLocked: PUBLIC ENTRY PROC[p: LSD.EProc] = {
-- Enumerates all locked LSD entries
ln: CARDINAL;
FOR ln IN [1..global.used] DO
-- for each used lock, call p
IF global[ln].lock#0 THEN {
IF p[global[ln].entry] THEN EXIT;
};
ENDLOOP;
};
GetDirty: PUBLIC ENTRY PROC
RETURNS [dirty: LSD.Entry] = {
-- Returns a dirty entry.
-- The returned entry is locked in exclusive mode.
-- If no dirty entry is found, NIL is returned.
relp: LSD.LPtr;
entry: LSD.Entry;
FOR relp ← base.dirtyChain.next, base[relp].next
UNTIL relp=LSD.dirtyHeadOffset DO
entry ← LOOPHOLE[@base[relp] - LSD.dirtyOffset, LSD.Entry];
IF LockInternal[entry, TRUE] THEN RETURN [entry];
ENDLOOP;
RETURN[NIL];
};
GetVictim: PUBLIC ENTRY PROC
RETURNS [victim: LSD.Entry] = {
-- Returns the LRU entry that is eligible for replacement.
-- The returned entry is locked in exclusive mode.
-- If no victim is found, NIL is returned.
relp: LSD.LPtr;
entry: LSD.Entry;
FOR relp ← base.mruChain.last, base[relp].last
UNTIL relp=LSD.mruHeadOffset DO
entry ← LOOPHOLE[@base[relp] - LSD.mruOffset, LSD.Entry];
IF NOT entry.dirtyF THEN {
IF LockInternal[entry, TRUE] THEN RETURN [entry];
};
ENDLOOP;
RETURN[NIL];
};
Lock: PUBLIC ENTRY PROC[entry: LSD.Entry, exclusive: BOOLEAN]
RETURNS [success: BOOLEAN] = {
-- Locks an LSD entry in share or exclusive mode.
-- Returns T if it was able to set the requested lock.
RETURN[LockInternal[entry, exclusive]];
};
Lookup: PUBLIC ENTRY PROC[name: Rope.ROPE]
RETURNS [entry: LSD.Entry] = {
-- Looks up an entry in the LSD by name. No lock is set.
-- Returns NIL if there is no entry with the specified name.
-- If entry is found, it is made MRU
entry ← LookupInternal[name];
IF entry#NIL THEN -- make this emtry mru --
BEGIN
Unlink[@entry.mru];
Link[to:@base.mruChain, node:@entry.mru];
WriteOutLSD[]
END;
};
SetDirty: PUBLIC ENTRY PROC[entry: LSD.Entry] = {
-- Marks an entry dirty.
IF NOT entry.dirtyF THEN {
Link[to: @base.dirtyChain, node: @entry.dirty];
entry.dirtyF ← TRUE;
};
WriteOutLSD[];
};
Unlock: PUBLIC ENTRY PROC[entry: LSD.Entry] = {
-- Clears the lock set on an entry.
-- If entry is not locked, Unlock is a nop.
UnlockInternal[entry];
};
UnlockAll: PUBLIC ENTRY PROC = {
-- Sledge hammer to unlock everything
global.used ← 0;
};
-- Internal procedures
AllocateEntry: INTERNAL PROC [size: CARDINAL]
RETURNS [entry: LSD.Entry] = {
-- allocate a new entry
-- first, see if we can find one on the free chain
relp: LSD.LPtr;
FOR relp ← base.freeChain.next, base[relp].next
UNTIL relp = LSD.freeHeadOffset DO
entry ← LOOPHOLE[@base[relp] - LSD.hashOffset, LSD.Entry];
IF size <= entry.size THEN {
Unlink[node: @entry.hash];
RETURN[entry];
};
ENDLOOP;
-- nothing on the free list for us
-- if we would overflow, return NIL
IF base.freePointer + size > global.lsdSize THEN RETURN[NIL];
entry ← LOOPHOLE[base.freePointer+base];
entry.size ← size;
base.freePointer ← base.freePointer + size;
RETURN[entry];
};
CompareName: PROC [e: LSD.Entry, name: Rope.ROPE]
RETURNS [m: BOOLEAN] = {
i: LONG INTEGER;
sname: LONG STRING = @e.name;
length: LONG INTEGER = Rope.Size[name];
IF Inline.LowHalf[length]#sname.length THEN RETURN[FALSE];
FOR i IN [0..length) DO
IF RopeInline.Lower[sname[i]]
#RopeInline.Lower[Rope.Fetch[name, i]] THEN RETURN[FALSE];
ENDLOOP;
RETURN[TRUE];
};
ComputeHash: PROC [s: Rope.ROPE]
RETURNS [hash: CARDINAL] = {
-- compute a hash function of s
i: LONG INTEGER;
length: LONG INTEGER = Rope.Size[s];
hash ← 0;
FOR i ← 0, i + 2 UNTIL i >= length
DO
-- Leo suggests doing a rotate first
hash ← Inline.BITOR[Inline.BITSHIFT[hash, 1], Inline.BITSHIFT[hash, -15]];
hash ← Inline.BITXOR[Inline.BITSHIFT[RopeInline.Lower[Rope.Fetch[s, i]], 8], hash];
IF i+1 < length THEN hash ← Inline.BITXOR[RopeInline.Lower[Rope.Fetch[s, i+1]], hash];
ENDLOOP;
-- now have 16 bit hash. reduce to number of buckets
hash ← hash MOD LSD.buckets;
RETURN[hash];
};
Link: INTERNAL PROC [to: LinkP, node: LinkP] = {
-- link a node into the list specified by to
-- first, generate relative pointers
rto: LSD.LPtr = LOOPHOLE[
LOOPHOLE[to, LONG ORDERED POINTER] -
LOOPHOLE[base, LONG ORDERED POINTER]];
rnode: LSD.LPtr = LOOPHOLE[
LOOPHOLE[node, LONG ORDERED POINTER] -
LOOPHOLE[ base, LONG ORDERED POINTER]];
-- now link in
node.next ← to.next;
node.last ← rto;
base[to.next].last ← rnode;
to.next ← rnode;
};
Unlink: INTERNAL PROC [node: LinkP] = {
-- unlink a node
base[node.next].last ← node.last;
base[node.last].next ← node.next;
};
LockInternal: INTERNAL PROC [entry: LSD.Entry, exclusive: BOOLEAN]
RETURNS [success: BOOLEAN] = {
ln: CARDINAL ← LookupLock[entry];
IF ln=0 THEN {
-- lock not found. create new lock entry
FOR ln IN [1..global.used] DO
-- see if there is a free entry
IF global.lockTable[ln].lock = 0 THEN {
global.lockTable[ln].entry ← entry;
global.lockTable[ln].lock ← IF exclusive THEN -1 ELSE 1;
RETURN[TRUE];
};
ENDLOOP;
-- no free entry. create a new one
-- if out of lock space, deny lock
IF (global.used + 1) >= maxLocks THEN RETURN[FALSE];
global.used ← global.used + 1;
global.lockTable[global.used].entry ← entry;
global.lockTable[global.used].lock ← IF exclusive THEN -1 ELSE 1;
RETURN[TRUE];
};
-- lock found.
-- if we want exclusive access, we can't set the lock.
IF exclusive THEN RETURN[FALSE];
-- if already exclusive, we can't set the lock
IF global.lockTable[ln].lock < 0 THEN RETURN[FALSE];
-- increment number of share locks
global.lockTable[ln].lock ← global.lockTable[ln].lock + 1;
RETURN[TRUE];
};
LookupLock: INTERNAL PROC [entry: LSD.Entry]
RETURNS [ln: CARDINAL] = {
-- lookup a lock. if not found, return 0
i: CARDINAL;
FOR i IN [1..global.used] DO
IF global.lockTable[i].entry=entry THEN RETURN[i];
ENDLOOP;
RETURN[0];
};
LookupInternal: INTERNAL PROC [name: Rope.ROPE]
RETURNS [entry: LSD.Entry] = {
-- lookup an entry in the lsd
class: CARDINAL ← ComputeHash[name];
relp: LSD.LPtr;
finish: LSD.LPtr = LOOPHOLE[
LOOPHOLE[@base.hash[class], LONG ORDERED POINTER] -
LOOPHOLE[base, LONG ORDERED POINTER]];
FOR relp ← base.hash[class].next, base[relp].next
UNTIL relp = finish DO
entry ← LOOPHOLE[@base[relp] - LSD.hashOffset];
IF CompareName[entry, name] THEN RETURN;
ENDLOOP;
entry ← NIL;
};
UnlockInternal: INTERNAL PROC [entry: LSD.Entry] = {
-- unlock a lock
ln: CARDINAL ← LookupLock[entry];
IF ln = 0 THEN RETURN;
IF global.lockTable[ln].lock > 0 THEN
{global.lockTable[ln].lock ← global.lockTable[ln].lock - 1}
ELSE
{global.lockTable[ln].lock ← 0};
-- if no lock left, clear entry
IF global.lockTable[ln].lock = 0 THEN global.lockTable[ln].entry ← NIL;
};
WriteOutLSD: PROC = {
-- write out the LSD
Space.ForceOut[global.sh];
};
-- Initialization
Init: PROC = {
InitLink: PROC [lp: LinkP] = {
-- procedure to intialize a link field to be empty
self: LSD.LPtr = LOOPHOLE[
LOOPHOLE[lp, LONG ORDERED POINTER] -
LOOPHOLE[base, LONG ORDERED POINTER]];
lp.next ← lp.last ← self;
};
found: BOOLEAN ← TRUE;
i: CARDINAL;
-- allocate storage
global ← NEW[Global[maxLocks]];
-- lookup the lsd. eventually it will be the volume root file
global.fc ← Directory.LookupUnlimited[fileName: "lsd.dir"L
! Directory.Error => {found ← FALSE; CONTINUE}];
-- if not found, create a file
IF NOT found THEN global.fc ← Directory.CreateFile[
fileName: "lsd.dir"L,
fileType: DCSFileTypes.tLeaderPage,
size: LSD.maxSize];
-- create a space to hold the lsd
-- this must be large enough to hold the largest lsd
global.sh ← Space.Create[size: LSD.maxSize, parent: Space.virtualMemory];
Space.Map[space: global.sh, window: Space.WindowOrigin[file: global.fc, base: 1]];
-- swap in lsd one page at a time
Space.CreateUniformSwapUnits[parent: global.sh];
base ← Space.LongPointer[global.sh];
global.lsdSize ← LONG[LSD.maxSize] * LONG[Environment.wordsPerPage];
-- if necessary, initialize the LSD
IF (NOT found) OR (base.version # LSD.headerVersion) THEN {
-- intialize LSD
base.version ← LSD.headerVersion;
InitLink[@base.mruChain];
InitLink[@base.freeChain];
InitLink[@base.dirtyChain];
-- pointer to free space past header
base.freePointer ← SIZE[LSD.LSDHeader];
FOR i IN [0..LSD.buckets) DO InitLink[@base.hash[i]] ENDLOOP;
WriteOutLSD[];
};
};
-- Start trap does the trick
Init[];
}..