MVFF pool class

author Gavin Matthews
date 1998-09-09
index terms pair: MVFF pool class; design single: pool class; MVFF design
organization Harlequin
revision //info.ravenbrook.com/project/mps/version/1.113/design/poolmvff.txt#1
status incomplete doc
tag design.mps.poolmvff

Introduction

.intro: This is the design of the MVFF (Manual Variable First-Fit) pool class. This pool implements a first (or last) fit policy for variable-sized manually-managed objects, with control over first/last, segment preference high/low, and slot fit low/high.

The pool was created in a response to a belief that the ScriptWorks EPDL/EPDR's first fit policy is beneficial for some classes of client behaviour, but the performance of a linear free list was unacceptable.

Overview

.over: This pool implements certain variants of the address-ordered first-fit policy. The implementation allows allocation across segment boundaries.

.over.buffer: Buffered allocation is also supported, but in that case, the buffer-filling policy is worst-fit. Buffered and unbuffered allocation can be used at the same time, but in that case, the first ap must be created before any allocations.

.over.buffer.class: The pool uses the simplest buffer class, BufferClass. This is appropriate since these buffers don't attach to segments, and hence don't constrain buffered regions to lie within segment boundaries.

.over.segments: The pool uses the simplest segment class (SegClass). There's no need for anything more complex.

Methods

.method: The MVFF pool supports the following methods:

Res MVFFInit(Pool pool, Args arg)

.method.init: This takes six keyword arguments:

Keyword argument Description
MPS_KEY_EXTEND_BY The segment size.
MPS_KEY_MEAN_SIZE The average object size.
MPS_KEY_ALIGN The alignment of allocations and frees. Must be at least sizeof(void*).
MPS_KEY_MVFF_SLOT_HIGH Whether to allocate objects at the end of free blocks found, as opposed to at the start (for unbuffered allocation).
MPS_KEY_MVFF_ARENA_HIGH Whether to express SegPrefHIGH to the arena, as opposed to SegPrefLOW.
MPS_KEY_MVFF_FIRST_FIT whether to use the suitable block of lowest address, as opposed to the highest (for unbuffered allocation)

.method.init.epdl: To simulate the EPDL pool, specify extendBy, avgSize, and maxSize as normal, and use slotHigh=FALSE, arenaHigh=FALSE, firstFit=TRUE.

.method.init.epdr: To simulate the EPDR pool, specify extendBy, avgSize, and maxSize as normal, and use slotHigh=TRUE, arenaHigh=TRUE, firstFit=TRUE.

.method.init.other: The performance characteristics of other combinations are unknown.

.method.finish: The PoolFinish() method,

.method.alloc: PoolAlloc() and PoolFree() methods are supported, implementing the policy set by the pool params (see .method.init).

.method.describe: The usual describe method.

.method.buffer: The buffer methods implement a worst-fit fill strategy.

External Functions

.function: MVFF supports the following external functions:

.function.free-size: mps_mvff_free_size() returns the total size of free space in segments allocated to the MVFF pool instance.

.function.size: mps_mvff_size() returns the total memory used by pool segments, whether free or allocated.

.function.class: mps_class_mvff() returns the class object for the pool class, to be used in pool creation.

Implementation

.impl.free-list: The pool stores its free list in a CBS (see //gdr-peewit/info.ravenbrook.com/project/mps/branch/2013-05-17/emergency/design/poolmvff.txt design.mps.cbs), failing over in emergencies to a Freelist (see design.mps.freelist) when the CBS cannot allocate new control structures. This is the reason for the alignment restriction above.

Details

.design.seg-size: When adding a segment, we use extendBy as the segment size unless the object won't fit, in which case we use the object size (in both cases we align up).

.design.seg-fail: If allocating a segment fails, we try again with a segment size just large enough for the object we're allocating. This is in response to request.mps.170186.

Document History

  • 1998-09-09 Gavin Matthews. Wrote a list of methods and function plus some notes.
  • 1999-01-06 Pekka P. Pirinen. Added overview, removed bogus ArenaEnter design, and described buffered allocation.
  • Modified for the "Sunset On Segments" redesign of segments. Buffered allocation is no longer limited to segment boundaries.
  • 2002-06-07 RB Converted from MMInfo database design document.
  • 2013-05-10 RB Converted to reStructuredText. Updated to document keyword arguments, replacing varargs.
  • 2013-06-04 GDR The CBS module no longer maintains its own emergency list, so MVFF handles the fail-over from its CBS to a Freelist.