Glibc内存管理--ptmalloc2源代码分析（十二）
5. 源代码分析分主要对源代码实现技巧的细节做分析，希望能进一步理解ptmalloc的实现，做到终极无惑。主要分析的文件包括arena.c和malloc.c，这两个文件包括了ptmalloc的核心实现，其中arena.c主要是对多线程支持的实现，malloc.c定义了公用的malloc()，free()等函数，实现了基于分配区的内存管理算法。本部分不会从头到尾分析arena.c和malloc.c整个文件，而是根据ptmalloc的实现原理，分成几个模块分别介绍，主要分析了malloc()和free()函数的实现，对其它的函数如realloc()，calloc()等不作介绍。由于ptmalloc同时支持32位平台和64位平台，所以这里的分析尽量兼顾到这两类平台，但主要基于Linux X86平台。
1
2
5.1 边界标记法
Ptmalloc使用chunk实现内存管理，对chunk的管理基于独特的边界标记法，第三节已经对chunk的管理做了概述，这里将详细分析chunk管理的源代码实现。
在不同的平台下，每个chunk的最小大小，地址对齐方式是不同的，ptmalloc依赖平台定义的size_t长度，对于32位平台，size_t长度为4字节，对64位平台，size_t长度可能为4字节，也可能为8字节，在Linux X86_64上size_t为8字节，这里就以size_t为4字节和8字节的情况进行分析。先看一段源代码：
#ifndef INTERNAL_SIZE_T#define INTERNAL_SIZE_T size_t#endif/* The corresponding word size */#define SIZE_SZ (sizeof(INTERNAL_SIZE_T))/*MALLOC_ALIGNMENT is the minimum alignment for malloc'ed chunks.It must be a power of two at least 2 * SIZE_SZ, even on machinesfor which smaller alignments would suffice. It may be defined aslarger than this though. Note however that code and data structuresare optimized for the case of 8-byte alignment.*/#ifndef MALLOC_ALIGNMENT#define MALLOC_ALIGNMENT (2 * SIZE_SZ)#endif/* The corresponding bit mask value */#define MALLOC_ALIGN_MASK (MALLOC_ALIGNMENT - 1) Ptmalloc使用宏来屏蔽不同平台的差异，将INTERNAL_SIZE_T定义为size_t，SIZE_SZ定义为size_t的大小，在32位平台下位4字节，在64位平台下位4字节或者8字节。另外分配chunk时必须以2*SIZE_SZ对齐，MALLOC_ALIGNMENT和MALLOC_ALIGN_MASK是用来处理chunk地址对齐的宏，将在后面的源代码介绍中经常看到。这里只需要知道在32平台chunk地址按8字节对齐，64位平台按8字节或是16字节对齐就可以了。
Ptmalloc采用边界标记法将内存划分成很多块，从而对内存的分配与回收进行管理。在ptmalloc的实现源码中定义结构体malloc_chunk来描述这些块，并使用宏封装了对chunk中每个域的读取，修改，校验，遍历等等。malloc_chunk定义如下：
struct malloc_chunk {INTERNAL_SIZE_T prev_size;/* Size of previous chunk (if free).*/INTERNAL_SIZE_T size; /* Size in bytes, including overhead. */struct malloc_chunk* fd; /* double links -- used only if free. */struct malloc_chunk* bk;/* Only used for large blocks: pointer to next larger size.*/struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */struct malloc_chunk* bk_nextsize;};chunk的定义相当简单明了，对各个域做一下简单介绍:
prev_size:如果前一个chunk是空闲的，该域表示前一个chunk的大小，如果前一个chunk不空闲，该域无意义。
size：当前chunk的大小，并且记录了当前chunk和前一个chunk的一些属性，包括前一个chunk是否在使用中，当前chunk是否是通过mmap获得的内存，当前chunk是否属于非主分配区。
fd和bk：指针fd和bk只有当该chunk块空闲时才存在，其作用是用于将对应的空闲chunk块加入到空闲chunk块链表中统一管理，如果该chunk块被分配给应用程序使用，那么这两个指针也就没有用（该chunk块已经从空闲链中拆出）了，所以也当作应用程序的使用空间，而不至于浪费。
fd_nextsize和bk_nextsize:当当前的chunk存在于large bins中时，large bins中的空闲chunk是按照大小排序的，但同一个大小的chunk可能有多个，增加了这两个字段可以加快遍历空闲chunk，并查找满足需要的空闲chunk，fd_nextsize指向下一个比当前chunk大小大的第一个空闲chunk，bk_nextszie指向前一个比当前chunk大小小的第一个空闲chunk。如果该chunk块被分配给应用程序使用，那么这两个指针也就没有用（该chunk块已经从size链中拆出）了，所以也当作应用程序的使用空间，而不至于浪费。
/* malloc_chunk details: (The following includes lightly edited explanations by Colin Plumb.) Chunks of memory are maintained using a `boundary tag' method as described in e.g., Knuth or Standish.(See the paper by Paul Wilson ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps for a survey of such techniques.)Sizes of free chunks are stored both in the front of each chunk and at the end.This makes consolidating fragmented chunks into bigger chunks very fast.The size fields also hold bits representing whether chunks are free or in use. An allocated chunk looks like this: chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Size of previous chunk, if allocated | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Size of chunk, in bytes |M|P| mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | User data starts here... . . . . (malloc_usable_size() bytes) . . |nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Size of chunk | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Where "chunk" is the front of the chunk for the purpose of most of the malloc code, but "mem" is the pointer that is returned to the user."Nextchunk" is the beginning of the next contiguous chunk. Chunks always begin on even word boundries, so the mem portion (which is returned to the user) is also on an even word boundary, and thus at least double-word aligned. Free chunks are stored in circular doubly-linked lists, and look like this: chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Size of previous chunk | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ `head:' | Size of chunk, in bytes |P| mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Forward pointer to next chunk in list | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Back pointer to previous chunk in list | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Unused space (may be 0 bytes long) . . . . |nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ `foot:' | Size of chunk, in bytes | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The P (PREV_INUSE) bit, stored in the unused low-order bit of the chunk size (which is always a multiple of two words), is an in-use bit for the *previous* chunk.If that bit is *clear*, then the word before the current chunk size contains the previous chunk size, and can be used to find the front of the previous chunk. The very first chunk allocated always has this bit set, preventing access to non-existent (or non-owned) memory. If prev_inuse is set for any given chunk, then you CANNOT determine the size of the previous chunk, and might even get a memory addressing fault when trying to do so. Note that the `foot' of the current chunk is actually represented as the prev_size of the NEXT chunk. This makes it easier to deal with alignments etc but can be very confusing when trying to extend or adapt this code. The two exceptions to all this are 1. The special chunk `top' doesn't bother using the trailing size field since there is no next contiguous chunk that would have to index off it. After initialization, `top' is forced to always exist.If it would become less than MINSIZE bytes long, it is replenished. 2. Chunks allocated via mmap, which have the second-lowest-order bit M (IS_MMAPPED) set in their size fields.Because they are allocated one-by-one, each must contain its own trailing size field.*/ 上面这段注释详细描述了chunk的细节，已分配的chunk和空闲的chunk形式不一样，充分利用空间复用，设计相当的巧妙。在前面的3.2.3.2节描述了这两种chunk形式，请参考前文的描述。
/* conversion from malloc headers to user pointers, and back */#define chunk2mem(p) ((Void_t*)((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)对于已经分配的chunk，通过chunk2mem宏根据chunk地址获得返回给用户的内存地址，反过来通过mem2chunk宏根据mem地址得到chunk地址，chunk的地址是按2*SIZE_SZ对齐的，而chunk结构体的前两个域刚好也是2*SIZE_SZ大小，所以，mem地址也是2*SIZE_SZ对齐的。宏aligned_OK和misaligned_chunk(p)用于校验地址是否是按2*SIZE_SZ对齐的。
MIN_CHUNK_SIZE定义了最小的chunk的大小，32位平台上位16字节，64位平台为24字节或是32字节。MINSIZE定义了最小的分配的内存大小，是对MIN_CHUNK_SIZE进行了2*SIZE_SZ对齐，地址对齐后与MIN_CHUNK_SIZE的大小仍然是一样的。
/* Check if a request is so large that it would wrap around zero when padded and aligned. To simplify some other code, the bound is made low enough so that adding MINSIZE will also not wrap around zero.*/#define REQUEST_OUT_OF_RANGE(req) \((unsigned long)(req) >= \ (unsigned long)(INTERNAL_SIZE_T)(-2 * MINSIZE))/* 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)/*Same, except also perform argument check */#define checked_request2size(req, sz) \if (REQUEST_OUT_OF_RANGE(req)) { \ MALLOC_FAILURE_ACTION; \ return 0; \} \(sz) = request2size(req); 这几个宏用于将用户请求的分配大小转换成内部需要分配的chunk大小，这里需要注意的在转换时不但考虑的地址对齐，还额外加上了SIZE_SZ，这意味着ptmalloc分配内存需要一个额外的overhead，为SIZE_SZ字节，通过chunk的空间复用，我们很容易得出这个overhead为SIZE_SZ。
以Linux X86_64平台为例，假设SIZE_SZ为8字节，空闲时，一个chunk中至少要4个size_t（8B）大小的空间，用来存储prev_size，size，fd和bk，也就是MINSIZE（32B），chunk的大小要对齐到2*SIZE_SZ（16B）。当一个chunk处于使用状态时，它的下一个chunk的prev_size域肯定是无效的。所以实际上，这个空间也可以被当前chunk使用。这听起来有点不可思议，但确实是合理空间复用的例子。故而实际上，一个使用中的chunk的大小的计算公式应该是：in_use_size = (用户请求大小+ 16 - 8 ) align to 8B，这里加16是因为需要存储prev_size和size，但又因为向下一个chunk“借”了8B，所以要减去8，每分配一个chunk的overhead为8B，即SIZE_SZ的大小。最后，因为空闲的chunk 和使用中的chunk使用的是同一块空间。所以肯定要取其中最大者作为实际的分配空间。即最终的分配空间chunk_size = max(in_use_size, 32)。这就是当用户请求内存分配时，ptmalloc实际需要分配的内存大小。
注意：如果chunk是由mmap ()直接分配的，则该chunk不会有前一个chunk和后一个chunk，所有本chunk没有下一个chunk的prev_size的空间可以“借”，所以对于直接mmap()分配内存的overhead为2*SIZE_SZ。
/* size field is or'ed with PREV_INUSE when previous adjacent chunk in use */#define PREV_INUSE 0x1/* extract inuse bit of previous chunk */#define prev_inuse(p) ((p)->size & PREV_INUSE)/* size field is or'ed with IS_MMAPPED if the chunk was obtained with mmap() */#define IS_MMAPPED 0x2/* check for mmap()'ed chunk */#define chunk_is_mmapped(p) ((p)->size & IS_MMAPPED)/* size field is or'ed with NON_MAIN_ARENA if the chunk was obtained from a non-main arena.This is only set immediately before handing the chunk to the user, if necessary.*/#define NON_MAIN_ARENA 0x4/* check for chunk from non-main arena */#define chunk_non_main_arena(p) ((p)->size & NON_MAIN_ARENA) chunk在分割时总是以地址对齐（默认是8字节，可以自由设置，但是8字节是最小值并且设置的值必须是2为底的幂函数值，即是alignment = 2^n，n为整数且n>=3）的方式来进行的，所以用chunk->size来存储本chunk块大小字节数的话，其末3bit位总是0，因此这三位可以用来存储其它信息，比如：
以第0位作为P状态位，标记前一chunk块是否在使用中，为1表示使用，为0表示空闲。
以第1位作为M状态位，标记本chunk块是否是使用mmap()直接从进程的mmap映射区域分配的，为1表示是，为0表示否。
以第2位作为A状态位，标记本chunk是否属于非主分配区，为1表示是，为0表示否。
/*Bits to mask off when extracting sizeNote: IS_MMAPPED is intentionally not masked off from size field inmacros for which mmapped chunks should never be seen. This shouldcause helpful core dumps to occur if it is tried by accident bypeople extending or adapting this malloc.*/#define SIZE_BITS (PREV_INUSE|IS_MMAPPED|NON_MAIN_ARENA)/* Get size, ignoring use bits */#define chunksize(p) ((p)->size & ~(SIZE_BITS))/* Ptr to next physical malloc_chunk. */#define next_chunk(p) ((mchunkptr)( ((char*)(p)) + ((p)->size & ~SIZE_BITS) ))/* Ptr to previous physical malloc_chunk */#define prev_chunk(p) ((mchunkptr)( ((char*)(p)) - ((p)->prev_size) ))/* Treat space at ptr + offset as a chunk */#define chunk_at_offset(p, s)((mchunkptr)(((char*)(p)) + (s))) prev_size字段虽然在当前chunk块结构体内，记录的却是前一个邻接chunk块的信息，这样做的好处就是我们通过本块chunk结构体就可以直接获取到前一chunk块的信息，从而方便做进一步的处理操作。相对的，当前chunk块的foot信息就存在于下一个邻接chunk块的结构体内。字段prev_size记录的什么信息呢？有两种情况：
1）如果前一个邻接chunk块空闲，那么当前chunk块结构体内的prev_size字段记录的是前一个邻接chunk块的大小。这就是由当前chunk指针获得前一个空闲chunk地址的依据。宏prev_chunk(p)就是依赖这个假设实现的。
2）如果前一个邻接chunk在使用中，则当前chunk的prev_size的空间被前一个chunk借用中，其中的值是前一个chunk的内存内容，对当前chunk没有任何意义。
字段size记录了本chunk的大小，无论下一个chunk是空闲状态或是被使用状态，都可以通过本chunk的地址加上本chunk的大小，得到下一个chunk的地址，由于size的低3个bit记录了控制信息，需要屏蔽掉这些控制信息，取出实际的size在进行计算下一个chunk地址，这是next_chunk(p)的实现原理。
宏chunksize(p)用于获得chunk的实际大小，需要屏蔽掉size中的控制信息。
宏chunk_at_offset(p, s)将p+s的地址强制看作一个chunk。
注意：按照边界标记法，可以有多个连续的并且正在被使用中的chunk块，但是不会有多个连续的空闲chunk块，因为连续的多个空闲chunk块一定会合并成一个大的空闲chunk块。
/* extract p's inuse bit */#define inuse(p)\((((mchunkptr)(((char*)(p))+((p)->size & ~SIZE_BITS)))->size) & PREV_INUSE)/* set/clear chunk as being inuse without otherwise disturbing */#define set_inuse(p)\((mchunkptr)(((char*)(p)) + ((p)->size & ~SIZE_BITS)))->size |= PREV_INUSE#define clear_inuse(p)\((mchunkptr)(((char*)(p)) + ((p)->size & ~SIZE_BITS)))->size &= ~(PREV_INUSE) 上面的这一组宏用于check/set/clear当前chunk使用标志位，有当前chunk的使用标志位存储在下一个chunk的size的第0 bit（P状态位），所以首先要获得下一个chunk的地址，然后check/set/clear下一个chunk的size域的第0 bit。
/* check/set/clear inuse bits in known places */#define inuse_bit_at_offset(p, s)\ (((mchunkptr)(((char*)(p)) + (s)))->size & PREV_INUSE)#define set_inuse_bit_at_offset(p, s)\ (((mchunkptr)(((char*)(p)) + (s)))->size |= PREV_INUSE)#define clear_inuse_bit_at_offset(p, s)\ (((mchunkptr)(((char*)(p)) + (s)))->size &= ~(PREV_INUSE))上面的三个宏用于check/set/clear指定chunk的size域中的使用标志位。/* Set size at head, without disturbing its use bit */#define set_head_size(p, s)((p)->size = (((p)->size & SIZE_BITS) | (s)))/* Set size/use field */#define set_head(p, s) ((p)->size = (s))/* Set size at footer (only when chunk is not in use) */#define set_foot(p, s) (((mchunkptr)((char*)(p) + (s)))->prev_size = (s)) 宏set_head_size(p, s)用于设置当前chunk p的size域并保留size域的控制信息。宏set_head(p, s) 用于设置当前chunk p的size域并忽略已有的size域控制信息。宏set_foot(p, s)用于设置当前chunk p的下一个chunk的prev_size为s，s为当前chunk的size，只有当chunk p为空闲时才能使用这个宏，当前chunk的foot的内存空间存在于下一个chunk，即下一个chunk的prev_size。
页:
[1]