一、【ptmalloc初始化实现】

一、ptmalloc的简介

Linux早期的版本，是由Doug Lea实现的，但是早期的版本有一个问题，就是没办法处理多线程下并发分配和回收的高效和正确性。Wolfram Gloger在Doug Lea的基础上改进使得Glibc的malloc可以支持多线程，ptmalloc。在glibc-2.3.x.中已经集成了ptmalloc2，所以我们平时使用Linux系统的时候，使用到的内存分配器就是ptmalloc。

ptmalloc实现了malloc()，free()以及一组其它的函数，提供系统级别的内存管理。

ptmalloc内存分配器处于用户程序和内核之间，通过malloc/free等函数响应上层使用者的内存分配请求。ptmalloc向操作系统申请内存，然后返回到上层用户层。

为了保持高效的分配，分配器一般都会预先分配一块大于用户请求的内存，并通过某种算法管理这块内存。来满足用户的内存分配要求，用户释放掉的内存也并不是立即就返回给操作系统，相反，分配器会管理这些被释放掉的空闲空间，以应对用户以后的内存分配要求。也就是说，分配器不但要管理已分配的内存块，还需要管理空闲的内存块，当响应用户分配要求时，分配器会首先在空闲空间中寻找一块合适的内存给用户，在空闲空间中找不到的情况下才分配一块新的内存。

通过下载glic2.31源码包，我们就能看到ptmalloc的源码实现。

二、入口启动函数__libc_malloc

ptmalloc的源码在glibc/malloc文件夹下。malloc函数的入口在malloc/malloc.c文件中。

但是我们没法直接找到malloc的函数，这里glibc就是通过别名机制string_alias，从malloc映射到__libc_malloc函数。

所以，当用户调用malloc(xx)分配内存的时候，实际调用了malloc.c文件中的__libc_malloc函数。

strong_alias (__libc_calloc, __calloc) weak_alias (__libc_calloc, calloc)

strong_alias (__libc_free, __free) strong_alias (__libc_free, free)

strong_alias (__libc_malloc, __malloc) strong_alias (__libc_malloc, malloc)

strong_alias (__libc_memalign, __memalign)

weak_alias (__libc_memalign, memalign)

strong_alias (__libc_realloc, __realloc) strong_alias (__libc_realloc, realloc)

strong_alias (__libc_valloc, __valloc) weak_alias (__libc_valloc, valloc)

strong_alias (__libc_pvalloc, __pvalloc) weak_alias (__libc_pvalloc, pvalloc)

strong_alias (__libc_mallinfo, __mallinfo)

weak_alias (__libc_mallinfo, mallinfo)

strong_alias (__libc_mallopt, __mallopt) weak_alias (__libc_mallopt, mallopt)

weak_alias (__malloc_stats, malloc_stats)

weak_alias (__malloc_usable_size, malloc_usable_size)

weak_alias (__malloc_trim, malloc_trim)

1. 初始化的原子模式atomic_forced_read

我们先看一下入口函数__libc_malloc的核心代码：

/**

* malloc() 主函数入口

*/

void *

__libc_malloc (size_t bytes)

{

mstate ar_ptr;

void *victim;

_Static_assert (PTRDIFF_MAX <= SIZE_MAX / 2,

"PTRDIFF_MAX is not more than half of SIZE_MAX");

/**

* 1. __malloc_hook 值是 malloc_hook_ini ，初始化ptmalloc

* 2. atomic_forced_read 汇编语句，原子读操作，读取__malloc_hook

* 3. weak_variable 相当于属性赋值操作attribute，将malloc_hook_ini转到__malloc_hook

* 4. malloc_hook_ini 中调用的是ptmalloc_init()函数，初始化ptmalloc

*/

void *(*hook) (size_t, const void *)

= atomic_forced_read (__malloc_hook);

if (__builtin_expect (hook != NULL, 0))

return (*hook)(bytes, RETURN_ADDRESS (0));

mstate ar_ptr指向全局内存分配器的指针，说白了就是全局内存分配器状态机。具体的数据结构第二章详细讲解。

atomic_forced_read 是汇编语句，用于原子读操作，每次只会读取一次。例如调用malloc_hook_ini初始化只会调用一次

__malloc_hook指向malloc_hook_ini，该函数为ptmalloc的初始化函数。主要用于初始化全局状态机+chunk的数据结构

//---------原子读操作

#ifndef atomic_forced_read

# define atomic_forced_read(x) \

({ __typeof (x) __x; __asm ("" : "=r" (__x) : "0" (x)); __x; })

#endif

//__malloc_hook指向malloc_hook_ini函数

void *weak_variable (*__malloc_hook)

(size_t __size, const void *) = malloc_hook_ini; //设置__malloc_hook函数

2. 初始化的调用顺序malloc_hook_ini

先看一下malloc_hook_ini函数：

/**

* 初始化

*/

static void *

malloc_hook_ini (size_t sz, const void *caller)

{

__malloc_hook = NULL;

ptmalloc_init ();

return __libc_malloc (sz);

}

先将__malloc_hook的值设置为NULL，然后调用ptmalloc_init函数，最后竟然又回调了__libc_malloc函数。

在我们第一次调用 malloc 申请堆空间的时候，首先会进入 malloc_hook_ini 函数里面进行对 ptmalloc 的初始化工作，然后再次进入 __libc_malloc 的时候，此时钩子 __malloc_hook 已经被置空了，从而继续执行剩余的代码，即转入 _int_malloc 函数

可以看一下整体的调用逻辑和顺序：

3. 初始化的核心逻辑ptmalloc_init

ptmalloc初始化过程核心就是初始化：全局内存分配器的状态机

通过__malloc_initialized全局变量，来记录初始化的状态。0=未初始化，1-初始化。如果已经初始化，则直接返回

main_arena是全局内存分配器状态机的主线程结构，数据结构：mstate

malloc_init_state是核心初始化mstate状态机数据结构

/*

* ptmalloc_init 初始化过程

*/

static void

ptmalloc_init (void)

{

/**

* 1. 判断是否已经初始化，如果初始化过了，则不再执行；

* 2. 如果等于0，则正在初始化，如果等于1，则初始化完成

*/

if (__malloc_initialized >= 0)

return;

__malloc_initialized = 0;

#ifdef SHARED

/* In case this libc copy is in a non-default namespace, never use brk.

Likewise if dlopened from statically linked program. */

Dl_info di;

struct link_map *l;

if (_dl_open_hook != NULL

|| (_dl_addr (ptmalloc_init, &di, &l, NULL) != 0

&& l->l_ns != LM_ID_BASE))

__morecore = __failing_morecore;

#endif

/**

* 1. main_arena为主分配区域

* 2. malloc_init_state 初始化主分配区数据

*/

thread_arena = &main_arena;

malloc_init_state (&main_arena);

......

......

......

//设置hook值

#if HAVE_MALLOC_INIT_HOOK

void (*hook) (void) = atomic_forced_read (__malloc_initialize_hook);

if (hook != NULL)

(*hook)();

#endif

/* 初始化完毕，则设置为1 */

__malloc_initialized = 1;

}

二、【分配器状态机malloc_state】

一、Linux系统的堆栈结构

Linux的内存空间地址从低到高一般分为五个部分：内核空间、栈区域、堆区域、BBS段、数据段和代码段

内核空间：我们在编写应用程序（非内核空间程序）的时候，这一块地址我们是不能够使用的

栈区域：程序中局部变量、函数参数、返回地址的地方地址。地址从低到高分配

堆区域：由malloc,calloc等创建的空间，是运行的时候由程序申请的。地址由高到低

BBS段：未初始化或初值为0的全局变量和静态局部变量

数据段：已初始化且初值非0的全局变量和静态局部变量

代码段：可执行代码、字符串字面值、只读变量

所以，我们使用ptmalloc的内存分配的时候，一般都是在堆上进行操作的。说白了，ptmalloc就是通过管理堆上的内存分配，来管理整个用户层malloc函数发起的内存请求

通过brk方式分配的内存，一般都是从高地址到低地址；（堆的操作，操作系统提供了brk的函数，glibc提供了sbrk的函数）

通过mmap方式分配的内存，一般都是从低地址到高地址的。

#include <unistd.h>

int brk( const void *addr )

void* sbrk ( intptr_t incr );

Brk：参数设置为新的brk上界地址，成功返回1，失败返回0；

Sbrk：参数为申请内存的大小，返回heap新的上界brk的地址

#include <sys/mman.h>

void *mmap(void *addr, size\_t length, int prot, int flags, int fd, off\_t offset);

int munmap(void *addr, size_t length);

mmap：第一种用法是映射此盘文件到内存中；第二种用法是匿名映射，不映射磁盘文件，而向映射区申请一块内存。

munmap：函数用于释放内存。

二、主分配区数据结构malloc_state

ptmalloc通过malloc_state的状态机来管理内存的分配。malloc_state主要用来管理分配的内存块，比如是否有空闲的chunk，有什么大小的空闲chunk 等等。（chunk是内存管理的最小单元，后面一章会重点讲解）。当用户层调用malloc/free等函数的时候，都会通过ptmalloc内核模块进行内存的分配，每一块从操作系统上分配的内存，都会使用malloc_state结构体来管理。

我们先看一下malloc_state的关键数据结构

mutex：线程锁，当多线程进行内存分配竞争的时候，需要首先拿到该锁才能进行分配区上的操作。

flags：记录了分配区的一些标志，比如 bit0 记录了分配区是否有 fast bin chunk ，bit1 标识分配区是否能返回连续的虚拟地址空间

have_fastchunks：用于标记是否有fast bins。

fastbinsY：fast bins是bins的高速缓冲区，大约有10个定长队列。当用户释放一块不大于max_fast（默认值64）的chunk（一般小内存）的时候，会默认会被放到fast bins上。

top：指向分配区的 top chunk。top chunk相当于分配区的顶部空闲内存，当bins上都不能满足内存分配要求的时候，就会来top chunk上分配。

last_remainder：最新的 chunk 分割之后剩下的那部分

bins：用于存储 unstored bin，small bins 和 large bins 的 chunk 链表。

binmap：ptmalloc 用一个 bit 来标识某一个 bin 中是否包含空闲 chunk 。

next：分配区全局链表，主分配区放头部，新加入的分配区放main_arean.next 位置。

next_free：空闲的分配区

/**

* 全局malloc状态管理

*/

struct malloc_state

{

/* Serialize access. 同步访问互斥锁 */

__libc_lock_define (, mutex);

/* Flags (formerly in max_fast).

* 用于标记当前主分配区的状态

* */

int flags;

/* Set if the fastbin chunks contain recently inserted free blocks. */

/* Note this is a bool but not all targets support atomics on booleans. */

/* 用于标记是否有fastchunk */

int have_fastchunks;

/* Fastbins fast bins。

* fast bins是bins的高速缓冲区，大约有10个定长队列。

* 当用户释放一块不大于max_fast（默认值64）的chunk（一般小内存）的时候，会默认会被放到fast bins上。

* */

mfastbinptr fastbinsY[NFASTBINS];

/* Base of the topmost chunk -- not otherwise kept in a bin */

/* Top chunk ：并不是所有的chunk都会被放到bins上。

* top chunk相当于分配区的顶部空闲内存，当bins上都不能满足内存分配要求的时候，就会来top chunk上分配。 */

mchunkptr top;

/* The remainder from the most recent split of a small request */

mchunkptr last_remainder;

/* Normal bins packed as described above

* 常规 bins chunk的链表数组

* 1. unsorted bin：是bins的一个缓冲区。当用户释放的内存大于max_fast或者fast bins合并后的chunk都会进入unsorted bin上

* 2. small bins和large bins。small bins和large bins是真正用来放置chunk双向链表的。每个bin之间相差8个字节，并且通过上面的这个列表，

* 可以快速定位到合适大小的空闲chunk。

* 3. 下标1是unsorted bin，2到63是small bin，64到126是large bin，共126个bin

* */

mchunkptr bins[NBINS * 2 - 2];

/* Bitmap of bins

* 表示bin数组当中某一个下标的bin是否为空，用来在分配的时候加速

* */

unsigned int binmap[BINMAPSIZE];

/* 分配区全局链表：分配区链表，主分配区放头部，新加入的分配区放main_arean.next 位置 Linked list */

struct malloc_state *next;

/* 分配区空闲链表 Linked list for free arenas. Access to this field is serialized

by free_list_lock in arena.c. */

struct malloc_state *next_free;

/* Number of threads attached to this arena. 0 if the arena is on

the free list. Access to this field is serialized by

free_list_lock in arena.c. */

INTERNAL_SIZE_T attached_threads;

/* Memory allocated from the system in this arena. */

INTERNAL_SIZE_T system_mem;

INTERNAL_SIZE_T max_system_mem;

};

三、状态机组织chunk的方式

ptmalloc的空闲chunk都是通过在malloc_state上的bins数组来管理的。

1. 基础类型的bins：fast、unsorted、small、large

一共分为四种类型的bins：fast bins、 unsorted bin、small bins和large bins。

fast bins：fast bins是bins的高速缓冲区，大约有10个定长队列。当用户释放一块不大于max_fast（默认值64）的chunk（一般小内存）的时候，会默认会被放到fast bins上。当用户下次需要申请内存的时候首先会到fast bins上寻找是否有合适的chunk，然后才会到bins上空闲链表里面查找的chunk。ptmalloc会遍历fast bin，看是否有合适的chunk需要合并到bins上。主要放置在fastbinsY数组上。

unsorted bin：是bins的一个缓冲区，bins数组下标为1的即是unstored bin。当用户释放的内存大于max_fast或者fast bins合并后的chunk都会进入unsorted bin上。当用户malloc的时候，先会到unsorted bin上查找是否有合适的bin，如果没有合适的bin，ptmalloc会将unsorted bin上的chunk放入bins上，然后到bins上查找合适的空闲chunk。

small bins：小于512字节（64位机器1024字节）的chunk被称为small chunk，而保存small chunks的bin被称为small bin。数组从2开始编号到63，前62个bin为small bins，small bin每个bin之间相差8个字节（64位16字节），同一个small bin中的chunk具有相同大小。起始bin大小为16字节（64位系统32）。

large bins：大于等于512字节（64位机器1024字节）的chunk被称为large chunk，而保存large chunks的bin被称为large bin。位于small bins后面，数组编号从64开始，后64个bin为large bins。同一个bin上的chunk，可以大小不一定相同。large bins都是通过等差步长的方式进行拆分。（以32位系统为例，前32个bin步长64，后16个bin步长512，后8个步长4096，后四个32768，后2个262144）（编号63到64的步长跟）。起始bin大小为512字节（64位系统1024）。

2. bins之间的步长关系

然后再看一下，small bin和large bin每个bin之间的步长等差数列。在32位系统下面，前63个bin（small bins）的步长为8，后32个bins（large bins）步长64，以此类推。

small bins一个62个，每个bins之间的步长一致，32位系统步长8，64位系统步长16；

large bins 一共32+16+8+4+2+1=63个 + 起始bin（512或者1024）。以32位系统为例，前32个bin步长64，后16个bin步长512，后8个步长4096，后四个32768，后2个262144，后一个不限制

Bins for sizes < 512 bytes contain chunks of all the same size, spaced

8 bytes apart. Larger bins are approximately logarithmically spaced:

64 bins of size 8

32 bins of size 64

16 bins of size 512

8 bins of size 4096

4 bins of size 32768

2 bins of size 262144

1 bin of size what's left

3. 特殊类型的bins：top chunk、mmaped chunk、last remainder chunk

除了上面可见的bins管理之外，还是三种例外的chunk管理方式：top chunk，mmaped chunk 和last remainder chunk

Top chunk：top chunk相当于分配区的顶部空闲内存，当bins上都不能满足内存分配要求的时候，就会来top chunk上分配。top chunk大小比用户所请求大小还大的时候，top chunk会分为两个部分：User chunk（用户请求大小）和Remainder chunk（剩余大小）。其中Remainder chunk成为新的top chunk。当top chunk大小小于用户所请求的大小时，top chunk就通过sbrk（main arena）或mmap（thread arena）系统调用来扩容。

mmaped chunk：当分配的内存非常大（大于分配阀值，默认128K）的时候，需要被mmap映射，则会放到mmaped chunk上，当释放mmaped chunk上的内存的时候会直接交还给操作系统。

Last remainder chunk：Last remainder chunk是另外一种特殊的chunk，就像top chunk和mmaped chunk一样，不会在任何bins中找到这种chunk。当需要分配一个small chunk,但在small bins中找不到合适的chunk，如果last remainder chunk的大小大于所需要的small chunk大小，last remainder chunk被分裂成两个chunk，其中一个chunk返回给用户，另一个chunk变成新的last remainder chunk。

四、多线程争夺问题的解决

ptmalloc的分配器为了解决多线程争夺问题，分为主分配区main_area和非主分配区thread_arena

每个进程有一个主分配区，也可以允许有多个非主分配区。

主分配区可以使用brk和mmap来分配，而非主分配区只能使用mmap来映射内存块

非主分配区的数量一旦增加，则不会减少。

主分配区和非主分配区形成一个环形链表进行管理。通过malloc_state->next来链接

我们可以看一下一个线程调用malloc的时候的流程以及分配区的状态：

当一个线程使用malloc分配内存的时候，首选会检查该线程环境中是否已经存在一个分配区，如果存在，则对该分配区进行加锁，并使用该分配区进行内存分配

如果分配失败，则遍历链表中获取的未加锁的分配区

如果整个链表都没有未加锁的分配区，则ptmalloc开辟一个新的分配区，假如malloc_state->next全局队列，并该线程在改内存分区上进行分配

当释放这块内存的时候，首先获取分配区的锁，然后释放内存，如果其他线程正在使用，则等待其他线程

/* 分配区全局链表：分配区链表，主分配区放头部，新加入的分配区放main_arean.next 位置 Linked list */

struct malloc_state *next;

/* 分配区空闲链表 Linked list for free arenas. Access to this field is serialized

by free_list_lock in arena.c. */

struct malloc_state *next_free;

五、状态机的初始化malloc_init_state

状态机的初始化，通过malloc_init_state。初始化过程主要做了三件事情：

将bins进行初始化，生成bins数组

处理fastchunk的状态

初始化Top chunk，默认指向了unsorted bin上的第一个chunk

static void

malloc_init_state (mstate av)

{

int i;

mbinptr bin;

/* Establish circular links for normal bins */

/* NBINS=128 */

/**

* 说明：ptmalloc通过bins数组来管理chunk双向链表，初始化的chunk链表指针都指向了自己

* 1. bins上管理三种bin：unsorted bin、small bins和large bins

* 2. 下标默认从1开始，其中下标为1的，则是unsorted bin

*/

for (i = 1; i < NBINS; ++i)

{

bin = bin_at (av, i);

bin->fd = bin->bk = bin;

}

#if MORECORE_CONTIGUOUS

if (av != &main_arena)

#endif

set_noncontiguous (av);

if (av == &main_arena)

set_max_fast (DEFAULT_MXFAST);

/* 默认fastchunk 是false的，没有被初始化的 */

atomic_store_relaxed (&av->have_fastchunks, false);

/* 初始化Top chunk，默认指向了unsorted bin上的第一个chunk */

av->top = initial_top (av);

}

//通过bin_at方法，找到bin对应位置

/* addressing -- note that bin_at(0) does not exist */

#define bin_at(m, i) \

(mbinptr) (((char *) &((m)->bins[((i) - 1) * 2])) \

- offsetof (struct malloc_chunk, fd))

六、BINS的宏定义和操作

前面说过，我们的空闲chunk，都会在bins上管理。ptmalloc提供了一些方便的宏函数，用于操作bin上的chunk。

1. BINS的基础定义字段

NBINS：值为128，用于循环遍历bin的个数，实际bin的个数为127个，因为下标从1开始

NSMALLBINS：定义了small bin的个数为64个，large bin个数为62个

SMALLBIN_WIDTH：small bin的步长宽度，32位系统8个字节，64位系统16个字节

MIN_LARGE_SIZE：large bin最小的值是64 * SMALLBIN_WIDTH，所以32位系统是512字节，64位系统是1024字节

#define NBINS 128 //默认128个bins

#define NSMALLBINS 64 //small bin的个数

#define SMALLBIN_WIDTH MALLOC_ALIGNMENT //small bin的长度

#define SMALLBIN_CORRECTION (MALLOC_ALIGNMENT > 2 * SIZE_SZ)

#define MIN_LARGE_SIZE ((NSMALLBINS - SMALLBIN_CORRECTION) * SMALLBIN_WIDTH)

2. BINS的基本查找函数

bin_at：通过下标找到bin

next_bin：通过bin上的一个chunk，找到物理地址的下一个chunk地址

first和last：获取空闲bins上的chunk双向链表指针，找到前后的chunk

bin_index：将 sz 大小转换成对应的数组下标。（判断属于 large bin 还是 small bin）。例：第一个largebin的起始大小为1024，那么1024>>6=16，所以其在bins数组中的下标为48+16=64

/* addressing -- note that bin_at(0) does not exist */

//通过下标找到bin

#define bin_at(m, i) \

(mbinptr) (((char *) &((m)->bins[((i) - 1) * 2])) \

- offsetof (struct malloc_chunk, fd))

/* analog of ++bin */

//通过bin上的一个chunk，找到物理地址的下一个chunk地址

#define next_bin(b) ((mbinptr) ((char *) (b) + (sizeof (mchunkptr) << 1)))

/* Reminders about list directionality within bins */

//在bins上管理的chunk是通过fd/bk双向链表指针链接起来的

//first=获取前一个指针地址 last=获取后一个指针地址

#define first(b) ((b)->fd)

#define last(b) ((b)->bk)

/* sz 大小属于 small bins 置 1，否则置 0 */

#define in_smallbin_range(sz) \

((unsigned long) (sz) < (unsigned long) MIN_LARGE_SIZE)

/* 将 sz 大小 转换成对应的数组下标。（对 samll bin） */

#define smallbin_index(sz) \

((SMALLBIN_WIDTH == 16 ? (((unsigned) (sz)) >> 4) : (((unsigned) (sz)) >> 3))\

+ SMALLBIN_CORRECTION)

/* 将 sz 大小 转换成对应的数组下标。（对 32 位 large bin） */

#define largebin_index_32(sz) \

(((((unsigned long) (sz)) >> 6) <= 38) ? 56 + (((unsigned long) (sz)) >> 6) :\

((((unsigned long) (sz)) >> 9) <= 20) ? 91 + (((unsigned long) (sz)) >> 9) :\

((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :\

((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :\

((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :\

126)

#define largebin_index_32_big(sz) \

(((((unsigned long) (sz)) >> 6) <= 45) ? 49 + (((unsigned long) (sz)) >> 6) :\

((((unsigned long) (sz)) >> 9) <= 20) ? 91 + (((unsigned long) (sz)) >> 9) :\

((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :\

((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :\

((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :\

126)

// XXX It remains to be seen whether it is good to keep the widths of

// XXX the buckets the same or whether it should be scaled by a factor

// XXX of two as well.

/* 将 sz 大小 转换成对应的数组下标。（对 64 位 large bin） */

/* 第一个largebin的起始大小为1024，那么1024>>6=16，所以其在bins数组中的下标为48+16=64 */

#define largebin_index_64(sz) \

(((((unsigned long) (sz)) >> 6) <= 48) ? 48 + (((unsigned long) (sz)) >> 6) :\

((((unsigned long) (sz)) >> 9) <= 20) ? 91 + (((unsigned long) (sz)) >> 9) :\

((((unsigned long) (sz)) >> 12) <= 10) ? 110 + (((unsigned long) (sz)) >> 12) :\

((((unsigned long) (sz)) >> 15) <= 4) ? 119 + (((unsigned long) (sz)) >> 15) :\

((((unsigned long) (sz)) >> 18) <= 2) ? 124 + (((unsigned long) (sz)) >> 18) :\

126)

/* 将 sz 大小 转换成对应的数组下标。（根据 SIZE_SZ 判断 large bin 转换宏）*/

#define largebin_index(sz) \

(SIZE_SZ == 8 ? largebin_index_64 (sz) \

: MALLOC_ALIGNMENT == 16 ? largebin_index_32_big (sz) \

: largebin_index_32 (sz))

/* 将 sz 大小 转换成对应的数组下标。（判断属于 large bin 还是 small bin） */

#define bin_index(sz) \

((in_smallbin_range (sz)) ? smallbin_index (sz) : largebin_index (sz))

三、【内存组织单元】

ptmalloc的最小内存组织单元是malloc_chunk的数据结构。通过malloc_chunk的数据结构，用于管理每次前端程序使用malloc函数调用所产生的在堆上分配的内存。

一、malloc_chunk的数据结构

1. malloc_chunk的基础结构

先来看一下malloc_chunk的数据结构：

mchunk_prev_size：该字段记录物理相邻的前一个chunk的大小（低地址chunk）。如果前一个chunk处于空闲，则该字段记录前一个chunk大小；如果前一个chunk已经被使用，则该字段空间可以被前一个chunk的用户数据空间复用

mchunk_size：该字段是chunk的大小。每次对齐的时候，都需要加上mchunk_prev_size和mchunk_size两个字段的空间值 2*SIZE_SZ 。该字段的低三个比特位对 chunk 的大小没有影响，所以被复用为标志位

fd和bk：当chunk空闲的时候，会放置到bins上双向链表管理。fd 指向下一个（非物理相邻）空闲的 chunk。bk 指向上一个（非物理相邻）空闲的 chunk。由于只有chunk空闲的时候，才会放置到bins上进行空闲管理，所以fd和bk占用的是用户数据区域user data

fd_nextsize和bk_nextsize：用于管理large块的时候的空闲chunk双向链表的管理。一般空闲的 large chunk 在 fd 的遍历顺序中，按照由大到小的顺序排列。这样做可以避免在寻找合适 chunk 时挨个遍历。

struct malloc_chunk {

INTERNAL_SIZE_T mchunk_prev_size; /* Size of previous chunk (if free). */

INTERNAL_SIZE_T mchunk_size; /* 当前chunk的大小 Size in bytes, including overhead. */

struct malloc_chunk* fd; /* double links -- used only if free. */

struct malloc_chunk* bk;

struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */

struct malloc_chunk* bk_nextsize;

};

2. malloc_chunk使用时的状态

当前chunk如果被使用中，则有几个特征：

复用相邻下一个nextchunk（高地址chunk）的mchunk_prev_size字段的数据空间。所以该chunk的内存空间为当前内存 + mchunk_prev_size字段空间

由于chunk被使用中，所以不需要通过双向链表方式挂载到空闲bins上管理，所以fd和bk以及fd_nextsize和bk_nextsize不需要被使用

图解：

chunk-> 是当前内存组织单元的开始地址；

mem -> 是用户数据区user data的开始区域；

nextchunk-> 是下一个内存组织单元的开始地址

从上图中可以看到，chunk正在被使用中，所以没有fd/bk以及fd_nextsize/bk_nextsize的指针。

而chunk的用户内存区域（user data），除了本身内存区域之外，也将底部nextchunk的mchunk_prev_size指针数据部分给复用了进来，实现了内存空间的复用。

3. malloc_chunk空闲时的状态

当chunk为空闲的时候，chunk会被挂载的空闲链表bins上进行管理，所以空闲的chunk有几个特征

fd/bk以及fd_nextsize/bk_nextsize的指针地址，复用了用户数据区域（userdata）的空间

下一个nextchunk的mchunk_prev_size值，记录了当前chunk的大小

从上图中可以看到，由于空闲chunk需要通过双向链表指针来管理，所以fd/bk的指针复用了用于内存存储区域。

二、mchunk_size的内存分配大小

最小的空间：mchunk_prev_size字段 + mchunk_size字段 + fd字段 + bk字段 所需要的空间。所以64位系统最低需要 4 * SIZE_SZ = 32字节；32位系统是16字节

实际空间：malloc大小 + chunk对齐规则 + mchunk_prev_size字段 + mchunk_size字段 + 下一个chunk的mchunk_prev_size成员空间

chunk对齐规则：按照2*SIZE_SZ进行对齐，32位系统是8字节，64位系统是16字节。

bins步长规则：按照等差数列的方式步长拆分，前一章有详细讲解。以32位系统为例，前64个bin步长8，后32个bin步长64，后16个bin步长512，后8个步长4096，后四个32768，后2个262144。

我们看一下chunk的数据结构大小的图（64位系统）：

三、mchunk_size的标记位的复用

mchunk_size在64位系统下是8个字节，字段的最后三个bit位，复用用作了（AMP）的标记位置。后三位bit位的复用，不会影响size的数据大小

A：A=0 为主分区分配，A=1 为非主分区分配，参见后面

M：M=1表示使用mmap映射区域，M=0为使用heap区域

P：P=1 表示pre_chunk空闲，mchunk_prev_size才有效

四、malloc_chunk的宏函数操作

malloc.c文件中定义了malloc_chunk的一系列相关宏的操作，重要定义如下：

chunk2mem：chunk的起始地址转换到用户内存mem地址。chunk起始地址在低地址，所以通过加上2*SIZE_SZ的方式，转换到高地址的mem地址指针

mem2chunk：用户内存mem地址转换到chunk的起始地址。用户内存mem地址在高地址，所以通过减去2*SIZE_SZ的方式，转到低地址的chunk的起始地址

MIN_CHUNK_SIZE：最小的chunk大小。通过offsetof 函数计算出 fd_nextsize 在 malloc_chunk 中的偏移，至少包含mchunk_prev_size、mchunk_size、fd、bk四个地址的空间量。所以64位系统，最小是32字节（4*8）；32位系统，最小是16字节（4*4）

aligned_OK：检查内存是否对齐。64位系统按照16字节对齐，32位系统按照8字节对齐

request2size：通过对齐后，实际chunk的大小。如果内存大小小于MINSIZE，则使用MINSIZE空间；否则通过MALLOC_ALIGN_MASK进行字节对齐。

/* conversion from malloc headers to user pointers, and back */

#define chunk2mem(p) ((void*)((char*)(p) + 2*SIZE_SZ))

#define mem2chunk(mem) ((mchunkptr)((char*)(mem) - 2*SIZE_SZ))

/* The smallest possible chunk */

#define MIN_CHUNK_SIZE (offsetof(struct malloc_chunk, fd_nextsize))

/* The smallest size we can malloc is an aligned minimal chunk */

#define MINSIZE \

(unsigned long)(((MIN_CHUNK_SIZE+MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK))

/* Check if m has acceptable alignment */

#define aligned_OK(m) (((unsigned long)(m) & MALLOC_ALIGN_MASK) == 0)

#define misaligned_chunk(p) \

((uintptr_t)(MALLOC_ALIGNMENT == 2 * SIZE_SZ ? (p) : chunk2mem (p)) \

& MALLOC_ALIGN_MASK)

/* pad request bytes into a usable size -- internal version */

#define request2size(req) \

(((req) + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE) ? \

MINSIZE : \

((req) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)

/* Check if REQ overflows when padded and aligned and if the resulting value

is less than PTRDIFF_T. Returns TRUE and the requested size or MINSIZE in

case the value is less than MINSIZE on SZ or false if any of the previous

check fail. */

static inline bool

checked_request2size (size_t req, size_t *sz) __nonnull (1)

{

if (__glibc_unlikely (req > PTRDIFF_MAX))

return false;

*sz = request2size (req);

return true;

}

/* MALLOC_ALIGNMENT is the minimum alignment for malloc'ed chunks. It

must be a power of two at least 2 * SIZE_SZ, even on machines for

which smaller alignments would suffice. It may be defined as larger

than this though. Note however that code and data structures are

optimized for the case of 8-byte alignment. */

#define MALLOC_ALIGNMENT (2 * SIZE_SZ < __alignof__ (long double) \

? __alignof__ (long double) : 2 * SIZE_SZ)