Page Numbers: Yes First Page: 62 X: 527 Y: 10.5"
Margins: Binding: 13
Odd Heading: Not-on-first-page
Alto/Mesa Storage Management Facilities
Even Heading:
Alto/Mesa Storage Management Facilities
Alto/Mesa Storage Management Facilities
October 1980
Two collections of Mesa procedures are available for acquiring and managing storage areas. The segmentation machinery, which is described in detail elsewhere, provides contiguous groups of pages (256 word blocks) in the virtual memory. A simplified interface with that machinery is described below. There is also a Mesa free storage package for managing arbitrarily sized nodes within free storage zones. Since all state information is recorded within the zones themselves, the system-provided instantiation of the latter package can manage an arbitrary number of zones. There is one system-defined zone, called the free storage heap, available for general use; special procedures exist for creating and destroying nodes within it. The salient characteristics of these packages are summarized below.
The segmentation machinery is most suitable for obtaining large blocks of storage. All bookkeeping information associated with such blocks is recorded in auxiliary tables that are managed by the segmentation system, not in the blocks themselves. Allocating or releasing a segment involves searching and updating a number of those tables. On the other hand, any freed page becomes available for general use by the system (loading, buffering, etc.) and any two adjacent free pages can be coalesced to become part of a new segment.
The free storage package is a transliteration of a BCPL program by Ed McCreight that was itself based upon a suggestion by Don Knuth (The Art of Computer Programming, Volume 1, p. 453, #19). Within a zone, free nodes are kept as a linked list. One hidden word containing bookkeeping information is stored with each allocated node, and additional bookkeeping information is kept in the header of each zone. Allocation and release of nodes are usually very fast. Adjacent free nodes are always able to be coalesced. It is also possible to add new areas of storage to enlarge a zone. These new areas are linked together so that they may be deleted if all the nodes in an area are free; in addition, an entire zone may be deleted.
The free storage package performs best when the sizes of nodes are small compared to the sizes of the block(s) making up the zone. In particular, the system’s heap is intended to be used for small, transient data structures, such as the nodes of a temporary list structure or the bodies of (short) strings when the maximum length must be computed dynamically or the structure must outlive the frame that creates it. Use of the heap for large (i.e., multipage) nodes decreases flexibility in storage management, since the additional pages may become a permanent part of the zone.
The allocators in both packages return absolute pointers; allocated nodes are not relocatable and there is no garbage collection or automatic deallocation of any sort. Also, the values returned by the allocators are free pointers (type POINTER TO UNSPECIFIED) which must be cast appropriately (usually by assignment) before they can be used.
Segmentation Interface
The following definitions are contained in Storage.
Words: PROCEDURE [nwords: CARDINAL] RETURNS [base: POINTER];
Allocates a segment of virtual memory containing at least nwords words and returns the address of the first word in that segment. Words provides a simple interface to MakeDataSegment, described in the Segment chapter of this document. The procedure Words assumes the segment will have a reasonably long lifetime; therefore, it uses an AllocInfo that assures that unlocked read-only file segments are pushed out of the way when the segment is allocated.
Such segments are returned to the system by
FreeWords: PROCEDURE [base: POINTER];
For uses in which the page structure is already known, the following procedures are also provided.
Pages: PROCEDURE [npages: CARDINAL] RETURNS [base: POINTER];
This procedure also assumes a relatively long lifetime for the allocated storage.
PagesForWords: PROCEDURE [nwords: CARDINAL] RETURNS [npages: CARDINAL];
FreePages: PROCEDURE [base: POINTER];
FreePagesNil: PROCEDURE [base: POINTER] RETURNS [nil: POINTER];
Always returns NIL. Use it to avoid dangling references.
Any storage obtained using Pages is guaranteed to begin on a page boundary.
The above functions are a subset of the most useful ones contained in the old interace SystemDefs. Since existing programs may use SystemDefs, the procedures are documented below.
AllocateSegment: PROCEDURE [nwords: CARDINAL] RETURNS [base: POINTER];
Like Storage.Words, except that it doesn’t try to move unlocked file segments out of the way.
AllocateResidentSegment: PROCEDURE [nwords: CARDINAL] RETURNS [base: POINTER];
The same as Storage.Words.
SegmentSize: PROCEDURE [base: POINTER] RETURNS [nwords: CARDINAL];
Returns the number of words actually obtained in the segment.
FreeSegment: PROCEDURE [base: POINTER];
The same as Storage.FreeWords.
AllocatePages: PROCEDURE [npages: CARDINAL] RETURNS [base: POINTER];
Like Storage.Pages, except that it doesn’t try to move unlocked file segments out of the way.
AllocateResidentPages: PROCEDURE [npages: CARDINAL] RETURNS [base: POINTER];
The same as Storage.Pages.
PagesForWords: PROCEDURE [nwords: CARDINAL] RETURNS [npages: CARDINAL];
The same as Storage.PagesForWords.
FreePages: PROCEDURE [base: POINTER];
The same as Storage.FreePages.
Free Storage Package
The following definitions are available in FSPDefs. A zone is a block of storage containing embedded nodes. The length of either a zone or a node is a value of type
BlockSize: TYPE = INTEGER [0..VMLimit/2]; -- 15 bits.
Each zone is headed by a ZoneHeader, which is a monitored record with the following public fields:
. . .
threshold: BlockSize,-- minimum node size in zone
checking: BOOLEAN,-- zone checking (see below)
. . .
Zones are identified by pointers of type
ZonePointer: TYPE = POINTER TO ZoneHeader;
Associated with each zone is a procedure of type
Deallocator: TYPE = PROCEDURE [POINTER];
which is used to deallocate the storage used by the zone. The following Deallocator may be supplied when nothing is to be done to the storage being freed:
DoNothingDeallocate: Deallocator;
Zone Operations
An arbitrary block of (uninterpreted) storage is converted to a zone by the procedure
MakeNewZone: PROCEDURE [
base: POINTER, length: BlockSize, deallocate: Deallocator]
RETURNS [z: ZonePointer];
Such a block can alternatively be made an extension of an existing zone by calling
AddToNewZone: PROCEDURE [
z: ZonePointer, base: POINTER, length: BlockSize, deallocate: Deallocator];
The following procedures default DoNothingDeallocate as the Deallocator:
MakeZone: PROCEDURE [base: POINTER, length: BlockSize] RETURNS [z: ZonePointer];
AddToZone: PROCEDURE [z: ZonePointer, base: POINTER, length: BlockSize];
The following errors can be raised if the space provided is not a reasonable size.
ZoneTooSmall: ERROR [POINTER];
The storage provided is not large enough for a ZoneHeader plus one free node and one allocated node.
ZoneTooLarge: ERROR [POINTER];
The storage provided is too large to be represented by a BlockSize (15 bits)
PruneZone: PROCEDURE [z: ZonePointer] RETURNS [BOOLEAN];
TRUE is returned if any areas were freed, otherwise FALSE.
A zone may be destroyed and all its storage freed by calling
DestroyZone: PROCEDURE [z: ZonePointer];
No check is made for any nodes that are in use.
Warning: This operation cannot be protected by the monitor, and can therefore result in severe errors if another process is inside the zone.
Node Operations
The largest node that can be allocated in a virgin block of size length is length-ZoneOverhead.
A node is allocated by
MakeNode: PROCEDURE [z: ZonePointer, n: BlockSize] RETURNS [POINTER];
The value returned points to a block of n words; there is an additional hidden word of overhead (at offset-1) which must be preserved by users of the node. Nodes are sometimes split to satisfy allocation requests. Splitting within a zone z never generates fragments with size less than z.threshold, which is initialized to the minimum size of a free node. A request for a node of size n will produce a node with size in the range [n . . n+z.threshold).
The actual size of an allocated node is returned by
NodeSize: PROCEDURE [p: POINTER] RETURNS [BlockSize];
If after coalescing all free nodes, a node of the requested size cannot be found,
NoRoomInZone: SIGNAL [z: ZonePointer];
is raised. This signal can be resumed (after, e.g., adding to the zone), and another attempt to allocate and return a suitable node will be made. An allocated node is returned to the zone by
FreeNode: PROCEDURE [z: ZonePointer, p: POINTER];
Alternatively, an existing node can be split by calling
SplitNode: PROCEDURE [z: ZonePointer, p: POINTER, n: BlockSize];
the first n words of the node p remain allocated, and the remainder of the node is freed.
When a zone z is created, the variable z.checking is initialized to FALSE. If that variable is set to TRUE, the zone is checked for consistency prior to each transaction involving that zone. A failure raises one of the following signals:
InvalidZone, InvalidNode: ERROR [POINTER];
Allocation From The Heap
Clients who use heap storage extensively are encouraged to create their own heap from the above operations. The following procedures provide an example of a simple interface to the free storage package.
myHeap: FSPDefs.ZonePointer ← NIL;
GetSpace: PROCEDURE [nwords: CARDINAL] RETURNS [p: POINTER] =
BEGIN OPEN Storage, FSPDefs;
np: CARDINAL;
p ← MakeNode[myHeap, nwords !
NoRoomInZone =>
BEGIN
np ← PagesForWords[nwords + ZoneOverhead + NodeOverhead];
AddToNewZone[
myHeap,
Storage.Pages[np],
np*AltoDefs.PageSize,
Storage.FreePages];
RESUME
END];
END;
FreeSpace: PROCEDURE [p: POINTER] =
{FSPDefs.FreeNode[myHeap, p]};
GetString: PROCEDURE [nchars: CARDINAL] RETURNS [s: STRING] =
BEGIN
s ← GetSpace[StringDefs.WordsForString[nchars]];
s↑ ← [length: 0, maxlength: nchars, text:];
END;
FreeString: PROCEDURE [s: STRING] = LOOPHOLE[FreeSpace];
InitHeap: PROCEDURE [npages: CARDINAL] =
BEGIN OPEN FSPDefs;
IF myHeap # NIL THEN EraseHeap[];
myHeap ← MakeNewZone[
Storage.Pages[npages],
npages*AltoDefs.PageSize, Storage.FreePages];
END;
EraseHeap: PROCEDURE =
BEGIN
FSPDefs.DestroyZone[myHeap];
myHeap ← NIL;
END;
The System Heap
Clients who use the heap infrequently may use the system storage heap. The following definitions are available in Storage. The heap is managed by the free storage package; the appropriate zone pointer for use with the procedures described in the previous section is returned by
HeapZone: PROCEDURE RETURNS [POINTER];
If an allocation request cannot be satisfied from existing heap storage, an attempt is made to extend the heap with a block of appropriate size obtained from the segmentation machinery. The extension becomes a permanent part of the heap. Large requests are allocated in pages from the segmentation machinery and do not become a permanent part of the heap.
The following procedures provide a specialized interface.
Node: PROCEDURE [nwords: CARDINAL] RETURNS [p: POINTER];
Allocates a node of size nwords from the system heap.
Free: PROCEDURE [p: POINTER];
Returns the node to the system heap.
In addition,
String: PROCEDURE [nchars: CARDINAL] RETURNS [s: STRING];
Allocates space for the body of a string in the heap. The field s.length is set to zero; s.maxlength is set to nchars.
Such strings are freed by
FreeString: PROCEDURE [s: STRING];
It is often a good idea to reset pointers when freeing heap nodes. Therefore, the following procedures, with obvious semantics, are provided.
FreeNodeNil: PROCEDURE [p: POINTER] RETURNS [nil: POINTER];
FreeStringNil: PROCEDURE [s: STRING] RETURNS [nil: POINTER];
The following procedures help managing strings from the heap.
CopyString: PROCEDURE [s: STRING, longer: CARDINAL ← 0] RETURNS [STRING];
Allocates space for the body of a string in the heap able to hold s.length+longer characters, and then copies s to the new string. If s = NIL then CopyString returns NIL if longer = 0, otherwise it returns Storage.String[longer].
ExpandString: PROCEDURE [s: POINTER TO STRING, longer: CARDINAL];
Equivalent to ns ← CopyString[s↑, longer]; FreeHeapString[s↑]; s↑ ← ns.
There is a convention to interpret NIL as an empty string. The following procedures (which are declared in the interface Storage as INLINE) handle some of the cases where one might otherwise dereference a NIL.
EmptyString: PROCEDURE [s: STRING] RETURNS [BOOLEAN];
StringLength: PROCEDURE [s: STRING] RETURNS [CARDINAL];
If a program uses the heap heavily, it is best to increase the size of the heap as part of the program’s initialization. This lowers the likelihood of creating sandbars by expanding the heap at unexpected times.
Expand: PROCEDURE [pages: CARDINAL];
Obtains a segment of size pages and adds it to the heap.
It is occasionally useful to give back any segments of the heap that are completely inactive.
Prune: PROCEDURE RETURNS [BOOLEAN];
Returns TRUE if any storage was returned to the segmentation machinery, and FALSE otherwise.
The interface SystemDefs provides some of the same functionality as Storage. Since some existing programs still reference SystemDefs, the following procedures from SystemDefs are documented here also.
HeapZone: PROCEDURE RETURNS [POINTER];
The same as Storage.HeapZone.
AllocateHeapNode: PROCEDURE [nwords: CARDINAL] RETURNS [p: POINTER];
The same as Storage.Node.
FreeHeapNode: PROCEDURE [p: POINTER];
Same as Storage.Free.
AllocateHeapString: PROCEDURE [nchars: CARDINAL] RETURNS [s: STRING];
Same as Storage.String.
FreeHeapString: PROCEDURE [nchars: CARDINAL] RETURNS [s: STRING];
Same as Storage.FreeString.
CopyString: PROCEDURE [s: STRING, longer: CARDINAL ← 0] RETURNS [STRING];
Same as Storage.CopyString.
ExpandString: PROCEDURE [s: POINTER TO STRING, longer: CARDINAL];
Same as Storage.ExpandString.
PruneHeap: PROCEDURE RETURNS [BOOLEAN];
The same as Storage.Prune.