入门篇介绍了zone在初始化时规定了nanozone办理256字节以内内存，其他内存由scalablezone办理，上篇介绍了nanozone的机制，本篇持续介绍scalablezone的内存机制。

全体战略与szone

关于256字节以上的内存，运用scalablezone分配，因为待分配内存的巨细差异较大，scalablezone在分配时不选用同一套逻辑，而是先将分配巨细划分红tiny、small、medium、large4个等级，针对这4个等级，选用不同的分配逻辑处理，其间tiny、small、medium（iOS下不运用，这儿不介绍）的全体逻辑相同，可是详细战略有差异，large有一套自己的机制，iOS上没有medium战略。

首要，调用create_scalable_szone函数创立scalablezone，scalablezone的类型是szone_s，是根底malloc_zone_t结构的扩展，szone_s界说如下：

typedef struct szone_s {
    malloc_zone_t basic_zone; // first page will be given read-only protection
    uint8_t pad[PAGE_MAX_SIZE - sizeof(malloc_zone_t)];
    struct rack_s tiny_rack;
    struct rack_s small_rack;
    struct rack_s medium_rack;
    _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_HIGH]; // "death row" for large malloc/free
    int large_cache_depth;
    size_t large_cache_entry_limit;
    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
    /* 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;
} szone_t;

包括以下字段：

• basic_zone：根底结构malloc_zone_t，存储内存办理的各进口函数地址，在入门篇文章中已介绍。
• tiny_rack/small_rack/medium_rack：rack_s类型，用于tiny、small、medium内存的详细办理，下文中介绍。
• large类型内存办理相关字段，包括计算信息，办理large内存块，缓存逻辑相关。
• helper_zone：辅佐zone。

create_scalable_szone函数创立scalablezone。

szone_t *create_scalable_szone(size_t initial_size, unsigned debug_flags)
{
    szone_t *szone;
    szone = mvm_allocate_pages(SZONE_PAGED_SIZE, 0, DISABLE_ASLR, VM_MEMORY_MALLOC);
    if (!szone) {
        return NULL;
    }
    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
    //large cache相关字段初始化
#endif
    szone->basic_zone.version = 13;
    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;
    //...
    return szone;
}

初始化逻辑包括以下部分：

1. mvm_allocate_pages创立一个szone_t内存，即scalablezone。
2. rack_init函数初始化tiny、small的rack数据，初始化分配逻辑。
3. 初始化large cach相关逻辑
4. 初始化malloc_zone_t base_zone的字段，作为scalablezone办理内存的进口API。

例如，scalablezone的malloc逻辑由szone_malloc完成：

void *szone_malloc(szone_t *szone, size_t size)
{
    return szone_malloc_should_clear(szone, size, 0);
}

内部调用szone_malloc_should_clear完成malloc，如下：

#if MALLOC_TARGET_64BIT
#define TINY_LIMIT_THRESHOLD (1008)
#else // MALLOC_TARGET_64BIT
#define TINY_LIMIT_THRESHOLD (496)
#endif // MALLOC_TARGET_64BIT
#if MALLOC_TARGET_IOS
#define SMALL_LIMIT_THRESHOLD (15 * 1024)
#else // MALLOC_TARGET_IOS
#define SMALL_LIMIT_THRESHOLD (32 * 1024)
#endif // MALLOC_TARGET_IOS
MALLOC_NOINLINE void *
szone_malloc_should_clear(szone_t *szone, size_t size, boolean_t cleared_requested)
{
    void *ptr;
    msize_t msize;
    if (size <= TINY_LIMIT_THRESHOLD) {
        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 <= SMALL_LIMIT_THRESHOLD) {
        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 {
        size_t num_kernel_pages = round_large_page_quanta(size) >> large_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;
}

能够看到，依据分配size巨细，运用不同的分配战略。

• tiny：tiny_malloc_should_clear，1008B以内
• small：small_malloc_should_clear1009B～15KB
• large：15KB以上

又例如，free逻辑由szone_free完成：

void szone_free(szone_t *szone, void *ptr)
{
    _szone_free(szone, ptr, false);
}
static void _szone_free(szone_t *szone, void *ptr, bool try)
{
    //...
    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 freedn", ptr);
            return;
        }
        free_tiny(&szone->tiny_rack, ptr, tiny_region, 0, false);
        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;
    }
    //...
    bool claimed = free_large(szone, ptr, try);
    if (!try || claimed) {
        return;
    }
}

类似malloc逻辑，free也详细调用free_tiny、free_small、free_large处理不同size内存的收回。用一张图表明scalablezone处理内存的逻辑如下：

tiny

tiny首要的完成在magazine_tiny.c文件中，首要结合代码，介绍tiny办理内存的相关数据结构及其概念。

相关概念

size分级

依据要分配的size，依照指定size的倍数核算对应的分级（msize），实践分配指定size的倍数分配，例如tiny类型，将内存划分为16B一级，则1008B的范围总共划分为63级（如下图所示）。

rack

如上所述，rack_s是办理内存的大局数据结构，检查rack_s的界说，中心字段如下：

OS_ENUM(rack_type, uint32_t,
    RACK_TYPE_NONE = 0,
    RACK_TYPE_TINY,
    RACK_TYPE_SMALL,
    RACK_TYPE_MEDIUM,
);
typedef struct rack_s {
    rack_type_t type; //类型
    //...
    size_t num_regions;
    region_t initial_regions[INITIAL_NUM_REGIONS];
    int num_magazines;
    magazine_t *magazines;
    //...
} rack_t;

• type：类型，对应tiny、small、medium三种战略类型。
• num_regions：分配的region内存块个数，region是向scalablezone向体系分配的虚拟内存的根底单位，不同类型分配的region的巨细不共同。
• initial_regions：初始化时分配的region数组。
• num_magazines：持有的magazine个数，magazine是办理scalable内存的中心概念，详细担任内存的办理，包括region块的分配与办理、闲暇块的运用与办理等。
• magazines：magazine数组，一种战略类型详细由若干个magazine办理。

创立scalable_szone时，经过rack_init初始化rack数据。

magazine

结构联系

magazine是办理内存的中心结构，每一种rack（tiny、small、medium），会创立多个magazine，rack在操作内存时，首要需求选取其间一个magazine详细操作，体现在数据结构上，rack_s下持有若干个magazine。

typedef struct rack_s {
    //...
    // array of per-processor magazines
    magazine_t *magazines;
}

详细的对应联系如图：

szone_t *
create_scalable_szone(size_t initial_size, unsigned debug_flags)
{
    //...
    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);
}
void rack_init(rack_t *rack, rack_type_t type, uint32_t num_magazines, uint32_t debug_flags)
{
    //...
    rack->num_magazines = num_magazines;
    //...
    if (num_magazines > 0) {
        size_t magsize = round_page_quanta(sizeof(magazine_t) * (num_magazines + 1));
        magazine_t *magazines = mvm_allocate_pages(magsize, 0, MALLOC_ADD_GUARD_PAGE_FLAGS|DISABLE_ASLR, VM_MEMORY_MALLOC);
        if (!magazines) {
            MALLOC_REPORT_FATAL_ERROR(0, "unable to allocate magazine array");
        }
        rack->magazines = &magazines[1];
    }
}

调用create_scalable_szone初始化tiny的rack数据，在rack_init办法中传入num_magazines并创立magazines，num_magazines经过mag_max_magazines办法获取.

unsigned int mag_max_magazines(void)
{
    return max_magazines;
}
static void _malloc_initialize(const char *apple[], const char *bootargs)
{
    logical_ncpus = *(uint8_t *)(uintptr_t)_COMM_PAGE_LOGICAL_CPUS;
    //...
    if (max_magazines) {
        max_magazines = MIN(max_magazines, logical_ncpus);
    } else {
        max_magazines = logical_ncpus;
    }
}

max_magazines由_COMM_PAGE_LOGICAL_CPUS获取，意义是number of logical CPUs（逻辑CPU的中心数）。因而magazines的个数由逻辑CPU的中心数决议。能够理解为magazine和CPU存在对应联系，如图，当分配内存时，依据当时线程履行的CPU，选择对应的magazine。

详细代码如下：

mag_index_t mag_index = tiny_mag_get_thread_index() % rack->num_magazines;
magazine_t *tiny_mag_ptr = &(rack->magazines[mag_index]);
mag_index_t tiny_mag_get_thread_index(void)
{
    if (likely_if(_os_cpu_number_override == -1)) {
        return _malloc_cpu_number();
    } else {
        return _os_cpu_number_override;
    }
}

经过tiny_mag_get_thread_index办法获取当时线程的cpu中心对应的mag_index下标，经过magazines[mag_index]回来magazine对象。CPU中心数和magazine对象的联系大致如图，

这样操作内存时，每个cpu中心对应一个magazine，多magazine一起操作内存，能够发挥多cpu中心并行的能力。

内存办理

magazine是怎么办理内存的，首要数据结构如下：

typedef struct magazine_s {
    //...
    void *mag_last_free;
    msize_t mag_last_free_msize;
    //...
    region_t mag_last_free_rgn;
    free_list_t mag_free_list[MAGAZINE_FREELIST_SLOTS]; //257
    uint32_t mag_bitmap[MAGAZINE_FREELIST_BITMAP_WORDS]; //9
    size_t mag_bytes_free_at_end; //最终请求的heap region中未运用的巨细
    size_t mag_bytes_free_at_start;
    region_t mag_last_region; // 最终一次向内核请求的heap region地址
    size_t mag_num_bytes_in_objects;
    size_t num_bytes_in_magazine;
    unsigned mag_num_objects;
    region_trailer_t *firstNode;
    region_trailer_t *lastNode;
    //...
}

首要字段如下：

• firstNode、lastNode：region链表，待分配内存从region平分配。
• mag_last_free：缓存的前一次收回内存块的地址
• mag_last_free_msize：缓存的前一次收回内存块的size分级
• mag_last_free_rgn：前一次收回内存地点的region
• mag_free_list：闲暇链表，记载了之前收回的内存，完成内存复用的中心字段
• mag_bitmap：内存闲暇状况数组，判别内存复用的辅佐字段。
• mag_bytes_free_at_end：region中剩下内存空间的完毕地址。
• mag_bytes_free_at_start：region中剩下内存空间的开端地址。

全体来看，包括2个中心数据结构和一些辅佐功用所需的字段，用一张图阐明。

region

上文所述，magazine会办理一系列region空间，其他分配器的逻辑类似，region是实践存储分配内存的物理空间，magazine分配内存时，会一次性分配一块较大的内存区域region（图中黄色区域），该区域巨细范围固定。而详细的内存从region平分配，当region剩下空间缺乏时，分配一块新的region。

内部结构

关于tiny内存，msize依照16B为基本单位，称为一个block内存，region内分配的不同size的内存块本质上由若干地址接连的block构成。因而，region是一块包括若干地址接连的16B内存块的较大物理空间，结构界说如下：

typedef struct tiny_region {
    //meta
    region_trailer_t trailer; //链表
    tiny_header_inuse_pair_t pairs[CEIL_NUM_TINY_BLOCKS_WORDS]; //bit状况信息
    region_free_blocks_t free_blocks_by_slot[NUM_TINY_SLOTS]; 
    uint8_t pad[TINY_REGION_PAD];
    region_cookie_t region_cookie;
    //block内存
    tiny_block_t blocks[NUM_TINY_BLOCKS];
} * tiny_region_t;

其间，tiny_block_t对应一个16B的block内存块，block是tiny内存块的基本单位，blocks字段是block数组，用于实践存储region内的业务数据，NUM_TINY_BLOCKS是数组容量，即region中包括的block块个数，决议了region可供运用的内存容量。

#define SHIFT_TINY_QUANTUM 4ull
#define TINY_QUANTUM (1 << SHIFT_TINY_QUANTUM)
#define NUM_TINY_BLOCKS 64504

NUM_TINY_BLOCKS是一个固定值64504，TINY_QUANTUM表明单个block巨细是16B，因而region内存的容量是NUM_TINY_BLOCKS*TINY_QUANTUM。

除了担任数据存储的blocks字段外，其他字段用于region状况的办理，包括region链表的保护，block内存状况，用于辅佐后续region内存操作与办理，这些字段称为region的meta数据字段。

下图反映了region空间的内存结构散布（真实的region是一块物理内存接连的空间，与图中展示的region存在差异，期望不要造成误解），region内存包括blocks区域和meta区域两部分，blocks区域的内存块由16B block根底内存块构成。

//blocks巨细
#define TINY_HEAP_SIZE (NUM_TINY_BLOCKS * TINY_QUANTUM)
//meta巨细
#define TINY_METADATA_SIZE (sizeof(region_trailer_t) + sizeof(tiny_header_inuse_pair_t) * CEIL_NUM_TINY_BLOCKS_WORDS + (sizeof(region_free_blocks_t) * NUM_TINY_SLOTS))
//region巨细
#define TINY_REGION_SIZE ((TINY_HEAP_SIZE + TINY_METADATA_SIZE + PAGE_MAX_SIZE - 1) & ~(PAGE_MAX_SIZE - 1))

一起，还供给了一些封装宏拜访region内部内存，例如TINY_REGION_METADATA是meta区开端地址，TINY_REGION_HEAP_BASE是blocks区开端地址，TINY_REGION_HEAP_END是blocks区完毕地址。

#define TINY_REGION_METADATA(region) ((uintptr_t)&((tiny_region_t)region)->trailer)
#define TINY_REGION_HEAP_BASE(region) ((void *)(((tiny_region_t)region)->blocks))
#define TINY_REGION_HEAP_END(region) ((void *)(((uintptr_t)TINY_REGION_HEAP_BASE(region)) + TINY_HEAP_SIZE))

一起，供给了TINY_INDEX_FOR_PTR宏，依据region中的任意内存地址ptr，回来对应的block内存在region中的index。

#define TINY_HEAP_OFFSET_FOR_PTR(ptr) ((uintptr_t)(ptr) - (uintptr_t)TINY_REGION_HEAP_BASE(TINY_REGION_FOR_PTR(ptr)))
#define TINY_INDEX_FOR_PTR(ptr) ((TINY_HEAP_OFFSET_FOR_PTR(ptr) >> SHIFT_TINY_QUANTUM) & (NUM_TINY_CEIL_BLOCKS - 1))

详细核算逻辑是，首要核算ptr间隔blocks开端地址的偏移量，然后除以单个block的size（16字节），再&(NUM_TINY_CEIL_BLOCKS – 1)得到block得index，offset如图：

#define TINY_PTR_FOR_INDEX(index, region) (void *)((uintptr_t)TINY_REGION_HEAP_BASE(region) + ((index) << SHIFT_TINY_QUANTUM))

也能够经过block区中的一个block内存块地址，找到其地点region区的meta字段内存地址。

#define TINY_BLOCK_HEADER_FOR_PTR(ptr) ((void *)&(((tiny_region_t)TINY_REGION_FOR_PTR(ptr))->pairs))

接下来介绍meta信息相关字段。

• trailer，region链表结构字段，保护magazine下分配的一切region内存，对应的数据结构：

  • typedef struct region_trailer {
        struct region_trailer *prev;
        struct region_trailer *next;
        //...
    } region_trailer_t;
    

  • 经过prev、next指针指向前后region。

• pairs[]数组，记载region内block内存的运用状况，辅佐magazine进行内存操作，其意义效果下文详细介绍。

• free_blocks_by_slot[]数组，记载region内不同msize闲暇内存块。

链表结构

如上所述，region经过meta的region_trailer_t结构的trailer字段保护链表，如图所示，经过链表能够遍历查找到magazine下分配的一切region。

1. 将region参加链表的结尾

   //将region参加tiny_mag_ptr的last node
   static void recirc_list_splice_last(rack_t *rack, magazine_t *mag_ptr, region_trailer_t *node)
   {
       if (NULL == mag_ptr->lastNode) {
           mag_ptr->firstNode = node;
           node->prev = NULL;
       } else {
           node->prev = mag_ptr->lastNode;
           mag_ptr->lastNode->next = node;
       }
       mag_ptr->lastNode = node;
       node->next = NULL;
       node->recirc_suitable = FALSE;
   }
   

2. 将region参加链表的头部

   static void recirc_list_splice_first(rack_t *rack, magazine_t *mag_ptr, region_trailer_t *node)
   {
       if (NULL == mag_ptr->firstNode) {
           mag_ptr->lastNode = node;
           node->next = NULL;
       } else {
           node->next = mag_ptr->firstNode;
           mag_ptr->firstNode->prev = node;
       }
       mag_ptr->firstNode = node;
       node->prev = NULL;
       node->recirc_suitable = FALSE;
   }
   

3. region节点从region trailer链表中移除

   static void recirc_list_extract(rack_t *rack, magazine_t *mag_ptr, region_trailer_t *node)
   {
       // excise node from list
       if (NULL == node->prev) {
           mag_ptr->firstNode = node->next;
       } else {
           node->prev->next = node->next;
       }
       if (NULL == node->next) {
           mag_ptr->lastNode = node->prev;
       } else {
           node->next->prev = node->prev;
       }
       node->next = node->prev = NULL;
       mag_ptr->recirculation_entries--;
   }
   

hash存储

除了magazine保护的region链表外，当分配了一块region后，会核算region的一个hash值，并记载到一块hash ring的内存结构中，标识rack下是否存在这块region，内存结构如图：

typedef struct rack_s {
    //...
    region_hash_generation_t *region_generation;
}
typedef struct region_hash_generation {
    size_t num_regions_allocated;
    size_t num_regions_allocated_shift;
    region_t *hashed_regions;
    struct region_hash_generation *nextgen;
} region_hash_generation_t;

界说了region_hash_generation_t类型的region_generation字段，数据结构内部保护了hashed_regions字段，存储region的hash index数据。当hashed_regions的容量无法满意region的增加时，会新分配一个region_generation作为当时generation的nextgen，存储扩容的hashed_regions，并将数据同步到新的hashed_regions。

相关完成

结合图示，剖析详细完成。

hash增加

当新分配一个region时，调用rack_region_insert参加region的hash index到hash ring中。

void rack_region_insert(rack_t *rack, region_t region)
{
    //rack的regions个数大于的2被大于当时generation的记载分配的region个数时，新增generation，并搬迁数据。
    if (rack->region_generation->num_regions_allocated < (2 * rack->num_regions)) {
        region_t *new_regions;
        size_t new_size;
        size_t new_shift = rack->region_generation->num_regions_allocated_shift; // In/Out parameter
        new_regions = hash_regions_grow_no_lock(rack->region_generation->hashed_regions,
                                                rack->region_generation->num_regions_allocated, &new_shift, &new_size);
        rack->region_generation->nextgen->hashed_regions = new_regions;
        rack->region_generation->nextgen->num_regions_allocated = new_size;
        rack->region_generation->nextgen->num_regions_allocated_shift = new_shift;
        //新generation作为当时generation
        rack->region_generation = rack->region_generation->nextgen;
    }
    //ragion的hash index参加generation的hashed_regions中
    hash_region_insert_no_lock(rack->region_generation->hashed_regions,
                               rack->region_generation->num_regions_allocated,
                               rack->region_generation->num_regions_allocated_shift,
                               region);
    rack->num_regions++;
}

1. 判别rack中regions个数（num_regions），是否超越当时generation的记载分配的region个数的一半，假如超越，则需求扩容hashed_regions，新建一个generation，指向扩容后的new_hashed_regions，并作为当时generation。

2. 扩容逻辑如下：

   static region_t *hash_regions_grow_no_lock(region_t *regions, size_t old_size, size_t *mutable_shift, size_t *new_size)
   {
       *new_size = old_size + old_size;
       *mutable_shift = *mutable_shift + 1;
       region_t *new_regions = hash_regions_alloc_no_lock(*new_size);
       size_t index;
       for (index = 0; index < old_size; ++index) {
           region_t r = regions[index];
           if (r != HASHRING_OPEN_ENTRY && r != HASHRING_REGION_DEALLOCATED) {
               hash_region_insert_no_lock(new_regions, *new_size, *mutable_shift, r);
           }
       }
       return new_regions;
   }
   

   分配一块新内存new_regions，容量是旧的2倍，并将旧region中存储的hash index数据搬迁到新的hashed_regions内存中。如图所示：

   

3. 将region的hash index参加generation的hashed_regions中。参加的详细完成是：

   static void hash_region_insert_no_lock(region_t *regions, size_t num_entries, size_t shift, region_t r)
   {
       size_t index, hash_index;
       rgnhdl_t entry;
       index = hash_index = (((uintptr_t)r >> HASH_BLOCKS_ALIGN) * 11400714819323198549ULL) >> (64 - shift);
       do {
           entry = regions + index;
           if (*entry == HASHRING_OPEN_ENTRY || *entry == HASHRING_REGION_DEALLOCATED) {
               *entry = r;
               return;
           }
           if (++index == num_entries) {
               index = 0;
           }
       } while (index != hash_index);
   }
   

   首要核算region的hash，以hash作为index，查找index位是否存储数据，假如已存储数据，则不断++index偏移至下一位查找是否有空位，直到找到空位，当index坐落buffer数组结尾，则从0持续遍历，整个遍历查找进程是一个环，假如查找回到开端的index，则停止。其间，这儿判别是当时hashed_regions[index]的值是否是枚举值HASHRING_OPEN_ENTRY和HASHRING_REGION_DEALLOCATED，HASHRING_OPEN_ENTRY是默认值0，表明没有存过数据，HASHRING_REGION_DEALLOCATED是-1表明之前存储的值被清空了。

   

   如图，核算出region的hash index，因为对应的hashed_regions[hash index]上现已存储数据了，则偏移直到找到空位存储。

hash查找

能够经过查询hash_regions中的index，判别rack中是否存在region。

static rgnhdl_t hash_lookup_region_no_lock(region_t *regions, size_t num_entries, size_t shift, region_t r)
{
    size_t index, hash_index;
    rgnhdl_t entry;
    if (!num_entries) {
        return 0;
    }
    index = hash_index = (((uintptr_t)r >> HASH_BLOCKS_ALIGN) * 11400714819323198549ULL) >> (64 - shift);
    do {
        entry = regions + index;
        if (*entry == 0) {
            return 0;
        }
        if (*entry == r) {
            return entry;
        }
        if (++index == num_entries) {
            index = 0;
        }
    } while (index != hash_index);
    return 0;
}

查找和增加的规则是相同的。

hash删去

当一个region被收回时，调用rack_region_remove办法删去对应的hash index。

bool rack_region_remove(rack_t *rack, region_t region, region_trailer_t *trailer)
{
    bool rv = true;
    //...
    rgnhdl_t pSlot = hash_lookup_region_no_lock(
            rack->region_generation->hashed_regions,
            rack->region_generation->num_regions_allocated,
            rack->region_generation->num_regions_allocated_shift,
            region);
    //...
    *pSlot = HASHRING_REGION_DEALLOCATED;
    return rv;
}

其间，pSlot是查找到的hash index，置位HASHRING_REGION_DEALLOCATED，这样下次能够复用。这儿不会收回hashed_regions内存，而是置空数据给后续region的hash index复用。

内存状况办理

上文所述，magazine平分配的内存实践从region平分配，并收回复用。为了办理magazine中的内存，首要需求记载这些内存的状况，因为只需知道每块内存的状况，才能有效判别，完成复用的逻辑，能够分为以下3种：

1. 未分配：未被分配的内存空间，即region中的剩下内存空间。
2. 分配并被运用：从region平分配了一块指定size的内存块，而且正在运用中。
3. 未运用：被收回的内存块，能够被复用。

用一张图来阐明：

bit位状况

运用mag_bitmap[]数组记载每一级msize是否存在内存，例如下图：

magazine界说了一些宏来操作bit位，以64位为例：

#define BITMAPV_SET(bitmap, slot) (bitmap[(slot) >> 5] |= 1 << ((slot)&31))
#define BITMAPV_CLR(bitmap, slot) (bitmap[(slot) >> 5] &= ~(1 << ((slot)&31)))
#define BITMAPV_BIT(bitmap, slot) ((bitmap[(slot) >> 5] >> ((slot)&31)) & 1)

block状况办理

mag_bitmap是magazine记载的magazine大局的内存块状况信息，一起关于每一块region，也会保护其内部内存块的状况。

region中内存块由若干个16B巨细的block构成，如图所示，淡黄色是msize=1的内存块，由1个block组成，黄色是msize=2的内存块，由2个block组成。

block的状况信息存储在pairs字段中，界说如下：

typedef struct tiny_header_inuse_pair {
    uint32_t header;
    uint32_t inuse;
} tiny_header_inuse_pair_t;
tiny_header_inuse_pair_t pairs[CEIL_NUM_TINY_BLOCKS_WORDS];

pairs字段能够理解为region的Header信息，是tiny_header_inuse_pair_t（简称pair）结构体数组，数组长度经过CEIL_NUM_TINY_BLOCKS_WORDS宏表明。

#define CEIL_NUM_TINY_BLOCKS_WORDS (((NUM_TINY_BLOCKS + 31) & ~31) >> 5)

每个pair结构体元素包括header和inuse2个字段，长度别离是32bit，因而最多能够存储32个block内存块的状况信息。而一块tiny region共有64504个block，CEIL_NUM_TINY_BLOCKS_WORDS表明存储这些block共需求的pair个数。

而每个pair结构体的字段经过记载这些内存块中block的bit值，来存储当时内存块的状况。其间header字段的bit位记载某个内存块是否被分配以及分配的msize长度，inuse字段记载该内存块的运用状况，是正在运用还是被收回未运用。

未分配

初始化状况下，region内未分配任何内存块，则一切block的bit均为0，下图是一个pair结构体下32个block的bit值，均为0（黄色表明）。

分配运用

当分配内存块时，bit位更新，分为2种状况，假如分配的内存msize是1，履行set_tiny_meta_header_in_use_1函数逻辑。假如分配的内存msize大于1，履行set_tiny_meta_header_in_use函数逻辑。

static MALLOC_INLINE void set_tiny_meta_header_in_use_1(const void *ptr) // As above with msize == 1
{
    uint32_t *block_header = TINY_BLOCK_HEADER_FOR_PTR(ptr);
    msize_t index = TINY_INDEX_FOR_PTR(ptr);
    msize_t midx = (index >> 5) << 1;
    uint32_t val = (1 << (index & 31));
    block_header[midx] |= val;   // BITARRAY_SET(block_header, index);
    block_header[midx + 1] |= val; // BITARRAY_SET(in_use, index);
    index++;
    midx = (index >> 5) << 1;
    val = (1 << (index & 31));
    block_header[midx] |= val; // BITARRAY_SET(block_header, (index+clr_msize))
}
static MALLOC_INLINE void set_tiny_meta_header_in_use(const void *ptr, msize_t msize)
{
    uint32_t *block_header = TINY_BLOCK_HEADER_FOR_PTR(ptr);
    msize_t index = TINY_INDEX_FOR_PTR(ptr);
    msize_t clr_msize = msize - 1;
    msize_t midx = (index >> 5) << 1;
    uint32_t val = (1 << (index & 31));
    block_header[midx] |= val;  // BITARRAY_SET(block_header, index);
    block_header[midx + 1] |= val; // BITARRAY_SET(in_use, index);
    index++;
    midx = (index >> 5) << 1;
    unsigned start = index & 31;
    unsigned end = start + clr_msize;
#if defined(__LP64__)
    if (end > 63) {
        unsigned mask0 = (0xFFFFFFFFU >> (31 - start)) >> 1;
        unsigned mask1 = (0xFFFFFFFFU << (end - 64));
        block_header[midx + 0] &= mask0; // clear header
        block_header[midx + 1] &= mask0; // clear in_use
        block_header[midx + 2] = 0;      // clear header
        block_header[midx + 3] = 0;      // clear in_use
        block_header[midx + 4] &= mask1; // clear header
        block_header[midx + 5] &= mask1; // clear in_use
    } else
#endif
        if (end > 31) {
            unsigned mask0 = (0xFFFFFFFFU >> (31 - start)) >> 1;
            unsigned mask1 = (0xFFFFFFFFU << (end - 32));
            block_header[midx + 0] &= mask0;
            block_header[midx + 1] &= mask0;
            block_header[midx + 2] &= mask1;
            block_header[midx + 3] &= mask1;
        } else {
            unsigned mask = (0xFFFFFFFFU >> (31 - start)) >> 1;
            mask |= (0xFFFFFFFFU << end);
            block_header[midx + 0] &= mask;
            block_header[midx + 1] &= mask;
        }
    // we set the block_header bit for the following block to reaffirm next block is a block
    index += clr_msize;
    midx = (index >> 5) << 1;
    val = (1 << (index & 31));
    block_header[midx] |= val; // BITARRAY_SET(block_header, (index+clr_msize));
}

其间，midx是pair的index，首要>>5定位表明每32个block的bit值存储在同一个pair中，<<1是因为block_header指针是32位，指向的pair长度包括2个32位字段，所以block_header表明的数组长度乘2，如图：

设置的规则是：

1. 设置header字段的bit位数值，规则是依据当时分配的内存的msize长度，进行设置，内存块包括的第一个block对应的bit位设置为1，其他block对应的bit位设置为0。
2. 为了符号内存块的边界范围，需求设置内存块中最终一个block的后一个block的bit为数值为1。因为确定内存块巨细的的逻辑是从开端block的bit位开端，直到找到下一个为1的bit位，该bit位表明一个新的内存块的开端方位。
3. 设置inuse字段的bit位数值，规则是内存块包括的第一个block对应的bit位设置为1，其他block对应的bit位设置为0。

当分配一个msize=1内存，pair字段对应的bit值如图。

当分配的内存块msize大于1，例如msize=5，分为两种状况：

1）内存块下的5个block坐落同一个pair index，从开端block开端，包括5个bit位数据1 0 0 0 0，下一个内存开端的bit设置为1，标识边界，一起inuse的bit位符号为1 0 0 0 0，只需求开端block的bit位符号为1，其他为0.

未运用

当产生收回逻辑时，内存块会被参加收回缓存链表，则对应的bit位需求符号为闲暇未运用状况。

static MALLOC_INLINE void
set_tiny_meta_header_free(const void *ptr, msize_t msize)
{
    // !msize is acceptable and means 65536
    uint32_t *block_header = TINY_BLOCK_HEADER_FOR_PTR(ptr);
    msize_t index = TINY_INDEX_FOR_PTR(ptr);
    msize_t midx = (index >> 5) << 1;
    uint32_t val = (1 << (index & 31));
    block_header[midx] |= val;      // BITARRAY_SET(block_header, index);
    block_header[midx + 1] &= ~val; // BITARRAY_CLR(in_use, index);
    //...
}

inuse字段bit位更新，首个block的bit位更新为0，这儿同样需求更新header的bit位，假如该内存之前分配过，则header的bit位没有改变，如图：

铲除

当一块内存块不存在时，相应的bit位需求被铲除，例如相邻闲暇内存块存在兼并的操作，则对应的bit位也需求更新，例如前后msize=5和misze=3的前后内存块兼并成一块msize=8的更大闲暇内存块，将misze=3的内存块的第一个block对应的bit位设置为0。

bit值改变如图：

static MALLOC_INLINE void
set_tiny_meta_header_middle(const void *ptr)
{
    // indicates this block is in the middle of an in use block
    uint32_t *block_header;
    uint32_t *in_use;
    msize_t index;
    block_header = TINY_BLOCK_HEADER_FOR_PTR(ptr);
    in_use = TINY_INUSE_FOR_HEADER(block_header);
    index = TINY_INDEX_FOR_PTR(ptr);
    BITARRAY_CLR(block_header, index);
    BITARRAY_CLR(in_use, index);
}
#define TINY_BLOCK_HEADER_FOR_REGION(region) ((void *)&(((tiny_region_t)region)->pairs))
#define TINY_INUSE_FOR_HEADER(_h) ((void *)&(((tiny_header_inuse_pair_t *)(_h))->inuse))

in_use和block_header能够经过region的字段直接获取，BITARRAY_CLR宏界说了清空bit位值的办法，一起封装了核算下标的操作，等效于上文的block_header index核算逻辑。

static void BITARRAY_CLR(uint32_t *bits, msize_t index)
{
    bits[(index >> 5) << 1] &= ~(1 << (index & 31));
}

状况判别

更新了bit信息之后，就能够依据header和inuse字段的bit值判别当时内存块的状况，例如判别一块内存是否处于闲暇状况。

static boolean_t tiny_meta_header_is_free(const void *ptr)
{
    uint32_t *block_header;
    uint32_t *in_use;
    msize_t index;
    block_header = TINY_BLOCK_HEADER_FOR_PTR(ptr);
    in_use = TINY_INUSE_FOR_HEADER(block_header);
    index = TINY_INDEX_FOR_PTR(ptr);
    if (!BITARRAY_BIT(block_header, index)) {
        return 0;
    }
    return !BITARRAY_BIT(in_use, index);
}

1. 获取内存块第一个block的index
2. 读取block_header字段对应bit位的数值，假如为0，阐明该内存块不存在，回来false
3. 假如内存块存在，读取in_use字段对应bit位的数值，假如为0，阐明是闲暇，回来true，不然回来false。

下图对应上述3种状况。

闲暇内存办理

除了记载内存状况，magazine需求运用其他数据结构办理内存，例如收回内存的复用。其间，闲暇链表mag_free_list是中心结构，当region中有内存块被收回时，依照size分级，将收回的内存块参加到magazine的闲暇链表结构mag_free_list中办理。例如tiny下mag_free_list共63个（如上图），阐明图中f1～f5坐落不同的Region，因为size分级相同，坐落同一个mag_free_list中。下图描绘Region中内存的收回进程。

1. Region1和Region2平分配若干size不等的内存，Region2中存在部分剩下空间未分配（白色区域）
2. Region1和Region2中部分内存被收回，例如先后收回了f1～f5，其间f1、f3、f4的msize相同是1，参加同一个mag_free_list中，f2、f5的msize相同是2，参加同一个mag_free_list中。
3. 再次分配内存，首要从对应size等级的mag_free_list平分配，例如分配2次16B的内存，先后取f4、f3，分配1次32B内存，取f5。
4. mag_bitmap字段记载了msize下是否存在之被收回的闲暇内存，是bit位数组，每个bit位对应一个msize，1表明存在，0表明不存在。这样，分配内存时，首要检查mag_bitmap下对应的bit位是为1，假如为1，则持续从对应的mag_free_list中回来内存。假如为0，则判别更大的bit位是否为1，即是否存在msize更大的闲暇内存块。

接下来，结合代码个图示详细讲解内存复用的完成机制。

数据结构

链表指针

mag_free_list链表结构的界说如下：

typedef struct magazine_s {
    free_list_t mag_free_list[MAGAZINE_FREELIST_SLOTS];
} magazine_t;

在tiny中，free_list_t结构被转化成了tiny_free_list_t结构，如下：

typedef struct {
    inplace_union previous;
    inplace_union next;
} tiny_free_list_t;

其间，previous字段是指向前一个闲暇内存块的指针数据，next字段是指向后一个闲暇内存块的指针数据，这样就能够遍历查询链表中一切闲暇内存块地址。如上图所示。之所以运用前16字节能够存储链表字段，是因为一个内存块至少包括16字节的长度(msize=1)。当内存块被收回时，会清空原本存储的数据，然后内存块的前16字节存储tiny_free_list_t字段数据。

msize数据

除了存储闲暇链表字段外，还会存储闲暇内存块的长度msize数据，方便后续操作，例如查找当时闲暇块在物理地址相邻的前一个闲暇块，如图所示：

static MALLOC_INLINE void
set_tiny_meta_header_free(const void *ptr, msize_t msize)
{
    //...
    if (msize > 1) {
        void *follower = FOLLOWING_TINY_PTR(ptr, msize);
        TINY_PREVIOUS_MSIZE(follower) = msize;
        TINY_FREE_SIZE(ptr) = msize;
    }
    if (msize == 0) {
        TINY_FREE_SIZE(ptr) = msize;
    }
}
#define TINY_FREE_SIZE(ptr) (((msize_t *)(ptr))[8])
#define TINY_PREVIOUS_MSIZE(ptr) ((msize_t *)(ptr))[-1]

其间FOLLOWING_TINY_PTR(ptr, msize)获取下一个内存块的开端地址，TINY_PREVIOUS_MSIZE获取该地址的前2字节，即当时内存块的最终2字节存储msize，TINY_FREE_SIZE(ptr)是开端地址偏移16字节后的2字节存储msize。

magazine相关

mag_free_list

如上文所述，magazine运用闲暇链表mag_free_list[slot]来办理一切闲暇的内存块，即magazine下一切region中的相同msize的闲暇内存块，都会被保护到同一个闲暇链表mag_free_list[slot]中，如图所示，magazine下共分配了region1和region2两块region，其间region1中包括两块msize=3的闲暇块，region2中包括一块，3个闲暇块组成了。

mag_bitmap

如上文所述，和mag_free_list字段对应，magazine运用mag_bitmap字段记载magazine是否存在msize的闲暇内存块，每个mag_bitmap[i]是uint32_t类型4字节32个bit位，因而能够存储32个msize的信息，详细能够参阅“bit位设置”的介绍。

region相关

free_blocks_by_slot

除了magazine保护的闲暇链表，每个region也记载了该region内的一切闲暇内存块，存储在free_blocks_by_slot字段中。

typedef struct tiny_region {
    // Indices of the first and last free block in this region. Value is the
    // block index + 1 so that 0 indicates no free block in this region for the
    // corresponding slot.
    region_free_blocks_t free_blocks_by_slot[NUM_TINY_SLOTS];
} * tiny_region_t;

free_blocks_by_slot数组存储的是相同msize的第一个闲暇块的block index和最终一个闲暇块的block index，index是从1开端，而不是0，假如free_blocks_by_slot[msize]是0，表明region中没有长度是msize的闲暇块。数据结构如下：

typedef struct {
    uint16_t first_block;
    uint16_t last_block;
} region_free_blocks_t;

region_free_blocks_t结构的first_block存储了region中最近一次被收回的闲暇内存块的block index，last_block存储了最先被收回的闲暇内存块的block index。

之所以region中也记载闲暇内存块，是为了方便操作闲暇链表的操作，例如快速定位region内最近一次被收回的内存块。

相关操作

剖析了数据结构后，接下来结合代码剖析闲暇链表的相关操作。在收拾逻辑之前，首要介绍一下magazine的多个region中闲暇内存块的链表结构。

增加进链表

当一个内存块被收回时，需求将其增加进闲暇链表，代码如下：

static void tiny_free_list_add_ptr(rack_t *rack, magazine_t *tiny_mag_ptr, void *ptr, msize_t msize)
{
    grain_t slot = (!msize || (msize > NUM_TINY_SLOTS)) ? NUM_TINY_SLOTS : msize - 1;
    tiny_free_list_t *free_ptr = ptr;
    tiny_free_list_t *free_head = tiny_mag_ptr->mag_free_list[slot].p;
    //1.设置闲暇状况
    set_tiny_meta_header_free(ptr, msize);
    //2.设置bit位状况
    if (free_head) {
    } else {
        BITMAPV_SET(tiny_mag_ptr->mag_bitmap, slot);
    }
    tiny_region_t region = TINY_REGION_FOR_PTR(ptr);
    //region内msize对应的闲暇内存index
    region_free_blocks_t *free_blocks = &region->free_blocks_by_slot[slot];
    //第一个闲暇块
    uint16_t first_free_block_index = free_blocks->first_block;
    //当时内存块的block index
    uint16_t this_block_index = TINY_INDEX_FOR_PTR(ptr);
    //存在msize对应的闲暇内存index
    if (first_free_block_index) {
        //firstblock对应的闲暇块
        tiny_free_list_t *old_first_free = TINY_PTR_FOR_INDEX(first_free_block_index - 1, region);
        //前一个内存块，坐落其他region内
        tiny_free_list_t *prev_ptr = free_list_unchecksum_ptr(rack, &old_first_free->previous);
        if (!prev_ptr) {
            //没有prev，则作为mag_free_list的首个元素
            tiny_mag_ptr->mag_free_list[slot].p = free_ptr;
        } else {
            //有prev，则刺进prev的后边
            prev_ptr->next.u = free_list_checksum_ptr(rack, free_ptr); // XXX
        }
        //设置prev联系
        free_ptr->previous.u = old_first_free->previous.u;        
        //设置next和prev联系，free_ptr成为链表中在region区的首个节点
        free_ptr->next.u = free_list_checksum_ptr(rack, old_first_free);
        old_first_free->previous.u = free_list_checksum_ptr(rack, free_ptr);
        //设置为闲暇blocks的第一个节点
        free_blocks->first_block = this_block_index + 1;
    } else {
        //当时region没有firstblock，ptr是region下第一个闲暇block
        tiny_free_list_t *prev_free = NULL;
        tiny_free_list_t *next_free;
        mag_index_t mag_index = MAGAZINE_INDEX_FOR_TINY_REGION(region);
        //遍历mag下的regions，找出前一个region的lastblock，prev_free是对应的内存块
        if (mag_index != DEPOT_MAGAZINE_INDEX
                && tiny_mag_ptr->mag_free_list[slot].p) {
            region_trailer_t *trailer = REGION_TRAILER_FOR_TINY_REGION(region);
            prev_free = tiny_earlier_region_last_free(tiny_mag_ptr, trailer, slot);
        }
        if (!prev_free) {
            //不存在prev，则作为mag_free_list的首个元素
            next_free = tiny_mag_ptr->mag_free_list[slot].p;
            tiny_mag_ptr->mag_free_list[slot].p = free_ptr;
        } else {
            //存在prev，则刺进prev之后
            next_free = free_list_unchecksum_ptr(rack, &prev_free->next);
            prev_free->next.u = free_list_checksum_ptr(rack, free_ptr);
        }
        free_ptr->previous.u = free_list_checksum_ptr(rack, prev_free);
        //从头设置prev和next
        if (next_free) {
            next_free->previous.u = free_list_checksum_ptr(rack, free_ptr);
        }
        free_ptr->next.u = free_list_checksum_ptr(rack, next_free);
        //成为当时region的firstblock
        free_blocks->first_block = free_blocks->last_block =
                this_block_index + 1;
    }
}

结合图示剖析：

1. 当内存ptr被收回，首要调用set_tiny_meta_header_free办法设置当时内存为闲暇状况，并更新设置msize信息。

2. 依据内存的msize定位mag_free_list，假如mag_free_list链表为空，则设置mag_bitmap，符号magazine存在msize的闲暇内存。

3. 依据region的free_blocks字段，查找region内存是否存在闲暇内存块，假如存在，则将ptr刺进该内存节点之前，并更新当时region的free_blocks->first_block为ptr的block index。下图中内存块5是当时region的first_block，ptr刺进3和5之间。

   

4. 假如不存在，则经过tiny_earlier_region_last_free办法，查找离当时region最近的前一个region中的闲暇内存块，将ptr刺进该内存节点之后，并更新当时region的free_blocks->first_block和last_block为ptr的block index。下图中，ptr地点的region没有闲暇块，则向前查找region，1是最近的闲暇块，ptr放在1之后。

   

   其间tiny_earlier_region_last_free办法经过遍历region链表，查找是否存在相同msize的闲暇块，直到遍历到当时region停止。

   static void * tiny_earlier_region_last_free(magazine_t *tiny_mag_ptr,
       region_trailer_t *trailer, grain_t slot)
   {
       //...
       while (next_trailer && next_trailer != trailer && count++ < 5) {
           tiny_region_t r = TINY_REGION_FOR_PTR(next_trailer);
           uint16_t block = r->free_blocks_by_slot[slot].last_block;
           if (block) {
               target_block = block;
               target_trailer = next_trailer;
           }
           next_trailer = next_trailer->next;
       }
   }
   

5. 假如前面的region不存在闲暇内存，则mag_free_list[msize]的首节点是ptr。

   

从链表删去

当闲暇内存块被从头运用，需求从闲暇链表结构中删去。

static void tiny_free_list_remove_ptr(rack_t *rack, magazine_t *tiny_mag_ptr, void *ptr, msize_t msize)
{
    grain_t slot = tiny_slot_from_msize(msize);
    tiny_free_list_t *free_ptr = ptr, *next, *previous;
    //后一个闲暇块
    next = free_list_unchecksum_ptr(rack, &free_ptr->next);
    //前一个闲暇块
    previous = free_list_unchecksum_ptr(rack, &free_ptr->previous);
    if (!previous) { //没有prev，则删去的是链表首节点 
        //next设置为首节点
        tiny_mag_ptr->mag_free_list[slot].p = next;
        if (!next) {
            BITMAPV_CLR(tiny_mag_ptr->mag_bitmap, slot);
        }
    } else {
        //设置prev的next指针指向next内存
        previous->next = free_ptr->next;
    }
    if (next) { //存在next内存
        //设置next的prev指针指向prev内存
        next->previous = free_ptr->previous;
    }
    tiny_region_t region = TINY_REGION_FOR_PTR(ptr);
    region_free_blocks_t *free_blocks = &region->free_blocks_by_slot[slot];
    uint16_t this_block_index = TINY_INDEX_FOR_PTR(ptr);
    //是否是region中first_block或许last_block
    boolean_t is_first = free_blocks->first_block == this_block_index + 1;
    boolean_t is_last = free_blocks->last_block == this_block_index + 1;
    if (is_first && is_last) {
        //是first_block和last_block，则region中只需该msize闲暇块，移除后，region内不存在msize闲暇块，更新为0
        free_blocks->first_block = free_blocks->last_block = 0;
    } else if (is_first) {
        //是first，则存在next内存，移除后first替换为next
        free_blocks->first_block = TINY_INDEX_FOR_PTR(next) + 1;
    } else if (is_last) {
        //是last，则存在prev内存，移除后last替换为previous
        free_blocks->last_block = TINY_INDEX_FOR_PTR(previous) + 1;
    }
}

结合图示剖析：

1. 例如闲暇内存块ptr被再次运用时，首要经过prev、next指针查找链表上前后闲暇块。
2. 假如没有prev，则ptr是mag_free_list链表的首节点，则将next设置为首节点，假如next也不存在，则ptr移除后链表中现已不存在msize的闲暇块了，调用BITMAPV_CLR清空将mag_bitmap上的对应bit符号方位为0。
3. 假如有prev，则prev的next指针指向next内存。这样ptr从链表中删去。

   

4. 更新region的free_blocks字段，假如first_block和last_block均等于ptr的block index，则当时region只存在一个msize的闲暇块ptr，移除后，first_block和last_block均置为0。
5. 假如first_block和last_block不等，则region中至少包括两个msize的闲暇块。
   1. 假如first_block是ptr的block index，则ptr是链表中在region范围内的第一个闲暇节点，ptr移除后，first_block替换为链表中后一个闲暇块的block index。

      

   2. 假如last_block是ptr的block index，则ptr是链表中在region范围内的最终一个闲暇节点，ptr移除后，last_block替换为链表中前一个闲暇块的block index。

      

检查前后闲暇块

获取相邻前一个闲暇块的内存开端地址。

static void *tiny_previous_preceding_free(void *ptr, msize_t *prev_msize)
{
    uint32_t *block_header;
    uint32_t *in_use;
    msize_t index;
    msize_t previous_msize;
    msize_t previous_index;
    void *previous_ptr;
    block_header = TINY_BLOCK_HEADER_FOR_PTR(ptr);
    in_use = TINY_INUSE_FOR_HEADER(block_header);
    index = TINY_INDEX_FOR_PTR(ptr);
    if (!index) {
        return NULL;
    }
    if ((previous_msize = get_tiny_previous_free_msize(ptr)) > index) {
        return NULL;
    }
    previous_index = index - previous_msize;
    previous_ptr = TINY_PTR_FOR_INDEX(previous_index, TINY_REGION_FOR_PTR(ptr));
    if (!BITARRAY_BIT(block_header, previous_index)) {
        return NULL;
    }
    if (BITARRAY_BIT(in_use, previous_index)) {
        return NULL;
    }
    if (get_tiny_free_size(previous_ptr) != previous_msize) {
        return NULL;
    }
    // conservative check did match true check
    *prev_msize = previous_msize;
    return previous_ptr;
}

ptr是当时闲暇内存块的地址，过程如下：

1. index是ptr的block index，运用get_tiny_previous_free_msize测验获取前一个闲暇内存的msize。

   #define TINY_PREVIOUS_MSIZE(ptr) ((msize_t *)(ptr))[-1]
   #define TINY_FREE_SIZE(ptr) (((msize_t *)(ptr))[8])
   static msize_t get_tiny_previous_free_msize(const void *ptr)
   {
       if (ptr != TINY_REGION_HEAP_BASE(TINY_REGION_FOR_PTR(ptr))) {
           void *prev_block = (void *)((uintptr_t)ptr - TINY_QUANTUM);
           uint32_t *prev_header = TINY_BLOCK_HEADER_FOR_PTR(prev_block);
           msize_t prev_index = TINY_INDEX_FOR_PTR(prev_block);
           if (BITARRAY_BIT(prev_header, prev_index)) {
               return 1;
           }
           msize_t *prev_msize_ptr = &TINY_PREVIOUS_MSIZE(ptr);
           return _malloc_read_uint16_via_rsp(prev_msize_ptr);
       }
       return 0;
   }
   

   首要判别向前偏移一个block的内存，假如BITARRAY_BIT为1，则存在内存块，msize是1，假如不是，则运用TINY_PREVIOUS_MSIZE宏取ptr地址的向前偏移2字节的内存，因为存储了前一个闲暇块的msize信息，回来值为previous_msize。

2. previous_ptr是向前偏移previous_msize长度后，前一个闲暇块的开端地址，previous_index是对应的block index。

3. 判别previous_index的block_header bit位，假如是1，则存在该内存，进一步判别inuse bit位，假如是0，则是闲暇块，调用get_tiny_free_size取8字节后的2字节存储的msize和之前的previous_msize比较，进一步校验。这些经过后，表明存在相邻的前一块闲暇块，长度是previous_msize。

相较于获取前一块内存地址，获取相邻地址后一块闲暇内存块的地址简略，ptr地址直接加上msize得到next开端地址。

size_t original_size = TINY_BYTES_FOR_MSIZE(msize);
void *next_block = ((unsigned char *)ptr + original_size);

如图所示：

底层内存办理

当分配和收回region时触发体系层的分配操作，实质调用底层接口办理虚拟内存，libmalloc做了封装，支持参数操控。

内存分配

void *mvm_allocate_pages(size_t size, unsigned char align, uint32_t debug_flags, int vm_page_label) {
    boolean_t add_prelude_guard_page = debug_flags & MALLOC_ADD_PRELUDE_GUARD_PAGE;
    boolean_t add_postlude_guard_page = debug_flags & MALLOC_ADD_POSTLUDE_GUARD_PAGE;
    boolean_t purgeable = debug_flags & MALLOC_PURGEABLE;
    boolean_t use_entropic_range = !(debug_flags & DISABLE_ASLR);
    vm_address_t vm_addr;
    uintptr_t addr;
    vm_size_t allocation_size = round_page_quanta(size);
    mach_vm_offset_t allocation_mask = ((mach_vm_offset_t)1 << align) - 1;
    int alloc_flags = VM_FLAGS_ANYWHERE | VM_MAKE_TAG(vm_page_label);
    kern_return_t kr;
    if (!allocation_size) {
        allocation_size = vm_page_quanta_size;
    }
    if (add_postlude_guard_page || add_prelude_guard_page) {
        if (add_prelude_guard_page && align > vm_page_quanta_shift) {
            allocation_size += (1 << align) + large_vm_page_quanta_size;
        } else {
            allocation_size += add_prelude_guard_page && add_postlude_guard_page ?
                    2 * large_vm_page_quanta_size : large_vm_page_quanta_size;
        }
    }
    if (purgeable) {
        alloc_flags |= VM_FLAGS_PURGABLE;
    }
    if (allocation_size < size) {
        return NULL;
    }
retry:
    vm_addr = use_entropic_range ? entropic_address : vm_page_quanta_size;
    kr = mach_vm_map(mach_task_self(), &vm_addr, allocation_size,
            allocation_mask, alloc_flags, MEMORY_OBJECT_NULL, 0, FALSE,
            VM_PROT_DEFAULT, VM_PROT_ALL, VM_INHERIT_DEFAULT);
    if (kr == KERN_NO_SPACE && use_entropic_range) {
        vm_addr = vm_page_quanta_size;
      kr = mach_vm_map(mach_task_self(), &vm_addr, allocation_size,
              allocation_mask, alloc_flags, MEMORY_OBJECT_NULL, 0, FALSE,
              VM_PROT_DEFAULT, VM_PROT_ALL, VM_INHERIT_DEFAULT);
    }
    if (kr) {
        if (kr != KERN_NO_SPACE) {
            //...
        }
        return NULL;
    }
    //...
    if (add_postlude_guard_page || add_prelude_guard_page) {
        //...
        mvm_protect((void *)addr, size, PROT_NONE, debug_flags);
    }
    return (void *)addr;
}

中心调用是经过xnu的mach_vm_map分配一块allocation_size巨细的虚拟内存，allocation_size是经过对齐后的巨细，debug_flags操控分配逻辑，例如add_prelude_guard_page和add_postlude_guard_page，经过mvm_protect办法对指定内存的操作权限进行操控。

内存收回

void mvm_deallocate_pages(void *addr, size_t size, unsigned debug_flags)
{
    boolean_t added_prelude_guard_page = debug_flags & MALLOC_ADD_PRELUDE_GUARD_PAGE;
    boolean_t added_postlude_guard_page = debug_flags & MALLOC_ADD_POSTLUDE_GUARD_PAGE;
    vm_address_t vm_addr = (vm_address_t)addr;
    vm_size_t allocation_size = size;
    kern_return_t kr;
    if (added_prelude_guard_page) {
        vm_addr -= large_vm_page_quanta_size;
        allocation_size += large_vm_page_quanta_size;
    }
    if (added_postlude_guard_page) {
        allocation_size += large_vm_page_quanta_size;
    }
    kr = vm_deallocate(mach_task_self(), vm_addr, allocation_size);
    if (kr) {
        malloc_zone_error(debug_flags, false, "Can't deallocate_pages region at %pn", addr);
    }
}

中心办法是经过vm_deallocate收回对齐后的内存空间。

内存权限

#define PROT_NONE       0x00    /* [MC2] no permissions */
#define PROT_READ       0x01    /* [MC2] pages can be read */
#define PROT_WRITE      0x02    /* [MC2] pages can be written */
#define PROT_EXEC       0x04    /* [MC2] pages can be executed */
void mvm_protect(void *address, size_t size, unsigned protection, unsigned debug_flags)
{
    kern_return_t err;
    if ((debug_flags & MALLOC_ADD_PRELUDE_GUARD_PAGE) && !(debug_flags & MALLOC_DONT_PROTECT_PRELUDE)) {
        err = mprotect((void *)((uintptr_t)address - large_vm_page_quanta_size), large_vm_page_quanta_size, protection);
    }
    if ((debug_flags & MALLOC_ADD_POSTLUDE_GUARD_PAGE) && !(debug_flags & MALLOC_DONT_PROTECT_POSTLUDE)) {
        err = mprotect((void *)(round_page_quanta(((uintptr_t)address + size))), large_vm_page_quanta_size, protection);
    }
}

调用mprotect设置虚拟内存的拜访权限，address和size操控了内存范围。

了解tiny相关结构后，接下来剖析tiny是怎么分配和和收回内存的。

depot magazine

depot magazine是rack下一个特别的magazine，下标是-1.

#define DEPOT_MAGAZINE_INDEX -1
rack->magazines[DEPOT_MAGAZINE_INDEX]

depot magazine下保护的region是从原magazine中的region搬迁过来的，触发条件是，当内存收回时，region中的闲暇内存占比到达必定阈值时，产生搬迁，首要包括两部分：

1. region从原magazine搬迁至depot magazine。
2. region内的一切闲暇内存块从原mag_free_list闲暇链表搬迁至depot magazine的mag_free_list。

搬迁操作如图，深黄色要搬迁的region，regions链表和freelist搬迁至depot magazine中。

static MALLOC_INLINE boolean_t
tiny_free_try_recirc_to_depot(rack_t *rack,
                              magazine_t *tiny_mag_ptr,
                              mag_index_t mag_index,
                              region_t region,
                              void *headptr,
                              size_t headsize,
                              void *ptr,
                              msize_t msize)
{
    region_trailer_t *node = REGION_TRAILER_FOR_TINY_REGION(region);
    size_t bytes_used = node->bytes_used;
    if (DEPOT_MAGAZINE_INDEX != mag_index) {
        //当闲暇内存到达必定程度，移到depot magazine
        if (tiny_magazine_below_recirc_threshold(tiny_mag_ptr)) {
            return tiny_free_do_recirc_to_depot(rack, tiny_mag_ptr, mag_index);
        }
    }
}

首要进行阈值判别：

static MALLOC_INLINE boolean_t tiny_magazine_below_recirc_threshold(magazine_t *mag_ptr)
    size_t a = mag_ptr->num_bytes_in_magazine;  // Total bytes allocated to this magazine
    size_t u = mag_ptr->mag_num_bytes_in_objects; // In use (malloc'd) from this magaqzine
    return a - u > ((3 * TINY_HEAP_SIZE) / 2)
            && u < DENSITY_THRESHOLD(a);
}
#define DENSITY_THRESHOLD(a) ((a) - ((a) >> 2)) 

条件是当magazine中未运用的内存巨细大于总内存的3/4时，产生搬迁操作。

调用tiny_free_do_recirc_to_depot办法，代码如下：

static boolean_t tiny_free_do_recirc_to_depot(rack_t *rack, magazine_t *tiny_mag_ptr, mag_index_t mag_index)
{
    region_trailer_t *node = tiny_mag_ptr->lastNode;
    region_t sparse_region = TINY_REGION_FOR_PTR(node);
    //...
    recirc_list_extract(rack, tiny_mag_ptr, node);
    int objects_in_use = tiny_free_detach_region(rack, tiny_mag_ptr, sparse_region);
    magazine_t *depot_ptr = &(rack->magazines[DEPOT_MAGAZINE_INDEX]);
    //...
    size_t bytes_inplay = tiny_free_reattach_region(rack, depot_ptr, sparse_region);
    tiny_mag_ptr->mag_num_bytes_in_objects -= bytes_inplay;
    tiny_mag_ptr->num_bytes_in_magazine -= TINY_HEAP_SIZE;
    tiny_mag_ptr->mag_num_objects -= objects_in_use;
    //...
    depot_ptr->mag_num_bytes_in_objects += bytes_inplay;
    depot_ptr->num_bytes_in_magazine += TINY_HEAP_SIZE;
    depot_ptr->mag_num_objects += objects_in_use;
    recirc_list_splice_last(rack, depot_ptr, node);
    //...
}

包括以下流程：

1. 调用recirc_list_extract办法将region从magazine的region链表中删去

region_trailer_t *node = tiny_mag_ptr->lastNode;
recirc_list_extract(rack, tiny_mag_ptr, node);

2. 调用tiny_free_detach_region办法将region中的一切内存块从magazine的freelist中删去。

int tiny_free_detach_region(rack_t *rack, magazine_t *tiny_mag_ptr, region_t r)
{
    uintptr_t start = (uintptr_t)TINY_REGION_HEAP_BASE(r);
    uintptr_t current = start;
    uintptr_t limit = (uintptr_t)TINY_REGION_HEAP_END(r);
    boolean_t is_free;
    msize_t msize;
    region_trailer_t *trailer = REGION_TRAILER_FOR_TINY_REGION(r);
    while (current < limit) {
        msize = get_tiny_meta_header((void *)current, &is_free);
        if (is_free && !msize && (current == start)) {
            break;
        }
        if (!msize) {
            break;
        }
        if (is_free) {
            //从闲暇链表中删去闲暇内存
            tiny_free_list_remove_ptr(rack, tiny_mag_ptr, (void *)current, msize);
        }
        current += TINY_BYTES_FOR_MSIZE(msize);
    }
    return trailer->objects_in_use;
}

办法内部遍历region中的一切闲暇内存块，调用tiny_free_list_remove_ptr将其从mag_free_list中删去。 3. 调用tiny_free_reattach_region办法将region中的一切内存块增加进depot magazine的freelist中。

size_t tiny_free_reattach_region(rack_t *rack, magazine_t *tiny_mag_ptr, region_t r)
{
    uintptr_t start = (uintptr_t)TINY_REGION_HEAP_BASE(r);
    uintptr_t current = start;
    uintptr_t limit = (uintptr_t)TINY_REGION_HEAP_END(r);
    boolean_t is_free;
    msize_t msize;
    size_t bytes_used = REGION_TRAILER_FOR_TINY_REGION(r)->bytes_used;
    while (current < limit) {
        msize = get_tiny_meta_header((void *)current, &is_free);
        if (is_free && !msize && (current == start)) {
            // first block is all free
            break;
        }
        if (!msize) {
            break;
        }
        if (is_free) {
            //参加free链表
            tiny_free_list_add_ptr(rack, tiny_mag_ptr, (void *)current, msize);
        }
        current += TINY_BYTES_FOR_MSIZE(msize);
    }
    return bytes_used;
}

办法内部遍历region中的一切闲暇内存块，调用tiny_free_reattach_region将其增加进mag_free_list中。

4. 更新magazine的计算信息字段，例如mag_num_bytes_in_objects。
5. 调用recirc_list_splice_last办法将region节点增加进depot magazine的region trailer链表

recirc_list_splice_last(rack, depot_ptr, node);

recirc_list_extract、recirc_list_splice_last的详细完成上文现已介绍。

中心流程

介绍完相关结构，接下来还是以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]);
    //...
#if CONFIG_TINY_CACHE
    ptr = tiny_mag_ptr->mag_last_free;
    if (tiny_mag_ptr->mag_last_free_msize == msize) {
        tiny_mag_ptr->mag_last_free = NULL;
        tiny_mag_ptr->mag_last_free_msize = 0;
        tiny_mag_ptr->mag_last_free_rgn = NULL;
        tiny_check_zero_and_clear(ptr, msize, cleared_requested);
        return ptr;
    }
#endif
    while (1) {
        ptr = tiny_malloc_from_free_list(rack, tiny_mag_ptr, mag_index, msize);
        if (ptr) {
            tiny_check_zero_and_clear(ptr, msize, cleared_requested);
            return ptr;
        }
#if CONFIG_RECIRC_DEPOT
        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) {
                tiny_check_zero_and_clear(ptr, msize, cleared_requested);
                return ptr;
            }
        }
#endif
        if (!tiny_mag_ptr->alloc_underway) {
            void *fresh_region;
            tiny_mag_ptr->alloc_underway = TRUE;
            fresh_region = mvm_allocate_pages(TINY_REGION_SIZE,
                                        TINY_BLOCKS_ALIGN,
                                        MALLOC_FIX_GUARD_PAGE_FLAGS(rack->debug_flags),
                                        VM_MEMORY_MALLOC_TINY);
            if (!fresh_region) { // out of memory!
                tiny_mag_ptr->alloc_underway = FALSE;
                return NULL;
            }
            ptr = tiny_malloc_from_region_no_lock(rack, tiny_mag_ptr, mag_index, msize, fresh_region);
        } else {
            yield();
        }
    }
}

中心过程收拾如下：

1. 选取处理内存的magazine对象tiny_mag_ptr。
2. cache匹配逻辑，假如射中则直接回来缓存mag_last_free，不射中持续。
3. 从缓存链表freeelist和现有的region中查找可用内存，成功回来，失利持续。
4. 查找depot magazine是否有闲暇内存，假如有，则将region以及region内的闲暇内存搬迁到tiny_mag_ptr，不存在则持续。
5. 分配一块新的region，并从新region平分配内存。假如失利，回来NULL。

每一过程涉及的内容较多，下面结合代码与图示详细打开讲解。

cache逻辑

为了提高分配时的性能，当最近一次内存被收回时，运用mag_last_free和mag_last_free_msize记载这次被收回的内存和msize，而不增加进闲暇链表mag_free_list。当下一次分配内存时，假如size巨细匹配缓存巨细，则直接取缓存内存mag_last_free，而不从闲暇链表mag_free_list中查找。这样提高了分配效率，假如缓存没匹配上，则从mag_free_list中查找。履行cache匹配逻辑，cache会在内存收回时更新。

更新

因为magazine中存储的cache是最近一次被收回的内存，因而每次收回内存时，会触发cache的更新逻辑。

void free_tiny(rack_t *rack, void *ptr, region_t tiny_region, size_t known_size,
        boolean_t partial_free)
{
    //取当时cache
    void *ptr2 = tiny_mag_ptr->mag_last_free;
    msize_t msize2 = tiny_mag_ptr->mag_last_free_msize;
    region_t rgn2 = tiny_mag_ptr->mag_last_free_rgn;
    //更新cache
    tiny_mag_ptr->mag_last_free = ptr;
    tiny_mag_ptr->mag_last_free_msize = msize;
    tiny_mag_ptr->mag_last_free_rgn = tiny_region;
    msize = msize2;
    ptr = ptr2;
    tiny_region = rgn2;
    flags |= TINY_FREE_FLAG_FROM_CACHE;
    //之前cache收回增加进freelist
    if (tiny_free_no_lock(rack, tiny_mag_ptr, mag_index, tiny_region, ptr, msize, flags)) {
    }
}

首要取出magazine的cache，cache更新为当时收回的内存，将之前cache收回增加进freelist。更新cache相关的三个字段：

• mag_last_free：收回的内存地址，作为cache内存地址
• mag_last_free_msize：收回的内存的msize，表明缓存内存块的巨细，cache匹配时运用
• mag_last_free_rgn：收回内存的region。

不管之前的cache是否被运用，都会被更新成新收回的内存和msize，如图：

运用

分配内存时，首要匹配cache，假如要分配的内存msize和mag_last_free_msize持平，则射中cache，直接回来mag_last_free，而且清空cache相关字段。假如下次内存分配前没有产生内存收回，则下次分配时无缓存，履行后续逻辑。

void *tiny_malloc_should_clear(rack_t *rack, msize_t msize, boolean_t cleared_requested)
{
    //...
#if CONFIG_TINY_CACHE
    ptr = tiny_mag_ptr->mag_last_free;
    //匹配成功，直接回来cache，清空cache字段。
    if (tiny_mag_ptr->mag_last_free_msize == msize) {
        tiny_mag_ptr->mag_last_free = NULL;
        tiny_mag_ptr->mag_last_free_msize = 0;
        tiny_mag_ptr->mag_last_free_rgn = NULL;
        tiny_check_zero_and_clear(ptr, msize, cleared_requested);
        return ptr;
    }
#endif
}

假如cache未射中，则调用tiny_malloc_from_free_list办法从已有的region中查找一块适宜的内存空间回来。

闲暇内存查找

从magazine办理的闲暇链表mag_free_list或许当时region内的剩下空间查找可用的内存块回来。

void *tiny_malloc_from_free_list(rack_t *rack, magazine_t *tiny_mag_ptr, mag_index_t mag_index, msize_t msize)
{
    tiny_free_list_t *ptr;
    msize_t this_msize;
    //核算msize
    grain_t slot = tiny_slot_from_msize(msize);
    //查找闲暇链表
    free_list_t *free_list = tiny_mag_ptr->mag_free_list;
    free_list_t *the_slot = free_list + slot;
    tiny_free_list_t *next;
    free_list_t *limit;
    uint64_t bitmap;
    //剩下size
    msize_t leftover_msize;
    tiny_free_list_t *leftover_ptr;
    //准确匹配，链表头节点
    ptr = the_slot->p;
    if (ptr) { //存在闲暇节点
        next = free_list_unchecksum_ptr(rack, &ptr->next);
        if (next) {
            next->previous = ptr->previous; //从链表中删去ptr
        } else {
            BITMAPV_CLR(tiny_mag_ptr->mag_bitmap, slot); //没有剩下的内存块，slot位对应的bitmap置为0
        }
        the_slot->p = next; //next变为链表的头节点
        this_msize = msize; //记载this_msize
        //更新region信息
        tiny_update_region_free_list_for_remove(slot, ptr, next);
        tiny_check_and_zero_inline_meta_from_freelist(rack, ptr, msize);
        //查找成功
        goto return_tiny_alloc;
    }
    //取出表明大于msize的bitmap
    bitmap = ((uint64_t *)(tiny_mag_ptr->mag_bitmap))[0] & ~((1ULL << slot) - 1);
    //闲暇链表中没有任何内存块，则走try_tiny_malloc_from_end逻辑
    if (!bitmap) {
        goto try_tiny_malloc_from_end;
    }
    //找到最低一个bit不为0的bitmap的方位
    slot = BITMAPV_CTZ(bitmap);
    limit = free_list + NUM_TINY_SLOTS;
    free_list += slot;
    if (free_list < limit) {
        ptr = free_list->p;
        if (ptr) {
            next = free_list_unchecksum_ptr(rack, &ptr->next);
            free_list->p = next;
            if (next) {
                next->previous = ptr->previous;
            } else {
                //没有剩下的内存块，slot位对应的bitmap置为0
                BITMAPV_CLR(tiny_mag_ptr->mag_bitmap, slot);
            }
            this_msize = get_tiny_free_size(ptr);
            tiny_update_region_free_list_for_remove(slot, ptr, next);
            tiny_check_and_zero_inline_meta_from_freelist(rack, ptr, this_msize);
            //剩下size参加free链表，回来ptr
            goto add_leftover_and_proceed;
        }
    }
    ptr = limit->p;
    if (ptr) {
        this_msize = get_tiny_free_size(ptr);
        next = free_list_unchecksum_ptr(rack, &ptr->next);
        //剩下size依然大于NUM_TINY_SLOTS
        if (this_msize - msize > NUM_TINY_SLOTS) {
            leftover_msize = this_msize - msize;
            leftover_ptr = (tiny_free_list_t *)((unsigned char *)ptr + TINY_BYTES_FOR_MSIZE(msize));
            tiny_free_list_t tmp_ptr = *ptr;
            tiny_check_and_zero_inline_meta_from_freelist(rack, ptr, this_msize);
            //剩下内存依然参加limit的free链表中
            limit->p = leftover_ptr;
            if (next) {
                next->previous.u = free_list_checksum_ptr(rack, leftover_ptr);
            }
            leftover_ptr->previous = tmp_ptr.previous;
            leftover_ptr->next = tmp_ptr.next;
            //对应bitmap设置为free
            set_tiny_meta_header_free(leftover_ptr, leftover_msize);
            this_msize = msize;
            tiny_update_region_free_list_for_remove(NUM_TINY_SLOTS, ptr, leftover_ptr);
            goto return_tiny_alloc;
        }
        if (next) {
            next->previous = ptr->previous;
        }
        limit->p = next;
        tiny_update_region_free_list_for_remove(slot, ptr, next);
        tiny_check_and_zero_inline_meta_from_freelist(rack, ptr, this_msize);
        //剩下size参加free链表，回来ptr
        goto add_leftover_and_proceed;
        /* NOTREACHED */
    }
try_tiny_malloc_from_end:
    //最终请求的heap region中未运用的巨细大于需求的size
    if (tiny_mag_ptr->mag_bytes_free_at_end >= TINY_BYTES_FOR_MSIZE(msize)) {
        //mag_last_region是低地址，因而可用区域的地址ptr是mag_last_region-mag_bytes_free_at_end
        ptr = (tiny_free_list_t *)((uintptr_t)TINY_REGION_HEAP_END(tiny_mag_ptr->mag_last_region) - tiny_mag_ptr->mag_bytes_free_at_end);
        //更新未运用巨细
        tiny_mag_ptr->mag_bytes_free_at_end -= TINY_BYTES_FOR_MSIZE(msize);
        if (tiny_mag_ptr->mag_bytes_free_at_end) {
            // let's add an in use block after ptr to serve as boundary
            //ptr~ptr+msize对应的block范围符号为运用中
            set_tiny_meta_header_in_use_1((unsigned char *)ptr + TINY_BYTES_FOR_MSIZE(msize));
        }
        this_msize = msize;
        goto return_tiny_alloc;
    }
    return NULL;
add_leftover_and_proceed: //处理剩下内存
    if (!this_msize || (this_msize > msize)) {
        // XXX This works even when (this_msize == 0) because the unsigned
        // subtraction wraps around to the correct result
        //剩下esize
        leftover_msize = this_msize - msize;
        //对应的地址
        leftover_ptr = (tiny_free_list_t *)((unsigned char *)ptr + TINY_BYTES_FOR_MSIZE(msize));
        //参加free链表
        tiny_free_list_add_ptr(rack, tiny_mag_ptr, leftover_ptr, leftover_msize);
        this_msize = msize;
    }
return_tiny_alloc:
    tiny_mag_ptr->mag_num_objects++;
    tiny_mag_ptr->mag_num_bytes_in_objects += TINY_BYTES_FOR_MSIZE(this_msize);
    // Check that the region cookie is intact and update the region's bytes in use count
    tiny_region_t region = TINY_REGION_FOR_PTR(ptr);
    region_check_cookie(region, &REGION_COOKIE_FOR_TINY_REGION(region));
    region_trailer_t *trailer = REGION_TRAILER_FOR_TINY_REGION(region);
    size_t bytes_used = trailer->bytes_used + TINY_BYTES_FOR_MSIZE(this_msize);
    trailer->bytes_used = (unsigned int)bytes_used;
    trailer->objects_in_use++;
    // Emptiness discriminant
    if (bytes_used < DENSITY_THRESHOLD(TINY_HEAP_SIZE)) {
    } else {
        trailer->recirc_suitable = FALSE;
    }
    if (this_msize > 1) {
        set_tiny_meta_header_in_use(ptr, this_msize);
    } else {
        set_tiny_meta_header_in_use_1(ptr);
    }
    return ptr;
}

代码较多，可是全体思路以下3点：

1. 依据需求的msize，首要从闲暇链表mag_free_list中查找一块适宜的闲暇内存块。
2. 假如闲暇链表中没有找到，则从region的剩下空间中划分一块msize的内存块
3. 假如都没有找到，则回来NULL。 从mag_free_list的查找战略，分为以下2点：
4. 首要查找msize巨细彻底匹配的闲暇内存块，找到回来
5. 其次查找较大msize的内存块，假如找到，则拆分分2块，前一块内存巨细是需求的msize回来，后一块是剩下的内存，持续参加闲暇链表中，剩下的内存分为2种状况
   1. 剩下msize小于limitsize，参加对应mag_free_list[slot]
   2. 剩下msize大于等于limitsize，依然放在mag_free_list[limit]里
   limitsize是tiny内存的最大（1008字节）尺寸/16字节。

为了直观的介绍，用下图表明region的内存状况。

接下来详细剖析：

1. 例如msize是需求分配的内存size，ptr用于存找到的内存块地址，依据msize核算其在mag_free_list的下标slot。

2. 首要准确匹配，查找mag_free_list[slot]中是否有闲暇内存块，假如有，则查找成功，经过更新next、prev指针将ptr从闲暇链表中删去。假如删去后链表为空，则将mag_bitmap对应的符号位铲除，表明magazine没有msize的闲暇内存。一起调用tiny_update_region_free_list_for_remove办法更新region的free_blocks_by_slot字段。操作完毕后，进入return_tiny_alloc流程。

3. 假如准确匹配没找到，则从mag_free_list[i]（i>slot）存储较大闲暇块的链表中查找。详细完成如下：

   • 读取mag_bitmap上存储的数据，回来一切bit位是1且高于msize的bit位的下标，这些下标对应的size等级均大于msize。假如没有找到bit位，则不持续处理，进入try_tiny_malloc_from_end流程。

   • 假如找到，则经过BITMAPV_CTZ(bitmap)从中取出最低的bit位下标，对应的size等级最小。如图，例如需求分配msize=2（32B的）内存，对应的bit位如下，取出大于该bit位的一切值为1的bit位数据，取出其间最低的bit位，对应的msize=4。

     

   • 定位到对应的slot下标和mag_free_list[slot]链表进口，假如slot小于limit（limit是tiny内存mag_free_list[]最大的下标63），则将mag_free_list[slot]的闲暇内存块拆分红两块，前半部分作为分配的内存回来，后半部分作为一块新的闲暇内存从头参加对应的mag_free_list中，如图所示：

     

     例如，找到msize=4的内存块，首要修正前后指针将内存块从原链表删去，然后进入add_leftover_and_proceed流程，进入拆分逻辑，例如需求msize=2的内存，则取前32B的内存块回来，一起剩下的32B的内存块参加对应的mag_free_list[slot]中。

   • 假如没找到，则查找最终一个链表mag_free_list[limit]中的闲暇内存块，假如找到，修正前后指针将内存块从原链表删去，拆分红两块，前msize部分作为ptr回来，针对剩下内存块（leftover_ptr）判别，假如块leftover_ptr的size依然大于limit size（1008），则依然将leftover_ptr参加mag_free_list[limit]中。如图所示，内存块1056B，取前32B回来，剩下部分1024B，依然参加mag_free_list[limit]。

     

     一起将leftover_ptr参加pairs状况符号位中，leftover_ptr是新的内存块。如下图，拆分后，pairs状况符号位多记载了一个leftover_ptr内存信息。然后走return_tiny_alloc流程。

     

   • 假如leftover_ptr的size小于等于limit size，则和过程c相同进入add_leftover_and_proceed流程。

4. 当时面的闲暇链表逻辑均没有可用的内存块时，则进入try_tiny_malloc_from_end流程，即检查magazine的当时region（mag_last_region）剩下的空间巨细mag_bytes_free_at_end是否满意分配msize需求，假如满意，则分配后进入return_tiny_alloc流程，不然直接回来NULL，表明内存查找失利。如图，mag_bytes_free_at_end满意分配msize，则分配一块msize的内存，mag_bytes_free_at_end-=msize。

   

5. add_leftover_and_proceed流程，处理拆分大内存块后的逻辑，将剩下内存leftover_ptr参加对应size的闲暇链表中，并在pairs中设置状况符号为闲暇，进入return_tiny_alloc流程

6. return_tiny_alloc流程，最终流程，将当时分配到的ptr，设置pairs中设置状况符号为运用中，并更新magezine和region相关的计算信息，包括

   tiny_mag_ptr->mag_num_objects++;
   tiny_mag_ptr->mag_num_bytes_in_objects
   trailer->bytes_used = (unsigned int)bytes_used;
   trailer->objects_in_use++;
   

   • mag_num_objects：magazine分配的总内存块数
   • mag_num_bytes_in_objects：magazine分配的总内存巨细
   • bytes_used：region运用的总内存巨细
   • objects_in_use：region运用的总内存块数

全体逻辑能够用一张流程图来表明：

depot查找

假如调用tiny_malloc_from_free_list办法没有找到可用的内存块，则调用tiny_get_region_from_depot办法检查depot magazine中的region中是否有适宜的内存块。

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) {
        return ptr;
    }
}
static boolean_t tiny_get_region_from_depot(rack_t *rack, magazine_t *tiny_mag_ptr, mag_index_t mag_index, msize_t msize)
{
    magazine_t *depot_ptr = &(rack->magazines[DEPOT_MAGAZINE_INDEX]);
    region_trailer_t *node;
    region_t sparse_region;
    msize_t try_msize = msize;
    while (1) {
        //寻找一个大于等于请求巨细msize的节点，回来该节点的heap region
        sparse_region = tiny_find_msize_region(rack, depot_ptr, DEPOT_MAGAZINE_INDEX, try_msize);
        if (NULL == sparse_region) { // Depot empty?
            return 0;
        }
        node = REGION_TRAILER_FOR_TINY_REGION(sparse_region);
        if (0 == node->pinned_to_depot) {
            // Found one!
            break;
        }
        try_msize++;
        if (try_msize > NUM_TINY_SLOTS) {
            SZONE_MAGAZINE_PTR_UNLOCK(depot_ptr);
            return 0;
        }
    }
    //经过trailer，从node链表中移除region
    recirc_list_extract(rack, depot_ptr, node);
    //将闲暇内存从depot_ptr的free链表中删去
    int objects_in_use = tiny_free_detach_region(rack, depot_ptr, sparse_region);
    // Transfer ownership of the region
    MAGAZINE_INDEX_FOR_TINY_REGION(sparse_region) = mag_index;
    //将闲暇内存参加tiny_mag_ptr的free链表
    size_t bytes_inplay = tiny_free_reattach_region(rack, tiny_mag_ptr, sparse_region);
    depot_ptr->mag_num_bytes_in_objects -= bytes_inplay;
    depot_ptr->num_bytes_in_magazine -= TINY_HEAP_SIZE;
    depot_ptr->mag_num_objects -= objects_in_use;
    tiny_mag_ptr->mag_num_bytes_in_objects += bytes_inplay;
    tiny_mag_ptr->num_bytes_in_magazine += TINY_HEAP_SIZE;
    tiny_mag_ptr->mag_num_objects += objects_in_use;
    //经过trailer，将region参加tiny_mag_ptr的链表
    recirc_list_splice_last(rack, tiny_mag_ptr, node);
    return 1;
}

全体逻辑如下：

1. 遍历depot magazine中的freelist，查找巨细满意msize的闲暇内存块，假如存在，回来地点的region。try_msize是要匹配的size，初识是msize，假如没有找到，则try_msize++，只需size大于等于msize，都满意条件。假如未找到，回来0，表明从depot magazine中查找失利。查找逻辑如下：

   static region_t tiny_find_msize_region(rack_t *rack, magazine_t *tiny_mag_ptr, mag_index_t mag_index, msize_t msize)
   {
       tiny_free_list_t *ptr;
       grain_t slot = tiny_slot_from_msize(msize);
       free_list_t *free_list = tiny_mag_ptr->mag_free_list;
       free_list_t *the_slot = free_list + slot;
       free_list_t *limit;
       #if defined(__LP64__)
           uint64_t bitmap;
       #else
           uint32_t bitmap;
       #endif
           ptr = the_slot->p;
       if (ptr) {
           return TINY_REGION_FOR_PTR(ptr);
       }
       #if defined(__LP64__)
           bitmap = ((uint64_t *)(tiny_mag_ptr->mag_bitmap))[0] & ~((1ULL << slot) - 1);
       #else
           bitmap = tiny_mag_ptr->mag_bitmap[0] & ~((1 << slot) - 1);
       #endif
       if (!bitmap) {
           return NULL;
       }
       slot = BITMAPV_CTZ(bitmap);
       limit = free_list + NUM_TINY_SLOTS;
       free_list += slot;
       if (free_list < limit) {
           ptr = free_list->p;
           if (ptr) {
               return TINY_REGION_FOR_PTR(ptr);
           }
       }
       ptr = limit->p;
       if (ptr) {
           return TINY_REGION_FOR_PTR(ptr);
       }
       return NULL;
   }
   

   逻辑和tiny_malloc_from_free_list类似，首要核算msize对应的slot，然后先从对应的mag_free_list[slot]中准确匹配，假如失利，则从mag_free_listslot找size更大的闲暇内存块，最终查找mag_free_list[limit]，假如找到，回来内存块地点的region，不然回来NULL，查找失利。

2. 假如查找成功，则将depot中的region从region链表中搬迁至tiny_mag_ptr，一起将region中的闲暇内存块从freelist中搬迁至tiny_mag_ptr的freelist中。如图所示，深黄色是查找到的region，从depot的regions链表和freelist中搬迁至新的magazine下。

   

3. 更新depot magazine和tiny_mag_ptr的计算信息。

当调用tiny_get_region_from_depot查好成功时，再次调用tiny_malloc_from_free_list办法从magazine中查找，因为上述逻辑仅仅把内存搬迁至magazine的相应结构中，所以需求再查找一次。

region分配

假如查找失利，阐明magazine中的没有可用的闲暇内存块，则从新的region平分配内存，包括两部分：

1. 新分配一块region空间
2. 从region平分配msize的内存，将region参加magazine结构中办理。

虚拟内存分配

首要调用mvm_allocate_pages办法分配一块region虚拟内存。

fresh_region = mvm_allocate_pages(TINY_REGION_SIZE,
                    TINY_BLOCKS_ALIGN,
                    MALLOC_FIX_GUARD_PAGE_FLAGS(rack->debug_flags),
                    VM_MEMORY_MALLOC_TINY);

TINY_REGION_SIZE是region的巨细范围，依照TINY_BLOCKS_ALIGN巨细对齐，一起支持传递一些flags参数，操控分配行为。

内存块分配

新region分配后，调用tiny_malloc_from_region_no_lock办法，从region平分配一块内存块，并将region参加rack和magazine的结构中保护。

ptr = tiny_malloc_from_region_no_lock(rack, tiny_mag_ptr, mag_index, msize, fresh_region);
return ptr;
static void *tiny_malloc_from_region_no_lock(rack_t *rack,
                                magazine_t *tiny_mag_ptr,
                                mag_index_t mag_index,
                                msize_t msize,
                                void *aligned_address)
{
    void *ptr;
    //处理之前未运用的剩下空间
    if (tiny_mag_ptr->mag_bytes_free_at_end || tiny_mag_ptr->mag_bytes_free_at_start) {
        tiny_finalize_region(rack, tiny_mag_ptr);
    }
    tiny_region_t region = (tiny_region_t)aligned_address;
    // We set the unused bits of the header in the last pair to be all ones, and those of the inuse to zeroes.
#if NUM_TINY_BLOCKS & 31
    const uint32_t header = 0xFFFFFFFFU << (NUM_TINY_BLOCKS & 31);
#else
    const uint32_t header = 0;
#endif
    region->pairs[CEIL_NUM_TINY_BLOCKS_WORDS - 1].header = header;
    region->pairs[CEIL_NUM_TINY_BLOCKS_WORDS - 1].inuse = 0;
    //设置mag_index
    MAGAZINE_INDEX_FOR_TINY_REGION(region) = mag_index;
    // Insert the new region into the hash ring
    rack_region_insert(rack, region);
    tiny_mag_ptr->mag_last_region = region;
    BYTES_USED_FOR_TINY_REGION(region) = TINY_BYTES_FOR_MSIZE(msize);
    OBJECTS_IN_USE_FOR_TINY_REGION(region) = 1;
    int offset_msize = 0;
    //内存分配地址ptr
    ptr = (void *)(TINY_REGION_HEAP_BASE(region) + TINY_BYTES_FOR_MSIZE(offset_msize));
    set_tiny_meta_header_in_use(ptr, msize);
    tiny_mag_ptr->mag_num_objects++;
    tiny_mag_ptr->mag_num_bytes_in_objects += TINY_BYTES_FOR_MSIZE(msize);
    tiny_mag_ptr->num_bytes_in_magazine += TINY_HEAP_SIZE;
    set_tiny_meta_header_in_use_1((void *)((uintptr_t)ptr + TINY_BYTES_FOR_MSIZE(msize)));
    tiny_mag_ptr->mag_bytes_free_at_end = TINY_BYTES_FOR_MSIZE(NUM_TINY_BLOCKS - msize - offset_msize);
    tiny_mag_ptr->mag_bytes_free_at_start = 0;
    //将region参加tiny_mag_ptr的last node
    recirc_list_splice_last(rack, tiny_mag_ptr, REGION_TRAILER_FOR_TINY_REGION(region));
    return ptr;
}

全体流程如下：

1. 首要判别，假如magazine还有一些剩下size从未运用，则将这部分内存更新为闲暇块参加闲暇链表。详细逻辑如图：

   

   白色区域是从未分配过的区域，会将这部分区域更新成收回状况，并将入mag_free_list中，参加之前会判别一下是否能够和空间接连的前一个内存块兼并，假如兼并，则更新mag_free_list中内存。代码如下：

   if (tiny_mag_ptr->mag_bytes_free_at_end || tiny_mag_ptr->mag_bytes_free_at_start) {
       tiny_finalize_region(rack, tiny_mag_ptr);
   }
   void tiny_finalize_region(rack_t *rack, magazine_t *tiny_mag_ptr)
   {
       void *last_block, *previous_block;
       uint32_t *last_header;
       msize_t last_msize, previous_msize, last_index;
       //假如还有一些剩下size，测验兼并前一个内存块
       if (tiny_mag_ptr->mag_bytes_free_at_end) {
           last_block = (void *)((uintptr_t)TINY_REGION_HEAP_END(tiny_mag_ptr->mag_last_region) - tiny_mag_ptr->mag_bytes_free_at_end);
           last_msize = TINY_MSIZE_FOR_BYTES(tiny_mag_ptr->mag_bytes_free_at_end);
           last_header = TINY_BLOCK_HEADER_FOR_PTR(last_block);
           last_index = TINY_INDEX_FOR_PTR(last_block);
           if (last_index != (NUM_TINY_BLOCKS - 1)) {
               BITARRAY_CLR(last_header, (last_index + 1));
           }
           //前一个闲暇的block
           previous_block = tiny_previous_preceding_free(last_block, &previous_msize);
           if (previous_block) {
               set_tiny_meta_header_middle(last_block);
               tiny_free_list_remove_ptr(rack, tiny_mag_ptr, previous_block, previous_msize);
               zero_tiny_free_inline_meta_following(previous_block, previous_msize);
               last_block = previous_block;
               last_msize += previous_msize;
           }
           tiny_free_list_add_ptr(rack, tiny_mag_ptr, last_block, last_msize);
           tiny_mag_ptr->mag_bytes_free_at_end = 0;
       }
       tiny_mag_ptr->mag_last_region = NULL;
   }
   

2. 调用rack_region_insert办法将region注册进rack的hash ring结构中。
3. 从region取偏移meta字段后的首地址作为内存块地址ptr回来，而且调用set_tiny_meta_header_in_use更新block状况。这儿有一个特别逻辑，设置内存块ptr后一个16字节的内存块为use状况，防止收回兼并操作。一起更新相关计算信息，包括mag_num_objects等，更新mag_bytes_free_at_end、mag_bytes_free_at_start的值。

   

4. 调用recirc_list_splice_last办法将region对应的trailer_t节点参加region链表中。

内存收回

free_tiny是tiny内存收回的进口办法，代码如下：

void free_tiny(rack_t *rack, void *ptr, region_t tiny_region, size_t known_size,
        boolean_t partial_free)
{
    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]);
    uint32_t flags = 0;
//cache
#if CONFIG_TINY_CACHE
    if (msize < TINY_QUANTUM) {
            void *ptr2 = tiny_mag_ptr->mag_last_free;
            msize_t msize2 = tiny_mag_ptr->mag_last_free_msize;
            region_t rgn2 = tiny_mag_ptr->mag_last_free_rgn;
            if (ptr == ptr2) {
                free_tiny_botch(rack, ptr);
                return;
            }
            //...
            tiny_mag_ptr->mag_last_free = ptr;
            tiny_mag_ptr->mag_last_free_msize = msize;
            tiny_mag_ptr->mag_last_free_rgn = tiny_region;
            //...
            msize = msize2;
            ptr = ptr2;
            tiny_region = rgn2;
            flags |= TINY_FREE_FLAG_FROM_CACHE;
        }
#endif 
    //...
    if (tiny_free_no_lock(rack, tiny_mag_ptr, mag_index, tiny_region, ptr,
            msize, flags)) {
    }
}

首要包括两部分逻辑：

1. cache更新逻辑，更新tiny_mag_ptr->mag_last_free，更新mag_last_free_msize、mag_last_free_rgn，将原有的cache参加收回逻辑，关于cache的逻辑，上文有详细介绍。
2. 调用tiny_free_no_lock进行内存收回操作

中心逻辑

tiny_free_no_lock是收回的中心完成，代码如下：

boolean_t tiny_free_no_lock(rack_t *rack, magazine_t *tiny_mag_ptr, mag_index_t mag_index,
        region_t region, void *ptr, msize_t msize, uint32_t flags)
{
    void *original_ptr = ptr;
    size_t original_size = TINY_BYTES_FOR_MSIZE(msize);
    void *next_block = ((unsigned char *)ptr + original_size);
    msize_t previous_msize, next_msize;
    void *previous;
    tiny_free_list_t *big_free_block;
    tiny_free_list_t *after_next_block;
    tiny_free_list_t *before_next_block;
    //测验兼并前一个闲暇的block
    previous = tiny_previous_preceding_free(ptr, &previous_msize);
    if (previous) {
        set_tiny_meta_header_middle(ptr);
        tiny_free_list_remove_ptr(rack, tiny_mag_ptr, previous, previous_msize);
        zero_tiny_free_inline_meta_following(previous, previous_msize);
        ptr = previous;
        msize += previous_msize;
    }
    //测验兼并后一个闲暇的block
    if ((next_block < TINY_REGION_HEAP_END(region)) && tiny_meta_header_is_free(next_block)) {
        next_msize = get_tiny_free_size(next_block);
        if (next_msize > NUM_TINY_SLOTS) {
            msize += next_msize;
            big_free_block = (tiny_free_list_t *)next_block;
            after_next_block = free_list_unchecksum_ptr(rack, &big_free_block->next);
            before_next_block = free_list_unchecksum_ptr(rack, &big_free_block->previous);
            if (!before_next_block) {
                tiny_mag_ptr->mag_free_list[NUM_TINY_SLOTS].p = ptr;
            } else {
                before_next_block->next.u = free_list_checksum_ptr(rack, ptr);
            }
            if (after_next_block) {
                after_next_block->previous.u = free_list_checksum_ptr(rack, ptr);
            }
            ((tiny_free_list_t *)ptr)->previous = big_free_block->previous;
            ((tiny_free_list_t *)ptr)->next = big_free_block->next;
            set_tiny_meta_header_middle(big_free_block);
            zero_tiny_free_inline_meta(big_free_block, next_msize);
            set_tiny_meta_header_free(ptr, msize);
            uint16_t next_block_index = TINY_INDEX_FOR_PTR(big_free_block) + 1;
            uint16_t ptr_index = TINY_INDEX_FOR_PTR(ptr) + 1;
            const grain_t slot = NUM_TINY_SLOTS;
            region_free_blocks_t *free_blocks = &((tiny_region_t)region)->free_blocks_by_slot[slot];
            if (free_blocks->first_block == next_block_index) {
                free_blocks->first_block = ptr_index;
            }
            if (free_blocks->last_block == next_block_index) {
                free_blocks->last_block = ptr_index;
            }
            goto tiny_free_ending;
        }
        tiny_free_list_remove_ptr(rack, tiny_mag_ptr, next_block, next_msize);
        set_tiny_meta_header_middle(next_block); // clear the meta_header to enable coalescing backwards
        zero_tiny_free_inline_meta(next_block, next_msize);
        msize += next_msize;
    }
    //从头增加进free链表和freeblock区
    tiny_free_list_add_ptr(rack, tiny_mag_ptr, ptr, msize);
tiny_free_ending:
    tiny_mag_ptr->mag_num_bytes_in_objects -= original_size;
    region_trailer_t *trailer = REGION_TRAILER_FOR_TINY_REGION(region);
    size_t bytes_used = trailer->bytes_used - original_size;
    trailer->bytes_used = (unsigned int)bytes_used;
    //...
    boolean_t needs_unlock = TRUE;
#if CONFIG_RECIRC_DEPOT
    needs_unlock = tiny_free_try_recirc_to_depot(rack, tiny_mag_ptr, mag_index, region, original_ptr, original_size, ptr, msize);
#endif // CONFIG_RECIRC_DEPOT
    return needs_unlock;
}

详细过程如下：

1. 测验查找相邻的内存是否闲暇，假如闲暇，能够进行兼并操作，首要调用tiny_previous_preceding_free办法查找前一块闲暇内存previous，假如找到则兼并。如下图1，兼并的操作如下：
   1. 因为兼并后内存块ptr不存在了，因而更新ptr的pair状况符号为空，set_tiny_meta_header_middle。
   2. 调用tiny_free_list_remove_ptr办法将previous从原闲暇链表mag_free_list中删去。
   3. 更新后的闲暇块是兼并后的巨细，是msize+previous_msize。

      

2. 测验兼并后一块内存块next，基本流程和兼并previous类似，更新next的pair状况符号为空，将next从mag_free_list中删去，如上图2。这儿包括一个特别逻辑，当next的size超越limit，则兼并后的闲暇内存块必定会被参加最终一个链表mag_free_list[limit]中，这儿独自处理，将next从原来的链表中删去，然后将兼并后的ptr参加mag_free_list[limit]的next原方位中，更新next的pair状况符号为空，其他操作共同，如下图。

   

3. 调用tiny_free_list_add_ptr办法将兼并后的闲暇块参加mag_free_list。
4. 更新计算信息，例如mag_num_bytes_in_objects、bytes_used。
5. 调用tiny_free_try_recirc_to_depot，判别当时magzine的闲暇块份额是否到达阈值，假如到达，需求将相应的region和闲暇内存块搬迁至depot magazine的结构中。
6. 假如收回的是depot magazine中内存，则进一步判别内存块地点的region是否内存悉数被收回，如是则调用体系办法会说该region内存。逻辑如下：

   static boolean_t
   tiny_free_try_recirc_to_depot(rack_t *rack,
                             magazine_t *tiny_mag_ptr,
                             mag_index_t mag_index,
                             region_t region,
                             void *headptr,
                             size_t headsize,
                             void *ptr,
                             msize_t msize)
   {
       if (DEPOT_MAGAZINE_INDEX != mag_index) {
       //收回给depot region的逻辑
       } else {
           if (0 < bytes_used || 0 < node->pinned_to_depot) {
           } else {
               //region的bytes_used为0，收回内存给体系
               region_t r_dealloc = tiny_free_try_depot_unmap_no_lock(rack, tiny_mag_ptr, node);
               SZONE_MAGAZINE_PTR_UNLOCK(tiny_mag_ptr);
               if (r_dealloc) {
                   mvm_deallocate_pages(r_dealloc, TINY_REGION_SIZE,
                       MALLOC_FIX_GUARD_PAGE_FLAGS(rack->debug_flags));
               }
               return FALSE;
           }
       }
       return TRUE;
   }
   

   1. 调用了tiny_free_try_depot_unmap_no_lock将depot magzine下的region从结构中删去
   2. 调用mvm_deallocate_pages办法收回内存。

以上是tiny内存分配的介绍，因为字数约束，small和large在另外一篇文章中介绍。