Dynamic memory allocation from out-of-band context
EVL applications usually have to manage the RAM resource dynamically,
so that the number of live objects they may need to maintain, and for
how long they would have to do so, does not have to be defined or even
known in advance. For this purpose, libevl implements a memory heap
manager usable from the out-of-band context, from which objects can be allocated or
released dynamically in a time-bound fashion.
An EVL heap is composed of at least one so-called memory extent, which is a contiguous RAM area chunks are allocated from and released to. Each extent is at most 4Gb - 512 bytes long. The first extent attached to any given heap is passed at creation time to evl_init_heap(). Then, you may add more space for storage by attaching more RAM extents to such heap using evl_extend_heap(). There is no arbitrary limit on the number of extents forming a heap; however, since these extents are tracked in a linked list which might have to be scanned for space when allocating chunks from a crowded heap, you may want to limit the live extents to a reasonable number (less than ten would seem appropriate). There is no arbitrary limit on the number of heaps an application can create either.
In other words, how many heaps you may create and how large such heaps might be is only limited to the amount of RAM available on your system.
How an EVL heap works
The memory allocation scheme is a variation of the algorithm described in a USENIX 1988 paper called “Design of a General Purpose Memory Allocator for the 4.3BSD Unix Kernel” by Marshall K. McKusick and Michael J. Karels. You can find it at various locations on the Internet.
An EVL heap organizes the memory extents it has been given as a set of fixed-size pages where allocated blocks live, with each page worth 512 bytes of storage. In any given extent, pages can be either part of the free pool, or busy storing user data. A busy page either contains one or multiple blocks (aka chunks), or it may be part of a larger block which spans multiple contiguous pages in memory. Pages containing chunks (as opposed to pages representing a portion of a larger block) are grouped by common chunk size, which is always a power of 2. Every allocation request is rounded to the next power of 2, with a minimum of 16 bytes, e.g. calling evl_alloc_heap() for 60 bytes will reserve a 64-byte chunk internally.
To this end, the heap manager maintains the following data structures for each extent of a given heap:
-
a free page pool. This pool is maintained in an couple of AVL trees to ensure time-bound operations on inserting and removing pages (either by size or address).
-
an array of lists of free pages used as a fast block cache. Each entry in the array links pages which are available for storing chunks of the same size. The chunk size may range from 2^4 to 2^8 bytes, which gives an array of five entries for representing all the possible sizes we may allocate from the fast cache. Within a single page of 512 bytes, up to 32 chunks of 16 bytes each are available, 16 chunks for 32 bytes and so on, down to 2 chunks of 256 bytes.
The allocation strategy is as follows, for each available extent until the request is satisfied or impossible to satisfy by any extent:
-
if the application requests a chunk which is not larger than half the size of a page (i.e. 2^8 or 256 bytes), then the fast block cache of the current extent is searched for a free chunk. For instance, a request for allocating 24 bytes would cause a lookup into the fast cache for a free chunk of 32 bytes. If no free chunk is available from the cache for that size, a new page is pulled from the free pool, added to the free page list for the corresponding size, and the allocation is tried again.
-
if the size of requested chunk rounded up to the next power of 2 is larger than half the size of a page (i.e. >= 2^9 bytes), a set of contiguous pages which covers the entire allocation request is directly pulled from the free pool maintained in the current extent. In this case, the fast block cache is not used.
Some runtime characteristics
-
the implementation is thread-safe when called via the serializing API, using an EVL mutex internally to serialize callers while updating the heap state.
-
O(1) access guarantee on allocation and release of free chunks into a fast block cache, ranging from 16 to 256 bytes. This is the typical allocation pattern an EVL heap is good at handling very quickly.
-
O(log n) access guarantee on allocation and release of pages from/to a free pool.
-
the EVL heap yields limited internal fragmentation for small chunks which can fit into fast block caches. Since there is no meta-data associated to busy blocks pulled from such cache, the memory overhead is basically zero in this case. The larger the chunk, the larger the internal fragmentation since all requested sizes are aligned on the next power of 2, up to 2^9. So asking for 257 bytes would actually consume an entire 512-byte page internally, directly pulled from the corresponding free pool.
-
for precise information about the runtime performance of the EVL heap manager on your platform, you may want to have a look at the output of the
heap_torturetest with verbosity turned on, as follows:
# $(evl test -L heap-torture) -v
Serializing vs non-serializing API
The EVL heap API comes in two flavours:
-
a non-serializing API which runs locklessly. Every call from this interface is suffixed by
_unlocked. This one should be used ONLY when you can guarantee that the target heap can never be accessed concurrently by multiple threads. -
a serializing API which enforces thread-safety via an EVL mutex. Every non-serializing call has a serializing counterpart (e.g. evl_alloc_block_unlocked() and evl_alloc_block()).
Other options for a real-time capable memory allocator
-
Another option for a deterministic memory allocator would be TLSF, which would easily work on top of EVL’s out-of-band context with some limited adaptation. It is slightly faster than the EVL heap on average, but internal fragmentation for the typical use cases it was confronted to looks much higher.
-
The fragmentation issue of the original TLSF implementation seems to have led to a later implementation addressing the problem.
These are only examples which come to mind. There should be no shortage of memory allocators you could adapt for running EVL applications. You would only need to make sure to use EVL services exclusively in that code, like mutexes if you need a thread-safe implementation.
Initializing a memory heap
This is how one could create a memory heap out of a static array of characters defined in a program:
#include <evl/heap.h>
static char heap_storage[EVL_HEAP_RAW_SIZE(1024 * 1024)]; /* 1Mb heap */
static struct evl_heap runtime_heap;
int init_runtime_heap(void)
{
int ret;
/* We use the serializing API. */
ret = evl_init_heap(&runtime_heap, heap_storage, sizeof heap_storage);
...
return ret;
}
Likewise, but this time using malloc(3) to get the raw storage for the new heap:
#include <stdlib.h>
#include <evl/heap.h>
static struct evl_heap runtime_heap;
int init_runtime_heap(void)
{
const size_t raw_size = EVL_HEAP_RAW_SIZE(1024 * 1024); /* 1Mb heap */
void *heap_storage;
int ret;
heap_storage = malloc(raw_size);
...
ret = evl_init_heap(&runtime_heap, heap_storage, raw_size);
...
return ret;
}
Memory heap services
This service initializes a heap, based on a memory area provided by the caller. This area should be large enough to contain both the user payload, and the meta-data the heap manager is going to need for maintaining such payload. The length of such area is called the raw size, as opposed to the lesser amount of bytes actually available for storing the user payload which is called the user size.
An in-memory heap descriptor is constructed by evl_init_heap(),
which contains ancillary information other calls will need. heap
is a pointer to such descriptor of type struct evl_heap.
The start address of the raw memory area which is given to the heap manager for serving dynamic allocation requests.
The size (in bytes) of the raw memory area starting at mem. This size
includes the space required to store the meta-data needed for
maintaining the new heap. You should use the
EVL_HEAP_RAW_SIZE(user_size) macro to determine the total amount
of memory which should be available from mem for creating a heap
offering up to user_size bytes of payload data. For instance, you
would use EVL_HEAP_RAW_SIZE(8192) as the value of the size
argument for creating a 8Kb heap.
Zero is returned on success. Otherwise, a negated error code is returned:
-
-EINVAL is returned if size is invalid, cannot be used to derive a proper user size. A proper user size should be aligned on a page boundary (512 bytes), cover at least one page of storage, without exceeding 4Gb - 512 bytes.
-
Since
evl_init_heap()creates a mutex for protecting access to the heap meta-data, any return code returned by evl_create_mutex().
Heaps initialized by this call MUST be accessed by serializing calls, excluding any call from the non-serializing API.
A heap which is strictly private to a given thread does not need to be guarded against concurrent accesses. This call is a variant of evl_init_heap() which does NOT plan for locking the heap while accessing it. For this reason, no EVL mutex is created by this call.
Zero is returned on success. Otherwise, a negated error code is returned:
- -EINVAL is returned if size is invalid, cannot be used to derive a proper user size. A proper user size should be aligned on a page boundary (512 bytes), cover at least one page of storage, without exceeding 4Gb - 512 bytes.
Heaps initialized by this call MUST be accessed by non-serializing calls, excluding any call from the serializing API.
Add more storage space to an existing heap. The extent space should be large enough to contain both the additional user payload, and the meta-data the heap manager is going to need for maintaining such payload.
The in-memory heap descriptor previously constructed by evl_init_heap().
The start address of the raw memory area which is added to the heap.
Like with evl_init_heap(), the size
(in bytes) of the raw memory area starting at mem which includes the
space required to store the meta-data needed for maintaining the
additional set of pages. You should use the
EVL_HEAP_RAW_SIZE(user_size) macro to determine the total amount of
memory which should be available from mem for creating an extent
offering up to user_size bytes of additional payload data. For
instance, you would use EVL_HEAP_RAW_SIZE(8192) as the value of the
size argument for creating a 8Kb extent.
Zero is returned on success. Otherwise, a negated error code is returned:
- -EINVAL is returned if size is invalid, cannot be used to derive a proper user size. A proper user size should be aligned on a page boundary (512 bytes), cover at least one page of storage, without exceeding 4Gb - 512 bytes.
This call is a variant of evl_extend_heap() which does NOT serialize callers when accessing the heap. As a result, this call is thread-unsafe.
Zero is returned on success. Otherwise, a negated error code is returned:
- -EINVAL is returned if size is invalid, cannot be used to derive a proper user size. A proper user size should be aligned on a page boundary (512 bytes), cover at least one page of storage, without exceeding 4Gb - 512 bytes.
This call dismantles a memory heap. The user storage is left unspoiled by the deletion process, and no specific action is taken regarding the raw storage received from either evl_init_heap() or evl_extend_heap() when the heap was active. Such storage should be further released by the caller if need be.
The in-memory heap descriptor previously constructed by evl_init_heap() to be dismantled.
This call is a variant of evl_destroy_heap() which must be used in pair with evl_init_heap_unlocked().
Allocate a chunk of memory from a given heap.
The in-memory heap descriptor previously constructed by evl_init_heap().
The amount of bytes to allocate.
A valid memory pointer is returned on success, otherwise NULL. The
following is true for any chunk of memory returned by
evl_alloc_block():
-
if size is smaller than 512 bytes, it is rounded up to the next power of 2, with a minimum of 16 bytes.
-
if size is larger than 512 bytes, it is rounded up to the next 512-byte boundary.
-
the address of the new chunk is aligned on a 16-byte boundary.
This call is a variant of evl_alloc_block() which does NOT serialize callers when accessing the heap. As a result, this call is thread-unsafe.
Release a previously allocated chunk of memory, returning it to the originating heap.
The in-memory heap descriptor previously constructed by evl_init_heap().
The address of a chunk to release which was originally obtained from evl_alloc_block().
This call is a variant of evl_free_block() which does NOT serialize callers when accessing the heap. As a result, this call is thread-unsafe.
Check if block is an active memory chunk living in heap. The
thoroughness of this test depends on whether libevl was compiled
with the optimizer disabled (i.e. -O0 passed to the compiler, causing
the __OPTIMIZE__ macro flag not to be defined at build time). If the
optimizer was enabled, this routine may not be able to detect whether
block is part of a valid data page. Therefore, you would probably
rely on this service only with debug builds.
The in-memory heap descriptor previously constructed by evl_init_heap().
The address of a block to check for sanity.
Zero is returned if block which was originally obtained from evl_alloc_block() and has not yat been released at the time of the call. Otherwise, a negated error code is returned:
- -EINVAL if block is not an active memory chunk previously returned by evl_alloc_block().
This call is a variant of evl_check_block() which does NOT serialize callers when accessing the heap. As a result, this call is thread-unsafe.
Return the raw size of the memory storage associated with heap. This size includes the storage which may have been further added to the heap by calling evl_extend_heap().
This routine may be called for any type of heap, serialized or not.
The in-memory heap descriptor previously constructed by evl_init_heap().
Return the raw size (in bytes) of the memory storage associated with heap.
Return the user (or payload) size of the memory storage associated with heap. This size includes the payload storage which may have been further added to the heap by calling evl_extend_heap(). This is the actual amount of bytes available for storing user data, which is lesser than the raw heap size since it does not account for the meta-data.
This routine may be called for any type of heap, serialized or not.
The in-memory heap descriptor previously constructed by evl_init_heap().
Return the user size (in bytes) of the memory storage associated with heap.
Return the amount of space already consumed from the user (or payload) area.
This routine may be called for any type of heap, serialized or not.
The in-memory heap descriptor previously constructed by evl_init_heap().
Return the amount of space (in bytes) consumed within heap. This value is lower or equal to the user (or payload) size.
