#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
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類