rtthread学习笔记系列(9) -- 内存管理

https://github.com/wdfk-prog/RT-Thread-Study

9. 内存管理

https://www.rt-thread.org/document/site/#/rt-thread-version/rt-thread-standard/programming-manual/memory/memory

9.1 初始化

1.rt_system_heap_init

• 对堆开始地址与结束地址进行内存对齐
• 在ART-PI中将所有剩余ROM划分给堆使用
• 断言堆设置是否正常
• 根据配置的内存策略 使用 _MEM_INIT
• 初始化多线程争用锁

9.2 小内存管理算法

• 小内存算法在分配内存的时候，随着内存碎片的增多，分配速度会越来越慢，当总的内存太大的时候，内存碎片的数量可能会更多，此时这种算法就会变得不再适用。
• 小内存管理算法主要针对系统资源比较少，一般用于小于 2MB 内存空间的系统
• 每个内存对象的起始12字节不可使用,设置为堆系统的配置

//这是一个掩码，用于将内存地址的最低位清零。在 RTT 的内存管理中，内存块的地址的最低位被用作标记该内存块是否被使用。#define MEM_MASK             0xfffffffe//这个宏用于标记内存块 _mem 为已使用。它首先使用 MEM_MASK 将 _mem 的最低位清零，然后将最低位设置为 1，表示该内存块已被使用。#define MEM_USED(_mem)       ((((rt_base_t)(_mem)) & MEM_MASK) |0x1)#define MEM_FREED(_mem)      ((((rt_base_t)(_mem)) & MEM_MASK) |0x0)//这将使用 ~MEM_MASK（即 MEM_MASK 的按位取反）与 pool_ptr 进行按位与操作。由于 MEM_MASK 的最低位是 0，所以 ~MEM_MASK 的最低位是 1。这意味着这个操作将提取出 pool_ptr 的最低位，即内存块的使用状态标记。#define MEM_ISUSED(_mem)   \
(((rt_base_t)(((struct rt_small_mem_item *)(_mem))->pool_ptr)) & (~MEM_MASK))

9.2.1 rt_smem_init

1. 内存对齐
2. 内存大小计算;至少需要满足两个 struct rt_small_mem_item结构体;因为堆起始与结束各有一个结构体

/* 初始化堆起始位置内存对象*/struct rt_small_mem_item *mem;mem        = (struct rt_small_mem_item *)small_mem->heap_ptr;//堆起始位置初始化mem->pool_ptr = MEM_FREED(small_mem);//小内存堆对象地址 设置为释放mem->next  = small_mem->mem_size_aligned + SIZEOF_STRUCT_MEM;//下一个内存对象设置到堆结尾内存对象mem->prev  = 0;//上一个对象为空//写入堆起始位置分配的内存名称rt_smem_setname(mem, "INIT");/* 堆大小 */small_mem->mem_size_aligned = mem_size;/* 指向堆的起始地址 */small_mem->heap_ptr = (rt_uint8_t *)begin_align;/* 初始化指向堆开始的最低空闲指针*/small_mem->lfree = (struct rt_small_mem_item *)small_mem->heap_ptr;//初始化堆结束内存对象性small_mem->heap_end        = (struct rt_small_mem_item *)&small_mem->heap_ptr[mem->next];//初始化设置为堆起始地址的下一个内存对象为堆结束地址small_mem->heap_end->pool_ptr = MEM_USED(small_mem);//设置为使用small_mem->heap_end->next  = small_mem->mem_size_aligned + SIZEOF_STRUCT_MEM;//下一个设置为自身small_mem->heap_end->prev  = small_mem->mem_size_aligned + SIZEOF_STRUCT_MEM;//上一个设置为自身//写入堆结束位置分配的内存名称rt_smem_setname(small_mem->heap_end, "INIT");

9.2.2 alloc分配

• 使用_MEM_MALLOC,操作 system_heap

rt_size_t ptr;//从当前的空闲内存块开始，遍历整个内存池，直到找到一个足够大的内存块或者遍历完整个内存池for (ptr = (rt_uint8_t *)small_mem->lfree - small_mem->heap_ptr;ptr <= small_mem->mem_size_aligned - size;ptr = ((struct rt_small_mem_item *)&small_mem->heap_ptr[ptr])->next){//查找未使用的内存且满足大小的区域if ((!MEM_ISUSED(mem)) && (mem->next - (ptr + SIZEOF_STRUCT_MEM)) >= size){//获取当前内存块的地址。mem = (struct rt_small_mem_item *)&small_mem->heap_ptr[ptr];//* 如果当前内存块足够大，那么可以将其分割成两个部分，一个用于分配，另一个保留为新的空闲内存块 */if (mem->next - (ptr + SIZEOF_STRUCT_MEM) >=(size + SIZEOF_STRUCT_MEM + MIN_SIZE_ALIGNED)){/* 创建新的空闲内存块 */ptr2 = ptr + SIZEOF_STRUCT_MEM + size;mem2       = (struct rt_small_mem_item *)&small_mem->heap_ptr[ptr2];mem2->pool_ptr = MEM_FREED(small_mem);mem2->next = mem->next;mem2->prev = ptr;/* 更新当前内存块的next指针，使其指向新的空闲内存块 */mem->next = ptr2;/* 如果新的空闲内存块不是最后一个内存块，那么更新下一个内存块的prev指针，使其指向新的空闲内存块 */if (mem2->next != small_mem->mem_size_aligned + SIZEOF_STRUCT_MEM)((struct rt_small_mem_item *)&small_mem->heap_ptr[mem2->next])->prev = ptr2;/* 更新已使用的内存大小和最大使用内存大小 */small_mem->parent.used += (size + SIZEOF_STRUCT_MEM);if (small_mem->parent.max < small_mem->parent.used)small_mem->parent.max = small_mem->parent.used;}else{/* 更新已使用的内存大小 */small_mem->parent.used += mem->next - ((rt_uint8_t *)mem - small_mem->heap_ptr);if (small_mem->parent.max < small_mem->parent.used)small_mem->parent.max = small_mem->parent.used;}/* 设置当前分配内存为使用中 */mem->pool_ptr = MEM_USED(small_mem);//线程分配的设置线程名称if (rt_thread_self())rt_smem_setname(mem, rt_thread_self()->parent.name);else//中断分配设置为NONErt_smem_setname(mem, "NONE");//如果使用的是已经分配到的最大堆地址if (mem == small_mem->lfree){/* 在内存之后找到下一个空闲块并更新最低空闲指针 */while (MEM_ISUSED(small_mem->lfree) && small_mem->lfree != small_mem->heap_end)small_mem->lfree = &small_mem->heap_ptr[small_mem->lfree->next];}}}

1. 第一次分配内存时

ptr = 0;mem = (struct rt_small_mem_item *)&small_mem->heap_ptr[0];//第一个内存对象//* 如果当前内存块足够大，那么可以将其分割成两个部分，一个用于分配，另一个保留为新的空闲内存块 */if (mem->next - (ptr + SIZEOF_STRUCT_MEM) >=(size + SIZEOF_STRUCT_MEM + MIN_SIZE_ALIGNED)){mem2->next = mem->next;//mem2指向堆末尾mem2->prev = ptr;//上一个指向堆起始mem->next = ptr2;//堆起始的下一个更新为mem2/* 如果新的空闲内存块不是最后一个内存块，那么更新下一个内存块的prev指针，使其指向新的空闲内存块 */if (mem2->next != small_mem->mem_size_aligned + SIZEOF_STRUCT_MEM){//堆结尾的内存对象的上一个对象设置为mem2((struct rt_small_mem_item *)&small_mem->heap_ptr[mem2->next])->prev = ptr2;  }}

2. 再一次分配内存时,如果分配后剩余的内存空间不够再开辟一个内存对象时

/* 更新已使用的内存大小 */small_mem->parent.used += mem->next - ((rt_uint8_t *)mem - small_mem->heap_ptr);if (small_mem->parent.max < small_mem->parent.used)small_mem->parent.max = small_mem->parent.used;

9.2.3 realloc

if (newsize + SIZEOF_STRUCT_MEM + MIN_SIZE < size)//当前内存块大小满足可分配区域{/*分割内存块*/small_mem->parent.used -= (size - newsize);ptr2 = ptr + SIZEOF_STRUCT_MEM + newsize;mem2 = (struct rt_small_mem_item *)&small_mem->heap_ptr[ptr2];mem2->pool_ptr = MEM_FREED(small_mem);mem2->next = mem->next;mem2->prev = ptr;//合并相邻的未使用内存区域plug_holes(small_mem, mem2);} else {/*扩展内存*/nmem = rt_smem_alloc(&small_mem->parent, newsize);if (nmem != RT_NULL) /* check memory */{rt_memcpy(nmem, rmem, size < newsize ? size : newsize);//释放原使用内存rt_smem_free(rmem);}}

9.2.4 plug_holes

• 处理内存碎片的。它试图通过合并相邻的未使用的内存块（称为“空洞”）来减少内存碎片。这个过程被称为“填充空洞”
• 获取前一个内存项,尝试合并;获取后一个尝试合并

9.2.5 free

• 当前地址设置为未使用
• 写入内存使用为空rt_smem_setname(mem, " ");
• plug_holes

9.3 slab 管理算法

• slab 内存管理算法则主要是在系统资源比较丰富时，提供了一种近似多内存池管理算法的快速算法

Linux目前为其“slab”分配器提供了三种选择:Slab是最初的，基于Bonwick的开创性论文，从Linux内核2.2版开始就可以使用。它忠实地实现了Bonwick的建议，并在Bonwick的后续论文中描述了多处理器的变化。Slub是下一代替代内存分配器，自2.6.23以来一直是Linux内核中的默认配置。它继续使用基本的“slab”模型，但修复了slab设计中的几个缺陷，特别是在具有大量处理器的系统上。Slub比较简单SLOB (Simple List Of Blocks)是一种内存分配器，针对内存非常少的嵌入式系统进行了优化——以兆字节为数量级。它在一个块列表上应用一个非常简单的首次拟合算法，这与旧的k&r风格的堆分配器没有什么不同。在消除内存分配器中几乎所有的溢出时，SLOB非常适合具有极端内存限制的系统，但是它不提供第1节中描述的任何好处，并且可能遭受病态碎片。

• 1.静态内存池管理。

  2.针对小内存块的分配管理（小内存管理算法）

  3.针对大内存块的管理算法（SLAB管理算法）

  前面两篇已经把第1，2种算法看了，现在就来看看第三种算法，第三种算法主要是针对大内存使用的。第二种，小内存算法在分配内存的时候，随着内存碎片的增多，分配速度会越来越慢，当总的内存太大的时候，内存碎片的数量可能会更多，此时这种算法就会变得不再适用。

  SLAB在我看来就是前两种算法的融合。

• https://club.rt-thread.org/ask/question/438bfc8cfd626cc2.html

struct rt_slab{struct rt_memory            parent;                         /**< inherit from rt_memory */rt_ubase_t                  heap_start;                     /**< memory start address */rt_ubase_t                  heap_end;                       /**< memory end address */struct rt_slab_memusage{rt_uint32_t     type: 2 ;               /**< page type */rt_uint32_t     size: 30;               /**< pages allocated or offset from zone */};struct rt_slab_memusage    *memusage;                       /*内存信息存放 类型+索引*/struct rt_slab_zone        *zone_array[RT_SLAB_NZONES];     /* linked list of zones NFree > 0 */struct rt_slab_zone        *zone_free;                      /* whole zones that have become free */rt_uint32_t                 zone_free_cnt;rt_uint32_t                 zone_size;rt_uint32_t                 zone_limit;rt_uint32_t                 zone_page_cnt;struct rt_slab_page        *page_list;};/** slab page allocator* 页大小及分配信息*/struct rt_slab_page{struct rt_slab_page *next;      /**< next valid page */rt_size_t page;                 /**< number of page  *//* dummy */chardummy[RT_MM_PAGE_SIZE - (sizeof(struct rt_slab_page *) + sizeof(rt_size_t))];};

9.3.1 初始化

• page初始化,按页释放内存

  • 开始地址的page写入所有内存的页数
  • 下一个指向页对象为NULL
  • slab->page_list指向开始地址

• 计算zone大小:zone翻倍 比 最小数量 /1024小,则翻倍zone

/* calculate zone size */slab->zone_size = ZALLOC_MIN_ZONE_SIZE;while (slab->zone_size < ZALLOC_MAX_ZONE_SIZE && (slab->zone_size << 1) < (limsize / 1024))slab->zone_size <<= 1;

• rt_slab_page_alloc 了 内存信息存放的空间 npage*内存信息结构体

9.3.2 页内存释放

voidrt_slab_page_free(rt_slab_tm, void *addr, rt_size_tnpages){struct rt_slab_page *b, *n;struct rt_slab_page **prev;struct rt_slab *slab = (struct rt_slab *)m;// 确保地址不为空，地址是内存页大小的倍数，且页数不为0RT_ASSERT(addr != RT_NULL);RT_ASSERT((rt_ubase_t)addr % RT_MM_PAGE_SIZE == 0);RT_ASSERT(npages != 0);// 将地址转换为rt_slab_page结构体n = (struct rt_slab_page *)addr;// 遍历slab的页面列表for (prev = &slab->page_list; (b = *prev) != RT_NULL; prev = &(b->next)){// 确保页面数量大于0，且当前页面在释放的页面之后或不重叠RT_ASSERT(b->page > 0);RT_ASSERT(b > n || b + b->page <= n);// 如果当前页面紧邻释放的页面if (b + b->page == n){//如果当前页面刚好满足释放,则进行合并if (b + (b->page += npages) == b->next){b->page += b->next->page;b->next  = b->next->next;}return;}// 如果当前页面刚好满足释放要求,则进行合并if (b == n + npages){n->page = b->page + npages;n->next = b->next;*prev   = n;return;}// 如果当前页面比所需的内存页来的大,则退出if (b > n + npages)break;}//写入页面信息与下一个节点n->page = npages;n->next = b;//上一个节点指向当前页面*prev   = n;}

9.3.3 页内存分配

// 遍历slab的page_listfor (prev = &slab->page_list; (b = *prev) != RT_NULL; prev = &(b->next)){// 如果b的页数大于npagesif (b->page > npages){// 分割页面n       = b + npages;n->next = b->next;n->page = b->page - npages;*prev   = n;break;}// 如果b的页数等于npagesif (b->page == npages){// 这个节点适合，移除这个节点*prev = b->next;break;}}

9.3.5 malloc

9.3.5.1 大内存

• 直接处理大量分配 ,直接分配

9.3.5.2小内存

/** 计算分配请求大小的区域索引，并将分配请求大小设置为该区域的块大小。*/rt_inline intzoneindex(rt_size_t *bytes){/* 无符号整数用于位移操作 */rt_ubase_t n = (rt_ubase_t)(*bytes);if (n < 128){/* 对齐到8字节，并计算区域索引 */*bytes = n = (n + 7) & ~7;return (n / 8 - 1);}if (n < 256){/* 对齐到16字节，并计算区域索引 */*bytes = n = (n + 15) & ~15;return (n / 16 + 7);}/* 对于更大的内存请求，使用更大的对齐单位，并计算相应的区域索引 */if (n < 8192){/* ...省略部分代码... */}if (n < 16384){/* 对齐到1024字节，并计算区域索引 */*bytes = n = (n + 1023) & ~1023;return (n / 1024 + 55);}/* 如果内存请求大小超出预期，打印错误信息 */rt_kprintf("Unexpected byte count %d", n);return0;}

9.3.5.2 没有分配过或者用光了

1. 该zone没有被使用过

   • 从页面分配一个区域,设置内存信息 memusage的类型与索引,设置zone空间信息
   • 计算块地址,链接到zone数组中

2. 该zone被使用过

   • 直接分配,从zone_free中移除

9.3.5.3 有zone数组

1. 分配完了,从zone数组中移除

2. 可分配,执行分配

3. 没有可分配空间

   • 在空闲块列表中查找(free的时候分配)
   • 从空闲块列表中删除此块

9.3.6 free

9.3.6.1 大内存释放

• 直接释放,size设置为0

9.3.6.2 小内存释放

• 将内存设置标识下一个free块节点为free块

• 将当前free块设置为当前内存

• 如果zone释放后可以提供分配了,添加回zone数组中

• 如果该区域完全空闲，并且我们可以从其他区域进行分配，则将该区域移到FreeZones列表中

  -空闲区域计数和释放：每当一个区域被移动到空闲区域列表中，空闲区域的计数（slab->zone_free_cnt）就会增加。如果空闲区域的数量超过了设定的阈值（ZONE_RELEASE_THRESH），那么就会释放一个区域到页面分配器。

  -页面的释放：在释放区域到页面分配器之前，会设置每个页面的使用情况（kup->type = PAGE_TYPE_FREE; kup->size = 0;）。然后，调用 rt_slab_page_free()函数来释放这些页面。

9.4 memheap 管理算法

• memheap 方法适用于系统存在多个内存堆的情况，它可以将多个内存 “粘贴” 在一起，形成一个大的内存堆，用户使用起来会非常方便

9.4.1 init

• 计算可用大小
• 设置信息
• 设置链表

9.4.2 alloc

• 可用分配

• 从链表中寻找可分配的内存

  1. 寻找到可分配的内存,分割进行分配
  2. 找不到;继续从最后一个内存往后分配

9.4.3 free

• 释放
• 查找是否可以与临近的内存合并,进行合并

9.5 malloc&&realloc分配

1. 线程中使用加锁,中断中使用不加锁
2. _MEM_MALLOC 调用不同内存算法的malloc
3. 解锁
4. 调用malloc call函数

9.6 TLSF 内存管理算法

https://www.cnblogs.com/pwl999/p/15534968.html

9.6.1 堆初始化

1. 创建内存池

• 清空结构体信息

2. 添加内存池

• 传递给给定内存块中的 TLSF 结构的开销 tlsf_add_pool，等于空闲块的开销和哨兵块。
• 创建主要空闲块。稍微偏移块的起点以便 prev_phys_block 字段落在池之外它永远不会被使用。

使用 const的原因有很多：提高代码的可读性：const关键字告诉读代码的人这个变量的值不会改变，这有助于理解代码的行为。防止误操作：在函数的其余部分，如果你试图改变 oldsize的值，编译器会报错，因此可以防止因误操作而导致的错误。优化性能：编译器知道 const变量的值不会改变，可能会进行一些优化。

• 设置块的大小,并设置该块为未使用,设置下一个块为使用中

constsize_t oldsize = block->size;//保留原有的oldsize使用标志不变的情况下,设置新的sizeblock->size = size | (oldsize & (block_header_free_bit | block_header_prev_free_bit));

• 插入新的块

staticvoidmapping_insert(size_tsize, int *fli, int *sli){int fl, sl;if (size < SMALL_BLOCK_SIZE) // 如果大小小于小块的大小{/* Store small blocks in first list. */fl = 0; // 第一级索引设置为0sl = tlsf_cast(int, size) / (SMALL_BLOCK_SIZE / SL_INDEX_COUNT); // 第二级索引根据大小和小块的数量进行计算}else // 如果大小大于或等于小块的大小{fl = tlsf_fls_sizet(size); // 使用位操作找到最高位的1，也就是第一级索引sl = tlsf_cast(int, size >> (fl - SL_INDEX_COUNT_LOG2)) ^ (1 << SL_INDEX_COUNT_LOG2); // 使用位操作计算第二级索引fl -= (FL_INDEX_SHIFT - 1); // 调整第一级索引，使其从0开始}*fli = fl; // 返回第一级索引*sli = sl; // 返回第二级索引}

• 分割块以创建零大小的哨兵块

9.6.2 添加堆

• 根据地址添加池
• 添加当前堆到链表中

9.6.3 malloc