#FREERTOS的和heap_4記憶體分配演算法

来源:https://www.cnblogs.com/chenpangzhi/archive/2023/04/05/17291060.html
-Advertisement-
Play Games

FreeRTOS的heap_4記憶體管理演算法具有記憶體碎片合併的功能，可以有效防止記憶體碎片產生，使用First fit演算法，在實現上與C標準庫的malloc類似，但是效率更高且能進行碎片合併回收。以下是個人對源碼的解析,有空再補充詳細。 一、初始化 static void prvHeapInit( vo ...


FreeRTOS的heap_4記憶體管理演算法具有記憶體碎片合併的功能，可以有效防止記憶體碎片產生，使用First fit演算法，在實現上與C標準庫的malloc類似，但是效率更高且能進行碎片合併回收。以下是個人對源碼的解析,有空再補充詳細。

一、初始化

static void prvHeapInit( void )
{
    BlockLink_t *pxFirstFreeBlock;
    uint8_t *pucAlignedHeap;
    size_t uxAddress;
    size_t xTotalHeapSize = configTOTAL_HEAP_SIZE;

/*====================================== 1 ===========================================*/
    /* 位元組對齊,4位元組 */
    uxAddress = ( size_t ) ucHeap;
    /*位元組對齊，一般是8位元組*/
    if( ( uxAddress & portBYTE_ALIGNMENT_MASK ) != 0 )
    {
        /* 對齊處理 */
        uxAddress += ( portBYTE_ALIGNMENT - 1 );
        uxAddress &= ~( ( size_t ) portBYTE_ALIGNMENT_MASK );
        xTotalHeapSize -= uxAddress - ( size_t ) ucHeap;
    }
    /*取對齊後的地址*/
    pucAlignedHeap = ( uint8_t * ) uxAddress;

/*====================================== 2 ===========================================*/
    /* 把xStart的next指針指向對齊後的頭地址，長度設置為0.xStart只是鏈表頭不參與記憶體分配*/
    xStart.pxNextFreeBlock = ( void * ) pucAlignedHeap;
    xStart.xBlockSize = ( size_t ) 0;
/*====================================== 3 ===========================================*/
    /* 計算尾部指針地址 */
    uxAddress = ( ( size_t ) pucAlignedHeap ) + xTotalHeapSize;
    /* 減去end所占用的8個位元組 */
    uxAddress -= xHeapStructSize;
    /* pxend位元組對齊，也就是尾部會空出8-15位元組用於放pxend */
    uxAddress &= ~( ( size_t ) portBYTE_ALIGNMENT_MASK );
    /* pxend初始化 */
    pxEnd = ( void * ) uxAddress;
    pxEnd->xBlockSize = 0;
    pxEnd->pxNextFreeBlock = NULL;

/*====================================== 4 ===========================================*/
    /* 初始化頭結構，也就是xstart一開始指向的那個地址 */
    pxFirstFreeBlock = ( void * ) pucAlignedHeap;
    pxFirstFreeBlock->xBlockSize = uxAddress - ( size_t ) pxFirstFreeBlock;
    pxFirstFreeBlock->pxNextFreeBlock = pxEnd;
    /* 初始化記憶體最大使用量和剩餘空間這兩個變數的值 */
    xMinimumEverFreeBytesRemaining = pxFirstFreeBlock->xBlockSize;
    xFreeBytesRemaining = pxFirstFreeBlock->xBlockSize;
    /* 定義xBlockSize最高bit，因為xBlockSize的最高bit用於判斷是否使用 */
    xBlockAllocatedBit = ( ( size_t ) 1 ) << ( ( sizeof( size_t ) * heapBITS_PER_BYTE ) - 1 );
}
  1. 進行位元組對齊，找到對齊後的首地址，在32位機中以8位元組進行對齊。
  2. 初始化xStart的值。
  3. 計算對齊後的尾部地址，將pxEnd指向這一地址，同時初始化。
  4. 初始化xStart指向的頭地址的值，因為還沒分配，所以next指向pxend，size為整個空間大小。初始化用於記錄剩餘空間的變數值

二、申請記憶體

void *pvPortMalloc( size_t xWantedSize )
{
    BlockLink_t *pxBlock, *pxPreviousBlock, *pxNewBlockLink;
    void *pvReturn = NULL;

    {
        /* 如果還沒初始化的話，就先初始化. */
        if( pxEnd == NULL )
        {
            prvHeapInit();
        }
        
        /* 檢查要分配的大小是否超過了最大值,因為最高位用來標誌空閑塊是否已經使用，
            所以能分配的空間最大值為0x7FFF FFFF 也就是2G*/
        if( ( xWantedSize & xBlockAllocatedBit ) == 0 )
        {
            /* 檢查分配空間是否為0 */
            if( xWantedSize > 0 )
            {
                /* 加上鏈表結構的大小 */
                xWantedSize += xHeapStructSize;
                /* 日常位元組對齊 */
                if( ( xWantedSize & portBYTE_ALIGNMENT_MASK ) != 0x00 )
                {
                    /* 補齊. */
                    xWantedSize += ( portBYTE_ALIGNMENT - ( xWantedSize & portBYTE_ALIGNMENT_MASK ) );
                }
            }
            /* 這裡也判斷xWantedSize>0,可以跟上面的代碼合併啊，判斷空閑的空間還夠不夠 */
            if( ( xWantedSize > 0 ) && ( xWantedSize <= xFreeBytesRemaining ) )
            {
                /* 從頭開始查找大小夠分配的空閑塊，直到找到pxend. */
                pxPreviousBlock = &xStart;
                pxBlock = xStart.pxNextFreeBlock;
                while( ( pxBlock->xBlockSize < xWantedSize ) && ( pxBlock->pxNextFreeBlock != NULL ) )
                {
                    pxPreviousBlock = pxBlock;
                    pxBlock = pxBlock->pxNextFreeBlock;
                }
                /* 如果是pxEnd就是說沒有能夠分配的空閑塊了，分配失敗 */
                if( pxBlock != pxEnd )
                {
                    /* 分配的地址是空閑塊管理結構地址+結構大小，如圖
                                分配了的空間     新的空閑塊
                        |____|_______________|________________| 
                          ☝  ↑分配的記憶體地址
                    有足夠空間的結構， */
                    pvReturn = ( void * ) ( ( ( uint8_t * ) pxPreviousBlock->pxNextFreeBlock ) + xHeapStructSize );
                    /* 跳過剛剛被使用的空閑塊，指向下一塊 */
                    pxPreviousBlock->pxNextFreeBlock = pxBlock->pxNextFreeBlock;
                    /* 如果當前空閑塊分配完之後剩餘的大小還>=16位元組，就分成兩塊 */
                    if( ( pxBlock->xBlockSize - xWantedSize ) > heapMINIMUM_BLOCK_SIZE )
                    {
                        /* 創建一個新的空閑塊，計算偏移地址 */
                        pxNewBlockLink = ( void * ) ( ( ( uint8_t * ) pxBlock ) + xWantedSize );
                        /* 初始化新空閑塊的大小，next需要做插入處理 */
                        pxNewBlockLink->xBlockSize = pxBlock->xBlockSize - xWantedSize;
                        /* 舊塊重新定義大小 */
                        pxBlock->xBlockSize = xWantedSize;
                        /* Insert the new block into the list of free blocks.看英語解釋 */
                        prvInsertBlockIntoFreeList( pxNewBlockLink );
                    }
                    /* 扣除剩餘的空間統計 */
                    xFreeBytesRemaining -= pxBlock->xBlockSize;
                    /* 記錄當前使用空間的最大值，也就是記錄系統運行中最多用了多少空間 */
                    if( xFreeBytesRemaining < xMinimumEverFreeBytesRemaining )
                    {
                        xMinimumEverFreeBytesRemaining = xFreeBytesRemaining;
                    }
                    /* 最高位置為1，清楚next指針，標記已經用掉了 */
                    pxBlock->xBlockSize |= xBlockAllocatedBit;
                    pxBlock->pxNextFreeBlock = NULL;
                }
            }
        }
    }
    {
        if( pvReturn == NULL )
        {
            printf("malloc fail \r\n");    
        }
        
    }
    return pvReturn;
}

三、釋放記憶體

oid vPortFree( void *pv )
{
uint8_t *puc = ( uint8_t * ) pv;
BlockLink_t *pxLink;

    if( pv != NULL )
    {
        /* 找到結構體的地址
                   ↓puc地址
            |______|___________________| 
            ↑BlockLink_t地址*/
        puc -= xHeapStructSize;
        /* 防一手編譯器警告 */
        pxLink = ( void * ) puc;
        /* 通過最高位判斷是否已經使用 */
        if( ( pxLink->xBlockSize & xBlockAllocatedBit ) != 0 )
        {
            /* 已經使用的next被覆製為null，可以看malloc */
            if( pxLink->pxNextFreeBlock == NULL )
            {
                /*清掉標誌位 */
                pxLink->xBlockSize &= ~xBlockAllocatedBit;
                {
                    /* 統計空閑內記憶體大小，插入鏈表中. */
                    xFreeBytesRemaining += pxLink->xBlockSize;
                    prvInsertBlockIntoFreeList( ( ( BlockLink_t * ) pxLink ) );
                }
            }
            
        }
        
    }
}
/*-----------------------------------------------------------*/

四、碎片整理

把新的空閑列表項插入鏈表中，同時進行空閑塊合併。

static void prvInsertBlockIntoFreeList( BlockLink_t *pxBlockToInsert )
{
    BlockLink_t *pxIterator;
    uint8_t *puc;    
    /* 遍歷鏈表，找到newlist的前一個list地址，也就是插入的位置.        
    heap4對鏈表的地址管理都是從小到大，所以只要迴圈比對地址大小就行了 */    
    for( pxIterator = &xStart; pxIterator->pxNextFreeBlock < pxBlockToInsert; pxIterator = pxIterator->pxNextFreeBlock )    
    {        
        /* Nothing to do here, just iterate to the right position. */    
    }    
    /* 插入前，檢查前(已有的項)後(要插入的項)兩個空閑塊是否相鄰，相鄰的話直接合併 */    
    puc = ( uint8_t * ) pxIterator;    
    if( ( puc + pxIterator->xBlockSize ) == ( uint8_t * ) pxBlockToInsert )    
    {        
        /* 合併處理 */        
        pxIterator->xBlockSize += pxBlockToInsert->xBlockSize;        
        pxBlockToInsert = pxIterator;    
    }    
    /* 插入前，檢查前(要插入的項pxBlockToInsert)後(已有的項)兩個空閑塊是否相鄰，相鄰的話直接合併，        
    跟上面的流程相同，只是比對的是跟在新鏈表後面的那個 */    
    puc = ( uint8_t * ) pxBlockToInsert;    
    if( ( puc + pxBlockToInsert->xBlockSize ) == ( uint8_t * ) pxIterator->pxNextFreeBlock )    
    {        
        if( pxIterator->pxNextFreeBlock != pxEnd )        
        {            
            /* 合成一塊 */            
            pxBlockToInsert->xBlockSize += pxIterator->pxNextFreeBlock->xBlockSize;            pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock->pxNextFreeBlock;     
        }        
        else        
        {            
            /* 不合併的話給新鏈表項的next賦值 */            
            pxBlockToInsert->pxNextFreeBlock = pxEnd;        
        }    
    }    
    else    
    {        
        /* 不合併的話給新鏈表項的next賦值 */        
        pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock;    
    }    
    /* 如果沒進行過合併，插入新鏈表 */    
    if( pxIterator != pxBlockToInsert )    
    {        
        pxIterator->pxNextFreeBlock = pxBlockToInsert;    
    }    
}

您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • MySQL四種日誌binlog/redolog/relaylog/undolog
    優質博文：IT-BLOG-CN 一、binlog binlog記錄資料庫表結構和表數據變更，比如update/delete/insert/truncate/create，它不會記錄select。存儲著每條變更的SQL語句和XID事務Id等等。binlog日誌文件如下： [[email protected] ...
  • 讀SQL進階教程筆記08_處理數列
    1. 處理有序集合也並非SQL的直接用途 1.1. SQL語言在處理數據時預設地都不考慮順序 2. 處理數據的方法有兩種 2.1. 第一種是把數據看成忽略了順序的集合 2.2. 第二種是把數據看成有序的集合 2.2.1. 首先用自連接生成起點和終點的組合 2.2.2. 其次在子查詢中描述內部的各個元 ...
  • mysql精確查年齡
    已知出生年月日，求到今天為止多少歲 select *, --如果當前月份大於出生月，年齡 = 當前年份 - 出生年 if (month(current_date())-month(substr(id_card,7,8))>0, year(current_date())-year(substr(id_ ...
  • Android Banner - ViewPager 02
    Android Banner - ViewPager 02 現在來給viewpager實現的banenr加上自動輪播 自動輪播的原理，使用handler的延遲消息來實現。 自動輪播實現如下內容 開始輪播&停止輪播 可配置輪播時長、輪播方向 通過自定義屬性來配置輪播時長，方向 感知生命周期，可見時開始 ...
  • JavaScript快速入門（二）
    文件中引入JavaScript 嵌入到HTML文件中 在body或者head中添加script標簽 <script> var age = 10; console.log(age); </script> 引入js文件 創建一個js文件 var age = 20; console.log(age); 在 ...
  • 如何設計一套支付系統
    支付永遠是一個公司的核心領域，因為這是一個有交易屬性公司的命脈。那麼，支付系統到底長什麼樣，又是怎麼運行交互的呢?拋開帶有支付牌照的金融公司的支付架構，下述鏈路和系統組成基本上符合絕大多數支付場景。其實整體可以看成是交易核心+支付核心 兩個大系統。交易系統關聯了業務場景和底層支付，而支付系統完成了調 ...
  • LAL v0.34.3發佈，G711音頻來了，Web UI也來了
    Go語言流媒體開源項目 LAL 今天發佈了v0.34.3版本。 LAL 項目地址：https://github.com/q191201771/lal 老規矩，簡單介紹一下： ▦ 一. 音頻G711 新增了對音頻G711A/G711U(也被稱為PCMA/PCMU)的支持。主要表現在： ✒ 1) rtm ...
  • 將代碼中的調試信息輸出到日誌文件中
    一、將調試信息輸出到屏幕中 1.1 一般寫法 我們平常在寫代碼時，肯定會有一些調試信息的輸出： #include <stdio.h> #include <stdlib.h> int main() { char szFileName[] = "test.txt"; FILE *fp = fopen(s ...
一周排行
    -Advertisement-
    Play Games
  • C# + WPF 音頻播放器 界面優雅，體驗良好
    前言 本文介紹一款使用 C# 與 WPF 開發的音頻播放器，其界面簡潔大方，操作體驗流暢。該播放器支持多種音頻格式（如 MP4、WMA、OGG、FLAC 等），並具備標記、實時歌詞顯示等功能。 另外，還支持換膚及多語言（中英文）切換。核心音頻處理採用 FFmpeg 組件，獲得了廣泛認可，目前 Git ...
  • OAuth2.0授權-gitee授權碼模式
    OAuth2.0授權驗證-gitee授權碼模式 本文主要介紹如何筆者自己是如何使用gitee提供的OAuth2.0協議完成授權驗證並登錄到自己的系統，完整模式如圖 1、創建應用 打開gitee個人中心->第三方應用->創建應用 創建應用後在我的應用界面，查看已創建應用的Client ID和Clien ...
  • FastReport.OpenSource .Net下開源免費報表列印組件
    解決了這個問題：《winForm下，fastReport.net 從.net framework 升級到.net5遇到的錯誤“Operation is not supported on this platform.”》 本文內容轉載自：https://www.fcnsoft.com/Home/Sho ...
  • 如何在 ASP.NET Core Web API 方法執行前後 “偷偷“ 作一些 “壞“ 事？初識 ActionFilterAttribute
    國內文章 WPF 從裸 Win 32 的 WM_Pointer 消息獲取觸摸點繪製筆跡 https://www.cnblogs.com/lindexi/p/18390983 本文將告訴大家如何在 WPF 裡面，接收裸 Win 32 的 WM_Pointer 消息，從消息裡面獲取觸摸點信息，使用觸摸點 ...
  • 在 ASP.NET Core Web API 中使用異常篩選器捕獲和統一處理異常
    前言 給大家推薦一個專為新零售快消行業打造了一套高效的進銷存管理系統。 系統不僅具備強大的庫存管理功能，還集成了高性能的輕量級 POS 解決方案，確保頁面載入速度極快，提供良好的用戶體驗。 項目介紹 Dorisoy.POS 是一款基於 .NET 7 和 Angular 4 開發的新零售快消進銷存管理 ...
  • AbpHelper CLI積累與實戰分享
    ABP CLI常用的代碼分享 一、確保環境配置正確 安裝.NET CLI： ABP CLI是基於.NET Core或.NET 5/6/7等更高版本構建的，因此首先需要在你的開發環境中安裝.NET CLI。這可以通過訪問Microsoft官網下載並安裝相應版本的.NET SDK來實現。 安裝ABP ...
  • 記一次HttpClient使用問題分析
    問題 問題是這樣的：第三方的webapi，需要先調用登陸介面獲取Cookie，訪問其它介面時攜帶Cookie信息。 但使用HttpClient類調用登陸介面，返回的Headers中沒有找到Cookie信息。 分析 首先，使用Postman測試該登陸介面，正常返回Cookie信息，說明是HttpCli ...
  • .NET周刊【9月第3期 2024-09-15】
    國內文章 關於.NET在中國為什麼工資低的分析 https://www.cnblogs.com/thinkingmore/p/18406244 .NET在中國開發者的薪資偏低，主要因市場需求、技術棧選擇和企業文化等因素所致。歷史上，.NET曾因微軟的閉源策略發展受限，儘管後來推出了跨平臺的.NET ...
  • 我的網站集成ElasticSearch初體驗
    在WPF開發應用中，動畫不僅可以引起用戶的註意與興趣，而且還使軟體更加便於使用。前面幾篇文章講解了畫筆（Brush），形狀（Shape），幾何圖形（Geometry），變換（Transform）等相關內容，今天繼續講解動畫相關內容和知識點，僅供學習分享使用，如有不足之處，還請指正。 ...
  • 第23篇 委托的概述
    什麼是委托？ 委托可以說是把一個方法代入另一個方法執行，相當於指向函數的指針；事件就相當於保存委托的數組； 1.實例化委托的方式： 方式1：通過new創建實例： public delegate void ShowDelegate(); 或者 public delegate string ShowDe ...
所有分類