Challenges and problems with memory fragmentation

[bugcrazy]

About the issues raised in this ticket about fragmentation.

This article has a test for fragmentation:

https://www.linkedin.com/blog/engineering/infrastructure/taming-memory-fragmentation-in-venice-with-jemalloc

"Allocations are done via brk() and others via mmap(). Smaller, manageable allocations are done via brk(), while larger ones are handled via an mmap() call. Knowing how this worked, I created a bit of simple C code with a pathological pattern. It would allocate objects in two waves, and then it would delete the earlier allocations while keeping around the ones that came later. This renders the address range where they would be allocated only half-utilized by the process, but still uses the memory of all allocations made thus far.

You can watch this in action with the following code and top (though the behavior may differ slightly depending on your system’s allocator):"

https://gist.github.com/ZacAttack/8c67b998c90afdb19c715dfe327112d2/raw/e18aede445520c8762c38034e5f95feab522cd05/heap-fragmentor.cpp

There is another article talking about fragmentation and a link to the reference article about RTOS fragmentation, maybe it will help:

https://www.researchgate.net/profile/Nikola-Zlatanov/publication/295010953_Dynamic_Memory_Allocation_and_Fragmentation/links/56c6577008ae03b93dda5421/Dynamic-Memory-Allocation-and-Fragmentation.pdf

https://web.archive.org/web/20120919162407/http://www.edn.com/design/systems-design/4333346/Handling-memory-fragmentation

[bugcrazy]

This article talks a little about 32-bit and 64-bit systems, the tests are Windows applications, they run on Wine, there is a lot explained about memory fragmentation:

https://www.softwareverify.com/blog/memory-fragmentation-your-worst-nightmare/

[TheTechsTech]

For me to act on something I need to experience the issue. In fact, and unfortunately https://lukasatkinson.de/2024/allocator-testing/ mentions mimalloc, which includes a stress test. I have added it here, but it produces mostly the same fragmentation results as mimalloc. It's still an usage pattern.

Anyway, my recent fixes and issues with this library has concluded in fork https://github.com/zelang-dev/tinycc

[bugcrazy]

For me to act on something I need to experience the issue. In fact, and unfortunately https://lukasatkinson.de/2024/allocator-testing/ mentions mimalloc, which includes a stress test. I have added it here, but it produces mostly the same fragmentation results as mimalloc. It's still an usage pattern.

Anyway, my recent fixes and issues with this library has concluded in fork https://github.com/zelang-dev/tinycc

There is this article explaining types of fragmentation: https://michael-s-yao.github.io/computing-systems/malloc/#fragmentation

Fragmentation problems are more evident on 32-bit systems, mimalloc has problems on 32-bit systems: https://github.com/microsoft/mimalloc/issues/218 and https://github.com/microsoft/mimalloc/issues/882

This article talks about the mimalloc problem on 32-bit systems:

https://ayende.com/blog/188001-C/reviewing-mimalloc-part-ii

"Indeed, in _mi_os_reset() they will explicitly ask the OS to throw the memory away by calling MADV_FREE or MEM_RESET. I find this interesting, because this let the OS know that the memory can be thrown away, but the allocation still persists. I’m currently looking into some fragmentation issues in 32bits, which won’t be helped by this scenario. Then again, I don’t think that mimalloc is primarily intended for 32 bits systems (I can see code handling 32 bits, but I don’t think this is the primary use case or that 32 bits had a lot of attention)."

Memory leak problems still occur in mimalloc under heavy use: https://pwy.io/posts/mimalloc-cigarette/

Haiku has these 2 tickets that are interesting to look into regarding issues with hoad2 allocator: https://dev.haiku-os.org/ticket/18603 and https://dev.haiku-os.org/ticket/17226 https://dev.haiku-os.org/ticket/15996

[TheTechsTech]

I understand the problem now, but i will not be coming up with a solution. It’s an issue with allocation in general, stdlib malloc just worst with some usage patterns, and using custom/developing one, might solve it some.

Haiku devs would need to submit PR if they plan on using this fork, but it seems they have moved on.

I have other things to work on. My use cases does not have the problem.

Anyway, I don’t see the rpmalloc finding, tests and results links. Anything other than that is worthless.