本篇是ScalableZone系列的第二篇，介绍small和large的内存的机制，因为small和tiny在机制上高度类似，本篇侧重介绍差异的部分。

small

首要完成在magazine_small.c文件中。和tiny相同，small内存也对应一个rack_s结构体办理内部数据。

typedef struct szone_s {
    //...
    struct rack_s small_rack;
    //...
}

内部结构和tiny类型保持共同，rack_s内部保护若干magazines具体办理small内存，每个magazine办理regions和闲暇链表mag_free_list。small magazine的逻辑和tinymagazine保持共同。

相关概念

size分级

small类型将内存划分为512B一级，则15KB的规模一共划分为30级，用SMALL_QUANTUM宏表明。

#define SHIFT_SMALL_QUANTUM (SHIFT_TINY_QUANTUM + 5) // 9
#define SMALL_QUANTUM (1 << SHIFT_SMALL_QUANTUM) // 512 bytes

region

small magazine下分配的region和tiny region结构类似，small region也是由根本内存块block组成的空间，单个block的巨细对应size分级的根本单位512B，用small_block_t类型表明，small_block_t是uint32_t数组，容量是512B/4 = 128。NUM_SMALL_BLOCKS表明region内包含的block个数，一个region能够存储16319个block巨细的内存数据。

typedef uint32_t small_block_t[SMALL_QUANTUM / sizeof(uint32_t)];
#define NUM_SMALL_BLOCKS 16319

small_region的界说如下：

typedef struct small_region {
    region_trailer_t trailer;
    msize_t small_meta_words[NUM_SMALL_BLOCKS];
    oob_free_entry_s small_oob_free_entries[SMALL_OOB_COUNT];
    uint8_t pad[SMALL_REGION_PAD];
    region_cookie_t region_cookie;
    small_block_t blocks[NUM_SMALL_BLOCKS];
} * small_region_t;

和tiny region的结构类似，首要包含两块数据存储和meta信息，首要字段如下：

• trailer：region链表结构，辅佐magazine办理region，和tiny相同。

• blocks：是实践寄存数据的区域，容量是NUM_SMALL_BLOCKS的block数组，能够存储NUM_SMALL_BLOCKS个block巨细的数据。

• small_meta_words[]：存储block内存块状况的数组，和tiny不同的是，不经过bit位存储，每32bit对应一个数组元素，而是每个block都对应一个数组元素，因而数组共NUM_SMALL_BLOCKS个元素。如图所示，region中每个内存块的block都能够在small_meta_words数值找到对应的index方位。

  

region的总巨细包含以上3个区域：

#define SMALL_REGION_SIZE ((SMALL_HEAP_SIZE + SMALL_METADATA_SIZE + PAGE_MAX_SIZE - 1) & ~(PAGE_MAX_SIZE - 1))
#define SMALL_HEAP_SIZE (NUM_SMALL_BLOCKS * SMALL_QUANTUM)
#define SMALL_METADATA_SIZE (sizeof(region_trailer_t) + NUM_SMALL_BLOCKS * sizeof(msize_t))
#define PAGE_MAX_SHIFT          14
#define PAGE_MAX_SIZE           (1 << PAGE_MAX_SHIFT)

• SMALL_HEAP_SIZE：blocks数据区巨细。
• SMALL_METADATA_SIZE：region链表+small_meta_words数组巨细。 再依照PAGE_MAX_SIZE（16K）对齐。

一起供给了一些宏，获取相应区域起始地址：

• 依据ptr获取region的地址

  #define SMALL_REGION_FOR_PTR(ptr) ((small_region_t)((uintptr_t)(ptr) & ~((1 << SMALL_BLOCKS_ALIGN) - 1)))
  

• 获取region的header：即block状况数组small_meta_words的地址

  #define SMALL_META_HEADER_FOR_REGION(region) (((small_region_t)region)->small_meta_words)
  #define SMALL_META_HEADER_FOR_PTR(ptr) (((small_region_t)SMALL_REGION_FOR_PTR(ptr))->small_meta_words)
  

• 获取region的blocks区域：

  #define SMALL_REGION_HEAP_BASE(region) ((void *)((small_region_t)region)->blocks)
  

• 获取ptr地址在region中的偏移

  #define SMALL_HEAP_OFFSET_FOR_PTR(ptr) ((uintptr_t)(ptr) - (uintptr_t)SMALL_REGION_HEAP_BASE(SMALL_REGION_FOR_PTR(ptr)))
  

• 获取ptr对应的block在small_meta_words的index和地址

  #define SMALL_META_INDEX_FOR_PTR(ptr) ((SMALL_HEAP_OFFSET_FOR_PTR(ptr) >> SHIFT_SMALL_QUANTUM) & (NUM_SMALL_CEIL_BLOCKS - 1))
  #define SMALL_METADATA_FOR_PTR(ptr) (SMALL_META_HEADER_FOR_PTR(ptr) + SMALL_META_INDEX_FOR_PTR(ptr))
  

内存状况办理

首要，small magazine也运用mag_bitmap数组来记载magazine下各msize的闲暇内存情况。其次，和tiny的pair字段不同，region结构中经过small_meta_words数组记载region内部的内存块的状况和巨细，可是不分成header和inuse两个字段别离存储内存块的有无和运用状况。

small_meta_words是msize_t数组，msize_t界说如下：

typedef unsigned short msize_t;

unsigned short能够存储16bit的信息，msize_t的最高bit位(1<<15)存储是否闲暇，其他bit位存储msize数值。最高位为1表明闲暇，0表明未闲暇。接下来结合代码剖析。

未分配

初始情况下未分配任何内存块，small_meta_words默许是全0，用黄色表明。

分配运用

例如分配了一个msize=2的内存块，则small_meta_words[index]设置如下：

static MALLOC_INLINE void small_meta_header_set_in_use(msize_t *meta_headers, msize_t index, msize_t msize)
{
    meta_headers[index] = msize;
}

msize_t的最高位位0，表明运用中，其他bit位存储msize值。

未运用

当内存块被收回时，符号为闲暇状况，设置第一个block和终究一个block的最高位bit为1。

static MALLOC_INLINE void
small_meta_header_set_is_free(msize_t *meta_headers, msize_t index, msize_t msize)
{
    meta_headers[index] = msize | SMALL_IS_FREE;
}
static MALLOC_INLINE void
small_free_mark_free(rack_t *rack, free_list_t entry, msize_t msize)
{
    void *ptr = small_free_list_get_ptr(entry);
    msize_t *meta_headers = SMALL_META_HEADER_FOR_PTR(ptr);
    uintptr_t start_index = SMALL_META_INDEX_FOR_PTR(ptr);
    uintptr_t end_index = SMALL_META_INDEX_FOR_PTR(ptr + SMALL_BYTES_FOR_MSIZE(msize) - 1);
    small_meta_header_set_is_free(meta_headers, start_index, msize);
    small_meta_header_set_is_free(meta_headers, end_index, msize);
}

之所以设置也设置终究一个block的size和和free状况，是为了后续收回操作时，方便查找相邻的前一块内存地址。

例如，收回一个msize=3的内存块，如图，内存块包含3个block，第1个和第3个block对应的bit最高位设置为1。

static MALLOC_INLINE void
small_meta_header_set_not_free(msize_t *meta_headers, msize_t index)
{
    meta_headers[index] &= ~SMALL_IS_FREE;
}
static MALLOC_INLINE void
small_free_mark_unfree(rack_t *rack, free_list_t entry, msize_t msize)
{
    void *ptr = small_free_list_get_ptr(entry);
    msize_t *meta_headers = SMALL_META_HEADER_FOR_PTR(ptr);
    uintptr_t start_index = SMALL_META_INDEX_FOR_PTR(ptr);
    uintptr_t end_index = SMALL_META_INDEX_FOR_PTR(ptr + SMALL_BYTES_FOR_MSIZE(msize) - 1);
    small_meta_header_set_not_free(meta_headers, start_index);
    small_meta_header_set_not_free(meta_headers, end_index);
}

铲除

当一块内存块不存在时，对应的bit位需求被铲除，例如相邻闲暇内存块存在兼并的操作，将其间一个内存块铲除，别离设置第一个block和终究一个block的bit位为0。

static MALLOC_INLINE void
small_meta_header_set_middle(msize_t *meta_headers, msize_t index)
{
    meta_headers[index] = 0;
}
static MALLOC_INLINE void
small_free_mark_middle(rack_t *rack, free_list_t entry, msize_t msize)
{
    // Marks both the start and end block of a free-list entry as "middle" (unfree).
    void *ptr = small_free_list_get_ptr(entry);
    msize_t *meta_headers = SMALL_META_HEADER_FOR_PTR(ptr);
    uintptr_t start_index = SMALL_META_INDEX_FOR_PTR(ptr);
    uintptr_t end_index = SMALL_META_INDEX_FOR_PTR(ptr + SMALL_BYTES_FOR_MSIZE(msize) - 1);
    small_meta_header_set_middle(meta_headers, start_index);
    small_meta_header_set_middle(meta_headers, end_index);
}

例如收回一个msize=2的内存块ptr时，兼并相邻的前一块msize=2的闲暇内存previous，别离将previous和ptr的符号位铲除。

闲暇内存办理

和tiny相同，small经过magazine的mag_free_list字段保护闲暇链表，办理被收回的闲暇内存块。

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

链表办理

根底结构

smal运用通用的free_list_t结构，作为闲暇链表的节点数据，是一个union类型

typedef union {
    small_inplace_free_entry_t small_inplace;
    medium_inplace_free_entry_t medium_inplace;
    inplace_free_entry_t inplace;
    oob_free_entry_t oob;
    void *p;
} free_list_t;
typedef struct _small_inplace_free_entry_s {
    inplace_linkage_s previous;
    inplace_linkage_s next;
} small_inplace_free_entry_s, *small_inplace_free_entry_t;
typedef struct {
    void *ptr;
    uint8_t checksum;
} inplace_linkage_s;

运用同一块内存，在不同场景下用途不同，small涉及small_inplace、oob、p三个字段的运用，经过small_inplace和p设置和获取链表的前后联系：

//设置
static MALLOC_INLINE void small_inplace_checksum_ptr(rack_t *rack, inplace_linkage_s *linkage, void *ptr)
{
    uintptr_t checksum = free_list_gen_checksum((uintptr_t)ptr ^ rack->cookie ^ (uintptr_t)rack);
    linkage->checksum = checksum;
    linkage->ptr = ptr;
}
static MALLOC_INLINE void small_inplace_free_entry_set_previous(rack_t *rack, small_inplace_free_entry_t entry, free_list_t previous)
{
    small_inplace_checksum_ptr(rack, &entry->previous, previous.p);
}
static MALLOC_INLINE void small_inplace_free_entry_set_next(rack_t *rack, small_inplace_free_entry_t entry, free_list_t next)
{
    small_inplace_checksum_ptr(rack, &entry->next, next.p);
}
//获取
static MALLOC_INLINE free_list_t small_inplace_unchecksum_ptr(rack_t *rack, inplace_linkage_s *linkage)
{
    return (free_list_t){ .p = linkage->ptr };
}
static MALLOC_INLINE free_list_t small_inplace_free_entry_get_previous(rack_t *rack, small_inplace_free_entry_t ptr)
{
    return small_inplace_unchecksum_ptr(rack, &ptr->previous);
}
static MALLOC_INLINE free_list_t small_inplace_free_entry_get_next(rack_t *rack, small_inplace_free_entry_t ptr)
{
    return small_inplace_unchecksum_ptr(rack, &ptr->next);
}

前后内存块地址存入linkage类型previous和next的ptr字段中，读取时经过linkage类型的ptr字段构建一个free_list_t结构，并赋值字段p，然后回来。

封装层如下：

//设置previous相关
static MALLOC_INLINE void small_free_list_set_previous(rack_t *rack, free_list_t entry, free_list_t previous)
{
    if (small_is_oob_free_entry(entry)) {
        small_oob_free_entry_set_previous(entry.oob, previous);
    } else {
        small_inplace_free_entry_set_previous(rack, entry.small_inplace, previous);
    }
}
//获取previous相关
static MALLOC_INLINE free_list_t small_free_list_get_previous(rack_t *rack, free_list_t ptr)
{
    if (small_is_oob_free_entry(ptr)) {
        return small_oob_free_entry_get_previous(ptr.oob);
    } else {
        return small_inplace_free_entry_get_previous(rack, ptr.small_inplace);
    }
}
//设置next相关
static MALLOC_INLINE void small_free_list_set_next(rack_t *rack, free_list_t entry, free_list_t next)
{
    if (small_is_oob_free_entry(entry)) {
        small_oob_free_entry_set_next(entry.oob, next);
    } else {
        small_inplace_free_entry_set_next(rack, entry.small_inplace, next);
    }
}
//获取next相关
static MALLOC_INLINE free_list_t small_free_list_get_next(rack_t *rack, free_list_t ptr)
{
    if (small_is_oob_free_entry(ptr)) {
        return small_oob_free_entry_get_next(ptr.oob);
    } else {
        return small_inplace_free_entry_get_next(rack, ptr.small_inplace);
    }
}

这儿先判别地址ptr是否是一个oob闲暇块，假如是则走oob办法设置和获取前后联系，不然运用small_inplace字段。

oob

oob即out-of-band闲暇内存，当一个内存块的size超过内存页巨细（vm_kernel_page_size）时，收回时会将其地址参加region的一个专门字段中保护，即small_oob_free_entries数组中，确保内存页dirty。

typedef struct small_region {
    //...
    oob_free_entry_s small_oob_free_entries[SMALL_OOB_COUNT];
    //..
} * small_region_t;

和free_list_t结构类似，oob数组保护SMALL_OOB_COUNT个oob_free_entry_t结构，对应SMALL_OOB_COUNT个oob内存块，经过注释能够了解，oob_free_entry_s的运用场景。界说如下：

// Out-of-band free list entry. Out-of-band free list entries are used
// in specific cases where a free-list entry is the *only* data on a given page,
// and the presence of that entry causes the page to stay dirty.
typedef struct {
    uintptr_t prev;
    uintptr_t next;
    uint16_t ptr;
} MALLOC_PACKED oob_free_entry_s, *oob_free_entry_t;

包含了prev、next保护链表前后联系，ptr存储内存块地址。SMALL_OOB_SIZE是存储oob_free_entry的区域，是region的总巨细减去其他内存区巨细，SMALL_OOB_SIZE是对应的数量。

#define SMALL_OOB_COUNT ((SMALL_REGION_SIZE - SMALL_HEAP_SIZE - SMALL_METADATA_SIZE - sizeof(region_cookie_t)) / sizeof(oob_free_entry_s))
#define SMALL_OOB_SIZE (SMALL_OOB_COUNT * sizeof(oob_free_entry_s))

oob内存的相关操作如下：

1. 当一个内存块被收回时，首要判别是否满意oob内存的条件，即msize>= vm_kernel_page_size.

   static MALLOC_INLINE boolean_t
   small_needs_oob_free_entry(void *ptr, msize_t msize)
   {
       vm_size_t ss = vm_kernel_page_size;
       uintptr_t pptr = trunc_page_quanta((uintptr_t)ptr);
       return ((trunc_page_quanta((uintptr_t)ptr) == (uintptr_t)ptr) && (SMALL_BYTES_FOR_MSIZE(msize) >= vm_kernel_page_size));
   }
   

2. 假如满意，则遍历small_oob_free_entries数组，查找可用的oob_free_entry_s结构包装内存信息。

   static MALLOC_INLINE oob_free_entry_t
   small_oob_free_find_empty(void *ptr, msize_t msize)
   {
       small_region_t region = SMALL_REGION_FOR_PTR(ptr);
       for (int i=0; i < SMALL_OOB_COUNT; i++) {
           if (region->small_oob_free_entries[i].ptr == 0) {
               return &region->small_oob_free_entries[i];
           }
       }
       return NULL;
   }
   

   即ptr==0的可用oob_free_entry_s。并将内存块地址ptr存储进结构中。

   #define SMALL_IS_OOB (1 << 15)
   static MALLOC_INLINE void
   small_oob_free_entry_set_ptr(oob_free_entry_t oobe, void *ptr)
   {
       oobe->ptr = SMALL_IS_OOB | (SMALL_REGION_OFFSET_FOR_PTR(ptr) >> SHIFT_SMALL_QUANTUM);
   }
   

   存储的数据包含：ptr在region中的相对偏移地址和SMALL_IS_OOB标识符。也有相应的get办法将oob结构中的数据还原成原内存地址。

   static MALLOC_INLINE void *
   small_oob_free_entry_get_ptr(oob_free_entry_t oobe)
   {
       if (!(oobe->ptr & SMALL_IS_OOB)) {
           return NULL;
       }
       small_region_t region = SMALL_REGION_FOR_PTR(oobe);
       uint16_t block = oobe->ptr & ~SMALL_IS_OOB;
       return (void *)((uintptr_t)region + (block << SHIFT_SMALL_QUANTUM));
   }
   

3. 设置和获取oob结构之间的前后链表联系。

   static MALLOC_INLINE void small_oob_free_entry_set_previous(oob_free_entry_t oobe, free_list_t previous)
   {
       oobe->prev = (uintptr_t)previous.p;
   }
   static MALLOC_INLINE free_list_t small_oob_free_entry_get_previous(oob_free_entry_t oobe)
   {
       return (free_list_t){ .p = (void *)oobe->prev };
   }
   static MALLOC_INLINE void small_oob_free_entry_set_next(oob_free_entry_t oobe, free_list_t next)
   {
       oobe->next = (uintptr_t)next.p;
   }
   static MALLOC_INLINE free_list_t small_oob_free_entry_get_next(oob_free_entry_t oobe)
   {
       return (free_list_t){ .p = (void *)oobe->next };
   }
   

4. 查找内存地址对应的oob存储结构，相同遍历small_oob_free_entries数组，匹配ptr是否持平。

   static MALLOC_INLINE oob_free_entry_t
   small_oob_free_find_ptr(void *ptr, msize_t msize)
   {
       small_region_t region = SMALL_REGION_FOR_PTR(ptr);
       for (int i=0; i < SMALL_OOB_COUNT; i++) {
           oob_free_entry_t oob = &region->small_oob_free_entries[i];
           if (small_oob_free_entry_get_ptr(oob) == ptr &&
               oob->ptr & SMALL_IS_OOB) {
               return &region->small_oob_free_entries[i];
           }
       }
       return NULL;
   }
   

5. oob_free_entry_t结构终究存储在free_list_t结构中，作为链表的节点。

相关操作

综上，闲暇内存块地址记载在free_list_t结构中，

static MALLOC_INLINE void *small_free_list_get_ptr(free_list_t ptr)
{
    if (!ptr.p) {
        return NULL;
    } else if (small_is_oob_free_entry(ptr)) {
        return small_oob_free_entry_get_ptr(ptr.oob);
    } else {
        return (void *)ptr.p;
    }
}

增加进链表

当内存块被收回，增加进闲暇链表结构中，代码如下：

static free_list_t small_free_list_add_ptr(rack_t *rack, magazine_t *small_mag_ptr, void *ptr, msize_t msize)
{
    //1.核算mszie和slot
    grain_t slot = SMALL_FREE_SLOT_FOR_MSIZE(rack, msize);
    free_list_t free_head = small_mag_ptr->mag_free_list[slot];
    //2.构建free_list_t结构
    free_list_t free_ptr = small_free_list_from_ptr(rack, ptr, msize);
    //3.设置链表联系
    small_free_list_set_previous(rack, free_ptr, (free_list_t){ .p = NULL });
    small_free_list_set_next(rack, free_ptr, free_head);
    //4.符号状况位
    small_free_mark_free(rack, free_ptr, msize);
    //5.设置链表联系，magazeinz的bit位
    if (small_free_list_get_ptr(free_head)) {
        small_free_list_set_previous(rack, free_head, free_ptr);
    } else {
        BITMAPN_SET(small_mag_ptr->mag_bitmap, slot);
    }
    //6.更新闲暇链表
    small_mag_ptr->mag_free_list[slot] = free_ptr;
    return free_ptr;
}

进程如下：

1. 核算mszie和slot，定位对应的闲暇链表，并获取head节点
2. 依据内存块地址ptr构建free_list_t节点，内部完成：

static MALLOC_INLINE free_list_t
small_free_list_from_ptr(rack_t *rack, void *ptr, msize_t msize)
{
    free_list_t entry;
    entry.p = ptr;
    if (small_needs_oob_free_entry(ptr, msize)) {
        oob_free_entry_t oobe = small_oob_free_find_empty(ptr, msize);
        if (oobe) {
            small_oob_free_entry_set_ptr(oobe, ptr);
            entry.oob = oobe;
        }
    }
    return entry;
}

这儿判别是否满意oob情况，假如是，则构建oob结构包装ptr，保护在entry的oob字段下，不然默许运用p字段保护ptr。

3. 设置链表联系，将当时新的节点参加链表头。
4. small_free_mark_free符号为闲暇，更新region内的状况数据，假如是msize的第一个闲暇块，则记载magazine的mag_bitmap状况位。
5. 终究更新mag_free_list闲暇链表。

从链表删去

假如从闲暇链表中查找到可用的内存块，需求删去链表中相应的的节点信息。

static void small_free_list_remove_ptr(rack_t *rack, magazine_t *small_mag_ptr, free_list_t entry, msize_t msize)
{
    small_free_mark_middle(rack, entry, msize);
    small_free_list_remove_ptr_no_clear(rack, small_mag_ptr, entry, msize);
}

entry是节点，首要更新状况位为从头运用。其次small_free_list_remove_ptr_no_clear办法更新链表。

static void small_free_list_remove_ptr_no_clear(rack_t *rack, magazine_t *small_mag_ptr, free_list_t entry, msize_t msize)
{
    grain_t slot = SMALL_FREE_SLOT_FOR_MSIZE(rack, msize);
    free_list_t next, previous;
    previous = small_free_list_get_previous(rack, entry);
    next = small_free_list_get_next(rack, entry);
    if (!small_free_list_get_ptr(previous)) {
        small_mag_ptr->mag_free_list[slot] = next;
        if (!small_free_list_get_ptr(next)) {
            BITMAPN_CLR(small_mag_ptr->mag_bitmap, slot);
        }
    } else {
        //...
        small_free_list_set_next(rack, previous, next);
    }
    if (small_free_list_get_ptr(next)) {
        free_list_t next_prev = small_free_list_get_previous(rack, next);
        //...
        small_free_list_set_previous(rack, next, previous);
    }
    if (small_is_oob_free_entry(entry)) {
        small_oob_free_entry_set_free(entry.oob);
    }
}

首要逻辑是经过更新previous、next指针，将entry节点从链表中删去。假如是oob内存，则将oob数组中的信息清空。

其他

magazine、region办理、cache、depot region等概念，small和tiny的逻辑相同。底层办理虚拟内存的接口也是共同，这儿不展开介绍，接下来剖析一下中心流程，即内存的分配和收回，因为机制上和tiny也是高度类似，这儿简要剖析一下。

中心流程

内存分配

void *small_malloc_should_clear(rack_t *rack, msize_t msize, boolean_t cleared_requested)
{
    int64_t heapSize = (NUM_SMALL_BLOCKS * SMALL_QUANTUM);
    size_t regionTrailerSize = sizeof(region_trailer_t);
    size_t mSize = sizeof(msize_t);
    int64_t metaSize = (regionTrailerSize + NUM_SMALL_BLOCKS * mSize);
    int64_t pageMaxSize = PAGE_MAX_SIZE;
    int64_t regionSize = ((heapSize + metaSize + PAGE_MAX_SIZE - 1) & ~(PAGE_MAX_SIZE - 1));
    void *ptr;
    mag_index_t mag_index = small_mag_get_thread_index() % rack->num_magazines;
    magazine_t *small_mag_ptr = &(rack->magazines[mag_index]);
#if CONFIG_SMALL_CACHE
    //...
#endif    
    while (1) {
        ptr = small_malloc_from_free_list(rack, small_mag_ptr, mag_index, msize);
        if (ptr) {
            return ptr;
        }
        if (small_get_region_from_depot(rack, small_mag_ptr, mag_index, msize)) {
            ptr = small_malloc_from_free_list(rack, small_mag_ptr, mag_index, msize);
            if (ptr) {
                return ptr;
            }
        }
        if (!small_mag_ptr->alloc_underway) {
            void *fresh_region;
            small_mag_ptr->alloc_underway = TRUE;
            fresh_region = mvm_allocate_pages(SMALL_REGION_SIZE,
                    SMALL_BLOCKS_ALIGN,
                    MALLOC_FIX_GUARD_PAGE_FLAGS(rack->debug_flags),
                    VM_MEMORY_MALLOC_SMALL);
            ptr = small_malloc_from_region_no_lock(rack, small_mag_ptr, mag_index, msize, fresh_region);
            small_mag_ptr->alloc_underway = FALSE;
            return ptr;
        }
    }
    //...
}

逻辑和tiny代码高度类似，进程如下：

1. 选取magazine，测验获取cache。
2. 假如未射中cache，调用small_malloc_from_free_list从闲暇链表中查找适宜的闲暇内存块。
3. 假如没有找到，则调用small_get_region_from_depot将depot magazine的region搬迁至当时magazine中，然后再次查找。
4. 假如仍未找到，则调用mvm_allocate_pages分配一块新内存fresh_region，并从头region中分配一块内存。

其间，CONFIG_SMALL_CACHE、small_malloc_from_free_list、small_get_region_from_depot、small_malloc_from_region_no_lock逻辑和CONFIG_TINY_CACHE、tiny_malloc_from_free_list、tiny_get_region_from_depot、tiny_malloc_from_region_no_lock相同，可参考上文。

内存收回

void free_small(rack_t *rack, void *ptr, region_t small_region, size_t known_size)
{
    msize_t msize;
    mag_index_t mag_index = MAGAZINE_INDEX_FOR_SMALL_REGION(SMALL_REGION_FOR_PTR(ptr));
    magazine_t *small_mag_ptr = &(rack->magazines[mag_index]);
    if (known_size) {
        msize = SMALL_MSIZE_FOR_BYTES(known_size + SMALL_QUANTUM - 1);
    } else {
        msize = SMALL_PTR_SIZE(ptr);
        if (SMALL_PTR_IS_FREE(ptr)) {
            free_small_botch(rack, ptr);
            return;
        }
    }
#if CONFIG_SMALL_CACHE
    //...
#endif
    region_trailer_t *trailer = REGION_TRAILER_FOR_SMALL_REGION(small_region);
    mag_index_t refreshed_index;
    mag_index = refreshed_index;
    small_mag_ptr = &(rack->magazines[mag_index]);
    if (small_free_no_lock(rack, small_mag_ptr, mag_index, small_region, ptr, msize)) {
    }
}

收回的进程也和tiny类似，首要选取magazine，更新cache信息，然后调用small_free_no_lock办法收回。

static MALLOC_INLINE boolean_t
small_free_no_lock(rack_t *rack, magazine_t *small_mag_ptr, mag_index_t mag_index, region_t region, void *ptr, msize_t msize)
{
    msize_t *meta_headers = SMALL_META_HEADER_FOR_PTR(ptr);
    unsigned index = SMALL_META_INDEX_FOR_PTR(ptr);
    size_t original_size = SMALL_BYTES_FOR_MSIZE(msize);
    void *next_block = ptr + original_size;
    msize_t next_index = index + msize;
    if (index > 0 && (meta_headers[index - 1] & SMALL_IS_FREE)) {
        msize_t previous_msize = meta_headers[index - 1] & ~SMALL_IS_FREE;
        grain_t previous_index = index - previous_msize;
        if (meta_headers[previous_index] == (previous_msize | SMALL_IS_FREE)) {
            void *previous_ptr = (void *)((uintptr_t)ptr - SMALL_BYTES_FOR_MSIZE(previous_msize));
            free_list_t previous = small_free_list_find_by_ptr(rack, small_mag_ptr, previous_ptr, previous_msize);
            small_free_list_remove_ptr(rack, small_mag_ptr, previous, previous_msize);
            ptr = previous_ptr;
            small_meta_header_set_middle(meta_headers, index); // This block is now a middle block.
            msize += previous_msize;
            index -= previous_msize;
        } else {
            __builtin_trap();
        }
    }
    if ((next_block < SMALL_REGION_HEAP_END(region)) && (meta_headers[next_index] & SMALL_IS_FREE)) {
        msize_t next_msize = meta_headers[next_index] & ~SMALL_IS_FREE;
        free_list_t next = small_free_list_find_by_ptr(rack, small_mag_ptr, next_block, next_msize);
        small_free_list_remove_ptr(rack, small_mag_ptr, next, next_msize);
        msize += next_msize;
    }
    free_list_t freee = small_free_list_add_ptr(rack, small_mag_ptr, ptr, msize);
    small_mag_ptr->mag_num_bytes_in_objects -= original_size;
    region_trailer_t *trailer = REGION_TRAILER_FOR_SMALL_REGION(region);
    size_t bytes_used = trailer->bytes_used - original_size;
    trailer->bytes_used = (unsigned int)bytes_used;
    needs_unlock = small_free_try_recirc_to_depot(rack, small_mag_ptr, mag_index, region, freee, msize, original_ptr, original_size);
    return needs_unlock;
}

进程包含：

1. 获取内存地址相邻的闲暇内存块，测验兼并。兼并操作更新链表和状况信息。即删去旧的节点，增加兼并后新的节点进链表。
2. 更新统计信息mag_num_bytes_in_objects、bytes_used。
3. 判别是否搬迁至small_free_try_recirc_to_depot，和tiny_free_try_recirc_to_depot的逻辑类似，能够参考tiny相关介绍。

以上是small代码的剖析。

large

首要完成在magazine_large.c文件中，large内存办理分为分配与收回两大块，本文在结合代码剖析的进程中，介绍相关的概念和完成机制。

相关概念

不同于tiny、small的内存分配办法，运用large办法分配，具备以下特点：

1. 因为分配的较大块的内存，超过15KB以上，因而每次分配时，依据实践需求的size分配，而不运用size分级策略，使实践分配的size固定为几档。
2. 每次分配和收回时，直接运用底层接口mvm_allocate_pages和mvm_deallocate_pages办法分配收回虚拟内存，没有region和freelist机制一次性分配较大内存，并在内部复用。

因而，large的内存办理较tiny、small较为简单，运用相关数据结构办理分配的内存块。

large_entry办理

large_entry_t是办理内存块的根底数据结构，当分配一个large内存块时，都会创立一个large_entry_t数据，增加进大局结构中办理，经过保护large_entry_t，办理分配的内存块。数据结构如下：

typedef struct large_entry_s {
    vm_address_t address;
    vm_size_t size;
    boolean_t did_madvise_reusable;
} large_entry_t;

address存储内存块地址，size存储内存块巨细，did_madvise_reusable表明是否可执行madvise重用逻辑。如图所示：

typedef struct szone_s {
    //...
    _malloc_lock_s large_szone_lock MALLOC_CACHE_ALIGN;
    unsigned num_large_objects_in_use;
    unsigned num_large_entries;
    large_entry_t *large_entries;
    size_t num_bytes_in_large_objects;
    //...
} szone_t;

字段如下：

• num_large_objects_in_use：分配在运用的内存块个数
• num_large_entries：能够容纳的entry个数
• large_entries：实践存储entry的hash数组
• num_bytes_in_large_objects：分配内存块的总巨细

增加entry

存储entry的large_entries是一个hash数组，存储entry的机制和一般的hash数组类似。增加entry的代码如下：

static void large_entry_insert_no_lock(szone_t *szone, large_entry_t range)
{
    unsigned num_large_entries = szone->num_large_entries;
    unsigned hash_index = (((uintptr_t)(range.address)) >> vm_page_quanta_shift) % num_large_entries;
    unsigned index = hash_index;
    large_entry_t *entry;
    do {
        entry = szone->large_entries + index;
        if (0 == entry->address) {
            *entry = range;
            return;
        }
        index++;
        if (index == num_large_entries) {
            index = 0;
        }
    } while (index != hash_index);
}

如下图，参加entry进large_entries的进程如下：

1. 依据entry的存储的内存块地址address，核算出hash_index，该index决议entry刺进hash数组中的方位。
2. 依据数组的首地址和index核算出偏移方位，将entry刺进该方位，假如该方位现已存储其他entry的数据，则index++，直到找到没有entry或者空entry的方位。空entry是指之前增加过entry，可是entry的数据现已清0。
3. 全体偏移判别的进程是类似遍历环状结构，假如index偏移到数组的结尾方位num_large_entries，则回到0方位持续，直到index再次和hash_index持平停止，即回到开端偏移的方位。

刺进进程如图所示：

为确保hash数组中的方位足够存储entry，当large_entries存储空间达到某阈值时，需求扩容，相关代码如下：

bool should_grow = (szone->num_large_objects_in_use + 1) * 4 > szone->num_large_entries;
if (should_grow) {
    large_entry_t *entries = large_entries_grow_no_lock(szone, range_to_deallocate);
}

判别条件是当时运用的内存块个数+1后*4大于hash数组目前的容量num_large_entries时扩容，执行扩容逻辑函数large_entries_grow_no_lock。

static large_entry_t *large_entries_grow_no_lock(szone_t *szone, vm_range_t *range_to_deallocate)
{
    unsigned old_num_entries = szone->num_large_entries;
    large_entry_t *old_entries = szone->large_entries;
    unsigned new_num_entries =
    (old_num_entries) ? old_num_entries * 2 + 1 : (unsigned)((large_vm_page_quanta_size / sizeof(large_entry_t)) - 1);
    large_entry_t *new_entries = large_entries_alloc_no_lock(szone, new_num_entries);
    unsigned index = old_num_entries;
    large_entry_t oldRange;
    if (new_entries == NULL) {
        return NULL;
    }
    szone->num_large_entries = new_num_entries;
    szone->large_entries = new_entries;
    while (index--) {
        oldRange = old_entries[index];
        if (oldRange.address) {
            large_entry_insert_no_lock(szone, oldRange);
        }
    }
    if (old_entries) {
        large_entries_free_no_lock(szone, old_entries, old_num_entries, range_to_deallocate);
    } else {
        range_to_deallocate->address = (vm_address_t)0;
        range_to_deallocate->size = 0;
    }
    return new_entries;
}

全体进程如下：

1. 核算要扩容的巨细，假如之前没有过当时large_entries为NULL，则分配一个虚拟内存页的巨细，不然在原根底上扩容1倍后加1，因而，这儿的扩容的机制是2倍扩容。

2. 依据扩容巨细，调用large_entries_alloc_no_lock办法分配新内存，回来新数组的地址。

   static large_entry_t *large_entries_alloc_no_lock(szone_t *szone, unsigned num)
   {
       size_t size = num * sizeof(large_entry_t);
       unsigned flags = MALLOC_APPLY_LARGE_ASLR(szone->debug_flags & (DISABLE_ASLR | DISABLE_LARGE_ASLR));
       return mvm_allocate_pages(round_large_page_quanta(size), 0, flags, VM_MEMORY_MALLOC_LARGE);
   }
   

   这儿调用mvm_allocate_pages进行分配一块虚拟内存。

3. 更新szone的large_entries和num_large_entries字段，并将原数组中的entry内容拷贝至新的数组中。搬迁进程如图，遍历原数组内存逐个增加进新数组，在新数组中方位保持和原方位不变。

   

4. 调用large_entries_free_no_lock办法收回逻辑。

   void large_entries_free_no_lock(szone_t *szone, large_entry_t *entries, unsigned num, vm_range_t *range_to_deallocate)
   {
       size_t size = num * sizeof(large_entry_t);
       range_to_deallocate->address = (vm_address_t)entries;
       range_to_deallocate->size = round_large_page_quanta(size);
   }
   

   该办法不真实收回内存，而是赋值给range_to_deallocate暂存，是range_to_deallocate传入扩容办法的参数，用于存储要释放的原内存，在执行完扩容后释放。

5. 回来新数组地址。

归纳来看，增加entry的逻辑如下：

```
void *large_malloc(szone_t *szone, size_t num_kernel_pages, unsigned char alignment, boolean_t cleared_requested)
{
    //...
    addr = mvm_allocate_pages(size, alignment, MALLOC_APPLY_LARGE_ASLR(szone->debug_flags), VM_MEMORY_MALLOC_LARGE);
    if (addr == NULL) {
        return NULL;
    }
    SZONE_LOCK(szone);
    bool success = large_entry_grow_and_insert_no_lock(szone, (vm_address_t) addr, (vm_size_t) size,
        &range_to_deallocate);
    SZONE_UNLOCK(szone);
    if (!success) {
        return NULL;
    }
    if (range_to_deallocate.size) {
        // we deallocate outside the lock
        mvm_deallocate_pages((void *)range_to_deallocate.address, range_to_deallocate.size, 0);
    }
    return addr;
}
```

1. 调用mvm_allocate_pages办法分配large内存块。

2. 调用large_entry_grow_and_insert_no_lock办法创立entry，并增加进entries数组中。

   static bool large_entry_grow_and_insert_no_lock(szone_t *szone, vm_address_t addr, vm_size_t size,
       vm_range_t *range_to_deallocate)
   {
       bool should_grow = (szone->num_large_objects_in_use + 1) * 4 > szone->num_large_entries;
       if (should_grow) {
           large_entry_t *entries = large_entries_grow_no_lock(szone, range_to_deallocate);
           if (entries == NULL) {
               return false;
           }
       }
       large_entry_t large_entry;
       large_entry.address = addr;
       large_entry.size = size;
       large_entry_insert_no_lock(szone, large_entry);
       szone->num_large_objects_in_use++;
       szone->num_bytes_in_large_objects += size;
       return true;
   }
   

   内部先执行扩容逻辑，生成新的entry，记载内存块的地址和size，参加entry数组中，并更新szone的其他字段，包含num_large_objects_in_use和num_bytes_in_large_objects。

3. 假如其间产生扩容逻辑，则range_to_deallocate存储原数组内存，调用mvm_deallocate_pages办法收回旧数组内存。

查询entry

因为entry存储某个large内存的地址和size，能够经过地址找到对应的entry。

large_entry_t *
large_entry_for_pointer_no_lock(szone_t *szone, const void *ptr)
{
    unsigned num_large_entries = szone->num_large_entries;
    unsigned hash_index;
    unsigned index;
    large_entry_t *range;
    if (!num_large_entries) {
        return NULL;
    }
    hash_index = ((uintptr_t)ptr >> vm_page_quanta_shift) % num_large_entries;
    index = hash_index;
    do {
        range = szone->large_entries + index;
        if (range->address == (vm_address_t)ptr) {
            return range;
        }
        if (0 == range->address) {
            break;
        }
        index++;
        if (index == num_large_entries) {
            index = 0;
        }
    } while (index != hash_index);
    return NULL;
}

具体逻辑和刺进entry共同：

1. 依据地址ptr，依据相同紫规则核算出hash_index。
2. szone->large_entries + index作为查询entry的初始进口方位，匹配ptr和当时方位上存储的entry的address，匹配不上则index++，假如匹配成功，则完毕遍历。
3. 当index再次等于hash_index，则遍历完毕，假如未找到，则查找失败，回来NULL。

铲除entry

如上文所述，entry被创立出来参加数组后，数组中存储的是entry结构体的数据，而不是地址，当对应的large内存被收回时，entry数据被清空即可。

static vm_range_t large_entry_free_no_lock(szone_t *szone, large_entry_t *entry)
{
    vm_range_t range;
    range.address = entry->address;
    range.size = entry->size;
    entry->address = 0;
    entry->size = 0;
    //rehash
    large_entries_rehash_after_entry_no_lock(szone, entry);
    return range;
}

1. 首要将entry存储的内存块address、size数据存储到range中。

2. 清空entry数据

3. 因为清空了其间一个entry数据，为确保hash机制，需求对一切entry的方位从头调整，确保每个entry依据之前的规则刺进到正确的方位，例如下图，原先刺进entry时，核算出hash_index方位现已有entry1数据了，index++，得到hash_index+2的方位写入entry数据，当entry2被铲除时，依照规则，entry需求被从头搬迁至hash_index+1的方位上。

   

   调用large_entries_rehash_after_entry_no_lock进行从头hash刺进的操作

   static void
   large_entries_rehash_after_entry_no_lock(szone_t *szone, large_entry_t *entry)
   {
       unsigned num_large_entries = szone->num_large_entries;
       uintptr_t hash_index = entry - szone->large_entries;
       uintptr_t index = hash_index;
       large_entry_t range;
       do {
           index++;
           if (index == num_large_entries) {
               index = 0;
           }
           range = szone->large_entries[index];
           if (0 == range.address) {
               return;
           }
           szone->large_entries[index].address = (vm_address_t)0;
           szone->large_entries[index].size = 0;
           large_entry_insert_no_lock(szone, range);
       } while (index != hash_index);
   }
   

   逻辑是遍历large_entries数组中每个方位，首要将存储的entry数据清空，再将entry数据从头刺进数组中。

4. 回来range给后续收回操作。

缓存机制

为了提高内存分配的性能，large内存也支撑cache机制，保护了一个大局结构缓存entry数据，收回内存块时，没有调用mvm_deallocate_pages办法收回给体系，而是将对应的entry参加缓存中，下次分配内存时先从缓存中查找匹配适宜size的entry，假如存在，则回来entry对应的内存块，不需求调用mvm_allocate_pages分配一块新内存。

缓存机制相关的字段也保护在了szone中。

typedef struct szone_s {
//...
#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];
    int large_cache_depth;
    size_t large_cache_entry_limit;
    //...
    size_t large_entry_cache_bytes;
#endif
//...
} szone_t;

字段含义如下：

• large_entry_cache：缓存entry数据的中心数据结构，是一个长度是LARGE_ENTRY_CACHE_SIZE_HIGH的数组，在szone_s内存创立时分配。LARGE_ENTRY_CACHE_SIZE_HIGH是界说数组容量的宏，64位下值是64。

#if MALLOC_TARGET_64BIT
#define LARGE_ENTRY_CACHE_SIZE_HIGH 64
#define LARGE_ENTRY_SIZE_ENTRY_LIMIT_HIGH (512 * 1024 * 1024)
#define LARGE_ENTRY_CACHE_SIZE_LOW 16
#define LARGE_ENTRY_SIZE_ENTRY_LIMIT_LOW (128 * 1024 * 1024)
#else
#define LARGE_ENTRY_CACHE_SIZE_HIGH 8
#define LARGE_ENTRY_SIZE_ENTRY_LIMIT_HIGH (32 * 1024 * 1024)
#define LARGE_ENTRY_CACHE_SIZE_LOW LARGE_ENTRY_CACHE_SIZE_HIGH
#define LARGE_ENTRY_SIZE_ENTRY_LIMIT_LOW LARGE_ENTRY_SIZE_ENTRY_LIMIT_HIGH
#endif

• large_cache_depth：答应缓存entry的最大个数。
• large_cache_entry_limit：缓存的内存块总巨细限制，即缓存的entry对应的内存块的总巨细有必要小于limit值。
• large_entry_cache_bytes：当时缓存的entry对应的内存块的总size。
• large_entry_cache_oldest：依照参加entry缓存的时刻先后顺序，最早参加缓存的entry，其在缓存数组中的index方位。
• large_entry_cache_newest：最新参加缓存的entry，其在缓存数组中的index方位。

初始化

在创立szone时，分配并初始化了相关字段。

#define LARGE_CACHE_EXPANDED_THRESHOLD (32ull * 1024 * 1024 * 1024)
uint64_t magazine_large_expanded_cache_threshold = LARGE_CACHE_EXPANDED_THRESHOLD;
szone_t *create_scalable_szone(size_t initial_size, unsigned debug_flags)
{
    //...
    uint64_t memsize = platform_hw_memsize();
    if (memsize >= magazine_large_expanded_cache_threshold) {
        szone->large_cache_depth = LARGE_ENTRY_CACHE_SIZE_HIGH;
        szone->large_cache_entry_limit = LARGE_ENTRY_SIZE_ENTRY_LIMIT_HIGH;
    } else {
        szone->large_cache_depth = LARGE_ENTRY_CACHE_SIZE_LOW;
        szone->large_cache_entry_limit = LARGE_ENTRY_SIZE_ENTRY_LIMIT_LOW;
    }
}

首要调用platform_hw_memsize函数获取设备总内存，假如超过32G，则设置较高标准的参数，不然运用较低标准，以64位设备为例，假如内存大于32G，则large_cache_depth和large_cache_entry_limit别离是64和512M，不然是16和128M。

增加

内存块被收回时，会将对应的entry增加进缓存数组中，结合代码介绍：

bool free_large(szone_t *szone, void *ptr, bool try)
{
    //...
    entry = large_entry_for_pointer_no_lock(szone, ptr);
    if (entry) {
        if (large_cache_enabled && entry->size <= szone->large_cache_entry_limit) {
            int idx = szone->large_entry_cache_newest, stop_idx = szone->large_entry_cache_oldest;
            large_entry_t this_entry = *entry;
            boolean_t reusable = TRUE;
            //检测重复收回情况
            while (1) { 
                vm_size_t curr_size = szone->large_entry_cache[idx].size;
                vm_address_t addr = szone->large_entry_cache[idx].address;
                if (addr == entry->address) {
                    malloc_zone_error(szone->debug_flags, true, "pointer %p being freed already on death-rown", ptr);
                    return true;
                }
                if (idx == stop_idx) { // exhausted live ring?
                    break;
                }
                if (idx) {
                    idx--; // bump idx down
                } else {
                    idx = szone->large_cache_depth - 1; // wrap idx
                }
            }
            vm_range_to_deallocate = large_entry_free_no_lock(szone, entry);
            entry = NULL;
            //...
            szone->num_large_objects_in_use--;
            szone->num_bytes_in_large_objects -= this_entry.size;
            if (reusable) {
                int idx = szone->large_entry_cache_newest; // Most recently occupied
                vm_address_t addr;
                size_t adjsize;
                //case1
                if (szone->large_entry_cache_newest == szone->large_entry_cache_oldest &&
                    0 == szone->large_entry_cache[idx].address) {
                        addr = 0;
                        adjsize = 0;
                } else {
                    //case2
                    if (idx == szone->large_cache_depth - 1) {
                        idx = 0;
                    } else {
                        idx++;
                    }
                    //case3
                    if (idx == szone->large_entry_cache_oldest) {
                        addr = szone->large_entry_cache[idx].address;
                        adjsize = szone->large_entry_cache[idx].size;
                        szone->large_entry_cache_bytes -= adjsize;
                    } else {
                        addr = 0;
                        adjsize = 0;
                    }
                }
                szone->large_entry_cache_bytes += this_entry.size;
                szone->large_entry_cache[idx] = this_entry;
                szone->large_entry_cache_newest = idx;
                if (0 == addr) {
                    return true;
                }
                if (szone->large_entry_cache_oldest == szone->large_cache_depth - 1) {
                    szone->large_entry_cache_oldest = 0;
                } else {
                    szone->large_entry_cache_oldest++;
                }
                mvm_deallocate_pages((void *)addr, (size_t)adjsize, 0);
            }
        }
    }
}

1. 查找缓存数组large_entry_cache中的方位，从large_entry_cache_newest开端，large_entry_cache_oldest完毕。

2. 重复收回判别逻辑，遍历large_entry_cache中现已存储的一切entry，匹配要收回的entry，假如两者的address和size数据相同，阐明该内存现已被收回参加缓存中了，属于重复收回，直接报错。

3. 开端查找存储方位，当时方位用idx表明，分为以下几种情况：

   1. 初始情况下，large_entry_cache数组为空，large_entry_cache_newest和large_entry_cache_oldest均为0，直接将entry存入large_entry_cache[idx]，如图，entry0是首个参加缓存的entry，large_entry_cache_newest和large_entry_cache_oledest均指向entry0。

      

   2. 假如large_entry_cache_newest不等于large_entry_cache_oldest，且idx未达到large_entry_cache_oldest，则缓存数组未满，large_entry_cache_newest更新加1，将entry参加large_entry_cache_newest方位上，large_entry_cache_oldest保持不变，如图，entry3是新参加缓存数组的entry，large_entry_cache_newest指向entry3。

      

   3. 假如idx达到large_entry_cache_oldest，阐明缓存数组已存满，需求将large_entry_cache_oldest上存储的原entry数据更新，并将对应的原内存收回，并更新large_entry_cache_oldest值，如图所示，large_entry_cache_newest指向的entry9是新参加的entry，替换entry0的数据，一起entry0对应的内存被收回，一起large_entry_cache_oldest指向entry1。

      

4. 更新entry后，更新large_entry_cache_bytes的值，large_entry_cache_bytes是缓存的内存总size，加上新增加的entry的内存size，减去被替换entry的内存size。

查找

当分配内存时，依据要分配的size从缓存结构中查找一块size匹配的entry，回来对应的内存块。具体完成代码如下：

static large_entry_t large_malloc_best_fit_in_cache(szone_t *szone, size_t size, unsigned char alignment)
{
    int best = -1, idx = szone->large_entry_cache_newest, stop_idx = szone->large_entry_cache_oldest;
    size_t best_size = SIZE_T_MAX;
    large_entry_t entry;
    memset(&entry, 0, sizeof(entry));
    while (1) {
        size_t this_size = szone->large_entry_cache[idx].size;
        vm_address_t addr = szone->large_entry_cache[idx].address;
        if (0 == alignment || 0 == (((uintptr_t)addr) & (((uintptr_t)1 << alignment) - 1))) {
            if (size == this_size || (size < this_size && this_size < best_size)) {
                best = idx;
                best_size = this_size;
                if (size == this_size) {
                    break;
                }
            }
        }
        if (idx == stop_idx) { // exhausted live ring?
            break;
        }
        if (idx) {
            idx--; // bump idx down
        } else {
            idx = szone->large_cache_depth - 1; // wrap idx
        }
    }
    if (best == -1 || (best_size - size) >= size) { // limit fragmentation to 50%
        return entry;
    }
    entry = szone->large_entry_cache[best];
    remove_from_death_row_no_lock(szone, best);
    return entry;
}

1. 开端遍历，起始方位是large_entry_cache_newest，是最新缓存的方位，完毕方位是large_entry_cache_oldest，是最旧缓存的方位，因为增加缓存时idx不断加1，因而跟着数组方位不断加1，缓存从旧到新。因而，查询缓存时，从最新的缓存开端匹配，idx不断减1进行遍历，idx=0时，重置回large_cache_depth-1.

   

2. 匹配逻辑是，假如当时缓存entry的size等于要分配的size，则直接匹配成功，记载方位，停止遍历。假如缓存entry的size大于要分配的size，则暂时记载方位，持续遍历匹配，检查是否有entry的size大于且更靠近要分配的size。best存储方位。假如entry的size小于要分配的size，则越过。
3. 当idx等于stop_idx，即large_entry_cache_oldest，阐明现已遍历到最早的缓存了，完毕遍历。
4. 假如best等于-1，则查找失败，回来空entry，不然返best方位上的entry。
5. 调用remove_from_death_row_no_lock办法调整缓存结构，因为匹配成功后，需求将entry从缓存数组中移除。

调整

static int remove_from_death_row_no_lock(szone_t *szone, int idx)
{
    int i, next_idx = -1;
    if (szone->large_entry_cache_oldest < szone->large_entry_cache_newest) {
        for (i = idx; i < szone->large_entry_cache_newest; ++i) {
            szone->large_entry_cache[i] = szone->large_entry_cache[i + 1];
        }
        if (idx == szone->large_entry_cache_oldest) {
            next_idx = -1;
        } else {
            next_idx = idx - 1;
        }
        szone->large_entry_cache_newest--; 
    } else if (szone->large_entry_cache_newest < szone->large_entry_cache_oldest) {
        if (idx <= szone->large_entry_cache_newest) {
            // Fill from right.
            for (i = idx; i < szone->large_entry_cache_newest; ++i) {
                szone->large_entry_cache[i] = szone->large_entry_cache[i + 1];
            }
            if (0 < szone->large_entry_cache_newest) {
                szone->large_entry_cache_newest--;
            } else {
                szone->large_entry_cache_newest = szone->large_cache_depth - 1;
            }
            if (idx == 0) {
                next_idx = szone->large_cache_depth - 1;
            } else {
                next_idx = idx - 1;
            }
        }
        else {
            for (i = idx; i > szone->large_entry_cache_oldest; --i) {
                szone->large_entry_cache[i] = szone->large_entry_cache[i - 1];
            }
            if (idx == szone->large_entry_cache_oldest) {
                next_idx = -1;
            } else {
                next_idx = idx;
            }
            if (szone->large_entry_cache_oldest < szone->large_cache_depth - 1) {
                szone->large_entry_cache_oldest++;
            } else {
                szone->large_entry_cache_oldest = 0;
            }
        }
    }
    else {
        szone->large_entry_cache[idx].address = 0;
        szone->large_entry_cache[idx].size = 0;
        next_idx = -1;
    }
    return next_idx;
}

分为以下几种情况：

1. large_entry_cache_oldest小于large_entry_cache_newest，例如缓存数组未满的情况，如图，例如匹配entry2并回来，移除后，entry3～6向前移动，其他entry方位不变。large_entry_cache_newest方位减1。

   

2. large_entry_cache_newest小于large_entry_cache_oldest，例如缓存数组满的情况，依据匹配entry的idx方位分为以下情况：

   1. idx <= szone->large_entry_cache_newest，如图，例如匹配entry10移除后，entry11～13向前移动，其他entry方位不变，large_entry_cache_newest方位减1.

      

   2. idx > szone->large_entry_cache_newest，如图，例如匹配entry7移除后，entry5～6向后移动，其他entry方位不变，large_entry_cache_oldest方位加1.

      

3. large_entry_cache_newest等于large_entry_cache_oldest，例如数组中仅存在一个entry的情况，移除后数组为空，如图。

   

中心流程

接下来剖析内存分配与收回的流程。

内存分配

运用large_malloc办法分配large内存

void *large_malloc(szone_t *szone, size_t num_kernel_pages, unsigned char alignment, boolean_t cleared_requested)
{
    void *addr;
    vm_range_t range_to_deallocate;
    size_t size;
    range_to_deallocate.size = 0;
    range_to_deallocate.address = 0;
#if CONFIG_LARGE_CACHE
    // Look for a large_entry_t on the death-row cache?
    if (large_cache_enabled && size <= szone->large_cache_entry_limit) {
        addr = large_malloc_from_cache(szone, size, alignment, cleared_requested);
        if (addr != NULL) {
            return addr;
        }
    }
#endif 
    addr = mvm_allocate_pages(size, alignment, MALLOC_APPLY_LARGE_ASLR(szone->debug_flags), VM_MEMORY_MALLOC_LARGE);
    if (addr == NULL) {
        return NULL;
    }
    bool success = large_entry_grow_and_insert_no_lock(szone, (vm_address_t) addr, (vm_size_t) size,
            &range_to_deallocate);
    if (!success) {
        return NULL;
    }
    if (range_to_deallocate.size) {
        mvm_deallocate_pages((void *)range_to_deallocate.address, range_to_deallocate.size, 0);
    }
    return addr;
}

进程如下：

1. 调用large_malloc_from_cache办法从缓存中查找可用的内存块，假如成功执结回来内存块地址addr。

   static void *large_malloc_from_cache(szone_t *szone, size_t size, unsigned char alignment, boolean_t cleared_requested)
   {
       large_entry_t entry;
       while (true) {
           entry = large_malloc_best_fit_in_cache(szone, size, alignment);
           if (entry.address == (vm_address_t)NULL) {
               return NULL;
           } else {
               break;
           }
       }
       vm_range_t range_to_deallocate;
       range_to_deallocate.size = 0;
       range_to_deallocate.address = 0;
       bool success = large_entry_grow_and_insert_no_lock(szone, entry.address, entry.size, &range_to_deallocate);
       if (!success) {
           return NULL;
       }
       szone->large_entry_cache_bytes -= entry.size;
       if (range_to_deallocate.size) {
           mvm_deallocate_pages((void *)range_to_deallocate.address, range_to_deallocate.size, 0);
       }
       return (void *)entry.address;
   }
   

   1. 调用large_malloc_best_fit_in_cache办法从缓存数组中查找可用内存块，假如未找到，则回来NULL，不然将找到的内存块对应的entry参加hash数组中办理。
   2. 更新缓存信息large_entry_cache_bytes。
   3. 假如扩容，range_to_deallocate记载原数组内存，调用mvm_deallocate_pages办法收回。

2. 假如没有找到，则调用mvm_allocate_pages办法分配一块内存，调用large_entry_grow_and_insert_no_lock办法并生成entry参加hash数组中办理。

3. 假如扩容，range_to_deallocate记载原数组内存，调用mvm_deallocate_pages办法收回。

4. 回来entry的内存块address

内存收回

调用free_large办法收回large内存

bool free_large(szone_t *szone, void *ptr, bool try)
{
    large_entry_t *entry;
    vm_range_t vm_range_to_deallocate;
    vm_range_to_deallocate.size = 0;
    vm_range_to_deallocate.address = 0;
    entry = large_entry_for_pointer_no_lock(szone, ptr);
    if (entry) {
#if CONFIG_LARGE_CACHE
        if (large_cache_enabled && entry->size <= szone->large_cache_entry_limit) {
            int idx = szone->large_entry_cache_newest, stop_idx = szone->large_entry_cache_oldest;
            large_entry_t this_entry = *entry;
            boolean_t reusable = TRUE;
            //判别是否二次收回
            while (1) {
                //...
            }
            vm_range_to_deallocate = large_entry_free_no_lock(szone, entry);
            entry = NULL;
            szone->num_large_objects_in_use--;
            szone->num_bytes_in_large_objects -= this_entry.size;
            //增加缓存
            if (reusable) {
                //...
            }
        }
#endif
        if (!vm_range_to_deallocate.address) {
            szone->num_large_objects_in_use--;
            szone->num_bytes_in_large_objects -= entry->size;
            vm_range_to_deallocate = large_entry_free_no_lock(szone, entry);
        }
    }
    if (vm_range_to_deallocate.address) {
        mvm_deallocate_pages((void *)vm_range_to_deallocate.address, (size_t)vm_range_to_deallocate.size, 0);
    }
    return true;
}

进程如下：

1. 调用large_entry_for_pointer_no_lock办法查找收回内存块的entry。
2. 假如支撑缓存逻辑，将entry增加进缓存后直接回来。
3. 不然调用mvm_deallocate_pages收回内存块，调用large_entry_free_no_lock清空hash数组中的entry数据。

以上是small和large代码的剖析，欢迎大家交流谈论～