[DPDK] heap memory fragmentation issue

[Stephen Hemminger]

On Wed, 19 Apr 2023 00:35:31 +0300
Dmitry Kozlyuk <dmitry.kozliuk at gmail.com> wrote:

> Hi,
> 
> 2023-04-12 08:44 (UTC+0000), wuchangsheng (C):
> > When using rte_malloc and rte_free to request and release memory repeatedly, the usage of large pages gradually increases.  
> 
> Do you have a repro?
> 
> > Checking the relevant source code shows that memory requests and releases
> > are started from the head of the freelist chain list of the heap.
> > Memory fragmentation seems to result from this, which is considered because
> > the memory recently released may be in the cache, and requesting this
> > memory at the time of allocation may achieve higher performance?  
> 
> Could you please elaborate?
> DPDK uses "first fit" algorithm to select the free block,
> is that what you mean by "memory fragmentation seems to result from this"?
> 
> > How does the community consider the heap's memory fragmentation issue? Is
> > there a future plan for memory fragmentation optimization?  
> 
> From my experience with a production app, fragmentation is indeed an issue.

The problem is that simple first-fit is often not good enough.
Memory allocation algorithms are much researched area of operating system design.
You will find lots of lectures online like https://www.scs.stanford.edu/15au-cs140/notes/mem_allocation.pdf

If interested, some other malloc libraries:
https://en.wikipedia.org/wiki/C_dynamic_memory_allocation

Glibc https://sourceware.org/glibc/wiki/MallocInternals
Dimalloc
	Small (<256) use simple best fit power of two with splitting
	Medium bitwise trie
	Large use mmap

JeMalloc https://jemalloc.net/
	What FreeBSD uses, avoids fragmentation

Mimalloc https://microsoft.github.io/mimalloc/
	Uses free list sharding (ie free list per page)
	https://www.microsoft.com/en-us/research/uploads/prod/2019/06/mimalloc-tr-v1.pdf

If someone wants to go deeper, then looking into some combination
of these would be good. Some of these already are huge page aware
so probably DPDK could stop reinventing this.