目的

• 熟悉堆内存布局
• 了解glibc(ptmalloc2)堆管理机制

目录

• 内存管理函数
  • 虚拟内存布局
  • mmap&munmap
  • brk&sbrk
  • malloc&free
  • 应用程序动态申请内存
• glibc堆管理机制
  • heap_info
  • malloc_state
    • malloc_state成员
    • bin
  • malloc_chunk
  • consolidate
    • consolidate forward
    • consolidate backward
  • unlink

内存管理函数

虚拟内存布局

图片来源：sploitfun

mmap&munmap

系统调用

void *mmap(void *addr, size_t length, int prot, int flags,int fd, off_t offset);
/*
    addr: NONE|addr
        NONE:操作系统选择创建虚拟内存区域的位置
        somewhere:操作系统从addr附近页边界处创建虚拟内存区域(linux)
    length:申请的字节数
    prot:PROT_NONE|PROT_EXEC|PROT_READ|PROT_WRITE|PROT_NONE
        PROT_EXEC:页可执行
        PROT_READ:页可读
        PROT_WRITE:页可写
        PROT_NONE:页不可访问
    flags:MAP_SHARED|MAP_PRIVATE|MAP_ANONYMOUS|...
        MAP_SHARED:虚拟内存区域可共享
        MAP_PRIVATE:私有虚拟内存区域
        MAP_ANONYMOUS:虚拟内存区域初始化为0，如果同时被设置为MAP_ANONYMOUS，fd应为-1
    fd:文件描述符，指定要映射的对象的一个连续片段，长度为length字节
    offset:文件开始的偏移处开始映射

*/

int munmap(void *addr, size_t length);
/*
    删除从addr开始共length字节的虚拟内存区域，再次引用该区域将导致段错误
*/

brk&sbrk

系统调用

int brk(void *addr);
void *sbrk(intptr_t increment);
/*
DESCRIPTION
    brk()  and  sbrk()  change the location of the program break, which defines the end of the process's data segment (i.e., the program break is the first location after the end of the uninitialized data segment).  Increasing the program break has  the effect of allocating memory to the process; decreasing the break deallocates memory.

    brk()  sets the end of the data segment to the value specified by addr, when that value is reasonable, the system has enough memory, and the process does not exceed its maximum data size (see setrlimit(2)).

    sbrk() increments the program's data space by increment bytes.  Calling sbrk() with an increment of 0 can be  used  to  find the current location of the program break.
*/

brk()参数为一个地址，把该地址作为堆底。
sbrk()参数为相对堆底的偏移，并把偏移后函数的返回值作为堆底。
sbrk(0)返回当前堆底地址。

brk()和mmap()申请虚拟空间时候的不同：

• brk(): 改变进程堆的大小；mmap(): 为文件创建一个内存映射(或匿名内存映射)，扩大进程的地址空间。
• brk()分配的虚拟内存在random brk offset的上方（高地址一端，对应图中program break brk处），random brk offset的低地址端紧挨着bss段。mmap()分配的虚拟内存的地址则位于某一处区域，不特意指定并不会在random brk offset附近。

一个例子：

/* sbrk and brk example */
#include 
#include 
#include 

int main()
{
        void *curr_brk, *tmp_brk = NULL;

        printf("Welcome to sbrk example:%d\n", getpid());

        /* sbrk(0) gives current program break location */
        tmp_brk = curr_brk = sbrk(0);
        printf("Program Break Location1:%p\n", curr_brk);
        getchar();

        /* brk(addr) increments/decrements program break location */
        brk(curr_brk+4096);

        curr_brk = sbrk(0);
        printf("Program break Location2:%p\n", curr_brk);
        getchar();

        brk(tmp_brk);

        curr_brk = sbrk(0);
        printf("Program Break Location3:%p\n", curr_brk);
        getchar();

        return 0;
}

malloc&free

非系统调用

malloc()是通过调用brk()和mmap()实现的，当

• 分配内存大于 128k ，调用 mmap() ，在文件映射区域中分配匿名虚存空间
• 与bss段相邻的区域没有足够空间来申请新的内存区域
• 非main thread申请新的内存区域

调用的是mmap()，否则brk(old_brk+length)来申请新的内存区域。

free()是通过brk()和munmap()系统调用实现的。

应用程序动态申请内存

allocator的使用可以避免频繁的系统调用操作，同时还有以下特性:

• 处理任意请求序列
• 立即相应请求
• 只使用堆
• 对齐块
• 不修改已分配的块

一个例子：

/* Per thread arena example. */
#include 
#include 
#include 
#include 
#include 
void* threadFunc(void* arg) {
        printf("Before malloc in thread 1\n");
        getchar();
        char* addr = (char*) malloc(1000);
        printf("After malloc and before free in thread 1\n");
        getchar();
        free(addr);
        printf("After free in thread 1\n");
        getchar();
}
int main() {
        pthread_t t1;
        void* s;
        int ret;
        char* addr;
        printf("Welcome to per thread arena example::%d\n",getpid());
        printf("Before malloc in main thread\n");
        getchar();
        addr = (char*) malloc(1000);
        printf("After malloc and before free in main thread\n");
        getchar();
        free(addr);
        printf("After free in main thread\n");
        getchar();
        ret = pthread_create(&t1, NULL, threadFunc, NULL);
        if(ret)
        {
                printf("Thread creation error\n");
                return -1;
        }
        ret = pthread_join(t1, &s);
        if(ret)
        {
                printf("Thread join error\n");
                return -1;
        }
        return 0;
}

glibc堆管理机制

heap_info——heap header

/* A heap is a single contiguous memory region holding (coalesceable)
   malloc_chunks.  It is allocated with mmap() and always starts at an
   address aligned to HEAP_MAX_SIZE.  */

typedef struct _heap_info
{
  mstate ar_ptr; /* Arena for this heap. */
  struct _heap_info *prev; /* Previous heap. */
  size_t size;   /* Current size in bytes. */
  size_t mprotect_size; /* Size in bytes that has been mprotected
                           PROT_READ|PROT_WRITE.  */
  /* Make sure the following data is properly aligned, particularly
     that sizeof (heap_info) + 2 * SIZE_SZ is a multiple of
     MALLOC_ALIGNMENT. */
  char pad[-6 * SIZE_SZ & MALLOC_ALIGN_MASK];
} heap_info;

来源:glibc2.27/malloc/arena.c

malloc_state——arena header

struct malloc_state
{
  /* Serialize access.  */
  mutex_t mutex;

  /* Flags (formerly in max_fast).  */
  int flags;

#if THREAD_STATS
  /* Statistics for locking.  Only used if THREAD_STATS is defined.  */
  long stat_lock_direct, stat_lock_loop, stat_lock_wait;
#endif

  /* Fastbins */
  mfastbinptr fastbinsY[NFASTBINS];

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

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

  /* Normal bins packed as described above */
  mchunkptr bins[NBINS * 2 - 2];

  /* Bitmap of bins */
  unsigned int binmap[BINMAPSIZE];

  /* Linked list */
  struct malloc_state *next;

  /* Linked list for free arenas.  */
  struct malloc_state *next_free;

  /* Memory allocated from the system in this arena.  */
  INTERNAL_SIZE_T system_mem;
  INTERNAL_SIZE_T max_system_mem;
};
/*
    mutex：用于支持多线程的互斥锁
    fastbinsY[FASTBINS]：fastbin指针数组
    top：指向top chunk指针
    last_remainder：remainder
    bins[NBINS * 2 - 2]：bins指针数组


*/

来源:glibc2.27/malloc/malloc.c

malloc_state成员

• top chunk是arena高地址处的一个chunk，当所有bin都无法满足分配要求时便判断top chunk的大小是否符合分配要求，若满足则拆分top chunk为新分配的空间和新的top chunk；否则，进行堆拓展。
• last remainder chunk是当请求一个small chunk而small bins和unsorted bins均无符合要求的chunk时由binmaps遍历bin寻找最合适的chunk，切分该chunk时如有剩余则作为新chunk加入unsorted bin，此时便成为last remainder chunk。当再次申请small chunk且small bins无合适chunk则搜索unsorted bin，若恰好last remainder chunk满足分配要求则对其切分，若有剩余那么剩余部分作为新的unsorted bins中的last remainder chunk。

bin

• fastbins
  • 16~64B(for 32bit);32~128B(for 64bit)
  • LIFO;单链表
  • 不合并
• bins
  • 循环双链表
  • bin1 - unsorted bin
    • free small chunk和free large chunk暂时添加到unsorted bin
  • bin2 to bin63 - small bin
    • 16,24,32,…,508 bytes(for 32bit),每个bin的chunk大小相同
  • bin64 to bin126 - large bin
    • >=512 bytes(for 32bit)

malloc_chunk——chunk header

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;
};


/*

chunk8字节对齐

allocated chunk:

    chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of previous chunk, if unallocated (P clear)  |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of chunk, in bytes                     |A|M|P|
      mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             User data starts here...                          .
            .                                                               .
            .             (malloc_usable_size() bytes)                      .
            .                                                               |
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             (size of chunk, but used for application data)    |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of next chunk, in bytes                |A|0|1|
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

        A:NON_MAIN_ARENA
        M:IS_MAPPED
        P:PRE_INUSE

freed chunk:

    chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of previous chunk, if unallocated (P clear)  |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    `head:' |             Size of chunk, in bytes                     |A|0|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                           |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of next chunk, in bytes                |A|0|0|
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
*/          

来源:glibc2.27/malloc/malloc.c

consolidate

针对non mapped chunks

consolidate forward

    if (nextchunk != av->top) {
      nextinuse = inuse_bit_at_offset(nextchunk, nextsize);

      if (!nextinuse) {
        size += nextsize;
        unlink(av, nextchunk, bck, fwd);
      } else
        clear_inuse_bit_at_offset(nextchunk, 0);

      first_unsorted = unsorted_bin->fd;
      unsorted_bin->fd = p;
      first_unsorted->bk = p;

      if (!in_smallbin_range (size)) {
        p->fd_nextsize = NULL;
        p->bk_nextsize = NULL;
      }

      set_head(p, size | PREV_INUSE);
      p->bk = unsorted_bin;
      p->fd = first_unsorted;
      set_foot(p, size);
    }

    else {
      size += nextsize;
      set_head(p, size | PREV_INUSE);
      av->top = p;
    }

• if PREV_INUSE is set:
  • p->next is a top chunk:
    1. p->size += nextsize
    2. 当前chunk p成为新top chunk
  • p->next is not a top chunk:
    • p->next->next->PRE_INUSE is set:
      1. p->size += p->next->size
      2. unlink
      3. move into unsorted bins

consolidate backward

    if (!prev_inuse(p)) {
      prevsize = prev_size (p);
      size += prevsize;
      p = chunk_at_offset(p, -((long) prevsize));
      unlink(av, p, bck, fwd);
    }

• if PREV_INUSE is set:
  1. p->size += p->prev->size
  2. unlink
  3. move into unsorted bins

unlink

/* Take a chunk off a bin list */
#define unlink(AV, P, BK, FD) {                                            \
    if (__builtin_expect (chunksize(P) != prev_size (next_chunk(P)), 0))      \
      malloc_printerr ("corrupted size vs. prev_size");               \
    FD = P->fd;                                   \
    BK = P->bk;                                   \

    if (__builtin_expect (FD->bk != P || BK->fd != P, 0))             \
      malloc_printerr ("corrupted double-linked list");               \


    else {                                    \
        FD->bk = BK;                                  \
        BK->fd = FD;                                  \
        if (!in_smallbin_range (chunksize_nomask (P))                 \
            && __builtin_expect (P->fd_nextsize != NULL, 0)) {            \
        if (__builtin_expect (P->fd_nextsize->bk_nextsize != P, 0)        \
        || __builtin_expect (P->bk_nextsize->fd_nextsize != P, 0))    \
          malloc_printerr ("corrupted double-linked list (not small)");   \
            if (FD->fd_nextsize == NULL) {                    \
                if (P->fd_nextsize == P)                      \
                  FD->fd_nextsize = FD->bk_nextsize = FD;             \
                else {                                \
                    FD->fd_nextsize = P->fd_nextsize;                 \
                    FD->bk_nextsize = P->bk_nextsize;                 \
                    P->fd_nextsize->bk_nextsize = FD;                 \
                    P->bk_nextsize->fd_nextsize = FD;                 \
                  }                               \
              } else {                                \
                P->fd_nextsize->bk_nextsize = P->bk_nextsize;             \
                P->bk_nextsize->fd_nextsize = P->fd_nextsize;             \
              }                                   \
          }                                   \
      }                                       \
}

其中：

• 3~4行对p->next->size和p->size进行一致性检查
• 8~9和17~19行对即将unlink的chunk进行防伪造检查

参考：

• How The Kernel Manages Your Memory
• heap overflow using unlink
• Linux堆内存管理深入分析 (上)
• Linux堆内存管理深入分析 (下)
• CSAPP #9.9动态内存管理
• glibc2.27/malloc.c & arena.c