11. MVFF (Manual Variable First Fit)

MVFF manually manages variable-sized, unformatted objects. It uses the first fit allocation policy for blocks allocated via mps_alloc().

Johnstone (1997) found that in his test cases:

No version of best fit had more than 5% actual fragmentation. This is also true for all versions of first fit that used an address-ordered free list, and the two versions of first fit that used a FIFO free list. This strongly suggests that the basic best-fit algorithm and the first-fit algorithm with an address-ordered free list are very robust algorithms.

The MVFF pool class also supports buffered allocation (that is, allocation via allocation points), and in this case, the allocation policy is different: the buffers are filled according to the worst fit policy, and allocation always proceeds upwards from the base.

Buffered and unbuffered allocation can be used at the same time, but the first allocation point must be created before any call to mps_alloc().

It is usually not advisable to use buffered and unbuffered allocation on the same pool, because the worst-fit policy of buffer filling will grab all the large blocks, leading to severe fragmentation. If you need both forms of allocation, use two separate pools.

11.1. MVFF properties

• Supports allocation via mps_alloc().

• Supports allocation via allocation points. If an allocation point is created in an MVFF pool, the call to mps_ap_create_k() takes no keyword arguments.

• Supports deallocation via mps_free().

• Supports allocation frames but does not use them to improve the efficiency of stack-like allocation.

• Supports segregated allocation caches.

• There are no garbage collections in this pool.

• Blocks may not contain references to blocks in automatically managed pools (unless these are registered as roots).

• Allocations may be variable in size.

• The alignment of blocks is configurable, but may not be smaller than sizeof(void*).

• Blocks do not have dependent objects.

• Blocks are not automatically reclaimed.

• Blocks are not scanned.

• Blocks are not protected by barriers (1).

• Blocks do not move.

• Blocks may not be registered for finalization.

• Blocks must not belong to an object format.

11.2. MVFF interface

#include "mpscmvff.h"

mps_pool_class_t mps_class_mvff(void)

Return the pool class for an MVFF (Manual Variable First Fit) pool.

When creating an MVFF pool, mps_pool_create_k() accepts seven optional keyword arguments:

• MPS_KEY_EXTEND_BY (type size_t, default 65536) is the size of block that the pool will request from the arena.

• MPS_KEY_MEAN_SIZE (type size_t, default 32) is the predicted mean size of blocks that will be allocated from the pool. This is a hint to the MPS: the pool will be less efficient if this is wrong, but nothing will break.

• MPS_KEY_ALIGN (type mps_align_t, default is MPS_PF_ALIGN) is the alignment of the addresses allocated (and freed) in the pool. The minimum alignment supported by pools of this class is sizeof(void*) and the maximum is the arena grain size (see MPS_KEY_ARENA_GRAIN_SIZE).

• MPS_KEY_SPARE (type double, default 0.75) is the maximum proportion of memory that the pool will keep spare for future allocations. If the proportion of memory that’s free exceeds this, then the pool will return some of it to the arena for use by other pools.

• MPS_KEY_MVFF_ARENA_HIGH (type mps_bool_t, default false) determines whether new blocks are acquired at high addresses (if true), or at low addresses (if false).

• MPS_KEY_MVFF_SLOT_HIGH 1 (type mps_bool_t, default false) determines whether to search for the highest addressed free area (if true) or lowest (if false) when allocating using mps_alloc().

• MPS_KEY_MVFF_FIRST_FIT 1 (type mps_bool_t, default true) determines whether to allocate from the highest address in a found free area (if true) or lowest (if false) when allocating using mps_alloc().

1(1,2)

Allocation points are not affected by MPS_KEY_MVFF_SLOT_HIGH or MPS_KEY_MVFF_FIRST_FIT. They use a worst-fit policy in order to maximise the number of in-line allocations.

The defaults yield a a simple first-fit allocator. Specify MPS_KEY_MVFF_ARENA_HIGH and MPS_KEY_MVFF_SLOT_HIGH true, and MPS_KEY_MVFF_FIRST_FIT false to get a first-fit allocator that works from the top of memory downwards. Other combinations may be useful in special circumstances.

For example:

MPS_ARGS_BEGIN(args) {
    MPS_ARGS_ADD(args, MPS_KEY_EXTEND_BY, 1024 * 1024);
    MPS_ARGS_ADD(args, MPS_KEY_MEAN_SIZE, 32);
    MPS_ARGS_ADD(args, MPS_KEY_ALIGN, 8);
    MPS_ARGS_ADD(args, MPS_KEY_MVFF_ARENA_HIGH, 1);
    MPS_ARGS_ADD(args, MPS_KEY_MVFF_SLOT_HIGH, 1);
    MPS_ARGS_ADD(args, MPS_KEY_MVFF_FIRST_FIT, 0);
    res = mps_pool_create_k(&pool, arena, mps_class_mvff(), args);
} MPS_ARGS_END(args);

mps_pool_class_t mps_class_mvff_debug(void)

A debugging version of the MVFF pool class.

When creating a debugging MVFF pool, mps_pool_create_k() accepts eight optional keyword arguments: MPS_KEY_EXTEND_BY, MPS_KEY_MEAN_SIZE, MPS_KEY_ALIGN, MPS_KEY_SPARE, MPS_KEY_MVFF_ARENA_HIGH, MPS_KEY_MVFF_SLOT_HIGH, and MPS_KEY_MVFF_FIRST_FIT are as described above, and MPS_KEY_POOL_DEBUG_OPTIONS specifies the debugging options. See mps_pool_debug_option_s.