Large分配

5.1.3.2 Large分配

大于3/4的page_size(4KB)且小于等于511个page_size的内存申请,也就是一个chunk的大小够用(之所以是511个page而不是512个是因为第一个page始终被chunk结构占用),如果申请多个page的话 分配的时候这些page都是连续的

static zend_always_inline void *zend_mm_alloc_large(zend_mm_heap *heap, size_t size ZEND_FILE_LINE_DC ZEND_FILE_LINE_ORIG_DC)
{
    //根据size大小计算需要分配多少个page
    int pages_count = (int)ZEND_MM_SIZE_TO_NUM(size, ZEND_MM_PAGE_SIZE);

    //分配pages_count个page
    void *ptr = zend_mm_alloc_pages(heap, pages_count, ...);

    ...

    return ptr;
}

进一步看下zend_mm_alloc_pages,这个过程比较复杂,简单描述的话就是从第一个chunk开始查找当前chunk下是否有pages_count个连续可用的page,有的话就停止查找,没有的话则接着查找下一个chunk,如果直到最后一个chunk也没找到则重新分配一个新的chunk并插入chunk链表,这个过程中最不好理解的一点在于如何查找pages_count个连续可用的page,这个主要根据 chunk->free_map 实现的,在看具体执行过程之前我们先解释下 free_map 的作用:

我们已经知道每个chunk由512个page组成,而不管是large分配还是small分配,其分配的最小粒子都是page(small也是先分配1个或多个page然后再进行的切割),所以需要有一个数组来记录每个page是否已经分配,free_map的作用就是标识当前chunk下各page的分配与否,比较特别的是free_map并不是512大小的数组,因为需要记录的信息非常简单,只需要一个bit位就够了,所以free_map就用长整形的各bit位来记录的(实际就是bitmap),不同位数的机器长整形大小不同,因此在32、64位下16或8个长整形就够512bit了(每个byte等于8bit,长整形为4byte或8byte),当然这么做并仅仅是节省空间,更重要的作用是可以提高查询效率 。

    typedef zend_ulong zend_mm_bitset;    /* 4-byte or 8-byte integer */
    #define ZEND_MM_BITSET_LEN      (sizeof(zend_mm_bitset) * 8)       /* 32 or 64 */
    #define ZEND_MM_PAGE_MAP_LEN    (ZEND_MM_PAGES / ZEND_MM_BITSET_LEN) /* 16 or 8 */

    typedef zend_mm_bitset zend_mm_page_map[ZEND_MM_PAGE_MAP_LEN];     /* 64B */

`heap->free_map`实际就是:__zend_ulong free_map[16 or 8]__,以 __free_map[8]__ 为例,数组中的8个数字分别表示:0-63、64-127、128-191、192-255、256-319、320-383、384-447、448-511 page的分配与否,比如当前chunk的page 0、page 2已经分配,则:`free_map[0] = 5`:

//5:
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000101

free_map

接下来看下zend_mm_alloc_pages的操作:

static void *zend_mm_alloc_pages(zend_mm_heap *heap, int pages_count ZEND_FILE_LINE_DC ZEND_FILE_LINE_ORIG_DC)
{
    zend_mm_chunk *chunk = heap->main_chunk;
    int page_num, len;

    //从第一个chunk开始查找可用page
    while (1) {
        //当前chunk剩余page总数已不够
        if (UNEXPECTED(chunk->free_pages < pages_count)) {
            goto not_found;
        }else{ //查找当前chunk是否有pages_count个连续可用的page
            int best = -1; //已找到可用page起始页
            int best_len = ZEND_MM_PAGES; //已找到chunk的page间隙大小,这个值尽可能接近page_count
            int free_tail = chunk->free_tail;
            zend_mm_bitset *bitset = chunk->free_map;
            zend_mm_bitset tmp = *(bitset++); // zend_mm_bitset tmp = *bitset;  bitset++ 这里是复制出的,不会影响free_map
            int i = 0; 

            //下面就是查找最优page的过程,稍后详细分析
            //find best page
        }

not_found:
        if (chunk->next == heap->main_chunk) { //是否已到最后一个chunk
get_chunk:
            ...
        }else{
            chunk = chunk->next;
        }
    }

found: //找到可用page,page编号为page_num至(page_num + pages_count)
    /* mark run as allocated */
    chunk->free_pages -= pages_count;
    zend_mm_bitset_set_range(chunk->free_map, page_num, pages_count); //将page_num至(page_num + pages_count)page的bit标识位设置为已分配
    chunk->map[page_num] = ZEND_MM_LRUN(pages_count); //map为两个值的组合值,首先表示当前page属于哪种类型,其次表示包含的page页数
    if (page_num == chunk->free_tail) {
        chunk->free_tail = page_num + pages_count;
    }
    return ZEND_MM_PAGE_ADDR(chunk, page_num);
}

查找过程就是从第一个chunk开始搜索,如果当前chunk没有合适的则进入下一chunk,如果直到最后都没有找到则新创建一个chunk。

注意:查找page的过程并不仅仅是够数即可,这里有一个标准是:申请的一个或多个的page要尽可能的填满chunk的空隙 ,也就是说如果当前chunk有多块内存满足需求则会选择最合适的那块,而合适的标准前面提到的那个。

最优page的检索过程

  • step1: 首先从第一个page分组(page 0-63)开始检查,如果当前分组无可用page(即free_map[x] = -1)则进入下一分组,直到当前分组有空闲page,然后进入step2
  • step2: 当前分组有可用page,首先找到第一个可用page的位置,记作page_num,接着__从page_num开始向下找第一个已分配page的位置,记作end_page_num,这个地方需要注意,如果当前分组剩下的page都是可用的则会进入下一分组接着搜索__,直到找到为止,这里还会借助chunk->free_tail避免无谓的查找到最后分组
  • step3: 根据上一步找到的page_num、end_page_num可计算得到当前可用内存块大小为len个page,然后与申请的page页数(page_count)比较
    • step3.1: 如果len=page_count则表示找到的内存块符合申请条件且非常完美,直接从page_num开始分配page_count个page
    • step3.2: 如果len>page_count则表示找到的内存块符合条件且空间很充裕,暂且记录下len、page_num,然后继续向下搜索,如果有更合适的则用更合适的替代
    • step3.3: 如果len

下面从一个例子具体看下,以64bit整形为例,假如当前page分配情况如下图-(1)(group1全部已分配;group2中page 67-68、71-74未分配,其余都已分配;group3中除page 128-129、133已分配外其余都未分配),现在要申请3个page:

free_map_1

检索过程:

  • a.首先会直接跳过group1,直接到group2检索
  • b.在group2中找到第一个可用page位置:67,然后向下找第一个不可用page位置:69,找到的可用内存块长度为2,小于3,表示此内存块不可用,这时会将page 67-68标识为已分配,图-(2)
  • c.接着再次在group2中查找到第一个可用page位置:71,然后向下找到第一个不可用page位置:75,内存块长度为4,大于3,表示找到一个符合的位置,虽然已经找到可用内存块但并不"完美",先将这个并不完美的page_num及len保存到best、best_len,如果后面没有比它更完美的就用它了,然后将page 71-74标示为已分配,图-(3)
  • d.再次检索,发现group2已无可用page,进入group3,找到可用内存位置:page 130-132,大小比c中找到的合适,所以最终返回的page就是130-132,图-(4)

page分配完成后会将free_map对应整数的bit位从page_num至(page_num+page_count)置为1,同时将chunk->map[page_num]置为ZEND_MM_LRUN(pages_count),表示page_num至(page_num+page_count)这些page是被Large分配占用的。

联系我们

邮箱 626512443@qq.com
电话 18611320371(微信)
QQ群 235681453

Copyright © 2015-2024

备案号:京ICP备15003423号-3