[導(dǎo)讀] 前文描述了棧的基本概念，本文來聊聊堆是怎么會事兒。RT-Thread 在社區(qū)廣受歡迎，閱讀了其內(nèi)核代碼，實(shí)現(xiàn)了堆的管理，代碼設(shè)計(jì)很清晰，可讀性很好。故一方面了解RT-Thread內(nèi)核實(shí)現(xiàn)，一方面可以弄清楚其堆的內(nèi)部實(shí)現(xiàn)。將學(xué)習(xí)體會記錄分享，希望對于堆的理解及實(shí)現(xiàn)有一個更深入的認(rèn)知。

注，文中代碼分析基于rt-thread-v4.0.2 版本。

什么是堆？

C語言堆是由malloc(),calloc(),realloc()等函數(shù)動態(tài)獲取內(nèi)存的一種機(jī)制。使用完成后，由程序員調(diào)用free()等函數(shù)進(jìn)行釋放。使用時(shí)，需要包含stdlib.h頭文件。

C++預(yù)言的堆管理則是使用new操作符向堆管理器申請動態(tài)內(nèi)存分配，使用delete操作符將使用完畢內(nèi)存的釋放給堆管理器。

注：本文只描述C的堆管理器實(shí)現(xiàn)相關(guān)內(nèi)容。

以C語言為例，將上面的描述，翻譯成一個圖：

要動態(tài)管理一片內(nèi)存，且需要動態(tài)分配釋放，這樣一個需求。很顯然C語言需要將動態(tài)內(nèi)存區(qū)抽象描述起來并實(shí)現(xiàn)動態(tài)管理。事實(shí)上，C語言中堆管理器其本質(zhì)是利用數(shù)據(jù)結(jié)構(gòu)將堆區(qū)抽象描述，所需要描述的方面：

• 可用于分配的內(nèi)存
• 正在使用的內(nèi)存塊
• 釋放掉的內(nèi)存塊

再利用相應(yīng)算法對于這類數(shù)據(jù)結(jié)構(gòu)對象進(jìn)行動態(tài)管理而實(shí)現(xiàn)的堆管理器。

**經(jīng)?？吹礁鞣N算法書很多只講算法原理，而不講應(yīng)用實(shí)例，往往體會不深。私以為可以做些改善。學(xué)而不能致用，何必費(fèi)力去學(xué)。所以不是晦澀難懂的算法無用，而是沒有去真正結(jié)合應(yīng)用?？梢栽龠M(jìn)一步想，如果算法沒有應(yīng)用場景，也一定會在技術(shù)發(fā)展的歷程中逐漸被世人遺忘。所以建議學(xué)習(xí)閱讀算法書籍時(shí)，找些實(shí)例來看看，一定會加深對算法的理解領(lǐng)悟。**這是比較重要的題外話，送給大家以共勉。

所以從本質(zhì)上講，堆管理器就是數(shù)據(jù)結(jié)構(gòu)+算法實(shí)現(xiàn)的動態(tài)內(nèi)存管理器，管理內(nèi)存的動態(tài)分配以及釋放。

為什么要堆？

C編程語言對內(nèi)存管理方式有靜態(tài)，自動或動態(tài)三種方式。靜態(tài)內(nèi)存分配的變量通常與程序的可執(zhí)行代碼一起分配在主存儲器中，并在程序的整個生命周期內(nèi)有效。自動分配內(nèi)存的變量在棧上分配，并隨著函數(shù)的調(diào)用和返回而申請或釋放。對于靜態(tài)分配內(nèi)存和自動分配內(nèi)存的生命周期，分配的大小必須是編譯時(shí)常量（可變長度自動數(shù)組[5]除外）。如果所需的內(nèi)存大小直到運(yùn)行時(shí)才知道（例如，如果要從用戶或磁盤文件中讀取任意大小的數(shù)據(jù)），則使用固定大小的數(shù)據(jù)對象則滿足不了要求了。試想，即便假定都知道要多大內(nèi)存，如在windows/Linux下有那么多應(yīng)用程序，每個應(yīng)用程序加載時(shí)都將運(yùn)行中所需的內(nèi)存采樣靜態(tài)分配策略，則如多個程序運(yùn)行內(nèi)存將很快耗盡。

分配的內(nèi)存的生命周期也可能引起關(guān)注。靜態(tài)或自動分配都不能滿足所有情況。自動分配內(nèi)存不能在多個函數(shù)調(diào)用之間保留，而靜態(tài)數(shù)據(jù)在程序的整個生命周期中必然保留，無論是否真正需要（所以都采用這樣的策略必然造成浪費(fèi)）。在許多情況下，程序員在管理分配的內(nèi)存的生命周期具有更多的靈活性。

通過使用動態(tài)內(nèi)存分配則避免了這些限制/缺點(diǎn)，在動態(tài)內(nèi)存分配中，更明確（但更靈活）地管理內(nèi)存，通常是通過從免費(fèi)存儲區(qū)（非正式地稱為“堆”）中分配內(nèi)存（為此目的而構(gòu)造的內(nèi)存區(qū)域）進(jìn)行分配的。在C語言中，庫函數(shù)malloc用于在堆上分配一個內(nèi)存塊。程序通過malloc返回的指針訪問該內(nèi)存塊。當(dāng)不再需要內(nèi)存時(shí)，會將指針傳遞給free，從而釋放內(nèi)存，以便可以將其用于其他目的。

誰實(shí)現(xiàn)堆

如果一問道這個問題，馬上會說C編譯器。不錯C編譯器實(shí)現(xiàn)了堆管理器，而事實(shí)上并非編譯器在編譯的過程中實(shí)現(xiàn)動態(tài)內(nèi)存管理器，而是C編譯器所實(shí)現(xiàn)的C庫實(shí)現(xiàn)了堆管理器，比如ANSI C，VC, IAR C編譯器，GNU C等其實(shí)都需要一些C庫的支持，那么這些庫的內(nèi)部就隱藏了這么一個堆管理器。眼見為實(shí)吧，還是以IAR ARM 8.40.1 為例，其堆管理器就實(shí)現(xiàn)在：

.\IAR Systems\Embedded Workbench 8.3\arm\src\lib\dlib\heap

一看有這么多的源碼，那么對于應(yīng)用開發(fā)而言，有哪些選項(xiàng)需要進(jìn)行配置呢？

支持四個選項(xiàng)：

• Automatic：
• 如果您的應(yīng)用程序中有對堆內(nèi)存分配例程的調(diào)用，但沒有對堆釋放例程的調(diào)用，則鏈接程序?qū)⒆詣舆x擇無空閑堆。
• 如果您的應(yīng)用程序中有對堆內(nèi)存分配例程的調(diào)用，則鏈接程序會自動選擇高級堆。
• 例如，如果在庫中調(diào)用了堆內(nèi)存分配例程，則鏈接程序會自動選擇基本堆。
• Advanced heap:高級堆（--advanced_heap）為廣泛使用該堆的應(yīng)用程序提供有效的內(nèi)存管理。特別是，重復(fù)分配和釋放內(nèi)存的應(yīng)用程序可能會在空間和時(shí)間上獲得較少的開銷。高級堆的代碼明顯大于基本堆的代碼。
• Basic heap: 基本堆（--basic_heap）是一個簡單的堆分配器，適用于不經(jīng)常使用堆的應(yīng)用程序。特別是，它可以用于僅分配堆內(nèi)存而從不釋放堆內(nèi)存的應(yīng)用程序中?；径巡⒉皇翘貏e快，并且在反復(fù)釋放內(nèi)存的應(yīng)用程序中使用它很可能導(dǎo)致不必要的堆碎片化?；径训拇a遠(yuǎn)小于高級堆的大小。
• No-free heap:無可用堆（--no_free_heap）使用此選項(xiàng)可以使用最小的堆實(shí)現(xiàn)。因?yàn)榇硕巡恢С轴尫呕蛑匦路峙?，所以它僅適用于在啟動階段為各種緩沖區(qū)分配堆內(nèi)存的應(yīng)用程序，以及永不釋放內(nèi)存的應(yīng)用程序。

但是如果認(rèn)為僅僅標(biāo)準(zhǔn)C庫負(fù)責(zé)實(shí)現(xiàn)堆管理器，則這種理解并不全面。回到事物的本質(zhì)，堆管理器是利用數(shù)據(jù)結(jié)構(gòu)及算法動態(tài)管理一片內(nèi)存的分配與釋放。那么有這樣需求的地方，都可能需要實(shí)現(xiàn)一個堆管理器。

堆管理器的實(shí)現(xiàn)很大程度取決于操作系統(tǒng)以及硬件體系架構(gòu)。大體上需要實(shí)現(xiàn)堆內(nèi)存管理器的有兩大類：

• 應(yīng)用程序，應(yīng)用程序需要堆內(nèi)存管理器，是顯而易見的。比如常見的windows/Linux下的應(yīng)用程序，都需要堆內(nèi)存管理器。而上述的cortex M或者其他單片機(jī)程序使用C/C++編程時(shí)都需要堆內(nèi)存管理器。
• 操作系統(tǒng)內(nèi)核，操作系統(tǒng)內(nèi)核需要像應(yīng)用程序一樣分配內(nèi)存。但是，內(nèi)核中malloc的實(shí)現(xiàn)通常與C庫使用的實(shí)現(xiàn)有很大不同。例如，內(nèi)存緩沖區(qū)可能需要符合DMA施加的特殊限制，或者可能從中斷上下文中調(diào)用內(nèi)存分配功能。這需要與操作系統(tǒng)內(nèi)核的虛擬內(nèi)存子系統(tǒng)緊密集成的malloc實(shí)現(xiàn)。比如Linux內(nèi)核就需要實(shí)現(xiàn)內(nèi)核版本的堆管理器，對外提供kmalloc/vmalloc申請內(nèi)存，kfree/vfree用于釋放內(nèi)存。

怎么實(shí)現(xiàn)堆

對于RT-Thread的內(nèi)核而言，也實(shí)現(xiàn)了一個內(nèi)核堆管理器，這里就來梳理一下RT-Thread內(nèi)核版本的小堆管理器的實(shí)現(xiàn)，同時(shí)來了解一下鏈表數(shù)據(jù)結(jié)構(gòu)及算法操作的實(shí)例應(yīng)用。

其堆管理器實(shí)現(xiàn)位于.\rt-thread-v4.0.2\rt-thread\src下mem.c，memheap.c以及mempool.c。

關(guān)鍵數(shù)據(jù)結(jié)構(gòu)

其堆管理器主要的數(shù)據(jù)結(jié)構(gòu)為heap_mem。

• heap_mem
  
  

堆管理器初始化

堆管理器的初始化入口在mem.c，函數(shù)為：

void rt_system_heap_init(void *begin_addr, void *end_addr)
{
    struct heap_mem *mem;
    /*按4字節(jié)對齊轉(zhuǎn)換地址*/
    /*如0x2000 0001～0x2000 0003,轉(zhuǎn)后為0x2000 0004*/
    rt_ubase_t begin_align = RT_ALIGN((rt_ubase_t)begin_addr, RT_ALIGN_SIZE);
    /*如0x3000 0001～0x3000 0003,轉(zhuǎn)后為0x3000 0000*/
    rt_ubase_t end_align   = RT_ALIGN_DOWN((rt_ubase_t)end_addr, RT_ALIGN_SIZE);
    
    /*調(diào)試信息，函數(shù)不可用于中斷內(nèi)部*/
    RT_DEBUG_NOT_IN_INTERRUPT;

    /* 分配地址范圍至少能存儲兩個heap_mem */
    if ((end_align > (2 * SIZEOF_STRUCT_MEM)) &&
        ((end_align - 2 * SIZEOF_STRUCT_MEM) >= begin_align))
    {
        /* 計(jì)算可用堆區(qū)，4字節(jié)對齊 */
        mem_size_aligned = end_align - begin_align - 2 * SIZEOF_STRUCT_MEM;
    }
    else
    {
        rt_kprintf("mem init, error begin address 0x%x, and end address 0x%x\n",
                   (rt_ubase_t)begin_addr, (rt_ubase_t)end_addr);

        return;
    }

    /* heap_ptr指向堆區(qū)起始地址 */
    heap_ptr = (rt_uint8_t *)begin_align;

    RT_DEBUG_LOG(RT_DEBUG_MEM, ("mem init, heap begin address 0x%x, size %d\n",
                                (rt_ubase_t)heap_ptr, mem_size_aligned));

    /* 初始化堆起始描述符 */
    mem        = (struct heap_mem *)heap_ptr;
    mem->magic = HEAP_MAGIC;
    mem->next  = mem_size_aligned + SIZEOF_STRUCT_MEM;
    mem->prev  = 0;
    mem->used  = 0;
#ifdef RT_USING_MEMTRACE
    rt_mem_setname(mem, "INIT");
#endif

    /* 初始化堆結(jié)束描述符 */
    heap_end        = (struct heap_mem *)&heap_ptr[mem->next];
    heap_end->magic = HEAP_MAGIC;
    heap_end->used  = 1;
    heap_end->next  = mem_size_aligned + SIZEOF_STRUCT_MEM;
    heap_end->prev  = mem_size_aligned + SIZEOF_STRUCT_MEM;
#ifdef RT_USING_MEMTRACE
    rt_mem_setname(heap_end, "INIT");
#endif

    rt_sem_init(&heap_sem, "heap", 1, RT_IPC_FLAG_FIFO);

    /* 初始化釋放指針指向堆的開始 */
    lfree = (struct heap_mem *)heap_ptr;
}

傳入鏈接堆區(qū)的內(nèi)存起始地址，以及結(jié)束地址。以STM32為例，傳入0x20000000--0x20018000，96k字節(jié)

上述rt_system_heap_init( 0x20000000,0x20018000)，主要做了下圖這么一件事情。

將堆管理頭尾描述符進(jìn)行了初始化，并指向?qū)?yīng)的內(nèi)存地址。用圖翻譯一下：

技巧點(diǎn)：

• 利用類型強(qiáng)制轉(zhuǎn)換將內(nèi)存數(shù)據(jù)轉(zhuǎn)換為struct heap_mem *。實(shí)現(xiàn)了靜態(tài)雙鏈表的創(chuàng)建

mem      = (struct heap_mem *)heap_ptr;
heap_end = (struct heap_mem *)&heap_ptr[mem->next];

• 定義heap_mem沒有定義使用多少字節(jié)為該塊的用戶數(shù)據(jù)字節(jié)數(shù)，節(jié)約了內(nèi)存。是一個比較好的處理方式。
• 對齊方式可配置，RT_ALIGN_SIZE默認(rèn)為4字節(jié)。
  
  

向堆申請內(nèi)存

用戶調(diào)用rt_malloc 用于申請分配動態(tài)內(nèi)存。

void *rt_malloc(rt_size_t size)
{
    rt_size_t ptr, ptr2;
    struct heap_mem *mem, *mem2;

    if (size == 0)
        return RT_NULL;

    RT_DEBUG_NOT_IN_INTERRUPT;
    /*按四字節(jié)對齊申請，如申請5字節(jié)，則實(shí)際按8字節(jié)申請*/
    if (size != RT_ALIGN(size, RT_ALIGN_SIZE))
        RT_DEBUG_LOG(RT_DEBUG_MEM, ("malloc size %d, but align to %d\n",
                                    size, RT_ALIGN(size, RT_ALIGN_SIZE)));
    else
        RT_DEBUG_LOG(RT_DEBUG_MEM, ("malloc size %d\n", size));

    /* 按四字節(jié)對齊申請，如申請5字節(jié)，則實(shí)際按8字節(jié)申請 */
    size = RT_ALIGN(size, RT_ALIGN_SIZE);

    if (size > mem_size_aligned)
    {
        RT_DEBUG_LOG(RT_DEBUG_MEM, ("no memory\n"));
        return RT_NULL;
    }

    /* 每塊的長度必須至少為MIN_SIZE_ALIGNED=12 STM32*/
    if (size < MIN_SIZE_ALIGNED)
        size = MIN_SIZE_ALIGNED;

    /* 獲取堆保護(hù)信號量 */
    rt_sem_take(&heap_sem, RT_WAITING_FOREVER);

    for (ptr = (rt_uint8_t *)lfree - heap_ptr;
         ptr < mem_size_aligned - size;
         ptr = ((struct heap_mem *)&heap_ptr[ptr])->next)
    {
        mem = (struct heap_mem *)&heap_ptr[ptr];

        /*如果該塊未使用，且滿足大小要求*/
        if ((!mem->used) && (mem->next - (ptr + SIZEOF_STRUCT_MEM)) >= size)
        {
            /* mem沒有被使用，至少完美的配合是可能的:
             * mem->next - (ptr + SIZEOF_STRUCT_MEM) 計(jì)算出mem的“用戶數(shù)據(jù)大小” */
            if (mem->next - (ptr + SIZEOF_STRUCT_MEM) >=
                (size + SIZEOF_STRUCT_MEM + MIN_SIZE_ALIGNED))
            {
                /* (除了上面的，我們測試另一個結(jié)構(gòu)heap_mem (SIZEOF_STRUCT_MEM)
                 * 是否包含至少M(fèi)IN_SIZE_ALIGNED的數(shù)據(jù)也適合'mem'的'用戶數(shù)據(jù)空間')
                 * -> 分割大的塊，創(chuàng)建空的余數(shù),
                 * 余數(shù)必須足夠大，以包含MIN_SIZE_ALIGNED大小數(shù)據(jù):
                 * 如果mem->next - (ptr + (2*SIZEOF_STRUCT_MEM)) == size,
                 * struct heap_mem 會適合，在mem2及mem2->next沒有使用
                 */
                ptr2 = ptr + SIZEOF_STRUCT_MEM + size;

                /* create mem2 struct */
                mem2       = (struct heap_mem *)&heap_ptr[ptr2];
                mem2->magic = HEAP_MAGIC;
                mem2->used = 0;
                mem2->next = mem->next;
                mem2->prev = ptr;
#ifdef RT_USING_MEMTRACE
                rt_mem_setname(mem2, "    ");
#endif
                /*將ptr2插入mem及mem->next之間 */
                mem->next = ptr2;
                mem->used = 1;

                if (mem2->next != mem_size_aligned + SIZEOF_STRUCT_MEM)
                {
                    ((struct heap_mem *)&heap_ptr[mem2->next])->prev = ptr2;
                }
#ifdef RT_MEM_STATS
                used_mem += (size + SIZEOF_STRUCT_MEM);
                if (max_mem < used_mem)
                    max_mem = used_mem;
#endif
            }
            else
            {
                mem->used = 1;
#ifdef RT_MEM_STATS
                used_mem += mem->next - ((rt_uint8_t *)mem - heap_ptr);
                if (max_mem < used_mem)
                    max_mem = used_mem;
#endif
            }
            /* 設(shè)置塊幻數(shù) */
            mem->magic = HEAP_MAGIC;
#ifdef RT_USING_MEMTRACE
            if (rt_thread_self())
                rt_mem_setname(mem, rt_thread_self()->name);
            else
                rt_mem_setname(mem, "NONE");
#endif

            if (mem == lfree)
            {
                /* 尋找下一個空閑塊并更新lfree指針*/
                while (lfree->used && lfree != heap_end)
                    lfree = (struct heap_mem *)&heap_ptr[lfree->next];

                RT_ASSERT(((lfree == heap_end) || (!lfree->used)));
            }

            rt_sem_release(&heap_sem);
            RT_ASSERT((rt_ubase_t)mem + SIZEOF_STRUCT_MEM + size <= (rt_ubase_t)heap_end);
            RT_ASSERT((rt_ubase_t)((rt_uint8_t *)mem + SIZEOF_STRUCT_MEM) % RT_ALIGN_SIZE == 0);
            RT_ASSERT((((rt_ubase_t)mem) & (RT_ALIGN_SIZE - 1)) == 0);

            RT_DEBUG_LOG(RT_DEBUG_MEM,
                         ("allocate memory at 0x%x, size: %d\n",
                          (rt_ubase_t)((rt_uint8_t *)mem + SIZEOF_STRUCT_MEM),
                          (rt_ubase_t)(mem->next - ((rt_uint8_t *)mem - heap_ptr))));

            RT_OBJECT_HOOK_CALL(rt_malloc_hook,
                                (((void *)((rt_uint8_t *)mem + SIZEOF_STRUCT_MEM)), size));

            /* 返回除mem結(jié)構(gòu)之外的內(nèi)存地址 */
            return (rt_uint8_t *)mem + SIZEOF_STRUCT_MEM;
        }
    }
    /* 釋放堆保護(hù)信號量 */
    rt_sem_release(&heap_sem);

    return RT_NULL;
}

其基本思路，從空閑塊鏈表開始檢索內(nèi)存塊，如檢索到某塊空閑且滿足申請大小且其剩余空間至少能存儲描述符，則滿足了申請要求，則將后續(xù)內(nèi)存頭部生成描述，更新前后指針，標(biāo)記幻數(shù)以及塊已被使用標(biāo)記，將該塊插入鏈表。返回申請成功的內(nèi)存地址。如果檢索不到，則返回空指針，表示申請失敗，堆目前沒有滿足要求的內(nèi)存可供使用。實(shí)際上，上述代碼在運(yùn)行時(shí)將堆內(nèi)存區(qū)按照下述示意圖進(jìn)行動態(tài)維護(hù)。

概括一下：

• heap_ptr總是指向堆起始地址，heap_end總是指向最后一個塊，兩者配合可以實(shí)現(xiàn)邊界保護(hù)，在釋放內(nèi)存時(shí)使用。
• lfree 總是指向最地址最小的空閑塊，因此在動態(tài)申請內(nèi)存時(shí)，總是從該塊進(jìn)行檢索是否有滿足申請要求的內(nèi)存塊可供使用。
• used=1表示該塊被占用，非空閑。used=0表示該塊空閑。
• magic 字段幻數(shù)，起始就是一個特殊標(biāo)記字，與used=0配合，用于檢測異常，試想一下如果僅僅用used=0判斷塊是空閑，則易出錯，或者需要加其他的輔助代碼，才能保證代碼的健壯性。
• 動態(tài)內(nèi)存管理申請比較慢，需要檢索鏈表，以及額外的內(nèi)存開銷。
• rt_realloc 及rt_calloc 不做分析了

釋放內(nèi)存

釋放內(nèi)存由rt_free實(shí)現(xiàn)：

void rt_free(void *rmem)
{
    struct heap_mem *mem;

    if (rmem == RT_NULL)
        return;

    RT_DEBUG_NOT_IN_INTERRUPT;

    RT_ASSERT((((rt_ubase_t)rmem) & (RT_ALIGN_SIZE - 1)) == 0);
    RT_ASSERT((rt_uint8_t *)rmem >= (rt_uint8_t *)heap_ptr &&
              (rt_uint8_t *)rmem < (rt_uint8_t *)heap_end);

    RT_OBJECT_HOOK_CALL(rt_free_hook, (rmem));
    /* 申請釋放地址不在堆區(qū) */
    if ((rt_uint8_t *)rmem < (rt_uint8_t *)heap_ptr ||
        (rt_uint8_t *)rmem >= (rt_uint8_t *)heap_end)
    {
        RT_DEBUG_LOG(RT_DEBUG_MEM, ("illegal memory\n"));

        return;
    }

    /* 獲取塊描述符 */
    mem = (struct heap_mem *)((rt_uint8_t *)rmem - SIZEOF_STRUCT_MEM);

    RT_DEBUG_LOG(RT_DEBUG_MEM,
                 ("release memory 0x%x, size: %d\n",
                  (rt_ubase_t)rmem,
                  (rt_ubase_t)(mem->next - ((rt_uint8_t *)mem - heap_ptr))));


    /* 獲取堆保護(hù)信號量 */
    rt_sem_take(&heap_sem, RT_WAITING_FOREVER);

    /* 待釋放的內(nèi)存，其塊描述符需是使用狀態(tài) */
    if (!mem->used || mem->magic != HEAP_MAGIC)
    {
        rt_kprintf("to free a bad data block:\n");
        rt_kprintf("mem: 0x%08x, used flag: %d, magic code: 0x%04x\n", mem, mem->used, mem->magic);
    }
    RT_ASSERT(mem->used);
    RT_ASSERT(mem->magic == HEAP_MAGIC);
    /* 清除使用標(biāo)志 */
    mem->used  = 0;
    mem->magic = HEAP_MAGIC;
#ifdef RT_USING_MEMTRACE
    rt_mem_setname(mem, "    ");
#endif

    if (mem < lfree)
    {
        /* 更新空閑塊lfree指針 */
        lfree = mem;
    }

#ifdef RT_MEM_STATS
    used_mem -= (mem->next - ((rt_uint8_t *)mem - heap_ptr));
#endif

    /* 如臨近塊也處于空閑態(tài)，則合并整理成一個更大的塊 */
    plug_holes(mem);
    rt_sem_release(&heap_sem);
}
RTM_EXPORT(rt_free);

合并空閑塊plug_holes

static void plug_holes(struct heap_mem *mem)
{
    struct heap_mem *nmem;
    struct heap_mem *pmem;

    RT_ASSERT((rt_uint8_t *)mem >= heap_ptr);
    RT_ASSERT((rt_uint8_t *)mem < (rt_uint8_t *)heap_end);
    RT_ASSERT(mem->used == 0);

    /* 前向整理 */
    nmem = (struct heap_mem *)&heap_ptr[mem->next];
    if (mem != nmem &&
        nmem->used == 0 &&
        (rt_uint8_t *)nmem != (rt_uint8_t *)heap_end)
    {
        /*如果mem->next是空閑，且非尾節(jié)點(diǎn)，則合并*/
        if (lfree == nmem)
        {
            lfree = mem;
        }
        mem->next = nmem->next;
        ((struct heap_mem *)&heap_ptr[nmem->next])->prev = (rt_uint8_t *)mem - heap_ptr;
    }

    /* 后向整理 */
    pmem = (struct heap_mem *)&heap_ptr[mem->prev];
    if (pmem != mem && pmem->used == 0)
    {
        /* 如mem->prev空閑,將mem與mem->prev合并 */
        if (lfree == mem)
        {
            lfree = pmem;
        }
        pmem->next = mem->next;
        ((struct heap_mem *)&heap_ptr[mem->next])->prev = (rt_uint8_t *)pmem - heap_ptr;
    }
}

動態(tài)內(nèi)存的釋放相對比較簡單，其思路主要是判斷傳入地址是否在堆區(qū)，如是堆內(nèi)存，則判斷其塊信息是否合法。如果合法，則將使用標(biāo)志清除。同時(shí)如果臨近塊如果是空閑態(tài)，則利用plug_holes將空閑塊進(jìn)行合并，合并成一個大的空閑塊。

內(nèi)存泄漏

使用free釋放內(nèi)存失敗會導(dǎo)致不可重用內(nèi)存的累積，程序不再使用這些內(nèi)存。這將浪費(fèi)內(nèi)存資源，并可能在耗盡這些資源時(shí)導(dǎo)致分配失敗。

怎么使用堆

堆區(qū)的配置

對于STM32而言,位于board.h

/ * 配置堆區(qū)大小，可根據(jù)實(shí)際使用進(jìn)行修改 */
#define HEAP_BEGIN   STM32_SRAM1_START
#define HEAP_END     STM32_SRAM1_END

/* 用于板級初始化堆區(qū) */
void rt_system_heap_init(void *begin_addr, void *end_addr)

堆的使用接口

用于動態(tài)申請內(nèi)存
void *rt_malloc(rt_size_t size)
/*追加申請內(nèi)存，此函數(shù)將更改先前分配的內(nèi)存塊。*/
void *rt_realloc(void *rmem, rt_size_t newsize)
/* 申請的內(nèi)存被初始化為0 */
void *rt_calloc(rt_size_t count, rt_size_t size)

內(nèi)存分配不能保證成功，而是可能返回一個空指針。使用返回的值，而不檢查分配是否成功，將調(diào)用未定義的行為。這通常會導(dǎo)致崩潰，但不能保證會發(fā)生崩潰，因此依賴于它也會導(dǎo)致問題。

對于申請的內(nèi)存，使用前必須進(jìn)行返回值判斷，否則申請失敗，且任繼續(xù)使用。將會出現(xiàn)意想不到的錯誤！！

總結(jié)一下

通過對RT-Thread的小堆管理器實(shí)現(xiàn)的梳理，層層遞進(jìn)更深入理解以下一些要點(diǎn)：

• 為什么需要堆，為什么堆是C/C++運(yùn)行時(shí)的基礎(chǔ)之一。堆可實(shí)現(xiàn)動態(tài)內(nèi)存管理的多樣性，在犧牲一定開銷情況下（申請/釋放開銷，以及內(nèi)存開銷),可以提供內(nèi)存的利用率，在一定程度上解決內(nèi)存不足的需求。
• 可以更深入的理解鏈表實(shí)用價(jià)值，理解靜態(tài)實(shí)現(xiàn)方法的一些技巧。
• 通過更深入的理解堆的實(shí)現(xiàn)，可以更好的使用堆。
• 理解堆管理器究竟在哪里實(shí)現(xiàn)的，C/C++標(biāo)準(zhǔn)庫，以及操作系統(tǒng)內(nèi)核都可能實(shí)現(xiàn)堆管理器。
• RT-Thread的小堆實(shí)現(xiàn)是一個比較簡單和比較好的學(xué)習(xí)堆管理的例子，事實(shí)上堆的實(shí)現(xiàn)還有更復(fù)雜的場景，比如基于SLAB堆管理器實(shí)現(xiàn)，以及IAR中庫的堆實(shí)現(xiàn)還需要使用樹這個數(shù)據(jù)結(jié)構(gòu)。

堆使用常見錯誤

• 使用前沒有檢查分配失敗：內(nèi)存分配不能保證成功，而是可能返回一個空指針。使用返回的值，而不檢查分配是否成功，將調(diào)用未定義的行為。這通常會導(dǎo)致崩潰，但不能保證會發(fā)生崩潰，因此依賴于它也會導(dǎo)致問題。
• 內(nèi)存泄露：使用free釋放內(nèi)存失敗會導(dǎo)致不可重用內(nèi)存的累積，程序不再使用這些內(nèi)存。這將浪費(fèi)內(nèi)存資源，并可能在耗盡這些資源時(shí)導(dǎo)致分配失敗。
  邏輯錯誤：所有的分配必須遵循相同的模式:使用malloc分配，使用free存儲數(shù)據(jù)，重新分配。如果不能堅(jiān)持這種模式，例如在調(diào)用free(懸空指針)之后或在調(diào)用malloc(野生指針)之前使用內(nèi)存、調(diào)用free兩次(“double free”)等，通常會導(dǎo)致分段錯誤并導(dǎo)致程序崩潰。這些錯誤可能是暫時(shí)的，而且很難調(diào)試

  留言區(qū)
  

—END—