Splitting and merging

.split-and-merge: There is support for splitting and merging segments, to give pools the flexibility to rearrange their tracts among segments as they see fit.

Res SegSplit(Seg *segLoReturn, Seg *segHiReturn, Seg seg, Addr at)

.split: If successful, segment seg is split at address at, yielding two segments which are returned in segLoReturn and segHiReturn for the low and high segments respectively. The base of the low segment is the old base of seg. The limit of the low segment is at. The base of the high segment is at. This limit of the high segment is the old limit of seg. seg is effectively destroyed during this operation (actually, it might be reused as one of the returned segments). Segment subclasses may make use of the optional arguments; the built-in classes do not.

.split.invariants: The client must ensure some invariants are met before calling SegSplit():

• .split.inv.align: at must be a multiple of the arena grain size, and lie between the base and limit of seg. Justification: the split segments cannot be represented if this is not so.
• .split.inv.buffer: If seg is attached to a buffer, the buffered region must not include address at. Justification: the segment module is not in a position to know how (or whether) a pool might wish to split a buffer. This permits the buffer to remain attached to just one of the returned segments.

.split.state: Except as noted above, the segments returned have the same properties as seg. That is, their colour, summary, rankset, nailedness etc. are set to the values of seg.

Res SegMerge(Seg *mergedSegReturn, Seg segLo, Seg segHi)

.merge: If successful, segments segLo and segHi are merged together, yielding a segment which is returned in mergedSegReturn. segLo and segHi are effectively destroyed during this operation (actually, one of them might be reused as the merged segment). Segment subclasses may make use of the optional arguments; the built-in classes do not.

.merge.invariants: The client must ensure some invariants are met before calling SegMerge():

• .merge.inv.abut: The limit of segLo must be the same as the base of segHi. Justification: the merged segment cannot be represented if this is not so.
• .merge.inv.buffer: One or other of segLo and segHi may be attached to a buffer, but not both. Justification: the segment module does not support attachment of a single seg to 2 buffers.
• .merge.inv.similar: segLo and segHi must be sufficiently similar. Two segments are sufficiently similar if they have identical values for each of the following fields: class, grey, white, nailed, rankSet. Justification: There has yet to be a need to implement default behaviour for these cases. Pool classes should arrange for these values to be the same before calling SegMerge().

.merge.state: The merged segment will share the same state as segLo and segHi for those fields which are identical (see .merge.inv.similar). The summary will be the union of the summaries of segLo and segHi.

Allocation

typedef Bool (*SegBufferFillMethod)(Addr *baseReturn, Addr *limitReturn, Seg seg, Size size, RankSet rankSet)

.method.buffer-fill: Allocate a block in the segment, of at least size bytes, with the given set of ranks. If successful, update *baseReturn and *limitReturn to the block and return TRUE. Otherwise, return FALSE. The allocated block must be accounted as buffered (see design.mps.strategy.account.buffered).

typedef void (*SegBufferEmptyMethod)(Seg seg, Buffer buffer)

.method.buffer-empty: Free the unused part of the buffer to the segment. Account the used part as new (see design.mps.strategy.account.new) and the unused part as free (see design.mps.strategy.account.free).

Garbage collection

typedef Res (*SegAccessMethod)(Seg seg, Arena arena, Addr addr, AccessSet mode, MutatorContext context)

.method.access: The access method indicates that the client program attempted to access the address addr, but has been denied due to a protection fault. The mode indicates whether the client program was trying to read (AccessREAD) or write (AccessWRITE) the address. If this can't be determined, mode is AccessREAD | AccessWRITE. The segment should perform any work necessary to remove the protection whilst still preserving appropriate invariants (this might scanning the region containing addr). Segment classes are not required to provide this method, and not doing so indicates they never protect any memory managed by the pool. This method is called via the generic function SegAccess().

typedef Res (*SegWhitenMethod)(Seg seg, Trace trace)

.method.whiten: The whiten method requests that the segment seg condemn (a subset of, but typically all) its objects for the trace trace. That is, prepare them for participation in the trace to determine their liveness. The segment should expect fix requests (.method.fix) during the trace and a reclaim request (.method.reclaim) at the end of the trace. Segment classes that automatically reclaim dead objects must provide this method, and pools that use these segment classes must additionally set the AttrGC attribute. This method is called via the generic function SegWhiten().

typedef void (*SegGreyenMethod)(Seg seg, Trace trace)

.method.grey: The greyen method requires the segment seg to colour its objects grey for the trace trace (excepting objects that were already condemned for this trace). That is, make them ready for scanning by the trace trace. The segment must arrange that any appropriate invariants are preserved, possibly by using the protection interface (see design.mps.prot). Segment classes are not required to provide this method, and not doing so indicates that all instances of this class will have no fixable or traceable references in them. This method is called via the generic function SegGreyen().

typedef void (*SegBlackenMethod)(Seg seg, TraceSet traceSet)

.method.blacken: The blacken method is called if it is known that the segment seg cannot refer to the white set for any of the traces in traceSet. The segment must blacken all its grey objects for those traces. Segment classes are not required to provide this method, and not doing so indicates that all instances of this class will have no fixable or traceable references in them. This method is called via the generic function SegBlacken().

typedef Res (*SegScanMethod)(Bool *totalReturn, Seg seg, ScanState ss)

.method.scan: The scan method scans all the grey objects on the segment seg, passing the scan state ss to TraceScanFormat(). The segment may additionally accumulate a summary of all its objects. If it succeeds in accumulating such a summary it must indicate that it has done so by setting the *totalReturn parameter to TRUE. Otherwise it must set *totalReturn to FALSE. This method is called via the generic function SegScan().

.method.scan.required: Automatically managed segment classes are required to provide this method, even if all instances of this class will have no fixable or traceable references in them, in order to support mps_pool_walk().

typedef Res (*SegFixMethod)(Seg seg, ScanState ss, Ref *refIO)

.method.fix: The fix method indicates that the reference *refIO has been discovered at rank ss->rank by the traces in ss->traces, and the segment must handle this discovery according to the fix protocol (design.mps.fix). If the method moves the object, it must update *refIO to refer to the new location of the object. If the method determines that the referenced object died (for example, because the highest-ranking references to the object were weak), it must update *refIO to NULL. Segment classes that automatically reclaim dead objects must provide this method, and pools that use these classes must additionally set the AttrGC attribute. Pool classes that use segment classes that may move objects must also set the AttrMOVINGGC attribute. The fix method is on the critical path (see design.mps.critical-path) and so must be fast. This method is called via the function TraceFix().

.method.fixEmergency: The fixEmergency method is used to perform fixing in "emergency" situations. Its specification is identical to the fix method, but it must complete its work without allocating memory (perhaps by using some approximation, or by running more slowly). Segment classes must provide this method if and only if they provide the fix method. If the fix method does not need to allocate memory, then it is acceptable for fix and fixEmergency to be the same.

typedef void (*SegReclaimMethod)(Seg seg, Trace trace)

.method.reclaim: The reclaim method indicates that any remaining white objects in the segment seg have now been proved unreachable by the trace trace, and so are dead. The segment should reclaim the resources associated with the dead objects. Segment classes are not required to provide this method. If they do, pools that use them must set the AttrGC attribute. This method is called via the generic function SegReclaim().

typedef void (*SegWalkMethod)(Seg seg, Format format, FormattedObjectsVisitor f, void *v, size_t s)

.method.walk: The walk method must call the visitor function f (along with its closure parameters v and s and the format format) once for each of the black objects in the segment seg. Padding objects may or may not be included in the walk, at the segment's discretion: it is the responsibility of the client program to handle them. Forwarding objects must not be included in the walk. Segment classes need not provide this method. This method is called by the generic function SegWalk(), which is called by the deprecated public functions mps_arena_formatted_objects_walk() and mps_amc_apply().

.method.walk.deprecated: The walk method is deprecated along with the public functions mps_arena_formatted_objects_walk() and mps_amc_apply() and will be removed along with them in a future release.

typedef void (*SegFlipMethod)(Seg seg, Trace trace)

.method.flip: Raise the read barrier, if necessary, for a trace that's about to flip and for which the segment is grey and potentially contains references.

Splitting and merging

typedef Res (*SegSplitMethod)(Seg seg, Seg segHi, Addr base, Addr mid, Addr limit)

.method.split: Segment subclasses may extend the support for segment splitting by defining their own "split" method. On entry, seg is a segment with region [base,limit), segHi is uninitialized, mid is the address at which the segment is to be split. The method is responsible for destructively modifying seg and initializing segHi so that on exit seg is a segment with region [base,mid) and segHi is a segment with region [mid,limit). Usually a method would only directly modify the fields defined for the segment subclass.

.method.split.next: A split method should always call the next method, either before or after any class-specific code (see design.mps.protocol.overview.next-method).

.method.split.accounting: If seg belongs to a generation in a chain, then the pool generation accounting must be updated. In the simple case where the split segments remain in the same generation, this can be done by calling PoolGenAccountForSegSplit().

typedef Res (*SegMergeMethod)(Seg seg, Seg segHi, Addr base, Addr mid, Addr limit)

.method.merge: Segment subclasses may extend the support for segment merging by defining their own merge method. On entry, seg is a segment with region [base,mid), segHi is a segment with region [mid,limit), The method is responsible for destructively modifying seg and finishing segHi so that on exit seg is a segment with region [base,limit) and segHi is garbage. Usually a method would only modify the fields defined for the segment subclass.

.method.merge.next: A merge method should always call the next method, either before or after any class-specific code (see design.mps.protocol.overview.next-method).

.method.merge.accounting: If seg belongs to a generation in a chain, then the pool generation accounting must be updated. In the simple case where the two segments started in the same generation and the merged segment remains in that generation, this can be done by calling PoolGenAccountForSegMerge().

.split-merge.shield: Split and merge methods may assume that the segments they are manipulating are not in the shield queue.

.split-merge.shield.flush: The shield queue is flushed before any split or merge methods are invoked.

.split-merge.shield.re-flush: If a split or merge method performs an operation on a segment which might cause the segment to be queued, the method must flush the shield queue before returning or calling another split or merge method.

.split-merge.fail: Split and merge methods might fail, in which case segments seg and segHi must be equivalently valid and configured at exit as they were according to the entry conditions. It's simplest if the failure can be detected before calling the next method (for example, by allocating any objects early in the method).

.split-merge.fail.anti: If it's not possible to detect failure before calling the next method, the appropriate anti-method must be used (see design.mps.protocol.guide.fail.after-next). Split methods are anti-methods for merge methods, and vice-versa.

.split-merge.fail.anti.constrain: In general, care should be taken when writing split and merge methods to ensure that they really are anti-methods for each other. The anti-method must not fail if the initial method succeeded. The anti-method should reverse any side effects of the initial method, except where it's known to be safe to avoid this (see .split-merge.fail.summary for an example of a safe case).

.split-merge.fail.anti.no: If this isn't possible (it might not be) then the methods won't support after-next failure. This fact should be documented, if the methods are intended to support further specialization. Note that using va_arg with the args parameter is sufficient to make it impossible to reverse all side effects.

.split-merge.fail.summary: The segment summary might not be restored exactly after a failed merge operation. Each segment would be left with a summary which is the union of the original summaries (see .merge.state). This increases the conservatism in the summaries, but is otherwise safe.

.split-merge.unsupported: Segment classes need not support segment merging at all. The function SegClassMixInNoSplitMerge() is supplied to set the split and merge methods to unsupporting methods that will report an error in checking varieties.