iOS开发

iOS -- malloc分析(2)

2.10 `segregated_band_grow`分析

boolean_t
segregated_band_grow(nanozone_t *nanozone, nano_meta_admin_t pMeta, size_t slot_bytes, unsigned int mag_index)

{

    用来计算slot_current_base_addr 的联合体

    nano_blk_addr_t u; // the compiler holds this in a register

    uintptr_t p, s;

    size_t watermark, hiwater;

if (0 == pMeta->slot_current_base_addr) { // First encounter?
//利用nano_blk_addr_t 来计算slot_current_base_addr。

        u.fields.nano_signature = NANOZONE_SIGNATURE;

        u.fields.nano_mag_index = mag_index;

        u.fields.nano_band = 0;

        u.fields.nano_slot = (slot_bytes >> SHIFT_NANO_QUANTUM) - 1;

        u.fields.nano_offset = 0;

//根据设置的属性计算 slot_current_base_addr 

        p = u.addr;

        pMeta->slot_bytes = (unsigned int)slot_bytes;

        pMeta->slot_objects = SLOT_IN_BAND_SIZE / slot_bytes;

    } else {

        p = pMeta->slot_current_base_addr + BAND_SIZE; // Growing, so stride ahead by BAND_SIZE


        u.addr = (uint64_t)p;
if (0 == u.fields.nano_band) { // Did the band index wrap?
return FALSE;

        }

assert(slot_bytes == pMeta->slot_bytes);

    }

    pMeta->slot_current_base_addr = p;
//BAND_SIZE = 1 << 21 = 2097152 = 256kb

    mach_vm_address_t vm_addr = p & ~((uintptr_t)(BAND_SIZE - 1)); // Address of the (2MB) band covering this (128KB) slot
if (nanozone->band_max_mapped_baseaddr[mag_index] < vm_addr) {
//如果最大能存储的地址 仍然小于目标地址，则小开辟新的band
#if !NANO_PREALLOCATE_BAND_VM
// Obtain the next band to cover this slot
//// mac 和模拟器 或重新使用
// Obtain the next band to cover this slot
//重新申请新的 band，调用mach_vm_map  从pmap 转换。

        kern_return_t kr = mach_vm_map(mach_task_self(), &vm_addr, BAND_SIZE, 0, VM_MAKE_TAG(VM_MEMORY_MALLOC_NANO),

                MEMORY_OBJECT_NULL, 0, FALSE, VM_PROT_DEFAULT, VM_PROT_ALL, VM_INHERIT_DEFAULT);

void *q = (void *)vm_addr;
if (kr || q != (void *)(p & ~((uintptr_t)(BAND_SIZE - 1)))) { // Must get exactly what we asked for
if (!kr) {
mach_vm_deallocate(mach_task_self(), vm_addr, BAND_SIZE);

            }
return FALSE;

        }
#endif

        nanozone->band_max_mapped_baseaddr[mag_index] = vm_addr;

    }

// Randomize the starting allocation from this slot (introduces 11 to 14 bits of entropy)
if (0 == pMeta->slot_objects_mapped) { // First encounter?

        pMeta->slot_objects_skipped = (malloc_entropy[1] % (SLOT_IN_BAND_SIZE / slot_bytes));

        pMeta->slot_bump_addr = p + (pMeta->slot_objects_skipped * slot_bytes);

    } else {

        pMeta->slot_bump_addr = p;

    }


    pMeta->slot_limit_addr = p + (SLOT_IN_BAND_SIZE / slot_bytes) * slot_bytes;

    pMeta->slot_objects_mapped += (SLOT_IN_BAND_SIZE / slot_bytes);


    u.fields.nano_signature = NANOZONE_SIGNATURE;

    u.fields.nano_mag_index = mag_index;

    u.fields.nano_band = 0;

    u.fields.nano_slot = 0;

    u.fields.nano_offset = 0;

    s = u.addr; // Base for this core.

// Set the high water mark for this CPU's entire magazine, if this resupply raised it.

    watermark = nanozone->core_mapped_size[mag_index];

    hiwater = MAX(watermark, p - s + SLOT_IN_BAND_SIZE);

    nanozone->core_mapped_size[mag_index] = hiwater;

return TRUE;

}

nano_blk_addr_t u 用来计算 slot_current_base_addr 的联合体
利用 nano_blk_addr_t 来计算 slot_current_base_addr
根据设置的属性计算 slot_current_base_addr
如果最大能存储的地址仍然小于目标地址，则小开辟新的band
mac 和模拟器或重新使用
重新申请新的 band，调用 mach_vm_map 从 pmap 转换。

当进入 segregated_band_grow 时，如果当前的 band 不够用，则使用 mach_vm_map 经由 pmap 重新映射物理内存到虚拟内存。

关于通过 nano_blk_addr_t 的联合体结构如下，其每个成员所占的 bit位数 已经写出。

struct nano_blk_addr_s {

    uint64_t                                   

    nano_offset:NANO_OFFSET_BITS,              //17 locates the block

    nano_slot:NANO_SLOT_BITS,                  //4  bucket of homogenous quanta-multiple blocks

    nano_band:NANO_BAND_BITS,                  //17

    nano_mag_index:NANO_MAG_BITS,              //6  the core that allocated this block

    nano_signature:NANOZONE_SIGNATURE_BITS;    //   the address range devoted to us.

};

#endif
// clang-format on

typedef union  {

    uint64_t            addr;
struct nano_blk_addr_s    fields;

} nano_blk_addr_t;

下面通过 LLDB 分析

在 free 的阶段，也是使用如上的方式获取对应的 slot，mag_index。

下面来梳理下 nana_zone 分配过程：

确定当前 cpu 对应的 mag 和通过 size参数 计算出来的 slot ，去对应 chained_block_s 的链表中取已经被释放过的内存区块缓存，如果取到检查指针地址是否有问题，没有问题就直接返回；
初次进行 nano malloc时，nano zon并没有缓存，会直接在 nano zone范围的地址空间上直接分配连续地址内存；
如当前 Band 中当前 Slot 耗尽则向系统申请新的 Band（每个 Band固定大小 2M，容纳了16个128k的槽），连续地址分配内存的基地址、limit地址以及当前分配到的地址由 meta data 结构维护起来，而这些 meta data 则以 Mag、Slot 为维度（Mag个数是处理器个数，Slot是16个）的二维数组形式，放在 nanozone_t 的 meta_data字段中。
流程如下

2.11 `scalable zone(helper_zone)` 分析

在 szone 上分配的内存包括 tiny、small和large 三大类，其中 tiny 和 small 的分配、释放过程大致相同，larg类型有自己的方式管理。同样会通过create_scalable_zone来构造zone。这里不在复述create_scalable_zone`，直接看内存的分配策略

2.12 `szone_malloc_should_clear` 分析

MALLOC_NOINLINE void *
szone_malloc_should_clear(szone_t *szone, size_t size, boolean_t cleared_requested)

{
void *ptr;

    msize_t msize;
//64位 <= 1008B  32位<= 496B
if (size <= SMALL_THRESHOLD) {
// tiny size: <=1008 bytes (64-bit), <=496 bytes (32-bit)
// think tiny

        msize = TINY_MSIZE_FOR_BYTES(size + TINY_QUANTUM - 1);
if (!msize) {

            msize = 1;

        }

        ptr = tiny_malloc_should_clear(&szone->tiny_rack, msize, cleared_requested);

    } else if (size <= szone->large_threshold) {
//64位 <= 128KB      32位 <= 128KB
// small size: <=15k (iOS), <=64k (large iOS), <=128k (macOS)
// think small

        msize = SMALL_MSIZE_FOR_BYTES(size + SMALL_QUANTUM - 1);
if (!msize) {

            msize = 1;

        }

        ptr = small_malloc_should_clear(&szone->small_rack, msize, cleared_requested);

    } else {
// large: all other allocations

        size_t num_kernel_pages = round_page_quanta(size) >> vm_page_quanta_shift;
if (num_kernel_pages == 0) { /* Overflowed */

            ptr = 0;

        } else {

            ptr = large_malloc(szone, num_kernel_pages, 0, cleared_requested);

        }

    }
#if DEBUG_MALLOC
if (LOG(szone, ptr)) {
malloc_report(ASL_LEVEL_INFO, "szone_malloc returned %p\n", ptr);

    }
#endif
/*

     * If requested, scribble on allocated memory.

     */
if ((szone->debug_flags & MALLOC_DO_SCRIBBLE) && ptr && !cleared_requested && size) {
memset(ptr, SCRIBBLE_BYTE, szone_size(szone, ptr));

    }
return ptr;

}

这里以看出在 szone 上分配的内存包括 tiny、small 和large 三大类，我们以 tiny为例 开始下面的分析

2.12 `tiny_malloc_should_clear` 分析

void *
tiny_malloc_should_clear(rack_t *rack, msize_t msize, boolean_t cleared_requested)

{
void *ptr;

    mag_index_t mag_index = tiny_mag_get_thread_index() % rack->num_magazines;
//获取magazine.  magazines 是一个由64个magazine_t组成的数组

    magazine_t *tiny_mag_ptr = &(rack->magazines[mag_index]);

MALLOC_TRACE(TRACE_tiny_malloc, (uintptr_t)rack, TINY_BYTES_FOR_MSIZE(msize), (uintptr_t)tiny_mag_ptr, cleared_requested);

#if DEBUG_MALLOC
if (DEPOT_MAGAZINE_INDEX == mag_index) {
malloc_zone_error(rack->debug_flags, true, "malloc called for magazine index -1\n");
return (NULL);

    }

if (!msize) {
malloc_zone_error(rack->debug_flags, true, "invariant broken (!msize) in allocation (region)\n");
return (NULL);

    }
#endif

SZONE_MAGAZINE_PTR_LOCK(tiny_mag_ptr);

#if CONFIG_TINY_CACHE

    ptr = tiny_mag_ptr->mag_last_free;
//如果开启了tiny 的缓存。
if (tiny_mag_ptr->mag_last_free_msize == msize) {
// we have a winner
//优先查看上次最后释放的区块是否和此次请求的大小刚好相等（都是对齐之后的slot大小），如果是则直接返回。

        tiny_mag_ptr->mag_last_free = NULL;

        tiny_mag_ptr->mag_last_free_msize = 0;

        tiny_mag_ptr->mag_last_free_rgn = NULL;
SZONE_MAGAZINE_PTR_UNLOCK(tiny_mag_ptr);
CHECK(szone, __PRETTY_FUNCTION__);
if (cleared_requested) {
memset(ptr, 0, TINY_BYTES_FOR_MSIZE(msize));

        }
#if DEBUG_MALLOC
if (LOG(szone, ptr)) {
malloc_report(ASL_LEVEL_INFO, "in tiny_malloc_should_clear(), tiny cache ptr=%p, msize=%d\n", ptr, msize);

        }
#endif
return ptr;

    }
#endif /* CONFIG_TINY_CACHE */

while (1) {
//先从freelist 查找

        ptr = tiny_malloc_from_free_list(rack, tiny_mag_ptr, mag_index, msize);
if (ptr) {
SZONE_MAGAZINE_PTR_UNLOCK(tiny_mag_ptr);
CHECK(szone, __PRETTY_FUNCTION__);
if (cleared_requested) {
memset(ptr, 0, TINY_BYTES_FOR_MSIZE(msize));

            }
return ptr;

        }
//从一个后备magazine中取出一个可用region，完整地拿过来放到当前magazine，再走一遍上面的步骤。
if (tiny_get_region_from_depot(rack, tiny_mag_ptr, mag_index, msize)) {
//再次尝试从freelist 中获取

            ptr = tiny_malloc_from_free_list(rack, tiny_mag_ptr, mag_index, msize);
if (ptr) {
SZONE_MAGAZINE_PTR_UNLOCK(tiny_mag_ptr);
CHECK(szone, __PRETTY_FUNCTION__);
if (cleared_requested) {
memset(ptr, 0, TINY_BYTES_FOR_MSIZE(msize));

                }
return ptr;

            }

        }

// The magazine is exhausted. A new region (heap) must be allocated to satisfy this call to malloc().
// The allocation, an mmap() system call, will be performed outside the magazine spin locks by the first
// thread that suffers the exhaustion. That thread sets "alloc_underway" and enters a critical section.
// Threads arriving here later are excluded from the critical section, yield the CPU, and then retry the
// allocation. After some time the magazine is resupplied, the original thread leaves with its allocation,
// and retry-ing threads succeed in the code just above.
if (!tiny_mag_ptr->alloc_underway) {
//如果没有正在申请新的的 regin 操作，则进行申请操作
void *fresh_region;

// time to create a new region (do this outside the magazine lock)
//设置当前正在申请新的 堆

            tiny_mag_ptr->alloc_underway = TRUE;
OSMemoryBarrier();
SZONE_MAGAZINE_PTR_UNLOCK(tiny_mag_ptr);
//申请新的堆                                 1m             

            fresh_region = mvm_allocate_pages_securely(TINY_REGION_SIZE, TINY_BLOCKS_ALIGN, VM_MEMORY_MALLOC_TINY, rack->debug_flags);
SZONE_MAGAZINE_PTR_LOCK(tiny_mag_ptr);

// DTrace USDT Probe
MAGMALLOC_ALLOCREGION(TINY_SZONE_FROM_RACK(rack), (int)mag_index, fresh_region, TINY_REGION_SIZE);

if (!fresh_region) { // out of memory!

                tiny_mag_ptr->alloc_underway = FALSE;
OSMemoryBarrier();
SZONE_MAGAZINE_PTR_UNLOCK(tiny_mag_ptr);
return NULL;

            }
//从最近的一个 region 或者新申请的 region中malloc

            ptr = tiny_malloc_from_region_no_lock(rack, tiny_mag_ptr, mag_index, msize, fresh_region);

// we don't clear because this freshly allocated space is pristine

            tiny_mag_ptr->alloc_underway = FALSE;
OSMemoryBarrier();
SZONE_MAGAZINE_PTR_UNLOCK(tiny_mag_ptr);
CHECK(szone, __PRETTY_FUNCTION__);
return ptr;

        } else {
SZONE_MAGAZINE_PTR_UNLOCK(tiny_mag_ptr);
yield();
SZONE_MAGAZINE_PTR_LOCK(tiny_mag_ptr);

        }

    }
/* NOTREACHED */

}

获取 magazine.
magazines 是一个由 64个magazine_t 组成的数组
如果开启了 tiny 的缓存
优先查看上次最后释放的区块是否和此次请求的大小刚好相等（都是对齐之后的 slot大小），如果是则直接返回。
ptr = tiny_malloc_from_free_list(rack, tiny_mag_ptr, mag_index, msize); 先从 freelist 查找
从一个后备 magazine 中取出一个可用 region，完整地拿过来放到当前 magazine，再走一遍上面的步骤。
void *fresh_region; 如果没有正在申请新的的 regin 操作，则进行申请操作
tiny_mag_ptr->alloc_underway = TRUE; 设置当前正在申请新的堆
fresh_region = mvm_allocate_pages_securely(TINY_REGION_SIZE, TINY_BLOCKS_ALIGN, VM_MEMORY_MALLOC_TINY, rack->debug_flags); 申请新的堆 --- 1M
ptr = tiny_malloc_from_region_no_lock(rack, tiny_mag_ptr, mag_index, msize, fresh_region); 从最近的一个 region 或者新申请的 region 中 malloc

每次调用 free 函数，会直接把要释放的内存优先放到mag_last_free 指针上，在下次 alloc 时，也会优先检查mag_last_free 是否存在大小相等的内存，如果存在就直接返回。

2.14 `tiny_malloc_from_free_list` & `tiny_get_region_from_depot` 分析

tiny_malloc_from_free_list函数的作用是从 free_list 中不断进行各种策略尝试。
从上面的流程可以看出，在查找已经释放的内存缓存，会采用2步缓存查找(策略1，2)，及两步备用内存的开辟(策略3，4)。
当 free_list 流程仍然找不到可以使用内存，就会使用tiny_get_region_from_depot

每一个类型的 rack 指向的 magazines ，都会在下标为-1 , magazine_t 当做备用：depot，该方法的作用是从备用的 depot查找出是否有满足条件的 region 如果存在，更新 depot 和 region 的关联关系，然后在关联当前的magazine_t 和 region。之后在再次重复 free_list 过程

2.15 `mvm_allocate_pages_securely` 的分析

走到这一步，就需要申请新的 heap 了，这里需要理解虚拟内存和物理内存的映射关系。
你其实只要记住两点：vm_map 代表就是一个进程运行时候涉及的虚拟内存，pmap 代表的就是和具体硬件架构相关的物理内存。
重新申请的核心函数为 mach_vm_map ,其概念如图

2.16 `tiny_malloc_from_region_no_lock` 的分析

重新申请了新的内存 (region) 之后，挂载到当前的 magazine下并分配内存。

这个方法的主要作用是把新申请的内存地址，转换为region，并进行相关的关联。及更新对应的 magazine。整个 scalable_zone 的结构体关系，及流程如下

2.17 `nano_zone` 总结

malloc 库会检查指针地址，如果没有问题，则以链表的形式将这些区块按大小存储起来。这些链表的头部放在 meta_data数组 中对应的 [mag][slot]元素中。

其实从缓存获取空余内存和释放内存时都会对指向这篇内存区域的指针进行检查，如果有类似地址不对齐、未释放/多次释放、所属地址与预期的 mag、slot 不匹配等情况都会以报错结束。

2.18 `scalable_zone` 分析

首先检查指针指向地址是否有问题。
如果 last free指针 上没有挂载内存区块，则放到 last free上。
如果有 last free ，置换内存，并把 last free 原有内存区块挂载到 free list上（在挂载的 free list前，会先根据 region 位图检查前后区块是否能合并成更大区块，如果能会合并成一个）。
合并后所在的 region 如果空闲字节超过一定条件，则将把此 region 放到后备的 magazine 中（-1）。
如果整个 region 都是空的，则直接还给系统内核。

三、流程总结

四、拓展补充

malloc_zone_t 提供了一个模板类，或者理解为malloc_zone_t 提供一类接口（高度抽象了alloc一个对象所需要的特征），free，calloc等。
由所有拓展的结构体来实现真正的目标函数。
同上对于上层 Objc，提供了抽象接口(依赖倒置),这样就降低了调用者 (Objc) 与实现模块间的耦合。

作者：Cooci
链接：https://www.jianshu.com/p/ff4e55c9c332

0

2021-04-25

0 个评论

要回复文章请先登录或注册

iOS -- malloc分析(2)

2.10 segregated_band_grow分析

2.11 scalable zone(helper_zone) 分析

2.12 szone_malloc_should_clear 分析

2.12 tiny_malloc_should_clear 分析

2.14 tiny_malloc_from_free_list & tiny_get_region_from_depot 分析

2.15 mvm_allocate_pages_securely 的分析

2.16 tiny_malloc_from_region_no_lock 的分析

2.17 nano_zone 总结

2.18 scalable_zone 分析