ToB企服应用市场:ToB评测及商务社交产业平台

标题: #FREERTOS的和heap_4内存分配算法 [打印本页]
作者: 万有斥力    时间: 2023-4-5 22:25
标题: #FREERTOS的和heap_4内存分配算法
FreeRTOS的heap_4内存管理算法具有内存碎片合并的功能，可以有效防止内存碎片产生，使用First fit算法，在实现上与C标准库的malloc类似，但是效率更高且能进行碎片合并回收。以下是个人对源码的解析,有空再补充详细。
一、初始化
  1. static void prvHeapInit( void )
  2. {
  3.     BlockLink_t *pxFirstFreeBlock;
  4.     uint8_t *pucAlignedHeap;
  5.     size_t uxAddress;
  6.     size_t xTotalHeapSize = configTOTAL_HEAP_SIZE;
  8. /*====================================== 1 ===========================================*/
  9.     /* 字节对齐,4字节 */
  10.     uxAddress = ( size_t ) ucHeap;
  11.     /*字节对齐，一般是8字节*/
  12.     if( ( uxAddress & portBYTE_ALIGNMENT_MASK ) != 0 )
  13.     {
  14.         /* 对齐处理 */
  15.         uxAddress += ( portBYTE_ALIGNMENT - 1 );
  16.         uxAddress &= ~( ( size_t ) portBYTE_ALIGNMENT_MASK );
  17.         xTotalHeapSize -= uxAddress - ( size_t ) ucHeap;
  18.     }
  19.     /*取对齐后的地址*/
  20.     pucAlignedHeap = ( uint8_t * ) uxAddress;
  22. /*====================================== 2 ===========================================*/
  23.     /* 把xStart的next指针指向对齐后的头地址，长度设置为0.xStart只是链表头不参与内存分配*/
  24.     xStart.pxNextFreeBlock = ( void * ) pucAlignedHeap;
  25.     xStart.xBlockSize = ( size_t ) 0;
  26. /*====================================== 3 ===========================================*/
  27.     /* 计算尾部指针地址 */
  28.     uxAddress = ( ( size_t ) pucAlignedHeap ) + xTotalHeapSize;
  29.     /* 减去end所占用的8个字节 */
  30.     uxAddress -= xHeapStructSize;
  31.     /* pxend字节对齐，也就是尾部会空出8-15字节用于放pxend */
  32.     uxAddress &= ~( ( size_t ) portBYTE_ALIGNMENT_MASK );
  33.     /* pxend初始化 */
  34.     pxEnd = ( void * ) uxAddress;
  35.     pxEnd->xBlockSize = 0;
  36.     pxEnd->pxNextFreeBlock = NULL;
  38. /*====================================== 4 ===========================================*/
  39.     /* 初始化头结构，也就是xstart一开始指向的那个地址 */
  40.     pxFirstFreeBlock = ( void * ) pucAlignedHeap;
  41.     pxFirstFreeBlock->xBlockSize = uxAddress - ( size_t ) pxFirstFreeBlock;
  42.     pxFirstFreeBlock->pxNextFreeBlock = pxEnd;
  43.     /* 初始化内存最大使用量和剩余空间这两个变量的值 */
  44.     xMinimumEverFreeBytesRemaining = pxFirstFreeBlock->xBlockSize;
  45.     xFreeBytesRemaining = pxFirstFreeBlock->xBlockSize;
  46.     /* 定义xBlockSize最高bit，因为xBlockSize的最高bit用于判断是否使用 */
  47.     xBlockAllocatedBit = ( ( size_t ) 1 ) << ( ( sizeof( size_t ) * heapBITS_PER_BYTE ) - 1 );
  48. }
复制代码
三、释放内存
  1. void *pvPortMalloc( size_t xWantedSize )
  2. {
  3.     BlockLink_t *pxBlock, *pxPreviousBlock, *pxNewBlockLink;
  4.     void *pvReturn = NULL;
  6.     {
  7.         /* 如果还没初始化的话，就先初始化. */
  8.         if( pxEnd == NULL )
  9.         {
  10.             prvHeapInit();
  11.         }
  12.         
  13.         /* 检查要分配的大小是否超过了最大值,因为最高位用来标志空闲块是否已经使用，
  14.             所以能分配的空间最大值为0x7FFF FFFF 也就是2G*/
  15.         if( ( xWantedSize & xBlockAllocatedBit ) == 0 )
  16.         {
  17.             /* 检查分配空间是否为0 */
  18.             if( xWantedSize > 0 )
  19.             {
  20.                 /* 加上链表结构的大小 */
  21.                 xWantedSize += xHeapStructSize;
  22.                 /* 日常字节对齐 */
  23.                 if( ( xWantedSize & portBYTE_ALIGNMENT_MASK ) != 0x00 )
  24.                 {
  25.                     /* 补齐. */
  26.                     xWantedSize += ( portBYTE_ALIGNMENT - ( xWantedSize & portBYTE_ALIGNMENT_MASK ) );
  27.                 }
  28.             }
  29.             /* 这里也判断xWantedSize>0,可以跟上面的代码合并啊，判断空闲的空间还够不够 */
  30.             if( ( xWantedSize > 0 ) && ( xWantedSize <= xFreeBytesRemaining ) )
  31.             {
  32.                 /* 从头开始查找大小够分配的空闲块，直到找到pxend. */
  33.                 pxPreviousBlock = &xStart;
  34.                 pxBlock = xStart.pxNextFreeBlock;
  35.                 while( ( pxBlock->xBlockSize < xWantedSize ) && ( pxBlock->pxNextFreeBlock != NULL ) )
  36.                 {
  37.                     pxPreviousBlock = pxBlock;
  38.                     pxBlock = pxBlock->pxNextFreeBlock;
  39.                 }
  40.                 /* 如果是pxEnd就是说没有能够分配的空闲块了，分配失败 */
  41.                 if( pxBlock != pxEnd )
  42.                 {
  43.                     /* 分配的地址是空闲块管理结构地址+结构大小，如图
  44.                                 分配了的空间     新的空闲块
  45.                         |____|_______________|________________|
  46.                           ☝  ↑分配的内存地址
  47.                     有足够空间的结构， */
  48.                     pvReturn = ( void * ) ( ( ( uint8_t * ) pxPreviousBlock->pxNextFreeBlock ) + xHeapStructSize );
  49.                     /* 跳过刚刚被使用的空闲块，指向下一块 */
  50.                     pxPreviousBlock->pxNextFreeBlock = pxBlock->pxNextFreeBlock;
  51.                     /* 如果当前空闲块分配完之后剩余的大小还>=16字节，就分成两块 */
  52.                     if( ( pxBlock->xBlockSize - xWantedSize ) > heapMINIMUM_BLOCK_SIZE )
  53.                     {
  54.                         /* 创建一个新的空闲块，计算偏移地址 */
  55.                         pxNewBlockLink = ( void * ) ( ( ( uint8_t * ) pxBlock ) + xWantedSize );
  56.                         /* 初始化新空闲块的大小，next需要做插入处理 */
  57.                         pxNewBlockLink->xBlockSize = pxBlock->xBlockSize - xWantedSize;
  58.                         /* 旧块重新定义大小 */
  59.                         pxBlock->xBlockSize = xWantedSize;
  60.                         /* Insert the new block into the list of free blocks.看英语解释 */
  61.                         prvInsertBlockIntoFreeList( pxNewBlockLink );
  62.                     }
  63.                     /* 扣除剩余的空间统计 */
  64.                     xFreeBytesRemaining -= pxBlock->xBlockSize;
  65.                     /* 记录当前使用空间的最大值，也就是记录系统运行中最多用了多少空间 */
  66.                     if( xFreeBytesRemaining < xMinimumEverFreeBytesRemaining )
  67.                     {
  68.                         xMinimumEverFreeBytesRemaining = xFreeBytesRemaining;
  69.                     }
  70.                     /* 最高位置为1，清楚next指针，标记已经用掉了 */
  71.                     pxBlock->xBlockSize |= xBlockAllocatedBit;
  72.                     pxBlock->pxNextFreeBlock = NULL;
  73.                 }
  74.             }
  75.         }
  76.     }
  77.     {
  78.         if( pvReturn == NULL )
  79.         {
  80.             printf("malloc fail \r\n");   
  81.         }
  82.         
  83.     }
  84.     return pvReturn;
  85. }
复制代码
四、碎片整理

把新的空闲列表项插入链表中，同时进行空闲块合并。
  1. oid vPortFree( void *pv )
  2. {
  3. uint8_t *puc = ( uint8_t * ) pv;
  4. BlockLink_t *pxLink;
  6.     if( pv != NULL )
  7.     {
  8.         /* 找到结构体的地址
  9.                    ↓puc地址
  10.             |______|___________________|
  11.             ↑BlockLink_t地址*/
  12.         puc -= xHeapStructSize;
  13.         /* 防一手编译器警告 */
  14.         pxLink = ( void * ) puc;
  15.         /* 通过最高位判断是否已经使用 */
  16.         if( ( pxLink->xBlockSize & xBlockAllocatedBit ) != 0 )
  17.         {
  18.             /* 已经使用的next被复制为null，可以看malloc */
  19.             if( pxLink->pxNextFreeBlock == NULL )
  20.             {
  21.                 /*清掉标志位 */
  22.                 pxLink->xBlockSize &= ~xBlockAllocatedBit;
  23.                 {
  24.                     /* 统计空闲内内存大小，插入链表中. */
  25.                     xFreeBytesRemaining += pxLink->xBlockSize;
  26.                     prvInsertBlockIntoFreeList( ( ( BlockLink_t * ) pxLink ) );
  27.                 }
  28.             }
  29.             
  30.         }
  31.         
  32.     }
  33. }
  34. /*-----------------------------------------------------------*/
复制代码
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4