.. mode: -*- rst -*-

MVFF pool class
===============

:Tag: design.mps.poolmvff
:Author: Gavin Matthews
:Date: 1998-09-09
:Organization: Harlequin
:Status: incomplete doc
:Revision: $Id: //info.ravenbrook.com/project/mps/version/1.113/design/poolmvff.txt#1 $
:Index terms:
   pair: MVFF pool class; design
   single: pool class; MVFF design


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 arguments`: 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 <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_.

.. _request.mps.170186: https://info.ravenbrook.com/project/mps/import/2001-11-05/mmprevol/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.

.. _RB: http://www.ravenbrook.com/consultants/rb/
.. _GDR: http://www.ravenbrook.com/consultants/gdr/


Copyright and License
---------------------

Copyright © 2013-2014 Ravenbrook Limited. All rights reserved.
<http://www.ravenbrook.com/>. This is an open source license. Contact
Ravenbrook for commercial licensing options.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are
met:

#. Redistributions of source code must retain the above copyright
   notice, this list of conditions and the following disclaimer.

#. Redistributions in binary form must reproduce the above copyright
   notice, this list of conditions and the following disclaimer in the
   documentation and/or other materials provided with the distribution.

#. Redistributions in any form must be accompanied by information on how
   to obtain complete source code for this software and any
   accompanying software that uses this software.  The source code must
   either be included in the distribution or be available for no more than
   the cost of distribution plus a nominal fee, and must be freely
   redistributable under reasonable conditions.  For an executable file,
   complete source code means the source code for all modules it contains.
   It does not include source code for modules or files that typically
   accompany the major components of the operating system on which the
   executable file runs.

**This software is provided by the copyright holders and contributors
"as is" and any express or implied warranties, including, but not
limited to, the implied warranties of merchantability, fitness for a
particular purpose, or non-infringement, are disclaimed.  In no event
shall the copyright holders and contributors be liable for any direct,
indirect, incidental, special, exemplary, or consequential damages
(including, but not limited to, procurement of substitute goods or
services; loss of use, data, or profits; or business interruption)
however caused and on any theory of liability, whether in contract,
strict liability, or tort (including negligence or otherwise) arising in
any way out of the use of this software, even if advised of the
possibility of such damage.**