超級精簡系列之:高效且運行時間固定的內存池實現

原創嵌入式Lee 2024-06-20 08:31

4周搞定BLE/Wi?Fi/NFC，從選型到首例工程
告別射頻開關短板！MEMS 高速測試資料

一.?前言

這里簡單提一下在RTOS環境開發中,比較容易出現的一個BUG為例，引出我們為什么要設計我們這個內存池的輪子。以FreeRTOS為例，堆管理malloc和free的實現是基于鏈表進行的，鏈表是一個全局的資源，且操作不是一個原子操作，涉及很多步驟，所以多處調用時就必須進行臨界段保護，否則操作到一半被打斷進行另外的操作就會導致資源被破壞。FreeRTOS的處理方式是關調度的方式來實現臨界段保護，關調度只能保證任務不會搶占，無法保證中斷搶占，所以中斷中不能調用FreeRTOS的malloc和free接口。而有時驅動設計又必須使用動態內存管理，驅動很多都是中斷驅動的有時必須在中斷中調用堆管理接口，此時直接調用FreeRTOS的堆管理接口就會導致問題，上述問題很可能難以發現，并且不一定能測試出來，可能在某種湊巧時機，剛好中斷中打斷任務中的堆接口執行，并調用堆管理接口此時就會出現問題。這種問題很可能就會出現很大的隨機性導致了的調試的困難。知道了這個原因就可以避免類似的錯誤了，但是回到問題來，我們中斷中還是有動態內存的使用需求那怎么辦呢，最簡單的方式就是還是使用FreeRTOS提供的堆接口，把關調度改為關中斷，這樣就可以保證臨界段不被搶占，就不會有問題，但是這里會有一些副作用就是關中斷時間的增加，并且這個時間還是不確定的，我們下一節就進行了實測。當然堆管理還有碎片化等問題，所以不適合在驅動層和中斷時調用。所以我們還有一種方式就是使用內存池，這是很多中間件，驅動比較常見的方式，我們這一篇就是要來實現一個簡單高效的內存池，但是我們不滿足于此，我們還有更高的要求，畢竟是在驅動層甚至中斷中使用，我們希望它執行非常快，并且執行時間基本無波動，因為這兩個指標都是很重要的，很多系統甚至是必須要滿足的。

二.?堆管理接口執行時間測試

執行時間測試有很多種方式，一般使用硬件定時器。我們這里使用另一種實踐中也常用的方式，使用IO翻轉，示波器查看波形的方式測試，進入接口執行時翻轉IO，退出接口執行，再次翻轉IO，IO波形得脈寬即執行時間，這樣可以可視化觀察，疏密變化可以看出執行時間的抖動，脈寬可以看出執行時間，maloc和free使用不同IO對比，還可以看出申請和釋放的時間分布等等，所以這是一種非常好的方式。

我這里實測某個平臺，freertos得malloc和free執行時間如下(注意執行時間硬件平臺不一樣也不一樣)，可以看到時間抖動較大，時間也不短，4.6uS已經算很長了，比如中斷中做時序解析這個時間很可能就難以滿足需求。

后面我們對比修改為我們高效的內存池實現的對比測試，可以看到基本無抖動，且執行時間非常短(這里還未去掉翻轉IO函數本身的執行和IO響應時間)。從匯編代碼其實也可以看出指令很少了。

三.?內存池實現

常規設計

將一塊空間劃分為n個等大小的塊，前面用一個字段標記是否使用的標記，剩余部分作為有效存儲空間。初始化全部是空閑，標記都是0，需要申請時從頭開始搜索，搜索到標記為0的塊則可申請將標記改為1，釋放則直接匹配地址將對應的標記設置為0.

上述標記至少需要占用一個字節，并且插入到有效塊前會影響有效塊的對齊屬性，所以還可以優化，標記信息單獨使用bitmap記錄，如下所示，

有效塊可以按照需要的原始數據結構連續對齊，bitmap一個bit對應一個塊，為1表示該塊已分配為0表示空閑，bitmap也減少了空間占用。申請釋放算法和原來類似，申請只是變為了搜索bitmap的最低字節最低位開始的0的位置將其設置為1，獲取對應的塊地址，釋放則是根據地址計算bitmap的bit索引將對應的bit設置為0.

高效無時間抖動設計

上述bitmap實現在存儲上已經優化了，但是在執行時間上因為要遍歷搜尋所以是有抖動的，那么要滿足我們的無時間抖動設計，目標就是要實現查找最低字節最低為開始的0的位置的算法時間固定。我們前面很多文章其實已經提到了矛盾的思想即，從矛盾的角度看問題，要解決一個問題可以看其對立面，因為往往矛盾是此消彼長的，算法的時間和空間就是矛盾體，要求時間那么我們就去看看是否能從空間的角度去考慮，一種常見的空間換時間的方法就是查表法，查表一方面時間固定一方面也高效。實際在uSOSII的實現中，查找最高就緒優先級就使用了該算法，我們直接拿過來使用并簡單介紹下其原理。

首先我們將bitmap按照矩陣排列，自然而然地想到以字節為列，bit0~7對應0~7列，多個字節對應多行。每個bit對應一個塊，bit為1表示空閑，為0表示占用。

那么最低字節的最低位位1則是我們要找的空閑塊。那么如何快速找到這個bit呢，常規思想是從字節0開始找，如果全為0則繼續找字節1，找到不為0的字節，然后從bit0到bit7找最開始出現的1的位置，那么這個bit在整個bit的索引就是(字節序號*8+位序號).

所以時間上可以分解為兩步，第一步是找字節位置，第二步找bit位置。

找bit位置實際我們可以很快想到通過查表法實現。

8為數據有256種可能，每一種可能我們直接將其最低出現1的位置寫出來就行，實際就是構造一個256字節的數組表，其指定索引的值，就是這個索引對應的數字，其最先出現1的bit位置。

比如

00000000 沒有1則最低最先出現1的位置是0，所以數組索引1的位置值為0

00000001 最先出現1的位置是bit0，所以數組索引1的位置值為0

00000010 最先出現1的位置是bit1，所以數組索引2的位置值為1

00000011 最先出現1的位置是bit0，所以數組索引3的位置值為0

00000100 最先出現1的位置是bit2，所以數組索引4的位置值為2

所以最終構造出如下表格

static uint8_t ?const ?s_unmaptbl[256] = {? ? 0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, ? ? ? /* 0x00 to 0x0F ? ? ? ? ? ? ? ? ? ? ? ? ? ? */? ? 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, ? ? ? /* 0x10 to 0x1F ? ? ? ? ? ? ? ? ? ? ? ? ? ? */? ? 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, ? ? ? /* 0x20 to 0x2F ? ? ? ? ? ? ? ? ? ? ? ? ? ? */? ? 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, ? ? ? /* 0x30 to 0x3F ? ? ? ? ? ? ? ? ? ? ? ? ? ? */? ? 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, ? ? ? /* 0x40 to 0x4F ? ? ? ? ? ? ? ? ? ? ? ? ? ? */? ? 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, ? ? ? /* 0x50 to 0x5F ? ? ? ? ? ? ? ? ? ? ? ? ? ? */? ? 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, ? ? ? /* 0x60 to 0x6F ? ? ? ? ? ? ? ? ? ? ? ? ? ? */? ? 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, ? ? ? /* 0x70 to 0x7F ? ? ? ? ? ? ? ? ? ? ? ? ? ? */? ? 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, ? ? ? /* 0x80 to 0x8F ? ? ? ? ? ? ? ? ? ? ? ? ? ? */? ? 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, ? ? ? /* 0x90 to 0x9F ? ? ? ? ? ? ? ? ? ? ? ? ? ? */? ? 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, ? ? ? /* 0xA0 to 0xAF ? ? ? ? ? ? ? ? ? ? ? ? ? ? */? ? 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, ? ? ? /* 0xB0 to 0xBF ? ? ? ? ? ? ? ? ? ? ? ? ? ? */? ? 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, ? ? ? /* 0xC0 to 0xCF ? ? ? ? ? ? ? ? ? ? ? ? ? ? */? ? 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, ? ? ? /* 0xD0 to 0xDF ? ? ? ? ? ? ? ? ? ? ? ? ? ? */? ? 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, ? ? ? /* 0xE0 to 0xEF ? ? ? ? ? ? ? ? ? ? ? ? ? ? */? ? 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0 ? ? ? ?/* 0xF0 to 0xFF ? ? ? ? ? ? ? ? ? ? ? ? ? ? */};

現在查找字節最開始出現1的位置查表一步就得到了時間是固定的，那么查找字節按照前面介紹還是的從字節0開始查詢最開始不是0的字節。我們仔細思考一下，前面一個字節8個bit一行的角度去查找最開始的1是對應的列，現在查找字節不就是對應的行嗎。

那么我們把每一行是否是0先記錄下來，再用一個bitmap來記錄這一行是否為0不就行了嗎。如下所示我們原來的bitmap有8個字節，8行，那么我們再使用一個字節8個bit就可以記錄這8個字節是否為0了，這個新增的bitmap我們叫做grp。

如果原來bitmap的字節1為0則grp的bit0為0，否則為1表示這個字節中有1即有空閑塊。那么問題簡單了，查找這8個字節，最低字節不為0的字節，即查找這個grp的最低位最先出現的1，這樣問題歸一了，就是我們前面的查表。這樣要找最低字節的最低先出現的1就是兩步查表，先根據grp查找到字節位置，然后根據這個字節的值查找bit位置。最終的索引就是”字節位置*8+bit位置”

最終算法實現如下

y = s_unmaptbl[dev->grp];? ? x = s_unmaptbl[dev->tbl[y]];? ? index = (uint8_t)((y<<3) + x);

這里的dev->grp即我們上面的grp字節，

Dev->tbl即bitmap字節數組。

y即字節位置，x即bit位置，index即bitmap的索引位置。

而找bitmap索引將對應的bit改為0即申請，操作如下，index>>3得到字節索引，~(1u<<(index & 0x07)是清除對應的bit。如果這個字節變為了0，則相應的grp字節的對應bit也要清零

? ? ? if(((dev->tbl[index>>3] &= (~(1u<<(index & 0x07)))) == 0))? ? ? ? {? ? ? ? ? ? dev->grp &= ~(1u<<(index>>3));? ? ? ? }

釋放則是將bitmap對應索引位置的bit置為1，

? ? dev->grp |= 1u<<(index>>3);? ? dev->tbl[index>>3] |= 1u<<(index & 0x07);

舉例如下

Tbl的2~7字節都非0所以，grp的bit2~bit7都為1，

tbl中最低字節最低位出現的1是字節2的bit3.

計算過程如下，先grp=0xFC=252查表得到，索引252處的值為2，所以定位到字節2

Tbl[2]的值為0x08，查表得到該索引對應的值是3

所以最開始出現1的位置是字節2的bit3，即2*8+3=19.

源碼如下

Mem_pool.c

#include "mem_pool.h"
static uint8_t ?const ?s_unmaptbl[256] = {? ? 0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, ? ? ? /* 0x00 to 0x0F ? ? ? ? ? ? ? ? ? ? ? ? ? ? */? ? 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, ? ? ? /* 0x10 to 0x1F ? ? ? ? ? ? ? ? ? ? ? ? ? ? */? ? 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, ? ? ? /* 0x20 to 0x2F ? ? ? ? ? ? ? ? ? ? ? ? ? ? */? ? 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, ? ? ? /* 0x30 to 0x3F ? ? ? ? ? ? ? ? ? ? ? ? ? ? */? ? 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, ? ? ? /* 0x40 to 0x4F ? ? ? ? ? ? ? ? ? ? ? ? ? ? */? ? 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, ? ? ? /* 0x50 to 0x5F ? ? ? ? ? ? ? ? ? ? ? ? ? ? */? ? 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, ? ? ? /* 0x60 to 0x6F ? ? ? ? ? ? ? ? ? ? ? ? ? ? */? ? 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, ? ? ? /* 0x70 to 0x7F ? ? ? ? ? ? ? ? ? ? ? ? ? ? */? ? 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, ? ? ? /* 0x80 to 0x8F ? ? ? ? ? ? ? ? ? ? ? ? ? ? */? ? 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, ? ? ? /* 0x90 to 0x9F ? ? ? ? ? ? ? ? ? ? ? ? ? ? */? ? 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, ? ? ? /* 0xA0 to 0xAF ? ? ? ? ? ? ? ? ? ? ? ? ? ? */? ? 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, ? ? ? /* 0xB0 to 0xBF ? ? ? ? ? ? ? ? ? ? ? ? ? ? */? ? 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, ? ? ? /* 0xC0 to 0xCF ? ? ? ? ? ? ? ? ? ? ? ? ? ? */? ? 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, ? ? ? /* 0xD0 to 0xDF ? ? ? ? ? ? ? ? ? ? ? ? ? ? */? ? 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, ? ? ? /* 0xE0 to 0xEF ? ? ? ? ? ? ? ? ? ? ? ? ? ? */? ? 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0 ? ? ? ?/* 0xF0 to 0xFF ? ? ? ? ? ? ? ? ? ? ? ? ? ? */};
int mem_pool_init(mem_pool_st* dev, void* buffer, void* tbl, uint32_t itemsize, uint32_t itemnum){? ? #if MEM_POOL_PARAM_CHECK? ? ? ? if(dev == (mem_pool_st*)0)? ? ? ? {? ? ? ? ? ? return -1;? ? ? ? }? ? ? ? if((buffer == (void*)0) || (tbl == (void*)0))? ? ? ? {? ? ? ? ? ? return -1;? ? ? ? }? ? #endif? ? dev->buffer = buffer;? ? dev->itemnum = itemnum;? ? dev->itemsize = itemsize;? ? dev->grp = (uint8_t)0xFF;? ? dev->tbl = tbl;? ? for(uint32_t i=0; i< (dev->itemnum+7)/8; i++)? ? {? ? ? ? dev->tbl[i] = (uint8_t)0xFF;? ? }? ? return 0;}
uint8_t* mem_pool_malloc(mem_pool_st* dev){? ? /* 查找最靠前的,空閑的塊 */#if MEM_POOL_PARAM_CHECK? ? if(dev == (mem_pool_st*)0)? ? {? ? ? ? return (void*)0;? ? }? ? if((dev->buffer == (void*)0) || (dev->tbl == (uint8_t*)0))? ? {? ? ? ? return (void*)0;? ? }#endif
? ? uint8_t y;? ? uint8_t x;? ? uint8_t index;? ? y = s_unmaptbl[dev->grp];? ? x = s_unmaptbl[dev->tbl[y]];? ? index = (uint8_t)((y<<3) + x);? ? if((index == 0) && (dev->tbl[0]==0))? ? {? ? ? ? /* 找到的索引為0,且對應的tbl為0, 說明bitmap所有位都為0,即無空閑 */? ? ? ? return (void*)0;? ? }? ? else? ? {? ? ? ? /* 對應bit置0,表示已經占用 */? ? ? ? if(((dev->tbl[index>>3] &= (~(1u<<(index & 0x07)))) == 0))? ? ? ? {? ? ? ? ? ? dev->grp &= ~(1u<<(index>>3));? ? ? ? }? ? ? ? /* 返回對應的地址 */? ? ? ? return dev->buffer + dev->itemsize*index;? ? }}
int mem_pool_free(mem_pool_st* dev, uint8_t* buffer){#if MEM_POOL_PARAM_CHECK? ? if(dev == (mem_pool_st*)0)? ? {? ? ? ? return -1;? ? }? ? if((dev->buffer == (void*)0) || (dev->tbl == (uint8_t*)0))? ? {? ? ? ? return -1;? ? }#endif
#if MEM_POOL_ERR_CHECK? ? if(buffer == (void*)0)? ? {? ? ? ? return -2;? ? }#endif? ? uint8_t index;? ? index = (buffer - dev->buffer)/dev->itemsize;#if MEM_POOL_ERR_CHECK? ? if(((dev->grp & (1u<<(index>>3))) != 0) && ((dev->tbl[index>>3] & (1u<<(index & 0x07))) != 0))? ? {? ? ? ? /* 釋放空閑的塊 */? ? ? ? return -3;? ? }#endif? ? /* 設置對應bit位置為1表示空閑 */? ? dev->grp |= 1u<<(index>>3);? ? dev->tbl[index>>3] |= 1u<<(index & 0x07);? ? return 0;}

Mem_pool.h

#ifndef MEM_POOL_H#define MEM_POOL_H
#ifdef __cplusplusextern "C" {#endif? #include 
#define MEM_POOL_PARAM_CHECK 1#define MEM_POOL_ERR_CHECK 1
typedef struct{? ? uint32_t ? grp;? ? uint32_t ? itemsize; /**< 區塊大小 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? */? ? uint32_t ? itemnum; ?/**< 總區塊數,8的倍數,最多256 ? ? ? ? ? ? ? ?*/? ? uint8_t* ? buffer; ? /**< 用戶提供的緩存區,大小為itemsize*itemnum ?*/? ? uint8_t* ? tbl;} mem_pool_st;
int mem_pool_init(mem_pool_st* dev, void* buffer, void* tbl, uint32_t itemsize, uint32_t itemnum);uint8_t* mem_pool_malloc(mem_pool_st* dev);int mem_pool_free(mem_pool_st* dev, uint8_t* buffer);
#ifdef __cplusplus}#endif
#endif

四.?實測

我們將其替換到我們某個驅動的實現中的malloc和free調用，測試功能OK，并按照二測試其時間抖動和執行時間，確認執行時間非常短，且基本無抖動。

初始化代碼如下

? #define TRANS_POOL_NUM 64? ? #define GROUP_POOL_NUM 64? ? static dma_trans_t s_trans_buffer[TRANS_POOL_NUM];? ? static uint8_t s_trans_bitmap_buffer[(TRANS_POOL_NUM+7)/8];? ? static mem_group_info_t s_group_buffer[GROUP_POOL_NUM];? ? static uint8_t s_group_bitmap_buffer[(GROUP_POOL_NUM+7)/8];
? ? mem_pool_st s_trans_mem_pool_dev;? ? mem_pool_st s_group_mem_pool_dev;? ? mem_pool_init(&s_trans_mem_pool_dev, s_trans_buffer, s_trans_bitmap_buffer, sizeof(dma_trans_t), TRANS_POOL_NUM);? ? mem_pool_init(&s_group_mem_pool_dev, s_group_buffer, s_group_bitmap_buffer, sizeof(mem_group_info_t), GROUP_POOL_NUM);

申請

trans = (dma_trans_t *)mem_pool_malloc(&s_trans_mem_pool_dev);

釋放

mem_pool_free(&s_trans_mem_pool_dev, trans);

五.?總結

以上我們借鑒uCOSII中的算法應用到我們自己設計的內存池輪子上，實現了高效且無時間抖動的內存池實現，是一個非常有用的輪子。這也提醒我們平常多注意借鑒參考別人的思想實現，并為己所用，不斷積累。

以上實際使用的是bitmap查表實現固定時間，使用二維bitmap來擴充容量，上述例子是支持最大塊數64個即8x8。如果要擴充更大的塊數怎么辦呢，自然想到得是增加二維的X/Y即可，即可將tbl和grp由8位改為16位，但是這存在一個問題，改為16位查表的表有2^16種情況,需要64k這在嵌入式中很可能是不可接受的。我們再來思考前面tbl擴展到grp，即X擴展到Y的過程，即一維擴展到二維的過程，我們是不是突然眼前一亮，拍案而起，甚至有點激動了，是的很自然的我們可以再增加一維變為三維，即對于體中點得位置，可以先找面，再找行，再找行中的bit點，就是這么簡單自然，所以只需要將grp也改為數組即可，再增加一個vol字節對grp數組進行記錄，vol一個bit 記錄grp一個字節是否為0。所以我們要從本質去理解一項技術才可能是正真得理解，比好比這個查表從維度擴充角度去思考這才是本質，懂了這個本質自然會擴充，并為己所用應用到其他場景，而不是糾結于查表等技術細節，糾結于這些實際并沒有理解本質，也僅僅會這個案例而已很難舉一反三，這也是我們為什么思考問題一定要思考到本質，為什么我一直強調思考技術問題一定要思考到背后的本質甚至哲學意義，背后的原理甚至哲學意義才是普適得本質原理。

我們通過增加維度實現擴充，這就是降維打擊，三階搜尋變為了三次查表，有點類似”對數的本質是把乘除法降維成加減法”，也許四維度空間生物看我們三維空間的生物是多么的藐視了。

不由的要感嘆世界的奇妙，也許只有造物主能做到，能夠降維實際也是一種普遍的現象，可能也是造物主雖然沒有讓我們活在高維世界但是給我們開了個后門，讓我們擁有了對高維進行降維分析的能力，對數降維，投影降維等都類似，可以讓我們從側面推測全貌，不知道能否從數學抽象角度來建立體系，證明具備何種屬性的空間具備可降維性，那么這就建立了一套分析高維的數理體系了。

登錄閱讀全文



免責聲明：該內容由專欄作者授權發布或作者轉載，目的在于傳遞更多信息，并不代表本網贊同其觀點，本站亦不保證或承諾內容真實性等。若內容或圖片侵犯您的權益，請及時聯系本站刪除。侵權投訴聯系：? nick.zong@aspencore.com！

嵌入式Lee

進入專欄

評論

嵌入式Lee

文章：323篇粉絲：23人

 私信