Intel TBB malloc 内存分配器

Created on August 28, 2024

2024   ·   TBB   Cpp   Performance   HPC   ·   TBB   Cpp

1. TBB Malloc 介绍

1.1. TBB Malloc 使用入门

有两种方式使用TBB Malloc：Run-Time替换，Link-Time替换。替换的函数(routines)包括：

routines Linux MacOS Windows
global C++ new / delete √ √ √
C库：malloc / calloc / realloc / free √ √ √
C库(C11)：aligned_alloc √ - -
POSIX：posix_memalign √ √ -

Run-Time替换方法：

平台 替换方法
Linux export LD_PRELOAD=$TBBROOT/lib/intel64/gcc4.8/libtbbmalloc_proxy.so.2
MacOS export DYLD_INSERT_LIBRARIES=$TBBROOT/lib/intel64/gcc4.8/libtbbmalloc_proxy.dylib

Link-Time替换方法：

平台 替换方法
Linux & MacOS -L$TBBROOT/lib/intel64/gcc4.8 -ltbbmalloc_proxy
Windows tbbmalloc_proxy.lib /INCLUDE:"__TBB_malloc_proxy"

Link-Time替换，需要添加编译flags。不添加这些编译flags，可能导致malloc等这些函数被内联为汇编，即失去了符号，也就没有办法替换了。需要添加的flags如下：

Linux/MacOS平台下，添加如下编译flags（适用于Linux/MacOS）：

-fno-builtin-malloc
-fno-builtin-calloc
-fno-builtin-realloc
-fno-builtin-free

Windows平台下，icc编译器添加如下编译flags：

- /Qfno-builtin-malloc
- /Qfno-builtin-calloc
- /Qfno-builtin-realloc
- /Qfno-builtin-free

替换Proxy入口代码文件为src/tbbmalloc_proxy/proxy.cpp。

1.1.1. 直接使用TBB malloc（Compile-Time）

Allocation Routine Deallocation Routine 对应系统运行时库
scalable_malloc, scalable_calloc, scalable_realloc scalable_free C Standard library
scalable_aligned_malloc, scalable_aligned_realloc scalable_aligned_free Microsoft C runtime

与C++ STL对应的allocator：

table_tbb_stl_allocator

一个简单使用示例：

#include <vector>
#include <algorithm>
#include <execution>
#include <tbb/scalable_allocator.h>

std::vector<int, tbb::scalable_allocator<int>> v{…};
std::sort(std::execution::par, v.begin(), v.end());

1.1.2. Huge Pages

TBB malloc支持Huge Pages，可以通过设置环境变量TBB_MALLOC_USE_HUGE_PAGES来启用，或者在代码中设置：

scalable_allocation_mode( TBBMALLOC_USE_HUGE_PAGES,1);

Huage Pages可以减少malloc调用，减少TLB Miss，提高性能，尤其是在分配大块内存时。

1.1.3. memory_pool_allocator

TBB malloc提供了一个memory_pool_allocator，它通过预先分配一大块内存，避免TBB Malloc模块的管理开销。管理器需要查找空闲块、分割块、记录元数据（这块内存多大、是否在用等）。

其约束为，每次分配的大小为固定的P，因为它是通过简单的基于 P 取模的偏移量获取内存块的。适用于作为STL容器的分配器。一个示例如下：

#define TBB_PREVIEW_MEMORY_POOL 1
#include "oneapi/tbb/memory_pool.h"
#include <list>

int main() {
    oneapi::tbb::memory_pool<std::allocator<int>> my_pool;

    typedef oneapi::tbb::memory_pool_allocator<int> pool_allocator_t;
    std::list<int, pool_allocator_t> my_list(pool_allocator_t{my_pool});

    my_list.emplace_back(1);
}

当memory_pool中内存用尽之后，将向底层Alloc申请内存进行扩容。新增的内存切分成若干FreeBlock，并添加到pool内部的空闲链表。扩容大小由extMemPool->granularity决定，扩容的内存可能来自其他线程丢弃的的orphaned blocks，也可能来自底层Alloc分配的内存。其类声明如下：

//! Thread-safe growable pool allocator for variable-size requests
template <typename Alloc>
class memory_pool : public pool_base

另外，定义了一个fixed_pool，内存池耗尽之后不会扩展。

1.1.4. 局部替代 new & delete

当某些模块需要自定义allocator时，可以通过局部替代new和delete来实现：

#include <tbb/parallel_for.h>
#include <tbb/tbb_allocator.h>

// No retry loop because we assume that
// scalable_malloc does all it takes to allocate the memory,
// so calling it repeatedly will not improve the situation at all

// No use of std::new handler because it cannot bedone in portable and
// thread-safe way We throw std::bad alloc() when scalable mallocreturns NULL
// (we return NULL if it is a no-throw implementation)

void *operator new(size_t size) throw(std::bad_alloc) {
  if (size == 0) size = 1;
  if (void *ptr = scalable_malloc(size))
    return ptr;
  throw std::bad_alloc();
}

void *operator new[](size_t size) throw(std::bad_alloc) {
  return operator new(size);
}

void *operator new(size_t size, const std::nothrow_t &) throw {
  if (size == 0) size = 1;
  if (void *ptr = scalable_malloc(size))
    return ptr;
  return NULL;
}

void *operator new[](size_t size, const std::nothrow_t &) throw {
  return operator new(size, std::nothrow);
}

void operator delete(void *ptr) throw() {
  if (ptr != 0) scalable_free(ptr);
}

void operator delete[](void *ptr) throw() { operator delete(ptr); }

void operator delete(void *ptr, const std::nothrow_t &) throw() {
  if (ptr != 0) scalable_free(ptr);
}

void operator delete[](void *ptr, const std::nothrow_t &) throw() {
  operator delete(ptr, std::nothrow);
}

int main(int argc, char **argv) {
  const size_t size = 1000;
  const size_t chunk = 100;

  // scalable malloc will be called to allocate
  // the memory for this array of integers
  int *p = new int[size];

  tbb::parallel_for(size_t{0}, size, [=](size_t chunk) {
    // scalable_malloc will be called to allocate the memory for this
    // array of integers
    int *p = new int[chunk];

    // scalable_free will be called to deallocate the memory for this
    // array of integers
    delete[] p;
  });

  return 0;
}

代码示例来自Pro TBB第七章：Scalable Memory Allocation。

1.2. TBB Malloc 架构分析

TBB Malloc基于前后端两层分层架构：分为Frontend和Backend两层。Frontend负责处理基于线程的内存分配请求，Backend负责物理内存分配和全局内存管理（线程分配及回收）。

每个线程都有一个自己独立的本地缓存（local cache）。当线程请求内存时，首先检查本地缓存中分配，如果有空闲块，则直接返回本地的空闲块，这个查询及分配操作是无锁的。另外，本地维护的空闲链表，被分类为不同大小的内存块（size class），每个size class维护一个空闲链表，比如8字节、16字节、2KB等。

Frontend代码路径：src/tbbmalloc/frontend.cpp。

Backend负责物理内存分配/释放、处理碎片。当某个线程的缓存空了，会向Backend请求内存块，当线程本地的缓存太多时，会将多余的内存块返回给Backend。

由于Backend是共享的，所有访问Backend需要加锁。另外，Huge Pages的支持也是在Backend实现的。

Backend代码路径：src/tbbmalloc/backend.cpp。

这套前端/后端的分层架构，特点为：

  • Thread-Local Storage (TLS): 利用 TLS 存储每个线程的分配器状态，避免全局锁。
  • Cross-Thread Recycling: 如果线程 A 释放了内存，而线程 B 需要内存，分配器需要能安全地将 A 释放的块转交给 B。TBB malloc 使用一种延迟回收或集中式回收的机制来处理这种跨线程转移，同时尽量减少锁竞争。
  • Object Caching: 释放的内存不会立即还给 OS，而是保留在缓存中，以便下次快速重用。

tbbmalloc相关的部分高层代码路径： include/oneapi/tbb/memory_pool.h src/tbb/allocator.cpp src/tbbmalloc_proxy/proxy.cpp。

1.2.1. Linux系统符号替换

ELF 格式中，符号有三种绑定类型（st_bind）：

类型 说明
STB_GLOBAL 强符号，全局可见，重复定义时链接报错
STB_WEAK 弱符号，可被强符号覆盖，未覆盖时使用弱版本
STB_LOCAL 局部符号，仅文件内可见

dlopen以及动态链接器只加载找到的第一个强符号，在proxy.cpp中，定义这些符号（部分定义截图）：

tbbmalloc_proxy_strong_symbol

并调用dlsym(RTLD_NEXT, ...)保留系统原始的symbol，用作初始化阶段bootstrap调用：

inline void InitOrigPointers()
{
    // race is OK here, as different threads found same functions
    if (!origFuncSearched.load(std::memory_order_acquire)) {
        orig_free = dlsym(RTLD_NEXT, "free");
        orig_realloc = dlsym(RTLD_NEXT, "realloc");
        orig_msize = dlsym(RTLD_NEXT, "malloc_usable_size");
        orig_libc_free = dlsym(RTLD_NEXT, "__libc_free");
        orig_libc_realloc = dlsym(RTLD_NEXT, "__libc_realloc");

        origFuncSearched.store(true, std::memory_order_release);
    }
}

另外，使用__attribute__((alias))将libc库中的__libc_*等函数替换为对应的routines：

tbbmalloc_symbol_alias_replace

alias(“sym”) 让当前符号成为 sym 的别名，两个名字指向同一段代码。即将__libc_free等符号截获并替换为free等符号。

A. 资料



    Enjoy Reading This Article?

    Here are some more articles you might like to read next:

  • al-folio 模板定制修改总结
  • al-folio 本地部署记录（Ubuntu 24.04）
  • C++ Traits
  • 道格拉斯-普克算法(Douglas–Peucker algorithm)
  • CMake支持库收集