基于Buddy算法的动态内存内存管理方案(GD32 小红板实现)

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 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-&gtageNbr * 2u - 1u;     /* 计算每个节点管理的页数(采用以2为底的对数来表示) */     logn = log2(pBuddy-&gtageNbr) & 0x3f;     node = 0u;     for (y = 0; y <= logn; y++)     {      x = (pBuddy-&gtageNbr >> (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-&gtageNbr) - 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-&gtageNbr;     /* 回溯调整到根节点路径上的所有节点的可分配内存页数(注意是路径上的全部节点) */     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-&gtageNbr);     /* 通过内存页编号获得叶子节点编号 */     node = index + pBuddy-&gtageNbr - 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 &ampAGES_AVAIL) && (rtag &ampAGES_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 &ampAGES_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