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

vec变长数组


请输入图片描述

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)

请输入图片描述

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整体视图

请输入图片描述

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

mheap_elt_t视图

请输入图片描述

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

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

请输入图片描述

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内存分配接口函数。

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;
    }

    ...
}
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);
}
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;
}
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;
}
/*
 * 如果每次都是计算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;
}
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对齐。
 */

请输入图片描述

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值。

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


实际使用的缓存一般是如下结构:
请输入图片描述
user_header指具体数据结构头部,比如:mhash_t,pool_header_t等等。

最后修改:2021 年 08 月 20 日 03 : 44 PM