Re: Xenomai 4 Allocator Fragmentation Questions

[Philippe Gerum <rpm@xenomai.org>]

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.