Dynamic Memory Allocation

基本概念

动态内存分配器维护着一个进程的虚拟内存区域，称为堆（heap）。应用程序使用它在运行时操纵虚拟内存。

分配器将堆视为一组不同大小的块（block）的集合来维护。每个块就是一个连续的虚拟内存片（chunk），要么是已分配的，要么是空闲的。

malloc

C 标准库提供了一个称为 malloc 的显示分配器。程序通过调用 malloc 函数来从堆中分配块。

sbrk 函数，分配器在内部使用它来增长和缩小堆。所以当分配器需要更多内存时，它调用 sbrk 来获得额外的虚拟内存，然后那部分被添加到堆中。

Allocation Example

约束

分配器在很多不同的约束下工作。

应用程序

  • 应用程序可以将已分配块和空闲块任意组合，因此，无法预测应用程序请求的内容；

  • free 必须使用来自之前调用 malloc 时返回的指针；

分配器

  • 无法控制分配块的大小或数量；

  • 如果应用程序调用 malloc，malloc 必须立即响应；

  • 必须从可用内存中分配块，一旦分配了一个块，那么该块就属于那个应用程序，而 malloc 不能触及它。这意味着分配器不能移动块，比如分配器无法将已分配的块放到一起以达到压缩块的目的；

  • 字节对齐，32 位系统需要 8 字节对齐，64 位系统需要 16 字节对齐。

Performance Goal

提高吞吐量，提升内存利用率，而这两个性能目标通常是相互冲突的。

吞吐率：单位时间所有的请求数量。

有很多方式来描述一个分配器使用堆的效率如何。在我们的经验中，最有用的标准是峰值利用率（peak utilization）。

有效载荷：应用程序调用 malloc 以请求一定大小的块，该块称为有效载荷。因此，使用 10 字节的参数调用 malloc ，我们请求的 10 字节称为有效载荷，该块中的其他所有内容都是开销。

在我们运行一系列请求之后，聚合有效载荷是当前分配的块中所有有效载荷的总和。在完美的分配器中，聚合有效负载等于内存量，等于所有已分配块的总大小，因为没有开销。

现在假设堆是单调非递减的。这是简化的假设，在真正的 malloc 中不是这样的。

前 k + 1 个请求的峰值利用率，表示为 Uk，可以通过下式得到：Uk=maxi<=kPi / Hk 。那么，分配器的目标就是在整个序列中使峰值利用率 Un-1 最大化。

碎片

如果有效负载小于块大小，则会发生内部碎片。

外部碎片发生在堆中有足够的内存时，但是没有一个可以满足特定请求的空闲块。

Implementation Issues

Knowing How Much to Free

Keeping Track of Free Blocks

Implicit Free List

块的有效负载必须从 16 字节边界开始，所以一开始的方式是在堆的开头创建这个未使用的字。最后有一个特殊的结局块。

隐式空闲链表的优点是简单。显著的缺点是任何操作的开销，例如放置分配的块，要求对空闲链表进行搜索，该搜索所需时间与堆中已分配块和空闲块的总数呈线性关系。

很重要的一点就是意识到系统对齐要求和分配器对块格式的选择会对分配器上的最小块大小有强制的要求。没有已分配块或者空闲块可以比这个最小值还小。例如，如果我们假设一个双字的对齐要求，那么每个块的大小都必须是双字（8字节）的倍数。因此，就导致最小的块大小为两个字：一个字作头，另一个字维持对齐要求。即使应用只请求一字节，分配器也仍然需要创建一个两字的块。

Implicit List: Data Structures

Block declaration

typedef uint64_t word_t;

typedef struct block
{
    word_t header;
    unsigned char payload[0];    // Zero length array
} block_t;

Getting payload from block pointer

// block_t *block
return (void*)(block->payload);

Getting header from payload

return (block_t *)((unsigned char*)bp 
                    - offsetof(block_t, payload));

C function offsetof(struct, member) returns offset of member within struct.

Implicit List: Header access

Getting allocated bit from header

return header & 0x1;

Getting size from header

return header & ~0xfL;

Initializing header

// block_t *block
block->header = size | alloc;

Implicit List: Traversing list

Find the next block

static block_t *find_next(block_t *block)
{
    return (block_t *)((unsigned char*) block 
                        + get_size(block));
}

Implicit List: Finding a Free Block

首次适配的优点是它趋向于将大的空闲块保留在链表的后面。缺点是它趋向于在靠近链表起始处留下小空闲块的“碎片”，这就增加了对较大块的搜索时间。

下一次适配源于这样一个想法：如果我们上一次在某个空闲块里已经发现了一个匹配，那么很可能下一次我们也能在这个剩余块中发现匹配。下一次适配比首次适配运行起来明显要快一些，尤其是当链表的前面布满了许多小的碎片时。然而，一些研究表明，下一次适配的内存利用率要比首次适配低得多。

研究还表明最佳适配比首次适配和下一次适配的内存利用率都要高一些。然而，在简单空闲链表组织结构中，比如隐式空闲链表中，使用最佳适配的缺点是它要求对堆进行彻底的搜索。在后面，我们将看到更加精细复杂的分离式空闲链表组织，它接近于最佳适配策略，不需要进行彻底的堆搜索。

Implicit List: Allocating in Free Block

static void split_block(block_t *block, size_t asize) {
    size_t block_size = get_size(block);
    if((block_size - asize) >= min_block_size) {
        write_header(block, asize, true);
        block_t *block_next = find_next(block);
        write_heaer(block_next, block_size - asize, false);
    }
}

Implicit List: Freeing a Block

当分配器释放一个已分配块时，可能有其他空闲块与这个新释放的空闲块相邻。这些邻接的空闲块可能引起一种现象，叫做假碎片（fault fragmentation），就是有许多可用的空闲块被切割成为小的、无法使用的空闲块。为了解决假碎片问题，任何实际的分配器都必须合并相邻的空闲块，这个过程称为合并（coalescing）。这就出现了一个重要的策略决定，那就是何时执行合并。分配器可以选择立即合并（immediate coalescing），也就是在每次一个块被释放时，就合并所有的相邻块。或者它也可以选择推迟合并（deferred coalescing），也就是等到某个稍晚的时候再合并空闲块。例如，分配器可以推迟合并，直到某个分配请求失败，然后扫描整个堆，合并所有的空闲块。

立即合并很简单明了，可以在常数时间内执行完成，但是对于某些请求模式，这种方式会产生一种形式的抖动，块会反复地合并，然后马上分割。在对分配器的讨论中，我们会假设使用立即合并，但是你应该了解，快速的分配器通常会选择某种形式的推迟合并。

Implicit List: Coalescing 合并

当前的情况，无法很好的检测前一个 block。这意味着每次调用 free 需要的时间都与堆的大小成线性关系。

Implicit List: Bidirectional Coalescing

Implementation with Footers

const size_t dsize = 2 * sizeof(word_t);

static word_t* header_to_footer(block_t* block)
{
    size_t asize = get_size(block);
    return (word_t*)(block->payload + asize - dsize);
}

static word_t *find_prev_footer(block_t *block)
{
    return &(block->header) - 1;
}

Splitting Free Block: Full Version

static void split_block(block_t *block, size_t asize) {
    size_t block_size = get_size(block);
    
    if((block_size - asize) >= min_block_size) {
        write_header(block, asize, true);
        write_footer(block, asize, true);
        block_t* block_next = find_next(block);
        write_header(block_next, block_size - asize, false);
        write_footer(block_next, block_size - asize, false);
    }
}

Constant Time Coalescing

Case 1

Case 2

Case 3

Case 4

Top-Level Malloc Code

/*
* round_up(n, m) = m * ((n + m - 1) / m);
*/

const size_t dsize = 2 * sizeof(word_t);

void *mm_malloc(size_t size)
{
    size_t asize = round_up(size + dsize, dsize);
    
    block_t *block = find_fit(asize);
    
    if(block == NULL)
        return NULL;
        
    size_t block_size = get_size(block);
    write_header(block, block_size, true);
    write_footer(block, block_size, true);
    
    split_block(block, asize);
    
    return header_to_payload(block);
}
void mm_free(void *bp)
{
    block_t *block = payload_to_header(bp);
    size_t size = get_size(block);
    
    write_header(block, size, false);
    write_footer(block, size, false);
    
    coalesce_block(block);
}

No Boundary Tag for Allocated Blocks

Case 1

Case 2

Case 3

Case 4