Notes

This module implements an allocator that manages a number of pools. Thereby, each pool contains a number of blocks of equal size.

Both the number of blocks and the block size must be configured for each pool. For example, the following configures pool 0 to contain 16 blocks at 256 bytes.

#define AO_ALLOC_POOL_BLOCK_COUNT_0 ( 16)
#define AO_ALLOC_POOL_BLOCK_SIZE_0  (256)

That way, up to 64 pools can be configured. However, there is a limit to the number of pools that can actually be used. It is determined by the number of bits of the standard library’s size_t type. So, if that type is 32 bits wide, then at most 32 pools are available.

This is due to the fact, that the module maintains a bitmask of type size_t, where each set bit indicates whether the respective pool contains at least one free block. Consequently, a clear bit indicates an empty pool.

Upon allocation, the module walks the bitmask starting at the least significant bit, that is, bit 0. For each bit, it checks, whether the respective pool is not empty and the block size is sufficient to fulfil the request. It stops as soon as it has found a suitable block. Consequently, pools should be configured with increasing block sizes, in order to minimize internal fragmentation.

Due to its iterative approach, allocation is a linear-time operation. In contrast, deallocation takes constant time. This is, because each block contains a header, that stores the pool, to which it belongs.

Include

Configuration

AO_ALLOC_ALLOCATED

AO_ALLOC_ALLOCATED_MAX

#define AO_ALLOC_ALLOCATED     (false)
#define AO_ALLOC_ALLOCATED_MAX (false)

Defines whether to keep track of the current and maximum number of allocated bytes, respectively. If this configuration option is enabled, then the respective data is gathered both globally and for each pool.

AO_ALLOC_FREE

AO_ALLOC_FREE_MIN

#define AO_ALLOC_FREE     (false)
#define AO_ALLOC_FREE_MIN (false)

Defines whether to keep track of the current and minimum number of free bytes, respectively. If this configuration option is enabled, then the respective data is gathered both globally and for each pool.

AO_ALLOC_POOL_BLOCK_COUNT_*

#define AO_ALLOC_POOL_BLOCK_COUNT_0  (0)
#define AO_ALLOC_POOL_BLOCK_COUNT_1  (0)

// ...

#define AO_ALLOC_POOL_BLOCK_COUNT_63 (0)

Defines the number of blocks in each pool.

AO_ALLOC_POOL_BLOCK_SIZE_*

#define AO_ALLOC_POOL_BLOCK_SIZE_0  (0)
#define AO_ALLOC_POOL_BLOCK_SIZE_1  (0)

// ...

#define AO_ALLOC_POOL_BLOCK_SIZE_63 (0)

Defines the size of the blocks in each pool, in bytes.

Types

ao_alloc_pool_t

typedef struct ao_alloc_pool_t ao_alloc_pool_t;

Represents a pool.

ao_alloc_pool_node_t

typedef struct ao_alloc_pool_node_t ao_alloc_pool_node_t;

Represents a pool node, which in turn contains a memory block.

ao_acquired_t

ao_released_t

ao_retained_t

typedef struct ao_acquired_t ao_acquired_t;
typedef struct ao_released_t ao_released_t;
typedef struct ao_retained_t ao_retained_t;

Represents information in the context of a call to ao_acquire(), ao_release(), or ao_retain(), respectively.

Structs

ao_alloc_pool_t

struct ao_alloc_pool_t
{

#if AO_ALLOC_ALLOCATED_MAX || \
    AO_ALLOC_ALLOCATED

    size_t volatile        allocated;

#endif

#if AO_ALLOC_ALLOCATED_MAX

    size_t volatile        allocated_max;

#endif

    size_t                 block_size;

#if AO_ALLOC_FREE_MIN || \
    AO_ALLOC_FREE

    size_t volatile        free;

#endif

#if AO_ALLOC_FREE_MIN

    size_t volatile        free_min;

#endif

    ao_alloc_pool_node_t * front;
};

ao_alloc_pool_node_t

This struct is not publicly exposed.

ao_acquired_t

struct ao_acquired_t
{
    size_t pool;
    void * ptr;
    bool   result;
    size_t size_body;
    size_t size_body_requested;
    size_t size_head;
};

ao_released_t

struct ao_released_t
{
    size_t pool;
    void * ptr;
    size_t ref;
    bool   result;
    size_t size_body;
    size_t size_head;
};

ao_retained_t

struct ao_retained_t
{
    size_t pool;
    void * ptr;
    size_t ref;
    bool   result;
    size_t size_body;
    size_t size_head;
};

Variables

ao_alloc_allocated

ao_alloc_allocated_max

extern size_t volatile ao_alloc_allocated;
extern size_t volatile ao_alloc_allocated_max;

The current and maximum number of allocated bytes.

ao_alloc_free

ao_alloc_free_min

extern size_t volatile ao_alloc_free;
extern size_t volatile ao_alloc_free_min;

The current and minimum number of free bytes.

ao_alloc_pool_*

extern ao_alloc_pool_t ao_alloc_pool_0;
extern ao_alloc_pool_t ao_alloc_pool_1;

// ...

extern ao_alloc_pool_t ao_alloc_pool_63;

The pools.