用 C 语言实现单片机中的内存管理单元(MMU)

================================================================================
标题: 用 C 语言实现单片机中的内存管理单元(MMU)
作者: 叶飞虎
日期: 2018.12.16
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

    在单片机中内存空间很小，主要是为了省硬件成本，如: coterx m3/m4 的 64KB/192KB, Quectel M26 的 256KB/512KB 等等都不带 MMU(内存管理单元)。为了实现内存动态分配和释放，要么使用厂家库的 MMU，要么自己写 MMU。

    在不同单片机中有些只有片内存储单元，而有些可支持多个片外RAM，而且片外尺寸要大很多，有 1MB/2MB 等等。需要把片内和片外内存都管理起来，且要支持不定尺寸的内存分配和释放，所以自己就设计开发了内存管理，为了与 C 中的 malloc 和 free 一样好用就把分配和释放内存函数定义如下：

// 分配指定尺寸的内存，若返回值非 NULL 则为分配成功的内存地址，否则分配失败
void* Malloc(int ASize);

// 释放已分配的内存
void  Free(void* AMemory);

    本内存管理算法采用 bit 位的完全二叉树来管理分配和释放，而内存管理所需要的另外内存开销为每 1KB 需要 16 字节，且内存分配的最小单元为 16 字节，即使分配 1 字节也占用 16 字节空间。其实最小单元字节数可以根据自己需要来调整，最小单元字节数越大则内存管理的额外开销就越小，如果最小单元字节数为 32 时 1KB 的开销只要 8 字节。若分配尺寸在最小单元字节数之内(含)时，只需要 1bit 来做标志；否则就需要 2bits 来做标志，在二叉树的分支结点和叶结点各一个 bit 位来做标志，分支结点对应分配内存的起始点，而叶结点为分配内存的最后一个单元对应点。

    下面通过举例来说明内存分配的过程及局限性：

例一
   若内存管理只有 1KB 空间，则下面按步骤来描述可分配及分配占用情况：
   1. [0..1023: 空闲] 可分配尺寸区间为 [1..1024]；
   2. Malloc(700) 分配成功且空间占用情况如下:
      [0..703: 占用],[704..767: 空闲],[768..1023: 空闲]
      这时的可分配尺寸区间为 [1..256]；
   3. Malloc(300) 分配失败，因为 300 超过可分配尺寸区间；
   4. Malloc(236) 分配成功且空间占用情况如下:
      [0..703: 占用],[704..767: 空闲],[768..1007: 占用],[1008..1023: 空闲]
      这时的可分配尺寸区间为 [1..64]；
   5. Malloc(40) 分配成功且空间占用情况如下:
      [0..703: 占用],[704..751: 占用],[752..767: 空闲],[768..1007: 占用],[1008..1023: 空闲]
      这时的可分配尺寸区间为 [1..16]；
   6. Malloc(16) 分配成功且空间占用情况如下:
      [0..703: 占用],[704..751: 占用],[752..767: 空闲],[768..1007: 占用],[1008..1023: 占用]
      这时的可分配尺寸区间为 [1..16]；
   7. Malloc(16) 分配成功且空间占用情况如下:
      [0..703: 占用],[704..751: 占用],[752..767: 占用],[768..1007: 占用],[1008..1023: 占用]
      这时的可分配尺寸为 0，分配情况为：{700, 236, 40, 16, 16}。

例二
   若内存管理只有 14KB 空间，则下面按步骤来描述可分配及分配占用情况：
   1. [2KB: 空闲],[4KB: 空闲],[8KB: 空闲], 可分配尺寸区间为 [1..8KB]；
   2. Malloc(10<<10) 分配失败，因为 10KB 超过可分配尺寸区间；
   3. Malloc(7<<10) 分配成功且空间占用情况如下:
      [2KB: 空闲],[4KB: 空闲],[0..7KB-1: 占用],[7KB..8KB-1: 空闲]
      这时的可分配尺寸区间为 [1..4KB]；
   4. Malloc(3<<10) 分配成功且空间占用情况如下:
      [2KB: 空闲],[0..3KB-1: 占用],[3KB..4KB-1: 空闲],[0..7KB-1: 占用],[7KB..8KB-1: 空闲]
      这时的可分配尺寸区间为 [1..2KB]；
   5. Malloc(1<<10) 分配成功且空间占用情况如下:
      [0..1KB-1: 空闲],[1KB..2KB-1: 占用],[0..3KB-1: 占用],..,[7KB..8KB-1: 空闲]
      这时的可分配尺寸区间为 [1..1KB]；
   6. Malloc(1<<10) 分配成功且空间占用情况如下:
      [0..1KB-1: 占用],[1KB..2KB-1: 占用],[0..3KB-1: 占用],..,[7KB..8KB-1: 空闲]
      这时的可分配尺寸区间为 [1..1KB]；
   ... ...

内存管理的头文件(KYMemory.h)如下：

// =======================================
// Unit   : memory manager (内存管理单元)
// Version: 4.0.1.0 (build 2018.12.16)
// Author : Kyee Ye
// Email  : kyee_ye(at)126.com
// Copyright (C) Kyee workroom
// =======================================

#ifndef _KYMemory_H_
#define _KYMemory_H_

#ifdef __cplusplus
extern \"C\"
{
#endif

// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

/* 内存分配/释放函数 */

// 分配指定尺寸的内存
void* Malloc(int ASize);

// 释放已分配的内存
void  Free(void* AMemory);

// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

/* 内存管理的相关函数 */

// ---------------- 内存管理使用示例 ----------------

/*
// 1KB 内存项数
#define _1KB_Count1 64

// 索引项的全局占用空间
static T1KBIndex  L_Indexs[_1KB_Count1];

// 内存项的全局占用空间
static T1KBItem   L_Items[_1KB_Count1];

// 内存块列表
static TMemBlock  L_Blocks[] = {{_1KB_Count1, L_Items, L_Indexs}};

// 内存管理的全局加锁
static void L_Lock(void)
{
   // ... ...
}

// 内存管理的全局解锁
static void L_Unlock(void)
{
   // ... ...
}

// 扩展内存分配
static void* L_Malloc(int ASize)
{
   return malloc(ASize);
}

// 扩展内存释放
static void L_Free(void* AMemory)
{
   free(AMemory);
}

// on-init: 在工程的初始化函数中
{
   // 初始化内存管理
   KYMemory_Init(&L_Lock, &L_Unlock, &L_Malloc, &L_Free,
                  L_Blocks, sizeof(L_Blocks)/sizeof(L_Blocks[0]));

   // 其它初始化
   ... ...
}

// on-fini: 在工程的结束函数中
{
   // 其它释放
   ... ...

   // 释放内存管理
   KYMemory_Fini();
}
*/

// ---------------- 类型定义 ----------------

// 内存管理的内存项/索引项类型
typedef unsigned char T1KBItem[1<<10]; // 1KB 的内存项
typedef unsigned char T1KBIndex[1<<4]; // 1KB 的索引项

// 锁的回调函数指针类型
typedef void  (*TLockFunc)(void);

// 第三方内存分配/释放函数指针类型
typedef void* (*TMalloc)(int ASize);
typedef void  (*TFree)(void* AMemory);

// 内存块项结构
typedef struct
{
   int         Count;      // 内存块的 1KB 内存项数
   T1KBItem*   Items;      // 内存块的内存项列表, 项数为: Count
   T1KBIndex*  Indexs;     // 内存块的索引项列表, 项数为: Count
} TMemBlock;

// ---------------- 构造函数和析构函数 ----------------

/* 内存管理初始化
参数:
   ALock    加锁函数
   AUnlock  解锁函数
   AMalloc  第三方内存分配函数, 注: 不允许为当前的 Malloc 函数
   AFree    第三方内存释放函数, 注: 不允许为当前的 Free 函数
   ABlocks  内存块列表, 列表项数为: ACount
   ACount   内存块的项数
返回值:
   >0       初始化成功, 返回内存块的项数
    0       初始化失败, 无合法内存块
   -1       初始化失败, 参数不合法
   -2       初始化失败, 表示已初始化
   -3       初始化失败, 表示正在初始化
*/
int   KYMemory_Init(TLockFunc  ALock,   TLockFunc AUnlock,
                    TMalloc    AMalloc, TFree     AFree,
                    TMemBlock* ABlocks, int       ACount);

// 内存管理释放
void  KYMemory_Fini(void);

// ---------------- 属性方法 ----------------

// 1KB 内存的总项数, 若未初始化则返回值为 -1
int   KYMemory_1KBCount(void);

// 内存的总单元个数(注: 每个单元 16 字节), 若未初始化则返回值为 -1
int   KYMemory_CellCount(void);

// 内存的已分配单元个数(注: 每个单元 16 字节), 若未初始化则返回值为 -1
int   KYMemory_UsedCount(void);

// 内存块列表的项数, 若未初始化则返回值为 -1
int   KYMemory_BlockCount(void);

#ifdef __cplusplus
}     // end extern \"C\"
#endif

#endif

   本内存管理单元已用于生产，可靠性都已经过严格的压力测试，现公开内存管理的源码，而源码文件(KYMemory.c)因涉及版权原因已做了代码混淆处理，但不影响使用。

内存管理单元代码(KYMemory.rar)下载如下：
https://pan.baidu.com/s/1eTWTYD0#list/path=%2Fshares%2Fsources%2F_open&parentPath=%2F