基于伙伴算法的动态内存管理算法

trochili

这个算法是我在最新版的trochili rtos中实现的，单独拿出来用也挺有意义的。如果有些同学想要移植到自己的系统中，注意重新定义一下数据类型。
不多说，上源码，看不懂的同学得先去看看buddy算法的核心二叉树的实现。这个buddy算法还是非常好用的。在这个实现里我顺便添加了bit位图来表示内存页是否被分配出去，防止二次释放的危险(某些著名的rtos可没这么友好)。

/* 动态内存管理配置 */
#define TCL_MEMORY_ENABLE              (1)
#define TCL_MEMORY_POOL_ENABLE         (1)
#define TCL_MEMORY_POOL_PAGES          (256U)
#define TCL_MEMORY_BUDDY_ENABLE        (1)
#define TCL_MEMORY_BUDDY_PAGES         (64)

/**************
*                                     Trochili RTOS Kernel                                      *
*                                  Copyright(C) 2015 LIUXUMING                                  *
*                                       www.trochili.com                                        *
**************/
#ifndef _TCL_MEMORY_BUDDY_H
#define _TCL_MEMORY_BUDDY_H

#include "tcl.types.h"
#include "tcl.config.h"
#include "tcl.memory.h"

#if ((TCL_MEMORY_ENABLE) && (TCL_MEMORY_BUDDY_ENABLE))

#define MEM_BUDDY_PAGE_TAGS  ((TCL_MEMORY_BUDDY_PAGES + 31u) >> 5u)
#define MEM_BUDDY_NODE_TAGS (TCL_MEMORY_BUDDY_PAGES * 2u - 1u)
#define MEM_PROP_READY (1)

typedef struct MemBuddyDef
{
    TProperty Property;                       /* 内存页池属性                      */
    TChar*    PageAddr;                       /* 被管理的内存的起始地址            */
    TWord     PageSize;                       /* 内存页大小                        */
    TWord     PageNbr;                        /* 内存页数目                        */
    TWord     PageAvail;                      /* 可用内存页数目                    */
    TBitMask  PageTags[MEM_BUDDY_PAGE_TAGS];  /* 内存页是否可用标记                */
    TWord     NodeNbr;
    TByte     NodeTags[MEM_BUDDY_NODE_TAGS];
} TMemBuddy;

extern TState xBuddyInit(TMemBuddy* pBuddy, TChar* pAddr, TWord pages, TWord pagesize, TError* pError);
extern TState xBuddyDeinit(TMemBuddy* pBuddy, TError* pError);
extern TState xBuddyMemMalloc(TMemBuddy* pBuddy, TWord length, void** pAddr, TError* pError);
extern TState xBuddyMemFree(TMemBuddy* pBuddy, void* pAddr, TError* pError);

#endif

#endif /* _TCL_MEMORY_BUDDY_H  */

trochili

/*****************************************************************
*                                     Trochili RTOS Kernel                                      *
*                                  Copyright(C) 2015 LIUXUMING                                  *
*                                       www.trochili.com                                        *
*****************************************************************/
#include <string.h>

#include "tcl.config.h"
#include "tcl.types.h"
#include "tcl.cpu.h"
#include "tcl.debug.h"
#include "tcl.mem.buddy.h"

#if ((TCL_MEMORY_ENABLE) && (TCL_MEMORY_BUDDY_ENABLE))

/* BUDDY属性标记定义 */
#define BUDDY_PROP_NONE           (0x0)                  /* BUDDY空属性标记                     */
#define BUDDY_PROP_READY          (0x1<<0u)              /* BUDDY就绪标记                       */

#define PAGES_AVAIL (0x1<<7u)

#define PARENT_NODE(x) (((x) - 1u) / 2u)
#define LEFT_NODE(x) ((x) * 2u + 1u)
#define RIGHT_NODE(x) ((x) * 2u + 2u)

/* 调整x到和它最相近且不小于它的2的幂数 */
static TWord clp2(TWord x)
{
    x = x - 1U;
    x = x | (x >> 1U);
    x = x | (x >> 2U);
    x = x | (x >> 4U);
    x = x | (x >> 8U);
    x = x | (x >> 16U);
    return (x + 1U);
}

/* 调整x到和它最相近且不大于它的2的幂数 */
static TWord flp2(TWord x)
{
    x = x | (x >> 1U);
    x = x | (x >> 2U);
    x = x | (x >> 4U);
    x = x | (x >> 8U);
    x = x | (x >> 16U);
    return (x - (x >> 1U));
}

/* 计算x以2为底的对数 */
static TWord log2(TWord x)
{
    TWord i = 0;
    while (!(x &0x1))
    {
        i++;
        x = x >> 1;
    }

    return i;
}

/* 计算2的x次幂 */
static TWord power2(TWord x)
{
    TWord i = 1;
    while (x)
    {
        i = i << 1;
        x--;
    }

    return i;
}


/*****************************************************************
*  功能：分配每个二叉树节点管理的内存页数                                                       *
*  参数：(1) pBuddy  伙伴系统分配器地址                                                         *
*  返回: 无                                                                                     *
*  说明：                                                                                       *
*****************************************************************/
static void BuildPageTree(TMemBuddy* pBuddy)
{
    TIndex node;
    U32 logn;
    U32 x;
    U32 y;

    /* 计算树的节点总数 */
    pBuddy->NodeNbr  = pBuddy->PageNbr * 2u  - 1u;

    /* 计算每个节点管理的页数(采用以2为底的对数来表示) */
    logn = log2(pBuddy->PageNbr) & 0x3f;
    node = 0u;
    for (y = 0; y <= logn; y++)
    {
        x = (pBuddy->PageNbr >> (logn - y));
        while (x--)
        {
            pBuddy->NodeTags[node] = ((logn - y) | PAGES_AVAIL);
            node++;
        }
    }
}


static int GetAvailPages(TMemBuddy* pBuddy)
{
    TByte tag;
    tag = pBuddy->NodeTags[0];
    if (tag & PAGES_AVAIL)
    {
        return power2(tag & 0x3f);
    }
    return 0;
}

/*****************************************************************
*  功能：从伙伴管理器中分配一定数目的页                                                         *
*  参数：(1) pBuddy    伙伴系统分配器对象地址                                                   *
*        (2) pages     需要分配的内存页数                                                       *
*        (3) index     分配得到的内存页号                                                       *
*  返回: (1) 分配到的页面的编号                                                                 *
*  说明：                                                                                       *
*****************************************************************/
static TWord MallocPages(TMemBuddy* pBuddy, TWord pages)
{
    TWord index;
    TWord lvl;
    TWord node;
    TByte tag;
    TByte logn;

    TByte ltag;
    TByte rtag;
    TByte llogn;
    TByte rlogn;

    /* 计算和pages对应的以2为底的对数 */
    logn = log2(pages);

    /* 计算需要遍历的(从root算起)层数 */
    lvl = log2(pBuddy->PageNbr) - logn;

    /* 从根节点开始遍历lvl次，找到可供分配的节点 */
    node = 0u;
    while (lvl--)
    {
        tag = (pBuddy->NodeTags[LEFT_NODE(node)]);
        if ((tag & PAGES_AVAIL) && ((tag & 0x3f) >= logn))
        {
            node = LEFT_NODE(node);
        }
        else
        {
            node = RIGHT_NODE(node);
        }
    }

    /* 取消分配给该节点的内存页 */
    pBuddy->NodeTags[node] = 0u;

    /* 通过节点编号计算内存页编号 */
    index = (node + 1u) * pages - pBuddy->PageNbr;

    /* 回溯调整到根节点路径上的所有节点的可分配内存页数(注意是路径上的全部节点) */
    while (node)
    {
        node  = PARENT_NODE(node);
        ltag = pBuddy->NodeTags[LEFT_NODE(node)];
        rtag = pBuddy->NodeTags[RIGHT_NODE(node)];
        if ((ltag & PAGES_AVAIL) && (rtag & PAGES_AVAIL))
        {
            llogn = (ltag & 0x3f);
            rlogn = (rtag & 0x3f);
            tag   = (llogn > rlogn) ? llogn : rlogn;
            tag   |= PAGES_AVAIL;
        }
        else if (ltag & PAGES_AVAIL)
        {
            tag = ltag;
        }
        else if (rtag & PAGES_AVAIL)
        {
            tag = rtag;
        }
        else
        {
            tag = 0u;
        }

        pBuddy->NodeTags[node] = tag;
    }

    return index;
}


/*****************************************************************
*  功能：线程通用阻塞终止函数,将指定的线程从阻塞队列中终止阻塞                                  *
*  参数：(1) pBuddy    伙伴系统分配器对象地址                                                   *
*        (2) index     待释放的多个内存页的起始页号                                             *
*  返回: 无                                                                                     *
*  说明：                                                                                       *
*****************************************************************/
static TWord FreePages(TMemBuddy* pBuddy, TWord index)
{
    TWord pages;
    TWord node;
    TByte tag;
    TByte logn;
    TWord lvl;

    TByte ltag;
    TByte rtag;
    TByte llogn;
    TByte rlogn;

    /* 计算根节点以2为底的对数 */
    lvl = log2(pBuddy->PageNbr);

    /* 通过内存页编号获得叶子节点编号 */
    node = index + pBuddy->PageNbr - 1u;

    /* 通过该叶子节点向上回溯查找分配该起始内存页的节点, 比对次数最多为树的深度 */
    for (logn = 0; logn <= lvl; logn++)
    {
        /* 如果找到分配该内存(n)页的那个节点 */
        if (!(pBuddy->NodeTags[node] & PAGES_AVAIL))
        {
            break;
        }
        node = PARENT_NODE(node);
    }

    /* 回收该相关内存(n)页,重新计算它可以管理的内存页数 */
    pBuddy->NodeTags[node] = ((logn & 0x3f) | PAGES_AVAIL);
    pages = power2(logn);

    /* 尝试进行进行伙伴节点合并,需要一直遍历到root节点。
       如果是根节点则不需要以下操作 */
    while (node)
    {
        node = PARENT_NODE(node);
        logn++;
        ltag = pBuddy->NodeTags[LEFT_NODE(node)];
        rtag = pBuddy->NodeTags[RIGHT_NODE(node)];

        if ((ltag &PAGES_AVAIL) && (rtag &PAGES_AVAIL))
        {
            llogn = (ltag &0x3f);
            rlogn = (rtag &0x3f);
            if (power2(llogn) + power2(rlogn) == power2(logn))
            {
                tag = ((logn &0x3f) | PAGES_AVAIL);
            }
            else
            {
                tag = (llogn > rlogn) ? llogn : rlogn;
                tag |= PAGES_AVAIL;
            }
        }
        else if (ltag &PAGES_AVAIL)
        {
            tag = ltag;
        }
        else //if (rtag &PAGES_AVAIL)
        {
            tag = rtag;
        }
        pBuddy->NodeTags[node] = tag;
    }

    return pages;
}


/*****************************************************************
*  功能：初始化伙伴内存管理控制结构                                                             *
*  参数：(1) pBuddy    伙伴系统分配器内存地址                                                   *
*        (2) pAddr     可供分配的内存地址                                                       *
*        (3) pagesize  内存页大小                                                               *
*        (4) pages     可供分配的内存页总数                                                     *
*        (5) pError    详细调用结果                                                             *
*  返回: (1) eSuccess  操作成功                                                                 *
*        (2) eFailure  操作失败                                                                 *
*  说明：                                                                                       *
*****************************************************************/
TState xBuddyInit(TMemBuddy* pBuddy, TChar* pAddr, TWord pages, TWord pagesize, TError* pError)
{
    TState state = eFailure;
    TError error = MEM_ERR_FAULT;
    TIndex index;

    TReg32 imask;

    CpuEnterCritical(&imask);
    if (!(pBuddy->Property & BUDDY_PROP_READY))
    {
        /* 调整pages到和它最相近且不大于它的2的幂数 */
        pages = flp2(pages);
        if (pages)
        {
            pBuddy->Property  = BUDDY_PROP_READY;
            pBuddy->PageAddr  = pAddr;
            pBuddy->PageSize  = pagesize;
            pBuddy->PageNbr   = pages;
            pBuddy->PageAvail = pages;

            /* 设置所有内存都处于可分配状态 */
            for (index = 0; index < MEM_BUDDY_PAGE_TAGS; index++)
            {
                pBuddy->PageTags[index] = ~0U;
            }

            /* 创建二叉树控制结构 */
            BuildPageTree(pBuddy);

            error = MEM_ERR_NONE;
            state = eSuccess;
        }
    }
    CpuLeaveCritical(imask);

    *pError = error;
    return state;
}


/*****************************************************************
*  功能：销毁伙伴内存管理控制结构                                                               *
*  参数：(1) pBuddy     伙伴系统分配器内存地址                                                  *
*        (2) pError     详细调用结果                                                            *
*  返回: (1) eSuccess   操作成功                                                                *
*        (2) eFailure   操作失败                                                                *
*  说明：                                                                                       *
*****************************************************************/
TState xBuddyDeinit(TMemBuddy* pBuddy, TError* pError)
{
    TReg32 imask;
    TState state = eFailure;
    TError error = MEM_ERR_UNREADY;

    CpuEnterCritical(&imask);
    if (pBuddy->Property & MEM_PROP_READY)
    {
        memset(pBuddy->PageAddr, 0u, pBuddy->PageSize * pBuddy->PageNbr);
        memset(pBuddy, 0u, sizeof(TMemBuddy));
        error = MEM_ERR_NONE;
        state = eSuccess;
    }
    CpuLeaveCritical(imask);

    *pError = error;
    return state;
}


/*****************************************************************
*  功能：从伙伴系统中申请内存                                                                   *
*  参数：(1) pBuddy    伙伴系统分配器对象地址                                                   *
*        (2) len       需要分配的内存长度                                                       *
*        (3) pAddr2    分配得到的内存地址指针                                                   *
*        (4) pError    详细调用结果                                                             *
*  返回: (1) eSuccess  操作成功                                                                 *
*        (2) eFailure  操作失败                                                                 *
*  说明：                                                                                       *
*****************************************************************/
TState xBuddyMemMalloc(TMemBuddy* pBuddy, TWord length, void** pAddr2, TError* pError)
{
    TState state = eFailure;
    TError error = MEM_ERR_UNREADY;
    TReg32 imask;
    TWord pages;
    TWord index;
    TWord avail;
    TIndex x;
    TIndex y;
    TIndex i;

    CpuEnterCritical(&imask);

    if (pBuddy->Property &BUDDY_PROP_READY)
    {
        /* 如果申请的内存长度没有超过BUDDY的范围 */
        if (length <= (pBuddy->PageNbr * pBuddy->PageSize))
        {
            /* 计算需要分配多少内存页 */
            pages = (length + pBuddy->PageSize - 1u) / (pBuddy->PageSize);

            /* 调整pages到和它最相近且不小于它的2的幂数 */
            pages = clp2(pages);

            avail = GetAvailPages(pBuddy);
            if (avail >= pages)
            {
                /* 获得分配的内存页编号 */
                index = MallocPages(pBuddy, pages);

                /* 标记该部分内存页已经被分配 */
                for (i = 0; i < pages; i++)
                {
                    y = ((index + i) >> 5);
                    x = ((index + i) & 0x1f);
                    pBuddy->PageTags[y]  &= ~(0x1 << x);
                }
                pBuddy->PageAvail -= pages;

                /* 通过内存页编号获得内存地址 */
                *pAddr2 = (void*)(pBuddy->PageAddr + index * pBuddy->PageSize);
               
                error = MEM_ERR_NONE;
                state = eSuccess;
            }
            else
            {
                *pAddr2 = (void*)0;
                error = MEM_ERR_NO_MEM;
            }
        }
        else
        {
            error = MEM_ERR_NO_MEM;
        }
    }
    CpuLeaveCritical(imask);

    *pError = error;
    return state;
}


/*****************************************************************
*  功能：向伙伴系统中释放内存                                                                   *
*  参数：(1) pBuddy    伙伴系统分配器对象地址                                                   *
*        (2) pAddr     待释放的内存地址                                                         *
*        (3) pError    详细调用结果                                                             *
*  返回: (1) eSuccess  操作成功                                                                 *
*        (2) eFailure  操作失败                                                                 *
*  说明：                                                                                       *
*****************************************************************/
TState xBuddyMemFree(TMemBuddy* pBuddy, void* pAddr, TError* pError)
{
    TState state = eFailure;
    TError error = MEM_ERR_UNREADY;
    TReg32 imask;
    TWord index;
    TIndex x;
    TIndex y;
    TBitMask tag;
    TWord pages;
    TIndex i;

    CpuEnterCritical(&imask);
    if ((pBuddy->Property &BUDDY_PROP_READY))
    {
        /* 检查被释放的地址是否在伙伴系统管理的内存范围内 */
        if (((char*)pAddr >= (char*)(pBuddy->PageAddr)) &&
            ((char*)pAddr < ((char*)(pBuddy->PageAddr) + pBuddy->PageSize* pBuddy->PageNbr)))
        {
            /* 通过内存地址计算起始页编号 */
            index = ((char*)pAddr - (char*)(pBuddy->PageAddr)) / pBuddy->PageSize;

            /* 检查内存页管理标记，避免再次释放已经释放过的内存页地址 */
            y = (index >> 5);
            x = (index & 0x1f);
            tag = pBuddy->PageTags[y] & (0x1 << x);
            if (tag == 0)
            {
                /* 释放该页起始的内存 */
                pages = FreePages(pBuddy, index);

                /* 标记该部分内存可以被分配 */
                for (i = 0; i < pages; i++)
                {
                    y = (index + i) >> 5;
                    x = (index + i) & 0x1f;
                    pBuddy->PageTags[y] |= (0x1 << x);
                }

                pBuddy->PageAvail += pages;
                error = MEM_ERR_NONE;
                state = eSuccess;
            }
            else
            {
                error = MEM_ERR_DBL_FREE;
            }
        }
        else
        {
            error = MEM_ERR_BAD_ADDR;
        }
    }
    CpuLeaveCritical(imask);

    *pError = error;
    return state;
}

#endif

FreeRTOS

楼主，代码看起来也费时呢，请问能不能用简单的言语来概括下这个算法的优点呢？

龙之谷

单纯仰视一下.....

ricefat

仰视大神

八度空间

仰视大神。。。

负西弱

这个叼，很早就听说过伙伴算法了~~但至今还没看过具体是怎么实现的、有什么优缺点，楼主来科普一下吧

FantaSy_

仰视大神。。。

正点原子

谢谢分享.

Jalon

这个内存管理 稳定吗？

Jalon

如果稳定的话 我直接移到产品上面去了

yyx112358

我之前看书时总结的几种内存算法对比：
a. 边界标识：较为占空间，回收时间为定值
b. 伙伴系统：较快，有碎片
c. 堆紧缩：内存未被占满时分配很快，算法简单。但最终回收时的紧缩开销极大
d. 等大小内存块：较快，有碎片（原子方法）

哈哈哈哈

yyx112358 发表于 2016-3-8 20:12
我之前看书时总结的几种内存算法对比：
a. 边界标识：较为占空间，回收时间为定值
b. 伙伴系统：较快，有 ...

能不能解释一下