Known requirements

.req.stack-alloc: Provide a interface for clients to describe a stack allocation pattern, as an alternative to using the control stack.

.req.efficient: Permit an implementation which is comparable in efficiency to allocating on the control stack.

.req.ap: Support allocation via allocation points (APs).

.req.format: Support the allocation of formatted objects.

.req.scan: Ensure that objects in allocation frames can participate in garbage collection by being scanned.

.req.fix: Ensure that objects in allocation frames can participate in garbage collection by accepting Fix requests.

.req.condemn: Ensure that objects in allocation frames can participate in garbage collection by being condemned.

.attr.locking: Minimize the synchronization cost for the creation and destruction of frames.

Proto-requirements

.proto-req: The following are possible requirements that might be important in the future. The design does not necessarily meet all these requirements, but it does consider them all. Each requirement either has direct support in the framework, or could be supported with future additions to the framework.

.req.parallels: The allocation frame protocol should provide a framework for exploiting the parallels between stack extents, generations and "ramps".

.req.pool-destroy: It should be possible to use allocation frames to free all objects in a pool without destroying the pool.

.req.epvm: It should be possible to implement EPVM-style save and restore operations by creating and destroying allocation frames.

.req.subst: It should be possible to substitute a stack pool with a GC-ed pool so that erroneous use of a stack pool can be detected.

.req.format-extensions: It should be possible for stack pools to utilize the same format as any other pool, including debugging formats that include fenceposting, etc.

.req.mis-nest: Should ensure "mis-nested" stacks are safe.

.req.non-top-level: Should support allocation in the non-top stack extent.

.req.copy-if-necessary: Should ensure that stack pools can support "copy-if-necessary" (so that low-level system code can heapify stack objects.)

.req.preserve: When an object is in an allocation frame which is being destroyed, it should be possible to preserve that object in the parent frame.

.req.contained: Should allow clients to ask if an object is "contained" in a frame. The object is contained in a frame if it is affected when the frame is ended.

.req.alloc-with-other: Should allow clients to allocate an object in the same frame as another object.

External types

.type.client.frame-handle: Frame handles are defined as the abstract type mps_frame_t.

typedef struct mps_frame_class_s *mps_frame_class_t

.type.client.frame-class: Frame classes are defined as an abstract type.

.type.client.frame-class.access: Clients access frame classes by means of dedicated functions for each frame class.

External functions

.fn.client.push: mps_ap_frame_push() is used by clients to invoke the FramePush operation. For lightweight frames, this might not invoke the corresponding internal function.

.fn.client.pop: mps_ap_frame_pop() is used by clients to invoke the FramePop operation. For lightweight frames, this might not invoke the corresponding internal function.

mps_res_t mps_ap_frame_select(mps_ap_t buf, mps_frame_t frame)

.fn.client.select: This following function is used by clients to invoke the FrameSelect operation.

mps_res_t mps_ap_frame_select_from_addr(mps_ap_t buf, mps_addr_t addr)

.fn.client.select-addr: This function is used by clients to invoke the FrameSelectOfAddr operation.

mps_res_t mps_ap_addr_in_frame(mps_bool_t *inframe_o, mps_ap_t buf, mps_addr_t *addrref, mps_frame_t frame)

.fn.client.in-frame: This function is used by clients to invoke the FrameHasAddr operation.

mps_res_t mps_ap_set_frame_class(mps_ap_t buf, mps_frame_class_t class)

.fn.client.set: This function is used by clients to invoke the SetFrameClass operation.

mps_frame_class_t mps_alloc_frame_class_stack(void)

.fn.client.stack-frame-class: This function is used by clients to access the frame class used for simple stack allocation.

Internal types

typedef struct AllocFrameStruct *AllocFrame

.type.frame-handle: Frame handles are defined as an abstract type.

typedef struct AllocFrameClassStruct *AllocFrameClass

.type.frame-class: Frame classes are defined as an abstract type.

typedef Res (*PoolFramePushMethod)(AllocFrame *frameReturn, Pool pool, Buffer buf)

.fn.push: A pool method of this type is called (if needed) to invoke the FramePush operation.

typedef Res (*PoolFramePopMethod)(Pool pool, Buffer buf, AllocFrame frame)

.fn.pop: A pool method of this type is called (if needed) to invoke the FramePop operation:

typedef Res (*PoolFrameSelectMethod)(Pool pool, Buffer buf, AllocFrame frame)

.fn.select: A pool method of this type is called to invoke the FrameSelect operation.

typedef Res (*PoolFrameSelectFromAddrMethod)(Pool pool, Buffer buf, Addr addr)

.fn.select-addr: A pool method of this type is called to invoke the FrameSelectOfAddr operation.

typedef Res (*PoolFrameHasAddrMethod)(Bool *inframeReturn, Pool pool, Seg seg, Addr *addrref, AllocFrame frame)

.fn.in-frame: A pool method of this type is called to invoke the FrameHasAddr operation.

typedef Res (*PoolSetFrameClassMethod)(Pool pool, Buffer buf, AllocFrameClass class)

.fn.set: A pool method of this type is called to invoke the SetFrameClass operation.

Overview

.lw-frame.overview: Allocation points provide direct support for lightweight frames, and are designed to permit FramePush and FramePop operations without the need for locking and delegation to the pool method. The pool method will be called whenever synchronization is required for other reasons (e.g. the buffer is tripped).

.lw-frame.model: Lightweight frames offer direct support for a particular model of allocation frame use, whereby the FramePush operation returns the current allocation pointer as a frame handle, and the FramePop operation causes the allocation pointer to be reset to the address of the frame handle. This model should be suitable for simple stack frames, where more advanced operations like FrameSelect are not supported. It may also be suitable for more advanced allocation frame models when they are being used simply. The use of a complex operation always involves synchronization via locking, and the pool may disable lightweight synchronization temporarily at this time.

Synchronization

.lw-frame.sync: The purpose of the design is that mutator may access the state of an AP without locking with MPS (via the external functions). The design assumes the normal MPS restriction that an operation on an AP may only be performed by a single mutator thread at a time. Each of the operations on allocation frames counts as an operation on an AP.

Implementation

.lw-frame.push: The external FramePush operation mps_ap_frame_push() performs the following operations:

IF ap->init != ap->alloc
   FAIL
ELSE IF ap->init < ap->limit
   *frame_o = ap->init;
ELSE
  WITH_ARENA_LOCK
    PerformInternalFramePushOperation(...)
  END
END

.lw-frame.push.limit: The reason for testing ap->init < ap->limit and not ap->init <= ap->limit is that a frame pointer at the limit of a buffer (and possibly therefore of a segment) would be ambiguous: is it at the limit of the segment, or at the base of the segment that's adjacent in memory? The internal operation must handle this case, for example by refilling the buffer and setting the frame at the beginning.

.lw-frame.pop: The external FramePop operation (mps_ap_frame_pop()) performs the following operations:

IF ap->init != ap->alloc
   FAIL
ELSE IF BufferBase(ap) <= frame AND frame < ap->init
   ap->init = ap->alloc = frame;
ELSE
  WITH_ARENA_LOCK
    PerformInternalFramePopOperation(...)
  END
END

.lw-frame.pop.buffer: The reason for testing that frame is in the buffer is that if it's not, then we're popping to an address in some other segment, and that means that some objects in the other segment (and all objects in any segments on the stack in between) are now dead, and the only way for the pool to mark them as being dead is to do a heavyweight pop.