Malloc¶
概述¶
DPDK EAL提供了类似malloc的内存分配API,通过它可以分配任意大小的大页内存,同时有利于程序移植 (glibc malloc->rte_malloc)。
注解
不要在数据平面代码中使用DPDK malloc,因为它在分配和释放时使用了锁,影响效率;应该使用mempool获取内存。
数据结构¶
主要有2个数据结构:
struct malloc_heap - 用于在每个socket上跟踪空闲内存
每个NUMA节点有一个malloc_heap结构,用于给NUMA节点上的线程分配内存,然而,它无法保证此内存仅被当前NUMA节点所使用。
struct malloc_heap { rte_spinlock_t lock; LIST_HEAD(, malloc_elem) free_head[RTE_HEAP_NUM_FREELISTS]; unsigned alloc_count; size_t total_size; } __rte_cache_aligned;
malloc_heap使用链表来维护空闲内存(free-list),当多个线程都需要访问此链表时,使用锁lock来进行同步;free_head指向free-list的首节点。
另外可以看到,free-list并非只有一个,而是对RTE_HEAD_NUM_FREELISTS(13)个。DPDK根据FREE内存块大小的不同,把它们挂到对应的链表上。
struct malloc_elem - 用于分配和空闲内存跟踪的基本元素
malloc_elem是不同内存块共用的通用首部结构体,它有3种用法:
- normal:做为空闲或已分配内存块的首部
- 在内存块内部作为填充首部(padding header)
- 做为memseg的结束标记
struct malloc_elem { struct malloc_heap* heap; struct malloc_elem* volatile prev; // points to prev elem in memseg LIST_ENTRY(malloc_elem) free_list; // list of free elements in heap const struct rte_memseg* ms; volatile enum elem_state state; uint32_t pad; size_t size; #ifdef RTE_LIBRTE_MALLOC_DEBUG uint64_t header_cookie; // Cookie marking start of data // trailer cookie at start + size #endif } __rte_cache_aligned;
其中,
- heap 用来指回分配此项的malloc_heap,当normal内存块被回收时,将它挂到heap上的空闲内存链表free-list
- prev 指向memseg中紧挨着的前一个节点。当释放内存时,会通过它来检查前一节点是否也可以被free,如果可以,那么当前节点和前一节点会合并成一个大节点
- next_free free_list是一个双向链表节点,它的next指针即next_free,仅用于normal节点,用于把空闲内存块链起来形成free-list
- state 节点状态,共有3个值:FREE,BUSY,和PAD。前两个用于表示normal节点的内存状态,最后一个表示当前节点是pad数据的尾部结构,用于内存对齐。当用于memseg的结束标记时,state置为BUSY,确保在释放内存时不会越过memseg的边界来合并空闲节点
- pad 填充数据的长度。对于normal节点,首部结束地址+pad就是实际数据的起始地址。对于normal节点内部的pad节点,它的pad值与外面normal节点的pad值相同
- size 节点的大小,包括首部长度。对于memseg结束标记,size值为0
Malloc相关数据结构的内部布局如下图所示:
malloc heap初始化¶
在EAL初始化阶段,大页内存的memseg创建好之后,会调用rte_eal_malloc_heap_init()来初始化malloc heap。主要过程有:
- 在每个memseg首部添加state为FREE的节点
- 在每个memseg尾部添加state为BUSY的节点做为结束标记
- 将FREE节点挂到malloc heap的空闲内存链表free-list中
以下3行代码(librte_eal/common/malloc_heap.c: malloc_heap_add_memseg)分别对应这3个过程:
malloc_elem_init(start_elem, heap, ms, elem_size);
malloc_elem_mkend(end_elem, start_elem);
malloc_elem_free_list_insert(start_elem);
在把FREE节点挂到free-list的时候,如前所言,会根据其大小,挂入对应的free-list。
void malloc_elem_free_list_insert(struct malloc_elem *elem)
{
size_t idx;
idx = malloc_elem_free_list_index(elem->size - MALLOC_ELEM_HEADER_LEN);
elem->state = ELEM_FREE;
LIST_INSERT_HEAD(&elem->heap->free_head[idx], elem, free_list);
}
malloc_elem_free_list_index()用于求得链表的索引,从这个函数的代码可以看到DPDK是怎么根据内存块大小来划分13个free-list的。
size_t malloc_elem_free_list_index(size_t size)
{
#define MALLOC_MINSIZE_LOG2 8
#define MALLOC_LOG2_INCREMENT 2
size_t log2;
size_t index;
if (size <= (1UL << MALLOC_MINSIZE_LOG2))
return 0;
log2 = sizeof(size) * 8 - __builtin_clzl(size-1);
index = (log2 - MALLOC_MINSIZE_LOG2 + MALLOC_LOG2_INCREMENT - 1) /
MALLOC_LOG2_INCREMENT;
return (index <= RTE_HEAP_NUM_FREELISTS-1?
index: RTE_HEAP_NUM_FREELISTS-1);
}
过程如下:
- 如果size <= 2^8,则放入free_list[0],否则到2
- 计算log2(size),取整数,比如2^7到2^8之间的数,含2^7,log2值都是7
- 根据log2值,求对应的free_list索引。由于log2步长是2,所以对于n>8,2^n和2^(n+1)会共用一个相同的下标
- 若idx>(13-1),则idx=12。大于等于2^31的全部会放入free_list[12]
注:__builtin_clzl()用于求unsigned long数第一个bit 1前面0的个数。
内存分配¶
核心函数malloc_heap_alloc(librte_eal/common/malloc_heap.c)。
首先从free_list中找到size对应的空闲节点,然后根据需要对此节点做一些处理,比如如果节点的内存大于所需内存,会分裂成两个节点。内存分配是有锁的(heap->lock)。
内存释放¶
核心函数rte_free(librte_eal/common/rte_malloc.c)。
首先从内存地址得到malloc_elem节点首部的地址,然后检查此节点紧挨着的前后是否有FREE内存块,如果有的话则将它们合并成一个FREE内存节点, 添加到free_list。
参考¶
[dpdk_guide_malloc] | DPDK Malloc |