TLSF内存算法

1、动态内存算法管理背景

项目中经常需要使用malloc进行动态内存分配，但是存在两个缺陷

  • 由于分配算法的复杂度，分配时间不确定
  • 在不断地申请、释放过程中，容易因为内存对齐产生碎片内存

这两个缺点在项目中华通常是不被允许的，因此需要一套较为合理且时间可确定的动态内存管理机制，目前有以下两种解决方案：

  • 动态内存堆管理算法（mmheap），用于不定长分配
  • 静态内存池管理算法（mmblk），用于定长分配

mmblk就是将一块内存划分为n个大小相同或者不同的块，用户可以动态的申请、释放，假设在使用动态内存，这种方式缺陷较为明显：用户可申请的最大块必须要小于mmblk中的最大块，并且内存利用率较低。

2、TLSF原理

TLSF 采用两级链表的形式来加快查找：

  • 第一级链表First List(简称fl)。第一层将空闲内存块的大小根据2的幂进行分类，如（16、32、64…），第一级的索引值fl[i]决定了这一级内存块的大小，范围为 [2^i,2^(i+1)] ;下图右侧区域
  • 第二级链表Second List(简称sl)。第二层链表在第一层的基础上，按照一定的间隔，线性分段，其范围应该在1-32对于32bit的处理器，第二级的索引值sl[i]一般为4或者5(根据经验定值，太小了对应的内存块很小，也没有意义)。

20241101-112428.png

例如上图分为fl和sl两级索引，FL_bitmap[]和SL_bitmaps[]的每个bit代表是否被使用：

  • fl分为8级
  • sl分为4级。这里说明下，图中sl分了8个小区，在计算sl时会将8个小区合为4个小区；

比如2的6次方这一段：

  • 第一级的FL_bitmap为110...1..0,次高位为1，次高位对应着2的6次方这一段，说明这一段有空闲块。
  • 第二级链表分为4个小区间[64,80]，[80,96]，[96,112]，[112，128]，每一级的链表都有一个bitmap用于标记对应的链表中是否有内存块。SL_bitmap位00000010，其对应着[80,96]这个区间有空闲块，即下面的89 Byte。

通过两级索引来查找或释放内存，tlsf_malloc与tlsf_free的所有操作花费是个时间常数，时间响应复杂度都为O(1)；

3、相关接口

https://github.com/mattconte/tlsf

我们所熟知的lvgl、liteos、uos、esp32-sdk中等都内置了tlsf

  • tlsf_create / tlsf_create_with_pool / tlsf_destroy:

    • tlsf_create: 初始化一个TLSF内存管理结构，使用提供的内存区域。
    • tlsf_create_with_pool: 初始化一个TLSF结构并创建一个内存池。
    • tlsf_destroy: 销毁TLSF结构，释放相关资源。

  • tlsf_get_pool:

    • 返回TLSF结构中管理的内存池。

  • tlsf_add_pool / tlsf_remove_pool:

    • tlsf_add_pool: 向TLSF结构中添加一个内存池。
    • tlsf_remove_pool: 从TLSF结构中移除一个内存池。

  • tlsf_malloc / tlsf_memalign / tlsf_memalign_offs / tlsf_malloc_addr / tlsf_realloc / tlsf_free:

    • tlsf_malloc: 分配指定大小的内存块。
    • tlsf_memalign: 分配对齐的内存块。
    • tlsf_memalign_offs: 分配带有偏移量的对齐内存块。
    • tlsf_malloc_addr: 分配内存块到指定地址（如果可能）。
    • tlsf_realloc: 调整已分配内存块的大小。
    • tlsf_free: 释放之前分配的内存块。

  • tlsf_block_size:

    • 返回内部块大小，而不是请求的原始大小。

  • tlsf_size / tlsf_pool_overhead / tlsf_alloc_overhead:

    • tlsf_size: 返回TLSF结构的大小。
    • tlsf_pool_overhead: 返回每个内存池的管理开销。
    • tlsf_alloc_overhead: 返回每个分配的内存块的管理开销。

  • tlsf_fit_size:

    • 根据传入的大小返回可分配的合适大小。

  • tlsf_walk_pool:

    • 遍历内存池中的内存块，执行用户定义的回调函数。

  • tlsf_check / tlsf_check_pool:

    • tlsf_check: 检查TLSF结构的内部一致性。
    • tlsf_check_pool: 检查特定内存池的内部一致性。

  • tlsf_check_hook:

    • 一个弱符号函数，用户可以实现此函数以在每个空闲内存块上执行特定检查。
文章目录