Cedar Nucleus: Layout of permanent disk data structures for File interface
VolumeFormat.mesa
Last Edited by: Andrew Birrell September 19, 1983 9:43 am
Last Edited by: Levin, June 28, 1983 4:04 pm
DIRECTORY
BootFile USING[ DiskFileID, nullLink ],
DiskFace USING[ PageCount, PageNumber, wordsPerPage ],
File USING[ FileID, FP, nullFileID, nullFP, PageNumber, VolumeFile, VolumeID ],
PhysicalVolume USING[ LogicalPage, LogicalPageCount, TimeParameters];
VolumeFormat: CEDAR DEFINITIONS =
BEGIN
-- ******** Concrete types for abstract fields of DiskFace.Label ******** --
Attributes: TYPE = MACHINE DEPENDENT {
These are compatible with Rubicon Pilot file types
physicalRoot(1), -- physical volume root page
badPageList(2), -- ?
badPage(3),
subVolumeMarker(4), -- physical volume marker pages
logicalRoot(5), -- logical volume root page
Cedar file types reserved in Klamath Pilot file type space are [9728D..9984D)
freePage(9728), -- label of a truly free page in a logical volume
header(9729), -- for file run-table and properties
data(9730), -- for file data pages
lastCedar(9984),
(LAST[CARDINAL])
};
AbsID: TYPE = RECORD[File.VolumeID];
Used in Physical/Logical marker and root pages, and in free pages.
RelID: TYPE = RECORD[File.FP];
Used in all pages of a file.
-- ******** Physical Root Page ******** --
PRSeal: CARDINAL = 121212B; -- word zero of a valid physical volume root page
PRCurrentVersion: CARDINAL = 6;
PhysicalRoot: TYPE = MACHINE DEPENDENT RECORD [
seal(0): CARDINAL ← PRSeal, -- must be 1st field
version(1): CARDINAL ← PRCurrentVersion, -- must be 2nd field
labelLength(2): CARDINAL [0..volumeLabelLength) ← 0,
pvID(3): File.VolumeID,
bootingInfo(10B): ARRAY PVBootFile OF BootFile.DiskFileID ← ALL[nullDiskFileID],
"bootingInfo" be at this offset as the microcode knows where to find it.
label(54B): PACKED ARRAY [0..volumeLabelLength) OF CHARACTER ← nullLabel | NULL,
subVolumeCount(100B): [0..maxSubVols),
subVolumeMarkerID(101B): AbsID ← NULL,
badPageCount(106B): DiskFace.PageCount ← 0,
maxBadPages(110B): DiskFace.PageCount ← allocatedBadPages,
onLineCount(112B): CARDINAL ← 0, -- TEMPORARILY unused.
subVolumes(113B): ARRAY [0..maxSubVols) OF SubVolumeDesc,
fill1(231B): ARRAY [0..374B - 231B) OF WORD ← ALL[0], -- fill to whole page
timeParametersValid(374B): BOOL ← FALSE,
timeParameters(375B): TimeParameters ← NULL,
checksum(377B): CARDINAL ← 0 -- MUST be the last field of this page
];
PVBootFile: TYPE = File.VolumeFile[checkpoint..bootFile];
maxSubVols: CARDINAL [4..7] = 6;
maximum subvolumes on a physical volume. Because the subVolumes array is just before the Fill area in the Descriptor, it is possible to increment this field so that the subVOlumes array effectively grows into the Fill area.
SubVolumeDesc: TYPE = MACHINE DEPENDENT RECORD [
lvID(0): File.VolumeID,
lvSize(5): LogicalPageCount,
lvPage(7): LogicalPage,
pvPage(11B): DiskFace.PageNumber,
nPages(13B): LogicalPageCount
];
rootPageNumber: DiskFace.PageNumber = [0];
credentialsPageNumber: DiskFace.PageNumber = [2];
volumeLabelLength: CARDINAL = 40;
nullLabel: PACKED ARRAY [0..volumeLabelLength) OF CHARACTER = ALL[0C];
TimeParameters: TYPE = PhysicalVolume.TimeParameters;
Opaque at this level. Concrete type is only interesting to Time software.
LogicalPage: TYPE = PhysicalVolume.LogicalPage;
-- Page number relative to a logical volume --
LogicalPageCount: TYPE = PhysicalVolume.LogicalPageCount;
nullDiskFileID: BootFile.DiskFileID =
[fID: [rel[LOOPHOLE[File.nullFP]]], firstPage: 0, firstLink: BootFile.nullLink];
-- ******** Physical volume bad page list ******** --
BadPageList: TYPE = ARRAY [0..allocatedBadPages) OF DiskFace.PageNumber;
The bad page is on physical page following PhysicalRoot.
allocatedBadPages: CARDINAL = DiskFace.wordsPerPage/SIZE[DiskFace.PageNumber];
current maximum number of bad pages permitted on a volume.
nullBadPage: DiskFace.PageNumber = rootPageNumber;
-- ******** Logical volume root page ******** --
LRSeal: CARDINAL = 131313B;
LRCurrentVersion: CARDINAL = 5;
LogicalRoot: TYPE = MACHINE DEPENDENT RECORD [
seal (0): CARDINAL ← LRSeal,
version (1): CARDINAL ← LRCurrentVersion,
vID (2): File.VolumeID,
labelLength (7): CARDINAL[0..volumeLabelLength) ← 0,
label (10B): PACKED ARRAY [0..volumeLabelLength) OF CHARACTER ← nullLabel,
type (34B): VolumeType ← cedar,
volumeSize (35B): LogicalPageCount,
bootingInfo (37B): ARRAY LVBootFile OF BootFile.DiskFileID ← ALL[nullDiskFileID],
Above here is pilot-compatible
rootFile (125B): ARRAY File.VolumeFile OF RootFile ← ALL[],
fill (265B): ARRAY [265B..374B) OF CARDINAL ← ALL[0],
coCedar(374B): BOOL ← FALSE,
lastFileID(375B): File.FileID ← File.nullFileID,
checksum (377B): CARDINAL ← 0
];
LVBootFile: TYPE = File.VolumeFile[checkpoint..debuggee];
RootFile: TYPE = MACHINE DEPENDENT RECORD[
fp(0): File.FP ← File.nullFP,
page(4): File.PageNumber ← [0]
];
VolumeType: TYPE = MACHINE DEPENDENT {
pilot(0),
pilotDebugger(1),
pilotDebuggerDebugger(2),
cedar(3)
};
-- ******** Physical volume marker pages ******** --
The subvolume end marker page marks the end of each subvolume on a physical volume and contains non-reconstructable information from both the physical (following) and logical volume root pages, and a checksum.
PSMSeal: CARDINAL = 141414B; -- word zero of a valid subvolume end marker page
PSMCurrentVersion: CARDINAL = 0;
PhysicalMarker: TYPE = MACHINE DEPENDENT RECORD [
seal(0): CARDINAL ← PSMSeal, -- must be 1st field
version(1): CARDINAL ← PSMCurrentVersion, -- must be 2nd field
Information (mainly) describing the physical volume:
pvID(2): File.VolumeID,
label(7): PACKED ARRAY [0..volumeLabelLength) OF CHARACTER ← nullLabel,
bootingInfo(33B): ARRAY PVBootFile OF BootFile.DiskFileID ← ALL[nullDiskFileID],
maxBadPages(77B): DiskFace.PageCount, -- size of bad page table
labelLength(101B:0..5): CARDINAL [0..volumeLabelLength) ← 0,
Information describing the preceding subvolume:
fill(101B:6..12): [0..128) ← 0,
svNumber(101B:13..15): [0..maxSubVols), -- ordinal number of preceding subvolume
descriptor(102B): SubVolumeDesc -- copy of descriptor for preceding subvolume
];
-- ******** Logical volume end marker ******** --
The subvolume end marker page marks the end of each subvolume on a physical volume and contains non-reconstructable information from both the physical and logical (following) volume root pages, and a checksum.
LSMSeal: CARDINAL = 151515B;
LSMCurrentVersion: CARDINAL = 0;
LogicalSubvolumeMarker: TYPE = MACHINE DEPENDENT RECORD [
seal (0): CARDINAL ← LSMSeal,
version (1): CARDINAL ← LSMCurrentVersion,
labelLength (2:0..5): CARDINAL [0..volumeLabelLength) ← 0,
type (2:6..7): VolumeType ← cedar,
coCedar (2:8..8): BOOL ← FALSE,
pad (2:9..15): [0..128) ← 0,
label (3): PACKED ARRAY [0..volumeLabelLength) OF CHARACTER ← nullLabel,
bootingInfo (27B): ARRAY LVBootFile OF BootFile.DiskFileID ← ALL[nullDiskFileID]
, clientRootFile (115B): File.Capability ← File.nullCapability
];
-- ******** Volume Allocation Map ******** --
The VAM is a ordinary file, pointed to from the volume root page. It is a bitmap indexed by logical volume page number, indicating for each page whether the page is in use. The bitmap is always generous: every free page is marked free in the bitmap, but some pages so marked may not be free. The truth about whether a page is free is in the page's label.
VAMObject: TYPE = MACHINE DEPENDENT RECORD[
Representation is messy, because we can't have an array index beyond LAST[CARDINAL
rover(0): LogicalPage,
size(2): LogicalPageCount,
used(vamChunkPos): SEQUENCE COMPUTED CARDINAL OF VAMChunk
];
VAMChunk: TYPE = PACKED ARRAY CARDINAL OF BOOL;
vamChunkPos: CARDINAL = 4;
-- ******** Disk Run Table ******** --
Each file has a run table, representing the pages of the file. This is a hint: the actual pages of a file are some initial subset of the pages described by its run-table.
LogicalRunObject: TYPE = MACHINE DEPENDENT RECORD[
headerPages(0): CARDINAL,
maxRuns(1): CARDINAL,
intention(2): RunTableIntention,
runs(5): SEQUENCE COMPUTED CARDINAL OF LogicalRun
];
RunTableIntention: TYPE = MACHINE DEPENDENT RECORD[
unstable(0:0..0): BOOL ← FALSE,
spare(0:1..15): [0..77777B) ← 0,
size(1): INT ← 0 -- delete if < 0
];
LogicalRun: TYPE = MACHINE DEPENDENT RECORD[
first(0): LogicalPage,
size(2): RunPageCount
];
lastLogicalRun: LogicalPage = [LAST[INT]]; -- end marker in LogicalRunObject --
RunPageCount: TYPE = CARDINAL; -- not INT, to maximise packing of run-tables on disk
END.