赵占旭的博客

[转]Cisco VPP内存管理

注:本文是转载,但不是100%的转载,可能稍微有些出入,原文地址点击这里

vec变长数组


avatar

len是数组元素个数,不是字节长度。每个数组元素都看作是等大小。
自定义头部后接vec 组合使用。组合vec将引申出其他内存管理结构。

_vec_find(v)

v指向数据部分,宏返回vec头部地址。

_vec_round_size(s)

s按sizeof (uword)大小,向上对齐。

vec_header_bytes (uword header_bytes)

自定义头部+vec 组合这种模型下,header_bytes代表自定义头部大小。函数返回自定义头部+vec总长度,按sizeof (vec_header_t)向上对齐。

vec_header (void *v, uword header_bytes)

自定义头部+vec 组合,按sizeof (vec_header_t)向上对齐这种模型下,v指向数据部分地址,header_bytes代表自定义头部大小,返回自定义头部地址。

vec_header_end (void *v, uword header_bytes)

自定义头部+vec 组合,按sizeof (vec_header_t)向上对齐这种模型下,v指向自定义头部地址,header_bytes代表自定义头部大小,返回数据部分地址。

vec_aligned_header (void *v, uword header_bytes, uword align)

自定义头部+vec 组合,按align向上对齐这种模型下,v指向数据部分地址,header_bytes代表自定义头部大小,返回自定义头部地址。

vec_aligned_header_end (void *v, uword header_bytes, uword align)

自定义头部+vec 组合,按align向上对齐这种模型下,v指向自定义头部地址,header_bytes代表自定义头部大小,返回数据部分地址。

_vec_len(v)

v指向数据部分,返回vec头部的vec_header_t->len

vec_len(v)

v指向数据部分,v等于null时返回0,否则返回vec头部的vec_header_t->len

vec_reset_length(v)

v指向数据部分,vec头部的vec_header_t->len置0。

vec_bytes(v)

v指向数据部分,返回数据部分总字节大小。

vec_capacity(v,b)

avatar

v指向data起始地址,b代表user_header大小,返回该mheap_elt_t字节大小,即vec的最大可占用内存。博主觉得该函数放在这里破坏了该头件的独立性。

vec_max_len(v)

类似vec_capacity(v,b)内存布局,v指向data起始地址,返回该vec可容纳最大数据块数目。

vec_end(v)

v指向data起始地址,返回vec数据部分末尾的下一个字节。

vec_is_member(v,e)

v指向data起始地址,返回e是否在该vec地址范围内。

vec_elt_at_index(v,i)

v指向data起始地址,返回第i个数据块的地址。

vec_elt(v,i)

v指向data起始地址,返回第i个数据块的内容。

vec_foreach(var,vec) vec_foreach_backwards(var,vec) vec_foreach_index(var,v)

迭代宏

mheap


mheap整体视图

avatar

注意每个elt大小不一定相等。这里的vec_header_t把后面数据看成一个字节一个字节的元素,因此vec->len实际是整个数据部分字节长度。

mheap_elt_t视图

avatar

基本函数操作在mheap_bootstrap.h中。该头文件基本函数,结合上文内容很容易理解,这里不再详细叙述。

mheap.c中会对上图基本结构更近一步索引管理,也是mheap的核心部分。

avatar

mheap_maybe_lock (void *v) mheap_maybe_unlock (void *v)

自旋锁加锁解锁函数,如果是持有锁的本CPU再次进入,可以无条件获取锁。

mheap_get_aligned (void v, uword n_user_data_bytes, uword align, uword align_offset, uword offset_return)

mheap内存分配接口函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
void *mheap_get_aligned (void *v, uword n_user_data_bytes,
uword align, uword align_offset, uword * offset_return)
{
...

//align至少是mheap_elt_t大小,并且是2的幂
align = clib_max (align, STRUCT_SIZE_OF (mheap_elt_t, user_data[0]));
align = max_pow2 (align);

...

//各种对齐,确保mheap_elt_t头部和数据部分都是STRUCT_SIZE_OF (mheap_elt_t, user_data[0])
//之后再用专门章节详细分析数据结构对齐背后的作者设计目的
n_user_data_bytes = clib_max (n_user_data_bytes, MHEAP_MIN_USER_DATA_BYTES);
n_user_data_bytes =
round_pow2 (n_user_data_bytes,
STRUCT_SIZE_OF (mheap_elt_t, user_data[0]));

if (!v)
v = mheap_alloc (0, 64 << 20);//分配完整的一个mheap结构

mheap_maybe_lock (v);

h = mheap_header (v);

if (h->flags & MHEAP_FLAG_VALIDATE)
mheap_validate (v);//遍历mheap的空闲块链表,验证是否正确链接。

/* First search free lists for object. */
//从空闲块链表中获取数据块
offset =
mheap_get_search_free_list (v, &n_user_data_bytes, align, align_offset);

h = mheap_header (v);

/* If that fails allocate object at end of heap by extending vector. */
if (offset == MHEAP_GROUNDED && _vec_len (v) < h->max_size)
{
//如果现有空闲块没有满足要求的块,则从mheap中新分配块
//注意h->max_size代表该mheap最大内存量,_vec_len (v)代表目前使用量
v = mheap_get_extend_vector (v, n_user_data_bytes, align, align_offset, &offset);
//mheap_get_extend_vector()并不会导致mheap重新分配,博主认为下面重新计算h毫无必要
h = mheap_header (v);
//如果扩充成功则统计值加1
h->stats.n_vector_expands += offset != MHEAP_GROUNDED;
}

...
}
1
2
3
4
5
6
7
8
9
10
11
void *mheap_alloc (void *memory, uword size)
{
...

//这里指的是利用cpu的SIMD向量指令加快缓存块的cache查找,之后会详细介绍
#ifdef CLIB_HAVE_VEC128
flags |= MHEAP_FLAG_SMALL_OBJECT_CACHE;
#endif

return mheap_alloc_with_flags (memory, size, flags);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
void *mheap_alloc_with_flags (void *memory, uword memory_size, uword flags)
{
...

if (!memory)
{
//通常用的是UNIX模式,该分配函数将mmap()匿名内存使用
memory = clib_mem_vm_alloc (memory_size);

...
}

//把memory向上对mheap_page_size 大小对齐
am = pointer_to_uword (memory);
av = mheap_page_round (am);
//计算对齐后的mheap头部地址
v = uword_to_pointer (av, void *);
h = mheap_header (v);
ah = pointer_to_uword (h);
//mheap头部地址小于memory起始地址,则增加一个mheap_page_size。
//这样mheap头部地址既在mmap()分配的内存范围中,也满足对齐要求。
while (ah < am)
ah += mheap_page_size;

h = uword_to_pointer (ah, void *);
v = mheap_vector (h);

//size代表mheap数据部分大小
size = memory + memory_size - v;

...

//虽然不解除映射也不会影响性能。但是这样好处是一旦访问了未分配的内存会导致段错误,提示开发人员编码错误
if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
mheap_vm (v, MHEAP_VM_UNMAP | MHEAP_VM_ROUND_UP,
(clib_address_t) v, h->max_size);

//MHEAP_GROUNDED代表该bin下没有空闲数据块,值为~0。所以这里用0xFF初始化。
memset (h->first_free_elt_uoffset_by_bin, 0xFF,
sizeof (h->first_free_elt_uoffset_by_bin));

return v;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
static uword mheap_get_search_free_list (void *v,
uword * n_user_bytes_arg, uword align, uword align_offset)
{
...

//计算bin值,用来索引对应大小空闲块链表
bin = user_data_size_to_bin_index (n_user_bytes);

//如果请求的是满足条件的块,则从一个额外的cache中获取
//避免了搜索空闲块链表开销,还可以利用CPU的SIMD向量指令来加速匹配。
if (MHEAP_HAVE_SMALL_OBJECT_CACHE
&& (h->flags & MHEAP_FLAG_SMALL_OBJECT_CACHE)
&& bin < 255
&& align == STRUCT_SIZE_OF (mheap_elt_t, user_data[0])
&& align_offset == 0)
{
//cache中寻找数据块,之后会详细分析
uword r = mheap_get_small_object (h, bin);
h->stats.n_small_object_cache_attempts += 1;
if (r != MHEAP_GROUNDED)
{
h->stats.n_small_object_cache_hits += 1;
return r;
}
}

//h->non_empty_free_elt_heads是一个位图,记录了对应bin链表是否为空
for (i = bin / BITS (uword); i < ARRAY_LEN (h->non_empty_free_elt_heads); i++)
{
uword non_empty_bin_mask = h->non_empty_free_elt_heads[i];

//把比bin小的位置的位图略掉
if (i == bin / BITS (uword))
non_empty_bin_mask &= ~pow2_mask (bin % BITS (uword));

//foreach_set_bit()从右往左遍历每个bit,为1的bit调用mheap_get_search_free_bin()
//foreach_set_bit()中first_set (uword x)用来计算从右算第一个为1的bit代表的数
foreach_set_bit (bi, non_empty_bin_mask, (
{
uword r = mheap_get_search_free_bin (v,
bi + i * BITS(uword),
n_user_bytes_arg,
align,
align_offset);
if (r != MHEAP_GROUNDED)
return r;
}
));
}

return MHEAP_GROUNDED;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/*
* 如果每次都是计算bin值再从链表中找空闲块就太麻烦了
* 对满足特定条件块,也应该是vpp使用频率最多的那种类型的块做了个cache
* 只需要计算bin值就能直接得到可用空闲块。该函数就是干这事。
*/
always_inline uword mheap_get_small_object (mheap_t * h, uword bin)
{
/*
* cache中c->bins.as_u8数组每个元素记录了(bin+1)
* 为0代表该位置没有空闲块。c->offsets记录对应bin的空闲块。
* mheap_small_object_cache_t *c = &h->small_object_cache;
* 查找c->bins.as_u8数组中,所有值为(bin+1)的索引组成的位图
*/
uword mask = mheap_small_object_cache_mask (c, bin + 1);
uword offset = MHEAP_GROUNDED;

//如果位图不为0,说明有空闲块,查找位图最左边那个为1bit的索引,
//返回对应的c->offsets值,即可用空闲块。
if (mask)
{
uword i = min_log2 (mask);
uword o = c->offsets[i];
ASSERT (o != MHEAP_GROUNDED);
c->bins.as_u8[i] = 0;
offset = o;
}

return offset;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
always_inline uword mheap_small_object_cache_mask (
mheap_small_object_cache_t * c, uword bin)
{
uword mask;

//本函数依赖于CPU支持向量指令。
#if !defined (CLIB_HAVE_VEC128) || defined (__ALTIVEC__)
mask = 0;
#else
//返回一个由16字节组成的向量,每个字节的值都是bin
u8x16 b = u8x16_splat (bin);

ASSERT (bin < 256);

/*
* u8x16_is_equal()比较两个128bit位向量,每个字节进行对比,
* 如果相等,返回字节为1,一共返回16个字节,组成一个返回值128bit向量。
* u8x16_compare_byte_mask()把返回的128bit向量转化成位图,共16个bit位图
*/
#define _(i) ((uword) u8x16_compare_byte_mask (
u8x16_is_equal (b, c->bins.as_u8x16[i])) << (uword) ((i)*16))
mask = _(0) | _(1);
if (BITS (uword) > 32)
mask |= _(2) | _(3);
#undef _

#endif
//32位系统返回的是32bit位图,64位系统返回64bit位图
return mask;
}

/*
* 该函数搜索bin对应的空闲块链表。找到一个大小满足要求的空闲块是很容易的,
* 本函数额外大量代码花在了满足空闲块的对齐要求上。
* align:首地址相对于heap偏移对齐,align_offset:首地址对齐后,再向左做个偏移。
* 分配内存时从对应的slot中查找,值得注意的是查找算法为了满足参数中对齐要求,
* 很有可能从空闲块中间部分分配内存,这样首尾部分空闲块重新链入新的slot。
* 一切的一切都是为了数据对齐。如果分配的内存是一个带头部的数据结构,例如vec+data类型。
* 那么分配内存时需要把头部大小作为align_offset参数,使数据部分满足起始地址align对齐。
*/

avatar

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
static uword mheap_get_search_free_bin (void *v,
uword bin, uword * n_user_data_bytes_arg,
uword align, uword align_offset)
{
...

//o0,f0是用于首部,f0,f1用于尾部,lo_free_usize切分后首部空间,hi_free_usize切分后尾部空间
word o0, o1, f0, f1, search_n_user_data_bytes;
word lo_free_usize, hi_free_usize;

...

/* Find an object that is large enough with correct alignment at given alignment offset. */
while (1)
{
...
//f0指向原始块首部地址偏移,f1指向原始块尾部地址偏移
f0 = ((void *) e->user_data - v);
f1 = f0 + this_object_n_user_data_bytes;

//从尾部往左分配目标块,o0指向首部偏移并且满足对齐要求
o0 = ((f1 - search_n_user_data_bytes) & ~(align - 1)) - align_offset;
//o0比f0还小了,右偏移一个align
while (o0 < f0)
o0 += align;

//确保切分后首部空闲块至少有MHEAP_ELT_OVERHEAD_BYTES大小,这是要给切去的块做头部的
while (1)
{
lo_free_usize = o0 != f0 ? o0 - f0 - MHEAP_ELT_OVERHEAD_BYTES : 0;
if (o0 <= f0 || lo_free_usize >= (word) MHEAP_MIN_USER_DATA_BYTES)
break;
//越偏移lo_free_usize越小,什么鬼,博主强烈认为这是bug,应该是+=
o0 -= align;
}

//o0~o1之间就是我们要找的内存了,大小,对齐性都满足
o1 = o0 + search_n_user_data_bytes;

...
}

found:
...

//从中间切开得到我们要的内存,尾部如果太小,
//就不单独做成空闲块了,直接给我们用。
if (hi_free_usize < (word) MHEAP_MIN_USER_DATA_BYTES)
{
search_n_user_data_bytes += f1 - o1;
o1 = f1;
hi_free_usize = 0;
}

//切去的内存mmap下
if (!(h->flags & MHEAP_FLAG_DISABLE_VM))
{
...
}

...

//切分后首部块重新链入bin表
if (lo_free_usize > 0)
{
...
}

mheap_elt_set_size (v, o0, search_n_user_data_bytes, /* is_free */ 0);

//切分后尾部块重新链入bin表
if (hi_free_usize > 0)
{
...
}

//分配的elt的数据部分大小
*n_user_data_bytes_arg = search_n_user_data_bytes;

h->stats.free_list.n_objects_found += 1;

//返回分配的elt的数据部分偏移值
return o0;
}

user_data_size_to_bin_index (uword n_user_data_bytes)
空闲mheap_elt_t按照数据部分大小分类链接到不同slot中。该函数计算bin值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
always_inline uword user_data_size_to_bin_index (uword n_user_data_bytes)
{
...

//n_user_data_bytes至少要能包含mheap_elt_t头部
n_user_data_bytes = clib_max (n_user_data_bytes, MHEAP_MIN_USER_DATA_BYTES);

...

//除去头部的纯数据部分长度,换算成占用word个数,即为bin值
small_bin = n_user_data_words -
(MHEAP_MIN_USER_DATA_BYTES / MHEAP_USER_DATA_WORD_BYTES);

large_bin =
MHEAP_N_SMALL_OBJECT_BINS + max_log2 (n_user_data_bytes) -
MHEAP_LOG2_N_SMALL_OBJECT_BINS;
//1 ~ MHEAP_N_SMALL_OBJECT_BINS每个值对应单独bin
//>= MHEAP_N_SMALL_OBJECT_BINS多个值映射到一个bin中。
//可见,分配内存越小,越能精准快速定位到可选空闲块。
return small_bin < MHEAP_N_SMALL_OBJECT_BINS ? small_bin : large_bin;
}

vector


实际使用的缓存一般是如下结构:
avatar
user_header指具体数据结构头部,比如:mhash_t,pool_header_t等等

注意:所有文章非特别说明皆为原创。为保证信息与源同步,转载时请务必注明文章出处!谢谢合作 :-)

原始链接:http://zhaozhanxu.com/2016/10/20/VPP/2016-10-20-VPP-mheap/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。