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/master/design/poolmvff.txt#18
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.

.background: 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.

Methods

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

Implementation

.impl.alloc_list: The pool stores the address ranges that it has acquired from the arena in a CBS (see design.mps.cbs).

.impl.free-list: The pool stores its free list in a CBS (see 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.acquire-size: When acquiring memory from the arena, we use extendBy as the unit of allocation unless the object won't fit, in which case we use the object size (in both cases we align up to the arena alignment).

.design.acquire-fail: If allocating extendBy, we try again with an aligned 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.
  • 2014-04-15 GDR The address ranges acquired from the arena are now stored in a CBS; segments are no longer used for this purpose.
  • 2014-06-12 GDR Remove public interface documentation (this is in the reference manual).