(FILECREATED "11-Mar-85 17:41:02" {ERIS}<LISP>INTERMEZZO>SOURCES>LFALLOCATIONMAP.;2 17093
changes to: (VARS LFALLOCATIONMAPCOMS)
previous date: "16-Feb-85 18:32:01" {ERIS}<LISP>INTERMEZZO>SOURCES>LFALLOCATIONMAP.;1)
(* Copyright (c) 1985 by Xerox Corporation. All rights reserved.)
(PRETTYCOMPRINT LFALLOCATIONMAPCOMS)
(RPAQQ LFALLOCATIONMAPCOMS ((* * Implements the 1108 file system volume file map. Very roughly
translates {idun}<apilot100>pilot>private>volAllocMapImpl.mesa, but
omits a number of dubious optimizations.)
(* * Needed improvement 1: restructure so that low-level part of
allocation is done a PageGroup at a time. That would (a)
allow bitmap searching to be done somewhat faster
(by just shifting a mask and comparing, rather than creating a new
mask each time)
and
(b)
more importantly allow disk accesses to be done a PageGroup at a time,
once DISKDLION gets updated to allow quick page run access)
(* * Needed improvement 2: Check old labels before allocating or
deallocating a page, and abort & tell user to scavenge if the label is
wrong.)
(* * Needed improvement 3: Restructure interface with FILEIO so that a
page can be allocated and written in one fell swoop. MFile/Pilot have
a special interface for this.)
[DECLARE: EVAL@COMPILE DONTCOPY (COMS (FILES (LOADCOMP)
LFPILOTFILE)
(FILES DECL)
(CONSTANTS (BITSPERPAGE 4096]
(DECLARE: (LOCALVARS . T)
(IGNOREDECL . T))
(* * Public routines)
(FNS \VAMAllocPageGroup \VAMFreePageGroup \VAMInit
\VAMRecomputeFreePageCount)
(* * Private routines:)
(FNS \VAMFilePageNumber \VAMAllocPage \VAMUpdateVAM \VAMFreePage
\VAMAdjustGroup)
(RESOURCES \DFSVAMpage)
(GLOBALVARS \VAMmonitor)
[INITVARS (\VAMmonitor (CREATE.MONITORLOCK (QUOTE VAMmonitor]
(* * buffer management)
(FNS \VAMGetVAMPageFor \VAMBufferInit \VAMBufferSave \VAMMarkBufferDirty)
(GLOBALVARS \VAMbuffer \VAMbufferVolume \VAMbufferVolumePage
\VAMbufferDirty)
(* * Initialize VAM)
(P (\VAMInit))))
(* * Implements the 1108 file system volume file map. Very roughly translates
{idun}<apilot100>pilot>private>volAllocMapImpl.mesa, but omits a number of dubious
optimizations.)
(* * Needed improvement 1: restructure so that low-level part of allocation is done a PageGroup
at a time. That would (a) allow bitmap searching to be done somewhat faster (by just shifting
a mask and comparing, rather than creating a new mask each time) and (b) more importantly allow
disk accesses to be done a PageGroup at a time, once DISKDLION gets updated to allow quick
page run access)
(* * Needed improvement 2: Check old labels before allocating or deallocating a page, and abort
& tell user to scavenge if the label is wrong.)
(* * Needed improvement 3: Restructure interface with FILEIO so that a page can be allocated
and written in one fell swoop. MFile/Pilot have a special interface for this.)
(DECLARE: EVAL@COMPILE DONTCOPY
(FILESLOAD (LOADCOMP)
LFPILOTFILE)
(FILESLOAD DECL)
(DECLARE: EVAL@COMPILE
(RPAQQ BITSPERPAGE 4096)
(CONSTANTS (BITSPERPAGE 4096))
)
)
(DECLARE:
(DECLARE: DOEVAL@COMPILE DONTCOPY
(LOCALVARS . T)
)
(DECLARE: DOEVAL@COMPILE DONTEVAL@LOAD DONTCOPY
(RESETSAVE COMPILEIGNOREDECL (QUOTE T))
)
)
(* * Public routines)
(DEFINEQ
(\VAMAllocPageGroup
[DLAMBDA ((vol LogicalVolumeDescriptor)
(filePtr FileDescriptor)
(groupPtr PageGroup)
(RETURNS NIL))
(* hts: "16-Feb-85 18:26")
(* * Allocates as many of the pages in groupPtr as it can in a contiguous run. Modifies groupPtr so the caller can
know what pages and how many were allocated)
[WITH.MONITOR \VAMmonitor
(UNINTERRUPTABLY
(PROG ((volPage# (fetch (LogicalVolumeDescriptor lowerBound) of vol))
(filePage# (fetch (PageGroup filePage) of groupPtr))
allocated)
(* * Find first free page and allocate it. lowerBound is supposed to be the first free page on the volume)
(until (PROGN [if (IGEQ volPage# (SUB1 (fetch (LogicalVolumeDescriptor
volumeSize)
of vol)))
then (DiskError "FILE SYSTEM RESOURCES EXCEEDED"
(PACKFILENAME.STRING
(QUOTE HOST)
(QUOTE DSK)
(QUOTE DIRECTORY)
(U-CASE (fetch (
LogicalVolumeDescriptor LVlabel) of vol]
(\VAMAllocPage vol volPage# filePtr
(\VAMFilePageNumber (fetch (FileDescriptor
type)
of filePtr)
volPage# filePage#)))
do (add volPage# 1))
(* * Note in groupPtr the beginning page of the run we will allocate to this file)
(replace (PageGroup volumePage) of groupPtr with volPage#)
(* * Keep allocating until either you run out of consecutive free pages or you've allocated enough)
[repeatuntil (PROGN (add volPage# 1)
(add filePage# 1)
[if (IGEQ volPage# (SUB1 (fetch (
LogicalVolumeDescriptor volumeSize) of vol)))
then (DiskError
"FILE SYSTEM RESOURCES EXCEEDED"
(PACKFILENAME.STRING
(QUOTE HOST)
(QUOTE DSK)
(QUOTE DIRECTORY)
(U-CASE (fetch (LogicalVolumeDescriptor
LVlabel)
of vol]
(OR (EQP filePage# (fetch (PageGroup nextFilePage)
of groupPtr))
(NOT (\VAMAllocPage vol volPage# filePtr
(\VAMFilePageNumber
(fetch (FileDescriptor
type)
of filePtr)
volPage# filePage#]
(SETQ allocated (IDIFFERENCE volPage# (fetch (PageGroup volumePage)
of groupPtr)))
(* * Note in the PageGroup what the last page allocated actually was, so the caller will know)
(replace (PageGroup nextFilePage) of groupPtr
with (IPLUS (fetch (PageGroup filePage) of groupPtr)
allocated))
(* * Update free page count and lower bound on the logical volume page)
(add (fetch (LogicalVolumeDescriptor freePageCount) of vol)
(MINUS allocated))
(replace (LogicalVolumeDescriptor lowerBound) of vol with volPage#)))]])
(\VAMFreePageGroup
[DLAMBDA ((vol LogicalVolumeDescriptor)
(filePtr FileDescriptor)
(groupPtr PageGroup)
(RETURNS NIL))
(* hts: "16-Feb-85 18:27")
(* * Frees each page in groupPtr)
[WITH.MONITOR \VAMmonitor (UNINTERRUPTABLY
[PROG ((group (\VAMAdjustGroup groupPtr)))
(* Adjust to coincide with Pilot's silly "[0, 0)"
convention)
(if (IGEQ (fetch (PageGroup filePage) of group)
(fetch (PageGroup nextFilePage) of group))
then (RETURN))
(* * Free up the pages you're supposed to)
(for filePageNumber from (fetch (PageGroup filePage)
of group)
to (SUB1 (fetch (PageGroup nextFilePage) of group))
as volumePageNumber from (fetch (PageGroup volumePage)
of group)
do (\VAMFreePage vol volumePageNumber filePtr
(\VAMFilePageNumber (fetch (FileDescriptor
type)
of filePtr)
volumePageNumber
filePageNumber)))
(* * Update free page count and lower bound on the logical volume page)
(add (fetch (LogicalVolumeDescriptor freePageCount)
of vol)
(IDIFFERENCE (fetch (PageGroup nextFilePage)
of group)
(fetch (PageGroup filePage) of group)))
(replace (LogicalVolumeDescriptor lowerBound) of vol
with (MIN (fetch (PageGroup volumePage) of group)
(fetch (LogicalVolumeDescriptor lowerBound)
of vol])]])
(\VAMInit
[LAMBDA NIL (* hts: " 5-Jan-85 16:18")
(* * Initializes or reinitializes the volume allocation map)
(WITH.MONITOR \VAMmonitor (\VAMBufferInit])
(\VAMRecomputeFreePageCount
[DLAMBDA ((vol LogicalVolumeDescriptor)
(RETURNS FIXP))
(* hts: " 9-Jan-85 17:37")
(* * Recomputes the free page count for each volume from scratch; also resets the lower bound pointer)
(WITH.MONITOR \VAMmonitor [replace (LogicalVolumeDescriptor freePageCount) of vol
with (bind (firstFree ← T) for page from 1
to (fetch (LogicalVolumeDescriptor volumeSize) of vol)
count (PROG [(free (ZEROP (\VAMUpdateVAM vol NIL page
(QUOTE read]
(if (AND free firstFree)
then (replace (LogicalVolumeDescriptor
lowerBound)
of vol with page)
(SETQ firstFree NIL))
(RETURN free]
(\PFPutLogicalVolumePage vol vol)
(fetch (LogicalVolumeDescriptor freePageCount) of vol))])
)
(* * Private routines:)
(DEFINEQ
(\VAMFilePageNumber
[DLAMBDA ((fileType SMALLP)
(volumePageNumber FIXP)
(filePageNumber FIXP)
(RETURNS FIXP))
(* hts: "16-Feb-85 16:21")
(* * Returns the real file page number)
(SELECTC fileType
(tLispFile filePageNumber)
(tLispDirectory filePageNumber)
(tVolumeFileMap volumePageNumber)
(tRootDirectory 0)
(tDiagnosticMicrocode filePageNumber)
(SHOULDNT))])
(\VAMAllocPage
[LAMBDA (vol volPage# filePtr filePage#) (* hts: " 5-Jan-85 16:17")
(* vol: LogicalVolumeDescriptor, filePtr:
FileDescriptor, page: FIXP)
(* * RETURNS T if successful at allocating page, otherwise NIL)
(if (ZEROP (\VAMUpdateVAM vol filePtr volPage# (QUOTE alloc)))
then (WITH-RESOURCE \DFSVAMpage
(* * Should really check label to make sure page was free. Put this in when DISKDLION gets rewritten to allow fast
access to runs of pages.)
(* * Write the fresh (zeroed) page with its new label. Again, this would be lots faster if it could be done a
PageGroup at a time when DISKDLION gets fixed. Further, for user files, it would be nice to write the write the
label and the data in one pass instead of two; Pilot provides a special interface to allow this)
(* * \DFSVAMpage is always full of zeroes, so this ensures each new page of a file will be clean.)
(\PFCreatePage filePtr filePage# volPage# \DFSVAMpage))
T
else NIL])
(\VAMUpdateVAM
[LAMBDA (vol filePtr page allocOrFree) (* hts: "16-Jan-85 21:08")
(* * vol: LogicalVolumeDescriptor, filePtr: FileDescriptor, page: FIXP, allocOrFree: {alloc, free})
(* * RETURNS previous value of allocation map for specified page)
(* * Sets (if allocOrFree = alloc) or clears (if allocOrFree = free) the map bit for the specified page)
(PROG ((VAMPage# (IQUOTIENT page BITSPERPAGE))
(VAMWord# (IQUOTIENT (IREMAINDER page BITSPERPAGE)
BITSPERWORD))
(VAMBit# (IREMAINDER page BITSPERWORD))
VAMPage VAMWord VAMBit result)
(SETQ VAMPage (\VAMGetVAMPageFor vol VAMPage#))
(SETQ VAMWord (\GETBASE VAMPage VAMWord#))
(SETQ VAMBit (MASK.1'S (DIFFERENCE 15 VAMBit#)
1))
(SETQ result (if (BITTEST VAMWord VAMBit)
then 1
else 0))
(SELECTQ allocOrFree
(alloc (SETQ VAMWord (BITSET VAMWord VAMBit))
(\VAMMarkBufferDirty))
(free (SETQ VAMWord (BITCLEAR VAMWord VAMBit))
(\VAMMarkBufferDirty))
(read)
(SHOULDNT))
(\PUTBASE VAMPage VAMWord# VAMWord)
(RETURN result])
(\VAMFreePage
[LAMBDA (vol volPageNumber filePtr filePageNumber) (* hts: " 5-Jan-85 16:17")
(* vol: LogicalVolumeDescriptor, filePtr:
FileDescriptor, page: FIXP)
(* * Frees the specified page)
(WITH-RESOURCE \DFSVAMpage
(* * Should really check label to make sure page was allocated to this file. Put this in when DISKDLION gets
rewritten to allow fast access to runs of pages.)
(* * Write a free page label on the page. Again, this would be faster if it could be done a PageGroup at a time once
DISKDLION gets fixed.)
(\PFCreateFreePage vol volPageNumber \DFSVAMpage))
(* * Mark the page as deallocated in the allocation map)
(\VAMUpdateVAM vol filePtr volPageNumber (QUOTE free))
NIL])
(\VAMAdjustGroup
[LAMBDA (groupPtr) (* hts: " 9-Jan-85 17:29")
(PROG ((group (create PageGroup using groupPtr)))
[if (EQ (fetch (PageGroup filePage) of group)
0)
then (if (EQ (fetch (PageGroup nextFilePage) of group)
0)
then (replace (PageGroup nextFilePage) of group with 1)
else (replace (PageGroup filePage) of group with 1)
(replace (PageGroup volumePage) of group with (ADD1 (fetch (PageGroup
volumePage)
of group]
(RETURN group])
)
(DECLARE: EVAL@COMPILE
[PUTDEF (QUOTE \DFSVAMpage)
(QUOTE RESOURCES)
(QUOTE (NEW (create Page]
)
(DECLARE: DOEVAL@COMPILE DONTCOPY
(GLOBALVARS \VAMmonitor)
)
(RPAQ? \VAMmonitor (CREATE.MONITORLOCK (QUOTE VAMmonitor)))
(* * buffer management)
(DEFINEQ
(\VAMGetVAMPageFor
[DLAMBDA ((vol LogicalVolumeDescriptor)
(VAMPage# SMALLP)
(RETURNS Page))
(* hts: "16-Jan-85 21:06")
(PROG ((volumePage (IPLUS (fetch (LogicalVolumeDescriptor vamStart) of vol)
VAMPage#)))
(if (AND (FIXP \VAMbufferVolumePage)
(EQ \VAMbufferVolume vol)
(EQP \VAMbufferVolumePage volumePage))
then
(* * If the desired VAM page is already read in, just return it)
(RETURN \VAMbuffer)
else
(* * Otherwise write out the old VAM page if there is one)
(\VAMBufferSave)
(UNINTERRUPTABLY
(* * Record what the new page is)
(SETQ \VAMbufferVolume vol)
(SETQ \VAMbufferVolumePage volumePage)
(* * and read it in)
(\PFGetAllocationMapPage \VAMbufferVolume \VAMbufferVolumePage \VAMbuffer))
(RETURN \VAMbuffer)))])
(\VAMBufferInit
[LAMBDA NIL (* hts: "16-Jan-85 21:04")
(* * if bufferVolumePage is NIL, GetVAMPageFor will not try to flush an old version of it)
(SETQ \VAMbuffer (create Page))
(SETQ \VAMbufferVolume)
(SETQ \VAMbufferVolumePage)
(SETQ \VAMbufferDirty NIL])
(\VAMBufferSave
[LAMBDA NIL (* hts: "16-Jan-85 21:03")
(* * Flush last VAM page used)
(if (AND (FIXP \VAMbufferVolumePage)
(the BOOL \VAMbufferDirty))
then (\PFPutAllocationMapPage \VAMbufferVolume \VAMbufferVolumePage \VAMbuffer)
(SETQ \VAMbufferDirty NIL])
(\VAMMarkBufferDirty
[LAMBDA NIL (* hts: "16-Jan-85 21:02")
(* * Indicate that the buffer VAM page is dirty and will have to be written out.)
(SETQ \VAMbufferDirty T)
NIL])
)
(DECLARE: DOEVAL@COMPILE DONTCOPY
(GLOBALVARS \VAMbuffer \VAMbufferVolume \VAMbufferVolumePage \VAMbufferDirty)
)
(* * Initialize VAM)
(\VAMInit)
(PUTPROPS LFALLOCATIONMAP COPYRIGHT ("Xerox Corporation" 1985))
(DECLARE: DONTCOPY
(FILEMAP (NIL (3560 9897 (\VAMAllocPageGroup 3570 . 6798) (\VAMFreePageGroup 6800 . 8671) (\VAMInit
8673 . 8908) (\VAMRecomputeFreePageCount 8910 . 9895)) (9928 14544 (\VAMFilePageNumber 9938 . 10468) (
\VAMAllocPage 10470 . 11664) (\VAMUpdateVAM 11666 . 12955) (\VAMFreePage 12957 . 13857) (
\VAMAdjustGroup 13859 . 14542)) (14802 16854 (\VAMGetVAMPageFor 14812 . 15844) (\VAMBufferInit 15846
. 16213) (\VAMBufferSave 16215 . 16592) (\VAMMarkBufferDirty 16594 . 16852)))))
STOP