-- Copyright (C) 1985  by Xerox Corporation. All rights reserved. 
-- FloppyImplPublicD.mesa (last edited by: EKN   on:   1-Feb-85  8:02:07)

DIRECTORY
   Environment USING [wordsPerPage],
   File USING [nullFile, Type],
   FileTypes USING [tUnassigned],
   Floppy USING [
     Density, Error, ErrorType, FileID, maxCharactersInLabel, nullFileID, Sides],
   FloppyChannel USING [Attributes, GetDeviceAttributes, GetHandle, SetContext],
   FloppyExtras USING [ExtrasError, ExtrasErrorType],
   FloppyFormat USING [
     badSpotSector, BadSpotSectors, ConvertPageCount, dataContext, FileListEntry,
     FileListSeal, FileListVersion, FloppySeal, FloppyVersion, ImplementedFileSize,
     MarkerPage, MarkerPageEntryType, MarkerPageVersion, MarkerSeal, maxBadSectors,
     minTrackZeroSectors, nullSector, Sector, SectorNine, TrackZero,
     trackZeroAddress, TrackZeroSector],
   FloppyImplInterface USING [
     AccessFloppy, Allocation, allocationsPerPage, CreateBuffer, DiskChanged,
     FileListType, FirstDataSector, IOError, IsDriveWriteProtected, ReadFloppy,
     ValidDrive, VolumeDesc, VolumeChanging, VolumeStable, volumeTable,
     WordsToPages],
   Runtime USING [CallDebugger],
   Space USING [Error, Interval, Map, nullInterval, PageCount, Unmap];

FloppyImplPublicD: MONITOR
   LOCKS volumeDesc USING volumeDesc: FloppyImplInterface.VolumeDesc
   IMPORTS Floppy, FloppyChannel, FloppyExtras, FloppyFormat, FloppyImplInterface,
     Runtime, Space
   EXPORTS FloppyExtras
   SHARES FloppyImplInterface =

  BEGIN

  -- PUBLIC ERRORs, SIGNALs and TYPEs

  -- Private constants, types, variables

  BugType: TYPE = {insufficientVM};
  Bug: PROCEDURE [bug: BugType] = {Runtime.CallDebugger["Insufficient VM"L]};
  --  When Bug moves from RuntimeInternal to SpecialRuntime, use the following
  --Bug: PROCEDURE [bug: BugType] = {RuntimeInternal.Bug[bug]};

  ScavengeProblemType: TYPE = {allocMapInconsistent, badPageTable, bootFile,
    duplicateFileID, duplicateFileList, fileList, fileListEntry,
    freeSpaceConflict, ioError, none, sectorNine};
  problem: ScavengeProblemType ¬ none;

  -- PUBLIC operations

  --FloppyExtras.--
  NewScavenge: PUBLIC PROCEDURE [drive: CARDINAL] RETURNS [okay: BOOLEAN] =
    BEGIN
    buffer: Space.Interval ¬ Space.nullInterval;
    type: Floppy.ErrorType;

    ScavengeInternal: ENTRY PROCEDURE [
      volumeDesc: FloppyImplInterface.VolumeDesc] =
      BEGIN

      Shutdown: PROCEDURE =
        BEGIN
        buffer.pointer ¬ Space.Unmap[buffer.pointer ! Space.Error => CONTINUE];
        IF volumeDesc.fileList ~= NIL THEN volumeDesc.fileList ¬
	  Space.Unmap[volumeDesc.fileList ! Space.Error => CONTINUE];
        IF volumeDesc.allocationMap ~= NIL THEN volumeDesc.allocationMap ¬
	  Space.Unmap[volumeDesc.allocationMap ! Space.Error => CONTINUE];
	END;

      BEGIN ENABLE
        BEGIN
        FloppyImplInterface.IOError => {problem ¬ ioError; GOTO notOK};
	Floppy.Error => {type ¬ error; GOTO floppyError}; --?????necessary????
	UNWIND => Shutdown[];
	END;
      trackZero: FloppyFormat.TrackZero;
      markerPage: LONG POINTER TO FloppyFormat.MarkerPage;
      requestedSize: Space.PageCount;
      sectorNine: LONG POINTER TO FloppyFormat.SectorNine;

      ValidMarkers: PROCEDURE [fileAddress: FloppyFormat.Sector,
        enclosee: FloppyFormat.MarkerPageEntryType,
        size: FloppyFormat.ImplementedFileSize,
	id: Floppy.FileID ¬ Floppy.nullFileID,
        type: File.Type ¬ FileTypes.tUnassigned]
        RETURNS [valid: BOOLEAN] =
        BEGIN
        FloppyImplInterface.ReadFloppy[
          volumeDesc: volumeDesc, buffer: markerPage, count: 1,
          address: fileAddress - 1];
        IF NOT ((markerPage.seal = FloppyFormat.MarkerSeal)
          AND (markerPage.version = FloppyFormat.MarkerPageVersion)
          AND (markerPage.next.length = size)) THEN GOTO failed;
        WITH mp: markerPage.next SELECT FROM
          free => IF enclosee ~= free THEN GOTO failed;
          file =>
            IF NOT ((enclosee = file) AND (mp.file = id) AND (mp.type = type))
	      THEN GOTO failed;
          fileList =>
            IF NOT
	      ((enclosee = fileList) AND (mp.file = id) AND (mp.type = type))
	      THEN GOTO failed;
          badSectors => IF enclosee ~= badSectors THEN GOTO failed;
	  ENDCASE => GOTO failed;
        FloppyImplInterface.ReadFloppy[
          volumeDesc: volumeDesc, buffer: markerPage, count: 1,
          address: fileAddress + size];
        IF NOT ((markerPage.seal = FloppyFormat.MarkerSeal)
          AND (markerPage.version = FloppyFormat.MarkerPageVersion)
          AND (markerPage.previous.length = size)) THEN GOTO failed;
        WITH mp: markerPage.previous SELECT FROM
          free => IF enclosee ~= free THEN GOTO failed;
          file =>
            IF ((enclosee ~= file) AND (mp.file = id) AND (mp.type = type))
	      THEN GOTO failed;
          fileList =>
            IF ((enclosee ~= fileList) AND (mp.file = id) AND (mp.type = type))
	      THEN GOTO failed;
          badSectors => IF enclosee ~= badSectors THEN GOTO failed;
          ENDCASE => GOTO failed;
        valid ¬ TRUE;
        EXITS failed => valid ¬ FALSE;
        END;  -- ValidMarkers

      --  Begin ScavengeInternal main code
      IF volumeDesc.open THEN
        RETURN WITH ERROR FloppyExtras.ExtrasError[volumeOpen];

      -- Get buffers and handle to access the floppy
      requestedSize ¬ 
        FloppyImplInterface.WordsToPages[(SIZE[FloppyFormat.TrackZeroSector] * 
	FloppyFormat.minTrackZeroSectors)] + 
        FloppyImplInterface.WordsToPages[SIZE[FloppyFormat.MarkerPage]];
      buffer ¬ FloppyImplInterface.CreateBuffer[requestedSize];
      IF requestedSize ~= buffer.count THEN Bug[insufficientVM];
      trackZero.BASE ¬ LOOPHOLE[buffer.pointer];
      markerPage ¬ LOOPHOLE[
        BASE[trackZero] +
        Environment.wordsPerPage * 
        (FloppyImplInterface.WordsToPages[FloppyFormat.minTrackZeroSectors *
	SIZE[FloppyFormat.TrackZeroSector]])];
      
      volumeDesc.fileList ¬ NIL;
      volumeDesc.allocationMap ¬ NIL;
      volumeDesc.handle ¬ FloppyChannel.GetHandle[drive];            
      IF (volumeDesc.writeProtected ¬
        FloppyImplInterface.IsDriveWriteProtected[volumeDesc])
          THEN RETURN WITH ERROR Floppy.Error[writeInhibited];

      -- Read track zero.  Validate contents, fill in our local database.
      -- (We can access fixed-format track0 before volumeDesc is complete.)
      FloppyImplInterface.AccessFloppy[
        volumeDesc, BASE[trackZero], FloppyFormat.trackZeroAddress,
        FloppyFormat.minTrackZeroSectors, read];

      -- Check SectorNine, continue filling in volumeDesc
      volumeDesc.sectorNine­ ¬ LOOPHOLE[trackZero[9]];
      sectorNine ¬ volumeDesc.sectorNine;
      IF FloppyChannel.SetContext[volumeDesc.handle, FloppyFormat.dataContext[single]] AND
        FloppyChannel.GetDeviceAttributes[volumeDesc.handle].maxSectorsPerTrack = sectorNine.sectorsPerTrack
	  THEN volumeDesc.density ¬ single
      ELSE IF FloppyChannel.SetContext[volumeDesc.handle, FloppyFormat.dataContext[double]] AND
        FloppyChannel.GetDeviceAttributes[volumeDesc.handle].maxSectorsPerTrack = sectorNine.sectorsPerTrack
	  THEN volumeDesc.density ¬ double
      ELSE {problem ¬ sectorNine; GOTO notOK};
      
      SELECT sectorNine.tracksPerCylinder FROM
        1 => volumeDesc.sides ¬ one;
        2 => volumeDesc.sides ¬ two;
        ENDCASE => {problem ¬ sectorNine; GOTO notOK};

      BEGIN
      attrib: FloppyChannel.Attributes ¬
        FloppyChannel.GetDeviceAttributes[volumeDesc.handle];
      IF NOT ((sectorNine.seal = FloppyFormat.FloppySeal)
	AND (sectorNine.version = FloppyFormat.FloppyVersion)
        AND (sectorNine.cylinders > 0)
        AND (sectorNine.cylinders = attrib.numberOfCylinders)
	AND (sectorNine.tracksPerCylinder = attrib.numberOfHeads)
        AND (sectorNine.sectorsPerTrack = attrib.maxSectorsPerTrack))
	THEN {problem ¬ sectorNine; GOTO notOK};
      volumeDesc.numPages ¬ sectorNine.sectorsPerTrack*
        sectorNine.tracksPerCylinder * sectorNine.cylinders;
      END;

      -- Check sector nine file list entries.
      IF NOT ((sectorNine.fileList ~= FloppyFormat.nullSector)
	AND (sectorNine.fileList < volumeDesc.numPages)
	AND (sectorNine.fileListID ~= Floppy.nullFileID)
	AND (sectorNine.fileListSize > 0))
	THEN {problem ¬ sectorNine; GOTO notOK};

      IF ~ValidMarkers[fileAddress: sectorNine.fileList, enclosee: fileList,
        size: sectorNine.fileListSize, id: sectorNine.fileListID,
        type: FloppyImplInterface.FileListType]
	THEN {problem ¬ fileList; GOTO notOK};

      -- Get file list itself, check
      volumeDesc.fileListSpace ¬
        FloppyImplInterface.CreateBuffer[sectorNine.fileListSize];
      volumeDesc.fileList ¬ volumeDesc.fileListSpace.pointer;
      FloppyImplInterface.ReadFloppy[
        volumeDesc, volumeDesc.fileList, sectorNine.fileList,
	sectorNine.fileListSize];
      IF NOT ((volumeDesc.fileList.seal = FloppyFormat.FileListSeal)
        AND (volumeDesc.fileList.version = FloppyFormat.FileListVersion)
        AND (volumeDesc.fileList.maxEntries > 0)
        AND (volumeDesc.fileList.maxEntries >= volumeDesc.fileList.count)
        AND (volumeDesc.fileList.count > 0))
        THEN {problem ¬ fileList; GOTO notOK};

      BEGIN
      fileListFound: BOOLEAN ¬ FALSE;
      highestID: Floppy.FileID ¬ Floppy.nullFileID;
      FOR i: CARDINAL IN [0..volumeDesc.fileList.count) DO
        file: FloppyFormat.FileListEntry = volumeDesc.fileList.files[i];
	IF NOT ((file.file ~= Floppy.nullFileID)
	  AND (file.location ~= FloppyFormat.nullSector)
	  AND (file.size > 0) AND (file.size <= volumeDesc.numPages))
	  THEN {problem ¬ fileListEntry; GOTO notOK};
	IF file.type = FloppyImplInterface.FileListType
	  THEN
	    {IF ~fileListFound THEN fileListFound ¬ TRUE
	      ELSE {problem ¬ duplicateFileList; GOTO notOK}}
	  ELSE IF ~ ValidMarkers[fileAddress: file.location, enclosee: file,
	    size: file.size, id: file.file, type: file.type]
	    THEN {problem ¬ fileListEntry; GOTO notOK};
	IF SmallerIDLargerID[highestID, file.file] THEN highestID ¬ file.file;
	FOR j: CARDINAL IN [0..volumeDesc.fileList.count - 1) DO
	  IF i = j THEN LOOP;
	  IF file.file = volumeDesc.fileList.files[j].file
	    THEN {problem ¬ duplicateFileID; GOTO notOK};
	  ENDLOOP;
	ENDLOOP;
      IF ~fileListFound THEN {problem ¬ fileList; GOTO notOK};
      IF sectorNine.nextUnusedFileID <= LOOPHOLE[highestID, LONG CARDINAL]
        THEN {problem ¬ sectorNine; GOTO notOK};
      -- For level 1 scavenger, nextUnusedFileID is guaranteed to be > last
      -- actual ID in file list, but it may be > last ID + 1.
      -- Level 2: reset nextUnusedFileID if ~= highestID + 1
      END;  -- check file list and related
      -- Level 2: if file list not sorted correctly (see PPM), rewrite sorted

      -- Check root file
      IF (~NullID[sectorNine.rootFile]
	AND (sectorNine.nextUnusedFileID <=
	  LOOPHOLE[sectorNine.rootFile, LONG CARDINAL]))
	THEN {problem ¬ fileList; GOTO notOK};
      -- ?? check at advertised loc only if ID > lastIDAllocated

      -- Check boot files: ensure advertised sector is in a file in the file list.
      -- Not necessary to check file itself because check file list did that.
      IF sectorNine.pilotMicrocode ~= FloppyFormat.nullSector THEN
        {IF ~BootFileInFileList[volumeDesc, sectorNine.pilotMicrocode]
	  THEN {problem ¬ bootFile; GOTO notOK}};
      IF sectorNine.diagnosticMicrocode ~= FloppyFormat.nullSector
        THEN {IF ~BootFileInFileList[
	  volumeDesc, sectorNine.diagnosticMicrocode]
	  THEN {problem ¬ bootFile; GOTO notOK}};
      IF sectorNine.germ ~= FloppyFormat.nullSector THEN
        {IF ~BootFileInFileList[volumeDesc, sectorNine.germ]
	  THEN {problem ¬ bootFile; GOTO notOK}};
      IF sectorNine.pilotBootFile ~= FloppyFormat.nullSector THEN
        {IF ~BootFileInFileList[volumeDesc, sectorNine.pilotBootFile]
	  THEN {problem ¬ bootFile; GOTO notOK}};

      IF NOT ((sectorNine.firstAlternateSector < volumeDesc.numPages)
        AND (sectorNine.countBadSectors < FloppyFormat.maxBadSectors)
        AND (sectorNine.labelSize <= Floppy.maxCharactersInLabel))
        THEN {problem ¬ sectorNine; GOTO notOK};
      -- End check sector nine

      -- Check bad spot table
      BEGIN
      track0Map: LONG POINTER TO FloppyFormat.BadSpotSectors ¬
        LOOPHOLE[BASE[trackZero] +
	  (FloppyFormat.badSpotSector-1)*SIZE[FloppyFormat.TrackZeroSector]];
      FOR i: CARDINAL IN [0..FloppyFormat.maxBadSectors) DO
        volumeDesc.badPageMap[i] ¬ track0Map[i];
	ENDLOOP;
      END;
      FOR i: CARDINAL IN [0..sectorNine.countBadSectors) DO
        IF NOT ((volumeDesc.badPageMap[i].bad ~= FloppyFormat.nullSector)
	  AND (volumeDesc.badPageMap[i].bad < volumeDesc.numPages)
	  AND (volumeDesc.badPageMap[i].bad ~= volumeDesc.badPageMap[i].alternate)
	  AND (volumeDesc.badPageMap[i].alternate ~= FloppyFormat.nullSector)
	  AND (volumeDesc.badPageMap[i].alternate < volumeDesc.numPages))
	  THEN {problem ¬ badPageTable; GOTO notOK};
	-- check page has valid markers or other bad page adjacent
	-- check sorted?
	ENDLOOP;
      -- End check bad spot table

      -- Cross check file list, bad spot table, and standard overhead sectors
      -- for overlap by building an allocation map.
      BEGIN
      -- This calculation is flakey so allocate an extra page for safety
      size: CARDINAL ¬ 1 + FloppyImplInterface.WordsToPages[
        (volumeDesc.numPages + FloppyImplInterface.allocationsPerPage - 1)/
          FloppyImplInterface.allocationsPerPage];
      volumeDesc.allocationMapSpace ¬ Space.Map[[File.nullFile, 0, size]]; 
      -- We should really catch the signals and convert them into something else
      volumeDesc.allocationMap ¬ volumeDesc.allocationMapSpace.pointer;
      IF ~BuildAllocationMap[
	volumeDesc: volumeDesc,
	map: volumeDesc.allocationMapSpace.pointer].consistent
          THEN {problem ¬ allocMapInconsistent; GOTO notOK};
      END;  -- build and check allocation map

      -- Check that chunks the allocation map thinks are free, i.e., not used by
      -- files, bad pages, or file system structures, are well formed free spaces
      -- on the disk.
      BEGIN
      first: FloppyFormat.Sector;
      next: FloppyFormat.Sector ¬
        FloppyImplInterface.FirstDataSector[volumeDesc];
      map: LONG POINTER TO PACKED ARRAY [0..0) OF FloppyImplInterface.Allocation
        ¬ volumeDesc.allocationMapSpace.pointer;
      DO
	FOR first ¬ next, first + 1 UNTIL first > volumeDesc.numPages DO
	  IF map[first] = free THEN EXIT;
	  REPEAT
	  FINISHED => GOTO allDone;
	  ENDLOOP;
	FOR next ¬ first + 1, next + 1 UNTIL next > volumeDesc.numPages DO
	  IF map[next] ~= free THEN EXIT;
	  REPEAT
	  FINISHED => {problem ¬ freeSpaceConflict; GOTO notOK};
	  ENDLOOP;
	IF ~ValidMarkers[fileAddress: first, enclosee: free, size: next-first]
	  THEN {problem ¬ freeSpaceConflict; GOTO notOK};
	REPEAT
	  allDone => NULL;
	ENDLOOP;
      END;  -- check free spaces

      -- Check, correct if wrong once file system verified (but not error)
      --   check track 0 sectors contents
      --   0..8, 10 specified in FloppyFormat
      --   11..26 are like 10
      --   check track 1 sectors contents

       FloppyImplInterface.VolumeStable[volumeDesc];
       Shutdown[];
       EXITS
         floppyError => {Shutdown[]; RETURN WITH ERROR Floppy.Error[type]};
         notOK =>
	   BEGIN
	   FloppyImplInterface.VolumeChanging[volumeDesc];
	   Shutdown[];
	   okay ¬ FALSE;
	   END;
       END;  -- scope of ENABLE
       END;  -- ScavengerInternal

     -- BEGIN Scavenge main code
     BEGIN ENABLE UNWIND => NULL;
     IF ~FloppyImplInterface.ValidDrive[drive] THEN
       ERROR Floppy.Error[noSuchDrive];
     okay ¬ TRUE;
     ScavengeInternal[FloppyImplInterface.volumeTable[drive]
       ! FloppyImplInterface.DiskChanged => RETRY];
     END;  -- scope of ENABLE
     END;  -- Scavenge

  BootFileInFileList: PROCEDURE [
    volumeDesc: FloppyImplInterface.VolumeDesc, page: FloppyFormat.Sector]
    RETURNS [BOOLEAN] =
    BEGIN
    FOR i: CARDINAL IN [0..volumeDesc.fileList.count) DO
      IF page IN [volumeDesc.fileList.files[i].location..
        volumeDesc.fileList.files[i].location+volumeDesc.fileList.files[i].size)
        THEN RETURN[TRUE];
      ENDLOOP;
    RETURN[FALSE];
    END;

  BuildAllocationMap: PROCEDURE [
    volumeDesc: FloppyImplInterface.VolumeDesc,
    map: LONG POINTER TO PACKED ARRAY [0..0) OF FloppyImplInterface.Allocation]
    RETURNS [consistent: BOOLEAN] =
    BEGIN
    -- This is almost exactly the same as
    -- FloppyImplPrivate.InitializeAllocationMap.  Volume is not open (thus not
    -- closed) and it doesn't quit as soon as it finds an inconsistency.
    -- InitializeEtc. could be modified to use this for stuff they have in common.

    -- Start clean
    FOR i: CARDINAL IN [0..FloppyFormat.ConvertPageCount[volumeDesc.numPages]] DO
      map[i] ¬ free;
      ENDLOOP;
    consistent ¬ TRUE;

    -- Mark first and last pages of disk as marker pages. If they are actually
    -- bad, loop over the bad page list below will take care of it.
    map[FloppyImplInterface.FirstDataSector[volumeDesc]] ¬ markerPage;
    map[FloppyFormat.ConvertPageCount[volumeDesc.numPages]] ¬ markerPage;

    -- Mark bad page list: bad pages and markers around them
    FOR i: CARDINAL IN [0..volumeDesc.sectorNine.countBadSectors) DO
      map[volumeDesc.badPageMap[i].bad] ¬ badPage;
      IF map[volumeDesc.badPageMap[i].bad-1] = free THEN
        map[volumeDesc.badPageMap[i].bad-1] ¬ markerPage;
      IF map[volumeDesc.badPageMap[i].bad+1] = free THEN
        map[volumeDesc.badPageMap[i].bad+1] ¬ markerPage;
      ENDLOOP;

    -- Mark Sector 0 and cylinder 0 allocated
    FOR i: CARDINAL IN [0..FloppyImplInterface.FirstDataSector[volumeDesc]) DO
      map[i] ¬ allocated;
      ENDLOOP;

    -- Mark marker pages and contents pages for all files in the File list
    FOR i: CARDINAL IN [0..volumeDesc.fileList.count) DO
      file: FloppyFormat.FileListEntry = volumeDesc.fileList.files[i];
      IF ~(map[file.location-1] = free OR map[file.location-1] = markerPage)
        THEN consistent ¬ FALSE ELSE map[file.location-1] ¬ markerPage;
      IF ~(map[file.location + file.size] = free OR
        map[file.location + file.size] = markerPage)
        THEN consistent ¬ FALSE ELSE map[file.location+file.size] ¬ markerPage;
      FOR j: CARDINAL IN [file.location..file.location + file.size) DO
	IF map[j] ~= free THEN consistent ¬ FALSE ELSE map[j] ¬ allocated;
	ENDLOOP;
      ENDLOOP;

    END;  -- BuildAllocationMap

  NullID: PROCEDURE [file: Floppy.FileID] RETURNS [BOOLEAN] = INLINE
    {RETURN[LOOPHOLE[file, LONG CARDINAL]
      = LOOPHOLE[Floppy.nullFileID, LONG CARDINAL]]};

  SmallerIDLargerID: PROCEDURE [idA, idB: Floppy.FileID] RETURNS [BOOLEAN] =
    INLINE
    {RETURN[LOOPHOLE[idA, LONG CARDINAL] < LOOPHOLE[idB, LONG CARDINAL]]};

  END.




LOG

13-Nov-84 15:42:58	CAJ 	Created file.
 1-Feb-85  8:02:15	EKN  	Removed uses of FloppyFormat.dataSectorsPerTrack. Fixed up uses of FloppyFormat.TrackZero. Fixed arrows.