Glibc-ptmalloc

比赛的第一分钟和最后一分钟要保保持一样的心态~

在Unix和类Unix系统中，glibc（GNU C Library）扮演着至关重要的角色。它作为系统调用和库函数的桥梁，使得程序员能够方便地利用底层系统资源。ptmalloc 是 malloc 在 GNU C Library（glibc）中的一个具体实现。

32 位模式下进程内存经典布局

着重关注两个区：heap（堆区） memory mapping（内存映射区）

brk函数其实就是在heap分配空间，在ptmalloc的设计中有start_brk和brk两个标志，他们两个的差值标记着堆区的大小。一开始这两个值是相同的，但是随着ptmalloc去调用brk函数，brk标记不断向高地址区域偏移，标记着heap堆区被分配出去了。
mmap函数则是在memory mapping区域分配空间，memory mapping区域除了我们常知道的映射动态库对象或者文件，其空间还可以被mmap映射至物理内存。

分配区

在 Doug Lea 实现的内存分配器中只有一个主分配区（main arena），每次分配内存都必须对主分配区加锁，分配完成后释放锁，在 SMP 多线程环境下，对主分配区的锁的争用很激烈，严重影响了 malloc 的分配效率。于是 Wolfram Gloger 在 Doug Lea 的基础上改进使得Glibc 的 malloc 可以支持多线程，增加了非主分配区（non main arena）支持，主分配区与非主分配区用环形链表进行管理。每一个分配区利用互斥锁（mutex）使线程对于该分配区的访问互斥。【有点分段锁的味道】

每个进程只有一个主分配区，但可能存在多个非主分配区，ptmalloc 根据系统对分配区的争用情况动态增加非主分配区的数量，分配区的数量一旦增加，就不会再减少了。**主分配区可以访问进程的 heap 区域和 mmap 映射区域，也就是说主分配区可以使用 sbrk 和 mmap向操作系统申请虚拟内存。而非主分配区只能访问进程的 mmap 映射区域，非主分配区每次使用 mmap()向操作系统“发”HEAP_MAX_SIZE（32 位系统上默认为 1MB，64 位系统默认为 64MB）大小的虚拟内存，**当用户向非主分配区请求分配内存时再切割成小块“零售”出去，毕竟系统调用是相对低效的，直接从用户空间分配内存快多了。所以 ptmalloc 在必要的情况下才会调用 mmap()函数向操作系统申请虚拟内存。

主分配区可以访问 heap 区域，如果用户不调用 brk()或是 sbrk()函数，分配程序就可以保证分配到连续的虚拟地址空间，因为每个进程只有一个主分配区使用 sbrk()分配 heap 区域的虚拟内存。内核对 brk 的实现可以看着是 mmap 的一个精简版，相对高效一些。如果主分配区的内存是通过 mmap()向系统分配的，当 free 该内存时，主分配区会直接调用 munmap()将该内存归还给系统。

**当某一线程需要调用 malloc()分配内存空间时，该线程先查看线程私有变量中是否已经存在一个分配区，如果存在，尝试对该分配区加锁，如果加锁成功，使用该分配区分配内存，如果失败，该线程搜索循环链表试图获得一个没有加锁的分配区。如果所有的分配区都已经加锁，那么 malloc()会开辟一个新的分配区，把该分配区加入到全局分配区循环链表并加锁，然后使用该分配区进行分配内存操作。**在释放操作中，线程同样试图获得待释放内存块所在分配区的锁，如果该分配区正在被别的线程使用，则需要等待直到其他线程释放该分配区的互斥锁之后才可以进行释放操作。申请小块内存时会产生很多内存碎片，ptmalloc 在整理时也需要对分配区做加锁操作。每个加锁操作大概需要 5～10 个 cpu 指令，而且程序线程很多的情况下，锁等待的时间就会延长，导致 malloc 性能下降。一次加锁操作需要消耗 100ns 左右，正是锁的缘故，导致 ptmalloc在多线程竞争情况下性能远远落后于 tcmalloc。最新版的 ptmalloc 对锁进行了优化，加入了PER_THREAD 和 ATOMIC_FASTBINS 优化，但默认编译不会启用该优化，这两个对锁的优化应该能够提升多线程内存的分配的效率。

代码角度理解

主分配区（Main Arena）

主分配区是唯一的，它与进程的主线程相关联。主分配区使用进程的堆（heap）来分配内存，并且在进程启动时创建，始终存在。以下是主分配区的一些关键代码实现细节：

malloc_state 结构体：

这是主分配区的核心数据结构，包含了所有用于管理内存的字段，例如 bins 数组、top 指针（指向当前未分配的内存区域）、last_remainder 指针（指向最后一个分割的内存块）等。

示例代码（简化）：

struct malloc_state {
    binmap_t binmap;          // 用于快速查找非空 bin 的位图
    malloc_chunk *top;        // 指向 top chunk
    malloc_chunk *last_remainder; // 指向最后一个分割的内存块
    malloc_chunk *bins[NBINS]; // bins 数组
    // 其他字段...
};

全局变量：
- 主分配区通常是一个全局变量，例如在 glibc 中，主分配区可以通过 main_arena 变量访问。
- 示例代码（简化）：
  1
  static malloc_state main_arena;
初始化：
- 主分配区在进程启动时初始化，通常在 ptmalloc 的初始化函数中完成。
- 示例代码（简化）：
  1
  2
  3
  4
  void ptmalloc_init() {
  // 初始化主分配区
  init_arena(&main_arena);
  }

从分配区（Thread Arena）

从分配区是为每个线程独立创建的分配区，它允许线程独立地管理内存，从而减少锁竞争，提高并发性能。以下是从分配区的一些关键代码实现细节：

线程局部存储（Thread Local Storage, TLS）：
- 每个线程可以通过线程局部存储（TLS）来访问自己的分配区。
  1
  __thread malloc_state *thread_arena;

创建从分配区：

当一个线程第一次调用 malloc 时，如果还没有分配区，ptmalloc 会为该线程创建一个新的从分配区。

示例代码（简化）：

static malloc_state *arena_get(mstate *ar_ptr, size_t size) {
    malloc_state *a;
    // 尝试获取现有的分配区或创建新的分配区
    a = get_free_list(); // 从空闲列表中获取分配区
    if (!a) {
        a = _int_new_arena(size); // 创建新的分配区
    }
    *ar_ptr = a;
    return a;
}

内存分配和释放：

当线程请求内存时，ptmalloc 会从相应的分配区中查找合适的内存块。如果找到合适的内存块，则将其从 bins 中移除并返回给调用者。

示例代码（简化）：

void *malloc(size_t size) {
    mstate ar_ptr;
    void *victim;
    // 获取当前线程的分配区
    arena_get(&ar_ptr, size);
    // 从分配区中查找合适的内存块
    victim = _int_malloc(ar_ptr, size);
    if (!victim) {
        // 处理内存分配失败的情况
        return 0;
    }
    return victim;
}

通过这些代码片段，可以看到主分配区和从分配区的基本结构和操作。

关键数据结构

在 ptmalloc 内存分配器中，unsorted bin、Fast Bins、top chunk、bins 和 mmaped chunk 是用于管理内存块的关键数据结构。它们之间的关系和作用如下：

unsorted bin

unsorted bin 是一个双向链表，用于临时存储最近释放的内存块。这些内存块在下次分配请求时会被重新整理并放入相应的 bins 中。

Fast Bins

Fast Bins 是一个单链表数组，用于存储较小的空闲内存块（通常小于64或128字节）。Fast Bins 中的内存块不会被合并，这样可以快速地进行分配和释放。

top chunk

top chunk 是分配区中未分配的内存区域。当 bins 中没有合适的内存块时，ptmalloc 会从 top chunk 中分割出所需的内存块。

bins

bins 是一个双向链表数组，用于存储具有相同大小的空闲内存块。bins 分为 small bins 和 large bins，分别用于存储较小的和较大的内存块。

mmaped chunk

mmaped chunk 是通过 mmap 系统调用分配的内存块。当请求的内存大小超过某个阈值时，ptmalloc 会使用 mmap 来分配内存，而不是从堆中分配。

代码解读

以下是一个简化的代码示例，展示了这些数据结构之间的关系和作用：

struct malloc_chunk {
    size_t prev_size;  // 前一个内存块的大小
    size_t size;       // 当前内存块的大小
    malloc_chunk *fd;  // 指向链表中下一个内存块
    malloc_chunk *bk;  // 指向链表中前一个内存块
};

struct malloc_state {
    malloc_chunk *top;        // 指向 top chunk
    malloc_chunk *fastbinsY[NFASTBINS]; // Fast Bins 数组
    malloc_chunk *bins[NBINS]; // bins 数组
    // 其他字段...
};

void *malloc(size_t size) {
    malloc_state *ar_ptr = get_arena(); // 获取当前线程的分配区
    size_t nb = request2size(size);     // 将请求的大小转换为实际分配的大小

    // 尝试从 Fast Bins 中分配内存
    if (nb <= get_max_fast()) {
        idx = fastbin_index(nb);
        fb = &fastbinsY[idx];
        victim = *fb;
        if (victim != NULL) {
            *fb = victim->fd;
            return chunk2mem(victim);
        }
    }

    // 尝试从 unsorted bin 中分配内存
    if (unsorted_chunks(ar_ptr) != NULL) {
        victim = unsorted_chunks(ar_ptr);
        unsorted_chunks(ar_ptr) = victim->fd;
        if (victim->size == nb) {
            return chunk2mem(victim);
        }
    }

    // 尝试从 bins 中分配内存
    idx = bin_index(nb);
    bin = bin_at(ar_ptr, idx);
    victim = first(bin);
    if (victim != bin) {
        unlink(victim, bk, fd);
        return chunk2mem(victim);
    }

    // 尝试从 top chunk 中分配内存
    victim = ar_ptr->top;
    size = chunksize(victim);
    if ((unsigned long)(size) >= (unsigned long)(nb + MINSIZE)) {
        remainder_size = size - nb;
        remainder = chunk_at_offset(victim, nb);
        ar_ptr->top = remainder;
        return chunk2mem(victim);
    }

    // 使用 mmap 分配内存
    if (nb & MMAP_THRESHOLD) {
        char *mem = (char *)mmap(0, nb, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
        if (mem == MAP_FAILED) return 0;
        return mem;
    }

    return 0;
}

代码解释

获取分配区：
- get_arena() 函数获取当前线程的分配区。
Fast Bins：
- 如果请求的大小小于 get_max_fast() 返回的值，尝试从 Fast Bins 中分配内存。
- fastbin_index(nb) 计算 Fast Bins 的索引，fastbinsY[idx] 获取相应的 Fast Bin。
- 如果找到合适的内存块，将其从 Fast Bin 中移除并返回。
unsorted bin：
- 如果 unsorted bin 不为空，尝试从中分配内存。
- 如果找到合适大小的内存块，直接返回。
bins：
- 计算请求大小的 bin 索引，尝试从相应的 bin 中分配内存。
- 如果找到合适的内存块，将其从 bin 中移除并返回。
top chunk：
- 如果 top chunk 的大小足够，从 top chunk 中分割出所需的内存块，并更新 top chunk 的指针。
mmaped chunk：
- 如果请求的大小超过某个阈值，使用 mmap 系统调用分配内存。

分配释放策略

ptmalloc 的分配策略

获取分配区锁，加锁成功则使用该分配区分配内存，否则就遍历分配区的环形链表。如果链表中没有空闲的，就开辟一个新的分配区，把其加入线程私有实例并且加入到环形链表。
将用户请求的字节向上对齐到bins中的最近字节。
如果小于64B就在fast bin中分配内存，如果大于再去判断是否小于512B，如果小于就去small bin中分配大小，如果大于就说明此时分配的是大内存。
首先会将fast bin中的chunk进行合并，然后链接至unsorted bin，再将其链接到相应的bin中。
然后去large bins中进行寻找，如果够用结束，不够下一步。
这个时候就需要判断top chunk是否够用，不够用下一步。
有两种选择，判断分配的字节大小是否大于等于mmap分配阈值，如果小于根据分配区去选择brk还是mmap去增加top chunk的大小；如果大于就直接调用mmap去映射。

ptmalloc 的释放策略