-- 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[];
      
      
 }..