Xenomai 4 Allocator Fragmentation Questions

Xenomai 4 Allocator Fragmentation Questions

[Kevin Strell]

We are currently using Xenomai 4 on an AM69 on our new prototype and
appear to be running into fragmentation issues with the default
allocator while trying to use thread local heaps. After several
seconds of operation our application starts experiencing allocation
failures with evl_alloc_block_unlocked returning NULL. Our heaps are
allocated on reset and we do not extended or otherwise change the size
of the heaps during runtime. The allocated memory in question is
allocated out-of-band and is typically under 100 bytes but
occasionally there are larger allocations. Additionally, we have tried
running the heap_torture test on our platform and the results do not
seem good. Pretty much every test with the +shuffle option is showing
more than 50% fragmentation and many show more than 90%.

We did try the compaction procedure documented on the Xenomai 4
Caveats page but it did not seem to improve our situation. It is
unclear to us when the compaction should be triggered. The
documentation states it needs to happen before mlockall() is called
but evl_init() makes a call to mlockall() and the latter seems like it
needs to be called first.

We have been able to avoid the fragmentation problems by switching to
using the rpmalloc library (https://github.com/mjansson/rpmalloc)
instead of libevl's memory heap services. All that being said, we have
a couple questions about the default Xenomai allocator.

1. Other than the compaction procedure, is there anything we can do
with the default Xenomai allocator to improve the performance in
regards to fragmentation?
2. When is the correct time to run the compaction procedure in regards
to when we should call evl_init()?
3. If the fragmentation is a known issue of the default allocator, is
there any other allocator that is recommended?

Regards,
Kevin Strell

Re: Xenomai 4 Allocator Fragmentation Questions

[Philippe Gerum]

Kevin Strell <kstrell@aerotech.com> writes:

> We are currently using Xenomai 4 on an AM69 on our new prototype and
> appear to be running into fragmentation issues with the default
> allocator while trying to use thread local heaps. After several
> seconds of operation our application starts experiencing allocation
> failures with evl_alloc_block_unlocked returning NULL. Our heaps are
> allocated on reset and we do not extended or otherwise change the size
> of the heaps during runtime. The allocated memory in question is
> allocated out-of-band and is typically under 100 bytes but
> occasionally there are larger allocations. Additionally, we have tried
> running the heap_torture test on our platform and the results do not
> seem good. Pretty much every test with the +shuffle option is showing
> more than 50% fragmentation and many show more than 90%.

I believe that you may be referring to this output of the heap-torture
test specifically:

sorted by: max fragmentation
  HEAPSZ  BLOCKSZ   NRBLKS  AVG-A  AVG-F  MAX-A  MAX-F   OVRH%  FRAG%  FLAGS
     16k       16     1024    1.8    1.9    7.3    4.7    0.0   99.8   +shuffle 
     16k       16     1024    1.8    1.8    5.3    4.3    0.0   99.8   +shuffle +hot
     16k       32      512    1.9    1.9    6.7    4.0    0.0   99.6   +shuffle 
     16k       32      512    1.9    1.9    4.0    4.0    0.0   99.6   +shuffle +hot
     16k       64      256    1.9    1.9    5.0    4.0    0.0   99.2   +shuffle +hot
     16k       64      256    1.9    2.0    7.7    3.7    0.0   99.2   +shuffle 
     16k      128      128    2.0    2.1    6.7    4.0    0.0   93.8   +shuffle 
     16k      128      128    2.0    1.9    4.0    4.0    0.0   93.8   +shuffle +hot

This is expected in the so-called "shuffle" mode, the results are
unfortunately slightly misleading in this case. In this mode, the test
allocates N blocks sequentially from an empty heap, then randomizes the
release of such blocks not to follow the allocation order, so that we
artificially create "holes" all over the map.

When enough blocks have been released (evl_free_block) to amount for
half of the heap size, the test then measures the difference between the
largest block size it is able to allocate next, and the amount of memory
which should be available, in theory. The ratio determines the
fragmentation value in the results above. Clearly, the
randomization/shuffle on free is ruining the coalescence between
released blocks, which shows in the figure.

IOW, heapmem may be subject to fragmentation when an adverse
allocation/deallocation pattern happens, but the one reported by the
test in shuffle mode is extremely unfavorable by design.

>
> We did try the compaction procedure documented on the Xenomai 4
> Caveats page but it did not seem to improve our situation. It is
> unclear to us when the compaction should be triggered. The
> documentation states it needs to happen before mlockall() is called
> but evl_init() makes a call to mlockall() and the latter seems like it
> needs to be called first.
>
> We have been able to avoid the fragmentation problems by switching to
> using the rpmalloc library (https://github.com/mjansson/rpmalloc)
> instead of libevl's memory heap services. All that being said, we have
> a couple questions about the default Xenomai allocator.

The documentation about (system-wide, kernel) memory compaction from the
Caveat section does not apply to heapmem in libevl which is
process-local, operating in fixed-size heaps as defined by the
user. heapmem has no compaction or garbage collection mechanism
whatsoever.

>
> 1. Other than the compaction procedure, is there anything we can do
> with the default Xenomai allocator to improve the performance in
> regards to fragmentation?

Use multiple heaps if possible, to confine the problematic allocation
patterns.

> 2. When is the correct time to run the compaction procedure in regards
> to when we should call evl_init()?

Those are unrelated issues.

> 3. If the fragmentation is a known issue of the default allocator, is
> there any other allocator that is recommended?
>

An allocator which meets real-time requirements while still limiting
external fragmentation to the minimum may be difficult to find because
both goals are somewhat conflicting (notably because garbage collection
may not fit well when it comes to time complexity). You may want to have
a look at respins of the TLSF allocator, some of them were designed to
address the fragmentation issue the original one had - which was the
reason for developing heapmem years ago.

I'm interested by any result in this area, feedback welcome.

-- 
Philippe.

Re: Xenomai 4 Allocator Fragmentation Questions

[Philippe Gerum]

Kevin Strell <kstrell@aerotech.com> writes:

> We have been able to avoid the fragmentation problems by switching to
> using the rpmalloc library (https://github.com/mjansson/rpmalloc)

A note regarding this allocator, which documentation reads as follows
under the "Worst case scenarios" section:

"Since each heap maps a span of memory pages per page type, a thread
that allocates just a few blocks of each size class (16, 32, ...) for
many size classes will commit a memory page for each used size class,
while only using a small fraction of the committed memory. However,
memory pages are committed on demand and blocks are initialized only as
needed, ..."

Assuming that "committing pages" may mean mapping them to the current
address space and/or performing some kind of memcontrol work (msync?),
you may want to make sure that rpmalloc can pre-commit pages, so that
this does not happen in time-critical work loops. Because rpmalloc
operates on a per-thread basis, you would need to ensure this for each
thread attached to the evl core specifically. Failing to do so would
certainly cause those real-time threads to be demoted to the in-band
stage. You may want to check this using the related health monitoring
service [1] (EVL_HMDIAG_SYSDEMOTE).

To sum up, rpmalloc addresses the fragmentation issue by dedicating each
memory page to dealing with a particular block size, for allocation
_and_ release, so it does not have to resort to dynamic garbage
collection. However, in order to meet real-time requirements, you may
want to make sure that alloc and release operations won't ever issue a
regular system call under the hood.

[1] https://v4.xenomai.org/core/user-api/thread/index.html#health-monitoring

-- 
Philippe.

Re: Xenomai 4 Allocator Fragmentation Questions

[Bryan Smith]

Philippe Gerum <rpm@xenomai.org> writes:

> Kevin Strell <kstrell@aerotech.com> writes:
>
> >
> > 1. Other than the compaction procedure, is there anything we can do
> > with the default Xenomai allocator to improve the performance in
> > regards to fragmentation?
>
> Use multiple heaps if possible, to confine the problematic allocation
> patterns.
>
> > 2. When is the correct time to run the compaction procedure in regards
> > to when we should call evl_init()?
>
> Those are unrelated issues.
>
> > 3. If the fragmentation is a known issue of the default allocator, is
> > there any other allocator that is recommended?
> >
>
> An allocator which meets real-time requirements while still limiting
> external fragmentation to the minimum may be difficult to find because
> both goals are somewhat conflicting (notably because garbage collection
> may not fit well when it comes to time complexity). You may want to have
> a look at respins of the TLSF allocator, some of them were designed to
> address the fragmentation issue the original one had - which was the
> reason for developing heapmem years ago.
>
> I'm interested by any result in this area, feedback welcome.

--

> Kevin Strell <kstrell@aerotech.com> writes:
>
> > We have been able to avoid the fragmentation problems by switching to
> > using the rpmalloc library (https://github.com/mjansson/rpmalloc)
>
> A note regarding this allocator, which documentation reads as follows
> under the "Worst case scenarios" section:
>
> "Since each heap maps a span of memory pages per page type, a thread
> that allocates just a few blocks of each size class (16, 32, ...) for
> many size classes will commit a memory page for each used size class,
> while only using a small fraction of the committed memory. However,
> memory pages are committed on demand and blocks are initialized only as
> needed, ..."
>
> Assuming that "committing pages" may mean mapping them to the current
> address space and/or performing some kind of memcontrol work (msync?),
> you may want to make sure that rpmalloc can pre-commit pages, so that
> this does not happen in time-critical work loops. Because rpmalloc
> operates on a per-thread basis, you would need to ensure this for each
> thread attached to the evl core specifically. Failing to do so would
> certainly cause those real-time threads to be demoted to the in-band
> stage. You may want to check this using the related health monitoring
> service [1] (EVL_HMDIAG_SYSDEMOTE).
>
> To sum up, rpmalloc addresses the fragmentation issue by dedicating each
> memory page to dealing with a particular block size, for allocation
> _and_ release, so it does not have to resort to dynamic garbage
> collection. However, in order to meet real-time requirements, you may
> want to make sure that alloc and release operations won't ever issue a
> regular system call under the hood.
>
> [1] https://v4.xenomai.org/core/user-api/thread/index.html#health-monitoring

Thank you for your feedback.

We originally had a process that used a single large heap that was
shared among multiple threads:

* Main thread: allocates upon initialization only.
* Lower-priority thread A: allocates/frees during normal operation.
* Lower-priority thread B: allocates/frees during normal operation.

Memory was allocated using the non-serializing/unlocked libevl heap
API, which was obviously problematic when threads A and B run
concurrently. We have historically avoided the use of mutexes and
similar mechanisms, so we attempted to continue using the unlocked API
with a large heap for the main thread and a smaller heap for one of the
lower-priority threads. The smaller heap was much more likely to be
fully consumed, which is where our concerns about fragmentation came
from.

When reverting to use a single large heap and the serializing libevl
heap API, we haven't seen any issues with memory allocation nor any
concerns about using mutexes. We had to use a small workaround because
there are multiple processes that each use their own `struct evl_heap`,
and the name of the mutex created internally by evl_init_heap() is only
unique within the same process (and not between multiple processes).

 struct evl_heap heap;
 ret = evl_new_mutex(&heap.lock, "heap:%.3d", getpid())
 /* ... */
 ret = evl_init_heap_unlocked(&heap, mem, size);

rpmalloc did end up meeting real-time performance requirements with
the evaluation that we had done, but I believe that we are going to
abandon this evaluation since the libevl serialized heap API works well
for our use case.

Regards,
Bryan

Re: Xenomai 4 Allocator Fragmentation Questions

[Philippe Gerum]

Bryan Smith <bsmith@aerotech.com> writes:

> Kevin Strell <kstrell@aerotech.com> writes:

> struct evl_heap heap;
> ret = evl_new_mutex(&heap.lock, "heap:%.3d", getpid())
> /* ... */
> ret = evl_init_heap_unlocked(&heap, mem, size);

Passing a NULL format should make the core pick a unique default name
for this private element, e.g. evl_new_mutex(&heap.lock, NULL);

> rpmalloc did end up meeting real-time performance requirements with
> the evaluation that we had done, but I believe that we are going to
> abandon this evaluation since the libevl serialized heap API works well
> for our use case.

Ok, good news. Thanks for the feedback.

-- 
Philippe.

Re: Xenomai 4 Allocator Fragmentation Questions

[Bryan Smith]

Philippe Gerum <rpm@xenomai.org> writes:

> Passing a NULL format should make the core pick a unique default name
> for this private element, e.g. evl_new_mutex(&heap.lock, NULL);

I didn't know about that capability, that's very useful. Thanks again.