Is malloc configuration and memory reservation needed when paired with a non-constant time memory allocator?

[shuhaowu]

My understanding is that the glibc allocator is not a constant time allocator. In this case, any malloc call could take a large amount of time either because:

1. A page fault is triggered as the allocator calls brk/sbrk/mmap.
2. The allocator itself is taking O(N) time.

In the examples for this repo, we configure malloc such that it doesn't give back memory upon free and do not use mmap (so free won't immediately munmap it). Is this needed? It doesn't really address the second problem if one chooses to malloc during the RT sections of the code.

Further, we also show reserving some heap memory, which when coupled with the above malloc configuration, effectively means we reserve a (large) amount of heap space that is monotonically increasing. However, since the allocator is not constant time, there appears to be no guarantee of anything.

So the questions are:

1. Is the memory allocation configuration needed?
2. Do we need to reserve memory?
3. Should we switch to an O(1) allocator?

This is not that big of a deal, what we're doing here doesn't hurt. It might "help" lower latency in the average case (if you use malloc during RT), although likely it does make the worst case latency harder to detect (as you have to trigger the O(N) behavior from the allocator to a point where you overrun your deadline).

cc: @carlossvg

[carlossvg]

@shuhaowu I think it's still needed to avoid page faults. Note with the minimal_memory_lock we example aims to show how to avoid latencies caused by a memory swap out but it doesn't mean this is just what you need to do with respect to memory allocations. My idea was to address each issue in separate examples.

1. Is the memory allocation configuration needed?
   • Yes, a page fault will be generated when you access memory that is not mapped in the physical RAM. This includes the memory from the stack too.
2. Do we need to reserve memory?
   • This shouldn't be necessary if the application doesn't allocate dynamically in runtime. But, if this is not the case, we may see page faults. If the allocator allows you to take memory that you already allocated (so it's already locked) then you won't need to reserve additional memory. I'm not sure how the TSLF allocator works but a memory pool-based allocator would work for this case. See see https://www.youtube.com/watch?v=l14Zkx5OXr4
3. Should we switch to an O(1) allocator?
   • Yes, as you said, calling malloc or similar syscalls it's not deterministic. However, note this is an additional problem apart from the page faults. IMO we should deal with this in a separate example. See https://github.com/ros-realtime/ros2-realtime-examples/tree/rolling-experimental/minimal_memory_allocator

I can create a PR for minimal_memory_allocator but the example will be incomplete because the use of memory allocators needs to be reworked: http://togithub.com/ros2/rosidl/issues/566

[shuhaowu]

Thanks for the detailed response. I agree that mlockall is absolutely necessary to avoid swapping. I tend to call that "memory locking" as it is not really related to the allocator. Sorry for the confusing terminology.

I'm more worried about telling people to reserve memory and configure malloc to not use mmap and give memory back to the system on free without also telling people to subsitute the glibc allocator (the usual default) with an O(1)/real-time-compatible allocator. It seems to me that if we used the glibc allocator, only reserving memory and configuring malloc would not be sufficient, as the glibc allocator seem to have a few non-deterministic/non-constant steps¹.

If someone can write a RT program that has all heap memory already allocated before entering the RT sections, then it seems to me that reserving memory and configuring malloc is just extra steps that would not be helpful. That said, I suppose it's not harmful either.

Having a separate example might be OK, but I fear that having the memory locking example also reserve memory and configure malloc in addition to mlockall may be misleading? I don't have too strong opinions on this tho. This is just something that came up as I'm reviewing this material for my blog posts.

Footnotes

1. This step sounds suspiciously non-determinstic during free, from the malloc internals docs: "If the chunk is large enough, coalesce any fastbins and see if the top chunk is large enough to give some memory back to the system. Note that this step might be deferred, for performance reasons, and happen during a malloc or other call". That said, it might be O(1) but just not documented as such. ↩