一文搞懂棧(stack)、堆(heap)、單片機裸機內存管理malloc

大家好，我是無際。

有一周沒水文了，俗話說夜路走多了難免遇到鬼。

最近就被一個熱心網友噴了。

說我的文章沒啥營養，所以今天來一篇燒腦的。

哈哈，開個玩笑，不要臉就沒人能把我綁架。

主要是最近研發第二代物聯網網關項目，必須要用到一個功能：內存管理。

溫馨提醒，全文4700多字，其中技術點是你進階到高手必須要學習的，最好，反復專注地看，否則可能會感覺在看天書。

說到內存管理大家會可能想到malloc和free函數。

在講這兩個函數之前，我們先來講講棧(Stack)和堆(heap)的概念。

1.棧(Stack)

我們單片機一般有個啟動文件，拿STM32F103來舉例。

這個Stack_Size就是棧大小，0x00000400就是代表有1K（0x400/1024）的大小。

那這個棧到底用來干嘛的呢？

比如說我們函數的形參、以及函數里定義的局部變量就是存儲在棧里，所以我們在函數的局部變量、數組這些不能超過1K(含嵌套的函數)，否則程序就會崩潰進入hardfaul。

除了這些局部變量以外，還有一些實時操作系統的現場保護、返回地址都是存儲在棧里面。

還有一點題外話，就是棧的增長方向是從高地址到低地址的，這個用得不多，暫時不需要去深究。

2.?堆(heap)

malloc()函數動態分配的內存就屬于堆的空間。

同樣，在單片機啟動文件里也有對堆大小的定義。

0x00000200就是代表有512個字節。

這意味著如果你用malloc()函數，那么最大分配的內存不能大于512字節，否則程序會崩潰。

網上很多文章說，全局變量和靜態變量是放在堆區。

但是我做了實驗，把堆的空間大小設置成0，程序正常運行并無影響。

這說明我們平時定義的全局變量、靜態變量是不存放在堆的，而是堆棧以外的另外一篇靜態空間區域，個人理解，如果有誤請指正。

Ok，那么我們簡單了解了堆和棧的概念，也知道malloc()函數分配的是堆的空間。

那么下面，我們探討一個問題，有現成的動態分配內存函數malloc()，為什么單片機卻很少用，為什么還要自己去做內存管理(自己寫代碼實現malloc()和free()等函數)？

malloc()函數經過成千上萬網友驗證，很容易出問題，所以一般單片機開發沒人敢用，除非是…。

而上位機很多就會用，因為lib庫里有寫好的內存管理的算法，并不適用于單片機。

malloc()用于單片機主要問題體現在容易產生內存碎片。

內存碎片是什么？

內存碎片就是分配了內存空間，但是未被使用的部分。

比如說你用malloc(1)分配了1個字節，但實際給你分配了8個字節的空間，剩余7個就是內存碎片。

那內存碎片是怎么產生的呢？

我們通過程序來演示一下：

我們在給p1和p2分配的時候，明明只分配1個字節，實際卻分配了8個字節的空間，在釋放前這7個字節都不能再被分配，相當于7個字節空間就浪費了。

這是其中一個產生碎片的方式，除此以外，還有別的方式會產生。

比如說你第一次連續申請了2個空間，第一塊是1個字節，第二塊也是1個字節。

理論上分配的空間地址都是連續的，但是中間產生7個字節內存碎片，分配兩塊的話就是14個字節。

當把第一塊1個字節釋放以后，第二塊1個字節的空間還沒釋放。

這樣相當于第一塊的空間只能用來分配1個左右字節的空間了(有可能還可以分配2-6個字節的)，具體要看Malloc()函數分配算法。

但可以肯定的是，不能分配像10個字節這么大的空間，那這塊空間的應用范圍就會縮小了很多。

如果一個程序分配很多1個字節這種小空間，那后面整個內存塊會有非常多這種碎片疊加。

最后會導致，明明有很多空閑內存，但是總是分配失敗，甚至導致程序崩潰。

所以，這就是要自己寫內存管理的原因，就是要解決內存碎片這種痛點。

內存管理由很多不同的子功能組成，比如說動態內存分配算法、內存釋放等等。

但是內存管理做起來是比較復雜的，涉及到數據結構和一些小算法。

有些高端的單片機為了幫工程師解決繁瑣的內存管理代碼，就內置了MMU(內存管理單元)模塊。

不過大多數單片機都沒有，我自己也沒用過，沒有的就要自己寫代碼去實現內存管理。

內存管理可以說是實時操作系統和自己寫程序架構的剛需，操作系統一般有自帶不用自己寫。

一、動態分配內存實際應用有哪些？

拿我們wifi報警主機這個項目為例。

1.用于任務靈活創建

我們的主機自己寫了一個小系統，有涉及到任務創建和調度。

我們在創建任務的時候就非常不靈活，需要手工去調整內核頭文件的任務數量。

最理想的狀態是系統內核文件不用修改任何東西，實際上沒動態內存分配根本做不到。

我們這個架構很多產品都能用，每個產品功能不一樣，所以任務數量也不一樣。

如果有動態內存分配，就可以給大家靈活地創建自己產品需要的任務，而不用手動改，甚至我都可以把架構的代碼都封裝成lib，直接提供函數接口給不同的工程師使用。

2.用于不確定數量的臨時數據

比如說我們主機有配對功能，就是可以通過無線通訊去學習探測器。

然后我們設置菜單有個探測器列表，列表會顯示所有已配對的探測器。

如果要把全部已經配對的探測器都顯示出來，比如說我主機總共支持配對20個探測器。

那我就要實現定義出能夠裝下20個探測器的結構體數組。

最慘的是，還需要定義成靜態的，不然下次進入這個函數，數據又丟了。

而如果我不在這個菜單的時候，實際上這塊內存是浪費了的，如果有動態內存分配，那絕對是相見恨晚。

如果你還不會，趕緊學，遲早用得上！

二、內存管理如何實現？

以前我就在網上找了很多資料和例程，一邊找一邊罵，結果還是以失敗告終。

這塊是我一直想突破，一直無法突破的痛，以前也做過，但是一直無法很好地解決碎片問題。

最近運氣好，經過一個高手推薦，在Github上嫖到了大神寫的內存管理代碼。

代碼給你沒用，知識嘛，學到才是自己的，哈哈。

下載下來，先深度研究，吃透以后改了個小BUG和一些細節代碼，搞成Keil能編譯的版本。

測試平臺是我們的wifi報警項目硬件，基于STM32F103。

下圖調試測試環節的痛苦過程。

是不是有種頭皮發麻的感覺？那就對了! 碼農的腦子從來沒有舒服過。

下面是測試數據(有點長，只截取了3/4)：

密密麻麻的數據上一行是地址，為了方便調試和顯示，我限制了最大只能分配120個字節，然后地址一個字節夠用，就把高3個字節地址去掉了。

下一行是數據，2行一組，如下圖所示。

Ok，下面進入本篇文章高潮部分，算法如何實現？

1.算法原理

本質就是在一個數組里面玩結構體指針，數組作為內存池。

先定義一個很大的數組，你最大支持多大內存分配，就定義多大的數組，比如說我目前最大支持120個字節，MEM_SIZE就是120。

2.數組存儲方式

我們每一次分配內存給這塊內存做一張”表格”，”表格”里面記錄這塊內存的信息。

表格用程序來表示就是結構體，因為只有結構體能表示不同類型數據的集合。

這個“表格”一共會記錄內存塊3個信息：內存塊數據的存儲地址、內存塊大小、內存塊ID。

這3個信息是為后面寫動態內存分配和釋放內存函數作鋪墊的，目的是更好地尋找到指定的內存塊。

相當于每動態分配一塊內存，都會在內存池(數組)里面分配兩塊內存空間。

一塊內存是用來存儲這塊內存唯一的表格(結構體)，根據結構體成員計算的話就是固定的8個字節。

另一塊內存就是實際你需要分配的內存空間大小，最終你的數據就是存在這塊內存里。

比如說，當我調用動態內存分配函數mem_malloc(10)，分配了10個字節的內存空間，并且全部寫入值1。

完成以后，內存池的存儲結構如下：

然后，我再調用動態內存分配函數mem_malloc(8)，又分配了8個字節的內存空間，并且全部值寫入2。

完成以后，內存池的存儲結構變化如下：

經過這兩次分配內存以后，不知道你發現了沒有。

內存是連續分配的，沒有碎片。

內存低地址空間保存內存塊信息(“表格”)，高地址空間分配用戶的緩存，有沒有感覺跟前面堆棧的使用一樣？都是往內存空間中間分配。

數據的低位存儲在內存的低地址中數據的低位存儲在內存的低地址中(即小端模式)

3. mem_malloc()動態內存分配函數

mem_malloc()函數就是以上面說的分配原理，然后用代碼去實現，源代碼如下：

這個函數相對簡單，注釋也詳細，大家可以自己研究下。

4.mem_free()內存釋放函數

真正的難點也就是在這個函數，主要是去碎片的算法。

先貼上這個函數的代碼：

實現原理：

比如我現在動態分配了3塊內存空間,每個內存塊對應信息如下。

內存塊1：

內存地址-94 00 00 20(十六進制)，轉換成高位在前就是0x20000094

內存大小-0a 00，換算成10進制就是10個數據，代表緩存區大小是10個字節

內存ID-01 00，每個內存塊ID都不同，自動遞增

緩存區-0x20000094這個地址存儲的數據，我程序初始化為全是1。

內存塊2：

內存地址-?8c 00 00 20 (十六進制)，轉換成高位在前就是0x2000008c

內存大小-?08 00，換算成10進制就是8個數據，代表緩存區大小是8個字節

內存ID-02 00，每個內存塊ID都不同，自動遞增

緩存區-0x2000008c這個地址存儲的數據，我程序初始化為全是2。

內存塊3：

內存地址-?78 00 00 20 (十六進制)，轉換成高位在前就是0x20000078

內存大小-?14 00，換算成10進制就是20個數據，代表緩存區大小是20個字節

內存ID-03 00，每個內存塊ID都不同，自動遞增

緩存區-0x20000078這個地址存儲的數據，我程序初始化為全是3。

最終內存池里的結構就是這樣的。

Ok，這個時候我調用內存釋放函數mem_free(2)，把內存塊2的空間釋放掉。

釋放完以后，內存池的存儲結構就成下圖了。

從圖中可以看出，內存塊2的內存表格信息和緩存區的數據都被內存塊3替代了。

所以mem_free(2)函數實現步驟大概如下：

第一步：先通過ID找到要釋放的內存塊表格信息，表格信息里有緩存區的地址。

第二步：通過內存塊2的信息可以計算出內存塊3的表格地址。

第三步：把內存塊3的緩存區數據遷移并覆蓋到內存塊2的緩存區 (也就是8個字節)。

第四步：內存塊3往內存空間高字節地址遷移8個字節(內存塊2緩存區大小)后，會多8個字節數據出來，值為3，把這8個字節數據清零。

第五步：把內存塊2的表格信息替換成內存塊3的表格信息

第六步：更新內存塊3表格信息里的緩存區地址改成最新的地址。

第六步：最后把原來存儲內存塊3表格信息地址的數據清掉，因為內存塊3表格信息此時已在內存塊2表格的位置。

這個步驟，估計大家已經看暈了。

這個不是寫給你現在看的，想要理解這個代碼，最好就是用串口把數據打印出來，一用看數據一邊用st-link仿真分析程序。

如果沒思路，再看我這個流程。

實現思路最重要，有這個思路完全可以自己寫代碼去實現。

至此，整個內存管理分析分享到此結束。

這個內存管理的代碼還是需要進一步優化才能真正用在項目上。

比如說：

1.現在動態分配內存是返回內存塊ID，實際最好返回分配出來的緩存區地址。

2.釋放內存是傳遞內存塊ID，實際最好傳遞緩存區地址。

3.分配和釋放內存前要進入臨界

這個就靠大家自己去優化了，我會把優化好的版本共享給我們的學員。

如果要這個版本的源代碼，可以找無際拿。

最后，目前我發現這個內存管理代碼唯一不足的地方就是每分配一塊內存都要額外增加8個字節來存儲內存塊表格信息。

源代碼是12個字節，被我干掉了4個，實際如果單次分配不超過256個字節，6個字節就夠用)。

不過，這算是我目前見過最好的了，如果還有更好的，麻煩分享給我，感謝！

這篇文章寫了將近6個小時，前期研究、測試代碼花了3天，又少了海量頭發，如果對你有幫助，麻煩，轉發，讓更多人收益！

單片機 數據結構

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。