[原创]Mimalloc分析-Pwn-看雪-安全社区|安全招聘|kanxue.com

[原创]Mimalloc分析

发表于: 2023-8-4 13:10 15006

[原创]Mimalloc分析

c12en

2023-8-4 13:10

15006

在今年的HWS中遇到了一道堆与往常不同的是 c语言标准库中的malloc分配器更换成了mimalloc 于是打算来了解一下这个分配器查看一下这个分配器要如何利用

同时由于本人水平不足对于mimalloc源码的分析不到位很多地方也是一知半解只能起到一个面向pwn解题的分析

个人认为相比起用ptmalloc锻炼源码分析能力 mimalloc更加轻量化更能起到练手的一个效果

本小节用来指引如何在ubuntu中配置c语言调用mimalloc库如果没有需要自己编译题目来调试的就不需要看

Microsoft / Mimalloc：Mimalloc是一款紧凑的通用分配器，具有出色的性能。 (github.com)

首先git clone库到本地

随后创建一个目录用来存放构建后的项目

接着是比较麻烦的一步因为在执行完make install后官方文档是说会在/usr/include中安装头文件但是我实测是没有的所以我们需要手动把头文件复制到对应目录中

随后我们在使用gcc编译的时候在后面加上-lmimalloc 就可以成功编译了

如果需要用到pwndbg进行源码调试的需要编译.so文件的时候加上-DCMAKE_BUILD_TYPE=Debug 参照官方文档

对于每一个线程都有对应的内存用来管理线程我们称其为TLD

TLD主要由两个部分组成 segment和heap 我们先来介绍segment

这里的page就是实际分配给用户的内存而第一个page的大小会小于其他page 是因为segment头部用来存放了当前segment的信息占用了page的一部分空间

具体的成员我个人认为没有值得关注的后面如果遇到了再说这里先暂时记住segment的起始地址就是由于mi_malloc多分配的一块内存地址

heap重点的成员有三个前面两个是用于存放空闲的内存块

pages_free_direct用于小于1024的内存块

thread_delayed_free是用于满页释放的稍后会提及

通过pwndbg直接观察会发现实际上重要信息存放是位于segment heap就起到了一个索引的功能

索引到的结构我们称之为内存页其主要的成员就四个

红框圈起来的就是free链表蓝框圈起来的是local free链表

你会发现和常规的malloc不同并不是被申请过的内存块被释放后才会放入到链表中

当我们申请一个内存块后当前page剩下的会划分成内存块放入到free链表中

当申请过的内存块释放后会进入local free链表

随后我们来观察一下实际分配给用户的内存空间

此时我申请的是0x80大小的内存空间可以看到此时的free链表就已经成型了

我们来分析一下mi_malloc函数的源码

mimalloc通过多次跳转指向了_mi_heap_malloc_zero_ex函数我们来分析一下这个函数的源码

首先是对要申请chunk的大小进行了一个判断如果小于MI_SMALL_SIZE_MAX 就会跳转到samll chunk的申请同时进行了一个断言检测

MI_SMALL_SIZE_MAX的值定义在mimalloc.h中可以看到是1024(64位的情况下和指针字节大小有关系)

我们先来分析大于1024的内存分配逻辑

对于heap指针是否为空和线程id进行了检查

随后跳转到_mi_malloc_generic函数中进行内存分配 mi_track_malloc函数是用来将内存块的信息存储在track跟踪器中方便调试

接着使用了条件编译语句根据MI_STAT的值来决定是否记录更新heap的数据用于调试

mi_heap_stat_increase函数用于更新heap的统计数据 mi_usable_size函数用于计算内存块的实际大小(不是申请的大小)

如果MI_DEBUG的值设置为3 那么就会调用mi_assert_expensive函数检测条件是否成立这里的条件是调用mi_mem_is_zero来检测分配的内存块的前size个字节是否为0 MI_DEBUG的默认值为0 常规情况下我们并不用担心fake_chunk被检测出来

随后我们进入_mi_malloc_generic函数查看一下分析的主要逻辑

最开始对于heap是否初始化了进行一个检测如果没有初始化则进行初始化

随后调用_mi_deferred_free将本线程所有标记释放的内存块加入到延迟释放列表中随后批量释放这一操作是为了提高性能

调用_mi_heap_delayed_free_partial函数释放其他线程已经标记释放的内存块但跳过正在争用的内存块

接着调用mi_find_page函数寻找可用的page 如果没有找到则将空闲的内存块回收后再次查找

如果最后还是没有找到空闲的page 就说明空间不足触发断言输出报错

如果找到了可用的page 接着对于page的立即可用性进行检测以及检测page的大小是否满足size的需求这里的检测依赖的是page的xblock成员其存储的是当前page中的内存块大小

接着是性能优化的问题通过xblock和zero参数来决定用哪种办法来清零内存块的内容

开头对于xblock和page的free链表重新进行了检查

如果block为零则说明不存在对应大小的page页就调用_mi_malloc_generic函数来分配

接着自增了page的used成员同时更新free链表调用 mi_block_next函数来获取下一个内存块的地址并且进行了检测不能为0

随后根据zero来决定是否在内存块中填充数据方便用来检测内存越界等问题常规情况下都是\x00 但是如果开启了调试模式就会被填充成\xd0

下面的一大堆编译优化的都不影响我们内存分配所以这里忽略感兴趣的可以自行了解

这里我们留意一下开头的这句话

// Note: in debug mode the size includes MI_PADDING_SIZE and might have overflowed.

这就是当我们在调试模式下申请一个0x200的内存块实际分配到的是0x280的原因 MI_PADDING_SIZE在上一个小节中出现过其用来计算填充数据的字节检测是否存在内存溢出等

默认情况下MI_PADDING_SIZE是零

至于第一个if判断也用上了unlikely 因为几乎不会触发看一下MI_MEDIUM_OBJ_SIZE_MAX的值就知道了 64位的情况下MI_MEDIUM_PAGE_SIZE是128kib 也就是说MI_MEDIUM_OBJ_SIZE_MAX是32*1024字节一般来说size是肯定小于的

接着就是调用mi_find_free_page来查找空闲的page

首先通过mi_page_queue函数索引到对应大小的队列如果是首次申请该size 一般来说都是page都是0

申请过的话会索引到page1的内存页

接下来是debug模式才会触发的随机扩展目的是为了增加安全性这里不进行讨论

接着调用_mi_page_free_collect函数获取page

调用mi_page_immediate_available检测page是否可用如果可用则置零retire_expire 将page标识为不回收随后返回

如果page为零那么就调用mi_page_queue_find_free_ex进行下一步的查找

如果page为0 那么就会跳过while循环进入if分支调用_mi_heap_collect_retired函数

该函数就是遍历heap->page_retired_min到heap->page_retired_max之间的所有页面队列具体的这里先不讲

接着调用mi_page_fresh函数来初始化一个新的内存页面这里返回的值实际上就是位于segment首地址处的page info信息

如果page还是为0的话就再次调用mi_page_queue_find_free_ex函数

如果page在while循环中获取到了就设置page为不可回收

在最后进行了断言判断 page要么可利用要么为0

一开始首先收集thread_free中的内存块接下来收集free和local_free的内存块这里来分析一下逻辑

如果loacl_free链表不为空进入if分支检测free链表是否为空如果为空则将local_free链表移到free链表中同时没有做任何的检查也就意味着这里我们可以做到任意地址申请只需要想办法覆盖local_free链表

主要的逻辑还是比较简单的就是通过_mi_heap_get_free_small_page函数获取到适合small内存块的page 随后调用 _mi_page_malloc来申请内存块剩余的部分就是一些check和计数信息的更新

那么到这里我们可以做一个大概的总结首先进入mi_malloc函数对于要申请的内存块的size进行了判断如果小于0x400则进入 mi_heap_malloc_small_zero函数如果大于0x400则进入_mi_malloc_generic函数

如果是进入mi_heap_malloc_small_zero函数那么会调用 _mi_page_malloc来获取内存块

该函数通过page的free链表来获取相应的内存块

如果是_mi_malloc_generic函数那么会调用mi_find_page函数来寻找可用的page 该函数继续索引到mi_find_free_page函数来寻找page

根据是否开启了debug模式来调用_mi_page_free_collect函数如果开启了debug模式就不会预编译对应的else分支如果关闭了debug模式就会进入该函数一开始先根据force参数或者是mi_page_thread_free函数的返回值来决定是否要调用thread_free 接着检查local_free链表根据free链表是否为空来考虑是否要把local_free链表存放到free链表中

两种情况最后都是进入了mi_page_queue_find_free_ex函数遍历retire链表如果没有空闲的page就初始化一个新的page 如果初始化失败就再次调用mi_page_queue_find_free_ex函数

开始调用相关函数获取内存块对应的page和segment

接下来对于是否为同线程的内存块进行了判断如果是其他线程的内存块直接调用_mi_free_generic函数进行额外的情况

page->flags.full_aligned成员是用来查看该page是否需要内存对齐的如果申请的大小刚好等于页的大小那么内部就不用进行内存对齐释放也直接调用_mi_free_generic函数来进行

接着检查了是否存在double free的情况(这里吐槽一下我觉得这个check太仁慈了就算检测出来竟然也没有直接终止进程你说就输出个报错有啥用阿哥甚至你不开debug模式都不会进行double free检测)

mi_check_padding函数主要是调试模式下会出申请padding的内存用来存放字节供检测是否出现内存越界的情况没有开启debug模式的话直接就可以忽略掉这个函数

mi_stat_free是用来统计free内存块的信息

可以看到最后是更新了page的local_free链表而非free链表也就是说释放的内存块会优先进入local_free链表

接着根据page->used的值来判断page是否都是空闲内存块如果是则retire整个page

通过mi_block_nextx函数来获取内存块的next成员如果为0或者和内存块位于同一个page 那么就会进入mi_check_is_double_freex函数进行更加详细的check 如果不开启debug模式的话不会进行double free检测

通过遍历page的三个链表来查找内存块是否已经被释放过了

相对来说比较好绕过只要更改链表头的next成员就可以让链表索引不到已经被释放过的内存块

开始先进行了内存对齐的检测随后就是老一套的内存块信息的记录

随后调用_mi_free_block函数释放内存块

仍然是先进行了内存越界和double free的检测同时根据是否开启了debug模式来决定是否要调用memset函数清空内存块的内容

随后就是更新local_free链表和used的值接着检查是否要释放整个page 或者是当前page是否已经成为满页如果是满页则从满页列表中移除

总结一下释放实际上就是先进行没啥软用的double free检查然后根据要释放的内存块是否就是整个page 来决定要不要用_mi_free_generic函数来释放

释放完的话是加入到local_free链表并且used的值会减少相对来说逻辑还是比较简单的

在泄露libc基址上同ptmalloc不一样因为供用户申请的内存块就算被释放后也不会根据大小进入bin中从而在fd域或者bk域写入libc地址我们在获得一个内存块后只能获得其next域的下一个内存块的地址

而在获得内存块后我们就可以计算得到page的地址

page中就存放着libc地址经过偏移计算即可得到libc基址

问题在于如何构造任意写经过上面的源码分析我们可以得知内存块的申请是优先从free链表中获取的如果我们拥有溢出的机会修改下一个内存块的next域是不是就可以实现任意地址申请

同时还需要注意一点由于mimalloc内存地址的特殊性如果我们申请的内存块过小就会导致低字节处\x00 截断输出进而妨碍我们泄露内存块地址

可以看到此时free链表中已经写入了我们想要用来泄露libc地址的fake chunk

此时我们再次申请出同样size的两个内存块打印第二个内存块的内容就可以得到_mi_heap_main的地址从而泄露libc基址

同时要注意一下 libc基址和libmimalloc基址是不一样的

由于2.34以上的版本的tls结构体的偏移进行了随机化所以还需要进行爆破一个字节才能得到正确的libc的基址

回顾一下mi_malloc_generic函数

会发现其调用了这个函数当时我的分析是将标记释放的内存块加入到延迟释放链表中

而在ida的汇编代码中你可以看到其是通过call指令来调用的

偏偏这个地址还是可写的所以我们可以通过往这个地址写入system函数从而进行任意函数调用

但是很快你会发现我们并没有办法控制rdi寄存器

但是可以控制rdx寄存器联想ptmalloc我们是如何实现的orw 就会想到setcontext这一手法

需要的可以自行下载或者编译

链接: https://pan.baidu.com/s/1R6jhSAod4g8RQZT9tQSg_g?pwd=d193 提取码: d193

git clone https://github.com/microsoft/mimalloc.git

cmake ../mimalloc/
make
sudo make install 

cmake ../mimalloc/

make

sudo make install

sudo cp -r /home/chen/mimalloc/include/* /usr/include/

gcc -o test ./test.c -lmimalloc

extern inline void* _mi_heap_malloc_zero(mi_heap_t* heap, size_t size, bool zero) mi_attr_noexcept {

  return _mi_heap_malloc_zero_ex(heap, size, zero, 0);
}
 
mi_decl_nodiscard extern inline mi_decl_restrict void* mi_heap_malloc(mi_heap_t* heap, size_t size) mi_attr_noexcept {

  return _mi_heap_malloc_zero(heap, size, false);
}
 
mi_decl_nodiscard extern inline mi_decl_restrict void* mi_malloc(size_t size) mi_attr_noexcept {

  return mi_heap_malloc(mi_prim_get_default_heap(), size);
}

extern inline void* _mi_heap_malloc_zero(mi_heap_t* heap, size_t size, bool zero) mi_attr_noexcept {

return _mi_heap_malloc_zero_ex(heap, size, zero, 0);

}

mi_decl_nodiscard extern inline mi_decl_restrict void* mi_heap_malloc(mi_heap_t* heap, size_t size) mi_attr_noexcept {

return _mi_heap_malloc_zero(heap, size, false);

}

mi_decl_nodiscard extern inline mi_decl_restrict void* mi_malloc(size_t size) mi_attr_noexcept {

return mi_heap_malloc(mi_prim_get_default_heap(), size);

}

// The main allocation function

extern inline void* _mi_heap_malloc_zero_ex(mi_heap_t* heap, size_t size, bool zero, size_t huge_alignment) mi_attr_noexcept {

  if mi_likely(size <= MI_SMALL_SIZE_MAX) {

    mi_assert_internal(huge_alignment == 0);

    return mi_heap_malloc_small_zero(heap, size, zero);

  }

  else {

    mi_assert(heap!=NULL);

    mi_assert(heap->thread_id == 0 || heap->thread_id == _mi_thread_id());   // heaps are thread local

    void* const p = _mi_malloc_generic(heap, size + MI_PADDING_SIZE, zero, huge_alignment);  // note: size can overflow but it is detected in malloc_generic

    mi_track_malloc(p,size,zero);

    #if MI_STAT>1

    if (p != NULL) {

      if (!mi_heap_is_initialized(heap)) { heap = mi_prim_get_default_heap(); }

      mi_heap_stat_increase(heap, malloc, mi_usable_size(p));

    }

    #endif

    #if MI_DEBUG>3

    if (p != NULL && zero) {

      mi_assert_expensive(mi_mem_is_zero(p, size));

    }

    #endif

    return p;

  }
}

// The main allocation function

extern inline void* _mi_heap_malloc_zero_ex(mi_heap_t* heap, size_t size, bool zero, size_t huge_alignment) mi_attr_noexcept {

if mi_likely(size <= MI_SMALL_SIZE_MAX) {

mi_assert_internal(huge_alignment == 0);

return mi_heap_malloc_small_zero(heap, size, zero);

}

else {

mi_assert(heap!=NULL);

mi_assert(heap->thread_id == 0 || heap->thread_id == _mi_thread_id()); // heaps are thread local

void* const p = _mi_malloc_generic(heap, size + MI_PADDING_SIZE, zero, huge_alignment); // note: size can overflow but it is detected in malloc_generic

mi_track_malloc(p,size,zero);

#if MI_STAT>1

if (p != NULL) {

if (!mi_heap_is_initialized(heap)) { heap = mi_prim_get_default_heap(); }

mi_heap_stat_increase(heap, malloc, mi_usable_size(p));

}

#endif

#if MI_DEBUG>3

if (p != NULL && zero) {

mi_assert_expensive(mi_mem_is_zero(p, size));

}

#endif

return p;

}

#define MI_SMALL_WSIZE_MAX (128)

#define MI_SMALL_SIZE_MAX (MI_SMALL_WSIZE_MAXsizeof(void))

#define MI_SMALL_WSIZE_MAX (128)

#define MI_SMALL_SIZE_MAX (MI_SMALL_WSIZE_MAXsizeof(void))

void* _mi_malloc_generic(mi_heap_t* heap, size_t size, bool zero, size_t huge_alignment) mi_attr_noexcept
{

  mi_assert_internal(heap != NULL);
 
  // initialize if necessary

  if mi_unlikely(!mi_heap_is_initialized(heap)) {

    heap = mi_heap_get_default(); // calls mi_thread_init 

    if mi_unlikely(!mi_heap_is_initialized(heap)) { return NULL; }

  }

  mi_assert_internal(mi_heap_is_initialized(heap));
 
  // call potential deferred free routines

  _mi_deferred_free(heap, false);
 
  // free delayed frees from other threads (but skip contended ones)

  _mi_heap_delayed_free_partial(heap);
 
  // find (or allocate) a page of the right size

  mi_page_t* page = mi_find_page(heap, size, huge_alignment);

  if mi_unlikely(page == NULL) { // first time out of memory, try to collect and retry the allocation once more

    mi_heap_collect(heap, true /* force */);

    page = mi_find_page(heap, size, huge_alignment);

  }
 
  if mi_unlikely(page == NULL) { // out of memory

    const size_t req_size = size - MI_PADDING_SIZE;  // correct for padding_size in case of an overflow on `size`

    _mi_error_message(ENOMEM, "unable to allocate memory (%zu bytes)\n", req_size);

    return NULL;

  }
 
  mi_assert_internal(mi_page_immediate_available(page));

  mi_assert_internal(mi_page_block_size(page) >= size);
 
  // and try again, this time succeeding! (i.e. this should never recurse through _mi_page_malloc)

  if mi_unlikely(zero && page->xblock_size == 0) {

    // note: we cannot call _mi_page_malloc with zeroing for huge blocks; we zero it afterwards in that case.

    void* p = _mi_page_malloc(heap, page, size, false);

    mi_assert_internal(p != NULL);

    _mi_memzero_aligned(p, mi_page_usable_block_size(page));

    return p;

  }

  else {

    return _mi_page_malloc(heap, page, size, zero);

  }
}

void* _mi_malloc_generic(mi_heap_t* heap, size_t size, bool zero, size_t huge_alignment) mi_attr_noexcept

{

mi_assert_internal(heap != NULL);

// initialize if necessary

if mi_unlikely(!mi_heap_is_initialized(heap)) {

heap = mi_heap_get_default(); // calls mi_thread_init

if mi_unlikely(!mi_heap_is_initialized(heap)) { return NULL; }

}

mi_assert_internal(mi_heap_is_initialized(heap));

// call potential deferred free routines

_mi_deferred_free(heap, false);

// free delayed frees from other threads (but skip contended ones)

_mi_heap_delayed_free_partial(heap);

// find (or allocate) a page of the right size

mi_page_t* page = mi_find_page(heap, size, huge_alignment);

if mi_unlikely(page == NULL) { // first time out of memory, try to collect and retry the allocation once more

mi_heap_collect(heap, true /* force */);

page = mi_find_page(heap, size, huge_alignment);

}

if mi_unlikely(page == NULL) { // out of memory

const size_t req_size = size - MI_PADDING_SIZE; // correct for padding_size in case of an overflow on `size`

_mi_error_message(ENOMEM, "unable to allocate memory (%zu bytes)\n", req_size);

return NULL;

}

mi_assert_internal(mi_page_immediate_available(page));

mi_assert_internal(mi_page_block_size(page) >= size);

// and try again, this time succeeding! (i.e. this should never recurse through _mi_page_malloc)

if mi_unlikely(zero && page->xblock_size == 0) {

// note: we cannot call _mi_page_malloc with zeroing for huge blocks; we zero it afterwards in that case.

void* p = _mi_page_malloc(heap, page, size, false);

mi_assert_internal(p != NULL);

_mi_memzero_aligned(p, mi_page_usable_block_size(page));

return p;

}

else {

return _mi_page_malloc(heap, page, size, zero);

}

extern inline void* _mi_page_malloc(mi_heap_t* heap, mi_page_t* page, size_t size, bool zero) mi_attr_noexcept {

  mi_assert_internal(page->xblock_size==0||mi_page_block_size(page) >= size);

  mi_block_t* const block = page->free;

  if mi_unlikely(block == NULL) {

    return _mi_malloc_generic(heap, size, zero, 0);

  }

  mi_assert_internal(block != NULL && _mi_ptr_page(block) == page);

  // pop from the free list

  page->used++;

  page->free = mi_block_next(page, block);

  mi_assert_internal(page->free == NULL || _mi_ptr_page(page->free) == page);

  #if MI_DEBUG>3

  if (page->free_is_zero) {

    mi_assert_expensive(mi_mem_is_zero(block+1,size - sizeof(*block)));

  }

  #endif
 
  // allow use of the block internally

  // note: when tracking we need to avoid ever touching the MI_PADDING since

  // that is tracked by valgrind etc. as non-accessible (through the red-zone, see `mimalloc/track.h`)

  mi_track_mem_undefined(block, mi_page_usable_block_size(page));
 
  // zero the block? note: we need to zero the full block size (issue #63)

  if mi_unlikely(zero) {

    mi_assert_internal(page->xblock_size != 0); // do not call with zero'ing for huge blocks (see _mi_malloc_generic)

    mi_assert_internal(page->xblock_size >= MI_PADDING_SIZE);

    if (page->free_is_zero) {

      block->next = 0;

      mi_track_mem_defined(block, page->xblock_size - MI_PADDING_SIZE);

    }

    else {

      _mi_memzero_aligned(block, page->xblock_size - MI_PADDING_SIZE);

    }    

  }
 
#if (MI_DEBUG>0) && !MI_TRACK_ENABLED && !MI_TSAN

  if (!zero && !mi_page_is_huge(page)) {

    memset(block, MI_DEBUG_UNINIT, mi_page_usable_block_size(page));

  }
#elif (MI_SECURE!=0)

  if (!zero) { block->next = 0; } // don't leak internal data
#endif
 
#if (MI_STAT>0)

  const size_t bsize = mi_page_usable_block_size(page);

  if (bsize <= MI_MEDIUM_OBJ_SIZE_MAX) {

    mi_heap_stat_increase(heap, normal, bsize);

    mi_heap_stat_counter_increase(heap, normal_count, 1);
#if (MI_STAT>1)

    const size_t bin = _mi_bin(bsize);

    mi_heap_stat_increase(heap, normal_bins[bin], 1);
#endif

  }
#endif
 
#if MI_PADDING // && !MI_TRACK_ENABLED

  mi_padding_t* const padding = (mi_padding_t*)((uint8_t*)block + mi_page_usable_block_size(page));

  ptrdiff_t delta = ((uint8_t*)padding - (uint8_t*)block - (size - MI_PADDING_SIZE));

  #if (MI_DEBUG>=2)

  mi_assert_internal(delta >= 0 && mi_page_usable_block_size(page) >= (size - MI_PADDING_SIZE + delta));

  #endif

  mi_track_mem_defined(padding,sizeof(mi_padding_t));  // note: re-enable since mi_page_usable_block_size may set noaccess

  padding->canary = (uint32_t)(mi_ptr_encode(page,block,page->keys));

  padding->delta  = (uint32_t)(delta);

  #if MI_PADDING_CHECK

  if (!mi_page_is_huge(page)) {

    uint8_t* fill = (uint8_t*)padding - delta;

    const size_t maxpad = (delta > MI_MAX_ALIGN_SIZE ? MI_MAX_ALIGN_SIZE : delta); // set at most N initial padding bytes

    for (size_t i = 0; i < maxpad; i++) { fill[i] = MI_DEBUG_PADDING; }

  }

  #endif
#endif
 
  return block;
}

extern inline void* _mi_page_malloc(mi_heap_t* heap, mi_page_t* page, size_t size, bool zero) mi_attr_noexcept {

mi_assert_internal(page->xblock_size==0||mi_page_block_size(page) >= size);

mi_block_t* const block = page->free;

if mi_unlikely(block == NULL) {

return _mi_malloc_generic(heap, size, zero, 0);

}

mi_assert_internal(block != NULL && _mi_ptr_page(block) == page);

// pop from the free list

page->used++;

page->free = mi_block_next(page, block);

mi_assert_internal(page->free == NULL || _mi_ptr_page(page->free) == page);

#if MI_DEBUG>3

if (page->free_is_zero) {

mi_assert_expensive(mi_mem_is_zero(block+1,size - sizeof(*block)));

}

#endif

// allow use of the block internally

// note: when tracking we need to avoid ever touching the MI_PADDING since

// that is tracked by valgrind etc. as non-accessible (through the red-zone, see `mimalloc/track.h`)

mi_track_mem_undefined(block, mi_page_usable_block_size(page));

// zero the block? note: we need to zero the full block size (issue #63)

if mi_unlikely(zero) {

mi_assert_internal(page->xblock_size != 0); // do not call with zero'ing for huge blocks (see _mi_malloc_generic)

mi_assert_internal(page->xblock_size >= MI_PADDING_SIZE);

if (page->free_is_zero) {

block->next = 0;

mi_track_mem_defined(block, page->xblock_size - MI_PADDING_SIZE);

}

else {

_mi_memzero_aligned(block, page->xblock_size - MI_PADDING_SIZE);

}

#if (MI_DEBUG>0) && !MI_TRACK_ENABLED && !MI_TSAN

if (!zero && !mi_page_is_huge(page)) {

memset(block, MI_DEBUG_UNINIT, mi_page_usable_block_size(page));

}

#elif (MI_SECURE!=0)

if (!zero) { block->next = 0; } // don't leak internal data

#endif

#if (MI_STAT>0)

const size_t bsize = mi_page_usable_block_size(page);

if (bsize <= MI_MEDIUM_OBJ_SIZE_MAX) {

mi_heap_stat_increase(heap, normal, bsize);

mi_heap_stat_counter_increase(heap, normal_count, 1);

#if (MI_STAT>1)

const size_t bin = _mi_bin(bsize);

mi_heap_stat_increase(heap, normal_bins[bin], 1);

#endif

}

#endif

#if MI_PADDING // && !MI_TRACK_ENABLED

mi_padding_t* const padding = (mi_padding_t*)((uint8_t*)block + mi_page_usable_block_size(page));

ptrdiff_t delta = ((uint8_t*)padding - (uint8_t*)block - (size - MI_PADDING_SIZE));

#if (MI_DEBUG>=2)

mi_assert_internal(delta >= 0 && mi_page_usable_block_size(page) >= (size - MI_PADDING_SIZE + delta));

#endif

mi_track_mem_defined(padding,sizeof(mi_padding_t)); // note: re-enable since mi_page_usable_block_size may set noaccess

padding->canary = (uint32_t)(mi_ptr_encode(page,block,page->keys));

padding->delta = (uint32_t)(delta);

#if MI_PADDING_CHECK

if (!mi_page_is_huge(page)) {

uint8_t* fill = (uint8_t*)padding - delta;

const size_t maxpad = (delta > MI_MAX_ALIGN_SIZE ? MI_MAX_ALIGN_SIZE : delta); // set at most N initial padding bytes

for (size_t i = 0; i < maxpad; i++) { fill[i] = MI_DEBUG_PADDING; }

}

#endif

return block;

}

// Allocate a page
// Note: in debug mode the size includes MI_PADDING_SIZE and might have overflowed.

static mi_page_t* mi_find_page(mi_heap_t* heap, size_t size, size_t huge_alignment) mi_attr_noexcept {

  // huge allocation?

  const size_t req_size = size - MI_PADDING_SIZE;  // correct for padding_size in case of an overflow on `size`  

  if mi_unlikely(req_size > (MI_MEDIUM_OBJ_SIZE_MAX - MI_PADDING_SIZE) || huge_alignment > 0) {

    if mi_unlikely(req_size > PTRDIFF_MAX) {  // we don't allocate more than PTRDIFF_MAX (see <https://sourceware.org/ml/libc-announce/2019/msg00001.html>)

      _mi_error_message(EOVERFLOW, "allocation request is too large (%zu bytes)\n", req_size);

      return NULL;

    }

    else {

      return mi_large_huge_page_alloc(heap,size,huge_alignment);

    }

  }

  else {

    // otherwise find a page with free blocks in our size segregated queues

    #if MI_PADDING

    mi_assert_internal(size >= MI_PADDING_SIZE); 

    #endif

    return mi_find_free_page(heap, size);

  }
}

// Allocate a page

// Note: in debug mode the size includes MI_PADDING_SIZE and might have overflowed.

static mi_page_t* mi_find_page(mi_heap_t* heap, size_t size, size_t huge_alignment) mi_attr_noexcept {

// huge allocation?

const size_t req_size = size - MI_PADDING_SIZE; // correct for padding_size in case of an overflow on `size`

if mi_unlikely(req_size > (MI_MEDIUM_OBJ_SIZE_MAX - MI_PADDING_SIZE) || huge_alignment > 0) {

if mi_unlikely(req_size > PTRDIFF_MAX) { // we don't allocate more than PTRDIFF_MAX (see <https://sourceware.org/ml/libc-announce/2019/msg00001.html>)

_mi_error_message(EOVERFLOW, "allocation request is too large (%zu bytes)\n", req_size);

return NULL;

}

else {

return mi_large_huge_page_alloc(heap,size,huge_alignment);

}

else {

// otherwise find a page with free blocks in our size segregated queues

#if MI_PADDING

mi_assert_internal(size >= MI_PADDING_SIZE);

#endif

return mi_find_free_page(heap, size);

}

#define MI_MEDIUM_OBJ_SIZE_MAX (MI_MEDIUM_PAGE_SIZE/4) // 128KiB on 64-bit

// Find a page with free blocks of `size`.

static inline mi_page_t* mi_find_free_page(mi_heap_t* heap, size_t size) {

  mi_page_queue_t* pq = mi_page_queue(heap,size);

  mi_page_t* page = pq->first;

  if (page != NULL) {

   #if (MI_SECURE>=3) // in secure mode, we extend half the time to increase randomness

    if (page->capacity < page->reserved && ((_mi_heap_random_next(heap) & 1) == 1)) {

      mi_page_extend_free(heap, page, heap->tld);

      mi_assert_internal(mi_page_immediate_available(page));

    }

    else

   #endif

    {

      _mi_page_free_collect(page,false);

    }
 
    if (mi_page_immediate_available(page)) {

      page->retire_expire = 0;

      return page; // fast path

    }

  }

  return mi_page_queue_find_free_ex(heap, pq, true);
}

// Find a page with free blocks of `size`.

static inline mi_page_t* mi_find_free_page(mi_heap_t* heap, size_t size) {

mi_page_queue_t* pq = mi_page_queue(heap,size);

mi_page_t* page = pq->first;

if (page != NULL) {

#if (MI_SECURE>=3) // in secure mode, we extend half the time to increase randomness

if (page->capacity < page->reserved && ((_mi_heap_random_next(heap) & 1) == 1)) {

mi_page_extend_free(heap, page, heap->tld);

mi_assert_internal(mi_page_immediate_available(page));

}

else

#endif

{

_mi_page_free_collect(page,false);

}

if (mi_page_immediate_available(page)) {

page->retire_expire = 0;

return page; // fast path

}

return mi_page_queue_find_free_ex(heap, pq, true);

}

static mi_page_t* mi_page_queue_find_free_ex(mi_heap_t* heap, mi_page_queue_t* pq, bool first_try)
{

  // search through the pages in "next fit" order

  #if MI_STAT

  size_t count = 0;

  #endif

  mi_page_t* page = pq->first;

  while (page != NULL)

  {

    mi_page_t* next = page->next; // remember next

    #if MI_STAT    

    count++;

    #endif
 
    // 0. collect freed blocks by us and other threads

    _mi_page_free_collect(page, false);
 
    // 1. if the page contains free blocks, we are done

    if (mi_page_immediate_available(page)) {

      break;  // pick this one

    }
 
    // 2. Try to extend

    if (page->capacity < page->reserved) {

      mi_page_extend_free(heap, page, heap->tld);

      mi_assert_internal(mi_page_immediate_available(page));

      break;

    }
 
    // 3. If the page is completely full, move it to the `mi_pages_full`

    // queue so we don't visit long-lived pages too often.

    mi_assert_internal(!mi_page_is_in_full(page) && !mi_page_immediate_available(page));

    mi_page_to_full(page, pq);
 
    page = next;

  } // for each page
 
  mi_heap_stat_counter_increase(heap, searches, count);
 
  if (page == NULL) {

    _mi_heap_collect_retired(heap, false); // perhaps make a page available?

    page = mi_page_fresh(heap, pq);

    if (page == NULL && first_try) {

      // out-of-memory _or_ an abandoned page with free blocks was reclaimed, try once again

      page = mi_page_queue_find_free_ex(heap, pq, false);

    }

  }

  else {

    mi_assert(pq->first == page);

    page->retire_expire = 0;

  }

  mi_assert_internal(page == NULL || mi_page_immediate_available(page));

  return page;
}

static mi_page_t* mi_page_queue_find_free_ex(mi_heap_t* heap, mi_page_queue_t* pq, bool first_try)

{

// search through the pages in "next fit" order

#if MI_STAT

size_t count = 0;

#endif

mi_page_t* page = pq->first;

while (page != NULL)

{

mi_page_t* next = page->next; // remember next

#if MI_STAT

count++;

#endif

登录后可查看完整内容

[招生]科锐逆向工程师培训(2024年11月15日实地，远程教学同时开班, 第51期)

收藏・7

免费・7

支持

最新回复 (1)
IceCliffs 雪币： 220 能力值： ( LV1，RANK：0 ) 在线值：发帖 0 回帖 1 粉丝 0 关注私信	IceCliffs 2 楼 2023-8-5 19:13 0
	游客登录 \| 注册方可回帖回帖表情雪币赚取及消费高级回复

c12en

发帖

回帖

RANK

关注

私信

他的文章

[原创]Mimalloc分析 15007

关于我们

联系我们

企业服务

看雪公众号