源码解读macOS/iOS Heap

By xia0

源码解读macOS/iOS Heap

关于linux的堆管理已经有很多人写了很多相关的分析,但在mac平台的堆相关的资料却很少。本文由tctf的一道mac平台pwn题目引起,是我对macOS/iOS的堆管理的一些理解,希望有所帮助。

从malloc说起

malloc是我们经常使用的函数,这里也是libmalloc.dylib暴露出来的接口,另外苹果开源了libmalloc代码。所以接下来我们就从源码的角度深入下去。

void *
malloc(size_t size)
{
    void *retval;
    retval = malloc_zone_malloc(default_zone, size);
    if (retval == NULL) {
        errno = ENOMEM;
    }
    return retval;
}

这里实际调用了malloc_zone_malloc函数,传入了default_zone全局变量

static virtual_default_zone_t virtual_default_zone
__attribute__((section("__DATA,__v_zone")))
__attribute__((aligned(PAGE_MAX_SIZE))) = {
    NULL,
    NULL,
    default_zone_size,
    default_zone_malloc,
    default_zone_calloc,
    default_zone_valloc,
    default_zone_free,
    default_zone_realloc,
    default_zone_destroy,
    DEFAULT_MALLOC_ZONE_STRING,
    default_zone_batch_malloc,
    default_zone_batch_free,
    &default_zone_introspect,
    10,
    default_zone_memalign,
    default_zone_free_definite_size,
    default_zone_pressure_relief,
    default_zone_malloc_claimed_address,
};

static malloc_zone_t *default_zone = &virtual_default_zone.malloc_zone;

这里初始化了一个默认的zone,正如名字一样virtual_default_zone其实是一个虚假的zone,接下来是调用malloc_zone_malloc

void *
malloc_zone_malloc(malloc_zone_t *zone, size_t size)
{
    MALLOC_TRACE(TRACE_malloc | DBG_FUNC_START, (uintptr_t)zone, size, 0, 0);

    void *ptr;
    if (malloc_check_start && (malloc_check_counter++ >= malloc_check_start)) {
        internal_check();
    }
    if (size > MALLOC_ABSOLUTE_MAX_SIZE) {
        return NULL;
    }

    ptr = zone->malloc(zone, size);        // if lite zone is passed in then we still call the lite methods


    if (malloc_logger) {
        malloc_logger(MALLOC_LOG_TYPE_ALLOCATE | MALLOC_LOG_TYPE_HAS_ZONE, (uintptr_t)zone, (uintptr_t)size, 0, (uintptr_t)ptr, 0);
    }

    MALLOC_TRACE(TRACE_malloc | DBG_FUNC_END, (uintptr_t)zone, size, (uintptr_t)ptr, 0);
    return ptr;
}

这里调用的ptr = zone->malloc(zone, size);就是default_zone_malloc函数

static void *
default_zone_malloc(malloc_zone_t *zone, size_t size)
{
    zone = runtime_default_zone();

    return zone->malloc(zone, size);
}

这里的runtime_default_zone()很重要,其实这里才是去真正的初始化zone

runtime_default_zone   // inline
----inline_malloc_default_zone  //inline
--------_malloc_initialize_once  //inline 
------------_malloc_initialize()

下面看_malloc_initialize函数,去掉了一些不相干代码

static void
_malloc_initialize(void *context __unused)
{
    MALLOC_LOCK();
    unsigned n;
    malloc_zone_t *zone = NULL;

    ...
    zone = create_scalable_zone(0, malloc_debug_flags);
    malloc_zone_register_while_locked(zone);
    malloc_set_zone_name(zone, DEFAULT_MALLOC_ZONE_STRING);    

    initial_default_zone = zone;

    if (n != 0) { // make the default first, for efficiency
        unsigned protect_size = malloc_num_zones_allocated * sizeof(malloc_zone_t *);
        malloc_zone_t *hold = malloc_zones[0];

        if (hold->zone_name && strcmp(hold->zone_name, DEFAULT_MALLOC_ZONE_STRING) == 0) {
            malloc_set_zone_name(hold, NULL);
        }

        mprotect(malloc_zones, protect_size, PROT_READ | PROT_WRITE);
        malloc_zones[0] = malloc_zones[n];
        malloc_zones[n] = hold;
        mprotect(malloc_zones, protect_size, PROT_READ);
    }

    ...
}

这里主要看create_scalable_zone函数,所以默认的zone实际上就是scalable zone

malloc_zone_t *
create_scalable_zone(size_t initial_size, unsigned debug_flags) {
    return (malloc_zone_t *) create_scalable_szone(initial_size, debug_flags);
}

szone_t *
create_scalable_szone(size_t initial_size, unsigned debug_flags)
{
    szone_t *szone;

    /* get memory for the zone. */
    szone = mvm_allocate_pages(SZONE_PAGED_SIZE, 0, 0, VM_MEMORY_MALLOC);
    if (!szone) {
        return NULL;
    }

    ...

    // Query the number of configured processors.
    // Uniprocessor case gets just one tiny and one small magazine (whose index is zero). This gives
    // the same behavior as the original scalable malloc. MP gets per-CPU magazines
    // that scale (way) better.
    unsigned int max_mags = mag_max_magazines();
    uint32_t num_magazines = (max_mags > 1) ? MIN(max_mags, TINY_MAX_MAGAZINES) : 1;
    rack_init(&szone->tiny_rack, RACK_TYPE_TINY, num_magazines, debug_flags);
    rack_init(&szone->small_rack, RACK_TYPE_SMALL, num_magazines, debug_flags);

#if CONFIG_LARGE_CACHE
    // madvise(..., MADV_REUSABLE) death-row arrivals above this threshold [~0.1%]
    szone->large_entry_cache_reserve_limit = (size_t)(memsize >> 10);

    /* <rdar://problem/6610904> Reset protection when returning a previous large allocation? */
    int32_t libSystemVersion = NSVersionOfLinkTimeLibrary("System");
    if ((-1 != libSystemVersion) && ((libSystemVersion >> 16) < 112) /* CFSystemVersionSnowLeopard */) {
        szone->large_legacy_reset_mprotect = TRUE;
    } else {
        szone->large_legacy_reset_mprotect = FALSE;
    }
#endif

    // Initialize the security token.
    szone->cookie = (uintptr_t)malloc_entropy[0];

    szone->basic_zone.version = 10;
    szone->basic_zone.size = (void *)szone_size;
    szone->basic_zone.malloc = (void *)szone_malloc;
    szone->basic_zone.calloc = (void *)szone_calloc;
    szone->basic_zone.valloc = (void *)szone_valloc;
    szone->basic_zone.free = (void *)szone_free;
    szone->basic_zone.realloc = (void *)szone_realloc;
    szone->basic_zone.destroy = (void *)szone_destroy;
    szone->basic_zone.batch_malloc = (void *)szone_batch_malloc;
    szone->basic_zone.batch_free = (void *)szone_batch_free;
    szone->basic_zone.introspect = (struct malloc_introspection_t *)&szone_introspect;
    szone->basic_zone.memalign = (void *)szone_memalign;
    szone->basic_zone.free_definite_size = (void *)szone_free_definite_size;
    szone->basic_zone.pressure_relief = (void *)szone_pressure_relief;
    szone->basic_zone.claimed_address = (void *)szone_claimed_address;

    /* Set to zero once and for all as required by CFAllocator. */
    szone->basic_zone.reserved1 = 0;
    /* Set to zero once and for all as required by CFAllocator. */
    szone->basic_zone.reserved2 = 0;

    /* Prevent overwriting the function pointers in basic_zone. */
    mprotect(szone, sizeof(szone->basic_zone), PROT_READ);

    szone->debug_flags = debug_flags;
    _malloc_lock_init(&szone->large_szone_lock);

    szone->cpu_id_key = -1UL; // Unused.

    CHECK(szone, __PRETTY_FUNCTION__);
    return szone;
}

这个函数分配并且初始化了szone,设置了szone_mallocszone_free等函数

所以后面在调用mallocfree的时候实际上调用的是szone_mallocszone_freeszone_malloc的实现涉及到苹果关于堆设计中最重要的部分,这里先不展开讲解。可以看出苹果设计的这种结构很方便扩展,事实上的确如此,不仅是scalable zone,还可以注册WebKit Malloc、GFXMallocZone、QuartzCore。由对应zone的malloc_zone_*进行实际的内存分配工作。

下面是程序第一次调用malloc的栈帧,可以看出与我们分析的调用顺序一致

 *  frame #0: 0x00007fff60bd72af libsystem_malloc.dylib`create_scalable_szone
    frame #1: 0x00007fff60bd6e71 libsystem_malloc.dylib`_malloc_initialize + 1482
    frame #2: 0x00007fff60c0facb libsystem_platform.dylib`_os_once_callout + 18
    frame #3: 0x00007fff60bd68a5 libsystem_malloc.dylib`default_zone_malloc + 77
    frame #4: 0x00007fff60bd6807 libsystem_malloc.dylib`malloc_zone_malloc + 103
    frame #5: 0x00007fff60bd6783 libsystem_malloc.dylib`malloc + 24
    frame #6: 0x00007fff60a9831d libsystem_c.dylib`arc4_init + 109
    frame #7: 0x00007fff60a98479 libsystem_c.dylib`arc4random_buf + 37
    frame #8: 0x00007fff5f94644e libobjc.A.dylib`_read_images + 396
    frame #9: 0x00007fff5f945473 libobjc.A.dylib`map_images_nolock + 1197
    frame #10: 0x00007fff5f959279 libobjc.A.dylib`map_images + 68
    ....

scalable zone

szone包含两个racks,分别是tiny和small rack

rack 32位机器 64位机器
tiny <= 496B <= 1008B
small <= 128KB <=128KB

大于127KB的就由large allocator分配,直接采用分配页大小的方式。这里不详细讨论。

  • 有几个处理器,rack就有几个magazine
  • 每个magazine有多个regions,tiny(1MB)、small(8MB)
  • 每个region被分为quantum,tiny(16B,64520 Q/region)、small(512B,16319 Q/region)

具体可以从后面结构体中看出来其包含关系。

malloc->szone_malloc->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;

    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) {
        // 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);
        }
    }

    return ptr;
}

上面可以清楚看出会根据其申请内存大小从tiny、small、large三种方式分配。这里以tiny为例

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

    if (tiny_mag_ptr->mag_last_free_msize == msize) {
        // we have a winner
        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) {
        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;
        }

        if (tiny_get_region_from_depot(rack, tiny_mag_ptr, mag_index, msize)) {
            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) {
            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);
            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;
            }

            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 */
}

这里的if (tiny_mag_ptr->mag_last_free_msize == msize)是判断申请大小是否和缓存的大小相同,如果相同,则直接把该内存返回给程序。反之则从ptr = tiny_malloc_from_free_list(rack, tiny_mag_ptr, mag_index, msize);free list中去获取刚好大于该大小的free list。这里的free list是按quantum的倍数递增的一个链表。若还是不能满足则去freelist中由合并得到的较大block中去分配。还不能满足则去region剩余部分申请。最后还不满足则申请新的一个region。申请失败则返回NULL。

free->malloc_zone_free->szone_free
void
szone_free(szone_t *szone, void *ptr)
{
    region_t tiny_region;
    region_t small_region;

#if DEBUG_MALLOC
    if (LOG(szone, ptr)) {
        malloc_report(ASL_LEVEL_INFO, "in szone_free with %p\n", ptr);
    }
#endif
    if (!ptr) {
        return;
    }
    /*
     * Try to free to a tiny region.
     */
    if ((uintptr_t)ptr & (TINY_QUANTUM - 1)) {
        malloc_zone_error(szone->debug_flags, true, "Non-aligned pointer %p being freed\n", ptr);
        return;
    }
    if ((tiny_region = tiny_region_for_ptr_no_lock(&szone->tiny_rack, ptr)) != NULL) {
        if (TINY_INDEX_FOR_PTR(ptr) >= NUM_TINY_BLOCKS) {
            malloc_zone_error(szone->debug_flags, true, "Pointer %p to metadata being freed\n", ptr);
            return;
        }
        free_tiny(&szone->tiny_rack, ptr, tiny_region, 0);
        return;
    }

    /*
     * Try to free to a small region.
     */
    if ((uintptr_t)ptr & (SMALL_QUANTUM - 1)) {
        malloc_zone_error(szone->debug_flags, true, "Non-aligned pointer %p being freed (2)\n", ptr);
        return;
    }
    if ((small_region = small_region_for_ptr_no_lock(&szone->small_rack, ptr)) != NULL) {
        if (SMALL_META_INDEX_FOR_PTR(ptr) >= NUM_SMALL_BLOCKS) {
            malloc_zone_error(szone->debug_flags, true, "Pointer %p to metadata being freed (2)\n", ptr);
            return;
        }
        free_small(&szone->small_rack, ptr, small_region, 0);
        return;
    }

    /* check that it's a legal large allocation */
    if ((uintptr_t)ptr & (vm_page_quanta_size - 1)) {
        malloc_zone_error(szone->debug_flags, true, "non-page-aligned, non-allocated pointer %p being freed\n", ptr);
        return;
    }
    free_large(szone, ptr);
}

同样,free的时候会先判断该内存是否属于tiny,small,large。则选取对应的free函数。这里以tiny为例

void
free_tiny(rack_t *rack, void *ptr, region_t tiny_region, size_t known_size)
{
    msize_t msize;
    boolean_t is_free;
    mag_index_t mag_index = MAGAZINE_INDEX_FOR_TINY_REGION(tiny_region);
    magazine_t *tiny_mag_ptr = &(rack->magazines[mag_index]);

    MALLOC_TRACE(TRACE_tiny_free, (uintptr_t)rack, (uintptr_t)ptr, (uintptr_t)tiny_mag_ptr, known_size);

    // ptr is known to be in tiny_region
    if (known_size) {
        msize = TINY_MSIZE_FOR_BYTES(known_size + TINY_QUANTUM - 1);
    } else {
        msize = get_tiny_meta_header(ptr, &is_free);
        if (is_free) {
            free_tiny_botch(rack, ptr);
            return;
        }
    }
#if DEBUG_MALLOC
    if (!msize) {
        malloc_report(ASL_LEVEL_ERR, "*** free_tiny() block in use is too large: %p\n", ptr);
        return;
    }
#endif

    SZONE_MAGAZINE_PTR_LOCK(tiny_mag_ptr);

#if CONFIG_TINY_CACHE
    // Depot does not participate in CONFIG_TINY_CACHE since it can't be directly malloc()'d
    if (DEPOT_MAGAZINE_INDEX != mag_index) {
        if (msize < TINY_QUANTUM) {                      // to see if the bits fit in the last 4 bits
            void *ptr2 = tiny_mag_ptr->mag_last_free; // Might be NULL
            msize_t msize2 = tiny_mag_ptr->mag_last_free_msize;
            region_t rgn2 = tiny_mag_ptr->mag_last_free_rgn;

            /* check that we don't already have this pointer in the cache */
            if (ptr == ptr2) {
                free_tiny_botch(rack, ptr);
                return;
            }

            if ((rack->debug_flags & MALLOC_DO_SCRIBBLE) && msize) {
                memset(ptr, SCRABBLE_BYTE, TINY_BYTES_FOR_MSIZE(msize));
            }

            tiny_mag_ptr->mag_last_free = ptr;
            tiny_mag_ptr->mag_last_free_msize = msize;
            tiny_mag_ptr->mag_last_free_rgn = tiny_region;

            if (!ptr2) {
                SZONE_MAGAZINE_PTR_UNLOCK(tiny_mag_ptr);
                CHECK(szone, __PRETTY_FUNCTION__);
                return;
            }

            msize = msize2;
            ptr = ptr2;
            tiny_region = rgn2;
        }
    }
#endif /* CONFIG_TINY_CACHE */

    // Now in the time it took to acquire the lock, the region may have migrated
    // from one magazine to another. I.e. trailer->mag_index is volatile.
    // In which case the magazine lock we obtained (namely magazines[mag_index].mag_lock)
    // is stale. If so, keep on tryin' ...
    region_trailer_t *trailer = REGION_TRAILER_FOR_TINY_REGION(tiny_region);
    mag_index_t refreshed_index;

    while (mag_index != (refreshed_index = trailer->mag_index)) { // Note assignment
        SZONE_MAGAZINE_PTR_UNLOCK(tiny_mag_ptr);
        mag_index = refreshed_index;
        tiny_mag_ptr = &(rack->magazines[mag_index]);
        SZONE_MAGAZINE_PTR_LOCK(tiny_mag_ptr);
    }

    if (tiny_free_no_lock(rack, tiny_mag_ptr, mag_index, tiny_region, ptr, msize)) {
        SZONE_MAGAZINE_PTR_UNLOCK(tiny_mag_ptr);
    }

    CHECK(szone, __PRETTY_FUNCTION__);
}

free的时候先将该内存缓存到mag_last_free,若之前mag_last_free为NULL,那么该内存暂时不会被free,仅仅是缓存到mag_last_free。反之,则会将mag_last_free之前的内存free。在free的时候会尝试向前向后合并。合并完成后设置其前后chunk指针等metadata后将其放入对应的free list大小之中。这里需要有注意以下几点

  • 最近free的内存会被缓存,不会立即合并
  • 在被free的块metadata是被保护的
    • 前后指针按16字节大小对齐
    • 指针前4位为checksum

关于free块checksum计算如下:

static MALLOC_INLINE uintptr_t
free_list_checksum_ptr(rack_t *rack, void *ptr)
{
    uintptr_t p = (uintptr_t)ptr;
    return (p >> NYBBLE) | ((free_list_gen_checksum(p ^ rack->cookie) & (uintptr_t)0xF) << ANTI_NYBBLE); // compiles to rotate instruction
}

指针p与cookie异或然后计算checksum后左移到最高字节或上指针p右移4位得到checksumed后的指针。

实验

代码如下

#include <stdio.h>

int main(int argc, char *argv[]) {

    void *p1,*p2,*p3,*p4;

    p1 = malloc(24);
    p2 = malloc(24);
    p3 = malloc(24);
    p4 = malloc(24);

    memset(p1,0xaa,24);
    memset(p2,0xbb,24);
    memset(p3,0xcc,24);

    free(p1);
    free(p3);
    free(p2);
    free(p4);

}

free(p1),直接将p1缓存,所以内存值不变

(lldb) x/24gx p1
0x1002001f0: 0xaaaaaaaaaaaaaaaa 0xaaaaaaaaaaaaaaaa
0x100200200: 0xaaaaaaaaaaaaaaaa 0x00007fff5f94d99c
0x100200210: 0xbbbbbbbbbbbbbbbb 0xbbbbbbbbbbbbbbbb
0x100200220: 0xbbbbbbbbbbbbbbbb 0x0000000000000000
0x100200230: 0xcccccccccccccccc 0xcccccccccccccccc
0x100200240: 0xcccccccccccccccc 0x0000000000000000

free(p3),p3放入缓存,p1放入大小为32字节的freelist,p1previous指针8字节设为NULL,next指针指向设为下一个free block,紧接着后面为该block大小,2*quantum=32字节

(lldb) x/24gx p1
0x1002001f0: 0x0000000000000000 0x1000000010020108
0x100200200: 0xaaaaaaaaaaaa0002 0x00027fff5f94d99c
0x100200210: 0xbbbbbbbbbbbbbbbb 0xbbbbbbbbbbbbbbbb
0x100200220: 0xbbbbbbbbbbbbbbbb 0x0000000000000000
0x100200230: 0xcccccccccccccccc 0xcccccccccccccccc
0x100200240: 0xcccccccccccccccc 0x0000000000000000

free(p2),p2放入缓存,p3放入大小为32字节的freelist,p3previous指针8字节设为NULL,next指针指向设为下一个p1

(lldb) x/24gx p1
0x1002001f0: 0x3000000010020023 0x1000000010020108
0x100200200: 0xaaaaaaaaaaaa0002 0x00027fff5f94d99c
0x100200210: 0xbbbbbbbbbbbbbbbb 0xbbbbbbbbbbbbbbbb
0x100200220: 0xbbbbbbbbbbbbbbbb 0x0000000000000000
0x100200230: 0x0000000000000000 0x200000001002001f
0x100200240: 0xcccccccccccc0002 0x0002000000000000
0x100200250: 0x0000000000000000 0x0000000000000000
0x100200260: 0x0000000000000029 0x0000000000000000

free(p4),p2向前向后合并,合并p1,p3。指向p1,大小为6*quantum=96字节。previous指针8字节设为NULL,next指针指向设为下一个大小为3Q的block

(lldb) x/24gx p1
0x1002001f0: 0x0000000000000000 0x5000000010020048
0x100200200: 0xaaaaaaaaaaaa0006 0x00027fff5f94d99c
0x100200210: 0xbbbbbbbbbbbbbbbb 0xbbbbbbbbbbbbbbbb
0x100200220: 0xbbbbbbbbbbbbbbbb 0x0000000000000000
0x100200230: 0x0000000000000000 0x1000000010020108
0x100200240: 0xcccccccccccc0002 0x0006000000000000
0x100200250: 0x0000000000000000 0x0000000000000000
0x100200260: 0x0000000000000029 0x0000000000000000

上面可以看出previous和next指针前4位都包含checksum。与上面描述的一致。

libmalloc中一些结构体

szone_s // magazine_zone.h
typedef struct szone_s {      // vm_allocate()'d, so page-aligned to begin with.
    malloc_zone_t basic_zone; // first page will be given read-only protection
    uint8_t pad[PAGE_MAX_SIZE - sizeof(malloc_zone_t)];

    unsigned long cpu_id_key; // unused
    // remainder of structure is R/W (contains no function pointers)
    unsigned debug_flags;
    void *log_address;

    /* Allocation racks per allocator type. */
    struct rack_s tiny_rack;
    struct rack_s small_rack;

    /* large objects: all the rest */
    _malloc_lock_s large_szone_lock MALLOC_CACHE_ALIGN; // One customer at a time for large
    unsigned num_large_objects_in_use;
    unsigned num_large_entries;
    large_entry_t *large_entries; // hashed by location; null entries don't count
    size_t num_bytes_in_large_objects;

#if CONFIG_LARGE_CACHE
    int large_entry_cache_oldest;
    int large_entry_cache_newest;
    large_entry_t large_entry_cache[LARGE_ENTRY_CACHE_SIZE]; // "death row" for large malloc/free
    boolean_t large_legacy_reset_mprotect;
    size_t large_entry_cache_reserve_bytes;
    size_t large_entry_cache_reserve_limit;
    size_t large_entry_cache_bytes; // total size of death row, bytes
#endif

    /* flag and limits pertaining to altered malloc behavior for systems with
     * large amounts of physical memory */
    unsigned is_largemem;
    unsigned large_threshold;
    unsigned vm_copy_threshold;

    /* security cookie */
    uintptr_t cookie;

    /* The purgeable zone constructed by create_purgeable_zone() would like to hand off tiny and small
     * allocations to the default scalable zone. Record the latter as the "helper" zone here. */
    struct szone_s *helper_zone;

    boolean_t flotsam_enabled;
} szone_t;
malloc_zone_t // malloc.h
typedef struct _malloc_zone_t {
    /* Only zone implementors should depend on the layout of this structure;
    Regular callers should use the access functions below */
    void    *reserved1;    /* RESERVED FOR CFAllocator DO NOT USE */
    void    *reserved2;    /* RESERVED FOR CFAllocator DO NOT USE */
    size_t     (* MALLOC_ZONE_FN_PTR(size))(struct _malloc_zone_t *zone, const void *ptr); /* returns the size of a block or 0 if not in this zone; must be fast, especially for negative answers */
    void     *(* MALLOC_ZONE_FN_PTR(malloc))(struct _malloc_zone_t *zone, size_t size);
    void     *(* MALLOC_ZONE_FN_PTR(calloc))(struct _malloc_zone_t *zone, size_t num_items, size_t size); /* same as malloc, but block returned is set to zero */
    void     *(* MALLOC_ZONE_FN_PTR(valloc))(struct _malloc_zone_t *zone, size_t size); /* same as malloc, but block returned is set to zero and is guaranteed to be page aligned */
    void     (* MALLOC_ZONE_FN_PTR(free))(struct _malloc_zone_t *zone, void *ptr);
    void     *(* MALLOC_ZONE_FN_PTR(realloc))(struct _malloc_zone_t *zone, void *ptr, size_t size);
    void     (* MALLOC_ZONE_FN_PTR(destroy))(struct _malloc_zone_t *zone); /* zone is destroyed and all memory reclaimed */g
    const char    *zone_name;

    /* Optional batch callbacks; these may be NULL */
    unsigned    (* MALLOC_ZONE_FN_PTR(batch_malloc))(struct _malloc_zone_t *zone, size_t size, void **results, unsigned num_requested); /* given a size, returns pointers capable of holding that size; returns the number of pointers allocated (maybe 0 or less than num_requested) */
    void    (* MALLOC_ZONE_FN_PTR(batch_free))(struct _malloc_zone_t *zone, void **to_be_freed, unsigned num_to_be_freed); /* frees all the pointers in to_be_freed; note that to_be_freed may be overwritten during the process */

    struct malloc_introspection_t    * MALLOC_INTROSPECT_TBL_PTR(introspect);
    unsigned    version;

    /* aligned memory allocation. The callback may be NULL. Present in version >= 5. */
    void *(* MALLOC_ZONE_FN_PTR(memalign))(struct _malloc_zone_t *zone, size_t alignment, size_t size);

    /* free a pointer known to be in zone and known to have the given size. The callback may be NULL. Present in version >= 6.*/
    void (* MALLOC_ZONE_FN_PTR(free_definite_size))(struct _malloc_zone_t *zone, void *ptr, size_t size);

    /* Empty out caches in the face of memory pressure. The callback may be NULL. Present in version >= 8. */
    size_t     (* MALLOC_ZONE_FN_PTR(pressure_relief))(struct _malloc_zone_t *zone, size_t goal);

    /*
     * Checks whether an address might belong to the zone. May be NULL. Present in version >= 10.
     * False positives are allowed (e.g. the pointer was freed, or it's in zone space that has
     * not yet been allocated. False negatives are not allowed.
     */
    boolean_t (* MALLOC_ZONE_FN_PTR(claimed_address))(struct _malloc_zone_t *zone, void *ptr);
} malloc_zone_t;
rack_t // magazine_rack.h
typedef struct rack_s {
    /* Regions for tiny objects */
    _malloc_lock_s region_lock MALLOC_CACHE_ALIGN;

    rack_type_t type;
    size_t num_regions;
    size_t num_regions_dealloc;
    region_hash_generation_t *region_generation;
    region_hash_generation_t rg[2];
    region_t initial_regions[INITIAL_NUM_REGIONS];

    int num_magazines;
    unsigned num_magazines_mask;
    int num_magazines_mask_shift;
    uint32_t debug_flags;

    // array of per-processor magazines
    magazine_t *magazines;

    uintptr_t cookie;
    uintptr_t last_madvise;
} rack_t;
magazine_t // magazine_zone.h
typedef struct magazine_s { // vm_allocate()'d, so the array of magazines is page-aligned to begin with.
    // Take magazine_lock first,  Depot lock when needed for recirc, then szone->{tiny,small}_regions_lock when needed for alloc
    _malloc_lock_s magazine_lock MALLOC_CACHE_ALIGN;
    // Protection for the crtical section that does allocate_pages outside the magazine_lock
    volatile boolean_t alloc_underway;

    // One element deep "death row", optimizes malloc/free/malloc for identical size.
    void *mag_last_free;
    msize_t mag_last_free_msize;    // msize for mag_last_free
#if MALLOC_TARGET_64BIT
    uint32_t _pad;
#endif
    region_t mag_last_free_rgn; // holds the region for mag_last_free

    free_list_t mag_free_list[MAGAZINE_FREELIST_SLOTS];
    uint32_t mag_bitmap[MAGAZINE_FREELIST_BITMAP_WORDS];

    // the first and last free region in the last block are treated as big blocks in use that are not accounted for
    size_t mag_bytes_free_at_end;
    size_t mag_bytes_free_at_start;
    region_t mag_last_region; // Valid iff mag_bytes_free_at_end || mag_bytes_free_at_start > 0

    // bean counting ...
    size_t mag_num_bytes_in_objects;
    size_t num_bytes_in_magazine;
    unsigned mag_num_objects;

    // recirculation list -- invariant: all regions owned by this magazine that meet the emptiness criteria
    // are located nearer to the head of the list than any region that doesn't satisfy that criteria.
    // Doubly linked list for efficient extraction.
    unsigned recirculation_entries;
    region_trailer_t *firstNode;
    region_trailer_t *lastNode;

#if MALLOC_TARGET_64BIT
    uintptr_t pad[320 - 14 - MAGAZINE_FREELIST_SLOTS -
            (MAGAZINE_FREELIST_BITMAP_WORDS + 1) / 2];
#else
    uintptr_t pad[320 - 16 - MAGAZINE_FREELIST_SLOTS -
            MAGAZINE_FREELIST_BITMAP_WORDS];
#endif

} magazine_t;
tiny_region_t //magazine_zone.h
/*
 * Layout of a tiny region
 */
typedef uint32_t tiny_block_t[4]; // assert(TINY_QUANTUM == sizeof(tiny_block_t))

typedef struct tiny_header_inuse_pair {
    uint32_t header;
    uint32_t inuse;
} tiny_header_inuse_pair_t;

typedef struct region_trailer {
    struct region_trailer *prev;
    struct region_trailer *next;
    boolean_t recirc_suitable;
    volatile int pinned_to_depot;
    unsigned bytes_used;
    mag_index_t mag_index;
} region_trailer_t;

#define NUM_TINY_BLOCKS 64520

typedef struct tiny_region {
    tiny_block_t blocks[NUM_TINY_BLOCKS];

    region_trailer_t trailer;

    // The interleaved bit arrays comprising the header and inuse bitfields.
    // The unused bits of each component in the last pair will be initialized to sentinel values.
    tiny_header_inuse_pair_t pairs[CEIL_NUM_TINY_BLOCKS_WORDS];

    uint8_t pad[TINY_REGION_SIZE - (NUM_TINY_BLOCKS * sizeof(tiny_block_t)) - TINY_METADATA_SIZE];
} * tiny_region_t;

参考